EastWind

Home

Archive

Links

About

操作系统

2025-07-21

概念

操作系统(Operating System，OS)是指控制和管理整个计算机系统的硬件和软件资源，并合理的组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的系统软件

  1. 操作系统是系统资源的管理者
  2. 向上层提供方便易用的服务
  3. 是最接近硬件的一层软件

执行一个程序前需要将该程序放到内存中，才能被CPU处理

image-20250806215335149 image-20250806215527318 image-20250806215854046

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

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

特征

并发&共享

并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的。但微观上是交替发生的

常考易混概念---并行：指两个或多个事件在同一时刻同时发生

并发其实可以这么理解，某一个时间段，你在做一件事情，炒菜，但炒菜这里包含多个工作，它是交替执行的，比如说8点切菜，9点烧菜，从宏观上看，它只在做一件事，炒菜，但从微观上看，这些动作是交替的

而并行就是说，8点炒菜并烧菜，这两个工作一起干，而不是分开干

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

操作系统就是伴随着“多道程序技术”而出现的。因此，操作系统和程序并发是一起诞生的

注意**(重要考点)**：

单核CPU同一时刻只能执行一个程序，各个程序只能并发执行

多核CPU同一时刻可以同时执行多个程序，多个程序可以并行执行

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

  • 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段只允许一个进程访问该资源
  • 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问

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

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

并发性和共享性互为共存条件

虚拟

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体(前者)是实际存在的，而逻辑上对应物(后者)是用户感受到的

可以这么理解，硬盘在电脑中是真实存在的，而硬盘分盘是一种逻辑上的分盘操作，并没有真实的把硬盘分割成几个小硬盘

异步

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

系统资源可能因某种情况而阻塞导致程序并不是同步的运行过去，而是异步的不按规定去运行

如果失去了并发性，即系统只能串行地运行各个程序，那么每个程序的执行会一贯到底。只有系统拥有并发性，才有可能导致异步性

发展&分类

手工操作阶段

程序猿将程序[二进制]写到纸带上，然后将纸带装到纸带机上，接着计算机需要将纸带机的数据读取，并给出纸带结果，最终程序猿需要取走纸带

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

批处理阶段

单道批处理系统

引入脱机输入/输出技术(用外围机+磁带完成)，并由监督程序负责控制作业的输入、输出【操作系统的雏形】

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

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

多道批处理系统

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

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

主要缺点：用户响应时间长，没有人机交互功能（用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业执行。）

eg：无法调试程序/无法在程序运行过程中输入一些参数

分时操作系统

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

主要优点：用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。

主要缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性

实时操作系统

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

在实时操作系统的控制下，计算机系统接收到外部新号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性

实时操作系统分为硬实时系统和软实时系统

  • 硬实时系统：必须在绝对严格的规定时间内完成处理
  • 软实时系统：能接受偶尔违反时间规定

其他操作系统

网络操作系统：是伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享(如文件共享)和各台计算机之间的通信。（如：Windows NT就是一种典型的网络操作系统，网站服务器就可以使用）

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

个人计算机操作系统：如Windows XP、MacOS，方便个人使用

运行机制

我们普通程序员写的程序就是“应用程序”

微软、苹果有一帮人负责实现操作系统，他们写的是“内核程序”

由很多内核程序组成了“操作系统内核”，简称“内核(Kernel)”

内核是操作系统最重要最核心的部分，也是最接近硬件的部分

甚至可以说，一个操作系统只要有内核就够了(eg：Docker->仅需Linux内核)

操作系统的功能未必都在内核中，如图形化用户界面GUI

  • 应用程序只能使用“非特权指令”，如：加法、减法指令等
  • 操作系统内核作为“管理者”，有时会让CPU执行一些“特权指令”，如：内存清零指令。
  • 这些指令影响重大，只允许管理者---即操作系统内核来使用

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

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

  • 处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令
  • 处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令
  • 拓展：CPU中有一个寄存器叫程序状态字寄存器(PSW)，其中有个二进制位，1表示“内核态”，0表示“用户态”
  • 别名：内核态=核心态=管态；用户态=目态

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

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

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

操作系统运行机制

  1. 刚开机时，CPU为内核态，操作系统内核程序先上CPU运行
  2. 开机完成后，用户可以启动某个应用程序
  3. 操作系统内核程序在合适的时候主动让出CPU，让该应用程序上CPU运行
  4. 应用程序运行在用户态
  5. 此时，黑客在应用程序中植入了一条特权指令，企图破坏系统
  6. CPU发现接下来要执行的这条指令是特权指令，但是自己又处于用户态
  7. 这个非法事件会引发一个中断信号
  8. 中断使操作系统再次夺回CPU的控制权
  9. 操作系统会对引发中断的事件进行处理，处理完了再把CPU使用权交给别的应用程序

操作系统内核在让出CPU之前，会用一条特权指令把PSW的标志位设置为用户态

CPU检测到中断信号后，会立即变为“核心态”，并停止运行当前的应用，转而运行处理中断信号的内核程序

中断&异常

中断的作用

中断会使CPU由用户态变为内核态，使操作系统重新夺回对CPU的控制权

CPU上会运行两种程序，一种是操作系统内核程序(是整个系统的管理者)，一种是应用程序

在合适的情况下，操作系统内核会把CPU的使用权主动让给应用程序

“中断”是让操作系统内核夺回CPU使用权的唯一途径

如果没有中断机制，那么一旦应用程序上CPU运行，CPU就会一直运行在这个应用程序

中断的类型

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

eg：

  1. 试图在用户态下执行特权指令
  2. 执行除法指令时发现除数为0(若当前执行的指令是非法的，则会引发一个中断信号)
  3. 有时候应用程序想请求操作系统内核的服务，此时会执行一条特殊的指令---陷入指令，该指令会引发一个内部中断的信号(执行陷入指令，意味着应用程序主动地将CPU控制器还给操作系统内核。系统调用就是通过陷入指令完成的)

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

eg：

  1. 时钟中断---由时钟部件发来的中断信号(时钟部件每隔一个时间片(如50ms)会给CPU发送一个时钟中断信号)
  2. I/0中断---由输入/输出设备发来的中断信号(当输入输出任务完成时，向CPU发送中断信号)

中断的分类

内中断也称异常、例外

内中断由陷阱(陷入)、故障、终止组成

  • 陷阱(陷入)：由陷入指令引发，是应用程序故意引发的
  • 故障：由错误条件引起的，可能被内核程序修复。内核程序修复故障后会把CPU使用权还给应用程序，让它继续执行下去
  • 终止：由致命错误引起，内核程序无法修复该错误，因此一般不再将CPU使用权还给引发终止的应用程序，而是直接终止该应用程序。如：整数除0、非法使用特权指令

外中断也称中断

外中断包括但不限于时钟中断、I/0中断请求

中断的基本原理

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

如图所示

image-20250810100536411

系统调用

操作系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中，程序接口由一组系统调用组成

系统调用是操作系统提供给应用程序(程序员/编程人员)使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务

普通应用程序可直接进行系统调用，也可以使用库函数，有的库函数涉及系统调用，有的不涉及
编程语言向上提供库函数。有时会将系统调用封装成库函数，以隐藏系统调用的一些细节，使程序员编程更加方便
操作系统向上提供系统调用，使得上层程序能请求内核的服务
裸机
image-20250810101639955

应用程序通过系统调用请求操作系统的服务。而系统中的各种共享资源都由操作系统内核统一掌管，因此凡是与共享资源有关的操作(如存储分配、I/0操作、文件管理等)，都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作

系统调用按功能分类:

  1. 设备管理:完成设备的 请求/释放/启动 等功能
  2. 文件管理：完成文件的 读/写/创建/删除 等功能
  3. 进程控制：完成进程的 创建/撤销/阻塞/唤醒 等功能
  4. 进程通信：完成进程之间的 消息传递/信号传递 等功能
  5. 内存管理：完成内存的 分配/回收 等功能

体系结构

概念

计算机系统层次结构如图所示

image-20250810135929538

内核是操作系统最基本、最核心的部分

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

  • 内核
    • 时钟管理：实现计时功能
    • 中断处理：负责实现中断机制
    • 原语：
      • 是一种特殊的程序
      • 处于操作系统最底层，是最接近硬件的部分
      • 这种程序的运行具有原子性---其运行只能一气呵成，不可中断
      • 运行时间较短，调用频繁
    • 对系统资源进行管理的功能
      • 进程管理
      • 存储器管理
      • 设备管理

内核也分为大内核以及微内核

  • 大内核
    • 将操作系统的主要功能模块都作为系统内核，运行在核心态
    • 优点：高性能
    • 缺点：内核代码庞大，结构混乱，难以维护
  • 微内核
    • 只把最基本的功能保留在内核
    • 优点：内核功能少，结构清晰，方便维护
    • 缺点：需要频繁地在核心态和用户态之间切换，性能低

典型的大内核/宏内核/单内核 操作系统：Linux、UNIX

典型的微内核 操作系统：Windows NT

image-20250810142118058

如图所示

大内核中将系统的主要功能存储在内核态中,应用程序存储在用户态中

微内核只保留了最基本的功能在内核态中,其余的都在用户态中

总结图

image-20250810142422270

引导

操作系统引导(boot)---开机的时候，怎么让操作系统运行起来？

如图所示

image-20250810145237909

操作系统引导：

  1. CPU从一个特定主存地址开始，取指令，执行ROM中的引导程序(先进行硬件自检,再开机)
  2. 将磁盘的第一块---主引导记录读入内存,执行磁盘引导程序,扫描分区表
  3. 从活动分区(又称主分区，即安装了操作系统的分区)读入分区引导记录，执行其中的程序
  4. 从根目录下找到完整的操作系统初始化程序(即启动管理器)并执行，完成“开机”的一系列动作

虚拟机

虚拟机，使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器(Virtual Machine,VM)，每个虚拟机器都可以独立运行一个操作系统

同义术语：虚拟机管理程序/虚拟机监控程序/Virtual Machine Monitor/Hypervisor

如图所示

image-20250810154031211

对比如下

第一类简单来说就是多系统了,第二类是运行在某种虚拟程序上,比如vmware

image-20250810155402104

进程

概念

程序：是静态的，就是存放在磁盘里的可执行文件，一系列的指令集合

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

组成

当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”---PID（Process ID,进程ID）

操作系统要记录PID、进程所属用户ID(基本的进程描述信息，可以让操作系统区分各个进程)

（如：分配了多少内存、正在使用哪些I/O设备、正在使用哪些文件[可用于实现操作系统对进程的控制、调度]）

还要记录进程的运行情况（如：CPU使用时间、磁盘使用情况、网络流量使用情况等[可用于实现操作系统对进程的控制、调度]）

这些信息都被保存在一个数据结构PCB（Process Control Block）中，即进程控制块

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

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

一个**进程实体(进程映像)由PCB(进程控制块)、程序段(包含程序指令)、数据段(包含运行过程中产生的各种数据)**组成

进程是动态的，进程实体(进程映像)是静态的

进程实体反应了进程在某一时刻的状态(如:x++后，x=2)

特征

  • 动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的
  • 并发性：内存中有多个进程实体，各进程可并发执行
  • 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
  • 异步性：各进程是按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题
  • 结构性：每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成

状态&转换

  • 进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化PCB

  • 当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲的CPU，就暂时不能运行

  • 如果一个进程此时在CPU上运行，那么这个进程处于“运行态”

  • CPU会执行该进程对应的程序(执行指令序列)

  • 在进程运行的过程中，可能会请求等待某个事件的发生(如等待某种系统资源的分配，或者等待其他进程的响应)

  • 在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入阻塞态

  • 当CPU空闲时，又会选择另一个就绪态进程上CPU运行

  • 一个进程可以执行exit系统调用，请求操作系统终止该进程。

  • 此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB

image-20250811220223814

状态转换图如上

  • 运行态:占有CPU,并在CPU上运行(单CPU情况下，同一时刻只会有一个进程处于运行态，多核CPU情况下，可能有多个进程处于运行态)
  • 就绪态：已经具备运行条件，但由于没有空闲CPU，而暂时不能运行
  • 阻塞态(等待态)：因等待某一事件而暂时不能运行
  • 创建态(新建态)：进程正在被创建，操作系统为进程分配资源，初始化PCB
  • 终止态(结束态)：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

控制

概念

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能

简化理解：反正进程控制就是要实现进程状态转换

原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断

可以用关中断指令和开中断指令这两个特权指令实现原子性

CPU执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查

相关的原语

image-20250812102737653 image-20250812102846503 image-20250812103518269 image-20250812103650620

通信(IPC)

概念

进程间通信(Inter-Process Communication,IPC)是指两个进程之间产生数据交互

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

共享存储

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

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

消息传递

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

消息发送需要消息头和消息体

其中消息头包括：

  • 发送进程ID
  • 接收进程ID
  • 消息长度等格式化的信息

而消息传递有两种方式

  • 直接通信方式
  • 间接通信方式

通过“信箱”间接的通信，因此又被称为信箱通信方式

image-20250812153455651

直接通信方式如上图所示

image-20250812154030993

间接通信通信方式如上图所示

管道通信

image-20250812155653070

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

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

  • 各进程要互斥地访问管道(由操作系统实现)

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

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

  • 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案

    • 一个管道允许多个写进程，一个读进程(考试选这个)
    • 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据

  • 写进程往管道写数据，即便管道没被写满，只要管道没空，读进程就可以从管道读数据

  • 读进程从管道读数据，即便管道没被读空，只要管道没满，写进程就可以往管道写数据

挂起状态&七状态模型

暂时调到外存等待的进程状态为挂起状态(挂起态，suspend)

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

image-20250813160146674

七状态模型如上图所示

注意挂起和阻塞的区别，两种状态都是暂时不能获取CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中

有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列

信号

  • 信号量(Semaphore)---实现进程间的同步、互斥
  • 信号(Signal)---实现进程间通信(IPC,Inter Process Communication)

信号是用于通知进程某个特定事件已经发生。进程收到一个信号后，对该信号进行处理

注1：不同的操作系统对信号类型的定义不一样

注2：通常用宏定义常量表示信号名，如：#define SIGINT 2

When 什么时候处理信号？

  • 当用户从内核态转为用户态时(如：系统调用返回、或中断处理返回时)，例行检查是否有待处理信号，如果有，就处理信号

How 怎么处理信号？

  1. 执行操作系统为此类信号设置的缺省**(默认)信号处理程序**(某些信号默认忽略，不作处理)
  2. 执行进程为此类信号设置用户自定义信号处理程序(自定义信号处理程序将覆盖①)
  • 信号处理程序运行结束后，通常会返回进程的下一条指令继续执行(除非信号处理程序将进程阻塞或终止)
  • 一旦处理了某个信号，就将pending位重置位0
  • 重复收到的同类信号，将被简单地丢弃（因为仅有1bit记录一类待处理信号）
  • 当同时收到多个不同类信号时，通常先处理序号更小的信号

信号可以作为异常的配套机制，让进程对操作系统的异常处理进行补充

在进程运行过程中，某些特殊事件可能引发“异常”，操作系统内核负责捕获并处理异常

  • 有些异常可以由内核完成全部处理，此时就不必再使用信号机制
  • 有些异常无法由内核完成全部处理，可能还需要用户进程配合，此时就可以用“信号机制”与”异常机制“相互配合（如：在Linux中，会发生除以0异常时，内核的异常处理程序会向用户进程发送SIGFPE信号。SIGFPE信号的默认处理程序会终止并转储内存；当然进程可以自定义SIGFPE信号处理程序）

线程

概念

可以把线程理解为“轻量级进程”

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

引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务(如QQ视频、文字聊天、传文件)

引入线程后，进程只作为除CPU之外的系统资源的分配单元(如打印机、内存地址空间等都是分配给进程的)

特点

引入线程机制后带来的变化

  • 资源分配、调度
    • 传统进程机制中，进程是资源分配、调度的基本单位
    • 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
  • 并发性
    • 传统进程机制中，只能进程间并发
    • 引入线程后，各线程间也能并发，提升了并发度
  • 系统开销
    • 传统的进程间并发，需要切换进程的运行环境，系统开销很大
    • 线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
    • 引入线程后，并发所带来的系统开销减小

属性

  • 线程是处理机调度的单位
  • 多CPU计算机中，各个线程可占用不同的CPU
  • 每个线程都有一个线程ID、线程控制块(TCB)
  • 线程也有就绪、阻塞、运行三种基本状态
  • 线程几乎不拥有系统资源
  • 同一进程的不同线程间共享进程的资源
  • 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
  • 同一进程中的线程切换，不会引起进程切换
  • 不同进程中的线程切换，会引起进程切换
  • 切换同进程内的线程，系统开销很小
  • 切换进程，系统开销较大

实现方式

用户级线程

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

“用户级线程”就是“从用户视角可以看到的线程”

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

内核级线程

  1. 内核级线程的管理工作由操作系统内核完成
  2. 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成
  3. 操作系统会为每个内核级线程建立相应的TCB(Thread Control Block，线程控制块)，通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角能看到的线程”
  • 优缺点
    • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程还在多核处理机上并行执行
    • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

多线程模型

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

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

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

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

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

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

重点：操作系统只看得见内核级线程，因此只有内核级线程才是处理机分配的单位，所以无法并行

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

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

可以这么理解：

用户级线程是“代码逻辑”的载体

内核级先是“运行机会”的载体

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

状态与转换

如图所示，其实线程的状态与转换和进程是类似的，几乎没区别

image-20250813145901208

进程调度

概念

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是调度研究的问题

高级调度

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

作业：一个具体的任务

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

低级调度

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

进程调度是操作系统中最基本的一种调度，在一般的操作系统中年都必须配置进程调度

进程调度的频率很高，一般几十毫秒一次

中级调度

内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存

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

中级调度(内存调度)---按照某种策略决定将哪个处于挂起状态的进程重新调入内存

一个进程可能会被多次调入和调出，因此中级调度发生的频率比高级调度更高

调度对比

要做什么调度发生发生频率对进程状态的影响
高级调度
(作业调度)		按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程外存->内存
(面向作业)		最低无->创建态->就绪态
中级调度
(内存调度)		按照某种规则，从挂起队列中选择合适的进程将其数据调回内存外存->内存
(面向进程)		中等挂起态->就绪态
(阻塞挂起->阻塞态)
低级调度
(进程调度)		按照某种规则，从就绪队列中选择一个进程为其分配处理机孽畜->CPU最高就绪态->运行态

时机

进程调度(低级调度)，就是按照某种算法从就绪队列中选择一个进程为其分配处理机

  • 需要进行进度调度与切换的情况
    • 当前运行的进程主动放弃处理机
      • 进程正常终止
      • 运行过程中发生异常而终止
      • 进程主动请求阻塞(如等待I/0)
    • 当前运行的进程被动放弃处理机
      • 分给进程的时间片用完
      • 有更紧急的事需要处理(如I/O中断)
      • 有更高优先级的进程进入就绪队列
  • 不能进行进程调度与切换的情况
    1. 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换
    2. 进程在操作系统内核程序临界区中
    3. 在原子操作过程中(原语)。原子操作不可中断，要一气呵成

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

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源

临界区：访问临界资源的那段代码

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成)

普通临界区是可以进行调度和切换的，内核临界区不可以

方式

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程或主动要求进入阻塞态，实现简单，系统开销小，但是无法及时处理紧急任务，适合于早期的批处理系统

剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧迫的那个进程，可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合于分时操作系统、实时操作系统

切换与过程

“狭义的进程调度”与“进程切换”的区别

狭义的进程调度指的是从就绪队列中选出一个要运行的进程。(这个进程可以是刚刚被暂停执行的过程，也可能是另一个进程，后一种情况就需要进程切换)

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程

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

进程切换的过程主要完成了：

  1. 对原来运行进程各种数据的保存
  2. 对新的进程各种数据的恢复(如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块)

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

调度器/调度程序

image-20250814102307432

