Architectures matérielles et systèmes d’exploitation

Cours 9 : Processus

1) Une logique matérielle

On entend souvent dire qu'"un ordinateur utilise uniquement des "1" et des "0"". Cette affirmation
mérite d'être précisée.

À la base de la plupart des composants d'un ordinateur, on retrouve le transistor. Ce composant

électronique a été inventé fin 1947 par les Américains John Bardeen, William Shockley et Walter
Brattain. L'invention du transistor a été un immense progrès, mais les premiers ordinateurs sont
antérieurs à cette invention. En effet, ces premiers ordinateurs, par exemple le Colossus qui date de
1943, étaient conçus à base de tubes électroniques (on parle aussi de tubes à vide) qui, bien que
beaucoup plus gros et beaucoup moins fiable que les transistors fonctionnent sur le même principe
que ce dernier.

un transistor un tube électronique

Autre aspect historique qu'il est important de préciser : on ne trouve plus, depuis quelque temps
déjà, de transistors en tant que composant électronique discret (comme le transistor de la photo ci-
dessus). Dans un ordinateur, les transistors sont regroupés au sein de ce que l'on appelle des
circuits intégrés. Dans un circuit intégré, les transistors sont gravés sur des plaques de silicium, les
connexions entre les millions de transistors qui composent un circuit intégré sont, elles aussi,
gravées directement dans le silicium. Les processus mis en jeu lors de ces gravures dépassent
largement le cadre de ce cours, si ce sujet vous intéresse, je vous invite à visionner cette vidéo :
[Link]

un circuit intégré

Un transistor se comporte comme un interrupteur : soit le transistor laisse

passer le courant électrique (interrupteur fermé), soit il ne le laisse pas passer (interrupteur ouvert).
Il n'a donc que deux états. On parle d'un état "haut" et d'un état "bas". On symbolise souvent l'état
"haut" par le chiffre "1" et l'état "bas" par le chiffre "0", On travaille donc uniquement avec 2
chiffres, voilà pourquoi un ordinateur travaille en base 2.

2) Une logique booléenne

1
 A) Les circuits logiques

Le transistor est l'élément de base des circuits logiques. Un circuit logique permet de réaliser une
opération booléenne. Ces opérations booléennes sont directement liées à l'algèbre de Boole
(Georges Boole, mathématicien Britannique 1815-1864). L'étude de l'algèbre de Boole dépasse le
cadre de ce cours, on se contentera de savoir qu'un circuit logique prend en entrée un ou des
signaux électriques (chaque entrée est dans un état "haut" (symbolisé par un "1") ou à un état "bas"
(symbolisé par un "0")) et donne en sortie un ou des signaux électriques (chaque sortie est aussi
dans un état "haut" ou à un état "bas").

Il existe deux catégories de circuit logique :

● les circuits combinatoires (les états en sortie dépendent uniquement des états en entrée)
● les circuits séquentiels (les états en sortie dépendent des états en entrée ainsi que du temps
et des états antérieurs)

Dans la suite nous nous intéresserons principalement aux circuits combinatoires. Ils sont constitués
d'un assemblage de transistors aux propriétés d'entrée et sortie spécifiques.

Le plus simple des circuits combinatoires est la porte "NON" ("NOT" en anglais) qui inverse l'état
en entrée : si l'entrée de la porte est dans un état "bas" alors la sortie sera dans un état "haut" et
vice versa. Si on symbolise l'état "haut" par un "1" et l'état "bas" pour un "0", on peut obtenir ce
que l'on appelle une table de vérité, c’est-à-dire la fonction liant entrées et sorties.

E (Entrée) S (Sortie)
1 0
0 1

Table de vérité de la porte "NON" :

La porte "NON" est symbolisée par le schéma suivant :

E1 E2 S
0 0 0
0 1 1
1 0 1
1 1 1

La porte "OU" a deux entrées (E1 et E2) et une sortie S :

2
Table de vérité de la porte "OU" :

