《操作系统》第5章 作业调度

操作系统的作业调度作业(job)是操作系统中⼀个常见的概念，所谓作业是指⽤户在⼀次计算过程或者事务处理过程中，要求计算机系统所作⼯作的集合。

所谓作业调度是指按照某种原则，从后备作业队列中选取作业进⼊内存，并为作业做好运⾏前的准备⼯作以及作业完成后的善后处理⼯作。

设计作业调度算法时应达到如下⽬标：• (1) 某段时间内尽可能运⾏更多的作业，应该优先考虑短作业。

• (2) 使处理机保持繁忙，应该优先考虑计算量⼤的作业，即计算型作业。

• (3) 使I/O设备保持繁忙，应该优先考虑I/O繁忙的作业，即I/O型作业。

• (4) 对所有的作业尽可能公平合理的。

这就要求对每个作业尽可能公平对待，不⽆故地或⽆限期地拖延⼀个作业的执⾏。

作业调度离不开具体调度算法，常⽤的作业调度算法有五种，下⾯我们作简单的介绍，并以单道批处理系统为例来具体分析每种算法的优劣。

先来先服务调度算法先来先服务调度算法(first come first service,FCFS)按作业到达系统的先后次序进⾏调度。

该算法优先考虑在系统中等待时间最长的作业，⽽不考虑作业运⾏时间的长短。

例如，有4个作业组成的⼀个作业流，如表2-1所⽰，在给出了作业的提交时间、运⾏时间后，经计算给出了作业的开始时间、完成时间、周转时间和带权周转时间。

由于单道批处理系统处理作业是⼀个接着⼀个的进⾏，所以第⼀个作业的结束时间就是第⼆个作业的开始时间，第⼆个作业的结束时间就是第三个作业的开始时间，等等。

所以，作业运⾏的次序为：1，2，3，4。

此作业流的平均周转时间为W ＝(1.0+3.0+6.0+3.75)/4=3.4375h注：通过以上分析，显然，这种算法容易实现，但效率很低。

短作业优先调度算法短作业优先调度算法(shortest job first,SJF)总是从作业的后备队列中挑选运⾏时间最短的作业，作为下—个调度运⾏的对象。

仍然采⽤上⾯的4个作业组成的⼀个作业流，计算其调度性能，如表2-2所⽰，经计算给出了作业的开始时间、完成时间、周转时间和带权周转时间。

操作系统——作业调度实验⼆作业调度模拟程序⼀、⽬的和要求 1. 实验⽬的 （1）加深对作业调度算法的理解； （2）进⾏程序设计的训练。

2．实验要求 ⽤⾼级语⾔编写⼀个或多个作业调度的模拟程序。

单道批处理系统的作业调度程序。

作业⼀投⼊运⾏，它就占有计算机的⼀切资源直到作业完成为⽌，因此调度作业时不必考虑它所需要的资源是否得到满⾜，它所运⾏的时间等因素。

作业调度算法： 1) 采⽤先来先服务（FCFS）调度算法，即按作业到达的先后次序进⾏调度。

总是⾸先调度在系统中等待时间最长的作业。

2) 短作业优先 (SJF) 调度算法，优先调度要求运⾏时间最短的作业。

3) 响应⽐⾼者优先(HRRN)调度算法，为每个作业设置⼀个优先权(响应⽐)，调度之前先计算各作业的优先权，优先数⾼者优先调度。

RP (响应⽐)＝作业周转时间 / 作业运⾏时间=1+作业等待时间/作业运⾏时间每个作业由⼀个作业控制块JCB表⽰，JCB可以包含以下信息：作业名、提交（到达）时间、所需的运⾏时间、所需的资源、作业状态、链指针等等。

作业的状态可以是等待W（Wait）、运⾏R（Run）和完成F（Finish）三种之⼀。

每个作业的最初状态都是等待W。

⼀、模拟数据的⽣成 1．允许⽤户指定作业的个数（2-24），默认值为5。

2. 允许⽤户选择输⼊每个作业的到达时间和所需运⾏时间。

3.（**）从⽂件中读⼊以上数据。

4.（**）也允许⽤户选择通过伪随机数指定每个作业的到达时间（0-30）和所需运⾏时间（1-8）。

