2.3_同步与互斥

进程同步的概念

临界资源

临界资源指一个时间段内只允许一个进程使用的资源。

例如物理设备、内存缓冲区等都是临界资源。

在每个进程中，访问临界资源的那部分代码被称为临界区。对临界资源的访问，可以分为四个阶段：

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

进入区：检查是否可以进入临界区，若可以进入，则设置正在访问临界资源的标志，以阻止其他进程进入临界区；
临界区（临界段）：进程中访问临界区的一段代码；
退出区：将正在访问临界资源的标志解除；
剩余区：代码中的其他部分。

进入区和退出区负责实现互斥。

实现互斥的逻辑代码的讲解

同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

互斥

对临界资源的访问，必须互斥地进行。

互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后, 另一个进程才能去访问临界资源。

互斥的原则

空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

举例：

题1：为什么需要进程同步

选C：

因为进程同步的是管理多个程序运行，而这些进程都是异步的

题2：进程之间的关系

进程B必须在A写入后才能读取，体现互斥（进程之间争夺互斥资源产生的制约）

进程B和A存在数据交换，体现同步（进程之间需要交换信息和，相互等待而产生的制约）

题3：临界区和临界资源的判断

临界资源是互斥共享，一次只能给一个进程使用

题4：临界资源与互斥

视频讲解

共享资源,是共享资源就要互斥，不是就不用
不同进程之间互不影响

题5：对同步/互斥设计准则的理解

解析：

1：体现了忙则等待

2：体现了空闲让进

3：体现了有限等待

4：体现了让权等待

临界区互斥的实现

软件实现

单标志法

视频讲解:单标志法

一个进程在访问完临界区后会把使用临界区资源的权限转交给另一个进程，即每个进程进入临界区的权限只能由另一个进程赋予

int turn=0;         //公用变量，表示当前允许进入临界区的进程号

// P0进程
while (turn != 0);  //进入区
critical section;   //临界区
turn = 1;           //退出区
remainder section;  //剩余区

// P1进程
while (turn != 1);  //进入区
critical section;   //临界区
turn = 0;           //退出区
remainder section;  //剩余区

该算法可以实现同一时刻只允许一个进程进入临界区。

但是两个程序必须轮流进入临界区，若1不再进入临界区，则0将无法再次进入临界区，违背了“空闲让进”原则。

双标志先检查法

视频讲解：双标志先检查法

设置一个数组，相应元素表示进程访问临界资源的意愿。

bool flag[2];       //表示进入临界区意愿
flag[0] = false;
flag[1] = false;

//P0进程
while (flag[1]);    //若P1希望进入临界区，则P0循环等待
flag[0] = true;     //标记P0希望进入临界区
critical section;   //访问临界区
flag[0] = false;    //标记P0不再希望使用临界区
remainder section;

//P1进程
while (flag[0]);    //若P0希望进入临界区，则P1循环等待
flag[1] = true;     //标记P1希望进入临界区
critical section;   //访问临界区
flag[1] = false;    //标记P1不再希望使用临界区
remainder section;

此算法不需要轮流进入临界区，可以连续访问临界资源。

在检查对方意愿和切换自己意愿之间有时间差，可能出现同时访问临界区，违反了“忙则等待”原则。

双标志后检查法

相比于双标志先检查法，此算法先修改自身意愿，再进行检查。

bool flag[2];       //表示进入临界区意愿
flag[0] = false;
flag[1] = false;

//P0进程
flag[0] = true;     //标记P0希望进入临界区
while (flag[1]);    //若P1希望进入临界区，则P0循环等待
critical section;   //访问临界区
flag[0] = false;    //标记P0不再希望使用临界区
remainder section;

//P1进程
flag[1] = true;     //标记P1希望进入临界区
while (flag[0]);    //若P0希望进入临界区，则P1循环等待
critical section;   //访问临界区
flag[1] = false;    //标记P1不再希望使用临界区
remainder section;

这一算法解决了“忙则等待”的问题，但是若两个进程同时标记为true，又会相互等待造成饥饿，违背了“空闲让进”和“有限等待”原则。

Peterson's Algorithm

视频讲解：Peterson算法

综合了单标志法和双标志后检查法。

