資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學查詢輪詢排程中給定 N 個程序的執行順序
在本文中，您將學習如何查詢輪詢排程演算法中給定 N 個程序的執行順序。但在開始編寫程式碼之前，讓我們先了解一下該演算法的工作原理。
輪詢排程是一種流行的 CPU 排程演算法，作業系統使用它以公平有效的方式將 CPU 時間分配給多個程序。在本博文中，我們將探討輪詢排程的執行機制、優缺點，並提供一個示例來幫助您更好地理解該概念。
什麼是輪詢排程？
輪詢排程是一種搶佔式排程演算法，其中每個程序都會獲得固定的時間片或量子來執行。CPU 排程程式按迴圈順序將 CPU 時間分配給程序，因此稱為“輪詢”。一旦程序用完了它的時間片，它就會被搶佔並新增到就緒佇列的末尾。然後，佇列中的下一個程序將被分配 CPU 以使用其時間片。
每個程序的時間片或量子通常很小，通常在 10 到 100 毫秒之間。時間片較小的優點是每個程序都能獲得公平的 CPU 時間，並且透過頻繁地在程序之間切換來有效地利用 CPU。
場景
為了瞭解輪詢排程的工作原理，讓我們考慮一個示例。假設我們有四個需要執行的程序
程序 1：需要 6 個 CPU 時間單位
程序 2：需要 4 個 CPU 時間單位
程序 3：需要 2 個 CPU 時間單位
程序 4：需要 8 個 CPU 時間單位
我們假設輪詢排程演算法的時間量子設定為 3 個時間單位。在排程過程開始時，所有四個程序都按到達順序新增到就緒佇列中
Ready queue: [Process 1, Process 2, Process 3, Process 4]
然後，排程演算法以迴圈方式開始執行程序，每個程序給出一個 3 個單位的時間量子
時間 0：程序 1 開始執行（需要 3 個 CPU 時間單位）
時間 3：程序 2 開始執行（需要 3 個 CPU 時間單位）
時間 6：程序 3 開始執行（需要 2 個 CPU 時間單位）
時間 8：程序 1 恢復執行（需要 3 個 CPU 時間單位）
時間 11：程序 4 開始執行（需要 3 個 CPU 時間單位）
時間 14：程序 2 恢復執行（需要 1 個 CPU 時間單位）
時間 15：程序 1 執行完畢
時間 15：程序 3 恢復執行（需要 1 個 CPU 時間單位）
時間 16：程序 2 執行完畢
時間 16：程序 4 恢復執行（需要 5 個 CPU 時間單位）
時間 19：程序 3 執行完畢
時間 19：程序 4 恢復執行（需要 2 個 CPU 時間單位）
時間 21：程序 4 執行完畢
Process Queue: P1 P2 P3 P1 P4 P2 P1 P3 P2 P4 P3 P4 P4
從示例中可以看出，每個程序都會獲得 3 個時間單位的時間量子，而不管它需要多少 CPU 時間才能完成。一旦程序完成其時間量子，它就會被搶佔並移動到就緒佇列的末尾，在那裡等待直到輪到它再次執行。
虛擬碼
讓我們來看一下實現輪詢排程的虛擬碼。這裡我們建立了一個名為 round_robin() 的函式，並初始化了諸如“等待時間”、“週轉時間”、“剩餘時間”、“當前時間”、“執行順序”和“就緒佇列”之類的變數。一旦所有操作都已執行完畢，就會啟動一個迴圈。
該函式在迴圈的每次迭代中將所有截至當前時間已到達的程序新增到就緒佇列中。然後，對就緒佇列中的第一個程序執行時間量子或直到其完成，以先發生者為準。
如果程序在時間量子內未完成，則將其添加回就緒佇列。如果它完成，則計算其等待時間和週轉時間。
所有程序執行完畢後，該函式計算平均等待時間和週轉時間，並將執行順序作為陣列返回。
function round_robin(processes, quantum):
//Initialize variables
n = length of processes
waiting_time = an array of n elements, initialized to 0
turnaround_time = an array of n elements, initialized to 0
remaining_time = an array of n elements, initialized to the CPU burst time of each process
current_time = 0
order_of_execution = an empty array
ready_queue = an empty array
index = 0
//Loop until all processes are executed
while true:
//Add all processes that have arrived at the current time to the ready queue
for i from index to n-1:
if processes[i].arrival_time <= current_time:
add i to ready_queue
increment index
//Break the loop if all processes have been executed
if the ready_queue is empty and the sum of remaining_time is 0:
break
// Execute the first process in the ready queue
if the ready_queue is not empty:
process_index = the first element in ready_queue
remove the first element from ready_queue
add process_index to order_of_execution
if remaining_time[process_index] > quantum:
increment current_time by quantum
decrement remaining_time[process_index] by quantum
add process_index to ready_queue
else:
increment current_time by remaining_time[process_index]
set waiting_time[process_index] to current_time - processes[process_index].burst_time
set remaining_time[process_index] to 0
set turnaround_time[process_index] to current_time - processes[process_index].arrival_time
else:
increment current_time by 1
// Calculate average waiting time and turnaround time
avg_waiting_time = sum of waiting_time divided by n
avg_turnaround_time = sum of turnaround_time divided by n
// Return the order of execution and average waiting/turnaround time
return order_of_execution, avg_waiting_time, avg_turnaround_time
實現
在這裡，您可以找到上述虛擬碼在 Python 和 Java 中的實現
Python 示例
def round_robin(processes, quantum):
# Initialize variables
n = len(processes)
waiting_time = [0] * n
turnaround_time = [0] * n
remaining_time = [processes[i][1] for i in range(n)]
current_time = 0
order_of_execution = []
ready_queue = []
index = 0
# Loop until all processes are executed
while True:
# Add all processes that have arrived at the current time to the ready queue
for i in range(index, n):
if processes[i][0] <= current_time:
ready_queue.append(i)
index += 1
# Break the loop if all processes have been executed
if not ready_queue and sum(remaining_time) == 0:
break
# Execute the first process in the ready queue
if ready_queue:
process_index = ready_queue.pop(0)
order_of_execution.append(process_index)
if remaining_time[process_index] > quantum:
current_time += quantum
remaining_time[process_index] -= quantum
ready_queue.append(process_index)
else:
current_time += remaining_time[process_index]
waiting_time[process_index] = current_time - processes[process_index][1]
remaining_time[process_index] = 0
turnaround_time[process_index] = current_time - processes[process_index][0]
else:
current_time += 1
# Calculate average waiting time and turnaround time
avg_waiting_time = sum(waiting_time) / n
avg_turnaround_time = sum(turnaround_time) / n
return order_of_execution, avg_waiting_time, avg_turnaround_time
processes = [(0, 5), (1, 3), (2, 8), (3, 6)]
time_quantum = 2
order_of_execution, avg_waiting_time, avg_turnaround_time = round_robin(processes, time_quantum)
print("Order of execution:", order_of_execution)
print("Average waiting time:", avg_waiting_time)
print("Average turnaround time:", avg_turnaround_time)
輸出
此程式碼將輸出程序的執行順序，以及給定時間量子的輪詢排程演算法的平均等待時間和平均週轉時間。請注意，這只是一個示例實現，可能需要根據不同的用例或要求進行修改。
Order of execution: [0, 0, 1, 2, 0, 3, 1, 2, 3, 2, 3, 2] Average waiting time: 10.25 Average turnaround time: 14.25
Java 示例
import java.util.*;
class Process {
int pid; // process ID
int arrival_time; // arrival time of process
int burst_time; // CPU burst time of process
Process(int pid, int arrival_time, int burst_time) {
this.pid = pid;
this.arrival_time = arrival_time;
this.burst_time = burst_time;
}
}
public class RoundRobinScheduling {
//Driver method
public static void main(String[] args) {
Process[] processes = new Process[] {
new Process(1, 0, 10),
new Process(2, 3, 5),
new Process(3, 5, 8),
new Process(4, 6, 3),
new Process(5, 8, 6)
};
// Time quantum
int quantum = 2;
// Run Round Robin Scheduling algorithm
int[] order_of_execution = round_robin(processes, quantum);
// Print order of execution
System.out.println("Order of Execution: " + Arrays.toString(order_of_execution));
}
//method to implement round-robin cpu scheduling
public static int[] round_robin(Process[] processes, int quantum) {
// Initialize variables
int n = processes.length;
int[] waiting_time = new int[n];
int[] turnaround_time = new int[n];
int[] remaining_time = new int[n];
for (int i = 0; i < n; i++) {
remaining_time[i] = processes[i].burst_time;
}
int current_time = 0;
List<Integer> order_of_execution = new ArrayList<Integer>();
Queue<Integer> ready_queue = new LinkedList<Integer>();
int index = 0;
// Loop until all processes are executed
while (true) {
// Add all processes that have arrived at the current time to the ready queue
for (int i = index; i < n; i++) {
if (processes[i].arrival_time <= current_time) {
ready_queue.add(i);
index++;
}
}
// Break the loop if all processes have been executed
if (ready_queue.isEmpty() && Arrays.stream(remaining_time).sum() == 0) {
break;
}
// Execute the first process in the ready queue
if (!ready_queue.isEmpty()) {
int process_index = ready_queue.remove();
order_of_execution.add(process_index);
if (remaining_time[process_index] > quantum) {
current_time += quantum;
remaining_time[process_index] -= quantum;
ready_queue.add(process_index);
} else {
current_time += remaining_time[process_index];
waiting_time[process_index] = current_time - processes[process_index].burst_time - processes[process_index].arrival_time;
remaining_time[process_index] = 0;
turnaround_time[process_index] = current_time - processes[process_index].arrival_time;
}
} else {
current_time++;
}
}
// Convert order of execution from list to array
int[] order_of_execution_arr = new int[order_of_execution.size()];
for (int i = 0; i < order_of_execution.size(); i++) {
order_of_execution_arr[i] = order_of_execution.get(i);
}
// Print average waiting time and turnaround time
float avg_waiting_time = Arrays.stream(waiting_time).sum() / (float) n;
float avg_turnaround_time = Arrays.stream(turnaround_time).sum() / (float) n;
System.out.println("Average Waiting Time: " + avg_waiting_time);
System.out.println("Average Turnaround Time: " + avg_turnaround_time);
// Return order of execution
return order_of_execution_arr;
}
}
輸出
Average Waiting Time: 15.0 Average Turnaround Time: 21.4 Order of Execution: [0, 0, 0, 1, 0, 2, 3, 1, 4, 0, 2, 3, 1, 4, 2, 4, 2]
結論
輪詢排程是一種流行的 CPU 排程演算法，作業系統使用它以公平有效的方式將 CPU 時間分配給多個程序。它是一種搶佔式排程演算法，其中每個程序都會獲得固定的時間片或量子來執行。
輪詢排程確保每個程序都能獲得公平的 CPU 時間份額，並且透過頻繁地在程序之間切換來有效地利用 CPU。但是，輪詢排程可能會由於程序之間頻繁的上下文切換而導致一些開銷，並可能導致某些程序的等待時間更長。
更新於：2023年8月22日
410 次瀏覽
廣告