Valentin Haudiquet


Primitives de synchronisation dans un noyau

Au sein du noyau, la plupart du code se doit d'être thread-safe. En effet, le code risque d'être exécuté par plusieurs processus différents ; il suffit par exemple qu'un processus en train d'effectuer un appel système soit schedulé vers un autre processus qui effectue à son tour un appel système. De plus, dans un système multiprocesseur (multicœurs), certaines parties du noyau seront réellement exécutées en même temps par les différents processeurs.

Généralement, l'aspect thread-safe consiste en la pseudo-atomicité de toutes les opérations critiques. Certaines parties gérant par exemple le mappage de mémoire virtuelle, l'allocation de mémoire physique, l'allocation ou libération dans le heap noyau, etc sont donc rendues pseudo-atomiques par des procédés divers. L'atomicité n'est pas forcément réelle, c'est pourquoi on parle de pseudo-atomicité : par exemple, le heap sera entièrement bloqué durant un appel à kmalloc(), mais le processus effectuant cet appel pourra toujours être schedulé vers un processus effectuant des opérations en espace utilisateur ou des opérations noyau ne nécessitant pas le heap.

Mutexes

Les mutexes sont les formes les plus simples de structures de données permettant la synchronisation. Un mutex possède deux paramètres : un état (soit libre soit verrouillé) et une file d'attente. Quand un processus verouille un mutex libre, le mutex est marqué comme verrouillé. Dans ce cas, si un second processus verouille le mutex, il sera ajouté à la file d'attente de ce mutex et retiré du scheduler. Enfin, quand le premier processus libèrera le mutex, le premier processus en file d'attente sera ajouté au scheduler, et la file sera mise à jour. Ainsi, le second processus retrouvera son exécution et marquera le mutex comme verrouillé, avant de le libérer à son tour.

Ce mécanisme est très simple mais très efficace, et c'est un des plus utilisés en pratique. Il est parfait pour rendre une partie du noyau atomique, par exemple l'allocateur mémoire, le heap... En définissant un mutex kernel_heap, on est sûr que les accès au heap seront atomiques (tant que chaque fonction accédant au heap verrouille puis déverrouille ce mutex).

Il faut faire attention : les opérations mutex_lock et mutex_unlock se doivent, elles, d'être atomique.

Ci-dessous une implémentation de mutexes (en C) : (on considère avoir une structure de liste chainée simple list_t, un heap noyau et un scheduler)

typedef struct MUTEX
{
	int locked;
	list_t* waiting;
} mutex_t;

void mutex_lock(mutex_t* mutex)
{
	/* Clear interrupts : désactive les interruptions, 
	 * pour rendre le lock atomique */
	asm("cli"); 
	
	if(mutex->locked)
	{
		/* ajouter à la liste d'attente */
		list_t** ptr = &mutex->waiting;
		while(*(ptr)) ptr = &(*ptr)->next;
		(*ptr) = kmalloc(sizeof(list_t));
		(*ptr)->element = current_process;
		(*ptr)->next = 0;
		
		/* demander au scheduler de retirer 
		 * immédiatement ce processus,
		 * ce qui causera un appel à schedule() 
		 * et le rétablissement des interruptions 
		 */
		scheduler_remove_process(current_process);
	}
	
	mutex->locked = 1;
	
	/* Set interrupts : réactive les interruptions */
	asm("sti");
}

void mutex_unlock(mutex_t* mutex)
{
	/* Clear interrupts : désactive les interruptions, 
	* pour rendre unlock atomique */
	asm("cli");
	
	/* déverrouiller le mutex */
	mutex->locked = 0;
	
	/* retirer le premier processus de la liste */
	process_t* process = mutex->waiting->element;
	list_t* ptr = mutex->waiting;
	mutex->waiting = ptr->next;
	kfree(ptr);
	
	/* ajouter le processus à la file d'attente du scheduler */
	scheduler_add_process(process);
	
	/* Set interrupts : réactive les interruptions */
	asm("sti");
}

Les mutexes présentés ici nécessitent donc évidemment la présence d'un scheduler, et sont restreints à une synchronisation entre processus. Cependant, on peut par exemple imaginer la même chose mais en remplaçant le processus par un thread.

Un mutex peut présenter plusieurs problèmes. Tout d'abord, le temps de dé-scheduler le processus pour le re-ajouter ensuite peut être en moyenne bien supérieur au temps d'attente active (cf. spinlocks plus bas), si la ressource à synchroniser est utilisée pendant des temps très courts. Bien sur, cela n'a de sens que dans un environnement multi-processeur, sinon, il faudra dans tous les cas effectuer un cycle d'ordonnancement pour changer de processus.

Ensuite, l'implémentation ci-dessus ne fonctionne pas dans un système multiprocesseurs : on utilise deux instructions, un if et une assignation de variable, pour vérifier que le mutex est déverrouillé puis ensuite le verrouiller. Les deux processeurs ne peuvent pas accéder à la même zone mémoire en même temps (si l'on spécifie l'envoi du signal LOCK sur le BUS mémoire, par une instruction assembleur), mais ici les deux if pourraient s'exécuter d'abord puis les deux set : mutex->locked = 1 (et encore, il n'y a aucune raison pour qu'un if ou une assignation mémoire soit atomique...). Pour palier à cela, GCC propose des instructions atomiques pour vérifier et définir une valeur. On utilisera donc ici à la place __sync_bool_compare_and_swap(mutex, 0, 1) par exemple. Pour plus d'informations, voir Using GCC : __sync Builtins

Enfin, si la ressource à synchroniser permet un certain nombre d'accès concurrents différent de 1, on utilisera plutôt un sémaphore.

Sémaphores

Un sémaphore est un mutex possédent un compteur d'utilisations. On initialise un sémaphore en définissant son compteur au nombre total d'accès concurrents possibles (par exemple, si on considère un ordinateur connecté à 3 imprimantes, ce compteur sera à 3 : on peut faire jusqu'à trois impressions simultanées mais un quatrième processus demandant une impression devra attendre).

Il suffit donc de changer l'implémentation précédente de la façon suivante : locked est initialisé à k durant l'allocation d'un mutex, et mutex_lock diminue k ou endort le processus si k == 0. mutex_unlock augmentera alors k et réveillera le processus en tête de file.

Spinlocks

Dans un système multi-processeur, si le processeur A verrouille une ressource, le temps d'attente nécessaire pour qu'il la libère n'est peut être pas suffisant pour induire un ordonnancement sur le processeur B qui la demande. On perds en effet du temps sur le processeur B à effectuer la commutation de contexte (qui on le sait est une opération très coûteuse). Dans ce cas, si l'on sait que la ressource est souvent utilisée pendant des temps très courts, on peut utiliser un spinlock à la place d'un mutex.

On effectue alors uniquement une attente active, de la forme while(mutex->locked);. La boucle retourne dès que le mutex est déverrouillé. On ne fait donc pas de commutation de contexte.

Une implémentation simple reprenant l'implémentation précédente des mutex (en C) :

void spin_lock(mutex_t* mutex)
{
	while(mutex->locked);
	mutex->locked = 1;
}

De la même manière que précédemment, une implémentation réelle utilisera __sync_bool_compare_and_swap(mutex, 0, 1), comme ceci :

void spin_lock(mutex_t* mutex)
{
	while(!__sync_bool_compare_and_swap(mutex, 0, 1));
}

Les spinlocks et mutex peuvent être mixés : on peut choisir d'effectuer N itérations d'attente active avant d'endormir le processus, ... On peut aussi compter dynamiquement le temps d'attente à une ressource et adapter en fonction. Cet article ne développera pas les usages avancés.

Voir aussi

Mutex, Sémaphore et Spinlock sur Wikipédia

Synchronization Primitives sur OSDev