②、③由调度程序引起，调度程序决定：

  • 让谁运行---调度算法
  • 运行多长时间---时间片大小

调度时机---什么事件会触发调度程序

  • 创建新进程
  • 进程退出
  • 运行进程阻塞
  • I/O中断发生(可能唤醒某些阻塞进程)
  • 非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作
  • 抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作

闲逛进程

调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程(idle)

闲逛进程的特性：

  • 优先级最低
  • 可以是0地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)
  • 能耗低

评价指标

CPU利用率

由于早期的CPU造价极其昂贵，因此人们会希望让CPU尽可能多的工作

CPU利用率：指CPU“忙碌”的时间占总时间的比例 $$ 利用率=\frac{忙碌的时间}{总时间} \ Eg:\ 某计算机只支持单道程序\ 某个作业刚开始需要在CPU上运行5秒，再用打印机打印输出5秒，之后再执行5秒才能结束。\ 在此过程中，CPU利用率、打印机利用率分别是多少？\ CPU利用率=\frac{5+5}{5+5+5}=66.66% \ 打印机利用率=\frac{5}{15}=33.33% $$

系统吞吐量

对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业

系统吞吐量：单位时间内完成作业的数量 $$ 系统吞吐量=\frac{总共完成了多少道作业}{总共花了多少时间} \ Eg:某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为？\ \frac{10}{100} = 0.1道/秒 $$

周转时间

对于计算机的用户来说，他很关心自己的作业从提交到完成花了多少时间

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

它包括四个部分：作业在外存后备队列上等待作业调度(高级调度)的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次

(作业)周转时间=作业完成时间-作业提交时间

对于用户来说，更关心自己单个作业的周转时间 $$ 平均周转时间=\frac{各作业周转时间之和}{作业数} $$ 对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高 $$ 带权周转时间=\frac{作业周转时间}{作业实际运行时间}=\frac{作业完成时间-作业提交时间}{作业实际运行的时间}\ 平均带权周转时间=\frac{各作业带权周转时间之和}{作业数} $$

等待时间

计算机的用户希望自己的作业尽可能少的等待处理机

等待时间，指进程/作业处于等待处理机状态时间之和,等待时间越长，用户满意度越低

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间

一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。当然，与前面的指标类似，也有“平均等待时间”来评价整体性能

响应时间

对应计算机用户来说，会希望自己的提交的请求(比如通过键盘输入了一个调试命令)尽早地开始被系统服务、回应

响应时间，指从用户提交请求到首次产生响应所用时间

调度算法

先来先服务

先来先服务(FCFS，First Come First Serve)

  • 主要从公平的角度考虑(类似于排队)
  • 按照作业/进程到达的先后顺序进行服务
  • 用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列
  • 非抢占式算法
  • 优点：公平、算法实现简单
  • 缺点：排在长作业(进程)后面的短作业需要等待很长时间，带权周期时间很大，对短作业来说用户体验不好。即FCFS算法对长作业有利，对短作业不利(Eg:排队)
  • 不会饥饿(饥饿是指某进程/作业长期得不到服务)

例题如下

image-20250814145328008

短作业优先

短作业优先(SJF,Shortest Job First)

  • 追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间
  • 最短的作业/进程优先得到服务(所谓“最短”，是指要求服务时间最短)
  • 可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先(SPF,Shortest Process First)”算法
  • SJF和SPF是非抢占式的算法。但是也有抢占式的版本---最短剩余时间优先算法(SRTN,Shortest Remaining Time Next)
  • 优点：“最短的”平均等待时间、平均周转时间
  • 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外。作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
  • 会饥饿。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生饥饿现象。如果一直得不到服务，则称为饿死

非抢占式短作业优先算法例题如下

image-20250814150546467

抢占式短作业优先算法解析

image-20250814151147429

抢占式短作业优先算法例题

image-20250814151323484

注意几个小细节：

  1. 如果题目中未特别说明，所提到的短作业/进程优先算法，默认是非抢占式的

  2. 很多书上都会说“SJF调度算法的平均等待时间、平均周转时间最少”

    严格来说，这个表述是错误的，不严谨的。

    之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少

    应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”；

    或者说“在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”；

    如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法(最短剩余时间优先，SRNT算法)的平均等待时间、平均周转时间最少”

  3. 虽然严格来说，SJF的平均等待时间、平均周转时间并不是最少，但相比于其他算法(如FCFS)，SJF依然可以获得较少的平均等待时间、平均周转时间

  4. 如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项

高响应比优先

高响应比优先(HRRN,Highest Response Ratio Next)

  • 要综合考虑作业/进程的等待时间和要求服务的时间

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

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

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

  • 属于非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比

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

  • 不会饥饿

例题如下

image-20250814155526360

时间片轮转

时间片轮转(RR,Round-Robin)

  • 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
  • 按照各进程到达就绪队列的顺序，轮流让每个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
  • 用于进程调度(只有作业放入内存建立了相应的进程后，才能被分配处理时间片)
  • 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到
  • 优点：公平；响应快，适用于分时操作系统；
  • 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度
  • 不会饥饿

如果时间片太大，使得每个进程都可以在一个时间片内完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大

另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小

例题如下

image-20250815102227212

优先级

优先级调度算法

  • 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
  • 调度时选择优先级最高的作业/进程
  • 既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中
  • 抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占
  • 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度
  • 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
  • 会饥饿

非抢占式例题

image-20250815104017583

抢占式例题

image-20250815104605357

补充：

就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。

  • 静态优先级：创建进程时确定，之后一直不变
  • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级

如何合理地设置各类进程的优先级？

通常：系统进程优先级高于用户进程，前台进程优先级高于后台进程，操作系统更偏好I/O型进程(或称I/O繁忙型进程)

注：与I/O型进程相对的是计算型进程(或称CPU繁忙型进程)

I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升

如果采用的是动态优先级，什么时候应该调整？

可以从追求公平、提升资源利用率等角度考虑

如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级

如果某进程占用处理机运行了很长时间，则可适当降低其优先级

如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级

多级反馈队列

多级反馈队列调度算法

  • 对其他调度算法的折中权衡
  • 规则
    1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
    2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
    3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片
  • 用于进程调度
  • 抢占式的算法。在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程，由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾
  • 对各类进程相对公平(FCFS的优点)；每个新到达的进程都可以很快就得到响应(RR)的优点；短进程只用较少的时间就可以完成(SPF的优点)；不必实现估计进程的运行时间(避免用户造假)；可灵活地调整对各类进程的偏好程度，比如CPU密集进程、I/O密集型进程(拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级)
  • 会饥饿

例题

image-20250815111515250

多级队列

多级队列调度算法

image-20250815140753659

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

队列之间可采取固定优先级，或时间片划分

  • 固定优先级：高优先级空时，低优先级进程才能被调度
  • 时间片划分：如三个队列分配时间50%、40%、10%

各队列可采用不同的调度策略，如：

  • 系统进程队列采用优先级调度
  • 交互式队列采用RR
  • 批处理队列采用FCFS

总结

算法可抢占？优点缺点考虑到等待时间&运行时间？会导致饥饿？
FCFS非抢占式公平；实现简单对短作业不利考虑等待时间
不考虑运行时间		不会
SJF/SPF默认为非抢占式，也有SJF的抢占式，即版本最短剩余时间优先算法(SRTN)“最短的”平均等待/周转时间对长作业不利；难以做到真正的短作业优先考虑等待时间
不考虑运行时间		会
HRRN非抢占式完善上述算法考虑等待时间
考虑运行时间		不会
时间片轮转抢占式公平，适用于分时系统频繁切换与开销，不区分优先级不会
优先级都有区分优先级，适用于实时操作系统可能会饥饿会
多级反馈队列抢占式优秀一般无缺点，可能会饥饿

多处理机调度

概念

单处理机调度：只需决定让哪个就绪进程优先上处理机即可

多处理机调度：

  1. 用调度算法决定让哪个就绪进程优先上处理机
  2. 还需决定被调度的进程到底上哪个处理机

多处理机调度中，应追求的目标：

  • 负载均衡---尽可能让每个CPU都同等忙碌
  • 处理机亲和性---尽量让一个进程调度到同一个CPU上运行，以发挥CPU中缓存的作用(Cache)

公共就绪队列

  • 所有CPU共享同一个就绪进程队列(位于内核区)
  • 每个CPU运行调度程序时，从公共就绪队列中选择一个进程运行
  • 每个CPU访问公共就绪队列时需要上锁(确保互斥)

优点：可以天然地实现负载均衡

缺点：各个进程频繁地切换CPU运行，“亲和性”不好

如何提示处理机亲和性？

  • 软亲和：由进程调度程序尽量保证“亲和性”
  • 硬亲和：由用户进程通过系统调用，主动要求操作系统分配固定的CPU，确保“亲和性”

私有就绪队列

  • 每个CPU都有一个私有就绪队列
  • CPU空闲时运行调度程序，从私有就绪队列中选择一个进程运行

如何实现负载均衡？

推迁移(Push)策略:

一个特定的系统程序周期性检查每个处理器的负载,如果负载不平衡,就从忙碌CPU的就绪队列中”推”一些就绪进程到空闲CPU的就绪队列中

拉迁移(Pull)策略:

每个CPU运行调度程序时,周期性检查自身负载与其他CPU负载.如果一个CPU负载很低,就从其他高负载CPU的就绪队列中”拉”一些就绪进程到自己的就绪队列

优点:天然地实现了处理机亲和性

同步&互斥

进程同步

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

进程互斥

概念

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

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

对临界资源的互斥访问，可以在逻辑上分为如下四个部分

  • 进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志(可理解为“上锁”)，以阻止其他进程同时进入临界区
  • 临界区：访问临界资源的那段代码
  • 退出区：负责解除正在访问临界资源的标志(可理解为“解锁”)
  • 剩余区：做其他处理

注意：

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

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

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

软件实现方法

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个赋予

image-20250816102046745

上图是具体过程

因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”

但算法有个致命的缺陷，只能按P0->P1->P0->P1->…这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时运行进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。

因此，单标志法存在的主要问题是：违背“空闲让进”原则

双标志先检查法

算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿,比如“flag[0]=true”，意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区

image-20250816102905161

如上图所示

若按照①⑤②⑥③⑦…的顺序执行，P0和P1将会同时访问临界区，因为进程可能并发执行，导致还没做判断时就被切换到另一个进程了

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

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

双标志后检查法

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，结果导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题

image-20250816103648339

如上图所示

若按照①⑤②⑥…的顺序执行，P0和P1将都无法进入临界区

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

Peterson算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试谦让。

做一个有礼貌的进程。

image-20250816104506485

如上图所示

看着很复杂，其实很简单

在进入区做了这些操作

  1. 主动争取资源
  2. 主动谦让
  3. 检查对方是否也想使用，且最后一次不是自己做了谦让动作

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

硬件实现方法

中断屏蔽方法

利用“开/关中断指令”实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

关中断后即不允许当前进程被中断，也必然不会发生进程切换

直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区

通常是在进入临界区前关中断，离开后开中断

优点：简单、高效

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

TestAndSet

简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令

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

以下是用C语言描述的逻辑

image-20250816145451220

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境

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

Swap指令

有的地方也叫Exchange指令，或简称XCHG指令

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

以下是用C语言描述的逻辑

image-20250816145022673

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境

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

互斥锁

解决临界区最简单的工具就是互斥锁(mutex lock)。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁。

每个互斥锁都有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

acquire()
    while(!available)
        ;  // 忙等待
     available = false;  // 获得锁
release(){
    available = true;  // 释放锁
}

acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现

互斥锁的主要缺点是忙等待，当有一个进程在临界区时，任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行

需要连续循环忙等待的互斥锁，都可称为自旋锁(spin lock)，如TSL指令、swap指令、单标志法

特性：

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

信号量机制

概念

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步

信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号内的信号量S其实就是函数调用时传入的一个参数

wait、signal原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此，做题的时候常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)

整型信号量

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

与普通整数变量的区别：

  • 对信号量的操作只有三种，即初始化、P操作、V操作

示例如下

image-20250816163320794

记录型信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量

示例如下

image-20250816163909397

// 记录型信号量的定义
typedef struct{
    int value;  // 剩余资源数
    Struct process *L;  // 等待队列
}


// 某进程需要使用资源时，通过wait 原语申请
void wait(semaphore S){
    S.value--;
    if(S.value < 0){
        block(S.L)
    }
}


// 进程使用完资源后，通过signal 原语释放
void signal(semaphore S){
    S.value++;
    if(S.value <= 0){
        wakeup(S.L);
    }
}

在考研题目中wait(S)、signal(S)也可以记为P(S)、V(S)，这对原语可用于实现系统资源的“申请”和“释放”

S.value的初值表示系统中某种资源的数目

对信号量S的一次P操作意味着进程请求一个单位的该类资源,因此需要执行S.value—，表示资源数减1，当S.value<0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞(当前运行的进程从运行态->阻塞态)，主动放弃处理机，并插入该类资源的等待队列S.L中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象

对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数加1，若加1后仍是S.value<=0，表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态->就绪态)

实现进程互斥

  1. 分析并发进程的关键活动，划定临界区(如：对临界资源打印机的访问就应该放在临界区)
  2. 设置互斥信号量mutex，初值为1
  3. 在进入区P(mutex)---申请资源
  4. 在退出区V(mutex)---释放资源

代码示例如下

typedef struct{
    int value;  // 剩余资源数
    struct process *L;  // 等待队列
}semaphore;


// 信号量机制实现互斥
semaphore mutex = 1;  // 初始化信号量
P1(){
    P(mutex);  // 使用临界资源前需要加锁
    临界资源代码段
    V(mutex);  // 使用临界资源后需要解锁
}


P2(){
    P(mutex);  // 使用临界资源前需要加锁
    临界资源代码段
    V(mutex);  // 使用临界资源后需要解锁
}

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

P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒

实现进程同步

进程同步：要让各并发进程按要求有序地推进

基于信号量实现进程同步，示例如下

  1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作(或两句代码)
  2. 设置同步信号量S，初始为0
  3. 在前操作之后执行V(S)
  4. 在后操作之前执行P(S)

口诀：前V后P

image-20250817143629145

实现前驱关系

其实每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作)

因此，

  1. 要为每一对前驱关系各设置一个同步信号量
  2. 在“前操作”之后对相应的同步信号量执行V操作
  3. 在“后操作”之前对相应的同步信号量执行P操作

生产者-消费者

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区取出一个产品并使用。(注：这里的“产品”理解为某种数据)

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

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

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

缓冲区是临界资源，各进程必须互斥访问(互斥关系)

如图所示

image-20250817161413295

semaphore mutex = 1;    // 缓冲区互斥信号量
semaphore empty = n;    // 缓冲区空闲位置数量
semaphore full = 0;     // 缓冲区物品数量


Process producer() {
    while(1) {
        生产一个物品;
        P(empty);    // 请求缓冲区一个空位
        P(mutex);
        往缓冲区中放入一个物品;
        V(mutex);
        V(full);    // 缓冲区物品数量加一
    }
}
Process consumer() {
    while(1) {
        P(full);    // 请求缓冲区一个物品
        P(mutex);
        从缓冲区中取出一个物品;
        V(mutex);
        V(empty);    // 缓冲区空位数量加一
        消费一个物品;
    }
}

多生产者-多消费者

桌子上有一只盘子，每次只能向其中放入一只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。image-20250818094106023

具体情况如上图所示

互斥关系：

对缓冲区(盘子)的访问要互斥的进行

同步关系(一前一后)：

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

盘子为空这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果

semahore 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);
            吃掉橘子;
    }
}

当然，这里也可以不设置互斥信号量，因为此处的信号量，至多只有一个是为1的，用完了就会唤醒其他的

比如说：父亲进程先上来，它准备了一个苹果，然后放入盘子，此刻改变了盘子的值，接着释放了苹果的信号量，让吃苹果的来进行消费，此时苹果会被吃掉，因为之前父亲最后执行了P操作，接着释放掉盘子，让父亲或母亲继续放水果，而在这期间，并没有额外的增长其他的信号量，只有被消费的苹果和被重新生产的盘子

在生产者-消费者问题中，如果缓冲区为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。得看情况分析

读者-写者

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的度进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：

  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名哲学家，每两个哲学家之间的桌上摆着一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

而5位哲学家对中间的筷子必然是互斥关系，当5位哲学家都各自持有一根筷子时，就会出现死锁问题

如何防止死锁的发生呢？

  1. 可以对哲学家进餐施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有应该哲学家是可以拿到左右两只筷子的
  2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况
  3. 各哲学家拿筷子这件事必须互斥地执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了

管程

概念

管程是一种特殊的软件模块，由这些部分组成：

  1. 局部于管程的共享数据结构说明
  2. 对该数据结构进行操作的一组过程
  3. 对局部于管程的共享数据设置初始值的语句
  4. 管程有应该名字

过程其实就是函数

管程的基本特征

  1. 局部于管程的数据只能被局部于管程的过程所访问
  2. 一个进程只有通过管程内的过程才能进入管程访问共享数据
  3. 每次仅允许一个进程在管程内执行某个内部过程

死锁

概念

每个人都占有一个资源，同时又在等待另一个人手里的资源。发生“死锁”

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是死锁。发生死锁后若无外力干涉，这些进程都将无法向前推进

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先(SPF)算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”

死循环：某进程设计过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的

共同点区别
死锁都是进程无法顺利向前推进的现象(故意设计的死循环除外)死锁一定是“循环等待对方手里的资源”导致的，因此如果有死锁现象，那么至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞态
饥饿可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态(如长期得不到需要的I/O设备)，也可能是就绪态(长期得不到处理机)
死循环可能只有一个进程发生死循环。死循环的进程可以上处理机运行(可以是运行态)，只不过无法像期待的那样顺利推进。死锁和饥饿问题是由操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。死锁和饥饿是管理者(操作系统)的问题，死循环是被管理者的问题

死锁产生的必要条件

  • 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子、打印机设备)。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源)
  • 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
  • 请求和保持条件：进程已经保持了至少一个资源,但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
  • 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

注意！发生死锁时一定有循环等待，但是发生循环等待时未必死锁(循环等待是死锁的必要不充分条件)

如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了

处理策略

预防死锁

破坏互斥条件

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

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

操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备

该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件

破坏不剥夺条件

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

破坏不剥夺条件：

方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源未使用完，也需要主动释放，从而破坏了不可剥夺条件

方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级(比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)

该策略的缺点：

  1. 实现起来比较复杂
  2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU
  3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量
  4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿

破坏请求和保持条件

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

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

该策略实现起来简单，但也有明显的缺点：

有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都保持着所有资源，就会造成严重的资源浪费，资源利用率低。另外，该策略也有可能导致某些进程饥饿

破坏循环等待条件

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

可采用顺序资源分配法.首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源,同类资源(即编号相同的资源)一次申请完

原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象

该策略的缺点：

  1. 不方便增加新的设备，因为可能需要重新分配所有的编号
  2. 进程实际使用的资源的顺序可能和编号递增顺序不一致，会导致资源浪费

避免死锁

安全序列

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

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

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁(处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)

因此可以在资源分配之前先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想

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

检测和解除

  1. 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁
  2. 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来

看视频吧，这章讲的比较抽象：https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=42

