Damien Vergnaud's Homepage

Exercice 1 - Lecteurs-Rédacteurs

Dans cet exercice, on considère la situation où une zone de mémoire partagée est accédée simultanément en lecture et en écriture. Il y a donc deux types de processus, d'une part des processus lecteurs et d'autre part des processus rédacteurs.

Deux objectifs doivent être atteints: le contenu de la zone de mémoire doit évidemment rester cohérent (donc les écritures ne doivent pas avoir lieu en même temps) et les lecteurs doivent lire une information stable (c'est-à-dire que les lecteurs ne doivent pas lire une information en cours de modification). Pour réaliser ces deux objectifs, il faut sur la zone de mémoire partagée : soit une seule écriture en cours, soit une ou plusieurs lectures en cours (les lectures simultanées ne gênant pas).

Un processus rédacteur accède toujours seul à la zone de mémoire (c'est-à-dire qu'il effectue des accès en exclusion mutuelle des autres rédacteurs et des lecteurs). Un lecteur exclut les rédacteurs mais pas les autres lecteurs (c'est-à-dire, seul le premier lecteur doit s'assurer qu'il n'y a pas d'accès en écriture en cours et seul le dernier lecteur doit réveiller un éventuel rédacteur). Il faut donc compter le nombre de lecteurs qui accèdent à la zone de mémoire partagée. Cette valeur doit rester cohérente (c'est-à-dire stockée dans une variable accédée en exclusion mutuelle).

1. Programmer un schéma lecteurs-rédacteur entre un processus père et ses deux fils pour l'accès à une variable commune. Le processus père modifie la variable commune en la multipliant par 10. Les processus fils lisent la valeur commune puis l'affiche.

2. L'approche décrite ci-dessus évite les interblocages mais malheureusement elle peut aboutir à un phénomène presque aussi grave : si un rédacteur tente d'accèder à la zone de mémoire partagée alors qu'un lecteur est dans la section critique, il peut attendre indéfiniment si un nouveau lecteur arrive avant que tous les lecteurs précédents ne partent. Modifier le programme précédent pour éviter ce phénomène de famine.

Exercice 2 - Le diner des philosophes

Ce problème est un grand classique des cours sur les systèmes d'exploitation : cinq philosophes sont réunis pour mener à bien deux activités majeures: "penser" et "manger". Chaque philosophe pense pendant un temps aléatoire, mange (si possible) pendant un temps aléatoire puis se remet à penser. Lorsqu'un philosophe demande à manger, un bol de riz l'attend. Les cinq bols sont disposés autour d'une table ronde. Pour qu'un philosophe puisse manger son riz, deux baguettes sont nécessaires : la sienne (celle de droite) et celle de son voisin de gauche. Naturellement, si l'un de ses voisins ou les deux voisins sont déjà en train de manger, le philosophe ne peut pas manger et doit patienter que l'une ou les deux baguettes occupées se libèrent.

La solution de ce problème doit être la plus optimisée possible : un philosophe voulant mais ne pouvant pas manger doit attendre son tour sans consommer de temps CPU inutilement. Chaque philosophe effectue plusieurs fois le cycle suivant :

• PENSE
• DEMANDE A MANGER
• MANGE

On doit naturellement constater que deux philosophes voisins ne mangent jamais en même temps, et qu'il ne risque pas d'avoir un interblocage.

1. Résoudre le problème du diner des philosophes en associant un sémaphore à chaque baguette. Chaque philosophe correspondra à un processus. (Le processus père lancera chaque philosophe et attendra).

2. Résoudre le problème du diner des philosophes en associant cette fois un sémaphore à chaque philosophe afin de profiter de sa file d'attente (un philosophe désirant manger mais ne le pouvant pas se placera dans la file d'attente de son sémaphore). Un tableau stockant l'état des philosophes ("PENSE", "DEMANDE A MANGER", "MANGE") sera stocké dans un segment de mémoire partagée (donc visible par les 5 processus). Ce segment de mémoire partagée devra être considéré comme une ressource critique (donc protégé par un sémaphore).

Aide

semget

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
 
int semget(key_t key, int nsems, int semflg);

semget crée un ensemble de sémaphores. L'entier retourné est le semid de l'ensemble de sémaphores ou -1 en cas d'erreur. semflag spécifie les priorités d'accès à l'ensemble de sémaphores. nsems désigne le nombre de sémaphores présents dans l'ensemble.

Exemple :

crée un ensemble de 4 sémaphores accessibles en lecture/écriture par tout processus.

semctl

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

union semun {    
		int val;
                struct semid_ds *buf;
                ushort *array
            }

int semctl(int semid, int semnum, int cmd, semun arg);

semctl permet de réaliser des opérations de contrôle sur l'ensemble de sémaphores identifié par semid. semnum désigne le numéro du sémaphore de l'ensemble concerné par l'opération, arg un (ou des) argument(s) variant suivant la commande. Le type d'opération est spécifié par cmd :

• GETVAL : renvoie la valeur de semval du sémaphore semnum.
• SETVAL : affecte la valeur arg.val à semnum.
• IPC_RMID : détruit les sémaphores de l'ensemble, semid et semid_ds.
• ...

Exemples :

union semun arg;
arg.val=1; 
semctl(semid,0,SETVAL,arg);

affecte la valeur 1 au premier sémaphore identifié par semid.

union semun arg;
arg.val=0; 
semctl(semid,0,IPC_RMID,arg);

détruit l'ensemble des sémaphores désigné par semid.

semop

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>


int semop(int semid, struct sembuf *sops, size_t nsops);

semop effectue une série d'opérations définies par les nsops éléments de sops, qui sont du type sembuf.

struct sembuf {
        ushort_t        sem_num;        /* semaphore # */
        short           sem_op;         /* semaphore operation */
        short           sem_flg;        /* operation flags */
};

Trois types d'opérations sont permis :

• sem_op < 0 (correspond au "P" : Proberen ou Puis-je ?)
  • Si (semval >= |sem_op|), alors semval = semval - |sem_op|.

  • Si (semval < |sem_op|), alors semncnt++ et le processus appelant est mis en attente jusqu'à ce que (semval >= |sem_op|). Ensuite, semncnt-- et semval=semval-|sem_op|.

• sem_op > 0 (correspond au "V" : Verhogen ou Vas-y !)
  • semval = semval + sem_op.
• sem_op = 0
  • Si (semval = 0), alors retour immédiat.

  • Si (semval != 0), alors semzcnt++ et le processus appelant est mis en attente jusqu'à ce que (semval=0). Ensuite, semznct--.

  Exemples :

  struct sembuf *sops;
  sops=(struct sembuf *)malloc(sizeof(struct sembuf));
  sops[0].sem_num = 0;
  sops[0].sem_op = -1;
  sops[0].sem_flg = 0;
  semop(semid,sops,1)
  

  correspond au "P" portant sur le premier sémaphore de l'ensemble de sémaphores identifié par semid.

  struct sembuf *sops;
  sops=(struct sembuf *)malloc(sizeof(struct sembuf));
  sops[0].sem_num = 0;
  sops[0].sem_op = 1;
  sops[0].sem_flg = 0;
  semop(semid,sops,1)
  

  correspond au "V" portant sur le premier sémaphore de l'ensemble de sémaphores identifié par semid.

  top