精华内容
下载资源
问答
  • 2018-12-29 19:05:38

    1.信号量机制
    信号量机制即利用pv操作来对信号量进行处理。

    什么是信号量?信号量(semaphore)的数据结构为一个值和一个指针,指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。

    当它的值大于0时,表示当前可用资源的数量;

    当它的值小于0时,其绝对值表示等待使用该资源的进程个数。

    注意,信号量的值仅能由PV操作来改变。

         一般来说,信号量S³0时,S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源,因此S的值减1;当S<0时,表示已经没有可用资源,请求者必须等待别的进程释放该类资源,它才能运行下去。而执行一个V操作意味着释放一个单位资源,因此S的值加1;若S£0,表示有某些进程正在等待该资源,因此要唤醒一个等待状态的进程,使之运行下去。

    2.PV操作
    什么是PV操作?
    p操作(wait):申请一个单位资源,进程进入

    经典伪代码


    wait(S){
        while(s<=0)    //如果没有资源则会循环等待;
            ;
        S-- ;
    }
    v操作(signal):释放一个单位资源,进程出来


    signal(S){
        S++ ;
    }


    p操作(wait):申请一个单位资源,进程进入
    v操作(signal):释放一个单位资源,进程出来
    PV操作的含义:PV操作由P操作原语和V操作原语组成(原语是不可中断的过程),对信号量进行操作,具体定义如下:
        P(S):①将信号量S的值减1,即S=S-1;
               ②如果S<=0,则该进程继续执行;否则该进程置为等待状态,排入等待队列。
        V(S):①将信号量S的值加1,即S=S+1;
               ②如果S>0,则该进程继续执行;否则释放队列中第一个等待信号量的进程。

    PV操作的意义:我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。


    使用PV操作实现进程互斥时应该注意的是:
        (1)每个程序中用户实现互斥的P、V操作必须成对出现,先做P操作,进临界区,后做V操作,出临界区。若有多个分支,要认真检查其成对性。
        (2)P、V操作应分别紧靠临界区的头尾部,临界区的代码应尽可能短,不能有死循环。
        (3)互斥信号量的初值一般为1。

    3.三个经典同步问题
    前面我们讲到信号量机制,下面我们讲解利用信号量及PV操作解决几个经典同步问题。
    a.生产者-消费者(缓冲区问题)

    生产者一消费者问题(producer-consumerproblem)是指若干进程通过有限的共享缓冲区交换数据时的缓冲区资源使用问题。假设“生产者”进程不断向共享缓冲区写人数据(即生产数据),而“消费者”进程不断从共享缓冲区读出数据(即消费数据);共享缓冲区共有n个;任何时刻只能有一个进程可对共享缓冲区进行操作。所有生产者和消费者之间要协调,以完成对共享缓冲区的操作。
    生产者进程结构:
    do{
         wait(empty) ;
         wait(mutex) ;
        
         add nextp to buffer
        
         signal(mutex) ;
         signal(full) ;
    }while(1) ;

    消费者进程结构:
    do{
         wait(full) ;
         wait(mutex) ;
        
         remove an item from buffer to nextp
        
         signal(mutex) ;
         signal(empty) ;
    }while(1) ;

    我们可把共享缓冲区中的n个缓冲块视为共享资源,生产者写人数据的缓冲块成为消费者可用资源,而消费者读出数据后的缓冲块成为生产者的可用资源。为此,可设置三个信号量:full、empty和mutex。其中:full表示有数据的缓冲块数目,初值是0;empty表示空的缓冲块数初值是n;mutex用于访问缓冲区时的互斥,初值是1。实际上,full和empty间存在如下关系:full + empty = N

    注意:这里每个进程中各个P操作的次序是重要的。各进程必须先检查自己对应的资源数在确信有可用资源后再申请对整个缓冲区的互斥操作;否则,先申请对整个缓冲区的互斥操后申请自己对应的缓冲块资源,就可能死锁。出现死锁的条件是,申请到对整个缓冲区的互斥操作后,才发现自己对应的缓冲块资源,这时已不可能放弃对整个缓冲区的占用。如果采用AND信号量集,相应的进入区和退出区都很简单。如生产者的进入区为Swait(empty,mutex),退出区为Ssignal(full,mutex)。
    b.作者读者问题
    读者一写者问题(readers-writersproblem)是指多个进程对一个共享资源进行读写操作的问题。
    假设“读者”进程可对共享资源进行读操作,“写者”进程可对共享资源进行写操作;任一时刻“写者”最多只允许一个,而“读者”则允许多个。即对共享资源的读写操作限制关系包括:“读—写,互斥、“写一写”互斥和“读—读”允许。


    我们可认为写者之间、写者与第一个读者之间要对共享资源进行互斥访问,而后续读者不需要互斥访问。为此,可设置两个信号量Wmutex、Rmutex和一个公共变量Rcount。其中:Wmutex表示“允许写”,初值是1;公共变量Rcount表示“正在读”的进程数,初值是0;Rmutex表示对Rcount的互斥操作,初值是1。

    在这个例子中,我们可见到临界资源访问过程的嵌套使用。在读者算法中,进入区和退出区又分别嵌套了一个临界资源访问过程。

    对读者一写者问题,也可采用一般“信号量集”机制来实现。如果我们在前面的读写操作限制上再加一个限制条件:同时读的“读者”最多R个。这时,可设置两个信号量Wmutex和Rcount。其中:Wmutex表示“允许写”,初值是¨Rcount表示“允许读者数目”,初值为R。为采用一般“信号量集”机制来实现的读者一写者算法。


    c.哲学家进餐问题


    (1) 在什么情况下5 个哲学家全部吃不上饭? 
    考虑两种实现的方式,如下: 
    A. 
    算法描述: 
    void philosopher(int i) /*i:哲学家编号,从0 到4*/ 

        while (TRUE) { 
            think( ); /*哲学家正在思考*/ 
            take_fork(i); /*取左侧的筷子*/ 
            take_fork((i+1) % N); /*取左侧筷子;%为取模运算*/ 
            eat( ); /*吃饭*/ 
            put_fork(i); /*把左侧筷子放回桌子*/ 
            put_fork((i+1) % N); /*把右侧筷子放回桌子*/ 
        } 


    分析:假如所有的哲学家都同时拿起左侧筷子,看到右侧筷子不可用,又都放下左侧筷子, 
    等一会儿,又同时拿起左侧筷子,如此这般,永远重复。对于这种情况,即所有的程序都在 
    无限期地运行,但是都无法取得任何进展,即出现饥饿,所有哲学家都吃不上饭。 
    B. 
    算法描述: 
    规定在拿到左侧的筷子后,先检查右面的筷子是否可用。如果不可用,则先放下左侧筷子, 
    等一段时间再重复整个过程。 
    分析:当出现以下情形,在某一个瞬间,所有的哲学家都同时启动这个算法,拿起左侧的筷 
    子,而看到右侧筷子不可用,又都放下左侧筷子,等一会儿,又同时拿起左侧筷子……如此 
    这样永远重复下去。对于这种情况,所有的程序都在运行,但却无法取得进展,即出现饥饿, 
    所有的哲学家都吃不上饭。 
    (2) 描述一种没有人饿死(永远拿不到筷子)算法。 
    考虑了四种实现的方式(A、B、C、D): 
    A.原理:至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释 
    放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量,只允 
    许4 个哲学家同时进入餐厅就餐,这样就能保证至少有一个哲学家可以就餐,而申请进入 
    餐厅的哲学家进入room 的等待队列,根据FIFO 的原则,总会进入到餐厅就餐,因此不会 
    出现饿死和死锁的现象。 
    伪码: 
    semaphore chopstick[5]={1,1,1,1,1};
    semaphore room=4; 
    void philosopher(int i) 

        while(true) 
        { 
            think(); 
            wait(room); //请求进入房间进餐 
            wait(chopstick[i]); //请求左手边的筷子 
            wait(chopstick[(i+1)%5]); //请求右手边的筷子 
            eat(); 
            signal(chopstick[(i+1)%5]); //释放右手边的筷子 
            signal(chopstick[i]); //释放左手边的筷子 
            signal(room); //退出房间释放信号量room 
        } 

    B.原理:仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。 
    方法1:利用AND 型信号量机制实现:根据课程讲述,在一个原语中,将一段代码同时需 
    要的多个临界资源,要么全部分配给它,要么一个都不分配,因此不会出现死锁的情形。当 
    某些资源不够时阻塞调用进程;由于等待队列的存在,使得对资源的请求满足FIFO 的要求, 
    因此不会出现饥饿的情形。 
    伪码: 
    semaphore chopstick[5]={1,1,1,1,1}; 
    void philosopher(int I) 

        while(true) 
        { 
            think(); 
            Swait(chopstick[(I+1)]%5,chopstick[I]); 
            eat(); 
            Ssignal(chopstick[(I+1)]%5,chopstick[I]); 
        } 


    方法2:利用信号量的保护机制实现。通过信号量mutex对eat()之前的取左侧和右侧筷 
    子的操作进行保护,使之成为一个原子操作,这样可以防止死锁的出现。 
    伪码: 
    semaphore mutex = 1 ; 
    semaphore chopstick[5]={1,1,1,1,1}; 
    void philosopher(int I) 

        while(true) 
        { 
            think(); 
            wait(mutex); 
            wait(chopstick[(I+1)]%5); 
            wait(chopstick[I]); 
            signal(mutex); 
            eat(); 
            signal(chopstick[(I+1)]%5); 
            signal(chopstick[I]); 
        } 


    C. 原理:规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号 
    的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即 
    五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获 
    得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列,根FIFO原则,则先申请的哲 
    学家会较先可以吃饭,因此不会出现饿死的哲学家。 
    伪码: 
    semaphore chopstick[5]={1,1,1,1,1}; 
    void philosopher(int i) 

        while(true) 
        { 
            think(); 
            if(i%2 == 0) //偶数哲学家,先右后左。 
            { 
                wait (chopstick[ i + 1 ] mod 5) ; 
                wait (chopstick[ i]) ; 
                eat(); 
                signal (chopstick[ i + 1 ] mod 5) ; 
                signal (chopstick[ i]) ; 
            } 
            Else //奇数哲学家,先左后右。 
            { 
                wait (chopstick[ i]) ; 
                wait (chopstick[ i + 1 ] mod 5) ; 
                eat(); 
                signal (chopstick[ i]) ; 
                signal (chopstick[ i + 1 ] mod 5) ; 
            } 
        } 
    }


    D.利用管程机制实现(最终该实现是失败的,见以下分析): 
    原理:不是对每只筷子设置信号量,而是对每个哲学家设置信号量。test()函数有以下作 
    用: 
    a. 如果当前处理的哲学家处于饥饿状态且两侧哲学家不在吃饭状态,则当前哲学家通过 
    test()函数试图进入吃饭状态。 
    b. 如果通过test()进入吃饭状态不成功,那么当前哲学家就在该信号量阻塞等待,直到 
    其他的哲学家进程通过test()将该哲学家的状态设置为EATING。 
    c. 当一个哲学家进程调用put_forks()放下筷子的时候,会通过test()测试它的邻居, 
    如果邻居处于饥饿状态,且该邻居的邻居不在吃饭状态,则该邻居进入吃饭状态。 
    由上所述,该算法不会出现死锁,因为一个哲学家只有在两个邻座都不在进餐时,才允 
    许转换到进餐状态。 
    该算法会出现某个哲学家适终无法吃饭的情况,即当该哲学家的左右两个哲学家交替 
    处在吃饭的状态的时候,则该哲学家始终无法进入吃饭的状态,因此不满足题目的要求。 
    但是该算法能够实现对于任意多位哲学家的情况都能获得最大的并行度,因此具有重要 
    的意义。 
    伪码: 
    #define N 5 /* 哲学家人数*/ 
    #define LEFT (i-1+N)%N /* i的左邻号码 */ 
    #define RIGHT (i+1)%N /* i的右邻号码 */ 
    typedef enum { THINKING, HUNGRY, EATING } phil_state; /*哲学家状态*/ 
    monitor dp /*管程*/ 

        phil_state state[N]; 
        semaphore mutex =1; 
        semaphore s[N]; /*每个哲学家一个信号量,初始值为0*/ 
        void test(int i) 
        { 
            if ( state[i] == HUNGRY &&state[LEFT(i)] != EATING && state[RIGHT(i)] != EATING ) 
            { 
                state[i] = EATING; 
                V(s[i]); 
            } 
        } 
        void get_forks(int i) 
        { 
            P(mutex); 
            state[i] = HUNGRY; 
            test(i); /*试图得到两支筷子*/ 
            V(mutex); 
            P(s[i]); /*得不到筷子则阻塞*/ 
        } 
        void put_forks(int i) 
        { 
            P(mutex); 
            state[i]= THINKING; 
            test(LEFT(i)); /*看左邻是否进餐*/ 
            test(RIGHT(i)); /*看右邻是否进餐*/ 
            V(mutex); 
        } 


    哲学家进程如下: 
    void philosopher(int process)

        while(true) 
        { 
            think(); 
            get_forks(process); 
            eat(); 
            put_forks(process); 
        } 


    看完上面想必大家有点转晕了,来几道题,熟悉下。


    【例1】生产者-消费者问题
    在多道程序环境下,进程同步是一个十分重要又令人感兴趣的问题,而生产者-消费者问题是其中一个有代表性的进程同步问题。下面我们给出了各种情况下的生产者-消费者问题,深入地分析和透彻地理解这个例子,对于全面解决操作系统内的同步、互斥问题将有很大帮助。

    (1)一个生产者,一个消费者,公用一个缓冲区。
    定义两个同步信号量:
    empty——表示缓冲区是否为空,初值为1。
       full——表示缓冲区中是否为满,初值为0。
    生产者进程
    while(TRUE){
    生产一个产品;
         P(empty);
         产品送往Buffer;
         V(full);
    }
    消费者进程
    while(True){
    P(full);
       从Buffer取出一个产品;
       V(empty);
       消费该产品;
       }
    (2)一个生产者,一个消费者,公用n个环形缓冲区。
    定义两个同步信号量:
    empty——表示缓冲区是否为空,初值为n。
    full——表示缓冲区中是否为满,初值为0。

        设缓冲区的编号为1~n-1,定义两个指针in和out,分别是生产者进程和消费者进程使用的指
    ,指向下一个可用的缓冲区。
    生产者进程
    while(TRUE){
         生产一个产品;
         P(empty);
         产品送往buffer(in);
         in=(in+1)mod n;
         V(full);
    }

    消费者进程
    while(TRUE){
     P(full);
       从buffer(out)中取出产品;
       out=(out+1)mod n;
       V(empty);
       消费该产品;
       }
    (3)一组生产者,一组消费者,公用n个环形缓冲区
        在这个问题中,不仅生产者与消费者之间要同步,而且各个生产者之间、各个消费者之间还必须互斥地访问缓冲区。
    定义四个信号量:
    empty——表示缓冲区是否为空,初值为n。
    full——表示缓冲区中是否为满,初值为0。
    mutex1——生产者之间的互斥信号量,初值为1。
    mutex2——消费者之间的互斥信号量,初值为1。

        设缓冲区的编号为1~n-1,定义两个指针in和out,分别是生产者进程和消费者进程使用的指针,指向下一个可用的缓冲区。
    生产者进程
    while(TRUE){
         生产一个产品;
         P(empty);
         P(mutex1);
         产品送往buffer(in);
         in=(in+1)mod n;
         V(mutex1);
         V(full);
    }
    消费者进程
    while(TRUE){
     P(full)
       P(mutex2);
       从buffer(out)中取出产品;
       out=(out+1)mod n;
       V(mutex2);
       V(empty);
       消费该产品;
       }
      需要注意的是无论在生产者进程中还是在消费者进程中,两个P操作的次序不能颠倒。应先执行同步信号量的P操作,然后再执行互斥信号量的P操作,否则可能造成进程死锁。

    【例2】桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用,请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

    分析在本题中,爸爸、儿子、女儿共用一个盘子,盘中一次只能放一个水果。当盘子为空时,爸爸可将一个水果放入果盘中。若放入果盘中的是桔子,则允许儿子吃,女儿必须等待;若放入果盘中的是苹果,则允许女儿吃,儿子必须等待。本题实际上是生产者-消费者问题的一种变形。这里,生产者放入缓冲区的产品有两类,消费者也有两类,每类消费者只消费其中固定的一类产品。

        解:在本题中,应设置三个信号量S、So、Sa,信号量S表示盘子是否为空,其初值为l;信号量So表示盘中是否有桔子,其初值为0;信号量Sa表示盘中是否有苹果,其初值为0。同步描述如下:
    int S=1;
    int Sa=0;
    int So=0;
          main()
          {
            cobegin
                father();      /*父亲进程*/
                son();        /*儿子进程*/
                daughter();    /*女儿进程*/
            coend
        }
        father()
        {
            while(1)
              {
                P(S);
                将水果放入盘中;
                if(放入的是桔子)V(So);
                else  V(Sa);
               }
         }
        son()
        {
            while(1)
              {
                 P(So);
                 从盘中取出桔子;
                 V(S);
                 吃桔子;
                }
        }
        daughter()
        {
             while(1)
                {
                  P(Sa);
                  从盘中取出苹果;
                  V(S);
                  吃苹果;
                }

     
    思考题:

    四个进程A、B、C、D都要读一个共享文件F,系统允许多个进程同时读文件F。但限制是进程A和进程C不能同时读文件F,进程B和进程D也不能同时读文件F。为了使这四个进程并发执行时能按系统要求使用文件,现用PV操作进行管理,请回答下面的问题:
        (1)应定义的信号量及初值:                    。
        (2)在下列的程序中填上适当的P、V操作,以保证它们能正确并发工作:
         A()                B()                  C()                 D()
          {                 {                    {                  {
          [1];                [3];                  [5];                 [7];
          read F;             read F;                read F;              read F;
         [2];                [4];                  [6];                 [8];
          }                  }                    }                  } 

        思考题解答:
    (1)定义二个信号量S1、S2,初值均为1,即:S1=1,S2=1。其中进程A和C使用信号量S1,进程B和D使用信号量S2。
    (2)从[1]到[8]分别为:P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2)

    1、测量控制系统中的数据采集任务把所采集的数据送一单缓冲区;计算任务则 从该缓冲区中取出数据并进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。

           Var Sempty,Sfull: semaphore:= 1,0

    Begin

                  Parbegin

                  Collection:begin

                  repeat

                         采集一个数据;

                         wait(Sempty);

                         数据放入缓冲区;

                         signal(Sfull);

                  untill false;

                  end;

                  Compute:begin

                  repeat

                         wait(Sfull);

                         从缓冲区取出数据;

                         signal(Sempty);

                         计算;

    `                    until false;

                         end;

                  Parend

           End

    2、有一阅览室,共有100个座位。读者进入时必须先在一种登记表上登记,该表为每一座位列一个表目,包括座号和读者姓名。读者离开时要注销掉登记内容。试用wait和signal原语描述读者进程的同步问题。

           var mutex, readcount :semaphore := 1,100;

    Begin

                  Parbegin

                  Process Reader:begin

                  repeat

                  wait(readcount);

                  wait(mutex);

                  <填入座号和姓名完成登记>;

                  signal(mutex);

    <阅读>

                  wait(mutex)

           <删除登记表中的相关表项,完成注销>

                  signal(mutex);

                  signal(readcount);

                  until false;

                  end;

                  parend;

           End;

    1)、桌上有一空盘,只允许放一个水果,爸爸专向盘中放苹果,妈妈专向盘中放桔子;女儿专吃盘中的苹果,儿子专吃盘中的桔子;试用wait和signal原语实现爸爸、妈妈、女儿、儿子之间的同步问题。

    var Sempty, Sapple, Sorange,: semaphore:= 1,0,0;

     begin

           parbegin

                  Father: begin

                                repeat

                                       wait(Sempty);                                <put apple in tray>;

                                       signal(Sapple);                         until false;

                           end;

                  Mother: begin

                                repeat

                                       wait(Sempty);                                <put orange in tray>;

                                       signal(Sorange);                       until false;

                            end;

                  Son: begin

                                repeat

                                       wait(Sorange);

                                       <take orange>;

                                       signal(Sempty);

                                until false;

                          end;

                  Daughter: begin

                                repeat

                                       wait(Sapple);

                                       <take apple>;

                                       signal(Sempty);                       until false;

                           end;

                  parend;

    end;

    1、在4×100米接力赛中,4个运动员之间存在如下关系,运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交给运动员3,运动员3也只有在接到运动员2传来的棒后才能跑,他跑完100米后交给运动员4,运动员4接到棒后跑完全程。请试用信号量机制对其上过程进行分析。

            

           var s1,s2,s3:semaphpre:=0,0,0;

           begin

                  parbegin

                         Athlete1: begin

                                       Run100m;

                                       signal(s1);

                                    end;

                         Athlete2: begin

                                       wait(s1);

                                       Run100m;

                                       signal(s2);

                                    end;

                         Athlete3: begin

                                       wait(s2);

                                       Run100m;

                                       signal(s3);

                                    end;

                         Athlete4: begin

                                       wait(s3);

                                       Run100m;

                                    end;

                  parend;

           end

     

    2、在公共汽车上,司机和售票员各行其职,司机负责开车和到站停车;售票员负责售票和开、关车门;当售票员关好车门后驾驶员才能开车行驶。试用wait和signal操作实现司机和售票员的同步。

    var s1,s2:semaphore:=0,0;

    begin

           parbegin

                  Process Driver

                  begin

                  repeat

                         <go right>;

                         <stop bus>;

                         signal(s2);

                         wait(s1);

                  until false;

                  end;

                  Process BookingClerk;

                  begin

                  repeat

                         <ticketing>;

                         wait(s2);

                         <open the door>;

                         <close the door>;

                         signal(s1);

                  until false

                  end;

           parend;

    end;

    1、假设有3个并发进程P,Q,R,其中P负责从输入设备上读入信息,并传送给Q,Q将信息加工后传送给R,R负责打印输出。进程P,Q共享一个有m个缓冲区组成的缓冲池;进程Q,R共享一个有n个缓冲区组成的缓冲池(假设缓冲池足够大,进程间每次传输信息的单位均小于等于缓冲区长度),请写出满足上述条件的并发程序。(12分)

    var mutex1,mutex2,Sip,Siq,Soq,Sor:semaphore:=1,1,m,0,n,0;

    begin

           parbegin

                  Process P

                  begin

                  repeat

                         <读入信息>

                         wait(Sip);

                         wait(mutex1);

                         <数据放入缓冲区>

                         signal(mutex1);

                         signal(Siq);

                  until false

                  end;

                  Process Q

                  begin

                  repeat

                         wait(Siq);

                         wait(mutex1);

                         <从缓冲区中取出数据>

                         signal(mutex1);

                         signal(Sip);

                         <数据处理〉

                         wait(Soq);

                         wait(mutex2);

                         <处理后的数据放入缓冲区>

                         signal(mutex2);

                         signal(Sor);

                  until false

                  end;

                  Process R

                  repeat

                         wait(Sor);

                         wait(mutex2);

                  <把数据送入打印机完成打印>;

                         signal(mutex2);

                         signal(Soq);

                  until false

                  end

           parend

    end

     

    2、有一只铁笼子,每次只能放入一只动物,猎手向笼子里放入老虎,农民向笼子里放入猪;动物园等待取笼子里的老虎,饭店等待取笼子里的猪。现请用wait和signal操作写出能同步执行的程序。

    var Sempty, Stiger, Spig,: semaphore:= 1,0,0;  

    begin

           parbegin

                  Hunter: begin

                                repeat

                                       wait(Sempty);

                                       <put tiger in cage>;

                                       signal(Stiger);

                                until false;

                           end;

                  Farmer: begin

                                repeat

                                       wait(Sempty);

                                       <put pig in cage>;

                                       signal(Spig);

                                until false;

                            end;

                  Zoo: begin

                                repeat

                                       wait(Stiger);

                                       <take tiger>;

                                       signal(Sempty);

                                until false;

                          end;

                  Hotel: begin

                                repeat

                                       wait(Spig);

                                       <take pig>;

                                       signal(Sempty);         until false;

                           end;

                  parend;

    end;

    更多相关内容
  • 是线程同步问题的读者写者算法,包括读者优先和写者优先。里面有实验报告,详细说明了实验原理及执行过程,字数够了吗吗
  • 操作系统经典例题——同步与互斥,里面收集了往年清华大学、西安电子科技大学的一些经典题目,难度系数中等,可以供考研第一阶段的复习巩固。
  • 操作系统经典同步问题总结总结
  • 经典同步问题

    千次阅读 2018-03-30 09:02:59
    进程同步: 进程同步机制的主要任务,是对多个相关进程在执行次序上进行协调,使并发执行的诸进程之间能按照一定的规则(或时序)共享系统资源,并能很好的互相合作,从而使程序的执行具有可再现性。 临界资源: ...

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

    临界资源:
    是在一段时间内只允许一个进程访问的资源。系统中的大多数的物理设备,以及栈、变量、表格,都属于临界资源,这些进程间应采用互斥方式,实现对这些资源的共享。

    临界区:
    每个进程中访问临界资源的代码称为临界区。
    若能保证进程互斥的进入自己的临界区,便可实现进程对临界资源的互斥访问。如果某一时间临界资源未被访问,进程便可进入临界区对该资源进行检查,看是否被访问;如果某一时间该临界资源被访问,该进程不能进入临界区。

    while(TRUE)
    {
        进入区
        临界区
        退出区
        剩余区
    }

    同步机制应遵循的规则:
    1.空闲让进:
    无进程处于临界区时,表名临界资源处于空闲状态,允许一个请求进入临界资源区的进程立即进入自己的临界区。
    2.忙则等待:
    当有进程进入临界区时,表明资源正在被访问,其他想进入该临界区的资源必须等待,以保证对临界资源的互斥访问。
    3.有限等待:
    对要求访问资源的进程,应保证在有限的时间内能进入自己的临界区,以避免陷入“死等”状态。
    4.让权等待:
    当进程不能进入自己的临界区时,应立即释放处理机,以避免进程进入“忙等”状态。

    实际上,在对临界区资源进行管理的时候,可以将标志看做一个“锁”,“锁开”进入,“锁关”等待, 起初锁是打开的。每个要进入临界资源的进程必须先对锁进程测试,当锁未开时,则必须等待,直至锁被打开。反之,当锁是打开的,则应立即把锁锁上,以阻止其他进程进入临界区。显然,测试和关锁必须是连续的,不允许分开执行。

    解决临界区的问题:
    1.关中断是最简单实现互斥的方法。在进入锁测试之前关闭中断,直到完成锁测试并上锁后才能打开中断。
    因此,进程在临界区执行期间,计算机系统不断相应中断,从而不会引发调度,也就不会发生进程或线程切换。保证了对锁测试的和关锁测试的完整性和连续性。

    缺点:
    滥用关中断权利可能导致严重后果;
    关中断时间过长,会影响系统效率,限制了处理器交叉执行程序的能力;
    不适用于多处理器系统,因为在一个处理器上关中断并不能防止进程在其他处理器上执行相同的代码。

    经典进程同步问题

    1.生产者-消费者问题

    问题描述:有一群生产者进程在生产产品,并将这些产品提供给消费者进程进行消费,为生产者进程与消费者进程能并发执行,在两者之间设置了一个具有n个缓冲区的缓冲池,生产者进程将其所生产的产品放入一个缓冲区中;消费者进程可以从一个缓冲区中取走产品去消费。

    尽管所有的生产者进程和消费者进程都是以异步方式运行的,但它们之间必须保持同步,既不允许消费者进程到一个空缓冲区去取产品,也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

    我们可以利用一个数组buffer来表示上述具有n个缓冲区的缓冲池。每投入一个产品时,缓冲池buffer中暂存产品的数组指针in加1.由于这里由buffer组成的缓冲池是被组织成循环缓冲的,故in=(in+1)%n表示+1操作。输出指针out,out=(out+1)%n,当(in+1)%n==out时,表示缓冲池已满;当in==out时,表示缓冲池为空。此外,还引入一个整型变量count,初始值为0,每当生产者进程向缓冲池中投放(或取走)一个产品后,count加1(或减1)。注意生产者进程和消费者进程共享这些变量。

    虽然生产者程序和消费者程序单独看都是正确的,但若并发执行就会出现差错,问题就在于count加1(或减1)操作在机器语言中被分为三部分:
    register=count;
    register=register+1;
    count=register;
    我们知道,count就是一个不能共同访问的临界资源。

    2.哲学家就餐问题

    问题描述:有5位哲学家,围绕一张圆桌吃饭,桌子上放着5根筷子,每两个哲学家之间放一支。哲学家的动作包括思考和进餐,进餐时需要同时拿到左右两边的叉子,思考时将两支叉子放回原处。
    问题:如何保证哲学家的动作有序进行?
    这里写图片描述

    方案一:
    利用信号量解决

    #define N 5   //哲学家个数
    semaphore chop[5];//信号量初值为1
    void phil(int i)//哲学家编号:0-4
    {
       while(TRUE){
         think();//哲学家思考
         P(chop[i]);//拿左边的筷子
         P(chop[i+1]%N);//拿右边的筷子
         eat();//进食
         V(chop[i]);//放下左边的筷子
         V(chop[i+1]%N);//放下右边的筷子
         }
    }

    缺点:当每个哲学家都先拿左边的筷子,都陷入等待状态,进入死锁的状态。

    方案二:

    #define N 5   //哲学家个数
    semaphore chop[5];//信号量初值为1
    semaphore mutex;//互斥信号量,初值1
    void phil(int i)//哲学家编号:0-4
    {
       while(TRUE){
         think();//哲学家思考
         P(mutex);//进入临界区
         P(chop[i]);//拿左边的筷子
         P(chop[i+1]%N);//拿右边的筷子
         eat();//进食
         V(chop[i]);//放下左边的筷子
         V(chop[i+1]%N);//放下右边的筷子
         V(mutex);//退出临界区
         }
    }

    保证大家顺序吃饭,互斥访问正确,但只允许一人进餐,效率低。

    方案三:

    #define N 5   //哲学家个数
    semaphore chop[5];//信号量初值为1
    void phil(int i)//哲学家编号:0-4
    {
       while(TRUE){
         think();//哲学家思考
         if(i%2 == 0){
             P(chop[i]);//拿左边的筷子
             P(chop[i+1]%N);//拿右边的筷子
         }else{
             P(chop[i+1]%N);//拿右边的筷子
             P(chop[i]);//拿左边的筷子
         }
         eat();//进食
          V(chop[i]);//放下左边的筷子
          V(chop[i+1]%N);//放下右边的筷子
         }
    }

    偶数编号的哲学家先拿左边,再拿右边;奇数编号的哲学家先拿右边的,再拿左边的。可以同时有两位哲学家进行就餐,提高了进餐效率。

    方案四:
    除了方案三的解决方法外,我们可以在方案二的基础上增加以下约束条件:
    至多只允许四个哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够就餐,并在用完时释放出他使用过的两只筷子,从而使更多的哲学家能够就餐。

    方案五:
    利用AND信号量机制解决,即仅当哲学家左右两边的筷子均可使用时,才允许进餐。

    semaphore chop[5];
    do{
       think();
       P(chop[(i+1)%N],chop[i]);//左右筷子同时拿起
       eat();
       V(chop[(i+1)%N],chop[i]);//左右筷子同时释放
    }whiel(TRUE);

    3.读者-写者问题

    问题描述:对共享数据的访问有两类使用者,读者和写者,读者只能读数据,不修改;写者可以读取和修改数据。“读-读”允许,“读-写”互斥,“写-写”互斥,即允许有多个读者读,没有写者时读者才可读,没有读者时写者才可写,没有其他写者时写者才可写。

    semaphore rmutex = 1; wmutex = 1;//互斥锁
    int readcount = 0;
    void reader(){
         do{
              P(rmutex);//关锁
              if (readcount == 0)wait(wmutex);//把写操作锁住,只需要在第一次读时
              readcount++;//读者数目+1
              V(rmutex);//开锁
              read();
    
              P(rmutex);//关锁
              readcount--;//读者数目-1
              if (readcount == 0)V(wmutex);//没有读者,执行写操作
              V(rmutex);//开锁
         } while (TRUE);
    }
    void writer(){
         do{
              P(rmutex);
              write();
              V(rmutex);
         } while (TRUE);
    }
    void main(){
         cobegin
              reader(); writer();
         coend
    }

    readcount记录读者的个数,当readcount=0,表示尚无读者在读,将写操作上锁(只需在第一次读时),若写操作执行成功,读操作便可进行读,readcount+1,执行读操作后,readcount-1。若没有读者读,便可进行写操作。

    展开全文
  • 用信号量解经典同步问题4.1 生产者消费者问题4.2 读者写者问题4.3 狒狒过桥问题4.4 理发师理发问题4.5 哲学家进餐问题 信号量机制是Dijkstra提出的一种卓有成效的进程同步工具。信号量有整形信号量、记录型信号量、...


    信号量机制是Dijkstra提出的一种卓有成效的进程同步工具。信号量有整形信号量、记录型信号量、AND型信号量等,这里主要介绍我们常见的记录型信号量。

    1. 基本结构

    typedef struct {
    	int value;  //信号量值
    	struct process_cntrol_block *list;  //阻塞队列
    }semaphore;
    

    在应用信号量的时候,信号量的值往往是临界资源的数量。当临界资源数量不足时,新的进程就阻塞,并插入到信号量阻塞队列中。

    2. P,V操作

    wait(S)和signal(S)操作是信号量机制的基本操作(通常称作P,V操作),定义如下:

    wait(semaphore *S) {
    	S->value--;  //信号量的值减一
    	if(S->value < 0) block(S->list);  //如果信号量的值小于零,进程阻塞
    
    signal(semaphore *S) {
    	S->value++;  //信号量的值加一
    	if(S->value <= 0) wakeup(S->list);  //唤醒
    }
    

    在实现进程同步时,一般先将S->value的初值设定为临界资源的初始数量,一旦进程要请求一个临界资源,先对代表此进程的信号量执行P操作,也就意味着资源数减一,当该进程运行完毕时,执行V操作,意味着资源数加一。值得注意的是,如果当前资源数量为0,再有进程想请求临界资源,就会在执行P操作时进入阻塞队列,信号量值变为-1,此后执行P操作的进程也都会被阻塞,信号量的绝对值为阻塞的进程数目。

    3. 信号量的应用

    3.1 信号量实现进程互斥

    有了P,V操作,我们就能很简单的实现进程互斥。方法是:设mutex为互斥信号量,初值为1。在需要互斥的临界区前后分别使用P,V操作即可,示意代码如下:

    semaphore mutex = 1;  //一般初值为1的信号量用来实现互斥
    P_A() {  //进程A
    	while(1) {
    		P(mutex);
    		临界区;
    		V(mutex);
    		剩余区;
    	}
    }
    P_B() {  //进程B
    	while(1) {
    		P(mutex);
    		临界区;
    		V(mutex);
    		剩余区;
    	}
    }
    

    在互斥问题中,我们可以把P操作理解成“上锁”,把V操作理解成“解锁”,当P_A和P_B两个进程并发执行时,无论哪一个进程先执行到了P操作,都会接下来执行P操作的进程阻塞,直到前一个进程执行到了V操作为止,这样就实现了临界区的互斥。

    3.2 信号量实现前驱关系

    思路如下:为每一组想要实现前后关系的进程,都分别定义一个信号量,初值设为0,把你想要先执行的进程后面加一个V操作,想要后执行的进程前面加一个P操作。这样一来,你想要后执行的进程如果先执行了,就会因为执行了其前面的P操作而阻塞,直到你想要先执行的进程执行完了,执行V操作后,才能解除阻塞继续执行。以上就是用信号量实现前驱关系的过程。
    假如我们要实现四个语句S1,S2,S3,S4需要按照一定的顺序同步执行,比如S1执行完S2,S3才能执行,S2,S3执行完了S4才能执行,代码如下:

    p1() {S1; V(a); V(b);}
    p2() {P(a); S2; V(c);}
    p3() {P(b); S3; V(d);}
    p4() {P(c); P(d); S4;}
    
    main() {
    	semaphore a,b,c,d = 0;
    	cobegin
    		p1();p2();p3();p4();
    	coend
    }
    

    4. 用信号量解经典同步问题

    4.1 生产者消费者问题

    假定生产者和消费者之间的公用缓冲池有n个缓冲区,生产者可以向缓冲区生产一个产品,消费者可以从缓冲区消耗一个产品,注意:生产者不能同时生产,消费者也不能同时消费,也不能同时生产和消费,当缓冲区空时无法消费,当缓冲区满时无法生产。请用信号量机制解决这一问题。
    解法如下:

    semaphore mutex = 1;  //实现生产与消费、生产与生产、消费与消费
    semaphore full = 0, empty = n;  //full表示已用缓冲区数,empty表示空缓冲区数
    void producer() {
    	while(1) {
    		P(empty);  //每次生产会减少一个空缓冲区,如果没有空缓存区了就阻塞
    	    P(mutex);  //保证互斥
    	    生产一个产品;
    	    V(mutex);  //保证互斥
    	    V(full);  //每次生产增加一个已用缓冲区
    	}
    }
    void consumer() {
    	while(1) {
    		P(full);  //每次消费会减少一个已用缓冲区,如果没有已用缓存区了就阻塞
    	    P(mutex);
    	    消耗一个产品;
    	    V(mutex);
    	    V(empty);  //每次生产增加一个空缓冲区
    	}
    }
    

    4.2 读者写者问题

    假设一个文件可被多个进程共享,我们允许多个进程同时读这个共享对象,但是不允许一个进程写这个共享对象的同时,别的进程进行读或写。换句话说:读和读不互斥,读和写互斥,写和写互斥。请用信号量机制解决这一问题。
    解法如下:

    semaphore rmutex, wmutex = 1; //wmutex用以实现写进程与其它进程的互斥
    int readcount = 0;  //记录读进程的数量
    void reader() {
    	while(1) {
    		P(rmutex);  //见下文解释
    		if(readcount == 0) P(wmutex);  //第一个读进程去把写进程上锁
    		readcount++;  
    		V(rmutex);  //见下文解释
    		读者读;
    		P(rmutex);  //见下文解释
    		readcount--;
    		if(readcount == 0) V(wmutex);  //解锁
    		V(rmutex);  //见下文解释
    	}
    }
    void writer() {
    	while(1) {
    		P(wmutex);  //实现写进程与其他进程都互斥
    		写者写;
    		V(wmutex);
    	}
    }
    

    这个问题的程序中有个关键点,就是明明读进程是不互斥的,为什么还需要rmutex来实现if判断的互斥呢。原因如下:当我们在进程互斥中使用条件语句和数值变化的时候,如果不把那一段也实现互斥的话,很有可能出问题,比如在这段代码中,要是不加第5行和第8行的话:如果一个读进程执行完了第6行,还没有执行第7行的readcount++操作之前,这个读进程被剥夺了处理机,换另一个读进程上处理机运行了,那么另一个读进程就会阻塞在第6行的P操作上,就无法实现多个读者一起读了;10行和13行同理,如果一个读进程执行完了第11行就被剥夺处理机,换上另一个读进程也执行了11行,这样readcount被连减两次,那么这两个进程都能通过12行的if判断,会执行两次V操作,产生错误。

    4.3 狒狒过桥问题

    一个主修人类学、辅修计算机科学的学生参加了一个课题,调查非洲狒狒是否能被教会理解死锁。他找到一处很深的峡谷,在上边固定了一根横跨峡谷的绳索,这样狒狒就可以攀住绳索越过峡谷。同一时刻可以有几只狒狒通过,只要它们朝着相同的方向。但如果向东和向西的狒狒同时攀在绳索上则将发生死锁(狒狒将被卡在中间),因为它们无法在吊在峡谷上时从另一只的背上翻过去。如果一只狒狒想越过峡谷,它必须看当前是否有别的狒狒正在逆向通过。使用信号量写一个避免死锁的程序来解决该问题。
    解法如下:

    semaphore wmutex, emutex, mutex = 1; 
    int wcount, ecount = 0;  //分别记录东西狒狒上绳索的个数
    void west_monkey {
    	while(1) {
    		P(wmutex);  //使if语句互斥
    		if(wcount == 0) P(mutex);  //第一个西狒狒给东狒狒上锁
    		wcount++;
    		V(wmutex);  //使if语句互斥
    		西狒狒过桥;
    		P(wmutex);
    		wcount--;
    		if(wcount == 0) V(mutex);
    		V(wmutex);
    	}
    }
    void east_monkey {  //和上面的一样
    	while(1) {
    		P(emutex);
    		if(ecount == 0) P(mutex);
    		ecount++;
    		V(emutex);
    		西狒狒过桥;
    		P(emutex);
    		ecount--;
    		if(ecount == 0) V(mutex);
    		V(emutex);
    	}
    }
    

    该问题属于读者写者问题的改进,如果完全理解了读者写者问题的解法,那么这个问题也能很快解决。东狒狒之间不互斥,西狒狒之间不互斥,东西狒狒之间互斥,思路是第一个东狒狒给西狒狒上锁,第一个西狒狒给东狒狒上锁,注意if判断也要实现互斥。

    4.4 理发师理发问题

    理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客,则理发师便在理发椅上睡觉。当一个顾客到来时,他必须先叫醒理发师,如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,他们就坐下来等。如果没有空椅子,他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们的行为,要求不能带有竞争条件。
    解法如下:

    semaphore customer, barber = 0;  //一开始没有顾客,理发师也是睡着的
    semaphore mutex = 1;  //互斥信号量
    int empty = N;  //空椅子数量为N
    void Barber() {
    	while(1) {
    		P(customer);  //只有顾客进程的V执行后才能执行,没有顾客就阻塞(睡觉)
    		P(mutex);  //把数量的变化实现互斥,以免影响到顾客进程的if判断语句
    		empty++;  //椅子上的顾客起身
    		V(barber);  //有了一个理发师可以理发
    		V(mutex);
    		理发;
    	}
    }
    void Customer() {
    	P(mutex);
    	if(empty > 0) {
    		empty--;  //不管是不是第一个顾客,来了先得坐凳子上,因为理发师在理发椅上睡觉呢
    		V(customer);  //增加一个顾客,唤醒沉睡的理发师
    		V(mutex); 
    		P(barber);  //消耗一个理发师,没有理发师就阻塞
    		理发;
    	} else {
    		V(mutex);
    		离开;
    	}
    }
    

    这道题本身不难,但其中很多细节的实现需要实现,比如座位是有上限的,这样就不得不设置判断条件和计数,来使超过N个的顾客离开,而加入计数和判断条件后就又要实现其互斥,增加了问题的复杂性。

    4.5 哲学家进餐问题

    五个哲学家共用一张圆桌,分别坐在周围的五张椅子上,在桌子上有五只碗和五只筷子,他们的生活方式是交替地进行思考和进餐。平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能进餐。进餐毕,放下筷子继续思考。请用信号量机制解决。
    这是一个讲解死锁的时候的经典例子,解决这道题的直接思路如下:

    semaphore chopstick[5] = {1,1,1,1,1};
    void philosopher() {
    	while(1) {
    	/*当哲学家饥饿时,总是先拿左边的筷子,再拿右边的筷子*/
    	P(chopstick[i]);
    	P(chopstick[(i+1)%5]);
    	吃饭;
    	V(chopstick[i]);
    	V(chopstick[(i+1)%5]);
    	}
    }
    

    但是这样可能会出现死锁问题:如果所有哲学家都拿起了左手边筷子,五个进程就会死锁。对于避免哲学家进餐问题发生死锁的方法有很多,这里只讲一种:只有当同时一个哲学家能同时拿起左右两只筷子时,才允许拿筷子,解法如下:

    semaphore chopstick[5] = {1,1,1,1,1};
    semaphore mutex = 1;
    void philosopher() {
    	while(1) {
    		P(mutex);
            P(chopstick[i]);
    		P(chopstick[(i+1)%5]);
    		V(mutex);
    		吃饭;
    		V(chopstick[i]);
    		V(chopstick[(i+1)%5]);
    	}
    }
    

    但仅仅这样做还是有问题,如果一个哲学家获得了两只筷子,开始进餐,此时他左边或者右边的哲学家进入了临界区后,被阻塞在第6行或者第7行,那么其他的哲学家就无法进入临界区了,也就是说这个时间只能有一个哲学家进餐,但显然同一时间是可以有不相邻的两个哲学家同时进餐的。
    对这个问题的更好解决方法可以去看Dijkstra在1965年给出的算法。

    展开全文
  • 计算机操作系统课件:第4章进程同步与通信-信号量与经典同步问题02.ppt
  • 经典同步问题及及解决方案

    千次阅读 2018-04-11 22:41:50
    经典同步问题及及解决方案 哲学家问题 1、 问题描述: 一张圆桌上坐着 5 名哲学家,桌子上每两个哲学家之间摆了一根叉子,桌子的中间是一碗米饭,如图所示: 哲学家们倾注毕生精力用于思考和进餐,哲学...

    经典同步问题及及解决方案

    哲学家问题

    1、 问题描述:

    一张圆桌上坐着 5 名哲学家,桌子上每两个哲学家之间摆了一根叉子,桌子的中间是一碗米饭,如图所示:

    mark

    哲学家们倾注毕生精力用于思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿的时候,才试图拿起左、右两根叉子(一根一根拿起)。如果叉子已在他人手上,则需等待。饥饿的哲学家只有同时拿到了两根叉子才可以开始进餐,当进餐完毕后,放下叉子继续思考。

    2、问题分析

    (1)5名哲学家与左右邻居对其中间叉子的访问是互斥关系。同时当哲学家要使用叉子时需要等待两个邻居都放下叉子才行,他们又是同步关系
    (2)解决办法:这里要开5个线程,每个哲学家对应一个线程。最开始想到的办法是:每个哲学家先拿起左叉子,再拿起右叉子。

    //Philosopher i:
    do {
        wait(chopstick[i])        //等左侧的筷子
        wait(chopstick[(i+1) % 5])//等右侧的筷子
             …
            eat
             …
        signal(chopstick[i]);    //放下左侧
        signal(chopstick[(i+1) % 5]);//放下右侧
             …
            think
             …
        } while (1);
    }

    但是这样会存在问题:如果每个哲学家同时拿起左叉子,都在等待右叉子时造成死锁。
    为了防止死锁的发生,可以对哲学家线程施加一些限制条件,比如:
    (1)同时只允许一位哲学家就餐
    (2)对哲学家顺序编号,要求奇数号哲学家先抓左边的叉子,然后再抓他右边的叉子,而偶数号哲学家刚好相反。
    (3)仅当一个哲学家左右两边的叉子都可用时才允许他抓起叉子;

    3、解决方案

    方法1

    //Philosopher i:
    semaphore mutex = 1;
    do {
        wait(mutex);             //当某一人请求用餐时,其他人不能用
        wait(chopstick[i])        //等左侧的筷子
        wait(chopstick[(i+1) % 5])//等右侧的筷子
             …
            eat
             …
        signal(chopstick[i]);    //放下左侧
        signal(chopstick[(i+1) % 5]);//放下右侧
        signal(mutex);
             …
            think
             …
        } while (1);
    }

    这里把就餐(而不是叉子)看做是互斥访问的临界资源,因此会造成(叉子)资源的浪费。从理论上说,如果有五把叉子,应允许两个不相邻的哲学家同时进餐。

    方法2

    //Philosopher i:
    
    do {
        if(i%2==1){
        wait(chopstick[i]);        //等左侧的筷子
        wait(chopstick[(i+1) % 5]);//等右侧的筷子
        }
        else{
        wait(chopstick[(i+1)%5]); //等待右侧的筷子
        wait(chopstick[i]);        //等左侧的筷子     
        }
             …
            eat
             …
        signal(chopstick[i]);    //放下左侧
        signal(chopstick[(i+1) % 5]);//放下右侧
             …
            think
             …
        } while (1);
    }

    规定奇数号哲学家先拿左筷子再拿右筷子,而偶数号哲学家相反。这样请求资源时,不会出现相互等待,死等的情况。

    生产者消费者问题

    最简单的情形–(一个生产者 + 一个消费者 + 一个大小为1的有限缓冲)

    其中的同步关系:

    • 必须在生产者放入一个产品之后,消费者才能够从缓冲中取出产品来消费。
    • 只有在消费者从缓冲区中取出产品(消费)之后,生产者才能再放新的产品进缓冲区。

    缓冲区的状态决定了生产者和消费者的行为:
    - 空——只能放,不能取
    - 满——只能取,不能放

    设置两个信号量empty = 1,full = 0;

    semaphore empty=1; 
    semaphore full=0; 
    Producer:
    while(true){
        //生产一个产品;
        wait(empty);
        //送产品到缓冲区;
        signal(full);
    };
    
    Consumer:
    while(true){
        wait(full);
        //从缓冲区取产品
        signal(empty);
        //消费产品
    };

    一个消费者+一个生产者+n个buffer

    我们使用了两个信号量:full 和 empty 。
    信号量mutex作为互斥信号量,它用于控制互斥访问缓冲池,互斥信号量初值为 1;
    信号量 full 用于记录当前缓冲池中“满”缓冲区数,初值为0。
    信号量 empty 用于记录当前缓冲池中“空”缓冲区数,初值为n。
    新的数据添加到缓存中后,full 在增加,而 empty 则减少。
    如果生产者试图在 empty 为0时减少其值,生产者就会被“催眠”。下一轮中有数据被消费掉时,empty就会增加,生产者就会被“唤醒”。

    semaphore mutex=1; //临界区互斥信号量
    semaphore empty=n;  //空闲缓冲区
    semaphore full=0;  //缓冲区初始化为空
    producer ()//生产者进程 
    {
        while(1)
        {
            //生产数据
            wait(empty);  //获取空缓冲区单元
            wait(mutex);  //进入临界区.
            //将数据放入缓冲区
            i = (i+1)%n;
            signal(mutex);  //离开临界区,释放互斥信号量
            signal(full);  //满缓冲区数加1
        }
    }
    
    consumer ()//消费者进程
    {
        while(1)
        {
            wait(full);  //获取满缓冲区单元
            wait(mutex);  // 进入临界区
            //从缓冲区中取出数据
            j = (j+1)%n;
            signal (mutex);  //离开临界区,释放互斥信号量
            signal (empty) ;  //空缓冲区数加1
            //消费数据
        }
    }
    

    m个生产者+k个消费者+n个缓冲区

    1)用两个信号量empty,full;
    2)m个生产者之间要互斥,n个消费者之间也要互斥,同时要求生产者和消费者互斥存取物品,
    因此设两个计数器i,j和一个互斥信号量mutex.

    semaphore mutex1=1; //生产者临界区互斥信号量
    semaphore mutex2=1//消费者临界区互斥信号量
    semaphore empty=n;  //空闲缓冲区
    semaphore full=0;  //缓冲区初始化为空
    producer ()//生产者进程 
    {
        while(1)
        {
            //生产数据
            wait(empty);  //获取空缓冲区单元
            wait(mutex1);  //进入临界区.
            //将数据放入缓冲区
            i = (i+1)%n;
            signal(mutex1);  //离开临界区,释放互斥信号量
            signal(full);  //满缓冲区数加1
        }
    }
    
    consumer ()//消费者进程
    {
        while(1)
        {
            wait(full);  //获取满缓冲区单元
            wait(mutex2);  // 进入临界区
            //从缓冲区中取出数据
            j = (j+1)%n;
            signal (mutex2);  //离开临界区,释放互斥信号量
            signal (empty) ;  //空缓冲区数加1
            //消费数据
        }
    }

    司机&售票员

    要求:
    先关门,后开车;
    先形势,后售票;
    先停车,后开门;

    mark

    司机:
    等待关门,启动,行驶,停车

    售票员:
    关门,等待行驶,售票,等待停车,开门

    semaphore door=1;     //door=1开门, =0关门 
    semaphore stop=1//1=汽车停止
    semaphore start=0;    //1=启动汽车
    
    Driver(){           //司机
        while(True){
        wait(door);
        //启动汽车;
        signal(start);
        //行驶
        //到站停车
        signal(stop);
        }
    } 
    
    Busserver(){      //售票员
        while(True){
        //关门
        signal(door);
        wait(start);
        //售票
        wait(stop);
        //开门
        }
    }
    

    设有两个优先级相同的进程p1和p2如下。信号量S1和S2的初值均为0,试问P1和P2并发执行结束后,x、y、z的值各位多少?

    进程P1               进程P2
    1)y = 1;             7)x = 1;
    2)y = y+2;          8)x = x +1;
    3)V(S1);              9)P(S1);
    4)z = y+1;          10)x = x+y;
    5)P(S2);              11)V(S2);
    6)y = z + y;          12)z=x+z;

    首先不论P1、P2谁先执行,到语句10)都没问题,
    10)此时x=5,y=3,z=4
    但是如果P1先执行,那么先执行语句6)y=7,后执行12)z=9
    若P2先执行,那么先执行语句12)z=9,后执行6)y=12

    因此,结果为:
    1)P1先执行 x=5,y=7,z=9;
    2) P2先执行 x=5,y=12,z=9;


    假定系统有3个并发进程get 、copy 和put共享缓冲器B1和B2。进程get负责从输入设备上读信息,每读出一条记录后放到B1中。进程copy从缓冲器B1中取出一条记录拷贝后存入B2。进程put取出B2中的记录打印输出。B1和B2每次只能存放一条记录。要求3个进程协调完成任务,使打印出来的与读入的记录个数、次序完全一样。请用记录型信号量写出并发程序。(北大1990年试题)

    解题思路:由于是两个资源B1,B2,分别对应着各自的空状态和满状态。因此,需要4个信号量。

    semaphore fullB1=0;
    semaphore emptyB1=1;
    semaphore fullB2=0;
    semaphore emptyB2=1;
    
    
    get(){
        while(true){
        //输入设备读入数据
        wait(emptyB1);   //等待B1空闲
        //将数据传入B1
        signal(fullB1);
        }
    }
    
    copy(){
        while(ture){
        wait(fullB1);    //B1有数据
        //从B1取出数据
        signal(emptyB1);
        wait(emptyB2);      //B2空闲
        //将数据拷贝到B2
        signal(fullB2);
        }
    }
    
    put(){
        while(true){
        wait(fullB2);       //B2有数据
        //从B2取数据打印
        signal(emptyB2);
        }
    }
    

    读者-写者问题

    读者优先

    读者(reader):只能读
    写者(writer):能读也能写

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

    semaphore mutex = 1;    //更新count时保证互斥
    semaphore wrt = 1;      //读者和写者的互斥访问临界区
    int readcount = 0;  //记录读者的数量
    
    Writer Process{    //写者进程
    wait(wrt);
         …
    //writing;signal(wrt);
    
    }
    
    
    Reader Process{     //读者进程
    wait(mutex);     //更新count时互斥
    readcount++;
    
    if (readcount == 1)
        wait(wrt);     //拥塞写者
    signal(mutex);
         …
    //reading;
         …
    wait(mutex);
    readcount--;        //更新count时互斥
    if (readcount == 0)
        signal(wrt);    //释放写者
    signal(mutex);
    }
    

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

    写者优先

    如果希望写进程优先,即当有读进程正在读共享文件时,有写进程请求访问,这时应禁止后续读进程的请求,等待到已在共享文件的读进程执行完毕则立即让写进程执行,只有在无写进程执行的情况下才允许读进程再次运行。
    所以,需要加一个信号量给写者,用于写者优先。

    /*初始化读者、写者队列为0,初始化临界区资源、读写计数器资源的初始值为1*/  
    int readCount = 0;  
    int writeCount = 0;  
    semaphore read = 1;  
    semaphore readCountSignal = 1;  
    semaphore writeCountSignal = 1;
    semaphore fileSrc=1;        //临界区资源的互斥访问  
    
    reader()  
    {  
          while(true)  
         {  
            wait(read);            //申请令牌  
            wait(readCountSignal); //申请读者队列计数器  
    
            if(!readCount)         //如果读者队列为空,申请文件资源  
               wait(fileSrc);   
            readCount++;  
    
            signal(readCountSignal); //释放读者计数器资源  
            signal(read);            //释放令牌  
    
            ...  
            perform read operation //执行读操作       
            ...  
    
            wait(readCountSignal);     
            readCount--;  
            if(!readCount)          //如果读者队列为空,释放文件资源  
              signal(fileSrc);  
            signal(readCountSignal);   
          }  
    }  
    
    writer()  
    {  
         while(true)  
         {  
           wait(writeCountSignal);  //申请写者计数器资源  
           if(!writeCount)          //如果写者队列为空则申请令牌  
             wait(read);  
           writeCount++;  
           signal(writeCountSignal); //释放写者计数器资源  
           wait(file);               //申请文件资源  
    
           ...  
           perform write operation   //执行写操作
           ...  
    
           signal(fileSrc);          //释放文件资源  
           wait(writeCountSignal);   
           writeCount--;  
           if(!writeCount)           //如果写者队列为空则释放令牌  
              signal(read);  
           signal(writeCountSignal); 
          }  
    }  

    公平竞争

    公平竞争要求:
    1.优先级相同。
    2.写者、读者互斥访问。
    3.只能有一个写者访问临界区。
    4.可以有多个读者同时访问临界资源。

    具体实现:
    1.设置fileSrc信号量实现对临界资源的互斥访问。
    2.设置计数器readCount实现多个读者访问临界资源,通过设置信号readCountsignal实现对readCount计数器的互斥访问。
    3.设置信号量keySignal实现读者和写者的公平竞争。
    4.设置信号量OneSignal实现只有读者队列或写者阻塞在keySignal。

    /* 读者队列初始值为0,其他资源初始值为1*/  
    int readCount = 0;  
    semaphore keySignal = 1;  
    semaphore OneSignal = 1;  
    semaphore readCountSignal = 1;  
    semaphore fileSrc=1;
    
    reader()  
    {  
        while(true)  
        {  
          wait(keySignal);        //申请令牌  
          wait(readCountSignal);   
          if(!readCount)          //为零则申请文件资源  
             wait(fileSrc);  
          readCount++;  
          signal(readCountSignal); 
          signal(keySignal);      //释放令牌  
    
          ...  
          perform read operation  //执行读操作
          ...  
    
          wait(readCountSignal);  
          readCount--;  
          if(!readCount)                //为零则释放文件资源  
             signal(fileSrc);  
        signal(readCountSignal); 
        }  
    }  
    
    writer()  
    {  
         while(true)  
         {  
            wait(OneSignal);     //申请令牌资源  
            wait(keySignal);     //申请令牌  
            wait(fileSrc);       //申请文件资源  
    
            ...  
            perform write operation //执行写操作 
            ...  
    
            signal(fileSrc);    
            signal(keysignal); 
            signal(OneSignal);  
         }  
    } 

    猴子过桥

    一个主修动物行为学、辅修计算机科学的学生参加了一个课题,调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷,横跨峡谷拉了一根绳索(假设为南北方向),这样猴子就可以攀着绳索越过峡谷。只要它们朝着相同的方向,同一时刻可以有多只猴子通过。但是如果在相反的方向上同时有猴子通过则会发生死锁(这些猴子将被卡在绳索中间,假设这些猴子无法在绳索上从另一只猴子身上翻过去)。如果一只猴子相越过峡谷,它必须看当前是否有别的猴子在逆向通过。请使用P/V 操作来解决该问题。
    (南航研究生试题)
    要求
    - 关键在于明确南北的猴子之间互斥,但同一个方向可以允许多只猴子通过,所以临界区可允许多个实例访问。
    - 当一方有猴子在绳索上时,同方向的猴子可继续通过,但此时要防止另一方的猴子跨越绳索。

    int southnum=0;
    int northnum=0;
    semaphore mutex=1;//绳索互斥访问
    semaphore south=1;//南方猴子互斥信号量
    semaphore north=1;//北方猴子互斥信号量
    
    southi(){
        wait(south);
        if(southnum==0)
            wait(mutex);
    
        southnum++;
    
        signal(south);
        signal(mutex);
        //cross越过绳索
    
        wait(south);
        southnum--;
        if(southnum==0)
            signal(mutex);
        signal(mutex);
        signal(south);
    }
    
    
    northi(){
        wait(north);
        if(northnum==0)
            wait(mutex);
    
        northnum++;
    
        signal(north);
        signal(mutex);
        //cross越过绳索
    
        wait(north);
        northnum--;
        if(northnum==0)
            signal(mutex);
        signal(north);
    }

    给出一个并发程序的描述:semaphore X1=X2=Y=1; int c1=c2=0; f1,f2流程如下。问computeA和computeB各自能有多少并发执行,会不会出现饿死?(清华大学)

    procedure f1:
    p(X1)
    if (++c1 == 1) 
    p(Y)
    v(X1)
    compute A
    p(X1)
    if (--c1 == 0) 
    v(Y)
    v(X1)
    
    procedure f2:
    p(X2)
    if (++c2 == 1) 
    p(Y)
    v(X2)
    compute B
    p(X2)
    if (--c2 == 0) 
    v(Y)
    v(X2)
    

    A、B各自能有多个并发执行
    考虑到一种极端情况,f1一直有进程存在,那么f2会饥饿。


    有桥如图所示。车流如箭头所示。桥上不允许两车交会,但允许同方向多辆车依次通过(即桥上可以有多个同方向的车)。用P、V操作实现交通管理以防止桥上堵塞。(北京大学)

    mark

    semaphore mutex=1;//道路互斥访问
    semaphore south=n;//南方互斥信号量记录型
    semaphore north=n;//北方互斥信号量记录型
    
    southi(){
        wait(south);
        wait(mutex);
        //过桥    
        signal(south);
        signal(mutex);
    }
    
    northi(){
        wait(north);
        wait(mutex);
        //过桥    
        signal(north);
        signal(mutex);
    }
    展开全文
  • 典型同步问题模拟处理编程设计与实现.zip
  • 一、问题描述 二、哲学家 i 的进程描述(可能引起死锁) 三、死锁分析 1. 什么情况下会发生死锁 假如五位哲学家同时饥饿,并且都拿起自己左边的筷子,就会使五个 chopstick[i] 信号量变为0,当它们再试图去拿...
  • 1.生产者消费者问题 1.1.问题分析 1.2.如何实现 2.多生产者多消费者问题 2.1.问题描述 2.2.问题分析 2.3.如何实现 1.生产者消费者问题 1.1.问题分析 1.2.如何实现 2.多生产者多消费者问题 多是...
  • 三大经典同步问题——Java代码实现(信号量模拟) 一、代码结构说明 1、common包①JavaSynchronizationTest.java 简单介绍了信号量机制在Java里面的实现:结合synchronized关键字和对象锁机制 /** * PV测试:PV...
  • 经典同步问题(三)---读者写者问题

    万次阅读 多人点赞 2015-08-12 03:06:13
    读者写者问题的信号量和条件变量算法
  • 操作系统(经典同步问题)

    千次阅读 2019-10-31 19:57:02
    王道上操作系统几大经典同步算法 生产者与消费者问题 分析:整个环境由生产者,消费者,缓冲区(临界区)组成,这种题明白以下几点 1)生产者与消费者对缓冲区的访问是互斥的,即某段时间内只允许二者其中一个对...
  • 2.5 经典的进程同步问题(重点!!!) 一、生产者-消费者问题 二、哲学家进餐问题 三、读者-写者问题
  • 生产者、消费者问题 1、互斥关系:生产者进程和消费者进程对缓冲池的访问互斥。 2、同步关系:缓冲池未满生产者才能向其中放入产品;缓冲池非空消费者才能从其中取出产品。 1. 利用记录型信号量解决 semaphore mutex...
  • 经典同步问题--读者和写者问题

    千次阅读 2015-09-03 20:23:31
    读者--写者问题 读者--写者问题是互斥问题的一个概括。一组并发的线程要访问一个共享的对象,例如一个主存中的数据结构, 或者是磁盘上的数据库。有些线程只读对象,其他线程只修改对象。只读对象的线程叫做读者,...
  • [操作系统]经典进程同步问题题库.doc
  • 经典进程同步问题总结

    千次阅读 2020-06-29 16:42:35
    关键词:进程同步;生产者-消费者问题;读者-写者问题;哲学家进餐问题 信号量机制可以实现互斥、...对于一类系统资源的申请和释放,可以设置一个信号量,初始值即为资源的数量(本质上也属于“同步问题”,若无空闲
  • 我们对临界区,临界资源,锁机制详细解读了下,留下了一个问题,就是锁机制只能判断临界资源是否被占用,所以他解决了互斥问题,但是他不能确定前面的进程是否完成,所以他不能用于同步问题中。下面就为你讲解信号量...
  • 操作系统中4类经典同步问题实验。Windows下,包括4个C++代码:生产者与消费者 、读者和写者 、哲学家问题 、理发师问题和1份实验报告
  • 目录生产者-消费者问题1. 问题描述2. 问题分析3. 进程描述代码4. 补充 生产者-消费者问题 1. 问题描述 一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区,只有缓冲区为满时,生产者才把消息放入...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 112,428
精华内容 44,971
关键字:

经典的同步问题