进程调度算法

一篇博客有一部分内容详细介绍：http://www.blogjava.net/killme2008/archive/2009/06/28/284459.html

1 中断与处理机调度的关系：
    中断与处理机管理密切相关的一个重要概念，确切的说，中断时实现多到程序设计的必要条件。没有中断，OS就无法获得系统的控制权，就不能将处理机资源分配给不同的进程。
    操作系统是中断驱动的。

2 中断有哪些类型
    强迫式中断
(1) 时钟中断: 如硬件实时时钟到时等
(2) I/O中断: 如设备出错、传输结束等 
(3) 控制台中断: 如系统操作员通过控制台发
     出命令等
(4) 硬件故障中断: 如掉电、内存校验错误等
(5) 程序性中断: 如目态程序执行特权指令、地址越界、缺页故障、溢出、除零等    
    自愿性中断
    自愿性中断是正在运行程序有意识安排的，它们通常由于正运行程序执行访管指令而引起，目的是要求系统为其提供某种服务。自愿性中断的发生具有必然性,而且发生位置确定。
  访管指令通常分为如下几类: 
 (1)与文件有关的系统调用:如建立文件、撤消文件、打开文件、关闭文件、读写文件、文件指针定位等。
 (2)与进程有关的系统调用:如创建进程、撤消进程、创建线程、监督进程运行状况等。
 (3)与通讯有关的系统调用:如发送消息、接收消息等。
 (4)与同步有关的系统调用:如P操作、V操作等

3 可能引起进程切换的中断原因有：
  时钟中断、设备I/O中断信号、系统调用等

4 什么是进程调度？
从就绪的进程中选出最适合的一个来执行。

5 调度什么时候发生？即：schedule()函数什么时候被调用？
1》 主动式
当进程需要等待资源等而暂时停止运行时，会把状态置于挂起（睡眠），并主动请求调度，让出cpu。

2》被动式（抢占）
 有更高优先级的进程抢占cpu，当有一个更高优先级的任务出现时，如果当前内核允许抢占，则可以将当前任务挂起，执行优先级更高的进程 。

！有两种抢占方式：用户抢占和内核抢占
！先介绍下用户态和内核态：
当一个任务（进程）执行系统调用而陷入内核代码中执行时，我们就称进程处于内核运行态（内核态）。在内核态下，CPU可执行任何指令。当进程在执行用户自己的代码时，则称其处于用户运行态（用户态）。用户态不能访问内核空间，包括代码和数据。
进程处于用户态时能访问的是用户空间，处于内核态时能访问的称为内核空间。
~~ 用户抢占发生在：
a 从系统调用返回用户空间
b 从中断处理程序返回用户空间
内核即将返回用户空间的时候，如果need_reshed标志被设置，会导致schedule()被调用，此时就会发生用户抢占。
~~ 内核抢占发生在：
   
a 中断处理程序完成，返回内核空间之前
b 当内核代码再一次具有可抢占性的时候，如解锁及使能软中断等
c 如果内核中的任务显示的调用schedule
d 如果内核中的任务阻塞
~~ 在支持内核抢占的系统中，某些特例不允许内核抢占的
1 内核在进行中断处理
2 内核在进行中断上下文处理
3 进程正持有自旋锁，读写锁等，当持有这些锁不应该抢占，否则由于抢占导致其他cpu长期不能获得锁而死等
4 内核正在执行调度scheduler
当内核要进入以上几种状态时，变量preempt_count就加1，指示内核不允许抢占，退出以上几种状态时，变量减1，同时进行判断与调度。
￥￥￥调度标志：
作用;
内核提供了一个need_resched标志来表明是否重新执行一次调度
设置：
当某个进程耗尽它的时间片时会设置这个标志
当一个优先级更高的进程进入可执行状态的时候，也设置这个标志
3》总结，进程调度的时机
引起进程调度的原因有以下几类
1》正在进行的进程执行完毕
2》执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠状态
3》执行中进程调用了p原语操作，从而因资源不足而被阻塞，或调用了v原语激活了等待资源的队列
4》执行中进程提出i/o请求后被阻塞
5》分时系统中时间片已经用完
6》在执行完系统调用等系统程序后返回用户进程时，这时可看作系统进程执行完毕，从而可调度选择一新的用户进程执行。 
7》就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。

6 首先硬件机制上如何保证操作系统的内核调度进程可以一定的时机可以获得CPU,来进行进程调度?
    通常我们会在软件层次上找答案.其实,是通过在CPU的硬件处理机制上实现的.CPU在执行完每个指令的周期后回扫描CPU的内部的一个中断寄存器,查询 是否存在中断发生,若没有,则继续执行指令;若有,则保存当前的CPU工作环境,跳转到中断服务列程,CPU执行中断服务程序,在推出中断后,跳转到内核 调度程序(这是个内核程序,但是是对所有的进程共享的,包括用户进程);此时,内核调度程序占据CPU,进行进程的调度,以决定下个将占用CPU的进程. （在时间中断里会调用进程调度，并且在中断的上半部分，也就是不可被打断。）

7  调度策略：
1)普通的分时进程
2)先入先出的实时进程
FCFS（First come first serve)，或者称为FIFO算法，先来先处理。这个算法的优点是简单，实现容易，并且似乎公平；缺点在于短的任务有可能变的非常慢，因为其前面的任务占用很长时间，造成了平均响应时间非常慢。

