OS Thread Sheduling Algorithm

Posted on Edited on In Views:

Outline:

  • workload
  • scheduling metrics
  • 处理器调度层次
  • 各种算法...

workload

  • Def: a fully-operational scheduling discipline
  • 为了方便下面各种算法的说明， 我们目前对work load做出如下假设：
    1. 每个工作运行相同的时间（工作就是进程）
    2. 所有的工作同时到达
    3. 一旦开始，所有工作保持运行直到完成
    4. 所有工作只使用CPU（即，不执行IO操作）
    5. 所有工作的运行时间已知

scheduling metrics

  • 性能指标：
    • 周转时间： 任务完成 - 任务到达
    • 响应时间：任务首次运行（服务时间） - 任务到达
      • 用于度量交互性，因为分时系统的用户会面对终端，这要求终端交互性好
  • 公平

处理器调度层次

  • 高级调度（长程调度、作业调度）: 决定能否加入到执行的进程池中
  • 中级调度（平衡负载调度）： 决定主存中的可用进程集合
  • 低级调度（短程调度、 进程调度）：决定哪个进程占用处理器执行

优化周转时间算法

用于批处理作业。下述三个算法都面向“周转时间”，但是当衡量其“响应时间”时，下述算法表现都不好。 对于SJF而言，只要短进程源源不断来, 长进程就饿死

FCFS

  • First Come First Service: 非抢占,直到某个进程运行结束,依次调度接下来的,偏爱长作业
    • 推翻假设1后（可能出现长作业），该算法fail

SJF

  • Shortest Job First: 非抢占，先运行最短的任务
    • 再推翻假设2,运行进程不同时到达，此时短任务可能会晚到达，由于算法非抢占，短任务必须等待长任务执行完，该算法fail

STCF

  • Shortest Time-to-Completion First: 最短完成时间优先: 抢占式SJF,推翻了假设3

优化响应时间算法

用于分时系统

RR

  • Round Robin:抢占,time slice结束时,当前进程放入就绪队列,然后切换到队列中的下个进程
    • “抢占”是指进程之间。 在同一time slice内，进程不抢占
    • time slice必须是时钟中断周期的倍数
    • time slice太短也不好，因为context switch有成本
  • 该算法在“周转时间”表现不佳

结合IO的STCF

  • 推翻假设4,现在运行程序执行IO。此时假设有两个工作A和B,每项占用50msCPU，但每A运行10ms会发起10ms的IO请求，而B只使用CPU
  • 此时可以把A的每个10ms工作视为独立的工作，因此系统先调度10ms的A，然后调度50ms的B，而10ms后新的A会提交，因此会抢占B执行，这样做实现了overlap
  • overlap： 一个进程在另一个进程等待IO时使用CPU

MLFQ

推翻假设5后，进程运行时间不可知，之前的算法失效

  • Multi-Level Feedback:多级反馈调度: 抢占式,每当进程被抢占时就降级

    • 建立多个不同优先级的就绪进程队列，多个就绪进程队列之间按照优先级调度
    • 高优先级的就绪进程, 分配的时间片短
    • 同一就绪进程队列中的进程的优先数和时间片相同, 按照FCFS调度
    • 工作进入系统时放在最高优先级
    • 一旦工作用完了其在某一层中的时间片，它就被抢占，自己移入低一级队列
      • 进程只有被抢占后才降级，因此如果一共只有一个进程，该进程不会降级

  • problem： 如果短工作不断到来，长进程可能饿死

    • 改进： 经过一段时间S, 将系统中所有工作重新加入最高优先级队列

比例份额

确保每个工作获得一定比例的CPU时间，实现公平性

份额调度最大的缺点在于难以确定份额，即依赖假设5

彩票调度

  • 每个进程持有一定数量的彩票，该进程的彩票数占总彩票数的百分比代表它占有某个资源的份额
  • CPU每个时间片随即抽取一个数，拥有该数对应彩票的进程会被调度一个时间片
    • 例如工作A和B分别有75, 25个彩票，对应数字0 - 74, 75 - 99.
    • OS抽取数字序列为：63, 85, 70, 39, 76, 17, 95
    • 工作调度次序为：A, B, A, A, B, A, B
  • 随机， 优点是实现简单，不依赖任何全局量
  • PROBLEM：基于概率，因此有可能出现异常情况

步长调度

  • 每个进程都具有步长(stride), 和一个行程（pass）值。
    • 步长： 一个大数 / 进程的彩票数
    • 初始时所有行程值为0
  • 每次调度当前具有最小行程值的进程，每当进程运行一个时间片后后， 行程值 += 步长
    • 进程在时间片内不被抢占
1
2
3
4
current = remove_min(queue); //pick client with min pass
schedule(current);// use resource for quantum
current -> pass += current -> stride;// compute next pass using stride
insert( queue, current );// put back into the queue

  • 例子：假设A,B,C彩票数分别为100,50,250, 其步长值分别为100, 200, 40

    1. 初始时所有步长为零，随即调度工作，假设A被调度，执行一个时间片，更新其行程值为100. 然后选择B, 运行后更新其行程值为200； 然后选择C,运行后更新其行程值为40

    2. 然后算法选择最小的工作，它会再调度2次C, C的行程值增加到120. 然后调度A ...

    行程值（A） （步长 = 100） 行程值（A） （步长 = 100） 行程值（A） （步长 = 100） 被调度进程
    0 0 0 A
    100 0 0 B
    100 200 0 C
    100 200 40 C
    100 200 80 C
    100 200 120 A
    200 200 120 C
    200 200 160 C

    可以看到，在这段时间内， A, B, C分别调度2, 1， 4次，与其彩票数占比相符合

  • 彩票调度只能在概率上实现比例（因此有概率翻车），而步长调度可以直接控制比例

  • PROBLEM： 步长调度需要维护全局状态：行程值。 如果中途有新进程加入，则新进程的行程值为0,它会独占CPU

HRRN

  • HRRN(highest response radio next)高响应比优先: 非抢占式
    • 响应比 = (等待时间+服务时间) / 服务时间

多处理器调度

缓存一致性：

  • 一种方案： 总线窥探（bus snooping）: 每个缓存都监听链接所有缓存和内存的总线，在发现内存访问。

同步问题：

  • 加锁

缓存亲和度：

  • 同意进程在同一CPU运行时，由于有cache而运行得快

SQMS

  • 单队列调度（Single-Queue Multiprocessor Scheduling）：所有工作放入一个全局的单调队列。每个CPU从队列中拿取工作

    • 当然，可以将工作以时间片为单位存储进队列，这样CPU每次都运行一个time slice的工作

  • 缓存亲和度问题： 假设有CPU 0-3, 队列中工作序列为A,B,C,D,E, 则：

    CPU0 CPU1 CPU2 CPU3
    A B C D
    E A B C
    D E A B
    C D E A
    可以看到亲和度很差

MQMS

  • 多队列调度（Multi-Queue Multiprocessor Scheduling）: 每个CPU拥有自己的队列。 不同队列可以采用不同的调度规则。OS依据一些启发式规则将新工作放入某个队列
    • 每个CPU之间调度相互独立