Python实战——实现进程调度算法（先来先服务（FCFS）、短作业优先（SJF）和动态最高优先数优先（HRRN）） python

Python实战——实现进程调度算法：FCFS、SJF和HRRN 实验要求进程调度算法：采用先来先服务、短作业、动态最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）。
每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：
进程名—进程标示数 ID
优先数 PRIORITY 优先数越大优先权越高（仅HRRN）
到达时间—进程的到达时间为进程输入的时间。、
进程还需要运行时间ALLTIME，进程运行完毕ALLTIME=0，
已用CPU时间----CPUTIME、
进程开始阻塞时间STARTBLOCK-表示当进程在运行STARTBLOCK个时间片后，进程将进入阻塞状态
进程的阻塞时间BLOCKTIME–表示当进程阻塞BLOCKTIME个时间片后，进程将进入就绪状态
进程状态—STATE
因为FCFS和SJF比较简单，所以写这两个算法时比较粗糙，没有设置阻塞时间，执行时也只是打印执行进程的信息（这俩是白给的）~~
【Python实战——实现进程调度算法（先来先服务（FCFS）、短作业优先（SJF）和动态最高优先数优先（HRRN））】HRRN算法每次都计算作业的优先级，随着作业等待时间的变长，优先级不断的提高，所以能够得到更快的执行。一般优先级的计算方法是：优先级 = (作业已等待时间 + 作业的服务时间) / 作业的服务时间，而这里我只是简单地令进程在等待或阻塞时优先数+1，效果都差不多~~
代码如下运行环境为python 3.7

import random class PCB: def __init__(self,pid,priority,arr_time,all_time,cpu_time,start_block,block_time,state): ##初始化进程 self.pid=pid self.priority=priority self.arr_time=arr_time self.all_time=all_time self.cpu_time=cpu_time self.start_block=start_block self.block_time=block_time self.state=statedef output(self):##hrrn输出 print("进程"+str(self.pid),"优先级："+str(self.priority),"到达时间:"+str(self.arr_time), "还需运行时间:"+str(self.all_time),"已运行时间:"+str(self.cpu_time), "开始阻塞时间："+str(self.start_block),"阻塞时间："+str(self.block_time),"状态："+self.state) def Output(self):##sjf fcfs输出 print("进程"+str(self.pid),"正在执行，到达时间:"+str(self.arr_time), "还需运行时间:"+str(self.all_time),"已运行时间:"+str(self.cpu_time)) def toBlock(self):##将状态置为Block self.state="Block" def toRun(self):##将状态置为Run self.state="Run" def toFinish(self):##将状态置为Finish self.state="Finish" def toReady(self):##将状态置为Ready self.state="Ready" def running(self):##进程运行时状态变化 self.all_time-=1 self.cpu_time+=1 def toBlocking(self):##进程将要开始阻塞的状态变化 if self.start_block>0: self.start_block-=1 def blocking(self):##进程阻塞时的状态变化 if self.block_time>0: self.block_time-=1 self.priority+=1def init(num):##初始化进程，生成四个进程并按到达时间将它们放入列表list1 list1=[] for i in range(num): list1.append(PCB(str(i),random.randint(1,10),random.randint(10,15), random.randint(1,10),0,random.randint(5,10),random.randint(1,10),"Ready")) for i in range(len(list1)-1): for j in range(i+1,len(list1)): if list1[i].arr_time>list1[j].arr_time: list1[i],list1[j]=list1[j],list1[i] return list1def fcfs(list1):##先来先服务 time=0 while 1: print("time:",time) if time>=list1[0].arr_time: list1[0].running() list1[0].Output() if list1[0].all_time==0: print("进程"+list1[0].pid+"执行完毕,周转时间："+str(time-list1[0].arr_time+1)+"\n") list1.remove(list1[0]) time+=1 if not list1: breakdef sjf(list1):##抢占式短作业优先 list2=[]##就绪队列 time=0 while 1: len_list2=len(list2) print("time:",time) if list1: i=0 while 1:##将进程放入就绪队列，就绪队列的第一个是正在执行的进程 if time==list1[i].arr_time: list2.append(list1[i]) list1.remove(list1[i]) pid=list2[0].pid##获取就绪队列第一个进程的进程ID i-=1 i+=1 if i>=len(list1): break if len(list2)>=2 and len(list2)!=len_list2: ##判断就绪队列中最短的作业 len_list2=len(list2) for i in range(len(list2)-1): for j in range(i+1,len(list2)): if list2[i].all_time>list2[j].all_time: list2[i],list2[j]=list2[j],list2[i] if list2: ##执行过程 if pid!=list2[0].pid: ##如果正在执行的进程改变，则发生抢占 print("发生抢占，进程"+list2[0].pid+"开始执行") pid=list2[0].pid list2[0].running() list2[0].Output() if list2[0].all_time==0: print("进程"+list2[0].pid+"执行完毕,周转时间："+str(time-list2[0].arr_time+1)+"\n") list2.remove(list2[0]) if list2: pid=list2[0].pid time+=1 if not list2 and not list1: break def hrrn(list1): ##动态最高优先数优先 list2=[]##就绪队列 list3=[]##阻塞队列 time=0 while 1: print("time:",time) if list1: i=0 while 1: ##将进程放入就绪队列 if time==list1[i].arr_time: list2.append(list1[i]) list1.remove(list1[i]) pid=list2[0].pid i-=1 i+=1 if i>=len(list1): break for i in range(len(list2)-1): ##将就绪队列的进程按优先级大小排列 for j in range(i+1,len(list2)): if list2[i].priority0 or list2[0].block_time<=0: list2[0].toRun() list2[0].running() list2[0].toBlocking() for i in range(1,len(list2)): list2[i].priority+=1 list2[i].toBlocking() if list3: ##阻塞队列 for i in list3: i.blocking()for i in list2: i.output() for i in list3: i.output()if list2:##当进程开始阻塞时间为0，将进程放入阻塞队列 i=0 while 1: if list2: if list2[i].start_block==0 and list2[i].block_time!=0: print("进程"+list2[i].pid+"开始阻塞，进入阻塞队列") list2[i].toBlock() list3.append(list2[i]) list2.remove(list2[i]) i-=1 i+=1 if i>=len(list2): breakif list3:##当进程阻塞时间为0，将进程放入就绪队列 i=0 while 1: if list3[i].block_time==0: print("进程"+list3[i].pid+"阻塞结束，进入就绪队列") list3[i].toReady() list2.append(list3[i]) list3.remove(list3[i]) pid=list2[0].pid i-=1 i+=1 if i>=len(list3): breakif list2: ##进程执行完毕则移出就绪队列 if list2[0].all_time<=0: list2[0].toFinish() print("进程"+list2[0].pid+"执行完毕，周转时间："+str(time-list2[0].arr_time+1),"状态："+list2[0].state+"\n") list2.remove(list2[0]) if list2: pid=list2[0].pidtime+=1 if not (list1 or list2 or list3): break if __name__=="__main__": while 1: n=input("请选择算法(1、先来先服务2、抢占式短作业优先3、动态最高优先数优先):") if n=="1": list1=init(4) for i in list1: i.Output() fcfs(list1) elif n=="2": list1=init(4) for i in list1: i.Output() sjf(list1) elif n=="3": list1=init(4) for i in list1: i.output() hrrn(list1) else: print("输入错误，请重新输入！")

运行结果如下 FCFS（仅截取部分）

Python实战——实现进程调度算法（先来先服务（FCFS）、短作业优先（SJF）和动态最高优先数优先（HRRN））

文章图片

SJF（仅截取部分）

文章图片

HRRN（仅截取部分）

文章图片

文章图片

进程的所有信息都是用Random库随机生成，因为一个个输入太麻烦~~
程序执行时只需选择调度算法，执行过程不需要任何操作
特别需要注意的是：在循环的每一秒中，输出信息和具体的操作一定要分开！一定要分开！一定要分开！要么先打印后操作，要么先操作后打印，不要边操作边打印，会混乱的~
亲身经历总结出的教训~