早期人们设计程序，采用顺序执行，在处理器上的执行有严格的顺序，即在一个操作结束后，才进行后面的操作，这称为程序内部顺序性；如果计算任务需要多个程序完成，这些程序按照调用次序有序执行，则称为程序外部顺序性。顺序程序设计具有如下特性：执行的顺序性、环境的封闭性、结果的确定性、过程的可再现性。

操作系统的基本控制和管理都围绕进程展开，最复杂的就是由于支持并发并行机制而引起的。自从操作系统引入并发程序设计技术后，程序的执行不再是顺序的，一个顺序未执行完而另一个程序便已经开始执行了，程序外部的顺序特性小时，程序与计算不再一一对应。

让程序并发执行能发挥CPU和设备的并行工作能力，从而提高计算机系统效率，一个程序被设计成可与其他程序并发执行，这这程序设计方法成为并发程序设计。

为协调好进程与进程之间的关系，避免因为同时使用资源而产生冲突，我们就有了锁的机制，即对共同享有的资源互斥使用，这就是这一部分主要讨论的内容。

并发进程

程序的并发执行

操作系统的的控制和管理都围绕着进程展开，其中复杂性是由于支持并发并行机制引发的。让程序并发执行能发挥CPU和设备的并行工作能力，从而提高计算机系统的效率。一个程序被设计成可与其他程序并发执行，则这种程序设计方法称为并发程序设计，操作系统应该具有多道程序动态分配资源、调度他们并发执行及协调它们协同工作的能力。

并发进程的特性

并发进程可能是无关的，也可能是交互的。 无关是指分别在不同的变量集合上操作，一个进程执行和其他并发进程进展无关，两者不会影响另一个进程的变量；交互实质并发进程共享某些变量，一个进程执行可能会因想到其他进程的执行结果，且两进程之间存在制约关系。

并发进程的无关性是进程与时间无关的一个充分条件，这一条件在1966年首先由Bernstein提出，称为Bernstein条件。

Bernstein条件简单地说，就是如果两个进程执行过程由数据冲突（Data hazard），那么这两个进程就无法并行执行。

• R(Pi)={a1,a2,…,an}，程序P在执行期间读变量集。
• W(Pi)={b1,b2,…,bm}，程序P在执行期间写变量集。

若两个进程的R(P)与W(P)集合之间不存在纠葛，说明并发进程执行与时间无关，即这两个进程，爱什么时间并行执行就什么时间并行执行，在时间上重叠也可以，不重叠也可以。

那么描述这个关系就是R(P1)和W(P2)相交为空，且R(P2)和W(P1)相交为空，且W(P1)和W(P2)相交为空，这就是Bernstein条件。R(P1)∩W(P2)UR(P1)∩W(P2)UW(P1)∩W(P2)=Ø。

进程的交互：竞争和协作

批处理系统建立多个批处理进程，共享同一套计算机系统资源，使得原本不存在逻辑关系的诸进程因共享资源而产生交互和制约关系，这是间接制约关系，又称互斥关系，操作系统必须协调进程对共享资源的争用。进程互斥是指若干进程因相互争夺独占性资源而产生的竞争制约关系。

一个作业可涉及一组并发进程，为了完成共同任务需要分工协作。进程同步是指为了完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。

临界区管理

互斥和临界区

并发进程中与共享变量有关的程序段称为临界区。

临界区概念由Dijkstra在1965年首先提出，共享变量的并发进程应遵守临界区调度的三个原则：

1. 一次至多只有一个进程进入临界区内执行
2. 如果已有进程在临界区中，试图进入次临界区的其他进程应等待
3. 进入临界区内的进程应在有限时间内退出，以便让等待队列中的一个进程进入

由此可总结为三句话：互斥使用，有空让进；忙则要等，有限等待；择一而入，算法可行。算法可行是指不能因为调度策略的选择，而导致饥饿、死锁现象。

信号量与PV操作

同步和同步机制

生产者－消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。生产者进程可以是计算进程、发送进程，消费者进程可以是打印进程、接受进程等等。解决好生产者与消费者的问题就解决了一类并发进程的同步问题。

我们生产者和消费者之间，建立一个缓冲区，只要缓冲区不满，生产者所生产的产品就可以投入缓冲区，同样，只要缓冲区非空，消费者就可以从缓冲区取走病消耗产品。

信号量与PV操作

在1965年，由Dijkstra提出的同步工具：信号量和PV操作。即将交通管制中多种颜色的信号灯管理方法引入操作系统，让多个进程通过特殊变量展开交互。

