第五章-进程管理经典的进程同步问题--副本课件

计算机科学与工程学院计算机科学与工程学院软件工程教研室软件工程教研室操作系统操作系统授课教师：王玲芬授课教师：王玲芬授课教师：王玲芬授课教师：王玲芬Operating System2-4372-437室室进程管理Process management-2-OperatingSystem主要内容主要内容n为什么要引入进程的概念为什么要引入进程的概念 n进程的表示和调度状态进程的表示和调度状态n进程的控制进程的控制n进程调度进程调度n线程及其管理线程及其管理n进程通信进程通信n死锁问题死锁问题-3-OperatingSystem四、经典的进程同步互斥问题四、经典的进程同步互斥问题-4-OperatingSystem1.1.生产者生产者消费者问题消费者问题消费者消费者生产者生产者同步问题：同步问题：生产者进程生产者进程P P不能往不能往“满满”的缓冲区中放的缓冲区中放产品，设置信号量产品，设置信号量SnSn，表示可用缓冲区数，表示可用缓冲区数 消费者进程消费者进程Q Q不能从不能从“空空”的缓冲区中取的缓冲区中取产品，设置信号量产品，设置信号量S0S0表示产品数量表示产品数量Sn初值为初值为1，S0初值为初值为0消耗该产品消耗该产品消耗该产品消耗该产品生产者进程生产者进程生产者进程生产者进程P P消费者进程消费者进程消费者进程消费者进程QQP(Sn)P(Sn)V(Sn)V(Sn)生产一种产品生产一种产品生产一种产品生产一种产品产品送入缓冲区产品送入缓冲区产品送入缓冲区产品送入缓冲区P(S0)P(S0)V(S0)V(S0)从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品Sn初值为初值为1，S0初值为初值为0消耗该产品消耗该产品消耗该产品消耗该产品生产者进程生产者进程生产者进程生产者进程P P消费者进程消费者进程消费者进程消费者进程QQP(Sn)P(Sn)V(Sn)V(Sn)生产一种产品生产一种产品生产一种产品生产一种产品产品送入缓冲区产品送入缓冲区产品送入缓冲区产品送入缓冲区P(S0)P(S0)V(S0)V(S0)从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品Sn初值为初值为n，S0初值为初值为0多个生产者，多个消费者多个生产者，多个消费者-10-OperatingSystem要不要对缓冲区（临界资源）要不要对缓冲区（临界资源）进行互斥操作？进行互斥操作？-11-OperatingSystem-12-OperatingSystem消耗该产品消耗该产品消耗该产品消耗该产品生产者进程生产者进程生产者进程生产者进程PiPi消费者进程消费者进程消费者进程消费者进程QiQiP(Sn)P(Sn)V(Sn)V(Sn)生产一种产品生产一种产品生产一种产品生产一种产品产品送入缓冲区产品送入缓冲区产品送入缓冲区产品送入缓冲区P(S0)P(S0)V(S0)V(S0)从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品Sn初值为初值为n，S0初值为初值为0-13-OperatingSystem 互斥访问缓冲区互斥访问缓冲区-14-OperatingSystem消耗该产品消耗该产品消耗该产品消耗该产品生产者进程生产者进程生产者进程生产者进程PiPi消费者进程消费者进程消费者进程消费者进程QiQiP(Sn)P(Sn)V(Sn)V(Sn)生产一种产品生产一种产品生产一种产品生产一种产品产品送入缓冲区产品送入缓冲区产品送入缓冲区产品送入缓冲区P(S0)P(S0)V(S0)V(S0)从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品S互斥信号量，初值为互斥信号量，初值为1P(S)P(S)V(S)V(S)P(S)P(S)V(S)V(S)Begin B:array0.n-1of integer;P,R:integer;S,Sn,S0:semaphore;P:=R:=0;S:=1;Sn:=n;S0:=0;Cobegin Process producer i(i=1,2,m)begin L1:produce a product;P(Sn);P(S);Bp:=product;p:=(p+1)mod n;V(s0);V(s);goto l1 endProcess consumet j(j=1,2,k)begin L2:P(S0);P(S);take a product form BR;R:=(R+1)mod n;V(sn);V(s);consume goto l2 end;coeng;end;-16-OperatingSystem消耗该产品消耗该产品消耗该产品消耗该产品生产者进程生产者进程生产者进程生产者进程PiPi消费者进程消费者进程消费者进程消费者进程QiQiV(Sn)V(Sn)生产一种产品生产一种产品生产一种产品生产一种产品产品送入缓冲区产品送入缓冲区产品送入缓冲区产品送入缓冲区P(S0)P(S0)V(S0)V(S0)从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品从缓冲区取取一产品S互斥信号量，初值为互斥信号量，初值为1P(S)P(S)V(S)V(S)P(S)P(S)V(S)V(S)P(Sn)P(Sn)用信号量解题的关键用信号量解题的关键n步骤：步骤：信号量的设置信号量的设置；给信号量赋初值给信号量赋初值（常（常用的互斥和同步信号量值的大小）；用的互斥和同步信号量值的大小）；P P、V V操作安操作安排的位置排的位置（其中，（其中，P P的顺序不能颠倒，的顺序不能颠倒，V V的顺序任意）的顺序任意）n注意区分注意区分n1 1）公用信号量公用信号量,互斥时使用的信号量：它联系着一互斥时使用的信号量：它联系着一组共行进程，初值为，每个进程均可对之施加、组共行进程，初值为，每个进程均可对之施加、操作。操作。n2 2）私用信号量：私用信号量：一般信号量一般信号量：它联系着一组共行：它联系着一组共行进程，但其初值为，或为某个正整数，表示资进程，但其初值为，或为某个正整数，表示资源的数目，主要用于进程同步。只允许拥有它的进源的数目，主要用于进程同步。只允许拥有它的进程对之施加操作。程对之施加操作。-18-OperatingSystem用用P、V操作能解决的问题操作能解决的问题n互斥：互斥：信号量初值为信号量初值为1 1n同步：同步：信号量的初值为信号量的初值为0 0n资源分配：资源分配：信号量的初值为信号量的初值为n n-19-OperatingSystem2.2.读者写者问题读者写者问题 有两组并发进程有两组并发进程:读者和写者读者和写者,共享一组数据区共享一组数据区 要求：要求：允许多个读者同时执行读操作允许多个读者同时执行读操作 不允许读者、写者同时操作不允许读者、写者同时操作 不允许多个写者同时操作不允许多个写者同时操作互斥互斥互斥互斥RRW-20-OperatingSystem读者优先读者优先如果读者来：如果读者来：1 1）无读者、写者，新读者可以读）无读者、写者，新读者可以读2 2）有写者等，但有其它读者正在读，则新读者也可以读）有写者等，但有其它读者正在读，则新读者也可以读3 3）有写者写，新读者等）有写者写，新读者等如果写者来：如果写者来：1 1）无读者，新写者可以写）无读者，新写者可以写2 2）有读者，新写者等待）有读者，新写者等待3 3）有其它写者，新写者等待）有其它写者，新写者等待-21-OperatingSystemBeginS,Sr:semaphore;rc:integer;S:=Sr:=1;rc:=0;Cobegin-22-OperatingSystemprocessReaderi(i=1,2,m)beginP(Sr);rc:=rc+1;ifrc=1thenP(S);V(Sr);readfileFP(Sr)rc:=rc-1;ifrc=0thenV(S);V(Sr)endprocessWriterj(j=1,2.k)beginP(S);WritefileFV(S)end初值：初值：S=1,Sr=1,rc=0n如果读者来：如果读者来：n1）无读者、写者，新读者可以读）无读者、写者，新读者可以读n2)有读者读有读者读,新读者也可以读新读者也可以读n2）有写者等，但有其它读者正在读，则）有写者等，但有其它读者正在读，则新读者也可以读新读者也可以读n3）有写者写，新读者等）有写者写，新读者等如果写者来：如果写者来：1 1）无读者，新写者可以写）无读者，新写者可以写2 2）有读者，新写者等待）有读者，新写者等待3 3）有其它写者，新写者等待）有其它写者，新写者等待-23-OperatingSystemprocessReaderi(i=1,2,m)beginP(Sr);rc:=rc+1;ifrc=1thenP(S);V(Sr);readfileFP(Sr)rc:=rc-1;ifrc=0thenV(S);V(Sr)endprocessWriterj(j=1,2.k)beginP(S);WritefileFV(S)end初值：初值：S=1,Sr=1,rc=0n如果读者来：如果读者来：n1）无读者、写者，新读者可以读）无读者、写者，新读者可以读n2)有读者读有读者读,新读者也可以读新读者也可以读n2）有写者等，但有其它读者正在读，则）有写者等，但有其它读者正在读，则新读者也可以读新读者也可以读n3）有写者写，新读者等）有写者写，新读者等如果写者来：如果写者来：1 1）无读者，新写者可以写）无读者，新写者可以写2 2）有读者，新写者等待）有读者，新写者等待3 3）有其它写者，新写者等待）有其它写者，新写者等待读者优先，会造成写者等待很长时间读者优先，会造成写者等待很长时间写者优先？写者优先？写者等，新读者不能读写者等，新读者不能读课后思考题课后思考题-24-OperatingSystem1)信号量的物理含义：信号量的物理含义：S0表示有表示有S个资源可用个资源可用 S=0表示无资源可用表示无资源可用 S0则则|S|表示表示S等待队列中的进程个数等待队列中的进程个数P.V操作讨论操作讨论P(S):表示申请一个资源表示申请一个资源V(S)表示释放一个资源。信号量的初值应该大于等于表示释放一个资源。信号量的初值应该大于等于0 P.V操作必须成对出现，操作必须成对出现，有一个有一个P操作就一定有一个操作就一定有一个V操作操作当为互斥操作时，它们同处于同一进程当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现当为同步操作时，则不在同一进程中出现如果如果P(S1)和和P(S2)两个操作在一起，那么两个操作在一起，那么P操的顺序至关重要操的顺序至关重要,而两个而两个V操作无关操作无关紧要紧要Begin B:array0.n-1of integer;P,R:integer;S,Sn,S0:semaphore;P:=R:=0;S:=1;Sn:=n;S0:=0;Cobegin Process producer i(i=1,2,m)begin L1:produce a product;P(Sn);P(S);Bp:=product;p:=(p+1)mod n;V(s0);V(s);goto l1 endProcess consumet j(j=1,2,k)begin L2:P(S0);P(S);take a product form BR;R:=(R+1)mod n;V(sn);V(s);consume goto l2 end;coeng;end;课后思考题课后思考题-27-OperatingSystem优点：优点：简单，而且表达能力强简单，而且表达能力强（用（用P.V操作可解决任何同步互斥问题）操作可解决任何同步互斥问题）缺点：缺点：不够安全；不够安全；P.V操作使用不当会出现死锁；操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂遇到复杂同步互斥问题时实现复杂P.V操作的优缺点操作的优缺点-28-OperatingSystem五、信号量集五、信号量集1.AND1.AND型信号量集型信号量集 2.2.一般一般“信号量集信号量集”-29-OperatingSystem六、六、引入更高级的工具引入更高级的工具 管程管程n问题关键问题关键:在程序的许多地方都有信号量的操作在程序的许多地方都有信号量的操作n想法想法:将共享数据、互斥将共享数据、互斥(同步同步)操作集中隐藏起操作集中隐藏起来，由辅助工具负责展开来，由辅助工具负责展开 monitor example int counter;void producer(x);void consumer(x);while(true)example.producer(x);while(true)example.consumer(x);编编译译器器将将其其展展开开 while(true)mutex.P();producer函数体函数体;if(?)xx.V();mutex.V();-30-OperatingSystem管程描述管程描述n管程将共享数据、同步互斥等封装起来管程将共享数据、同步互斥等封装起来管程里的数据结构只能通过管管程里的数据结构只能通过管程中的操作访问程中的操作访问初始化初始化共享数据共享数据操作操作一次只允许一个进程调用这一次只允许一个进程调用这些操作些操作(互斥进入互斥进入)条件变量条件变量(condition)关联一关联一个队列，用来实现同步个队列，用来实现同步隐隐式式实实现现互互斥斥条件变量上的操作只有条件变量上的操作只有wait(即即P)和和signal(即即V)隐隐式式实实现现同同步步条件条件x-31-OperatingSystem用管程解决生产者用管程解决生产者 消费者问题消费者问题 monitor ProducerConsumer int counter;condition full,empty;void enter(x)if(counter=N)full.wait();将将x放入缓冲区放入缓冲区;counter+;if(counter=1)empty.signal();item remove()if(counter=0)empty.wait();从缓存区取出从缓存区取出x;counter-;if(counter=N-1)full.signal();void producer()while(true)生产生产x;ProducerConsumer.enter(x);void consumer()while(true)x=ProducerConsumer.remove();-32-OperatingSystem实际操作系统提供哪些同步工具实际操作系统提供哪些同步工具!-33-OperatingSystem5.4 5.4 高级通讯高级通讯n通讯通讯:进程间信息的传递进程间信息的传递低级通讯低级通讯:进程间控制信息的传递进程间控制信息的传递(控制进程的速度控制进程的速度)进程通讯类型（消息缓冲、信箱通讯、共享文件）进程通讯类型（消息缓冲、信箱通讯、共享文件）高级通讯高级通讯:进程间大批量数据的传递进程间大批量数据的传递(效率高效率高)-34-OperatingSystem 一、消息缓冲通信（直接通讯）一、消息缓冲通信（直接通讯）发发送送进进程程在在自自己己的的工工作作区区域域,设设置置发发送送区区,然然后后,调调用用发发送送原原语语将将信信息息发发送送到到消消息息缓缓冲冲区区，接接收收进进程程也也是是先先在在自自己己的的工工作作区区域域准准备备好好接接收收区区,然然后后调调用用接收原语，将消息缓冲区的消息接收到工作区。接收原语，将消息缓冲区的消息接收到工作区。-35-OperatingSystem 2.2.发送和接收原语发送和接收原语Send(receiver,addr)Send(receiver,addr)Receiver(addr)Receiver(addr)发送进程发消息时要指定接收进程的名字，发送进程发消息时要指定接收进程的名字，1.消息缓冲区的数据结构消息缓冲区的数据结构发送者进程标识符：发送者进程标识符：Sender消息长度：消息长度：size消息正文消息正文:text指向下一消息缓冲区的指针：指向下一消息缓冲区的指针：nextSender:ASender:ASIZE:5SIZE:5TEXT:helloTEXT:hello接收者接收者进程进程发送消息发送消息地址地址接收消息接收消息地址地址-36-OperatingSystemn3.PCB中应增数据项中应增数据项：mq 消息队列指针消息队列指针mutex 消息队列互斥信息量消息队列互斥信息量sm消息队列资源信息量（消息消息队列资源信息量（消息数）数）-37-OperatingSystemmqmutexsmsender:Asize:5text:Hellosend(B,a)sender:Asize:5text:hellonext:0发送区发送区sender:Asize:5text:Helloreceive(A，b)接收区接收区ab进程进程APCB(B)进程进程B4.发送与接收过程发送与接收过程-38-OperatingSystem用用P.VP.V操作来实现操作来实现SendSend原语原语:SendSend（B B，a a）P(mmutex);P(mmutex);Begin Begin 把缓冲区挂到接收进程把缓冲区挂到接收进程 根据根据B B找接收进程，找接收进程，的消息链链尾的消息链链尾;如果没找到出错返回如果没找到出错返回;V(mmutex);V(mmutex);申请空缓冲区申请空缓冲区P P（sbsb）；V(smV(sm););P(bmutex);END P(bmutex);END 取空缓冲区取空缓冲区;V(bmutex);V(bmutex);把消息从把消息从a a处处copycopy到空缓冲区到空缓冲区;其中其中sbsb初值初值:n;sm:n;sm初值初值:0:0Receive(b)Receive(b)课堂练习课堂练习-39-OperatingSystem用用P.VP.V操作来实现操作来实现Receive原语原语:Receive(A，b)P(bmutex);P(bmutex);Begin Begin 把空缓冲区挂到空白把空缓冲区挂到空白 P P（smsm）缓冲区链尾缓冲区链尾;V(bmutex);V(bmutex);V(sbV(sb););P(mmutex);END P(mmutex);END 从消息链中取进程从消息链中取进程A A发来的消息发来的消息 内容复制到工作区内容复制到工作区b b V(mmutex);V(mmutex);其中其中sbsb初值初值:n;sm:n;sm初值初值:0:0Receive(A,b)Receive(A,b)课堂练习课堂练习-40-OperatingSystem二、信箱通讯（间接通信）：二、信箱通讯（间接通信）：发送进程发消息时不指定接收进程的名字，而是指定发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信一个中间媒介，即信箱。进程间通过信箱实现通信 发送原语：发送原语：send(MB,Message)send(MB,Message)接收原语：接收原语：receive(MB,Message)receive(MB,Message)信信 箱箱 头头格格子子1格格子子2格格子子3格格子子n进程进程A发送信件发送信件进程进程B接收信件接收信件(1)信箱的数据结构信箱的数据结构boxname:信箱名信箱名boxsize:信箱大小信箱大小mesnum:已存信件数已存信件数fremnum;空的格子数空的格子数 boxname boxsize mesnum fremnum信件信件满满信件信件满满格子格子空空格子格子空空(2)发送与接收原语发送与接收原语n Send(boxname,msg)n Receiver(boxname,msg)SendSend（boxnameboxname，msgmsg）Begin Begin local X;local X;根据根据boxnameboxname找到信箱找到信箱;P P（fremnum);fremnum);选择标志为空的格子；选择标志为空的格子；把消息把消息msgmsg放入空的格子放入空的格子X X中；中；置格子置格子X X为满标志；为满标志；V(mesnum);V(mesnum);end endreceivereceive（bosnamebosname，msgmsg）Begin Begin local X;local X;根据根据boxnameboxname找到信箱找到信箱;P P（mesnum);mesnum);选择标志为满的格子选择标志为满的格子X X；将将X X中的信件取出放入中的信件取出放入megmeg中；中；置格子置格子X X为空标志；为空标志；V(fremnum);V(fremnum);end end-43-OperatingSystem三、管道通信方式三、管道通信方式 Pipe(共享文件）共享文件）也称共享文件方式，基于文件系统，利用一个打开的共也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输享文件连接两个相互通信的进程，文件作为缓冲传输介质介质发送进程发送进程接收进程接收进程字符流方式写入读出字符流方式写入读出先进先出顺序先进先出顺序有关的系统功能调用：有关的系统功能调用：pipe(fd)fd:intfd2其中其中:fd0、fd1文件描述符（读、写）文件描述符（读、写）write(fd,buf,byte)、read(fd,buf,byte)fd:文件描述符文件描述符buf:信息传送的源（目标）地址信息传送的源（目标）地址byte:传送的字节数传送的字节数lockf(fd,function,byte)fd:文件描述符文件描述符function:1:锁定锁定0:解锁解锁byte:锁定的字节数锁定的字节数，0:从当前位置到文件尾从当前位置到文件尾sleep:调用进程进入睡眠状态调用进程进入睡眠状态(封锁封锁),直到被唤醒直到被唤醒.exit(status)进程自我终止进程自我终止wait(stat-loc):阻塞调用进程阻塞调用进程控制父进程与子进程的同步。当子进程结束时，系统控制父进程与子进程的同步。当子进程结束时，系统会向父进程发出信号。父进程返回继续执行原来的程会向父进程发出信号。父进程返回继续执行原来的程序。序。例例1：用用C语语言言编编写写一一个个程程序序，建建立立一一个个pipe，同同时时父父进进程程生生成成一一个个子子进进程程，子子进进程程向向pipe中中写写入入一一字字符符串串,父父进进程程从从pipe中中读出该字符串读出该字符串#includemain()intx,fd2;charbuf30,s30;pipe(fd);while(x=fork()=-1);if(x=0)/子进程代码子进程代码sprintf(buf,Thisisanexamplen);write(fd1,buf,30);exit(0);elsewait(0);/父进程代码父进程代码read(fd0,s,30);printf(%s,s);结果结果:ThisisanexampleThisisanexampleThisisanexamplebufwrite(fd1sThisisanexampleread(fd0,写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits47谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal