【OS】操作系统笔记——进程概述与进程调度

今天开始复习操作系统啦,没想到两个月前看的书现在记忆就没有那么清晰了,赶紧抓起来复习一下。

进程概述

程序就是一些存储在磁盘上的指令,它本身没有生命周期,只是存在于磁盘上的指令。通过操作系统,可以将这些指令运行起来,从而让程序发挥作用,这些正在运行的程序实际上就是进程。

进程实际上是操作系统为正在运行的程序提供的一种抽象。操作系统通过时分复用实现在有限个物理 CPU 的基础上,提供无数个 CPU 可用的假象,从而使得在同一个 CPU 上,看似可以『同时』运行多个进程。关于这个进程的切换策略,则取决于具体的进程调度策略。

运行

操作系统要运行一个程序,从而将其转变为一个进程,主要是经过如下的步骤:

  1. 将代码和静态数据加载到内存。这个过程在早期的操作系统中是尽早完成的,而在现代操作系统中往往是懒加载的。
  2. 为程序的运行时栈以及堆分配一些内存。
  3. 执行一些其他初始化任务,如 UNIX 中会打开 3 个文件操作符,用于输入、输出、报错。
  4. 在入口处,也就是 main() 函数处运行程序。

进程状态

进程的状态可以分为下面三种:

  • 运行(running):表示进程正在处理器上运行。
  • 就绪(ready):表示进程已经准备好运行。
  • 阻塞(blocked):一个进程执行了某些操作,直到发生其他事件才准备运行,如进行了 I/O 请求等。

用户态与内核态

为了对进程的行为进行一些控制,因此引入了一种『用户态与内核态』的机制,

用户进程往往运行在用户态下,在用户态下运行的代码会受到限制,如不能发出 I/O 请求等等,如果执行了某些受限的操作会引发异常。

而操作系统往往运行在内核态下,它可以做它想做的任何事,包括 I/O 请求、执行受限的指令等。

系统调用(System call)

当用户进程想要执行如 I/O 操作的特权操作时,可以通过操作系统提供的系统调用(System call)实现,为了执行系统调用,则程序需要执行陷入(trap)指令,它会使得进程陷入内核态,并提高其权限,可以执行所需的操作。当执行完成后,操作系统通过陷阱返回(return-from-trap)指令返回到用户态,降低权限。

陷阱表(Trap table)

进程陷入内核态后调用的具体代码的地址取决于操作系统维护的一个陷阱表(Trap table),从而避免用户进程可以跳转到任何想要调用的位置。

操作系统启动的时候,它会告诉硬件在发生某些异常事件的时候执行哪些代码,也就是一些陷阱处理程序的位置。通过这样可以对陷阱表进行配置。

进程的切换

当进程在一个 CPU 上运行的时候,就意味着操作系统将控制权交给了进程,那操作系统该如何取回自己的控制权呢?

通过系统调用

在一些早期的操作系统中,操作系统信任进程会合理运行,进程需要主动调用一个系统调用,从而将控制权交还给操作系统。

但这样对某些恶意进程来说,就可以不断地占用资源而不再将控制权交还给操作系统,此时操作系统无能为力。

操作系统进行控制

为了解决这个问题,操作系统利用了一个硬件的特性:时钟中断

时钟设备会被编程为每几毫秒产生一次中断,每当产生中断,当前的进程都会停止,操作系统配置的中断处理程序会被执行。此时操作系统就重新获得了控制权,可以对进程进行调度,继续当前进程或启动其他的进程。

上下文切换

在进行进程之间的切换的时候,操作系统会执行上下文切换(Context Switch),它会将当前执行的进程中一些寄存器的值进行保存(比如保存到操作系统的内核栈),并对将要切换的进程的寄存器的值进行恢复(比如从操作系统的内核栈进行恢复)。

进程上下文的切换往往是由一些底层汇编代码实现,将通用寄存器、程序计数器、当前正在运行的进程的内核栈指针等信息进行保存。

Linux 中的进程

Linux 系统中,使用了一个名为 task_struct 的结构体来描述进程,将进程存放在了一个 task_list双向循环链表中。

