操作系统原理与实例分析

1、第二章进程管理1本章要点基础：进程描述及控制策略：进程调度实现：互斥与同步避免：死锁与饥饿解决：几个经典问题关于：进程通信22.1 进程的引入3程序顺序执行程序：源代码程序、目标程序和可执行程序 程序执行：编辑、编译、链接、执行程序的结构：顺序结构、分支结构和循环结构 4程序顺序执行程序顺序执行的特征：顺序性、封闭性、可再现性5程序并发执行多道程序设计技术：多个程序并发执行程序并发执行时的特征：间断性、非封闭性、不可再现性6程序并发执行引发的问题协调各程序的执行顺序 例如，当输入的数据还未全部输入内存时，计算必须等待 多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果 选择哪些

2、、多少个程序进入内存执行？内存中的执行程序谁先执行，谁后执行？内存如何有效分配？ 7进程的概念 定义：可并发执行的程序，在一个数据集合上的运行过程。申请/拥有资源 调度（线程）程序：静态概念，是指令和数据的集合，可长期存储进程与程序对应关系： - 一个程序可以对应一个进程或多个进程 - 一个进程可以对应一个程序，或者一段程序8进程的特征动态性并发性独立性异步性9引入进程带来的问题 增加了空间开销 ：为进程建立数据结构 额外的时间开销 ：管理和协调、跟踪、填写和更新有关数据结构、切换进程、保护现场 更难控制 ： - 协调多个进程竞争和共享资源如何预防 - 解决多个进程因为竞争资源而出现故障 处理

3、机的竞争尤为突出 10进程的结构组成（进程映像）: 程序、数据集合、进程控制块PCB (Process Control Block )PCB是进程存在的唯一标志。创建进程时，创建PCB；进程结束时，系统将撤消其PCB。 11PCB进程标识信息：进程的内部和外部标识符处理机状态信息：通用寄存器值、指令计数器值、程序状态字PSW值、用户栈指针值进程调度信息：进程状态、进程优先权、进程调度的其它信息其它信息：程序及数据地址、进程同步和通讯机制、资源清单、链接指针12PCB的组织方式之一- 单一队列 所有进程的PCB通过链表组织成为一个单一队列。适用于进程数目不多的系统。如，Windows操作系统。

4、13PCB的组织方式之二-表格结构 PCB按进程状态不同，组织成不同的表格：就绪进程表、执行进程表（多机系统中）及阻塞进程表系统分别记载各PCB表的起始地址 14PCB的表格结构15PCB的组织方式之三-多级队列 PCB按进程状态不同用链接指针组成不同队列：就绪进程队列、阻塞进程队列（可按阻塞原因不同，分别组织）系统分别记载各PCB链表的起始地址16PCB多级队列172.2 进程的状态18进程执行轨迹 进程的轨迹：进程执行的指令序列，用以观察处理机的执行过程。例，假设内存中有3个进程A、B、C，他们的程序代码已全部装入内存。若A、B两进程需要执行12条指令，C进程需要执行4条指令，且C进程执行

5、到第4条指令处必须等待I/O1920假设分派程序分派处理机需要依次执行指令序列：s+0,s+1,s+5进程A的执行轨迹为a+0,a+1,a+2,a+3,进程B的执行轨迹为b+0,b+1,b+2,b+3,进程C的执行轨迹为c+0,c+1,c+2,c+3,当它执行到c+3指令时遇到了I/O指令，需要释放处理机，进行输入/输出操作 2129 s+030 s+131 s+232 s+333 s+434 s+51 a+02 a+1 a+2 a+3 a+4 a+535 a+636 a+737 a+838 a+939 a+1040 a+117 s+08 s+19 s+210 s+311 s+412 s+51

6、3 b+014 b+115 b+216 b+317 b+418 b+525 c+026 c+127 c+228 c+341 s+0s+1s+2s+3s+4s+519 s+020 s+121 s+222 s+323 s+424 s+57 b+648 b+749 b+850 b+951 b+1052 b+1122 两状态进程模型 两状态：执行、未执行 - 进程获得处理机，进入执行状态;当时间片结束或其它某种原因，进程释放处理机，暂停执行，处于未执行状态。 23两状态进程模型：队列形式24 注： 并非所有进程只要“未执行”就处于就绪（ready），有的需要阻塞（ blocked ）等待I/O完成“未

7、执行”又可分为 就绪和阻塞25进程的五状态 执行状态（Running）就绪状态（Ready）阻塞状态（Blocked）新状态（New）终止状态（Terminated）26 1. 新状态：进程已经创建，但未被OS接纳为可执行进程2. 就绪状态：准备执行3. 执行状态：占用处理机（单处理机环境中，某一时刻仅一个进程占用处理机）4. 阻塞状态：等待某事件发生才能执行，如等待I/O完成等5. 终止状态：因停止或取消，被OS从执行状态释放 2728 空 新状态 新创建的进程首先处于新状态。 新状态 就绪状态 当系统允许增加就绪进程时，操作系统接纳新建状态进程，将它变为就绪状态，插入就绪队列中。 就绪状态

8、 执行状态 当处理机空闲时，将从就绪队列中选择一个进程执行，该选择过程称为进程调度，或将处理机分派给一个进程，该进程状态从就绪转变为执行。 执行状态 终止状态 执行状态的进程执行完毕，或出现诸如访问地址越界、非法指令等错误，而被异常结束，则进程从执行状态转换为终止状态。29 执行状态 就绪状态 分时系统中，时间片用完，或优先级高的进程到来，将中断较低优先级进程的执行。进程从执行状态转变为就绪状态，等待下一次调度。 执行状态 阻塞状态 执行进程需要等待某事件发生。通常，会因为进程需要的系统调用不能立即完成，如读文件、共享虚拟内存、等待I/O操作、等待另一进程与之通信等事件而阻塞。 阻塞状态 就绪

