zhouqijie

进程的互斥与同步

死锁和饥饿问题：

在资源有限的系统上并发的多个进程之间可能存在资源争用的问题，而原本毫无关系也并不互相通信的进程间对资源的竞争，对引发两种极端情况：死锁和饥饿。

一组进程均只占有部分所需资源而无法继续运行，陷入阻塞。
即这一组进程集合中每个进程都死等集合中其他进程占有的资源，最终这一组进程都陷入永远等待的状态。

进程被调度程序长期忽视而分配不到CPU执行。

互斥和同步：

若干进程因相互竞争独占性的资源而产生的竞争制约关系称为互斥(Mutual Exclusion)。

为完成共同任务的并发进程基于某个条件来协调其运行进度、执行次序而等待、传递信号或消息而产生的协作制约关系称为同步(Synchronization)。

互斥也是一种特殊的同步–以一定次序协调地使用共享资源。



1、与时间有关的错误

并发进程可以是无关的，也可以是有关的。

无关的并发进程是指进程分别运行在不同的数据集上，一个进程的执行与其他进程的进展无关。

反之如果两个进程共享了数据集，则一个进程的执行可能影响另一个进程的结果，即两个进程存在制约关系。对于一组共享了数据集的并发进程，执行的相对速度无法控制，就会出现所谓的时间相关错误。



2、临界资源和临界区

系统中如果存在多个进程共享各种资源。然而某些资源在某一时刻只能允许一个进程使用（例如打印机等硬件和队列等数据结构），如果有多个进程同时去使用这类资源就会造成混乱。因此必须保护这些资源，避免多个进程同时访问。

这类在某时间内只能允许一个进程使用的资源称为临界资源，访问临界资源的代码段称为临界区(Critical Section)。

几个进程如果共享同一临界资源，他们必须以互斥的方式使用这个临界资源，即当一个进程正在使用某个临界资源时且尚未使用完毕时，其他进程必须延迟对该资源的操作；当使用该资源的进程释放该资源时，其他进程才可以使用该资源。

  1. 一次至多一个进程能进入临界区执行。
  2. 如果已有进程在临界区，其他试图进入的进程应该等待。
  3. 进入临界区的进程应该在有限时间内退出以便其他进程进入。

A.用软件方法管理临界区：

用软件方法支持在共享内存的单CPU或者多CPU系统中实现进程并发，实施依据是内存访问级别的基本互斥性。

1981年G.L.Perterson提出了一种巧妙的算法解决了进程互斥进入临界区的问题。

//Perterson算法
bool flag[2] = {false, true}; //是否有意访问临界资源    
int turn;   
void P0(){
    while(true){
        flag[0] = true;
        turn = 1;
        while(flag[1] && turn == 1);//空循环
        //[临界区]
        //...
        flag[0] = false;
    }
}
void P1(){
    while(true){
        flag[1] = true;
        turn = 0;
        while(flag[0] && turn == 0);//空循环
        //[临界区]
        //...
        flag[1] = false;
    }
}

现在很少用软件算法实现临界区管理问题，但是这些算法对理解同步问题还是很有指导意义的。

B.用硬件方法管理临界区：

用软件方法管理临界区的标志算法比较容易出现标志逻辑混乱的情况，根本原因是在于管理临界区标志要用两条指令：一条指令是看对方的标志，另一条指令是设置自己的标志。进程并发可能导致一个进程在执行这两条指令时被另一个进程中断，最终产生进程对临界区的不正确访问。保证进程在执行这两条指令时不被中断，能很容易地进行临界区管理。完全用软件方法有一定局限性和困难，现在一般都借助于硬件。

最简单的方法是硬件上的关中断，即禁止中断。在检查临界区标志的两条指令之前将中断关上，计算机系统在进程测试并进入临界区期间不响应中断，只有临界区访问完后系统才打开中断，保证了临界资源的互斥访问。

  1. 影响计算机效率 –关中断时间太长会限制计算机交叉执行程序的能力。
  2. 不能及时处理重要程序 –滥用关中断导致重要的中断程序不能及时处理。
  3. 在多CPU下方法失效 –访问相同临界资源的临界区代码可能被另一个进程在另一个CPU上执行。

许多计算机提供了一些特殊的硬件治疗，用于保证几个动作的原子性。这几个动作在一个指令周期中执行，不会被中断，不受到其他指令的干扰。因此，实现临界区管理可以利用硬件提供的测试并设置(Test and Set)指令TS，或者交换指令SWAP。

可将TS指令功能看作一个函数，该函数有一个布尔参数x和一个返回条件码。根据测试到的x值形成条件码，当x为true时置x为false并返回true；否则返回false。
在实现临界区管理时，TS指令将布尔变量x与临界区关联起来–如果x为真，表示没有进程在临界区内，临界资源可用，并立即将x置false，即阻止其他进程进入临界区访问临界资源；如果x为false，则表示已有其他进程进入临界区，本进程需等待。

