Archives par mot-clé : cours

Théorie des Systèmes d’exploitation

Introduction

Un système d’exploitation désigne un ensemble de programmes qui réalisent l’interface entre le matériel et l’utilisateur. Ils ont été introduit pour résoudre les problemes posés par les premiers ordinateurs.

En général, une architecture matérielle peut être de la manière suivante:

Schéma simple d'une architecture matérielle
Figure 1. Schéma simple d’une architecture matérielle

On peut distinguer :

  • Un OS est la partie du logiciel qui fonctionne en mode noyau. Il est donc protégé par le matériel contre toute manipulation. Ce mode est également appelé mode superviseur.
  • Les autres programmes fonctionnent en mode utilisateur.

Historique

Les OS sont liés aux architectures matériels des ordinateurs. On peut noter 4 générations d’évolution:

  • 1945-1955: Les tubes à vide. Construction des premiers ordinateurs à tube électronique.Quelques caractéristiques:
    • ~ 20 000 tubes par ordinateur
    • Poids: 20 tonnes
    • Surface: 160M²

    Ses marchines n’ont pas de mémoire et n’exécute qu’un programme à la fois. Il n’y a donc pas de système d’exploitation. Les programmes étaient en langue machine et chargés dans les registres bit par bit. => Travail d’experts.

  • 1955-1965: Génération Transistor. Introduction du transistor (1950) permet de voir apparaître pour la première fois la séparation entre concepteur et construction de programmes. Ses machines étaient enfermées dans des pièces où l’air était conditionnée. Les programmes étaient écris en fortran ou en assembleur. Ils étaient introduit dans le système par des cartes perforées. Devant la perte de temps et le coût des équipements, on a lancé le batch processing. Ce processus consistait à regrouper et traiter des travaux similaires à la suite. Ainsi tous les programmes en fortran furent regroupés par lots.
  • 1965-1980: Troisième génération, circuits intégrés et multi-programmation. Les circuits intégrés coûtent moins cher à produire, les modèles évoluent rapidement. On voit grandir les problèmes de compatibilitéet d’opérabilité. L’arrivée du disque dur par contre permet de grandes avancées, puisqu’elle permet le recouvrement de phases de calculs d’un programme avec des phases d’Entrée/Sortie d’un autre programme. C’est la naissance du concept de multi-programmeation. Ce concept permet de rétablir l’intéropérabilité, car plusieurs personnes peuvent travailler simultanément, chacun sur un terminal. Le processeur leur est attribué un … de temps. C’est dans cet esprit qu’a été inventé MULTICS.
  • 1980-1990: Miniaturisation Introduction des micro-ordinateurs. Ordinateurs caractérisés par des systèmes interactifs. Cela introduit d’importantes possibilités graphiques. MS-DOS est utilisé sur des IBM PC. En parallèle, on assiste au développement des systèmes multi-processeurs. Les réseaux se développent, tels que Arbalète, SNA, Transpac, Ethernet,… Ces machines on été gérées par des OS adaptés à leur problèmes.

Interface entre le mode User et le Matériel au moyen d'un mode noyau
Figure 2. Interface entre le mode User et le Matériel au moyen d’un mode noyau

Introduction

On distingue deux types de systèmes d’exploitation:

  • Centralisé
  • Réparti

Un système d’exploitation réparti est un ensemble de sites faiblements couplés. Un site est un ensemble de ressources physiques fortements couplées tel que le processeur, la mémoire, les périphériques. Les sites du système réparti sont dit faiblement couplés dans le sens où leur interaction repose sur l’utilisation d’un support de communication et non pas sur l’utilisation de mémoire commune.