//P0进程
flag[0] = true;              //标记P0希望进入临界区
turn = 1;                    

while (flag[1]&&turn==1);    //若P1希望进入临界区，则P0循环等待
critical section;            //访问临界区
flag[0] = false;             //标记P0不再希望使用临界区
remainder section;

//P1进程
flag[1] = true;              //标记P1希望进入临界区
turn = 0;

while (flag[0]&&turn==0);    //若P0希望进入临界区，则P1循环等待
critical section;            //访问临界区
flag[1] = false;             //标记P1不再希望使用临界区
remainder section;

首先设置自身想要访问临界区，并将当前访问权限交给对方。
若此时对方也希望访问临界资源，则自身循环等待。
当自身访问完临界区后，取消访问意愿标记。以便其它进程访问。

此算法利用flag[ ]实现了临界资源的互斥访问，并用turn解决了“饥饿”现象；
遵循了空闲让进、忙则等待和有限等待原则；
但是没有遵循让权等待原则（需要在CPU上不断循环检测）。

举例：Peterson算法的考察

硬件实现

中断屏蔽方法

利用开关中断的方式实现

视频讲解：中断屏蔽

...
关中断 //关中断后不允许当前进程被中断
临界区
开中断
...

优点
- 简洁、高效
缺点
- 不适用于多处理机
- 只适用于操作系统内核进程（开/关中断指令只能执行在内核态）

TestAndSet指令

简称TS指令，或TSL（TestAndSetLock）指令。

视频讲解：TS/TSL指令

TSL指令是用硬件实现的，执行的过程不允许被中断。以下是其C语言逻辑：

bool lock;                        //共享变量表示临界资源是否上锁

bool TestAndSet(bool *lock){
    bool old;
    old = *lock;
    *lock = true;                //无论之前是否上锁，将lock设置为true
    return old;                  //返回之前lock的值
}

while (TestAndSet (&lock));      //若可以进入临界区，则进入循环
critical section;
lock = false;                    //为临界资源解锁
remainder section;

优点
- 实现简单
- 适用于多处理机环境
缺点
- 不满足让权等待原则，暂时无法进入临界区的资源仍然会占用CPU并循环执行TS指令，导致“忙等”。

Swap指令

也称为Exchange指令，或简称XCHG指令。

视频讲解：SWAP指令

Swap指令是用硬件实现的，执行的过程不允许被中断。以下是其C语言逻辑：

bool lock;

