操作系统复习资料

操作系统复习一、 选择题1. 什么是多道程序？本质是什么？为什么要引入？多道程序设计技术概念：在多道批处理系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，是它们共享CPU和系统中的各种资源。引入多道程序技术是为了进一步提高资源的利用率和吞吐量。多道程序设计技术带来的好处：1）提高CPU的利用率2）提高内存和I/O设备利用率3）增加系统的吞吐量，保存CPU、I/O设备不断忙碌，大幅度地提高系统的吞吐量2. 信号量互斥（1）资源（值为负数（代表什么）信号量的概念：表明资源可以提供给进城使用的量，它是一个整型值。计数信号量S的物理含义：S0：表示有n个可利用的资源。S0：表示有n个被阻塞的资源。S=0：表示资源正在使用。信号量值可变，但仅能由、操作来改变1) P操作原语P(S) (1) P操作一次，S值减，即SS（请求分配一资源）； (2) 如果S0，则该进程继续执行； 如果S0表示无资源，则该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至另一个进程执行V（S）操作）。2)V操作原语（荷兰语的等待）V(S) (1) V操作一次，S值加1，即SS+（释放一单位量资源）； (2) 如果S0，表示有资源，则该进程继续执行； 如果S0，则释放信号量队列上的第一个PCB所对应的进程（阻塞态改为就绪态），执行V操作的进程继续执行。3. 作业调度（概念、估计时间、几种调度算法）作业：包含通常的程序和数据，还配有作业说明书，系统根据该说明书对程序的运行进行控制。作业调度的主要任务是根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。作业调度中每次接纳进入内存的作业数，取决于多道程序度，应将作业从外存调入内存，取决于采用的调度算法。作业调度算法：先来先服务算法（FCFS），每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。作业的等待时间就是作业的优先级，等待时间越长，优先级越高。可用于作业调度和进程调度。（特殊情况无法执行）短作业优先(SJF)调度，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。以作业的长短来计算优先级，作业越短，其优先级越高。可用于作业调度和进程调度。（长作业可能被饿死）优先级调度算法（PSA），系统从后备队列中选择若干个优先级最高的作业装入内存。基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据优先级进行调度的。（确认优先级困难）高响应比优先调度算法（HRRN），优先权=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间=响应比（Rp）。等待时间相同时，要求服务时间越短优先权越高，类似SJF算法；要求服务时间相同时，等待时间越长优先级越高，类似FCFS算法；对于长作业的优先级，可以随等待时间的增加而提高，当其等待时间足够长时，也可以获得处理机。（产生额外开销）作业的周转时间包括四部分时间：1、作业在外存后备队列上等待（作业）调度的时间；2、进程在就绪队列上等待进程调度的时间；3、进程在CPU上执行的时间；4进程等待I/O操作完成的时间。周转时间：1) 周转时间=完成时刻提交时刻2) 平均周转时间=周转时间n3) 带权周转时间=周转时间实际运行时间4) 平均带权周转时间=带权周转时间n4. 几个管理功能是哪些？分别管理什么？1）处理机管理：进程控制，进程同步，进程通信，调度；2）存储器管理：内存分配和回收，地址映射，内存保护，内存扩充；3）设备管理：缓冲管理，设备分配，设备处理；4）文件管理：文件存储空间的管理，目录管理，文件的读/写管理及文件的共享和保护；5）OS与用户之间的接口：程序接口，用户接口，联机接口，脱机接口，图形接口；新功能：系统安全、网络的功能和服务、支持多媒体5. 基本段、页式内存管理中，需要访问几次内存？24位地址，则虚拟内存空间可达多少？2次，2次；224;6. 虚拟存储含义，本质虚拟存储器的概念：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储系统。7. 进程的几个状态，之间的转换进程的基本状态：就绪、执行、阻塞。进程在三个基本状态之间转换：1)绪状态执行状态：进程分配到CPU资源；2)执行状态就绪状态：时间片用完；3)执行状态阻塞状态：I/O请求；4)阻塞状态就绪状态：I/O完成。8. 常见操作系统单任务、多任务是什么？单用户单任务操作系统：只允许一个用户上机，且只允许用户程序作为一个任务执行。这是最简单的微机操作系统，主要配置在8位和16位微机上，典型代表：CP/M（8位）、MS-DOS（16位）单用户多任务操作系统：只允许一个用户上机，但是允许用户把程序分成若干个任务，使它们并发执行，从而改善了系统的功能。典型代表：Window（32位）多用户多任务操作系统：允许多个用户通过各自的终端，使用同一台机器，共享主机系统的各种资源，而每个用户程序又可以进一步分为几个任务，使它们能并发执行，从而可进一步提高资源利用率和系统吞吐量。典型代表：UNIX OS（32位）其变形有Solaris OS和Linux9. 同步的概念，异步的概念，并行概念，并发概念并行：指两个或多个事件在同一时刻发生；并发：指两个或多个事件在同一时间间隔内发生；同步：同步指两个或两个以上随时间变化的量在变化过程中保持一定的相对关系。异步：与同步相对应，异步指的是让CPU暂时搁置当前请求的响应,处理下一个请求,当通过轮询或其他方式得到回调通知后,开始运行。进程的同步：主要源于进程合作，是进程间共同完成一项任务时直接发生相互作用的关系。为进程之间的直接制约关系。在多道环境下，这种进程间在执行次序上的协调是必不可少的。进程的互斥：主要源于资源共享，市进程之间简介制约关系。再多得到系统中每次只允许一个进程访问的自愿成为临界资源，进程互斥就是保证每一次只有一个进程使用临界资源。10. 操作系统的抖动理解，处理CPU在虚拟存储中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃，这种现象称为抖动。减少抖动：1减少页面的频繁调进主存2选择适当的置换算法11. 四种I/O方式了解，各种I/O概念I/O控制方式的种类和应用：1)程序I/O 方式：早期计算机无中断机构，处理机对I/O设备的控制采用程序I/O方式或称忙等的方式。（适用于结构简单，只需少量硬件的电路）2)中断驱动I/O 控制方式：适用于有中断机构的计算机系统中。（适用于高效场合）3)直接存储器访问(DMA)I/O 控制方式：适用于具有DMA控制器的计算机系统中。（适用于无需CPU介入的控制器来控制内存与外设之间的数据交流的场合）4)I/O通道控制方式：具有通道程序的计算机系统中。（适用于以字节为单位的干预，同时实现CPU、通道和I/O设备三者同时操作的场合）12. 分时、实时操作系统了解（Spooling操作系统（给出四个选项要知道哪个是哪个系统）分时系统概念：将一台计算机很好的提供给多个用户同时使用，提高计算机的利用率。（为了满足用户对人-机交互的需求）实时系统概念：是计算机系统可以立即对用户程序要求或者外部信号作出反应的系统，它可以分为硬实时系统和软实时系统。（飞机或火车的订票系统、由于播放音频和视频的多媒体系统、嵌入式系统（智能仪器和设备）Spooling：它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。Spooling系统：若有进程要求对它打印输出时，SPOOLing系统并不是将这台打印机直接分配给进程，而是在共享设备（磁盘或磁鼓）上的输出SPOOLing存储区中为其分配一块存储空间，进程的输出数据以文件形式存放于此。各进程的数据输出文件形成了一个输出队列，由输出SPOOLing系统控制这台打印机进程，依次将队列中的输出文件实际打印输出。在SPOOLing 系统中，实际上并没有为任何进程分配，而只是在输入井和输出井中，为进程分配一存储区和建立一张I/O请求表。这样，便把独占设备改造为共享设备。SPOOLing技术的优点：提高了I/O的速度；将独占设备改造为共享设备；实现了虚拟设备功能。 分时系统与实时系统进行比较. a. 分时系统是一种通用系统，主要用于运行终端用户程序，因而它具有较强的交互能力；而实时系统虽然也有交互能力，但其交互能力不及前 b. 实时信息系统对实用性的要求与分时系统类似，都是以人所能接收的等待时间来确定；而实时控制系统的及时性则是以控制对象所要求的开始截止时间和完成截止时间来确定的，因此实时系统的及时性要高于分时系统的及时性 c. 实时系统对系统的可靠性要求要比分时系统对系统的可靠性要求高13. 分段、分页、段页式管理，最大段数及页数分页存储管理方式：在该方式中，将用户程序的地址空间分为若干个固定大小的区域，称为“页”或“页面”。相应的，也将内存空间分为若干个物理块或页框，页和框的大小相同。这样用户程序的任意一页放入任一物理块中，实现了离散分配。分段存储管理方式：为了满足用户要求而形成的一种存储管理方式，它把用户程序地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。以段为单位，这些段在内存中可以不相邻接，所以也同样实现了离散分配。段页式管理存储方式：这是分页和分段两种存储管理方式相结合的产物，同时具有两者的优点，是目前应用较为广泛的一种存储管理方式。请求分页系统：是在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许用户程序只装入少数页面的程序（及数据）即可启动运行。请求分段系统：在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。它允许用户程序只要装入少数段（而非所有段）的程序和数据即可启动运行。最大段数为2的段位数次方地址长度为32位，其中015位为段内地址，1631位为段号，则允许一个作业最长有64k个段，每个段的最大长度为64KB最大页数为2的页位数次方地址长度为32位，其中111位为页内地址，即每页的大小为4kB，1231位为页号，地址空间最多允许有1M页1kB=1024=2101M=1024kB=210kB1G=1024M=210M232=4G分页与分段的区别 分页信息的物理单位大小一样，由系统固定地址空间是一维的分段信息的逻辑单位 大小不等，由用户确定 地址空间是二维的分区存储管理中常采用哪些分配策略？比较它们的优缺点。 分配策略有：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法。 a.首次适应算法的优缺点：保留了高址部分的大空闲区，有利于后到来的大型作业的分配；低址部分不断被划分，留下许多难以利用的、小的空闲区，且每次分区分配查找时都是从低址部分开始，会增加查找时的系统开销。 b.循环首次适应算法的优缺点：使内存中的空闲分区分布得更为均匀，减少了查找时的系统开销；缺乏大的空闲分区，从而导致不能装入大型作业。 c.最佳适应算法的优缺点：每次分配给文件的都是最适合该文件大小的分区；内存中留下许多难以利用的小的空闲区。 d.最坏适应算法的优缺点：给文件分配分区后剩下的的空闲区不至于太小，产生碎片的几率最小，对中小型文件分配分区操作有利；使存储器中缺乏大的空闲区，对大型文件的分区分配不利。14. 页表、段表地址如何转换（基本机制）所谓地址转换就是将用户的逻辑地址转换成内存的物理地址，完成地址重定位。在具有快表的段页式存储管理方式中，如何实现地址变换？ 答：在CPU给出有效地址后，由地址变换机构自动将页号P送入高速缓冲寄存器，并将此 页号与高速缓存中的所有页号比较，若找到匹配页号，表示要访问的页表项在快表中。可直 接从快表读出该页对应物理块号，送到物理地址寄存器中。如快表中没有对应页表项，则再 访问内存页表，找到后，把从页表项中读出物理块号送地址寄存器；同时修改快表，将此页 表项存入快表。但若寄存器已满，则OS必须找到合适的页表项换出。2. 分页存储管理的地址机构15 12 11 0 页号P 页内位移量W页号4位，每个作业最多2的4次方=16页，表示页号从00001111（24-1），页内位移量的位数表示页的大小，若页内位移量12位，则2的12次方=4k，页的大小为4k，页内地址从000000000000111111111111若给定一个逻辑地址为A，页面大小为L，则页号P=INTA/L，页内地址W=A MOD L3. 页表分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中，为了能在内存中找到每个页面对应的物理块，系统为每个进程建立一张页面映射表，简称页表。页表的作用是实现从页号到物理块号的地址映射。页表： 页号 物理块号 存取控制 0 2 1 15（F） 2 14（E） 3 1 4. 地址变换（1） 程序执行时，从PCB中取出页表始址和页表长度（4），装入页表寄存器PTR。（2） 由分页地址变换机构将逻辑地址自动分成页号和页内地址。例：11406D=0010|110010001110B=2C8EH 页号为2,位移量为C8EH=3214D或11406 DIV 4096=2 11406 MOD 4096=3214（3） 将页号与页表长度进行比较(24)，若页号大于或等于页表长度，则表示本次访问的地址已超越进程的地址空间，产生越界中断。（4） 将页表始址与页号和页表项长度的乘积相加，便得到该页表项在页表中的位置。（5） 取出页描述子得到该页的物理块号。 2 14（E）（6） 对该页的存取控制进行检查。（7） 将物理块号送入物理地址寄存器中，再将有效地址寄存器中的页内地址直接送入物理地址寄存器的块内地址字段中，拼接得到实际的物理地址。例：0010|110010001101B1110|110010001101B=EC8EH=60558D或 14*4096+3214=60558D3. 分段地址结构作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例程序段、数据段等。每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间是二维的。15 12 11 0 段号 段内位移量段号4位，每个作业最多24=16段，表示段号从00001111（24-1）；段内位移量12位，212=4k，表示每段的段内地址最大为4K（各段长度不同），从0000000000001111111111114. 段表段号 段长 起始地址 存取控制 0 1K 4096 1 4K 17500 2 2K 8192 5. 地址变换(1). 程序执行时，从PCB中取出段表始址和段表长度（3），装入段表寄存器。(2). 由分段地址变换机构将逻辑地址自动分成段号和段内地址。例：7310D=0001|110010001110B=1C8EH段号为1,位移量为C8EH=3214D(3). 将段号与段表长度进行比较(13)，若段号大于或等于段表长度，则表示本次访问的地址已超越进程的地址空间，产生越界中断。(4). 将段表始址与段号和段表项长度的乘积相加，便得到该段表项在段表中的位置。(5). 取出段描述子得到该段的起始物理地址。1 4K 17500(6). 检查段内位移量是否超出该段的段长(3214执行：进程分配到CPU资源2）执行-就绪：时间片用完3）执行-阻塞:I/O请求4）阻塞-就绪:I/O完成7.有哪些I/O控制方式，概念？I/O控制方式的种类和应用：1)程序I/O 方式：早期计算机无中断机构，处理机对I/O设备的控制采用程序I/O方式或称忙等的方式。（适用于结构简单，只需少量硬件的电路）2)中断驱动I/O 控制方式：适用于有中断机构的计算机系统中。（适用于高效场合）3)直接存储器访问(DMA)I/O 控制方式：适用于具有DMA控制器的计算机系统中。（适用于无需CPU介入的控制器来控制内存与外设之间的数据交流的场合）4)I/O通道控制方式：具有通道程序的计算机系统中。（适用于以字节为单位的干预，同时实现CPU、通道和I/O设备三者同时操作的场合）8.调度概念，高中低级调度是什么？3）三级调度：高级调度（作业调度）、中级调度（内存对换）、低级调度（进程调度）高级调度的任务：高级调度的主要任务是根据某种算法，把外存上处于后备队列中的那些作业调入内存。低级调度的任务：低级调度是保存处理机的现场信息，按某种算法先取进程，再把处理器分配给进程。引入中级调度的目的：引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用内存资源，将它们调至外存等待，把进程状态改为就绪驻外存状态或挂起状态。9.什么是快表，作用是什么？为了提高地址变换速度，在地址变换机构中增设一个具有并行查询功能的特殊高速缓冲寄存器，称为快表；作用是用来存放当前访问的那些页表项10. 文件系统的目录结构有哪些？优缺点？文件系统的模型可以分为三层：第一层：对象及其属性说明第二层：对对象操纵和管理的软件集合第三层：文件系统接口逻辑文件：物理文件中存储的数据的一种视图方式，不包含具体的数据，仅包含物理文件中的数据的索引。物理文件：是指文件在外存上的存储组织形式文件系统：又被管理的文件，操作系统中管理文件的软件和相应的数据结构组成的一个系统。目录结构：单级目录、两级目录和多级目录结构。采用单级目录五年级是否能满足对目录管理的主要要求？为什么？不能，单级目录在整个文件系统中只建立一张目录表，每个文件占一个目录项，其中含文件名、文件扩展名、文件长度、文件类型、文件物理地址、状态位等其它文件属性。单级只能实现目录管理的基本功能，不能满足查找速度、允许重名和文件共享的要求。目前广泛应用的目录结构有哪些？它有什么优点？现代操作系统都采用多级目录结构，基本特点是查询速度快、层次结构清晰、文件管理和保护易于实现。文件目录等同于常所接触的文件夹？现代操作系统如何实现文件目录管理？ 严格来说不等同。文件目录就是指一本文件内容的总纲,目录上标明了各贡内容的主题.这个就叫目录。文件夹，是专门装整页文件用的，主要目的是为了更好的保存文件，使它整齐规范。目录管理：（1）实现“按名存取”，即用户只须向系统提供所需访问的文件名字。（2）提高对目录的检索速度（3）文件共享，在多用户系统中，应允许多个用户共享一个文件（4）允许文件重名。以便于用户按照自己的习惯给文件命名和使用文件。11.进程与线程的区别与联系？进程概念：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位线程概念：是程序执行流的最小单元，是程序中一个单一的顺序控制流程相同点：1)二者都具有ID、一组寄存器、状态、优先级及所要遵循的调度策略2）每个进程都有一个进程控制块，线程也拥有一个线程控制块3）线程和子进程共享父进程中的资源；线程与子进程独立与它们的父进程，竞争使用处理机资源；线程与子进程的创建者可以在线程和子进程上实行某些控制；线程与子进程可以改变其属性并创建新的资源不同点：1） 线程是进程的一部分，一个没有线程的进程是可以被看作单线程的，如果一个进程内拥有多个进程，进程的执行过程不是一条线程的，而是多条线程共同完成的2） 启动一个线程所花费的空间远远小于启动一个进程所花费的空间，而且，线程间彼此切换所需要的时间也远远小于进程间切换所花费的时间3） 系统在运行的时候会为每个进程分配不同的内存区域，但不会为线程分配内存（线程所使用的资源是它所属的进程的资源），线程组只能共享资源。对于不同的进程来说，它们具有独立的数据空间，要进行数据的传递只能通过通信的方式进行，这种方式不仅费时而且很不方便。而一个线程的数据可以直接为其他线程所用，着不仅快捷，而且方便4） 与进程的控制表PCB相似，线程也有自己的控制表TCB，但是TCB中所保存的线程状态比PCB表中少多了5） 进程是系统所有资源分配时候的一个基本单位，拥有一个完整的虚拟空间地址，并不依赖线程而独立存在进程和线程的比较：1）调度性：线程在OS 中作为调度和分派的基本单位，进程只作为资源拥有的基本单位。2）并发性：进程可以并发执行，一个进程的多个线程也可并发执行。3）拥有资源：进程始终是拥有资源的基本单位，线程只拥有运行时必不可少的资源，本身基本不拥有系统资源，但可以访问隶属进程的资源。4）系统开销：操作系统在创建、撤消和切换进程时付出的开销显著大于线程。12. 信号量机制，AND型基本特征？信号量机制：一种进程同步的工具分类：整型信号量机制、记录型信号量机制、AND型信号量机制AND型信号量机制的特征：将进程在整个运行过程中所需要的所有资源，一次性全部地分配给进程，待进程使用完后在一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给它。13. 什么是虚拟存储器，实现的形式？虚拟存储器的概念：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储系统。虚拟存储器的特征：离散性、多次性、对换性和虚拟性。最本质的是离散性，最重要的是虚拟性。虚拟存储器的实现方法：1）在分页请求系统中是在分页的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。允许只装入少数页面的程序(及数据)，便启动运行。2)在请求分段系统中是在分段系统的基础上，增加了请求调段及分段置换功能后形成的段式虚拟存储系统。允许只装入少数段(而非所有段)的用户程序和数据，即可启动运行。可能考的简答题l 进程和程序的比较：1)动态性是进程最基本的特性，表现为由创建而产生，由调度而执行，因得不到资源而暂停执行，由撤销而消亡。进程有一定的生命期，而程序只是一组有序的指令集合，是静态实体。2）并发性是进程的重要特征，同时也是OS 的重要特征。引入进程的目的正是为了使其程序能和其它进程的程序并发执行，而程序是不能并发执行的。3）独立性是指进程实体是一个能独立运行的基本单位，也是系统中独立获得资源和独立调度的基本单位。对于未建立任何进程的程序，不能作为独立单位参加运行。l 什么是死锁？造成死锁的根本原因是什么？死锁是指系统中几个进程无限期的等待永远不会发生的条件，使系统处于停滞状态造成死锁的原因：系统资源不足；进程运行推进的顺序不合适；资源分配不当之处l 产生死锁的必要条件？（1） 互斥条件：系统使用临界资源（2） 占有且申请条件： 进程投入时不是一次性地申请所需全部资源，而是运行时按需要 临时动态的申请（3） 资源的循环等待条件： 系统中的几个进程形成循环地等待对方所占用的资源的关系（4） 不可强占条件：一个进程占用资源，未经本进程释放，其他进程不能强行剥夺。如果在计算机系统中同时具备上面四个必要条件时，那么会发生死锁。即四个条件中有一个不具备，系统就不会发生死锁。l 解决死锁的一般方法？死锁的预防、避免、检测与恢复。 死锁的预防1. 死锁预防的基本思想：打破产生死锁的四个必要条件的一个或几个。2. 预防死锁的策略：资源预先分配策略、资源有序分配策略。 1) 资源预先分配策略：打破占有且申请条件，进程在运行前一次性地向系统申请它所需要的全部资源，如果所序言的全部资源得不到满足，则不分配任何资源，此进程暂不运行。2) 资源有序分配策略：打破循环等待条件，把资源事先分类编号，按序分配，使进程在申请、占用资源时不会形成环路。死锁的避免避免死锁的方法：银行家算法（分配资源之前，判断系统是否是安全的；若是，才分配）死锁的检测1. 死锁的检测算法：是当进程进行资源请求时检查并发进程组是否构成资源的请求和占用环路。如果不存在这一环路，则系统中一定没有死锁。 2. 总之：如果资源分配图中不存在环路，则系统不存在死锁；反之如果资源分配图中存在环路，则系统可能存在死锁，也可能不存在死锁。 死锁的恢复 1.死锁的恢复思想：一旦在死锁检测时发现死锁，就要消除死锁，使系统从死锁中恢复过来。2. 死锁的恢复方法：1) 系统重新启动2) 撤消进程、剥夺资源 三、综合题信号量表示前趋图磁盘调度算法（1） 先来先服务FCFS：公平，简单，每个进程的请求都能依次得到处理。 没有对寻道优化，平均寻道时间长。（2） 最短时间优先调度算法SSTF：要求访问的磁道是当前磁头所在的磁道最近，每次寻道时间最短。可能导致一些请求无限期推延。（3） （扫描）电梯调度算法SCAN：不仅考虑当前磁道的距离，优先考虑在磁道前进方向的最短时间，排除磁头在盘面上的往复运动(电梯原理)。（4） N-SCAN：是SCAN的改良。磁头改变方向时，以到达请求服务的最短时间。对中间请求服务更有利。（5） 循环扫描算法C-SCAN：磁头单项移动。消除N-SCAN对两端请求的不公平。页面置换算法1. 最佳（Optimal）置换算法：其所选择的被淘汰页面将是以后永远不适用或是在最长（未来）时间内不再被访问的页面2. 先进先出（FIFO）页面置换算法：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰3. LRU置换算法：选择最近最久未使用的页面予以淘汰