⼆、模拟程序的功能 1．按照模拟数据的到达时间和所需运⾏时间，执⾏FCFS, SJF和HRRN调度算法，程序计算各作业的开始执⾏时间，各作业的完成时间，周转时间和带权周转时间（周转系数）。

2. 动态演⽰每调度⼀次，更新现在系统时刻，处于运⾏状态和等待各作业的相应信息（作业名、到达时间、所需的运⾏时间等）对于HRRN算法，能在每次调度时显⽰各作业的响应⽐R情况。

操作系统-第五章-进程调度⼀、CPU调度概述1.长程调度⼜称作业调度或⾼级调度处于新建状态的进程⼀般⾸先被放到外存的进程池中，当内存进程的数量没有达到最多进程数时，操作系统的调度程序才从新建状态选择⼀个进⼊内存并转换为就绪状态“新建”状态转换到“就绪”状态由调度程序选择控制多道程序的“道/度”2.短程调度⼜称为CPU调度或低级调度在就绪队列中可能存在不⽌⼀个进程，当CPU空闲时，操作系统就需要从就绪队列中挑选⼀个进程让它运⾏3.长程调度与短程调度的⽐较4.中程调度⼜称为交换从本质上讲，中程调度不属于进程管理的内容，⽽应该属于内存管理⼀个进程在内存和外存间的换进换出，最⼤的⽬的是节省内存当⼀个进程在内存中长期不运⾏时，会造成内存浪费，为此，操作系统把这些进程从内存换道外存，从⽽腾出内存空间供运⾏进程使⽤当⼀个在外存的进程接下来需要运⾏时，操作系统则执⾏还如操作，把这个进程从外存换⼊内存5.进程调度队列为了⽅便进⾏CPU调度，操作系统需要对不同状态的进程进⾏组织和管理。

