《操作系统第5章并发性：互斥和同步》由会员分享，可在线阅读，更多相关《操作系统第5章并发性：互斥和同步（52页珍藏版）》请在金锄头文库上搜索。
1、第第5 5章章 并发性：互斥和同步并发性：互斥和同步主要内容主要内容05.1 5.1 并发的原理并发的原理05.2 5.2 互斥：硬件的支持互斥：硬件的支持05.3 5.3 信号量信号量05.4 5.4 管程管程05.5 5.5 消息传递消息传递05.6 5.6 读者读者/ /写者问题写者问题1与并发相关的关键术语与并发相关的关键术语原子操作原子操作0保证指令序列要么作为一个组来执行，要么都不执行；保证指令序列要么作为一个组来执行，要么都不执行；临界区临界区0一段代码，在这段代码中进程将访问共享资源，当一个一段代码，在这段代码中进程将访问共享资源，当一个进程已经在这段代码中运行时，另外一个进程
2、就不能在进程已经在这段代码中运行时，另外一个进程就不能在这段代码中执行；这段代码中执行；死锁死锁0两个或两个以上的进程因其中的每个进程都在等待其他两个或两个以上的进程因其中的每个进程都在等待其他进程做完某些事情而不能继续执行；进程做完某些事情而不能继续执行；活锁活锁0两个或两个以上进程为了响应其他进程中的变化而持续两个或两个以上进程为了响应其他进程中的变化而持续改变自己的状态但不做有用的工作；改变自己的状态但不做有用的工作；2与并发相关的关键术语与并发相关的关键术语互斥互斥0当一个进程在临界区访问共享资源时，其他进程不能进当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资
3、源；入该临界区访问任何共享资源；竞争条件竞争条件0多个线程或进程在读写一个共享数据时，结果依赖于它多个线程或进程在读写一个共享数据时，结果依赖于它们执行的相对时间；们执行的相对时间；饥饿饥饿0一个可运行的进程被调度程序无限期地忽略，不能被调一个可运行的进程被调度程序无限期地忽略，不能被调度执行的情形。度执行的情形。35.1 5.1 并发的原理并发的原理1 1、基本概念、基本概念并发并发0单处理器多道程序设计系统中，进程交替执行；单处理器多道程序设计系统中，进程交替执行；并行并行0多处理器系统中，不仅可以交替执行进程，还可以重多处理器系统中，不仅可以交替执行进程，还可以重叠执行进程。叠执行进程。
4、并发问题并发问题0并发进程的相对执行速度是不可预测的，取决于其他并发进程的相对执行速度是不可预测的，取决于其他进程的活动、操作系统处理中断的方式以及操作系统进程的活动、操作系统处理中断的方式以及操作系统的调度策略。的调度策略。0可能发生各种与时间有关的错误。可能发生各种与时间有关的错误。4（结果不唯一）机票问题（结果不唯一）机票问题/飞机票售票问题飞机票售票问题void T1( ) void T2( ) void T1( ) void T2( ) 按旅客订票要求找到按旅客订票要求找到AjAj; ; 按旅客订票要求找到按旅客订票要求找到AjAj; intint X1= X1=AjAj; ; in
5、tint X2= X2=AjAj; ; if(X1=1) if(X2=1) if(X1=1) if(X2=1) X1-; X2-; X1-; X2-; AjAj=X1; =X1; AjAj=X2;=X2; 输出一张票输出一张票; ; 输出一张票输出一张票; else else elseelse 输出信息输出信息 票已售完票已售完; ; 输出信息输出信息 票已售完票已售完; 5T1T1、T2T2并发执行，可能出现如下交叉情况：并发执行，可能出现如下交叉情况：T1:X1=T1:X1=AjAj; /X1=m; /X1=mT2:X2=T2:X2=AjAj; /X2=m; /X2=mT2:X2-;Aj=
6、X2;T2:X2-;Aj=X2;输出一张票输出一张票; /; /AjAj=m-1=m-1T1:X1-;Aj=X1;T1:X1-;Aj=X1;输出一张票输出一张票; /; /AjAj=m-1=m-1同一张票卖给两位旅客（若只有一张余票）或者余同一张票卖给两位旅客（若只有一张余票）或者余票数不正确（若有多张余票）。票数不正确（若有多张余票）。6（永远等待）主存管理问题（永远等待）主存管理问题申请和归还主存资源问题申请和归还主存资源问题intint X=memory; /memory X=memory; /memory为初始主存容量为初始主存容量voidvoid borrow(intborrow(i
7、nt B) void B) void return(intreturn(int B) B) while(Bwhile(BX) X=X+B;X) X=X+B; 进程进入等待主存资源队列进程进入等待主存资源队列; ; 修改主存分配表修改主存分配表; X=X-B ; X=X-B ; 释放等主存资源进程释放等主存资源进程; ; 修改主存分配表，修改主存分配表， 进程获得主存资源进程获得主存资源; ; 7若对若对borrowborrow和和returnreturn的并发执行不加限制将会导致的并发执行不加限制将会导致错误，例如：错误，例如：Borrow:while(BBorrow:while(BX);X)
8、;Return:XReturn:X=X+B;=X+B;修改主存分配表修改主存分配表;释放等待主存资释放等待主存资源的进程源的进程 ；此时，因为此时，因为borrowborrow还没有进入等待队列，因此，还没有进入等待队列，因此，returnreturn的释放操作是空操作，当的释放操作是空操作，当borrowborrow进入等待队进入等待队列时，可能没有进程再来归还，处于永远等待状态。列时，可能没有进程再来归还，处于永远等待状态。82 2、操作系统关注的问题、操作系统关注的问题并发带来的设计和管理问题：并发带来的设计和管理问题：0操作系统必须能跟踪不同的进程；操作系统必须能跟踪不同的进程；0操作
9、系统必须为每个活跃进程分配和释放各种资源；操作系统必须为每个活跃进程分配和释放各种资源；0操作系统必须保护每个进程的数据和物理资源；操作系统必须保护每个进程的数据和物理资源；0一个进程的功能和执行结果必须与执行速度无关。一个进程的功能和执行结果必须与执行速度无关。93 3、进程的交互、进程的交互进程间的资源竞争进程间的资源竞争0互斥、死锁、饥饿互斥、死锁、饥饿进程间通过共享合作进程间通过共享合作0互斥、死锁、饥饿、数据一致性互斥、死锁、饥饿、数据一致性进程间通过通信合作进程间通过通信合作0死锁、饥饿死锁、饥饿104 4、互斥的要求、互斥的要求必须强制实施互斥；必须强制实施互斥；一个在非临界区停
10、止的进程不能干涉其他进程；一个在非临界区停止的进程不能干涉其他进程；不允许出现需要访问临界区的进程被无限延迟的不允许出现需要访问临界区的进程被无限延迟的情况；情况；当没有进程在临界区时，任何需要进入临界区的当没有进程在临界区时，任何需要进入临界区的进程必须能够立即进入；进程必须能够立即进入；对相关进程的执行速度和处理器的数目没有任何对相关进程的执行速度和处理器的数目没有任何要求和限制；要求和限制；一个进程驻留在临界区中的时间必须是有限的。一个进程驻留在临界区中的时间必须是有限的。11解决互斥问题的方法解决互斥问题的方法软件方法软件方法0由并发执行的进程担负解决问题的责任；由并发执行的进程担负解
11、决问题的责任；硬件方法硬件方法0中断禁用中断禁用0专用机器指令专用机器指令操作系统或程序设计语言中提供某种级别的支持操作系统或程序设计语言中提供某种级别的支持0信号量信号量0管程管程0消息传递消息传递125.2 5.2 互斥：硬件的支持互斥：硬件的支持1 1、中断禁用、中断禁用while (true)while (true) /* /* 禁用中断禁用中断 * */;/; /* /* 临界区临界区 * */;/; /* /* 启用中断启用中断 * */;/; /* /* 其余部分其余部分 * */;/; 问题：问题：0代价非常高；代价非常高；0不能用于多处理器结构中。不能用于多处理器结构中。13
12、2 2、专用机器指令、专用机器指令比较和交换指令比较和交换指令intint compare_and_swapcompare_and_swap ( (intint *word, *word, intint testvaltestval, , intint newvalnewval) ) intint oldvaloldval; ;oldvaloldval = *word; = *word;if (if (oldvaloldval = = testvaltestval) *word = ) *word = newvalnewval; ;return return oldvaloldval; ; 1
13、4交换指令交换指令void exchange (void exchange (intint register, register, intint memory) memory) intint temp; temp;temp = memory;temp = memory;memory = register;memory = register;register = temp;register = temp; 15互斥协议互斥协议16机器指令方法的优缺点机器指令方法的优缺点优点优点0适用于在单处理器或共享内存的多处理器上的任何数适用于在单处理器或共享内存的多处理器上的任何数目的进程；目的进程；0非常
14、简单且易于证明；非常简单且易于证明；0可用于支持多个临界区，每个临界区可以用它自己的可用于支持多个临界区，每个临界区可以用它自己的变量定义。变量定义。缺点缺点0忙等待；忙等待；0可能饥饿；可能饥饿；0可能死锁。可能死锁。175.3 5.3 信号量信号量19651965年年E.W.DijkstraE.W.Dijkstra提出了新的同步工具提出了新的同步工具-信号量。信号量。基本原理基本原理0两个或多个进程通过简单的信号进行合作，一个进程被两个或多个进程通过简单的信号进行合作，一个进程被迫在某一位置停止，直到它接收到一个特定的信号。迫在某一位置停止，直到它接收到一个特定的信号。0任何复杂的合作需求
15、都可以通过适当的信号结构得到满任何复杂的合作需求都可以通过适当的信号结构得到满足。足。18信号量信号量信号量是一个与队列有关的整型变量。信号量是一个与队列有关的整型变量。0可以初始化成非负数；可以初始化成非负数；0semWaitsemWait操操作作使使信信号号量量减减1 1。若若值值为为负负数数，则则执执行行semWaitsemWait的进程阻塞，否则继续执行；的进程阻塞，否则继续执行；0semSignalsemSignal操操作作使使信信号号量量加加1 1。若若值值小小于于或或等等于于0 0，则则被被semWaitsemWait操作阻塞的进程被解除阻塞。操作阻塞的进程被解除阻塞。信号量的值
16、信号量的值(-2)(-2) 信号量队列指针信号量队列指针19信号量原语的定义信号量原语的定义205.3.1 5.3.1 互斥互斥21互斥的例子互斥的例子225.3.2 5.3.2 生产者生产者/ /消费者问题消费者问题问题描述：问题描述：0有一个或多个生产者生产某种类型的数据，并放置在有一个或多个生产者生产某种类型的数据，并放置在缓冲区中；缓冲区中；0有一个消费者从缓冲区中取数据，每次取一项；有一个消费者从缓冲区中取数据，每次取一项；0系统保证避免对缓冲区的重复操作，即任何时候只有系统保证避免对缓冲区的重复操作，即任何时候只有一个主体（生产者或消费者）可以访问缓冲区。一个主体（生产者或消费者）
17、可以访问缓冲区。0缓存已满时，生产者不能继续添加数据；缓存已满时，生产者不能继续添加数据；0缓存已空时，消费者不能继续移走数据。缓存已空时，消费者不能继续移走数据。231 1、无限缓冲区的生产者、无限缓冲区的生产者/ /消费者问题消费者问题producer:producer:while (true) while (true) /* produce item v */* produce item v */binbin = v; = v;in+; in+; consumer:consumer:while (true) while (true) while (in = out) while (in
18、= out) /*do nothing */;/*do nothing */;w = w = boutbout;out+; out+; /* consume item w */* consume item w */ 24无限缓冲区无限缓冲区25使用信号量解决无限缓冲区生产者使用信号量解决无限缓冲区生产者/ /消费者问题消费者问题262 2、有限缓冲缓冲区的生产者、有限缓冲缓冲区的生产者/ /消费者问题消费者问题producer:producer:while (true) while (true) /* produce item v */ /* produce item v */while (i
19、n + 1) % n = out) while (in + 1) % n = out) /* do nothing */; /* do nothing */;binbin = v; = v;in = (in + 1) % nin = (in + 1) % n 27consumer:consumer:while (true) while (true) while (in = out)while (in = out)/* do nothing */;/* do nothing */;w = w = boutbout;out = (out + 1) % n;out = (out + 1) % n;
20、/* consume item w */ /* consume item w */ 28有限缓冲区有限缓冲区29使用信号量解决有限缓冲区生产者使用信号量解决有限缓冲区生产者/ /消费者问题消费者问题305.6 5.6 读者读者/ /写者问题写者问题问题定义问题定义有一个由多个进程共享的数据区，一些进程只读有一个由多个进程共享的数据区，一些进程只读取这个数据区中的数据，一些进程只往数据区中取这个数据区中的数据，一些进程只往数据区中写数据。并须满足以下条件：写数据。并须满足以下条件：0任意多的读进程可以同时读文件；任意多的读进程可以同时读文件；0一次只有一个写进程可以写文件；一次只有一个写进程可以
21、写文件；0如果一个写进程正在写文件，那么禁止任何读进程读如果一个写进程正在写文件，那么禁止任何读进程读文件。文件。31读者优先读者优先信号量信号量32总结总结信号量小结信号量小结semWaitsemWait和和semSignalsemSignal操作小结操作小结针对信号量问题的补充练习针对信号量问题的补充练习331 1、信号量小结、信号量小结v一个信号量可用于一个信号量可用于n n个进程的同步互斥；且只能由个进程的同步互斥；且只能由semWaitsemWait、semSignalsemSignal操作修改。操作修改。用于互斥时，用于互斥时，S S初值为初值为1 1，取值为，取值为1 - (n-
22、1) 1 - (n-1) （相当于临界区的通行证，实际上也是资源个数）相当于临界区的通行证，实际上也是资源个数） S=1S=1：临界区可用：临界区可用 S=0S=0：已有一进程进入临界区：已有一进程进入临界区 S0S=0=0 S=0:S=0:表示可用资源个数表示可用资源个数 S0:S0: 表示该资源的等待队列长度表示该资源的等待队列长度342 2、 semWaitsemWait、semSignalsemSignal操作小结操作小结semWait(SsemWait(S) )：请求分配一个资源。请求分配一个资源。semSignal(SsemSignal(S) )：释放一个资源。释放一个资源。sem
23、WaitsemWait、semSignalsemSignal操作必须成对出现。操作必须成对出现。 用于互斥时，位于同一进程内；用于互斥时，位于同一进程内； 用于同步时，交错出现于两个合作进程内。用于同步时，交错出现于两个合作进程内。多个多个semWaitsemWait操作的次序不能颠倒，否则可能导致操作的次序不能颠倒，否则可能导致死锁。死锁。 多个多个semSignalsemSignal操作的次序可任意。操作的次序可任意。353 3、针对信号量问题的补充练习、针对信号量问题的补充练习1)1)桌子上有一个盘子，可以存放一个水果。父亲总桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而
24、母亲总是放香蕉到盘子中；是放苹果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃盘中的香蕉，而女儿专等吃盘中的苹儿子专等吃盘中的香蕉，而女儿专等吃盘中的苹果。果。分析：生产者消费者问题的一种变形，生产者、消费分析：生产者消费者问题的一种变形，生产者、消费者以及放入缓冲区的产品都有两类，但每类消费者只消者以及放入缓冲区的产品都有两类，但每类消费者只消费其中固定的一种产品。费其中固定的一种产品。数据结构：数据结构：semaphore dishsemaphore dish， apple apple ， banana ;banana ;dishdish：表示盘子是否为空，初值为表示盘子是否为空，初值为1
25、 1appleapple：表示盘中是否有苹果，初值为表示盘中是否有苹果，初值为0 0bananabanana：表示盘中是否有香蕉，初值为表示盘中是否有香蕉，初值为0 036process father()process father() semWait(dishsemWait(dish);); 将苹果放到盘中；将苹果放到盘中； semSignal(applesemSignal(apple);); process mother()process mother() semWait(dishsemWait(dish);); 将香蕉放到盘中；将香蕉放到盘中； semSignal(bananasemSi
26、gnal(banana);); process son()process son() semWait(bananasemWait(banana);); 从盘中取出香蕉；从盘中取出香蕉； semSignal(dishsemSignal(dish);); process daughter()process daughter() semWait(applesemWait(apple);); 从盘中取出苹果；从盘中取出苹果； semSignal(dishsemSignal(dish);); 372)2)在一个盒子里，混装了数量相等的黑白围棋子。现在用在一个盒子里，混装了数量相等的黑白围棋子。现在用自动
27、分拣系统把黑子、白子分开，设分拣系统有两个进自动分拣系统把黑子、白子分开，设分拣系统有两个进程程P1P1和和P2P2，其中，其中P1P1拣白子，拣白子，P2P2拣黑子。规定每个进程每拣黑子。规定每个进程每次拣一子，当一个进程在拣时，不允许另一个进程去拣；次拣一子，当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试用当一个进程拣了一子时，必须让另一个进程去拣。试用信号量和信号量和P P、V V操作协调两个进程的并发执行。操作协调两个进程的并发执行。分析：分析：实际上就是两个进程的同步问题。实际上就是两个进程的同步问题。数据结构：数据结构：semaphore S
28、1semaphore S1， S2 ;S2 ;S1 和和S2 分别表示可拣白子和黑子，不失一般性，若分别表示可拣白子和黑子，不失一般性，若令先拣白子。初值，令先拣白子。初值， S1=1； S2=0；38process P1()process P1() while(truewhile(true) semWait(S1); semWait(S1); 拣白子；拣白子； semSignal(S2);semSignal(S2); process P2( ) while(true) semWait(S2); 拣黑子；拣黑子； semSignal(S1); 395.4 5.4 管程管程管程是一个或多个过程、
29、一个初始化序列和局部管程是一个或多个过程、一个初始化序列和局部数据组成的软件模块，主要特点如下：数据组成的软件模块，主要特点如下：0局部数据变量只能被管程的过程访问，任何外部过程局部数据变量只能被管程的过程访问，任何外部过程都不能访问；都不能访问；0一个进程通过调用管程的一个过程进入管程；一个进程通过调用管程的一个过程进入管程；0在任何时候，只能有一个进程在管程中执行，调用管在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程可用。程的任何其他进程都被阻塞，以等待管程可用。管程通过条件变量提供对同步的支持。条件变量管程通过条件变量提供对同步的支持。条件变量只有在管
30、程中才能被访问。只有在管程中才能被访问。0cwait(ccwait(c) )：调用管程的进程在条件：调用管程的进程在条件c c上阻塞。上阻塞。0csignal(ccsignal(c) )：恢复执行在：恢复执行在cwaitcwait之后因为某些条件而阻之后因为某些条件而阻塞的进程。塞的进程。40管程的结构管程的结构41使用管程解决有界缓冲区的生产者使用管程解决有界缓冲区的生产者/ /消费者问题消费者问题42435.5 5.5 消息传递消息传递消息传递：合作进程之间进行信息交换。消息传递：合作进程之间进行信息交换。消息传递原语消息传递原语0send (destination, message)se
31、nd (destination, message)0receive (source, message)receive (source, message)445.5.1 5.5.1 同步同步阻塞阻塞send,send,阻塞阻塞receivereceive0发送者和接收者都被阻塞，直到完成信息的投递。发送者和接收者都被阻塞，直到完成信息的投递。无阻塞无阻塞send,send,阻塞阻塞receivereceive0接收者阻塞，直到请求的信息到达。接收者阻塞，直到请求的信息到达。无阻塞无阻塞send,send,无阻塞无阻塞receivereceive0不要求任何一方等待。不要求任何一方等待。455.5
32、.2 5.5.2 寻址寻址直接寻址直接寻址0sendsend原语包含目标进程的标识号；原语包含目标进程的标识号；0receivereceive原语可显式地指定源进程，也可不指定。原语可显式地指定源进程，也可不指定。间接寻址间接寻址0发送者将消息发送到合适的信箱；发送者将消息发送到合适的信箱；0接收者从信箱中获得消息。接收者从信箱中获得消息。465.5.3 5.5.3 消息格式消息格式固定长度消息固定长度消息可变长度消息可变长度消息消息类型消息类型目的进程标识符目的进程标识符源进程标识符源进程标识符消息长度消息长度控制信息控制信息消息内容消息内容消息头消息头消息体消息体475.5.4 5.5.4
33、 排队原则排队原则先进先出先进先出优先级优先级485.5.5 5.5.5 互斥互斥49使用消息解决有界缓冲区生产者使用消息解决有界缓冲区生产者/ /消费者问题消费者问题50作业作业1 1、写出信号量定义，、写出信号量定义，semWaitsemWait和和semSignalsemSignal原语，原语，以及用信号量实现互斥的伪代码。以及用信号量实现互斥的伪代码。2 2、假设一个阅览室有、假设一个阅览室有100100个座位，没有座位时读者个座位，没有座位时读者在阅览室外等待；每个读者进入阅览室时都必须在阅览室外等待；每个读者进入阅览室时都必须在阅览室门口的一个登记本上登记座位号和姓名，在阅览室门口
34、的一个登记本上登记座位号和姓名，然后阅览，离开阅览室时要去掉登记项。每次只然后阅览，离开阅览室时要去掉登记项。每次只允许一个人登记或去掉登记。用信号量操作描述允许一个人登记或去掉登记。用信号量操作描述读者的行为。读者的行为。51作业作业3 3、设公共汽车上，司机和售票员活动如下：、设公共汽车上，司机和售票员活动如下：1 1）司机：启动汽车，正常行车，到站停车；）司机：启动汽车，正常行车，到站停车；2 2）售票员：关车门，售票，开门上下客。）售票员：关车门，售票，开门上下客。用信号量操作描述司机和售票员的同步。用信号量操作描述司机和售票员的同步。4 4、 ( (选做选做) )独木桥问题：东、西向汽车过独木桥。独木桥问题：东、西向汽车过独木桥。桥上无车时允许一方汽车过桥，待全部过完后才桥上无车时允许一方汽车过桥，待全部过完后才允许另一方汽车过桥。用信号量操作写出同步算允许另一方汽车过桥。用信号量操作写出同步算法。法。( (提示：参考读者优先的解法提示：参考读者优先的解法) )52
