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>
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