为此操作系统为某些特定的状态设⽴了⼀个或多个进程队列，⽤于管理这些进程作业队列：在系统中的所有进程的集合就绪队列：在主存中的，就绪并等待执⾏的所有进程的集合,不必是先进先出队列，队列中的记录通常是进程控制块(PCB)设备队列：等待某⼀I/O设备的进程队列进程的执⾏过程实际上就是进程在各种队列之间的迁移6.CPU调度过程调度程序根据某种策略选择内存中的⼀个就绪进程⼀个CPU同时只能运⾏⼀个进程做选择分派程序负责把CPU的控制权转交CPU调度程序切换上下⽂切换到⽤户态跳转到⽤户程序的适当位置并重新运⾏之分派延迟：分派程序终⽌⼀个进程的运⾏并启动另⼀个进程运⾏所花的时间7.调度⽅式⾮抢占式调度⼀旦把CPU分配给某个进程后，系统不可以抢占已分配的CPU并分配给其他进程只有进程⾃愿释放CPU，才可以把CPU分配给其他进程优点：容易实现，调度开销⼩，适合批处理系统缺点：响应时间长，不合适交互系统抢占式调度调度程序可以根据某种原则暂停某个正在执⾏的进程，将已分配给它的CPU重新分配给另⼀个进程当多个进程共享数据时，抢占调度可能导致竞争情况抢占也影响操作系统的内核设计可防⽌单⼀进程长时间独占CPU系统开销⼤受中断影响的代码应加以保护，从⽽避免同时使⽤，为了这些代码段不被多个进程同时访问，在进⼊时禁⽌中断⽽退出时启⽤中断抢占式与⾮抢占式的区分运⾏进程是否是⾃愿放弃CPU8.CPU调度时机CPU调度可能发⽣在当⼀个进程从运⾏转到等待(⾮抢占式)从运⾏转到就绪(抢占式)从等待转到就绪(抢占式)终⽌运⾏(⾮抢占式)⼆、调度准则CPU利⽤率：固定时间内CPU运⾏时间的⽐例吞吐量：单位时间内运⾏完的进程数周转时间：进程从提交到运⾏结束的全部时间等待时间：进程等待调度(不在运⾏)的时间⽚总和响应时间：从进程提出请求到⾸次被响应(⽽不是输出结果)的时间段(在分时系统环境下)，也就是第⼀段的等待时间周转时间=等待时间+运⾏时间带权周转时间:周转时间/运⾏时间三、调度算法1.先来先服务调度算法(FCFS)调度策略：按照进程请求CPU的先后顺序来使⽤CPU调度依据：进⼊就绪队列的时间调度⽅法：先进⼊就绪队列的进程被优先选中运⾏使⽤FIFO队列实现特点：实现简单，可使⽤FIFO队列实现⾮抢占式调度公平，每个进程都有被调度的机会适⽤于长程调度，后台批处理系统的短程调度对长CPU脉冲的进程有利，对短CPU脉冲的进程不利护航效果：当⼀个长进程后⾯的多个短进程，让长进程先执⾏，会让后⾯的短进程等待较长时间，从⽽导致CPU和设备利⽤率降低例：2.短作业优先调度算法(SJF)调度策略：关联到每个进程下次运⾏的CPU脉冲长度，调度最短的进程调度依据：每个进程下次运⾏的CPU脉冲长度调度⽅法：调度最短的进程运⾏两种模式：⾮抢占式调度：⼀旦进程拥有CPU，它可在该CPU脉冲结束后让出CPU抢占式调度：有⽐当前进程剩余时间更短的进程到达时，新来的进程抢占当前运⾏进程的CPU，也称为最短剩余时间优先调度SJF最优：对⼀组的进程⽽⾔，它给出了最短的平均等待时间SJF算法困难：如何知道下⼀个CPU区间的长度SJF通常⽤于长程调度指数估算法：通过先前的CPU区间长度及其指数平均进⾏预测饥饿：长进程可能长时间等待，知道进程会运⾏但不知道什么时候运⾏死锁：进程长时间等待，不会运⾏例：3.优先级调度算法⽬前主流的操作系统调度算法调度依据：优先级就绪队列中的排列⽅式：优先级⾼的在前，优先级低的在后调度⽅法：调度优先级最⾼进程运⾏优先数：表⽰优先级的整数可以参考不同的因素来设置(时间极限，内存要求，进程的重要性)优先数可⽤某⼀范围的整数来表⽰静态优先级：进程创建时确定，在运⾏期间不变简单易⾏，系统开销⼩不够精确，可能会出现饥饿问题动态优先级：进程创建时的优先级随进程推进或等待时间增加⽽改变调度模式：抢占式调度⾮抢占式调度特点：实现简单，考虑了进程的紧迫程度策略灵活，可模拟其他算法存在问题：饥饿(低优先级的进程可能永远得不到运⾏)解决问题：视进程等待时间的延长提⾼其优先级例：4.时间⽚轮转(RR)为分时系统设计算法原理：把⼀段时间分割成若⼲个⼩碎⽚，每个需要运⾏的进程获得⼀个碎⽚运⾏，即在这段时间内，每个进程都得到运⾏时间⽚：较⼩单位的CPU时间，通常为10-100毫秒RR算法的性能很⼤程度上取决于时间⽚的⼤⼩时间⽚⼤->FCFS时间⽚⼩->系统开销⼤⼀般准则：时间⽚/10>进程上下⽂切换时间周转时间也依赖时间⽚的⼤⼩调度依据：进⼊就绪队列的时间调度⽅法：每个进程运⾏时间长度为⼀个时间⽚，时间⽚⽤完后，该进程被抢占并插⼊就绪队列末尾假定就绪队列中有n个进程、时间⽚q则每个进程每次得到不超过q单位的成块CPU时间没有⼀个进程的等待时间会超过(n-1)q在不超过nq时间内，n个进程都运⾏⼀次例：5.多级队列调度(MLQ)以上算法存在局限性，不能适应各种不同类型的进程SJF算法有利于短进程，⽽不利于长进程RR算法系统开销⼤优先级算法存在饥饿问题等所有进程采⽤同⼀策略，不合理不同类型的进程需要不同策略交互进程需要较短的响应时间批处理进程需要较短的等待时间通常，交互进程较批处理进程的优先级⾼多级队列调度允许系统中存在多个就绪队列，每个就绪队列有⾃⼰的调度算法根据进程属性，如内存⼤⼩、进程优先级、进程类型等，⼀个进程永远分到⼀个队列，每个队列有⾃⼰的调度算法队列之间应有调度通常采⽤固定优先级抢占调度，可能产⽣饥饿另⼀种⽅法是在队列之间划分时间⽚，每个队列都有⼀定⽐例的CPU时间，可⽤于调度队列内的进程关键：需要确定就绪队列的数量需要确定新进程进⼊那个队列需要确定每⼀个队列的调度算法例：就绪队列：前台(交互式)后台(批处理)每个队列有⾃⼰的调度算法前台：RR后台：FCFS队列间的调度⽅法固定优先级调度，即前台运⾏完后再运⾏后台。

