最近操作系统的实验课老师要求我们来实现进程调度算法，加之最近又在学习Python。于是就用Python实现进程调度的几个经典算法：先来先服务、短进程优先、时间片轮转。
算法解析
先简单的介绍一下三种进程调度算法
FCFS先来先服务
讲道理这个算法是最简单的调度算法，就是判断谁先来，先来的就先服务。没啥道理可讲
SJF短进程优先
这个只是FCFS的改进版，防止长进程过长时间占用CPU，因此将CPU设置为优先服务短进程
时间片轮转法
为了应对上述两种方法在，进程并发上的缺陷，将CPU的服务量化为时间片，将CPU的计算资源分配改为按时间片分配。每个进程拥有一定的时间片，从而让每个进程都可以得到相应。当然对于时间片轮转算法可以有很多改进，例如给每个进程加上优先级，优先服务优先级高的程序
算法实现
依据上面说的算法原理，采用OOP的思想（虽然超级不严谨）来进行实现
PCB
众所周知，PCB是进程控制块，也就是计算机中标识程序的那个部分。我们既然要调度进程就需要建立进程，而进程调度肯定不止一个进程，所以我们应该建立一个进程队列。当然只有一个进程队列还是不够的，我们还应该定义进程队列的相关操作。根据上面的三种算法，我们需要具备队列的基本操作要求，还要能找到最先到的程序，找到短进程，找到优先级最高的程序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
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的进程调度功能了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 |
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()函数的内容可以分享一下吗