操作系统原理第四章(03)

1第四章并发处理24.6信号灯和P、V操作4.6.1信号灯的概念信号灯的概念是由Dijkstra提出的（1968）。他把互斥的关键概念抽象到信号量这个概念中，信号量是一个被保护的变量，只有P操作、V操作和一种称为信号量初始化操作才能访问和改变它的值。34.6信号灯和P、V操作4.6.1信号灯的概念信号灯的定义：信号灯是一个确定的二元组（s,q），s是一个具有非负初值的整型变量，q是一个初始状态为空的排队站。s代表资源的实体。在实际应用中应准确地说明s的意义和初值，每个信号灯都有一个队列，其初始状态为空。44.6信号灯和P、V操作4.6.2P、V操作信号灯的值仅能由P、V操作来改变。对信号灯的P操作记为：P(S)，P操作是一个原子操作。对信号灯的V操作记为：V(S),V操作是一个原子操作。在实际操作系统中，一般情况下是由机器硬件提供P、V操作的指令，当然是原子操作，若机器不提供P、V操作的指令，则操作系统提供P、V操作原语。54.6信号灯和P、V操作4.6.2P、V操作P操作：（1）s值减1；（2）若相减结果大于等于0，则进程继续执行；（3）若结果小于0，则该进程挂起。64.6信号灯和P、V操作4.6.2P、V操作算法P输入：变量s输出：无｛s--;if(s0){保留调用进程CPU现场；将该进程入s的等待队列；置“等待”状态；转进程调度程序；}｝74.6信号灯和P、V操作4.6.2P、V操作V操作：（1）s值加1；（2）若相加结果大于0，进程继续执行；（3）否则，唤醒一个（或多个）等待该信号灯的进程，然后本进程继续执行。84.6信号灯和P、V操作4.6.2P、V操作算法V输入：变量s输出：无｛s++;if(s=0){移出s等待队列首元素；将该进程入就绪队列；置“就绪”态；}｝94.6信号灯和P、V操作4.6.3用信号灯实现进程互斥例：两个进程共享打印机设信号灯mutex(互斥)表示打印机，初值为1，表示打印机可用。104.6信号灯和P、V操作4.6.3用信号灯实现进程互斥main(){intmutex=1;cobeginppa();ppb();coend}ppa(){…;p(mutex);使用打印机；v(mutex);…;}ppb(){…;p(mutex);使用打印机；v(mutex);…;}两个进程共用打印机mutex(1,0,-1)1：打印机空闲；0：有一个进程正在使用打印机；-1：有一个进程正在使用打印机，还有一个进程等待使用打印机；114.6信号灯和P、V操作4.6.3用信号灯实现进程互斥ppa(){…;p(mutex);使用打印机；v(mutex);…;}若P,V操作不是原语操作，会出现什么问题？1.初值：mutex=1;2.进程ppa进入P操作：s--；使得mutex=0;3.进程ppb进入P操作：s--；使得mutex=-1;4.进程ppa：if(s0)条件满足，将自己挂起；5.进程ppb：if(s0)条件满足，将自己挂起；6.结果：ppa和ppb都挂起？谁唤醒它们？算法P｛s--;if(s0){保留调用进程CPU现场；将该进程入s的等待队列；置“等待”状态；转进程调度程序；}｝124.7进程同步4.7.1同步的例子例:司机售票员启动关门正常运行售票到站停开门134.7进程同步4.7.2同步的概念互斥的概念来自于诸进程对独占使用资源（设备）的竞争；同步来源于多个进程的合作。在人类社会中竞争与合作是永恒的。同步：并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。144.7进程同步4.7.3用信号灯实现进程的同步同步可归纳为：•诸进程合作完成某工作的逻辑顺序；•对系统资源的共享。如两个进程共享一个缓冲区完成誊抄问题154.7进程同步4.7.3用信号灯实现进程的同步（一）合作进程的执行次序用进程流图来描述诸进程合作完成某一任务的次序。164.7进程同步4.7.3用信号灯实现进程的同步用信号灯及P、V操作来描述左图1、说明进程的同步关系进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。2、设置信号灯，说明含义、初值。s13=0表示进程P1尚未执行完成；s23=0表示进程P2尚未执行完成；174.7进程同步4.7.3用信号灯实现进程的同步main(){ints13=0,s23=0;cobeginp1();p2();p3();coend;}p1(){…;v(s13);}p2(){…;v(s23);}p3(){p(s13);p(s23);…;}184.7进程同步4.7.3用信号灯实现进程的同步(二）共享缓冲区的合作进程的同步设有一个缓冲区buffer，大小为一个字节，CP进程不断产生字符，送buffer，IOP进程从buffer中取出字符打印。如不加控制，会有什么结果？194.7进程同步4.7.3用信号灯实现进程的同步要保证打印结果的正确，CP、IOP必须遵循以下同步规则：(1)当CP把结果送入buffer后，IOP才能从buffer中取，否则IOP必须等待；(2)当IOP从buffer中取走数据后，CP才能将新产生数据送buffer，否则也必须等待。204.7进程同步4.7.3用信号灯实现进程的同步解决这个问题的步骤：(1)分析问题，弄清楚同步关系，如上分析；(2)设置信号灯，说明含义、初值；(3)写出程序描述。214.7进程同步4.7.3用信号灯实现进程的同步sb:buffer是否有空位存放数据。初值为1：缓冲区空闲。sa:buffer是否有数据可打印。初值为0：缓冲区无数据。main(){intsa=0;intsb=1;cobegincp();iop();}cp(){while(计算未完成){得到一个计算结果;p(sb);将数据送入buffer;v(sa);}}iop(){while(打印未完成){p(sa);从buffer中取数据;v(sb);从打印机上输出；}}224.7进程同步4.7.4生产者－消费者问题假定缓冲区buffer是一个有界缓冲区，可存放n个数据，同时假定有n个CP进程不断地产生数据，并送buffer；有m个IOP进程从缓冲区中取数据打印。234.7进程同步4.7.4生产者－消费者问题•仓库有n个仓位•生产者制造产品，并送仓库•消费者从仓库取产品消费244.7进程同步4.7.4生产者－消费者问题生产者：产生一个数据送入缓冲区时，要检查缓冲区是否已满，若未满，则送入数据，并通知消费者进程；否则，等待；消费者：取数据时，要检查缓冲区中是否有数据，若有则取走一个数据，并通知生产者进程，否则，等待。这种相互等待，并互通信息就是典型的进程同步。同时，缓冲区是临界资源，因此，诸进程对缓冲区的操作程序是一个共享临界区，因此，还有个互斥的问题。254.7进程同步4.7.4生产者－消费者问题full:缓冲区产品数目，初值为0；empty:缓冲区可存放产品的空位，初值为n;mutex:缓冲区互斥信号灯，初值为1。main(){intfull=0;intempty=n;intmutex=1;cobeginpruducer();consumer();coend}264.7进程同步4.7.4生产者－消费者问题producer(){while(生产未完成){…;生产一个产品；p(empty);p(mutex);送一个产品到buffer;v(mutex);v(full);}}consumer(){while(还要继续消费){p(full);p(mutex);从buffer中取一个产品;v(mutex);v(empty);…;}}274.7进程同步4.7.4生产者－消费者问题思考：p(empty)和p(mutex)能否交换？28补充题1：读者写者问题。•有十个读者和两个编辑同时处理一篇文章；•对于读操作是可以同时进行的；•若有读者正在读，编辑就不能工作；•若编辑正在处理，读者就不能读；•编辑与编辑的工作也是互斥的。试用信号灯及P、V操作写出读者与编辑之间协同工作的程序描述。29补充题1：读者写者问题。mutex:互斥信号灯，初值为1。main(){intcounter=0;intmutex=1;cobeginreadi();editi();coend}readi(){if(counter==0)p(mutex);counter++;读文章;counter--;if(counter==0)v(mutex);}editi(){p(mutex);处理文章;v(mutex);}是否正确？30补充题1：读者写者问题。（正解）mutex:用于读者与编辑、编辑与编辑的互斥信号灯，初值为1。mutex1:用于对counter操作的互斥信号灯，初值为1。31补充题1：读者写者问题。（正解）main(){intcounter=0;intmutex=1;intmutex1=1;cobeginreadi();editi();coend}readi(){p(mutex1);counter++;if(counter==1)p(mutex);v(mutex1);读文章;p(mutex1);counter--;if(counter==0)v(mutex);v(mutex1);}editi(){p(mutex);处理文章;v(mutex);}32补充题2：哲学家就餐问题•五个哲学家围坐在一个圆桌周围；•每个哲学家面前都有一盘通心面，相邻两个盘子间有一把叉子。•每个哲学家的行为是思考，感到饥饿，然后吃通心粉；•为了吃通心粉，每个哲学家必须拿到两把叉子，并且每个人只能直接从自己的左边或右边去取叉子；•试用信号灯及P、V操作写出哲学家行为的程序描述，要求不能让某个（或某些哲学家饿死）。33补充题2：哲学家就餐问题34补充题2：哲学家就餐问题intfork[5];/*5把叉子*/fork[0]=fork[1]=fork[2]=fork[3]=fork[4]=1ProcessPi:while(1){think;P(fork[i]);P(fork[i+1mod5]);eat;V(fork[i+1mod5]);V(fork[i]);}35补充题2：哲学家就餐问题intfork[5];/*5把叉子*/fork[0]=fork[1]=fork[2]=fork[3]=fork[4]=1ProcessPi:while(1){think;P(fork[i]);P(fork[i+1mod5]);eat;V(fork[i+1mod5]);V(fork[i]);}问题：五个哲学家同时拿起左这的叉子。产生死锁！36补充题2：哲学家就餐问题解决办法一：最多允许4个哲学家同时坐桌子周围。37补充题2：哲学家就餐问题intfork[5];/*5把叉子*/fork[0]=fork[1]=fork[2]=fork[3]=fork[4]=1intT=4;ProcessPi:while(1){think;P(T);P(fork[i]);P(fork[i+1mod5]);eat;V(fork[i+1mod5]);V(fork[i]);V(T);}38补充题2：哲学家就餐问题解决办法二：哲学家拿左边叉子和右边叉子之间不能被中断。39补充题2：哲学家就餐问题intfork[5];/*5把叉子*/fork[0]=fork[1]=fork[2]=fork[3]=fork[4]=1intmutex=1;ProcessPi:while(1){think;P(mutex);P(fork[i]);P(fork[i+1mod5]);V(mutex);eat;V(fork[i+1mod5]);V(fork[i]);}