第一章 操作系统引论

操作系统OS是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。

1. 目标

有效性、方便性、可扩充性、开放性。

2. 作用

作为用户与计算机硬件系统之间的接口作为计算机系统资源的管理者实现了对计算机资源的抽象

3.发展过程

①人工操作方式：用户独占全机，CPU等待人工操作。

②脱机输入输出方式：事先将装有用户程序和数据的纸带装入纸带输入机，在外围机的控制下，把纸带上的数据输入到磁带上（类似于磁盘）。当CPU需要时，从磁带将其高速地调入内存。反之类同。优点：减少了CPU的空闲时间，提高了I/O速度。

③单道批处理系统：首先监督程序将磁带第一个作业装入内存，运行控制权在该作业，该作业处理完成时，控制权交回到监督程序，再由监督程序把磁带上的第二个作业调入内存。系统自动对作业成批处理。（内存始终只保持一道作业—单道批处理）。

缺点：内存浪费，不能充分利用系统资源。

④多道批处理系统：用户所提交的作业先存放在外存，排成一个“后备队列”，再由作业调度程序按一定的算法从队列选择若干作业调入内存，使他们共享CPU和系统中的各种资源。

优缺点：资源利用率提高，系统吞吐量大，平均周转时间长，无交互能力。

⑤分时系统：在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。因此，作业直接进入内存，采用轮转运行方式，系统配置一个多路卡（实现分时多路复用），及时接收用户终端命令（数据）。

特征：多路性、独立性、及时性、交互性。

⑥实时系统：系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务的协调一致的运行。

特征：多路性（周期性信息采集，多个对象或执行机构进行控制）、独立性、及时性、交互性、可靠性（多级容错措施）。

4.基本特征

①并发性

引入进程：提高了系统资源的利用率和系统吞吐量，并改善了系统的性能。

引入线程：对它的调度所付出的开销比进程小得多，能更高效地提高系统内多个程序间并发执行的程度。

②共享性

互斥共享方式：在一段时间内只允许一个进程访问的资源称为临界资源或独占资源。

同时访问方式：允许在一段时间内由多个进程同时对它们进行访问。

③虚拟技术（通过某种技术把一个物理实体变为若干个逻辑上的对应物）

(1) 时分复用技术：利用处理机的空闲时间运行其他程序，提高处理机的利用率。

(2) 空分复用技术：利用存储器的空闲空间存放其他程序，提高内存的利用率。

④异步性（进程以不可预知的速度向前推进）。

5.主要功能

存储器管理功能

①进程控制：创建和撤销进程，分配资源、资源回收，控制进程运行过程中的状态转换。

②进程同步：为多个进程运行进行协调。

进程互斥（为每个临界资源配置一把锁）、进程同步。

③进程通信：实现相互合作之间的进程之间的信息交换。

④调度：作业调度，进程调度。

存储器管理功能

存储器管理的主要任务：为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率，并能从逻辑上扩充内存。

功能：

①内存分配：静态分配、动态分配。

②内存保护：确保每道用户程序都只在自己的内存空间内运行，彼此互不干扰。一种比较简单的内存保护机制是设置两个界限寄存器。

③地址映射：将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。

④内存扩充：借助于虚拟存储技术，逻辑上扩充内存容量。

设备管理功能：

设备管理的主要任务：完成用户进程提出的I/O请求，为其分配所需的I/O设备；提高CPU和I/O设备的利用率，提高I/O速度，方便用户使用I/O设备。

功能：

①缓存管理：缓和CPU和I/O设备速度不匹配的矛盾。

②设备分配：根据用户进程I/O请求、系统现有资源情况以及按照某种设备的分配策略，为之分配其所需的设备。

③设备处理：用于实现CPU和设备控制器之间的通信。

文件管理功能

文件管理的主要任务：对用户文件和系统文件进行管理，方便用户使用，并保证文件的安全性。

①文件存储空间的管理：为每个文件分配必要的外存空间，提高外存的利用率，并能有助于提高文件系统的存、取速度。

②目录管理：为每个文件建立其目录项，并对众多的目录项加以有效的组织，以实现方便的按名存取，即用户只须提供文件名便可对该文件进行存取。

③文件的读/写管理和保护 操作系统与用户之间的接口：用户接口、程序接口

6.系统调用

如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。

Linux 系统调用主要有以下这些： 进程控制 fork(); exit(); wait(); 进程通信 pipe(); shmget(); mmap(); 文件操作 open(); read(); write(); 设备操作 ioctl(); read(); write(); 信息维护 getpid(); alarm(); sleep(); 安全 chmod(); umask(); chown()。