操作系统：作业调度和进程调度的理解操作系统：作业调度和进程调度的理解含义：作业调度：是指作业从外存调⼊到内存的过程进程调度：是指进程从内存到分配cpu执⾏的过程理解：当我们打开两个程序，不妨设为程序A和程序B，⾸先这两个程序都是在外存（硬盘）上存储的，想要打开并运⾏这两个程序就必须加载到内存上，但这两个程序加载到内存上的顺序是什么呢？是先加载A呢还是先加载B呢？这个时候就涉及到作业调度了，作业调度第⼀种就是先来先服务（FCFS），即先打开的哪个程序，就先在内存上加载哪个程序；第⼆种就是短作业优先调度，即如果程序A⽐较⼤，可能是某个⼤型游戏，但是程序B⽐较⼩，可能只是打开个图⽚，假设必须要等这个⼤型游戏打开了才能打开这个图⽚，这显然图⽚等待的时间太长了，这时就涉及到了短作业优先调度，即系统会先打开图⽚，再打开游戏；第三种就是作业优先权调度，系统为作业分配优先权，优先等级⾼的就先调⼊内存，低的则等待；第四种就是⾼响应⽐调度，假设还有⼀个程序C，⽽且程序C还要在A之前打开，但是C的优先级低于A和B，如果按照优先级调度，那么C就会等很长⼀段时间，这显然对C是不公平的，所以这时就涉及到了⾼响应⽐优先，响应⽐=1+作业等待时间/执⾏时间，即：等待的时间越长，响应⽐就越⾼，就会提前执⾏。

当通过作业调度进⼊到内存后，这些作业就变成了⼀个个进程，但是要想分得CPU进⾏执⾏，还需进程调度算法，即还需要再分配⼀个顺序，来确定到底谁先分得CPU，进程调度算法有：优先权调度、短作业优先等，即通过每个进程的优先权或者作业的长短来确定分得CPU 的执⾏顺序，顺序分好以后，就该真正的执⾏了，这时采⽤时间⽚原则，即：所有的进程都分⼀个相同的时间⽚，执⾏完时间⽚后，如果没有运⾏完，到队尾等待，不断重复，直到所有程序都执⾏完；当然，这种执⾏⽅式有缺点，就是轮换的次数太多了，费时间，所以有了反馈排队调度，这种算法是先分了好⼏个等级队列，最⾼等级的队列时间⽚最短，最低等级的时间⽚最长，假设有1、2、3、4四个队列，有程序A、B、C需要被执⾏，那么A、B、C先分别执⾏⼀个时间⽚，假如C在这⼀个时间⽚内执⾏完了，那就可以直接⾛了，⽽A和B就换到第2个队列中继续执⾏⼀个第2个队列的时间⽚，就此类推，直到全部执⾏完。

