Os-04-1_2同步及互斥

1、1计算机操作系统教程(第2版)24.4 .1 进程间的互斥( Mutual Exclusion )为什么要讨论互斥？3现代操作系统中进程执行的特点：独立性，异步性，并发并发带来的影响:资源共享（提高资源利用率 如CPU）资源竞争（出现不希望出现的错误）4ReadFromFileA ( X ) ；if ( X 1 ) thenX := X - 1；WriteToFileA( X ) ；飞机订票系统：远程终端通过位于服务器主机中的进程Ti处理订票业务；位于服务器主机中的文件FileA存放的数据表示剩余的票数和下一次即将卖出的座位号25ms50ms5T1ReadFromFileA(X) ；if (

2、X 1 ) thenX := X - 1；WriteToFileA( X ) ；50ms (1)飞机订票系统：位于武昌的某远程终端通过位于服务器主机中的进程 T1 处理订票业务；位于汉口的某远程终端通过位于服务器主机中的进程 T2 处理订票业务；T2ReadFromFileA(X) ；if ( X 1 ) thenX := X - 1；WriteToFileA( X ) ；50ms (2)6T1ReadFromFileA(X) ；if ( X 1 ) then25ms (1)T2ReadFromFileA(X) ；if ( X 1 ) thenX := X - 1；25ms (3)WriteT

3、oFileA( X ) ；25ms (2)X := X - 1；25ms (4)WriteToFileA( X ) ；飞机订票系统：71. 大量共享资源如只读数据可以同时访问，以提高资源的利用率；2. 部分资源（如外设、共享数据结构），多个进程在对其进行访问时（主要是进行写入或修改），可能出现无法预料的错误。提高资源利用率的前提是要保证数据的完整性和安全性。进程间的并发必须加以控制怎么控制？8进程的互斥 Mutual Exclusion1.可以同时使用的2.不可以同时使用的由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程间的这种关系为进程互斥。两个概念：临界资

4、源：critical resource临界区 ：critical section9系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源。临界资源：critical resource10程序 段1程序 段2程序 段n共享变 量11临界区（互斥区）：critical section在进程中涉及到临界资源的程序段叫临界区。多个进程关于同一临界资源的一组临界区称为相关临界区集合。12临界区的访问过程的抽象算法entry sectioncritical sectionexit sectionremainder section13进程间互斥问题的解决（P、V操作）P1P(mutex)V(

5、mutex)互斥区P2P(mutex)V(mutex)P3P(mutex)V(mutex)14进程互斥问题模拟演示有控的进程并发无控的进程并发具体实现？154.4 .2 互斥算法1 中断屏蔽方法2 “测试并设置”指令3 上锁原语4 信号量 (semaphore)16临界区的访问过程entry sectioncritical sectionexit sectionremainder section17中断屏蔽方法“开关中断”指令进入临界区前执行：执行“关中断”指令离开临界区后执行：执行“开中断”指令简单，有效较高的代价，限制CPU并发能力（临界区小）不适应多处理器“测试并设置”指令boolean

6、 TS (boolean*lock)boolean old;old = *lock;*lock = true;Return old;Test-and-Set指令lock表示资源的两种状态：TRUEFALSE占用空闲利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通 1819互斥算法（TS指令）while TS(&lock);critical sectionlock = FALSE;remainder section20测试并设置”指令方法的缺点等待要耗费CPU时间，空转，不能实现“让权

7、等待”；每次获得CPU都要重新测试可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，不公平21上锁原语Lock ( x )if( x=true)保护现行进程的CPU现场；现行进程进入x的等待队列；设置该进程为等待状态；转进程调度；x=true;UnLock ( x )if (x等待队列不空) 移出队列首元素；将进程放入就绪队列；设置该进程为就绪状态；x=false;22上锁原语PB remainder section Lock (key ) critical section UnLock (key ) remainder section 23优点：不用空转CPU ；缺点

8、：每次被唤醒获得CPU,还要重新测试；可能会上当不公平现象；上锁原语24Goto APA和PB反复使用临界区的情况：PAA：lock(key)unlock(key)PBB：lock(key)unlock(key)Goto B25解决上述问题首先必须找到产生问题的原因。显然，在用加锁法解决进程互斥的问题时，一个进程能否进入临界区是依靠进程自己调用lock过程去测试相应的锁定位。每个进程能否进入临界区是依靠自己的测试判断。这样没有获得执行机会的进程当然无法判断，从而出现不公平现象。而获得了测试机会的进程又因需要测试而损失一定的CPU 时间。上锁原语26这正如某个学生想使用某个人人都可借用、且不规定

9、使用时间的教室时一样，他必须首先申请获得使用该教室的权利，然后再到教室看看该教室是不是被锁上了。如果该教室被锁上了，他只好下次再来观察，看该教室的门是否已被打开。这种反复将持续到他进门后为止。27一种最直观的办法是，设置一个教室管理员。如果有学生申请使用教室而未能如愿时，教室管理员记下他的名字，并等到教室门一打开则通知该学生进入。这样，既减少了学生多次来去教室检查门是否被打开的时间，又减少了因为学生自发地检查造成的不公平现象。28信号量(semaphore)前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来

10、处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。信号量代表可用资源实体的数量。29信号量和P、V原语1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语 Passeren 和Verhoog 的头一个字母，相当于英文的Pass和Increment的意思)。P、V是一种卓有成效的进程同步机制。30每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识信号量只能通过初始化和两个标准的原语来访问作为OS核心代码执行，不受进程调度的打断初始化指定一个非负整数值，表示空闲资源总数（又称为资源信号量）若为非负值表示

11、当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数31在整数值s.count大于等于零时代表可供并发进程使用的资源实体数，在整数值s.count小于零时则表示正在等待使用临界区的进程数。显然，信号量s的初值应该大于零。32原语操作功能原语操作功能331. P原语wait(s)-s.count; /表示申请一个资源;if (s.count 0) /表示没有空闲资源;调用进程进入等待队列s.queue;阻塞调用进程;342. V原语signal(s)V原语通常唤醒进程等待队列中的头一个进程+s.count; /表示释放一个资源；if (s.count = 0)/表示有进程处于阻塞状态；从

12、等待队列s.queue中取出一个进程P;进程P进入就绪队列;35重复或遗漏3. 利用信号量实现互斥P(mutex);critical sectionV(mutex);remainder section为临界资源设置一个互斥信号量mutex(MUTualExclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、36用P、V操作解决进程间互斥问题P1P(mutex)V(mutex)互斥区P2P(mutex)V(m

13、utex)P3P(mutex)V(mutex)374. 利用信号量来描述前趋关系前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为每个前趋关系设置一个互斥信号量S12，其初值为0P1C1V(S12);P2P(S12);C238经典的生产者消费者问题消费者生产者39经典的生产者消费者问题（续1）同步问题：P进程不能往“满”的缓冲区中放产品，设置信号量为SemptyQ进程不能从“空”的缓冲区中取产品，设置信号量Sfull40Sempty初值为1，Sfull初值为0deposit(data) ：while (true) 生产一个产品;P(Sempty) ;送产品

14、到缓冲区;V(Sfull);remove(data) ：while (true) P(Sfull);从缓冲区取产品;V(Sempty);消费产品;经典的生产者消费者问题（续2）411 单生产者 单消费者 单缓冲区2 多生产者 多消费者 单缓冲区3 单生产者 单消费者 多缓冲区4 多生产者 多消费者 多缓冲区经典的生产者消费者问题（续2）互斥：生产者消费者 （对缓冲区）同步：生产者消费者消费者生产者消费者消费者互斥：生产者消费者生产者生产者同步：生产者消费者消费者生产者互斥：生产者消费者 （对缓冲区队列）同步：生产者消费者消费者生产者互斥：生产者消费者 （对缓冲区队列）生产者生产者 消费者消费者

15、同步：生产者消费者 消费者生产者42deposit(data)P(Sempty) ;P(Mutex) ;Buf(x)data ;V(Mutex) ;V(Sfull) ;remove(data)P(Sfull) ;P(Mutex) ;dataBuf(x) ;V(Mutex);V(Sempty) ;（1）为互斥设置一个公用信号量Mutex，初值为1（2）为同步设置两个私用信号量Sempty，初值为n；Sfull，初值为0；43注意：P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那

16、么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要44（1）为互斥设置一个公用信号量Mutex，初值为1（2）为同步设置两个私用信号量empty，初值为n；full，初值为0；deposit(data)P(Mutex) ;P(Sempty) ;Buf(x)data ;V(Mutex) ;V(Sfull) ;remove(data)P(Mutex) ;P(Sfull) ;dataBuf(x) ;V(Mutex);V(Sempty) ;45一家人吃苹果、桔子问题（1）只有 一个 盘子，盘子中只能放一个水果（2）父亲削苹果，放入盘中（3）母亲剥

17、桔子，放入盘中（4）儿子从盘中拿苹果，吃（5）女儿从盘中拿桔子，吃分析：多生产者、多消费者、单缓冲区 模型(挑剔的消费者)同步关系：父亲儿子， 母亲女儿，儿子（女儿） 父亲（母亲）46信号量Sapple=0，Sorange=0, Semptyplate=1；father()削苹果；P(Semptyplate) ;放入盘中 ;V(Sapple) ; mother()剥桔子；P(Semptyplate) ;放入盘中 ;V(Sorange) ; son() P(Sapple) ;从盘中拿苹果;V(Semptyplate) ;吃苹果； daughter() P(Sorange) ;从盘中拿桔子;V(S

18、emptyplate) ;吃桔子； 47例:司机P1售票员P2while (true)启动车辆；正常运行；到站停车；while (true)关门；售票；开门；1648信号量及P、V操作讨论1) 信号量的物理含义：S0表示有S个资源可用S=0表示无资源可用S0则| S |表示S等待队列中的进程个数P(S)：表示申请一个资源V(S)：表示释放一个资源。信号量的初值应该大于等于049进程互斥和同步举例50Windows NTMutex对象：互斥对象，相当于互斥信号量，在一个时刻只能被一个线程使用。有关的API：CreateMutex创建一个互斥对象，返回对象句柄；OpenMutex返回一个已存在的互

19、斥对象的句柄，用于后续访问；ReleaseMutex释放对互斥对象的占用，使之成为可用；对象可用(signaled state)表示该对象不被任何线程使用或所有；1. NT支持的三种同步对象对象名称是由用户给出的字符串。不同进程中用同样的名称来创建或打开对象，从而获得该对象在本进程的句柄。51Semaphore对象：相当于资源信号量，取值在0到指定最大值之间，用于限制并发访问的线程数。有关的API：CreateSemaphore创建一个信号量对象，指定最大值和初值，返回对象句柄；OpenSemaphore返回一个已存在的信号量对象的句柄，用于后续访问；ReleaseSemaphore释放对信号

20、量对象的占用；52Event对象：事件对象，相当于触发器，可通知一个或多个线程某事件的出现。有关的API：CreateEvent创建一个事件对象，返回对象句柄；OpenEvent返回一个已存在的事件对象的句柄，用于后续访问；SetEvent和PulseEvent设置指定事件对象为可用状态；ResetEvent设置指定事件对象为不可用状态（nonsignaled）；手工复位，并唤醒所有等待线程；532. 同步对象等待(1) WaitForSingleObject在指定的时间内等待指定对象为可用状态(signaled state)；DWORD WaitForSingleObject( HANDLE

21、 hHandle,/ handle of object to wait for/ time-out interval in millisecondsDWORD dwMilliseconds);(2) WaitForMultipleObjects在指定的时间内等待多个对象为可用状态；DWORD WaitForMultipleObjects( DWORD nCount,/对象句柄数组中的句柄数；CONST HANDLE *lpHandles,/ 指向对象句柄数组的指针，数组中可包括多种对象句柄；BOOL bWaitAll,/ 等待标志：TRUE表示所有对象同时可用，FALSE表示至少一个对象可用；

22、DWORD dwMilliseconds / 等待超时时限；);544. 其他同步方法Critical Section对象：只能在同一进程内使用的临界区，同一进程内各线程对它的访问是互斥进行的。把变量说明为CRITICAL_SECTION类型，就可作为临界区使用。有关的API：InitializeCriticalSection对临界区对象进行初始化；EnterCriticalSection等待占用临界区的使用权，得到使用权时返回；TryEnterCriticalSection非等待方式申请临界区的使用权；申请失败时，返回0；LeaveCriticalSection释放临界区的使用权；Delet

