2.3 进程同步

2.3.1 进程同步的基本概念

2.3.1.1 进程同步

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

2.3.1.1 临界资源

进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源，两种资源共享方式为

• 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源
• 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

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

对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

do {
    /*
        进入区,负责检查是否可进入临界区，
        若可进入，则应设置正在访问临界资
        源的标志（可理解为“上锁”），以阻
        止其他进程同时进入临界区
    */
    entry section;      
    critical section;   //临界区,访问临界资源的那段代码
    exit section;       //退出去,负责解除正在访问临界资源的标志（可理解为“解锁”）
    remainder section;  //剩余区,做其他处理
} while(true)

临界区也可称为“临界段”,是进程中访问临界资源的代码段。

进入区和退出区是负责实现互斥的代码段.

2.3.1.2 进程互斥

当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程推出临界区后，另一经常才允许区访问次临界资源。为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

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

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

2.3.2.1 软件实现方法

2.3.2.1.1 单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

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

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

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

该算法可以实现“同一时刻最多只允许一个进程访问临界区”，单标志法存在的主要问题是：违背“空闲让进”原则。

2.3.2.1.2 双标志先检查法

算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = ture”意味着0 号进程P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i] 设为true，之后开始访问临界区。

bool flag[2];       //表示进入临界区意愿的数组
//刚开始设置为两个进程都不想进入临界区
flag[0] = false;    
flag[1] = false;

//P0进程
while(flag[1]);     //进入区
flag[0] = true;     //进入区
critical section;   //临界区
flag[0] = false;    //退出区
remainder section;  //剩余区

//P1进程
while(flag[0]);     //如果此时P0想进入临界区，P1就循环等待
flag[1] = true;     //标记为P1进程想要进入临界区
critical section;   //访问临界区
flag[1] = false;    //访问完临界区，修改标记为P1不想使用临界区
remainder section;

双标志先检查法优点：不用交替进入，可连续使用；主要问题是：违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

2.3.2.1.3 双标志后检查法

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

bool flag[2];       //表示进入临界区意愿的数组
//刚开始设置为两个进程都不想进入临界区
flag[0] = false;    
flag[1] = false;

//P0进程
flag[0] = true;     //进入区
while(flag[1]);     //进入区
critical section;   //临界区
flag[0] = false;    //退出区
remainder section;  //剩余区

//P1进程
flag[1] = true;     //标记为P1进程想要进入临界区
while(flag[0]);     //如果此时P0想进入临界区，P1就循环等待
critical section;   //访问临界区
flag[1] = false;    //访问完临界区，修改标记为P1不想使用临界区
remainder section;

因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

2.3.2.1.4 Peterson 算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。

bool flag[2];       //表示进入临界区意愿的数组
//刚开始设置为两个进程都不想进入临界区
flag[0] = false;    
flag[1] = false;
int turn = 0;       //turn表示优先让哪个进程进入临界区

//P0进程
flag[0] = true;     //进入区
turn = 1;           //进入区
while (flag[1] && turn == 1);   //进入区
critical section;   //临界区
flag[0] = false;    //退出区
remainder section;  //剩余区

//P1进程
flag[1] = true;     //表示自己想进入临界区
turn = 0;           //可以优先让对方进入临界区
while (flag[0] && turn == 0);   //对方详尽，且最后一次是自己礼让，那就循环等待
critical section;
flag[1] = false;    //访问完临界区，表示不想访问临界区
remainder section;

Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

2.3.2.2 硬件实现方法

2.3.2.2.1 中断屏蔽方法

利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

优点:简单、高效

缺点:不适用于多处理机;只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

2.3.2.2.2 TestAndSet指令

简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用c语言描述的逻辑

//布尔型共享变量lock表示当前临界区是否被加锁，true表示已加锁
bool TestAndSet(bool *lock){
    bool old;
    old = *lock;        //old用来存放lock原来的值
    *lock = true;       //无论之前是否已经加锁，都设置为true
    return old;         //返回lock原来的值
}

该指令实现进程互斥的算法描述为

while TestAndSet(&lock);    //上锁并检查
...     //临界区代码段
lock = false;   //解锁
...     //剩余区代码段

若刚开始lock是false，则TSL返回的old值为false，while循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TLS后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境；缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

2.3.2.2.3 Swap指令

有的地方也叫 Exchange指令，或简称XCHG指令。Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用c语言描述的逻辑

