操作系统全册配套最完整精品课件1.ppt

1、操作系统全册配套最完整操作系统全册配套最完整 精品课件精品课件1 计算机操作系统计算机操作系统 引引 言言 课程特点：课程特点：概念多、原理性强、较抽象 课程学习目的：课程学习目的：基础核心课，有利于对计 算机系统的理解和软件开发 课程学习方法：课程学习方法：以问题驱动学习、理论联 系实际 课程学习难点：课程学习难点：概念、原理、算法、数据 结构 教材及参考书教材及参考书 教材：教材： 计算机操作系统，汤小丹等计算机操作系统，汤小丹等 西安电子科技大学出版社西安电子科技大学出版社 参考书：参考书： 计算机操作系统学习指导与题解，汤子瀛主审计算机操作系统学习指导与题解，汤子瀛主审 梁红兵等编梁红

2、兵等编 著，西安电子科技大学出版社著，西安电子科技大学出版社 操作系统教程与实验，胡明庆、高巍、钟梅，清华大学出操作系统教程与实验，胡明庆、高巍、钟梅，清华大学出 版社，版社，2007.01第第1版版 计算机操作系统，何炎祥、李飞、李宁，清华大学出版社，计算机操作系统，何炎祥、李飞、李宁，清华大学出版社， 2004年第年第1版版 Operating System Concepts，Seventh Edition. Silberschatz, Galvin, Gagne, John wiley S2 : b : = a - 5; S3 : c : = b + 1; I : 输入操作 C : 计算

3、操作 P : 打印操作 顺序性：顺序性：处理机的操作必须严格按照程序所规定 的顺序执行。 封闭性：封闭性：程序在执行时独占系统的全部资源，机 器资源状态的改变只与执行的程序有关，而与外 界环境无关。 可再现性：可再现性：只要初始条件相同，一个程序的多次 重复执行，将得到相同的结果。 2、程序顺序执行的特征 2.1.2 前趋图 前趋图是一个有向无循环图，用于描述程序段或进程之 间执行的先后次序关系。图中的结点用于描述一个程序段或 一个进程，结点间的有向边用于表示两个结点之间存在的偏 序或前趋关系“”。 =(Pi, Pj)|Pi must complete before Pj may start,

4、 如果(Pi, Pj),可写成PiPj，称Pi是Pj的直接前趋，而称Pj是Pi的直 接后继。在前趋图中，把没有前趋的结点称为初始结点，把 没有后继的结点称为终止结点。 每个结点还具有一个重量，用于表示该结点所含有的 程序量或结点的执行时间。 图 2-2 前趋图 P1 P2 P3 P4 P5 P7 P6 P8P9 (a)具有九个结点的前趋图 S1 S2 S3 (b)具有循环的图 图 2-3 并发执行时的前趋图 2.1.3 程序的并发执行及其特征 1、程序的并发执行 I1I2I3I4 C1C2C3C4 P1P2P3P4 例子： 对于具有下述四条语句的程序段 S1: a =x+2 S2: b =y+

5、4 S3: c =a+b S4: d =c+b 图 2-4 四条语句的前趋关系 S1 S2 S3S4 1、程序的并发执行 间断性：由于资源共享和相互合作，并发执行的程 序间形成了相互制约关系，导致程序的运行过程出 现“执行-暂停-执行”的现象。 失去封闭性：程序在执行时与其他并发执行的程序 共享系统的资源，因此，资源状态的改变还与其他 程序有关，即程序本身的执行环境要受到外界程序 的影响。 不可再现性：同样的初始条件，一个程序的多次重 复执行，可得到不同的结果。 2、程序并发执行时的特征 例如，有两个循环程序A和B，它们共享一个变量N。程 序A每执行一次时，都要做N =N+1操作；程序B每执行

