操作系统的进程调度算法(python语言实现)

一、实验内容

（1）优先权法、轮转法

简化假设
1） 进程为计算型的（无I/O）
2） 进程状态：ready、running、finish
3） 进程需要的CPU时间以时间片为单位确定

（2） 算法描述

1） 优先权法——动态优先权
当前运行进程用完时间片后，其优先权减去一个常数。
2） 轮转法

参考书本：计算机操作系统第四版 汤小丹 梁红兵等编

二、流程图

动态优先级(左)——轮转法(右)

三、实验分析

（1）如何表示进程，一个进程应该包含哪些必要信息
在操作系统中，每个进程都有一个专用数据结构PCB——进程控制块来记录os所需的，用于描述进程的当前情况以及管理进程运行的全部信息。一般包含进程标识符、处理机状态、进程调度信息，进程控制信息四个部分。

本实验只是模拟处理机调度，所以我选择创建一个pcb类来表示进程，该PCB类的属性包括进程序号id（表示到达的先后顺序）、状态state、开始执行时间starttime、执行结束时间endtime、所需执行时间cputime，剩余执行时间restoftime,已运行时间runtime。还包括显示pcb的方法。

我将所有的进程保存在一个列表中，表示他们都是0时刻进入内存，id表示到达顺序。

具体代码如下

class PCB :
    def __init__(self, id, prior, cputime) :
        # id:序号 prior优先级 cputime:进程所需时间
        self.id = id
        self.prior = prior      #这是初始值的优先级，不会再变了，可以看做静态优先级
        self.dy_prior = prior   #动态优先级，每执行一次要减一
        self.cputime = cputime
        self.runtime = 0  # 进程已运行的时间，就是流程图中已占用CPU时间片数，每执行一次-1
        self.restoftime = cputime   # 还需要的运行的时间，
        self.state = 0  # 0表示ready 1表示running 2表示finish
        self.starttime = 0    #进程开始运行的时间
        self.endtime = 0     #进程结束运行时间

    def outSituation_dy(self) :  #输出动态优先级法进程运行情况
        state_temp = ''
        if self.state == 0:
            state_temp = 'ready'
        elif self.state == 1:
            state_temp = 'running'
        elif self.state == 2 :
            state_temp = 'finish'
        print(("进程:" + str(self.id) + '\t' +"动态优先级:%-3d" + " 当前状态:%-7s" + "  进程所需CPU时间:%-2d" +
               "  还需时间:" + str(self.restoftime))%(self.dy_prior,state_temp,self.cputime))

    def outSituation_rr(self) :  #输出rr法进程运行情况
        state_temp = ''
        if self.state == 0:
            state_temp = 'ready'
        elif self.state == 1:
            state_temp = 'running'
        elif self.state == 2 :
            state_temp = 'finish'
        print(("进程:" + str(self.id) + " 当前状态:%-7s" + "  进程所需CPU时间:%-2d" +
               "  还需时间:" + str(self.restoftime))%(state_temp,self.cputime))

    def outall_dy(self) :  #输出动态优先级法进程运行总体情况
        state_temp = ''
        if self.state == 0:
            state_temp = 'ready'
        elif self.state == 1:
            state_temp = 'running'
        elif self.state == 2 :
            state_temp = 'finish'
        print(("进程:" + str(self.id) + '\t' +"静态优先级:%-3d" + " 当前状态:%-7s" + "进程所需CPU时间:%-2d" + " 开始运行时间：%-2d" +
               " 结束运行时间：%-3d"+" 还需时间:" + str(self.restoftime))%(self.prior,state_temp,self.cputime,self.starttime,self.endtime,))

    def outall_rr(self) :  #输出rr法进程运行总体情况
        state_temp = ''
        if self.state == 0:
            state_temp = 'ready'
        elif self.state == 1:
            state_temp = 'running'
        elif self.state == 2 :
            state_temp = 'finish'
        print(("进程:" + str(self.id) + " 当前状态:%-7s" + "进程所需CPU时间:%-2d" + " 开始运行时间：%-2d" +
               " 结束运行时间：%-3d"+" 还需时间:" + str(self.restoftime))%(state_temp,self.cputime,self.starttime,self.endtime,))

（2）只要输入进程数并选择算法，初始化的进程队列全部是随机产生。代码如下

def init(num) :
    pcbList = []
    for i in range(num) :
        pcbList.append(PCB(i, random.randint(1, 9), random.randint(1, 20)))
        # 将随机产生的n个进程保存，里面分别是进程id,优先级，CPU时间
    print("刚生成的各进程")
    for i in pcbList:  #输出最开始时进程情况
        i.outSituation_dy()
    print('\n')
    return pcbList

