操作系统 进程同步

时间：2022-08-28 21:48:24

进程同步的基本概念：临界资源、同步和互斥

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。

临界资源

虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。

对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可以把临界资源的访问过程分成四个部分：
  • 进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，如果可以进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
  • 临界区。进程中访问临界资源的那段代码，又称临界段。
  • 退出区。将正在访问临界区的标志清除。
  • 剩余区。代码中的其余部分。
  • do {
    entry section; //进入区
    critical section; //临界区
    exit section; //退出区
    remainder section; //剩余区
    } while (true)

  • 同步

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

    例如，输入进程A通过单缓冲向进程B提供数据。当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据送入缓冲区，进程B被唤醒。反之，当缓冲区满时，进程A被阻塞，仅当进程B取走缓冲数据时，才唤醒进程A。

    互斥

    互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待, 当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

    例如，在仅有一台打印机的系统中，有两个进程A和进程B，如果进程A需要打印时, 系统已将打印机分配给进程B,则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程A唤醒，并将其由阻塞状态变为就绪状态。

    为禁止两个进程同时进入临界区，同步机制应遵循以下准则：
    • 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
    • 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
    • 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。
    • 让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

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

    软件实现方法

    在进入区设置和检查一些标志来标明是否有进程在临界区中，如果已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

    1) 算法一：单标志法。

    该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号，即若turn=0，则允许P0进程进入临界区。该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，如果某个进程不再进入临界区了，那么另一个进程也将进入临界区（违背“空闲让进”）这样很容易造成资源利用的不充分。 
  • </pre><pre name="code" class="cpp">// P0进程
    while(turn!=0);
    critical section;
    turn=1;
    remainder section;
    

    

    

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

    

    2) 算法二：双标志法先检查。
    
该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程需等待；否则，进程才进入自己的临界区。为此，设置了一个数据flag[i]，如第i个元素值为FALSE，表示Pi进程未进入临界区，值为TRUE，表示Pi进程进入临界区。
    // Pi 进程
    while(flag[j]);  // ①    
    flag[i]=TRUE;  // ③  
    critical section;   
    flag[i] = FALSE; 
    remainder section;
    

    

    // Pj 进程
    while(flag[i]);  // ② 进入区
    flag[j] =TRUE;  // ④ 进入区
    critical section;  // 临界区
    flag[j] = FALSE;  // 退出区
    remainder section;  // 剩余区
    

    
优点：不用交替进入，可连续使用；缺点：Pi和Pj可能同时进入临界区。按序列①②③④ 执行时，会同时进入临界区（违背“忙则等待”)。即在检查对方flag之后和切换自己flag 之前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。
    3) 算法三：双标志法后检查。
    
算法二是先检测对方进程状态标志后，再置自己标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后，同时进入临界区。为此，算法三釆用先设置自己标志为TRUE后,再检测对方状态标志，若对方标志为TURE，则进程等待；否则进入临界区。

    •  
 



// Pi进程
flag[i] =TRUE;
while(flag[j]);
critical section;
flag[i] =FLASE;
remainder section;




// Pj进程
flag[j] =TRUE;  // 进入区
while(flag[i]);  // 进入区
critical section;  // 临界区
flag [j] =FLASE;   // 退出区
remainder section;  // 剩余区



当两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态（执行while语句），发现对方也要进入临界区，于是双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。
4)算法四：Peterson’s Algorithm。

为了防止两个进程为进入临界区而无限期等待，又设置变量turn，指示不允许进入临界区的进程编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入。这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区，只允许一个进程进入临界区。 

// Pi进程
flag[i]=TURE; turn=j;
while(flag[j]&&turn==j); 
critical section;
flag[i]=FLASE;
remainder section;



// Pj进程
flag[j] =TRUE;turn=i;  // 进入区
while(flag[i]&&turn==i);   // 进入区
critical section;  // 临界区
flag[j]=FLASE;  // 退出区
remainder section;  // 剩余区



本算法的基本思想是算法一和算法三的结合。利用flag解决临界资源的互斥访问，而利用turn解决“饥饿”现象。
硬件实现方法

本节对硬件实现的具体理解对后面的信号量的学习很有帮助。计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。通过硬件支持实现临界段问题的低级方法或称为元方法。
1) 中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再执行开中断。其典型模式为：…关中断;临界区;开中断;…这种方法限制了处理机交替执行程序的能力，因此执行的效率将会明显降低。对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后不再开中断，则系统可能会因此终止。
2) 硬件指令方法

