Shortest job first — Wikipédia

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En informatique, SJF est l’acronyme de Shortest Job First (« plus court processus en premier »). Il désigne une méthode d'ordonnancement des processus.

Il s’agit d’un algorithme d'ordonnancement, c'est-à-dire d’un algorithme servant à choisir lequel de plusieurs processus sera traité en premier par le processeur. Le choix se fait en fonction du temps d’exécution estimé du processus. Ainsi, l’ordonnanceur va laisser passer d'abord le plus court des processus de la file d’attente.

Il existe deux versions de cet algorithme : une version préemptive, et une version non préemptive. Dans cette dernière, un processus ayant pris le contrôle de l’UC ne le quitte qu’une fois la rafale terminée.

La version préemptive, aussi appelée SRTF, Shortest Remaining Time First (« plus court temps restant en premier »), est plus souple. Si un processus dont le temps d’exécution est plus court que le reste du temps d’exécution du processus en cours de traitement entre dans la file d’attente, alors il prendra sa place. Il y a alors une commutation de contexte, et le traitement du processus interrompu reprendra plus tard là ou il avait été laissé.

SJF s'avère un des algorithmes les plus rentables en ce qui concerne la réduction du temps passé dans la file d’attente des processus. Toutefois il est rarement utilisé en dehors d'environnements spécialisés, car il nécessite une évaluation précise du temps d'exécution de tous les processus en attente de traitement.

Portail de l'informatique théorique

v · m Théorie des files d'attente
Nœuds de file d'attente uniques	D/M/1 queue (en) M/D/1 queue (en) M/D/c queue (en) file M/M/1 Burke's theorem (en) M/M/c queue (en) M/M/∞ queue (en) M/G/1 queue (en) Formule de Pollaczek-Khinchine Matrix analytic method (en) M/G/k queue (en) G/M/1 queue (en) G/G/1 queue (en) Kingman's formula (en) Lindley equation (en) Fork–join queue (en) Bulk queue (en)
Processus d'arrivée	Processus de Poisson Markovian arrival process (en) Rational arrival process (en)
File de réseau	Jackson network (en) Traffic equations (en) Gordon–Newell theorem (en) Mean value analysis (en) Buzen's algorithm (en) Kelly network (en) G-network (en) BCMP network (en)
Politique de services	First in, first out Last in, first out Processor sharing (en) Shortest job first Shortest remaining time
Concepts clés	Processus de Markov à temps continu Notation de Kendall Théorie des files d'attente Product-form solution (en) Balance equation (en) Quasireversibility (en) Flow-equivalent server method (en) Arrival theorem (en) Decomposition method (queueing theory) (en) Beneš method (en)
Limite des théorèmes	Fluid limit (en) Mean field theory Heavy traffic approximation (en) Reflected Brownian motion (en)
Extensions	Fluid queue (en) Layered queueing network (en) Polling system (en) Adversarial queueing network (en) Loss network (en)