精华内容
下载资源
问答
  • pv原语

    2014-02-14 07:06:38
    PV原语操作详解       PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。 信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出,其基本思路是用一...
    PV原语操作详解 
     
     
      PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。 信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出,其基本思路是用一种新的变量类型(semaphore)来记录当前可用资源的数量。
     
        semaphore有两种实现方式:
     
        1semaphore的取值必须大于或等于0。0表示当前已没有空闲资源,而正数表示当前空闲资源的数量;
        2) semaphore的取值可正可负,负数的绝对值表示正在等待进入临界区的进程个数。
     
        信号量是由操作系统来维护的,用户进程只能通过初始化和两个标准原语(P、V原语)来访问。初始化可指定一个非负整数,即空闲资源总数。
     
        P原语:P是荷兰语Proberen(测试)的首字母。为阻塞原语,负责把当前进程由运行状态转换为阻塞状态,直到另外一个进程唤醒它。操作为:申请一个空闲资源(把信号量减1),若成功,则退出;若失败,则该进程被阻塞;
     
        V原语:V是荷兰语Verhogen(增加)的首字母。为唤醒原语,负责把一个被阻塞的进程唤醒,它有一个参数表,存放着等待被唤醒的进程信息。操作为:释放一个被占用的资源(把信号量加1),如果发现有被阻塞的进程,则选择一个唤醒之。
     
        P原语操作的动作是:
        (1)sem减1;
        (2)若sem减1后仍大于或等于零,则进程继续执行;
        (3)若sem减1后小于零,则该进程被阻塞后进入与该信号相对应的队列中,然后转进程调度。
        V原语操作的动作是:
        (1)sem加1;
        (2)若相加结果大于零,则进程继续执行;
        (3)若相加结果小于或等于零,则从该信号的等待队列中唤醒一等待进程,然后再返回原进程继续执行或转进程调度。

        PV操作对于每一个进程来说,都只能进行一次,而且必须成对使用。在PV原语执行期间不允许有中断的发生。
     
     
    ---------------------------------------------
     
        具体PV原语对信号量的操作可以分为三种情况:
     
        1把信号量视为一个加锁标志位,实现对一个共享变量的互斥访问。
     
        实现过程:
     
        P(mutex); // mutex的初始值为1 访问该共享数据;
        V(mutex);
        非临界区;
     
        2把信号量视为是某种类型的共享资源的剩余个数,实现对一类共享资源的访问。
     
        实现过程:
     
        P(resource); // resource的初始值为该资源的个数N 使用该资源;
        V(resource);
        非临界区;
     
      3把信号量作为进程间的同步工具
     
        实现过程:
     
        临界区C1;
        P(S);
        V(S);
        临界区C2;
     
     
    ---------------------------------------------
     
    举例说明:
     
     
        例1:某超市门口为顾客准备了100辆手推车,每位顾客在进去买东西时取一辆推车,在买完东西结完帐以后再把推车还回去。试用P、V操作正确实现顾客进程的同步互斥关系。
     
        分析:把手推车视为某种资源,每个顾客为一个要互斥访问该资源的进程。因此这个例子为PV原语的第二种应用类型。
     
        解:
     
    semaphore S_CartNum;    // 空闲的手推车数量,初值为100
    void  consumer(void)    // 顾客进程
    {
        P(S_CartNum);
       买东西;
       结帐;
       V(S_CartNum); 
    }
     
     
        例2:桌子上有一个水果盘,每一次可以往里面放入一个水果。爸爸专向盘子中放苹果,儿子专等吃盘子中的苹果。把爸爸、儿子看作二个进程,试用P、V操作使这两个进程能正确地并发执行。
     
        分析:爸爸和儿子两个进程相互制约,爸爸进程执行完即往盘中放入苹果后,儿子进程才能执行即吃苹果。因此该问题为进程间的同步问题。
     
        解:
     
    semaphore  S_PlateNum;  // 盘子容量,初值为1
    semaphore  S_AppleNum;  // 苹果数量,初值为0
    void  father( )  // 父亲进程
    {
        while(1)
        {
            P(S_PlateNum);
            往盘子中放入一个苹果;
            V(S_AppleNum);
        } 
    }
    void  son( )   // 儿子进程
    {
        while(1)
        {
            P(S_AppleNum);
            从盘中取出苹果;
            V(S_PlateNum);
            吃苹果;
        } 
    }
     
    ---------------------------------------------
     
        另附用PV原语解决进程同步与互斥问题的例子:
     
       
        例3两个进程PA、PB通过两个FIFO(先进先出)缓冲区队列连接(如图)
        pv.JPG 
        PA从Q2取消息,处理后往Q1发消息;PB从Q1取消息,处理后往Q2发消息,每个缓冲区长度等于传送消息长度。 Q1队列长度为n,Q2队列长度为m. 假设开始时Q1中装满了消息,试用P、V操作解决上述进程间通讯问题。
     
        解:
     
    // Q1队列当中的空闲缓冲区个数,初值为0
    semaphore  S_BuffNum_Q1;  
    // Q2队列当中的空闲缓冲区个数,初值为m 
    semaphore  S_BuffNum_Q2;    
    // Q1队列当中的消息数量,初值为n 
    semaphore  S_MessageNum_Q1;
    // Q2队列当中的消息数量,初值为0 
    semaphore  S_MessageNum_Q2;
     
    void PA( )
    {
        while(1)
        {
            P(S_MessageNum_Q2);
            从Q2当中取出一条消息;
            V(S_BuffNum_Q2);
            处理消息;
            生成新的消息;
            P(S_BuffNum_Q1);
            把该消息发送到Q1当中;
            V(S_MessageNum_Q1);
        
    }
     
    void PB( )
    {
        while(1)
        {
            P(S_MessageNum_Q1);
            从Q1当中取出一条消息;
            V(S_BuffNum_Q1);
            处理消息;
            生成新的消息;
            P(S_BuffNum_Q2);
            把该消息发送到Q2当中;
            V(S_MessageNum_Q2);
        
    }
     
     
        例4:《操作系统》课程的期末考试即将举行,假设把学生和监考老师都看作进程,学生有N人,教师1人。考场门口每次只能进出一个人,进考场的原则是先来先进。当N个学生都进入了考场后,教师才能发卷子。学生交卷后即可离开考场,而教师要等收上来全部卷子并封装卷子后才能离开考场。
        (1)问共需设置几个进程?
        (2)请用P、V操作解决上述问题中的同步和互斥关系。
     
        解:
     
    semaphore  S_Door;         // 能否进出门,初值1
    semaphore  S_StudentReady; // 学生是否到齐,初值为0
    semaphore  S_ExamBegin;   // 开始考试,初值为0
    semaphore  S_ExamOver;    // 考试结束,初值为0
     
    int nStudentNum = 0;       // 学生数目
    semaphore  S_Mutex1;       //互斥信号量,初值为1
    int  nPaperNum = 0;       // 已交的卷子数目
    semaphore  S_Mutex2;       //互斥信号量,初值为1
     
    void  student( )
    {
        P(S_Door);
        进门;
        V(S_Door);
        P(S_Mutex1);
        nStudentNum ++;   // 增加学生的个数
        if(nStudentNum == N)  V(S_StudentReady);
        V(S_Mutex1);
        P(S_ExamBegin);  // 等老师宣布考试开始
        考试中…
        交卷;
        P(S_Mutex2);
        nPaperNum ++;    // 增加试卷的份数
            if(nPaperNum == N) 
            V(S_ExamOver);
            V(S_Mutex2);
            P(S_Door);
            出门;
            V(S_Door);
    }
     
    void  teacher( )
    {
        P(S_Door);
        进门;
        V(S_Door);
        P(S_StudentReady);    //等待最后一个学生来唤醒
        发卷子;
            for(i = 1; i <= N; i++)   
            V(S_ExamBegin);
            P(S_ExamOver);    //等待考试结束
            封装试卷;
            P(S_Door);
            出门;
            V(S_Door);
    }
     
     
     
         5某商店有两种食品A和B,最大数量均为m个。 该商店将A、B两种食品搭配出售,每次各取一个。为避免食品变质,遵循先到食品先出售的原则。有两个食品公司分别不断地供应A、B两种食品(每次一个)。为保证正常销售,当某种食品的数量比另一种的数量超过k(k<m)个时,暂停对数量大的食品进货,补充数量少的食品。
        (1) 问共需设置几个进程?
        (2) 用P、V操作解决上述问题中的同步互斥关系。
     
        解:
     
    semaphore  S_BuffNum_A;  //A的缓冲区个数, 初值m
    semaphore  S_Num_A;      // A的个数,初值为0
    semaphore  S_BuffNum_B;  //B的缓冲区个数, 初值m
    semaphore  S_Num_B;      // B的个数,初值为0
     
    void  Shop( )
    {
        while(1)
        {
            P(S_Num_A);
            P(S_Num_B);
            分别取出A、B食品各一个;
            V(S_BuffNum_A);
            V(S_BuffNum_A);
            搭配地销售这一对食品;
        
    }
     
    // “A食品加1,而B食品不变”这种情形允许出现的次数(许可证的数量),其值等于//k-(A-B),初值为k
    semaphore  S_A_B;
    // “B食品加1,而A食品不变”这种情形允许出现的次数(许可证的数量),其值等于//k-(B-A),初值为k
    semaphore  S_B_A;
     
    void  Producer_A( )
    {
        while(1)
        {
            生产一个A食品;
            P(S_BuffNum_A);
            P(S_A_B);
            向商店提供一个A食品;
            V(S_Num_A);
            V(S_B_A);
        
    }
     
    void  Producer_B( )
    {
        while(1)
        {
            生产一个B食品;
            P(S_BuffNum_B);
            P(S_B_A);
            向商店提供一个B食品;
            V(S_Num_B);
            V(S_A_B);
        
    }
     
     
        6:在一栋学生公寓里,只有一间浴室,而且这间浴室非常小,每一次只能容纳一个人。公寓里既住着男生也住着女生,他们不得不分享这间浴室。因此,楼长制定了以下的浴室使用规则:
         (1)每一次只能有一个人在使用;
         (2)女生的优先级要高于男生,即如果同时有男生和女生在等待使用浴室,则女生优先;
         (3)对于相同性别的人来说,采用先来先使用的原则。
     
        假设:
        (1)当一个男生想要使用浴室时,他会去执行一个函数boy_wants_to_use_bathroom,当他离开浴室时,也会去执行另外一个函数boy_leaves_bathroom;
        (2)当一个女生想要使用浴室时,会去执行函数girl_wants_to_use_bathroom,当她离开时, 也会执行函数girl_leaves_bathroom;
     
        问题:请用信号量和P、V操作来实现这四个函数(初始状态:浴室是空的)。
     
        解:
     
    信号量的定义:
    semaphore  S_mutex;  // 互斥信号量,初值均为1
    semaphore  S_boys;   // 男生等待队列,初值为0
    semaphore  S_girls; // 女生等待队列,初值为0
     
    普通变量的定义:
    int  boys_waiting = 0;  // 正在等待的男生数;
    int  girls_waiting = 0; // 正在等待的女生数;
    int  using = 0;         // 当前是否有人在使用浴室;
     
    void  boy_wants_to_use_bathroom ( )
    {
        P(S_mutex);
        if((using == 0) && (girls_waiting == 0))
            {
                using  =  1;
                V(S_mutex);
            }
        else
            {
                boys_waiting ++;
                V(S_mutex);
                P(S_boys);
            }
    }
     
    void  boy_leaves_bathroom ( )
    {
        P(S_mutex);
        if(girls_waiting  >  0)  // 优先唤醒女生
            {
                girls_waiting --;
                V(S_girls);
            }
        else  if(boys_waiting  >  0)
            {
                boys_waiting --;
                V(S_ boys);
            }
            else   
                using  =  0;     // 无人在等待
                V(S_mutex);
    }
     
    void  girl_wants_to_use_bathroom ( )
    {
        P(S_mutex);
        if(using == 0)
        {
            using  =  1;
            V(S_mutex);
        }
        else
        {
            girls_waiting ++;
            V(S_mutex);
            P(S_girls);
        }
    }
     
    void  girl_leaves_bathroom ( )
    {
        P(S_mutex);
        if(girls_waiting  >  0)  // 优先唤醒女生
        {
            girls_waiting --;
            V(S_girls);
        }
        else  if(boys_waiting  >  0)
            {
                boys_waiting --;
                V(S_ boys);
            }
            else   
                using  =  0;     // 无人在等待
                V(S_mutex);
    }
     
     
     
     
     
     
     
     
    再附上几个例子:
    ********************************************************************************************************
     
    用PV原语实现进程的互斥

      由于用于互斥的信号量sem与所有的并发进程有关,所以称之为公有信号量。公有信号量的值反映了公有资源的数量。只要把临界区置于P(sem)和V(sem)之间,即可实现进程间的互斥。就象火车中的每节车厢只有一个卫生间,该车厢的所有旅客共享这个公有资源:卫生间,所以旅客间必须互斥进入卫生间,只要把卫生间放在P(sem)和V(sem)之间,就可以到达互斥的效果。以下例子说明进程的互斥实现。

    例1: 
        生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里,现要用自动分拣系统把黑子和白子分开,该系统由两个并发执行的进程组成,功能如下:
        (1)进程A专门拣黑子,进程B专门拣白子;
        (2)每个进程每次只拣一个子,当一个进程在拣子时不允许另一个进程去拣子;
     
        分析:
        第一步:确定进程间的关系。由功能(2)可知进程之间是互斥的关系。
        第二步:确定信号量及其值。由于进程A和进程B要互斥进入箱子去拣棋子,箱子是两个进程的公有资源,所以设置一个信号量s,其值取决于公有资源的数目,由于箱子只有一个,s的初值就设为1。
     
        实现:
    begin
        s:semaphore;
        s:=1;
        cobegin
            process A
            begin
                L1: P(s);
                拣黑子;
                V(s);
                goto L1;
            end; 
            process B
            begin
                L2:P(s);
                拣白子;
                V(s);
                goto L2;
            end;
        coend;
    end;
     
      判断进程间是否互斥,关键是看进程间是否共享某一公有资源,一个公有资源与一个信号量相对应。确定信号量的值是一个关键点,它代表了可用资源实体数。如下实例:
     
     
    例2: 
        某车站售票厅,任何时刻最多可容纳20名购票者进入,当售票厅中少于20名购票者时,厅外的购票者可立即进入,否则需要在外面等待。每个购票者可看成一个进程。
     
        分析:第一步:确定进程间的关系。售票厅是各进程共享的公有资源,当售票厅中多于20名购票者时,厅外的购票者需要在外面等待。所以进程间是互斥的关系。第二步:确定信号量及其值。只有一个公有资源:售票厅,所以设置一个信号量s。售票厅最多容纳20个进程,即可用资源实体数为20,s的初值就设为20。
     
        实现:
     
    begin 
        s:semaphore;
        s:=20;
        cobegin
            process PI(I=1,2,……)
            begin P(s);
                进入售票厅;
                购票;
                退出;
                V(s);
            end;
        coend;
    end; 
     
        当购票者进入售票厅前要执行P(s)操作,执行后若s大于或等于零,说明售票厅的人数还未满可进入。执行后若s小于零,则说明售票厅的人数已满不能进入。这个实现中同时最多允许20个进程进入售票厅购票,其余进程只能等待。
     
    用PV原语实现进程的同步

      与进程互斥不同,进程同步时的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关,所以称该信号量为私有信号量。利用PV原语实现进程同步的方法是:首先判断进程间的关系为同步的,且为各并发进程设置私有信号量,然后为私有信号量赋初值,最后利用PV原语和私有信号量规定各进程的执行顺序。下面我们将例1增添一个条件,使其成为进程间是同步的。

    例3: 
        在例1的基础之上再添加一个功能:
      (3)当一个进程拣了一个棋子(黑子或白子)以后,必让另一个进程拣一个棋子(黑子或白子)。
     
        分析:
        第一步:确定进程间的关系。由功能(1)(2)(3)可知,进程间的关系为同步关系。第二步:确定信号量及其值。进程A和B共享箱子这个公有资源,但规定两个进程必须轮流去取不同色的棋子,因而相互间要互通消息。对于进程A可设置一个私有信号量s1,该私有信号量用于判断进程A是否能去拣黑子,初值为1。对于进程B同样设置一个私有信号量s2,该私有信号量用于判断进程B是否能去拣白子,初值为0。当然你也可以设置s1初值为0,s2初值为1。
     
        实现:
     
    begin
        s1,s2:semaphore;
        s1:=1;s2:=0;
        cobegin
            process A
                begin
                L1: P(s1);
                拣黑子;
                V(s2);
                goto L1;
            end;    
            process B
            begin
                L2:P(s2);
                拣白子;
                V(s1);
                goto L2;
            end;
        coend;
    end;
     

      另外一个问题就是P原语是不是一定在V原语的前面?回答是否定的。下面看一个例子:

    例4:
        设在公共汽车上,司机和售票员的活动分别是:司机:启动车辆,正常行车,到站停车。售票员:上乘客,关车门,售票,开车门,下乘客。用PV操作对其控制。
     
        分析:
        第一步:确定进程间的关系。司机到站停车后,售票员方可工作。同样,售票员关车门后,司机才能工作。所以司机与售票员之间是一种同步关系。
        第二步:确定信号量及其值。由于司机与售票员之间要互通消息,司机进程设置一个私有信号量run,用于判断司机能否进行工作,初值为0。售票员进程设置一个私有信号量stop,用于判断是否停车,售票员是否能够开车门,初值为0。
        实现:
    begin
        stop ,run:semaphore
        stop:=0;run:=0;
        cobegin
            driver:
            begin
                L1: P(run);
                启动车辆;
                正常行车;
                到站停车;
                V(stop);
                goto L1;
            end;
            conductor:
            begin
                L2:上乘客;
                关车门;
                V(run);
                售票;
                P(stop);
                开车门;
                下乘客;
                goto L2;
            end;
        coend;
    end;
     
    展开全文
  • PV原语

    2013-05-30 00:02:09
    PV原语的含义 ...PV原语及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量sem是一整数,sem大于等于零时代表可供并发进程使用的资源实体数,但sem小于零时则表示正在等待使用临界区的进程数。

    转自:http://www.cnblogs.com/Jezze/archive/2011/12/23/2299865.html


    PV原语的含义

      P操作和V操作是不可中断的程序段,称为原语。PV原语及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量sem是一整数,sem大于等于零时代表可供并发进程使用的资源实体数,但sem小于零时则表示正在等待使用临界区的进程数。
      P原语操作的动作是:
      (1)sem减1;
      (2)若sem减1后仍大于或等于零,(资源充足)则进程继续执行;
      (3)若sem减1后小于零,则该进程被阻塞后进入与该信号相对应的队列中,然后转进程调度。
      V原语操作的动作是:
      (1)sem加1;
      (2)若相加结果大于零,则进程继续执行(原来没有进程等待资源);
      (3)若相加结果小于或等于零,(原来就有进程等待资源)则从该信号的等待队列中唤醒一等待进程,然后再返回原进程继续执行或转进程调度。
      PV操作对于每一个进程来说,都只能进行一次,而且必须成对使用。在PV原语执行期间不允许有中断的发生。
    用PV原语实现进程的互斥
      由于用于互斥的信号量sem与所有的并发进程有关,所以称之为公有信号量。公有信号量的值反映了公有资源的数量。只要把临界区置于P(sem)和V(sem)之间,即可实现进程间的互斥。就象火车中的每节车厢只有一个卫生间,该车厢的所有旅客共享这个公有资源:卫生间,所以旅客间必须互斥进入卫生间,只要把卫生间放在P(sem)和V(sem)之间,就可以到达互斥的效果。以下例子说明进程的互斥实现。
    例1
      生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里,现要用自动分拣系统把黑子和白子分开,该系统由两个并发执行的进程组成,功能如下:
      (1)进程A专门拣黑子,进程B专门拣白子;
      (2)每个进程每次只拣一个子,当一个进程在拣子时不允许另一个进程去拣子;
    分析:
      第一步:确定进程间的关系。由功能(2)可知进程之间是互斥的关系。
      第二步:确定信号量及其值。由于进程A和进程B要互斥进入箱子去拣棋子,箱子是两个进程的公有资源,所以设置一个信号量s,其值取决于公有资源的数目,由于箱子只有一个,s的初值就设为1。
    实现:
      begin
      s:semaphore;
      s:=1;
       cobegin
        process A
        begin
        L1: P(s);
         拣黑子;
         V(s);
         goto L1;
        end;
        process B
        begin
        L2:P(s);
         拣白子;
         V(s);
         goto L2;
        end;
       coend;
      end;
      判断进程间是否互斥,关键是看进程间是否共享某一公有资源,一个公有资源与一个信号量相对应。确定信号量的值是一个关键点,它代表了可用资源实体数。如下实例:
    例2
      某车站售票厅,任何时刻最多可容纳20名购票者进入,当售票厅中少于20名购票者时,厅外的购票者可立即进入,否则需要在外面等待。每个购票者可看成一个进程。
      分析:第一步:确定进程间的关系。售票厅是各进程共享的公有资源,当售票厅中多于20名购票者时,厅外的购票者需要在外面等待。所以进程间是互斥的关系。第二步:确定信号量及其值。只有一个公有资源:售票厅,所以设置一个信号量s。售票厅最多容纳20个进程,即可用资源实体数为20,s的初值就设为20。
    实现:
      begin
      s:semaphore;
      s:=20;
      cobegin
       process PI(I=1,2,……)
        begin P(s);
         进入售票厅;
         购票;
         退出;
         V(s);
        end;
       coend
    当购票者进入售票厅前要执行P(s)操作,执行后若s大于或等于零,说明售票厅的人数还未满可进入。执行后若s小于零,则说明售票厅的人数已满不能进入。这个实现中同时最多允许20个进程进入售票厅购票,其余进程只能等待。
    用PV原语实现进程的同步
      与进程互斥不同,进程同步时的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关,所以称该信号量为私有信号量。利用PV原语实现进程同步的方法是:首先判断进程间的关系为同步的,且为各并发进程设置私有信号量,然后为私有信号量赋初值,最后利用PV原语和私有信号量规定各进程的执行顺序。下面我们将例1增添一个条件,使其成为进程间是同步的。
    例3
      在例1的基础之上再添加一个功能:
      (3)当一个进程拣了一个棋子(黑子或白子)以后,必让另一个进程拣一个棋子(黑子或白子)。
    分析:
      第一步:确定进程间的关系。由功能(1)(2)(3)可知,进程间的关系为同步关系。第二步:确定信号量及其值。进程A和B共享箱子这个公有资源,但规定两个进程必须轮流去取不同色的棋子,因而相互间要互通消息。对于进程A可设置一个私有信号量s1,该私有信号量用于判断进程A是否能去拣黑子,初值为1。对于进程B同样设置一个私有信号量s2,该私有信号量用于判断进程B是否能去拣白子,初值为0。当然你也可以设置s1初值为0,s2初值为1。
    实现:
      begin
      s1,s2:semaphore;
      s1:=1;s2:=0;
      cobegin
       process A
       begin
       L1: P(s1);
        拣黑子;
        V(s2);
        goto L1;
       end; 
       process B
       begin
       L2:P(s2);
        拣白子;
        V(s1);
        goto L2;
       end;
      coend;
      end;
      另外一个问题就是P原语是不是一定在V原语的前面?回答是否定的。下面看一个例子。
    例4
      设在公共汽车上,司机和售票员的活动分别是:司机:启动车辆,正常行车,到站停车。售票员:上乘客,关车门,售票,开车门,下乘客。用PV操作对其控制。
    分析:
      第一步:确定进程间的关系。司机到站停车后,售票员方可工作。同样,售票员关车门后,司机才能工作。所以司机与售票员之间是一种同步关系。
      第二步:确定信号量及其值。由于司机与售票员之间要互通消息,司机进程设置一个私有信号量run,用于判断司机能否进行工作,初值为0。售票员进程设置一个私有信号量stop,用于判断是否停车,售票员是否能够开车门,初值为0。
      实现:
      begin stop ,run:semaphore
      stop:=0;run:=0;
      cobegin
       driver: begin
       L1: P(run);
        启动车辆;
        正常行车;
        到站停车;
         V(stop);
        goto  L1;
       end;
       conductor:begin
       L2:上乘客;
        关车门;
        V(run);
        售票;
        P(stop);
        开车门;
        下乘客;
        goto L2;
       end;
       coend;
      end;
      用PV操作还可以实现进程同步与互斥的混合问题,典型的如:多个生产者和多个消费者共享容量为n的缓存区。这个例子在很多书中都有介绍,在这里就不说了。
    展开全文
  • PV原语小结通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。信号量是由操作系统来维护的,用户进程只能通过初始化和两个标准原语(P、V原语)来访问,它们在执行时是不可中断的...

    信号量S的物理含义

    S>0:表示有S个资源可用;S=0表示无资源可用;S<0绝对值表示等待队列或链表中的进程个数。信号量的初值应大于等于0。

    PV原语小结

    通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。

    信号量是由操作系统来维护的,用户进程只能通过初始化和两个标准原语(P、V原语)来访问,它们在执行时是不可中断的。初始化可指定一个非负整数,即空闲资源总数。

    P原语:P是荷兰语Proberen(测试)的首字母。为阻塞原语,负责把当前进程由运行状态转换为阻塞状态,直到另外一个进程唤醒它。操作为:申请一个空闲资源(把信号量减1),则若成功,则退出;若失败,则该进程被阻塞;

    V原语:V是荷兰语Verhogen(增加)的首字母。为唤醒原语,负责把一个被阻塞的进程唤醒,它有一个参数表,存放着等待被唤醒的进程信息。操作为:释放一个被占用的资源(把信号量加1),如果发现有被阻塞的进程,则选择一个唤醒之。

    P(S):表示申请一个资源,S减 1;若 减1 后仍S>=0,则该进程继续执行;若 减1 后 S<0,表示已无资源可用,需要将自己阻塞起来。

    V(S):表示释放一个资源,S加 1;若 加1 后S>0,则该进程继续执行;若 加1 后 S<=0,表示等待队列上有等待进程,需要将第一个等待的进程唤醒。

    PV原语对信号量的操作可以分为三种情况:

    .

    1. 把信号量视为一个加锁标志位,实现对一个共享变量的互斥访问。

    实现过程:

    P(mutex); // mutex的初始值为1

    访问该共享数据

    V(mutex);

    非临界区

    互斥信号量是根据临界资源的类型设置的。有几种类型的临界资源就设置几个互斥信号量。它代表该类临界资源的数量,或表示是否可用,其初值一般为“1”。

    .

    2. 把信号量视为是某种类型的共享资源的剩余个数,实现对一类共享资源的访问。

    实现过程:

    P(resource); // resource的初始值为该资源的个数N

    使用该资源;

    V(resource);

    非临界区

    .

    3. 把信号量作为进程间的同步工具

    实现过程:

    临界区C1; P(S);

    V(S); 临界区C2;

    同步信号量是根据进程的数量设置的。一般情况下,有几个进程就设置几个同步信号量,表示该进程是否可以执行,或表示该进程是否执行结束,其初值一般为“0”。

    同步与互斥的解题思路

    分清哪些是互斥问题(互斥访问临界资源的),哪些是同步问题(具有前后执行顺序要求的)。

    对互斥问题要设置互斥信号量,不管有互斥关系的进程有几个或几类,通常只设置一个互斥信号量,且初值为1,代表一次只允许一个进程对临界资源访问。

    对同步问题要设置同步信号量,通常同步信号量的个数与参与同步的进程种类有关,即同步关系涉及几类进程,就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。

    在每个进程中用于实现互斥的PV操作必须成对出现;用于实现同步的PV操作也必须成对出现,但可以分别出现在不同的进程中;在某个进程中如果同时存在互斥与同步的P操作,则其顺序不能颠倒,必须先执行对同步信号量的P操作,再执行对互斥信号量的P操作,但V操作的顺序没有严格要求。

    为什么P操作不能颠倒?

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

    1) 关系分析。找出问题中的进程数,并且分析它们之间的同步和互斥关系。同步、互斥关系直接按照上面的经典范式改写。

    2) 整理思路。找出解决问题的关键点,并且根据做过的题目找出解决的思路。根据进程的操作流程确定P操作、V操作的大致顺序。

    3) 设置信号量。根据上面两步,设置需要的信号量,确定初值,完善整理。

    生产者消费者问题

    问题描述

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

    问题分析

    关系分析:生产者往缓冲区写消息,,消费者从缓冲区取消息必须分开进行,所以两者是互斥关系;同时只有生产者放入消息后,消费者才能从中取出消息,所以两者还是同步关系。

    整理思路:两个进程,既是互斥关系,又是同步关系。此时需要注意互斥同步PV操作的位置。

    信号量设置:互斥信号量mutex,初值为1,保证互斥的访问缓冲池;信号量full记录当前缓冲池中满缓冲区个数,初值为0,信号量empty记录当前缓冲池空缓冲区个数,初值为n。

    类C语言代码

    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; //消费数据

    }

    }

    生产者消费者问题扩展

    问题描述

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

    问题分析

    关系分析:爸妈往盘子里放水果,必须互斥进行,所以爸妈是互斥关系;爸爸和女儿、妈妈和儿子是同步关系,类似生产者和消费者;儿子和女儿没有什么关系,有相应需求的水果就拿走

    整理思路:有四个进程:爸爸放苹果、女儿吃苹果、妈妈放橘子、儿子吃橘子,可抽象为两对生产者消费者对一个缓冲区(盘子)进行操作

    信号量设置:盘子plate为互斥信号量,表示是否允许向盘子中放置水果,初值为1, 表示允许放入。同步信号量设置两个,分别为apple、orange,因为两类进程:爸爸和女儿取放苹果、妈妈和儿子取放橘子。apple表示盘中是否有苹果,初值为0,表示盘子为空,不可取,若apple为1可以取;orange类似。

    类C语言代码

    semaphore plate=1, apple=0, orange=0;

    father() //父亲进程

    {

    while(1)

    {

    P(plate); //互斥向盘中放水果

    向盘中放苹果;

    V(apple); //放好后,此时可以取苹果

    }

    }

    mother() //母亲进程

    {

    while(1)

    {

    P(plate); //互斥向盘中放水果

    向盘中放橘子;

    V(orange); //放好后,此时可以取橘子

    }

    }

    sun() //儿子进程

    {

    while(1)

    {

    P(orange); //互斥从盘中取橘子

    从盘中取橘子;

    V(plate); //取完后盘子可用

    }

    }

    daughter() //女儿进程

    {

    while(1)

    {

    P(apple); //互斥从盘中取苹果

    从盘中取苹果;

    V(plate); //取完后盘子可用

    }

    }

    PV原语第二种类型示例

    问题描述

    某超市门口为顾客准备了100辆手推车,每位顾客在进去买东西时取一辆推车,在买完东西结完帐以后再把推车还回去。试用P、V操作正确实现顾客进程的同步互斥关系。

    问题分析

    把手推车视为某种资源,每个顾客为一个要互斥访问该资源的进程。因此这个例子为PV原语的第二种应用类型。

    类C代码

    semaphore num=100;

    consumer()

    {

    P(num);

    买东西;

    结帐;

    V(num);

    }

    哲学家就餐问题

    问题描述

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

    221de42f5f0db8c48e17dd60670f8d76.png

    问题分析

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

    整理思路:这里有五个进程。本题的关键是如何让一个哲学家拿到左右两个筷子而不造成死锁或者饥饿现象。那么解决方法有两个,一个是让他们同时拿两个筷子;二是对每个哲学家的动作制定规则,避免饥饿或者死锁现象的发生。为了防止死锁的发生,可以对哲学家进程施加一些限制条件,比如至多允许四个哲学家同时进餐;仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子;对哲学家顺序编号,要求奇数号哲学家先抓左边的筷子,然后再转他右边的筷子,而偶数号哲学家刚好相反。正解制定规则如下:假设釆用第二种方法,当一个哲学家左右两边的筷子都可用时,才允许他抓起筷子。

    信号量设置:定义互斥信号量数组Chopstick[5] = {l, 1, 1, 1, 1}用于对5个筷子的互斥访问。取筷子的信号量mutex,初值为1

    类C语言代码

    semaphore chopstick[5] = {

    1,1,1,1,1}; //初始化信号量

    semaphore mutex=1; //设置取筷子的信号量

    Pi(){ //i号哲学家的进程

    while(1)

    {

    P (mutex) ; //在取筷子前获得互斥量

    P (chopstick [i]) ; //取左边筷子

    P (chopstick[ (i+1) %5]) ; //取右边筷子

    V (mutex) ; //释放取筷子的信号量

    eat; //进餐

    V(chopstick[i] ) ; //放回左边筷子

    V(chopstick[ (i+l)%5]) ; //放回右边筷子

    think; // 思考

    }

    }

    会发生死锁的算法

    semaphore chopstick[5] = {

    1,1,1,1,1}; //初始化信号量

    Pi(){ //i号哲学家的进程

    while(1)

    {

    P (chopstick [i]) ; //取左边筷子

    P (chopstick[ (i+1) %5]) ; //取右边筷子

    eat; //进餐

    V(chopstick[i] ) ; //放回左边筷子

    V(chopstick[ (i+l)%5]) ; //放回右边筷子

    think; // 思考

    }

    }

    /*当每个哲学家同时拿起同一侧的筷子时,会发生死锁*/

    展开全文
  • PV原语解决司机与售票员问题 4用PV原语解决民航售票问题 5.用PV原语解决汽车租赁问题 1.死锁 死锁是指多个进程之间相互等待对方的资源,而在得到对方资源之前又不释放自己的资源,这样,造成循环等待的一种现象。...

    1.死锁

    • 死锁是指多个进程之间相互等待对方的资源,而在得到对方资源之前又不释放自己的资源,这样,造成循环等待的一种现象。如果所有进程都在等待一个不可能发生的事,则进程就死锁了。

    • 进程与进程间的关系
      (1)互斥:类似人之间的矛盾关系 2个小孩争抢同一个玩具
      多个进程排他性的使用他们所共享的资源,这些进程间就构成互斥关系
      (2)同步:类似人之间的协作关系 公共汽车安全行驶问题 司机 售票员

    • 死锁产生的必要条件
      (1)互斥条件
      进程对资源进行排他性使用,即在一段时间内某资源仅为一个进程所占用
      (2)请求和保持条件
      当进程因请求资源而阻塞时,对已获得的资源保持不放
      (3)不可剥夺条件
      进程已获得的资源在未使用完之前,不能被剥夺,只能在使用完时由自己释放
      (4)环路等待条件
      各个进程组成封闭的环形链,每个进程都等待下一个进程所占用的资源
      说明:
      如果一个进程同一时刻,允许多个进程占用的话,就不会构成死锁
      因为进程要排他性地使用资源,所以防止死锁产生,重点是防止上面的(2)(3)(4)条件

    • 防止死锁办法
      (1)资源一次性分配:破坏请求和保持条件
      (2)可剥夺资源:破坏不可剥夺条件
      所需要的资源都得到满足的时候,才能够占有,而不能占有一半的资源;
      (3)资源有序分配法:破坏循环等待条件
      当一个进程请求资源时,可以破坏其它进程所占有的资源

    • 死锁避免
      (1)预防死锁的几种策略,会严重地损害系统性能。因此,在避免死锁时,要施加较弱的限制,从而获得较满意的系统性能
      (2)由于在避免死锁的策略中,允许进程动态地申请资源。
      因而,系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程,否则,进程等待。其中最具有代表性的避免死锁算法是银行家算法。

    • 银行家算法
      为保证资金的安全,银行家规定:
      (1)当一个顾客对资金的最大需求量不超过银行家现有的资金时,就可以接纳该顾客
      (2)顾客可以分期贷款,但贷款的总数不能超过最大需求量
      (3)当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟值赋,但总能使顾客在有限的时间里得到贷款
      (4)当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金
      进程资源的分配可以模拟银行家算法
      (1)一个进程申请的资源不超过系统的资源时,就可以允许该进程申请资源,否则就延迟申请
      (2)进程申请的资源系统不能满足,进程可以分配申请,但是申请的资源不能超过系统的容量
      (3)进程申请资源时,若系统暂时不能满足进程,系统会让进程等待,系统让进程在有限的时间里得到资源
      (4)进程得到所有的资源,能够在有限的时间内归还所有的资源

    • 哲学家就餐问题
      (1)5个哲学家围在一个圆桌上就餐,每个人都必须拿起2把叉子才能用餐
      (2)哲学家就餐问题解法
      解法1:服务生解法;这个方法将服务生作为一个管理者,它会判断资源是否处于安全的状态,若是安全状态,则会允许哲学家拿起叉子,否则不允许,继续等待.这是死锁避免算法,类似用银行家算法来解决问题
      解法2:最多4个哲学家;这个方法不好,实际改变了条件;
      解法3:仅当一个哲学家两边筷子都可以用时,才允许他拿筷子;这是破坏请求和保持条件
      解法4:给所有哲学家编号,奇数号的哲学家必须首先拿左边的筷子,偶数号的哲学家则反之;这是破坏环路和等待条件
      在这里插入图片描述

    2.信号量与PV原语

    • 信号量和PV原语解决进程同步和互斥问题
    • 信号量和P、V原语是由Dijkstra迪杰斯特拉提出的
    • 信号量
      互斥:P、V在同一个进程中
      同步:P、V在不同进程中
    • 信号量值含义,S:计数值,等于-1表示:有1个进程处于等待的状态
      S>0:S表示可用资源的个数
      S=0:表示无可用资源,无等待进程
      S<0,|S|表示等待队列中进程的个数
    • 信号量
    struct semaphore
    {
    	int value;
    	pointer_PCB queue;进程控制块指针:表示当前有哪些进程处于等待的状态
    };
    
    • P原语
      进程申请资源
      下面的代码是原子性的操作,不能被打断,在硬件上,而可以通过关闭中断的方式来实现
    P(s)
    {
    	s.value=s.value--;
    	if (s.value < 0)
    	{
    		该进程状态置为等待状态
    		将该进程的PCB插入相应的等待队列s.queue末尾
    	}
    }
    
    • V原语
      进程归还资源
    V(s)
    {
    	s.value=s.value++;
    	if (s.value <=0)
    	{
    		唤醒相应等待队列s.queue中等待的一个进程
    		改变其状态为就绪态
    		并将其插入就绪队列
    	}
    }
    
    

    3.用PV原语解决司机与售票员问题

    • 若信号量PV操作分布在不同进程中是解决同步问题的
      P(S1)将司机进程处于等待状态,当售票员进程关上门之后会给司机一个信号,即执行V(S1)操作,使得S1信号量的值增加了,唤醒了司机进程,司机进程就能进入启动车辆的状态;
      由于司机到站停车后才能开门,且S2信号量的值为0,因而它也进入到了等待状态,直到司机进程到站停车后执行V(S2)操作,唤醒等待的售票员进程,所以,售票员进程能开门
      在这里插入图片描述

    4用PV原语解决民航售票问题

    • 互斥问题
      (1)S(1) 信号量的初始计数值为1,对S进行P操作进入临界区,此时S-1等于0,若有其他进程进入临界区,则会处于等待的状态,因为当前信号量的计数值为0,直到该进程执行V操作,释放对临界资源的控制权,才能够唤醒另外一个进程
      (2)
    if (x>0)
    x–;
    上面是临界区,x称之为临界资源
    /***********************/
    
    票数=x
    S(1)
    
    P(S)
    if (x>0)
    	x--;
    V(S)
    

    5.用PV原语解决汽车租赁问题

    • 信号量计数值表示当前资源的个数
    • 有一汽车租赁公司有两部敞篷车可以出租,假定同时来了四个顾客都要租赁敞篷车,那么肯定会有两个人租不到
      在这里插入图片描述
      因为有2辆敞篷车,所以信号量计数值为2,注意这里的资源必须是同类的资源
      当一个顾客比较快办理完手续,首先进行一次P操作,计数值为1,接着。。。以此类推
      有一天B归还车了,他要唤醒其中的一个进程,会将当前的计数值-2改为-1,表示当前还有一个人处于等待的状态。。。以此类推
    展开全文
  • 一、PV原语的含义P操作和V操作是不可终端的程序段,成为原语,PV原语及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量sem是一个整数。Sem大于等于零时代表可供并发进程使用的资源实体数,但sem小于零时则...
  • 一:桌上有1空盘,允许存放1个水果。...请用Wait()、Signal()原语实现爸爸、儿子、女儿三个并发进程的同步。Semaphore mutex=1,mutex1=0,mutex2=0;main(){cobeignfather();son();daugther();coend...
  • PV原语详解

    千次阅读 2018-10-29 21:41:35
    PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出,其基本思路是用一种新的变量类型(semaphore)来记录当前...
  • pv原语文章收集

    2011-11-02 11:43:44
    pv原语试题集锦 各种典型例题 有利于理解,典型易懂
  • PV原语操作详解

    千次阅读 2018-07-30 10:14:54
    PV原语操作详解       PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。 信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出,其基本思路是用一种新的...
  • PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。 信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出,其基本思路是用一种新的变量类型(semaphore)来记录当前...
  • 计算机操作系统PV原语分析,介绍PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序……
  • 在处理进程间的同步与互斥问题时,我们离不开信号量和PV原语,使用这两个工具的目的在于打造一段不可分割不可中断的程序。应当注意的是,信号量和PV原语是解决进程间同步与互斥问题的一种机制,但并不是唯一的机制。...
  • pv原语的定义及解释理解

    千次阅读 2016-06-05 17:40:00
    PV原语的含义    P操作和V操作是不可中断的程序段,称为原语.PV原语及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的.信号量sem是一整数,sem大于等于零时代表可供并发进程使用的资源实体数,但sem小于零时则表示...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 605
精华内容 242
关键字:

pv原语