//TS指令定义
bool TS(bool & x){
    if(x == true){
        x = false;
        return true;
    }
    else{
        return false;
    }
}

另一类特殊指令为交换指令，交换指令在x86指令集中为XCHG指令。

XCHG OPRD1, OPRD2

其功能是交换两个操作数的值，可以简单有效地实现互斥。

//交换指令实现互斥
bool lock = false;
cobegin
process Pi(){
    bool ki = true;
    do{
        SWAP(ki, lock);
    }while(ki);

    //临界区
    //...
    SWAP(ki, lock);
}
coend



3、进程同步机制

互斥也是一种特殊同步。

常见的同步机制有锁、信号量、管程和消息传递。

信号量：

进程在某一特殊点上被迫阻塞直到接收到一个对应的特殊变量值，这种特殊变量值就是信号量(Semaphore)。除了初值外，信号量的值只能由P操作和V操作进行修改，进程通过P、V这两个特殊操作在信号量所关联的系统资源上实现同步和互斥。

信号量可以实现为一种记录型数据结构，包含两个分量，一个是信号量的值value，一个是在信号量关联资源上阻塞的进程的队列的队头指针list。信号量在操作系统中的主要作用是封锁临界区、进程同步和维护资源计数。

typedef struct semaphore{
    int value;
    struct pcb * list;
}

将信号量的值减一。
如果结果小于0，则调用P(s)的进程被阻塞并进入信号量s的阻塞队列；
如果结果大于等于0，则调用P(s)的进程继续执行。

void P(semaphore & s){
    s.value--;
    if(s.value < 0) block(s.list);
}

将信号量的值加一。
若结果不大于0，则调用V(s)的进程从该信号量的阻塞队列中释放，唤醒一个处于等待的进程，将其转换为就绪状态，调用V(s)的进程继续执行；
若结果大于0，则调用V(s)的进程继续执行。

void V(semaphore & s){
    s.value++;
    if(s.value <= 0) wakeup(s.list);
}
  1. P操作意味着进程申请一个资源，求而不得则阻塞进程；V操作意味着释放一个资源，如果有进程在等待获取该资源，则被唤醒。
  2. 若信号量的值为正数，该正数表示可对信号量进行的P操作的次数，即可用资源数，一般初始化设为系统中相关资源总数。（互斥信号量设为1）
  3. 若信号量的值为负数，其绝对值表示有多少个进程在阻塞队列等待。

利用信号量机制也可以是西安进程互斥进入临界区。与TS指令法不同，P、V操作只对信号量测试一次。

semaphore mutex = 1;
cobegin
process Pi(){   //i = 1,2,3...n
    P(mutex);
    //临界区
    V(mutex);
}
coend

设置互斥信号量mutex，初值为1，表示只有一个进程可以用P操作将mutex的值减少为零。
其他试图进入临界区的进程会因为执行P(mutex)而阻塞，从而保证形成互斥。
此例中mutex取值范围为[-(n - 1), 1]，其中n为试图进入临界区的进程个数。

管程：

锁机制有开锁和关锁原语，主要用于解决互斥问题。测试能否进入临界区的判断分散于相互竞争的进程中不停地循环执行。等待的过程消耗了有价值的CPU时间，即忙等待。所以说锁机制效率很低，浪费系统资源。
用信号量实现进程同步时，P、V操作仍然分散在各个进程中。临界资源较多时P、V操作也较多，在编程时容易造成P、V操作的顺序混乱而出现死锁的情况。所以有了新的同步机制：管程(Monitor)，把分散在各进程中的临界区集中起来进行管理，用数据结构抽象表示共享资源，防止进程有意或无意违法同步操作，便于用高级语言来编写程序，也便于程序正确性验证。

管程的基本思想是：把分散在各个进程中的控制和管理临界资源的临界区集中起来统一管理，这样既便于系统管理共享资源，又能保证互斥访问。

管程体现了面向对象的思想。

管程的特点：

  1. 模块化-管程是一个程序基本单位，不仅包含数据还有对数据的操作。
  2. 隐蔽性-管程内与临界资源相关的数据相当于管程的私有成员，仅限管程内部访问，通过管程申请使用该资源的进程无法直接访问，只能调用管程提供的接口。
  3. 互斥性-任一时刻只能有一个进程真正进入管程内部使用相应的系统资源，其他进程必须等待直至管程再次可用。

条件变量(Condition)：

为了有效管理进入管程却因资源不足而阻塞的进程，必须引入条件变量(Condition Var)同步机制，让阻塞进程暂时放弃管理控制权(开放管程)，进入该条件变量相应的等待队列，再适时检测管程内状态变化，以进一步调度。

