凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

操作系统—— 精髓与设计原理--期末复习_操作系统精髓与设计原理复习

作者：凡人多烦事01 | 2024-02-08 16:00:51

踩

操作系统精髓与设计原理复习

一、计算机系统概述

1、基本构成

计算机有四个主要的结构化部件：

①处理器（Processor）：控制计算机的操作，执行数据处理功能。当只有一个处理器时，它通常指中央处理器（CPU）

②内存（Main memory）：存储数据和程序

③输入/输出模块（I/O modules）：在计算机和外部环境之间移动数据

④系统总线（System bus）：在处理器、内存和输入/输出模块间提供通信的设施

2、部件补充

①存储器地址寄存器（MAR）：确定下一次读/写的存储器地址

②存储器缓存寄存器（MBR）：存放要写入存储器的数据或从存储器读取的数据

③程序计数器（PC）：保存下一次要取的指令地址

④指令寄存器（IR）：存放取到的指令

3、中断

中断最初是用于提高处理器效率的手段。

利用中断功能，处理器可以在I/O操作的执行过程中执行其他指令。

4、重要习题

1.列出简要定义计算机的四个主要组成部分

2.一般而言，一条机器指令能指定的四种不同操作是什么

3.什么是中断

4.多处理器系统和多核系统区别是什么

5.空间局部性和时间局部性的区别是什么

6.开发空间局部性和时间局部性的策略是什么

二、操作系统概述

1、操作系统的目标

操作系统是控制应用程序执行的程序，是应用程序和计算机硬件之间的接口。它有三个目标：

①方便：操作系统使计算机更易于使用

②有效：操作系统允许以更有效的方式使用计算机资源

③扩展能力：在构造操作系统时，应允许在不妨碍服务的前提下，有效的开发、测试和引入新的系统功能。

2、操作系统的概念

操作系统是指控制和管理整个计算机系统的硬件和软件资源，并且合理地自主调度计算机的工作和资源的分配，提供给用户和其他软件比较方便的接口和环境，是计算机系统中最基本的系统软件。

3、操作系统的基本特征

①并发：指两个或多个事件在同一时间间隔内发生，宏观上看是同时发生，微观上看是交替发生的

并行：是指系统具有同时进行运算或操作的特性，在同一时刻能完成两种或以上的工作

PS：单核CPU的程序只能并发执行，多核CPU的程序可以并行执行

②共享：系统中的资源可供内存中多个并发执行的进程共同使用

互斥共享：资源在特定一段时间内只允许一个进程访问该资源

同时共享：一个时间段内允许多个进程同时对某些资源进行访问

③虚拟

④异步：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底。而是走走停停的，以不可预知的速度向前推进。

4、操作系统的功能和接口

操作系统作为系统资源的管理者对资源进行管理：处理机管理、存储器管理、文件管理、设备管理

①处理机管理

在多道程序环境下，处理机的分配和运行都以进程为基本单位，因而对处理机的管理可归纳为对进程的管理

进程管理的主要功能包括：进程控制、进程同步、进程通信、死锁处理、处理机调度

②存储器管理

主要包括：内存分配与回收、地址映射、内存保护与共享和内存扩充

③文件管理

主要包括：文件存储空间的管理、目录管理以及文件读写管理和保护

④设备管理

主要包括：缓冲管理、设备分配、设备处理和虚拟设备

操作系统作为用户与计算机硬件系统之间的接口提供了用户接口：

①命令接口

联机命令接口（交互式命令接口）适用于分时或实时系统的接口

脱机命令接口（批处理命令接口）适用于批处理系统

向上层提供服务：给软件或程序员提供程序接口（系统调用）

②程序接口

程序接口由一组系统调用组成。用户通过在程序中使用这些系如调用来请求操作系统为其提供服务

5、操作系统的发展过程

（1）单道批处理系统

特点：单路性、独占性、自动性、封闭性、顺序性

缺点：系统的资源得不到充分利用

（2）多道批处理系统

特点：多路性、共享性、自动性、封闭性、无序性、调度性

好处：提高CPU利用率，提高内存和I/O设备的利用率，增加系统吞吐量

缺点：平均周转时间长，无交互能力

PS：引入多道程序设计的前提之一是系统具有中断功能

（3）分时系统

允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源

采用“时间片轮转”的处理机调度策略

PS：分时系统的主要目的是比较快速地响应用户

（4）实时系统

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

6、操作系统的运行环境

1.CPU执行两种不同性质的程序：操作系统内核程序、应用程序

操作系统划分为用户态和核心态，严格区分两类程序

用户自编的程序在用户态，操作系统内核程序在核心态

2.内核

是计算机最低层的软件，是计算机功能的延申。包含四个方面内容：

①时钟管理：操作系统需要通过时钟管理向用户提供准确时间，通过时钟中断的管理，可实现进程的切换

②中断机制：引入中断机制的初衷是提高多道程序环境中CPU的利用率

③原语：原语是底层的一些可被调用的公用小程序，他们各自完成一个规定的操作，是不可划分的单位

④系统控制及其数据结构处理

3.中断和异常

本质：发生中断就意味着需要操作系统介入开展管理工作

中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权。

“核心态”→“用户态”的切换是通过执行一个特权指令，将程序状态字(PSW)的标志位设置为“用户态”

4.中断的分类

①内中断（异常）：a、资源中断-指令中断（trap指令）；b、强迫中断（缺页）

②外中断：a、外设请求（中断信号）；b、人工干预（用户强制）

三、进程控制与描述

1、进程的概念

1、定义：进程是程序的一次执行

2、组成：进程由程序控制块（PCB）、程序段、数据段组成

操作系统通过PCB来管理进程，PCB中应该包含操作系统对其进行管理所需的各种信息。

3、组织方式

①链式方式：按照进程状态将PCB分为多个队列，操作系统持有指向各个队列的指针

②索引方式：依据进程的状态不同，建立索引表，操作系统持有指向各个索引表的指针

4、进程的特征

①动态性：进程是程序的一次执行过程，是动态的产生、变化和消亡

②并发性：内存中有多个进程实体，各进程可并发执行

③独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位

④异步性：各个进程按各自独立的、不可预知的速度向前推进，操作系统要提供进程同步机制来解决异步问题

⑤结构性：每个进程都会配置一个PCB

PS：进程和程序本质区别在于：前者可以并发执行，后者不能并发执行

2、进程的状态和切换

1、进程有五个状态：就绪状态、运行状态、阻塞状态、创建状态、终止状态。

创建态：进程在创建时，需要申请一个空白的PCB，向其中填写控制和管理进程的信息完成资源分配，如果创建工作无法完成，此时进程所处的状态称为创建态

运行态：进程占用CPU，并在CPU上运行

就绪态：进程已具备运行条件，但由于未分配CPU无法运行

阻塞态：进程因等待某个事件发生而暂时不能运行

终止态：进程结束或出现错误或被系统终止

2、状态的转换

3、进程通信

1.进程通信是指进程之间的信息交换

PV操作是最低级的通信

高级通信方法主要有三类：

①共享存储（生产者消费者）

②消息传递

③管道通信（pipe文件）

4、线程

1、引入线程的目的正是为了简化进程间的通信，以小的开销来提高进程内的并发程度

线程是进程中执行运算的最小单位，是进程中的一个实体，是被系统独立调度和分派的基本单位。线程不拥有系统资源，但可与同属一个进程的其他线程共享进程拥有的全部资源

一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行

2.线程表示进程的一个控制点。

进程是系统资源分配的单位，线程是处理机调度的单位

3、比较

四、处理机调度

1、基本概念

1、不同的调度算法具有不同的特性，主要的评价准则：

①CPU利用率

②系统吞吐量：单位时间内CPU完成的作业数

③周转时间：从作业提交到作业完成所经历的时间

④等待时间：进程处于等处理机状态的时间之和

⑤响应时间

2、进程调度方式

①非剥夺调度：当一个进程正在处理机上执行，即使有更为重要的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或进入阻塞态，才把处理机分配给更为重要的进程

②剥夺调度：抢占方式，遵循一定的原则。

2、先来先服务算法

FCFS：按照作业到达的先后顺序进行调度

适用情况：作业调度、进程调度

优点：算法实现简单

缺点：对长作业有利，对短作业不利

3、短作业优先算法

SJF：以作业的长短来计算优先级

适用情况：作业调度、进程调度

优点：最短的平均等待时间及平均周转时间

缺点：①必须先知道作业的运行时间

②对长作业不利，会出现饥饿现象

③没有考虑作业的紧迫程度

4、优先级算法

基于进程的紧迫程度，由外部赋予进程相应的优先级，进行调度

适用情况：作业调度、进程调度、I/O调度

优点：用优先级区分紧急程度，运用于实时OS

缺点：可能导致低优先级进程的饥饿

优先级类型：

①静态优先级：在创建进程时确定，其在进程的整个运行期间不变

②动态优先级：在创建进程之初，先赋予一个优先级，然后动态调整

5、时间片轮转算法

RR：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，若进程未到一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队

适用情况：进程调度

属于抢占式算法

优点：公平、响应快、适用于分时OS

缺点：不能区分任务的紧急程度，需要进程切换，消耗较大

6、高相应比优先算法

HRRN：综合考虑作业的等待时间和要求服务的时间

算法规则：在每次调度前，计算各个作业的响应比，选择响应比最高的作业为其服务

适用情况：作业调度、进程调度

优点：综合考虑了等待时间和运行时间

缺点：每次调度前都要计算响应比，增加系统的开销

PS：不会导致饥饿

7、多级反馈队列调度算法

算法规则：设置多个就绪队列，各级队列优先级从高到低，时间片从大到小

每个队列采用FCFS算法

按队列优先级调度

适用情况：进程调度

优点：用优先级区分紧急程度，运用于实时OS

缺点：可能导致低优先级进程的饥饿

五、并发：死锁与饥饿

1、死锁的概念

1.死锁的定义：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象

注意区分：

2.产生死锁的必要条件

①互斥条件：只有对互斥使用的资源才会导致死锁（哲学家的筷子）

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

③循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程请求

④不剥夺条件：进程获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放

2、死锁的预防

死锁的处理就是不允许死锁的发生，分为静态策略（预防死锁）和动态策略（避免死锁）

1.预防死锁：破坏死锁产生的必要条件

2.避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）

3.死锁的检测和解除：允许死锁的发生，不过操作系统会检测出死锁的发生，然后采取某种措施解除死锁

①破坏互斥条件

如果把互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。例如：SPOOLing技术

②破坏不剥夺条件

当某个进程请求新的资源得不到满足时。它必须立即释放保持的所有资源，待以后需要时再重新申请。

③破坏请求和保持条件

可以采用静态分配的方法，即进程在运行请按一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归他所有，该进程就不会再请求别的资源了

④破坏循环等待条件

对所有资源类型进行先行排序（顺序资源分配法）。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序情求资源，同类资源一次申请完

PS：产生死锁的原因可能是：①时间上：调度时机不合适；②空间上：独占资源分配不当

3、死锁的避免--银行家算法

1.系统安全状态

在避免死锁方法中，把系统的状态分为安全和不安全。当系统处于安全状态时可避免发生死锁。

2.安全序列

如果系统按照这种序列分配资源，则么各进程都能顺利完成，只要找出一个安全序列，系统就是安全状态

3.银行家算法

核心思想：在资源分配之前预先判断这次分配是否导致系统进入不安全状态，依此决定是否应答资源分配请求，让该进程先阻塞等待

（1）数据结构

①可利用资源向量Available。长度为m的一维数组，表示还有多少可用资源

②最大需求矩阵Max。表示各进程对资源的最大需求数，n×m矩阵

③分配矩阵Allocation。表示已经给各进程分配了多少资源，n×m矩阵

④需求矩阵Need。表示各进程最多还需要多少资源，Max-Allocation=Need

⑤进程P的请求向量。长度为m的一维数组，表示进程此次申请的各种资源数

（2）算法步骤

④系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。

（3）安全性算法

例：

（1）由题：已占有资源：A：1+1，B：3+6，C：1+5+3+1，D：2+4+2+4

用资源拥有量减去相应已占有资源，再相加：1+5+2+0=8

（2）

（3）

4、死锁的检测与解除

如果系统中既不采用预防死锁也不采用避免死锁的措施，系统应当提供两个算法：

1.死锁检测算法

2.死锁解除算法

六、并发性：互斥与同步

1、同步与互斥的基本概念

1.临界资源：

是一次仅允许一个进程使用的共享资源。各进程采取互斥的方式，实现共享的资源叫做临界资源。属于临界资源的硬件有：打印机；软件有：消息队列、变量、数组、缓冲区。

2.临界区：

每个进程中访问临界资源的那段代码称为临界区，每次只允许一个进程进入临界区，进入后，不允许其他进程进入。

3.进程同步：

同步也称直接制约关系，它指的是多个进程一起完成某个任务，这些进程因为合作、因为需要在某些位置上协调他们的工作次序而产生了某些制约关系。

PS：区分进程同步与进程调度：

①进程调度是为了最大程度利用CPU资源，选用合适的算法调度就绪队列中的进程。

②进程同步是为了协调一些进程以完成某个任务。

4.进程互斥：

互斥也称为间接制约关系，当某个进程A在访问临界区使用临界资源时，另一个进程B必须等待，直到A进程访问结束并释放资源后，B进程才能去访问。

为禁止两个进程同时进入临界区，同步机制应遵守：

①空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区

②忙则等待：当已有进程进入临界区时，其它试图进入的进程必须等待

③有限等待：对请求访问的进程，应保证能在有限时间内进入临界区

④让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待

2、进程同步机制

1.软件同步机制

一个经典的解决方案：Peterson算法

算法思想：为防止两个进程为进入临界区而无限等待，设置变量turn，每个进程先设置自己的标志后，再设置turn标志。这时，同时检测另一个进程状态标志和不允许进入标志。以保证两个进程同时要求进入临界区时，只允许一个进程进入临界区。

算法：


