操作系统：核心原理与机制 ​

操作系统概述 ​

一、操作系统概述 ​

1、概念 ​

操作系统：

指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配

以提供给用户和其他软件方便的接口和环境

是计算机系统中最基本的系统软件

2、功能和目标 ​

1）系统资源管理 ​

提供的功能：处理机管理、存储器管理、文件管理、设备管理

2）向上层提供服务 ​

**封装思想：**操作系统把一些"丑陋"的硬件功能封装成简单易用的服务，使用户能更方便地使用计算机，用户无需关心底层硬件的原理，只需要对操作系统发出命令即可

1. 直接服务用户 ​

GUI：图形用户解密

命令接口：

1. 联机命令接口 = 交互式命令接口（有问有答）
2. 脱机命令接口 = 批处理命令接口（用户说，系统做）

2. 服务软件 ​

程序接口：可以在程序中进行系统调用来使用程序接口。普通用户不能直接使用程序接口，只能通过程序代码间接使用（系统调用=广义指令）

3）对硬件机器的拓展 ​

没有任何软件支持的计算机成为裸机。在裸机上安装的操作系统，可以提供资源管理功能和方便用户的服务功能，将裸机改造成功能更强、使用更方便的机器

通常把覆盖了软件的机器成为扩充机器，又称之为虚拟机

二、四个特征 ​

1、并发 ​

**并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生（复用技术）**的。

（补）并行：指两个或多个事件在同一时刻同时发生。

**操作系统的并发性：**指计算机系统中"同时"运行着多个程序，这些程序宏观上看是同时运行着的，而微观上看是交替运行的。

操作系统就是伴随着"多道程序技术"而出现的。因此，操作系统和程序并发是一起诞生的。并发性是操作系统一个最基本的特性

2、共享 ​

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

资源分享的两种方式：

1. 互斥共享方式：只能单一程序访问（打印机）
2. 同时共享方式：可以多程序并发访问（硬盘的同时访问）

2.5、并发和共享的关系 ​

并发性指计算机系统中同时存在着多个运行着的程序。

共享性是指系统中的资源可供内存中多个并发执行的进程共同使用。

并发和共享是两个基本特征，二者互为存在条件

3、虚拟 ​

**虚拟：**是指把一个物理上的实体变为若干个逻辑上的对应物。（用户的感受大于实体）

1. 时分复用技术：虚拟处理器
2. 空分复用技术：虚拟内存

没有并发性，就谈不上虚拟性

4、异步 ​

**异步：**是指在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行速度不匹配。

只有系统拥有并发性，才有可能导致异步性。

三、发展与分类 ​

1、手工操作阶段 ​

用户独占全机、人机速度矛盾导致资源利用率极低

2、批处理阶段 ​

1）单道批处理系统 ​

概述：引入脱机输入/输出技术（用外围机+磁带完成），并由监督程序负责控制作业的输入、输出

**优点：**缓解了一定程度的人机速度矛盾，资源利用率有所提升。

**缺点：**内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU有大量的时间是在空闲等待I/O完成。资源利用率依然很低。

image-20221129041428094

2）多道批处理系统 ​

**概述：**每次往内存中读入多道程序。操作系统正式诞生，用于支持多道程序并发运行

**优点：**多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大。

**缺点：**用户响应时间长，没有人机交互功能

3、分时操作系统 ​

**概述：**计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。

**优点：**用户请求可以被即时响应，实现人机交互问题。允许多个用户同时使用一台计算机。

**缺点：**不能优先处理一些紧急任务。

4、实时操作系统 ​

**概述：**在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。

**特点：**及时性、可靠性

**优点：**能够优先响应一些紧急任务，某些紧急任务不需时间片排队。

**分类：**硬实时系统、软实时系统

5、其他操作系统 ​

**网络操作系统：**能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享和各台计算机之间的通信。

**分布式操作系统：**主要特点是分布性和并行性。系统中的各台计算机地位相同，任何工作都可以分布在这些计算机上，由它们并行、协同完成这个任务。

个人计算机操作系统：Windows 10、MacOS

四、运行机制和体系结构 ​

1、运行机制 ​

1）两种指令 ​

**特权指令：**只有操作系统内核程序才能运行的指令

**非特权指令：**应用程序可以运行的指令

在CPU设计和生产的时候就划分了特权指令和非特权指令，因此CPU执行一条指令前就能判断出其类型

2）两种处理器状态 ​

用于CPU区分此时正在运行程序类型

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

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

拓展：CPU 中有一个寄存器叫程序状态字寄存器（PSW），其中有个二进制位，1表示“内核态”，0表示“用户态”

别名：内核态=核心态=管态；用户态=目态

内核态、用户态的切换

1. 操作系统内核在让出CPU之前，会用一条特权指令把 PSW 的标志位设置为“用户态”
2. CPU发现接下来要执行的这条指令是特权指令，但是自己又处于“用户态”。这个非法事件会引发一个中断信号
3. CPU检测到中断信号后，会立即变为“核心态”，并停止运行当前的应用程序，转而运行处理中断信号的内核程序

3）两种程序 ​

**内核程序：**系统的管理者，既可以执行特权指令，也可以执行非特权指令，运行在核心态

**应用程序：**只能执行非特权指令，运行在用户态

2、操作系统内核 ​

内核是计算机上配置的底层软件，是操作系统最基本、最核心的部分。

实现操作系统内核功能的那些程序就是内核程序

1. 时钟管理：实现计时功能
2. 中断处理：负责实现中断机制
3. 原语：是一种特殊的程序。处于操作系统最底层，是最接近硬件的部分。这种程序的运行具有原子性（不可被中断）。运行时间较短、调用频繁
4. 对系统资源进行管理的功能：进程管理、存储器管理、设备笞理

3、操作系统体系结构 ​

image-20221129043604098

1）大内核 ​

将操作系统的主要功能模块都作为系统内核，运行在核心态

优点：高性能

缺点：内核代码庞大，结构混乱，难以维护

2）微内核 ​

只把最基本的功能保留在内核

优点：内核功能少，结构清晰，方便维护

缺点：需要频繁地在核心态和用户态之间切换，性能低

五、中断和异常 ​

1、中断的作用 ​

中断是让操作系统内核夺回CPU使用权的唯一途径。使CPU由用户态变为内核态，使操作系统重新夺回对CPU的控制权

**内核态 => 用户态：**执行一条特权指令，修改PSW的标志位为“用户态”，操作系统将主动让出CPU使用权

**用户态 => 内核态：**由中断引发，硬件自动完成变态过程，触发中断信号，操作系统将强行夺回CPU的使用权

2、（广义）中断的类型 ​

1）内中断（异常） ​

与当前执行的指令有关，中断信号来源于CPU内部

**陷阱、陷入：**由陷入指令引发，是应用程序为了系统调用故意引发

**故障：**由错误条件引起的，可能被内核程序修复。内核程序修复故障后会把 CPU使用权还给应用程序，让它继续执行下去。如：缺页故障。

**终止：**由致命错误引起，内核程序无法修复该错误，因此一般不再将CPU使用权还给引发终止的应用程序，而是直接终止该应用程序。如：整数除0、非法使用特权指令

