Encuentre el orden de ejecución de N procesos dados en la Programación Round Robin

Dada una array arr[] que representa el tiempo de ráfaga de N procesos programados utilizando el algoritmo Round Robin con el tiempo cuántico Q dado . Suponiendo que todos los procesos llegan en el tiempo t = 0 , la tarea es encontrar el orden en que se ejecutan los procesos.

Ejemplos:

Entrada: arr[] = {3, 7, 4}, q = 3
Salida: 0 2 1
Explicación:
El orden de ejecución es el siguiente P0, P1, P2, P1, P2, P1
Dado que P0 tiene un tiempo de ráfaga de 3 y el tiempo cuántico también es 3, se completa primero.
P1 tiene un tiempo de ráfaga de 7, por lo que después de ejecutarse durante 3 unidades, cambia de contexto y se ejecuta P2.
P2 tiene un tiempo de ráfaga de 4, por lo que después de ejecutarse durante 3 unidades, cambia de contexto y se ejecuta P1.
Nuevamente, P1 comienza a ejecutarse ya que le quedan 4 unidades de tiempo de ráfaga, por lo que se ejecuta durante otras 3 unidades y luego cambia de contexto.
Ahora el proceso P2 se ejecuta por 1 unidad y se completa.
Al final se completa el proceso P1.
Completan la ejecución en el orden P0, P2, P1.

Entrada: arr[] = {13, 8, 5}, q = 6
Salida: 2 1 0
Explicación: 
Inicialmente comienza P0 y después de 6 unidades, su contexto cambia.
P1 se ejecuta durante 6 unidades y cambia de contexto.
Dado que P2 tiene un tiempo de ráfaga menor que el tiempo cuántico, se ejecuta durante 5 unidades y se completa primero.
P0 tiene un tiempo de ráfaga restante de 7 unidades, por lo que se ejecuta de nuevo durante 6 unidades y cambia de contexto.
P1 tiene un tiempo de ráfaga restante de 2 unidades y se completa en segundo lugar.
Al final, el proceso P0 se completa.
Completan la ejecución en el orden P2, P1, P0.

Enfoque: La idea es crear una array auxiliar que contenga la frecuencia del número de veces que un proceso ha interactuado con la CPU . Luego, la array freq[] se puede ordenar en orden creciente de frecuencias. El proceso que tiene la menor frecuencia se completa primero, luego el segundo proceso, y así sucesivamente. La array ordenada da el orden de finalización del proceso. A continuación se muestran los pasos:

  • Inicialice una array freq[] , donde freq[i] es la cantidad de veces que el i -ésimo proceso ha interactuado con la CPU .
  • Inicialice la array order[] para almacenar el orden de finalización de los procesos y store order[i] = i .
  • Ordene la array order[]  en el orden creciente de freq[] tal que freq[order[i]] ≤ freq[order[i + 1]] .
  • Imprime el array order[] , que es el orden en el que los procesos completan su ejecución.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to sort the array order[]
// on the basis of the array freq[]
void merge(int* order, int* freq, int i,
           int mid, int j)
{
    int tempOrder[j - i + 1];
    int temp = mid + 1, index = -1;
 
    while (i <= mid && temp <= j) {
 
        // If order[i]th is less than
        // order[temp]th process
        if (freq[order[i]]
            <= freq[order[temp]]) {
            tempOrder[++index] = order[i++];
        }
 
        // Otherwise
        else {
            tempOrder[++index] = order[temp++];
        }
    }
 
    // Add the left half to tempOrder[]
    while (i <= mid) {
        tempOrder[++index] = order[i++];
    }
 
    // Add right half to tempOrder[]
    while (temp <= j) {
        tempOrder[++index] = order[temp++];
    }
 
    // Copy the tempOrder[] array to
    // order[] array
    for (index; index >= 0; index--) {
        order[j--] = tempOrder[index];
    }
}
 
// Utility function to sort the array
// order[] on the basis of freq[]
void divide(int* order, int* freq,
            int i, int j)
{
    // Base Case
    if (i >= j)
        return;
 
    // Divide array into 2 parts
    int mid = i / 2 + j / 2;
 
    // Sort the left array
    divide(order, freq, i, mid);
 
    // Sort the right array
    divide(order, freq, mid + 1, j);
 
    // Merge the sorted arrays
    merge(order, freq, i, mid, j);
}
 