bool flag[2];
int turn=0;
P0 进程:
flag[0]=true;
true=1;
while(flag[1]&&turn==1);
critical section;//临界区
flag[0]=false;
remainder section;//剩余区
P1 进程:
flag[1]=true;
turn=0;
while(flga[0]&&turn==0);
critical section;
flag[1]=false;
remainder section;

Peterson算法用软件方法解决了进程互斥问题，但未遵循让权等待原则。但相较于其他算法，这种解决方案是最好的。

2.硬件同步机制

①关中断

在进入锁测试之前，关闭中断，直到完成锁测试并上锁后才能打开中断

优点：简单、高效

缺点：不适合多CPU系统；只适合操作系统内核进程，不适合用户进程

②利用Test-and-Set指令实现互斥

简称TSL指令，执行过程不允许被中断，即一条原语

优点：实现简单，适用于多CPU系统

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

③利用swap指令直线进程互斥

④实时系统

3、信号量

信号量机制是一种功能性较强的机制，可用来解决互斥和同步问题，它只能被两个标准的原语wait（S）和signal（S）访问，也可记为P操作和V操作

1.整型信号量

被定义为一个用于表示资源数目的整型量S，相应的PV操作：

未遵循“让权等待”原则。

2.记录型信号量

记录型信号量是不存在忙等现象的进程同步机制，现需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程。记录型信号量可描述为：


typedef struct{
    int value;
    struct process*L;
}semaphore;
 
void wait(semaphore S){
    S.value--;
    if(S.value<O){
        add this process to S.L;
        block(S.L);
    }
}
 
void signal(semaphore S){
    S.value++;
    if(S.value<=O){
        remove a process to S.L;
        wakeup(P);
    }
}

PS:①S.value的初值表示系统中某类资源的数目

②对信号量进行的每次P操作，意味着进程请求一个单位的该类资源，这会使系统中可供分配的该类资源数减少一个，当S.value<0时，代表该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，可见，该机制遵循了“让权等待”原则

③对信号量的每次V操作，意味着进程释放一个单位资源，这会使系统中的可供分配的资源数增加一个。若加一后仍然是S.value<=0，则表示在该信号量链表中仍有等待该资源的进程被阻塞，故调用wakeup原语唤醒第一个等待进程

④如果S.value的初值为1，则表示只允许一个进程访问临界资源，此时信号量会转化为互斥信号量

4、信号量基本应用

1.实现多个进程的互斥：

①互斥信号量mutex初值为1

②每个进程中将临界区代码置于P（mutex）和V（mutex）原语之间

③必须成对使用P（mutex）和V（mutex）原语。

遗漏P原语不能保证互斥访问，遗漏V原语不能在使用临界资源后将其释放。

2.实现同步

①分析在需要实现同步关系的地方，即必须保证一前一后执行的两个操作

②设置同步信号量S，初值为0

③在“前操作”之后执行V（S）

④在“后操作”之前执行P（S）

保证了代码4一定是在代码2之后执行的。

PS：当信号量K>0时，表示还有K个资源可用，当信号量<0时，表示有|K|个进程在等待该资源。

mutex小于0时，其绝对值等于等待进入临界区的进程数

5、管程

1.为什么引入管程：

信号量机制存在编写困难、易出错问题，而管程可以让程序员不需要关注PV操作，写程序更加轻松

2.管程定义

管程是一种特殊的软件模块，包含：多个彼此可以交互并共用资源的线程，多个与资源使用有关的变量，一个互斥锁，一个用来避免竞态条件的不变量

3.基本特征：

①模块化

②抽象数据类型

③信息隐藏

④使用的互斥性

6、生产者消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每一次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。生产者、消费者共享一个初始为空、大小为n的缓冲区。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品,否则必须等待。缓冲区是临界资源，各进程必须互斥地访问。

主要的两种关系：
①生产者—消费者之间的同步关系表现为:一旦缓冲池中所有缓冲区均装满产品时,生产者必须等待消费者提供空缓冲区;一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区。

②生产者一消费者之间还有互斥关系:由于缓冲池是临界资源,所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。

实现：

互斥的实现是在同一个进程中进行的一对PV操作。

同步的实现是在两个进程中进行的,在一个进程中执行P操作,在另一个进程中执行V操作。


semaphore mutex=1;//互斥信号量
semaphore empty=n;//同步信号量，空闲缓冲区的数量
semaphore full=0;//同步信号量，产品的数量
producer(){
	while(1){
		生产一个产品;
		P(empty);//消耗一个空闲缓冲区
		P(mutex);
		把产品放入缓冲区
		P(mutex);
		V(full);//增加一个产品 
	}
} 
consumer(){
	while(1){
		P(full);//消耗一个产品
		P(mutex);
		从缓冲区取出一个产品;
		V(mutex);
		V(empty);//增加一个空闲缓冲区
		使用产品; 
	}
}

PS：实现互斥的P操作一定要放在实现同步的P操作之后

7、读者写者问题

要求：①允许多个读者同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作之前，应让已有的读者和写者全部退出

写者进程和任何进程都互斥，设置一个互斥信号量rw，在写者访问文件前后分别执行P、V操作

P(rw)和V(rw)其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第一个访问文件的读进程“加锁”，让最后一个访问完文件的读进程“解锁”。可以设置一个整数变量count来记录当前有几个读进程在访问文件。


semaphore rw=1;
int count=0;
semaphore mutex=1;
int i=0;
writer(){
	while(1){
		P(rw);
		写文件;
		V(rw); 
	}
}
reader(){
	while(1){
		P(mutex);
		if(count==0)//第一个读进程负责加锁
		{
			P(rw);
		 } 
		count++;
		V(mutex);
		读文件;
		P(mutex);
		count--;
		if(count==0)//最后一个读进程负责解锁
		{
			V(rw);
		 } 
		V(mutex);
	}
}

桥上不允许两车交汇，相当于读写互斥。


semaphore mutex=1;//桥的互斥访问信号量
semaphore smutex=1;//作为southcount的互斥访问信号量
semaphore nmutex=1;//作为northcount的互斥访问信号量
int southcount=0;//记录南方向车辆数 
int northcount=0;//记录北方向车辆数
void south(){
	while(1){
		P(smutex);
		if(southcount==0){
			P(mutex);
		}
		southcount++;
		V(smutex);
		南方车辆通过;
		P(smutex);
		southcount--;
		if(southcount==0){
			V(mutex);
		} 
		V(smutex);
	}
} 
void north(){
	while(1){
		P(nmutex);
		if(northcount==0){
			P(mutex);
		}
		northcount++;
		V(nmutex);
		北方车辆通过;
		P(nmutex);
		northcount--;
		if(northcount==0){
			V(mutex);
		} 
		V(nmutex);
	}
}

8、哲学家进餐问题

有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子,平时一个哲学家进行思考,饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。

方法一：至多允许四位哲学家同时拿左筷子，保证至少有一位哲学家可以就餐，不会出现饿死和死锁现象

方法二：仅当哲学家的左右手筷子都拿起时才允许就餐

方法三：规定奇数号哲学家先拿左筷子再拿右筷子，偶数号哲学家相反

七、内存管理

1、内存管理的基本原理和要求

1.内存管理的定义

操作系统对内存的划分和动态分配

2.内存管理的功能

内存空间的分配和回收：由操作系统完成对主存的分配和回收，对编程人员透明。

地址转换：使逻辑地址转换为真实的物理地址

3.程序的装入和链接

创建进程首先要将程序和数据装入内存，将用户源程序变为可在内存中执行的程序。

①步骤描述：

编译：由编译程序将用户源代码编译为若干目标模块

链接：由链接程序将编译后的一组目标模块和所需的库函数链接在一起，形成一个完整的装入模块

装入：由装入程序将装入模块装入内存运行

②程序链接的方式

静态链接：在程序运行之前，先将各目标模块及他们所需的库函数链接成一个可执行程序，此后不再拆开

装入时动态链接：编译后所得的一组目标模块在装入时，边装入边链接

运行时动态链接：对某些目标模块的链接，是在程序执行中需要该目标模块时才进行的。便于修改和更新以及实现对目标模块的共享

③装入内存的方式

绝对装入：在编译时就知道程序将装入的内存具体地址，则编译程序将产生绝对地址的目标代码，而后将程序和数据装入内存，只适用于单道程序环境

可重定位装入：在多道程序环境中，多个目标模块的起始地址均为0开始，装入内存时，通过所分配的内存起始地址加上程序内的相对地址进行地址的动态变换，一次完成，又称为静态重定位

动态运行时装入：模块装入内存后并不立即进行地址转换，而是等到程序执行时才进行。

④逻辑地址空间与物理地址空间

逻辑地址空间:程序编译后的每个模块都是以0开始编址，称为目标模块的逻辑地址。当链接为一个完整的可执行目标程序时，链接程序将按顺序以0开始编址，构造统一的逻辑地址空间

物理地址空间：内存中物理单元的集合，是地址转换的最终地址，当装入程序将可执行代码装入内存中时，必须将逻辑地址转化为物理地址

⑤内存保护

内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响

内存保护的两种方式：

Ⅰ、在CPU中设立一对上、下限寄存器，存放用户作业在主存中的上下限地址，每当CPU要访问一个地址时，先根据这对上下限寄存器判断是否越界访问

Ⅱ、采用冲抵为寄存器和限长寄存器来实现这种保护。重定位寄存器保存最小的物理地址，限长寄存器保存逻辑地址的最大值，进行内存访问时，先判断逻辑地址是否大于限长寄存器值，若未越界，则加上重定位寄存器的值映射成物理地址，再进行内存访问

2、覆盖与交换

覆盖与交换技术是在多道程序环境下扩充内存的两种方法

1.覆盖

早期系统主存小，仅存放一道用户程序,但存储空间放不下用户进程也时有发生，这一问题可以通过覆盖技术解决。覆盖技术的思想:将程序分为多个段(多个模块)。常用的段常驻内存，不常用的段在需要时调入内存。把内存划分为一个固定区和若干个覆盖区，固定区存放用户程序经常活跃的部分，调入后就不再调出(除非运行结束)，其余部分按调用关系分段，将即将访问的段放在覆盖区，需要用到时调入内存，用不到时调出内存。其他放在外存，在需要调用前，系统将其调入覆盖区，替换原有的段。必须由程序员声明覆盖结构，操作系统完成自动覆盖。

2.交换

基本思想:把处于等待状态的进程或者被CPU剥夺运行权限的进程从内存移出到辅存,这一过程称为换出;把准备好竞争CPU的进程从辅存移到内存，这一过程称为换入。暂时换出外存等待的进程状态为挂起状态(挂起态)。挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。

①具有对换功能的操作系统中,通常把磁盘空间分为文件区和对换区两部分，文件区主要用于存放文件,主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式:对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区，由于对换的速度直接影响到系统的整体速度,因此对换区空间的管理主要是求换入换出速度，因此通常对换区采用连续分配方式。总之，对接I/O速度比文件区的更快。

②交换通常在许多进程运行且内存吃紧时运行,而系统负有降低就暂停。例如:在发现许多进程运行时经常发生缺页,就说明内存紧张,此时可以换出一些进程,如果缺页明显下降,就可以暂停换出。

③可换出优先级低的进程:为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间。

(注意,PCB会常驻内存，不会被换出外存)

3、连续分配管理

1.单一连续分配

在单一连续分配方式中，内存被分为：系统区和用户区

系统区通常位于内存的低地址部分，用于存放操作系统系统区，用户区用于存放用户进程相关数据

特点：内存中只能有一道用户程序，独占整个用户区空间

优点：实现简单，无外部碎片；可以采用覆盖技术扩充内存；不一定需要内存保护

缺点：只能用于单用户、单任务的操作系统；有内部碎片，存储器利用率极低

PS：连续存储分配时，存储单元地址一定连续

2.固定分区分配

它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业

两种方法：

①分区大小相等：缺乏灵活性，只适用于一台计算机控制多个相同对象的场合

②分区大小不等：增加了灵活性，可以满足不同大小的进程需求

为便于内存分配，通常将分区按大小排队，建立一张分区说明表

优点：实现简单，无外部碎片

缺点：当用户程序太大，可能所有分区都不能满足需求，此时需要采用覆盖技术来解决，但又会降低性能；会产生内部碎片，内存利用率低

4、动态分区分配

动态分区分配又称可变分区分配,是一种动态划分内存的分区方法。这种分配方式不会预先划分内存分区,而是在进程装入内存时,根据进程的大小动态地建立分区。系统分区的大小和数目是可变的。

两种常用的数据结构:空闲分区表和空闲分区链

①空闲分区表:每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息。

②空闲分区链:每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息。

四种动态分区匹配算法：

（1）首次适应算法（Frist Fit）。空闲分区以地址递增的次序链接，分配内存时顺序查找，找到大小能满足要求的第一个空闲分区

（2）最佳适应算法（Best Fit）。空闲分区按容量递增的方式形成分区链，找到第一个能满足要求的空闲分区

缺点：会产生很多的外部碎片

（3）最坏适应算法（Worst Fit）。空闲分区以容量递减的次序链接，找到第一个能满足要求的空闲分区，即挑选出最大的分区

（4）邻近适应算法（Next Fit）。又称循环首次适应算法，不同之处是，分配内存时从上次查找结束的位置开始继续查找。

5、分页存储管理方式

1.基本分页存储管理方式

算法思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分，分页管理不会产生外部碎片

①页面和页面大小

进程中的块称为页（Page），内存中的块称为页框（Page Frame）。外存也以同样的单位进行划分，直接称为块（Block）。进程在执行时需要申请主存空间，即要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。页面大小应该适中，应为2的整数幂。

②地址结构

即每页大小为4KB，地址空间最多允许2^20页

③页表

为了便于在内存中找到进程每个页面所对应的物理块，系统为每个进程建立一张页表，它记录页面在内存中对应的物理块号，页表一般存放在内存中。

页表是由页表项组成的，页表项由页号和物理内存中的块号组成

④地址变换结构

a、基本的地址变换机构

