进程的描述与控制

• 1.前趋图与程序执行
  • 1.1 前趋图介绍:
    • 描述程序先后执行顺序，又称为有向无循环图，可记为DAG(Directed Acyclic Graph)
    • 如进程Pi与进程Pj存在着前趋关系，可写为Pi -> Pj(或（Pi,Pj）)，表示在Pj开始前Pi必须完成，这里称Pi为Pj的直接前趋，Pj为Pi的直接后继，在前趋图中，没有直接前趋的点称为初始节点(Initial Node)，没有直接后继的点称为终止节点(Final Node)
    • 需要注意的是，前趋图是不允许有循环的，原因可从定义中找，如S1->S2->S3,不能要求S2和S3之间还有循环，这个循环是指，在上图的前提下，又要求S2执行前要求S3必须执行完成
  • 1.2 程序顺序执行
    • 顺序执行的特征:
      • 顺序性:每一个操作必须在上一个操作结束之后才能开始
      • 封闭性:程序运行时，独占本机资源，执行结果不受外界干扰
      • 可再现性:只要程序初始条件和环境相同，重复执行，结果都相同
  • 1.3 程序并发执行
    • 特征:
      • 间断性:并发的程序会有相互制约的关系，在程序运行时，会具有"执行--暂停--执行"这种间断性的活动规律
      • 失去封闭性:并发执行时，由于系统的资源被这些并发程序共享，资源状态会被这些程序改变，所以导致某一程序运行时，他的运行环境必然受到其他程序的影响
      • 不可再现性:失去了封闭性，那么资源状态也不稳定，所以也会失去可再现性
