操作系统教程pdf南OS3-同步通信与死锁

第三章同步、通信与死锁并发进程临界区管理信号量与PV操作管程进程通信死锁 Linux同步和通信 Windows同步和通信1

§3.1 3.1.1顺序程序设计

并发进程

顺序性：前一个操作结束后才开始下一操作封闭性：独占资源，执行过程不受外界影响执行结果确定，执行过程可再现系统效率不高

3.1.2进程的并发性引入并发：一组进程的执行时间重叠，提高吞吐率和资源利用率。进程间的相互作用：无关进程：操作不同数据集合,与其它进程进展情况无关。交互(相关)进程：由于共享某些变量(资源),一个进程的执行可能影响其它进程的执行结果。与同一共享资源有关的程序段分散在各进程中，且各进程的执行速度不可预知。

由于对资源的共享和竞争，并发程序相互制约。并发程序的执行结果将不可再现(不确定)。如果不满足并发条件，还会导致“与时间有关的错误”。3

3.1.2进程的并发性两个程序或语句S1和S2并发执行的条件：

S1和S2的读集与写集不相交。R(S1)∩W(S2)∪R(S2)∩W(S1)∪W(S1)∩W(S2)=Φ例：有4条语句：S1:a=x+y;S3:c=a-b;它们的读集和写集分别为： R(S1)={x,y} R(S2)={z} W(S1)={a} W(S2)={b}则S1、S2和S4可并发；而S1和S3, S2和S3, S3和S4不能并发执行。4

S2:b=z+1; S4:w=c+1; R(S3)={a,b} W(S3)={c} R(S4)={c} W(S4)={w}

对程序的并发执行不加以控制时具有不可再现性和错误的例子：例：堆栈S,栈顶指针top,取栈顶数据的程序get(top)和将数据压栈的程序put(blk)。 Procedure get(top) Procedure put(blk) Begin Begin local r r:=(top) top:=top+1 top:=top-1 (top):=blk return(r) End End top topA B E

rA B E F

put(blk)运行top++之后

top get(top)开始执行

A B E F5

栈S

F

栈S

栈S

“与时间有关的错误”对一次只允许一个进程使用的资源(临界资源)的共享过程不加以控制时，会导致程序结果与执行速度有关。结果不唯一或进程永远等待。例：程序A的n:=n+1和程序B的print(n)、n:=0交叉运行。程序A……① L1: n:=n+1;…… goto L1;程序B……② L2: print(n);③ n:=0;…… goto L2;

上面的3条语句执行顺序：①②③和②③①都认为是正确的，但②①③被认为是错误的。6

3.1.3进程的交互：协作和竞争进程互斥(Mutual Exclusion):指若干个进程因相互争夺独占型资源时所产生的间接制约关系。进程同步(Synchronize):指协作的并发进程需要按先后次序执行所产生的直接制约关系。一个进程的执行依赖于协作进程的消息或信号。当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。

进程的互斥：由资源共享引起间接制约例：两个售票进程P1、P2共享一个数据库

。某航班X现有1张票剩余。新到达一个售票请求 X 1,P1已确定可售但尚未修改“剩余票数”时，其时间片中断到。又到达 X 1,P2修改X航班的剩余票数为0。然后P1开始修改“剩余票数”,……。因此对数据库或其中的记录应互斥写。

进程的同步：由进程协作引起直接制约例：送数进程和计算进程使用同一个缓冲区。PA:送数 L1: BUF:=数据 Signal to B Wait for B goto L1 PB:取数计算 L2: Wait for A计算BUF中的数据 Signal to A goto L2

协作进程的执行过程互相影响。协作进程之间共享数据或资源。如果对共享数据的并发访问不加以约束，可能会导致数据不一致。9

§3.23.2.1互斥和临界区

临界区管理

临界资源：一次仅允许一个进程使用的资源。临界区：一个进程访问临界资源的那段程序代码。互斥时的原则：

互斥使用：一次至多一个进程能够进入临界区内执行 有空让进：当临界区空闲时，请求进程立即进入执行 忙则等待：有进程正在临界区时，其它请求进程等待 有限等待：请求进程应在有限的等待时间内进入临界区 多中择一：从多个请求进程中选择一个进入临界区 算法可行：不能造成进程饥饿或死锁10

3.2.2临界区管理的尝试只考虑两进程的互斥。insidex为true表示Px正在临界区中。(初值均为false) Process P1{while (true){ while (inside2);//等待 inside1= true;{临界区}; inside1= false;}} Process P1{while (true){ inside1= true; while (inside2);//等待{临界区}; inside1= false;}} Process P2{while (true){ while (inside1);//等待 inside2= true;{临界区}; inside2= false;}} Process P2{while (true){ inside2= true; while (inside1);//等待{临界区}; inside2= false;}}

A BUG:P1和P2可能同时进入临界区。

A BUG:P1和P2可能互相等待。11

3.2.3实现临界区管理的软件算法//1981,Peterson算法：只适于两个进程的互斥boolean inside[2]; enum{0,1} turn;初值 inside[0]= inside[1]= false, turn= 0. inside[ i]=true&& turn=i Pi正在临界区中运行 Process P0{while (true){ inside[ 0]= true; turn= 1; while (inside[ 1]&& turn== 1);临界区 inside[ 0]= false; Process P1}}{while (true){ inside[ 1]= true; turn= 0;分析：如果P0执行后， while (inside[ 0]&& turn== 0); P1开始执行会怎样？临界区 inside[ 1]= false;}} 12

3.2.4实现临界区管理的硬件设施关中断可以解决临界区问题。但长时间关中断导致系统效率低；不适合多处理器系统；不能让用户关中断。现代计算机提供特殊的原子硬件指令。不可被中断两种硬件指令： Test and Set:原子地测试并设置一个字的内容。 SWAP:原子地交换两个变量的内容。13

一个临界资源一个lock变量，lock=

false时资源可用； lock= true时进程等待。 lock初值为false(开锁)。bool TS(bool&x){ if (x==true){ x=true; return true;} else{ x=true; return false;}}

void Swap(bool&a, bool&b){ bool tmp=a; a=b; b=tmp;}

用TestAndSet和Swap实现互斥。

{…… while (TS(lock));临界区 lock=false;……}

{…… key=true; while (key==true) Swap(lock,key);临界区 lock=false;……}14

忙等导致CPU效率低。

§3.3

信号量与PV操作

信号量：不要求忙等的同步工具。一个信号量表示一个资源或一个同步条件。信号量 S只能被下面的两个原语访问： P(S) V(S)也称 wait (S)操作也称 signal (S)操作

1965,荷兰，Dijkstra提出

3.3.1同步和同步机制生产者-消费者Producer-Consumer问题：

生产者进程产生信息，供消费者进程使用。有界缓冲：假设缓冲池大小固定，包含k个缓冲区。设公共变量counter一个 BUF in指针对有效缓冲计数。当 counter==0, out指针消费者等待。当 counter==k,消费者取出 Buffer一个 BUF生产者等待。 Pool对counter的访问不加控制会导致错误。16

生产者放入