扫描调度算法

A. 莫系统空闲分区如下表.哪种算法可满足该作业序列请求为什么

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

B. 磁盘调度算法中的~扫描算法~还有~循环扫描算法~，需要移动到0磁道再返回码麻烦高手指点，学校发的破书写

总是按一个方向移动磁盘臂（向0反方向移动），处理完编号最高的磁道后，移动到具有读写请求的编号最低的磁道，然后继续向上移动。

这里你反过来理解就好了，就是从高到低

这里先访问168，然后是140,117，小于117的磁道已经没有请求了，此时磁盘臂应该回到288，然后向0方向移动

C. I/O与磁盘调度是什么

外部设备分类
（1）按系统和用户分：系统设备、用户设备
（2）按输入输出传送方式分（UNIX或Linux操作系统）：字符型设备、块设备
（3）按资源特点分：独享设备、共享设备、虚拟设备
（4）按设备硬件物理特性分：顺序存取设备、直接存取设备
（5）按设备使用分：物理设备、逻辑设备、伪设备
（6）按数据组织分：块设备、字符设备
（7）按数据传输率分：低速设备、中速设备、高速设备
设备管理的目标与任务
设备管理的目标：
（1）按用户需求提出的要求接入外部设备，系统按一定算法分配和管理控制，而用户不必关心设备的实际地址和控制指令；
（2）尽量提高输入输出设备的利用率，例如发挥主机与外设以及外设与外设之间的真正并行工作能力。主要利用的技术有：中断技术、DMA技术、通道技术、缓冲技术。
设备管理的任务：
（1）动态掌握并记录设备的状态
（2）分配设备和释放
（3）对输入输出缓冲区进行管理
（4）控制和实现真正的输入输出操作
（5）提供设备使用的用户接口
（6）在一些较大系统中实现虚拟设备技术
通道（channel）：计算机系统中能够独立完成输入输出操作的硬件装置，也称为“输入输出处理机”。
虽然在CPU与I/O设备之间增加了设备控制器，但CPU的负担仍很重。为此，在CPU和设备控制器之间又增设了I/O通道。其目的是使一些原来由CPU处理的I/O任务转由通道来承担，从而把CPU从繁杂的I/O任务中解脱出来。
CPU并不直接操作外围设备，他连接通道（I/O处理机），通道连接设备控制器，设备控制器连接设备。CPU只需把“I/O"设备启动，并给出相关的操作要求。然后就由通道来处理输入输出事宜，做完后报告CPU。
根据信息交换方式的不同，可把通道分成以下三种类型：
字节多路通道(Byte Multiplexor Channal)
数组选择通道(Block Selector Channal)
数组多路通道(Block Multiplexor Channal)
中断技术
中断(Interrupt)是指计算机在执行期间，系统内发生非寻常的或非预期的急需处理事件，使得CPU暂时中断当前正在执行的程序而转去执行响应的事件处理程序。待处理完毕后又返回原来中断处继续执行或调度新的程序执行的过程。中断一般可分成软件中断和硬件中断。
中断方式（interrupt）被用来控制外围设备和内存与CPU之间的数据传送。这种方式要求CPU与设备（或控制器）之间有相应的中断请求线，而且在设备控制器的控制状态寄存器的相应的中断允许位。
1．数据输入操作步骤：
l进程需要数据时，通过CPU发出“start”指令启动外围设备准备数据
l在进程发出指令启动设备后，该进程放弃处理机，等待输入完成。
l当输入完成时，I/O控制器通过中断请求线向CPU发出中断请求。
l在以后的某个时刻，进程调度程序选中提出请求并得到数据的进程，该进程从约定的内存特定单元中取出数据继续工作。
2．中断方式的缺点：
1）由于在一次数据传送过程中，发生中断次数较多。这将耗去大量CPU处理时间。
2）当设备把数据放入数据缓冲寄存器并发出中断信号之后，CPU有足够的时间在下一个（组）数据进入数据缓冲寄存器之前取走数据。如果外设的速度也非常快，则有可能造成数据缓冲寄存器的数据丢失。
DMA技术
DMA 是Direct Memory Access的缩写，其意思是“存储器直接访问”。它是指一种高速的数据传输操作，允许在外部设备和存储器之间直接读写数据，即不通过CPU，也不需要 CPU干预。整个数据传输操作在一个称为“DMA控制器”的控制下进行的。CPU除了在数据传输开始和结束时作一点处理外，在传输过程中CPU可以进行其它的工作。这样，在大部分时间里，CPU和输入输出都处在并行操作。因此，使整个计算机系统的效率大大提高。
缓冲技术
缓冲指用来暂存数据的缓冲存储器。
缓冲技术是二种不同速度的设备之间传输信息时平滑传输过程的一种常用手段。它可提高外设利用率，尽可能使外设处于忙状态。引入缓冲的主要原因，可归结为以下几点：
1. 改善CPU与I/O设备间速度不匹配的矛盾
2. 可以减少对 CPU的中断频率，放宽对中断响应时间的限制
3. 提高 CPU和 I／O设备之间的并行性
根据I/O控制方式，缓冲的实现方法有两种：一种是采用专用硬件缓冲器；另一种是在内存划出一个具有n个单元的专用缓冲区，以便存放输入/输出的数据。内存缓冲区又称软件缓冲。
根据系统设置的缓冲器的个数，可把缓冲技术分为：单缓冲、双缓冲、多缓冲和缓冲池
假脱机技术（SPOOLing）
SPOOLing，即外围设备联机并行操作，它是一种速度匹配技术、也是一种虚拟设备技术（用一种物理设备模拟另一类物理设备，使各作业在执行期间只使用虚拟的设备而不直接使用物理的独占设备。这种技术可使独占的设备变成可共享的设备，使得设备的利用率和系统效率都能得到提高）。
1．SPOOL系统的组成
SPOOLing系统主要有以下三部分组成：
（1）输入井和输出井
它们是在磁盘上开辟的两个大缓冲区。输入井是模拟脱机输入时的磁盘，用于收容I/O设备输入的数据；输出井是模拟脱机输出时的磁盘，用于收容用户程序的输出数据。
（2）输入缓冲区和输出缓冲区
在内存中要开辟两个缓冲区，其中输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井；输出缓冲区用于暂存从输出井送来的数据，以后再传送给输出设备。
（3）输入进程SPi和输出进程Spo
进程Spi模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井。当CPU需要输入数据时，直接从输入井读入内存。Spo进程模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备上。
2、实现虚拟设备的条件
硬件条件：大容量磁盘；中断装置和通道；中央处理器与通道并行工作的能力。
软件条件：要求操作系统采用多道程序设计技术。
3、虚拟设备的实现原理
对于多道程序，输入时将一批作业的信息通过输入设备预先传送到磁盘上。输出时将作业产生的结果也全部暂时存在磁盘上而不直接输出，直到一个作业得到全部结果而执行结束时再行输出。（就是用磁盘来模拟输入机和打印机的工作，把它们的工作内容先保存起来，然后一并执行）
磁盘调度
对磁盘进行驱动调度的目的：尽可能的降低多个访问者执行输入输出操作的总时间，增加单位时间内的输入输出操作次数，有利于系统效率的提高。
磁盘的驱动调度：在多道程序设计系统中，同时有多个访问者请求磁盘操作，此时系统采用一定的调度策略来决定各等待访问者的执行次序，所以系统决定等待磁盘访问者的执行次序的工作就是磁盘的“驱动调度”。
磁盘调度分为移臂调度和旋转调度。
根据访问者指定的柱面位置来决定执行次序的调度称“移臂调度”；
当移动臂定位后，如有多个访问者等待访问该柱面时，根据延迟时间来决定执行次序的调度称为“旋转调度”。
移臂调度算法包括以下四种：
1）先来先服务算法(FCFS)；
2）最短寻找时间优先调度算法(SSTF)；
3）电梯调度算法(SCAN)；
4）单向扫描调度算法(CSCAN)。

D. 高手给解释下，操作系统中的，电梯调度算法和扫描调度算法的区别到底是什么最好举例图

操作系统概念那本书上有图，电梯就是磁头一直向左然后一直向右这么来来回回。CSCAN就是磁头一直向左，然后再回到右边开始一直向左，类似于示波器的逐行扫描。

E. 关于《操作系统》中的磁盘调度算法

（1）先来先服务调度算法
由于该算法就是按照磁道请求序列的先后次序依次访问磁道的，因此磁道的访问序列（服务顺序）就是：
110、180、32、115、15、120、60、70。
当前磁头在50号磁道。故磁头移动道数为：
（110-50）+（180-110）+（180-32）+（115-32）+（115-15）+（120-15）+（120-60）+（70-60）=60+70+148+83+100+105+60+10=636
（2）单向扫描调度算法
该算法是沿磁头移动方向访问距离当前磁道最近的磁道，当到达一个顶端时立刻返回到另一个顶端继续扫描。本题磁头移动方向是磁道增加的方向，当前磁头在50号磁道。因此磁道的访问序列（服务顺序）就是：60、70、110、115、120、180、15、32。而磁头移动道数与前面（1）问差不多，也是两两相减，然后求和。在此略

F. 最短寻道时间优先算法与扫描算法有什么异同

最短进程优先算法是一种非剥夺式算法,总是选取预计作业时间最短的作业优先运行；最短剩余时间优先算法是非剥夺式的,但可以改造成剥夺式的调度算法,称抢占式最短作业优先算法.
至于二者的平均周转时间,比如有四个进程P1,P2,P3,P4,分别在0,1,2,3时刻到达,所需时间分别为7,5,3,8；那么其平均周转时间为（（15-0）+（9-1）+（5-2）+（23-15））/4=8.5；
最短进程优先的比较简单了,就不写出来了,不会的话再追问吧.

G. 常见的磁盘调度算法有哪些，有什么优缺点

1.先来先服务（FCFS）
2.最短寻道时间优先（SSTF）
3.扫描（scan）算法
4循环扫描（CSCAN）算法
5.NStep和FSCAN调度算法

H. 目前常用的磁盘调度算法有哪几种每种算法优先考虑的问题是什么

(1)先来先服务(FCFS，First-Come First-Served)
此算法根据进程请求访问磁盘的先后次序进行调度。
(2)最短寻道时间优先(SSTF ，ShortestSeekTimeFirst)
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
(3)扫描(SCAN)算法
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
(4)循环扫描(CSCAN)算法
CSCAN算法规定磁头单向移动，避免了扫描算法导致的某些进程磁盘请求的严重延迟。
(5) N-Step-SCAN和FSCAN调度算法
1) N-Step-SCAN算法。为克服前述SSTF、SCAN、CSCAN等调度算法都可能出现的磁臂停留在某处不动的情况即磁臂粘着现象，将磁盘请求队列分成若干个长度为N的子队列，按先来先服务算法依次处理这些子队列，而各队列分别以扫描算法进行处理。
2) FSCAN算法
FSCAN算法实质上是N步SCAN算法的简化。它只将磁盘请求访问队列分成两个子队列。一是当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。另一个队列则是在 扫描期间，新出现的所有请求磁盘I/O进程的队列，放入另一等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。

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

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

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

优点：公平、简单

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

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

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

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

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

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

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

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

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

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

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

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

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

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

优点：简化NStepSCAN算法

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