• 2.进程的描述

  • 2.1 定义与特征

    • 为了使参与并发执行的每个程序都能独立的运行，在操作系统中都为其配置一个专门的数据结构->进程控制块(Process Control Block,PCB)。使用PCB来描述进程的基本情况和活动过程，进而控制管理进程

    • 程序段、相关的数据段和PCB构成了进程实体(进程映像)，一般简称进程实体为进程

    • 创建进程，撤销进程，都指的是创建进程实体中的PCB和撤销进程实体中的PCB

    • 定义:

      • 进程是程序的一次执行
      • 进程是一个程序机器数据在处理机上顺序执行时所发生的活动
      • 进程是具有独立功能的程序在一个数据集合上运行的过程，是系统进行资源调度和分配的一个独立单元
      • 一句话：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

    • 特征:

      • 动态性:进程的实质是进程实体的运行过程，动态性是进程的最基本的特征；具有"创建而产生，调度而执行，撤销而消亡"，即进程实体具有一定的生命期，而程序指示一段有序指令的集合，并存放在某种介质上，即静态的
      • 并发性:指多个进程实体共存于内存中，且能在一段时间内同时运行。引入进程目的就是为了使进程实体能与其他进程实体并发执行
      • 独立性:指进程实体是一个能独立运行，独立获得资源和独立接受调度的基本单位
      • 异步性:指进程是按照异步方式运行的，即按照各自独立的、不可预知的速度向前推进

    • 进程的基本状态

      • 就绪(Ready)状态:指进程已分配到除CPU外的所有必要资源，只要获得CPU，便可立即执行。即进程已处于准备好运行的状态
      • 执行(Running)状态:指进程已获得CPU,其程序正在执行的状态
      • 阻塞(Block)状态:指正在进行的进程受到某事件(I/O请求，申请缓存区失败等)暂时无法继续执行时的状态。此时引起进程调度，OS将处理机分配给另一个就绪队列中的就绪进程，将这个阻塞进程处于暂停阶段，称这个暂停状态为阻塞状态，阻塞状态的进程大于一个时，会排成一份队列，称为阻塞队列

    • 三种基本状态的转化

      三种基本状态的转化
      • 创建状态和终止状态
        • 创建状态:进程由创建而产生。创建步骤:①进程申请一个空白PCB②向PCB中填写用于控制和管理进程的信息③为进程分配所必须的资源④将进程转入到就绪状态插入到就绪队列中。若进程创建所需资源不足时，进程不能被调度运行，因为创建工作尚未完成，把这个状态称为创建状态
      • 终止状态:终止步骤:①等待OS进行善后处理②将PCB清零③将PCB空间返还系统

    • 挂起操作和进程状态的转换

      • 挂起操作:当挂起操作作用于某个进程时，该进程将被挂起，意味着进入静止状态，若该进程正在执行，将暂停执行，若原本处于就绪状态，将不接受调度。与挂起操作对应的是激活操作
      • 挂起状态的引入
        • 终端用户的需要
        • 父进程的请求
        • 负荷调节的需要
        • 操作系统的需要
      • 引入挂起操作或激活操作后，三个基本进程状态的转换
        • 活动就绪->静止就绪(引入挂起)
        • 活动阻塞->静止阻塞(引入挂起)
        • 静止就绪->活动就绪(引入激活)
        • 静止阻塞->活动阻塞(引入激活)
      • 引入挂起操作后五个进程状态的转换
        • NULL -> 创建
        • 创建 -> 活动就绪
        • 创建 -> 静止就绪

        • 执行 -> 终止

          
          
          Snip20170109_1.png

  • 进程管理中的数据结构

    • 操作系统中用于管理控制的数据结构

      • 数据结构:为了便于对计算机中的各类资源(硬件和信息等)的使用和管理，OS将他们抽象为相应的各种数据结构，并提供一组对资源进行操作的命令，用户可利用这些数据结构及操作命令来执行相应的操作，而无需关心他们实现的具体细节。

      • OS中用于管理控制的数据结构

        • OS中，对每个资源和进程都设置了一个数据结构，来表征其实体。包含了资源或进程的表示、描述、状态等信息和指针。通过指针，可以进行分类，便于OS查找

          
          
          Snip20170109_3.png

      • 进程表(进程控制块PCB)

        • 作用:
          • 作为独立运行基本单位的标志:OS是通过PCB去感知进程的存在，PCB已经成为进程存在于系统的中唯一标志
          • 能实现间断性运行方式:在多道程序环境下，程序是间断性运行，所以进程必须要保留运行时的CPU现场信息，再次被调度运行时，还需恢复CPU现场信息，这个信息保留在PCB中
          • 提供进程管理所需要的信息:进程被调度时，根据PCB中记录的程序和数据在内存或外存中的始址地址，找到程序和数据。
          • 提供进程调度所需要的信息:进程只有在就绪状态才能被调度运行，而这种进程的状态信息就是存储在PCB中，另外比如优先级，已执行时间等等也是在PCB中
          • 实现与其他进程的同步和通信:PCB中具有用于实现进程通信的区域和通信队列指针等
        • PCB中的信息(主要)
          • 进程标识符
            • 外部标识符:为了方便用户(进程)对进程的访问，由创建者提供，一般由数字、字母组成
            • 内部标识符:方便系统对进程的使用，赋予每个进程一个唯一的数字标识符，通常是进程的序号
          • 处理机状态
            • 主要由处理机中的各种寄存器中的内容组成，这些寄存器包括①通用寄存器②指令计数器③程序状态字PSW④用户栈指针
          • 进程调度信息
            • 进程状态
            • 进程优先级
            • 进程调度所需其他信息，如进程已执行时间、等待CPU时间总和等
            • 事件:指进程状态由执行->阻塞所发生的事件，即阻塞原因
          • 进程控制信息
            • 指用于进程控制所需要的必须信息:①程序和数据的指针②进程同步和通信机制③资源清单④链接指针(给出了PCB所在队列的下一个进程的PCB首地址)
        • PCB的组织方式
          • 线性方式:将系统中所有PCB都组织在一张线性表中，将该表的首址存放在内存中的专用区域中。优点:简单，开销小。缺点:每次查找都要扫描整张表
          • 链接方式:把相同状态进程的PCB分别通过PCB中链接字链接成一个队列。就会形成就绪队列、空白队列、若干阻塞队列等，队列中，往往会进行优先级排列
          • 索引方式:根据所有进程状态的不同，建立几张索引表，如就绪索引表、阻塞索引表等，并把各索引表的首地址存在内存中一些专用单元中
