操作系统原理学习笔记（七）-进程同步

操作系统原理学习笔记目录

后面的部分是手机打完后，用电脑整理和补充的，所以可能有的地方前后文不搭。

进程同步的概念

进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的进程之间能按照一定的规则共享系统资源，互相合作，从而使得程序的执行具有可再现性。

间接相互制约关系：
多个程序需要使用同一种临界资源，如打印机，这种资源只能一次被一个进程占用，因此互相制约。

直接相互制约关系：
进程B的输入是进程A的输出，则必须等待A进程执行后才能执行B进程。

临界资源(Critical Resource)：
如打印机、磁带机这种资源属于临界资源，进程间采用互斥模式来共享这种资源，但临界资源不完全是硬件资源。

生产者-消费者(Producer-Consumer)问题是一个进程同步问题：
生产者生产东西提供给消费者使用，为了能够并发执行，生产者将东西放入缓冲区，消费者从缓冲区取出东西。
缓冲区满时，不允许填入；缓冲区空时，不允许取出。
在顺序执行的情况下，不论放入取出的顺序如何，缓冲区的结果都将是正确的，但在并发执行时，因为使用同一个变量（保存缓冲区当前大小，用作比对当前缓冲区情况），会出现差错。
为了防止这个差错的出现，应该把缓冲区变量设置为临界资源，同时只运行一个进程访问。

临界区(Critical Section)：
访问临界资源的代码叫做临界区，为了让临界区只在空闲时被访问，需要设置一个进入区(entry section)，与一个退出区(exit section)，分别用来判断是否可用（可用则设置正在使用的标志并进入使用）与还原被修改的使用标志，除了三个区外的代码被称为剩余区。
一个访问临界资源的循环进程可以这样表示：
while(TURE){
进入区
临界区
退出区
剩余区
}

同步机制应该遵循的规则：
空闲让进：临界区空闲时允许进入。
忙则等待：临界区繁忙时阻止进入，令其等待。
有限等待：保证进程能在有限时间内访问临界区。
让权等待：立即释放不能进入临界区的进程处理机，防止出现“忙等状态”。

硬件同步机制

使用软件方法解决进程互斥进入临界区的问题存在很大局限性，因此较少采用，取而代之的是硬件同步机制。

关中断：
在进入锁测试之前关闭中断，直到完成锁测试并关上锁之后才能打开中断。
这样，临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。
但存在诸多缺点：
滥用关中断权利可能导致严重后果。
关中断时间过长会影响系统效率，限制处理器交叉执行程序的能力。
关中断不适用于多CPU系统，因为在一个处理器上关中断不能防止其他处理器执行相同的临界区代码。

利用Test-and-Set指令实现互斥：
硬件指令：“测试并建立”原语指令。
一般性描述：
boolean TS(boolean *lock){
boolean old;
old = *lock;
*lock = TRUE;
return old;
}
利用TS指令实现互斥的循环进程结构描述
do{
...
while (TS(&lock));
critical section;
lock = FALSE;
remainder section;
} while(TRUE);
容易看出，lock为FALSE时，第二层循环将lock修改为TRUE后会直接结束循环，在执行完临界区代码后，将lock重置为FALSE，再执行剩余区代码。

利用Swap指令实现进程互斥：
对换指令，在Intel 80x86中也称为XCHG指令，用于交换两个字的内容，效果与代码入门的交换两个数的值一样。
过程描述：
do{
key = TRUE;
do{
swap(&lock, &key);
}
critical section;
lock = FALSE;
...
} while(TRUE);

利用上述硬件指令能有效实现进程互斥，但临界资源繁忙时，可能会被频繁测试，处于“忙等”状态，不符合“让权等待”的原则。

信号量机制

信号量：Semaphores

整型信号量：
由Dijkstra定义，定义为用于表示资源数目的整型量S。
除初始化外，仅能通过两个原子操作wait(S)与signal(S)访问，两者也被称为P、V操作。两者可如下描述：

wait(S){
    while(S<=0);
    S--;
}
signal(S){
    S++;
}

记录型信号量：
在整型信号量机制中，wait操作会在S≤0时不断测试，未遵守“让权等待”，反而造成进程“忙等”。
记录型信号量机制不存在“忙等”，但采用“让权等待”策略后，会出现多个进程等待访问同一临界资源。
因此，在信号量机制中除了代表资源数目的value整型变量外，还应增加进程链表指针list（链接等待进程）。两个新增数据可描述为：

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

wait(semaphore *S){
    S->value -= 1;
    if(S->value < 0) block(S->list);
}

signal(semaphore *S){
    S->value += 1;
    if(S->value <= 0) wakeup(S->list);
}

可以看出，记录型信号量使用了block原语与wakeup原语来代替while查询，防止忙等。
一旦资源用完，block原语会阻塞信号量，直到有signal信号出现，wakeup原语唤醒。

AND型信号量：
当两个进程A B需要临界资源C D时，若此时A获得C，B获得D，若无外力介入，A B会进入死锁状态。
AND同步机制通过对资源的一次性分配来防止上述情况的发生，若无法一次性分配所有资源，则其他资源则不会分配。描述如下：

//这部分代码里面的英文句子是书上的，第60页。
Swait(S1, S2, ..., Sn){
    while(TRUE){
        if(Si>=1 && ... && Sn>=1){
            for(i=1;    i<=n;    i++) Si--;
            break;
        }
        else{
            Place the process in the waiting associated with first Si found with Si<1, and set the program count of this process to the begin of Swait operation.
        }
    }
}

Ssignal(S1, S2, ..., Sn){
    while(TRUE){
        for(i=1;    i<=n;    i++){
            Si++;
            Remove all the process waiting in the queue associated with Si into the ready queue
        }
    }
}

信号量集：

记录型信号量机制一次只能对临界资源进行一个单位的申请与释放，若需要N个单位，效率很低，且增加了死锁概率。若此时将申请的数量按需设置，即可解决该问题。
通过对AND信号量机制扩展，使得进程对信号量Si的测试值由1改为该资源的下限值ti，即Si>=ti，进程的资源占用量为di。描述如下：

Swait(S1, t1, d1, ..., Sn, tn, dn);
Ssignal(S1, d1, ..., Sn, dn);

信号量集的几种特殊情况：
Swait(S, d, d)，此时信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源少于d时，不分配。
Swait(S, 1, 1)，此时信号量集已蜕化为一般的记录型信号量（S>1）或互斥信号量（S=1）。
Swait(S, 1, 0)，特殊且有用的信号量操作，当S≥1时，允许多个进程进入某特定区。S变为0后将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

信号量的应用

利用信号量实现进程排斥：
设置一个互斥信号量mutex，并设其初始值为1，进程访问的临界区CS置于wait(mutex)和signal(mutex)操作间即可，wait()与signal()必须成对出现。两个进程的互斥实现形式描述如下：

文字描述：
mutex为互斥信号量，初值为1，范围为-1，0，1。
为1时，表示两个进程均未进入该临界区。
为0时，表示有一个进程进入临界区运行，此时另一个必须等待，挂入阻塞队列。
为-1时，一个进程进入临界区运行，另一个进程因等待而阻塞在信号量队列中，需要被当前已在临界区运行的进程退出时唤醒。

semaphore mutex = 1;
Pa(){
    while(1){
        wait(mutex);
        critical section;
        signal(mutex);
        remainder section;
    }
}

//代码描述
Pb(){
    while(1){
        wait(mutex);
        critical section;
        signal(mutex);
        remainder section;
    }
}

利用信号量实现前驱关系：
进程P1与P2中分别有语句S1与S2，需要在S1执行后才执行S2，只需要一个公用信号量S，如下操作即可：
进程P1中：S1; signal(S);
进程P2中：wait(S); S2;

管程机制
管程(Monitors)：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成的一个操作系统的资源管理模块。
Hansan对管程的定义：一个管程定义了一个数据结构，和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。
组成：
管程的名称。
局部于管程的共享数据结构说明。
对该数据结构进行操作的一组过程。
对局部于管程的共享数据设置初始值的语句。

管程的语法描述如下：

Monitor monitor_name{             // 管程名
    share variable declarations;  // 共享变量说明
    cond declarations;            // 条件变量说明
    public:                       // 能被进程调用的过程
    void P1(...){                 // 对数据结构操作的过程
        ...
    }
    void P2(...){
        ...
    }
    ...
    {                             // 管程主体
        initialization code;      // 初始化代码
        ...
    }
}

特性：
模块化：管程是一个基本程序单位，可以单独编译。
抽象数据类型：管程中不仅有数据，还有对数据的操作。
信息掩蔽：管程中的数据仅能被管程中的过程访问，这些过程也是在管程内部定义的。

管程和进程不同：
进程定义的是私有的数据结构PCB，而管程定义的是公共数据类型，如消息队列。
进程由顺序程序执行有关操作，管程也是进行同步操作和初始化操作。
设置进程的目的在于实现系统并发性，而管程主要是同步操作和初始化操作。
进程通过调用管程中的过程对共享数据结构实行操作，该过程如子程序一般，因此管程是被动工作方式，进程为主动工作方式。
进程之间能并发执行，管程不能与调用者并发。
进程具有动态性，由创建而生，由撤销而亡，而管程也是操作系统中的一个资源管理模块，供进程调用。

条件变量：
当一个进程调用了管程，并在管程中被阻塞或挂起，直到进程恢复的期间，如果该进程不释放管程，其他进程就无法进入管程。
为此，引入了条件变量condition，且因为阻塞或挂起的原因并不单一，因此需要设置多个条件变量，且对其的访问智能在管程中进行。
条件变量的形式为：condition x, y;
只能使用wait和signal操作条件变量。
条件变量也是一种抽象数据类型，每个条件变量保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作可表示为x.wait与x.signal：
x.wait：正在调用管程的进程，因条件x需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列中，并释放管程，直到x条件变化。
x.signal：正在调用管程的进程，发现条件x发生了变化，调用x.signal，重新启动一个因为条件x阻塞或挂起的进程，如果有多个，则选择一个，如果没有，则不操作。
如果被条件x阻塞的进程Q，被调用管程的P执行x.signal后，被重新启动，为了确定Q与P哪个执行哪个不执行，可如此处理：
P等待，直到Q离开管程或等待另一条件。
Q等待，直到P离开管程或等待另一条件。
Hoare采用了第一种处理方式，而Hansan选择两者折中，即：管程中的过程，所执行的signal操作，是过程体的最后一个操作，于是，进程P执行signal操作后退出管程，Q恢复执行。