6、一次 时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B 以不同的速度运行。 (1) N =N+1在Print(N)和N =0之前，此时得到的N值分 别为n+1, n+1, 0。 (2) N =N+1在Print(N)和N =0之后，此时得到的N值分 别为n, 0, 1。 (3) N =N+1在Print(N)和N =0之间，此时得到的N值分 别为n, n+1, 0。 2、程序并发执行时的特征 2.1.4 进程的特征与状态 1、进程的特征和定义 进程=？程序 一个进程比一个程序的内容要多 程序只是进程状态的一部分内容 引入进程的目的：引入进程的目的：为了使程序能够正确地并发执行

7、。 进程的特征：进程的特征： 结构特征：结构特征：进程实体 = 程序段 + 数据段 + PCB 动态性：动态性： 进程的实质是进程实体的一次执行过程 进程具有一定的生命周期：由创建而产生，由调度而 执行，由撤消而消亡。 并发性：并发性：多个进程实体同存于内存中，且能在一段时间内 同时运行。 独立性：独立性：进程实体是一个能独立运行、独立分配资源和独 立接受调度的基本单位。 异步性：异步性：进程可按各自独立的、不可预知的速度向前推进。 1、进程的特征和定义 进程与程序的区别：进程与程序的区别： 程序程序是进程的静态文本，进程进程是执行程序的动 态过程； 一个进程一个进程可以执行一个或多个程序一个

8、或多个程序，几个进程几个进程 可以同时执行一个程序一个程序； 程序程序可作为软件资源长期保存，进程进程只是一次 执行过程，是暂时的； 进程进程是系统分配调度的独立单位，能与其他进 程并发执行。 定义：定义：进程是一个可并发执行的程序，在一个数 据集合上的一次运行过程。它是系统进行资源分 配和调度的一个独立单位。 1、进程的特征和定义 就绪状态（就绪状态（Ready） 执行状态（执行状态（Running） 阻塞状态（阻塞状态（Blocked） 图 2-5 进程的三种基本 状态及其转换 2、进程的三种基本状态 对单个进程： 任何时刻，进程只能处理三种 基本状态之一； 随着进程自身的推进和外界条 件

9、的变化，进程的状态可以动 态地转换 对整个系统： 每个时刻允许同时有多个进程处于就绪/阻塞状态； 对于执行状态的进程，每个处理机最多只允许有一个。 就绪 执行阻塞 进程调度 I/O请求 I/O完成 时间片完 挂起：挂起：实质是使进程不能继续执行 被挂起的进程处于静止状态； 没被挂起的进程处于活动状态。 引起挂起的原因：原因： 终端用户的请求； 父进程请求； 负荷调节的需要； 操作系统的需要； 3、挂起状态 进程状态的转换 Suspend Suspend Active Active 3、挂起状态 静止就绪(Readys) 静止阻塞(Blockeds) 活动就绪(Readya) 活动阻塞(Bloc

10、keda) 活动就绪(Readya) 活动阻塞(Blockeda) 静止就绪(Readys) 静止阻塞(Blockeds) 3、挂起状态 图 2-6 具有挂起状态的进程状态图 执行 静止 就绪 静止 阻塞 活动 就绪 活动 阻塞 请求I/O 挂起 激活 挂起 激活 挂起 唤醒 唤醒 进程调度 时间片完 创建状态 为一个新进程创建PCB，并填写必要的管理信息； 把该进程转入就绪状态并插入就绪队列之中。 引入创建状态的目的 为了保证进程的调度必须在创建工作完成后进行， 确保进程控制块操作的完整性。 增加管理的灵活性，操作系统可以根据系统性能 或主存容量的限制，推迟创建状态进程的提交。 4、创建状态

11、和终止状态 终止状态 首先等待操作系统进行善后处理； 然后将其PCB清零，并将PCB空间返还系统。 引起进程终止的事件 自然结束； 出现无法克服的错误； 被操作系统终结，或其他有终止权的进程所终结。 终止进程的处理过程 进入终止状态的进程以后不能被执行，但在操作系统中保 留有一个记录，其中保存状态码和一些计时统计数据，供 其他进程收集； 一旦其它进程完成了对终止状态进程的信息提取后，操作 系统将删除该进程。 4、创建状态和终止状态 增加创建状态与终止状态的状态转换图 4、创建状态和终止状态 图 2-7 进程的五种基本状态及转换 就绪 执行阻塞 时间片完 进程调度 I/O请求 I/O完成 创建

