进程间制约关系

1、操作系统第操作系统第8 8课课进程间的制约关系进程间的制约关系今日内容今日内容u进程的互斥进程的互斥u进程的同步进程的同步u信号量和信号量和P P、V V操作操作内容回顾内容回顾: :进程间的制约关系进程间的制约关系u进程的并发，使一个进程何时占有处理进程的并发，使一个进程何时占有处理机、占有多长时间、执行速度的快慢、机、占有多长时间、执行速度的快慢、以及外界对进程产生作用等都带有随机以及外界对进程产生作用等都带有随机性。因此，一个进程对其他进程的影响性。因此，一个进程对其他进程的影响无法预测。进程间存在制约关系。无法预测。进程间存在制约关系。&间接制约间接制约&直接制约直接制

2、约共享变量修改引起的冲突共享变量修改引起的冲突一个飞机售票系统，两个终端，运行两个进程：一个飞机售票系统，两个终端，运行两个进程：例：对输入井文件目录的管理例：对输入井文件目录的管理u为输出井设置一张为输出井设置一张 “ “输出井文件输出井文件目录表目录表”，它由若干目录项组成，它由若干目录项组成。每个目录项记录一个要打印输。每个目录项记录一个要打印输出的文件名以及该文件在磁盘的出的文件名以及该文件在磁盘的存放地址。存放地址。u两个指针：两个指针：outout和和inin。u两个程序：两个程序：&“井管理写程序井管理写程序”根据根据inin的指点存放的指点存放要求输出的文件目录信息，要

3、求输出的文件目录信息，inin总是指总是指向下一个可用的目录项位置。向下一个可用的目录项位置。&“缓输出程序缓输出程序”根据根据outout的指点进行的指点进行打印，打印，outout总是指向下一个被打印的总是指向下一个被打印的文件。文件。test . cgroup . probit . txt45674out7in输出井文件目录表输出井文件目录表例：通过双缓冲区复制文件例：通过双缓冲区复制文件u编写一个复制n个记录的程序，它把文件F中的每个记录依次读到输入缓冲区R，再从R拷贝到输出缓冲区T，最后写到文件G中。假定R和T正好存放一个记录。u写3个子程序作为进程来完成整个工作：GET：从

4、文件F按照顺序读出一个记录，然后送入输入缓冲区R；COPY：把输入缓冲区R里的记录拷贝到输出缓冲区T里；PUT：从输出缓冲区T里读出一个记录，然后依照顺序写入文件G。记录记录1记录记录2记录记录nGETCOPYPUT文件文件F记录记录1记录记录2记录记录n文件文件G输入缓冲区输入缓冲区R输出缓冲区输出缓冲区T例：通过双缓冲区复制文件例：通过双缓冲区复制文件u在复制过程中，若COPY已把R里的记录拷贝到了T中，那么GET和PUT就可以并发执行了。即GET从F里读出下一个记录送到R中的操作，与PUT从T中取出里面的内容写入G的操作，谁先做谁后做都没有关系，不会影响到复制结果的正确性。由于利用了它们

5、并发性，工作效率就会提高。u但是，如果不去顾及这三者之间执行顺序的这种关系，随意让GET、COPY、PUT去并发执行，那么就会产生错误。 记录记录1记录记录2记录记录nGETCOPYPUT文件文件F记录记录1记录记录2记录记录n文件文件G输入缓冲区输入缓冲区R输出缓冲区输出缓冲区T若不管若不管GET、COPY、PUT的执行关系，那么可有六种执行可能：的执行关系，那么可有六种执行可能： 1）COPYPUTGET；2）COPYGETPUT；3）PUTCOPYGET 4）PUTGETCOPY；5）GETCOPYPUT；6）GETPUTCOPY.记录3记录4记录n文件F记录2记录1文件GRT记录1GE

6、TPUT记录1记录1文件GRT记录3记录4记录n文件F记录1记录4记录n文件F记录3记录1文件GRT记录1COPY记录1记录4记录n文件F记录3记录3文件GRT记录1123(2)(3)(1)(4)进程的互斥进程的互斥u共享变量共享变量&在操作系统中，把那些可以被进程共享的资源（如文在操作系统中，把那些可以被进程共享的资源（如文件、队列、缓冲区、表格、变量等）统称为件、队列、缓冲区、表格、变量等）统称为“共享变共享变量量”或或“临界资源临界资源”。u互斥互斥&与一个共享变量（或临界资源）交往的多个进程，为与一个共享变量（或临界资源）交往的多个进程，为了保证它们各自运行结果的正确性

