python *** 作系统调度算法仿真程序

python *** 作系统调度算法仿真程序 调度算法仿真程序

1. 实验要求
   编程完成对先来先服务、短作业优先和高响应比优先三种作业调度算法。
2. 代码

import threading
import datetime
import time
import numpy as np
import random
import argparse
    
class Job(threading.Thread):
    def __init__(self, id, name,arrive):
        super(Job,self).__init__()
        self.id = id
        self.name = name
        self.arrive = arrive
        self.wait = datetime.timedelta(seconds=0)
        self.runtime = datetime.timedelta(seconds=np.random.rand()*
            np.random.randint(1,100))
        self.isfinish = False
    def run(self):
        print("Start job:",self.name,'at',self.arrive,'wait',self.wait)
        end_t = self.arrive + self.runtime
        #time.sleep(self.runtime)
        print("Exit job:",self.name,'at',end_t)
        print()
        self.isfinish = True
        return end_t
def average_turnaround(jobs):
    return sum([job.wait/datetime.timedelta(seconds=1)+
        job.runtime/datetime.timedelta(seconds=1)
             for job in jobs])/len(jobs)

def weighted_turnaround(jobs):
    return sum([(job.wait/datetime.timedelta(seconds=1)+
        job.runtime/datetime.timedelta(seconds=1))/(job.runtime/
            datetime.timedelta(seconds=1)) for job in jobs])/len(jobs)

def FCFS(start_t,jobs):
    end_t = start_t
    for job in jobs:
        if end_t other_job.arrive 
                and min_t > other_job.runtime/datetime.timedelta(seconds=1):
                serve = other_job
                flag = False
                min_t = other_job.runtime/datetime.timedelta(seconds=1)
        if flag:
            end_t = job.run()
        else:
            serve.wait = end_t - serve.arrive
            end_t = serve.run()
def HRRN(start_t,jobs):
    end_t = start_t
    for job in jobs:
        min_t = np.inf
        serve = job
        flag = True
        for other_job in jobs:
            if (not other_job.isfinish) 
                and end_t > other_job.arrive 
                and min_t > ((other_job.arrive-end_t)/datetime.timedelta(seconds=1))/
                    (other_job.runtime/datetime.timedelta(seconds=1)):
                serve = other_job
                flag = False
                min_t = other_job.runtime/datetime.timedelta(seconds=1)
        if flag:
            end_t = job.run()
        else:
            serve.wait = end_t - serve.arrive
            end_t = serve.run()

parser = argparse.ArgumentParser(description="OS exp1")
parser.add_argument('--fcfs', action='store_true', default=False,
                    help="use FCFS")
parser.add_argument('--sjf', action='store_true', default=False,
                    help="use SJF")
parser.add_argument('--hrrn', action='store_true', default=False,
                    help="use HRRN")
args = parser.parse_args()
start_t = datetime.datetime.now()
CHAR_SET = [chr(ord('A')+i) for i in range(26)]+
    [chr(ord('a')+i) for i in range(26)]+
    [chr(ord('0')+i) for i in range(10)]
num_jobs = np.random.randint(5,20)
jobs = []
for i in range(num_jobs):
    runtime = datetime.timedelta(seconds=np.random.rand()*np.random.randint(1,100))
    arrive = start_t + runtime
    jobs.append(Job(id=i,name=''.join(random.sample(CHAR_SET, 4)),arrive=arrive))
    #time.sleep(runtime)
if args.fcfs:
    FCFS(start_t=start_t,jobs=jobs)
elif args.sjf:
    SJF(start_t=start_t,jobs=jobs)
elif args.hrrn:
    HRRN(start_t=start_t,jobs=jobs)
print('平均周转时间:',average_turnaround(jobs))
print('加权周转时间:',weighted_turnaround(jobs))

3. 模拟优化
   • 注释掉time.sleep()以节省执行时间，为了追求真实情况，可以取消注释并全部改成真实时间
   • 随机初始化[5,20)个作业，每个作业执行时间为[0,100)s，每个作业到来时间离上一个作业的到来时间为[0,1000)s
   • I/O *** 作时间忽略不计
   • 为了贴近真实情况，一次性只能执行一种算法。
4. 评价指标

符号含义 t 0 t_0 t0​周转时间 t w t_w tw​等待时间 t r t_r tr​运行时间 t o t_o to​I/O时间 n n n作业数 A T A_T AT​平均周转时间 W T W_T WT​加权周转时间

t 0 = t w + t r + t o t_0 = t_w + t_r + t_o t0​=tw​+tr​+to​
A T = 1 n ∑ i = 0 n t 0 A_T = frac{1}{n}sum_{i=0}^n t_0 AT​=n1​i=0∑n​t0​
W T = 1 n ∑ i = 0 n t 0 t r W_T = frac{1}{n}sum_{i=0}^n frac{t_0}{t_r} WT​=n1​i=0∑n​tr​t0​​
5. 分析：
结合学习和将随机数改变为固定数得出以下结论：
* 短作业优先算法的平均周转时间和加权周转时间低于其他两个算法
* 高响应比优先算法更适用于大型作业
* 先来先算法实现更简单，对于短作业来说
6. 运行方式

python exp1.py --fcfs #执行先来先
python exp1.py --sjf  #执行短作业优先
python exp1.py --hrrn #执行高响应比优先