二、 操作系统运行环境

2.1 处理器

2.1.1 处理器的构成与基本工作方式

处理器一般由运算器、控制器、一系列的寄存器以及高速缓存构成。

2.1.1.1 寄存器

处理器中通常有两类寄存器：用户可见寄存器、控制和状态寄存器。

其中用户可见寄存器一般包括：数据寄存器、地址寄存器、条件码寄存器。

常见的控制和状态寄存器有：程序计数器(Program Counter，PC)、指令寄存器（Instruction Register，IR）、程序状态字（Program Status Word，PSW）。

2.1.2 特权指令和非特权指令

特权指令是指那些只能由操作系统使用的指令。用户只能使用非特权指令。

如果一个用户程序需要使用特权指令，一般将引起一次处理器状态的切换，通过移交处理权给操作系统中一段特殊代码，这个过程称为陷入（Trap）。

2.1.3 处理器工作状态

2.1.3.1 分为管态和目态

处理器处于管态时可以使用全部指令（包括特权和非特权）。目态又称用户态，只有非特权指令能执行。

2.1.3.2 处理器工作状态的转换

1. 唯一的途径是通过中断
2. 通过设置PSW指令（修改程序状态字），实现从操作系统向用户程序的转换。

2.1.4 程序状态字（PSW）

用一个专门的寄存器来指示处理器状态，成为程序状态字（PSW）；用程序计数器（PC）这个专门的寄存器来指示下一条要执行的指令。

2.2 计算机系统硬件部件

中央处理器（CPU）能直接访问的唯一的存储空间是内存储器，操作系统本身也存储在内存中并运行。

2.2.1 存储系统

2.2.1.1 存储器的类型

可分为两类：一种是读写型的存储器，另一种是只读型的存储器。

读写型的存储器常被称为随机访问存储器（Random Access Memory，RAM）。RAM主要用作存储随机存取的程序的数据。

只读存储器（Read-Only Memory，ROM）使用特殊的方法写入数据。有些也可以用特殊的方法擦去，重新写入。

存储的最小单位成为“二进位”。存储器的最小编址单位是字节，一个字节包含8个二进位，而2个字节一般称为一个字，4个字节称为双字。

2.2.1.2 存储器的层次结构

计算机存储系统的设计主要考虑三个问题：容量、速度和成本。

从整个系统来看，在计算机系统中的层次化的存储体系是由寄存器、高速缓存、内存储器、硬盘存储器、磁带机和光盘存储器等装置构成的，他们的速度如下：寄存器>高速缓存>内存储器>硬盘存储器>磁带机和光盘存储器。

2.2.1.3 存储器保护

界地址寄存器是被广泛使用的一种存储保护技术。

其方法是在处理器种设置一对界限寄存器来存储用户作业在内存中的上限和下限地址，分别为下限寄存器和上限寄存器。每当处理器访问内存时，硬件自动进行比较，判断是否越界。如果未越界，则按此地址访问内存，否则产生程序中断-越界中断或称为存储保护中断。

2.2.2 I/O部件

2.1.2.1 I/O结构

早期的I/O设备控制器连接CPU，CPU定期轮询各个I/O设备控制器，效率太低，已经淘汰了。

2.2.2.2 通道

通道对外部设备实行统一的管理，它代替处理器对I/O操作进行控制，从而使处理器和外部设备可以并行工作。所以通道又称为I/O处理器。

采用通道这种I/O结构的最大优点是，可以实现中央处理器和各种外部设备并行工作。

2.2.2.3 DMA技术

直接存储器访问（Direct Memory Access，DMA）技术通过系统总线中的一个独立控制单元-DMA控制器，自动地控制成块数据在内存和I/O单元之间的传送。

DMA技术大大提高了处理I/O的效能。

2.2.2.4 缓冲技术

缓冲技术是用在外部设备与其他硬件部件之间的一种数据暂存技术，通过设置数据的一个存储区域，称为缓冲区。

采用缓冲技术最根本的原因是，处理器处理数据速度与设备传输数据速度不相匹配，需要缓冲区缓解其间的速度矛盾。为了提高设备利用率，通常使用单个缓冲区是不够的，可以设置双缓冲区，甚至多缓冲区。

2.2.3 时钟部件

时钟一般分成硬件时钟和软件时钟。

硬件提供的时钟比较少，不能满足要求，所以软件时钟是经常需要的。软件时钟与硬件时钟的同步工作由操作系统负责维护。

时钟的用途可分为绝对时钟和相对时钟。

2.3 中断机制

中断机制是操作系统中极为重要的一个部分。

由于中断机制的实现必须依靠相关的硬件支持，所有硬件中断装置是操作系统运行环境中一个极为重要的组成部分。

中断的实现是硬件中断装置和相应的中断处理软件共同完成的。

2.3.1 中断与异常的概念

中断是所有要打断处理器的正常工作次序，并要求其去处理某一事件的常用手段。

中断是由外部事件引发的，而异常则是由正在执行的指令引发的。

典型的中断包括：时钟中断、输入输出（I/O）中断、控制台中断、硬件故障中断。

典型的异常包括：程序性中断、访管指令异常（要求操作系统提供系统服务）。

2.3.2 中断系统

中断系统分为两大组成部分：中断系统中的硬件中断装置和软件中断处理程序。

在中断逻辑线路中有若干个专门接受中断信号的触发器，每个触发器称为一个中断位，这些触发器的全体称为中断寄存器，所以中断寄存器是由若干个中断位组成的。

中断请求的响应机制如下。处理器的控制部件中设有中断信号扫描结构，它在每条指令执行周期的最后时刻扫描中断寄存器，有中断则接受硬件中断装置发来的中断向量代号。

保存中断点的程序执行上下文环境又称保护现场。

处理器根据中断向量代号查询中断向量表，获得与该中断源相联系的中断处理程序的入口地址，并将PC置成该地址。随后控制权转移到中断处理程序。

中断信号的处理可以简单地归纳为：接受和响应中断，保护中断断点现场，分析中断向量，调用中断处理程序，中断处理结束恢复现场，原有程序继续执行。

2.3.3 中断优先级、中断屏蔽与中断嵌套

现代的微处理器都提供有多级中断系统，中断信号的级别代表了该中断信号是否具有被优先处理的特权，以及特权的大小。

属于机器故障中断这一类中断信号是不可屏蔽的。

中断嵌套即中断按照优先度分级，允许优先级较高的中断打断优先级较低的中断处理过程，于是引起中断处理的嵌套。在中断嵌套中，保护现场的次序，与恢复现场的次序正好相反，应采用堆栈作为现场保护区域。

2.4 系统调用

为了从操作系统中获得服务，用户程序必须使用系统调用（System Call）。

2.4.1 系统调用简介

所谓系统调用，就是用户在程序中调用操作系统所提供的一些子能力。

系统调用和函数调用的区别：①不同的系统状态，在系统调用中调用程序运行在目态，而被调用程序运行在管态。②状态转换：通过软中断机制由目态转换为管态。③返回问题。优先级高的进程优先执行。④嵌套调用，系统对嵌套深度有一定限制。

系统调用的分类：①进程控制类系统调用；②文件操作类系统调用；③进程通信类系统调用；④设备管理类系统调用；⑤信息维护类系统调用。

系统调用命令又称“广义指令”，它扩大了机器的指令系统，增强了处理器功能，为了区别于真实的物理处理器，我们称它为“虚处理器”。

应用程序接口（Application Programming Interface，API），又称应用编程接口，它是提供给应用程序调用使用的代码。

2.4.2 系统调用的处理过程

系统中为控制系统调用服务的机构称为陷入（Trap）或异常处理机构。

因为是通过陷入来使用系统调用，将CPU由目态切换为管态，所以在管态唯一不能执行的指令就是陷入。

如何实现用户程序和系统程序之间的参数传递？①陷入指令自带参数，指令长度有限，只能带几个参数。②通过通用寄存器传递参数，UNIX类操作系统常用这个办法。③内存中开辟专用堆栈区传递参数。

2.5 本章小结

​ 操作系统需要硬件运行环境的支持。可以把计算机系统看成一个层次式的结构，硬件系统位于计算机系统中的底层，软件系统分为系统软件、支撑软件和应用软件三个层次，其中操作系统在软件系统的最下层。

​ 处理器由运算器、控制器以及一系列的寄存器构成。最常见的控制寄存器有程序状态字(PSW)。在多用户或多任务的多道程序设计环境中，指令必须区分成特权指令和非特权指令，特权指令是指只能由操作系统使用的指令，用户只能使用非特权指令。操作系统管理程序运行的状态称为管态，一般用户程序运行时的状态称为目态。

​ 半导体存储器可划分为读写型和只读型的存储器。为了简化管理，以块为最小单位分配存储空间。存储系统主要考虑三个问题，容量、速度和成本。提高存储系统效能的关键在于程序的存储访问局部性原理。操作系统必须对内存中的信息加以严格的保护，存储保护机构是操作系统运行环境中的重要部分。在界地址寄存器方法中，设置了一对界地址寄存器存储作业在内存中的下限和上限地址，访问内存时，硬件将被访问的地址与界限寄存器的内容比较以防止越界。

​ 计算机系统中常使用通道以及直接存储器存取(DMA)等1/O技术。通道独立于中央处理器，它代替处理器对外部设备实行统一的管理，从而使处理器和外部设备并行工作，提高多道程序处理的效率。DMA技术由DMA控制器自动控制成块数据在内存和I/O单元之间的传送，提高了处理I/O的效能。缓冲技术是用以缓解处理器处理数据速度与设备传输数据速度不相匹配矛盾的一种数据暂存技术。

​ 计算机系统中的时钟可分为硬件时钟和软件时钟，以及绝对时钟和相对时钟。时钟可防止系统陷入死循环，实现作业按时间片轮转运行，给出正确的时间信号，定时唤醒事先按确定时间执行的事件，记录事项，等等。

​ 中断是指处理器对系统中或系统外发生的异步事件的响应。中断能充分发挥处理器的使用效率，提高系统的实时能力。中断可划分为强迫性中断和自愿性中断。中断系统包括硬件中断装置和中断处理程序。硬件中断装置接收中断信号，并把中断信号寄存在中断寄存器中；处理器的中断扫描机构在每条指令执行周期的最后时刻扫描中断寄存器。在多级中断中，中断的级别的高低标识了中断的紧急或者重要的程度，处理器接收中断优先级为最高的中断；如果有优先级相当的多个中断信号同时到达，可采用固定的优先数或表格轮转法依次处理。可通过对程序状态字PSW中设置中断屏蔽位的方法，以禁止或者允许对某些类别中断的响应。中断事件的处理需要硬件和软件两方面的配合，共同完成分辨和接收中断信号、保护现场、分析中断原因、调用中断处理程序进行处理、处理完毕恢复现场和原有程序继续执行的整个中断处理过程。如果在中断的处理过程中又发生了中断，将引起中断处理的嵌套。

​ 为了从操作系统中获得服务，用户程序必须使用系统调用，系统调用陷入内核并调用操作系统。系统调用和普通函数调用非常相似，二者区别在于，系统调用由操作系统内核实现，运行于管态；而函数调用由函数库或用户自己提供，运行于目态。系统调用是操作系统提供给编程人员的唯一接口。当用户使用操作系统调用时，通过使用访管指令产生中断，把目态切换成管态，并启用操作系统。访管指令包含对应系统调用的功能号。系统设计人员还必须为实现各种系统调用功能的子程序编造入口地址表，每个入口地址都与相应的系统程序名对应起来。然后，陷入处理程序把陷入指令中所包含的功能号与该入口地址表中的有关项对应起来，从而由系统调用功能号驱动有关子程序执行。当有关工作完成之后，在系统调用后面的指令把控制权返回给用户程序，系统调用的执行结果也要以参数形式返回给用户程序，可通过指令自带、寄存器、内存中专门的堆栈来传递。

三、 进程与线程

为了能够从技术上较为准确地描述正在运行、将要运行或者刚刚退出运行的各个程序的执行代码、数据以及所需的资源信息等，人们引进了进程(Process)这个概念。

3.1 多道程序设计

3.1.1 程序的顺序执行

把一个具有独立功能的程序独占处理器直到得到最终结果的过程称为程序的顺序执行。

程序的顺序执行具有如下特点。1.顺序性；2.封闭性；3.程序执行结果的确定性；4.程序执行结果的可再现性。

程序的顺序性和封闭性是一切顺序程序所应具有的特性。

3.1.2 程序的并发执行

程序并发执行，是指两个或两个以上程序在计算机系统中，同时处于已开始执行且尚未结束的状态。能够参与并发执行的程序称为并发程序。

程序的并发执行有如下特征。1.在执行期间并发程序相互制约； 2.程序与计算不再一一对应；3.并发程序的执行结果不可再现；4.程序的并行执行与程序的并发执行，这两者存在着差别。前者是指不论从宏观的时间周期上看，还是从微观上看，若干程序确实在同时运行；而程序的并发执行，如果在单处理器系统中，它们在宏观上是同时进行的，但在微观上，这些程序仍然是顺序执行的。

3.1.3 多道程序设计

为了提高计算机系统中各种资源的利用效率，缩短进程的周转时间，在现代计算机中广泛采用多道程序技术，使多种硬件资源能并行工作。

通常采用并行操作技术，使系统的各种硬件资源尽量做到并行工作。

多道程序设计，就是允许多个程序同时进入内存并运行。多道程序设计是操作系统所采用的最基本、最重要的技术，其根本目的是提高整个系统的效率。

衡量系统效率的尺度是系统吞吐量。所谓吞吐量是指单位时间内系统所处理进程(程序)的道数(数量)。

