时间片轮转调度的等待时间计算

### 计算时间片轮转调度算法中的等待时间

对于时间片轮转调度算法而言，等待时间是指一个进程从进入就绪队列到获得CPU处理之间所经历的时间总和。具体来说，在每次时间片到期时，当前正在运行的进程被中断并放回就绪队列末尾，而下一个处于就绪状态的进程则得到执行机会。

假设存在一组进程P1, P2,..., Pn，并且它们各自所需的服务时间为B1,B2,…, Bn秒。设时间片大小为T秒，则可以按照如下方式来估算各个进程的平均等待时间和周转时间：

- **首次响应时间**：即第一个时间片分配给该进程直到其真正开始被执行之间的间隔。通常情况下等于前面所有进程剩余服务时间加上自身已经消耗掉的部分时间片之和。

- **完成时刻**：指某个特定进程全部请求都得到了满足从而退出系统的瞬间。可以通过累加此进程中各次实际占用处理器期间以及中间可能产生的排队延迟得出。

- 到达时刻

- **等待时间**= 周转时间 - 服务时间

为了更直观地展示这一过程，下面给出一段Python代码用于模拟简单的RR调度机制及其对应的等待时间统计[^1]：

def rr_scheduling(processes, time_slice):
    n = len(processes)
    remaining_burst_time = [0] * n
    
    # 初始化剩余burst times
    for i in range(n):
        remaining_burst_time[i] = processes[i][2]

    t = 0  # 当前时间戳
    wait_times = []
    
    while True:
        done = True
        
        for i in range(len(processes)):
            if remaining_burst_time[i] > 0:
                done = False
                
                if remaining_burst_time[i] > time_slice:
                    t += time_slice
                    
                    remaining_burst_time[i] -= time_slice
                else:
                    t = t + remaining_burst_time[i]
                    
                    wait_times.append(t-processes[i][1]-processes[i][2])
                    
                    remaining_burst_time[i] = 0
            
        if done == True:
            break
            
    avg_wait_time = sum(wait_times)/len(wait_times)

    return avg_wait_time


# 测试数据集 [(id, arrival_time, burst_time)]
test_processes = [
    (1, 0, 8),
    (2, 1, 4),
    (3, 2, 9),
    (4, 3, 5)]

time_quantum = 2  

average_waiting_time = rr_scheduling(test_processes,time_quantum )

print(f'Average waiting time under RR scheduling with quantum {time_quantum}:', average_waiting_time )