Q1. Que permet de garantir un système RTOS ?

Un RTOS, ou Real Time Operating System, est un système d’exploitation conçu pour respecter des contraintes temporelles déterministes. La propriété essentielle n’est pas simplement d’être rapide, mais de pouvoir garantir qu’une tâche sera exécutée dans un délai maximal connu.

Dans un système temps réel dur, une échéance manquée peut être considérée comme une défaillance du système. Par exemple, dans un système de contrôle industriel, une commande devant être exécutée avant une échéance précise doit effectivement l’être dans cette limite.

Le RTOS fournit donc notamment un ordonnancement adapté aux contraintes temporelles, des mécanismes de synchronisation déterministes et des temps de réponse bornés autant que possible. La priorité est donnée à la prédictibilité du comportement plutôt qu’à la maximisation du débit moyen.

Il faut distinguer cette propriété d’un système rapide d’un système déterministe. Un ordinateur généraliste peut exécuter une tâche très rapidement en moyenne sans être capable de garantir qu’elle terminera toujours avant une échéance donnée.

Q2. Que garantit un OS moderne ?

Un système d’exploitation moderne fournit une couche d’abstraction entre les programmes et le matériel. Il permet à plusieurs programmes de partager les ressources matérielles tout en limitant leurs interactions.

Du point de vue de la sécurité, l’OS fournit notamment une séparation entre les processus, des mécanismes de droits d’accès, une séparation entre espace utilisateur et espace noyau ainsi que des mécanismes de protection de la mémoire. Un programme utilisateur ne doit normalement pas pouvoir modifier directement la mémoire d’un autre processus ou accéder arbitrairement aux périphériques.

Du point de vue de la gestion des utilisateurs, l’OS associe les processus à des identités et à des droits. Les fichiers, périphériques et autres ressources peuvent ainsi être protégés par des permissions.

Du point de vue de la mémoire, l’OS fournit généralement une mémoire virtuelle. Chaque processus possède l’illusion de disposer de son propre espace d’adressage. Les adresses virtuelles sont traduites en adresses physiques par le matériel de gestion mémoire, sous le contrôle du système d’exploitation.

Du point de vue du processeur, l’OS réalise l’ordonnancement des processus et des threads. Il décide notamment quel thread doit être exécuté et pendant combien de temps.

Enfin, l’OS cherche à assurer l’isolationde ces differents points.

Q3. Variable, langage et matériel

Une variable est avant tout une abstraction définie par le langage de programmation. Par exemple, en C, la déclaration

float x;

indique au compilateur qu’il doit manipuler une donnée de type float. Le langage définit les opérations qui peuvent être effectuées sur cette donnée et le compilateur choisit ensuite une représentation et des instructions adaptées à l’architecture cible.

Au niveau matériel, cette variable correspond finalement à une suite de bits stockée quelque part. Elle peut être placée dans un registre du processeur, dans une zone de pile, dans le tas ou être entièrement éliminée par le compilateur si sa valeur n’a pas besoin d’être matérialisée.

Il faut donc distinguer trois niveaux. Le premier est le niveau sémantique du langage, qui définit la notion de variable et de type. Le deuxième est le niveau du compilateur ou de la JVM, qui choisit comment représenter et manipuler cette donnée. Le troisième est le niveau matériel, qui utilise des registres, des instructions et des emplacements mémoire réels.

Les instructions assembleur illustrent directement cette différence. Une instruction add peut correspondre à une addition entière, alors que addss désigne une addition scalaire de nombres flottants simple précision dans les extensions SIMD x86. Une instruction addb désigne quant à elle une addition portant sur une donnée de 8 bits.

Les instructions de déplacement illustrent également cette distinction. mov est une instruction générale de transfert de données sur x86. movss est spécialisée dans le déplacement de valeurs flottantes simple précision.

