同步与互斥实现方法.pptx

利用处理机提供的特殊指令实现临界区加锁
单处理机系统常见硬件指令有:

Parbegin
A(amount){
disableInterrupt();
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_Set”指令。
该指令功能描述为:
Function Test_and_Set(Var target:boolean)
:boolean;
begin
Test_and_Set = target;
Target = true;
end;
二、“Swap”指令。
该指令功能描述为:
Procedure Swap(Var a,b:boolean);
Var temp:boolean;
begin
temp = a;
a = b;
b = temp;
end;
设Lock为全局布尔变量,利用Test&Set指令,即可实现对临界区的加锁与解锁:
Repeat
while Test&Set (lock) do skip
critical section
lock = false;
non-critical section
Until false;
“test&set”读后置1指令实例:
T&S Ri,Aj 解释为将(Aj)地址所指内存单元内容读到Ri寄存器中,同时将1置入Aj所指的内存单元中.
设Lock为临界段锁变量,则安排如下指令,即可实现加锁与解锁:*
临界段
非临界段
A1<=&Lock;(将Lock单元地址送A1寄存器。Lock单元初始值为0)
Loop:T&S R1,A1;
JRN R1,Loop; (If (R1=1)then goto Loop )
A1 <=&Lock;
(A1) <=0;(0置Lock内存单元)
设Lock为全局布尔变量(初值为假),每个进程设一个局部布尔变量Key。利用Swap指令,可实现对临界区的加锁与解锁。
Repeat
key = true;
repeat
Swap (lock, key);
until key = false;
critical section
lock = false;
non-critical section
Until false;
信号量
信号量机构:“信号量”、“P、V操作”。
信号量S为一整型变量:
P(S): While S≤0 do skip ;
S = S-1 ;
V(S):S = S+1;
P、V操作是两条原语,即保证P、V操作对变量S的访问是互斥操作。
一. 原语概念与实现
原语:指完成某种功能且不被分割或不被中断执行的操作序列。
原语可通过硬件实现不可中断性;或通过实现临界段的元方法达到不被中断。
实现临界段的元方法:
屏蔽中断(只用于单机)
加硬锁。