操作系统必知的面试题

解释一下什么是操作系统

操作系统是运行在计算机上最重要的一种软件,它管理计算机的资源和进程以及所有的硬件和软件。它为计算机硬件和软件提供了一种中间层

通常情况下,计算机上会运行着许多应用程序,它们都需要对内存和 CPU 进行交互,操作系统的目的就是为了保证这些访问和交互能够准确无误的进行。

解释一下操作系统的主要目的是什么

操作系统是一种软件,它的主要目的有三种

  • 管理计算机资源,这些资源包括 CPU、内存、磁盘驱动器、打印机等。
  • 提供一种图形界面,就像我们前面描述的那样,它提供了用户和计算机之间的桥梁。
  • 为其他软件提供服务,操作系统与软件进行交互,以便为其分配运行所需的任何必要资源。

操作系统的种类有哪些

操作系统通常预装在你购买计算机之前。大部分用户都会使用默认的操作系统,但是你也可以升级甚至更改操作系统。但是一般常见的操作系统只有三种:Windows、macOS 和 Linux

操作系统结构

单体系统

在大多数系统中,整个系统在内核态以单一程序的方式运行。整个操作系统是以程序集合来编写的,链接在一块形成一个大的二进制可执行程序,这种系统称为单体系统。

在单体系统中构造实际目标程序时,会首先编译所有单个过程(或包含这些过程的文件),然后使用系统链接器将它们全部绑定到一个可执行文件中

在单体系统中,对于每个系统调用都会有一个服务程序来保障和运行。需要一组实用程序来弥补服务程序需要的功能,例如从用户程序中获取数据。可将各种过程划分为一个三层模型

除了在计算机初启动时所装载的核心操作系统外,许多操作系统还支持额外的扩展。比如 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 端口,并声称一个内核调用,这样就完成了一次调用过程。

客户-服务器模式

微内核思想的策略是把进程划分为两类:服务器,每个服务器用来提供服务;客户端,使用这些服务。这个模式就是所谓的 客户-服务器模式。

客户-服务器模式会有两种载体,一种情况是一台计算机既是客户又是服务器,在这种方式下,操作系统会有某种优化;但是普遍情况下是客户端和服务器在不同的机器上,它们通过局域网或广域网连接。

客户通过发送消息与服务器通信,客户端并不需要知道这些消息是在本地机器上处理,还是通过网络被送到远程机器上处理。对于客户端而言,这两种情形是一样的:都是发送请求并得到回应。

什么是按需分页

在操作系统中,进程是以页为单位加载到内存中的,按需分页是一种虚拟内存的管理方式。在使用请求分页的系统中,只有在尝试访问页面所在的磁盘并且该页面尚未在内存中时,也就发生了缺页异常,操作系统才会将磁盘页面复制到内存中。

多处理系统的优势

随着处理器的不断增加,我们的计算机系统由单机系统变为了多处理系统,多处理系统的吞吐量比较高,多处理系统拥有多个并行的处理器,这些处理器共享时钟、内存、总线、外围设备等。

多处理系统由于可以共享资源,因此可以开源节流,省钱。整个系统的可靠性也随之提高。

什么是内核

在计算机中,内核是一个计算机程序,它是操作系统的核心,可以控制操作系统中所有的内容。内核通常是在 boot loader 装载程序之前加载的第一个程序。

这里还需要了解一下什么是 boot loader

boot loader 又被称为引导加载程序,它是一个程序,能够将计算机的操作系统放入内存中。在电源通电或者计算机重启时,BIOS 会执行一些初始测试,然后将控制权转移到引导加载程序所在的主引导记录(MBR)

什么是实时系统

实时操作系统对时间做出了严格的要求,实时操作系统分为两种:硬实时和软实时

硬实时操作系统规定某个动作必须在规定的时刻内完成或发生,比如汽车生产车间,焊接机器必须在某一时刻内完成焊接,焊接的太早或者太晚都会对汽车造成永久性伤害。

软实时操作系统虽然不希望偶尔违反最终的时限要求,但是仍然可以接受。并且不会引起任何永久性伤害。比如数字音频、多媒体、手机都是属于软实时操作系统。

你可以简单理解硬实时和软实时的两个指标:是否在时刻内必须完成以及是否造成严重损害

什么是虚拟内存

虚拟内存是一种内存分配方案,是一项可以用来辅助内存分配的机制。我们知道,应用程序是按页装载进内存中的。但并不是所有的页都会装载到内存中,计算机中的硬件和软件会将数据从 RAM 临时传输到磁盘中来弥补内存的不足。如果没有虚拟内存的话,一旦你将计算机内存填满后,计算机会对你说