L’exploitation d’un système réparti repose essentiellement sur la disponibilté des moyens de communication entre sites. On voit donc apparaître un autre concept: les Protocoles de communication. Ces protocoles permettent à des entités logiciels d’échanger des informations sous formes de messages. L’utilisation de ces protocoles de communication peut être réalisée à différents niveaux. Le niveau du système où les protocoles sont utilisés détermine la vision que l’utilisateur a du système réparti. Chronologiquement, on les situe comme suit:

  • Les protocoles de communication ne sont utilisés que par des applications particulières dédiées à la mise en oeuvre de certains service bien identifiés: les transferts de fichiers, la connexion a distances d’un système. C’est l’approche la plus ancienne. Elle a permis la mise en oeuvre de services répartis sur des OS existants et hétérogènes.
  • Les protocoles de communication sont utilisés au sein du noyau de l’OS pour étendre la répartition de certaines des fonctions du noyau. Cette approche qui permet d’étendre les fonctionnalités existantes sans les modifier de façon massive aa été appliquée majoritairement au système UNIX, en particulier dans le cadre de l’extension du système de fichiers à la répartition.
  • Les protocoles de communication sont utilisés au coeur de l’OS. Tous les objets de l’OS (processus, fichiers,…) sont manipulables de façon répartie. Cette approche est celle de l’OS proprement réparti.

Les systèmes répartis sont caractérisés par un noyau. On cite deux noyaux :

  • Chorus par Chorus System: Ces concepts fondamentaux sont inspiré des travaux de l’INRI entre 1980 et 1986. On voit un noyau de système temps réel portable, un ensemble des systèmes d’exploitation construit de façon modulaire par rapport au noyau. Ce noyau est disponible sur toute une gamme de matériels.
    Note
    Chorus a été adopté comme OS par un certain nombre de constructeurs, en particulier les télécommunications et les approches temps réel.
  • Mach développé par une société américaine: Carmegie Mellon.Les concepts fondamentaux des noyaux Mach sont inspirés des résultats des expérimentation des systèmes Rig et Accent (1980 – 1987). Contrairement à Chorus, Mach n’a pas été disponible en tant que tel, mais sur ses concepteurs ont préféré l’intégrer au noyau UNIX BSD 4.3. Il est disponible sur un ensemble d’architectures matérielles différentes, en particulier sur des architectures à processeur fortement couplé. Mach a été développé par des industriels de …

Un noyau tel que Mach fourni un ensemble de fonctions génériques strictement nécessaires à la mise en oeuvre de l’application ou des services répartis. On appelle ca la notion de micro-noyau:

  • Cadencement et contrôle d’exécution des processus.
  • Communication entre processus
  • Gestion de mémoire virtuelle

Ces fonctions reposent sur un ensemble réduits de concepts simples: les objets gérés par le noyau sont des objets élémentaires. Les sous-systèmes construisent à leur tour des objets plus complexes par assemblage d’objets élémentaires. Les objets élémentaires gérés par Mach et Chorus sont relativement similaires.

Les objets élémentaires

Les systèmes d’exploitations répartis sont caractérisés par la notion de micro-noyau et par des objets élémentaires.

Unité de Structuration

Dans un premier lieu, le noyau définit une entité de structuration du système qu’on appelle Acteur chez Chorus, et Tâche (Task) chez Mach. L’acteur est l’unité d’allocation de ressouces. Il fourni un espace d’adessage protégé ainsi que des accès à des ressources système (les objets de communication, les objets mémoire…).

Unité d’Exécution

L’activité appelle aussi Thread est l’unité d’exécution. Une activité est un processus séquentiel. Elle est caractérisée par un contexte d’exécution. Une activité est attachée à un acteur qui défini son environnement d’exécution. Plusieurs activités peuvent patager l’environnement offert par un acteur.

Les activités d’un environnement accèdent librement à toutes les ressources détenus par l’acteur.

Les activités sont cadencées par le noyau comme des entités indépendantes. Elles peuvent donc s’exécuter en parallèle sur les différents processus d’un multi-processeur symétrique (il existe des systèmes multi-processeurs symétriques et asymétriques). Les activités d’un acteur partagent un même espace d’adressage.

Communication

De ce fait, les activités peuvent se synchroniser et communiquer en utilisant le partage de mémoire.

Remarque
Une des caractéristiques des noyaux tel que Chorus et Mach est d’offrir un mécanisme de communication uniforme indépendamment de la localisation de l’activité. Il est appelé IPC: Inter Processus Communication.

Les communications entre activités sont mises en oeuvre au moyen d’une interface uniforme. Quelle que soit la localisation des activités communicantes, elles prennent la forme de messages. Les activités ne communiquent pas directement entre elles, mais utilisent des objets spécifiques dédiés à la communication appelés Porte (ou Port).

