OS2

null第二章 进程管理第二章 进程管理多道程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 进程 进程间的相互作用 进程间的通信 进程调度（CPU调度） 线程 前趋图 (Precedence Graph) 前趋图 (Precedence Graph) 前趋图是一个有向无循环图，记为DAG (Drected Acyclic Graph) 前趋图用来描述程序各部分间的依赖关系或一个大的计算各子部分间的因果关系 前趋图中的元素 结 点：表示一个语句、程序段、进程 有向边： 表示结点间的偏序关系（前趋关系） →={(Pi , Pj)|Pi must complete before Pj may start} 若(Pi , Pj) ∈→，可写成 Pi →Pj，称 Pi是 Pj的直接前趋，而 Pj是Pi的直接后继。 前趋图示例前趋图示例2316745 7个结点的前趋图前趋关系 P1 → P2, P1 → P3 P1 → P4, P2 → P5 P3 → P5, P4 → P6 P5 → P7, P6 → P7多道程序设计多道程序设计顺序程序 并发程序 多道程序设计 顺序程序 顺序程序程序： 指令或语句序列，体现了某种算法，所有程序是顺序的 顺序环境： 在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响程序顺序执行的例程序顺序执行的例程序顺序执行前趋图I1C1P1I2C2P2null顺序程序特征： 程序执行的顺序性 程序执行的封闭性 独占资源，执行过程中不受外界影响 程序执行结果的确定性 程序结果的可再现性 程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同null语句的执行顺序 S1：a=x+y S2：b=a-5 S3：c=b+1并发程序并发程序并发环境： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的程序并发执行的例程序并发执行的例程序并发执行前趋图 I1I2I3I4C1C2C3C4p1P2P3P4null并发程序特征： （1）程序结果的不可再现性(P29) 并发程序执行的结果与其执行的相对速度有关，是不确定的 （2）在并发环境下程序的执行是间断性的 执行——停——执行（3）资源共享 系统中资源被多个进程使用 （4）独立性和制约性 独立的相对速度、起始时间 进程之间可相互作用（相互制约） 可分为直接作用和间接作用 （5）程序和计算不再一一对应 （计算：一个程序的执行）（3）资源共享 系统中资源被多个进程使用 （4）独立性和制约性 独立的相对速度、起始时间 进程之间可相互作用（相互制约） 可分为直接作用和间接作用 （5）程序和计算不再一一对应 （计算：一个程序的执行）并发程序并发程序引入并发的目的： 引入并发是为了提高资源利用率，从而提高系统效率。 并发与并行概念的区别： concurrency,parallelnullS1: a:=x+1 S2: b:=y+2 S3: c:=a+b S4: d:=c+b多道程序设计多道程序设计定义：Multiprogramming 多道程序设计是指允许多个程序同时进入内存并运行 （引入目的是为了提高系统效率） 与并发不完全是一个概念，但效果相似在顺序环境下单道程序执行： CPU利用率= 40/80 = 50% DEV1利用率=15/80=18.75% DEV2利用率=25/80=31.25% 在顺序环境下单道程序执行： CPU利用率= 40/80 = 50% DEV1利用率=15/80=18.75% DEV2利用率=25/80=31.25% CPU DEV1DEV1CPU CPU A 10 15 20 30 40 t(s) DEV2CPU DEV2DEV2 CPU B 10 20 30 40 t(s) 25 例：例：例：在并发环境下多道程序执行： CPU利用=40/45 = 89%DEV1并发环境下利用=15/45= 33%DEV2并发环境下利用=25/45= 56%0 10 20 30 35 45 CPU DEV1 ---CPU DEV1CPUDEV2 CPU DEV2 CPU ---- DEV2T(s)null例:两个计算问题A、B，A计算50ms,打印100ms，再计算50ms，打印100ms结束，B计算50ms，输入80ms，再计算100ms，打印100ms结束，假定让B先开始。试计算单道程序执行和多道程序执行CPU的利用率。null考虑因素： 在多道程序环境下如何向用户提供服务 在并发程序之间如何正确传递消息（通讯） 如何对CPU进行调度，保证每个用户相对公平地得到CPU （CPU是一个只可调度，不可分配的资源）null已知一个求值公式(A2+3B)/(B+5A),若A,B已赋值,试画出该公式求值过程的前驱图.null程序的顺序执行通常在 的工作环境中,具有以下特征 ;程序的并发执行在 的工作环境中,具有以下特征 A.单道程序 B.多道程序 C.程序的可再现性 D.资源共享 null如何管理其他资源 当各用户对资源使用上发生冲突时，如何处理竞争 对CPU只能通过调度来解决竞争问题，而对于其他资源通过申请—分配—使用—回收的办法进行管理，当且仅当占有CPU的时候才可以申请，否则要排队等候nullCobegin get; copy; put; Coend复制一个 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 null并行环境下程序间的制约关系进程 进程的概念 进程的状态及其转换 进程控制块（Process Control Block） 进程的特征进程OS 对进程的 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 OS 对进程的要求OS 必须交替执行多个进程，以便最大程度的使用CPU，同时提供合理的响应时间 OS 必须将资源分配给进程，同时避免死锁 OS必须支持进程间通信以及用户进程创建进程的概念进程的概念定义：Process 进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位进程的定义进程的定义进程是程序的一次执行 进程是一个程序及其数据在处理机上顺序执行时所发生的活动 进程是程序在一个数据集合上的运行过程, 是系统进行资源分配和调度的一个独立单位null 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。null进程的分类： 系统进程 用户进程 （系统进程优先于用户进程）进程的特征进程的特征（1）动态性 进程是程序执行过程，动态性是基本特征。动态性还表现在进程有生命期，有创建、执行、暂停、消亡的过程。“由创建而产生，由调度而执行，由撤消而消亡”． 程序是静态的概念，在机内外都存在，而进程只存在于系统内部。null（2）并发性 指多个进程实体同时存在于内存中，能在一段时间内同时运行（并发）。 并发性是进程的重要特征，也是操作系统的重要特征，引入进程的目的就是为了是程序能并发执行。 进程的特征进程的特征进程的特征（3）独立性 指进程是一个运行的独立单位和获得资源的独立单位。 （4）异步性 由于进程共享资源和相互合作形成了相互制约的关系，找成进程执行的间断性，进程以各自独立的、不可预知的速度向前推进。 和PCB组成，也称“进程映象”。进程的特征进程的特征（5）结构特征 为了管理和控制进程，系统为每个进程设立一个进程控制块（PCB），这样从结构上看，每个进程都由响应的代码段、数据段．null程序与进程之间的区别： 进程更能真实地描述并发，而程序不能 进程是由程序和数据两部分组成的 程序是静态的，进程是动态的 进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 一个程序可对应多个进程，反之亦然 进程具有创建其他进程的功能，而程序没有nullnullnull进程的基本状态及其转换进程的基本状态及其转换进程的三种基本状态： 进程在生命消亡前处于且仅处于三种基本状态之一 不同系统设置的进程状态数目不同null运行态（Running）： 进程占有CPU，并在CPU上运行 就绪态（Ready）： 一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行）null等待态（Blocked）：阻塞态、挂起态、封锁态 冻结态、睡眠态 指进程因等待某种事件的发生而暂时不能运行的状态 （即使CPU空闲，该进程也不可运行） null运行就绪等待进程的状态及其转换null进程状态转换： 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换  就绪—运行  运行—就绪  运行—等待  等待—就绪进程转换进程转换就绪 --> 运行 调度程序选择一个新的进程运行 运行 --> 就绪 运行进程用完了时间片 运行进程被中断，因为一高优先级进程处于就绪状态 进程转换运行 --> 等待 当一进程必须等待时 OS尚未完成服务 对一资源的访问尚不能进行 初始化I/O 且必须等待结果 等待某一进程提供输入 等待 --> 就绪 当所等待的事件发生时进程转换null【思考题】 1． 有没有这样的状态转换，为什么？ 等待—运行； 就绪—等待 null其他状态： 创建状态，终止状态 挂起状态 （调节负载，对换，父进程，操作系统，终端用户）null创建( 新new)状态 OS 已完成为创建一进程所必要的工作 已构造了进程标识符 已创建了管理进程所需的 表格 关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载 但还没有允许执行该进程 (尚未同意) 因为资源有限null终止（退出exit)状态 中止后进程移入该状态 它不再有执行资格 表格和其它信息暂时由辅助程序保留 例子: 为处理用户帐单而累计资源使用情况的财务程序 当数据不再需要后，进程(和它的表格)被删除五状态进程模型五状态进程模型准备退出：父进程可中止子进程新状态转换 (中期调度)新状态转换 (中期调度)阻塞 -->阻塞挂起 当所有进程都阻塞，OS会安排空间让一就绪进程进入内存 阻塞挂起 --> 就绪挂起 当等待的事件发生时 (状态信息已在OS中) null就绪挂起-->就绪 当内存中没有就绪进程时 就绪-->就绪挂起 (较少见) 当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时 null七状态进程模型null设系统中有n (n>2)个进程,且当前不在执行进程调试程序,试考虑下述种情况,不可能是发生的是( )。 A.没有运行进程,有2个就绪进程,n个进程处于等待状态 B.有1个运行进程,没有就绪进程,n-1个进程处于等待状态 C.有1个运行进程,有1个就绪进程,n-2个进程处于等待状态 D.有1个运行进程,有n-1个就绪进程,没有进程处于等待状态 进程控制块 （Process Control Block）进程控制块 （Process Control Block）概念： 系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程 null系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志 进程与PCB是一一对应的 进程映象 (进程要素)进程映象 (进程要素)用户程序 用户数据 栈 -用于过程调用和参数传递null进程控制块PCB (执行上下文) 控制进程所需的数据(进程属性)，包括: 进程标识符信息 处理器状态信息 进程控制信息 nullnullPCB的内容： 调度信息： 进程名；进程的内部标识；用户名；进程状态；进程优先级；进程的存储信息（起始地址，长度）；进程资源清单；进程家族关系；进程的队列指针；进程的消息队列指针；进程当前打开的文件… ... 现场信息： 记录了重要的寄存器；(虚)时钟等内容进程标识符 (在PCB中)进程标识符 (在PCB中)可使用一些数字标识符 统一进程标识符 (必然的) 索引至 (直接或间接) 主进程表 用户标识符 与某个作业对应的用户 创建本进程的某个进程的标识符处理器状态信息 (在PCB中)处理器状态信息 (在PCB中)处理器寄存器内容 用户可见寄存器 控制和状态寄存器 栈指针 程序状态字 (PSW) 包含状态信息 例子: 在Pentium机中的EFLAGS寄存器进程控制信息 (在PCB中)进程控制信息 (在PCB中)调度和状态信息 进程状态 (如: 运行，就绪，阻塞...) 进程优先级 该进程在等待的事件 (若被阻塞) 数据结构信息 进程可能需要有指向其他PCB的指针, 父-子进程关系及其它结构进程控制信息 (在PCB中)进程间通信 可能需要标志和信号 进程特权 如: 访问特定的内存地址... 存储管理 指向赋予该进程的段/页表的指针 所拥有的资源和使用情况 使用中的资源: 打开的文件，I/O设备... (CPU , I/O...)的时间使用史进程控制信息 (在PCB中)执行的方式执行的方式为了提供对PCB (和OS其它数据)的保护，多数处理器支持至少两种执行方式: 特权方式 (又称作系统方式，内核方式，管理方式,控制方式) 操作控制寄存器,基本 I/O指令， 存储管理... 用户方式 为此， CPU提供一个(或一些)方式位，这些二进制位只能被中断、陷阱或OS调用所设置nullPCB表： 系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度 （注：多道程序中的多道与系统并发度不同）nullPCB表组织方式：PCB表组织方式： 常用索引方式，对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址 （其他方式：线性表或链表） 进程队列：不同状态进程分别组成队列 运行队列、就绪队列、等待队列进程控制块（Process Control Block）进程控制块（Process Control Block）null 进程控制 进程控制 创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。 进程创建原语 进程撤消原语 阻塞原语 唤醒原语 挂起原语 激活（解挂）原语进程的创建进程的创建创建一个PCB 赋予一个统一进程标识符 为进程映象分配空间 初始化进程控制块 许多默认值 (如: 状态为 New，无I/O设备或文件...) 设置相应的链接 如: 把新进程加到就绪队列的链表中进程阻塞进程阻塞 处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态 进程唤醒进程撤消进程撤消收回进程所占有的资源 撤消该进程的PCBnull 可再入程序： 可被多个进程同时调用的程序，具有下列性质： 它是纯代码的，即在执行过程中自身不改变，调用它的进程应该提供数据区进程间的联系进程间的联系相交进程与无关进程 相交进程：指多个并发进程在逻辑上有某种联系 无关进程（不相交进程）：在逻辑上无任何联系的进程null直接作用和间接作用 直接作用： 进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间 间接作用： 进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间进程的同步（直接作用）进程的同步（直接作用）进程的同步：synchronism 指系统中一些进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态例: 司机 P1 售票员 P2 REPEAT REPEAT 启动 关门 正常运行 售票 到站停 开门 UNTIL FALSE UNTIL FALSE 例: 司机 P1 售票员 P2 REPEAT REPEAT 启动 关门 正常运行 售票 到站停 开门 UNTIL FALSE UNTIL FALSE null进程的互斥（间接作用）mutual exclusion 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥临界资源：critical resource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量null临界区（互斥区）：critical section 一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作 在进程中涉及到临界资源的程序段叫临界区nulla := a -1 print (a)a := a +1 print (a) 进程的互斥 （间接作用）nullnull使用互斥区的原则： 有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入 无空等待：不允许两个以上的进程同时进入互斥区 多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待 有限等待：任何进入互斥区的要求应在有限的时间内得到满足 让权等待：处于等待状态的进程应放弃占用CPUnull使用互斥区的原则： 前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定 解决方法： 硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高） 软件（用编程解决，但常常忙等待 ）软件解法 (1) free: 表示临界状态 true: 无进程在临界区(初值) false:有进程在临界区 .... L: if free then begin free:=false; ‘进入临界区’ end else goto L; free:=true 软件解法 (1) free: 表示临界状态 true: 无进程在临界区(初值) false:有进程在临界区 .... L: if free then begin free:=false; ‘进入临界区’ end else goto L; free:=true null软件解法 (2) turn: true P进入临界区 false Q进入临界区 .... P: repeat until turn; ‘进入临界区’ turn:=flase; Q: repeat until not turn; ‘进入临界区’ turn:=true; 软件解法：(3) pturn,qturn: 初值为false P进入临界区的条件: pturn∧ not qturn Q进入临界区的条件: not pturn∧ qturn P .... Q ..... pturn:=true; qturn:=ture; repeat until not qturn; repeat until not pturn ‘进入临界区’ ‘进入临界区’ pturn:=false; qturn:=false ... ... null软件解法的缺点： 1. 忙等待 2. 实现过于复杂，需要高的编程技巧 硬件解法 (1) “测试并设置”指令硬件解法 (1) “测试并设置”指令Function Test_and_Set (var target:boolean):boolean begin Test_and_Set:=target; target:=true end 硬件解法 (1) 硬件解法 (1) Var lock:boolean; 进入临界区前执行： While Test_and_Set(lock) do skip; 离开临界区后执行： lock:=false; 硬件解法 (2) “交换”指令硬件解法 (2) “交换”指令Function Swap(var a,b:boolean) Var temp:boolean; begin temp:=a; a:=b; b:=temp end 每一组共享变量定义一个全局变量 每一组共享变量定义一个全局变量Var lock:boolean; 每个进程定义一个局部变量 Var key:boolean; 进入临界区前执行： key:=true; repeat swap(lock,key); until key=false; 离开临界区后执行：lock:=false;硬件解法 (3) “开关中断”指令硬件解法 (3) “开关中断”指令进入临界区前执行： 执行“关中断”指令 离开临界区后执行： 执行“开中断”指令进程的同步机制── 信号量及P.V操作（解决进程同步）进程的同步机制── 信号量及P.V操作（解决进程同步）同步机制： 信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中） null同步机制应满足的基本要求： * 描述能力 * 可以实现 * 效率高 * 使用方便 null信号量：semaphore 是一个数据结构，定义如下： TYPE semaphore= RECORD Value：integer Queue：Pointer_PCB END 信号量说明： VAR：S：semaphoreP.V操作P.V操作P操作 P(s) : [wait(s)] s . Value : = s . Value - 1; IF s . Value < 0 then 将该进程状态置为等待状态 然后将该进程的PCB插入相应的等待队列末尾P.V操作P.V操作V操作 V(s) :[signal(s)] s .Value : = s .Value + 1; IF s .Value < = 0 then 唤醒相应等待队列中等待的一个进程 改变其状态为就绪态 并将其插入就绪队列nullP、V操作为原语操作 原语：primitive or atomic action 是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性 即原语的执行必须是连续的，在执行过程中不允许被中断 实现：开关中断null信号量的使用： 必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作null用P.V操作解决进程间互斥问题经典的生产者─消费者问题经典的生产者─消费者问题消费者生产者缓冲区经典的生产者─消费者问题经典的生产者─消费者问题同步问题： P进程不能往“满”的缓冲区中放产品，只有缓冲区有空后才可放产品,设置信号量为empty,初值为1. Q进程不能从“空”的缓冲区中取产品，只有在缓冲区有产品以后才可取产品,设置信号量full,初值为0.nullP（生产者）： 生产一件产品； P（empty); 产品存入缓冲区； V（full); Q (消费者）： P（full); 从缓冲区取一件产品； V（empty); 消费产品； nullVar mutex:semaphore:=1; repeat p(mutex); 进入临界区； v(mutex); until false; 利用信号量实现互斥null问题描述 有一群生产者进程在生产消息, 并将消息提供给消费者进程去消费. 为使生产者进程和消费者进程能并发执行, 在它们之间设置了一个具有n个缓冲区的缓冲池, 生产者进程可将它所生产的消息放入一个缓冲区中, 消费者进程可从一个缓冲区中取得一个消息消费. 尽管所有的生产者进程和消费者进程都以异步方式运行, 但它们之间必须保持同步, 即不允许消费进程者到一个空缓冲区去取消息, 也不允许生产者进程向一个已装有消息且尚未被取走消息的缓冲区中投放消息. nullnull三个信号量 empty =n 缓冲区空白的个数 Full=0 数据的个数 Mutex=1 是否能访问缓冲区nullQ： Repeat P(full); P(mutex); 从缓冲区取产品； V(mutex); V(empty); 消费产品； Until false; P： Repeat 生产一个产品； P(empty); P(mutex); 送产品到缓冲区； V(mutex); V(full); Until false; nullP.V操作讨论 1) 信号量的物理含义： S>0表示有S个资源可用 S=0表示无资源可用 S<0则| S |表示S等待队列中的进程个数 P(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应该大于等于0null2) P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前 而两个V操作无关紧要null3）P.V操作的优缺点 优点： 简单，而且表达能力强（用P.V操作可解决任何同步互斥问题） 缺点： 不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂【思考题】【思考题】1.用P.V操作解决下图之同步问题:输入处理打印fstgnullVar s1,s2:semaphore; /*s1表示缓冲区是否可用； s2表示缓冲区有无可供打印的数*/ s1:=1;s2:=0 nullPorcess 计算进程 Pc Begin repeat P(s1); 计算下一数据并放入缓冲区； V(s2); until false; End.nullProcess 打印进程 Pp Begin repeat P(s2); 从缓冲区中取数； v(s1); 打印数据； untill false; End.用P.V操作解决司机与售票员的问题用P.V操作解决司机与售票员的问题null设初始状态为车停在始发站，车门开着。 Run 表示能否启动车辆 Open 表示能否开车门 Var run,open:semaphore:=1,0;nullProcess 司机 Begin repeat P(run); 启动车辆； 正常行驶； 到站停车； V（open); until false; End. Process 售票员 Begin repeat P(open); 开车门； 关车门； V（run); 售票； until false; End. 经典问题 经典问题1.读者写者问题 有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作第一类：读者优先第一类：读者优先如果读者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待读者与写者问题读者与写者问题null2.第二类读者写者问题： 写者优先 条件： 1）多个读者可以同时进行读 2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行） 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）2.哲学家就餐问题2.哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的感到饥饿后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子null 为防止死锁发生可采取的措施： 最多允许4个哲学家同时去拿左边的筷子 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 nullVar fork:array of [0..4]: semaphore ; Fork[I]=1 null Repeat p(fork[(i+1) mod 5])； p(fork[i]); 进食； v(fork[i]); v(fork[(i+1) mod 5])； Until false; 【作业】【作业】1. 若有一个文件F，供进程共享，现把进程分成A、B两组，规定同组的进程可以同时读文件F，但当有A组（或B组）的进程在读文件F时不允许B组（或A组）的进程读文件F。现定义两个计数器C1和C2分别记录A组和B组中读文件F 的进程数，当用P、V操作进行管理时需要三个信号量S1、S2、Sab 才能保证正确的并发执行，试写出对应的程序。null三个信号量、两个计数器 S1,s2,sab、c1,c2 S1,s2是计数器c1,c2的互斥信号量 Sab 是a、b两组间的互斥信号量 其初值为 S1:=1,s2:=1; sab:=1, c1:=0,c2:=0 null程序结构为： Begin s1,s2,sab:semaphore; C1,c2:integer; S1:=1,s2:=1;sab:=1,c1:=0,c2:=0 Cobegin null process ai(i=1,2,3…) begin p(s1); c1:=c1+1; if c1=1 then p(sab); v(s1); read file f; p(s1); c1:=c1-1； if c1=0 then v(sab); v(s1); end;nullprocess bj(j=1,2,3…) begin p(s2); c2:=c2+1; if c2=1 then p(sab); v(s2); read file f; p(s2); c2:=c2-1； if c2=0 then v(sab); v(s2); end; Coend; End. null【作业】哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全体到齐后开始讨论；在讨论的间隙四位哲学家进餐，每人进餐时都需使用刀、叉各一把，餐桌上的布置如下图，请用信号量及P、V操作说明这四位哲学家的同步、互斥过程。甲乙丙丁食品刀1叉2刀2叉1nullPa( ) begin repeat p (knife1); p ( fork1); 进餐; v (knife1); v (fork1); 讨论问题; until false; end. null【作业】：一个理发店，由一间等候室W和一间工作室B组成，顾客可以从大街上进入W，等候理发，两个房间的入口是并排的，且共享一扇日本式的推拉门（门总是挡住一个入口）。顾客在工作室理完发，可由B旁门出去。W中有N把椅子，顾客必须坐着等候。理发师可由门上小窗查看W中无人就睡觉，否则开门，并叫一位顾客入内理发，顾客每进入一位，都拉铃通知理发师，试问，若把顾客和理发师都视为进程，请用P、V操作写出进程的同步算法。nullBWnullVar Sn, mutex, s :semaphore:=n,1,0; Process 顾客 begin wait(Sn); wait(mutex); 推门进入W; signal(mutex); signal(s); 坐下等侯; 被理发师叫入B; signal(Sn); 退出; end.nullProcess 理发师 begin repeat wait(s); wait(mutex); 开门并叫进一位; signal(mutex); 理发; until false; end. null【作业】有桥如下图,车流如箭头所示,桥上不允许两车交会,但允许同方向多辆车依次通行(即桥上可以有多个同方向的车)。用P、V操作实现交通管理以防止桥上堵塞。 null利用锁解决互斥 当进程进入临界区之前，首先测试 w的状态，w=1表示上锁，该资源已占用，w=0表示开锁，该资源已空闲，未被占用。 Lock (int w) { while (w==1); W=1 }Unlock(int w) { w=0 } null﹕ Lock(w); 临界区; Unlock(w); ﹕ 进程通信 进程通信管程 消息缓冲通信方式结构化的同步/互斥机制——管程 结构化的同步/互斥机制——管程 建立管程的基本理由是：由于对临界区的执行分散在各进程中，这样不便于系统对临界资源的控制和管理，也很难发现和纠正分散在用户程序中的对同步原语的错误使用等问题。为此，应把分散的各同类临界区集中起来。并为每个可共享资源设立一个专门的管程来统一管理各进程对该资源的访问。这样既便于系统管理共享资源，又能保证互斥访问。null管程主要由两部分组成： （1）局部于该管程的共享数据，这些数据表示了相应资源的状态。 （2）局部于该管程的若干过程，每个过程完成关于上述数据的某种规定操作。 为了实现对临界资源的互斥访问，管程每次只允许一个进程进入其内（即访问管程内的某个过程），这是由编译系统保证的。 在利用管程解决生产者、消费者问题时，其中的生产者和消费者可描述为：在利用管程解决生产者、消费者问题时，其中的生产者和消费者可描述为：producer：begin repeat produce an item； ringbuffer. put(item)； until false； end consumer：begin repeat ringbuffer. get (item)； consume the item； end概述概述 P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息 如果要在进程间传递大量信息则要用Send / Receive原语（高级通讯原语）进程的通信方式之二——消息缓冲 进程的通信方式之二——消息缓冲 1．SEND(A)（发送消息）原语 2．RECEIVE（A）（读取消息）原语 null进程通信的方式 共享内存： 相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换 null消息传递： 系统为进程提供了两个高级通讯原语send和receive send： 当要进行消息传递时执行send receive： 当接收者要接收消息时执行receive消息传递模式消息传递模式消息缓冲 在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传递来的缓冲区 信箱通信直接方式：直接方式： 发送进程发消息时要指定接收进程的名字， 反过来，接收时要指明发送进程的名字 Send(receiver,message) Receiver(sender,message) * 对称形式：一对一 * 非对称形式：多对一 （顾客/服务员） 有缓冲（有界，无界），无缓冲 间接方式： 间接方式： 发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信 发送原语：send(MB,Message) 接收原语：receive(MB,Message) 消息缓冲 消息缓冲（有界缓冲区原理）： 在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行send系统调用，产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行 消息缓冲 消息缓冲（有界缓冲区原理）： 在以后某个时刻，当接收进程执行到receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行 nullnull消息缓冲区结构： 消息长度 消息正文 发送者 消息队列指针 线程的基本概念线程的基本概念线程的引入 线程与进程的对比 线程的实现 线程的引入线程的引入进程的两个基本属性： 资源的拥有者： 给每个进程分配一虚拟地址空间，保存进程映像 控制一些资源（文件，I/O设备） 有状态、优先级、调度线程的引入-2线程的引入-2进程的两个基本属性： 调度单位： 进程是一个执行轨迹 以上两个属性构成进程并发执行的基础线程的引入-3线程的引入-3系统必须完成的操作： 创建进程 撤消进程 进程切换线程的引入-4线程的引入-4线程：有时称轻量级进程 进程中的一个实体 是一个CPU调度单位 资源的拥有者还是进程或称任务线程的引入-5线程的引入-5线程： 有执行状态 不运行时保存上下文 有一个执行栈 有一些局部变量的静态存储 可存取所在进程的内存和其他资源 可以创建、撤消另一个线程null线程和进程： 单进程、单线程 单进程、多线程 多进程、一个进程一个线程 多进程、一个进程多个线程nullnull引入线程的好处：引入线程的好处：两个线程的切换花费时间少创建一个新线程花费时间少（结束亦如此）因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核线程与进程的比较线程与进程的比较调度 拥有资源 并发性 系统开销null(1)调度方面 在传统的操作系统中，拥有资源和独立调度的基本单位都是进程，而在引入线程的操作系统中，线程是独立调度的基本单位，进程是资源拥有的基本单位。在同一进程中，线程的切换不会引起进程切换，在不同的进程中进行线程切换，将会引起进程切换。null（2）拥有资源 不论是传统操作系统还是设有线程的操作系统，进程都是拥有资源的基本单位，而线程不拥有系统资源（只有一点必不可少的资源），但线程可以访问其所隶属进程的资源。null（3）并发性 在引入线程的操作系统中，不仅进程之间可以并发执行，而且同一进程内的多个线程之间也可并发执行。null（4）系统开销 由于创建进程或撤消进程时，系统都要为之分配或回收资源，操作系统所付出的开销远大于创建或撤消线程时的开销。 在进行进程切换时，涉及到整个当前进程CPU环境的保存及新调度到进程的CPU环境的设置；而线程切换时，只需保存和设置少量寄存器内容，因此开销很小。 另外，由于同一进程内的多个线程共享进程的地址空间，因此，多线程之间的同步与通信非常容易实现，甚至无需操作系统的干预。线程的实现机制线程的实现机制用户级线程 核心级线程 两者结合方法用户级线程（ULT）：用户级线程（ULT）：核心不知道线程的存在线程库：线程库：在线程之间传递消息和数据对用户级线程的核心活动：对用户级线程的核心活动：当线程调用系统调用时，整个进程阻塞用户级线程的优点和缺点：用户级线程的优点和缺点：调度是应用程序特定的：可以选择最好的算法用户级线程的优点和缺点：用户级线程的优点和缺点：大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞核心级线程（KLT）：核心级线程（KLT）：没有线程库，但对核心线程工具提供API核心级线程的优点和缺点：核心级线程的优点和缺点：阻塞是在线程一级完成核心级线程的优点和缺点：核心级线程的优点和缺点：在同一进程内的线程切换调用内核，导致速度下降线程与进程的关系线程与进程的关系1:1每一执行的线程是 有自己的地址空间 和资源的唯一进程.各种UNIX版本M:1进程定义了所拥有 的地址空间和动态 资源。在该进程中 多个线程可被创建 和执行.Windows NT, Solaris, OS/2, OS/390, MACHWindows NT进程Windows NT进程以对象形式实现 一个可执行进程可包含一个或多个线程 进程和线程对象都有内建的同步能力Windows NT进程对象的属性Windows NT进程对象的属性Windows NT线程对象的属性Windows NT线程对象的属性NT线程状态NT线程状态