操作系统进程管理

1、第二章 进程管理主要内容： 进程的基本概念： 进程的定义。 进程的组成。 进程的状态及变迁。 进程控制。 进程的互斥与同步。重点与难点：进程的同步。1. 进程的基本概念 一、为什么要引入进程？ 1.程序的顺序执行 程序的顺序执行过程： 若将程序执行视为3类操作：输入（I）、计算（C）和打印（P） 组成一个作业序列，则顺序执行多个作业的过程如下：I1C1P1I2C2P3InCnPn作业1作业2作业n每个作业的顺序特点： 顺序性：严格按提交的顺序执行；前一步工作完成 后，后一步工作才开始。 封闭性：程序一旦执行，其运行的结果不受外界的影响。 可再现性（与时间无关性）：程序执行的结果与它的执行速度

2、无关。（与时间无关性），只与初始条件有关。 即：相同的初始条件，则重复执行程序，得到的 结果是相同的。 注：顺序执行程序具有与时间无关性的先决条件是：要求程序 自身是封闭的。 2、程序的并发执行 （1）程序并发执行过程：I1I2I3I4C1C2C3P2P1并发执行：I2和C1，I3、C2和P1，I4、C3和P2 （2）并发程序段的语句表示 cobegin s1；s2；.；sn； （ s1；s2；.；sn 执行次序任意） coend （3）特点 a、失去了程序的封闭性和可再现性。 运行的结果与并发程序的执行速度有关，即与时间有关； 一个程序的执行可能会改变另一个程序的相同变量值。 例： 程序A

3、程序BN=N+1;PRINT(N);N=0;L2:L1:A、B程序有公共变量N，并发执行的可能过程： N=N+1PRINT(N)N=0 PRINT(N)N=0 N=N+1 PRINT(N)N=N+1 N=0 设N的初值为N0，则： N的结果：0；打印值：N0+1。 N的结果：1；打印值：N0。 N的结果：0；打印值：N0。 B、程序与计算不再一一对应。 C、程序并发执行时有相互制约关系。 特别程序有相同的公共变量，或共享一个资源时。 引入进程的原因： 提高资源的利用率。 正确地描述程序的执行情况。 二、进程的定义 1.进程的定义 一个程序，在给定的活动空间和初始环境下，在一个处理机上 的一次执

4、行过程。 2. 进程与程序的区别与联系 （1）程序是指令的有序集合，本身无任何运行的含义，它是一种静态的概念。进程是程序在cpu上的一次执行过程，它是一种动态的概念。这是它们的本质区别。 程序可作为软件资料长期保存。 进程有一定的生命期，它可动态地产生和消亡，即：进程可由创建而产生，由调度而执行，因得不到资源而暂停，以致最后由撤销而消亡。 （2）进程是一个能独立运行的单位，能与其它进程并发执行 。（独立性和并发性） （3）进程是一个竞争系统有限资源的基本单位，也是cpu调度的基本单位。 （4）多个不同的进程可以包含相同的程序。即：同一个程序同时运行在不同的数据集合上，他会属于不同的进程。 如：

5、一个能被多个用户调用的程序，称为可再入程序（又称：纯代码程序）：执行中自身不能改变的程序。如：编译程序，操作系统程序等。 3.进程的属性 进程具有动态性。 多个不同的进程可以包含相同的程序。 进程可并发执行。 进程有三种基本状态。 三、进程的状态及变迁 1.进程的三种基本状态 用状态描述进程的活动规律：执行-暂停-准备又执行。 （1）进程的三种基本状态 进程的三种基本状态：运行状态、就绪状态和等待状态运行状态、就绪状态和等待状态（阻塞 状态、封锁状态、睡眠状态）。 运行状态：当进程由进程调度程序调度而获得cpu控制权，其程 序正在cpu上执行，此时进程所处的状态。 就绪状态：处于等待cpu队列

6、中的进程，它们一切准备就绪 （除cpu外，所需的资源都有了），只欠cpu的状态。 等待状态：正在等待某个事件的完成（如：I/O）。 注意：进程在活动时至少要区分这三种状态。 复杂的系统还可以设置多种状态：挂起状态、死琐状态、 高（低）优先就绪状态等。 （2）为什么要将进程区分三种状态？ 在多道程序运行系统中，cpu和其他资源的数目远远少于进程的数目，往往只有少数的进程才能获得cpu并其上运行，处于运行状态。获不到cpu的进程只有处于就绪状态；因等待除cpu以外的资源的进程就处于等待状态。 2.进程状态变迁图 进程状态变迁图：结点：表示状态；箭头表示状态变化的方 向；箭头旁要标注变迁的原因。 如

7、：某个分时系统的进程状态变迁图：运行就绪等待请求系统服务（如：需要I/O）服务完成进程调度时间片到变迁的原因： 运行状态等待状态：等待I/O传输，申请内存空间，程序运行 出错，等等。 等待状态就绪状态： I/O传输完成，内存空间获得，程序运行 错误处理完成，等等。 就绪状态运行状态：由OS中的进程调度程序，按一定的原则 调度就绪队列中进程占用cpu。 运行状态就绪状态：时间片到，高优先进程进入就绪队列， 等等。 四、进程的组成 1.进程的组成 三部分组成：数据，程序，进程控制块（PCB）。 2.进程控制块 进程控制块进程控制块PCB (Process Control Block)是操作系统为描

8、述进是操作系统为描述进程状态过程所采用的一个与进程相联系的数据结构。程状态过程所采用的一个与进程相联系的数据结构。 作用：系统通过作用：系统通过进程控制块对进程实施控制和管理。进程控制块对进程实施控制和管理。 当系统创建一个进程时，就建立一个当系统创建一个进程时，就建立一个PCB，然后，系统根据，然后，系统根据进程活动状态通过进程活动状态通过PCB加以控制，进程完成任务后，由系统回收加以控制，进程完成任务后，由系统回收PCB，进程就消亡了。，进程就消亡了。 PCB是系统感知进程存在的唯一实体。是系统感知进程存在的唯一实体。 进程的类型：进程的类型：（1）按进程性质）按进程性质v系统进程：系统进

9、程：起着资源管理和控制的作用起着资源管理和控制的作用v用户进程用户进程 ：执行用户程序的进程执行用户程序的进程 （2）按进程活动特征）按进程活动特征 v计算量大的进程计算量大的进程 vI/O量大的进程量大的进程 3.进程控制块（进程控制块（PCB）的一般结构）的一般结构一般包括4类信息： 标识信息：说明进程 名。 说明信息：说明进程的 基本情况。 现场信息：保存cpu现场信息。 管理信息：用于进程调度。五、进程队列 将状态相同进程的PCB组成队列链表（单向或双向链表），管理进程。六、进程控制六、进程控制 对进程的产生、运行、暂停、终止等操作进行的控制。对进程的产生、运行、暂停、终止等操作进行的

10、控制。 进程控制包括进程控制包括： 进程创建进程创建、 进程撤消进程撤消、 进程阻塞进程阻塞、 进程唤醒进程唤醒、 改变进程优先数改变进程优先数、 调度进程运行。调度进程运行。 这些操作都要对应地执行一个特殊的程序段（操作系统核心程这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语（一种特殊的系统调用）。上叫原语（一种特殊的系统调用）。 控制机构：原语控制机构：原语 原语：是一种特殊的系统调用命令，执行时不可中断。原语：是一种特殊的系统调用命令，执行时不可中断。 进程

11、的控制原语：进程的控制原语： 创建原语、撤消原语、阻塞原语、唤醒原语。创建原语、撤消原语、阻塞原语、唤醒原语。 1.进程创建进程创建 创建者：由用户向创建者：由用户向os请求、或者由请求、或者由os中相关的调度程序中相关的调度程序 （如：作业调度程序）创建。（如：作业调度程序）创建。 创建的手段：调用进程创建原语。如创建的手段：调用进程创建原语。如UNIX系统中：系统中： create (name，priority，start-addr) 创建进程的工作：为程序分配一个工作区、建立创建进程的工作：为程序分配一个工作区、建立PCB、置、置 进程为就绪状态入就绪队列。进程为就绪状态入就绪队列。 导

12、致导致创建进程的事件：创建进程的事件： 用户登录：在分时系统中用户登录成功，系统为用户建用户登录：在分时系统中用户登录成功，系统为用户建 立一个进程。立一个进程。 作业调度：当作业调度程序调入一个作业到内存，立即作业调度：当作业调度程序调入一个作业到内存，立即 为该作业建立对应的进程。为该作业建立对应的进程。 提供系统服务：在程序中，使用系统调用命令请求系统服提供系统服务：在程序中，使用系统调用命令请求系统服 务，系统专门创建一个进程来满足用户的请求。务，系统专门创建一个进程来满足用户的请求。 应用请求：用户在程序中应用创建进程命令建立进程。应用请求：用户在程序中应用创建进程命令建立进程。 2

13、.撤销进程撤销进程 撤销者：用户用撤销原语撤销进程。如：撤销者：用户用撤销原语撤销进程。如：UNIX中：中： kill（）或（）或exit（）。（）。 在进程家族中，由父进程撤销子进程。在进程家族中，由父进程撤销子进程。 撤销进程的工作：回收进程占用的资源和撤销进程的工作：回收进程占用的资源和PCB，并从相应队列，并从相应队列 和进程总链中摘除。和进程总链中摘除。 导致导致撤销进程的事件：撤销进程的事件： 正常结束：进程运行完毕。正常结束：进程运行完毕。 异常结束：由异常事件引起：异常结束：由异常事件引起： 越界错误：程序访问超出进程访问区。越界错误：程序访问超出进程访问区。 特权指令错：用户

14、程序使用了特权指令。特权指令错：用户程序使用了特权指令。 使用非法指令错、运行超时错、使用非法指令错、运行超时错、I/O故障错等。故障错等。 外界干预：操作员干预、外界干预：操作员干预、os干预、父进程请求等。干预、父进程请求等。 3. 进程的阻塞与唤醒进程的阻塞与唤醒 创建原语和撤消原语虽然使进程从产生到消亡，但使进程从运行创建原语和撤消原语虽然使进程从产生到消亡，但使进程从运行到阻塞、从阻塞到就绪的状态的过度，可使用两种方法：到阻塞、从阻塞到就绪的状态的过度，可使用两种方法： 直接使用直接使用阻塞原语与唤醒原语实现：由阻塞原语与唤醒原语实现：由os控制。控制。 通过进程的同步机构或通信机构

