基本概念

定义：把异步环境下的一组并发进程因直接制约而相互发送消息、相互合作、相互等待，使得各进程按一定的速度执行的过程，称为进程同步

协作进程：具有同步关系的一组并发进程

进程同步机制的主要任务：在执行次序上对多个协作进程进行协调，使并发执行的诸多协作进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性

两种形式的制约关系

间接相互制约关系（互斥关系）

多个程序在并发执行时，由于共享系统资源，这些并发执行的程序之间会形成相互制约的关系

为了保证这些进程能有序地进行，对于系统中的这类资源，必须由系统实施统一分配，即用户在要使用这类资源之前应先提出申请，而不能直接使用

直接相互制约关系（同步关系）

某些应用程序为了完成某项任务，会建立两个或多个进程。这些进程会为了完成同一任务而相互合作。进程间的直接制约关系就是源于它们之间的相互合作，该关系也可称为同步关系

进程同步的概念是一个大的范畴，协作进程间的制约关系可统称为进程同步。根据制约形式的不同，可细分为同步关系和互斥关系，互斥是同步的一个特例。同步强调的是保证进程之间操作的先后次序的约束，而互斥强调的是对共享资源的互斥访问

临界资源

定义：系统中一次只允许一个进程使用的资源

临界资源既可以是硬件资源，也可以是软件资源

临界区问题

临界区：进程中访问临界资源的代码段

进入区：用于检查是否可以进入临界区的代码段

退出区：将临界区正被访问的标志恢复为未被访问标志的代码段

剩余区：其他代码

临界区：进程中访问临界资源的代码段

进入区和退出区：负责实现互斥的代码段

一个访问临界资源的循环进程的描述：

while(TURE){
    进入区
    临界区
    退出区
    剩余区
}

同步机制应遵循的准则：

1. 空闲让进：当无进程处于临界区时，表明临界资源处于空闲状态，应允许 1 个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源
2. 忙则等待：当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问
3. 有限等待：对于要求访问临界资源的进程，应保证其在有限时间内能进入自己的临界区，以免陷入“死等”状态
4. 让权等待（原则上应遵循，但非必须）：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态

软件同步机制

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予

int turn=0; //turn表示当前允许进入临界区的进程号
//P0进程
while(turn!=0); //①
critical section; //②
turn =1; //③
remainder section; //④
//P1进程
while(turn!=1); //⑤
critical section; //⑥
turn =1; //⑦
remainder section; //⑧

分析：

1. turn 的初值为 0，即刚开始只允许 0 号进程进入临界区
2. 若 P1 先上处理机运行，则会一直卡在 ⑤【违反“空闲让进”】 。直到 P1 的时间片用完，发生调度，切换 P0 上处理机运行。若代码 ① 不会卡住 P0，P0 可以正常访问临界区，在 P0 访问临界区期间即使切换回 P1，P1 依然会卡在 ⑤，只有 P0 退出临界区将 turn 改为 1 后，P1 才能进入临界区

适用范围：可以实现“同一时刻最多只允许一个进程访问临界区”

存在的问题：违反“空闲让进”的原则

双标志先检查法

算法思想：设置一个布尔数组 flag，数组中各个元素用来标记各进程想进入临界区的意愿，flag[0]=true表示 P0 现在想进入临界区。每个进程在进入临界区之前先检查当前有无别的进程想进入临界区，若无，则把自身对应的标志 flag 设为 true，之后开始访问临界区

//初始化
bool flag[2]; //表示进入临界区意愿的数组
flag[0]=false;
flag[1]=false;
//P0
while(flag[1]); //①
flag[0]=true; //②
critical section; //③
flag[0]=false; //④
remainder section; 
//P1
while(flag[0]); //⑤
flag[1]=true; //⑥
critical section; //⑦
flag[1]=false; //⑧
remainder section; 

分析：

1. 当其中一个进程先到达并进入临界区后，另一个进程只能等待，等待其从临界区出来后再进入
2. 当两个进程几乎同时达到，按照 1-->5-->2-->6 的顺序执行时，两个进程同时访问临界区，违反“忙则等待”的原则
3. ……

存在的问题：违反“忙则等待”的原则

双标志后检查法

算法思路：双标志先检查法的改版，前一个算法是先“检查”后“上锁”，但是二者无法一气呵成，故导致两个进程同时进入临界区的问题。因此，想到先“上锁”后“检查”的方法避免上述问题

//初始化
bool flag[2]; //表示进入临界区意愿的数组
flag[0]=false;
flag[1]=false;
//P0
flag[0]=true; //①
while(flag[1]);  //②
critical section; //③
flag[0]=false; //④
remainder section; 
//P1
flag[1]=true; //⑤
while(flag[0]); //⑥
critical section; //⑦
flag[1]=false; //⑧
remainder section; 

分析：

1. 当其中一个进程先到达并进入临界区后，另一个进程只能等待
2. 当两个进程同时到达，按照 1-->5-->2-->6 的顺序执行时，两个进程均开始原地循环，无法进入临界区，违反“空闲让进”和“有限等待”的原则
3. ……

存在的问题：违反“空闲让进”和“有限等待”的原则，会因各进程都长期无法访问临界资源而产生式“饥饿”现象

Peterson 解决方案

一个经典的基于软件的临界区问题的解决方案 —— Peterson 解决方案

算法思想：结合双标志法、单标志法的思想，若双方都争着想进入临界区，就可以让进程尝试谦让，做一个有礼貌的进程

适用情况：适用于两个进程交替执行临界区的情况，Pi，Pj

int turn; //表示哪个进程可以进入临界区
boolean flag[2]; //表示哪个进程准备进入临界区，初值均为false

//Pi
do{
    flag[i] = TRUE; //进程i准备进入临界区【主动争取】 ①
    turn = j; //进程j可以进入临界区【主动谦让】 ②
    while(flag[j] && turn == j); //【检查对方是否也想使用，且最后一次是不是自己说了“客气话”】 ③
    临界区; 
    flag[i] = FALSE;
    剩余区;
}while(TRUE);

//Pj
do{
    flag[j] = TRUE; //进程j准备进入临界区 ④
    turn = i; //进程i可以进入临界区 ⑤
    while(flag[i] && turn == i); // ⑥
    临界区;
    flag[j] = FALSE;
    剩余区;
}while(TRUE);

若两个进程同时试图进入临界区，turn 的值会几乎同时被设置成 i 或 j，但只有一个赋值语句的结果会被保留，故最终将由 turn 的值决定哪个进程被允许进入临界区执行

分析：

1. 当进程 i 和进程 j 只有一个到达时，以进程 i 到达，进程 j 未到达为例，当进程 i 到达后，先运行flag[i]=true;，turn=j;，因为flag[j]&&turn==j为假，跳出循环，进入临界区【空闲让进】，若此时进程 j 到达，运行flag[j]=ture，turn=i，因为flag[i]&&turn==i为真，进入 while 循环【忙则等待】，直到进程 i 退出临界区，并运行flag[i]=false后，进程 j 才能跳出循环，进入临界区【有限等待】
2. 当进程 i 和进程 j 同时到达时，若按 ①->④->②->⑤->③->⑥ 的次序执行，则进程 i 先进入临界区【空闲让进】，进程 j 进入 while 循环进行等待【忙则等待】，等到进程 i 退出临界区，进程 j 便进入临界区【有限等待】；若按 ①->②->④->⑤->⑥->③ 的次序执行，此时 ⑥ 进入循环，即进程 j 等待，进程 i 进入临界区；若按 ①->④->⑤->②->⑥->③ 的次序执行，此时进程 j 进入临界区，进程 i 等待……
3. 综上，我们可以发现：flag 的实际含义是提出进入临界区的请求；turn 则表示谦让；最后给 turn 赋值的进程后执行【因为最后给 turn 赋值的进程，正在进行谦让，便失去进入临界区的优先权】

证明正确性：

若要证明 Peterson 解决方案是正确的，则须证明该方案满足解决临界区问题的 3 个准则：忙则等待、空闲让进、有限等待【因为让权等待属于较高要求，在早期的解决方案中未对此做出要求，虽会影响系统效率，但不影响临界区问题的解决】

存在的问题：未遵循“让权等待”的原则

硬件同步机制

可利用特殊的指令解决临界区问题

实际上，在对临界区进行管理时，可以将标志看作一个锁，“锁开”进入，“锁关”等待，初始时锁是打开的。每个要进入临界区的进程，必须先对锁进行测试，当锁未开时，则必须等待，直至锁被打开。当锁打开时，则应立即把其锁上，以阻止其他进程进入临界区。为防止多个进程同时测试到“锁开”，测试和关锁操作必须是连续的，不允许分开进行

关中断

地位：实现互斥最简单的方法之一

在进入锁测试之前，关闭中断，直到完成锁测试并上锁之后，才能打开中断。进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。由此，保证了对锁的测试和关锁操作的连续性和完整性，进而有效地保证了互斥

优点：简单、高效

缺点：

1. 滥用关中断权力可能导致严重后果
2. 关中断时间过长会影响系统效率，进而会限制 CPU 交叉执行程序的能力
3. 关中断方法不适用于多 CPU 系统，因为在一个 CPU 上进行关中断并不能防止进程在其他 CPU 上执行相同的临界区代码
4. 只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

Test-and-Set 指令

简称：TS 指令，也称 TSL 指令

TS 指令用硬件实现，执行的过程不允许被中断，只能一气呵成

适应情况：多处理机环境

TS 指令的一般性描述：

boolean TS(boolean *lock){
    boolean old; //存放原来的lock值
    old = *lock;
    *lock = TRUE; //上锁
    return old; //返回lock原来的值
}
//其执行过程是不可分割的，是一条原语
//lock = FALSE，表示该资源空闲
//lock = TRUE，表示该资源正在被使用

利用 TS 指令实现互斥的循环进程结构的描述：

do{
    ...
    while TS(&lock); //检测锁状态，若返回false，表示资源空闲；若返回true，表示资源正在被使用【检查并上锁】
    critical section; //临界区
    lock := FALSE; //退出临界区，解锁
    remainder section;
}while(TRUE);

分析：

1. 若刚开始 lock 是 false，则 TS 返回的 old 值为 false，while 循环条件不满足，之间跳过循环，进入临界区
2. 若刚开始 lock 是 true，则 TS 返回的 old 值为 true，while 循环条件满足，进入循环，直到当前访问临界区的进程退出临界区解锁后，此进程跳出循环，进入临界区

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TS 指令，从而导致“忙等”

利用 swap 指令实现进程互斥

swap 指令：被称为对换指令，XCHG 指令（Intel 80x86），用于交换两个字的内容

//交换两个变量的值
void swap(boolean *a,boolean *b){
    boolean temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

do{
    key = TRUE;
    do{
        swap(&lock, &key);
    }while(key != FALSE);
    临界区操作;
    lock = FALSE;
    ...
}while(TRUE);
//为每个临界资源设置一个全局的布尔变量lock，其初值为FALSE
//在每个进程中再设置一个局部变量key，使用swap指令与lock进行数值交换，以此循环判断lock的取值
//只有当key为FALSE时，进程才可以进行临界区操作

总结

利用上述硬件指令能有效地实现进程互斥。但当临界资源被访问时，其他访问进程必须不断地进行测试，即处于一种忙等状态，这不符合“让权等待”的原则，因而会造成处理机时间的浪费，同时也很难将其用于解决复杂的进程同步问题

互斥锁

地位：解决临界区最简单的工具

描述：

1. 一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数 acquire() 获得锁，函数 releasse() 释放锁
2. 每个互斥锁有一个布尔变量 available，表示锁是否可用，若锁可用，调用 acqiure() 会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放
3. 因为两个函数的执行必须是原子操作，因此互斥锁通常采用硬件机制实现

acquire(){
    while(!available)
        ;  //忙等锁
    available = false;  //获得锁
}
release(){
    available = true;  //释放锁
}

缺点：忙等待

适用情况：用于多处理系统，一个线程可以在一个处理器上等待，不影响其他线程的执行

自旋锁：需要连续循环忙等的互斥锁，如 TS 指令、Swap 指令、单标志法

特性：

1. 需忙等，进程时间片用完才下处理机，违反“让权等待”
2. 优点：等待期间不切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低
3. 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
4. 不太适用于单处理机系统，忙等的过程中不可能解锁

信号量机制

地位：一种卓有成效的进程同步工具

发展：整型信号量 —> 记录型信号量 —> AND 型信号量 —> 信号量集

信号量软件解决方案：

1. 保证两个或多个代码段不被并发调用
2. 在进入关键代码段前，进程必须获取一个信号量，否则不能运行
3. 执行完该关键代码段，必须释放信号量
4. 信号量有值，为正说明其空闲，为负说明其忙碌

信号量机制介绍

整型信号量

定义：一个用于表示资源数目的整型量 S

访问：除初始化外，仅能通过两个标准的原子操作访问，即 wait(S) 和 signal(S) 操作，被称为 P 操作和 V 操作

wait(S){
    while(S<=0) //忙等
        S--;
}
signal(S){
    S++;
}

缺点：

1. 未遵循“让权等待”准则，使进程处于“忙等”状态
2. 不符合有序等待

记录型信号量

地位：一种不存在“忙等”现象的同步机制

value：代表资源数目

list：进程链表指针，用于链接等待进程（多个进程等待访问同一临界资源）

数据项

typedef struct{
    int value;
    struct process_control_block *list;
}semaphore;

wait(S) 和 signal(S) 操作

wait(semaphore *S){//进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个
    S->value--;
    if(S->value<0)//表示该类资源已分配完毕
        block(S->list);//自我阻塞，放弃处理机，并将该进程插入信号量链表list中
                       //|S->value|表示该信号量链表中已阻塞进程的数目
}
signal(semaphore *S){//进程释放一个单位的资源，使系统中可供分配的该类资源数增加一个
    S->value++;
    if(S->value<=0)//表示在该信号量链表中仍有等待该资源的进程被阻塞
        wakeup(S->list);//将S->list链表中的第一个等待进程唤醒，唤醒之后不会立马执行，
                        //而是进入就绪队列，而且不是从wait开始执行，而是从signal执行
}
//S->value的初值：系统中某类资源的数目，故又被称为资源信号量
//若S->value的初值为1，表示只允许一个进程访问临界资源，此时的信号量会转化为互斥信号量，用于进行互斥

AND 型信号量

适应情况：一个进程需要获得两个或更多的共享资源后才能执行其任务

基本思想：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放，只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源，也不分配给它。即对若干个临界资源的分配，采取原子操作方式：要么把其所请求的资源全部分配给它，要么一个也不分配，可避免死锁的发生。为此，在 wait(S) 操作中增加一个“AND”条件，称之为 AND 同步，或同时 wait(S) 操作，即 Swait(simultaneous wait)

//Swait
Swait(S1, S2, ..., Sn){
    while(TRUE){
        if(S1>=1 && S2>=1 &&...&& Sn>=1){
            for(i=1; i<=n; i++)
                Si--;
            break;
        }
        else{
            place the process in the waiting queue associated with the first
            Si found with Si<1, and set the program count of this process to
            the beginning of Swait operation
        }
    }
}
//Ssignal
Ssignal(S1, S2, ..., Sn){
    while(TRUE){
        for(i=1; i<=n; i++){
            Si++;
            Remove all the process waiting in the queue associated with Si
            into the ready queue
        }
    }
}

信号量集

适应情况：执行进程时一次需要 N 个单位的某类临界资源的问题

描述：进程对信号量 Si 的测试值不是 1，而是该资源的分配下限值 ti，即要求 Si>=ti，否则不予分配。一旦允许分配，则基于进程对该资源的需求值 di（表示资源占用量）进行 Si=Si-di 操作，而不是简单的 Si=Si-1

Swait(S1,t1,d1;...;Sn,tn,dn);

Ssignal(S1,d1;...;Sn,dn);

一般化的“信号量集”有下列 3 种特殊情况：

1. Swait(S,d,d)此时在信号量集中只有一个信号量 S，允许其每次申请 d 个资源，当现有资源数少于 d 时，不予分配
2. Swait(S,1,1)此时的信号量集已蜕化为一般的记录型信号量（S>1 时）或互斥信号量（S=1 时）
3. Swait(S,1,0)一种特殊且很有用的信号量操作，当 S>=1 时，允许多个进程进入某个特定的临界区；当 S=0 时，将阻止任何进程进入特定区。换言之，其相当于一个可控开关

总结

信号量的应用

利用信号量实现进程互斥

设置互斥信号量

操作次序

1. 分析并发进程的关键活动，划定临界区
2. 设置互斥信号量 mutex，初值为 1
3. 在进入区 P(mutex) —— 申请资源
4. 在退出区 V(mutex) —— 释放资源

描述

1. 设 mutex 为互斥型信号量，其初值为 1，取值范围为 (-1,0,1) 。当 mutex=1 时，表示两个进程皆未进入需要互斥访问的临界区；当 mutex=0 时，表示有一个进程进入临界区运行，另一个必须等待，挂入阻塞队列；当 mutex=-1 时，表示有一个进程正在临界区运行，而另一个进程因等待而阻塞在信号量队列中，需要被当前已在临界区运行的进程在退出时唤醒
2. 代码描述

semaphore mutex=1;
Pa(){
    while(1){
        wait(mutex);
        临界区;
        signal(mutex);
        剩余区;
    }
}
Pb(){
    while(1){
        wait(mutex);
        临界区;
        signal(mutex);
        剩余区;
    }
}

PS：

1. 利用信号量机制实现进程互斥时应注意，wait(mutex) 和 signal(mutex) 必须成对出现。缺少 wait(mutex) 将会导致系统混乱，无法保证对临界资源的互斥访问；缺少 signal(mutex) 将会导致临界资源永远不被释放，从而使因等待该资源而阻塞的进程不能被唤醒
2. 对不同的临界资源需要设置不同的互斥信号量

考点

某资源的数量：n 个

进程数量：m 个（m>n）

mutex 的初始值：n

mutex 的取值范围：n，n-1，...，n-m

利用信号量实现进程同步

设置同步信号量

协作进程间除了互斥地访问临界资源外，还需要相互制约和传递信息，以同步它们之间的运行，利用信号量可达到这一目的

操作次序

1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
2. 设置同步信号量 mutex，初值为 0
3. 在“前操作”之后执行 V(S)
4. 在“后操作”之前执行 P(S)

技巧口诀：前 V 后 P

举例

假设进程 P1 和进程 P2 中有两段代码 C1 和 C2，若要强制 C1 先于 C2 执行，则须在 C2 前添加 wait(S)，在 C1 后添加 signal(S) 。需要说明的是，信号量 S 的初值应该被设置为 0，只有 P1 在执行完 C1 后，才能执行 signal(S) 把 S 的值设置为 1。这时，P2 执行 wait(S) 才能申请到信号量 S，并执行 C2 。若 P1 的 C1 没有提前执行，则信号量 S 的值为 0，P2 执行 wait(S) 时会因申请不到信号量 S 而阻塞

1. 设 S 为同步型信号量，其初值为 0，取值范围为 (-1,0,1) 。当 S=0 时，表示 C1 还未执行，C2 也未执行；当 S=1 时，表示 C1 已经执行，C2 可以执行；当 S=-1 时，表示 C2 想执行，但由于 C1 尚未执行，C2 不能执行，进程 P2 处于阻塞状态
2. 代码描述

semaphore S=0;
P1(){
    while(1){
        C1;
        signal(S);
        ...
    }
}
P2(){
    while(1){
        wait(S);
        C2;
        ...
    }
}

一般情况下，同步型信号量的 wait(S) 和 signal(S) 操作位于两个不同的进程内

利用信号量实现前趋关系

每一对前驱关系都是一个进程同步问题（需保证一前一后的操作），因此：

1. 要为每一对前驱关系各设置一个同步信号量
2. 在“前操作”之后对相应的同步信号量执行 V 操作
3. 在“后操作”之前对相应的同步信号量执行 P 操作

管程机制

管程的定义

利用共享数据结构抽象地表示系统中的共享资源，并且将对该共享数据结构实施的特定操作定义为一组过程。进程对共享资源的申请、释放和其他操作，必须通过由这组过程间接地对共享数据结构进行操作加以实现。对于请求访问共享资源的诸多并发进程，可以根据资源的情况接受或阻塞，以确保每次仅有一个进程进入管程。通过执行这组过程使用共享资源，可以实现对共享资源所有访问的统一管理，进而有效地实现进程互斥

管程：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个 OS 的资源管理模块，称为管程

管程被请求和释放资源的进程所调用

管程的组成【类似于“类”】：

1. 管程的名称
2. 局限于管程内的共享数据结构说明（尽管数据结构是共享的，但该共享变量局限于管程内）【数据结构】
3. 对该数据结构进行操作的一组过程【函数】
4. 设置局限于管程内的共享数据初值的语句【初始化语句】

管程的语法描述：

monitor monitor_name{  //管程名
    share variable declarations;  //共享变量说明
    cond declarations;  //条件变量说明
    public:  //能被进程调用的过程
    void P1(......){  //对数据结构操作的过程
        ......
    }
    void P2(......){  //对数据结构操作的过程
        ......
    }
    ......
    void (......){  
        ......
    }
    ......
    {  //管程主体
        initialization code;  //初始化代码
    }
}

管程中包含了面向对象的思想，将表征共享资源的数据结构及其对数据结构操作的一组过程（包括同步机制），都集中并封装在了一个对象内部，隐藏了实现细节。封装于管程内部的数据结构仅能被封装于管程内部的过程所访问，管程外的任何过程都不能访问它；同时，封装于管程内部的过程仅能访问管程内的数据结构。所有进程当要访问临界资源时，都只能通过管程直接访问，而管程每次只准许一个进程进入管程，执行管程内的过程，从而实现了进程互斥

管程的特性（语言角度）：

1. 模块化，管程是一个基本程序单位，可以单独编译
2. 抽象数据类型，管程中不仅有数据，而且有对数据的操作
3. 信息掩蔽，管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部被定义的，供管程外的进程调用，而管程中的数据结构以及过程（函数）的具体实现，外部不可见

管程和进程不同：

1. 虽然二者都定义了数据结构，但进程定义的是私有数据结构——PCB，管程定义的是公共数据结构，如消息队列……
2. 二者都存在争对各自数据结构的操作，进程是由顺序程序执行有关操作的，而管程则主要进行同步操作和初始化操作
3. 设置进程的目的在于实现系统的并发性，而管程的设置是为了解决共享资源的互斥使用问题
4. 进程通过调用管程中的过程对共享数据结构进行操作，该过程就像通常的子程序被调用一样，因而管程为被动工作方式，进程则为主动工作方式
5. 进程之间能并发执行，而管程则不能与其调用者并发
6. 进程具有动态性，由创建而诞生，由撤销而消亡，而管程则是 OS 中的一个资源管理模块，仅供进程调用

条件变量

利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语 wait 和 signal 。当某进程通过管程请求获得临界资源而未能被满足时，管程便会调用 wait 原语以使该进程处于等待状态，并将其排在等待队列上，仅当另一进程访问完成并释放该资源后，管程才会调用 signal 原语，唤醒等待队列中的队首进程

引入

当一个进程调用管程，在管程中运行时被阻塞或挂起，直到阻塞或挂起的原因解除，在此期间，若该进程不释放管程，则其他进程就会因为无法进入管程而被迫进行长时间的等待。为解决此问题，引入条件变量 condition 。通常一个进程被阻塞或挂起的条件（原因）可以有多个，故在管程中设置了多个条件变量，且对这些条件变量的访问，只能在管程中进行

使用

管程中对每个条件变量都须予以说明，其形式为：condition x,y。对条件变量的操作仅仅是 wait 和 signal，因此条件变量也是一种抽象数据类型，每个条件变量均保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作可表示为 x.wait 和 x.signal，含义如下：

1. x.wait：若正在调用管程的进程因 x 条件需要而被阻塞或挂起，则调用x.wait将自己插入到 x 条件的等待队列上，并释放管程，直到 x 条件变化，此时其他进程可以使用该管程
2. x.signal：若正在调用管程的进程发现 x 条件发生了变化，则调用x.signal，重新启动一个因 x 条件而阻塞或挂起的进程，若存在多个这样的进程，则选择其中一个；若没有，则继续执行原进程，而不产生任何结果，与信号量机制中的 signal 操作不同，因为后者要执行s=s+1操作，会改变信号量的状态

若进程 Q 因 x 条件而处于阻塞状态，则正在调用管程的进程 P 执行了x.signal操作后，进程 Q 会被重新启动，此时针对两个进程 P 和 Q，应该如何确定哪个执行、哪个等待呢？

1. P 等待，直至 Q 离开管程或等待另一条件
2. Q 等待，直至 P 离开管程或等待另一条件
3. 汉森：规定管程中的过程所执行的 signal 操作是过程体的最后一个操作，故进程 P 执行 signal 操作后会立即退出管程，进程 Q 可以马上被恢复执行

生产者 - 消费者问题

生产者 - 消费者问题是相互合作进程关系的一种抽象

描述：所有的生产者生产同一种产品，所有的消费者消费同一种产品

问题描述

生产者（M 个）：生成产品，并放入缓冲区

消费者（N 个）：从缓冲区取产品消费

问题：如何实现生产者和消费者之间的同步和互斥？

互斥分析

生产者

把产品放入指定缓冲区

in：所有的生产者对 in 指针需要互斥

counter：所有生产者 - 消费者进程对 counter 互斥

buffer[in] = nextp;
in = (in+1) % n;
counter++;

消费者

从指定缓冲区取出产品

out：所有的消费者对 out 指针需要互斥

counter：所有生产者 - 消费者进程对 counter 互斥

nextc = buffer[out];
out = (out+1) % n;
counter--;

增加互斥机制

semaphore *m;  //互斥信号量，实现对缓冲区的互斥访问
m->value=1;
生产者:{
    ...
    生产一个产品
    ...
    wait(m);
    ...
    把产品放入指定缓冲区【临界区】
    ...
    signal(m);
}
消费者:{
    ...
    wait(m);
    ...
    从指定缓冲区取出产品【临界区】
    ...
    signal(m);
    ...
    消费取出的产品
    ...
}

同步分析

两者需要协同的部分

• 生产者：把产品放入指定缓冲区（关键代码 C1）
• 消费者：从满缓冲区取出一个产品（关键代码 C2）

三种运行次序（不同条件下不同运行次序）

1. 所有缓冲区空时
2. 所有缓冲区满时
3. 缓冲区有空也有满时

算法分析

生产者

1. 判断是否能获得一个空缓冲区，若不能则阻塞（同步：判断）
2. C1：把产品放入指定缓冲区
3. 满缓冲区数量＋1，若有消费者由于等消费产品而被阻塞，则唤醒该消费者（同步：通知）

消费者

1. 判断是否能获得一个满缓冲区，若不能则阻塞（同步：判断）
2. 从满缓冲区取出一个产品
3. 空缓冲区数量+1，若有生产者由于等空缓冲区而阻塞，则唤醒该生产者（同步：通知）

同步信号量定义

semaphore *full, *empty, *m;
//full：满缓冲区数量；empty：空缓冲区数量
//初始化
full->value=0;
empty->value=n;
m->value=1;

解决方法

生产者:{
    ...
    生产一个产品
    ...
    wait(empty);//empty>0表示有空缓冲区，继续执行；否则表示无空缓冲区，当前生产者阻塞
    wait(m);
    ...
    C1:把产品放入指定缓冲区
    ...
    signal(m);
    signal(full);//把full+1，若有消费者等在full的队列上，则唤醒该消费者
}

消费者:{
    ...
    wait(full);//full>0表示有缓冲区满，继续执行；否则表示无满缓冲区，当前消费者阻塞
    wait(m);
    ...
    C2:从指定缓冲区取出产品
    ...
    signal(m);
    signal(empty);//把empty+1，若有生产者等在empty的队列上，则唤醒该生产者
    ...
    消费取出产品
    ...
}

利用记录型信号量解决

• 假定在生产者和消费者之间的公用缓冲池中，具有 n 个缓冲区，此时可利用互斥信号量 mutex 实现各进程对缓冲池的互斥使用
• 利用信号量 empty 和 full 分别表示缓冲池中空缓冲区和满缓冲区的数量
• 假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息

int in=0,out=0;
item buffer[n];
semaphore mutex=1,empty=n,full=0;
void producer(){
    do{
        produce an item nextp;//生产一个产品
        ...
        wait(empty);
        wait(mutex);
        buffer[in]=nextp;
        in=(in+1)%n;
        signal(mutex);
        signal(full);
    }while(TRUE);
}
void consumer(){
    do{
        wait(full);
        wait(mutex);
        nextc=buffer[out];
        out=(out+1)%n;
        signal(mutex);
        signal(empty);
        consume the item in nextc;//消费取出产品
        ...
    }while(TRUE);
}
void main(){
    cobegin
    producer();
    consumer();
    coend;
}

PS：

1. 在每个进程中用于实现互斥的 wait(mutex) 和 signal(mutex) 必须成对出现
2. 对资源信号量 empty 和 full 的 wait 和 signal 操作，同样需要成对出现，但其处于不同的进程中
3. 每个程序中的多个 wait 操作的顺序不能颠倒，应先执行对资源信号量的 wait 操作，再执行对互斥信号量的 wait 操作，否则可能会引起进程死锁【当缓冲区满时，生产者进入临界区等待消费者释放空缓冲区，而消费者等待生产者释放临界区，相互等待，出现“死锁”】
4. 每个程序中的多个 signal 操作的顺序能颠倒
5. 生产者生产一个产品和消费者使用产品可以放在 P、V 操作之间，逻辑上可行，但是会导致临界区代码变得更长，导致一个进程对临界区上锁的时间会增长，不利于各进程交替的使用临界区资源，所以要让临界区代码尽可能的短

利用 AND 信号量解决

• 用Swait(empty,mutex)代替wait(empty)和wait(mutex)
• 用Ssignal(mutex,full)代替signal(mutex)和signal(full)
• 用Swait(full,mutex)代替wait(full)和wait(mutex)
• 用Ssignal(mutex,empty)代替signal(mutex)和signal(empty)

int in=0,out=0;
item buffer[n];
semaphore mutex=1,empty=n,full=0;
void producer(){
    do{
        produce an item nextp;
        ...
        Swait(empty,mutex);
        buffer[in]=nextp;
        in=(in+1)%n;
        Ssignal(mutex,full);
    }while(TRUE);
}
void consumer(){
    do{
        Swait(full,mutex);
        nextc=buffer[out];
        out=(out+1)%n;
        Ssignal(mutex,empty);
        consume the item in nextc;
        ...
    }while(TRUE);
}

利用管程解决

利用管程解决生产者-消费者问题时，首先须建立一个管程，并将其命名为 producerconsumer（简称 PC），其中包括以下两个过程：

1. put(x)：生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量 count 表示在缓冲池中已有的产品数目，当 count>=n 时，表明缓冲池已满，生产者应等待
2. get(x)：消费者利用该过程从缓冲池中取出一个产品，当 count<=0 时，表示缓冲池中已无可取用的产品，消费者应等待

对于条件变量 notfull 和 notempty，有以下两个过程可以对其进行操作：

1. cwait(condition)：当管程被一个进程占用时，其他进程调用该过程时会阻塞，并且会被挂在条件 condition 的队列上
2. csignal(condition)：唤醒在 cwait 执行后阻塞在条件 condition 队列上的进程，若这样的进程不止一个，则选择其中一个实施唤醒操作；若队列为空，则无操作返回

monitor producerconsumer{
    item buffer[N];
    int in,out;
    condition notfull,notempty; //条件变量，用来实现同步
    int count; //缓冲池中已有的产品数目
    public:
        void put(item x){ //将生产的产品投放到缓冲区中
            if(count>=n) //缓冲区是否已满
                cwait(notfull); //由于缓冲区已满，阻塞生产者进程
            buffer[in]=x;
            in=(in+1)%n;
            count++;
            csignal(notempty); //唤醒消费者进程
        }
        void get(item x){ //从缓冲区中取出一个产品
            if(count<=0) //缓冲区是否为空
                cwait(notempty); //由于缓冲区为空，阻塞消费者进程
            x=buffer[out];
            out=(out+1)%n;
            count--;
            csignal(notfull); //唤醒生产者进程
        }
        {
            in=0;
            out=0;
            count=0;
        }
}PC;

void producer(){
    item x;
    while(TRUE){
        ...
        produce an item in nextp;
        PC.put(x);
    }
}
void consumer(){
    item x;
    while(TRUE){
        PC.get(x);
        consume the item in nextc;
        ...
    }
}
void main(){
    cobegin
    producer();
    consumer();
    coend
}

引入管程的目的：更方便地实现进程互斥和同步

1. 需要在管程中定义共享数据：缓冲区
2. 需要在管程中定义用于访问这些共享数据的“入口”—— 其实就是一些函数：可用定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品
3. 只有通过这些特定的“入口”才能访问共享数据
4. 管程中有很多“入口”，但每次只能开放其中一个“入口”，并且只能让一个进程或线程进入：各进程需互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区，注意：这种互斥特性是由编译器负责实现的，程序员不用关心
5. 可在管程中设置条件变量及对对应的等待/唤醒操作以解决同步问题。可用让一个进程或线程在条件变量上等待（此时进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒

多生产者-多消费者问题

描述：不同类别的生产者生产不同的产品，不同类别的消费者使用不同的产品

互斥关系：对缓冲区的访问要互斥进行

同步关系：

1. 对于某类产品，只能先生产再消费
2. 只有盘子存在空缓冲区时，才允许生产者生产产品

mutex：

1. 若缓冲区大小 > 1，必须专门设置一个互斥信号量 mutex 保证互斥访问缓冲区
2. 若缓冲区大小 = 1，可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能，但不是绝对的，要具体问题具体分析

解题关键：

解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度分析，要把“一前一后”发生的事看作两种“事件”的前后关系，例如：

缓冲区大小为 1，A_生产者生产 a 产品，A_消费者消费使用 a 产品；B_生产者生产 b 产品，B_消费者消费使用 b 产品：

若缓冲区中有产品 a，则一定要 A_消费者使用产品 a 之后 A_生产者或 B_生产者才能生产产品；

若缓冲区中有产品 b，则一定要 B_消费者使用产品 b 之后 A_生产者或 B_生产者才能生产产品；

如此分析，意味着要设置 4 个同步信号量分别实现 4 个“一前一后”的关系，但这是错误的

正确的分析方法该从“事件”的角度考虑，可以把对上述 4 对“进程行为的前后关系”抽象为 1 对“事件的前后关系”：缓冲区变空事件 —> 生产产品事件，“缓冲区变空事件”既可由 A_消费者引发，也可由 B_消费者引发；“生产产品事件”既可能是 A_生产者执行，也可能是 B_生产者执行，如此便可用 1 个同步信号量解决问题

哲学家进餐问题

描述：有 5 个哲学家共用 1 张圆桌，其分别坐在圆桌周围的 5 把椅子上，在圆桌上有 5 个碗和 5 根筷子，他们的生活方式是交替地进行思考和进餐；平时，1 个哲学家进行思考，其饥饿时便会试图取用左右两边最靠近自己的筷子，他只有在拿到 2 根筷子时才能进餐；进餐毕，放下筷子继续思考

特点：

1. n 个进程，n 个资源
2. 每个进程只有拿到 2 个资源才可以运行
3. 进程之间只有互斥，没有协作

哲学家进餐问题的关键：解决进程死锁

考点：一个进程需要同时持有多个临界资源

利用记录型信号量解决

临界资源：筷子

semaphore chopstick[5]={1,1,1,1,1};//1个信号量表示1根筷子，由这5根筷子对应的5个信号量构成信号量数组

do{
    wait(chopstick[i]); //哲学家饥饿时总是先拿起其左边筷子
    wait(chopstick[(i+1)%5]); //成功拿起左边筷子之后，去拿其右边筷子
        ...
    //eat
        ...
    signal(chopstick[i]); //先放下左边筷子
    signal(chopstick[(i+1)%5]); //后放下右边筷子
        ...
    //think
        ...
}while(TRUE);

优点：可保证不会有两个相邻的哲学家同时进餐

缺点：可能引起死锁，假如 5 位哲学家同时饥饿而各自拿起左边的筷子，会使 5 个信号量 chopstick 均为 0，当其试图去拿右边筷子时，都将会因无筷子可拿而进行无限期的等待，解决此死锁问题的方法如下：

1. 至多只允许有 4 位哲学家同时去拿左边的筷子：最终能保证至少有 1 位哲学家能够进餐，并在进餐毕时能释放出其用过的 2 根筷子，从而使更多的哲学家进餐

semaphore chopstick[5]={1,1,1,1,1};
semaphore count=4; //设置一个控制信号量count，控制并发的数目
do{
    wait(count);
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
    eat...
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    signal(count);
    think... 
}while(TRUE);

1. 仅当哲学家的左右两根筷子均可用时，才允许其拿起筷子进餐

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex=1; //互斥地取筷子
Pi(){ //i号哲学家的进程
    while(1){
        P(mutex);
        P(chopstick[i]); //拿左
        P(chopstick[(i+1)%5]); //拿右
        V(mutex);
        eat...
        V(chopstick[i]);
        V(chopstick[(i+1)%5]);
        think...
    }
}

表述不太准确：

• 因为两边的筷子都可用时，哲学家也可能拿不起筷子（当 0 号哲学家拿起筷子时，由于没有退出临界区，2 号哲学家可能拿不起筷子）
• 哲学家左右两根只有一根筷子可用，也可能拿起这只可用的筷子（当 0 号哲学家拿起两根筷子且退出临界区时，4 号哲学家可进入临界区拿起一根筷子，另一根筷子由于被 0 号哲学家拿走了而无法得到，使进程阻塞）

更准确的说法：

各哲学家拿筷子这件事必须互斥的执行，能保证即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子，这样，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子

1. 规定奇数号哲学家先拿起左边筷子，然后再拿起右边筷子，而偶数号哲学家则相反：可以保证若相邻的两个奇偶哲学家都想吃饭，那么会先争抢二者共同的筷子，只会有其中一个可以拿起第一根筷子，另一个会直接阻塞，可避免占有一根后再等待另一根的情况

do{
    if(i%2==1){
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]);
    }
    else{
        wait(chopstick[(i+1)%5]);
        wait(chopstick[i]);
    }
    eat...
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    think...
}while(TRUE);

1. 对筷子进程编号，规定哲学家先取编号小的筷子
2. 若哲学家拿起左边的筷子后，申请右边的筷子得不到满足，则放下左边的筷子，隔一段时间后再申请左边的筷子

利用 AND 信号量机制解决

semaphore chopstick[5]={1,1,1,1,1};
do{
        ...
    //think
        ...
    Swait(chopstick[(i+1)%5],chopstick[i]);
        ...
    //eat
        ...
    Ssignal(chopstick[(i+1)%5],chopstick[i]);
}while(TRUE);

利用管程解决

利用管程解决哲学家进餐问题时，可使一个哲学家只有在左右两根筷子都可用时才被允许拿起筷子

需区分哲学家所处的 3 个状态，引入枚举类型变量：enum{thinking,hungry,eating} state[5];

哲学家 i 只有在其左右两个邻居不进餐时才能将变量 state[i] 设置为 eating，即state[(i+4)%5]!=eating && state[(i+1)%5]!=eating

需声明条件变量：condition self[5];

哲学家 i 在饥饿且不能拿到所需筷子时，需阻塞自己

//管程dp控制筷子的拿起与否
monitor dp{
    enum{thinking,hungry,eating} state[5];
    condition self[5];
    initialization_code(){ //设置哲学家的状态
        for(int i=0;i<5;i++)
            state[i]=thinking;
    }
    void pickup(int i){ //吃饭前的检验
        state[i]=hungry; //将本人的状态设为饥饿
        test(i); //检查本人左右两边的筷子是否空闲，若空闲，则将本人的状态设为吃饭并且唤醒本人
        if(state[i]!=eating) //若本人左右两边的筷子正在被使用，则将本人阻塞
            self[i].wait();
    }
    void putdown(int i){ //吃饭后的工作
        state[i]=thinking; //将本人的状态设为思考
        //test left and right neighbors
        test((i+4)%5); //检验本人周围的两个人是否因本人放下的筷子能被唤醒，若能则唤醒2222
        test((i+1)%5);
    }
    void test(int i){
        if((state[(i+4)%5]!=eating) && (state[(i+1)%5]!=eating) && (state[i]==hungry)){
            state[i]=eating;
            self[i].signal();
        }
    }
}

//哲学家i的活动
do{
    dp.pickup(i);
    ...
    eat
    ...
    dp.putdown(i);
}while(TRUE)

读者 - 写者问题

定义：指保证一个 writer 进程必须与其他进程互斥地访问共享对象的同步问题

应用：常被用于测试新同步原语

要求：

1. 允许多个 reader 进程同时操作，因为读操作不会使数据文件混乱
2. 不允许 writer 进程、reader 进程同时操作
3. 不允许多个 writer 进程同时操作

读者优先

若读者来：

• 无读者、写者，新读者可以读
• 有写者等，但有其他读者正在读，则新读者也可以读
• 有写者写，新读者等

若写者来：

• 无读者，新写者可以写
• 有读者，新写者等待
• 有其他写者，新写着等待

对此问题的解答，可能会导致写者饥饿

利用记录型信号量解决

互斥信号量 wmutex：实现 reader 与 writer 进程在读 / 写时的互斥

整型变量 readcount：用于表示正在读的进程数目，因为 readcount 是一个可被多个 reader 进程访问的临界资源，故需为其设置一个互斥信号量 rmutex

semaphore rmutex=1,wmutex=1;
int readcount=0;
void reader(){ 
    do{
        wait(rmutex); 
        if(readcount==0) 
            wait(wmutex); //当前无读者正在读，新读者申请临界资源
        readcount++; //当前有读者正在读，新读者直接开始读
        signal(rmutex);
        ...
        perform read operation; //读操作
        ...
        wait(rmutex); //其中一个正在读的读者的读操作结束后，readcount--
        readcount--;
        if(readcount==0) //所有的正在读的操作都完成后，释放临界资源
            signal(wmutex);
        signal(rmutex);
    }while(TRUE);
}
void writer(){
    do{
        wait(wmutex); //写者到达，申请临界资源
        perform write operation; //写操作
        signal(wmutex); //写操作完成，释放临界资源
    }while(TRUE);
}
void main(){
    cobegin;
    reader();
    writer();
    coend;
}

