Support de Cours

Système d’Exploitation I

Chiheb Eddine Ben N’Cir

[email protected]

Plan

• Ordonnancement des processus

• Critères d’évaluation de la qualité

d’ordonnancement

• Les politiques d’ordonnancement: FCFS,SJF,

Round Robin, avec priorités

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Contexte

• Un processeur ne peut exécuter qu’un seul processus

• Les systèmes actuels permettent l’exécution de plusieurs

processus simultanément

Solution 1: Un processeur pour chaque processus

Solution 2: partager le processeur entre les processus

demandant simultanément le processeur

On parle d’ordonnancement des processus

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Objectifs de l’ordonnancement

• Maximiser le nombre de processus exécutés par unité de temps

• Maximiser le temps d’attente d’exécution de chaque processus

• Maximiser le temps d’utilisation des processeurs et autre ressources

• Eviter le problème de famine

• Favoriser les processus les plus prioritaires

• Minimiser le nombre de changements de contexte

→ Difficile de satisfaire tous les objectifs à la fois

Solution: Satisfaire les objectifs selon un ordre de priorité (sachant les

objectifs derrière l’utilisation du SE)

Ben N’Cir chiheb-Eddine-ESEN-Manouba

L’ordonnanceur

• Le système d'exploitation applique un programme pour gérer l'ordre

d'exécution des processus, appelé scheduler, dispatcher ou

ordonnanceur.

• L'ordonnanceur dispose de plusieurs algorithmes d'ordonnancement

qui correspondent à différentes politiques d'organisation des

processus : équitable, avec priorité, plus court d'abord. Il agit sur la file

des processus prêts et l'organise en appliquant un algorithme donné.

• Il faut souligner à ce stade que l'ordonnanceur ne change pas de

politique d'ordonnancement. Chaque système d'exploitation applique

un algorithme choisi par les concepteurs.

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Mode d’ordonnancement

Deux classes d’ordonnanceur:

1. Non préemptif: (sans réquisition) Sélectionne un processus, puis le

laisse s’exécuter jusqu’à ce qu’il bloque (soit sur une E/S, soit en

attente d’un autre processus) où qu’il libère volontairement le

processeur. Même s’il s’exécute pendant des heures, il ne sera pas

suspendu de force. Aucune décision d’ordonnancement

n’intervient pendant le s interruptions de l’horloge.

2. Préemptif: (avec réquisition) Sélectionne un processus et le laisse

s’exécuter pendant un délai déterminé. Si le processus est toujours

en cours à l’issue de ce délai, il est suspendu et le scheduleur

sélectionne un autre processus à exécuter.

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Règles d’arbitrages

• Si deux processus ont le même ordre selon la politique

d’ordonnancement, le système d’exploitation utilise des

règles d’arbitrages pour choisir le processus à exécuter

• Les règles d’arbitrages possibles:

Aléatoire,
plus court processus,
processus le plus prioritaire,
etc…

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Système multi-processus

ordonnancement haut niveau et bas niveau

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Critère d’évaluation de la performance de

l’ordonnancement

• Rendement (throughput) :

Nombre de travaux exécutés par unité de temps.

• Temps de service (turnaround time):

Temps qui s'écoule entre le moment où un travail est soumis et

où il est exécuté (temps d'accès mémoire + temps d'attente en

file des éligibles + temps d'exécution dans le processeur et E/S).

• Temps d'attente (waiting time) :

Temps passé dans la file des processus éligibles.

• Temps de réponse (response time):

Temps qui s'écoule entre la soumission d'une requête et la

première réponse obtenue.

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Politique d’ordonnancement 1

FCFS

• Le processus qui arrive premier occupera le processeur

• L’implantation de la politique FCFS est facilement gérée

avec une file d’attente FIFO. Une fois que la CPU a été

allouée à un processus, celui-ci garde la CPU jusqu’à ce qu’il

la libère (fin ou E/S).

• FCFS est particulièrement inapproprié pour le temps

partagé où il est important que chaque utilisateur obtienne

la CPU à des intervalles réguliers.

• Temps moyen d’attente: généralement n’est pas minimal et

peut varier substantiellement si les temps de cycles de la

CPU du processus varient beaucoup

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Exercice

Processus

Date arrivée

Temps CPU

1) Donner le Diagramme de Gantt de l’exécution des processus en utilisant l’ordonnanceur

FCFS

2) Calculer les indicateurs de performance suivants: Temps d’attente Moyen (TA), Temps

de réponse Moyen (TR), Temps de service moyen (TS), Rendement (4-microseconde)

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Politique d’ordonnancement 2

SJF

• Short Job First (SJF) Le processus qui a le temps CPU le plus minimale