15、来实现：由程序员在程序中控通过进程的同步机构或通信机构来实现：由程序员在程序中控 制。制。 引起引起进程的阻塞或唤醒的事件：进程的阻塞或唤醒的事件： 请求系统服务请求系统服务 启动某个操作：如启动启动某个操作：如启动I/OI/O后进程被后进程被阻塞，阻塞，I/O完成后被唤醒。完成后被唤醒。 新数据未达到：合作进程之间，一个进程未收到另一进程的新数据未达到：合作进程之间，一个进程未收到另一进程的 信息，则等待。收到被唤醒。信息，则等待。收到被唤醒。 无新工作可做：系统进程完成任务后，无新工作可做，将自己无新工作可做：系统进程完成任务后，无新工作可做，将自己 阻塞，等待新工作的到来。阻塞，等待新工

16、作的到来。 （1）进程的阻塞）进程的阻塞 当进程所期待的某个事件尚未出现时，该进程调用阻塞原语将自当进程所期待的某个事件尚未出现时，该进程调用阻塞原语将自己阻塞。己阻塞。 阻塞进程的工作：中断阻塞进程的工作：中断cpu； 置进程为阻塞状态；置进程为阻塞状态； 保留保留cpu现场于保护区；现场于保护区； 将进程的将进程的PCB插入到等待队列中，转进程调度插入到等待队列中，转进程调度 程序调度另一进程运行。程序调度另一进程运行。 （2）进程的唤醒）进程的唤醒 进程所期待的某个事件出现时，由进程所期待的某个事件出现时，由“发现者发现者”进程调用唤醒进程调用唤醒原语唤醒该进程。原语唤醒该进程。 唤醒进

17、程的工作：将进程移出等待队列；唤醒进程的工作：将进程移出等待队列； 置进程状态为置进程状态为“就绪就绪”； 将进程入就绪队列。将进程入就绪队列。 2.UNIX系统的进程系统的进程 一、一、UNIX的进程组成的进程组成 三部分组成：进程控制块、正文段和数据段。三部分组成：进程控制块、正文段和数据段。 1.进程控制块进程控制块 组成：基本控制块和扩充控制块组成：基本控制块和扩充控制块 目的：节省目的：节省PCB占用内存。占用内存。 （1）基本进程控制块基本进程控制块 proc结构结构：存放进程的最基本的控制和管理：存放进程的最基本的控制和管理信息，不论该进程是否处于运行状态，系统都要访问的信息，必

18、信息，不论该进程是否处于运行状态，系统都要访问的信息，必须常驻内存；须常驻内存； 如：进程标识信息、状态、优先数、代码长度等。如：进程标识信息、状态、优先数、代码长度等。（2）扩充进程控制块扩充进程控制块 user结构结构：存放进程的管理和控制信息，这：存放进程的管理和控制信息，这些信息只有当进程处于运行状态时，系统才访问，不一定常驻内些信息只有当进程处于运行状态时，系统才访问，不一定常驻内存。存。 如：进程调度、用户管理、进程图像管理、文件系统、缓冲区等如：进程调度、用户管理、进程图像管理、文件系统、缓冲区等信息。信息。 2.正文段（共享正文段）正文段（共享正文段） 可为多个进程共享的程序称

19、为进程的正文段。作为正文段的程序必可为多个进程共享的程序称为进程的正文段。作为正文段的程序必须是可重入的。如：编译程序等。须是可重入的。如：编译程序等。 利用利用text表管理正文段，表管理正文段， text表目的内容：正文段在内存和磁盘表目的内容：正文段在内存和磁盘上的位置、大小和调度该段的进程数等。上的位置、大小和调度该段的进程数等。 3.数据段数据段 包括：用户栈、用户数据区、核心栈和包括：用户栈、用户数据区、核心栈和user结构。结构。4. UNIX4. UNIX系统进程数据结系统进程数据结构构(1)proc结构结构,在在UNIX系系统的统的/sys/proc.h文件文件中；中；(2)

20、user结构结构 ,在在UNIX系系统的统的/sys/user.h文件中；文件中；(3)text结构结构（用来管理（用来管理正文段的数据结构）正文段的数据结构） text结构在结构在UNIX系统系统的的/sys/text.h文件中文件中进程图像：可在内外存调进进程图像：可在内外存调进调出。调出。二、二、UNIX进程状态及变迁进程状态及变迁 1. UNIX进程状态进程状态 （1）两种运行状态：核心态：指进程正在执行）两种运行状态：核心态：指进程正在执行UNIX核心程序；核心程序； 用户态：指进程正在执行用户程序；用户态：指进程正在执行用户程序； （2）就绪状态：分为内存就绪状态和外存就绪状态。）

21、就绪状态：分为内存就绪状态和外存就绪状态。 内存就绪状态：处于就绪状态的进程，进程图像在内存。一旦内存就绪状态：处于就绪状态的进程，进程图像在内存。一旦 调度，便可运行。调度，便可运行。 外存就绪状态：处于就绪状态的进程，进程图像在外存。必须外存就绪状态：处于就绪状态的进程，进程图像在外存。必须 先由先由“对换进程对换进程”（0号进程），把它调入内存，号进程），把它调入内存， 然后调度才能执行。然后调度才能执行。 （3）睡眠状态（阻塞或等待）睡眠状态（阻塞或等待） （4）创建状态：父进程调用）创建状态：父进程调用fork( )创建子进程。创建子进程。 （5）僵死状态：子进程等待父进程进行善后处

