操作系统基础知识校招面经整理、热身

操作系统基础知识

进程和线程的区别：

进程是程序调度的基本单位，既包括时间概念——一段由一系列指令占用的 CPU 的时间片，也包括资源概念——处理这些指令所需的各种资源，包括内存空间，进程上下文，I/O权限等。
线程是进程中任务执行的基本单位，是比进程更细的粒度对资源的划分，进程中占用的 CPU 时间片可以继续细化为一个个具体的任务，每个任务分别占用一小段时间片。同时不同线程也拥有自己的线程上下文，并共享所在进程内的公共内存空间，为了更好操作这些公共内存空间，线程间需要一些同步、互斥机制（如各种锁、信号等），共享内存以及同步、互斥机制，就成为了线程间通信的手段。
例如 Java 当中启动 Main 函数以后相当于启动了一个 JVM 进程，而 Main 函数所在线程作为该进程的主线程。

CPU 主要调度是线程还是进程：

从系统角度看，CPU 的调度是以进程为粒度的。每次 CPU 挂起、就绪、运行、阻塞、终止等操作的基本对象都是进程。CPU 要负责对运行的进程调度所需的各种资源，并在当前进程挂起时为其保存上下文。
线程更多的是进程内部的概念，其切换不影响 CPU 资源分配。

僵尸进程与孤儿进程：

僵尸进程：一个已经执行完毕的子进程，向父进程发送的 exit() 信号没有被处理，导致该进程继续存在于进程表中没有被处理，也无法被直接关闭，成为僵尸进程。
处理方法：

对其父进程执行 kill -9 指令，杀掉父进程。
重启电脑。

孤儿进程：一个正在执行的子进程，其父进程已经退出，该进程成为孤儿进程。
该进程无需特殊处理，会被 init 进程接管，处理其执行状态，直到该子进程运行完毕结束生命周期。

Linux 进程管理：

进程信息
- 进程地址空间
- 进程状态
- 进程执行优先级
- 进程调用的资源信息
- 进程打开的文件、网络端口
- 进程的信号掩码
- 进程用户组
进程状态
- Runnable 正在（准备）执行
- Sleeping 等待资源
- Zombie 尝试结束
- Stopped 挂起、停止运行
信号：可作为进程间通信的手段，也可以由终端发送，改变进程状态。常见如 INT、KILL、STOP、Quit、HUP、TERM、SEGV 等
进程相关命令
- kill [-signal] pid 给进程传递信号，默认发送 TERM
- pgrep 筛选进程号
- pkill 发送信号给筛选结果
- killall 杀死进程的所有实例
- ps 资源监控，显示进程的 PID、UID、优先级、控制终端、占用内存、CPU时间、当前状态
- top 实时版的 ps，类似 windows 的任务管理器和资源监视器
前台进程：由用户控制的终端会话创建和控制的进程；后台进程：不与用户交互的进程

Linux 内存管理：

内存分区
- 代码段 text
- 数据段 data
- BSS 段
- 堆
- 栈
进程数据结构组织方法
- 进程内存描述映射到一个数据结构 vm_area_struct ，该结构以链表、红黑树形式组织，结点指向其对应进程的起始地址和终止地址
内核内存管理
- 分页，空闲页面处理采用伙伴关系
- 基本函数 get_free_page 在内核中分配内存 malloc 利用堆动态分配调用 brk 分配内存
- 内存分配器
  - slab 将小内存当作对象，使用完毕后缓存到「存储池」留待复用，接口 Kmalloc
  - Vmalloc 函数实现非连续内存分配

进程通信：

「互斥量」mutex，「信号量」Semaphore，用于并发控制: 二者都是可以同时被若干进程访问的全局变量。互斥量可以看作是只有 1 bit 的二元信号量（类似 boolean 值），对应「加锁」、「解锁」操作，但两次操作的进程须为同一个；而信号量是一个正整数 n，同一时间最多可以有 n 个进程可以访问到资源。
信号量需要维护如下信息
- 信号量的当前值，记为 x；
- 在此信号量上操作的最后一个进程的PID；
- 等待该信号量的值大于 x 的进程数；
- 等待该信号量的值为 0 的进程数；
  此外需要维护一个阻塞在该信号量上的进程队列。
「管程」Monitor，用于并发控制：互斥量和信号量的问题在于，作为全局变量，围绕其写的并发代码可读性、可维护性差，往往牵一发而动全身。因此，我们可以把这类变量（通常是一系列条件变量）封装在一个专门用于实现并发的类中，称为管程 Monitor，而互斥量和信号量就是其内部私有的一个数据结构。管程中有指向进程的指针（或PID），用以标记当前占用资源的进程；有进程等待队列，标记等待资源的进程。
「管道」：一个环形的缓冲区存储无格式的字节流。，允许两个进程以「生产者-消费者」模型进行通信。操作系统对请求管道的进程强制实施互斥，因而管道是半双工。管道分为「命名管道」和「匿名管道」。
- 命名管道：允许无亲缘关系的进程间通信。
- 匿名管道：用于父子进程间通信。
消息传递：进程间通过系统提供的 send 和 receive 系统调用发送与接受消息。如果消息的寻址方式为「直接寻址」，则进程之间直接处理消息；若为「间接寻址」，则存取消息通过一个「信箱」媒介，这种形式即是常见的「消息队列」。
「共享内存」：性能最好，最常用的通信方式。创建一段内存，多个进程都有一块虚拟内存映射到这块公共内存块。需要搭配信号量等互斥约束使用。
- linux 的共享内存实现方式比较特殊。在系统初始化时就在磁盘 SWAP 区（即 linux 下辅助实现虚拟内存的分区），建立了一个专门用来实现共享内存的临时文件系统 shm（断电后销毁）。内核定义一种结构 ipc_ids，实例名为 shm_ids，该实例中的 entries 字段指向了一个 ipc_id_ary 结构；此结构有一个数组字段，数组每一个元素指向了一个 shmid kernel 结构；此结构中的 shm_perm 字段指向了一个 kern_ipc_perm 结构，定义了进程间通信的许可信息、另一个字段 shm_file 指向了一个临时文件 file 对象，进程通信时，内核将这个文件映射到用户地址空间，从而可以被许可的进程共享。
「信号」signal：通知进程某个异步事件已经发生，信号可以在进程之间发送，也可由内核发送。UNIX 中一个信号对应其目标进程所在进程表中的一个字段中的一位，因此没有特定的顺序、优先级等概念。而 LINUX 还扩展出了可以有优先级和排队功能的「实时信号」。
「套接字」Socket：用于不同机器间的进程通信。

进程调度方法：

进程的调度本质上就是对不同进程的优先级队列进行队列管理，所有调度方法的区别可以说就是一个个存储进程指针的优先级队列(Prioritry Queue)的优先级算法的区别。
调度分为「长程调度」（决定是否一个作业创建进程）、「中程调度」（决定进程在内存中的换入换出）、以及「短程调度」（决定下次执行哪个进程）。一般意义上的「调度」指短程调度。

调度的规则（目标）：
- 面向用户：响应时间 latency，设定一个阈值，使得平均响应时间小于该阈值的用户数量最多。
- 面向系统：吞吐量 throughput，进程完成的速度。重要性次于前者。
调度策略（选择函数，即决定优先级队列中下一个进程的函数）：策略可以根据根据是否发生「抢占」（中断当前进程而切换到下一个进程）来分类。
几个参数：
$w$ - 进程当前在系统中的停留时间；
$T_r$ - 周转时间，进程从提交到完成的时间间隔，是其所有 $w$ 片段的加和；
$e$ - 当前进程花费的执行时间；
$T_s$ - 进程所需的总服务时间，即进程总共执行了 $s$ 时间后，可以结束，是其所有 $e$ 的加和；
$T_r/T_s$ - 归一化周转时间，表示进程的相对延迟，如果很高则说明进程的等待时间远大于执行时间；
$s$ - 进程预计的服务时间。
- 「先到先服务」（First Come First Served，FCFS，或先进先出 FIFO），则选择函数为 max[$w$], 即选择等待时间最长的进程。
  对长进程比较友好，但会使得长进程之后的短进程的归一化周转时间 $T_r/T_s$ 远超其他进程。
  更合理的做法是维护多个优先级队列，每个队列内部采用 FCFS 方案，而队列之间的优先级采用其他方法。
- 「轮转」（Round Robin，RR，或 Time slicing）最简单，选择函数为常数，周期性产生时钟中断。每个进程公平地分配到长度为 $q$ 的时间片。
  较小的时间片 $q$ 对短进程比较友好，当时间片 $q$ 很大时，RR 退化为 FCFS。
  对处理器密集型进程友好，而 I/O密集型进程多数时间因等待 I/O 而被阻塞，降低 I/O 设备性能。一种改进是使用「虚拟轮转法」（Virtual Round Robin，VRR），非 I/O 进程在一个就绪队列中排队，对于 I/O 进程，每一个 I/O 信号对应一个阻塞队列，当队列中的进程解除阻塞后，会加入到一个由所有 I/O 进程共享的 FCFS 的辅助队列当中，这个辅助队列的优先级高于前述非 I/O 进程的就绪队列，处理器在这个辅助队列和就绪队列之间采用 RR 分配时间片。
- 「最短进程优先」（Shortest Process Next, SPN），选择预计处理时间最短的进程，采用「指数平均法」预测进程运行时间， $S_{(n+1)} = \alpha T_n + (1-\alpha)S_n$。
  降低了对长作业的偏向，但连续的短进程会导致长进程饥饿。另外缺少抢占机制，没有改善当长进程进入运行时后来短进程仍然很高的归一化周转时间 $T_r/T_s$。
- 「最短剩余时间」（Shortest Remaining Time，SRT），类似 SPN，但是增加了抢占机制，于是选择函数从「预计最短处理时间」变成了「预计最短剩余时间」。
  不容易偏向长进程，中断的开销好于轮转法，但需要额外开销记录过去的服务时间。
- 「最高相应比优先」（Highest Response Rate Next，HRRN），由于我们事先不知道进程服务时间的大小，所以用响应比 $R = \frac {w+s} s$ 来预测，选择 R 值更大的进程。
  短进程的 $s$ 更小，作为分母会使得 R 值更大，因此往往优先得到服务，长进程在等待足够长的时间（$w$ 值足够大）之后，也能较后来的短进程获得优先服务。
- 「反馈法」（Feed Back， FB），基于「轮转」的动态优先级机制。设立多个优先级队列，RQ0, RQ1, … RQn，其中前一个队列的优先级严格大于后一个，每一个队列内部以 FCFS 组织优先级。新进入的进程放在最高优先级的 RQ0 队列，以时间片轮转的方式获得处理器时间，当进程没有运行完而遭到抢占后，会降级到下一级队列，即从 RQ0 进入 RQ1，RQ1 进入 RQ2，以此类推。
  此方案可能使得长进程的周转时间 $T_r$ 增加，当有短进程不断进入时，会导致长进程饥饿。可以作适当优化。考虑到长进程被多次抢占，会进入靠后的优先级队列，可以让时间片长度 $q$ 随队列优先级靠后而增长，例如，对于队列 RQi，其时间片长度为 $q=2^i$。此外，还可以设定等待阈值，当进程在某一优先级队列中等待时间超过该阈值，将此进程提升到高一优先级的队列。

为什么要有内核态、用户态？中断、系统调用、进程切换等相关：

