第四章 进程管理 多道程序设计 进程 进程间的相互作用 进程间的通信 进程调度（CPU调度） 线程

4.1 多道程序设计 顺序程序 并发程序 多道程序设计

4.1.1 顺序程序 程序： 顺序环境： 在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响 指令或语句序列，体现了某种算法，所有程序是顺序的 顺序环境： 在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响

特征：程序执行的顺序性 程序执行的封闭性 独占资源，执行过程中不受外界影响 程序执行结果的确定性 即：程序结果的可再现性 程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同

4.1.2 并发程序 并发环境： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的 B A

特征： （1）程序结果的不可再现性 并发程序执行的结果与其执行的相对速度有关，是不确定的 （2）在并发环境下程序的执行是间断性的 执行——停——执行

（3）资源共享. 系统中资源被多个进程使用 （4）独立性和制约性. 独立的相对速度、起始时间 进程之间可相互作用（相互制约） （3）资源共享 系统中资源被多个进程使用 （4）独立性和制约性 独立的相对速度、起始时间 进程之间可相互作用（相互制约） 可分为直接作用和间接作用 （5）程序和计算不再一一对应 （计算：一个程序的执行）

4.1.2 并发程序 引入并发的目的： 引入并发是为了提高资源利用率，从而提高系统效率 并发与并行概念的区别： concurrency,parallel

4.1.3 多道程序设计 定义：Multiprogramming 多道程序设计是指允许多个程序同时进入内存并运行 （引入目的是为了提高系统效率） 与并发不完全是一个概念，但效果相似

考虑因素： 在多道程序环境下如何向用户提供服务 在并发程序之间如何正确传递消息（通讯） 如何对CPU进行调度，保证每个用户相对公平地得到CPU （CPU是一个只可调度，不可分配的资源）

如何管理其他资源 当各用户对资源使用上发生冲突时，如何处理竞争 对CPU只能通过调度来解决竞争问题，而对于其他资源通过申请—分配—使用—回收的办法进行管理，当且仅当占有CPU的时候才可以申请，否则要排队等候

4.1.4 与时间有关的错误 一飞机订票系统，两个终端，运行T1、T2进程 T1 : T2: ... ... 4.1.4 与时间有关的错误 一飞机订票系统，两个终端，运行T1、T2进程 T1 : T2: ... ... Read(x); Read(x); if x>=1 then if x>=1 then x:=x-1; x:=x-1; write(x); write(x);

get copy put f s t g 复制一个记录 Cobegin get; copy; put; Coend

f s t g 初始状态 3,4,...,m 2 2 (1,2) g,c,p 4,5,...,m 3 3 (1,2,3)  g,p,c 4,5,...,m 3 3 (1,2,2) X c,g,p 4,5,...,m 3 2 (1,2,2) X c,p,g 4,5,...,m 3 2 (1,2,2) X p,c,g 4,5,...,m 3 2 (1,2,2) X p,g,c 4,5,...,m 3 3 (1,2,2) X 设信息长度为m，有多少种可能性？

c p g 并行环境下程序间的制约关系

4.2 进程 进程的概念 进程的状态及其转换 进程控制块（Process Control Block） 进程的特征

OS 对进程的要求 OS 必须交替执行多个进程，以便最大程度的使用CPU，同时提供合理的响应时间 OS 必须将资源分配给进程，同时避免死锁

4.2.1 进程的概念 定义：Process 进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位

进程何时创建? 提交一个批处理作业 用户登录 由OS创建，用以向一用户提供服务( 如：打印文件) 由已存在的一进程创建 一个用户程序可创建成多个进程

进程何时中止? 批处理作业发出暂停（Halt）指令 用户退出登录 进程执行一中止服务请求 出错及失败因素

进程中止的原因 正常结束 给定时限到 缺少内存 存储器出界 保护性出错 例子: 写只读文件 算术错 超出时间 进程等待超过对某事件的最大值

进程中止的原因（续1） I/O 失败 无效指令 如试图执行数据 特权指令 操作系统干预 如当死锁发生时 父进程请求中止某一子进程 父进程中止，所以子进程也中止

程序与进程之间的区别： 进程更能真实地描述并发，而程序不能 进程是由程序和数据两部分组成的 程序是静态的，进程是动态的 进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 一个程序可对应多个进程，反之亦然 进程具有创建其他进程的功能，而程序没有

进程的分类： 系统进程 用户进程 （系统进程优先于用户进程）

4.2.2 进程的基本状态及其转换 进程的三种基本状态： 进程在生命消亡前处于且仅处于三种基本状态之一 不同系统设置的进程状态数目不同

运行态（Running）： 进程占有CPU，并在CPU上运行 就绪态（Ready）： 一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行） 等待态（Blocked）：阻塞态、挂起态、封 锁态 冻结态、睡眠态 指进程因等待某种事件的发生而暂时不能运行的状态 （即使CPU空闲，该进程也不可运行）

运行     等待 就绪 进程的状态及其转换

进程状态转换： 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换  就绪—运行  运行—就绪  运行—等待  等待—就绪

进程转换 就绪 --> 运行 运行 --> 就绪 调度程序选择一个新的进程运行 运行进程用完了时间片 运行进程被中断，因为一高优先级进程处于就绪状态

进程转换（续1） 运行 --> 等待 等待 --> 就绪 当一进程必须等待时 当所等待的事件发生时 OS尚未完成服务 对一资源的访问尚不能进行 初始化I/O 且必须等待结果 等待某一进程提供输入 (IPC) 等待 --> 就绪 当所等待的事件发生时

其他状态： 创建状态，终止状态 挂起状态 （调节负载，对换，父进程，操作系统，终端用户）

创建( 新new)状态 OS 已完成为创建一进程所必要的工作 但还没有允许执行该进程 (尚未同意) 已构造了进程标识符 已创建了管理进程所需的表格 但还没有允许执行该进程 (尚未同意) 因为资源有限

终止（退出exit)状态 中止后进程移入该状态 它不再有执行资格 表格和其它信息暂时由辅助程序保留 例子: 为处理用户帐单而累计资源使用情况的财务程序 当数据不再需要后，进程(和它的表格)被删除

五状态进程模型 准备退出：父进程可中止子进程

七状态进程模型 活动 挂起 事件 发生 等待 调度 超时 释放

新状态转换 (中期调度) 阻塞 -->阻塞挂起 阻塞挂起 --> 就绪挂起 就绪挂起-->就绪 当所有进程都阻塞，OS会安排空间让一就绪进程进入内存 阻塞挂起 --> 就绪挂起 当等待的事件发生时 (状态信息已在OS中) 就绪挂起-->就绪 当内存中没有就绪进程时 就绪-->就绪挂起 (较少见) 当没有被阻塞的进程，而为了性能上的考虑，必须释放一些内存时

4.2.3 进程控制块 （Process Control Block） 概念： 系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志 进程与PCB是一一对应的

进程映象 (进程要素) 用户程序 用户数据 栈 进程控制块PCB (执行上下文) 用于过程调用和参数传递 控制进程所需的数据(进程属性)，包括: 进程标识符信息 处理器状态信息 进程控制信息

PCB的内容： 调度信息： 进程名；进程的内部标识；用户名；进程状态；进程优先级；进程的存储信息（起始地址，长度）；进程资源清单；进程家族关系；进程的队列指针；进程的消息队列指针；进程当前打开的文件… ... 现场信息： 记录了重要的寄存器；(虚)时钟等内容

进程标识符 (在PCB中) 可使用一些数字标识符 统一进程标识符 (必然的) 用户标识符 创建本进程的某个进程的标识符 索引至 (直接或间接) 主进程表 用户标识符 与某个作业对应的用户 创建本进程的某个进程的标识符

处理器状态信息 (在PCB中) 处理器寄存器内容 程序状态字 (PSW) 用户可见寄存器 控制和状态寄存器 栈指针 包含状态信息 例子: 在Pentium机中的EFLAGS寄存器

进程控制信息 (在PCB中) 调度和状态信息 数据结构信息 进程状态 (如: 运行，就绪，阻塞...) 进程优先级 该进程在等待的事件 (若被阻塞) 数据结构信息 进程可能需要有指向其他PCB的指针, 父-子进程关系及其它结构

进程控制信息 (在PCB中) 进程间通信 进程特权 存储管理 所拥有的资源和使用情况 IPC可能需要标志和信号 如: 访问特定的内存地址... 存储管理 指向赋予该进程的段/页表的指针 所拥有的资源和使用情况 使用中的资源: 打开的文件，I/O设备... (CPU , I/O...)的时间使用史

执行的方式 为了提供对PCB (和OS其它数据)的保护，多数处理器支持至少两种执行方式: 特权方式 (又称作系统方式，内核方式，管理方式,控制方式) 操作控制寄存器,基本 I/O指令， 存储管理... 用户方式 为此， CPU提供一个(或一些)方式位，这些二进制位只能被中断、陷阱或OS调用所设置

