进程同步

进程同步

临界资源

对临界资源的访问必须需要互斥地进行
访问过程

1. 进入区。检查是否可以进入临界区。可以则设置访问临界区的标志
2. 临界区。访问临界资源的代码
3. 退出区。将访问临界区的标志清除
4. 剩余区

同步与互斥

同步也称为直接制约关系。指为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某个位置上协调他们的工作次序而等待、传递信息所产生的制约关系

互斥也成为简介制约关系。当一个进程进入临界区使用临界资源，另外一个进程必须等待占用临界资源的进程退出临界区后，才能去访问

同步机制的准则

1. 空闲让进
2. 忙则等待
3. 有限等待。保证有限时间内可以进入临界区
4. 让权等待。不能进入临界区应该立即释放处理器，防止进程忙等待

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

软件实现方法

1. 单标志法：违背空闲让进
2. 双标志先检查法：违背忙则等待
3. 双标志后检查法：两个进程同时想进入临界区时，会互相谦让。导致“饥饿”现象。
4. 皮特森算法Peterson’s Algorithm：结合单标志法和双标志后检查法。利用flag解决临界资源的互斥访问，利用turn解决饥饿现象。

硬件实现方法

1. 中断屏蔽

   关中断；
   临界区；
   开中断；

2. 硬件指令
   1. TestAndSet
      即采用原子操作
   2. Swap指令
      硬件方法不能实现让权等待

信号量机制

用以解决互斥和同步问题。标准原语wait(S)和signal(S)。记为P操作和V操作(对应荷兰语的pass和release)

实现同步

semaphore S = 0;
p1(){
    x;
    V(S)
}

p2(){
    P(S)
    x;
}

先执行P1，再执行P2

实现互斥

semaphore S = 1;
p1(){
    P(S)
    x;
    V(S)
}

p2(){
    P(S)
    x;
    V(S)
}

管程

管程是一组数据以及定义这组数据之上的对这组数据操作组成的软件模块。可实现同步和互斥(类比于抽象类)
组成

1. 局部于管程的共享结构数据说明
2. 对该数据结构进行操作的一组过程
3. 对局部于管程的共享数据设置初始值的语句

经典的同步问题

1. 生产者-消费者问题
2. 读写者问题
3. 哲学家进餐问题
4. 吸烟者问题