1 操作系统概述

1.1 介绍

1、计算机系统：

计算机硬件

计算机软件：系统软件、支撑软件、应用软件

2、操作系统概念

操作系统是最接近硬件的一层软件，是最基本的系统软件，是用户与计算机硬件系统之间的接口，是系统资源的管理者。

1.2 发展和分类

1、手工操作阶段

缺点：人机速度矛盾

2、批处理操作系统

（1）单道批处理操作系统（引入脱机输入输出技术）

优点：缓解人机速度矛盾

缺点：资源利用率依然很低

（2）多道批处理操作系统（操作系统开始出现）

优点：多道程序并发执行，资源利用率高，系统吞吐量大

缺点：作业的平均周转时间长，不提供人机交互功能

3、分时操作系统

时间片：作业能够连续使用CPU的最长时间，通常是几十毫秒

优点：提供人机交互功能，多路性、独立性、及时性、交互性（最重要的特征之一）

缺点：不能优先处理紧急任务

4、实时操作系统

（1）硬实时系统

必须在绝对严格的规定时间内完成处理

（2）软实时系统

能接受偶尔违反时间规定

优点：能优先处理紧急任务

实时操作系统不强求系统资源的利用率，及时性、可靠性都很高

5、微机操作系统

6、网络操作系统

7、分布式操作系统

8、嵌入式操作系统

1.3 特征和功能

（1）特征

并发性、共享性、虚拟性、异步性

（2）功能

处理器管理、存储器管理、设备管理、文件管理、提供用户接口

（3）用户接口

命令接口(CLI)、应用程序接口(API)、图形接口(GUI)

1.4 详细介绍

1.4.1 运行机制

（1）运行状态

内核是操作系统最核心最重要的部分，也是最接近硬件的部分，但是操作系统的功能未必都在内核中，如图形化用户界面 GUI

CPU有两种状态，“内核态”和“用户态”

处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令

处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令

1、CPU中有一个寄存器叫程序状态字寄存器（PSW），其中有个二进制位，1表示“内核态”，0表示“用户态”
2、别名：内核态=核心态=管态；用户态=目态

内核态 --> 用户态：==执行一条特权指令一一修改PSW的标志位为“用户态”==，这个动作意味着操作系统将主动让出CPU使用权
用户态 --> 内核态：==由“中断”引发，硬件自动完成变态过程==，触发中断信号意味着操作系统将强行夺回CPU的使用权

除了非法使用特权指令之外，还有很多事件会触发中断信号。一个共性是，但凡需要操作系统介入的地方，都会触发中断信号

1.4.2 中断和异常

（1）内中断：与当前执行的指令有关，中断信号来源于CPU内部，又称为异常

（2）外中断：与当前执行的指令无关，中断信号来源于CPU外部，又称为中断，如时钟部件发来的信号

1.4.3 系统调用

在Unix/Linux中，应用程序接口又称为系统调用，通常使用访管指令来实现（SVC）。

调用程序运行在用户态，被调用过程运行在系统态，需要通过中断及陷入机制，由用户态转到系统态，才能转向相应的内核执行被调用过程。

==访管指令是一种特殊的非特权指令==

1.4.4 内核结构

结构	描述	优点	缺点
整体结构	所有的系统功能都放在内核里（大内核结构的OS通常也采用了“模块化“的设计思想）	系统效率高、性能好，	模块独立性差，调用关系复杂，维护和扩充困难
模块结构	将内核划分为多个模块，各模块之间相互协作。	1.模块间逻辑清晰易于维护，确定模块间接口后即可多模块同时开发， 2.支持动态加载新的内核模块（如：安装设备驱动程序、安装新的文件系统模块到内核），增强OS适应性 3.任何模块都可以直接调用其他模块，无需采用消息传递进行通信，效率高	模块间的接口定义未必合理、实用模块间相互依赖，更难调试和验证
层次结构	内核分多层，每层只能单向调用更低一层提供的接	1.便于调试和验证，自底向上逐层调试验证 2.易扩充和易维护，各层之间调用接口清晰固定	1.仅可调用相邻低层，难以合理定义各层的边界 2.效率低，不可跨层调用，系统调用执行时间长
微内核结构	只把中断、原语、进程通信等最核心的功能放入内核。进程管理、文件管理、设备管理等功能以用户进程的形式运行在用户态	1. 内核小功能少、易于维护，内核可靠性高 2.内核外的某个功能模块出错不会导致整个系统崩溃	1. 性能低，需要频繁的切换用户态/核心态。 2. 用户态下的各功能模块不可以直接相互调用，只能通过内核的“消息传递“来间接通信

题目

下列说法正确的有（）
A、Win7是单用户单任务操作系统
B、Unix是多用户多任务操作系统
C、Linux是单用户多任务操作系统
D、鸿蒙是多用户多任务操作系统
E、Android是多用户多任务操作系统
B D E

2 进程管理

2.1 进程概念

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

2.1.1 特征

1、动态性（最基本的特征）

2、并发性：内存中的多个进程能在一段时间内同时交替运行

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

4、异步性：各进程以不可预知的速度向前推进，可能导致运行结果的不确定性

2.1.2 组成

1、程序段：程序的代码（指令序列）

2、数据段：运行过程中产生的各种数据（如：程序中定义的变量）

3、堆栈，包括内核栈和用户栈

4、进程控制块（PCB, Process Control Block）：进程描述信息、进程控制和管理信息、资源分配清单、处理机相关信息

2.1.3 状态及转化

1、状态：运行状态、就绪状态、阻塞状态、创建状态、终止状态

2、状态转化：

就绪态一>运行态：进程被调度

运行态一>就绪态：时间片到，或CPU被其他高优先级的进程抢占

运行态一>阻塞态：等待系统资源分配，或等待某事件发生（主动行为）

阻塞态一>就绪态：资源分配到位，等待的事件发生（被动行为）

创建态一>就绪态：系统完成创建进程相关的工作

运行态一>终止态：进程运行结束，或运行过程中遇到不可修复的错误

2.2 进程控制

进程控制包括创建、撤销、状态转化等，使用一组原语来实现。

原语用关/开中断来实现，原语是一种特殊的程序，原语的执行必须一气呵成，不可中断

包括：进程的创建、进程的终止、进程的阻塞、进程的唤醒、进程的切换

2.3 进程通信

进程通信：多个并发运行的协作进程通常需要进行信息交换，就是进程通信。

低级通信方式：锁机制、信号量机制

高级通信机制：共享存储器系统通信、消息传递系统通信、管道通信、客户-服务器系统通信

2.3.1 共享存储器系统通信

设置一个共享内存区域，并映射到进程的虚拟地址空间

要互斥地访问共享空间（由通信进程自己负责实现互斥）

特点：没有中间环节，通信双方直接读写共享存储分区而实现信息交换，通信速度快

2.3.2 消息传递系统通信

（1）定义

传递结构化的消息（消息头/消息体），操作系统提供“发送/接受原语”

（1）两种方式

直接通信方式：消息直接挂到接收进程的消息队列里

间接（信箱）通信方式：消息先发到中间体（信箱）

2.3.3 管道通信

（1）定义

设置一个特殊的共享文件（管道），其实就是一个内存缓冲区，管道文件又称为FIFO文件

一个管道只能实现半双工通信

实现双向同时通信要建立两个管道

各进程要互斥访问管道（由操作系统负责实现互斥）

管道写满时，写进程阻塞。管道读空时，读进程阻塞

（2）实现机制

1、无名管道

存在于高速缓存中的临时文件，没有对应的磁盘映像，常用于有亲缘关系的父子进程或兄弟进程之间的通信，由系统调用pipe()建立。进程使用完后将其关闭，管道文件不复存在

2、有名管道

在文件系统中长期存在的具有路径名的文件，由系统调用mkfifo()建立，是一种特殊的文件。

2.3.4 客户-服务器系统通信

socket实现，RPC远程过程调用

2.4 线程机制

2.4.1 线程的资源

线程一般有线程ID、寄存器、用户栈和内核栈、私有存储区（存放很少的私有数据）、线程控制块TCB，线程共享所属进程的资源

线程是调度和执行的基本单位，进程是资源分配和拥有的基本单位

2.4.2 实现机制

1、实现方式

（1）用户级线程（User Level Threads, ULT）

从用户视角能看到的线程，由线程库实现，操作系统调度还是以进程为单位

1.用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）

2.用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。

3.在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程“

优缺点
优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

（2）内核级线程：从操作系统视角看到的线程，由操作系统实现

1.内核级线程的管理工作由操作系统内核完成。

2.线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。

3.操作系统会为每个内核级线程建立相应的TCB （ Thread Control Block，线程控制块），通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”

4.优缺点

优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

==内核级线程才是处理机分配的单位==

（3）组合方式：上述两种方式的结合

2、多线程模型

（1）一对一模型

用户级线程映射到一个内核级线程