// Function to find the order of
// processes in which execution occurs
void orderProcesses(int A[], int N, int q)
{
    int i = 0;
 
    // Store the frequency
    int freq[N];
 
    // Find elements in array freq[]
    for (i = 0; i < N; i++) {
        freq[i] = (A[i] / q)
                  + (A[i] % q > 0);
    }
 
    // Store the order of completion
    // of processes
    int order[4];
 
    // Initialize order[i] as i
    for (i = 0; i < N; i++) {
        order[i] = i;
    }
 
    // Function Call to find the order
    // of execution
    divide(order, freq, 0, N - 1);
 
    // Print order of completion
    // of processes
    for (i = 0; i < N; i++) {
        cout << order[i] << "  ";
    }
}
 
// Driver Code
int main()
{
    // Burst Time of the processes
    int arr[] = { 3, 7, 4 };
 
    // Quantum Time
    int Q = 3;
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    orderProcesses(arr, N, Q);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to sort the array order[]
// on the basis of the array freq[]
static void merge(int order[], int freq[], int i,
           int mid, int j)
{
    int tempOrder[] = new int[j - i + 1];
    int temp = mid + 1, index = -1;
 
    while (i <= mid && temp <= j)
    {
 
        // If order[i]th is less than
        // order[temp]th process
        if (freq[order[i]]
            <= freq[order[temp]])
        {
            tempOrder[++index] = order[i++];
        }
 
        // Otherwise
        else
        {
            tempOrder[++index] = order[temp++];
        }
    }
 
    // Add the left half to tempOrder[]
    while (i <= mid)
    {
        tempOrder[++index] = order[i++];
    }
 
    // Add right half to tempOrder[]
    while (temp <= j)
    {
        tempOrder[++index] = order[temp++];
    }
 
    // Copy the tempOrder[] array to
    // order[] array
  int ind= index;
    for (index= ind; index >= 0; index--)
    {
        order[j--] = tempOrder[index];
    }
}
 
// Utility function to sort the array
// order[] on the basis of freq[]
static void divide(int order[], int freq[],
            int i, int j)
{
    // Base Case
    if (i >= j)
        return;
 
    // Divide array into 2 parts
    int mid = i / 2 + j / 2;
 
    // Sort the left array
    divide(order, freq, i, mid);
 
    // Sort the right array
    divide(order, freq, mid + 1, j);
 
    // Merge the sorted arrays
    merge(order, freq, i, mid, j);
}
 
// Function to find the order of
// processes in which execution occurs
static void orderProcesses(int A[], int N, int q)
{
    int i = 0;
 
    // Store the frequency
    int freq[] = new int[N];
 
    // Find elements in array freq[]
    for (i = 0; i < N; i++)
    {
        freq[i] = (A[i] / q);
        if (A[i] % q > 0)
              freq[i] += 1;
    }
 
    // Store the order of completion
    // of processes
    int order[] = new int[4];
 
    // Initialize order[i] as i
    for (i = 0; i < N; i++) {
        order[i] = i;
    }
 
    // Function Call to find the order
    // of execution
    divide(order, freq, 0, N - 1);
 
    // Print order of completion
    // of processes
    for (i = 0; i < N; i++) {
        System.out.print( order[i] + "  ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Burst Time of the processes
    int arr[] = { 3, 7, 4 };
 
    // Quantum Time
    int Q = 3;
 
    int N = arr.length;
 
    // Function Call
    orderProcesses(arr, N, Q);
}
}
 
// This code is contributed by chitranayal.

C#

// C# program for the above approach
using System;
 
class GFG{
  
// Function to sort the array order[]
// on the basis of the array freq[]
static void merge(int[] order, int[] freq, int i,
                  int mid, int j)
{
    int[] tempOrder = new int[j - i + 1];
    int temp = mid + 1, index = -1;
  
    while (i <= mid && temp <= j)
    {
         
        // If order[i]th is less than
        // order[temp]th process
        if (freq[order[i]] <= freq[order[temp]])
        {
            tempOrder[++index] = order[i++];
        }
  
        // Otherwise
        else
        {
            tempOrder[++index] = order[temp++];
        }
    }
  
    // Add the left half to tempOrder[]
    while (i <= mid)
    {
        tempOrder[++index] = order[i++];
    }
  
    // Add right half to tempOrder[]
    while (temp <= j)
    {
        tempOrder[++index] = order[temp++];
    }
  
    // Copy the tempOrder[] array to
    // order[] array
    int ind = index;
    for(index = ind; index >= 0; index--)
    {
        order[j--] = tempOrder[index];
    }
}
  
// Utility function to sort the array
// order[] on the basis of freq[]
static void divide(int[] order, int[] freq,
                   int i, int j)
{
     
    // Base Case
    if (i >= j)
        return;
  
    // Divide array into 2 parts
    int mid = i / 2 + j / 2;
  
    // Sort the left array
    divide(order, freq, i, mid);
  
    // Sort the right array
    divide(order, freq, mid + 1, j);
  
    // Merge the sorted arrays
    merge(order, freq, i, mid, j);
}
  
// Function to find the order of
// processes in which execution occurs
static void orderProcesses(int[] A, int N, int q)
{
    int i = 0;
     
    // Store the frequency
    int[] freq = new int[N];
  
    // Find elements in array freq[]
    for(i = 0; i < N; i++)
    {
        freq[i] = (A[i] / q);
         
        if (A[i] % q > 0)
              freq[i] += 1;
    }
  
    // Store the order of completion
    // of processes
    int[] order = new int[4];
  
    // Initialize order[i] as i
    for(i = 0; i < N; i++)
    {
        order[i] = i;
    }
  
    // Function Call to find the order
    // of execution
    divide(order, freq, 0, N - 1);
  
    // Print order of completion
    // of processes
    for(i = 0; i < N; i++)
    {
        Console.Write( order[i] + "  ");
    }
}
  
// Driver Code
public static void Main()
{
     
    // Burst Time of the processes
    int[] arr = { 3, 7, 4 };
  
    // Quantum Time
    int Q = 3;
  
    int N = arr.Length;
  
    // Function Call
    orderProcesses(arr, N, Q);
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to sort the array order[]
// on the basis of the array freq[]
function merge(order, freq, i, mid, j)
{
    var tempOrder = Array(j - i + 1);
    var temp = mid + 1, index = -1;
 
    while (i <= mid && temp <= j) {
 
        // If order[i]th is less than
        // order[temp]th process
        if (freq[order[i]]
            <= freq[order[temp]]) {
            tempOrder[++index] = order[i++];
        }
 
        // Otherwise
        else {
            tempOrder[++index] = order[temp++];
        }
    }
 
    // Add the left half to tempOrder[]
    while (i <= mid) {
        tempOrder[++index] = order[i++];
    }
 
    // Add right half to tempOrder[]
    while (temp <= j) {
        tempOrder[++index] = order[temp++];
    }
 
    // Copy the tempOrder[] array to
    // order[] array
    for (index; index >= 0; index--) {
        order[j--] = tempOrder[index];
    }
}
 
// Utility function to sort the array
// order[] on the basis of freq[]
function divide(order, freq, i, j)
{
    // Base Case
    if (i >= j)
        return;
 
    // Divide array into 2 parts
    var mid = parseInt(i / 2) + parseInt(j / 2);
 
    // Sort the left array
    divide(order, freq, i, mid);
 
    // Sort the right array
    divide(order, freq, mid + 1, j);
 
    // Merge the sorted arrays
    merge(order, freq, i, mid, j);
}
 
// Function to find the order of
// processes in which execution occurs
function orderProcesses(A, N, q)
{
    var i = 0;
 
    // Store the frequency
    var freq = Array(N);
 
    // Find elements in array freq[]
    for (i = 0; i < N; i++) {
        freq[i] = (A[i] / q)
                  + (A[i] % q > 0);
    }
 
    // Store the order of completion
    // of processes
    var order = Array(4);
 
    // Initialize order[i] as i
    for (i = 0; i < N; i++) {
        order[i] = i;
    }
 
    // Function Call to find the order
    // of execution
    divide(order, freq, 0, N - 1);
 
    // Print order of completion
    // of processes
    for (i = 0; i < N; i++) {
        document.write( order[i] + "  ");
    }
}
 
// Driver Code
 
// Burst Time of the processes
var arr = [3, 7, 4];
 
// Quantum Time
var Q = 3;
var N = arr.length;
 
// Function Call
orderProcesses(arr, N, Q);
 
</script>
Producción: 

0  2  1

 

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *