基本概念

1. 多道程序设计的目的将CPU的利用率最大化
2. 多个进程同时存在于内存（并发），当一个进程暂不使用cpu时，系统调用另一个进程占用cpu。
3. cpu调度程序

• whenever the cpu becomes idle(空闲) the operating system must select one of the processes in the ready queue to be executed .The selection process is carried out by the CPU scheduler.(cpu 调度程序)
• 每当CPU变为空闲时，操作系统必须从就绪队列中选择一个进程来执行。这个选择过程由CPU调度器来进行。

4. 抢占调度(process scheduling)

• 非抢占调度（nonpreemptive scheduling）
  • 一旦某个进程得到CPU，就会一直占用到终止或等待状态。
• 抢占调度（Preemptive scheduling）

5. 调度算法性能的衡量

• cpu利用率：cpu的忙碌程度
• 响应时间：从提交任务到第一次响应的时间(对于每一个指令，需要到cpu中执行，需要等待调度程调度到cpu中）
• 等待时间：进程积累在就绪队列中等待的时间，（对于多次进入就绪状态的时间是累加的）
• 周转时间：从提交到完成的时间
• 吞吐率：每个时钟单位处理的任务数
• 公平性：以合理的方式让各个进程共享cpu

5. 调度性能指标

• 作业（job）=进程（process）
• 假设作业i提交给系统的时刻是S，完成的时刻是F,所需运行的时间是K，那么：
  

调度算法

1. 先来先服务(FCFS)

• Frist-Come,First-Served(FCFS)
  • 早期系统里，FCFS意味着一个程序会一直运行到结束（尽管其中会出现I/O的情况）
  • 如今，当一个程序阻塞时会让出CPU。
• FCFS的优缺点
  • 简单易行（在系统中是默认的一个算法）
  • 如果短作业在长作业的后面将导致周转时间变长，假如超市只买了一瓶矿泉水，那排在队伍最后是感觉很不好的

2. 时间片轮转（round robin）

• 每个进程都可以得到相同的cpu时间（CPU时间片，time slice），当时间片到达，进程将会被剥夺cpu并加入就绪队列的尾部。
• 抢占式调度算法
• n个就绪队列中的进程和时间片q
  • 每个进程获得1/n的cpu时间，大约是q个时间单位
  • 没有进程等待时间会超过（n-1）q
• rr的平局周转时间是比较差的

3. 最短作业优先（sjf）

• SJF(Shortest Job First):下次调度总是选择所需要CPU时间最短的那个作业（进程 ）
• 这是一个非抢占式的算法，也可以改成抢占式SRTF
  
• 算法分析
  • 该算法总是将短进程移到长进程之前执行，因此平均等待时间最小，该算法被证明是最优的
  • 饥饿现象：长进程可能长时间无法获得CPU
  • 预测技术：
    • 该算法需要事先知道进程所需的CPU时间
    • 预测一个进程的cpu时间并非易事
  • 优缺点：
    • 优化了响应时间（+）
    • 难以预测作业CPU时间（-）
    • 不公平算法（-）

4. 优先级调度（PRIORITY）

• 优先级通常为固定区间的数字，如[0，10]
  • 数字大小与优先级高低的关系在不同系统中实现不一样，以Linux为例，0为最高优先级。
  • 调度策略：下一次调度总是选择优先级最高的进程。
  • SJF是优先级调度的一个特例。
  • 优先级调度可以是抢占式，也可以式非抢占式。
• 优先级的定义
  • 静态优先级
    • 优先级保持不变，但会出现不公平(饥饿)现象
  • 动态优先级（退化aging）
    • 根据进程占用CPU时间，当进程占用CPU时间愈长，则慢慢减低它的优先级；
    • 根据进程等待CPU时间：当进程在就绪队列中等待时间愈长，则慢慢提升它的优先级。