Définition de Porte
Une porte est définie par un entier naturel positif ou nul permettant de distinguer une porte d’une autre d’un même acteur, et d’une file d’attente de messages.

La porte est LA ressource de communication bidirectionnelle. Elle est donc source et destination des messages. La porte source d’un message fourni en particulier un moyen d’identification de l’émeteur par le récepteur. A une porte est donc associé une queue de messages non consommés par les activités. Aux portes, sont associés également des droits d’utilisation (émission et réception). Le mode de gestion de ces droits diffère dans les deux systèmes mais un principe de conception commune est observable. Par exemple, le droit de réception sur une porte n’est à un instant donné attribué qu’à un seul acteur. Seules les activités attachées à ces acteurs peuvent consommer les messages destinés à cette porte. En revanche, le droit d’émission peut être partagé par de multiples émeteurs potentiels.

Définition de Message
Paquet d’informations, typé ou non typé.

Pour mettre en oeuvre le mécanisme de transmision de portes, on peut utiliser des messages typés: cela signifie que l’utilisateur décrit la structure du message lors de l’envoi permettant au noyau de retrouver les informations (portes). Un message est un ensemble de couples de la forme :

<type,données>

Lors de l’envoi et la réception de chaque message, le noyau interprète la description du message. Cette stratégie permet:

  • La mise en oeuvre des mécanismes de transmission de portes.
  • La prise en compte de la diversité de représentation de données entre sites.
  • Une grande généralité dans la définition du contenu d’un message.
Exemple 1.
On peut utiliser le message pour transporter une région de mémoire virtuelle. On peut même transporter un espace d’adressage entier.
Remarque
La mise en oeuvre de toutes ces caractéristiques représentent un facteur de coût important.

Objets Mémoire

Un acteur défini un espace d’adressage protégé. Un espace d’adressage appelé également contexte est constitué d’un ensemble de régions => Région définie par un ensemble d’adresses contigües.

Deux régions ne peuvent se recouvrir au sein d’un même espace d’adressage. Elles constituent des fenêtres d’accès aux objets mémoire (segments).

Un segment représente l’unité d’information en mémoire secondaire. Lorsqu’une région fournit un moyen d’accès à un segment, le segment devient protégé (mapped) sur la région.

Projection de Segments protégés (mappés)
Figure 3. Projection de Segments protégés (mappés)

Tout accès en lecture ou écriture par le processeur physique à une donnée représentée par l’une des adresses virtuelles définissant la région est logiquement équivalent à un accès à la donnée correspondante du segment. La région fournit donc un moyen d’accès transparent au segment. On peut voir qu’une région peut représenter la totalité d’un segment ou seulement une partie de segment.

Les droits d’accès sont associés aux régions. Différents fragments d’un segment peuvent être protégés différemment en projetant chacune d’elles sur une région différente.

Une portion d’un segment peut être projeté sur différentes régions. Ces régions pouvant être des régions d’espace d’adressage différents, c’est-à-dire des acteurs différents et peut être même des sites différents. L’accès à un segment peut être partagé.

Partage de Segment
Figure 4. Partage de Segment

Un segment accédé par un site est représenté par un nouvel objet: le cache. Il gère la mémoire physique du site utilisé pour le compte du segment à un instant donné.

Représentation d'un cache
Figure 5. Représentation d’un cache

Le rôle du noyau est de gérer les contextes, régions et caches. Les segments sont gérés par des serveurs externes appelés également gestionnaires de segments ou mappeur (pager). Ils sont responsables du stockage des segments. le noyau ne projette aucune supposition sur la sémantique associé à ce segment.

L’accès à un segment est la résultante d’une coopération entre noyau et mappeurs prenant la forme de transferts de données entre cache et segment. Ces transferts sont réalisés par des outils de communication offerts par le noyau (échange de messages entre portes).

