目录
一、相关面试题
1. 进程的调度算法有哪些?
调度原则
(1)先来先服务调度算法
(2)最短作业优先调度算法
(3)高响应比优先调度算法
(4)时间片轮转调度算法
(5)最高优先级调度算法
(6)多级反馈队列调度算法
2. 说一说僵尸进程和孤儿进程
(1)孤儿进程
(2)僵尸进程
二、其他问题
1. 什么是中断和异常?它们有什么区别?
(1)中断
(2)异常
(3)区别综述
2. 用户态和核心态
(1)用户态和内核态的区别?
(2)在什么场景下,会发生内核态和用户态的切换?
一、相关面试题
1. 进程的调度算法有哪些?
一旦 操作系统 把进程 切换到 运行状态,也就意味着该 进程 占用着 CPU 在执行,但是当操作系统把进程 切换 到其他状态时,那就不能在 CPU 中执行了,于是 操作系统会 选择 下一个 要运行的 进程。选择一个 进程运行 这一功能是在 操作系统 中完成的,通常称为调度程序(scheduler)。
在进程的生命周期中,当进程从一个运行状态到另外一状态变化的时候,都会触发一次调度。如;
- 从就绪态 -> 运行态:当进程被 创建时,会进入到 就绪队列,操作系统会 从就绪队列 选择一个进程 运行;
- 从运行态 -> 阻塞态:当进程发生 I/O 事件 而阻塞时,操作系统 必须选择 另外一个 进程运行;
- 从运行态 -> 结束态:当进程 退出结束后,操作系统得从 就绪队列 选择另外一个 进程运行;
如果 硬件时钟 提供 某个频率的 周期性中断,那么 可以 根据 如何处理 时钟中断,把调 度算法 分为两类:
- 非抢占式调度算法:挑选一个进程,然后 让该进程 运行 直到被阻塞,或者 直到 该进程 退出,才会 调用 另外一个 进程,也就是说 不会理时钟中断 这个事情。
- 抢占式调度算法:挑选一个进程,然后 让该进程 只运行 某段时间,如果 在该时段结束时,该进程 仍然在 运行时,则会把它 挂起,接着 调度程序 从就绪队列 挑选另外一个 进程。这种 抢占式调度处理,需要 在时间间隔的 末端 发生时钟中断,以便 把 CPU 控制 返回给 调度程序 进行调度,也就是常说的 时间片机制。
调度原则
- CPU 利用率:调度程序应 确保 CPU 是 始终匆忙的 状态,这可提高 CPU 的 利用率;
- 系统吞吐量:吞吐量 表示的是 单位时间内 CPU 完成 进程的数量,长作业的 进程会 占用 较长的 CPU 资源,因此会 降低 吞吐量,相反,短作业的 进程会 提升 系统吞吐量;
- 周转时间:周转时间是 进程运行+阻塞时间+等待时间的 总和,一个进程的 周转时间 越小越好;
- 等待时间:这个 等待时间 不是阻塞状态的 时间,而是 进程 处于 就绪队列的 时间,等待的 时间越长,用户 越不满意;
- 响应时间:用户 提交请求 到系统 第一次 产生响应 所花费的 时间,在 交互式 系统中,响应时间是 衡量 调度算法 好坏 的主要标准。
(1)先来先服务调度算法
非抢占式的 先来先服务(First Come First Serve, FCFS)算法。
每次 从 就绪队列 选择 最先进入队列 的进程,然后 一直运行,直到 进程退出 或被 阻塞,才会继续 从队列中 选择 第一个 进程 接着运行。
当一个 长作业 先运行了,那么 后面的 短作业 等待的时间 就会很长,不利于 短作业。FCFS 对长作业有利,适用于 CPU 繁忙型 作业的 系统,而 不适用于 I/O 繁忙型作业的系统。
(2)最短作业优先调度算法
最短作业优先(Shortest Job First, SJF)调度算法会 优先选择 运行时间最短 的 进程来运行,这有助于 提高系统的 吞吐量。
这显然对长作业不利,很容易造成一种极端现象。
比如,一个 长作业 在就绪队列 等待运行,而这个 就绪队列有 非常多的短作业,那么就会 使得 长作业 不断的 往后推,周转时间变长,致使 长作业 长期不会被运行。
(3)高响应比优先调度算法
上述「先来先服务调度算法」和「最短作业优先调度算法」都没有很好的 权衡 短作业和长作业。
高响应比优先(Highest Response Ratio Next, HRRN)调度算法 主要是 权衡了 短作业和长作业。每次 进行 进程调度时,先计算「响应比优先级」,然后把「响应比优先级」最高的 进程 投入运行,「响应比优先级」的计算公式:
从上面的公式,可以发现:
- 如果两个进程的「等待时间」相同时,「要求的服务时间」越短,「响应比」就越高,这样 短作业的进程 容易 被选中运行;
- 如果 两个进程「要求的服务时间」相同时,「等待时间」越长,「响应比」就越高,这就 兼顾 到了长作业 进程,因为 进程的响应比 可以 随时间等待的增加 而提高,当其 等待时间 足够长时,其 响应比 便可以 升到很高,从而 获得运行 的机会;
(4)时间片轮转调度算法
最古老、最简单、最公平且 使用最广的算法 就是 时间片轮转(Round Robin, RR)调度算法。
每个进程被分配一个时间段,称为 时间片(Quantum),即 允许 该进程在 该时间段中 运行。
- 如果 时间片 用完,进程 还在运行,那么 将会 把此进程从 CPU 释放出来,并把 CPU 分配给另外一个进程;
- 如果 该进程在时间片 结束前 阻塞或结束,则 CPU 立即 进行切换;
关于 时间片的长度:
- 如果时间片设得太短会导致过多的进程上下文切换,降低了 CPU 效率;
- 如果设得太长又可能引起对短作业进程的响应时间变长。
一般来说,时间片设为 20ms~50ms 通常是一个比较合理的折中值。
(5)最高优先级调度算法
「时间片轮转算法」做了个假设,即 让所有的 进程 同等重要,运行时间都一样。但是,对于多用户 计算机系统 希望调度 是有优先级的,即 希望调度程序 能 从就绪队列中 选择 最高优先级的 进程进行运行,这称为 最高优先级(Highest Priority First, HPF)调度算法。
进程的优先级可以分为,静态优先级和动态优先级:
- 静态优先级:创建进程时候,就已经确定了优先级了,然后 整个运行时间 优先级 都不会变化;
- 动态优先级:根据 进程的 动态变化 调整优先级,比如 如果进程 运行 时间增加,则 降低其 优先级,如果 进程 等待时间(就绪队列的 等待时间)增加,则升高其 优先级,也就是 随着时间的 推移 增加 等待进程的 优先级。
该算法也有 两种 处理优先级高的 方法,非抢占式和抢占式:
- 非抢占式:当 就绪队列中 出现优先级高的 进程,运行完 当前进程,再 选择优先级高的 进程。
- 抢占式:当 就绪队列中 出现 优先级高的 进程,当前进程 挂起,调度 优先级高 的 进程运行。但是 依然有 缺点,可能会导致 低优先级的 进程永远不会运行。
(6)多级反馈队列调度算法
多级反馈队列(Multilevel Feedback Queue) 调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。
- 「多级」:表示有多个队列,每个队列 优先级 从高到低,同时 优先级越高 时间片越短。
- 「反馈」:表示 如果 有新的进程 加入优先级高的 队列时,立刻 停止当前 正在运行的 进程,转而去 运行优先级高的 队列。
它是如何工作的:
- 设置了 多个队列,赋予 每个队列不同的 优先级,每个队列 优先级 从高到低,同时 优先级 越高时间片越短;
- 新的进程会 被放入到 第一级队列的 末尾,按 先来先服务的 原则 排队 等待被调度,如果在 第一级队列 规定的 时间片 没运行完成,则 将其 转入到 第二级队列的 末尾,以此类推,直至完成;
- 当 较高优先级的 队列为空,才 调度 较低优先级 的队列中的 进程运行。如果 进程运行时,有 新进程 进入 较高优先级的 队列,则 停止当前 运行的 进程 并将其 移入到 原队列 未尾,接着让 较高优先级的 进程运行;
可以发现,对于 短作业 可能可以在 第一级 队列很快被处理完。对于长作业,如果在 第一级 队列处理 不完,可以 移入 下次队列 等待 被执行,虽然 等待的时间 变长了,但是 运行时间 也变 更长了,所以 该算法 很好的兼顾了 长短作业,同时有 较好的 响应时间。
- 银行设置了 多个排队(就绪)队列,每个队列 都有不同的 优先级,各个队列 优先级 从高到低,同时 每个队列 执行时间片的长度也不同,优先级 越高的 时间片越短。
- 新客户(进程)来了,先进入 第一级 队列的 未尾,按 先来先服务 原则 排队等待 被叫号(运行)。如果 时间片 用完客户的 业务 还没办理完成,则让 客户进入到 下一级队列的 末尾,以此类推,直至 客户业务 办理完成。
- 当 第一级队列 没人排队 时,就会 叫号 二级队列的 客户。如果 客户办理业务 过程中,有新的 客户加入 到较高 优先级的 队列,那么 此时 办理中的 客户需要 停止办理,回到 原队列的 末尾 等待再次叫号,因为 要把 窗口让给 刚进入 较高优先级队列的 客户。
可以发现,对于 要办理短业务的 客户来说,可以 很快的 轮到并解决。对于 要办理 长业务的客户,一下子解决不了,就可以 放到下一个 队列,虽然 等待的 时间稍微 变长了,但是 轮到自己的办理时间 也变长了,也可以接受,不会造 成极端的现象,可以说是综合上面几种算法的优点。
2. 说一说僵尸进程和孤儿进程
(1)孤儿进程
一个 父进程 退出,而 它的 一个 或 多个 子进程 还在运行,那么那些 子进程 将成为 孤儿进程。孤儿进程 将被 init 进程(进程号 为 1)所 收养,并由 init 进程 对它们 完成 状态收集 工作。
(2)僵尸进程
一个 进程 使用 fork 创建 子进程,如果 子进程 退出,而 父进程 并没有 调用 wait(阻塞) 或 waitpid(非阻塞) 获取 子进程的 状态 信息,那么 子进程 的 进程描述符 仍然 保存在 系统中。这种 进程 称之为 僵尸进程。
二、其他问题
1. 什么是中断和异常?它们有什么区别?
中断和异常都会 导致处理器 暂停 当前正在执行的 任务,并 转向 执行一个 特定的 处理程序(中断处理程序 或 异常处理程序)。然后 在处理完 这些特殊情况 后,处理器 会返回 到被打断的 任务继续执行。
(1)中断
中断 是由 计算机系统 外部事件触发的,通常 与硬件设备 相关。中断的 目的是 为了 及时 响应 重要事件 而暂时 中断正常的 程序执行。典型的 中断 包括 时钟中断、I/O 设备中断(如 键盘输入、鼠标事件)和 硬件错误中断等。
操作系统 通常会 为每种类型的 中断 分配一个 中断处理程序,用于 处理相应的事件。
(2)异常
异常 是由 计算机系统 内部事件触发的,通常 与正在执行的 程序或指令 有关,比如 程序的 非法操作码、地址越界、运算溢出等 错误引起的 事件,异常 不能被 屏蔽,当出现异常时,计算机系统会 暂停正常的 执行流程,并 转到 异常处理程序 来处理 该异常。
(3)区别综述
- 中断 是由 外部设备 或 其他 处理器 产生的,它们 通常是 异步的,也就是 说,它们 可以 在 任何时候 发生,与 当前 执行的 指令无关。例如,键盘输入、鼠标移动、网络数据 到达 等 都会 产生 中断信号,通知 CPU 去处理 这些 事件。
- 异常是 由 CPU 内部 产生的,它们 通常是 同步的,也就是说,它们 只会在 执行 某些 指令时发生,与 当前 执行的 指令有关。例如,除法运算时 除数为零、访问 非法 内存地址、执行 非法指令等 都会 产生 异常信号,通知 CPU 去处理 这些 错误 或 故障。
- 中断 可以 被屏蔽 或 禁止,这 意味着 CPU 可以 通过 设置 某些标志位 或 寄存器 来 忽略 或 延迟响应 某些 中断信号。这样 可以避免 中断过于 频繁 或 干扰 重要的 任务。
- 异常 不能 被 屏蔽 或 禁止,这 意味着 CPU 必须 立即 响应异常信号,并 进行相应的 处理。这样可以 保证程序的 正确性 和 系统的 稳定性。
2. 用户态和核心态
(1)用户态和内核态的区别?
用户态 (user Mode)和 内核态(Kernel Mode) 是操作系统 为了 保护系统资源 和 实现 权限控制 而设计的 两种不同的 CPU 运行级别,可以 控制进程 或 程序 对 计算机硬件资源的 访问权限 和 操作范围。
- 用户态:在用户态下,进程 或 程序 只能 访问受限的 资源 和 执行受限的 指令集,不能 直接访问 操作系统的 核心部分,也不能 直接访问 硬件资源。
- 核心态:核心态是 操作系统的 特权级别,允许 进程 或 程序执行 特权指令 和 访问操作系统的 核心部分。在核心态下,进程 可以 直接访问 硬件资源,执行 系统调用,管理内存、文件系统等 操作。
(2)在什么场景下,会发生内核态和用户态的切换?
- 系统调用:当用户程序 需要请求 操作系统 提供的服务 时,会 通过 系统调用 进入内核态。
- 异常:当 程序执行过程中 出现错误 或 异常情况 时,CPU 会自动 切换到 内核态,以便 操作系统能够 处理 这些异常。
- 中断:外部设备(如键盘、鼠标、磁盘等)产生的 中断信号 会使 CPU 从用户态 切换到 内核态。操作系统会 处理这些 中断,执行 相应的 中断处理 程序,然后再 将 CPU 切换回 用户态。