信号量按照用途可以分为两种：公用信号量，也称为互斥信号量，联系一组并发进程，相关进程均可在此信号量上执行PV操作，初值为1，实现进程互斥；私有信号量，联系一组并发进程，仅允许此信号量所拥有的进程执行P操作，而且他相关进程可在其上实行V操作，初值往往为0或正整数，多用于并发进程同步。信号量按照取值分类可分为两种：二值信号量，仅允许为0或1，主要用于解决互斥问题；一般信号量，也成技术信号量，允许取大于1的整数值，主要用于解决同步问题。

一般信号量

PV操作的原语描述如下：

1. P(s)：将信号量自减1，若小于0，则该进程阻塞，排入与信号量s有关的进程队列中，若结果大于等于0，则继续执行。
2. V(s)：将信号量自加1， 若结果小于或等于0，则从队列中释放一个进程，并转为就绪态，若结果大于0，则继续执行该进程。

记录型信号量和PV操作定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

typedef struct semaphore {
  int value;
  struct pcb *list;
}
void P(semaphore s) {
  s.value--;
  if(s.value<0) sleep(s.list);
}
void V(semaphore s) {
  s.value++;
  if(s.value<=0) wakeup(s.list);
}

由此我们可以得出三个推论：

1. s.value为正数时，正是实际可用物理资源数
2. s.value为负数时，其绝对值为登记排列在s信号量队列中等待的进程个数
3. P操作意味着请求一个资源，V操作意味着释放一个资源，在一定条件下，P操作代表挂起进程操作，V操作代表唤醒被挂起进程的操作。

信号量实现互斥

信号量与PV操作可用来解决进程互斥问题，PV操作也可用测试信号量的方法来决定是否进入临界区。用信号量和PV操作管理并发进程互斥进入临界区的一般形式为：

1
2
3
4
5
6
7
8
9

semaphore mutex;
mutex = 1;
cobegin
  process Pi() {
  	P(mutex);
  	// 临界区
  	V(mutex);
  }
coend

当有进程在临界区的时候，mutex的值为0或负值，否则为1。通过P操作把mutex减至0，这时试图进入临界区的其他进程会因P(mutex)而被迫等待。

哲学家吃面问题

通过信号量和PV操作解决操作系统中很经典的五哲学家吃面问题，是进程互斥问题的代表。

如图哲学家坐在桌子旁，每两人间一把叉子，哲学家思考、饥饿、吃面。要吃面，必须拿起两把叉子，并且只能拿身边的两把叉子。这个问题的关键就是叉子需要互斥使用，所以我们可以把叉子设置为互斥量，则由fork[5]={1,1,1,1,1}，即代表有五把分别独立的叉子。信号量与PV操作解决哲学家吃面问题的伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

semaphore fork[5];
for(int i=0; i<5; i++) fork[i] = 1;
cobegin
  process philosopher_i() {		// 
    while(true) {
      think();					// 思考。。。
      P(fork[i]);				// 拿起左叉子
      P(fork[(i + 1) % 5]);		// 拿起右叉子
      eat();					// 吃。。。
      V(fork[i]);				// 放下左叉子
      V(fork[(i + 1) % 5]);		// 放下右叉子
    }
  }
coend

这并不是完美方式！！！这段代码会产生死锁，即当所有哲学家先拿起左边的叉子，再拿起右叉子，此时就会发现没叉子可拿，于是死锁。

生产者消费者问题

在协作进程之间，一个进程的执行依赖于协作进程的信号或消息，在尚未得到来自协作进程的信号或消息时则等待，直至信号或消息到达时才被唤醒。

该类问题是典型的进程同步问题，这些进程必须按照一定的生产率和消费率来访问共享存储区，用PV操作解决生产者和消费者共享单缓冲区的问题，可设置两个信号量，empty和full，empty表示能向缓冲区放产品的个数，full表示能从缓冲区取产品的个数。

为保证生产者和消费者互斥对缓冲区操作，还需要一个mutex互斥信号，保证同一时刻操作缓冲区的进程唯一。

这么一来，我们就可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

