问题整理自cyc大佬的专栏。

推荐付费阅读他的其他文章，很有收获。另外大佬的GitHub内容也非常有用。

部分答案整理自网络，点击蓝字可以查看原链接。蓝字都是可以点进去的。

面试的主要内容：

本文主要整理操作系统及Linux的常见问题。

一 操作系统

1 ★★★ 进程与线程的本质区别、以及各自的使用场景。

进程：

程序并不能单独运行，只有将程序装载到内存中，系统为它分配资源才能运行，而这种执行的程序就称之为进程。程序和进程的区别就在于：程序是指令的集合，它是进程运行的静态描述文本；进程是程序的一次执行活动，属于动态概念。

在多道编程中，我们允许多个程序同时加载到内存中，在操作系统的调度下，可以实现并发地执行。这是这样的设计，大大提高了CPU的利用率。进程的出现让每个用户感觉到自己独享CPU，因此，进程就是为了在CPU上实现多道编程而提出的。

进程不足：

  • 进程只能在一个时间干一件事，如果想同时干两件事或多件事，进程就无能为力了。

  • 进程在执行的过程中如果阻塞，例如等待输入，整个进程就会挂起，即使进程中有些工作不依赖于输入的数据，也将无法执行。

因为要并发，我们发明了进程，又进一步发明了线程。只不过进程和线程的并发层次不同：进程属于在处理器这一层上提供的抽象；线程则属于在进程这个层次上再提供了一层并发的抽象。还可以有效地利用多处理器和多核计算机。

区别：

  • 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。
  • 线程是进程的一个实体, 是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。
  • 一个线程可以创建和撤销另一个线程，同一个进程中的多个线程之间可以并发执行。
  • 线程缺乏访问控制，进程中的一个线程出错，会终止掉整个进程。
  • 切换的效率，复杂度也不同。

2 ★☆☆ 进程状态

  • 创建状态：进程在创建时需要申请一个空白PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建工作无法完成，比如资源无法满足，就无法被调度运行，把此时进程所处状态称为创建状态
  • 就绪状态：进程已经准备好，已分配到所需资源，只要分配到CPU就能够立即运行
  • 执行状态：进程处于就绪状态被调度后，进程进入执行状态
  • 阻塞状态：正在执行的进程由于某些事件（I/O请求，申请缓存区失败）而暂时无法运行，进程受到阻塞。在满足请求时进入就绪状态等待系统调用
  • 终止状态：进程结束，或出现错误，或被系统终止，进入终止状态。无法再执行

如果进程运行时间片使用完也会进入就绪状态。 
另外为用户观察需要，进程还有挂起和激活两种操作。挂起后进程处于静止状态进程不再被系统调用，对于操作是激活操作。
 

3 ★★★ 进程调度算法的特点以及使用场景。优缺点比较。

先来先去服务(FCFS: first come first service) ： 总是把当前处于就绪队列之首的那个进程调度到运行状态。

非抢占式 

  • 优点：有利于长作业以及CPU繁忙的作业
  • 缺点：不利于短作业以及I/O繁忙的作业

短作业(进程)优先调度算法SJ(P)F：对预计执行时间短的作业（进程）优先分派处理机.通常后来的短作业不抢先正在执行的作业.

  • 优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；
  • 缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。

轮转法（RR调度算法）：让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。属于抢占式调度。优点是兼顾长短作业；缺点是平均等待时间较长，上下文切换较费时。适用于分时系统。

优先级调度算法（HPF）：在进程等待队列中选择优先级最高的来执行。常被用于批处理系统中，还可用于实时系统中。

多级反馈队列算法：设置多个就绪队列，分别赋予不同的优先级

高响应比优先调度算法：根据“响应比=（进程执行时间+进程等待时间）/ 进程执行时间”这个公式得到的响应比来进行调度。高响应比优先算法在等待时间相同的情况下，作业执行的时间越短，响应比越高，满足段任务优先，同时响应比会随着等待时间增加而变大，优先级会提高，能够避免饥饿现象。优点是兼顾长短作业，缺点是计算响应比开销大，适用于批处理系统。

3 ★☆☆ 线程实现的方式

待补充

4 ★★☆ 协程的作用

协程是进程和线程的升级版,进程和线程都面临着内核态和用户态的切换问题而耗费许多切换时间,
而协程就是用户自己控制切换的时机,不再需要陷入系统的内核态。
协程的执行效率非常高。因为子程序切换不是线程切换，而是由程序自身控制。因此，没有线程切换的开销，和多线程相比，线程数量越多，相同数量的协程体现出的优势越明显
不需要多线程的锁机制。由于只有一个线程，也不存在同时写变量的冲突，在协程中控制共享资源不需要加锁，只需要判断数据的状态，所以执行效率远高于线程 ，对于多核CPU可以使用多进程+协程来尽可能高效率地利用CPU。

5 ★★☆ 常见进程同步问题。

生产者与消费者问题 

问题描述：一组生产者进程和一组消费者进程共享一块初始为空，大小确定的缓冲区，该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。常采用进程间通信的方法解决该问题，

问题分析：生产者与消费者进程对缓冲区的访问是互斥关系，而生产者与消费者本身又存在同步关系，即必须生成之后才能消费。因而对于缓冲区的访问设置一个互斥量，再设置两个信号量一个记录空闲缓冲区单元，一个记录满缓冲区单元来实现生产者与消费者的同步。

读者与写者问题

问题描述：有读者与写者两个并发进程共享一个数据，两个或以上的读进程可以访问数据，但是一个写者进程访问数据与其他进程都互斥。

问题分析：读者与写者是互斥关系，写者与写者是互斥关系，读者与读者是同步关系。因而需要一个互斥量实现读与写和写与写互斥，一个读者的访问计数和实现对计数的互斥。

哲学家就餐问题

问题描述：一张圆桌上坐着五名哲学家，每两名哲学家之间的桌子摆一根筷子，哲学家只有同时拿起左右两根筷子时才可以用餐，用餐完了筷子放回原处。

问题分析：这里五名哲学家就是五个进程，五根筷子是需要获取的资源。可以定义互斥数组用于表示五根筷子的互斥访问，为了防止哲学家个取一根筷子出现死锁，需要添加一定的限制条件。一种方法是限制仅当哲学家左右筷子均可以用时，才拿起筷子，这里需要一个互斥量来限制获取筷子不会出现竞争。

问题解决：一次仅能一个哲学家拿起筷子，效率比较低。

6 ★★★ 进程通信方法的特点以及使用场景

管道（包括无名管道和命名管道）、消息队列、信号量、共享存储、Socket、Streams等。其中 Socket和Streams支持不同主机上的两个进程IPC。

无名管道：

  • 它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。
  • 它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）。
  • 它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。

FIFO，也称为命名管道，它是一种文件类型。类似于在进程中使用文件来传输数据，只不过FIFO类型文件同时具有管道的特性。在数据读出时，FIFO管道中同时清除数据，并且“先进先出”。

  • FIFO可以在无关的进程之间交换数据，与无名管道不同。

  • FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。

 消息队列：是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。

  • 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。

  • 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。

  • 消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。

信号量：是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

  • 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。

  • 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。

  • 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。

  • 支持信号量组。

共享内存（Shared Memory）：指两个或多个进程共享一个给定的存储区。

  • 共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。

  • 因为多个进程可以同时操作，所以需要进行同步。

  • 信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

总结：

  • 管道：速度慢，容量有限，只有父子进程能通讯    
  • FIFO：任何进程间都能通讯，但速度慢    
  • 消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题    
  • 信号量：不能传递复杂消息，只能用来同步    
  • 共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存
     

7 ★★★ 死锁必要条件、解决死锁策略，能写出和分析死锁的代码，能说明在数据库管理系统或者 Java 中如何解决死锁。

死锁是指两个或两个以上的进程（线程）在运行过程中因争夺资源而造成的一种僵局（Deadly-Embrace) ) ，若无外力作用，这些进程（线程）都将无法向前推进。

互斥条件，不可剥夺条件，请求与保持条件，循环等待条件

  • 处理方法：预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。
  • 避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态。有序资源分配法，银行家算法
  • 检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。
  • 解除死锁：当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。

8 ★★★ 虚拟内存的作用，分页系统实现虚拟内存原理。

虚拟内存是计算机系统内存管理的一种技术。 它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。 目前，大多数操作系统都使用了虚拟内存，如Windows家族的“虚拟内存”；Linux的“交换空间”等。对虚拟内存的定义是基于对地址空间的重定义的，即把地址空间定义为“连续的虚拟内存地址”，以借此“欺骗”程序，使它们以为自己正在使用一大块的“连续”地址。

