先来先服务调度算法、短作业优先调度算法、时间片轮转调度算法和优先级调度算法的实现（python）_进程调度短作业优先算法的实现

作者：笔触狂放9 | 2024-05-17 06:38:25

踩

进程调度短作业优先算法的实现

一、算法简介:

先来先服务算法（FCFS）：系统将按照作业到达的先后次序来进行调度，优先从后备队列中，选择一个或多个位于队列头部的作业，把他们调入内存，分配所需资源、创建进程，然后放入“就绪队列”；
短作业优先调度算法（SJF）：以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。；
时间片轮转调度算法（RR）：每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾；
优先级调度算法（HRRN）：优先级进程调度算法，是为每个作业设置一个优先权（响应比），然后把处理机分配给就绪队列中优先级最高的进程，在这里我们使用的是动态优先级，即在每次调度之前计算每个进程的优先级：RR（优先级） = 作业周转时间/作业运行时间 = 1 + 作业等待时间/作业运行时间。
大概流程：

代码分两个：text_JCB.py，相当于一个main文件；text_JCB_function.py，写函数。

二、代码实现


import text_JCB_function
 
while(True):
    text_JCB_function.show_menu()
 
    action_str = input("请输入要选择的操作：")
    # 123 表示对进程的操作
    if action_str in ["1", "2", "3"]:
        if action_str == "1":
            # 新增一个进程
            text_JCB_function.new_JCB()
            continue
        elif action_str == "2":
            # 打印所有进程
            text_JCB_function.show_JCB()
            continue
        else:
            # 选择进程调度算法
            text_JCB_function.function_choice_menu()
            function_choice = input("请输入要选择的调度算法：")
            if function_choice in ["1", "2", "3", "4"]:
                if function_choice == "1":
                    # 使用的是 先到先服务算法
                    text_JCB_function.function_FCFS()
                    continue
                if function_choice == '2':
                    # 使用的是 短作业优先算法
                    text_JCB_function.function_SJF()
                    continue
                if function_choice == '3':
                    # 使用时间片轮转调度算法,时间片为1
                    text_JCB_function.function_RR()
                    continue
                if function_choice == '4':
                    # 使用 非抢占式优先级调度算法
                    text_JCB_function.function_HRRN()
                    continue              
            continue
 
    # 0 表示退出系统
    elif action_str == "0":
        print("已退出，欢迎下次使用！！")
        break
 
    else:
        print("输入错误，请重新输入！")


# 数据结构的确定 ： 每个进程信息用字典存储，再用列表存储各个进程
JCB_list = []
 
# 进程模拟系统的 实际函数编写
def show_menu():
 
    # 功能菜单：
    print("~" * 50)
    print("欢迎使用【进程调度算法展示系统】 [V 1.0]")
    print("1. 新增进程；\n2. 打印所有进程；\n3. 选择使用的进程调度算法；\n\n0. 退出系统;")
    print("~" * 50)
 
 
 
def new_JCB():
    # 新增进程信息
    print("-" * 50)
    # > 1 提示用户输入进程相关信息
    while True:
        JCB_name = input("请输入进程名：")
        if JCB_name != "":
            break
        else:
            print("输入不能为空!")
    while True:
        JCB_come = input("请输入进程到达时间：")
        if JCB_name != "":
            break
        else:
            print("输入不能为空!")
    while True:
        JCB_need = input("请输入进程服务时间：")
        if JCB_name != "":
            break
        else:
            print("输入不能为空!")
    JCB_level = 0 # 将进程的优先级初始化为0
 
    # > 2 将进程信息存储在字典中
    JCB_dict = {
        "JCB_name" : JCB_name,
        "JCB_come" : JCB_come,
        "JCB_need" : JCB_need,
        'JCB_level': JCB_level,
        }
    # > 3 将进程字典存储到列表中
    JCB_list.append(JCB_dict)
 
    # > 4 提示用户，新建进程成功
    print("新增进程名： %s 成功" % JCB_name)
 
 
 
def show_JCB():
    # 显示所有的进程
    print("-" * 50)
 
    if len(JCB_list) == 0:
        print("当前没有任何进程，请先添加新的进程！")
        return
    # > 1 将JCB_list中的所有进程输出,遍历所有的list即可
    # 打印数据
    for jcb in JCB_list:
        print("进程名称:%s   到达时间:%s   服务时间:%s" % (jcb["JCB_name"], jcb["JCB_come"], jcb["JCB_need"]))
    # > 2 提示用户，显示所有进程成功
    print("进程输出完成！")
 
 
 