优：各个线程可分配到多核处理机并行执行，并发度高

缺：线程管理都需要操作系统支持，开销大

（2）多对一模型

多个用户级线程映射到一个内核级线程

优：线程管理开销小效率高

缺：一个线程阻塞会导致整个进程都被阻塞（并发度低）

（3）多对多模型

n个用户级线程映射到m个内核级线程（n≥m），集前二者之所长

2.5 进程调度

调度：系统按照一定的原则选择某个作业或者进程来占用资源参与运行

2.5.1 调度概念

（1）调度层次

1、高级调度（作业调度、长程调度）

按照某种规则从后备队列中选择合适的作业将其调入内存，并为其创建进程

外存 --> 内存（面向作业），发生频率：最低，以分钟或者小时单位计

2、中级调度（中程调度、对换调度）

当内存紧张时，将暂时不运行的进程换出到外存，此时的进程称为挂起状态

当内存充裕时，按照某种规则，从挂起队列中选择合适的进程将其数据调回内存

外存 --> 内存（面向进程），发生频率：中等，几秒一次

目的：提高系统的内存利用率和系统吞吐量

3、低级调度（进程调度、短程调度）

按照某种规则从就绪队列中选择一个进程为其分配处理机

内存 --> CPU，发生频率：最高，十几毫秒一次

（2）调度功能

排队程序、分派程序、上下文切换程序

（3）调度方式

非抢占式、抢占式

（4）调度时机

1.可以调度的时机

1、当前运行进程已结束或无法再继续运行下去

2、对于抢占式，出现优先级更高的就绪进程时

2.不能调度的情况

1、在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。

2、进程在操作系统内核程序临界区中。

3、在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列）

CAUTION

进程在==操作系统内核程序临界区==中==不能进行调度与切换==

进程处于临界区时可以进行处理机调度

（普通临界区访问的临界资源不会直接影响操作系统内核的管理工作，因此==在访问普通临界区时可以进行调度与切换，如打印机==）

（5）调度性能的评价指标

1、CPU的利用率

$利用率 = \frac{忙碌的时间}{使用时间}$

2、系统吞吐量

$系统吞吐量 = \frac{总共完成了多少道作业}{总共花了多少时间}$

3、周转时间和带权周转时间

周转时间 = 完成时间 - 提交时间

$带权周转时间 = \frac{周转时间}{实际运行时间}$ ，带权周转时间>=1，越小越好

4、响应时间

5、对截止时间的保证

2.5.2 调度算法

（1）先来先服务算法（First-Come, First-Served, FCFS）

按照作业/进程到达的先后顺序进行服务

1、非抢占式
2、优点
公平、算法实现简单
3、缺点
排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法==对长作业有利，对短作业不利==
4、不会导致饥饿

（2）短作业优先调度算法（Shortest-job-First, SJF）

最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）

1、有抢占式和非抢占式两种，获得是最短的平均周转时间及较高的系统吞吐量
2、优点
“最短的”平均等待时间、平均周转时间
3、缺点
不公平。==对短作业有利，对长作业不利==。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
4、会导致饥饿

（3）高相应比优先算法（Highest Response Ratio First, HRRF）

在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务

$响应比 = \frac{要求服务时间 + 等待时间}{要求服务时间}$

1、非抢占式
2、综合考虑了等待时间和运行时间（要求服务时间）。等待时间相同时，要求服务时间短的优先（SJF的优点）；要求服务时间相同时，等待时间长的优先（FCFS 的优点）。对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
3、不会导致饥饿

（4）时间片轮转调度算法（Round-Robin, RR）

按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

1、抢占式
2、优点：公平，响应快，适用于分时操作系统
3、缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
4、不会导致饥饿

NOTE

1、如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大 2、另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

（5）优先级调度算法

调度时选择优先级最高的作业/进程

1、抢占式和非抢占式都有
2、优点
用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
3、缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
4、会导致饥饿

（6）多级反馈队列调度算法

1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

2.新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾

3.只有第k级队列为空时，才会为k+1级队头的进程分配时间片

1、抢占式
2、比较平衡
3、会导致饥饿

（7）多级队列调度算法

系统中按进程类型设置多个队列，进程创建成功后插入某个队列

1、优点：实现简单，调度开销小
2、缺点：不够灵活
3、会导致饥饿

2.6 进程同步

2.6.1 基本概念

1、进程同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

2、互斥

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

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

临界区是进程中访问临界资源的代码段，临界区也可称为“临界段”。
进入区和退出区是负责实现互厅的代码段。

3、遵循的原则

1.空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；

2.忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；

3.有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；

4.让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

2.6.2 进程同步机制

（1）硬件方法

1、禁止中断

优点：简单高效
缺点：只适用于单处理机；只适用于操作系统内核进程

2、专用机器指令

TSL（Test and Set Lock）指令、Swap指令

优点：实现简单；适用于多处理机环境；
缺点：不满足“让权等待”

（2）软件方法

（3）锁机制

1、需忙等，进程时间片用完才下处理机，违反“让权等待” 2、优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低 3、==常用于多处理器系统==，一个核忙等，其他核照常工作，并快速释放临界区 4、不太适用于单处理机系统，忙等的过程中不可能解锁

（4）信号量机制

1、整型信号量

用一个整数型变量作为信号量，数值表示某种资源数

整型信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作

整型信号量存在的问题：==不满足让权等待原则==

2、记录型信号量

S.value 表示某种资源数，S.L指向等待该资源的队列

P 操作中，一定是先S.value--，之后可能需要执行block原语

wait(S){
	S.value --;
	if (s.value < 0) block(S.list);
}

V 操作中，一定是先S.value++，之后可能需要执行wakeup原语

signal(){
	S.value ++;
	if (S.value <= 0) wakeup(S.list);
}

可以用记录型信号量实现系统资源的"申请"和"释放“

可以用记录型信号量实现进程互厅、进程同步

当S > 0时，==其值表示当前可供分配的资源数目==
当S < 0时，==其绝对值表示阻塞队列中的等待进程数目==

3、用记录型信号量实现互斥和同步

1）实现进程互斥

1.分析问题，确定临界区

2.设置互斥信号量，初值为1

3.临界区之前对信号量执行 P 操作

4.临界区之后对信号量执行V操作

2）实现进程同步

1.分析问题，找出哪里需要实现”一前一后"的同步关系

2.设置同步信号量，初始值为0

3.在"前操作"之后执行V 操作

4.在"后操作"之前执行 P 操作

3）实现进程的前驱关系

1.分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题

2.为每一对前驱关系设置同步信号量，初值为0

3.在每个"前操作"之后执行V 操作

4.在每个"后操作"之前执行 P 操作

如果同时有互斥和同步的P操作，先实现同步的，再实现互斥的，否则会产生死锁
对于同时有互斥和同步的V操作，顺序没有关系，但是一般也还是先同步的，再互斥的。

（5）管程机制

1、组成