• 3.进程控制
  • 进程控制主要包括哪些:创建、终止、阻塞、状态转换等，一般是通过OS中内核的原语实现
  • OS内核:
    • 一些与硬件紧密相关的模块、各种常用设备的驱动程序以及运行效率较高的模块，安排在仅靠硬件的软件层次中，并常驻内存，这些通常被称为OS的内核，安排OS内核的目的:①便于保护这些软件，防止被篡改②提高OS的运行效率
    • OS内核主要功能:
      • 支撑功能:
        • 中断处理:是内核最基本的功能，是OS赖以活动的基础，为了提高程序执行的并发性，减少处理机中断的过程，内核对中断进行“有效处理”后，便转入相关的进程
        • 时钟管理:是内核的基本功能。如时间片轮的调度中，时间片用完时，时钟管理产生一个中断信号，使调度程序重新调度
        • 原语操作:原语->若干条指令组成，用于完成一定功能的一个过程。与其他的过程区别在于:是“原子操作”。(原子操作->一个操作中所有动作要么全做，要么全不做。也就是说是一个不可分割的基本单位)。因为原语的特性，所以原语执行过程中不允许被打断。原语有:对链表操作的原语、用来实现进程同步的原语等
      • 资源管理功能:
        • 进程管理:由于进程管理中的各个功能模块调用频率高或者被其他功能模块所需要，为了提高OS性能，将他们都放在内核中
        • 存储器管理:存储器管理软件的运行频率较高，放在内核中，来保证存储器管理具有较高的运行速度
        • 设备管理:因为设备管理与硬件(设备)紧密相关，所以大部分都设置在内核中。如驱动程序、来缓和CPU和I/O速度不匹配矛盾的缓冲管理等模块
    • 进程的创建
      • 进程的层次结构:OS中允许进程创建另一个进程，创建进程的进程->父进程，被创建的进程->子进程，子进程可创建更多的孙进程等，形成一个进程家族。子进程可继承父进程的资源，撤销父进程也会撤销其所有的子进程；需要注意的是:Windows中不存在进程层次结构的概念，所有进程地位都相同，而是获得句柄有否，控制与被控制的简单关系
      • 进程图:为了形象地描述一个进程的家族关系引入来描述进程间关系的有向树
      • 引起创建进程的事件:使程序之间并发运行，需要分别建立进程。导致进程创建进程的事件有:
        • 用户登录:分时系统中，终端键入登录命令，成功就建立一个进程，并插入就绪队列
        • 作业调度:多道批处理系统中，调度到某个作业时，便装入内存，创建进程，并插入就绪队列
        • 提供服务:当运行中的用户程序提出某种请求后，系统将专门创建一个进程来满足用户提出的服务，如打印请求
        • 应用请求:以上三种都是系统内核为用户创建的进程，而这类事件是用户进程自己创建新进程
      • 进程的创建: OS调用进程创建原语Creat按照下述四个步骤创建新进程
        • 申请空白PCB:为新进程申请唯一的数字标志符，并从PCB集合中索取一个空白PCB
        • 为新进程分配其运行所需资源:如内存、文件、I/O设备和CPU时间等，这些从OS或者父进程中获取
        • 初始化PCB:包括①初始化标识信息②初始化处理机状态信息③初始化处理机控制信息
        • 若进程就绪队列可以接纳这个新进程，就插入到就绪队列
    • 进程的终止
      • 引起进程终止的事件
        • 正常结束
        • 异常结束
        • 外界干预
      • 进程的终止过程
        • 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从PCB中读取进程状态
        • 若该进程状态处于执行状态，应立即终止该进程的执行，并置换调度标志为真，代表该进程终止后应重新进行调度
        • 若该进程还有子孙进程，还应将所有子孙进程都终止
        • 将被终止的进程所拥有的资源归还于父进程或者系统
        • 将被终止的进程PCB从所在队列(或链表)中移出，等待其他程序来搜集信息
    • 进程的阻塞和唤醒
      • 引起进程阻塞和唤醒的事件
        • 向系统请求共享资源失败
        • 等待某种操作的完成
        • 新数据尚未到达
        • 等待新任务的到达
      • 进程阻塞过程:正在执行的进程，发生了上述事件，便调用阻塞原语Block将自己阻塞，所以阻塞是一种自身行为
      • 进程唤醒过程:当被阻塞进程发生了所期待的事件，由有关进程调用唤醒原语wakeup，将这个进程唤醒:①将被阻塞进程从等待改时间的阻塞队列中移出②将其PCB中的现行状态由阻塞改为就绪③将PCB插入到就绪队列中
      • 注意:block原语与wakeup原语是必须成对使用，即使用了block原语，必须在相关进程中安排一条对应的wakeup原语
    • 进程的挂起和激活
      • 进程的挂起:执行过程:①检查被挂起进程状态，活动就绪->静止就绪，活动阻塞->静止阻塞②把该进程的PCB复制到某指定的内存区域，这是为了方便用户或父进程检查其运行情况③若该进程正在运行，则转向调度程序重新调度
      • 进程的激活过程:执行过程:①检查被激活进程状态，静止就绪->活动就绪，静止阻塞->活动阻塞②若执行的是抢占调度策略，就由调度程序将被激活进程与当前进程优先级比较，选择高的运行
• 4.进程的同步
• 引入同步原因:OS引入进程后，既能提高系统的吞吐量，也能提高系统的资源利用率，但是也使得系统的变得复杂，如果不对多个进程进行妥善管理，那么这些进程就会对资源的无序争夺造成混乱，所以要引入进程同步机制，来使得多个进程有条不紊的执行
  • 进程同步的基本概念
    • 两种形式的制约关系
      • 间接相互制约关系
        • 多个程序在并发执行时，由于共享系统资源，比如CPU，I/O设备等，导致这些并发程序之间存在着相互制约关系。另外对于打印机、磁带机这些只有一个的临界资源，必须保证多个进程对他的访问时互斥的。对于系统中这些资源，用户要使用，首先申请，不能任由用户进程随意直接使用
      • 直接相互制约关系
        • 某些应用程序，为了完成任务而创建了多个进程，这些进程为了完成同一项任务而相互合作。直接相互制约关系就源于它们之间的相互合作。如输入进程A和计算进程B，B会等待A的输入后开始执行
    • 临界资源
      • 一些硬件资源比如打印机、磁带机等，都是临界资源，另外除了上述的硬件临界资源还有软件临界资源。并发进程间应采取互斥方式，来实现对此资源的共享
    • 临界区(critical section)
      • 把每个进程中访问临界资源的代码称为临界区。①进入区:临界区前面增加的用来检查临界资源是否正在被访问的代码②临界区:不再解释③退出区:临界区后面加上的代码，来修改代表临界资源正被访问的标志为未被访问的标志④剩余区:除了进入区、临界区、退出区之外的其他部分代码
    • 同步机制应遵循的规则
      • 空闲让进
      • 忙则等待
      • 有限等待
      • 让权等待
  • 硬件同步机制
    • 关中断

      • 是实现互斥最简单的方法之一。进入锁 测试之前关闭中断，完成锁测试并上锁后才能打开中断。即进程在临界区执行时，OS不相应中断，也就不会调度进程，也就不会进程切换。缺点:①滥用关中断权利可能造成严重后果②若时间过长，会影响系统性能③不适用于多CPU系统，因为一个CPU上关中断不能防止进程在其他处理器上执行相同的临界区代码

      • 使用Swap指令实现进程互斥

          void swap(boolean *a,boolean *b){
              boolean temp;
              temp = *a;
              *a = *b;
              *b = temp;
          }
          // 实现进程互斥伪代码
          boolean lock = FALSE;
          do{
          boolean key = TRUE;
          do{
          swap(&lock,key);
              }while(key!=FALSE);
          临界区操作
          lock = FALSE;
          ...
          }while(TRUE);
        

  • 信号量机制
    • 整形信号量

      • 最初的设计:把整形信号量定义为表示资源数目的整形量S，不同于一般整形量，只能通过两个标准的原子操作wait(S)、singal(S)来访问，被称为P、V操作

          wait(S){
              while(s<=0);  // do no operation
              S--;
          }       
          singal(S){
              S++;
          }   
        

    • 记录性信号量
      • 采用记录性的数据结构得名，包含两个数据项:表示资源数目的整形变量Value,进程链表指针list
    • AND型信号量
      • 针对一个进程需要获得多个共享资源后才执行任务等情况
    • 信号量集
      • 对AND型信号量机制扩充所得，每次可以对临界资源进行一个单位的申请和释放，扩充为可一次申请N个单位
  • 信号量的应用
  • 管程机制
    • 管程(Monitors):一个数据结构和该数据结构上能被并发进程所执行的一组操作

如下图:

Snip20170111_4.png

