大部分内容基于中国大学MOOC的2021考研数据结构课程所做的笔记，后续又根据2023年考研的大纲增加了一些内容，主要有操作系统引导、虚拟机、多级队列调度算法、互斥锁、调度器和闲逛进程、内存映射文件、文件系统的全局结构、虚拟文件系统、固态硬盘SSD、输入输出应用程序接口 、驱动程序接口等等。

感谢我的室友HXN，他帮我写了一部分第五章的内容。

课程内容和西电平时讲课的内容大致重合，西电可能每章会多讲一点UNIX系统的实例，可以听完这课再快速过一遍老师的课件防止漏掉什么内容。

这门课讲的其实不算特别硬核，没怎么涉及具体的代码。不过我其实感觉操作系统是个大无底洞，能学到多深基本取决于愿意花多少时间和精力。如果有闲心，推荐看下南大蒋炎岩老师的《操作系统：设计与实现》和哈工大李治军老师的《操作系统》，讲的更深入，当然难度也相应的大的多。

 

其他各章节的链接如下：

操作系统笔记（王道考研） 第一章：计算机系统概述

操作系统笔记（王道考研） 第二章：进程管理（1）

操作系统笔记（王道考研） 第二章：进程管理（2）

操作系统笔记（王道考研） 第三章：内存管理

操作系统笔记（王道考研） 第四章：文件管理

操作系统笔记（王道考研） 第五章：输入输出（I/O）管理

其他各科笔记汇总

计算机系统概述

操作系统基本概念，功能

操作系统的概念，定义

在任务管理器界面，我们就可以看到现在系统当中运行的进程有哪些。所谓进程就其实是正在运行的软件和程序，从这个地方可以看到操作系统肯定是在对软件进行管理。在右边这个界面可以看到操作系统对CPU，内存等等这一系列硬件资源的使用情况也是在监控的，操作系统肯定是在对硬件进行管理的。因此操作系统作为软件和硬件之间的层次，是系统资源的管理者，既管理软件资源也管理硬件资源。

接下来会对上图列出的操作系统3个功能进行更进一步的细分和分析，来更形象地体会操作系统的作用

操作系统的功能和目标——作为系统资源的管理者

首先要看的是操作系统作为软件和硬件中间的层次，它是系统资源的管理者。下图以QQ视频聊天为例

各步体现的操作系统提供的功能如下，具体说明此处略过不计

Step1：文件管理

Step2：存储器管理（也叫做主存管理，内存管理）

Step3：处理机管理

Step4：设备管理

以上功能都会在后面几章做具体讲解，操作系统在后期要重点学习的就是它作为系统资源的管理者要如何设计和实现这些功能。

操作系统的功能和目标——向上层提供方便易用的服务

早期的一些操作系统并没有图形化界面，都是让用户通过命令接口的方式，也就是命令行的方式和操作系统进行交互。命令接口又可以分为联系命令接口和脱机命令接口，都是操作系统对上层提供的两种接口

.bat文件里有一堆命令，但本质上和time命令没有任何区别，我们只不过是把这一系列的命令罗列在了清单里，然后当我们执行.bat文件时操作系统其实就是根据这个文件当中的命令一条一条地往后执行。

 

刚才我们提到的三种接口都是可以让普通用户直接使用的，操作系统还有一种对外提供的接口叫做程序接口，这种接口是给程序员使用的。

普通程序员使用了C语言提供的库函数printf。这个库函数在底层实现的时候其实是使用了操作系统提供的系统调用的功能，操作系统在收到系统调用的请求之后，它才会替我们去操作硬件显示器，并且在显示器上显示出“Hello world”。

很多操作系统中都提供了上百种的系统调用，由这些系统调用组成了所谓的程序接口。

 

总结一下

操作系统的功能和目标——作为最接近硬件的层次

 

操作系统的四个特征

操作系统的特征——并发

操作系统的特征——共享

有的时候这个同时共享也有可能是微观上也确实在同时地共享资源，比如边打游戏边听歌，扬声器设备一边在播放游戏的音效一边在播放音乐。在这种情况下，扬声器的声音输出设备是真的在微观上也是同时正在被音乐播放器和游戏这两个进程同时使用的

操作系统的特征——并发和共享的关系

总之并发性和共享性互为存在条件