Swap(bool *a, bool *b){
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

bool old = true;                //局部变量，存放之前lock的值
while (old == true){
    Swap(&old, &lock)
}
critical section;
lock = false;                   //解锁临界资源
remainder section;

其原理、优缺点实际上都与TS指令相似。

锁

视频讲解：锁

也称为“自旋锁”，解决临界区最简单的方法就是锁。进程在进入临界区时获得锁，在退出临界区时释放锁。

bool avialible; //锁是否可用

//获得锁
acquire(){
    while(!available)
        ;				//忙等锁
    available = false;	//获得锁
}

//释放锁
release(){
    available = true;	//释放锁
}

acquire与release必须是原子操作。

优点
- 等待期间不用切换进程上下文，多核处理器中若上锁的时间很短，则等待代价很低
- 常用于多处理器系统，一个核忙等，其它核正常工作，并快速释放临界区
缺点
- 需要忙等，进程时间片用完才下处理机，违反“让权等待”
- 不适用于单处理机系统，忙等的过程中不可解锁

信号量

信号量是一种功能较强的机制，可用于解决互斥与同步的问题。它只能被两个标准原语wait(S)和signal(S)访问，也被记作“P操作”和“V操作”。

在荷兰文中，通过叫passeren，释放叫vrijgeven，PV操作因此得名

视频讲解：信号量是什么以及如何修改信号量

整形信号量

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

与普通整型变量相比，信号量只有三种操作：初始化、P操作、V操作

视频讲解：整形信号量

int S = 1;                //初始化整型信号量，表示当前系统中可用资源数量

void wait(int S){         //wait原语，相当于进入区
    while (S <= 0);       //若资源不够，则一直等待
    S = S-1;              //若资源够，则占用一个资源
}

void signal(int S){       //signal原语，相当于退出区
    s = S+1;              //释放资源
}

由于P操作中资源不够时会一直循环，所以不满足让权等待，会发生“忙等”。

记录型信号量

视频讲解：记录型信号量

typedef struct {
    int value;            //剩余资源数
    struct process *L;    //等待队列
} semaphore;

在记录型信号量中，除了代表资源数量的value之外，还有一个进程链表L

void wait (semaphore S){
    S.value--;
    if (S.value < 0){
        block(S.L);        //若资源数量不足，则使用block原语将进程阻塞，并加入等待队列之中
    }
}

void signal (semaphore S){
    S.value++;
    if (S.value <= 0){
        wakeup(S.L);       //若释放资源后可还有进程在等待，则唤醒该进程，使其从阻塞态变为就绪态
    }
}

此机制遵循了让权等待原则，不会发生“忙等”。

记录型信号量是绝对的重点，要求能手搓代码

用信号量机制实现进程同步、互斥

进程互斥

视频讲解：信号量实现进程互斥

设置互斥信号量mutex，初值为1。

semaphore mutex = 1;        //这里可以直接这么写

P1(){
    ...
    P(mutex);               //申请进入临界区
    critical section;
    V(mutex);               //释放资源
    ...
}

P2(){
    ...
    P(mutex);
    critical section;
    V(mutex);
    ...
}

可以理解为此信号量表示进入临界区的名额，并且只有一个。

需要为不同的临界资源设置不同的互斥信号量；

P、V操作必须成对出现。

进程同步

视频讲解：信号量实现进程同步

进程同步：让各并发进程按照一定顺序进行

设置同步信号量S，初值为0；

semaphore S = 0;

P1(){
    CODE1;
    CODE2;
    V(S);
    CODE3;
}

P2(){
    P(S);
    CODE4;
    CODE5;
    CODE6;
}

只有CODE1、2执行完毕，且进行了V操作之后，进程2中的P操作才不会阻塞，并且能够继续执行下去。

信号量机制实现前驱关系

前驱图

需要为每一对前驱关系设置一个同步信号量；
在前操作之后对相应的同步信号量执行V操作；
在后操作之前对相应的同步信号量执行P操作。

上面简称为“前V后P”,在实际解题时，每一对前驱关系都是一个进程同步问题

P1(){
    ...
    S1;
    V(a);
    V(b);
    ...
}

P2(){
    ...
    P(a);
    S2;
    V(c);
    V(d);
    ...
}

P3(){
    ...
    P(b);
    S3;
    V(g);
    ...
}

P4(){
    ...
    P(c);
    S4;
    V(e);
    ...
}

P5(){
    ...
    P(d);
    S5;
    V(f);
    ...
}

P6(){
    ...
    P(e);
    P(f);
    P(g);
    S6;
    ...
}

举例：

题1：信号量与进程数之间关系

互斥量

互斥量初值一般为1，表示临界区只允许1个进程进入，从而实现互斥

互斥量等于0时，表示临界区已有1个进程进入，临界区外无等待进程

互斥量小于0时，表示临界区中有1个进程，临界区外等待的进程数量等于互斥量的绝对值

资源量

资源量初值可以是任何数，表示可用的资源数

资源量小于0，表示所有进程已用完，等待的进程数就是资源量的绝对值

题2：信号量与进程联系

解：每次允许2个，所以信号量初始值为2，同时有3个进程，所以可能有1个进程在临界区等待，所以最小值是1。所以答案是A

题3：信号量与进程之间关系

分析：

唤醒另一个进程，但只是唤醒，说明这个进程要么在临界区，要么在临界区外等待，所以信号量的值小于等于0

题4：不同同步机制的比较

解析

A：Peterson方法

while(1) {
    turn = j;    // 表示谦让给对方
    flag[i] = true;    // 表示自己希望进入
    while(turn == j && flag[j] == true)    // 对方也希望进入并且自己还把机会谦让给对方了
    // 临界区
    flag[i] = false;
    // 剩余区
}

Peterson方法可以实现
空闲让进
忙则等待
有限等待
但不能实现让权等待，因为是while循环就算无法获取临界资源也会占用CPU

B:swap指令

void swap(boolean *a, boolean *b) {
        boolean tmp = *a;
        *a = *b;
        *b = tmp;
}

对于每个临界资源，Swap指令为其设置一个全局布尔变量lock，其初值为FALSE。
在每个进程中还会设置一个局部布尔变量key，其初值为TRUE。
有进程在临界区时，重复交换和检查过程，直到临界区里的进程退出

do {
    key = true;
    do {
        swap(&lock, &key);
    }while(key == true);
    // 临界区
    lock = false;
    // 剩余区
}while(true);

swap可以实现空闲让进
但是swap不能实现让权等待，因为swap其实是硬件实现，所以会一鼓作气执行完，这就意味着不会中断，那么就不能实现让权等待

C: 信号量方法

typedef struct {
    int value;  //表示资源的数量
    struct process *L;  //一个链表，用来链接所有等待当前资源的进程
}semaphore;
void wait(semaphore S) {
    S.value--;  //表示申请一个资源
    if(S.value < 0){ //如果进程已经使用完了
        将这个进程加到当前信号量S相应的阻塞队列中
        block(S.L); //自我阻塞，放弃处理机，并且加入对应资源的阻塞队列中
    }   
}
void signal(semaphore S) {
    S.value++;  //表示对应资源可以申请的数量增加1
    if(S.value <= 0) {  // 如果当前资源依然在被需求，仍有等待该进程的资源被阻塞
        将S.L中第一个被阻塞的进程移除
        wakeup(S.L) //唤醒S.L中第一个被阻塞的进程。与上面移除对应，从阻塞态转变为就绪态
    }
}

信号量是同时满足了同步/阻塞的四种要求

D: TSL指令

boolean TSL(boolean *lock){
    boolean old = *lock;
    *lock = true;
    return old;
}
do {
    while(TSL(&lock));  //判断当前临界资源是否可以使用
    临界区
    lock = false;
    剩余区
}(true)

TSL也可以满足闲则让进，但和B的swap一样,TSL也是由机器代码实现，所以一口气执行完，所以不会中途退出，也就不能满足让权等待

题5 信号量的使用

管程

管程的定义和基本特征

什么是管程：

管程是一种特殊的软件模块，由这些部分组成:：

局部于管程的共享数据结构说明；
对该数据结构进行操作的一组过程；
对局部于管程的共享数据设置初始值的语句；
管程有一个名字。

这里“过程”其实就是函数

管程的特征：

局部于管程的数据只能被局部于管程的过程所访问；
一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
每次仅允许一个进程在管程内执行某个内部过程；
每次只开放一个过程（由编译器实现）；
可以在管程中设置条件变量和等待/唤醒操作以解决同步问题。

类似于Java中的实体类封装，只能用类提供的方法来修改内部变量

例：用管程实现生产者消费者问题

monitor ProducerConsumer{
    condition full, empty;
    int count = 0;
    
    void insert(Item item){
        if (count == N){
            wait(full);
        }
        count++;
        
        insert_item (item);
        
        if (count == 1){
            signal(empty);
        }
    }
    
    void remove(){
        if (count == 0){
            wait (empty);
        };
        count--;
        
        if (count == N-1){
            signal(full);
        }
        
        return remove_item();
    };
}

producer(){
    while (1){
        Item itme = 生产产品;
        ProducerConsumer.insert(item);
    }
}

consumer(){
    while (1){
        Item itme = ProducerConsumer.remove();
        消费产品
    }
}

附：Java中实现管程

static class monitor{
    private Item buffer[] = new Item[N];
    private int count = 0;
    
    public synchronized void insert(Item item){
        ......
    }
}

通过synchronized关键字即可实现类似的功能

条件变量

条件变量用于进程同步

如下图中定义了a、b、c三个条件变量

可以简单理解为资源的等待队列，一个条件变量代表一种阻塞的原因
条件变量的调用使用signal/wait
条件变量无法实现互斥，实际使用一般与锁配合使用

与信号量的区别：

	信号量	条件变量
是否有值	有，表示资源数，也有等待队列	无，仅仅是一个等待队列
操作	P、V	wait、signal
	V操作会累计值	signal可能会有无效操作