常用调度算法简介

一、关于调度

进程调度用于多进程或者多线程并发访问资源。

进程调度的需求出现在同时执行多个任务( multitasking )或者同时传输多数据流( mulplexing )。

主要关心方面如下：

• 吞吐量: 在一个整体时间内尽可能多地执行完进程，或者尽可能多地发出请求并响应。
• 延时: 进程提交执行请求并尽早开始执行，或者请求发出之后尽早得到相应。
• 公平性: 每个处理任务的消耗时间长度不会相差太多。

这几点有时相互矛盾，所以对于不同需求采用不同的调度算法尽量满足。

二、常见调度策略

操作系统中可以选择不同的调度算法模块，对任务进行调度，操作系统中常用的调度策略有如下。

1 、先来先服务( FCFS )

按照请求次序进行调度。

实现简单不用对队列进行调整，但是可能因某个元素处理时间过长，出现等待超时。

2、最短作业优先（ SJF ）

按照作业执行的消耗时间，消耗最短时间的先执行。

需要预先估计作业执行时间，耗时较长的作业可能一直得不到执行。

3、基于优先权的调度算法（ FPPS ）

给作业赋予一定优先权，每次从最高优先权的元素中取出一个并执行。

4、时间片轮转（ RR ）

给每个作业赋予一个运行时间片，当时间片到则取下一个元素。

是对 FCFS 和 SJF 算法的折衷，不会出现超时。

5、多级队列调度（ Multilevel feedback queue ）

对任务进行分类，不同分类放置到不同队列中，可能会采用不同的调度算法，队列中元素视情况会在不同队列之间迁移。

如何选择调度策略

以上是常见的策略，实际实现中，经常是几种方案综合实现。

例如windows将多级队列，优先权队列，时间片轮转，以及先进进出方式进行综合，每种优先权任务位于不同队列，高优先权采用时间片轮转方式调度，低优先权采用先进进出方式调度。

有时根据任务等待或者执行程度会调整优先权队列中元素的优先权。

三、为什么选择优先权队列？

假设我们选择优先权队列，这里给出常见的原因：

根据需求，需要对客户请求赋予一定优先级别，并且每个客户执行时间很难预先估计，采用 FPPS 方式实现比较容易接受。

采用一种改进方式：

1. 所有客户请求都包含一定优先级别,所有请求位于一个全局队列当中。
2. 当一个客户达到运行上限，则将该客户对应所有请求优先级别调整到最低（阻塞状态），相当于逻辑上将队列放置到一个阻塞队列中。
3. 每次只从队列中去非阻塞客户的、最高优先级别的请求处理。
4. 如果队列中没有非阻塞的客户，则等待。
5. 当客户释放资源，则会将队列中所有对应该客户端的请求有限级别恢复成阻塞之前。

几个关键点：

1. 优先权数越低则级别越大。（许多地方都这样实现）
2. 优先权队列使用堆方式实现非常常见。（一个是排序算法复杂度低，一个是调整堆的代价小，一个是动态性强）
3. 队列中任务如果处于阻塞，应当调整相应客户到低优先级，这样相当于“阻塞”了当前客户，而不影响其它同优先级客户的调度运行。（同样许多地方如此做）

<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')

其他

更详细资料，参考：

• http://en.wikipedia.org/wiki/Scheduling_(computing)
• http://blog.csdn.net/ppgs8903/article/details/5483428
• http://docs.python.org/library/heapq.html?highlight=heapq#heapq
• http://hg.python.org/cpython/file/2.7/Lib/Queue.py
• http://docs.python.org/library/heapq.html?highlight=heapq#heapq