3)时间片轮转的实时进程
时间片轮询算法，这是对FIFO算法的改进，目的是改善短程序（运行时间短）的响应时间，其方法就是周期性地进行进程切换。这个算法的关键点在于时间片的 选择，时间片过大，那么轮转就越接近FIFO，如果太小，进程切换的开销大于执行程序的开销，从而降低了系统效率。因此选择合适的时间片就非常重要。选择 时间片的两个需要考虑的因素：一次进程切换所使用的系统消耗以及我们能接受的整个系统消耗、系统运行的进程数。
    时间片轮询看上起非常公平，并且响应时间非常好，然而时间片轮转并不能保证系统的响应时间总是比FIFO短，这很大程度上取决于时间片大小的选择，以及这个大小与进程运行时间的相互关系。
4 )短任务优先
STCF算法（Short time to complete first)，顾名思义就是短任务优先算法。这种算法的核心就是所有的程序都有一个优先级，短任务的优先级比长任务的高，而OS总是安排优先级高的进程运行。
    STCF又分为两类：非抢占式和抢占式。非抢占式STCF就是让已经在CPU上运行的程序执行到结束或者阻塞，然后在所有的就绪进程中选择执行时间最短的 来执行；而抢占式STCF就不是这样，在每进来一个新的进程时，就对所有进程（包括正在CPU上执行的进程）进行检查，谁的执行时间短，就运行谁。

    STCF总是能提供最优的响应时间，然而它也有缺点，第一可能造成长任务的程序无法得到CPU时间而饥饿，因为OS总是优先执行短任务；其次，关键问题在 于我们怎么知道程序的运行时间，怎么预测某个进程需要的执行时间？通常有两个办法：使用启发式方法估算（例如根据程序大小估算），或者将程序执行一遍后记 录其所用的CPU时间，在以后的执行过程中就可以根据这个测量数据来进行STCF调度。
5)优先级调度，STCF遇到的问题是长任务的程序可能饥饿，那么优先级调度算法可以通过给长任务的进程更高的优先级来解决这个问题；优先级调度遇到的问 题可能是短任务的进程饥饿，这个可以通过动态调整优先级来解决。实际上动态调整优先级（称为权值）+时间片轮询的策略正是linux的进程调度策略之一的 SCHED_OTHER分时调度策略,它的调度过程如下：

（1）创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。

（2）将根据每个任务的nice值确定在cpu上的执行时间(counter)。

（3）如果没有等待资源，则将该任务加入到就绪队列中。

（4）调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20-nice)结果，选择计算结果最大的一个去运行，当这个时 间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。

（5）此时调度程序重复上面计算过程，转到第4步。

（6）当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。

linux还有两个实时进程的调度策略：FIFO和RR,实时进程会立即抢占非实时进程。

6) 最高响应比优先算法(HRN)
按响应比由大到小的次序调度。
响应比计算公式如下：
rr=（bt+wt）/bt  
BT为CPU阵发时间，WT为等待时间。显然，对于同时到达的任务，处理时间短的将被优先调度，处理时间较长的作业将随其等待时间的增加而动态提升其响应比，因而不会出现饿死现象。
7) 分类排队算法
分类排队法又称多级队列法，它以多个就绪进程队列为特征。
  多个就绪队列将系统中所有可运行进程按某种原则加以分类,以实现某种调度目标。
  例如,在通用操作系统中,可将所有就绪进程排成如下三个队列:
      Q1: 实时就绪进程队列
      Q2: 分时就绪进程队列
      Q3: 批处理就绪进程队列
  当处理机空闲时,首先选择Q1中的进程,若Q1为空，则选择Q2中的进程；若Q1,Q2均为空,则选择Q3中的进程。每个队列内部又可分别采用不同的调度算法。
8) 反馈排队算法
分类排队法中,尽管系统中有多个进程就绪队列,但一个进程仅属于一个就绪队列,即进程不能在不同的就绪队列之间移动。
   反馈排队法也以多个进程就绪队列为特征,每个队列中通常采用时间片轮转调度算法,与分类排队法不同的是进程可以在不同的就绪队列之间移动。  
反馈排队法的基本思想：
   多个就绪队列的优先级依次递减,而其时间片的长度则依次递增。当一进程被创建或所等待的事件发生时,进入第一级就绪队列。当某队列的一个进程获得CPU并 使用完该队列所对应的时间片后,如果它尚未结束,则进入下一级就绪队列。 当最后一级队列的一个进程获得CPU并使用完该队列所对应的时间片后,如果它尚未结束,则进入同一级就绪队列。当处理机空闲时,先选择第一级就绪队列的进 程,当该级队列为空时,选择第二级就绪队列的进程,如此类推。    
说明：
  在反馈排队法中,如果高优先级队列一直不为空,则低优先级队列中的进程可能长时间得不到运行的机会,如此便可能会发生“饿死”现象。
  为解决这一问题,常根据某种原则允许将低优先级队列中的进程移到高优先级队列中去。

8 进程调度的上下文切换
@保存处理器的上下文，包括程序计数器和其它寄存器
@用新状态和其它相关信息更新正在运行进程的PCB(进程状态控制块) 
@把原来的进程移至合适的队列-就绪、阻塞 
@选择另一个要执行的进程 　　
@更新被选中进程的PCB 　　
@从被选中进程中重装入cpu上下文