Agrégation informatique externe 2022, épreuve 1Sujet et rapport du jury

AGREGATION
CONCOURS EXTERNE

INFORMATION AUX CANDIDATS

Ces codes doivent être reportés sur chacune des copies que vous remettrez.

Partie 1 : Système

[untel:~/Ag] ls -al
total 36
drwxrwxr-x 3 untel guntel 4096 nov. 7 18:10 .
drwxr-xr-x 75 untel guntel 20480 nov. 7 20:04 ..
lrwxrwxrwx 1 untel guntel 6 nov. 7 18:08 fc.txt -> fi.txt
-rw-rw-r-- 1 untel guntel 153 nov. 7 18:10 fi.txt
-rwxrw-r-- 1 untel otel 83 nov. 7 18:10 oui.sh
drwxrw-r-- 2 untel guntel 4096 nov. 7 18:08 sAg

• a.Quel est l'utilisateur qui utilise le terminal ?
• b.Quel est le propriétaire des fichiers?
• c.Que sont guntel et otel?
• d.Quel est le nom du répertoire courant ?
• e.Combien contient-il de fichiers? de répertoires?
• f.Pour oui.sh et fc.txt, expliquer les informations affichées. Des réponses précises sont demandées pour les colonnes 1, 3, 4 ainsi que la dernière.
• g.Quelles sont les opérations liées à sAg que peut faire un utilisateur dont l'identifiant est tritel (précisez les différentes possibilités) ? Par exemple, que se passe-t-il si, à partir du répertoire Ag, tritel tape la commande cd sAg.
• h.Pourquoi certains systèmes d'exploitation ont-ils une politique de gestion des droits et de permissions d'accès aux fichiers?

• -les 12 (de 0 à 11) premiers champs pointent sur un bloc de données,
• -le champ 12 pointe vers 256 blocs de données (simple indirection),
• -le champ 13 pointe vers 256^2 blocs de données (double indirection),
• -le champ 14 pointe vers 256^3 blocs de données (triple indirection),
• -le champ longueur : 32 bits, mais le premier bit de poids fort n'est pas utilisé.
• a.Quelle est la taille maximum d'un fichier sur ce système de gestion de fichiers?
• b.Quel est le nombre maximum de blocs ?

• c.Soit un fichier contenant 4567 octets.
  Combien de blocs occupe-t-il?
• d.Même question pour un fichier de 573448 octets. Parmi ces blocs, combien y a-t-il de blocs directs, indirects, double indirects et triple indirects?

"Imaginons maintenant un ministère qui garde ses dossiers dans une énorme armoire avec des millions de tiroirs : on aimerait bien, pour les mêmes raisons qu'avant, que les documents afférents à un même dossier se trouvent dans la mesure du possible rangés dans des tiroirs contigus. Vous devez embaucher une secrétaire et vous avez le choix entre deux candidates aux pratiques assez différentes : la première, quand un dossier est bouclé se limite à vider les tiroirs, et quand un nouveau dossier arrive elle le sépare en petits groupes de documents de la taille d'un tiroir, et range chaque groupe au hasard dans le premier tiroir vide qu'elle trouve dans l'armoire. Lorsque vous lui faites remarquer que ça risque alors d'être bien difficile de retrouver vite tous les documents du dossier du Crédit Lyonnais, elle répond qu'il faut engager tous les week-ends une dizaine de garçons pour tout remettre en ordre. La deuxième secrétaire, par contre, conserve sur son bureau une liste des tiroirs vides contigus, qu'elle met à jour toutes les fois qu'un dossier est clos et qu'on l'enlève des tiroirs ; quand un nouveau dossier arrive, elle cherche dans sa liste une suite de tiroirs vides contigus de taille suffisante et c'est là qu'elle place le nouveau dossier. Ainsi, vous explique-t-elle, s'il y a assez de mouvement, l'armoire restera toujours très bien rangée."

