Corso di Informatica
per Giurisprudenza
Lezione 6
Matteo Cristani
Dipartimento di Informatica
Facoltà di Scienze MM. FF. NN.
Università degli Studi di Verona
http://www.sci.univr.it/~cristani
1
Agenda

Struttura di un sistema operativo
 Processi,
gestione memoria, file system;
 Dispositivi di input-output;
 Backup

Sistemi operativi esistenti
 DOS,
Windows, MAC OS, Linux
2
Schema generale di un sistema operativo
3
Concetto di processo
Un processo è un programma in esecuzione
 Sistemi operativi diversi modellano
diversamente le relazioni temporali tra
processi
 ATTENZIONE: Un’applicazione non è
necessariamente un programma

 Molte
applicazioni sono implementate da un
insieme di programmi e quindi quando sono in
esecuzione vi sono molti processi
4
Stato di un processo

Un processo, in un sistema operativo, può
trovarsi in una delle seguenti situazioni
 Attivo:
 In
attesa:
 Sopito:
il processo è in esecuzione, e
controlla le risorse;
il processo è in esecuzione, ma
non controlla le risorse;
il processo non è in esecuzione,
ma attende di essere richiamato
5
Gestione delle risorse

Le risorse a disposizione di un processo
sono fondamentalmente tre:
 Il
tempo di CPU, ovvero il controllo
dell’esecuzione su macchine sequenziali, il
possesso di una delle risorse di calcolo parallele
su macchine non sequenziali
 La memoria centrale
 Le periferiche
6
Condivisibilità



Una risorsa si dice condivisibile se il fatto che un
processo vi acceda non significa che la controlli
Un processo accede ad una risorsa quando può
farne uso, ovvero quando i comandi che invia a
quella risorsa sono eseguiti
Un processo controlla una risorsa quando ogni
richiesta di accesso da parte di altri processi
effettuata mentre il processo stesso vi accede viene
respinta
7
Monitor
Un pezzo essenziale del kernel di un
sistema operativo è il monitor
 Presiede al coordinamento ed al controllo
delle funzioni del Resource Manager che
gestisce

 Job
Scheduling (CPU Time)
 Memory assignement
 Periferiche
8
Funzioni del monitor

Il monitor
 Stabilisce
l’accesso alla CPU
 Gestisce l’accesso a memoria e periferiche
 Coordina le funzioni di accesso
9
Problema generale

I tempi d’accesso a






Operazioni di CPU
Memoria centrale
Periferiche
sono enormemente differenti
un accesso a periferica si compie in tempi
dell’ordine dei millisecondi
un accesso a memoria centrale in tempi dell’ordine
dei microsecondi
una operazione di CPU si compie in tempi
dell’ordine dei picosecondi
10
Conseguenze
Nel tempo che un processo impiega a fare
accesso a memoria centrale o addirittura ad
una periferica la CPU è posseduta ma ferma
 Meccanismo risolutore

 Si
sottrae la CPU
 Si INTRAPPOLA il processo, cosicchè il
monitor, quando riceve notizie dalla memoria o
dalla periferica interessata che segnalano la
terminazione dell’accesso toglie il processo
dalla sua trappola e lo riammette in coda
11
Resource manager
12
Trap e DMA (1)



Se la CPU viene sottratta ad un processo e questo
processo deve accedere ad una risorsa, chi
eseguirà i comandi di accesso?
La tecnica implementata negli attuali H/W è la
DMA (Direct Memory Access)
Ogni banco di memoria centrale (RAM, ROM) ed
ogni periferica posseggono un chip collaterale che
esegue i comandi di accesso relativi alla memoria
od alla specifica periferica: la DMA
13
Trap e DMA (2)
Se intrappoliamo un processo e lo
consegnamo alla DMA che eseguirà la sua
richiesta di accesso alla risorsa controllata
otteremo lo scopo prefissato
 La CPU sarà libera
 La coda non verrà interrotta

14
Fatti storici
Anche se la tecnica sulle DMA è posteriore
alla concezione di algoritmi atti ad
implementare una politica di scheduling
ROUND-ROBIN esse sono molto motivanti
per tale scelta
 Inoltre, senza ROUND-ROBIN le DMA
sono poco utili

15
Funzioni generali di un sistema operativo

Il sistema operativo deve svolgere le
seguenti funzioni
1.
2.
Processare le richieste di risorse non
condivisibili stabilendo le modalità con cui i
processi richiedenti accedono alle risorse
stesse e l’ordine di accesso;
Processare le richieste di risorse condivisibili
stabilendo l’ordine di accesso
16
Accesso alla CPU

Storicamente
 Accesso
secondo richiesta
 Accesso secondo priority
 Accesso secondo dimensioni
 Accesso a rotazione
