《实现临界段的硬件方法概要》由会员分享，可在线阅读，更多相关《实现临界段的硬件方法概要（25页珍藏版）》请在金锄头文库上搜索。
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&S Ri,Aj 解释为将(Aj)地址所指内存单元内容读到Ri寄存器中,同时将1置入Aj所指的内存单元中. 设Lock为临界段锁变量，则安排如下指令，即可实现加锁与解锁：*,临界段,非临界段,A1 = (If (R1=
3、1)then goto Loop),A1 = (置Lock内存单元为0),二、“Swap”指令 其功能描述为： Procedure Swap（Var a,b：boolean）； Var temp：boolean； begin temp = a； a = b； b = temp； end；,设lock为全局布尔变量（初值为假），每个进程设一个局部布尔变量Key。利用Swap指令，可实现对临界区的加锁与解锁。,Repeat key = true; repeat Swap (lock, key); until key = false; critical section lock = false; n
4、on-critical section Until false;,设s为全局整形变量（初值为1) ，利用下面的指令序列，可实现对临界区的加锁与解锁吗？,Repeat while s = 0 do skip; s-; critical section s+; non-critical section Until false;,三、“Dec_and_Test”指令 其功能描述为： Function Dec_and_Test(Var s：int):boolean； begin s = s - 1； Dec_and_Read = (s = 0)； end；,设s为全局整形变量（初值为1) ，利用Dec
5、_and_Test指令，也可实现对临界区的加锁与解锁：,4.2.4 信号量,信号量机制：“信号量”、“P、V操作”。 信号量s为一整型变量，它只能通过P、V操作访问：,P(s): while !Dec_and_Test (s) do s+; V(s): s+；,一. 原子操作 原子操作：指完成某种功能且不被分割、不被中断执行的操作序列。或称此类操作序列为原子的。 在单机环境下：一条硬件指令就是一个原子操作，也可以通过中断屏蔽实现由一组指令序列构成的原子操作。 在多机环境下：一些硬件指令是原子的，如Test_and_Set、Swap、Dec_and_Test等。,一.信号量的使用(互斥与同步)
6、互斥：用于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(synch);,S2;,end;,Parend;,操作系统实现信号量时与进程调度相结合，消除忙等待现象。 原则是：在P操作循环等待的地方加入放弃处理机/挂入等待队列动作，在V操作时，从等待
7、队列中摘取进程变为就绪态。,二.信号量的具体实现,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.L队列取一进程挂入就绪队列,4.2.5 进程同步与互斥举例 一、有限缓冲区问题 问题描述：设有n个缓冲区，一组生产者进程往缓冲区写数据，一组消费者进程从缓冲区取数据，写取以一个缓冲区为
8、单位。 说明： 将缓冲池看作是共享数据，对缓冲区的 操作必须是互斥操作 如果缓冲区全满，生产者进程必须等待 如果缓冲区全空，消费者进程必须等待,有限缓冲区的生产者/消费者问题（生产者和消费者共享一个产品缓冲池）,共享N个缓冲区,P1 P2 Pm C1 C2 Cn,生产者,消费者,缓冲池,解：设置以下信号量 mutex,初值为1，控制互斥访问缓冲池 full,初值为0，表示当前缓冲池中满缓冲区数 empty,初值为n，表示当前缓冲池中空缓冲区数 有限缓冲区生产者/消费者进程描述如下： type item= ; var buffer= ; full,empty,mutex:semaphor; ne
9、xtp,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 in nextc; until false; end; Parend;,consumer:begin repeat P(full); P(mutex); remove an item f
10、rom 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)；取右筷子 吃 V(chopsticki);放左筷子 V(chopstick(i+1)mod 5；放右筷子 思考 until false;,(这可能导致死锁),小结,目的与要求：掌握信号量解决进程同步互斥问题的方法。 重点与难点：信号量的典型应用 作业：15，16，17,