7.OS结构设计

传统的操作系统结构：无结构操作系统 –> 模块化结构OS –> 分层式结构OS

大内核与微内核

大内核

大内核是将操作系统功能作为一个紧密结合的整体放到内核。 由于各模块共享信息，因此有很高的性能。 大内核是将操作系统功能作为一个紧密结合的整体放到内核。 由于各模块共享信息，因此有很高的性能。

微内核

由于操作系统不断复杂，因此将一部分操作系统的功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。 在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。

微内核OS结构

①足够小的内核

②基于客户/服务器的模式

③应用“机制与策略分离”的原理

④采用面向对象技术

微内核的基本功能

①进程（线程）管理

②低级存储器管理

③中断和陷入处理

微内核操作系统存在的问题：运行效率降低。

微内核OS的效率降低的最主要原因：

频繁地在用户态和核心态之间进行切换。即在完成一次客户对OS提出的服务请求时，需要利用消息实现多次交互和进行用户/内核模式以及上下文的多次切换。

8.中断分类

外中断

由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。 – 异常 由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。 – 陷入 在用户程序中使用系统调用。

第二章 进程管理

进程的基本概念

程序的顺序执行：按照某种先后次序顺序执行，仅当前一程序执行完后，才能执行后继操作。

特征：顺序性、封闭性、可再现性。

前驱图：描述进程之间执行的前后关系。

程序的并发执行：

特征：间断性、失去封闭性、不可再现性

进程实体：由程序段、相关的数据段和PCB组成，所谓创建和撤销进程实际是对其中的PCB的创建和撤销。（PCB：进程控制块Process Control Block）

进程的特征：动态性、并发性、独立性、异步性

进程定义：是进程实体的运行过程，是系统进行资源分配和调度的一个独立单元。

进程的三种基本状态：就绪状态、执行状态、阻塞状态（阻塞典型事件：请求I/O，申请缓冲空间等）。

进程的三种基本状态及其转换图。

挂起状态：进程处于静止状态，暂停执行（执行状态下挂起），暂不接受调度（就绪状态下挂起）。

进程的五种基本状态及其转换图。

具有创建、终止和挂起状态的进程状态图。

进程控制块PCB

PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。是操作系统中最重要的记录型数据结构。

进程控制块中的信息：进程标识符、处理机状态、进程调度信息、进程控制信息。

进程控制块的组织方式：链接方式、索引方式。

进程控制

进程控制一般是由OS的内核中的原语来实现的。

进程的创建

①申请空白PCB。

②为新进程分配资源。

③初始化进程控制块。

④将新进程插入就绪队列（如果进程就绪队列能够接纳新进程）。

进程的终止过程

①根据被终止进程的标识符，从 PCB **中检索出该进程的 PCB，从中读出该进程的状态。 ②若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。

③若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防它们成为不可控的进程。 ④将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。

⑤将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。

进程的阻塞与唤醒

进程的挂起与**

进程同步

并发进程之间的制约关系

①间接相互制约关系。源于资源共享。

②直接相互制约关系。源于进程间的合作。

临界区：每个进程中访问临界资源的那段代码称为临界区。筑进程互斥地进入自己的临界区，便可实现诸进程对临界资源互斥访问。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

可把一个访问临界资源的循环进程描述如下：

同步机制应遵循的规则：空闲让进、忙则等待、有限等待、让权等待。

信号量机制

整型信号量

用于表示资源数目的整型量，仅能通过原子操作wait（S）和signal（S）来访问，也就是常见的 P 和 V 操作，执行时不可中断，通常的做法是在执行这些操作的时候屏蔽中断。

记录型信号量

不存在“忙等”现象的进程同步机制，遵循了“让权等待”的准则。需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针L，用于链接上述的所有等待进程。

如果信号量的取值只能为0或者1，那么就成为了互斥量（Mutex），0表示临界区已经加锁，1表示临界区解锁。用于进程互斥。

AND型信号量

将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。

信号量集

AND型信号量基础上，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放。

信号量的应用

利用信号量实现进程互斥

wait(mutex)和signal(mutex)必须成对地出现。 利用信号量实现前趋关系

管程机制

虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作wait(S)和signal(S)。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。

代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源 管理程序，共同构成了一个操作系统的资源管理模块，我们称之为管程。

管程被请求和释放资源的进程所调用。

Hansan为管程所下的定义是：“一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据”。

管程由四部分组成：

①管程的名称。

②局部于管程内部的共享数据结构说明。

③对该数据结构进行操作的一组过程。

④对局部于管程内部的共享数据设置初始值的语句。

管程相当于围墙，它把共享变量和对它进行操作的若干过程围了起来，所有进程要访问临界资源时，都必须经过管程(相当于通过围墙的门)才能进入，而管程每次只准许一个进程进入管程，从而实现了进程互斥。

条件变量

对条件变量的操作仅仅是 wait 和 signal，因此条件变量也是一种抽象数据类型，每个条件变量保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作即可表示为x.wait和x.signal，其含义为：

①x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其它进程可以使用该管程。

②x.signal：正在调用管程的进程发现x条件发生了变化，则调x.signal，重新启动一个因x条件而阻塞或挂起的进程。如果存在多个这样的进程，则选择其中的一个，如果没有，则继续执行原进程，而不产生任何结果。

经典进程同步问题（使用信号量方法解决）

生产者-消费者问题

①利用记录型信号量

②利用AND信号量

③利用管程

哲学家进餐问题

①利用记录型信号量

考虑到如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。

为了防止死锁的发生，可以设置两个条件：

必须同时拿起左右两根筷子；

只有在两个邻居都没有进餐的情况下才允许进餐。

②利用AND信号量机制。

读者-写者问题

①利用记录型信号量

②利用信号量集机制

进程通信

进程同步与进程通信很容易混淆，它们的区别在于：

进程同步：控制多个进程按一定顺序执行；

进程通信：进程之间的信息交换。

进程通信是一种手段，而进程同步是一种目的。

也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。 进程通信的类型

共享存储器系统

因为数据不需要在进程之间**，所以这是最快的一种 IPC。

①基于共享数据结构的通信方式。低效，只适于传递相对少量的数据。

②基于共享存储区的通信方式。高级通信方式。

消息传递系统

在该机制中，进程间的数据交换是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用操作系统提供的一组通信命令(原语)，实现大量数据的传递。

分为直接通信方式和间接通信方式

管道通信系统

“管道”（pipe）是指用于连接一个读进程和一个写进程以实现彼此间通信的一个共享文件，又名pipe文件。

它具有以下限制： 只支持半双工通信（单向交替传输）； 只能在父子进程中使用。

FIFO也称为命名管道，去除了管道只能在父子进程中使用的限制。

消息缓冲队列通信机制

发送进程利用Send原语将消息直接发送给接收进程；接收进程则利用Receive原语接收消息。

相比于 FIFO，消息队列具有以下优点： 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难； 避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法； 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

信号量

它是一个计数器，用于为多个进程提供对共享数据对象的访问。

线程

线程与进程的比较

①调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

②并发性

不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行。

③拥有资源

进程都可以拥有资源，是系统中拥有资源的一个基本单位。一般而言，线程自己不拥有系统资源(也有一点必不可少的资源)，但它可以访问其隶属进程的资源。

④系统开销

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

线程间的同步和通信

互斥锁；

条件变量；

信号量机制。

①私有信号量：实现同一进程中各线程之间的同步，属于特定的进程所有，OS并不知道私用信号量的存在。

②公有信号量：实现不同进程间或不同进程中各线程之间的同步，由OS为它分配空间并进行管理，是一种比较安全的同步机制。

线程的实现方式

①内核支持线程

在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等也是依靠内核，在内核空间实现的。

②用户级线程

仅存在于用户空间中。对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。

第三章 处理机调度与死锁

处理机调度的层次

①高级调度

高级调度又称为作业调度或长程调度，其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存，也就是说，它的调度对象是作业。

作业：通常的程序、数据和作业说明书。

作业控制块 JCB：保存了系统对作业进行管理和调度所需的全部信息。

②低级调度

通常也把低级调度(Low Level Sche*ng)称为进程调度或短程调度(ShortTerm Sche*ng)，它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的 OS 中，都必须配置这级调度。

低级调度的功能

保存处理机的现场信息、按某种算法选取进程、把处理机分配给进程

进程调度中的三个基本机制

排队器、分派器（分派任务）、上下文切换机制

进程调度方式

非抢占方式

实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。

抢占方式

抢占方式的优点是，可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。但抢占方式比非抢占方式调度所需付出的开销较大。

进程调度原则

优先权原则、段作业（进程）优先原则、时间片原则。

③中级调度