FIFO
PQ
SJF
ROUND-ROBIN
17
Modello FIFO
I processi che chiedono la CPU ne entrano
in possesso quando tutti i processi che ne
avevano fatto richiesta prima l’hanno
impiegata
 Un processo in coda è sempre in attesa
 Non esistono processi sopiti

18
Esempio





Al tempo 0 chiede la CPU il processo p1, che la
terrà occupata per 10 secondi
Al tempo 3 chiede la CPU il processo p2 che la
terrà occupata per 12 secondi
Al tempo 8 chiede la CPU il processo p3 che la
occuperà 3 secondi
Al tempo 11 chiede la CPU il processo p4 che la
occupa 7 secondi
Al tempo 17 chiede la CPU il processo p5 che la
occuperà per 4 secondi
19
Esempio

Pertanto:










Al tempo 0 il processo attivo è p1, nessun processo in coda
Al tempo 3 si accoda p2
Al tempo 8 si accoda p3
Al tempo 10 termina p1 e diviene attivo p2
Al tempo 11 si accoda p4
Al tempo 17 si accoda p5
Al tempo 22 termina p2 e diviene attivo p3
Al tempo 25 termina p3 e diviene attivo p4
Al tempo 32 termina p4 e diviene attivo p5
Al tempo 36 termina p5
20
Schema
p5
p1
p3 p4
p4
p5
p2
p2 p3p3
p3
p4
p1
p1 p2p2
p2
p3
p4
p5
} processo
attivo
0
3
8
10 11
17
22
25
32
36
21
Caratteristiche di FIFO

Vantaggi



Ordine di precedenza
rispettato
Certezza
dell’esecuzione
Completamento di un
singolo processo in
tempo pari al tempo di
esecuzione dopo
l’accesso alla risorsa

Svantaggi



Tempo di attesa in
coda variabile
Impossibilità di gestire
le urgenza
Processi molto lunghi
possono tenere in coda
processi molto corti
22
Priority queueing
I processi che chiedono la CPU ne entrano
in possesso quando tutti i processi che ne
avevano fatto richiesta prima avendo
priorità maggiore o uguale al processo
richiedente l’hanno impiegata
 Un processo in coda è sempre in attesa
 Non esistono processi sopiti

23
Implementazioni di PQ (1)

A coda singola
I
processi vengono monitorati solo all’ingresso
in coda e la risalgono fino a quando il processo
che le precede ha la stessa priorità, o priorità
maggiore o hanno raggiunto la cima della coda
24
Implementazioni di PQ (2)

A coda multipla
 Ogni
priorità ha la sua coda
 I processi di una coda vengono eseguiti in
ordine FIFO
 Le code vengono monitorate in ordine diretto
dalla priorità più alta a quella più bassa
25
Caratteristiche di PQ (1)

Vantaggi


Garanzia di priorità per
processi urgenti
Tempo di attesa in
coda dipende dalla
priorità

Svantaggi


Processi a bassa
priorità possono restare
in coda potenzialmente
all’infinito
Difficile attribuire le
priorità in modo
automatico
26
Caratteristiche di PQ (2)

Vantaggi



Garanzia di priorità per
processi urgenti
Tempo di attesa in
coda dipende dalla
priorità e in parte
dall’ordine di richiesta
I processi, anche a
bassa priorità vengono
sempre eseguiti

Svantaggi


Difficile attribuire le
priorità in modo
automatico
Processi ad alta priorità
possono attendere a
lungo in ogni caso,
essendo in coda alle
richieste
27
Shortest Job First
Viene eseguito per primo il processo più
breve tra quelli in coda
 Un processo in coda è sempre in attesa
 Non esistono processi sopiti

28
Caratteristiche di SJF

Vantaggi

Tempo medio di attesa
in coda è minimizzato

Svantaggi


Processi lunghi
possono restare in coda
potenzialmente
all’infinito
Nessuna priorità
29
Round-Robin
Ogni processo è ripartito in fette di tempo
(time-slice) di durata massima predefinita
 Quando una time-slice è terminata la CPU
viene attribuita al processo successivo in
coda
 I processi in coda sono sia in attesa che
sopiti

30
Round-Robin e DMA
Se un processo fa solo operazioni CPU
durante il suo Time-Slice, allora, dato che
non verrà intrappolato continuerà a
possedere la CPU
 Se un processo accede a memoria o
periferiche finirà intrappolato e il monitor
gli sottrarrà la CPU
 Perciò, in presenza di un trap, la durata di
una time-slice sarà inferiore

31
Caratteristiche del Round-Robin

Vantaggi



Certezza
dell’esecuzione
Minimizzazione del
tempo di attesa in coda
Sfruttamento completo
delle risorse

