2.3 进程同步

2.3.1 进程同步的概念

一、临界资源

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

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

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

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

1. 进入区：检查是否可以进入临界区，若可以进入，则设置正在访问临界资源的标志，以阻止其他进程进入临界区；

2. 临界区（临界段）：进程中访问临界区的一段代码；

3. 退出区：将正在访问临界资源的标志解除；

4. 剩余区：代码中的其他部分。

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

二、同步

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

三、互斥

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

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

互斥的原则

1. 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；

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

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

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

2.3.2 临界区互斥的实现

一、软件实现

1、单标志法

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

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将无法再次进入临界区，违背了“空闲让进”原则。

2、双标志先检查法

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

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;

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

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

3、双标志后检查法

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

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，又会相互等待造成饥饿，违背了“空闲让进”和“有限等待”原则。

4、Peterson's Algorithm

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

//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;

1. 首先设置自身想要访问临界区，并将当前访问权限交给对方。

2. 若此时对方也希望访问临界资源，则自身循环等待。

3. 当自身访问完临界区后，取消访问意愿标记。以便其它进程访问。

• 此算法利用flag[ ]实现了临界资源的互斥访问，并用turn解决了“饥饿”现象；

• 遵循了空闲让进、忙则等待和有限等待原则；

• 但是没有遵循让权等待原则（需要在CPU上不断循环检测）。

二、硬件实现

1、中断屏蔽方法

利用开关中断的方式实现

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

• 优点

  • 简洁、高效

• 缺点

  • 不适用于多处理机

  • 只适用于操作系统内核进程（开/关中断指令只能执行在内核态）

2、TestAndSet指令

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

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指令，导致“忙等”。

3、Swap指令

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

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指令相似。

2.3.3 锁

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

bool avialible; //锁是否可用

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

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

acquire与release必须是原子操作。

• 优点

  • 等待期间不用切换进程上下文，多核处理器中若上锁的时间很短，则等待代价很低

  • 常用于多处理器系统，一个核忙等，其它核正常工作，并快速释放临界区

• 缺点

  • 需要忙等，进程时间片用完才下处理机，违反“让权等待”

  • 不适用于单处理机系统，忙等的过程中不可解锁

2.3.4 信号量

信号量是一种功能较强的机制，可用于解决互斥与同步的问题。它只能被两个标准原语**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);       //若释放资源后可还有进程在等待，则唤醒该进程，使其从阻塞态变为就绪态
    }
}

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

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

1、进程互斥

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

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

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

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

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

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

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

2、进程同步

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

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

semaphore S = 0;

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

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

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

四、信号量机制实现前驱关系

前驱图

1. 需要为每一对前驱关系设置一个同步信号量；

2. 在前操作之后对相应的同步信号量执行V操作；

3. 在后操作之前对相应的同步信号量执行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;
    ...
}

2.3.5 管程

一、管程的定义和基本特征

什么是管程：

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

1. 局部于管程的共享数据结构说明；

2. 对该数据结构进行操作的一组过程；

3. 对局部于管程的共享数据设置初始值的语句；

4. 管程有一个名字。

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

管程的特征：

1. 局部于管程的数据只能被局部于管程的过程所访问；

2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；

3. 每次仅允许一个进程在管程内执行某个内部过程；

4. 每次只开放一个过程（由编译器实现）；

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可能会有无效操作