Notions d’interblocage

icône de pdf
Signaler

Le système dispose d’un ordonnanceur qui permet de gérer les accès concurrents aux ressources et prévenir certains problèmes que nous allons évoquer.

I) L’ordonnancement

Plusieurs processus peuvent être dans l’état prêt : comment choisir celui qui sera élu ? L’ordonnanceur (scheduler) classe les processus prêts dans une file et le répartiteur (dispatcher) alloue quant à lui un processeur à l’élu dans le cas d’une architecture multiprocesseur.

Il existe plusieurs politiques d’ordonnancement dont le choix va dépendre des objectifs du système. Voici quelques exemples :

Premier arrivé, premier servi : simple, mais peu adapté à la plupart des situations.

Plus court d’abord : très efficace, mais il est la plupart du temps impossible de connaître à l’avance le temps d’exécution d’un processus.

Priorité : le système alloue un niveau de priorité aux processus (SCHED_FIFO sur Linux). Cependant des processus de faible priorité peuvent ne jamais être élus.

Tourniquet : un quantum de temps est alloué à chaque processus (SCHED_RR sous Linux). Si le processus n’est pas terminé au bout de ce temps, il est mis en bout de file en état prêt.

Un système hybride entre tourniquet et priorité qu’on retrouve dans les systèmes Unix.

II) Un problème de synchronisation

1) Une situation type

Considérons un programme de jeu multi-joueurs contenant une variable globale nb_pions qui représente le nombre de pions disponibles pour tous les joueurs.

Une fonction permet de prendre un pion dans le tas commun de pions disponibles.

Imaginons deux joueurs utilisant cette fonction.

2) Des processus concurrents

L’exécution de ces fonctions se traduit par la création de deux processus P1 et P2, chacun correspondant à un joueur.

Supposons qu’il ne reste qu’un pion dans le tas. Supposons que le processus P1 est élu en premier. Il lance donc la prise d’un pion mais est interrompu par l’ordonnanceur pour élire P2 qui était en attente, et ce avant de décrémenter nb_pions. P2 est lancé alors qu’il reste encore un pion et a le temps lui de décrémenter nb_pions.

Quand P1 est élu à nouveau, il reprend où il en était et ne vérifie pas s’il reste un pion et ne voit pas d’anomalie : chacun se retrouve avec un pion alors qu’il n’y en avait qu’un.

III) Un problème d’interblocage

Imaginons un processus P1 demandant et obtenant une ressource R1 puis commuté par l’ordonnanceur. Un processus P2 est élu et demande et obtient R2 puis demande R1 mais ne peut l’obtenir car détenue par P1. P2 est donc commuté et P1 est élu et demande R2. Il est à son tour commuté et P2 est élu car R2 est détenue par P2.

Les processus P1 et P2 sont alors bloqués dans l’attente l’un de l’autre dans un cycle sans fin.

On parle dans ce cas d’interblocage. Des solutions (détection/guérison ou prévention) sont mises en place qui ne seront pas étudiées ici.

6c321204-6115-4d6b-9f82-95963d96d130

IV) Threads – Processus légers

Un thread (fil en français) désigne ce qui est appelé en français processus léger.

Plutôt que de se voir allouer une partie de la mémoire, les processus légers forment des groupes qui vont se partager un même espace mémoire mais ont chacun leur propre pile d’exécution.

Cette technique permet, par exemple, de faciliter le parallélisme sur des machines multiprocesseurs, ou de pouvoir laisser des calculs lourds se faire dans un fil et les échanges via le clavier et l’écran dans un autre. En contrepartie, les données étant partagées dans le même espace mémoire, cela impose une plus grande surveillance pour la synchronisation.