SERIE D’EXERCICES DE REVISION

Concepts de base des systèmes d’exploitation

Iset’Com - Stic-L1-14-Juin-2011

* * * *

QUESTION POSEE PAR L’ETUDIANTE SAFA FRAIJI - STIC L1D

LRU (Least Recently Used) : Cet algorithme remplace la page la moins récemment utilisée. L'idée

est de garder les données récemment utilisées.

FIFO (First In First Out) : Les pages sont remplacées dans l'ordre où elles sont arrivées.

Attention : Il y’a une grande différence entre LRU et FIFO !

Exercice corrigé:

Un ordinateur possède une mémoire principale constituée de 3 cadres de pages. Lorsqu'il n'y a pas

assez de mémoire principale, le système d'exploitation récupère un cadre de page en utilisant

l'algorithme de remplacement LRU.

Combien de défauts de page se produit pour la séquence de demandes de pages :

1, 2, 3, 1, 4, 1, 3, 2, 5,4 (sachant qu'au démarrage, aucune page n'est en mémoire principale) ?

Solution (LRU):

* * * * * * *

1 1 1 1. 1 1. 1 1 5 5

- 2 2 2 4 4 4 2 2 2

- - 3 3 3 3 3. 3 3 4

Nombre des fautes de pages = 7

Solution (FIFO):

* * * * * * * *

1 1 1 1. 4 4 4 4 5 5

- 2 2 2 2 1 1 1 1 4

- - 3 3 3 3 3. 2 2 2

Nombre des fautes de pages = 8

QUIZZ N°1

Question 1:

Aux origines de l’informatique, l'interface utilisateur des systèmes d’exploitations était composée :

1. D’écrans, de claviers et de souris

2. De cartes perforées

3. D’interrupteurs et de lampes <---

Question 2:

Avec l’évolution des systèmes d’exploitation, la ligne de commande et l’interface graphique sont apparues

pour faciliter le dialogue entre les OS et les utilisateurs. Mais quel système est apparu avant l’autre ?

1. L’interface graphique avant la ligne de commande

2. La ligne de commande avant l’interface graphique <---

3. Les deux sont apparues en même temps

Question 3:

Dans les années 80, à quelle société Microsoft proposa t-il son système d’exploitation PC-DOS qui allait

ensuite devenir MS-DOS ?

1. IBM

2. Amiga <---

3. Apple

Question 4:

Avec quel type de processeur Microsoft Windows n’est pas compatible :

1. Motorola

2. AMD <---

3. Intel

Question 5:

Plus de 80% des 500 ordinateurs les plus puissants au monde sont équipés d’un système d’exploitation :

1. Unix

2. Windows

3. Linux <---

Question 6:

Quelle entreprise finance le système d’exploitation open source mobile Androïd ?

1. Microsoft

2. Yahoo

3. Google

Question 7:

Le système d’exploitation FreeBSD, utilisé partiellement pour le système d’exploitation d’Apple, est basé sur

un noyau :

1. Microsoft

2. Unix

3. Linux

Question 8:

Une de ces distributions n’est pas une distribution Linux. Laquelle ?

1. Solaris <---

2. Mandriva

3. Ubuntu

Question 9:

Quelles sont les bibliothèques qui ne sont pas utilisées dans les systèmes d’exploitation ?

1. Les bibliothèques applicatives

2. Les bibliothèques utilitaires <---

3. Les bibliothèques systèmes

Question 10:

A quoi sert un système de fichier ?

1. Il permet de stocker les informations et de les organiser sur la mémoire cache

2. Il permet de stocker les informations et de les organiser sur la mémoire vive

3. Il permet de stocker les informations et de les organiser sur les mémoires secondaires<-

Bonnes réponses:

Q1: (3); Q2: (2); Q3: (1); Q4: (1); Q5: (3); Q6: (3); Q7: (2); Q8: (1); Q9: (1); Q10: (3)

QUIZZ N° 2

Question 1- Un système informatique est constitué de:

1. Le matériel

2. Le logiciel

3. Les applications des utilisateurs

Question 2- Le système d'exploitation fait partie:

1. Du matériel

2. Des logiciels de base

3. Des logiciels d'application

Question 3- Un système d'exploitation permet de:

1. Transformer le matériel en une machine virtuelle

2. Exploiter les ressources CPU au maximum

3. Optimiser l'utilisation des ressources (matérielles et logicielles)

Question 4- Un système monotâche:

1. N'utilise pas de système d'exploitation

2. A pour seule tâche le système d'exploitation

3. Contient en mémoire le système d'exploitation

4. Contient en mémoire la tâche en cours d'exécution

Question 5- Unix est un système :

1. Multitâche

2. À temps complet

3. Multi-utilisateur

4. À temps partagé

Question 6- L'architecture logicielle "classique" d'un ordinateur est :

1. Le système d'exploitation directement au-dessus du matériel

2. L'application directement au-dessus du matériel

3. Les applications directement au-dessus du système d'exploitation

4. Le système d'exploitation à côté des applications

Bonnes Réponses : Q1:(1,2) - Q2: (2)– Q3: (1,2,3) – Q4: (3,4) – Q5: (1,3,4) – Q6: (1,3)

QUIZZ N° 3

Q1- Un système d’exploitation

1. C’est la fonction de l’administrateur système

2. C’est un intermédiaire entre la machine et l’utilisateur

3. C’est le nom du processeur central de l’ordinateur

4. C’est l’éditeur exploitant le système

Q2- Linux c’est :

1. Un système d’exploitation fonctionnant sur PC

2. Un système d’exploitation fonctionnant sur Macintosh

3. Un pingouin de dessin animé

4. Un système d’exploitation au format libre

Q3- A proprietary operating system is ____.

1. unique to a manufacturer

2. similar to those of other manufacturers

3. used by many different computer manufacturers

4. properlyconfigured to operate

Q4- A computer's BIOS will ____

1. check for the presence of peripherals like mouse, sound card, scanner

2. run a check of memory

3. be loaded first when the computer is powered on

4. none of the above

Q5- When a computer is "swapping", it is _____.

1. moving data from the hard drive to the floppy drive

2. moving data from memory to the swap file on the hard drive

3. moving data between registers in memory

4. none of the above

Q6- L'origine d'Unix remonte à :

1. 1969

2. 1974

3. 1976

4. La date de création de DOS

5. 1984

Q7- Une tâche est :

1. Un logiciel de divertissement

2. Un processus

3. Une exécution de programme

4. Un mouvement de données avec les périphériques

Q8- Le multitâche :

1. nécessite, pour un système d'exploitation, d'avoir en mémoire centrale plusieurs tâches simultanément

2. Permet de commencer l'exécution d'un second programme alors qu'un premier est déjà en exécution,

3. chacun s'exécutant à tour de rôle

4. Ne permet pas le multi-utilisateur

Q9- Etats du processeur : quelle transition est déclenchée par l’évènement de l’arrivée d’un caractère

saisi au clavier ?

1. actif -> bloqué

2. bloqué -> prêt

3. prêt -> actif

Bonnes réponses:

Q1: (2); Q2: (4); Q3: (1); Q4: (1); Q5: (2); Q6: (1); Q7: (2 3); Q8: (1 2); Q9: (2)

QUIZZ N° 4

1. Que signifie préempter un processus, une tâche ?

(a) Suspendre son exécution au profit d’un autre processus / une autre tâche.

(b) Arrêter définitivement son exécution au profit d’un autre processus / une autre tâche.

(c) Geler le processus / la tâche pour un temps indéterminé (fini).

(d) Transférer le processus / la tâche en zone de swap

2. Qu’est-ce qu’un processus au sens d’un O.S. (Operating System) ?

(a) Une opération d’Entrée/Sortie.