En assembleur, le programmeur peut manipuler explicitement les registres, les adresses mémoire et les instructions particulières du processeur. En C, certaines possibilités bas niveau existent également, par exemple avec les pointeurs, l’arithmétique d’adresse, les opérations bit à bit, les fonctions intrinsèques ou l’assembleur inline selon le compilateur.

Java fournit une abstraction beaucoup plus forte. Le programme Java ne peut normalement pas demander directement à la JVM d’écrire une valeur arbitraire dans un registre xmm, ni manipuler directement une adresse physique. La JVM et le compilateur JIT décident eux-mêmes de la représentation matérielle appropriée. Il est donc impossible de faire des optimisations cibles.

Q4. Tableaux Java

On considère :

float[] b = new float[50];
byte[] a = new byte[50];

Un float Java occupe 32 bits, soit 4 octets. Les 50 éléments de b nécessitent donc :

50 × 4 = 200 octets

pour les données du tableau.

Un byte Java occupe 8 bits, soit 1 octet. Les 50 éléments de a nécessitent donc :

50 × 1 = 50 octets

pour les données.

Ces valeurs ne correspondent cependant pas nécessairement à la taille réelle des objets en mémoire. Un tableau Java est un objet. Il possède donc un en-tête contenant notamment des informations nécessaires à la JVM, auxquelles peuvent s’ajouter des contraintes d’alignement. La taille exacte dépend de la JVM, de l’architecture et de sa configuration, a priori ces donees sembles d’etre 8 octets de metadata et probablement 8 octet concernant length.

Concernant leur emplacement, rien ne garantit que a et b soient contigus. Chaque tableau constitue un objet indépendant. La JVM peut les placer à des endroits différents du tas.

Avec un garbage collector compactant, l’adresse physique ou virtuelle utilisée par un objet peut changer au cours de son existence. Les références Java restent valides parce que la JVM met à jour ou gère les références concernées.

En supposant que le premier élément du tableau corresponde à l’offset 0 relativement aux données du tableau, l’offset de b[10] est :

10 × sizeof(float) = 10 × 4 = 40 octets

L’offset de a[16] est :

16 × sizeof(byte) = 16 octets

Il faut cependant distinguer cet offset logique à l’intérieur des données du tableau de l’adresse réelle de l’objet en mémoire. En Java il faudrais donc, peut-etre (cela depend de l’implementation) decaller l’offset de la taille des metadatas.

En C, pour :

float b[50];
char a[50];

les tableaux sont des zones mémoire contenant directement leurs éléments. Si ces tableaux sont des variables locales, ils sont généralement placés dans la pile, tandis que des tableaux alloués dynamiquement sont placés dans le tas.

Le C donne également au programmeur un contrôle beaucoup plus direct de l’organisation mémoire. En revanche, le langage Java impose une abstraction des références et de la gestion mémoire.

Q5. Structures, classes et alignement

En C :

struct Pixel {
    int r;
    int g;
    int b;
};

Si int occupe 4 octets et que son alignement est de 4 octets, les trois champs occupent 12 octets. Aucun padding supplémentaire n’est nécessaire entre eux.

On peut donc avoir :

offset 0    : r
offset 4    : g
offset 8    : b

La taille de la structure est alors 12 octets.

La structure donne une interprétation aux 12 octets. Les quatre premiers octets représentent r, les quatre suivants représentent g et les quatre derniers représentent b.

Cette représentation constitue un contrat entre le programme et la mémoire. La mémoire elle-même ne sait pas qu’une zone représente un pixel. Ce sont le programme et son type Pixel qui attribuent cette signification aux bits.

La situation est différente en Java :

class Pixel {
    int r;
    int g;
    int b;
}

Il ne faut pas conclure que l’objet Java fait exactement 12 octets. Il s’agit d’un objet géré par la JVM. Il possède un en-tête d’objet, les champs sont organisés selon les règles de la JVM et de son implémentation, et l’objet peut être soumis aux contraintes d’alignement.