1）外中断（中断） ​

与当前执行的指令无关，中断信号来源于CPU外部

每一条指令执行结束时，CPU都会例行检查是否有外中断信号（时钟信号、IO设备）

3、中断机制的基本原理 ​

**不同的中断信号，需要用不同的中断处理程序来处理。**当CPU检测到中断信号后，会根据中断信号的类型去查询“中断向量表”，以此来找到相应的中断处理程序在内存中的存放位置。

六、系统调用 ​

1、什么是系统调用 ​

系统调用：是操作系统提供给应用程序使用的接口

可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务

2、系统调用与库函数的区别 ​

3、系统调用的功能 ​

4、系统调用的过程 ​

传递系统调用参数 => 执行陷入指令（用户态） => 执行相应的内请求核程序处理系统调用（核心态） => 返回应用程序

陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，使CPU进入核心态

发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行

（陷入指令 = trap 指令 = 访管指令）

进程管理 ​

一、进程 ​

1、进程的概念 ​

程序：是静态的，就是个存放在磁盘里的可执行文件

进程：是动态的，是程序的一次执行过程

同一个程序多次执行会对应多个进程

2、进程的组成 ​

1）进程控制块PCB ​

操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中。

PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。

2）程序段、数据段 ​

PCB 是给操作系统用的。

程序段、数据段是给进程自己用的。

一个进程实体（进程映像）由PCB、程序段、数据段组成。

进程是动态的，进程实体（进程映像）是静态的。进程实体反应了进程在某一时刻的状态，类似快照。

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

3、进程的特征 ​

动态性是进程最基本的特征。

异步性会导致并发程序执行结果的不确定性

4、进程的状态 ​

运行态：占有CPU，并在CPU上运行

就绪态：已经具备运行条件，但由于没有空闲CPU，而暂时不能运行

阻塞态（等待态）：因等待某一事件而暂时不能运行

创建态（新建态）：进程正在被创建，操作系统为新进程分配资源、创建PCB

终止态（结束态）：进程正在从系统中撤销，操作系统回收进程的资源、撤销PCB

5、进程状态的转换 ​

6、进程的组织 ​

1）进程的组织概述 ​

进程PCB中，会有一个变量 state 来表示进程的当前状态。（如：1表示创建态、2表示就绪态、3表示运行态…）

为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的PCB组织起来。

2）进程的组织的方式 ​

1. 链接方式 ​

**执行指针：**指向当前处于运行态（执行态）的进程。单CPU计算机中，同一时刻只会有一个进程处于运行态。多核CPU可有多个进程同时处于运行态

**就绪队列指针：**指向当前处于就绪态的进程

**阻塞队列指针：**指向当前处于阻塞态的进程（很多操作系统还会根据阻塞原因不同，再分为多个阻塞队列）

2. 索引方式 ​

7、进程控制 ​

1）进程控制的方式 ​

2）进程控制相关原语 ​

1. 进程的创建 ​

2. 进程的终止 ​

3. 进程的阻塞和唤醒 ​

4. 进程的切换 ​

6、进程通信IPC ​

进程间通信：是指两个进程之间产生数据交互。

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。

1）共享存储 ​

1. 基于数据结构的共享 ​

**基于数据结构的共享：**这种共享方式速度慢、限制多，是一种低级通信方式。比如共享空间里只能放一个长度为3的数组。

image-20221130155844612

2. 基于存储区的共享 ​

**基于存储区的共享：**操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。

为避免出错，各个进程对共享空间的访问应该是互斥的。

各个进程可使用操作系统内核提供的同步互斥工具

2）消息传递 ​

1. 直接通讯方式 ​

进程间的数据交换以格式化的消（Message）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

消息发送进程要指明接收进程的ID

2. 间接通讯方式 ​

间接通信方式：以“信箱”作为中间实体进行消息传递。

可以多个进程往同一个信箱send消息，也可以多个进程从同一个信箱中receive消息

3）管道通信 ​

“管道”是一个特殊的共享文 件，又名pipe文件。其实就是在内存中开辟一个大小固定的内存缓冲区

管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。

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

当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。

当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。

管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案： ①一个管道允许多个写进程，一个读进程（2014年408真题高教社官方答案） ②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）

二、线程 ​

1、线程的概述 ​

资源分配、调度

传统进程机制中，进程是资源分配、调度的基本单位

引入线程后，进程是资源分配的基本单位，线程是调度的基本单位

线程是一个基本的CPU执行单元，也是程序执行流的最小单位

线程则作为处理机的分配单元。

并发性

传统进程机制中，只能进程间并发

引入线程后，各线程间也能并发，提升了并发度

系统开销

传统的进程间并发，需要切换进程的运行环境，系统开销很大

线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小

引入线程后，并发所带来的系统开销减小

2、线程的属性 ​

线程是处理机调度的单位

多CPU计算机中，各个线程可占用不同的CPU

每个线程都有一个线程ID、线程控制块 (TCB)

线程也有就绪、阻塞、运行三种基本状态

线程几乎不拥有系统资源，同一进程的不同线程间共享进程的资源

由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预

同一进程中的线程切换，不会引起进程切换。不同进程中的线程切换，会引起进程切换

切换同进程内的线程，系统开销很小。切换进程，系统开销较大

3、线程的实现方式 ​

1）用户级线程 ​

早期的操作系统（如：早期Unix）只支持进程，不支持线程。

当时的“线程”是由线程库实现的，很多编程语言提供了强大的线程库，可以实现线程的创建、销毁、调度等功能。

1. 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
2. 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
3. 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程”

**优点：**用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

**缺点：**当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

2）内核级线程 ​

内核级线程（又称内核支持的线程）

1. 内核级线程的管理工作由操作系统内核完成。
2. 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
3. 操作系统会为每个内核级线程建立相应的TCB（Thread Control Block，线程控制块），通过TCB对线程进行管理。“内核级线程”就 是“从操作系统内核视角看能看到的线程”

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

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

3、多线程模型 ​

在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型

1）一对一模型 ​

**一对一模型：**一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

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

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

2）多对一模型 ​

多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

3）多对多模型 ​

多对多模型：n 用户及线程映射到 m 个内核级线程（n >= m）。每个用户进程对应 m 个内核级线程。

克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

用户级线程是“代码逻辑”的载体、内核级线程是“运行机会”的载体（内核级线程才是处理机分配的单位）

一段“代码逻辑”只有获得了“运行机会”才能被CPU执行

内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有两个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞

三、调度 ​

1、三层调度 ​

1）高级调度（作业调度） ​

高级调度（作业调度）：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。**每个作业只调入一次，调出一次。**作业调入时会建立PCB，调出时才撤销PCB。

作业：一个具体的任务

用户向系统提交一个作业：用户让操作系统启动一个程序（来处理一个具体的任务）

2）低级调度（进程调度） ​

低级调度（进程调度/处理机调度）：按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

3）中级调度（内存调度） ​

暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列

中级调度（内存调度）：按照某种策略决定将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

4）三层调度总结 ​

2、七状态模型 ​

