8月15日学习

14.6 Rust语言中的同步机制

引用计数

原子操作

执行同步

条件变量

互斥信号量

读写锁

Higher-level synchronization objects in Rust

Arc: A thread-safe atomically Reference-Counted pointer, which can be used in multithreaded environments

Barrier: Ensures multiple threads will wait for each other to reach a point in the program, before continuing execution all together 执行同步

Condvar: Condition Variable, providing the ability to block a thread while waiting for an event to occur 条件变量，让权等待

Mutex: Mutual Exclusion mechanism, which ensures that at most one thread at a time is able to access some data 访问共享数据机制

RwLock: Provides a mutual exclusion mechanism which allows multiple readers at the same time, while allowing only one writer at a time 读写锁

Rc（Reference Counting）引用计数

A single-threaded reference-counting pointer. 'Rc' stands for 'Reference Counted'

第十五讲 死锁和并发错误检测

15.1 死锁概念

由于竞争资源或者通信关系，两个或更多线程在执行中出现，永远相互等待只能由其它进程引发的事件

进程访问资源的流程

资源类型R1，R2，...Rm，CPU执行时间、内存空间、IO设备等

每类资源Ri有Wi个实例

进程访问资源的流程，请求/获取，申请空闲资源，使用/占用，进程占用资源，释放，资源状态由占用变成空闲

资源分类

1、可重用资源（Reusable Resouce）资源不能被删除且在任何时刻只能有一个进程使用；进程释放资源后，其他进程可重用。示例：硬件：处理器、IO通道、主和副存储器、设备等；软件：文件、数据库和信号量等数据结构；可能出现死锁：每个进程占用一部分资源并请求其它资源

2、消耗资源（Consumable resource）资源创建和销毁，示例：在IO缓冲区的中断、信号、消息等。可能出现死锁：进程间相互等待接收对方的消息

资源分配图：

描述资源和进程间的分配和占用关系的有向图

出现死锁的必要条件：

互斥：任何时刻只能有一个进程使用一个资源实例

持有并等待：进程保持至少一个资源，并正在等待获取其他进程持有的资源

非抢占：资源只能在进程使用后自愿释放

循环等待：存在等待进程集合{P0，P1，P2....PN}，P0正在等待P1所占用的资源，P1正在等待P2占用的资源，PN-1在等待PN所占用的资源，PN正在等待P0所占用的资源

15.2 死锁的处理方法

死锁预防（Deadlock Prevention）：确保系统永远不会进入死锁状态

死锁避免（Deadlock Avoidance）：在使用前进行判断，只允许不会出现死锁的进程请求资源

死锁检测和恢复（Deadlock Detection & Recovery）：在检测到运行系统进入死锁状态后，进行恢复

在实际OS中，由应用进程处理死锁，OS忽略死锁，这是大多数OS，包括UNIX的做法

死锁预防：限制申请方式

预防是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件

互斥：把互斥的共享资源封装成可同时访问

持有并等待：进程请求资源时，要求它不持有任何其他资源，仅允许进程在开始执行时，必须一次把所有的资源申请到，资源利用率低

非抢占，如进程请求不能立即分配的资源，则释放已占有资源，只在能够同时获得所有需要资源时，才执行分配操作

循环等待：对资源排序，要求进程按顺序请求资源

死锁避免：利用额外的先验信息，在分配资源的时候判断是否会出现死锁，只在不会死锁的时候分配资源；要求进程事先声明需要资源的最大数目；限定提供与分配的资源数目，确保满足进程的最大需求；动态检查资源分配状态，确保不会出现环形等待；

系统资源分配安全状态：当进程请求资源时，系统判断分配后是否处于安全状态

系统处于安全状态：针对所有已占用进程，存在安全序列；

序列<P1, P2, ..., PN>是安全的，Pi要求的资源<=当前可用资源+所有Pj持有资源，其中j<i

如Pi的资源请求不能立即分配，则Pi等待所有Pj（j<i）完成

Pi完成后，Pi+1可得到所需资源，执行并释放所分配的资源

最终整个序列的所有Pi都能获得所需资源

安全状态与死锁的关系：系统处于安全状态，一定没有死锁；系统处于不安全状态，可能出现死锁，避免死锁就是确保系统不会进入不安全状态；

15.3 银行家算法

死锁避免的方法，以银行贷款分配策略为基础，判断并保证系统处于安全状态

