操作系统常见面试问题


Author: yifei / Created: Aug. 3, 2018, 12:16 a.m. / Modified: Aug. 3, 2018, 9:28 a.m. / Edit

Linux 内核进程调度算法

linux内核将进程分成两个级别:普通进程和实时进程。实时进程的优先级都高于普通进程,除此之外,它们的调度策略也有所不同。

实时进程

Linux 并不能做到硬实时,只能实现软实时。实时进程在 Linux 中不会被抢占调度,只要开始执行之后,除非主动让出 CPU,否则会一直执行。内核也不会更改实时进程的优先级,而是由进程指定。如果有多个可以执行的实时线程,内核会直接选取优先级搞得线程来执行。

只要高优先级的实时进程一直处于可执行状态,低优先级的实时进程就一直不能得到CPU;只要一直有实时进程处于可执行状态,普通进程就一直不能得到CPU。

当有多个优先级相同的实时进程需要调度的时候,有两种调度方法可以选择:

  1. SCHED_FIFO:先进先出。直到先被执行的进程变为非可执行状态,后来的进程才被调度执行。在这种策略下,先来的进程可以行sched_yield系统调用,自愿放弃CPU,以让权给后来的进程;
  2. SCHED_RR:轮转调度。内核为实时进程分配时间片,在时间片用完时,让下一个进程使用CPU;

普通进程

和实时进程调度不同的是,Linux 内核会调整普通进程的优先级。用户设定的优先级被称为静态优先级,内核会在运行过程中动态生成一个动态优先级。

大名鼎鼎的 O(1) 调度器

  1. 在linux 2.4时,可执行状态的进程被挂在一个链表中。每次调度,调度程序需要扫描整个链表,以找出最优的那个进程来运行。复杂度为O(n);
  2. 在linux 2.6早期,可执行状态的进程被挂在N(N=140)个链表中,每一个链表代表一个优先级,系统中支持多少个优先级就有多少个链表。每次调度,调度程序只需要从第一个不为空的链表中取出位于链表头的进程即可。这样就大大提高了调度程序的效率,复杂度为O(1);
  3. 在linux 2.6近期的版本中,可执行状态的进程按照优先级顺序被挂在一个红黑树(可以想象成平衡二叉树)中。每次调度,调度程序需要从树中找出优先级最高的进程。复杂度为O(logN)。

O(1) 调度器虽好,但是优先级只有固定的几个,所以最终还是被换成了红黑树,O(logn) 和 O(1) 的差距还是很小的。

触发调度的时机

  1. 进程主动进入不可执行状态。比如 sleep,或者进行 IO 等
  2. 抢占。也就是时间片用完了。
  3. 处理中断的过程中,其实抢占也可以理解为处理时间中断。

优先级继承

优先级高的进程 A 需要访问的临界区资源被 B 持有,但是 B 又被优先级稍高的 C 抢占,导致 A 不得不等待比它优先级更低的进程 C。这被称为优先级翻转。解决方法是采用优先级继承,当A开始等待B退出临界区时,则 B 可临时继承 A 的优先级,以防被 C 抢占。

内核如何保证每个进程都有执行机会?

进程的动态优先级在随着进程的执行不断降低

自旋锁

一般的锁在等待的时候都会被挂起,然后系统调度另一个线程执行。而如果临界区比较小,这时候挂起再执行就没有必要了。这时候可以使用自旋锁,不断检测锁是否被释放。

内核抢占

内核可以被抢占,但是也可以打开不可抢占的标志。

多核调度

每个处理器都有自己的调度队列,但是每个进程只能出现在一个队列中。一个进程被同一个核心更有可能命中缓存,从而提高性能。

进程和线程的区别?

这个问题也只有在校招面试才会问吧,太简单了

内核态和用户态的区别

系统调用分为三个阶段

参数准备阶段。 系统调用识别阶段。 系统调用执行阶段。 在参数准备阶段,需要使用系统服务的程序将系统调用所需要的参数,如上述例子中的 fd,buffer,nbytes,压到栈上。然后调用库函数read。库函数read将系统调用read的代码放在一个约定好的寄存器里,通过陷入 (trap,一种中断方式)将控制交给操作系统。由此进入到第二个阶段。操作系统获得控制后,将系统调用代码从寄存器里取出,与操作系统维护的一张系统调 用表进行比较,获得系统调用read的程序体所在的内存地址。之后跳到该地址,进入到第三个阶段,执行系统调用函数。系统调用执行完毕后返回到用户程序。

实模式和保护模式

1:实模式

是CPU启动的时候的模式 这时候就相当于一个速度超快的8086 不能使用多线程 不能实现权限分级 还不能访问20位以上地址线,也就是说只能访问1M内存 BIOS加载Bootloader(GRUB)

2:保护模式

操作系统接管CPU后. 会使CPU进入保护模式. 这时候可以发挥80x86的所有威力. 包括权限分级、内存分页、等等等等各种功能

参考资料

  1. linux进程调度浅析
  2. Linux 调度器发展简述
  3. Linux CGroup 调度

有任何问题可以发邮件到 kongyifei (at) gmail.com 讨论