Une référence Java vers cet objet ne contient pas nécessairement directement l’objet lui-même. Elle permet à la JVM de retrouver l’objet.

Alignement

Considérons :

struct Exemple {
    char c;
    int a;
};

Avec un char d’un octet et un int de quatre octets aligné sur une frontière de quatre octets, c est placé à l’offset 0.

Les trois octets suivants sont du padding :

offset :  0    1    2    3    4    5    6    7
          +----+----+----+----+----+----+----+----+
          | c  |pad |pad |pad |       a       |
          +----+----+----+----+----+----+----+----+

a commence donc à l’offset 4.

La taille totale est généralement de 8 octets. Le padding existe pour respecter les contraintes d’alignement du int.

L’indice important est que la taille d’une structure n’est pas nécessairement égale à la somme naïve des tailles de ses champs. Le compilateur peut introduire du padding entre les champs et à la fin de la structure.

En Java, le même raisonnement ne permet pas de déterminer précisément la taille d’un objet. La JVM peut réorganiser certains champs, utiliser différentes tailles de références et ajouter un en-tête d’objet. La représentation exacte dépend donc de l’implémentation.

Q6. Tableau 3D vers tableau 1D

On considère une image de largeur 50, hauteur 100 et 4 composantes par pixel.

On choisit l’ordre suivant :

c varie le plus rapidement
puis x
puis y

Autrement dit, les quatre composantes d’un pixel sont contiguës.

L’indice 1D peut alors être défini par :

i = ((y × 50) + x) × 4 + c

avec :

0 ≤ x < 50
0 ≤ y < 100
0 ≤ c < 4

Le nombre total d’éléments est :

50 × 100 × 4 = 20000

Si chaque composante est un octet, le tableau occupe également 20000 octets.

Pour retrouver les coordonnées à partir de i, on commence par retrouver c :

c = i mod 4

On définit ensuite :

q = i / 4

avec une division entière.

On obtient alors :

x = q mod 50

et :

y = q / 50

avec une nouvelle division entière.

Ainsi :

c = i % 4
q = i / 4
x = q % 50
y = q / 50

Cette transformation repose sur la décomposition d’un indice selon les différentes dimensions du tableau.

Q6.3. Interpolation linéaire

On souhaite transformer une valeur x de l’intervalle [a,b] vers une valeur de [c,d].

Une première étape consiste à normaliser x dans [0,1]. On définit :

t = (x - a) / (b - a)

Lorsque x = a, on obtient t = 0. Lorsque x = b, on obtient t = 1.

Il suffit ensuite de transformer [0,1] vers [c,d] :

f(x) = c + t(d-c)

En remplaçant t :

f(x) = c + ((x-a)/(b-a))(d-c)

soit :

f(x) = c + (x-a)(d-c)/(b-a)

Cette fonction vérifie :

f(a) = c
f(b) = d

Lorsque a ≠ b, cette fonction est bijective entre les deux intervalles si c ≠ d.

Q7. FileWriter et couches logicielles

Lorsque le programme Java exécute :

FileWriter fw = new FileWriter(...);
fw.write(...);
fw.close();

le programme ne commande pas directement le disque physique.

Le premier niveau est celui du programme Java. FileWriter appartient aux bibliothèques de la plateforme Java et fournit une abstraction permettant d’écrire des caractères dans un fichier.

La JVM exécute le bytecode Java. Selon l’implémentation, certaines opérations peuvent être interprétées, compilées dynamiquement ou exécutées par du code natif fourni par la bibliothèque.

Pour effectuer réellement une opération sur un fichier, la JVM ou une bibliothèque native doit finalement demander au système d’exploitation d’effectuer une opération d’entrée-sortie. Cette communication passe par des appels système ou par des mécanismes équivalents dépendant du système.

On peut représenter le chemin conceptuel ainsi :

Cette organisation permet au programme de rester indépendant des détails du matériel. Le même code Java peut demander l’ouverture d’un fichier sans connaître le protocole matériel utilisé par le SSD ou le disque.