暂时调到外存等待的进程状态为挂起状态（挂起态）

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

3、进程调度的时机 ​

1）需要调度的时机 ​

当前运行的进程主动放弃处理机

1. 进程正常终止
2. 运行过程中发生异常而终止
3. 进程主动请求阻塞（如 等待I/O）

当前运行的进程被动放弃处理机

1. 分给进程的时间片用完
2. 有更紧急的事需要处理（如 I/O中断）
3. 有更高优先级的进程进入就绪队列

2）不能调度的时机 ​

1. 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
2. 进程在操作系统内核程序临界区中。（内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列）（但是进程在普通临界区中是可以进行调度、切换的）
3. 在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如修改PCB中进程状态标志，并把PCB放到相应队列）

4、进程调度切换与过程 ​

狭义的进程调度与进程切换

1. 狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
2. 进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。（对原来运行进程各种数据的保存、对新的进程各种数据的恢复）

广义的进程调度

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换是有代价的

如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少

5、进度调度的方式 ​

非剥夺调度方式，又称非抢占方式：只能由当前运行的进程主动放弃CPU

剥夺调度方式，又称抢占方式：可由操作系统剥夺当前进程的CPU使用权

6、调度算法的评价指标 ​

1）CPU利用率 ​

利用率 = 忙碌的时间 / 总时间

2）系统吞吐量 ​

系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间

3）周转时间 ​

周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

4）等待时间 ​

等待时间：进程/作业处于等待处理机状态时间之和

5）响应时间 ​

响应时间：用户提交请求到首次产生响应所用的时间。

7、调度算法 ​

1）先来先服务（FCFS） ​

思想：公平

规则：先来后到顺序

用于作业调度时，考虑的是作业；用于进程调度时，考虑的是进程。

非抢占式的算法

优点：公平、算法实现简单

缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。FCFS算法对长作业有利，对短作业不利

不会导致饥饿（饥饿：某进程/作业长期得不到服务）

2）最短作业优先（SJF） ​

思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

算法规则：服务时间最短的先服务

最短剩余时间优先算法：就绪队列改变时、一个进程完成时就需要重新调度，运行剩余时间最短的进程

可用于作业调度，也可用于进程调度。（用于进程调度时称为“短进程优先算法SPF”）

SJF和SPF是非抢占式的算法。但是也有抢占式的版本（最短剩余时间优先算法SRTN）

优点：“最短的”平均等待时间、平均周转时间

缺点：

1. 不公平。对短作业有利，对长作业不利，产生饥饿现象
2. 运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

对于最短作业优先算法的补充：

1. 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
2. 抢占式的短作业/进程优先调度算法（最短剩余时间优先SRNT算法）的平均等待时间、平均周转时间最少
3. 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如 FCFS），SJF依然可以获得较少的平均等待时间、平均周转时间
4. 如果选择题中遇到“SJF 算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项

3）最高响应比优先（HRRN） ​

思想：综合考虑等待时间和要求服务的时间

规则：每次调度前计算响应比，服务响应比最高的作业

响应比 = (等待时间 + 要求服务时间) / 要求服务时间

高响应比优先算法：只有当前运行的进程主动放弃CPU时进行调度，计算所有就绪进程的响应比，处理响应比最高的进程。

既可用于作业调度，也可用于进程调度

非抢占式的调度算法

特点：

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

4）时间片轮转（RR） ​

思想：公平地、轮流地为各个进程服务

规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片。

用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）

若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU中指服务

优点：公平、响应快、适用于分时操作系统、不会导致饥饿

缺点：由于高频率的进程切换，因此有一定开销、不能区分任务的紧急程度

5）优先级调度 ​

思想：根据任紧急程度决定顺序

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

非抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。

抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占。

非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占

既可用于作业调度，也可用于进程调度。（甚至，还会用于在之后会学习的I/O调度中）

优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。

缺点：若源源不断地有高优先级进程到来，则可能导致饥饿

6）多级反馈队列 ​

思想：折中权衡

用于进程调度

规则：

1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
3. 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片

抢占式的算法。在 k 级队列的进程运行过程中，若更上级的队列（1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾

特点：

1. 对各类型进程相对公平（FCFS的优点）
2. 每个新到达的进程都可以很快就得到响应（RR的优点）
3. 短进程只用较少的时间就可完成（SPF的优点）
4. 不必实现估计进程的运行时间（避免用户作假）
5. 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）
6. 会导致饥饿

四、进程同步和互斥 ​

1、进程同步概述 ​

并发性带来了异步性，有时需要通过进程同步解决这种异步问题。

有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序。

2、进程互斥概述 ​

1）临界资源 ​

把一个时间段内只允许一个进程使用的资源称为临界资源

对临界资源的访问，必须互斥地进行

2）进程互斥四个部分 ​

1. 进入区：检查是否可进入临界区，若可进入，需要“上锁"
2. 临界区：访问临界资源的那段代码
3. 退出区：负贵"解锁"
4. 剩余区：做其他处理

3）互斥操作的原则 ​

1. 空闲让进：临界区空闲时，应允许一个进程访问
2. 忙则等待：临界区正在被访问时，其他试图访问的进程需要等待
3. 有限等待：要在有限时间内进入临界区，保证不会饥饿
4. 让权等待：进不了临界区的进程，要释放处理机，防止忙等

3、进程互斥的软件实现 ​

1）单标志法 ​

turn 变量背后的逻辑：表达“谦让”

单标志法存在的主要问题是：违背“空闲让进”原则（对方不谦让，我就不能用）。

2）双标志先检查法 ​

flag[]数组中各个元素用来标记各进程想进入临界区的意愿

双标志先检查法的主要问题是：违反“忙则等待”原则。

进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换

3）双标志后检查法 ​

双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。

两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

4）Peterson算法 ​

结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。

Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

4、进程互斥的硬件实现 ​

1）中断屏蔽方式 ​

利用“开/关中断指令”实现，在某进程开始访问临界区到结束访问为止都不允许被中断，就不能发生进程切换

···
关中断;	// 关中断后即不允许当前进程被中断，也必然不会发生进程切换
临界区;
开中断;	// 直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区
···

优点：简单、高效

缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

2）TestAndSet（TS/TSL指令） ​

TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

//布尔型共享变量 lock 表示当前临界区是否被加锁
//true 表示已加锁，false 表示未加锁
bool TestAndset (bool *lock){
	bool old;
	old = *lock; 	//old用来存放lock原来的值
	*lock = true; 	//无论之前是否已加锁，都将lock设为true
	return old;		//返回lock原来的值
}

//以下是使用 TSL 指令实现互斥的算法逻辑
while (TestAndset (&lock));	//"上锁"并"检查"
临界区代码段...
lock = false;	//解锁
剩余区代码段...

优点：实现简单、适用于多处理机环境

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

3）Swap指令（XCHG指令） ​

Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

//Swap 指令的作用是交换两个变量的值
void Swap (bool *a, bool *b) {
	bool temp;
	temp = *a;
	*a = *b;
    *b = temp;
}

//以下是用 Swap 指令实现互斥的算法逻辑
//lock 表示当前临界区是否被加锁
bool old = true;
while (old == true)
	Swap (&lock, &old);