操作系统需要具备如下功能：内存保护（操作系统所运行的内存环境不能被用户的程序干扰）、特权指令（一些机器指令只有操作系统能够执行），为了实现这两个功能，引入「运行模式」的概念，分为「内核模式」和「用户模式」。
「内核」在多数情况下作为一个进程来实现，提供操作系统的绝大多数功能，例如：调度、文件系统、网络、设备驱动、内存管理等。在现今流行的「微内核体系结构」当中，内核的功能主要有：地址空间管理、进程间通信、基本的调度。
在典型的 Linux 系统中，「用户模式」下进程可以通过内核提供的「内核组件」切换到「内核模式」。内核组件包括两大类：「信号」（内核向进程提供的信息，通常由陷阱、进程调度、中断等触发）和「系统调用」（进程通过此类接口主动请求内核的服务，包括文件系统、进程、调度、进程间通信、套接字等）。
「进程切换」或者说「进程调度」，是触发模式切换的常见场景，以此为例体会一下整个流程。

中断的时机：中断、陷阱、系统调用。其中「中断」和「陷阱」都是「系统中断」的一种，前者是由当前进程外部的事件引发，后者则是当前进程遇到的错误或异常引发。「中断」会由中断处理器处理后，转移控制权给该中断对应的操作系统例程，常见的情形有「时钟中断」（进程时间片耗尽）、「I/O中断」、「内存失效」（虚存地址对应的物理内存不在内存中，需要从外存调用）；「陷阱」则会视严重程度退出当前进程或尝试恢复；「系统调用」则由进程主动激活。
模式切换：对于中断的处理，处理器会保存当前进程的部分上下文，将程序计数器进入中断处理程序，并从用户模式切换到内核模式，并进一步判断是否进入进程切换。
进程切换：保存当前进程的全部上下文（程序计数器 PC 和其他寄存器），更新进程控制块 PCB，并将 PCB 移到相应的进程状态队列，最后选择另一个进程执行并更新对应的上下文环境。

锁与死锁相关：

对锁的理解

锁的本质就是一种对资源访问的限制手段，所有影响了资源访问权限的操作广义上都可以叫做「锁」。
对于一个锁，我们关心如下问题：

（我们管理的是）什么资源
（不）允许访问的条件
加锁的粒度（锁影响的范围）。

所有锁的设计实现，基本就围绕着解决以上三点的思路展开。

针对不同的使用场景，还可能会出现相应的针对性设计，如事务原子性（典型如数据库）、分布式、资源单一性等。

死锁产生的充分必要条件

「互斥」，一次只有一个进程可以访问一个资源。
「占有并等待」，当一个进程等待其他进程时，继续占有已分配的资源。
「不可抢占」，不能剥夺（抢占）某个进程已经占有的资源。
「循环等待」，存在一个以进程为节点的有向环，每个进程至少占有其有向边所指向进程所需的一个资源。（此条件是策略条件，取决于进程请求和释放资源的顺序）

死锁的预防：破坏死锁产生的条件

「间接预防」：防止死锁产生的前三个条件中的任意一个
- 互斥：互斥是保证并发一致性的前提，无法禁止。但是在某些情况中可以采用策略削弱互斥性，例如某些资源允许多个读访问（写访问依然是互斥的），则多个进程的读请求不会引发死锁。
- 占有并等待：可以要求进程一次性请求所有需要的资源，若有请求不满足则阻塞。
  缺点是会造成低效。进程可能暂时只需要一部分资源就能执行，但是该策略使得进程被阻塞；另一方面，进程占有过多资源又暂时用不上，造成了浪费。
- 不可抢占：当已经占有某些资源的一个进程进一步申请其他资源遭到拒绝时，操作系统可以要求其返还已占有的资源；或者，当一个较低优先级的进程所占有的资源被另一个较高优先级的进程申请时，操作系统可以抢占前者，并释放资源供后者使用。
「直接预防」：防止发生循环等待
- 循环等待：操作系统定义不同类型资源的申请顺序，$R_1, R_2, R_3, …, R_n$。当进程已经占有资源 $R_i$时，只能继续请求满足 $j > i$ 的资源 $R_j$。与防止占有并等待的策略类似，此方法会造成务必要的阻塞等待、资源浪费。

死锁的避免：是死锁预防的进一步优化，并不确切地破坏某个死锁条件，而是通过在请求资源时，具体判断该请求是否会达到死锁点并加以避免。

