> Linux教程 > 系统运维 >

进程的调度方式,调度算法总结

进程的三种状态:
1、等待态:等待某个事件的完成;
2、就绪态:等待系统分配处理器以便运行
3、运行态:占有处理器正在运行
 
三种状态的转化:
运行态到等待态:往往是由于等待外设,等待主存等资源分配或等待人工干预而引起的;
等待态到就绪态:等待的条件已经满足,只需要分配到处理器后就能运行;
就绪态到运行态:系统按某种策略选中就绪队列中的一个进程占用处理器;
运行态到就绪态:由于外界原因是运行状态的进程让出处理器,例如有更高优先级的进程来抢占处理器,或时间片(时间片是系统分配给程序的运行时间)用完。
 
调度方式:
剥夺方式:当一个进程正在运行时,系统可以基于某种原则,剥夺已分配给他的处理机,将之分配给其他进程,剥夺原则有:优先权原则、短进程优先原则、时间片原则。
非剥夺方式:分配程序一旦吧处理机分配给某进程后便让他一直运行下去,知道进程完成或发生事件而阻塞时,才把处理机分配给另一个进程。
 
进程调度算法有:
1、先来先服务调度算法(FCFS,first come first served):谁第一个排队,谁就先被执行,在它执行过程中,不会中断它;
2、短作业优先调度算法(SJF,shortest job first):对预计执行时间短的进程有限分配处理机,通常后来的短进程不会抢先正在执行的进程;对长进程非常不利,可能长时间得不到执行。
3、最高响应比优先法(HRRN,highest response radio next):对于FCFS和SJF的平衡,FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短,而SJF只考虑了执行时间而未考虑等待时间的长短,因此两种算法在某种极端的情况下会带来某些不便。HRRN通过综合这两种情况算出响应比R,根据响应比完成调度。优点:长作业也有机会投入运行,缺点:每次调度前要计算响应比。
4、时间片轮转法(RR,Round-Robin):采用剥夺方式,每个进程被分配一个时间段,按照在队列中的顺序交替执行;不利于处理紧急作业。
5、多级反馈队列(multilevel feedback queue): UNIX使用这种调度算法;进程在进入待调度的队列等待时,首先进入优先级最高的Q1中等待;首先调度优先级高的队列中的进程。若高优先级队列中已经没有调度的进程,则调度次优先级队列的进程;同一队列中的各个进程按照时间片轮转调度;在低优先级队列中的进程在运行时,又有新到达的作业,那么在运行完这个时间片后,CPU马上分配给新到达的作业(剥夺)。
 
多级反馈队列算法实例:
假设3个反馈队列Q1,Q2,Q3,时间片分别是2、4、8
三个进程J1,J2,J3,到达时刻为0,1,3;需要执行时间为3,2,1个时间片
0、时刻0,J1进入Q1,执行一个时间片J1(1),到达时刻1;
1、时刻1,J2到达进入Q2,等待,J1(1)在Q1中执行一个时间片,得到J1(2),Q1时间片用完,到达时刻2;
2、时刻2,J1(2)进入Q2等待,J2开始在Q2中执行一个时间片得到J2(1),到达时刻3;
3、时刻3,J3到达,因为此时Q1为空,所以进入Q1等待,但此时J2(1)在Q2中还在执行,J2(1)在Q2中执行一个时间片,得到J2(2),完成J2,到达时刻4;
4、时刻4,此时Q1中是未执行的J3,Q2中是J1(2),所以J3再Q1中执行一个时间片得到J3(1),完成J3,到达时刻5;
5、时刻5、J1(2)在Q2中执行一个时间片,得到J1(3),完成。
 

 

(责任编辑:IT)