操作系统面试指南

写在前面

校招在即，着手准备操作系统方面的面试。因为大二下学期学习了操作系统，所以对知识的理解还算深刻，只是一些细节忘记了，在这里重新梳理一下。

本文部分内容转自：JavaGuide面试指南

操作系统基础

什么是操作系统？

• 操作系统本质上是一个运行在计算机上的软件程序 ，用于管理计算机硬件和软件资源。
• 操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。

什么是系统调用？

介绍系统调用之前，我们先来了解一下用户态和系统态。

根据进程访问资源的特点，我们可以把进程在系统上的运行分为两个级别：

• 用户态：用户态运行的进程可以直接读取用户程序的数据
• 系统态：系统态运行的进程几乎可以访问计算机的任何资源，不受限制

说了用户态和系统态之后，那么什么是系统调用呢？

我们运行的程序基本都是在用户态上的，如果我们想调用操作系统提供的系统态级别的子功能咋办呢？那就需要系统调用了。

我们在运行的用户程序中，凡是与系统态级别的资源有关的操作（如文件管理、进程控制、进程通信、内存管理，设备管理等），都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

这些系统调用大致可分为如下几类：

• 设备管理：完成设备的请求与释放，以及设备启动等功能。
• 文件管理：完成文件的读、写、创建及删除等功能。
• 进程控制：完成进程的创建、撤销、阻塞以及唤醒功能
• 进程通信：完成进程之间的消息传递或信号传递等功能
• 内存管理：完成内存分配、回收以及获取作业占用内存区大小及地址等功能

进程和线程

进程和线程的区别

线程是进程划分的更小的运行单位，一个进程在其执行期间可以产生多个线程。线程和进程最大的区别在于基本上各进程是独立的，而各线程则不一定，因为同一进程中的线程极有可能会相互影响。线程执行开销小，但不利于资源的管理和保护。进程恰恰相反。

按石林老师的话来讲，进程是资源分配的最小单位，线程是CPU调度的最小单位。但是捏，CPU它也算资源吧，那这句话这么说就不太对了。石老师破天荒的提出了，进程是资源分配的最小单位，线程是时间分配的最小单位。

进程有哪几种状态？

进程的状态和线程的状态很相似，我们一般把他分为五态，考研还细分出了七态，我说真变态。

• 创建状态：进程正在被创建，尚未到就绪状态。
• 就绪状态：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源（处理器分配时间片）即可运行
• 阻塞状态：又称为等待状态，进程正在等待某一件事件而暂停运行，如等待某资源为可用或等待IO操作完成。即使处理器空闲，该进程也不能运行。
• 结束状态：进程正在从系统中消失。可能是进程正常结束或者其他原因中断退出运行。

进程间通信的方式

大概有七种常见的进程通信方式：

• 管道/匿名管道（Pipes）：用于具有亲缘关系的父子进程间或兄弟进程间的通信
  • 有名管道（Names Pipes）：匿名管道由于没有名字，只能用于亲缘关系的进程通信。为了克服这个缺点，提出了有名管道。有名管道严格遵循先进先出。有名管道以磁盘文件的形式存在，可以实现本机任意两个进程通信。
• 信号：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已发生。
• 消息队列：消息队列是消息的链表，具有特定的格式，存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出原则。与管道不同的是消息队列存放在内核中，只有在内核重启（操作系统重启），或者显示的删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取，也可以按消息的类型读取。比FIFO更有优势。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点
• 信号量：信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。
• 共享内存：使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有用的进程间通信方式。
• 套接字（socket）：此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持TCP/IP的网络通信的基本操作单元，可以看作是不同主机之间的进程进行双向通信的端点，简单点说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。

线程间的同步方式

线程同步是两个或多个共享关键资源的线程的并发执行。应该同步线程以避免关键资源的使用冲突。操作系统一般有下面三种线程的同步方式：

• 互斥量：采用互斥对象机制，只有拥有互斥对象的进程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如Java中的synchronized关键词和各种Lock都是这种机制。
• 信号量：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程量。
• 事件：Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程的优先级的比较操作。

进程的调度算法

• 先到先服务调度算法（FCFS）：从就绪队列中选择一个最先进入该队列的进程为之分配资源，使他立即执行并一直执行到完成或发生某件事而被阻塞放弃占用CPU时再重新调度。
• 短作业优先（SJF）调度算法：从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使他立即执行并一直执行到完成或发生某件事而被阻塞放弃占用CPU时再重新调度。
• 时间片轮转调度算法：时间片轮转调度是一种最古老，最简单，最公平且使用最广的一种算法。又称RR调度，每个进程被分配一个时间段，称作他为时间片，即该进程允许运行的时间。
• 多级反馈队列调度算法：多级反馈队列调度算法既能使高优先级作业得到响应又能使短作业迅速完成。因而它是目前被公认的一种较好的进程调度算法,UNIX操作系统采取的便是多级反馈队列调度算法。

