前言

为了准备秋招及春招，现阶段的任务是将所学过的知识进行复习，并串联起来。而操作系统中，最为重要的就是进程、线程、内存、文件

还有一些很常问的一些技术点，堆和栈、内存分区、虚拟内存 + 物理内存、进程 + 线程 + 协程、死锁、分片机制、五大组件、中断和系统调用、同步和异步等等问题。

对于操作系统的理解，对于这些基础的计算机知识的掌握是必须深入学习，要花很大的功夫去理解清楚这些，工作中，对于真实线上系统的稳定性、对于底层技术的理解是有帮助的，操作系统是面试中常见问题之一。

OS概述

操作系统（Operating System）

控制和管理整个计算机系统的硬件和软件资源，并合理组织和调度资源分配（系统资源的管理者）
为用户和应用软件提供接口和服务（向上层提供方便易用的服务）
最基本的系统软件，对硬件机器功能进行拓展（最接近硬件的一层软件）

指令：CPU能识别、执行的最基本的指令，二进制机器代码

操作系统提供的服务、功能？

GUI，图形用户界面
命令接口：联机（交互式）命令接口windows中的cmd，脱机（批处理）命令接口.bat文件
系统调用，需通过程序间接使用printf函数

操作系统的特点？

并发。指两个或多个事件在同一时间间隔内交替执行。区别于并行的概念，并行指的是同一时刻同时发生。单核 CPU同一时刻只能执行一个程序，因此各个程序只能并发执行；而多核 CPU则可以并行执行相应CPU数量的程序。
共享。资源共享，系统资源可供多个并发的进程共同使用。互斥共享（摄像头）和同时共享（访问磁盘资源）
虚拟。把一个物理上的实体变为若干个逻辑上的对应物。空分复用技术（虚拟存储器，虚拟内存）和时分复用技术（虚拟处理器）。没有并发性，虚拟性就没有存在的意义
异步。在多道程序环境下，允许多个程序并发执行，但系统资源是有限的，因此进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进。没有并发性，也就不存在异步性

用户态、内核态

内核态->用户态。执行一条特权指令，修改PSW标志位为“用户态”

用户态->内核态。由“中断”引发，硬件自动完成变态的过程。凡是需要操作系统介入的地方，都会引发中断信号，意味着强行夺回CPU的控制权

中断

中断的出现，可以使操作系统夺回对CPU的控制权（用户态->内核态），避免出现一个程序从始至终占用着CPU的情况，保证并发性

内外中断的内外指的是，使得中断发生的指令来自于CPU内还是外

内中断（异常），与当前指令有关，来源于CPU的内部。如以下例子

在用户态下执行特权指令
执行除法指令时，除数为0
应用程序请求操作系统内核的服务，执行陷入指令（陷入指令是在用户态 执行的，执行陷入指令后立刻引发内中断，使CPU进入核心态）

外中断，与当前指令无关，来源于CPU的外部。如以下例子

时钟中断。当一个时间片完毕后，时钟部件就会发送一个中断信号给CPU。这时的CPU是处于用户态的

系统调用：凡是需要对共享资源进行访问，就一定需要操作系统介入，并使用系统调用来实现

OS引导（boot）

在这里插入图片描述

CPU执行主存中特定地址的ROM引导程序（作用：硬件自检，将主引导记录读入RAM）
把磁盘中第一块的主引导记录读入内存，执行磁盘引导程序，扫描分区表（作用：找到活动分区）
从活动分区中读入引导记录并执行（作用：找到启动管理器）
执行OS初始化程序，完成开机

进程管理（处理机CPU）

进程概念

进程出现的意义？

更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性

什么是进程？进程由什么组成？

进程是程序的一次执行过程
是资源分配和调度的独立单位
是对一个正在执行程序的一种抽象

PCB、程序段、数据段构成了进程实体
PCB是进程存在的唯一标识，包含了PID、UID和所分配给进程的内存、文件等各种信息
程序段由程序的可执行文件，一系列的指令组成
数据段是进程在执行过程中产生的数据

进程状态

创建态、终止态

就绪态、运行态、阻塞态

