Linux O(1)调度算法

1. 算法特点

1. 复杂度:O(1)，选取和添加任务都可以在常数时间内完成,Linux 2.5引入
2. 抢占式的，基于优先级的调度算法，将任务划分为两个独立的优先级范围
   • 实时范围（real-time tasks）: 优先级为0-99
   • 相对优先级较高，分配的时间片较长，适合CPU Bound tasks * 分时范围（time-sharing tasks）:优先级为100-139
   • 相对优先级较低，分配的时间片较短，适合IO Bound tasks

2. 时间片长度

1. 由任务的优先级判定
2. 优先级较低的任务，分配较短的时间片
3. 优先级较高的任务，分配较长的时间片

3. 反馈机制

1. 根据每个任务之前的sleep time调整其优先级, sleep time是该任务wait或idle的时间
2. sleep time较长，则证明该任务的交互性较强，因此提升其优先级，并增加其时间片长度
3. sleep time较短，则证明该任务的计算性较强，因此降低其优先级，并减少其时间片长度

4. 数据结构

1. 活动队列（Active quque）
   • 包含所有在其时间片中尚有剩余时间的任务，即需要运行的任务，用于选择下一个要执行的任务
   • 选择和添加任务的操作都可以在常量时间内完成
   • 在每个任务的时间片结束之前，该任务将一直保留在活动队列中
2. 到期队列(Expired queue)
   • 包含所有时间片到期的任务
   • 当活动队列中的任务耗尽时间片时，将其移动到到期队列中，并重新计算其动态优先级
   • 当活动队列中没有任务时，则交换活动队列和到期队列

5. 缺点

1. 活动性较强的任务要再次运行，就需要等待当前等待队列中的所有任务都执行完成之后，这将在很大程序上影响活动性较强的任务的使用体验
2. 不能保证公平性，即不能保证在给定的时间间隔内，为每个任务分配的时间与其优先级是成比例的