Java 找出给定N个进程在循环调度中的执行顺序

在本文中，您将了解如何在循环调度算法中找到给定N个进程的执行顺序。但在开始编码之前，让我们先了解一下这个算法的工作原理。

循环调度是一种常用的CPU调度算法，用于以公平高效的方式为多个进程分配CPU时间。在本文中，我们将探讨循环调度的工作原理、优点和缺点，并提供一个示例来帮助您更好地理解概念。

什么是循环调度

循环调度是一种抢占式调度算法，每个进程被赋予一个固定的时间片或量子来执行。CPU调度器按照循环顺序将CPU时间分配给进程，因此得名“轮流”（round robin）。一旦一个进程使用完其时间片，它将被抢占并添加到就绪队列的末尾。然后，队列中的下一个进程被分配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恢复执行（需要3个单位的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()的函数，并初始化了诸如”waiting_time”、”turnaround_time”、”remaining”、”current”、”order_of_execution”和”ready_queue”之类的变量。一旦所有的操作都完成，就会开始一个循环。

• 在循环的每次迭代中，该函数将所有已到达当前时间的进程添加到就绪队列中。然后，就开始执行就绪队列中的第一个进程，执行时间为时间片或直到它完成，以先到者为准。

• 如果进程在时间片内未完成，它将被重新添加到就绪队列中。如果进程完成了，将计算其等待时间和周转时间。

• 在所有进程执行完毕后，该函数计算平均等待时间和周转时间，并将执行顺序作为数组返回。

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。然而，轮转调度可能会由于进程间频繁上下文切换而造成一些开销，并可能导致某些进程的等待时间较长。