第4章进程及进程管理3

1、2021-11-2914.4 进程之间的约束关系进程之间的约束关系问题的提出问题的提出为了解决多道程序并发执行时产生的与时间有关的错误，协调并发进程间的正常运行，需先分析进程间的各种可能的约束关系。4.4.1 进程的竞争与合作进程的竞争与合作进程间相互制约关系分两种：v1、竞争系统资源：处理机的竞争，内存页面的竞争，进程向系统申请，由系统统一分配。v2、进程协作：进程间通过同步机构自行协调。信息共享，并行处理。2021-11-2934.4.2 进程互斥的概念进程互斥的概念两个概念：临界资源临界资源与临界区临界区。1临界资源临界资源临界资源临界资源指的是一次只允许一个进程使用的独占资源。诸进程对

2、它的访问必须互斥。（包括可能的系统资源及用户资源）2 2临界区临界区临界区临界区是指包含了访问临界资源的那段程序。临界区作为特殊的程序段进行如下处理：1）进程在进入临界区之前必须先申请，2）当且仅当临界区中涉及的临界资源没有其它进程使用时才能进入临界区；3）在出临界区后立即释放临界资源。2021-11-2944.4.2 进程互斥的概念进程互斥的概念互斥必要条件：互斥必要条件：诸进程共享同一个临界资源诸进程共享同一个临界资源；共享的方式是先来者先使用的异步方式共享的方式是先来者先使用的异步方式。只有同时满足以上两个必要条件的多进程共享临界资源的问题，才是互斥问题。操作系统提供的互斥机制必须满足以

3、下要求：操作系统提供的互斥机制必须满足以下要求：(临界区问题的解答必须满足的要求临界区问题的解答必须满足的要求)1实现互斥：即任意时刻最多只能有一个进程进入临界区，执行临界区的进程不能受到其它进程的干扰。2有空让进：当临界资源空闲时，应该允许申请进入临界区的进程进入临界区。3有限等待：对要求进入临界区的进程，应在有限时间内进入，以免陷入“死等“；进入临界区的进程不能被无限期地延迟或死锁2021-11-2954.4.3 进程进程同步的概念同步的概念同步问题：同步问题：当各进程的执行具有一定先后顺序的限制时，称为当各进程的执行具有一定先后顺序的限制时，称为同步问题同步问题。同步与互斥的比较：同步与

4、互斥的比较：是否一定共享临界资是否一定共享临界资源源运行方式运行方式互斥问题互斥问题一定一定异步：先来者先进入，无先后异步：先来者先进入，无先后顺序，异步顺序，异步同步问题同步问题不一定不一定同步：有先后顺序同步：有先后顺序同步互斥混合问题同步互斥混合问题一定一定进入临界区异步执行、进程间进入临界区异步执行、进程间同步同步2021-11-2964.4.3 进程进程同步的概念同步的概念u解决同步问题的信号量为解决同步问题的信号量为私有信号量私有信号量，局限于需要同步的协，局限于需要同步的协作进程之间使用。作进程之间使用。u协作进程之间的关联属于协作进程之间的关联属于直接关联直接关联。u互斥可以看

5、成是同步的一种特殊情况，互斥可以看成是同步的一种特殊情况，广义上的同步广义上的同步包含了包含了互斥在内，我们将两者统称为进程的同步问题。广义上的同互斥在内，我们将两者统称为进程的同步问题。广义上的同步可以定义为诸进程之间步可以定义为诸进程之间在执行时间上所加的某种约束在执行时间上所加的某种约束，如，如果这种约束是因为共享临界资源，而且约束的方式是异步的果这种约束是因为共享临界资源，而且约束的方式是异步的则为互斥约束；否则就是同步约束。则为互斥约束；否则就是同步约束。2021-11-2974.4.3 进程进程同步的概念同步的概念协作进程之间一般有以下几种不同的同步问题：协作进程之间一般有以下几种

6、不同的同步问题：前驱与后继同步问题前驱与后继同步问题单缓冲与多缓冲读写同步问题单缓冲与多缓冲读写同步问题生产者消费者同步问题生产者消费者同步问题2021-11-2984.5.1 锁和上锁、开锁操作锁和上锁、开锁操作解决互斥的最简单方法：解决互斥的最简单方法：为临界区设置锁位为临界区设置锁位。4.5 同步机构同步机构2021-11-2994.5.1 锁和上锁、开锁操作锁和上锁、开锁操作上锁原语上锁原语算法lock输入：锁变量输入：锁变量w输出：无输出：无/*检测锁位为检测锁位为0吗？不为吗？不为0继续检测继续检测*/while(w=1);w=1;/进入临界区前先上锁进入临界区前先上锁开锁原语开锁

7、原语算法 unlock输入：锁变量输入：锁变量w输出：无输出：无w=0; /开锁开锁该方法的缺点：可能产生进程的忙等待！该方法的缺点：可能产生进程的忙等待！CPU效率下降！效率下降！改进办法？改进办法？2021-11-29104.5.2 信号灯及其信号灯及其P、V操作操作v信号量（信号灯）信号量是一种数据结构信号量的一般构成（s和q）信号量s值的含义v信号量机制使用信号量实现进程间的同步和互斥的机制，是操作系统提供的一种进程通信方式。2021-11-29114.5.2 信号量及其信号量及其P、V操作操作v信号量总结：信号量总结：信号量的值与相应资源的使用情况有关信号量的值与相应资源的使用情况有

8、关信号量的初值设定信号量的初值设定信号量的值仅由信号量的值仅由P、V操作来改变操作来改变vPV操作操作用来申请或释放信号量的操作，由系统提供的系统调用完成用来申请或释放信号量的操作，由系统提供的系统调用完成: P操作表示申请资源；操作表示申请资源； V操作表示释放资源。操作表示释放资源。P、V操作用原语实现，不允许中断。操作用原语实现，不允许中断。2021-11-29124.5.2 信号量及其信号量及其P、V操作操作/*P操作原语操作原语请求资源或条件请求资源或条件*/P（s）s；if（s0）保留调用进程的保留调用进程的CPU现场；现场； 将该进程插入将该进程插入s的等待队列；的等待队列；置该

9、进程为等待态置该进程为等待态;转进程调度转进程调度;2021-11-29134.5.2 信号量及其信号量及其P、V操作操作/*V操作原语操作原语释放资源或条件释放资源或条件*/V（s）s；if (s0) 移出移出s等待队列中的第一个进等待队列中的第一个进程；程； 将该进程插入就绪队列；将该进程插入就绪队列； 置该进程为就绪态置该进程为就绪态;2021-11-29144.6 进程互斥与同步的实现进程互斥与同步的实现4.6 .1上锁原语和开锁原语实现进程互斥上锁原语和开锁原语实现进程互斥 上锁上锁 临界区临界区csb 开锁开锁进程进程B 上锁上锁 临界区临界区csa 开锁开锁进程进程A2021-1

10、1-29154.6 进程互斥与同步的实现进程互斥与同步的实现4.6 .1上锁原语和开锁原语实现进程互斥上锁原语和开锁原语实现进程互斥main()int w=0;cobeginppa();ppb();coendppa()lock(w)csa;unlock(w)ppb()lock(w)csb;unlock(w)2021-11-29164.6.2 用信号灯实现进程互斥用信号灯实现进程互斥假设有假设有多种多种临界资源提供给多个进程共享，对其实现互斥使用临界资源提供给多个进程共享，对其实现互斥使用的方法为：的方法为：针对针对每一类临界资源每一类临界资源设一个互斥信号量设一个互斥信号量mutexi，若某类

11、临，若某类临界资源有界资源有n个，初值为个，初值为n；如果只有一个或者抽象表示只能；如果只有一个或者抽象表示只能一个进程进入，则初值设为一个进程进入，则初值设为1。在每个进程中对涉及临界资源在每个进程中对涉及临界资源i的临界区做如下处理的临界区做如下处理 P（mutexi）；）； 临界区；临界区；V (mutexi)；2021-11-29174.6.2 用信号灯实现进程互斥用信号灯实现进程互斥步骤：步骤：寻找共享的临界寻找共享的临界资源；资源；判定临界区；判定临界区；设置信号量及其设置信号量及其初值；初值；使用使用mutex的的P、V操作将临界区操作将临界区括起来。括起来。2021-11-29

