Process Behavior--进程行为

  • 几乎所有进程都会交替使用I/O请求进行计算

  • CPU-bound：计算密集型

    • 花费大量时间在计算上

  • IO-bound：I/O密集型

    • 在等待I/O上花费了绝大多数时间

Process Scheduling--进程调度

Scheduler--调度程序

  • 决定接下来要运行哪一个进程，是操作系统的一部分

Scheduling Algorithm--调度算法

  • 调度程序用于做出该决定的策略
  • 为了确保进程不会运行太长时间，使用时钟来引起周期性中断（通常在50-60 Hz左右）；也就是说，大约每20毫秒。

Preemptive Scheduling--抢占式调度

允许暂时挂起可运行的进程（将其变为ready状态），以便其他进程有机会使用CPU

什么时候进行调度

  • 当一个新的进程被创建
  • 当一个进程退出
  • 当一个进程阻塞在I/O
  • 在一个I/O中断发生时

Scheduling Algorithm Goals

  1. Fairness
  2. Efficiency
  3. Response Time
  4. Turnaround Time 周转时间
    • 从提交批处理工作到完成的平均时间
  5. Throughput 吞吐量
    • 每小时处理工作的数量

FCFS Scheduling 先来先服务

  • First-Come, First Served
  • 按顺序来

SJF Scheduling 最短作业优先

  • Shortest-Job-First
  • 与每个进程关联其下一个CPU突发的长度。选取最短的运行
  • 缺点：确定下一个CPU请求的长度上有困难
  • 有两种模式：
    1. nonpreemptive 非抢占
      • 一旦CPU给到进程，除非计算完成，否则其他进程不能抢占
    2. preemptive 抢占
      • 若新进程到达时，且新进程的CPU占用时长小于当前执行进程的剩余时间，则抢占。
      • 这一模式称为SRTF ( Shortest-Remaining-Time-First) 最短剩余时间优先
  • SJF是最优的–为给定的一组进程提供最小的平均等待时间。

非抢占

抢占

RR Scheduling 轮转调度

  • Round Robin
  • 每个进程被分配一个时间段，称为时间片，允许该进程在该时间段中运行
  • 所有进程都在等待队列中，切换后，原来的进程会进入到等待队列的末尾
  • 通常，平均周转率高于SJF，但响应更好。
  • 时间片
    • 时间片设得太短会导致过多的进程切换，降低了CPU效率
    • 时间片设得太长可能引起对短的交互请求的响应时间变长。
    • 将时间片设为20~50ms是一个比较合理的折中

Priority Scheduling 优先度调度

  • 给每一个进程一个优先级，允许优先级最高的可运行进程先运行
  • CPU会分配给优先级最高的进程
  • SJF就是一种优先级调度，优先级就是预测的下一个CPU突发时间
  • 缺点：
    • Starvation：低优先级的进程永远不会运行
  • 解决：随着时间增加进程的优先级

更多的调度

  1. Shortest Process Next
    • 通过根据过去的行为估计运行时间来在交互式环境中使用
    • a T0 + (1-a) T1 其中 T0 是前一次估计，T1 是当前运行时间。
  2. Guaranteed Scheduling
  3. Lottery Scheduling
  4. Fair-Share Scheduling

Thread Scheduling

  • 进程调度的算法也可以用于在线程调度中。
  • 在实践中，轮流调度和优先级调度是常用的。
  • 用户级线程和内核级线程
    • 用户级线程和内核级线程的主要区别在于性能。
    • 用户级线程可以采用特定于应用程序的线程调度器

问题

Check points

  1. What is IO-bound process?
  2. When to schedule processes?
  3. What are the goals of Scheduling algorithms?
  4. What is the drawback of the SJF algorithm?
  5. What is RR scheduling
Solution
  1. Cost most time for waiting I/O
  2. 4个
    • 新进程建立
    • 进程删除
    • 进程阻塞在I/O
    • I/O中断
  3. 5个
    • Fairness
    • Effcient
    • Respond time
    • Turnaround time
    • Throughput
  4. 可能会造成优先级问题
  5. 分发给每一个进程一个固定的时间片，进行不断地切换