操作系统的特征——虚拟

操作系统的特征——异步

 

操作系统的发展与分类

绿框内为重点内容

手工操作阶段

由有无小孔代表0和1

批处理阶段——单道批处理系统

批处理阶段——多道批处理系统

分时操作系统

实时操作系统

其他操作系统

 

操作系统的运行机制

预备知识——程序是如何运行的？

像我们平时用C语言代码写的程序都会经过编译器的编译工作把C语言代码翻译成二进制机器指令。像我们平时用C语言这种高级语言写的一条代码经过编译之后可能会对应很多机器指令。程序运行的过程其实就是CPU执行一条一条机器指令的过程。

“指令”就是处理器CPU能识别，执行的最基本命令。

注：很多人习惯把Linux，Windows，MacOS的“小黑框”中使用的命令也成为“指令”，其实这是“交互式命令接口”，注意与本节的“指令”区别开。本节中的“指令”指二进制机器指令

总之平时我们用高级语言编写的程序最后执行的时候肯定是要变成CPU能够读的懂的用二进制机器指令表现的这种形式，这就是程序运行的基本原理。

内核程序与应用程序

在操作系统这门课当中，我们要注意区分两种类型的程序，分别是内核程序和应用程序。我们普通程序员写的程序就是“应用程序”。微软、苹果有一帮人负责实现操作系统，他们写的是“内核程序”。由很多内核程序组成了“操作系统内核”，或简称“内核(Kernel)”。内核是操作系统最重要最核心的部分，也是最接近硬件的部分。甚至可以说，一个操作系统只要有内核就够了（eg：有的同学可能接触过容器技术，比如说Docker，在Docker容器里只需要有Linux的内核就可以实现Linux的所有功能了）。操作系统的功能未必都在内核中，如图形化用户界面 GUI。

即使没有图形化的界面我们依然可以用命令行（也就是之前说的“小黑框”）的方式来使用操作系统。所以操作系统的内核当中所包含的只是操作系统当中最重要最核心的功能

特权指令与非特权指令

既然操作系统内核是系统资源的管理者，它作为管理者的角色有时可能会让CPU执行一些比较特殊的指令

内核态与用户态

虽然CPU能够分辨出特权指令和非特权指令，但是它又怎么分辨出此时正在执行的指令到底是一个“应用程序”的指令还是一个“内核程序”的指令呢？为了让CPU能够区分此时正在运行的指令是属于应用程序还是内核程序，CPU会被划分成两种状态，一种叫“内核态”，一种叫“用户态”。

接下来我们要探讨的问题是CPU要怎么实现这两种状态间的切换

内核态，用户态的切换

开机的时候需要加载我们的操作系统，然后操作系统要进行一些初始化的工作。系统初始化的工作其实就是由操作系统当中的某一些内核程序来完成的，所以在开机的过程当中需要执行内核程序，因此在这个时候，CPU肯定要处于“内核态”。

 

中断和异常

中断的作用

中断的类型

内中断的例子

例子1：试图在用户态下执行特权指令（如上节中黑客攻击的例子）

例子2：执行除法指令时发现除数为0

总之若当前执行的指令本身或者指令的一些参数是非法的，则会引发一个中断信号

例子3：有时候应用程序想请求操作系统内核的服务，此时会执行一条特殊的指令陷入指令，该指令会引发一个内部中断信号。执行“陷入指令”，意味着应用程序主动地将CPU控制权还给操作系统内核。“系统调用”就是通过陷入指令完成的

注意陷入指令并不是特权指令。因为这个程序是运行在用户态的，而在用户态下可以执行的指令不可能是特权指令

外中断的例子

例子1：时钟中断，由时钟部件发来的中断信号

例子2：I/O中断，由输入/输出设备发来的中断信号

