基本概念

1. 临界资源：一次仅允许一个进程使用的资源
2. 访问临界资源的那段代码称为临界区
3. 临界资源的访问过程：进入区、临界区、退出区、剩余区
4. 同步
   如何理解：假设有A、B两个进程，B进程需要A进程提供数据x，并且由单缓冲区传送。则缓冲区中空时，B会被阻塞；当A送数据x进缓冲区，B运行。——A、B进程的这种制约（合作）关系就是同步
5. 互斥
   如何理解：只需要记住临界资源只能有一个进程占用（此时在临界区），其他的进程必须等待。只有等该进程退出临界区，其他进程才能访问
6. 同步机制准则
   1. 空闲让进
   2. 忙则等待
   3. 有限等待
   4. 让权等待

临界区互斥方法

软件实现方法

单标志法

违背了空闲让进的原则，容易造成资源利用不充分

互斥解释：假设p1进程执行了进入区代码（但是它又不用），p0进程发现p1想用，就无法进入临界区了——“占着茅坑不拉s”

// P0进程
while(turn!=0);
critical section;
turn=1;
remainder section;
// P1进程
while(turn!=1); // 进入区
critical section; // 临界区
turn = 0; // 退出区
remainder section; // 剩余区
1
2
3
4
5
6
7
8
9
10

双标志法先检查

优点：不用交替进入，可连续使用
缺点：违背了忙则等待的原则

互斥解释：pi执行了循环发现pj不用，就想将标志改成了true（但是还没改），此时pj就判断了对方是否想用（pi还没改），此时就会造成双方的flag都改成true

// Pi 进程
while(flag[j]); // ①
flag[i]=TRUE; // ③
critical section;
flag[i] = FALSE;
remainder section;
// Pj 进程
while(flag[i]); // ② 进入区
flag[j] =TRUE; // ④ 进入区
critical section; // 临界区
flag[j] = FALSE; // 退出区
remainder section; // 剩余区
1
2
3
4
5
6
7
8
9
10
11
12

双标志法后检查

优点：解决了忙则等待的原则
缺点：违反了空闲让进和有限等待的原则

互斥解释：这就是我们狭路遭遇，你们都想过去（并发执行了第一句），但是你们发现对方想过去（都停在了第二句），然后就都过不去了

// Pi进程
flag[i] =TRUE;
while(flag[j]);
critical section;
flag[i] =FLASE;
remainder section;
// Pj进程
flag[j] =TRUE; // 进入区
while(flag[i]); // 进入区
critical section; // 临界区
flag [j] =FLASE; // 退出区
remainder section; // 剩余区
1
2
3
4
5
6
7
8
9
10
11
12

Peterson’s Algorithm

优点：利用flag解决临界资源的互斥访问，利用trun解决了“饥饿”问题，遵循了空闲让进、忙则等待和有限等待的原则
缺点：违反了让权等待的原则

// Pi进程
flag[i]=TURE; turn=j;
while(flag[j]&&turn==j);
critical section;
flag[i]=FLASE;
remainder section;
// Pj进程
flag[j] =TRUE;turn=i; // 进入区
while(flag[i]&&turn==i); // 进入区
critical section; // 临界区
flag[j]=FLASE; // 退出区
remainder section; // 剩余区
1
2
3
4
5
6
7
8
9
10
11
12

硬件实现方法