（3）在动态优先级中，采用冒泡排序来给队列优先级排序。相同优先级，先到达的排在前面。

（4）在流程图中，存在就绪队列。我只有一个存放pcb的列表。所以我每次执行完队首进程，将当前进程列表重新排序，保证每次执行的队首进程永远是可执行的优先级最大的进程。

四、完整代码及输出

（1）完整代码

import random

class PCB :
    def __init__(self, id, prior, cputime) :
        # id:序号 prior优先级 cputime:进程所需时间
        self.id = id
        self.prior = prior      #这是初始值的优先级，不会再变了，可以看做静态优先级
        self.dy_prior = prior   #动态优先级，每执行一次要减一
        self.cputime = cputime
        self.runtime = 0  # 进程已运行的时间，就是流程图中已占用CPU时间片数，每执行一次-1
        self.restoftime = cputime   # 还需要的运行的时间，
        self.state = 0  # 0表示ready 1表示running 2表示finish
        self.starttime = 0    #进程开始运行的时间
        self.endtime = 0     #进程结束运行时间

    def outSituation_dy(self) :  #输出动态优先级法进程运行情况
        state_temp = ''
        if self.state == 0:
            state_temp = 'ready'
        elif self.state == 1:
            state_temp = 'running'
        elif self.state == 2 :
            state_temp = 'finish'
        print(("进程:" + str(self.id) + '\t' +"动态优先级:%-3d" + " 当前状态:%-7s" + "  进程所需CPU时间:%-2d" +
               "  还需时间:" + str(self.restoftime))%(self.dy_prior,state_temp,self.cputime))

    def outSituation_rr(self) :  #输出rr法进程运行情况
        state_temp = ''
        if self.state == 0:
            state_temp = 'ready'
        elif self.state == 1:
            state_temp = 'running'
        elif self.state == 2 :
            state_temp = 'finish'
        print(("进程:" + str(self.id) + " 当前状态:%-7s" + "  进程所需CPU时间:%-2d" +
               "  还需时间:" + str(self.restoftime))%(state_temp,self.cputime))

    def outall_dy(self) :  #输出动态优先级法进程运行总体情况
        state_temp = ''
        if self.state == 0:
            state_temp = 'ready'
        elif self.state == 1:
            state_temp = 'running'
        elif self.state == 2 :
            state_temp = 'finish'
        print(("进程:" + str(self.id) + '\t' +"静态优先级:%-3d" + " 当前状态:%-7s" + "进程所需CPU时间:%-2d" + " 开始运行时间：%-2d" +
               " 结束运行时间：%-3d"+" 还需时间:" + str(self.restoftime))%(self.prior,state_temp,self.cputime,self.starttime,self.endtime,))

    def outall_rr(self) :  #输出rr法进程运行总体情况
        state_temp = ''
        if self.state == 0:
            state_temp = 'ready'
        elif self.state == 1:
            state_temp = 'running'
        elif self.state == 2 :
            state_temp = 'finish'
        print(("进程:" + str(self.id) + " 当前状态:%-7s" + "进程所需CPU时间:%-2d" + " 开始运行时间：%-2d" +
               " 结束运行时间：%-3d"+" 还需时间:" + str(self.restoftime))%(state_temp,self.cputime,self.starttime,self.endtime,))

def init(num) :
    pcbList = []
    for i in range(num) :
        pcbList.append(PCB(i, random.randint(1, 9), random.randint(1, 20)))
        # 将随机产生的n个进程保存，里面分别是进程id,优先级，CPU时间
    print("刚生成的各进程")
    for i in pcbList:  #输出最开始时进程情况
        i.outSituation_dy()
    print('\n')
    return pcbList

def sort_dy_pcblist(pcbList): #按优先级将进程排序，[0:]优先级依次减小
    for i in range(1,len(pcbList)): #冒泡排序
        for j in range(0,len(pcbList)-1):
            if pcbList[i].dy_prior > pcbList[j].dy_prior:
                pcbList[i], pcbList[j] = pcbList[j], pcbList[i]
    for i in range(len(pcbList)-1):  #相同优先级的，id小的排在前面
        if pcbList[i].dy_prior == pcbList[i+1].dy_prior:
            if pcbList[i].id > pcbList[i+1].id:
                pcbList[i],pcbList[i + 1] = pcbList[i + 1], pcbList[i]
    if pcbList[0].state == 2 :  #保证首位不是finish 如果是，和后面第一个ready交换
        for i in range(1,len(pcbList)):
            if pcbList[i].state == 0 :
                pcbList[i],pcbList[0] = pcbList[0],pcbList[i]
                break
    return pcbList

def sort_rr_pcblist(pcbList):  #将进程插到队列尾
    pcbList.append(pcbList[0])
    del pcbList[0]
    if pcbList[0].state == 2 :  #保证首位不是finish 如果是，和后面第一个ready交换
        for i in range(1,len(pcbList)):
            if pcbList[i].state == 0 :
                pcbList[i],pcbList[0] = pcbList[0],pcbList[i]
                break
    return pcbList

def dy_prior_method(pcbList) :  #动态优先级法
    count = 0
    while pcbList[0].state == 0:  #只要首进程状态为ready，就说明还有进程未执行
        print("这是第%d次时间片"%count)
        if pcbList[0].dy_prior == pcbList[0].prior :
            pcbList[0].starttime = count
        pcbList[0].state = 1      #状态变更为running
        pcbList[0].runtime += 1
        pcbList[0].dy_prior -= 3
        pcbList[0].restoftime -= 1
        for i in pcbList :  # 输出进程情况
            i.outSituation_dy()
        if pcbList[0].restoftime == 0:
            pcbList[0].state = 2
            pcbList[0].endtime = count
        else :
            pcbList[0].state = 0
        sort_dy_pcblist(pcbList)
        count += 1

    # 显示进程运行总体情况
    print("                 动态优先级         总 体 情 况                   ")
    # 输出完成时进程情况
    Turnaround_time = 0   #总周转时间周转
    daiquan_time = 0      #总带权周转时间
    for j in range(len(pcbList)): #按id顺序输出
        for i in pcbList:
            if i.id == j :
                i.outall_dy()
    for i in pcbList :  # 计算平均周转时间
        Turnaround_time += i.endtime - i.starttime+1   #时间从0开始，两个相减就少了一段时间片
        daiquan_time += (i.endtime-i.starttime+1)/i.cputime
    print(('平均周转时间：%.2f'+'  平均带权周转时间%.2f')%(Turnaround_time/len(pcbList),daiquan_time/len(pcbList)))
    #周转时间就是就是执行完成的时间-开始执行的时间
    #带权周转时间就是  周转时间/所需时间


#轮转法比动态优先级简单，直接对着流程图抄上一个函数就好了。
def rr_method(pcbList) :   #轮转法
    rr_time = random.randint(1,5) #随机产生一个时间片  流程图害人
    count = 0
    time = 0  #每个进程已经占用的时间片，time<=rr_time
    while pcbList[0].state == 0 :
        print("这是第%d次时间片"%count)
        time += 1
        if pcbList[0].dy_prior == pcbList[0].prior :
            #首次执行就改变动态优先级，这个参数在这里没啥用，不如废物利用
            pcbList[0].starttime = count
            pcbList[0].dy_prior = 21 #要保证比随机数大
        pcbList[0].state = 1      #状态变更为running
        pcbList[0].runtime +=  1
        pcbList[0].restoftime -=  1
        for i in pcbList :  # 输出进程情况
            i.outSituation_rr()
        if pcbList[0].restoftime == 0:
            pcbList[0].state = 2
            pcbList[0].endtime = count
            sort_rr_pcblist(pcbList)
            time = 0
        else :
            pcbList[0].state = 0
            if time == rr_time :
                time = 0
                sort_rr_pcblist(pcbList)
        count += 1

    #显示进程运行总体情况
    print("                 轮转法         总 体 情 况                   ")
    # 输出完成时进程情况
    print("轮转时间片 q = "+str(rr_time))
    Turnaround_time = 0  # 总周转时间周转
    daiquan_time = 0  # 总带权周转时间
    for j in range(len(pcbList)) : #按id顺序输出
        for i in pcbList :
            if i.id == j :
                i.outall_rr()
    for i in pcbList :  # 计算平均周转时间
        Turnaround_time += i.endtime - i.starttime + 1  # 时间从0开始，两个相减就少了一段时间片
        daiquan_time += (i.endtime - i.starttime + 1) / i.cputime
    print(('平均周转时间：%.2f' + '  平均带权周转时间%.2f') % (Turnaround_time / len(pcbList), daiquan_time / len(pcbList)))

def main() :
    pcbNum = int(input("输入进程数量(4,8)："))
    print("请从以下方法中选择一种进程调度方法")
    print("（1）动态优先级法 （2）轮转法")
    method = int(input())
    pcbList = init(pcbNum)
    if method == 1 :
        dy_prior_method(pcbList)
    else :
        rr_method(pcbList)

if __name__ == '__main__' :
    main()

（2）输出

1. 先输出随机数生成的原始进程数据
2. 再输出每个时间片的进程运行情况
3. 最后输出进程的总体执行情况（周转时间等）

只展示轮转法的部分输出

本文地址：https://blog.csdn.net/weixin_42572826/article/details/107080192