同步与互斥实现方法

1、第八讲第八讲 同步与互斥实现方法同步与互斥实现方法 目的与要求：目的与要求：理解互斥问题的硬件实现方理解互斥问题的硬件实现方法；掌握信号量机制及使用它解决进程同法；掌握信号量机制及使用它解决进程同步互斥问题的方法。步互斥问题的方法。 重点与难点重点与难点：信号量实现及使用。：信号量实现及使用。 作业：作业：1，2，4，13（没做（没做7题请补做）题请补做）实现临界段的硬件方法利用处理机提供的特殊指令实现临界区加锁利用处理机提供的特殊指令实现临界区加锁单处理机系统常见硬件指令有单处理机系统常见硬件指令有: :一一. .屏蔽中断屏蔽中断Parbegin A(amount) disableInter

2、rupt(); R1=balance; R2=amount; R1=R1+R2; balance=R1; enableInterrupt(); ; B(amount) disableInterrupt(); R1=balance; R2=amount; R1=R1-R2; balance=R1; enableInterrupt(); ;Parend;多处理机系统硬件指令有多处理机系统硬件指令有: :一、一、“Test_and_SetTest_and_Set”指令。指令。该指令该指令功能功能描述为：描述为：Function Test_and_Set（Var target：boolean） :bo

3、olean；beginTest_and_Set = target；Target = true；end；二、二、“SwapSwap”指令。指令。该指令该指令功能功能描述为：描述为：Procedure SwapProcedure Swap（Var a,bVar a,b：booleanboolean）；）；Var tempVar temp：booleanboolean；beginbegintemp = atemp = a；a = ba = b；b = tempb = temp；endend；设设LockLock为全局布尔变量，利用为全局布尔变量，利用Test&SetTest&Set指

4、令，即可实现对临界区的加锁与解锁：指令，即可实现对临界区的加锁与解锁：Repeat while Test&Set (lock) do skip critical section lock = false; non-critical sectionUntil false;“test&settest&set” 读后置读后置1 1指令实例：指令实例：T&S Ri,Aj T&S Ri,Aj 解释为将解释为将(Aj)(Aj)地址所指内地址所指内存单元内容读到存单元内容读到RiRi寄存器中寄存器中, ,同时将同时将1 1置入置入AjAj所指的内存单元中所指的内存单元

5、中. .设设LockLock为临界段锁变量，则安排如下指令，为临界段锁变量，则安排如下指令，即可实现加锁与解锁：即可实现加锁与解锁：* *临界段非临界段非临界段 A1A1&Lock;&Lock;（将（将LockLock单元地址送单元地址送A1A1寄存器。寄存器。LockLock单元初始值为单元初始值为0 0）Loop:T&S R1,A1;Loop:T&S R1,A1; JRN R1,Loop; (If (R1=1)then goto JRN R1,Loop; (If (R1=1)then goto Loop )Loop )A1 =&Lock;A1 =&a

6、mp;Lock;(A1) =0;(0(A1) =0;(0置置LockLock内存单元内存单元) )设设LockLock为全局布尔变量（初值为假），每个进程为全局布尔变量（初值为假），每个进程设一个局部布尔变量设一个局部布尔变量KeyKey。利用。利用SwapSwap指令，可实指令，可实现对临界区的加锁与解锁。现对临界区的加锁与解锁。Repeat key = true; repeat Swap (lock, key); until key = false; critical section lock = false; non-critical sectionUntil false;信号量信号量机

7、构：信号量机构：“信号量信号量”、“P P、V V操作操作”。 信号量信号量S S为一整型变量：为一整型变量： P(S): While S0 do skip P(S): While S0 do skip ； S = S-1 S = S-1 ； V V（S S）：）：S = SS = S1 1；P P、V V操作是两条原语，即保证操作是两条原语，即保证P P、V V操作对变量操作对变量S S的访问是互斥操作。的访问是互斥操作。一. 原语概念与实现原语：原语：指完成某种功能且不被分割或不指完成某种功能且不被分割或不被中断执行的操作序列。被中断执行的操作序列。原语可通过硬件实现不可中断性；或通原语可

8、通过硬件实现不可中断性；或通过实现临界段的元方法达到不被中断。过实现临界段的元方法达到不被中断。实现临界段的元方法实现临界段的元方法: :屏蔽中断屏蔽中断( (只用于单机只用于单机) )加硬锁。加硬锁。下面我们用屏蔽中断方法实现下面我们用屏蔽中断方法实现P P（s s）和）和V V（s s）的原子性。）的原子性。P P（s s） DisableInterrupt();DisableInterrupt();while while （s0s0）do do enableInterrupt();enableInterrupt();DisableInterrupt();DisableInterrupt(

9、); ；s = s - 1s = s - 1；enableInterrupt();enableInterrupt(); V V（s s） DisableInterrupt();DisableInterrupt(); s = s +1s = s +1；enableInterrupt();enableInterrupt(); 二、信号量的使用(互斥与同步)互斥：互斥：用于用于n n个进程的临界段互斥，个进程的临界段互斥，n n进程共享一进程共享一个信号量个信号量mutex,mutex,初值为初值为1 1，任一进程，任一进程PiPi的结构为：的结构为： P(mutex)V(mutex)临界段非临界段

10、repeatUntil false同步：同步：有有P1P1、P2 P2 两进程，必须在两进程，必须在P P1 1执行完执行完S1S1语句后，语句后，P2P2才能执行才能执行S2S2。需同步的两进程共享。需同步的两进程共享信号量信号量synchsynch，初值为，初值为0 0。Parbegin P2: begin P1: beginS1;V(synch);end; P(synch);S2;end;Parend;S1S2S3S4S5S6S7请用并行语句和PV操作描述操作系统实现信号量时与进程调度相结合，操作系统实现信号量时与进程调度相结合，消除忙等待现象。消除忙等待现象。原则是：原则是：在在P P

11、操作循环等待的地方加入放弃操作循环等待的地方加入放弃处理机处理机/ /挂入等待队列动作，在挂入等待队列动作，在V V操作时，操作时，从等待队列中摘取进程变为就绪态。从等待队列中摘取进程变为就绪态。（P P、V V原语本身的互斥操作通过屏敝中断原语本身的互斥操作通过屏敝中断或为信号量加硬锁实现）或为信号量加硬锁实现）三.信号量的具体实现1 1、信号量定义、信号量定义 type Semaphore=recordtype Semaphore=record value:integer; value:integer; 一个数型变量一个数型变量 L:List of process;L:List of process;一个一个PCBPCB队列队列 end;end;2 2、P P操作操作 P(S):S.Value=S.value P(S):S.Value=S.value 1;1; If S.value0 then If S.value0