精华内容
下载资源
问答
  • 进程调度方式主要是指具有不同优先级的进程到来时如何分配CPU,调度方式主要 可剥夺 与 不可剥夺 两种。 可剥夺是当具有更高优先级的进程到来时,会强行的将正在运行进程的CPU资源分配给更高优先级的进程;不可...

    概述

    进程调度方式主要是指具有不同优先级的进程到来时如何分配CPU,调度方式主要有 可剥夺不可剥夺 两种。

    可剥夺是当具有更高优先级的进程到来时,会强行的将正在运行进程的CPU资源分配给更高优先级的进程;不可剥夺则是必须等待正在运行的进程自动释放占用的CPU,才会将CPU再次分配。

    三级调度

    通常在操作系统中,一个作业从提交到完成需要经历三级调度。

    1. 高级调度

      又称为长调度、作业调度、接纳调度。它决定处于输入池中的哪个后备作业可以调入主系统做好运行准备,称为一个或一组就绪进程。在系统中每个作业只需经过一次高级调度

    2. 中级调度

      又称为中程调度、对换调度。它决定处于交换区的哪个就绪进程可以调入内存,直接参与对CPU的竞争;而在内存资源不足时,为了将进程调入内存,则必须将内存中处于阻塞状态的进程调出至交换区,这相当于将处于内存的进程与交换区的进程交换位置。

    3. 低级调度

      又称为短程调度、进程调度。它决定内存中的哪个就绪进程可以占用CPU,低级调度是操作系统中最活跃最核心的调度程序。

    调度算法

    调度的方式有很多,但主要有下面这几类:

    1. 先来先服务

      这是最简单的方式,即按照作业提交或进程变更为就绪态的次序分配CPU。这种调度方式明显利于需要长作业的情况,但不利于需要频繁中断的作业。主要用于宏观调度。

    2. 时间片轮转

      时间片轮转即每个进程都运行一定时间,它主要用于微观调度,目的是提升资源的利用率。时间片的长度可以从几毫秒到数百毫秒不等,又有固定时间片和可变时间片两种。

    3. 优先级调度

      这种方式要求进程都有一个优先级,系统调度时总选择优先级更高的进程占用CPU,优先级的分配有两种方式:

      • 静态优先级——在创建时就确定进程优先级,直至进程终止优先级也不会发生变化,通常根据三种因素决定:进程类型、资源需求、用户要求。
      • 动态优先级——在创建时也赋予一个优先级,但运行过程中可被改变,以便调度更合理。如在就绪队列中等待越长则优先级将提高,而进程被执行一个时间片后则降低。
    4. 多级反馈调度

      它是时间片轮转及优先级的综合。优点有三:照顾短进程提高系统吞吐量、缩短平均轮转时间;照顾I/O需求较高的进程,提升I/O设备利用率和缩短响应时间;无需估计进程执行耗时,动态调整优先级。

      如下图所示:

      Multi Level Dispatch

      其具体算法如下:

      • 设置多个就绪队列Q1,Q2,,QnQ_1, Q_2, \dots, Q_n,分别对应不同优先级Q1>Q2>>QnQ_1 > Q_2 > \dots > Q_n。每个队列执行时间片的长度不同,规定优先级越低,时间片越长,逐级加倍。
      • 新进程进入内存后,先放入Q1Q_1中,按先来先服务的方式调度,若该进程在Q1Q_1中的一个时间片未能完成,则往下放入Q2Q_2中,同样按照先来先服务的方式调度。直至到QnQ_n中,在QnQ_n中按照时间片轮转方式调度。
      • 仅较高优先级队列为空时才会调度次高优先级队列的进程执行。即如有新进程进入,则会抢先执行新进程。

      进程优先级确定

      进程优先级考虑如下情况:

      1. I/O型进程——让其进入最高优先级队列,以及时响应I/O交互进程。
      2. 计算型进程——每次执行都会降低优先级,以期最终采用较长时间片执行,减少调度次数。
      3. 少数I/O型进程——I/O完成后则应逐渐降低优先级,不应长期处于高优先队列中。
    展开全文
  • 一、调度的概念 调度的基本概念 在多道程序系统中,进程的数量往往多于处理机的个数,因此进程争用处理...·通常有以下两种进程调度方式: 非剥夺(非抢占)调度方式:当一个进程正在处理机上执行时,即使有某个更为

    一、调度的概念

    1. 调度的基本概念
      在多道程序系统中,进程的数量往往多于处理机的个数,因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配,即从就绪队列中按照一定的算法(公平、高效)选择一个进程并将处理机分配给它运行,以实现进程并发执行。
      在这里插入图片描述

    二、进程调度的方式
    当某个进程正在处理机上执行时。若有某个更为重要或紧迫的进程需要处理,即有优先权更高的进程进入就绪队列,此时要考虑以某种方式分配处理机。

    ·通常有以下两种进程调度方式:

    1. 非剥夺(非抢占)调度方式:当一个进程正在处理机上执行时,即使有某个更为重要或者紧迫的进程进入就绪队列,仍然让正在执行的进程继续执行,知道该进程完成或发生某种事件而进入阻塞态时,才把处理机分配给更为重要或紧迫(优先级更高)的进程。其优点是实现简单,系统开销小,适用于大多数批处理系统,但它不能用于分时系统和大多数实时系统。
    2. 剥夺(抢占)调度方式:当一个进程正在处理机上执行时,若有某个更为重要或紧迫的进程(优先级更高)的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给这个更重要的进程。这种方式对提高系统吞吐率和响应效率都有明显的好处。但抢占也要遵循一定原则。

    三、调度的基本准则
    不同的调度算法具有不同的特性,在选择调度算法时,必须考虑算法的特性。为了比较处理机调度算法的性能,人们提出了很多评价准则,主要有一下几种:

    1. CPU利用率:CPU是计算机系统中最重要和最昂贵的资源之一,所以应该尽可能使得CPU保持忙的状态,资源利用率尽可能高。
    2. 系统吞吐量:单位时间内CPU完成的作业数量。长作业需要消耗较长的处理机时间,会降低系统的吞吐量。对于短作业,他们所需消耗的处理机时间较短,因此能提高系统吞吐量。调度算法和方式不同,也会对系统的吞吐量产生较大影响。
    3. 周转时间:周转时间是指从作业提交到作业完成所经历的时间,是作业等待、在就绪队列中排队,在处理机上运行及输入输出操作所花费的时间的总和。
    4. 等待时间:进程处于等处理机状态的时间之和。等待时间越长,用户满意度越低。实际上,处理机调度算法实际上并不影响作业执行或输入输出操作的时间,只影响作业在就绪队列中等待所花的时间。因此,衡量一个调度算法的优劣,常常只需简单地考察等待时间。
    5. 响应时间:用户提交请求到系统首次产生响应所用的时间。在交互式系统中,周转时间不可能是最好的评价准则,一般采用响应时间作业衡量调度算法的重要准则之一。从用户角度来看,调度策略应该尽量降低响应时间,使得响应时间处在用户能接受的范围之内。

    总之,想得到一个满足所有用户和系统要求的算法几乎是不可能的。设计调度程序,一方面要满足特定系统用户的要求(比如,实时和交互进程的快速响应要求),另一方面要考虑系统整体的效率(比如,减少整个系统的进程平均周转时间),同时还要考虑调度算法的开销等。

    四、几种典型的调度算法

    • 先来先服务(FCFS)调度算法
      FCFS是一种最简单的调度算法,它既可以用于作业的调度,又可以用于进程调度。在作业调度中,算法每次从后备作业队列中选择最先进入该队列的一个或几个作业,将他们调入内存,分配必要的资源,创建进程并放入就绪队列。
      在进程调度中,FCFS调度算法每次从就绪队列中选择最先进入该队列的进程,将处理机分噢诶给它,使之投入运行,直到完成或尹某种原因而阻塞时才释放处理机。
      FCFS属于不可剥夺(抢占)算法。从表面上看,它对所有作业都是公平的,但是如果有一个长作业先到达系统,就会使后面许多短作业等待很长时间,因此这种方法肯定不能作为分时系统和实时系统的调度方法,但是它常被结合在其他调度策略使用。比如在使用优先级作为调度策略的系统中,往往对多个具有相同优先级的进程按FCFS原则处理。
      · 特点分析:算法简单,但是效率低下;对长作业较为有利,对短作业不利;利于CPU繁忙型作业,不利于I/O繁忙型作业。

    • 短作业优先(SJF)调度算法
      短作业(进程)优先调度算法是指对短作业(进程)优先调度算法。短作业优先调度算法从后备队列中选择一个或若干估计运行时间最短的作业,将它们调入内存运行;短进程优先(SPF)调度算法是从就绪队列中选择一个估计运行时间最短的进程,将处理机分配给它,使之立即指向,直到完成或发生某时间而阻塞时,才释放处理机。
      但是这种算法有着不容忽视的缺点:
      ①该算法对长作业不利,SJF中长作业的周转时间会增加。更糟的是,若一旦有长作业进入系统的后备队列,由于调度程序总是优先调度那些短作业(即使是后来的短作业也会被优先安排给处理机),导致长作业长期不被调度,饿死在后备队列中。
      ②完全没有考虑作业的紧迫程度,因而不能保证紧迫的作业会被及时处理。
      ③由于作业的长短只是根据用户所提供的预估的执行时间而定的,而用户又可能会有意无意地缩短其作业的估计运行时间,使得算法不一定能真正做到短作业优先调度。
      但这算法的优点也显而易见:平均等待时间、平均周转时间最少。

    • 优先级调度算法
      又称优先权调度算法,它既可以用于作业调度,又可用于进程调度。该算法的优先级用于描述作业运行的紧迫程度。
      在作业调度中,优先级调度算法每次从后备作业队列中选择优先级最该的一个或几个作业,将他们调入内存,分配必要的资源,创建进程并放入就绪队列。在进程调度中,优先级调度算法每次从就绪队列中选择优先级最高的进程,并分配处理机,运行。
      根据新的更高的优先级进程能否抢占正在执行的进程,可将该调度算法分为如下两种:
      ①非剥夺(抢占)式优先级调度算法:当一个进程正在处理机上运行时,即使有某个更在重要或者紧迫的进程进入就绪队列,仍然让正在运行的进程继续运行,直到由于自身的原因而主动让出处理机时(任务完成或等待),才把处理机分配给更重要或紧迫的进程。
      ②剥夺式优先级调度算法:当一个进程正在处理机上运行,若有某个更为重要或紧迫的进程进入就绪队列,则立即暂停正在运行的进程,将处理机分配给更重要或紧迫的进程。
      而根据进程创建后其优先级是否可以改变,可以将进程优先级分为一下两种:
      ①静态优先级:优先级是在创建进程时确定的,并且进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。
      ②动态优先级:在进程运行过程中,根据进程情况的变化动态调整优先级。动态调整优先级的主要依据有进程占有CPU的时间的长短、就绪进程等待CPU时间的长短。
      一般来说,进程优先级可以参考一下原则:
      ①系统进程>用户进程。
      ②交互型进程>非交互型进程(前台进程>后台进程)
      ③I/O型进程>计算型进程。

    • 高响应比优先调度算法
      主要用于作业调度,是对FCFS调度算法和SJF调度算法的一种综合平衡,同时考虑了每个作业的等待时间和估计的运行时间。在每次进行作业调度时,先计算后备队列中每个作业的响应比,从中选出响应比最高的作业投入运行。
      响应比的变化规律可描述为:
      响应比Rp = (等待时间+要求服务时间)/要求服务时间
      根据公式可知:
      ①作业的等待时间相同时,要求服务时间约旦,响应比越高,有利于短作业。
      ②要求服务时间相同时,作业的响应比由其等待时间决定,等待时间越长,其响应比越高,因而它实现的是先来先服务。
      ③对于长作业,作业的响应比可以随等待时间的增加而提高,等待时间足够长时,其响应比便可升到很高,从而可以获得处理机,不会饿死。

    • 时间片轮转调度算法
      时间片轮转调度算法主要适用于分时系统。在这种算法中,系统将所有就绪进程按到达时间的先后次序排成一个队列,进程调度程序总是选择就绪队列中的第一个进程执行,即先来先服务的原则,但是仅能运行一个时间片。在使用完一个时间片后,即使进程并未完成其运行,它也必须释放出(被抢占)处理机给下一个就绪的进程,而被抢占的进程返回到就绪队列的末尾重新排队,等候再次运行。
      在时间片轮转的调度算法中,时间片的大小对系统性能有很大影响。如果时间片足够大,以至于所以进程都能在一个事件内执行完毕,则时间片轮转调度算法就退化成FCFS算法。如果时间片很小,则处理机将在进程间过于频繁地切换,使得处理机开销增大,而真正用于运行用户进程的时间将减少。因此,时间片的选择要适当,可以根据系统响应时间、就绪队列中的进程数目和系统的处理能力等决定。

    • 多级反馈队列调度算法
      多级反馈队列调度算法是时间片轮转算法和优先级调度算法的综合与发展。通过动态调整进程优先级和时间片的大小,多级反馈队列调度算法可以兼顾多方面的系统目标。例如,为了提高系统吞吐量和缩短平均周转时间而照顾短进程;为了获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程;同时,也不必实现估计进程的执行时间。
      多级反馈队列

    • 多级反馈队列调度算法的实现思想如下:
      (1)设置多个就绪队列,并为各个队列赋予不同的优先级,第一级队列的优先级最高,第二级队列次之,其余队列的优先级逐次降低。
      (2)赋予各个队列中进程执行时间片的大小各不相同。在优先级越高的队列中,每个进程的运行时间片越小。例如,第二级队列的时间片要比第一级队列的时间片长一倍…第i+1级队列的时间片要比第i级队列的时间片长一倍。
      (3)当一个新的进程进入内存后,首先将它放入第一级队列的末尾,按FCFS原则排队等待调度。当轮到该进程执行时候,如果它能在时间片内完成,便可准备撤离系统;若它在一个时间片结束时尚未完成,调度程序便将该进程转入第二级末尾,再同样按FCFS原则等待调度执行;若它在第二级队列中运行一个时间片后仍未完成,再以同样的方法进入第三级队列…如此下去,当一个长进程从第一级队列一次降到第n级队列后,在第n级队列中便采用时间片轮转方式进行。
      (4)仅当第一级队列为空时,调度程序才调度第二级队列中的进程进行;仅当第1到(i-1)级队列均为空,才会调度第i级队列中的进程运行。若处理机正在执行第i级队列中的某个进程,此时又有新的进程进入优先级较高的队列[第1到(i-1)级的任意一级],则此时行进程将抢占正在运行的处理机,即由调度程序把正在运行的进程放回第i级队列末尾,把处理机分配给新到的更高优先级进程。

    • 这种调度方法优势如下:
      (1)终端型作业用户:短作业优先。
      (2)短批处理作业用户:周转时间较短。
      (3)长批处理作业用户:经过前面几个队列得到部分执行,不会饿死。

    五、例题:

    • 根据下表给出的进程调度信息,试用Gantt图(进程调度次序图)描述分别采用FCFS、非抢占式SJF、抢占式SJF调度算法、非抢占式优先权、抢占式优先权及时间片轮转(时间片为1)算法的执行次序,并计算平均周转时间和平均等待时间。(注:优先数越大,优先权越小)
    进程 到达时刻(秒) 执行时间(秒) 优先数
    P1 0 10 3
    P2 2 1 1
    P3 4 2 3
    P4 5 1 4
    P5 6 5 2
    • 解答:
      在这里插入图片描述
    • 平均周转时间和平均等待时间的求解:
    进程 FCFS周转时间 抢占式SJF周转时间 非抢占式SJF周转时间 非抢占式优先级周转时间 抢占式优先级周转时间 时间片轮转周转时间
    P1 10S 19S 10S 10S 16S 19S
    P2 9S 1S 9S 9S 1S 1S
    P3 9S 3S 10S 14S 14S 4S
    P4 9S 1S 7S 14S 14S 2S
    P5 13S 6S 13S 10S 5S 11S
    平均周转时间 8S 6S 9.8S 11.4S 10S 7.4S

    提示:根据前面所说的周转时间求解方式和甘特图,用进程到达(提交)的时间减去最终进程完成的时间即可。

    进程 FCFS等待时间 抢占式SJF等待时间 非抢占式优先级等待时间 非抢占式SJF等待时间 抢占式优先级等待时间 时间片轮转等待时间
    P1 0S 9S 0S 0S 6S 9S
    P2 8S 0S 8S 8S 0S 0S
    P3 7S 1S 12S 8S 12S 2S
    P4 8S 0S 13S 6S 13S 1S
    P5 8S 1S 5S 8S 0S 6S
    平均等待时间 6.2S 2.2SS 7.6S 6S 6.2S 3.6S

    提示:进程到达(提交)后,只要没有执行完并且没有分配处理机,就是在等待状态,根据甘特图很直观的可以求出各进程的等待时间。

    (PS:如有误,欢迎批评指正,不胜感谢!)

    展开全文
  • 进程调度与死锁

    2018-04-14 22:18:09
    进程调度方式 非抢占式 :直到进程完成或因为某时间而不能运行时,才将CPU分配给其他进程 。通常用在批处理系统中。主要优点是简单、系统开销小 抢占式 :当一个进程正在执行,系统可以基于某种策略剥夺CPU给其他...

    1.进程调度的功能
    记录系统中所有进程的状态、优先数和资源的需求情况
    确定调度算法。决定将CPU分配给哪个进程及多长时间
    分配处理机给进程

    2.进程调度方式
    非抢占式 :直到进程完成或因为某时间而不能运行时,才将CPU分配给其他进程 。通常用在批处理系统中。主要优点是简单、系统开销小
    抢占式 :当一个进程正在执行,系统可以基于某种策略剥夺CPU给其他进程。剥夺的原则有:优先权原则、短进程优先原则和时间原则。主要用于分时系统和实时系统,以便及时响应各进程请求

    3.引进进程调度的时机
    正在执行的进程正确完成/由于错误终止运行(陷阱和中断)
    执行的进程提出I/O请求,等待其完成
    分时系统中,进程时间片用完
    按照优先级调度时,有更高的优先级进程变为就绪时(抢占方式)
    发生阻塞(执行的进程执行了wait、阻塞原语和唤醒原语时)

    4.进程调度算法的评价准则
    1)面向系统的调度性能准则
    吞吐量 处理及利用率 各个设备的均衡利用
    2)面向用户的调度性能准则
    周转时间 响应时间 截止时间 公平性 优先级
    3)调度算法本身的调度性能准则
    易于实现 执行开销比


    多级反馈队列算法(多列轮转法)
    设置多个就绪队列,分别赋予不同的优先级,队列1的优先级最高,其他逐渐降低,每队列分配不同的时间片,规定优先级越低时间片越长
    (1)新进程就绪后,先投入队列1的末尾按FCFS算法调度(先进先出调度算法,按进程进入就绪队列的先后次序,分派cpu,当前进程占用cpu,知道执行完或阻塞,才出让cpu(非抢占方式),在进程唤醒后(如i/o操作完成),并不立即恢复执行,通常等到当前进程出让cpu),(2)若一个时间片未能执行完,则降低投入到队列2的末尾,(3)以此类推,降低到最后的队列,则按时间片轮转算法(通过时间片轮转,提高进程并发性和响应时间特性,从而提高资源利用率。将就绪进程按FCFS原则,排成一个队列,每次调度时cpu分派给队首进程,执行一个时间片,时间片结束时,暂停当前进程的执行,将其送到队尾,并通过cpu现场切换执行当前队首进程。进程可以未使用完一个时间片,就让出cpu,比如阻塞)直到调度完成。(4)进程由于等待事件而放弃cpu后,进入等待队列,一旦等待的事件发生,回到原来的就绪队列。
    仅当较高优先级的队列为空,才调度较低优先级的队列中进程执行。如果进程执行时有新进程进入较高优先级的队列,则抢先执行新进程,被抢先的进程被投入到原队列末尾
    为适应一个进程在不同的时间段的运行特点,I/O完成时,提高优先级;时间片用完时,降低优先级


    CPU调度过程
    保存现场:顺序保存,最后一步保存PSW(程序状态)
    选择要运行的程序
    如果没有就绪进程,系统会安排一个闲逛进程(idle),没有其他进程时,该进程一直运行,在执行过程中可接受中断
    恢复现场:最后一步恢复选中进程的PSW


    闲逛进程——idle进程

    idle 进程,也就是0号进程,不参与schedule机制,当系统中没有任何进程可以调度(就绪队列为空),cpu会进入该进程。多cpu系统中每个cpu一个idle。
    void cpu_idle (void)
    {

    while (1) {
    void (*idle)(void) = pm_idle;
    if (!idle)
    idle = default_idle;
    while (!current->need_resched)
    idle();
    schedule();

    }

    内核初始化后,所有core都会进入该函数。pm_idle为电源管理idle函数不讨论。
    所以使用

    `default_idle`。
    #define safe_halt()             __asm__ __volatile__("sti; hlt": : :"memory")

    进入default_idle后,会执行hlt, 也就是硬件停机,处于该状态时cpu不能执行任何指令,只有通过中断请求才能唤醒。
    中断函数中设置need_resched就会进入schedule又开始正常进程调度。否则继续idle。

    系统空闲进程,一般优先级最低,系统没事干的时候就执行它。实际上在某些系统会在idle中处理一些内存回收之类的事情。其存在的原因是为了让调度器有事情做,要不然所有的进程全挂起了调度器会很郁闷的。


    产生死锁的原因:
    1)竞争资源引起死锁
    永久性资源:可以给多个进程多次使用(可再用资源)——剥夺兴资源(CPU,内存),非剥夺性资源(磁带机、打印机)
    临时性资源:只可使用一次的资源(可消耗性资源);如信号量,中断信号,同步信号
    2)进程推进顺序不当
    对资源采取“申请——分配——使用——释放”模式,由于推进不当两进程都要申请对方的资源
    进程争夺资源有可能产生死锁,但不一定就会死锁,其取决于进程推进的速度和对资源的请求的顺序。死锁是一种与时间有关的错误

    产生死锁的必要条件:
    1)互斥条件:一个资源每次只能给一个进程使用
    2)不可剥夺条件:资源申请者不能强行的从资源占有者中夺取资源,资源只能由占有者资源释放
    3)请求和保持条件:在申请新的资源的同时保持对原有资源的占有
    4)循环等待条件:存在一个进程—等待资源环形链

    死锁的预防
    预防死锁的方法是破坏死锁的四个必要条件之一

    死锁的避免
    允许进程动态的申请资源,系统在进行资源分配之前,先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换,便可将资源分配给进程;否则不分配资源,进程必须阻塞等待。从而避免发生死锁
    避免死锁的实质是使系统不进入不安全状态

    展开全文
  • 进程调度

    2016-07-29 15:04:12
     通常有以下两种进程调度方式:  (1)非剥夺调度方式(非抢占方式):实现简单,系统开销小,适用于大多数的批处理系统,但它不能用于分时系统和大多数的实时系统。  (2)剥夺调度方式(抢占方式):要遵循

    进程调度方式

        进程调度方式是指当某一处进程正在处理机上执行时,若有某个更为重要或紧迫的进程需要处理,即有优先权更高的进程进入就绪队列,此时应如何分配处理机。

        通常有以下两种进程调度方式:

        (1)非剥夺调度方式(非抢占方式):实现简单,系统开销小,适用于大多数的批处理系统,但它不能用于分时系统和大多数的实时系统。

        (2)剥夺调度方式(抢占方式):要遵循一定的原则,主要有:优先级、短进程优先和时间片原则。

    • 衡量调度性能的指标

        (1)CPU利用率:CPU在忙碌状态所占的时间比

        (2)系统吞吐量:单位时间内CPU完成作业的数量

        (3)周转时间:从作业提交到作业完成所经历的时间,包括作业等待、在就绪队列中排队、在处理机上运行以及进行输入\输出操作所花费的时间的总和。

        (4)等待时间:进程处理等处理机状态时间之和。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间,只影响作业在就绪队列中等待所花的时间。因此,衡量一个高度算法的优劣,常常只需简单地考察等待时间。等待时间=周转时间-处理机上运行时间-输入\输出所花费的时间。

        (5)响应时间:从用户提交请求到系统首次产生响应所用的时间。

    • 典型的调度算法

        (1)先来先服务(FCFS first come first serve):属于不可剥夺算法。算法每次从后备作业队列中选择最先进入该队列的一个或几个作业进行处理。特点:算法简单,效率低,对长作业有利,对短作业不利。

        (2)短作业优先(SJF short job first):算法从后备队列中选择一个或若干个估计运行时间最短的作业处理。直到完成作业或发生某事件而阻塞时,才释放处理机。缺点:(1)对长作业不利,造成“饥饿”现象(2)未考虑作业紧迫程度(3)由于运行时间是估计所得,所以并不一定能做到短作业优先。

        (3)优先级:可分为(1)非剥夺式(2)剥夺式;其中优先级可分为:(1)静态优先级(2)动态优先级

        (4)高响应比优先:响应比=(等待时间+处理时间)/处理时间=1+等待时间/处理时间

        (5)时间片轮转

    • 进程(数据库也适用)死锁

        两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去。

        (1)产生进程死锁的原因

          1)系统资源不足。

          2)资源分配不当。

          3)进程运行推进顺序不合适。

        (2)产生进程死锁的必要条件:四点

          1)互斥条件:线程在某一时间内独占资源。

          2)不剥夺条件:线程已获得资源,在末使用完之前,不能强行剥夺。

          3)请求与保持条件:一个线程因请求资源而阻塞时,对已获得的资源保持不放。

          4)循环等待条件:若干线程之间形成一种头尾相接的循环等待资源关系。

        (2)怎样避免死锁

          1)加锁顺序:确保所有的进程都是按照相同的顺序获得锁。

          2)加锁限时:在尝试获取锁的时候加一个超时时间,若超过了这个时限该进程则放弃对该锁请求。

          3)银行家算法,每次在分配资源之前,先判断资源分配后,系统是否会进入不安全的状态,会则不分配,不会则分配。

          3)死锁检测:检测如果发生死锁,通过外边破坏产生死锁的四个必要条件,打破死锁。   

    • 饥饿(无限期阻塞)

        当进程的等待时间过长,给进程推进和响应带来明显影响时,称发生了进程“饥饿”。当“饥饿”到一定程度的进程被赋予的任务即使完成也不再具有实际意义时称该进程被“饿死”。

        饥饿产生的主要原因:进程所请求的资源(可以是CPU资源)长时间得不到满足,从而长时间处于阻塞或就绪状态。

        饥饿与死锁的区别:(1)进入饥饿的进程可以只有一个,而死锁的进程至少有两个。(2)饥饿状态的进程可以是就绪状态和阻塞状态,而处于死锁的进程一定是阻塞状态。

    展开全文
  • 进程调度进程序度的概念(1)高级、中级和低级调度A、高级调度...C、低级调度低级调底是用于将内存中就绪队列中的作业分配处理机,使共执行(2)进程调度方式进程调度通常有以下两种方式A、非剥夺方式B、剥夺方式
  • 进程调度算法

    2019-10-26 14:59:34
    进程调度的原因: 在操作系统中,由于进程综述多于处理机,它们必然竞争处理机,为了充分利用计算机系统中的CPU资源,让计算机系统能够多快好省...通常有以下两种调度方式: 1)非剥夺调度方式,又称非抢占方式 是指...
  • 操作系统进程调度算法(c语言实现)

    万次阅读 多人点赞 2019-12-03 17:15:00
    进程调度算法 一、先来先服务(FCFS) 基本思想:先到达的进程先进入就绪队列,先进行调度的原则。非抢占方式。 二、短作业优先(SJF) 基本思想:根据进程中的执行时间,选取执行时间最短的作业优先调度;可抢占...
  • 进程调度分为高级、中级、低级调度:  高级调度通常也称作业调度,用于决定把外存上处于后备队列中的哪些作业调入内存,... 进程调度通常有以下两种方式: (1)非剥夺方式:分派程序一旦把处理机分配给某进程...
  • 接下来主要介绍一下进程的几种调度方式。 一般系统会同时运行交互进程和后台进程,而标准的内核算法通常能够提供足够的性能和响应度。但通常一下几点要求: 需要提供担保最大响应时间。 高优先级进程...
  • linux进程调度解析

    千次阅读 2007-04-17 09:38:00
    1调度器的启动通常有两种方式:A. 主动式在核心应用中直接调用schedule()。这通常发生在因等待核心事件而需要将进程置于挂起(休眠)状态的时候--这时应该主动请求调度以方便其他进程使用CPU。下面就是一个主动调度...
  • Linux 2.4进程调度分析 5

    千次阅读 2004-05-29 16:02:00
    2. 调度器工作时机调度器的启动通常有两种方式:A. 主动式在核心应用中直接调用schedule()。这通常发生在因等待核心事件而需要将进程置于挂起(休眠)状态的时候--这时应该主动请求调度以方便其他进程使用CPU。下面...
  • 一、进程调度的原因 在操作系统中,由于进程综述多于处理机,它们必然竞争处理机。为了充分利用计算机系统中的CPU资源,让计算机系统能够多快好省地完成我们让它做的各种任务,所以...通常有以下两种进程调度方式
  • 调度-资源调度算法

    2019-06-19 16:19:00
    一个调度平台,可以根据业务需要选择不同的调度算法,这里的作业资源调度算法跟操作系统的进程资源调度算法相似性,但是不存在操作系统的系统进程用户进程调度划分,这里按照通俗的理解,例举一些常用的作业资源...
  • 进程

    2019-07-11 17:57:03
    目录进程的概念进程间的通信匿名管道命名管道FIFO消息队列信号量共享存储进程调度 进程的概念 进程(Process)是计算机中的程序关于某数据集合上的一次运行...IPC的方式通常有管道(包括无名管道和命名管道)、消...
  • 进程调度方式: 非抢占式 抢占式 轮转调度算法 优先级调度算法 多队列调度算法 多级反馈队列调度算法 基于公平原则的调度算法 实时调度 针对实时性要求的任务,其调度要满足对截至时间的要求 1. 基本条件 ...
  • 1.进程与线程什么是进程,在计算机系统内进程是包括I/O,虚拟内存,处理器在内的一种抽象概念,通常情况下,一个程序就是一个进程。在Android应用程序中可以给四大组件指定android:process属性来创建多线程。什么是...
  • 二、进程调度的方式 在Linux中,线程是由进程来实现的,线程可以理解为轻量级的进程。因此线程的调度是按照进程的调度方式来进行调度的 (1)SCHED_OTHER,分时调度策略 (2)SCHED_FIFO,实时调度策略,先到先...
  • 常用调度算法

    2018-11-30 20:47:50
    不同的系统和系统目标,通常采用不同的调度算法——适合自己的才是最好的。 1、先来先服务调度算法FCFS 2. 短作业(进程)优先调度算法SJF/SPF: 优点:通过上表可见采用SJF/SPF算法,平均周转时间、平均带权周转...
  • 有进程调度的调度队列模型 通常,将进程组织组织成FIFO队列,新创建的进程将插在队列末尾,按照时间片轮转的方式运行。 进程执行三种情况: 在时间片内完成进程,将提前释放处理机 时间片内未完成,将该进程放...
  • 作业调度算法

    2016-08-31 20:45:26
    作业调度算法1.先来先服务(FCFS, First Come First Serve)是最简单的调度算法,按先后顺序进行调度... 在作业或进程唤醒后(如I/O完成),并不立即恢复执行,通常等到当前作业或进程出让CPU。适用场景: 比较...
  • 批处理任务通常**并行(或者串行)**启动多个计算进程去处理一批工作项(work item),处理完成后,整个批处理任务结束。 按照批处理任务实现方式的不同,批处理任务可以分为以下的几种模式: Job Template ...
  • 操作系统中调度算法调度算法FCFS(First Come First Service)先来先服务SPN(Short Job First)最短进程优先SRT(Shortest Remaining Time)最短剩余时间...一个调度能否被抢占,对进程的顺序极大的影响。 FCFS
  • 进程 与 线程的异同

    2020-09-03 10:59:45
    有进程,后面再有线程 2.概念不同 进程进程是程序真正运行起来的实例,是系统分配资源与调度的基本单位 线程: 是CPU调度的基本单位 3.内存共享方式不同 进程: 操作系统给不同进程分配一定的内存,不同进程的...
  • 九、进程控制

    2020-05-23 17:04:13
    概念:进程具有由创建而产生、由调度而执行、由撤销而消亡的生命周期,因此,操作系统要进程生命周期的各个环节进行控制的功能,这就是进程控制。 操作系统的内核:通常将一些与硬件紧密相关的模块,各种常用...
  • Linux进程(一)

    2017-12-06 00:06:06
    Linux 使用了一个被称为“进程调度”的方式。首先,为每个进程指派一定的运行时间,通常以毫秒为单位,然后依照某种规则,从众多的进程中挑选一个运行,在此时间内,其他进程为等待状态。当正在运行的程序时间耗尽,...
  • ⑴作业:指在一次应用业务处理过程中,用户提交给OS处理的一个独立任务,用户通常通过作业说明书或特定控制命令来说明作业执行的控制方式。 ⑵作业步:在作业运行期间,经过的若干个相对独立又相互关联的顺序加工...
  • 进程调度进程调度时机 进程调度需求的分类: 第一种分类方式: I/O -bound(频繁进行I/O,通常会花很多时间等待I/O操作) CPU-bound(计算密集型、需要花大量CPU时间进行运算) 第二种分类方式: 批处理进程...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 170
精华内容 68
关键字:

进程调度方式通常有