精华内容
下载资源
问答
  • 处理作业调度问题是一个典型的非线性规划问题,针对具有条件限制的处理作业调度问题,提出了一种基于改进的植物生长模拟算法(IPGSA)来搜索问题解的空间.该方法首先将条件限制和目标函数定义为该问题的...
  • 操作系统之处理机调度算法

    千次阅读 多人点赞 2018-06-21 17:26:21
    处理机调度算法道程序系统中,调度实际上是一种资源分配,即对处理资源的分配;处理机调度算法是指根据处理分配策略所规定的处理分配方法; 处理调度 处理调度的层次 高级调度 高级调度又...

    处理机调度算法


    在多道程序系统中,调度实际上是一种资源分配,即对处理机资源的分配;处理机调度算法是指根据处理机分配策略所规定的处理机分配方法;

    处理机调度

    处理机调度的层次

    1. 高级调度

      高级调度又称为长程调度或者作业调度;其调度对象是作业;主要功能是根据调度算法决定从外存中的后备队列中选择哪几个作业调入内存,为它们创建进程、分配必要的资源,然后将其放入就绪队列。高级调度主要用于多道批处理系统中,在分时系统和实时系统中不设置高级调度;

    2. 低级调度

      低级调度又称为短程调度或者进程调度;其调度的对象是进程;主要功能是根据调度算法决定哪个进程可以获得处理机而运行,由分派程序将处理机分配给被选中的进程;进程调度是一种基本调度,多道批处理系统、分时系统和实时系统都需要设置这种调度;

    3. 中级调度

      中级调度又称为中程调度或者内存调度;其调度对象是进程;主要功能是将暂时不能运行的进程调至外存等待,此时进程即处于就绪驻外存状态(挂起状态);当它们具备运行条件而且内存空间又允许的时候,由中级调度来决定把处于外存上的那些具备运行条件的就绪进程再调入内存,修改其状态为就绪状态; 中级调度其实就是存储器管理中的对换功能。

    长程调度、中程调度以及短程调度是根据程序的运行频率和周期来划分的;长程调度运行频率最低,所以其周期较长;短程调度最为频繁,为避免调度本身占用过多CPU时间,其调度算法不能过于复杂,即运行周期最短;而中程调度不论运行频率还是运行周期都在两者之间;

    处理机调度算法的目标

    一般而言,一个操作系统采用什么样的调度方式和算法,取决于系统的类型以及设计目标;

    处理机调度算法的共同目标

    1. 资源利用率。为提高系统资源的利用率,应使系统中的处理机和其它所有资源都尽可能的处于忙碌状态;其中CPU的利用率可以使用该式计算:CPU的利用率=CPU的有效工作时间/(CPU有效工作时间+CPU空闲等待时间);
    2. 公平性。公平性是指应使各个进程都获得合理的CPU时间,不会发生进程饥饿现象;但是公平是相对的,即同一类进程应获得相同的服务,但是不同类的进程由于进程的紧急程度或者重要性不同,则应区别对待;
    3. 平衡性。系统中的资源多种多样,有的属于计算型作业,有的属于IO型,调度算法应使系统资源的使用保持平衡;
    4. 策略强制执行。对于所制定的策略,如安全策略,只要需要,就必须准确地执行;

    批处理系统的目标

    1. 平均周转周期短。作业的周转周期是指从作业提交给系统到作业完成为止这段时间;周转周期通常由四部分组成:作业在外存上后备队列中的等待时间、进程在就绪队列中的时间、执行时间和等待IO操作等阻塞的时间;

      对于用户而言,希望自己的作业周转周期尽可能地短;对于系统而言,希望作业的平均周转周期短,这样不但有利于提高系统资源的利用率也可以使大多数用户满意;总的来说,应使作业的周转周期和平均周转周期都较短;

      平均周转周期T=(所有作业的周转周期之和)/作业总数;

      为了进一步反映调度的性能,更清晰地描述进程在其周转时间中等待和执行时间的具体分配状况,通常使用加权周转时间W,即作业的周转时间T与系统为它提供服务的时间Ts之比:W=T/Ts;平均加权周转周期为各个作业的加权周转时间之和/作业总数;

    2. 系统吞吐量大。如果单纯为了提高系统的吞吐量,应尽量执行较短的作业运行;吞吐量被定义为单位时间里,系统完成的作业数;

    3. 处理机效率高。由于CPU十分昂贵,使得处理机的利用率成为衡量系统性能的重要指标;而调度方式和调度算法由对处理机的利用率起着十分重要的作用。如果单纯提高处理机效率,那么应选择计算量大的作业运行。

    分时系统的目标

    1. 响应时间快。响应时间快是分时系统中调度算法的重要准则,所谓响应时间由三部分组成:命令输入时间、CPU处理时间、命令结果返回时间;
    2. 均衡性。不同的用户对响应时间的要求不同,简单任务要求较短的响应时间,复杂的任务允许较长的响应时间,均衡性是指,系统的响应时间应该和用户所请求任务的复杂度相适应;

    实时系统的目标

    1. 对截止时间的保证。对实时系统而言,调度算法的一个主要目标就是保证实时任务对截止时间的要求;其中对HRT任务,需要调度方式和调度算法必须确保对截止时间的要求;对SRT任务,要求调度方式和调度算法基本可以保证对截止时间的要求;
    2. 可预测性。在实时系统中,可预测性十分重要,主要是通过可预测性提高系统的实时性;

    作业调度

    作业是比程序更加广泛的概念,其中包括程序、数据和作业说明书,系统根据作业说明书来对程序的运行进行控制;

    作业控制块(JCB)

    1. 引入作业控制块的目的:管理和调度作业,系统为每个作业设置一个作业控制块JCB,它是作业在系统中存在的标记;
    2. 作业控制块的内容:它保存了系统对作业进行管理和调度所需要的全部信息。这些内容有:作业标记、用户名称、用户账号、作业类型(CPU型繁忙型、IO型、批量型、终端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、内存大小等)、资源的使用状况等;

    作业运行的三种状态

    1. 收容状态。操作员将作业输入到硬盘上,为其建立JCB,将其放入作业后备队列中,等待调度,此时的状态称为收容状态;此时作业在外存上;
    2. 运行状态。作业被调度算法选中,为其分配了所需要的资源并建立了进程,将其进程插入到就绪队列中。从作业第一次进入就绪队列开始到作业完成,作业均处于运行状态;
    3. 完成状态。当作业完成、或者发生异常情况而提前结束时,作业将进入完成状态,系统中的相应程序将回收分配的资源和JCB,并将作业运行的结果输出;

    作业调度的主要任务

    作业调度的主要任务就是根据JCB中的内容,检查系统资源情况是否满足作业的要求,并按照一定的调度算法,从外存的后备队列中选择某些作业调入内存,为它们创建进程、分配资源,然后将进程插入到就绪队列中等待调度;其实归根到底需要解决两个问题:

    1. 接纳多少个作业

      这是由系统的多道程序度(Degree of Multiprogramming)决定的,即允许多少个作业同时出现在内存中;对系统而言,当然希望装入较多的作业以提高CPU的利用率和系统的吞吐量,但是内存中的作业过于多时,由于内存不够而引发的中断就会急剧增加,从而影响系统效率和服务质量;因此,多道程序度是由计算机系统的规模、运行速度、作业大小、以及能否获得较好的系统性能等确定的;

    2. 接纳那些作业

      最简单的调度算法是先到先服务算法;较常见的一中调度算法是短作业优先算法;另一种常见的算法是基于作业优先级的调度算法;比较好的调度算法是响应比高者优先算法;

    值得注意的是,作业调度只有在多道批处理系统中才有;因为分时系统因为要保证较高的响应性,所以用户输入的命令和数据被直接送入内存;所以分时系统中需要考虑的是如何控制用户的数量,无需考虑长程调度问题。实时系统也是类似;

    先来先服务算法(FCFS,First-Come First-Served)

    FCFS调度算法中,优先选择先到的作业或者进程进行服务,或者说,它选择的是在队列中等待时间最长的作业或者进程,而没有考虑作业自身的情况,比如作业的优先级、作业的预计运行时间等;基本上FCFS算法很少作为系统的主调度算法,但经常把它和其他调度算法相结合使用。

    该调度算法既可以用于作业调度也可以用于进程调度(即适用于长程调度和短程调度);

    短作业优先调度算法(SJF,Short-Job First)

    短作业优先算法使用作业或者进程的长短来标记它们的优先级,越短的作业(进程)其优先级越高;

    短作业优先调度算法相比先来先服务算法有了明显的感改进(考虑了作业或者进程自身的相关信息),但是仍然有缺点:

    1. 必须预知作业的运行时间,这不是很容易做到,如果估计偏低,那么系统可能会提前终止作业,而作业此时尚未完成;所以一般都偏长估计;
    2. 对长作业非常不利,一个极端的现象就是长作业根本得不到运行,即系统中总是有比该作业更短的作业,从而出现饥饿现象;即便在普通情况下,长作业的周转周期也会明显增长;
    3. 无法实现人机交互(需要交互的程序得不到运行);
    4. 没有考虑作业的紧急程度,不能保证紧迫的作业得到及时的处理;

    该调度算法既可以用于作业调度也可以用于进程调度;

    优先级调度算法(PSA,Priority-Scheduling Algorithm)

    优先级调度算法中选择作业或者进程的标准是它们的优先级,优先级越高,越早获得调度而执行;其实FCFS中,作业或者进程的等待时间就相当于其优先级;SJF中,作业的长度就相当于其优先级;但是这种优先级并不能反映作业或者进程的紧急程度;PSA算法就是要保证紧迫性任务得到优先运行;

    该调度算法既可以用于作业调度也可以用于进程调度;

    高响应比优先调度算法(HRRN,Highest Response Radio Next)

    FCFS算法中,只考虑作业或者进程等待的时间;SJF算法中,只考虑了作业或者进程的运行时间;高响应比优先调度算法既考虑了等待时间也考虑了作业或者进程的要求时间;是一种动态优先级设定;其优先权计算公式:优先权=(要求服务的时间+等待时间)/要求服务的时间;这样,当两个作业或者进程等待了相同时间时,短作业将获的较大的优先级,类似SJF调度方式;当两个进程要求服务时间相同时,等待时间长的作业将获得较大的优先级,类似于FCFS调度方法;这种调度方法的问题就在于每次进行调度时需要进行响应比的计算,于是会增加一定的系统开销;

    进程调度

    进程调度的任务

    进程调度的主要任务有三:

    1. 保留处理机线程。将当前进程的处理机现场记录到PCB中,包括程序计数器、多个通用寄存器的内容;
    2. 按照某种算法选择下一个执行的进程。调度程序将从就绪队列中选择一个进程,改变其运行状态,将处理机分配给它;
    3. 将处理机分配给进程。由分派程序将处理机分配给该进程,此时需要将对应的PCB中的内容装入相应的寄存器内,让其从上一次中断的地方开始执行;

    进程调度机制

    为实现进程调度,进程调度机制中,应具有以下三个部分:排队器、分派器和上下文切换器;

    1. 排队器的主要任务是将就绪状态的进程组织为一个或多个队列,以便调度程序可以可以快速找到它;每当一个进程转入就绪状态,排队器就把它插入到相应的就绪队列;
    2. 分派器的主要任务是将调度程序所选择的进程从就绪队列中取出来,然后进行从分派器到新进程的上下文切换;
    3. 上下文切换器的主要任务是,在发生进程切换时,首先将当前进程的相关信息存储到对应的PCB中,然后装入分派程序;然后将分派程序的上下文移出,装入新进程的处理机信息;即一次进程切换中,发生了两次处理机上下文的切换;

    由于一次上下文切换中需要执行大量的load和store命令,所以比较费时,现代系统以实现靠硬件来减少上下文切换时间;当然也可以采用两组寄存器,其中一组寄存器供处理机在系统态时使用,另一组寄存器供应用程序使用。这样只需改变指针即可实现上下文的切换;

    进程调度的方式

    早期系统大多采用非抢占式调度方式,但是这很难满足交互性作业和实时任务的需求,后来在进程调度方式中又引入了抢占式调度方式;

    1. 非抢占式调度

      非抢占式调度方式中,一旦把处理机分配给某个进程,就让它一直运行下去,绝不会因为时钟中断或其他原因而抢占当前正在运行进程的处理机,直到该进程完成或者因某事件而阻塞,才将处理机分配给其他进程;非抢占方式中,引起进程调度的原因有:

      1. 正在执行的进程正常结束,或者因为某事件而无法继续执行;
      2. 正在执行的进程提出IO请求而暂停执行;
      3. 在进程同步和通信中,执行了某种原语操作,如挂起原语等;

      这种调度方法的特点是系统开销小,简单,适合大多数批处理系统,但是不能用于分时系统和实时系统;

    2. 抢占式调度

      抢占式调度中,允许调度程序按照某种原则,暂停某个正在执行的进程;将已分配给该进程的处理机分配给另一进程;现代OS中广泛采用抢占式调度,这是因为,抢占式调度方法可以防止一个长进程长时间占用CPU,以确保处理机能为各个进程提供更为公平的服务,另外在分时系统中,只有抢占式调度才能实现人-机交互。实时系统中,抢占式可以满足实时任务的要求。但是抢占式实现起来比较复杂,系统开销较大;

      抢占不是一种任意的行为,它必须遵守一定的规则:

      1. 优先权原则:只有优先级高的进程才能抢占优先级低的进程的处理机,反之不行;
      2. 短进程优先原则:当新来进程所要求的服务时间明显少于当前执行进程还需要执行的时间时,发生抢占;
      3. 时间片原则:各进程按时间片轮转执行时,当正在执行的进程的一个时间片用完后,便停止该进程的执行;

    进程调度算法

    1. 轮转调度算法(RR,Round Robin)

      分时系统中最简单也是最常用的算法;该方式采用非常公平的处理机分配方法,即采用FCFS策略组织就绪队列,让就绪队列中的每一个进程每次都运行一个时间片;这种方法中,进程的切换发生在:

      1. 若时间片尚未用完,正在执行的进程便已完成,就立即激活调度程序;将其从就绪队列中删除,从就绪队列中选择队首进程运行,同时启动一个新的时间片;
      2. 若时间片用完,计时器中断处理程序被激活;如果进程尚未运行完毕,就把它送入就绪队列的末尾,重新排队;

      时间片大小的选取对系统性能有着很大的影响;若选择小的时间片,那么短作业则可能在一次时间片中就结束运行,但是时间片过小,那么系统将频繁发生进程调度和处理机上下文切换,增加系统开销;反之,若时间片太长,则RR退化为FCFS,无法满足短作业和交互式作业的需求;一个可取的策略就是时间片大小应略大一一次交互所需要的时间,这样使大多数交互式作业可以在一个时间片里完成,从而获得较小的响应时间;

    2. 优先级调度算法

      优先级调度算法中,将处理机分配给就绪队列中优先级最高的进程。按照是否允许抢占,分为抢占式和非抢占式;

      1. 非抢占式优先级调度算法

        该算法中,一旦将处理机分配给就绪队列中优先级最高的进城后,该进程便一直执行下去,直到结束(正常结束或者被阻塞、挂起等)才将处理机分配给就绪队列中另一优先级最高的进程;

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

        该算法中,把处理机分配给优先级最高的进程,使之执行,但是如果在其执行期间出现优先级更高的进程,调度程序就将处理机分配给新的优先级最高的进程;抢占式优先级调度算法常用于对实时性要求较高的系统中;

      优先级的类型——静态优先级和动态优先级:

      1. 静态优先级在创建进程的时候就已经设定,其运行周期内不再改变;常使用0-255中的一个整数来表示其优先级大小;设定静态优先级时需要考虑进程的类型,通常系统进程的优先级高于用户进程的优先级;进程对于资源的需求量,一般来说,需求量小的具有较高的优先级;用户的要求;静态优先级实现较为简单,系统开销小,但是不够精确,可能出现优先级低的进程长时间得不到运行的情况;
      2. 动态优先级是指进程的优先级会随着其运行发生改变,常见的需要考虑的变量有进程的初始优先级和等待时间等;
    3. 多队列调度算法

      多列调度算法中,将就绪队列组织为多个按照不同调度算法调度的就绪队列,以满足不同用户对调度策略的不同要求,并且这些就绪队列本身也可以设定优先级,方便在多处理机系统中为每个处理机设置一个单独的就绪队列;避免了仅有一个就绪队列时调度算法的固定、单一。这样对于含有多个线程的进程,可以将这些线程分配在一个就绪队列中,全部在一个处理机上运行;对于一组需要相互合作的进程而言,可以将其安排在一组处理机所对应的多个就绪队列中,使它们可以同时获得处理机并发执行;

    4. 多级反馈队列调度算法(Multileved feedback queue)

      前面介绍的进程调度算法,或多或少都有一定的局限性,如果未能指明进程的长度,则短进程优先和基于进程长度的抢占式调度算法都将无法使用。多级反馈队列不用提前知道各种进程的执行时间,还可以较好地满足各种类型进程的需要,是目前公认的一种较好地进程调度算法;它的核心为

      1. 设置多个就绪队列;系统中设置多个就绪队列,并且每个就绪队列也有自己的优先级。第一个队列的优先级最高,以此降低;该算法为每个队列中的进程所分配的时间片大小也是不同的,优先级越高的队列,其所分配的时间片越小(便于进程向低优先级转移);
      2. 每个队列都采用FCFS算法。当新进程进入内存时,将其放入第一队列的末尾,然后按照FCFS等待调度;如果该进程在时间片内完成,便撤离系统;否则进入第二队列末尾等待调度;当进程进入最后一个队列时,便采用RR方式运行;
      3. 按照队列优先级调度。调度程序首先调度最高优先级队列中的进程运行,仅当第一队列空闲时才调度第二队列中的进程;如果处理机正在第x队列中为某进程服务时,有新进程进入任意优先级较高的队列,那么该进程立即被送回第x队列末尾,将处理机交给新到的高优先级进程;

      多级反馈队列中,可以使短作业较早的完成,而且长作业经过第1,2,3…队列的执行,到最后一个队列时,采用RR调度算法,也不用担心过其作业长期得不到处理;

    5. 基于公平原则调度算法

      以上几种调度算法,保证了优先运行,但是并不能保证作业占用多少处理时间。另外也没有考虑调度的公平性;这里有两种相对公平的调度算法

      1. 保证调度算法,它向用户所做出的保证不是优先运行而是明确的性能保证,一种比较容易实现的性能保证算法是处理机分配的公平。如果系统中有n个进程,那么需要保证每个进程都获得相同的处理机时间1/n;实施公平调度算法时,系统需要:

        1. 跟踪计算每个进程自创建以来已执行的时间;
        2. 计算每个进程应该获得的处理机时间;
        3. 计算进程获得处理机时间的比率;
        4. 比较各个进程的这个比率,然后选择最小的进程,将处理机分配给它,并让该进程一直运行下去,直到超过最接近它的进程比率为止;
      2. 公平分享调度算法

        公平的角度不同,所使用的算法也就不同;保证调度算法对进程是公平的,但是对用户就不一定:有的用户拥有的进程多,有的用户拥有的进程少。公平分享算法是用户层面的公平调度算法。

    实时调度

    实时系统中存在两类不同的任务:硬实时任务和软实时任务;它们都关联着一个截止时间;实时调度算法必须能够满足实时任务对截止时间的要求;所以实时调度算法有一定的条件。

    实现实时调度的基本条件

    1. 提供必要的信息:系统应向调度程序提供有关任务的信息
      1. 就绪时间:某项任务进入就绪队列的时间;
      2. 开始截止时间和完成截止时间;
      3. 处理时间,从开始执行到结束需要的时间;
      4. 优先级,如果某项任务开始截止时间的错过将势必引起故障,那么将赋予该任务绝对的优先级;如果其开始截止时间的错过,对任务的继续运行没有重大影响,那么可以赋予该任务相对的优先级;
      5. 资源要求;
    2. 系统的处理能力强。如果系统的处理能力不够,那么很有可能因处理机忙不过来而导致一些实时任务得不到执行;提高系统处理能力有两种途径:一是使用单处理机系统,但是需增强其处理能力,以显著降低对每一个任务的处理时间;二是采用多处理机系统。
    3. 采用抢占式调度机制。广泛采用抢占式机制,可以满足HRT任务对截止时间的要求;但是这种调度机制实现比较复杂,对于一些小的实时系统,如果能预知任务的开始截止时间,则对实时任务的调度可以采用非抢占式调度机制,以降低调度程序和任务调度是所花费的系统开销;如果采用非抢占式调度机制,应使每个实时任务都比较小,以便能及时将自己阻塞起来,以便释放处理机;
    4. 具有快速切换机制。一是对中断的快速响应能力,对紧迫的外部事件请求中断能及时响应,要求系统具有快速硬件中断机制,还应使禁止中断的时间间隔尽量短,以避免耽误其他紧迫任务;二是快速的任务分派能力,为了提高分派程序进行任务切换的能力,应使系统中的每个运行功能单元适当的小,以减少任务切换的时间花销;

    实时调度算法的分类

    按照任务类型可以分为:硬实时任务调度算法和软实时任务调度算法;按照调度方式可以分为:抢占式调度算法和非抢占式调度算法;

    1. 非抢占式调度算法
      1. 非抢占式轮转调度算法:将实时任务组织为一个轮转队列,调度程序每次选择队列中的第一个任务投入运行,当该任务运行完毕后即将其放入轮转队列末尾等待。这种调度算法可以获得数秒到数十秒的响应时间,可用于不太严格的实时控制系统;
      2. 非抢占式优先调度算法:即使用优先权组织轮转队列;这种调度算法经过精心处理后,可以获得数秒到数百毫秒的响应时间,可用于有一定要求的实时控制系统;
    2. 抢占式调度算法
      1. 基于时钟中断的抢占式调度算法。在某实时任务到达时,如果它的优先级高于当前任务的优先级,这是并不立即抢占当前任务的处理机,而是等待时钟中断发生时,调度程序才剥夺当前任务的执行;这种算法可以获得较好的响应效果,其调度延迟可以降低到几十到几毫秒,可用于大多数实时任务系统中;
      2. 立即抢占的优先级调度算法。在这种调度策略中,要求操作系统有较高的快速响应外部事件中断的能力;一旦出现外部中断,只要当前任务没有处于临界区便立即剥夺当前任务的执行。这种调度算法可以获得非常快的响应,可把调度延迟减低到几毫秒到几百微秒;

    最早截止时间优先算法(Earliest Deadline First)

    该调度算法中,根据任务的截止时间确定任务的优先级,任务截止时间越早,优先级越大;具有最早截止时间的任务排在队列队首;调度程序选择任务时,直接选择就绪队列中的第一个即可;按照非抢占式和抢占式可以分为:抢占式最早截止时间优先和非抢占式最早截止时间优先这两种。非抢占式算法是指在某个任务执行的过程中,如果新到的任务的截止时间早于正在执行的任务的截止时间,并不会发生抢占;而抢占式则相反,会立即将处理机分配给优先级大的任务;通常而言,非抢占式常用于非周期性任务;抢占式常用于周期性任务;

    最低松弛度优先算法(Least Laxity First)

    该调度算法中,根据任务的紧急程度来确定任务的优先级,越紧急的任务,其优先级越大;而越紧急也意味着它的松弛度越低;在该算法中,任务的松弛度由任务的完成截止时间减去任务要求的处理时间来确定;该算法通常用于可抢占方式中;一般来说,抢占发生在某一任务的最低松弛度为0的时候,即该任务不得不执行,而考虑到任务切换的时间,通常还会提前一点;所以调度发生的情况为:某一任务正常结束或者某一任务的最低松弛度变为0;

    优先级倒置现象及其解决方法

    由于进城之间存在两种约束(直接约束和间接约束),所以有可能出现具有高优先级的进程因低优先级的进程而阻塞的情况;这种情况被称为优先级倒置;比如,低优先级A首先获得了临界资源R(因为比它高级的进程还没到),然后有比它优先级高的进程B到来,A被剥夺处理机,但是临界资源并没有被释放,之后用于最高优先级的进程C到来,B被抢占处理机,而C由于请求临界资源R失败而阻塞(进入阻塞队列),之后B开始运行,结束后A再运行临界区代码,进程A释放临界资源R后,C才能执行。这样B进程比C进程优先级低,但是先得到处理;常见的解决方法有两种:一是当进程处于临界区的时候,不允许中断,这样A执行完毕后,因为C的优先级高,处于就绪队列的前面,所以C可以在B之前执行;但是当A的临界区非常长,则C还是要等待较长时间;另一种办法是建立在动态优先级继承基础上的,该方法规定,当优先级较高的进程要进入临界区,使用临界资源,如果有一个低优先级进程正在使用该资源,那么高优先级进城被阻塞,而低优先级进程将继承高优先级进程的优先级,直到低进程退出临界区;这样就可以避免低进程被中等进程阻塞而出现优先级倒置现象;

    展开全文
  • 处理机调度算法(时间调度)

    千次阅读 2013-12-14 20:50:11
    南昌航空大学实验报告 课程名称: 操作系统 实验名称: 处理调度 ...要求掌握几种处理机调度算法的基本思想和特点,理解并发与并行的区别,学会设计处理调度算法 二 实验内容: 时间片轮转算法: 时间片轮转调

    南昌航空大学实验报告

    课程名称:  操作系统              实验名称:   处理机调度

    班级:110462          姓名:XXX    学号:  11046208

    一 实验目的:

    编写程序以下面三种方式之一模拟处理机调度。要求掌握几种处理机调度算法的基本思想和特点,理解并发与并行的区别,学会设计处理调度算法

    二 实验内容:

    时间片轮转算法:

    时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法,又称RR调度。每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间。

    时间片设得太短会导致过多的进程切换,降低了CPU效率;而设得太长又可能引起对短的交互请求的响应变差。将时间片设为100毫秒通常是一个比较合理的折衷。

    三 实验分析:

    每个任务都只运行一个固定的时间片或者但程序运行结束的时候时间片还有剩余则主动转向另外一个程序执行;所以需要设置程序时片的大小,也需要设置以上的第二种情况发生的时候,自动转向另外一个程序;

    设计思路:

    1        设计一个队列,需要运行的进程作为结点,保存需要进行运行的程序,

    2        设计调度一个队列的处理算法,也就是设计时间片轮转调度;

    四 实验程序代码设计:

    package com.rainplus.processor;
    
    public class Processor {
    	private long cpuTime = 3000l; // 设置时间片大小
    
    	class ProcessQueue {
    		private ProcessNode first;
    		private ProcessNode last;
    		private long size = 0;
    
    		public void insert(ProcessNode pn) {
    			if (size == 0) {
    				first = pn;
    			} else {
    				last.setNext(pn);
    			}
    			last = pn;
    			size++;
    		}
    
    		public void delete() {
    			Process p = first.getProcess();
    			first = first.getNext();
    			size--;
    		}
    	}
    
    	class ProcessNode {
    		private Process process;
    		private ProcessNode next;
    
    		public void setProcess(Process p) {
    			process = p;
    		}
    
    		public Process getProcess() {
    			return process;
    		}
    
    		public void setNext(ProcessNode pn) {
    			next = pn;
    		}
    
    		public ProcessNode getNext() {
    			return next;
    		}
    
    	}
    
    	class Process {
    		private long runTime;
    		private String name;
    
    		public void setName(String name) {
    			this.name = name;
    		}
    
    		public String getName() {
    			return name;
    		}
    
    		public void setRunTime(long runTime) {
    			this.runTime = runTime;
    		}
    
    		public long getRunTime() {
    			return runTime;
    		}
    	}
    
    	public void processing(ProcessQueue queue) {
    		
    		System.out.print("各个作业需要运行的时间为:");
    		ProcessNode temp0 = queue.first;
    		for (int i = 0; i < queue.size; i++) {
    			System.out.print(temp0.getProcess().getRunTime() + "ms, ");
    			temp0 = temp0.getNext();
    		}System.out.println("\n--------开始执行程序!-----------");
    		while (queue.size != 0) {
    			ProcessNode temp = queue.first;
    			if (temp.getProcess().runTime <= cpuTime) {// 如果<=时间片轮转时间,则占用一个时间片,执行后想下一个结点执行
    				System.out.println(temp.getProcess().getName()
    						+ "进程执行结束,转向下一个作业");
    				queue.delete();
    			} else {// 占用多个时间片,运行时间-时间片后移动到队列尾部
    				long remainTime = temp.getProcess().getRunTime() - cpuTime;
    				System.out.println(temp.getProcess().getName()
    						+ "运行3000ms后中断执行,移动到执行队列后端,剩余运行时间为:" + remainTime
    						+ "ms");
    				temp.getProcess().setRunTime(remainTime);
    				queue.insert(temp);
    				queue.delete();
    			}
    
    		}
    		System.out.println("已没有需要执行的作业\n--------执行程序结束!-----------!");
    
    	}
    
    	public void test() {
    		ProcessQueue queue = new ProcessQueue();
    		int processNum = 5;
    		long[] runTimes = { 7000, 2000, 5000, 10000, 1600 };
    		ProcessNode[] processNodes = new ProcessNode[processNum];
    		for (int i = 0; i < processNum; i++) {
    			processNodes[i] = new ProcessNode();
    			processNodes[i].setProcess(new Process());
    		}
    		for (int i = 0; i < processNodes.length; i++) {
    			processNodes[i].getProcess().setName("作业" + i);
    			processNodes[i].getProcess().setRunTime(runTimes[i]);
    			queue.insert(processNodes[i]);
    		}
    		processing(queue);
    
    	}
    
    	public static void main(String[] args) {
    		new Processor().test();
    	}
    }
    


    五 实验结果:

    各个作业需要运行的时间为:7000ms,2000ms, 5000ms, 10000ms, 1600ms,

    --------开始执行程序!-----------

    作业0运行3000ms后中断执行,移动到执行队列后端,剩余运行时间为:4000ms

    作业1进程执行结束,转向下一个作业

    作业2运行3000ms后中断执行,移动到执行队列后端,剩余运行时间为:2000ms

    作业3运行3000ms后中断执行,移动到执行队列后端,剩余运行时间为:7000ms

    作业4进程执行结束,转向下一个作业

    作业0运行3000ms后中断执行,移动到执行队列后端,剩余运行时间为:1000ms

    作业2进程执行结束,转向下一个作业

    作业3运行3000ms后中断执行,移动到执行队列后端,剩余运行时间为:4000ms

    作业0进程执行结束,转向下一个作业

    作业3运行3000ms后中断执行,移动到执行队列后端,剩余运行时间为:1000ms

    作业3进程执行结束,转向下一个作业

    已没有需要执行的作业

    --------执行程序结束!-----------!

     

    六 实验体会:

    通过本次实验,了解了几种处理机调度算法的基本思想和特点,理解并发与并行的区别,并真实实现了时间片处理算法

     

     

     

    展开全文
  • 1. 处理机调度概念 ...处理机调度就是从就绪队列中挑选下一个占用CPU运行的进程(单处理),如果是处理的话,就还包含从个可以用的CPU中挑选就绪进程可使用的CPU资源。 调度程序是指在内核当中,用...

    1. 处理机调度概念

    处理机调度是操作系统当中用来管理处理机执行能力的这一部分资源的功能。

    1. CPU资源的时分复用
      之前进程切换实际上就是对CPU资源的当前占用者的一种切换,通过这种切换来实现CPU资源的时分复用。

      处理机调度就是从就绪队列中挑选下一个占用CPU运行的进程(单处理机),如果是多处理机的话,就还包含从多个可以用的CPU中挑选就绪进程可使用的CPU资源。
      调度程序是指在内核当中,用来挑选就绪进程的函数。 这里面就包含两个问题,一是调度策略(依据什么原则挑选进程/线程),二是调度时机

    2. 调度时机
      ==1==


    2. 调度准则

    1. 调度策略
      ==2==

    2. 处理机资源的使用模式
      进程通常是在CPU计算和I/O操作间交替运行
      ==3==

    3. 比较调度算法好坏的准则

      CPU使用率:CPU处于忙状态的时间百分比
      吞吐量:单位时间内完成的进程数量(这前两个都是基于系统效率来讲,后面的是从用户的角度)
      周转时间:进程从初始化到结束(包括等待)的总时间
      等待时间:进程在就绪队列中的总时间
      响应时间:从提交请求到产生响应所花费的时间(对于交互性应用)

      ==7==


    1. 吞吐量与相应时间的关系
      ==4==
    2. 处理机调度策略的目标
      1. 响应时间目标(响应时间是操作系统的计算延迟)
        ==5==
      2. 吞吐量目标(吞吐量是操作系统的计算带宽)
        ==6==
      3. 公平性目标
        公平的定义:保证每个进程占用相同的CPU时间或者保证每个进程的等待时间相同。公平通常会增加平均响应时间。

    3. 调度算法

    前三种为关于就绪队列排序的算法,主要是根据先后达到顺序、执行时间、等待时间来排序。
    ==8==

    1. 先来先服务算法(FCFS)

    ==9==
    ==10==
    在上图中,进程进入等待或者结束状态就意味着进程主动让出CPU,周转时间指的是进程进程从初始化到结束(包括等待)的总时间。

    2. 短进程优先算法(SPN)

    由于先来先服务算法周转时间抖动的问题,将进程的执行时间也考虑到算法里。短进程优先算法的策略就是选择就绪队列中执行时间最短进程占用CPU进入运行状态。这种算法具有最优平均周转时间
    ==11==

    1. 缺点
      ==12==
    2. 改进:短剩余时间优先算法(SRT):如果A进程的剩余执行时间短于当前正在执行的进程的剩余时间,则允许CPU资源被A进程抢占。

    3. 最高响应比优先算法(HRRN)

    在短进程优先算法中,会因为长进程等的时间而出现而出现饥饿问题。就出现了这种算法

    在这里插入图片描述


    4. 时间片轮转算法(RR)

    在该算法中,首先约定一个进程调度的基本时间单位:时间片,它是处理机进行资源分配的基本单位。其基本思路就是按照各个进程按照时间片轮流的占用CPU资源。

    1. 工作原理
      ==14==
    2. 示例
      ==15==
    3. 时间片的长度选择问题
      ==16==

    在前面的算法中,每个进程占用CPU多长时间定下来了,排队的先后顺序也定下来了。但是这仍然无法满足应用程序的所有要求。所以为了综合前面的算法,就出现了下面的几种算法。

    5. 多级队列调度算法(MQ)

    基本思路

    1. 就绪队列被划分为多个独立的子队列,比如说前台需要交互,那么可以用时间轮转算法(时间片设置短些),后台主要是批处理,就可以用先来先服务。
    2. 各个队列拥有自己的调度策略
    3. 队列间的调度采用下图的策略

    ==17==

    6. 多级反馈队列算法(MLFQ)

    在多级队列调度算法中,各个队列之间是没有交互的,也就是进程不能在队列间移动,这就出现了该算法。注意,下图中的高优先级对应的是第1级;
    ==18==
    算法特征: CPU密集型进程的优先级会下降很快(这样也就相当于执行时间越长的进程,切换的频率就会越低,开销越小)。I/O密集型的进程会停留在高优先级(因为每次算的时间都很短,时间片没用完)

    7. 公平共享算法(FFS)

    ==19==
    ==20==


    4. 实时调度+多处理器调度

    实时调度是对时间有要求的调度算法,多处理器调度是指在有多个处理器的系统里的调度算法

    1. 实时调度

    1. 实时操作系统
      时间约束的可预测性就是说在什么情况下,时间约束是可以达到的。
      ==21==

    2. 实时任务以及周期实时任务
      ==22==
      ==23==
      ==24==

    3. 可调度性
      在下图的示例中,系统在执行这三个周期实时任务时是可调度的么?
      ==25==

    4. 实时调度的两种算法
      ==26==


    2. 优先级反置

    注意:在Unix和Linux系统中,优先级越高,值越小。在Windows中,优先级越高,值越大。这里采用第2种。
    基于优先级的可抢占调度算法会出现优先级反置。

    1. T1优先级为40,它正在运行状态中,占用资源L1
    2. 然后,另一个进程T2(优先级为50)进入运行状态,在T2的运行过程中,需要申请T1已占用的资源L1,此时,由于T1已经占用了资源L1,所以T2就处于等待状态。
    3. 假设这时T3抢占CPU进入运行状态,而T1被迫停止了(且资源也没有释放),那么T2就会一直等待T1的资源,就产生了优先反置现象。
      ==29==
    1. 优先级继承
      下图中,在时刻t3,T3进入了阻塞。在时刻t4,占用资源的T3继承了申请资源T1的优先级,T3就会继续执行,释放资源后,T3的优先级就会变为原来的。
      ==30==
    2. 天花板协议
      ==31==

    3. 多处理器调度

    ==27==
    ==28==

    展开全文
  • 贪心算法多机调度问题

        n个作业组成的作业集,可由m台相同机器加工处理。要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。作业不能拆分成更小的子作业;每个作业均可在任何一台机器上加工处理。

        这个问题是NP完全问题,还没有有效的解法(求最优解),但是可以用贪心选择策略设计出较好的近似算法(求次优解)。当n<=m时,只要将作业时间区间分配给作业即可;当n>m时,首先将n个作业从大到小排序,然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中,选择需要处理时间最长的,然后依次选择处理时间次长的,直到所有的作业全部处理完毕,或者机器不能再处理其他作业为止。如果我们每次是将需要处理时间最短的作业分配给空闲的机器,那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况,这样势必效率较低。在下面的代码中没有讨论n和m的大小关系,把这两种情况合二为一了。

        具体实现代码如下所示:

    /**  

    *@Title: MultiMachineSchedule.java

    *@Package greedyalgorithm

    *@Description: TODO

    *@author peidong 

    *@date 2017-5-17 上午9:42:01

    *@version V1.0  

    */

    packagegreedyalgorithm;

     

    importjava.util.ArrayList;

    importjava.util.Collections;

    importjava.util.LinkedList;

    importjava.util.List;

     

    /**

     * @ClassName: MultiMachineSchedule

     * @Description: 多机调度问题

     * @date 2017-5-17 上午9:42:01

     * 

     */

    publicclass MultiMachineSchedule {

          

           /**

            *

           * @ClassName: TaskNode

           * @Description: 任务结点

           * @date 2017-5-17 上午9:58:10

           *

            */

           public static class TaskNode implementsComparable{

                  int id; //作业标号

                  int time;  //作业时间

                 

                  /**

                   *

                  * <p>Title: </p>

                  * <p>Description:构造函数 </p>

                  * @param id

                  * @param time

                   */

                  public TaskNode(int id, int time){

                         this.id = id;

                         this.time = time;

                  }

     

                  /* 

                  * <p>Title:compareTo</p>

                  * <p>Description: 按时间长短从大到小排列作业</p>

                  * @param o

                  * @return

                  * @seejava.lang.Comparable#compareTo(java.lang.Object)

                  */

                  public int compareTo(Object o) {

                         // TODO Auto-generatedmethod stub

                         int times =((TaskNode)o).time;

                         if(time > times)

                                return -1;

                         if(time == times)

                                return 0;

                         return 1;

                  }

           }

          

           /**

            *

           * @ClassName: MachineNode

           * @Description: 机器结点

           * @date 2017-5-17 上午10:02:30

           *

            */

           public static class MachineNodeimplements Comparable{

                  int id;//机器标号

                  int avail; //机器空闲时间

                 

                  /**

                   *

                  * <p>Title: </p>

                  * <p>Description:构造函数 </p>

                  * @param id

                  * @param avail

                   */

                  public MachineNode(int id, intavail){

                         this.id = id;

                         this.avail = avail;

                  }

                 

          

                  /* 

                  * <p>Title:compareTo</p>

                  * <p>Description:升序排序,LinkedList的first为最小的 </p>

                  * @param o

                  * @return

                  * @seejava.lang.Comparable#compareTo(java.lang.Object)

                  */

                  public int compareTo(Object o) {

                         // TODO Auto-generatedmethod stub

                         int xs =((MachineNode)o).avail;

                         if(avail < xs)

                                return -1;

                         if(avail == xs)

                                return 0;

                         return 1;

                  }

           }

     

           public static int greedy(int[] a, int m){

                  int n = a.length - 1; a的下标从1开始,所以n(作业的数目)=a.length-1

                  int sum = 0;

                 

                  //如果作业数量小于机器数量

                  if(n <= m){

                         for(int i = 0; i < n;i++){

                                sum+= a[i+1];

                                System.out.println("为每个作业分别分配一台机器");

                                return sum;

                         }

                  }

                 

                  List<TaskNode> d = newArrayList<TaskNode>();  //保存所有的作业

                 

                  for(int i = 0; i < n; i++){//将所有的作业存入List中,保存id和时间

                         TaskNode tn = newTaskNode(i+1,  a[i+1]);

                         d.add(tn); //入队

                  }

                 

                  Collections.sort(d); //对作业进行排序

                  LinkedList<MachineNode> h =new LinkedList<MachineNode>(); //h保存所有的机器

                  for(int i = 1; i < m; i++){ //将所有的机器存入链表中

                         MachineNode mn = newMachineNode(i,0); //初始化时,每台机器的空闲时间为0

                         h.add(mn); //入队

                  }

                 

                  int len = h.size();

                 

                  for(int i = 0; i < n; i++){

                         Collections.sort(h);  //对机器进行排序

                         MachineNode temp =h.peek();

                         System.out.println("将机器"+temp.id+"从"+temp.avail+"到"+(temp.avail+d.get(i).time)+"的时间段分配给作业"+d.get(i).id); 

                         temp.avail+=d.get(i).time;

                         sum = temp.avail;

                  }

                  return sum;

           }

           /**

            *@Title: main

            *@Description: TODO

            *@param args   

            *@return void   

            *@throws

            */

           public static void main(String[] args) {

                  // TODO Auto-generated method stub

                  int[] a={0,2,14,4,16,6,5,3};

                  int m=5;

                  int sum=greedy(a,m); 

                  System.out.println("总时间为:"+sum); 

           }

     

    }


        

    展开全文
  • 个人资料整理 仅限学习使用 实验七磁盘调度算法 目 录 一实验目的 加深对磁盘的工作原理和调度效率的理解掌握各种磁盘调度算法模拟实现一种磁盘调度算法 等 b5E2RGbCAP 二实验属性 该实验为设计性实验 个人资料整理 ...
  • 调度算法

    千次阅读 2019-09-04 21:20:30
    1、常见的批处理作业调度算法 (1) 先来先服务调度算法(FCFS,First Come First Service) (2) 短作业优先调度算法(SJF,Shortest Job First) (3) 最短剩余时间优先算法(SRT,Shortest Remaining Time) (4) 最高...
  • 一 ,先来先服务的调度算法 1.1 优缺点 二,最短作业优先算法SJF 2.1 SJF算法的优缺点: 2.2 SJF调度算法的问题: 三,高优先级调度算法 3.1 优先级调度的含义 3.2 调度算法的两种方式 3.3 优先级的类型 ...
  • OS处理机调度算法----理论篇

    千次阅读 2020-01-23 22:49:24
    处理管理的功能主要包含:进程控制、进程同步、进程通信、调度。下面我们一个个的来分析其功能的具体含义。 进程控制是处理管理中最基本的功能,主要包含为调入内存中的作业创建进程、终止已完成的进程、将因...
  • 针对嵌入式应用领域对操作系统在重构、扩展、移植、交互、安全、高效等方面...实验结果表明,基于Forth虚拟机架构的任务调度算法发挥了Forth系统所固有的特性,针对特定应用,提高了效率,适合资源有限的嵌入式环境。
  • 磁盘调度算法

    万次阅读 多人点赞 2016-05-24 15:12:42
    磁盘调度算法
  • 多机调度问题(贪心算法)

    千次阅读 2020-12-13 16:55:03
    m时,首先将n个作业从大到小排序,然后依此顺序将作业分配给空闲 的处理。也就是说从剩下的作业中,选择需要处理时间最长的,然后依次选择处理时间次长的,直到所有的作业全部处 理完毕,或者机器不能再处理其他...
  • 贪心算法多机调度问题

    万次阅读 2018-07-07 15:49:50
    问题描述: 设有n个独立的作业,由m台相同的机器进行加工处理。作业i所需的处理时间为t[i]... 这个问题是NP完全问题,到目前为止还没有有效的解法(求最优解),但是可以用贪心选择策略设计出较好的近似算法(求次优...
  • 为提高异构处理器任务调度的执行效率, 充分发挥处理器并行性能, 提出一种基于粒子群优化的异构处理器任务调度算法——FPSOTTS算法。该算法以求得任务最短完成时间为目标, 首先通过建立新的编码方式和粒子更新...
  • 常用调度算法总结

    千次阅读 2018-06-08 15:18:27
    )[+]先来先服务队列最短优先优先队列高优先权优先调度算法优先权调度算法的类型高响应比优先调度算法基于时间片的轮转调度算法时间片轮转法多级反馈队列调度算法电梯调度算法调度算法是指:根据系统的资源分配策略所...
  • 论文研究-基于JIT的多目标并行多机调度问题的混合遗传算法.pdf, 针对一类极小化 makespan和延迟区间的并行多机零件排序问题 ,设计了一个混合遗传算法 .该算法的特点是...
  • 进程的调度算法

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

    2016-12-25 12:19:25
    c语言实现时间片轮转,高响应比优先,短作业优先调度算法并比较他们的周转时间及效率
  • 在已有的WMN负载均衡算法基础上,提出一种新的基于网关协作机制的WMN负载均衡调度算法。该算法以源节点到网关节点的跳数信息和网络负载信息相结合作为网关的选择和切换标准,通过个网关的协作机制,结合高效的网关...
  • 为了实现任务执行效率与执行代价的同步优化,提出了一种云计算环境中的DAG任务目标调度优化算法算法目标最优化问题以满足Pareto最优的均衡最优解集合的形式进行建模,以启发式方式对模型进行求解。为了衡量...
  • NR调度算法

    2020-12-20 22:54:42
    NR调度算法依据下面三类: 优先级计算 调度器根据调度输入的信息,确定承载的调度优先级和选定调度的用户,保证调度公平性的同时,最大化系统吞吐量。 MCS(Modulation and Coding Scheme)选择 调度器根据调度输入...
  • 电梯调度算法

    2018-08-16 16:43:25
    传统电梯调度算法 1.1 先来先服务算法(FCFS) 先来先服务(FCFS-First Come First Serve)算法,是一种随即服务算法,它不仅仅没有对寻找楼层进行优化,也没有实时性的特征,它是一种最简单的电梯调度算法。 它...
  • 在DQ 算法的基础上,采用进一步细化QoS 参数和划分任务权值的方法,设计了属性QoS 约束的调度算法(multi-QoS constraints scheduling algorithm,MQCSA)。该算法通过选取任务的完成期限和网络带宽属性以及完成...
  • 多机调度问题是个NP完全问题,到目前为止没有有效的算法(求得最优解的有效的算法),但是利用贪心算法可以近似求出最优解。 采用最长处理时间作业优先的贪心选择策略,可以设计出较好的解。 在n<m时,我们大可以...
  • OS进程调度及典型调度算法

    千次阅读 2017-05-03 21:11:07
    确定调度算法,决定将CPU分配给哪个进程多少时间 分配处理给进程,进行CPU现场的保护和移交 调度的层次一个作业从提交开始直到完成,往往要经历以下三级调度,如图所示。 作业调度。又称高级调度,.其主要任务是按...
  • 任务调度算法汇总

    万次阅读 2016-10-05 13:54:54
    任务调度算法汇总
  • CPU 调度算法

    千次阅读 2019-03-24 22:19:47
    先来先服务调度(First Come First Serve) 效率不高,只考虑等候时间,而没考虑作业的长短,不利于短作业情况。 ...响应比高者优先调度算法 兼顾响应时间和等待时间,计算作业的响应时间和运行...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 103,482
精华内容 41,392
关键字:

多机调度算法效率