您好、欢迎来到现金彩票网!
当前位置:红彩会 > 分派优先级 >

操作系统8————处理机调度

发布时间:2019-08-17 12:28 来源:未知 编辑:admin

  在多道程序系统中,调度实质是一种资源分配,处理就调度算法是指根据处理机分配策略所规定的处理机分配算法。一个作业从获得处理机执行到作业运行完毕,可能会经历多级处理机调度。下面介绍处理机的层次。

  高级调度又称为长程调度或者作业调度,它的调度对象是作业。主要功能是根据某种算法,决定将外存上处于后备队列中那几个作业调入内存,为它们创建进程,分配必要的资源,并将它们放入就绪队列。高级调度主要用于多道批处理系统,而在分时和实时系统中不设置高级调度。作用调度的频率很低,周期很长,大于几分钟一次。

  低级调度有称进程调度或者短程调度,它的调度对象是进程。其主要功能是,根据某种算法,决定就绪队列中的那个进程获得处理机。并由分派程序将处理机分派给选择的进程。进程调度这是一种最基本的调度,在多道批处理,实时和分时三种类型的OS中,都必须配置这级调度。进程调度的频率很高,周期很短,在分时系统中大概仅10~100nm.

  中机调度又称为内存调度,引入中级调度的主要目的是,提高内存利用率和系统吞吐量。中级调度的作用就是讲暂时不能运行的进程,调至外存等待(挂起转台),和将外存上已经满足条件的就绪进程在调入内存中。内存调度的频率和周期处于,作业调度和内存调度之间。

  a.资源利用率:为了提高资源的利用率,应使系统中的处理机和其他所有资源尽可能保持忙碌状态。

  **b.公平性:**公平性是指应使诸进程都获得合理的CPU时间,不会发生进程饥饿现象。但公平是相对的,对于相同类型的进程应获得相同的服务,对于不同类型的进程,由于其紧急程度和重要性不同,提供不同的服务。

  **c.平衡性:**为使系统中CPU和各种外部设备都能经常处于忙碌状态,调度算法应保存系统资源使用的平衡性。

  d.策略强制执行:对所指定的策略其中也包括安全策略,只要需要,就必须提供。

  b.系统吞吐量高:吞吐量是指单位时间内系统完成的作业数,如果单纯为了获得高的系统吞吐量,那么就应该尽可能选择短作业运行。

  c.处理机利用率高:如果单纯为获得处理机利用率高,那么应该尽可能选择长作业运行。

  a.相应时间快:响应时间是指,是从用户通过键盘提交一个请求开始,直到屏幕上显示处理结果为止那一段时间。

  b.均衡性:用户对于响应时间的要求并非完全相同,用户对于简单的任务要求响应时间短,复杂任务时间允许较长。

  **a.截止时间的保证:**截止时间是指:某任务必须开始执行的最迟时间,或者必须完成的最初时间。对于严格的实时系统,其调度方式和调度算法必须要保证这一点。

  作业(Job): 作业是一个比系统更广泛的概念,它不仅包含了通常的程序和数据,而且还应配有一份作业说明书,系统根据该说明书来对程序的运行进行控制。在批处理系统中,是以作业为基本单位从外存调入内存。

  作业步(Job Step):在作业运行期间,每个作业都必须经过若干相互独立又相互关联的顺序加工步骤才能得到结果。我们把其中每一步称为一个作业步。例如,一个典型的作业步可以分为:“编译”作业步,“链接装配”作业步,和“运行”作业步。

  和进程线程类似,作业中也包含一个作业控制块(JCB)。通常JCB包含:作业标识,用户名称,用户账号,作业类型,作业专业,调度信息,资源需求,资源使用情况。

  作业从进入系统到运行,通常要经历收容,运行和完成阶段,相应的也就有了“收容状态” “运行状态” “完成状态”。

  a.收容状态:操作员把用户提交的作业通过某种方式或SPOOLing系统输入到硬盘上,在为该作业建立JCB,并把它放入作业后备对列中。

  **b.运行状态:**当作业被作业调度选中后,边为它分配必要的资源和建立进程,并把他放入就绪队列。

  c.完成状态:当作业运行完成,或发生异常情况而提前结束时,作业便进入了完成阶段。

  作业调度的主要任务就是根据JCB中的信息,检查系统中的资源能否满足作业队资源的要求,以及按照一定的调度算法,从外存的后备对列选取某些作业调入内存。在每次执行作业调度时,都需要做出以下两个决定:

  **a.接纳多少个作业:**接纳多少作业取决于多道程序度。而多道程序度取决于:计算机系统规模,运行速度,作业大小,以及能否获得较好的系统性能.

  b.接纳哪些作业:选择哪些作业取决于,作业调度采用哪种算法,常见的算法如下

  先来先服务算法,既可以用于作业调度,也可以用于进程调度。当作业调度中采取该算法时,系统将按照作业到达的先后次序来进行调度。

  在系统调度中采用FCFS算法时,每次调度是从就绪的进程队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或者阻塞时,进程调度程序才会将处理机分配给其他进程。

  FCFS算法在单处理机系统中以及很少作为主调度算法,但经常把它和其他调度算法结合使用,形成一种更为有效的调度算法。例如,可以在系统中按进程的优先级设置多个队列,每一个优先级一个队列,其中每一个队列的调度都基于FCFS。

  SJF算法是以作业的短来计算优先级,作业越短,其优先级越高。作业的长短是以作业所要求的时间来衡量的。SJF也可以分别用于作业调度和进程调度。但用于进程调度时优于作业调度。

  优先级调度算法也是既可以用于作业调度,也可以用于进程调度。FSFC和SJF算法都无法使紧迫性的作业得到尽快的处理,而PSA正是基于作业的紧迫程度,由外部赋予的作业优先级,进行作业调度。

  FSFC算法值考虑的作业的等待时间,SJF只考虑的作业的需要运行时间。而HRRN则既考虑了作业的等待时间,又考虑的作业的紧迫时间,从而改善了处理机调度的性能。

  优先权=等待时间+要求服务的时间要求服务的时间优先权= \frac{等待时间+要求服务的时间}{要求服务的时间}优先权=要求服务的时间等待时间+要求服务的时间

  优先权=Rp=响应时间要求服务的时间优先权=R_p= \frac{响应时间}{要求服务的时间}优先权=Rp=要求服务的时间响应时间

  如果作业的等待时间相同,这要求服务的时间越短,则优先权越大。此时类似于SJF算法。

  当要求服务的时间相同时,作业的优先权又决定于其等待时间。此时类似于FCFS算法。

  对于长作业的优先权,可以随等待时间的增加而提高。当其等待时间足够长,也可以获得处理机。避免出现饥饿现象。

  排队器:为了提高进程调度的效率。应事先将系统中的所有就绪进程按照一定策略排成一个或多个队列,以便调度程序能最快的找到它。以后每当有一个进程转换为就绪状态时,排队器便把它插入到相应的就绪队列中。

  分派器:分派器依据调度程序所选定的进程,将其从就绪队列取出,然后进行从分派器到新选的进程间的上下文切换,将处理机分配给新选出的进程。

  上下文切换器:在对处理机进行切换时,会发生两对上下文的切换操作。①第一对上下文切换时,OS保存当前进程的上下文,即把当前进程的处理机寄存器内部保存到该进程的PCB中,再装入分派程序的上下文。以便分派程序运行。②第二对上下文切换是移出分派程序的上下文。把新选进程的CPU现场信息装入到处理机的各个相应寄存器中,以便新选进程运行。

  采用这种调度方式时,一旦把处理机分配给某进程后,就一直让他运行下去,绝不会因为时钟中断或者其他原因抢占当前处理机,直到该进程完成或者阻塞,才把处理机分配给其他进程。这种方式的好处就是实现简单,系统开销小,适用于大部分法批处理系统。但是无法适应于分时系统和大部分的实数系统。

  这种调度方式允调度程序根据某种原则,去暂停某个正在执行的进程,将已经分给该进程的处理机重新分给另一进程。广泛采用抢占式,是因为对于批处理系统,可以防止一个长进程长时间的占用处理机,以确保处理机能够为所有进程提供更为公平的服务。 在分时系统中,只有采用抢占式才能实现人机交互,在实时系统中,抢占式能满足实时任务的要求。但同时抢占式比较复杂,所需要的系统开销也比较大。

  优先权原则,指允许优先级高的新到进程抢占当前长进程的处理机,即新进进程到达时,如果他的优先度比正在执行的进程优先度高,则调度程序剥夺当前进程的处理机。

  短进程优先,指允许新到的短进程抢占当前的长进程的处理机,即新进 进程到达时,如果他的比正在执行的(尚需运行)时间明显短,则调度程序剥夺当前进程的处理机。

  时间片原则, 即各进程按时间片轮转运行时,当正在执行的进程的一个时间片段用完后,变停止该进程的执行,而重新进行调度。

  在分时系统中,最简单也是教常用的是基于时间片的轮转算法(RR).该算法采用了非常公平的处理机分配方法,即让每个进程每次仅运行一个时间片。如果就绪队列上有n个进程,则每个进程大约获得1/n的处理机时间。

  在RR中,系统将所有的就绪进程按照FCFS策略排成一个就绪队列,系统可设置每个一定时间便产生一次中断, 去激活进程调度进行激活,把CPU分配队首进程,并令其执行一个时间片。运行完毕后,又把处理机分配给就绪队列的新的队首。

  优先级进程调度算法,是把处理机分配给就绪队列中优先级最高的进程。同时又可以进一步把该算法分为:

  之前所述的各种调度算法,在应用于进程调度时,由于系统中仅设置一个进程的就绪队列,即低级调度的算法是单一的,固定的,无法满足系统中不同用户对进程调度策略的不同要求,在多处理机系统中,这种单一调度策略实现机制缺点更加明显。因此多级队列算法能够在一定程度上弥补这一缺点。

  多级队列算法将进程就绪队列拆分成若干个,不同的就绪队列采用不同的调度算算法,所以可以很好的满足不同用户对进程调度策略的不同需求,同时也可以满足多处理机系统的需求。

  多级反馈队列不同与之前的调度算法,他可以不需确定各进程运行的时间,还可以较好的满足各种类型进程的需求。

  每个队列都采用FCFS算法,当新进程进入内存后,首先将它放在第一队列末尾,按照FCFS原则等待调度,当轮到该进程执行时,如果能在该时间片内完成,便可撤离系统。否则,调度程序便把他转入第二队列末尾等待。如果他在第二队列运行一个时间片认为完成,在一次放入第三队列…以此类推。当进程最后被降到第n队列后,在第n队列中便采用RR方式运行。

  安照队列优先级调度,调度程序首先调度最高优先级队列中的诸进程,仅当第一队列空闲时才调度第二队列中的进程运行。换而言之,仅当第1~(i-1)队列均为空时,才会调度第i队列中的进程运行,如果处理机正在为第i队列中的某进程服务时,有新进程进入较高级的队列,此时必须把正在运行的进程放回第i队列的末尾,而把处理机分配给新到的高优先级队列。

  保证调度算法是另一种类型的调度算法,它想用户所作出的保证并不是优先运行,而是明确的性能保证,该算法可以做到调度的公平性。一种比较容易的性能保证是处理机的公平性,如果在系统中有n个类型相同的进程同时运行,为了公平期间,每个进程都获得相同的处理机时间1/n。

  计算进程获得处理机时间的比率,即进程实际执行的处理时间和应获得的处理机时间之比。

  比较各进程获得处理机时间的比率。如进程A的比率最低,为0.5,而进程B的比率为0.8,进程C的比率为1.2等。

  调度程序应选择比率最小的进程将处理机分配给它,并让该进程一直运行,直到超过最接近它的进程比率为止。

  分配给每个进程相同的处理机时间,显然,这对诸进程而言,是体现了一定程度的公平,但如果各个用户所拥有的进程数不同,就会发生对用户的不公平问题。 在该算法中,调度的公平性是体针对于用户而言。使所有的用户获得相同的处理机时间,或要求的时间比例。

  ·在实时系统中,可能存在着两类不同性质的实时任务,即HRT任务和SRT任务,它们都联系着一个截止时间。为保证系统能正常工作,实时调度必须能满足实时任务对截止时间的要求。为此,实现实时调度应具备一定的条件。

  在实时系统中,若处理机的处理能力不够强,则有可能因处理机忙不过,而致使某些实时任务不能得到及时处理,从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务HRT,它们的处理时间可表示为Ci,周期时间表示为Pi,则在单处理机情况下,必须满足下面的限制条件系统才是可调度的:

  提高系统处理能力的途径有二:一是采用单处理机系统,但须增强其处理能力,以显著地减少对每一个任务的处理时间;二是采用多处理机系统。假定系统中的处理机数为N,则应将上述的限制条件改为:

  在含有HRT任务的实时系统中,广泛采用抢占机制。这样便可满足HRT任务对截止时间的要求。但这种调度机制比较复杂。 对于一些小的实时系统,如果能够预知任务法开始截止时间,则对于实时任务的调度可以采用非抢占式调度。

  为保证硬实时任务能及时运行,在系统中还应具有快速切换机制,使之能进行任务的快速切换。该机制应具有如下两方面的能力:

  该算法是根据任务的截止时间确定任务的优先级,任务的截止时间越早,其优先级越高,具有最高优先级的排在队首。EDF既可以用于抢占式也可以用于非抢占式。

  下图有两个周期任务,任务A和任务B的周期时间分别为20 ms和50 ms,每个周期的处理时间分别为10 ms和25 ms。

  该算法在确定任务的优先级时,根据的是任务的紧急(或松弛)程度。任务紧急程度愈高,赋予该任务的优先级就愈高,以使之优先执行。 该方式主要用可抢占式调度。

  假如在一个实时系统中有两个周期性实时任务A和B,任务A要求每20 ms执行一次,执行时间为10 ms,任务B要求每50 ms执行一次,执行时间为25 ms。由此可知,任务A和B每次必须完成的时间分别为:A1、A2、A3、…和B1、B2、B3、…,如下图

  系统中存在着影响进程运行的资源而可能产生“优先级倒置”的现象,即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。

  一种较简单的解决方法就是,规定进程进入临界区后,该进程占用的处理机不允许被抢占

  另一个比较实用的方法建立在动态优先级基础的基础上:该方法规定,当高优先级进程要进入临界区时,去使用临界资源R时,如果已有一个低优先级进程正在使用该资源。此时高优先进程被阻塞,另一方面低优先级进程继承高优先进程的优先级,直到低优先进程退出临界区。

  操作系统处理机调度及常见的调度算法(先来先服务调度算法(FCFS),短作业(进程)优先调度算法,高优先权优先调度算法,时间片轮转算法)...博文来自:wangiijing的博客

  一般来说,处理机调度最常用的是低级调度,也称为进程调度,进程调度的主要功能是根据某种算法,决定就绪队列中的哪个进程获得处理机。高级调度又称为作业调度,其主要功能是根据某种算法决定将外存上处于后备队列中...博文来自:sunjinbat的博客

  实验要求选择1~3种进程调度算法(先来先服务、短作业优先、最高响应比优先、时间片轮转、优先级法等)模拟实现进程调度功能;能够输入进程的基本信息,如进程名、到达时间和运行时间等;根据选择的调度算法显示进...博文来自:Core00077的博客

  什么是死锁死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进。例如,在某一个计算机系统中只有一台打印机和一台输入设备,进程P1正占用输入设备,同时又提出使用...博文来自:小白的博客

  BOOM,困到不行,这个写完就睡觉了,今天好像有点感冒,翘了晚上的课一直睡到10点起来,睡不着在写代码,现在又困了高响应比算法,是一种动态调整优先级的算法,在上面介绍的PSA算法中,给每个作业安排一个...博文来自:蒟蒻升级中...Orz

  FCFS:先来先服务,也可以称为先进先出轮转:以一个周期性间隔产生时钟中断,此时当前正在运行的进程被置于就绪队列,基于FCFS选择下一个就绪进程      运行。SPN:最短进程优先,下一次选择所需处...博文来自:haoshens blog

  决策模式决策模式说明选择函数在执行的瞬间的处理方式,通常分为以下两类:非抢占:一旦进入运行状态,就不会终止直到运行结束。抢占:当前正在运行的进程可以被打断,并转移到就绪态。 一个调度算法是否能抢占,对...博文来自:xieminyao123的博客

  处理机调度算法在多道程序系统中,调度实际上是一种资源分配,即对处理机资源的分配;处理机调度算法是指根据处理机分配策略所规定的处理机分配方法;处理机调度处理机调度的层次高级调度高级调度又称为长程调度或者...博文来自:知识必具有个性,才配说是自己的~

  4.处理机调度4.1处理机调度概述☆4.1.1三种等级的调度高级调度决定把外存上哪些作业调入内存、创建进程、分配资源作业调度、长程调度或宏观调度低级调度决定就绪队列中哪个进程应获得处理机进程调度、短程...博文来自:maniacxx的博客

  操作系统实验报告(处理机调度算法的实现)内容详细 1、实验名称: 处理机调度算法的实现 2、实验要求: 了解操作系统处理机调度概念的基本概念,处理机调度程序的功能,常用的处理机调度算法。C或C++编程方法与语句格式,提前初步编好试...

  随机给出一个进程调度实例,如: 进程 到达时间 服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 模拟进程调度,给出按照算法先来先服...

  设计一个按优先权调度算法实现处理器调度的程序 设计一个按时间片轮转法实现处理器调度的程序

  随机给出一个进程调度实例,如: 进程 到达时间 服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2 模拟进程调度,给出按照算法先来先服...

  在多道程序环境下,进程数目往往多于处理机数目,致使它们竞争使用处理机。这就要求系统能按某种算法,动态地把处理机分配给就绪队列中的一个进程,使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统...博文来自:杨森源的博客

  首先有一点需要说明:计算机中一切事务的执行者只能够是处理机,处理机的直接执行对象只能是机器码。   “进程管理”只是对处理器要做的单个作业进行了一些统筹,而作业的实际执行者是处理机。举个例子:...博文来自:A_Pointer的博客

  处理机调度的基本概念1高/中/低级调度A(不经常用)高级调度(长调度/作业调度/接纳调度):决定外存上处于后备队列中的哪些作业调入内存.1)作业调度时需决定:接纳多少作业:取决于系统规模接纳哪些作业:...博文来自:Silly2016的博客

  处理机调度与死锁处理机调度与死锁处理机调度的层次和调度算法的目标作业与作业调度进程调度实时调度死锁概述处理机调度的层次和调度算法的目标处理机调度的层次高级调度。又称长程调度或作业调度。它的调度对象为作...博文来自:yo_bc的博客

  在批处理系统中,FCFS算法所考虑的只是作业的等待时间,而忽视了作业的运行时间。而SJF算法正好与之相反,只考虑作业的运行时间,而忽视了作业的等待时间。高响应比优先调度算法则是即考虑了作业的等待时间,...博文来自:辣条不爱辣的博客

  文章目录处理机调度基本概念三个层次三层调度的联系、对比补充知识知识结构图进程调度时机切换与过程方式知识结构图调度算法调度算法的评价指标CPU利用率系统吞吐量周转时间等待时间响应时间知识结构图调度算法—...博文来自:半路出家的博客

  本实验随机输入的进程个数、进程名称、进程提交到系统的时间、进程运行所需时间。通过模拟程序。显示以下信息:1)处理机对进程的调度过程。2)计算这N个进程的平均周转时间。三、HRRN(最高响应比调度算法)...博文来自:29DCH的博客

  1.下列()进程调度算法会引起进程的饥饿问题A。FCFS  B.RR C.优先级 D.多级反馈队列【答案】C【解析】优先级低的可能长时间得不到服务,产生饿死现象。2.以下情况不可能引起进程调度的是()...博文来自:Liuyaoyun的博客

  这道题慢悠悠地做,出现了很多错误,大多都是空指针产生的中断,最后还是实现了。实习题目:设计一个按优先数调度算法实现处理器调度的程序。[提示]:(1) 假定系统有5个进程,每个进程用一个PCB来代表。P...博文来自:yill_h的博客

  用静态数组和结构体实现:先用结构体定义进程的进程号,时间,优先级等属性,另外,我还加了一个属性“下标v”。首先将输入的进程按照其优先级的从高到低排序(这里我用的是冒泡排序),运行当前优先级最高的那个进...博文来自:Chuck的博客

  处理机调度:多道程序环境下,动态的把处理机分配给就绪队列中的一个进程使之执行。提高处理机的利用率、改善系统性能,很大程度上取决于处理机调度的性能。处理机调度便成为OS设计的中心问题之一。分配的任务由处...博文来自:Marvin_Huoshan的博客

  注:本文记录WHUT-计算机学院-操作系统课程实验1:处理机调度纸上得来终觉浅,觉知此事需躬行! 1、实验内容:•实验预备:掌握处理机调度的相关内容,对进程调度算法有深入的理解•实验内容:模拟实现...博文来自:拾年之璐

  1.先来先服务调度算法先来先服务(FCFS)调度算法思想:每次调度都是从后背作业队列中选择一个获多个最先进入该队列的作业,将它们调入内存,为他们分配资源、创建进程,然后放入就绪队列。特点:在进程调度中...博文来自:u010842515的博客

  这个算法很好玩,综合了短作业优先,先来先服务,以及长作业也能得到服务的特性,因此,是一种综合的调度算法。计算公式:优先权=(等待时间+要求服务时间)/要求服务时间又因为等待时间+要求服务时间=响应时间...博文来自:Bings Blog

  处理机:计算机系统中存储程序和数据,并按照程序规定的步骤执行指令的部件。处理机包括中央处理器,主存储器,I/O接口。处理机再加上外围设备eg:鼠标?键盘?等构成完整的计算机系统。处理器:中央处理器(C...博文来自:的博客

  假设系统有n个进程,每个进程用一个进程控制块(PCB)来代表。进程结点的数据元素有:进程号 进程到达时间进程状态 优先数 进程运行时间 进程运行时间C++实现模拟时间片轮转法进程调度源代码:#incl...博文来自:龙套的博客

  一、先来先服务和短作业(进程)优先调度算法1.先来先服务调度算法先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,每次调度都是...博文来自:libo222的博客

  实验目的与要求 一、实验目的 在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态。当就绪状态进程个数大于处理器数时,就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟...博文来自:会飞的小咸鱼

  外部中断,就是我们通常所说的中断(interrupt)。对于执行的系统来说,这种中断发生完全是异步的,根本无法预测到此类中断会在什么时候发生。因此,CPU(或者软件)对于此类外部中断完全是被动...博文来自:fantasyagain的专栏

  1.处理机调度层次及调度算法的目标调度层次包括三级调度。(1)高级调度。也叫作业调度或长程调度。调度的对象是作业,主要用于多道批处理系统中。(为什么实时系统和分时系统不需要嘞,因为对响应时间要求较高呀...博文来自:Liuyaoyun的博客

  写在前面:这一部分开始第三章处理机相关内容的学习。处理机是最重要的计算机资源,在多道程序环境下,主存中有着多个进程,其数目往往多于处理机数目。要求系统能按某种算法,动态地把处理机分配给就绪队列中的一个...

http://m3-ctech.com/fenpaiyouxianji/777.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有