操作系统互斥的七种算法

硬件

1.单标记法：
设置一个标记turn表示谦让，访问临界资源前，检查是否被谦让，每次访问完，将临界资源谦让出去：

//检查
while(turn==1);
//访问
TODO
//谦让
turn=1;

缺陷：若让出后，P1不用，则P0永远不能用。所以只适合P0->P1->P0->P1循环。

2.双标记先检查法：
双标记指的是flag[2]表示想访问，其中flag[0]=1;表示P0想用；flag[1]=1;表示P1想用。
每次先检查后上锁。

//检查
while(flag[1]==1);
//上锁
flag[0]=1;
//访问
TODO
//开锁
flag[0]=0;

缺陷：由于检查和上锁不能一气呵成，所以在检查完之后发生时间片轮转，容易同时访问临界区。

3.双标记后检查法：
每次先上锁后检查。

//上锁
flag[0]=1;
//检查
while(flag[1]==1);
//访问
TODO
//开锁
flag[0]=0;

缺点：同上，容易造成死锁。

4.PeterSon算法：
综合单标记法和双标记法（三个标记），有turn表示谦让,flag[2]表示想访问，其中flag[0]=1;表示P0想用；flag[1]=1;表示P1想用。

//表示想用，再表示谦让
flag[0]=1；
turn=1;
//检查
while(flag[1]==1&&turn=1);//他想用，且我谦让了
//访问
TODO
//表示不想用
flag[0]=0;

缺点：没有实现让权等待。

软件

5. TestAndSet
   将检查和上锁一气呵成，bolck表示上锁。

TestAndSet(bool &lock)//检查和上锁一气呵成
{
bool old=lock;//先检查
lock=true；//后上锁
return old;
}


//先检查，后上锁
while(TestAndSet(bool &lock)==true);
//访问
TODO
//开锁
lock=false；

缺点：没有实现让权等待。

信号量

6.整形信号量
用整形数S表示资源数。（先检查后上锁）

 wait(S)
 {
 //检查
 while(S<=0);
 //占用资源
 S--;
 //访问
 TODO
 }
 signal(S)
 {
 //释放资源
 S++;
}

缺点：没有实现让权等待。

8.记录型信号量
记录可以将进程挂起，实现让权等待。（先上锁后检查）

typedef Struct{
int value;//资源剩余数
Struct process *L//进程
}semaphore;//信号量

P(semaphore S){
//占用资源
S.value--;
//检查,如果没资源则挂起
if(S.value<0)
	bolck(S.L);
}

V(semaphore S){
//释放资源
S.value++;
//检查是否还有阻塞的进程
if(S.value<=0)//因为value<=0表明释放后仍没有空闲资源，即一定还有进程被阻塞，所以要唤醒
	weakup(S.L);
}

同步互斥：

同步先V后P；互斥先P后V。