实验:模拟作业调度算法

内容

  • 先来先服务法FCFS

  • 短作业优先法SJF

  • 最高响应比优先HRRN

  • 时间片轮转RR

1. 基本概念

2. FCFS

  • 有利于长作业，不利于短作业

3. SJF

  • 降低作业的平均等待时间，提高系统吞吐量
  • 对长作业不利，严重的会导致长作业长期的得不到执行
  • 未考虑作业紧迫程度

4. HRRN

Highest Response Ratio Next

  • $优先权=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}$
  • 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，转化为短作业优先。
  • 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，转化为先来先服务。

5. RR

Round-Robin

  • 简单时间片轮转法
    • 进程排成队列、先来先服务

6. 实现

测试数据t_data

1
2
3
4
5
6
#作业编号  作业名称  提交时间  要求服务运行时间（分钟）
1      JA       02:40     20
2      JB       02:50     30
3      JC       02:55     10
4      JD       03:00     24
5      JE       03:05     6

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
from datetime import datetime, timedelta
import threading
import time
time_piece = timedelta(minutes=10)


class JCB:
    pass


class JobThread(threading.Thread):

    def __init__(self, tmp):
        super(JobThread, self).__init__()
        self.__flag = threading.Event()     # 用于暂停线程的标识
        self.__flag.set()       # 设置为True
        self.__running = threading.Event()      # 用于停止线程的标识
        self.__running.set()      # 将running设置为True
        self.tmp = tmp  # JCB
        self.rtime = timedelta(minutes=0)

    def run(self, ctime):
        while self.__running.isSet():
            self.resume()
            self.__flag.wait()      # 为True时立即返回, 为False时阻塞直到内部的标识位为True后返回
            ctime = self.doSlice(ctime)
            return ctime

    def pause(self):
        self.__flag.clear()     # 设置为False, 让线程阻塞

    def resume(self):
        self.__flag.set()    # 设置为True, 让线程停止阻塞

    def stop(self):
        self.__flag.set()       # 将线程从暂停状态恢复, 如果已经暂停的话
        self.__running.clear()        # 设置为False

    def doSlice(self, ctime):
        self.__flag.set()
        if(self.tmp.pull > ctime):
            print("job {0} error.".format(self.tmp.index))
            self.pause()
        print("job {0} begin.".format(self.tmp.index))
        if(self.tmp.begin == None):
            self.tmp.begin = ctime
        if self.rtime+time_piece < timedelta(minutes=int(self.tmp.need)):
            ctime += time_piece
            self.rtime += time_piece
            print("job {0} pause.".format(self.tmp.index))
            self.pause()
            return ctime
        else:
            ctime += timedelta(minutes=int(self.tmp.need))-self.rtime
            self.tmp.end = ctime
            self.tmp.wait = (self.tmp.begin-self.tmp.pull).seconds//60
            self.tmp.turnover = (self.tmp.end-self.tmp.begin).seconds//60
            self.tmp.weighted_turnover = round(
                self.tmp.turnover/int(self.tmp.need), 2)
            print("job {0} stop.".format(self.tmp.index))
            self.stop()
            return ctime

    def getSatus(self):
        if self.__running.isSet():
            return True
        return False


def setJCB(jobs):
    dumbdate = datetime(1900, 1, 1, 0, 0, 0)
    with open('t.txt', 'r+', encoding='utf-8') as f:
        for line in f.readlines():
            j = JCB()
            j.index, j.name, _, j.need = line[:-1].split()
            j.pull = datetime.strptime(_, "%H:%M")-dumbdate
            j.begin = j.end = j.wait = j.turnover = None
            jobs.append(j)


def showInfo(tmp):
    for k, v in vars(tmp).items():
        print("{0}: {1}".format(k, v), end='\t')
    print('')


def showAvg(jobs):
    a = '%.2f' % (sum(x.turnover for x in jobs)/len(jobs))
    b = '%.2f' % (sum(x.weighted_turnover for x in jobs)/len(jobs))
    print('Average_totime = {0}\tAverage_wtotime = {1}\n'.format(a, b))


def doJob(tmp, rtime):
    tmp.begin = rtime if rtime >= tmp.pull else tmp.pull
    tmp.end = tmp.begin+timedelta(minutes=int(tmp.need))
    tmp.wait = (tmp.begin-tmp.pull).seconds//60
    tmp.turnover = (tmp.end-tmp.pull).seconds//60
    tmp.weighted_turnover = round(tmp.turnover/int(tmp.need), 2)
    rtime = tmp.end
    showInfo(tmp)
    return rtime

简要说明

  • JCB类

    • 定义作业信息，相当于c语言中的结构体struct

  • JobThread类

    • 定义线程及线程的暂停、恢复以及终止操作，用于RR算法

  • rtime变量

    • run_time：记录运行时间

  • ctime变量

    • current_time：记录当前事件

  • time_piece变量

    • RR算法中时间分片的大小

  • dumbdate变量

    • 由于datetime.strptime默认会在按1900-1-1 00:00:00补全，所以需要减去不必要的（或者说是错误的）信息
    • 注意到减去dumbdate后，将使变量pull从datetime.datetime转化为datetime.timedelta

7. 分别实现

FCFS

  • 代码

    1
    2
    3
    4
    5
    6
    def FCFS(jobs):
        jobs.sort(key=lambda x: (x.pull, x.index))
        rtime = timedelta(minutes=0)
        for tmp in jobs[:]:
            rtime = doJob(tmp, rtime)
        showAvg(jobs)

  • 结果

    1
    2
    3
    4
    5
    6
    index: 1	name: JA	need: 20	pull: 2:40:00	begin: 2:40:00	end: 3:00:00	wait: 0	turnover: 20	weighted_turnover: 1.0	
    index: 2	name: JB	need: 30	pull: 2:50:00	begin: 3:00:00	end: 3:30:00	wait: 10	turnover: 40	weighted_turnover: 1.33	
    index: 3	name: JC	need: 10	pull: 2:55:00	begin: 3:30:00	end: 3:40:00	wait: 35	turnover: 45	weighted_turnover: 4.5	
    index: 4	name: JD	need: 24	pull: 3:00:00	begin: 3:40:00	end: 4:04:00	wait: 40	turnover: 64	weighted_turnover: 2.67	
    index: 5	name: JE	need: 6	pull: 3:05:00	begin: 4:04:00	end: 4:10:00	wait: 59	turnover: 65	weighted_turnover: 10.83	
    Average_totime = 46.80	Average_wtotime = 4.07

SJF

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def SJF(jobs):
        job = []
        rtime = timedelta(minutes=0)
        while(len(jobs) != 0):
            tp = [x for x in jobs if rtime >= x.pull]
            if(tp == []):
                tmp = min(jobs, key=lambda x: (x.pull, x.index))
            else:
                tmp = min(tp, key=lambda x: (int(x.need), x.index))
            rtime = doJob(tmp, rtime)
            jobs.remove(tmp)
            job.append(tmp)
        showAvg(job)

  • 结果

    1
    2
    3
    4
    5
    6
    index: 1	name: JA	need: 20	pull: 2:40:00	begin: 2:40:00	end: 3:00:00	wait: 0	turnover: 20	weighted_turnover: 1.0	
    index: 3	name: JC	need: 10	pull: 2:55:00	begin: 3:00:00	end: 3:10:00	wait: 5	turnover: 15	weighted_turnover: 1.5	
    index: 5	name: JE	need: 6	pull: 3:05:00	begin: 3:10:00	end: 3:16:00	wait: 5	turnover: 11	weighted_turnover: 1.83	
    index: 4	name: JD	need: 24	pull: 3:00:00	begin: 3:16:00	end: 3:40:00	wait: 16	turnover: 40	weighted_turnover: 1.67	
    index: 2	name: JB	need: 30	pull: 2:50:00	begin: 3:40:00	end: 4:10:00	wait: 50	turnover: 80	weighted_turnover: 2.67	
    Average_totime = 33.20	Average_wtotime = 1.73

