Linux课程笔记 | 进程3——进程调度

进程的分类

第一种分类：

I/O-bound ：频繁的进行I/O

CPU-bound ：计算密集型

第二种分类：

交互式进程（interactive process）
- 需要经常与用户交互，因此要花很多时间等待用户输入操作响应时间要快，平均延迟要低于50~150ms
- 典型的交互式程序：shell、文本编辑程序、图形应用程序等

批处理进程（batch process）
- 不必与用户交互，通常在后台运行
- 典型的批处理程序：编译程序、科学计算

实时进程（real-time process）
- 有实时需求，不应被低优先级的进程阻塞；响应时间要短
- 典型的实时进程：视频/音频、机械控制等

O(1)调度器：常数时间内完成其工作(不依赖于系统上运行的进程数目）

CFS调度器（completely fair scheduler）：完全放弃了原有的设计原则，前一个调度器中为确保用户交互任务响应快速，需要许多启发式原则

调度中最基本的数据结构;

是给定处理器上的可运行进程的列表;

每个处理器一个;

每个可运行的进程唯一归属于一个runqueue;

包含每个处理器的调度信息；

是每个处理器最重要的数据结构

定义在kernel/sched.c中。

runqueue 中最关键的数据结构。

每个 CPU 的就绪队列按时间片是否用完分为两部分

active 指向时间片没用完、当前可被调度的就绪进程

expired 指向时间片已用完的就绪进程。

Linux课程笔记 | 进程3——进程调度

主体思想就是：

当一个普通进程的时间片用完以后将重新计算进程的时间片和优先级，将该进程从active array中删除，添加 expired array中相应优先级的进程队列中。

当 active 为空时，则表示当前所有进程的时间片都消耗完了，此时，active 和 expired 进行一次对调，重新开始下一轮的时间片递减过程 .

而在2.4内核中重新计算时间片是在所有就绪进程的时间片都用完以后才统一进行的，因而进程时间片的计算非常耗时，而在O(1)中计算时间片是分散的，而且通过以上的方法来实现时间片的轮转，这也是O(1)调度器一个亮点