TestAndSet指令：这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。指令的功能描述如下：
boolean TestAndSet(boolean *lock){
    boolean old;
    old = *lock;
    *lock=true;
    return old;
}



可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用，初值为false。在进程访问临界资源之前，利用TestAndSet检查和修改标志lock；若有进程在临界区，则重复检查，直到进程退出。利用该指令实现进程互斥的算法描述如下：


while TestAndSet (& 1 ock);
// 进程的临界区代码段;
lock=false;
// 进程的其他代码



Swap指令：该指令的功能是交换两个字节的内容。其功能描述如下。 

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



注意：以上对TestAndSet和Swap指令的描述仅仅是功能实现，并非软件实现定义，事实上它们是由硬件逻辑直接实现的，不会被中断。应为每个临界资源设置了一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。在进入临界区之前先利用Swap指令交换lock 与key的内容，然后检查key的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。利用Swap指令实现进程互斥的算法描述如下： 

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



硬件方法的优点：适用于任意数目的进程，不管是单处理机还是多处理机；简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。硬件方法的缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。 

2.11 信号量：整型、记录型信号量以及利用信号量实现进程互斥和前驱关系

信号量机构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为“P操作”（通过）和“V操作（释放）”。原语是指完成某种功能且不被分割不被中断执行的操作序列，通常可由硬件来实现完成不被分割执行特性的功能。如前述的“Test-and-Set”和“Swap”指令，就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机时可由软件通过屏蔽中断方法实现。原语之所以不能被中断执行，是因为原语对变量的操作过程如果被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。如果能够找到一种解决临界段问题的元方法，就可以实现对共享变量操作的原子性。
整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S，wait和signal操作可描述为：


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



wait操作中，只要信号量S<=0，就会不断地测试。因此，该机制并未遵循“让权等待” 的准则，而是使进程处于“忙等”的状态。
记录型信号量

记录型信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程，记录型信号量是由于釆用了记录型的数据结构得名。记录型信号量可描述为： 

typedef struct{
    int value;
    struct process *L;
} semaphore;



相应的wait(S)和signal(S)的操作如下： 

void wait (semaphore S) { //相当于申请资源
    S.value--;
    if(S.value<0) {
        add this process to S.L;
        block(S.L);
    }
}



wait操作，S.value--，表示进程请求一个该类资源，当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到该类资源的等待队列S.L中，可见该机制遵循了“让权等待”的准则。 

void signal (semaphore S) {  //相当于释放资源
    S.value++;
    if(S.value<=0){
        remove a process P from S.L;
        wakeup(P);
    }
}

signal操作，表示进程释放一个资源，使系统中可供分配的该类资源数增1，故S.value++。若加1后仍是S.value<=0，则表示在S.L中仍有等待该资源的进程被阻塞，故还应调用wakeup 原语，将S.L中的第一个等待进程唤醒。
利用信号量实现同步

信号量机构能用于解决进程间各种同步问题。设S为实现进程P1、P2同步的公共信号量，初值为0。进程P2中的语句y要使用进程P1中语句x的运行结果，所以只有当语句x执行完成之后语句y才可以执行。其实现进程同步的算法如下：


semaphore S = 0;  //初始化信号量
P1 ( ) {
    // …
    x;  //语句x
    V(S);  //告诉进程P2,语句乂已经完成
}
P2()）{
    // …
    P(S) ;  //检查语句x是否运行完成
    y;  // 检查无误，运行y语句
    // …
}


利用信号量实现进程互斥

信号量机构也能很方便地解决进程互斥问题。设S为实现进程Pl、P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数为1)。只需把临界区置于P(S)和V(S)之间，即可实现两进程对临界资源的互斥访问。其算法如下： 

semaphore S = 1;  //初化信号量
P1 ( ) {
    // …
    P(S);  // 准备开始访问临界资源，加锁
    // 进程P1的临界区
    V(S);  // 访问结束，解锁
    // …
}
P2() {
    // …
    P(S); //准备开始访问临界资源，加锁
    // 进程P2的临界区；
    V(S);  // 访问结束，解锁
    // …
}

互斥的实现是不同进程对同一信号量进行P、V操作，一个进程在成功地对信号量执行了P操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作,表示当前没有进程进入临界区，可以让其他进程进入。
利用信号量实现前驱关系

信号量也可以用来描述程序之间或者语句之间的前驱关系。图2-8给出了一个前驱图，其中S1, S2, S3, …, S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干个初始值为“0”的信号量。例如，为保证S1 -> S2、 S1 -> S3的前驱关系，应分别设置信号量a1、a2。同样，为了保证 S2 -> S4、S2 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,应设置信号量bl、b2、c、d、e。 
操作系统 进程同步
图2-8 前驱图举例


实现算法如下： 

semaphore  al=a2=bl=b2=c=d=e=0;  //初始化信号量
S1() {
    // …
    V(al);  V(a2) ;  //S1已经运行完成
}
S2() {
    P(a1);  //检查S1是否运行完成
    // …
    V(bl); V(b2); // S2已经运行完成
}
S3() {
    P(a2);  //检查S1是否已经运行完成
    // …
    V(c);  //S3已经运行完成
}
S4() {
    P(b1);  //检查S2是否已经运行完成
    // …
    V(d);  //S4已经运行完成
}
S5() {
    P(b2);  //检查S2是否已经运行完成
    // …
    V(e);  // S5已经运行完成
}
S6() {
    P(c);  //检查S3是否已经运行完成
    P(d);  //检查S4是否已经运行完成
    P(e);  //检查S5是否已经运行完成
    // …;
}




分析进程同步和互斥问题的方法步骤

1) 关系分析。找出问题中的进程数，并且分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。2) 整理思路。找出解决问题的关键点，并且根据做过的题目找出解决的思路。根据进程的操作流程确定P操作、V操作的大致顺序。3) 设置信号量。根据上面两步，设置需要的信号量，确定初值，完善整理。

 

2.12 管程：管程的定义、组成及基本特性


管程的定义

系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略了它们的内部结构和实现细节。管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。
管程的组成

1) 局部于管程的共享结构数据说明。2) 对该数据结构进行操作的一组过程。3) 对局部于管程的共享数据设置初始值的语句。
管程的基本特性

1) 局部于管程的数据只能被局部于管程内的过程所访问。2) 一个进程只有通过调用管程内的过程才能进入管程访问共享数据。3) 每次仅允许一个进程在管程内执行某个内部过程。由于管程是一个语言成分，所以管程的互斥访问完全由编译程序在编译时自动添加，无需程序员关注，而且保证正确。
2.13 经典进程同步问题1：生产者-消费者问题


问题描述

一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。
问题分析

1) 关系分析。生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，他们也是同步关系。2) 整理思路。这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。3) 信号量设置。信号量mutex作为互斥信号量，它用于控制互斥访问缓冲池，互斥信号量初值为1；信号量full用于记录当前缓冲池中“满”缓冲区数，初值为0。信号量empty 用于记录当前缓冲池中“空”缓冲区数，初值为n。生产者-消费者进程的描述如下： 

semaphore mutex=1; //临界区互斥信号量
semaphore empty=n;  //空闲缓冲区
semaphore full=0;  //缓冲区初始化为空
producer () { //生产者进程
    while(1){
        produce an item in nextp;  //生产数据
        P(empty);  //获取空缓冲区单元
        P(mutex);  //进入临界区.
        add nextp to buffer;  //将数据放入缓冲区
        V(mutex);  //离开临界区,释放互斥信号量
        V(full);  //满缓冲区数加1
    }
}

consumer () {  //消费者进程
    while(1){
        P(full);  //获取满缓冲区单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  //从缓冲区中取出数据
        V (mutex);  //离开临界区，释放互斥信号量
        V (empty) ;  //空缓冲区数加1
        consume the item;  //消费数据
    }
}

该类问题要注意对缓冲区大小为n的处理，当缓冲区中有空时便可对empty变量执行P 操作，一旦取走一个产品便要执行V操作以释放空闲区。对empty和full变量的P操作必须放在对mutex的P操作之前。如果生产者进程先执行P(mutex)，然后执行P(empty)，消费者执行P(mutex),然后执行P(fall),这样可不可以？答案是否定的。设想生产者进程已经将缓冲区放满，消费者进程并没有取产品，即empty = 0，当下次仍然是生产者进程运行时，它先执行P(mutex)*信号量，再执行P(empty)时将被阻塞，希望消费者取出产品后将其唤醒。轮到消费者进程运行时，它先执行P(mutex)，然而由于生产者进程已经*mutex信号量，消费者进程也会被阻塞，这样一来生产者、消费者进程都将阻塞，都指望对方唤醒自己，陷入了无休止的等待。同理，如果消费者进程已经将缓冲区取空，即 full = 0,下次如果还是消费者先运行，也会出现类似的死锁。不过生产者释放信号量时，mutex、full先释放哪一个无所谓，消费者先释放mutex还是empty都可以。

下面再看一个较为复杂的生产者-消费者问题:
问题描述

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈就可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿
可以从盘子中取出。
问题分析

1) 关系分析。这里的关系稍复杂一些，首先由每次只能向其中放入一只水果可知爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发，如图2-8所示。

2) 整理思路。这里有4个进程，实际上可以抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。

操作系统 进程同步

图2-9  进程之间的关系
3) 信号量设置。首先设置信号量plate为互斥信号量，表示是否允许向盘子放入水果，初值为1，表示允许放入，且只允许放入一个。信号量 apple表示盘子中是否有苹果，初值为0，表示盘子为空，不许取，若apple=l可以取。信号量orange表示盘子中是否有橘子，初值为0，表示盘子为空，不许取，若orange=l可以取。解决该问题的代码如下：
semaphore plate=l, apple=0, orange=0;
dad() {  //父亲进程
    while (1) {
        prepare an apple;
        P(plate) ;  //互斥向盘中取、放水果
        put the apple on the plate;  //向盘中放苹果
        V(apple);  //允许取苹果
    }
}

mom() {  // 母亲进程
    while(1) {
        prepare an orange;
        P(plate);  //互斥向盘中取、放水果
        put the orange on the plate;  //向盘中放橘子
        V(orange); //允许取橘子
    }
}

son(){  //儿子进程
    while(1){
        P(orange) ;  //互斥向盘中取橘子
        take an orange from the plate;
        V(plate);  //允许向盘中取、放水果
        eat the orange;
    }
}

daughter () {  //女儿进程
    while(1) {
        P(apple);  // 互斥向盘中取苹果
        take an apple from the plate;
        V(plate);  //运行向盘中取、放水果
        eat the apple;
    }
}

进程间的关系如图2-9所示。dad()和daughter()、mam()和son()必须连续执行，正因为如此，也只能在女儿拿走苹果后，或儿子拿走橘子后才能释放盘子，即V(plate)操作。




2.14 经典进程同步问题2：读者-写者问题


问题描述

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

1) 关系分析。由题目分析读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题。

2) 整理思路。两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的P操作、V操作即可解决。读者的问题比较复杂，它必须实现与写者互斥的同时还要实现与其他读者的同步，因此，仅仅简单的一对P操作、V操作是无法解决的。那么，在这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者的时候写者是无法写文件的，此时读者会一直占用文件，当没有读者的时候写者才可以写文件。同时这里不同读者对计数器的访问也应该是互斥的。

3) 信号量设置。首先设置信号量count为计数器，用来记录当前读者数量，初值为0; 设置mutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw用于保证读者和写者的互斥访问。

代码如下： 

int count=0;  //用于记录当前的读者数量
semaphore mutex=1;  //用于保护更新count变量时的互斥
semaphore rw=1;  //用于保证读者和写者互斥地访问文件
writer () {  //写者进程
    while (1){
        P(rw); // 互斥访问共享文件
        Writing;  //写入
        V(rw) ;  //释放共享文件
    }
}

reader () {  // 读者进程
    while(1){
        P (mutex) ;  //互斥访问count变量
        if (count==0)  //当第一个读进程读共享文件时
            P(rw);  //阻止写进程写
        count++;  //读者计数器加1
        V (mutex) ;  //释放互斥变量count
        reading;  //读取
        P (mutex) ;  //互斥访问count变量
        count--; //读者计数器减1
        if (count==0)  //当最后一个读进程读完共享文件
            V(rw) ;  //允许写进程写
        V (mutex) ;  //释放互斥变量 count
    }
}


在上面的算法中，读进程是优先的，也就是说，当存在读进程时，写操作将被延迟，并且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式下，会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

如果希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等待到已在共享文件的读进程执行完毕则立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并且在上面的程序中 writer()和reader()函数中各增加一对PV操作，就可以得到写进程优先的解决程序。


int count = 0;  //用于记录当前的读者数量
semaphore mutex = 1;  //用于保护更新count变量时的互斥
semaphore rw=1;  //用于保证读者和写者互斥地访问文件
semaphore w=1;  //用于实现“写优先”

writer(){
    while(1){
        P(w);  //在无写进程请求时进入
        P(rw);  //互斥访问共享文件
        writing;  //写入
        V(rw);  // 释放共享文件
        V(w) ;  //恢复对共享支件的访问
    }
}

reader () {  //读者进程
    while (1){
        P (w) ;  // 在无写进程请求时进入
        P (mutex);  // 互斥访问count变量

        if (count==0)  //当第一个读进程读共享文件时
            P(rw);  //阻止写进程写

        count++;  //读者计数器加1
        V (mutex) ;  //释放互斥变量count
        V(w);  //恢复对共享文件的访问
        reading;  //读取
        P (mutex) ; //互斥访问count变量
        count--;  //读者计数器减1

        if (count==0)  //当最后一个读进程读完共享文件
            V(rw);  //允许写进程写

        V (mutex);  //释放互斥变量count
    }
}


2.15 经典进程同步问题3：哲学家进餐问题


问题描述

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

1) 关系分析。5名哲学家与左右邻居对其中间筷子的访问是互斥关系。

2) 整理思路。显然这里有五个进程。本题的关键是如何让一个哲学家拿到左右两个筷子而不造成死锁或者饥饿现象。那么解决方法有两个，一个是让他们同时拿两个筷子；二是对每个哲学家的动作制定规则，避免饥饿或者死锁现象的发生。

操作系统 进程同步

图2-10 5名哲学家进餐
3) 信号量设置。定义互斥信号量数组Ch0PstiCk[5] = {l, 1, 1, 1, 1}用于对5个筷子的互斥访问。

对哲学家按顺序从0～4编号，哲学家i左边的筷子的编号为i，哲学家右边的筷子的编号为(i+l)%5。 

semaphore chopstick[5] = {1,1,1,1,1}; //定义信号量数组chopstick[5],并初始化
Pi(){  //i号哲学家的进程
    do{
        P (chopstick[i] ) ; //取左边筷子
        P (chopstick[(i+1) %5] ) ；  //取右边篌子
        eat;  //进餐
        V(chopstick[i]) ; //放回左边筷子
        V(chopstick[(i+l)%5]);  //放回右边筷子
        think;  //思考
    } while (1);
}

该算法存在以下问题：当五个哲学家都想要进餐，分别拿起他们左边筷子的时候（都恰好执行完wait(chopstick[i]);)筷子已经被拿光了，等到他们再想拿右边的筷子的时候（执行 wait(chopstick[(i+l)%5]);)就全被阻塞了，这就出现了死锁。

为了防止死锁的发生，可以对哲学家进程施加一些限制条件，比如至多允许四个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子;对哲学家顺序编号，要求奇数号哲学家先抓左边的筷子，然后再转他右边的筷子，而偶数号哲学家刚好相反。正解制定规则如下：假设釆用第二种方法，当一个哲学家左右两边的筷子都可用时，才允许他抓起筷子。


semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量
semaphore mutex=l;  //设置取筷子的信号量
Pi(){ //i号哲学家的进程
    do{
        P (mutex) ; //在取筷子前获得互斥量
        P (chopstick [i]) ; //取左边筷子
        P (chopstick[ (i+1) %5]) ;  //取右边筷子
        V (mutex) ; //释放取筷子的信号量
        eat;  //进餐
        V(chopstick[i] ) ;  //放回左边筷子
        V(chopstick[ (i+l)%5]) ;  //放回右边筷子
        think;  // 思考
    }while(1);
}

此外还可以釆用AND型信号量机制来解决哲学家进餐问题，有兴趣的读者可以查阅相关资料，自行思考。 

 

2.16 经典进程同步问题4：吸烟者问题


向题描述

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

1) 关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或 以上的抽烟者，三个抽烟者对抽烟这个动作互斥（或由三个抽烟者轮流抽烟得知）

2) 整理思路。显然这里有四个进程。供应者作为生产者向三个抽烟者提供材料。

3) 信号量设置。信号量offer1、offer2、offer3分别表示烟草和纸组合的资源、烟草和 胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。

代码如下： 

int random; //存储随机数
semaphore offer1=0; //定义信号量对应烟草和纸组合的资源
semaphore offer2=0; //定义信号量对应烟草和胶水组合的资源
semaphore offer3=0; //定义信号量对应纸和胶水组合的资源
semaphore finish=0; //定义信号量表示抽烟是否完成

//供应者
while(1){
    random = 任意一个整数随机数;
    random=random% 3;
    if(random==0)
        V(offerl) ; //提供烟草和纸
    else if(random==l) 
        V(offer2);  //提供烟草和胶水
    else
        V(offer3)  //提供纸和胶水
    // 任意两种材料放在桌子上;
    P(finish);
}

//拥有烟草者
while(1){
    P (offer3);
    // 拿纸和胶水，卷成烟，抽掉;
    V(finish);
}

//拥有纸者
while(1){
    P(offer2);
    // 烟草和胶水,卷成烟，抽掉；
    V(finish);
}

//拥有胶水者
while(1){
    P(offer1);
    // 拿烟草和纸，卷成烟，抽掉;
    v(finish);
}


标签：
相关文章