semaphore empty = k, full = 0;	// 初始状态，缓冲区为空，容量为k
semaphore mutex = 1;			// 互斥信号量
cobegin
  process producer_i() {
  	while(true) {
      produce();		// 生产操作
      P(empty);			// 测试缓冲区是否有空间，占用缓冲区空间
      P(mutex);			// 对互斥信号做P操作，加锁
      store();			// 将产品放入缓冲区
      V(mutex);			// 解锁
      V(full);			// 修改缓冲区信号量，表明占用缓冲区一个空间
    }
  }
  process consumer_i() {
  	while(true) {
      P(full);			// 测试缓冲区是否有产品，取产品
      P(mutex);			// 对互斥信号做P操作，加锁
      pickup();			// 取用产品
      V(mutex);			// 解锁
      V(empty);			// 修改缓冲区信号量，表明释放缓冲区一个空间
    }
  }
coend

程序中互斥信号的PV操作P(mutex)和V(mutex)必须成对出现， 两者之间的代码称为临界区。

施加于empty和full信号量的PV操作也要成对出现，当占用一个空间，占用完成的时候就要标记，同样释放空间后，也要标记。

如果缓冲区存满了k个产品，此时的empty信号量是0，那么再对empty做P操作，会导致进程等待；同样的，如果缓冲区无产品，此时full信号量为0，消费者要取用产品，对full做P操作，会导致进程等待。

每个PV操作的顺序都十分重要，因为不当的顺序可能导致死锁。举例，若把P(mutex)放到P(empty)之前执行，则先上锁，之后测试缓冲区是否有空间，若没空间进程等待，此时并没有把mutex解锁，进而其余进程无法执行，导致死锁。在使用信号量和PV操作实现进程同步时，特别要注意P操作的顺序，V操作的顺序无关紧要。通常来说，互斥信号量的P操作后执行。

另外可以定义两个互斥信号量mutex1和mutex2，分别用于生产者群体和消费者群体的各自互斥，这样可以提升并发行。那么可写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

semaphore empty = k, full = 0;		// 初始状态，缓冲区为空，容量为k
semaphore mutex1 = 1, mutex2 = 1;	// 互斥信号量
cobegin
  process producer_i() {
  	while(true) {
      produce();		// 生产操作
      P(empty);			// 测试缓冲区是否有空间，占用缓冲区空间
      P(mutex1);		// 对生产者互斥信号做P操作，加锁
      store();			// 将产品放入缓冲区
      V(mutex1);		// 生产者解锁
      V(full);			// 修改缓冲区信号量，表明占用缓冲区一个空间
    }
  }
  process consumer_i() {
  	while(true) {
      P(full);			// 测试缓冲区是否有产品，取产品
      P(mutex2);		// 对消费者互斥信号做P操作，加锁
      pickup();			// 取用产品
      V(mutex2);		// 消费者解锁
      V(empty);			// 修改缓冲区信号量，表明释放缓冲区一个空间
    }
  }
coend

读者写者问题

Reader Writer Problem，经典的并发程序设计问题。共有两组并发进程：读者和写者，共享文件F，要求如下：

1. 允许多个读者同时读文件。
2. 同时只允许一个写者对文件写操作。
3. 任何写者完成写操作前不允许其他读者、写者操作。
4. 写者执行写操作前，应让已有的写者和读者全部退出。

由于上述需求，我们需要引入计数器来对读进程计数readcount，写入锁writeblock。分析需求，得出当readcount为0的时候，writeblock做V操作；当readcount为1的时候，writeblock做P操作；我们可写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int readcount = 0;
semaphore writeblock = 1, mutex = 1;
cobegin
  process reader_i() {
    P(mutex);				// 互斥锁加锁
  	readcount++;			// 读者计数
  	if(readcount == 1) {	// 如果是首个读者进入
      P(writeblock);		// 写入锁加锁
    }
    V(mutex);				// 互斥锁解锁
  	// 读文件
    P(mutex);				// 互斥锁加锁
    readcount--;			// 读者计数
    if(readcount == 0) {	// 如果是最后一个读者离开
      V(writeblock);		// 写入锁解锁
    }
    V(mutex);				// 互斥锁解锁
  }
  process writer_j() {
    P(writeblock);
    // 写操作
    V(writeblock);
  }
coend

这段代码存在的问题是，当第一个读者并且未离开的时候，一直可以有新读者进入，而写者只能等待，除非所有读者离开，这就导致了饥饿问题，写者可能无限等待。

睡眠理发师问题

// TODO: 睡眠理发师问题

死锁

死锁的产生及原因

当操作系统允许多个进程并发执行时可能出现进程永远被阻塞现象，如两个进程分别等待对方所占有的一个资源，于是两者都不能执行而处于永远等待状态。

原因有很多，比如进程推进顺序不当，PV操作使用不妥，同类资源分配不均，或对某些资源的使用未加限制。

