计算机操作系统--FCFS和SJF代码实现

FCFS实现较简单:
1.按照时间先后到达顺序,进行进程对列的构造
2.有的时候一个进程处理结束但是后一个进程还未到,则后一个进程的完成时间=进程到达时间+进程服务时间
SJF实现有许多细节要注意:终于有用到for...else结构了
1.第一个是最早到达的进程,而不管他是否服务时间最短
2.后面的进程选取服务时间最短的
2.1:有可能进程处理完成后,后面服务时间最短的进程还未到达,则选取其他已经到达且服务时间最短的,我这里实现的是已经到达的进程中的第一个,不一定是服务时间最短的,也不一定是最早的
【计算机操作系统--FCFS和SJF代码实现】2.2:没有则等待服务时间最短的到达(但是还有比他更早到达的呢,这个算法应该要是动态的,但是实现好难)

""" from multiprocessing import Process import time import datetime import os """ import random import functools n = int(input('please input process num:')) MaxNum = 100# 最大进程数 Pid_queue = []# 进程队列 Pid_set = []# 进程集 ArrivalTime = random.sample(range(n), n)# 到达时间 ServiceTime = random.sample(range(1, 13), n)# 服务时间 FinishTime = []# 完成时间 WholeTime = []# 周转时间 WeightWholeTime = []# 带权周转时间 Average_WT_FCFS, Average_WT_SJF = 0, 0# 平均周转时间 Average_WWT_FCFS, Average_WWT_SJF = 0, 0# 平均带权周转时间 absolute_first_index = 0def initial(num): """初始化""" for i in range(num): print("please input {0} process' id:".format(i)) ID = str(input()) Pid_set.append(ID) # sample可以去不重复的数 # ArrivalTime.append(random.sample(range(n), 1)) if ArrivalTime[i] == 0: absolute_first_index = i # ServiceTime.append(random.sample(range(1, 13), 1)) FinishTime.append(0) WholeTime.append(0) WeightWholeTime.append(0)def deinitial(num): global Average_WT_FCFS, Average_WT_SJF, Average_WWT_FCFS, Average_WWT_SJF global Pid_queue for i in range(num): FinishTime[i] = 0 WholeTime[i] = 0 WeightWholeTime[i] = 0 Average_WT_FCFS, Average_WT_SJF = 0, 0# 平均周转时间 Average_WWT_FCFS, Average_WWT_SJF = 0, 0# 平均带权周转时间 Pid_queue = []def display_fcfs(): """打印函数""" print("进程队列:", Pid_queue) print("到达时间:", ArrivalTime) print("服务时间:", ServiceTime) print("完成时间:", FinishTime) print("周转时间:", WholeTime) print("带权周转时间:", WeightWholeTime) print("平均周转时间:", round(Average_WT_FCFS, 2)) print("平均带权周转时间:", round(Average_WWT_FCFS, 2))def display_sjf(): """打印函数""" print("进程队列:", Pid_queue) print("到达时间:", ArrivalTime) print("服务时间:", ServiceTime) print("完成时间:", FinishTime) print("周转时间:", WholeTime) print("带权周转时间:", WeightWholeTime) print("平均周转时间:", round(Average_WT_SJF, 2)) print("平均带权周转时间:", round(Average_WWT_SJF, 2))def FCFS(): """FCFS调度算法""" # 先排序 global Average_WT_FCFS global Average_WWT_FCFS arrival = ArrivalTime.copy() sum_fcfs_wt = 0 sum_fcfs_wwt = 0 for i in range(n): mini = min(arrival) arrival.remove(mini) min_index = i for j in range(n): if ArrivalTime[j] == mini: min_index = j break Pid_queue.append(min_index) # 算FinishTime count = 0 for i in Pid_queue: if count == 0: # 进程队列第一个进程的完成时间这样算 FinishTime[i] += ServiceTime[i] + ArrivalTime[i] else: # 后面的进程的完成时间这么算 if FinishTime[Pid_queue[count-1]] >= ArrivalTime[i]: FinishTime[i] = FinishTime[Pid_queue[count-1]] + ServiceTime[i] else: FinishTime[i] = ArrivalTime[i] + ServiceTime[i] WholeTime[i] = FinishTime[i] - ArrivalTime[i] WeightWholeTime[i] = WholeTime[i]/ServiceTime[i] sum_fcfs_wt += WholeTime[i] sum_fcfs_wwt += WeightWholeTime[i] count += 1 Average_WT_FCFS = sum_fcfs_wt/n Average_WWT_FCFS = sum_fcfs_wwt/n # 打印 display_fcfs() # 重置 deinitial(n)# todo FCFS也有作业未到达的情况,SJF更有 def SJF(): """短作业优先算法需要考虑作业还未到达的情况""" # 先排序 global Average_WWT_SJF global Average_WT_SJF sum_wt_sjf = 0 sum_wwt_sjf = 0 service = ServiceTime.copy() arrival = ArrivalTime.copy() min_time = min(arrival) for i in range(n): min_index = i # 每次选出剩余进程中服务时间最短的 mini = min(service) # service.remove(mini) for j in range(n): if ServiceTime[j] == mini: # service.remove(mini) if ArrivalTime[j] > min_time: for k in range(n): # 感觉还有个bug,同时有多个小于min_time要怎么选取服务时间最短的呢 # 这里是选取第一个小于min_time的 if ArrivalTime[k] <= min_time: min_index = k arrival.remove(ArrivalTime[k]) min_time += ServiceTime[k] break # 最短服务进程到达时间是最早的,但是依旧很慢,得用for...else else: min_time = min(arrival) for x in range(n): if ArrivalTime[x] == min_time: min_index = x arrival.remove(min_time) break else: min_index = j min_time += ServiceTime[j] break service.remove(ServiceTime[min_index]) Pid_queue.append(min_index) count = 0 for i in Pid_queue: if count == 0: FinishTime[i] += ServiceTime[i] else: # 可能服务完成后另一个进程还未到达 # FinishTime[i] += FinishTime[Pid_queue[count-1]] + ServiceTime[i] if FinishTime[Pid_queue[count-1]] >= ArrivalTime[i]: FinishTime[i] = FinishTime[Pid_queue[count-1]] + ServiceTime[i] else: FinishTime[i] = ArrivalTime[i] + ServiceTime[i] WholeTime[i] += FinishTime[i] - ArrivalTime[i] WeightWholeTime[i] += WholeTime[i]/ServiceTime[i] sum_wt_sjf += WholeTime[i] sum_wwt_sjf += WeightWholeTime[i] count += 1 Average_WT_SJF = sum_wt_sjf/n Average_WWT_SJF = sum_wwt_sjf/n # 打印 display_sjf() # 重置 deinitial(n)if __name__ == '__main__': initial(n) # FCFS() SJF()


    推荐阅读