【操作系统】常见面试题集锦（全）

前言

这篇文章主要讲解的主要面向企业面试而非考研的复试，不过相同的知识点，考研崽也可以复习一下

1. 进程、线程的区别和联系

具体也可看我这篇文章的详细回顾

1. 【操作系统】线程与进程的深入剖析（全）
2. 【操作系统】守护线程和守护进程的区别

进程是资源分配和调度的基本单位，而线程是进程的一个实体，也是 CPU 调度和分派的基本单位

共同点就是两者的切换过程是一样的，都是用户态内核态用户态，调用的栈都是内核栈

不同点就是花销，进程的花销要大于线程，因为创建撤销回收等
不同进程地址空间相互独立，同一进程内的线程共享同一地址空间
进程间相互不影响，而一个线程挂掉可能会导致进程无法执行

• 进程是系统资源调度的基本单位，拥有自已的独立堆栈。不同进程之间的通信需要切换上下文，开销比较大
• 线程是程序执行的基本单位，拥有程序计数器，一组寄存器和栈，堆是共享的。通信的时候主要通过共享内存，切换上下文比较快。
• 协程是用户态的轻量级别线程，拥有栈，堆是共享的，切换上下文比较快，因为没有内核态的参与。

2. 有了进程为什么还要线程

不同进程之间切换实现并发，各自占有CPU实现并行。但是这些也会导致缺点，一个进程只能做一件事，其他的进程来了会将其阻塞，为此引进了更小的粒度，线程。减少程序在并发执行时所付出的时间和空间开销，提高并发性能

3. 进程状态的切换

详情可看我这篇文章
【操作系统】线程与进程的深入剖析（全）

4. 并发和并行

• 并发是指宏观上在一段时间内能同时运行多个程序
• 并行则指同一时刻能运行多个指令（需要硬件支持，如多流水线、多核处理器或者分布式计算系统）

操作系统通过引入进程和线程，使得程序能够并发运行

并行是指两个或者多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔发生
并行是在不同实体上的多个事件，并发是在同一实体上的多个事件；

5. 外中断和异常的区别

• 外中断是指由CPU 执行指令以外的事件引起，如 I/O 完成中断（设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求）、时钟中断、控制台中断等
• 异常时由CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等

相同点：
最后都是由CPU发送给内核，由内核去处理，处理程序的流程设计上是相似的

不同点：

1. 产生源不相同，异常是由CPU产生的，而中断是由硬件设备产生的
2. 内核需要根据是异常还是中断调用不同的处理程序
3. 中断不是时钟同步的，这意味着中断可能随时到来；异常由于是CPU产生的，所以它是时钟同步的
4. 当处理中断时，处于中断上下文中；处理异常时，处于进程上下文中

6. 进程调度算法了解多少

先来先服务、短作业优先、最短剩余时间优先、

• 先来先服务 first-come first-serverd（FCFS） ：非抢占式，按照请求的顺序进行调度
  优点：有利长作业
  缺点：不利短作业，长作业需要执行很长时间，造成了短作业等待时间过长

• 短作业优先 shortest job first（SJF） ：非抢占式，估计运行时间最短的顺序进行调度
  缺点：长作业有可能会饿死，处于一直等待短作业执行完毕的状态。如果一直有短作业到来，那么长作业永远得不到调度

• 最短剩余时间优先 shortest remaining time next（SRTN） ：最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度，当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较，如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待

• 时间片轮转 ：将所有就绪进程按 FCFS （先来先服务）的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
  时间片轮转算法的效率和时间片的大小有很大关系：因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。而如果时间片过长，那么实时性就不能得到保证。

• 优先级调度 ：为每个进程分配一个优先级，按优先级进行调度。
  为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级

• 多级反馈队列
  一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。
  多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,…。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合

7. 动态分区分配算法的了解