La porte "ET" ("AND") a deux entrées (E1 et E2) et une sortie S :

E1 E2 S
0 0
0 1
1 0
1 1

Table de vérité de la porte "ET" :

Compléter la table

La porte "OU EXCLUSIF" ("XOR") a deux entrées (E1 et E2) et une sortie S :

E1 E2 S
0 0
0 1
1 0
1 1

Table de vérité de la porte "XOR" :

Compléter la table

Exercice 1 : Compléter la table du circuit ci-dessous.

3
Ce circuit équivaut à une porte connue, laquelle? _ _ _ _ _ _ _

Exercice 2 : Dessiner un circuit réalisant la table de vérité de XOR en n'utilisant que les circuits
NOT, OR et AND.

Table XOR Circuit correspondant

B) Effectuer des opérations numériques

Un calcul entre deux nombres revient à faire subir un traitement entre deux entrées pour obtenir
une sortie. Les nombres étant stockés en binaire, il faut donc faire une succession d'opérations
entre les bits de chacun de ces nombres.

Pour simplifier la situation, nous allons considérer des opérations sur deux nombres écrits sur un
seul bit.

En observant les tables de vérité précédentes, identifier laquelle correspond à une multiplication :

La porte logique “ET” ou “AND” qui correspond à une multiplication.

Expliquer pourquoi aucune table de vérité ne permet d'effectuer une addition.

La porte logique “OR” ou “OU” se rapproche le plus d’une addition car la sortie maximum
possible est 1.

En combinant les portes logiques, on obtient des circuits plus complexes. Par exemple en
combinant 2 portes "XOR", 2 portes "AND" et une porte "OR" on obtient un additionneur.
4
Additionneur

Comme son nom l'indique, l'additionneur permet d'additionner 2 bits (E1 et E2) en tenant compte
de la retenue entrante ("Cin" "carry in" en anglais). En sortie on obtient le résultat de l'addition (S)
et la retenue sortante ("Cout").
Lorsqu'on additionne deux bits, on a les situations suivantes :
0+0=0
0+1=1
1+0=1
1+1=2

Dans ce dernier cas, le nombre 2, noté 10 en binaire, se retenue

décompose en 1 (chiffre stocké en retenue) et 0 le reste unitaire.
1 1 10 1 0 10 1 1
Dans une opération sur plusieurs bits, il faut donc imaginer qu'il + 00 011 010
existe déjà une retenue potentielle. Elle est stockée dans Cin. A
l'issue d'une somme entre deux bits, il y aura aussi =11 101 101
potentiellement une retenue, à stocker dans Cout.

Exercice 3 : On suppose qu'à une étape donnée du calcul, les valeurs d'entrée sont E1 = 1, E2 = 0,
Cin = 1.

En identifiant les symboles de chaque transistor, compléter l'additionneur ci-dessous en donnant la

valeur obtenue à l'issue de chaque transistor :

5
Vérifier que les valeurs de S et Cout correspondent bien à l'opération réalisée.

Établir la table de vérité de l'additionneur en complétant le tableau ci-dessous :

E1 E2 Cin Cout S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

En combinant plusieurs fois le type de circuit décrit ci-dessus, on obtient des additionneurs
capables d'additionner des nombres sur X bits.

L'additionneur 8 bits ci-dessous effectue donc comme nous l'addition de droite à gauche.

6
 3) Processeur et langage machine
Une chose est très importante à bien comprendre : à la base nous avons le transistor, une
combinaison de transistor (sous forme de circuit intégré) permet d'obtenir des circuits logiques, la
combinaison de circuits logiques permet d'obtenir des circuits plus complexes (exemple :
l'additionneur), et ainsi de suite...

L’architecture de Von Neumann décompose l’ordinateur en 4 parties distinctes :

● l’unité arithmétique et logique (UAL ou ALU en anglais) ou unité de traitement : son