临界区代码段...
lock = false;
剩余区代码段...

与TSL 指令类似

5、信号量机制 ​

1）信号量机制概述 ​

信号量：一个变可以用来表示系统中某种资源的数量的变量

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。

一对原语：wait(S) 原语和 signal(S) 原语。简称为 P、V操作

2）信号量分类 ​

1. 整型信号量 ​

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

存在的问题：不满足“让权等待”原则，会发生“忙等”

int S = 1;	//初始化整型信号量s，表示当前系统中可用的资源数

void wait (int S) {	//wait 原语，相当于进入区
    while (S <= 0);	//如果资源数不够，就一直循环等待
    S--;			//如果资源数够，则占用一个资源
}

void signal (int S) {	//signal 原语，相当于退出区
    S++;				//使用完资源后，在退出区释放资源
}

2. 记录型信号量 ​

记录型信号量：用记录型数据结构表示的信号量

该机制遵循了“让权等待”原则

typedef struct {
    int value;
    struct process *L;	// 等待队列
} semaphore;

void wait (semaphore S) {	
    S.value--;
    if (S.value < 0) {
        block(S.L);
    }
}

void signal (semaphore S) {	
    S.value++;
    if (S.value <= 0) {
        wakeup(S.L);
    }
}

如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量 S 的阻塞队列中

释放资源后，若还有别的进程在等待这种资源，则使用wakeup 原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态

3）信号量实现互斥 ​

一个信号量对应一种资源

信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）

P(S) ：申请一个资源S，如果资源不够就阻塞等待

V(S) ： 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程

对不同的临界资源需要设置不同的互斥信号量。

P、V操作必须成对出现

semaphore mutex = 1;

f() {
    P(mutex);
    临界区代码...;
    V(mutex);
}

4）信号量实现同步 ​

前V后P

信号量S代表“某种资源”，刚开始是没有这种资源的。P2需要使用这种资源，而又只能由P1产生这种资源

4.5）互斥和同步的对比 ​

5）信号量实现前驱关系 ​

1. 分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题
2. 为每一对前取关系设置同步信号量，初值为0
3. 在每个"前操作"之后执行 V 操作
4. 在每个"后操作"之前执行 P 操作

6、PV操作模型 ​

1）生产者消费者问题 ​

生产者、消费者共享一个初始为空、大小为n的缓冲区。

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。

只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

缓冲区是临界资源，各进程必须互斥地访问。

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

V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; //同步信号量，表示空闲缓冲区的数量
semaphore full = 0; //同步信号量，表示产品的数量，也即非空缓冲区的数量

producer (){
    while(1){
        生产一个产品;
        P(empty);
        P(mutex);
        把产品放入缓冲区;
        V(mutex);
        V(full);
	}
}

consumer (){
    while(1){
        P(full);
        P(mutex);
        从缓冲区取出一个产品;
        V(mutex);
        V(empty);
        使用产品; 
    } 
}

2）多生产者多消费者问题 ​

互斥关系：对缓冲区（盘子）的访问要互斥地进行

同步关系（一前一后）：

1. 父亲将苹果放入盘子后，女儿才能取苹果
2. 母亲将橘子放入盘子后，儿子才能取橘子
3. 只有盘子为空时，父亲或母亲才能放入水果

semaphore mutex = 1; //实现互斥访问盘子（缓冲区）
semaphore apple = 0; //盘子中有几个苹果
semaphore orange = 0; //盘子中有几个橘子
semaphore plate = 1; //盘子中还可以放多少个水果

dad (){
    while(1){
        准备一个苹果;
        P(plate);
        P(mutex);
        把苹果放入盘子;
        V(mutex);
        V(apple);
    }
}

mom (){
    while(1){
        准备一个橘子;
        P(plate);
        P(mutex);
        把橘子放入盘子;
        V(mutex);
        V(orange);
    } 
}

daughter (){
    while(1){
        P(apple);
        P(mutex);
        从盘中取出苹果;
        V(mutex);
        V(plate);
    吃掉苹果; 
    } 
}

son (){
    while(1){
        P(orange);
        P(mutex);
        从盘中取出橘子;
        V(mutex);
        V(plate);
        吃掉橘子; 
    } 
}

发现：即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象。

本题中的缓冲区大小为1。在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。

因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。

3）吸烟者问题 ​

生产多种产品的单生产者多消费者

PV操作顺序：“前V后P”

semaphore offer1 = 0; //桌上组合一的数量
semaphore offer2 = 0; //桌上组合二的数量
semaphore offer3 = 0; //桌上组合三的数量
semaphore finish = 0; //抽烟是否完成
int i = 0; //用于实现“三个抽烟者轮流抽烟”

provider (){
    while(1){
        if(i==0) {
            将组合一放桌上;
            V(offer1);
        } else if(i==1) {
            将组合二放桌上;
            V(offer2);
        } else if(i==2) {
            将组合三放桌上;
            V(offer3);
        }
        i = (i+1)%3;
        P(finish);
    } 
}

smoker1 (){
    while(1){
        P(offer1);
        从桌上拿走组合一；卷烟；抽掉；
        V(finish);
    }
}

4）读者写者问题 ​

1. 允许多个读者可以同时对文件执行读操作
2. 只允许一个写者往文件中写信息
3. 任一写者在完成写操作之前不允许其他读者或写者工作
4. 写者执行写操作前，应让已有的读者和写者全部退出

互斥关系：写进程—写进程、写进程—读进程。读进程与读进程不存在互斥问题。

读写公平算法

semaphore rw=1; //用于实现对共享文件的互斥访问
int count = 0; //记录当前有几个读进程在访问文件
semaphore mutex = 1; //用于保证对count变量的互斥访问
semaphore w = 1; //用于实现“写优先（公平读写）”

writer (){
    while(1){
        P(w);
        P(rw);
        写文件…
        V(rw);
        V(w);
    }
}

reader (){
    while(1){
        P(w);
        P(mutex);
        if(count==0)
        	P(rw);
        count++;
        V(mutex);
        V(w);
        
        读文件…
            
        P(mutex);
        count--;
        if(count==0)
        	V(rw);
        V(mutex);
    }
}

5）哲学家进餐问题 ​

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

如果每位哲学家循环等待右边的人放下筷子（阻塞），发生“死锁”

1. 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况
3. 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

7、管程 ​

组成：

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

基本特征：

1. 各外部进程/线程只能通过管程提供的特定”入口"才能访问共享数据
2. 每次仅允汻一个进程在管程内执行某个内部过程
3. 各进程必须互斥访问管程的特性是由编译器实现的
4. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题

每次只能有一个线程进入add函数，如果多个线程同时调用add函数，则后来者需要排队等待

static class Main {
    private int cnt = 0;
    
    public synchronized int add (int n) {
        return cnt + n;
    }
}

五、死锁 ​

1、死锁概述 ​

死锁：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象。

饥饿：发生饥饿的进程既可能是阻塞态（如长期得不到需要的I/O设备），也可能是就绪态（长期得不到处理机）

