进程间制约关系

操作系统第8课进程间的制约关系今日内容进程的互斥进程的同步信号量和P、V操作内容回顾:进程间的制约关系进程的并发，使一个进程何时占有处理机、占有多长时间、执行速度的快慢、以及外界对进程产生作用等都带有随机性。因此，一个进程对其他进程的影响无法预测。进程间存在制约关系。间接制约直接制约共享变量修改引起的冲突一个飞机售票系统，两个终端，运行两个进程：例：对输入井文件目录的管理

为输出井设置一张“输出井文件目录表”，它由若干目录项组成。每个目录项记录一个要打印输出的文件名以及该文件在磁盘的存放地址。两个指针：out和in。两个程序：“井管理写程序”根据in的指点存放要求输出的文件目录信息，in总是指向下一个可用的目录项位置。“缓输出程序”根据out的指点进行打印，out总是指向下一个被打印的文件。bit.txt45674out7in输出井文件目录表例：通过双缓冲区复制文件编写一个复制n个记录的程序，它把文件F中的每个记录依次读到输入缓冲区R，再从R拷贝到输出缓冲区T，最后写到文件G中。假定R和T正好存放一个记录。写3个子程序作为进程来完成整个工作：GET：从文件F按照顺序读出一个记录，然后送入输入缓冲区R；COPY：把输入缓冲区R里的记录拷贝到输出缓冲区T里；PUT：从输出缓冲区T里读出一个记录，然后依照顺序写入文件G。记录1记录2记录nGETCOPYPUT文件F记录1记录2记录n文件G输入缓冲区R输出缓冲区T例：通过双缓冲区复制文件在复制过程中，若COPY已把R里的记录拷贝到了T中，那么GET和PUT就可以并发执行了。即GET从F里读出下一个记录送到R中的操作，与PUT从T中取出里面的内容写入G的操作，谁先做谁后做都没有关系，不会影响到复制结果的正确性。由于利用了它们并发性，工作效率就会提高。但是，如果不去顾及这三者之间执行顺序的这种关系，随意让GET、COPY、PUT去并发执行，那么就会产生错误。

记录1记录2记录nGETCOPYPUT文件F记录1记录2记录n文件G输入缓冲区R输出缓冲区T若不管GET、COPY、PUT的执行关系，那么可有六种执行可能：

1）COPY→PUT→GET；2）COPY→GET→PUT；3）PUT→COPY→GET4）PUT→GET→COPY；5）GET→COPY→PUT；6）GET→PUT→COPY.记录3记录4记录n文件F记录2记录1文件GRT记录1GETPUT记录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)进程的互斥共享变量在操作系统中，把那些可以被进程共享的资源（如文件、队列、缓冲区、表格、变量等）统称为“共享变量”或“临界资源”。互斥与一个共享变量（或临界资源）交往的多个进程，为了保证它们各自运行结果的正确性，当其中的一个进程正在对该变量（或临界资源）进行操作时，就不允许其他进程同时对它进行操作。进程间的这种制约关系被称为“互斥”。临界区把进程程序中“真正需要保证互斥执行”的程序，称为该进程的“临界区（或临界段）”。一个飞机售票系统，两个终端，运行两个进程：临界区a:=a-1print(a)a:=a+1print(a)P1互斥P2互斥Ifa<0thena:=a+1elsea:=a-1P3互斥

进程的互斥（间接作用）使用临界区的原则：（一组并发进程互斥执行时应满足的准则，保证使用共享数据的进程能够正确和高效地运行）有空让进：当无进程在临界区时，任何有权使用临界区的进程之一可进入无空等待：已有进程在临界区，其它欲进入临界区的进程需等待有限等待：任何进入临界区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权协同工作——进程同步从文件F取出一个记录送至输入缓冲区R向COPY发送“可以拷贝”的消息等待COPY发来的“拷贝结束”的消息等待GET发来“可以拷贝”的消息将输入缓冲区R里的记录拷贝到输出缓冲区T里向GET发送“拷贝结束”的消息GETCOPY.3.3.例：GET和COPY间的协调一致GET读记录到R后，给COPY发送消息，告诉它R中已有记录，然后暂停下来，等待COPY发来“拷贝结束”的消息，只有接到这个消息，GET才能去做下一步工作。相对地，COPY也一直处于等待。只有接到GET发送来“可以拷贝”的消息才能工作，将R里的记录拷贝到T里，然后向GET发“拷贝结束”的消息，随之又等待GET发消息。同步、同步点、同步条件一组并发进程因直接制约而互相发送消息，进行互相合作，互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。进程暂停等待以取得同步的那一点，称为“同步点”。一个进程需要等待另一个进程完成的操作或发送的信息，称为“同步条件”。实现进程互斥和同步的方法1、进程互斥的软件方法通过平等协商方式实现进程互斥的最初方法是软件方法其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志其中的主要问题是设置什么标志和如何检查标志软件解法之一free:表示临界区标志