23、eCriticalSection释放与临界区对象相关的所有系统资源；55互锁变量访问：相当于硬件指令，对一个整数（进程内的变量或进程间的共享变量）进行操作。其目的是避免线程间切换的影响。有关的API：InterlockedExchange进行32位数据的先读后写原子操作；InterlockedCompareExchange依据比较结果进行赋值的原子操作；InterlockedExchangeAdd先加后存结果的原子操作；InterlockedDecrement先减1后存结果的原子操作；InterlockedIncrement先加1后存结果的原子操作；56管程管程和条件变量霍尔方法实现管程汉森方

24、法实现管程57管程PV操作：分散式同步机制：共享变量操作，PV操作，分散在整个系统中或各个进程中。缺点：可读性差；正确性不易保证；不易修改。优点：高效，灵活。管程：集中式同步工具：共享变量及其所有相关操作集中在一个模块中。优点：可读性好；正确性易于保证；易于修改。缺点：不甚灵活，效率略低。58管程：一种同步机制(管程-进程)管程定义:指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作593.4.1 什么是管程为什么要引入管程把分散在各进程中的临界区集中起来进行管理 ；防止进程有意或无意的违法同步操作，便于用高级语言来书写程序，也便于程序正确性验证。管程的属性共享性安全性

25、互斥性60管程的形式TYPE monitor_name = MONITOR;共享变量说明define 本管程内所定义、本管程外可调用的过程（函数）名字表use本管程外所定义、本管程内将调用的过程（函数）名字表PROCEDURE 过程名（形参表）；过程局部变量说明；BEGIN语句序列；END;.61管程的形式（续）FUNCTION 函数名（形参表）：值类型；函数局部变量说明；BEGIN语句序列；END;.BEGIN共享变量初始化语句序列；END;管程的四个组成部分：名称共享数据结构说明对该数据结构进行操作的一组过程/函数初始化语句62管程有如下几个要素：（一）管程中的共享变量在管程外部是不可见的

26、，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量（二）为了保证管程共享变量的数据完整性，规定管程互斥进入（三）管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作管程的要素63因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。管程的实现问题64问题：多个进程出现在管程中当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的进程，两者必须有一个退出或停止使

27、用管程。管程的实现问题（续1）65管程的实现问题（续1）问题：多个进程出现在管程中处理方法有三种：等待继续，直到退出或等待（Hoare）等待继续，直到等待或退出规定唤醒为管程中最后一个可执行的操作66管程的实现问题（续1）如果进程唤醒进程，则等待继续，如果进程在执行又唤醒进程，则等待继续， （Hoare）在管程内部，由于执行唤醒操作，可能会出现多个等待进程，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级。67由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。(* 资

28、源等待而非管程等待 *)(入口等待队列和紧急等待队列都是需要管程)为此在管程内部可以说明和使用一种特殊类型的变量，称作条件变量：VAR C:condition;对于条件型变量，可以执行wait和signal操作：管程的实现问题（续2）68管程的条件变量条件变量当调用管程过程的进程无法运行时，用于阻塞进程的一种信号量同步原语wait,signal当一个管程过程发现无法继续时，它在某些条件变量condition上执行wait，这个动作引起调用进程阻塞另一个进程可以通过对其伙伴在等待的同一个条件变量condition上执行同步原语signal操作来唤醒等待进程。69管程的实现问题（续3）wait（c

29、）：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程的PCB入c链尾部signal（c）：如果c链为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程的PCB入紧急等待队列的尾部70管程的实现问题（续3）使用signal释放等待进程时，可能出现两个进程同时停留在管程内解决方法执行signal的进程等待，直到被释放进程退出管程或等待另一个条件被释放进程等待，直到执行signal的进程退出管程或等待另一个条件霍尔采用了第一种办法汉森选择了两者的折衷，规定管程中的过程所执行的signal操作是过程体的最后一个操作71wait(c1)con

30、dition cnwait(cn)urgent queuesignal入口管程等待调用的进程队列局部数据管程的结构管程等待区域condition c1条件变量过程1过程k初始化代码出口72Hoare方法实现管程霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理。不要求signal操作是过程体的最后一个操作，且wait和signal操作可被设计成可以中断的过程。73Hoare管程数据结构公用信号量mutex对每个管程，使用用于管程中过程互斥调用的信号量mutex（初值为1）。进程调用管程中的任何过程时，应执行P(mutex)；进程退出管程时应执行V(mutex

31、)开放管程，以便让其他调用者进入。为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源。74urgent和urgent-count信 号 量 urgent （ 初 值 为 0 ） ， 凡 发 出signal操作的进程应该用P(urgent)挂起自己，直到被释放进程退出管程或产生其他等待条件。进程在退出管程的过程前，须检查是否有别的进程在信号量urgent上等待，若有，则用V(urgent)唤醒它。urgent-count（初值为0），用来记录在urgent上等待的进程个数。75x-sem和 x-count引入信