2、死锁产生的必要条件 ​

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

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

请求和保持条件：保持着某些资源不放的同时，请求别的资源

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

3、预防死锁（静态策略） ​

1）破坏互斥条件 ​

将临界盗源改造为可共享使用的资源

缺点：可行性不高，很多时候无法破坏互斥条件

2）破坏不剥夺条件 ​

1、申请的资源得不到满足时，立即释放拥有的所有资源

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

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

3）破坏请求和保持条件 ​

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

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

4）破坏循环等待条件 ​

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

缺点：不方便添加新设备、会导致资源浪费、用户编程困难

4、避免死锁（动态策略） ​

1）安全序列 ​

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

安全状态：只要能找出一个安全序列的系统

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态

系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

2）银行家算法 ​

核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

5、死锁的检测 ​

资源分配图

1. 两种节点
   1. 进程结点：对应一个进程
   2. 资源结点：对应一类资源，一类资源可能有多个
2. 两种边
   1. 进程结点 => 资源结点：表示进程想申请几个资源（每条边代表一个)
   2. 资源节点 => 进程结点：表示已经为进程分配了几个资源（每条边代表一个）

依次消除与不阻塞进程相连的边，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（安全序列）。如果最终不能消除所有边，那么此时就是发生了死锁，最终还连着边的那些进程就是处于死锁状态的进程。

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

6、死锁的解除 ​

1. 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2. 撤销进程法（或称终止进程法）：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。
3. 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程。

内存管理 ​

一、内存概述 ​

1、内存作用 ​

内存作用：缓和CPU与硬盘之间的速度矛盾

程序执行前需要先放到内存中才能被CPU处理

2、编址方式 ​

内存地址从0开始，每个地址对应一个存储单元

按字节编址：每个存储单元大小为1字节，即 1B，即 8个二进制位

按字编址：每个存储单元大小为1个字

二、进程运行的基本原理 ​

1、写程序到程序运行 ​

编译：把高级语言翻译为机器语言

链接：由目标模块生成装入模块，链接后形成完整的逻辑地址

装入（装载）：将装入模块装入内存，装入后形成物理地址

2、链接方式 ​

1）静态装入 ​

在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。

静态装入：装入前链接成一个完整装入模块

2）装入时动态链接 ​

将各目标模块装入内存时，边装入边链接的链接方式

装入时动态链接：运行前边装入边链接

3）运行时动态链接 ​

在程序执行中需要该目标模块时，才对它进行链接。其优点是便 于修改和更新，便于实现对目标模块的共享。

运行时动态链接：运行时需要目标模块才装入并链接

3、装入方式 ​

1）绝对装入 ​

如果知道程序将会放在内存的具体位置，就在编译的时候生成程序的物理地址。之后装入程序就会按照装入模块里面已经生成的物理地址放进内存进行运行。

只适用于单道程序的运行环境（单道批那时候没有操作系统，所以就是编译程序来干转换地址的事情）

编译时产生绝对地址

2）可重定位装入（静态重定位） ​

在多道程序的运行环境下，我们并不能预知当程序并发执行的时候会放在内存的哪个地方。

多个目标模块的起始地址通常都从0开始，其他的地址则是相对于0的相对地址。

在装入的时候对程序里面的一些指令和数据进行修改的过程叫做重定位，地址变换也在装入的时候一次完成，把逻辑地址转换成对应内存的物理地址。在装入的时候转换了以后就不会再进行修改，所以也叫静态重定位

装入时将逻辑地址转换为物理地址

3）动态运行时装入（动态重定位） ​

在要执行的时候，才把这一部分的目标模块进行地址转换。（此时已经在内存中等待运行了）所以在等待运行的时候，地址都是相对地址。

这种方式需要重定位寄存器的支持，重定位寄存器存放的是装入模块在内存中的起始位置，根据这个起始位置来确定指令，执行指令。

可以把程序放在不连续的存储区中，在程序运行之前装入他的部分代码就可以运行，然后再程序运行的时候根据需要动态申请内存。

运行时将逻辑地址转换为物理地址，需设置重定位奇存器

三、内存空间的分配与回收 ​

1、连续分配 ​

1）单一连续分配 ​

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

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

用户区：用于存放用户进程相关数据。只能有一道用户程序，用户程序独占整个用户区空间。

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

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

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上

外部碎片：指内存中的某些空闲分区由于太小而难以利用

2）固定分区分配 ​

将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业

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

分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分

分区说明表：实现各个分区的分配与回收。

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

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

3）动态分区分配 ​

在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。

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

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

回收分区：与相邻的合并或增加表项

动态分区分配没有内部碎片，但是有外部碎片。（通过紧凑技术来解决外部碎片）

动态分区分配算法

2、非连续分配 ​

1）基本分页存储管理 ​

1. 分页存储 ​

将内存空间分为一个个大小相等的分区，每个分区就是一个页框。每个页框有一个编号，即页框号，页框号从0开始。

页框=页帧=内存块=物理块=物理页面

页框号=页帧号=内存块号=物理块号=物理页号

将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页。每个页面也有一个编号，即页号，页号也是从0开始。

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。

进程的最后一个页面可能没有一个页框那么大 ==> 分页存储有可能产生内部碎片

2. 页表 ​

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表

1. 一个进程对应一张页表
2. 进程的每个页面对应一个页表项
3. 每个页表项由页号和块号组成
4. 页表记录进程页面和实际存放的内存块之间的映射关系
5. 每个页表项的长度是相同的

计算机中内存块的数量 => 页表项中块号至少占多少字节

页号不占用存储空间

J 号内存块的起始地址 = J * 内存块大小

3. 逻辑地址的转换 ​

对于十进制形式

页号 = 逻辑地址 / 页面长度

页内偏移量 = 逻辑地址 % 页面长度

对于二进制形式

"逻辑地址" = "页号" + "页内偏移量"

4. 地址转换的实现 ​

1. 根据逻辑地址算出页号、页内偏移量
2. 页号的合法性检查（与页表长度对比）
3. 若页号合法，再根据页表起始地址、页号找到对应页表项
4. 根据页表项中记录的内存块号、页内偏移量 得到最终的物理地址
5. 访问物理内存对应的内存单元

第一次访问内存：查页表

第二次访问内存：访问目标内存单元

5. 补充 ​

页内偏移量位数与 页面大小之间的关系 （要能用其中一个条件推出另一个条件）

页式管理中地址是一维的

通常使一个页框怡好能放入整数个页表项

为了方便找到页表项，页表一般是放在连续的内存块中的

2）具有快表的地址变换机构 ​

1. 快表的概述 ​

快表（联想寄存器、TLB）是一种访问速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本，可以加速地址变换的速度。内存中的页表常称为慢表。

TLB和普通 Cache 的区别：TLB 中只有页表项的副本，而普通 Cache 中可能会有其他各种数据的副本

2. 具有快表的地址变换过程 ​

1. 算页号、页内偏移量
2. 检查页号合法性
3. 查快表。若命中，即可知道页面存放的内存块号，可直接进行⑤；若未命中则进行④
4. 查页表，找到页面存放的内存块号，并且将页表项复制到快表中
5. 根据内存块号与页内偏移量得到物理地址
6. 访问目标内存单元