时钟部件每隔一个时间片（如50ms）会给CPU发送一个时钟中断信号。通过时钟中断信号就可以实现多道程序并发运行了。当某应用程序执行了几条指令后，时钟部件发现此时已经过了50ms，它会给CPU发送一个中断信号（注意这个中断信号和当前执行的指令是没有关系的，它来自CPU的外部）。然后根据我们之前学习的知识，CPU检测到该信号后会先暂停此时正在运行的应用程序，然后转而执行一个相应的内核程序来处理这个中断信号。所以接下来CPU会对时钟中断信号进行处理，并且转为内核态。在内核态下CPU开始执行内核程序来处理刚才收到的中断信号，这个内核程序执行的过程当中发现该应用程序已经用了50ms的时间，应该让下一个应用程序上CPU运行。于是接下来这个内核程序会把CPU的使用权给下一个应用程序，接下来又会切换回用户态，然后下一个程序上CPU运行。之后的过程都是类似的，通过这个例子可以看出应用程序是如何在中断机制的支持下一直不断地切换来实现并发运行的，以及中断在现代计算机中到底有多大的作用。

除了时钟发出的中断信号之外，有时候还会有来自I/O设备的中断信号。比如说某个应用程序可能会请求打印机的打印服务，打印机在打印输出完成之后会向CPU发出中断信号用来通知CPU任务完成。接下来CPU会用中断信号相对应的内核程序来对中断信号进行处理。

每一条指令执行结束时，CPU都会例行检查是否有外中断信号

中断的分类

中断机制的基本原理

具体硬件上怎么实现见计算机组成原理

 

系统调用

什么是系统调用，有何作用？

系统调用与库函数的区别

其实我们在写程序的时候可以用汇编语言的方式来直接请求系统调用服务的，但是现在的编程更多地是使用高级语言来编程，所以我们一般会直接使用高级语言的库函数，但是这些高级语言的库函数在底层其实也会用到操作系统提供的系统调用功能来请求操作系统的服务。所以系统调用应该是比高级语言的库函数更为底层的接口。

我们的裸机之上是操作系统，操作系统向上层提供的接口是系统调用，使上面的库函数和应用程序能够通过系统调用的方式来请求操作系统的内核的服务。然后在操作系统之上各种各样的高级编程语言会用库函数的方式来封装这些系统调用，然后向更上层的应用程序的程序员来暴露一些更好用的编程接口。

不过也并不是所有的库函数都会使用系统调用

小例子：为什么系统调用是必须的？

通过系统调用来实现并发进程对共享资源的互斥访问

什么功能要用到系统调用？

系统调用的过程

假设一个应用程序想要进行系统调用，它在背后需要做什么事情呢？

现有一个应用程序运行在用户态，然后这个应用程序的各个指令会被CPU依次执行。当它想要发出系统调用的时候，他需要用传参数的指令给CPU的寄存器当中传递一些必要的参数，比如说在某一个寄存器中放入了参数1，这个参数1是指明了此次要进行哪种类型的系统调用，比如说像Linux里的“folk”系统调用。传递参数的指令可能要有多条，主要看我们的系统调用需要传递几个参数。操作系统会根据应用程序提供的这些参数来判断它想要的到底是哪种服务，当这些参数都放入了寄存器之后，应用程序就会执行一条特殊的指令叫陷入指令，该指令会引发一个内中断，CPU在检测到这个内部中断信号之后，它发现这个内部中断信号是由陷入指令引起的，于是这个CPU接下来就会暂停运行这个应用程序，转而去执行处理陷入指令的那个处理程序，这个程序就是系统调用入口程序。显然接下来要执行的程序肯定是属于内核程序，因此它需要在内核态下运行，我们也可以说这个程序也是某一种中断处理程序，只不过它处理的是由陷入指令引发的那个内中断。接下来系统调用入口程序会检查寄存器里的参数，通过第一个参数它会知道此时这个应用程序想要的是这种类型的系统调用服务，于是接下来入口程序就会调用与特定的系统调用类型所对应的处理程序，然后让这个程序上CPU运行。那这个系统调用处理程序在执行的时候就可以根据应用程序传递的其他参数来看一下它所需要的具体是哪些服务。当系统调用被处理完之后CPU又会转回用户态，然后接着执行之前的那个应用程序。

执行了陷入指令之后就意味着这个应用程序把CPU的控制权主动交还给了操作系统的内核，用这样的方式来请求操作系统的服务，注意它并不是特权指令。

 

 

操作系统的体系结构（1）

本节学习操作系统的内核应该如何设计，只需要做简要了解即可

操作系统的内核

想要实现程序并发就必然离不开时钟管理内核功能

在执行原语的这一小段程序当中，即使有外部中断信号过来，CPU继续把原理处理完成，才去处理外部中断信号