就绪态->运行态：分配了CPU资源
运行态->就绪态：时间片到，或被其它优先级更高的进程抢占
运行态->阻塞态：申请某种资源，或等待某一事件的发生
阻塞态->就绪态：资源分配到位，等待的事件发生
创建态->就绪态：初始化PCB，并分配相应资源

进程通信

指两个进程之间产生数据交互

因各进程的内存地址空间相互独立，所以进程通信必须要有操作系统参与

共享存储

因为各进程间的地址空间是分隔开的，想要实现数据交互，只能另外开辟一个共享存储区，步骤为：

申请一片共享内存区
将共享内存区映射到进程自己的地址空间

各个进程对共享存储区的访问是互斥（PV）的

基于存储区的共享。由进程控制数据形式以及存放位置
基于数据结构的共享。

消息传递

以格式化的消息为单位
用“发送消息 / 接收消息”两个原语进行数据交换

消息传递可以分为两种方式：

直接通信方式。发送进程要指明接收进程的ID，反之接收也要进行指定
间接通信方式。以“信箱”作为中间实体进行通信。从原先要指定进程的ID变为指定信箱的ID。可以多个进程往同一个信箱send消息，也可以多个receive消息

管道通信

管道，就是一个固定大小的内存缓冲区

半双工通信。同一时刻只能存在一个方向的数据通信
各进程互斥访问管道
管道在被写满或者读空时，写/读进程将会被阻塞

线程机制

什么是线程？为什么要引入线程？

为了使程序能够并发执行，我们引入了进程。
但有了进程以后，有的进程可能需要“同时 ”做很多事，而传统的进程只能串行地执行一系列程序。因此，引入了线程，来增加并发度。

程序执行流的最小单位由进程变为了线程
进程是系统资源分配的基本单位，而线程是CPU调度的基本单位
进程实现并发的同时，线程也具有并发性，从而使得一个进程内多种任务可以同时执行
引入线程使得系统的开销减小。实现线程级的并发时，由于不需要切换进程环境，系统开销小

用户级线程、内核级线程

用户级线程的管理工作由应用程序通过线程库实现；内核级线程则由操作系统的内核完成
用户级线程不需要操作系统切换至核心态；而内核级需要切换
操作系统能意识到内核级线程的存在，而意识不到用户级线程，会将它看成一整个进程

	优点	缺点
用户级线程	不需要切换至核心态，系统开销小，效率高	如果一个用户级线程被阻塞，会导致整个进程都被阻塞，并发度不高。多个线程不能充分利用多核处理机实现并行运行
内核级线程	一个内核级线程被阻塞，其余线程不受影响。多线程可在多核处理机上并行执行	需要变态，开销大，成本高

内核级线程才是CPU调度的基本单位

进程调度

调度：以某种规则处理任务的执行顺序

三个层次：

区别是所要进行调度的对象，由大至小，由高至低

高级调度（作业调度）：作业，一个具体的任务。用户向操作系统提交一个作业，表明希望让操作系统启动一个程序，并处理一个具体的任务。每一个作业只调入一次，调出一次，会创建对应的PCB。（外存 $\rightarrow$ 内存，面向作业）
中级调度（内存调度）：把处于挂起状态的进程，重新调入内存。内存不足时，会暂时将某些进程的数据调出外存。待内存空闲或进程需要时，再重新调入内存。（外存 $\rightarrow$ 内存，面向进程）
低级调度（进程 / 处理机调度）：从就绪队列中按照某种规则选择一个进程，将处理机分配给它。最基本的一种调度，频率很高。（内存 $\rightarrow$ CPU）

挂起态：进程映像调到了外存。（就绪挂起，阻塞挂起）

	要做什么？	调度发生在？	发生频率	对进程状态的影响
高级调度	按照某种规则，从后备队列中选择合适的作业调入内存，并为其创建进程	外存 $\rightarrow$ 内存（面向作业）	低	无 $\rightarrow$ 创建态 $\rightarrow$ 就绪态
中级调度	按照某种规则，从挂起队列中选择进程将其数据调回内存	外存 $\rightarrow$ 内存（面向进程）	中	挂起 $\rightarrow$ 就绪
低级调度	按照某种规则，从就绪队列中选择进程为其分配处理机	内存 $\rightarrow$ CPU	高	就绪态 $\rightarrow$ 执行态

调度评价指标

CPU利用率：忙碌时间 / 总时间
系统吞吐量：单位时间内完成作业的数量
周转时间：从提交到被完成所经历的时间
平均周转时间：各作业的周转时间之和 / 作业数
带权周转时间：作业周转时间 / 实际运行时间（ $\geq1$ ）。带权周转时间越小，用户体验越好。周转时间相同时，运行时间的长短所带来的体验会不一样，因此有了这个指标
平均带权周转时间：各作业带权周转时间之和 / 作业数
等待时间：周转时间 - 等待时间
响应时间：从提交请求到首次响应所经过的时间

进程调度算法

算法思想
算法规则
作业调度 or 进程调度
抢占 or 非抢占
优缺点
饥饿：某进程 / 作业长期得不到服务

FCFS

先来先服务，First Come First Server

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

非抢占式
优点：公平、算法实现简单
缺点：对长作业有利，而对短作业不利。排在长作业后的短作业，带权周转时间很大
不会饥饿

只考虑了等待时间，而没有考虑运行时间

SJF

短作业优先，Short Job First

最短，指的是要求服务的时间最短

每次调度时选择当前已到达且运行时间最短的作业 / 进程

默认是非抢占式（抢占式：最短剩余时间优先算法）
优点：平均等待时间、平均周转时间“最短”
缺点：不公平。短作业有利，长作业不利
长作业饥饿

最短剩余时间优先算法，Shortest Remaining Time Next：

每当有新的进程加入就绪队列，比较新加入进程的剩余运行时间与当前运行的进程剩余时间。如果更短，新进程则会抢占处理机，原进程重新回到就绪队列

只考虑了运行时间，而没有考虑等待时间

HRRN

高响应比优先算法，Highest Response Ratio Next

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

计算响应比，选择响应比最高的作业 / 进程为其服务

非抢占式，只有当前运行的进程主动放弃CPU时，才进行调度
优点：综合考虑等待时间与运行时间
不会饥饿

既考虑了等待时间，又考虑了运行时间

时间片轮转

Round-Robin

时间片大小为2：

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

设置时间片不宜过大，否则算法会退化为先来先服务算法
如果太小（切换进程开销占比不超过1%），会导致进程切换过于频繁
所以太大太小都不行

用于进程调度，只有进程才有被分配处理机时间片这一概念
只能是抢占式
优点：公平；让各个进程得到及时的响应；适合分时操作系统
缺点：进程切换有开销；不区分任务的紧急程度
不会饥饿

优先级调度

根据任务的紧急程度，决定处理顺序

每个作业 / 进程有各自的优先级，调度时选择优先级较高的作业 / 进程

（本题优先数越大，优先级越高）

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

抢占式的优先级调度算法，除了进程主动放弃处理机的情况，当就绪队列发生改变时，也需要检查是否抢占

优点：用优先级区分紧急程度，适用于实时操作系统。可以灵活地调整对各种作业 / 进程被服务的机会
缺点：若频繁地有更高优先级的进程到来，可能导致饥饿
会发生饥饿

多级反馈队列

对所有调度算法的折中

规则如下：

设置多个就绪队列，优先级从高到低，时间片从小到大
新进程到达时先进入第1级队列，按FCFS原则排队等待分配时间片
若在一级队列的时间片用完后还未结束，进行下一级优先队列的队尾
只有K级队列为空时，才会为K+1级队列中的进程分配时间片
发生抢占时（在k级队列运行的过程中，若更上级的队列1~k-1级进入了一个新的进程，新进程会抢占处理机 ），被抢占处理机的进程重新放回本队列的队尾

特点如下：

用于进程调度
抢占式
优点：公平；响应快；照顾了短进程；
缺点：会饥饿，不断的有高优先级的短进程到来

进程同步、进程互斥

进程同步

进程同步：对多个相关的进程在执行次序上进行协调，以使并发执行的各进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性

进程间制约关系：

间接制约关系（互斥关系，互斥地访问临界资源）
直接制约关系（同步关系、合作关系）

同步机制 / 临界互斥应遵循的规则：

空闲让进：当临界区空闲时，应使一个请求进入临界区的进程立即进入
忙则等待：当有进程正在临界区时，其它进程必须等待
有限等待：进程等待进入临界区的时间必须是有限的，防止死等
让权等待：一旦一个进程无法进入临界区，则必须让出处理机，防止忙等

进程互斥

进程互斥：当一个进程正在访问某个临界资源时，另一个也想要访问的进程必须等待

逻辑上的实现：

进入区。设置正在访问临界资源标志
临界区。访问临界资源
退出区。解除正在访问临界资源的标志
剩余区

死锁问题

死锁：各进程互相等待对方手里的资源，处于一种僵持局面，若无外力作用，该组进程中的所有进程均无法继续向前推进，称为进程死锁

死锁的4个必要条件：

互斥条件：对必须互斥访问的资源的争抢才会引起死锁
不剥夺条件：进程保持的资源只能主动释放，不可强行剥夺
请求与保持条件：保持某些资源不放的同时，请求别的资源
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程所拥有的资源正在被下一个进程所请求

什么时候会发生死锁？

对不可抢占性资源（打印机）的竞争
进程的推进顺序不当，即请求和释放资源的顺序不当

预防死锁

破坏死锁4个必要条件中的某一个或某几个

破坏互斥条件。SPOOLing技术（将互斥资源改为共享资源）。但大多情况下不可行
破坏不可剥夺条件。进程在请求某一资源得不到满足时，选择放弃已有的全部资源或者从别的进程那强行剥夺需要的资源
破坏请求与保持条件。静态分配方式，在进程开始运行前一次性申请完它所需要的全部资源，而后的过程中不需要再请求资源
破坏循环等待条件。顺序资源分配法，即给系统中的每一个资源编号。一个进程只有拥有了小编号的资源，才能去申请大编号的资源

避免死锁（银行家算法）

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

在不安全状态，不一定发生死锁。发生死锁，一定是在不安全状态。
不安全状态只是发生死锁的必要条件

银行家算法的核心思想：

[x] 在资源分配之前，预先判断这次分配是否会导致系统进入不安全状态

资源总数（10，5，7），剩余可用资源（3，3，2）

算法步骤：

检查本次申请的资源数是否不超过最先声明的请求资源数
检查本次申请的资源数是否不超过系统剩余可用的资源
如果满足1、2条件，则预分配资源给当前请求的进程，并更新数据
进行【安全性检测】，如果不会进入不安全状态，则正式分配

安全性检测：

检查当前的剩余可用资源是否能够满足某一个进程的最大需求，如果可以，则把该进程加入安全序列。待进程执行结束后，把该进程所持有的资源全部回收

死锁的检测与解除

检测是否发生了死锁。
发生了死锁后，如何从死锁状态中解脱出来

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

而在上述的图中，先找到请求资源小于等于剩余资源的结点，消去边

表示可完全简化，没发生死锁

解除死锁的方法：

资源剥夺法。挂起（暂时放到外存）某些死锁进程，并抢占它的所有资源，将这些资源分配给其它死锁进程
撤销进程法。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源，意味着从头再来
进程回退法。让一个或多个死锁进程回退到不发生死锁的位置。这要求系统记录进程的历史信息

内存管理（存储器）

分页分段

分页的作用，好处？和分段有什么区别？

把进程分页，各个页面可离散地放到各个内存块当中
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。即进程的页面与内存的页框具有一一对应关系

既免除了移动信息的工作，又充分利用了内存空间；消除了动态分区法的碎片问题，提升了内存空间的利用率

分页的参数：

页面：将进程的逻辑地址空间分为大小相等的分区
页框：将进程的物理地址空间分为大小相等的分区
页表：记录页面到页框的对应关系

和分段的区别：

分页是固定大小且各个页面大小相等的；分段大小不等，根据程序逻辑划分；
分页主要目的是为了提升内存的空间利用率，分段是为了满足用户编程和使用上模块化的需求；
分页是信息的物理单位，是用户不可见的，页长由系统确定，只能从页大小的整数倍地址开始；分段是信息的逻辑单位，是用户可见的，由用户根据需要确定，段起始可以从内存任何地址开始。

内存分配机制

内存分配的机制？

单一连续分配：也称单用户存储管理。将内存分为系统区和用户区两部分。用户区一次只能装入一个作业
固定分区分配：将内存用户空间划分为若干个大小相等的区域，每个分区只装入一道作业
动态分区分配：按照作业大小分区，但划分的时间、大小、位置都是动态的

虚拟内存

什么是虚拟内存？

基于局部性原理，实现信息的部分装入，从逻辑上为用户提供一个比物理内存容量大得多的、可寻址的内存储器

局部性原理：

时间局部性：近期执行的某条指令或者被访问的某个数据，在不久后很可能再次被执行或访问
空间局部性：某个存储单元被访问后，不久后其附近的存储单元也有可能被访问到

虚拟内存的特征：

多次性：一个作业被分成多次调入内存执行（最重要）
对换性：允许在作业的运行过程中进行换进、换出
虚拟性：能够从逻辑上扩充内存容量，用户可使用的内存容量远大于实际内存容量

页面置换算法

请求分页存储管理中的页面算法：决定应该换出哪个页面，追求更少的缺页率

当所访问的信息不在内存时，由操作系统负责将所需的信息从外存调入内存
若内存空间不足，由操作系统负责将内存中暂时用不到的信息调出内存

OPT

最佳置换算法，optimal

在这里插入图片描述
每次选择淘汰的页面，将是以后不再使用（向后看）的页面。

性能最好，但无法实现

FIFO

先进先出置换算法

在这里插入图片描述
每次选择淘汰的页面，是最早进入内存的页面

实现简单，但算法性能差

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

LRU

最近最久未使用置换算法，least recently used

在这里插入图片描述
每次选择淘汰的页面，是最近最久未使用（往前看）的页面

算法性能好，最接近OPT，但需要专门的硬件支持

CLOCK

时钟置换算法，CLOCK算法；最近未用算法，NRU算法

为每个页面设置一个访问位
- 访问位为1，表示最近访问过
- 访问位为0，表示最近没被访问过
内存中的每个页面通过链接指针，链接成一个循环队列
当需要淘汰一个页面的时候，只需检测访问位。如果有0，则将其换出；如果是1，则置为0

简单的CLOCK算法选择一个淘汰页面的时候，最多会经过2轮扫描。即使第1轮没有出现访问位为0的，第二轮由于第一轮将1置0，则一定会在第2轮出现

改进CLOCK

在考虑一个页面是否有被访问过的基础上，还考虑了该页面是否进行了修改。如果被修改了，则需要写回外存，会执行IO操作。所以应该优先淘汰没有修改过的页面

为每个页面同时增加（访问位，修改位）

先找（0，0），最近没被访问，也没修改 ；
找不到再找（0，1），顺便将扫描过的页的访问位置0，最近没访问，但被修改 ；
再找（0，0），最近访问过，但没修改 ；
最后找（0，1），既访问，也修改

改进型的CLOCK算法选择一个淘汰页面的时候，最多会经过4轮扫描

文件管理

文件结构

文件系统中文件是如何组织的？

文件的逻辑结构：
1、流式文件
这是一种无结构的文件，文件内的数据不再组成记录，只是一串顺序的信息集合，称为字节流文件。

2、记录式文件
这是一种有结构的文件，它包含若干逻辑记录，逻辑记录是文件中按信息在逻辑上的独立含义所划分的信息单位。

文件的物理结构：
1、顺序文件：又称连续文件，是一种逻辑记录顺序和物理块顺序完全一致的文件；
2、连接文件：存放信息的物理块不必连续，使用连接字进行连接。
3、索引文件：系统为每个文件建立索引表，可以有不同的索引形式，具有连接文件、记录可以散列存储，具有直接读写任意记录的能力；缺点是索引表的空间开销和查找时间过大。
4、直接文件：使用哈希法，实现快速存储。

文件共享是指多个进程使用同一个文件，不仅为不同进程完成共同任务所必需，而且节省大量外存空间，减少因文件复制而增加的I/O操作次数。

文件共享的方式：静态共享、动态共享和符号连接共享。

静态共享：从多个目录可以到达同一个文件，无论进程是否运行都会存在的连接是静态的。

动态共享：不同应用进程或同一用户的不同进程，并发地访问同一文件。