3）两级页表 ​

1. 单级页表的问题 ​

• 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
• 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

2. 两级页表的原理 ​

页目录表：把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置

页目录表 = 外层页表 = 顶层页表

3. 两级页表的地址变换 ​

1. 按照地址结构将逻辑地址拆分成三部分
2. 从PCB 中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
3. 根据二级页号查表，找到最终想访问的内存块号
4. 结合页内偏移量得到物理地址

4. 两级页表补充 ​

多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级。

多级页表的访存次数（没有快表机构）：N级页表访问一个逻辑地址需要 N+1次访存

4）基本分段存储管理 ​

1. 分段 ​

分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）所组成。

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

2. 段表 ​

段表：记录逻辑段到实际存储地址的映射关系

每个段对应一个段表项。各段表项长度相同，由段号（隐含）、段长、基质组成

3. 地址变换 ​

1. 由逻辑地址得到段号、段内地址
2. 段号与段表奇存聚中的段长度比较，检查是否越界
3. 由段表始址、段号找到对应段表项
4. 根据段表中记录的段长，检耷段内地址是否越界
5. 由段表中的基址+段内地址得到最终的物理地址
6. 访问目标单元

分段、分页管理的对比

1、分页对用户不可见，分段对用户可见

• 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
• 段是信息的逻辑单位。分页的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

2、分页的地址空间是一维的，分段的地址空间是二维的

• 分页的用户进程地址空间是一维的：程序员只需给出一个记忆符即可表示一个地址。
• 分段的用户进程地址空间是二维的：程序员在标识一个地址时，既要给出段名，也要给出段内地址。

3、分段更容易实现信息的共享和保护

4、分页（单级页表）、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构

• 分页（单级页表）：第一次访存（查内存中的页表），第二次访存（访问目标内存单元）。总共两次访存
• 分段：第一次访存（查内存中的段表），第二次访存（访问目标内存单元）。总共两次访存
• 分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

5）段页式存储管理 ​

1. 分页分段的特点分析 ​

分段管理中产生的外部碎片也可以用紧凑来解决，只是需要付出较大的时间代价

2. 段表和页表 ​

段页式系统的逻辑地址结构：（段号，页号，页内偏移量）

• 段号的位数：每个进程最多可以分几个段
• 页号位数：每个段最大有多少页
• 页内偏移量：页面大小、内存块大小是多少

段页式管理的地址结构是二维的

3. 地址变换 ​

1. 由逻辑地址得到段号、页号、页内偏移量
2. 段号与段表寄存器中的段长度比较，检查是否越界
3. 由段表始址、段号找到对应段表项
4. 根据段表中记录的页表长度，检查页号是否越界
5. 由段表中的页表地址、页号得到查询页表，找到相应页表项
6. 由页面存放的内存块号、页内偏移量得到最终的物理地址
7. 访问目标单元

四、内存空间的扩充 ​

1、覆盖技术 ​

内存中分为一个“固定区”和若干个“覆盖区”。

将程序分为多个段（多个模块），需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束）。不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存

必须由程序员声明覆盖结构，操作系统完成自动覆盖。

缺点：对用户不透明，增加了用户编程负担。

2、交换技术 ​

内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

暂时换出外存等待的进程状态为挂起状态

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。对换区（连续）的I/O速度比文件区（离散）的更快。

交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。

PCB 会常驻内存，不会被换出外存

覆盖技术与交换技术的区别：覆盖是在同一个程序或进程中的，交换是在不同进程间的

3、虚拟存储技术 ​

1）传统存储管理方式的缺点 ​

一次性：作业必须一次性全部装入内存后才能开始运行。

驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。

2）局部性原理 ​

时间局部性：如果执行了程序中的某条指令、数据，那么不久后这条指令、数据很有可能再次执行。

空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。

高速缓冲技术：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。

3）虚拟内存概述 ​

程序不需全部装入即可运行。运行时根据需要动态调入数据，若内存不够，还需换出一些数据

访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存（请求调页功能）

内存空间不够时，将内存中暂时用不到的信息换出到外存（页面置换功能）

4）虚拟内存的特征 ​

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

对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。

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

5）虚拟内存的实现（请求分页管理） ​

1. 页表机制 ​

状态位：表示页面是否已在内存中

访问宇段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考

修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需在置换时写回外存

外存地址：页面在外存中存放的位置

2. 缺页中断机构 ​

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

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

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

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

3. 地址变换机构 ​

1. 找到页表项是需要检查页面是否在内存中
2. 若页面不再内存中，需要请求调页
3. 若内存空间不够，还需换出页面
4. 页面调入内存后，需要修改相应页表项

快表中有的页面一定是在内存中的

若某个页面被换出外存则快表中的。相应表项也要删除，否则可能访问错误的页面

4. 页面置换算法 ​

Belady 异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。（只有 FIFO 算法会触发）

5. 页面分配策略 ​

####### 驻留集

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

####### 页面分配、置换策略

• 固定分配、可变分配：区别在于进程运行期间驻留集大小是否可变
• 局部置换、全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出

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

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

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

####### 调页策略

预调页策略：一般用于进程运行前

请求调页策略：进程运行时，发现缺页再调页

####### 从何处调页

对换区：采用连续存储方式，速度快

文件区：采用离散存储方式，速度慢

对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行

对换区不够大：不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入

UNIX方式：第一次使用的页面都从文件区调入；调出的页面都写回对换区，再次使用时从对换区调入

####### 抖动（颠簸）现象

页面频繁换入换出的现象

主要原因：分配给进程的物理块不够

####### 工作集

• 驻留集：指请求分页存储管理中给进程分配的内存块的集合。
• 工作集：指在某段时间间隔里，进程实际访问页面的集合。

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

五、地址转换 ​

1、地址转换概述 ​

操作系统负责实现逻辑地址到物理地址的转换

2、地址转换的方式 ​

1. 绝对装入：编译时产生绝对地址
2. 可重定位装入：装入时将逻辑地址转换为物理地址
3. 动态运行时装入：运行时将逻辑地址转换为物理地址，需设置重定位奇存器

六、存储保护 ​

1、存储保护概述 ​

保证各进程在自己的内存空间运行，不会越界访问

2、存储保护的方式 ​

1）上下限寄存器 ​

2）重定位寄存器、界地址寄存器 ​

重定位寄存器（基址寄存器）：进程的起始物理地址

界地址寄存器（限长寄存器）：进程的最大逻辑地址

文件管理 ​

一、文件管理 ​

1、文件管理概述 ​

文件的定义：一组有意义的信息的集合

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

2、文件的逻辑结构 ​

逻辑结构：指在用户看来，文件内部的数据应该是如何组织起来的。

物理结构：指的是在操作系统看来，文件的数据是如何存放在外存中的。

无结构文件：文件内部的数据就是一系列二进制流或字符流组成。如txt

文件内部的数据其实就是一系列字符流，没有明显的结构特性

1）顺序文件 ​

串结构：记录顺序与关键字无关

顺序结构：记录按关键字顺序排列

