导图社区 操作系统期末复习总结
- 375
- 29
- 9
- 举报
操作系统期末复习总结
大学操作系统期末复习总结重点。下图内容包括操作系统引论、进程的描述与控制、处理机调度与死锁、储存器管理、虚拟储存器等。
编辑于2020-12-29 05:08:52
- 相似推荐
- 大纲
操作系统
第一章，操作系统引论
操作系统的目标和作用
定义
计算机系统中控制和管理计算机系统资源，合理组织计算机工作流程，提高资源利用率和方便用户使用计算机系统的计算机程序的集合。
目标
1.方便性（从用户角度分析）
2.有效性（从成本和效益角度分析（硬件贵））
3.可扩充性（从发展角度分析（功能完善和新增））
4.开放性（从发展角度分析（兼容））
作用
1. Os作为用户与计算机硬件系统之间的接口（从一般用户的观点看）
2. Os作为计算机系统资源的管理者（从资源管理观点看）
3. Os实现了对计算机资源的抽象（ OS用作扩充器）
操作系统的发展过程
未配置操作系统的计算机系统
人工操作方式
缺点：人工操作方式严重降低了计算机资源的利用率，此即所谓的人机矛盾。
脱机输入/输出方式
优点：这种脱机I/O方式的主要优点为： （1）减少了CPU的空闲时间。装带、卸带，以及将数据从低速i/o设备送到高速磁带上（或反之）的操作，都是在脱机情况下由外围机完成的，并不占用主机时间，从而有效的减少了CPU的空闲时间。 （2）提高了i/o速度。当CPU在运行中需要输入数据时，是直接从高速的磁带上将数据输入到内存的，这便极大的提高了i/o速度，从而进一步减少了CPU的空闲时间。
单道批处理系统
缺点：单道批处理系统最主要的缺点是，系统中的资源得不到充分的利用。
多道批处理系统
多道批处理系统的优缺点 1.资源利用率高。引入多道批处理，能够使多道程序交替进行，以保持CPU处于忙碌状态；在内存中装入多道程序可提高内存的利用率；此外还可以提高i/o设备的利用率。 2.系统吞吐量大。能提高系统吞吐量的主要原因可归纳为：① CPU和其他支援保持“忙碌”状态；②仅当作业完成时或运行不下去时才进行切换，系统开销小。 3.平均周转时间长。由于作业要排队依次进行处理，婴儿作业的周转时间较长，通常需几个小时甚至几天。 4.无交互能力。用户一旦把作业提交给系统后，直至作业完成，用户都不能与自己的作业进行交互，修改和调试程序及不方便。
分时系统
优点： 1.人机交互。 2.共享主机。 3.便于用户上机。 四个特征： 1.多路性。显著的提高了资源利用率，降低了使用费用，从而促进了计算机更广泛的应用。 2.独立性。提供了每个用户独立上机的用机环境，彼此之间互不干扰。 3.及时性。使用户的请求能在较短的时间内获得响应。 4.交互性。用户可通过终端与系统进行广泛的人机对话。
实时系统
五个特性： 1.多路性。 2.独立性。 3.及时性。 4.交互性。 5.可靠性。
比较
1.实时系统的多路更稳定；分时与用户情况有关。 2.实时系统对及时性的要求更及时。 3.对于交互性实时系统相对分时系统较弱。 4.从可靠性上面看实时系统的要求更高。
操作系统的基本特性
并发
并行性是指两个或多个事件在同一时刻发生。而并发性是指两个或多个事件在同一时间间隔内发生。
共享
在os环境下的资源共享或称为资源互用，是指系统中的资源可供内存中多个并发执行的进程共同使用。
虚拟
在os中，把通过某种技术将一个物理实体变为若干个逻辑上的对应物的功能，称为“虚拟”。
异步
异步的另外一种含义是计算机多线程的异步处理。与同步处理相对，异步处理不用阻塞当前线程来等待处理完成，而是允许后续操作，直至其它线程将处理完成，并回调通知此线程。
操作系统的主要功能
引入os的主要目的是，为多道程序的运行提供良好的运行环境，以保证多道程序能有条不序的高效的进行，并能最大程度的提高系统中各种资源的利用率，方便用户的使用。
处理机管理
1.进程控制。
2.进程同步。
3.进程通信。
4.调度。
作业调度。
进程调度。
存储器管理
1.内存分配。
2.内存保护。
3.地址映射。
4.内存扩充。
第二章，进程的描述与控制
进程的描述
定义
（1）进程是程序的一次执行。 （2）进程是一个程序及其数据在处理器上顺序执行时所发生的活动。 （3）进程是个独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
特征
1.动态性。
进程的实质是进程实体的执行过程，因此，动态性就是进程的最基本的特征。动态性还表现在：“它由创建而产生，由调度而执行，由撤销而消亡。”可见，进程实体有一定的生命期，而程序则只是一组有序指令的集合，并存放于某种介质上，其本身并不具有活动的含义，因而是静态的。
2.并发性。
是指多个进程实体同存于内存中，且能在一段时间内同时运行。引入进程的目的也正是为了使其进程实体能和其他进程实体并发进行。因此，并发性是进程的另一重要特征，同时也成为os的重要特征。而程序（没有建立PCB）是不能参与并发执行的。
3.独立性。
在传统的os中，独立性是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。
4.异步性。
异步性是指进程是按异步方式运行的，即按各自独立的，不可预知的速度向前推进。
状态（三种）
就绪状态。
这是指进程已处于准备好运行的状态，即进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。如果系统中有许多处于就绪状态的进程，通常将他们按一定的策略（如优先级策略）排成一个队列，称该队列为就绪队列。
执行状态。
这是指进程已获得CPU，其程序正在执行的状态。对任何一个时刻而言，在单处理机系统中，只有一个进程处于执行状态，而在多处理器系统中，则有多个进程处于执行状态。
阻塞状态。
这是指正在执行的进程由于发生某事件（如i/o请求、申请缓冲区失败等）暂时无法继续执行的状态，亦即进程的执行受到阻塞。此时引起进程调度， OS把处理机分配给另一个就绪进程，而让受阻进程处于暂停状态，一般将这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。通常系统将处于阻塞状态的进程也排成一个队列，称该队列为阻塞队列。实际上，在较大的系统中，为了减少队列操作的开销，提高系统效率，根据阻塞原因的不同，会设置多个阻塞队列。
转换
进程同步
临界资源
许多硬件资源如打印机、磁带机等，都属于临界资源，诸进程间应采取互斥方式，实现对这种资源的共享。
临界区
把在每个进程中访问临界资源的那段代码称为临界区。
为实现进程互斥地进入自己的临界区，所有同步机制都应遵循下述4条准则。 （1）空闲让进。 （2）忙则等待。 （3）有限等待。 （4）让权等待。
信号量的P,V操作
wait(S)称为P操作，表占用资源
signal(S)称为V操作，表释放资源
达到多少时挂起
经典进程的同步问题
生产者-消费者问题
1.利用记录型信号量解决生产者-消费者问题 2.利用AND信号量解决生产者-消费者问题 3.利用管程解决生产者-消费者问题
哲学家进餐问题
1.利用记录型信号量解决哲学家进餐问题 2.利用AND信号量机智解决哲学家进餐问题
读者-写者问题
1.利用记录型信号量解决读者-写者问题 2.利用信号量集机智解决读者-写者问题
进程通信（类型）
进程通信是指进程之间的信息交换。
1.共享存储器系统
（1）基于共享数据结构的通信方式
（2）基于共享存储区的通信方式
2.管道通信系统
半双工工作方式，属于高级的通信方式
3.消息传递系统
在该机制中，进程不必借助任何共享存储区或数据结构，而是以格式化的消息为单位，将通信的数据封装在消息中，并利用操作系统提供的一组通信命令，在进程间进行消息传递，完成进程间的数据交换。属于高级通信方式。
（1）直接通信方式。
（2）间接通信方式。
4.客户机-服务器系统
（1）套接字
（2）远程过程调用和远程方法调用
线程的基本概念
线程是操作系统能够进行调度运算的最小单位，它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。
线程与进程的比较
1.调度的基本单位
在传统的os中，进程是作为独立调度和分配的基本单位，因而进程是能独立运行的基本单位。在每次被调度时，都需要进行上下文切换，开销比较大。 而在引入线程的os中。已把线程作为调度和分配的基本单位，因而线程是能独立运行的基本单位。当线程切换时，仅需保存和设置少量寄存器内容，切换代价远低于进程。在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，必然就会引起进程的切换。
2.并发性
在引入线程的os中，不仅用户之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，甚至还允许在一个进程中的所有线程都能并发执行。同样，不同进程中的线程也能并发执行。 这使得os具有更好的并发性，从而能更加有效的提高系统资源的利用率和系统的吞吐量。
3.拥有资源
进城可以拥有资源，并作为系统中拥有资源的一个基本单位。然而，线程本身并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源。 线程除了拥有自己的少量资源（几乎不拥有资源）外，还允许多个线程共享该进程所拥有的资源。
4.独立性
在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。
5.系统开销
在创建或撤销进程时，系统都要为之分配和回收进程控制块、分配或回收其他资源，如内存空间和i/o设备等。 Os为此所付出的开销，明显大于线程创建或撤销时所付出的开销。 在进程切换时涉及到进程上下文的切换，而线程的切换代价也远低于进程。
6.支持多处理机系统
对于传统的进程，即单线程进程，不管有多少处理机，该进程只能运行在一个处理机上。 但对于多线程进程，就可以将一个进程中的多个线程分配到多个处理机上，使他们并行执行。
第三章，处理机调度与死锁
处理机调度的层次和调度算法的目标（3个层次，做什么，从哪里）
高级调度（又称长程调度或作业调度）
它的调度对象是作业。其主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为他们创建进程、分配必要的资源，并将他们放入就绪队列。高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。
低级调度（又称进程调度或短程调度）
其所调度的对象是进程（或内核级线程）。其主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的os中，都必须配置这级调度。
中级调度（又称内存调度或中程调度）
引入中级调度的主要目的是，提高内存利用率和系统吞吐量。为此，应把那些暂时不能运行的进程，调至外存等待，此时进程的状态称为就绪驻外存状态（或挂起状态）。当他们已具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些以具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。
CPU的利用率= CPU有效工作时间/ CPU有效工作时间+CPU空闲等待时间。 系统吞吐量=系统总共完成了多少作业/总共花了多少时间
作业与作业调度（各时间）
先来先服务（FCFS）
非抢正式算法 优点：公平,实现简单。 缺点：对淦作业不利。 不会产生饥饿现象。
短作业优先（SJF）
有抢占式，有非抢占式。 优点：追求最少平均等待时间，平均周转时间，平均带权周转时间。 缺点：（1）必须预知作业的运行时间。 （2）对长作业非常不利。 （3）采用短作业优先算法时，人机无法实现交互。 （4）该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业得到及时处理。 会产生饥饿现象。 “短作业/进程优先算法”默认为非抢占式。 “平均周转时间最少”用短作业优先。
优先级调度（PSA）
优点：能用优先级反映作业的紧迫程度，可以保证紧迫性作业优先运行。 缺点：可能会产生饥饿。 优先级调度算法可作为作业调度算法，也可作为进程调度算法。
高响应比优先（HRRN）
非抢占式调度算法。 优点：既考虑了作业的等待时间，又考虑了作业的运行时间，实现了较好的折中。 缺点：每次要进行调度之前，都需要先做响应比的计算，显然会增加系统开销。 不会产生饥饿。 响应比Rp=(等待时间+要求服务时间)/要求服务时间 =响应时间/要求服务时间 >1
周转时间=完成时间-到达时间 带权周转时间=周转时间/运行时间 等待时间=周转时间-运行时间
进程调度（哪几种优先级，从哪开始）
时间片轮转调度
可抢占式调度算法。 优点：相对公平，操作简单。可保证就绪队列中的所有进程，在一个确定的时间段内，都能获得一次CPU执行。 缺点：时间片较小会频繁的执行进程调度和进程上下文的切换，会增加系统的开销。 时间片较大，便退化为先来先服务算法，无法满足短作业和交互式用户的需求。 不会产生饥饿现象。
优先级调度
优先级调度算法的类型
（1）非抢占式优先级调度算法。
（2）抢占式优先级调度算法。
优先级的类型
（1）静态优先级。
优点：简单易行，系统开销小。 缺点：不够精确，可能会出现优先级低的进程长期没有被调度的情况。
（2）动态优先级。
当采用抢占死掉的方式时，若在规定当前进程的优先级随运行时间的推移而下降，则可防止一个长作业长期的垄断处理机。
多队列调度
多级反馈队列调度
可抢占式进程调度。 优点：对各类型进程相对公平（FCFS优点），每个新到来的进程都可以能快得到响应（RR优点）；短进程只要较少的时间就可以完成（SPF优点）；不必实现估计进程的运行时间（避免用户作假） 会产生饥饿现象。
基于公平原则的调度
实时调度（优先级倒置）
优先级倒置的解决办法： 条件：基于优先级抢线式的任务调度，资源共享。 现象：高优先级进程（线程）被低优先级进程（线程）阻塞或延迟的现象。 一种简单的解决方法是规定：进程在进入临界区后，其所占有的处理及不允许被抢占。 另外一种比较实用的方法是采用动态优先级继承方法。
死锁概述（产生的原因：3个；定义，产生的必要条件，处理方法）
定义：如果一组进程中的每一个进程都在等待仅由该进程中的其它进程才能引发的事件，那么该组进程是死锁的
产生死锁的原因
1.竞争不可抢占性资源引起死锁。
2.竞争可消耗资源引起死锁
3.进程推进顺序不当引起死锁
产生死锁的必要条件
（1）互斥条件。
（2）请求和保持条件。
（3）不可抢占条件。
（4）循环等待条件。
处理死锁的方法
（1）预防死锁。
这是一种较简单和直观的实现预防方法。该方法是通过设置某些限制条件，去破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较易实现的方法，已被广泛使用。
（2）避免死锁。
同样是属于事先预防策略，但它并不是事先采用各种限制措施，去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。
（3）检测死锁。
这种方法无需事先采取任何限制性措施，允许进程在运行过程中发生死锁。但可通过检测机构及时地检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。
（4）解除死锁。
当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤销一些进程，回收他们的资源，将它们分配给已处于阻塞状态的进程，使其能继续运行。
预防死锁
破坏“请求和保持”条件。
系统必须保证做到：当一个进程在请求资源时，他不能持有不可抢占资源。该保证可通过两种协议实现：第1种协议。第2种协议。
破坏“不可抢占”条件。
允许对进程实行抢夺。 这种方法实现起来比较复杂，且需付出很大的代价。会因为反复的申请和释放资源致使进程的执行被无限的推迟，不仅延长了进程的周转时间，而且也增加了系统的开销，降低了系统吞吐量。
破坏“循环等待”条件。
一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。规定每个进程必须按序号递增的顺序请求资源。 优点：其资源利用率和系统吞吐量都有较明显的改善。 缺点：1.限制了新类型设备的增加。 2.经常会发生作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。 3.会限制用户简单自主的编程。
避免死锁（安全、序列）
安全状态：只要能找到一个安全序列，系统就处于安全状态。 安全序列：如果系统按照这种序列分配资源，则每个进程都能够顺利完成。安全序列可以有多个。 如果系统处于安全状态，就一定不会发生死锁。如果系统处于不安全状态，则可能会发生死锁。
利用银行家算法避免死锁。
银行家算法中的数据结构： （1）可利用资源向量 Available.。如果 Available[j]=K，则表示系统中现有Rj类资源K个。 （2）最大需求矩阵 Max。如果 Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。 （3）分配矩阵Allocation。如果Allocation[i，j]=K，则表示进程i当前以分等Rj类资源的数目为K。 （4）需求矩阵 Need。如果Need[i，j]=K，则表示进程i还需要Rj类资源K个方能完成其任务。 Need[i，j]= Max[i，j]- Allocation[i，j]
死锁的检测与解除（给图判断是否会死锁）
检测（根据资源分配图判断是否死锁）
解除（1.抢占资源。2.终止（或撤销）进程）
第四章，存储器管理
存储器的层次结构
CPU寄存器
寄存器
主存
高速缓存
主存储器
磁盘缓存
辅存
固定磁盘
可移动存储介质
程序的装入和链接（哪几种，方法）
装入
1.绝对装入方式。
编译时产生绝对地址 只适用于单道程序环境
2.可从定位装入方式。
装入时将逻辑地址转化为物理地址 用于多道程序环境
3.动态运行时的装入方式。
运行时将逻辑地址转化为物理地址，需要设置重定位寄存器 允许程序运行时在内存中移动位置
链接
1.静态链接方式。
在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开
2.装入时动态链接。
将用户源程序编译后所得到的一组目标模块，在装入内存时，釆用边装入边链接的链接方式 优点：便于修改和更新，便于实现对目标模块的共享
3.运行时动态链接。
在执行过程中，当发现一个被调用的模块尚未装入内存时，立即由OS去找到该模块，并将之装入内存，将其链接到调用者模块上 优点：加快程序的装入过程，节省大量内存空间
连续分配存储管理方式
单一连续分配
最简单的一种存储管理方式，但只能用于单用户、单任务的OS中 方法：将内存分为系统区（内存低端，分配给OS用）和用户区（内存高端，分配给用户用）。采用静态分配方式，即作业一旦进入内存，就要等待它运行结束后才能释放内存 产生内部碎片
固定分区分配
最早使用的一种可运行多道程序的存储管理方法 数据结构：分区说明表 方法：将内存空间划分为若干个固定大小的分区，除OS占一区外，其余的一个分区装入一道程序。分区的大小可以相等，也可以不等，但事先必须确定，在运行时不能改变。即分区大小及边界在运行时不能改变 特点 一个作业只能装入一个分区，当分区大小不能满足作业的要求时,该作业暂时不能装入 通过对“分区使用表”的改写，来实现主存的分配与回收。作业在执行时，不会改变存储区域，所以采用静态地址重定位方式。此方法易于实现，系统开销小 产生内部碎片
概要
动态分区分配
一种动态划分存储器的分区方法 数据结构：空闲分区表；空闲分区链 方法：在作业进入内存时，根据作业的大小动态地建立分区，并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的
基于顺序搜索
首次适应算法
最快最好的也是最简单的 思想：从头到尾找到合适的分区
循环首次适应算法
思想：每次从上次查找结束的位置开始查找
最佳适应算法
思想：优先使用更小的分区，以保留更多大分区
最坏适应算法
思想：优先使用更大的分区，以防止产生太小的不可用的碎片
基于索引搜索
只有外部碎片 外部碎片可采用“紧凑”技术来实现
快速适应算法
该算法又称为分类搜索法,是将空闲分区根据其容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表,这样系统中存在多个空闲分区链表。同时,在内存中设立一张管理索引表,其中的每一个索引表项对应了一种空闲分区类型,并记录了该类型空闲分区链表表头的指针。
伙伴系统
哈希算法
动态可重定位分区分配
可重定位分区分配的目的是为了解决碎片问题。
对换（定义，类型，进程换进换出）
把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把具备运行条件的进程或进程所要的程序和数据换入内存
类型
（1）整体对换。（用于分时系统）
（2）页面（分段）对换。（为了支持虚拟存储系统）
进程的换入与换出
换入：将进程从外存调入内存。
换出：将内存中的某些进程调出至对换区，以便腾出内存空间。
分页存储管理方式
页面、物理块 地址结构：页号P和页内位移量W 页表 页表是存放在内存中的 为每个进程创建一个页表 作用：记录进程页面和实际存放的内存块之间的关系 快表 快表解决了两次访问内存的问题，降低系统的开销
分段存储管理方式
分段地址结构：段号、段内地址 三次访问
对比区别
（1）页是信息的物理单位，分页对用户不可见。段是信息的逻辑单位,分段对用户可见。
（2）页的大小固定，由系统确定，将逻辑地址划分为页号和页内地址是由机器硬件实现的。而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时根据信息的性质来划分
（3）分页的地址空间是一维的。分段的地址空间是二维的
（4）分段更容易实现信息的共享和保护（纯代码\可重入代码可以共享）
（5）分页（一级页表）、分段访问一个逻辑地址都需要两次访问，分段存储也可以引入快表机制
第五章，虚拟存储器
虚拟存储器概述（定义、局部性原理（时间、空间）、特征、实现方法）
具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
局部性原理
时间局限性。
如果程序中的某条指令被执行，则不久以后该指令可能再次执行；如果某个数据被访问过，则不久以后该数据可能再次被访问 原因：程序中存在着大量的循环操作
空间局限性。
一旦程序访问了某个单元，在不久以后其附近的存储单元也将被访问，即程序在一段时间内所访问的地址可能集中在一定的范围之内 典型情况：程序的顺序执行
基本特征
（1）多次性。
（2）对换性。
（3）虚拟性。
实现方法
1、分页请求系统。
2、请求分段系统。
请求分页存储管理方式（列表有哪些项、意思、缺页中断、策略哪几种）
请求分页存储管理方式
请求分页的页表项。
页号、物理块号 状态位P：指示该页是否已调入内存，供程序访问时参考 访问字段A：用于记录本页在一段时间内被访问的次数 修改位M：标识该页在调入内存后是否被修改过 外存地址：用于指出该页在外存上的地址，通常是物理块
缺页中断。
在请求分页系统中，每当所要访问的页面不在内存时，便产生一切页中断，请求OS将所缺之页调入内存。
越界中断。
页号大于或等于页表长度；段内地址超过该段的段长
内存分配策略。
固定分配局部置换
可变分配全局置换
可变分配局部置换
页面调入策略。
预调页策略
请求调页策略
页面置换算法（缺页数，缺页率，页面置换次数）
缺页率：一个进程逻辑空间为n页，系统为其分配的内存物理块数为m(m≤n)。进程运行过程中，访问页面成功次数为S，访问页面失败次数为F，则进程总的访问次数为A=S+F。 缺页率即为：f=F/A
最佳置换算法。
其所选择的被淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。 采用最佳置换算法通常可保证获得最低的缺页率。
先进先出页面置换算法。
会出现“贝拉迪异常”
最近最久未使用置换算法。
最少使用置换算法。
Clock置换算法。
页面缓冲算法。
第六章，输入输出系统
磁盘存储器的性能和调度（调度算法（总的，平均））
磁盘访问时间
寻道时间
Ts=m×n+s s：启动磁臂的时间。约为2ms。 n：磁头移动n条磁道所花费的时间。 m：常数（与磁盘驱动器的速度有关），对一般磁盘，m=0.2；对高速磁盘，m≤0.1。
旋转延迟时间
传输时间
这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。 Tt的大小与每次所读/写的字节数b和旋转速度有关： Tt=b/rN r：磁盘每秒钟的转速。 N：一条磁道上的字节数。 当一次读/写的字节数相当于半条磁道上的字节数时，Tt与Tπ（旋转延迟时间）相同，因此，可将访问时间Ta表示为： Ta=Ts+1/2r+b/rN
磁盘调度算法
先来先服务
目标：使磁盘的平均寻道时间最少 思想：进程请求访问磁盘的先后次序进行调度
最短寻道时间优先
思想：选择从当前磁头位置出发，移动距离或时间最少的磁盘 I/ 0 请求
扫描算法
思想：处理所有向上的请求，然后再处理相反方向的请求
循环扫描算法
思想：移动磁头从磁盘一端到磁盘另一端，并且处理行程上的请求。然而，当磁头到达另一端时，它立即返回到磁盘的开头，而并不处理任何回程上的请求