面试题-操作系统

前言

计算机操作系统部分的题目，是我根据Java Guide的面试突击版本V3.0再整理出来的，其中，我选择了一些比较重要的问题，并重新做出相应回答，并添加了一些比较重要的问题，希望对大家起到一定的帮助。

系列文章：

面试题-Java基础

面试题-Java集合

面试题-Java多线程基础、实现工具和可见性保证

操作系统-进程定义/进程切换/进程调度

进程是什么？为什么需要进程？

最开始cpu是串行执行程序的，但是现实中人们更希望能同时运行多个程序，而cpu资源是有限的，如何在物理上有限的cpu上同时运行几百上千个程序呢？操作系统提出了一种虚拟化的概念，通过不断地快速切换运行的程序让使用者觉得自己在同时运行这些程序（时分共享）。既然现在系统中有多个程序都需要运行，就需要一种数据结构来表示运行的程序的状态，然后才能做切换，这种数据结构就是进程。
到底什么构成了进程？（哪些要素构成了运行中的程序状态）
- 进程可以访问的地址空间 --》内存
- 寄存器（PC，栈指针，栈帧指针等等）
- IO信息（当前打开的文件列表等等）
简单说说创建进程的过程？（程序是如何变成进程的）
1. 将代码和静态数据从磁盘加载到内存中
2. 给进程分配栈内存，可能会初始化栈（把main函数的参数填入main函数的栈帧中）
3. 给进程分配堆内存
4. 一些其他的初始化任务，比如IO，每个进程会有三个打开的文件描述符，分别代表标准输入/标准输出/标准错误
进程的状态
系统调用是什么？为什么需要系统调用？

系统调用是操作系统提供给应用程序的针对受限资源的访问接口。

当用户希望访问一些受限的资源时，需要通过系统调用，把控制权交给操作系统来代完成，如果没有系统调用，是无法实现安全可控的在用户程序中访问硬件资源的。**
系统调用是如何实现的?

首先，硬件提供不同的执行模式来实现系统调用

用户模式：用户的程序运行在这个模式，不能完全访问硬件
内核模式：操作系统运行在这个模式，可以访问全部硬件资源

当执行系统调用时，会执行一个特殊的指令 trap 陷入内核模式，那么trap如何知道应该跳转到内核的哪个位置开始执行呢？

在操作系统启动的时候，会初始化一个trap表，记录了当发生系统调用时，硬件应该执行什么代码。

操作系统启动（内核模式）硬件

初始化trap表

记住系统调用处理程序的地址

进程是如何切换的-如何从用户态切换到内核态？

进程需要通过操作系统进行切换，如果操作系统一直不运行，就没法切换。所以想要切换进程，首先需要考虑如何从用户态切换到内核态。现代操作系统使用时钟中断机制来实现从用户态切换到内核态。

简单理解就是一个定时器，每隔一段时间都会产生中断，如果cpu检测到中断，cpu会执行预先设置好的中断处理程序，此时操作系统获得cpu的控制权。
进程是如何切换的-具体的切换过程

每个进程有一个内核栈，当从内核态trap out跳出时，cpu会从给定的内核栈中恢复数据到寄存器。进程切换的过程其实就是操作系统替换了另外的内核栈栈帧给cpu，这样cpu就可以执行另外的程序。
进程是如何调度的？你了解那些调度算法？

研究调度算法，首先需要对工作负载做出一定的假设，并且提出衡量指标，来评价算法的优劣。

操作系统导论中对工作负载做出以下假设：
1. 工作同时到达
2. 工作一旦开始就不会停止（非抢占式）
3. 工作只占用cpu，不做io操作
4. 每个工作的运行时间是已知的
5. 每个工作运行相同的时间
同样的，在该书中，提出了两个重要的指标：
- 周转时间：T_周转时间 = T_完成时间 - T_到达时间
- 响应时间：T_响应时间 = T_{首次执行时间} - T_到达时间
先进先出算法（FIFO）

有ABC三个任务，同时到来，都执行10s，按照如图所示执行

T_{平均周转时间} = （10+20+30）/3 = 20

T_{平均响应时间} = （0+10+20）/3 = 10

现在去掉假设5，让先到来的A执行100s，B和C执行10s

T_{平均周转时间} = （100+110+120）/3 = 110

T_{平均响应时间} = （0+100+110）/3 = 70

结论：在任务执行时间相差较大的场景下，如果按照顺序先执行执行时间较长的任务，会导致周转时间和响应时间显著增大。

最短任务优先（SJF）

在以上假设不变的情况下，任务执行如图，先执行较短的B和C，后执行A

T_{平均周转时间} = （10+20+120）/3 = 50

T_{平均响应时间} = （0+10+20）/3 = 10

结论：SJF在上述假设满足条件下，是优于FIFO算法的。

如果去掉同时到达的假设，A先于B和C10ms到达

和FIFO中的问题类似，平均周转时间和响应时间都会显著增加。

最短完成时间优先（STCF）

现在去掉假设2，可以抢占。

T_{平均周转时间} = （120+10+20）/3 = 50

T_{平均响应时间} = （0+10+20）/3 = 10

结论：STCF在已知任务执行时间的条件下，是目前最好的算法。

轮转算法（RR）

轮转算法是更关注响应时间的算法，在上面的例子中，如果使用轮转算法，每5s切换一次任务,切换任务需要的时间忽略不计。

T_{平均响应时间} = （0+5+5）/3 = 3.3

T_{平均周转时间} = （120+25+30）/3 = 58.33

总体结论： 如果是全cpu任务，并且任务执行时长已知的情况下

如果更关注响应时间，选择RR算法
如果更关注周转时间，选择STCF算法

你了解多级反馈队列吗？

在问题9中，我们研究过在已知任务执行时长的情况下可以选择哪些算法，但是大部分情况我们是不知道任务执行时长的，多级反馈队列更关注任务在运行中的实时表现，针对不同的表现决定后续的处理。

多级反馈队列按照优先级从大到小有多个队列，最开始会假设任务都是交互式的，所以优先级最高。
- 如果在一个时间片内，任务一直没有放弃cpu，代表不是交互式任务，会自动降低优先级到下一队列
- 如果放弃过cpu，代表是交互式任务，就保持优先级不变。
- 如果用完当前队列的累积执行时长就自动降级
cpu会先执行优先级更高的队列中的任务，在同一队列中，使用RR算法来轮转执行。

同时，为了防止饥饿现象，经过一段时间s，将系统中所有任务重新加入最高优先级队列。

操作系统启动（内核模式）	硬件
初始化trap表
	记住系统调用处理程序的地址