12、184.6.2 用信号灯实现进程互斥用信号灯实现进程互斥 对于飞机订票系统的例子，可以采用下列方法解决对于飞机订票系统的例子，可以采用下列方法解决“与时间有关的错误与时间有关的错误”：针对临界资源机票库设置一个信号量针对临界资源机票库设置一个信号量mutex，初值为，初值为1。每个终端进程中的程序。每个终端进程中的程序描述如下：描述如下：P（mutex）；）；在机票数据库中取出当前剩余票数在机票数据库中取出当前剩余票数X；判断判断X0（有票吗）？（有票吗）？如果有，如果有， XN（票够吗）？（票够吗）？如果够，则出票（打印票据）；如果够，则出票（打印票据）；XXN（修改剩余票数）；（修改剩余票

13、数）；将将X回写到数据库中；回写到数据库中；V（mutex）；）；如果终端如果终端A先来，对先来，对mutex进行进行P操作后，进入临界区，此时操作后，进入临界区，此时mutex为为0。当它还没。当它还没有处理完毕时，其它任何终端到来都因其执行有处理完毕时，其它任何终端到来都因其执行P(mutex)后被阻塞，直到终端后被阻塞，直到终端A执行了执行了V(mutex)后将它们唤醒后才能进入其临界区对后将它们唤醒后才能进入其临界区对x进行操作，从而保证了只进行操作，从而保证了只有一个进程进入临界区，避免了有一个进程进入临界区，避免了“与时间有关的错误与时间有关的错误” 的发生。的发生。2021-11

14、-29194.6.2 用信号灯实现进程互斥用信号灯实现进程互斥如果有如果有n个终端，则个终端，则mutex信号量的取值范围为：信号量的取值范围为： （n1）mutex1其物理含义为：其物理含义为：当机票库空闲时，当机票库空闲时，mutex=1。当有一个终端进入，对机票进行处理，其它终端进程还没有当有一个终端进入，对机票进行处理，其它终端进程还没有到来时，到来时，mutex=0。当所有终端进程都到来，且有一个正在对机票进行处理时，当所有终端进程都到来，且有一个正在对机票进行处理时，mutex=（n1）。它表示有）。它表示有n1个进程在等待队列上等个进程在等待队列上等待。待。2021-11-292

15、04.6.2 进程同步的实现进程同步的实现用用P、V操作实现进程同步的算法可以简单归纳如下：操作实现进程同步的算法可以简单归纳如下：设置信号量设置信号量分析每个进程的分析每个进程的执行条件和释放条件执行条件和释放条件，针对每个执行条件针对每个执行条件设置一个信号设置一个信号量，其初值根据初始情况确定；量，其初值根据初始情况确定；对每个进程的处理：对每个进程的处理：u在请求条件处执行在请求条件处执行P（执行条件信号量）；（执行条件信号量）；u在释放条件处执行在释放条件处执行V（释放条件信号量）。（释放条件信号量）。解决同步问题与互斥问题的区别解决同步问题与互斥问题的区别：互斥问题互斥问题中各进程

16、涉及共同的临界资源，因此每个进程中涉及同一个临中各进程涉及共同的临界资源，因此每个进程中涉及同一个临界资源的临界区中界资源的临界区中所执行的所执行的P、V操作的信号量是相同的操作的信号量是相同的；同步问题同步问题中每个进程由于执行条件和释放条件的不同因而其中每个进程由于执行条件和释放条件的不同因而其P、V操作涉操作涉及的信号量不同及的信号量不同。2021-11-2921例如：设有例如：设有4个进程，其执行的先后流图如下图所示。用个进程，其执行的先后流图如下图所示。用P、V操作实现操作实现其同步。其同步。P 1P 4P 3P 2前驱与后继同步问题前驱与后继同步问题进程进程Pj有 无 前 驱有 无

