IFT2245 ? Systèmes d'exploitation Cours 1, mercredi 6 septembre ...

exec nom de programme / adresse mémoire. Job typique: loop .... Process classique: - fork(): tous les registres. Process ..... Retour sur l'examen ... Cours 15  ...


un extrait du document



IFT2245 – Systèmes d'exploitation


Cours 1, mercredi 6 septembre 2006

Définition (Système d'exploitation): Une couche de logiciel qui gère le matériel afin d'offrir les services requis par les autres programmes.









OS = logiciel gratuit livré avec le matériel (avant Gates)

OS primitifs: CPM – micros à mémoire de 4ko (associés à des disquettes)
OS modernes: (associés à un CD de 650 Mo)


Ordinateur:

mais on doit garder à l'esprit que le BUS est très
complexe ...

Autres exemples: un floppy: 16 commandes
registres
13 paramètres (lire)
réponse: 23 params.
Objectifs fondamentaux des SE:
1. Ergonomie: Donner une vision plus simple de l'ordinateur. (Functionality)
2. Efficacité: Permettre de fonctionner plus vite. (Gérer la capacité de parallélisme des composantes de l'ordi.)
( + débit [Gestion efficace des ressources]
( - temps de passage
3. Évolutif: (Par exemple, les disquettes sont passé de 256Ko à 1Mo à 1Go à 100Go
[problèmes d'adressage... 18bits 20bits 30bits 36bits]

Fonctions principales (modules):
1. Gestion des périphériques (drivers / pilotes)
- Interruptions
2. Gestion de fichiers. (espace secondaire)
- Gestion de l'espace
- Correspondance nom(adresse
- Sécurité
3. Gestion de la mémoire centrale.
- Gestion de l'espace
- Sécurité
4. Interface usager
- Fenêtres
- Shell [enocre très utile pour scripts]
5. Gestion du parallélisme
- Process
6. Communication entre process
- Télécommunication / Réseaux
7. Protection et partage (verouillage de fichier...)
- bits de protection
- Comptes usagers
8. Performance
- comptabilité
- mesure
9. Utilitaires
- librairies mathématiques
- compilateur
- assembleur
- éditeur de liens
- date/time
10. Démarrage


Démo 1, jeudi 7 septembre 2006

David – 3332 – Mercredi 10h@12h


Cours 2, lundi 11 septembre 2006

1950: eniac, 200 caractères
1960: ibm 1401, ordinateur commercial, premier à utiliser des transistor, 16 kilooctets
1984: mac

Flop: Floating point operation

Année195019601985
3M (1mega op/pixel/octet)2000NomEniacIBM1401NextPC typiqueMémoire200 octets8-16 Ko1Mo100MoCPU (ULA)5000 add/s et 400 mult. ou div./s1Mflops1GHzDisquenon10Mo
100ms + accès100Go
10msModemnon300bauds (50octets/s)10Mb/s (Ethernet)
Éléments physiques: Impression (1200 lignes/min ( 20 pages/min) approximativement la même chose!

Disque + accès: 100ms ( 10ms peu de différence...

Donc, les OS doivent gérer un ensemble de composantes à vitesses très différentes.
Parallélisme
Disparité des vitesses

Vitesse ( Garder les unités occupées en leur donnant un ensemble de tâches.
( Donc, parallélisme et multi-tâches

Process(us) -- Threads (fil d'exécution)
-- Tasks
-- activités

Un OS: fournit à chaque process une machine virtuelle séquentielle.

Ressources: quelque chose dont un process a besoin pour avancer.
mémoire centrale / disque
cpu
périphériques
Partage des ressources physiques entre les process. (Multiplexage)
Multiplexage dans l'espace: diviser la ressource en portionset les affecter pour la durée de l'activité.
Multiplexage dans le temps: toute la ressource est affectée pour une tranche de temps.
Cours 3, mercredi 13 septembre 2006


Multiplexage (suite):




Performance: Peut-on aller plus vite avec le parallélisme?

ex.: T1 [ R1 ] tâches/ressources
T2 [ R2 ]
 8hrs (











( Débit x2












ex.2: T1: [ Calcule | Écrire | Calcule | Écrire ] ( 8
T2: [ Lire | Calcule | Lire | Calcule ] ( 8

Ici, comme les ressources ne sont pas utilisées en même temps, il n'y a pas d'impact et on peut ainsi tout faire en 8 unités de temps. (Multiprogrammation)

Note: Pour accélérer T2 ( Lecture de parallèle avec le calcul.


(Spooling)


Problèmes de protection:

Dès qu'on a plusieurs choses en même temps en mémoire, on a des problèmes de:
Protection
Synchronisation

Diapo 1-31


ENIAC: Calculatrice
Pas de mémoire programmable (filage)
Pas d'OS

Ordinateurs industriels: IBM-1401 (décimal variable)
 IBM-7040 (point flottant)

Lampes
Transistors

Mémoire ferrite ~ 10 Ko
Data
PGM

Lecteur de carte, imprimante ...

Chargeur: Premier logiciel utilitaire. (logiciel)
BootStrap: mini-chargeur. (matériel?)
- Lire enregistrement du device dont l'adresse est sur le panneau et d'y brancher.


Matériel: Logiciel:
Bootstrap Chargeur
Cartes
600 cartes / minute 10 cartes/s ( ~1Ko/s
 Périphériques rapides
Bandes ( Vitesse + RW Assembleurs 10 Ko/s à 100Ko/s Compilateurs
Disques 100Ko/s à 1Mo/s

Stockage rapide de données intermédiaires (plusieurs passes)

Programmation complexe:
Avancer, reculer
Lire, écrire
Vérification d'erreur
( IOCS (Input Output Control System) qui est un pilote: Une librairie pour gérer les lectures et écritures!
Donc, 2em morceau de logiciel après chargeur. (Le Bootstrap est passé de soft à hardware)

 Encore plus difficile: disques. ( pilotes
Avantage des disques: accès aléatoire/direct.
( Organisation de l'espace en fichiers. VTOC: index


 Volume Table Of Contents:

NomDébutTailleASMFTNTMP1
Cette table généralement positionnée en début de disque.

Donc, en mémoire, on a donc: Bootstrap (BIOS), Chargeur, IOCS, File system, Copie du VTOC, etc.

Cours 4, lundi 18 septembre 2006

Bootstrap: Mini mini pour charger... le chargeur.

Booting:
1. Charger n caractères de l'unité 0 dans TAMPON. (Tampon étant une adresse juste après bootstrap)
2. Goto Tampon

Très rapidement, le Bootstrap a été mis en ROM.
Dès l'arrivée des supports plus rapides, on a ajouter un IOCS en mémoire.

Le BIOS d'aujourd'hui contient le Bootstrap, le Chargeur et le IOCS.

Système de fichier: nom ( adresse sur disque

Moniteur: (shell)
Interprète de commandes + teletype (machine à écrire)
ex.: dir (ls) ( sur le papier de la "machine à écrire"
type (cat, print)
charger xxx ( amener le programme en mémoire
exec ( nom de programme / adresse mémoire

Job typique:
 loop
 lire quelque chose
 clacul
 écrire quelque chose
 end.



 Plus tard:




CPU14013603601GHzCalc. I/S5000106 (x200)ES(disque 106109Lecture0.1s100ms10ms5msCalcul0.1s0.5ms0.5ms0,0005msÉcriture0.1s1000ms10ms5msUtilisation CPU33%0,25%2,5%0,005%Durée job pour 1000 bandes~5 min200s20s10s
Canaux: (DMA: Direct Memory Access)
CPU ultra simple qui fait le transfert mémoire à périphérique en parallèle avec CPU.






 Permet parallélisme:





Cours 5, mercredi 20 septembre 2006

Devrait avoir lu les chapîtres 1, 3 et 4 à la fin de ce cours.

Évolution des systèmes:

Chargeurs & Bootstrap
IOCS (pilotes)
Fichiers
Shell
Monoprogrammation BATCH

!!! Problèmes d'efficacité ( Parallélisme / process

ES complexes: canaux (DMA) & interuption
Multiprogrammation
Spooling (files d'impression)
Hiérarchie de mémoire
Mémoire virtuelle
Caches
Multi-tâches interactif (quantum)
Systèmes distribués:
Lan & Internet [ Sockets ]
JVM (Java Virtual Machine)


Multiprogrammation:

plusieurs jobs en mémoire en même temps.

Mais

Nécessite plus de mémoire
Nécessite plus de périphériques (pas partageables)

Besoin

Protection mémoire
Parallélisme ( Canaux
Commutation de tâche
Interruptions


Spooling: Technique pour gérer efficacement des unités lentes et non partageables (par exemple une imprimante).

exemple: 3 jobs. J1 ( impression de 100 lignes. (CPU ~ 0.1%
J2 ( calculs + E/S disque. (CPU ~10% et écrire une ligne
 J3 ( calculs + E/S bandes et impression 1 ligne. 15s avec (CPU ~ 10%













Implanter des imprimantes «virtuelles».

Stockage temporaire des fichiers sur unités rapides (disques) des données destinées à l'imprimante.

+ Les jobs s'exécutent plus vite. (par exemple 10x plus vite)
+ on peut exécuter plusieurs jobs d'impression en même temps.




Besoin d'une tâche système qui imprime les fichiers de sortie.


Simultaneous
Peripheral
Operation
Off (ou On)
Line


Traitement interactif:

( 10 à 100 usagers

( Périphériques très lents (personnes !)

( Exigences de temps de réaction.

Solutions:
( Ordonnancement préemptif. (Multi-tasking)
Une horloge qui limite la tranche de temps CPU pour une job à un certain maximum (Quantum).
«Mémoire virtuelle»: On garde les programmes sur disque et on les entre en mémoire pour leur quantum.
1. Swap in / Swap out
2. Pagination (on ne garde en mémoire que les portions actives d'un programme).

Mini
PC ( GUI (Graphic User Interface)
Xerox ( souris! (4-5 ans avant MAC)
LISA
MAC
( batterie.
- Réseaux locaux (LAN: Local Area Network) >> Services partagés
- Systèmes embarqués.
¤ Voitures
¤ Téléphones
¤ Lecteurs mp3

Hardware pour OS: [ protection et efficacité ]

Canaux DMA
Bootstrap Note: POST (Power On Self Test)
Protection mémoire
Registres spéciaux
Instructions privilégiées (mode système)
Aide à la commutation
Interruptions

Démo 2, jeudi 21 septembre 2006

man2: Fonction primitives linux
man3: C

man2 open pour connaître le bon include à faire

fcntl.h ( open write read [ souvent besoin des autres aussi, voir démo 3 ]

char buf[1024];
sprintf(buf, "%d-%d\n", 01234, 5678);
write(1,buf,strlen(buf));


Cours 6, lundi 25 septembre 2006

Matériel spécial pour OS:
Canaux (DMA)
Boot [CO ( adresse de début]
Protection
mémoire
mode maître
Commutation de tâche [ch.6]


Protection mémoire:

Adresses logiques/physiques:
ex.: goto L;
( goto 500 ( goto 12345+500;

pagination
Base, limite

2 registres d'adressage:
* RB (registre de base): adresse physique où est chargé le programme.
* LIM (limite): adresse logique maximum permise (taille).

Algorithme d'adressage: AL ( AP
AL = |AL|
si AL>LIM alors erreur
sinon AP = AL + RB

Registres spéciaux: (par opposition à registres usagers)
Registres: CO, R1 à Rn, ... (standards)
Mais, registres spéciaux: RB, LIM... si on ne les protège pas, on perd la protection ci-haut.

à protéger
restreindre à des programmes appropriés (OS)

mode maître / mode usager ( Registre M/U
Instructions privilégiées ( opérations réservées au mode maître.
accès aux registres système
entrées/sorties
commutation de tâches

Commutation de tâches:
 MEM: Space multiplexing
CPU: Time multiplexing



Context switching:
Arrêt d'une activité
Reprise d'une autre
* Appel de procédure (ex.: sin(123); ) et retour
LIFO (pile)
* Multiprogrammation
(passer d'une job à une autre)
* Requêtes de services du OS.
( maître ( retour en mode usager
Requête. Interruption.
* Multi-threads (dans une même job)

Cours 7, mercredi 27 septembre 2006

Commutation de tâche: «context switch»
Pour passer d'un contexte à un autre:
Sauvegarder quelque part l'état de la tâche en cours. (Contenu de tous ou de quelques registres du CPU).
Charger le CPU avec l'état d'une nouvelle tâche.

Ex.: Appel de méthode.
«état» ~=~ CO + SP (stack pointer)

Process classique: - fork(): tous les registres
Process moderne: - Process = environnement (registres usagers) - Thread = CO + Rn seulement (dans un même process)

Matériel: Prévoit des instructions privilégiées qui charge/décharge TOUS les registres critiques d'un coup.
Tous les registres systèmes: S/U, adressage (RB, LIM)
+ certains registres usagers: CO + SP + [...]

( PSW: Process States Words. (registres critiques, pour le matériel)

( PCB: Process Control Block. (descripteur de process, pour le système)

Instruction XPSW: [ Exchange PSW ]

XPSW PSW1, PSW2
Reg CPU ( PSW1
Reg CPU ( PSW2

Appel de méthode:
Branch & Link XXX
empiler CP
CO ( XXX

Deux sortes de XPSW:
Tel que décrit ci-haut et ne peut être exécuté que par le OS.
Version bridée (INTERUPTION) avec PSW1 et PSW2 prédéterminés (qui permet d'aller d'un usager à l'OS). PSW1 = où l'état est sauvegardé = pile système (OS) PSW2 = adresse cablée qui dépend du type d'interruption.

Vecteur d'interruption: Zone mémoire fixe avec un mot par type d'interruption où l'OS doit mettre l'adresse d'une méthode pour la traiter.


Exemples d'interruptions: Mécanisme rapide et sécuritaire pour réagir à des événements rares.

E/S: - Changement dans l'état d'un périphérique. (fin, erreur, ...)
- Horloge
Erreurs: - Usager (division par 0)
(adressage illégal)
(instruction illégale)

Trappe ou Supervisor Call (SVC) … une des instrucgtion illégale qui permet de demander au système un service (je vais avoir mis un code et des paramètres dans les registres).
- Machine (panne)
(parité)

Masquage d'interruption:

Il existe un registre pour masquer les interruption avec peut-être un bit par type d'interruption on a E/S.
ou
3 modes: Usager / Système / Noyau (Noyau = Système + non-interruptible)


Gestion des process:

Table de descripteurs (PCB)
Contenu du PCB: (voir table 6.3)
PSW
Identification
Appartenance (Owner)
Ressources
Variables SHELL
Comptabilité
"État" grossier (actif, en attente, etc.)

Ident: - PID (Process Identifier)

Relations: - PPID (Parent PID)
- Propriétaire: UID / GID
- Process enfant / Threads

Ressources: - mémoire
- fichiers
- périphériques
- tampons

Variables Shell: $HOME / $PWD

Mesures: - Priorité
- #E/S, tempsCPU, Heure début

État grossier: Actif
En attente (pourquoi?: bloqué sur ressource / attend son tour )
Libre (mort)
(implémanté par une liste)


Démo 4, jeudi 28 septembre 2006

fork: lance une copie identique du processus en cours
pid = fork();
( pid contiendra le vrai pid du parent pour parent.
( contiendra 0 pour le fils (pour le vrai pid, faire un getpid() ...)


execl et execv: juste la syntaxe qui change, on ne poursuit plus le code, on switch plutôt au nouveau code
(penser à mettre un exit après l'appel pour les cas d'erreur...)
system: appel un programme via un shell (mais ne remplace pas le programme courant) – bloque en attendant.

wait: quand retourne -1, alors il n'y a plus de fils.
bloque tant qu'un processus ne sort pas...







Cours 8, lundi 2 octobre 2006

PSW – État d'une activité vu par le matériel.

XPSW – Appel machine pour changer d'état, genre LOAD PSW
( Interruption : XPSW «bridé»
- masque
- Vecteur d'interruptions

PCB: Process Control Bloc (PSW + autres bidules dont «État grossier», niveau logiciel)

Opération sur un process:

Création
Lancement
Mort
Arrêt/Reprise
Arrêt volontaire (demande de quelque chose)
Arrêt involontaire (fin du quantum)








































fork():
Allocation de PCB2
Duplication de la mémoire usager
Copie PCB1 ( PCB2
PCB2 ( «Prêt»
Dispatch



Cours 9, mercredi 4 octobre 2006

exec("p2"):
Allouer espace pour CODE
Charger «p2»
Nettoyer DATA
Initialiser CO + Stack (SP)
Dispatch

Threads: Process: Logiciels séparés
Thread: Activités parallèles dans un programme

C'est un «Process léger», une activité parallèle qui partage l'espace mémoire et les ressources d'un process avec d'autres threads.

 Voir Thread Control Block dans le dessin ci-haut.








Java: Stockés au niveau OS
±100@1000
Donc attention différence stocké user
ou stocké system (kernel thread)
User thread: pas de limite
lorsqu'un bloque, alors on change de PCB
Kernel thread: limite de nombre
lorsqu'un bloque, alors on change juste de TCB

Synchronisation:

Mécanisme par lequel une tâche peut attendre quelque chose et se faire réveiller correctement quand la situation désirée est atteinte.

Besoins: - Compétition
- Collaboration

Compétition: pour des ressources (non partageables)... les acteurs ne se connaissent pas.
ex.: imprimante, variable, structure de données
Collaboration: les acteurs se connaissent
ex.: producteur-consommateur p1 (put) ( tampon(x espaces) ( p2 (get)

Problème:

Imbrication d'opérations atomiques.
[programme: suite d'opérations atomiques] ex.: LOAD ou STORE (opérations de base de la machine)
genre: « i=3; » « x=i; »
Buzy Wait / SpinLock: while(lock); Marche pas vraiment.


Cours 10, lundi 16 octobre 2006

absent


Cours 11, mercredi 18 octobre 2006

Exclusion (Section critique):

Essai #1: flag (marche pas vraiment)

Essai #2: Inhiber les interruptions



shared int solde;

P1: P2:
solde += x; vs solde -=x;


problèmes: 1. inhiber/restaurer interrupt sont des opérations privilégiées (donc, pénible pour threads!)
2. peut pas faire E/S durant S.C. (donc marche pas pour l'imprimante!)
3. ne fonctionne pas sur multiprocesseurs

Essai #3: Verrou + inhiber interruption

entree(lock) { boolean verrou = false;

while lock==true do {

entrée(verrou);
} [ Section critique ]
lock=true; sortir(verrour);

}
sortie(lock) {

lock = false;

}
problèmes: 1. fonctionne avec un CPU, mais pas en multi-processeur
2. Perte de temps due à l'attente active
3. Exige un mécanisme privilégié (inhiber interrupt)

Essai #4: (OK!) Peterson (Dekker en 1965 – via Dijkstra)

boolean besoin[0:1] init false ( besoin[0], besoin[1] ( moi, lui )
int tour = 0 ou 1

entree:
besoin[moi] = true; (1)
tour = lui; (*)
while besoin[lui] && tour=lui do; (2)
[Section critique]

sortie:
besoin[moi] = false; (3)

Possibilité de deadlock (avec juste 1, 2 (avant &&) et 3)










( Fonctionne: exclusion mutuelle
( pas de deadlock
( fonctionne avec multiprocesseur
MAIS
( 2 process
( attente active


Sémaphore: Abstraction de synchronisation (Dijkstra 1965).

Type abstrait + opérations ( entrer (P) - wait
( sortir (V) - signal
Section critique
Autres types de synchronisation
Implantation facile

Spécification
exemples
implantation
Définition: Au départ: «entier non-négatif»
Maintenant: Un sémaphore est un objet avec une «valeur abstraite» avec 2 (non 3) opérations.

0) Initialisation i.e.: sema s init 1;
1) «sortie» ou incrémentation
V(sema) , signal. V(s) == [s.valeur++; ] ( atomique
2) «entree»
P(sema) , (wait(s)) P(s) == [ when s.valeur > 0 do s.valeur--; ] ( atomique (!)


sema s init 0;
 P1: --- P2: --- P3: ---
--- --- ---
P(s); P(s); V(s);
 --- --- ---
--- --- ---

 Exemples:
 1) Implanter une section critique



 1 ressource = 1 sémaphore





2) Calcul parallèle

z:= a * b + c * d;





main: sema s init 0;
sema s2 init 0; P2:
lire(a, b, c, d);
V(s); P(s);
x = a*b; y = c*d;
P(s2); V(s2);
z = x + y;



Cours 12, jeudi 19 octobre 2006

Pour l'intra: Lire tout de 1 à 8 sauf 7.
 Accès à un livre + une feuille un côté.


Producteur – Consommateur:


var: ---
---
sema msg init 0,
place init n,
mutex init 1;

prod: cycle consommateur: cycle
 --- P(msg)
--- P(mutex)
x ( get du tampon
--- V(mutex)
 P(place) V(place)
P(mutex) ---

V(mutex) ---
V(msg) ---
--- ---
end end
Lecteur – Rédacteur: (Readers&Writers)

solution 1:

sema BD init 1;

lire: P(BD) ecriture:P(BD)

V(BD) V(BD)

* solution trop basique, on perd le parallélisme en lecture.

solution 2:

int NL=0;
sema accesBD init 1,
accesNL init 1;

lire: écrivain:
P(accesNL) P(accesBD)
NL++;
if NL == 1 then P(accesBD) V(accesBD)
V(accesNL)
---

---
P(accesNL)
NL--;
if NL == 0 then V(accesBD)
V(accesNL)

* risque de famine de l'écrivain.


Preuves avec sémaphore:

nP(s): nombre de process ayant franchi P(s)
nV(s): nombre de process ayant franchi V(s)
init(s): valeur initiale de s
valeur(s): init(s) + nV(s) – nP(s) e" 0

Invariant: nP(s)  nV(s) d" init(s)

Preuve de l'exclusion mutuelle: sema mutex init 1;
P(mutex)
Prouver que N (# de proc en SC) S.C. (N)
0 ou 1 (d"1) V(mutex)

on a: N = nP(mutex)  nV(mutex)
par l'invariant: d" init(mutex)
d" 1
cqfd

nota: sur la feuille de la démo #5, toutes les fonctions thread_mutex sont intéressantes...
l'exemple #4 est intéressant...

Implantation des sémaphores (et Section Critique):

- aide du matériel
( instruction machine qui fait 2 accès mémoire de façon atomique. «Test and Set» TAS TS

ex.: TAS(bool x) ( bool b = x; utilisation: bool occupe = false;
x = true; SC: while TAS(occupe) do;
return b;
occupe=false;

Donc: s: record
int N
boolean lock = false;
end;

P(s) { V(s) {
Label: while lock.TAS() do …; while lock.TAS() do …;
if N