22、理的状态。）僵死状态：子进程等待父进程进行善后处理的状态。用户态运行核心态运行中断自陷及返回中断自陷中断自陷中断自陷 及返回内存睡眠外存睡眠换出内存就绪外存就绪换进换出被抢占sleepwakeupwakeupswith创建有内存无内存fork僵死exit2.UNIX系统的进程状态变迁图系统的进程状态变迁图 UNIX进程树进程树0进程进程：系统初启时由系统初启程序建立，完成系统初启的相应工作后，创系统初启时由系统初启程序建立，完成系统初启的相应工作后，创建建1进程；然后的工作有两项，其一是进程交换（进程图象的管理）；其二进程；然后的工作有两项，其一是进程交换（进程图象的管理）；其二是进程切换（进

23、程调度）。是进程切换（进程调度）。1 1 进程：进程：为系统的每个联机终端创建一个终端进程，然后就做托管工作。为系统的每个联机终端创建一个终端进程，然后就做托管工作。2 2、3 3、n n、n+1n+1进程：终端进程进程：终端进程，执行程序是，执行程序是shellshell，该进程执行是接受，该进程执行是接受和执行用户键入的和执行用户键入的shellshell命令，或命令，或shellshell命令程序。命令程序。用户创建的进程：用户创建的进程：用户的用户的shell命令或命令或shell程序所创建的进程；用户在其程程序所创建的进程；用户在其程序中创建的进程。序中创建的进程。三、三、UNIXU

24、NIX系统的进程控制系统的进程控制 1. 1.进程的创建与终止进程的创建与终止 （1 1）进程的创建）进程的创建v在在UNIX环境中，除环境中，除0号进程外，所有进程都是调用号进程外，所有进程都是调用fork()创建创建的。调用的。调用fork的进程是父进程，而新创建的进程是子进程。的进程是父进程，而新创建的进程是子进程。v调用调用fork的三种情况的三种情况: a.在在shell键人一个键人一个shell命令，在命令，在shell中会调用中会调用fork为键入的命为键入的命令创建一个进程；令创建一个进程； b.在用户程序中调用在用户程序中调用fork系统调用创建一个进程；系统调用创建一个进程

25、； c.执行执行shell程序（在程序（在linux称为脚本）时，在称为脚本）时，在shell中会调用中会调用fork创建进程。创建进程。 （2 2）进程终止与等待）进程终止与等待 进程终止进程终止exit UNIX系统中当一个进程完成了它的使命后，将调用系统调用系统中当一个进程完成了它的使命后，将调用系统调用exit来终止运行。每个终止的进程转换成僵死状态，释放它占用来终止运行。每个终止的进程转换成僵死状态，释放它占用的资源，撤消进程图象，但保留进程的的资源，撤消进程图象，但保留进程的proc结构。结构。 进程等待进程等待wait：父进程利用：父进程利用wait命令，等待子进程终止。命令，等

26、待子进程终止。 2.2.进程睡眠与唤醒进程睡眠与唤醒 运行状态运行状态-睡眠状态睡眠状态-就绪状态。就绪状态。 3.执行用户程序执行用户程序execlexecl 系统调用系统调用execlexecl功能：运行一个可执行程序（功能：运行一个可执行程序（.exe.exe程序）程序）阻塞操作sleep唤醒操作唤醒操作wakeup main() int status; if(fork() = 0) execl(“/bin/date”,“date”,0); wait(&status); v这个程序创建一个子进这个程序创建一个子进程，当父进程从程，当父进程从fork中中返回时（即返回值是子返回时（

27、即返回值是子进程标识号一个大进程标识号一个大于于0的正整型数），执行的正整型数），执行系统调用系统调用wait，等待子，等待子进程的终止。当子进程进程的终止。当子进程从从fork中返回时（返回中返回时（返回值为值为0），执行语句），执行语句 execl(“/bin/date”,“date”,0)。 3.进程通信进程通信 解决的问题：利用同步机构或通信机构实现对多个进程正确地解决的问题：利用同步机构或通信机构实现对多个进程正确地 共享资源。共享资源。 常用的同步机构或通信机构：常用的同步机构或通信机构： 锁、信号量、消息缓冲区通信、信箱通信等。锁、信号量、消息缓冲区通信、信箱通信等。 进程间的两

28、类制约关系：进程间的两类制约关系： 直接直接制约关系（同步关系）：为共同完成一个任务，各进程制约关系（同步关系）：为共同完成一个任务，各进程 之间的相互合作关系。模式：之间的相互合作关系。模式：“进程进程进程进程”的通信。的通信。 间接间接制约关系（互斥关系）：由各进程对资源共享引起的制约关系（互斥关系）：由各进程对资源共享引起的 制约关系。模式：制约关系。模式：“进程进程资源资源-进程进程”的通信。的通信。 一、进程的一、进程的互斥互斥 1.1.临界资源和临界区临界资源和临界区 （1）临界资源）临界资源 一次仅允许一个进程使用的资源称为临界资源。一次仅允许一个进程使用的资源称为临界资源。 如