呃,不,对不起,您无法再加载任何应用程序,请关闭另一个应用程序以加载新的应用程序。对于虚拟内存,计算机可以执行操作是查看内存中最近未使用过的区域,然后将其复制到硬盘上。虚拟内存通过复制技术实现了 妹子,你快来看哥哥能装这么多程序 的资本。复制是自动进行的,你无法感知到它的存在。

什么是进程和进程表

进程就是正在执行程序的实例,比如说 Web 程序就是一个进程,shell 也是一个进程,文章编辑器 typora 也是一个进程。

操作系统负责管理所有正在运行的进程,操作系统会为每个进程分配特定的时间来占用 CPU,操作系统还会为每个进程分配特定的资源。

操作系统为了跟踪每个进程的活动状态,维护了一个进程表。在进程表的内部,列出了每个进程的状态以及每个进程使用的资源等。

http://courses.cs.vt.edu/csonline/OS/Lessons/Processes/index.html 这个网站上面有一个关于进程状态轮转的动画,做的真是太好了。

什么是线程,线程和进程的区别

这又是一道老生常谈的问题了,从操作系统的角度来回答一下吧。

我们上面说到进程是正在运行的程序的实例,而线程其实就是进程中的单条流向,因为线程具有进程中的某些属性,所以线程又被称为轻量级的进程。浏览器如果是一个进程的话,那么浏览器下面的每个 tab 页可以看作是一个个的线程。

下面是线程和进程持有资源的区别

线程不像进程那样具有很强的独立性,线程之间会共享数据

创建线程的开销要比进程小很多,因为创建线程仅仅需要堆栈指针程序计数器就可以了,而创建进程需要操作系统分配新的地址空间,数据资源等,这个开销比较大。

使用多线程的好处是什么

多线程是程序员不得不知的基本素养之一,所以,下面我们给出一些多线程编程的好处

  • 能够提高对用户的响应顺序
  • 在流程中的资源共享
  • 比较经济适用
  • 能够对多线程架构有深入的理解

什么是 RR 调度算法

RR(round-robin) 调度算法主要针对分时系统,RR 的调度算法会把时间片以相同的部分并循环的分配给每个进程,RR 调度算法没有优先级的概念。这种算法的实现比较简单,而且每个线程都会占有时间片,并不存在线程饥饿的问题。

导致系统出现死锁的情况

死锁的出现需要同时满足下面四个条件

  • 互斥(Mutual Exclusion):一次只能有一个进程使用资源。如果另一个进程请求该资源,则必须延迟请求进程,直到释放该资源为止。
  • 保持并等待(Hold and Wait):必须存在一个进程,该进程至少持有一个资源,并且正在等待获取其他进程当前所持有的资源。
  • 无抢占(No Preemption):资源不能被抢占,也就是说,在进程完成其任务之后,只能由拥有它的进程自动释放资源。
  • 循环等待(Circular Wait) :必须存在一组 {p0,p1,….. pn} 的等待进程,使 p0 等待 p1 持有的资源,p1 等待由 p2 持有的资源, pn-1 正在等待由 pn 持有的资源,而 pn 正在等待由 p0 持有的资源。

RAID 的不同级别

RAID 称为 磁盘冗余阵列,简称 磁盘阵列。利用虚拟化技术把多个硬盘结合在一起,成为一个或多个磁盘阵列组,目的是提升性能或数据冗余。

RAID 有不同的级别

  • RAID 0 – 无容错的条带化磁盘阵列
  • RAID 1 – 镜像和双工
  • RAID 2 – 内存式纠错码
  • RAID 3 – 比特交错奇偶校验
  • RAID 4 – 块交错奇偶校验
  • RAID 5 – 块交错分布式奇偶校验
  • RAID 6 – P + Q冗余

什么是 DMA

DMA 的中文名称是直接内存访问,它意味着 CPU 授予 I/O 模块权限在不涉及 CPU 的情况下读取或写入内存。也就是 DMA 可以不需要 CPU 的参与。这个过程由称为 DMA 控制器(DMAC)的芯片管理。由于 DMA 设备可以直接在内存之间传输数据,而不是使用 CPU 作为中介,因此可以缓解总线上的拥塞。DMA 通过允许 CPU 执行任务,同时 DMA 系统通过系统和内存总线传输数据来提高系统并发性。

多线程编程的好处是什么

对不起,我忍不住想偷笑

说直白点,为什么单线程能够处理的却要用多线程来处理?当然是为了提高程序的装逼并行能力了。多线程在某些情况下能够使你程序运行的更快,这也是为什么多核 CPU 会出现,但是多核 CPU 的出现会导致数据的一致性问题,不过这些问题程序员就能解决。另一个角度来说,多线程编程能够提高程序员的编程能力和编程思维。同时也能提高程序员的管理能力,你如果把每条线程流当作罗老师时间管理的女主一样,能够及时协调好所有P友的关系,那你也是超神程序员了,所以,是谁说程序员不会做管理的?Doug Lea 大佬牛逼!!!