中级调度(Intermediate Level Sche*ng)又称中程调度(Medium-Term Sche*ng)。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重新具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度实际上就是存储器管理中的对换功能。

调度队列模型

①仅有进程调度的调度队列模型

②具有高级和低级调度的调度队列模型

③同时具有三级调度的调度队列模型

选择调度方式和调度算法的若干准则

面向用户的准则：周转时间短、响应时间快、截止时间的保证、优先权准则面向系统的准则：系统吞吐量高、处理机利用率好、各类资源的平衡利用。

调度算法

在 OS 中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。

①先来先服务调度算法

FCFS 算法比较有利于长作业(进程)，而不利于短作业(进程)。FCFS 调度算法有利于 CPU 繁忙型的作业，而 不利于 I/O 繁忙型的作业(进程)。CPU 繁忙型作业是指该类作业需要大量的 CPU 时间进行 计算，而很少请求 I/O。通常的科学计算便属于 CPU 繁忙型作业。I/O 繁忙型作业是指 CPU 进行处理时需频繁地请求 I/O。目前的大多数事务处理都属于 I/O 繁忙型作业。

②短作业(进程)优先调度算法

SJF 调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。

③高优先权优先调度算法

优先权调度算法的类型

非抢占式优先权算法

主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。

抢占式优先权调度算法

常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。

优先权的类型

①静态优先权

静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变

②动态优先权

动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。

高响应比优先调度算法

既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。

Rp优先级 =（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间

基于时间片的轮转调度算法

时间片轮转法

就绪队列中的所有进程在给定的时间内均能获得一时间片的处理机执行时间。

时间片大小的确定：时间片略大于一次典型的交互所需要的时间

多级反馈队列调度算法

①应设置多个就绪队列，并为各个队列赋予不同的优先级、不同大小的执行时间片。在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。

②当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。

③仅当第一队列空闲时，调度程序才调度第二队列中的进程运行。

实时调度

实现条件

①提供必要的信息

②系统处理能力强

③采用抢占式调度机制

④具有快速切换机制

分类

①非抢占式调度算法

非抢占式轮转调度算法、非抢占式优先调度算法

②抢占式调度算法

基于时钟中断的抢占式优先权调度算法

常用的几种实时调度算法

最早截止时间优先即EDF(Earliest Deadline First)算法

根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。

最低松弛度优先即LLF(Least Laxity First)算法

根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高，以使之优先执行。 产生死锁的原因和必要条件

死锁(Deadlock)，是指多个进程在运行 过程中因争夺资源而造成的一种僵局。

产生死锁的原因可归结为如下两点：

①竞争资源。

②进程间推进顺序非法。

产生死锁的必要条件：

①互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源 的进程用毕释放。

②请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

③不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

④环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链。处理死锁的基本方法

①鸵鸟策略

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。 当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。 大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

②预防死锁

通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。

③避免死锁

在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。

④检测死锁与解除死锁

检测死锁允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后，采取适当措施，从系统中将已发生的死锁清除掉。

解除死锁常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。预防死锁的方法预防死锁

使四个必要条件中的第2、3、4个条件之一不能成立，来避免发生死锁。至于必要条件1，因为它是由设备的固有特性所决定的。

①破坏“请求和保持”条件：破坏请求：系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。破坏保持：分配资源时，只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，而让该进程等待。

②破坏“不可抢占”条件：当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。

③破坏“循环等待”条件：系统将所有资源按类型进行线性排队，并赋予不同的序号。系统安全状态