7、，当其中的一个进了保证它们各自运行结果的正确性，当其中的一个进程正在对该变量（或临界资源）进行操作时，就不允程正在对该变量（或临界资源）进行操作时，就不允许其他进程同时对它进行操作。进程间的这种制约关许其他进程同时对它进行操作。进程间的这种制约关系被称为系被称为“互斥互斥”。 u临界区临界区&把进程程序中把进程程序中“真正需要保证互斥执行真正需要保证互斥执行”的程序，称的程序，称为该进程的为该进程的“临界区（或临界段）临界区（或临界段）”。 一个飞机售票系统，两个终端，运行两个进程：一个飞机售票系统，两个终端，运行两个进程：临界区临界区a := a -1 print (a)a := a

8、 +1 print (a)P1互斥互斥P2互斥互斥If a 0then a := a +1else a:= a-1P3互斥互斥 进程的互斥进程的互斥（间接作用）（间接作用）程 序 段1程 序 段2程 序 段n共 享 变 量使用临界区的原则：使用临界区的原则：（一组并发进程互斥执行时应满足的准则，保证使用共享数据的进程能够正确和高效地运行）有空让进有空让进：当无进程在临界区时，任何有权使用：当无进程在临界区时，任何有权使用临界区的进程之一可进入临界区的进程之一可进入无空等待无空等待：已有进程在临界区，其它欲进入临界：已有进程在临界区，其它欲进入临界区的进程需等待区的进程需等待有限等待有限等待：任

9、何进入临界区的要求应在有限的时：任何进入临界区的要求应在有限的时间内得到满足间内得到满足让权等待让权等待：处于等待状态的进程应放弃占用：处于等待状态的进程应放弃占用CPUCPU，以使其他进程有机会得到，以使其他进程有机会得到CPUCPU的使用权的使用权协同工作协同工作进程同步进程同步从文件从文件F取出一个记取出一个记录送至输入缓冲区录送至输入缓冲区R向向COPY发送发送“可可以拷贝以拷贝” 的消息的消息等待等待COPY发来的发来的“拷贝结束拷贝结束”的消息的消息等待等待GET发来发来“可可以拷贝以拷贝” 的消息的消息将输入缓冲区将输入缓冲区R里的记录里的记录拷贝到输出缓冲区拷贝到输出缓冲区T里

10、里向向GET发送发送“拷拷贝结束贝结束”的消的消息息GETCOPY1.1.2.2.3.3.例：例：GET和和COPY间的协调一致间的协调一致GET读记录到R后，给COPY发送消息，告诉它R中已有记录，然后暂停下来，等待COPY发来 “拷贝结束”的消息，只有接到这个消息，GET才能去做下一步工作。相对地，COPY也一直处于等待。只有接到GET发送来 “可以拷贝”的消息才能工作，将R里的记录拷贝到T里，然后向GET发“拷贝结束”的消息，随之又等待GET发消息。 同步、同步点、同步条件同步、同步点、同步条件u一组并发进程因直接制约而互相发送消息，进一组并发进程因直接制约而互相发送消息，进行互相合作，

11、互相等待，使得各进程按一定的行互相合作，互相等待，使得各进程按一定的速度执行的过程称为速度执行的过程称为进程间的同步进程间的同步。u进程暂停等待以取得同步的那一点，称为进程暂停等待以取得同步的那一点，称为“同同步点步点”。u一个进程需要等待另一个进程完成的操作或发一个进程需要等待另一个进程完成的操作或发送的信息，称为送的信息，称为“同步条件同步条件”。实现进程互斥和同步的方法实现进程互斥和同步的方法1 1、进程互斥的软件方法、进程互斥的软件方法 通过平等协商方式实现进程互斥的通过平等协商方式实现进程互斥的最初方法是软件方法最初方法是软件方法 其基本思路是在进入区检查和设置其基本思路是在进入区检

12、查和设置一些标志，如果已有进程在临界区，一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；则在进入区通过循环检查进行等待；在退出区修改标志在退出区修改标志 其中的主要问题是设置什么标志和其中的主要问题是设置什么标志和如何检查标志如何检查标志软件解法之一软件解法之一 free: free: 表示临界区标志表示临界区标志 true: true: 有进程在临界区有进程在临界区 false:false:无进程在临界区无进程在临界区( (初值初值) ) . . while (free); while (free); free = true; free = true; 临界区临界区 free

