AI 文章摘要

文章介绍了进程调度中的SPF和RR算法：SPF优先执行最短进程以减少等待时间，但可能导致长进程饥饿；RR使用时间片轮转保证公平性，但响应时间不确定。文章定义了PCB类并初始化五个进程，展示了算法执行过程和结果。阅读此文章大概需要4分钟。
摘要更新时间：2026-06-21 16:13

一、内容
（1）进程通过定义一个进程控制块的数据结构（PCB）来表示；
（2）每个进程需要赋予进程ID、进程到达时间、进程需要运行的总时间、阻塞时间的属性；
（3）在RR中，以1为时间片单位；
（4）运行时，输入5个进程序列，按照进程的ID输出其执行序列。

二、算法的介绍

（1）短进程优先调度算法（SPF）

短进程优先调度算法是一种 CPU 调度算法，它根据进程所需的 CPU 执行时间来决定下一个要执行的进程。SPF 算法会优先选择需要执行时间最短的进程来分配 CPU 资源。

工作原理：

  • 非抢占式：在 SJF 算法中，一旦 CPU 被分配给进程，进程就会一直运行，直到完成任务或者发生 I/O 等待。
  • 任务排序：进程按照其预计的 CPU 执行时间（也称为服务时间）进行排序，执行时间短的进程先执行，长任务排在后面。
  • 执行流程：当一个进程到达就绪队列时，系统会比较它的执行时间和其他进程的执行时间，选择执行时间最短的进程分配 CPU 资源。

特点和优点：

  • 最小化平均等待时间：SPF算法能够最小化平均等待时间，因为它优先执行执行时间最短的进程，这样短任务能够快速完成，减少等待时间。
  • 高效性：对于短任务来说，SJF 算法的执行效率很高，能够快速完成执行。

缺点和局限性：

  • 不利于长任务：对于执行时间长的任务，可能会等待很长时间才能获得 CPU 资源，容易出现长任务等待（饥饿）现象。
  • 无法预测执行时间：在实际应用中，很难准确预测每个进程的执行时间，因此需要较好的执行时间估计。

（2）时间片轮转调度算法（RR）

时间片轮转调度算法（Round Robin Scheduling）是一种 CPU 调度算法，主要用于多道批处理系统中。它将 CPU 时间分割成若干个时间片（时间量），并按照时间片大小依次轮流分配给处于就绪状态的进程。

工作原理：

  • 时间片大小：系统将 CPU 时间划分为固定大小的时间片（例如，每个时间片为1个单位时间）。
  • 进程轮转：当进程到达就绪状态，系统按照队列顺序将 CPU 时间片分配给它，该进程执行一个时间片的时间，然后被放回就绪队列末尾等待下一次调度。
  • 调度策略：按照队列顺序轮流调度进程，每个进程都有机会获得 CPU 时间片，不会出现某个进程一直占用 CPU 的情况。

特点和优点：

  • 公平性：每个进程都有机会执行，避免了某个长任务长时间占用 CPU 资源，保证了公平性。
  • 简单易实现：实现相对简单，易于理解和管理。
  • 实时性：对于短任务有较好的响应，能够迅速执行。

缺点和局限性：

  • 等待时间长：对于长时间的任务，可能需要等待较长时间才能执行完毕，因为它们需要多次切片才能完成。
  • 响应时间不确定：无法保证对每个进程的响应时间，有可能会有长时间的等待。

三、定义PCB模块

class Status(Enum):
    running = 1
    ready = 2
    blocked = 3

class PCB:
    def __init__(self, pid, arrival_time, total_time, block_time=0):
        self.id = pid
        self.arrival_time = arrival_time
        self.total_time = total_time
        self.remaining_time = total_time
        self.block_time = block_time
        self.state = Status.ready
        self.next = None

四、进程列表的初始化

#调用PCB类进行初始化
processes = [
    PCB(1, 0, 10),
    PCB(2, 1, 4),
    PCB(3, 2, 5),
    PCB(4, 3, 3),
    PCB(5, 4, 8)
]

由此可见，初始化了五个进程序列，从左至右分别是进程序号，进程到达时间，进程需要执行的时间。

五、运行结果

（1）SPF算法：

在最短进程优先算法（SPF）中，每次选择当前剩余时间最短的进程来执行。在上述运行结果中：

  1. 进程执行过程：
    • 进程 4 是首先到达的，在时间 3 开始执行，因为它总时间最短，执行完毕后在时间 6 完成执行。
    • 进程 2 在时间 6 开始执行，因为此时它是剩余时间最短的进程，执行完毕后在时间 10 完成执行。
    • 进程 3 在时间 10 开始执行，因为此时它是剩余时间最短的进程，执行完毕后在时间 15 完成执行。
    • 进程 5 在时间 15 开始执行，因为此时它是剩余时间最短的进程，执行完毕后在时间 23 完成执行。
    • 进程 1 在时间 23 开始执行，因为此时它是剩余时间最短的进程，执行完毕后在时间 33 完成执行。
  2. 进程执行完成时间：
    • 进程 1 在时间 33 完成执行。
    • 进程 2 在时间 10 完成执行。
    • 进程 3 在时间 15 完成执行。
    • 进程 4 在时间 6 完成执行。
    • 进程 5 在时间 23 完成执行。

SPF 算法在每个时间点选择剩余时间最短的进程执行，这样保证了更短任务能更早完成，但也可能导致长任务等待时间增加。因此，虽然某些进程可能需要等待较长时间才能执行，但短任务的执行速度较快，这是最短进程优先算法的特点。

（2）RR算法

在上述时间片轮转算法（RR）的运行结果中，轮转过程是一直持续，直到所有进程都完成执行。每个进程都按照时间片大小（1个时间片）执行，直到完成，或者在时间片内无法完成时让出 CPU 给下一个进程。它执行的过程与预期符合，因此证明程序正确。

六、附全部代码

from enum import Enum

class Status(Enum):
    running = 1
    ready = 2
    blocked = 3

class PCB:
    def __init__(self, pid, arrival_time, total_time, block_time=0):
        self.id = pid
        self.arrival_time = arrival_time
        self.total_time = total_time
        self.remaining_time = total_time
        self.block_time = block_time
        self.state = Status.ready
        self.next = None

def round_robin_scheduler(processes, time_slice):
    current_time = 0  # 当前时间初始化为0
    completed_processes = []  # 存储已完成的进程信息

    # 当进程列表非空时，执行调度
    while processes:
        for process in processes:  # 对于每个进程
            # 检查进程是否可以执行
            if process.arrival_time <= current_time and process.state != Status.blocked:
                if process.remaining_time <= time_slice:  # 如果进程剩余时间小于等于时间片
                    current_time += process.remaining_time  # 更新当前时间
                    process.remaining_time = 0  # 进程剩余时间置为0，表示执行完成
                    process.state = Status.blocked  # 进程状态设置为阻塞
                    completed_processes.append((process.id, current_time))  # 将完成的进程信息添加到列表中
                    print(f"进程 {process.id} 在时间 {current_time} 执行完成")  # 输出进程执行完成信息
                    processes.remove(process)  # 从进程列表中移除该进程
                else:
                    current_time += time_slice  # 更新当前时间为一个时间片
                    process.remaining_time -= time_slice  # 减去执行的时间片
                    process.state = Status.ready  # 进程状态设置为就绪
                    print(f"进程 {process.id} 在时间 {current_time} 执行")  # 输出进程执行信息

    return completed_processes  # 返回完成执行的进程信息列表


def spf_scheduler(processes):
    current_time = 0
    completed_processes = []

    while processes:
        shortest_process = min(processes, key=lambda x: x.total_time)
        current_process = shortest_process

        if current_process.arrival_time > current_time:
            current_time = current_process.arrival_time

        current_process.state = Status.running
        print(f"进程 {current_process.id} 在时间 {current_time} 执行")
        current_time += current_process.total_time
        current_process.remaining_time = 0
        completed_processes.append((current_process.id, current_time))
        print(f"进程 {current_process.id} 在时间 {current_time} 执行完毕")
        processes.remove(current_process)

    return completed_processes

processes = [
    PCB(1, 0, 10),
    PCB(2, 1, 4),
    PCB(3, 2, 5),
    PCB(4, 3, 3),
    PCB(5, 4, 8)
]

print("五个进程序列分别为：")
for process in processes:
    print(f"进程序号: {process.id}, 到达时间: {process.arrival_time}, 总时间: {process.total_time}")

print("请选择选用何种算法：1、SPF  2、RR")

a = input()
if int(a) == 1:
    result = spf_scheduler(processes)
    result.sort(key=lambda x: x[0])  # 按照进程ID排序
    
    print("\n")
    print("进程执行完成时间分别为:")
    for process_id, execution_time in result:
        print(f"进程 {process_id} 执行完成时间 {execution_time}")

if int(a) == 2:
    time_slice = 1
    result = round_robin_scheduler(processes, time_slice)
    result.sort(key=lambda x: x[0])  # 按照进程ID排序

    print("\n")
    print("进程执行完成时间分别为:")
    for process_id, execution_time in result:
        print(f"进程 {process_id} 执行完成时间 {execution_time}")
浏览量: 493
You Might Like