所谓安全状态，是指系统能按某种进程顺序(P1，P2，…，Pn)(称〈P1，P2，…，Pn〉序 列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态是安全的。 定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。 安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

利用银行家算法避免死锁

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的E、P以及A分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示4个资源分别还剩下1/0/2/0。 检查一个状态是否安全的算法如下： – 查找右边的矩阵是否存在一行小于等于向量A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。 – 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到A中。 – 重复以上两步，直到所有进程都标记为终止，则状态时安全的。 如果一个状态不是安全的，需要拒绝进入这个状态。

死锁的检测与解除

死锁的检测

S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。

死锁的解除

①剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。

②撤销进程。最简单的撤消进程的方法是使全部死锁进程都夭折。

第四章 存储器管理

存储器的层次结构

①CPU寄存器：寄存器 ②主存（内存）：高速缓存、主存储器、磁盘缓存 ③辅存：固定磁盘，可移动存储介质 寄存器和主存储器又被称为可执行存储器。

操作系统的存储管理，负责对可执行存储器的分配、回收以及提供在存储层次间数据移动的管理机制程序的装入和链接

将一个用户源程序变为一个可在内存中执行的程序，通常都要经过以下几个步骤：

①编译，由编译程序将用户源代码编译成若干个目标模块；

②链接，由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块；

③装入，由装入程序将装入模块装入内存。

程序的装入

①绝对装入方式（单道程序环境）

编译时知道程序将驻留在内存的位置，将产生绝对地址（即物理地址）的目标代码。绝对装入程序按照已知地址将装入模块装入内存，不需对地址修改。

②可重定位装入方式

装入时，对目标程序中指令和数据的各地址重定位（虚拟地址到内存地址映射）。（静态重定位）

③动态运行时装入方式

在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。

程序的链接

①静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。

②装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。

③运行时动态链接。这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。（可加快程序的装入过程，且可节省大量的内存空间）

连续分配管理方式

①单一连续分配

（单道程序环境下）将内存分为系统区和用户区，系统区仅供OS使用，用户区仅装用户程序（独占）。

②固定分区分配

（多道程序环境下）将整个用户空间划分为若干个固定大小的区域。被划分几个分区便允许几个程序并发运行而不会互相干扰。

③动态分区分配

根据进程的实际需要，动态地为之分配内存空间。

数据结构：空闲分区表、空闲分区链。

分区分配算法

顺序搜索法

首次适应算法

要求空间分区链以地址递增的次序链接。分配内存时，从链首开始顺序查找，直至大小满足要求，按照作业大小从该空闲分区划分内存空间给请求者，余下的空闲空间留在空闲链中。

循环首次适应算法

从上次找到的空闲分区的下一个空闲分区开始查找。设置起始查寻指针，用于指示下一次起始查寻的空闲分区，采用循环查找方式。

最佳适应算法

要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。（容易形成许多难以利用的碎片）

最坏适应算法

扫描整个空闲分区表或链表，挑选一个最大的空闲区，分割一部分存储空间给作业使用。

快速适应算法（分类搜索法）

将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，空闲分区的分类是根据进程常用的空间大小进行划分，

分区分配操作：分配内存、回收内存。

④可重定位分区分配

系统对内存进行“紧凑”使若干程序移位，用该程序在内存的新起始地址去置换原来的起始地址。（获得新起始地址——动态重定位：系统中增设一个重定位寄存器存放程序和数据在内存的起始地址，程序执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的）。

对换

是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。

在具有对换功能的OS中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。文件区采取离散分**式。对换区采用连续分**式。 基本分页存储管理方式

连续分**式形成的许多“碎片”，不进行“紧凑”，利用离散的方式，将一个进程直接分散地装入到许多不相邻接的分区中。

①页面与页表

分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从 0开始，如第 0 页、第 1 页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)。

地址结构：前一部分为页号P，后一部分为位（偏）移量W（页内地址）。

系统应能保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统又为每个进程建立了一张页面映像表，简称页表。实现从页号到物理块号的地址映射。

②地址变换机构

实现从逻辑地址到物理地址的转换。实际上只是将逻辑地址中的页号，转换为内存中的物理块号。借助于页表来完成。

基本的地址变换机构

页表大多驻留在内存中。在系统中只设置一个页表寄存器 PTR(Page-Table Register)，在其中存放页表在内存的始址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的 PCB 中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。

具有快表的地址变换机构

为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或称为“快表”，用以存放当前访问的那些页表项。 基本分段存储管理方式

①分段系统的基本原理

作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。

分段地址中的地址结构：段号-段内地址

段表：记录了该段在内存中的起始地址和段的长度。用于实现从逻辑段到物理内存去的映射。

地址变换机构 逻辑地址中的段号S与段表长度TL比较。若S>TL，段号太大，访问越界，产生越界中断信号。若S<TL，未越界，根据段表始址和该段段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。检查比较段内地址d和该段的段长SL。若d>SL，发出越界中断信号。若d<SL，未越界，段基址+段内地址=要访问的内存物理地址。

分页和分段的区别

页是信息的物理单位，分页系统是系统管理的需要。段是信息的逻辑单位，分段系统是为满足用户的需要。 – 页的大小固定且由系统决定。 段的长度不固定，决定于用户所编写的程序，根据信息的性质划分的。 – 分页的用户程序地址空间是一维的。分段的用户程序地址空间是二维的。分段是用户的行为，程序员标示一个地址时，既需给出段名，也需给出段内地址。

分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

