最近操作系统的实验课老师要求我们来实现进程调度算法，加之最近又在学习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()函数的内容可以分享一下吗