Linux 中的进程主要有以下的几种状态:

  • TASK_RUNNING(运行):表示进程是可执行的。它可能正在执行或正在队列中等待。这种状态是用户空间执行的进程的唯一可能状态。
  • TASK_INTERRUPTIBLE(可中断):表示进程正在睡眠(被阻塞),当某些条件达成后,它又会被设置为运行状态。此状态的进程会因为收到信号而提前被唤醒并随时准备投入运行。
  • TASK_UNINTERRUPTIBLE(不可中断):表示即使接收到信号也不回被唤醒或准备投入运行。通常在进程必须等待不被干扰或等待事件很快发生时出现,较少使用。
  • _TASK_TRACED(被跟踪):表示该进程被其他进程跟踪(如 ptrace 指令)
  • _TASK_STOPPED(停止):进程停止执行,没有投入运行也不能投入运行。它发生在接收到 SIGSTOPSIGSTP 等信号时。

进程调度

操作系统需要通过一定的进程调度策略,对不同进程之间进行调度,从而使得各进程可以以最高效的形式执行,从而有效利用资源

调度指标

进程调度的性能需要通过某些调度指标进行衡量,主要有以下的指标:

  • 周转时间:周转时间是指进程从到达到完成所花的时间,它的计算方法为进程的完成时间减去进程的到达时间。T周转 = T完成 - T到达。我们应尽量使得周转时间短,往往用于衡量批处理系统
  • 响应时间:响应时间是指进程从到达到首次运行的时间,它的计算方法为进程的首次运行时间剪去进程的到达时间。T响应 = T运行 - T到达。我们应尽量使得响应时间短,往往用于衡量分时系统

先进先出 FIFO

很简单也是很容易想到的一种方式就是 FIFO 算法, A、B、C 依次到达,A、B、C 需要等到前面的进程完成后才能执行。

这样看似很公平,但如果 A 是一个非常耗时的进程,就意味着 B、C 需要等待其执行完毕,导致周转时间过长。

最短任务进程 SJF

当所有进程同时到达时,SJF 会选择其中最短的一个进程去执行。这样当 A、B、C 同时到达时,它会选择其中最短的 B 或 C 进行执行。

但事实往往没有那么理想,进程随时可能到达,如果时间花费较长的进程 A 先到达,而 B、C 随后到达,则 B、C 仍然需要等待 A 执行完成后才能执行。

最短完成时间优先 STCF

STCF 与 SJF 的思想相似,只是它引入了抢占的机制。当 B、C 到达后,操作系统会使 B、C 抢占进程 A,从而使得 B、C 先执行。

轮转 RR

虽然最短完成时间优先可以使得周转时间尽量的短,但这样的方式无法使得响应时间尽可能短,因此我们可以采用轮转的方式实现。

时间被划分为了一段段时间片,每个时间片内运行一个进程,之后切换到下一个进程,反复执行直到所有进程全部完成。

轮转使得响应时间表现不错,不过进程的切换需要带来上下文的切换的开销,因此时间片长度是需要权衡一下的,不能过长也不能过短。

多级反馈队列 MLFQ

多级反馈队列这种方式,一方面优化了周转时间,一方面带来了响应时间的降低,它会根据进程的运行情况动态地对调度顺序进行调整。

在 MLFQ 中维护了多个队列,每个队列具有不同的优先级。每个进程只能存在于其中的一个队列。而 MLFQ 在调度时总是执行优先级更高的进程。在相同优先级的队列中采用轮转的方式进行调度

它的优先级的调整是根据每个进程的具体表现而决定的。每个进程初始情况下优先级都是位于最高优先级。在进程运行的过程中,对于非常频繁的进行 I/O 操作的进程,它的优先级会更高(I/O 密集型)。而对于长时间占用 CPU 的进程,其优先级会更低(CPU 密集型)

通过对时间片的利用情况可以对其 I/O 操作的密集程度进行判断。当进程耗尽了其时间片,则其优先级会被降低(长时间执行为 CPU 密集型)

但如果此时我们有太多交互型的高优先级进程,则有可能导致 CPU 不断被占用,低优先级进程永远无法得到 CPU 的使用权(饿死)。因此 MLFQ 每经过一个固定时间 S,就会将所有进程重新加入高优先级队列

同时,MLFQ 还支持了不同队列可变的时间片长度,高优先级队列的时间片更短,而低优先级队列的时间片更长

总结下来可以归纳为如下的五点规则:

  1. A 优先级 > B 优先级,运行 A。
  2. A 优先级 = B 优先级,轮转运行 A、B。
  3. 进程默认情况下在高优先级。
  4. 当进程耗尽其对应时间片,降低其优先级。
  5. 每经过一段时间 S,将所有进程重新放入高优先级队列。