什么是死锁？

多个进程/线程同时被阻塞，他们中的一个或者全部都在等待某个资源被释放。由于进程/线程被无限期的阻塞，因此程序不可能正常终止。

死锁的四个条件

• 互斥：资源必须处于非共享模式，既一次只有一个进程可以使用。如果另一进程申请该资源，那么必须等待直到该资源被释放为止。
• 占有并等待：一个进程至少应该占有一个资源，并等待另一资源，而该资源被其他进程占有。
• 非抢占：资源不能被抢占。只能在持有资源的进程完成任务后，该资源才会被释放，
• 循环等待：顾名思义

注意，以上四点必须同时成立！

解决死锁的方法

解决死锁的方法可以从多个角度去分析，一般的情况下，有预防，避免，检测和解除四种。

• 预防 是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间上都不满足。
• 避免则是系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生
• 检测是指系统设有专门的机构，当死锁发生时，该机构能够检测死锁的发生，并精确地确定与死锁有关的进程和资源。
• 解除 是与检测相配套的一种措施，用于将进程从死锁状态下解脱出来。

死锁的预防

死锁四大必要条件上面都已经列出来了，只要破坏四个必要条件中的任何一个就能够预防死锁的发生。

• 破坏第一个条件 互斥条件：有很多资源 往往是不能同时访问的 ，所以这种做法在大多数的场合是行不通的。
• 破坏第三个条件 非抢占 ：剥夺式调度算法，会导致 资源利用率下降。

所以一般比较实用的 预防死锁的方法，是通过考虑破坏第二个条件和第四个条件。

1、静态分配策略（破坏占用并等待）

静态分配策略可以破坏死锁产生的第二个条件（占有并等待）。所谓静态分配策略，就是指一个进程必须在执行前就申请到它所需要的全部资源，并且知道它所要的资源都得到满足之后才开始执行。进程要么占有所有的资源然后开始执行，要么不占有资源，不会出现占有一些资源等待一些资源的情况。

2、层次分配策略（破坏循环等待）

层次分配策略破坏了产生死锁的第四个条件(循环等待)。在层次分配策略下，所有的资源被分成了多个层次，一个进程得到某一次的一个资源后，它只能再申请较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源，按这种策略，是不可能出现循环等待链的，因为那样的话，就出现了已经申请了较高层的资源，反而去申请了较低层的资源，不符合层次分配策略。

死锁的避免（银行家算法）

上面提到的 破坏 死锁产生的四个必要条件之一就可以成功 预防系统发生死锁 ，但是会导致 低效的进程运行 和 资源使用率 。而死锁的避免相反，它的角度是允许系统中同时存在四个必要条件 ，只要掌握并发进程中与每个进程有关的资源动态申请情况，做出 明智和合理的选择 ，仍然可以避免死锁，因为四大条件仅仅是产生死锁的必要条件。

我们将系统的状态分为 安全状态 和 不安全状态 ，每当在未申请者分配资源前先测试系统状态，若把系统资源分配给申请者会产生死锁，则拒绝分配，否则接受申请，并为它分配资源。

那么如何保证系统保持在安全状态呢？通过算法，其中最具有代表性的 避免死锁算法 就是 Dijkstra 的银行家算法，银行家算法用一句话表达就是：当一个进程申请使用资源的时候，银行家算法 通过先 试探 分配给该进程资源，然后通过 安全性算法 判断分配后系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待，若能够进入到安全的状态，则就 真的分配资源给该进程。

A：已分配资源 N：所需资源 M：需求

M-A=N 用剩余资源去比较每个进程此时的N，看是否可以满足，如果可以，释放此进程的M，可用资源就+M，再进行比较。如果都可以妥善解决，那此刻系统就是安全状态。

死锁的避免(银行家算法)改善解决了 资源使用率低的问题 ，但是它要不断地检测每个进程对各类资源的占用和申请情况，以及做 安全性检查 ，需要花费较多的时间。

死锁的检测

对资源的分配加以限制可以 预防和避免 死锁的发生，但是都不利于各进程对系统资源的充分共享。解决死锁问题的另一条途径是 死锁检测和解除 。这种方法对资源的分配不加以任何限制，也不采取死锁避免措施，但系统 定时地运行一个 “死锁检测” 的程序，判断系统内是否出现死锁，如果检测到系统发生了死锁，再采取措施去解除它

真相

说了这么多，实际上对于操作系统而言，对于死锁采用的是鸵鸟策略。埋头不管，最为高效。