def function_choice_menu():   
    # 选择算法的界面
    print("~" * 50)
    print("【进程调度算法展示系统】 [V 1.0]\n")
    print("请选择要使用的调度算法：\n1. 先来先服务算法；\n2. 短作业优先算法；\n3. 时间片轮转调度算法；\n4. 优先调度算法；\n")
    print("~" * 50)
 
 
 
def function_FCFS():
    # ***先到先服务算法：
    # 使用冒泡排序，将列表重新排序，按照 到达时间从小到大 排列
    time_going = 0.0 # 时间标识
    time = 0.0 # 作业周转时间的总和
    over_time = 0.0 # 每个作业的周转时间
    weighted_time = 0.0 # 作业的带权周转时间
    account_max = len(JCB_list)
    account = 0
 
    for i in range( len(JCB_list) - 1 ): # 将列表重新排序，按照进程到来的先后顺序
        for j in range( len(JCB_list) - i - 1 ):
            if JCB_list[j]["JCB_come"] > JCB_list[j + 1]["JCB_come"]:
                JCB_list[j], JCB_list[j + 1] = JCB_list[j + 1], JCB_list[j]
 
    while True: # 主体
        for jcb in JCB_list:
            if  (float(jcb["JCB_come"]) <= time_going):
                time_going = time_going + float(jcb["JCB_need"])
                over_time = float(over_time) + float(jcb["JCB_need"]) - float(jcb["JCB_come"])
                time = float(time) + float(over_time)
                weighted_time = float(weighted_time) + over_time /  float(jcb["JCB_need"])
                print("进程名称:%s   到达时间:%s   服务时间:%s   结束时间:%s" % 
                        (jcb["JCB_name"], jcb["JCB_come"], jcb["JCB_need"], over_time))
                # 执行过的作业，直接删除
                JCB_list.remove(jcb)
                account = account + 1
                break
        if account == account_max:
            break
    print("平均周转时间:%s    平均带权周转时间:%s" % (time/account_max, weighted_time/account_max))
    print("进程执行完毕！")
 
 
 
def function_SJF():
    # ***短作业优先算法
    time = 0.0 # 作业周转时间的总和
    over_time = 0.0 # 每个作业的结束时间
    weighted_time = 0.0 # 作业的带权周转时间
    account = 0
    process_list = JCB_list
    account_max = len(process_list)
 
    for i in range( len(process_list) - 1 ):
        for j in range( len(process_list) - i - 1 ):
            if float(process_list[j]["JCB_need"]) > float(process_list[j + 1]["JCB_need"]):
                process_list[j], process_list[j + 1] = process_list[j + 1], process_list[j]
 
    while True: # 循环主体
        for i in range( len(process_list) ):
            if float(process_list[i]["JCB_come"]) <= over_time: # 判断进程是否到达
                over_time = float(over_time) + float(process_list[i]["JCB_need"])
                time = float(time) + float(over_time) - float(process_list[i]["JCB_come"])
                weighted_time = float(weighted_time) + (over_time - float(process_list[i]["JCB_come"])) / float(process_list[i]["JCB_need"])
                print("进程名称:%s   到达时间:%s   服务时间:%s   结束时间:%s" % 
                        (process_list[i]["JCB_name"], process_list[i]["JCB_come"], process_list[i]["JCB_need"], over_time))
                # 执行过的作业，直接删除
                account = account + 1
                process_list.remove(process_list[i])
                break
        if account == account_max:
            break
    print("平均周转时间:%s\t平均带权周转时间:%s" % (time/account_max, weighted_time/account_max))
    print("进程执行完毕！")
 
 
 
