电子科技大学《计算机操作系统》第2章并发与进程-同步

计算机操作系统,电子科技大学计算机科学与工程学院,李玉军,主要内容,2.6进程并发控制:互斥与同步,日常生活现象过十字路口理发店理发银行取钱足球比赛为什么需要“规则和秩序”？个体自主性异步（车辆，行人，顾客）资源稀缺性独占（十字路口，理发师，ATM）任务需合作协作（进球）,2.6进程并发控制:互斥与同步,多道程序设计为什么需要同步？进程是计算机中的独立个体，且具有异步性、并发性资源是计算机中的稀缺个体，需共享，如CPU、内存、I/O设备进程之间可能需要协作完成任务进程同步的主要任务使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。,2.6.1并发控制,并发控制示例1两个用户分别采用存折和储蓄卡对同一帐户（余额为5000元）同时办理两笔存款业务，分别存入1000元和2000元。从系统的角度看，有两个进程将同时对储户余额等数据进行修改。储户余额可能是6000元、7000元或8000元。原因：两个进程同时修改同一数据，而没有进行有效控制。正确的方法：对两个进程进行控制，一次仅允许一个进程全部完成读数据、修改数据、写数据事件以后，才允许别的进程对同一数据的读、修改和写操作。,2.6.1并发控制,并发控制示例2系统中有两个进程P1、P2和P3，共享一个缓冲区，P1和P2负责向缓冲区中写数据，P3负责取出缓冲区中的数据。某时刻，P1和P2都准备将数据送往缓冲区，考虑可能出现的情况。若计算进程P1、P2的推进速度远远低于P3进程的推进速度，考虑可能出现的情况，反之呢？,2.6.1并发控制竞争资源,进程间的制约关系间接制约资源共享互斥直接制约进程合作同步临界资源（CriticalResouce）必须互斥使用的资源为临界资源。,2.6.1并发控制竞争资源,临界区（criticalsection）访问临界资源的那段代码称为临界区。,2.6.1并发控制竞争资源,竞争临界资源引起的问题忙等、饥饿和死锁,忙等,死锁,饥饿,效率公平,2.6.1并发控制竞争资源,临界区使用原则（互斥条件）,2.6.2互斥与同步的解决策略,2.6.2互斥与同步的解决策略,软件方法由进程通过执行相应的程序指令，实现与其他进程的互斥与同步。难以实现且开销大。硬件方法通过屏蔽中断（单CPU）或采用专门的机器指令控制互斥与同步。硬件约束条件强且可能导致进程饥饿与死锁现象。操作系统或专门的程序设计语言提供的特别支持信号量方法已成为通用方法管程方法消息传递方法,2.6.3软件方法,软件方法在进入区设置和检查一些标志来标明是否有进程在临界区。若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。初步设想轮换使用临界区,备注：严格轮换，实现了互斥访问。即使在临界区外失败也会影响另进程的执行。违反了“空闲让进”原则。忙等。,2.6.3软件方法,第一次改进设置临界区状态标志,备注：忙等违反了“忙则等待”原则，互斥访问未实现,2.6.3软件方法,第一次改进设置临界区状态标志（续）,Ifflag1=false,while(flag1);,Ifflag0=false,while(flag0);,flag0=true;,flag1=true;,2.6.3软件方法,第二次改进预先表明进入临界区的态度,备注：实现了互斥访问。违反了“空闲让进”原则，可能导致死锁。,2.6.3软件方法,第二次改进预先表明进入临界区的态度（续）,flag0=true;,flag1=true;,while(flag1);,while(flag0);,2.6.3软件方法,第三次改进预先表明进入临界区的态度+谦让,备注：实现了互斥访问非死锁，但可能长时间僵持,2.6.3软件方法第三次改进（续）,flag0=true,flag1=true,whileflag1,whileflag0,flag0=false延迟一段时间,flag1=false延迟一段时间,flag0=true,flag1=true,2.6.3软件方法Dekker互斥算法,给定序号避免“过分谦让”,2.6.3软件方法Dekker互斥算法（续）,2.6.3软件方法Peterson互斥算法,软件方法特点软件方法始终不能解决“忙等”现象，降低系统效率。采用软件方法实现进程互斥使用临界资源是很困难的，它们通常能实现两个进程的互斥，很难控制多个进程的互斥。算法设计需要非常小心，否则可能出现死锁，或互斥失败等严重问题。,2.6.3软件方法,2.6.4硬件方法,2.6.4硬件方法屏蔽中断,屏蔽中断：避免进程切换，实现互斥访问。屏蔽中断的缺点系统无法响应外部请求无法接受异常，处理系统故障无法切换进程性能下降不支持多处理机,while(true)disableinterrupt/屏蔽中断criticalsection/临界区enableinterrupt/启用中断remainder/其余部分,2.6.4硬件方法专用机器指令,专用机器指令在多处理器环境中，几个处理器共享访问公共主存；处理器表现出一种对等关系，不存在主从关系；处理器之间没有支持互斥的中断机制；处理器的设计者提出了一些机器指令，用于保证两个动作的原子性如在一个周期中对一个存储器单元的读和写；这些动作在一个指令周期中执行，不会被打断，不会受到其他指令的干扰。,2.6.4硬件方法TestandSet,测试某个变量的值，如果满足条件，则置位X86:TEST,1:functiontestset(vari:integer):boolean;2:begin3:ifi=0then4:begin5:i:=1;6:testset:=true;7:end8:elsetestset:=false;9:end,2.6.4硬件方法TestandSet（续）,1:programmutualexclusion;2:constn.;*进程数*3:varbolt:integer；4:procedureP(i:integer)；5:begin6:repeat7:repeatdono-opuntiltestset(bolt);*当bolt为0时，进入临界区*8:;9:bolt:=0;10:;11:forever12:end;13:begin*mainprogram*14:bolt:=0;15:parbegin16:P(1);P(2);.P(n);17:parend18:end,示例,2.6.4硬件方法Exchange,原子性地交换寄存器和内存的值X86:XCHG,1:procedureexchange(varr:register;varm:memory);2:vartemp;3:begin4:temp:=m;5:m:=r;6:r:=temp;7:end,2.6.4硬件方法Exchange（续）,1:programmutualexclusion；2:constn=.;*numberofprocesses*3:varbolt:integer;4:procedureP(i:integer);5:varkey:integer;6:begin7:repeat8:key:=1;9:repeatexchange(key,bolt)untilkey=0;10:;11:exchange(key，bolt);12:;13:forever14:end;15:begin*mainprogram*16:bolt:=0;17:parbegin18:P(1);P(2);.P(n);19:parend20:end,示例,2.6.4硬件方法,?,2.6.5信号量方法,交通信号灯：红灯停，绿灯行,2.6.5信号量方法,信号量实现进程互斥的基本原理两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行（阻塞等待），直到它收到一个可以“向前推进”的信号（被唤醒）。将实现信号灯作用的变量称为信号量，常定义为记录型变量s，其中一个域为整型，另一个域为队列，其元素为等待该信号量的阻塞进程（通常为FIFO）。,2.6.5信号量方法,信号量定义,typesemaphore=recordcount:integer;queue:listofprocessend;vars:semaphore;,2.6.5信号量方法,信号量的两个原子操作：wait(s)和signal(s)，有时也称作P(s)和V(s)。,vars:semaphore;wait(s):s.count:=s.count1;ifs.count0thenbegin进程阻塞；进程进入s.queue队列；end;,vars:semaphore;signal(s):s.count:=s.count+1;ifs.count=0thenbegin唤醒队首进程；将进程从s.queue阻塞队列中移出；end;,2.6.5信号量方法,信号量的物理意义s.count0表示目前临界资源的可用数量，即还可执行wait(s)而不会阻塞的进程数。每执行一次wait(s)操作，意味着请求分配一个单位的资源。s.count0表示已无可用的临界资源，请求该资源的进程被阻塞。此时，s.count的绝对值等于该信号量阻塞队列中的等待进程数。执行一次signal操作，就意味着释放一个单位的资源。若s.count0，表示s.queue队列中还有被阻塞的进程，需要唤醒该队列中的第一个进程，将它转移到就绪队列中。,2.6.5信号量方法,wait、signal的应用进程进入临界区之前，首先执行wait(s)原语，若s.count0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区的某一空单元中；P2每次用getodd()从该缓冲区取出一个奇数并用countodd统计奇数个数；P3每次用geteven()从缓冲区取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。,2.7生产者/消费者问题,生产者/消费者问题示例分析缓冲区是一互斥资源，故设置互斥信号量mutexP1、P2因为奇数的放置与取用而同步，设置同步信号量odd；P1、P3因为偶数的放置与取用而同步，设置同步信号量even；P1、P2、P3因为共享缓冲区，设置同步信号量empty。,2.7生产者/消费者问题,semaphoremutex=1;/缓冲区操作互斥信号量semaphoreodd=0,even=0;/奇数、偶数进程的同步信号量semaphoreempty=N;/空缓冲区单元个数信号量P1()while(true)number=produce();P(empty);/递减空缓冲区的单元个数P(mutex);/互斥访问缓冲区put();V(mutex);/恢复访问缓冲区if(number%2=0)/为偶数V(even);/允许取偶数else/为奇数V(odd);/允许取奇数,2.7生产者/消费者问题,P2()while(true)P(odd);/互斥取奇数P(mutex);/互斥访问缓冲区getodd();V(mutex);/恢复访问缓冲区V(empty);/递增空缓冲区的单元个数countodd();,2.7生产者/消费者问题,P3()while(true)P(even);/互斥取偶数P(mutex);/互斥访问缓冲区geteven();V(mutex);/恢复访问缓冲区V(empty);/递增空缓冲区的单元个数counteven();main()/*主程序*/cobeginP1();P2();P3();coend,2.8读者和写者问题,问题描述多个进程访问一个共享数据区为数据库、文件、内存区及一组寄存器等的数据访问问题建立了一个通用模型。其中若干读进程只能读数据，若干写进程只能写数据。示例联网售票系统、12306在该系统中，数据的查询和更新非常频繁，不可避免会出现多个进程试图查询或修改（读/写）其中某一条数据的情形。,2.8读者和写者问题,读者/写者进程满足的条件允许多个读者进程可以同时读数据；不允许多个写者进程同时写数据，即只能互斥写数据；若有写者进程正在写数据，则不允许读者进程读数据互斥读写。,2.8读者和写者问题,如何控制读者和写者？采用生产者/消费者问题解决方法严格互斥任何读者和写者进程，可以保证数据更新操作的正确性。允许同时读，但不允许同时写、读写。,2.8读者和写者问题,读者和写者问题描述图,2.8读者和写者问题,读者和写者问题解决策略,2.8读者和写者问题,读者优先一旦有读者正在读数据，则允许随后的读者进入读数据。只有当全部读者退出，才允许写者进入写数据。导致写者饥饿读者优先的变量设置wsem：互斥信号量，用于Writers互斥Writers和Readers，以及第一个Reader互斥Writersreadcount：统计同时读数据的Readers个数mutex：对变量readcount互斥算术操作,voidreader()while(1)P(mutex);readcount+;if(readcount=1)P(wsem);V(mutex);READ;P(mutex);readcount-;if(readcount=0)V(wsem);V(mutex);,2.8读者和写者问题,voidwriter()while(1)P(wsem);WRITE;V(wsem);,intreadcount=0；semaphoremutex=1,wsem=1;,序列：RRRWWWRWRRWRWRRWWRWRRW,writer饥饿,2.8读者和写者问题,公平优先写过程中，若其它读者、写者到来，则按到达顺序处理。公平优先的变量设置wsem：互斥信号量，用于Writers互斥Writers和Readers，以及第一个Reader互斥Writersreadcount：统计同时读数据的Readers个数mrc：对变量readcount互斥算术操作wrsem：互斥信号量，确定Writer、Reader请求顺序,2.8读者和写者问题,intreadcount=0,semaphoremrc=l,wrsem=1,wsem=l;,voidreader()while(true)P(wrsem);P(mrc);readercount+;if(readercount=1)P(wsem);V(mrc);V(wrsem);READ;P(mrc);readercount-;if(readercount=0)V(wsem);V(mrc);,voidwriter()while(true)P(wrsem);P(wsem);WRITE;V(wsem);V(wrsem);,序列：R,R,R,W,R,R,R,W,R,2.8读者和写者问题,写者优先只要有一个写者申请写数据，则不再允许新的读者进入读数据。解决了写者饥饿问题，但降低了并发程度，系统的并发性能较差。写者优先的变量设置rsem：互斥信号量，当至少有一个写者申请写数据时互斥新的读者进入读数据writecount：用于控制rsem信号量mwc：对变量writecount互斥算术操作,2.8读者和写者问题,intreadcount=0,writecount=0;semaphoremrc=l,mwc=1,wsem=1,rsem=l;,voidreader()while(1)P(rsem);P(mrc);readcount+;if(readcount=1)P(wsem);V(mrc);V(rsem)；READ;P(mrc);readcount-;if(readcount=0)V(wsem);V(mrc);,voidwriter()while(1)P(mwc);writecount+;if(writecount=1)P(rsem);V(mwc);P(wsem);WRITE;V(wsem);P(mwc);writecount-;if(writecount=0)V(rsem);V(mwc);,序列：,WRRW,WRR,RRRRRW,1.RRWR,2.8读者和写者问题,intreadcount=0,writecount=0;semaphoremrc=l,mwc=1,z=1,wsem=1,rsem=l;,voidreader()while(1)P(z);P(rsem);P(mrc);readcount+;if(readcount=1)P(wsem);V(mrc);V(rsem)；V(z);READ;P(mrc);readcount-;if(readcount=0)V(wsem);V(mrc);,voidwriter()while(1)P(mwc);writecount+;if(writecount=1)P(rsem);V(mwc);P(wsem);WRITE;V(wsem);P(mwc);writecount-;if(writecount=0)V(rsem);V(mwc);,RRRRRW,2.8读者和写者问题,写者优先的思考教材中描述“z信号量的好处是：限制了rsem阻塞队列的长度”，“无法唤醒全部阻塞读者”P(z)和P(rsem)能否互换位置？,理发店有一位理发师、一把理发椅和5把供等候理发的顾客坐的椅子。如果没有顾客，则理发师睡觉。当一个顾客到来时，他必须叫醒理发师，如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等。如果没有空椅子，他就离开。,补充理发师睡觉问题,理发师和顾客工作流程,补充理发师睡觉问题,voidcustomer()P(mutex);/互斥waiting变量的操作if(waiting6)/有空椅子则坐下等待waiting+;/等待顾客数增1else离开；V(mutex);/允许waiting变量的操作P(wchair);/找一个空椅子坐下P(bchair);/再找理发椅坐下V(wchair);/允许其他人坐空椅子V(ready);/该顾客准备好了P(finish);/等待理发师完成理发V(bchair);/离开理发椅P(mutex);/互斥waiting变量的操作waiting-;/等待顾客数减1V(mutex);/允许waiting变量的操作,补充理发师睡觉问题,intwaiting=0;/等待的顾客,含正在理发的人数semaphoremutex=1;/waiting的互斥信号量semaphorebchair=1;/理发椅的个数semaphorewchair=5;/空椅子的个数semaphoreready=0;/是否有顾客准备好semaphorefinish=0;/理发师是否完成理发main()cobeginbaber();customer();coendvoidbaber()/理发师进程while(true)P(ready);/有顾客准备好了理发；V(finish);/允许其他顾客理发,某银行提供一个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：cobeginprocess顾客i从取号机上获取一个号码；等待叫号；获取服务；process营业员while(true)叫号；为顾客服务；请添加必要的信号量和P、V（或wait()、signal()）操作，实现上述过程中的互斥与同步。要求写出完成的过程，说明信号量的含义并赋初值。,补充理发师睡觉问题的类似问题,semaphoremutex=1;/互斥使用取号机的信号量semaphoreempty=10;/空座位的数量信号量semaphorefull=0;/已占座位的数量信号量semaphoreservice=0;/等待叫号信号量,补充理发师睡觉问题的类似问题,process顾客iP(empty);P(mutex);从取号机获得一个号；V(mutex);V(full);P(service);/等待叫号,process营业员while(true)P(full);V(empty);V(service);/叫号为顾客服务;,2.9消息传递,进程通信(InterProcessCommunication,IPC)进程之间的信息交换进程通信方式低级通信以信号、信号量作为通信工具，由于其所交换的信息量少而被归结为低级通信。高级通信指用户可直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。,2.9消息传递,电子邮件的发送与接收过程,2.9.1进程通信的方式,2.9.2共享存储区方式,共享数据结构（程序员控制）共享存储区（操作系统控制）,进程A的虚空间,内存空间,进程B的虚空间,A,A,B,B,2.9.3消息传递机制,数据交换以格式化的消息为单位消息的一般格式,2.9.3消息传递机制,消息传递的同步两条通信原语Send(destination,message)Receive(source,message)消息传递的同步当发送进程调用Send原语发送消息时，若没有空闲的消息缓冲区，则发送进程塞阻。当接收进程调用Receive原语接收消息时，如果没有消息可接收，则接收进程阻塞，直到一条消息到达。,2.9.3消息传递机制,三种同步方式,2.9.3消息传递机制,不阻塞发送如打印服务，每当进程需要打印时，都可以以消息形式发出请求，然后继续执行，无须阻塞等待打印完成。“不阻塞发送”方式容易导致消息的无限发送。必须在程序中考虑让接收进程发回应答消息，证实其是否收到消息增加了并发程序的设计难度。阻塞接收并发程序设计中常采用该方式。若消息丢失，或发送进程发送消息之前失败，则接收进程将永久阻塞。,2.9.3消息传递机制,消息传递中的寻址寻址方式：直接寻址和间接寻址。若采用直接寻址，send原语中必须指定目标进程的具体标识号receive原语中的source地址有两种处理方法：接收进程显式地指定发送方进程标识号，这就要求接收进程必须事先清楚将接收哪个进程发来的消息。接收进程可以不必指定接收哪个进程的消息,2.9.3消息传递机制,间接寻址采用间接寻址传递消息时，消息不再从发送方直接发送到接收方，而是通过发送进程与接收进程共享的一个数据结构进行中转，该数据结构通常称为邮箱。发送进程将消息发送到指定的邮箱中，接收进程从邮箱中接收消息。,2.9.3消息传递机制,邮箱不限制进程数，允许多个发送进程向邮箱发送消息，同时，也允许多个接收进程从邮箱接收消息,2.9.4利用消息传递实现互斥,互斥不允许两个或两个以上的进程同时进入临界区如何利用消息传递实现互斥？多个并发执行的发送进程和接收进程共享一个邮箱box，且box的初始状态为仅包含一条空消息；采用“不阻塞发送，阻塞接收”方式传递消息；若邮箱中存在一条消息，则允许一个进程进入临界区。若邮箱为空，则表明有一个进程位于临界区，其它试图进入临界区的进程必须阻塞。只要保证邮箱中最多只有一条消息，就能保证只允许一个进程进入临界区，从而实现进程互斥使用临界资源。,voidP(inti)messagemsg;while(true)receive(box,msg);/*从邮箱接收一条消息*/;send(box,msg);/*将消息发回到邮箱*/,/*programmutualexclusion*/constintn=/*进程数*/;,voidmain()create_mailbox(box);/*创建邮箱*/send(box,null);/*初始化，向邮箱发送一条空消息*/parbegin(P(1),P(2),P(n);,生产者/消费者模型缓冲区：固定大小生产者：满则等待，空则填充消费者：空着等待，有则获取,2.9.5利用消息传递解决生产者/消费者问题,2.9.5利用消息传递解决生产者/消费者问题,如何采用消息传递的方法实现生产者/消费者同步？使用capacity条消息，其作用类似于缓冲区的大小；capacity条消息的初始状态为“空”消息，类似于缓冲区的初始状态为空（未填充生产数据）；生产者生产一条数据后，取一条“空”消息，并发送回一条填充了数据的消息；消费者消费一条数据后，取一条填充了数据的消息，并发送回一条“空”消息；若生产者速度快于消费者消速度，则因无“空”消息可用而阻塞；若消费者速度快于生产者消速度，则因无填充了数据的消息可用而阻塞。,voidproducer()messagepmsg;while(true)receive(mayproduce,pmsg);pmsg=produce();send(mayconsume,pmsg);,voidmain()create_mailbox(mayproduce);create_mailbox(mayconsume);for(inti=1;i=capacity;i+)send(mayproduce,null);/初始化信箱parbegin(producer,consumer);,voidconsumermessagecmsg;while(true)receive(mayconsume,cmsg);consume(cmsg);send(mayproduce,null);,constint;capacity=/*缓冲区容量*/null=/*空消息*/,作业与Project,作业41.什么是临界资源、临界区，临界区的使用原则有哪些？2.简述信号量的含义及作用。3.请用P、V操作描述下列过程,作业与Project,作业4（续）4.图书馆有N个座位，一张登记表，要求(1)阅读者进入时登记，取得座位号；(2)出来时注销。请用P、V操作描述一个读者的使用过程。5.有3个进程PA，PB和PC合作解决文件打印问题：(1)PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；(2)PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；(3)PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P，V操作来保证文件的正确打印。,作业与Project,作业4（续）6.桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子；儿子专等吃盘中的桔子，女儿专等吃苹果。用P、V操作实现爸爸、儿子、女儿三个并发进程