精华内容
下载资源
问答
  • 进程同步问题

    2017-12-26 23:07:00
    我们知道进程之间可以...代码内部的变量是什么值,对我们来说非常困难,而且,如果两个进程同时修改一个变量,可能会出现错误,因此我们引入了“进程同步”的概念。  1、临界区问题  每个进程有一个代码段我们...

      我们知道进程之间可以相互通信,通过访问一组进程共同拥有的代码和空间,这在前面我们已经讨论过了,但是在计算机内部执行那个进程实际上是非常复杂的,进程之间执行的顺序有时候也是不确定的,因此要确定当前代码执行到哪一步,代码内部的变量是什么值,对我们来说非常困难,而且,如果两个进程同时修改一个变量,可能会出现错误,因此我们引入了“进程同步”的概念。

      1、临界区问题

      每个进程有一个代码段我们称为临界区,在该区中的继承可能改变共同变量、更新一个表、写一个文件等,为了防止出现以上的问题,我们需要优化系统来解决上述问题。

      临界区问题的解答需要满足下面三个条件:

      (1)互斥:如果有一个进程在临界区,那么其他进程都不能进入临界区;

      (2)前进:如果没有进程在其临界区执行且有进程需要进入临界区,那么只有那些不在临界区的进程可以选择,而且这种选择不能无限期延迟;

      (3)有限等待:从一个进程做出临界区的请求,直到该请求允许为止,其他进程允许进入临界区的次数为上限。

      2、Peterson算法

    do
    {
         flag[i]=TRUE;
          turn=j;
          while(flag[j] && turn==j);
          临界区
          flag[i]=FALSE;
          剩余区  
    } while(TRUE);   
       

     

      在上述代码中,turn表示那个进程可以进入其临界区,flag[i]=TRUE,表示进程i申请进入临界区

     上述代码满足我们提到的互斥,前进条件和有限等待

      只有当flag[j]==false或者turn==i时,进程i才被允许进入临界区,满足互斥。

      只要flag[j]==true和turn==j成立,进程j就陷入while循环语句,表示等待,当正在执行的进程i退出临界区时,flag[i]=false,那么进程j就可以进入临界区了,满足前进条件。

      只要进程i退出临界区,那么进程j就可以进入临界区,有限等待满足。

      3、信号量

     

      PV操作由P操作原语和V操作原语组成(原语是不可中断的过程),对信号量进行操作,具体定义如下:
          P(S):①将信号量S的值减1,即S=S-1;
                 ②如果S³0,则该进程继续执行;否则该进程置为等待状态,排入等待队列。
          V(S):①将信号量S的值加1,即S=S+1;
                 ②如果S>0,则该进程继续执行;否则释放队列中第一个等待信号量的进程。
      PV操作的意义:我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。

     

      什么是信号量?信号量(semaphore)的数据结构为一个值和一个指针,指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时,表示当前可用资源的数量;当它的值小于0时,其绝对值表示等待使用该资源的进程个数。注意,信号量的值仅能由PV操作来改变。
         一般来说,信号量S³0时,S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源,因此S的值减1;当S<0时,表示已经没有可用资源,请求者必须等待别的进程释放该类资源,它才能运行下去。而执行一个V操作意味着释放一个单位资源,因此S的值加1;若S£0,表示有某些进程正在等待该资源,因此要唤醒一个等待状态的进程,使之运行下去。

     

      利用信号量和PV操作实现进程互斥的一般模型是:
      进程P1              进程P2           ……          进程Pn
      ……                  ……                           ……
      P(S);              P(S);                         P(S);
      临界区;             临界区;                        临界区;
      V(S);              V(S);                        V(S);
      ……                  ……            ……           ……

     

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

     

      PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来,当信号量的值为0时,表示期望的消息尚未产生;当信号量的值非0时,表示期望的消息已经存在。用PV操作实现进程同步时,调用P操作测试消息是否到达,调用V操作发送消息。
        使用PV操作实现进程同步时应该注意的是:

     

        (1)分析进程间的制约关系,确定信号量种类。在保持进程间有正确的同步关系情况下,哪个进程先执行,哪些进程后执行,彼此间通过什么资源(信号量)进行协调,从而明确要设置哪些信号量。
        (2)信号量的初值与相应资源的数量有关,也与P、V操作在程序代码中出现的位置有关。
        (3)同一信号量的P、V操作要成对出现,但它们分别在不同的进程代码中。

     

      4、管程:

     

      信号量机制功能强大,但使用时对信号量的操作分散,而且难以控制,读写和维护都很困难。因此后来又提出了一种集中式同步进程——管程。其基本思想是将共享变量和对它们的操作集中在一个模块中,操作系统或并发程序就由这样的模块构成。这样模块之间联系清晰,便于维护和修改,易于保证正确性。

     

      管程作为一个模块,它的类型定义如下: 
      monitor_name = MoNITOR; 
      共享变量说明; 
      define 本管程内部定义、外部可调用的函数名表; 
      use 本管程外部定义、内部可调用的函数名表; 
      内部定义的函数说明和函数体 
      { 
        共享变量初始化语句; 
      }

     

      从语言的角度看,管程主要有以下特性: 
      (1)模块化。管程是一个基本程序单位,可以单独编译; 
      (2)抽象数据类型。管程是中不仅有数据,而且有对数据的操作; 
      (3)信息掩蔽。管程外可以调用管程内部定义的一些函数,但函数的具体实现外部不可见; 
      对于管程中定义的共享变量的所有操作都局限在管程中,外部只能通过调用管程的某些函数来间接访问这些变量。因此管程有很好的封装性。 
      为了保证共享变量的数据一致性,管程应互斥使用。 管程通常是用于管理资源的,因此管程中有进程等待队列和相应的等待和唤醒操作。在管程入口有一个等待队列,称为入口等待队列。当一个已进入管程的进程等待时,就释放管程的互斥使用权;当已进入管程的一个进程唤醒另一个进程时,两者必须有一个退出或停止使用管程。在管程内部,由于执行唤醒操作,可能存在多个等待进程(等待使用管程),称为紧急等待队列,它的优先级高于入口等待队列。 
    因此,一个进程进入管程之前要先申请,一般由管程提供一个enter过程;离开时释放使用权,如果紧急等待队列不空,则唤醒第一个等待者,一般也由管程提供外部过程leave。 
      管程内部有自己的等待机制。管程可以说明一种特殊的条件型变量:var c:condition;实际上是一个指针,指向一个等待该条件的PCB队列。对条件型变量可执行wait和signal操作:(联系P和V; take和give) 
      wait(c):若紧急等待队列不空,唤醒第一个等待者,否则释放管程使用权。执行本操作的进程进入C队列尾部; 
      signal(c):若C队列为空,继续原进程,否则唤醒队列第一个等待者,自己进入紧急等待队列尾部。

      部分内容引用自:https://www.cnblogs.com/sonic4x/archive/2011/07/05/2098036.html

     

    转载于:https://www.cnblogs.com/PIRATE-JFZHOU/p/8111665.html

    展开全文
  • 经典的进程同步问题

    万次阅读 多人点赞 2018-08-04 14:23:33
    经典的进程同步问题 普通版:一类进程作为生产者,生产产品,生产的产品放入一个缓冲区,消费者从缓冲区中取出产品,需要保证生产者不可以向满的缓冲区中添加产品,消费者不可以从空的缓冲区中取出产品。同一时刻...

    经典的进程同步问题

    普通版:一类进程作为生产者,生产产品,生产的产品放入一个缓冲区,消费者从缓冲区中取出产品,需要保证生产者不可以向满的缓冲区中添加产品,消费者不可以从空的缓冲区中取出产品。同一时刻只可以有一个生产者生产产品或者消费者消费产品。

    升级版可以实现同一个时刻既有生产者生产产品,又有消费者消费产品。但是绝对不可以同一时刻多个生产者生产产品或者多个消费者消费产品。同时使用count记录缓冲区中产品的数量。

    • 生产者消费者问题

      1)生产者进程和消费者进程都以异步方式运行, 但它们之间必须保持同步。

      2)可利用互斥信号量$mutex$实现诸进程对缓冲池的互斥使用(不可以同时既向缓冲区中放入数据,又从缓冲区中拿出数据);利用资源信号量empty和full分别表示缓冲池中空缓冲池和满缓冲池的数量。 假定这些生产者和消费者相互等效

      /*
      in表示放入数据的地址,out表示取出数据的地址
      buffer[n]:表示大小为n的缓冲池(由多个缓冲区组成) 
      mutex,mutex1,mutex2:互斥型信号量,初值为1
      empty,full:资源型信号量,empty表示空缓冲区的数量,full表示满缓冲区的数量
      item:表示一个数据项
      */
      Int in=0,out=0;  
      Item buffer[n];   
      Semaphore mutex1=1,mutex2 = 1,empty=n,full=0;  
      
      //生产者
      Void producer(){ 
       	do{
      		生产一个产品放入nextp;
              
              /*
               * 进入区
               * 先申请资源信号量,在申请互斥信号量
               * mutex1控制同一个时间段内只能有一个生产者生产产品
               */
      		wait(empty);
      		wait(mutex1);
              
              /*临界区*/
      		buffer[in]=nextp;
      		in=(in+1) % n;
              
              /*退出区*/
      		signal(mutex1);
      		signal(full);
              
              /*对计数器count的互斥访问*/
              wait(mutex);
              count++;
              signal(mutex);
      	}while(TRUE)
      }
      
      //消费者
      Void consumer(){ 
          do{
             /*进入区*/
      	   wait(full);
      	   wait(mutex2);     //消费者对缓冲区的互斥访问
             
             /*临界区*/
      	   nextc =buffer[out];          //只有一份
      	   out =(out+1) mod n;
              
             /*退出区*/
      	   signal(mutex2);
      	   signal(empty);
              
              /*对计数器count的互斥访问*/
              wait(mutex);
              count--;
              signal(mutex);
      	   消费 nextc中的产品;                        
      	}while(TRUE)
      }
      
      
      Void main(){
      	cobegin
      	    proceducer();
       	    consumer();
      	coend
      }

      注意:

      1)每个程序的互斥操作wait()和signal()必须成对的出现。

      2)输入进程不可以向满的缓冲池中输入数据,计算进程不可以从空的缓冲池中取数据

      3)在每个程序中的多个wait操作顺序不能颠倒,必须先执行对资源信号量的wait操作,在进行对互斥信号量的wait操作,否则可能引起进程死锁。

      4)可以使用三个互斥信号量mutex、mutex1、mutex2实现同一时刻既有生产者生产,又有消费者消费。

    • 读者—写着问题

      该问题涉计两类进程,第一类进程是读进程Reader,另一类进程是写进程Writer,多个读进程可以同时读一个文件(共享资源),多个写的进程不可以同时写一个文件(对写互斥),并且读的时候不能写,写的时候不能读(对读互斥)。

      1)问题核心:保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。

      2)只要求读文件的进程称为“Reader进程”,其它进程则称为“Writer进程”。

      3)允许多个进程同时读一个共享对象,但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象(共享对象并不是临界资源,因为他允许多个进程对其访问)

      /*
      记录型信号量解决读者—写者问题
      
      rmutex:读进程对Readcount的互斥
      wmutex:writer对reader和writer的互斥
      readcount:表示正在读的进程数目,只有当readcount=0的时候才需要申请wmutex权限,大于0的时候不需要
      */
      
      semaphore rmutex=1, wmutex =1;
      int readcount =0;
      Void Reader(){
      	do{
      		wait(rmutex);          //防止多个reader进程对readcount的访问
      		if (Readcount==0){    //如果readcount不等于0,表示有进程正在进行读操作,绝对没有写操作
      			wait(wmutex);
      		}
      		Readcount ++;
      		signal(rmutex);
      		…
      		读;
      		…
      		wait(rmutex);
      		Readcount - -;
      		if (Readcount==0){      //只有等于0的时候才需要释放资源,使得写进程可以工作
      			signal(wmutex);
      		}
      		signal(rmutex);
      	}while(TRUE);
      }
      Void writer(){
          do{
              wait(wmutex);      //申请写权限的资源
              写;
              signal(wmutex);
          }while(TRUE);
      }
      
      Void main(){
          cobegin
             reader();  writer();
      	Coend
      }

      利用信号量集的机制实现读者-写者问题

      int RN;
      semaphore L = RN;             //表示读者的数量
      mx = 1;						//对写者进行互斥的访问
      
      void Reader(){
          while(true){
              Swait(L, 1, 1);         //申请一个读者进程
              Swait(mx, 1, 0);       //判断当前是否有写者进程在写,该出相当于一个开关
              
              operation...
                  
              Ssignal(L, 1);
          }
      }
      
      void Writer(){
          while(true){
              //此处首先申请一个mx,如果当前系统中无写者进程,则该语句必定执行成功,Reader进程中的
              //Swait(mx, 1, 0)便处于关闭状态,只需要等系统中的读进程执行完毕,(L, RN,0)执行成
              //功,打开开关即可。
              Swait(mx, 1, 1; L, RN, 0);
              
              operation...;
              
              //释放一个写进程
              Ssignal(mx, 1);
          }
      }
      
      void main(){
          cobegin
              Reader();
          	Writer();
          coend;
      }

       

    • 哲学家的进餐问题

      五个哲学家共用一张圆桌,分别坐在周围的五张椅子上,在桌子上有五只碗和五只筷子,他们的生活方式是交替地进行思考和进餐。平时,一个哲学家进行思考,饥饿时便试图取用其左右最靠近他的筷子,只有在他拿到两只筷子时才能进餐。进餐毕,放下筷子继续思考。

      /*
      记录型信号量解决问题
      */
      //每一只筷子均为临界资源
      semaphore chopstick[5]={1,1,1,1,1};
      //所有的信号量均被初始化为1,第i位哲学家的活动可描述为:
      do{
      	wait(chopstick[i]);          //拿左手的筷子
      	wait(chopstick[(i+1) mod 5] );      //拿右手的筷子
      	…
      	eat;
      	…
      	signal(chopstick[i]);    //放左手
      	signal(chopstick[(i +1)mod 5]);       //放右手
      	…
      	think;
      }while(TRUE);

      存在的问题:假如五位哲学家同时饥饿而各自拿起左边的筷子时,就会使五个信号量chopstick均为0,当他们再试图去拿右边的筷子时,都将因无筷子可拿而无限等待。进入死锁状态。

      解决办法:

      **1)**至多只允许有四位哲学家同时去拿左边的筷子,最终能保证至少有一位哲学家能够进餐,并在用毕后释放出他用过的两只筷子,从而使更多的哲学家能够进餐。

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

      **2)**仅当哲学家的左右两只筷子均可用时,才允许他拿起筷子进餐。

      /*
      使用AND型信号量解决,本质当同时拥有两只筷子的时候才允许拿起筷子进餐
      */
      semaphore chopstick[5]={1,1,1,1,1};
      Philosopher i
      do{
      	think;
      	Swait(chopstick[(i+1)mod 5],chopstick[i ]);     //同时分配两只筷子
      	eat;
      	Ssignal(chopstick[(i+1)mod 5], chopstick[i ] );     //同时放下两只筷子  
      }while(TRUE)

      **3)**规定奇数号哲学家先拿他左边的筷子,然后再去拿右边的筷子;偶数号哲学家则相反。

      semaphore chopstick[5]={1,1,1,1,1};
      //第i 位哲学家的活动可描述为:
      do{
          //奇数位哲学家先拿左手的筷子
      	if  i mod 2=1 {
      		wait(chopstick[ i ]);
      		wait(chopstick[ ( i +1) mod 5] )
      	}
          //偶数位哲学家先拿右手边的筷子
      	else
      	{
      		wait(chopstick[ ( i +1) mod 5] );
      		wait(chopstick[ i ])
      	}
      	eat;
      	signal(chopstick[ i ]);
      	signal(chopstick[(i +1)mod 5]);
      	…
      	think;
      }while(TRUE)

     

    展开全文
  • 进程同步问题习题.doc

    2020-12-15 23:35:39
    进程同步问题习题.doc
  • 操作系统进程同步问题
  • 进程同步问题实例

    2020-10-06 10:43:31
    进程同步问题实例(参考): 1、 桌上有个能盛得下五个水果的空盘子,爸爸不停地向盘中放苹果或桔子,儿子不停地从盘中取出桔子享用,女儿不停地从盘中取出苹果享用。规定三人不能同时从盘中取放水果。试用信号量...

    进程同步问题实例(参考):
    1、 桌上有个能盛得下五个水果的空盘子,爸爸不停地向盘中放苹果或桔子,儿子不停地从盘中取出桔子享用,女儿不停地从盘中取出苹果享用。规定三人不能同时从盘中取放水果。试用信号量实现爸爸、儿子和女儿这三个循环进程之间的同步。
    分析:本题是生产者—消费者问题的变形,相当于一个能生产两种产品的生产者(爸爸)向两个消费者(儿子和女儿)提供产品的同步问题,因此,需设置两个不同的full信号量apple和orange,初值均为0。

    Semaphore empty=5,orange=0,apple=0,mutex=1;
    Int buffer[5];
    Dad(){
    Int nextp;
    While(1){
    Wait(empty);
    Wait(mutex);
    Buffer[in]:=nextp;
    Signal(mutex);
    If(buffer[in]=orange)
    Signal(orange);
    Else signal(apple);
    }
    }
    Son(){
    Int nexts;
    While(1){
    Wait(orange);
    Wait(mutex);
    Nexts:=buffer(out);
    Signal(mutex);
    Signal(empty);
    Eat;
    }
    }
    

    2、 请用信号量解决以下的“过独木桥”问题:同一方向的行人可连续过桥,当某一方向有人过桥时,另一方向的行人必须等待;当某一方向无人过桥时,另一方向的行人可以过桥。

    Semaphore bridge=1;(用来实现不同方向行人对桥的互斥共享)
    Semaphore mutexA=mutexB=1;
    Int countA=countB=0;(分别表示A、B两个方向过桥的行人数量)
    PA(){
    Wait(mutexA);
    If(countA==0) wait(bridge);
    countA++;
    signal(mutexA);
    过桥;
    Wait(mutexA);
    countA--;
    if(countA==0)signal(bridge);
    signal(mutexA);
    }
    

    B方向行人的算法与A方向行人算法类似。

    3、 有一间酒吧里有3个音乐爱好者队列,第1队的音乐爱好者只有随身听,第2队的音乐爱好者只有音乐磁带,第3队的音乐爱好者只有电池。而要听音乐就必须随身听、音乐磁带和电池这三种物品俱全。酒吧老板一次出售这三种物品中的任意两种。当一名音乐爱好者得到这三种物品并听完一首乐曲后,酒吧老板才能再一次出售这三种物品中的任意两种,于是第2队音乐爱好者得到这三种物品,并开始听乐曲。全部买卖就这样进行下去。试用信号量实现他们的同步关系。
    分析:根据题意,当酒吧老板提供两种物品时,必须被同一个音乐爱好者取走,我们应把每两种物品看成是一组合起来的临界资源。三个队为它设置一个临界资源信号量S1,S2,S3的初值为0。只有当一个音乐爱好者听完一首乐曲后,老板才能再次出售商品,为这种同步关系设置一个初值为0的信号量

    music_over。
    Semaphore S1=S2=S3=0;
    Semaphore music_over=0;
    Boss(){
    While(1){
    提供任意两种物品出售;
    IF(提供的是音乐磁带和电池)signal(S1);
    Else if (提供的是随身听和电池)signal(S2);
    Else signal(S3);
    Wait(music_over);
    }
    }
    Fan1(){
    Wait(S1);
    买音乐磁带和电池;
    听乐曲;
    Signal(music_over);
    }
    Fan2(){
    Wait(S2);
    买随身听和电池;
    听音乐;
    Signal(music_over);
    }
    Fan3(){
    Wait(S3);
    买到随身听和音乐磁带;
    听乐曲;
    Signal(music_over);
    }
    Main(){
    Cobegin
    Boss(); fan1(); fan2(); fan3();
    Coend;}
    
    展开全文
  • 经典进程同步问题

    2020-10-21 18:37:58
    @[toc] 经典进程同步问题 1 生产者-消费者问题 问题 1 一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区,只有缓冲区没满时,生产者才能把消息放入缓冲区,否则必须等待;只有缓冲区不空时,消费...

    1 生产者-消费者问题

    问题 1

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

    分析:

    生产者和消费者对缓冲区的访问是互斥关系;同时它们之间又存在着同步关系,只有生产者生产之后消费者才能消费,而只有缓冲区未满(消费者一直消费)生产者才能生产产品。

    semaphore mutex = 1;	//用于实现对缓冲区的互斥访问
    semaphore empty = n;	//空闲缓冲区数量
    semaphore full = 0;		//非空闲缓冲区(产品)数量
    
    // 生产者进程
    producer(){
    	while(1){
    		生产一个消息;
    		p(empty);
    		p(mutex);
    		将一个消息放入缓冲区;
    		v(mutex);
    		v(full);
    	}
    }
    
    // 消费者进程
    producer(){
    	while(1){
    		p(full);
    		p(mutex);
    		从缓冲区取一个消息;
    		v(mutex);
    		v(empty);
    		消费消息;
    	}
    }
    

    问题 2

    桌上有一个盘子,每次只能向其中放入一个水果。爸爸只放苹果,妈妈只放橘子,女儿只拿苹果,儿子只拿橘子。只有盘子为空时,爸爸或妈妈才能向盘子中放水果,只有盘子不空时,儿子或女儿才能从盘子中拿水果

    分析:

    爸爸、妈妈都向盘子放水果,儿子、女儿都从盘子取水果,儿子取妈妈放的水果,女儿取爸爸放的水果。因此爸爸妈妈、儿子女儿各自之间为互斥关系;爸爸女儿、妈妈儿子各自之间为同步关系

    semaphore plate = 1, apple = 0, orange = 0;
    
    dad(){
    	while(1){
    		准备一个苹果;
    		p(plate);
    		放入一个苹果;
    		v(apple);
    	}
    }
    mom(){
    	while(1){
    		准备一个橘子;
    		p(plate);
    		放入一个橘子;
    		v(orange);
    	}
    }	
    
    son(){
    	while(1){
    		p(orange);
    		拿走一个橘子;
    		v(plate);
    		吃橘子;
    	}
    }
    daughter(){
    	while(1){
    		p(apple);
    		拿走一个苹果;
    		v(plate);
    		吃苹果;
    	}
    }
    

    2 读者-写者问题

    读者优先

    有读者和写者两组并发进程,共享一个文件,当两个或以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(写进程或读进程)同时访问共享数据时则可能导致数据不一致的情况发生。因此要求:

    • ①允许多个读者可以同时对文件执行读操作
    • ②只允许一个写者向文件写消息
    • ③任一写者完成写操作之前不允许其他读者或写者工作
    • ④写者执行写操作前,应让已有的读者和写者全部退出

    分析:

    允许一个或多个读者同时访问、只允许一个写者访问。因此读写互斥、写写互斥。总之,只要有写者,则必须互斥。

    设置互斥信号量 mutex,用于对数据区互斥访问,再设计数器 read_count,用于记录读者数量,当第一个读者到来时,对 mutex 进行p操作,只有最后一个读者离开时,才对 mutex 进行v操作,这样只要有读者,无论来多少个写者都会被阻塞,直到所有读者离开,释放 mutex 。如此便能实现读者优先

    int read_count = 0;  //用于记录读者数量
    semaphore rmutex = 1;//用于对read_count互斥访问
    semaphore mutex = 1; //用于对数据区互斥访问
    
    //写进程
    writer(){
    	while(1){
    		p(mutex);
    		写;
    		v(mutex);
    	}
    }
    
    //读进程
    reader(){
    	while(1){
    		p(rmutex);
    		if(read_count == 0)
    			p(mutex);
    		read_count++;
    		v(rmutex);
    		读;
    		p(rmutex);
    		read_count--;
    		if(read_count == 0)
    			v(mutex);
    		v(rmutex);
    	}
    }
    

    读写公平

    思考读者优先的方案:假设已有读进程正在对文件进行读取,后续又源源不断的有读进程到来,也有写进程到来。只要一直有读进程,则信号量 mutex 就一直得不到释放,则写进程就会一直被阻塞,尽管有的写进程比读进程到来的早。这就会造成写进程长时间被阻塞,甚至”饿死“。

    解决方案:若希望读进程、写进程公平访问文件,则需再设一个信号量 wmutex。当有读进程或写进程到来时,需要先对 wmutex 进行 p 操作,若写进程先到,则先p(wmutex),后续的读进程就会被阻塞;若读进程先到,则先p(wmutex),后续的写进程就会被阻塞。如此便能保证访问的公平性了。

    int read_count = 0;  //用于记录读者数量
    semaphore rmutex = 1;//用于对read_count互斥访问
    semaphore mutex = 1; //用于对数据区互斥访问
    semaphore wmutex = 1;//若已有写者到来,则阻塞后来的读者
    
    //写进程
    writer(){
    	while(1){
    		p(wmutex);
    		p(mutex);
    		写;
    		v(mutex);
    		v(wmutex);
    	}
    }
    
    //读进程
    reader(){
    	while(1){
    		p(wmutex);
    		p(rmutex);
    		if(read_count == 0)
    			p(mutex);
    		read_count++;
    		v(rmutex);
    		v(wmutex);
    		读;
    		p(rmutex);
    		read_count--;
    		if(read_count == 0)
    			v(mutex);
    		v(rmutex);
    	}
    }
    

    写者优先

    仿照读者优先的例子,添加一个互斥信号量readable,让写者对此信号量进行p操作,则只要有写者存在,此信号量由于没被写者释放,则读者一直被阻塞,从而实现写者优先

    semaphore mutex = 1;   //用于互斥访问数据区
    semaphore rmutex = 1;  //用于读者互斥访问read_count
    semaphore wmutex = 1;  //用于写者互斥访问write_count
    semaphore readable = 1;//用于表示当前是否有写者
    int read_count = 0, write_count = 0; //用于记录读者和写者数量
    
    reader(){
    	while(1){
    	    p(readable);
            p(rmutex);
            if(read_count == 0)
                p(mutex);
            read_count++;
            v(rmutex);
            v(readable);
            读;
            p(rmutex);
            read_count--;
            if(read_count == 0)
                v(mutex);
            v(rmutex);
    	}
    }
    
    writer(){
    	while(1){
    		p(wmutex);
    		if(write_count == 0)
    			p(readable);
    		v(wmutex);
    		
    		p(mutex);
    		写;
    		v(mutex);
    		
    		p(wmutex);
    		write_count--;
    		if(write_count == 0)
    			v(readable);
    		v(wmutex);
    	}
    }
    

    3 哲学家进餐问题

    一张圆桌边上坐着五名哲学家,没两名哲学家之间的桌上摆着一根筷子,两根筷子之间时一碗米饭,哲学家不是吃饭就是思考。只有哲学家饥饿时,才试图拿起左右两根筷子(一根一根的拿起)。若筷子已在他人手上,则需要等待。饥饿的哲学家只有同时拿起两根筷子才能进餐,进餐完毕后,放下筷子继续思考。

    初始方案

    定义信号量数组chopstick[5] = {1,1,1,1,1} ,用于对 5 根筷子进行互斥访问。哲学家按顺序编号为0~4,哲学家 i 左边筷子编号为 i ,右边筷子编号为 (i+1)%5 。

    semaphore chopstick[5] = {1,1,1,1,1};
    
    philosopher(){
    	while(1){
    		p(chopstick[i]);
             p(chopstick[(i+1)%5]);
    		吃饭;
    		v(chopstick[i]);
             v(chopstick[(i+1)%5]);		
             思考;
    	}
    }
    

    改进方案

    初始方案中,可能存在一种情况:若每名哲学家都拿起一根筷子时,由于没有人有两根筷子,于是谁也不能进餐,每个人都在等待,因此出现了死锁。

    为防止死锁,可对初始方案用以下三个方法解决

    • 方法一:至多允许 4 名哲学家同时进餐
    • 方法二:仅当一名哲学家左右两边的筷子都可用时,才允许他抓起筷子。这样必有一名哲学家可以拿起 2 根筷子
    • 方法三:对哲学家顺序编号,要求齐数号哲学家先拿起左边的筷子,然后再拿右边的筷子,而偶数号哲学家刚好相反

    方法一:至多允许 4 名哲学家同时进餐

    至多只允许四位哲学家同时去拿左筷子,最终能保证至少有一位哲学家能进餐,并在用完后释放两只筷子供他人使用。设置一个初值为 4 的信号量 num,只允许 4 个哲学家同时去拿左筷子,这样就能保证至少有一个哲学家可以就餐,不会出现饿死和死锁的现象

    semaphore chopstick[5] = {1,1,1,1,1};
    semaphore num = 4;
    
    philosopher(int i){
    	while(1){
    		p(num);					//请求进餐
    		p(chopstick[i]);		 //拿左筷子
             p(chopstick[(i+1)%5]);	  //拿右筷子
    		吃饭;
    		v(chopstick[i]);
             v(chopstick[(i+1)%5]);	
             v(num);
             思考;
    	}
    }
    

    方法二:仅当一名哲学家左右两边的筷子都可用时,才允许他抓起筷子

    将拿左右筷子的操作看成一个连贯的操作,在其周围加上pv操作,从而保证拿起筷子的过程不被打断,保证同时持有左右两根筷子

    semaphore chopstick[5] = {1,1,1,1,1};
    semaphore mutex = 1;
    
    philosopher(){
    	while(1){
    		p(mutex);
    		p(chopstick[i]);
             p(chopstick[(i+1)%5]);
             v(mutex);
    		吃饭;
    		v(chopstick[i]);
             v(chopstick[(i+1)%5]);		
             思考;
    	}
    }
    

    方法三:对哲学家顺序编号,要求齐数号哲学家先拿起左边的筷子,然后再拿右边的筷子,而偶数号哲学家刚好相反

    semaphore chopstick[5] = {1,1,1,1,1};
    
    philosopher(int i){
    	while(1){
    		if(i % 2 != 0) {			//若为奇数号哲学家
    			p(chopstick[i]);		//先拿左筷子
             	 p(chopstick[(i+1)%5]);   //后拿右筷子
             	 吃饭;
                 v(chopstick[i]);
                 v(chopstick[(i+1)%5]);	
                 思考;
    		} else {					//若为偶数号哲学家
    			p(chopstick[(i+1)%5]);    //先拿右筷子
    			p(chopstick[i]);		 //后拿左筷子
             	 吃饭;
                 v(chopstick[(i+1)%5]);
                 v(chopstick[i]);
                 思考;
    		}
    	}
    }
    

    4 吸烟者问题

    假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停的卷烟并抽掉它,但要卷起并抽掉一支烟,抽烟者需要三种材料:烟草、纸、胶水。三个抽烟者分别拥有烟草、纸、胶水。供应者无限提供三种材料,他每次将两种材料放到桌子上,拥有剩下那种材料的抽烟者卷起一根烟并抽掉,并给供应者一个信号告诉已完成,此时供应者会将两外两种材料放到桌子上,如此循环……。

    要求让三个抽烟者轮流抽烟

    int random;
    semaphore offer1 = 0; //对应纸和胶水的资源
    semaphore offer2 = 0; //对应烟草和胶水的资源
    semaphore offer3 = 0; //对应烟草和纸的资源
    semaphore finish = 0;
    
    //供应者进程
    process(){
    	random = 随意一个整数;
    	while(1){
    		flag = random % 3;
    		if(flag == 0)
    			v(offer1);
    		else if(flag == 1)
    			v(offer2);
    		else
    			v(offer3);
    		random++;
    		p(finish);
    	}
    }
    
    //抽烟者进程
    smoker_1(){
    	while(1){
    		p(offer1);
    		拿起纸和胶水,卷烟,抽掉;
    		v(finish);
    	}
    }
    smoker_2(){
    	while(1){
    		p(offer2);
    		拿起胶水和烟草,卷烟,抽掉;
    		v(finish);
    	}
    }
    smoker_3(){
    	while(1){
    		p(offer3);
    		拿起烟草和纸,卷烟,抽掉;
    		v(finish);
    	}
    }
    

    5 理发师问题

    理发店有一位理发师、一把理发椅、n 个供顾客等候用的凳子。若没有顾客,则理发师在理发椅上睡觉。当一位顾客到来时,顾客必须叫醒理发师;若理发师正在理发时又有顾客到来,若有空椅子可坐,则顾客坐下来等待,否则离开。

    分析:

    一把理发椅、n 个供顾客等候用的凳子,则理发店最多可容纳 n+1 人。根据对理发椅处理方法的不同,则有两种解决方法

    • 方法一:将理发椅和凳子看成两种不同的资源
    • 方法二:将理发椅和凳子看成一种资源

    方法一:将理发椅和凳子看成两种不同的资源

    int customer_count = 0;		//记录当前顾客人数
    semaphore mutex = 1;		//用于互斥访问wait_count
    semaphore baber_chair = 1;	//理发椅
    semaphore wait_chair = 1;	//凳子
    semaphore finish = 0;
    semaphore ready = 0;
    
    barber(){
    	while(1){
    		p(ready);	//等候为顾客理发,若无顾客,则睡觉
    		理发;
    		v(finish);	//理发完毕,可为下一位顾客理发
    	}
    }
    customer(){
    	p(mutex);			//互斥访问customers
    	if(customer_count <= n){//还有空位
    		customer_count++;	//进店坐下,空位减一
    		v(mutex);
    	} else {
    		v(mutex);		//没有空位,直接离开
    	}
    	
    	p(wait_chair);		//找一个空凳子坐下
    	p(barber_chair);	//等待坐上理发椅
    	v(wait_chair);		//离开凳子,去坐理发椅
    	v(ready);			//通知理发师理发。若理发师在睡觉,则唤醒之
    	p(finish);			//等待理发完成
    	v(barber_chair); 	//理发完成,离开理发椅
    	p(mutex);			//互斥访问customer_count
    	customer_count--;	//离开,空位加一
    	v(mutex);
    }
    

    方法二:将理发椅和凳子看成一种资源

    int chairs = n+1;
    semaphore ready = 0;
    semaphore finish = 1;
    semaphore mutex = 1;
    
    barber(){
    	while(1){
    		p(ready);	//等候为顾客理发,若无顾客,则睡觉
    		理发;
    		p(mutex);
    		chairs--;
    		v(mutex);
    		v(finish);	//理发完毕,可为下一位顾客理发
    	}
    }
    
    customer(){
    	p(mutex);
    	if(chairs > 0){	//有空位,进店
    		chairs--;
    		v(mutex);
    		v(ready);	//通知理发师理发。若理发师在睡觉,则唤醒之
    		p(finish);	//等待理发完成
    	} else {
    		v(mutex);	//无空位,离开
    	}
    }
    
    展开全文
  • [操作系统]经典进程同步问题题库.doc
  • 2.4经典进程同步问题 1.生产者——消费者问题 无论生产者、消费者使用缓冲池时应保证互斥使用(互斥信号量mutex ) 生产者和消费者间交叉有序: 有序的控制最根源在产品数量上。 设置两个信号量:分别针对生产者、...
  • 进程同步问题(一)

    2020-03-03 21:31:40
    进程同步问题(一)主要任务制约关系临界资源生产者消费者问题临界区的基本概念临界区的使用方法临界区的使用同步机制应遵循的规则信号量机制整型信号量纪录型信号量纪录型信号量的P、V操作如下:利用纪录型信号量...
  • 进程同步问题(主要是PV问题) 先了解基本概念 ​ 因为在多道环境下,进程之间是并发执行的,而程序之间为了抢夺各种资源,相互制约,如果不对这种制约加以协调,操作系统就很容易进入死锁状态,影响进程们的运行。...
  • 常见进程同步问题

    2021-02-23 20:45:40
    文章目录前言一、同步的概念二、经典同步问题1. 哲学家就餐问题2.读入数据总结 前言 进程同步:在多道程序环境下,进程是并发执行的,不同进程之间存在着不同的相互制约关系。 一、同步的概念   我们把异步环境...
  • 经典进程同步问题之生产者消费者问题 什么是生产者消费者问题 学术性描述:生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是:有一群生产者进程在生产产品,并将这些产品提供给消费者进程...
  • 经典进程同步问题 : 生产者—消费者问题(合作互斥) 是相互合作的进程关系的一种抽象,同时也包含着进程的互斥。 分析 : 空缓冲区不为空,生产者才能将生产的数据放入缓冲区中。 满缓冲区不为空,消费者才能从...
  • 进程同步问题——生产者—消费者问题 问题梗概 生产者—消费者问题是相互合作关系的进程关系的一种抽象,是一个广义的概念,可以代表一类具有相同属性的进程 生产者:一个或者是多个生产者将生产的数据存入缓冲区中...
  • 进程同步问题-锁线程

    2017-05-22 17:00:54
    * 处理进程同步问题 * 多个线程访问同一个资源时保证一个线程在一段操作结束前独占cpu * 锁线程 synchronized
  • 经典的进程同步问题-----哲学家进餐问题详解

    千次阅读 多人点赞 2019-11-25 08:33:21
    ​ 本文和接下来几篇博文是对上篇文章(进程同步机制)的一次实践,通过具体的例子来加深理论的理解,会用三个经典的进程同步问题来进行讲解,并且会配有伪代码和Java实践(使用多线程模拟),深入的进行讲解。...
  • 经典的进程同步问题-----读者-写者问题详解 ​ 本文和接下来几篇博文是对上篇文章(进程同步机制)的一次实践,通过具体的例子来加深理论的理解,会用三个经典的进程同步问题来进行讲解,并且会配有伪代码和Java...
  • 操作系统之经典进程同步问题

    千次阅读 2017-12-02 15:20:55
    这里介绍三中进程同步问题:  1.生产者-消费者问题  2.读者-写者问题  3.哲学家进餐问题 一、生产者-消费者问题  1.问题描述:生产者-消费者模型描述的是有一群生产者进程在生产产品,并将这些产品提供给消费...
  • 生产者-消费者问题是一个著名的进程同步问题。 它描述的是:有一群生产者进程在生产产品,并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行,在两者之间设置了一个具有n个缓冲区的缓冲池...
  • 进程同步问题——生产者、消费者问题在这里插入图片描述       生产者、消费者问题是操作系统中个著名的进程同步问题。一般是指: 有一群生产者进程在生产产品,并将此产品提供给消费...
  • 使用win32线程,采用信号量实现进程同步问题--生产者消费者问题。
  • 三 :进程同步 为保证多个程序并发执行时,保留可再现性,在多道程序系统中,必须引入进程同步机制。 进程同步机制的主要任务,是对多个相关进程在执行次序上进行协作,使并发执行的诸进程之间能按照一定的规则(或...
  • 操作系统经典进程同步问题之哲学家进餐问题 哲学家进餐问题 1.问题描述:有五位哲学家,它们的生活方式是交替的进行思考和进餐。哲学家门共用一张圆桌,分别坐在周围的五张椅子上。在圆桌上有五只碗和五根筷子,平时...
  • 经典的进程同步问题-----生产者-消费者问题详解

    千次阅读 多人点赞 2019-11-25 08:32:47
    经典的进程同步问题-----生产者-消费者问题详解 ​ 本文和接下来几篇博文是对上篇文章(进程同步机制)的一次实践,通过具体的例子来加深理论的理解,会用三个经典的进程同步问题来进行讲解,并且会配有伪代码和...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,102
精华内容 3,240
关键字:

进程同步问题