计算机操作系统第2章进程管理教学课件PPT.ppt

第二章 进程管理进程管理 进程管理 v 概述 v 进程的描述 v 进程控制 v 线程 进程互斥和同步 进程间通信 死锁问题 进程其他方面的举例 为了描述程序在并发执行时对系统资源的共享，需要 一个描述程序执行时动态特征的概念，这就是进程。 本章将讨论进程概念、进程控制和进程间关系。 进程管理 本章要点 v基础：进程描述及控制 v实现：互斥与同步 v解决：几个经典问题 v关于：进程通信 重点 难点 进程管理 2.1进程的基本概念 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 前趋图：是一个有向无循环图。 前趋图用于描述进程之间执行的前后关系 。 图中的每个结点可用于描述一个程序段或进程，乃至一条语句； 结点间的有向边则用于表示两个结点之间存在的偏序或前趋关系“”。 节点 概述： 进程管理 图21(a) 中存在着这样的前趋关系： p1p2, p1p3, p1p4, p2p5, p3p5, p4p6, p4p7, p5p8, p6p8, p7p9, p8p9 图 2-1 前趋图 进程管理 或表示为： p=p1, p2, p3, p4, p5, p6, p7, p8, p9 = (p1, p2), (p1, p3), (p1, p4), (p2, p5), (p3, p5), (p4, p6), (p4, p7), (p5, p8), (p6, p8), (p7, p9), (p8, p9) 应当注意，前趋图中必须不存在 循环，但在左图中却有着下述的 前趋关系： s2s3, s3s2 进程管理 程序并发执行的目的： 提高计算机的处理能力 提高资源利用率 分为两种形式： 多道程序环境下的多道程序的并发执行 在某道程序的几个程序段中，包含可同 时执行或可颠倒顺序执行的代码。 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 计算：顺序执行和并发执行下各设备的使用效率？ 进程管理 进程管理 顺序执行: 并发执行： 程序具有封闭性 程序失去封闭性 独享资源 共享资源(互为存在条件) 可再现性 程序与“计算”不再一一对 应 有相互制约 进程管理 进程管理 进程管理 进程管理 进程的定义 进程的特征 动态性： 进程对应程序的执行 进程是动态产生：创建运行消亡 进程在其生命周期内，在三种基本状态之间转换 独立性：各进程的地址空间相互独立，除非采用进 程间通信手段; 并发性：指多个进程实体同存于内存中，且能在一段时 间内同时运行; 异步性：每个进程都以其相对独立的不可预知的速 度向前推进; 结构化：进程 = 代码段 + 数据段 + pcb; 进程管理 进程与程序的区别 进程是动态的，程序是静态的：炒菜菜谱 进程是暂时的，程序的永久的：进程是一个状态变 化的过程，程序可长久保存。 进程与程序的组成不同：进程的组成包括程序、数 据和进程控制块（即进程状态信息）。 进程与程序的对应关系：通过多次执行，一个程序 可对应多个进程；通过调用关系，一个进程可包括 多个程序。 进程具有并行特征，程序没有。 进程是竞争计算机资源的基本单位。 进程管理 进程的描述 进程 = 程序 + 数据 + 进程控制块pcb 有人把这三部分称为”进程映像”. 程序是进程的不可缺少的组成部分；如果一个程序段允许被共享，则 它应该是可重入的，或纯代码段 数据是进程处理的对象 进程控制块是进程的控制结构，包含了进程的描述信息、控制信息和 资源信息以及现场保护区，是进程的唯一标识，系统通过pcb管理和 控制进程。 v 通常的程序是不能并发执行的,为使程序能并发执行,应为之配置一进 程控制块,即pcb; v 所谓创建进程是指创建进程实体中的pcb，撤销亦如此。 进程管理 进程控制块pcb (process control block) 进程控制块是由os维护的用来记录进程相关信息 和管理进程而设置的一个专门的数据结构 包含了进程的描述信息、控制信息和资 源信息以及现场保护区 pcb是进程动态特性的集中反映 系统通过pcb感知进程的存在，通过 pcb中所包含的各项变量的变化，掌握进程的 状态以达到控制进程活动的目的 进程管理 pcb结构的全部或部分常驻内存； pcb随进程的创建而填写，随进程的撤消而 释放,有生命周期； 系统利用pcb来控制和管理进程，所以pcb 是系统感知进程存在的唯一标志 进程与pcb是一一对应的 进程管理 进程控制块的内容（数据结构很复杂） v 进程标识符： 内部进程标识符(process id)，唯一，通常是一个整数； 进程名(外部标识符)，通常基于可执行文件名（不唯一） ； 用户标识符(user id)；进程组关系(process group) v 进程控制信息： 程序和数据的地址； 进程同步和通信机制； 资源清单； 链接指针 v 进程调度信息：进程状态、进程优先级、资源信息等 v 处理机状态：寄存器值（通用、程序计数器pc、状态 psw，地址包括栈指针） 进程管理 pcb的组织方式 v链接方式：同一状态的进程其pcb成一链表，多个 状态对应多个不同的链表 各状态的进程形成不同的链表：就绪链表、阻塞链 表 进程管理 链接链接 pcb14 pcb23 pcb30 pcb4 pcb5 pcb6 pcb7 pcb8 pcb9 pcb10 8 7 9 0 11 执行指针 就绪队列指针 阻塞队列指针 空闲队列指针 进程管理 v 索引方式： 进程管理 pcb索引表： 执行指针 就绪表指针 等待表指针 空闲表指针 pcb1 pcb2 pcb3 pcb4 pcb5 pcb6 pcb7 pcb8 pcb9 就绪索引表 1 4 3 等待索引表 6 7 5 空闲索引表 8 9 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程的状态及其转换其它状态 创建状态：创建( 新new)状态 os 已完成为创建一进程所必要的工作 已构造了进程标识符 已创建了管理进程所需的表格 终止状态（exit） 终止后进程移入该状态 它不再有执行资格 表格和其它信息暂时保留 实用程序为了分析性能和利用率，可能要提取 程序的历史信息 挂起状态：把一个进程从内存转到外存 进程管理 挂起状态 这个问题的引入是由于进程优先级的引入，一些低优先级进程可能 等待较长时间，从而被对换至外存。目的是： 提高处理机效率：就绪进程表为空时，os将阻塞进程从 内存中“挂起”到磁盘的“挂起队列”，再从该队列选另一 进程进入内存，或接受一个新进程的请求。 为运行进程提供足够内存：资源紧张时，暂停某些进程 ，如：cpu繁忙（或实时任务执行），内存紧张 用于调试：在调试时，挂起被调试进程（从而对其地址 空间进行读写） 进程管理 状态间的转换 挂起（suspend）：把一个进程从内存转到外存 ；可能有以下几种情况： 阻塞到阻塞挂起：没有进程处于就绪状态 或就绪进程要求更多内存资源时，会进行这种转换， 以纳入新进程或运行就绪进程； 就绪到就绪挂起：当有高优先级阻塞（系 统认为会很快就绪的）进程和低优先级就绪进程时， 系统会选择挂起低优先级就绪进程； 运行到就绪挂起：对抢先式分时系统，当 有高优先级阻塞挂起进程因事件出现而进入就绪挂起 时，系统可能会把运行进程转到就绪挂起状态； 进程管理 状态间的转换 激活（activate）：把一个进程从外存转到内 存；可能有以下几种情况： 就绪挂起到就绪：没有就绪进程或挂起就 绪进程优先级高于就绪进程时，会进行这种转换； 阻塞挂起到阻塞：当一个进程释放足够内 存时，系统会把一个高优先级阻塞挂起（系统认为 会很快出现所等待的事件）进程转为阻塞状态；较 少出现。 进程管理 进程管理 unix v中的进程状态： 另 一 进 程 用户运行态 核心运行态被抢占状态僵死状态 内存中睡眠 睡眠且交换就绪且交换 内存中就绪 创建状态 fork exit 内存足够 内存不足 交换进 交换进 交换出 交换出 唤醒 唤醒 睡眠 被调度 中断返回 系统调用 返回 被抢占 返回用户态 o 就绪（/睡眠）且交换态：外存就绪（/睡眠）态。由于内存有限，将原 位于内存的程序和数据交换出去，使之位于外存。 o 被抢占态：在进程完成系统调用返回用户态之前，检查是否有优先级更 高的进程存在。若有，则当前进程被抢占。 进程管理 进程管理 v 这些控制和管理功能是由操作系统的原语来实现。 v 原语(primitive)是在管态下执行、完成系统特定功能的过程 。 v 原语和机器指令类似，其特点是执行过程中不允许被中断， 是一个不可分割的基本单位，原语的执行是顺序的而不可能是 并发的。 v 一种原语的实现方法是以系统调用方式提供原语接口，且采 用屏蔽中断的方式来实现原语功能，以保证原语操作不被打断 的特性。 进程管理 进程管理 进程管理 何时创建进程： 用户登录时： 作业调度时： 用户程序向os提出服务请求时：如创建打印进程 用户程序调用其他子程序时： 创建过程： create ( pstat, paddr, pid, prio, pname, ）原语 fork（） 分配空白pcb及内存，初始化pcb并插入就绪队列。 进程管理 进程管理 进程管理 输入：新进程的符号名，优先级、开始执行地址输入：新进程的符号名，优先级、开始执行地址 输出：新创建进程的内部标识符输出：新创建进程的内部标识符pidpid 在总链队列上查找有无同名的进程； if（有同名进程） return（ 错误码）； /*带错误码返回*/ 从pcb资源池中申请一个空闲的pcb结构； if（无空pcb结构） return（错误码）；/*带错误码返回*/ 用入口参数设置pcb内容； 置进程为“就绪”态； 将新进程的pcb插入就绪队列； 将新进程的pcb插入总链队列； return（新进程的pid）； 创建原语creat 进程管理 2、进程的终止： 何时终止进程： 正常结束：halt，return，exit()，logout。 异常结束：越界，访问权限错，特权指令错，非法指令错 ，运行/等待超时，算术运算错，i/o故障等 os干预（如死锁时），父进程请求终止某子进程，父进 程本身已终止时 终止过程： kill ( pid )、exit( ) 原语 找到其pcb，终止运行并重新调度，终止所有子进程，释放 资源，将pcb移入空队列。 进程管理 进程管理 进程管理 命令形式为： kill原语 无参数，无返回信息。 算法 kill 输入：无输入：无 输出：无输出：无 由运行指针得当前进程的pid； 释放本进程所占用的资源； 该进程从总链队列中摘除； 释放pcb结构； 转进程调度程序； 进程管理 3、进程的阻塞： o 何时阻塞： o 请求系统服务得不到满足时： o 启动i/o操作时： o 合作进程提供的数据尚未到达时： o 系统进程无新任务可处理时： o 阻塞过程： wait() 原语 保护现场停止执行，修改进程状态，将其pcb插入到阻塞队 列，调度另一进程。 4、进程的唤醒：当等待事件发生时唤醒。signal() 将其pcb改为就绪态，并从阻塞队列移入就绪队列。 进程管理 进程管理 进程管理 进程管理 进程管理 v 正在执行的进程由于其时间片完而被暂停执行，此时进程应 从运行态变为 a 状态；处于静止阻塞状态的进程，在进程等待 的事件出现后，应转变为 b 状态；若进程正处于运行态时，应 终端的请求而暂停下来以便研究其运行情况(执行挂起进程原语 )，这时进程应转变为 c 状态，若进程已处于阻塞状态，则此 时应转变为 d 状态，若进程已处于就绪状态，则此时应转变为 e 状态；执行解除挂起进程原语后，如挂起进程处于就绪状态 ，则应转变为 f 态，如处于阻塞状态，则应转变为 g 态；一 个进程刚被创建时，它的初始状态为 h 。 ah：(1)静止阻塞；(2)活动阻塞；(3)静止就绪； (4)活动就绪；(5)执行。 进程管理 进程同步与互斥 一、进程间的相互作用： q 无关进程：不影响其它进程，与其它进程的进展情况无关 。 q 相关进程：由于共享某些资源，所以一个进程的执行可能 会影响其它进程的执行结果。 q “与时间有关的错误”：对一次只允许一个进程使用的资 源（临界资源）的共享过程不加以控制时，会导致程序结果 与执行速度有关。（即结果不可再现） 例：程序a的n:=n+1和程序b的print(n)、n:=0交叉运行。 进程管理 v 进程的同步：直接制约 进程管理 进程管理 v 进程的互斥：由资源共享引起间接制约 进程管理 v 互斥： 不允许两个以上的进程同时使用临界资源或进入临界区。 v 互斥时的原则： 有空让进：当临界区空闲时，允许请求进程立即进入该临 界区。 无空等待：有进程正在临界区时，其它请求进程等待。 有限等待：请求进程应在有限的等待时间内进入临界区。 让权等待：当进程不能进入临界区时，应立即释放处理机 。 进程管理 2.3.2 信号量机制 基本原理： 两个或多个进程可以通过简单的信号进行合作，一个 进程可以被迫在某一位置停止，直到它接收到一个特定的 信号。任何复杂的合作需求都可以通过适当的信号结构得 到满足。为了发信号，需要使用一个称作信号量的特殊变 量。 为通过信号量s传送信号，进程可执行原语signal(s)； 为通过信号量s接收信号，进程可执行原语wait(s)；如果 相应的信号仍然没有发送，进程被阻塞，直到发生传送。 这两个操作被称为“p、v”操作。 进程管理 进程管理 公用信号量：通常用于实现进程间互斥，初值为1。 私有信号量：用于实现进间的同步,初值为0或正整数n。仅允 许拥有它的进程实施p操作。 信号量s大于等于零时表示可供并发进程使用的资源实体数， 但s小于零时表示正在等待使用临界区的进程数。 p原语的操作功能v原语的操作功能 进程管理 进程管理 进程管理 除初始化外，对s值的修改只能通过原子操作进行 ，而不能使用一般的赋值语句。 进程管理 进程管理 进程管理 vv 1 1 整型信号量整型信号量 信号量s是个特殊的整型变量，信号s的值描述了可用 资源的数量或等待该资源的进程个数 当s0时表示可用资源数； 当s0时其绝对值|s|表示等待该资源的进程数。 除初始化外，对s值的修改只能通过原子操作进行 ，而不能使用一般的赋值语句。 进程管理 s s是一个整型量，通过是一个整型量，通过2 2个原子操作个原子操作wait(swait(s) )和和signal(ssignal(s) )来来 访问。访问。 wait(swait(s): while s1s1，记录型信号量。，记录型信号量。 s=1s=1时，互斥型信号量。时，互斥型信号量。 vv （3 3）swait(s,1,0)swait(s,1,0)，可控开关，当时，允许进，可控开关，当时，允许进 入，入，s=0， s=0 表示可用资源个数 s20)个时，信号 量可能的变化范围。 进程管理 问题分析 判断该问题是互斥问题还是同步问题： 可以将该售票厅的每个窗口看作是一个临界资源为每个购票者 进程共享，每个购票者进程只能使用其中一个窗口。 售票厅有20个窗口，所以有20个同类的临界资源，一次可以允 许20个进程进入，并且先来者先进入。 由此可知：该问题满足互斥的2个必要条件（共享临界资源， 共享方式是先来者先进入），所以该问题是互斥问题。 根据互斥问题的解决方法设置信号量并赋初值： 设置一个信号量mutex，初值为20。 用信号量的p、v操作将临界区括起来。 进程管理 算法描述 主函数算法： main() int mutex=20; cobegin p1(); pi();pn(); coend 购票者i的算法： pi() p(mutex); 进入售票厅占有一个窗口 购票； v(mutex); 进程管理 v 该类问题是指多个合作进程在执行时有先后次序的要求 ，前后形成前驱后继关系，可以用前趋图描述。 v 在前驱与后继同步问题中，每个进程是否能够执行，取 决于它的所有前驱是否执行结束。每个前驱的结束都是它 得以执行的必要条件之一，因此，需要针对该进程的每个 前驱设置一个信号量，并在该进程开始处执行相应的p操作 。 v 同样，如果进程有后继，则当它结束时，需要执行其后 继所等待的信号量的v操作，释放其后继所等待的执行条件 。 2.利用信号量来描述前趋关系 进程管理 合作进程的执行次序： 例：pa、pb、pc为一组合作进程，其前驱 图如右： 要求pa执行结束后， pb、pc才能执行。 设两个信号量sb、sc分别表示进程pb、pc 能否开始执行，初值为sb=0、sc=0。 pa： pb： pc： p（sb） p（sc） v（sb） v（sc） 进程管理 共享单缓冲区的两个进程的同步问题： 例：设一计算进程ic和一打印进程op共用 一个单缓冲，如图所示。ic进程负责不断 地计算数据并输入缓冲区t中，op进程负 责从缓冲区t中取出数据去打印。 同步约束： op进程只有在ic进程将数据输入缓冲区后，才能取出打印。 ic进程只有在op进程将数据取出打印后，才能送入下一个计 算数据。 进程管理 sa=0；/ sa信号量表示缓冲区中有无信息（初始无数据） sb=1；/ sb信号量表示缓冲区中有无空位（初始有空位） 进程管理 对于前驱后继同步问题的算法可以按下列步骤进行： 分析每个进程j，看它有无前驱，如果有，则针对 每个前驱i设置一个信号量v，初值皆为0； 在每个进程j开始时，针对其每个前驱的信号量sij 执行p操作，有几个前驱执行几个p操作； 在每个进程i执行完毕后，针对其每个后继的信号 量sij执行v操作，有几个后继执行几个v操作。 其中：i表示前驱进程号，j表示后继进程号。 进程管理 此时，让他们共享一个公用信号量s， s初值一般为=0， s=0 表示可用资源个数 s=0。（s为可用资源个数） 实现：a进程已执行过程序段1，b进程才能执行程序段2。 设一信号量s，初值为0。 a进程 程序段1 l1：v(s); b进程 l2：p(s); 程序段2 进程管理 进程管理 进程管理 v若p、v操作的信号量初值为1，当前值为-3，则表 示有 个等待进程。 3个 进程管理 2.4 经典进程同步问题 vv2.4.12.4.1生产者消费者问题生产者消费者问题 vv2.4.22.4.2哲学家进餐问题哲学家进餐问题 vv2.4.32.4.3读者写者问题读者写者问题 进程管理 2.4.1 生产者消费者问题 生产者和消费者问题，是相互合作进程关系的一种 抽象，是一个广义的概念，可以代表一类具有相同 属性的进程。 生产者和消费者问题： 生产者和消费者进程共享一个固定大小的缓冲区， 其中，一个或多个生产者生产数据，并将数据存入缓 冲区，并有一个消费者从缓冲区中取数据。 进程管理 假设缓冲区的大小为n（存储单元的个数），它可以 被生产者和消费者循环使用。 分别设置两个指针in和out，in指向生产者将存放数 据的存储单元，而out指向消费者将取数据的存储单元 。 进程管理 1 2 3 4 5 6 7 8 9n outin 1 2 3 4 5 6 7 8 9n outin 进程管理 生产者和消费者必须互斥： 必须是生产者和消费者互斥进入缓冲区。即，某时 刻只允许一个实体（生产者或消费者）访问缓冲区， 生产者互斥消费者和其它任何生产者。 生产者和消费者必须同步： 生产者不能向满缓冲区写数据； 消费者也不能在空缓冲区取数据。 进程管理 生产一条数据 空单元？ 可用？ 存入一条数据 归还使用权 数据单元加1，唤醒一个消费者 阻塞 等待资源 被唤醒 阻塞 等待使用权 被唤醒 是 有 无 否 数据单元？ 可用？ 取一条数据 归还使用权 空单元加1，唤醒一个生产者 阻塞 等待资源 被唤醒 阻塞 等待使用权 被唤醒 是 有 无 否 消费数据 进程管理 一个互斥条件： v 缓冲区一次只能让一个进程访问， 设一互斥信号量mutex，初值为1。 两个同步条件： v 缓冲区中至少有一个单元为空时，生产者才 送数。 设一信号量empty，表示空缓冲区的数量，初值为n。 v 缓冲区中至少有一个单元为满时，消费者才 取数。 设一信号量full，表示满缓冲区的数量，初值为0。 进程管理 void main( ) int mutex=1, empty=n, full=0; int in=0，out=0； elemtype buffern; cobegin producer(); consumer(); coend full:装满产品的缓冲区数目，初值为0； empty：空缓冲区数目，初值为n； mutex：对缓冲区互斥使用的公用信号量，初值为1； 一、利用记录型信号量解决生产者一消费者问题 进程管理 void producer( ) while(true) 生产一个数据; wait(empty); /*申请空缓冲区 */ wait(mutex); /*实现对缓冲池的互斥使用*/ bufferin=生产的数据; in=（in+1）mod n; signal(mutex); signal(full); /* 满缓冲区的个数加1*/ 进程管理 void consumer( ) while(true) wait(full); /*申请满缓冲区*/ wait(mutex); /*实现互斥*/ 消费bufferout中的数据； out=（out+1）mod n； signal(mutex); signal(empty); /*空缓冲区的个数加1*/ 进程管理 二、利用and信号量解决生产者消费者问题 void producer( ) while(true) 生产一个数据; swait(empty,mutex); /*申请空缓冲区, 实现对缓冲池的互斥使用*/ bufferin=生产的数据; in=（in+1）mod n; ssignal(mutex，full); /* 满缓冲区的个数加1*/ 进程管理 void consumer( ) while(true) swait(full，mutex); /*申请满缓冲区， 实现互斥*/ 消费bufferout中的数据； out=（out+1）mod n； ssignal(mutex，empty); /*空缓冲区的个数加1*/ 进程管理 注意： 进程应该先申请资源信号量，再申请互斥信号量，顺序 不能颠倒。 对任何信号量的wait与signal操作必须配对。同一进程 中的多对wait与signal语句只能嵌套，不能交叉。 对同一信号量的wait与signal可以不在同一个进程中。 wait与signal语句不能颠倒顺序，wait语句一定先于 signal语句。 进程管理 2.4.2哲学家进餐问题 2 0 1 23 4 0 1 3 4 进程管理 vv 1.1.利用记录型信号量解决哲学家进餐问题利用记录型信号量解决哲学家进餐问题 放在桌子上的筷子是临界资源，在一段时间内只允许一 位哲学家使用。为了实现对筷子的互斥使用，可以用一 个信号量表示一只筷子，由这五个信号量构成信号量数 组。其描述如下： var chopstick: array0, , 4 of semaphore; 所有的信号量都要初始化为1 进程管理 1）原理：至多只允许四个哲学家同时进餐,以保证至 少有一个哲学家能够进餐,最终总会释放出他所使 用过的两支筷子,从而可使更多的哲学家进餐。 以下将room 作为信号量，只允许4 个哲学家同 时进入餐厅就餐，这样就能保证至少有一个哲学家 可以就餐，而申请进入餐厅的哲学家进入room 的 等待队列，根据fifo 的原则，总会进入到餐厅就 餐，因此不会出现饿死和死锁的现象。 进程管理 semaphore chopstick5=1，1，1，1，1; semaphore room=4; void philosopher(int i) while(true) think(); wait(room); /请求进入房间进餐 wait(chopsticki); /请求左手边的筷子 wait(chopstick(i+1)%5); /请求右手边的筷子 eat(); signal(chopstick(i+1)%5); /释放右手边的筷子 signal(chopsticki); /释放左手边的筷子 signal(room); /退出房间释放信号量room 进程管理 2）原理：仅当哲学家的左右两支筷子都可用时,才允许 他拿起筷子进餐。 方法1：利用and 型信号量机制实现：根据课程 讲述，在一个原语中，将一段代码同时需要的多个 临界资源，要么全部分配给它，要么一个都不分配 ，因此不会出现死锁的情形。当某些资源不够时阻 塞调用进程;由于等待队列的存在，使得对资源的请 求满足fifo 的要求，因此不会出现饥饿的情形。 进程管理 semaphore chopstick5=1，1，1，1，1; void philosopher(int i) while(true) think(); swait(chopstick(i+1)%5,chopsticki); eat(); ssignal(chopstick(i+1)%5,chopsticki); 进程管理 方法2：利用信号量的保护机制实现。通过信号量mutex对eat（）之前的 取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以 防止死锁的出现。 semaphore mutex = 1 ; semaphore chopstick5=1，1，1，1，1; void philosopher(int i) while(true) think(); wait(mutex); wait(chopstick(i+1)%5); wait(chopsticki); signal(mutex); eat(); signal(chopstick(i+1)%5); signal(chopsticki); 进程管理 3）原理：规定奇数号的哲学家先拿起他左边的筷子, 然后再去拿他右边的筷子;而偶数号的哲学家则相反. 按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学 家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获 得后,再去竞争偶数号筷子,最后总会有一个哲学家能 获得两支筷子而进餐。而申请不到的哲学家进入阻塞 等待队列，根fifo原则，则先申请的哲学家会较先可 以吃饭，因此不会出现饿死的哲学家。 2 1 2 34 5 5 1 3 4 进程管理 semaphore chopstick5=1，1，1，1，1; void philosopher(int i) while(true) think(); if(i%2 = 0) /偶数哲学家，先右后左。 wait (chopstick i + 1 mod 5) ; wait (chopstick i) ; eat(); signal (chopstick i + 1 mod 5) ; signal (chopstick i) ; 进程管理 else /奇数哲学家，先左后右。 wait (chopstick i) ; wait (chopstick i + 1 mod 5) ; eat(); signal (chopstick i) ; signal (chopstick i + 1 mod 5) ; 进程管理 2.4.3 读者写者问题 vv 读者读者/ /写者进程应满足的条件：写者进程应满足的条件： 允许多个读者进程可以同时读数据。允许多个读者进程可以同时读数据。 不允许多个写者进程同时写数据，即只能互不允许多个写者进程同时写数据，即只能互 斥写数据。斥写数据。 若有写者进程正在写数据，则不允许读者进若有写者进程正在写数据，则不允许读者进 程读数据。程读数据。 问题描述：问题描述： 为多个进程访问一个共享数据区，如数据库为多个进程访问一个共享数据区，如数据库 、文件、内存区以及一组寄存器等的数据问、文件、内存区以及一组寄存器等的数据问 题建立一个通用模型，其中若干读进程只能题建立一个通用模型，其中若干读进程只能 读数据，若干写进程只能写数据。读数据，若干写进程只能写数据。 进程管理 解决读者/写者问题，需设置两个信号量： （1）读互斥信号量rmutex,用于使读者互斥地访问共享 变量readcount,这里readcount是记录有多少读者正在 读; （2）写互斥信号量wmutex,用于实现读写互斥和写写互 斥地访问共享文件。 读者/写者问题进行如下描述： int rmutex,wmutex,readcount=0; rmutex=1;wmutex=1; 进程管理 void reader( ) while(true) wait(rmutex); if （readcount=0） wait(wmutex); readcount+; signal(rmutex); perform read operation; wait(rmutex); readcount= readcount-1; if （readcount=0） signal(wmutex); signal(rmutex); 一、利用记录型信号量解决读者写者问题 进程管理 void writer() while(true) wait(wmutex); perform write operation; signal(wmutex)； void main() readcount=0; parbegin(reader,writer); 进程管理 2.5 进程通信 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 进程管理 例：建立一pipe，子进程向pipe写，父进程从pipe读。 # include # include main() int x,fd2; char buf30,s30; pipe(fd); /*创建管道*/ while (x=fork()= -1); /*循环创建，直至成功*/ if (x=0) sprintf(buf,”this is a test.n”); /*写入buf数组*/ write(fd1,buf,30); /*把buf中字符写入管道*/ exit(0); /*正常结束*/ else /*从子进程返回，执行父进程*/ wait(0); /*阻塞父进程，直至子进程终止*/ read(fd0,s,30); /*从管道中读30b至s数组*/ printf(“%s”,s); 子进程 执行部分 父进程 执行部分 父进程 执行部分 进程管理 2.5.3 消息传递系统中的几个问题 vv 一、通信链路：一、通信链路： （ （1 1）显式建立：（进程完成）显式建立：（进程完成） （ （2 2）隐式建立：（系统完成）隐式建立：（系统完成） 链路类型：链路类型： （1 1）由连接方法分：点）由连接方法分：点点链路，多点链点链路，多点链 路。路。 （2 2）由通信方式分：单向、双向。）由通信方式分：单向、双向。 （3 3）由容量分：无容量（无缓冲区）、有）由容量分：无容量（无缓冲区）、有 （有缓冲区）。（有缓冲区）。 进程管理 2.5.3消息传递系统中的几个问题 vv 二、消息格式：二、消息格式： 消息头：含控制信息如：收消息头：含控制信息如：收/ /发进程名，消息长度、发进程名，消息长度、 类型、编号类型、编号 消息内容：消息内容： 定长消息：系统开销小，用户不便（特别是传长消定长消息：系统开销小，用户不便（特别是传长消 息用户）息用户） 变长消息：开销大，用户方便。变长消息：开销大，用户方便。 进程管理 2.5.3消息传递系统中的几个问题 vv 三、进程同步方式三、进程同步方式 .1 1.发送和接收进程阻塞（汇合）发送和接收进程阻塞（汇合） 用于紧密同步，无缓冲区时。用于紧密同步，无缓冲区时。 .2 2.发送进程不阻塞，接收进程阻塞（多个）发送进程不阻塞，接收进程阻塞（多个） 相当于接收进程（可能是多个）一直等相当于接收进程（可能是多个）一直等 待发送进程，如：打印进程等待打印任务。待发送进程，如：打印进程等待打印任务。 .3 3.发送发送/ /接收进程均不阻塞接收进程均不阻塞 一般在发、收进程间有多个缓冲区时。一般在发、收进程间有多个缓冲区时。 进程管理 2.5.4 消息缓冲队列通信机制 vv 一、数据结构一、数据结构 vv 1. 1.消息缓冲区消息缓冲区 type message buffer =recordtype message buffer =record sender:sender: size:size: text:text: next:next:指向下一指针指向下一指针 vv 2.pcb2.pcb中应增数据项：中应增数据项： type type pcbpcb=record=record mqmq 消息队列指针消息队列指针 mutex mutex 消息队列互斥