- 进程对共享资源的访问都是通过这组过程对共享数据结构的操作来实现，这组过程根据资源的使用情况，接受或者阻塞进程对共享资源的访问，确保同一时间只有一个进程访问共享资源，实现进程的互斥
- 管程的结构:

                TYPE<管程名> = MONITOR
                // 在管程内部的数据结构，只能被管程内部的过程访问；反之，管程内部的过程也只能访问管程内的数据结构
                      <共享变量说明>;
                  procedure<过程名>(<形式参数表>);
                    begin
                        <过程体>;
                    end;
                  ....
                  procedure<过程名>(<形式参数表>);
                      begin
                        <过程体>;
                      end;
                begin<管程的局部数据初始化语句序列>;
                  end;




        - 管程相当于围墙，把共享变量和对他操作的若干过程围起来，所有过程要访问临界资源，都必须经过管程才能进入，而管程每次只允许一个进程进入管程，这样实现进程互斥
        - 管程的特性:
            - 模块化
                - 是一个基本数据单位，可单独编译
            - 抽象数据类型
                - 管程中不仅有数据，还有对数据的操作
            - 信息隐蔽
                - 数据结构和过程的实现外部不可见
        - 管程与进程区别
            -  管程定义的是公用数据结构，而进程定义的是私有数据结构PCB
            -  管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中
            -  管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的
            -  管程是被要使用共享资源的进程所调用的，管程和调用它的进程不能并发工作，而进程之间能并发工作，并发性是进程的固有特性
            -  管程是OS中的一个资源管理模块，供进程调用；而进程有生命周期:创建而产生，撤销而消亡
        - *条件变量 *
            - 在管程机制中，当某个进程通过管程请求临界资源未能满足时，管程便调用wait原语使该进程等待，但等待的原因会有多个，通过在P,V操作前引入条件变量来说明作为区别
            - 条件变量是一种抽象数据类型，每个条件变量保存了一个链表，用于记录因该条件变量而堵塞的所有进程
            - 条件变量的定义格式
                -   var x,y:condition;
            - 对条件变量执行的两种操作
                -   wait操作(如x.wait):用来堵塞正在调用管程的进程，并把进程塞入到与条件变量x对应的等待队列，并释放管程，直到x条件变化。此时其他进程可以使用该管程
                -   signal操作(如x.signal):用来唤醒与条件变量x对应的等待队列中的一个进程(因为x条件而堵塞)。若没有这样的进程，则继续执行原进程，不产生任何的结果

• 5.经典进程的同步问题
  • 生产者-消费者问题
    • 这个问题是最著名的进程同步问题。描述了一组生产者和一组消费者共享一个缓存池(有N个缓存池)，生产者通过缓存池向消费者提供物品
    • 定义两个同步信号量
      • empty : 代表缓存池中空缓存池的数量，初始为n
      • full : 代表缓存池中满缓存池的数量，初始为0
    • 实际例子:
      • M个生产者，K个消费者，公用N个缓存区的缓存池
        • 设缓存池的长度为n（n>0）,一群生产者进程P1,P2...Pm,一群消费者进程C1,C2...Ck,如果生产者和消费者是相互等效，只要缓存池未满，生产者就可以把产品送入缓存区，类似地，只要缓存池为空，消费者便可以从缓存区取走产品并消耗他。生产者和消费者的同步关系将禁止生产者向满的缓存池输送产品，也禁止消费者从空的缓存池提取产品
      • Snip20170111_2.png
      • 设置两个同步信号量和一个互斥信号量

        • empty:说明空缓冲区的数目，初值为缓存池数量n，代表有n个空缓冲区使用

        • full:说明满缓存区的数量，即产品数量，初值为0，代表生产者尚未把产品放入缓存池，有0个满缓存区可用

        • mutex:说明该缓存池是一临界资源，必须互斥使用，初值为1

          producer（）{
              while(true){
                  //生产一个产品放入nextp;
                  P(empty);
                  P(mutex);
                  Buffer[in] = nextp;
                  in = (in + 1) mod n;
                  V(mutex);
                  V(full);
              }
          }
          consumer(){
              while(true){
              P(full);
              P(mutex);
              nextc = Buffer[out];
              out = (out + 1) mod n;
              V(mutex);
              v(empty);
              // 消费nextc中的产品
              }
          }
          

      • "生产者-消费者"问题中的注意事项
        • 互斥信号量P、V操作在每一个进程中必须成对出现
        • 对资源信号量(full,empty)的P、V操作也必须成对出现，但可以处于不同的程序中
        • 多个P操作顺序不能颠倒
        • 先执行资源信号量的P操作，再执行互斥信号量P的操作，否则可能引起进程死锁
        • 这是一个同步问题:
          • 消费者想要取产品，缓存区中至少有一个缓存池是满的
          • 生产者想要放产品，缓存池至少有一个缓存区是空的
        • 这是一个互斥问题
          • 缓存池是一个临界资源，因此，各生产着进程和各消费者进程必须互斥访问
      • 使用管程机制解决"生产者-消费者"问题
        • 建立Producer-consumer(PC)管程

                    Monitor producerconsumer{
                        item buffer[N];
                        int in,out;
                        condition notfull,notempty;
                        int count;
                        public:
                        void put(item x){
                            if(count>=N)cwait(notfull);
                            buffer[in] = x;
                            in = (in + 1) % N;
                            count++;
                            csignal(notempty);
                        }
                        void get(item x){
                            if(count<=0) cwait(notempty);
                            x = buffer[out];
                            out = (out + 1) % N;
                            count--;
                            csignal(notfull);
                        }
                        {in=0;out=0;count=0;}
                    }PC;
            - producer-consumer(PC)管程
                - put(item)过程
                    - 生产者利用这个过程将产品放入到缓存池中，若缓存池满(count n)，则等待
                - get(item)过程
                    - 消费者利用这个过程从缓存池中取出产品，若缓存池空(count 0)，则等待
                - cwait(condition)过程:对条件变量notfull和notempty进行操作，当管程被一个进程占用时，其他进程调用该过程时堵塞，并挂在条件condition的队列上
                - csignal(condition)过程:对条件变量notfull和notempty进行操作，唤醒在cwait执行后堵塞在条件condition队列上的进程，如果这样的进程不止一个，则选择其中一个进程实施唤醒操作，若队列为空，什么也不做 
            - 利用管程解决"生产者-消费者"问题时，其中的消费者和生产者可描述为:

            
                    void producer(){
                        item x;
                        while(TRUE){
                            ...
                            producer an item in nextp;
                            PC.put(x);
                        }
                    }
                    void consumer(){
                        item x;
                        while(TRUE){
                            PC.get(x);
                            consumer the item in nextc;
                            ...
                        }
                    }
                    void main(){
                        cobegin
                        producer();
                        consumer();
                        coend
                    }

                
    - 哲学家进餐问题
        -   描述:有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。
        - 哲学家进餐问题可看作是并发进程并发执行时，处理共享资源的一个有代表性的问题。
        - 使用记录性信号量解决哲学家进餐问题

                semphore chopstick[5] = {1,1,1,1,1}; // 分别表示5只筷子
                philosopher(int i){
                    think;
                    P(chopstick[i];
                    P(chopstick[(i+1) mod 5]);
                    eat;
                    V(chopstick[i];
                    V(chopstick[(i+1) mod 5]);
                }
                // 如果五个哲学家同时eat，各自拿起了左边的筷子，那么他们试图去拿右边的筷子时，因为已经没有筷子了，就会陷入无期限等待，可能引起死锁
                // 解决死锁
        - 解决方法一:设置一个信号量Sm,其初值为4，用于限制同时进餐的哲学家数目至多为4，这样第i个哲学家的活动描述为:

                while(TRUE){
                    wait(Sm);
                    wait(chopstick[i]);
                    wait(chopstick[(i+1) mod 5]);
                    eat;
                    signal(chopstick[i]);
                    signal(chopstick[(i+1) mod 5]);
                    signal(Sm);
                    ...
                    think;
                }
            - 解决方法二:对五个哲学家，规定:单号者进餐时，先拿左手(i)的筷子，再拿右手(i+1)的筷子。双号相反。这样即使五个人同时就餐，就不会产生死锁

                    while(TRUE){
                        if odd(i){
                            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;
                        ...
                    }

• "读者-作者"问题
  • 描述
    • 一个数据对象（数据文件或记录）可被多个进程共享。其中，读者（reader）进程要求读，写者（writer）进程要求写或修改。
      • 为了保证读写的正确性和数据对象的一致性，系统要求：当有读者进程读文件时，不允许任何写者进程写，但允许多个读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进程读。
    • 问题的解决
      • 该问题的同步算法描述

        • 设置一个共享变量和两个信号量

        • 共享变量readcount:记录当前正在读数据集的读进程数目，初值为0

        • 读互斥信号量rmutex:表示读进程互斥的访问共享变量readcount,初值为1

        • 写互斥信号量wmutex:表示写进程与其他进程(读、写)互斥地访问数据集，初值为1

                   semaphore rmutex = 1;
                   semaphore wmutex = 1;
                   int readcount = 0;
                   main(){
                       cobegin
                       reader();
                       write();
                       coend
                   }  
                   
                   reader(){
                       while(TRUE){
                           P(rmutex);
                           if(readcount == 0) P(wmutex);
                           readcount++;
                           V(rmutex);
                           // 读数据集
                           P(rmutex);
                           readcount--;
                           if(readcount == 0) V(wmutex); // 第末位读者允许写者进
                           V(rmutex);
                       }
                   }
                   
                   write(){
                       while(TRUE){
                           P(wmutex);//阻止其他进程读、写
                           学数据集；
                           V(wmutex);// 允许其他进程读、写
                       }
                   }