17、 前 驱（执行条件）（执行条件）请求信号量请求信号量信号量初值信号量初值有无后继有无后继（释放条件）（释放条件）释放信号量释放信号量P1无无无无无无P2、P3S12、S13P2P1结束结束S120P4S24P3P1结束结束S130P4S34P4P2、P3结束结束S24、S340无无无无同步分析：2021-11-2922算法描述算法描述：main()int s12 = s13 = s24 = s34 = 0;cobeginp1(); p2(); p3(); p4();coendp1()执行执行P1自己的程序自己的程序;/无前驱，所以无无前驱，所以无P操作操作V(s12);/有后继有后继P2，释放

18、条件，释放条件s12V(s13);/有后继有后继P3，释放条件，释放条件s13p2()P(s12);/有前驱有前驱P1，申请条件，申请条件s12执行执行P2自己的程序自己的程序;V(s24); /有后继有后继P4，释放条件，释放条件s24p3( )P(s13);/有前驱有前驱P1，申请条件，申请条件s13执行执行P3自己的程序自己的程序;V(s34);/有后继有后继P4，释放条件，释放条件s34p4( )P(s24);/有前驱有前驱P2，申请条件，申请条件s24P(s34);/有前驱有前驱P3，申请条件，申请条件s34执行执行P4自己的程序自己的程序; /无后继，所以无无后继，所以无V操作操作

19、这样，无论哪个进程先来，只要不是这样，无论哪个进程先来，只要不是p1p1进程，都会在执行了相应的进程，都会在执行了相应的P P操作后，操作后，因为执行条件不成立而被挂到相应因为执行条件不成立而被挂到相应信号量的等待队列上，等待其前驱信号量的等待队列上，等待其前驱执行该信号量的执行该信号量的V V操作后将其唤醒，操作后将其唤醒，从而保证这些进程并发执行时其执从而保证这些进程并发执行时其执行的时序遵循给定的同步关系行的时序遵循给定的同步关系。2021-11-2923生产者消费者问题生产者消费者问题一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享多个缓冲区多个生产者、多个消费者共享多个

20、缓冲区多个生产者、多个消费者共享一个缓冲区多个生产者、一个消费者共享多个缓冲区一个生产者、多个消费者共享多个缓冲区2021-11-2924一个生产者、一个消费者共享一个缓冲区（同步问题）一个生产者、一个消费者共享一个缓冲区（同步问题）v同步分析进程进程执行条件与信号量执行条件与信号量初值初值释放条件与信号释放条件与信号量量生产者生产者缓冲区有空，缓冲区有空，empty1 1缓冲区有产品，缓冲区有产品，fullfull消费者消费者缓冲区有产品，缓冲区有产品，fullfull0 0缓冲区有缓冲区有空空,empty,empty2021-11-2925算法描述：算法描述：main()int empty

21、=1; /设置信号量及初值设置信号量及初值int full=0;cobeginproducer( ); cosumer( );coendproducer( )while(生产未完成生产未完成) 生产出产品生产出产品;P(empty); /申请条件申请条件empty将该产品送到缓冲区；将该产品送到缓冲区；V(full); /释放条件释放条件full cosumer( )while(输出未完成输出未完成) P(full); /申请条件申请条件full从缓冲区中获取产品从缓冲区中获取产品;V(empty); /释放条件释放条件empty 一个生产者、一个消费者共享一个缓冲区（同步问题）一个生产者、一

22、个消费者共享一个缓冲区（同步问题）2021-11-2926多个生产者、多个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区（同步互斥共存）（同步互斥共存）v互斥分析设互斥信号量mutex，初值为1，表示一次只能进一个生产者或消费者进程。v同步分析(设有n个缓冲区)生产者进程消费者进程多缓冲区进程进程执行条件与信号量执行条件与信号量初值初值释放条件与信号释放条件与信号量量第第i i个生产个生产者者缓冲区有空，缓冲区有空，emptyn n缓冲区有产品，缓冲区有产品，fullfull第第j j个消费个消费者者缓冲区有产品，缓冲区有产品，fullfull0 0缓冲区有缓冲区有空空,empty,

23、empty2021-11-2927算法描述：算法描述：main() /*定义信号量及其初值定义信号量及其初值*/int full=0;int empty=n;int mutex=1;cobegin produceri(); consumerj();coend/*某个生产者进程某个生产者进程i*/produceri() while(生产未完成生产未完成)生产一个产品；生产一个产品； P(empty);/请求缓请求缓冲区有空条件冲区有空条件 P(mutex); /请求进请求进入临界区入临界区 送一个产品到缓冲区；送一个产品到缓冲区；/临界区临界区 V(mutex); /释放临释放临界区界区 V(f

24、ull);/释放缓释放缓冲区有数条件冲区有数条件/*某个消费者进程某个消费者进程j*/cosumerj() while(还要继续消费还要继续消费)P(full); /请求缓冲区有数请求缓冲区有数条件条件 P(mutex); /请求请求进入临界区进入临界区 从缓冲区中取一个产从缓冲区中取一个产品；品；/临界区临界区 V(mutex); /释放释放临界区临界区 V(empty); /释放释放缓冲区有空条件缓冲区有空条件 消费产品；消费产品；多个生产者、多个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区（同步互斥共存）（同步互斥共存）2021-11-2928苹果桔子问题（同步问题） 桌上有

25、一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果(apple)(apple)，妈妈专向盘子中放桔于，妈妈专向盘子中放桔于(orange)(orange)，一个儿子专等吃盘子中，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。的桔子，一个女儿专等吃盘子里的苹果。 同步分析：（设盘子可装n个水果）进程进程执行条件与信号量执行条件与信号量初值初值释放条件与信号量释放条件与信号量fatherfather盘子里可以放水果，盘子里可以放水果，spn n盘子中有苹果，盘子中有苹果，samothermother盘子里可以放水果，盘子里可以放

26、水果，spn n盘子中有桔子盘子中有桔子, ,sosonson盘子中有桔子，盘子中有桔子， so0 0盘子中可以放水果，盘子中可以放水果，spspdaughterdaughter盘子中有苹果，盘子中有苹果， sa0 0盘子中可以放水果，盘子中可以放水果，sp2021-11-2929算法描述：算法描述：main() /*定义信号量及其初值定义信号量及其初值*/int sp=n； /* 盘子里可以放盘子里可以放n个水果个水果 */int so=0; /* 盘子里有桔子盘子里有桔子,初始无桔子初始无桔子 */int sa=0; /* 盘子里有苹果盘子里有苹果,初始无苹果初始无苹果 */cobegin

27、 father();mother()； son();daughter(); coendfather() L1:削一个苹果；削一个苹果；P(sp); 把苹果放入盘子；把苹果放入盘子；V(sa);goto L1;mother()L2:剥一个桔子；剥一个桔子；P(sp); 把桔子放入盘子；把桔子放入盘子；V(so);goto L2;son() L3:P(so); 从从盘子盘子中取桔子；中取桔子；V(sp); 吃桔子；吃桔子；goto L3;daughter() L4:P(sa); 从从盘子盘子中取苹果；中取苹果；V(sp); 吃苹果；吃苹果；goto L4;苹果桔子问题（同步问题）2021-11-2

28、930理发师问题（同步互斥共存）理发师问题（同步互斥共存）v理发店里有一位理发师、一把理发椅和理发店里有一位理发师、一把理发椅和n n把供等候理发的顾客坐的椅子把供等候理发的顾客坐的椅子v如果没有顾客，理发师便在理发椅上睡觉如果没有顾客，理发师便在理发椅上睡觉v一个顾客到来时，它必须叫醒理发师一个顾客到来时，它必须叫醒理发师v如果理发师正在理发时又有顾客来到，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则如果有空椅子可坐，就坐下来等待，否则就离开则就离开互斥分析：互斥分析：对临界资源对临界资源“剩余的椅子数剩余的椅子数”必须采用互斥必须采用互斥, ,互斥信号量为互斥信

29、号量为mutexmutex。同步分析：同步分析：进程进程执行条件与信号量执行条件与信号量初值初值释放条件与信号量释放条件与信号量barberbarber有顾客需要理发，有顾客需要理发，customerscustomers0 0理发师空闲，理发师空闲，barbersbarberscustomercustomer理发师空闲，理发师空闲，barbersbarbers1 1（有顾客需要理发（有顾客需要理发, , customerscustomers）2021-11-2931算法描述：算法描述：main()int chairs=n;/*以下为信号量以下为信号量*/int mutex;int customers=0;/*等待服务的顾等待服务的顾客数客数*/int barbers