《操作系统第二章》word版.doc

操作系统 第二章 1第二章进程管理本章要点基础：进程描述及控制策略：进程调度实现：互斥与同步避免：死锁与饥饿解决：几个经典问题关于：进程通信2.1进程的引入程序顺序执行程序：源代码程序、目标程序和可执行程序程序执行：编辑、编译、链接、执行程序的结构：顺序结构、分支结构和循环结构程序顺序执行的特征：顺序性、封闭性、可再现性程序并发执行多道程序设计技术：多个程序并发执行程序并发执行时的特征间断性、非封闭性、不可再现性。程序并发执行引发的问题协调各程序的执行顺序例如，当输入的数据还未全部输入内存时，计算必须等待多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果选择哪些、多少个程序进入内存执行?内存中的执行程序谁先执行内存如何有效分配?进程的概念定义：可并发执行的程序，在一个数据集合上的运行过程。申请/拥有资源调度(线程)程序：静态概念，是指令和数据的集合，可长期存储进程与程序对应关系一个程序可以对应一个进程或多个进程一个进程可以对应一个程序，或者一段程序进程的特征动态性并发性独立性异步性引入进程带来的问题增加了空间开销：为进程建立数据结构额外的时间开销：管理和协调、跟踪、填写和更新有关数据结构、切换进程、保护现场更难控制：协调多个进程竞争和共享资源如何预防解决多个进程因为竞争资源而出现故障处理机的竞争尤为突出进程的结构组成(进程映像)：程序、数据集合、进程控制块PCB(Process Control Block)PCB是进程存在的唯一标志。创建进程时，创建PCB；进程结束时，系统将撤销PCB PCB进程标识信息：进程的内部和外部标识符处理机状态信息：通用寄存器值、指令寄存器值、程序状态字值、用户栈指针值进程调度信息：进程状态、进程优先权、进程调度的其他信息其他信息：程序及数据地址、进程同步和通讯机制、资源清单、链接指针PCB的组织方式单队列所有进程的PCB通过链表组织成为一个单一队列。适用于进程数目不多的系统。(过多导致查找过于频繁)如，Windows操作系统表格结构PCB按进程状态不同，组织成不同的表格：就绪进程表、执行进程表(多级系统中)及阻塞进程表系统分别记载各PCB表的起始地址。多级队列PCB按进程状态不同用链接指针组成不同队列：就绪进程队列、阻塞进程队列(可按阻塞原因不同，分别组织)系统分别记载各PCB链表的起始地址2.2进程的状态进程执行轨迹进程的轨迹：进程执行的指令序列，用以观察处理机的执行过程两状态进程模型两状态：执行、未执行进程获得处理机，进入执行状态；当时间片结束或其它某种原因，进程释放处理机，暂停执行，处于未执行状态两状态进程模型：1队列形式注：并非所有进程只要未执行就处于就绪，有的需要阻塞等待I/O完成未执行又分为就绪和阻塞进程的五状态执行状态(Running)就绪状态(Ready)阻塞状态(Blocked)新状态(NEW)终止状态(Terminated)1新状态：进程已经创建，但未被OS接纳为可执行进程2就绪状态：准备执行3执行状态：占用处理机(单处理机环境中，某一时刻仅一个进程占用处理机)4阻塞状态：等待某事件发生才能执行，如等待i/0完成等5终止状态：因停止或取消，被OS从执行状态释放。空-新状态新创建的进程首先处于新状态新状态就绪状态当系统允许增加就绪进程时，操作系统接纳新建状态进程，将它变为就绪状态，插入就绪队列中。就绪状态执行状态当处理机空闲时，将从就绪队列中选择一个进程执行，该选择过程称为进程调度，或将处理机分派给一个进程，该进程状态从就绪转变为执行。执行状态终止状态执行状态的进程执行完毕，或出现诸如访问地址越界、非法指令等错误，而被异常结束，则进程从执行状态转换为终止状态。执行状态就绪状态分时系统中，时间片用完，或高优先级的进程到来，将中断较低优先级进程的执行。进程从执行状态转变为就绪状态，等待下一次调度。执行状态阻塞状态执行进程需要等待某事情发生。通常，会因为进程需要的系统调用不能立即完成，如读文件、共享虚拟内存、等待i/0操作、等待另一进程与之通信等事件而阻塞。阻塞状态就绪状态当阻塞进程等待的事情发生，就转换为就绪状态。进入就绪队列排队，等待被调度执行。注：某些系统允许父进程在任何情况下终止其子进程。如果一个父进程被终止，其子孙进程都必须终止。新状态终止就绪状态终止阻塞状态终止问题：多个进程竞争内存资源内存资源紧张无就绪进程，处理机空闲：i/0的速度比处理机的速度慢得多，可能出现全部进程阻塞等待i/0解决方法采用交换技术：换出一部分进程到外村，以腾出内存空间。采用虚拟存储技术：每个进程只能装入一部分程序和数据(存储管理部分)对换技术，交换技术(Swapping)将内存中暂时不能运行的进程，或暂时不用的数据和程序，换出到外村，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的数据和程序，换入内存。注：通常PCB并不换到外存进程的挂起状态进程被交换到外存，状态变为挂起状态进程挂起的原因进程全部阻塞，处理机空闲。系统负荷过重，内存空间紧张。操作系统的需要。操作系统可能需要挂起后台进程或一些服务进程，或者某些可能导致系统故障的进程。终端用户的请求父进程的需求被挂起进程的特征不能立即执行可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能执行。使之挂起的进程为；自身、其父进程、OS只有挂起它的进程才能使之由挂起状态转换为其他状态。挂起于阻塞问题1.是否只能挂起阻塞进程?2.如何激活一个挂起进程?区分两个概念进程是否等待事件，阻塞与否进程是否被换出内存，挂起与否4种状态组合就绪：进程在内存，准备执行阻塞：进程在内存，等待事件就绪/挂起：进程在外存，只要调入内存即可执行阻塞/挂起：进程在外存，等待事件注：处理机可调度执行的进程有两种：新创建的进程或换入一个以前挂起的进程通常为避免增加系统负载，系统会换入一个以前挂起的进程执行。具有挂起状态额进程状态转换图2.3进程的控制两种执行模式系统模式(又称为系统态)、控制模式或内核模式1具有较高的特权2运行系统特定的指令，包括读.写控制寄存器的指令、基本i/0指令以及与存储器管理有关的指令，及一些特定的内存区3内核模式下的处理机机器指令、寄存器和内存都受到完全控制和保护用户模式(或用户态)1具有较低的特权2用户程序一般运行在用户模式模式切换用户模式-系统模式：用户程序执行到一条系统调用，进入操作系统内核执行系统模式-用户模式：执行完系统调用的功能，返回到用户程序。特殊情况：程序执行到结束语句时，切换到系统模式，不再返回到用户程序。操作系统内核(Kernel)操作系统的核心，是基于硬件的第一层软件扩充，提供操作系统最基本的功能，是操作系统工作的基础现代操作系统设计中，为减少系统本身的开销，往往将一些与硬件紧密相关的(如中断处理程序、设备驱动程序等)、基本的、公共的、运行频率较高的模块(如时钟管理、进程调度等)以及关键性数据结构独立开来，使之常驻内存，并对它们进行特殊保护。通常把这一部分称为操作系统的内核。3.用户通过系统调用访问操作系统的功能，这些功能最终都通过操作系统内核实现。4不同的操作系统对内核的定义和功能范围的设定是不同的5一般地，操作系统内核的功能可以概括地分为资源管理功能和支撑功能。资源管理；进程管理、存储管理和i/0设备管理支撑功能：中断处理、统计、检测、时钟、管理、原语操作等资源管理功能1进程管理：进程创建和终止、调度、状态转换、同步和通信、管理PCB 2存储管理：为进程分配地址空间、兑换、段/页管理i/0设备管理：缓存管理、为进程分配i/0通道和设备支撑功能中断处理时钟管理原语(Primitive)：原子操作统计监测进程控制原语进程切换创建与终止阻塞与唤醒挂起与激活进程创建：原因提交新的批处理作业交互式用户注册操作系统提供服务父进程创建子进程进程创建：步骤1.为进程分配一个唯一标识号ID主进程表中增加一个新的表项2.为进程分配空间：用户地址空间、用户栈空间、PCB空间。若共享已有空间，则应建立相应的链接3.初始化PCB：进程标识、处理机状态信息、进程状态4.建立链接：若调度队列是链表，则将新进程插入到就绪或就绪/挂起链表5.建立或扩展其他数据结构进程终止：原因批处理作业执行到结束语句交互式用户注销停止进程(应用程序)的执行遇到错误或故障进程终止：具体原因正常结束超时终止，执行时间超过预计时间内存不足，无法为进程分配所需的内存空间越界访问企图使用未允许用的数据，或操作方式错计算错，如除零，或企图存储硬件允许的最大数超时等待某事件发生i/0失败，如找不到文件或多次重试仍无法读写文件，或无效操作无效指令，企图执行不存在的指令特权指令，企图执行特权指令数据类型不符，或未初始化操作员或OS干预，如发生死锁的时候父进程终止父进程请求进程终止：步骤1.根据被终止进程的标识符ID，找到其PCB，读出该进程的状态2.若该进程为执行状态，则终止其执行，调度新进程执行。3.若该进程有子孙进程，则立即终止其所有子孙进程4.将该进程的全部资源，或归还给其父进程，或归还给系统5.将被终止进程的PCB从所在的队列中移出，等待其它程序来所及信息。进程的阻塞与唤醒阻塞原因：请求系统服务；启动某种操作，如i/0；新数据尚未到达；暂时无新工作可做等当出现阻塞事件，进程调用阻塞原语将自己阻塞。并将其状态变为阻塞状态，并进入相应事件的阻塞队列。当阻塞进程期待的事件发生，有关进程调用唤醒原语，将等待该事件的进程唤醒。并将其状态变为就绪状态，插入就绪队列一般，进程可以自己阻塞自己；而唤醒操作则由操作系统，或其它相关进程来完成，进程无法自己唤醒自己进程的挂起与激活当出现挂起事件，系统利用挂起原语将指定进程或一个阻塞进程挂起。进程从内存换出到外存，其状态转换：就绪-就绪/挂起或阻塞-阻塞/挂起当激活事件发生，系统利用激活原语将指定进程激活。将相应进程从外存换入到内存，可能的状态转换：就绪/挂起-就绪，或阻塞/挂起-阻塞进程切换时钟中断进程执行完一个时间片i/0中断内存访问出错虚拟存储中，需要的指令或数据不在内存陷阱执行遇到错误可能使进程转换到终止状态进程A切换到进程B的步骤进程切换vs模式切换进程切换，作用于进程之间的一种操作。当分派程序收回当前进程的CPU并准备把它分派给某个就绪进程时，该操作将被引用。模式切换，是进程内部所引用的一种操作。当用户程序转入系统调用，或相反时，该操作将被引用。进程切换一定引发模式切换，反之则不然2.4进程调度什么是调度调度是指，在一个队列中，按照某种方法(算法)，选择一个合适的个体的过程。调度的关键是需要某种方法或算法，好的调度算法有利于选择到合适的个体如何判断、设计一个号的地阿杜算法呢?调度目标公平性，防止进程长期不能获得调度而饥饿；处理机利用率，尽量提高处理机的利用率；提高系统吞吐量；尽量减少进程的响应时间调度原则满足用户的要求；相应时间、周转时间、截止时间满足系统的需求：系统吞吐量、处理机利用率、各类资源的平衡使用、公平性及优先级面向用户的原则：响应时间是指，从用户通过键盘提交一个请求开始、直到系统首次产生响应为止的时间。输入的请求传送到处理机的时间处理机对请求信息进行处理的时间将响应结果发送到输出终端的时间响应时间调度算法则应考虑尽可能使绝大多数用户的请求能在响应时间内完成。常用于评价分时系统的性能面向用户的原则：周转时间指从作业提交给系统开始，到作业完成为止的这段时间间隔作业在外存排队等待调度的时间进程在就绪队列中等待调度的时间进程被处理机执行的时间等待I/O操作完成的时间周转时间常用于评价批处理系统的性能影响周转时间的调度作业从外存调度到内存(作业调度)进入内存还需在就绪队列中排队，等待进程调度甚至，可能会挂起进程，在外存等待被激活(中程调度)面向用户的原则：截止时间指实时系统中，某任务必须开始执行的最迟时间，或必须完成的最迟时间常用于评价实时系统的性能。面向系统的原则：处理机利用率大、中型多用户系统，由于处理机价格昂贵，处理机利用率是衡量系统性能的一个重要指标单用户微机或某些实时系统，则并非很重要。面向系统的原则：各类资源的平衡使用多道程序系统的目标之一就是为了提高系统资源的利用率，因此，调度算法有责任使系统中的各种资源都尽量处于忙碌状态。该原则同时适用于长程调度和中程调度，因为他们可以决定哪些作业(进程)可以进入内存，可以考虑系统资源的均衡使用。面向系统的原则：优先权优先权高的进程应优先调度可以根据进程的优先权不同，组织不同的就绪队列。进程调度时首先选择高优先权队列中的进程，直到该队列空，再调度较低优先权队列中的进程，几乎所有操作系统的调度算法都可考虑优先权原则。当然，仅考虑优先权，可能会出现饥饿，对低优先权的进程不公平。可以将进程排队的等待时间等因素纳入优先权的计算，随着进程等待时间的增长，其优先权也不断提高，进程也会在不久的将来得到调度。进程调度方式根据执行进程的处理机是由进程自己释放，还是被强行剥夺，可以将进程调度方式分为非剥夺方式和剥夺方式两种。非剥夺方式执行进程只有在执行完毕，或因申请i/0阻塞自己时，才中断其执行，释放处理机，调度新的进程执行、这种方式不利于即时性要求较高的分时和实时系统。主要用于批处理系统。剥夺方式操作系统可以在新进程到来时，或某个具有较高优先权的被阻塞进程插入就绪队列时，活在基于时间片调度的系统中，时间片用完而中断当前进程的执行，调度新的进程执行。这种方式会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统和分时系统。调度的类型批处理调度、分时调度、实时调度和多处理机调度长程调度、中程调度、短程调度i/0调度长程调度又称为高级调度，或作业调度，它为被调度作业或用户程序创建进程，分配必要的系统资源，并将新进程插入就绪队列，等待短程调度。某些采用交换技术的系统将新创建的进程插入到就绪/挂起队列，等待中程调度。在批处理系统中，作业进入系统后，先驻留在磁盘上，组织成批处理队列，称为后备队列。长程调度从该队列中选择一个或多个作业，为之创建进程。长程调度需要考虑两个问题1.选择多少个作业进入内存，为之创建进程?取决于多道程序的度，即允许同时在内存中运行的进程数。2.选择哪些作业?取决于长程调度算法。短程调度也称进程调度，或低级调度，决定就绪队列中的哪个进程将获得处理机。短程调度运行频率最高。现代操作系统几乎都具有段程调度工程。中程调度又称为中级调度。它是对换功能的一部分当内存空间非常紧张时，或处理机找不到一个可执行的就绪进程时，需要选择一个进程(阻塞或就绪状态)换出到外存，释放出内存空间给别的进程使用；当内存空间较充裕时，从外存选择一个挂起状态的进程调度到内存(换入)。阻塞/挂起到就绪/挂起不需要调度，只需等待事件结束目的：为了提高内存的利用率和系统吞吐量。只有支持进程挂起的操作系统才具有中程调度功能。进程调度算法先来先服务(FCFS)该方法按照进程到达的先后顺序排队，每次调度队首的进程。FCFS算法属于非剥夺调度方式，实现简单，看似公平。但，对于那些后进入队列而运行时间较短的进程，或i/0型的进程而言，可能需要长时间等待。分析：对短进程不公平由于长进程可能排在队列前面，必将增加队列后部进程的等待时间，从而将增加平均周转时间。不利于i/0型进程，未有效利用系统资源。一般地，FCFS与其他调度算法混合使用。例如，系统可以按照不同的优先级维护多个就绪队列，每个队列内部按照FCFS算法调度。FCFS算法同时适合于长城、中程和短程调度三种调度类型。短进程优先当需要调度进程(或作业)时，通过计算判断就绪进程队列中哪个进程的预期执行时间最短，或后备作业队列中哪一个或几个作业的预期时间最短，就调度谁属于非剥夺调度算法。当某进程获得处理机，直到其执行完成，或需要等待某事件而阻塞时，才自动释放处理机。系统又调度新的进程(或作业)短进程优先与FCFS算法比较，短进程优先调度算法改善了系统的性能，降低了系统的平均等待时间，提高了系统的吞吐量。但是，该算法也存在一些问题：1很难准确预测进程的执行时间。2可能导致长进程饥饿，这对长进程不公平；3采用非剥夺调度方式，未考虑进程的紧迫程度，不适合于分时系统和事物处理系统。时间片轮转调度法1在分时联机系统中，n个进程循环地获得时间片儿执行。从系统中来看他们是交替执行的，但就每个终端用户而言，都感觉到自己独占了一台主机，不受其他用户的影响。这是通过进程并发执行实现的。2如果用户数太多，主机处理的进程将会剧增加，进程排队等待的时间也会很长，进程的响应时间也可能增长，用户将明显感觉到主机的速度变慢而不满意。3另外，时间片的大小也会影响进程的响应时间。时间片的设置1进程切换将会增加系统的额外开销。2时间片设定得太短，进程切换会非常频繁，而降低处理机的效率；时间片设定的太长，将无法满足交互式用户对响应时间的要求。3因此，时间片大小的确定应综合考虑系统的最大用户数、响应时间、系统效率等多种因素。时间片轮转调度法为了简单，图中忽略了进程切换时的系统开销，而实际操作系统中，这类额外开销是客观存在的。可见，采用基于时间片轮转调度法，进程的周转时间和平均周转时间并不比采用FCFS和短进程优先调度算法小。加上进程切换所需的系统开销时间，该算法的平均周转时间还会增长。时间片轮转调度法常用于分时系统及事务处理系统，合理的时间片大小将带来满意的响应时间。通常，合理的时间片指，能让80%左右的进程在一个时间片内完成。对于短的、计算型的进程较有利。不适合于批处理系统的进程调度。不利于批处理系统的进程调度。不利于i/0型的进程。改进的方法之一，可以将i/0阻塞事件完成的进程单独组织一个就绪队列，该队列进程的时间片可以设置的小一些，且优先调度。基于优先级的调度算法基于时间片轮转调度法循环式地为每个被调度的进程分配一个时间片，对每个进程都是公平的。然而，实际应用中，进程的性质可能是不同的。例如，一个与用户进行交互的前台进程击破地需要对用户的输入做出响应，而一个后台打印进程的迫切性也许就不那么重要。因此，可以为每个进程定义一个优先级，优先级越高的进程将优先获得处理机的调度。如何设定进程的优先级进程完成功能的重要性进程完成功能的急迫性为均衡系统资源的使用，指定进程(作业)优先级进程对资源的占用程度例如，可以为短进程(或作业)赋予较高的优先级。静态与动态优先级静态优先级：一旦确定，则进程运行期间优先级一直不改变。动态优先级：系统首先赋予进程一个初始优先级，该优先级将随着进程的运行而改变。动态优先级典型的动态优先级变化方式为：优先级随着进程运行的剩余时间的减少而上升，使简要执行结束的进程尽快完成；或随着进程排队等待时间的增长而上升，使等待时间越长的进程优先得到调度，不至于长时间饥饿。具体实现方法，可以在每个时钟中断时，或需要进程切换时，重新计算就绪队列中各进程的优先级，并优先调度高优先级的进程。采用动态优先级的两种调度算法：剩余时间最短者优先和响应比高者优先。剩余时间最短者优先为了使将要结束的进程尽早结束，释放系统资源，让别的进程执行。可以在每个时钟中断时，根据就绪队列中各进的剩余执行时间动态调整其优先级，剩余时间最短的进程优先级最高。显然，该算法是剥夺型的短进程优先调度算法，调度程序总是选择剩余执行时间最短的进程调度执行。存在问题与短进程优先调度算法一样，该调度算法很难准确估计进程的剩余执行时间由于长进程在未执行时，或刚开始执行的一段时间内，其剩余执行时间都不会最短，所以该算法对长进程不公平。但是，它不像FCFS算法偏袒长进程，也不像轮转调度算法会产生很多中断而增加系统负担。由于短进程提前完成，故采用剩余时间最短者优先的调度算法获得的平均周转时间比采用短进程优先算法短。响应比高者优先将进程的等待时间和进程的预期执行时间纳入优先级的计算，进程(预期执行时间)越长优先级越低，而随着进程的等待时间增长优先级上升，即进程的优先级与等待时间成正比，与进程执行那个时间成反比。令w表示等待时间，s表示预期执行执行时间，则响应比：R=w/s+1调度方法：若当前执行进程执行完毕，或需要阻塞等待某事件而释放处理机，调度程序选择就绪队列中响应比最大的进程执行。若等待时间相同，短进程因为s较小，R较大而优先调度。若进程的预期执行时间相同，则等待时间长的进程优先调度，相当于FCFS。随着等待时间的增加，长进程的响应比不断增大，在某个时刻，也必然被调度。评价同短进程优先和剩余时间最短者优先调度算法一样，很难准确估计进程的预期执行时间。每次调度之前都需要计算响应比，增加了系统开销。反馈调度法前面介绍的几种调度算法都存在各自不同的问题，尤其是短进程优先、剩余时间最短者优先以及响应比高者优先调度算法都需要估计进程的预期执行时间，如果估计不准确，将影响调度结果和系统性能。如果根据进程执行历史，而非未来，进行调度，将解决这个问题。反馈调度法就是一种根据进程执行历史调整调度方式的调度方法，它结合了优先级和时间片轮转调度思想。反馈调度法该方法有利于交互型短进程或短批处理作业，因为他们一般只需要一个或很少的几个时间片即可完成，但可能使长进程的周转时间急剧增加。如果不断地有新进程到来，还可能出现长进程长期饥饿现象。为此，可以为各队列设置不同的时间片，优先级越低时间片越长。若队列中只有一个进程执行完是否会中断?中断前提是有新进程到来或处理机空闲，所以没必要中断若有新进程到来，按时间片原则到时间片到则中断若就绪队列1中正在执行，有新进程进入就绪队列0，进程怎么执行注意是单处理机，时间片到会中断，若没有执行完进入下一就绪队列，而调度高优先级的进程进入就绪队列0，然后执行。进程调度算法小结1如何选择进程调度算法与系统设计的目标有关.2交互式多任务系统，主要考虑联机用户对响应时间的要求，一般采用基于时间片轮转调度算法，同时，根据进程的性质设置不同的优先级；批处理系统往往以作业的平均周转时间按来衡量调度性能，常选用基于优先级的短进程(或作业)优先调度算法。实时系统指，能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行的计算机系统。分为实时控制系统和实时信息处理系统。实时控制系统指要进行实时控制的系统主要用于生产过程的控制，实时采集现场数据，并对所采集的数据进行及时