13、 = false;free = false;2 2、硬件方法：硬件方法：TSLTSL（“测试并上锁测试并上锁”）指令）指令 借助一条硬件指令来实现互斥的同步机构。借助一条硬件指令来实现互斥的同步机构。 TSL TSL指令：指令： 包括读数和写包括读数和写数两个操作。数两个操作。 enter_region; enter_region; 临界区临界区 leave_region;leave_region;3 3、信号量及、信号量及P.VP.V操作操作19651965年，由荷兰学者年，由荷兰学者DijkstraDijkstra提出（所提出（所以以P P、V V分别是荷兰语的分别是荷兰语的test(pr

14、oberen)test(proberen)和和increment(verhogen)increment(verhogen)），是一种卓），是一种卓有成效的进程同步机制。有成效的进程同步机制。1 1、信号量、信号量semphoresemphore（semsem） 操作系统中，信号量操作系统中，信号量semsem是一整是一整数，大于等于数，大于等于0 0时代表可供并发进时代表可供并发进程使用的资源实体；小于程使用的资源实体；小于0 0时则表时则表示正在等待使用临界区的进程数。示正在等待使用临界区的进程数。信号量的使用：信号量的使用： 通过初始化和两个标准原语来访问。通过初始化和两个标准原语来访问。

15、 1 1、必须置一次且只能置一次初值；、必须置一次且只能置一次初值； 初值不能为负数初值不能为负数 2 2、只能执行、只能执行P P、V V操作操作2 2、P P、V V原语操作原语操作P(sem)P(sem) sem.value - -;sem.value - -; / /表示申请一个资源表示申请一个资源 if (sem.value 0)if (sem.value 0) / /表示无可用资源表示无可用资源 将该进程状态置为等待状态并将该进程插入将该进程状态置为等待状态并将该进程插入与该信号相对应的等待队列中与该信号相对应的等待队列中; ; elseelse / /表示还有可用资源表示还有可用

16、资源 进程继续运行进程继续运行 V(sem) V(sem) sem.value + +sem.value + +; /; /表示释放一个资源表示释放一个资源 if (sem.value = 0) if (sem.value 0 then /sell the ticket count=count-1; 设置信号量设置信号量 S， s.value=1（初始值为初始值为 1）P：P(S) if count0 then /sell the ticket count=count-1 V(S)P P( (S S):): S.value-;S.value-;if (S.value 0) if (S.valu

17、e 0 then /sell the ticket count=count-1 V(S)s.value=0P0：P(S) if count0 then /sell the ticket count=count-1 V(S)P0：P(S) if count0 then /sell the ticket count=count-1 V(S)P1：P(S) if count0 then /sell the ticket count=count-1 V(S)s.value=0P P( (S S):): S.value-;S.value-;if (S.value 0) if (S.value 0 the

18、n /sell the ticket count=count-1 V(S)P P( (S S):): S.value-;S.value-;if (S.value 0) if (S.value 0 then /sell the ticket count=count-1 V(S)P P( (S S):): S.value-;S.value-;if (S.value 0)if (S.value 0 then /sell the ticket count=count-1 V(S)S.value=-1S.list-P1 P1：P(S) if count0 then /sell the ticket co

19、unt=count-1 V(S)P P( (S S):): S.value-;S.value-;if (S.value 0) if (S.value P1 P1：P(S) if count0 then /sell the ticket count=count-1 V(S)P P( (S S):): S.value-;S.value-;if (S.value 0) if (S.value 0 then /sell the ticket count=count-1 V(S)P1：P(S) if count0 then /sell the ticket count=count-1 V(S)S.val

20、ue=-1S.list-P1 唤醒相应等待队列中等待唤醒相应等待队列中等待 的一个进程；的一个进程； 改变其状态为就绪态，改变其状态为就绪态， 并将其插入就绪队列中；并将其插入就绪队列中；P0：P(S) if count0 then /sell the ticket count=count-1 V(S)S.value=-1S.list-P1 唤醒相应等待队列中等待唤醒相应等待队列中等待 的一个进程；的一个进程； 改变其状态为就绪态，改变其状态为就绪态， 并将其插入就绪队列中；并将其插入就绪队列中；P0：P(S) if count0 then /sell the ticket count=cou

21、nt-1 V(S)S.value=0S.list-P1 唤醒相应等待队列中等待唤醒相应等待队列中等待 的一个进程；的一个进程； 改变其状态为就绪态，改变其状态为就绪态， 并将其插入就绪队列中；并将其插入就绪队列中；P0：P(S) if count0 then /sell the ticket count=count-1 V(S)S.value=0S.list-P1 唤醒相应等待队列中等待唤醒相应等待队列中等待 的一个进程；的一个进程； 改变其状态为就绪态，改变其状态为就绪态， 并将其插入就绪队列中；并将其插入就绪队列中；P0：P(S) if count0 then /sell the ticket count=count