Les processus

Hicham Bensaid
Les processus

 Concept de processus
 Ordonnancement des processus
 Opérations sur les processus
 Communication inter-processus (IPC)
 Exemples de système IPC
 Communication dans les systèmes client-serveur
Objectifs

 Introduire la notion de processus : un programme en

exécution qui forme la base de tous les calculs
 Décrire les différentes caractéristiques des processus,
en particulier l'ordonnancement, la création, la
terminaison et la communication
 Explorer la communication inter processus en utilisant
la mémoire partagée et le passage de messages
 Décrire la communication dans les systèmes client-
serveur
Concept de processus

 Un OS exécute plusieurs types de programmes

 Système batch : jobs
 Systèmes à temps partagé : programmes utilisateur ou tâches
 Les livres utilisent les termes job et processus de manière
interchangeable
 Processus : un programme en exécution ; l'exécution progresse
de manière séquentielle
 Plusieurs parties
 Code du programme : text section
 Activité courante : PC, registres
 Pile pour les données temporaires
 Paramètres de fonction, adresses de retour, variables locales
 Data section : variables globales
 Tas (Heap) : mémoire allouée dynamiquement durant l'exécution
Concept de processus

 Un programme est une entité passive stockée sur

disque (fichier exécutable), le processus est actif
 Le programme devient processus quand le fichier exécutable
est chargé en mémoire
 Exécution du programme démarre via clics de la souris
(GUI), commande, ...
 Un programme peut être plusieurs processus
 Plusieurs utilisateurs exécutant le même programe
Processus en mémoire
État d'un processus

 Durant son exécution, un processus change d'état :

 Nouveau : vient d'être créé
 En exécution : les instructions sont exécutées
 En attente : le processus attend un évènement
 Prêt : le processus attend d'être affecté à un processus
 Terminé : le processus a terminé l'exécution
Diagramme des états d'un processus
Bloc de contrôle d'un processus (PCB)

 Information associée à chaque processus

 État du processus
 PC
 Registres
 Informations d'ordonnancement (priorités,
pointeurs sur les files de priorité)
 Informations de gestion de la mémoire
(alloué au processus)
 Infos de comptabilisation : usage CPU,
temps écoulé depuis le début, limites
temporelles
 Informations sur le statut E/S : périphs.
Alloués, liste des fichiers ouverts
Le CPU bascule entre les processus
Threads (processus légers)

 Jusqu'à présent : un processus = 1 seul thread

d'exécution
 Considérons plusieurs PC par processus
 Plusieurs instructions peuvent s'exécuter en « même temps »
 Stockage pour les détails des threads, plusieurs PC dans
le PCB
 On verra plus tard
Représentation d'un processus sous Linux

 Représenté par la structure C task_struct

pid t_pid; /* process identifier */
long state; /* state of the process */
unsigned int time_slice /* scheduling information */
struct task_struct *parent; /* this process’s parent */
struct list_head children; /* this process’s children */
struct files_struct *files; /* list of open files */
struct mm_struct *mm; /* address space of this process */
Ordonnancement des processus

 Maximise l'utilisation du CPU, bascule rapidement les

processus dans le CPU pour le partage de temps
 L'ordonnanceur (de processus) choisit parmi les
processus disponibles le prochain à occuper le CPU
 Maintient des files d'ordonnancement pour les processus
 File des jobs : ensemble de tous les processus dans le système
 File des prêts : ensemble des processus résidant en mémoire
(principale), prêts et en attente d'exécution
 Files de périphériques : ensemble des processus attendant un
périphérique d'E/S
 Les processus migrent entre les différentes files
File des prêts et différentes files d'E/S
Représentation de l'ordonnancement des
processus

 Diagramme de file représentant les files, les ressources

et les flux
Les ordonnanceurs

 Ordonnanceur cours-terme (ou ordonnanceur CPU) : choisit quel

processus doit être prochainement exécuté et lui alloue le CPU
 Parfois c'est le seul ordonnanceur du système
 Invoqué très fréquemment (ms) => doit être rapide
 Ordonnanceur long-terme (ou ordonnanceur des jobs) : choisit
quel processus doit être ramené à la file des prêts
 Invoqué moins fréquemment (s, mn) => lent
 Contrôle le niveau de multiprogrammation
 Les processus peuvent être décrits ou bien :
 Processus liés aux E/S : passent plus de temps en E/S qu'en calculs, plusieurs
bursts courts de CPU
 Processus liés au CPU : passent plus de temps à calculer, peu de bursts longs
de CPU
 L'ordonnanceur long-terme fait son possible pour un bon mix de
processus
Ajout d'un ordonannceur moyen-terme

 Un ordonnanceur moyen-terme peut être

ajouté si le niveau de multiprogrammation doit
décroitre
 Enlève un processus de la mémoire, le stocke sur