29、：如：电话、键盘、磁带、鼠标；内存变量、指针、数组等。电话、键盘、磁带、鼠标；内存变量、指针、数组等。（2）临界区）临界区 每个进程中访问临界资源的那段程序段称为临每个进程中访问临界资源的那段程序段称为临 界区（临界段）。界区（临界段）。例：例：process A process B a a：=0=0； printprint（a a）；）； a a：=a+1=a+1； a a：=a+2=a+2； 临界区临界区临界区临界区a 2.互斥互斥 定义定义: 在操作系统中，当某一进程正在访问某临界区时，就不允许其它在操作系统中，当某一进程正在访问某临界区时，就不允许其它进程进入，否则就会发生进程进入，否

30、则就会发生(后果后果)无法估计的错误。我们把进程之无法估计的错误。我们把进程之间的这种相互制约的关系称为互斥。间的这种相互制约的关系称为互斥。 例例1：进程：进程A、B共享一台打印机，则当一进程占用打印机后，另一共享一台打印机，则当一进程占用打印机后，另一进程若也要使用打印机，则必须等待，直至它释放打印机。进程若也要使用打印机，则必须等待，直至它释放打印机。例例2：有甲、乙两个售票点，同时销售同一航班的机票。用：有甲、乙两个售票点，同时销售同一航班的机票。用A和和B表表示甲、乙两个售票点的售票进程。则：示甲、乙两个售票点的售票进程。则： process A process B process

31、A process B X: interer X: interer； X: intererX: interer； begin beginbegin begin x x：=x+1=x+1； x x：=x+1=x+1； printprint（x x）；）； printprint（x x）；）； endend； endend ； 若：若：A、B顺序执行，顺序执行，且设且设x的初值为的初值为15：A执行后，输出执行后，输出16号号机票；机票；B后执行，输后执行，输出出17号机票。结果正号机票。结果正确。确。 问题：问题：A、B有可能并发执行，并发程序：有可能并发执行，并发程序： begin X: in

32、terer； cobegin process A begin x：=x+1； print（x）；）； end； process B begin x：=x+1； print（x）；）； end； coend ； end；A、B并发执行：且设并发执行：且设x的初值为的初值为15； A、B可可能同时执行到：能同时执行到： x：=x+1；则，会同时；则，会同时出售两张出售两张16号机票给两号机票给两个乘客。造成错误。称个乘客。造成错误。称这种错误为这种错误为“与时间有与时间有关的错误关的错误”。v进入临界区的准则：进入临界区的准则： (1) (1) 每次至多有一个进程处于临界区；每次至多有一个进程处于

33、临界区； (2)(2)当有若干个进程欲进入临界区时，应在有限的时间内使其进入；当有若干个进程欲进入临界区时，应在有限的时间内使其进入； (3)(3)进程在临界区内仅逗留有限的时间。进程在临界区内仅逗留有限的时间。 二、信号量及二、信号量及P P、V V操作操作 1 1、信号量、信号量v信号量的定义：信号量的定义： 信号量是一个确定的二元组（信号量是一个确定的二元组（s,q），）， s 是一个具有是一个具有非负初值非负初值的整型变量，的整型变量， q 是一个初始状态为空的队列指针。是一个初始状态为空的队列指针。 S代表资源的实体。在实际应用中应准确地说明代表资源的实体。在实际应用中应准确地说明s

34、的意义和初值，的意义和初值，每个信号量都有一个等待队列，其初始状态为空。每个信号量都有一个等待队列，其初始状态为空。 2、P、V操作操作v信号量的值仅能由信号量的值仅能由P、V操作来改变，操作来改变， 对信号量的对信号量的P P操作记为：操作记为：P(S)P(S)；对信号量；对信号量 的的V V操作记为：操作记为：V(S) V(S) P(S) P(S)和和V(S)V(S)是操作系统程序。是操作系统程序。vP操作：操作： （1）s值减值减1； （2）若相减结果大于等于）若相减结果大于等于0，则，则 进程继续执行；进程继续执行； （3）若结果小于）若结果小于0，则该进程挂在信号量等待队列中。，则该

35、进程挂在信号量等待队列中。入信号量等待队列置等待状态转进程调度0开始返回00vV操作：操作：（1）s值加值加1；（2）若相加结果大于）若相加结果大于0，进程，进程继续执行；继续执行；（3）否则，唤醒一个或多个）否则，唤醒一个或多个等待该信号灯的进程，然后等待该信号灯的进程，然后本进程继续执行。本进程继续执行。 注：注：P操作意味着请求系统操作意味着请求系统 分配一个资源；分配一个资源； V操作意味操作意味着释放一个资源。着释放一个资源。唤醒等待队列的首元素0开始返回00 三、利用信号量实现进程互斥三、利用信号量实现进程互斥 例：用二个进程共用打印机来说明例：用二个进程共用打印机来说明P、V操作

36、的意义。系统有一台操作的意义。系统有一台打印机，供二个进程打印机，供二个进程A、B自行使用。自行使用。 解：设置信号量解：设置信号量s，表示一台打印机可供使用。初值为，表示一台打印机可供使用。初值为1. begin s：semaphore； process B； s：=1； begin cobegin L2： 准备数据；准备数据； process A； P(S) ; begin 使用打印机打印数据；使用打印机打印数据； L1： 准备数据；准备数据； V(S)； P(S) ; goto L2； 使用打印机打印数据；使用打印机打印数据； end； V(S)； coend； goto L1； end