共享数据结构、对数据结构初始化的语句、一组用来访问数据结构的过程(函数）

2、基本特征

各外部进程/线程只能通过管程提供的特定”入口材能访问共享数据

每次仅充许一个进程在管程内执行某个内部过程

1、各进程必须互斥访问管程的特性是由==编译器==实现的
2、可在管程中设置==条件变量==及等待/唤醒操作以解决同步问题
3、管程不是系统调用，是编程语言成分，由编译器实现

2.7 死锁

2.7.1 概念

1、定义

死锁：各进程互相等待对方丰里的资源，无法回前推进，导致各进程都阻塞

2、原因

根本原因：资源有限并且分配不当

1）资源

资源分为可重用资源和消耗性资源，可重用资源分为可剥夺资源和不可剥夺资源

对==不可剥夺资源==和==消耗性资源==的竞争，可能会产生死锁，对可剥夺资源的竞争不会

3、必要条件

互斥条件：对必须互斥使用的资源的争抢才会导致死锁

不可剥夺条件：进程保持的资源只能主动释放，不可强行剥夺

占有且等待条件：保持着某些资源不放的同时，请求别的资源

循环等待条件：存在一种进程资源的循环等待链，==循环等待未必死锁，死锁一定有循环等待==

2.7.1 处理死锁

（1）预防死锁

核心：破坏死锁产生的四个必要条件

1、破环占有且等待条件

运行前分配好所有需要的资源，之后一直保持

缺点：资源利用率低；可能导致饥饿

2、破环不可剥夺条件

方案一，申请的资源得不到满足时，立即释放拥有的所有资源

方案二，申请的资源被其他进程占用时，由操作系统协助剥夺（考虑优先级）

缺点：实现复杂；剥夺资源可能导致部分工作失效；
反复申请和释放导致系统开销大；可能导致饥饿

3、破环循环等待条件

给资源编号，必须按编号从小到大的顺序申请资源

缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦

（2）避免死锁

核心：避免系统进入不安全状态（银行家算法）

1、查找安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个，如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源前总是要考虑到最坏的情况。

2、如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）。因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想

银行家算法的局限性：

1）系统中进程数量及资源数量众多，而且每当进程申请资源时都要运行该算法，因此算法本身的运行开销大

2）银行家算法是按照最严苛的条件判断安全性的，过于保守，会降低资源利用率及延迟进程推进速度

3）银行家算法在寻找安全序列时完全没有考虑进程之间的同步关系：相互协作进程间的前驱后继关系，这在实际系统中是很不现实的

（3）检测和解除死锁

核心：允许死锁发生，系统负责检测出死锁并解除

1）检测

1、数据结构：资源分配图

2、两种结点：进程结点、资源结点

3、两种边：

进程结点 --> 资源结点（请求边）

资源节点 --> 进程结点（分配边）

2）解除

资源剥夺法、撤销进程法（终止进程法）、进程回退法

系统中有N台打印机，M个进程共享打印机资源，每个进程要求K台。当M的取值不超过（）时，系统不会发生死锁。

解：==M*(K-1)+1<=N==

2.8 题目

在Linux的shell中输入一个命令时，shell会创建一个新进程来执行这个命令。
正确

UNIX系统中进程的进程控制块中常驻内存的是（）
A.proc结构 B.user 结构 C.proc结构和user 结构
A
proc结构体常驻内存，用于存储进程状态、执行优先级等关键信息，而user结构体可能被交换到磁盘，仅保留当前进程的user结构体在内存中。进程的状态信息和控制信息等由 proc 结构体和 user 结构体管理。每个进程各自会被分配1 组上述结构体的实例。 proc 结构体常驻内存，而 user 结构体有可能被移至交换空间

若一个进程实体由PCB、共享正文段、数据堆段和数据栈段组成，则下列说法正确的有（）
A.全局赋值变量位于数据堆段中 B.未赋值局部变量位于数据栈段中 C.函数调用实参传递值位于数据栈段中 D.使用malloc （）申请的动态分配的存储区位于数据堆段 E.常变量（如100， “abc”）位于共享正文段中 F.进程的优先级位于共享正文段
B C D E，C语言程序中二进制代码、常量、赋值全局变量都在正文段中

在Linux中，创建一个共享内存段的系统调用是（）。
A.msgget() B.creatshm() C.shmget() D.shmat()
C

关于Linux的管道通信机制，以下说法正确的是（）。
A.无名管道由一组VFS对象来实现，存在于内存的高速缓存中，没有对应的磁盘映像 B.有名管道是利用共享文件来实现的，因此管道大小是由文件系统决定的 C.由于管道是单向通信的，因此一个管道只能有一个读进程和一个写进程 D.使用mkfifo()系统调用创建一个有名管道时，系统会为其建立一个i节点，并同时分配若干磁盘空间以存放管道文件内容
A

下列关于线程的叙述中，正确的是（）
A.线程包含CPU现场，可L以独立执行程序 B.每个线程有自己独立的地址空间 C.一个进程只能包含一个线程 D.线程之间的通信必须使用系统调用函数
A

下列关于线程的描述中，正确的有（）
A.内核级线程的调度由操作系统完成 B.操作系统将为每个用户级线程建立一个线程控制块 C.用户级线程间的切换比内核级线程间的切换效率高 D.用户级线程机制可以在任意操作系统上实现 E.同一进程中的各个线程都拥有各自不同的地址空间
A C D

由一个进程中的线程切换到另一个进程中的线程时，一定需要操作系统内核的参与。
正确

线程机制中，一个进程可以包含多个线程；一个线程也可以属于多个进程。
错误

对于纯用户级线程，其调度是由运行在用户态下面的线程库来完成的，因此两个纯用户级线程的切换将不会引起进程的切换。
错误

在多进程的系统中，肯定不会因为竞争内存而产生死锁。
正确，内存是可剥夺性资源

3 存储器

3.1 存储器管理概述

3.1.1 存储器管理功能

1、内存的分配和回收

2、地址映射

3、内存的共享与保护

（1）上下界寄存器保护

下界寄存器：存放开始地址（首址）

上界寄存器：存放末地址

判断越界：
==判别式：下界寄存器 ≤ 物理地址 ≤ 上界寄存器==

（2）界地址保护

基址寄存器：存放开始地址（首址）

限长寄存器 ：存放程序长度（字节数）

判断越界：
==判别式：逻辑地址<限长寄存器==

4、内存扩充

3.1.2 程序的装入和链接

程序经过编译、链接后生成的指令中指明的是逻辑地址（相对地址），即：相对于进程的起始地址而言的地址

链接方式	装入方式
静态链接	绝对装入
装入时动态链接	静态重定位装入
运行时动态链接	动态重定位装入

3.2 存储器管理方式

3.2.1 连续存储器管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间。

3.2.1.1 固定分区方式

将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业或者程序。可分为分区大小相等和分区大小不等

3.2.1.2 可变分区方式

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

（1）分配算法

1、首次适应算法

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

如何实现：空闲分区==以地址递增的次序排列==。每次分配内存时顺序查找空闲分区链（或空闲分区表），==找到大小能满足要求的第一个空闲分区。==

2、最佳适应算法

算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区即，优先使用更小的空闲区。

如何实现：空闲分区==按容量递增次序（由小到大）==链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到==大小能满足要求的第一个空闲分区。==

缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

3、最坏适应算法

算法思想：为了解决最佳适应算法的问题一一即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现：空闲分区==按容量递减次序（由大到小）==链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到==大小能满足要求的第一个空闲分区。==

算法	算法思想	分区排列顺序	优点	缺点
首次适应	从头到尾找适合的分区	空闲分区以地址递增次序排列	综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序
最佳适应	优先使用更小的分区，以保留更多大分区	空闲分区以容量递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片：算法开销大，回收分区后可能需要对空闲分区队列重新排序
最坏适应	优先使用更大的分区，以防止产生太小的不可用的碎片	空闲分区以容量递减次序排列	可以减少难以利用的小碎片	大分区容易被用完，不利于大进程；算法开销大（原因同上）

（2）回收

1、上邻接

2、下邻接

3、上下邻接（空闲分区数-1）

4、无邻接（空闲分区数+1）

3.2.1.3 对比

	固定分区方式	可变分区方式
优点	实现简单，无外部碎片	无内部碎片
缺点	分区内部可能存在空间的浪费，存在内部碎片，降低了内存的利用率	有外部碎片，可以使用"紧凑"技术来解决

3.2.2 非连续存储器管理方式

3.2.2.1 分页存储管理

1、将内存的物理空间和程序逻辑空间分成大小相等的块，具体大小==由CPU硬件机构决定==。在逻辑空间中的块成为页面（虚页），在物理空间中的块称为物理块（页框、帧、实页）。

每个页面大小和页框大小相等

2、逻辑地址结构：

==页号P + 页内地址d（又称为页内偏移量）==

其中页面的大小决定了页内地址的位数，页号位数决定了逻辑地址空间中页面的总数
==页面大小决定了页内偏移量==

3、地址映射公式

给定逻辑地址A，页面大小L，那么（INT代表向下取整，mod是取余除法）：

页号P = INT（A/L） 页内地址d = A mod L

4、页表

页表记录了页号到物理块号的映射关系，每个进程都有一张页表，页表通常存在PCB（进程控制块）中。

==页表存放在内存系统区的一个连续空间中，进程的PCB存有进程页表在内存的首地址和页表长度；==

1、一个进程对应一张页表
2、进程的每个页面对应一个页表项
3、每个页表项在逻辑上由 “页号”和“块号”组成，==在物理存储上只存储物理块号，页号不占用存储空间==
4、页表记录进程页面和实际存放的内存块之间的映射关系
5、i号页表项存放地址 = 页表始址 + i* 页表项大小

5、地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

设页面大小为L，逻辑地址A到物理地址E的变换过程如下：（1）计算页号P和页内偏移量W （如果用十进制数手算，则 P=A/L，W=A%L；但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量）

（2）比较页号P和页表长度M，若 P>=M，则产生越界中断，否则继续执行。（注意：页号是从O开始的，而页表长度至少是1，因此 P=M 时也会越界）

（3）页表中页号P对应的页表项地址=页表起始地址F+页号P* 页表项长度，取出该页表项内容b，即为内存块号。

（4）计算 E=b *L+ W，用得到的物理地址E去访存。（如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了）

TIP

页表长度指的是这个页表中==总共有几个页表项，即总共有几个页==；

页表项长度指的是==每个页表项占多大的存储空间==；

页面大小指的是==一个页面占多大的存储空间==；

==总共需要两次访存，第一次访存：查页表；第二次访存：访问目标内存单元==

在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此，==页式管理中地址是一维的==。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。

	地址变换过程	访问一个逻辑地址的次数
基本地址变换机构	1、算页号、页内偏移量 2、检查页号合法性 3、查页表，找到页面存放的内存块号 4、根据内存块号与页内偏移量得到物理地址 5、访问目标内存单元	两次
具有快表的地址变换机构	1、算页号、页内偏移量 2、检查页号合法性 3、查快表。若命中，即可知道页面存放的内存块号，可直接进行`5`，若未命中则进行`4` 4、查页表，找到页面存放的内存块号，并且将页表项复制到快表中 5、根据内存块号与页内偏移量得到物理地址 6、访问目标内存单元	快表命中，只需一次访存快表未命中，需要两次访存

6、多级页表

1、若采用多级页表机制，则各级页表的大小不能超过一个页面
2、多级页表的访存次数（假设没有快表机构），==N级页表访问一个逻辑地址需要N+1次访存==

3.2.2.2 分段存储管理

1、介绍

进程的地址空间：按照==程序自身的逻辑关系==划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址，每个段都是存储有逻辑意义的一组相关信息

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高。

2、逻辑地址结构

==段号P + 段内地址d==

段号的位数决定了每个进程最多可以分几个段
段内地址位数决定了每个段的最大长度是多少

3、段表

程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。

1、进程的段表存放在内存中，==段表在内存的始址及长度则保存在进程的PCB中==
2、段表项由==段号、段长和段基址==三部分构成，每个段的长度不一定相同
3、每个段表项的长度是相同的
4、分段可以实现信息的共享，进行==共享的代码不能是临界资源==

4、地址变换机构

通常会在系统中设置一个段表寄存器（PTR），存放段表在内存中的起始地址F和段表长度M。进程未执行时，段表的始址和段表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

设段表始址F，段表长度为M，逻辑地址A到物理地址E的变换过程如下：（1）根据逻辑地址得到段号S、段内地址W

（2）判断段号是否越界。若S>=M，则产生越界中断，否则继续执行（注意：段号是从O开始的，而段表长度至少是1，因此 P=M 时也会越界）

（3）查询段表，找到对应的段表项，段表项的存放地址为F+S*段表项长度

（4）==检查段内地址是否超过段长。若W>=C，则产生越界中断，否则继续执行==

（5）计算得到物理地址，访问目标单元

3.2.2.3 分页和分段的对比

分页	分段
页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。页的大小是固定的。	段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。段长是可变的
页的大小固定且由系统决定。	段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。	分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
分页（单级页表），第一次访存一一查内存中的页表，第二次访存一一访问目标内存单元。总共两次访存	分段：第一次访存一一查内存中的段表，第二次访存一一访问自标内存单元。总共两次访存
	分段比分页更容易实现信息的共享和保护
内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片	如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片
不方便按照逻辑模块实现信息的共享和保护	很方便按照逻辑模块实现信息的共享和保护

3.2.2.4 段页式存储管理

1、介绍

将进程按逻辑模块分段，再将各段分页，将内存空间分为大小相同的内存块/页框/页帧/物理块，将各页面分别装入各内存块中。

段的长度可能不是页面大小的整数倍，所以在段的最后一页可能会产生内部碎片。

2、逻辑地址结构

将原本的段式存储的地址：==段号P + 段内地址d（又称为页内偏移量）==中的段内地址进行拆分，形成==段号P + 页号d + 页内偏移量==。

1、段号的位数决定了每个进程最多可以分几个段
2、页号位数决定了每个段最大有多少页
3、页内偏移量决定了页面大小、内存块大小是多少
4、“分段”对用户是可见的，程序员编程时需要显式地给出段号、段内地址。而将各段 “分页” 对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。因此段页式管理的地址结构是==二维的==。

3、和段式存储中的段表对比，和页式存储中的页表对比

段页式存储中，每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号（页表起始地址）组成。每个段表项长度相等，段号是隐含的。每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的。

4、地址变换

1.由逻辑地址得到段号、页号、页内偏移量

2.段号与段表寄存器中的段长度比较，检查是否越界

3.由段表始址、段号找到对应段表项

4.根据段表中记录的页表长度，检查页号是否越界

5.由段表中的页表地址、页号得到查询页表，找到相应页表项

6.由页面存放的内存块号、页内偏移量得到最终的物理地址

7.访问目标单元

访存次数：三次，第一次——查段表、第二次一一查页表、第三次一一访问目标单元

3.2.3 虚拟存储系统

3.2.3.1 介绍

1、基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

2、在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

3、若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

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

5、虚拟内存的实现需要建立在离散分配的内存管理方式之上

6、虚拟内存的实现：请求分页存储管理、请求分段存储管理、请求段页式存储管理

虚拟存储系统特定：
多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
置换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
传统存储管理方式
一次性：作业必须一次全部调入内存
驻留性：作业数据在整个运行期间都会常驻内存

3.2.3.2 请求分页存储管理方式

（1）概述

请求分页存储管理方式在基本分页存储管理系统基础之上，增加了==请求调页功能和页面置换功能==。

（2）页表

新增字段
1、状态位P，表示是否已调入内存
2、访问字段A，记录页面被访问的情况
3、修改位M，表示页面装入内存之后是否被修改过，供页面置换参考
4、外存地址，记录页面在外存上的地址

（3）缺页中断机构

功能：

1、找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断

2、缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面

3、缺页中断属于内中断，属于内中断中的"故障"，即可能被系统修复的异常

4、一条指令在执行过程中可能产生多次缺页中断

（4）地址变换机构

1、找到页表项是需要检查页面是否在内存中

2、若页面不再内存中，需要请求调页

3、若内存空间不够，还需换出页面

4、页面调入内存后，需要修改相应页表项

CAUTION

在具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是：查快表（未命中）一一查慢表（发现未调入内存）——调页（调入的页面对应的表项会直接加入快表）一一查快表（命中）一一访问目标内存单元

3.2.3.3 页面置换算法

（1）最佳置换算法（Optional，OPT）

每次选择淘汰的页面将是==以后永不使用，或者在最长时间内不再被访问==的页面，这样可以保证最低的缺页率。

在实际实现中，无发预知页面走向，所以最佳置换算法只是理论上的算法，实际上无法实现。

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

每次选择淘汰的页面是最早进入内存的页面

TIP

只有FIFO算法会产生Belady异常，即：

当为进程分配的物理块数增大时，缺页次数不减反增的异常现象

（3）最近最久未使用置换算法（Least Recently Used，LRU）

每次淘汰的页面是最近最久未使用的页面。实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面

NOTE

一般来说，LRU算法的性能较好，接近于OPT置换算法。

如果经常出现访问较长时间以前曾经访问过的页面，性能会变差

需要移位寄存器和栈等硬件支持

==实际中更常用的是LFU和CLOCK算法==

（4）最近最少使用置换算法（Least Frequently Used，LFU）

LFU存储的是页面被访问的频次，每次淘汰访问次数最少的页面

（5）时钟置换算法（CLOCK）

又称为最近未用算法（Not Recently Used，NRU）

	算法规则	优缺点
OPT	优先淘汰最长时间内不会被访问的页面	缺页率最小，性能最好，但无法实现
FIFO	优先淘汰最先进入内存的页面	实现简单；但性能很差，可能出现`Belady异常`
LRU	优先淘汰最近最久没访问的页面	性能很好：但需要硬件支持，算法开销大
CLOCK（NRU）	循环扫描各页面第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。若第一轮没选中，则进行第二轮扫描。	实现简单，算法开销小；但未考虑页面是否被修改过。
改进型的CLOCK（改进型的NRU）	若用（访问位，修改位）的形式表述，则第一轮：淘汰（0,0）第二轮：淘汰（0,1），并将扫描过的页面访问位都置为0 第三轮：淘汰（0,0）第四轮：淘汰（0, 1)	算法开销较小，性能也不错

