Devoir de T°NSI : ordonnancement, commandes du terminal, python

Exercice 1

1) La commande ps suivie éventuellement de diverses options permet de lister les processus actifs ou en attente sur une machine. Sur une machine équipée du système d’exploitation GNU/Linux, la commande “ps -aef” permet d’obtenir la sortie suivante (extrait) :

a) Quelle est la particularité de l’utilisateur “root” ?

corrigé

Le super-utilisateur (root) dans GNU/Linux est l'utilisateur qui a les droits d'accès administratifs au système, donc tous les droits.

b) Quel est le processus parent du processus ayant pour PID 3383 ?

corrigé

C'est le processus dont le PID est 1 car le PPID (Parent PID) de 3383 est 1. C'est donc celui lancé par la commande /sbin/init splash

Dans un bureau d’architectes, on dispose de certaines ressources qui ne peuvent être utilisées simultanément par plus d’un processus, comme l’imprimante, la table traçante, le modem. Chaque programme, lorsqu’il s’exécute, demande l’allocation des ressources qui lui sont nécessaires. Lorsqu’il a fini de s’exécuter, il libère ses ressources.

2) On appelle p1, p2 et p3 les processus associés respectivement aux programmes 1, 2 et 3.

a) Justifier qu'une situation d'interblocage peut se produire.

corrigé

Si chaque processus a exécuté sa première instruction, p1 a obtenu la table traçante, p2 le modem, p3 l'imprimante. Tous ont besoin d'une ressource qui est déjà prise pour continuer leur exécution, on a donc un interblocage (les processus se bloquent entre eux).

b) Modifier l'ordre des instructions du programme 3 pour qu'une telle situation ne puisse pas se produire.

corrigé

Il suffit de changer l'ordre pour que le programme 3 demande d'abord la table traçante avant le modem.

De cette manière on a l'ordre table traçante -> modem -> imprimante et un processus demande toujours les processus dans cet ordre. Il ne peut donc pas y avoir de boucle de demande, car cela nécessiterait un processus qui a une ressource et en demande une qui est devant dans l'ordre.

On pourrait aussi justifier plus simplement que le blocage précédent ne peut pas se produire car les programmes 1 et 3 ne pourront pas exécuter seulement leur première instruction chacuns, et que dans chacun des cas au moins un programme peut continuer donc il n'y a pas d'interblocage.

Exercice 2

Voici le résultat d'une commande ls -l dans le terminal linux:

laura@portable:~/docs$ ls -l
total 4
drwxr-xr-x 2 laura laura 4096  2 mars  21:31 bidule
-rwxrw---x 1 laura profs    0  1 mars  21:10 machin.sh
-rw-r--r-- 1 root root     0  2 mars  21:31 truc

Quel est l'utilisateur ? laura
Quel est le nom de la machine utilisée ? portable
Quel est le répertoire courant ? ~/docs
Combien contient-il de fichiers ? de dossiers ?

Un dossier (marqué avec d, bidule) et deux fichiers (- à la place de d, machin.sh et truc) 5. Pour le fichier machin.sh, expliquer chacune des informations affichées.

Le fichier est possédé par l'utilisatrice laura et elle a tous les droits dessus (rwx), par le groupe profs dont les utilisateurs ont les droits de lecture et écriture rw- et les autres utilisateurs ont le droit d'exécution --x. On a ensuite la taille du fichier en octets (0) et la date de dernière modification.

Exercice 3

Dessinez l'arborescence du répertoire ~/sandbox à la fin de cette série de commandes :

laura@portable:~$ mkdir sandbox
laura@portable:~$ cd sandbox/
laura@portable:~/sandbox$ mkdir a b c d

laura@portable:~/sandbox$ touch a/t.txt d/foo.txt

laura@portable:~/sandbox$ cd c
laura@portable:~/sandbox/c$ mkdir ../b/e f g

laura@portable:~/sandbox/c$ cd ..
laura@portable:~/sandbox$ cp */*.txt c/g

laura@portable:~/sandbox$ rm -rf d

Exercice 4

Expliquez ce qui est fait dans la série de commandes suivantes :

laura@portable:~/sandbox$ wget tnsi.xyz/script.sh
laura@portable:~/sandbox$ ls -l
total 4
-rw-r--r-- 1 laura profs 65  2 mars  21:45 script.sh
laura@portable:~/sandbox$ chmod g+w script.sh 
laura@portable:~/sandbox$ ls -l
total 4
-rw-rw-r-- 1 laura profs 65  2 mars  21:45 script.sh
laura@portable:~/sandbox$ chmod a+x script.sh 
laura@portable:~/sandbox$ ls -l
total 4
-rwxrwxr-x 1 laura profs 65  2 mars  21:45 script.sh
laura@portable:~/sandbox$ ./script.sh

corrigé

On télécharge depuis internet le fichier script.sh avec la commande wget, qu'on voit bien dans l'affichage de ls -l suivant.

Puis on modifie ses droits avec la commande chmod pour autoriser tous les utilisateurs du groupe qui le possède à le modifier g+w, c'est à dire les utilisateurs du groupe profs.

Ensuite on ajoute à tous le droit d'exécution avec a+x.

Enfin on exécute ce script avec ./script.sh : c'est la manière d'exécuter un programme qui se trouve à l'endroit où on est, car . est un référence au répertoire actuel. Si on ne met par le ./, le terminal cherche le programme dans la liste des endroits pour programme de la variable PATH, qui ne contient pas forcément le répertoire actuel.

Exercice 5

Créez une classe Arbre avec :

une méthode __init__ qui ne prend pas de paramètres et initialise un attribut sous_arbres avec la liste vide.
une méthode récursive taille qui renvoie 1 plus la somme de ce que renvoie la méthode taille de chacun des éléments de l'attribut sous_arbres.
une méthode récursive hauteur qui calcule la hauteur de l'arbre (à vous de trouver comment). La hauteur de l'arbre créé avec l'appel Arbre() doit être de 0.

corrigé

class Arbre:
    def __init__(self):
        self.sous_arbres = []

    def taille(self):
        resultat = 1
        for arbre in self.sous_arbres:
            resultat += arbre.taille()
        return resultat
    
    def hauteur(self):
        max_hauteur_sous_arbre = 0
        for arbre in self.sous_arbres:
            hauteur_arbre = arbre.hauteur()
            if hauteur_arbre > max_hauteur_sous_arbre:
                max_hauteur_sous_arbre = hauteur_arbre
        return 1 + max_hauteur_sous_arbre

quelles sont les complexités de taille et hauteur en fonction du nombre de noeuds \(n\) de l'arbre ?

corrigé

Les deux font un parcours en profondeur de l'arbre, donc elles sont exécutées une fois sur chaque noeud, donc la complexité est linéaire en \(n\) c'est à dire en \(O(n)\).