def function_RR():
    # 按时间片轮转调度算法
    process_list = []# 用来表示进程的队列
    copy_list = JCB_list
    account_max = len(JCB_list) # 计数器，标识调度完成
    q = 1.0 # 时间片为1
    index = 0
    in_put = 0
    time_going = 0.0 # 时间进度
    time = 0.0 # 作业周转时间的总和
    nochange_list = []
    weighted_time = 0.0 # 作业的带权周转时间总和
    for k in JCB_list: # 首先将每个进程的服务时间保存下来，因为后续会对 JCB_need 不断进行修改
        nochange_list.append(k["JCB_need"])
    
 
    # 冒泡排序，按到达时间，从小到大排列
    for i in range( len(JCB_list) - 1 ):
        for j in range( len(JCB_list) - i - 1 ):
            if float(JCB_list[j]["JCB_come"]) > float(JCB_list[j + 1]["JCB_come"]):
                JCB_list[j], JCB_list[j + 1] = JCB_list[j + 1], JCB_list[j]
    
    while True: # 将第 0s已经就绪的进程，放入队列
        if index == len(copy_list):
            break
        if float((copy_list[index]["JCB_come"])) <= time_going:
            process_list.append(copy_list[index])
            copy_list.remove(copy_list[index])
            index -= 1
        index += 1
 
    while True:
        # 调度循环
        if len(process_list) == 0: # 进程列表为空，退出循环
            break
        current_process = process_list[0]
        process_list.remove(current_process) # 将即将要工作的作业，从列表去除，待操作完如果need > 0，再写回
 
        if float(current_process["JCB_need"]) > 0: # 还没有循环完毕
            if float(current_process["JCB_need"]) >= q: # 还没有循环完毕，并且这一个进程需要的时间大于时间片
                time_going += q
                current_process["JCB_need"] = float(current_process["JCB_need"]) - q
            else: # 需要的时间小于时间片
                time_going = time_going + float(current_process["JCB_need"])
                current_process["JCB_need"] = 0
 
        if float(current_process["JCB_need"]) == 0: # 已经循环完毕，计算平均周转时间，平均带权周转时间
            time = time + time_going - float(current_process["JCB_come"]) # 累加周转时间 and 加权周转时间
            for jcb_need in range(len(nochange_list)): # 取到已经结束的作业的 need, 并将该作业删除
                if  jcb_need + 1 == float(current_process["JCB_name"]):
                    need = float(nochange_list[jcb_need])
                    break
            weighted_time = weighted_time + (time_going - float(current_process["JCB_come"])) / need
        
            print("进程名称:%s   到达时间:%s   结束时间:%s" % 
                    (current_process["JCB_name"], current_process["JCB_come"], time_going))
        while True:
            if in_put == len(copy_list):
                break
            if float((copy_list[in_put]["JCB_come"])) <= time_going:
                process_list.append(copy_list[in_put])
                copy_list.remove(copy_list[in_put])
                in_put -= 1 # 回退一行
            in_put += 1 # 向下执行
        in_put = 0 # 归零
 
        if  current_process["JCB_need"] != 0: # 上一个作业，还没有执行完毕，将这个作业加到最后一个，待执行
                process_list.append(current_process)
    
    print("平均周转时间:%s    平均带权周转时间:%s" % (time/account_max, weighted_time/account_max))
    print("进程执行完毕！")
 
 
 
def function_HRRN():
    # 按非抢占式优先级调度算法
    process_list = []
    time = 0.0 # 作业周转时间的总和
    over_time = 0.0 # 每个作业的结束时间
    weighted_time = 0.0 # 作业的带权周转时间
    index = 0
    in_put = 0
    copy_list = JCB_list
    account_max = len(copy_list)
 
    # 每次循环，都要重新查询进程的优先级
 
    while True: # 将已经就绪的进程，放入就绪队列，并从进程队列中删除
        if index == len(copy_list):
            break
        if float((copy_list[index]["JCB_come"])) <= over_time:
            process_list.append(copy_list[index])
            copy_list.remove(copy_list[index])
            index -= 1
        index += 1
 
    while True: # 循环主体
        if len(process_list) == 0: # 进程列表为空，退出循环
            break
 
        max_level = 0.0 # 进程不为空，循环进程列表，求出每一个进程 此刻对应的响应比，响应比高者，优先处理
        for item in process_list:
            item["JCB_level"] = 1 + over_time / float(item["JCB_need"]) # 计算某进程当前的响应比
            if item["JCB_level"] > max_level: # 响应比高者，优先调度
                max_level = item["JCB_level"]
                current_process = item # 拿到最高响应比的进程
 
        # 进行操作，依次计算
        over_time = float(over_time) + float(current_process["JCB_need"])
        time = float(time) + float(over_time) - float(current_process["JCB_come"])
        weighted_time = float(weighted_time) + (over_time - float(current_process["JCB_come"])) / float(current_process["JCB_need"])
        print("进程名称:%s   到达时间:%s   服务时间:%s    优先级:%s   结束时间:%s" % 
                (current_process["JCB_name"], current_process["JCB_come"], current_process["JCB_need"], current_process["JCB_level"], over_time))
        
        # 执行过的作业，直接删除
        process_list.remove(current_process)
 
        while True: # 将已经就绪的进程，放入队列
            if in_put == len(copy_list):
                break
            if float((copy_list[in_put]["JCB_come"])) <= over_time:
                process_list.append(copy_list[in_put])
                copy_list.remove(copy_list[in_put])
                in_put -= 1
            in_put += 1
        in_put = 0
    print("平均周转时间:%s\t平均带权周转时间:%s" % (time / account_max, weighted_time / account_max))
    print("进程执行完毕！")

三、源码下载：

百度网盘：百度网盘

提取码：iuxp

可能有错误，欢迎指出。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/582387