进程同步
（1)进程同步
1.进程同步的基本概念
进程同步的主要任务是使并发执行的诸进程之间能有效地共享资源和相互合作，使执行的结果具有可再现性。
2.进程之间的两种制约关系
间接相互制约关系 系统资源共享：互斥地访问、系统统一分配
直接相互制约关系 进程间合作，比如进程A、B，进程B是对进程A的数据进行处理，那么进程B就一定要在进程A之后执行。
临界资源(critical resource)：一段时间仅允许一个进程访问的资源。
临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。
并发进程对临界资源的访问必须做某种限制，否则就可能出现与时间有关的错误
3.四大区
临界区：临界段，在每个程序中，访问临界资源的那段程序。
进入区：用于进入临界区前检查临界资源是否正在被访问的代码块。
退出区：在临界区之后用于将临界区正在被访问的标志恢复为未被访问的状态的代码块。
剩余区：除进入区、临界区及退出区之外的其它部分的代码。
一个访问临界资源的循环进程描述为：
while(true) { 进入区 临界区 退出区 剩余区 }
4.同步机制应遵循的规则：
空闲让进：当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。（多中选一）
忙则等待：当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。 （互斥访问）
有限等待： 对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，避免陷入"死等"状态。 (避免死等)
让权等待： 当进程不能进入自己的临界区时，应立即释放处理机，避免进程陷入"忙等"状态。 (避免忙等)
（2）硬件同步机制
1.关中断
关中断：实现互斥最简单的方法。 进入锁测试之前关闭中断，直到完成锁测试并且关上锁以后再打开中断。进程进入临界区执行期间，计算机系统不会响应中断，也不会引发调度，就不会引起线程或者进程的切换。
缺点：影响系统效率、不适合多CPU、会导致严重后果
2.利用Test-and-Set指令实现互斥（专用机器指令）
TS指令的一般性描述：
boolean TS(boolean *lock){ boolean old; old=*lock; *lock=TRUE; return old; }
利用TS指令实现互斥的循环进程结构描述为：
do{ … while TS(&lock); critical section; lock:=false; remainder seciton; }while（true）
3.利用swap指令实现互斥（交换指令）
void swap(boolean *a, boolean *b) { boolean temp; temp=*a; *a=*b; *b=temp; }
利用Swap指令实现进程互斥的循环进程描述为：
do{ key=TRUE; do{ swap(&lock, &key); } while(key!=FALSE); critical section; //临界区操作 lock:=false; … } while(TRUE);
（3）信号量机制
1、整型信号量
把整型信号量定义为一个整型量：表示资源数目
由两个标准原子操作wait(S)（P操作）和signal(S)（V操作）来访问。
P/wait(S): { while (S≤0);/*do no-op*/ S:=S-1; } V/signal(S): { S:=S+1; }
2、记录型信号量
记录型信号量机制采取“让权等待”策略，避免了整型信号量出现的“忙等”现象。
实现时需要一个用于代表资源数目的整型变量value（资源信号量）：用一个少一个
一个用于链接所有阻塞进程的进程链表list ：让权等待
信号量是一个数据结构，定义如下： tupedef struct { int value; struct Process_Control_Block *list; } semaphore 信号量说明： semaphore s; P(semaphore *s)/wait(semaphore *s) { s.value = s.value -1; if (s.value < 0) { //该进程状态置为阻塞状态 //将该进程的PCB插入相应的阻塞队列末尾s.queue; } } V(semaphore *s)/signal(semaphore *s) { s.value = s.value +1; if (s.value < = 0) { //唤醒相应阻塞队列s.queue中阻塞的一个进程 //改变其状态为就绪状态 //并将其插入就绪队列 } }
3、AND型信号量
AND同步机制的基本思想是：
将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未分配给进程，其它所有可能为之分配的资源，也不分配给它。
实现时在wait操作中，增加一个“AND”条件，故称AND同步，或同时wait操作(Swait)。
Swait(S1, S2, …, Sn) //P原语； { if(S1 >=1 && S2 >= 1 && … && Sn >= 1) { //满足资源要求时的处理； for (i = 1; i <= n; ++i) --Si; } else { //某些资源不够时的处理； //调用进程将自己转为阻塞状态， //将其插入第一个小于1信号量的阻塞队列Si.queue; } } Ssignal(S1, S2, …, Sn) { for (i = 1; i <= n; ++i) { ++Si; //释放占用的资源； //将与Si相关的所有阻塞进程移出到就绪队列 } }
4、信号量集
信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。 一般信号量集的基本思路就是在AND型信号量的基础上进行扩充，在一次原语操作中完成所有的资源申请
进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si >= ti；即当资源数量低于ti时，便不予分配）
占用值为di（表示资源的申请量，即Si=Si-di）
对应的P、V原语格式为：
Swait(S1, t1, d1; ...; Sn, tn, dn);
Ssignal(S1, d1; ...; Sn, dn);
Swait(S1,t1,d1,…, Sn,tn,dn) if S1≥t1 and … and Sn≥tn then for i:=1 to n do Si:=Si-di; endfor else //当发现有Si<ti时，该进程状态置为阻塞状态 endif Ssignal(S1, d1,…, Sn, dn) for i:=1 to n do Si:=Si+di; //将与Si相关的所有阻塞进程移出到就绪队列 endfor
一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：
Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配
Swait(S, 1, 1) 表示记录型信号量或互斥信号量
Swait(S, 1, 0)可作为一个可控开关（当S³1时，允许多个进程进入特定区域；当S=0时，禁止任何进程进入该特定区域）
一般“信号量集”未必成对使用。如：一起申请，但不一起释放
整型信号量：引入表示资源数目的整型量S以及原子操作wait/signal（P/V）
记录型信号量：增加进程链表指针list
AND型信号量：需要获得多个共享资源引入and条件
信号量集：多个共享资源每次申请n个
5.利用信号量实现进程互斥
要使多个进程能互斥地访问某临界资源：
1. 为临界资源设置一互斥信号量mutex，设其初始值为1；
2. 将各进程访问该临界资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。
3. 每一个要访问该临界资源的进程在进入临界区之前，都必须对互斥信号量mutex执行wait操作；当进程退出临界区以后，需要对互斥信号量mutex执行signal操作
semaphore mutex = 1; Pa(){ while(1){ wait(mutex); 临界区; signal(mutex); 剩余区; } } Pb(){ while(1){ wait(mutex); 临界区; signal(mutex); 剩余区; } }
Wait和signal原语的物理意义
每执行一次wait操作，意味着请求分配一个单位的资源，描述为mutex = mutex - 1;
- 当mutex<0表示已无资源，请求该资源的进程将被阻塞。
- |mutex|表示等待该信号量的等待进程数。
每执行一次signal操作，意味着释放一个单位的资源，描述为mutex = mutex + 1;
- 若mutex<0表示仍有被阻塞进程。将被阻进程队列中的第一个进程唤醒插入就绪队列中
原语的物理意义
mutex>0时，mutex表示可使用资源数。
mutex=0时，表示已无资源可用，或表示不允许进程再进。
mutex<0时，|mutex|表示等待使用资源的进程个数。
6.利用信号量实现前趋关系
若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没 有次序的要求，为了描述方便，可以用一个前驱图来表示进程集合的执行次序。
- 在需要顺序执行的进程（P1→P2）间设置一个公用信号量S（标识后面的进程是否可以开始运行），供两个进程共享，并赋初值为0。
- 若进程P1要求在P2之前执行，为P1、P2之间的前趋关系设置一个信号量S，初始化为0，
- S为0表示任何一个进程也没有执行（跟S有关的进程都应该被阻塞）。
- P1执行完后，置S为1，P2若要执行，必须是S为1才能执行。在进程P1中，运行…. ，signal(S) 在进程P2中，wait(S)，运行…
P1( ) { S1; signal(a); signal(b); } P2( ) { wait(a); S2; signal(c); signal(d); } P3( ) { wait(b); S3; signal(e); } P4( ) { wait(c); S4; signal(f); } P5( ) { wait(d); S5; signal(g); } P6( ) { wait(e); wait(f); wait(g); S6; } main( ) { semaphore a,b,c,d,e,f,g; a.value:=0; b.value=0;……. cobegin p1( ); p2( ); p3( ); p4( ); p5( ); p6( ); coend }
（4）管程机制
1.管程的基本概念和定义
引入的原因
大量的同步操作分散在各个进程中，给系统的管理带来麻烦，还会因为同步操作使用不当而导致死锁。
解决的办法——引入管程
为每个可共享资源设立一个专门的管程，来统一管理各进程对该资源的访问。
管程的定义：一个管程包含一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据(构成一个操作系统的资源管理模块)。
管程的四个部分
- 管程名称
- 局部于管程的共享变量说明
- 对该数据结构进行操作的一组过程
- 对局部于管程的数据设置初始值的语句
管程的特点
- 模块化（面向对象思想）、抽象数据类型、信息隐蔽（隐藏实现细节）
- 局部数据变量只能被管程的过程访问，任何外部过程都不能访问。封装于管程内部的过程也只能访问管程内部的数据结构。
- 所有进程要访问临界资源时，都只能通过管程间接访问，在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被挂起，以等待管程变成可用的。
- 一个进程通过调用管程的一个过程进入管程。
管程和进程的区别
- 进程定义的是私有的PCB；管程定义的数据结构是公共数据结构。
- 进程中涉及到的操作由程序的顺序执行有关系；管程中的操作是初始化以及帮助进程同步。
- 进程实现多道程序并发执行；管程实现共享资源互斥使用。
- 管程是被动执行，进程是主动工作。
- 进程可以并发执行；管程不能与其他调用者并发。
- 进程具有动态性由创建而产生，由撤销而消亡；管程是操作系统中的一个资源模块，供进程调用。
用管程实现进程同步
- 为了保证共享变量的数据一致性，管程应互斥使用。
- 管程通常是用于管理资源的，因此管程中有进程等待队列和相应的等待和唤醒操作。
- 在管程入口有一个等待队列，称为入口等待队列。仅当一个已进入管程的进程释放管程的互斥使用权时；管程才会唤醒另一个等待进程。两者必须有一个退出或停止使用管程。
- 在管程内部，由于执行唤醒操作，可能存在多个等待进程（等待使用管程）。
2.条件变量
- 管程内部有自己的等待机制。
- 管程可以说明一种特殊的条件型变量：condition；实际上是一个指针，指向一个等待该条件的PCB队列。
- 条件变量实际上是区分阻塞的原因。
- 对条件变量的访问只能在管程中进行，管程中对每个条件变量都必须予以说明：condition x,y；
- 对条件变量的操作仅能采用PV操作，因此条件变量也是一种抽象的数据类型，每个条件变量保存了一个链表，用于记录因为该条件变量而阻塞的所有进程。
条件变量
- 管程利用wait原语让进程等待时，等待的原因可用条件变量condition区别
- 应置于wait和signal之前
- 每个条件变量还关联一个链表
例如：X:condition
X.Wait 表示正在调用管程的进程原因因为X条件需要被阻塞或者挂起。调用X.Wait 将自己插在X条件的等待队列上，并释放管程直到X条件发生变化
X.Signal 表示正在调用管程的进程发现X条件发生了变化，则调用 X.signal 重新启动一个因为X条件而被阻塞的进程，如果有多个进程选择一个；如果没有被阻塞的进程，不产生任何后果。
参考《计算机操作系统》(汤小丹 第四版)
