第二章 进程同步

基础概念

相关提炼内容见 process-synchronization。

进程同步的基本概念

• 临界区见 critical-section
  • 临界资源―一次仅允许一个进程使用的资源称为临界资源
    • 临界资源的访问过程 ↓
      • 进入区
      • 临界区
      • 退出区
      • 剩余区

do{
  entry section; // 进入区
  critical section; // 临界区
  exit section; // 退出区
  remainder section; // 剩余区
} while(true)

• 同步―直接制约关系
• 互斥―间接制约关系
• 为了防止两个进程同时进入临界区，同步机制应该遵循以下原则
  • 空闲让进
  • 忙则等待
  • 有限等待―对请求访问的进程，应保证能在有限时间内进入临界区
  • 让权等待―当进程不能进入临界区时，应立即释放处理器，防止进程忙等待

实现临界区互斥的基本方法

• 软件实现方法
  • 单标志法
  • 双标志法先检查
  • 双标志法后检查
  • Peterson’s Algorithm
• 硬件实现方法（低级方法，元方法）
  • 中断屏蔽方法（屏蔽中断，关中断）
  • 硬件指令方法
    • TestAndSet 指令
    • Swap 指令
    • 优点： 适用于任意数目的进程，而不管是单处理机还是多处理机；简单容易检验正确性
    • 缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待
• 信号量见 semaphore
  • 整型信号量
    • 一个用于表示资源数目的整型量 S

wait(S){
  while(S <= 0);
  S--;0
}
 
signal(S){
  S++;
}

• 记录型信号量

typedef struct{
int value;
struct process *L;
}semaphore;

• 相应的 wait(S) 和 signal(S)的操作如下
• wait(S)

void wait(semaphore S){ // 相当于申请资源
S.value--;
if(S.value < 0){
add this process to S.L;
block(S.L);
}
}

• signal(S)

void signal(semaphore S){ // 相当于释放资源
S.value++;
if(S.value <= 0){
remove a process P from S.L;
wakeup(P);
}
}

• 利用信号量实现同步

semaphore S = 0; // 初始化信号量
P1(){
x;		// x语句
V(S);   // 告诉进程2，语句x已经完成
}
P2(){
P(S);   // 检查语句x是否运行完成
y;  // 检查无误，运行y语句
}

• 利用信号量实现进程互斥

...
P(S);
critical section
V(S);
...

• 利用信号量实现前驱关系

管程

见 monitor。

经典同步问题

- 生产者消费者问题：有点像管道通信中的read 和 write
- 读者写者问题
- 哲学者进餐问题
- 吸烟者问题