操作系统实验二：进程调度

问题描述

进程调度是指从已经进入内存的进程的就绪队列中选择一个进程真正占有CPU，并为其运行进行上下文转换，让其立即运行。按照一定的进程调度算法，从内存的进程中选择一个进程，将处理机分配给它，使其执行。

问题要求

假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：

进程名（name）：进程的标识
指针：将按优先数的大小将五个进程链成一个队列，用指针指向下一个进程PCB的首址，最后一个进程指针为NULL，另用一个队首标记指向队列第一个进程的PCB
要求运行时间（runTime）：指的是进程从当前到运行结束还需的时间单位
优先数（priority）：代表一个进程的优先等级，优先数最高的进程将最先执行
状态（state）：代表一个进程的是否还将运行，用 “ R ” 表示就绪状态，用 “ F ” 表示结束状态

在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。
为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。
处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数发生变化。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：
- 优先数 = 优先数 / 2；
- 要求运行时间 = 要求运行时间 - 1.
来模拟进程的一次运行。提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。
进程运行一次后，若要求运行时间 ≠ 0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间 = 0，则把它的状态修改成 “ F ”（结束），且退出队列。
若 “ R ” （就绪）状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为 “ F ”（结束）状态。
在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。
为五个进程任意确定一组 “ 优先数 ” 和 “ 要求运行时间 ”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。

问题分析

本实验其实不难，最主要的部分就是要会使用数据结构中的链队列来将所有的 PCB 按优先数连接起来，并且每一次都对其进行重新排序。其实在本实验中指针的存在是不需要的，建立一个数组每一次都对所有进程按优先数进行排序更加方便，而且对队列的元素重新排序也大大提高了实验的难度。同时，本实验使用的是 python 语言，在 python 中是没有指针的概念的，所以我们就不对指针进行操作。而其他部分是没有难度的，具体实验的过程可以分为以下几步：

创建 PCB 块并进行赋值；
对所有进程按优先数从大到小进行排序；
对优先数最高的进程快进行仿真运行操作；
对所有进程的要求运行时间进行判断，如果有进程的要求运行时间 = 0，那么就更改这个进程的状态为 “ F ”（结束），并将其退出队列；
再次对进程按优先数从大到小进行排序，并一直重复（2）~（4）步；
所有进程的状态都为 “ F ”（结束），退出程序。

实验用例

[‘P1’, 2, 1, ‘R’]，[‘P2’, 3, 10, ‘R’]，[‘P3’, 1, 6, ‘R’]，[‘P4’, 2, 9, ‘R’]，[‘P5’, 4, 4, ‘R’]

源代码

class PCB(): # 定义PCB块
    # 初始化进程
    def __init__(self, name, runTime, priority, state):
        super().__init__()
        self.name = name # 进程名
        self.runTime = runTime # 要求运行时间
        self.priority = priority # 优先级
        self.state = state # 状态

    # 模拟进程启动运行
    def process(self):
        self.priority /= 2 # 优先级减半
        self.runTime -= 1 # 要求运行时间减一
        print('[' + self.name + '] 运行了，' + '优先级变为：' + str(self.priority))

        # 如果时间用完就结束
        if self.runTime == 0:
            print(self.name + ' 运行结束了' + '状态变为：F ,退出队列')
            self.state = 'F'
            self.priority = -1

# 获得进程的优先级
def takePriority(P):
    return P.priority

# 打印队列信息
def show_PCB(P_list):
    if P_list[0].priority > 0 :
        print('\n')
        print('-----------------队列情况-------------------')

    for p in P_list:
        if p.priority > 0:
            print(p.name + ' 要求运行时间：' + str(p.runTime) + ',   优先级： ' + str(p.priority) + ',   状态： ' + p.state)

    print('')

# 定义进程
PCB_list = [PCB('P1', 2, 1, 'R'), PCB('P2', 3, 10, 'R'), PCB('P3', 1, 6, 'R'), PCB('P4', 2, 9, 'R'), PCB('P5', 4, 4, 'R')]

while(1):
    # 按优先级排序
    PCB_list.sort(key = takePriority, reverse = True)
    # 按优先级展示各个进程
    show_PCB(PCB_list)

    # 如果队列中还有进程，那他的优先级一定大于 0
    if PCB_list[0].priority > 0:
        # 因为进行了优先级的排序，所以第一个进程一定是优先级最高的进程
        PCB_list[0].process()
    else:
        print('-----------------程序结束-------------------')
        break