Linux系统进程调度
姓名: 班级: 学号：
摘要
Linux 自出现以来以惊人的速度在服务器和桌面系统中获得了成功。

本文介绍了现代操作系统常见进程调度算法以及linux2.6.32中进程调度的策略并根据具体例子对Linux进程调度过程进行了具体分析。

一、最常用的操作系统调度算法有以下几种;
1.先来先服务调度算法
调度程序按照进程在就绪队列中的提交顺序或变为就绪状态的先后进行调度,是一种最普遍和最简单的方法,所需的系统开销最小。

该算法对所有的进程一视同仁,不能反映对实时进程或特殊要求的进程的特殊处理,在实际操作系统中,很少单独使用该算法,而是和其它一些算法配合起来使用。

2.高优先权优先调度算法
1 优先权类型。

1)静态优先权，他是在创建进程时确定的，且在进程的整个运行期间保持不变。

2)动态优先权，他是在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。

2优先权调度算法的类型。

1)非抢占式优先权算法。

在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。

2)抢占式优先权调度算法。

这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。

但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。

3.时间片的轮转调度算法
时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一
个时间片。

当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。

4.多级反馈轮转法
它是在优先级和轮转法的基础上,根据进程加入就绪队列的原因不同,将就绪队列分为多个就绪队列,不同的队列之间优先权不同,而同一个队列内的进程优先权相同而按照先来先服务的原则排列。

二、LINUX的进程调度
1.调度的时机
1)当前进程调用系统调用nanosleep()或者pause(),使自己进入睡眠状态，主动让出一段时间的cpu使用权。

2) 进程终止，永久地放弃对cpu的使用。

3)在时钟中断处理程序执行过程中，发现当前进程连续运行时间过长。

4)当唤醒一个睡眠进程时，发现被唤醒的进程比当前进程更有资格运行。

5)一个进程通过执行系统调用来改变调度策略或者降低自身的优先权，从而引起立
即调度。

2.Linux系统中的调度策略
1)SCHED_OTHER
这是Linux的标准调度策略，也是所谓TSS调度策略。

其时间片是动态决定的。

2)SCHED_FIFO
这是实时调度策略，即具有静态优先级的调度策略。

Linux内核中能够为实时调度策略的进程指定的优先级为1～99。

使用了SCHED_FIFO调度策略的进程，除了等待I/O完成时休眠、自发休眠或优先级更高的实时进程获得优先权以外，不会释放执行权。

3)SCHED_RR
这也是实时调度策略。

RR是round robin（轮询）的缩写，与SCHED_FIFO不同的是，它具有时间片。

时间片使用完时，执行权将转移到其他进程。

4)SCHED_BATCH
指定这个调度策略的进程不是会话型，不会根据休眠时间更改优先级。

5)SCHED_IDLE
这是由CFS导入的新等级。

CPU空闲时，即SCHED_IDLE等级以外处于可执行状态的进程消失时，将被赋予执行权。

也就是它将成为优先级最低的进程。

3.举例分析进程调度与切换具体过程
本过程以用户进程str1 和str2为例进行详细讲述。

1)str1刚被创建并处于就绪态。

此时shell进程刚创建完str1，shell进程状态为就绪状态，str1也为就绪状态。

2)shell进程将自己挂起，然后准备切换到str1执行。

此时用户没有敲击键盘，shell进程会调用schedule 函数进行切换。

3)准备切换到str1进程执行。

进入schedule函数后，从进程槽数组的末端开始扫描系统中以存在的进程是否启用了报警器，该报警器的意思是当到达某个时间点给内核进程发送一个报警信号，内核进程可以检测报警器的数值，唤醒进程。

之后进行第二次遍历，内核通过while 循环选择一个合适的进程投入运行。

最后执行switch_to实施进程切换，使cpu切换到新的进程执行。

4)str1执行时发生时钟中断。

在str1执行时，假设刚开始执行就发生了时钟中断。

5)时钟中断递减str1运行的时间片。

在时钟中断处理函数do_timer中，内核递减当前进程的时间片，每次减一，当时间片递减到0时，才有可能从当前进程切换到其他进程。

6)str1执行一段时间后挂起，shell进程新建str2进程。

在进程str1执行一段时间后，会调用sleep（）进入TASK_INTERRUPTIBLE状态，但他的时间片并没有用完，如果此时用户在shell中输入./str2这个新的用户进程，str1进入可中断等待状态，shell进程进入可中断等待状态，str2进入就绪态。

7)str2运行期间发生时间中断
进程str2在运行期间又发生了时钟中断，中断处理程序检查当前时间是否超过了str1睡眠时间后的时间。

如果超过了，则将进程str1信号位设置成SIGALRM，并
设置str1进程状态为TASK_RUNNING。

此时，str1时间片不变，同时，str2时间片会被削减，然后str2继续执行。

Str2的程序代码和str1的程序代码相同，所以，也会被置为可中断等待状态，于是中断处理调用schedule进行任务的切换。

8)系统切换到str1程序执行。

由于str1此时为就绪态，所以会切换到str1，等到str1时间片削减为0后，系统会继续分配时间片，让他们继续轮流操作。

参考文献
【1】新设计团队。

Linux内核设计的艺术:图解Linux操作系统架构设计与实现原理。

北京：机械工业出版社，2011.5
【2】汤小丹。

计算机操作系统（第四版）。

西安：西安电子科技大学出版社，2014.5 【3】高桥浩和编杨婷译。

Linux内核精髓。

北京：机械工业出版社，2013。