操作系统论文 处理机调度及算法.doc

处理机调度及算法摘要：在多道程序环境中，进程数往往多于处理机数，这必然引起多个程序对处理机的竞争问题，分配处理机的任务是由处理机调度程序完成的。处理机调度是操作系统核心的重要组成部分。一个作业从提交到执行，要经过三级调度。处理机常用的调度算法有先来先服务调度算法、短作业或短进程优先调度算法（SJF/SPF）、时间片论转调度算法（RR）、最高优先权优先调度算法（HPF）、最高响应比优先调度算法（HRP）多级反馈队列调度算法。在实时系统中存在若干实时任务，这些任务对时间有严格要求，并带有某种程度的紧迫性。关键词：处理机 调度算法 实时系统处理机调度即进程调度。在多道程序环境中，进程数往往多于处理机数，这必然引起多个程序对处理机的竞争问题，分配处理机的任务是由处理机调度程序完成的。如何提高处理机的利用率，在很大程度上取决于调度算法性能的好坏。处理机调度的目的是满足系统响应时间、吞吐量、处理机的效率等要求，一个作业被提交后，必须经处理机调度后，才能获得执行权力。一个作业从提交到执行，往往要经过三级调度。一般情况下，当占用处理机的进程因为某种请求得不到满足而不得不放弃CPU进入等待状态时，或者当时间片到，系统不得不将CPU分配给就绪队列中另一进程的时候，都要引起处理机调度。除此之外，进程正常结束、中断处理等也可能引起处理机的调度。处理机调度是操作系统核心的重要组成部分。要记住进程的状态，如进程名称、指令计数器、程序状态寄存器以及所有通用寄存器等现场信息，将这些信息记录在相应的进程控制块中。然后根据一定的算法，决定哪个进程能获得处理机，以及占用多长时间。最后收回处理机，即正在执行的进程因为时间片用完或因为某种原因不能再执行的时候，保存该进程的现场，并收回处理机。处理机调度的功能中，很重要的一项就是根据一定算法，从就绪队列中选出一个进程占用CPU运行。可见，算法是处理机调度的关键。一个作业从提交到执行，往往要经过三级调度，即高级调度、低级调度和中级调度。高级调度又称作业调度，用于决定把外存中处于后备队列中的哪些作业调入内存。当作业调入内存后，为之分配必要的资源，创建进程，入就绪队列。低级调度又称进程调度，用于决定就绪队列中的哪个程序获得处理机，这个程序由分派程序来完成。剥夺方式（抢占方式）允许进程调度程序根据某种策略终止当前正在运行的程序，将其转入就绪队列，并根据某种调度算法选择另一个进程投入运行。剥夺原则：1.优先权原则；2.短作业（进程）优先原则；3.时间片原则。非剥夺方式（非抢占方式）：在这种进程调度方式下，一旦一个进程被选中投入运行，它就一直运行下去，直到完成工作或自愿放弃CPU，或因某事件而被阻塞为止，才把CPU让给其他进程。这种调度方式优点是实现简单、系统开销小，适于大多是批系统处理环境，但它难以满足紧急任务的要求。中级调度又称对换功能，用于把那些暂时不能运行的进程调到外存去等待（挂起状态），当它们又具备运行条件且内存空闲时，决定将外存那些重新又具备运行条件的就绪进程，重新又调入内存，并修改其状态为就绪状态，入就绪队列。中级调度的运行频率介于高级调度与低级调度之间。处理机常用的调度算法有先来先服务调度算法、短作业或短进程优先调度算法（SJF/SPF）、时间片论转调度算法（RR）、最高优先权优先调度算法（HPF）、最高响应比优先调度算法（HRP）多级反馈队列调度算法。先来先服务调度算法基本思想是按作业（进程）到达时间先后顺序依次使用CPU。适用于作业/进程调度。非抢占调度方式。优点是实现简单。缺点是未考虑进程的优先级或紧急性，不利于短作业（进程）的运行，利于CPU繁忙型作业，而不利于I/O繁忙型作业。很少单独使用，常与其他 算法结合使用（辅助算法）。所以这种算法容易实现，但效率低。短作业（进程）优先调度算法基本思想是选择就绪（后备）队列中估计运行时间最短的进程（作业）投入运行。适用于作业/进程调度。非抢占调度方式最短剩余时间优先算法或抢占调度方式。优点是有效缩短作业的平均周转时间，从而提高系统吞吐量。缺点是不利于长作业和紧迫作业的运行（无法满足公平性，估计有主观性）。所以这咱算法容易实现，且效率比较高，但未考虑作业的利益。高优先权优先调度算法基本思想是选择优先级最高的进程或作业投入运行。适用于作业/进程调度。非抢占调度方式批处理系统“等你打完我再打”抢占调度方式实时系统 “不等你打完电话，抢过话筒就打”优先级（优先权）即优先数，是由系统或用户按某种原则指定的，一般用整数表示。（1）静态优先权“一定终身”是在创建进程/作业时确定的，且在整个运行期间保持不变。优先级的确定依据：用户要求、进程/作业类型、对资源的要求不同系统有不同的确定原则，及表求方法。优点是简单易行，系统开销小。缺点是不够精确，可能出现某些低优先级的进程永不能被执行。动态优先权是在创建进程/作业时赋予的优先级，可随着进程的推进而改变。决定/动态改变因素：等待时间、已使用处理机的时间、其他资源的使用情况等。特点是可防止低优先级的进程/作业长时间得不到调度。高响应比优先调度算法实际上是一种动态优先权调度算法。响应比R = 响应时间 / 要求服务时间=（等待时间 + 运行时间）/ 运行时间= 1 +（等待时间 / 运行时间） 基本思想是同时兼顾每个作业等待时间和运行时间两方面因素，选择响应比最高的作业/进程投入运行。优点是利于短作业，利于长作业。缺点：系统开销大。多级反馈队列调度算法是时间片轮转算法的发展，其出发点是为照顾各种作业/进程。基本思想是系统中设置有多个不同优先级的就绪队列，且每个队列具有不同的时间片，使优先级愈高的队列时间片愈小。各个队列按照FCFS调度算法，而最后一级则时间片轮转。一个新进程就绪后进入第一级队列。进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列。当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾。当第一队列空时，就去调度第二级队列，依次类推。当时间片到后却还未完成的进程，则必须放弃CPU，回到下一级队列。优点是有较好的性能，能满足各类型用户需要。 在实时系统中存在若干实时任务，这些任务对时间有严格要求，并带有某种程度的紧迫性。之前所描述的多种调度算法并不能很好的满足实时系统对调度的要求，为此，引入一种新的调度，即实时调度。实时系统的任务具有一定的时间约束（截止时间）。根据截止时间，实时系统的实时性分为“硬实时”和“软实时”。硬实时是指应用的时间需求能够得到完全满足，否则就造成重大安全事故，甚至造成重大的生命财产损失和生态破坏，如在航空航天、军事、核工业等一些关键领域中的应用。软实时是指某些应用虽然提出时间需求，但实时任务偶尔违反这种需求对系统运行及环境不会造成严重影响，如监控系统等和信息采集系统等。可预测性是指系统能够对实时任务的执行时间进行判断，确定是否能够满足任务的时限要求。由于实时系统对时间约束要求的严格性，使可预测性称为实时系统的一项重要性能要求。除了要求硬件延迟的可预测性以外，还要求软件系统的可预测性，包括应用程序的响应时间是可预测的，即在有限的时间内完成必须的工作；以及操作系统的可预测性，即实时原语、调度函数等运行开销应是有界的，以保证应用程序执行时间的有界性。大多数实时系统要求有较高的可靠性。在一些重要的实时应用中，任何不可靠因素和计算机的一个微小故障，或某些特定强实时任务（又叫关键任务）超过时限，都可能引起难以预测的严重后果。为此，系统需要采用静态分析和保留资源的方法及冗余配置，使系统在最坏情况下都能正常工作或避免损失。可靠性已成为衡量实时系统性能不可缺少的重要指标。实时系统通常运行在一定的环境下，外部环境是实时系统不可缺少的一个组成部分。计算机子系统一般是控制系统，它必须在规定的时间内对外部请求做出反应。外部物理环境往往是被控子系统，两者互相作用构成完整的实时系统。大多数控制子系统必须连续运转以保证子系统的正常工作或准备对任何异常行为采取行动。早期的实时系统功能简单，包括单板机、单片机，以及简单的嵌入式实时系统等