3.2.3.3 页面分配策略

1、驻留集

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

（1）固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变

（2）可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少即，驻留集大小可变

（3）局部置换：发生缺页时只能选进程自己的物理块进行置换。

（4）全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

2、页面置换策略

（1）固定分配局部置换：进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页

（2）可变分配全局置换：只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面

（3）可变分配局部置换：频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块。直到缺页率合适

3、抖动

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为==抖动，或颠簸==。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）

4、工作集

在某段时间间隔里，进程实际访问页面的集合。驻留集大小一般不能小于工作集大小

3.3 题目

在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是（）
A、编辑
B、编译
C、链接
D、装载
C

在分页存储管理方式中，如果采用单级页表，则进程的页表会（）。
A、连续存放在进程用户区
B、离散存放在进程用户区
C、连续存放在系统内核区
D、离散存放在系统内核区
C

链接过程中需要完成的工作有（）
A、修改指令中的相对地址
B、修改指令中的绝对地址
C、完成地址映射
D、修改外部调用符号
A D，地址映射是在装入阶段

采用段式存储管理时，一个程序如何分段是在（）时决定的
A、分配主存时
B、用户编程时
C、装入作业时
D、程序执行时
B

已知系统为32位实地址，采用48位虚拟地址，页面大小4KB，页表项大小为8B。假设系统使用纯
页式存储，若最高级页表能保存在一个块内，则要采用（）。
A、单级页表
B、二级页表
C、三级页表
D、四级页表
D （48-12）/ （12-3）向上取整