ps:Doug Lea 大佬开发的 JUC 工具包,此处不加狗头。

什么是设备驱动程序

在计算机中,设备驱动程序是一种计算机程序,它能够控制或者操作连接到计算机的特定设备。驱动程序提供了与硬件进行交互的软件接口,使操作系统和其他计算机程序能够访问特定设备,不用需要了解其硬件的具体构造。

进程间的通信方式

通信概念

进程间的通信方式比较多,首先你需要理解下面这几个概念

  • 竞态条件:即两个或多个线程同时对一共享数据进行修改,从而影响程序运行的正确性时,这种就被称为竞态条件(race condition)

  • 临界区:不仅共享资源会造成竞态条件,事实上共享文件、共享内存也会造成竞态条件、那么该如何避免呢?或许一句话可以概括说明:禁止一个或多个进程在同一时刻对共享资源(包括共享内存、共享文件等)进行读写。换句话说,我们需要一种 互斥(mutual exclusion) 条件,这也就是说,如果一个进程在某种方式下使用共享变量和文件的话,除该进程之外的其他进程就禁止做这种事(访问统一资源)。

    一个好的解决方案,应该包含下面四种条件

    1. 任何时候两个进程不能同时处于临界区
    2. 不应对 CPU 的速度和数量做任何假设
    3. 位于临界区外的进程不得阻塞其他进程
    4. 不能使任何进程无限等待进入临界区

  • 忙等互斥:当一个进程在对资源进行修改时,其他进程必须进行等待,进程之间要具有互斥性,我们讨论的解决方案其实都是基于忙等互斥提出的。

解决方案

进程间的通信用专业一点的术语来表示就是 Inter Process Communication,IPC,它主要有下面几种通信方式

  • 消息传递:消息传递是进程间实现通信和同步等待的机制,使用消息传递,进程间的交流不需要共享变量,直接就可以进行通信;消息传递分为发送方和接收方
  • 先进先出队列:先进先出队列指的是两个不相关联进程间的通信,两个进程之间可以彼此相互进程通信,这是一种全双工通信方式
  • 管道:管道用于两个相关进程之间的通信,这是一种半双工的通信方式,如果需要全双工,需要另外一个管道。
  • 直接通信:在这种进程通信的方式中,进程与进程之间只存在一条链接,进程间要明确通信双方的命名。
  • 间接通信:间接通信是通信双方不会直接建立连接,而是找到一个中介者,这个中介者可能是个对象等等,进程可以在其中放置消息,并且可以从中删除消息,以此达到进程间通信的目的。
  • 消息队列:消息队列是内核中存储消息的链表,它由消息队列标识符进行标识,这种方式能够在不同的进程之间提供全双工的通信连接。
  • 共享内存:共享内存是使用所有进程之间的内存来建立连接,这种类型需要同步进程访问来相互保护。

进程间状态模型

cat chapter1 chapter2 chapter3 | grep tree

第一个进程是 cat,将三个文件级联并输出。第二个进程是 grep,它从输入中选择具有包含关键字 tree 的内容,根据这两个进程的相对速度(这取决于两个程序的相对复杂度和各自所分配到的 CPU 时间片),可能会发生下面这种情况,grep 准备就绪开始运行,但是输入进程还没有完成,于是必须阻塞 grep 进程,直到输入完毕。

当一个进程开始运行时,它可能会经历下面这几种状态

图中会涉及三种状态

  1. 运行态,运行态指的就是进程实际占用 CPU 时间片运行时
  2. 就绪态,就绪态指的是可运行,但因为其他进程正在运行而处于就绪状态
  3. 阻塞态,除非某种外部事件发生,否则进程不能运行

逻辑上来说,运行态和就绪态是很相似的。这两种情况下都表示进程可运行,但是第二种情况没有获得 CPU 时间分片。第三种状态与前两种状态不同的原因是这个进程不能运行,CPU 空闲时也不能运行。

三种状态会涉及四种状态间的切换,在操作系统发现进程不能继续执行时会发生状态1的轮转,在某些系统中进程执行系统调用,例如 pause,来获取一个阻塞的状态。在其他系统中包括 UNIX,当进程从管道或特殊文件(例如终端)中读取没有可用的输入时,该进程会被自动终止。

转换 2 和转换 3 都是由进程调度程序(操作系统的一部分)引起的,进程本身不知道调度程序的存在。转换 2 的出现说明进程调度器认定当前进程已经运行了足够长的时间,是时候让其他进程运行 CPU 时间片了。当所有其他进程都运行过后,这时候该是让第一个进程重新获得 CPU 时间片的时候了,就会发生转换 3。