// 交换两个字的内容
void swap(boolean *a, boolean *b){
    boolean temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

Swap指令实现进程互斥的代码

key = true;
while(key != false)
    Swap(&lock, &key);
...     //进程的临界区代码段
lock = false;
...     //进程的其他代码

逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old变量上），再将上锁标记lock设置为true，最后检查old，如果old为 false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境；缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

2.3.3 信号量

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1 的信号量。只能被一对原语所访问：wait(S) 原语和signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S 其实就是函数调用时传入的一个参数。wait、signal 原语常简称为P、V操作（来自荷兰语proberen 和verhogen）。因此，做题的时候常把wait(S)、signal(S) 两个操作分别写为P(S)、V(S)

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

2.3.3.1 整型信号量

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

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

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

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

存在的问题：不满足“让权等待”原则，会发生“忙等”

2.3.3.2 记录型信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量

// 记录型信号量的定义
typedef struct{
    int value;          //剩余资源数
    struct process *L   //等待队列
}semaphore;

//某进程需要使用资源时，通过wait原语申请
void wait(semaphore S){
    S.value--;
    if (S.value < 0){
        /*
            如果剩余资源数不够，使用block原语使进程从
            运行态进入阻塞态，并把挂到信号量S 的等待
            队列（即阻塞队列）中
        */
        block(S.L)
    }
}

//进程使用完资源后，通过signal原语释放
void signal(semaphore S){
    S.value ++ ;
    if (S.value <= 0){.
        /*
            释放资源后，若还有别的进程在等待这种资源，则使用
            wakeup 原语唤醒等待队列中的一个进程，该进程从阻
            塞态变为就绪态
        */
        wakeup(S.L);
    }
}

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

1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
2. 设置互斥信号量mutex，初值为1
3. 在进入区P(mutex)——申请资源
4. 在退出区V(mutex)——释放资源

// 记录型信号量的定义
typedef struct{
    int value;          //剩余资源数
    struct process *L   //等待队列
}semaphore;

semaphore mutex = 1;

P1(){
    ...;
    P(mutex);       //使用临界资源前需要加锁
    ...;            //临界区代码段
    V(mutex);       //使用临界资源后需要解锁
    ...;
}

P2(){
    ...;
    P(mutex);       //使用临界资源前需要加锁
    ...;            //临界区代码段
    V(mutex);       //使用临界资源后需要解锁
    ...;
}

对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现。缺少P(mutex) 就不能保证临界资源的互斥访问。缺少V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。

2.3.3.4 利用信号量实现进程同步

进程同步：要让各并发进程按要求有序地推进。

1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
2. 设置同步信号量S, 初始为0
3. 在“前操作”之后执行V(S)
4. 在“后操作”之前执行P(S)

semaphore S = 0;

P1(){
    代码1;
    代码2;
    V(S);
    代码3;
}

P2(){
    P(S);
    代码4;
    代码5;
    代码6;
}

上述代码保证了代码4 一定是在代码2 之后执行

利用信号量实现前驱关系实际上可以理解为每两个之间的同步，即对每一对关系设置一个信号量，分别做上述操作即可

PV操作题目分析步骤：

1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
3. 设置信号量。并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

2.3.4 经典同步问题

2.3.4.1 生产者-消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）生产者、消费者共享一个初始为空、大小为n的缓冲区。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须互斥地访问。

图片.png

semaphore mutex = 1;        //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;        //同步信号量，表示空闲缓冲区的数量
semaphore full = 0;         //同步信号量，表示产品的数量，也即非空缓冲区的数量

producer (){
    while(1){
        生产一个产品;
        P(empty);           //消耗一个空闲缓冲区
        P(mutex);
        把产品放入缓冲区;
        V(mutex);
        V(full);            //增加一个产品
    }
}

consumer (){
    while(1){
        P(full);            //消耗一个产品（非空缓冲区）
        P(mutex);
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);           //增加一个空闲缓冲区
        使用产品;
    }
}

实现互斥是在同一进程中进行一对PV操作

实现两进程的同步关系，是在其中一个进程中执行P，另一进程中执行V

实现互斥的P操作一定要在实现同步的P操作之后,否则可能导致死锁。两个V操作顺序可以交换。

2.3.4.2 多生产者-多消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

[图片上传失败...(image-5a82e5-1631025230971)]

semaphore apple = 0;        //盘子中有几个苹果
semaphore orange = 0;       //盘子中有几个橘子
semaphore plate = 1;        //盘子中还可以放多少个水果