产生死锁的因素不仅与系统拥有的资源数量有关，而且与资源分配策略、进程对资源的使用要求以及并发进程的推进顺序有关。

死锁定义

如果一个进程集合中的每个进程都在等待中只能由此集合中的其他进程才能引发的事件，而无限期陷入僵持的局面称为死锁。

死锁的防止

产生死锁的条件

系统产生死锁必定同时保持如下四个条件：

• 互斥条件（mutual exclusion）：临界资源是独占资源，进程应互斥且排他地使用这些资源。
• 占有和等待条件（hold and wait）：进程在请求资源得不到满足而等待时，不释放已有资源。
• 不剥夺条件（no preemption）：又称不可抢占，已获资源只能由进程自愿释放，不允许被其他进程剥夺。
• 循环等待条件（circular wait）：又称环路条件，存在循环等待链，其中每个进程都在等待链中等待下一个进程所持有的资源，造成这组进程处于永远等待的状态。

前三个条件是必要不充分条件，第四个条件是前三个条件同时存在所产生的结果，条件并不完全独立。但单独考虑每个条件是有用的，只要能破坏四个必要条件之一，就可以防止死锁。

死锁防止策略

破坏互斥条件，可让资源同时被访问，而非互斥使用。

破坏占有和等待条件，可让进程在请求资源不满足时，释放掉已申请资源。

破坏不剥夺条件，有两种方法，一是占有资源的进程要申请新资源，需要主动释放已有资源（剥夺式），若仍要占用资源，需向系统申请；二是资源管理程序分配进程时，若资源足够则分配，不够则剥夺其拥有的全部资源，并进入等待资源状态，待充足后再唤醒它重新申请所有资源。

破坏循环等待条件，采用层次分配策略，把系统中的所有资源排列到不同层次，申请资源时，由底层向高层，每层纸分配一个资源；释放资源时，由高层到底层；当想在本层申请新资源，必须释放掉同层资源才能申请。采用资源有序使用方法，能够有效地破坏循环等待条件。

银行家算法

抽象模型

银行家算法就是把钱看作资源，客户看作进程，银行家看作操作系统。在客户需要贷款的时候要提出最大需求量，银行家若能满足则要满足，在满足了需求并且使用完毕后，客户要还钱。如果当前银行资金不能满足客户需求，则等到银行有钱再给。

算法描述

银行家算法又称为资源分配拒绝法。

基本思想：系统中所有进程进入进程集合，在安全状态下系统收到进程资源请求后，如果资源够则分配给他，然后系统把剩下的可用资源和进程集合中其他进程还需要的资源数做对比，找出生于资源能满足最大需求量的进程，从而保证进程运行完毕并归还全部资源，这是把这个进程从进程集合中删除，归还其所占用的所有资源，系统的声誉资源则更多，反复执行以上步骤，最后检查进程集合，若为空则表明本次申请可行，系统处于安全状态，可以真正实施本次分配，否则只要进程集合非空，系统便处于不安全状态，本次资源分配暂不实施，让申请资源的进程等待。

死锁的检测和恢复

系统可以定时运行死锁检测程序，判断系统内是否出现了死锁，如果出现死锁再采取措施解除。

资源分配图和死锁定理

资源用方块表示，进程用圆圈表示，用有向边表示进程申请资源和资源分配情况。如图这就是一个资源分配图的例子。

进程－资源分配图里存在环路并不一定发生死锁，因为循环等待资源仅是思索发生的必要条件，而不是充分条件。如下图就是一个有环路而无死锁的例子。

P1和P3看似已经无法从R1和R2拿够资源，但实际上P2和P4已经满足了要求，在完成了任务后归还资源，P1和P3能够拿到足够的资源，所以不存在死锁。

通过以下步骤来执行一个死锁检测：

1. 如果进程－资源分配图中无环路，则无死锁。
2. 如果进程－资源分配图中有环路，并且每种资源仅有一个资源，则死锁。此时环路是发生死锁的充要条件，环路中的进程就是死锁进程。
3. 如果进程－资源分配图中有环路，且所涉及的资源均有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件，系统不一定发生死锁。

系统发生死锁状态的充分条件是：当且仅当此状态进程－资源分配图是不可完全简化的，这一充分条件称为死锁定理。

死锁检测算法

正是利用银行家算法的思路来分配资源，检测死锁，具体不表。

死锁的检测和恢复

死锁的检测和恢复通常配套使用。死锁被检测到后，恢复方法大致有资源剥夺法、进程回退法、进程撤销法、系统重启法。