L’appel système constitue donc une frontière importante entre l’espace utilisateur et le noyau. Le programme utilisateur demande un service au système d’exploitation, et le noyau possède les privilèges nécessaires pour manipuler les ressources protégées.

Q8. Format de fichier conteneur

Le format proposé contient un en-tête avec un magic code, une version et une table de tuples décrivant les fichiers internes.

Un tuple contient :

int debut
int fin

Si un int occupe 4 octets, un tuple occupe donc :

4 + 4 = 8 octets

La table dispose de 1024 octets. Le nombre maximal de tuples est donc :

1024 / 8 = 128

Le format permet donc de référencer au maximum 128 fichiers.

Une structure C naturelle serait :

struct FileEntry {
    uint32_t debut;
    uint32_t fin;
};

Cette structure représente directement les deux nombres utilisés dans le format binaire, sous réserve de définir explicitement leur représentation et leur endianness.

En Java, on pourrait utiliser :

class FileEntry {
    int debut;
    int fin;
}

Mais cette classe ne doit pas être considérée comme un format de fichier binaire. Un objet Java possède une représentation mémoire propre à la JVM et contient notamment un en-tête d’objet. Il faut donc explicitement écrire les deux entiers dans le format voulu.

Par exemple, un programme Java peut utiliser un DataOutputStream ou des opérations équivalentes pour sérialiser explicitement les champs.

Cette distinction est fondamentale. Une structure C peut avoir une représentation mémoire très proche du format binaire souhaité, mais il faut malgré tout faire attention au padding, à l’endianess et à la taille exacte des types. Une classe Java est une abstraction objet et ne constitue pas directement une spécification de format binaire.

Ajouter un fichier

Pour ajouter un fichier, le programme doit d’abord identifier une zone libre dans le conteneur. Il écrit ensuite les données du nouveau fichier dans cette zone et ajoute une entrée dans la table contenant son début et sa fin.

Si le fichier est ajouté à la fin du conteneur, le processus est particulièrement simple :

nouvelle_fin = ancienne_fin + taille_du_fichier

puis :

entry.debut = ancienne_fin
entry.fin = nouvelle_fin

La table doit ensuite être mise à jour.

Si les 128 entrées sont déjà utilisées, il faut soit refuser l’ajout, soit disposer d’une table plus grande ou d’un mécanisme permettant d’étendre la table.

Supprimer un fichier

La solution la plus simple consiste à effectuer une suppression logique. L’entrée correspondant au fichier est marquée comme libre, mais les données du fichier restent physiquement dans le conteneur.

On obtient alors :

+------+--------+------+--------+------+
| F1   | libre  | F3   | libre  | F5   |
+------+--------+------+--------+------+

Cette solution est très rapide, car supprimer un fichier peut se limiter à modifier une entrée dans la table.

En revanche, l’espace disque n’est pas immédiatement récupéré sous la forme d’une zone contiguë utilisable sans gestion supplémentaire. Plusieurs suppressions peuvent donc provoquer une fragmentation.

Une suppression physique consiste à déplacer les données situées après le fichier supprimé afin de fermer le trou. Si un fichier supprimé se trouve au milieu du conteneur, cela peut nécessiter le déplacement d’une grande quantité de données.

Il faut alors mettre à jour les offsets des fichiers déplacés. La suppression peut donc devenir coûteuse en temps d’exécution et en écritures disque.

Fragmentation

Après plusieurs opérations d’ajout et de suppression, l’espace libre peut être réparti entre différents fichiers.

Par exemple :

+------+--------+------+--------+------+
| F1   | libre  | F3   | libre  | F5   |
+------+--------+------+--------+------+

L’espace libre total peut être important tout en étant divisé en petites zones.

Cela constitue une fragmentation externe. Un nouveau fichier de grande taille peut ne pas pouvoir être placé dans une seule zone libre suffisamment grande, même si la quantité totale d’espace libre est suffisante.