某系统采用基址、限长寄存器方法进行存储保护，在这种方法中下列判断是否越界的判别式中正确的是（）：
A、被访问的物理地址<基址寄存器的内容
B、被访问的物理地址≤基址寄存器的内容
C、被访问的逻辑地址<限长寄存器的内容
D、被访问的逻辑地址≤限长寄存器的内容
C

请求分页存储管理中发生的缺页中断属于（)
A.I/O中断
B.硬件故障
C.程序中断
D.访管中断
C

在虚拟存储系统中，完成地址转换工作的是（）。
A.硬件
B.地址转换程序
C.装入程序
D.编译程序
A，地址映射机构是硬件

理论上虚拟内存的最大容量只受（）的限制
A.计算机字长
B.内存容量
C.硬盘容量
D.计算机的地址位数
D

系统“抖动”现象发生的原因是（)
A.置换算法选择不当
B.交换信息量过大
C.内存容量不足
D.请求页式管理方案
A

假设系统有m个内存块供分配，初始时全空，页面引用串长度为p，包含了n个不同的页号，则无论用什么页面置换算法，缺页次数不会少于（）。
A. m
B. p
C. n
D. min(m,n)
C

3.下列哪些存储分配方案可能使系统抖动（） 1.动态分区分配 2.简单页式分配 3.虚拟页式 4.简单段页式 5.简单段式 6.虚拟段式
A.1 2 5 B. 3 4 C.只有3 D. 3 6
D

在采用请求分页式存储管理的系统中，地址变换过程可能会因为下列哪些原因而产生中断（）。
1.地址越界 2. 缺页 3.访问权限错误 4.存取控制
A. 1 2
B. 2 3
C. 1 2 3
D. 1 3 4
A

请求分页存储管理中发生的缺页中断属于（) A.I/O中断
B.硬件故障
C.程序中断
D.访管中断
C

在Linux系统中，当一个普通文件处于“未打开”状态时，文件所占用的资源有（）
A.一个文件目录项 B.一个磁盘索引节点项 C.—个或多个磁盘块 D.一个文件控制块FCB E.用户文件描述符表中的一个登记表项
A B C

分页存储管理中的分页是由（）完成的
A.硬件 B.编译程序 C.程序员 D.链接程序
A

4 设备管理

4.1 设备管理的功能

设备分配、缓冲管理、设备处理（设备驱动）

4.2 I/O系统

4.2.1 设备的分类

1、按照数据传输速率分类

高速设备（磁盘、光盘、U盘）
中速设备（打印机、扫描仪）
低速设备（鼠标、键盘）

2、按照信息交换单位分类

==块设备（传输快，可寻址，一般采用DMA控制）==
==字符设备（传输慢，不可寻址，常采用中断驱动方式控制）==

3、按照设备共享属性分类

独占设备，一般位低速I/O设备，如打印机
共享设备
虚拟设备

4、按照工作特性分类

存储设备，又称为块设备
I/O设备，又称为字符设备

4.2.2 设备控制器

（1）功能

接受和识别CPU发出的命令（要有控制寄存器）
数据交换（要有数据寄存器，暂存输入/输出的数据）
地址识别（由I/O逻辑实现）
数据缓冲
向CPU报告设备的状态（要有状态寄存器）
差错控制

（2）组成

==CPU与控制器之间的接口（实现控制器与CPU之间的通信），又叫系统接口==
I/O逻辑（负责识别CPU发出的命令，并向设备发出命令）
==控制器与设备之间的接口（实现控制器与设备之间的通信），又叫设备接口==

（3）两种寄存器编址方式

1、内存映射I/O：控制器中的寄存器与内存统一编制，可以采用对内存进行操作的指令来对控制器进行操作
2、寄存器独立编制：控制器中的寄存器独立编制，需要设置专门的指令来操作控制器

4.2.3 I/O通道

（1）I/O通道，位于CPU和设备控制器之间，用来完成原来由CPU处理的I/O任务，一种硬件

NOTE

特点：

1、有自己的指令系统，能按照指定的要求独立地完成输入输出操作

2、用于实现数据在内存与外设之间的直接传输，让CPU与设备并行工作

3、指令系统简单，一般只有数据传送指令、设备控制指令等

4、没有自己的内存，与CPU共享内存

（2）通道类型

1）字节多路通道，以字节为单位传输数据，以时分复用的方式可以同时执行几个通道程序，管理堕胎设备，通常用于管理多个低速设备或者中速设备

2）数据选择通道，一次只执行一个通道程序，实现数据的成批传送，通常用于管理高速设备

3）数据多路通道，结合之间的两种方式的特点

（3）通道程序，与一般的机器指令不同

TIP

==一个通道可控制多个设备控制器，每个设备控制器可控制多个设备。==

4.2.4 I/O系统结构

分为总线型I/O系统和通道型I/O系统结构

4.3 I/O控制方式

控制方式	完成一次读/写的过程	CPU干预频率	每次I/O数据传输单位	数据流向	优点	缺点
程序直接控制方式	CPU发出I/O命令后需要不断轮询	极高	字	设备->CPU->内存内存->CPU->设备	实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可	CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于 “忙等”状态，CPU利用率低
中断驱动方式	CPU发出I/O命令后可以做其他事，本次l/O完成后设备控制器发出中断信号	高	字	设备->CPU->内存内存->CPU->设备	CPU和I/O设备可并行工作，CPU利用率得到明显提升	每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。
DMA（直接存储器存取）方式	CPU发出I/O命令后可以做其他事，本次I/O完成后DMA控制器发出中断信号	中	块	设备->内存内存->设备	数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。	CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块
通道控制方式	CPU发出I/O命令后可以其他事。通道会执行通道程序以完成/O，完成后通道向CPU发出中断信号	低	一组块	设备->内存内存->设备	CPU、通道、 I/O设备可并行工作，资源利用率很高。	实现复杂，需要专门的通道硬件支持

每一个阶段的优点都是解决了上一阶段的最大缺点。总体来说，整个发展过程就是要尽量减少CPU对I/O过程的干预，把CPU从繁杂的I/O控制事务中解脱出来，以便更多地去完成数据处理任务。

4.4 I/O软件

I/O软件采用层次结构进行组织，从上到下一次分为用户进程、设备独立性软件、设备驱动程序、设备中断处理程序、硬件。下面分别介绍每个层次的功能。

设备中断处理程序和设备驱动程序与硬件相关
设备独立性软件和用户进程与硬件无关

4.4.1 用户进程

实现与用户交互的接口，向上提供方便易用的库函数，Spooling技术的实现等

4.4.2 设备独立性软件

1、对设备命名，建立逻辑设备名到物理设备名的映射关系

2、提供设备保护

3、提供与设备无关的逻辑块

4、实现缓冲技术

5、出错处理

6、向上层提供统一的调用接口（如 read/write 系统调用）

7、根据设备类型选择调用相应的驱动程序

==设备独立性是指用户程序独立于具体物理设备的一种特性==

4.4.3 设备驱动程序

设置设备寄存器、检查设备状态

4.4.4 设备中断处理程序

进行中断处理

4.4.5 硬件

执行I/O操作，由机械部件、电子部件组成

4.6 设备分配

1、设备分配中的数据结构

（1）设备控制表（DCT）

每个设备对应一张DCT，关键字段：类型/标识符/状态/指向COCT的指针/等待队列指针

（2）控制器控制表（COCT）

每个控制器对应一张COCT，关键字段：状态/指向CHCT的指针/等待队列指针

（3）通道控制表（CHCT）

每个通道对应一张CHCT，关键字段：状态/等待队列指针

（4）系统设备表（SDT）

记录整个系统中所有设备的情况，每个设备对应一个表目，关键字段：设备类型/标识符/DCT/驱动程序入口

2、设备分配算法

先来先服务算法、优先级高者优先算法

3、设备分配过程

（1）根据进程请求的物理设备名查找SDT （注：物理设备名是进程请求分配设备时提供的参数）

（2）根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程。

（3）根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。

（4）根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。

只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送

4.5 缓冲管理

4.5.1 概述

1、作用或目的

（1）缓和CPU与VO设备之间速度不匹配的矛盾
（2）减少对CPU的中断频率，放宽对CPU中断相应时间的限制
（3）解决数据粒度不匹配的问题
（4）提高CPU与I/O设备之间的并行性

2、缓冲与高速缓存的区别

区别	高速缓存	缓冲
存放数据	存放的是低速设备上某些数据的拷贝，即高速缓存上的数据低速设备上一定有	存放的是低速设备上传输给高速设备的数据（或者相反），这些数据在低速设备（或高速设备）上不一定有
目的	存放的是高速设备经常要访问的数据，如果高速设备要访问的数据不在高速缓存中，则需要访问低速设备	缓和高速设备与低速设备之间速度不匹配的矛盾，提高两者的并行性

