进程互斥和同步

发表于 | 分类于 ，

临界区和临界资源

  • 什么叫临界区(critical section) ？

    在并发进程中，对共享变量操作的那段程序叫临界区。或把不允许多个并发进程交叉执行的一段程序称为临界区

  • 与时间有关的错误

    对于一组交往的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现，表现形式：
    • 结果不唯一
    • 永远等待

  • 什么叫互斥？

    一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥
    而一次仅允许一个进程使用的资源称为临界资源（critical resource）

  • 临界区调度原则

    • 一次至多一个进程能够进入临界区内执行
    • 如果已有进程在临界区，其他试图进入的进程应等待
    • 进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入

  • 实现临界区的软件算法Peterson算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    bool inside[2];
    inside[0]=false;
    inside[1]=false;
    enum {0,1} turn;

    cobegin
    process P0( ) {                   
      inside[0]=true;    //p0想要进入临界区
      turn=1;            //p1能够进入临界区 
      while(inside[1]&&turn==1);    //p1在临界区，等待……
        {临界区};                      
        inside[0]=false;   //p0退出临界区
    }

    process P1( ) {
       inside[1]=true;    //p1想要进入临界区
       turn=0;            //p0能够进入临界区 
       while(inside[0]&&turn==0);    //p0在临界区，等待……
        {临界区};                     
       inside[1]=false;   //p0退出临界区
    }                                 
    coend
    //turn只能取一值，故总有一个进程能进入临界区
    • 实现临界区管理的硬件设施
      • 关中断
      • 测试并建立指令
      • 对换指令

  • 进程互斥

    • 锁和上锁、开锁操作

      一个进程使用某个临界资源之前必须完成下列操作：
    1. 考察锁位的值

    2. 若原来的值是为“0”，将锁位置为“1”

      （占用该资源）

    3. 若原来值是为“1”，该资源已被别人占用），则转到第1步
    4. 当进程使用完资源后，将锁位置为“0 ” ，称为开锁操作

  • 信号灯和P、V操作

    • 信号灯(semaphore)的概念

      • 信号灯的概念是由Dijkstra提出的（1968)
      • 他把互斥的概念抽象到信号量这个概念中
      • 信号量是一个被保护的变量，只有P操作、V操作和一种称为信号量初始化操作才能访问和改变它的值

    • 信号灯的定义

      信号灯是一个确定的二元数组（s,q）
      • s ：是一个有非负初值的整型变量，代表资源的实体。在实际应用中应准确地说明s的意义和初值
      • q ：是一个初始状态为空的等待队列

    • P、V操作

      信号灯的值仅能由P、V操作来改变。

      • P操作记为：P(S)，P操作是一个原子操作
      • V操作记为：V(S)，V操作是一个原子操作

      在实际操作系统中，一般情况下是由机器硬件提供P、V操作的指令。若机器不提供P、V操作的指令，则操作系统提供P、V操作原语

      • P操作

        1
        2
        3
        4
        5
        {
        s--;        //该进程想要对s进行操作
        if(s<0)     //如果s资源不足
        挂起该进程;
        }

      • V操作

        1
        2
        3
        4
        5
        {
        s++;        //对s操作完毕，归还资源
        if(s<=0)    //存在想要对s操作的挂起的资源
        唤醒挂起的进程;
        }

  • 进程同步

    • 同步

      所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步在操作系统中，同步有各种各样，但归纳起来有两类：
      • 诸进程合作完成某工作的逻辑顺序
      • 对系统资源的共享。如两个进程共享一个缓冲区

  • 经典的同步/互斥问题

    1. 生产者－消费者问题

      假定缓冲区buffer是一个有界缓冲区，可存放n个数据，同时假定有K个CP进程不断地产生数据，并送buffer；有m个IOP进程从缓冲区中取数据打印

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      int full = 0        //缓冲区产品数目
      int empty = n       //缓冲区可存放的产品的空位
      int mutex = 1       //对缓冲区互斥信号灯

      main()
      {
          cobegin
              producer();
              consumer();
          coend
      }

      producer()
      {
          while(生产未完成)
          {
              ……;
              生产一个产品;
              p(empty);
              p(mutex);
              将产品放入缓冲区;
              v(mutex);
              v(full);
          }
      }

      consumer()
      {
          while(还要继续消费)
          {
              p(full);
              p(mutex);
              从缓冲区取出一个产品;
              v(mutex);
              v(empty);
              消费一个产品;
              ……;
          }
      }

    2. 读者和写者问题

      有十个读者和两个编辑同时处理一篇文章，对于读操作是可以同时进行的，若有读者正在读这篇文章，编辑就不能工作，若编辑正在处理这篇文章，读者就不能作读操作，编辑与编辑的工作也是互斥的，试用信号灯及P、V操作写出读者与编辑之间协同工作的程序描述

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      int mutex = 1;     //读者与编辑，编辑与编辑的互斥信号灯
      int mutex1 = 1;    //对count操作的互斥信号灯
      int count = 0;

      reader()
      {
          p(mutex1);
          if(count == 0) //若该进程是第一个读文章
              p(mutex);
          count++;
          v(mutex1);
          读文章;
          p(mutex1);
          count--;
          if(count == 0) //若该进程是最后一个读完文章
              v(mutex);
          v(mutex1);
      }

      editor()
      {
          p(mutex);
          编辑文章;
          v(mutex);
      }

    3. 理发师睡觉问题

      理发店里有一位理发师、一把理发椅和n把供顾客等候理发坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉，当一顾客来到时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等，如果没有空椅子，他就离开。用信号灯和P、V操作写出理发师和顾客行为的程序描述。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      int chair = n;
      int customer = 0;
      int barber = 1;
      int mutex = 1;

      barber()
      {
          while(true)
          {
              p(customer);
              理发;
              p(mutex);
              chair++;
              v(barber);
              v(mutex);
          }
      }

      customer()
      {
          while(true)
          {
              p(mutex);
              if(chair == 0)
                  离开;
              else
              {
                  chair--;
                  v(customer);
              }
              v(mutex);
              p(barber);
              理发;
          }
      }

    • 哲学家就餐问题

      • 五个哲学家围坐在一个园桌周围，每个哲学家面前都有一盘通心面，由于面条很滑，所以要两把叉子才能夹住。相邻两个盘子间有一把叉子
      • 哲学家的生活包括两种活动：即吃面条和思考。当哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次拿一把，不分先后次序，如果成功，他就开始吃面条，吃完后放下叉子，继续思考。试用信号灯及P、V操作写出哲学家行为的程序描述，要求不能让某个（或某些哲学家饿死）

  • 结构化的同步/互斥机构-管程

    虽然信号量是一种既方便又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作P（S），V（S）。这使大量的同步操作分散在各个进程中。这不仅给系统的管理带来麻烦，而且还会因同步操作的使用不当而导致系统死锁。便产生了一种新的进程同步工具 — 管程，定义：

    将共享资源和与共享资源有关的操作集中在一个模块中，可单独编译。即管程对共享资源进行了封装，将信号量及其操作原语封装在一个对象内部。进程只能互斥进入管程，在一个管程中，不能同时有两个活动的进程