实现临界段的硬件方法概要.ppt

第八讲 信号量 4.2.3 实现临界段的硬件方法 4.2.4 信号量 信号量的使用（互斥与同步） 信号量的具体实现 4.2.5 进程同步与互斥举例 有限缓冲区问题 哲学家就餐问题 小结 目的与要求：掌握信号量解决进程同步互斥问题的方法。 重点与难点：信号量的典型应用 作业：15，16，17 * * * 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 = 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指令实例： TS Ri,Aj 解释为将(Aj)地址所指内存单元内容读到Ri寄存器中,同时将1置入Aj所指的内存单元中. 设Lock为临界段锁变量，则安排如下指令，即可实现加锁与解锁：* 临界段 非临界段 A1 = Lock;（将Lock单元地址送A1寄存器,Lock初值为0） Loop: TS R1, A1; JRN R1, Loop; (If (R1=1)then goto Loop) A1 = Lock; (A1) = 0; (置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; non-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_and_Test指令，也可实现对临界区的加锁与解锁： Repeat while !Dec_and_Test (s) do s++ critical section s++; non-critical section Until false; 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等。 一.信号量的使用(互斥与同步) 互斥：用于n个进程的临界段互斥，n进程共享一个信号量mutex,初值为1，任一进程Pi的结构为： P(mutex) V(mutex) 临界段 非临界段 repeat until false 同步：有P1、P2 两进程，必须在P1执行完S1语句