(b) Un utilisateur connecté au système et utilisant des ressources.

(c) L’instance d’un programme en cours d’exécution.

(d) Un fichier statique stocké sur une mémoire de masse.

3. A quoi sert l’espace d’échange communément appelé espace de swap ?

(a) A améliorer le bon fonctionnement de l’O.S.

(b) A stocker momentanément des processus qui ne peuvent tenir (pour des raisons de place) dans la mémoire

principale (centrale).

(c) A empêcher la saturation de la mémoire centrale.

(d) A stocker des processus préemptés par le kernel.

4. Quel est le rôle d’un ordonnanceur scheduler au sein d’un O.S. ?

(a) Ordonnancer l’utilisation la mémoire virtuelle.

(b) Ordonnancer les opérations d’E/S.

(c) Ordonnancer les interruptions provoquées par les opérations d’E/S.

(d) Ordonnancer les processus à exécuter selon un ou des critères.

5. Qu’est-ce qu’un thread au sens d’un O.S. (Operating System) ?

(a) Une unité de commutation.

(b) Un processus léger.

(c) Une unité atomique d’exécution.

(d) Un nouveau terme remplaçant le terme obsolète de processus.

6. Que permet le concept de mémoire virtuelle ?

(a) de gérer une partie de l’espace disque (mémoire secondaire) comme s’il s’agissait de mémoire principale.

(b) d’exécuter des tâches qui ne peuvent physiquement tenir complètement en mémoire principale.

(c) d’utiliser efficacement les caches mémoires L1 et L2.

(d) d’augmenter la vitesse de commutation lors de la préemption des tâches.

7. Qu’est-ce qu’un driver au sens de Windows ?

(a) un protocole de fonctionnement pour toutes les cartes réseaux.

(b) une interface de gestion des imprimantes.

(c) une interface entre le matériel et l’O.S..

(d) une interface de gestion des cartes graphiques.

8. Quel est l’intérêt du partitionnement ?

(a) séparer le système, des données.

(b) attribuer des systèmes de fichiers différents aux différentes partitions.

(c) séparer l’espace noyau kernel land de l’espace utilisateur user land

(d) permettre l’installation de différents systèmes.

9. A quoi sert, globalement, la base de registres sous Windows ?

(a) Gérer la table des partitions.

(b) Gérer le mode de démarrage (normal, sans échec ...).

(c) Gérer la configuration logicielle et système de l’ordinateur.

(d) Gérer le matériel.

10. Un processus est :

(a) Un programme exécutable

(b) Une instance d’un programme exécutable

(c) un contexte processeur

11. Un processus Zombie est un processus

(a) qui a perdu son père

(b) qui a terminé son exécution en erreur

(a) qui a terminé son exécution et qui attend la prise en compte de cette fin par son père

12. Le processus A de priorité 7 s’exécute. Le processus B de priorité 5 se réveille. Le plus petit chiffre code

la priorité la plus forte. Quelles sont les propositions justes :

(a) B interrompt l’exécution de A car B est plus prioritaire et l’ordonnancement est préemptif

(b) A continue son exécution car il est plus prioritaire et l’ordonnancement est préemptif

(c) A continue son exécution car l’ordonnancement est non préemptif

(d) B interrompt l’exécution de A car B est plus prioritaire et l’ordonnancement est non préemptif

13. Pour gérer l’accès au processeur par les processus, l’algorithme d’ordonnancement LRU s’appuie en

particulier sur:

(a) Le temps CPU consommé par chaque processus

(b) Le nombre de fois que chaque processus a occupé le processeur

(c) Le dernier moment où chaque processus a utilisé le CPU

(d) Le nombre de processus en attente de CPU

14. Dans un langage de programmation les pointeurs permettent :

(a) de partager une zone de mémoire

(b) de chaîner les blocs de mémoire

(c) de transférer des données sans les déplacer

15. DOS signifie:

(a) Data Output System

(b) Disk Operating System

(c) Device Open System

QUESTIONS DIVERSES - I

Exercice 1

Définir les termes suivants :

1. Mémoire virtuelle:

2.Mémoire paginée :

3.Mémoire segmentée:

4. Mémoire associative:

Exercice 2

Définir succinctement les termes suivants :

1.Batch processing:

2.Time sharing:

3.Scheduling:

4. Multitasking:

5. First Come First Served:

Exercice 3

Un processeur a une vitesse de traitement de 0,5 Mips. Sa politique d'ordonnancement est RR avec un

quantum q. q est très inférieur au temps de service S (q<<S). On a un débit d'entrée de 1,5 programme/s et

chaque programme correspond en moyenne à 100000 instructions.

Combien y a-t-il, en moyenne, de programmes dans le système (en attente et en exécution)?

Quel est le temps de passage d'un programme?

Exercice 4

On donne cinq partitions libres de mémoire dans l’ordre : 100Ko, 500Ko, 200Ko, 300Ko, 600Ko.

Comment placent les algorithmes First-fit, Best-fit, et Worst-fit les processus suivants de 212Ko,

417Ko, 112Ko, et 426Ko ? Quel algorithme qui permet l'utilisation la plus efficace de la mémoire?

Exercice 5

Un processus A de priorité 7 s’exécute. Un processus B de priorité 5 se réveille. Le plus petit chiffre code la

priorité la plus forte.

Quelles sont les propositions justes :

1. B interrompt l’exécution de A car B est plus prioritaire et l’ordonnancement est préemptif

2. A continue son exécution car il est plus prioritaire et l’ordonnancement est préemptif

3. A continue son exécution car l’ordonnancement est non préemptif

4. B interrompt l’exécution de A car B est plus prioritaire et l’ordonnancement est non préemptif

QUESTIONS DIVERSES - II

Question 1 Une machine virtuelle est :

A. un composant matériel spécifique qui améliore la rapidité d’un système d’exploitation

B. un logiciel qui gère l’exécution de plusieurs systèmes d’exploitation en même temps

C. un logiciel qui permet la simulation du matériel sous-jacent

Question 2 Quelles sont les principales différences entre un processus et un thread ? Dans une application qui

partage des données en mémoire, faut-il privilégier les processus ou les threads ?

Question 3 Gestion mémoire : expliquez quand se produit un défaut de page et citez un algorithme de

remplacement de page qui gère les pages pour « swapper » les pages les moins récemment utilisées.

Question 4 On considère un ordinateur qui dispose de 4 cases mémoire. On donne ci-dessous en

microsecondes les moments de chargement, du dernier accès ainsi qu’un indicateur d’accès. Quelle est parmi

ces pages, la page qui sera remplacée et réécrite sur la zone de swap disque, sachant que l’algorithme utilisé

est FIFO ?

A. Page 0 Chargement : 126 Dernier accès : 279 Modifiée : Non

B. Page 1 ‘’ 230 ‘’ 260 Oui

C. Page 2 ‘’ 120 ‘’ 272 Non

D. Page 3 ‘’ 160 ‘’ 280 Oui

Question 5 On considère un ordinateur qui a 4 cases mémoire. On donne ci-dessous le moment de

chargementet le moment du dernier accès. Quel est la page qui sera remplacée par l’algorithme LRU ?

A. Page 0 Chargement : 126 Dernier accès : 279

B. Page 1 ‘’ 230 ‘’ 280

C. Page 2 ‘’ 120 ‘’ 281

D. Page 3 ‘’ 160 ‘’ 282

Question 6 Dans le contexte d’un système multiprogrammé à mémoire virtuelle, toutes les affirmations

suivantes sont vraies sauf une :

A. S’il y a une case libre en mémoire centrale, alors allouer la case

B. S’il n’y a pas de case libre en mémoire centrale, alors remplacer une page présente dans une case suivant

un algorithme de remplacement de pages

C. lorsque la page chargée en mémoire réelle est bien présente mais inexploitable, on parle de défaut de page

D. Un défaut de page se produit lorsque la page virtuelle n’est pas présente en mémoire réelle

Question 7 Dans un système de gestion mémoire virtuelle à pagination, dans quel cas est-il nécessaire de

réécrire la page sur l’espace de swap :

A. il n’y a plus d’espace disponible en mémoire centrale, donc toutes les pages déjà chargées sont réécrites

dans l’espace de swap

B. seules les pages modifiées sont sauvegardées dans l’espace de swap, pour les processus dont les pages

seront remplacées par l’algorithme de gestion des pages

C. lorsque le code du programme utilisateur est modifié dynamiquement

Question 8 Un défaut de page se produit :

A. lorsque la page virtuelle n’est pas présente en mémoire physique

B. Lorsque la page virtuelle ne peut plus être accédée sur le disque, dû à un secteur inaccessible

C. lorsque la page chargée en mémoire réelle est bien présente mais inexploitable

Question 9 La mémoire virtuelle à système de pagination est un mécanisme de gestion de la mémoire centrale

qui permet :

A. d’augmenter significativement le nombre de processus en mémoire centrale

B. d’augmenter considérablement l’espace de mémoire physique de la machine

C. d’augmenter uniquement l’espace de mémoire partagée entre processus

Question 10 Une mémoire centrale comporte 3 cases libres initialement vides. Un processus effectue les

accès suivants à ses pages : 1,2,3,1, 4. Lors de l'accès à la page 4 :

A. Avec une stratégie FIFO, la page 1 est remplacée

B. Avec une stratégie FIFO, la page 3est remplacée

C. Avec une stratégie LRU, la page 1 est remplacée

D. Avec une stratégie LRU, la page 3 est remplacée

Ancienne série - corrigée en classe

Exercice 1 Chacun des programmes en cours d’exécution d’un système multitâche est associé à une lettre majuscule de l’alphabet. Les temps d’exécution prévus sont donnés par les suites de lettres "AAAAAAAAA", "BBBB", "CCC" ; ainsi, par exemple, l’exécution complète du programme "B" nécessite quatre unités de temps.

La série de lettres "ABAAAABAACABCACB" indique l’utilisation des unités de temps du processeur.

Dans cet exemple, le programme "A" démarre en premier puis le programme "B" est activé; ensuite, le programme "A" poursuit son exécution pendant quatre unités de temps, etc. Chaque programme démarre au moment de la première apparition de sa lettre et attend tant qu’il n’est pas terminé et qu’un autre programme est actif.

Dans l’exemple précédent, combien de temps les trois programmes ont-ils attendu au total (unités de temps) – en justifiant votre approche de calcul ?

Exercice 2 Soit TS le temps de service d'un travail (job), c'est à dire le temps écoulé entre la soumission du travail et sa fin. On considère un système de traitement séquentiel (batch) dans lequel quatre travaux arrivent dans l'ordre suivant : N° du JOB Instant d'arrivée Durée 1 0 8 2 1 4 3 2 9 4 3 5 a- Donner le TS moyen dans le cas où l'on adopte la politique PAPS (Premier Arrivé, Premier Servi, ou encore FCFS, Fist Come Fisrt Served) b- Donner le TS moyen dans le cas où l'on adopte la politique préemptive : PCA (le plus court d'abord, ou encore SJF, Shortest Job First) Exercice 3 (Quantum de temps) Dans le cas de la stratégie d'allocation du processeur avec recyclage (algorithme du tourniquet, ou encore algorithme du quantum de temps), indiquer quels sont les effets des choix suivants pour le quantum q, sachant que s est le temps de changement de contexte et que t est le temps moyen d'utilisation du processeur entre deux événements bloquants (t >> s et [epsilon] << s) :

1. q = [infini] 2. q = [epsilon] 3. q = s

4. q = t 5. s < q <t 6. q > t

Pour chaque question, étudier les cas où s compris dans le quantum ou non.

Exercice 4 Un processeur a une vitesse de traitement de 0,5 Mips. Sa politique d'ordonnancement est RR avec un quantum q. q est très inférieur au temps de service S (q<<S). On a un débit d'entrée de 1,5 programme/s et chaque programme correspond en moyenne à 100000 instructions.

1. Combien y a t-il, en moyenne, de programmes dans le système (en attente et en exécution)? 2. Quel est le temps de passage d'un programme

Un petit problème

Réponse de l’exercice 3 :

1. Le processus garde le processeur tant qu'il en a besoin (comme FCFS,Fist Come Fisrt Served ), 2. Le processus ne fait presque rien entre chaque changement de contexte, progression très lente. Si s

est compté dans q, aucun processus n'est exécuté. 3. Si s est compris dans q, il ne se passe rien, sinon exécution pendant au plus s, 4. Le quantum a tendance à favoriser les processus orientés entrées-sorties, 5. Le quantum est quelconque, 6. Le quantum favorise les processus qui ne font que du calcul.

Rappels sur les algorithmes d’ordonnancement

FCFS (First Come First Serve), premier arrivé premier servi.

Dans un système à ordonnancement non préemptif ou sans réquisition, le système d'exploitation choisit le prochain processus à exécuter, en général, le Premier Arrivé est le Premier Servi PAPS (ou FCFS First-Come First-Served) ou le plus court d'abord ( SJF Short Job First). Il lui alloue le processeur jusqu'à ce qu'il se termine ou il se bloque (en attente d'un événement). Il n'y a pas de réquisition.

SJF (Short Job First), plus court d'abord

Si l'ordonnanceur fonctionne selon la stratégie SJF, il choisit parmi le lot de processus à exécuter, le plus court d'abord (plus petit temps d'exécution). Cette stratégie est bien adaptée au traitement par lots de processus dont les temps maximaux d'exécution sont connus ou fixés par les utilisateurs car elle offre un meilleur temps moyen de séjour. Le temps de séjour d'un processus (temps de rotation ou de virement) est l'intervalle de temps entre la soumission du processus et son achèvement.

SRT (Shortest Remaining Time), plus petit temps de séjour

L'ordonnancement du plus petit temps de séjour ou Shortest Remaining Time est la version préemptive de l'algorithme SJF. Un processus arrive dans la file de processus, l'ordonnanceur compare la valeur espérée pour ce processus contre la valeur du processus actuellement en exécution. Si le temps du nouveau processus est plus petit, il rentre en exécution immédiatement.

RR (Round Robin), algorithme circulaire

L'algorithme du tourniquet, circulaire ou round robin est un algorithme ancien, simple, fiable et très utilisé. Il mémorise dans une file du type FIFO (First In First Out) la liste des processus prêts, c'est à dire, en attente d'exécution. Il alloue le processeur au processus en tête de file, pendant un quantum de temps. Si le processus se bloque ou se termine avant la fin de son quantum, le processeur est immédiatement alloué à un autre processus (celui en tête de file). Si le processus ne se termine pas au bout de son quantum, son exécution est suspendue. Le processeur est alloué à un autre processus (celui en tête de file). Le processus suspendu est inséré en queue de file. Les processus qui arrivent ou qui passent de l'état bloqué à l'état prêt sont insérés en queue de file.

PRI (Priorités, sans évolution)

L'ordonnanceur à priorité attribue à chaque processus une priorité. Le choix du processus à élire dépend des priorités des processus prêts. Les processus de même priorité sont regroupés dans une file du type FIFO. Il y a autant de files qu'il y a de niveaux de priorité. L'ordonnanceur choisit le processus le plus prioritaire qui se trouve en tête de file. En général, les processus de même priorité sont ordonnancés selon l’algorithme du tourniquet.