37、. end； 注意注意 （1）搞清楚搞清楚P P、V V操作控制的含义：操作控制的含义： 当当s=1s=1，表示有一个资源可供使用；无进程进入临界区。，表示有一个资源可供使用；无进程进入临界区。 当当s=0s=0，表示有一个进程进入临界区使用资源；，表示有一个进程进入临界区使用资源； 当当s=-1s=-1，表示有一个进程进入临界区使用资源；另一进程，表示有一个进程进入临界区使用资源；另一进程在等待。在等待。 若有若有3 3个进程要共享一个临界区资源，则，信号量个进程要共享一个临界区资源，则，信号量s s的可能取值：的可能取值： 1 1，0 0，-1-1，-2-2；-2-2表示一个进程进入临界区

38、，另两个进程在表示一个进程进入临界区，另两个进程在 等待。等待。 （2 2）注意要把）注意要把P P、V V操作放到正确的位置上：操作放到正确的位置上： 不要把不是临界资源放到不要把不是临界资源放到P P、V V控制中。控制中。 如：上例：如：上例：L1:P(S)L1:P(S)； 准备数据；准备数据； 降低了并行程度。降低了并行程度。 使用打印机打印数据；使用打印机打印数据； 又如上例：又如上例： goto goto L1 L1； V(S)V(S)；使系统处于停顿和瘫痪状态。；使系统处于停顿和瘫痪状态。 例：例：有甲、乙两个售票点，同时销售同一航班的机票。用有甲、乙两个售票点，同时销售同一航班

39、的机票。用A和和B表示甲、乙两个售票点的售票进程。则用表示甲、乙两个售票点的售票进程。则用P、V操作实现控制。操作实现控制。 解：与上例完全类似：解：与上例完全类似： 设置信号量设置信号量s，表示每次是否可卖一张票。初值为，表示每次是否可卖一张票。初值为1 begin s：semaphore； X: interer； X:=0；S:=1; cobegin process A； begin P(S); x:=x+1； print（x）；）； V(S); end； process B； begin P(S); x:=x+1； print（x）；）； V(S); end； coend ； end；例

40、：设一个飞机售票系统有例：设一个飞机售票系统有n个售票点，每个售票点通过终端访问个售票点，每个售票点通过终端访问 系统的公共数据区；假定该区中有系统的公共数据区；假定该区中有Ak（k=1，2，.n）单元）单元存存 放某天的各航班的余票；设放某天的各航班的余票；设P1，P2，.，Pn为各终端售票进为各终端售票进程；程；R1、R2、.、Rn各进程的工作单元。各进程的工作单元。P、V操作实现如下：操作实现如下：begin begin s：semaphore； Ri:=Ri-1; s：=1； Ak:=Ri;cobegin V(s); process Pi(i=1,2,n) 输出一张票； begin e

41、nd； 按旅客要求找到Ak； else begin P(S); V(S); Ri：=Ak； 输出“已售完”； if Ri=1 then end； end； coend； end.例：例：读写者读写者互斥问题：假定有多个读、写者进程共享文件互斥问题：假定有多个读、写者进程共享文件F。规定规定 ：多个读进程可同时读文件：多个读进程可同时读文件F；只要有一个写进程在写文件；只要有一个写进程在写文件F，其他的写进程或读进程都不能对文件其他的写进程或读进程都不能对文件F写或读。试用写或读。试用P、V操作实操作实现之。现之。 解：设置信号量解：设置信号量s：表示：表示F是否可共读写，初值为是否可共读写，初

42、值为1.Program RW； var s：semaphore；rc：integer； begin s：=1；rc：=0； cobegin process readeri（i=1，2，n） begin process writerj（j=1，2，m） rc：=rc+1； begin if rc=1 then P(s); P(s); 读文件读文件F； 写文件写文件F； rc：=rc-1； V(S)； if rc=0 then V(S)； end； end； coend；end； 程序的读者进程互斥控制存在问题：程序的读者进程互斥控制存在问题： rc是读者计数器，有可能是读者计数器，有可能rc1,

43、此时，不能执行此时，不能执行P(s).。这时，写。这时，写者进程有可能通过会写文件者进程有可能通过会写文件F。解决方法：再设置信号量。解决方法：再设置信号量s1用以用以 对对rc互斥使用的控制。正确程序：互斥使用的控制。正确程序：Program RW； V(S1); var s1，s：semaphore；rc：integer； end； begin process writerj（j=1，2，m） s：=1；s1：=1；rc：=0； begin cobegin P(S); process readeri（i=1，2，n） 写文件写文件F； begin V(S)； P(S1) ; end； rc

44、：=rc+1； coend； if rc=1 then P(s); end； V(s1); 读文件读文件F； P(S1); rc：=rc-1； if rc=0 then V(S)；四、利用四、利用P、V操作实现进程的同步操作实现进程的同步 1、同步的概念、同步的概念定义：为了完成一个共同的任务，并发进程之间在一些关键点上，需要互相等待和互通信息。这样的过程称为进程同步。同步的例子：病员就诊：诊病进程和化验进程的同步。看病化验 有无化验单 诊病 开化验单 化验有无化验结果 产生化验结果 诊断开处方 等化验单等化验结果问有无化验单 2、用、用P、V操作来实现进程同步操作来实现进程同步例： 病员就诊

45、 设置两个信号量： s1：表示有无化验结果 s1 = 0 s2：表示有无化验单 s2 = 0s2 ：0+1=1看病化验 p(s2) 诊病 v(s2) 化验 p(s1) v(s1) 开处方 开化验单s2 ：1-1=0s1 ：0-1= -1s1 ：-1+1=0得到化验单产生化验结果等化验结果 p(s2) 诊病 v(s2) 化验 p(s1) v(s1) 开处方 p(s2) 诊病 v(s2) 化验 p(s1) v(s1) 开处方 p(s2) 诊病 v(s2) 化验 p(s1) v(s1) 开处方 p(s2) 诊病 v(s2) 化验 p(s1) v(s1) 开处方 p(s2) 诊病 v(s2) 化验 p

46、(s1) v(s1) 开处方 进程的同步与互斥的区别：进程的同步与互斥的区别： 进程互斥：多个进程为竞争临界资源引起的相互制约的关系。进程互斥：多个进程为竞争临界资源引起的相互制约的关系。 进程同步：各进程为了共同完成一个任务，彼此之间的协作进程同步：各进程为了共同完成一个任务，彼此之间的协作 关系。关系。 两种类型的同步问题：两种类型的同步问题： 保证共享缓冲区（或共享数据）的合作进程的同步。保证共享缓冲区（或共享数据）的合作进程的同步。 保证一组合作进程按逻辑需要所确定的执行次序。保证一组合作进程按逻辑需要所确定的执行次序。 用用PVPV操作解决同步问题的步骤：操作解决同步问题的步骤： a

47、 a、写出同步关系描述；、写出同步关系描述； b b、设置信号量，并给出信号量的含义和初值；、设置信号量，并给出信号量的含义和初值； c c、写出算法描述及算法程序。、写出算法描述及算法程序。 （1 1）共享缓冲区（或共享数据）的合作进程的同步共享缓冲区（或共享数据）的合作进程的同步 例例1：有两个进程：有两个进程：cpcp计算进程和计算进程和IOPIOP打印进程共用一个单缓冲打印进程共用一个单缓冲 区，完成一个计算打印任务。试用区，完成一个计算打印任务。试用P P、V V操作实现之。操作实现之。 解：解：a、同步关系描述、同步关系描述 要保证打印结果的正确，要保证打印结果的正确，CP、IOP

48、必须同步：必须同步： 当当CP把结果送入把结果送入buffer后，后，IOP才能从才能从buffer中取，否则中取，否则IOP必必须等待；须等待； 当当IOP从从buffer中取走数据后，中取走数据后，CP才能将新产生数据送才能将新产生数据送 buffer，否则也必须等待。，否则也必须等待。 b、设置信号量、设置信号量 设置两个信号量：设置两个信号量：sc和和si： sc：表示：表示buffer中是否有空位置存放打印信息，初值为中是否有空位置存放打印信息，初值为1； si：表示：表示buffer中是否有可供打印的信息，初值为中是否有可供打印的信息，初值为0； c、算法描述、算法描述 cp：生产

49、一个数据：生产一个数据 ； IOP： P(si)； P(sc)； 从从beffer中取一数据；中取一数据； 送缓冲区送缓冲区beffer中；中； V(sc)； V(si)； 打印数据；打印数据；Program IP; var sc，si：semaphore；buf：integer； begin sc：=1；si：=0； end； cobegin process IOP； process cp； begin begin L2: P(si)； L1:produce a data； take from buf； P(sc)； V(sc)； buf：=data； output； V(si)； goto

50、 L2； goto L1; end； coend； end. 注意：注意： 同步信号量同步信号量scsc、sisi彼此放到对方彼此放到对方P P、V V操作中，起到了传递操作中，起到了传递控制信号的作用。控制信号的作用。 视视cpcp进程为生产者；进程为生产者；IOPIOP进程为消费者。则，此问题是：进程为消费者。则，此问题是： 一个生产者和一个消费者共享单缓冲区的问题。一个生产者和一个消费者共享单缓冲区的问题。 例例2 2：一个生产者和一个消费者共享存放：一个生产者和一个消费者共享存放n n个产品的缓冲区的问题。个产品的缓冲区的问题。同步算法：同步算法： program qqprogram

51、qq; ; var var s1,s2:semaphore; s1,s2:semaphore; b:array0.n-1 of integer; b:array0.n-1 of integer; k,t:integer k,t:integer; ; begin begin s1:=n; s2:=0; k:=0; t:=0; s1:=n; s2:=0; k:=0; t:=0; cobegin cobegin process A； process B； begin begin while 未完成未完成 do while 未完成未完成 do begin begin 生产一个产品；生产一个产品； P(

52、S2); P(S1); 从从bt中取一个产品；中取一个产品； bk:=一个产品；一个产品； t:=(t+1) mod n; k:=(k+1) mod n; V(S1); V(S2); 消费一个产品；消费一个产品； end; end； end; end； coend； end.例例3：三个进程：三个进程R、W1、W2共享一个单缓冲区共享一个单缓冲区B：B奇数偶数RW1W2解：解：a、同步关系描述、同步关系描述 R：生产一个数据，若：生产一个数据，若B有空位送有空位送B中，否则，中，否则，R必须等待；必须等待； W1：若：若B中是一个奇数，则取出打印，否则必须等待；中是一个奇数，则取出打印，否则必

