Exercice Corrigé Ordonnancement Des Processus – Partie 2
L‘ordonnancement du processus est à la base des systèmes d’exploitation multiprogrammés. En répartissant l’unité centrale entre les processus, le système d’exploitation peut rendre l’ordinateur plus productif. Dans ce chapitre, nous présentons des exercices corrigés sur les concepts de base de l’ordonnancement, l’idée d’allocation de ressources et discutons en détail de l’ordonnancement de l’unité centrale. FCFS, SJF, Round-Robin, Priorité et les autres algorithmes d’ordonnancement devraient être familiers à vous.
Exercice 1: First Come First Serve (FCFS)
Rappel: Dans l’ordonnancement FCFS
- Le processus qui arrive en premier dans la file d’attente est le premier à se voir attribuer l’unité centrale.
- En cas d’égalité, le processus dont l’identifiant est le plus petit est exécuté en premier.
- L’ordonnancement est toujours non préemptif par nature.
- Les jobs sont exécutés selon le principe du premier arrivé, premier servi.
- Il s’agit d’un algorithme d’ordonnancement préemptif et non préemptif.
- Facile à comprendre et à implémenter.
- Son implantation est basée sur la file d’attente FIFO.
- Peu performant car le temps d’attente moyen est élevé.
1.1) Considérons les processus suivants avec un temps de rafale (temps d’exécution de l’unité centrale). Dessinez l’ordre d’exécution des processus à l’aide d’un diagramme de Gantt (ligne temporelle) pour FCFS, et calculez le temps d’attente moyen et le temps moyen de rotation.
+-----------------+-----------------+------------------------------------------+ | ID du processus | Temps d'arrivée | Temps de rafale/temps d'exécution du CPU | +-----------------+-----------------+------------------------------------------+ | P1 | 0 | 2 | +-----------------+-----------------+------------------------------------------+ | P2 | 1 | 3 | +-----------------+-----------------+------------------------------------------+ | P3 | 2 | 5 | +-----------------+-----------------+------------------------------------------+ | P4 | 3 | 4 | +-----------------+-----------------+------------------------------------------+ | P5 | 4 | 6 | +-----------------+-----------------+------------------------------------------+
Temps de rotation = Temps fin d’exécution – Temps d’arrivée
Temps d’attente = Temps de rotation – Temps de rafale
Temps moyen de rotation = 2+4+8+11+16/5 = 41/5 = 8.2 Temps moyen d'attente = 0+1+3+7+10/5 = 21/5 = 4.2
1.2) Considérons les processus suivants P1, P2, P3 arrive pour être exécuté dans le même ordre, avec un temps d’arrivée de 0 avec un temps de rafale (temps d’exécution de l’unité centrale). Dessinez l’ordre d’exécution des processus à l’aide d’un diagramme de Gantt (ligne temporelle) pour FCFS, et calculez le temps d’attente moyen et le temps moyen de rotation.
+-----------------+-----------------+-----------------+ | ID du processus | Temps d'arrivée | Temps de rafale | +-----------------+-----------------+-----------------+ | P1 | 0 | 24 | +-----------------+-----------------+-----------------+ | P2 | 0 | 3 | +-----------------+-----------------+-----------------+ | P3 | 0 | 5 | +-----------------+-----------------+-----------------+
Temps de rotation = Temps fin d’exécution – Temps d’arrivée
Temps d’attente = Temps de rotation – Temps de rafale
+-----------+-----------------+-------------------+ | Processus | Temps d'attente | Temps de rotation | +-----------+-----------------+-------------------+ | P1 | 0 | 24 | +-----------+-----------------+-------------------+ | P2 | 24 | 27 | +-----------+-----------------+-------------------+ | P3 | 27 | 30 | +-----------+-----------------+-------------------+
Temps d'attente total = 0 + 24 + 27 = 51 ms
Temps moyen d'attente = (Temps d'attente total) / (Nombre total de processus)
= 51 / 3
= 17 ms
Temps de rotation total = 24 + 27 + 30 = 81 ms
Temps moyen de rotation = (Temps de rotation total) / (Nombre total de processus)
= 81 / 3
= 27 ms
Débit = 3 jobs/30 sec = 0.1 jobs/sec
1.3) Considérons les processus suivants P1, P2, P3, P4 arrive pour être exécuté dans le même ordre, avec un temps de rafale (temps d’exécution de l’unité centrale). Dessinez l’ordre d’exécution des processus à l’aide d’un diagramme de Gantt (ligne temporelle) pour FCFS, et calculez le temps d’attente moyen et le temps moyen de rotation.
+-----------------+-----------------+-----------------+ | ID du processus | Temps d'arrivée | Temps de rafale | +-----------------+-----------------+-----------------+ | P1 | 0 | 8 | +-----------------+-----------------+-----------------+ | P2 | 1 | 4 | +-----------------+-----------------+-----------------+ | P3 | 2 | 9 | +-----------------+-----------------+-----------------+ | P4 | 3 | 5 | +-----------------+-----------------+-----------------+
Temps de rotation = Temps fin d’exécution – Temps d’arrivée
Temps d’attente = Temps de rotation – Temps de rafale
+-----------+-----------------+-------------------+ | Processus | Temps d'attente | Temps de rotation | +-----------+-----------------+-------------------+ | P1 | 0 | 8 – 0 = 8 | +-----------+-----------------+-------------------+ | P2 | 8 – 1 = 7 | 12 – 1 = 11 | +-----------+-----------------+-------------------+ | P3 | 12 – 2 = 10 | 21 – 2 = 19 | +-----------+-----------------+-------------------+ | P4 | 21 – 3 = 18 | 26 – 3 = 23 | +-----------+-----------------+-------------------+
Temps d'attente total = 0 + 7 + 10 + 18 = 35 ms
Temps moyen d'attente = (Temps d'attente total) / (Nombre total de processus)
= 35 / 4
= 8.75 ms
Temps de rotation total = 8 + 11 + 19 + 23 = 61 ms
Temps moyen de rotation = (Temps de rotation total) / (Nombre total de processus)
= 61 / 4
= 15.25 ms
Débit = 4 jobs/26 sec = 0.15385 jobs/sec
Exercice 2: Shortest Job First (SJF)
Rappel: Dans l’ordonnancement SJF
- Les processus qui ont le temps d’exécution le plus court sont ordonnancés en premier.
- Si deux processus ont le même temps de rafale, l’algorithme FCFS est utilisé pour les départager.
- Il s’agit d’un algorithme d’ordonnancement non préemptif et préemptif.
- La meilleure approche pour minimiser le temps d’attente.
- Facile à mettre en œuvre dans les systèmes de traitement par lots où le temps CPU nécessaire est connu à l’avance.
- Impossible à mettre en œuvre dans les systèmes interactifs où le temps CPU requis n’est pas connu.
- Le processeur doit connaître à l’avance la durée du processus.
- Le mode préemptif de SJF est appelé SRTF.
2.1) Considérons les processus suivants P1, P2, P3, P4, P5 arrive pour être exécuté, avec un temps de rafale (temps d’exécution de l’unité centrale). Dessinez l’ordre d’exécution des processus à l’aide d’un diagramme de Gantt (ligne temporelle) pour la politique d’ordonnancement SJF non préemptive, et calculez le temps d’attente moyen et le temps moyen de rotation.
+-----------------+-----------------+-----------------+ | ID du processus | Temps d'arrivée | Temps de rafale | +-----------------+-----------------+-----------------+ | P1 | 3 | 1 | +-----------------+-----------------+-----------------+ | P2 | 1 | 4 | +-----------------+-----------------+-----------------+ | P3 | 4 | 2 | +-----------------+-----------------+-----------------+ | P4 | 0 | 6 | +-----------------+-----------------+-----------------+ | P5 | 2 | 3 | +-----------------+-----------------+-----------------+
Maintenant, on sait que:
Temps de rotation = Temps fin d’exécution – Temps d’arrivée
Temps d’attente = Temps de rotation – Temps de rafale
+-----------+-----------------+-------------------+ | Processus | Temps d'attente | Temps de rotation | +-----------+-----------------+-------------------+ | P1 | 4 – 1 = 3 | 7 – 3 = 4 | +-----------+-----------------+-------------------+ | P2 | 15 – 4 = 11 | 16 – 1 = 15 | +-----------+-----------------+-------------------+ | P3 | 5 – 2 = 3 | 9 – 4 = 5 | +-----------+-----------------+-------------------+ | P4 | 6 – 6 = 0 | 6 – 0 = 6 | +-----------+-----------------+-------------------+ | P5 | 10 – 3 = 7 | 12 – 2 = 10 | +-----------+-----------------+-------------------+
Temps moyen d'attente = (Temps d'attente total) / (Nombre total de processus)
= (3 + 11 + 3 + 0 + 7) / 5
= 24 / 5
= 4.8 unités
Temps moyen de rotation = (Temps de rotation total) / (Nombre total de processus)
= (4 + 15 + 5 + 6 + 10) / 5
= 40 / 5
= 8 unités
2.2) Considérons les processus suivants P1, P2, P3, P4, P5 arrive pour être exécuté, avec un temps de rafale (temps d’exécution de l’unité centrale). Dessinez l’ordre d’exécution des processus à l’aide d’un diagramme de Gantt (ligne temporelle) pour la politique d’ordonnancement SJF préemptive, et calculez le temps d’attente moyen et le temps moyen de rotation.
+-----------------+-----------------+-----------------+ | ID du processus | Temps d'arrivée | Temps de rafale | +-----------------+-----------------+-----------------+ | P1 | 3 | 1 | +-----------------+-----------------+-----------------+ | P2 | 1 | 4 | +-----------------+-----------------+-----------------+ | P3 | 4 | 2 | +-----------------+-----------------+-----------------+ | P4 | 0 | 6 | +-----------------+-----------------+-----------------+ | P5 | 2 | 3 | +-----------------+-----------------+-----------------+
Maintenant, on sait que:
Temps de rotation = Temps fin d’exécution – Temps d’arrivée
Temps d’attente = Temps de rotation – Temps de rafale
+-----------+-----------------+-------------------+ | Processus | Temps d'attente | Temps de rotation | +-----------+-----------------+-------------------+ | P1 | 1 – 1 = 0 | 4 – 3 = 1 | +-----------+-----------------+-------------------+ | P2 | 5 – 4 = 1 | 6 – 1 = 5 | +-----------+-----------------+-------------------+ | P3 | 4 – 2 = 2 | 8 – 4 = 4 | +-----------+-----------------+-------------------+ | P4 | 16 – 6 = 10 | 16 – 0 = 16 | +-----------+-----------------+-------------------+ | P5 | 9 – 3 = 6 | 11 – 2 = 9 | +-----------+-----------------+-------------------+
Temps moyen d'attente = (Temps d'attente total) / (Nombre total de processus)
= (0 + 1 + 2 + 10 + 6) / 5
= 19 / 5
= 3.8 unités
Temps moyen de rotation = (Temps de rotation total) / (Nombre total de processus)
= (1 + 5 + 4 + 16 + 9) / 5
= 35 / 5
= 7 unités
2.3) Considérons les processus suivants P1, P2, P3, P4, P5, P6 arrive pour être exécuté, avec un temps de rafale (temps d’exécution de l’unité centrale). Dessinez l’ordre d’exécution des processus à l’aide d’un diagramme de Gantt (ligne temporelle) pour la politique d’ordonnancement SRTF (Shortest Remaining Time First), et calculez le temps d’attente moyen et le temps moyen de rotation.
+-----------------+-----------------+-----------------+ | ID du processus | Temps d'arrivée | Temps de rafale | +-----------------+-----------------+-----------------+ | P1 | 0 | 7 | +-----------------+-----------------+-----------------+ | P2 | 1 | 5 | +-----------------+-----------------+-----------------+ | P3 | 2 | 3 | +-----------------+-----------------+-----------------+ | P4 | 3 | 1 | +-----------------+-----------------+-----------------+ | P5 | 4 | 2 | +-----------------+-----------------+-----------------+ | P6 | 5 | 1 | +-----------------+-----------------+-----------------+
Maintenant, on sait que:
Temps de rotation = Temps fin d’exécution – Temps d’arrivée
Temps d’attente = Temps de rotation – Temps de rafale
+-----------+-----------------+-------------------+ | Processus | Temps d'attente | Temps de rotation | +-----------+-----------------+-------------------+ | P1 | 19 – 7 = 12 | 19 – 0 = 19 | +-----------+-----------------+-------------------+ | P2 | 12 – 5 = 7 | 13 – 1 = 12 | +-----------+-----------------+-------------------+ | P3 | 4 – 3 = 1 | 6 – 2 = 4 | +-----------+-----------------+-------------------+ | P4 | 1 – 1 = 0 | 4 – 3 = 1 | +-----------+-----------------+-------------------+ | P5 | 5 – 2 = 3 | 9 – 4 = 5 | +-----------+-----------------+-------------------+ | P6 | 2 – 1 = 1 | 7 – 5 = 2 | +-----------+-----------------+-------------------+
Temps moyen d'attente = (Temps d'attente total) / (Nombre total de processus)
= (12 + 7 + 1 + 0 + 3 + 1) / 6
= 24 / 6
= 4 unités
Temps moyen de rotation = (Temps de rotation total) / (Nombre total de processus)
= (19 + 12 + 4 + 1 + 5 + 2) / 6
= 43 / 6
= 7.17 unités
2.4) Considérons les processus suivants P1, P2, P3 arrive pour être exécuté, avec un temps de rafale (temps d’exécution de l’unité centrale). Dessinez l’ordre d’exécution des processus à l’aide d’un diagramme de Gantt (ligne temporelle) pour la politique d’ordonnancement SRTF (Shortest Remaining Time First), et calculez le temps d’attente moyen et le temps moyen de rotation.
+-----------------+-----------------+-----------------+ | ID du processus | Temps d'arrivée | Temps de rafale | +-----------------+-----------------+-----------------+ | P1 | 0 | 9 | +-----------------+-----------------+-----------------+ | P2 | 1 | 4 | +-----------------+-----------------+-----------------+ | P3 | 2 | 9 | +-----------------+-----------------+-----------------+
Maintenant, on sait que:
Temps de rotation = Temps fin d’exécution – Temps d’arrivée
Temps d’attente = Temps de rotation – Temps de rafale
+-----------+-----------------+-------------------+ | Processus | Temps d'attente | Temps de rotation | +-----------+-----------------+-------------------+ | P1 | 13 – 9 = 4 | 13 – 0 = 13 | +-----------+-----------------+-------------------+ | P2 | 4 – 4 = 0 | 5 – 1 = 4 | +-----------+-----------------+-------------------+ | P3 | 20 – 9 = 11 | 22- 2 = 20 | +-----------+-----------------+-------------------+
Temps moyen d'attente = (Temps d'attente total) / (Nombre total de processus)
= (4 + 0 + 11) / 3
= 15 / 3
= 5 unités
Temps moyen de rotation = (Temps de rotation total) / (Nombre total de processus)
= (13 + 4 + 20) / 3
= 37 / 3
= 12.33 unités
2.5) Considérons les processus suivants P1, P2, P3, P4 arrive pour être exécuté, avec un temps de rafale (temps d’exécution de l’unité centrale). Dessinez l’ordre d’exécution des processus à l’aide d’un diagramme de Gantt (ligne temporelle) pour la politique d’ordonnancement SRTF (Shortest Remaining Time First), et calculez le temps d’attente du processus P2.
+-----------------+-----------------+-----------------+ | ID du processus | Temps d'arrivée | Temps de rafale | +-----------------+-----------------+-----------------+ | P1 | 0 | 20 | +-----------------+-----------------+-----------------+ | P2 | 15 | 25 | +-----------------+-----------------+-----------------+ | P3 | 30 | 10 | +-----------------+-----------------+-----------------+ | P4 | 45 | 15 | +-----------------+-----------------+-----------------+
Maintenant, on sait que:
Temps de rotation = Temps fin d’exécution – Temps d’arrivée
Temps d’attente = Temps de rotation – Temps de rafale
Donc:
Temps moyen d’attente du processus P2 = 55 – 15 = 40 unités
Temps moyen de rotation du processus P2 = 40 – 25 = 15 unités
- Exercice Corrigé Ordonnancement Des Processus – Partie 1
- Exercice Corrigé Ordonnancement Des Processus – Partie 2
- Exercice Corrigé Ordonnancement Des Processus – Partie 3
- Exercice Corrigé Ordonnancement Des Processus – Partie 4
- Exercice Corrigé Ordonnancement Des Processus – Partie 5
- Exercice Corrigé Système d’Exploitation Linux – Partie 1
- Exercice Corrigé Système d’Exploitation Linux – Partie 2
- Exercice Corrigé Système d’Exploitation Linux – Partie 3
- Exercice Corrigé Gestion Des Processus Linux – Partie 1
- Exercice Corrigé Gestion Des Processus Linux – Partie 2
- Exercice Corrigé Gestion Des Processus Linux – Partie 3
- Exercice Corrigé Gestion Des Processus Linux – Partie 4
- Exercice Corrigé Gestion Des Processus Linux – Partie 5
- Exercice Corrigé Gestion Des Processus Linux – Partie 6
- Exercice Corrigé Gestion Des Processus Linux – Partie 7
- Exercice Corrigé Gestion Des Processus Linux – Partie 8
- Exercice Corrigé Gestion Des Processus Linux – Partie 9
- Exercice Corrigé Gestion Des Processus Linux – Partie 10
- Exercice Corrigé – Gestion de la mémoire – Partie 1
- Exercice Corrigé – Gestion de la mémoire – Partie 2
- Exercice Corrigé – Gestion de la mémoire – Partie 3
- Questions techniques sur MYSQL
- QCM MySQL Corrigé – Optimisation de requêtes
- QCM Base de données avec correction
- QCM sur PHP
- QCM Symfony
- QCM AngularJS
- QCM React
- QCM HTML / CSS
- QCM Java – Programmation Orientée Objet
- QCM Python
- QCM Cloud Computing
- QCM Framework Spring
- QCM Javascript
- QCM jQuery
- QCM Oracle
- QCM sur GIT – Gestionnaire de version
- QCM Linux – Gestion de processus
- QCM Réseau
- QCM Architecture des ordinateurs
- QCM Securité informatique
- QCM En Informatique Générale
- QCM en C
- QCM en C#
- QCM sur l'algorithmique
- QCM Word
- QCM Excel
- QCM PowerPoint
- QCM Access