dad (){
    while(1){
        准备一个苹果;
        P(plate);
        P(mutex);
        把苹果放入盘子;
        V(mutex);
        V(apple);
    }
}

mom (){
    while(1){
        准备一个橘子;
        P(plate);
        P(mutex);
        把橘子放入盘子;
        V(mutex);
        V(orange);
    }
}

daughter (){
    while(1){
        P(apple);
        P(mutex);
        从盘中取出苹果;
        V(mutex);
        V(plate);
        吃掉苹果;
    }
}

son (){
    while(1){
        P(orange);
        P(mutex);
        从盘中取出橘子;
        V(mutex);
        V(plate);
        吃掉橘子;
    }
}

本题中的缓冲区大小为1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区，因此即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象

2.3.4.3 吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟)

图片.png

semaphore offer1 = 0;       //桌上组合一的数量
semaphore offer2 = 0;       //桌上组合二的数量
semaphore offer3 = 0;       //桌上组合三的数量
semaphore finish = 0;       //抽烟是否完成
int i = 0;                  //用于实现“三个抽烟者轮流抽烟”

provider (){
    while(1){
        if(i==0) {
            将组合一放桌上;
            V(offer1);
        } else if(i==1){
            将组合二放桌上;
            V(offer2);
        } else if(i==2){
            将组合三放桌上;
            V(offer3);
        }
        i = (i+1)%3;
        P(finish);
    }
}

smoker1 (){
    while(1){
        P(offer1);
        从桌上拿走组合一；卷烟；抽掉；
        V(finish);
    }
}

smoker2 (){
    while(1){
        P(offer2);
        从桌上拿走组合二；卷烟；抽掉；
        V(finish);
    }
}

smoker3 (){
    while(1){
        P(offer2);
        从桌上拿走组合三；卷烟；抽掉；
        V(finish);
    }
}

2.3.4.4 读者-写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前，应让已有的读者和写者全部退出。

semaphore rw=1;         //用于实现对共享文件的互斥访问
int count = 0;          //记录当前有几个读进程在访问文件
semaphore mutex = 1;    //用于保证对count􀨈量的互斥访问
//semaphore w = 1;      //用于实现"写优先"

writer (){
    while(1){
        //P(W);         //设置另一个互斥信号量,在无写进程时请求加入
        P(rw);          //写之前“加锁”
        写文件…
        V(rw);          //写完了“解锁”
        //V(W);         //设置另一个互斥信号量,恢复对共享文件的访问
    }
}

reader (){
    while(1){
        P(mutex);       //各读进程互斥访问count
        if(count==0)    //由第一个读进程负责
            P(rw);      //读之前“加锁”
        count++;        //访问文件的读进程数+1
        V(mutex);
        读文件…
        P(mutex);       //各读进程互斥访问count
        count--;        //访问文件的读进程数-1
        if(count==0)    //由最后一个读进程负责
            V(rw);      //读完了“解锁”
        V(mutex);
    }
}

若两个读进程并发执行，则count=o时两个进程也许都能满足if条件，都会执行P(rw)，从而使第二个读进程阻塞的情况。出现上述问题的原因在于对count变量的检查和赋值无法一气呵成，因此可以设置另一个互斥信号量来保证各读进程对count的访问是互斥的。

2.3.4.5 哲学家进餐问题

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

1. 关系分析。系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
2. 整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的事，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。
3. 信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1} 用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i 左边的筷子编号为i，右边的筷子编号为(i+1)%5。

semaphore chopstick[5]={1,1,1,1,1};     //初始化信号量
semaphore mutex = 1;                    //互斥地取筷子
Pi (){                                  //i号哲学家的进程
    while(1){
        P(mutex);                       //在取筷子前获得互斥量
        P(chopstick[i]);                //拿左
        P(chopstick[(i+1)%5]);          //拿右
        V(mutex);                       //释放取筷子的信号量
        吃饭…
        V(chopstick[i]);                //放左
        V(chopstick[(i+1)%5]);          //放右
        思考…
    }
}

2.3.4 管程

信号量机制存在的问题:编写程序困难、易出错1973年，Brinch Hansen首次在程序设计语言(Pascal)中引入了“管程”成分――一种高级同步机制。管程是一种特殊的软件模块，有这些部分组成:

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

管程的基本特征:

• 局部于管程的数据只能被局部于管程的过程所访问;
• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
• 每次仅允许一个进程在管程内执行某个内部过程。