多道程序设计改善了各种资源的使用情况，从而增加了吞吐量，提高了系统效率，但也带来了资源竞争。因此，在实现多道程序设计时，必须协调好资源使用者与被使用资源之间的关系。

多道程序设计环境具有以下特点。(1)独立性。(2)随机性。 (3)资源共享性。

多道程序设计的缺陷：(1)可能延长程序的执行时间。(2)系统效率的提高有一定限度。

3.2 进程

3.2.1 进程的定义

进程是具有一定独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位。

从操作系统角度来看，可将进程分为系统进程和用户进程两类。

进程和程序的联系：程序是构成进程的组成部分之一，一个进程的运行目标是执行它所对应的程序。从静态的角度看，进程是由程序、数据和进程控制块(PCB)三部分组成的。

进程和程序的区别：程序是静态的，而进程是动态的。 进程是程序的一个执行过程。程序的存在是永久的(这里不讨论人为删除程序等行为)。而进程是为了程序的一次执行而暂时存在的。进程有生命周期，有诞生，亦有消亡。 一个进程可以包括若干程序的执行，而一个程序亦可以产生多个进程。

一个能够被多个用户同时调用的程序称作是“可再入”的程序。现代的操作系统及编译程序都是属于可再入程序，它们能同时被不同用户调用而形成不同的进程。

进程具有两个基本属性。1.进程是一个可拥有资源的独立单位；2.进程同时又是一个可以独立调度和分派的基本单位。

进程具有以下特性。(1)并发性；(2)动态性；(3)独立性；(4)交往性；(5)异步性；(6)结构性。

一个进程由程序、数据和进程控制块三部分组成。

3.2.2 进程的状态与转换

1. 三状态进程模型。运行中的进程可以处于以下三种状态之一：运行、就绪、等待。
2. 五状态进程模型。1、运行状态（Running）；2、就绪状态（Ready）；3、阻塞状态（Blocked）；4、创建状态（New）；5、结束状态（Exit）。
3. 七状态进程模型。七状态进程模型把原来的就绪状态和阻塞状态进行细分，增加了就绪挂起和阻塞挂起两个状态。是为了进一步区分进程的地址空间位于内存还是外存。

进程之间的转换	说明
就绪态→运行态	进程被调度
运行态→就绪态	时间片刻，或CPU被其他高优先级的进程抢占
运行态→阻塞态	等待系统资源分配，或等待某事件发生（主动行为）
阻塞态→就绪态	资源分配到位，等待的事件发生（被动行为）

3.2.3 进程控制块

为了便于系统控制和描述进程的活动过程，在操作系统核心中定义了一个专门的数据结构，称为进程控制块(Process Control Block，PCB)。

操作系统利用PCB来描述进程的基本情况以及进程的运行变化过程。PCB是进程存在的唯一标志。

1.进程控制块（PCB）的内容，可以分成调度信息和现场信息两大部分。调度信息供进程调度时使用，描述了进程当前所处的状况，它包括进程名、进程号、地址空间信息、优先级、当前状态、资源清单、“家族”关系、消息队列指针、进程队列指针和当前打开文件等。 现场信息刻画了进程的运行情况，PCB中的现场信息只记录那些可能会被其他进程改变的寄存器。

2.进程的组成。进程由程序、数据和进程控制块三部分组成。PCB是进程的“灵魂”，由于进程控制块中保存有进程的地址信息，通过PCB可以得到进程程序的存储位置，也可以找到整个进程。程序和数据是进程的“躯体”，程序部分描述了进程要实现的功能，而数据则是程序操作的对象。

3.进程控制块（PCB）组织方式。 (1)线性方式；(2)索引方式； (3)链接方式。

4.进程的队列分成三类。(1)就绪队列 ； (2)等待队列； (3)运行队列。

5.进程队列的组成。进程队列可以用进程控制块的链接来形成。常用链接的方式有两种：单向链接和双向链接。

3.2.4 进程控制

进程控制是指对进程在整个生命周期中各种状态之间的转换进行有效的控制。

用原语来实现进程控制。所谓原语，是由若干条指令所组成的一个指令序列，用来实现某个特定的操作功能。

原语是操作系统核心(由一组程序模块所组成的、完成操作系统中基本功能)的一个组成部分。原语必须在管态下执行，并且常驻内存。

原语的特点是执行期间不允许中断，只能一气呵成。这种不可被中断的操作即原子操作。

源于采用“关中断指令”和“开中断指令”实现。

用于进程控制的原语一般有：创建进程、撤销进程、挂起进程、激活进程、阻塞进程、唤醒进程以及改变进程优先级等。

3.3 线程

什么是线程？线程是处理器调度和分派的基本单位。

为什么引入线程？可以增加并发度，减少并发带来的开销。

3.3.1 进程和线程

线程具有许多传统进程所具有的特征，故又称轻量级进程（Ligth-Weight Process），而传统进程成为重量级进程（Heavy-Weight Process）。

进程和线程的区别。①、引入线程的操作系统中，把线程作为调度和分派的基本单位，把进程作为资源分配的基本单位；②线程提高了并发性；③同一个进程中的资源可供它属下的所有线程共享；④进程切换的开销远大于线程切换的开销，线程的切换、同步和通信可以无须操作系统内核的干预。

3.3.2 线程的实现机制

用户级线程。用户级线程不依赖于内核，只存在于用户态中，内核也不知道有用户级线程的存在。用户级线程中，线程的调度非常快捷。

内核级线程。内核级线程依赖于内核，在内核中保留一个线程控制块，系统根据控制块对线程进行控制。缺点是系统调用开销大。

3.3.3 进程调度

3.3.3.1 进程调度概念和层次

进程调度即处理机调度。就是按照某种算法选择一个进程将处理机分配给它。

分三个层次：①作业调度（高级调度），从后备队列选择合适的作业将其调入内存，并为其创建进程；②内存调度（中级调度），从挂起队列选择合适的进程将其数据调回内存；③进程调度（低级调度），从就绪队列中选择一个进程为其分配处理机。

三层调度的联系与区别。①作业调度，外存→内存（面向作业），发生频率低；②内存调度，外存→内存（面向进程），发生频率中等；③进程调度，内存→CPU，发生频率高。

3.3.3.2 进程调度的时机、切换与过程、方式

什么时候需要进程调度？

主动放弃	被动放弃
进程正常中止	分给进程的时间片用完
运行过程中发生异常而中止	有更紧急的事处理（如I/O中断）
主动阻塞（如等待I/O）	有更高优先级的进程进入就绪队列

进程调度的方式：①抢占式：可由操作系统剥夺当前进程的CPU使用权；②非抢占式：只能由当前运行的进程主动放弃CPU。

3.3.3.3 调度算法的评价指标

1. 周转时间（进程从提交到完成时刻的统计时间）=作业完成时间-到达时间。
2. 带权周转事件=作业周转时间÷作业运行时间
3. 等待时间=周转时间-运行时间。

3.3.3.4 进程调度算法

饥饿（Starvation）的概念，当短进程源源不断进入后备池，长进程将会长时间滞留在后备池中，这种现场称为长进程处于“饥饿”。

适用于批处理系统的三种算法：

1、先来先服务算法（First-Come First-Served，FCFS）。非抢占式，不饥饿。

2、最短进程优先算法（Shortest Job First，SJF），非抢占式；最短剩余时间优先算法（Shortest Remaining Time Next，SRTN），抢占式，可能饥饿。

3、最高响应比优先算法（Highest Response Rate First，HRRF）。非抢占式，不饥饿。响应比Rp=（等待时间+运行时间）/运行时间=周转时间/运行时间。

适用于交互式系统的调度算法：

1、时间片轮转算法（Round-Robin，RR）。将处理器的处理时间划分城一个个时间片，就绪队列中的诸进程轮流运行一个时间片。用于进程调度，抢占式，不饥饿。时间片不能太大也不能太小。优点：公平，响应快，适用于分时操作系统；缺点：有一定开销，不区分任务的紧急程度。

2、最高优先级算法（Highest Priority First，HPF）。每次将处理器分配给具有最高优先级的就绪程序。既可用于作业调度，也可用于进程调度，抢占、非抢占都有，可能饥饿。

3、多级反馈队列调度算法。综合了先进先出、时间片轮转和可抢占式最高优先级算法。①设计多级就绪队列，各级队列优先级从高到低，时间片从小到大；②新进程到达时先进入第1级队列，按先进先出（FCFS）原则等待被分配时间片，用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾；③只有第k级队列为空时，才会为k+1级队头的进程分配时间片用于进程调度。优点：很多，缺点：复杂，可能饥饿。

3.3.4 系统内核

为了提高系统运行效率、保护系统的关键部分，一般把操作系统中提供支持系统运行的各种基本操作和基础功能的一组程序模块集中安排，形成系统内核（Kernel）。

内核只占整个操作系统代码中的一小部分，是最接近裸机的部分。·系统内核本身不是进程，是系统进程和用户进程赖以活动的基础。系统内核常驻内存之中。

3.4 本章小结

​ 一个具有独立功能的程序独占处理器执行，直到得到最终结果的过程，是程序的顺序执行过程，具有顺序性、封闭性、执行结果的确定性和可再现性。程序并发执行，是指两个或两个以上程序在计算机系统中，同时处于已开始执行且尚未结束的状态。并发执行的程序相互制约，程序与计算不再一一对应，而且执行结果不可再现。多道程序设计是操作系统最基本、最重要的技术之一，多道程序设计改善了各种资源的使用情况，增加了吞吐量，提高了系统效率，但也带来了资源竞争，其特点是独立性、随机性和资源共享性；其缺点是可能延长程序的执行时间，对系统效率的提高有一定有限度。

​ 进程是具有一定独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位。进程和程序既有联系又有区别，从静态的角度看，进程是由程序、数据和进程控制块(PCB)三部分组成的；程序是静态的，而进程是动态的；一个进程可以包括若干程序的执行，而一个程序亦可以产生多个进程；进程具有创建其他进程的功能，从而可以构成进程家族。进程具有并发性、动态性、独立性、交往性和异步性。一个的进程可以处于运行、就绪和等待三种基本状态之中。随着进程自身的进展情况和外界环境条件的动态变化，一个进程的状态可以在三种基本状态中转换。

​ 操作系统利用PCB来描述进程的基本情况以及进程的运行变化过程，PCB是进程存在的唯一标志。PCB是进程的“灵魂”，由于进程控制块中保存有进程的地址信息，通过PCB可以得到进程程序的存储位置，也可以找到整个进程。程序和数据是进程的“躯体”，程序部分描述了进程要实现的功能，而数据则是程序操作的对象。通常，系统中进程队列分成就绪队列、等待队列和运行队列三类。进程队列可以用进程控制块的链接来形成，常用链接的方式有单向链接和双向链接。

​ 进程控制通过进程控制原语对进程在整个生命周期中各种状态之间的转换进行有效的控制。原语是操作系统核心的一个组成部分，必须在管态下执行，并常驻内存。用于进程控制的原语一般有创建进程、撤销进程、挂起进程、激活进程、阻塞进程、唤醒进程以及改变进程优先级等。

​ 线程是进程中的一个实体，是处理器调度和分派的基本单位。线程只拥有少量在运行中必不可少的资源，但共享所属进程所拥有的全部资源。线程可以提高系统内程序并发执行的级别，进一步提高系统效率。

​ 进程调度的任务是是记录系统中所有进程的执行状况，根据一定的调度算法，从就绪队列中选出一个进程，把处理器分配给它。处理器方式有不可抢占式和抢占式。进程调度算法的任务是对各个就绪的进程进行处理器分配，以达到预定的进程调度目标，算法应该合理、有效，尽可能提高资源利用率，并减少处理器空闲。常用的算法有先来先服务算法、时间片轮转算法、最短进程优先算法、最高响应比优先算法、最高优先级算法和多级队列反馈法等。选择进程调度算法时应该考虑处理器利用率、吞吐量、等待时间和响应时间等因素，并确定优先考虑的指标，在此基础上对各种算法进行评估，选出合适的算法。

​ 为了提高系统运行效率、保护系统的关键部分，把支持系统运行的各种基本操作和基础功能的一组程序模块集中安排，形成系统内核。一般而言，内核提供中断处理、进程同步与互斥、进程调度、控制与通信、存储管理的基本操作以及时钟管理等。内核只占整个操作系统代码中的一小部分，是最接近裸机的部分，内核是进程赖以活动的基础，内核的功能通过执行原语操作来实现。

四、 进程同步与互斥

4.1 进程间相互作用

在逻辑上具有某种联系的进程称为相关进程，在逻辑上没有任何联系的进程称为无关进程。

在并发程序中共享了公共变量，使得程序的计算结果与并发程序执行的速度有关，这种错误往往与时间有关，称为“与时间有关的错误”。

4.2 进程的同步与互斥

进程的同步是指进程之间一种直接的协同工作关系，一些进程相互合作，共同完成一项任务。进程之间的同步也是进程间的一种直接制约关系。能实现进程同步的机制称为“同步机制”。

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。临界资源一次只为一个进程服务，各进程间只能互斥的使用临界资源，这种关系就是进程的互斥。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

1. 有空让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
2. 无空等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
3. 多中择一。当多个进程要求进入临界区，只能让其中一个进入临界区，其他进程必须等待；
4. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
5. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

4.3 信号量及P、V操作

整型信号量：①用一个整数型变量作为信号量，数值表示某种资源数；②整型信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作；③整型信号量存在的问题：不满足让权等待原则

记录型信号量（一个整型变量附加一个队列）：①S.value表示某种资源数，S.L指向等待该资源的队列；②P操作中，一定是先S.value–，之后可能需要执行block原语；③V操作中，一定是先S.value++，之后可能需要执行 wakeup 原语；④注意：要能够自己推断在什么条件下需要执行blockA或 wakeup；⑤可以用记录型信号量实现系统资源的“申请“和“释放”；⑥可以用记录型信号量实现进程互斥、进程同步

PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：

P（S）：①将信号量S的值减1，即S=S-1；

②如果S>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。

V（S）：①将信号量S的值加1，即S=S+1；

②如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。

4.4 经典的进程同步问题

4.4.1 多个生产者-消费者问题

生产者和消费者之间存在同步和互斥关系。

算法如下：

//同步问题：1.生产者不能往“满”的缓冲区中放产品，设信号量为empty，初值为k，用于指示缓冲池中空缓冲区数目；2.消费者不能从“空”的缓冲区中取产品。，设置信号量为full，初值为0，用于指示缓冲池中满缓冲区数目。
//互斥问题：设信号量为mutex，初值为1，用于实现临界区的互斥。

//生产者进程P1,P2,....,Pn：
i=0;
while(true){
    生产产品;
    P(empty);
    p(mutex);
    	往Buffer[i]中放产品;
    	i=(i+1)%k;
    V(mutex);
    V(full);
};
//消费者进程Q1,Q2,....,Qm：
j=0;
while(true){
    P(full);
    p(mutex);
    	往Buffer[j]中取产品;
    	j=(j+1)%k;
    V(mutex);
    V(full);
    消费产品;
}; 
    

互斥的P操作一定要在实现同步的P操作之后。也就是一定要先同步P操作，再互斥P操作，否则可能造成“死锁”。

P、V问题先画图，遵循以下原则：①互斥：在临界区前后分别P、V；②同步：前V后P。

4.4.2 读者-写者问题

一个数据对象可以供多个进程共享。需要遵循以下规定：

1. 多个进程可以同时读文件。
2. 任一个进程在对文件进行写时，不允许其他进程对文件进行读或写。
3. 当有进程正在读文件时不允许任何进程去写文件。

显然，写者与写者互斥；读者与写者互斥，但第一个读者读了文件后，其他读者也可以跟着读，所以，写者与读者间的互斥变成写者与第一个读者之间的互斥。

//设read_count=0记录当前正在读的读者进程个数；多个读者访问read_count，需要互斥使用互，设信号量为mutex=1；写者互斥信号量write=1；
//为了防止读进程源源不断，产生写进程饥饿，设互斥信号量W=1；

//写者进程：
while(true){
    P(W);
    P(write);
    	写文件;
    V(write);
    V(W);
}

//读者进程：
while(true){
    P(W);
    P(mutex);
    	read_count=read_count+1;
    	if(read_count=1)
            P(write);
    V(mutex);
    V(W);
    	读文件;
    P(mutex);
    	read_count=read_count-1;
    	if(read_count=0)
            V(write);
    V(mutex);
}

4.4.3 吸烟者问题

4.5 管程

为什么要引入管程?解决信号量机制易读性差、程序不利于维护和修改、易出错的问题。

管程的组成：1.共享数据结构；2.对数据结构初始化的语句；3.一组用来访问数据结构的过程（函数）。

管程的重要特征：1.各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据；2.每次仅允许一个进程在管程内执行某个内部过程。

4.6 进程通信

进程之间的大量通信有三类解决方案：1、共享内存；2.消息机制；3.通过共享文件即管道通信。

4.7 本章小结

并发进程相互之间可能是无关的，也可能是相关的。如果一个进程的执行依赖其他进程的进展，或者一个进程的执行可能影响其他进程的执行结果，则这些并发进程是相关的。由于在并发程序中存在共享公共变量，使得程序的计算结果与并发程序执行的时间有关，这种“与时间有关的错误”需要依靠进程的同步处理解决。

进程同步是指进程之间一种直接的协同工作关系，是一些进程相互合作，共同完成一项任务。在系统中，许多进程需要共享资源，而这些资源往往要求排他性的使用，进程间的这种关系就是进程的互斥。若系统中某些资源一次只允许一个进程使用，则这类资源称为临界资源，而在进程中访问临界资源的程序称为临界区。系统对临界区的使用规则为有空让进、无空等待、多中择一、有限等待和让权等待。

设信号量为S可取不同的整数值，利用S的取值表示共享资源的使用情况。信号量S的物理含义是某类可用的临界资源。当S>0时，S值的大小表示该类资源可以分配的数量；当S<0时，表示没有可分配的资源数量，其S的绝对值表示排在S信号量的等待队列中进程的数目。对信号量S实施P、V操作的物理含义是，每执行一次P操作，意味着对请求的进程分配到一个资源；每执行一次V操作，意味着进程释放了一个资源。用P、V操作可实现进程之间的互斥和同步。P、V操作在使用时必须成对出现，有一个P操作就一定有一个V操作。P、V操作当为互斥操作时，它们位于同一进程；当为同步操作时，则不在同一进程中出现。生产者——消费者问题和读者——写者问题是进程同步互斥的两个经典例子。

信号量及P、V操作一种有效处理进程同步互斥问题的机制，但是在使用不正确时会导致一些错误且难以检测出来。为此提出了管程机制。管程定义了一个共享变量的数据结构以及在该数据结构上所执行的一组操作，只有使用这些操作才能修改共享变量。典型的管程设计方案是Hoare管程。

P、V操作不能承担进程间大量信息的交换任务，解决进程间的大量信息通信的问题有共享内存、消息缓冲通信、信箱通信以及管道通信方式。共享内存方式在相互通信的进程之 间设有一个公共内存区，一组进程向公共内存中写，另一组从公共内存中读，从而实现两组进程间的信息交换。消息缓冲通信方式根据“生产者——消费者”原理，利用内存中公用消息缓冲区实现进程之间的信息交换，为实现消息缓冲通信，要利用发送原语send和接收原语receive。信箱通信方式设立信箱，通过发送信件以及接收回答信件实现进程间通信。管道通信通过连接两个进程之间的一打开的共享文件，进行进程间通信，管道通信的基础是文件系统。

五、 死锁

5.1 死锁的产生

死锁是指一组进程中每一个进程均无限期地等待被该组进程中的另一个进程所占用且永远不会释放的资源。

死锁、饥饿、死循环的区别：

1. 死锁：死锁进程的个数至少为两个，死锁进程处于阻塞态；
2. 饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪；
3. 死循环：可能只有一个进程发生死循环，死循环进程可上处理机；
4. 死锁和饥饿是操作系统要解决的问题，死循环是程序员要解决的。

死锁产生的原因：一是竞争资源，系统资源在分配时出现失误，进程间对资源的相互争夺而造成僵局；二是多道程序运行时，进程推进顺序不合理。

死锁产生的四个必要条件：一是互斥条件，对必须互斥使用的资源的争抢才会导致死锁；二是不可剥夺条件，进程保持的资源只能主动释放，不可强行剥夺；三是请求和保持条件，保持着某些资源不放的同时，请求别的资源；四是循环等待条件，形成一种进程资源的循环等待链。

解决死锁的方法：一是预防死锁；二是避免死锁；三是检测与解除死锁；四是忽略死锁。

5.2 死锁预防

死锁预防的基本思想是防患于未然。

在预防死锁的静态分配策略中，可以采用以下方法：

1. 破坏互斥条件。临界资源改为可共享使用的资源。缺点：可行性不高，很多时候无法破坏互斥条件。
2. 破坏不可剥夺条件。方案1：申请资源得不到满足时，立刻释放拥有的所有资源；方案2：申请的资源被其他进程占用时，操作系统根据优先级协助剥夺。缺点：实现复杂、剥夺资源导致部分工作失效、系统开销大、可能导致饥饿；
3. 破坏请求和保持条件：运行前分配好所需要的资源，然后一直保持。缺点：资源利用率低、可能导致饥饿；
4. 破坏循环等待：采用资源的有序分配法，给资源编号，必须按照编号从小到大的顺序申请资源。缺点：不方便增加新设备、导致资源浪费、用户编程麻烦。

5.3 死锁避免

死锁避免的基本思想时：系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配。

安全序列是指，如果系统按照这种序列分配资源，则每个进程都能顺利完成。

安全状态的定义：如果操作系统能保证所有进程在有限时间内得到需要的全部资源，则称系统处于安全状态。不安全状态不一定导致死锁，而是有可能导致死锁。

银行家算法步骤：
①检查此次申请是否超过了之前声明的最大需求数
②检查此时系统剩余的可用资源是否还能满足这次请求
③试探着分配，更改各数据结构
④用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤：
检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
不断重复上述过程，看最终是否能让所有进程都加入安全序列。

5.4 死锁的检测与解除

如何检测？采用资源分配图和死锁检测算法来检测。

如何解除？1、资源剥夺法：使用挂起/激活机制挂起一些进程，剥夺它们占有的资源给死锁进程，以解除死锁，待条件成熟后，在激活被挂起的进程，设立检查还原点可以安全的释放资源；2、撤销进程：将它们占有的资源分配给另一些死锁进程，直到死锁解除为止。

5.4.1 资源分配图

资源分配图是一张有向图，其中有2种结点：1、进程结点用圆圈表示；2、方框表示每类资源结点；

资源分配图有2种边：1、分配边，从方框中的圆点引出，表明资源实例已被占有；2、申请边，从进程到资源的有向边。

死锁定理：1、如果资源分配图中没有环路，则系统没有死锁；2、如果资源分配图中出现环路，则系统中可能存在死锁。3、如果处于环路中的每个资源类中均只包含一个资源实例，则环路是死锁存在的充分必要条件。

5.4.2 资源分配图化简方法

化简方法：

1. 找出一个既非等待又非孤立的进程结点，获取它所需要的全部资源，运行后释放它占用的资源，然后再资源分配图中消去进程结点的所有申请边和分配边，使之称为既无申请边又无分配边的孤立结点；
2. 将释放的资源分配给申请它们的进程，并将申请边改为分配边；
3. 重复1、2过程，直到找不到符合条件的进程结点。
4. 若资源分配图是不可完全简化的，说明发生了死锁

6 本章小结

本章介绍了死锁的基本概念、发生死锁的原因、引起死锁产生的必要条件，然后讨论了解决死锁问题的各种方法。

所谓死锁是指在多道程序系统中，一组进程中的每一个进程均无限期地等待被该组进程中的另一个进程所占有且永远不会释放的资源，这种现象称系统处于死锁状态，简称死锁。处于死锁状态的进程称为死锁进程。

产生死锁的原因主要有两个：一是竞争资源，系统提供的资源数量有限，不能满足每个进程的需求；二是多道程序运行时，进程推进顺序不合理。系统中形成死锁一定同时保持了四个必要条件，即互斥使用资源、请求和保持资源、不可抢夺资源和循环等待资源。注意这四个条件是必要条件，而不是充分条件。解决死锁问题一般有三种方法。

(1)死锁预防。预先确定一些资源分配策略，进程按规定申请资源，系统按预定的策略进行分配，这些分配策略均能使产生死锁的四个必要条件中的一个条件不成立，从而使系统不会发生死锁。

(2)死锁避免。当进程提出资源申请时系统动态测试资源分配情况，仅当能确保系统安全时才把资源分配给进程。一个死锁避免常用的算法是著名的银行家算法，该算法将银行管理贷款的方法应用于操作系统资源管理中，可保证系统时刻处于安全状态，从而使系统不会发生死锁。银行家算法有些保守，并且在使用时必须知道每个进程对资源的最大需求量。

(3)死锁检测和解除。允许系统中发生死锁现象，即对资源的申请和分配不加任何限制，只要有剩余的资源就把资源分配给申请进程，因此，就可能出现死锁。但是，系统将不断跟踪所有进程的进展，定时运行一个“死锁检测程序”。若检测后没有发现死锁，则系统可以继续工作，若检测后发现系统有死锁，则可通过剥夺资源或撤销进程的方法解除死锁。当然，在解除死锁时要考虑到系统代价。

在一个实际的操作系统中要兼顾资源的使用效率和安全可靠，对不同的资源可采用不同的分配策略，往往采用死锁预防、避免和检测与解除的综合策略，以使整个系统能处于安全状态不出现死锁。

资源分配图是用有向图的方式描述系统状态。如果资源分配图中没有环路，则系统没有死锁。如果资源分配图中出现了环路，则系统中可能存在死锁。如果处于环路中的每个资源类中均只包含一个资源实例，则环路是死锁存在的充分必要条件。通过化简资源分配图可以判断系统中是否出现死锁。

总之，死锁是人们不希望发生的，对计算机系统的正常运行有较大的损害，但又是不可避免的随机现象。当然，还有一种最简单的方法来处理死锁，即像鸵鸟一样对死锁视而不见。每个人对死锁的看法都是不同的。数学家认为要彻底防止死锁的产生，不论代价有多大；工程师们想要了解死锁发生的频率、系统因各种原因崩溃的频率以及死锁的严重程度，如果死锁每五年平均产生一次，而每个月系统都会因硬件故障、编译器出错误或者操作系统故障而崩溃一次，那么大多数的工程师们不会不惜代价地去清除死锁。

六、 存储管理

6.1 存储管理体系及任务

速度由快至慢，价格由贵到便宜分为寄存器、高速缓存（通常是MB的数量级）、内存RAM（GB数量级）、磁盘（TB数量级）、光盘和磁带机。

存储管理直接影响系统性能。存储器由内存和外存组成。

内存空间，是由存储单元（字节或字）组成的一堆连续的地址空间。

内存空间一般分为两部分：系统区和用户区。

内存管理问题主要包括：内存管理办法、内存的分配和释放算法、虚拟存储器的管理、控制内存和外存之间数据流动方法、地址变换技术和内存数据保护与共享技术等。

6.1.1 内存的分配和回收

通过引入内存分配表，对用户提出的需求为之分配相应的存储空间。

