### 用户调度算法实现代码示例 以下是基于多种常见调度算法（如先来先服务 FCFS、短作业优先 SJF、时间片轮转 RR 和优先级 HRRN）的 Python 实现代码示例： #### 1. 先来先服务 (FCFS) 调度算法 ```python def fcfs_scheduling(processes): n = len(processes) processes.sort(key=lambda x: x['arrival_time']) # 按照到达时间排序 total_waiting_time = 0 current_time = 0 for i in range(n): process = processes[i] waiting_time = max(0, current_time - process['arrival_time']) total_waiting_time += waiting_time current_time += process['burst_time'] print(f"Process {process['pid']} | Waiting Time: {waiting_time} units") avg_waiting_time = total_waiting_time / n print(f"\nAverage Waiting Time: {avg_waiting_time:.2f} units") # 测试数据 processes_fcfs = [ {'pid': 'P1', 'arrival_time': 0, 'burst_time': 8}, {'pid': 'P2', 'arrival_time': 1, 'burst_time': 4}, {'pid': 'P3', 'arrival_time': 2, 'burst_time': 9} ] fcfs_scheduling(processes_fcfs) ``` 此代码实现了先来先服务调度逻辑，按照进程到达顺序依次执行[^4]。 --- #### 2. 时间片轮转 (RR) 调度算法 ```python def rr_scheduling(processes, time_quantum=2): n = len(processes) remaining_burst_times = [p['burst_time'] for p in processes] total_waiting_time = 0 current_time = 0 queue_index = 0 while True: all_done = True for i in range(n): if remaining_burst_times[i] > 0: all_done = False if remaining_burst_times[i] > time_quantum: current_time += time_quantum remaining_burst_times[i] -= time_quantum else: current_time += remaining_burst_times[i] waiting_time = current_time - processes[i]['burst_time'] - processes[i]['arrival_time'] total_waiting_time += waiting_time remaining_burst_times[i] = 0 print(f"Process {processes[i]['pid']} | Waiting Time: {waiting_time} units") if all_done: break avg_waiting_time = total_waiting_time / n print(f"\nAverage Waiting Time: {avg_waiting_time:.2f} units") # 测试数据 processes_rr = [ {'pid': 'P1', 'arrival_time': 0, 'burst_time': 7}, {'pid': 'P2', 'arrival_time': 2, 'burst_time': 4}, {'pid': 'P3', 'arrival_time': 4, 'burst_time': 1} ] rr_scheduling(processes_rr, time_quantum=2) ``` 上述代码展示了如何通过设定固定的时间片大小 `time_quantum` 来实现时间片轮转调度[^2]。 --- #### 3. 短作业优先 (SJF) 非抢占式调度算法 ```python def sjf_scheduling(processes): n = len(processes) processes_sorted = sorted(processes, key=lambda x: (x['arrival_time'], x['burst_time'])) completion_times = [] current_time = 0 for proc in processes_sorted: if current_time < proc['arrival_time']: current_time = proc['arrival_time'] start_time = current_time current_time += proc['burst_time'] turnaround_time = current_time - proc['arrival_time'] waiting_time = turnaround_time - proc['burst_time'] completion_times.append({ 'pid': proc['pid'], 'start_time': start_time, 'completion_time': current_time, 'turnaround_time': turnaround_time, 'waiting_time': waiting_time }) total_waiting_time = sum([ct['waiting_time'] for ct in completion_times]) avg_waiting_time = total_waiting_time / n for ct in completion_times: print(f"Process {ct['pid']} | Start Time: {ct['start_time']} | Completion Time: {ct['completion_time']} " f"| Turnaround Time: {ct['turnaround_time']} | Waiting Time: {ct['waiting_time']} units") print(f"\nAverage Waiting Time: {avg_waiting_time:.2f} units") # 测试数据 processes_sjf = [ {'pid': 'P1', 'arrival_time': 0, 'burst_time': 6}, {'pid': 'P2', 'arrival_time': 2, 'burst_time': 1}, {'pid': 'P3', 'arrival_time': 4, 'burst_time': 4} ] sjf_scheduling(processes_sjf) ``` 这段代码实现了短作业优先调度策略，其中较短的任务会被优先安排执行。 --- #### 4. 动态优先级调度 (HRRN) 算法 ```python def hrrn_scheduling(processes): n = len(processes) current_time = 0 completed_processes = [] while len(completed_processes) != n: available_procs = [proc for proc in processes if proc not in completed_processes and proc['arrival_time'] <= current_time] if not available_procs: current_time += 1 continue selected_proc = None highest_priority = float('-inf') for proc in available_procs: priority = (current_time - proc['arrival_time'] + proc['burst_time']) / proc['burst_time'] if priority > highest_priority: highest_priority = priority selected_proc = proc current_time += selected_proc['burst_time'] selected_proc['completion_time'] = current_time selected_proc['turnaround_time'] = current_time - selected_proc['arrival_time'] selected_proc['waiting_time'] = selected_proc['turnaround_time'] - selected_proc['burst_time'] completed_processes.append(selected_proc) total_waiting_time = sum(proc['waiting_time'] for proc in completed_processes) avg_waiting_time = total_waiting_time / n for proc in completed_processes: print(f"Process {proc['pid']} | Arrival Time: {proc['arrival_time']} | Burst Time: {proc['burst_time']} " f"| Waiting Time: {proc['waiting_time']} units") print(f"\nAverage Waiting Time: {avg_waiting_time:.2f} units") # 测试数据 processes_hrrn = [ {'pid': 'P1', 'arrival_time': 0, 'burst_time': 3}, {'pid': 'P2', 'arrival_time': 2, 'burst_time': 6}, {'pid': 'P3', 'arrival_time': 4, 'burst_time': 4} ] hrrn_scheduling(processes_hrrn) ``` 以上代码演示了动态优先级调度算法的核心思想——根据响应比选择下一个要执行的进程。 --- ### 总结 这些代码分别对应不同的调度算法，涵盖了常见的 CPU 调度场景。每种算法都有其特定的应用场合和优缺点。