计算机操作系统--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()
推荐阅读
- 操作系统|[译]从内部了解现代浏览器(1)
- ACSL|ACSL 美国计算机科学联赛 2016-2017 R4 摩天大楼-Skyscraper 题解
- 历史上的今天|【历史上的今天】2 月 16 日(世界上第一个 BBS 诞生;中国计算机教育开端;IBM 机器人赢得智能竞赛)
- 计算机网络基础TCP\HTTP\HTTPS
- 计算机网络|计算机网络——DHCP协议详解
- android|android today上下卡片,【精品文档】关于计算机专业大学生安卓系统有关的外文文献翻译成品(基于Android(安卓)的考勤管理系统(中英文双语对照)
- 计算机与时间
- 中国农业大学计算机就业薪资,2020年工资出炉,这个行业倒数第一,不过这类大学专业有金矿可挖...
- 网络|简单聊聊压缩网络
- 计算机教学楼起名,给教学楼起名字(富有诗意教学楼名字)