操作系统原理与实例分析PPT课件第二章 进程管理.ppt

第二章第二章 进程管理进程管理 2.1 2.1 进程的引入进程的引入 2.1.1 2.1.1 程序顺序执行与并发执行程序顺序执行与并发执行 程序的执行顺序程序的执行顺序 1程序的顺序执行 例子： S1：a： x+y； S2：b： a-5； S3：c： b+1； 2程序顺序执行时的特征 （1）顺序性：处理机的操作严格按照程 序所规定的顺序执行。 （2）封闭性：程序运行时独占全机资源 ，程序一旦开始执行，其执行结果不受 外界因素影响。 （3）可再现性：只要程序执行时的环境 和初始条件相同，都将获得相同的结果 。 （不论它是从头到尾不停顿地执行，还是 “停停走走”地执行） 3. 程序的并发执行 4. 程序并发执行时的特征 1）间断性:由于它们共享系统资源，以及为完 成同一项任务而相互合作，致使在这些并发 执行的程序之间，形成了相互制约的关系。 相互制约将导致并发程序具有“执行暂停 执行”这种间断性的活动规律。 2）失去封闭性: 是多个程序共享系统中的各种 资源，因而这些资源的状态将由多个程序来 改变，致使程序的运行已失去了封闭性。 3）不可再现性: 程序在并发执行时，由于失 去了封闭性，导致不可再现性 。 例如，有两个循环程序A和已它们共享 一个变量N。程序A每执行一次时，都 要做N：=N1操作；程序B每执行一 次时，都要执行Print（N）操作，然后 再将N置成“0”。程序A和B以不同的速 度运行。这样，可能出现其计算结果不 可再现性，亦即，程序经过多次执行后 ，虽然它们执行时的环境和初始条件相 同，但得到的结果却各不相同。 例子：变量X为共享变量，程序1和程序2都要对X进 行访问，当两个程序执行的速度变化时可得到不 同的结果。 执行顺序1：程序1程序2 结果为：X增加2。 执行顺序2： R1=X; R2=X; R1=R1+1; R2=R2+1; X=R1; X=R2 结果为： X 增加1。 还可有许多其它组合 程序2 R2=X R2=R2+1 X=R2 程序1 R1=X R1=R1+1 X=R1 目 标 程 序 并发执行的条件：达到封闭性和可再现性并发执行的条件：达到封闭性和可再现性 并发执行失去封闭性的原因是共享资源的影 响，去掉这种影响就行了。1966年，由 Bernstein 给出并发执行的条件。 程序 P(i) 针对共享变量的读集和写集 R(i)和W(i) 条件：任意两个程序P(i)和P(j)，有： R(i)W(j)=; W(i)R(j)=; W(i)W(j)=; 前两条保证一个程序的两次读之间数据不变化；最 后一条保证写的结果不丢掉。 现在的问题是这个条件不好检查。 并发和并行区别并发和并行区别 并发是指在某一时间间隔内计算机系统 中存在着多个程序活动。 并行是指在同一时刻计算机内有多个程 序都在执行，这只有在多CPU的系统中才能 实现。在单CPU的计算机系统中，多个程序 是不可能同时执行的。并发是从宏观上（这 种“宏观”也许不到一秒的时间）看多个程序 的运行活动，这些程序在串行的、交错的运 行，由操作系统负责这些程序之间的运行切 换，人们从外部宏观上观察，有多个程序都 在系统中运行。 2.1.2 2.1.2 进程的概念和特征进程的概念和特征 1、进程的定义 进程是一个具有一定独立功能的程 序关于某个数据集合的一次运行活动， 是系统进行资源分配和调度的基本单位 。 进程与程序的区别和相互关系进程与程序的区别和相互关系 程序 进程 静态的指令序列 动态的程序执行过程 一程序可对应 一个进程对应至少有 多个进程 一个程序在工作 永久性软件资源 暂存资源, 动态产生过程 资源分配和调度的单位 2、进程的特征 动态性动态性：进程是程序在并发系统内的一次执行， 一个进程有一个从产生到消失的生命期，是进程 的最基本的特征； 并发性并发性：正是为了描述程序在并发系统内执行的 动态特性才引入了进程，没有并发就没有进程， 是进程的最重要的特征，正是因为并发性，才提 高了系统资源的利用率和系统的吞吐量； 独立性独立性：每个进程的程序都是相对独立的顺序程 序，可以按照自己的方向和速度独立地向前推进 ； 异步性异步性：指进程的执行进度，或推进速度不可预 测，而与同时驻留在内存的其它进程有关； 制约性制约性：进程之间的相互制约，主要表现在互斥 地使用资源和相关进程之间必要的同步和通讯； 结构性结构性：进程 = PCB + 程序 + 数据集合 3、引入进程后需要解决的问题 * *增加了空间开销增加了空间开销 * *额外的时间开销额外的时间开销 * *更难控制更难控制 * *处理机的竞争尤为突出处理机的竞争尤为突出 2.1.3 2.1.3 进程的结构进程的结构 为了刻画进程的动态变化，通常把 进程表示为由程序段、私有数据块和进 程控制块（PCB）组成。进程控制块是进程控制块是 操作系统感知进程存在的唯一标志操作系统感知进程存在的唯一标志。 程序部分描述进程本身所要完成的 功能，而“私有数据块”是接受程序规定 操作的一组存储单元的内容，是操作的 对象。进程控制块是在进程创建时产生 的，当进程存在于系统时（运行），进 程控制块就标识了这个进程。 PCB包含了进程的描述信息和控制信息，通常有如下项 目： (1) 标识符 (2) 存贮信息 (3) 现场状态 (4) 优先数 (5) 现场信息 (6) 链接字(或称队列指针) (7) 族系关系 (8) 资源清单 (9) 其他 * 标识符 分为外部标识符和内部标识符。外部标 识符由创建进程者提供，通常由字母、数字 等组成，在用户或其它进程访问该进程时使 用。内部标识符是一个整数。在操作系统的 PCB表区中，有多个PCB表，每个PCB表有一个 序号，通常将这个序号做为内部标识符，以 方便系统使用。 * 程序地址 进程的程序部分在内存及外存的地址， 或描述程序地址信息的段表地址、页表地址 等。 * 数据地址 进程的数据部分在内存及外存的地址， 或描述数据地址信息的段表地址、页表地址 等。 * 状态 进程当前所处的状态，即就绪状态、执 行状态及阻塞状态，已经被创建的进程的状 态必为此三者之一。 * CPU状态保护区 CPU状态信息主要由通用寄存器、程序计 数器PC、程序状态字PSW以及用户栈指针等组 成，也称为中断点现场信息。CPU状态保护区 用以保护进程被中断而暂停执行时CPU的状态 信息，以便进程重新获得CPU时能够重布现场 ，从上次被中断处继续执行。 * 进程优先级 进程优先级是用以描述进程使用处理机 的优先级别的整数，是优先级调度算法中调 度的依据。通常数值越小，优先级别越高。 优先级可以处理成不变的，称为静态优先级 ，也可以处理成可变的，称为动态优先级。 * 通信信息 进程通信时需要使用的信息，包括标志 位、信号或信号量、消息队列信息等。如消 息缓冲通信机制中，在进程的PCB表中，需要 有消息队列队首指针、消息个数及互斥使用 消息队列的信号量等。 * 资源信息 进程对资源的需求及已经分配资源的清 单。 * 队列指针 除了执行状态的进程外，其余的进程PCB 表都处于某一就绪队列或某一阻塞队列中。 队列指针用于指向进程所在队列中下一个PCB 表的首地址。 * 家族指针 进程在运行过程中可以创建新进程来协 同完成同一任务。创建者称为父进程，被创 建者称为子进程。父进程PCB表中有指向子进 程的PCB表的指针，子进程的PCB表中有指向 父进程的PCB表的指针，这就是家族指针，它 可以将一个家族的进程联系起来，形成进程 家族树。 进程控制块的组织进程控制块的组织 为了便于管理，系统把所有的PCB用适 当方式组织起来。一般说来，大致有以下三 种组织方式： (1) 线性表方式 (2) 索引方式 (3) 链接方式 2.2 2.2 进程的状态进程的状态 2.2.1 2.2.1 进程执行轨迹进程执行轨迹 例 假设内存中有3个进程A、B、C，他 们的程序代码已全部装入内存。若A、C 两进程需要执行12条指令，B进程需要 执行4条指令，且B进程执行到第4条指 令处必须等待I/O 2.2.2 2.2.2 两状态进程模型两状态进程模型 在两状态模型中进程可能处于如下 两种状态中： 执行 (Running ） 非执行（ Not-running ） 两状态队列模型两状态队列模型 进程的创建进程的创建 事 件说 明 新的批作业通常位于磁带或磁盘中的批作业控制流被提供给 操作系统。当操作系统准备接纳新工作时。它将 读取下一个作业控制命令 交互登录 终端用户登录到系统 操作系统因为 提供一项服务 而创建 操作系统可以创建一个进程，代表用户程序执行 一个功能，使用户无需等待（如控制打印的进程 ） 由现有的进程 生成 基于模块化的考虑，或者为了开发并行性，用户 程序可以规定许多进程的创建 进程的终止进程的终止 事件说明 正常完成进程自行执行一个操作系统服务调用，表示它已经结 束运行 超过时限 进程运行时间超过规定的时限。可以测量很多种类型的时间 ，包括总的运行时间（“挂钟时间”）。花费在执行上的时间 以及对于交互进程从上一次用户输入到当前时刻的时间总量 无可用存储器系统无法满足进程需要的存储器空间 越界 进程试图访问不允许访问的存储器单元 保护错误进程试图使用不允许使用的资源或文件，或者试图以 一种不正确的方式使用，如往只读文件中写 算术错误 进程试图进行被禁止的计算，如除以零或者存储器大 于硬件可以接纳的数字 接上表 事件说明 时间超出进程等待某一事件发生的时间超过了规定的最 大值 I/O失败 在输入或输出期间发生错误，如找不到文件、在超过规定 的最多努力次数后仍然读写失败（例如当遇到了磁带上 的一个坏区时）或者无效操作（如从行式打印机中读） 无效指令 进程试图执行一个不存在的指令（通常是由于转移 到了数据区并企图执行数据） 特权指令进程试图使用为操作系统保留的指令 数据误用错误类型或未初始化的一块数据 操作员或操作系 统干涉 由于某些原因，操作员或操作系统终止进程（ 例如，如果存在死锁） 父进程终止当父进程终止时，操作系统可能会自动终止该 进程的所有后代进程 父进程请求父进程通常具有终止其任何后代进程的权力 导致进程状态转换的事件导致进程状态转换的事件 2.2.3 2.2.3 五状态进程模型五状态进程模型 Running：占用处理机（单处理机环境 中，某一时刻仅一个进程占用处理机） Ready：准备执行 Blocked：等待某事件发生才能执行， 如等待I/O完成等 New：进程已经创建，但未被OS接纳 为可执行进程，并且程序还在辅存， PCB在内存 Exit：因停止或取消，被OS从执行状态 释放 Null New：新创建进程首先处于新状态 事 件说 明 新的批作业通常位于磁带或磁盘中的批作业控制流被提供给 操作系统。当操作系统准备接纳新工作时。它将 读取下一个作业控制命令 交互登录 终端用户登录到系统 操作系统因为 提供一项服务 而创建 操作系统可以创建一个进程，代表用户程序执行 一个功能，使用户无需等待（如控制打印的进程 ） 由现有的进程 生成 基于模块化的考虑，或者为了开发并行性，用户 程序可以规定许多进程的创建 NewReady：OS接纳新状态进程为就绪进 程 Ready Running：OS只能从就绪进程中选 一个进程执行 Running Exit：执行状态的进程执行完毕 ，或被取消，则转换为退出状态 RunningReady：分时系统中，时间片用完 ，或优先级高的进程到来，将终止优先级低 的进程的执行 Running Blocked：执行进程需要等待某事 件发生。通常因进程需要的系统调用不能立 即完成，而阻塞 Blocked Ready：当阻塞进程等待的事件发 生，就转换为就绪状态 Ready Exit：某些系统允许父进程在任何 情况下终止其子进程。若一个父进程终止， 其子孙进程都必须终止。 Blocked Exit：因为它自身退出了，或者是 因为某种原因被取消。 Using Two Queues 2.2.4 2.2.4 进程的挂起状态进程的挂起状态 这个问题的出现是由于进程优先级的引入， 一些低优先级进程可能等待较长时间，从而 被对换至外存。这样做的目的是： 提高处理机效率：就绪进程表为空时，要提交新 进程，以提高处理机效率； 为运行进程提供足够内存：资源紧张时，暂停某 些进程，如：CPU繁忙（或实时任务执行），内 存紧张； 被挂起进程的原因 用于调试：在调试时，挂起被调试进程（ 从而对其地址空间进行读写）； 操作系统的需要：操作系统可能挂起后台 进程或一些服务进程，或某些可能导致系 统故障的进程； 父进程的需求：父进程可能挂起子进程。 被挂起进程的特征 不能被调度执行。 可能是等待某事件发生，若是，则阻塞 条件独立于挂起条件，即使阻塞事件发 生，该进程也不能执行。 为了阻止进程执行，可以通过代理使进 程挂起。代理可以是进程自身或父进程 、或OS。 只有实施挂起操作的进程才能使之由挂 起状态转换为其他状态。 One Suspend StateOne Suspend State 一个挂起 Two Suspend States 具有挂起状态的进程状态转换具有挂起状态的进程状态转换 BlockedBlocked/Suspend ：OS通常将阻塞进程换 出，以腾出内存空间 Blocked/SuspendReady/Suspend: 当Blocked/Suspend进程等待的事件发生时，可以将 其转换为Ready/suspend Ready/SuspendReady：OS需要调入一个进程执行 时 ReadyReady/Suspend ：挂起就绪进程，释放足够 的内存空间 New Ready/suspend（New Ready）： 新进程创建后，可以插入到就绪队列或 Ready/suspend队列。若无足够的内存分配给新进程 ，则需要New Ready/Suspend 具有挂起状态的进程状态转换具有挂起状态的进程状态转换（续）（续） Blocked/SuspendBlocked：当Blocked/Suspend队 列中有一个进程的阻塞事件可能会很快发生，则可 将一个Blocked/Suspend进程换入内存，变为 Blocked RunningReady/Suspend ：当执行进程的时间片用 完时，会转换为Ready。或，一个高优先级的 Blocked/Suspend进程正好变为非阻塞状态，OS可以 将执行进程转换为Ready/Suspend状态 AllExit：通常，Running Exit。但某些OS中 ，父进程可以终止其子进程，使任何状态的进程都 可转换为退出状态 2.3 2.3 进程的控制进程的控制 2.3.1 2.3.1 执行模式执行模式 处理机有核心态和用户态两种执行状态 核心态核心态：由设备中断、异常、自陷、信号 （即软中断）等进入，这种状态具有较高的 特权，允许使用全部机器资源与机器指令， 是操作系统程序执行时的状态。 用户态用户态：处理机在这种状态下只能使用指 定的机器指令，不能使用如I/O、改变机器状 态、修改存储保护等指令，并且只允许访问 用户自己的存储区，是用户程序执行时的状 态。 2.3.2 2.3.2 操作系统内核操作系统内核 没有配置任何软件的计算机称为裸 机，操作系统是在裸机上添加多层软件 形成的。通常将与硬件紧密相关的部分 ，如中断处理程序、设备驱动程序及进 程从创建到撤消包括进程状态变迁中用 到的公共操作等集中在一起，常驻内存 ，作为裸机上添加的第一层软件，叫做 内核内核。 操作系统内核的功能操作系统内核的功能 运行频率高的功能模块大都放在操作系 统的内核来实现。 1、资源管理的功能 * * 进程管理进程管理 进程的创建和终止、进程调度、进程状态 转换、进程之间的同步和通信、以及PCB管 理等等。 * * 存储管理存储管理 为进程分配空间、实现内存保护和对换 功能、对内存进行分段和分页管理的等等。 * * I/OI/O设备管理设备管理 I/O缓冲区管理、为进程分配I/O通道和 设备等等 2、支持功能 * I/OI/O中断处理中断处理 中断 处理功能既是内核的最基本功 能，也是整个操作系统赖以活动的基础 ，即操作系统的一切重要活动都最终依 赖于中断。 * 原语操作原语操作 操作系统内核的功能大都通过执行 各种原语来实现的。 原语：是机器指令的延伸，是由若干 条机器指令构成的、完成特定功能的一 个过程。 原子操作：指一个操作中的所有动作 ，要么全做，要么全不做，即原子操作 是一个不可分割的操作。 在单处理机中，操作的原子性可以通 过屏蔽中断来实现。 时钟管理时钟管理 时钟就是操作系统运行的脉搏。 2.3.3 2.3.3 进程控制进程控制 1、进程的创建和撤消 进程的创建进程的创建 进程的撤消进程的撤消 2、进程的阻塞和唤醒 阻塞是进程自己通过调用阻塞原语 自己阻塞自己，而唤醒操作则由操作系 统或其它相关进程调用唤醒原语来唤醒 ，进程自己无法自己唤醒自己。 进程阻塞的原因： * 进程请求I/O服务，无论获得I/O服 务与否，通常都要暂时放弃CPU； * 某些原语操作，如P操作等可能引 起进程阻塞； * 某些系统进程工作时占用CPU，无 事可做时，则调用阻塞原语将自己阻塞 。 进程的阻塞进程的阻塞 进程唤醒的原因： * 进程请求的I/O操作完成； * 某些原语操作，如V操作等可以解 封阻塞进程； * 某些系统进程有事可做时，用唤醒 原语将其唤醒。 进程的唤醒进程的唤醒 3、进程的挂起与激活 根据进程所处状态，挂起原语可以 有三种处理： * 完成进程从活动就绪状态到静止就 绪状态的转变; * 完成进程从活动阻塞状态到静止阻 塞状态的转变; * 若进程是执行状态，则转变为静止 就绪状态。 挂起对象挂起对象： * 进程请求挂起自身； * 父进程挂起子进程。 挂起方式如下挂起方式如下： * 挂起一个具有指定标识符的进 程； * 挂起某个进程及其所有子孙进 程。采用这种挂起方式可以避免进 程被挂起而其子孙进程仍在活动而 带来的问题。 进程挂起进程挂起 进程的激活进程的激活 4、进程切换 进程切换的大致的两个步骤： * 保护被切换进程的现场； * 恢复投入运行的现场。 2.4 2.4 进程调度进程调度 2.4.1 2.4.1 进程调度的目标、原则和方式进程调度的目标、原则和方式 1. 1. 交通控制程序交通控制程序 交通控制程序(Traffic Controller) 是J.H.Saltzer于 1966 年起的名字。他 把操作系统中指挥各个进程的工作比作 一个交通警察， 而把各个进程比作车 辆。 它们之间有时要竞争，有时要合 作， 交通警察就要保证它们协调一致 ，互不冲突。在操作系统中，交通控制 程序的主要职能是管理进程状态之间的 转变和协调进程间的通讯。 2. 2. 进程调度程序进程调度程序 在进程状态的变化中，从就绪到运 行的转变是由一个专门的程序来完成的 ，该程序称为进程调度程序。进程调度 称为“低级”调度，是相对作业调度而言 的。进程调度程序所要完成的是把一台 物理的CPU转变为多台虚拟的CPU或者 多台逻辑的CPU。 3. 3. 引起进程调度的原因引起进程调度的原因 * 现运行进程运行结束或者因任务完成而正 常结束，或者因出现错误而异常结束。 * 现运行进程因某种原因，比如I/O请求， 从运行进入阻塞状态。 * 现运行进程执行某种原语操作，如P操作 、阻塞原语等，进入阻塞状态。 * 一个具有更高优先级的进程要求使用处理 机，即进入就绪队列。 * 分配给该进程运行的时间片已用完。 4. 4. 进程调度程序的功能进程调度程序的功能 * 记住系统中所有进程的状态、 优先 数和资源需求情况。 对于动态优先数 ，还须按一定算法定期地对它进行计算 。 * 确定调度算法，决定把处理机分配 给哪个进程和分配多长时间。 某个进 程正在运行时，如果有优先级更高的进 程进入就绪队列，是继续运行原进程还 是分配处理机给优先级更高的进程，由 调度方式确定。 * 分配处理机给进程。 5. 5. 进程调度方式进程调度方式 所谓进程调度方式，是指当一个进 程正在处理机上运行时，若有某个更为 紧迫或更为重要的进程需要进行处理， 或者说，如果有更高优先级的进程进入 就绪队列时，如何分配处理机。 通常 有两种进程调度方式： 通常有两种进程调度方式： * 非剥夺方式 进程一旦获得CPU就一直执行，直到完 成或发生某事件（如请求I/O服务、P操作等 ）而阻塞，其它的进程方可运行。这种调度 方式简单，容易实现，但是一个进程的运行 往往可能导致多数进程长期得不到服务，所 以非抢占方式不适宜有多个竞争用户的通用 系统。 * 剥夺方式 允许在逻辑上可执行的进程暂时放弃 CPU。抢占方式的调度策略（如时间片轮转、 优先级等）允许非执行进程在满足某种条件 时抢占执行进程所占用的CPU。 6. 6. 进程调度的目标进程调度的目标 进程调度要满足两个方面的目标： * 满足用户的需求 -交互式用户对响应时间的要求； -批处理系统用户对作业周转时间的要求 ； -实时系统对任务截止时间的要求。 * 满足系统的需求 -系统吞吐量； -处理机利用率； -各类资源的平衡使用； -公平性； -优先级。 7. 7. 进程调度原则进程调度原则 A .A .面向用户的原则面向用户的原则 * 响应时间响应时间 响应时间响应时间：是指从用户通过键盘提交一 个请求开始，直到系统首次产生响应为止的 时间。常用于评价分时系统的性能。 响应时间包括3个部分时间的总和： （1）从键盘输入的请求信息传送到处理 机的时间； （2）处理机对请求信息进行处理的时间 ； （3）将响应结果发送到输出终端的时间 。 * 周转时间周转时间 周转时间周转时间：指从作业提交给系统开始， 到作业完成为止的这段时间间隔，也叫 作业周转时间。常用于批处理系统的性 能。 周转时间包括4个部分时间的总和： （1）作业在外存排队等待调度的时间 ； （2）进程在就绪队列中等待调度的时 间（可能多次等待）； （3）进程被处理机执行的时间。 （4）等待I/O操作完成的时间。 * 截止时间截止时间 截止时间截止时间：指实时系统中，某任务必 须开始执行的最迟时间，或必须完成的 最迟时间。常用于评价实时系统的性能 。 B .B .面向系统的原则面向系统的原则 * 系统吞吐量系统吞吐量 系统吞吐量系统吞吐量：指单位时间内系统所完 成的作业数。常用于评价批处理系统的 性能。 * 处理机利用率处理机利用率 处理机利用率处理机利用率：指处理机被使用的频 率。对于衡量大中型机的多用户系统是 一个重要的指标。对于但用户微机或某 些实时系统，则并非很重要。 * 各种资源的平衡使用各种资源的平衡使用 多道程序系统的目标之一就是提高 系统资源的利用率，因此，调度算法有 责任是系统中的各种资源都尽量处于忙 碌状态。该原则同时适合中级调度和高 级调度。 * * 公平性公平性 调度算法应该对所有进程公平，而 不偏袒任何进程。 * * 优先权优先权 优先权是调度算法需要考虑的一个 重要因素。优先权高的进程应该优先调 度。 确定优先权的高低的方式： * 静态优先权 * 动态优先权 2.4.2 2.4.2 进程调度的类型进程调度的类型 按照算法所运行的系统类型， 可以分为： * 批处理调度 * 分时调度 * 实时调度 * 多处理机调度 按照调度的层次，可以分为： * 高级调度（长程调度） * 低级调度（短程调度） * 中级调度（中程调度） * 高级调度高级调度 即作业调度或宏观调度。其任务是对那 些提交给系统后被收容的作业, 按照一定策 略选择出某些作业, 为其分配内存等必要的 资源, 建立与之对应的进程, 并将进程的PCB 表放入就绪队列中, 使其具备参与竞争使用 CPU的权利。 作业调度 高级调度要考虑的两个问题： * 选择多少个作业进入内存，为之创建进 程， 这取决于多道程序度。 * 选择哪些作业，这取决于高级调度算法 。 可用的高级调度算法有： -先来先服务 -短作业优先 -基于优先级调度 -响应比高者优先 注意注意：如果系统不支持作业处理功能，也 就 不会有高级调度。 *低级调度低级调度 即进程调度或微观调度。其任务是在进 入内存并处于就绪队列的进程中, 确定哪个 进程真正获得CPU及其使用CPU的时间。用执 行指针指向选中进程的PCB表，将它从就绪队 列移出并重布现场，使其运行。现代操作系 统都支持低级调度。 进程调度 *中级调度中级调度 将就绪状态细化为内存就绪和外存就绪 状态，阻塞状态细化为内存阻塞和外存阻塞 状态后，中级调度完成进程在内存与外存之 间的对换。其任务是周期性地将那些在内存 中暂时不用的进程换出并放到外存，而将那 些在外存上需要运行的进程换入到内存。 中级调度 处处处处理机的三理机的三级调级调级调级调 度度 2.4.3 2.4.3 进程调度算法进程调度算法 下面是几项主要的评估标准： （） 平均周转时间 作业从提交 时刻is到完成时刻ic所经历的时间称 为该作业的周转时间，即ic is；进程从进入就绪队列的时刻 ir到执行完本次 周期的时刻 ic称为该进程的周转时间i，即i icir。于是，个作业的平均周转 时间或个进程的平均周转时间为： （） 平均带权周转时间 作业的周 转时间Ti与其实际运行时间i之比 称为该作业的带权周转时间，即 ，同样，进程的周转时间与其本 次 周期的时值之比 称为该 进程的带权周转时间。于是，个作业 或个进程的平均带权周转时间为 ： （）平均等待时间 进程从进入就绪 队列那一时刻ir到获得的那一 时刻ip 所经历的时间称为它的等待时 间i，即iipir，那么个进 程的平均等待时间为： 通常，用用来衡量不同调度算法对同一来衡量不同调度算法对同一 作业流或同一进程集的调度性能，用作业流或同一进程集的调度性能，用来衡来衡 量不同进程调度算法对同一进程集的调度性量不同进程调度算法对同一进程集的调度性 能，而用能，而用 来衡量同一来衡量同一调度算法对不同作业调度算法对不同作业 流或不同进程集的调度性能流或不同进程集的调度性能。 现代操作系统采用了以下几种现代操作系统采用了以下几种 调度算法：调度算法： * * 先来先服务（先来先服务（FCFSFCFS） 在先来先服务算法中，进程到达就 绪队列时按先后顺序排队。选择进程去 执行时，始终选队首进程。进程获得 CPU后，直至执行完或发生某等待事件 ，才释放CPU。 先来先服务算法（）本质上是非 剥夺式的，如果可剥夺，则不能保证 原则的实施。 先来先服务算法（）优点： 实现简单 先来先服务算法（）缺点： * 对短进程不公平，使排在队列后面的短 进程要等待很长时间，增加整个系统的平均 周转时间。 * 不利于I/O型进程，未能有效利用系统 资源 * 采用非剥夺调度方式，未考虑进程的紧 迫程度，不适合分时系统和事务处理系统。 因此，先来先服务算法（ ）算法常常和其它调度算法混合使用， 算法适合高级调度、中级调度 和低级调度。 平均周转时间和平均带权周转时间平均周转时间和平均带权周转时间 考虑三个进程、和，它 们的本次周期的时值分别为 、 和 ，且以、 的次序处于就绪队列中，不妨认 为它们进入就绪队列的相对时刻均为 。于是，在调度下，其执行过 程可表示如下： P3P2P1 0 21 2730 、和的等待时间分别为 、和，周转时间分别为 、和，故它们的平均等待时间 和平均周转时间分别为： * * 短进程优先短进程优先 短进程优先算法本质上是非剥夺式的， 如果可剥夺，则不能保证原则的实施。 短进程优先算法优点： 降低了平均等待时间，提高了系统的吞吐 量。 短进程优先算法缺点： * 算法需要预测进程的预期执行时间，当 进程还没运行时，很难准确预测进程的执行 时间。 * 该算法总是优先调度短进程，有可能导 致长进程饥饿，对长进程不公平。 * 采用非剥夺调度方式，未考虑进程的紧 迫程度，不适合分时系统和事务处理系统。 * * 时间片轮转调度法时间片轮转调度法 （ ）算法是 一种剥夺式的进程调度算法，它依据公平服 务的原则，将时间划分成一个个的时 间片（记为S），并以为单位，轮转地为各 个就绪进程一次分配一个时间片。常用于分 时系统和事务处理系统 时间片轮转调度算法优点： * 解决了短进程和长进程的不公平问题； * 对计算型的进程较有利； * 满足分时系统用户对响应时间的要求。 时间片轮转调度算法缺点： * 不适合批处理系统的进程调度。 * 不利于I/O型的进程。 时间片轮转调度算法的时间片选择 时注意的问题： * 不能太短，太短会使进程切换非常 频繁，从而降低处理机的效率； * 不能太长，太长将无法满足交互式 用户对响应时间的要求。 因此，时间片大小的设置要综合考 虑系统的最大用户数、响应时间的要求 和系统效率等多种因素。 以前述的三个进程为例，考察算法的 执行情况及其调度性能。设 ，则有 ： P1P1P1P1P2P1P3P2 P1 04811 151721 25 2930 进程首先执行一个时间片并被剥夺 ，其周期所剩余的 放到以后 执行；执行一个时间片后也被剥夺； 的时值为 ，不足一个时间片。 第二轮开始，又由先执行一个时间片后 被剥夺； 这次只执行 。至此， 和的周期已先后完成，故随后连 续个时间片都分给了，直至完成， 在最后一个时间片里，只执行了 。容易算出，该例的平均等待时间和平均周 转时间分别为： 其中，为系统的响应时间上限， 为系统中的进程数目上限。例如，设 ，则0.1 。 * * 基于优先级的调度算法基于优先级的调度算法 优先级通常是用一个整型数 来表示，称为优先数。对于不同的对于不同的 系统，既可以用较大的数也可以用系统，既可以用较大的数也可以用 较小的数来表示较高的优先级，这较小的数来表示较高的优先级，这 并无统一的规定并无统一的规定。 优先级的设置考虑的因素： * 进程完成功能的重要性； * 进程完成功能的紧迫性； * 为均衡系统资源的使用，指定 进程（作业）优先级； * 进程对资源的占有程度。 确定优先权的高低的方式： * 静态优先权 在进程运行期间其优先级一直不变， * 动态优先权 随着进程的运行其优先级要改变， 其变化考虑的典型因素有： 根据进程运行时间的剩余时间的 减少而上升，以使要执行结束 的进程尽快结束； 根据进程在队列等待时间的增加而上 升，以不至于饥饿。 动态确定优先级的时刻一般在每个时钟动态确定优先级的时刻一般在每个时钟 中断或需要进程切换时。中断或需要进程切换时。 设有五个就绪进程，它们各自的本 次周期的长度、初始优先数及进 入就绪队列的相对时刻如下所示： 在非剥夺的静态设置方式下，执行 情况如下： P4P3P5P1P2 0 436 526062 在进程执行完时，已进入就绪队 列，因其优先级较高，故先于和之前 执行。可算得这些进程的平均等待时间、平 均周转时间以 及平均带权周转时间 分 别为： * * 剩余时间最短者优先算法剩余时间最短者优先算法 根据进程运行时间的剩余时间最短 者优先级最高，以使要执行结束的进程 尽快结束。本质上是剥夺型的短进程优 先调度算法。剥夺是根据时间片。 * * 响应比高者优先算法响应比高者优先算法 根据进程等待时间和进程的预期执行时间纳入 优先级的运算。使进程的优先级与等待时间成正 比，与进程执行时间成反比。 响应比： 响应时间需运行时间 （已等待时间需运行时间）需运行时间 已等待时间需运行时间 响应比高者优先算法优点： 是长进程和短进程都得到合理的运行机会。 响应比高者优先算法缺点： 很难估计进程的剩余执行时间。 * * 反馈调度算法反馈调度算法 多级反馈队列就是综合了 、和的 一种进程调度算法 ，其基本思想如下： （）系统按优先级别设置个就绪进 程队列，第一级队列的优先级最高，以 下逐级降低，第级队列的优先级最低 ； （）每个就绪队列对应有一个时间片 Si（i，2, ，n），且有 ； 多级反馈队列多级反馈队列 2.4.4 2.4.4 实时系统与实时任务调度实时系统与实时任务调度 实时系统实时系统 实时系统实时系统：指能及时响应外部事件的请求 ，在规定的时间内完成对该事件的处理，并 控制所有实时任务协调一致地运行的计算机 系统。 实时系统分为实时控制系统和实时信 息处理系统。 实时控制系统实时控制系统：指要求进行实时控制 的系统，主要用于生产过程和实时采集现场 数据。 实时信息处理系统实时信息处理系统：指能对信息进行实 时处理的系统，该系统由一台或多台主 机通过通信线路连接成百上千个远程终 端，主机根据终端来的请求进行信息检 索和处理，并在很短的时间内为用户做 出正确的回答。 实时任务实时任务 实时任务实时任务：指具有及时性要求的、常常被 重复执行的特定进程，在实时系统中常称为 任务。 按照任务执行是否呈现周性来划分任务有： * 周性性实时任务 要求按照指定的周期循环执行。 * 非周期实时任务 任务执行无指定的周期性，但必须要联 系着一个截止时间（包括开始截止时间和完 成截止时间）。 按照对截止时间的要求可以划分为： * 硬实时任务 系统必须满足任务对截止时间的要 求。 * 软实时任务 联系着一个截止时间，但并不严格 。 实时调度的目标实时调度的目标 实时系统的关键即任务调度，调 度策略主要考虑如何使硬实时任务在其 规定的截止时间内完成，同时尽可能使 软硬实时任务也能在其规定的截止时间 内完成。 大多数现代实时操作系统无法直大多数现代实时操作系统无法直 接处理任务的截止时间，只能尽量提高接处理任务的截止时间，只能尽量提高 响应速度，以尽快地调度任务。响应速度，以尽快地调度任务。 实时调度算法实时调度算法 常采用的算法有： * 最早截止时间优先调度算法 * 速度单调调度算法（RMS） 即根据任务的周期大小给进程优先 级， 最短周期的任务具有最高优先级。 任务周期任务周期：指一个任务到达至下一任 务到达之间的时间范围。 任务速度任务速度：指周期的倒数。 2.5 2.5 线程线程 2.5.1 2.5.1 线程的定义线程的定义 线程可定义为“进程内的一个执行单进程内的一个执行单 位位”， 或者定义为“进程内的一个可调进程内的一个可调 度的实体度的实体”。 在具有多线程机制的操作系统中， 处理机调度的基本单位不是进程而是线 程。 负责处理机调度的程序称为线程 调度程序，它是操作系统内核的重要组 成部分， 线程调度也是内核的主要功 能之一。 2.5.2 2.5.2 进程和线程的关系进程和线程的关系 (1) 线程是进程的一个组成部分。 每个进程 在创建时通常只有一个线程，需要时这个线 程可以创建其它线程。 (2) 进程的多线程都在进程的地址空间活动 。 (3) 资源是分给进程的，而不是分给线程的 ，线程在执行中需要资源时，系统从进程的 资源配额中扣除并分配给它。 (4) 处理机调度的基本单位是线程，线程之 间竞争处理机，真正在处理机上运行的是线 程。 (5) 线程在执行过程中， 需要同步。 2.5.3 2.5.3 线程的类型线程的类型 在操作系统中，系统能否感知到线程的存在呢 ？这个问题涉及到将线程放在用户空间还是放在 系统空间进行管理。 在某些操作系统中，系统感知不到线程的存在 。换言之，线程完全在用户空间进行管理。那么 ，当一个线程将被阻塞时，它在停止之前选择并 启动它的后继线程，而不必由操作系统内核进行 控制。 在另外一些系统中，操作系统知道每个进程中 有多少个线程，所以当一个线程被阻塞时，操作 系统会选择下一个线程运行，它可能来自同一个 进程，也可以来自其它进程。为了进行调度，核 心必须设有一张线程控制表，其中列出了系统中 所有的线程，类似于进程控制表所起的作用。 这两种选择的性能相差很远。在进程发 生切换时，在用户空间管理的线程比需要操 作系统核心调用的线程要快得多。这表明， 将线程管理放在用户空间比较合理。而另一 方面，当线程完全在用户空间管理时，若一 个线程阻塞（例如，请求 I/O服务或处理页 面中断等），则操作系统核心会将线程所属 的整个进程阻塞，因为它甚至不知道线程的 存在。这表明，将线程放在系统空间进行管 理更适宜。目前的做法是两种选择都被采用 ，同时还提出了各种混合方案。 不同类型的线程有着不同的属性和使用方 法，以下讨论两种主要的线程类型。 * 内核线程 内核线程的特点： A、一个内核线程可以独立工作，不需要与一个用 户进程联系起来。 B、内核线程的创建与撤消是由系统的内部需求决 定的，用来负责执行一个指定的任务，它共享 系统的程序与全局数据，具有自己的堆栈。 C、内核线程能够被单独调度并使用标准的系统同 步机制。 D、内核线程的创建和使用开销不是很大，它 们 使用的资源是内核堆栈和在它们不运行时 用 来保存寄存器上下文的一个内存区域，当 然 还需要一些数据结构来保存调度和同步信 息。 E、内核线程间的上下文切换是很快的，因为 内 存映射不用刷新。 F、内核线程运行在系统空间，系统中有一张 线 程表，列出了所有的内核线程，系统可以 选 择内核线程运行。 * 用户线程 用户线程的特点： A、用户线程运行在用户空间，内核 无 需也无法感知它。 B、每个用户线程仅需一个栈和程序 计 数器PC, 切换速度快。 C、当一个用户线程被阻塞时, 它在 停 止之前选择并启动它的后继线程 。 D、用户线程的实现是可能的，因为 用 户线程的上下文可以在没有内核 干 预的情况下被保存和恢复。 E、每一个用户线程有自己的用户堆栈， 一块用来保存用户级寄存器上下文以 及如信号屏蔽等状态信息的内存区域。 F、通过保存当前线程的堆栈和寄存器内容， 以及装入新调度线程的那些堆栈和寄存 器内容，可实现用户线程间的调度和上 下文的切换。 普通进程上的用户线程普通进程上的用户线程 2.6 2.6 进程互斥与同步进程互斥与同步 2.6.1 2.6.1 并发控制并发控制 进程间的同步进程间的同步 多个进程在执行过程中，为了共享资源 与相互合作而在执行次序上的协调，称为同同 步步。 例：有用户作业程序，其形式是： Z=func 1(x)*func 2(y) 其中func 1(x)， func 2(y)均是一个复杂复杂 函数，函数， 为了加快本题的计算速度，可用两个为了加快本题的计算速度，可用两个 进程进程P1P1、 P2 P2 各计算一个函数各计算一个函数。 进程P2 计算 func 2(y)，进程P1 在计算完func 1(x)之后， 与进程P2 的计算结果相乘， 以获得最终结果 Z。 进程进程P1 P1 和和P2 P2 间的同步间的同步 2. 2. 进程间的互斥进程间的互斥 当某一进程访问某一资源时，不允许别 的进程同时访问，这种限制称为互斥互斥。 就其 本质来讲，互斥仍是一种同步。 资源互斥使用例资源互斥使用例 3. 3. 并发控制的内容并发控制的内容 * * 竞争资源竞争资源 多个进程因为使用共享资源而产生 竞争关系，在抢占使用资源时可能导致 使用失败，都达不到目的，因而要有信 息交换以保证各得其所。 临界资源临界资源：一次仅允许一个进程访问的资 源。 例如，若有两个进程P1、P2，共享一个公用变量c， 初值为8，P1、P2所做工作如下： P1 P2 L1：a = c； L4：b = c； L2：a = a+1； L5：b