变换过程计算：设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

①计算页号P=A/L和页内偏移量W=A%L。

②比较页号P和页表长度M，若P>M，则产生越界中断，否则继续执行。

③页表中页号P对应的页表项地址=页表始址F+页号P*页表项长度，取出该页表项内容b，即为物理块号。要注意区分页表长度和页表项长度，页表长度的值表示一共有多少页，页表项长度的值表示页地址占多大存储空间。

④计算E=b*L+W，用得到的物理地址E去访问。

b、具有快表的地址变换机构

快表，又称联想寄存器（TLB）

由于查询快表的速度比查询页表快的多，因此只要快表命中，就可以省略很多时间。因为局部性原理，一般快表的命中率可达99%以上。

解：（1+100）×0.9+（1+100+100）×0.1=111μs

两级页表

6、分段存储管理方式

1.分段：逻辑地址由段号S和段内偏移量W两部分组成

2.段表：每个段表项对应进程的一段，段表项记录该段在内存中的始址和长度。

3.地址变换机构：

在系统中设置了段表寄存器，用于存放段表始址F和段表长度M。

分段和分页管理的对比：

①页是信息的物理单位，段是信息的逻辑单位

②页的大小固定且由系统决定，段的长度不固定

③分页的用户程序地址空间是一维的，分段的用户程序地址空间是二维的。

7、段页式存储管理方式

在段页式系统中，作业的逻辑地址分为三部分：

八、虚拟内存管理

1、虚拟内存的基本概念

传统存储管理方式具有一次性和驻留性的特性。一次性是指作业必须一次性全部嵌入内存后才能开始运行。这会导致大作业无法运行，多道程序并发下降。驻留性是指一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。

1.局部性原理

局部性原理既适用于程序结构，又适用于数据结构

局部性原理体现在两方面：

①时间局部性：通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现

②空间局部性：通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现

2.虚拟存储器的定义和特征

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存

虚拟存储器有三个主要特征：

①多次性：无须在作业运行时一次性地全部装入内存，而允许被分成多次调入内存运行。

②对换性：无须在作业运行时一直常驻内存，而允许在作业的运行过程中进行换进和换出。

③虚拟性：从逻辑上扩充内存的容量，使用户所看到的内存容量远大于实际的内存容量。

3.虚拟内存技术的实现

虚拟内存的实现有三种方式：

①请求分页存储管理

②请求分段存储管理

③请求段页式存储管理

不管哪种方式，都需要有一定的硬件支持

4.请求分页管理方式

请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。

a.页表机制

请求分页系统的页表机制不同于基本分页系统，如图所示：

增加的四个字段：

Ⅰ、状态位P：用于指示该页是否已调入内存，供程序访问时参考

Ⅱ、访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考

Ⅲ、修改位：标识该页在调入内存后是否被修改过

Ⅳ、外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考

b.缺页中断机构

在请求分页系统中，每当所要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞，若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改了页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页。

c.地址变换机构

PS：虚拟存储器容量既不受外存容量限制，又不受内存容量限制，而是由CPU寻址范围决定的

2、页面置换算法

常见的置换算法有以下四种：

1.最佳置换算法（OPT）

算法思想：选择以后永不使用的页面淘汰或者在最长时间内不再被访问的页面，以保证获得最低的缺页率

2.先进先出页面置换算法（FIFO）

算法思想：优先淘汰最早进入内存的页面，即在内存中驻留时间最久的页面

当分配块数量增多，但缺页次数不减反增，这种现象称为Belady异常。FIFO算法会出现Belady异常

3.最近最久未使用置换算法（LRU）

算法思想：选择最近最久时间未访问过的页面予以淘汰

4.时钟置换算法（CLOCK）又称最近未用算法（NRU）

实现方法：

考点：（1）缺页次数（2）页面置换次数（3）缺页率=缺页次数/总页数

置换算法对比：

3、页面分配策略

1.驻留集大小

驻留集：指请求分页存储管理中给进程分配的物理块的集合

若驻留集太小，会导致缺页策略，系统要花大量时间来处理缺页；若驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应采用一定的策略：

①固定分配局部置换：它为每个进程分配一定数目的物理块，在整个运行期间都不改变。

②可变分配全局置换：它为每个进程分配一定数目的物理块，操作系统自身也保持一个空闲物理块队列。

③可变分配局部置换：它为每个进程分配一定数目的物理块，当某个进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，因此不会影响其他进程的运行。

2.调入页面的时机

①预调页策略：根据局部性原理，一次调入若干相邻的页可能会比一次调入一页更高效

②请求调页策略：进程在运行中需要访问的页面不在内存而提出请求，由系统将所需页面调入内存

3.从何处调入页面

①系统拥有足够的对换区空间：可以全部从对换区调入所需页面，以提高调页速度。

②系统缺少足够的对换区空间：凡不会被修改的文件都直接从文件区调入；而当换出这些页面时，不必再换出。对于那些可能被修改的部分，在将它们换出时须调到对换区。

③UNIX方式：与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入。

4.抖动

在页面置换过程中，一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的页面调度行为称为抖动。频繁发生的缺页中断（抖动）的主要原因是：某个进程频繁访问的页面数目高于可用的物理页帧数目

5.工作集

工作集是指在某段时间间隔内，进程要访问的页面集合

一般来说，驻留集的大小不能小于工作集的大小，否则进程运行过程中将频繁缺页。

PS：当系统发生抖动时，可以采取的有效措施：撤销部分进程

九、文件管理

1、文件逻辑结构

1.文件系统基础

①文件的定义：文件是以计算机硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。在系统运行中，计算机以进程为基本单位进行资源的调度和分配，而在用户进行的输入和输出中，则以文件为基本单位。

②文件的属性：文件具有一定的属性，系统不同，属性也会有所不同，但通常都包括如下属性：名称、标识符、类型、位置、大小、保护、时间、日期和用户标识。

③文件的基本操作：操作系统提供系统调用，它对文件进行创建、写、读、重定位、删除和截断等操作。

PS：从用户的观点看，操作系统引入文件系统的目的是：实现对文件的按名存取。

2.文件的逻辑结构

文件的逻辑结构是从用户观点出发看到的文件的组织方式，文件的物理结构是从实体观点出发看到的文件在外村上的存储组织形式。

按逻辑结构，文件可划分为无结构文件和有结构文件。

①无结构文件（流式文件）

无结构文件时最简单的文件组织形式。无结构文件将按顺序组织成记录并积累、保存。它是有序相关信息项的集合，以字节（Byte）为单位。

②有结构文件（记录式文件）

有结构文件按记录的组织形式可分为如下几种：

a.顺序文件

b.索引文件

c.索引顺序文件

d.直接文件或散列文件

解：最好的情况是有 $\sqrt{10000}$ =100组，每组100条记录，因此顺序查找时，平均查找记录个数=50+50=100.

2、文件目录

与文件管理系统和文件集合相关联的是文件目录

1.文件控制块

与进程管理一样，为实现目录管理，操作系统中引入了文件控制块的数据结构，文件控制块（FCB）是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。为了创建一个新文件，系统将分配一个FCB并存放在文件目录中，成为目录项。