内存分配有两种方式：静态分配（装入时确认并分配，运行时不允许变动）和动态分配（运行时允许内存“搬家”或申请）。

6.1.2 存储共享

存储共享是指两个或多个进程共用内存中相同区域。

6.1.3 存储保护

1.地址越界保护：发生越界时产生中断，由操作系统进行相应处理。2.权限保护。

6.1.4 地址转换

存储器以字节（每个字节为8个二进制位）为编址单位，假定存储器的容量为n个字节，其地址编号顺序为0，1，2.…，n＝1.这些地址称为内存的“绝对地址”，由绝对地址对应的内存空间称为“物理地址空间”。

为了方便用户，每个用户都可认为自己的程序和数据存储在一组“0”地址开始的连续空间中。用户程序中使用的地址称为“逻辑地址”，由逻辑地址对应的存储空间称为“逻辑地址空间”。

6.1.5 地址重定位

把逻辑地址转换成绝对地址的工作称“地址重定位”或“地址转换”，又称“地址缺射”。重定位的方式可以有“静态重定位”和“动态重定位”两种。

由于地址转换工作是在程序开始执行前集中完成的，所以在程序执行过程中就无须再进行地址转内存地址空间换工作，这种地址转换方式称“静态重定位”。

在程序执行过程中，每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成绝对地址。这种方式的地址转换是在程序执行时动态完成的，故称为“动态重定位”。

动态重定位由软件和硬件相互配合来实现。硬件要有一个地址转换机构，该机构可由一个基址寄存器和一个地址转换线路组成。

6.2 分区管理方案

分区管理是能满足多道程序运行的最简单的存储管理方案。其基本思想是把内存划分成若干个连续区域，称为分区，每个分区装入一个运行程序。分区可分为固定分区和可变分区两类。

6.2.1 固定分区

固定分区是指系统先把内存划分成若干个大小固定的分区，一旦划分好，在系统运行期间便不再重新划分。

用于固定分区管理的内存分配表是一张分区说明表，按顺序每个分区在分区说明表中对应一个表目。表目内容包括分区序号、分区大小、分区起始地址以及使用状态（空闲或占用）。

固定分区方案虽然可以使多个程序共存于内存中，但都不能充分利用内存。因为一个程序的大小，不可能刚好等于某个分区的大小。所以很难避免内存空间的浪费（无外部碎片，有内部碎片）。另外，固定分区方案灵活性差，可接纳程序的大小受到了分区大小的严格限制。

6.2.2 可变分区

可变分区是指系统不预先划分固定分区，而是在装入程序时划分内存分区，使为程序分配的分区的大小正好等于该程序的需求量，且分区的个数是可变的。

随着一系列的内存分配和回收。原来的一整块大空闲区形成了若干占用区和空闲区相间的布局。若有上下相邻的两块空闲区，系统应将它们合并成为一块连续的大空闲区。

可变分区管理方案中，随着分配和回收次数的增加，必然导致碎片（有外部碎片，无内部碎片）的出现。解决碎片问题的办法是在适当时刻进行碎片整理，通过移动内存中的程序，把所有空闲碎片合并成一个连续的大空闲区且放在内存的一端，而把所有程序占用区放在内存的另一端。这一技术称为“紧缩技术”，或“压缩技术”。

采用紧缩技术要注意以下问题：

1. 紧缩技术会增加系统的开销。采用紧缩技术，需要大量的、在内存中进行数据块移动的操作，还要修改内存分配表和进程控制块，这些工作既增加了系统程序的规模，也增大了系统运行时间。
2. 移动是有条件的。不是任何在内存中的进程都能随时移动。比如，若某个进程正在与外部设备交换信息，那么与该进程有关的数据块就不能移动。

所以，在采用紧缩技术时，应该尽可能减少需要移动的进程数和信息量。

6.2.3 可变分区的实现

采用可变分区方式管理时，要有硬件的地址转换机构作支持。硬件设置两个专用的控制寄存器：基址寄存器和限长寄存器。

限长寄存器用来存储程序所占分区的长度，基址寄存器用来存储程序所占分区的起始地址。

当程序被装到所分配的分区后，把分区的起始地址和长度作为现场信息存入该进程的进程控制块中。程序执行过程中，处理器每执行一条指令都要取出该指令中的逻辑地址，当逻辑地址小于限长寄存器中的限长值时，则逻辑地址加基址寄存器值就可得到绝对地址。当逻辑地址大于限长寄存器中的限长值时，表示欲访问的内存地址超出了所分配的分区范围。这时就不允许访问，而形成一个“地址越界”的程序性中断事件。

内存分配表由两张表格组成。一个是已分配区表，记录已装入的程序在内存中占用分区的起始地址和长度，用标志位指出占用分区的程序名。另一个是空闲区表，记录内存中可供分配的空闲区的起始地址和长度，用标志位指出该分区是未分配的空闲区。

6.2.4 空闲分区的分配策略

三种算法。1、最先适应算法：顺序查找分区表，找到第一个满足长度的分区表。2、最优适应算法：找到第一个能满足长度的最小分区（容易产生外部碎片）。3、最坏适应算法：找到能满足申请条件的最大空闲区分配（大程序申请内存时，找不到满足要求的大空间）。

6.2.5 分区的保护

存在两种存储分区保护方法。一是设置界限寄存器；二是保护键方法，为每个分区和进程各分配一个保护键，每当访问时内存时，检查是否匹配。

6.3 覆盖与交换技术

为了扩充内存，将进程地址空间中信息的一部分放在外存上，需要执行的放在内存，就会出现信息交换的问题。

6.3.1 覆盖技术

覆盖技术是指一个程序的若干程序段、或几个程序的某些部分共享某一个存储空间。它利用相互独立的程序段之间在内存空间的相互覆盖，在逻辑上扩充了内存。

覆盖技术是由用户程序自己附加的控制。

6.3.2 交换技术

进程从内存移到磁盘，并再移回内存称为交换。交换技术多用于分时系统中。

交换技术是进程在内存与外存之间的动态调度，是操作系统控制的。

交换技术考虑的问题。1、换出进程的选择。采用时间轮转法或其他调度算法选择要换出的进程；2、交换时机：内存空间可能不够时；3、交换空间的分配；4、换入进程换回内存位置的确定。

交换技术的缺点是，由于交换时需要花费大量的处理器时间，这将影响对用户的响应时间，因此，减少交换的信息量是交换技术的关键问题。合理的做法是，在外存中保留每个程序的交换副本，换出时仅将执行时修改过的部分复制到外存。

覆盖技术和交换技术的发展导致了虚拟存储技术的出现。

6.4 虚拟页式存储管理方案

把一个逻辑地址连续的程序分散存储到几个不连续的内存区域中，并且保证程序的正确执行，则既可充分利用内存空间，又可减少移动所花费的开销。页式存储管理就是这样一种有效的管理方式。

6.4.1 虚拟存储技术

虚拟存储技术的基本思想是利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，简称虚存，以便能够有效地支持多道程序系统的实现和大型程序运行的需要，从而增强系统的处理能力。

虚拟存储管理支持多道程序设计技术。

实现虚拟存储器需要以下的硬件支持。1）系统有容量足够大的外存。2）系统有一定容量的内存。（3）最主要的是，硬件提供实现虚－实地址映射的机制。

虚拟存储器的工作原理如下：当进程开始运行时，先将一部分程序装入内存，另一部分暂时留在外存；当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存的工作；当没有足够的内存空间时，系统自动选择部分内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其他进程使用。

虚拟存储技术和交换技术的区别在于：交换技术交换的对象一般是进程，而虚拟存储一般是以页为单位。

6.4.2 虚拟页式存储管理

支持页式存储管理的硬件部件通常称为“存储管理部件”（Memory Management Unit，MMU）。

存储管理部件首先把内存分成大小相等的许多区，把每个区称为“物理页面”，物理页面是进行内存空间分配的物理单位。同时，要求程序中的逻辑地址也进行分页，页的大小与物理页面的大小一致。

此时“逻辑地址”可被称为虚拟地址。

这样，就可把程序信息按页存放到物理页面中。于是，页式存储器提供编程使用的虚拟地址由两部分组成：虚拟页号和页内地址。其格式如下所示：

虚拟页号	页内地址

页式存储的地址结构确定了物理页面的大小。假定地址用m个二进制表示，其中页内地址部分占用n个二进制位，那么，每一个块的长度就是2^n^，也就是每一页有2^n^个字节。这时，页号部分占用了m－n位，所以，最大的程序可允许有2^(m-n)^个页面。显然，从地结构来看，虚拟地址是连续的。虚拟地址从“0”开始（页号为“0”，页内地址也为“0”），当编址到2^n^－1时，第0页的页内地址的各位均为“1”，即占满了一个页面。下个地址是2^n^，这时页号部分就为“1”，而页内地址部分又恢复到“0”，表示进入了第1页。再继续顺序编址，此时页内地址0～（2^n^－1）是属于第1页的。依次类推，一组顺序的拟地址结构将其自然地分页了。

6.4.3 物理内存的分配与回收

物理页面号=字号×字长 + 位号

假定归还块的块号为i，字号=[i/字长]，位号=i mod 字长

6.4.4 虚拟页式存储地址转换过程

6.4.4.1 页式存储管理的地址转换

为了实现页式存储管理，系统要提供一对硬件的页表控制寄存器，即页表始址寄存器和页表长度寄存器，另外还需要高速缓冲存储器的支持。

页表始址寄存器：用于保存正在运行进程的页表在内存的首地址，当进程被调度程序选中投入运行时，系统将其页表首地址从进程控制块中取出送入该寄存器。

页表长度寄存器：用于保存正在运行进程的页表的长度，当进程被选中运行时，系统将它从进程控制块中取出送入该寄存器。 页表指出该程序虚拟地址中的页号与所占用的物理页面号之间的对应关系。页表的长度由程序拥有的页面数而定，故每个程序的页表长度可能是不同的。

页表是硬件进行地址转换的依据，每执行一条指令时按虚拟地址中的页号查页表。若页表中无此页号，则产生一个“地址错”的程序性中断事件。若页表中有此页号，则可得到对应的物理页面号，按计算公式可转换成访问的内存的物理地址。

物理地址的计算公式为： 物理地址＝物理页面号×块长＋页内地址

需要强调的是，物理页面号又称为页帧和页框号。 根据二进制乘法运算的性质，一个二进制数乘以2^n^结果实际上是将该数左移n位。所以，实际上是把物理页面号作为绝对地址的高位地址，而页内地址作为它的低地址部分。

6.4.4.2 页表项

进程运行前，不是全部装入页面，而是装入一个或零个，然后根据需要动态装入其他页面；当内存空间满了以后，根据某种算法淘汰某个页面，以便装入新页面。

6.4.4.3 页表

1、多级页表。一般来说，页表页不可以连续存放，所以需要对页表页进行索引。最简单的办法是分级，比如采用两级页表，即页面大小（页内偏移量）为4KB（2^12^B）的32位机器，虚拟地址可被分为10位页目录、10位页表和12位的页内偏移。

2、散列页表。

3、反置页表。

4、转换检测缓冲区（TLB）（快表）。利用高速缓冲存储器存储当前访问最频繁的少数活动页面的页号，称为转换检测缓冲区TLB（也叫快表）。

5、缺页异常处理。若在页表中发现要访问的页面不在内存，则产生缺页异常。当发生缺页异常时，操作系统必须在内存中选择一个页面将其移除内存，如果该页面被修改过，则要将它写回磁盘更新磁盘上的副本，如果没有被修改过，则不需要写回，调入的页直接覆盖。

6.4.4.4 页面调度策略

虚拟存储器系统通常定义三种策略来规定如何（或何时）进行页面调度：调入策略、置页策略和置换策略。

（1）调入策略

在虚拟页式管理中有两种常用调入策略。 ①请求调页（Denand　Paging）：只调入发生缺页时所需的页面。这种调入策略实现简单，但容易产生较多的缺页，造成对外存I/O次数多，时间开销过大，容易产生颠簸或象。 ②预调页（Prepqing）：在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。这种策略提高了调页的I/O效率，减少了I/O次数。但由于这是一种基于局部性原理的预测，若调入的页在以后很少被访问，则造成浪费。这种方式常在程序装入时使用。

进程装入时，将其全部页面复制到交换区，以后总是从交换区调入。执行时调入速度快，要求交换区空间较大。

凡是未被修改的页面，都直接从文件区读入，而被置换时不需调出；已被修改的页面，被置换时需调出到交换区，以后从交换区调入。

（2）置页策略

当线程产生缺页时，内存管理器还必须确定将调入的虚拟页放在物理内存的何处。用于确定最佳位置的一组规则称为“置页策略”。

（3）置换策略

如果缺页发生时物理内存已满，“置换策略”被用于确定哪个虚页面必须从内存中移出为新的页面腾出空位。在虚拟页式存储管理方案中，可采用两种分配策略，即固定和可变分配策略。在进行置换时，也可以采用两种策略，即全局置换和局部置换。将它们组合起来，有如下三种策略。

①固定分配局部置换。为每一个进程分配固定的页数的内存空间，运行期间不再改变。

②可变分配全局置换（Variable　 Allocation ，Global　 Replacement ）。采用这种策略时，当某进程发生缺页时，由系统的空闲物理块队列中取出一物理块分配给该进程。但当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一块调出。该块可能是系统中任意一个进程的页。

③可变分配局部置换（Variable　 Allocation ，Local　 Replacement ）。同样基于进程的类型，为每一进程分配一定数目的内存空间。但当某进程发生缺页时，只允许从该进程的页面中选出一页换出，这样就不影响其他进程的运行。如果进程在运行的过程中，频繁地发生缺页，则系统再为该进程分配若干物理块，直到进程的缺页率降低到适当程度为止。

