经典进程调度算法

介绍进程调度的概念和作用

当 CPU 有一堆任务要处理时，由于其资源有限，这些事情就没法 同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这 就是 “调度” 研究的问题。除了接下来将要说的进程调度，还有 作业调度、内存调度等。

进程的三态模型：

 运行态 （running）：进程占有 CPU 正在运行。
 就绪态 （ready）：进程具备运行条件，等待系统分配 CPU 以便运行。
 阻塞态 / 等待态（wait）：进程不具备运行条件，正在等待某个事件的完成。

介绍常见的内核任务调度策略，分析经2-3个经典调度算法的实现原理及适用场景（Shortest Job First (SJF)、Round-robin (RR)）

非抢占式进程调度算法

① 先到先服务 FCFS
先来先服务调度算法（First Come First Serve，FCFS）：按照进程到达的先后顺序进行调度，先到的进程就先被调度 ，也就是说，等待时间越久的越优先得到服务。

② 最短作业优先 SJF
最短作业/进程优先调度算法（Shortest Job First，SJF）：每次调度时选择当前已到达的、且运行时间最短 的进程 。

③ 高响应比优先 HRRN
高响应比优先算法（Highest Response Ratio Next，HRRN）：只有当前运行的进程主动放弃 CPU 时（正常/异常完成，或主动阻塞），才需要进行调度，调度时计算所有就绪进程的响应比，为响应比最高的进程分配 CPU 。响应比 = (进程的等待时间 + 进程需要的运行时间) / 进程需要的运行时间

抢占式进程调度算法

① 最短剩余时间优先 SRTN
最短剩余时间优先（Shortest Remaining Time Next，SRTN）算法是最短作业优先的抢占式版本 。
当一个新的进程到达时，把它所需要的整个运行时间与当前进程的剩余运行时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程，否则新的进程等待。

② 轮转调度算法 RR
轮转调度算法（Round Robin，RR）也称时间片调度算法：调度程序每次把 CPU 分配给就绪队列首进程使用规定的时间间隔，称为时间片，通常为 10ms ~ 200ms，就绪队列中的每个进程轮流地运行一个时间片，当时间片耗尽时就强迫当前运行进程让出 CPU 资源，转而排到就绪队列尾部，等待下一轮调度。所以，一个进程一般都需要多次轮转才能完成。
轮转调度算法对每个进程都一视同仁，就好比大家都排好队，一个一个来，每个人都运行一会儿再接着重新排队等待运行。
最高优先级调度算法 HPF

RR 调度算法对所有的进程都是相同的策略，如果用户进程太多，可能会导致内核的服务进程响应跟不上。而在操作系统中，内核进程是比用户进程重要的多的，毕竟它关乎整个系统的稳定性。

最高优先级调度算法（Highest Priority First，HPF）就是从就绪队列中选择最高优先级的进程进行运行。进程的优先级是怎么规定的呢？

分为静态优先级或动态优先级：

1. 静态优先级：创建进程时候，就预先规定优先级，并且整个运行过程中该进程的优先级都不会发生变化。一般来说，内核进程的优先级都是高于用户进程的。
2. 动态优先级：根据进程的动态变化调整优先级。比如随着进程的运行时间增加，适当的降低其优先级；随着就绪队列中进程的等待时间增加，适当的升高其优先级。
   另外，需要注意的是，最高优先级算法并非是固定的抢占式策略或非抢占式，系统可预先规定使用哪种策略：

 非抢占式：当就绪队列中出现优先级高的进程，则运行完当前进程后，再选择该优先级高的进程。

 抢占式：当就绪队列中出现优先级高的进程，则立即强制剥夺当前运行进程的 CPU 资源，分配给优先级更高的进程运行。

先来先服务（FCFS）调度算法

顾名思义，就是谁先来谁先用处理机，就和我们食堂排队打饭一样。可以看的出来，这种算法是讲究公平的，不管你是什么进程，都得按照先来后到的顺序来用处理机。它适用于进程调度和作业调度。
虽然说这个算法体现了公平性，但是万一先到达的进程或者是作业需要的用时很长，那么就会使得后面的作业或进程（特别是后面的作业是短作业或短进程的时候）等待很久，这样就会大大的降低处理机调度以及处理机运行的效率。
所以说，这个算法虽然简单并且公平，但是总体来讲，对长作业或者长进程有利，而且效率比较低，特别是当一个进程需要多次请求I/O的时候，会对后面排队的进程造成很大的影响。
适用场景
对长作业比较有利，但对短作业不利；有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

SJF算法

