概念

临界资源

类型：物理设备、可被进程共享的许多变量、数据等

临界区：访问临界资源的那段代码

临界资源的访问过程分成 4 部分：

1）进入区：进入区要检查能否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区

2）临界区：进程中访问临界资源的那段代码，又称临界段

3）退出区：将正在访问临界区的标志清除

4）剩余区：代码中的其余部分

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

同步（直接制约关系）

同步是为完成某种任务，多个进程需要在某些位置上协调工作次序而产生的制约关系

互斥（间接制约关系）

当一个进程进入临界区使用临界资源，另一进程必须等待。当占用临界资源的进程退出临界区后，另一进程才能访问此临界资源

遵循原则：

1）空闲让进：临界区空闲时，允许一个请求临界区资源的进程立即进入临界区

2）忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待

3）有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）

4）让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

互斥实现方法

软件实现方法

单标志法

设置一个公用整型变量 turn，用于指示被允许进入临界区的进程编号。进程在访问完临界区后将 turn 修改为另一个进程（每个进程进入临界区的权限只能被另一个进程赋予）

进入区：检验标志 turn 是否允许进程自身使用

退出区：将标志 turn 修改为另一进程

违反原则：若某个进程不再进入临界区，则另一个 进程也将无法进入临界区（违背"空闲让进”）

双标志法

设置一个布尔型数组 flag[ ] ，表示各进程进入临界区的意愿。进程进入临界区前先检查有无其他进程想进入临界区，若没有，则把自身对应的标志 flag 设为 true ，之后开始访问临界区

进入区：检查其他进程是否正在访问，若无，标记自身意愿

退出区：删除自身意愿

违反原则：并发时可能同时进入临界区（违背“忙则等待”）

双标志后检查

进入区：

1）先标记自身意愿

2）再检查其他进程是否正在访问，若无则访问临界区，反之则循环等待

退出区：删除自身意愿

违反原则：当两个进程同时都想进入临界区时，分别将标志值设置为 TRUE ，并同时检测对方的状态，发现对方也要进入临界区，发生死锁。（违背了“空闲让进”和“有限等待”原则）

Peterson 算法

进入区：

1）先设置自身意愿标志

2）再将 turn 设为对方 ID（谦让）

3）最后检查对方是否有意愿、是否trun为对方ID（看ID确定是否自己为最后谦让者）。若对方有意愿且 turn 为对方 ID 则对方访问临界区

退出区：删除自身意愿

违反原则：不满足条件时进程会一直等待（违反“让权等待”原则）

硬件实现方法

中断屏蔽法

进入区：关中断

退出区：开中断

缺点：

1）不适用于多处理机

2）只适用于操作系统内核进程，不适用于用户进程

硬件指令法

TestAndSet 指令

也称TS指令、TestAndSetLock指令、TSL指令

用硬件实现的、原子操作

使用一个 bool 变量作为锁

进入区：先检查原来是否上锁，且检查后无论原来是否上锁，都再次尝试上锁

退出区：解锁

违反原则： 暂时无法进入临界区的进程会占用CPU并循环执行TSL指令（违反“让权等待”原则）

Swap 指令

也称Exchange指令、XCHG指令

用硬件实现的、原子操作

逻辑与 TS 指令相同、违反“让权等待”原则

互斥锁

定义：

1）使用一个布尔变量作为临界区的锁

2）一个进程在进入临界区时获得锁，在退出临界区时释放锁

acquire(){
    while(!available);      //忙等待
    avilable = false;       //获得锁
}
release(){
    available = true;       //释放锁
}

函数acquire()获得锁，而函数release()释放锁。acquire()和release()是原子操作，由硬件机制完成

效果：等待期间不会切换进程上下文，会进行忙等（违反“让权等待”原则）。在多处理器系统中上锁时间很短，等待代价很低

信号量

信号量机制

信号量是一种变量，表示某种资源的数量。只能被wait(S)和signal(S)访问，记为 “ P 操作”和“ V 操作”

P 操作：申请一个资源，如果资源不够就阻塞等待
V 操作：释放一个资源，如果有进程在等待该资源，则唤醒一个进程

整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

代码表示：

// 1. 初始化
int S = 1; // 初始值为资源数量（最多能为几个进程同时提供服务）

// 2. wait
void wait(int S)
{
    while(S <= 0); // 资源不够，循环等待
    --S; // 使用资源时占有资源
}

// 3. signal
void signal(int S)
{
    ++S; // 使用完资源，释放资源
}

违反“让权等待”原则，会出现忙等

记录型信号量

除整型变量外，增加一个所有等待该资源进程的链表

代码表示：

value 初始值为资源数量（最多能为几个进程同时提供服务）

如果值为负数，说明队列中存在等待进程，需要执行唤醒进程的方法

// 1. 记录型信号量定义
typedef struct
{
    int value;
    struct process *L;
} semaphore;

// 2. wait
void wait(semaphore S)
{
    --S.value; // 先记录占用资源
    if(S.value < 0)
    {
        block(S.L); // 资源数量不足，阻塞
    }
}

// 3. signal
void signal(semaphore S)
{
    ++S.value; // 结束使用后，释放资源
    if(S.value <= 0)
    {
        wakeup(S.L);// 若有进程阻塞等待，则唤醒一个进程
    }
}

wait：如果剩余资源数不足，使用 block 原语使进程从运行态进入阻塞态，并放入阻塞队列中

signal：释放资源后，若有进程在等待资源，则使用 wakeup 原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态。

信号量实现进程互斥

1）设置互斥信号量mutex = 1

2）进入区使用 P 操作、退出区使用 V 操作

伪代码：

semaphore mutex = 1;

//P1与P2进行互斥操作
P1()
{
    P(mutex);
    // 临界区
    V(mutex);
}

P2()
{
    P(mutex);
    // 临界区
    V(mutex);
}

信号量实现进程同步

1）设置同步信号量S = 0

2）“前操作”在 V 操作之前

3）“后操作”在 P 操作之后

伪代码：

semaphore S = 0;

//P1和P2进行同步操作
//这里要求code1在code3之前完成
P1()
{
    //code1
    V(S);
    //code2
}

P2()
{
    P(s);
    //code3
}

经典同步问题

生产者-消费者问题

1.问题描述：

1）系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用

2）生产者、消费者共享一个初始为空、大小为n的缓冲区。

3）只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。

4）只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

5）缓冲区是临界资源，各进程必须互斥地访问。

2.分析：

同步关系：缓冲区没满，生产者生产。缓冲区没空，消费者消费。

互斥关系：各进程互斥访问缓冲区。

3.方案：

若进程互斥信号量P(mutex)与相邻的同步信号量P(empty)或P(full)互换顺序会导致死锁

V操作可以交换顺序

多生产者-多消费者问题

1.问题描述：

1）有一个盘子，每次只能向其中放入一个水果

2）爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子只吃盘子中的橘子，女儿只吃盘子中的苹果

3）只有盘子空时，爸爸或妈妈才可向盘子中放一个水果

4）仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果

2.分析：

同步关系：

1） 父亲将苹果放入盘子，女儿才能取苹果

2）母亲将句子放入盘子，儿子才能取橘子

3）只有盘子为空，父亲或者母亲才能放水果

互斥关系：对缓冲区(盘子)的访问要互斥的进行

3.方案：

当缓冲区大小大于1，必须设置互斥变量（无论大小是否为 1 尽量还是都设置互斥变量）

读者-写者问题

1.问题描述：

有读者和写者两组并发进程，共享一个文件

1）允许多个读者同时读

2）同时只允许一个写者写

3）写者完成写操作前，不允许其他读者读或写者写

4）写者执行写操作前，应让已有的读者和写者全部退出

2.分析：

互斥关系：写进程与读或写进程都存在互斥

3.方案：

1）rw 是写文件的互斥变量，在写操作前后与读操作前后都要有 rw 的 PV 操作

2）为了实现多个读者同时读，增加了 count 变量，使得第一个读者执行 rw 的 P 操作，最后一读者执行 rw 的 V 操作

3）因为 count 变量不是原子操作，所以需要添加 mutex 作为 count 的互斥变量

4）此时若源源不断有读者来读，则写者饥饿。P(w)实现写者能够排队，后续读者排在写者之后

哲学家进餐问题

1.问题描述：

1）圆桌上 5 名哲学家，每两个哲学家之间摆一根筷子，中间是一碗米饭

2）当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则等待

3）饥饿的哲学家只有同时拥有两根筷子才可以开始进餐，当进餐完毕后，放下筷子

2.分析：

5位哲学家与左右邻居对其中间筷子的访问是互斥关系，需要避免死锁

定义互斥信号量数组 chopstick[5]={1,1,1,1,1}

对哲学家按0~4编号，哲学家 i 左边的筷子编号为 i，右边的筷子编号为 (i+1)%5

引入一个“拿筷子”动作的互斥变量 mutex

3.方案：

哲学家只有同时拥有两个筷子才解锁互斥

管程

1）管程是一个资源管理模块，其中包含了共享资源的数据结构和对资源操作的方法

2）管程中包含条件变量，用于管理进程的阻塞和唤醒。其形式为 condition x；对它的操作仅有 wait 和 signal

理解：管程类似一个类，把对临界资源的操作进行封装，当进程要对资源进行操作时，只需调用管程的方法