本文对面试/笔试过程中经常会被问到的一些关于操作系统的问题进行了梳理和总结，一方面方便自己温故知新，另一方面也希望为找工作的同学们提供一个复习参考。
进程与线程及他们的区别
- 进程是对运行时程序的封装，是系统进行资源调度和分配的的基本单位，实现了操作系统的并发；
- 线程是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发；
- 一个程序至少有一个进程，一个进程至少有一个线程，线程依赖于进程而存在；
- 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存
进程间通信的几种方式
- 管道（pipe）及命名管道（named pipe）：管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信；
- 信号（signal）：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；
- 消息队列：消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；
- 共享内存：可以说这是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等；
- 信号量：主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段；
- 套接字：这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。
线程同步的方式
- 互斥量 Synchronized/Lock：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问
- 信号量 Semphare：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
- 事件(信号)，Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作
进程同步有哪几种机制
- 原子操作
- 信号量机制
- 自旋锁管程
- 会合
- 分布式系统
死锁
死锁的概念
在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲，就是两个或多个进程无限期的阻塞、相互等待的一种状态。
死锁产生的四个必要条件
- 互斥：至少有一个资源必须属于非共享模式，即一次只能被一个进程使用；若其他申请使用该资源，那么申请进程必须等到该资源被释放为止；
- 占有并等待：一个进程必须占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有；
- 非抢占：进程不能被抢占，即资源只能被进程在完成任务后自愿释放
- 循环等待：若干进程之间形成一种头尾相接的环形等待资源关系
死锁的处理基本策略和常用方法
解决死锁的基本方法主要有 预防死锁、避免死锁、检测死锁、解除死锁 、鸵鸟策略 等
死锁预防
死锁预防的基本思想是只要确保死锁发生的四个必要条件中至少有一个不成立，就能预防死锁的发生，具体方法包括：
- 打破互斥条件：允许进程同时访问某些资源。但是，有些资源是不能被多个进程所共享的，这是由资源本身属性所决定的，因此，这种办法通常并无实用价值。
- 打破占有并等待条件：可以实行资源预先分配策略(进程在运行前一次性向系统申请它所需要的全部资源，若所需全部资源得不到满足，则不分配任何资源，此进程暂不运行；只有当系统能满足当前进程所需的全部资源时，才一次性将所申请资源全部分配给该线程)或者只允许进程在没有占用资源时才可以申请资源（一个进程可申请一些资源并使用它们，但是在当前进程申请更多资源之前，它必须全部释放当前所占有的资源）。但是这种策略也存在一些缺点：在很多情况下，无法预知一个进程执行前所需的全部资源，因为进程是动态执行的，不可预知的；同时，会降低资源利用率，导致降低了进程的并发性。
- 打破非抢占条件：允许进程强行从占有者那里夺取某些资源。也就是说，当一个进程占有了一部分资源，在其申请新的资源且得不到满足时，它必须释放所有占有的资源以便让其它线程使用。这种预防死锁的方式实现起来困难，会降低系统性能。
- 打破循环等待条件：实行资源有序分配策略。对所有资源排序编号，所有进程对资源的请求必须严格按资源序号递增的顺序提出，即只有占用了小号资源才能申请大号资源，这样就不回产生环路，预防死锁的发生
死锁避免的基本思想
死锁避免的基本思想是动态地检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。
所谓安全状态是指：如果系统能按某个顺序为每个进程分配资源（不超过其最大值），那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。资源分配图算法和银行家算法是两种经典的死锁避免的算法，其可以确保系统始终处于安全状态。其中，资源分配图算法应用场景为每种资源类型只有一个实例(申请边，分配边，需求边，不形成环才允许分配)，而银行家算法应用于每种资源类型可以有多个实例的场景。
死锁解除
死锁解除的常用两种方法为进程终止和资源抢占。所谓进程终止是指简单地终止一个或多个进程以打破循环等待，包括两种方式：终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止；所谓资源抢占是指从一个或多个死锁进程那里抢占一个或多个资源，此时必须考虑三个问题：
- 选择一个牺牲品
- 回滚：回滚到安全状态
- 饥饿（在代价因素中加上回滚次数，回滚的越多则越不可能继续被作为牺牲品，避免一个进程总是被回滚）
操作系统内存管理，分页和分段有什么区别
段式存储管理
段式存储管理是一种符合用户视角的内存分配管理方案。在段式存储管理中，将程序的地址空间划分为若干段（segment），如代码段，数据段，堆栈段；这样每个进程有一个二维地址空间，相互独立，互不干扰。段式管理的优点是：没有内碎片（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外碎片（比如4k的段换5k的段，会产生1k的外碎片）
页式存储管理
页式存储管理是一种用户视角内存与物理内存相分离的内存分配管理方案。在页式存储管理中，将程序的逻辑地址划分为固定大小的页（page），而物理内存划分为同样大小的帧，程序加载时，可以将任意一页放入内存中任意一个帧，这些帧不必连续，从而实现了离散分离。页式存储管理的优点是：没有外碎片（因为页的大小固定），但会产生内碎片（一个页可能填充不满）。
两者的不同点：
目的不同：分页是由于系统管理的需要而不是用户的需要，它是信息的物理单位；分段的目的是为了能更好地满足用户的需要，它是信息的逻辑单位，它含有一组其意义相对完整的信息；
大小不同：页的大小固定且由系统决定，而段的长度却不固定，由其所完成的功能决定；
地址空间不同： 段向用户提供二维地址空间；页向用户提供的是一维地址空间；
信息共享：段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制；
内存碎片：页式存储管理的优点是没有外碎片（因为页的大小固定），但会产生内碎片（一个页可能填充不满）；而段式管理的优点是没有内碎片（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外碎片（比如4k的段换5k的段，会产生1k的外碎片）。
操作系统中进程调度策略
FCFS(先来先服务，队列实现，非抢占的)：先请求CPU的进程先分配到CPU
SJF(最短作业优先调度算法)：平均等待时间最短，但难以知道下一个CPU区间长度
优先级调度算法(可以是抢占的，也可以是非抢占的)：优先级越高越先分配到CPU，相同优先级先到先服务，存在的主要问题是：低优先级进程无穷等待CPU，会导致无穷阻塞或饥饿；解决方案：老化
时间片轮转调度算法(可抢占的)：队列中没有进程被分配超过一个时间片的CPU时间，除非它是唯一可运行的进程。如果进程的CPU区间超过了一个时间片，那么该进程就被抢占并放回就绪队列。
多级队列调度算法：将就绪队列分成多个独立的队列，每个队列都有自己的调度算法，队列之间采用固定优先级抢占调度。其中，一个进程根据自身属性被永久地分配到一个队列中。
多级反馈队列调度算法：与多级队列调度算法相比，其允许进程在队列之间移动：若进程使用过多CPU时间，那么它会被转移到更低的优先级队列；在较低优先级队列等待时间过长的进程会被转移到更高优先级队列，以防止饥饿发生。
虚拟内存
虚拟内存允许执行进程不必完全在内存中。
虚拟内存的基本思想是：每个进程拥有独立的地址空间，这个空间被分为大小相等的多个块，称为页(Page)，每个页都是一段连续的地址。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻进行必要的映射；当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。这样，对于进程而言，逻辑上似乎有很大的内存空间，实际上其中一部分对应物理内存上的一块(称为帧，通常页和帧大小相等)，还有一些没加载在内存中的对应在硬盘上，如下图所示。
由上图可以看出，虚拟内存实际上可以比物理内存大。当访问虚拟内存时，会访问MMU（内存管理单元）去匹配对应的物理地址（比如图5的0，1，2）。如果虚拟内存的页并不存在于物理内存中（如图5的3,4），会产生缺页中断，从磁盘中取得缺的页放入内存，如果内存已满，还会根据某种算法将磁盘中的页换出。
注意，请求分页系统、请求分段系统和请求段页式系统都是针对虚拟内存的，通过请求实现内存与外存的信息置换。
页面置换算法
FIFO先进先出算法：在操作系统中经常被用到，比如作业调度（主要实现简单，很容易想到）；
LRU（Least recently use）最近最少使用算法：根据使用时间到现在的长短来判断；
LFU（Least frequently use）最少使用次数算法：根据使用次数来判断；
OPT（Optimal replacement）最优置换算法：理论的最优，理论；就是要保证置换出去的是不再被使用的页，或者是在实际内存中最晚使用的算法。
虚拟内存的应用与优点
虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以把CPU交给另一个进程使用。虚拟内存的使用可以带来以下好处：
- 在内存中可以保留多个进程，系统并发度提高
- 解除了用户与内存之间的紧密约束，进程可以比内存的全部空间还大
颠簸
颠簸本质上是指频繁的页调度行为，具体来讲，进程发生缺页中断，这时，必须置换某一页。然而，其他所有的页都在使用，它置换一个页，但又立刻再次需要这个页。因此，会不断产生缺页中断，导致整个系统的效率急剧下降，这种现象称为颠簸（抖动）。
内存颠簸的解决策略包括：
- 如果是因为页面替换策略失误，可以修改替换算法来解决这个问题；
- 如果是因为运行的程序太多，造成程序无法同时将所有频繁访问的页面调入内存，则要降低多道程序的数量；
- 否则，还剩下两个办法：终止该进程或增加物理内存容量。
局部性原理
时间上的局部性：最近被访问的页在不久的将来还会被访问；
空间上的局部性：内存中被访问的页周围的页也很可能被访问。
系统中断
中断是指CPU对系统发生的某个事件做出的一种反应，CPU暂停正在执行的程序，保留现场后自动地转去执行相应的处理程序，处理完该事件后再返回断点继续执行被“打断”的程序。
中断可分为三类
- 第一类是由CPU外部引起的，称作中断，如I/O中断、时钟中断、控制台中断等。
- 第二类是来自CPU的内部事件或程序执行中的事件引起的过程，称作异常，如由于CPU本身故障（电源电压低于105V或频率在47～63Hz之外）、程序故障（非法操作码、地址越界、浮点溢出等）等引起的过程。
- 第三类由于在程序中使用了请求系统服务的系统调用而引发的过程，称作“陷入”(trap,或者陷阱)。
前两类通常都称作中断，它们的产生往往是无意、被动的，而陷入是有意和主动的。
中断处理
中断处理一般分为中断响应和中断处理两个步骤。中断响应由硬件实施，中断处理主要由软件实施。
中断响应
对中断请求的整个处理过程是由硬件和软件结合起来而形成的一套中断机构实施的。发生中断时，CPU暂停执行当前的程序，而转去处理中断。这个由硬件对中断请求作出反应的过程，称为中断响应。一般说来，中断响应顺序执行下述三步动作：
- 中止当前程序的执行；
- 保存原程序的断点信息（主要是程序计数器PC和程序状态寄存器PS的内容）；
- 从中断控制器取出中断向量，转到相应的处理程序。
通常CPU在执行完一条指令后，立即检查有无中断请求，如果有，则立即做出响应。
当发生中断时，系统作出响应，不管它们是来自硬件（如来自时钟或者外部设备）、程序性中断（执行指令导致“软件中断”—Software Interrupts），或者来自意外事件（如访问页面不在内存）。
如果当前CPU的执行优先级低于中断的优先级，那么它就中止对当前程序下条指令的执行，接受该中断，并提升处理机的执行级别（一般与中断优先级相同），以便在CPU处理当前中断时，能屏蔽其它同级的或低级的中断，然后保存断点现场信息，通过取得的中断向量转到相应的中断处理程序的入口。
中断处理
CPU从中断控制器取得中断向量，然后根据具体的中断向量从中断向量表IDT中找到相应的表项，该表项应是一个中断门。于是，CPU就根据中断门的设置而到达了该通道的总服务程序的入口。
核心对中断处理的顺序主要由以下动作完成：
- 保存正在运行进程的各寄存器的内容，把它们放入核心栈的新帧面中
- 确定“中断源”或核查中断发生，识别中断的类型（如时钟中断或盘中断）和中断的设备号（如哪个磁盘引起的中断）。系统接到中断后，就从机器那里得到一个中断号，它是检索中断向量表的位移。中断向量因机器而异，但通常都包括相应中断处理程序入口地址和中断处理时处理机的状态字
- 核心调用中断处理程序，对中断进行处理
- 中断处理完成并返回。中断处理程序执行完以后，核心便执行与机器相关的特定指令序列，恢复中断时寄存器内容和执行核心栈退栈，进程回到用户态。如果设置了重调度标志，则在本进程返回到用户态时做进程调度。
管程机制
管程的概念
管程可以看做一个软件模块，它是将共享的变量和对于这些共享变量的操作封装起来，形成一个具有一定接口的功能模块，进程可以调用管程来实现进程级别的并发控制。
进程只能互斥地使用管程，即当一个进程使用管程时，另一个进程必须等待。当一个进程使用完管程后，它必须释放管程并唤醒等待管程的某一个进程。
在管程入口处的等待队列称为入口等待队列，由于进程会执行唤醒操作，因此可能有多个等待使用管程的队列，这样的队列称为紧急队列，它的优先级高于等待队列。
管程的特征
模块化
管程是一个基本的软件模块，可以被单独编译。
抽象数据类型
管程中封装了数据及对于数据的操作，这点有点像面向对象编程语言中的类。
信息隐藏
管程外的进程或其他软件模块只能通过管程对外的接口来访问管程提供的操作，管程内部的实现细节对外界是透明的。
使用的互斥
任何一个时刻，管程只能由一个进程使用。进入管程时的互斥由编译器负责完成。
目态与管态
大多数计算机系统将CPU执行状态分为目态与管态。CPU的状态属于程序状态字PSW的一位。CPU交替执行操作系统程序和用户程序。
管态又叫特权态，系统态或核心态。CPU在管态下可以执行指令系统的全集。通常，操作系统在管态下运行。
目态又叫常态或用户态。机器处于目态时，程序只能执行非特权指令。用户程序只能在目态下运行，如果用户程序在目态下执行特权指令，硬件将发生中断，由操作系统获得控制，特权指令执行被禁止，这样可以防止用户程序有意或无意的破坏系统。
从目态转换为管态的唯一途径是中断。
从管态到目态可以通过修改程序状态字来实现，这将伴随这由操作系统程序到用户程序的转换。