系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 （注：多道程序中的多道与系统并发度不同）

PCB表组织方式： 常用索引方式，对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址 （其他方式：线性表或链表） 进程队列：不同状态进程分别组成队列 运行队列、就绪队列、等待队列

进程控制块（Process Control Block） PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCBn ...... 空 PCB 运行态 就绪态 等待1 等待2 6 7 5 10 15

4.2.4 进程控制 创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。 进程创建原语 进程撤消原语 阻塞原语 唤醒原语 挂起原语 激活（解挂）原语

进程的创建 创建一个PCB 赋予一个统一进程标识符 为进程映象分配空间 初始化进程控制块 设置相应的链接 许多默认值 (如: 状态为 New，无I/O设备或文件...) 设置相应的链接 如: 把新进程加到就绪队列的链表中

进程撤消 收回进程所占有的资源 撤消该进程的PCB

进程阻塞 处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态 进程唤醒

4.2.5 进程的特征 并发性 任何进程都可以同其他进程一起向前推进 动态性 进程对应程序的执行 进程是动态产生，动态消亡的 进程在其生命周期内，在三种基本状态之间转换

独立性. 进程是资源分配的一个独立单位 交互性. 指进程在执行过程中可能与其它进程产生直接或间接的关系 异步性 独立性 进程是资源分配的一个独立单位 交互性 指进程在执行过程中可能与其它进程产生直接或间接的关系 异步性 每个进程都以其相对独立的、不可预知的速度向前推进

结构性： 进程的组成：程序+数据+PCB 可再入程序： 可被多个进程同时调用的程序，具有下列性质： 它是纯代码的，即在执行过程中自身不改变，调用它的进程应该提供数据区

【思考题】 1．如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？ 2. 有没有这样的状态转换，为什么？ 等待—运行； 就绪—等待 3. 一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能 4. 举3个日常生活中类似进程的例子

4.3 进程间的相互作用 进程间的联系 进程的同步机制──信号量及P.V操作（解决进程同步互斥问题）

4.3.1 进程间的联系 相交进程与无关进程 相交进程：指多个并发进程在逻辑上有某种联系 无关进程（不相交进程）：在逻辑上无任何联系的进程

直接作用和间接作用 直接作用： 进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间 间接作用： 进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间

相互感知程度 交互关系 一个进程对其他进程的影响 相互不感知(完全不了解其它进程的存在) 竞争(competition) 一个进程的操作对其他进程的结果无影响 间接感知(双方都与第三方交互，如共享资源) 通过共享进行协作 一个进程的结果依赖于从其他进程获得的信息 直接感知(双方直接交互，如通信) 通过通信进行协作

进程的同步（直接作用） 进程的同步：synchronism 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态

例: 司机 P1 售票员 P2 while (true) while (true) { { 启动车辆； 关门； 正常运行； 售票； 到站停车； 开门； } }

进程的互斥（间接作用）mutual exclusion 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥 临界资源：critical resource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量

临界区（互斥区）：critical section 一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作 在进程中涉及到临界资源的程序段叫临界区 多个进程的临界区称为相关临界区

（间接作用） 进程的互斥 P1 互斥 P2 互斥 a := a +1 print (a) a := a -1 print (a) If a < 0 then a := a +1 else a:= a-1 P3 互斥 进程的互斥 （间接作用）

使用互斥区的原则： 有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入 无空等待：不允许两个以上的进程同时进入互斥区 多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待 有限等待：任何进入互斥区的要求应在有限的时间内得到满足 让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权

硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高） 软件（用编程解决，但常常忙等待 ） 使用互斥区的原则： 前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定 进程互斥的解决有两种做法: 由竞争各方平等协商 引入进程管理者，由管理者来协调竞争各方对互斥资源的使用 具体方法： 硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高） 软件（用编程解决，但常常忙等待 ）

进程互斥的软件方法 通过平等协商方式实现进程互斥的最初方法是软件方法 其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志 其中的主要问题是设置什么标志和如何检查标志

软件解法 (1) free: 表示临界区标志 true: 有进程在临界区 false:无进程在临界区(初值) .... while (free); free = true; 临界区 free = false;

软件解法 (2) turn: true P进入临界区 false Q进入临界区 .... P: while (not turn); 临界区 turn = false; Q: while (turn); turn = true;