4.5.2 实现机制

1、单缓冲

假设设备把数据输入到缓冲区的时间为T，缓冲区到用户区传输时间为M，CPU的处理时间为C。

那么系统对每一块的处理时间为==Max(C,T) + M==

2、双缓冲

假设设备把数据输入到缓冲区的时间为T，缓冲区到用户区传输时间为M，CPU的处理时间为C。

那么系统对每一块的处理时间为：

==1）如果C<T，那么为MAX((C+M)，T)==

==2）如果C>T，那么为MAX((T+M)，C)==

3、循环缓冲

4、缓冲池

（1）三个队列：空缓冲队列、输入队列、输出队列

（2）四种工作缓冲区:

用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区

用于收容输出数据的工作缓冲区、用于提取输出数据的工作缓冲区

WARNING

当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；

当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。

4.7 Spooling技术

1、脱机技术：

外围控制机+更高速的设备——磁带

作用：缓解设备与CPU的速度矛盾，实现预输入、缓输出

2、假脱机技术

（1）输入井和输出井，是在磁盘上开辟的存储区，模拟脱机输入/输出时的磁带

（2）输入进程和输出进程，模拟脱机输入/输出时的外围控制机

（3）输入缓冲区和输出缓冲区，内存中的缓冲区，输入、输出时的"中转站

4.8 题目

通道用于实现（）之间的信息传输。
A.内存与外设
B.CPU与外设
C.外存与外设
D.用户进程与外设
A

5 文件管理

5.1 概述

文件是具有符号名、在逻辑上有完整意义的一组相关信息项的有序集合

文件的属性：文件名、标识符、类型、位置、大小、保护信息……

5.1.1 文件的分类

1、按照文件用途分类
系统文件、库文件和用户文件
2、按照文件保护级别
只读文件、读写文件、只执行文件、不保护文件
3、按照文件的存取方法
顺序存取文件和随机存取文件
4、操作系统中的分类
Windows中：普通文件和目录文件
Unix和Linux中：普通文件、目录文件和特殊文件
特殊文件：FIFO文件（管道文件）、字符设备文件、块设备文件、符号链接文件（软连接）

5.1.2 文件系统的功能

（1）文件存储空间的管理

（2）文件目录管理

（3）文件地址映射

（4）文件读写管理

（5）文件共享和保护

NOTE

文件系统最基本的功能是==实现文件的“按名存取”==

5.2 文件结构

文件的结构包含文件的逻辑结构和文件的物理结构

文件的逻辑结构是面向用户的文件组织方式和构造方式

文件的物理结构是文件在存储介质上的组织方式

5.2.1 文件的逻辑结构

文件的逻辑结构可以分为==有结构文件和无结构文件==

（1）有结构文件

1、有结构文件，由一组相似的记录组成，又称==记录式文件==。每条记录由若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字。

2、根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。

3、有结构文件的逻辑结构

1）顺序文件

顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。

按照记录是否定长，可分为定长记录顺序文件和变长记录顺序文件

按照是否按照关键字的顺序排列，分为串结构和顺序结构

TIP

串结构：记录之间的顺序与关键字无关，通常按照记录存入的时间决定记录的顺序，每次检索时需要从头开始查找，比较耗时

顺序结构：记录之间的顺序按关键字顺序排列，可以使用高效的查找算法，检索效率高

==定长记录顺序文件可以方便地实现随机存取，变长记录不可以==

NOTE

顺序文件的优缺点

优点：顺序存取时效率高

缺点：不利于文件记录的增加和删除

2）索引文件

为每个逻辑文件建立一张索引表，每条记录占一个表项，表项中存放记录地关键字、长度和起始位置，逻辑文件不再保存记录的长度，索引表和逻辑文件构成索引文件。这样就实现了：

==变长记录顺序文件的顺序检索 ==》定长记录索引文件的随机检索==

NOTE

索引文件的优缺点

优点：可以随机访问，有利于文件的增加和删除

缺点：增加了存储空间的开销

3）索引顺序文件

1、将记录分组，每组对应一个索引表项

2、检索记录时先顺序查索引表，找到分组，再顺序查找分组

3、当记录过多时，可建立多级索引表

4）直接文件和散列文件

（2）无结构文件

在无结构文件中，文件内部的数据就是一系列二进制流或字符流组成，又称==流式文件==

1、在无结构文件中，其长度按照==字节==进行计算
2、在UNIX、Linux及Windows系统中，所有的文件都被看作流式文件

5.2.2 文件的物理结构

物理块（又称为磁盘块或簇）是磁盘上一组连续扇区，它是文件分配和传输信息的基本单位。

常用的文件物理结构有连续文件、链接文件和索引文件。

（1）连续文件

1、连续文件又称为顺序文件，要求文件在磁盘上占有一组连续的块。

2、在文件目录中需要存放==文件的长度==和==其起始盘块号==

优点：支持顺序访问和直接访问（即随机访问）：连续分配的文件在顺序访问时速度最快
缺点：不方便文件拓展（动态增长）；存储空间利用率低，会产生磁盘碎片

（2）链接文件

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

1）隐式链接

1、在隐式链接中，除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。

2、文件目录包括文件第一块的指针和最后一块的指针（或者起始盘块号和长度）。

优点：很方便文件拓展，不会有碎片问题，外存利用率高。
缺点：==只支持顺序访问，不支持随机访问==，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间；如果某个磁盘块出现故障，会导致后续的盘块指针丢失，可靠性较差。

2）显式链接

1、显式链接，把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，File Allocation Table）。一个磁盘只会建立一张文件分配表。开机时文件分配表从外存读入内存，并常驻内存。

2、其中，FAT表项包括物理块号和下一块，但是FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此 “物理块号” 字段可以是隐含的。

3、在文件目录中只需记录文件的起始块号即可。

优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且==支持随机访问==。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点：文件分配表的需要占用一定的存储空间。

（3）索引文件

1、单级索引文件

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块，数据存放的磁盘块称为数据块。

在文件目录中只需要记录文件的索引指针。

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

CAUTION

每个文件对应一张索引表，每个磁盘对应一张FAT表

2、多级索引文件

对于大文件，其索引表本身会占用很多个磁盘块，为此提出了多级索引。

==采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作==

优点：提供对大文件的支持
缺点：访问磁盘的次数随着索引级数的增加而增多；即使是小文件，访问一个数据块依然需要K+1次读磁盘

3、混合索引文件

混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索表）。

CAUTION

（1）Unix System V：

i节点中的物理地址字段iaddr(13)：

iaddr(0)~iaddr(9)：直接地址

iaddr(10)：一级索引

iaddr(11)：二级索引

iaddr(12)：三级索引

（2）Linux ext: i节点中的物理地址字段iaddr(15)：

iaddr(0)~iaddr(11)：直接地址

iaddr(12)：一级索引

iaddr(13)：二级索引

iaddr(14)：三级索引

优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

（4）对比

分配方式	如何实现	目录项内容	优点	缺点
顺序分配	为文件分配的必须是连续的磁盘块	起始块号、文件长度	顺序存取速度快，支持随机访问	会产生碎片，不利于文件拓展
链接分配（隐式链接）	除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针	起始块号、结束块号	可解决碎片问题，外存利用率高，文件拓展实现方便	只能顺序访问，不能随机访问。
链接分配（显式链接）	建立一张文件分配表（FAT)显式记录盘块的先后关系（开机后FAT常驻内存）	起始块号	除了拥有隐式链接的优点之外，还可通过查询内存中的FAT实现随机访问	FAT需要占用一定的存储空间
索引分配	为文件数据块建立索引表若文件太大，可采用链接方案、多层索引、混合索引	链接方案记录的是第一个索引块的块号，多层/混合索引记录的是顶级索引块的块号	支持随机访问，易于实现文件的拓展	索引表需占用一定的存储空间。访问数据块前需要先读入索引块。若采用链接方案，查找索引块时可能需要很多次读磁盘操作。

5.2.3 文件存取

存储介质类型	磁盘	磁盘	磁盘	磁带
物理结构	连续文件	链接文件	索引文件	连续文件
存取方法	顺序、随机	顺序	顺序、随机	顺序

5.3 文件目录

5.3.1 文件目录管理的功能

1、实现“按名存取”

2、提高目录的检索速度

3、允许文件重名

4、允许文件共享

5.3.2 文件目录的实现

（1）文件控制块

1、一个文件包括两个部分：文件体和文件控制块（File Control Block，FCB）。

2、其中，文件体中包含的是文件本身的内容，文件控制块用于描述和控制文件的数据结构，保存系统管理文件所需要的全部属性信息。

3、FCB 中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。最重要，==最基本的还是文件名、文件存放的物理地址==

