操作系统进程管理三互斥和同步二

1、12.3 进程互斥和同步 临界资源、临界区定义 记录型的信号量内部成员 的意义 signal wait操作含义 怎样利用信号量解决进程之间的前趋关系？2 临界区(critical section)：进程中访问临界资源的一段代码。 进入区(entry section)：在进入临界区之前，检查可否进入临界区检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临正在访问临界区界区标志 退出区(exit section)：用于将正在访问临界区标志清除。 剩余区(remainder section)：代码中的其余部分。返回32.3.1 基本概念-临界区 2、临界区：每个进程中访问临界资

2、源的那段、临界区：每个进程中访问临界资源的那段程序段称为临界区（临界段）。程序段称为临界区（临界段）。42.3.1 基本概念-临界区的访问过程entry sectionexit section critical section remainder section临界区的访问过程返回进入区退出区临界区5同步机制应遵循的准则 空闲让进：其他进程均不处于临界区； 忙则等待：已有进程处于其临界区； 有限等待：等待进入临界区的进程不能死等； 让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）返回6实现进程互斥的硬件方法 完全利用软件方法，有很大局限性（如不适于多进程），现在已很少采用。 可

3、以利用某些硬件指令其读写操作由一条指令完成，因而保证读操作与写操作不被打断；Test-and-Set指令该指令读出标志后设置为该指令读出标志后设置为TRUEboolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old;lock表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲7互斥算法（互斥算法（TS指令）指令） 利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE 在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；while TS

4、(&lock);lock = FALSE;critical sectionremainder section82.3.2 信号量(semaphore)需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。 1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。 信号量是一个被保护的变量，被初始化之后，只有只有wait操作、signal操作才能访问和改变它的值。信号量代表可用资源实体的数量

5、。 wait操作、signal操作又称为P、V操作。它们都是原子操作（原语原语）92.3.2 信号量(semaphore)一、一、整型信号量整型信号量 整型信号量是表示共享资源状态且只能由特殊的原子操作改变的整型量。 想法：定义一个整型变量，用整形变量值来标记资源 使用情况：如整型量0,说明有可用资源;整型量0说明资源忙，进程必须等待。 对于一次只允许一个进程访问的临界资源，可定义一个用于互斥的整型信号量，并初始化为初始化为1 1。 102.3.2 信号量(semaphore)一、一、整型信号量整型信号量 整型信号量的wait和signal操作Wait(s):while s0 do no-op

6、 对CS的互斥访问。 s:=s-1. Signal(s): s:=s+1 实现对资源的释放注：wait(s)和 signal(s)都是原子操作(原语）112.3.2 信号量(semaphore)一、一、整型信号量整型信号量 利用整型信号量实现互斥方法：利用整型信号量实现互斥方法： 想法：为必须互斥访问的CS定义一个互斥信号量mutexmutex，初始值为1，然后将CS放入wait(mutexwait(mutex) )和signal(mutexsignal(mutex) )之间，当CS可访问时，wait(mutexwait(mutex) )才能正常结束使进程进入CS。122.3.2 信号量(se

7、maphore)二、利用整型信号量实现互斥二、利用整型信号量实现互斥while mutex0 do no-op mutex:=mutex-1.mutexmutex:=mutex+1:=mutex+1 Begin Repeat wait(mutex); Critical section Signal(mutex) Remainder section Until false;end13三、利用信号量来协调进程执行的顺序三、利用信号量来协调进程执行的顺序例例1 1：P P1 1、P P2 2两个进程，要求两个进程，要求P P2 2必须在必须在P P1 1结束结束后执行后执行, ,为此，设置一个信号量

8、为此，设置一个信号量S,S,初始值初始值为为0 0。 parbegin begin P1; Signal(s); end begin Wait(s); P2 ; end parend14三、利用信号量来描述前趋关系三、利用信号量来描述前趋关系例2：有P1，P2两个进程：S1，S2，SS6分别是P1、P2中的语句，我们要求它们的执行顺序如下图所示 :15fS1S2S5S4S3S6gbdace16利用信号量来描述前趋关系利用信号量来描述前趋关系-例例2 2varvar a,b,c,d,e,f,g:semaphorea,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0;:=0,0

9、,0,0,0,0;beginbegin prabeginprabegin begimbegim s s1 1; signal(a); signal(b); end; signal(a); signal(b); end; begin wait(a); begin wait(a); s s2 2; ;signal(c); signal(d); signal(c); signal(d); end;end; begin wait(b); begin wait(b); s s3 3; ;signal(g); end;signal(g); end; begin wait(c); begin wait(c)

10、; s s4 4; ;signal(e); end;signal(e); end; begin wait(d); begin wait(d); s s5 5; ;signal(f); end;signal(f); end; begin wait(e); wait(f); wait(g); begin wait(e); wait(f); wait(g); s s6 6; ; end.end. parendparendend.end.17记录型信号量和wait、signal原语 信号量是一个确定的二元组（value, L），value 是一个具有非负初值的整型变量，L 是一个初始状态为空的队列。

11、value代表资源的实体。在实际应用中应准确地说明s的意义和初值; 初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”）若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数 L：每个信号量的相关队列，表示因得不到临界资源而阻塞的进程，其初始状态为空。 信号量和wait、signal原语 信号量只能通过信号量只能通过初始化初始化和和两个标准的两个标准的原语原语来访问来访问作为作为OS核心代码执行，核心代码执行，不受进程调度的打断不受进程调度的打断在实际操作系统中，一般情况下是由机器硬件提供在实际操作系统中，一般情况下是由机器硬件提供P、V操操

12、作作的指令，当然是原子操作，若机器不提供的指令，当然是原子操作，若机器不提供P、V操作的指操作的指令，则操作系统提供令，则操作系统提供P、V操作原语。操作原语。 信号量的形式化定义：信号量的形式化定义：type semaphore=record value: integer; L: listofprocess;end1. P原语(wait)19procedure wait(S)var S：semaphore；beginS.value:=S.value-1； /表示申请一个资源表示申请一个资源;if S.value0 then block(S.L)； /如果没如果没有空闲资源，调用进程进入和有空

13、闲资源，调用进程进入和信号量信号量S相关的等相关的等待队列待队列 s.L; 阻塞调用阻塞调用wait 的进程的进程end 2. V原语(signal)procedure signal(S)var S: semaphore；beginS.value:=S.value+1； /表示释放一个资源；表示释放一个资源；if S.value=1 & S2 = 1 & & Sn = 1) /满足资源要求时的处理；满足资源要求时的处理； for (i = 1; i = n; +i) -Si; /注：与注：与wait的处理不同，这里是在确信可满足的处理不同，这里是在确信可满足 /资源要求