上图提到的最底层的时钟管理，中断处理，原理这三个部分都是和硬件关联最为紧密的，所以它们必须放在内核当中。有的操作系统并不会把下面列出的几个不直接涉及硬件的管理功能放在内核当中，而只在内核当中保留与硬件接触最紧密的这些部分。

因此这就引出了两种截然不同的内核设计方法。把所有的这些功能都包含在操作系统内核当中，这种结构就叫做大内核。而如果内核当中只保留与硬件关系最紧密的这些部分，这种内核就叫做微内核。需要注意的是如果采用的是微内核的这种结构的话，那么属于内核的这些功能是需要运行在内核态的，而不属于内核的上面的这些功能就需要运行在用户态，这会对我们系统的性能造成一定的影响，下小节会用更直观的例子来体会这点。

操作系统的体系结构

假设现在有两种体系结构的系统。第一个系统采用的是大内核的体系结构，由于进程管理，存储管理这些功能都是被划分在内核当中的，所以这些功能的处理都需要运行在内核态，只有应用程序是运行在用户态的。而对于采用微内核结构的操作系统来说，只有和硬件联系最紧密的这些功能被划分在了内核当中，只有这些功能是需要在内核态下才可以执行的，而其他的这些功能模块在用户态下就可以运行。

假设现在一个应用程序想要请求操作系统的服务，并且这个服务的背后需要同时涉及到进程管理、存储管理、设备管理这几个功能。如果采用的是大内核的体系结构的话，那么应用程序向操作系统提出服务的请求，这个时候CPU会从用户态切换为内核态，然后开始运行这一系列的内核程序。应用程序的这个请求只需要两次变态就可以了。

而如果采用的是微内核的体系结构的话，应用程序向操作系统提出服务的请求，接下来操作系统的这几个模块都需要为操作系统服务。而进程管理这个模块在处理应用程序的请求的时候同样也需要得到内核的支持，所以这个模块对内核的访问就涉及到CPU从用户态转到内核态，服务完成之后又会从内核态转回用户态。然后同样地存储管理和设备管理这两个模块在完成相应的工作的时候也需要得到内核的支持，因此每一个模块都需要请求内核的服务，每一次请求内核的服务都会涉及到一个CPU状态转换的过程。整个过程处理需要六次变态。

 

 

 

后面的内容是2023年课程新加的

操作系统的体系结构（2）

操作系统结构 —— 分层结构

每一层只能调用相邻低层所提供的接口，不能跨层调用

操作系统结构 —— 模块化

内核 = 主模块 + 可加载内核模块。设备驱动程序属于可加载内核模块

操作系统结构 —— 宏内核、微内核

微内核各个模块间的调用没那么方便。如进程管理模块想要调用存储管理模块的功能只能通过消息传递的方式进行。进程管理模块向微内核发送消息，消息里面指明调用对象和参数，由微内核的进程间通信相关功能把消息传递给存储管理模块，该模块处理调用请求。如果要返回调用结果也要通过消息传递的方式

操作系统结构 —— 外核（exokernel）

应用程序可以通过系统提供的库函数调用普通内核和外核的功能

普通的操作系统用户进程想要申请一块内存空间，被分配的内存空间是经过抽象的。从用户进程的视角似乎自己拥有一整片连续的内存空间，但实际上这只是虚拟的地址空间，操作系统会把这些虚拟页面映射到实际的物理页框当中，这些物理页框在内存当中通常是离散的

除了内存空间之外，给进程分配的外存空间也是经过抽象的。从进程的视角似乎文件是连续的地址空间，但事实上文件的各个块在磁盘当中通常是离散存放的。用户进程的文件在外存当中零散地分布到哪些位置完全由操作系统决定，自己并不能控制

由于普通的操作系统给用户进程分配的都是抽象的硬件资源，一个用户进程在访问自己的用户空间时只能提供虚拟地址，而操作系统需要查页表通过多次访存才能够把虚拟地址转换成实际的物理地址。把虚拟地址映射到实际的物理地址的过程也需要时间代价，降低系统的整体效率

 

而外核可以直接给用户进程分配未经抽象的系统资源。这样的资源管理策略有时很有用，比如一个用户进程知道需要经常随机访问自身文件，就可以向外存申请分配一整片连续的磁盘块，随机访问时磁头移动的距离变少性能提升。应用程序也可以向外核申请分配一整片连续的物理内存

外核除了负责分配和回收这些未经抽象的硬件资源之外，还需要保证这些硬件资源的使用安全

在有外核的操作系统当中有的进程申请的是虚拟的地址空间，有的申请的是物理地址空间，给各个进程分配资源的策略以及后续的管理需要考虑各种情况，所以会降低系统的一致性，使系统变得更复杂

操作系统引导（Boot）

 

安装操作系统后的磁盘（硬盘）

在一个新磁盘里安装操作系统，安装后磁盘里面可能是下图这样，除了能看见的C、D、E、F磁盘分区外，在磁盘开头位置会留出一片区域用于存储MBR

分区表是一个数据结构，说明每个分区分别占多大空间以及每个分区的地址范围

C盘安装了操作系统，并且会使用C盘来启动操作系统，在这种情况下就可以把C盘称为这个磁盘的活动分区

再把C盘内部进一步细分。根目录就是你双击打开C盘之后看见的那些内容，可能会包含一些文件夹和文件

操作系统引导（开机过程）

操作系统要启动，数据要被放到主存里面

计算机的主存由ROM和RAM两部分组成，平时说手机内存和电脑内存是多少通常说的是RAM，里面的数据一断电就被清空。ROM芯片被集成在电脑主板上，里面存储BIOS（Basic Input/Output System）基本输入输出系统，BIOS由一系列程序组成，其中最重要的是ROM引导程序，ROM芯片里的数据不会因为断电而丢失

开机时CPU通电就会从主存当中固定的位置找到并执行ROM引导程序

它会指示CPU把磁盘的MBR读入主存，CPU执行磁盘引导程序，磁盘引导程序根据分区表判断C盘的位置

接下来读入PBR，CPU执行PBR里面的程序，它会负责找到启动管理器程序，这个程序通常存放在更目录下面完成操作系统初始化的一系列工作

硬件自检 —— 检查有没有插磁盘，有没有插内存条等等

例：Windows操作系统的自举程序

虚拟机

传统计算机

虚拟机

借助虚拟机管理程序把一台物理机器虚拟化为多台虚拟机器

第一类VMM类似传统的操作系统，负责直接管理并分配硬件资源

第一类VMM如何把硬件资源分配给各个VM，让每个VM都拥有各自独立的硬件资源？一个单核CPU也可以模拟多台VM，只需要划分CPU的时间片，给每个VM分配若干个时间片，在上层的操作系统看来似乎给自己分配的就是一个独立的CPU。磁盘和内存的分配则只需要划分空间分配给各个VM

只有VMM运行在内核态能够使用特权指令，而上层的的操作系统运行在用户态，当上层的操作系统想要使用特权指令时行为动作会被VMM截获，VMM负责判断使用是否合法和对指令进行等价转换模拟出执行效果

 

第二类VMM运行在Host OS上，想要给各个VM分配硬件资源只能申请Host OS给它分配，它再进行再分配。硬件资源的管理者依然是Host OS

第二类VMM在内核态的部分以VM驱动程序的形式加载到Host OS当中，当上层的Guest OS发出系统调用会被第二类VMM截获，然后由第二类VMM进行处理，代替它向底层的Host OS发出系统调用

第一类VMM可以直接把未经抽象的物理资源分配给上层的VM

Host OS给申请分配物理资源的第二类VMM分配的资源是经过抽象的，第二类VMM把得到的虚拟硬件资源再分配给各个VM。上层的Guest OS使用硬件资源时地址需要先映射为VMM获得的虚拟地址空间，Host OS需要再将其映射到实际的物理地址空间。经过多层虚拟就意味着再使用这些硬件资源时需要经过多层映射才可以对应到最终的物理地址上，这就会导致第二类VMM性能更差

常用的虚拟机软件

上图要迁移Guest OS，只需要将其导出为ISO镜像文件，拷贝到在另一台电脑后在该电脑的VirtualBox上加载安装就可以使用跟原来完全一样的Guest OS，包括在原Guest OS上安装的一些程序和数据

支持虚拟化的CPU通常分更多指令等级

如让第一类VMM运行在Ring 0，让Guest OS的内核运行在Ring 1，用户进程运行在Ring2，这样第一类VMM就不用检查每一条特权指令的执行