Une solution consiste à effectuer périodiquement une compactification. Les fichiers sont alors déplacés afin de regrouper l’espace libre.

Par exemple :

avant :

+------+--------+------+--------+------+
| F1   | libre  | F3   | libre  | F5   |
+------+--------+------+--------+------+

après :

+------+------+------+----------------+
| F1   | F3   | F5   |      libre     |
+------+------+------+----------------+

La compactification améliore l’utilisation de l’espace mais peut être coûteuse puisqu’elle implique des déplacements de données et une mise à jour des offsets.

Optimisation de la table

La première représentation utilise deux entiers de 32 bits par fichier :

début : 32 bits
fin   : 32 bits

soit 64 bits par entrée.

Avec 1024 octets, cela donne 128 fichiers.

Une première optimisation consiste à remplacer fin par la taille du fichier :

début
taille

Cela ne réduit pas directement le nombre de bits nécessaires, mais peut simplifier certaines opérations et permettre d’autres optimisations.

Une optimisation plus intéressante consiste à utiliser des unités d’allocation plus grandes que l’octet. Supposons par exemple que le conteneur soit organisé en blocs de 256 octets. Un offset n’a alors plus besoin d’exprimer chaque octet individuellement. Il peut exprimer un numéro de bloc.

Si le conteneur possède au maximum un nombre de blocs limité, le numéro de bloc peut être représenté avec moins de bits qu’un offset complet.

La possibilité de réduire les offsets dépend donc de la taille maximale du fichier conteneur et de la granularité minimale d’allocation.

Par exemple, si le conteneur ne peut pas dépasser une taille de 2^32 octets, un offset en octets nécessite 32 bits. Si l’on accepte une granularité de 256 octets, il suffit de référencer :

2^32 / 2^8 = 2^24

blocs.

Un offset de bloc peut donc être codé sur 24 bits au lieu de 32 bits.

Si début et fin sont tous deux codés sur 24 bits :

24 + 24 = 48 bits

soit 6 octets par entrée.

La table de 1024 octets pourrait alors contenir :

1024 / 6 = 170

entrées complètes, avec 4 octets inutilisés.

On pourrait donc référencer jusqu’à 170 fichiers avec cette représentation, contre 128 avec deux int de 32 bits.

Il est possible d’aller plus loin en utilisant une représentation différente, par exemple en stockant un offset de début et une taille, ou en utilisant des blocs de taille fixe. Cependant, toute réduction de la taille des métadonnées impose généralement une contrainte supplémentaire sur la taille maximale du fichier ou sur la granularité des allocations.

Il existe donc un compromis général entre capacité d’adressage, précision des offsets, taille des métadonnées, espace disque et performances.

Synthèse générale

L’ensemble du TD illustre une même idée fondamentale : un programme manipule des abstractions, mais ces abstractions doivent finalement être représentées par des bits et traitées par du matériel.

Une variable de haut niveau devient finalement une représentation mémoire ou un registre. Une structure décrit une interprétation particulière d’une suite d’octets. Un tableau multidimensionnel peut être représenté par une simple séquence contiguë d’octets. Un appel Java à write finit par nécessiter une interaction avec le système d’exploitation, puis avec le matériel.

Le système d’exploitation constitue une couche d’abstraction et de protection entre les programmes et les ressources matérielles. La JVM ajoute une couche supplémentaire d’abstraction dans le cas de Java. À l’inverse, le C et surtout l’assembleur permettent de se rapprocher beaucoup plus directement de la représentation matérielle.

Enfin, un format de fichier impose explicitement une représentation des données indépendante des abstractions du langage. Pour garantir qu’un fichier puisse être relu correctement, il faut définir précisément la taille des champs, leur ordre, leur représentation binaire, leur alignement éventuel et leur endianness. C’est précisément à ce niveau que les notions de langage, de mémoire, de système d’exploitation et de matériel se rejoignent.