常用调度算法简介
一、关于调度
进程调度用于多进程或者多线程并发访问资源。
进程调度的需求出现在同时执行多个任务( multitasking )或者同时传输多数据流( mulplexing )。
主要关心方面如下：
- 吞吐量: 在一个整体时间内尽可能多地执行完进程，或者尽可能多地发出请求并响应。
- 延时: 进程提交执行请求并尽早开始执行，或者请求发出之后尽早得到相应。
- 公平性: 每个处理任务的消耗时间长度不会相差太多。
这几点有时相互矛盾，所以对于不同需求采用不同的调度算法尽量满足。
二、常见调度策略
操作系统中可以选择不同的调度算法模块，对任务进行调度，操作系统中常用的调度策略有如下。
1 、先来先服务( FCFS )
按照请求次序进行调度。
实现简单不用对队列进行调整，但是可能因某个元素处理时间过长，出现等待超时。
2、最短作业优先（ SJF ）
按照作业执行的消耗时间，消耗最短时间的先执行。
需要预先估计作业执行时间，耗时较长的作业可能一直得不到执行。
3、基于优先权的调度算法（ FPPS ）
给作业赋予一定优先权，每次从最高优先权的元素中取出一个并执行。
4、时间片轮转（ RR ）
给每个作业赋予一个运行时间片，当时间片到则取下一个元素。
是对 FCFS 和 SJF 算法的折衷，不会出现超时。
5、多级队列调度（ Multilevel feedback queue ）
对任务进行分类，不同分类放置到不同队列中，可能会采用不同的调度算法，队列中元素视情况会在不同队列之间迁移。
如何选择调度策略
以上是常见的策略，实际实现中，经常是几种方案综合实现。
例如windows将多级队列，优先权队列，时间片轮转，以及先进进出方式进行综合，每种优先权任务位于不同队列，高优先权采用时间片轮转方式调度，低优先权采用先进进出方式调度。
有时根据任务等待或者执行程度会调整优先权队列中元素的优先权。
三、为什么选择优先权队列？
假设我们选择优先权队列，这里给出常见的原因：
根据需求，需要对客户请求赋予一定优先级别，并且每个客户执行时间很难预先估计，采用 FPPS 方式实现比较容易接受。
采用一种改进方式：
- 所有客户请求都包含一定优先级别,所有请求位于一个全局队列当中。
- 当一个客户达到运行上限，则将该客户对应所有请求优先级别调整到最低（阻塞状态），相当于逻辑上将队列放置到一个阻塞队列中。
- 每次只从队列中去非阻塞客户的、最高优先级别的请求处理。
- 如果队列中没有非阻塞的客户，则等待。
- 当客户释放资源，则会将队列中所有对应该客户端的请求有限级别恢复成阻塞之前。
几个关键点：
- 优先权数越低则级别越大。（许多地方都这样实现）
- 优先权队列使用堆方式实现非常常见。（一个是排序算法复杂度低，一个是调整堆的代价小，一个是动态性强）
- 队列中任务如果处于阻塞，应当调整相应客户到低优先级，这样相当于“阻塞”了当前客户，而不影响其它同优先级客户的调度运行。（同样许多地方如此做）
<span class="timestamp-wrapper"><span class="timestamp">[2012-09-28 五 13:05] </span></span> python的稳定优先权队列实现注意
如果根据优先权来进行队列排序，由于python的优先权队列使用heap实现，而heap不是稳定的排序，所以，想要实现同优先权内部也有序，则需要增加一个计数，表示该优先权的顺序。
参考以下代码：
#!/usr/bin/python
from Queue import Queue
from Queue import PriorityQueue
a1='a1'
a2='a2'
a3='a3'
a4='a4'
a5='a5'
b1='b1'
b2='b2'
b3='b3'
b4='b4'
b5='b5'
q = Queue()
pq = PriorityQueue()
for i in xrange(5):
p = 5 - i
q.put("a"+str(p))
q.put("b"+str(p))
pq.put((p,"a"+str(p)))
pq.put((p,"b"+str(p)))
for i in xrange(5):
p = 5 - i
q.put("a"+str(p)+str(i+5))
q.put("b"+str(p)+str(i+5))
pq.put((p,"a"+str(p)+str(i+5)))
pq.put((p,"b"+str(p)+str(i+5)))
size = q.qsize()
print "queue item size:%s" %size
print "queue items:"
for i in xrange(size):
print q.get()
size = pq.qsize()
print "priority queue item size:%s" %size
print "priority queue items:"
for i in xrange(size):
print pq.get()
#"but priority queue with same priority is not queue, if we want so, do the following:"
import itertools
count = itertools.count()
poq = PriorityQueue()
for i in xrange(5):
p = 5 - i
poq.put((p,count.next(),"a"+str(p)))
poq.put((p,count.next(),"b"+str(p)))
for i in xrange(5):
p = 5 - i
poq.put((p,count.next(),"a"+str(p)+str(i+5)))
poq.put((p,count.next(),"b"+str(p)+str(i+5)))
size = poq.qsize()
print "priority ordered queue item size:%s" %size
print "priority ordered queue items:"
for i in xrange(size):
print poq.get()
输入类似如下:
queue item size:20
queue items:
a5
b5
a4
b4
a3
b3
a2
b2
a1
b1
a55
b55
a46
b46
a37
b37
a28
b28
a19
b19
priority queue item size:20
priority queue items:
(1, 'a1')
(1, 'a19')
(1, 'b1')
(1, 'b19')
(2, 'a2')
(2, 'a28')
(2, 'b2')
(2, 'b28')
(3, 'a3')
(3, 'a37')
(3, 'b3')
(3, 'b37')
(4, 'a4')
(4, 'a46')
(4, 'b4')
(4, 'b46')
(5, 'a5')
(5, 'a55')
(5, 'b5')
(5, 'b55')
priority ordered queue item size:20
priority ordered queue items:
(1, 8, 'a1')
(1, 9, 'b1')
(1, 18, 'a19')
(1, 19, 'b19')
(2, 6, 'a2')
(2, 7, 'b2')
(2, 16, 'a28')
(2, 17, 'b28')
(3, 4, 'a3')
(3, 5, 'b3')
(3, 14, 'a37')
(3, 15, 'b37')
(4, 2, 'a4')
(4, 3, 'b4')
(4, 12, 'a46')
(4, 13, 'b46')
(5, 0, 'a5')
(5, 1, 'b5')
(5, 10, 'a55')
(5, 11, 'b55')
其他
更详细资料，参考：
网友评论