操作系统教程北京大学出版第四章_1

1、第四章 进程管理多道程序设计进程进程间的相互作用进程间的通信进程（线程）调度（CPU调度）系统核心线程一、多道程序设计顺序程序并发程序多道程序设计1.顺序程序程序：指令或语句序列，体现了某种算法，所有程序是顺序的顺序环境： 在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响特征：程序执行的顺序性程序执行的封闭性 独占资源，执行过程中不受外界影响程序执行结果的确定性 即：程序结果的可再现性 程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同顺序程序（续）2.并发程序并发环境： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且

2、次序不是事先确定的BAABBAAB特征：（1）程序结果的不可再现性 并发程序执行的结果与其执行的相对速度有关，是不确定的（2）在并发环境下程序的执行是间断性的 执行停执行并发程序（续1）（3）资源共享系统中资源被多个进程使用（4）独立性和制约性独立的相对速度、起始时间 进程之间可相互作用（相互制约） 可分为直接作用和间接作用（5）程序和计算不再一一对应 （计算：一个程序的执行）并发程序（续2）并发程序（续3）引入并发的目的： 引入并发是为了提高资源利用率，从而提高系统效率并发与并行概念的区别：Concurrency，parallel在顺序环境下 CPU利用率= 40/80 = 50% DEV1

3、利用率= 15/80=18.75% DEV2利用率= 25/80=31.25% t(s) t(s) CPU DEV1 DEV2 CPU CPU A 10 15 20 3040 DEV2 CPU DEV 1 DEV2 CPU B 1020 30 40 25并发程序（续4）在并发环境下 CPU利用 = 40/45=89%DEV1并发环境下利用 =15/45= 33%DEV2并发环境下利用 = 30/45=66%ABCPUDEV1DEV2CPUCPU1015203040 t(s)25DEV1CPU3545DEV2CPUDEV2并发程序（续5）3.多道程序设计（Multiprogramming） 多道

4、程序设计是指允许多个程序同时进入内存并运行，引入目的是为了提高系统效率考虑因素：在多道程序环境下如何向用户提供服务在并发程序之间如何正确传递消息（通讯）如何对CPU进行调度，保证每个用户相对公平地得到CPU（CPU是一个只可调度，不可分配的资源）如何管理其他资源 当各用户对资源使用上发生冲突时，如何处理竞争对CPU只能通过调度来解决竞争问题，而对于其他资源通过申请分配使用回收的办法进行管理，当且仅当占有CPU的时候才可以申请，否则要排队等候多道程序设计（续）二、进程进程的概念进程的状态及其转换进程控制块（Process Control Block）进程的特征进程：为了描述程序在并发执行时对系统

5、资源的共享，所需的一个描述程序执行时动态特征的概念OS 必须交替执行多个进程，以便最大程度的使用CPU，同时提供合理的响应时间OS 必须将资源分配给进程，同时避免死锁OS必须支持用户创建进程OS必须支持进程间通信1.进程的概念定义：Process 进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位进程何时创建?提交一个批处理作业用户登录由OS创建，用以向一用户提供服务( 如：打印文件) 由已存在的一进程创建一个用户程序可创建成多个进程进程何时中止?批处理作业发出暂停（Halt）指令用户退出登录进程执行一中止服务请求出错及失败因素进程中止的原因正常结束给

6、定时限到缺少内存存储器出界保护性出错例子: 写只读文件算术错超出时间进程等待超过对某事件的最大值进程中止的原因（续1）I/O 失败无效指令如试图执行数据特权指令操作系统干预如当死锁发生时父进程请求中止某一子进程父进程中止，所以子进程也中止程序与进程之间的区别：进程更能真实地描述并发，而程序不能进程是由程序和数据两部分组成的程序是静态的，进程是动态的进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的一个程序可对应多个进程，反之亦然进程具有创建其他进程的功能，而程序没有进程的分类：系统进程用户进程（系统进程优先于用户进程）2.进程的基本状态及其转换进程的三种基本状态：进程在生命消亡前处于且仅

7、处于三种基本状态之一不同系统设置的进程状态数目不同运行态（Running）：进程占有CPU，并在CPU上运行就绪态（Ready）：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行）等待态（Blocked）：阻塞态、封锁态、睡眠态指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）运行就绪等待进程的状态及其转换进程状态转换： 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换 就绪运行 运行就绪 运行等待 等待就绪进程转换就绪 - 运行调度程序选择一个新的进程运行运行 - 就绪

8、运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态进程转换（续1）运行 - 等待当一进程必须等待时OS尚未完成服务对一资源的访问尚不能进行初始化I/O 且必须等待结果等待某一进程提供输入 (IPC)等待 - 就绪当所等待的事件发生时其他状态：创建状态，终止状态挂起状态 （调节负载，对换，父进程，操作系统，终端用户）创建(新new)状态OS 已完成为创建一进程所必要的工作已构造了进程标识符已创建了管理进程所需的表格但还没有允许执行该进程 (尚未同意) 因为资源有限终止（退出exit)状态中止后进程移入该状态它不再有执行资格表格和其它信息暂时由辅助程序保留例子: 为处理用户帐单而累

9、计资源使用情况的财务程序当数据不再需要后，进程(和它的表格)被删除五状态进程模型准备退出：父进程可中止子进程七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起就绪状态(Ready)：进程在内存且可立即进入运行状态阻塞状态(Blocked)：进程在内存并等待某事件的出现阻塞挂起状态（Blocked, suspend）：进程在外存并等待某事件的出现就绪挂起状态（Ready, suspend）：进程在外存，但只要进入内存，即可运行七状态进程模型（续1）挂起（Suspend）：把一个进程从内存转到外存；可能有以下几种情况：阻塞阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源