4、FCB 的有序集合称为“文件目录”，一个FCB就是一个文件目录项。

FCB 实现了文件名和文件之间的映射。使用户（用户程序）可以实现 “按名存取“

（2）索引节点

在查找各级目录的过程中只需要用到 “文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息。因可以考虑让目录表“瘦身”来提升效率。

1、将除了文件名之外的文件描述信息单独构成一个数据结构，称为索引节点（简称i节点）

2、之后，==目录项中只包含文件名、索引结点指针==，因此每个目录项的长度大幅减小

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

（1）存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。
（2）相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。

5.3.3 文件目录结构

1、单级目录结构

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

TIP

优点：

1、实现和管理简单

2、能够实现“按名存取”

缺点：

1、查找速度慢

2、不允许文件重名

3、不便于实现文件共享

2、两级目录结构

采用两级目录结构，分为主文件目录（MFD， Master File Directory）和用户文件目录（UFD， User Flie Directory）。

主文件目录记录用户名及相应用户文件目录的存放位置；用户文件目录由该用户的文件FCB组成

TIP

优点：

1、提高了目录检索速度

2、允许文件重名

3、不同用户可以使用不同的文件名来访问系统中的同一个共享文件

缺点：

缺乏灵活性，用户不能对自己的文件进行分类

3、多级目录结构

多级目录结构又称为树形目录结构，允许用户文件目录再建立下级子目录

不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享

系统根据"文件路径“找到目标文件，从根目录出发的路径是“绝对路径”，当前目录出发的路径是“相对路径“。

根据相对路径检索可以减少磁盘IO的次数

TIP

优点：

1、层次清楚

2、解决了文件的重名问题

3、便于文件共享

4、查询速度快

缺点：

==不方面文件的共享（所以提出了无环图目录结构）==

5.3.4 目录检索技术

线性检索法、Hash方法

5.4 文件存储空间管理

5.4.1 介绍

NOTE

文件的物理结构：对非空闲磁盘块的管理

文件存储空间管理：对空闲磁盘块的管理

TIP

1、将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）

2、将每个文件卷划分为目录区和文件区，其中目录区生要存放文件目录信息（FCB ）、用于磁盘存储空间管理的信息等，文件区用于存放文件数据

5.4.2 空闲表法

1、定义：为外存上的所有空闲分区建立一张空闲表，空闲表中记录每个连续空闲区的序号、起始盘块号、盘块数

2、分配：与内存管理的动态分区分配很类似，为文件分配连续的存储空间，同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

3、回收：回收时注意表项的合并问题

优点：适用于外存空间的“连续分配方式“
缺点：空闲区太多时，空闲表会变得很大，降低分配效率

5.4.3 空闲链表法

1、空闲盘块链

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

（1）分配

分配时从链头依次取出空闲块，并且修改空闲链的链头指针

（2）回收

将空闲块插入链首，并且将空闲块链首指针指向它

或者将空闲块插到链尾

优点：适用于离散分配的物理结构
缺点：为文件分配多个盘块和回收空闲块时可能要重复多次磁盘IO操作，效率较低

2、空闲盘区链

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

（1）分配

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

（2）回收

若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾，回收时注意相邻空闲盘区合并的问题

优点：相较于空闲盘块链来说，==离散分配、连续分配都适用，为一个文件分配多个盘块时效率更高==

5.4.4 位示图法

利用一个二进制位表示磁盘中一个盘块的使用情况，0表示对应的盘块空闲，1表示对应的盘块已分配（含义可以反过来），所有盘块的二进制位构成的集合称为位示图。

可以用（字号，位号）或（行号，列号）表示一个盘块

CAUTION

重点：盘块号和行号、列号的对应关系（盘块号b，行号i，列号j，每行的列数n）

（1）盘块号、字号、位号从0开始

$b = i * n + j$

$i = b / n$

$j = b % {n} $

（2）盘块号、字号、位号从1开始

$b = (i - 1) * n + j$

$i = (b - 1) / n + 1$

$j = (b - 1) % n + 1 $

连续分配、离散分配都适用

5.4.5 成组链接法

==UNIX采用的策略，适合大型文件系统==。

5.5 文件的共享和保护

5.5.1 文件的共享

操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件，实现文件共享的实质就是可以使用不同的路径、不同的文件名打开同一个文件。

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

1、索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。

2、各个用户的目录项指向同一个索引结点，若count=2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。

3、若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1。

4、只有文件的count值为1时，文件主才能删除文件，否则会导致指针悬空。

优点：可以实现文件的异名共享且系统开销不大
缺点：当有多个用户共享文件时，文件主不能删除文件；不能跨文件卷共享

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

1、在一个 Link 型的文件中记录共享文件的存放路径（Windows 快捷方式），==文件中的内容只有共享文件的路径名，不会增加共享文件的count计数==

2、操作系统根据路径一层层查找自录，最终找到共享文件

3、即使软链接指向的共享文件已被删除，Link型文件依然存在，不会留下悬空指针，只是通过 Link型文件中的路径去查找共享文件会失败（找不到对应自录项）

4、由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘/0，因此用软链接访问速度比硬链接慢

5.5.2 文件的保护

造成文件被破坏的原因：

1、系统发生故障或者各种意外，造成文件被破坏。（文件的可靠性问题）

2、多个用户共享文件时引起错误。（文件的安全性问题）

（1）文件备份

为了解决文件的可靠性问题，一般做法时文件备份。

1）批量备份

批量备份分为全量转储和增量转储

2）同步备份

同步备份分为镜像盘支持和双机动态文件备份

（2）文件访问保护

1）口令保护

为文件设置一个“口令”（如：abc112233），用户请求访问该文件时必须提供“口令”。

口令一般存放在文件对应的 FCB 或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则充许该用户访问文件

优点：实现方便，保存口令的空间开销不多，验证口令的时间开销也很小。
缺点：正确的 “口令”存放在系统内部，不够安全；对文件不能实现按用户控制存取权限

2）加密保护

使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。

优点：保密性强，不需要在系统中存储 “密码”
缺点：编码/译码，或者说加密/解密要花费一定时间。

3）为文件设置访问权限

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

对文件的访问类型可以分为：读/写/执行/删除等

优点：实现灵活，可以实现复杂的文件保护功能

5.5.3 磁盘调度

（1）磁盘管理概述

1、磁盘介绍

磁盘由若干个磁盘片组成。每个盘面上的若干个同心圆称为磁道，每个磁道从逻辑上分为若干个大小相等的扇区。

2、扇区的编址方式

（1）CHS（Cylinder/Head/Sector，柱面/磁头/扇区）方式

使用==柱面号、磁头号、扇区号==表示每个扇区

（2）LBA（Logical Block Addressing，相对扇区号）方式

使用相对扇区号表示扇区，以磁盘第一个扇区（0柱面、0磁头、1扇区）作为LBA的0扇区

转化（以磁盘第一个扇区==（0柱面、0磁头、1扇区）==作为LBA的0扇区）：
1、CHS --> LBA
若L、M、N表示一个磁盘的柱面数、磁头数及扇区数，则第i柱面、j磁头、k扇区对应的LBA扇区号为：==LBA = (i * M * N) + (j * N) + k -1==
2、LBA --> CHS
若已知LBA相对扇区号，则对应的柱面号i，磁头号j、扇区号k分别是：
==i = int(LBA / (M * N))==
==j = [LBA mod (M * N)] / N==
==k = [LBA mod (M * N)] mod N + 1==

3、磁盘访问时间

（1）寻道时间 $T_{s}$

是指把磁头从当前位置移动到指定磁道所需要的时间，通常为：

$ T_s = m *n + s$

其中，s是启动磁臂的时间，m是磁头每移动一条磁道所需要的时间，与磁盘驱动器的速度相关；n是移动的磁道数，也称为寻道距离，是影响 $T_{s}$ 的重要参数，一般寻道时间为5~15ms

（2）旋转延迟时间 $T_{r}$

通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则平均所需的延迟时间

$T_{r} = \frac{1}{2} * \frac{1}{r} = \frac{1}{2 r}$

（3）传输时间 $T_{t}$

从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N，那么传输时间

$T_{t} = \frac{1}{r} * \frac{b}{N} = \frac{b}{r * N}$

1、磁盘的访问时间 $T_{a}$ = 寻道时间 $T_{s}$ + 旋转延迟时间 $T_{r}$ + 传输时间 $T_{r}$
2、延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间

（2）磁盘调度算法

1、移臂调度

（1）先来先服务算法（FCFS）

按访问请求到达的先后顺序进行处理

优点：公平且实现简单，不会产生饥饿现象
缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。

（2）最短寻道时间优先算法（SSTS，Shortest Seek Time First）

SSTF算法会优先处理的磁道是与当前磁头最近的磁道。==可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。==（其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优）