1、客户在第一次申请贷款时，声明所需最大资金量，在满足所有贷款要求并完成项目时，及时归还

2、在客户贷款数量不超过银行拥有的最大值时，银行家尽量满足客户需要

类比： 银行家——OS 资金——资源 客户——申请资源的线程

n=线程数量 m=资源类型数量

Max（总需求量）：n×m矩阵 线程Ti最多请求类型Rj的资源 Max[i,j]个实例

Available（剩余空闲量）：长度为m的向量 当前有Available[i]个类型Rj的资源实例可用

Allocation（已分配量）：n×m矩阵 线程Ti当前分配了Allocation[i,j]个Rj的实例

Need（未来需要量）：n×m矩阵 线程Ti未来需要Need[i,j]个Rj资源实例

Need[i,j] = Max[i,j] - Allocation[i,j] 未来需要的等于最大的减去你已经分配的

安全状态判断

1、Work和Finish分别是长度为m和n的向量初始化：

Work = Available //当前资源剩余空闲量

Finish = false for i：1,2，...,n //线程i没结束

2、寻找线程Ti

（a）Finish[i]=false //接下来找出Need比Work小的线程i

(b) Need[i]<=Work

没有找到满足条件的Ti，转4

3、Work = Work + Allocation[i] //线程i的资源需求量小于当前剩余空闲资源量，所以配置给它再回收

Finish[i] = true

转2

4、如所有线程Ti满足Finish[i]==true //所有线程的Finish为True，表明系统处于安全状态

则系统处于安全状态

核心是当前的剩余资源可以满足某一个线程的未来需要，并且这种迭代循环到最后能够满足所有的线程的需要，也就是相当于找到了一个安全序列

初始化：

Requesti线程Ti的资源请求向量

Request[j]线程Ti请求资源Rj的实例

循环：

1、如果Requesti<=Need[i]，转到步骤2，否则，拒绝资源申请，因为线程已经超过了其最大要求

2、如果Requesti<=Available，转到步骤3。否则，Ti必须等待，因为资源不可用

3、通过安全状态判断来确定是否分配资源给Ti：生成一个需要判断状态是否安全的资源分配环境

Available = Available- Requesti；

Allocation[i]=Allocation[i]+Requesti；

Need[i]=Need[i]- Requesti；

调用安全状态判断：

如果返回结果是安全，将资源分配给Ti

如果返回结果是不安全，系统会拒绝Ti的资源请求

15.4 死锁检测

允许系统进入死锁状态，维护系统资源分配图，定期调用死锁检测算法来搜索图中是否存在死锁，出现死锁时，用死锁恢复机制进行恢复

Available：长度为m的向量，每种类型可用资源的数量

Allocation：一个n×m矩阵，当前分配给各个进程每种类型资源的数量，进程Pi拥有资源Rj的Allocation[i,j]个实例

1、Work和Finish分别是长度为m和n的向量初始化：

（a）Work = Available //当前资源剩余空闲量

（b）Allocation[i]>0时，Finish[i] = false 否则 Finish[i] = true //Finish为线程是否结束

2、寻找线程Ti满足：

（a）Finish[i]=false //线程没有结束的线程，且此线程将需要的资源量小于当前空闲资源量

(b) Requesti<=Work

没有找到满足条件的i，转4

3、Work = Work + Allocation[i] //把找到的线程拥有的资源释放回当前空闲资源中

Finish[i] = true

转2

4、如某个Finish[i]==false，系统处于死锁状态 //如果有Finish为false，表明系统处于死锁状态

算法需要O(m*n^2)操作检测是否系统处于死锁状态

死锁检测的时间和周期选择依据：

死锁多久可能会发生，多少进程需要被回滚

资源图可能由多个循环：难于分辨“造成”死锁的关键进程

终止所有的死锁进程，一次只终止一个进程直到死锁消除，

终止进程的顺序应该是：

进程的优先级；进程已运行时间以及还需运行时间；进程已占用资源；进程完成需要的资源；终止进程数目；进程是交互还是批处理

选择被抢占进程：最小成本目标

进程回退：返回到一些安全状态，重启进程到安全状态

可能出现饥饿：同一进程可能一直被选作被抢占者

12.5 并发错误检测

Concurrency Bug

Concurrency Bug Detection

AVIO

ConSeq & ConMem

第十六讲 进程通信

16.1 进程通信概念

IPC，Inter-Process Communication

进程通信是进程进行通信和同步的机制

IPC提供2个基本操作：发送操作：send（message）；接收操作：receive（message）

进程通信流程：在通信进程间建立通信链路，通过send/receive交换消息

进程链路特征：物理（如，共享内存，硬件总线）；逻辑（如，逻辑属性）

间接通信：依赖于操作系统内核完成的进程间的通讯，首先在通讯进程和内核之间建立相应的机构，能够支持这种通讯，比如说建立消息队列，然后一个进程可以把信息发送到内核的消息队列上，然后另一个进程从这里读出来，从而实现进程A和B之间的通讯，这个过程它的生命周期甚至可以不一样，比如说A发信息的时候B还没有创建，而B接收数据的时候A可能已经关闭了

直接通信：在两个进程之间建立一个通讯信道，就是我们这里的共享信道，由于进程之间直接进行交流，因此两个进程必须同时存在才能够进行通讯，发方向共享信道里面发送数据，收方从共享信道里读取数据

直接通信

进程必须正确地命名对方

send（P，message）-发送信息到进程P

receive（Q，message）-从进程Q接受消息

通信链路的属性：1、自动建立链路；2、一条链路恰好对应一对通信进程；3、每对进程之间只有一个链路存在；4、链接可以是单向的，但通常为双向的

间接通信

通过OS维护的消息队列实现进程间的消息接收和发送，每个消息队列都有一个唯一的标识，只有共享了相同消息队列的进程，才能够通信；因此可以通过内核的安全机制，实现两个进程之间通讯的保密性；

通信链路的属性：1、只有共享了相同消息队列的进程，才建立连接；2、连接可以是单向或双向；3、消息队列可以与多个进程相关联；4、每对进程可以共享多个消息队列

通信流程：1、创建一个新的消息队列；2、通过消息队列发送和接收消息；3、销毁消息队列

基本通信操作：

send（A，message）-发送消息到队列A

receive（A，message）-从队列A接受消息

进程通信可划分为阻塞（同步）或非阻塞（异步）

阻塞通信：阻塞发送：发送者在发送消息后进入等待，直到接受者成功收到；阻塞接收：接受者在请求接收消息后进入等待，直到成功收到一条消息

非阻塞通信：非阻塞发送：发送者在消息发送后，可立即进行其他操作；非阻塞接收：没有消息发送时，接收者在请求接收消息后，接收不到任何消息

通信链路缓冲

进程发送的消息在链路上可能有3种缓冲方式

1、 0容量：发送方必须等待接收方

2、有限容量：通信链路缓冲队列满时，发送方必须等待

3、无限容量：发送方不需要等待

16.2 信号和管道：OS提供的两种简单的通讯机制

信号（Signal）：进程间的软件中断通知和处理机制，如：SIGKILL、SIGSTOP、SIGCONT等，

信号的接收处理：捕获（catch）：执行进程指定的信号处理函数被调用；忽略（Ignore）：执行操作系统指定的缺省处理，例如：进程终止、进程挂起等；屏蔽（Mask）：禁止进程接收和处理信号，可能是暂时的（当处理同样类型的信号）

不足：传送的信息量小，只有一个信号类型

作为快速响应机制，比别的通讯机制要快

信号的实现：首先进程在启动的时候，需要注册相应的信号处理例程给操作系统内核，以便OS在有相应的信号送过来的时候，它能够知道去执行哪一个处理函数，这是注册，然后是有其他进程或者说其他设备发出信号的时候，那么OS内核负责把这个信号送给指定的进程，并且启动其中的信号处理函数，然后执行信号处理函数，完成相应的处理，例如将当前正在执行的进程掐掉，或者说把它暂停，或者忽视

管道（pipe）

进程间基于内存文件的通信机制：子进程从父进程继承文件描述符，这几个缺省的文件描述符：0 stdin，1 stdout，2 stderr，在子进程里都是有继承的；

通讯时进程不关心另一端是谁，只关心通讯的管道是谁，并不关心另一端是谁往里面放数据，数据可能从键盘、文件、程序读取；可能写入到终端、文件、程序

与管道相关的系统调用：

读管道：read（fd，buffer，nbytes） fd是文件描述符 scanf是基于它实现的

写管道：write（fd，buffer，nbytes） printf是基于它实现的

创建管道：pipe（rgfd） rgfd是2个文件描述符组成组成的数组；rgfd[0]是读文件描述符；rgfd[1]是写文件描述符