解除死锁的主要方法有：

  1. 资源剥夺法。挂起(暂时放到外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿
  2. 撤销进程法(或终止进程法)。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来
  3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点

如何决定“对谁动手”

  1. 进程优先级
  2. 已执行多长时间
  3. 还要多久能完成
  4. 进程已经使用了多少资源
  5. 进程是交互式的还是批处理式的

内存

基础知识

内存可存放数据。程序执行前需要放到内存中才能被CPU处理---缓和CPU与硬盘之间的速度矛盾

思考：在多道程序环境下，系统中会有多个程序并发执行，也就是说会有多个程序的数据需要同时放到内存中。那么，如何区分各个程序的数据是放在什么地方的呢？

方案：给内存的单元编地址

内存中也有一个一个的“小房间”，每个小房间就是一个“存储单位”

如果计算机“按字节编址”，则每个存储单元大小为1字节，即1B，即8个二进制位

如果字长位16位的计算机“按字编址”，则每个存储单位大小为1个字；每个字的大小为16个二进制位

绝对装入

绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存

编译、链接后得到的装入模块的指令直接就使用了绝对地址

绝对装入只适用于单道程序环境

可重定位装入

静态重定位：又称可重定位装入。编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相当于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变为物理地址(地址变换是在装入时一次完成的)

静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业

动态重定位

动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持

并且这种方法可以将程序分配到不连续的存储区中；在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间

采用动态重定位时允许程序在内存中发生移动

链接的三种方式

  1. 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件(装入模块)，之后不再拆开
  2. 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式
  3. 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享

内存管理

操作系统作为系统资源的管理者，也需要对内存进行管理，具体要管什么呢？

  1. 操作系统负责内存空间的分配与回收
  2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
  3. 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
  4. 操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰

内存保护可采用两种方法：

  1. 在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界
  2. 采用重定位寄存器(又称基址寄存器)和界地址寄存器(又称限长寄存器)进行越界检查。重定位寄存器存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址

进程的内存映像

具体情况如图所示

image-20250819141755796

覆盖

早期的计算机内存很小，比如IBM推出的第一台PC机最大只支持1MB大小的内存。因此经常会出现内存大小不够的情况

后来人们引入了覆盖技术，用来解决“程序大小超过物理内存总和”的问题

覆盖技术的思想：将程序分为多个段(多个模块)。

常用的段常驻内存，不常用的段在需要时调入内存

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

需要常驻内存的段放在“固定区”中，调入后就不再调出(除非运行结束)

不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存

覆盖技术如图所示

image-20250819142805408

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

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

覆盖技术只用于早期的操作系统中，现在已成为历史

交换

交换(对换)技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)

那么，也就出现了三个问题

  1. 应该在外存(磁盘)的上面位置保存被换出的进程
    • 具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式。总之，对换区I/O速度比文件区更快
  2. 什么时候应该交换
    • 交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生缺页，说明内存紧张，此时可以换出一些进程；如果缺页率明显下降，就可以暂停换出
  3. 应该换出哪些进程
    • 可以优先换出阻塞进程；可换出优先级低的进程；为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间

注意：PCB会常驻内存，不会被换出内存

连续分配管理方式

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

单一连续分配

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

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

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

优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护(eg：早期的PC操作系统MS-DOS)

缺点：只能用于单用户、单任务的操作系统中；有内部碎片(分配给某进程的内存区域中，如果有些部分没有用上，就是“内存碎片”)；存储器利用率极低

固定分区分配

20世纪60年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式

分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合(比如：钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序)

分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分(比如：划分多个小分区、适量中等分区、少量大分区)

如图所示

image-20250819164633438

操作系统需要建立一个数据结构---分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排序。每个表项包括对应分区的大小、起始地址、状态(是否已分配)

当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“已分配”

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

缺点：

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

动态分区分配

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

但这样又引出了新的问题

  1. 系统要用什么样的数据结构记录内存的使用情况
    • 空闲分区表：每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息
    • 空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息
  2. 当很多个空闲分区都能满足需求时，应选择哪个分区进行分配
    • 把一个新作业装入内存时，续按照一定的动态分区分配算法，从空闲分区表(或空闲分区链)中选出一个分区分配给该作业。由于分配算法对系统性能有很大的影响，因此人们对它进行了广泛的研究
  3. 如何进行分区的分配与回收操作？
    • 相邻空闲分区合并

动态分区分配没有内部碎片，但是有外部碎片

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

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

如果内存中空闲空间的总和可以满足某进程的要求

但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求

可以通过紧凑(拼凑，Compaction)技术来解决外部碎片

动态分区分配算法

首次适应算法

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

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

最佳适应算法

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

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

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

最坏适应算法

又称最大适应算法(Largest Fit)

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

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

缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了

邻近适应算法

算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址不符出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题

如何实现：空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区

总结

算法算法思想分区排列顺序优点缺点
首次适应从头到尾找适合的分区空闲分区以地址递增次序排列综合看性能最好。算法开销小，回收分区后一般
最佳适应优先使用更小的分区，以保留更多大分区空闲分区以容量递增次序排列会有更多大分区被保留下来，更能满足大进程需求会产生很多太小的、难以回收的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序
最坏适应优先使用更大的分区，以防止产生太小的不可用的碎片空闲分区以容量递减次序排列可以减少难以利用的小碎片大分区容易被用完，不利于大进程；算法开销大(原因同上)
邻近适应由首次适应演变而来，每次从上次查找结束为止开始查找空闲分区以地址递增次序排列(可排序成循环链表)不用每次都从低地址的小分区开始检索。算法开销小(原因同首次适应)会使高地址分区也被用完

基本分页存储管理

分页存储

将内存空间分为一个个大小相等的分区(比如：每个分区4KB)，每个分区就是一个“页框”(页框=页帧=内存块=物理块=物理页面)。每个页框有一个编号，即“页框号”(页框号=页帧号=内存块号=物理块号=物理页号)，页框号从0开始

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

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分部放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系

各个页面不必连续存放，可以放到不相邻的各个页框中

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

注：页表通常存在PCB(进程控制块)中

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

内存块比较容易理解一些，而内存块其实就是刚刚上面提到的页框，后续都以内存块进行讲解

针对上述概念，那么就存在一些问题

每个页表项占多少字节？ $$ Eg:假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？ \ 内存块大小=页面大小=4KB=4*1KB=2^{12} \ 1KB=1024B=2^{10}B \ 4=2^2 \ 4GB的内存总共会被分为2^{32}/2^{12}=2^{20}个内存块\ 4GB=2^{2} * 1GB= 2^{2} * 1024MB=2^{2} * 1024 * 1024KB=2^{2}2^{10}102410241B \ 整合上面的公式\ 2^{2}*2^{10}*2^{10}2^{10}1B=2^{32}B \ 因为内存被分成的块数=总内存除以每页大小 \ 所以内存块数的范围应该是0到2^{20}-1 \ 内存块数至少要用20bit来表示 至少要用3B来表示块号(38=24bit) $$ 页表中的页号是隐含的，即页号不占用存储空间，因此如上题所示，每个页表项占3B，存储整个页表至少需要3(n+1)B

这里的n+1是因为页号是从0开始的，所以需要+1

注意：页表记录的至少内存块号，而不是内存块的起始地址！

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

如何实现地址的转换？

  • 进程在内存中连续存放时，操作系统是如何实现逻辑地址到物理地址的转换的？
    • 重定位寄存器中指明了进程在内存中的起始位置,通常是通过目标逻辑地址与起始地址相加，就可以得到物理地址(绝对地址)了
    • 逻辑地址：相对于起始位置的偏移量
  • 将进程地址空间分页之后，操作系统是如何实现逻辑地址到物理地址的转换的？
    • 虽然进程的各个页面是离散存放的，但是页面内部是连续存放的
    • 如果要访问逻辑地址A，则
      1. 确定逻辑地址A对应的“页号”P
      2. 找到P号页面在内存中的起始地址(需要查页表)
      3. 确定逻辑地址A的“页内偏移量”W
    • 逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W

如何确定一个逻辑地址对应的页号、页内偏移量

Eg：在某计算机系统中，页面大小是50B。某进程逻辑地址空间大小为200B，则逻辑地址110对应的页号、页内偏移量是多少？

已知进程空间大小为200，页面大小为50，那么可以分为4个页面

页号=逻辑地址/页面长度(取除法的整数部分)=110/50=2

页内偏移量=逻辑地址%页面长度(取除法的余数部分)=110%50=10

逻辑地址可拆分为(页号，页内偏移量)

通过页号查询页表，可知页面在内存中的起始地址

页面在内存中的起始地址+页内偏移量=实际的物理地址

在计算机内部，地址是用二进制表示的，如果页面大小刚好是2的整数幂，则计算机硬件可以很快速的把逻辑地址拆分成(页号，页内偏移量) $$ 结论：如果每个页面大小为2^{K}B,用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号 $$

基本地址变换机构

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

通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M。

进程未执行时，页表的始址和页表长度放在进程控制块(PCB)中，当进程被调度时，操作系统内核会把它们放到页表寄存器中

注意：页面大小是2的整数幂

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

  1. 计算页号P和页内偏移量W(如果用十进制数手算，则P=A/L，W=A%L；但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量)
  2. 比较页号P和页表长度M，若P**>=**M，则产生越界中断，否则继续执行。(注意：页号是从0开始的，而页表长度至少是1，因此P=M时也会越界)
  3. 页表中页号P对应的页表项地址=页表地址F+页号P*页表项长度，取出该页表项内容b，即为内存块号。(注意区分页表项长度、页表长度、页面大小的区别。 页表长度指的是这个页表中总共有几个页表项，即总共有几个页；页表项长度指的是每个页表项占多大的存储空间； 页面大小指的是一个页面占多大的存储空间)
  4. 计算E=b*L+W，用得到的物理地址E去访存。(如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了)

具体情况如图所示

image-20250820161051287

具有快表的地址变换机构

局部性原理

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)

空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)

快表

快表，又称联想寄存器(TLB，translation lookaside buffer)，是一种访问速度比内存快很多的高速缓冲(TLB不是内存！)，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表

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

引入快表后，地址的变换过程

  1. CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较
  2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可
  3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应的页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存(注意：在找到页表项后，应同时将其存入快表，以便后面可能再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)

具体情况如图所示

image-20250821103722581

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。

因为局部性原理，一般来说快表的命中率可以达到90%以上

例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时1us，访问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少？

(1+100)*0.9+(1+100+100)*0.1=111us

为什么是这样呢，因为1us是快表查询速度，查询到了访问一次100us，命中率是90%，所以乘以0.9，那么剩下的就是慢表的查询了，需要查询一次快表，发现没有查到，再去查慢表，再访问，就是如上公式了

