L14 CPU调度策略

  • FIFO
  • Priority

不同场景如何设定不同的策略

  • 面向用户的
  • 面向进程的

要求

  • 尽快结束任务: 周转时间(从任务进入到任务结束)短
  • 系统内耗时间少: 吞吐量(完成的任务量)

  • 用户操作尽快响应: 响应时间(从操作发生到响应)短 :::info 前台任务和后台任务的关注点不同

  • 前台任务关注响应时间，

  • 后台任务关注周转时间 ::: IO约束型任务和CPU约束型任务有各自的特点
    image.png

  • IO约束型

    几种常见的CPU调度算法

    FCFS

    最质朴直接的想法：先来先服务
    这种方式十分简单，但是会造成一个问题：可能周转时间会比较长；
    image.png :::tips 对于第一种调度：🧶Part_05 如何调度 - 图3 :::

    SJF

    缩短调度时间的质朴的想法：短作业优先；
    image.png
    把CPU区间较短的作业放在前面，那么后面任务等待的时间肯定会降低
    但是这样也会带来问题：后面的作业的响应时间可能会过长

    RR

    改进方案：按时间片来轮转调度
    image.png

    响应时间和周转时间同时存在，怎么办

  • 直观想法: 定义前台任务和后台任务两队列，前台RR，后台SJF，只有前台任务没有时才调度后台任务

but会出现很多问题（前台一直有任务，后台任务就不会执行）

  • 后台任务优先级动态升高，但后台任务(用SJF调度)一旦执行，

前台的响应时间…
TBC

L15 一个实际的schedule函数

  1. void Schedule(void) //在kernel/sched.c中
  2. { 
  3.     while(1){ 
  4.     c=-1; next=0; i=NR_TASKS;//Linux0.11中，PCB以数组的形式存储，NR_TASKS指向数组末尾
  5.     p=&task[NR_TASKS];
  6.     while(--i){ 
  7.         if((*p->state == TASK_RUNNING&&(*p)->counter>c) 
  8.         c=(*p)->counter, next=i;
  9.     }
  10.     if(c) break; //找到了最大的counter
  11.     for(p=&LAST_TASK;p>&FIRST_TASK;--p)
  12.     (*p)->counter=((*p)->counter>>1)+(*p)->priority; 
  13.    }//时间片轮转？
  14.     switch_to(next);
  15. }

conter作用1：时间片轮转

  1. void do_timer(...) //在kernel/sched.c中
  2. { 
  3.     if((--current->counter>0) return;//每次时间片--，为零就切换
  4.     current->counter=0;
  5.     schedule(); 
  6. }
  8. _timer_interrupt: //在kernel/system_call.s中
  9. ...
  10. call _do_timer    //每次时钟中断都会调用，查看时间片是否为0
  12. void sched_init(void) {
  13.     set_intr_gate(0x20, &timer_interrupt)
  14. };

conter作用2：优先级动态调整：IO操作的优先级会生高（阻塞队列中待得越久，conter越会升高）
image.png