最近操作系统的实验课老师要求我们来实现进程调度算法,加之最近又在学习Python。于是就用Python实现进程调度的几个经典算法:先来先服务、短进程优先、时间片轮转。
算法解析
先简单的介绍一下三种进程调度算法
FCFS先来先服务
讲道理这个算法是最简单的调度算法,就是判断谁先来,先来的就先服务。没啥道理可讲
SJF短进程优先
这个只是FCFS的改进版,防止长进程过长时间占用CPU,因此将CPU设置为优先服务短进程
时间片轮转法
为了应对上述两种方法在,进程并发上的缺陷,将CPU的服务量化为时间片,将CPU的计算资源分配改为按时间片分配。每个进程拥有一定的时间片,从而让每个进程都可以得到相应。当然对于时间片轮转算法可以有很多改进,例如给每个进程加上优先级,优先服务优先级高的程序
算法实现
依据上面说的算法原理,采用OOP的思想(虽然超级不严谨)来进行实现
PCB
众所周知,PCB是进程控制块,也就是计算机中标识程序的那个部分。我们既然要调度进程就需要建立进程,而进程调度肯定不止一个进程,所以我们应该建立一个进程队列。当然只有一个进程队列还是不够的,我们还应该定义进程队列的相关操作。根据上面的三种算法,我们需要具备队列的基本操作要求,还要能找到最先到的程序,找到短进程,找到优先级最高的程序
class PCB: def __init__(self): self.pcbList = {} self.processId = 1000 def addPCB(self, priority, allTime, arriveTime, startBlock, startTime): self.pcbList[self.processId + int(arriveTime)] = { 'priority' : int(priority), 'arriveTime' : int(arriveTime), 'allTime' : int(allTime), 'cpuTime' : 0, 'startBlock' : int(startBlock), 'startTime' : int(startTime), 'innerTime' : int(startBlock), 'status' : True #ready is True block is False } def getPCB(self, id): return {id : self.pcbList['id']} def getList(self): return self.pcbList @staticmethod def pop(queue): if queue: popId = min(queue.keys()) return {popId : queue.pop(popId)} else: return None @staticmethod def pop(queue, popId): if queue: return {popId : queue.pop(popId)} else: return None @staticmethod def head(queue): if queue: popId = min(queue.keys()) return popId else: return None @staticmethod def push(queue, pcb): queue.update(pcb) @staticmethod def setInnerTime(pcb): id = PCB.head(pcb) if pcb[id]['status']: pcb[id]['innerTime'] = pcb[id]['startBlock'] else: pcb[id]['innerTime'] = pcb[id]['startTime'] #pcbList'struct is same with readyqueue and blockqueue @staticmethod def getShortJob(pcb): sjId = PCB.head(pcb) for id in pcb: if pcb[id]['allTime'] < pcb[sjId]['allTime']: sjId = id return sjId @staticmethod def getVipProcess(pcb): vipId = PCB.head(pcb) for id in pcb: if pcb[id]['priority'] > pcb[vipId]['priority']: vipId = id elif pcb[id]['priority'] == pcb[vipId]['priority']: vipId = vipId if pcb[id]['arriveTime'] > pcb[vipId]['arriveTime'] else id return vipId
其中priority代表优先级,arriveTime代表到达时间,allTime表示程序运行需要的时间,cpuTime代表已经使用了多久的CPU,startBlock表示多久后发生阻塞,startTime表示阻塞后多久就绪,innerTime内部计数器,status表示进程当前状态
CPU
既然有了PCB,下面我们就要来实现CPU的进程调度功能了。
class CPU: def __init__(self): workMethod = ['FCFS', 'SJF', 'RAA'] #tip class FCFS: def __init__(self): self.cpuTime = 0 self.needTime = 0 self.readyQueue = {} self.blockQueue = {} self.processCount = 0 def dealTime(self, pcbList): if pcbList: headId = PCB.head(pcbList) if pcbList[headId]['status']: if pcbList[headId]['allTime'] > 0: pcbList[headId]['allTime'] -= 1 pcbList[headId]['cpuTime'] += 1 if pcbList[headId]['innerTime'] > 0: pcbList[headId]['innerTime'] -= 1 self.blockProecss() else: self.finishProcess() else: for id in pcbList: if pcbList[id]['innerTime'] > 0: pcbList[id]['innerTime'] -= 1 self.wakeUpProcess() self.cpuTime += 1 def finishProcess(self): if self.readyQueue: headId = PCB.head(self.readyQueue) if self.readyQueue[headId]['allTime'] == 0: if PCB.pop(self.readyQueue, headId) != None: return True else: return False return False def wakeUpProcess(self): headId = PCB.head(self.blockQueue) if self.blockQueue[headId]['innerTime'] == 0: wakeUpId = PCB.pop(self.blockQueue,headId) wakeUpId[list(wakeUpId.keys())[0]]['status'] = True PCB.setInnerTime(wakeUpId) PCB.push(self.readyQueue, wakeUpId) return True else: return False def blockProecss(self): headId = PCB.head(self.readyQueue) if self.readyQueue[headId]['innerTime'] == 0: blockId = PCB.pop(self.readyQueue,headId) blockId[list(blockId.keys())[0]]['status'] = False PCB.setInnerTime(blockId) PCB.push(self.blockQueue, blockId) return True else: return False def loadProcess(self,pcbList): self.readyQueue = pcbList self.processCount = len(pcbList) for i in pcbList: self.needTime += pcbList[i]['allTime'] def FCFS(self,flag = 0): while self.readyQueue or self.blockQueue: if flag == 0: self.showStatus(self.readyQueue) print("-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*") self.showStatus(self.blockQueue) print("/./././././././././././././././././././././././././././././././././././././././././././././././.") print("\n") time.sleep(0.7) self.dealTime(self.readyQueue) self.dealTime(self.blockQueue) def showStatus(self,queue): if queue: for i in queue: print("process:" + str(i) + " status:" + str(queue[i]['status']) + " remainingTime:" + str(queue[i]['allTime']) + " cpuTime:" + str(self.cpuTime) + " | after " + str(queue[i]['innerTime']) + " second will block or ready") else: print('queue is empty') class SJF: def __init__(self): self.cpuTime = 0 self.needTime = 0 self.readyQueue = {} self.blockQueue = {} self.processCount = 0 def dealTime(self, pcbList): if pcbList: headId = PCB.getShortJob(pcbList) if pcbList[headId]['status']: if pcbList[headId]['allTime'] > 0: pcbList[headId]['allTime'] -= 1 pcbList[headId]['cpuTime'] += 1 if pcbList[headId]['innerTime'] > 0: pcbList[headId]['innerTime'] -= 1 self.blockProecss() else: self.finishProcess() else: for id in pcbList: if pcbList[id]['innerTime'] > 0: pcbList[id]['innerTime'] -= 1 self.wakeUpProcess() self.cpuTime += 1 def finishProcess(self): if self.readyQueue: headId = PCB.getShortJob(self.readyQueue) if self.readyQueue[headId]['allTime'] == 0: if PCB.pop(self.readyQueue, headId) != None: return True else: return False return False def wakeUpProcess(self): headId = PCB.getShortJob(self.blockQueue) if self.blockQueue[headId]['innerTime'] == 0: wakeUpId = PCB.pop(self.blockQueue,headId) wakeUpId[list(wakeUpId.keys())[0]]['status'] = True PCB.setInnerTime(wakeUpId) PCB.push(self.readyQueue, wakeUpId) return True else: return False def blockProecss(self): headId = PCB.getShortJob(self.readyQueue) if self.readyQueue[headId]['innerTime'] == 0: blockId = PCB.pop(self.readyQueue,headId) blockId[list(blockId.keys())[0]]['status'] = False PCB.setInnerTime(blockId) PCB.push(self.blockQueue, blockId) return True else: return False def loadProcess(self,pcbList): self.readyQueue = pcbList self.processCount = len(pcbList) for i in pcbList: self.needTime += pcbList[i]['allTime'] def SJF(self,flag = 0): while self.readyQueue or self.blockQueue: if flag == 0: self.showStatus(self.readyQueue) print("-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*") self.showStatus(self.blockQueue) print("/./././././././././././././././././././././././././././././././././././././././././././././././.") print("\n") time.sleep(0.7) self.dealTime(self.readyQueue) self.dealTime(self.blockQueue) def showStatus(self,queue): if queue: for i in queue: print("process:" + str(i) + " status:" + str(queue[i]['status']) + " remainingTime:" + str(queue[i]['allTime']) + " cpuTime:" + str(self.cpuTime) + " | after " + str(queue[i]['innerTime']) + " second will block or ready") else: print('queue is empty') class RRA: def __init__(self): self.cpuTime = 0 self.needTime = 0 self.readyQueue = {} self.blockQueue = {} self.processCount = 0 def dealTime(self, pcbList): if pcbList: headId = PCB.getVipProcess(pcbList) if pcbList[headId]['status']: if pcbList[headId]['allTime'] > 0: pcbList[headId]['allTime'] -= 1 pcbList[headId]['cpuTime'] += 1 if pcbList[headId]['innerTime'] > 0: pcbList[headId]['innerTime'] -= 1 self.blockProecss() else: self.finishProcess() else: for id in pcbList: if pcbList[id]['innerTime'] > 0: pcbList[id]['innerTime'] -= 1 self.wakeUpProcess() self.cpuTime += 1 def finishProcess(self): if self.readyQueue: headId = PCB.getVipProcess(self.readyQueue) if self.readyQueue[headId]['allTime'] == 0: if PCB.pop(self.readyQueue, headId) != None: return True else: return False return False def wakeUpProcess(self): headId = PCB.getVipProcess(self.blockQueue) if self.blockQueue[headId]['innerTime'] == 0: wakeUpId = PCB.pop(self.blockQueue,headId) wakeUpId[list(wakeUpId.keys())[0]]['status'] = True PCB.setInnerTime(wakeUpId) PCB.push(self.readyQueue, wakeUpId) return True else: return False def blockProecss(self): headId = PCB.getVipProcess(self.readyQueue) if self.readyQueue[headId]['innerTime'] == 0: blockId = PCB.pop(self.readyQueue,headId) blockId[list(blockId.keys())[0]]['status'] = False PCB.setInnerTime(blockId) PCB.push(self.blockQueue, blockId) return True else: return False def loadProcess(self,pcbList): self.readyQueue = pcbList self.processCount = len(pcbList) for i in pcbList: self.needTime += pcbList[i]['allTime'] def RRA(self,flag = 0): while self.readyQueue or self.blockQueue: if flag == 0: self.showStatus(self.readyQueue) print("-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*") self.showStatus(self.blockQueue) print("/./././././././././././././././././././././././././././././././././././././././././././././././.") print("\n") time.sleep(0.7) self.dealTime(self.readyQueue) self.dealTime(self.blockQueue) def showStatus(self,queue): if queue: for i in queue: print("process:" + str(i) + " status:" + str(queue[i]['status']) + " priority:" + str(queue[i]['priority']) + " remainingTime:" + str(queue[i]['allTime']) + " cpuTime:" + str(self.cpuTime) + " | after " + str(queue[i]['innerTime']) + " second will block or ready") else: print('queue is empty')
因为涉及到阻塞和就绪,所以阻塞队列和就绪队列是标配。在我写程序的时候我就在想,如何把控CPU的基本单位时间片。最后采用了一个函数来处理时间,即函数运行一次就认为是一个时间片也就是代码中的dealTime负责。其实只要解决的如何模拟CPU的运行后面的算法实现就很简单了
main()函数的内容可以分享一下吗