学习笔记 编程与算法

基于Python的进程调度算法实验

最近操作系统的实验课老师要求我们来实现进程调度算法,加之最近又在学习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的运行后面的算法实现就很简单了

1条评论

  1. main()函数的内容可以分享一下吗

发表评论

您的电子邮箱地址不会被公开。