32、号量x-sem（初值为0），申请资源得不到满足时，执行P(x-sem)挂起。用计数器x-count（初值为0）记录等待资源的进程数。执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现。76每个管程定义如下数据结构TYPE interf = RECORDmutex:semaphore; /*进程调用管程过程前使用的互斥信号量*/urgent:semaphore; /*发出signal的进程挂起自己的信号量*/urgent_count:integer;/*在next上等待的进程数*/END;77Hoare管程的外部过程形

33、式任何一个调用管程中过程的外部过程应组织成下列形式，确保互斥地进入管程。P(IM.mutex);if IM.urgent_count 0 then V(IM.urgent);else V(IM.mutex);78汉森方法实现管程汉森方法的管程中的过程所执行的signal操作一定是过程体的最后一个操作，一个进程当所调用的过程执行了signal操作后，便立即退出了管程。汉森方法使用四条原语WaitSignalCheckre1ease79每个管程使用的一个数据类型TYPE interf = RECORDintsem : condition; /* 开放管程的信号量 */count1 : intege

34、r;count2 : integer;END;/* 等待调用的进程个数 */* 调用了管程中的过程且不处于等待状态的进程个数 */80调用查看原语check如果管程是开放的，则执行这条原语后关闭管程，相应进程继续执行；如果管程是关闭的，则执行这条原语后相应进程被置成等待调用状态procedure check(var IM interf);beginif IM.count2 = 0then IM.count2 := IM.count2 + 1;elsebeginIM.count1 := IM.count1 + 1;W(IM.intsem);end;end;81开放原语release如果除了发出这

35、条原语的进程外，不再有调用了管程中过程但又不处于等待状态的进程，那么就释放一个等待者或开放管程procedure release(var IM interf);beginIM.count2 := IM.count2 - 1;if IM.count2 = 0 and IM.count1 0 thenbeginIM.count1 := IM.count1 - 1;IM.count2 := IM.count2 + 1;R(IM.intsem);end;end;82等待原语wait执行这条原语后相应进程被置成等待状态，同时开放管程，允许其它进程调用管程中的过程procedure wait(var s:

36、condition; var IM interf);begins := s + 1;IM.count2 := IM.count2 1;if IM.count1 0 thenbeginIM.count1 := IM.count1 1;IM.count2 := IM.count2 + 1;R(IM.intsem);end;W(s);end;释放原语signal执行这条原语后释放指定等待进程队列中的一个进程。如指定等待进程队列为空，本操作相当于空操作varIM83procedure signal(var s:condition;interf);beginif s 0 thenbegins := s

37、1;IM.count2 := IM.count2 + 1;R(s);end;end;84利用汉森方法实现的管程实现进程同步时，进程应按下列次序工作请求资源使用资源释放资源85TYPE one_instance=RECORDmutex:semaphore;（初值1）urgent:semaphore;（初值0）urgent_count:integer;（初值0）END;TYPEmonitor_elements=MODULE;define enter,leave,wait,signal;mutex（入口互斥队列）urgent（紧急等待队列）urgent_count（紧急等待队列计数）86PROCED

38、URE enter(VAR instance:one_instance);BEGINP(instance.mutex)END;87PROCEDURE leave(VARinstance:one_instance);BEGINIF instance.urgent_count 0 THENBEGIN instance.urgent-;V(instance.urgent)ENDELSEV(instance.mutex)END;88PROCEDURE wait(VAR instance:one_instance;VARs:semephore;VAR count:integer);BEGINcount+;IF instance.urgent_count0 THENBEGINinstance.urgent_count-;V(instance.urgent)ENDELSEV(instance. mutex);P(s);END;89PROCEDUREsignal(VAR instance:one_instance;VAR s:semaphore;VAR count:integer);BEGINIF count0 THENBEGINcount-;instance.urgent_count+;V(s);P(instance.urgent)ENDEND;90例子