6.4.4.5 页面置换算法

如果刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁。这种现象称为“抖动”或称“颠簸”。

页面置换算法的优劣将会影响虚拟存储系统的性能，进而影响整个系统的性能。下面将介绍几个主要的页面置换算法。

（1）理想页面置换算法（Optimal replacement ，OPT）

OPT算法淘汰以后不再需要的或者在最长时间以后才会用到的页面。这一算法一般不可能实现，但它可以作为衡量其他页面淘汰算法优劣的一个标准。

（2）先进先出页面置换算法（First-In First-Out，FIFO）

先进先出页面置换算法总是选择最先装入内存的一页调出，或者说是把驻留在内存中时间最长的一页调出。FIFO算法简单，容易实现。把装入内存的那些页面的页号按进入的先后次序排好队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排入队尾。

（3）第二次机会页面置换算法

（4）时钟页面置换算法（Clock）

把所有的页面都保存在一个类似时钟面的环形链表中、一个表针指向最老的页面。当发生缺页时，算法首先检查表针指向的页面，如果进入内存时间最久的R位是0就置换该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。由于这个算法的工作方式，就将它称为时钟（clock）算法。

（5）最近最少使用页面置换算法（Least　Recently　Used，LRU）

在缺页发生时，首先淘汰掉最长时间未被使用过的页面。这个策略称为LRU页面置换算法。 最近最少使用页面置换算法总是选择距离现在最长时间内没有被访问过的页面先调出。实现这种算法的一种方法是在页表中为每一页增加一个“计时”标志，记录该页面自上次被访问以来所经历的时间，每被访问一次都应从“0”开始重新计时。当要装入新页时，检查页表中各页的计时标志，从中选出计时值最大的那一页调出（即最近一段时间里最长时间没有被使用过的页），并且把各页的计时标志全置成“0”，重新计时。这种实现方法必须对每一页的访问情况时时刻刻地加以记录和更新，实现起来开销比较大，但LRU算法是在效果上最接近OPP算法的算法。

LRW在手动做题时，可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。

6.4.4.6 缺页率

程序执行中访问页面的总次数为A，其中产生了F次缺页异常，则f=F/A,f称为缺页率。

影响缺页率的因素如下：①分配给程序的物理页面数。②页面的大小。③和程序的局部化程度密切相关。④页面调度算法：FIFO调度算法产生的缺页率约为最佳算法的3倍。

6.5 虚拟页式存储管理的优缺点

虚拟页式存储管理的主要优点是，由于它不要求进程的程序段和数据在内存中连续存放，从而有效地解决了碎片问题。这既提高了内存的利用率，又有利于组织多道程序执行。

虚拟页式存储管理的主要缺点是，存在页面空间的浪费问题。这是由于各种程序代码的长度是各不相同的，但页面的大小是固定的，所以在每个程序的最后一页内总有一部分空间得不到利用。如果页面较大，则由此引起的存储空间的损失仍然较大。

6.6 本章小结

由寄存器、高速缓存（Cache）、主内存储器、硬盘存储器、磁带机和光盘存储器等装置构成了计算机系统中一个速度由快到慢、容量由小到大的层次化的存储体系。内存空间、般分为两部分：一部分是系统区，用以存储操作系统常驻内存部分，用户不能占用这部分空间；另一部分是用户区，分配给用户使用，用于装入并存储用户程序和数据。

存储管理的任务有：存储分配，为用户分配存储空间，在不需要时及时回收，内存分配有静态分配和动态分配方式；内存共享，使多个进程共用内存中相同区域，包括代码共享和数据共享；存储保护，使系统正常运行，避免内存中各程序相互干扰；“扩充”内存容量，使用户得到比实际内存容量大的多的内存空间。

在多道程序设计的系统中，内存中同时存储了多个用户程序，为了保证程序的正确执行，必须根据分配给程序的内存区域对程序中指令和数据的存储地址进行重定位，即要把逻辑转换成绝对地址。静态重定位的地址转换工作是在程序开始执行前集中完成的。动态重定位，在装入程序时不进行地址转换，而在程序执行过程中，每当执行一条指令时才将指令中的逻辑地址转换成绝对地址。动态重定位由软件和硬件地址转换机构相互配合来实现，包括一个基址寄存器和一个地址转换线路。动态重定位的系统支持“程序浮动”，静态重定位的系统不支持“程序浮动”。

分区管理是能满足多道程序运行的最简单的存储管理方案，其基本思想是把内存划分成若干个连续分区，每个分区装入一个运行程序。分区方式有固定分区和可变分区两类。用于固定分区管理的内存分配表是一张分区说明表，在寻找和分配空闲区时有三种分配算法，最先适应算法、最优适应算法和最坏适应算法。固定分区很难避免内存碎片，另外，固定分区方案灵活性差，可接纳程序的大小受到了分区大小的严格限制。可变分区方案在装入程序时划分内存分区，分配的分区大小正好等于该程序的需求量，且分区的个数是可变的。可变分区的内存分配表由已分配区表和空闲区表组成。用户程序执行结束后，系统回收分区，将其记录在空闲区表中。在分区管理中，随着分配和回收次数的增加，必然导致碎片的出现，解决办法是使用紧缩技术进行碎片整理。紧缩技术可以集中分散的空闲区，提高内存的利用率，便于进程动态扩充内存，但是紧缩技术会增加系统的开销，而且移动也是有条件的，在采用紧缩技术时，应该尽可能减少需要移动的进程数和信息量。分区的存储保护方法有两种，一种是系统设置界限寄存器，另一种是保护键方法。分区存储管理算法比较简单，实现较容易，额外开销少，存储保护措施也简单，可变分区的内存利用率比固定分区高；主要缺点是，内存使用不充分，存在较为严重的碎片问题，此外，分区管理不能为用户提供“虚存”。

覆盖技术把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域，未执行的程序段先保存在磁盘上，当有关程序段的前一部分执行结束后，把后续程序段调入内存，覆盖前面的程序段。覆盖技术可以完全由用户实现，也可以由编译程序提供支持。覆盖技术从用户级解决了内存小装不下程序的问题。

交换技术由操作系统控制，将那些不在运行中的进程或其一部分调出内存，暂时存储在外存上的盘交换区中，以腾出内存空间给现在需要内存空间的进程，后者可能需要从外存换入内存，以后再将换出的进程调入内存继续执行。多数现代操作系统使用交换技术，交换技术有力地支持多道程序设计，也是虚拟存储技术的基础。

虚拟存储技术的基本思想是，在硬件支持下把内存和外存统一实施管理，利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，达到“扩充”内存的目的，以便能够有效地支持多道程序系统的实现和大型程序运行的需要，从而增强系统的处理能力。操作系统把程序当前使用的部分保留在内存，而把其他部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。虚拟存储管理支持多道程序设计技术。实现虚拟存储器需要一个容量足够大的外存，一定容量的内存和提供实现虚实地址映射的硬件机制。虚拟存储器的工作原理是，当进程开始运行时，先将一部分程序装入内存，另一部分暂时留在外存；当要执行的指令不在内存时，系统自动将它们从外存调入内存工作。当没有足够内存空间时，系统自动选择部分内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其他进程使用。

虚拟页式存储管理思想是，把内存分成大小相等的许多物理页面，程序中的虚拟地址也进行分页，页的大小与物理页面的大小一致，这样，可把程序信息按页存储到物理页面中。页式存储器的虚拟地址由两部分组成，虚拟页号和页内地址。页式管理分配内存以页面为单位，要在内存分配表中标识哪些物理页面已经分配、哪些物理页面尚未分配以及当前剩余的空闲物理页面数等，简单的内存分配表可以用一张“位示图”构成。页式存储管理要有硬件的地址转换机构作支持，即页表始址寄存器和页表长度寄存器。每个被装入内存的进程有一张页表，该页表所在内存的起始地址和长度作为现场信息存储在该进程的进程控制块中。一旦进程被调度进入处理器执行，这些信息将被作为恢复现场信息送入系统的地址映射机制中的寄存器。页表是硬件进行地址转换的依据，每执行一条指令时按虚拟地址中的页号查页表。若页表中无此页号，则产生一个“地址错”程序性中断事件。若页表中有此页号，则可得到对应的物理页面号，按计算公式可转换成访问的内存的物理地址。TLB利用高速缓冲存储器存储当前访问最频繁的少数活动页面的页号，可快速查找并提高指令执行速度。页式存储管理的主要优点是，由于它不要求程序段和数据在内存中连续存储，解决了碎片问题；主要缺点是，存在页面空间的浪费问题；另一个不足之处是不能应用在分段编写的、非连续存储的大型程序中。页式存储管理允许多个程序共享程序中的代码或公共数据段，因此必须注意解决共享信息的保护问题。

虚拟页式存储管理在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其他页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，装入新的页面。虚拟页式存储管理需要在页表中增加表示某页是否在内存。在内存期间是否被访问过以及表示在内存中是否被修改过等标志位。若在页表中发现所要访问的页面不在内存，则产生缺页异常，系统在内存中选择一个页面将其移出内存；如果要移走的页面在内存期间已经被修改过，就必须把它写回磁盘以更新副本；如果该页没有被修改过，则不需要写回，调入的页直接覆盖被淘汰的页。

页面置换算法直接影响虚拟存储系统的性能。OPT算法淘汰以后不再需要的或者在最长时间以后才会用到的页面，不过这一算法无法实现，但可以作为衡量其他页面淘汰算法的一个标准。FIFO算法总是选择最先装入内存的一页调出，这样做简单而容易实现，但会把常用页面调出。第二次机会算法，是寻找一个最近的时钟间隔以来没有被访问过的页面。Clock算法是把所有的页面都保存在一个类似时钟面的环形链表中，一个表针指向最老的页面，当发生缺页时，算法首先检查表针指向的页面，如果它的R位是0就置换该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。LRU算法首先淘汰掉未使用时间为最长的页，需要在页表中为每一页增加一个“计时”标志，对每一页的访问进行记录和更新，实现开销较大。

若程序执行中访问页面的总次数为A，其中有F次访问的页面尚未装入内存，则f＝F／A为“缺页率”。影响缺页率的因素有：分配给程序的物理页面数、页面的大小、程序编制方法和页面调度算法。

引入虚拟存储，统一管理内存和外存的真正目的，是把访问概率高的页放入内存，减少内外存交换的次数。如果刚被调出的页面又被频繁调度，则出现了颠簸。颠簸由缺页率高引起。对于给定的进程访页序列，在时刻（t－Δ）到时刻t之间所访问页面的集合，称为该进程的工作集。采用工作集模型，为每个进程保持一个工作集，通过动态调整，使该进程获得与工作集相等的物理页面数，可以解决颠簸问题。

七、 文件系统

7.1 文件系统的基本概念

7.1.1 文件系统的任务

在文件系统中，把程序和数据等信息看作文件，文件是通过操作系统来管理的。

文件可以被解释为一组带标识（文件名）的、在逻辑上有完整意义的信息项（构成文件的内容）的序列。

所谓文件系统，是操作系统中统一管理信息资源的一种软件。它管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。

7.1.2 文件的存储介质及存取方式

外存储设备通常由驱动部分和存储介质两部分组成。存储介质又称为卷，驱动器作用是使计算机能够读写存储介质上的内容。

常见的外存储介质有：

1. 磁带：存储容量大；存取速度慢，只能顺序存取。
2. 磁盘：分为软盘和磁盘，磁盘存储容量大、成本低，是随机存储设备。在磁盘中，磁盘空间由盘面、柱面、磁道和扇区组成。磁盘的盘面上划分出的同心圆称为磁道，信息以线性顺序记录在每个磁道上。磁道圆周分为若干弧段，就是扇区，进一步减少物理寻址单位和存取单位，每个扇区构成磁盘的一个物理块。访问磁盘时，将磁头臂移动到对应柱面的磁道上，称为寻道。一次访问磁盘的时间中，寻道花费时间最长。
3. 光盘：价格便宜，一般不可写。
4. 闪存：读写比磁盘快。

文件在存储设备中的存取方式（逻辑地址到物理地址的映射或变换机制）：

1. 顺序存取。从前到后的次序依次访问文件的各信息项。
2. 随机存取。又称直接存取，即根据存取命令把读写指针移动到文件中指定记录处读写。

7.1.3 文件的分类

用途分类：系统文件、库函数文件、用户文件。

组织形式分类：普通文件、目录文件、特殊文件。

还可按保护方式划分，流向分类，存放时限分类，介质类型分类等。

7.2 文件的逻辑结构和物理结构

7.2.1 文件的逻辑结构

文件的逻辑结构是面向用户的文件的组织结构，是用户看到的文件的组织结构。

可以按逻辑结构将文件划分为三类：无结构的字符流式文件、定长记录文件和不定长记录文件构成的记录树。

1. 流式文件是有序字符的集合，就是一串有开头和结尾的连续字符，不存在任何可以视为结构的组织形式。可以说，流式文件无结构。
2. 记录式文件。是一组有序记录的集合，构成该文件的基本单位是记录。记录由该文件的逻辑地址与记录名所对应的关键字（Key）、属性及其属性值所组成，可按键查找。比如：excel记录，SQL文件。记录式文件可分为定长记录文件（可随机存取）和不定长记录文件（只能顺序存取）两种。

7.2.2 文件的物理结构

常用的文件物理结构有顺序结构、链接结构、索引结构。