true:有进程在临界区

false:无进程在临界区(初值)

....

while(free);

free=true;

临界区

free=false;2、硬件方法：TSL（“测试并上锁”）指令

借助一条硬件指令来实现互斥的同步机构。TSL指令：包括读数和写数两个操作。enter_region;

临界区

leave_region;3、信号量及P.V操作1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。1、信号量semphore（sem）操作系统中，信号量sem是一整数，大于等于0时代表可供并发进程使用的资源实体；小于0时则表示正在等待使用临界区的进程数。信号量的使用：

通过初始化和两个标准原语来访问。1、必须置一次且只能置一次初值；初值不能为负数

2、只能执行P、V操作2、P、V原语操作P(sem){

sem.value--;//表示申请一个资源

if(sem.value<0)//表示无可用资源

{

将该进程状态置为等待状态并将该进程插入与该信号相对应的等待队列中;

}else//表示还有可用资源

{进程继续运行}}V(sem){

sem.value++;//表示释放一个资源

if(sem.value<=0)//表示有等待使用资源的进程

{唤醒相应等待队列中等待的一个进程；改变其状态为就绪态；并将其插入就绪队列。

}

进程继续运行或转进程调度程序}用P、V操作解决进程间互斥问题为临界资源设置一个互斥信号量mutex，并设初值（有几个共享资源初值就为几）；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间。用P、V操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3临界区P(mutex)P(mutex)V(mutex)V(mutex)注意：必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；

例：用信号量来解决飞机售票系统的互斥问题：

Program：

...ifcount>0then{//selltheticketcount=count-1;}

设置信号量S，s.value=1（初始值为

1）P：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--; if(S.value<0){

将该进程状态置为等待状态并将该进程插入与该信号相对应的等待队列S.list中;

block; }}

s.value=1s.value=0P0：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)s.value=0P0：P(S)ifcount>0then

{

//selltheticketcount=count-1}V(S)P0：P(S)ifcount>0then

{

//selltheticketcount=count-1}V(S)P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)s.value=0P(S): {

S.value--; if(S.value<0){

将该进程状态置为等待状态并将该进程插入与该信号相对应的等待队列S.list中;

block; }}

s.value=0P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--; if(S.value<0){

将该进程状态置为等待状态并将该进程插入与该信号相对应的等待队列S.list中;

block; }}

s.value=-1P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--;

if(S.value<0)

{

将该进程状态置为等待状态并将该进程插入与该信号相对应的等待队列S.list中;

block; }}s.value=-1P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=-1S.list->P1

P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--; if(S.value<0){

将该进程状态置为等待状态并将该进程插入与该信号相对应的等待队列S.list中;

block; }}

S.value=-1S.list->P1

P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)P(S): {

S.value--; if(S.value<0){

将该进程状态置为等待状态并将该进程插入与该信号相对应的等待队列S.list中;

block; }}

P0：P(S)ifcount>0then

{

//selltheticketcount=count-1}V(S)P1：P(S)

ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=-1S.list->P1

V(S):

S.value++;if(S.value<=0){

唤醒相应等待队列中等待的一个进程；改变其状态为就绪态，并将其插入就绪队列中；

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=-1S.list->P1

V(S):

S.value++;if(S.value<=0){

唤醒相应等待队列中等待的一个进程；改变其状态为就绪态，并将其插入就绪队列中；

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0S.list->P1

V(S):

S.value++;if(S.value<=0){

唤醒相应等待队列中等待的一个进程；改变其状态为就绪态，并将其插入就绪队列中；

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0S.list->P1

V(S):

S.value++;if(S.value<=0){

唤醒相应等待队列中等待的一个进程；改变其状态为就绪态，并将其插入就绪队列中；

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0S.List->P1

V(S):

S.value++;if(S.value<=0){

唤醒相应等待队列中等待的一个进程；改变其状态为就绪态，并将其插入就绪队列中；

}P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0唤醒

P1

P0：P(S)ifcount>0then{

//selltheticketcount=count-1}V(S)S.value=0唤醒P1

P1：P(S)

ifco