有的系统支持快表和慢表同时查找，如果是这样，平均耗时是(1+100)*0.9+(100+100)*0.1=110.9us

若未采用快表机制，则访问一个逻辑地址需要100+100=200us

显然，引入快表机制后，访问一个逻辑地址的速度快多了

两级页表

单及页表存在着两个明显的问题

  1. 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框

    思考：我们是如何解决进程在内存中必须连续存储的问题的？

    将进程地址空间分页，并为其建立一张页表，记录各页面的存放位置

    同样的思路也可用于解决“页表必须连续存放”的问题，把必须连续存放的页表再分页

    思路：可将长长的页表进行分组，使每个内存块刚好可以放入一个分组(比如上个例子中，页面大小4KB，每个页表项4B，每个页面可存放1K个页表项，因此每1K个连续的页表项为一组，每组刚好占一个内存块，再将各组离散地放到各个内存块)

    另外，要为离散分配的页表再建立一张页表，称为页目录表，或称外层页表，或称顶层页表

  2. 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面

    • 可以在需要访问页面时才把页面调入内存(虚拟存储技术)。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存；若想访问的页面不在内存中，则产生缺页中断(内中断)，然后将目标页面从外存调入内存

基本分段存储管理

与“分页”最大的区别就是---离散分配时所分配地址空间的基本单位不同

分段

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名(在低级语言中，程序员使用段名来编程)，每段从0开始编址

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

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

段号的位数决定了每个进程最多可以分几个段

段内地址位数决定了每个段的最大长度是多少

段表

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

  1. 每个段对应一个段表项，其中记录了该段在内存中的起始位置(又称“基址”)和段的长度
  2. 各个段表项的长度是相同的。例如：某系统按字节寻址，采用分段存储管理，逻辑地址为(段号16位，段内地址16位)，因此用16位即可表示最大段长。物理内存大小为4GB(可用32位表示整个物理内存地址空间)。因此，可以让每个段表项占16+32=48位，即6B。由于段表项长度相同，因此段号可以是隐含的，不占存储空间。若段表存放的起始地址为M，则K号段对应的段表项存放的地址为M+K*6

地址变换

image-20250822103943491

分段、页对比

  • 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的
  • 段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名
  • 页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序
  • 分页的用户进程地址空间是一维的，程序员只需要给出一个记忆符即可表示一个地址
  • 分段的用户进程地址空间是二维的，程序员在标识一个地址，既要给出段名，也要给出段内地址

分段比分页更容易实现信息的共享和保护

不能被修改的代码称为纯代码或可重入代码(不属于临界资源)，这样的代码是可以共享的。可修改的代码是不能共享的(比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致)

段页式管理方式

分段+分页---段页式管理方式

分页管理

  • 优点：内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片
  • 缺点：不方便按照逻辑模块实现信息的共享和保护

分段管理

  • 很方便按照逻辑模块实现信息的共享和保护
  • 如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片**(分段管理中产生的外部碎片也可以用“紧凑”来解决，只是需要付出较大的时间代价)**

段页式系统的逻辑地址由段号、页号、页内地址(页内偏移量)组成。

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

$$ 在上述例子中，若系统是按字节寻址的，则\ 段号占16位，因此在该系统中，每个进程最多有2^{16}=64K个段\ 页号占4位，因此每个段最多有2^{4}=16页\ 页内偏移量占12位，因此每个页面|每个内存块大小为2^{12}=4096=4KB $$

“分段”对用户是可见的，程序员编程时需要显式地给出段号、段内地址。而将各段“分页”对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。

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

每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号(页表起始地址)组成。每个段表项长度相等，段号是隐含的。

每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的

虚拟内存

传统存储管理方式的特征、缺点

一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：①作业很大时，不能全部装入内存，导致大作业无法运行；②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降

驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源

定义和特征

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

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

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

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

虚拟内存有以下三个主要特征：

  1. 多次性：无需在作业运行时一次性全部装入内存，而是运行被分成多次调入内存
  2. 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出
  3. 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量

请求分页管理

请求分页存储管理与基本分页存储管理的主要区别：

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存(操作系统要提供请求调页功能，将缺失页面从外存调入内存)，然后继续执行程序

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出外存(操作系统要提供页面置换的功能，将暂时用不到的页面换出外存)

页表机制

与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存；如果还没调入，那么也需要知道该页面在外存中存放的位置

当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息

页表如图所示

image-20250823164546814

缺页中断机构

假设此时要访问逻辑地址=(页号，页内偏移量)=(0,1024)

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断

此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项

如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断

一条指令在执行期间，可能产生多次缺页中断。(如copy A to B，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断)

页面置换算法

缺页次数 = 在访问页面时，如果该页面不在内存块中（即没有命中），则需要从外存调入，计为一次缺页。

最佳置换算法

最佳置换算法(OPT，Optimal)：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率

注意：缺页时未必发生页面置换。若还有可用的空闲内存块，就不用进行页面置换

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法预判页面访问序列，因此，最佳置换算法是无法实现的

先进先出置换算法

先进先出置换算法(FIFO)：每次选择淘汰的页面是最早进入内存的页面

实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可

队列的最大长度取决于系统为进程分配了多少个内存块

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

只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适合，因为先进入的页面也有可能最经常被访问，因此，算法性能差

最近最久未使用置换算法

最近最久未使用置换算法(LRU，least recently used)：每次淘汰的页面是最近最久未使用的页面

实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t

当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面

该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大

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

时钟置换算法

简单型

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法（NRU，Not Recently Used)

简单的CLOCK算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某也被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。

如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

改进型

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回内存

因此，除了考虑一个页面最近有没有被访问之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型时钟置换算法的思想。

为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1,1）表示一个页面近期被访问过，且被修改过

算法规则：将所有可能被置换的页面排成一个循环队列

第一轮：从当前位置开始扫描到第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位

第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧设为0

第三轮：若第二轮扫描识别，则重新扫描，查找第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位

第四轮：若第三轮扫描识别，则重新扫描，查找第一个（0,1）的帧用于替换

由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描

第一优先级：最近没访问，且没修过的页面

第二优先级：最近没访问，但修改过的页面

第三优先级：最近访问过，但没修过的页面

第四优先级：最近访问过，且修改过的页面

页面分配策略

页面分配、置换策略

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

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；

驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小

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

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。

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

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

全局置换意味着一个进程拥有的物理块数必然会改变，因此固定分配不会存在全局置换

固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变、若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以格局进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)

可变分配全局置换：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加

可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块

可变分配全局置换：只要缺页就给分配新物理块

可变分配局部置换：要根据发生缺页的频率来动态地增加或减少进程的物理块

何时调入页面

  1. 预调页策略：根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过。则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分
  2. 请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大

抖动(颠簸)现象

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

为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率

为了研究应该为每个进程分配多少个物理块，Denning提出了进程“工作集”的概念

工作集：指在某段时间间隔里，进程实际访问页面的集合

工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。如：窗口尺寸为5，经过一段时间的检测发现某进程的工作集最大为3，那么说明该进程由很好局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要

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

拓展：基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此，可以根据进程近期访问的页面集合(工作集)来设计一种页面置换算法---选择一个不在工作集中的页面进行淘汰

内存映射文件

内存映射文件---操作系统向上层程序员提供的功能(系统调用)

  • 方便程序员访问文件数据
  • 方便多个进程共享同一个文件

文件

概念

一个文件有哪些属性？

  • 文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件。同一目录下不允许有重名文件。
  • 标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称
  • 类型：指明文件的类型
  • 位置：指明文件存放的路径(让用户使用)、在外存中的地址(操作系统使用，对用户不可见)
  • 大小：指明文件大小
  • 创建时间、上次修改时间
  • 文件所有者信息
  • 保护信息：对文件进行保护的访问控制信息

无结构文件(如文本文件)---由一些二进制或字符流组成，又称“流式文件”

有结构文件(如数据库表)---由一组相似的记录组成，又称“记录式文件”

记录是一组相关数据项的集合

数据项是文件系统中最基本的数据单位

逻辑结构

有结构文件

按文件是否有结构分类，可以分为无结构文件、有结构文件两种

无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如：Windows操作系统中的.txt文件

有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录由若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字。根据各条记录的长度(占用的存储空间)是否相等，又可分为定长记录和可变长记录两种

顺序文件

顺序文件：文件中的记录一个接一个地顺序排列(逻辑上)，记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储

顺序存储---逻辑上相邻的记录物理上也相邻(类似于顺序表)

  • 可变长记录
    • 无法实现随机存取。每次只能从第一个记录开始依次往后查找
  • 定长记录
    • 可实现随机存储。记录长度为L，则第i个记录存放的相对位置是i*L
    • 若采用串结构，无法快速找到某关键字对应的记录
    • 若采用顺序结构，可以快速找到某关键字对应的记录

链式存储---逻辑上相邻的记录物理上不一定相邻(类似于链表)

  • 无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找

结论：定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取；若能再保证记录的顺序结构，则可实现快速检索(即根据关键字快速找到对应记录)

索引文件

对于可变长记录文件，要找到第i个记录，必须先顺序的查找前i-1个记录，但是很多应用场景中又必须使用可变长记录。如何解决这个问题？

建立一张索引表以加快文件检索速度。每条记录对应一个索引项

文件中的这些记录在物理上可以离散地存放

索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。

可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找

每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合

另外，**可以用不同的数据项建立多个索引表。**如：学生信息表中，用关键字“学号”或“姓名”建立一张索引表，当然索引是唯一的，需要考虑其他问题

文件目录

文件控制块

目录文件中的一条记录就是一个“文件控制块(FCB)”

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

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

最重要、最基本的还是文件名、文件存放的物理地址

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

单级目录结构

早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项

单级目录实现了“按名存取”，但是不允许文件重名

在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许创建文件，并将新文件对应的目录项插入目录表。

显然，单级目录结构不适用于多用户操作系统

两级目录结构

早期的多用户操作系统，采用两级目录结构。分为主文件目录(MFB，Master File Directory)和用户文件目录(UFD，User File Directory)

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