rôle est d’effectuer les opérations de base ;
● l’unité de contrôle, chargée du « séquençage » des opérations ;
● la mémoire qui contient à la fois les données et le programme qui indiquera à l’unité de
contrôle quels sont les calculs à faire sur ces données. La mémoire se divise entre mémoire
volatile (programmes et données en cours de fonctionnement) et mémoire permanente
(programmes et données de base de la machine) ;
● les dispositifs d’entrée-sortie, qui permettent de communiquer avec le monde extérieur.

Le microprocesseur CPU (Central Processing Unit)

Le microprocesseur est le "cœur" d'un ordinateur : les instructions

sont exécutées au niveau du CPU. Il est schématiquement constitué
de 3 parties :

● les registres permettent de mémoriser de l'information

(donnée ou instruction) au sein même du CPU. Leur nombre
et leur taille sont variables en fonction du type de microprocesseur. Dans la suite on
nommera ces registres R1, R2, R3...
● L'unité arithmétique et logique (UAL ou ALU en anglais) est chargée de l'exécution de
tous les calculs que peut réaliser le microprocesseur. Nous allons retrouver dans cette UAL
des circuits comme l'additionneur (voir plus haut)
● L'unité de commande permet d'exécuter les instructions (les programmes)

En outre, une horloge doit fournir un signal régulier pour cadencer les opérations et synchroniser
le fonctionnement du processeur.

7
Initiation à l'assembleur

Revenons sur ces instructions aussi appelées "instructions machines" exécutées par l'unité de
commande. Comme vous le savez déjà, un ordinateur exécute des programmes qui sont des suites
d'instructions. Le CPU est incapable d'exécuter directement des programmes écrits, par exemple,
en Python. En effet, comme tous les autres constituants d'un ordinateur, le CPU gère uniquement 2
états (toujours symbolisés par un "1" et un "0"), les instructions exécutées au niveau du CPU sont
donc codées en binaire. L'ensemble des instructions exécutables directement par le
microprocesseur constitue ce que l'on appelle le "langage machine".

Une instruction machine est une chaîne binaire composée principalement de 2 parties :

● le champ "code opération" qui indique au processeur le type de traitement à réaliser. Par
exemple le code "00100110" donne l'ordre au CPU d'effectuer une multiplication.
● le champ "opérandes" indique la nature des données sur lesquelles l'opération désignée par
le "code opération" doit être effectuée.

Les instructions machines sont relativement basiques (on parle d'instructions de bas niveau), voici
quelques exemples :

● les instructions arithmétiques (addition, soustraction, multiplication...). Par exemple, on

peut avoir une instruction qui ressemble à "additionne la valeur contenue dans le registre
R1 et le nombre 789 et range le résultat dans le registre R0" (l'adresse mémoire est donnée
en base 10 pour souci de simplicité, n'oubliez pas qu'en interne elle est codée en binaire)
● les instructions de transfert de données qui permettent de transférer une donnée d'un
registre du CPU vers la mémoire vive et vice versa. Par exemple, on peut avoir une
instruction qui ressemble à "prendre la valeur située à l'adresse mémoire 487 et la placer
dans le registre R2" ou encore "prendre la valeur située dans le registre R1 et la placer à
l'adresse mémoire 512"
● les instructions de rupture de séquence : les instructions machines sont situées en mémoire
vive, si, par exemple, l'instruction n°1 est située à l'adresse mémoire 343, l'instruction n°2
sera située à l'adresse mémoire 344, l'instruction n°3 sera située à l'adresse mémoire 345...
Au cours de l'exécution d'un programme, le CPU passe d'une instruction à une autre en
passant d'une adresse mémoire à l'adresse mémoire immédiatement supérieure.
Les instructions de rupture de séquence d'exécution encore appelées instructions de saut ou
de branchement permettent d'interrompre l'ordre initial sous certaines conditions en passant
à une instruction située une adresse mémoire donnée, par exemple, nous pouvons avoir une
instruction qui ressemble à cela : imaginons qu'à l'adresse mémoire 354 nous avons
l'instruction "si la valeur contenue dans le registre R1 est strictement supérieure à 0 alors
exécuter l'instruction située à l'adresse mémoire 4521". Si la valeur contenue dans le
registre R1 est strictement supérieure à 0 alors la prochaine instruction à exécuter est
l'adresse mémoire 4521, dans le contraire, la prochaine instruction à exécuter est à l'adresse
mémoire 355.