• -Que représente l'énorme armoire du ministère?
• -Que représentent les dossiers à ranger dans cette armoire?
• -Pourquoi séparer un dossier en petits groupes de documents?
• -Que représente la dizaine de garçons qui remettent tout en ordre?
• -Que représente la liste des tiroirs vides mise à jour par la deuxième secrétaire.
• -Quelle est la méthode la plus performante ?
• -Si vous en connaissez, donnez des exemples concrets correspondants aux deux méthodes décrites.

int main(void)
{
    for (;;)
        fork();
        return 0;
    }

• • 2.Est-ce un problème? Si oui, donner une solution pour l'éviter.
• b.1. Soit la fonction C qui calcule x^n de façon récursive en créant un fils qui va calculer x^(n/2) et le reste par le père.

int calcul (int x, int n)
{
    int a, b, pid;
    int p = n / 2;
    int fds[2];
    if (n == 0) return 1;
    if (n == 1)
    {
        return x;
    }
    if (pipe (fds) == -1)
    {
        perror ("Erreur creation tube");
        exit (1);
    }
    pid = fork ();
    switch (pid)
    {
    case -1:
        perror ("Erreur creation processus fils");
        exit (1);
    case 0: // fils
        close (fds[0]);
        a = calcul (x, p);
        write (fds[1], &a, sizeof (int));
        exit (0);
    default: // pere
        close (fds[1]);
        read (fds[0], &a, sizeof (int));
        b = calcul (x, n - p);
        wait (NULL);
    }
    return (a * b);
}

pid_t fork(void);
int pipe(int pipefd[2]);
pid_t wait(int *status);
ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, const void *buf, size_t count);
int close(int fd);

2. Que pouvez-vous dire de l'efficacité de ces deux fonctions calculant x^n ?

Partie 2 : Nombres flottants

• a.0000000000000000000000000000000000000000000000000000000000000000 qu'on peut noter 0|0⋯0|0⋯0
• b.0000000000000000000000000000000000000000000000000000000000000001 qu'on peut noter 0|0⋯0|0⋯01
• c.0000000000010000000000000000000000000000000000000000000000000000 qu'on peut noter 0|0⋯01|0⋯0
• d.0000000000010000000000000000000000000000000000000000000000000001 qu'on peut noter 0 | 0⋯01|0⋯01

• a.1
• b.-1
• c. 2^(− 53)
• d. 1 + 2^(− 50)

• a.Supposons s = 0, E = 0 et f ≠ 1⋯1; que vaut S(x) ?
• b.Supposons s = 0, 1 ≤ E ≤ 2^(11) − 2 et f ≠ 1⋯1; que vaut S(x) ?
• c.Supposons s = 0, E = 0 et f = 1⋯1; que vaut S(x) ?
• d.Supposons s = 0, 0 ≤ E ≤ 2^(11) − 2 et f ≠ 1⋯1; que vaut S(x) ?
• e.Supposons s = 0, 0 ≤ E ≤ 2^(11) − 2 et f = 1⋯1; que vaut S(x) ?
• f.Conclure sur S.

• a.Prouver que 0, 1, 1/8, 2^(52) et − 2^(52) sont des flottants selon cette caractérisation.
• b.Donner le plus grand nombre flottant et le plus petit nombre flottant strictement positif.
• c.Donner tous les nombres flottants dans l'intervalle [1 − 2^(− 52); 1 + 2^(− 52)].

if (x != 0):
    z=1/(x*x)

• a.Trouver un nombre flottant x tel que 1 ⊕ x = 1.
• b.Trouver le plus grand nombre flottant x tel que 1 ⊕ x = 1. Justifier.

• a.Trouver un nombre flottant x tel que D(1 + x) = 1.
• b.Trouver le plus grand nombre flottant x tel que D(1 + x) = 1. Justifier.

• a.Trouver un nombre flottant x tel que U(1 + x) = 1.
• b.Trouver le plus grand nombre flottant x tel que U(1 + x) = 1. Justifier.

Partie 3 : Logique, déduction naturelle

• 1.Si Informatix réussit sa preuve, il sera content.
• 2.S'il pleut, Informatix restera chez lui.
• 3.Si Informatix ne reste pas chez lui, alors il sera content.
• 4.Chez lui, Informatix s'entraîne.
• 5.Informatix réussira sa preuve s'il s'entraîne.
• a.Formaliser ces faits à l'aide de formules logiques propositionnelles.
• b.Montrer, en déduction naturelle, qu'Informatix sera content.

• a.Montrer en déduction naturelle les deux séquents suivants. L'un des deux séquents est classique, dire lequel.
  • 1. Γ⊢(A ⇒ B) ⇒ (¬A ∨ B)
  • 2. Γ⊢(¬A ∨ B) ⇒ (A ⇒ B)
• b.Lorsque la formule à éliminer est une hypothèse, on donne les règles alternatives Hypothèses, en annexe.
  En vous aidant des règles Hypothèses, montrer que : Γ⊢∃x¬P(x) ⇒ ¬(∀xP(x))
• c.A partir de la règle ⊢A ∨ ¬A, est-il possible de montrer ⊢¬¬A ⇒ A ?
  Si oui, faire la démonstration, sinon expliquer pourquoi.
• d.Expliquer par un (contre-)exemple (intuitif) pourquoi ∀x∃yP(x, y) n'est pas la même chose que ∃y∀xP(x, y).

Partie 4 : Réseaux

Figure 1 - Le réseau étudié.

• 1.La machine A ne dispose pour l'instant que de son adresse mac et sait qu'il faut utiliser DHCP pour obtenir une adresse IP. Décrire les trames transmises dans le réseau 174.24.64.0 pour que la machine A obtienne une adresse ip. Pour cela, indiquer le service auquel correspond chaque trame et le plus de détails possibles sur le type d'opération du service et les entêtes des unités de données encapsulées dans la trame (les adresses MAC, les adresses IP, et le cas échéant d'autres identifiants de niveau supérieur).

• 2.L'utilisateur de la machine A souhaite consulter le site web www.agreg-info.org. Décrire les trames échangées lorsque la machine A cherche à établir une session web sur le serveur (www.agreg-info.org). Nous supposons que le serveur dNS situé sur le même réseau que l'utilisateur dispose, lui, de l'information pour résoudre directement le nom de domaine www.agreg-info.org en 185.26.126.225.
• 3.Pour les trames identifiées dans les deux premières questions et encapsulant des messages de haut niveau (applicatifs), est ce qu'elles encapsulent toutes des segments du même protocole de transport? Justifier.

4. Suite à une analyse de trafic sur l'interface if2 du routeur R1 nous avons capturé les deux datagrammes représentés en figure 2. Visiblement il s'agit de deux fragments d'un même datagramme (numéro 85). En effet, le protocole IP au niveau de R2 a dû fragmenter le datagramme numéro 85 avant de le transmettre sur le lien R2 - R1.

• • a- Donner l'unité maximale de transmission (MTU) sur le lien R2-R1. Pour quelles raisons peut-on limiter la taille maximale des trames sur les supports de transmission?
  • b- Même si la MTU dans le réseau 174.24.64.0 est de 1500 octets, le protocole IP ne réassemble les fragments qu'à la destination finale. Pour quelles raisons?
  • c- Le champs TTL est utilisé pour détruire les datagrammes lorsque sa valeur arrive à 0. Sachant que la valeur du TTL du datagramme original (à la source) était de 64 au départ, combien de routeurs ont été traversés par ces deux datagrammes ?
  • d- Quelles sont les valeurs de ^′ x^′ et ^′ y^′ dans les champs data des deux fragments?
  • e- La somme de contrôle "Header Checksum" sert à la fonction du contrôle d'erreurs au niveau de l'entête du datagramme ip. Cette fonction est-elle réalisée uniquement au niveau de la destination ou au niveau de chaque routeur traversé ? Justifier.
• 5.À présent, l'utilisateur souhaite faire un transfert de fichiers vers le serveur ftp.
  • a- Ce service nécessite également l'établissement d'une connexion. Quelle est l'entité de protocole qui se charge de l'établissement de cette connexion ? Cette même entité existe sur R1, sur R2, ou sur tous les routeurs?
  • b- Vu que la machine A dispose déjà d'une connexion tcp avec le serveur web, peut-il établir une seconde connexion pour le service FTP? Si oui, comment l'entité protocolaire distingue-t-elle les deux connexions ?

• • c- On considère dans la suite que la machine A a normalement terminé le téléchargement et a fermé sa connexion avec le service FTP. La connexion avec le service web s'est brutalement interrompue et la machine A en démarre une nouvelle (toujours vers www.agreg-info.org). Est-il possible que des segments de la première connexion du service WEB interfèrent avec ceux de la seconde? Justifier.
• 6.
  Nous considérons la table de routage du routeur R2. Quatre datagrammes arrivent sur R2 et ont respectivement comme adresse IP destination : 174.24.64.45, 188.114.255.2, 188.114.255.4, 67.44.21.97.

  Destination	Prochain saut	Interface
  174.24.64.0/18	R1	if1
  67.44.16.0/20	R3	if3
  67.44.16.0/22	R4	if4
  188.114.255.0/30	R3	if3
  0.0.0.0/0	R5	if2

  • a- Donner le prochain saut de chacun de ces paquets en expliquant le principe de fonctionnement suivi et les opérations réalisées dans la table.
  • b- Nous avons, par la suite, constaté d'autres paquets destinés toujours à la machine 174.24.64.45. Ces paquets proviennent de la même source et ont exactement la même taille. En revanche leur latences respectives étaient différentes. Donner les raisons de cette variabilité en décrivant les facteurs impactant les délais de transmission de bout-en-bout.
• 7.
  Nous considérons cette fois un système autonome constitué de six routeurs nommés R1, R2, R3, R4, R5 et R6 (voir figure 3). Le protocole de routage utilisé est RIP (Routing Information Protocol) s'appuyant sur l'algorithme de détermination des routes décentralisé Bellman-Ford.
  

  Figure 3 - Système autonome à six routeurs.
  • a- Établir les tables de routage des routeurs R2 et R3. L'ordre dans lequel circulent les messages RIP a-t-il de l'importance?
  • b- La liaison entre R2 et R6 tombe en panne. Expliquer comment les routeurs R2 et R3 détectent la rupture et montrer comment l'information se propage aux autres routeurs.
  • c- Expliquer la différence entre une panne d'un routeur et une rupture de lien avec l'incidence que cela pourrait avoir sur les tables de routage.
• 8.Supposons que la machine A et les deux serveurs dns et dhcp sont sur un réseau ethernet 1Gbit/s qui utilise une trame minimale de 512 octets.
  • a- Quel est le temps d'émission d'une trame de longueur minimale?

• b- Peut-on en déduire la période de vulnérabilité dans un tel réseau?
• c- Décrire la différence entre ce débit support, le débit utile et le débit réel en s'appuyant sur les facteurs influençant les variations du débit.

Annexes partie 4

Annexe A - Encapsulation dans TCP/IP et dans UDP/IP

Figure 4 - Encapsulation de données dans TCP/IP.

Annexe B - Principe de DHCP

• -Le client diffuse un datagramme DHCP_DISCOVER.
• -Tout serveur DHCP ayant reçu ce datagramme, envoie une offre DHCP_OFFER s'il est en mesure de proposer une adresse sur le réseau auquel appartient le client.
• -Le client retient une des offres reçues et diffuse sur le réseau un datagramme de requête DHCP_REQUEST.
• -Le serveur DHCP élabore un datagramme d'accusé de réception DHCP_A CK qui assigne au client l'adresse ip et son masque de sous-réseau, la durée du bail de cette adresse, etc.

Annexe C - Principe de DNS

• -Le client DNS de la machine envoie une requête DNS "Je recherche l'adresse ip de www.agreg-info.org".
• -Le serveur DNS envoie une réponse au client (www.agreg-info.org = @IP 185.26.126.225).