Exercice
Développer et préciser le concept de mémoire virtuelle dans le noyau des systèmes distribués. (ex: le service de gestion mémoire est un composant essentiel du système. Son rôle est de supporter l’exécution de programmes indépendants ainsi que les transferts de données nécessaires à l’exécution de ce programme. Il gère des espaces d’adressage protégés (contextes) au sein desquels codes et données des programmes sont accessibles par les activités. De tels objets de mémoire ou segments sont projetés sous forme de régions dans les espaces d’adressage. Le service de gestion mémoire se décompose logiquement en deux grandes parties:

  • Création des espaces d’adressage ou contextes et mise en oeuvre de la projection des segments sous forme de régions de ces espaces.
  • Gestion des segments et de leur cache

Elements de Base

En 1960, les concepteurs du système d’exploitation MULTICS ont introduit le terme de processus comme une abstraction de l’activité du processeur. On veut exprimer par ceci qu’un fragment de code est en cours d’exécution bien qu’il ne progresse pas dans l’attente du microprocesseur physique.

Différences fondamentales

Programme

Un programme est une entité purement statique associée à la suite des instructions qui le composent.

Processus

Un processus est une entité purement dynamique (qui n’existe que dans la mémoire physique de l’ordinateur) associée à la suite des actions (correspondant aux instructions d’un programme) réalisé par un programme.

Remarque
La notion de processus nous éclaire et nous introduit dans le fonctionnement des systèmes multi-programmés. Un système est dit multiprogrammé lorsqu’il a l’aptitude d’exécuter sur un processeur ou plusieurs processeurs physiques une multitude de processus.

Etat d’un processus

En général, on définit un état comme étant un ensemble de couples de la forme:

<entité,valeur>

L’état d’un processus permet d’exprimer si un processus est:

  • réellement exécuté: dispose à cet instant de la ressource physique microprocesseur.
  • seulement pr à être exécuté: à cet instant, il dispose de l’ensemble des ressources nécessaires à sa complition sauf la ressource microprocesseur.
  • en attente de ressources autre que le microprocesseur: à cet instant, il peut attendre une réponse d’une opération d’entrée/sortie d’un organe physique.
  • dans un état bloqué: une certainre condition n’a pas pu être réalisée.

On distingue donc les états suivants:

<prêt, en exécution, en attente, bloqué, terminé, …>

Plus précisément, c’est le système d’exploitation qui détermine et modifie l’état d’un processus sous l’effet de la notion d’événements. On remarque donc un nouveau couple

<état, événement>
Exemple 2. Etat d’un processus
Une demande d’Entrée/Sortie peut faire passer un processus de l’état « en exécution » ) l’état « en attente »:

<exécution, evénement> <attente, événement>

Représentation interne d’un processus

Un processus est représenté par une structure de données appelée le bloc de contrôle processus ou BCP: Bloc Control Processus, c’est une table de la forme suivante:Schéma d'un BCP
Figure 6. Schéma d’un BCP

On peut trouver des informations relatives à la quantité de mémoire allouée au processus et des pointeurs vers cette mémoire. On peut trouver des informations qualitatives, le temps UC utilisé, le temps restant autorisé, on peut aussi trouver des informations concernant des opérations d’Entrée/Sortie du processus tel que les périphériques alloués, des opérations en attente de complition, des fichiers ouverts, des descripteurs de connexions réseaux, … On trouve également des informations sur les files d’attente où figure les processus.

Exemple 3.
A chaque fois qu’un processus tente d’accéder à une ressource convoitée par d’autres processus, il peut se trouver dans une file d’attente de cette ressource.

De manière générale, on peut dire avec précision que le BCP d’un processus doit contenir des informations qu’il faut sauvegarder pour permettre la reprise ultérieure de l’exécution du processus.

Exercice
Détailler l’ensemble des champs du BCP d’un processus Linux ainsi que les opérations d’exécution du processus.

Opérations d’un Processus

Un ensemble minimal d’opérations sur les processus est réalisé par le système d’exploitation:

  • Créer et Détruire
  • Mettre en attente et Réveiller
  • Suspendre et Reprendre
  • Changer de priorité
  • etc.

Créer

Un processus peut en créer un autre (c’est d’ailleurs le fonctionnement de la plupart des systèmes d’exploitations). Le premier processus est appelé processus père et le second processus fils. Le fils peut à son tour créer d’autres processus et en devient le père. Ces suites de création peuvent être représentée par un graphe orienté acyclique. La racine de cet arbre est le père de tous les autres processus.