程序调度指的是,决定哪个进程优先被运行和运行多久,这是很重要的一点。已经设计出许多算法来尝试平衡系统整体效率与各个流程之间的竞争需求。

当进程等待的一个外部事件发生时(如从外部输入一些数据后),则发生转换 4。如果此时没有其他进程在运行,则立刻触发转换 3,该进程便开始运行,否则该进程会处于就绪阶段,等待 CPU 空闲后再轮到它运行。

调度算法都有哪些

调度算法分为三大类:批处理中的调度、交互系统中的调度、实时系统中的调度

批处理中的调度

先来先服务

很像是先到先得。。。可能最简单的非抢占式调度算法的设计就是 先来先服务(first-come,first-serverd)。使用此算法,将按照请求顺序为进程分配 CPU。最基本的,会有一个就绪进程的等待队列。当第一个任务从外部进入系统时,将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时,它们排到就绪队列尾部。当正在运行的进程阻塞,处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时,它会像一个新到达的任务,会排在队列的末尾,即排在所有进程最后。

这个算法的强大之处在于易于理解和编程,在这个算法中,一个单链表记录了所有就绪进程。要选取一个进程运行,只要从该队列的头部移走一个进程即可;要添加一个新的作业或者阻塞一个进程,只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。

不过,先来先服务也是有缺点的,那就是没有优先级的关系,试想一下,如果有 100 个 I/O 进程正在排队,第 101 个是一个 CPU 密集型进程,那岂不是需要等 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行,这在实际情况下根本不可能,所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。

最短作业优先

批处理中,第二种调度算法是 最短作业优先(Shortest Job 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 将得到 90 % 的 CPU 时间,而用户 2 将之得到 10 % 的 CPU 时间。

为了阻止这种情况的出现,一些系统在调度前会把进程的拥有者考虑在内。在这种模型下,每个用户都会分配一些CPU 时间,而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证,那么无论一个用户有多少个进程,都将获得相同的 CPU 份额。

页面置换算法都有哪些

算法 注释
最优算法 不可实现,但可以用作基准
NRU(最近未使用) 算法 和 LRU 算法很相似
FIFO(先进先出) 算法 有可能会抛弃重要的页面
第二次机会算法 比 FIFO 有较大的改善
时钟算法 实际使用
LRU(最近最少)算法 比较优秀,但是很难实现
NFU(最不经常食用)算法 和 LRU 很类似
老化算法 近似 LRU 的高效算法
工作集算法 实施起来开销很大
工作集时钟算法 比较有效的算法
  • 最优算法在当前页面中置换最后要访问的页面。不幸的是,没有办法来判定哪个页面是最后一个要访问的,因此实际上该算法不能使用。然而,它可以作为衡量其他算法的标准。
  • NRU 算法根据 R 位和 M 位的状态将页面氛围四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现,但是性能不是很好。存在更好的算法。
  • FIFO 会跟踪页面加载进入内存中的顺序,并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面,因此这个算法也不是一个很好的选择。
  • 第二次机会算法是对 FIFO 的一个修改,它会在删除页面之前检查这个页面是否仍在使用。如果页面正在使用,就会进行保留。这个改进大大提高了性能。
  • 时钟 算法是第二次机会算法的另外一种实现形式,时钟算法和第二次算法的性能差不多,但是会花费更少的时间来执行算法。
  • LRU 算法是一个非常优秀的算法,但是没有特殊的硬件(TLB)很难实现。如果没有硬件,就不能使用 LRU 算法。
  • NFU 算法是一种近似于 LRU 的算法,它的性能不是非常好。
  • 老化 算法是一种更接近 LRU 算法的实现,并且可以更好的实现,因此是一个很好的选择
  • 最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销,但是它的实现比较复杂。WSClock 是另外一种变体,它不仅能够提供良好的性能,而且可以高效地实现。

最好的算法是老化算法和WSClock算法。他们分别是基于 LRU 和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法,但实际上这两个可能是最重要的。

影响调度程序的指标是什么

会有下面几个因素决定调度程序的好坏

  • CPU 使用率:

CPU 正在执行任务(即不处于空闲状态)的时间百分比。

  • 等待时间

这是进程轮流执行的时间,也就是进程切换的时间

  • 吞吐量

单位时间内完成进程的数量

  • 响应时间

这是从提交流程到获得有用输出所经过的时间。

  • 周转时间

从提交流程到完成流程所经过的时间。

什么是僵尸进程

僵尸进程是已完成且处于终止状态,但在进程表中却仍然存在的进程。僵尸进程通常发生在父子关系的进程中,由于父进程仍需要读取其子进程的退出状态所造成的。