10、时，发生这种转换，以提交新进程或运行就绪进程就绪就绪挂起：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程运行就绪挂起：对抢占式系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态七状态进程模型（续2）激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况：就绪挂起就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，发生转换阻塞挂起阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程七状态进程模型（续3）3.进程控制块（Process Con

11、trol Block）概念：系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的进程映象 (进程要素)用户程序用户数据栈用于过程调用和参数传递进程控制块PCB (进程属性)处于核心段用户进程不能直接访问、修改自己的PCB进程映象（续）对进程执行活动全过程的静态描述 由进程的用户地址空间内容、硬件寄存器内容及与该进程相关的核心数据结构组成用户级上下文：进程的用户地址空间（包括用户栈各层次），包括用户正文段、用户数据段和用户栈寄存器级上下文：程序寄存器、处理机状态寄

12、存器、栈指针、通用寄存器的值系统级上下文：静态部分（PCB和资源表格）动态部分：核心栈（核心过程的栈结构，不同进程在调用相同核心过程时有不同核心栈） PCB的内容进程描述信息：进程标识符(process ID)，唯一，通常是一个整数进程名，通常基于可执行文件名（不唯一）用户标识符(user ID)；进程组关系进程控制信息：当前状态优先级(priority)代码执行入口地址程序的外存地址运行统计信息（执行时间、页面调度）进程间同步和通信；阻塞原因PCB的内容（续）进程的队列指针进程的消息队列指针所拥有的资源和使用情况：虚拟地址空间的现状打开文件列表CPU现场保护信息：寄存器值（通用、程序计数器P

13、C、状态PSW，地址包括栈指针）指向赋予该进程的段/页表的指针PCB表： 系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度 PCB表组织方式PCB表组织方式（续）链接结构：同一状态进程的PCB组成一个链表，不同状态对应多个不同的链表就绪链表、阻塞链表 索引结构：对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址进程队列：不同状态进程分别组成队列运行队列、就绪队列、等待队列PCB表组织方式（续）索引表就绪队列等待队列 1等待队列 2PCB 1PCB 2PCB 3PCB 4PC

14、B 5PCB 6PCB 7PCB n PCB表4.进程控制 创建、撤消进程以及完成进程各状态之间的转换，由具有特定功能的原语完成 进程创建原语 进程撤消原语 阻塞原语 唤醒原语 挂起原语 激活（解挂）原语 改变进程优先级进程的创建创建一个PCB赋予一个统一进程标识符为进程映象分配空间初始化进程控制块许多默认值 (如: 状态为 New，无I/O设备或文件.)设置相应的链接如: 把新进程加到就绪队列的链表中进程撤消收回进程所占有的资源撤消该进程的PCB进程阻塞和进程唤醒 处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未

15、发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态5.进程的特征 并发性任何进程都可以同其他进程一起向前推进动态性进程对应程序的执行进程是动态产生，动态消亡的进程在其生命周期内，在三种基本状态之间转换动态的地址空间进程的特征（续1）独立性进程是资源分配的一个独立单位 例如：各进程的地址空间相互独立交互性指进程在执行过程中可能与其他进程产生直接或间接的关系异步性每个进程都以其相对独立的、不可预知的速度向前推进结构性：进程的组成：程序+数据+PCB可再入程序：可被多个进程同时调用的程序，具有下列性质：它是纯代码的，即在执行过程中自身不改变，调用它的进程应该提供数据区进程的特征（续2）三、进程

16、间的相互作用进程间的联系进程的同步机制信号量及操作（解决进程同步互斥问题）1.进程间的联系相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程（不相交进程）：在逻辑上无任何联系的进程直接作用和间接作用直接作用：进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间进程的同步（直接作用）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该

17、进程处于等待状态，获得消息后被唤醒进入就绪态例: 司机 P1 售票员 P2 while (true) while (true) 启动车辆； 关门； 正常运行； 售票； 到站停车； 开门； 进程的互斥（间接作用）由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥临界资源：critical resource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量临界区（互斥区）：critical section一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作 在进程中涉及到临

18、界资源的程序段叫临界区 多个进程的临界区称为相关临界区a := a -1 print (a)a := a +1 print (a)P1互斥P2互斥If a 0then a := a +1else a:= a-1P3互斥 进程的互斥（间接作用）使用互斥区的原则有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入无空等待：不允许两个以上的进程同时进入互斥区多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用

19、权前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程互斥的解决有两种做法:由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件软件使用互斥区的原则（续）软件解法 (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); 临

20、界区 turn = true;软件解法(3)pturn,qturn: 初值为falseP进入临界区的条件: pturn not qturnQ进入临界区的条件: 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=

21、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. 实现过于复杂，需要高的编程技巧硬件解法：提供专门的硬件指令，允许对一个字的内容进行检测和修正，或交换两个字的内容目的

22、：解决共享变量的完整性和正确性 简单、有效，特别适用于多处理机缺点：忙等待硬件解法 (1) “测试并设置”指令 boolean TS (boolean *lock) TS = *lock; *lock = true; while TS(&lock); 临界区 lock = false;硬件解法 (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;中断屏蔽方法 “开关中断”指令进入临界

23、区前执行： 执行“关中断”指令离开临界区后执行： 执行“开中断”指令简单，有效较高的代价，限制CPU并发能力（临界区小）不适应多处理器2.进程的同步机制信号量及操作 以上介绍的各种算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题 操作系统可从进程管理者的角度来处理互斥的问题，信号量就是操作系统提供的管理公有资源的有效手段进程的同步机制（续）同步机制： 信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中） 会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）同步机制应满足的基本要求：* 描述能力* 可以实现* 效率高* 使用方便进程的同步机制（续）1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test