利用“信号量集”机制解决

增加一个限制：最多只允许 RN 个读者同时进行读操作

信号量 L：初值 RN，Swait(L,1,1)控制读者数目，每当有一个读者进行读操作时，要先执行此操作使 L 的值减 1，当有 RN 个读者进行读操作后，L 便会减为 0，此时第 RN+1 个读者若要进行读操作，则会因此操作失败而阻塞

mx：表示写资源

int RN;
semaphore L=RN,mx=1;
void reader(){
    do{
        Swait(L,1,1); 
        Swait(mx,1,0); //起“开关”的作用，只要无writer进程进行写操作，mx=1，reader进程就可以读；
                       //只要有writer进程进行写操作，mx=0，任何reader进程都无法进行读操作
        ...
        perform read operation;
        ...
        Ssignal(L,1);
    }while(TRUE);
}
void writer(){
    do{
        Swait(mx,1,1;L,RN,0);//表示仅当既无writer进程在写（mx=1），又无reader进程在读（L=RN）
                             //时，writer进程才能进入临界区写
        perform write operation;
        Ssignal(mx,1);
    }while(TRUE);
}
void main(){
    cobegin;
    reader();
    writer();
    coend;
}

编程实现方法

1. 编写程序核心代码
2. 分析进程同步关系
3. 分析进程互斥关系

进程同步分析方法

1. 找出需要同步的代码片段（关键代码）
2. 分析所找代码片段的执行次序
3. 增加同步信号量并赋初值
4. 在所找代码片段后加 wait(S) 和 signal(S) 操作

进程互斥分析方法

1. 查找临界资源
2. 划分临界区
3. 定义互斥信号量并赋初值
4. 在临界区前后的进入区和退出区中分别加入 wait(S) 和 signal(S) 操作