磁盘调度先来先服务算法

① 描述磁盘调度中涉及哪些时间

磁盘调度中分别涉及寻找时间和延迟时间。
磁盘驱动调度包括移臂调度和旋转调度，
磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：

先来先服务算法（FCFS），
最短寻道时间优先算法（SSTF），
扫描算法（SCAN），
循环扫描算法（CSCAN）
希望我的回答对你有所帮助

② 磁盘移动调度的目的是什么,算法又有哪些呢

磁盘它移动磁盘臂进行调度的主要目的是为了尽可能的减少输入输出造作中的寻找时间。磁盘调度算法有先来先服务调度算法，这个就是谁先到，谁先执行，如果有空间的话，后来的可以继续占用并调度，如果没有空间的话，必须等待。再有就是最短寻找时间调度算法。还有就是电梯调度算法和单向调度算法。这些算法要根据不同的需要加以选择。

③ 2018-06-09

一、常见的批处理作业调度算法

1.先来先服务调度算法（FCFS）:就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单，公平。其缺点是没有考虑到系统中各种资源的综合使用情况，往往使短作业的用户不满意，因为短作业等待处理的时间可能比实际运行时间长得多。

2.短作业优先调度算法(SPF): 就是优先调度并处理短作业，所谓短是指作业的运行时间短。而在作业未投入运行时，并不能知道它实际的运行时间的长短，因此需要用户在提交作业时同时提交作业运行时间的估计值。

3.最高响应比优先算法(HRN)：FCFS可能造成短作业用户不满，SPF可能使得长作业用户不满，于是提出HRN，选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。

4. 基于优先数调度算法(HPF)：每一个作业规定一个表示该作业优先级别的整数，当需要将新的作业由输入井调入内存处理时，优先选择优先数最高的作业。

5.均衡调度算法，即多级队列调度算法

基本概念：

  作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)

  作业平均周转时间(T)＝周转时间/作业个数

  作业带权周转时间（Wi）＝周转时间/运行时间

  响应比＝（等待时间＋运行时间）/运行时间

二、进程调度算法

1.先进先出算法(FIFO)：按照进程进入就绪队列的先后次序来选择。即每当进入进程调度，总是把就绪队列的队首进程投入运行。

2. 时间片轮转算法(RR)：分时系统的一种调度算法。轮转的基本思想是，将CPU的处理时间划分成一个个的时间片，就绪队列中的进程轮流运行一个时间片。当时间片结束时，就强迫进程让出CPU，该进程进入就绪队列，等待下一次调度，同时，进程调度又去选择就绪队列中的一个进程，分配给它一个时间片，以投入运行。

3. 最高优先级算法(HPF)：进程调度每次将处理机分配给具有最高优先级的就绪进程。最高优先级算法可与不同的CPU方式结合形成可抢占式最高优先级算法和不可抢占式最高优先级算法。

4. 多级队列反馈法：几种调度算法的结合形式多级队列方式。

三、空闲分区分配算法

\1. 首先适应算法：当接到内存申请时，查找分区说明表，找到第一个满足申请长度的空闲区，将其分割并分配。此算法简单，可以快速做出分配决定。

2. 最佳适应算法：当接到内存申请时，查找分区说明表，找到第一个能满足申请长度的最小空闲区，将其进行分割并分配。此算法最节约空间，因为它尽量不分割到大的空闲区，其缺点是可能会形成很多很小的空闲分区，称为“碎片”。

3. 最坏适应算法：当接到内存申请时，查找分区说明表，找到能满足申请要求的最大的空闲区。该算法的优点是避免形成碎片，而缺点是分割了大的空闲区后，在遇到较大的程序申请内存时，无法满足的可能性较大。

四、虚拟页式存储管理中的页面置换算法

1.理想页面置换算法(OPT)：这是一种理想的算法，在实际中不可能实现。该算法的思想是：发生缺页时，选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。

2.先进先出页面置换算法(FIFO)：选择最先进入内存的页面予以淘汰。

3. 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。

4.最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。

三、磁盘调度

1.先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置

2.最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题

3.扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。

4.循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。

对一个进程来说,一个重要的指标是它执行所需要的时间. 从进程提交到进程完成的时间间隔为周转时间.也就是等待进入内存的时间,在就绪队列中等待的时间,在 CPU中执行的时间和I/O操作的时间的总和.

例1.设一个系统中有5个进程，它们的到达时间和服务时间如下，A的到达时间为0，服务时间为3；B的到达时间为2，服务时间为6；C的到达时间为4，服务时间为4；D的到达时间为6，服务时间为5；E的 到达时间为8，服务时间为2，忽略1/0以及其他开销时间，若分别按先来先服务（fFCFS）进行CPU调度，其平均周转时间为？

10.2

6.4

8.6

4.5

先来先服务调度算法

进程名  到达时间 服务时间  开始执行时间  完成时间  周转时间

A              0              3                0                3                3

B              2              6                3                9                7

C              4              4                9                13              9

D              6              5                13              18              12

E              8              2                18              20              12

周转时间 = 完成时间 - 到达时间

平均周转时间 = 所有进程周转时间 / 进程数 = （3+7+9+12+12）/ 5 = 8.6

单道批处理系统中有4个作业，J1的提交时间8.0，运行时间为2.0；J2的提交时间8.6，运行时间为0.6；J3提交时间8.8，运行时间为0.2；J4的提交时间9.0，运行时间为0.5。在采用响应比高者优先调度算法时，其平均周转时间为T为（）小时？

2.5

1.8

1.975

2.675

周转时间=作业完成时间-作业提交时间

响应比=（作业等待时间+作业执行时间）/作业执行时间

当提交J1时，只有J1作业，执行J1，J1的周转时间为2，此时时间为10.

J2、J3、J4提交时，由于正在执行J1，因此等待。

当J1执行完毕（此时时间为10），J2、J3、J4的等待时间分别为：1.4,1.2,1，

其响应比分别为：1.4/0.6+1=3.33    1.2/0.2+1=7      1/0.5+1=3，因此执行J3，J3的周转时间为1.2+0.2=1.4

当J3执行完毕（此时时间为10.2），J2和J4的等待时间分别为1.6,1.2，

其响应比分别为：1.6/0.6+1=3.66      1.2/0.5+1=3.4，因此执行J2，J2的周转时间为1.6+0.6=2.2

执行J2完毕后时间为10.8，接下来执行J4，执行完后时时间为11.3，J4的周转时间为2.3

于是平均周转时间为（2+1.4+2.2+2.3）/4=1.975

如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。

例3、

现有4个同时到达的作业J1,J2,J3和J4,它们的执行时间分别是3小时,5小时,7小时,9小时系统按单道方式运行且采用短作业优先算法,则平均周转时间是()小时

12.5

24

19

6

作业到达时间执行时间开始时间完成时间周转时间

J103033

J20 5388

J30781515

J409152424

平均周转时间（3+8+15+24）/4=12.5 

有4个进程A,B,C,D,设它们依次进入就绪队列，因相差时间很短可视为同时到达。4个进程按轮转法分别运行11,7,2,和4个时间单位，设时间片为1。四个进程的平均周转时间为 （）？

15.25

16.25

16.75

17.25

17.75

18.25

A:1  4  4  3  3  2  2  2  1  1  1  共24

B:2  4  4  3  3  2  2                  共20

C:3  4                                      共7

D:4  4  3  3                              共14

字母后面的数字为等待的时间加运行时间

平均周转时间为（24+20+7+14）/4=16.25

例5、假设系统按单值方式运行且采用最短作业优先算法，有J1,J2,J3,J4共4个作业同时到达，则以下哪几种情况下的平均周转时间为10分钟?

执行时间J1:1分钟 J2:5分钟 J3:9分钟 J4:13分钟

执行时间J1:1分钟 J2:4分钟 J3:7分钟 J4:10分钟

执行时间J1:2分钟 J2:4分钟 J3:6分钟 J4:8分钟

执行时间J1:3分钟 J2:6分钟 J3:9分钟 J4:12分钟

首先，短作业优先则短时间的作业利用资源，其余的作业等待

根据平均周转时间概念，将所有作业"等待时间"加上"运行时间"除以"作业数量"即可得到平均周转时间

A： (J1执行1分钟 + J2等待1分钟 + J2执行5分钟 + J3等待6分钟 + J3执行9分钟 + J4等待15分钟 + J4执行13分钟) / 4  = 50/4 = 12.5

B：  (J1执行1分钟 + J2等待1分钟 + J2执行4分钟 + J3等待5分钟 + J3执行7分钟 + J4等待12分钟 + J4执行10分钟) / 4  = 40/4 = 10

C： (J1执行2分钟 + J2等待2分钟 + J2执行4分钟 + J3等待6分钟 + J3执行6分钟 + J4等待12分钟 + J4执行8分钟) / 4    = 40/4 = 10

D：  (J1执行3分钟 + J2等待3分钟 + J2执行6分钟 + J3等待9分钟 + J3执行9分钟 + J4等待18分钟 + J4执行12分钟) / 4  = 50/4 = 12.5

例6、假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。  表1 进程到达和需要服务时间  进程    到达时间    服务时间  A          0            3  B          2            6  C          4            4  D          6            5  E          8            2

表2 进程的完成时间和周转时间

                  进程                  A      B        C      D      E        平均

  FCFS          完成时间      3      9      13      18      20 

                周转时间            3      7        9      12      12      8.6

            带权周转时间      1.00 1.17  2.25  2.40    6.00      2.56

  SPF(非抢占)  完成时间    3      9      15      20      11 

                周转时间            3      7      11      14      3        7.6

            带权周转时间      1.00  1.17  1.75    2.80    1.50    1.84

  SPF(抢占)    完成时间    3      15      8      20      10 

                周转时间            3      13      4      14      2        7.2

            带权周转时间      1.00  2.16  1.00  2.80  1.00    1.59

例7、假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：    作业  进入系统时间    估计运行时间/分钟      1            8:00                40      2            8:20                30      3            8:30                12      4            9:00                18

      5            9:10                5

如果应用先来先服务和应用最短作业优先的作业调度算法，试将下面表格填写完整。

(1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。

    作业  进入系统时间  估计运行时间/分钟  开始时间  结束时间  周转时间/分钟

    1        8:00            40            8：00    8：40        40

    2        8:20            30            8：40    9：10        50

    3        8:30            12            9：10    9：22        52

    4        9:00            18            9：22    9：40        40

    5        9:10            5              9：40    9：45        35

作业平均周转时间T= 43.4  217

2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。    作业  进入系统时间  估计运行时间/分钟  开始时间  结束时间  周转时间/分钟    1        8:00            40              8：00    8：40          40    2        8:20            30              8：52    9：22          62    3        8:30            12              8：40    8：52          22    4        9:00            18              9：27    9：45          45    5        9:10            5              9：22    9：27          17作业平均周转时间T= 37.2  186

CPU和两台输入/输出设备(I1,I2)多道程序设计环境下,同时有三个作业J1,J2,J3进行,这三个作业

使用CPU和输入/输出设备的顺序和时间如下所示:

J1:I2(35ms);CPU(15ms);I1(35ms);CPU(15ms);I2(25ms)

J2:I1(25ms);CPU(30ms);I2(35ms)

J3:CPU(30ms);I1(25ms);CPU(15ms);I1(15ms);

假定CPU,I1,I2都能并行工作,J1的优先级最高,J2次之,J3优先级最低,优先级高的作业可以抢占优先级低的作业的CPU,但不能抢占I1,I2,作业从J3开始到完成需要多少时间?

④ 计算机操作系统习题，求解

（1）先来先服务调度算法
由于该算法就是按照磁道请求序列的先后次序依次访问磁道的，因此磁道的访问序列（服务顺序）就是：
55、58、39、18、90、160、150、38、184
当前磁头在100号磁道。故磁头移动道数为：
（100-55）+（58-55）+（58-39）+（39-18）+（90-18）+（160-90）+（160-150）+（150-38）+（184-38）=45+3+19+21+72+70+10+112+146=498
平均寻道时间：498/9=55.3
（2）本题磁头移动方向是磁道增加的方向。因此磁道的访问序列（服务顺序）就是90、58、55、39、38、18、150、160、184。当前磁头在100号磁道 ，故磁头移动道数为：（100-90）+（90-58）+（58-55）+（55-39）+（39-38）+（38-18）+（150-18）+（160-150）+（184-160）=248
平均寻道时间：248/8=27.5

⑤ 磁盘调度算法用来改善磁头的性能对不对

对的，磁盘是计算机系统中最重要的存储设备，其中含有绝大部分文件。对文件的操作直接涉及到磁盘的访问，磁盘IO的速度效率和可靠性将直接影响系统的性能。因此，好的磁盘调度算法、优越的冗余技术，都是提高磁盘系统性能的切入点。
磁盘调度算法

1.先来先服务：按照进程访问磁盘的先后顺序进行调度。

优点：公平、简单

缺点：效率低，平均寻道时间较长

2.最短寻道时间优先：要求访问磁道与当前磁头的磁道距离最近。

优点：相比于先来先服务，明显减少平均寻道长度

缺点：磁头可能在一个小的范围内一直寻到，造成远处请求不满足而饥饿

3.扫描算法：又称电梯调度算法，像电梯一样上下连续来回寻道

优点：避免了“饥饿”现象

缺点：对于刚刚经过的磁道又来了新的请求，再次访问要最多等2个磁道长度

4.循环扫描算法：磁头单向移动，其余和扫描算法一样

优点：解决了可能的错过型请求的双倍延迟

缺点：浪费一个磁头的移动次数，什么都没做

5.NStepSCAN算法：磁盘请求分成N个队列，队列间用先来先服务处理，队列内用扫描算法处理

优点：避免新请求带来的粘着问题

缺点：N值很大时，接近于扫描算法；N=1时，就是先来先服务

6.FSCAN算法：磁盘请求只分成两个队列，一个是当前请求队列，一个是未来请求队列，当前队列按照扫描算法处理，当前队列处理完就处理另一个，此时另一个为当前队列，已经处理完的是未来请求队列

优点：简化NStepSCAN算法

缺点：所有新来的请求都在下次扫描时再处理，对于紧急的高优先级的请求也要放到下次

⑥ 作业调度算法的先来先服务

先来先服务（FCFS,
First
Come
First
Serve）是最简单的调度算法，按先后顺序进行调度。
按照作业提交或进程变为就绪状态的先后次序，分派CPU；
当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。
在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。
比较有利于长作业，而不利于短作业。
有利于CPU繁忙的作业，而不利于I/O繁忙的作业。

⑦ 操作系统的主要算法都有哪些

一、进程(作业)调度算法
l 先来先服务调度算法（FCFS）：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。

l 短进程（作业）优先调度算法(SPF)：它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。

l 时间片轮转调度算法 ：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。

l 优先数调度算法 ：它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。

l 响应比高者优先调度算法：它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。

l 多级队列调度算法

基本概念：

作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)

作业平均周转时间(T)＝周转时间/作业个数

作业带权周转时间（Wi）＝周转时间/运行时间

响应比＝（等待时间＋运行时间）/运行时间

二、存储器连续分配方式中分区分配算法
n 首次适应分配算法（FF）：对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。

n 循环首次适应算法：每次分配均从上次分配的位置之后开始查找。

n 最佳适应分配算法(BF)：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。

三、页面置换算法
l 最佳置换算法（OPT) ：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。

l 先进先出置换算法（FIFO）：选择最先进入内存的页面予以淘汰。

l 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。

l 最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。

四、磁盘调度
n 先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置

n 最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题

n 扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。

n 循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。

⑧ 求磁盘调度算法scan算法的java代码

1、先来先服务算法（FCFS）First Come First Service
这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。
先来先服务 （125）86.147.91.177.94.150.102.175.130

[java] view plain print?

⑨ 若磁头的当前位置100柱面，磁头正向磁道号减小方向移动。现有一磁盘读写请求队列，柱面号依次为:

磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。为了尽快的响应进程的磁盘请求，人们设计了磁盘调度算法。主要有四种磁盘调度算法。先来先服务算法（FCFS），最短寻道时间优先算法（SSTF），扫描算法（SCAN），循环扫描算法（CSCAN）。

运用最短寻道优先算法依次选择的磁道是：90、80、125、140、160、190、30、29、25、20、10。

运用电梯调度算法依次经过的磁道是：90、80、30、29、25、20、10、125、140、160、190。

我们根据算法的寻道序列可以得出：最短寻道优先算法的经过的煮面数为310个柱面，电梯调度算法经过的柱面数为270次。

(9)磁盘调度先来先服务算法扩展阅读：

每种磁盘调度算法的优缺点

先来先服务算法的优点会根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。

最短寻道优先算法的缺点每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期地被延迟，有些请求的响应时间将不可预期。

扫描算法的优缺点此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。

循环扫描算法的优点是这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。

参考资料来源：网络-磁盘调度算法

⑩ 磁盘调度 算法

(1)FCFS(先来先服务):
143-86=57
147-86=61
147-91=56
177-91=86
177-94=97
150-94=56
150-102=48
175-102=73
175-130=45
57+61+56+86+97+56+48+73+45=579

(2)SSTF(最短寻道时间优先)：
寻道顺序：143（当前），147，150，130，102，94，91，86，175，177；
4+3+20+28+8+3+5+89+2=162

(3)SCAN：
当前方向：从143#向磁道号增加的方向
依次访问：143（当前），147，150，175，177
再从递减方向：130，102，94，91，86
4+3+25+2+47+28+8+3+5=125

(4)LOOK:(即SCAN，电梯调度算法)

(5)CSCAN:
当前方向：从143#向磁道号增加的方向
依次访问：143（当前），147，150，175，177
再从0开始增加方向：86,91,94,102,130
4+3+25+2+91+5+3+8+28=169