Quand on considère l'instruction machine : "additionne le nombre 125 et la valeur située dans le
registre R2 , range le résultat dans le registre R1", nous avons 2 valeurs : le "nombre 125" (qui est
une valeur immédiate, nous sommes dans le cas n°1) et "la valeur située dans le registre R2" (nous
sommes dans le cas n°2)

8
Quand on considère l'instruction machine : "prendre la valeur située dans le registre R1 et la placer
à l'adresse mémoire 512", nous avons 2 valeurs : "à l'adresse mémoire 512" (nous sommes dans le
cas n°3) et "la valeur située dans le registre R1" (nous sommes toujours dans le cas n°2)

Évidemment le microprocesseur est incapable d'interpréter la phrase "additionne le nombre 125 et

la valeur située dans le registre R2 , range le résultat dans le registre R1" tout cela doit être codé
sous forme binaire. Ce langage est évidemment compliqué à interpréter pour un humain. Nous
utiliserons donc des symboles pour décrire ces instructions.

Exemple d'instruction :

En langage naturel : "additionne le nombre 125 et la valeur située dans le registre R2 , range le
résultat dans le registre R1"

En binaire : "11100010100000100001000001111101"

En langage machine : "ADD R1,R2,#125".

Le processeur va interpréter le langage machine à l'aide d'un programme appelé "assembleur" qui
assure le passage de "ADD R1,R2,#125" à "11100010100000100001000001111101".

Il n'est pas question d'apprendre à programmer en assembleur dans ce cours, mais voici tout de
même quelques exemples d'instructions en assembleur :

Assembleur Langage naturel

LDR R1,78 Place la valeur stockée à l'adresse mémoire 78 dans le registre R1
STR R3,125 Place la valeur stockée dans le registre R3 en mémoire vive à l'adresse 125
ADD R1,R0,#128 Additionne le nombre 128 (une valeur immédiate est identifiée grâce au
symbole #) et la valeur stockée dans le registre R0, place le résultat dans le
registre R1
ADD R0,R1,R2 Additionne la valeur stockée dans le registre R1 et la valeur stockée dans le
registre R2, place le résultat dans le registre R0
SUB R1,R0,#128 Soustrait le nombre 128 de la valeur stockée dans le registre R0, place le
résultat dans le registre R1
MOV R1, #23 Place le nombre 23 dans le registre R1
B 45 Nous avons une structure de rupture de séquence, la prochaine instruction à
exécuter se situe en mémoire vive à l'adresse 45
CMP R0, #23 Compare la valeur stockée dans le registre R0 et le nombre 23. Cette
instruction CMP doit précéder une instruction de branchement conditionnel
BEQ, BNE, BGT, BLT (voir ci-dessous)
CMP R0, #23 La prochaine instruction à exécuter se situe à l'adresse mémoire 78 si la
BEQ 78
valeur stockée dans le registre R0 est égale à 23

9
 CMP R0, #23 La prochaine instruction à exécuter se situe à l'adresse mémoire 78 si la
BNE 78
valeur stockée dans le registre R0 n'est pas égale à 23
CMP R0, #23 La prochaine instruction à exécuter se situe à l'adresse mémoire 78 si la
BGT 78
valeur stockée dans le registre R0 est plus grand que 23
CMP R0, #23 La prochaine instruction à exécuter se situe à l'adresse mémoire 78 si la
BLT 78
valeur stockée dans le registre R0 est plus petit que 23
HALT Arrête l'exécution du programme

Un exemple de séquence d'instructions

N° Assembleur Langage naturel

