Lea aquí para conocer el algoritmo de programación de trabajo más corto primero para los mismos tiempos de llegada .
El trabajo más corto primero (SJF) o el trabajo más corto a continuación, es una política de programación que selecciona el proceso de espera con el menor tiempo de ejecución para ejecutar a continuación.
En este artículo, implementaremos el algoritmo SJF (Shorest Job First Scheduling) usando una cola de prioridad, de modo que podamos manejar los procesos en diferentes tiempos de llegada.
Ejemplos:
Input: The processes are
Process id Arrival time Burst time
p1 4 3
p2 0 8
p3 5 4
p4 9 2
Output: Process scheduling according to SJF is
Process id Arrival time Burst time
p2 0 8
p1 4 3
p4 9 2
p3 5 4
Input: The processes are
Process id Arrival time Burst time
p1 0 3
p2 0 8
p3 5 4
p4 9 2
Output: Process scheduling according to SJF is
Process id Arrival time Burst time
p1 0 3
p2 0 8
p4 9 2
p3 5 4
En este programa, la tarea es programar los procesos de acuerdo con el algoritmo de programación SJF, que establece que se dará prioridad al proceso con un tiempo de ráfaga mínimo, lo que puede implementarse simplemente clasificando el tiempo de ráfaga de los procesos en orden ascendente. El problema surge cuando tenemos que manejar los procesos en diferentes tiempos de llegada, entonces simplemente no podemos clasificar los procesos de acuerdo con el tiempo de ráfaga, ya que debemos considerar el tiempo de llegada del proceso para que el procesador no permanezca inactivo.
Ejemplo:
si un proceso con más tiempo de ráfaga llega antes que un proceso con menos tiempo de ráfaga, entonces tenemos que darle tiempo al procesador al proceso que llegó primero para que el procesador no se quede inactivo.
Acercarse:
Para manejar procesos con diferente hora de llegada en caso de programación SJF:
- Primero, ordene los procesos según la hora de llegada.
- Mantenga una cola de espera, que mantenga el proceso con un tiempo de ráfaga mínimo en la parte superior.
- Mantener el tiempo de ejecución actual, que es la suma de los tiempos de ráfaga de los procesos ejecutados.
- Un proceso ingresa a la cola de espera de acuerdo con su hora de llegada, si un nuevo proceso tiene una hora de llegada inferior
al tiempo de ejecución actual, se coloca en la cola de espera. - Un proceso se extrae de la cola de espera cuando se va a ejecutar. Su tiempo de ráfaga se agrega al tiempo de ejecución actual, su tiempo de llegada se actualiza a -1 para que no ingrese nuevamente a la cola de espera.
- Un proceso ingresa a la cola de espera de acuerdo con su hora de llegada, si un nuevo proceso tiene una hora de llegada inferior
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of SJF
#include <bits/stdc++.h>
using namespace std;
// number of process
#define SIZE 4
// Structure to store the
// process information
typedef struct proinfo {
string pname; // process name
int atime; // arrival time
int btime; // burst time
} proinfo;
// This structure maintains the
// wait queue, using burst
// time to compare.
typedef struct cmpBtime {
int operator()(const proinfo& a,
const proinfo& b)
{
return a.btime > b.btime;
}
} cmpBtime;
// This function schedules the
// process according to the SJF
// scheduling algorithm.
void sjfNonpremetive(proinfo* arr)
{
// Used to sort the processes
// according to arrival time
int index = 0;
for (int i = 0; i < SIZE - 1; i++) {
index = i;
for (int j = i + 1; j < SIZE; j++) {
if (arr[j].atime
< arr[index].atime) {
index = j;
}
}
swap(arr[i], arr[index]);
}
// ctime stores the current run time
int ctime = arr[0].atime;
// priority queue, wait, is used
// to store all the processes that
// arrive <= ctime (current run time)
// this is a minimum priority queue
// that arranges values according to
// the burst time of the processes.
priority_queue<proinfo, vector<proinfo>,
cmpBtime>
wait;
int temp = arr[0].atime;
// The first process is
// pushed in the wait queue.
wait.push(arr[0]);
arr[0].atime = -1;
cout << "Process id"
<< "\t";
cout << "Arrival time"
<< "\t";
cout << "Burst time"
<< "\t";
cout << endl;
while (!wait.empty()) {
cout << "\t";
cout << wait.top().pname << "\t\t";
cout << wait.top().atime << "\t\t";
cout << wait.top().btime << "\t\t";
cout << endl;
// ctime is increased with
// the burst time of the
// currently executed process.
ctime += wait.top().btime;
// The executed process is
// removed from the wait queue.
wait.pop();
for (int i = 0; i < SIZE; i++) {
if (arr[i].atime <= ctime
&& arr[i].atime != -1) {
wait.push(arr[i]);
// When the process once
// enters the wait queue
// its arrival time is
// assigned to -1 so that
// it doesn't enter again
// int the wait queue.
arr[i].atime = -1;
}
}
}
}
// Driver Code
int main()
{
// an array of process info structures.
proinfo arr[SIZE];
arr[0] = { "p1", 4, 3 };
arr[1] = { "p2", 0, 8 };
arr[2] = { "p3", 5, 4 };
arr[3] = { "p4", 9, 2 };
cout << "Process scheduling ";
cout << "according to SJF is: \n"
<< endl;
sjfNonpremetive(arr);
}
Java
// Java implementation of SJF
import java.util.*;
class GFG {
// number of process
static int SIZE = 4;
// A class to represent the
// process information
static class proinfo {
String pname; // process name
int atime; // arrival time
int btime; // burst time
proinfo(String pname, int atime, int btime)
{
this.pname = pname;
this.atime = atime;
this.btime = btime;
}
}
static void swap(int i, int idx, proinfo[] arr)
{
proinfo tmp = arr[i];
arr[i] = arr[idx];
arr[idx] = tmp;
}
// This function schedules the
// process according to the SJF
// scheduling algorithm.
static void sjfNonpremetive(proinfo[] arr)
{
// Used to sort the processes
// according to arrival time
int index = 0;
for (int i = 0; i < SIZE - 1; i++) {
index = i;
for (int j = i + 1; j < SIZE; j++) {
if (arr[j].atime < arr[index].atime) {
index = j;
}
}
swap(i, index, arr);
}
// ctime stores the current run time
int ctime = arr[0].atime;
// priority queue, wait, is used
// to store all the processes that
// arrive <= ctime (current run time)
// this is a minimum priority queue
// that arranges values according to
// the burst time of the processes.
PriorityQueue<proinfo> wait
= new PriorityQueue<proinfo>(
(a, b) -> { return a.btime - b.btime; });
// The first process is
// pushed in the wait queue.
wait.add(new proinfo(arr[0].pname, arr[0].atime,
arr[0].btime));
arr[0].atime = -1;
System.out.print("Process id"
+ "\t");
System.out.print("Arrival time"
+ "\t");
System.out.println("Burst time\t");
while (!wait.isEmpty()) {
System.out.print("\t");
System.out.print(wait.peek().pname + "\t\t");
System.out.print(wait.peek().atime + "\t\t");
System.out.println(wait.peek().btime + "\t\t");
// ctime is increased with
// the burst time of the
// currently executed process.
ctime += wait.peek().btime;
// The executed process is
// removed from the wait queue.
wait.remove();
for (int i = 0; i < SIZE; i++) {
if (arr[i].atime <= ctime
&& arr[i].atime != -1) {
wait.add(new proinfo(arr[i].pname,
arr[i].atime,
arr[i].btime));
// When the process once
// enters the wait queue
// its arrival time is
// assigned to -1 so that
// it doesn't enter again
// int the wait queue.
arr[i].atime = -1;
}
}
}
}
// Driver Code
public static void main(String[] args)
{
// an array of process info structures.
proinfo[] arr = new proinfo[SIZE];
arr[0] = new proinfo("p1", 4, 3);
arr[1] = new proinfo("p2", 0, 8);
arr[2] = new proinfo("p3", 5, 4);
arr[3] = new proinfo("p4", 9, 2);
System.out.print("Process scheduling ");
System.out.println("according to SJF is: \n");
sjfNonpremetive(arr);
}
}
// This code is contributed by Karandeep Singh
Python3
# Python 3 implementation of SJF
import heapq as hq
# number of process
SIZE=4
# This function schedules the
# process according to the SJF
# scheduling algorithm.
def sjfNonpremetive(arr):
# Used to sort the processes
# according to arrival time
index = 0
for i in range(SIZE - 1):
index = i
for j in range(i + 1, SIZE) :
if (arr[j][1] < arr[index][1]) :
index = j
arr[i], arr[index]=arr[index],arr[i]
# ctime stores the current run time
ctime = arr[0][1]
# priority queue, wait, is used
# to store all the processes that
# arrive <= ctime (current run time)
# this is a minimum priority queue
# that arranges values according to
# the burst time of the processes.
wait=[]
temp = arr[0][1]
# The first process is
# pushed in the wait queue.
hq.heappush(wait,arr[0].copy())
arr[0][1] = -1
print("Process id",end="\t")
print("Arrival time",end="\t")
print("Burst time",end="\t")
print()
while (wait) :
print(end="\t")
print(wait[0][2],end= "\t\t")
print(wait[0][1],end="\t\t")
print(wait[0][0],end="\t\t")
print()
# ctime is increased with
# the burst time of the
# currently executed process.
ctime += wait[0][0]
# The executed process is
# removed from the wait queue.
hq.heappop(wait)
for i in range(SIZE):
if (arr[i][1] <= ctime
and arr[i][1] != -1) :
hq.heappush(wait,arr[i].copy())
# When the process once
# enters the wait queue
# its arrival time is
# assigned to -1 so that
# it doesn't enter again
# int the wait queue.
arr[i][1] = -1
# Driver Code
if __name__ == '__main__':
# an array of process info structures.
arr=[None]*SIZE
arr[0] =[3, 4, "p1"]
arr[1] = [8, 0, "p2"]
arr[2] = [4, 5, "p3"]
arr[3] = [2, 9, "p4"]
print("Process scheduling according to SJF is: \n")
sjfNonpremetive(arr)
Producción:
Process scheduling according to SJF is:
Process id Arrival time Burst time
p2 0 8
p1 4 3
p4 9 2
p3 5 4
Complejidad de tiempo: O(N^2).
Espacio Auxiliar : O(N).
Publicación traducida automáticamente
Artículo escrito por DeveshRattan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA