Section courante

A propos

Section administrative du site

L'utilisation du Concurrent Pascal

Nous allons maintenant programmer les composantes du système un par un, de haut en bas (mais nous pourrions tout aussi bien le faire de bas en haut). Bien que nous n'ayons besoin que d'un seul processus d'entrée, nous pouvons tout aussi bien le définir comme un type de système général dont plusieurs copies peuvent exister :

  1. type 
  2.  inputprocess=process(buffer:diskbuffer);
  3.  
  4. var 
  5.  block:page;
  6.  
  7. cycle
  8.  readcards(block);
  9.  buffer.send(block);
  10. end

Un processus d'entrée a accès à un buffer de type diskbuffer (à définir ultérieurement). Le processus possède une variable privée block de type page. Le type de données page est déclaré ailleurs sous la forme d'un tableau de caractères :

  1. type page=array[1..512] of char

Un type de processus définit un programme séquentiel, dans ce cas, un cycle sans fin saisissant un bloc à partir d'un lecteur de cartes et l'envoie via le tampon à un autre processus. Nous ignorerons les détails de l'entrée du lecteur de cartes. L'opération d'envoi sur le tampon est appelée comme suit (en utilisant le bloc comme paramètre) :

  1. buffer.send(block)

Le prochain type de composante que nous allons définir est un processus de travail :

  1. type 
  2.  jobprocess=process(input, output:diskbuffer);
  3.  
  4. var 
  5.  block:page;
  6.  
  7. cycle
  8.  input.receive(block);
  9.  update(block);
  10.  output.send(block);
  11. end

Un processus de travail a accès à deux tampons de disque appelés entrée et sortie. Il reçoit des blocs d'un tampon, les met à jour et les envoie via l'autre tampon. Les détails de la mise à jour peuvent être ignorés ici. Enfin, nous avons besoin d'un processus de sortie pouvant recevoir des données d'un tampon de disque et les sortir sur une imprimante ligne par ligne :

  1. type 
  2.  outputprocess=process(buffer:diskbuffer);
  3.  
  4. var 
  5.  block:page;
  6.  
  7. cycle
  8.  buffer.receive(block);
  9.  printlines(block);
  10. end

Ce qui suit montre une déclaration des principaux composantes du système :

  1. var
  2.  buffer1,buffer2:diskbuffer;
  3.  reader:inputprocess;
  4.  master:jobprocess;
  5.  writer:outputprocess;

Il y a un processus d'entrée, appelé «reader», un processus de travail, appelé «master», et un processus de sortie, appelé «writer». Ensuite, il y a deux tampons de disque, «buffer1» et «buffer2», qui les relient.

J'expliquerai plus tard comment un tampon de disque est défini et initialisé. Si nous supposons que les tampons de disque ont déjà été initialisés, nous pouvons initialiser le processus d'entrée comme suit :

  1. init reader(buffer1)

L'instruction init alloue de l'espace aux variables privées du processus lecteur et démarre son exécution en tant que processus séquentiel avec accès à buffer1. Les droits d'accès d'un processus à d'autres composantes du système, tels que buffer1, sont également appelés ses paramètres. Un processus ne peut être initialisé qu'une seule fois. Après l'initialisation, les paramètres et les variables privées d'un processus existent pour toujours. On les appelle variables permanentes.

L'instruction init peut être utilisée pour démarrer l'exécution simultanée de plusieurs processus et définir leurs droits d'accès. Par exemple, l'instruction :

  1. init reader(buffer1), master(buffer1, buffer2), writer(buffer2)

démarre l'exécution simultanée du processus lecteur (avec accès à buffer1), du processus maître (avec accès aux deux tampons) et du processus écrivant (avec accès à buffer2).

Un processus ne peut accéder qu'à ses propres paramètres et variables privées. Ces dernières ne sont pas accessibles aux autres composantes du système. Comparez cela aux règles de portée plus libérales des langages de programmation à structure de blocs dans lesquels un bloc de programme peut accéder non seulement à ses propres paramètres et variables locales, mais aussi à ceux déclarés dans les blocs externes. Dans Concurrent Pascal, toutes les variables accessibles à une composante système sont déclarées dans sa définition de type. Cette règle d'accès et l'instruction init permettent à un programmeur d'indiquer explicitement les droits d'accès et de les faire vérifier par un compilateur. Elles permettent également d'étudier un type système comme une unité de programme autonome.

Bien que les exemples de programmation ne le montrent pas, on peut également définir des constantes, des types de données et des procédures au sein d'un processus. Ces objets ne peuvent être utilisés qu'au sein du type de processus.

Moniteurs

Le tampon de disque (disk buffer) est un type de moniteur :

  1. type 
  2.  diskbuffer=monitor(consoleaccess,diskaccess:resource;base,limit:integer);
  3.  
  4. var
  5.  disk:virtualdisk; 
  6.  sender,receiver:queue;
  7.  head,tail,length:integer;
  8.  
  9. procedure entry send(block:page);begin
  10.  if length = limit then delay(sender);
  11.  disk.write(base + tail, block);
  12.  tail := (tail + 1) mod limit;
  13.  length := length + 1;
  14.  continue(receiver);
  15. end;
  16.  
  17. procedure entry receive(var block:page);begin
  18.  if length = 0 then delay(receiver);
  19.  disk.read(base + head, block);
  20.  head := (head + 1) mod limit;
  21.  length := length - 1;
  22.  continue(sender);
  23. end;
  24.  
  25. begin "initialisation d'instruction"
  26.  init disk(consoleaccess, diskaccess);
  27.  head:=0; tail:=0; length:=0;
  28. end

Un tampon de disque a accès à deux autres composantes, consoleaccess et diskaccess, de type resource (à définir ultérieurement). Il a également accès à deux constantes entières définissant l'adresse de base et la limite du tampon sur le disque.

Le moniteur déclare un ensemble de variables partagées : Le disque est déclaré comme une variable de type virtualdisk. Deux variables de type queue sont utilisées pour retarder les processus expéditeur et destinataire jusqu'à ce que le tampon devienne non plein et non vide. Trois entiers définissent les adresses relatives des éléments de tête et de queue du tampon et sa longueur actuelle.

Le moniteur définit deux procédures de moniteur, send et receive. Elles sont marquées du mot entry pour les distinguer des procédures locales utilisées dans le moniteur (il n'y en a aucune dans cet exemple).

receive renvoie une page au processus appelant. Si le tampon est vide, le processus appelant est retardé dans la file d'attente du récepteur jusqu'à ce qu'un autre processus envoie une page via le tampon. La procédure receive lira et supprimera ensuite une page de la tête du tampon du disque en appelant une opération de lecture définie dans le type de disque virtuel :

  1. disk.read(base+head,block)

Enfin, la procédure de réception poursuivra l'exécution d'un processus d'envoi (si ce dernier est en attente dans la file d'attente de l'expéditeur).

send est similaire à receive.

Le mécanisme de mise en file d'attente sera expliqué en détail dans la section suivante. L'instruction initiale d'un tampon de disque initialise son disque virtuel avec accès à la console et aux ressources du disque. Elle définit également la longueur du tampon à zéro. (Remarque : un tampon de disque n'utilise pas ses droits d'accès à la console et au disque, mais les transmet uniquement à un disque virtuel déclaré en son sein.)

Ce qui suit montre une déclaration de deux composantes système de type ressource et de deux entiers définissant la base et la limite d'un tampon de disque :

  1. var 
  2.  consoleaccess,diskaccess:resource;
  3.  base,limit:integer;
  4.  buffer:diskbuffer;

Si nous supposons que ces variables ont déjà été initialisées, nous pouvons initialiser un tampon de disque comme suit :

  1. init buffer(consoleaccess, diskaccess, base, limit)

L'instruction init alloue de l'espace d'entreposage pour les paramètres et les variables partagées du tampon de disque et exécute son instruction initiale.

Un moniteur ne peut être initialisé qu'une seule fois. Après l'initialisation, les paramètres et les variables partagées d'un moniteur existent pour toujours. On les appelle variables permanentes. Les paramètres et les variables locales d'une procédure de moniteur, en revanche, n'existent que pendant son exécution. On les appelle variables temporaires.

Une procédure de moniteur ne peut accéder qu'à ses propres variables temporaires et permanentes. Ces variables ne sont pas accessibles aux autres composantes du système. D'autres composantes peuvent cependant appeler des entrées de procédure dans un moniteur. Pendant qu'une procédure de moniteur est en cours d'exécution, elle a un accès exclusif aux variables permanentes du moniteur. Si des processus concurrents tentent d'appeler simultanément des procédures dans le même moniteur, ces procédures seront exécutées strictement une à la fois.

Seuls les moniteurs et les constantes peuvent être des paramètres permanents de processus et de moniteurs. Cette règle garantit que les processus ne communiquent que par l'intermédiaire de moniteurs.

Il est possible de définir des constantes, des types de données et des procédures locales dans les moniteurs (et les processus). Les procédures locales d'un type système ne peuvent être appelées qu'au sein du type système. Pour éviter le blocage des appels de moniteur et garantir que les droits d'accès sont hiérarchiques, les règles suivantes sont appliquées : une procédure doit être déclarée avant de pouvoir être appelée; les définitions de procédure ne peuvent pas être imbriquées et ne peuvent pas s'appeler elles-mêmes; un type système ne peut pas appeler ses propres entrées de procédure.

L'absence de récursivité permet à un compilateur de déterminer les exigences d'entreposage de tous les composantes système. Cela et l'utilisation de composantes permanentes permettent d'utiliser une allocation d'entreposage fixe sur un ordinateur ne prenant pas en charge la pagination.

Les composantes système étant permanentes, elles doivent être déclarés comme variables permanentes d'autres composantes.

Files d'attente

Une procédure de surveillance peut retarder un processus appelant pendant une durée quelconque en exécutant une opération de retard sur une variable de file d'attente. Un seul processus à la fois peut attendre dans une file d'attente. Lorsqu'un processus appelant est retardé par une procédure de surveillance, il perd son accès exclusif aux variables de surveillance jusqu'à ce qu'un autre processus appelle le même moniteur et exécute une opération de continuation sur la file d'attente dans laquelle le processus attend.

L'opération de continuation fait revenir le processus appelant de son appel de surveillance. Si un processus attend dans la file d'attente sélectionnée, il reprendra immédiatement l'exécution de la procédure de surveillance l'ayant retardé. Après avoir repris, le processus a de nouveau un accès exclusif aux variables permanentes du moniteur.

D'autres variantes de files d'attente de processus (appelées «événements» et «conditions») sont proposées par Brinch Hansen (1972) et Hoare (1974). Ce sont des files d'attente multiprocessus utilisant des règles d'ordonnancement différentes (mais fixes). Une file d'attente à processus unique est l'outil le plus simple donnant au programmeur un contrôle complet sur la planification des processus individuels.

Plus tard, nous montrerons comment des files d'attente multiprocessus peuvent être construites à partir de files d'attente à processus unique. Une file d'attente doit être déclarée comme une variable permanente dans un type de moniteur.

Classes

Chaque tampon de disque possède son propre disque virtuel. Un disque virtuel est défini comme un type de classe :

  1. type 
  2.  virtualdisk=class(consoleaccess,diskaccess:resource);
  3.  
  4. var 
  5.  terminal:virtualconsole; 
  6.  peripheral:disk;
  7.  
  8. procedure entry read(pageno:integer;var block:page);
  9. var 
  10.  error:boolean;
  11. begin
  12.  repeat
  13.   diskaccess.request;
  14.   peripheral.read(pageno,block,error);
  15.   diskaccess.release;
  16.   if error then terminal.write('panne de disque');
  17.  until not error;
  18. end;
  19.  
  20. procedure entry write(pageno:integer;block:page);begin
  21.  "similaire à lire" 
  22. end;
  23.  
  24. begin "instruction initiale"
  25.  init terminal(consoleaccess), peripheral;
  26. end

Un disque virtuel a accès à une ressource console et à une ressource disque. Ses variables permanentes définissent une console virtuelle et un disque. Un processus peut accéder à son disque virtuel au moyen de procédures de lecture et d'écriture. Ces entrées de procédure demandent et libèrent un accès exclusif au disque réel avant et après chaque transfert de bloc. Si le disque réel échoue, le disque virtuel appelle sa console virtuelle pour signaler l'erreur.

L'instruction initiale d'un disque virtuel initialise sa console virtuelle et le disque réel.

Une classe ne peut être initialisée qu'une seule fois. Après l'initialisation, ses paramètres et ses variables privées existent pour toujours. Une procédure de classe ne peut accéder qu'à ses propres variables temporaires et permanentes. Celles-ci ne sont pas accessibles aux autres composantes.

Une classe est une composante système ne pouvant pas être appelé simultanément par plusieurs autres composantes. Ceci est garanti par la règle suivante : une classe doit être déclarée comme variable permanente au sein d'un type système ; une classe peut être transmise comme paramètre permanent à une autre classe (mais pas à un processus ou à un moniteur). Ainsi, une chaîne d'appels de classes imbriqués ne peut être démarrée que par un seul processus ou moniteur. Par conséquent, il n'est pas nécessaire de planifier des appels de classe simultanés au moment de l'exécution, car ils ne peuvent pas se produire.

Entrée/Sortie

Le disque réel est contrôlé par une classe :

  1. type disk=class

avec deux entrées de procédure :

  1. read(pageno, block, error)
  2. write(pageno, block, error)

La classe utilise une procédure standard :

  1. io(block, param, device)

pour transférer un bloc vers ou depuis le périphérique de disque. Le paramètre io est un enregistrement :

  1. var
  2.  param:record
  3.   operation:iooperation;
  4.   result:ioresult;
  5.   pageno:integer
  6.  end

définissant une opération d'entrée/sortie, son résultat et un numéro de page sur le disque. Le processus appelant est retardé jusqu'à ce qu'une opération d'entrée/sortie soit terminée. Une console virtuelle est également définie comme une classe :

  1. type 
  2.  virtualconsole=class(access:resource);
  3.  
  4. var 
  5.  terminal:console;

On peut y accéder par des opérations de lecture et d'écriture similaires les unes aux autres :

  1. procedure entry read(var text:line);begin
  2.  access.request;
  3.  terminal.read(text);
  4.  access.release;
  5. end

La vraie console est contrôlée par une classe similaire à la classe disque.

Ordonnancement multiprocessus

L'accès à la console et au disque est contrôlé par deux moniteurs de type ressource. Pour simplifier la présentation, je supposerai que les processus concurrents sont servis dans l'ordre du premier arrivé, premier servi. (Un algorithme d'ordonnancement de disque bien meilleur est défini dans Hoare (1974). Il peut également être programmé en Concurrent Pascal, mais implique plus de détails que le présent.)

Nous allons définir une file d'attente multiprocessus comme un tableau de files d'attente à processus unique :

  1. type multiqueue=array[0..qlength-1] of queue

où qlength est une limite supérieure du nombre de processus simultanés dans le système.

Un planificateur premier arrivé, premier servi est désormais simple à programmer :

  1. type 
  2.  resource=monitor
  3.  
  4. var 
  5.  free:boolean; 
  6.  q:multiqueue;
  7.  head,tail,length:integer;
  8.  
  9. procedure entry request;
  10. var 
  11.  arrival:integer;
  12. begin
  13.  if free then free:=false
  14.   else
  15.  begin
  16.   arrival:=tail;
  17.   tail:=(tail + 1) mod qlength;
  18.   length:=length + 1;
  19.   delay(q[arrival]);
  20.  end;
  21. end;
  22.  
  23. procedure entry release;
  24. var 
  25.  departure:integer;
  26. begin
  27.  if length=0 then free:=true
  28.   else
  29.  begin
  30.   departure:=head;
  31.   head:=(head + 1) mod qlength;
  32.   length := length - 1;
  33.   continue(q[departure]);
  34.  end;
  35. end;
  36.  
  37. begin "Instructions initial"
  38.  free:=true; length:=0;
  39.  head:=0; tail:=0;
  40. end

Processus initial

Enfin, nous allons rassembler tous ces composantes dans un programme concurrent. Un programme Concurrent Pascal se compose de définitions imbriquées de types de systèmes. Le type de système le plus externe est un processus anonyme, appelé processus initial. Une instance de ce processus est créée lors du chargement du système. Il initialise les autres composantes du système.

Le processus initial définit les types de systèmes et leurs instances. Il exécute des instructions initialisant ces composantes du système. Dans notre exemple, le processus initial peut être esquissé comme suit (en ignorant le problème de la définition des adresses de base et des limites des tampons de disque) :

  1. type
  2.  resource=monitor ... end;
  3.  console=class ... end;
  4.  virtualconsole=class(access:resource); ... end;
  5.  disk=class ... end;
  6.  virtualdisk=class(consoleaccess,diskaccess:resource); ... end;
  7.  diskbuffer =
  8.   monitor(consoleaccess,diskaccess:resource;base,limit:integer); ...
  9.   end;
  10.  inputprocess=process(buffer:diskbuffer); ... end;
  11.  jobprocess=process(input,output:diskbuffer); ... end;
  12.  outputprocess=process(buffer:diskbuffer); ... end;
  13.  
  14. var
  15.  consoleaccess,diskaccess:resource;
  16.  buffer1,buffer2:diskbuffer;
  17.  reader:inputprocess;
  18.  master:jobprocess;
  19.  writer:outputprocess;
  20. begin
  21.  init consoleaccess, diskaccess,
  22.  buffer1(consoleaccess, diskaccess, base1, limit1),
  23.  buffer2(consoleaccess, diskaccess, base2, limit2),
  24.  reader(buffer1),
  25.  master(buffer1, buffer2),
  26.  writer(buffer2);
  27. end.

Lorsque l'exécution d'un processus (comme le processus initial) se termine, ses variables privées continuent d'exister. Cela est nécessaire car ces variables peuvent avoir été transmises comme paramètres permanents à d'autres composants du système.



Dernière mise à jour : Mercredi, le 17 juillet 2024