允许不同用户的文件重名。文件名虽然相同，但是对应的其实是不同的文件

两级目录结构允许不同用户的文件重名，也可以在目录上实现访问限制(检查此时登录的用户名是否匹配)。但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类

多级目录结构

又称树形目录结构

用户(或用户进程)要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径

如果说，此时打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相当路径”

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”

无环图目录结构

在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享

可以用不同的文件名指向同一个文件，甚至指向同一个目录(共享同一目录下的所有内容)

需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点

注意：共享文件不同于复杂文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化

索引结点

如果内容都放在一个表中，FCB的大小会过大，导致盘块增多，盘块增多的话，读写速度也会变慢

如果我们能减少FCB，就能让检索速度变快，所以我们可以仅保留文件名用于检索

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件

存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”

相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等

物理结构

文件块&磁盘块

在内存管理中，进程的逻辑地址空间被分为一个一个页面

同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”

于是文件的逻辑地址也可以表示为(逻辑块号，块内地址)的形式

操作系统为文件分配存储空间是以块为单位的

分配方式

连续分配

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

用户通过逻辑地址来操作自己的文件，操作系统如何实现从逻辑地址到物理地址的映射？

(逻辑块号，块内地址)->(物理块号，块内地址)。只需转变块号就行，块内地址保持不变

文件目录中记录存放的起始块号和长度(总共占用几个块)

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项(FCB)

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

当然，还需要检查用户提供的逻辑块号是否合法(逻辑块号>=长度就不合法)

因为可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问(即随机访问)

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长

结论：连续分配的文件在顺序读/写时速度最快

缺点：

当文件要拓展时，若没有连续的空闲磁盘块，就需要将该文件全部迁移到存在空闲磁盘块的区域

image-20250829164747474

而又因为必须采用连续分配，需要占用一组连续的块，存储空间利用率会变低，会产生难以利用的小的磁盘碎片，可以用紧凑来处理碎片，但是需要耗费很大的时间代价

优点：支持顺序访问和直接访问(即随机访问)；连续分配的文件在顺序访问时速度最快

缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片

链接分配

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

隐式链接

目录中记录了文件存放的起始块号和结束块号。当然，也可以增进一个字段来表示文件的长度

除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的

那么，如何实现文件的逻辑块号到物理块号的转变？

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB)

从目录项中找到起始块号(即0号块)，将0号逻辑块读入内容，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置…以此类推

因此，读入i号逻辑块，总共需要i+1次磁盘I/O

结论：采用**链式分配(隐式链接)**方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间

是否方便拓展文件？

若此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块尾，并修改文件的FCB

结论：采用隐式链接的链接分配方式，很方便文件拓展

另外，所有空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高

显式链接

把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表(FAT，File Allocation Table)

目录中只需记录文件的起始块号

如图所示

image-20250829214756391

如何实现文件的逻辑块号到物理块号的转变？

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB)

从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT，从后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作

结论：采用链式分配(显式存储)方式的文件，支持顺序访问，也支持随机访问(想访问i号逻辑块时，并不需要依次访问之前的0~i-1号逻辑块)，由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多

显然，显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展

索引分配

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

如何实现文件的逻辑块号到物理块号的转换？

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项(FCB)

从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可知i号逻辑块在外存中的存放位置

可见，索引分配方式可以支持随机访问。文件拓展也很容易实现(只需给文件分配一个空闲块，并增加一个索引表项即可)

  1. 链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放
  2. 多层索引：建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块[若采用多层索引，则各层索引表大小不能超过一个磁盘块]
  3. 混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)

存储空间管理

划分和初始化

  • 存储空间的划分：将物理磁盘划分为一个个文件卷(逻辑卷、逻辑盘)
    • 有的系统支持超大型文件，可支持由多个物理磁盘组成一个文件卷
  • 存储空间的初始化：将各个文件卷划分为目录区、文件区
    • 目录区主要存放文件目录信息(FCB)、用于磁盘存储空间管理的信息
    • 文件区用于存放文件数据

空闲表法

image-20250830102253835

空闲链表法

空闲链表法又分为空闲盘块链和空闲盘区链

  • 空闲盘块链：以盘块为单位组成一条空闲链
  • 空闲盘区链：以盘区为单位组成一条空闲链

如图所示

image-20250830102656100

空闲盘块链

操作系统保存着链头、链尾指针。

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

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

适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作

空闲盘区链

操作系统保存着链头、链尾指针。

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

如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的应该空闲盘区挂到链尾

离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高

位示图法

如图所示，基于二进制位表示存储空间

image-20250830110202908

成组链接法

UNIX采用的策略，适合大型文件系统。理解即可，不方便用文字描述的知识点很难作为考题

无法描述，推荐看视频

https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=66

基本操作

创建文件

进行Create系统调用时，需要提供的几个主要参数：

  1. 所需的外存空间大小(如：一个盘块，即1KB)
  2. 文件存放路径
  3. 文件名

操作系统在处理Create系统调用时，主要做了两件事：

  1. 在外存中找到文件所需的空间
  2. 根据文件存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息

删除文件

进行Delete系统调用时，需要提供的几个主要参数：

  1. 文件存放路径
  2. 文件名

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

  1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项
  2. 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块
  3. 从目标表中删除文件对应的目录项

打开文件

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

  1. 文件存放路径
  2. 文件名
  3. 要对文件的操作类型(如：r只读;rw读写等)

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

  1. 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，并检查该用户是否有指定的操作权限
  2. 将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件

关闭文件

进程在使用完文件后，要“关闭文件”

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

  1. 将进程的打开文件表相应表项删除
  2. 回收分配给该文件的内存空间等资源
  3. 系统打开文件表的打开计数器count减1，若count=0，则删除对应表项

读文件

进程使用read系统调用完成读操作。需要指明是哪个文件(在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可)，还需要指明要读入多少数据、指明读入的数据要放在内存中的什么位置

操作系统在处理read系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中

写文件

进程使用write系统调用完成写操作，需要指明是哪个文件(在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可)，还需要指明要写出多少数据、写回外存的数据放在内存中的什么位置

操作系统在处理write系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存

文件共享

基于索引结点的共享方式(硬链接)

知识回顾：索引结点，是一种文件目录瘦身策略。由于检索文件时只需用到文件名，因此可以将除了文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针

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

若count=2，说明此时有两个用户目录项链接到该索引结点上，或者说有两个用户在共享此文件。若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1

若count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空

若count=0时系统负责删除文件

基于符号链的共享方式(软链接)

  • 在一个Link型的文件中记录共享文件的存放路径(Windows快捷方式)
  • 操作系统根据路径一层层查找目录，最终找到共享文件
  • 即使软链接指向的共享文件已被删除，Link型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败(找不到对应目录项)
  • 由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问

文件保护

口令保护

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

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

  • 优点：保存口令的空间开销不多，验证口令的时间开销也很小
  • 缺点：正确的“口令”存放在系统内部，不够安全

加密保护

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

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

访问控制

在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List,ACL），该表中记录了各个用户可以对该文件执行哪些操作

精简的访问列表：以“组”为单位，标记各“组”用户可以对文件执行哪些操作。

如：分为系统管理员、文件主、文件主的伙伴、其他用户 几个分组

当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限

文件系统的层次结构

如图

image-20250830203054188

文件系统的全局结构(布局)

物理格式化，即低级格式化---划分扇区，检测坏扇区，并用备用扇区替换坏扇区

具体可看这个视频，比较抽象：https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=71

虚拟文件系统

https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=72

I/O设备

基本概念和分类

I/O就是输入/输出(Input/Output)

I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件

  • 按使用特性分类
    • 人机交互类外部设备(eg:键盘、鼠标)
    • 存储设备(eg:移动硬盘、光盘)
    • 网络通信设备(eg:调制解调器)
  • 按传输速率分类
    • 低速设备
    • 中速设备
    • 高速设备
  • 按信息交换的单位分类
    • 块设备(传输快，可寻址)(eg:磁盘)
    • 字符设备(传输慢，不可寻址，常采用中断驱动方式)(eg:键盘、鼠标)

控制器

概念

I/O设备的机械部件主要用来执行具体I/O操作

如我们看得见摸得着的鼠标/键盘的按钮；显示器的LED屏；移动硬盘的磁臂、磁盘盘面

I/O设备的电子部件通常是一块插入主板扩充槽的印刷电路板

CPU无法直接控制I/O设备的机械部件，因此I/O设备还要有一个电子部件作为CPU和I/O设备机械部件之间的“中介”，用于实现CPU对设备的控制

这个电子部件就是I/O控制器，又称设备控制器。CPU可控制I/O控制器，又由I/O控制器来控制设备的机械部件

功能

  • 接受和识别CPU发出的命令
    • 如CPU发来的read/write命令，I/O控制器中会有相应的控制寄存器来存放命令和参数
  • 向CPU报告设备的状态
    • I/O控制器中会有相应的状态寄存器，用于记录I/O设备的当前状态。如：1表示空闲，0表示忙碌
  • 数据交换
    • I/O控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据
  • 地址识别
    • 类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的“地址”。I/O控制器通过CPU提供的“地址”来判断CPU要读/写的是哪个寄存器

组成

如图

image-20250831093610969

值得注意的小细节:

  1. 一个I/O控制器可能会对应多个设备
  2. 数据寄存器、控制寄存器、状态寄存器可能有多个(如：每个状态/控制寄存器对应一个具体的设备)，且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O；另一些计算机则采用I/O专用地址，即寄存器独立编址

内存映像v.s.寄存器独立编址

image-20250831094217119

控制方式

程序直接控制方式

具体流程如图所示

image-20250831103841841
  • CPU干预的频率
    • 很频繁，I/O操作开始之前、完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断地轮询检查
  • 数据传送的单位
    • 每次读/写一个字
  • 数据的流向
    • 读操作(数据输入)：I/O设备->CPU(CPU的寄存器)->内存
    • 写操作(数据输出)：内存->CPU->I/O设备
    • 每个字的读/写都需要CPU的帮助
  • 优缺点
    • 优点：实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可(因此才称为“程序直接控制方式”)
    • 缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于“忙等”状态，CPU利用率低

