精华内容
下载资源
问答
  • 如何用PV原语实现进程间的互斥与同步 P操作和V操作是不可中断的程序段,称为原语。PV原语及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量sem是一整数,sem大于等于零时代表可供并发进程使用的资源实体...
  • 信号量sem是一整数,sem大于等于零时代表可供并发进程使用资源实体数,但sem小于零时则表示正在等待使用临界区的进程数。 P原语操作动作是: (1)sem减1; (2)若sem减1后仍大于或等于零,则进程继续执行;...
       
    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的缓存区。 
     
     

    转载于:https://www.cnblogs.com/tyouketu/archive/2007/03/09/669331.html

    展开全文
  • //打开信号量,flag参数打开普通文件标记一样   sem_t *sem_open(const char *name, int oflag,mode_t mode, unsigned int value);   //创建并打开信号量,value参数指是信号量初始值  int sem_...

    转:http://www.oschina.net/code/snippet_237505_8646#13755

         howaylee 发布于 2012年02月12日 20时


    /* 
       命名信号量不带内存共享,编译时要带库文件-lpthread或-lrt 
       int sem_wait(sem_t *sem); //P操作,若是信号量大于零则减一,否则阻塞在该函数位置等待. 
       int sem_post(sem_t *sem); //V操作,信号量加一 
       sem_t *sem_open(const char *name, int oflag);//打开信号量,flag参数与打开普通文件的标记一样 
       sem_t *sem_open(const char *name, int oflag,mode_t mode, unsigned int value); 
     //创建并打开信号量,value参数指的是信号量的初始值 
    int sem_unlink(const char *name);//删除系统创建的信号量 
    int sem_close(sem_t *sem);//关闭彻底销毁信号量 
     */ 


    sem_dan_syn.c

    #include <stdio.h>
    #include <errno.h>
    #include <semaphore.h>
    #include <fcntl.h>
     
    /*
       命名信号量不带内存共享,编译时要带库文件-lpthread或-lrt
       int sem_wait(sem_t *sem); //P操作,若是信号量大于零则减一,否则阻塞在该函数位置等待.
       int sem_post(sem_t *sem); //V操作,信号量加一
       sem_t *sem_open(const char *name, int oflag);//打开信号量,flag参数与打开普通文件的标记一样
       sem_t *sem_open(const char *name, int oflag,mode_t mode, unsigned int value);
    //创建并打开信号量,value参数指的是信号量的初始值
    int sem_unlink(const char *name);//删除系统创建的信号量
    int sem_close(sem_t *sem);//关闭彻底销毁信号量
     */
     
    /*进程排斥*/
     
    #define SEM_NAME "mysem"
    #define OPEN_FLAG O_RDWR|O_CREAT
    #define OPEN_MODE 00777
    #define INIT_V    0
    static sem_t *sem = NULL;
     
    static void mysem(char *str)
    {
        int i = 0;
        while('\0' != str[i])
        {
            printf("%c\n", str[i++]);
            sleep(1);
        }
    }
     
     
    /*单次同步, 把信号量先初始化为0*/
     
    int main(void)
    {
     
        pid_t pid = -1;
        int ret = -1;
        int status = -1;
     
        //创建一个命名信号量
        sem = sem_open(SEM_NAME, OPEN_FLAG, OPEN_MODE, INIT_V);
     
        //创建子进程
        pid = fork();
        if(-1 == (ret = pid))
        {
            perror("fork failed: ");
            goto _OUT;
        }
     
        if(0 == pid)
        {
            mysem("abcd");
            //V操作
            sem_post(sem);
        }
     
        if(0 < pid)
        {
            //P操作
            sem_wait(sem);
            mysem("1234");
            //等待子进程结束
            wait(&status);
            //删掉在系统创建的信号量
            sem_unlink(SEM_NAME);
            //彻底销毁打开的信号量
            sem_close(sem);
        }
     
    _OUT:
        return ret;
    }





     sem_diedai_syn.c

    #include <stdio.h>
    #include <errno.h>
    #include <semaphore.h>
    #include <fcntl.h>
    #include <signal.h>
     
    /*
       命名信号量不带内存共享,编译时要带库文件-lpthread或-lrt
       int sem_wait(sem_t *sem); //P操作,若是信号量大于零则减一,否则阻塞在该函数位置等待.
       int sem_post(sem_t *sem); //V操作,信号量加一
       sem_t *sem_open(const char *name, int oflag);//打开信号量,flag参数与打开普通文件的标记一样
       sem_t *sem_open(const char *name, int oflag,mode_t mode, unsigned int value);
    //创建并打开信号量,value参数指的是信号量的初始值
    int sem_unlink(const char *name);//删除系统创建的信号量
    int sem_close(sem_t *sem);//关闭彻底销毁信号量
     */
     
    #define SEM_NAME1 "mysem1"
    #define SEM_NAME2 "mysem2"
    #define OPEN_FLAG O_RDWR|O_CREAT
    #define OPEN_MODE 00777
     
    static sem_t *sem1 = NULL;
    static sem_t *sem2 = NULL;
     
    //临界区
    static void mysem(char *str)
    {
        int i = 0;
        while('\0' != str[i])
        {
            printf("%c\n", str[i++]);
            sleep(1);
        }
    }
    //信号捕捉处理
    static void myhandler(void)
    {
            //删掉在系统创建的信号量
            sem_unlink(SEM_NAME1);
            sem_unlink(SEM_NAME2);
            //彻底销毁打开的信号量
            sem_close(sem1);   
            sem_close(sem2);   
    }
     
     
    /*迭代同步,两个信号量,开始时一个为1,一个为0, 一个进程执行完换另一个进程运行*/
     
    int main(void)
    {
     
        pid_t pid = -1;
        int ret = -1;
        int status = -1;
     
        //安装捕捉信号
        signal(SIGINT,(void *)myhandler );
     
        //创建一个命名信号量
        sem1 = sem_open(SEM_NAME1, OPEN_FLAG, OPEN_MODE, 1);   
        sem2 = sem_open(SEM_NAME2, OPEN_FLAG, OPEN_MODE, 0);   
     
        //创建子进程
        pid = fork();
        if(-1 == (ret = pid))
        {
            perror("fork failed: ");
            goto _OUT;
        }
     
        if(0 == pid)
        {
            while(1)
            {
            //P操作
            sem_wait(sem1);
            mysem("abcd");
            //V操作
            sem_post(sem2);
            }
        }
     
        if(0 < pid)
        {
            while(1)
            {
            //P操作
            sem_wait(sem2);
            mysem("1234");
            //V操作
            sem_post(sem1);
            }
            //等待子进程结束
            wait(&status);
        }
     
    _OUT:
        return ret;
    }



    sem_paichi.c

    #include <stdio.h>
    #include <errno.h>
    #include <semaphore.h>
    #include <fcntl.h>
     
    /*
       命名信号量不带内存共享,编译时要带库文件-lpthread或-lrt
       int sem_wait(sem_t *sem); //P操作,若是信号量大于零则减一,否则阻塞在该函数位置等待.
       int sem_post(sem_t *sem); //V操作,信号量加一
       sem_t *sem_open(const char *name, int oflag);//打开信号量,flag参数与打开普通文件的标记一样
       sem_t *sem_open(const char *name, int oflag,mode_t mode, unsigned int value);
        //创建并打开信号量,value参数指的是信号量的初始值
    int sem_unlink(const char *name);//删除系统创建的信号量
    int sem_close(sem_t *sem);//关闭彻底销毁信号量
     */
     
     
    #define SEM_NAME "mysem"
    #define OPEN_FLAG O_RDWR|O_CREAT
    #define OPEN_MODE 00777
    #define INIT_V    1
    static sem_t *sem = NULL;
     
    static void mysem(char *str)
    {
        int i = 0;
        //P操作
        sem_wait(sem);
        while('\0' != str[i])
        {
            printf("%c\n", str[i++]);
            sleep(1);
        }
        //V操作
        sem_post(sem);
    }
     
     
    /*进程排斥,在临界区设置PV操作*/
     
    int main(void)
    {
     
        pid_t pid = -1;
        int ret = -1;
        int status = -1;
     
        //创建一个命名信号量
        sem = sem_open(SEM_NAME, OPEN_FLAG, OPEN_MODE, INIT_V);
     
        //创建子进程
        pid = fork();
        if(-1 == (ret = pid))
        {
            perror("fork failed: ");
            goto _OUT;
        }
         
        if(0 == pid)
        {
            mysem("abcd");
        }
         
        if(0 < pid)
        {
            mysem("1234");
            //等待子进程结束
            wait(&status);
            //删掉在系统创建的信号量
            sem_unlink(SEM_NAME);
            //彻底销毁打开的信号量
            sem_close(sem);
        }
     
    _OUT:
        return ret;
    }




    展开全文
  • 信号量sem是一整数,sem大于等于零时代表可供并发进程使用资源实体数,但sem小于零时则表示正在等待使用临界区的进程数。  P原语操作动作是:  (1)sem减1;  (2)若sem减1后仍大于或等于零,则进程继续...

    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原语

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

    信号量的概念1965年由著名的荷兰计算机科学家Dijkstra提出,其基本思路是用一种新的变量类型(semaphore)来记录当前可用资源的数量。有两种实现方式:1)semaphore的取值必须大于或等于0。0表示当前已没有空闲资源,而正数表示当前空闲资源的数量;2) semaphore的取值可正可负,负数的绝对值表示正在等待进入临界区的进程个数。

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

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

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

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

    1)把信号量视为一个加锁标志位,实现对一个共享变量的互斥访问。
    实现过程:
    P(mutex); // mutex的初始值为1 访问该共享数据;
    V(mutex);
    非临界区

    2)把信号量视为是某种类型的共享资源的剩余个数,实现对一类共享资源的访问。
    实现过程:
    P(resource); // resource的初始值为该资源的个数N 使用该资源;
    V(resource); 非临界区

    3)把信号量作为进程间的同步工具
    实现过程:
    临界区C1;
    P(S);
    V(S);
    临界区C2;


    PV原语操作

    信号量
    信号量是最早出现的用来解决进程同步与互斥问题的机制,包括一个称为信号量的变量及对它进行的两个原语操作。
    本节将从以下几个方面进行介绍--
    --------------------------------------------------------------------------------

    一. 信号量的概念
    1. 信号量的类型定义
    2. PV原语

    --------------------------------------------------------------------------------

    二. 实例
    1. 生产者-消费者问题(有buffer)
    2. 第一类读-写者问题
    3. 哲学家问题

    --------------------------------------------------------------------------------

    一. 信号量的概念
    1. 信号量的类型定义
    每个信号量至少须记录两个信息:信号量的值和等待该信号量的进程队列。它的类型定义如下:(用类PASCAL语言表述) semaphore = record value: integer; queue: ^PCB; end; 其中PCB是进程控制块,是操作系统为每个进程建立的数据结构。 s.value>=0时,s.queue为空; s.value<0时,s.value的绝对值为s.queue中等待进程的个数;
    返回

    --------------------------------------------------------------------------------

    2. PV原语
    对一个信号量变量可以进行两种原语操作:p操作和v操作,定义如下: procedure p(var s:samephore); { s.value=s.value-1; if (s.value<0) asleep(s.queue); } procedure v(var s:samephore); { s.value=s.value+1; if (s.value<=0) wakeup(s.queue); } 其中用到两个标准过程: asleep(s.queue);执行此操作的进程的PCB进入s.queue尾部,进程变成等待状态 wakeup(s.queue);将s.queue头进程唤醒插入就绪队列 s.value初值为1时,可以用来实现进程的互斥。 p操作和v操作是不可中断的程序段,称为原语。如果将信号量看作共享变量,则pv操作为其临界区,多个进程不能同时执行,一般用硬件方法保证。一个信号量只能置一次初值,以后只能对之进行p操作或v操作。由此也可以看到,信号量机制必须有公共内存,不能用于分布式操作系统,这是它最大的弱点。
    返回

    --------------------------------------------------------------------------------

    二. 实例
    1. 生产者-消费者问题(有buffer)
    问题描述: 一个仓库可以存放K件物品。生产者每生产一件产品,将产品放入仓库,仓库满了就停止生产。消费者每次从仓库中去一件物品,然后进行消费,仓库空时就停止消费。解答: 进程:Producer - 生产者进程,Consumer - 消费者进程 共有的数据结构: buffer: array [0..k-1] of integer; in,out: 0..k-1; — in记录第一个空缓冲区,out记录第一个不空的缓冲区 s1,s2,mutex: semaphore; — s1控制缓冲区不满,s2控制缓冲区不空,mutex保护临界区; 初始化s1=k,s2=0,mutex=1 producer(生产者进程): Item_Type item; { while (true) { produce(&item); p(s1); p(mutex); buffer[in]:=item; in:=(in+1) mod k; v(mutex); v(s2); } } consumer(消费者进程): Item_Type item; { while (true) { p(s2); p(mutex); item:=buffer[out]; out:=(out+1) mod k; v(mutex); v(s1); consume(&item); } } 例程演示
    返回

    --------------------------------------------------------------------------------

    2. 第一类读-写者问题
    问题描述: 一些读者和一些写者对同一个黑板进行读写。多个读者可同时读黑板,但一个时刻只能有一个写者,读者写者不能同时使用黑板。对使用黑板优先级的不同规定使读者-写者问题又可分为几类。第一类问题规定读者优先级较高,仅当无读者时允许写者使用黑板。解答: 进程:writer - 写者进程,reader - 读者进程 共有的数据结构: read_account:integer; r_w,mutex: semaphore; — r_w控制谁使用黑板,mutex保护临界区,初值都为1 reader - (读者进程): { while (true) { p(mutex); read_account++; if(read_account=1) p(r_w); v(mutex); read(); p(mutex); read_account--; if(read_account=0) v(r_w);; v(mutex); } } writer - (写者进程): { while (true) { p(mutex); write(); v(mutex); } } 例程演示
    返回

    --------------------------------------------------------------------------------

    3. 哲学家问题
    问题描述: 一个房间内有5个哲学家,他们的生活就是思考和进食。房间里有一张圆桌,中间放着一盘通心粉(假定通心粉无限多)。桌子周围放有五把椅子,分别属于五位哲学家每两位哲学家之间有一把叉子,哲学家进食时必须同时使用左右两把叉子。解答: 进程:philosopher - 哲学家 共有的数据结构&过程: state: array [0..4] of (think,hungry,eat); ph: array [0..4] of semaphore; — 每个哲学家有一个信号量,初值为0 mutex: semaphore; — mutex保护临界区,初值=1 procedure test(i:0..4); { if ((state[i]=hungry) and (state[(i+1)mod 5]<>eating) and (state[(i-1)mod 5]<>eating)) { state[i]=eating; V(ph[i]); } } philosopher(i:0..4): { while (true) { think(); p(mutex); state[i]=hungry; test(i); v(mutex); p(ph[i]); eat(); p(mutex); state[i]=think; test((i-1) mod 5); test((i+1) mod 5); v(mutex); } }


    PV原语-2004上半年上午试题

      若有一个仓库,可以存放P1、P2两种产品,但是每次只能存放一种产品.要求:
       ① w=P1的数量-P2的数量
       ② -i&lt;w&lt;k (i、k为正整数)
      若用PV操作实现P1和P2产品的入库过程,至少需要__(23)__个同步信号量及__(24)__个互斥信号量,其中,同步信号量的初值分别为__(25)__,互斥信号量的初值分别为__(26)__。
      (23)A.0  B.1   C.2    D.3
      (24)A.0  B.1   C.2    D.3
      (25)A.0  B.i,k,0  C.i,k    D.i-1,k-1
      (26)A.1  B.1,1  C.1,1,1  D.i,k

    答案是C B D A


    系分考试知识:PV操作释疑

    信号量

        信号量是最早出现的用来解决进程同步与互斥问题的机制,

        包括一个称为信号量的变量及对它进行的两个原语操作。

        一. 信号量的概念

        1.信号量的类型定义

        每个信号量至少须记录两个信息:信号量的值和等待该信号量的进程队列。它的类型定义如下:(用类PASCAL语言表述)

            semaphore = record

                 value: integer;

                 queue: ^PCB;

               end;

          其中PCB是进程控制块,是操作系统为每个进程建立的数据结构。

        s.value>=0时,s.queue为空;

        s.value<0时,s.value的绝对值为s.queue中等待进程的个数;

        2.PV原语

        对一个信号量变量可以进行两种原语操作:p操作和v操作,定义如下:   procedure p(var s:samephore);

             {

               s.value=s.value-1;

               if (s.value<0) asleep(s.queue);

             }

          procedure v(var s:samephore);

             {

               s.value=s.value+1;

               if (s.value<=0) wakeup(s.queue);

        }

    其中用到两个标准过程:

          asleep(s.queue);执行此操作的进程的PCB进入s.queue尾部,进程变成等待状态

    wakeup(s.queue);将s.queue头进程唤醒插入就绪队列

        s.value初值为1时,可以用来实现进程的互斥。

        p操作和v操作是不可中断的程序段,称为原语。如果将信号量看作共享变量,则pv操作为其临界区,多个进程不能同时执行,一般用硬件方法保证。一个信号量只能置一次初值,以后只能对之进行p操作或v操作。

        由此也可以看到,信号量机制必须有公共内存,不能用于分布式操作系统,这是它最大的弱点。

        V原语的主要操作是:

        (1)sem加1;

        (2)若相加结果大于零,则进程继续执行;

        (3)若相加结果小于或等于零,则唤醒一阻塞在该信号量上的进程,然后再返回原进程继续执行或转进程调度。

        典型理解偏差:

        一,以V原语的1、2步来做,Sem不就永远大于0,那进程不就一直循环执行成为死循环了?

        二,Sem大于0那就表示有临界资源可供使用,为什么不唤醒进程?

        三,Sem小于0应该是说没有临界资源可供使用,为什么还要唤醒进程?

        析疑: 一,P操作对sem减1的。P、V原语必须成对使用!从而不会造成死循环。 二,Sem大于0的确表示有临界资源可供使用,而且这个时候没有进程被阻塞在这个资源上,也就是说没有进程因为得不到这类资源而阻塞,所以没有被阻塞的进程,自然不需要唤醒。 三,V原语操作的本质在于:一个进程使用完临界资源后,释放临界资源,使Sem加1,以通知其它的进程,这个时候如果Sem<0,表明有进程阻塞在该类资源上,因此要从阻塞队列里唤醒一个进程来“转手”该类资源。 比如,有2个某类资源,三个进程A、B、C、D要用该类资源,最开始Sem=2,当A进入,Sem=1,当B进入Sem=0,表明该类资源刚好用完, 当C进入时Sem=-1,表明有一个进程被阻塞了,D进入,Sem=-2。当A用完该类资源时,进行V操作,Sem=-1,释放该类资源,而这时Sem<0,表明有进程阻塞在该类资源上,于是唤醒一个。

        为了进一步加深理解,再引入二个问题: 四,如果是互斥信号量的话,应该设置信号量Sen=1,但是当有5个进程都访问的话,最后在该信号量的链表里会有4个在等待,也是说S=-4,那么第一个进程执行了V操作使S加1,释放了资源,下一个应该能够执行,但唤醒的这个进程在执行P操作时因S〈0 ,也还是执行不了,这是怎么回事呢? 五,Sem的绝对值表示等待的进程数,同时又表示临界资源,这到底是怎么回事? 析疑: 四,当一个进程阻塞了的时候,它已经执行过了P操作,并卡在临界区那个地方。当唤醒它时就立即进入它自己的临界区,并不需要执行P操作了,当执行完了临界区的程序后,就执行V操作。 五,当信号量Sem小于0时,其绝对值表示系统中因请求该类资源而被阻塞的进程数目.S大于0时表示可用的临界资源数。注意在不同情况下所表达的含义不一样。当等于0时,表示刚好用完。


    吸烟者问题(Patil, 1971)
      三个吸烟者在一间房间内,还有一个香烟供应者。为了制造并抽掉香烟,每个吸烟者需要三样东西:烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中,第一个有自己的烟草,第二个有自己的纸,第三个有自己的火柴。供应者将两样东西放在桌子上,允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者,供应者再放两样东西(随机地)在桌面上,然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。

    分析思想:
    1) 供应者seller随即产生两样东西,提供它们,这里用普通变量来表示 
    2) 吸烟者进程smoker根据其排号不同,拥有不同的一件东西。假设1号吸烟者拥有烟草tobacco,2号吸烟者拥有纸paper,3号吸烟者拥有火柴match。其他号码错误返回。
    3) 吸烟者的序号代表他们拥有的东西,用他们的序号和供应者产生的两样东西比较,如果都不相等,则说明他拥有的东西和供应者产生的东西匹配,它可以吸烟。如果其中一个相等,则推出,继续排队。
    4) mutex信息量代表一个只能进入的门,每次只有一个吸烟者可以进入进行比较和吸烟。
    5) 每个吸烟者在吸烟完毕之后出门之前要叫醒供应者,调用seller进程。

    信息量:
    mutex:=1 ——互斥信息量,表示吸烟者进入的门

    解法:
    #typedef int semaphore
    semaphore mutex=1;
    int thing1,thing2;

    void seller(){
    Randomize;
    int i = random(2);  //产生0-2的随机数
    thing1 = ((i-1)%3)+1; //将thing赋值为0-2种不等于i的两个数+1
    thing2 = ((i+1)%3)+1; 
    }
    void smoker(int i){
    if((i<=0)||(i>3))  //i值应为1-3
      return false;
    while(true){
      P(mutex)
      if((i!=thing1)&&(i!=thing2)){ //所拥有的物品与供应者放出的物品不一样
       吸烟;
       seller();   //唤醒供应者
       V(mutex);
      }
      else{
       V(mutex)
      }//end if
    }//end while
    }


    用pv原语完成下列题目:

    (1)在南开大学和天津大学之间有一条弯曲的小路,其中从S到T一段路每次只允许一辆自行车通过,但中间有一个小的“安全岛”M(同时允许两辆自行车停留),可供两辆自行车已从两端进入小路情况下错车使用,如图所示。试设计一个算法来使来往的自行车均可顺利通过。
    (2)5.某高校计算机系开设网络课并安排上机实习,假设机房共有2m台机器,有2n名学生选课(m,n均大于等于1),规定:
    1,每两个学生组成一组,各占一台及其协同完成上机实习;
    2,只有一组两个学生到齐,并且此时机房有空闲机器时,该组学生才能进入机房;
    3,上机实习由一名教师检查,检查完毕,一组学生同时离开机房
    试用P、V操纵模拟上机实习过程。
    (3)某寺庙,有小和尚和老和尚若干,有一个水缸,由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水,水取自同一口井中,由于水井口窄,每次只能容纳一个水桶取水。水桶总数为3个(老和尚和小和尚共同使用)。每次入水、取水仅为一桶,且不可同时进行。试给出有关取水、入水的算法描述。
    (4)设公共汽车上,司机和售票员的活动分别是:
         司机:               售票员:
             启动车辆               上下乘客
             正常行车               关车门
             到站停车               售票
                                         开车门
                                         上下乘客                         
       在汽车不断到站,停车,行驶过程中,这两个活动的同步关系

    1) 设信号量 sk=1(表示有无车通过1表示有车)
                ts=1(.........)
                st=1(.......)
                lt=1(......)
                m=2(.......)
    执行p操作
    从s到t                        从t到s
    p(st)                        p(ts)
    p(sk)                        p(lt)
    从s到k                       从l到t
    p(m)                         p(m)
    进入m                        进入m
    v(sk)                        v(lt)
    p(lt)                        p(sk)
    从l到t                       从k到s
    v(st)                        v(ts)
    v(lt)                        v(sk)

    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;

    展开全文
  • 信号量sem是一整数,sem大于等于零时代表可供并发进程使用资源实体数,但sem小于零时则表示正在等待使用临界区的进程数。 P原语操作动作是: (1) sem减1; (2) 若sem减1后仍大于或等于零,则进程继续执行; ...

     




    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的缓存区。这个例子在很多书中都有介绍,在这里就不说了。





    看完后对互斥及同步有了深一步的了解了.
    互斥: 同一个共享资源,不能让两个进程同时,,,,,,
    同步: 两个进程间的通信信号:例如进程1处理完后用一个V(S2)操作,告诉进程2:喂,可能 了.然后进程检查自己的信号量:P(S2),发现,真的可以了耶,则开始做自己的事情,做完离开共享区后又告诉进程1,用一个V(S1)操作告诉进程1,我做完了,轮到你了.然后进程1开始检查P(s1),对噢,然后就开始执行.
    -->S1和S2是进程1和进程2的各自私有信号量. 对方通过修改自己的私有信号量来实现通信,交流,同步协作.
    展开全文
  • 最近准备考软件设计师,觉得以前学习内容都忘了不少~,现在又要重新学习,真好累呀~今晚遇到了有关pv原语题目,我记得以前我学这些都还可以,但现在真是。。。在网上找了很久,总于找到一篇较容易理解...
  • 进程间互斥与同步

    千次阅读 2017-05-15 22:18:21
    进程间互斥与同步实验题目:进程间的互斥与同步 实验内容:编写算法,实现进程间对临界资源的互斥访问以及进程间的同步关系 实验要求: 1、要求进程互斥使用文本文件; 2、假定文本文件txt1最大可写入30个字符; ...
  • 当前,利用软件方法、硬件方法、信号量方法、管程方法、消息传递方法都可以有效地解决进程间的互斥与同步,其中信号量的方法更具有优势(目前已经通用)。 1. 软件方法: 软件方法是指由进程自己,通过执行相应的...
  • 线程间的互斥与同步

    2019-02-25 15:18:48
    生产者消费者问题(用于理解线程间互斥与同步的典型事例) 线程互斥:对于临界资源区,同一时刻只能由一个线程访问。相当于仓库,生产好产品入库时,就不能从仓库中取东西;从仓库中取东西时,就不能将生产好...
  • 进程间的同步与互斥

    千次阅读 2018-05-13 10:04:23
    同步 互斥
  • 进程的互斥与同步

    2013-03-23 21:07:37
    它包括很多设计问题,如进程间通信、资源共享争用、多个进程活动的同步以及分配给进程处理器时间等。  2:进程并发出现在以下三种不同上下文环境中:  多个应用程序、结构化应用程序、操作系统结构。 ...
  • 进程互斥与同步

    2019-04-23 17:11:00
    1:解释并发并行,并说明两者关系。 并发:指两个或多个事件在同一时间间隔发生。 并行:两个或者多个事件在同一时刻发生。...3:为什么说进程的互斥也是一种同步进程互斥也是一种特殊的进程同步关系,即逐...
  • 进程(Process)是计算机中程序关于某数据集合上一次运行活动,是系统进行资源分配和调度基本单位,是操作系统结构基础。 线程(英语:thread)是操作系统能够进行运算调度最小单位。它被包含在进程之中,...
  • 进程间同步与互斥

    2019-12-07 01:05:34
    [2019 百度 计算存储系统研发工程师笔试] 描述只读锁和读写锁的互斥关系 描述linux文件系统读写IO流程,从vfs到块设备层。
  • 进程互斥与同步后续

    2019-04-23 17:42:00
    解释并发并行,并说明两者关系。 答:并行是指两个或者多个事件在同一时刻发生;而并发是指两个或多个事件在同一时间 隔发生。 ... 为什么说进程的互斥也是一种同步? 答:进程同步是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,408
精华内容 563
关键字:

进程间的互斥与同步