• 首次适应算法：从低地址开始查找，找到第–个能满足大小的空闲分区。原理：：空闲分区以地址递增的次序排列，每次分配内存时顺序查找
• 最佳适应算法：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区,即，优先使用更小的空闲区。原理：空闲分区按容量递增次序链接。每次分配内存时顺序查找
• 最坏适应算法：为了解决最佳适应算法的问题—即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小。原理：空闲分区按容量递减次序链接，每次分配内存时顺序查找
• 邻近适应算法：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。原理：空闲分区以地址递增的顺序排列(可排成-一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区

总结：

8. Linux下进程间通信方式

• 管道：
  无名管道（内存文件）：管道是一种半双工的通信方式，数据只能单向流动
  有名管道（FIFO文件，借助文件系统）：有名管道也是半双工的通信方式，管道是先进先出的通信方式。
• 共享内存：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多
  个进程都可以访问。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设
  计的。它往往与信号量，配合使用来实现进程间的同步和通信。
• 消息队列：消息队列是有消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 套接字：适用于不同机器间进程通信，在本地也可作为两个进程通信的方式。
• 信号：用于通知接收进程某个事件已经发生，比如按下ctrl + C就是信号。
• 信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，实现进程、线程的对临界区的同步及互斥访问。

9. 几种典型的锁

• 读写锁
  （可以同时进行读）
  写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
  写者优先于读者
• 互斥锁
  一次只能一个线程拥有互斥锁，其他线程只有等待
  互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒，而操作系统负责线程调度，为了实现锁的状态发生改变时唤醒阻塞的线程或者进程，需要把锁交给操作系统管理，所以互斥锁在加锁操作时涉及上下文的切换
• 条件变量（同步）
  互斥锁一个明显的缺点是他只有两种状态：锁定和非锁定
  条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足，他常和互斥锁一起使用，以免出现竞态条件。当条件不满足时，线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。一旦其他的某个线程改变了条件变量，他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说互斥锁是线程间互斥的机制，条件变量则是同步机制。
• 自旋锁
  如果进线程无法取得锁，进线程不会立刻放弃CPU时间片，而是一直循环尝试获取锁，直到获取为止
  如果别的线程长时期占有锁，那么自旋就是在浪费CPU做无用功，但是自旋锁一般应用于加锁时间很短的场景，这个时候效率比较高

10. 地址变换中，有快表和没快表的区别

11. 常见的几种磁盘调度算法

磁盘块的时间的影响因素有：

• 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
• 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
• 实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

1. 先来先服务：按照磁盘请求的顺序进行调度。
   优点：公平
   缺点：未对寻道做任何优化，使平均寻道时间可能较长。
2. 最短寻道时间优先
   优先调度与当前磁头所在磁道距离最近的磁道。
   缺点：不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象
3. 电梯扫描算法
   电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。
   电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。
   因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题

12. 什么叫抖动

如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。通俗的说刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。

原因：进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够)
为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并
发度，降低某些资源的利用率

为了研究为应该为每个进程分配多少个物理块，Denning 提出了进程工作集” 的概念

13. 页面置换算法的了解

• 最佳置换法(OPT)：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率
  最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的
• 先进先出置换算法(FIFO)：每次选择淘汰的页面是最早进入内存的页面
  把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面队列，它最大长度取决于系统为进程分配了多少个内存块
  缺点：先进入的页面也有可能最经常被访问。因此，算法性能差。在FIFO算法下被反复调入和调
  出，并且有抖动现象
• 最近最久未使用置换算法(LRU)：每次淘汰的页面是最近最久未使用的页面
  赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t(该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大)。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。算法开销比较大
• 时钟置换算法(CLOCK)或者叫做或最近未用算法：循环扫描缓冲区像时钟一样转动
  为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰-一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第- - ~轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择–个淘汰页面最多会经过两轮扫描)
• 改进的时钟置换算法：使用访问位和修改位来判断是否置换该页面
  1类(A =0, M = 0)：表示该页面最近既未被访问，又未被修改，是最佳淘汰页。
  2类(A =0, M = 1)：表示该页面最近未被访问，但已被修改，并不是很好的淘汰页。
  3类(A =1, M = 0)：表示该页面最近已被访问，但未被修改，该页有可能再被访问。
  4类(A =1, M = 1)：表示该页最近已被访问且被修改，该页可能再被访问。

总结：

1. 最佳置换算法性OPT能最好，但无法实现；
2. 先进先出置换算法实现简单，但算法性能差；
3. 最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大
4. CLOCK循环扫描各页面 第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。若第二轮没选中，则进行第二轮扫描。实现简单，算法开销小;但未考虑页面是否被修改过。
5. 改进的clock：若用(访问位，修改位)的形式表述，则 第一轮:淘汰(0,0) ，第二轮:淘汰(0,1)，并将扫描过的页面访问位都置为0 ，第三轮:淘汰(0, 0)， 第四轮:淘汰(0, 1)。算法开销较小，性能也不错

14. 死锁是什么

死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，处于僵持状态，没有外力的情况下无法推动

15. 死锁产生条件

四个条件缺一不可

1. 互斥条件：进程对所需求的资源具有排他性，若有其他进程请求该资源，请求进程只能等待。
2. 不剥夺条件：进程在所获得的资源未释放前，不能被其他进程强行夺走，只能自己释放。
3. 请求和保持条件：进程当前所拥有的资源在进程请求其他新资源时，由该进程继续占有。
4. 循环等待条件：存在一种进程资源循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

16. 解决死锁的基本方法

预防死锁

避免死锁

检测死锁

解除死锁

17. 大小端模式

大端模式（Big-Endian）：指的是数据的低位保存在内存的高地址中，而数据的高位保存在内存的低地址中.

小端模式（Little-Endian）：指的是数据的低位保存在内存的低地址中，而数据的高位保存在内存的高地址中