disque, le ramène du disque pour continuer
l'exécution : le swapping
Changement de contexte

 Quand le CPU bascule vers un autre processus, le

système doit sauvegarder l'état de l'ancien processus
et charger l'état sauvegardé du nouveau processus via
un changement de contexte
 Contexte d'un processus représenté dans le PCB
 Le temps passé dans un CC est un temps inutile (pour
l'utilisateur)
 Plus l'OS et le PCB sont complexe plus le temps du CC est
grand
 Le temps dépend du support matériel
 Certains matériels fournissent plusieurs ensembles de registres
par CPU => plusieurs contextes chargés à la fois
Opérations sur les processus

 Le système doit fournir des mécanismes pour :

 Créer un processus
 Terminer un processus
 Et ainsi de suite comme détaillé dans la suite
Création d'un processus

 Le processus père crée des processus fils, qui à leur tour

créent d'autres processus, etc
 Arbre de processus
 Processus identifiés et gérés via un pid (process
identifier)
 Options pour le partage de ressources
 Le père et ses fils partagent toutes les ressources
 Les fils partagent un sous-ensemble des ressources de leur père
 Père et fils ne partagent aucune ressource
 Options d'exécution
 Le père et les fils s'exécutent en concurrence
 Le père attend que ses fils terminent
Un arbre de processus sous Linux
init
pid = 1

login kthreadd sshd

pid = 8415 pid = 2 pid = 3028

bash khelper pdflush sshd

pid = 8416 pid = 6 pid = 200 pid = 3610

emacs tcsch
ps
pid = 9204 pid = 4005
pid = 9298
Création d'un processus

 Espace d'adresses
 Le fils est une copie du père
 Le fils a un programme chargé dedans
 Exemples Unix
 fork() appel système pour créer un nouveau processus
 exec() appel système utilisé après un fork() pour remplacer l'espace
mémoire du fils avec un nouveau programme
Programme C pour forker des processus
séparés
Créer un processus séparé par l'API
Windows
Terminaison d'un processus

 Le processus exécute sa dernière instruction puis

demande à l'OS de le supprimer en utilisant l'AS exit()
 Retourne le statut du fils au père (via wait())
 Les ressources du processus sont désalloués par l'OS
 Le père peut terminer l'exécution de ses fils en utilisant
l'AS abort(). Ceci car
 Le fils a dépassé les ressources allouées
 La tâche assignée au fils n'est plus nécessaire
 Le père veut terminer et l'OS ne permet pas à un fils de
continuer si son père termine
Terminaison de processus

 Certains OS ne permettent pas à un fils d'exister si son père

est terminé. Si un processus termine alors tous ses fils
doivent se terminer
 Terminaison en cascade
 La terminaison est initiée par l'OS
 Le père peut attendre la terminaison d'un fils avec l'AS
wait(). L'appel retourne une info de statut et le pid du fils
terminé
pid = wait($status) ;
 Si aucun père en attente (n'a pas invoqué wait()) le
processus est un zombie
 Si le père termine sans wait, le processus est orphelin
Communication interprocessus

 Les processus dans un système peuvent être indépendant ou

coopérants
 Les processus coopérant peuvent affecter ou être affecter par
d'autres processus, en particulier les données partagées
 Raisons pour les processus coopérants :
 Partage d'information
 Accélération des calculs
 Modularité
 Les processus coopérants ont besoin d'IPC (interprocess
communication)
 Deux modèles d'IPC
 Mémoire partagée
 Passage de messages
Modèles de communication

(a) Passage de message. (b) Mémoire partagée

Problème de producteur consommateur

 Paradigme pour les processus coopérants : le

producteur produit l'information consommée par le
consommateur
 Buffer sans limites
 Buffer limité
Buffer limité : solution avec mémoire
partagée

 Données partagées
#define BUFFER_SIZE 10
typedef struct {
. . .
} item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

 La solution est correcte, mais peut utiliser seulement

BUFFER_SIZE – 1 éléments
Buffer limité : le producteur

item next_produced;
while (true) {
/* produce an item in next produced */
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
}
Buffer limité : le consommateur

item next_consumed;
while (true) {
while (in == out)
; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;

/* consume the item in next consumed */

}
IPC : mémoire partagée

 Une zone de la mémoire partagée entre les processus

qui veulent communiquer
 La communication est sous le contrôle des processus
utilisateurs et non pas l'OS
 Le plus grand problème est de fournir des mécanismes
qui permettent aux processus de synchroniser leurs
actions quand ils accèdent à la mémoire partagée
 La synchronisation sera discutée plus tard
IPC : passage de messages

 Mécanisme pour permettre aux processus de

communiquer et synchroniser leurs actions
 Système de massages : les processus communiquent
entre eux sans utiliser des variables partagées
 La facilité IPC fournit 2 opérations
 send(message)
 receive(message)
 La taille du message est soit fixe soit variable
Passage de message (suite)

 Si deux processus P et Q veulent communiquer, ils ont

besoin de :
 Établir un lien de communication entre eux
 Échanger des messages via send/receive
 Questions sur l'implémentation :
 Comment les liens sont-ils établis ?
 Un lien peut-il être associé à plus de 2 processus ?
 Combien de liens peut-on avoir entre chaque paire de processus
communicants ?
 Quelle est la capacité d'un lien ?
 Est-ce que la taille d'un message sur un lien est fixe ou variable ?
 Un lien est-il unidirectionnel ou bi-directionnel ?
Passage de messages (suite)

 Implémentation des liens de communication

 Physique :
 Mémoire partagée
 Bus matériel
 Réseau
 Logique :
 Direct ou indirect
 Synchrone ou asynchrone
 Mise en tampon explicite ou automatique
Exemple de passage de massage sous Posix:
création et envoi
#include <sys/types.h> if ((msqid = msgget(key, msgflg )) < 0) {
#include <sys/ipc.h> perror("msgget");
#include <sys/msg.h> exit(1);
#include <stdio.h> }
#include <string.h> else
#define MSGSZ 128 (void) fprintf(stderr,"msgget: msgget succeeded: msqid = %d\n", msqid);
/* Declare the message structure. */ /*We'll send message type 1 */
typedef struct msgbuf { sbuf.mtype = 1;
long mtype; (void) fprintf(stderr,"msgget: msgget succeeded: msqid = %d\n", msqid);
char mtext[MSGSZ]; (void) strcpy(sbuf.mtext, "Did you get this?");
} message_buf; (void) fprintf(stderr,"msgget: msgget succeeded: msqid = %d\n", msqid);
main() { buf_length = strlen(sbuf.mtext) + 1 ;
int msqid; /*Send a message. */
int msgflg = IPC_CREAT | 0666; if (msgsnd(msqid, &sbuf, buf_length, IPC_NOWAIT) < 0) {
key_t key; printf ("%d, %d, %s, %d\n", msqid, sbuf.mtype, sbuf.mtext, buf_length);
message_buf sbuf; perror("msgsnd");
size_t buf_length; exit(1);
/*Get the message queue id for the "name" 1234, which was created by }
the server. */
else
key = 1234;
printf("Message: \"%s\" Sent\n", sbuf.mtext);
(void) fprintf(stderr, "\nmsgget: Calling msgget(%#lx,\
exit(0);
%#o)\n« , key, msgflg);
}
Exemple de passage de massage sous Posix:
réception
#include <sys/types.h> /*
#include <sys/ipc.h> * Receive an answer of message type 1.
*/
#include <sys/msg.h>
if (msgrcv(msqid, &rbuf, MSGSZ, 1, 0) < 0) {
#include <stdio.h> perror("msgrcv");
#define MSGSZ 128 exit(1);
/* Declare the message structure. */
}
typedef struct msgbuf { /*
long mtype; * Print the answer.
char mtext[MSGSZ]; */
printf("%s\n", rbuf.mtext);
} message_buf;
exit(0);
main() { }
int msqid;
key_t key;
message_buf rbuf;
/*Get the message queue id for the "name" 1234, which was created
by the server. */
key = 1234;
if ((msqid = msgget(key, 0666)) < 0) {
perror("msgget");
exit(1);
}
Communication directe

 Les processus doivent s'appeler explicitement

 send(P,message) : envoie un message à P
 receive(Q,message) : reçoit un message de Q
 Propriétés d'un lien de communication
 Les liens sont établis automatiquement
 Un lien est associé avec exactement une paire de processus
communicants
 Entre chaque paire il existe exactement un lien
 Le lien peut être unidirectionnel mais il est souvent bi-
directionnel
Communication indirecte

 Les messages sont envoyés et reçus depuis des boîtes

aux lettres (appelés aussi des ports)
 Chaque boite aux lettres a un unique id
 Des processus ne peuvent communiquer que s'il partagent
une boite aux lettres
 Propriétés du lien de communication
 Établi seulement si les processus partagent une boite aux
lettres
 Un lien peut être associé à plusieurs processus
 Chaque paire de processus peut partager plusieurs liens de
communications
 Un lien peut être unidirectionnel ou bi-directionnel
Communication indirecte

 Opérations
 Créer une nouvelle boite au lettres (port)
 Envoyer et recevoir les messages à travers la boite aux lettres
 Détruire la boite aux lettres
 Les primitives sont définies comme :
 send(A,message) : envoyer un message à la boite aux lettres A
 receive(A,message) : recevoir un message depuis la boite aux
lettres A
Communication indirecte

 Partage de boite aux lettres

 P1, P2 et P3 partagent la BL A
 P1 envoie, P2 et P3 recoivent
 Qui reçoit le message ?
 Solutions
 Autoriser un lien à être associé avec au plus 2 processus
 Autoriser un seul processus à un moment donné à faire une
opération de réception
 Autoriser le système à choisir de manière arbitraire le
récepteur. L'envoyeur est notifié de l'identité du récepteur
La synchronisation

 Le passage de message peut être bloquant ou non bloquant

 Un passage bloquant est considéré synchrone
 Envoi bloquant : l'envoyeur est bloqué jusqu'à ce que le message soit
reçu
 Réception bloquante : le récepteur est bloqué jusqu'à ce qu'un
message soit disponible
 Un passage non bloquant est considéré asynchrone
 Envoi non bloquant : l'envoyeur envoie son message et continue
 Réception non bloquante : le récepteur reçoit :
 Un message valide, ou
 Un message nul
 Plusieurs combinaisons possibles
 Si l'envoi et la réception sont tous les deux bloquants, on a un rendez-
vous
La synchronisation (suite)

 Le problème du producteur/consommateur devient

trivial
message next_produced;
while (true) {
/* produce an item in next produced */
send(next_produced);
}

message next_consumed;
while (true) {
receive(next_consumed);
/* consume the item in next consumed */
}
Mise en tampon

 File de messages attachée au lien

 Implémentée d'une manière parmi 3 :
 Capacité zéro : aucun message n'est enfilé sur le lien.
L'envoyeur doit attendre le récepteur (rendez-vous)
 Capacité limitée : file de taille finie (n messages). L'envoyeur
doit attendre si le lien est plein
 Capacité infinie : taille de la file infinie. L'envoyeur n'attend
jamais
Exemples de systèmes IPC : POSIX

 Mémoire partagée POSIX

 Le processus crée d'abord un segment de mémoire partagée
shm_fd = shm_open(name, O CREAT | O RDWR, 0666);
 Utilisée également pour ouvrir un segment existant pour le
partager
 Établit la taille de l'objet
ftruncate(shm fd, 4096);
 Le processus peut maintenant écrire dans la mémoire
partagée
sprintf(shared memory, "Writing to shared memory");
Producteur IPC POSIX
Consommateur IPC POSIX
Communications dans les systèmes
Client/Serveur

 Sockets
 RPC
 Pipes
Sockets

 Une socket est une extrémité d'une communication

 Concaténation de l'adresse IP et du port
 Exemple : la socket 161.25.19.8:1625
 Communication entre une paire de sockets
 Tous les ports sous 1024 sont bien connus et utilisés
pour des services standards
Communication avec des sockets
RPC : Remote Procedure Call

 RPC abstrait les appels de procédures entre des

processus dans des systèmes en réseau
 Utilise des ports pour identifier les services
 Stubs : proxy côté client pour l'appel réel sur le serveur
 Le stub localise le serveur et sérialise les paramètres
 Le skeleton (ou stub côté serveur) reçoit le message,
déséréalise les paramètres et effectue la procédure sur
le serveur
Exécution du RPC
Les pipes

 Agit comme un tuyau qui permet à deux processus de

communiquer
 Problèmes :
 Communication unidirectionnelle ou bi-directionnelle ?
 Half ou full duplex ?
 Est-ce qu'il faut une relation (i.e. Père-fils) entre les processus
communicants ?
 Peut-on utiliser des pipes sur le réseau
 Pipes ordinaires : ne peuvent pas être accédés à l'extérieur du
processus qui les a crées. Typiquement, un processus père crée un
pipe et l'utilise pour communiquer avec un processus fils qu'il a
créé
 Pipes nommés : peuvent être accédés sans relation père-fils
Pipes ordinaires

 Les pipes ordinaires permettent la communication dans le style standard

producteur / consommateur
 Le producteur écrit dans une extrémité (l'extrémité d'écriture dans le pipe)
 Le consommateur lit de l'autre extrémité (l'extrémité de lecture du pipe)
 Les pipes ordinaires sont unidirectionnels
 Nécessitent une relation père-fils entre les processus communicants
Exemple Pipes POSIX
#include <unistd.h>
#include <stdio.h>
Int main() {
int pdes[2];
pipe(pdes);
if ( fork() == 0 ) { /* child */
close(pdes[1]);
read( pdes[0]); /* read from parent */
.....
}
else {
close(pdes[0]);
write( pdes[1]); /* write to child */
.....
}
}
Pipes nommés

 Plus puissantes que les pipes ordinaires

 Communication bi-directionnelle
 Pas de relation père-fils nécessaire entre les processus
communicants
 Plusieurs processus peuvent utiliser la pipe nommée
pour communiquer
 Disponibles sous Linux et Windows