转进程的调度方式

http://blog.csdn.net/kavensu/article/details/8075642

1.等待态&＃xff1a;等待某个事件的完成&＃xff1b; 　　2.就绪态&＃xff1a;等待系统分配处理器以便运行&＃xff1b; 　　3.运行态&＃xff1a;占有处理器正在运行。 　　运行态→等待态 往往是由于等待外设&＃xff0c;等待主存等资源分配或等待人工干预而引起的。 　　等待态→就绪态 则是等待的条件已满足&＃xff0c;只需分配到处理器后就能运行。 　　运行态→就绪态 不是由于自身原因&＃xff0c;而是由外界原因使运行状态的进程让出处理器&＃xff0c;这时候就变成就绪态。例如时间片用完&＃xff0c;或有更高优先级的进程来抢占处理器等。 　　就绪态→运行态 系统按某种策略选中就绪队列中的一个进程占用处理器&＃xff0c;此时就变成了运行态

分派程序一旦把处理机分配给某进程后便让它一直运行下去&＃xff0c;直到进程完成或发生  某事件而阻塞时&＃xff0c;才把处理机分配给另一个进程。

当一个进程正在运行时&＃xff0c;系统可以基于某种原则&＃xff0c;剥夺已分配给它的处理机&＃xff0c;将之分配给其它进程。剥夺原则有&＃xff1a;优先权原则、短进程优先原则、时间片原则。 　　例如&＃xff0c;有三个进程P1、P2、P3先后到达&＃xff0c;它们分别需要20、4和2个单位时间运行完毕。 　　假如它们就按P1、P2、P3的顺序执行&＃xff0c;且不可剥夺&＃xff0c;则三进程各自的周转时间分别为20、24、 　　26个单位时间&＃xff0c;平均周转时间是23.33个时间单位。 　　假如用时间片原则的剥夺调度方式&＃xff0c;可得到&＃xff1a; 　　可见&＃xff1a;P1、P2、P3的周转时间分别为26、10、6个单位时间(假设时间片为2个单位时间)&＃xff0c;平均周转时间为14个单位时间。 　　衡量进程调度性能的指标有&＃xff1a;周转时间、响应时间、CPU-I/O执行期。

算法总是把处理机分配给最先进入就绪队列的进程&＃xff0c;一个进程一旦分得处理机&＃xff0c;便一直执行下去&＃xff0c;直到该进程完成或阻塞时&＃xff0c;才释放处理机。 　　例如&＃xff0c;有三个进程P1、P2和P3先后进入就绪队列&＃xff0c;它们的执行期分别是21、6和3个单位时间&＃xff0c; 　　执行情况如下图&＃xff1a; 　　对于P1、P2、P3的周转时间为21、27、30&＃xff0c;平均周转时间为26。 　　可见&＃xff0c;FIFO算法服务质量不佳&＃xff0c;容易引起作业用户不满&＃xff0c;常作为一种辅助调度算法。

2、最短CPU运行期优先调度算法(SCBF--Shortest CPU Burst First)

　　该算法从就绪队列中选出下一个“CPU执行期最短”的进程&＃xff0c;为之分配处理机。 　　例如&＃xff0c;在就绪队列中有四个进程P1、P2、P3和P4&＃xff0c;它们的下一个执行  期分别是16、12、4和3个单位时间&＃xff0c;执行情况如下图&＃xff1a; 　　P1、P2、P3和P4的周转时间分别为35、19、7、3&＃xff0c;平均周转时间为16。 　　该算法虽可获得较好的调度性能&＃xff0c;但难以准确地知道下一个CPU执行期&＃xff0c;而只能根据每一个进程的执行历史来预测。

前几种算法主要用于批处理系统中&＃xff0c;不能作为分时系统中的主调度算法&＃xff0c;在分时系统中&＃xff0c;都采用时间片轮转法。 　　简单轮转法&＃xff1a;系统将所有就绪进程按FIFO规则排队&＃xff0c;按一定的时间间隔把处理机分配给队列中的进程。这样&＃xff0c;就绪队列中所有进程均可获得一个时间片的处理机而运行。

4、多级反馈队列&＃xff1a;

　　多级队列方法&＃xff1a;将系统中所有进程分成若干类&＃xff0c;每类为一级。　多级反馈队列方式是在系统中设置多个就绪队列&＃xff0c;并赋予各队列以不同的优先权。

进程调度发生在什么时机呢&＃xff1f;这与引起进程调度的原因以及进程调度的方式有关。 　　(1)正在执行的进程执行完毕。这时&＃xff0c;如果不选择新的就绪进程执行&＃xff0c;将浪费处理机资源。 　　(2)执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等状态。 　　(3)执行中进程调用了P原语操作&＃xff0c;从而因资源不足而被阻塞&＃xff1b;或调用了v原语操作激活了等待资源的进程队列。 　　(4)执行中进程提出I/O请求后被阻塞。 　　(5)在分时系统中时间片已经用完。 　　(6)在执行完系统调用等系统程序后返回用户进程时&＃xff0c;这时可看作系统进程执行完毕&＃xff0c;从而可调度选择一新的用户进程执行。 　　以上都是在不可剥夺方式下的引起进程调度的原因。在CPU执行方式是可剥夺时&＃xff0e;还有 　　(7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级&＃xff0c;从而也将引发进程调度。

UNIX操作系统采用可剥夺的动态优先级调度算法。进程的优先级由赋给它的优先数确定&＃xff0c;优先数越小&＃xff0c;优先级越高。在该算法中&＃xff0c;进程的优先数随着它占用CPU的时间增加而增加。当进程占用CPU的时间减少时&＃xff0c;其优先数也随着减少。

补充&＃xff1a;作为一个分时的、多任务、多用户操作系统&＃xff0c;要保证公平地对待各个用户的进程&＃xff0c;使各终端用户的响应时间不至太一长.所以UNIX操作系统采用了这种调度算法。但这种算法不能满足关键任务的需求&＃xff0c;从而使传统的UNIXrK操作系统缺乏实时性。

Linux中的进程如果从调度策略划分&＃xff0c;可以分为两类&＃xff0c;普通进程和实时进程。实时进程又可分为两类&＃xff0c;FIFO&＃xff0c;RR。实时进程的优先级远远大于普通进程。Linux的处理策略是如果有实时进程处于可运行状态&＃xff0c;那么优先运行实时进程&＃xff0c;知道所有的实时进程或者结束&＃xff0c;或者被杀掉&＃xff0c;或者处于阻塞状态。也就是说如果实时进程一直在运行&＃xff0c;那么普通的进程就会被活活饿死。由于实时进程和普通进程所采用的调度策略不同&＃xff0c;下面分别介绍。

每一个普通进程都有一个静态优先级。这个值会被调度器用来与作为参考来调度进程。在内核中调度的优先级的区间为[100&＃xff0c;139]&＃xff0c;数字越低&＃xff0c;优先级越高。

&＃xff08;二&＃xff09;实时进程调度

 

每一个实时进程都会与一个实时优先级相关联。实时优先级在1到99之间。不同与普通进程&＃xff0c;系统调度时&＃xff0c;实时优先级高的进程总是先于优先级低的进程执行。知道实时优先级高的实时进程无法执行。实时进程总是被认为处于活动状态。

如果有数个 优先级相同的实时进程&＃xff0c;那么系统就会按照进程出现在队列上的顺序选择进程。假设当前CPU运行的实时进程A的优先级为a&＃xff0c;而此时有个优先级为b的实时进程B进入可运行状态&＃xff0c;那么只要b

 

不同调度策略的实时进程只有在相同优先级时才有可比性&＃xff1a;

1. 对于FIFO的进程&＃xff0c;意味着只有当前进程执行完毕才会轮到其他进程执行。由此可见相当霸道。
2. 对于RR的进程。一旦时间片消耗完毕&＃xff0c;则会将该进程置于队列的末尾&＃xff0c;然后运行其他相同优先级的进程&＃xff0c;如果没有其他相同优先级的进程&＃xff0c;则该进程会继续执行。
总而言之&＃xff0c;对于实时进程&＃xff0c;高优先级的进程就是大爷。它执行到没法执行了&＃xff0c;才轮到低优先级的进程执行。等级制度相当森严啊。