「进程启动拒绝」：如果一个进程的启动会导致死锁，则拒绝启动。
对于一个由 $n$ 个进程和 $m$ 种资源组成的系统，定义如下向量和矩阵

变量	描述
Resource = $\bold R$ = $(R_1, R_2, \dots, R_m)$	系统中每种资源的总量
Available = $\bold V$ = $(V_1, V_2, \dots, V_m)$	当前可用的每种资源存量
Claim = $\bold C$ =$\begin{bmatrix} C_{11} & C_{12} & \dots & C_{1m} \ C_{21} & C_{22} & \dots & C_{2m} \ \vdots & \vdots & \ddots & \vdots \ C_{n1} & C_{n2} & \dots & C_{nm} \end{bmatrix}$	进程 $i$ 对资源 $j$ 的请求量
Allocation = $\bold A$ =$\begin{bmatrix} A_{11} & A_{12} & \dots & A_{1m} \ A_{21} & A_{22} & \dots & A_{2m} \ \vdots & \vdots & \ddots & \vdots \ A_{n1} & A_{n2} & \dots & A_{nm} \end{bmatrix}$	当前进程 $i$ 占有的资源 $j$
可得如下关系：

对于任意类的资源 $j$，满足 $R_j = V_j + /sum^N_{i = 1} A_{ij}$。即一份资源要么可用，要么已被分配。
对于任意进程 $i$ 和资源 $j$，满足 $A_{ij} \le C_{ij} \le R_j$，前一个不等号表示进程占有的资源不会超过其请求的量，后一个不等号表示进程请求的资源量不能超过该资源的总量。
则避免策略可以定义为，若一个新进程 $\bold P_{n+1}$ 的对某个资源 $j$ 的请求 $C_{(n+1)j}$ 会导致死锁，则拒绝启动。即合法的新进程 $P_{n+1}$ 对所有资源 $j$ 的请求必须满足 $R_j \ge C_{(n+1)j} + \sum^n_{i=1} C_{ij}$

「资源分配拒绝」：又名「银行家算法」。
当系统中的某个进程能顺利运行到结束之后，其会返回所占用的资源。那么我们可以通过前面定义的一组向量和矩阵 $\bold R, \bold V, \bold C, \bold A$ 来定义一个系统当前的状态。则如果当前状态存在一个资源分配序列不会导致死锁（即该分配序列中，每次分配资源后，总有至少一个进程能运行到结束，从而返还资源，供其他进程继续运行），则称其为「安全状态」；否则称为「不安全状态」
则避免策略可以定义为，进程 $i$ 请求一组资源时，假设同意后（即引入了新的一行 $C_i, A_i$）系统仍处于安全状态，则允许该请求；否则阻塞，直到当前系统的状态（一般指 $V$ 向量）发生变化，使得同意后仍处于安全状态。
死锁避免的优点：无需像死锁预防那样采用抢占或者回滚进程的策略，资源浪费少，适用范围更广。
死锁避免的缺点（局限性）：
- 需要进程事先知道并声明请求的最大资源；
- 需要不同进程之间相互独立，没有同步关系；
- 所分配的资源总量需要保持恒定；
- 进程在占有资源时不能退出。

死锁的检测：操作系统尽可能满足进程请求的资源，但是周期性地执行死锁检测算法，检查循环等待条件是否成立。

死锁检测算法
检测后的恢复
1. 取消所有死锁涉及的进程；
2. 把死锁进程回滚到之前定义过的安全的检查点，并重启；
3. 依次取消死锁涉及的进程，直到某一次检测不到死锁为止；
4. 依次抢占资源，直到某一次检测不到死锁为止；

解决死锁的综合策略：将资源按照用途分类，不同资源之间定义申请顺序（防止循环等待），对每一类资源内部的分配采用适合该资源类的算法：
- 「可交换空间」：进程交换所涉及的外存存储块，采用类似占有并等待的预防策略，要求进程一次性请求所需的所有资源。
- 「进程资源」：可分配的文件和设备，采用类似死锁避免策略，要求进程事先声明所需的资源量。
- 「内存」：内存页、内存段等，采用类似不可抢占的预防策略，令高优先级的进程抢占低优先级进程的内存资源，低优先级的进程将被挂起。
- 「内部资源」：I/O 通道等，采用基于资源排序的预防策略。