虚拟内存的实现有以下三种方式： 

  • 请求分页存储管理。 
  • 请求分段存储管理。 
  • 请求段页式存储管理。 

请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。

在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。

为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址变换机构。

9 ★★★ 页面置换算法的原理，特别是 LRU 的实现原理，最好能手写，再说明它在 Redis 等作为缓存置换算法。

  • 最佳置换算法（OPT）（理想置换算法）：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。
  • 先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。 
  • 最近最久未使用（LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。 

算法特点：（链接有实现代码）

a.FIFO，Optimal，LRU这三种置换算法的优劣？

优点：

  • FIFO页面置换算法实现简单，要求的硬件支持较少。
  • Optimal页面置换算法可保证获得最低的缺页率，并且可以用来评价其他算法。
  • LRU页面置换算法利用“最近的过去”代替“最近的将来”，以此模拟Optimal算法，是实际应用中缺页率最低的算法。

缺点：

  • FIFO算法所依据的条件是各个页面调入内存的时间，而页面调入内存的先后并不能反映页面的使用情况。
  • Optimal算法是理论上的算法，目前该算法是无法实现的。
  • LRU算法是根据各页以前的使用情况，来代替各页面将来的使用情况，进而判断要替换出去的页面，而页面过去和将来的走向之间并无必然的联系；其实际应用时要求较多的硬件支持，因而多采用近似算法。

b. 在什么情况下采用哪种置换算法更有利？

  • FIFO算法在按线性顺序访问地址空间时使用；当硬件水平不足时，FIFO算法也可作为首选。
  • OPT算法可以进行模拟实验分析或理论分析。
  • 当系统有寄存器或栈的硬件支持时，利用LRU算法可以获得最低缺页率。

在Redis中LRU算法是一个近似算法，默认情况下，Redis随机挑选5个键，并且从中选取一个最近最久未使用的key进行淘汰.

10 ★★★ 比较分页与分段的区别。

  • 页是信息的物理单位，分页是为了实现离散分配方式，以消减内存的外零头，提高内存的利用率。分页仅仅是由于系统管理的需要而不是用户的需要；段是信息的逻辑单位，分段的目的是为了能更好地满足用户的需要
  • 页的大小固定，由系统把逻辑地址划分为页号和页内地址两部分，段的长度却不固定，决定于用户所编写的程序
  • 分页的作业地址空间是一维的，即单一的线性地址空间。 分段的作业地址空间是二维的 在标识一个地址时，即需给出段名，又需给出段内地址

11 ★★★ 分析静态链接的不足，以及动态链接的特点

静态链接库的优点 

  •   代码装载速度快，执行速度略比动态链接库快； 
  •   只需保证在开发者的计算机中有正确的.LIB文件，在以二进制形式发布程序时不需考虑在用户的计算机上.LIB文件是否存在及版本问题，可避免DLL地狱等问题。 

动态链接库的优点 

  •  更加节省内存并减少页面交换；
  •   DLL文件与EXE文件独立，只要输出接口不变（即名称、参数、返回值类型和调用约定不变），更换DLL文件不会对EXE文件造成任何影响，因而极大地提高了可维护性和可扩展性；
  •  不同编程语言编写的程序只要按照函数调用约定就可以调用同一个DLL函数；
  •  适用于大规模的软件开发，使开发过程独立、耦合度小，便于不同开发者和开发组织之间进行开发和测试。

各自不足之处

  •  使用静态链接生成的可执行文件体积较大，包含相同的公共代码，造成浪费；
  •  使用动态链接库的应用程序不是自完备的，它依赖的DLL模块也要存在，如果使用载入时动态链接，程序启动时发现DLL不存在，系统将终止程序并给出错误信息。而使用运行时动态链接，系统不会终止，但由于DLL中的导出函数不可用，程序会加载失败；速度比静态链接慢。当某个模块更新后，如果新模块与旧的模块不兼容，那么那些需要该模块才能运行的软件，统统撕掉。这在早期Windows中很常见。

二 Linux

1 ★★☆ 文件系统的原理，特别是 inode 和 block。数据恢复原理。

在LINUX系统中有一个重要的概念：一切都是文件。 

 

Linux正统的文件系统(如ext2、ext3)一个文件由目录项、inode和数据块组成。

  • 目录项:包括文件名和inode节点号。
  • Inode：又称文件索引节点，是文件基本信息的存放地和数据块指针存放地。
  • 数据块：文件的具体内容存放地。

当查看某个文件时，会先从inode table中查出文件属性及数据存放点，再从数据块中读取数据。

inode与block：

  • inode：中文译名为"索引节点"。记录文件的属性，一个文件占用一个inode，同时记录此文件的数据所在的 block 号码；Unix/Linux系统内部不使用文件名，而使用inode号码来识别文件。对于系统来说，文件名只是inode号码便于识别的别称或者绰号。
  • block：实际记录文件的内容，若文件太大时，会占用多个 block 。block由一个或多个sector（扇区）组成，文件系统中最小的操作单位；OS的虚拟文件系统从硬件设备上读取一个block，实际为从硬件设备读取一个或多个sector。对于文件管理来说，每个文件对应的多个block可能是不连续的;

数据恢复：

Ext3/Ext4文件系统下数据删除后的恢复原理就是根据日志文件残留inode信息来恢复，由于日志文件大小有限，不可能记录下大量文件操作过程中产生的记录。

（FAT32）文件的删除很简单，只是把DIR区文件的第一个字符改为E5（常规删除，如果你用软件覆盖了，就不是如此了，数据也不能恢复了）这也就是说，文件的数据并没有被覆盖，也就为为恢复创造了可能。
ps：任何数据能恢复的前提是，这个要恢复的数据没有被新写入的数据覆盖。

2 ★★★ 硬链接与软链接的区别。

为解决文件的共享使用，Linux 系统引入了两种链接：硬链接 (hard link) 与软链接。

硬链接（hard link）

我们可以将它理解为一个“指向原始文件inode的指针”，系统不为它分配独立的inode和文件。所以，硬链接文件与原始文件其实是同一个文件，只不过是不同的名字而已。我们每添加一个硬链接，该文件的inode链接数就会增加1；而且只有当该文件的inode连接数为0时，才算彻底将它删除。换言之，由于硬链接实际上是指向原文件的inode的指针，因此即便原始文件被删除，依然可以通过硬链接文件来访问。

总结起来有以下几点：

  • 硬链接，以文件副本的形式存在。但不占用实际空间。
  • 不允许给目录创建硬链接
  • 硬链接只有在同一个文件系统中才能创建

软连接（也称为符号链接[symbolic link]）

软链接仅仅包含所链接文件的路径名，因此能链接目录文件，也可以跨越文件系统进行链接。但是，当原始文件被删除后，链接文件也将失效，从这一点上来说与Windows系统中的“快捷方式”具有一样的性质。

总结起来有以下几点：

  • 软链接，以路径的形式存在。类似于Windows操作系统中的快捷方式
  • 软链接可以跨文件系统 ，硬链接不可以
  • 软链接可以对一个不存在的文件名进行链接
  • 软链接可以对目录进行链接
     

3 ★★☆ 能够使用常用的命令，比如 cat 文件内容查看、find 搜索文件，以及 cut、sort 等管线命令。了解 grep 和 awk 的作用。

Linux grep命令用于查找文件里符合条件的字符串。

awk是一种处理文本文件的语言，是一个强大的文本分析工具。

参看菜鸟教程Linux命令大全：https://www.runoob.com/linux/linux-command-manual.html

 

4 ★★★ 僵尸进程与孤儿进程的区别，从 SIGCHLD 分析产生僵尸进程的原因。

在unix/linux中，正常情况下，子进程是通过父进程创建的，子进程在创建新的进程。子进程的结束和父进程的运行是一个异步过程,即父进程永远无法预测子进程 到底什么时候结束。 当一个 进程完成它的工作终止之后，它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态。

  • 孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
  • 僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。

僵尸进程产生原因：在子进程终止后到父进程调用wait()前的时间里，子进程被称为zombie；具体：

  • 子进程结束后向父进程发出SIGCHLD信号，父进程默认忽略了它
  • 父进程没有调用wait()或waitpid()函数来等待子进程的结束
  • 网络原因有时会引起僵尸进程；

防止僵尸进程：

  • 让僵尸进程成为孤儿进程，由init进程回收；(手动杀死父进程)
  • 调用fork()两次；
  • 捕捉SIGCHLD信号，并在信号处理函数中调用wait函数；

涉及到操作系统及Linux的部分先写到这儿，每一部分想详细了解都可以点蓝字。下一篇分析数据库与计算机网络的问题。

( ^_^ )/~~拜拜