操作系统原理——多道系统作业调度

本文章用到的语言：Python

前言

其实一周前就把程序写完了，但是因为博客最近才搭好以及最近才学习了一手markdown所以现在才开始写（绝对不是我懒！）
操作系统课程的作业，其实挺不想写的（真的），毕竟我数据结构与算法学得很垃圾www，就当顺便学习python好了

原理

这部分略过。（因为真的没什么好写的，以后再补充一下吧）

复制实验说明上的原话：

由于在多道批处理系统中，一批作业投入运行，调度作业时需要根据当前系统各类空闲资源的情况选择一个或多个作业进入内存，再按照进程调度方式选择一个作业的进程占用 CPU。
每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。
作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。
各个等待的作业按照提交时刻的先后次序排队，总是首先调度等待队列中队首的作业。
每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。

实现

核心

有两部分，先说第一部分：作业控制块（JCB）
其实这里存的东西过多了，但是好处就是意思都很清晰，后面计算总时间或者打印信息什么的也方便

class JCB:
    """作业控制块"""

    def __init__(self, job_name, commit_time, run_time, source):
        """初始化作业程序块"""
        self.job_name = job_name  # 作业名字
        self.commit_time = commit_time  # 作业提交时间
        self.run_time = run_time  # 作业所需时间
        self.start_time = 0  # 作业开始时间
        self.finish_time = 0  # 作业完成时间
        self.rr = 0  # 作业响应比
        self.status = 'w'  # 程序状态，w为等待，r为运行，f为完成
        self.ta_time = 0  # 作业周转时间
        self.wta_time = 0  # 作业带权周转时间
        self.source = source  # 作业所需资源

    def cul_rr(self, clock):
        """计算作业相应比"""
        self.rr = ((clock - self.commit_time) + self.run_time) / self.run_time

然后是第二部分，这部分用到了python的特性：双下划线方法以及嵌套函数、返回函数等，这里用到的特性会放到后面要写的一些文章中更详细地介绍。
先看代码：

def getMethod(method):
    """不同算法的排序方法"""

    def FCFS_lt(self, other):
        return self.commit_time < other.commit_time

    def SJF_lt(self, other):
        return self.run_time < other.run_time

    def HRRF_lt(self, other):
        return self.rr > other.rr

    if method == 'FCFS':
        return FCFS_lt
    elif method == 'SJF':
        return SJF_lt
    elif method == 'HRRF':
        return HRRF_lt

调用这个方法，传入一个字符串，根据不同的字符串返回不同的排序方法，这里一共用到了三种算法：

• FCFS：先来先服务
• SJF：短作业优先
• HRRF：响应比最高者优先

比如我要用FCFS，那么就：JCB.__lt__ = getMethod('FCFS')，这里getMethod返回了一个函数对象，再赋值给了JCB类的__lt__()方法，这样JCB.__lt__()就和FCFS_lt()一样了（我省略了参数order），这个方法在之后的文章再详细说，
现在可以这样理解：这么做重载了JCB类的默认比较方法，两个JCB之间可以比大小了，怎么比就看__lt__()里了。
那么能比较大小了，排序就能方便起来，而python里边提供了sort()函数来对列表进行永久排序，这个时候即使列表里是一堆JCB对象，我们也可以进行排序。

算法部分

注释写得算比较清楚所以在这里不多赘述了，以后有空说不定会更新（实打实的懒狗）
其实写得不算好吧…自己感觉是写复杂了，某些地方凭感觉写了点东西保证不出错，比如那个删除队列，按道理来说有写判断条件的话就不会出错

注意这里用到了copy.deepcopy()，需要导入copy模块

import copy

def simulator(JCB_queue, method, src):
    """作业调度模拟程序"""
    # 系统时钟和资源数
    clock = 0
    source = src
    # 平均周转时间
    avg_ta_time = 0
    # 平均带权周转时间
    avg_wta_time = 0
    # 拷贝队列
    copy_queue = copy.deepcopy(JCB_queue)
    # 队列长度
    queue_len = int(len(copy_queue))
    # 创建执行队列和等待队列
    wait_queue = []
    run_queue = []
    num = 0
    # 排序
    JCB.__lt__ = getMethod('FCFS')
    copy_queue.sort()
    while True:
        # 运行队列中的作业变更
        if run_queue:
            for job in run_queue:
                # 检查作业是否完成
                if job.run_time <= clock - job.start_time and job.status == 'r':
                    job.status = 'f'  # 将当前作业状态设置为完成
                    job.finish_time = clock  # 作业完成（结束）时间为当前系统时间
                    job.ta_time = job.finish_time - job.commit_time  # 作业周转时间 = 作业完成时间 - 作业提交时间
                    job.wta_time = job.ta_time / job.run_time  # 作业带权周转时间 = 作业周转时间 / 作业所需时间
                    avg_ta_time = avg_ta_time + job.ta_time
                    avg_wta_time = avg_wta_time + job.wta_time
                    num = num + 1  # 作业完成数+1
                    source = source + job.source  # 归还资源
                    print(f"作业名：{job.job_name}\t"
                          f"作业开始时间：{job.start_time}\t"
                          f"作业完成时间：{job.finish_time}\t"
                          f"作业周转时间：{job.ta_time}\t"
                          f"作业带权周转时间：{job.wta_time:.2f}\t")

        # 检查是否有可以进入等待作业队列的作业
        for job in copy_queue:
            if job.commit_time <= clock and job.status == 'w':
                wait_queue.append(job)

        # 等待队列不为空，检查是否有可以进入运行队列的作业
        if wait_queue:
            # 计算响应比
            for job in wait_queue:
                job.cul_rr(clock)
            JCB.__lt__ = getMethod(method)
            wait_queue.sort()
            # 用于删除等待队列列表元素的列表
            del_queue = []
            for job in wait_queue:
                if job.source <= source and job.status == 'w':
                    run_queue.append(job)
                    del_queue.append(job)
                    job.start_time = clock  # 作业开始时间为当前系统时间
                    job.status = 'r'
                    source = source - job.source
            if del_queue and wait_queue:
                for job in del_queue:
                    wait_queue.remove(job)

        # 跳出循环用
        if num == queue_len:
            break

        # 系统时钟自增
        clock = clock + 1
    avg_ta_time = avg_ta_time / queue_len
    avg_wta_time = avg_wta_time / queue_len
    print(f"平均周转时间：{avg_ta_time:.2f}\t带权周转时间：{avg_wta_time:.2f}")

其他函数

其实只有一个input()用来获取用户输入

def inputJCB():
    """初始化JCB队列"""
    JCB_queue = []
    src = int(input("请输入系统资源数："))
    JCB_num = int(input("请输入作业数量："))
    for i in range(JCB_num):
        print(f"当前是第{i + 1}个作业；")
        jn = input("请输入作业名字：")
        ct = int(input("请输入作业提交时间："))
        rt = int(input("请输入作业运行时间："))
        sc = int(input("请输入作业所需资源："))
        new_JCB = JCB(jn, ct, rt, sc)
        JCB_queue.append(new_JCB)
    print("\n")
    # 打印JCB队列
    for i in range(JCB_num):
        print(f"第{i + 1}个作业名字：{JCB_queue[i].job_name}\t"
              f"作业提交时间：{JCB_queue[i].commit_time}\t"
              f"作业所需运行时间：{JCB_queue[i].run_time}\t"
              f"作业所需资源数：{JCB_queue[i].source}")
    print("FCFS算法：")
    simulator(JCB_queue, "FCFS", src)
    print("SJF算法：")
    simulator(JCB_queue, "SJF", src)
    print("HRRF算法：")
    simulator(JCB_queue, "HRRF", src)

python测试代码

if __name__ == "__main__":
    inputJCB()

运行结果

暂时不贴结果，没找到一个好云图库放图，上传到github也不合适www
麻烦各位自己运行一下了

结语

日后补充（兄啊一篇文章下来省略了多少啊）

---

希望本文章能够帮到您~