分段系统的一个突出优点，是易于实现段的共享，即允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。

②段页式存储管理方式

分页和分段存储管理方式都各有其优缺点。分页系统能有效地提高内存利用率，而分段系统则能很好地满足用户需要。

基本原理

段页式系统的基本原理，是分段和分页原理的结合，程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页，并为每一个段赋予一个段名。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

其地址结构由段号、段内 页号及页内地址三部分所组成。

虚拟存储器的基本概念

虚拟存储器(内存)的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。 为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。 从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

局部性原理

程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。

时间局限性

典型原因是由于在程序中存在着大量的循环操作。

空间局限性

典型情况是程序的顺序执行。

虚拟存储器

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。

虚拟存储器的特征

①多次性

多次性是指一个作业被分成多次调入内存运行，亦即在作业运行时没有必要将其全部装入，只需将当前要运行的那部分程序和数据装入内存即可；以后每当要运行到尚未调入的那部分程序时，再将它调入。

②对换性

对换性是指允许在作业的运行过程中进行换进、换出，亦即，在进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区(换出)，待以后需要时再将它们从外存调至内存(换进)；甚至还允许将暂时不运行的进程调至外存，待它们重又具备运行条件时再调入内存。换进和换出能有效地提高内存利用率。

③虚拟性

虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。实现小内存运行大作业，改善内存利用率，提高并发程度，增加系统吞吐量。

虚拟存储器的实现方法

虚拟存储器的实现，都毫无例外地建立在离散分配的存储管理方式的基础上。

①请求分页系统

硬件支持

请求分页的页表机制

请求页表增加四个字段作为请求分页的数据结构。请求分页系统中页表诸项：页号、物理块号、状态位P、访问字段A、修改位M、外存地址。

缺页中断机构

每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。

地址变换机构

在分页系统地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能而形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。

实现请求分页的软件：在硬件的支持下，将程序正在运行时所需的页面(尚未在内存中的)调入内存，再将内存中暂时不用的页面从内存置换到磁盘上。

②请求分段系统

硬件支持：请求分段的段表机制、缺段中断机构、地址变换机构

内存分配策略和分配算法

①最小物理块数的确定。

②物理块的分配策略 固定分配局部置换可变分配全局置换可变分配拒不置换

③物理块的分配算法

平均分配算法按比例分配算法考虑优先权的分配算法

调页策略

①调入页面的时机

预调页策略

如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页更高效些。

请求调页策略

当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由OS将其所需页面调入内存。

②确定从何处调入页面

全部从对换区调入所需页面不会被修改的文件都直接从文件区调入，那些可能被修改的部分，从对换区调入。Unix方式。未运行过的页面从文件去调入，曾经运行过但又被换出的页面，从对换区调入。

页面调入过程

每当程序所要访问的页面未在内存（存在位为“0”）。

①向CPU发缺页中断。

②中断处理程序保留CPU环境去分析中断原因。

③转入缺页中断处理程序。

④通过查找页表得到该页所在外存物理块。

⑤若内存未满，启动磁盘I/O，调该缺页入内存，修改页表。

⑥若内存已满，置换算法将内存中一页换出，调该缺页入内存，修改页表，置该页面存在位为“1”，页表项写入快表。

页面置换算法

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

①最佳置换算法

其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。

②先进先出(FIFO)页面置换算法

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算**将那些经常被访问的页面也被换出，从而使缺页率升高。

③最近最久未使用(LRU)置换算法

选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

硬件支持：寄存器和栈。

④Clock置换算法

循环地检查各页面的使用情况。

⑤最少使用（LFU）置换算法

在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。

⑥页面缓冲算法(PBA)

将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中；否则，便放入已修改页面的链表中。

当有一个未被修改的页要换出时，实际上并不将它换出内存，而是把该未被修改的页所在的物理块挂在自由页链表的末尾。类似地，在置换一个已修改的页面时，也将其所在的物理块挂在修改页面链表的末尾。利用这种方式可使已被修改的页面和未被修改的页面都仍然保留在内存中。当该进程以后再次访问这些页面时，只需花费较小的开销，使这些页面又返回到该进程的驻留集中。

请求分段存储管理方式

硬件支持

①段表机制

段表项中增加了增补位。这是请求分段式管理中所特有的字段，用于表示本段在运行过程中是否做过动态增长。

②缺段中断机构

段不是定长的，这使对缺段中断的处理要比对缺页中断的处理复杂。

③地址变换机构

因为被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能再利用段表进行地址变换。