一．各作业情况如下：优先级为小值优先，求平均周转时间和带权平均周转时间?1.先来先服务2.短作业优先3.静态优先答：时刻作业3和作业4都到达，3先所以执行3，再执行4平均周转时间=[(2-0)+(7-1)+(15-2)+(18-3)]/4=9平均带权周转时间=[(2-0)/2+(7-1)/5+(15-2)/8+(18-3)/3]/40时刻只有作业1到达，所以先执行1；2时刻作业2和3都到达，2短所以先执行2；7时刻作业3和4都到达，4短所以执行4，最后执行3平均周转时间=[(2-0)+(7-1)+(18-2)+(10-3)]/4=7.75平均带权周转时间=[(2-0)/2+(7-1)/5+(18-2)/8+(10-3)/3]/40时刻只有作业1到达，所以先执行1；2时刻作业2和3都到达，3优先值小所以先执行3；10时刻作业2和4都到达，4优先值小所以执行4，最后执行2平均周转时间=[(2-0)+(18-1)+(10-2)+(13-3)]/4=9.25平均带权周转时间=[(2-0)/2+(18-1)/5+(10-2)/8+(13-3)/3]/4二．各进程情况如下：求平均周转时间和带权平均周转时间?1.最高响应比优先2.时间片轮转（设时间片长为1）答：0时刻只有进程1到达，所以先执行1；3时刻只有进程2到达，所以执行2；9时刻进程3、4、5都到达, 进程3此时响应比是1+(9-4)/4=2.25, 进程4此时响应比是1+(9-6)/5=1.6, 进程5此时响应比是1+(9-8)/2=1.5，所以执行进程3；13时刻还剩进程4和5，进程4此时响应比是1+(13-6)/5=2.4, 进程5此时响应比是1+(13-8)/2=3.5，所以执行进程5，然后再进程4 平均周转时间=[(3-0)+(9-2)+(13-4)+(20-6)+(15-8)]/5=8平均带权周转时间=[(3-0)/3+(9-2)/6+(13-4)/4+(20-6)/5+(15-8)/2]/5求平均周转时间和带权平均周转时间平均周转时间=[(4-0)+(18-2)+(17-4)+(20-6)+(15-8)]/5=10.8平均带权周转时间=[(4-0)/3+(18-2)/6+(17-4)/4+(20-6)/5+(15-8)/2]/53．(6分)假设有四个作业，它们的提交时间和需要的计算时间如表2所示。

作业调度程序作业调度程序是操作系统中的一个重要组件，它负责将作业从提交状态转换为运行状态，并决定哪些作业在什么时候运行以及在哪个处理器上运行。

作业调度程序的目标是实现资源的有效利用，包括处理器、内存、磁盘等，以提高系统的整体性能。

一、作业调度程序的基本概念作业调度程序的主要任务是将作业放入等待队列，并根据一定的调度算法从等待队列中选取作业进行处理。

在操作系统中，作业是一个程序或一个程序的一个执行实例。

当用户提交一个作业时，操作系统会为该作业分配必要的资源，并将其放入等待队列中。

等待队列按照先进先出（FIFO）的原则对作业进行排序。

当一个处理器空闲时，作业调度程序会从等待队列中选取一个作业进行处理。

在选择作业时，需要考虑许多因素，如作业的优先级、作业的类型（批处理、交互式、实时等）、作业的性质（CPU密集型、I/O密集型）等。

二、常见的作业调度算法1.先来先服务（FCFS）算法：按照作业到达的顺序进行调度，优先级相同的情况下最先到达的作业将优先获得处理器。

这种算法简单易行，但无法充分利用系统资源。

2.最短作业优先（SJF）算法：优先调度预计运行时间最短的作业。

这种算法可以减少平均等待时间和平均周转时间，但可能造成短作业长时间等待。

3.优先级调度算法：为不同类型的作业分配不同的优先级，优先级高的作业将优先获得处理器。

这种算法可以实现资源的有效利用，但实现起来比较复杂。

4.轮转法（Round Robin）：按照固定的时间片将处理器分配给等待队列中的作业，时间片用完后该作业被放到队尾重新排队。

这种算法可以实现资源的平均分配，但可能导致某些作业等待时间过长。

5.多级反馈队列算法：将等待队列分为多个级别，不同级别的队列采用不同的调度算法。

这种算法可以灵活地适应不同类型和不同性质的作业，但实现起来比较复杂。

三、作业调度程序的实现作业调度程序的实现需要依赖于操作系统的内核和处理器。

在内核中，需要实现等待队列的管理、进程状态的管理以及处理器上下文的保存和恢复等功能。

操作系统实验报告作业调度操作系统实验报告：作业调度引言：操作系统是计算机系统中最核心的软件之一，它负责管理计算机的资源，为用户提供良好的使用环境。