可变长记录的顺序文件无法实现随机存取，定长记录可以（可变长记录的顺序文件在每 次查询时只能从头依次查找）

定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速找到记录）

缺点：不方便增加、删除记录

2）索引文件 ​

建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录

索引表本身就是定长记录的质顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取

若索引表按关键字顺序排列，则可支持快速检索

解决了顺序文件不方便增、删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间

3）索引顺序文件 ​

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

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

当记录过多时，可建立多级素引表

3、文件目录 ​

1）文件目录的实现 ​

一个文件对应一个FCB（目录项），多个FCB组成文件目录

图中的每一条数据即为一个FCB

2）目录结构 ​

1. 单级目录结构 ​

一个系统只有一张目录表，不允许文件重名

2. 两级目录结构 ​

主文件目录（MFD）和用户文件目录（UFD）。不同用户有不同的目录表

不同用户的文件可以重名，但不能自己创建目录

3. 树形目录结构 ​

不同文件下的目录可以重名，可以自己创建目录进行分类

系统根据文件路径找到目标文件

不方便文件共享

绝对路径：从根目录出发的路径

相对路径：从当前目录出发的路径

相对路径检索文件可以减少磁盘IO次数

4. 无环图目录结构 ​

在树形目录结构的基础 上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图

为共享结点设置一个共享计数器，计数器为0时才真正删除该结点

3）索引节点 ​

除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引节点

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

由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，提高了检索效率

4、文件保护 ​

1）口令保护 ​

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

实现开销小，但"口令"一般存放在FCB或索引结点中（存放在系统中），因此不太安全

2）加密保护 ​

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

安全性高，但加密/解密需要耗费一定的时间

3）访问控制 ​

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

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

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

5、文件共享 ​

1）硬连接 ​

硬连接：基于索引结点的共享

各个用户的目录项指向同一个索引结点

索引结点中需要有链接计数 count

某用户想删除文件时，只是删除该用户的目录项，且count--

只有count ==0时才能真正删除文件数据和索引结点，否则会导致指针悬空

2）软连接 ​

软连接：基于符号链的共享

在一个 Link 型的文件中记录共享文件的存放路径（Windows 快捷方式）

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

即使软链接指向的共享文件已被刷除，Link 型文件依然存在，只是通过 Link 型文件中的路径去查找共享文件会失败（找不到对应目录项）

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

二、文件 ​

1、文件实现 ​

类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。

磁盘块的大小与内存块、页面的大小相同

内存与磁盘之间的数据交换都是以“块”为单位进行的。即每次读入一块，或每次写出一块

2、文件分配方式 ​

1）连续分配 ​

连续分配方式要求每个文件在磁盘上占有一组连续的块。

物理块号 = 起始块号 + 逻辑块号

连续分配支持顺序访问和直接访问（即随机访问）

2）隐式链接分配 ​

缺点：只支持顺序访问，不支持随机访问，查找效率低。指向下一个盘块的指针也需要耗费少量的存储空间。

优点：不会有碎片问题，外存利用率高。方便文件拓展。

3）显式链接分配 ​

把用于链接文件各物理块的指针显式地存放在一张表中。即 文件分配表（FAT）

一个磁盘仅设置一张FAT。 开机时，将FAT读入内存，并常驻内存。

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

缺点：文件分配表的需要占用一定的存储空间

4）索引分配 ​

1. 链接方案 ​

如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

2. 多层索引 ​

建立多层索引（原理类似于多级页表）

若采用多层索引，则各层索引表大小不能超过一个磁盘块

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

3. 混合索引 ​

多种索引分配方式的结合

5）总结 ​

3、逻辑结构和物理结构 ​

1）逻辑结构 ​

用户（文件创建者）的视角看到的样子

在用户看来，整个文件占用连续的逻辑地址空间

文件内部的信息组织完全由用户自己决定，操作系统井不关心

2）物理结构 ​

由操作系统决定文件采用什么物理结构存储

操作系统负责将逻辑地址转变为（逻辑块号：块内偏移量）的形式，并负责实现逻辑块号到物理块号的映射

4、文件存储空间管理 ​

1）存储空间的划分与初始化 ​

存储空间的初始化：将各个文件卷划分为目录区、文件区

目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据

文件区用于存放文件数据

2）空闲表法 ​

为一个文件分配连续的存储空间。

可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

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

3）空闲链表法 ​

空闲盘块链：以盘块为单位组成一条空闲链。分配时从链头依次取出空闲块，回收时将空闲块查到链尾。

空闲盘区链：以盘区为单位组成一条空闲链。分配时可采用首次适应、最佳适应等策略，回收时注意相邻空闲盘区合并的问题。

4）位示图法 ​

位示图：每个二进制位对应一个盘块。可以用**（字号，位号）**对应一个盘块号。

注意题目条件：盘块号、字号、位号到底是从0开始还是从1开始

(字号, 位号)=(i, j) 的二进制位对应的 盘块号 b = ni + j

b号盘块对应的字号 i = b/n，位号 j = b%n

5）成组链接法 ​

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

理解即可，不方便用文字描述的知识点也很难作为考题

咸鱼学长这里讲的比较一般，参考【天勤考研】成组链接法

分组：

1号块为超级块，超级块需要调入内存

1块的空间用完之后，将2块调入内存

5、文件基本操作 ​

创建文件：分配外存空间，创建目录项

删除文件：回收外存空间，删除目录项

打开文件：

1. 将目录项中的信息复制到内存中的打开文件表中，并将打开文件表的索引号（文件描述符）返回给用户
2. 打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作
3. 每个进程有自己的打开文件表，系统中也有一张总的打开文件表
4. 进程打开文件表中特有的属性：读写指针、访问权限（只读？读写？）
5. 系统打开文件表中特有的属性：打开计数器（有多少个进程打开了该文件）

关闭文件：

1. 将进程打开文件表中的相应表项删除
2. 系统打开文件表的打开计数器减1，若打开计数器为0，则别除系统表的表项

读文件：根据读指针、读入数据量、内存位置将文件数据从外存读入内存

写文件：根据写指针、写出数据量、内存位置将文件数据从内存写出外存

6、文件系统的层次结构 ​

用一个例子来辅助记忆文件系统的层次结构：

假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后100条记录。

1. 用户需要通过操作系统提供的接口发出上述请求——用户接口
2. 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项——文件目录系统
3. 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块（存取控制验证层）
4. 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区
5. 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统
6. 要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块
7. 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块

三、磁盘 ​

1、磁盘的结构 ​

1）磁盘、磁道、扇区 ​

磁盘由表面涂有磁性物质的圆形盘片组成

每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区

最内侧磁道上的扇区面积最小，因此数据密度最大

2）如何在磁盘中读/写数据 ​

磁头移动到目标位置，磁片旋转，对应扇区划过磁道才能完成读写

3）盘面、柱面的概念 ​

磁盘有多个盘片“摞”起来，每个盘片有两个盘面

所有盘面中相对位置相同的磁道组成柱面

4）磁盘的物理地址 ​

（柱面号，盘面号，扇区号）

5）磁盘的分类 ​

