《操作系统原理教程(第3版)第三章课件》由会员分享，可在线阅读，更多相关《操作系统原理教程(第3版)第三章课件（134页珍藏版）》请在金锄头文库上搜索。
1、第第3 3章章 进程之间的并发进程之间的并发 控制和死锁控制和死锁2.6 2.6 进程之间的低级通信进程之间的低级通信多道程序系统中进程是并发执行的，并 发进程之间存在着相互制约关系，为了协 调进程之间的相互制约关系，就需要实现 进程的低级通信。系统之间之所以有这种关系是由于 以下两方面的原因造成的：(1) 各并发进程对资源的共享 互斥关系：通过共享资源而使进程之间产生的关 系叫做间接制约关系，又叫做互斥关系。用“进程-资源-进程” 描述。例 进程P1和P2在运行中都要使用打印机，为了 使各进程输出的完整性，打印机的使用必须独 占。一旦系统将打印机分配给进程P1，那么进 程P2必须等待。P1-
2、打印机-P2(2) 系统中存在若干协作进程 同步关系：一个用户作业涉及一组并发进程（输入 、计算和输出进程），这些进程须相互协作共同 完成这项任务。进程之间的这种制约关系叫做直 接制约关系。互斥是同步的一种特殊情况。低级通信：进程之间的这种相互依赖又相互制约、 相互合作又相互竞争的关系，也即进程的同步与 互斥关系,也叫进程之间的低级通信。共享资源引起进程之间的互斥 几个基本概念： l 共享资源：慢速的硬设备，如打印机等资源， 软件资源，如共享变量、共享文件等。l 临界资源：一次仅允许一个进程使用的资源。具 有这种特点的上述资源。 临界资源：上一章打印机的例子： 如何避免这种情况发生，关键是防止
3、多个进 程同时读或写共享数据。换句话就是必须 互斥的使用共享变量in。l 临界区(critical section)：就是并发执行的进程访 问临界资源的那个必须互斥执行的程序段。2.6.1 进程之间的互斥 进程之间的互斥l为进一步说明临界资源的概念，下面举一个著 名的进程同步问题的例子：l生产者_消费者问题。l在生产者与消费者问题中，描述的是生产者与 消费者的关系。有一个生产者进程生产产品， 并将所生产的产品提供给一个消费者进程去消 费。为了使生产者与消费者并发进行，在两者 之间设置了一个具有n个缓冲区的缓冲池，尽 管生产者与消费者都以异步的方式进行，但是 它们之间必须保持一定的同步关系。即消
4、费者 进程不允许到空缓冲区去取产品，也不允许生 产者进程向一个已装满产品，且尚未取走的缓 冲区投放产品。进程之间的互斥我们利用一个数组表示上述具有n个缓冲区的缓冲池。 使用输入指针in指示下一个可以放产品的缓冲区，每放一 个产品指针加1。 用一个输出指针out指示下一个可以取从中取产品的缓冲 区，每当消费者进程从缓冲区取走一个产品输出指针 加1 由于缓冲区使用的是循环缓冲数组方式，所以输入加1表 示为in=（in+1）mod n 同样输出加1表示为out=（out+1）mod n 当（in+1）mod n=out，表示缓冲区满。 初始状态in=out表示缓冲区空。 此外还要设置一个表示缓冲区产
5、品数量的变量counter初 值为0，每投放一个产品counter加1，消费者每取走一 个产品counter减1进程之间的互斥生产者与消费者共享下列变量： Var n, integer; Type item=“” ; Var buffer:arry0,1,2,n-1of item; In, out :0,1,n-1; Counter: 0,1,n; In和out初始化为1。Noop表示控操作； While condition do no-op语句表示重复测试条件（ condition）直到条件为假false. 生产者使用一个局部变量nextp,用于存放每次刚刚生产出 来的产品， 消费者使用一局
6、部变量nextc存放每次将要消费的产品。 则有程序：进程之间的互斥Producer: repeat produce an item in nextp; .while counter=n do no-op;bufferin:=nextp;In:=(in+1)mod n;Counter:=counter+1;Until fase;Consumer: repeatwhile counter=0 do no-op;nextc:=bufferout;out:=(out+1)mod ncounter:=counter-1;consumer the item in nextc;until false进程之间
7、的互斥这个程序显然是正确的，串行运行也是正确的，但是如 果并行运行结果就不一定正确：其问题出现在两个进 程共享了变量counter。其生产者加1操作和消费者的减 1操作，在计算机上实现时可用下面语句描述： 其生产者加1操作: Register1:=counter; Register1:=register1+1; Counter:=register1; 消费者减1操作: Register2:=counter; Register2:=register2-1; Counter:=register2; 假设现在counter当前值为5如果顺序执行先生产者后消费者执行一遍counter内的值 为5，但按
8、如下顺序执行： Register1:=counter; register1=5 Register1:=register1+1； register1=6 Register2:=counter; register2=5 Register2:=register2-1; register2=4 Counter:=register1; counter=6 Counter:=register2； counter=4 正确值应该是5，可执行结果为4.又是结果还可能是6。 表明程序并运行时已失去了再现性。 这就是因为counter变量属于临界资源，而生产者与消费 者没有互斥的访问它们，对counter的访问具
9、有很大的 任意性，故产生了不确定性，解决问题的关键是将 counter作为临界资源来处理，即要求生产者和消费者 互斥访问。进程之间的互斥进程之间的互斥l临界区(critical section)：就是并发执行的进程 访问临界资源的那个必须互斥执行的程序段。l在实现互斥时如果采取整体的程序采取互斥运 行将会大大降低进程的并发性。事实上每个进 程访问某个临界区的代码只是一小段，因此只 需控制进程互斥的进入这一小段代码。我们将 这一小段代码叫做临界区。l为此进程在进入临界区之前应对临界区进行检 查，看是否被访问的标志，我们将这一段代码 成为进入区(entry section),l同样退出临界区应将其
10、标志为未被访问，这一 段代码称为退出区（exit section）l此外的代码可成为剩余区（remainder section）l于是可以将访问临界资源的循环进程描述为进程之间的互斥repeat entry sectioncritical sectionExit sectionRemainder section Until false任何时刻最多只有一个进程位于临界区。 有空让进当已有进程处于其临界区时，后到达的进程只能 在外等待。无空等待不应该使要进入临界区的进程无限期地等待在临 界区之外。有限等待不能进入临界区的进程，应先释放处理机，转换 到阻塞状态。让权等待为了正确而有效地使用临界资源，
11、系统中 的并发进程需要遵循如下四个准则：有空让进；无空等待；有限等待；让权等待。2. 解决进程之间互斥的方法 (1) 关中断 解决进程互斥的最简单办法是当一 个进程正在临界区执行时，关闭所有的中断。当进程退出临界段时，再开中断。之后其它 要进入临界区的进程就可进入。描述如下：关中断(disable) critical section开中断(enable) 优点：简单。 缺点：限制了进程并发执行的能力。 在多 处理机情况下，这种方法不灵。l锁位变量W ：为每个临界资源设置一个，以 指示该资源当前的状态。系统初始化时，将 W置为0。 lTestset指令可定义如下：(2) 使用测试和设置指令(te
12、st and set)testset(int w)l: if(w=0) w=1;else goto l;/一条机器指令，其执行不可被中断。Const int n=/*进程数 */ int w; void p(int i)while(TRUE)testset(w);w=0;显然，采用 这种加锁语 句，由于进 程循环测试 ，白白浪费 了CPU的时间 。这种现象 又叫做“忙 等待”。void main() w=0;p(1);p(2);p(n);同步的原因：一组进程要合作完成一项任务 。 例两个用户进程通过共享缓冲区完成其计 算和打印任务。2.6.2 进程之间的同步共享缓冲区计算进程打印进程 计算进程
13、在缓冲区满时等待，打印进程在缓冲 区空时等待。两个进程这种由于速度不匹配引起 的关系，需要进行同步处理。 为了解决进程之间的同步，引入信号量机制。l1965年，荷兰学者Dijkstra提出的一种同 步机制。 l基本原理：两个或多个进程可以通过简单 的信号机制，进行同步。为此，需要引入 一个称作的特殊变量信号量。2.6.3 信号量和PV操作typedef struct semaphoreint value; /表示该类资源的可用数量struct process *pointer; /等待使用该类 资源的进程排成队列的队列头指针。 sem;v 对信号量s只允许执行P、V操作。v P、V操作由原语组
14、成，执行过程中不可分割。信号量的类型描述：Sem s；P（S)操作原语： void wait (sem s) s.value=s.value-1; /表示申请一个资源 if(s.value0,S=0,和S0表示有资源，进程可以进如临界区。S=0表示资源数已经为0，进程应到指针指向的队列去排队 。S=n时，xn;m=n和m= 1 then V(S2)；lR:=R-1;lV(S);l离开理发店lend习题习题l理发师的活动：lBeginl L2: P(S1); /检查是否有顾客理发， 无则睡觉l给顾客理发；lGoto L2；lend习题习题l3_19 假定系统中只有一类资源，且进程一次 只申请一个
15、单位的资源，并且进程申请的资 源数不会超过系统拥有的资源总数。假定进 程申请的资源总数为2，且系统资源总数如下 ：问下列哪些情况会发生死锁？进程数资源总数进程数资源总数（1）12（4）33（2）22（5）35（3）23（6）45习题习题l答：会死锁的（2），（4）l ：情况2，4 会发生死锁。习题习题l3_21.考虑某一系统，有四类资源R1, R2, R3 , R4. 有5个并发进程P0,P1, P2,P3,P4. 请按银行家算法回答下列问题。l（1）各进程的最大资源请求和已分配的 资源矩阵，及系统当前的剩余资源向量 如图所示，计算各进程剩余资源请求向 量组成的矩阵。l（2）系统当前处于安全状态吗？l（3）当进程P2申请资源分别为（1，0， 0，1）时，系统能立即满足吗？习题习题分配向量最大需求量 R1R2R3R4R1R2R3R4 P000120012 P110001750 P213542356 P306320652 P400140656R1R2R3R41502习题习题 3_21。l（1）当前系统是安全的。这是因为：l 剩余资源向量：1502l 剩余请求矩阵为： 已分配矩阵：l 0 0 0 0 0 0 1 2l 0 7 5 0 1 0 0 0l 1 0 0