条件变量只能在管程中通过两个原语操作–wait和signal原语。若一个进程已进入管程但无法继续执行，便在相应的条件变量x上调用x.wait()，将自己阻塞并移入x的等待队列中，放弃管程控制权(开放管程)；另一进程可通过**对同一个条件变量执行x.signal()来唤醒之前在x上等待的进程，队列为空时，signal为空操作。

条件变量仅起到维护等待队列的作用，本身不存在相关的值，自然也不能像信号量那样加减。

管程和进程的关系：

管程是为管理共享资源而建立的，进程主要是为实现系统并发性而引入的。
管程被进程调用，管程和调用它的进程不能并行工作，而进程之间可以并行工作。
管程是语言或者操作系统的组成部分，不必创建和销毁，而进程有生命周期。
管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中。

signal唤醒时的进程共存问题：

已占用管程的进程A，再某一条件变量condition上执行了signal原语后，如果再管程中有进程B阻塞于condition上则该进程会被唤醒。调用signal原语的进程A还未退出管程。这就意味着此时此刻可能会有两个进程再使用管程–而管程的互斥性不允许出现这种情况，为了协调这个问题，有两种解决办法。

办法一：执行signal的进程A等待，直到被释放的进程B退出管程或者因其他条件而阻塞。（Hoare采用的办法）（CRE：A进入urgent队列）
办法二：被释放的进程B等待，直到执行signal的进程A退出管程或者因其他条件而阻塞。
折衷：规定signal原语必须位于管程过程的最后一步。（Hansen采用的办法）

紧急等待队列：

管程中由于一系列的唤醒操作，可能会出现多个等待进程。
这些进程并非资源不足而等待某一条件变量，而是因进程唤醒操作切换使用权而等待。
为此特设一紧急等待队列，其优先级要高于管程入口等待队列。

Hoare管程：

Hoare方法使用信号量和P、V操作来实现对管程中过程的互斥调用，从而实现对资源的互斥调用，其基本思路如下。

1) 管程中设置一个互斥信号量mutex(初值为1)，用于进程互斥调用管程内部过程。进程调用管程内部的任何过程之前都必须先执行P(mutex)，退出管程时必须执行V(mutex)，占用管程的进程在资源不足时要用wait原语阻塞自己，开放管程，因此wait原语中必须执行V(mutex)。

2) 为前文提到的紧急等待队列设置信号量urgent(初值为0)–signal原语中必须执行P(urgent)以避免调用signal的进程与被唤醒的进程共存于管程中，再引入urgent_count存储紧急等待队列中的进程数。管程外的进程在进入管程前先检查是否有进程在等待urgent信号量，如果有则用V(urgent)唤醒它，以体现紧急队列的优先级。

3) 设置信号量x(初值为0)用于阻塞等待资源的进程以及相应的计数器x_count，当进程申请资源而得不到时执行P(x)将自己阻塞，在调用signal时，可用V(x)实现让曾进入管程但在等待资源的进程先于执行该signal的进程。

一般在管程的实现中。将上述(1)(2)封装在一个结构中，称为InterfaceModule。

//Hoare管程实现代码
typedef struct InterfaceModule
{
	semaphore mutex = 1;
	semaphore urgent = 0;
	int urgent_count = 0;
};

InterfaceModule IM;				//	在信号量x上等待的进程数
semaphore x;
int x_count = 0;

void enter()
{
	P(IM.mutex);				//互斥进入管程
}

void leave()
{
	if (IM.urgent_count > 0)	//是否有执行signal而阻塞在urgent上的进程
		V(IM.urgent);			//有则唤醒一个urgent上的进程
	else
		V(IM.mutex);			//没有则直接开放管程
}

void wait()
{
	x_count++;					//等待资源的进程数加一
	if (IM.urgent_count > 0)	//是否存在阻塞在urgent的进程
		V(IM.urgent);			//有则释放一个
	else
		V(IM.mutex);			//没有则直接开放管程

	P(x);						//等待资源的进程阻塞自己
	x_count--;					//等待资源的进程数减一
}

void signal()
{
	if (x_count > 0)			//判断是否有等待资源的进程
	{
		IM.urgent_count++;		//有=>紧急队列进程数加一
		V(x);					//释放一个资源
		P(IM.urgent);			//阻塞发出该signal的进程
		IM.urgent_count--;		//发出signal被阻塞在urgent队列中的进程数减一
	}
}

monitorX.enter();
//...调用管程中过程的代码...
monitorX.leave();



4、进程同步经典问题

  1. 生产者-消费者问题。
  2. 读者-写者问题。
  3. ……
    (具体解决方法见参考资料)

(END)