容器虚拟化，微服务，Docker 及 K8s 相关：

「内核控制组」（cgroups）：容器的实现基础。Linux 内核提供的一系列 API，以允许将进程分组、管理用户安全权限、系统资源。Linux 进程的 namespace 具有层次结构，所有进程都是一个名叫 Init 的引导时进程的子进程，cgroups 允许多个这样的进程层次结构在单个操作系统中共存。cgroups 提供以下功能
- 资源限制：配置每个组的内存限制。
- 优先级：使某些组获得更大的 CPU 利用率、磁盘 I/O 吞吐量等。
- 记账：记录一个组的资源使用情况。
- 控制：冻结某个进程组、设置检查点、重启等操作。
容器引擎的典型任务：
- 设置：创建并启动 Linux 容器环境。这是实现用户空间分区的基础。
- 配置：配置网络参数、根文件系统、装载操作、允许越过容器环境访问的设备等。这使得容器可以运行特定的应用程序和命令。
- 管理：提供容器环境的启动、停止、冻结、迁移等操作。
容器的典型特征：
- 容器环境中不需要客户操作系统，开销更小。
- 容器管理软件简化了容器创建和管理过程，因此具有便携性，可以快速从一个系统迁移到另一个系统。
容器的缺陷：
- 容器化的应用程序只能在支持相同操作系统内核、具有相同虚拟化支持功能的系统上移植。容器化的 Windows 程序只能在 Windows 机器上运行。
- 客户操作系统可以为虚拟机提供独特的内核设置，不适用于主机上的其他虚拟机。容器没有这类功能。
- 容器虚拟化位于操作系统和应用程序的边界（不同于虚拟机虚拟化位于硬件的操作系统的边界），降低开销的同时可能带来更大的安全漏洞。
微服务
- 微服务定义：应用程序组件的架构分解为若干个独立服务，这些服务之间组成了松散耦合模式，每个服务就是一个微服务元素，元素之间使用一组明确的 API 相互通信。原先的应用程序中的每个特定服务都被分解为各个部分，而不再共享单一的应用程序堆栈。
- 微服务主要优点
  - 实现更小的可部署单元，便于用户更快地发布更新、执行功能。符合「持续交付」（Continuous Delivery，CD）的要求，在不必创建单片系统的情况下推出小型单元。
  - 支持精确的可扩展性，可以轻松复制某个微服务以创建多个实例，并分散负载到应用的一小部分，而不必为整个应用程序执行复制操作。
Docker：Docker 提供了一种简单快捷的方式在主机操作系统上运行、加载容器「镜像」（image）。主要由以下组件构成
- 镜像 Image：一个只读的模板，用以创建实例化 Docker 容器。
- 客户端 Client：用户在客户端请求使用镜像创建新容器。
- 主机 Host：一个具有自己主机操作系统的平台，可以执行容器化应用程序。
- 引擎 Engine：轻量级的运行时包，可在主机系统上构建和运行 Docker 容器。
- 机器 Machine：机器用于在主机上安装、设置引擎，并配置客户端与引擎的通信。机器也可以直接在机器所在的主机上直接设置镜像。
- 注册表 Registry：注册表存储镜像。镜像创建后可以推送到公共注册表（如 Docker Hub）或私有注册表。镜像可以从注册表中被提取到主机。
- Kubernutes：一种容器编排技术。

生产者-消费者问题：

问题描述：现有一个缓冲区 Buffer，一个生产者 Producer 负责向 Buffer 中添加（生产）数据，一个消费者 Consumer 负责向 Buffer 中读取（消费）数据。请问如何保证在 Buffer 为空时，消费者不会继续读取数据；在 Buffer 满时，生产者不会继续添加数据？