Svantaggi

La maggior
complicazione
dell’algoritmo di
scheduling richiede
grande attenzione alla
sua implementazione
32
Schemi del Job Scheduling
33
Concorrenza
Processi eseguiti in coda su macchine
sequenziali monitorate da un sistema
operativo con Job Scheduler a politica
Round-Robin si dicono concorrenti
 La concorrenza non è parallelismo

34
Tipi di sistema operativo (1)

Rispetto all’esecuzione di applicazioni un
sistema operativo può concepire
applicazioni in tre stati
 Con
il Focus
 Attive
 Accessibili
35
Tipi di sistema operativo (2)
Se un sistema operativo ammette più
applicazioni con il focus e il Job Scheduling
è Round-Robin, allora due utenti potrebbero
eseguire applicazioni diverse in concorrenza
 Se ciò avviene diremo che il sistema
operativo con time-sharing competitivo

36
Tipi di sistema operativo (3)
Nel caso opposto, cioè quando una
applicazione cede il focus solo
spontaneamente, diremo che il time-sharing
è cooperativo
 Windows95 e Mac OS fino alla versione 4
sono sistemi definiti cooperativi
 Da Windows98 in poi e da Mac OS 5 si
parla di sistemi competitivi

37
File system
Si chiama File System l’organizzazione
strutturale dei dati di memoria di massa
gestita da un sistema operativo
 Questa funzione è fondamentale

38
Organizzazione del file system

Aspetto
È
un albero
 Navigabile bidirezionalmente
 I nodi si chiamano Directory, e i legami
parenthood links
39
Organizzazione dei dati
I file vengono collocati nel disco dove
possibile
 Per sfruttare al meglio lo spazio i file
possono essere spezzati in blocchi
 La cancellazione di un file o la sua modifica
comporta la modifica (e potenzialemte)
l’eliminazione dei blocchi che lo
compongono

40
Metodo
Occorre quindi progettare tecniche di
Allocazione dei Blocchi che consentano di
evitare sprechi e garantire la conservazione
dell’integrità dei dati stessi
 Le politiche di allocazione sono uno delle
più significative scelte strategiche nella
definizione di un sistema operativo

41
Tecniche di allocazione (1)

Le tecniche di allocazione dei blocchi sono
costruite sui seguenti assunti
I
blocchi hanno tutti le stesse dimensioni
 Il numero di blocchi di un file è variabile
42
Best-Fit
Trova le zone libere del disco
 Ripartisci il file in segmenti di blocchi
adiacenti in modo da garantire che ogni
segmento occupi una zona libera del disco
con il minimo spreco di memoria

43
Caratteristiche di Best-Fit



Potenzialmente difficile il problema di trovare le
aree per l’allocazione
Se residuano piccole porzioni del disco esse
saranno certamente sprecate
Esempio

Windows95, Windows98

Implementava una FAT (File Allocation Table) dove registrava
le informazioni di allocazione e disallocazione

Dopo un periodo di uso intenso occorreva operare una
deframmentazione per compattare e quindi riutilizzare le aree
del disco inutilizzate
44
Worst-Fit
Trova le zone libere del disco
 Ripartisci il file in blocchi in modo da
garantire che ogni segmento occupi una
zona libera del disco con il massimo spreco
di memoria

45
Caratteristiche di Worst-Fit
Minor spreco
 È più probabile che se un file è piccolo si
allochi subito

46
Backup (1)
A causa dei crash elettrici, degli errori
umani e dei problemi con software con
bachi è possibile che dati recentemente
scaricati sul computer siano illeggibili
 Per prudenza, quindi, si fa copia del
contenuto del disco (o talvolta di una sua
parte)
 Tale copia si chiama backup

47
Backup (2)
Il backup, per sistemi di grandi dimensioni,
può risultare voluminoso e lungo da fare a
mano
 Si ricorre quindi a tecniche di Backup
periodico (ogni giorno)

48
Sistemi operativi esistenti

La grande famiglia UNIX
 Unix
 Linux
 NetBSD,

FreeBSD
Windows
 Windows
95
 Windows 98
 Windows 2000
 Windows XP
49
DOS e Windows
DOS (Disk Operating System) fu una idea
di interesse sviluppata con lo scopo di
rendere semplice l’accesso a risorse di un
computer da parte di utenti inesperti
 Attualmente esso è una componente di
Windows (il Prompt dei Comandi)

50
Mac OS
La Apple ha sempre prodotto il software di
gestione delle proprie macchine in modo
totalmente autonomo rispetto alle pressioni
del mercato
 Il sistema operativo, molto simile come
ambiente operativo a Windows, gestisce la
memoria e le altre risorse in modo
prioritario

51