数据结构
网络
关系数据库管理系统(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 次浏览
广告