根据磁头是否可移动：固定头磁盘（每个磁道有一个磁头）、移动头磁盘（每个盘面只有一个磁头）

根据盘片是否可更换：固定盘磁盘、可换盘磁盘

2、磁盘调度算法 ​

1）一次读写的时间 ​

寻道时间：启动磁臂、移动磁头所花的时间

① 启动磁头臂是需要时间的。假设耗时为 s；

② 移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为 m，总共需要跨越 n 条磁道。

则寻道时间 TS = s + m * n

延迟时间：将目标扇区转到磁头下面所花的时间

设磁盘转速为 r （单位：转/秒，或 转/分）

则平均所需的延迟时间 TR = (1/2) * (1/r) = 1/(2r)

传输时间：读/写数据花费的时间

假设磁盘转速为 r，此次读/写的字节数为 b，每个磁道上的字节数为 N

传输时间Tt = (1/r) * (b/N) = b/(rN)

2）先来先服务（FCFS） ​

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

优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去

缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。

3）最短寻找时间优先 （SSTF） ​

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

贪心算法的思想，能保证眼前最优，但无法保证总的寻道时间最短

优点：性能较好，平均寻道时间短

缺点：可能导致饥饿

4）扫描算法（电梯算法、SCAN） ​

只有磁头移动到最边缘的磁道时才可以改变磁头移动方向

缺点：对各个位置磁道的响应频率不平均

5）循环扫描算法（C-SCAN） ​

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

6）LOOK算法 ​

SCAN 算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向

7）C-LOOK 算法 ​

C-SCAN 算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回

3、减少延迟时间的优化 ​

1）交替编号 ​

磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”

具体做法：让编号相邻的扇区在物理上不相邻

原理：读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区

2）错位命名 ​

具体做法：让相邻盘面的扇区编号"错位"

原理：与"交替编号"的原理相同。"错位命名法”可降低延迟时间

3）磁盘地址结构的设计 ​

磁盘的物理地址是**（柱面号，盘面号，扇区号）**

在读取地址连续的磁盘块时，不需要移动磁头

4、磁盘的管理 ​

1）磁盘初始化 ​

1. 低级格式化/物理格式化：划分扇区
2. 磁盘分区 （C盘、D盘、E盘）
3. 逻辑格式化：建立文件系统（建立根目录文件、建立用于存储空问管理的数据结构）

2）引导块 ​

计算机启动时需要运行初始化程序（自举程序）来完成初始化

ROM中存放很小的自举装入程序

完整的自举程序存放在初始块（引导块）中

3）坏块的管理 ​

简单的磁盘：逻辑格式化时将坏块标记出来（坏块对操作系统不透明）

复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区（坏块对操作系统透明）

I/O管理 ​

一、I/O控制器 ​

1、主要功能 ​

接受和识别CPU发出的命令（控制寄存器）

向CPU报告设备的状态（状态寄存器)

数据交换（数据寄存器，暂存输入/输出的数据）

地址识别（由I/O逻辑实现)

2、组成 ​

CPU与控制器之间的接口：实现控制器与CPU之间的通信

I/O逻辑：负责识别CPU发出的命令，并向设备发出命令

控制器与设备之间的接口：实现控制器与设备之间的通信

一个I/O控制器可能会对应多个设备

数据寄存器、控制寄存器、状态寄存器可能有多个

3、寄存器编址方式 ​

1）内存映射I/O ​

控制器中的寄存器与内存统一编制

可以采用对内存进行操作的指令来对控制器进行操作

2）寄存器独立编制 ​

控制器中的寄存器独立编制

需要设置专门的指令来操作控制器

二、I/O控制方式 ​

计算机组成原理-IO系统

三、I/O软件层次结构 ​

用户层软件：实现与用户交互的接口，向上提供方便易用的库函数

设备独立性软件：

1. 向上层提供统一的调用接口（如 read/write 系统调用）
2. 设备的保护
3. 差错处理
4. 设备的分配与回收
5. 数据缓冲区管理
6. 建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序

设备驱动程序：设置设备寄存器、检查设备状态

中断处理程序：进行中断处理

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

直接涉及到硬件具体细节、且与中断无关的操作肯定是在设备驱动程序层完成的

没有涉及硬件的、对各种设备都需要进行的管理工作都是在设备独立性软件层完成的

四、I/O核心子系统 ​

1、概述 ​

2、假脱机技术 ​

脱机技术：解决设备与CPU的速度矛盾，实现预输入缓输出

假脱机技术：又叫SPOOLing技术，用软件的方式模拟脱机技术

1. 输入井和输出井：模拟脱机输入/输出时的磁带
2. 输入进程和输出进程：模拟脱机输入/输出时的外围控制机
3. 输入缓冲区和输出缓冲区：内存中的缓冲区，输入、输出时的"中转站"

3、设备的分配与回收 ​

1）考虑的因素 ​

1. 固有属性 ：独占设备、共享设备、虚拟设备（SPOOLing）
2. 分配算法：先来先服务、优先级高者优先、短任务优先等
3. 安全性：安全分配方式、不安全分配方式

2）静态分配与动态分配 ​

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源

动态分配：进程运行过程中动态申请设备资源

3）设备分配管理中的数据结构 ​

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

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

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

通道控制表（CHCT）：每个控制器对应一张CHCT，关键字段：状态/待队列指针

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

4）设备分配的步骤 ​

1. 根据进程请求的物理设备名查找SDT
2. 根据SDT找到DCT并分配设备
3. 根据DCT找到COCT并分配控制器
4. 根据COCT找到CHCT并分配通道

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

缺点：用户编程时必须使用"物理设备名"，若换了一个物理设备，则程序无法运行。若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

5）设备分配步骤的改进 ​

逻辑设备表（LUT）建立了逻辑设备名与物理设备名之间的映射关系。

用户编程时使用逻辑设备名申请设备，操作系统负责实现从逻辑设备名到物理设备名的映射（通过LUT）

• 整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复
• 每个用户一张LUT：各个用户的逻辑设备名可重复

4、缓冲区管理 ​

1）缓冲区的概念 ​

一般利用内存作为缓冲区

缓冲区作用：

1. 缓解CPU与设备的速度矛盾
2. 减少对CPU的中断频率
3. 解决数据粒度不匹配的问题
4. 提高CPU与I/O设备之间的并行性

2）单缓冲 ​

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

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

T > C，因此CPU处理完数据后暂时不能将下一块数据传送到工作区，必须等待缓冲区中冲满数据

T < C，因此缓冲区中冲满数据后暂时不能继续冲入下一块数据，必须等待CPU处理结束后将数据从缓冲区传送到工作区

处理一块数据平均耗时 Max(C, T)+M

分析问题的初始状态：工作区满，缓冲区空

3）双缓冲 ​

T > C + M

T < C + M

处理一块数据平均耗时 Max(T, C+M)

分析问题的初始状态：工作区空，一个缓冲区满，另一个缓冲区空

4）循环缓冲 ​

多个缓冲区链接成循环队列，in指针指向第一个空缓冲区，out指针指向第一个满缓冲区

5）缓冲池 ​

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

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