53、须等待； W2：若：若B中是一个偶数，则取出打印，否则必须等待；中是一个偶数，则取出打印，否则必须等待； b、设置信号量：、设置信号量： s1：表示：表示B中是否有空位置，初值为中是否有空位置，初值为1； s2：表示：表示B中是否存放有奇数可供中是否存放有奇数可供W1提取，初值为提取，初值为0； s3：表示：表示B中是否存放有偶数可供中是否存放有偶数可供W2提取，初值为提取，初值为0； c、同步算法：、同步算法： program WW; var s1,s2,s3:semaphore; B:integer; begin process W1; process W2; s1:=1;s2:=0;s3

54、:=0; y:integer; z:integer; cobegin begin begin process R; while 未完成 do while 未完成 do x:integer; begin begin begin P(S2); P(S3) ; while 未完成 do y:=B; z:=B; begin V(S1); V(S1); 从读入设备读入一个数； 打印y中的数； 打印z中的数; x:=读入的数； end end P(S1); end； end； B：=x； coend if B=奇数 then V(S2) end. else V(S3); end end;例例4：有三个进程

55、：有三个进程get,copy,put,共享两个单缓冲区共享两个单缓冲区s和和t，完成誊写，完成誊写 任务。如图：任务。如图：FHgetcopyputst 试用试用P、V操作，写出协调操作，写出协调get，copy，put的同步算法。的同步算法。 解：解：a、同步关系描述、同步关系描述 get：只有：只有s中有空位置时，才能送数据到中有空位置时，才能送数据到s中，否则，中，否则，get 必须等待；当必须等待；当get送数据到送数据到s中后，才能通知中后，才能通知copy复制。复制。 copy：只有：只有s中有数据时，且中有数据时，且t中有空位置，才能复制，否则中有空位置，才能复制，否则 等待。当

56、等待。当copy复制数据后，它同时通知复制数据后，它同时通知get可向可向s中中 放数据，放数据，put从从t中取数据。中取数据。 put：只有：只有t中有数据时，中有数据时，put才能取数据送才能取数据送H，否则必须等待，否则必须等待 。当。当put从从t中取数据后，才能通知中取数据后，才能通知copy复制。复制。 b、设置信号量、设置信号量 s1：表示：表示s中有无空位置供中有无空位置供get存放数据，初值为存放数据，初值为1。 s2：表示：表示s中有无数据供中有无数据供copy复制，初值为复制，初值为0.。 s3：表示：表示t中有无空位置，供中有无空位置，供copy存放数据，初值为存放数

57、据，初值为1。 s4：表示：表示t中有无数据供中有无数据供put取出，初值为取出，初值为0。 c、同步算法、同步算法 get： copy： put： 产生一个数据；产生一个数据； P(S2); P(S4); P(S1); P(S3); 从从t中取数据；中取数据； 数据送数据送s中；中； 从从s取数据送取数据送t中；中； V(S3); V(S2); V(S1); 输出数据；输出数据； V(S4); program M var s1,s2,s3,s4:semaphore; begin s1:=1;s2:=0;s3:=1;s4:=0; cobegin process get; process cop

58、y; process put; begin begin begin while 未完成未完成 do while 未完成未完成 do while 未完成未完成 do begin begin begin 生产一个数据；生产一个数据； P(S2); P(S4); P(S1); P(S3); 从从t中取数据；中取数据； 将数据送入将数据送入s中；中； 从从s中取数据送中取数据送t中；中； V(S3); V(S2); V(S1); 输出数据；输出数据； end V(S4); end end； end end； end； coend end. 同步与互斥的混合问题：同步与互斥的混合问题： 例例5 5：生产

59、者与消费者问题：有：生产者与消费者问题：有m m个生产者和个生产者和k k个消费者，共享容量个消费者，共享容量 为为n n个的有界缓冲区如图，试用个的有界缓冲区如图，试用P P、V V操作实现同步。操作实现同步。C1C2C3CkP1P2P3Pm1 . n有界缓冲区生产者消费者解：解：a、同步关系描述：禁止生产者向满缓冲区存放信息；、同步关系描述：禁止生产者向满缓冲区存放信息； 禁止消费者从空缓冲区提取信息。禁止消费者从空缓冲区提取信息。 互斥关系描述：当多个生产者向缓冲区单元存放信息互斥关系描述：当多个生产者向缓冲区单元存放信息 时，必须互斥，以避免造成信息的丢失。时，必须互斥，以避免造成信息

60、的丢失。 当多个消费者从缓冲区单元提取信息时，也必须互斥。当多个消费者从缓冲区单元提取信息时，也必须互斥。 避免重复提取信息。避免重复提取信息。 b、信号量设置、信号量设置同步信号量同步信号量s1：表示缓冲区中是否有空位置存放信息，初值为：表示缓冲区中是否有空位置存放信息，初值为n。 s2：表示缓冲区中是否有信息可供提取。初值为：表示缓冲区中是否有信息可供提取。初值为0。 互斥信号量：互斥信号量：mutex，mutex1：分别表示：分别表示m个生产者或个生产者或k个消费者个消费者互斥进入缓冲区。初值均为互斥进入缓冲区。初值均为1。 c、算法描述、算法描述 producer i ： consumer