1. 顺序结构，又称连续结构，它把逻辑上连续的文件信息依次存放在连续编号的物理块中。优点是简单、支持顺序存取和随机存取；缺点是文件不能动态增长，不利于文件插入与删除，有存储碎片。
2. 链接结构。实质通过指针就是为每个文件构造所使用磁盘块的链表。优点是无存储碎片，有利于动态扩充和插入删除，提高了磁盘空间利用率；缺点是存取速度慢，不适于随机存取文件，效率低，存在可靠性问题，指针占用一定空间，需要更多寻道次数和寻道时间。
3. 索引结构。索引结构的文件把每个物理盘块的指针字，集中存储在称为索引表的数据结构中的内存索引表中。在相应的目录条目中包括该文件的索引表地址。优点是支持顺序存取和随机存取，满足文件动态增长、插入与删除要求，充分利用外存空间。缺点是会引起较多的寻道次数和寻道时间，索引表本身增加了存储空间开销。索引表一般不采用连续结构或链接文件结构存储，而是采用间接索引，也称多级索引结构比较好。

7.2.3 UNIX的三级索引结构

UNIX操作系统的i结点是一种多级索引文件结构，i结点的基本思想是，给每个文件赋予一张称为i结点的小表，在这张小表中列出文件属性和文件中各块在磁盘上的物理地址。

简单来说就是索引表分为直接盘块和间接盘块，直接盘块直接链接数据块，间接盘块链接二级或三级索引表。

7.3 文件目录

计算机系统中保存有许多文件，文件系统根据文件名找到指定文件。为了便于对文件进行管理，设置了文件目录，用于检索系统中的所有文件。

7.3.1 文件控制块

文件系统的一个特点是“按名存取”，即用户给出文件的符号名就能存取在外存空间的该文件的信息，而不必了解和处理文件的具体物理地址。

在操作系统中，为了管理大量的文件，为每个文件都设置一个描述性数据结构——文件控制块(FCB， File Control Block )，把所有文件的文件控制块有机地组织起来，就构成了文件控制块的一个有序集合，称为文件目录。

文件目录实际就是文件符号名到文件物理地址之间的一种映射机制。

文件控制块FCB是系统为管理文件而设置的一个数据结构。FCB是文件存在的标志，它记录了系统管理文件所需要的全部信息。

7.3.2 文件目录和当前目录

文件目录分为一级目录结构、二级目录结构和多级目录结构。

1. 一级目录结构包含所有文件的文件控制块FCB，每个FCB指向一个普通文件。优点是简答；缺点是搜索效率低，检索时间长，不能重名。
2. 二级目录结构。第一级称为主文件目录MFD，包含用户名和子目录指针，第二级称为用户文件目录UFD，包含用户文件的文件控制块。优点是解决了重名问题，实现了用户间文件共享，搜索时间变快；缺点是增加了系统开销。
3. 多级目录。又称树型目录结构。除了最低一级物理块中装有文件信息，其他每一级目录中存储的都是下一级目录或文件的说明信息，由此形成层级关系。优点是层级清楚、解决重名问题、查找搜索速度快；缺点是多次访盘影响速度，结构相对复杂。
4. 当前目录。就是绝对路径和相对路径的概念。

7.3.3 目录项和目录文件

目录项是用于管理目录的基本数据结构，一般而言是定长的记录。为了便于管理，通常将文件控制块做成定长数据结构的一个记录，这样的一个记录称为目录项。

目录文件就是目录项的有序集合，通常可以保存到外存储设备上。多个文件的文件控制块集中在一起组成了文件的目录。文件的目录以文件的形式保存起来，这个文件就被称为目录文件。

目录项分解法，即把目录项(FCB)分为两部分，符号目录项和基本目录项。优点是减少了访问磁盘次数，提高了文件目录检索速度。

7.3.4 UNIX的文件目录实现

普通文件的物理结构是三级索引结构。./是当前目录，../是上一级目录，/是根目录。

7.3.5 FAT文件系统的实现

分为引导扇区、文件分配表和根目录。

7.4 文件存储空间管理

为了进行存储空间的分配和回收，在外存储设备上设置有空闲空间登记表，该表动态跟踪该外存储设备上所有还没有分配给任何文件的空闲块的数目和块号。

7.4.1 磁盘空间的分配回收算法

设计空闲空间登记表的数据结构时，有四种方案：

1. 位示图。基本思想是利用一串二进制位(bit)的值来反映磁盘空间的分配使用情况。在位示图中，每一个磁盘中物理块用一个二进制位对应，如果某个物理块为空闲，则相应的二进制位为0；如果该物理块已分配了，则相应的二进位为1。在申请磁盘物理块时，在位示图中从头查找为0的字位，如有则将其改为1，同时返回该二进制位对应的物理块号。归还物理块时，则在位示图中将该物理块对应的二进制字位改为0，表示该物理块恢复为空闲状态。
2. 空闲块表。空闲块表是专门为空闲块建立的一张表，该表记录外存储器全部空闲的物理块：包括个空闲块的第一个空闲物理块号和该空闲块中空闲物理块的个数。在建立新文件时，系统首先查找空闲块表项中是否有符合条件的对应表项，如果有，就将该表项从空闲块表中删去，并且把所对应的一组连续的空闲物理块分配给申请者。当删除文件时，系统收回它所占用的物理块并且考虑所收回的物理块是否可以与原有空闲块相邻接，以便合并成更大的空闲区域，最后修改有关空闲块表项。
3. 空闲块链表。将外存储器中所有的空闲物理块连成一个链表，用一个空闲块首指针指向第一个空间块，随后的每个空闲块中都含有指向下一个空闲块的指针，最后一块的指针为空，表示尾，这样就构成了一个空闲块链表。在空闲块链表模式中对空间的申请和释放是以块为单位的。申请空间是从链首取空闲块，空间释放时将物理块接入链尾。

7.4.2 空间块成组链接法

对链接表的一个改进方案是将n个空闲盘块的地址存储在第一个空闲块中,其余n-1个空闲盘块是实际空闲的。假设每100个空闲块为一组。第一组的100个空闲块块号放在第二组的头一块中，而第二组的其余99块是完全空闲的。第二组的100个块号又放在第三组的头一块中,依次类推,组与组之间形成链接关系。在最后一组的块号中第2个单元填“0”，表示该块中指出的块号是最后一组的块号，空闲块链到此结束。在这个空闲块链中，不足100块的一个组的块号，通常放在内存的一个专用块中。这种方式称为成组链接。

当需分配空闲块时，系统在初始化时先把专用块内容读到内存中，然后在内存中找到哪些块是空闲的，每分配一块后把空闲块数减1。但在把一组中的第一个空闲块分配出去之前，应把登记在该块中的下一组的块号及块数保存到专用块中（此时原专用块中的信息已经无用，因为它指出的一组空闲块都已被分配了）。当一组空闲块被分配完后，则再把专用块的内容读到内存中，指出另一组可供分配的空闲块。

当归还一个空闲块时，只要把归还块的块号登记到当前组中，且空闲块数加1。如果当前组已满100块，则把这100个块号写到归还的那块中，该归还块就成为新组的第一块。

7.5 实现文件系统的表目

当用户申请打开一个文件时，系统要在内存中为该用户保存一些必要的信息，这些信息以表格栏目中的内容的形式出现，被称为表目。

常用于共享文件修改标志、共享计数。

7.6文件及文件目录的操作

7.6.1 典型的文件操作

1. 建立文件：creat（文件名，访问权限，（最大长度））
2. 删除文件:delete（文件名）
3. 打开文件：fd=open（文件路径名，打开方式）
4. 关闭文件：close（文件名）
5. 读文件：read（文件名，（文件内位置），要读的长度，内存目的地址）
6. 写文件：write（文件名，记录键，内存位置）
7. 指针定位：seek（fd，新指针的位置）

7.6.2 典型的目录操作

1. creat，创建目录
2. delete，删除目录
3. opendir，打开目录
4. closedir，关闭目录
5. readdir，返回打开目录的下一目录项
6. rename，目录换名
7. link，链接技术允许多个目录下出现同一文件。
8. unlink，删除目录项。

7.7 文件系统的性能

文件系统的物理基础是磁盘设备，磁盘存储器是关键，设计文件系统时应尽可能减少磁盘访问次数。

7.7.1 磁盘高速缓存

基本思想是，系统在内存中保存一些磁盘块，这些磁盘块在逻辑上属于磁盘，划分出的区域称为块高速缓存。运行时，系统检查所有的读请求，看所需的文件块是否在块高速缓存中。如果在，则可直接在内存中进行读操作；否则，首先要启动磁盘，将所需块读到高速缓存中，再复制到其他内存区域。如果内存中的高速缓存已满，则需要按照一定的算法淘汰一些较少使用的磁盘块，让出块高速缓存空间。

记录的成组，把若干个逻辑记录合成一组存储一物理块的工作，每块中的逻辑记录个数称为“块因子”。优点是提高了存储空间利用率，减少了启动外部设备的次数，提高了系统的工作效率。

对定长记录格式的文件按记录成组的方式存储到存储个质上，则除最后一块外，每块中存储的逻辑记录个数是相同的。故只要在文件目录中说明逻辑记录的长度和块因子，在需要使用某个记录时就能方便地将其找出。 如果是一个不定长记录格式的文件，各个逻辑记录的长度可能不相等，在进行记录成组操作时，就应在每个逻辑记录前附加说明该记录长度的控制信息。

记录的分解，从一组逻辑记录中把一个逻辑记录分离出来的操作。对定长记录格式，只要知道逻辑记录的长度就能够很容易地进行分解。对不定长记录格式，要根据说明逻辑记录长度的控制信息，计算出用户所指定的记录在内存缓冲区中的位置，然后把记录分解出来。

7.7.2 RAID技术

解决速度慢和出现故障的问题。最常用的有以下几种。

1. RAID0采用多个磁盘并行提高读写速度。
2. RAID1采用磁盘镜像的方法提高可靠性。
3. RAID5采用检验码以”块“为单位与数据块一起随机存储在磁盘块中。

7.8 文件共享、保护和保密

7.8.1 文件共享

共享文件的使用有两种情况：1、文件可以同时使用；2、文件不允许同时使用。

三种文件的共享形式。1、文件被多个用户使用，由存取权限控制；2、文件被多个程序使用，但分别用自己的读写指针；3、文件被多个程序使用，但共享读写指针。

在多级目录中，连接法是常用的实现文件共享技术。一种是可共享所连接的目录及各个子目录所包含的全部文件，所有共享文件放在一个公共目录。另一种连接方式只允许对单个普通文件连接，从而通过不同路径访问同一个文件。

7.8.2 文件存取控制

1. 建立副本
2. 定时转储
3. 规定文件的存取权限：一是采用树形目录结构；二是采用存取控制表。

7.8.3 UNIX的文件使用权限管理方案

1. 存取控制矩阵。 一维代表所有用户，另一维代表所有的文件。两维交叉点所对应的矩阵元素则是某一个用户对一个文件的存取控制权限，包括读R、写W和执行E。
2. 二级存取控制。 通过设立两个存取级别。在第一级，把用户按某种关系划分为若干个用户组，进行对访问者的识别；在第二级，进行对操作权限的识别。
3. UNIX中的文件存取权限。“d”表示目录，“c”表示该文件为字符设备文件，“b”表示为块设备文件，“I”表示为一个符号连接；其余九个位置分别表示三组的三种权限设置：第二个到第四个位置表示属主的权限分别设置为读、写和执行，第五个到第七个位置设置同组用户的权限，第八个到第十个位置设置其他用户的权限。若指定位置上没有显示对应的权限，而是“－”，则表示不允许对应的权限。

7.8.4 文件的保密措施

1. 隐蔽文件目录
2. 设置口令
3. 使用密码
4. 病毒防范

7.9 本章小结

本章首先介绍文件系统的基本概念、分类以及文件系统的功能。任何文件都有其内在的文件结构。用户看到的是文件的逻辑结构，有无结构的字符流式文件、定长记录文件和不定长记录文件。常用的文件物理结构有顺序结构、链接结构、索引结构和i结点结构。顺序结构最简单，它把逻辑上连续的文件信息依次存储在连续编号的物理块中，其优点是一旦知道了文件在文件存储设备上的起始块号和文件长度，就能很快地进行存取；顺序结构缺点在于文件不能动态增长,有碎片问题。文件的链接结构的实质就是为每个文件构造所使用磁盘块的链表，其优点是没有存储碎片问题，有利于文件动态扩充，有利于文件插入和删除，提高了磁盘空间利用率；主要缺点是存取速度慢，不适于随机存取文件，效率相对较低，存在文件的可靠性问题。索引结构的文件把每个物理盘块的指针字，集中存储在称为索引表的数据结构中即内存索引表中,该结构保持了链接结构的优点,又解决了其缺点,既适于顺序存取，也适用于随机存取；其缺点是，较多的寻道次数和寻道时间，增加了存储空间的开销。i结点是多级索引结构文件在UNIX操作系统中的具体实现。i结点解决了索引结构的缺点，其基本思想是给每个文件赋予一张称为i结点的小表，在这张小表中列出了文件属性和文件中各块在磁盘上的地址。i结点的文件结构，不仅适合小文件使用，也可供大型文件使用，灵活性比较强，占用的系统空间也比多级索引结构的文件要少。

在计算机系统中，外存储设备同内存相比较，一般有容量大、断电后仍可保存信息、速度较慢、成本较低等特点。常见的外存储设备有顺序存取设备和随机存取设备两种。磁带是典型的顺序存取设备，优点是容量大，但存取速度太慢。磁盘是一种典型的随机存取设备，允许文件系统直接存取磁盘上的任意物理块。磁盘的物理地址具有如下的形式：磁头号（盘面号）、柱面号（磁道号）、扇区号。

文件的存取方式是实现文件的逻辑结构和物理结构之间的映射或变换机制，把用户对逻辑文件的存取要求，变换为对相关文件的物理存储块的读写请求。文件常用的存取方法有顺序存取和随机存取等两种方式。文件的存取方式，既取决于用户使用文件的方式，也与文件所使用的存储介质有关。

文件系统的特点是“按名存取”，用户只要给出文件的符号名就能存取文件，而不必了解和处理文件的具体物理地址。每个文件有一个描述性数据结构――文件控制块FCB。把所有文件的文件控制块组织起来构成了文件目录。FCB是文件存在的标志，它记录了系统管理文件所需要的全部信息，分成文件存取控制信息、文件结构信息和文件管理信息。文件目录以文件的形式保存起来，这个文件就被称为目录文件。一般把文件目录设计成一级目录结构、二级目录结构和多级目录结构。一级目录结构是系统中一张线性目录表，表中包括了所有文件的文件控制块，每个文件控制块指向一个普通文件。在系统初启时或需要时，系统将该一级目录表调入内存，或部分调入内存，通过该目录表提供的信息，对文件进行创建、搜索、读写和删除等操作。一级目录结构的优点是简单而容易实现，但只能按连续结构或顺序结构存储，限制了用户对文件的命名，不能重名，搜索效率较低，文件平均检索时间长。在二级目录结构中，目录被分为两级。第一级称为主文件目录，给出了用户名和用户子目录所在的物理位置；第二级称为用户文件目录，给出了该用户所有文件的FCB。二级目录解决了文件的重名问题，可以实现用户间的文件共享，查找时间也降低了。二级目录的缺点是增加了系统的开销。把二级目录的层次关系加以推广，就形成了树型目录结构，最高层为根目录，最低层为文件。根目录是唯一的，从根结点出发到任一非叶结点或叶结点都有且仅有一条路径，该路径上的全部分支组成了一个全路径名。树型目录结构的优点是便于文件分类，层次清楚，解决了文件重名问题，查找搜索速度快。多级目录结构的缺点是，查找一个文件多次访盘会影响速度，结构相对比较复杂。为加快目录检索可采用目录项分解法，把目录项分为符号目录项和基本目录项。在不同系统中，管理目录的系统调用是不同的，常见的目录操作有创建目录、删除目录、打开目录、关闭目录、读取目录、目录换名、链接多个目录和删除目录项等。

为了进行存储空间的分配与回收，设置有空闲空间登记表，动态跟踪记录该外存储设备上所有尚未分配给任何文件的空闲块的数目和块号。位示图法的基本思想是，利用一串二进制位的值来反映磁盘空间的分配使用情况。位示图对空间分配情况的描述能力强，查找既方便又快速，适用于各种文件物理结构的文件系统。空闲块表记录外存储器全部空闲的物理块——包括每个空闲块的第一个空闲物理块号和和该空闲块中空闲物理块的个数。空闲块表方式特别适合于文件物理结构为顺序结构的文件系统。将外存储器中所有的空闲物理块连成一个链表，用一个空闲块首指针指向第一个空闲块，随后的每个空闲块中都含有指向下一个空闲块的指针，最后一块的指针为空，表示链尾，就构成了一个空闲块链表。空闲块链表法节省内存,但申请空间和回收空间的速度较慢,实现效率较低。对链接表的改进方案是将n个空闲盘块的地址存储在第一个空闲块中，第一组的空闲块块号放在第二组的头一块中，第二组的块号放在第三组的头一块中,依次类推,组与组之间形成链接关系。在最后一组的块号中第2个单元填“0”，表示该块中指出的块号是最后一组的块号，空闲块链到此结束。在空闲块链中不足一组的块号,通常放在内存的一个专用块中。采用成组链接后,分配回收空闲块均在内存中查找和修改，只有在一组空闲块分配完或空闲磁盘块构成一组时才需要启动磁盘读写,所以成组链接的管理方式效率高,能够迅速找到大量空闲盘块地址。

当用户申请打开一个文件时，系统要在内存表目中为该用户保存一些必要的信息。系统打开文件表用于保存已打开文件的文件控制块以及有已打开文件的文件号、共享计数、修改标志等。在每个进程中有一个用户打开文件表，内容有文件描述符、打开方式、读写指针、系统打开文件表入口等。

当用户文件的逻辑记录比存储介质的物理分块小时，可把若干个逻辑记录合成一组存储于一物理块，即记录的成组；从一组逻辑记录中把一个逻辑记录分离出来的操作，即为记录的分解。记录的成组和分解技术，提高存储空间的利用率和减少启动设备的次数，但需要代价，如设立内存缓冲区和相关的操作系统功能等。

文件系统是提供给用户使用的，常用文件操作有建立文件、打开文件、读文件、写文件、关闭文件、撤销文件和指针定位等。

文件的共享是指一个文件可以允许多个用户共同使用。文件共享节省了文件所占用的存储空间，可免除系统复制文件的工作，减少实际输入输出文件的次数，并实现进程间相互通信。在多级目录结构中，连接法是常用的文件共享技术。文件系统必须有防止硬、软件的各种可能意外破坏文件的能力，为此文件系统要采用建立副本和定时转储的方法来保护文件。为了保护文件，要对用户的存取权限实施控制。对文件存取权限的设置方法，有存取控制矩阵和二级存取控制等。在存取控制矩阵方式中，系统以一个二维矩阵来实施文件的存取控制。与存取控制矩阵配套，系统中有存取控制验证模块。当用户向文件系统提出存取要求时，存取控制验证模块根据该文件存取控制矩阵的内容对用户的本次存取要求进行比较，如果不匹配，则系统拒绝执行用户的本次存取要求。存取控制矩阵比较简单，容易实现。但是，当文件和用户较多时，存取控制矩阵占用了太多空间，时间开销也比较多。二级存取控制方法将存取级别分为两个级别，在第一级把用户划分为若干用户组，进行对访问者的识别；在第二级进行对操作权限的识别，所有用户组对文件权限的集合形成了对该文件的存取控制。文件的保密的目的，是防止不经文件拥有者授权而窃取文件，文件保密的措施有隐蔽文件目录、设置口令和使用密码。计算机病毒是一类特殊的攻击，防范病毒最关键的一步是阻止病毒入侵；另外要定期进行病毒检测和消除。

八、I/O设备管理

操作系统中负责管理输入输出设备使用的部分，称为操作系统的设备管理系统，也称为I/O系统。

8.1 I/O设备管理的基本概念

操作系统复杂和庞大的主要原因是它所管理的资源庞杂和采用了并发技术；I/O设备与处理器的速度鸿沟正是导致并发技术产生的直接原因。

如何解除速度鸿沟？操作系统主要通过缓冲技术、中断技术和虚拟技术来解决这一问题。

8.1.1 I/O设备分类

I/O设备按使用特性可分为输入设备、输出设备、交互式设备和存储设备等。

I/O设备按设备的信息组织方式可分为字符设备和块设备。

I/O设备按使用可共享性分为独占设备、共享设备和虚拟设备等。

8.2 I/O硬件和I/O软件的组成

8.2.1 I/O硬件组成

从硬件的角度来看，I/O硬件由物理设备和电子部件两部分组成。

硬件结构分为：中央部分是处理器和内存，第二层是接口（适配器），第三层是各种设备控制器和外围设备。

每个设备控制器都有若干个寄存器来和处理器进行通信，包括控制寄存器（控制发送、接受数据）、状态寄存器（获取设备状态）和数据寄存器（缓冲区）。

8.2.2 I/O软件组成

I/O软件结构分为四层：中断处理层软件，设备驱动层程序，设备独立层软件和用户层软件。

8.2.3 设备独立性

I/O软件和设备相互独立，不依赖于硬件，只要安装相应设备驱动，就可以方便的使用新的I/O设备。

通过以下方法实现。

1. 设备命名。采用文件系统路径名的方法来命名设备。
2. 设备保护。系统中的I/O设备借用文件系统中的“rwx”位进行保护。
3. 提供一个与设备无关的逻辑块。向上层提供大小统一逻辑块尺寸，这样，高层软件只与抽象设备打交道。
4. 缓冲区。设置缓冲区。
5. 存储设备的块分配。在硬盘中分配新的存储块。
6. 独占设备的分配和释放。
7. 错误处理。

8.3 I/O设备控制方式

主要有四种：程序控制方式、中断控制方式、DMA控制方式和通道控制方式。

8.3.1 程序控制方式

程序控制方式也称为PIO( Programmed I/O，程控I/O)方式，是指由用户进程直接控制处理器或内存和外围设备之间进行信息传送的方式，也称为“忙·等”方式、轮询方式或循环测试方式，这种方式的控制者是用户进程。

当用户进程需要从外围设备输入数据时，它通过处理器发出启动设备准备数据的启动命令(通常是把一个启动位为1的控制字通过数据总线写入设备的控制寄存器中)，然后，用户进程进入测试等待状态。在等待时间，处理器不断地用一条测试指令检查设备的状态寄存器是否为完成状态(通常是检测状态寄存器的完成位是否为1)，而外围设备只有将输入数据送入数据缓冲寄存器之后，才将该寄存器置为完成状态。当处理器检测到设备的状态寄存器为完成状态，则从设备的数据缓冲寄存器读取数据到内存或处理器。 反之，当用户进程需要向输出设备输出数据时，也必须同样发出启动命令和等待设备准备好止后才能输出数据。

程序直接控制方式的优点是处理器和外设的操作能通过状态信息得到同步，而且硬件结构比较简单；其缺点是处理器效率较低，传输完全在处理器控制下完成，对外部出现的异常事件无实时响应能力。 所以，程序直接控制方式只适用于那些处理器执行速度较慢，且外围设备较少的系统，如单片机系统。

8.3.2 中断控制方式

中断是一种在发生了一个异常事件时，调用相应处理程序（通常称为中断服务程序）进行服务的过程。

中断源一旦需要处理器为其服务时，就向处理器发出请求，处理器一般在当前指令执行完，且状态为允许中断的情况下响应该请求。并由硬件自动关中断（防止在保留断点和程序转移过程中又有新的中断请求发生）、保留断点、转到相应的中断服务程序入口处。然后执行中断服务程序，由软件完成中断服务。中断服务程序结束时，执行中断延回指令返回断点处，继续执行原程序。

采用中断控制方式，可以做到以下内容。 处理器与外设在大部分时间内并行工作，有效地提高了计算机的效率。处理器启动外设后，不需要去查询其工作状态，可继续执行主程序，因此两者可并行工作。等外设将数据推备好后，主动申请中断处理器的工作，请求服务。

8.3.3 DMA控制方式

中断方式速度还是太慢。采用DMA方式解决这一问题。

DMA是直接内存访问( DiretMemory Access)的缩写，它是一种完全由硬件执行 I/O数据交换的工作方式。在这种方式中，DMA控制器( DMAController ，DMAC)从处理器完全接管对总线的控制，数据交换不经过处理器，而直接在内存和I/O设备之间进行。采用DMA方式工作时，由DMA控制器向内存发出地址和控制信号，进行地址修改，对传送字的个数计数，并且以中断方式向处理器报告传送操作的结束。

DMA方式一般用于高速传送成组的数据。其优点是操作均由硬件电路实现，传输速度快；处理器仅在初始化和结束时参与，对数据传送基本上不干预，可以减少大批量数据传输时处理器的开销；处理器与外设并行工作，效率高。但是DMA方式也有一定的局限性，这是因为DMA方式在初始化和结束时仍由处理器控制，因此，为了进一步减轻CPU的负担和提高系统的并行工作程度，除了设置DMA器件之外，还设置了专门的硬件装置——通道。

8.3.4 通道控制方式

通道(Channel)是一个特殊功能的处理器，它有自己的指令和程序，可以实现对外围设备的统一管理和外围设备与内存之间的数据传送。引入通道的目的是为了进一步减少数据输入输出对整个系统运行效率的影响。

与DMA方式相比，通道方式增加了处理器与通道操作的并行能力；增加了通道之间以及同一通道内各设备之间的并行操作能力；为用户提供了灵活增加外设的可能性。

按照信息交换方式的不同，一个系统中可以设立三种类型的通道，即选择通道、数组多路通道和字节多路通道。

1. 选择通道是一种高速通道，在物理上它可以连接多个设备，但是这些设备不能同时工作，在某一段时间内通道只能选择一个设备进行工作。选择通道主要用于连接高速外围设备（磁盘、磁带等），优点是以数据块单位进行传输，传输率高；缺点是通道利用率低。
2. 数组多路通道的基本思想是当某个设备进行数据传送时，通道只为该设备服务；当设备在执行寻址等控制性动作时，通道暂时断开与这个设备的连接，挂起该设备的通道程序，去为其他设备服务，即执行其他设备的通道程序。其优点是同选择通道一样，以数据块为单位进行传输，传输率高；又具有多路并行操作的能力，通道利用率高。缺点是控制复杂。
3. 字节多路通道是一种简单的共享通道，在分时的基础上为多台低速和中速设备服务。它的主要特点是：各设备与通道之间的数据传送是以字节为单位交替进行的，各设备轮流占用一个很短的时间片；多路并行操作能力与数组多路通道相同。

8.4 设备分配与回收

1.数据结构

在设备分配算法的实现中，常采用的数据结构主要含四张表，即系统设备表(System Device Table，SDT)、设备控制表(Device Control Table，DCT)、控制器控制表(Contolle Contol Table，COCT)和通道控制表(Channel Contol Table，CHCT)。这四张表在分配算法中形成了一个有机整体，有效地记录了外设资源在系统中的情况。设备的每一次分配调用都与这四张表有关。

系统设备表SDT。SDT表在整个系统中只有一张，全面反映了系统中的外设资源的类型、数量、占用情况等。

设备控制表DCT。系统中的每台设备都有一张设备控制表DCT。在DCT中充分体现出了设备的各方面特征，以及与该设备相连的设备控制器的情况，并保存了控制器块的入口位置。

控制器控制表COCT。每个控制器都有一张控制器控制表COCT，用于登录某控制器的使用分配情况及与该控制器相连的通道的情况。

通道控制表CHCT。CHCT表反映了通道的情况，系统中的每个通道一张CHCT。

2.分配原则

设备分配的总原则是：要充分发挥设备的使用效率，尽可能地让设备忙碌，但又要避免由于不合理的分配方法造成进程死锁。

设备分配方式有两种，即静态分配和动态分配。

静态分配方式是在用户作业开始执行前，由系统一次分配该作业所要求的全部设备、控制器（和通道）。一旦分配后，就一直为改作业所占用，直到作业被撤销。该方式不会出现死锁，但利用率低，不符合分配总原则。

动态分配在进程执行过程中根据执行需要进行。利用率高，但可能造成死锁。

3.分配策略

设备的分配策略和进程调度相似，优先采用先来先服务（FIFS）算法和高优先级优先算法等。

8.4.1 独占设备分配

设备的绝对好与相对号：用户使用相对号，系统根据分配情况选择符合条件的绝对号设备，用一张设备分配表映射出相对号和绝对号的关系。

指定设备的方式：1、指定设备的绝对号；2、指定设备类、相对号。

独占设备指在一段时间内只能有一个进程所占有。

8.4.2 共享设备分配

共享设备可被多个进程所共享，但每个I/O传输的单位时间内只由一个进程所占有。

将独占设备转变为共享设备的技术叫SPOOLing系统，也称“虚拟设备”。

8.5 磁盘调度策略

磁盘执行一次输入输出所花费的时间包括：寻找时间、延迟时间、传送时间。

8.5.1 移臂调度及调度算法

根据访问者指定的柱面位置来决定执行次序的调度，称为“移臂调度”。移臂调度的目的是尽可能地减少操作中的寻找时间。

在磁盘盘面上，0磁道在盘面的外部；号数越大，磁道越靠近盘片的中心。磁盘在关时，硬盘磁头停放在最内圈柱面。

常用的移臂调度算法有先来先服务算法、最短寻找时间优先算法、电梯调度算法和单向扫描算法。

1. 先来先服务算法。
2. 最短寻找时间优先算法：总是从等待访问中挑选寻找时间最短的哪个请求执行的，不管访问者到来的先后次序。
3. 电梯调度算法：是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。
4. 单向扫描算法：不考虑访问中等待的先后次序，总是从0号柱面开始向里道扫描，按照各自所要访问的柱面位置的次序去选择访问者。

8.5.2 旋转调度优化

根据延迟时间来决定柱面的访问执行次序的调度。

8.5.3 信息的优化分布

扇区的错开分布。

优化分布有利于减少延迟时间，缩短输入输出操作的时间。

8.6 缓冲技术

8.6.1 缓冲的引入

I/O设备和处理器处理速度不匹配的问题制约了计算机系统性能的进一步提高，限制了系统的应用范围。

I/O设备与处理器速度不匹配的问题可以采用设置缓冲区的方法解决。在设置了缓冲区之后，计算进程可把数据首先输出到缓冲区，然后打印机则可以从缓冲区取出数据慢慢打印。 再者，数据缓冲区大大减少了处理器的中断处理时间。

实现缓冲区的方法：1、采用专用的硬件设置数据缓冲区；2、在内存划出一定容量的专门数据缓冲区，称为“软件缓冲区”。

8.6.2 缓冲的种类

根据系统设置的缓冲区的个数，可把缓冲技术分为单缓冲、双缓冲和多缓冲以及缓冲池等几种。

单缓冲是在I/O设备和处理器之间设置一个缓冲区。

解决两台I/O设备或者打印机和终端之间的并行操作问题的办法是设置双缓冲区。

多缓冲是指，一种具有多个缓冲区，其中一部分缓冲区专门用于输入，另一部分缓冲区专门用于输出的缓冲结构。

而缓冲池则是把多个缓冲区连接起来统一管理，在缓冲池中的每个缓冲区既可用于输入又可用于输出的一种缓冲结构。

8.6.3 缓冲池管理

由于缓冲区是一种临界资源，所以在使用缓冲区时都有一个申请、释放和互斥的问题需要考虑。 首先考察缓冲池的组成。缓冲池由多个缓冲区组成，而一个缓冲区由两部分组成：一部分是用来标识和管理该缓冲器的缓冲首部，另一部分是用于存储数据的缓冲体。这两部分有――对应的映射关系。对缓冲池的管理是通过对每一个缓冲器的缓冲首部进行操作实现的。

系统把各缓冲区按其使用状况连成三种队列。(1)空闲缓冲队列em；(2)装满输入数据的输入缓冲队列in； (3)装满输出数据的输出缓冲队列out。

8.7 虚拟设备技术

虚拟设备技术，又称为SPOOLing技术，是多道程序设计系统中处理独占I/O设备的一种方法，它可以提高设备利用率并缩短单个程序的响应时间。SPOOLing技术之所以被称为虚拟设备技术，是因为它可以使进程在所需的外部设备不存在或被占用的情况下使用该设备。

8.7.1 虚拟设备的实现原理——SPOOLing系统工作原理

SPOOLing系统，全称为 Simultaneous Peripheral Operations On-Line，其含义是同时的外部设备联机操作，也称假脱机技术。

SPOOLing系统主要包括输入程序模块、输出程序模块、作业调度程序三部分。其工作原理如下。

利用SPOOLing系统中的输入程序模块，在作业执行前就利用慢速设备将作业预先输入到后援存储器（如磁盘、磁鼓，此时，这些磁盘、磁鼓称为输入井）中去，称为预输入。作业进入内存运行后，使用数据时，直接从输入井中取出。 另一方面，作业执行时不必直接启动外部设备输出数据，只需将这些数据写入输出井（专门用于存储将要输出信息的磁盘、磁鼓）中去，称为缓输出。 待作业全部运行完毕，再由外部设备输出全部数据和信息。

8.7.2 SPOOLing的组成和实现

划分了许多输入井和输出井，每一个独占设备对应一个井（也是一个存储块）。外存储设备通过通道联接到主机系统中。

8.7.3 SPOOLing系统的实现——打印机的值班进程

打印机是一种典型的独占设备，引入SPOOLing技术后，用户的打印请求挂到打印队列上,这样就把独占设备改造成了共享设备，从而提高了设备的利用率和系统效率。 并不是所有的独占设备都能通过SPOOLing系统改造为共享设备的，例如摄像机等一些需要实时响应的设备。

8.8 本章小结

本章首先总述设备管理工作的重要性，然后叙述输入输出设备的分类。I/O设备由物理设备和电子部件两部分组成。物理设备泛指输入输出设备中为执行所规定的操作所必须有的物理装置。电子部件是指接受和发送计算机与输入输出设备之间的控制命令以及数据的电子部件，一部分是I/O设备控制器，另一部分是设备接口。

系统对I/O设备的控制模式有程序查询方式、程序中断方式、DMA方式和通道方式。查询方式定时对各种设备轮流询问一遍有无处理要求，有要求的则加以处理，在处理完I/O设备要求之后，处理器返回继续工作。查询占据了处理器部分处理时间，效率较低。

为了提高整体效率，支持多道程序和I/O设备的并行操作，采用中断方式控制I/O设备和内存与处理器之间的数据传送。但是中断次数的增加会造成处理器无法响应中断和数据丢失，如果I/O数据缓冲区较小，发生中断的次数较多，将耗去处理器处理时间。

DMA技术是指数据在内存与I/O设备间直接进行成块传输。DMA在内存与I/O设备间传送一个数据块的过程中，不需要处理器的任何中间干涉，只需要处理器在过程开始时向设备发出“传送块数据”的命令，然后通过中断来得知过程是否结束和下次操作是否准备就绪、实际的操作由DMA硬件直接完成，处理器可去做其他的处理而不被此传送打扰。在处理器发出DMA命令之后，DMA实际上采用了窃取总线控制权的方法进行工作。DMA方式与中断方式的主要区别是，中断方式是在数据缓冲寄存器满后发出中断，而DMA方式则在数据块全部传送结束时要求中断处理，减少了中断次数。另外，中断方式的数据传送是在中断处理时由处理器控制完成的，而DMA方式则是在DMA控制器的控制下，不经过处理器控制完成的。DMA技术提高了I/O效率，但是降低了处理器处理效率。

输入/输出通道是一个独立于处理器的、专门管理I/O的处理器，它控制设备与内存直接进行数据交换。它有自己的通道指令，这些通道指令由处理器启动，并在操作结束时向处理器发出中断信号，是一种以内存为中心，实现设备和内存直接交换数据的控制方式。通道对系统整体性能的提高起了相当重要的作用。

I/O软件的设计目标是提供设备的独立性以及对设备的统一命名。I/O软件采用层次化结构，低层与硬件相关，把硬件与较高层次软件隔离，高层的软件向应用提供友好、清晰而统一的I/O设备接口。I/O软件结构分为中断处理程序、设备驱动程序、与设备无关的操作系统软件和用户级软件四层。I/O设备中断处理程序要考虑到I/O设备操作的正常结束和异常结束，配以必要的处理。设备驱动程序直接同硬件打交道，接受来自与设备无关上层软件的抽象请求，进行与I/O硬件设备相关的处理。设备驱动程序最突出的特点是，它与I/O设备的硬件结构密切联系，其代码依赖于设备，是系统底层中唯一知道各种I/O设备控制器细节以及其用途的部分。与设备无关软件的功能包括所有设备都需要的I/O功能，为应用层提供一个统一的接口，对设备进行保护，防止无授权的应用或非法使用，屏蔽各种I/O设备不相同的细节，向高层软件提供统一的逻辑块、缓冲区，实现存储设备的块分配，进行独占设备的分配和释放，从事出错处理。在用户程序中会有一小部分程序与I/O有关。

设备分配的原则是，充分发挥设备的使用效率，但要避免死锁；用户程序面对逻辑设备，分配程序在系统把逻辑设备转换成物理设备之后，再根据物理设备号进行分配。静态分配方式是在用户作业开始执行前，由系统一次分配该作业所要求的全部设备。动态分配根据执行需要进行，当进程需要设备时，通过系统命令提出请求，系统按照策略分配设备，用完之后立即释放。动态分配可提高设备的利用率，但有可能造成死锁。

为了对外部设备进行管理，系统为每一台设备确定一个编号，即设备的“绝对号”。用户对在程序中定义的，要求使用的若干设备给出的编号称为设备的“相对号”。独占型设备在一段时间内只能由一个进程所占有。操作系统设置“设备类表”和“设备表”记录计算机系统所配置的独占设备类型、台数以及分配情况等。用户作业提出某类外部设备申请后，系统首先检查“设备类表”，如果现存台数可以满足要求，则取得该类设备的“设备表”始址，否则进入等待队列；修改“设备类表”中该类设备的现存台数；把该台设备在“设备表”中的“分配状态”标志改成“已分配”；在该“设备表”中填上拟占用该设备的作业名和作业程序中定义的该设备相对号。

共享设备可被多个进程所共享，但在每个I/O传输的单位时间内只由一个进程所占有。用户在使用共享型设备时没有明显的设备申请与设备释放活动。不过，在每一个使用命令之前都隐含有一个申请命令，在每一个使用命令之后都隐含有一个释放命令，在此隐含的申请命令和隐含的释放命令之间，执行了一次I/O传输。

启动磁盘时，要把移动臂移动到指定的柱面，再等待指定的扇区旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。执行一次输入输出所花的时间有寻找时间、延迟时间和传送时间。在读写请求来到时，应采用调度策略决定执行次序，使寻找和延迟时间都尽可能小的那个访问者可优先得到服务，降低访问者的总访问时间，增加磁盘单位时间内的操作次数。磁盘驱动调度由“移臂调度”和“旋转调度”两部分组成。常用的移臂调度算法有先来先服务、最短寻找时间优先、电梯调度和单向扫描算法。当移动臂定位后，旋转调度应该优先选择延迟时间最短的访问者去执行。记录在磁道上的排列方式会影响磁盘的操作时间，优化分布有利于减少延迟时间，缩短整个输入输出操作的时间。

为了匹配I/O设备与处理器间的处理速度，减少外部中断的次数和处理器中断处理所花费的时间，并解决DMA或通道方式中可能出现的瓶颈问题，需要使用暂存数据的缓冲技术。实现缓冲区的方法有两种，一是采用专用的硬件设置数据缓冲区，另一种方法是在内存划出专用数据缓冲区，即“软件缓冲”。缓冲区有单缓冲、双缓冲和多缓冲以及缓冲池等几种。单缓冲能匹配设备和处理器的处理速度，但是，I/O设备之间不能通过单缓冲实现并行操作。双缓冲是一种设备和设备、处理器和设备并行操作的简单模型，但不能用于实际的并行操作。多缓冲是具有多个缓冲区，其中一部分专门用于输入，另一部分专门用于输出的缓冲结构。而缓冲池则把多个缓冲区连接起来统一管理，缓冲池中的每个缓冲区既可用于输入又可用于输出。缓冲区是一种临界资源，所以需要考虑使用缓冲区的申请、释放和互斥问题。

虚设备技术，称为SPOOLing技术，是多道程序设计系统中处理独占I/O设备的一种方法。SPOOLing包括输入程序模块、输出程序模块、作业调度程序三部分。利用输入程序模块，在作业执行前就用慢速设备将作业预先输入到输入井中；作业进入内存运行后，使用数据时，直接从输入井中取出；作业执行时不直接启动外部设备输出数据，只需将数据写入输入井；待作业全部运行完毕，再由外部设备输出全部数据和信息。SPOOLing提高了设备利用率，缩短了用户程序执行时间，但并不提高处理器利用率。