L1415 【哈工大_操作系统】CPU调度策略一个实际的schedule函数

L2.7 CPU调度策略

1、调度的策略

• 周转时间：任务进入到任务结束（后台任务更关注）
• 响应时间：操作发生到响应时（前台任务更关注）
• 吞吐量：CPU完成的任务量

1. 响应时间小 -> 切换次数多 -> 系统内耗大 -> 吞吐量小
2. IO约束型任务优先级更高，IO启动后完后可以与CPU并行

2、几种调度算法

1. First Come, First Served（FCFS）
   

2. SJF：短作业优先

• 周转时间最小
  

3. 轮转调度（RR）

它将CPU时间公平地分配给每个就绪的进程，让所有进程轮流使用CPU执行一段固定的时间（时间片），避免某个进程长期占用CPU资源。如果该进程在规定的时间片内没有完成，就将它放回队列的末尾，等待下一轮调度。

• 响应时间小
  

3、调度策略

1. 前台任务-RR，后台任务-SJF。
2. 前台与后台之间优先级调度
3. 对于后台任务：
   1. 防止后台任务一直等待：后台任务优先级动态升高；
   2. 又防止后台任务比如gcc运行时间太长，前台响应时间太长：后台任务也需要时间片。

---

L2.8 一个实际的schedule函数

void schedule(void)
{int i,next,c;struct task_struct ** p;struct task_struct *pnext = &(init_task.task);/* check alarm, wake up any interruptible tasks that have got a signal */for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)if (*p) {if ((*p)->alarm && (*p)->alarm < jiffies) {(*p)->signal |= (1<<(SIGALRM-1));(*p)->alarm = 0;}if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&(*p)->state==TASK_INTERRUPTIBLE)(*p)->state=TASK_RUNNING;}/* this is the scheduler proper: */while (1) {c = -1;next = 0;pnext = task[next];i = NR_TASKS;p = &task[NR_TASKS];// 从最后一个进程往前遍历所有进程while (--i) {// 跳过空任务if (!*--p)continue;// 比较每个就绪态进程的counter，找到最大的counterif ((*p)->state == TASK_RUNNING && (*p)->counter > c)c = (*p)->counter, next = i, pnext = *p;}// 若找到了最大时间片是大于零的，则退出循环调用switch_to执行if (c) break;// 没有就绪态，或者就绪态时间片都等于零，则遍历所有进程：// 1. 若时间片等于0（即就绪态），则设置counter=初值// 2. 若为阻塞态，此时counter是不为0的，则设置counter肯定大于初值，即执行I/O而阻塞的进程回来后优先级高for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)if (*p)(*p)->counter = ((*p)->counter >> 1) +(*p)->priority;}switch_to(pnext, _LDT(next));
}

counter：时间片（优先级）

• 寻找最大的counter执行，体现了优先级的概念
• IO时间越长，优先级升高越多，防止后台等待时间太久
• counter保证了相应时间的界，最大时间片为2p，则最大响应时间为2np
• 不断地轮转，短作业一定比长作业先完成，近似了SJF，保证了周转时间