一、课程设计目的 1. 加深对进程概念的理解，明确进程和程序的区别。 2. 深入了解系统如何组织进程、创建进程。 3. 进一步认识如何实现处理器调度。 二、课程设计内容 编写程序完成单处理器系统中的进程调度，要求实现时间片轮转、优先数、最短进程优 先和最短剩余时间优先四种调度算法。 实验具体包括：首先确定进程控制块的内容，进程控 制块的组成方式；然后完成进程创建原语和进程调度原语；最后编写主函数对所作工作进行测试。 模拟程序只对你所设置的“虚拟 PCB ”进行相应的调度模拟操作，即每发生“调度”时，显示出当前运行进程的“进程标识符”、“优先数”、“剩余运行时间”等，而不需要对系统中真正的 PCB 等数据进行修改。 三、要求及提示 要求能够动态地随机生成新进程添加到就绪队列中。 主要考虑三个问题：如何组织进程、如何创建进程和如何实现处理器调度。 1、组织进程 考虑如何组织进程，首先要设定进程控制块的内容。进程控制块 PCB 记录各个进程执行时的情况。不同的操作系统，进程控制块记录的信息内容不一样。操作系统功能越强，软件也越庞大，进程控制块的内容也就越多。这里只使用必不可少的信息。一般操作系统中，无论进程控制块中信息量多少，信息都可以大致分为以下四类： （1 ）标识信息 每个进程都要有一个唯一的标识符，用来标识进程的存在和区别于其他进程。这个标识 符是必不可少的，可以用符号或编号实现，它必须是操作系统分配的。例如采用编号方式，也就是为每个进程依次分配一个不相同的正整数。 （2 ）说明信息 用于记录进程的基本情况，例如进程的状态、等待原因、进程程序存放位置、进程数据13 存放位置等等。实验中，因为进程没有数据和程序，仅使用模拟的进程控制块，所以这部分内容仅包含进程状态。进程状态可假设只有就绪、运行、终止三种。如果要设置“等待（阻塞）”状态，需要随机生成“阻塞时间”，阻塞时间到时转为就绪态。 （3 ）现场信息 现场信息记录各个寄存器的内容。当进程由于某种原因让出处理器时，需要将现场信息记录在进程控制块中，当进行进程调度时，从选中进程的进程控制块中读取现场信息进行现场恢复。现场信息就是处理器的相关寄存器内容，包括通用寄存器、程序计数器和程序状态 字寄存器等。在本实验中，本部分可忽略。 （4 ）管理信息 管理信息记录进程管理和调度的信息。例如进程优先数、进程队列指针等。 另外，本实验为了模拟进程的不同运行时间，再添加一个“剩余运行时间”属性。 因此可将进程控制块结构定义如下： struct pcb { int name; // 进程标识符 int status; // 进程状态 int pri; // 进程优先数 int time; // 剩余运行时间，以时间片为单位，当减至 0 时该进程终止 int next; // 下一个进程控制块的位置 } 确定进程控制块内容后，要考虑的就是如何将进程控制块组织在一起。多道程序设计系统中，往往同时创建多个进程。在单处理器的情况下，每次只能有一个进程处于运行态，其它的进程处于就绪状态或者等待状态。为了便于管理，通常把处于相同状态的进程的进程控制块链接在一起组成就绪队列和等待队列。由于实验模拟的是进程调度，没有对等待队列的操作，所以实验中只有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列指针。操作系统实现中，系统往往在主存中划分出一个连续的专门区域存放系统的进程控制块，实验中应该用数组模拟这个 专门的进程控制块区域，定义如下： #define n 10 // 假定系统允许进程个数为 n struct pcb pcbarea[n]; // 模拟进程控制块区域的数组 14 这样，进程控制块的链表实际上是数据结构中使用的静态链表。实验中，进程控制块队列采用单向不循环静态链表。为了管理空闲进程控制块，还应该将空闲控制块链接成一个队列。 进程调度其实就是一个排队的过程，不同的算法区别在于按照什么样的次序将就绪队列里面的进程进行排序，比如时间片轮转调度算法，是将进程控制块按照进入就绪队列的先后次序排队。关于就绪队列的操作就是从队头摘下一个进程控制块和从队尾挂入一个进程控制块。因此为就绪队列定义两个指针，一个头指针，指向就绪队列的第一个进程控制块；一个尾指针，指向就绪队列的最后一个进程控制块。 实验中指向运行进程的进程控制块指针、就绪队列指针和空闲进程控制块队列指针定义如下： int run; // 定义指向正在运行进程的进程控制块的指针 struct { int head; int tail; // 定义指向就绪队列的头指针 head 和尾指针 tail }ready; int pfree; // 定义指向空闲进程控制块队列的指针 2、创建进程 进程创建是一个原语，因此在实验中应该用一个函数实现，进程创建的过程应该包括： （1）申请进程控制块 进程控制块的数量是有限的，如果没有空闲进程控制块，则进程不能创建，如果申请成 功才可以执行第二步。 （2）填写进程控制块 将该进程信息写入进程控制块内。进程标识符应该随机生成并且是唯一，优先数和剩余 运行时间随机生成，刚刚创建的进程为就绪态，然后转去执行第三步。 （3）挂入就绪队列 如果原来就绪队列不为空，则将该进程挂入就绪队列尾部，并修改就绪队列尾部指针； 如果原来就绪队列为空，则将就绪队列的头指针、尾指针均指向该进程控制块，进程创建完 成。 多道程序设计的系统中，处于就绪状态的进程往往是多个，它们都要求占用处理器，可是单处理器系统的处理器只有一个，进程调度就是解决这个处理器竞争问题的。进程调度的15任务就是按照某种算法从就绪进程队列中选择一个进程，让它占有处理器。因此进程调度程序就应该包括两部分，一部分是在进程就绪队列中选择一个进程，并将其进程控制块从进程就绪队列中摘下来，另一部分工作就是分配处理器给选中的进程，也就是将指向正在运行进程的进程控制块指针指向该进程的进程控制块，并将该进程的进程控制块信息写入处理器的各个寄存器中。 注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在本实验里省去了这些工作。以时间片轮转调度算法为例说明如何挂入就绪队列。时间片轮转调度算法让就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占有处理器，但是规定只能使用一个“时间片”。时间片就是规定进程一次使用处理器的最长时间。实验中采用每个进程都使用相同的不变时间片。每被调度 1 次，将其剩余运行时间－ 1 。进程运行一次后，若剩余运行时间不等于 0 ，则再将它加入就绪队列尾；若剩余运行时间等于 0 ，则把它的状态修改成“终止”，且退出队列。若就绪进程队列不为空，则重复调度，直到所有进程都“终止”。 3、调度 完成上述功能后，编写主函数进行测试：首先建立一个就绪队列，随机生成信息建立若 干个进程；然后进行进程调度；将正在运行进程指针指向的进程控制块的内容以及调度一次 后进程队列的现状输出，查看结果。题目要求模拟实现四种调度方法，要求和提示如下： （1） 时间片轮转调度 时间片轮转调度的要求和提示已经在上述过程中进行了说明，请参看。 （2） 优先数调度 要求动态改变优先数，假设大数代表高优先级，进程每运行一次优先数就减“1 ”，即被调度时执行：优先数－1 ，剩余运行时间－ 1 ，来模拟进程的一次运行。进程运行一次后，若剩余运行时间不等于 0 ，则再将它加入队列（按优先数大小插入，且置队首标志）；若剩余运行时间等于 0 ，则把它的状态修改成“终止”，且退出队列。若就绪进程队列不为空，则重复调度，直到所有进程都“终止”。 （3） 最短进程优先 按照进程执行时间的长短进行排队，优先调度短进程，因为该调度不抢占，因此调度到的进程就可以运行完，其状态修改成“终止”，且退出队列。若就绪进程队列不为空，则重复调度，直到所有进程都“终止”。 （4） 最短剩余时间优先 最短进程优先的抢占版本，比较当前进程的剩余运行时间和新到达进程的预计运行时间，短者优先执行。进程运行一次后，若剩余运行时间不等于 0 ，则再将它加入队列（按剩余时间长短插入，且置队首标志）；若剩余运行时间等于 0 ，则把它的状态修改成“终止”， 且退出队列。若就绪进程队列不为空，则重复调度，直到所有进程都“终止”。
需求分析：
本程序旨在模拟单处理器系统中的进程调度，实现时间片轮转、优先数、最短进程优先和最短剩余时间优先四种调度算法。程序将模拟进程创建、就绪队列管理以及调度过程，并输出相关信息以验证调度算法的正确性。
(1)输入的形式和输入值的范围；
无。
(2)输出的形式；
当前运行进程的标识符、优先数、剩余运行时间信息
调度后就绪队列中进程的标识符、优先数、剩余运行时间等信息
(3)程序所能达到的功能；
组织进程：
定义进程控制块（PCB）结构体，包含进程标识符、优先数、剩余运行时间信息。创建就绪队列，用于存储等待调度的进程。
创建进程：
接收用户输入的进程数量、标识符、优先数和初始运行时间。为每个进程分配PCB，并填写相关信息。将新创建的进程挂入就绪队列。
实现四种调度算法：
时间片轮转调度：按照进程在就绪队列中的顺序依次运行，每个进程运行一个时间片后切换到下一个进程。
优先数调度：选择优先数最高的进程运行。
最短进程优先：选择初始运行时间最短的进程运行。
最短剩余时间优先：选择剩余运行时间最短的进程运行。
在每次调度时，输出当前运行进程的PCB信息以及调度后就绪队列的状态。
测试数据：（随机生成）
概要设计：
(1)抽象数据类型（ADT）定义
PCB（进程控制块）
pid：整数类型，表示进程标识符。
priority：整数类型，表示进程的优先数，数值越小表示优先级越高。
remaining_time：整数类型，表示进程的剩余运行时间。
Scheduler（调度器）
ready_queue：PCB对象列表，表示就绪队列。
run_pcb：PCB对象，指向当前正在运行的进程控制块。
time_slice：整数类型，表示时间片长度。
(2)主程序的流程
初始化调度器对象（Scheduler），设定时间片长度。
调用调度器的create_processes方法创建指定数量的进程，并将它们加入就绪队列。
调用相应的调度算法（SJF、SRTF、其他调度算法），选择就绪队列中的进程执行。
如果当前进程执行完毕（remaining_time为0），则从就绪队列中移除该进程。
如果当前进程未执行完毕，但时间片耗尽，则将当前进程放回就绪队列，并更新其剩余时间。
重复步骤3至5，直到就绪队列为空。
(3)各程序模块之间的层次 (调用)关系
主程序
初始化Scheduler对象。
调用Scheduler对象的create_processes方法创建进程。
调用Scheduler对象的调度算法方法（如shortest_job_first、shortest_remaining_time_first等）进行进程调度。
Scheduler类
维护就绪队列（ready_queue）和当前运行进程（run_pcb）。
提供创建进程（create_processes）和进程调度（如shortest_job_first、shortest_remaining_time_first等）的方法。
PCB类
表示进程控制块，包含进程的基本信息（pid、priority、remaining_time）。
提供__str__方法用于打印进程信息。
调用关系图：
概要设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模
块也都需要写出伪码算法；画出函数的调用关系图。
伪码算法：
1.PCB 类:
初始化(pid, priority, remaining_time):
设置 pid 为进程标识符
设置 priority 为进程优先数
设置 remaining_time 为剩余运行时间
转换为字符串():
返回 PCB 的字符串表示形式
2.Scheduler 类:
初始化(time_slice=2):
设置就绪队列 ready_queue 为空列表
设置正在运行的 PCB 指针 run_pcb 为 None
设置时间片长度 time_slice
创建进程(num_processes):
对于 i 从 0 到 num_processes-1:
pid = i + 1
priority = 生成 1 到 10 之间的随机整数
remaining_time = 生成 1 到 5 之间的随机整数
创建 PCB 实例 pcb，参数为 pid, priority, remaining_time
将 pcb 添加到 ready_queue
打印 "创建进程: " 和 pcb 的字符串表示
时间片轮转调度算法
round_robin(self):
打印 "时间片轮转调度算法(quantum=" + 字符串表示(self.time_slice) + ")"
当 ready_queue 不为空时执行:
取出 ready_queue 的第一个 PCB 赋值给 run_pcb
打印 "运行: " + 字符串表示(run_pcb)
如果 run_pcb 的剩余时间 remaining_time 大于 0:
run_pcb 的剩余时间减去时间片长度
如果剩余时间小于 0，则将其设置为 0
打印 " 剩余时间: " + 字符串表示(run_pcb.remaining_time)
如果剩余时间仍大于 0，将 run_pcb 放回 ready_queue 的末尾
打印 "所有进程都已终止"
优先数调度算法
priority_scheduling(self):
打印 "优先数调度算法"
当 ready_queue 不为空时执行:
对 ready_queue 按优先级升序排序
取出 ready_queue 的第一个 PCB 赋值给 run_pcb
打印 "运行: " + 字符串表示(run_pcb)
当 run_pcb 的剩余时间 remaining_time 大于 0 时执行:
run_pcb 的剩余时间减去 1
打印 " 剩余时间: " + 字符串表示(run_pcb.remaining_time)
打印 "所有进程都已终止"（这里的位置可能不恰当，通常应在所有进程运行完后打印）
最短进程优先调度算法（SJF）
shortest_job_first(self):
打印 "最短进程优先调度算法"
当 ready_queue 不为空时执行:
对 ready_queue 按剩余时间升序排序
取出 ready_queue 的第一个 PCB 赋值给 run_pcb
打印 "运行: " + 字符串表示(run_pcb)
将 run_pcb 的剩余时间设置为 0（假设连续运行到完成）
打印 "所有进程都已终止"
shortest_remaining_time_first():
当 ready_queue 不为空时:
从 ready_queue 中选择剩余时间最短的 PCB
从 ready_queue 中移除该 PCB
将 PCB 设置为当前运行 PCB
打印 "运行: " + 当前运行 PCB 的信息
如果 当前运行 PCB 的剩余时间大于 0:
当前运行 PCB 的剩余时间减 1
打印 "剩余时间: " + 当前运行 PCB 的剩余时间
如果 当前运行 PCB 的剩余时间仍大于 0:
将 当前运行 PCB 放回 ready_queue
打印 "所有进程都已终止"
程序流程：
1. 导入和初始化Schedule
2. 创建进程，使用create_processes方法创建进程。
3. 时间片轮转调度算法
4. 优先数调度算法
5. 最短进程优先调度算法
6. 最短剩余时间优先调度算法
测试运行结果：
生成的时间片、生成的进程优先数、运行剩余时间均为随机生成数。
时间片轮转调度算法：
优先数调度算法：
最短进程优先调度算法：
最短剩余时间优先调度算法：
源代码：
import random
class PCB:
def __init__(self, pid, priority, remaining_time):
self.pid = pid # 进程标识符
self.priority = priority # 进程优先数
self.remaining_time = remaining_time # 剩余运行时间
def __str__(self):
return f"PcB(pid={self.pid},priority={self.priority},remaining_time={self.remaining_time})"
class Scheduler:
def __init__(self, time_slice):
self.ready_queue = [] # 就绪队列
self.run_pcb = None # 指向正在运行进程的进程控制块指针
self.time_slice = time_slice # 时间片长度
# 创建进程
def create_processes(self, num_processes):
for i in range(num_processes):
pid = i + 1
priority = random.randint(1, 10) # 随机生成进程优先数
remaining_time = random.randint(1, 5) # 随机生成剩余运行时间
pcb = PCB(pid, priority, remaining_time)
self.ready_queue.append(pcb)
print(f"创建进程: {pcb}")
# 时间片轮转调度算法
def round_robin(self):
print(f"Time-slice Round Robin(quantum={self.time_slice}):")
while self.ready_queue:
# 取出就绪队列的第一个进程运行
self.run_pcb = self.ready_queue.pop(0)
print(f"运行: {self.run_pcb}")
# 模拟进程运行一个时间片
if self.run_pcb.remaining_time > 0:
self.run_pcb.remaining_time -= self.time_slice
if self.run_pcb.remaining_time < 0:
self.run_pcb.remaining_time = 0
print(f" 剩余时间: {self.run_pcb.remaining_time}")
# 如果剩余时间大于0，则放回就绪队列末尾
if self.run_pcb.remaining_time > 0:
self.ready_queue.append(self.run_pcb)
# 所有进程都已终止
print("所有进程都已终止")
# 优先数调度算法
def priority_scheduling(self):
print("Priority Scheduling:")
while self.ready_queue:
# 按照优先级排序就绪队列
self.ready_queue.sort(key=lambda x: x.priority)
# 取出优先级最高的进程运行
self.run_pcb = self.ready_queue.pop(0)
print(f"运行: {self.run_pcb}")
# 模拟进程运行到完成
while self.run_pcb.remaining_time > 0:
self.run_pcb.remaining_time -= 1
print(f" 剩余时间: {self.run_pcb.remaining_time}")
# 如果进程已经运行完，则不需要放回就绪队列
print("所有进程都已终止")
# 最短进程优先调度算法（SJF）
def shortest_job_first(self):
print("Shortest Job First:")
while self.ready_queue:
# 按照剩余时间排序就绪队列
self.ready_queue.sort(key=lambda x: x.remaining_time)
# 取出剩余时间最短的进程运行
self.run_pcb = self.ready_queue.pop(0)
print(f"运行: {self.run_pcb}")
# 模拟进程运行到完成
self.run_pcb.remaining_time = 0 # 因为SJF假设进程会连续运行到完成
print("所有进程都已终止")
# 最短剩余时间优先调度算法（SRTF）
def shortest_remaining_time_first(self):
print("Shortest Remaining Time First:")
while self.ready_queue:
# 选择剩余时间最短的进程
min_remaining_time_pcb = min(self.ready_queue, key=lambda x: x.remaining_time)
# 取出并运行该进程
self.ready_queue.remove(min_remaining_time_pcb)
self.run_pcb = min_remaining_time_pcb
print(f"运行: {self.run_pcb}")
# 模拟进程运行一个时间片
if self.run_pcb.remaining_time > 0:
self.run_pcb.remaining_time -= 1
print(f" 剩余时间: {self.run_pcb.remaining_time}")
# 如果剩余时间大于0，则放回就绪队列
if self.run_pcb.remaining_time > 0:
self.ready_queue.append(self.run_pcb)
print("所有进程都已终止")
# 测试
if __name__ == "__main__":
time_slice = random.randint(1, 3)
scheduler = Scheduler(time_slice)
# 创建5个进程
scheduler.create_processes(5)
# 时间片轮转调度算法
print("---时间片轮转调度算法---")
scheduler.round_robin()
print('----------重新创建进程-------------')
scheduler.ready_queue = [] # 清空就绪队列
scheduler.create_processes(5) # 重新创建5个进程
# 优先数调度算法
print("---优先数调度算法---")
scheduler.priority_scheduling()
print('----------重新创建进程-------------')
scheduler.ready_queue = [] # 清空就绪队列
scheduler.create_processes(5) # 重新创建5个进程
# 最短进程优先调度算法
print("---最短进程优先调度算法---")
scheduler.shortest_job_first()
print('----------重新创建进程-------------')
scheduler.ready_queue = [] # 清空就绪队列
scheduler.create_processes(5) # 重新创建5个进程
# 最短剩余时间优先调度算法
print("---最短剩余时间优先调度算法---")
scheduler.shortest_remaining_time_first()