中断驱动方式

具体流程如图所示

image-20250831144839895

引入中断机制。由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。当I/O完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器，再写入主存。接着，CPU恢复等待I/O的进程(或其他进程)的运行环境，然后继续执行

注意：

  1. CPU会在每个指令周期的末尾检查中断
  2. 中断处理过程中需要保存、恢复进程的运行环境，这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能
  • CPU干预的频率
    • 每次I/O操作开始之前、完成之后需要CPU介入
    • 等待I/O完成的过程中CPU可以切换到别的进程执行
  • 数据传送的单位
    • 每次读/写一个字
  • 数据的流向
    • 读操作(数据输入)：I/O设备->CPU->内存
    • 写操作(数据输出)：内存->CPU->I/O设备
  • 主要缺点和主要优点
    • 优点：与“程序直接控制方式”相比，在“中断驱动方式”中，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率明显得到提升
    • 缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间

DMA方式

与“中断驱动方式”相比，DMA方式(Direct Memory Access，直接存储器存取。主要用于块设备的I/O控制)

有这样几个改进

  1. 数据的传送单位是“块”。不再是一个字、一个字的传送
  2. 数据的流向是从设备直接放入内存，或者从内存直接到设备。不再需要CPU作为“快递小哥”
  3. 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预

DMA操作步骤

DMA结构

  • CPU干预的频率
    • 仅在传送一个或多个数据块的开始和结束时，才需要CPU干预
  • 数据传送的单位
    • 每次读/写一个或多个块(注意：每次读写的只能是连续的多个块，且这些块读入内存后在内存中也必须是连续的)
  • 数据的流向(不再需要经过CPU)
    • 读操作(数据输入)：I/O设备->内存
    • 写操作(数据输出)：内存->I/O设备
  • 优缺点
    • 优点：数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升
    • 缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。如果要读/写多个离散的数据块，或者要将数据分别写入到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成

通道控制方式

完成一次I/O的步骤

  • CPU干预的频率
    • 极低，通道会根据CPU的指示执行相应的通道程序，只有完成一组数据块的读/写才需要发出中断信号，请求CPU干预
  • 数据传送的单位
    • 每次读/写一组数据块
  • 数据的流向(在通道的控制下进行)
    • 读操作(数据输入)：I/O设备->内存
    • 写操作(数据输出)：内存->I/O设备
  • 优缺点
    • 优点：CPU、通道、I/O设备可并行工作，资源利用率很高
    • 缺点：实现复杂，需要专门的通道硬件支持

软件层次结构

用户层软件

用户层软件

设备独立性软件

设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现

主要实现的功能：

  1. 向上层提供统一的调用接口(如read/write 系统调用)
  2. 设备的保护
    • 原理类似与文件保护。设备被看作是一种特殊的文件，不同用户对各个文件的访问权限是不一样的，同理，对设备的访问权限也不一样
  3. 差错处理
    • 设备独立性软件需要对一些设备的错误进行处理
  4. 设备的分配与回收
  5. 数据缓冲区管理
    • 可以通过缓冲技术屏蔽设备之间数据交换单位大小和传输速度的差异
  6. 建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序
    • 用户或用户层软件发出I/O操作相关系统调用的系统调用时，需要指明此次要操作的I/O设备的逻辑设备名(eg:去学校打印店打印时,需要选择打印机1/打印机2/打印机3，其实这些都是逻辑设备名)
    • 设备独立性软件需要通过“逻辑设备表(LUT,Logical Unit Table)”来确定逻辑设备对应的物理设备，并找到该设备对应的设备驱动程序
    • 操作系统可以采用两种方式管理逻辑设备表(LUT)：
      • 第一种方式，整个系统只设置一张LUT，这就意味着所有用户不能使用相同的逻辑设备名，因此这种方式只适用于单用户操作系统
      • 第二种方式，为每个用户设置一张LUT，各个用户使用的逻辑设备名就可以重复，适用于多用户操作系统。系统会在用户登录时为其创建一个用户管理进程，而LUT就存放在用户管理进程的PCB中

设备驱动程序

主要负责对硬件设备的具体控制,将上层发出的一系列命令(如read/write) 转化成特定设备“能听得懂”的一系列操作。包括设置设备寄存器；检查设备状态等

不同的I/O设备有不同的硬件特性，具体细节只有设备的厂家才知道。因此厂家需要根据设备的硬件特性设计并提供相应的驱动程序

注：驱动程序一般会以一个独立进程的方式存在

中断处理程序

当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。

输入输出应用程序接口和驱动程序接口

输入输出程序接口

极其抽象：https://www.bilibili.com/video/BV1YE411D7nH/?p=77&spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=b39debcbe1026bb04f6c19f233bab974

阻塞I/O：应用程序发出I/O系统调用，进程需转为阻塞态等待

非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待

假脱机技术(SPOOLing技术)

批处理阶段引入了脱机输入/输出技术(用磁带完成)：

通常是将内容放到纸带机上后，通过一台外围控制机，慢速输入设备的数据先被输入到更快速的磁带上。之后主机可以从快速的磁带上读入数据，从而缓解了速度矛盾

引入脱机技术后，缓解了CPU与慢速I/O设备的速度矛盾。另一方面，即使CPU在忙碌，也可以提前将数据输入到磁带：即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带

Tips：为什么称为“脱机”---脱离主机的控制进行的输入/输出操作

“假脱机技术”，又称“SPOOLing技术”是用软件的方式模拟脱机技术。SPOOLing系统的组成如下：

通常是通过输入进程和输出进程来将数据进行输入和输出

image-20250901204155514

设备的分配和回收

设备的固有属性可分为三种：独占设备、共享设备、虚拟设备

  • 独占设备：一个时段只能分配给一个进程(如打印机)
  • 共享设备：可同时分配给多个进程使用(如磁盘)，各进程往往是宏观上同时共享使用设备，而微观上交替使用
  • 虚拟设备：采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用(如采用SPOOLing技术实现的共享打印机)

从进程运行的安全性上考虑，设备分配有两种方式：

安全分配方式：为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒(eg：考虑进程请求打印机打印输出的例子)

一个时段内每个进程只能使用一个设备

  • 优点：破坏了“请求和保持”的条件，不会死锁
  • 缺点：对于一个进程来说，CPU和I/O设备只能串行工作

不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞

一个进程可以同时使用多个设备

  • 优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进
  • 缺点：有可能发生死锁(死锁避免、死锁的检测和解除)

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

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

设备控制表(DCT)：系统为每个设备配置一张DCT，用于记录设备情况

设备控制表

控制器控制表(COCT)：每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理

控制器控制表

通道控制表(CHCT)：每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理

image-20250902101227754

系统设备表(SDT)：记录了系统中全部设备的情况，每个设备对应一个表目

系统设备表

设备分配的步骤

  1. 根据进程请求的物理设备名查找SDT(注：物理设备名是进程请求分配设备时提供的参数)
  2. 根据SDT找到DCT。若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程
  3. 根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程
  4. 根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程

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

缺点：

  1. 用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程
  2. 若换了一个物理设备，则程序无法运行
  3. 若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名

改进后前两个设备分配步骤如下：

  1. 根据进程请求的逻辑设备名查找SDT(注：用户编程时提供的逻辑设备名其实就是设备类型)
  2. 查找SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表(LUT)中新增一个表项

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

某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户进程指定的设备类型(逻辑设备名)查找系统设备表，找到一个空闲设备分配给进程，并在LUT中增加相应表项

如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址

逻辑设备表的设置问题：

整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统

每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统

缓冲区管理

概述

太抽象了：https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=81

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区

使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合(如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本)

一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区

缓冲区的作用

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

单缓存

假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区(若题目中没有特别说明，一个缓冲区的大小就是一个块)

注意：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出

单缓存策略用时过程

循环缓冲区

将多个大小相等的缓冲区链接成一个循环队列

注：以下图示中，橙色表示已充满数据的缓冲区，绿色表示空缓冲区

循环缓冲区

缓冲池

缓冲池由系统中共用的缓冲区组成。这些缓冲区按使用状况可以分为：空缓冲队列、装满输入数据的缓冲队列(输入队列)、装满输出数据的缓冲队列(输出队列)

另外，根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：用于收容输入数据的工作缓冲区(hin)、用于提取输入数据的工作缓冲区(sin)、用于收容输出数据的工作缓冲区(hout)、用于提取输出数据的工作缓冲区(sout)

比较复杂，建议观看概述中的视频链接

磁盘的结构

不抽象，比较难写笔记：https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=82

磁盘、磁道、扇区

磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据

磁盘的盘面被划分为一个个磁道。

一个磁道又被划分成一个个扇区，每个扇区就是一个“磁盘块”。各个扇区存放的数据量相同(如1KB)

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

磁盘的物理地址

image-20250902155831286

磁盘的分类

image-20250902160259759

盘片可以更换的称为可还盘磁盘

盘片不可更换的称为固定盘磁盘

磁盘调度算法

读/写 磁盘操作

$$ 寻找时间(寻道时间)T_s：在读/写数据前，将磁头移动到指定磁道所花的时间 \ ①启动磁头臂是需要时间的。假设耗时为s; ②移动磁头也是需要时间的。假设磁头匀速移动，每跨域一个磁道耗时为m\总共需要跨越n条磁道。\ 则：寻道时间T_s=s+mn \ 延迟时间T_R：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。\ 设磁盘转速为r(单位：转/秒，或转/分)，则平均所需的延迟时间T_R=(1/2)(1/r)=1/(2r)\ 传输时间T：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节 \ 数为N。则：传输时间T_t=(1/r)*(b/N)=b/(rN) \ 总的平均存取时间T_a=T_s+1/2r+b/(rN) $$

算法比较多，都是跟之前类似的，不再赘述：https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=83

减少磁盘延迟时间

https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=84

磁盘的管理

https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=85

固态硬盘SSD

https://www.bilibili.com/video/BV1YE411D7nH?spm_id_from=333.788.player.switch&vd_source=b39debcbe1026bb04f6c19f233bab974&p=86

#408