mémoire
1 LDR R0,42 Place la valeur stockée à l'adresse mémoire 42 dans le registre R0
2 LDR R1,17 Place la valeur stockée à l'adresse mémoire 17 dans le registre R1
3 ADD R2,R0,R1 Additionne les nombres stockés dans les registres R0 et R1, place
le résultat dans le registre R2
4 STR R3,42 Place la valeur stockée dans le registre R3 en mémoire vive à
l'adresse 42

Si la variable x est stockée à l'adresse mémoire 42, et la variable y est stockée à l'adresse mémoire
17 alors la série d'instructions ci-dessous revient à faire la commande python : x = x +y.

Exercice 4
La séquence suivante inclue une instruction de branchement conditionnel. Cela signifie que les
instructions ne se lisent pas nécessairement dans l'ordre croissant des numéros de mémoire mais
peut faire des sauts si l'instruction indique un emplacement mémoire de l'instruction suivante.

N° Assembleur Langage naturel

mémoire

1 LDR R0,18

2 CMP R0, #10

3 BGT 7

4 ADD R1,R0,#1

5 STR R1,18

6 HALT
10
 7 SUB R1,R0,#1

8 STR R1,18

9 HALT

1) Compléter le tableau en traduisant les instructions en langage naturel.

2) Si la mémoire 18 contient le nombre 12 au début de la séquence, que contiendra-t-elle à la fin
de la séquence?
3) Si la mémoire 18 contient le nombre 7 au début de la séquence, que contiendra-t-elle à la fin
de la séquence?
4) Si on note x la variable stockée dans la mémoire 18, traduire en python la séquence
d'instruction proposée.

11
 4) Gestion de processus
On appelle processus un programme en cours d'exécution. Attention, il ne faut pas confondre le
code source du programme et un processus, qui lui, correspond à l'exécution de ce programme par
un ordinateur. Un processus est donc un programme en langage machine.
Lorsqu'un programme est exécuté plusieurs fois, il crée à chaque fois un nouveau processus.

Chaque processus possède un identifiant appelé PID (Process Identification), ce PID est un
nombre. Le premier processus créé au démarrage du système à pour PID 0, le second 1, le
troisième 2... Le système d'exploitation utilise un compteur qui est incrémenté de 1 à chaque
création de processus, le système utilise ce compteur pour attribuer les PID aux processus.

Tous les systèmes d'exploitation "modernes" (Linux, Windows, macOS, Android, iOS...) sont
capables de gérer l'exécution de plusieurs processus en même temps. Mais pour être précis, cela
n'est pas en véritable "en même temps", mais plutôt un "chacun son tour". Pour gérer ce "chacun
son tour", les systèmes d'exploitation attribuent des "états" au processus.

Voici les différents états :

● Lorsqu'un processus est créé, il se trouve alors dans l'état "prêt". Il attend de pouvoir
accéder au processeur.
● Lorsqu'un processus est en train de s'exécuter (qu'il utilise le microprocesseur), on dit que
le processus est dans l'état "élu".
● Un processus qui se trouve dans l'état élu peut demander à accéder à une ressource pas
forcément disponible instantanément (par exemple lire une donnée sur le disque dur). Le
processus ne peut pas poursuivre son exécution tant qu'il n'a pas obtenu cette ressource. En
attendant de recevoir cette ressource, il passe de l'état "élu" à l'état "bloqué".
● Lorsque le processus finit par obtenir la ressource attendue, celui-ci peut potentiellement
reprendre son exécution. Mais le processeur ne peut "s'occuper" que d'un seul processus à
la fois donc un seul processus peut se trouver dans un état "élu".
Quand un processus passe d'un état "élu" à un état "bloqué", un autre processus peut alors
"prendre sa place" et passer dans l'état "élu". Le processus qui vient de recevoir la
ressource attendue ne va donc pas forcément pouvoir reprendre son exécution tout de suite,
car pendant qu'il était dans un état "bloqué" un autre processus a "pris sa place".
Un processus qui quitte l'état bloqué ne repasse pas forcément à l'état "élu", il peut, en
attendant que la place se libère passer dans l'état "prêt" (sous-entendu "j'ai obtenu ce que
j'attendais, je suis prêt à reprendre mon exécution dès que la "place sera libérée").

12
Le passage de l'état "prêt" vers l'état "élu" constitue l'opération "d'élection". Le passage de l'état
"élu" vers l'état "bloqué" est l'opération de "blocage". Pour se terminer, un processus doit
obligatoirement se trouver dans l'état "élu".

On peut résumer tout

cela avec le diagramme
suivant :

Il est vraiment
important de bien comprendre que le "chef d'orchestre" qui attribue aux processus leur état "élu",
"bloqué" ou "prêt" est le système d'exploitation. On dit que le système gère l'ordonnancement des
processus (tel processus sera prioritaire sur tel autre...).

Pour choisir les processus à relancer si plusieurs sont dans l'état "prêt", le système d'exploitation
utilise un système de priorités associées à chaque processus.

Lorsqu'un processus P2 passe dans l'état prêt, si un processus P1 est en cours d'exécution mais est
moins prioritaire que P2, alors le système décidera de commuter P1 et P2.

P1 passera dans l'état _ _ _ _ _ _ et P2 dans l'état _ _ _ _ _ _

Exemple
Un processeur choisit à chaque cycle d’exécution le processus qui doit être exécuté. Le tableau ci-
dessous donne pour trois processus P1, P2, P3 :
- la durée d’exécution (en nombre de cycles),
- l’instant d’arrivée sur le processeur (exprimé en nombre de cycles à partir de 0),
- le numéro de priorité.
Le numéro de priorité est d’autant plus petit que la priorité est grande. On suppose qu’à chaque
instant, c’est le processus qui a le plus petit numéro de priorité qui est exécuté, ce qui peut
provoquer la suspension d’un autre processus, lequel reprendra lorsqu’il sera le plus prioritaire.

Processus Durée d’exécution Instant d’arrivée Numéro de priorité

P1 3 3 1
P2 3 2 2
P3 4 0 3

Compléter le tableau ci-dessous avec le processus exécuté à chaque cycle.

P3

13
Gestion de l'accès aux ressources
Une ressource ne peut être utilisée simultanément par deux processus.
Si une ressource est disponible, le processus peut l'acquérir, sinon il doit attendre.
Une fois utilisé, la ressource doit être libérée pour devenir accessible à un autre processus.
De plus le processus ne sera pas débloqué (retour à l'état prêt) tant qu'il utilise une ressource.

Pour acquérir ou libérer une ressource, un processus doit obligatoirement être dans un état "élu".

14
Exemple
On reprend l'exemple précédent.
On suppose maintenant que les trois processus précédents s’exécutent et utilisent une ou plusieurs
ressources parmi R1, R2 et R3. Ces ressources sont libres au début de l'exécution
Dès qu'un processus effectue une action vers ces ressources, il passe en état bloqué.

Compléter le tableau suivant en précisant les état des processus avant et après exécution de la
commande, ainsi que l'état L (libre) ou O (occupée) de chaque ressource.

Processus élu Etat après exécution

exécution P1 P2 P3 R1 R2 R3

Etat initial prêt prêt prêt L L L

P1 acquiert R1 bloqué prêt prêt O L L

P2 acquiert R2

P3 attend R1

P1 libère R1

P2 libère R2

P3 acquiert R1

Un problème d'interblocage (deadlock)

Scénario

P1 acquiert R1

P2 acquiert R2

P1 attend R2

P2 attend R1

On suppose ici qu'il n'y a que deux processus actifs P1 et P2.

Expliquer le problème rencontré dans le scénario ci-contre.

_____________________________

_____________________________

15
_____________________________

Il existe plusieurs solutions permettant soit de mettre fin à un interblocage (suppression des
processus en cause) ou d'éviter les interblocage (détection, guérison, prévention), mais ces
solutions ne seront pas étudiées ici.

16