Python实现Round Robin调度时deque报'int'对象不可下标访问错误

问题现象 #

在Python3.10中实现Round Robin调度算法时，访问双端队列self.__ready_queue内的列表元素时，持续触发以下错误：

Traceback (most recent call last):
  File "/home/neo/Documents/Python/Scheduling Algorithms/rr.py", line 94, in <module>
    rr.calculate()
  File "/home/neo/Documents/Python/Scheduling Algorithms/rr.py", line 61, in calculate
    if list(self.__ready_queue)[i][2] <= self.time_quantum:
TypeError: 'int' object is not subscriptable

尝试打印该元素时显示正常，但在条件判断或f-string中使用时触发错误。

触发错误的代码块：

def calculate(self):
    grant_chart = f'{self.__ready_queue[0][1]} '
    n_a_t = 0
    completion_times = []
    i = 0
    while len(self.__ready_queue) != 0:
      if self.__ready_queue[i][2] <= self.time_quantum:
        n_a_t += self.__ready_queue[i][2]
        completion_times.append([self.__ready_queue[i][0], n_a_t])
        self.__ready_queue.popleft()
      else:
        n_a_t += self.time_quantum
        item = self.__ready_queue[i][2]
        self.__ready_queue[i][2] -= self.time_quantum
        self.__ready_queue.popleft()
        self.__ready_queue.append(item)
      gant_chart += f'{self.__ready_queue[i][0]} {n_a_t} '
      if i+1 > len(self.__ready_queue):
        i = 0
      else:
        i += 1
    print(gant_chart)

完整代码：

from tabulate import tabulate
from collections import deque

# INFO
# Completion Time - time to complete certain process
# Turn Around Time = Completion Time - Arrival Time

# Constants 
ARRIVAL_TIME = 'arrival_time'
BURST_TIME = 'burst_time'
COMPLETION_TIME = 'completion_time'
WAITING_TIME = 'waiting_time'
TURNAROUND_TIME = 'turnaround_time'

class RoundRobin:
  def __init__(self, processes: list, arrival_times: list, burst_times: list, time_quantum: int):
    self.time_quantum = time_quantum
    self.processes = processes
    self.arrival_times = arrival_times
    self.burst_times = burst_times
    self.__waiting_times = [0] * len(self.processes)
    self.__turnaround_times = [0] * len(self.processes)
    self.__completion_times = [0] * len(self.processes)
    self.__zipped = zip(
      self.processes, 
      self.arrival_times, 
      self.burst_times, 
      self.__completion_times,  
      self.__waiting_times, 
      self.__turnaround_times
      )
    self.__mapped = list(map(lambda x: list(x), self.__zipped))
    self.__sorted = sorted(self.__mapped, key=lambda x : x[1])
    self.__ready_queue = deque([[x[0], x[1], x[2]] for x in self.__sorted])
    self.__dicted = {
      x[0]: {
        ARRIVAL_TIME: x[1], 
        BURST_TIME: x[2], 
        COMPLETION_TIME: self.__completion_times[self.processes.index(x[0])], 
        WAITING_TIME: self.__waiting_times[self.processes.index(x[0])], 
        TURNAROUND_TIME: self.__turnaround_times[self.processes.index(x[0])]} 
        for x in self.__sorted
        }
    self.__table = tabulate(self.__mapped, headers=['Process ID', 'Arrival Time', 'Burst Time', 'Completion Time', 'Waiting Time', 'Turnaround Time'], tablefmt='github')

  def calculate(self):
    gant_chart = f'{self.__ready_queue[0][1]} '
    n_a_t = 0
    completion_times = []
    i = 0
    while len(self.__ready_queue) != 0:
      if self.__ready_queue[i][2] <= self.time_quantum:
        n_a_t += self.__ready_queue[i][2]
        completion_times.append([self.__ready_queue[i][0], n_a_t])
        self.__ready_queue.popleft()
      else:
        n_a_t += self.time_quantum
        item = self.__ready_queue[i][2]
        self.__ready_queue[i][2] -= self.time_quantum
        self.__ready_queue.popleft()
        self.__ready_queue.append(item)
      gant_chart += f'{self.__ready_queue[i][0]} {n_a_t} '
      if i+1 > len(self.__ready_queue):
        i = 0
      else:
        i += 1
    print(gant_chart)
    print(self.__ready_queue[i][0])
    
  def print_as_diagram(self):
    print(self.__table)
  
rr = RoundRobin(('p1', 'p2', 'p3', 'p4'), (0, 1, 2, 3), (8, 4, 10, 5), 4)
# rr.print_as_diagram()
rr.calculate()

问题根源 #

错误的核心是else分支中向队列添加了错误的元素类型：
在else分支里，item = self.__ready_queue[i][2]获取的是单个整数（剩余的CPU执行时间），随后self.__ready_queue.append(item)把这个整数加入了队列。而队列中原本的元素是三元组列表[进程ID, 到达时间, 剩余执行时间]，当后续循环访问这个整数元素时，尝试[i][2]就会触发TypeError，因为整数不支持下标访问。

另外，使用索引i来遍历双端队列的逻辑存在缺陷：每次调用popleft()后队列长度变化，索引i很容易越界，进一步引发其他错误。

修复方案 #

1. 修正队列元素添加逻辑 #

将else分支中添加单个整数的操作，改为添加修改后的完整进程三元组：

else:
    n_a_t += self.time_quantum
    # 获取当前进程的完整三元组
    current_process = self.__ready_queue[i]
    # 减去时间片长度
    current_process[2] -= self.time_quantum
    # 弹出头部元素后，将修改后的进程加入队列尾部
    self.__ready_queue.popleft()
    self.__ready_queue.append(current_process)

2. 优化遍历逻辑（推荐） #

Round Robin算法的核心是每次处理队列头部的进程，完全不需要使用索引i来访问队列元素，直接操作队列头部即可避免索引越界问题。优化后的calculate方法如下：

def calculate(self):
    # 处理空队列的边界情况
    if not self.__ready_queue:
        print("就绪队列为空")
        return
    
    gant_chart = f'{self.__ready_queue[0][1]} '
    n_a_t = 0
    completion_times = []
    
    while self.__ready_queue:
        # 每次取队列头部的进程
        current_process = self.__ready_queue[0]
        
        if current_process[2] <= self.time_quantum:
            # 进程剩余时间不足时间片，直接执行完毕
            n_a_t += current_process[2]
            completion_times.append([current_process[0], n_a_t])
            self.__ready_queue.popleft()
        else:
            # 进程剩余时间大于时间片，执行一个时间片后放回队列尾部
            n_a_t += self.time_quantum
            current_process[2] -= self.time_quantum
            self.__ready_queue.popleft()
            self.__ready_queue.append(current_process)
        
        # 更新甘特图时先判断队列是否为空
        if self.__ready_queue:
            gant_chart += f'{self.__ready_queue[0][0]} {n_a_t} '
    
    print(gant_chart)

额外说明 #

优化后的代码不仅修复了TypeError问题，还处理了队列空时的边界情况，同时逻辑更贴合Round Robin算法的核心思想，代码可读性和稳定性都有所提升。

内容的提问来源于stack exchange，提问作者Umidjon Juraboev