实现临界段硬件方法

1、第八讲 信号量,4.2.3 实现临界段的硬件方法 4.2.4 信号量 信号量的使用（互斥与同步） 信号量的具体实现 4.2.5 进程同步与互斥举例 有限缓冲区问题 哲学家就餐问题,4.2.3 实现临界段的硬件方法,利用处理机提供的特殊指令实现临界区加锁 常见硬件指令有:,一、“Test_and_Set”指令 二、“Swap”指令 三、“Dec_and_Test”指令,一、“Test_and_Set”指令 其功能描述为： Function Test_and_Set(Var target：boolean) :boolean； begin Test_and_Set = target； target

2、= true； end；,设lock为全局布尔变量，利用Test_and_Set指令，即可实现对临界区的加锁与解锁：,Repeat while Test_and_Set (lock) do skip critical section lock = false; non-critical section Until false;,“Test_and_Set” 读后置1指令实例： T repeat Swap (lock, key); until key = false; critical section lock = false; non-critical section Until false;

3、,设s为全局整形变量（初值为1) ，利用下面的指令序列，可实现对临界区的加锁与解锁吗？,Repeat while s = 0)； end；,设s为全局整形变量（初值为1) ，利用Dec_and_Test指令，也可实现对临界区的加锁与解锁：,4.2.4 信号量,信号量机制：“信号量”、“P、V操作”。 信号量s为一整型变量，它只能通过P、V操作访问：,P(s): while !Dec_and_Test (s) do s+; V(s): s+；,一. 原子操作 原子操作：指完成某种功能且不被分割、不被中断执行的操作序列。或称此类操作序列为原子的。 在单机环境下：一条硬件指令就是一个原子操作，也可以

4、通过中断屏蔽实现由一组指令序列构成的原子操作。 在多机环境下：一些硬件指令是原子的，如Test_and_Set、Swap、Dec_and_Test等。,一.信号量的使用(互斥与同步) 互斥：用于n个进程的临界段互斥，n进程共享一个信号量mutex,初值为1，任一进程Pi的结构为：,P(mutex),V(mutex),临界段,非临界段,repeat,until false,同步：有P1、P2 两进程，必须在P1执行完S1语句后，P2才能执行S2。需同步的两进程共享信号量synch，初值为0。,Parbegin,P2: begin,P1: begin,S1;,V(synch);,end;,P(sy

5、nch);,S2;,end;,Parend;,操作系统实现信号量时与进程调度相结合，消除忙等待现象。 原则是：在P操作循环等待的地方加入放弃处理机/挂入等待队列动作，在V操作时，从等待队列中摘取进程变为就绪态。,二.信号量的具体实现,1、信号量定义 type Semaphore=record value:integer; 一个数型变量 L:List of process;一个PCB队列 end; 2、P操作 P(S):S.Value-; if S.value0 then 保存现场 将本进程挂入S.L队列，重新调度 3、V操作 V(S):S.value+ if S.value0 then 从S.

6、L队列取一进程挂入就绪队列,4.2.5 进程同步与互斥举例 一、有限缓冲区问题 问题描述：设有n个缓冲区，一组生产者进程往缓冲区写数据，一组消费者进程从缓冲区取数据，写取以一个缓冲区为单位。 说明： 将缓冲池看作是共享数据，对缓冲区的 操作必须是互斥操作 如果缓冲区全满，生产者进程必须等待 如果缓冲区全空，消费者进程必须等待,有限缓冲区的生产者/消费者问题（生产者和消费者共享一个产品缓冲池）,共享N个缓冲区,P1 P2 Pm C1 C2 Cn,生产者,消费者,缓冲池,解：设置以下信号量 mutex,初值为1，控制互斥访问缓冲池 full,初值为0，表示当前缓冲池中满缓冲区数 empty,初值为

7、n，表示当前缓冲池中空缓冲区数 有限缓冲区生产者/消费者进程描述如下： type item= ; var buffer= ; full,empty,mutex:semaphor; nextp,nextc:item; begin full:=0; empty:=n; mutex:=1;,P(empty); P(mutex); add nextp to buffer; V(full); V(mutex); until false; end;,Parbegin Producer: begin repeat produce an item in nextp; ., consume the item i

8、n nextc; until false; end; Parend;,consumer:begin repeat P(full); P(mutex); remove an item from buffer to nextc 释放缓冲区 V(empty); V(mutex);,二、哲学家就餐问题 问题描述：五个哲学家五只筷子，哲学家循环做着思考和吃饭的动作，吃饭程序是：先取左边筷子，再取右边筷子，再吃饭，再放筷子。,实现： 为每个筷子设一把锁（信号量，初值为1） var chopstick:array 0,4of semaphore; 第i个进程描述为(i=0, ,4): repeat P(chopsticki);取左筷子 P(chopstick(i+1)mod 5)；取右筷子 吃