sera exécuté

• Associe à chaque processus la longueur de son prochain cycle de

CPU. Quand la CPU est disponible, elle est assignée au processus

qui possède le prochain cycle le plus petit.

• Si deux processus possèdent la même longueur, le FCFS peut être

utilisé (arbitrage).

• SJF est optimal: il obtient le temps moyen d’attente minimal pour

un ensemble de processus donné.

• Difficulté: pouvoir connaître la longueur de la prochaine requête

de la CPU , problème famine

• Deux mode: Non préemptif et préemptif.

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Exercice

Processus

Date arrivée

Temps CPU

1) Donner le Diagramme de Gantt de l’exécution des processus en utilisant l’ordonnanceur

SJF sans réquisition

2) Calculer les indicateurs de performance suivants: Temps d’attente Moyen (TA), Temps

de réponse Moyen (TR), Temps de service moyen (TS), Rendement (4-microseconde)

3) Donner le Diagramme de Gantt de l’exécution des processus en utilisant l’ordonnanceur

SJF avec réquisition

4) Calculer les indicateurs de performance suivants: Temps d’attente Moyen (TA), Temps

de réponse Moyen (TR), Temps de service moyen (TS), Rendement (4-microseconde)

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Politique d’ordonnancement 3

Tourniquet

• Appelé aussi Round Robin (RR)

• Chaque processus a une petite unité de temps appelée tranche de

temps ou Quantum q.

• Le scheduleur de la CPU parcourt la file d’attente des processus prêts

en allouant la CPU à chaque processus pendant un intervalle de

temps allant jusqu’à un quantum.

• Lorsque un processus actif épuise son quantum q, il libère le

processeur ensuite il est placé en queue d’une liste

• La file d’attente des processus prêts est implantée comme une file

FIFO.

• Les nouveaux processus sont placés à la fin de la liste

• tous les processus ont la même priorité

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Exercice

Processus

Date arrivée

Temps CPU

1) Donner le Diagramme de Gantt de l’exécution des processus en utilisant l’ordonnanceur

Round Robin avec q=3.

2) Calculer les indicateurs de performance suivants: Temps d’attente Moyen (TA), Temps

de réponse Moyen (TR), Temps de service moyen (TS), Rendement (4-microseconde)

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Politique d’ordonnancement 3

Tourniquet

Performance:

• Si le quantum est trop grand: RR devient FCFS

• Si le quantum est très petit: RR est appelé partage du

processeur (si n processus résident dans la file, la

vitesse du processeur est ralentie de 1/n, selon

l’utilisateur

• Généralement, q doit être suffisamment grand par

rapport au temps de commutation

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Politique d’ordonnancement 4

Avec Priorité

• Une priorité est associée à chaque processus. CPU est allouée au processus de plus

haute priorité (priorité = 1 > priorité = 2 )

•

Les processus ayant la même priorité sont schedulés dans un ordre FCFS ou SJF (règle

d’arbitrage).

• Exemple Processus Temps de cycle Priorité

• Deux Modes d’exécutions: Préemptif et non préemptif

• Problème: Famine (starvation) ou blocage indéfinie: processus avec des basses priorités

peuvent attendre indéfiniment (ne jamais être exécutés).

•

Solution: Vieillissement : technique qui consiste à augmenter la priorité des processus

plus vieux.

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Evaluations des algorithmes

d’ordonnancement

• FCFS: pénalise les processus de court temps

d’exécution

• SJF: problème de famine

• Tourniquet: Bien choisir le Quantum de temps par

rapport au cout de commutation de contexte

• Priorité :Risque de famine des processus de faible

priorité

Ben N’Cir chiheb-Eddine-ESEN-Manouba

Scheduling avec des files d’attente à multi-

niveaux

Séparer les processus ayant des caractéristiques différentes de cycle de CPU en différentes files.

Permet aux processus de se déplacer entre les files.

Processus employant beaucoup de temps processeur: file de priorité inférieure

Processus tributaire E/S: file de priorité supérieure

Processus qui attend trop longtemps dans une file de priorité basse peut

être déplacé à un file de priorité supérieure

Exemple: 3 files d’attente

Q0: quantum 8ns; Q1: quantum 16ns ; Q2: FCFS

Un nouveau processus est inséré dans Q0

Processus de Q0: S’il ne finit pas en 8ns, alors il est interrompu et placé en

Si Q0 est vide, le processus en tête de Q1 prend la CPU. S’il ne termine pas en 16ns, il est

interrompu et mis dans Q2

Processus de Q2: exécutés avec FCFS (seulement quand Q0 et Q1 sont vides)

Ben N’Cir chiheb-Eddine-ESEN-Manouba