12、许可 终止 释放 增加创建状态与终止状态的状态转换图 4、创建状态和终止状态 图 2-8 具有创建、终止和挂起状态的进程状态图 执行 静止 就绪 静止 阻塞 活动 就绪 活动 阻塞 请求I/O 挂起 激活 挂起 激活 挂起 唤醒 唤醒 进程调度 时间片完 创建 许可 终止 释放 许可 2.1.5 进程控制块 1、进程控制块中的信息 PCB 程序段 私有 数据 进程名 当前状态 优先数 现场保留区 指示处于同一状态 进程的链指针 资源清单 进程起始地址 家族关系 其他 （a）进程示意图 （b）进程控制块的基本内容 PCB是进程存在的唯一标志。 创建进程时，创建PCB； 进程结束时，系统将撤消其P

13、CB。 进程控制块PCB（Process Control Block）： 是进程实体的一部分 是操作系统中最重要的记录型数据结构 记录了操作系统所需的、用于描述进程当前情况以及 控制进程运行的全部信息 PCB的作用：将程序变成可并发执行的进程 PCB必须长驻内存 2、进程控制块的作用 调度进程执行时,需要从该进程的PCB中查出其现 行状态及优先级； 调度到某进程后，根据PCB中所保存的处理机状态 信息，设置该进程恢复运行的现场，并根据PCB中 的程序和数据的内存始址，找到其程序和数据； 进程在执行过程中，当需要和与之合作的进程实现 同步、通信或访问文件时，也需要访问PCB； 当进程由于某种原因

14、而暂停执行时，又须将断点的 处理机环境保存在PCB中。 2、进程控制块的作用 进程标识符进程标识符 处理机状态处理机状态 进程调度信息进程调度信息 进程控制信息进程控制信息 3、进程控制块中的信息 3.1、进程标识符 进程标识符用于唯一地标识一个进程。 （1）内部标识符。在所有的操作系统中， 都为每一个进程赋予一个唯一的数字标识符， 它通常是一个进程的序号。 （2）外部标识符 由创建者提供，通常是 由用户在访问该进程时使用。 进程标识符 3.2、处理机状态 处理机状态信息主要是由处理机的各种寄存器中的 内容组成的。 处理机运行时，许多信息都存放在寄 存器中。当处理机被中断时，所有这些信息都必须

15、 保存在PCB中，以便该进程重新执行时，能从断点继 续执行。这些寄存器包括： 通用寄存器：用户可视寄存器，用于暂存信息，用户程序可 以访问； 指令计数器：存放了要访问的下一条指令的地址； 程序状态字PSW:其中包含了状态信息，如条件码、执行方式、 终端屏蔽标志等； 用户栈指针：每个用户进程都有一个或若干个与之相关的系 统栈，用于存放过程和系统调用参数及调用地址。栈指针指 向栈顶。 3.3、进程调度信息 在PCB中还存放一些与进程调度和进程对换有关的信 息，包括： 进程状态 指明进程的当前状态，作为进程调度和对 换时的依据； 进程优先级 优先级高的进程应先获得处理机 进程调度所需的其它信息 与所

16、采用的进程调度算法 有关，比如，进程已等待CPU的时间总和、进程已执 行的时间总和等； 事件 即阻塞原因，指进程由执行状态转变为阻塞状 态所等待发生的事件。 3.4、进程控制信息 程序和数据的地址: 指进程的程序和数据所在的内存 或外存地址，以便再调度到该程序执行时，能从PCB 中找到其程序和数据； 进程同步和通信机制:指实现进程同步和通信必需的 机制，如消息队列指针、信号量等； 资源清单：是一张列出了使用CPU以外的、进程所需 的全部资源及已经分配到该进程的资源的清单； 链接指针：它给出了本进程（PCB）所在队列中的下 一个进程的PCB的首地址。 链接方式：链接方式：把具有同一状态的PCB，

17、用其中的 链接字链接成一个队列 4、进程控制块的组织方式 执行指针 就绪队列指针 阻塞队列指针 空闲队列指针 PCB14 PCB23 PCB30 PCB48 PCB5 PCB67 PCB79 PCB80 PCB915 P5正在执行； 就绪进程有：P1,P4,P8 阻塞进程有：P2,P3 其余为空闲进程控制块PCB 索引方式：系统根据所有进程的状态建立几张索引 表，并把各索引表在内存的首地址记录在内存的一 些专用单元中。在每个索引表的表目中，记录具有 相应状态的某个PCB在PCB表中的地址。 3、进程控制块的组织方式 PCB1执行指针 就绪表指针 阻塞表指针 就绪索引表 阻塞索引表 PCB2 P

18、CB3 PCB4 PCB5 PCB6 PCB7 2.2 进程控制 2.2 进程控制 进程控制进程控制是进程管理中最基本的功能： 创建和撤消进程 对进程在整个生命期中各种状态之间的转换进 行有效控制。 进程控制是操作系统的内核通过原语来实现 的。 原语：原语：是指由若干条指令组成，用来实现某 个特定操作的一个过程。 原语的执行具有原子性； 原语常驻内存，且在系统状态下执行。 2.2 进程控制 系统状态系统状态和用户状态用户状态是处理机的两种执行状 态，用于防止用户程序破坏操作系统内核代 码和数据。 系统状态：系统状态：也叫管态或核心状态，它具有较 高的特权，能执行一切指令，访问所有寄存 器和存储

19、区。 通常操作系统内核就运行在系统状态。 用户状态：用户状态：也叫目态，是一种具有较低特权 的执行状态，它只能执行规定的指令、访问 规定的寄存器和存储区。 通常用户程序都是运行在用户状态。 图 2-9 进程树 2.2.1 进程的创建 1、进程图（Process Graph） 进程图：用于描述 一个进程的家庭关 系的有向树。 父进程 子进程 祖先进程 祖先 子进程可以继承父 进程所拥有的资源 A BC DEFGH IJKLM (1) 用户登录。 (2) 作业调度。 (3) 提供服务。 (4) 应用请求。 2、引起创建进程的事件 由系统内核创建新进程 由应用程序创建新进程 创建原语Creat()：

20、 功能：创建进程控制块PCB 入口信息：进程标识符、优先 级、进程开始地址、初始CPU 状态、资源清单等 实现过程： 申请空白PCB； 为新进程分配资源； 初始化进程控制块 将新进程插入就绪队列 3、进程的创建(Creation of Progress) 开始 申请空白PCB 为新进程分配资源 初始化进程控制块 将新进程插入就绪队列 2.2.2 进程的终止 1) 正常结束 2) 异常结束 越界错误 保护错 非法指令 特权指令错 运行超时 等待超时 算术运算错 I/O故障 3)外界干预 操作员或操作系统干预 父进程请求 父进程终止 1、引起进程终止(Termination of Process)

21、的事件 终止原语： 功能：终止一个指定的进程 入口信息：被终止的进程名 实现过程： 根据被终止进程的标识符，从 PCB集合中检索进程的PCB。 若被终止进程正在执行，则终 止它的执行，并置重新调度标 志。 终止属于该进程的所有子孙进 程。 释放被终止进程所拥有的全部 资源。 将终止进程移出它所在队列并 收回PCB。 2、进程的终止过程 开始 检索PCB，读出进程状态 若是执行，置调度标志为真 若有子孙进程，终止其子孙进程 将所拥有的资源归还给父进程或系统 将PCB从所在队列移出 2.2.3 进程的阻塞与唤醒 请求系统服务 启动某种操作 新数据尚未到达 无新工作可做 1、引起进程阻塞和唤醒的事件

22、 阻塞原语（block()）： 功能：将进程从执行状态 转换成阻塞状态 入口信息：可省略 实现过程： 停止进程执行，将其状态 改为阻塞状态； 将其PCB插入相应的阻塞队 列； 转调度程度进行重新调度。 进程的阻塞是进程的主动 行为 2、进程的阻塞过程 开始 将CPU当前状态存入PCB 设置进程状态为阻塞状态 将PCB置入阻塞队列 转处理机调度 唤醒原语（wakeup()）： 功能：当被阻塞进程所等待 的事件完成时，唤醒某一处 于等待队列当中的进程。 入口信息：被唤醒进程的名 字 实现过程： 将被阻塞的进程从等待该事 件的阻塞队列中移出； 将其PCB中的状态由阻塞改 为就绪； 将该PCB插入到就

23、绪队列中。 3、进程唤醒过程 开始 从阻塞队列删除该PCB 设置进程状态为就绪状态 将PCB置入就绪队列 结束 2.2.4 进程的挂起与激活 挂起原语（suspend()）： 功能：将指定进程挂起 实现过程： 挂起进程处于活动就绪状态，将其转换为静止就绪； 挂起进程处于活动阻塞状态，将其转换为静止阻塞； 把被挂起的进程的PCB复制到某指定的内存区域； 若被挂起的进程正在执行，则转向调度程序重新调度。 如果挂起是为了对换，则在挂起进程时还必须将它换出 到外存 1、进程的挂起 激活原语（active()）： 功能：使处于静止状态的进程变为活动 执行过程： 若进程处于静止阻塞状态，则将它转换成活动阻

24、塞状态； 若进程为静止就绪状态，则将它转换为活动就绪状态； 若进程转换成活动就绪状态，而系统又采用抢占调度策 略，则应检查该进程是否有权抢占CPU，若有则应进行 进程调度； 如果挂起是为了对换，则在激活被挂起的进程时还必须 将它调入内存。 2、进程的激活 2.3 进程同步 进程同步问题的提出进程同步问题的提出 进程异步推进可能造成混乱 混乱可能导致不可再现 进程同步目标进程同步目标 2.3 进程同步 间接相互制约关系（进程互斥）：这种制约源于资源共享。 直接相互制约关系（进程同步）：这种制约源于进程间合作。 2.3.1 进程同步的基本概念 同同 步步互互 斥斥 进程-进程进程-资源-进程 时间

25、次序上受到某种限制未竞争到物理资源的进程处于阻塞状态 相互清楚对方的存在及作用，交 换信息 不一定清楚其他进程情况 往往指有几个进程共同完成一个 任务 往往指多个任务多个进程间通讯制约 例：生产与消费之间，发送与接 受之间，作者与读者之间，供者 与用者之间 例：交通十字路口，单轨火车的拨道岔 口 1、两种形式的制约关系 临界资源：临界资源：在一段时间内只允许一个进程访问的 资源。临界资源的访问要求互斥的访问。 物理设备，如输入机、打印机、磁带机 软件资源，如公用变量、数据、表格、队列等 为了使多个进程有效地共享临界资源，并使程序 的执行具有可再现性，系统必须保证它们互斥地互斥地 使用临界资源使

26、用临界资源。 2、临界资源(Critical Resource) 3、生产者消费者问题 放产品 取产品 一次只能放一个产品； 一次只能取走一个产品； 缓冲区满则生产者不能放产品； 缓冲区空则消费者不能取产品； 生产者进程 消费者进程 并发 012345 n-1 生产者消费者 缓冲池 inout counter 数据结构：var n:integer; /*具有n个缓冲区的缓冲池*/ type item=; var buffer:array0,1,n-1 of item; in,out:0,1,n-1; /*指向缓冲区的指针*/ counter:0,1,n; /*缓冲区中的消息数*/ 3、生产者消

27、费者问题 register2:=counter; register2:=register2-1; counter:= register2; producer: repeat producer an item in nextp while counter=n do no-op; bufferin:=nextp; in:=(in+1)mod n counter:=counter+1; until false; consumer: repeat while counter=0 do no-op; nextc:=bufferout; out:=(out+1)mod n counter:=counter

28、-1; consume the item in nextc; until false; 说明：nextp:局部变量，用于暂时存放每次生产出的消息。 nextc:局部变量，用于存放每次要消费的消息。 register1:=counter; register1:=register1+1; counter:= register1; 3、生产者消费者问题 in out 0 1 2 34 5 6 7 3、生产者消费者问题 register 1:=counter; register 1:=register+1; counter:=register 1; register 2:=counter； regis

29、ter 2: =register 2 -1; counter:= register 2 按什么顺序执行时，counter的值是6？ register 1:=counter; register 1:=register 1+1; register 2:=counter; register 2:=register 2-1; counter:=register 2; counter:=register 1; register 1=5 register 1=6 register 2=5 register 2=4 counter=4 counter=6 假设counter的当前值为5 为了解决以上问题，可

30、将counter作为临界资源 不论是硬件临界资源，还是软件临界资源，多个进程 必须互斥地对它进行访问。 临界区定义：每个进程中访问临界资源的那段代码； 4、临界区(critical section) P1P2P3 临界区临界区临界区 4、临界区(critical section) repeat entry section exit section critical section remainder section; until false; 用于对临界资源进 行检查 将临界区正被访 问的标志恢复为 未被访问的标志 (1)空闲让进 (2) 忙则等待 (3) 有限等待 (4) 让权等待 5、同步

31、机制应遵循的规则 2.3.2 信号量机制 信号量机制的基本概念 信号量信号量(Semaphores) 信号量机制是进程同步工具 信号量是对具体物理资源的抽象 不同类的资源用不同名称的信号量代表 同类资源的个数用 0的信号量值表示 信号量值为 0 或 1 的信号量表示临界资源 信号量：Dijkstra把整型信号量定义为一个整型量S。 特性：除初始化外，仅能通过两个标准的原子操作 wait(s)（P操作）和signal(s)（V操作）来访问。描述 如下： wait(S): while S0 do no-op； S = S 1； signal(S): S = S + 1； 存在问题：只要S=0，wa

32、it操作就会不断地测试， 没能做到“让权等待” 1、整型信号量 引入进程阻塞机制，解决了“忙等”问题。 在信号量里增加对阻塞进程的记录 在信号量机制中，除了需要一个用于代表资源数目的整 型变量value外，还增加一个等待队列指针L，记录型的 数据结构描述如下： type semaphore = record value: integer; /*代表资源数目*/ L: list of process;/*等待进程链表*/ end 2、记录型信号量 2、记录型信号量 wait(S)和signal(S)操作描述： procedure wait(S) var S: semaphore; begin S

33、.value := S.value 1; if S.value 0 then block(S.L) end procedure signal(S) var S: semaphore; begin S.value := S.value + 1; if S.value 0时，可进行资源预留 di：申请个数 一次可申请一种资源的多个 4、信号量集 信号量集流程信号量集流程 1）将正在执行的进程移入第一 个Siti的等待队列中； 2）将程序指针指向该进程中 Swait操作开始处 4、信号量集 信号量集流程 将与Si相关的等待队列 中的所有进程移到准备 队列 4、信号量集 (1) Swait(S, d,

34、 d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。 (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录 型信号量(S1时)或互斥信号量(S=1时)。 (3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。 当S1时，允许多个进程进入某特定区；当S变为0后，将阻止 任何进程进入特定区。换言之，它相当于一个可控开关。 4、信号量集特殊情况 S=2 Swait(S,1,0) 临界区 P1 P2 P3 Pn S=0 Swait(S,1,0) 临界区 P1 P2P3Pn 2.3.3 信号量的应用 对竞争资源的

35、互斥访问过程 1、利用信号量实现进程互斥 利用信号量实现进程互斥的进程可描述如下： Var mutex:semaphore =1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend 1、利用

36、信号量实现进程互斥 wait(mutex)和signal(mutex)必须成对出现 Pi代表进程； Si代表Pi中的语句；s为具有前驱关系的两进程的公用信号量， 其初值为0。 var s:semaphore:=0; begin parbegin begin S1; signal(s);end; begin wait(s); S2; end; parend end S1 S2 s p1p2 2、利用信号量实现前趋关系 2、利用信号量实现前趋关系 S1 S2 S5 S3 S4 S6 a b cd gfe Var a,b,c,d,e,f,g: semaphore:=0,0,0,0,0,0,0; be

37、gin parbegin begin S1;signal(a);signal(b);end; begin wait(a);S2;signal(c);signal(d);end; begin wait(c);S3;signal(e);end; begin wait(d);S4;signal(f);end; begin wait(b);S5;signal(g);end; begin wait(e);wait(f);wait(g);S6;end; parend end 2.3.4 管程机制 信号量同步的缺点 同步操作分散：信号量机制中，同步操作分散在 各个进程中，使用不当就可能导致各进程死锁（ 如P

38、、V操作的次序错误、重复或遗漏） 易读性差：要了解对于一组共享变量及信号量的 操作是否正确，必须通读整个系统或者并发程序 不利于修改和维护：各模块的独立性差，任一组 变量或一段代码的修改都可能影响全局 正确性难以保证：操作系统或并发程序通常很大 ，很难保证这样一个复杂的系统没有逻辑错误 管程：代表共享资源的数据结构，以及由对该 共享数据结构实施操作的一组过程所组成的资 源管理程序，共同构成了一个操作系统的资源 管理模块。 管程的组成： 管程的名称 局部于管程内部的共享数据结构说明； 对该数据结构进行操作的一组过程； 对局部于管程内部的共享数据设置初始值的语句。 1、管程（Monitors）的定

39、义 Hansen 图 2-13 管程的示意图 1、管程的定义 初始化代码 一组操作过程 共享数据 条件（不忙）队列 进入队列 管程的语法： type monitor_name=monitor define ; use ; procedure (); begin end; function (): 值类型; begin end; begin ; end 1、管程的定义 管程名：monitor_name 局部于管程的共享变 量说明； 对该数据结构进行操 作的一组过程； 对局部于管程的数据 设置初始值的语句 1、管程的定义 管程的特点： 局部性：管程内的局部变量只能被局部于管程内的过程 所访问；反之

40、亦然，即局部于管程内的过程只能访问管 程内的变量； 访问接口：任何进程只能通过调用管程提供的过程入口 进入管程 互斥性：任一时刻，最多只能有一个进程在管程中执行 注：保证进程互斥地进入管程是由编译器负责的。即管程是一 种编程语言的构件，它的实现需要得到编译器的支持。 1、管程的定义 管程的特性（从语言角度看）： 模块化：管程是一个基本程序单位，可以单独编译。 抽象数据类型：管程中不仅有数据，而且有对数据的操 作。 信息：管程中的数据结构只能被管程中的过程访问，这 些过程也是在管程内部定义的，供管程外的进程调用， 而管程中的数据结构以及过程（函数）的具体实现外部 不可见。 1、管程的定义 管程和

41、进程的区别： 定义的数据结构：进程定义的是私有数据结构PCB；管 程定义的是公共数据结构； 数据结构上的操作：进程由顺序程序执行有关操作；管 程主要进行同步操作和初始化操作； 设置的目的：设置进程的目的在于实现系统的并发性； 管程的设置则是解决共享资源的互斥使用问题； 工作方式：进程通过调用管程中的过程对共享数据结构 实行操作，因此进程是主动工作方式，管程是被动工作 方式； 并发性：进程之间能并发执行，而管程则不能与其调用 者并发； 进程具有动态性，由创建而生，由撤消而亡；而管程是 操作系统的一个资源管理模块，供进程调用。 条件变量：是局部于管程的变量，用于区分不同的阻 塞原因 格式： Var

42、 x, y:condition。 条件变量是一种抽象数据类型，每个条件变量保存了 一个链表。 条件变量的操作： x.wait操作：将执行进程挂到与条件变量x相应的等待队列 上，并释放管程，如果没有等待进程，x.signal不起任何作 用。 signal操作：唤醒与x相应的等待队列上的一个进程，如果 存在多个这样的进程，则选择其中的一个，但如果没有被 阻塞的进程，则x.signal操作不产生任何后果。 2、条件变量 2.4 经典进程的同步问题 2.4.1 生产者消费者问题 消息缓冲池消息缓冲池 生产者产生的消息放入缓冲 池内； 消费者从缓冲池内取走消息 消费； 消费者消费后的空白消息块 放进空白

43、缓冲池内供生产者使 用。 23121 算法分析算法分析 两类进程两类进程：生产者进程和消费者进程 （1）进程间的关系）进程间的关系 生产者生产消息后消费者消费 消费者消费后的空白缓冲块由生产者生产消息 （2）队列的操作）队列的操作 两个共享队列： 消息缓冲队列 空白缓冲队列 多个进程共享一个队列 是否需要保护 进程间的关系进程间的关系 生产者生产消息 后 消费者消费的合作关系 消费者消费 后 的空白缓冲块由生产者生产消息的 合作关系 进程间在队列操作上的互斥关系 信号量信号量 full：私有信号量，表示缓冲池中满缓冲区数量 empty：私有信号量，表示缓冲池中空缓冲区数量 mutex：公用信号

44、量，实现诸进程对缓冲池的互斥 使用 1、利用记录型信号量解决生产者-消费者问题 算法流程 Var mutex, empty, full:semaphore =1,n,0; buffer:array0, , n-1 of item; in, out: integer =0, 0; begin parbegin producer:begin repeat producer an item nextp; wait(empty); wait(mutex); buffer(in) =nextp; in =(in+1) mod n; signal(mutex); signal(full); until f

45、alse; end consumer:begin repeat wait(full); wait(mutex); nextc =buffer(out); out =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end Var mutex, empty, full: semaphore : = 1,n,0; buffer:array0, , n-1 of item; in, out: integer : = 0, 0; begin parbegin

46、producer:begin repeat producer an item nextp; wait(empty); wait(mutex); buffer(in) = nextp; in = (in+1) mod n; signal(mutex); signal(full); until false; end consumer:begin repeat wait(full); wait(mutex); nextc = buffer(out); out = (out+1) mod n; signal(mutex); signal(empty); consumer the item in nex

47、tc; until false; end parend end Swait(empty, mutex); Ssignal(mutex, full); Swait(full, mutex); Ssignal(mutex, empty); 2、利用AND信号量解决生产者-消费者问题 建立一个管程，并命名为producer-consumer, 或简 称为PC。其中包括两个局部过程： put(item)过程：负责将产品投放到缓冲池中； get(item)过程：负责从缓冲池中取出产品。 其他变量包括： 整型变量count：表示在缓冲池中已有的产品数目； 条件变量notfull：对应于缓冲池不全满； 条件

48、变量notempty：对应于缓冲池不全空。 3、利用管程解决生产者-消费者问题 type PC = monitor var in,out,count:integer; buffer:array0,n-1 of item; notfull, notempty:condition; procedure entry put(item) begin if countn then notfull.wait; buffer(in) = item; in = (in+1) mod n; count = count+1; if notempty.queue then notempty.signal; end

49、共享局部 变量说明 /定义管程 /将产品投放到缓冲池中的过程 /等待缓冲池不全满条件成立 /缓冲池不全空条件成立 条件变量 procedure entry get(item) begin if count0 then notempty.wait; item = buffer(out); out = (out+1) mod n; count = count-1; if notfull.quene then notfull.signal; end begin in = out = 0; count =0 end 初始化代码 /负责从缓冲池中取出产品的过程 /等待缓冲池不全空条件成立 /缓冲池不全满

50、条件成立 在利用管程解决生产者-消费者问题时， 其中的生 产者和消费者可描述为： producer:begin repeat produce an item in nextp; PC.put(nextp); until false; end consumer:begin repeat PC.get(nextc); consume the item in nextc; until false; end 2.4.2 哲学家进餐问题 问题描述问题描述 五位哲学家围桌而坐 哲学家在思考问题时不 需要任何资源，思考完 问题后进入进餐态。 每人必须获得左右两支 筷子才能进餐 思考 思考 思考 思考 思考