FCB包含以下信息：

①基本信息

②存取控制信息

2.目录结构

①单级目录结构：

在整个文件系统中只建立一张目录表，每个文件占一个目录项。

②两级目录结构：

将文件目录分成文件目录和用户文件目录两级。

③多级目录结构：

将两级目录结构层次关系加以推广，就形成了树形目录结构：

④无环图目录结构：

目的是为了实现文件共享。

3.索引结点

除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点，目录项中只包含文件、索引结点指针，因此每个目录项的长度大幅减少。

由于目录项长度减少，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘I/O的次数就少了很多。

3、文件共享

1.基于索引结点的共享方式（硬链接）

索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。若count=2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1。若count >0，说明还有别的用户要使用该文件暂时不能把文件数据删除，否则会导致指针悬空。

2.基于符号链的共享方式（软链接）

为使用户B能共享用户A的一个文件F，可以由系统创建一个LINK类型的新文件,也取名为F，并将文件F写入用户B的目录中，以实现用户B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名。这样的链接方法被称为符号链接。新文件中的路径名只被视为符号链,当用户B要访问被链接的文件F且正要读LINK类新文件时,操作系统根据新文件中的路径名去读该文件,从而实现用户B对文件F的共享。

解析:建立符号链接时，引用计数值直接复制;建立硬链接时，引用计数值加1。删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件不存在，直接删除符号链接;但对于硬链接则不可直接删除，引用计数值减1，若值不为0，则不能删除此文件，因为还有其他硬链接指向此文件。

当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为2-1=1，F2的引用计数值不变。

4、文件保护

1.口令保护

为文件设置一个“口令”，用户想要访问文件时就需要提供口令，由系统验证口令是否正确。

2.加密保护

用一个“密码”对文件加密，用户想要访问文件时，需要提供相同的“密码”才能正确解密。

3.访问控制

用一个访问控制表（ACL）记录各个用户对文件的访问权限。

5、文件的物理结构

文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间方法有三种：

1.连续分配

连续分配方法要求每个文件在磁盘上占有一组连续的块。文件的连续分配可以用第一块磁盘地址和连续快的数量来定义。

优点:实现简单、存取速度快。缺点:文件长度不宜动态增加。

2.链接分配

链接分配采取离散分配的方式，消除了外部碎片，提高了磁盘空间的利用率。分为隐式链接和显式链接两种，

采用链式分配方式(隐式链接)方式的文件,除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。但只支持顺序访问，不支持随机访问，查找效率低。

优点:方便文件拓展。缺点:不会产生碎片问题，外存利用率高。

采用链式分配方式(显式链接)方式的文件，把用于链接文件各物理块的指针显式的放在一张表中,即文件分配表(FAT)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

优点:支持顺序访问，也支持随机访问，查找效率高。缺点：文件分配表需要占用一定的存储空间

3.索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表-一-建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

优点:索引分配方式可以支持随机访问。文件拓展也很容易实现(只需要给文件分配一个空闲块,并增加一个索引表项即可)。缺点:索引表需要占用一定的存储空间。

若磁盘块装不下文件的整张索引表，需要采用以下机制来解决处理这个问题:①链接方案:如果索引表太小，一个索引块装不下，那么可以将多个索引块链接起来存放。②多层索引:建立多层索引，使第一层索引块指向第二层的索引块,还可以根据文件大小的要求再建立第三层、第四层索引块。③混合索引:多种索引分配方式的结合。例如，一个文件的顶级索引表中既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。

分配方式对比：

6、文件存储空间管理

1.文件存储器空间的划分与初始化

一般来说，一个文件存储在一个文件卷中。文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大型文件的文件卷也可由多个物理盘组成。

2.存储空间管理

①空闲表法

空闲表法属于连续分配方式，它与内存动态分配方式类似，为每个文件分配一块连续的存储空间。

如何分配：为一个文件分配连续的存储空间，同样可采取首次适应、最佳适应、最坏适应等算法来决定分配区间。

如何回收磁盘块:与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况。

a.回收区的前后都没有相邻空闲区；

b.回收区的前后都是空闲区;

c.回收区前面是空闲区；

d.回收区后面是空闲区。

总之，回收时需要注意表项的合并问题。

②空闲链表法

a.空闲盘块链:以盘块为单位组成一条空闲链。操作系统保存着链头、链尾指针。

如何分配:若某文件申请K个盘块，则从链头开始依次摘下K盘块分配，并修改空闲链的链头指针。

如何回收:回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

适用于离散分配的物理站构，为文件分配多个盘块时可能更主文多次操作。

b.空闲盘区链:以盘区为单位组成一条空闲链。操作系统保存着链头、链尾指针。

如何分配:若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块,也可以将不同盘区的盘块同时分配给一个文件,注意分配后可能要修改相应的链指针、盘区大小等数据。

如何回收:若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。离散分配、连续分配都适用，为个文件分配多个盘块时效率更高

③位示图法

每个二进制位对应一个盘块，“0”表示空闲，“1”表示已分配

如何分配:若文件需要K个块，先进行顺序扫描位示图,找到K个相邻或不相邻的“0”，再根据字号、位号算出对应的盘块号，将相应盘块分配给文件。最后将相应位设置为“1”。

若n表示字长，则(字号，位号)=(i,j)的二进制位对应的盘块号b=ni+j。b号盘块对应的字号i=b/n;位号j= b%n

如何回收:先根据回收的盘块号计算出对应的字号、位号，再将相应二进制位设为“0”

④成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。

文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。

7、文件的基本操作

1.创建文件

创建文件有两个必要步骤，一是在文件系统中为文件找到空间；二是在目录中为新文件创建条目，该条目记录文件名称、在文件系统中的位置以及其他信息。

2.写文件

为了写文件，执行一个系统调用，指明文件名称和要写入文件的内容，对于给定文件名称，系统搜索目录以查找文件位置。系统必须为该文件维护一个写位置的指针。

3.读文件

为了读文件，执行一个系统调用，指明文件名称和要读入文件块的内存位置。同样，需要搜索目录以找到相关目录项，系统维护一个读位置的指针，每当发生读操作，更新读指针。一个进程通常只对一个文件读或写，因此当前操作位置可以作为每个进程当前文件位置的指针，由于读写操作都使用同一指针，因此节省了空间，也降低了系统复杂度。

4.文件重定位

按某条件搜索目录，将当前文件位置设为给定值，并且不会读写文件。

5.删除文件

先从目录中找到要删除的文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。

6.截断文件

允许文件所有属性不变，并删除文件内容，即将其长度设为0并释放其空间。

7.打开文件

在很多操作系统中，在对文件进行操作之前，要求用户先使用open系统调用打开文件，需要提供的几个主要参数:

①文件存放路径(“D:/Demo”)

②文件名(“text.txt”)

③要对文件的操作类型(如:r只读:rw读写等)

操作系统在处理open系统调用时，主要做了几件事:

①根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。

②将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。

8.关闭文件

进程使用完文件后，要关闭文件。操作系统在处理Close系统调用时，主要做了：

①将进程的打开文件表相应表项删除;

②回收分配给该文件的内存空间等资源;

③系统打开文件表的打开计数器count减1，若count =0，则删除对应表项。

8、文件系统的层次结构

十、I/O设备管理

1、I/O设备的基本概念和分类

1.计算机系统中的I/O设备按使用特性可分为：

1)人机交互类外部设备，用于与计算机用户之间交互的设备，如打印机、显示器、鼠标、键盘等。这类设备的数据交换速度相对较慢，通常是以字节为单位进行数据交换的。

2）存储设备，用于存储程序和数据的设备，如磁盘、磁带、光盘等。这类设备用于数据交换，速度较快，通常以多字节组成的块为单位进行数据交换。3）网络通信设备，用于与远程设备通信的设备，如各种网络接口、调制解调器等。其速度介于前两类设备之间。网络通信设备在使用和管理上与前两类设备也有很大不同。

除了上面最常见的分类方法，IIO设备还可以按以下方法分类。

1）按传输速率分类

①低速设备,传输速率仅为每秒几字节到数百字节的一类设备,如键盘、鼠标等。

②中速设备，传输速率为每秒数千字节至数万字节的一类设备，如行式打印机、激光打印机等。

③高速设备，传输速率在数百千字节至千兆字节的一类设备，如磁带机、磁盘机、光盘机等。

2)按信息交换的单位分类

①块设备，由于信息的存取总是以数据块为单位的，所以存储信息的设备称为块设备。它属于有结构设备，如磁盘等。磁盘设备的基本特征是传输速率较高、可寻址，即对它可随机地读/写任一块。

②字符设备，用于数据输入/输出的设备为字符设备，因为其传输的基本单位是字符。它属于无结构类型，如交互式终端机、打印机等。它们的基本特征是传输速率低、不可寻址，并且在输入/输出时常采用中断驱动方式。

2、I/O控制方式

设备管理的主要任务之一是控制设备和内存或处理机之间的数据传送。外围设备和内存之间的输入/输出控制方式有4种，下面分别加以介绍:

1）程序直接控制方式

如图所示，计算机从外部设备读取数据到存储器，每次读一个字的数据。对读入的每个字,CPU需要对外设状态进行循环检查,直到确定该字已经在I/O控制器的数据寄存器中。在程序直接控制方式中,由于CPU的高速性和I/O设备的低速性，致使CPU的绝大部分时间都处于等待I/O设备完成数据IO的循环测试中，造成了CPU资源的极大浪费。

程序直接控制方式虽然简单且易于实现但其缺点也显而易见，由于CPU和I/O设备只能串行工作，导致CPU利用率低

2）中断驱动方式

中断驱动方式的思想是，允许IIO设备主动打断CPU的运行并请求服务，从而“解放”CPU,使得其向I/o控制器发送读命令后可以继续做其他有用的工作。如图所示，我们从IIO控制器和CPU两个角度分别来看中断驱动方式的工作过程。

中断驱动方式比程序直接控制方式有效,但由于数据中的每个字在存储器与IIO控制器之间的传输都必须经过CPU，这就导致了中断驱动方式仍然会消耗较多的CPU时间。

3）DMA方式

在中断驱动方式中，IlO设备与内存之间的数据交换必须经过CPU中的寄存器，所以速度还是受限，而DMA(直接存储器存取)方式的基本思想是在IIO设备和内存之间开辟直接的数据交换通路,彻底“解放”CPU。DMA方式的特点如下:

①基本单位是数据块;

②所传送的数据，是从设备直接送入内存的，或者相反;

③仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在DMA控制器的控制下完成的。

要在主机与控制器之间实现成块数据的直接交换,须在DMA控制器中设置如下4类寄存器。

①命令/状态寄存器(CR)。用于接收从CPU发来的IIO命令或有关控制信息，或设备的状态。

②内存地址寄存器(MAR)。在输入时，它存放把数据从设备传送到内存的起始目标地址:在输出时，它存放由内存到设备的内存源地址。

③数据寄存器(DR)。用于暂存从设备到内存或从内存到设备的数据。

④数据计数器(DC)。存放本次要传送的字(节)数。

DMA方式的工作过程如下:

CPU接收到IO设备的DMA请求时，它给IIO控制器发出一条命令，启动DMA控制器，然后继续其他工作。之后CPU就把控制操作委托给DMA控制器，由该控制器负责处理。DMA控制器直接与存储器交互，传送整个数据块，每次传送一个字，这个过程不需要CPU参与。传送完成后，DMA控制器发送一个中断信号给处理器。

DMA控制方式与中断驱动方式的主要区别:

中断驱动方式在每个数据需要传输时中断CPU,而DMA控制方式则是在所要求传送的一批数据全部传送结束时才中断CPU;此外，中断驱动方式数据传送是在中断处理时由CPU控制完成的，而DMA控制方式则是在DMA控制器的控制下完成的。

4）通道控制方式

I/O通道是指专门负责输入/输出的处理机。

I/O通道方式是DMA方式的发展，它可以进一步减少CPU的干预，即把对一个数据块的读或写)为单位的干预，减少为对一组数据块的读(或写)及有关控制和管理为单位的干预。同时又可以实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

I/O通道与DMA方式的区别:DMA方式需要CPU来控制传输的数据块大小、传输的内存位置，而通道方式中这些信息是由通道控制的。另外，每个DMA控制器对应一台设备与内存传递数据，而一个通道可以控制多台设备与内存的数据交换。

3、I/O软件层次结构

为了使复杂的IIO软件具有清晰的结构、良好的可移植性和适应性，在IIO软件中普遍采用了层次式结构，将系统输入/输出功能组织成一系列的层次，每层都利用其下层提供的服务，完成输入/输出功能中的某些子功能，并屏蔽这些功能实现的细节，向高层提供服务。

一个比较合理的层次划分如图所示。整个IIO系统可以视为具有4个层次的系统结构，各层次及其功能如下:

1)用户层IIO软件。实现与用户交互的接口，用户可直接调用在用户层提供的、与I/O操作有关的库函数，对设备进行操作。

2）设备独立性软件。用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护及设备分配与释放等，同时为设备管理和数据传送提供必要的存储空间。设备独立性也称设备无关性，使得应用程序独立于具体使用的物理设备。

使用逻辑设备名的好处是:①增加设备分配的灵活性;②易于实现IO重定向。

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

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

5)硬件设备。IIO设备通常包括一个机械部件和一个电子部件。

设备控制器的主要功能如下:

1)接收和识别CPU或通道发来的命令，如磁盘控制器能接收读、写、查找等命令。

2）实现数据交换，包括设备和控制器之间的数据传输;通过数据总线或通道，控制器和主存之间的数据传输。

3）发现和记录设备及自身的状态信息，供CPU处理使用。

4）设备地址识别。

为实现上述功能,设备控制器必须包含以下组成部分:

①设备控制器与CPU的接口。该接口有三类信号线:数据线、地址线和控制线。

②设备控制器与设备的接口。设备控制器连接设备需要相应数量的接口，一个接口连续一台设备。每个接口中都存在数据、控制和状态三种类型的信号。

③I/O控制逻辑。用于实现对设备的控制。

类似于文件系统的层次结构，例如，当用户要读取某设备的内容时，通过操作系统提供的read命令接口，这就经过了用户层。

操作系统提供给用户使用的接口，一般是统一的通用接口,也就是几乎每个设备都可以响应的统一命令，如read命令，用户发出的read命令，首先经过设备独立层进行解析，然后再交往下层。

接下来，不同类型的设备对read命令的行为会有所不同，如磁盘接收read命令后的行为与打印机接收read命令后的行为是不同的。因此，需要针对不同的设备，把read命令解析成不同的指令，这就经过了设备驱动层。

命令解析完毕后，需要中断正在运行的进程，转而执行read命令，这就需要中断处理程序。最后，命令真正抵达硬件设备，硬件设备的控制器按照上层传达的命令操控硬件设备，完成相应的功能。

系统只要按设备类型配置设备驱动程序即可。

4、I/O子系统概述

1）I/O调度概念

I/O调度就是确定一个好的顺序来执行这些I/O请求。磁盘调度算法就是I/O调度的一种。

2）磁盘高速缓存(Disk Cache)

操作系统中使用磁盘高速缓存技术来提高磁盘的I/O速度,对高速缓存复制的访问要比原始数据访问更为高效。

不过，磁盘高速缓存技术不同于通常意义下的介于CPU与内存之间的小容量高速存储器，而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。因此,磁盘高速缓存逻辑上属于磁盘,物理上则是驻留在内存中的盘块。高速缓存在内存中分为两种形式:

①在内存中开辟一个单独的存储空间作为磁盘高速缓存，大小固定;

②把未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘I/O时共享。

3)缓冲区(Buffer)

在设备管理子系统中，引入缓冲区的目的主要如下:

①缓和CPU与IIO设备间速度不匹配自的矛盾;

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

③解决基本数据单元大小(即数据粒度)不匹配的问题;

④提高CPU和1/O设备之间的并行性;

5、设备分配与回收

1）设备分配概述

设备分配是指根据用户的I/O请求分配所需的设备。分配的总原则是充分发挥设备的使用效率,尽可能地让设备忙碌，又要避免由于不合理的分配方法造成进程死锁。从设备的特性看，分为独占设备、共享设备和虚拟设备。

①独占式使用设备。是指在申请设备时,若设备空闲，则将其独占，不再允许其他进程申请使用，一直等到该设备被释放才允许其他进程申请使用。

②分时式共享使用设备。独占设备时通过分时共享使用提高利用率。

③以SPOOLing方式使用外部设备。SPOOLing技术（假脱机I/O技术)，是指对I/O操作进行批处理。SPOOLing技术实质上是一种用空间换时间的技术。

2）设备分配的数据结构
设备分配依据的主要数据结构有设备控制表(DCT)、控制器控制表(COCT)、通道控制表(CHCT)和系统设备表(SDT)，各数据结构功能如下。设备控制表(DCT):我们可以认为，一个设备控制表就表征一个设备，而这个控制表中的表项就是设备的各个属性，如图所示。

每个设备都分为机械部件和电子部件两部分，其中负责解析上层传达的命令并控制机械部件运作的是电子部件(控制器)，所以每个DCT者需要一个表项来表示控制器，即需要一个指向控制器控制表(COCT)的指针，因此DCT与COCT有一一对应的关系。

现代操作系统的I/O控制采用的都是通道控制。设备控制器控制设备与内存交换数据,而设备控制器又需要请求通道为它服务，因此每个COCT必定有一个表项存放指向相应通道控制表(CHCT)的指针,而一个通道可为多个设备控制器服务，因此CHCT中必定有一个指针，指向一个表，这个表上的信息表达的是CHCT提供服务的那几个设备控制器。CHCT与COCT的关系是一对多的关系。

系统设备表(SDT):整个系统只有一张SDT,如图所示。它记录已连接到系统中的所有物理设备的情况，每个物理设备占一个表目。

3）设备分配的策略

①设备分配原则。设备分配应根据设备特性、用户要求和系统配置情况。分配的总原则是:既要充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户程序和具体设备隔离开。

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

静态分配主要用于对独占设备的分配,它在用户作业开始执行前，由系统一次性分配该作业所要求的全部设备、控制器(如通道等)。

动态分配在进程执行过程中根据执行需要进行。当进程需要设备时,通过系统调用命令向系统提出设备请求，由系统按照事先规定的策略给进程分配所需要的设备、I/O控制器，一旦用完，便立即释放。

③设备分配算法。常用的动态设备分配算法有先请求先分配、优先级高者优先等。

对于独占设备，既可以采用动态分配方式，又可以采用静态分配方式，但往往采用静态分配方式，即在作业执行前，将作业所要用的这一类设备分配给它。共享设备可被多个进程所共享，一般采用动态分配方式，但在每个I/O传输的单位时间内只被一个进程所占有，通常采用先请求先分配和优先级高者优先的分配算法。

4）设备分配的安全性

设备分配的安全性是指设备分配中应队方止发生进程死锁。

①安全分配方式。

每当进程发出I/O话请求后便进入阻塞态，直到其IO操作完成时才被唤醒这样，一旦进程已经获得某种设备后便阻塞，不能再请求任何资源，而且在它阻塞时也不保持任何资源。

②不安全分配方式。

进程在发出I/O请求后继续运行，需要时又发出第二个、第三个I/O请求等。仅当进程所请求的设备已被另一进程占用时，才进入阻塞态。

6、SPOOLing技术

为了缓和CPU的高速性与I/O设备低速性之间的矛盾，引入了脱机输入/输出技术。该技术利用专门的外围控制机,将低速I/O设备上的数据传送到高速磁盘上，或者相反。SPOOLing的意思是外部设备同时联机操作，又称假脱机输入/输出操作，是操作系统中采用的一项将独占设备改造成共享设备的技术。

SPOOLing系统的组成如图所示。

1)输入井和输出井

输入井和输出井是指在磁盘上开辟出的两个存储区域。

输入井模拟脱机输入时的磁盘，用于收容IlO设备输入的数据。输出井模拟脱机输出时的磁盘，用于收容用户程序的输出数据。

2）输入缓冲区和输出缓冲区

输入缓冲区和输出缓冲区是在内存中开辟的两个缓冲区。

输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。输出缓冲区用于暂存从输出井送来的数据，以后再传送到输出设备。

3）输入进程和输出进程

输入进程模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井。当CPU需要输入数据时,直接将数据从输入井读入内存。输出进程模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井,待输出设备空闲时,再将输出井中的数据经过输出缓冲区送到输出设备。共享打印机是使用SPOOLing技术的一个实例，当用户进程请求打印输出时，SPOOLing系统同意为它打印输出，但并不真正立即把打印机分配给该用户进程,而只为它做两件事:

①由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中;

②输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中再将该表挂到请求打印队列上。

SPOOLing系统的主要特点有：提高了I/O的速度；将独占设备改造为共享设备；实现了虚拟设备功能。