优点：性能较好，平均寻道时间短
缺点：磁头在一个小区域内来回来去地移动，可能产生 “饥饿”现象；可能造成磁头频繁地改变移动方向而影响磁盘的机械寿命

（3）扫描算法（SCAN，又称为电梯算法）

只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。

优点：性能较好，平均寻道时间短，不会产生饥饿现象，有利于中间磁道的访问请求
缺点：对各个位置磁道的响应频率不平均

（4）循环扫描算法（Circular SCAN， CSCAN）

只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求

优点：比起SCAN来，对于各个位置磁道的响应频率很平均。
缺点：会有”磁臂黏着“现象

（5）N-Step-SCAN算法

将当前的磁盘请求队列分成若干个长度为N的子队列，磁盘调度按==FCFS==依次处理这些子队列

（6）FSCAN(FairSCAN)算法

将磁盘请求分为两个子队列，当前所有磁盘请求放在一个队列中，由磁盘调度按照SCAN算法处理；

对新出现的磁盘请求放在另一个等待队列中；待上一个队列处理完后，再来处理这个队列的磁盘请求

5.6 题目

文件系统是指（)
A.文件的集合
B.文件的目录
C.文件、管理文件的软件及数据结构的总体
D.实现文件管理的一组软件
答案：C

在Linux系统中，当一个普通文件处于 “未打开” 状态时，又件所占用的资源有（) A.一个文件目录项
B.一个磁盘索引I节点项
C.一个或多个磁盘块
D.一个文件控制块FCB
E.用户文件描述符表中的一个登记表项
答案：A,B,C

Linux的ext2文件系统采用用户权限表实现文件保护。
正确
错误
答案：错误
题目解析：Unix和Linux都使用访问控制表

基于索引节点的共享方式，不能用于目录文件的共享。
正确
错误
答案：正确

基于索引节点的共享方式不能实现跨文件卷的文件共享。
正确
错误
答案：正确
题目解析：因为每个文件卷中的文件索引|节点都是从0开始编号的，即不同文件卷上的索引节点编号是重复的

启动磁盘读写一块数据时，( )是硬件设计时就固定的。
A.寻道时间 B.旋转延迟时间 C.传输时间 D.读写一块数据的总时间
C

位示图 (bitmap) 是一种简单高效的磁盘块管理方式，但在使用过程中，尤其是经过频繁的分配与回收后，可能会出现磁盘碎片化的问题，从而导致磁盘块分配效率下降。为此，可以考虑以下改进建议：

1、引入分区管理策略

将磁盘空间分成若干分区，每个分区独立维护自己的位示图。分区管理策略可以缓解整体位示图的复杂度：

按文件类型分区：将小文件和大文件分别存储在不同的分区中。
按访问频率分区：将频繁访问的文件集中管理，减少碎片化的影响。

2、优化扫描策略

位示图需要扫描找到空闲块，可通过以下方式优化扫描效率：

记录最近扫描位置：维护一个指针，指向上次分配结束的位置，下次扫描从该位置继续，以减少重复扫描。
分块扫描：将位示图按固定大小分块，并对每块维护一个空闲块计数器，先查找空闲计数器非零的块，再深入扫描。

3、预分配和回收优化

预分配空闲块：对常见文件大小预分配一定数量的连续块，减少动态分配时的碎片化。
合并空闲块：在回收时尝试合并相邻的空闲块，以形成较大的连续空闲空间。

4、碎片整理机制

定期碎片整理：通过后台任务，将零散的空闲块合并，形成更大的连续空间。
延迟分配：在某些情况下，延迟实际分配操作，以避免碎片化（如写入缓存机制）。

总结

针对位示图效率下降的问题，需要结合实际应用场景选择合适的优化策略。如果碎片化严重，可以重点考虑碎片整理和空闲块合并；如果分配速度慢，可以优化扫描算法和分区管理策略。

1 操作系统概述 ​

1.1 介绍 ​

1.2 发展和分类 ​

1.3 特征和功能 ​

1.4 详细介绍 ​

1.4.1 运行机制 ​

1.4.2 中断和异常 ​

1.4.3 系统调用 ​

1.4.4 内核结构 ​

题目 ​

2 进程管理 ​

2.1 进程概念 ​

2.1.1 特征 ​

2.1.2 组成 ​

2.1.3 状态及转化 ​

2.2 进程控制 ​

2.3 进程通信 ​

2.3.1 共享存储器系统通信 ​

2.3.2 消息传递系统通信 ​

2.3.3 管道通信 ​

2.3.4 客户-服务器系统通信 ​

2.4 线程机制 ​

2.4.1 线程的资源 ​

2.4.2 实现机制 ​

2.5 进程调度 ​

2.5.1 调度概念 ​

2.5.2 调度算法 ​

2.6 进程同步 ​

2.6.1 基本概念 ​

2.6.2 进程同步机制 ​

2.7 死锁 ​

2.7.1 概念 ​

2.7.1 处理死锁 ​

2.8 题目 ​

3 存储器 ​

3.1 存储器管理概述 ​

3.1.1 存储器管理功能 ​

3.1.2 程序的装入和链接 ​

3.2 存储器管理方式 ​

3.2.1 连续存储器管理方式 ​

3.2.1.1 固定分区方式 ​

3.2.1.2 可变分区方式 ​

3.2.1.3 对比 ​

3.2.2 非连续存储器管理方式 ​

3.2.2.1 分页存储管理 ​

3.2.2.2 分段存储管理 ​

3.2.2.3 分页和分段的对比 ​

3.2.2.4 段页式存储管理 ​

3.2.3 虚拟存储系统 ​

3.2.3.1 介绍 ​

3.2.3.2 请求分页存储管理方式 ​

3.2.3.3 页面置换算法 ​

3.2.3.3 页面分配策略 ​

3.3 题目 ​

4 设备管理 ​

4.1 设备管理的功能 ​

4.2 I/O系统 ​

4.2.1 设备的分类 ​

4.2.2 设备控制器 ​

4.2.3 I/O通道 ​

4.2.4 I/O系统结构 ​

4.3 I/O控制方式 ​

4.4 I/O软件 ​

4.4.1 用户进程 ​

4.4.2 设备独立性软件 ​

4.4.3 设备驱动程序 ​

4.4.4 设备中断处理程序 ​

4.4.5 硬件 ​

4.6 设备分配 ​

4.5 缓冲管理 ​

4.5.1 概述 ​

4.5.2 实现机制 ​

4.7 Spooling技术 ​

4.8 题目 ​

5 文件管理 ​

5.1 概述 ​

5.1.1 文件的分类 ​

5.1.2 文件系统的功能 ​

5.2 文件结构 ​

5.2.1 文件的逻辑结构 ​

1 操作系统概述

1.1 介绍

1.2 发展和分类

1.3 特征和功能

1.4 详细介绍

1.4.1 运行机制

1.4.2 中断和异常

1.4.3 系统调用

1.4.4 内核结构

题目

2 进程管理

2.1 进程概念

2.1.1 特征

2.1.2 组成

2.1.3 状态及转化

2.2 进程控制

2.3 进程通信

2.3.1 共享存储器系统通信

2.3.2 消息传递系统通信

2.3.3 管道通信

2.3.4 客户-服务器系统通信

2.4 线程机制

2.4.1 线程的资源

2.4.2 实现机制

2.5 进程调度

2.5.1 调度概念

2.5.2 调度算法

2.6 进程同步

2.6.1 基本概念

2.6.2 进程同步机制

2.7 死锁

2.7.1 概念

2.7.1 处理死锁

2.8 题目

3 存储器

3.1 存储器管理概述

3.1.1 存储器管理功能

3.1.2 程序的装入和链接

3.2 存储器管理方式

3.2.1 连续存储器管理方式

3.2.1.1 固定分区方式

3.2.1.2 可变分区方式

3.2.1.3 对比

3.2.2 非连续存储器管理方式

3.2.2.1 分页存储管理

3.2.2.2 分段存储管理

3.2.2.3 分页和分段的对比

3.2.2.4 段页式存储管理

3.2.3 虚拟存储系统

3.2.3.1 介绍

3.2.3.2 请求分页存储管理方式

3.2.3.3 页面置换算法

3.2.3.3 页面分配策略

3.3 题目

4 设备管理

4.1 设备管理的功能

4.2 I/O系统

4.2.1 设备的分类

4.2.2 设备控制器

4.2.3 I/O通道

4.2.4 I/O系统结构

4.3 I/O控制方式

4.4 I/O软件

4.4.1 用户进程

4.4.2 设备独立性软件

4.4.3 设备驱动程序

4.4.4 设备中断处理程序

4.4.5 硬件

4.6 设备分配

4.5 缓冲管理

4.5.1 概述

4.5.2 实现机制

4.7 Spooling技术

4.8 题目

5 文件管理

5.1 概述

5.1.1 文件的分类

5.1.2 文件系统的功能

5.2 文件结构

5.2.1 文件的逻辑结构