14、时，才进行减资源要求时，才进行减1操作；操作； break; else /某些资源不够时的处理；某些资源不够时的处理； 调用进程进入第一个小于调用进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.L; 阻塞调用进程阻塞调用进程;将调用进程的将调用进程的PC置为置为swait操作开头操作开头 44 Ssignal(S1, S2, , Sn) for (i = 1; i = n; +i) +Si;/释放占用的资源；释放占用的资源； for (each process P waiting in Si.L) /检查每种资源的等待队列的所有进程；检查每种资源的等待队列的所有进程； 从等待队列从等

15、待队列Si.L中取出进程中取出进程P;进程进程P进入就绪队列进入就绪队列; 需要注意：需要注意：原先处于阻塞状态的进程，被唤醒后，从何处开始执行？原先处于阻塞状态的进程，被唤醒后，从何处开始执行？与与 记录型信号量机制有何不同？记录型信号量机制有何不同？451. 生产者消费者问题(the producer-consumer problem)问题描述：若干进程通过有限的共享缓冲区交换数据。其中，生产者进程不断写入，而消费者进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。共享缓冲区生产指针消费指针Producer 1Producer 2.Producer MCons

16、umer 1Consumer 2.Consumer N满空指针移动方向46生产者消费者问题 AND型信号量 若不愿意考虑wait操作的先后顺序，也可用AND型信号量来实现。 生产者进程中生产者进程中： 用用Swait(empty,mutex)代替代替wait(empty)和和wait(mutex), 用用Ssignal(mutex,full)代替代替signal(mutex)和和signal(full) 消费者进程中消费者进程中 用用Swait(full,mutex)代替代替wait(full)和和wait(mutex), 用用Ssignal(mutex,empty)代替代替signal(mu

17、tex)和和signal(empty)472. 读者写者问题读者写者问题(the readers-writers problem) 问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个 “读写”互斥， “写写”互斥， 读读允许48 采用信号量机制： Wmutex表示允许写，初值是1。 公共变量Rcount表示“正在读”的进程数，初值是0； Rmutex表示对Rcount的互斥操作，初值是1。P(Rmutex); if (Rcount = 0)P(Wmutex); +Rcount;V(Rmutex); read;P(Rmutex); -Rcount; if (Rc

18、ount = 0)V(Wmutex);V(Rmutex);ReaderP(Wmutex); write;V(Wmutex);Writer49 采用一般信号量集机制：问题增加一个限制条件：同时读的读者最多R个 Wmutex表示允许写，初值是1 Rcount表示允许读者数目，初值为RSwait(Rcount, 1, 1; Wmutex, 1, 0); read;Ssignal(Rcount, 1);ReaderSwait(Wmutex, 1, 1; Rcount, R, 0); write;Ssignal(Wmutex, 1);Writer503. 哲学家进餐问题(the dining philo

19、sophers problem) 问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；5152 1.利用记录型信号量机制解决 2.利用AND型信号量机制解决2.4.2哲学家就餐问题53哲学家就餐问题 问题分析： 筷子是临界资源：每根有多于一个哲学家要用，而且同时只能有一个哲学家使用 5根筷子可以用5个信号量表示。形成信号量数组： var ch

20、opstick:array0,4of semaphore； 所有信号量初值为1，表示未被使用。54哲学家就餐问题 第第i位哲学家的活动描述为：位哲学家的活动描述为： Repeat wait(chopsticki); wait(chopstick(i+1)mod 5); eat; signal(chopsticki); signal(chopstick(i+1)mod 5); think; Until false;parbegin philosopher (0)；philosopher (1)；philosopher (2)；philosopher (3)；philosopher (4)；parend