是以进入系统的作业所要求的CPU时间为标准，是指对短作业或者短进程优先调度的算法，将每个进程与其估计运行时间进行关联选取估计计算时间最短的作业投入运行。
从名字上来看，这个调度算法是为短作业量身定做的，当进行作业调度的时候，该调度算法选择一个估计运行时间最短的作业进入内存，当进行进程调度的时候，该算法从就绪队列里面，挑一个估计运行时间最短的进程，并将处理机分配给它。
适合短作业，不适合长作业

 分析Linux0.11内核版本中的调度函数schedule()，解释清楚其实现思路。

Task_struct

task_struct（sched.c第80行）
// 进程控制块
struct task_struct {
/*-----------------------these are hardcoded - don't touch -----------------------*/
long state; //进程运行状态（-1不可运行，0可运行，>0以停止）
long counter; //任务运行时间片，递减到0是说明时间片用完
long priority; //任务运行优先数，刚开始是counter＝priority
long signal; //任务的信号位图，信号值=偏移+1
struct sigacTIon sigacTIon[32]; //信号执行属性结构，对应信号将要执行的操作和标志信息
long blocked; //信号屏蔽码
/*-----------------------------------various fields--------------------------------- */
int exit_code; //任务退出码，当任务结束时其父进程会读取
unsigned long start_code,end_code,end_data,brk,start_stack;
// start_code 代码段起始的线性地址
//end_code 代码段长度
//end_data 代码段长度+数据段长度
//brk 代码段长度+数据段长度+bss段长度
// start_stack 堆栈段起始线性地址
long pid,father,pgrp,session,leader;
// pid 进程号
// father 父进程号
// pgrp 父进程组号
// session 会话号
// leader 会话首领
unsigned short uid,euid,suid;
// uid 用户标id
// euid 有效用户id
// suid 保存的用户id
unsigned short gid,egid,sgid;
// gid 组id
// egid 有效组id
// sgid 保存组id
long alarm; //报警定时值
long uTIme,sTIme,cutime,cstime,start_time;
// utime 用户态运行时间
//stime 内核态运行时间
//cutime 子进程用户态运行时间
//cstime 子进程内核态运行时间
//start_time 进程开始运行时刻
unsigned short used_math; //标志，是否使用了387协处理器
/*----------------------------------file system info-------------------------------- */
int tty; //进程使用tty的子设备号，-1表示没有使用
unsigned short umask; //文件创建属性屏蔽码
struct m_inode * pwd; //当前工作目录的i节点
struct m_inode * root; //根目录的i节点
struct m_inode * executable; //可执行文件的i节点
unsigned long close_on_exec; //执行时关闭文件句柄位图标志
struct file * filp[NR_OPEN]; //进程使用的文件
/*------------------ldt for this task 0 - zero 1 - cs 2 - ds&ss -------------------*/
struct desc_struct ldt[3]; //本任务的ldt表，0-空，1-代码段，2-数据和堆栈段
/*---------------------------------tss for this task---------------------------------*/
struct tss_struct tss; //本任务的tss段
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

void Schedule(void) //在kernel/sched.c
{
  int i,next,c;
  struct task_struct **p; //PCB指针
  while(1){  
     c = -1;next = 0;i = NR_TASKS;
     p = &task[NR_TASKS];
     while(--i){
      if((*p)->state==TASK_RUNNING&&(*p)->counter>c)      c = (*p)->counter,next=i; 
    } 
  if(c) break;
  for(p=&LAST_TASK;p>&FIRST_TASK;--p)
    (*p)->counter=((*p)->counter>>1)+(*p)->priority;
  }
  switch_to(next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Linux0.11内核中schedule函数解析：

struct task_struct **p是生成一个任务指针。

在Linux中,将PCB做成了一个数组,NR_TASKS就是数组的范围。 在schedule中,首先将p指向PCB的最后一个元素,然后遍历整个数组。
while (–i) 开始遍历整个task[]数组

TASK_RUNNING是就绪状态，等待运行。

这个if判断是寻找剩余时间片最长的可运行进程

c记录目前找到的最长时间片
next记录目前最长时间片进程的任务号

如果有进程时间片没有用完c一定大于0。这时退出循环，执行 switch_to任务切换

到这里说明所有可运行进程的时间片都用完了，则利用任务优先级重新分配时间片。

这里需要重新设置所有任务的时间片，而不光是可运行任务的时间片。

利用公式：counter = counter/2 + priority

新counter的值是原来值的一半加上进程的静态优先级（priortiy），除非进程已经释放CPU，否则原来counter的值为0。因此，schedule通常只是把counter初始化为静态优先级。(*p)->counter>>1是右移1位，相当于除以2

整个设置时间片过程结束后，重新进入进程选择过程 。当上面的循环退出时，说明找到了可以切换的任务