《操作系统精髓与设计原理Chap5.ppt》由会员分享，可在线阅读，更多相关《操作系统精髓与设计原理Chap5.ppt（120页珍藏版）》请在金锄头文库上搜索。
1、Concurrency: Mutual Exclusion and SynchronizationChapter 5while(1) input，process，output Utilizing rate of CPU:52/(78+52+20)35%78InputProcessorDisk130 150228280300378430450 TimeConcunrrency Utilizing rate of CPU: （52 * n） /（78*n+52+20） = 67%78InputProcessorDisk130150228306208286384364 TimeWhile(1) in
2、put,send While(1) receive,process,send While(1) receive,outputOutline 5.1 Principle of concurrency 5.2 Mutual Exclusion:Hardware support 5.3 Semaphores 5.4 Monitors 5.5 Message passing 5.6 Readers/Writers problemSoftware support5.1 Principle of concurrency 进程执行的并发性：一组进程的执 行在时间上是重叠的。也就说一个进 程执行的第一条指令是
3、在另外一个进 程执行的最后一条指令之前开始的。 并发的实质是一个处理器在几个进 程之间的多路复用，并发是对有限的 物理资源强制行使多用户共享，消除 计算机部件之间的互等现象，以提高 系统资源利用率并发进程分类 无关的并发进程：一组并发进程分别在不同 的变量集合上操作，一个进程的执行与其他并发 进程的进展无关。 交互的并发进程：共享某些变量，一个进程 的执行可能影响其它进程的执行结果，具有制约 关系。 并发系统中诸进程由于资源共享、进程合作 ，而产生进程之间的相互制约；又因共享资源 的方式不同，而导致两种不同的制约关系： 间接制约关系（进程互斥）：由于共享资源 而引起的在临界区内不允许并发进程交
4、叉执行的 现象称为由共享公有资源而造成的对并发进程执 行速度的间接制约。(系统资源：如A、B两进程 竞争打印机) 直接制约关系（进程同步）：由于并发进程 互相共享对方的私有资源所引起的直接制约。（ 进程间合作：如输入进程、计算进程和打印进程 ）进程互斥指若干进程要使用同一共享资源时 ，任何时刻最多允许一个进程使用，其他进程 必须等待，直到占有资源的进程释放该资源。 进程同步指两个以上进程基于某个条件来协 调它们的活动。一个进程的执行依赖于协作进 程的消息或信号，当一个进程没有得到来自于 协作进程的消息或信号时需等待，直到消息或 信号到达才被唤醒进入就绪态 同步点：暂停等待以取得同步的那一点 同
5、步条件：需要等待一个进程完成的操作或发送的 信息。 对于一组交互的并发进程，执行 的相对速度无法相互控制，各种与 时间有关的错误就可能出现。 与时间有关错误的表现形式： 结果不唯一 永远等待Simple Example error about execution speedvoid echo()chin = getchar();chout = chin;putchar(chout);Process P1Process P2chin = getchar();. chin = getchar();. chout = chin;. putchar(chout);chout = chin;.putch
6、ar(chout);.Uncertain resultUncertain resultprocess Ti ( i = 1, 2 )var Xi:integer; begin 按旅客定票要求找到Aj； Xi := Aj; if Xi=1 then begin Xi:=Xi-1; Aj:=Xi;输出一张票 ； end else 输出票已售完； end;假设一个飞机订票 系统有两个终端， 分别运行进程Tl 和T2。该系统的公 共数据区中的一些 单元Aj(j=l，2， )分别存放某月 某日某次航班的余 票数，而xl 和x2 表示进程T1 和T2 执行时所用的工作 单元。飞机票售票 程序如右： 由于T
7、1 和T2 是两个可同时执行的并发进程，它们在 同一个计算机系统中运行，共享同一批票源数据，因此， 可能出现如下所示的运行情况。 T1: X1 := Aj; X1 = m (m0) T2: X2 := Aj; X2 = m T2: X2:=X2-1; Aj:=X2;输出一张票； Aj = m-1 T1: X1:=X1-1; Aj:=X1;输出一张票； Aj = m-1 两个旅客可能各自都买到一张同天同次航班的机票， 可是，Aj 的值实际上只减去了1，造成余票数的不正确。 特别是，当某次航班只有一张余票时，就可能把这一张票 同时售给了两位旅客，这是不能允许的。Waiting foreverpro
8、cedure borrow (var B:integer)beginif Bx then申请进程进入等待队列等主存资源x:=x-B;修改主存分配表，申请进程获得主存资 源end; procedure return (var B:integer)beginx:=x+B;修改主存分配表释放等主存资源的进程end;假定有两个并发 进程borrow 和 return 分别负 责申请和归还主 存资源，算法描 述中，x表示现 有空闲主存总量 ，B表示申请或 归还的主存量。 并发进程算法及 执行描述如右：由于borrow 和return 共享了表示主存物 理资源的临界变量x，对并发执行不加限制会 导致错误。
9、例如，一个进程调用borrow 申请 主存，在执行了比较B 和x 的指令后，发现 Bx，但在执行申请进程进入等待队列等主 存资源前，另一个进程调用return抢先执行 ，归还了所借全部主存资源。这时，由于前 一个进程还未成为等待状态，return中的释 放等主存资源的进程相当于空操作。以后当 调用borrow 的进程被置成等主存资源时，可 能己经没有其他进程来归还主存资源了，从 而，该申请资源的进程处于永远等待状态。 Solution : Control the code that accesses the shared global variableOperating System Conc
10、ernsKeep track of active processes Allocate and deallocate resources Processor time Memory Files I/O devices Protect data and resources Result of process must be independent of the speed of execution of other concurrent processesCompetition Among Processes for Resources Mutual Exclusion Critical res
11、ource: non-sharable resource Critical sections: the portion of program that use critical resource Only one program at a time is allowed in its critical section Deadlock A situation in which two or more processes are unable to proceed because each is waiting for one of the others to do something. Sta
12、rvation A situation in which a runnable process is overlooked indefinitely by the scheduler;although it is able to proceed,it is never chosen.Requirements for Mutual Exclusion Only one process at a time is allowed in the critical section for a resource A process that halts in its non-critical sectio
13、n must do so without interfering with other processes No deadlock or starvationRequirements for Mutual Exclusion A process must not be delayed access to a critical section when there is no other process using it No assumptions are made about relative process speeds or number of processes A process r
14、emains inside its critical section for a finite time only互斥机制要求l空闲让进 忙则等待 有限等待 让权等待（当进程不能进入临界区， 应该立即释放处理机，防止进程忙等待 ）Implementation of mutual exclusion Software approaches Hardware approaches Support of OS or programming language Semaphores Monitors Message passingFirst AttemptEach process can examine
15、 the others status but cannot alter it When a process wants to enter the critical section is checks the other processes first If no other process is in the critical section, it sets its status for the critical section This method does not guarantee mutual exclusion Each process can check the flags a
16、nd then proceed to enter the critical section at the same timeBoolean inside1,inside2: inside1 = false; /* P1 is not in its critical section */ inside2 = false; /* P2 is not in its critical section */ void P1( )while (inside2) ;inside1 = true; critical section ; inside1 = false;void P2( )while( inside1);inside2 = true; crit
