Shortest job first

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.

v · m
  • Completely Fair Scheduler
  • EDF
  • FIFO
  • LIFO
  • Rate-monotonic
  • Round-robin
  • Shortest job first
  • Shortest remaining time
v · m
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
Concepts clés
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)
  • icône décorative Portail de l'informatique théorique