分段的共享与保护

①共享段表

共享进程计数count、存取控制字段、段号。

②共享段的分配与回收

③分段保护 越界检查（逻辑地址空间的段号与段表长度进行比较，段内地址与段长进行比较）。存取控制检查。环保护机构（一个程序可以访问驻留在相同环或较低特权环中的数据，一个程序可以调用驻留在相同环或较高特权环中的服务）。

第五章 设备管理

I/O系统

设备控制器

设备控制器是计算机中的一个实体，其主要职责是控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换。

设备控制器的基本功能

①接收和识别命令：相应的控制寄存器，存放接收的命令和参数，进行译码。 ②数据交换：CPU与控制器之间、控制器与I/O设备之间，数据交换。 ③标识和报告设备的状态：控制器记录设备的状态供CPU了解。 ④地址识别：控制器中配置地址译码器，识别其所控制的设备的地址。 ⑤数据缓区：主机速率高，I/O设备速率低，暂存数据匹配速率再进行数据传送。 ⑥差错控制：I/O设备传来的数据，设备控制器进行差错检测，若错，将差错检测码置位，并向CPU报告，CPU处理，数据作废，重新传送。

I/O通道

I/O通道处于CPU和设备控制器之间，是一种特殊的处理机，它具有执行I/O指令的能力，并通过执行通道(I/O)程序来控制I/O操作。指令类型单一、通道与CPU共享内存。

通道类型

①字节多路通道

按字节交叉方式工作的通道。

②数组选择通道

按数组方式进行数据传送，

③数组多路通道

将数组选择通道传输速率高和字节多路通道能使各子通道(设备)分时并行操作的优点相结合而形成的一种新通道。数据传送是按数组方式进行的。

总线系统

在计算机系统中的各部件，如 CPU、存储器以及各种I/O设备之间的联系，都是通过总线来实现的。总线的性能是用总线的时钟频率、带宽和相应的总线传输速率等指标来衡量的。 I/O控制方式

①程序I/O方式（不断循环测试状态寄存器中的忙/闲标志busy）

②中断驱动I/O控制方式（CPU中断处理，I/O设备可与CPU并行工作）

③直接寄存器访问（DMA）I/O控制方式（数据传输的基本单位是数据块，所传送的数据是从设备直接送入内存的或者相反，仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的）

④I/O通道控制方式

DMA方式的发展，进一步减少CPU的干预，把对一个数据块的 读(或写)为单位的干预减少为对一组数据块的读(或写)及有关的控制和管理为单位的干预。实现CPU、通道、I/O设备三者的并行操作。缓冲管理

引入缓冲区的原因

①缓和CPU与I/O设备间速度不匹配的矛盾。

②减少对CPU的中断频率，放宽对CPU中断响应时间的限制。

③提高CPU和I/O设备之间的并行性。

单缓冲

在单缓冲情况下，每当用户进程发出一I/O请求时，操作系统便在主存中为之分配一缓冲区。

双缓冲

实现双向传输。一个用作发送缓冲区，另一个用作接收缓冲区。

循环缓冲

当输入与输出或生产者与消费者的速度相差甚远时，可将多个缓冲组织成循环缓冲形式。使输入进程和计算进程并行执行。可能出现系统受计算限制（输入进程阻塞）和系统受I/O限制（计算进程阻塞）。

缓冲池

提高缓冲区的利用率，既可用于输入又可用于输出的公用缓冲池。 I/O软件

I/O软件的总体设计目标是高效率和通用性。前者是要确保I/O设备与CPU的并发性，以提高资源的利用率；后者则是指尽可能地提供简单抽象、清晰而统一的接口，采用统一标准的方法，来管理所有的设备以及所需的I/O操作。

I/O系统的层次及功能

用户层软件

实现与用户交互的接口。

设备独立性软件

负责实现与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。

设备驱动程序

与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序。

中断处理程序

用于保存被中断进程的 CPU 环境，转入相应的中断处理程序进行处理，处理完后再恢复被中断进程的现场后返回到被中断进程

硬件

执行I/O操作。

中断处理程序的处理过程

①唤醒被阻塞的驱动（程序）进程

②保护被中断进程的CPU环境 ③转入相应的设备处理程序 ④中断处理

⑤恢复CPU的现场并退出中断

设备驱动程序

是I/O进程与设备控制器之间的通信程序。

设备驱动程序的功能

①接收由设备独立性软件发来的命令和参数，并将命令中的抽象要求转换为具体要求。

②检查用户 I/O 请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式。

③发出I/O命令。如果设备空闲，便立即启动I/O设备去完成指定的I/O操作；如果设备处于忙碌状态，则将请求者的请求块挂在设备队列上等待。

④及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行处理。

⑤对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序。

设备独立性软件

设备无关性：应用程序独立于具体使用的物理设备。

设备独立性软件的主要功能

①执行所有设备的公有操作。

②向用户层（或文件层）软件提供统一接口。设备分配

设备分配中的数据结构

设备控制表、控制器控制表、通道控制表和系统设备表

设备分配时应考虑的因素

①设备的固有属性

对独占、共享、可虚拟三种设备应采取不同的分配策略。

②设备分配算法

先来先服务、优先级高者调用。

③设备分配中的安全性

安全分**式、不安全分**式

SPOOLing技术

利用一道程序模拟脱机输入时的外围控制机功能，把低速I/O设备的数据传送到高速磁盘上（脱机输入），再利用另一道程序脱机输出时的外围控制机功能，把高速磁盘的数据传送到低速输出设备上（脱机输出）。。这样，便可在主机的直接控制下，实现脱机输入、输出功能。此时的外围操作与CPU对数据的处理同时进行，我们把这种在联机情况下实现的同时外围操作称为 SPOOLing，或称为假脱机操作。

SPOOLing系统的组成

①输入井和输出井

②输入缓冲区和输出缓冲区

③输入进程SPi和输出进程SPo

SPOOLing系统的特点

①提高了I/O的速度。

②将独占设备改造为共享设备。

③实现了虚拟设备功能。 磁盘存储器的管理

磁盘结构

盘面（Platter）：一个磁盘有多个盘面； 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道； 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小； 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）； 制动手臂（Actuator arm）：用于在磁道之间移动磁头； 主轴（Spindle）：使整个盘面转动。

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

寻道时间（制动手臂移动，使得磁头移动到适当的磁道上） 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上） 实际的数据传输时间 其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。 ①先来先服务

这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。仅适用于请求磁盘I/O的进程数目较少的场合。

②最短寻道时间优先

要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

③扫描算法

该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了SSTF的饥饿问题。

④循环扫描算法

CSCAN算法规定磁头单向移动。将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。

⑤NStepSCAN和FSCAN调度算法

NStepSCAN算法

N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按 FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。当正在处理某子队列时，如果又出现新的磁盘 I/O请求，便将新请求进程放入其他队列，这样就可避免出现粘着现象。

FSCAN算法

FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。

磁盘高速缓存

磁盘高速缓存的形式

磁盘高速缓存是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。这里的高速缓存是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。

数据交付方式

数据交付是指将磁盘高速缓存中的数据传送给请求者进程。（数据交付、指针交付）。

置换算法

最近最久未使用算法LRU、最近未使用算法NRU及最少使用算法LFU。

除了考虑到最近最久未使用这一原则外，还考虑了以下几点：

访问频率、可预见性、数据一致性。

周期性地写回磁盘

在UNIX系统中专门增设了一个修改(update)程序，使之在后台运行，该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。

提高磁盘I/O速度的其它方法

①提前读

用户(进程)对文件进行访问时，经常采用顺序访问方式，即顺序地访问文件各盘块的数据。在这种情况下，在读当前块时可以预知下一次要读的盘块。因此，可以采取预先读方式，即在读当前块的同时，还要求将下一个盘块(提前读的块)中的数据也读入缓冲区。

②延迟写

延迟写是指在缓冲区A中的数据，本应立即写回磁盘，但考虑到该缓冲区中的数据在不久之后可能还会再被本进程或其它进程访问(共享资源)，因而并不立即将该缓冲区 A 中的数据写入磁盘，而是将它挂在空闲缓冲区队列的末尾。当该缓冲区A仍在队列中时，任何访问该数据的进程，都可直接读出其中的数据而不必去访问磁盘。

③优化物理块的分布

使磁头的移动距离最小。

④虚拟盘

所谓虚拟盘，是指利用内存空间去仿真磁盘，又称为RAM盘。虚拟盘的主要问题是：它是易失性存储器。与磁盘高速缓存的主要区别在于: 虚拟盘中的内容完全由用户控制，而高速磁盘缓存中的内容则是由OS控制的。

廉价磁盘冗余阵列

它是利用一台磁盘阵列控制器，来统一管理和控制一组(几台到几十台)磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。磁盘阵列采取并行交叉存取。