Arbre des Processus
Figure 7. Arbre des Processus

Tous les processus zombie (qui n’ont plus de père) sont récupérés par la racine (le père de tous les processus). Ils sont encore présent dans la table des processus même s’ils n’ont plus aucunes ressources d’allouées, et qu’il ne font plus de tâches particulière.

Exemple 4.
dans le système UNIX, les nouveaux processus sont créés par l’appel système à une primitive du système appelée Fork. Le couple <fork,exec> permet d’exécuter en parallèle des programmes différents.
Exemple 5.

… id=fork(); // Retourne 0 au fils et le numéro du fils opéré if id=0 exec(Processus fils); else exec(Processus père);

Dans UNIX, les processus pères et fils ont des contextes mémoire séparés; un processus dans un système multithreadé, les threads partagent le même espace mémoire. Le processus fils à accès à toutes les ressources (ex: fichier ouvert par le processus père). En revanche la communication entre le père et le fils doit passer par l’intermédiaire d’un fichier ou une portion de la mémoire partagée.

Détruire

un processus fils se termine de différentes façons :

  • Il se termine normalement après exécution de sa dernière instruction.
  • Il exécute une instruction d’autodestruction comme par exemple la fonction EXIT d’UNIX.
  • Il es détruit par un autre processus comme par exemple le KILL d’UNIX.
Exercice
Ecrire un algorithme qui matérialise la fonction EXIT d’UNIX.
Entrée: Code de retour pour le processus parent. Sortie: Néant { ignorer tous les signaux; if(Moniteur du groupe de processus associé au terminal de contrôle) { envoyer un signal « Coupure de ligne » à tous les membres du groupe; mettre à zéro; } fermer tous les fichiers ouverts; //utilisation de la version Interne de Classe libérer le répertoire courant; //algorithme iput libérer le répertoire racine; libérer les régions, la mémoire associée au processus; écrire les informations statiques; rendre l’état du processus Zombie; affecter l’ID du processus du père e tous les processus fils au processus init; si un des fils est zombie, alors envoyer le signal « Mort d’un fils » à init; envoyer le signal « mort d’un fils » au processus parent; changement de contexte; }

Mettre en attente et réveiller

Lorsqu’un processus a besoin de ressources autres que l’UC (microprocesseur) pour poursuivre sa progression, il est placé par le système d’exploitation dans l’état « en attente. Lorsque plus tard, le système d’exploitation est en mesure de lui affecter les ressources demandées, le processus est mis dans l’état « prêt » signigiant que le processus disporse de toutes les ressources sauf l’UC.

Suspendre et Reprendre

La suspension est l’action qui amène un processus dans l’état suspendu. Précisément c’est un retrait momentané de ce processus. Lorsque la reprise intervient, le processus repasse dans l’état « prêt » ou « en attente ».

A tout processus on associe un diagramme d’état associé avec des événements permettant de passer d’un état à l’autre.

Changer de priorité

(engendre beaucoup de calculs). Changer la priorité d’un processus se fait en modifiant le champ correspondant dans son BCP. C’est une opération triviale, mais répercutée sur l’ordonnancement. Une priorité par défaut est attribuée à la naissance de chaque processus. Cela se solde toujours comme un appel système, le BCP n’est modifié que par le noyau. Le scheduler se chargera de reclaculer les priorités.

Note
Le système d’exploitation garantit à chaque processus d’accéder à des ressources. Cela nécessite de mettre en place un ordonnanceur, pour scheduler (ordonnancer) les différents processus, cette fonctionnalité est faite par plusieurs algorithmes.
Exercice
Tracer le graphe d’état en général des processus et celui d’UNIX System V


Figure 8. Diagramme d’Etats

Voici la liste complète des états d’un processus UNIX:

  • Le processus s’exécute en mode user
  • Le processus s’exécute en mode noyau
  • Le processus ne s’exécute pas mais est prêt à s’exécuter dès que le noyau le liberera
  • Le processus est endormi et réside en mémoire centrale
  • Le processus est prêt à s’exécuter mais le swapper (processus 0) doit transférer le processus en mémoire principale avant que le noya ne puisse le lire en vue de son exécution
  • Le processus est endormi et le swapper a transféré le processus en mémoire secondaire pour obtenir de la place en mémoire centrale
  • Le processus est passé du mode noyau au mode user, mais le noyau l’a préempté (retiré) et à effectué un changement de contexte pour élire un autre processus
  • Le processus est nouvellement créé et se trouve dans un état de transition: le processus existe mais n’est pas prêt en vue de son exécution ni endormi. En quelque sorte c’est l’état de tous les processus sauf le swapper
  • Le processus a exécuté l’appel EXIT et est dans l’état Zombie. Dans ce das, le processus n’existe plus, mais laisse un enregistrement contenant le code de retour et quelques statistiques de temps qui est à rassembler par son processus parent. C’est l’état final d’un processus

Diagramme de ces états
Figure 9. Diagramme de ces Etats

Exercice
Faire un schéma explicatif de l’image d’un fichier exécutable.

Format d'un fichier exécutable UNIX
Figure 10. Format d’un fichier exécutable UNIX

Le Magic Number est un entier appelé a_magic dont l’objectif est d’indiquer le type du fichier exécutable: paginé, partageable, texte de données dans le même segment, texte de données séparées, etc. Il vient ensuite la taille du texte (dans l’entête), ensuite les données initialisées puis non initialisées et la table des symbôles; que l’on appelle également: a_texta_dataa_bssa_syms. Cette section ne contient pas de données au départ, elle sera plutôt dynamiquement construite à l’aide des différents appels systèmes tels que sbrk(). Quant à la table des symbôles, elle peut apparaître ou non, on appelle cela à ce moment des fichiers strippés.

Schéma d'un espace virtuel d'un processus dans l'espace user
Figure 11. Schéma d’un espace virtuel d’un processus dans l’espace user

Schéma d'un contexte de processus
Figure 12. Schéma d’un contexte de processus

Un processus peut augmenter ou diminuer la taille de sa région de données, en utilisant par exemple sbrk()

Exercice
Donner un schéma d’algorithme de sbrk()
Pré: n: entier>0 Debut verrouiller la région des données des processus; Si(Taille de la région doit augmenter) alors Debut déverrouiller(la région des données); return(Erreur); Fin changer la taille de la région en appelant: growreg; initialisation à zéro du nouvel espace de données; déverrouiller(la région de données des processus); Fin Post: Ancienne valeur

Un processus peut être vu comme une succession d’étapes de calculs et d’entrées/sorties. c’est pour cela qu’on dit que la vie d’un processus se décompose en une alternance de périodes d’utilisation de l’UC et de périodes d’accomplissement d’opérations d’entrées/sorties. On appelle la première période la phase de calculs et la seconde, la phase d’entrées/sorties.

Expérimentalement, on a montré que la grande majorité des processus ont des phases de calculs extrêmement courtes alternant aec des périodes d’entrées/sorties beaucoup plus longues.

Exemple 6

  • Les systèmes interactifs utilisent plus longuement les entrées/sorties
  • les systèmes scientifiques utilisent très peu les opération d’entrées/sorties

Les Ressources

Définition

On appelle ressource tout élément qui contribue à la progression des processus (tout objet participant à la complition d’un processus).

Fonctionnement et types

A une ressource sont associées des procédures d’accès qui permettent de la manipuler et les règles d’utilisation qui constituent les conditions d’emploi. (ex: les axiomes).

Il existe deux formes de ressources:

  • Ressources Matérielles tel que l’UC, les mémoires, les organes d’entrée/sortie,…
  • Ressources Logiques tel qu’un compilateur, un éditeur, un processus, un programme,… (tout ce qui n’est pas ressource matérielle)

Classes de Ressources

La multiplicité des ressources permet de les classifier, c’est à dire metre sous forme de famille de ressources.

Définition

On appelle Classe de ressources un couple

<nom commun,procédure>

Le nom commun permet de regrouper l’ensemble des éléments associés à la ressource, la procédure (ou opération) est l’ensemble des fonctions applicables au premier élément du couple.

Remarque
La classification des ressources dépend essentiellement du contexte.
Exemple 7
Une imprimante matricielle et une imprimante laser appartiennent ou n’appartiennent pas à la même classe selon que les modes d’accès sont identiques ou non.

Les opérations associées aux ressources d’un système d’exploitation sont les suivantes:

  • Demandées
  • Allouées
  • Utilisées
  • Libérées

Une ressource donnée d’un système d’exploitation possède des états internes qui peuvent être modifiés par leur utilisateur à travers l’ensemble des services associés. Si l’état d’une ressource est susceptible d’être modifié, il doit être réinitialisé après chaque libération. Le système d’exploitation contrôle les utilisations de toutes les ressources à l’aide d’une table indiquant les éléments suivants: Ressource disponible ou non, allouée ou non (cf Ensemble des élements). A chaque objet ressource est associé une file d’attente contenant les BCP (Figure 6, « Schéma d’un BCP ») des processus qui l’attendent.

Il arrive parfois d’autoriser des utilisations supplémentaires, comme « réquisitionner », c’est-à-dire que lorsqu’une ressource R est allouée et qu’une demande émanat d’un processus survient, et en particulier d’un processus prioritaire, alors on retire la ressource au processus en cours et on l’attribue au processus prioritaire demandeur.

Dans le cas de réquisition de la ressource, son état doit être sauvegardé.

Généralité

Ordonnancement

Dans un système multiprogrammé, l’ordonnanceur qu’on appelle un scheduler est le processus qui définit l’ordre dans lequel les processus prêts acquièrent le processeur central et la durée pendant laquelle ils l’utilisent.

Le terme d’ordonnanceur a un sens plus large. Il désigne un processus sous l’autorité duquel d’autres processus ont accès à des ressources. Ces ressources sont les mémoires centrales et auxiliaires tels que les disques, les bandes ou tout autre type de périphérique.

File d’attente

Lorsque plusieurs processus demandent l’allocation d’une ressource qui n’est pas disponible mais indispensable à leur progression, ce processus doit attendre. La seule façon de procéder, est de gérer une file d’attente. Lorsque la ressource redevient disponible, le système d’exploitation doit être capable de sélectionner un des processus en attente et de lui affecter la ressource attendue.

Type d’ordonnanceur

Il existe plusieurs types d’ordonnanceurs:

Ordonnanceur à long terme (JOB SCHEDULER)

Sa mission est de déterminer si un processus utilisateur qui le demande peut entrer dans le système. (cette décision dépend d’informations sur les performances du système à l’instant considéré).

Ordonnanceur de l’Unité Centrale (CPU SCHEDULER)

Sa mission est de choisir dans la file d’attente associée à l’Unité Centrale le processus à qui sera allouée le CPU.

Remarque
Le CPU SCHEDULER est activé au bout d’une période maximum qui correspond à la durée de la phase de calcul du processus précédent. Cette période en question a un ordre de grandeur de 10ms.
Ordonnanceur à moyen terme (MEDIUM TERME SCHEDULER)

Sa mission est de déterminer quel processus rangé temporairement sur le disque peut accéder à la mémoire centrale et inversement. c’est aussi un scheduler qui fixe l’accès au disque.

Mécanismes de base

Deux mécanismes fondamentaux sont implémentés au niveau matériel:

  • La commutation du mot d’état
  • Les interruptions

Les registres de l’unité centrale

L’exécution d’une instruction peut provoquer le transfert de données entre l’unité centrale et la mémoire centrale. Deux registres servent à gérer ces communications:

  • Un registre d’adresses qui indique l’adresse de la cellule vers laquelle ou de laquelle a lieu un transfert de données.
  • Un registre de données qui contient la valeur transferée.

L’Unité centrale contient des registres qui contiennent certaines informations sur son propre état.

Exemple
Active ou non active; mode système ou mode utilisateur;…

Les registres de l’Unité Centrale peuvent aussi contenir des informations sur les processus en cours d’exécution.

Exemple
Zone mémoire accessible et droits d’accès; niveau de droits d’accès; …

L’ensemble de tous ces registres est appelé le mot d’état ou PSW: Processus Status Word.

A tout instant un processus est donc entièrement caractérisé par:

  • Le programme sousjacent et ses données qu’on appelle son contexte en mémoire.
  • Sa valeur du mot d’état qu’on appelle « contexte d’unité centrale ».

Quelques définitions

Notion d’activité

On appelle activité la résultante de l’exécution ininterrompu d’une procédure unique (sachant qu’un programme séquentiel, élément d’un processus, est constitué d’une procédure qui s’appelle mutuellement.) Une procédure est caractérisée par un segment de procédure distinct et un segment de données. Ce dernier peut être propre à la procédure.

Notion de contexte

On appelle contexte d’activité, l’ensemble d’informations mis à la disposition du processeur au cours de cette activité. Un contexte comprend donc un contexte de processus tel que les registres […] et un contexte en mémoire tel que les registres de segments, instructions ou données.

Lors du passage d’une activité à une autre, on peut assister à une commutation de contexte.

Commutation du mot d’état

Dans le cas où plusieurs programmes se trouvent en mémoire centrale prêts à être exécutés, on va procéder en partageant l’Unité Centrale entre ces différentes activités, c’est-à-dire exécuter une partie du premier programme, puis exécuter une partie du second programme, etc.

Laisser s’exécuter d’autres processus que le processus courant modifie fortement le contexte de l’unité centrale, en particulier les registres du microprocesseur. Il est donc indispensable de sauvegarder ces contextes susceptibles d’être modifiés. C’est la raison pour laquelle l’opération de commutation de contexte est considérée comme mécanisme de base. Cette opération de commutation de contexte permet l’exécution de manière atomique (c’est à dire sans interruption).

  • La sauvegarde du PSW dans une zone précise
  • Le chargement d’une nouvelle valeur à partir d’une zone précise

Une opération de commutation du contexte du mot d’état provoque l’exécution d’un nouveau processus car le compteur ordinal fait parti du mot d’état (Le nouveau processus peut être le processus interrompu ou un autre).

Remarque
Si la sauvegarde du mot d’état n’est pas suffisante (c’est-à-dire partielle), il est facile de faire accomplir cette tâche par le nouveau processus come une première activité.

Interruption

Une interruption est une commutation de contexte (de mot d’état) provoquée par un signal généré par le matériel (donc indépendant de l’exécution de l’instruction en cours). Le signal est donc lui même la conséquence d’un événement. Physiquement, c’est un signal au processeur interrompu.

Remarque
Il arrive parfois que le signal peut être interne au processus et donc résultant de son exécution, ou bien extérieur et donc indépendant de son exécution.
Remarque 2
Le signal provoquant une interruption provoque le changement d’état d’un indicateur consulté au cours de chaque instruction et peut être un signal provenant d’un autre processeur, d’un dispositif d’entrée/sortie, d’un organe externe, d’une action d’un opérateur, ou plus généralement de tous les processus physiques extérieurs au processeur interrompu.
Remarque 3
La conséquence d’une interruption est la suspension de l’activité d’un processus dès le premier point interruptible du programme en cours d’exécution et à exécuter un programme prédéfini.
Exemple
On peut distinguer les éléments suivants

  • L’événement peut concerner un autre processus
  • L’événement peut concerner un élément d’entrée/sortie
  • L’événement peut concerner un utilisateur
  • L’événement peut concerner tout signal extérieur tel qu’un capteur

Le système consulte régulièrement un indicateur qui peut être modifié par le signal d’interruption pour déterminer la cause de l’interruption. Il s’agit en général de plusieurs bits du mot d’état qui constitue le vecteur d’interruption. A chaque cause est associée un niveau d’interruption. On distingue au moins trois niveaux d’interruption:

  • Les Interruptions externes dont la cause est extérieure au déroulement du processus
  • Les déroutements qui proviennent d’une situation exceptionnelle ou d’une erreur liée à l’instruction en cours (Division par zéro…)
  • Les appels au système (SuperVisor Call) lorsque l’instruction d’un programme réalise explicitement l’appel d’une fonction du système d’exploitation (demande d’une opération d’Entrée/Sortie…)