1. 解释一下什么是操作系统
操作系统是运行在计算机上最重要的一种软件，它管理计算机的资源和进程以及所有的硬件和软件。它为计算机硬件和软件提供了一种中间层
通常情况下，计算机上会运行着许多应用程序，它们都需要对内存和 CPU 进行交互，操作系统的目的就是为了保证这些访问和交互能够准确无误的进行
操作系统所处位置示意图
2. 解释一下操作系统的主要目的是什么
- 管理计算机资源，这些资源包括 CPU、内存、磁盘驱动器、打印机等
- 提供一种图形界面，作为用户和计算机之间的桥梁
- 为其他软件提供服务，操作系统与软件进行交互，以便为其分配运行所需的任何必要资源
3. 操作系统的种类有哪些
- 操作系统通常预装在用户购买计算机之前，大部分用户都会使用默认的操作系统
- 用户额可以升级或者更改操作系统，常见的操作系统有三种：Windows、macOS 和 Linux
4. 操作系统结构
单体结构
在大多数系统中，整个系统在内核态以单一程序的方式运行。整个操作系统是以程序集合来编写的，链接在一块形成一个大的二进制可执行程序，这种系统统称为单体系统
在单体系统中构造实际目标程序时，会首先编译所有单个过程（或包含这些过程的文件），然后使用系统链接器将它们全部绑定到一个可执行文件中
在单体系统中，对于每个系统调用都会有一个服务程序来保障和运行。需要一组使用程序来弥补服务程序需要的功能，例如从用户程序中获取数据，可将各种过程划分为一个三层模型
除了在计算机初启动时所装载的和兴操作系统外，许多操作系统还支持额外的扩展。比如 I/O 设备驱动和文件系统。这些部件可以按需装载。在 UNIX 中把它们叫做
共享库（shared library），在 Windows 中则被称为动态链接库（Dynamic Link Library, DLL）。它们的扩展名为.dll，在C:\Windows\system32目录下存在 1000 多个 DLL 文件，所以不能轻易删除 C 盘文件
分层结构
分层系统使用层来分隔不同的功能单元，每一层只与该层的上层和下层通信。每一层都使用下面的层来执行其功能，层与层之间的通信通过预定义的固定接口通信
分层结构操作系统示意图
微内核
为了实现高可靠性，将操作系统划分成小的、层级之间能够更好定义的模块是很有必要的。只有一个微内核模块运行在内核态，其余模块可以作为普通用户进程运行。由于把每个设备驱动和文件系统分别作为普通用户进程，这些模块中的错误虽然会使这些模块崩溃，但是不会使整个系统死机
MINIX 3是微内核的代表作，它的具体结构如下
在内核的外部，系统的构造有三层，它们都在用户态下运行，最底层是设备驱动器。由于它们都在用户态下运行，所以不能物理地访问 I/O 端口空间，也不能直接发出 I/O 命令。相反，为了能够对 I/O 设备编程，驱动器构建一个结构，指明哪个参数写到哪个 I/O 端口，并声称一个内核调用，这样就完成了一次调用过程
客户-服务器模式
微内核思想的策略是把进程划分为两类：
服务器，每个服务器用来提供服务；客户端，使用这些服务。这个模式就是所谓的客户-服务器模式客户-服务器模式会有两种载体，一种情况是一台计算机即是客户又是服务器，在这种方式下，操作系统会有某种优化；但是普遍情况下是客户端和服务器在不同的机器上，它们通过局域网或广域网连接
客户通过发送消息与服务器通信，客户端并不需要知道这些消息是在本地机器上处理，还是通过网络被送到远程机器上处理。对于客户端而言，这两种情形是一样的：都是发送请求并得到回应
5. 什么是按需分页
- 在操作系统中，进程是以页为单位加载到内存中的，按需分页是一种虚拟内存的管理方式
- 在使用请求分页的系统中，只有在尝试访问页面所在的磁盘并且该页面尚未在内存中时，也就发生了缺页异常，操作系统才会将磁盘页面复制到内存中
6. 多处理系统的优势
随着处理器的不断增加，计算机系统有单机系统变为了多处理系统，多处理系统的吞吐量比较高，多处理系统拥有多个并行的处理器，这些处理器共享时钟、内存、总线、外围设备等
多处理系统由于可以共享资源，因此可以开源节流，节省成本，整个系统的可靠性也随之提高。多处理系统示意图
7. 什么是内核
- 在计算机中，内核是一个计算机程序，它是操作系统的核心，可以控制操作系统中所有的内容。内核通常是在 boot loader 装载程序之前加载的第一个程序
- boot loader：引导加载程序，它是一个程序，能够将计算机的操作系统放入内存中。在电影通电或者计算机重启时，BIOS 会执行一些初始测试，然后将控制权转移到引导加载程序所在的主引导记录（MBR）
8. 什么是实时系统
- 实时操作系统对时间做出了严格的要求，实时操作系统分为两种：硬实时和软实时
- 硬实时操作系统：规定某个动作必须在规定的时刻内完成或发生，比如汽车生产车间，焊接机器必须在某一时刻内完成焊接，焊接得太早或者太晚都会对汽车造成永久伤害
- 软实时操作系统：虽然不希望偶尔违反最终的时限要求，但是仍然可以接受。并且不会引起任何永久性伤害。比如数字音频、多媒体、手机都是属于软实时操作系统
- 二者的区别是：是否在时刻内必须完成以及是否造成严重伤害
9. 什么是虚拟内存
- 虚拟内存是一种内存分配方案，是一项可以用来辅助内存分配的机制。应用程序是按页装载进内存中的，但并不是所有的页都会装载到内存中，计算机中的硬件和软件会将数据从 RAM 临时传输到磁盘中来弥补内存的不足
- 如果没有虚拟内存的话，一旦将计算机内存填满后，计算机会反馈：对不起，您无法再加载任何应用程序，请关闭另一个应用程序以加载新的应用程序
- 对于虚拟内存，计算机可以执行操作时查看内存中最近未使用过的区域，然后将其复制到硬盘上。虚拟内存通过复制技术实现了加载更多应用程序的能力。复制是自动进行的，用户感知不到它的存在
10. 什么是进程和进程表
- 进程就是正在执行程序的实例，比如说 Web 程序就是一个进程，shell 也是一个进程，文章编辑器 Macdown 也是一个进程
- 操作系统负责管理所有正在运行的进程，操作系统会为每个进程分配特定的时间来占用 CPU，操作系统还会为每个进程分配特定的资源
- 操作系统为例跟踪每个进程的活动状态，维护了一个进程表。在进程表的内部，列出了每个进程的状态以及每个进程使用的资源等
11. 什么是线程，线程和进程的区别
进程是正在运行的程序的实例，线程就是进程中的单条流向。因为线程具有进程中的某些属性，所以线程又被称为轻量级的进程
创建线程的开销要比进程小很多，因为创建线程仅仅需要堆栈指针和程序计数器就可以了，而创建进程需要操作系统分配新的地址空间、数据资源等，这个开销比较大
线程不像进程那样具有很强的独立性，线程之间会共享数据。线程和进程持有资源的区别如下
12. 使用多线程的好处是什么
- 能够提高用户的响应顺序
- 在流程中的资源共享
- 比较经济适用
- 能够对多线程架构有深入的理解
13. 什么是 RR 调度算法
- RR(Round-Robin) 调度算法主要针对分时系统，RR 的调度算法会把时间片以相同的部分并循环地分配给每个进程，RR 调度算法没有优先级的概念
- RR 调度算法的实现比较简单，而且每个线程都会占有时间片，并不存在线程饥渴的问题
14. 导致系统出现死锁的情况（需要同时满足的四个条件）
- 互斥（Mutual Exclusion）：一次只能有一个进程使用资源。如果另一个进程请求该资源，则必须延迟请求进程，直到释放该资源为止
- 保持并等待（Hold and Wait）：必须存在一个进程，该进程至少持有一个资源，并且正在等待获取其他进程当前所持有的资源
- 无抢占（No Preemption）：资源不能被抢占，也就是说，在进程完成任务之后，只能由拥有它的进程自动释放资源
- 循环等待（Circular Wait）：必须存在一组 {p0, p1, … pn} 的等待进程，使 p0 等待 p1 持有的资源、p1 等待由 p2 持有的资源，pn-1 等待由 pn 持有的资源，而 pn 等待由 p0 持有的资源
15. RAID 的不同级别
- RAID 概念：磁盘冗余阵列，简称磁盘阵列。利用虚拟化技术把多个硬盘结合在一起，称为一个或多个磁盘阵列组，目的是提升性能或数据冗余
- RAID 级别
- RAID 0：无容错的条带化磁盘阵列
- RAID 1：镜像和双工
- RAID 2：内存式纠错码
- RAID 3：比特交错奇偶校验
- RAID 4：块交错奇偶校验
- RAID 5：块交错分布式奇偶校验
- RAID 6：P + Q 冗余
16. 什么是 DMA
- DMA 的中文名称是直接内存访问，即 CPU 授予 I/O 模块权限在不涉及 CPU 的情况下读取或写入内存，也就是 DMA 可以不需要 CPU 的参与，这个过程由称为 DMA 控制器（DMAC）的芯片管理
- 由于 DMA 设备可以直接在内存之间传输数据，而不是使用 CPU 作为中介，因此可以缓解总线上的拥塞。DMA 通过允许 CPU 执行任务，同时 DMA 系统通过系统和内存总线传输数据来提高系统并发性
17. 什么是设备驱动程序
- 在计算机中，设备驱动程序时一种计算机程序，它能够控制或操作连接到计算机的特定设备
- 驱动程序提供了与硬件进行交互的软件接口，使操作系统和其他计算机程序能够访问特定设备，同时不需要了解其硬件的具体构造
18. 进程间的通信方式
通信概念
竞态条件：即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种情况就被称为竞态条件（race condition）
临界区
不仅共享资源会造成竞态条件，事实上共享文件、共享内存也会造成竞态条件。避免方式：禁止一个或多个进程在同一时刻对共享资源（包括共享内存、共享文件等）进行读写
换句话说，我们需要一种互斥（mutual exclusion）条件，也就是说，如果一个进程在某种方式下使用共享变量和文件的话，除该进程之外的其他进程就禁止做这种事（访问统一资源）
一个好的解决方案，应该包含下面四种条件
任何时候两个进程不能同时处于临界区
不应对 CPU 的速度和数量做任何假设
位于临界区外的进程不得阻塞其他进程
不能使任何进程无限等待进入临界区
忙等互斥：当一个进程在对资源进行修改时，其他进程必须进行等待，进程之间要具有互斥性，事实上各种解决方案都是基于忙等互斥提出的
解决方案
消息传递：消息传递是进程间实现通信和同步等待的机制，使用消息传递，进程间的交流不需要共享变量，直接就可以进行通信；消息传递分为发送方和接收方
先进先出队列：先进先出队列指的是两个不相关联进程间的通信，两个进程之间可以彼此相互进程通信，这是一种全双工通信方式
管道：管道用于两个相关进程之间的通信，这是一种半双工的通信方式，如果需要全双工，需要另外一个管道
直接通信：在这种进程通信的方式中，进程与进程之间只存在一条链接，进程间要明确通信双方的命名
间接通信：间接通信时通信双方不会直接建立连接，而是找到一个中介者，这个中介者可能是一个对象等等。进程可以在其中放置消息，并且可以从中删除消息，以此达到进程间通信的目的
消息队列：消息队列是内核中存储消息的链表，它由消息队列标识符进行标识，这种方式能够在不同的进程之间提供全双工的通信连接
共享内存：共享内存是使用所有进程之间的内存来建立连接，这种类型需要同步进程访问来相互保护
19. 进程间状态模型
cat chapter1 chapter2 chapter3 | grep tree- 第一个进程是
cat，将三个文件级联并输出；第二个进程是grep，它从输入中选择具有包含关键字tree的内容。 - 根据这两个进程的相对速度（这取决于两个程序的相对复杂度和个子所分配到的 CPU 时间片），可能会发生这种情况：grep 准备就绪开始运行，但是输入进程还没有完成，于是必须阻塞 grep 进程，直到输入完毕
- 第一个进程是
当一个进程开始运行时，进程间的状态切换图如下
- 运行态：进程实际占用 CPU 时间片运行时
- 就绪态：可运行，但因为其他进程正在运行而处于就绪状态
- 阻塞态：除非某种外部事件发生，否则进程不能运行
进程间状态切换过程
- 逻辑上来说，运行态和就绪态是很相似的。这两种情况下都表示进程可运行，但是第二种情况没有获得 CPU 时间分片。第三种状态与前面两种状态不同的原因是这个进程不能运行，CPU 空闲时也不能运行
- 三种状态会涉及四种状态的切换，在操作系统发现进程不能继续执行时会发生状态 1 的轮换，在某些系统中进程执行系统调用，例如 pause，来获取一个阻塞的状态。在其他系统中包括 UNIX，当进程从管道或特殊文件（例如终端）中读取没有可用的输入时，该进程会被自动终止
- 转换 2 和转换 3 都是由进程调度程序（操作系统的一部分）引起的，进程本身不知道调度程序的存在。转换 2 的出现说明进程调度器认定当前进程已经运行了足够长的时间，是时候让其他进程运行 CPU 时间片了。当所有其他进程都运行过后，这时候是让第一个进程重新获得 CPU 时间片的时候了，就会发生转换 3
- 程序调度指的是，决定哪个进程优先被运行和运行多久，这是很重要的一点。已经设计出许多算法来尝试平衡系统整体效率与各个流程之间的竞争需求
- 当进程等待的一个外部事件发生时（如从外部输入一些数据后），则发生转换 4.如果此时没有其他进程在运行，则立刻触发转换 3，该进程便开始运行，否则该进程会处于就绪阶段，等待 CPU 空闲后再轮到它运行
20. 调度算法都有哪些
批处理中的算法
先来先服务
很像是先到先得，可能最简单的非抢占式调度算法的设计就是先来先服务（First-come, First-served）。使用此算法，将按照请求顺序为进程分配 CPU。最基本的，会有一个就绪进程的等待队列。当第一个任务从外部进入系统时，将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时，它们排到就绪队列尾部。当正在运行的进程阻塞，处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时，它会像一个新到达的任务，会排在队列的末尾，即排在所有进程最后
这个算法的强大之处在于易于理解和编程，在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加一个新的作业或者阻塞一个进程，只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现
不过，先来先服务也是有缺点的，那就是没有优先级的关系。试想一下，如果有 100 个 I/O 进程正在排队，第 101 个是一个 CPU 密集型进程，那岂不是需要等到 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行，这在实际情况下根本不可能，所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行
最短作业优先
批处理中，第二种调度算法是最短作业优先（Shortest Jog First），我们假设运行时间已知。例如，一家保险公司，因为每天要做类似的工作，所以人们可以相当精确地预测处理 1000 个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短优先作业算法。如下图 a 所示，这里有 4 个作业 A、B、C、D，运行时间分别为 8、4、4、4 分钟。若按图中的次序运行，则 A 的周转时间为 8 分钟，B 为 12 分钟，C 为 16 分钟，D 为 20 分钟，平均时间为 14 分钟
现在考虑使用最短作业优先算法运行 4 个作业，如上图 b 所示，目前的周转时间分别为 4、8、12、20，平均为 11 分钟，可以证明最短作业优先是最优的。考虑有 4 个作业的情况，其运行时间分别为 a、b、c、d。第一个作业在时间 a 结束，第二个在时间 a + b 结束，以此类推。平均周转时间为 (4a + 3b + 2c + d)/4。显然 a 对平均值的影响最大，所以 a 应该是最短优先作业，其次是 b，然后是 c，最后是 d 它就只能影响自己的周转时间了。需要注意的是，在所有的进程都可以运行的情况下，最短作业优先的算法才是最优的
最短剩余时间优先
- 最短作业优先的抢占式版本被称作为最短剩余时间优先（Shortest Remaining Time Next）算法。使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。当一个新作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。这种方式能够使短期作业获得良好的服务
交互系统中的调度
轮询调度
一种最古老、最简单、最公平且最广泛使用的算法就是轮询算法（Round-Robin）。每个进程都会被分配一个时间段，称为时间片（quantum），在这个时间片内允许进程运行。如果时间片结束时进程还在运行的话，则抢占一个 CPU 并将其分配给另一个进程。如果进程在时间片结束前阻塞或结束，则 CPU 立即进行切换
轮询算法比较容易实现，调度程序所做的就是维护一个可运行进程的列表，就像下图中的 a，当一个进程用完时间片后就被移到队列的末尾，就像下图的 b
优先级调度
事实情况是不是所有的进程都是优先级相等的。例如，在一所大学中的等级制度，首先是院长，然后是教授、秘书、后勤人员，最后是学生。这种将外部情况考虑在内就实现了优先级调度（Priority Scheduling）
它的基本思想很明确，每个进程都被赋予一个优先级，优先级高的进程优先运行。但是也不意味着高优先级的进程能够永远一直运行下去，调度程序会在每个时钟中断期间降低当前运行进程的优先级。如果此操作导致其优先级降低到下一个最高进程的优先级以下，则会发送进程切换。或者，可以为每个进程分配允许运行的最大时间间隔。当时间间隔用完后，下一个高优先级的进程会得到运行的机会
最短进程优先
对于批处理系统而言，由于最短作业优先常常伴随着最短响应时间，一种方式是根据进程过去的行为进行推测，并执行估计运行时间最短的那个。假设每个终端上每条命令的预估运行时间为 T0，现在假设测量到其下一次运行时间为 T1，可以用两个值的加权来改进估计时间，即
aT0 + (1 - 1) T1。通过选择 a 的值，可以决定是尽快忘掉老的运行时间，还是在一段长时间内始终记住它们。当 a = 1/2 时，可以得到下面这个序列
可以看到，在三轮过后，T0 在新的估计值中所占比重下降至 1/8。有时把这种通过当前测量值和先前估计值进行加权平均从而从而得到下一个估计值的技术称为老化（aging），这种方法会使用很多预测值基于当前值的情况
彩票调度
- 有一种既可以给出预测结果而又有一种比较简单的实现方式的算法，就是彩票调度（Lottery Scheduling）算法。它的基本思想是为进程提供各种系统资源的彩票
- 当做出一个调度决策的时候，就随机抽出一张彩票，拥有彩票的进程将获得资源。比如在 CPU 进行调度时，系统可以每秒持有 50 次抽奖，每个中奖进程会获得额外运行时间的奖励。可以把彩票理解为 buff，这个 buff 有 15% 的几率能让你产生速度之靴的效果
公平分析调度
- 如果用户 1 启动了 9 个进程，而用户 2 启动了 1 个进程，使用轮换或相同优先级调度算法，那么用户 1 将得到 90% 的 CPU 时间，而用户 2 将得到 10% 的 CPU 时间
- 为了阻止这种情况的出现，一些系统在调度前会把进程的拥有者考虑在内。在这种模型下，每个用户都会分配一些 CPU 时间，而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证，那么无论一个用户有多少个进程，都将获得相同的 CPU 份额
实时系统中的调度
21. 页面置换算法都有哪些
分类
最优算法：在当前页面中置换最后要访问的页面。不幸的是，没有办法来判定哪个页面是最后一个要访问的，因此实际上该算法不能使用。然而，它可以作为衡量其他算法的标准
NRU 算法：更加 R 位和 M 位的状态将页面分为四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现，但是性能不是很好，存在更好的算法
FIFO 算法：会跟着页面加载进入内存中的顺序，并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面，因此这个算法也不是一个很好的选择
第二次机会算法：对 FIFO 的一个修改，它会删除页面之前检查这个页面是否仍在使用。如果页面正在使用，就会进行保留。这个改进算法提高了性能
时钟算法：是第二次机会算法的另外一种实现形式，时钟算法和第二次算法的性能差不多，但是会花费更少的时间来执行算法
LRU 算法：是一个非常优秀的算法，但是没有特殊的硬件（TLB）很难实现。如果没有硬件，就不能使用 LRU 算法
NFU 算法：是一种近似于 LRU 的算法，它的性能不是非常好
老化算法：是一种更接近 LRU 算法的实现，并且可以更好地实现，因此是一个很好的选择
工作集/工作集时钟算法：工作集算法提供了合理的性能开销，但是它的实现比较复杂。WSClock 是另外一种变体，它不仅能够提供良好的性能，而且可以高效地实现
最好的算法是老化算法和 WSClock 算法，它们分别是基于 LRU 和工作集算法，它们都具有良好的性能并且能够被有效实现。还存在其他一些好的算法，但实际上这两个可能是最重要的
总结
算法 注释 最优算法 不可实现，但可以用作基准 NRU(最近未使用) 算法 和 LRU 算法很相似 FIFO(先进先出) 算法 有可能会抛弃重要的页面 第二次机会算法 比 FIFO 有较大的改善 时钟算法 实际使用 LRU(最近最少) 算法 比较优秀，但是很难实现 NFU(最不经常使用) 算法 和 LRU 很类似 老化算法 近似 LRU 的高效算法 工作集算法 实施起来开销很大 工作集时钟算法 比较有效的算法
22. 影响调度程序的指标是什么
- CPU 使用率：CPU 正在执行任务（即不处于空闲状态）的时间百分比
- 等待时间：这是进程轮流执行的时间，也就是进程切换的时间
- 吞吐量：单位时间内完成进程的数量
- 响应时间：从提交流程到获得有用输出所经过的时间
- 周转时间：从提交流程到完成流程所经过的时间
23. 什么是僵尸进程
- 僵尸进程是已完成且处于终止状态，但在进程表中仍然存在的进程
- 僵尸进程通常发生在父子关系的进程中，由于父进程仍需要读取子进程的退出状态所造成的