比例份额

比例份额的核心思想非常简单:确保每个进程获得一定比例的 CPU 时间

例如 A、B 两个进程,假设 A 占有 25% 的比例,B 占有 75% 的比例,则操作系统不断定时从 0-99 中抽取一个数,如果它在 0-74 之间则运行 A,否则运行 B。通过这种随机的方式可以以非常快的速度决定下一个调度的进程。

同时还可以支持转让机制,让 A 进程将自己的份额临时转让给 B,从而让 B 更频繁的被调度。

这种比例份额机制的实现非常简单,只需要维护一个链表来放置进程,当获取到随机数后根据链表一个个往下找直到遇到需要执行的进程即可。

多处理器调度

CPU 缓存

在单 CPU 系统中存在着多级的硬件缓存,这些缓存可以让处理器更快执行进程,它们相比内存更小但访问速度更快。

缓存主要是依赖于局部性这种理论而被设计的。

  • 时间局部性指如果数据被访问后,则它在不久的将来将会再次被访问。
  • 空间局部性则是指如果访问了地址为 x 的数据,则可能接着访问 x 周围的数据。

通过这种局部性,硬件很容易判断哪些数据应当被加入缓存。

缓存一致性

由于 CPU 缓存的存在,因此存在着一种缓存一致性的问题:比如假设进程 A 运行在 CPU1 上,当修改了其中变量 D 的值为 D‘,由于写回内存比较慢,因此此时往往是将 CPU1 上该值的缓存修改为了 D’,之后再进行写回内存。但如果此时操作系统对该进程进行了中断,该进程被交给了 CPU2,此时 CPU2 从内存中读取到的值仍然为 D,这就是缓存一致性问题。

硬件会对这种缓存一致性的问题进行解决,例如通过总线窥探,每个缓存都监听缓存和内存的总线来发现内存的访问。

虽然硬件对缓存提供了一致性,但我们开发时仍然需要对同步问题进行关心。

例如多个 CPU 对一个共享的数据结构的访问,仍然需要在对该数据结构访问时进行加锁,否则无法保证这个数据结构状态更新的原子性。

缓存亲和度

缓存亲和度主要描述了对缓存的利用程度。

多 CPU 下还存在着一种缓存亲和度不足的问题:当一个进程在某 CPU 上运行时,会在这个 CPU 的缓存中维护很多它的状态,下次可以通过获取这些缓存的数据而更快执行,而当这个进程在多个 CPU 上运行时,由于需要重新加载数据,会导致速度变慢。

单队列调度 SQMS

对于多处理器系统的调度程序,可以选择简单复用单处理器系统的基本架构,将所有需要调度的进程放入同一个队列。

这种方式非常简单,但有着如下的几个缺点:

  1. 存在性能问题,由于该队列是几个 CPU 共享,因此需要在访问队列时进行加锁,加锁会带来性能损失,特别是 CPU 多时造成的对锁的竞争。

  2. 缓存亲和性,例如假设有 5 个进程,4 个 CPU,则每个进程会依次执行一个时间片,然后选择下一个进程。可能会有如下图的调度顺序,这样就会导致每个工作在 4 个 CPU 之间不断转移,与缓存亲和度的目的背道而驰。

    image-20191228141205788

多队列调度 MQMS

多队列调度的方案会采用多个调度队列,如每个 CPU 一个队列等。

每个调度队列可以采用不同的调度算法,当进程执行后,系统会根据一些规则放入某个队列(如随机或根据队列情况),每个 CPU 之间相互独立,避免了单队列由于数据共享和同步带来的问题。

它相比 SQMS 有着更好的可扩展性,并且具有良好的缓存亲和度,任务都保持在固定的 CPU 中,可以很好的利用缓存数据。

但多队列调度存在着一种负载不均的问题,进程较少的 CPU 对应队列中的进程所获得的 CPU 时间更多,而进程较多的 CPU 对应队列中的进程所获得的 CPU 时间就相对较少了。此时可以通过迁移的方式将较多进程的队列中的进程迁移部分至进程较少的队列中,从而使得负载均衡。

Linux 进程调度

Linux 采用了抢占式多任务系统,由调度程序来决定什么时候停止一个进程的运行,进程被抢占前所能运行的时间被叫做时间片。

2.4 版本及以前的Linux调度程序都是十分简陋的,在 2.5 中引入了一种新的调度程序—— O(1) 调度器,解决了之前的许多不足。但它对于响应时间敏感的程序走很大的不足,因此在 2.6.23 版本中,被 CFS (完全公平调度算法)所替代。

通常来说,I/O 密集型进程需要需要高频且短暂的调度策略(即时性高),而 CPU 密集型的进程则需要调度时间长而调度频率低的调度策略(即时性低)。Linux 为了保证交互式应用的性能,会更倾向于调度 I/O 密集型的进程,但同时也不会忽略 CPU 密集型的进程。

进程优先级算法的思想就是高优先级先运行,低优先级后运行,但 Linux 并未完全采用。它用了两种不同的优先级范围

  1. nice 值。越低代表优先级越高(越高人越好的意思)

  2. 实时优先级。值是可以配置的,越高意味着进程优先级越高。任何实时进程优先级都高于普通进程。

CFS 并不是直接分配时间片给进程,而是将处理器的使用比重划分给进程。这个比例与系统负载相关,同时受到 nice 值的影响。

虽然 CFS 不再分配时间片,但它仍然会对进程的运行时间进行记录,使用了了一个名为 sched_entity 的结构体进行记录,它保存在了 task_struct 中。在 sched_entity 中,记录了一个 vruntime 字段,它记录了进程实际运行了多少时间。而 CFS 调度算法的核心思想就是选择 vruntime 最小的进程,从而保证公平调度。

CFS 使用了红黑树组织可运行进程队列,通过红黑树可以快速找到最小 vruntime 的进程

上下文切换

Linux 上下文切换 context_switch() 函数主要分为两步:

  1. switch_mm() 将虚拟内存从上一个进程切换到新进程。

  2. switch_to() 将上一个进程的处理器状态切换到新进程的处理器状态,包括保存、恢复栈信息及寄存器信息,以及其他相关的状态信息

Linux 内核需要知道何时调用 schedule(),提供了一个 need_resched 变量用于标志是否需要重新进行调度。当某个进程应当被抢占时,scheduler_tick() 会对这个标志进行设置。同时,唤醒的函数 try_to_wake_up() 也会设置这个标志。如果它被设置,内核会调用 schedule() 切换到一个新进程。

用户抢占

内核返回用户空间时,会检查 need_resched,若被设置,就会调用 schedule(),发生用户抢占。

因此用户抢占的发生有下列情形:

  • 从系统调用返回用户空间时
  • 从中断处理程序返回用户空间时

内核抢占

Linux 还支持了内核抢占,可以在内核级的进程执行时进行重新调度。不过内核抢占的前提是重新调度是安全的

安全的前提是,需要当前进程没有持有锁。因此在进程的 thread_info 中引入了 preempt_count 用于表示持有锁的数量。当从中断返回内核空间时,若 need_resched 被设置并且 preempt_count 为 0 时,调度程序就会被重新调用。若不为 0,则会回到当前进程,等到该进程释放所有锁时,便会再次去检查 need_resched,若被设置,则会重新进行调度。

同时,内核中的进程还可以显式调用 schedule() 从而主动发生内核抢占。

因此内核抢占主要有下列四个场景:

  • 中断程序正在执行,且返回内核空间前。
  • 内核代码再次具有可抢占性时(不持有锁)。
  • 内核中的任务显式调用 schedule()
  • 内核中的任务阻塞。

实时调度

Linux 提供两种实时调度策略: SCHED_FIFOSCHED_RR。默认的非实时调度策略则是 SCHED_NORMAL。实时策略并不受完全公平调度器管理,而是被特殊的实时调度器管理。

SCHED_FIFO 即先入先出调度,不使用时间片,处于这个级别的进程会比任何 SCHED_NORMAL 的进程优先调度。处于该级别的进程会一直执行下去,直到受阻塞或显式释放处理器。

SCHED_RR 在同一级别的实时进程之间轮流调度,但不能被低优先级的进程抢占

同时,Linux 提供了 sched_yield() 来让进程能够主动让出CPU。

参考资料

《操作系统导论》(Operating System : Three Easy Pieces

《Linux 内核设计与实现》(Linux Kernel Development

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

%d 博主赞过: