精华内容
下载资源
问答
  • 进程调度算法Linux进程调度算法

    千次阅读 2018-02-06 20:02:27
    这次介绍一下操作系统的进程调度算法 操作系统的调度分为三种:1.远程调度(创建新进程);2.中程调度(交换功能的一部分);3.短程调度(下次执行哪个进程) 这次讲述的就是短程调度,可以简单的看作咱们平时...

    这次介绍一下操作系统的进程调度算法

    • 操作系统的调度分为三种:1.远程调度(创建新进程);2.中程调度(交换功能的一部分);3.短程调度(下次执行哪个进程)

    这次讲述的就是短程调度,可以简单的看作咱们平时所说的进程调度啦

    当发生下面几种情况的时候会调用短程调度器,然后就看下次执行那个进程啦

    • 时钟中断
    • I/O中断
    • 操作系统调用
    • 信号(如信号量)

     

    • 进程调度算法:
      • 先来先服务(FCFS)
      • 短作业优先(SPN)
      • 最短剩余时间(SRT)
      • 时间片轮转
      • 最高响应比优先
      • 公平共享调度

     

     

    • 先来先服务


    就和名字一样,哪个进程先来就先获得处理器时间,,用一个队列暂存等待处理器的进程,优点是实现简单(太简单了吧喂),缺点,遇到那种又臭又长的进程就很不爽了,好比食堂打饭,前面的人不买一直问,后面的人一直排队,那么后面的人就怎么了呢?后面的人就饥饿!同时如果现在有一个马上就要饿死的人急需吃饭,这就很尴尬了(紧急的进程无法处理,优先级高的进程处于饥饿状态),所以有了优先级队列的先来先服务算法,这样也不是很好,因为总有又臭又长的进程,排队是谁都不乐意的吧,而且处理器时间就不公平了。

    • 短作业优先

    因为先来先服务不好,所以有了短作业优先,通过设置执行时间短的进程作业的优先级为高来实现,也很简单粗暴,就是说进程时间越短就越先执行,看着是比较好了,不浪费时间了,但是有没有想过长进程的感受,来了一群短的进程,然后一直来短进程,这是要饿死长进程的节奏,人家长有错么?如果是可抢占的方式(见最短剩余时间版本),就更惨了,只要来了更短的就别想好好执行了。。。

    • 最短剩余时间

    就是刚才说的短作业优先的抢占版本,说过他的缺点了,当前执行的进程还剩10个时间单位,但是一直来了一群只要2个时间单位就跑完的进程,那当前的进程就会被抢占,然后含恨饿死。。

    • 时间片轮转

    既然上面几种算法都有可能出现饥饿进程,那么我就干脆让每个进程都执行那么一会,这样不就比较公平了?每个进程都有机会在处理器上跑,看起来很和谐,但是还是没有解决优先级的问题,优先级不好控制,比如有什么紧急的进程需要立即执行,就不好办了。而且每个进程的具体情况也是不一样的,比如有I/O消耗型进程,和处理器消耗型进程,在同样的事件片里真正占用处理器的时间是不一样的,而我们是真正占用处理器的时间希望能一样的,这样就公平了嘛。这样看来,时间片轮转也是有缺点的。

    • 最高响应比优先

    什么是响应比?看一下这个公式:R=(w+s)/s,其中R是响应比,w是等待处理器的时间,s是期待的服务时间,简单的来说响应比就是,进程从加入等待队列开始一直到执行完毕经历的时间除以进程使用处理器的时间,这个响应比比较高的就证明该进程等待比较久了,它估计会很饿,先让它吃!

    • 公平共享调度

    Linux系统中普通进程使用的调度方法就是公平共享调度的一个实例,被称作完全公平调度算法(CFS),虽然一定不可能公平。。。详情参照我的另一篇博客。。传送门召唤!!:http://www.cnblogs.com/lenomirei/p/5516872.html

    • Linux系统中的进程调度方案

    Linux在进行进程调度的时候把进程分为两种:1.普通进程;2.实时进程

    实时进程的优先级永远比普通进程的优先级高,也就是说实时进程只要来了就可以抢占普通进程,而且还抓住处理器就不撒手,直到所有的实时进程都执行完毕,才会把处理器让出来给普通进程使用

    之前也说了,普通进程的调度采用的是完全公平调度(CFS)对应的是SCHED_NORMAL

    而实时进程采用的调度方法就比较简单粗暴了,Linux提供了两种实时调度策略:SCHED_FIFO和SCHED_RR。

    SCHED_FIFO:简单的先入先出的调度算法,不使用时间片,只可能被更高优先级的FIFO或者SCHED_RR抢占

    SCHED_RR:时间片轮转的方式,优先级比SCHED_FIFO还要高,可以抢占SCHED_FIFO

    实时进程的调度没有实时优先级这一说法,采用的是静态优先级,一开始定好优先级之后就不会改变了。

    展开全文
  • 1.作业调度与进程调度算法 作业调度算法: 先来先服务调度算法(FCFS) 短作业优先调度算法(SJF) 优先级调度算法 高响应比优先调度算法 进程调度算法: 先来先服务调度算法(FCFS) 短进程优先调度算法(SPF) ...

    1.作业调度与进程调度算法

    作业调度算法:

    • 先来先服务调度算法(FCFS)
    • 短作业优先调度算法(SJF)
    • 优先级调度算法
    • 高响应比优先调度算法

    进程调度算法:

    • 先来先服务调度算法(FCFS)
    • 短进程优先调度算法(SPF)
    • 优先级调度算法
    • 高响应比优先调度算法
    • 时间片轮转调度算法
    • 多级反馈队列调度算法

    下面分别介绍一一下各种算法。


    1.1. 作业调度算法

    先来先服务调度算法

    基本思想:在作业调度中,系统按照作业到达的先后顺序(或者说优先考虑系统中等待时间最长的作业),从后备队列中选择一个或者多个最先进入该队列的作业,将它们调入内存中,为它们分配资源和创建进程,然后放入就绪队列。

    短作业优先调度算法

    基本思想:在作业调度中,从后备队列中选择若干个估计时间最短的作业,将它们优先调入内存运行。

    优先级调度算法

    基本思想:在优先级调度算法中,是基于作业的紧迫程度,由外部赋予作业相应的优先级,调度算法是根据该优先级进行调度。

    高响应比优先调度算法

    问题:FCFS算法考虑的只是作业的等待时间,而忽略了作业的运行时间。SJF算法恰与之相反,只考虑了作业的运行时间,而忽略了作业的等待时间。

    而高响应比调度算法既考虑了作业的等待时间,又考虑了作业的运行时间,即照顾了短作业,又不致使长作业的等待时间过长,从而改善了处理机调度的性能。下面就看一下高响应比有线调度算法的思想。

    基本思想:如果我们能为每个作业引入一个动态优先级,令它随等待时间延长而增加,这将使长作业的优先级在等待不断增加,等到足够的时间后,必有机会获得处理机。该优先级的变化规律如下图所示:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nWTgKlNT-1607867257126)(D:\笔记图片集\1607860418941.png)]

    1.2. 进程调度算法

    先来先服务调度算法(FCFS)

    基本思想:在进程调度中,每次从就绪队列中选择一个或多个最先进入该队列的进程,为之分配处理机,使之投入运行。

    短进程优先调度算法(SPF)

    略,与SJP相似。

    优先级调度算法

    高响应比优先调度算法

    见作业调度

    时间片轮转调度算法

    基本思想:系统根据FCFS策略,将所有就绪进程排成一个就绪队列,并设置每隔一定时间间隔产生一次中断,激活系统中的进程调度程序,完成一次调度,将CPU分配给队首进程,令其执行。当该进程的时间片耗尽或运行完毕时,系统再次将CPU分配给新的队首进程。由此,可保证就绪队列中的所有进程在一个确定时间段内,都能够获得一次CPU执行。

    多级反馈队列调度算法

    1.3. 做题方法

    先来先服务调度算法

    题:

    假设一个系统有 5 个进程,他们的到达时间和服务时间如下表所示,忽略 I/O 以及其他的开销时间,若按先来先服务进行 CPU 调度,请给进程平均周转时间和平均带权周转时间.(保留两位小数)

    进程P1P2P3P4P5
    到达时间02468
    服务时间36452

    解答:

    在这里插入图片描述

    平均周转时间:8.60

    平均带权周转时间:2.56

    短进程优先调度算法

    题:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VkW5EWJ6-1607867257132)(D:\笔记图片集\1607863856948.png)]

    解答:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yt11pD2Y-1607867257132)(G:\1607865850499.png)]

    优先级调度算法

    高响应比优先调度算法

    时间片轮转调度算法

    题:

    设有5个进程P1、P2、P3、P4和P5;它们到达时间和要求服务时间如下表,求非抢占方式下,采用RR,q = 4(Round Robin quantum=4)调度算法时。

    进程P1P2P3P4P5
    到达时间0891823
    服务时间231417125

    ①给出进程调度顺序的甘特图

    ②计算平均周转时间和平均带权周转时间(保留两位小数)

    解答:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A63exRfH-1607867257134)(D:\笔记图片集\RR.jpg)]

    ①如上图

    ②平均周转时间:51.40;平均带权周转时间:4.16

    出进程调度顺序的甘特图

    参考

    • 处理机调度ppt
    • 计算机操作系统(第四版)
    展开全文
  • 进程调度算法

    万次阅读 多人点赞 2019-03-20 19:58:15
    操作系统常见的进程调度算法 调度算法是指:根据系统的资源分配策略所规定的资源分配算法。常见的进程调度算法有:  1.先来先去服务  2.时间片轮转法  3.多级反馈队列算法  4.最短进程优先  5.最短剩余...

    操作系统常见的进程调度算法

    调度算法是指:根据系统的资源分配策略所规定的资源分配算法。常见的进程调度算法有:

      1.先来先去服务

      2.时间片轮转法

      3.多级反馈队列算法

      4.最短进程优先

      5.最短剩余时间优先

      6.最高响应比优先

      7.多级反馈队列调度算法

    一、先来先去服务

      先来先去服务调度算法是一种最简单的调度算法,也称为先进先出或严格排队方案。当每个进程就绪后,它加入就绪队列。当前正运行的进程停止执行,选择在就绪队列中存在时间最长的进程运行。该算法既可以用于作业调度,也可以用于进程调度。先来先去服务比较适合于常作业(进程),而不利于段作业(进程)。

    二、时间片轮转法

      轮转法是基于适中的抢占策略的,以一个周期性间隔产生时钟中断,当中断发生后,当前正在运行的进程被置于就绪队列中,然后基于先来先去服务策略选择下一个就绪作业的运行。这种技术也称为时间片,因为每个进程再被抢占之前都给定一片时间。

    三、最短进程优先

      最短进程优先是一个非抢占策略,他的原则是下一次选择预计处理时间最短的进程,因此短进程将会越过长作业,跳至队列头。该算法即可用于作业调度,也可用于进程调度。但是他对长作业不利,不能保证紧迫性作业(进程)被及时处理,作业的长短只是被估算出来的。

    四、最短剩余时间优先

      最短剩余时间是针对最短进程优先增加了抢占机制的版本。在这种情况下,进程调度总是选择预期剩余时间最短的进程。当一个进程加入到就绪队列时,他可能比当前运行的进程具有更短的剩余时间,因此只要新进程就绪,调度程序就能可能抢占当前正在运行的进程。像最短进程优先一样,调度程序正在执行选择函数是必须有关于处理时间的估计,并且存在长进程饥饿的危险。

    五、最高响应比优先

    根据比率:R=(w+s)/s (R为响应比,w为等待处理的时间,s为预计的服务时间)

      如果该进程被立即调用,则R值等于归一化周转时间(周转时间和服务时间的比率)。R最小值为1.0,只有第一个进入系统的进程才能达到该值。调度规则为:当前进程完成或被阻塞时,选择R值最大的就绪进程,它说明了进程的年龄。当偏向短作业时,长进程由于得不到服务,等待时间不断增加,从而增加比值,最终在竞争中赢了短进程。

      和最短进程优先、最短剩余时间优先一样,使用最高响应比策略需要估计预计服务时间。

    六、反馈法

      如果没有关于进程相对长度的任何信息,则最短进程优先,最短剩余时间、最高响应优先比都不能使用。另一种导致偏向短作业的方法是处罚运行时间较长的作业,换句话说,如果不能获得剩余的执行时间,那就关注已执行了的时间。

      方法为:调度基于被抢占原则(按时间片)并使用动态优先级机制。当一个进程第一次进入系统中时,他被放置在一个优先级队列中,当第一次被抢占后并返回就绪状态时,它被放置在下一个低优先级队列中,在随后的时间里,每当被抢占时,他被降级到下一个低优先级队列中。一个短进程很快被执行完,不会在就绪队列中降很多级,一个长进程会逐渐降级。因此先到的进程和短进程优先于长进程和老进程。在每个队列中,除了优先级在最低的队列中之外,都是用简单的先来先去服务机制,一旦一个进程处于优先级最低的队列中,它就不可能在降级,但会重复的返回该队列,直到运行结束。因此,该队列课按照轮转方式调度。

     七、多级反馈队列调度算法

      多级反馈队列算法,不必事先知道各种进程所需要执行的时间,他是当前被公认的一种较好的进程调度算法。其实施过程如下:

      1)设置多个就绪队列,并为各个队列赋予不同的优先级。在优先权越高的队列中,为每个进程所规定的执行时间片就越小。

      2)当一个新进程进入内存后,首先放入第一队列的末尾,按照先来先去原则排队等候调度。如果他能在一个时间片中完成,便可撤离;如果未完成,就转入第二队列的末尾,同样等待调度.....如此下去,当一个长作业(进程)从第一队列依次将到第n队列(最后队列)后,便按第n队列时间片轮转运行。

      3)仅当第一队列空闲的时候,调度程序才调度第二队列中的进程运行;仅当第1到(i-1)队列空时,才会调度第i队列中的进程运行,并执行相应的时间片轮转。

      4)如果处理机正在处理第i队列中某进程,又有新进程进入优先权较高的队列,则此新队列抢占正在运行的处理机,并把正在运行的进程放在第i队列的队尾。

     

     

     

    进程调度:

      无论是在批处理系统还是分时系统中,用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外,系统进程也同样需要使用处理机

    这就要求进程调度程序按一定的策略,动态地把处理机分配给处于就绪队列中的某一个进程,以使之执行。

    一、进程的基本状态及状态间的转换:

      1.等待态:等待某个事件的完成;

      2.就绪态:等待系统分配处理器以便运行;

      3.运行态:占有处理器正在运行。

       运行态→等待态 往往是由于等待外设,等待主存等资源分配或等待人工干预而引起的。

       等待态→就绪态 则是等待的条件已满足,只需分配到处理器后就能运行

       运行态→就绪态 不是由于自身原因,而是由外界原因使运行状态的进程让出处理器,这时候就变成就绪态。例如时间片用完,或有更高优先级的进程来抢占处理器等。

       就绪态→运行态 系统按某种策略选中就绪队列中的一个进程占用处理器,此时就变成了运行态

     

    二、处理机

      高级、中级和低级调度作业从提交开始直到完成,往往要经历下述三级调度:

      高级调度:(High-Level Scheduling)又称为作业调度,它决定把后备作业调入内存运行;

      低级调度:(Low-Level Scheduling)又称为进程调度,它决定把就绪队列的某进程获得CPU;

      中级调度:(Intermediate-Level Scheduling)又称为在虚拟存储器中引入,在内、外存对换区进行进程对换。

     

    三、进程调度的算法及思想

    1.先来先服务调度算法

      先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,

    每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪

    队列。在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。

    该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

     

    来看一个例子,假设有三个进程和它们各自执行时间(以毫秒为单位)如下表:

     

     

    那么如果三个进程按照P1, P2, P3的顺序启动的话,按照先到先服务的调度算法,执行过程如下:

     

     

      平均等待时间就是(0 + 24 + 27) / 3 = 17毫秒。FCFS算法是非抢占式的,一旦内核将CPU分配给一个进程就不会被释放

    了,除非进程结束或者请求I/O阻塞。这也是我们之前学习的多任务系统的特点。

    2、基于优先级调度 (Priority Scheduling)

      在优先级调度算法中,每个进程都关联一个优先级,内核将CPU分配给最高优先级的进程。具有相同优先级的进程,按照

    先来先服务的原则进行调度。假设进程的执行时间和优先级如下,并且这些进程同时存在于内存中时,内核基于优先级的

    调度过程如下:

     

     

     

      采取基于优先级调度算法要考虑进程饿死的问题,因为高优先级的进程总是会被优先调度,具有低优先级的进程可能永远

    都不会被内核调度执行。Aging是对于这个问题的一个解决方案,所谓Aging就是指逐渐提高系统中长时间等待的进程的

    优先级。比如如果优先级的范围从127到0(127表示最低优先级),那么我们可以每15分钟将等待进程的优先级加1。最终

    经过一段时间,即便是拥有最低优先级127的进程也会变成系统中最高优先级的进程,从而被执行。

     

      优先级调度可以抢占式或者非抢占式的。当一个进程在Ready队列中时,内核将它的优先级与正在CPU上执行的进程的优先级

    进行比较。当发现这个新进程的优先级比正在执行的进程高时:对于抢占式内核,新进程会抢占CPU,之前正在执行的进程

    转入Ready队列;对于非抢占式内核,新进程只会被放置在Ready队列的头部,不会抢占正在执行的进程。

     

     

     

    3、短进程优先(SCBF--Shortest CPU Burst First)

      最短CPU运行期优先调度算法(SCBF--Shortest CPU Burst First)

    该算法从就绪队列中选出下一个“CPU执行期最短”的进程,为之分配处理机

    最短作业优先调度是优先级调度的特例。在优先级调度中我们根据进程的优先级来进行调度,在最短作业优先调度中我们

    根据作业的执行时间长短来调度。通过下面的例子来看看SJF是怎样调度的。

     

     

     

      进程1首先执行了1毫秒,当执行时间更短的进程2进入Ready队列时发生抢占。进程3在进程2执行1毫秒后到来,但是进程3的

    执行时间比进程2长。同理进程4的到来也没法抢占进程2,所以进程2可以一直执行到结束。之后是执行时间第二短的进程4

    执行,最后是进程1(要看剩余执行时间,还剩7毫秒)和进程3。

     

      SJF调度是最优的调度,但难点在于如何预测进程的执行时间(Burst Time)。对于批处理系统中的长期调度来说,可以将用户

    提交进程时输入的执行时间上限作为依据。但对于短期调度来说,没有办法能够提前得知下一个要被分配CPU的进程的执行

    时间长短。我们只能通过历史数据来进行预测,公式如下:

     

     

    α可以取0.5,公式前半部分表示最近一次Burst Time,而后半部分表示过去历史平均的Burst Time。

    该算法虽可获得较好的调度性能,但难以准确地知道下一个CPU执行期,而只能根据每一个进程的执行历史来预测。

     

    4、轮转法 (Round-Robin Scheduling) (RR)

      前几种算法主要用于批处理系统中,不能作为分时系统中的主调度算法,在分时系统中,都采用时间片轮转法。

    简单轮转法:系统将所有就绪进程按FIFO规则排队,按一定的时间间隔把处理机分配给队列中的进程。这样,就绪

    队列中所有进程均可获得一个时间片的处理机而运行。多级队列方法:将系统中所有进程分成若干类,每类为一级。

      RR调度算法转为分时系统设计,它与FCFS很像,但是加入了抢占。具体调度过程是:内核从Ready队列中选取第一个进程,

    将CPU资源分配给它,并且设置一个定时器在一个时间片后中断该进程,调度Ready队列中的下一进程。很明显,RR调度

    算法是抢占式的,并且在该算法的调度下,没有一个进程能够连续占用CPU超过一个时间片,从而达到了分时的目的。

     

    来看下面的例子,假设一个时间片的长度为4毫秒:

     

     

     

     

    5、高响应比优先调度算法

      (1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业.

      (2) 当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务.

      (3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高, 从而也可获得处理机.

      该算法照顾了短作业,且不会使长作业长期得不到服务

     

    6、抢占式调度算法

    1. 非抢占式调度算法

    为每一个被控对象建立一个实时任务并将它们排列成一轮转队列,调度程序每次选择队列中的第一个任务投入运行.该任务完成后便把它挂在轮转队列的队尾等待下次调度运行.

    2. 非抢占式优先调度算法.

    实时任务到达时,把他们安排在就绪队列的对首,等待当前任务自我终止或运行完成后才能被调度执行.

    3. 抢占式调度算法

    1)基于时钟中断的抢占式优先权调度算法.

    实时任务到达后,如果该任务的优先级别高于当前任务的优先级并不立即抢占当前任务的处理机,而是等到时钟中断到来时,调度程序才剥夺当前任务的执行,将处理机分配给新到的高优先权任务.

    2)立即抢占的优先权调度算法.

    在这种调度策略中,要求操作系统具有快速响应外部时间中断的能力.一旦出现外部中断,只要当前任务未处于临界区便立即剥夺当前任务的执行,把处理机分配给请求中断的紧迫任务,实时进程调度,实时进程抢占当前。

    展开全文
  • 最近几周操作系统实习,要求完成几道题目,下面是自己敲出来的模拟在单处理器情况下的进程调度算法(说算法可能过于高大尚), 采用的是短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中的最高...

    原创


    最近几周操作系统实习,要求完成几道题目,下面是自己敲出来的模拟在单处理器情况下的进程调度算法(说算法可能过于高大尚),

    采用的是短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中的最高优先级算法。

    题目阐述如下:

                        设计一:进程调度

      设计目的:    

      进程管理是操作系统中的重要功能,用来创建进程、撤消进程、实现进程状态转换,它提供了在可运行的进程之间复用CPU的方法。

    在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处

    理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。本设计模拟在单处理器情况下的进程调度,目的是加深对进程调度

    工作的理解,掌握不同调度算法的优缺点。

      设计内容:

    设计程序模拟单处理机系统中的进程调度算法,在短作业优先调度算法、时间片轮转调度、最高优先级优先算法三种算法中选择两种实现。

    每个进程由一个进程控制块(PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进

    程状态等。进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。进程的到达时间为进程输入的时间。

    进程的运行时间以时间片为单位进行计算。

    每个进程的状态可以是就绪W(Wait)、运行R(Run)或完成F(Finish)3中状态之一。

    以下是最高优先级优先算法思想:

    就绪进程获得CPU后都只能运行一个时间片,用已占用CPU时间加1来表示。

    如果运行一个时间片后,进程的已占用CPU时间已达到所需要的运行时间,则撤销该进程,如果运行一个时间片后进程的已占用CPU时间

    还未达到所需要的运行时间,也即进程还需要继续运行,此时应将进程的优先数减1(即降低一级),然后把它插入就绪队列等待CPU。

    每进行一次调度程序都打印一次运行进程、就绪队列以及各个进程的PCB,以便进行检查。

    重复以上过程,直到所有进程都完成为止。

     

    每个PCB进程包括:进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态;采用结构体类型来存储一个PCB。

    采用的数据结构是队列,创建的进程形成一个双向队列(采用双向队列容易寻找前驱结点的地址),遍历队列,从中找出优先级

    最高的PCB取出(相当于调入CPU),将其优先数降低,增加其已用CPU时间,改变其进程状态;然后判断其已用CPU时间是否

    大于等于需要运行时间,大于将其进程状态置为完成状态,否则将此PCB插入队列尾部,再次在队列中寻找优先级最高的PCB......

    /*
        最高优先级算法 
    */
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #define N 3
    #define Time_film 2    //时间片
    
    int count = 0;    //统计进程完成个数 
    
    void print(struct PCB *head);
    
    struct PCB{
        int process_name;    //进程名 
        int priority_number;    //优先数,随机产生 
        int arrive_time;    //到达时间,为进程的创建时间 
        int need_time;    //需要运行的时间,随机产生 
        int used_time;    //已用CPU的时间,初始值为0 
        int process_state;    //进程状态,1表示运行,0表示完成,-1表示就绪,初始值为-1 
        struct PCB *cre;    //前驱指针域
        struct PCB *next;    //后驱指针域
    };
    
    void Process_scheduling(struct PCB *head){
        /*
        扫描队列,寻找最高优先数的PCB,调入CPU运行;
        如果 use_CPU == need_time 撤销此PCB;
        否则用完一个时间片后放回队列尾部,继续扫描;
        */
        //****************************
        struct PCB *Move=head->next;
        struct PCB *Max_Pri=head->next;
        struct PCB *Tail;    //尾指针 
        //****************************
        while(Move!=NULL){
            if(Max_Pri->priority_number < Move->priority_number){
                Max_Pri = Move;
            }                        //寻找最高优先级进程 
            Move = Move->next;
        }
        //****************************
        Move = Max_Pri->cre;        //将最高优先级进程调出
        Move->next = Max_Pri->next;
        if(Move->next != NULL){
            Move = Max_Pri->next;
            Move->cre = Max_Pri->cre;    
        }
        //****************************
        printf("        进程 %d 被调度: \n",Max_Pri->process_name);
        Max_Pri->used_time += Time_film;    //增加CPU占用时间
        if(Max_Pri->used_time >= Max_Pri->need_time){
            Max_Pri->used_time = Max_Pri->need_time;    //进程状态改变
            Max_Pri->process_state = 0;
            count++;
        }
        else{
            Max_Pri->process_state = 1;
        }
        Max_Pri->priority_number-=1;    //优先数减1
        printf(" %d     %d     %d        %d         %d      %d \n\n",Max_Pri->process_name,Max_Pri->priority_number,Max_Pri->arrive_time,Max_Pri->need_time,Max_Pri->used_time,Max_Pri->process_state);
        if(count == N){    //所有进程执行完毕 
            printf("        所有进程执行完毕!");
            return;
        }
        printf("        就绪队列:\n");
        print(head);    //输出就绪队列
        printf("\n");
        //****************************
        if(Max_Pri->process_state !=0){
            Move = head;
            while( Move->next!=NULL ){    //当被调出进程未完成时将其插入就绪队列尾部 
                Move = Move->next; 
            }
            Tail = Move;
            Max_Pri->cre = Tail;
            Max_Pri->next = NULL;
            Tail->next = Max_Pri;
            Max_Pri->process_state = -1;
        }
        //****************************
        Process_scheduling(head);
    }
    
    void print(struct PCB *head){    //输出队列函数 
        if(head->next == NULL){
            printf("就绪队列已空\n");
            return;
        }
        printf("name priority arr_time need_time use_CPU pro_state\n");
        struct PCB *fry = head->next;
        while(fry != NULL){
            printf(" %d     ",fry->process_name);
            printf("%d     ",fry->priority_number);
            printf("%d        ",fry->arrive_time);
            printf("%d         ",fry->need_time);
            printf("%d      ",fry->used_time);
            printf("%d ",fry->process_state);
            printf("\n");
            fry = fry->next;    
        }
        printf("\n"); 
    }
    
    int main(){
        struct PCB *head;    //头指针
        struct PCB Pro[N+1];    //创建 N+1 个进程
        head = &Pro[0];
        srand(time(0));
        
        //****************************
        //设置进程参数
        Pro[0].process_name = 0;
        Pro[0].cre = NULL;
        Pro[0].next = &Pro[1];
        Pro[0].priority_number = 0;
        int i=0;
        for(i=1;i<=N;i++){
            Pro[i].process_name = i;
            Pro[i].priority_number = rand()%10;
            while(Pro[i].priority_number == 0){
                Pro[i].priority_number = rand()%10;
            }
            Pro[i].arrive_time = i;
            Pro[i].need_time = rand()%7;
            while(Pro[i].need_time == 0){
                Pro[i].need_time = rand()%7;
            }
            Pro[i].used_time = 0;
            Pro[i].process_state = -1;
        }
        for(i=1;i<=N;i++){    //形成双向队列
            if( i == N ){
                Pro[i].cre = &Pro[i-1];
                Pro[i].next = NULL;
                break;
            }
            Pro[i].cre = &Pro[i-1];
            Pro[i].next = &Pro[i+1];
        }
        //****************************
        
        printf("        进程初始状态: \n");
        print(head);    //输出初始队列状态
        
        Process_scheduling(head);    //调用进程调度函数(最高优先级)
        
        return 0;
    }

    (运行结果部分截图)

    10:58:00 

    2018-05-12

     

    改进:

    上面忽视了进程的到达时间这个因素,会产生致命错误:

    进程没有到达,但是其优先级最高,还是会被调用!

    必须从已经到达的进程中选择优先级最高的调入CPU运行,每个进程每次使用一次时间片后必须判断哪些进程已经到来,然后再

    所有到达的进程中选择优先级最高的调入CPU运行;可以设置一个动态的系统时间 system_time(初始值为最先到达进程的到

    达时间)system_time 在每个进程执行完一次后都增加该进程此次执行的时间(这里不指明每次执行时间为时间片是因为当进程

    剩下需要的执行时间小于一个时间片后 system_time 不会增加一个时间片),进程每次执行完一个时间片后,将 system_time

    每个进程的到达时间进行比较,大于 system_time 则未到达,反之,到达;再从已到达的进程中选择优先级最高的调入CPU运

    行......值得一提的是,若遇到进程到来比较晚( system_time<进程的到达时间)前面的进程都已经执行完成(已从队列中移除)

    则通过 system_time 将找不到合适的进程调入,此时必须通过 “手动”添加系统时间来达到下一个进程的到达时间,然后将其执行。

    /*
        最高优先级算法 
    */
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #define N 5
    #define Time_film 2    //时间片
    
    int count = 0;    //统计进程完成个数 
    int system_time=100; 
    int flag=0;
    int ff=0;
    
    void print(struct PCB *head);
    
    struct PCB{
        int process_name;    //进程名
        int priority_number;    //优先数,随机产生 
        int arrive_time;    //进程的到达时间,随机产生 
        int need_time;    //需要运行的时间,随机产生 
        int used_time;    //已用CPU的时间,初始值为0 
        int process_state;    //进程状态,1表示运行,0表示完成,-1表示就绪,初始值为-1 
        struct PCB *cre;    //前驱指针域
        struct PCB *next;    //后驱指针域
    };
    
    void Process_scheduling(struct PCB *head){
        /*
        扫描队列,将最先到达的进程调入运行,若多个进程
        同时到达,选取优先级最高的进程    调入,运行状态
        的进程用完一个时间片后判断是否进程是否执行完毕
        或有新进程到达,加入新进程后再次选取优先级最高
        的调入运行,直至进程全部调用完毕。 
        */
         
        //****************************
        struct PCB *Move=head->next;
        struct PCB *Max_Pri=head;
        struct PCB *Tail;    //尾指针 
        //****************************
        
        /*
        while(Move!=NULL){
            if(Max_Pri->arrive_time > Move->arrive_time){    //寻找最早到达的进程 
                Max_Pri = Move;
            }
            Move = Move->next;
        }
        Move=hear->next;
        while(Move!=NULL){    //在几个同时最早时间到达的进程中选择优先级最高的 
            if(Max_Pri->arrive_time == Move->arrive_time){
                if(Max_Pri->priority_number>Move->priority_number){
                    Max_Pri=Move;
                }
            }
            Move=Move->next; 
        }
        */
        flag=0;
        ff=0;
        while(++flag){
            Move=head->next;
            Max_Pri=head;
            while(Move!=NULL){
                if(Move->arrive_time <= system_time){    //小于等于系统时间的进程说明已经到达,小于系统时间的进程都要相互比较优先级
                    if(Move->priority_number>Max_Pri->priority_number){
                        Max_Pri=Move;
                    }    
                }
                Move=Move->next;
            }
            if(Max_Pri->cre==NULL){    //说明没有选出合适进程,需要增加系统时间
                ff=1;
                system_time++; 
            }
            else{
                break;
            }
        }
        if(ff==1){
            printf("暂无进程可执行,等待 %d 后,系统时间为: %d \n\n",flag-1,system_time);
        }
        //****************************
        Move = Max_Pri->cre;        //将上面选择的进程调入CPU运行
        Move->next = Max_Pri->next;
        if(Move->next != NULL){
            Move = Max_Pri->next;
            Move->cre = Max_Pri->cre;
        }
        //****************************
        printf("        进程 %d 被调度: \n",Max_Pri->process_name);
        Max_Pri->used_time += Time_film;    //增加CPU占用时间
        if(Max_Pri->used_time >= Max_Pri->need_time){
            if(Max_Pri->used_time==Max_Pri->need_time){
                system_time+=Time_film;
            }
            if(Max_Pri->used_time > Max_Pri->need_time){
                system_time+=(Max_Pri->used_time-Max_Pri->need_time);
            }
            Max_Pri->used_time = Max_Pri->need_time;
            Max_Pri->process_state = 0;        //进程状态改变
            count++;
        }
        else{
            system_time+=Time_film;
            Max_Pri->process_state = 1;
        }
        Max_Pri->priority_number-=1;    //优先数减1
        printf(" %d     %d     %d        %d         %d       %d\n\n",Max_Pri->process_name,Max_Pri->priority_number,Max_Pri->arrive_time,Max_Pri->need_time,Max_Pri->used_time,Max_Pri->process_state);
        if(count == N){    //所有进程执行完毕 
            printf("        所有进程执行完毕!");
            return;
        }
        if(Max_Pri->process_state==1){
            printf("进程 %d 未完成,进入就绪队列,系统时间为: %d \n\n",Max_Pri->process_name,system_time);
        }
        else{
            printf("进程 %d 已完成,系统时间为: %d \n\n",Max_Pri->process_name,system_time);
        }
        printf("        就绪队列:\n");
        //****************************
        if(Max_Pri->process_state !=0){
            Move = head;
            while( Move->next!=NULL ){    //当被调出进程未完成时将其插入就绪队列尾部
                Move = Move->next; 
            }
            Tail = Move;
            Max_Pri->cre = Tail;
            Max_Pri->next = NULL;
            Tail->next = Max_Pri;
            Max_Pri->process_state = -1;
        }
        print(head);
        //****************************
        Process_scheduling(head);
    }
    
    void print(struct PCB *head){    //输出队列函数 
        if(head->next == NULL){
            printf("就绪队列已空\n");
            return;
        }
        printf("name priority arr_time need_time use_CPU pro_state\n");
        struct PCB *fry = head->next;
        while(fry != NULL){
            printf(" %d     ",fry->process_name);
            printf("%d     ",fry->priority_number);
            printf("%d        ",fry->arrive_time);
            printf("%d         ",fry->need_time);
            printf("%d      ",fry->used_time);
            printf("%d          ",fry->process_state);
            printf("\n");
            fry = fry->next;
        }
        printf("\n"); 
    }
    
    int main(){
        struct PCB *head;    //头指针
        struct PCB Pro[N+1];    //创建 N+1 个进程-----就绪状态队列
        srand(time(0));
        
        //****************************
        //设置就绪状态进程参数
        head = &Pro[0];
        int i=0;
        for(i=0;i<=N;i++){
            if(i==0){
                Pro[i].process_name = 0;
                Pro[i].cre = NULL;
                Pro[i].next = &Pro[i+1];
                Pro[i].priority_number = -100;
                continue;
            }
            Pro[i].process_name = i;
            Pro[i].priority_number = rand()%10;
            while(Pro[i].priority_number == 0){
                Pro[i].priority_number = rand()%10;
            }
            Pro[i].arrive_time = rand()%10;
            Pro[i].need_time = rand()%7;
            while(Pro[i].need_time == 0){
                Pro[i].need_time = rand()%7;
            }
            Pro[i].used_time = 0;
            Pro[i].process_state = -1;
        }
        for(i=1;i<=N;i++){    //形成双向队列
            if( i == N ){
                Pro[i].cre = &Pro[i-1];
                Pro[i].next = NULL;
                break;
            }
            Pro[i].cre = &Pro[i-1];
            Pro[i].next = &Pro[i+1];
        }
        //****************************
        for(i=1;i<=N;i++){    //将最先到达进程的时间设置为系统开始时间 
            if(Pro[i].arrive_time<system_time){ 
                system_time=Pro[i].arrive_time;
            }
        }
        printf("系统时间为: %d \n",system_time);
        //****************************
        
        
        printf("        就绪状态进程: \n");
        print(head);    //输出就绪状态进程 
        
        Process_scheduling(head);    //调用进程调度函数(最高优先级)
        
        return 0;
    }

    (运行结果部分截图)

    16:31:29

    2018-05-18

    转载于:https://www.cnblogs.com/chiweiming/p/9028002.html

    展开全文
  • Linux进程调度算法分析

    千次阅读 2012-10-09 14:36:43
    Linux进程调度算法分析 摘要 :基于X86平台Linux2.6.26内核进程调度部分代码,刨析Linux进程调度算法,对算法的原理,实现和复杂度进行了分析并提出了算法改进措施。 关键字:Linux内核 进程调度 算法   1. ...
  • 常用的进程调度算法

    2019-12-13 21:40:18
    进程调度是由操作系统的进程调度程序按照某种策略和算法从就绪态进程中为当前空闲的CPU选择要运⾏的新进程,常用的进程调度算法有以下几种: 1. 先来先服务调度算法 从就绪队列的队⾸选择最先到达的进程,为该进程...
  • 进程调度算法解决以何种次序对各就绪进程进行处理器的分配以及按何种时间比例让进程占用处理器。 1、先来先服务算法 在所有调度算法中,最简单的是非抢占式的先来先服务(First-Come First-Served, FCFS)算法。...
  • 进程调度算法

    2016-12-18 11:05:11
    在操作系统中存在多种调度算法,其中有的调度算法适用于作业调度,有的调度算法适用于进程调度,有的调度算法两者都适用。下面介绍几种常用的调度算法。 先来先服务(FCFS)调度算法 FCFS调度算法是一种最简单的...
  • 进程调度算法FCFS和RR

    千次阅读 2018-11-16 17:20:37
    本次试验要求编写的是进程调度中的FCFS算法和RR算法(轮转法)。 FCFS算法:最简单的CPU调度算法,采取先到先服务的规则,不存在进程优先级之说,也不管进程服务时间的长短,只有前面的进程完成或者阻塞后面的进程...
  • 操作系统的常见进程调度算法

    万次阅读 多人点赞 2016-06-11 21:46:59
    在所有调度算法中,最简单的是非抢占式的FCFS算法。 算法原理:进程按照它们请求CPU的顺序使用CPU.就像你买东西去排队,谁第一个排,谁就先被执行,在它执行的过程中,不会中断它。当其他人也想进入内存被执行,...
  • 进程调度算法相关习题

    千次阅读 多人点赞 2020-04-13 10:14:22
    1.1.假设一个系统有 5 个进程,他们的到达时间和服务时间如上表所示,忽略 I/O 以及其他的开销时间,若分别按 先来先服务( FCFS ) 、 非抢占式及抢占 的短进程优先( SPF ) 调度算法进行 CPU 调度,请给出各进程...
  • Linux - 进程调度算法

    2017-02-08 17:59:58
    进程调度:  无论是在批处理系统还是分时系统中,用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外,系统进程也同样需要使用处理机。 这就要求进程调度程序按一定的策略,动态地把处理机分配给...
  • 这里先说明,进程调度算法有很多,这里实现的调度算法有先来先服务、短进程优先、高响应比优先、时间片轮转算法。此外还有一个多级反馈队列算法,因为这个算法比较复杂,之后再分析。 下面是我针对各个调度算法的...
  • 进程调度的任务是 控制 ,协调进程对于CPU的竞争,按照一定的调度算法,使某一就绪进程获得CPU的控制权,转换成运行状态。 进程调度也叫低级调度。实际上进程调度完成一台物理的CPU转变成多台虚拟的(或逻辑的)CPU...
  • LINUX 进程调度算法

    2017-02-19 20:32:56
    进程调度:  无论是在批处理系统还是分时系统中,用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外,系统进程也同样需要使用处理机。 这就要求进程调度程序按一定的策略,动态地把处理机分配...
  • 1.O(1)调度器的时间计算公式与CFS调度器Linux 2.6.23之前普遍采用...2.6.23以后的CFS呢,它是一种基于权重的非时间片调度算法进程每次执行的时间并不是固定的,而是根据进程数在一个准固定周期内按照其权重比例的时间
  • Linux之进程调度算法

    千次阅读 2019-05-29 19:28:52
           操作系统管理了系统的有限资源,当有多个进程(或多个进程发出的请求)要使用这些资源时,因为...下面是几种常见的调度算法。 1. 先来先服务(FCFS)调度算法   ...
  • 3、分别实现下面两种调度算法 •按FCFS调度算法实现处理器调度 •按SJF实现处理器调度 3、实验结果输出格式。 要求输出格式如下: 进程名 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间; 每个进程...
  • 进程调度分为: 长程调度,又称作业调度,用于决定把外存上处于后备队列中的哪些作业调入内存,并为它们创建进程、分配...常见的cpu调度算法有先到先服务调度(FCFS)、最短作业优先调度(SJF)、优先级调度(pri...
  • 处理机调度算法详解----进程调度

    千次阅读 2020-01-25 17:43:17
    进程调度调度的对象是进程,其主要任务...因为执行频率高,进程调度算法不宜过于复杂(太过复杂会占用太多CPU的时间)下面我们一起来看下进程调度的几种调度算法。 轮转调度算法、多队列调度算法、多级反馈调度算法...
  • 我们在编码开发的时候,就是在跟进程打交道。不过,可能由于一些高级语言的封装,我们在开发的过程可能感觉不到我们的代码对进程的创建或调用过程。...下面我就使用Java开发语言来模拟一下进程在操作系统中的调度过程。
  • 【操作系统 - 2】时间片轮转RR进程调度算法

    万次阅读 多人点赞 2017-03-17 23:56:31
    【操作系统 - 2】时间片轮转RR进程调度算法。学习至此,发现很多学了但很久没用的知识,久而久之,慢慢遗忘。等哪天还需要的话,却发现已经忘得差不多了,即使整理了文档(word等),还是得从头再学一遍。读研第一...
  • 进程调度算法--c语言实现

    千次阅读 多人点赞 2018-12-03 20:15:22
    下面我用c语言模拟实现了FCFS(先来先服务)、SJF(短作业优先)和RR(时间片轮转)的操作系统中的进程调度算法,还有实现结果哦~~  关于这些算法的思想,大家可以去自己找一下,我呢就用结构体数组简单的实现了一下...
  • 谈谈Linux/Windows 中使用的调度算法 如何评价调度算法的性能谈谈下面每对指标间的关系 aCPU利用率和响应时间 b平均周转时间和最大等待时间 cI/O设备利用率和CPU利用率 CPU使用率其实就是你运行的程序占用的CPU资源...
  • 常见的几种进程调度算法

    千次阅读 2017-02-19 20:22:08
    进程调度概念:操作系统必须为多个,吗进程可能有竞争的请求分配计算机资源。对处理器而言,可分配的资源是在处理器上的执行时间,分配途径是调度。调度功能必须设计成可以满足多个目标,包括公平、任何进程都不会饿...
  • Linux CFS 进程调度算法

    千次阅读 2013-08-29 10:30:23
    Linux主要实现了两大类调度算法,CFS(完全公平调度算法)和实时调度算法。宏SCHED_NOMAL和SCHED_BATCH主要用于CFS调度,而SCHED_FIFO和SCHED_RR主要用于实时调度。这几个宏的定义可以在include/linux/sched.h中找到...
  • 常见进程调度算法轮转调度算法(RR)、优先级调度算法、多队列调度算法、多级反馈队列调度算法、保证调度算法、公平分享调度算法。1 轮转调度算法(RR)(1)原理:在轮转法中,系统将所有的就绪进程按先来先服务(FIFC)...
  • 设计作业调度算法时应达到如下目标: (1) 某段时间内尽可能运行更多的作业,应该优先考虑短作业。 (2) 使处理机保持繁忙,应该优先考虑计算量大的作业,即计算型作业。 (3) 使I/O设备保持繁忙,应该优先考虑I/

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 64,510
精华内容 25,804
关键字:

下面算法不是进程调度算法