HRRN

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def HRRN(jobs):
        job = []
        rtime = timedelta(minutes=0)
        while(len(jobs) != 0):
            tp = [x for x in jobs if rtime >= x.pull]
            if(tp == []):
                tmp = min(jobs, key=lambda x: (x.pull, x.index))
            else:
                tmp = max(tp, key=lambda x: (
                    (int(x.need)+(rtime-x.pull).seconds//60)/int(x.need), x.index))
            rtime = doJob(tmp, rtime)
            jobs.remove(tmp)
            job.append(tmp)
        showAvg(job)

  • 结果

    1
    2
    3
    4
    5
    6
    index: 1	name: JA	need: 20	pull: 2:40:00	begin: 2:40:00	end: 3:00:00	wait: 0	turnover: 20	weighted_turnover: 1.0	
    index: 3	name: JC	need: 10	pull: 2:55:00	begin: 3:00:00	end: 3:10:00	wait: 5	turnover: 15	weighted_turnover: 1.5	
    index: 5	name: JE	need: 6	pull: 3:05:00	begin: 3:10:00	end: 3:16:00	wait: 5	turnover: 11	weighted_turnover: 1.83	
    index: 2	name: JB	need: 30	pull: 2:50:00	begin: 3:16:00	end: 3:46:00	wait: 26	turnover: 56	weighted_turnover: 1.87	
    index: 4	name: JD	need: 24	pull: 3:00:00	begin: 3:46:00	end: 4:10:00	wait: 46	turnover: 70	weighted_turnover: 2.92	
    Average_totime = 34.40	Average_wtotime = 1.82

RR

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def RR(jobs):
        job = []  # 线程数组
        rjob = []  # 结果数组
        rtime = timedelta(minutes=0)
        jobs.sort(key=lambda x: (x.pull, x.index))
        for i in range(len(jobs)):
            tp = JobThread(jobs[i])
            job.append(tp)
        ctime = jobs[0].pull  # current time
        while(True):
            tp = job.copy()
            for i in tp:
                ctime = i.run(ctime)
                if i.getSatus() == False:
                    rjob.append(i.tmp)
                    job.remove(i)
            print('')
            if(len(job) == 0):
                break
        for i in rjob:
            showInfo(i)
        showAvg(rjob)

  • 结果( 时间片 $time_piece=10min$ )

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    job 1 begin.
    job 1 pause.
    job 2 begin.
    job 2 pause.
    job 3 begin.
    job 3 stop.
    job 4 begin.
    job 4 pause.
    job 5 begin.
    job 5 stop.

    job 1 begin.
    job 1 stop.
    job 2 begin.
    job 2 pause.
    job 4 begin.
    job 4 pause.

    job 2 begin.
    job 2 stop.
    job 4 begin.
    job 4 stop.

    index: 3	name: JC	need: 10	pull: 2:55:00	begin: 3:00:00	end: 3:10:00	wait: 5	turnover: 10	weighted_turnover: 1.0	
    index: 5	name: JE	need: 6	pull: 3:05:00	begin: 3:10:00	end: 3:26:00	wait: 5	turnover: 16	weighted_turnover: 2.67	
    index: 1	name: JA	need: 20	pull: 2:40:00	begin: 2:40:00	end: 3:36:00	wait: 0	turnover: 56	weighted_turnover: 2.8	
    index: 2	name: JB	need: 30	pull: 2:50:00	begin: 3:16:00	end: 4:06:00	wait: 26	turnover: 50	weighted_turnover: 1.67	
    index: 4	name: JD	need: 24	pull: 3:00:00	begin: 3:46:00	end: 4:10:00	wait: 46	turnover: 24	weighted_turnover: 1.0	
    Average_totime = 31.20	Average_wtotime = 1.83

8. 参考资料

python-线程的暂停, 恢复, 退出 - scolia - 博客园