9、状态 当阻塞进程等待的事件发生，就转换为就绪状态。进入就绪队列排队，等待被调度执行。 30注：某些系统允许父进程在任何情况下终止其子进程。如果一个父进程被终止，其子孙进程都必须终止。 - 新状态 终止 - 就绪状态 终止 - 阻塞状态 终止3132问题：多个进程竞争内存资源 内存资源紧张无就绪进程，处理机空闲：I/O的速度比处理机的速度慢得多，可能出现全部进程阻塞等待I/O33解决方法 采用交换技术：换出一部分进程到外存，以腾出内存空间采用虚拟存储技术：每个进程只能装入一部分程序和数据（存储管理部分）34对换技术,交换技术(Swapping ） 将内存中暂时不能运行的进程，或暂时不用的数据和程

10、序，换出到外存，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的数据和程序，换入内存。35进程的挂起状态 进程被交换到外存，状态变为挂起状态36进程挂起的原因进程全部阻塞，处理机空闲。系统负荷过重，内存空间紧张。操作系统的需要。操作系统可能需要挂起后台进程或一些服务进程，或者某些可能导致系统故障的进程。 终端用户的请求。父进程的需求。37被挂起进程的特征不能立即执行可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能执行使之挂起的进程为：自身、其父进程、OS只有挂起它的进程才能使之由挂起状态转换为其他状态38挂起与阻塞 问题 是否只能挂起阻

11、塞进程？ 如何激活一个挂起进程？39挂起与阻塞区分两个概念：? 进程是否等待事件，阻塞与否? 进程是否被换出内存，挂起与否种状态组合：就绪：进程在内存，准备执行阻塞：进程在内存，等待事件 就绪/挂起：进程在外存，只要调入内存即可执行阻塞/挂起：进程在外存，等待事件40注: 处理机可调度执行的进程有两种：新创建的进程或换入一个以前挂起的进程 通常为避免增加系统负载，系统会换入一个以前挂起的进程执行。41挂起接纳激活就绪/挂起图2.12 具有挂起状态的进程模型挂起时间片完新建 就绪 执行 阻塞 终止分派/调度事件发生事件等待完成激活阻塞/挂起事件发生 42具有挂起状态的进程状态转换阻塞阻塞/挂起

12、：OS通常将阻塞进程换出，以腾出内存空间阻塞/挂起 就绪/挂起:当阻塞/挂起进程等待的事件发生时，可以将其转换为就绪/挂起就绪/挂起就绪：OS需要调入一个进程执行就绪 就绪/挂起：一般，OS挂起阻塞进程。但有时也会挂起就绪进程，释放足够的内存空间新就绪/挂起（新 就绪）：新进程创建后，可以插入到就绪队列或就绪，挂起队列。若无足够的内存分配给新进程，则需要新 就绪/挂起43具有挂起状态的进程状态转换（续）阻塞/挂起 阻塞：当阻塞/挂起队列中有一个进程的阻塞事件可能会很快发生，则可将一个阻塞/挂起进程换入内存，变为阻塞执行 就绪/挂起：当执行进程的时间片用完时，会转换为就绪。 或，一个高优先级的阻

13、塞/挂起进程正好变为非阻塞状态，OS可以将执行进程转换为就绪/挂起状态所有状态 终止：通常，执行 终止。但某些OS中，父进程可以终止其子进程，使任何状态的进程都可转换为退出状态442.3 进程的控制 45两种执行模式 系统模式（又称为系统态）、控制模式或内核模式： - 具有较高的特权 - 运行系统特定的指令,包括读/写控制寄存器的指令、基本I/O指令以及与存储器管理有关的指令，及一些特定的内存区 - 内核模式下的处理机及其指令、寄存器和内存都受到完全控制和保护用户模式（或用户态） - 具有较低的特权 - 用户程序一般运行在用户模式46模式切换用户模式 系统模式：用户程序执行到一条系统调用，进入

14、操作系统内核执行系统模式 用户模式 ：执行完系统调用的功能，返回到用户程序特殊情况：程序执行到结束语句时，切换到系统模式，不再返回到用户程序 47操作系统内核（Kernel）操作系统的核心，是基于硬件的第一层软件扩充，提供操作系统最基本的功能，是操作系统工作的基础。现代操作系统设计中，为减少系统本身的开销，往往将一些与硬件紧密相关的（如中断处理程序、设备驱动程序等）、基本的、公共的、运行频率较高的模块（如时钟管理、进程调度等）以及关键性数据结构独立开来，使之常驻内存，并对它们进行特殊保护。通常把这一部分称为操作系统的内核。48用户通过系统调用访问操作系统的功能，这些功能最终都通过操作系统内核实

15、现。不同的操作系统对内核的定义和功能范围的设定是不同的。一般地，操作系统内核的功能可以概括地划分为资源管理功能和支撑功能。 - 资源管理：进程管理、存储管理和I/O设备管理 - 支撑功能：中断处理、统计、监测、时钟管理、原语操作等。 49资源管理功能进程管理：进程创建和终止、调度、状态转换、同步和通信、管理PCB 存储管理：为进程分配地址空间、对换、段/页管理I/O 设备管理：缓存管理、为进程分配I/O通道和设备50支撑功能中断处理时钟管理原语（ Primitive ）: 原子操作统计监测51进程控制原语进程切换创建与终止阻塞与唤醒挂起与激活52进程创建: 原因提交新的批处理作业交互式用户注册

16、操作系统提供服务父进程创建子进程53进程创建: 步骤为进程分配一个唯一标识号ID 主进程表中增加一个新的表项为进程分配空间 : 用户地址空间、用户栈空间、PCB空间。若共享已有空间，则应建立相应的链接。初始化PCB:进程标识、处理机状态信息、进程状态建立链接 :若调度队列是链表，则将新进程插入到就绪或就绪/挂起链表建立或扩展其他数据结构54进程终止: 原因批处理作业执行到“结束”语句交互式用户“注销”停止进程（应用程序）的执行遇到错误或故障55进程终止: 具体原因正常结束超时终止,执行时间超过预计时间内存不足,无法为进程分配所需的内存空间越界访问企图使用未允许用的数据，或操作方式错计算错,如除

17、零，或企图存储硬件允许的最大数超时等待某事件发生56进程终止: 具体原因I/O 失败, 如找不到文件或多次重试仍无法读写文件，或无效操作无效指令,企图执行不存在的指令特权指令,企图执行特权指令数据类型不符，或未初始化操作员或OS干预，如发生死锁的时候父进程终止父进程请求57进程终止: 步骤根据被终止进程的标识符ID，找到其PCB，读出该进程的状态；若该进程为执行状态，则终止其执行，调度新进程执行；若该进程有子孙进程，则立即终止其所有子孙进程将该进程的全部资源，或归还给其父进程，或归还给系统将被终止进程（的PCB）从所在的队列中移出，等待其它程序来搜集信息58进程的阻塞与唤醒 阻塞原因：请求系统

18、服务；启动某种操作，如I/O；新数据尚未到达；暂时无新工作可做等当出现阻塞事件，进程调用阻塞原语将自己阻塞。并将其状态变为“阻塞状态”，并进入相应事件的阻塞队列；当阻塞进程期待的事件发生，有关进程调用唤醒原语，将等待该事件的进程唤醒。并将其状态变为“就绪状态”，插入就绪队列。一般,进程可以自己阻塞自己；而唤醒操作则由操作系统，或其它相关进程来完成，进程无法自己唤醒自己。 59进程的挂起与激活 当出现挂起事件，系统利用挂起原语将指定进程或一个阻塞进程挂起。进程从内存换出到外存，其状态转换：就绪 就绪/挂起 或阻塞 阻塞/挂起当激活事件发生，系统利用激活原语将指定进程激活。将相应进程从外存换入到内

19、存，可能的状态转换：就绪/挂起 就绪，或 阻塞/挂起 阻塞60进程切换时钟中断进程执行完一个时间片I/O 中断内存访问出错 - 虚拟存储中，需要的指令或数据不在内存陷阱执行遇到错误可能使进程转换到终止状态61进程A切换到进程B 的步骤首先，保护进程A的现场 将进程A的当前运行信息，如程序执行到的当前位置，程序状态字，所有的寄存器值等保存到进程A的PCB中。然后，恢复进程B的现场 从进程B的PCB中获取其执行信息，将这些信息写入相应的寄存器中，程序计数器指向进程B将执行的下一条指令。进程B可能第一次开始执行，也可能是被中断过的进程，恢复执行。不论是哪一种情况，进程B的执行信息都能在其PCB中找到

20、。 62进程切换 vs. 模式切换进程切换,作用于进程之间的一种操作。当分派程序收回当前进程的CPU并准备把它分派给某个就绪进程时，该操作将被引用。模式切换,是进程内部所引用的一种操作。当用户程序转入系统调用，或相反时，该操作将被引用。进程切换一定引发模式切换，反之则不然。632.4 进程调度64什么是调度？调度是指，在一个队列中，按照某种方法（算法），选择一个合适的个体的过程。调度的关键是需要某种方法或算法，好的调度算法有利于选择到合适的个体。如何判断、设计一个好的调度算法呢？ 65调度实例66调度目标公平性，防止进程长期不能获得调度而饥饿；处理机利用率，尽量提高处理机的利用率；提高系统吞吐

21、量;尽量减少进程的响应时间67调度原则满足用户的要求:响应时间、周转时间、截止时间满足系统的需求：系统吞吐量、处理机利用率、各类资源的平衡使用、公平性及优先级 68面向用户的原则：响应时间是指，从用户通过键盘提交一个请求开始，直到系统首次产生响应为止的时间。 输入的请求传送到处理机的时间+ 处理机对请求信息进行处理的时间+ 将响应结果发送到输出终端的时间响应时间调度算法则应考虑尽可能使绝大多数用户的请求能在响应时间内完成。常用于评价分时系统的性能。 69面向用户的原则：周转时间指从作业提交给系统开始，到作业完成为止的这段时间间隔作业在外存排队等待调度的时间+进程在就绪队列中等待调度的时间+进程

22、被处理机执行的时间+等待I/O操作完成的时间 周转时间常用于评价批处理系统的性能70面向用户的原则：周转时间（续）影响周转时间的调度：作业从外存调度到内存（作业调度）进入内存还需在就绪队列中排队，等待进程调度。甚至，可能会挂起进程，在外存等待被激活（中程调度）71面向用户的原则：截止时间指实时系统中，某任务必须开始执行的最迟时间，或必须完成的最迟时间。常用于评价实时系统的性能。 72面向系统的原则：系统吞吐量 指单位时间内系统所完成的作业数常用于评价批处理系统的性能。 73面向系统的原则：处理机利用率 大、中型多用户系统，由于处理机价格昂贵，处理机利用率是衡量系统性能的一个重要指标单用户微机或

23、某些实时系统，则并非很重要。 74面向系统的原则：各类资源的平衡使用多道程序系统的目标之一就是为了提高系统资源的利用率，因此，调度算法有责任使系统中的各种资源都尽量处于忙碌状态。该原则同时适用于长程调度和中程调度，因为它们可以决定哪些作业（进程）可以进入内存，可以考虑系统资源的均衡使用。 75面向系统的原则：公平性     调度算法应该对所有进程公平，不偏袒任何进程。 76面向系统的原则：优先权 优先权高的进程应优先调度可以根据进程的优先权不同，组织不同的就绪队列。进程调度时首先选择高优先权队列中的进程，直到该队列空，再调度较低优先权队列中的进程，如图2.13所示

24、7778几乎所有操作系统的调度算法都可考虑优先权原则。当然，仅考虑优先权，可能会出现饥饿，对低优先权的进程不公平。可以将进程排队的等待时间等因素纳入优先权的计算，随着进程等待时间的增长，其优先权也不断提高，进程也会在不久的将来得到调度。79进程调度方式根据执行进程的处理机是由进程自己释放，还是被强行剥夺，可以将进程调度方式分为非剥夺方式和剥夺方式两种。 80进程调度方式：非剥夺方式执行进程只有在执行完毕，或因申请I/O阻塞自己时，才中断其执行，释放处理机，调度新的进程执行这种方式不利于“即时性”要求较高的分时和实时系统，主要用于批处理系统。81进程调度方式：剥夺方式操作系统可以在新进

25、程到来时，或某个具有较高优先权的被阻塞进程插入就绪队列时，或在基于时间片调度的系统中，时间片用完而中断当前进程的执行，调度新的进程执行。这种方式会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统和分时系统。82调度的类型 批处理调度、分时调度、实时调度和多处理机调度 长程调度、中程调度、短程调度I/O调度 83长程调度（Long-term scheduling） 又称高级调度，或作业调度，它为被调度作业或用户程序创建进程，分配必要的系统资源，并将新创建的进程插入就绪队列，等待短程调度。某些采用交换技术的系统将新创建的进程插入到就绪/挂起队列，等待中程调度。在批处理系统

26、中，作业进入系统后，先驻留在磁盘上，组织成批处理队列，称为后备队列。长程调度从该队列中选择一个或多个作业，为之创建进程。如图 :8485长程调度需要考虑两个问题选择多少个作业进入内存，为之创建进程？ - 取决于多道程序的度，即允许同时在内存中运行的进程数。2.选择哪些作业? - 取决于长程调度算法86短程调度（Short-term scheduling） 也称进程调度，或低级调度，决定就绪队列中的哪个进程将获得处理机。短程调度运行频率最高。现代操作系统几乎都具有短程调度功能。87中程调度（Medium-term scheduling） 又称为中级调度。它是对换功能的一部分。当内存空间非常紧张时

27、，或处理机找不到一个可执行的就绪进程时，需要选择一个进程（阻塞或就绪状态）换出到外存，释放出内存空间给别的进程使用；当内存空间较充裕时，从外存选择一个挂起状态的进程调度到内存（换入），见图。8889中程调度（Medium-term scheduling） 目的：为了提高内存的利用率和系统吞吐量。只有支持进程挂起的操作系统才具有中程调度功能。 90进程调度算法 - 先来先服务（FCFS）该方法按照进程到达的先后顺序排队，每次调度队首的进程。FCFS算法属于非剥夺调度方式，实现简单，看似公平。但，对于那些后进入队列而运行时间较短的进程，或I/O型的进程而言，可能需要长时间等待。91进程调度算法 -

28、 先来先服务（FCFS）分析前面列举的幼儿园一组小孩进食的例子：如果采用FCFS方法，让全部小孩排成一个先进先出的队列，老师从队首开始逐个给小孩喂食，只有当前一个小孩吃饱了，才喂食下一个小孩。那么，排在队列后面的的小孩将长时间不能被喂食而饥饿。特别地，如果排在队列前面的某些小孩需要喂食的时间较长，而排在队列后面的某些小孩只需进食很少的饭量，却需要等待很长的时间。故，该方法对这样的小孩不公平。92进程调度算法 - 先来先服务（FCFS）假设 就绪队列中从队首开始依次排列有四个进程P1，P2，P3和P4（假设它们同时到达就绪队列），它们的预计执行时间分别为16，12，4和3个单位时间。若采用FCF

29、S方法调度，试计算P1，P2，P3和P4的周转时间分别为多少？平均周转时间是多少？9394进程调度算法 - 先来先服务（FCFS）对短进程不公平。由于长进程可能排在队列前面，必将增加队列后部进程的等待时间，从而将增加平均周转时间。不利于I/O型进程，未有效利用系统资源。一般地，FCFS与其他调度算法混合使用。例如，系统可以按照不同的优先级维护多个就绪队列，每个队列内部按照FCFS算法调度。FCFS算法同时适合于长程、中程和短程调度三种调度类型。 95短进程优先 当需要调度进程（或作业）时，通过计算判断就绪进程队列中哪一个进程的预期执行时间最短，或后备作业队列中哪一个或几个作业的预期执行时间最短

30、，就调度谁。96短进程优先属于非剥夺调度算法。当某进程获得处理机，直到其执行完成，或需要等待某事件而阻塞时，才自动释放处理机。系统又调度新的进程（或作业）。若采用短进程优先算法调度上例的4个进程，按照进程预期执行时间排序（升序）为P4，P3，P2，P1，试分别计算4个进程的周转时间和他们的平均周转时间。 9798短进程优先与FCFS算法比较，短进程优先调度算法改善了系统的性能，降低了系统的平均等待时间，提高了系统的吞吐量。但是，该算法也存在一些问题： 很难准确预测进程的执行时间； 可能导致长进程饥饿，这对长进程不公平； 采用非剥夺调度方式，未考虑进程的紧迫程度，不适合于分时系统和事务处理系统。

31、 99时间片轮转调度法 例如 在一个分时联机系统中，同时有n个人通过各自的终端共享一台主机（服务器）。终端完成输入/输出操作，主机负责处理从终端发来的请求，为之建立进程、协调各进程的运行、调度各个进程等，并尽量满足每个终端用户对响应时间的要求。100基于时间片轮转调度主机终端1终端2终端n图2.18 一个基于时间片轮转调度的联机系统101时间片轮转调度法在分时联机系统中，n个进程循环地获得时间片而执行。从系统中来看它们是交替执行的，但就每个终端用户而言，都感觉到自己独占了一台主机，不受其他用户的影响。这是通过进程并发执行实现的。如果用户数太多，主机处理的进程将会急剧增加，进程排队等待的时间也会

32、很长，进程的响应时间也可能增长，用户将明显感觉到主机的速度变慢而不满意。另外，时间片的大小也会影响进程的响应时间。 102时间片的设置进程切换将会增加系统的额外开销。 时间片设定得太短，进程切换会非常频繁，从而降低处理机的效率；时间片设定得太长，将无法满足交互式用户对响应时间的要求。因此，时间片大小的确定应综合考虑系统的最大用户数、响应时间、系统效率等多种因素。 103时间片轮转调度法采用基于时间片轮转调度算法调度上例的4个进程，并分别按照两种时间片大小轮转调度（1个单位时间和4和单位时间），分析该算法的性能。首先按照进程到达的先后顺序组织就绪队列，即P1,P2,P3,P4。从队首开始调度，首

33、先调度P1，执行一个时间片，强行中断P1，P1回到就绪队列队尾排队；切换到P2，执行一个时间片，强行中断P2，P2回到就绪队列队尾排队（排在P1之后） 104105106时间片轮转调度法为了简单，图中忽略了进程切换时的系统开销，而实际操作系统中，这类额外开销是客观存在的。可见，采用基于时间片轮转调度法，进程的周转时间和平均周转时间并不比采用FCFS和短进程优先调度算法小。加上进程切换所需的系统开销时间，该算法的平均周转时间还会增长。 107时间片轮转调度法常用于分时系统及事务处理系统，合理的时间片大小将带来满意的响应时间。通常，合理的时间片指，能让80%左右的进程在一个时间片内完成。对于短的、

34、计算型的进程较有利。不适合于批处理系统的进程调度不利于I/O型的进程。改进的方法之一，可以将I/O阻塞事件完成的进程单独组织一个就绪队列，该队列进程的时间片可以设置的小一些，且优先调度。108基于优先级的调度算法基于时间片轮转调度法循环式地为每个被调度的进程分配一个时间片，对每个进程都是公平的。然而，实际应用中，进程的性质可能是不同的。例如，一个与用户进行交互的前台进程急迫地需要对用户的输入作出响应，而一个后台打印进程的迫切性也许就不那么重要。因此，可以为每个进程定义一个优先级，优先级越高的进程将优先获得处理机的调度。 109如何设定进程的优先级呢？ 进程完成功能的重要性 进程完成功能的急迫性

35、 为均衡系统资源的使用，指定进程（作业）优先级进程对资源的占用程度 例如，可以为短进程（或作业）赋予较高的优先级。 110静态与动态优先级静态优先级：一旦确定，则进程运行期间优先级一直不改变。动态优先级：系统首先赋予进程一个初始优先级，该优先级将随着进程的运行而改变。111动态优先级典型的动态优先级变化方式为： - 优先级随着进程运行的剩余时间的减少而上升，使将要执行结束的进程尽快完成； - 或随着进程排队等待时间的增长而上升，使等待时间越长的进程优先得到调度，不至于长时间饥饿。具体实现方法，可以在每个时钟中断时，或需要进程切换时，重新计算就绪队列中各进程的优先级，并优先调度高优先级的进程。采

36、用动态优先级的两种调度算法：剩余时间最短者优先和响应比高者优先。 112剩余时间最短者优先 为了使将要结束的进程尽早结束，释放系统资源，让别的进程执行。可以在每个时钟中断时，根据就绪队列中各进的剩余执行时间动态调整其优先级，剩余时间最短的进程优先级最高。显然，该算法是剥夺型的短进程优先调度算法，调度程序总是选择剩余执行时间最短的进程调度执行。113剩余时间最短者优先 与短进程优先调度算法一样，该调度算法很难准确估计进程的剩余执行时间。由于长进程在未执行时，或刚开始执行的一段时间内，其剩余执行时间都不会最短，所以该算法对长进程不公平。但是，它不象FCFS算法偏袒长进程，也不象轮转调度算法会产生很

37、多中断而增加系统负担。由于短进程提前完成，故采用剩余时间最短者优先的调度算法获得的平均周转时间比采用短进程优先算法短。 114响应比高者优先 将进程的等待时间和进程的预期执行时间纳入优先级的计算，进程（预期执行时间）越长优先级越低，而随着进程的等待时间增长优先级上升，即进程的优先级与等待时间成正比，与进程执行时间成反比。令w表示等待时间，s表示预期执行时间，则响应比：115响应比高者优先调度方法：若当前执行进程执行完毕，或需要阻塞等待某事件而释放处理机，调度程序选择就绪队列中响应比最大的进程执行。若等待时间相同，短进程因为s较小，R较大而优先调度。若进程的预期执行时间相同，则等待时间长的进程优

38、先调度，相当于FCFS。随着等待时间的增加，长进程的响应比不断增大，在某个时刻，也必然被调度。 116响应比高者优先同短进程优先和剩余时间最短者优先调度算法一样，很难准确估计进程的预期执行时间。每次调度之前都需要计算响应比，增加了系统开销。 117反馈调度法前面介绍的几种调度算法都存在各自不同的问题，尤其是短进程优先、剩余时间最短者优先以及响应比高者优先调度算法都需要估计进程的预期执行时间，如果估计不准确，将影响调度结果和系统性能。如果根据进程执行历史，而非未来，进行调度，将解决这个问题。反馈调度法就是一种根据进程执行历史调整调度方式的调度方法，它结合了优先级和时间片轮转调度思想。 11811

39、9反馈调度法该方法有利于交互型短进程或短批处理作业，因为它们一般只需要一个或很少的几个时间片即可完成，但可能使长进程的周转时间急剧增加。如果不断地有新进程到来，还可能出现长进程长期饥饿现象。为此，可以为各队列设置不同的时间片，优先级愈低时间片愈长。 120进程调度算法小结如何选择进程调度算法与系统设计的目标有关。交互式多任务系统，主要考虑联机用户对响应时间的要求，一般采用基于时间片轮转调度算法，同时，根据进程的性质设置不同的优先级；批处理系统往往以作业的平均周转时间来衡量调度性能，常选用基于优先级的短进程（或作业）优先调度算法。 121实时系统(Real-Time System) 指，能及时响

40、应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行的计算机系统.分为实时控制系统和实时信息处理系统122实时系统- 实时控制系统指要求进行实时控制的系统。主要用于生产过程的控制，实时采集现场数据，并对所采集的数据进行及时处理，进而自动地控制相应的执行机构，使某些(个)参数(如温度、压力、方位等)能按预定的规律变化，以保证产品的质量和提高产量。也可用于武器的控制，如火炮的自动控制系统，飞机的自动驾驶系统，以及导弹的制导系统等。123实时系统-实时信息处理系统指能对信息进行实时处理的系统。该系统由一台或多台主机通过通信线路连接成百上千个远程终端，计算机接收从远程终

41、端发来的服务请求，根据用户提出的问题，对信息进行检索和处理，并在很短的时间内为用户做出正确的回答。典型的实时信息处理系统有：飞机订票系统、情报检索系统等。124实时任务(real-time task)指，具有及时性要求的、常常被重复执行的特定进程，在实时系统中习惯称为任务。按任务执行时是否呈现周期性来分类：（1）周期性实时任务，要求按指定的周期循环执行，以便周期性地控制某个外部事件。（2）非周期性实时任务，任务的执行无明显的周期性，但都必须联系着一个截止时间(deadline)。125实时任务(real-time task)截止时间包括：开始截止时间（任务在某时间以前，必须开始执行）和完成截止

42、时间（任务在某时间以前必须完成）。根据对截止时间的要求将实时任务划分为：（1）硬实时任务，系统必须满足任务对截止时间的要求，否则可能出现难以预测的结果。（2）软实时任务，它也联系着一个截止时间，但并不严格,若错过了任务的截止时间，对系统产生的影响不会太大。 126实时调度的目标主要考虑如何使硬实时任务在其规定的截止时间内完成，同时，尽可能使软实时任务也能在规定的截止时间内完成。而公平性和最短平均响应时间等要求已不再重要。但是，大多数现代实时操作系统无法直接处理任务的截止时间，它们只能尽量提高响应速度，以尽快地调度任务。 127实时调度算法实时性要求不太高的实时系统可用的调度算法：基于时间片轮转

43、调度算法基于优先级的调度算法最早截止时间优先调度算法，即优先调度截止时间最近的实时任务。 128速度单调调度算法（Rate Monotonic Scheduling，RMS）根据任务的周期大小赋予优先级，最短周期的任务具有最高优先级。其中， - 任务周期（period），指一个任务到达至下一任务到达之间的时间范围。 - 任务速度（rate），即周期（以秒计）的倒数,以赫兹为单位。任务周期的结束，表示任务的硬截止时间。任务的执行时间不应超过任务周期。 129速度单调调度算法（Rate Monotonic Scheduling，RMS）在RMS调度算法中，如果以任务速度为参数，则优先级函数是一个单

44、调递增的函数，故称为速度单调算法。 该调度算法广泛用于工业实时系统的周期性任务调度。1301312.5 线程 132多线程 操作系统中引入进程的目的是，为了描述和实现多个程序的并发执行，以改善资源利用率及提高系统的吞吐量。为什么还需要引入线程呢？这是为了减少程序并发执行时系统所付出的额外开销，使操作系统具有更好的并发性。进程的两个基本属性：（1）进程是一个拥有资源的独立单位；（2）进程同时又是一个可以独立调度的基本单位。133系统为进程进行的操作 创建进程 、撤消进程 、进程切换 进程作为资源的拥有者和系统的调度对象，需要花费系统较大的额外开销。故，系统中同时存在的进程数目不宜过多，进程切换的

45、频率也不宜过高，而这也就限制了并发度的进一步提高。134由进程到线程目标：既能提高进程并发度，又能降低系统的额外开销。实现：将进程的资源申请和调度属性分开。即进程作为资源的申请和拥有者，但不作为调度的基本单位。这样，就产生了线程的概念。线程是进程中的一个实体，是独立调度和分派的基本单位。线程自身基本上不拥有系统资源，只拥有少许运行中必不可少的私有资源。线程可与同属一个进程的其它线程共享进程的全部资源。135线程的状态进程中的所有线程共享该进程的状态。线程具有三种基本状态：就绪、执行和阻塞。一般不具有挂起状态，因为线程共享进程的资源，包括存储空间，如果挂起一个进程，其所属的全部进程必将被挂起。而

46、单独挂起某进程中的一个线程，必然会影响同一进程中的其它线程的执行，这是没有任何意义的。 136对线程的操作一个进程可以创建和撤消一个或多个线程，同一进程中的多个线程可以并发执行。对线程的操作包括：派生(Spawn)，当系统创建一个进程时，同时也为该进程派生一个线程，同一进程中的线程可以再派生其它线程。阻塞(Block)，当线程需要等待某事件时，它将被阻塞，释放处理机执行其它线程。137对线程的操作3.解除阻塞(Unblock)，当线程的阻塞事件发生，其状态转换为就绪，并插入到就绪队列，等待调度执行。4.结束(Finish)，当线程执行完毕，释放其私有资源。注意，线程阻塞不一定会引起整个进程的阻

47、塞，否则，引入线程带来的并发性就不会提高。138进程与线程 传统操作系统中，一个进程可以创建一个线程， 如MS DOS就是一个单用户、单进程、单线程的操作系统，UNIX是一个多用户、多进程、单线程的操作系统。现代操作系统和软件设计大多支持多线程运行。例如，Java虚拟机是一个单进程、多线程的运行环境，Windows系列操作系统和Linux操作系统都采用了多进程、多线程技术。139进程与线程- 调度传统操作系统中，进程既是拥有资源的基本单位，又是独立调度的基本单位。引入线程的操作系统中，线程是独立调度的基本单位，进程是资源拥有的基本单位，从而可以显著地提高系统的并发程度。同一进程中的线程间切换不

48、会引起进程切换，但当一个进程中的线程切换到另一进程中的线程时，将会引起进程切换。140进程与线程-并发进程之间可以并发执行同属于一个进程的多个线程之间，亦可并发执行因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。141进程与线程-并发例如在一个未引入线程的单处理机操作系统中，若仅设置一个文件服务进程，当它由于某种原因而被阻塞时，便没有其它的文件服务进程来提供服务。引入线程以后，可以在一个文件服务进程中设置多个服务线程，当第一个线程阻塞时，文件服务进程中的第二个线程可以继续运行；当第二个线程阻塞时，第三个线程可以继续执行，从而显著地提高了文件服务的质量和系统吞吐量。 142进程与线程-拥有资源进程是拥有资源的独立单位，它有权申请系统的各类资源。线程除了拥有很少的私有资源以外，不能申请系统资源，可以共享其所属进程的资源。即，进程的代码段、数据段以