Treball més curt

El treball més curt, també conegut com a Shortest Job First (SJF) o Shortest Process Next (SPN), és una política de planificació que selecciona el procés amb el temps d'execució més petit per executar-lo a continuació o fins i tot per reemplaçar el procés que s'està executant.

Aquest mètode és avantatjós per motius de la seva simplicitat i perquè minimitza la quantitat mitjana de temps d'espera de cada procés fins que la seva execució s'hagi llençat. No obstant això, si entren contínuament processos curts implica que els processos llargs no s'arriben a executar mai.

Un altre desavantatge de l'ús del treball més curt és que el temps d'execució total d'un treball ha de ser conegut abans de l'execució. Si bé, encara que no és possible predir perfectament el temps d'execució, hi ha diversos mètodes que poden ser utilitzats per estimar el temps d'execució d'un treball, com, per exemple,una mitja ponderada dels temps d'execució anteriors.

A continuació passarem a explicar més detalladament l'algorisme SJF, les seves característiques, on es podria implementar aquesta planificació, un petit exemple i el codi en llenguatge C de l'algorisme.

Algorisme SJF

L'algorisme SJF es basa en els cicles de vida dels processos. Els cicles transcorren en dues etapes, o períodes, que són: cicles de CPU i cicles d'entrada/sortida (també coneguts per ràfegues).

La paraula shortest (el més curt) es refereix al procés que tingui el proper cicle de CPU més curt. La idea és escollir entre tots els processos "ready" (llests) el que tingui el seu proper cicle de CPU més petit.

El SJF es pot comportar de dues formes:

• Amb Desallotjament: Si s'incorpora un nou procés a la cua de llests i té un cicle de CPU menor que el cicle de CPU del procés que s'està executant, llavors aquest procés és desallotjat i el nou procés pren la CPU.
• Sense desallotjament: Quan un procés pren la CPU, cap altre procés podrà apropiar-se d'ella fins que el procés que la posseeix acabi d'executar-se.

Característiques

• El procés amb la ràfega de CPU més curta s'apropia de la CPU.
• Minimitza el temps d'espera mitjà.
• Risc que mai s'executin els processos de llarga durada.
• S'estima les durades dels processos segons el seu historial recent.

Implementació de SJF

Aquest tipus d'algorisme de planificació es fa servir per al processament per blocs, en els quals es pot saber el temps de durada de l'execució de cada procés i aleshores, es pot saber i seleccionar el procés més curt.

Exemple de SJF

Suposem que arriben els següents treballs als instants de temps indicats i amb la durada que es mostra a la taula següent:

TREBALLS	HORA D'ARRIBADA	DURADA DE CPU TEMPS DE SERVEI
T1	0	9
T2	3	5
T3	6	1

SOLUCIÓ:

ejemplo_jsf

Codi en C del algorisme

int main(){
int time,bt[10],at[10],sum_bt=0,smallest,n,i;
int sumt=0,sumw=0; printf("no of processes : "); 
scanf("%d",&n); 
for(i=0;i<n;i++){ 
printf("arrival time for process P%d : ",i+1); 
scanf("%d",&at[i]); 
printf("burst time for process P%d : ",i+1); 
scanf("%d",&bt[i]); sum_bt+=bt[i];
} 
bt[9]=9999; 
for(time=0;time<sum_bt;){ 
smallest=9; 
for(i=0;i<n;i++){ 
if(at[i]<=time && bt[i]>0 && bt[i]<bt[smallest])
smallest=i;
}
printf("P[%d]\t|\t%d\t|\t%d\n",smallest+1,time+bt[smallest]-at[smallest],time-at[smallest]);
sumt+=time+bt[smallest]-at[smallest]; 
sumw+=time-at[smallest]; 
time+=bt[smallest]; 
bt[smallest]=0;
} 
printf("\n\n average waiting time = %f",sumw*1.0/n);
printf("\n\n average turnaround time = %f",sumt*1.0/n); 
return 0;}

Annexos

Temes relacionats amb SJF:

Scheduling

És un component funcional molt important dels sistemes operatius multitasca i multiprocés, i és essencial en els sistemes operatius de temps real. La seva funció consisteix a repartir el temps disponible d'un microprocessador entre tots els processos que estan disponibles per a la seva execució. Per exemple, en un instant de temps, en l'ordinador poden existir diversos processos llests per ser executats, però només un d'ells pot ser executat en cada microprocessador. Per aquest motiu existeix la necessitat que una part del sistema operatiu gestioni, d'una manera equitativa, quin procés ha d'executar-se a cada moment per fer un ús eficient del processador.

Criteris de planificació

Els algorismes de planificació tindran diferents propietats que afavoriran a certa classe de processos. Per tant, és necessari definir criteris per poder avaluar els algorismes de planificació, que són:

• Utilització de CPU (CPU utilització): És el percentatge d'ús (quant a execució de tasques d'usuari o del sistema que són considerades útils) que té un processador.
• Rendiment (Throughput): És el nombre de processos que van executar completament per unitat de temps (p.ex: una hora).
• Temps de tornada (Turnaround time): És l'interval de temps des que un procés és carregat fins que aquest finalitza la seva execució.
• Temps d'espera (Waiting time): És la suma dels intervals de temps que un procés va estar en la cua de processos llests (ready queue).
• Temps de resposta (Response time): És l'interval de temps des que un procés és carregat fins que brinda la seva primer resposta. És útil en sistemes interactius.

Enllaços externs

• Algoritmo-sjf
• Ejemplo de jsf