进程调度

进程

进程是程序在计算机中的一个执行过程。程序是静态的，而进程是动态的。

每个进程都有一个进程控制块，操作系统用来存放进程有关的信息。

进程的创建

四种主要事件会导致进程的创建：

• 系统初始化
• 正在运行的程序执行了创建进程的系统调用
• 用户请求创建一个新的进程
• 一个批处理作业的初始化

进程的终止

进程的终止通常由以下四种主要事件导致：

• 正常退出（自愿）
• 出错推出（自愿）
• 严重错误（非自愿）
• 被其他进程杀死（非自愿）

进程的状态

进程状态转换.jpg

基本状态：执行、就绪、阻塞
其他状态：挂起、僵死、等待

挂起：

• 将暂不执行的进程换出到外村，节省内存空间

进程五状态.jpg linux进程状态图.jpg

进程调度的时机

• 新进程的创建
• 当前进程的退出
• 正在执行的进程阻塞
• I/O中断发生

调度算法

分类

• CPU的分配方式
  • 非剥夺式（非抢占式）
  • 剥夺式（抢占式）
• 系统的分时方式
  • 批处理系统
  • 交互系统
  • 实时系统

调度目标

• 公平（让每个用户满意）
• 平衡（系统效率最高）

批处理系统

调度目标

• 吞吐量：系统每小时完成的作业数
• 周转时间： 一个作业从提交到完成时的统计平均时间
• CPU利用率

批处理系统中的调度算法

先来先服务

• 按照请求CPU的顺序使用CPU
  • 就绪队列时间先后的顺序
  • 队首取，队尾加
• 易于理解、便于实现
• 对短作业不公平

最短作业优先

• 提高平均周转时间
• 预知作业运行时间
• 最短剩余时间优先
  • 最短作业优先的强占版
  • 新作业比正在执行的作业剩余时间短
• 长作业无限期等待
  • 有失公平性

最高响应比优先算法

• 响应比
  • 作业等待时间/作业所需运行时间
• 优先考虑短作业
• 防止长作业无限等待

交互系统

调度目标

• 响应时间
  • 快速响应交互请求

交互系统中的调度算法

轮转法

• 使用时间片进行调度的算法，时间片段用完后会排到队尾，考虑到CPU效率与用户等待时间一般设置为20ms-50ms
  • 未用完时间片就I/O阻塞的，当I/O就绪后到就绪队尾重新排队。可以为其单设队列，优先考虑I/O后就绪进程直至其用完时间片。
• 优先级
  • 优先级高的进程先运行，同优先级的进程轮转（同一队列中轮转）
  • 每个进程设立优先级，高优先级的队列中没有进程，调度下一级队列
    • 静态设定
    • 动态设定：在优先级高的进程运行一个时间片后降低其优先级（防止高优先级进程独占CPU饿死低优先级的进程）

彩票法

• 向进程提供各种系统资源的彩票
• 调度时随机抽取彩票，拥有该彩票的资源得到资源
  • 可给重要的今晨更多的彩票
  • 协作进程可以交换彩票

公平分享法

• 为每个用户分配一定比例的CPU时间
  • 假设用户1开了四个进程ABCD，用户2开设一个进程E，则CPU调度有可能为AEBECEDEAEBE...
• 按照比例个用户之间挑选进程

实时系统

调度目标

• 满足截止时间
  • 正确的但是迟到的应答比没有更糟糕
• 硬实时
  • 必须满足的绝对的截止时间
• 软实时
  • 可以容忍偶尔的错失截止时间

基本条件

• 提供必要的信息
• 系统处理能力强
• 采用抢占式调度机制
• 具有快速切换机制

调度算法

最早截止时间优先算法

先把截止时间早的任务给完成，否则这个任务如果在截止时间后才完成就没有意义了。

进程切换开销

• 时间和空间上的系统开销
• 保存和恢复进程的上下文

Linux的进程调度

这里朱凯豪师兄总结的特别好，这里附上链接