在操作系统中，作业调度是非常重要的一部分，它决定了计算机如何合理地分配和调度各个作业的执行顺序，以提高计算机的效率和性能。

本实验报告将介绍作业调度的概念、调度算法以及实验结果。

一、作业调度的概念作业调度是指根据一定的策略和算法，将就绪队列中的作业按照一定的顺序分配给处理器，使得计算机系统能够充分利用资源，提高系统的吞吐量和响应时间。

作业调度的目标是实现公平性、高效性和平衡性。

二、作业调度的算法1. 先来先服务（FCFS）调度算法FCFS调度算法是最简单的调度算法之一，它按照作业的到达顺序进行调度，先到达的作业先执行。

这种算法的优点是简单易实现，但是可能会导致长作业等待时间过长，造成资源浪费。

2. 最短作业优先（SJF）调度算法SJF调度算法是根据作业的执行时间来进行调度，执行时间短的作业先执行。

这种算法能够最大程度地减少平均等待时间，提高系统的响应速度，但是可能会导致长作业长时间等待。

3. 优先级调度算法优先级调度算法是根据作业的优先级来进行调度，优先级高的作业先执行。

这种算法可以根据不同的需求设置不同的优先级，但是可能会导致低优先级的作业长时间等待。

4. 时间片轮转调度算法时间片轮转调度算法是将处理器的执行时间划分为多个时间片，每个作业在一个时间片内执行，时间片用完后，将处理器分配给下一个作业。

这种算法可以实现公平性，但是可能会导致长作业等待时间过长。

三、实验结果与分析在本次实验中，我们使用了不同的作业调度算法，并对其进行了性能测试。

测试结果显示，FCFS算法在平均等待时间方面表现较差，而SJF算法和优先级调度算法在平均等待时间方面表现较好。

时间片轮转调度算法能够实现公平性，但是可能会导致长作业等待时间过长。

结论：作业调度是操作系统中的重要组成部分，合理的作业调度算法能够提高计算机系统的效率和性能。

操作系统作业调度算法操作系统作业调度算法是操作系统中的一个重要概念，它决定了在多道程序环境下，各个作业的执行顺序和分配时间。

正确选择合适的调度算法可以提高系统的效率和性能，保证作业能够按时完成。

本文将介绍几种常见的作业调度算法，包括先来先服务（FCFS）、短作业优先（SJF）、最高响应比优先（HRRN）和轮转法（RR）。

先来先服务（FCFS）调度算法是最简单的一种算法，它按照作业到达的先后顺序进行调度。

当一个作业到达后，如果系统中没有其他作业在执行，则该作业立即执行；如果有其他作业在执行，则该作业会进入就绪队列等待。

FCFS算法的优点是实现简单，但是它容易导致长作业等待时间过长，影响系统的响应时间。

短作业优先（SJF）调度算法是根据作业的执行时间来进行调度的。

当一个作业到达后，系统会比较该作业的执行时间与当前正在执行的作业的执行时间，如果该作业的执行时间更短，则该作业会被优先执行。

SJF算法的优点是能够减少作业的等待时间，提高系统的响应速度，但是它需要预先知道每个作业的执行时间，对于实时系统来说并不适用。

最高响应比优先（HRRN）调度算法是根据作业的等待时间和执行时间的比值来进行调度的。

当一个作业到达后，系统会计算该作业的响应比，响应比越高，优先级越高，该作业会被优先执行。

响应比的计算公式为（等待时间+执行时间）/ 执行时间。

HRRN算法的优点是能够兼顾作业的等待时间和执行时间，提高系统的整体性能，但是它需要不断地重新计算作业的响应比，增加了调度算法的复杂度。

轮转法（RR）调度算法是将系统的处理时间分为若干个时间片，每个时间片内一个作业可以执行的时间是固定的，当一个作业到达后，系统会将其放入就绪队列的末尾，并在当前时间片内执行该作业。

当一个时间片结束后，如果作业还没有执行完，系统会将其放回就绪队列的末尾，等待下一轮的调度。

轮转法算法的优点是能够公平地分配CPU时间，避免了长作业的等待时间过长，但是它可能导致一些短作业的响应时间较长。