软件解法(3) pturn,qturn: 初值为false P进入临界区的条件: pturn∧ not qturn Q进入临界区的条件: not pturn∧ qturn P .... Q ..... pturn = true; qturn = true; while (qturn); while (pturn); 临界区 临界区 pturn = false; qturn = false; ... ...

软件解法(4) : Dekker算法 在解法(3)基础上引入turn枚举类型 初值任意 P : while (true) { pturn = true; while (qturn) { if (turn==2) { pturn = false; while (turn==2)； pturn = true; } 临界区 turn = 2; pturn = false; ..... }

软件解法(4)（续1） Q : while (true) { qturn = true; while (pturn) { if (turn==1) { qturn = false; while (turn==1)； qturn = true; } 临界区 turn = 1; qturn = false; ..... }

软件解法的缺点： 1. 忙等待 2. 实现过于复杂，需要高的编程技巧

硬件解法 (1) “测试并设置”指令 boolean TS (boolean *lock) while TS(&lock); { 硬件解法 (1) “测试并设置”指令 boolean TS (boolean *lock) { boolean old; old = *lock; *lock = true; return old; } while TS(&lock); 临界区 lock = false;

硬件解法 (2) “交换”指令 key = true; do { SWAP(&lock,&key); }while(key); 临界区 硬件解法 (2) “交换”指令 void SWAP(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } key = true; do { SWAP(&lock,&key); }while(key); 临界区 lock:=false;

硬件解法 (3) “开关中断”指令 进入临界区前执行： 执行“关中断”指令 离开临界区后执行： 执行“开中断”指令

4.3.2 进程的同步机制── 信号量及P.V操作（解决进程同步） 同步机制： 信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中） 会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）

同步机制应满足的基本要求： * 描述能力 * 可以实现 * 效率高 * 使用方便

信号量：semaphore 是一个数据结构 定义如下： struct semaphore { int value; pointer_PCB queue; } 信号量说明： semaphore s;

P、V操作 P(s) { s.value = s.value --; if (s.value < 0) 该进程状态置为等待状态 将该进程的PCB插入相应的等待队列末尾s.queue; }

P、V操作 V(s) { s.value = s.value ++; if (s.value < = 0) 唤醒相应等待队列s.queue中等待的一个进程 改变其状态为就绪态 并将其插入就绪队列 }

P、V操作为原语操作 原语：primitive or atomic action 是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性 即原语的执行必须是连续的，在执行过程中不允许被中断 实现：开关中断

信号量的使用： 必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作

用P、V操作解决进程间互斥问题 P(mutex) V(mutex) P1 P2 P3 互斥区

经典的生产者─消费者问题 生产者 消费者

经典的生产者─消费者问题 同步问题： P进程不能往“满”的缓冲区中放产品，设置信号量为S1 Q进程不能从“空”的缓冲区中取产品，设置信号量S2

S1初值为1，S2初值为0 P： Q： while (true) { while (true) { 生产一个产品; P(s2); 送产品到缓冲区; V(s1); V(s2); 消费产品; }; }; S1初值为1，S2初值为0

多个缓冲区的生产者和消费者 P： i = 0; while (true) { 生产产品; P(S1); 往Buffer [i]放产品; V(S2); i = (i+1) % n; }; Q： j = 0; while (true) { P(S2); 从Buffer[j]取产品; V(S1); 消费产品; j = (j+1) % n; };

【思考题】要不要对缓冲区（临界资源）进行互斥操作？

n个缓冲区、m个生产者和k个消费者 P： i = 0; while (true) { 生产产品; P(S1); P(mutex); 往Buffer [i]放产品; V(mutex); V(S2); i = (i+1) % n; }; Q： j = 0; while (true) { P(S2); P(mutex); 从Buffer[j]取产品; V(mutex); V(S1); 消费产品; j = (j+1) % n; }; 有错误？若颠倒两个P操作的顺序？

n个缓冲区、m个生产者和k个消费者 P： i = 0; while (true) { 生产产品; P(S1); P(mutex1); 往Buffer [i]放产品; i = (i+1) % n; V(mutex1); V(S2); }; Q： j = 0; while (true) { P(S2); P(mutex2); 从Buffer[j]取产品; j = (j+1) % n; V(mutex2); V(S1); 消费产品; }; 正确

P.V操作讨论 1) 信号量的物理含义： S>0表示有S个资源可用 S=0表示无资源可用 P(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应该大于等于0

2) P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前 而两个V操作无关紧要

3）P.V操作的优缺点 优点： 简单，而且表达能力强（用P.V操作可解决任何同步互斥问题） 缺点： 不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂

信号量集——AND型信号量集 AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配 AND型信号量集P原语为Swait AND型信号量集V原语为Ssignal

Swait(S1, S2, …, Sn) //P原语； { 调用进程进入第一个小于1信号量的等待队列Sj.queue; 阻塞调用进程; while (TRUE) { if (S1 >=1 && S2 >= 1 && … && Sn >= 1) { //满足资源要求时的处理； for (i = 1; i <= n; ++i) -–Si; //注：与P的处理不同，这里是在确信可满足 // 资源要求时，才进行减1操作； break; } else { //某些资源不够时的处理； 调用进程进入第一个小于1信号量的等待队列Sj.queue; 阻塞调用进程;

Ssignal(S1, S2, …, Sn) { for (i = 1; i <= n; ++i) ++Si; //释放占用的资源； for (在Si.queue中等待的每一个进程P) //检查每种资源的等待队列的所有进程； 从等待队列Si.queue中取出进程P;

if (判断进程P是否通过Swait中的测试) //注：与signal不同，这里要进行重新判断； {//通过检查（资源够用）时的处理； 进程P进入就绪队列; } else {//未通过检查（资源不够用）时的处理； 进程P进入某等待队列；

一般“信号量集” 一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理 一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请

测试值为ti（表示信号量的判断条件，要求Si >= ti；即当资源数量低于ti时，便不予分配） 占用值为di（表示资源的申请量，即Si = Si - di） 对应的P、V原语格式为： Swait(S1, t1, d1; ...; Sn, tn, dn); Ssignal(S1, d1; ...; Sn, dn);

一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况： Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配 Swait(S, 1, 1)表示互斥信号量 Swait(S, 1, 0)可作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区）

【思考题】 1.用P.V操作解决下图之同步问题: get copy put f s t g

用P.V操作解决司机与售票员的问题 司机进程： while (true){ 启动车辆 正常驾驶 到站停车 }… 售票员进程： 关门 售票 开门

4.3.3 IPC经典问题 1.读者写者问题 有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作

第一类：读者优先 如果读者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待

第一类读者写者问题的解法 写者： while (true) { P(w); 写 V(w); }; 读者： while (true) { P(mutex); readcount ++; if (readcount==1) P (w); V(mutex); 读 readcount --; if (readcount==0) V(w); }; 写者： while (true) { P(w); 写 V(w); };

2.哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子

#define N 5 void philosopher (int i) { while (true) { 思考； 取fork[i]; 取fork[(i+1) % 5]； 进食； 放fork[i]; 放fork[(i+1) % 5]； }

为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿

哲学家就餐问题解法 #define N 5 #define THINKING 0 #define HUNGRY 1 #define EATING 2 #typedef int semaphore; int state[N]; semaphore mutex=1; semaphore s[N];

void test(int i) { if (state[ i ] == HUNGRY) && (state [ (i-1) % 5] != EATING) && (state [ (i+1) % 5] != EATING) state[ i ] = EATING; V(&s[ i ]); }

放左筷子； 放右筷子； P(&mutex) state[ i ] = THINKING； test([i-1] % 5); void philosopher (int i) { while (true) { 思考; P(&mutex); state[i] = HUNGRY; test(i); V(&mutex); P(&s[i]); 拿左筷子； 拿右筷子； 进食； 放左筷子； 放右筷子； P(&mutex) state[ i ] = THINKING； test([i-1] % 5); test([i+1] % 5); V(&mutex); } state[ i ] = THINKING s[ i ] = 0

【作业】 1. 推广例子中的消息缓冲问题。 消息缓冲区为k个，有1个发送进程， n个接收进程，每个接收进程对发送来的消息都必须取一次 若有m个发送进程呢？

2.第二类读者写者问题： 写者优先 条件： 1）多个读者可以同时进行读 2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行） 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）

3.理发师睡觉问题 理发店里有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子 如果没有顾客,则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先唤醒理发师 如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开

4.4 进程通信 概述 消息缓冲通信方式

4.4.1 概述 P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息 如果要在进程间传递大量信息则要用Send / Receive原语（高级通讯原语）

进程通信的方式 共享内存： 相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换

消息传递： 系统为进程提供了两个高级通讯原语send和receive send： 当要进行消息传递时执行send receive：

消息传递模式 消息缓冲 在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传递来的缓冲区 信箱通信

直接方式： 发送进程发消息时要指定接收进程的名字， 反过来，接收时要指明发送进程的名字 Send(receiver,message) Receiver(sender,message) * 对称形式：一对一 * 非对称形式：多对一 （顾客/服务员） 有缓冲（有界，无界），无缓冲

间接方式： 发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信 发送原语：send(MB,Message) 接收原语：receive(MB,Message)

4.4.2 消息缓冲 （有界缓冲区原理）： 在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行send系统调用，产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行

4.4.2 消息缓冲（续1） （有界缓冲区原理）： 在以后某个时刻，当接收进程执行到receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行

发送进程 S 接受进程 R 消息 ...... PCB N: M: ...... 消息链指针 ...... ...... Send(R, M) SIZE:消息长度 TEXT:消息正文 ...... Receive(pid, N) SIZE:消息长度 TEXT:消息正文 N: M:

消息缓冲区结构： 消息长度 消息正文 发送者 消息队列指针

用P.V操作来实现Send原语: Send（R，M） P(m-mutex); Begin 把缓冲区挂到接收进程 如果没找到出错返回; V(m-mutex); 申请空缓冲区P（s-b）； V(s-m); P(b-mutex); END 摘空缓冲区; V(b-mutex); 把消息从M处copy到空缓冲区; 其中s-b初值:n ;s-m初值:0

4.4.3 信箱通信 信箱组成 信箱说明 与 信箱体 可存放信件数，已存放信件数，指针 信箱使用规则 若发送信件时信箱已满，则发送进程被置为“等信箱”状态，直到信箱有空时才被释放 若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被释放

4.4.3 信箱通信（续1） Send实现 send（N，M）：把信件M送到指定的信箱N中 步骤： 查找指定信箱N； 若信箱已满置发送信件进程为“等信箱”状态；

4.4.3 信箱通信（续2） Receive实现 receive（N，X）：从指定信箱N中取出一封信，存放到指定的地址X中 步骤： 若信箱中无信件则置接收信件进程“等信件”状态；

4.4.3 信箱通信（续3） 应用实例 磁盘管理进程：从信箱中收取信件，处理，启动磁盘工作 其他进程：要求访问磁盘，向磁盘管理进程发一封信

4.4.4 管道通信方式 Pipe 也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质 发送进程 接收进程 字符流方式写入读出 先进先出顺序

4.5 进程调度（CPU调度） 要解决的问题 WHAT：按什么原则分配CPU —进程调度算法 WHEN：何时分配CPU —进程调度的时机 HOW： 如何分配CPU —CPU调度过程（进程的上下文切换）

处理机调度分成三个层次 处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度

高级调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天 中级调度涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问 低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效

4.5.1 进程调度算法 1．进程调度 进程调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程

2．确定算法的原则 具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量

3．各种进程调度算法 先进先出进程调度算法（FIFO） 按照进程就绪的先后次序来调度进程 优点:实现简单 缺点:没考虑进程的优先级

基于优先数的调度 （HPF—Highest Priority First） 优先选择就绪队列中优先级最高的进程投入运行 优先级根据优先数来决定

确定优先数的方法 静态优先数法： 在进程创建时指定优先数，在进程运行时优先数不变 动态优先数法： 在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变

两种占用CPU的方式 可剥夺式（可抢占式Preemptive）： 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去

时间片轮转程序调度算法 (RR—Round Robin) 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行

分时系统中常用时间片轮转法 时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力

多队列反馈调度算法： 将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.....当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列

* 首先系统中设置多个就绪队列 * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大 * 各个队列按照先进先出调度算法 * 一个新进程就绪后进入第一级队列 * 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列 * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾 * 当第一级队列空时，就去调度第二级队列，如此类推 * 当时间片到后，进程放弃CPU，回到下一级队列

4.5.2 进程调度的时机 当一个进程运行完毕，或由于某种错误而终止运行 当一个进程在运行中处于等待状态（等待I/O） 分时系统中时间片到 当有一个优先级更高的进程就绪（可抢占式） 例如：新创建一个进程，一个等待进程变成就绪 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语）

4.5.3 进程切换 进程切换 一个进程让出处理器，由另一个进程占用处理器的过程 进程的切换使系统中的各进程均有机会占用CPU 进程的切换是由进程状态的变化引起的，而进程状态的变化又与出现中断事件有关 当有中断事件发生时，当前运行的进程被中断，中断响应后由操作系统处理出现的中断事件。中断处理后，某些进程的状态会发生变化，也可能又创建了一些新的进程。因此，要进行队列的调整。然后，进程调度根据预定的调度算法从就绪队列选一个进程占用CPU。这个占用CPU运行的进程可能仍是被中断的进程，也可能是另一个进程

何时切换进程? 只要OS取得对CPU的控制，进程切换就可能发生，如: 超级用户调用 陷阱 中断 来自程序的显式请求 (如：打开文件)， 该进程通常会被阻塞 陷阱 最末一条指令导致出错，会引起进程移至退出状态 中断 外部因素影响当前指令的执行，控制被转移至IH（中断处理程序）

中断的例子 时钟 I/O 存储器因素 进程用完其时间片，被转换至就绪状态 先前等待该事件的进程被转换为就绪(或就绪挂起)状态 然后重新运行该进程或选择一更高优先级的进程 存储器因素 内存地址是在虚拟存储器中，它必须把对应的存储块调入主存 于是相应的进程成为阻塞状态(等待I/O完成)

4.5.4 CPU调度过程 * 保存现场：顺序保存，最后一步保存PSW * 选择要运行的程序 （如果没有就绪进程,系统会安排一个闲逛进程(idle),没有其他进程时该进程一直运行,在执行过程中可接收中断） * 恢复现场：最后一步恢复选中进程的PSW

在进程（上下文）中切换的步骤 保存处理器的上下文，包括程序计数器和其它寄存器 用新状态和其它相关信息更新正在运行进程的PCB 把原来的进程移至合适的队列-就绪、阻塞 选择另一个要执行的进程 更新被选中进程的PCB 从被选中进程中重装入 CPU 上下文

4.6 系统核心 系统核心： 向上提供多个无中断的虚拟机器 在核心内不允许中断 特点：* 为进程运行提供一个舞台 * 核心常驻内存 * 设计短小精焊

4.6.1 核心的组成 中断处理 进程管理: 调度 控制 通讯 互斥 同步等 原语管理: 在核心中提供一系列原语，同步,通信，创建，撤消等

队列管理: 队列数据结构:指向队首的表指针 三个队列: 运行，就绪，等待队列 排队方式: 排队首 排队尾 插 队 出队方式: 队首出队/队中出队 队列管理: 中断之后，进程调度之前

现场管理: 保存现场;注意顺序,中断之后第一步 恢复现场:恢复时机，进程调度最后一步 时钟管理: 以固定频率 +1 -1 用途:进入绝对时钟 间隔时钟 进行分析比较

虚时钟: 每个进程分配给一个虚时钟来记录CPU时间,这个时钟称为虚时钟 虚时钟存放在PCB中，属于现场的一部分，进程运行时，将虚时钟放入内存开辟的专门单元，离开CPU则放在 PCB中

4.6.2 核心处理流程 进入核心的唯一入口:中断 中断后进入核心，由硬件完成

4.6.3 内核的执行特点 由中断驱动的: 中断→内核→退出 内核执行是连续的 内核执行过程中在中断屏蔽状态下 内核使用特权指令

4.7 线程的基本概念 线程的引入 线程与进程的对比 线程的实现 实例：Solaris

给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，I/O设备），有状态、优先级、调度 4.7.1 线程的引入 进程的两个基本属性： 资源的拥有者： 给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，I/O设备），有状态、优先级、调度 调度单位： 进程是一个执行轨迹 以上两个属性构成进程并发执行的基础

4.7.1 线程的引入（续1） 系统必须完成的操作： 创建进程 撤消进程 进程切换 缺点： 时间空间开销大，限制并发度的提高

4.7.1 线程的引入（续2） 在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制 线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度

4.7.1 线程的引入（续3） 线程：有时称轻量级进程 进程中的一个运行实体 是一个CPU调度单位 资源的拥有者还是进程或称任务 将原来进程的两个属性分开处理

4.7.1 线程的引入（续4） 线程： 有执行状态（状态转换） 不运行时保存上下文 有一个执行栈 有一些局部变量的静态存储 可存取所在进程的内存和其他资源 可以创建、撤消另一个线程

线程和进程： 单进程、单线程 单进程、多线程 多进程、一个进程一个线程 多进程、一个进程多个线程

包含了寄存器映像，线程优先数和线程状态信息 P C B 用 户 栈 单线程进程模型 用户地址空间 核 心 线程控制块： 包含了寄存器映像，线程优先数和线程状态信息

P C B 多线程进程模型 用户 地址 空间 用 户 栈 核 心 线程 控制块

引入线程的好处： 创建一个新线程花费时间少（结束亦如此） 两个线程的切换花费时间少 （如果机器设有“存储[恢复]所有寄存器”指令，则整个切换过程用几条指令即可完成） 因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核 适合多处理机系统

例子1： LAN中的一个文件服务器，在一段时间内需要处理几个文件请求 因此有效的方法是：为每一个请求创建一个线程 在一个SMP机器上：多个线程可以同时在不同的处理器上运行

例子2： 一个线程显示菜单，并读入用户输入； 另一个线程执行用户命令 考虑一个应用：由几个独立部分组成，这几个部分不需要顺序执行，则每个部分可以以线程方式实现 当一个线程因I/O阻塞时，可以切换到同一应用的另一个线程

4.7.2 线程与进程的比较 调度 并发性 拥有资源 系统开销

4.7.3 线程的实现机制 用户级线程 核心级线程 两者结合方法

一、用户级线程（User Level Thread） 由应用程序完成所有线程的管理 通过线程库(用户空间) 一组管理线程的过程 核心不知道线程的存在 线程切换不需要核心态特权 调度是应用特定的

线程库 创建、撤消线程 在线程之间传递消息和数据 调度线程执行 保护和恢复线程上下文

对用户级线程的核心活动 即线程状态是与进程状态独立的 核心不知道线程的活动，但仍然管理线程的进程的活动 当线程调用系统调用时，整个进程阻塞 但对线程库来说，线程仍然是运行状态 即线程状态是与进程状态独立的

用户级线程的优点和缺点 优点： 线程切换不调用核心 调度是应用程序特定的：可以选择最好的算法 ULT可运行在任何操作系统上（只需要线程库） 缺点： 大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞 核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上

二、核心级线程（KLT） 所有线程管理由核心完成 没有线程库，但对核心线程工具提供API 核心维护进程和线程的上下文 线程之间的切换需要核心支持 以线程为基础进行调度 例子：Windows NT，OS/2

核心级线程的优点和缺点 优点： 对多处理器，核心可以同时调度同一进程的多个线程 阻塞是在线程一级完成 核心例程是多线程的 缺点： 在同一进程内的线程切换调用内核，导致速度下降

三、两者分析 针对不同的操作系统 开销和性能（线程的调度和切换速度） 系统调用（阻塞） 线程执行时间 灵活性 可扩充性 抢占CPU 共享进程的资源

四、ULT和KLT结合方法 线程创建在用户空间完成 大量线程调度和同步在用户空间完成 程序员可以调整KLT的数量 可以取两者中最好的 例子：Solaris

4.7.4 实例：Solaris 进程： 用户地址空间 用户栈 进程控制块

实例：Solaris（续1） 用户级线程（线程库）： 可在应用进程中建立多个ULT 每个ULT需要：栈、程序计数器 不受调度程序的调度，线程切换快 对操作系统不可见 提供应用程序并行性接口

实例：Solaris（续2） 核心级线程： 设置了大量KLT 有一个小的数据结构和栈 完成内核的所有工作 调度处理器的单位，其结构由核心维护

实例：Solaris（续3） 轻型进程（LWP）： 每个ULT利用LWP与内核通信 每个LWP对应用程序可见，内核看到的是多个LWP而看不到ULT

Solaris： 如果逻辑并行性不需要硬件并行性的支持，则可使用ULT 例子：多个窗口，任一时刻只有一个窗口是活跃的 如果内核级线程可能被阻塞，则可以指定两个或多个LWP，避免整个应用程序的阻塞

分派 唤醒 继续 抢占 停止 可运行 睡眠 用户级线程 活跃 连接在LWP上

LWP状态独立于状态ULT（受限制ULT除外） 分派 唤醒 继续 时间片 或抢占 停止 运行 阻塞 系统 调用 轻型进程状态 LWP状态独立于状态ULT（受限制ULT除外） 可运行

进程 1 进程 2 进程 3 进程 4 进程 5 进程库 用户 内核 硬件 用户级线程 内核级线程 轻型线程 处理器

线程与进程的关系 线程：进程 特点 例子 各种UNIX版本 1:1 每一执行的线程是 有自己的地址空间 和资源的唯一进程. M:1 进程定义了所拥有 的地址空间和动态 资源。在该进程中 多个线程可被创建 和执行. Windows NT, Solaris, OS/2, OS/390, MACH