Dispense

Sistemi di Elaborazione A.A. 2004/2005 1

Sistemi di Elaborazione dell’Informazione

Luca [email protected]

www.diiga.univpm.it/~spalazzi/

DIIGA - Università Politecnica delle Marche

A.A. 2004/2005


� Introduzione

� Gestione dei Processi

� Gestione della Memoria

� File System� Sistemi di I/O

� Linux

Programma del Corso

• Struttura dei sistemi di elaborazione• Struttura dei SO

• Processi e Thread• Scheduling della CPU

• Gestione della memoria• Memoria virtuale

• Struttura dei sistemi di I/O• Struttura dei dischi

• Installazione• Amministrazione di sistema• Programmazione tramite script


Testi di riferimento e materiale didattico

� A. Silberschatz, P. B. Galvin, G. Gagne, Sistemi Operativi, VI Edizione, Addison-Wesley

� A. Silberschatz, P. B. Galvin, G. Gagne, Instructor’s Manual (soluzioni degli esercizi del libro)

� Copia dei lucidi proiettati a lezione� Raccolta di esercizi del docente


Sito Web del corsowww.diiga.unian.it/C3I067/

� Registrazione al sito del corsofare il login con• username: registra• password: sistelab

appena registrati arriva una email con la password� Il sito serve per

� Reperire informazioni sul corso, esami, ricevimento, ecc.

� Scaricare materiale didattico� Iscriversi alle esercitazioni di laboratorio� Iscriversi all’esame


Laboratorio� Esercitatori

ing. G. Capuzzi, ing. F. Pagliarecci� Esercitazioni di linux (knoppix)� Una versione di knoppix si può scaricare al seguente

indirizzo:www.knoppix.org

� Orario delle esercitazioni (4 turni)• Mercoledì 10:30-13:30• Venerdì 13:30-16:30

� Iscrizione alle esercitazioni� Inviare un messaggio (con il servizio di posta

interna al sito) all’utentelaboratorio

� L’oggetto del messaggio deve contenerecognome, nome, matricola


Iscrizione Esami� Iscrizione agli esami

� Ci sarà un utente per appello, il nome di tale utente corrisponde alla data dell’esame

� Inviare un messaggio (con il servizio di posta interna al sito) all’utente corrispondente alla data prescelta

� L’oggetto del messaggio deve contenerecognome, nome, matricola

� L’iscrizione si chiude due giorni prima dell’appello� Terminate l’iscrizione, viene pubblicato sul sito

l’elenco degli iscritti e gli orari dell’esame� Verificate che risultate iscritti!!!


Modalità di esame

� Prima prova: scritta (questionario al calcolatore)• vale 10,5 punti

� Seconda prova: orale• vale 21 punti

stesso appello dellaprova scritta

ha tempo fino a gennaio 2006

Quando

non ammesso< 5

ammesso5 ≤ voto < 6

ammessovoto ≥ 6Ammissione all’oraleVoto Prova Scritta


Assistenza studenti� Orario di ricevimento

• Martedì 11:30 – 13:30� Recapito telefonico

• 071 220 4829� Recapito di posta elettronica

• [email protected]


Introduzione� Sistemi di Elaborazione� Esempi di Sistemi di Elaborazione

• Mainframe, Desktop, Multiprocessore, Distribuiti, Real -Time, Handheld

� Architettura dell’Hardware• CPU• Memoria centrale• Dispositivi di I/O• Gerarchia della memoria• Protezione dell’Hardware

� Architettura del Sistema Operativo• Componenti e servizi di un SO• System call• Architetture

> Monolitica> Stratificata> Microkernel> Macchina Virtuale


Sistema di Elaborazione

Insieme di risorse hardware e software per l’elaborazione automatica delle informazioni.


Architettura di un Sistema di Elaborazione


1. Hardware: le risorse di calcolo fondamentali (CPU, memoria, dispositivi di I/O).

2. Sistema Operativo:controlla e coordina l’utilizzo dell’hardware da parte dei vari programmi applicativi di utenti diversi.

3. Programmi Applicativi:definiscono il modo in cui le risorse del sistema devono essere usate per risolvere i problemi di elaborazione dei diversi utenti (es. compilatori, basi di dati, video game, videoscrittura, programmi scientifici, programmi contabili).

4. Utenti:coloro che utilizzano i programmi applicativi (persone, macchine, altri computer).

Architettura di un Sistema di Elaborazione


Sistema Operativo

� Un programma che funge da intermediario tra un utente e l’hardware di un computer.

� Un programma che rende possibile lo sfruttamento in modo efficiente dell’hardware del computer

� Obiettivi di un SO:• Eseguire i programmi utente

• Facilitare la soluzione dei problemi degli utenti.

• Rendere il computer conveniente.


Altre Definizioni di SO

� Allocatore di Risorse – gestisce ed alloca risorse.

� Programma di Controllo – controllo l’esecuzione deiprogrammi utente e le operazioni dei dispositivi di I/O.

� Kernel – l’unico programma che è sempre in esecuzione(tutti gli altri sono considerati programmi applicativi).



• Mainframe, Desktop, Multiprocessore, Distribuiti, Real -Time, Handheld





Simple Batch System

Memory layout


Multiprogrammed Batch Systems

Diversi job sono tenuti in memoria contemporaneamente e la CPU è multiplexata tra loro.


Cosa serve per la Multiprogrammazione

� Scheduling della CPU:il sistema deve scegliere tra i diversi job pronti per l’esecuzione.

� Gestione della Memoria:il sistema deve allocare la memoria a diversi job.

� Gestione dei Dispositivi di I/O:• il sistema deve allocare l’I/O a diversi job.

• il sistema deve fornire le routine di I/O.


Time-Sharing

� La CPU è multiplexata tra diversi job che sono sia in memoria sia su disco. La CPU è allocata solo a job chesono in memoria.

� Ogni job può essere portato dal disco in memoria (swap in) e viceversa (swap out).

� Viene messa a diposizione una comunicazione on-line tragli utenti ed il sistema; quando il SO termina l’esecuzionedi un comando, il controllo passa alla tastiera (e quindiall’utente).

� Viene messo a diposizione degli utenti un sistema on-line per accedere ai dati ed al codice.


Desktop Systems

� Personal computers – computer dedicati ad un singoloutente.

� Dispositivi di I/O – tastiera, mouse, schermo, stampante.

� Maggior convenienza e prontezza delle risposte ma anche maggior responsabilità per gli utenti.

� Infatti spesso non vengono forniti sofisticati meccanismidi protezione.

� Possono girare diversi tipi di SO (Windows, MacOS, UNIX, Linux)


Sistemi Paralleli

� Sistemi multiprocessore con le CPU in strettacomunicazione fra loro.

� Sistemi Strettamente Accoppiati (Tightly coupled system) i processori condividono la memoria e il clock; i processori, di solito, comunicano tra loro attravero la memoria condivisa.

� Vantaggi dei sistemi paralleli: • throughput elevato

• economia di scala

• affidabilità elevata

> graceful degradation: possibilità di continuare il servizio in misura proporzionale al livello di hardware difettoso


� Symmetric multiprocessing (SMP)

• In ogni processore è in esecuzione la stessa copia di SO.

• Possono essere eseguiti diversi procesicontemporaneamente senza degrado delle prestazioni.

• La maggior parte dei moderni SO supporta SMP

� Asymmetric multiprocessing

• Ad ogni processore viene assegnato un compito specifico; esiste un processore master che ha il compito di schedularee allocare il lavoro sui diversi processori slave.

• Sono più comuni in sistemi estremamente grandi.

Sistemi Paralleli (Cont.)


Symmetric Multiprocessing


Sistemi Distribuiti

� L’elaborazione è distribuita tra diversi procesori fisici.

� Sistemi lascamente accoppiati (Loosely coupled system) ogni processore ha la sua memoria locale; ogniprocessore comunica con gli altri attraverso linee dicomunicazione (bus ad alta veocità, linee telefoniche, ...).

� Vantaggi dei sistemi distribuiti.• Condivisione delle risorse

• Accelerazione della computazione – bilanciamento del carico di lavoro

• Affidabilità

• Comunicazione


� Richiedono infrastrutture di rete.

� Reti locali (Local area networks - LAN) o Reti geografiche(Wide area networks - WAN)

� Possono adottare architetture • client-server

• peer-to-peer.

Sistemi Distribuiti (Cont.)


Client-Server


Peer-to-Peer

peer peer peer peer...

network


Sistemi Real-Time

� Spesso sono usati come dispositivi di controllo in applicazioni dedicate come il controllo di esperimentiscientifici, di immagini mediche, di applicazioniindustriali,...

� Esitono vincoli temporali precisi.

� Possono essere hard or soft real-time.


Real-Time Systems (Cont.)

� Hard real-time:• La memoria secondaria è limitata o assente, i dati sono

memorizzati in memoria RAM o ROM.

• Di solito i general-purpose operating systems non vanno bene.

� Soft real-time• Limitato impiego nella robotica industriale.

• E’ utilesoprattutto in applicazioni (quali multimedia, virtual reality) che richiedono SO con caratteristiche avanzate.


Sistemi Handheld

� Personal Digital Assistants (PDAs)

� Telefoni cellulari

� Caratteristiche:• memoria limitata

• processori lenti

• schermi piccoli.

� Possono girare diversi tipi di SO (Windows Mobile, Embedded Linux, Symbian, Android (?))



� Mainframe, Desktop, Multiprocessore, Distribuiti, Real -Time, Handheld





Architettura di un Computer


Operazioni di un Computer

� I dispositivi di I/O e la CPU funzionano concorrentemente.

� Ogni controller si occupa solo di un particolare tipo di dispositivo.

� Ogni controller ha un buffer locale..

� La CPU trasferisce dati dalla memoria centrale ai buffer locali e viceversa.

� Una operazione di I/O consiste nel trasferire dati dal dispositivoal buffer locale e/o viceversa.

� Controller dei dispositivi e CPU devono essere sincronizzati traloro.


Architettura di una CPU

BusBusIndirizziIndirizzi

DatiDati

ControlloControllo

CPUCPU


Architettura della Memoria Centrale


DatiDati

ControlloControllo

Circuiti dicontrollo

Memoria CentraleMemoria Centrale


Ciclo di funzionamento

while (not halt ) do

{ /* fetch istruzione */

RCP -> RIp;

RIp -> RIm;

M[RIm] ->RLSm;

RLSm -> RLSp;

RLSp -> RIC;

/* decodifica istruzione */

“attiva rete di decodifica”;

/* esegui istruzione */

....

RCP + 1 -> RCP

}


Decodificatore

Indirizzi:-indirizzi (RId)

Circuiti di controllo:-istruzione corrente (RICd)

-stato (RSd)

Registri:-lettura/scrittura (RLSd)

Dispositivo Dispositivo

Architettura dei Dispositivi di I/O

ControllerController


DatiDati

ControlloControllo


Ogni dispositivo e’ collegato al bus di sistema tramite un’interfacciadove risiedono alcuni registri (di controllo, per permettere lasincronizzazione CPU-Dispositivo, buffer per contenere i dati iningresso/uscita). Questa interfaccia e’ chiamata controller.

La CPU colloquia con il controller scrivendo/leggendo i suoi registri:

-utilizzando apposite istruzioni (IN / OUT) che avranno comeparametro un “indirizzo” che identifica un particolare controller

-utilizzando normali istruzioni LOAD/STORE a indirizzi associati ai registri del controller: questa tecnica si chiama Memory Mapped I/O

Architettura dei Dispositivi di I/O


Nelle architetture più semplici si trovano normalmente tre tipi di schemi per eseguire le azioni di I/O

•I/O programmato con Busy-Waiting

•I/O guidato dalle interruzioni (Interrupt)

•I/O con accesso diretto alla memoria (DMA)

Tipi di I/O


I/O Programmato (con busy waiting)


Pseudocodice per il controllo dell’output di una stringa di caratteri sul display

I/O Programmato (con busy waiting)

Busy Waiting


Dato che CPU e dispositivi di I/O hanno velocità molto diverse, èopportuno non tenere la CPU bloccata in un ciclo di controllo dei bitdi stato in attesa che termini l’operazione richiesta. Se si potesse evitare il busy waiting, mentre i dispositivi di I/O lavorano, la CPUpotrebbe essere impiegata in compiti più utili (per esempio eseguire una altro programma).

I/O guidato da Interrupt


Interazione CPU/tastiera basata su interrupt

Tastiera

ControlloreCPU1.Comando input

2. Interrupt

3. CPU copia in memoriaRAM

La CPU viene interrotta prima del trasferimento in memoria (che viene effettuato dalla CPU) del contenuto del buffer.



Problemi:

Come funziona nel caso ci siano più dispositivi che possono inviare segnali di interrupt ?

1. i segnali provenienti dai diversi dispositivi vengono messi in OR

2. il dispositivo che ha causato interrupt viene individuato tramitePolling oppure utilizzando la tecnica dell’Interrupt Vettorizzato

CPU CPU Device 1 Device 1 Device n Device n

INTINT

OROR


Int. 1Int. 1 Int. nInt. n


Problemi:

Cosa accade se arrivano piu’ interrupt contemporaneamente?la CPU avverte un solo segnale (OR di tutti i segnali di int.)

1) se si usa il Polling, l’ordine di scansione determina unordinamento implicito tra i dispositivi

2) se si usa l’Interrupt vettorizzato, occorre impostare un protocollo di comunicazione tra CPU e dispositivi: quando la CPU ha ricevuto l’interrupt ed e’ pronta a gestirlo, invia un segnale di Acknowledge (INTA). Quando il controller riceve il segnale invia l’identificatoredel dispositivo (vettore di interrupt) sul bus dati. Se il segnale diINTA viene propagato sequenzialmente dai controllori dei dispositivi (collegamento daisy chain) e assorbito dal primo controller che aveva un interrupt pendente, si ha un ordinamento implicito tra i dispositivi determinato dal collegamento in daisy chain degli stessi




INTINT

OROR

INTAINTA

Int.Int.VectVect.1.1 Int.Int.VectVect.n.n


BusBus datidati





Problemi:

Cosa accade se arriva un secondo interrupt mentre e’ inesecuzione la procedura di trattamento di un (primo) interrupt?

1. Deve essere possibile disabilitare gli interrupt per prevenire laperdita di interrupt e più in generale quando deve essere eseguita una porzione di codice senza interruzioni. In questo caso gli interrupt pendenti vengono ingorati fino alla riabilitazione degli interrupt. Non si possono avere interruptannidati.

2. Se vi sono segnali di interrupt con vincoli stringenti sui tempi di risposta, e’ opportuno poter definire diversi livelli di priorita’ epermettere ad un interrupt ad alta priorita’ di essere gestito anche se e’ in esecuzione una procedura di gestione di unaltro interrupt (a piu’ bassa priorita’) – si possono quindi avereinterrupt annidati




INTINT

OROR

INTAINTA

Int.Int.VectVect.1.1 Int.Int.VectVect.n.n


BusBus datidati


PortaPorta

di di

uscita uscita

AbAb. 1. 1

AbAb. n. n

All’arrivo di una interruzione con priorità pj vengono disabilitate le interruzioni da dispositivi con priorità inferiore a pj


Esempio di utilizzo di diversi livelli di priorita’ per gli interrupt

Stampante: Livello 2, RS232: Livello 5, Disco: livello 4



Gestione dell’interrupt

Cosa succede quando la CPU riceve un interrupt:

1. L’istruzione macchina in corso viene completata.2. Si salva in memoria lo stato della computazione interrotta

(registri e program counter) nel descrittore di processo.3. Si determina il tipo di interruzione che è avvenuta (tramite

polling o tecnica dell’interrupt vettorizzato).4. Si salta ad una posizione in memoria dove è contenuto

l’interrupt handler ovvero il gestore di quel tipo di interruzioni (es. driver del disco). Infatti segmenti di codice separati determinano quale azione deve essere eseguita per ogni tipo di interrupt.

5. Dopo aver gestito l’interrupt, viene ripristinato lo stato del programma interrotto e la sua esecuzione prosegueTutto cio’ deve essere TRASPARENTE rispetto

a chi viene interrotto



Alcuni esempi di interrupt handlerL’interrupt handler per un interrupt da disco trasferisce dati dalbuffer del controller a memoria o viceversa, e se esistono richieste di I/O in attesa del disco una di queste viene inoltrata al controller.Inoltre il programma che era in attesa dell’I/O appena terminato,viene riportato nell’insieme dei programmi a cui deve essere assegnata la CPU.

L’interrupt handler per un timer interrupt si occupa dell’assegnazione della CPU ad un altro programma, fra quelli pronti per l’esecuzione.

L’interrupt handler per un interrupt da tastiera trasferisce il carattere appena ricevuto dalla tastiera in memoria e riporta il programma che era in attesa dell’I/O appena terminato nell’insieme dei programmi a cui deve essere assegnata la CPU.



La CPU deve poter sapere quale dispositivo ha inviato l’interrupt:

CPUController

dispositivo

Richiesta

operazione

INT

esecuzione

I/O

INTA

ID (Identificatore

dispositivo)

Salta alla procedura di gestione dell’interrupt(interrupt handler) il cuiindirizzo di partenza si trova nell’interrupt vector, una tabella del sistema operativo indicizzato in base al (tipo di)dispositivo, qui indicato da ID.

I/O guidato da InterruptGestione dell’interrupt

Disabilita

interruzioni


Rilevamento e disabilitazione/abilitazionedegli interrupt

Esempio di

microinterprete senza

gestione degli interrupt:


{ fetch istruzione;

decodifica istruzione;

esegui istruzione;

}

Esempio di microinterprete con

gestione degli interrupt:


{ if (interrupt & not int_disable)

{salva stato;

invia INTA;

leggi device_id;

int_disable = true;

PC = int_vector[device_id];}

fetch istruzione;

decodifica istruzione;

esegui istruzione; }



Direct Memory Access Structure� Utilizzato per dispositivi di I/O ad alta velocità in grado di

trasferire dati ad una velocità vicina a quella della memoria.

� Il controller del dispositivo trasferisce blocchi di dati dal buffer direttamente alla memoria centrale senza l’intervento della CPU.

� Viene generato un solo interrupt per blocco piuttosto che un interrupt per byte.


CPU

Controller

DMA

RAM

1. comando input

2. Copia Blocco

(senza l’intervento

della CPU)

3. interrupt

La CPU viene interrotta dopo il trasferimentoin memoria (senza il suo intervento) delcontenuto del buffer. Il controller DMA e la CPU si contendono il bus.

I/O con Accesso Diretto alla MemoriaInterazione CPU/controller DMA


Poiche’ il Bus di collegamento alla memoria e’ condiviso occorreun arbitro che gestisca i conflitti. Fenomeno del Cycle Stealing che letteralmente significa furto di cicli (del Bus).

I/O con Accesso Diretto alla Memoria


Esiste un altro tipo di interrupt, provocato dall’esecuzione di una determinata istruzione del programma in esecuzione:• istruzioni con errori (divisione per zero, accesso in memoria nonvalido, ...)• istruzioni esplicite di “trap” al SO (un programma utente richiedeun servizio del SO

Le trap vengono trattate in modo del tutto analogo agli interrupt:ciascun tipo di trap ha un identificatore che viene usato per cercare nell’interrupt vector l’indirizzo della prima istruzione delcorrispondente interrupt handler.

Gli Interrupt sono ASINCRONI rispetto al programma inesecuzione mentre le Trap sono SINCRONE: causate dal programma in esecuzione.

Interruzioni Software (Trap)


Memoria Secondaria

� La memoria centrale è un supporto di memorizzazione (volatile) che può essere acceduto direttamente dalla CPU.

� La memoria secondaria è una estensione della memoria centrale, in grado di fornire un supporto di memorizzazione non volatile e di maggiori dimensioni.

� Un disco magnetico è un insieme di piatti ricoperti di materialemagnetico.


Disco Magnetico


Gerarchia della Memoria

� Gerarchie delle memorie - il sistema di memorizzazione è organizzato gerarchicamente sulla base di:.• Velocità

• Costo

• Volatilità

� Caching – consiste nel copiare i dati contenuti nella memoria diun certo livello in una memoria di livello superiore (più veloce). Questa serve per tenere i dati che sono stati utilizzati più di recente. • Questo richiede una politica di cache management.

• Questo richiede che dati che si trovano simultaneamente in più diun livello devono essere consistenti tra loro.

La cache serve per fare il caching della memoria centrale.La memoria centrale può essere vista come la cache della memoria secondaria.


Gerarchia della Memoria


Migrazione di A dal Disco ai Registri


Protezioni Hardware� Funzionamento in Dual-Mode

� Protezione dell’I/O

� Protezione della Memoria

� Protezione della CPU


Funzionamento in Dual-Mode� La condivisione delle risorse di sistema richiede al SO di

assicurare che un programma non corretto non danneggi gli altriprogrammi (SO incluso).

� I sistemi sono quindi forniti di hardware di supporto per differenziare come minimo due modi di funzionamento:1. User mode – il sistema sta eseguendo istruzioni per conto di

programma utente.

2. Kernel mode (anche detto monitor mode o system mode) – ilsistema sta eseguendo istruzioni per conto del SO.

� Anche le istruzioni vengono suddivise in � istruzioni privilegiate – le istruzioni macchina in grado di causare

danni allo stato del sistema

� istruzioni non privilegiate – tutte le altre istruzioni

Le istruzioni privilegiate possono essere eseguire solo in modalità kernel.


Funzionamento in Dual-Mode (Cont.)� Viene aggiunto un bit di modo all’hardwa del computer

per indicare la modalità di funzionamento: kernel (0) o user (1).

� Quando c’è una interruzione o un trap, l’hardware passain modalità kernel. In questo modo l’interrupt handler (chee’ un componente del software di sistema operativo)esegue in modalità kernel. Alla istruzione di ritorno dainterrupt, viene ripristinata la modalità utente.

kernel user

Interrupt/fault

set user mode


Istruzioni privilegiate

La fase di esecuzione di una qualsiasi istruzione privilegiata inizierà con un test sul bit di modo: se questo è impostato a “kernel” l’esecuzione prosegue, altrimenti viene generata una eccezione (trap) e il programma che ha tentato di eseguire l’istruzione privilegiata viene interrotto.

Funzionamento in Dual-Mode (Cont.)


Protezione dell’I/O� Tutte le istruzioni di I/O sono istruzioni privilegiate.

� Questo è il motivo per cui per eseguire operazioni di I/O bisogna eseguire delle system call.


Protezione della Memoria� Le protezioni viste fino ad ora non sono sufficienti, infatti un

programma utente potrebbe modificare il vettore di interrupt mettendo un indirizzo relativo al codice del programma utentestesso, in questo modo il programma utente riuscirebbe ad eseguire le proprie istruzioni in modalità utente.

� Serve quindi proteggere la memoria da accessi indesiderati, al meno per il vettore di interrupt e gli interrupt handler.

� Per avere la protezione della memoria bisogna aggiungere due registri che determinano l’intervallo nello spazio degli indirizziche un programma può accedere legalmente:• Registro Base – contiene l’indirizzo fisico più basso al quale un

programma può accedere legalmente.

• Registro Limite – contiene la dimenione dell’intervallo

� La memoria al di fuori di tale intervallo è protetta.


Protezione della Memoria




� Quando il SO sta funzionando in modalità kernel, ha accessoillimitato sia alla memoria del monitor sia alla memoria deiprogrammi utente.

� Le istruzioni di load per i registri base e limite sono istruzioniprivilegiate.



Protezione della CPU� Bisogna evitare che un programma mantenga il controllo della

CPU per un tempo illimitato, il SO deve essere sempre in grado di riprendere il controllo della CPU.

� Questo può essere ottenuto con un timer.

� Timer – interrompe il computer dopo uno specifico periodo ditempo:• Timer è un contatore che viene decrementato dopo ogni clock tick.

• Quando raggiunge il valore 0, viene generato un interrupt.

� Timer sono comunemente usati per realizzare il time sharing.

� Timer sono anche usati per calcolare l’ora.

� Load-timer è una istruzione privilegiata.



� Mainframe, Desktop, Multiprocessore, Distribuiti, Clustered, Real -Time, Handheld

� Architettura dell’Hardware� CPU� Memoria centrale� Dispositivi di I/O� Gerarchia della memoria� Protezione dell’Hardware




Componenti di un SO

� Gestione dei processi

� Gestione della memoria centrale

� Gestione dei dispositivi di I/O

� Gestione della memoria secondaria

� Gestione del file system

� Gestione delle reti

� Sistema di Protezione

� Interprete di comandi


Gestione dei Processi

� Un processo è un programma in esecuzione

� Ogni processo ha bisogno di determinate risorse per terminare il suo compito: CPU, memoria, file e dispositividi I/O.

� Il SO è responsabile della gestione dei processi:• Creazione e cancellazione deiprocessi,

• Sospensione e ripristino dei processi,

• Meccanismi per :

> la sincronizzazione dei processi

> la comunicazione dei processi


Gestione della Memoria

� La memoria centrale è un array di word o byte moltogrande, ognuno con un suo indirizzo. Permette l’accessoveloce a dati condivisi dalla CPU e dai dispositivi di I/O.

� La memoria centrale è un dispositivo di memorizzazionevolatile.

� Il SO è responsabile delle seguenti attività relative allagestione della memoria:• Tenere traccia di quali parti della memoria sono utilizzate e

da chi.

• Decidere quali processi caricare in memoria.

• Allocare e deallocare lo spazio di memoria.


Gestione dei File

� Un file è una collezione di informazioni collegate tra loro e definite dal suo creatore. Di solito un file rappresenta o un programma (sorgente o oggetto) o dei dati.

� Il SO è responsabile delle seguenti attività relative alla gestionedei file:• Creazione e cancellazione dei file.

• Creazione e cancellazione di directory (cartelle).

• Mettere a disposizione primitive per la manipolazione di file e directory.

• “Mappare” i file su dispositivi di memorizzazione secondaria e/o altri dispositivi di I/O.

• Gestire il backup dei file.


Gestione dell’I/O

� Il sistema di gestione dell’I/O consiste in:• Un sistema di buffer-caching

• Una interfaccia generale per i driver dei dispositivi

• Driver per specifici dispositivi hardware


Gestione della Memoria Secondaria

� La maggior parte dei moderni computer utilizza i dischi come principale mezzo di memorizzazione sia per programmi sia per i dati.

� Il SO è responsabile delle seguenti attività relative alla gestione dei dischi:• Gestione dello spazio libero

• Allocazione dellospazio

• Scheduling del disco


Gestione delle Reti

� Un sistema distribuito è una collezione di processori che non condividono ne la memori ne il clock.

� Il SO è responsabile delle seguenti attività relative alla gestione delle reti:• Invio e ricezione di messaggi

• Instradamento e gestione delle connessioni

• Gestione dei conflitti

• Gestione della sicurezza


Sistema di Protezione

� La protezione si riferisce al meccanismo per controllare l’accesodi processi e utenti alle risorse di un utente e a quelle disistema.

� Il sistema di protezione deve:• distinguere tra un utilizzo autorizzato ed uno non autorizzato

• specificare quali controlli devono essere eseguiti ed i mezzi per effettuarli


Interprete dei Comandi� Gran parte dei comandi sono dati al SO per mezzo di istruzioni.

Tali istruzioni permettono:• la creazione e la gestione dei processi• la gestione dell’I/O• la gestione della memoria secondaria• secondary-storage management• la gestione della memoria centrale• l’accesso al file system• la protezione delle risorse• il networking

� Il programma che legge ed interpreta tali istruzioni è chiamato in diversi modi: • interprete comandi• shell (in UNIX)• prompt di MS-DOS (in MS Windows)

� Esistono anche interpreti basati su interfacce grafiche• Finder (MacOS)• Explorer (MS Windows)• X Windows (Unix)


Servizi di un SO

� Caricamento ed esecuzione dei programmi.

� Operazioni di I/O – siccome un utente non può eseguirele operazioni di I/O direttamente, il SO deve fornire ilmodo di eseguirle.

� Manipolazione del File-system – la possibilità per un processo o un utente di leggere, scrivere, creare e cancellare file.

� Comunicazione – la possibilità per due processi (sullastessa macchina o su due macchine differenti collegatetra loro in rete) di scambiarsi informazioni. Può essererealizzata attraverso la memoria condivisa o lo scambio di messaggi.


Comunicazione tra processi

Scambio di Messaggi Memoria Condivisa


Servizi di un SO (cont.)

� Rilevamento di errori.

� Allocazione delle risorse – a più utenti/processi inesecuzione nello stesso momento.

� Contabilizzazione dell’uso delle risorse – tenere traccia dichi e per quanto tempo ha utilizzato che cosa. Questoserve sia per raccogliere statistiche sul funzionamentodel sistema sia nei sistemi in cui l’accesso alle risorse è apagamento.

� Protezione – assicurare che l’accesso alle risorse delsistema sia controllato.


System Call

� Le system call costituiscono l’interfaccia tra un programma in esecuzione ed I servizi di un SO.

� Le chiamate alle system call sono realizzate tramite trap.

� Esistono tre metodi per il passaggio dei parametri:• I valori dei parametri vengono memorizzati nei registri.

• I valori dei parametri vengono memorizzati in una tabella in memoria e l’indirizzo della tabella viene memorizzato in un registro.

• I valori dei parametri vengono memorizzati dal programmacon una operazione di push nello stack e letti dal SO con una operazione di pop.


System Call


Passaggio parametri attraverso Tabella


Programmi di sistema

� Costituiscono l’ambiente di sviluppo ed esecuzione deiprogrammi:• Manipolazione e modifica file

• Stato del sistema

• Strumenti di ausilio alla programmazione

• Caricamento ed esecuzione di programmi

• Comunicazione

• Programmi di utilità

� Per la maggior parte degli utenti, il SO è caratterizzato daiprogrammi di sistema che mette a disposizione piuttostoche dalle system call.


Architettura Monolitica

Applicazione Applicazione

User mode

Kernel modeSystem services

Controllers


MS-DOS

� MS-DOS è stato scritto (da Tim Paterson) tenendo conto delle limitazioni dell’hardware e per dare il massimo delle funzionalità occupando il minimo spazio. Infatti MS-DOS, anche se ha un minimo di strutturazione:• non è diviso in moduli

• le interfacce e i livelli di funzionalità non sono ben separati


MS-DOS


UNIX

� UNIX – è stato scritto (da Ken Thompson) tenendo conto delle limitazioni dell’hardware. Quindi lo UNIX originale ha una strutturazione limitata. Il sistema consiste di due parti: • programmi di sistema

• il kernel

> tutto ciò che è compreso tra l’interfaccia con le system call e l’hardware del sistema

> tutte le funzioni di gestione della CU, della memoriaed altre ancora sono riunite in un unico livello.


UNIX


Architettura Stratificata

� Il SO è suddiviso in un certo numero di strati (chiamati livelli).

� Ogni strato è costruito sopra gli strati precedenti. Il livello piùbasso (livello 0) è l’hardware ed il livello più alto (livello N) è l’interfaccia utente.

� Per rendere il sistema modulare, i livelli sono definiti in modotale che ogni livello utilizza soltanto funzioni (operazioni) e servizi che appartengono ai livelli inferiori.


Applicazione Applicazione Applicazione

Controllers

Architettura Stratificata

User modeKernel modeoperazioni strato M visibili dalle applicazioni

operazioni strato M nascoste

layer M-1 operazioni strato M-1 visibili dallo strato M

operazioni strato M-1 nascoste

layer M

layer 1 operazioni strato 1 visibili dallo strato 2

operazioni strato 1 nascoste

layer …


OS/2


Architettura a Microkernel (Client/Server)� Spostare tutto quanto è possibile dal kernel allo spazio “utente”.

� La comunicazione tra i moduli utente avviene utilizzando lo scambio di messaggi.

� Benefici:

- è più facile estendere un microkernel

- è più facile fare il porting del SO su nuove architetture

- si adatta più facilmente ai sistemi distribuiti

- più affidabile (meno codice gira in modalità kernel)

- più sicuro


Microkernel

User mode

Kernel mode

Applicazione(client)



Memory server

Network server

ChiamataRisposta

File server

Controllers

Architettura a Microkernel (Client/Server)


Windows NT


Symbian

Symbian adotta una architettura a microkernel

� È ad oggetti: invece di creare descrittori delle risorse vengonocreate istanze di classi opportune e le system call invocano i metodi di tali istanze

� È multitask e multithread

� Struttura:• nanokernel - lavora in kernel mode – si occupa di sincronizzazione

e scheduling delle operazioni

• microkernel – lavora in kernel mode – si occupa di gestione dei thread, scheduling dei processi, context switching, gestione della memoria, caricamento delle librerie, sincronizzazione di oggetti e comunicazione tra processi

• server layer – lavora in user mode – si occupa di gestione del display, delle socket, …

• user-mode applications – lavora in user mode – sono le applicazioni utente


Microkernel

User mode

Kernel mode




esock Wservetel

Controllers

Symbian

Nanokernel


Architettura Ibrida

� Le architetture a microkernel sono state ritenute da Linus Torvalds e da Ken Thompson inutilmente troppo complicate (memorabile la disputa con Andrew Tanenbaum nel 1992).

� È stata proposta da Linus Torvalds una architettura ametà strada tra l’architettura monolitica e quella stratificata.


Linux

Linux (scritto da Linus Torvalds) adotta una architettura ibrida

� adotta una architettura monolitica

� adotta i moduli • così non si deve ricompilare il kernel ogni volta che si

aggiunge un driver o una nuova funzionalità

• basta caricare il modulo e linkarlo dinamicamente per aggiungere una nuova funzionalità

• il modulo è software che gira in modalità kernel, se contiene degli errori può danneggiare il kernel (il sistema si può bloccare)


Linux� Come in gran parte delle implementazioni di Unix,

Linux ha tre componenti principali:• Kernel

• System libraries

• System utilities


Linux� Il kernel

• Realizza tutte le funzioni del sistema operativo e serve per isolare il resto del sistema dalle caratteristiche dell’hardware

• Viene eseguito in kernel mode ed ha accesso a tutte le risorse fisiche del sistema

• Tutto il codice del kernel e le strutture dati sono mantenuti nello stesso spazio degli indirizzi

� Le librerie di sistema• Definiscono un insieme standard di funzioni attraverso le

quali le applicazioni interagiscono con il kernel

• Vengono eseguite in user mode

� Le system utilities• Eseguono dei compiti di gestione specializzati

• Vengono eseguite in user mode


Linux� I moduli del kernel

• Sono sezioni del kernel che possono essere compilate,caricate e scaricate in modo indipendente dal resto del kernel.

• Un modulo del kernel tipicamente serve per realizzare un driver di un dispositivo, un file system o un protocollo di rete.

• Questo permette a terze parti di distribuire driver o file system che non possono essere distribuiti con licenza GPL.

• Questo permette a linux di essere configurato con un kernelminimo, senza moduli esterni.


Architettura a Macchine Virtuali� Una macchina virtuale porta alle estreme conseguenze

l’approccio stratificato. Tratta l’hardware ed il kernel del SO come facenti parte entrambi dell’hardware.

� Una macchina virtuale non offre alcuna funzionalità aggiuntiva, ma fornisce una interfaccia identica all’hardware sottostante

� In questo modo il SO crea l’illusione ad ogni processo di avere a sua completa disposizione un proprio processore con la sua memoria

� Le risorse del computer fisico sono condivise per creare le macchine virtuali. • Lo scheduling della CPU crea l’illusione per l’utente di avere un

processore a sua completa disposizione.

• Lo spooling ed il file system creano l’illusione per l’utente di avere a propria completa disposizione sia la stampante sia l’unità a disco.

• ....


Non-virtual Machine Virtual Machine

Architettura a Macchine Virtuali


Vantaggi e Svantaggi

� Il concetto di macchina virtuale fornisce una completaprotezione alle risorse del sistema, infatti ogni macchinavirtuale è isolata dalle altre. Questo isolamento non permette però di condividere le risorse (si pensi al disco).

� Una macchina virtuale è il veicolo ideale per la ricerca e lo sviluppo di nuovi SO. Infatti lo sviluppo viene fatto sullamacchina virtuale e questo non danneggia il normalefunzionamento della macchina.

� Una macchina virtuale è difficile da realizza a causa delladifficoltà nel fornire un esatto duplicato della macchinasottostante.

� Il concetto di macchina virtuale è ritornato di moda recentemente per risolvere i problemi di interoperabilità • VMware (http://www.vmware.com/)• la macchina virtuale di Java

Architettura a Macchine Virtuali


Java Virtual Machine� I programmi compilati Java sono dei bytecode indipendenti dalla

piattaforma e possono essere eseguiti da una Java Virtual Machine (JVM).

� JVM consiste in

- un class loader

- un class verifier

- un interprete

� I compilatori Just-In-Time (JIT) aumentano le prestazioni


Java Virtual Machine


Processi e Scheduling

� Processi e Thread• I processi e le operazioni sui processi• I thread e le operazioni sui thread• I processi e i thread Linux• I processi e i thread Symbian

� Scheduling dei processi• Criteri di scheduling• Algoritmi di scheduling

� FCFS� SJF� Priorità� RR� Multilevel queue

• Lo scheduling in Linux• Lo scheduling in Symbian


ProcessoProcesso = Programma in esecuzione.

Formalmente:P = (C , S)

� P : processo� C : codice eseguibile� S : stato dell’esecuzione

fanno parte dello stato di esecuzione di un processo:• program counter • altri registri della CPU• stato del processo• stack• data section• lista dei file aperti• ….


Diagramma di Stato di un Processo


Process Control Block (PCB)o descrittore di processo

Le informazioni relative ad un processo (il suo stato di esecuzione) sono contenute in una struttura dati apposita.

� Stato� Program counter� Registri della CPU� Informazioni sullo scheduling CPU� Informazioni sulla gestione della memoria� Informazioni sullo stato dell’I/O� Informazioni contabili


Process Control Block (PCB)


Switch della CPU tra i Processi

� Context-switch produce overhead.� Il tempo di switch dipende dal supporto hardware a disposizione.


Operazioni su Processi: CreazioneIl processo è un tipo di dato astratto sul quale sono state definite alcune operazioni fondamentali, la prima è quella di creazione.

� Un processo padre può creare dei nuovi processi che vengonodetti processi figli che a loro volta possono creare altri processi, formando un albero dei processi.

� Condivisione risorse• Genitore e figli condividono tutte le risorse. • I figli condividono un sottoinsieme delle risorse del genitore. • Genitore e figli NON condividono risorse.

� Esecuzione• Genitore e figli vengono eseguiti concorrentemente. • Il Genitore attende che tutti o alcuni figli terminino.

� Spazio degli indirizzi• Il figlio è un duplicato del genitore.• Nel figlio viene caricato un programma (eventualmente diverso da

quello del genitore).


Albero dei Processi in Unix� In UNIX:

• La system call fork crea un nuovo processo• La system call exec sostituisce lo spazio di memoria corrente del

processo con un nuovo programma.


� Un processo esegue l’ultima istruzione e chiede al SO di essere cancellato (exit).

• Può riportare alcuni dati al processo genitore che li riceve con una istruzione (wait).

• Tutte le risorse del processo sono deallocate dal SO.� Un genitore può terminare i processi figli (abort) per diverse

ragioni:• Il figlio ha ecceduto le risorse allocate• Il compito assegnato al figlio non è più necessario• Il genitore stesso deve terminare la sua esecuzione

� e il SO non permette ai figli di continuare dopo la terminazionedei padri.

� Terminazione a cascata.

Operazioni su Processi: Terminazione


Esempio#include <stdio.h>

void main (int argc, char *argv[])

{

pid = fork(); /* genera nuovo processo */

if (pid < 0) { /* errore */

fprintf(stderr,“creazione nuovo processo fallita”);

exit(-1);

}

else if (pid == 0) { /* processo figlio */

execlp(“/bin/ls”, “ls”, NULL);

}

else { /* processo padre */

wait( NULL); /* attende terminazione figlio */

printf(“il processo figlio ha terminato”);

exit(0);

}

}


Thread

Processo a thread singolo Processo multithread• Prontezza• Condivisione delle risorse• Economicità• Utilizzazione di architetture multiprocessore

Benefici:


ThreadLo spazio di indirizzamento è condiviso (viene usata la stessa coppia di registri “base e limite” per tutti i thread di un processo).

Ogni thread tuttavia ha un suo stato (ready, running, waiting), i suoi registri di CPU (stato della computazione), incluso il program counter, stack pointer, ecc., il suo stack.

NON VI È PROTEZIONE FRA THREAD: i thread si potrebbero “pasticciare” i dati

(per esempio quelli sullo stack) a vicenda...


Thread� Thread a livello utente – i thread sono gestiti da una libreria a

livello utente. Esempi:- POSIX Pthreads- Mach C-threads- Solaris threads

� Thread a livello kernel – le funzionalità dei thread sono messe a disposizione e gestite direttamente dal kernel. Esempi:- Windows 95/98/NT/2000- Solaris- Tru64 UNIX- BeOS- Linux- Symbian

Modelli di Multithreading: � Molti-a-Uno� Uno-a-Uno� Molti-a-Molti


Modello Molti-a-Uno� Molti thread a livello utente sono mappati ad un singolo

thread a livello kernel. � Viene usato nei sistemi che non forniscono thread a livello

utente.


Vantaggi• Tempo di context switch (fra thread di uno stesso processo) molto basso (non c’è il passaggio a kernel mode)• Puo' essere implementato al di sopra di qualsiasi sistema operativo

Svantaggi• È complesso fare in modo che quando un thread ha bisogno di eseguire una system call bloccante non vengano bloccati anche gli altri thread nello stesso processo (perché il S.O. memorizza nel PCB del processo “stato = bloccato” e non gli assegna tempo di CPU finché la system call bloccante non viene servita)• Solo un thread running per processo anche se il sistema è multiprocessore•Potrebbe non essere banale gestire i thread in time sharing (quindi occorre basarsi sulla “buona volontà” dei thread che periodicamente cedono il passo con una esplicita richiesta di thread_yield al RTE)

Sistema Operativo

Ambiente Run Timeper la gestione dei thread

tabella dei processi

tabella dei thread

Applicazione Multithreadedthread_create

tid

Molti-a-Uno


Modello Uno-a-Uno� Ogni thread a livello utente si mappa ad un thread a livello

kernel. Esempi:- Windows 95 in poi- OS/2


Vantaggi

• In un sistema con molte CPU èpossibile avere più di un thread running per processo• La gestione di system callbloccanti non pone alcun problema: il sistema è sempre in grado di schedulare i thread pronti ad eseguire anche se uno o più altri thread nello stesso processo sono bloccati in attesa di un evento.

Svantaggi

• Il tempo di context switch fra thread di uno stesso processo, anche se meno costoso di un context switch fra processi diversi, è comunque costoso perchérichiede il passaggio a modalitàkernel

• Il sistema operativo deve predisporre strutture dati per gestire tutti i thread: questo pone limitazioni sul numero massimo di thread che possono essere attivati all'interno di ciascun processo e complessivamente nel sistema

Sistema Operativotabella dei processie dei threads

Applicazione Multithreadedthread_create

tid

Uno-a-Uno


Modello Molti-a-Molti� Diversi thread a livello utente sono mappati a diversi thread a

livello kernel. � Questo permette al SO di creare un numero sufficiente di

thread a livello kernel. • Windows NT/2000 con il ThreadFiber package• Solaris 2


Sistema Operativo

Ambiente Run Timeper la gestione dei thread

tabella dei processie dei kernel threads

tabella dei thread utente

Applicazione Multithreadeduser_thread_create

utid

kernel_thread_create

ktid

L’RTE potrebbe richiedere un nuovo kernel thread ogni volta che viè almeno uno user thread in stato ready ma tutti gli altri kernelthread assegnati al processo sono waiting a causa di qualche system call bloccante. Parte dei context switch avverrebbe ancora all’interno dell’RTE (in user mode).

Molti-a-Molti


Vantaggi• In sistemi multi-CPU è possibile avere piu' thread running per processo• Il context switch fra thread a livello utente avviene in modalità utente, a cura del sistema run-time; Il SO effettua il context switch di kernel threads, che risulterà un po' meno costoso nel caso di context switchtra kernel threads associati ad uno stesso processo perchè queste condivideranno lo spazio di indirizzi, e quindi la tabella delle pagine) • La gestione di system callbloccanti non pone grossi problema: il SO e' in grado di schedulare ikernel thread pronti di un dato processo anche se una o piu' altre kernel thread dello stesso processo sono bloccati in attesa di un evento.

Svantaggi• Il modello è più complicato e richiede che lo scheduler (del S.O.) della CPU e lo scheduler dei threads a livello utente (parte del supporto run-time del thread package) collaborino.• Le priorità associate ai threadspotrebbero non essere rispettate dallo scheduler della CPU, che vede solo i threads associati alle kernel entities.• Il SO deve predisporre strutture dati per gestire i kernel thread:dato che queste dovrebbero essere in numero decisamente inferiore al numero di threadutente ci sono meno problemi di allocazione di risorse rispetto allo schema con soli thread a livello kernel.

Molti-a-Molti


Pthreads� PTHREADS è una API standard (è parte dello standard POSIX -

IEEE 1003.1c) per la creazione e la sincronizzazione dei thread.� La API specifica il comportomanto della libreria di thread, la

realizzazione è lasciata allo sviluppatore della libreria.� È diffusa soprattutto nei SO della famiglia UNIX.


Esempio#include <pthread.h>

#include <stdio.h>

int somma; /* questo dato è condiviso dai thread */

void *runner(void *param) /* il thread */

void main (int argc, char *argv[])

{

pthread_t tid; /* identificatore del thread */

pthread_attr_t attr; /* attributi del thread */

if (arcgc != 2) || (atoi(argv[1]) < 0) /* errore */

exit(-1);

else {

/* reperisce gli attributi predefiniti */

pthread_attr_init(&attr);

/* creazione del thread */

pthread_create(&tid,&attr,runner,argv[1]);

/* attende la terminazione del thread */

pthread_join(tid,NULL);

}

}


Esempio/* codice del thread */

void *runner(void *param)

{

int sup, i;

sup = atoi(param);

somma = 0;

if (sup > 0) {

for (i = 1; i <= sup; i++)

somma += 1;

}

pthread_exit(0); /* terminazione del thread */

}


I Task di Linux� Linux utilizza la stessa rappresentazione interna sia per I

processi sia per i thread che in entrambi i casi vengono chiamati task.

� L’unica differenza è che un thread è un task che condivide lo stesso spazio degli indirizzi con il genitore mentre il processo ha uno spazio degli indirizzi diverso.

� Questa differenza viene indicata in fase di creazione del task effettuando una system call opportuna

• fork crea un nuovo task con un suo nuovo contesto• clone crea un nuovo task con una sua identità propria, ma con le

strutture dati condivise con il suo genitore� Le proprietà di un task linux possono essere classificate in tre

categorie:• Identità del task• Ambiente del task• Contesto del task


I Task di Linux Identità di un Task

� Process ID (PID). Identifica in modo univoco un task. Per esempio, se una applicazione deve effettuare una system call per inviare un messaggio, modificare o attendere un task, il parametro da passare al SO è il PID del task.

� Credential. Ad ogni task viene associato uno user ID ed uno o più group ID. Serve per determinare i diritti di accesso del task a risorse e a file.

� Personality. Questa caratteristica non di trova nei tradizionali sistemi Unix. Sotto Linux, ad ogni task viene associato un personality ID. Modifica la semantica di certe system call. Principalmente viene utilizzato da librerie di emulazione per rendere le system call compatibili con determinate caratteristiche di Unix.


I Task di Linux Ambiente di un task

� Ogni task eredita dal genitore due vettori:• Il vettore degli argomenti contiene tutti gli argomenti presenti nella

linea di comando per avviare il programma. Convenzionalmente il primo argomento è il nome del programma stesso. Questo è uno strumento per parametrizzare l’esecuzione dei programmi.

• Il vettore dell’ambiente è una lista di coppie del tipo “NAME=VALUE”

che associa ad ogni variabile di ambiente un valore.In questo modo ogni task può avere il SO configurato ad hoc, invece di avere una configurazione unica per tutti i task.

• Inoltre le variabili possono essere utilizzate per passare informazioni da un task ad un altro.

� Far ereditare ad un task l’ambiente del task genitore è un modo per far passare informazioni dal genitore al figlio.


I Processi LinuxContesto di un task

� Lo scheduling context è la parte più importante. Sono le informazioni necessarie allo scheduler per sospendere e riattivare un task.

� Informazioni contabili su tutte le risorse usate attualmente ed utilizzate fino a quel momento dal task.

� La tabella dei file aperti. � La signal-handler table indica quali routine (appartenenti allo

spazio degli indirizzi del task) devono essere chiamate quando al task arriva uno specifico segnale (signal).

� La virtual-memory context indica l’intero contenuto dello spazio degli indirizzi del task.

Lo stato dell’esecuzione di un task (le informazioni contenute in un descrittore di task).


I Processi Symbian� Un processo in Symbian OS è un insieme di thread che sono in

esecuzione concorrentemente.� Ogni processo ha un proprio spazio degli indirizzi privato. � Un processo può creare un altro processo.� Ogni processo ha una sua priorità.� Un descrittore di processo è un oggetto del kernel, al quale si

può accedere attraverso un handle handle (l’interfaccia è fornita da RProcess).


I Thread Symbian� Un thread in Symbian OS è l’unità di esecuzione.� Ogni processo ha un thread primario che viene creato al

momento della inizializzazione del processo stesso. � Un thread può creare, sospendere, riattivare, eliminare un altro

thread� Un thread può passare dati ad altri thread sia dello stesso

processo sia di un altro processo.� Ogni thread ha una sua priorità:

• di default ogni thread riceve la priorità del processo a cui appartiene,

• tale priorità si può modificare.� Un descrittore di thread è un oggetto del kernel, al quale si può

accedere attraverso un handle (l’interfaccia è fornita da RThread).


Gli Active Object Symbian� Un active object in Symbian OS permette la programmazione ad

eventi (orientata agli oggetti).� Ogni thread ha un insieme di active object.� Ogni active object è una classe collegata ad uno specifico tipo

di evento: bisogna indicare quale è l’evento e quale è il metododi risposta all’evento.

� Ogni evento ha la sua priorità.� Quando si verifica un determinato evento, viene creata una

istanza dell’active object corrispondente.� Se un evento si verifica quando un altro active object è già

attivo, viene messo in coda anche se ha una priorità più alta.


Processi e Scheduling

� Processi e Thread� I processi e le operazioni sui processi� I thread e le operazioni sui thread� I processi e i thread Linux� I processi e i thread Symbian

� Scheduling dei processi• Criteri di scheduling• Algoritmi di scheduling

� FCFS� SJF� Priorità� RR� Multilevel queue

• Lo scheduling in Linux• Lo scheduling in Symbian


Code di Scheduling dei Processi

Job QueueEsiste inoltre una coda di tutti i processi del sistema


Scheduling dei Processi


Sequenza di CPU Burst e I/O BurstL’esecuzione di un processo consiste di un ciclo di esecuzione nella CPU e di attesa dell’I/O.


Distribuzione dei CPU-burst


CPU-bound e I/O-bound� I processi possono essere:

• Processi I/O-bound – impiegano più tempo per l’I/O che per le elaborazioni, hanno molti CPU bursts di breve durata.

• Processi CPU-bound – impiegano più tempo nelle elaborazioni cheper l’I/O, hanno pochi CPU bursts ma di lunga durata.


Scheduler� Scheduler a lungo termine (o job scheduler) – seleziona tra i

processi in stato di new quelli da caricare in memoria.• E’ invocato di rado (secondi, minuti) ⇒ (può essere lento).• Deve massimizzare il grado di multiprogrammazione senza far

degradare le prestazioni del sistema.

� Scheduler a medio termine – seleziona tra i processi “scaricati” dalla memoria (swapped-out) quelli da caricare (swap in) nuovamente in memoria.

• E’ invocato di rado (secondi) ⇒ (può essere lento).• Deve evitare il degrado delle prestazioni del sistema.

� Scheduler a breve termine (o CPU scheduler) – seleziona tra i processi presenti nella ready queue il processo a cui allocare la CPU.

• E’ invocato di frequente (millisecondi) ⇒ deve essere molto veloce.• Deve massimizzare l’utilizzo della CPU


Job Scheduler• Controlla il grado di multiprogrammazione (possono essere caricati

nuovi processi in memoria senza provocare il trashing?).• Se sì, seleziona i processi che devono essere caricati in memoria. • I descrittori di tali processi vengono inseriti nella ready queue.• Lo stato di tali processi passa da new a ready.


Middle-term Scheduler• Controlla il grado di multiprogrammazione ed il rischio di degrado

delle prestazioni del sistema (trashing).• Se il grado di multiprogrammazione è troppo elevato (il sistema

rischia il trashing), seleziona i processi da scaricare (swap out).• Lo stato di tali processi passa a wait.• Se il grado di multiprogrammazione è sufficientemente basso,

seleziona i processi swapped-out che devono essere caricati in memoria (swap in).

• I descrittori di tali processi vengono inseriti nella ready queue.• Lo stato di tali processi passa da wait a ready.


CPU Scheduler� Seleziona un processo tra quelli presenti in memoria che sono

pronti per l’esecuzione ed alloca la CPU a tale processo. � Le decisioni riguardanti lo scheduling della CPU si possono

prendere nelle seguenti circostanze:1. Un processo passa dallo stato di running allo stato di waiting.2. Un processo passa dallo stato di running allo stato di ready.3. Un processo passa dallo stato di waiting allo stato di ready.4. Un processo termina.

� Scheduling senza diritto di prelazione (nonpreemptive) quando si assegna la CPU ad un processo, questo rimane in possesso della CPU fino a quando non la rilascia spontaneamente.

� Scheduling con diritto di prelazione (preemptive) quando il SO può obbligare un processo a rilasciare la CPU anche se il processo ne ha ancora bisogno.


Dispatcher� Dispatcher assegna il controllo della CPU al processo

selezionato dal short-term scheduler; questo comporta:• Commutazione di contesto (switching context)• Passaggio da modalità kernel a modalità utente• Salto alla locazione di memoria appropriata per far ripartire il

programma utente� Latenza di Dispatch – il tempo necessario a fermare un

processo e a far partire un altro.


Criteri di Scheduling� Utilizzo della CPU – tenere la CPU occupata il più

possibile da massimizzare� Produttività (Throughput) – numero di processi

che completano la loro esecuzione per unità di tempo da massimizzare

� Tempo di Completamento (Turnaround Time) –il tempo di esecuzione di uno specifico processo da minimizzare

� Tempo di attesa – quanto tempo in totale un processo è rimasto nella coda di ready da minimizzare

� Tempo di risposta – quanto tempo passa dal momento in cui la richiesta è stata sottomessa al momento in cui viene prodotta la prima risposta (non il suo output) – per i sistemi time-sharing da minimizzare


First-Come, First-Served (FCFS)

Process Burst TimeP1 24P2 3P3 3

� Supponiamo che l’ordine di arrivo dei processi sia: P1 , P2 , P3 Il diagramma di Gantt risulta essere il seguente:

� Tempi di attesa: P1 = 0; P2 = 24; P3 = 27� Tempo medio di attesa: (0 + 24 + 27)/3 = 17

P1 P2 P3

24 27 300


FCFS (Cont.)Supponiamo che l’ordine di arrivo sia invece il seguente:

P2 , P3 , P1 .� Il diagramma di Gantt diventa:

� Tempi di attesa: P1 = 6; P2 = 0; P3 = 3� Tempo medio di attesa: (6 + 0 + 3)/3 = 3� Il miglioramento è considerevole.� Effetto convoglio: I processi brevi si accodano ai processi

lunghi.

P1P3P2

63 300


Shortest-Job-First (SJR)� Questo algoritmo associa a ogni processo la lunghezza del CPU

burst successivo.� La CPU viene assegnata al processo con il CPU burst

successivo più breve.� Due schemi:

• Senza prelazione – il processo mantiene il possesso della CPU fino a quando non completa il CPU burst attuale.

• Con prelazione – se arriva un nuovo processo con un CPU burst inferiore del CPU burst che resta al processo attualmente in esecuzione. Questo schema viene chiamato anche Shortest-Remaining-Time-First (SRTF).

� SJF è ottimale – minimizza il tempo medio di attesa.


Process Arrival Time Burst TimeP1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4

� SJF (non-preemptive)

� Tempo medio di attesa = (0 + 6 + 3 + 7)/4 = 4.25

Non-Preemptive SJF

P1 P3 P2

73 160

P4

8 12


Preemptive SJFProcess Arrival Time Burst Time

P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4

� SJF (preemptive)

� Tempo medio di attesa = ( ((0 - 0)+(11 – 2)) + ((2 - 2)+(5 - 4)) + (4 – 4) + (7 – 5) ) / 4 =

P1 P2 P3 P4(9 + 1 + 0 + 2)/4 = 3

P1 P3P2

42 110

P4

5 7

P2 P1

16


Lunghezza del CPU Burst Successivo� Può essere solo stimata.� Si può utilizzare la media esponenziale dei CPU burts

precedenti.

1. tn = lunghezza effettiva dell’n-esimo CPU burst2. τn = lunghezza stimata dell’n-esimo CPU burst3. α = peso, dove 0 ≤ α ≤ 14. c = stima iniziale del primo CPU burst

τn+1 = α tn + (1 – α) τn

τ1 = c


Lunghezza del CPU Burst Successivo


Media Esponenziale� α =0

• τn+1 = τn = … = τ1

• La storia recente del processo non conta.� α =1

• τn+1 = tn• Conta solo l’ultimo CPU burst.

� Se espandiamo la formula otteniamo:

τn+1 = α tn+(1 - α) α tn -1 + …

+(1 - α )j α tn - j + …

+(1 - α )n τ1

= (1 - α )j α tn - j + (1 - α )n τ1

� Siccome sia α sia (1 - α) sono minori o uguali ad uno, ogni termine ha un peso minore dei termini precedenti.

Σn-1

j=0


Scheduling per Priorità� Ad ogni processo viene associata una priorità (un numero

intero)� La CPU viene allocata al processo con la priorità più alta

(numero piccolo ≡ alta priorità).• Con prelazione• Senza prelazione

� SJF è uno scheduling per priorità dove la priorità è la lunghezza del CPU burst successivo.

� Problema ≡ Starvation – processi con bassi priorità potrebbero non ricevere mai la CPU.

� Soluzione ≡ Aging – con il passare del tempo nella coda di ready, la priorità viene aumentata.


Round Robin (RR)� Ogni processo riceve la CPU per una piccola unità di tempo

(quanto di tempo), di solito 10-100 millisecondi. Allo scadere di questo quanto di tempo il processo è prelazionato ed aggiunto alla coda dei processi ready.

� La coda dei processi di ready viene gestita come una coda (FIFO) circolare.

� Se ci sono n processi nella coda di ready e il quanto di tempo è q, allora ogni processo non aspetta più di (n-1)q unità di tempo.

� Le prestazioni dipendono da q• q molto grande ⇒ RR diventa FCFS• q molto piccolo ⇒ q deve essere molto più grande del tempo di

commutazione di contesto, altrimenti l’overhead è troppo elevato.


RR con Quanto di Tempo = 20

Process Burst TimeP1 53P2 17P3 68P4 24

� Il diagramma di Gantt è il seguente:

� Tipicamente ha un tempo medio di completamento maggiore di SJF, ma ha un tempo di risposta migliore.

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162


Quanto di Tempo e Numero di Commutazioni


Tempo di Completamento e Quanto di Tempo


Multilevel Queue� Questo algoritmo di scheduling suddivide la coda di ready in

diverse code distinte. Ad esempio:• Processi foreground (interattivi)• Processi background (batch)

� Ogni coda adotta un proprio algoritmo di scheduling, ad esempio:

• foreground – RR• background – FCFS

� È inoltre necessario avere uno scheduling tra le code.• Priorità fissa con prelazione; (per esempio vengono serviti prima

tutti i processi foreground e poi quelli background). Possibilità di starvation.

• Time slice – ogni coda ha a disposizione una certa quantità di tempo di CPU per i propri processi: ad esempio � 80% ai processi foreground in RR� 20% ai processi background in FCFS


Multilevel Queue


Multilevel Feedback Queue� Un processo può passare da una coda ad un’altra.� Ad esempio un processo che usa troppo la CPU si può spostare

in una coda con priorità minore. Questo schema mantiene i processi con prevalenza di I/O e i processi interattivi nelle code con priorità elevata.

� Analogamente un processo che attende da troppo tempo si può spostare in una coda con priorità maggiore (ovvero questo è un modo per implementare l’aging).


Multilevel Feedback Queue� Scheduling

• Un nuovo processo entra nella coda Q0. Quando ottiene la CPU, riceve 8 millisecondi. Se non finisce in 8 millisecondi, il processo viene spostato nella coda Q1.

• Nella coda Q1, quando il processo ottiene di nuovo la CPU, riceve 16 millisecondi. Se ancora non bastano, al termine del quanto di tempo il processo è spostato in Q2.

• Nella coda Q2, quando il processo ottiene di nuovo la CPU, va avanti fino al suo completamento o a una sua sospensione.


Scheduling in Linux� Contrariamente a quello che avviene in altri SO, in Linux lo

scheduling coinvolge sia i task che lavorano in modalità utente sia i task che lavorano in modalità kernel.

� La richiesta di una esecuzione in modalità kernel può avvenire in due modi diversi:

• Un programma in esecuzione può richiedere l’esecuzione di un task del kernel esplicitamente (tramite una system call) o implicitamente (quando si verifica un errore, ad esempio un pagefault).

• Un driver di un dispositivo può richiedere l’esecuzione di un task del kernel quando invia una interruzione hardware (che ha come effetto l’esecuzione del kernel-defined handler per quell’interrupt).


Scheduling in LinuxScheduling dei Task

� Linux usa due algoritmi di scheduling:• time-sharing quando è più importante l’equa distribuzione del tempo• real-time quando le priorità sono più importanti dell’equità

� L’identità di un task contiene anche la classe di scheduling, attraverso la quale si determina quale algoritmo applicare. Taliclassi sono:

• time-sharing• real-time RR• real-time FCFS:

� Un task in classe real-time ha priorità statica e goodness più alte rispetto ad un task in classe time-sharing

� Lo scheduler entra in azione• quando un task cede spontaneamente la CPU• quando il quanto di tempo riservato ad un task scade• quando un nuovo task entra nella coda dei task pronti e la sua

priorità è più alta della priorità dell'attuale task in esecuzione


Scheduling in LinuxScheduling Time-Sharing

� Per i task time-sharing, Linux usa un algoritmo per priorità basato sui crediti (RR con quanto dinamico).

• Ogni task ha:� rt_priorità = 0� ts_priorità0 = 20 – nice dove –19 ≤ nice ≤ 20� crediti0 = priorità / 4 di fatto è il suo quanto di tempo� goodnessn = ts_prioritàn + creditin

• Quando occorre assegnare la CPU, tra i task time-sharing la scelta cade sul task che ha il maggior numero di crediti.

• Ogni volta che si ha una interruzione dal timer, il task in esecuzione perde un credito.

• Quando i suoi crediti arrivano a zero, viene scelto un altro task.• Quando tutti i task hanno credito zero, vengono ricalcolati i crediti di

tutti i task del sistema (non solo quelli ready) con la formula:� creditin+1 = (creditin / 2) + (ts_prioritàn / 4)

• Questo sistema privilegia i task interattivi (I/O-bound). Infatti I task che restano gran parte del tempo in stato di wait non arrivano mai a zero con i loro crediti, anzi i loro crediti aumentano ad ogni ricalcolo.


� È uno scheduling real-time debole• Ogni task ha:

� 1 ≤ rt_priorità ≤ 99� ts_priorità0 non definita� crediti0 non definita� goodness = rt_priorità + 1000

• Lo scheduler esegue i task con la rt_priorità più alta, a parità di rt_priorità quelli che attendono da più tempo.

• I task in classe FIFO continuano fino a quando non rilasciano laCPU spontaneamente o arriva un task con rt_priorità maggiore.

• I task in classe RR vengono interrotti allo scadere del loro quanto di tempo e rimessi in coda oppure arriva un task con rt_priorità maggiore.

Scheduling in LinuxScheduling Real-Time


Scheduling in SymbianLo scheduler dei thread in Symbian OS è di tipo multilevel queue.� Lo scheduling delle code è una variante soft real-time dello

scheduling per priorità con prelazione: scheduling statico monotono.

• Ogni processo ha una deadline (scadenza) entro la quale deve essere completato.

• I processi sono organizzati in modo da dare la priorità più alta ai processi che hanno la scadenza più vicina.

• Lo scheduler gestisce 64 code.• I thread hanno una priorità che può essere assoluta (non dipende da

quella del processo al quale appartengono) o relativa (è funzione della priorità del processo).

• Quando arriva un thread con priorità più alta, toglie la CPU al thread attualmente in stato di RUNNING.

� Lo scheduling dei thread di una coda è di tipo round robin.� Lo scheduling degli active object è per priorità senza prelazione.

• Gli active object hanno un sistema di priorità diverso da quello di processi e thread.


970 Kernel supervisor850 Real-time servers750 File server650 Window server470 Comms server500 absolute thread priority EPriorityAbsoluteHigh450 Font & Bitmap server, high priority tasks400 absolute thread priority EPriorityAbsoluteForeground350 Normal process priority, foreground UI app, EPriorityForeground300 absolute thread priority EPriorityAbsoluteBackground250 Background UI app, low-priority threads200 absolute thread priority EPriorityAbsoluteLow150 background threads100 absolute thread priority EPriorityAbsoluteVeryLow

0 Null (idle) thread – power saving

Scheduling in SymbianPriorità di processi e thread


Scheduling in Symbian� Priorità relativa dei thread: process_priority + thread_priority_weighting

• un thread può variare la sua priorità rispetto a quella del processo che l’ha generato di ± 10 o ± 20

• se viene modificata la priorità del processo di q, anche la prioritàdel thread viene variata di q

• Esempio – processo con priorità pari a EPriorityForeground

thread_priority_weighting

• Se la priorità del processo viene diminuita di 100, anche il thread avrà la sua priorità diminuita di 100

� Priorità assoluta dei thread• se a un thread assegniamo una priorità assoluta, questa non varia

al variare della priorità del processo

370 EPriorityMuchMore360 EPriorityMore350 EPriorityNormal (default)340 EPriorityLess330 EPriorityMuchLess

0 EPriorityNull100 EPriorityAbsoluteVeryLow200 EPriorityAbsoluteLow300 EPriorityAbsoluteBackground400 EPriorityAbsoluteForeground500 EPriorityAbsoluteHigh850 EPriorityRealTime


Gestione della Memoria� Introduzione

• Codice rilocabile• Swapping

� Gestione della Memoria• Allocazione contigua• Paginazione• Segmentazione• Segmentazione con Paginazione

� Memoria Virtuale• Paginazione su richiesta• Algoritmi di sostituzione delle pagine: FIFO, Ottimale, LRU, Orologio• Algoritmi di assegnazione dei frame liberi: Uniforme, Proporzionale,

per Priorità, basata sul Working Set, basata su Page Fault Rate� Gestione della Memoria in Linux

• Memoria Fisica• Memoria Virtuale


Introduzione� Un programma in genere risiede in un disco sotto forma di file

binario eseguibile.

� Il programma per essere eseguito deve essere caricato inmemoria ed inserito all’interno di un processo.

� Coda di Ingresso (input queue) – insieme di processi che devono essere caricati in memoria per essere eseguiti (se èpresente lo scheduler a lungo termine, la coda viene gestita dallo scheduler a lungo termine).

� I programmi utente passano attraverso diversi passi prima di poter essere eseguiti.

Sistemi di Elaborazione A.A. 2004/2005 3Fasi

di E

labo

razi

one

diun

Prog

ram

ma

Codice Sorgente

Modulo Oggetto

Codice EseguibileLibreria di sistema

Libreria di sistemacaricata

dinamicamente

Compilatoreo Assembatore

Linker

Caricatore(loader)

Processo(immagine in

memoria)

Altri modulioggetto

dynamic linking

compile time

load time

run time


Binding di Istruzioni e Dati a Indirizzi di Memoria

� Compilazione: Se è noto a priori dove il processo risiederà in memoria, può essere generato un codice assoluto, che contiene direttamente indirizzi assoluti; se la locazione di inizio cambia, bisogna ricompilare il programma. Un esempio sono i .com di MS-DOS

� Caricamento: Se dove il processo risiederà in memoriaNON è noto a priori, il compilatore genera un codice rilocabile, che contiene indirizzi rilocabili. È compito delcaricatore fare il binding tra indirizzi rilocabili e gli indirizzi assoluti (rilocazione statica).

� Esecuzione: Se durante l’esecuzione il processo può essere spostato da un segmento di memoria ad un altro,il binding deve essere ritardato fino al momento dell’esecuzione (rilocazione dinamica). È necessario dell’hardware di supporto per gestire questa situazione (per esempio I registri base e limite). La maggior parte dei SO d’uso generale impiega questo metodo

Può avvenire in una qualsiasi delle seguenti fasi.


Spazio di Indirizzi Logici e Fisici� Per una corretta gestione della memoria abbiamo bisogno di

due tipi di spazio di indirizzi separati tra loro, anche se esiste unlegame che li unisce.

• Indirizzi Logici (Indirizzi Virtuali) – sono gli indirizzi generati dallaCPU, cioè quelli che vengono messi in RIp, il registro indice dellaCPU, e trasmessi attraverso il bus indirizzi.

• Indirizzi Fisici – sono gli indirizzi visti dalla unità di memoria, cioè quelli che vengono messi in RIm, il registro indice della Memoria(anche chiamato MAR – Memory Address Register).

� Indirizzi logici e fisici coincidono quando il binding viene fatto infase di compilazione o caricamento, sono diversi quando ilbinding viene fatto in fase di esecuzione

� Il programma utente ha a che fare con gli indirizzi logici e nonvede mai gli indirizzi fisici.

� L’hardware che traduce gli indirizzi logici in fisici è il Memory Management Unit (MMU).


Memory-Management Unit (MMU)• Usa il registro di rilocazione (al posto del registro base). Il suo valore

viene sommato a tutti gli indirizzi generati dalla CPU.• N.B. l’uso del registri base è diverso, infatti il registro base viene

confrontato con (e NON sommato a) l’indirizzo generato dalla CPU.

346

1000 14000

143461346

error


Swapping (Avvicendamento)� Un processo può che si trova in memoria centrale, può essere

temporaneamente trsferito nella memoria secondaria, per far posto inmemoria centrale ad un altro processo. Successivamente, quando deve riprendere la sua esecuzione, viene riportato in memoria centrale.

� Il tempo di swapping è un fattore critico.



� Codice rilocabile� Swapping

� Gestione della Memoria• Allocazione contigua• Paginazione• Segmentazione• Segmentazione con Paginazione





Allocazione Contigua – Partizioni Fisse � La memoria viene suddivisa in un certo numero di partizioni di

dimensione fissa.� Ogni processo viene caricato in una partizione.� Quando un processo termina l’esecuzione, libera una partizione

che può essere occupata da un altro processo in attesa nellacoda di ingresso (singola o multipla).

� Il grado di multiprogrammazione è limitato dal numero di partizioni


�All’inizio ci sono due partizioni, una allocata al SO e l’altra (il resto della memoria) è libera.

� Il SO conserva in una tabella le partizioni libere (buchi) e lepartizioni allocate, ognuna con dimensioni diverse dalle altre.

�Quando arriva un processo, viene allocato in un buco abbastanza grande da contenerlo. La parte di buco non utilizzata viene lasciata come partizione libera per un altro processo.

OS

process 5

process 8

process 2

OS

process 5

process 2

OS

process 5

process 2

OS

process 5

process 9

process 2

process 9

process 10

Allocazione Contigua – Partizioni Variabili


� First-fit: Alloca il primo buco di dimensioni sufficienti.� Best-fit: Alloca il buco più piccolo in grado di soddisfare

la richiesta; bisogna scandire l’intera lista (a meno chenon sia ordinata per dimensione). Produce le parti di buco inutilizzate più piccole.

� Worst-fit: Alloca il buco più grande; bisogna scandire l’intera lista (a meno che non sia ordinata perdimensione). Produce le parti di buco inutilizzate più grandi.

Come soddisfare una richiesta di dimensione n avendo adisposizione una lista di buchi.

First-fit e best-fit sono migliori di worst-fit in termini di velocità e utilizzo della memoria.



In memoria sono presenti i seguenti spazi liberi:100K, 500K, 200K, 300K, 600K

(ordinati in base all’indirizzo di partenza). Come verrebbero allocati i seguenti processi:

P1 (212K), P2 (417K), P3 (112K), P4 (426K), utilizzando gli algoritmi First Fit, Best Fit e Worst Fit?

First Fit: P1 in 500K (rimane 288K), P2 in 600K (rimane 183K)

P3 in 288K (rimane 176K), P4 deve attendere

Best Fit: P1 in 300K (rimane 88K), P2 in 500K (rimane 83K)

P3 in 200K (rimane 88K), P4 in 600K (rimane 174K)

Worst Fit: P1 in 600K (rimane 388K), P2 in 500K (rimane 83K)

P3 in 388K (rimane 276K), P4 deve attendere



Frammentazione� Frammentazione Interna – la memoria allocata può essere più

grande di quella che effettivamente serve; la memoria in più èinterna alla partizione, ma non può essere usata.Tipica delle partizioni fisse.

� Frammentazione Esterna – la somma totale di tutti gli spazi liberi è sufficiente per contenere un nuovo processo, ma il processo non può essere caricato in memoria perché questi spazi non sono contigui.Tipica delle partizioni variabili.

� La frammentazione esterna può essere eliminata con lacompattazione.

• Riordina il contenuto della memoria per riunire la memoria libera in un unico buco.

• La compattazione è possibile solo se la rilocazione è dinamica.• La compattazione è costosa.


Paginazione� Lo spazio degli indirizzi logici può non essere contiguo.� La memoria fisica è divisa in blocchi di dimensioni fisse chiamati

frame (le dimensioni sono potenze di 2, tra 512 byte e 8192 byte).

� La memoria logica è divisa in blocchi chiamati pagine, le cuidimensioni sono pari a quelle dei frame.

� Bisogna tenere traccia di tutti i frame liberi.� Per eseguire un programma di dimensioni pari ad n pagine,

bisogna trovare n frame liberi e caricare le pagine in quei frame.� Viene usata una tabella delle pagine (di solito una per

processo) per tradurre gli indirizzi logici in indirizzi fisici. � Presenta il problema della frammentazione interna.


� Gli indirizzi generati dalla CPU si dividono in due parti:• Numero di pagina (p) – viene usato come indice della tabella delle

pagine che contiene l’indirizzo base di ogni pagina nella memoria fisica.

• Offset (d) – è lo scostamento all’interno della pagina.

Paginazione - Traduzione degli Indirizzi


Paginazione - Esempio


Paginazione - Esempio


Frame Liberi

Prima dell’assegnazione Dopo l’assegnazione


Realizzazione della Tabella delle Pagine� La Tabella delle Pagine è mantenuta in memoria.� Page-table base register (PTBR) indica l’inizio della Tabella

delle Pagine.� Page-table length register (PRLR) indica le dimensioni della

Tabella delle Pagine.� Con questo schema, per ogni accesso a dati/istruzioni ci sono

due accessi in memoria: uno alla Tabella delle Pagine ed uno ai dati/istruzioni veri e propri.

� Il problema del duplice accesso in memoria può essere risoltocon una speciale memoria associativa usata come cache. Questa memoria viene chiamata translation look-aside buffer(TLB)

� La memoria associativa permette di cercare in parallelo su tutti gli elementi quale sia uguale ad un valore dato.


Realizzazione della Tabella delle Pagine


Tempo Effettivo di Accesso con TLB� Tempo di accesso alla memoria associativa = ε unità di tempo� Tempo di accesso in memoria = 1 unità di tempo� Hit ratio = α

percentuale di successo nel trovare l’elemento cercato nel TLB.� Tempo Effettivo di Accesso (EAT)

EAT = (1 + ε) α + (2 + ε)(1 – α)= 2 + ε – α


Protezione della Memoria�Ad ogni frame viene associato un bit di protezione. �Ad ogni elemento della Tabella delle Pagine viene associato un

bit di validità:• “valido” indica che la pagina associata rientra nello spazio

degli indirizzi logici del processo. • “non valido” indica che la pagina associata NON rientra nello

spazio degli indirizzi logici.


Paginazione a Due Livelli� Tecnica di paginazione per ridurre le dimensioni delle pagine. È

comune in macchine con indirizzi a 32 bit o meno. Consiste nel paginare la stessa tabella delle pagine

� Su una macchina a 32-bit con pagine di 4K, l’indirizzo èsuddiviso in: :• Un numero di pagina di 20 bit.• Un offset di 12 bit.

� Siccome la tabella delle pagine è paginata, il numero di pagina èulteriormente suddiviso in: • Un numero di pagina di 10-bit. • Un offset di 10-bit.

� Quindi un indirizzo logico ha la seguente struttura:

dove p1 è l’indice della tabella esterna delle pagine, e p2 è loscostamento all’interno della pagina della tabella delle pagine.

� Ad esempio il Pentium II usa questa tecnica.� Macchine con indirizzi più lunghi di 32 bit adottano altre tecniche.

page number page offset

p1 p2 d

10 10 12


Paginazione a Due Livelli


Paginazione a Due LivelliSchema di Traduzione degli Indirizzi


Segmentazione� È uno swchema di gestione della memoria che si avvicina al

modo in cui l’utente vede la memoria. � Un programma è una collezione di segmenti. Ogni segmento è

una unità logica. Ad esempio abbiamo:programma principale,procedure, funzioni,metodi,oggetti,variabili locali e variabili globali,blocco comune,stack,symbol table, array


1subroutine

3programma principale

2stack

4tabella dei

simboli

1

4

2

3

Spazio logico degli indirizzi(vista dell’utente)

Spazio fisico degli indirizzi(memoria fisica)

Segmentazione


� Gli indirizzi logici sono costituiti da una coppia:<numero-di-segmento, offset>,

� Tabella dei segmenti – permette la traduzione dallo spazio bidimensionale degli indirizzi logici allo spazio unidimensionale degli indirizzi fisici. Ogni elemento della tabella ha:

• base – contiene l’indirizzo fisico di inizio dell’area di memoria doverisiede il segmento.

• limite – indica la lunghezza del segmento.� Segment-table base register (STBR) punta alla locazione di

memoria dove risiede la tabella dei segmenti. � Segment-table length register (STLR) indica il numero di

segmenti;numero-di-segmento s è legale se s < STLR.

Segmentazione


� Protezione.Ad ogni elemento della tabella vengono associati:

• Bit di validità (quando = 0 ⇒ segmento illegale)• Privilegi di lettura/scrittura/esecuzione

� Condivisione dei segmenti.Siccome la protezione avviene a livello di ogni singolo segmento, i segmenti possono essere condivisi tra processi diversi.

� Problema di allocazione dinamica della memoria.Siccome I segmenti sono di lunghezza variabile, si presentano gli stessi problemi affrontati per l’allocazione contigua apartizioni variabili (frammentazione esterna, first/best/worst fit).

Segmentazione


Segmentazione


Segmentazione - Esempio


Condivisione di Segmenti


Segmentazione con Paginazione: Intel 386L’Intel 386 usa la segmentazione con paginazione a due livelli.




� Gestione della Memoria� Allocazione contigua� Paginazione� Segmentazione� Segmentazione con Paginazione





Memoria Virtuale�Lo spazio degli indirizzi logici è più grande dello spazio degli

indirizzi fisici.•Solo la porzione di processo necessaria viene tenuta in memoria perl’esecuzione.

•Lo spazio degli indirizzi può essere condiviso tra processi diversi.•La creazione dei processi è più efficiente.

�Realizzazione:•Paginazione su richiesta. •Segmentazione su richiesta.


Paginazione su Richiesta


Paginazione su Richiesta

�I bit di validità è inizializzato a 0.�In fase di traduzione, se bit = 0 ⇒ page fault.�Riferimento non valido�Pagina non in memoria


Gestione di un Page Fault


Prestazioni della Paginazione su Richiesta� Probabilità che si verifichi un Page Fault: 0 ≤ p ≤ 1.0

• p = 0 page fault non si verifica mai• p = 1 page fault si verifica sempre

� Tempo di accesso effettivo (EAT)EAT = (1 – p) x accesso_in_memoria

+ p (page_fault + swap_out + swap_in+ restart)

� Esempio:si desidera un rallentamento inferiore al 10% avendo le seguenti prestazioni:- accesso_in_memoria = 0.1 µs- page_fault + swap_out + swap_in+ restart = 25 ms = 25000 µs

EAT = (1 – p) x 0.1 + p 25000 = = 0.1 + 24999.9 x p < 0.11

dobbiamo averep < 4 x 10-7


Paginazione su RichiestaRealizzazione

� Swap-out Per ridurre il numero di swap-out richiesti, si può utilizzare un bit di modifica (dirty bit):

• Il bit viene messo ad 1 ogni volta che la pagina viene modifcata• Durante lo swap-out la pagina viene effettivamente copiata su

disco solo se il bit di modifica è a 1.

� Servono inoltre:• Algoritmo di assegnazione dei blocchi di memoria• Algoritmo di sostituzione delle pagine.


Sostituzione delle PagineNecessità della Sostituzione


Sostituzione delle PagineAlgoritmo Base


� Deve minimizzare la probabilità di page-fault.� Gli algoritmi vengono valutati considerando il loro

comportamento (il numero di page fault prodotti) con determinatesuccessioni dei riferimenti.

� In tutti i nostri esempi le successione dei riferimenti sono: successione 1: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.successione 2: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1.

Sostituzione delle PagineCriteri di Scelta dell’Algoritmo


Andamento Desiderato deiPage Fault in Funzione del Numero di Frame

Sostituzione delle Pagine


Algoritmo First-In-First-Out (FIFO)� Sostituire la prima pagina caricata in memoria� Successione 1: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5� 3 frame (in ogni istante possono essere in memoria 3

pagine per processo)

� 4 frame

� Anomalia di Belady• Aumentare I frame non garantisc una diminuzione dei page

fault

1

2

3

1

2

3

4

1

2

5

3

4

9 page fault

1

2

3

1

2

3

5

1

2

4

5 10 page fault

44 3


Algoritmo First-In-First-Out (FIFO)Anomalia di Belady


Algoritmo First-In-First-Out (FIFO)

Successione 2


Algoritmo Ottimo� Sostituire la pagina che si utilizzerà il più tardi possibile.� 4 frame

Successione 1: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

� Impossibile da realizzare in pratica� Usato come punto di riferimento per gli altri algoritmi.

1

2

3

4

6 page fault

4 5


Algoritmo Ottimo

Successione 2


Algoritmo Least Recently Used (LRU)� Sostituire la pagina che è stata usata meno di recente� Successione 1: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1

2

3

5

4

4 3

5

8 page fault


Algoritmo Least Recently Used (LRU)

Successione 2


� Con i Contatori• Ogni elemento delle pagine ha un contatore.• Ogni volta che c’è un rifermento alla pagina, il valore del clock

viene copiato nel contatore.• Quando bisogna selezionare una pagina, si sceglie quella che ha il

valore più piccolo del contatore.

� Con lo Stack• I numeri delle pagine sono organizzati in una lista doppiamente

concatenata.• Ogni volta che c’è un riferimento ad una pagina, il suo numero

viene inserito/spostato in cima allo stack.• Quando bisogna selezionare una pagina, si sceglie quella presente

in fondo allo stack => la sostituzione non richiede nessuna ricerca nella lista

Algoritmo Least Recently Used (LRU)Realizzazione


Algoritmo Least Recently Used (LRU)Realizzazione con lo Stack


Algoritmi che Approssimano LRU� Bit di Riferimento

• Ad ogni pagina è associato un bit di riferimento, inizialmente = 0• Ogni volta che c’e’ un accesso alla pagina il bit viene posto ad 1.• La lista delle pagine è gestita FIFO, viene sostituita la pagina che ha il bit di

riferimento a 0 (se esiste).• Il bit dice se la pagina è stata usata recentemente, ma non mi dice l’ordine

d’uso. � Seconda chance

• Utilizza il bit di riferimento.• La lista delle pagine è una lista circolare (per questo viene detto anche

algoritmo dell’orologio) gestita FIFO, viene selezionata una pagina:• Se il bit di riferimento è a 0 => - viene sostituita• Se il bit di riferimento è a 1 => - il bit viene messo a 0,

- la pagina è lasciata in memoria, - viene selezionata la pagina successiva

a cui vengono applicate le stesse regole


Algoritmo della Seconda Chance (Orologio)


Applicare l’algoritmo della seconda chance alla seguente successione :

successione 2:7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1.

Esercizio: Algoritmo della Seconda Chance


Assegnazione dei Blocchi di Memoria� Nella paginazione su richiesta pura, inizialmente tutti I frame

sono posti nella lista dei frame liberi, quando il primo processo deve essere caricato in memoria, il processo genera una sequenza di page fault.

� Un metodo più efficiente, consiste nell’assegnare al processo direttamente in fase di caricamento un certo numero di frameliberi.

� Ogni processo ha bisogno di un numero minimo di pagine che devono essere assegnate ad ogni processo. Tale numero dipende dal linguaggio macchina.

� Esempio: IBM 370 – possono servire fino a 6 pagine pereseguire l’istruzione SS MOVE <from> <to>:

• L’istruzione occupa 6 byte, quindi può stare a cavallo di due pagine.• Il contenuto della parola indirizzata da <from> può stare a cavallo di

due pagine.• Il contenuto della parola indirizzata da <to> può stare a cavallo di

due pagine.


Algoritmo di Assegnazione Uniforme� I frame vengono assegnati in base al numero di processi:

sia m il numero di frame liberi ed n il numero di processi,ogni processo riceve m/n frame.

� Esempio m = 100 frame n = 5 processi,

ogni processo riceve 20 pagine.


Algoritmo di Assegnazione Proporzionale� Con l’assegnazione uniforme ci sono processi di piccole

dimensioni che ricevono molti frame e processi di grandi dimensioni che ricevono pochi frame.

� Con l’assegnazione proporzionale i frame vengono assegnati in base alle dimensioni del processo:

• si dimensioni del processo pi,

• S = Σsi

• m numero totale di frame• ai = m × si/S numero di frame assegnati al processo pi

� Esempiom = 62 s1 = 10 s2 = 127Uniforme Proporzionalea1 = 62/2 = 31 a2 = 62 × 10/137 ≈ 4a1 = 62/2 = 31 a2 = 62 × 127/137≈ 57

rimane 1 frame libero


Algoritmo di Assegnazione per Priorità� Sia con l’assegnazione uniforma sia con l’assegnazione

proporzionale, un processo con priorità elevata viene trattato nello stesso modo di un processo a bassa priorità.

� L’assegnazione per priorità si basa su una assegnazione proporzionale alla priorità dei processi invece che alla loro dimensione.

� Se un processo Pi genera un page fault,• Si sostituisce uno dei suoi frame (assegnazione locale).• Si sostituisce un frame di un processo con priorità minore

(assegnazione globale).Questo permette ad un processo con una priorità elevata di aumentare il numero di frame che gli sono stati assegnati.


Assegnazione Globale e Locale� Assegnazione Globale –

per la sostituzione viene selezionato un frame tra tutti quelli esistenti, anche se appartiene ad un processo diverso da quello che ha generato il page fault. In questo modo ci sono processi che vedono aumentare il numero di frame a loro disposizione eprocessi che vedono tale numero diminuire.

� Assegnazione Locale –per la sostituzione viene selezionato un frame del processo cheha generato il page fault.


Paginazione Degenere (Thrashing)� Se un processo non ha un numero “sufficiente” di pagine, il

tasso di page fault diventa troppo alto. Questa può essere laconseguenza della seguente situazione1. se si verifica un basso utilizzazo della CPU2. il SO decide di aumentare il grado di multiprogrammazione3. aggiunge un altro processo in memoria.

� Thrashing ≡ il SO impiega gran parte del tempo in operazioni di swap-in e swap-out.

� Questo si verifica soprattutto se si usa un algoritmo di assegnazione globale.


Prin

cipi

o di

Loc

alità

� Le pagine usate da un processo in un certo periodo della sua esistenza formano lalocalità in cui si trova il processo in quel momento.

•Un processo migra da una località adun’altra.

•Le località si possono sovrapporre tra loro.

� Il trashing si verifica se: Σ dim(località) >

dim(memoria)


�Working-set di un processo ≡ insieme delle pagine referenziate negli ultimi ∆ istanti (dove ∆ ≡ finestra del working-set).

�WSSi = dimensione del working-set del processo Pi (varia nel tempo)• se ∆ troppo piccolo non include l’intera località.• se ∆ troppo grande può sovrapporre più località.• se ∆ = ∞ ⇒ include l’intero processo.

�D = Σ WSSi ≡ totale della domanda di frame (se D > m ⇒ Thrashing)�Schema basato sul working-set

• assegnazione pari a dimensione del working set (varia nel tempo)• se D < m, allora viene attivato un nuovo processo; • se D > m, allora un processo viene sospeso.

Assegnazione Basata sul Working-Set

= 10


Calcolare l’evoluzione temporale del working setnel seguente caso:

ampiezza finestra:∆ = 10

successione 2:7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1.

Esercizio: Working Set


Assegnazione Basata su Page Fault Rate

� Schema basato sulla frequenza di page-fault.• Se la frequenza scende sotto il limite inferiore,

al processo viene tolto un frame.• Se la frequenza sale sopra il limite superiore,

al processo viene assegnato un altro frame.

Il processo necessita di altri frame

Il processo ha troppi frame


ConsiderazioniStruttura dei programmi

� Esempio• Supponiamo di avere pagine di dimensionipari a 1024 parole.• Supponiamo di dover inizializzare a zero tutti gli elementi della

seguente matriceint A[1024][1024];

• Ogni riga è memorizzata in una pagina. • Programma 1 for (j = 0; j < 1024; j++)

for (i = 0; i < 1024; i++)A[i,j] = 0;

1024 x 1024 page fault

• Programma 2 for (i = 0; i < 1024; i++)for (j = 0; j < 1024; j++)

A[i,j] = 0;

1024 page fault


ConsiderazioniVincoli di I/O

�Le pagine che sono usateper copiare un file da undispositivo di I/O devono poter essere vincolate inmemoria per evitare che vengano selezionate dall’ algoritmo di sostituzione delle pagine.




� Gestione della Memoria� Allocazione contigua� Paginazione� Segmentazione� Segmentazione con Paginazione

� Memoria Virtuale� Paginazione su richiesta� Algoritmi di sostituzione delle pagine: FIFO, Ottimale, LRU, Orologio� Algoritmi di assegnazione dei frame liberi: Uniforme, Proporzionale,




Gestione della Memoria in Linux

Spazio di indirizzamento di un task su architetture Intel a 32 bit.� Indirizzi a 32 bit, quindi abbiamo al massimo 4GB di memoria.� Ogni task ha a disposizione uno spazio d indirizzamento virtuale

di 3GB, il restante 1GB è riservato al kernel.• Un task in user mode non vede lo spazio riservato al kernel.• Ogni volta che viene invocato il kernel (per es. richiamando una

system call) il kernel riesce a vedere il suo spazio di indirizzamento senza bisogno di “ripulire” la TLB, aumentando le prestazioni del sistema.

� Lo spazio di indirizzamento è costituito da un insieme di regioni.� Ogni regione è costituita da un insieme di pagine omogenee e

contigue.� Ogni pagina ha dimensione pari a 4KB su architetture x86


Gestione della Memoria in Linux

Il gestore della memoria di Linux ha due componenti:� Gestore della memoria fisica. Si occupa dell’assegnazione e del

rilascio di pagine fisiche, gruppi di pagine fisiche e piccoli blocchi di memoria (blocchi di memoria di dimensione inferiorealla pagina).

� Gestore della memoria virtuale. Si occupa della gestione della memoria virtuale, ovvero la memoria indirizzabile dai task inesecuzione.


� L’allocazione della memoria può avvenire in due modi:• staticamente – i driver riservano aree di memoria contigua durante

l’avvio del sistema;• dinamicamente – tramite un allocatore delle pagine (quello base

oppure per alcuni moduli del kernel dei propri allocatori specializzati)

� allocatore delle pagine di base (page allocator):• è responsabile dell’allocazione e del rilascio di pagine fisiche,• è in grado di assegnare su richiesta gruppi di pagine fisicamente

contigue (regioni),• utilizza l’algoritmo buddy-heap.

Gestione della Memoria in LinuxMemoria Fisica


Algoritmo buddy-heap:� Ogni regione allocabile ha:

• dimensione pari a 2n pagine fisiche (quindi la regione più piccola ha dimensione pari ad una pagina),

• una compagna adiacente (detta buddy).� Per gestire le regioni libere, vengono utilizzate liste concatenate

distinte, una per ogni dimensione.

� Ad ogni rilascio di memoria:• Se la regione rilasciata è adiacente ad un’altra regione libera, le due

regioni vengono combinate per formarne una più ampia.



Algoritmo buddy-heap (continua):� Ad ogni richiesta di memoria:

• Sia k il numero di pagine richieste (es. k=5).• Si calcola m pari alla prima potenza di 2 superiore a k (es. m=8).• Se esiste una regione nella lista delle regioni a dimensione m, viene

allocata alla richiesta.• Altrimenti si cerca nelle liste delle regioni di dimensioni

immediatamente superiori (2m, 4m, …) fino a trovare una regione libera.

• Sia 2h .m la sua dimensione, essa viene divisa in due buddy per hvolte fino ad ottenere una regione della dimensione desiderata.

� Vantaggi:• Allocazione della memoria molto veloce

� Svantaggi:• Frammentazione interna ed esterna• Esistono dei meccanismi per riutilizzare la memoria “sprecata” a

causa della frammentazione interna



41616

8 8 8 8 8

8

8 8 84 4

4

64

32

32 32 32 32 32 32 32 32

16

16

168 8 8 8 8

844

Algoritmo buddy-heap – Esempio:• Sequenza di richieste: 8 pagine, 8 pagine, 4 pagine;• Seguita dal rilascio: 8 pagine, 8 pagine



Regioni di memoria virtuale� Lo spazio di indirizzamento è costituito da un insieme di regioni.� Ogni regione rappresenta un insieme di pagine logicamente

contigue, contenenti informazioni omogenee tra loro (codice,dati, ...).

� Ogni regione è descritta da una struttura dati(vm_area_struct) che contiene tra l’altro:

• permessi di lettura, scrittura ed esecuzione,• proprietà di paginazione, • informazioni riguardo i file,• numero della prima e dell’ultima pagina appartenente alla regione.

� Le regioni relative ad uno spazio di indirizzamento sono organizzate in un albero binario bilanciato

• per una rapida ricerca della regione corrispondente ad un dato indirizzo virtuale.

Gestione della Memoria in LinuxMemoria Virtuale


Paginazione su richiesta a tre livelli� Con i processori più semplici (per es. il pentium) il secondo

livello è disabilitato.


aPTBR

g m p dIndirizzo logico

f dIndirizzo fisico

+ + +b

...

a

g

c...

b

m

f

...

c

p


Algoritmo di sostituzione� esiste un demone chiamato kswapd il cui codice viene eseguito

una volta al secondo• verifica che ci siano abbastanza pagine libere disponibili• in caso contrario, seleziona una pagina occupata e la rende libera

� le pagine di codice vengono mappate direttamente nei fileeseguibili da cui derivano

� tutte le altre pagine vengono mappate• nella partizione di swap

� più efficiente� scrittura contigua, accesso diretto al dispositivo

• in file di swap (fino a 8 file diversi)� meno efficiente� blocchi possono essere fisicamente non contigui, accesso

attraverso il file system� algoritmo di selezione

• decide quali pagine selezionare



Algoritmo di selezione� l’algoritmo è piuttosto complesso, riportiamo una versione

semplificata:• si cerca il processo che ha più pagine in memoria• si analzano tutte le sue regioni (a partire dall'ultima regione

analizzata nella ricerca precedente)• non vengono considerate le pagine condivise, utilizzate dai canali

DMA, locked, assenti dalla memoria• per selezionare la pagina si adotta l’algoritmo dell’orologio a doppia

scansione.



Algoritmo di selezione (continua)� vengono utilizzate due liste:

• la lista delle pagine attive• la lista delle pagine inattive

� quando si fa lo swap-in di una pagina, • la pagina viene messa in testa alla lista delle pagine inattive ed il bit

di validità viene messo a uno� quando una pagina viene referenziata

• se è inattiva e il bit è a zero, il bit viene messo a uno• se è inattiva e il bit è a uno, viene messa in testa alla lista delle

pagine attive ed il bit viene messo a zero• se è attiva, il bit viene messo a uno

� periodicamente le pagine con bit a zero vicine alla coda della lista delle pagine attive, vengono messe in testa alla lista delle pagine inattive

� quando si deve fare uno swap-out, • viene selezionata la pagina con bit di validità a zero più vicina alla

coda della lista delle pagine inattive• la copia su disco viene fatta solo se il dirty bit è a uno



Linux crea un novo spazio di indirizzamento virtuale quando:� Viene eseguita una exec

• Viene creato uno spazio di indirizzi completamente vuoto.• È compito del caricatore popolare lo spazio con regioni di memoria

virtuale.� Viene eseguita una fork

• Viene creata una copia dello spazio di indirizzamento del task genitore.

• Il kernel copia tutti i vm_area_struct del genitore.• Crea un nuovo insieme di tabelle delle pagine per il figlio.• Il contenuto delle tabelle delle pagine del genitore è copiato nelle

tabelle del figlio.• Dopo la fork, genitore e figlio condividono le stesse pagine fisiche

(anche quelle private del genitore). • La pagina di una regione privata viene duplicata solo in fase di

esecuzione, quando uno dei due task chiede di modificarla.• Così le copie delle pagine si creano solo quando è necessario.



� Linux adotta per i programmi eseguibili:• Il formato a.out (comune ai vecchi sistemi Unix);• Il formato ELF.

� Inizialmente il programma eseguibile viene mappato nello spazio di indirizzamento virtuale, ma le pagine non vengono caricate

• solo quando il task chiede di accedere ad una data pagina, ci sarà un page fault e di conseguenza la pagina verrà caricata (swappedin) nella memoria fisica.

• Il compito del caricatore è quello di instaurare le associazioni iniziali per permettere l’avvio dell’esecuzione del programma.

� Linux permette due tipi di collegamento alle librerie di sistema:• Il collegamento statico• Il collegamento dinamico (occupa meno spazio sia in memoria

centrale sia su disco)



brk


Organizzazione della memoria per il formato ELF


File-System� Interfaccia del File System

• Tipo di Dato Astratto File• File Ordinari• Directory• File Speciali • Protezioni

� Realizzazione del File System• Struttura dei file system• Realizzazione delle directory• Realizzazione dei file (assegnazione dei blocchi liberi)• Cache (dei blocchi e delle pagine)

� File System di Linux• Virtual File System• Ext2 File System• Ext3 File System• Proc File System• Network File System


File� Un file è un tipo di dato astratto.� Definire un file significa quindi definire:

• Struttura• Attributi• Operazioni

� Fornisce agli utenti (e in particolare ai programmatori) una interfaccia uniforme alla gestione dei dispositivi di I/O

� In particolare il concetto di file è utile per la gestione dellememorie di massa. In questo caso, ogni file denota uno spazio logico degli indirizzi contiguo, indipendentemente da come è realizzato.


Struttura dei Filea) Assenza di struttura – sequenza di byteb) Struttura a Record – sequenza di record

• Record di lunghezza fissa • Record di lunghezza variabile

c) Struttura Complessa• Grafo/Albero di record• Documento formattato (es. Ipertesti)

� Chi gestisce la struttura del file?• Sistema operativo• Programma

Le strutture (b) e (c) si possono realizzare con struttura (a) (sequenze di byte)dotata di opportuni caratteri di controllo


Attributi dei File � Nome – è l’informazione che permette agli utenti di identificare

in modo univoco il file. � Identificatore - è l’informazione che permette al SO di

identificare in modo univoco il file. � Tipo – questa informazione serve ai sistemi che gestiscono file

di tipo diverso.� Locazione – è il puntatore al dispositivo e alla locazione del file

in tale dispositivo. � Dimensione – è l’attuale dimensione del file.� Protezione – sono informazioni di controllo degli accessi al file

(chi può leggere, scrivere, far eseguire il file).� Ora, data, e identificatore dell’utente – sono informazioni

relative alla creazione, all’ultima modifica e all’ultimo uso del file. Servono per la protezione ed il controllo dell’uso.

Gli attributi dei file sono conservati nella struttura directory, che risiede a sua volta nella memoria secondaria.


Operazioni sui File� Create – per creare un file bisogna compiere due passi:

1) si deve trovare lo spazio per il file nel file system;2) si deve creare un nuovo elemento nella directory dove registrare i suoi attributi.

� Open – questa operazione riceve il nome del file, lo cerca nella directory, e copia l’elemento ad esso associato in memoria (nella tabella dei file aperti). In alcuni SO l’apertura dei file avviene implicitamente la prima volta che il processo fa riferimento al file.

� Write – il file system deve mantenere un puntatore di scrittura contenentela locazione nel file in cui deve avvenire la prossima operazione di scrittura. Il file deve essere già aperto.

� Read – il file system deve mantenere un puntatore di lettura contenente lalocazione nel file in cui deve avvenire la prossima operazione di lettura. Il file deve essere già aperto.

� Seek – spesso il puntatore di lettura e quello di scrittura coincidono, la seek cambia il valore a tale puntatore (senza operazioni di I/O).

� Delete – si cerca l’elemento relativo al file nella directory, si rilascia lo spazio assegnato al file e si elimina l’elemento di directory.

� Truncate – si cancella il contenuto del file mantenendo i suoi attributi.� Close – copia l’elemento contenuto nella tabella dei file aperti nella

directory. In alcuni SOla chiusura avviene implicitamente quando il processo termina.


Tipi di File – Estensione dei Nomi

ps, pdf


Metodi di AccessoMetodi Base

�Accesso Sequenzialeread next legge il record nella posizione corrente (cp)write next scrive il record nella posizione corrente,

quel record diventa l’ultimo del filereset riporta la posizione corrente all’inizio del file (cp = 0)

- non è possibile fare una read dopo una write se prima non si fa una reset

- non è possibile fare una rewrite�Accesso Diretto

read n legge il blocco n-esimo (cp = n)write n scrive il blocco n-esimo (cp = n)rewrite n riscrive il blocco n-esimo

- è la base di altri metodi di accesso: accesso con indice, accesso con hash


Accesso Sequenziale


Accesso con Indice

chiave


Directory� È una collezione di file. � Una directory è un tipo di dato astratto. È un tipo di file quindi:

• Possiede gli stessi attributi e le stesse operazioni dei file. • Ha una struttura particolare. • Possiede inoltre delle operazioni aggiuntive.

F 1 F 2F 3

F 4

F n

Directory

Files


OrganizzazioneTipica di un File-System


Elemento di Directory

Ogni elemento di directory contiene informazioni relative ad un file (gli attributi del file)�Nome �Tipo�Locazione �Dimensione attuale�Dimensione massima consentita�Data dell’ultimo accesso�Data dell’ultimo aggiornamento�ID del proprietario�Protezione


Operazioni sulle Directory� Search – ricerca di un file� Create – creazione di un file� Delete – cancellazione di un file� List – elenco di una directory� Rename – ridenominazione di un file� Traverse – attraversamento del file system


Organizzazione Logica delle Directory

Il file system deve essere organizzato logicamente in modo tale da soddisfare i seguenti requisiti:� Efficienza – deve essere possibile per l’utente ritrovare i propri

file il più rapidamente possibile.� Assegnazione di nomi unici – ogni file deve avere un nome

unico, ma questo spesso contrasta con le esigenze degli utenti:• Due utenti possono usare lo stesso nome per due file diversi.• Due utenti possono dare due nomi diversi allo stesso file.

� Raggruppamento – deve essere possibile raggruppare logicamente i file sulla base delle loro proprietà (tutti i file di undato programma, tutti i documenti di un certo tipo, …).


Directory a Livello Singolo� Una unica directory per tutti gli utenti.

Problema dei nomi unici

Problema del raggruppamento dei file


Directory a Due Livelli� Una directory separata per ogni utente.

•Path name•Si possono avere file di utenti diversi con lo stesso nome•Ricerca più efficiente

•Ad un utente non è permesso raggruppare i propri file


Directory Strutturata ad Albero

� Ricerca efficiente� Possibilità di raggruppare i file� Path name assoluto e relativo� Directory corrente

(directory di lavoro)


Directory Strutturata a Grafo Aciclico� È permessa la condivisione di file e directory:

• Collegamenti simbolici – lo spazio è reso disponibile solo quando ècancellato il file (MS Windows e Unix)

• Collegamenti effettivi (hard link) – lo spazio è reso disponibile quando� È cancellato il primo hard link� Sono stati cancellati tutti gli hard link (Unix)


Directory Strutturata a Grafo Generale� È permessa la presenza di cicli


� Bisogna evitare che i processi che attraversano il file systemvadano in loop infinito:

• Controllare se si è in presenza di un ciclo nel grafo.• Impedire collegamenti a directory

� Sia MS Windows sia Unix permettono cicli realizzati attraverso icollegamenti simbolici.

� Unix non permette hard link a directory.

Directory Strutturata a Grafo Generale


File System esistente Partizione non montata

File System Mounting� Un file system deve essere montato prima di potervi accedere. � Un file system non montato viene montato ad un mount point.

mount point


......

fredbill

File System Mounting


I “file speciali” sono inclusi nella gerarchia delle directory come qualsiasi altro file, ma in realtà corrispondono a device di I/O. Si possono avere file speciali a blocchi (dischi) o a caratteri (tastiere, video a caratteri, ecc.). Questo trucco permetti di fare riferimentoad un dispositivo utilizzando un pathname.

/

dev

hd3 tty00hello world!12>

File Speciali


Protezioni� Il proprietario/creatore di un file deve essere in grado di

controllare:• cosa può essere fatto (modi di accesso: Read, Write, eXecute)• da chi

� Gli utenti di ogni file vengono raggruppati in tre categorie:• Proprietario – RWX

è l’utente che ha creato il file 7 ⇒ 1 1 1• Gruppo – RW–

insieme di utenti che condividono il file 6 ⇒ 1 1 0• Universo – – – X

tutti gli altri utenti del sistema 1 ⇒ 0 0 1

� Ogni utente può essere associato ad uno o più gruppi



� Tipo di Dato Astratto File� File Ordinari� Directory� File Speciali � Protezioni

� Realizzazione del File System• Struttura dei file system• Realizzazione delle directory• Realizzazione dei file (assegnazione dei blocchi liberi)• Cache (dei blocchi e delle pagine)



File System Stratificato1.Interazione con il file system.

2.Reperimento dei file all’interno della gerarchia delle directory. Gestione dei metadati (es. i descrittori di file o FCB).

3.Assegnazione dei blocchi liberi del disco. Traduzione indirizzi dei blocchi logici in indirizzi dei blocchi fisici.

4.Cache. Comunicazione con i driver perleggere e scrivere blocchi fisici(<superfice,cilindro,settore>).

5.Driver dei dischi. Interazione con i controller.

6.Controller. Interazione con i dispositivi


Ciascun strato è realizzato grazie ai servizi degli strati sottostanti. Una system call percorrerà i diversi strati a partire dal primo, fino ad arrivare all’ultimo, il driver, che si occuperà di far svolgere al controller del disco su cui si trova il file/directory coinvolto le operazioni necessarie a soddisfare la richiesta.

Uno dei motivi per strutturare in questo modo la gestione del file system riguarda la separazione degli strati che dipendono dall’hardware da quelli che sono indipendenti dall’hardware.

File System Stratificato


Virtual File System� VFS fornisce la stessa interfaccia basata su system call (API)

da usare per diversi tipi di file system.


Descrittore di File - File Control BlockStrutture del File System in Memoria


Strutture del File System in Memoria

aper

tura

lettu

ra


Realizzazione delle Directory� Lista lineare –

Lista di nomi di file con puntatori ai blocchi dei dati. • Ricerca di un file: ricerca lineare.• Aggiunta di un file: ricerca lineare se non esiste un omonimo ed

inserimento in fondo alla lista.• Cancellazione di un file: ricerca lineare del file, marcatura

dell’elemento di directory come libero (oppure si copia l’ultimo elemento in quello liberato oppure si usa una lista concatenata).

� Semplice da programmare.� Costosa computazionalmente.

� Hash Table –Lista lineare con struttura dati hash.

• Ricerca tramite funzione di hash.� Tempo di ricerca molto breve.� Bisogna gestire le collisioni (due elementi con lo stesso indice).� La dimensione della tabella è fissa e decisa a priori.


Realizzazione dei File: Metodi di AllocazioneIl problema principale da risolvere è come assegnare lo spazio ai file

� Assegnazione Contigua

� Assegnazione Concatenata

� Assegnazione Indicizzata


Assegnazione ContiguaOgni file occupa un insieme contiguo di blocchi nel disco.

�È semplice, serve solo la locazione iniziale e la lunghezza (numero dei blocchi) .

�Consente l’accesso diretto.�Problema dell’assegnazione dinamica della

memoria:•first-fit, best-fit, worst-fit,•frammentazione esterna.

�Problema della quantità di spazio necessario:•La dimensione massima è fissa.

•Frammentazione interna•Assegnazione contigua con Estensione


Assegnazione ConcatenataOgni file è una lista concatenata di blocchi.Ogni blocco può trovarsi in un punto qualsiasi del disco.

�Traduzione degli indirizzisiaLA = Indirizzo LogicoB = Numero di Blocco S = Scostamento:�B = LA / 511�S = (LA % 511) + 1


� È semplice.� Non esiste frammentazione esterna.� Non è necessario dichiarare la dimensione massima.

� Permette solo l’accesso sequenziale.� I puntatori richiedono spazio.

� Affidabilità (se si perde un puntatore …)

Blocco =

(512 byte)

Pointer: 4 byte

Dati: 508 byte

× T

Assegnazione Concatenata


File-Allocation Table (FAT)Variante dell’assegnazione concatenata. È utilizzata da MS-DOS e OS/2.


Assegnazione IndicizzataTutti i puntatori vengono mantenuti in una tabella indice.

�Accesso diretto�Accesso dinamico

senza frammentazione esterna.

�File di lunghezza illimitata.

�Necessità di riservare dello spazio per latabella indice.

�Sovraccarico per lagestione della tabella indice.


� La tabella degli indici è realizzata con una lista concatenata di blocchi

� Traduzione degli indirizzi siaLA = Indirizzo LogicoQ1 = blocco della tabella indiceQ2 = scostamento nel blocco della tabella indiceR2 = scostamento nel blocco del file

� Q1 = LA / (512 × 511)� R1 = LA % (512 × 511)� Q2 = R1 / 512 � R2 = R1 % 512

Assegnazione IndicizzataSchema Concatenato


� La tabella degli indici è a sua volta indicizzata.� Traduzione degli indirizzi (esempio a due livelli)

siaLA = Indirizzo LogicoQ1 = scostamento nella tabella indice di primo livello (outer index)Q2 = scostamento nel blocco della tabella indice di 2° livelloR2 = scostamento nel blocco del file

� Q1 = LA / (512 × 512)� R1 = LA % (512 × 512)� Q2 = R1 / 512 � R2 = R1 % 512

Assegnazione IndicizzataIndice a più Livelli

�

outer-index index table file


Assegnazione IndicizzataSchema Combinato

UFS – File System di Unix BSD (8K bytes per blocco)

(12)


Gestione dello Spazio LiberoVettore di Bit

…0 1 2 n-1

bit[i] =

��

� 0 ⇒ block[i] libero

1 ⇒ block[i] occupato

numero blocco = (numero di bit per parola) * (numero di parole di valore 0) + (offset del primo bit a 1)

� Facile da realizzare� Efficiente solo se il vettore è tenuto in memoria centrale

� Utilizzabile solo se i dischi sono piccoli


Gestione dello Spazio LiberoLista Concatenata


Cache del Disco� Per migliorare le prestazioni del file system si può utilizzare una

parte della memoria centrale come cache del disco.� Nella cache del disco vengono tenuti i blocchi che si prevede di

utilizzare entro breve tempo� Per migliorare le prestazioni nei PC, a volte una parte della

memoria viene utilizzata come disco virtuale (RAM disk).

� Algoritmo di sostituzione dei blocchi: LRU

Diverse locazioni di cache per i dischi


Cache delle Pagine� Utilizza tecniche di memoria virtuale per la gestione dei dati dei

file come pagine anzichè come blocchi fisici del disco.� L’uso degli indirizzi virtuali è più efficiente dell’uso dei blocchi

fisici del disco� Questo permette di utilizzare la cache sia per le pagine dei

processi sia per le pagine dei dati del disco (memoria virtuale unificata)

� Algoritmo di sostituzione delle pagine:• LRU• Paginazine con priorità

l’algoritmo di scansione delle pagine dà la priorità alle pagine dei processi rispetto a quelle dei dati del disco.



� Tipo di Dato Astratto File� File Ordinari� Directory� File Speciali � Protezioni

� Realizzazione del File System� Struttura dei file system� Realizzazione delle directory� Realizzazione dei file (assegnazione dei blocchi liberi)� Cache (dei blocchi e delle pagine)



File System di Linux

� Interfaccia del File System• Il file system di linux appare adotta una interfaccia a grafo con la

stessa semantica degli altri sistemi Unix.� Realizzazione del File System

• Il file system di linux deve essere in grado di gestire diversi tipi di file system contemporaneamente.

• I dettagli implementativi di ogni tipo di file system vengono nascosti da uno strato comune a tutti, il file system virtuale (VFS).

• VFS è stato progettato secondo i principi della programmazione ad oggetti.

• I tre tipi di oggetti principali definiti dal VFS sono:� inode-object e file-object rappresentano file singoli� file-system-object rappresenta un intero file system


File System di LinuxVirtual File System

� Media based• ext2 - Linux native• minix - Minix• ufs – BSD Unix• sysv – System V Unix• fat - DOS FS• vfat - win 95• NTFS - NT ’s FS• hpfs - OS/2• Isofs - CDROM• hfs - Macintosh• affs - Amiga Fast FS• adfs - Acorn-strongarm

� Network• nfs• Coda• AFS - Andrew FS• smbfs – Lan Manager• ncpfs - Novell

� Journaling• ext3 - Linux native• reiserfs - Linux native

� Special ones• procfs - proc• umsdos - Unix in DOS• userfs - redirector to user



System Call Layer

VFS Layer

Buffer Cache

LocalFS 1

LocalFS 2

NFSClient

NFSServer

Driver Driver Messageto server

Messagefrom client

Localdisk

Localdisk


� Layout di un file system

� Cosa contiene un superblocco in Linux?• meta-informazioni sull'intero file system• qual'è il file system contenuto nella partizione• quanti blocchi esistono, quanti sono liberi• qual’è la dimensione dei blocchi• informazioni specifiche dei particolari file system


Boot Block Superblock Gestione

spazio liberoGestione

spazio occupatoFile e

DirectoryRootdir


� Ext2fs utilizza un meccanismo di allocazione dei blocchi di un file simile a quello di BSD Fast File System (ffs).

� Le principali differenze sono:• In ffs, i blocchi sono da 8Kb e sono suddivisi in frammenti da 1Kb

per ridurre la frammentazione interna nell’ultimo blocco.• Ext2fs non usa frammenti, esistono solo blocchi da 1Kb, anche se

sono permessi anche blocchi da 2Kb e 4Kb.• Ext2fs utilizza politiche di allocazione progettate in modo tale che

una richiesta di I/O riguardante diversi blocchi può essere effettuata con una sola operazione:� suddivide un file system in gruppi di blocchi e tenta di

assegnare ad un file solo blocchi appartenenti ad un unico gruppo;

� tenta di posizionare blocchi logicamente adiacenti in blocchi fisicamente adiacenti sul disco.

File System di LinuxExt2 File System



Boot Block

Block Group 1

BlockGroup 2

BlockGroup 3

BlockGroup n…

Super-block

Group descriptor

Block bitmap

i-node bitmap Data blocksi-nodes ≈≈ ≈≈

≈≈ ≈≈Gruppo di blocchi



Politica di assegnazione dei blocchi


� Ext3 – è una versione journaling di Ext2 (ovvero con annotazione delle modifiche)

• Largamente basato su codice Ext2 (un file system Ext3 può essere montato come file system Ext2)

• Inserisce un journal (.journal file) in Ext2

� Come funziona il journal di Ext3?• Ogni operazione sul file system viene fatta in due passi:

� una copia dei blocchi da scrivere viene scritta nel journal (commit)

� al completamento del commit, i blocchi vengono scritti nelle effettive destinazioni

• Al momento del recovery (distinguiamo due casi):� prima della terminazione del commit: rimozione, fs inalterato� dopo la terminazione del commit: replica delle operazioni



� Tre modalità di funzionamento:• Journal

� Nel journal finiscono sia i metadati che i dati� Molto costoso

• Ordered� Prima vengono fatte le operazioni sui dati� Poi i metadati vengono scritti sul journal� Poi i metadati sono scritti nella destinazione effettiva� Default

• Writeback� Nel journal finiscono solo i metadati� Più efficiente



� Il file system proc non serve per archiviare in modo permanente dati, ma serve da interfaccia per altri servizi, quindi:

• non memorizza dati, • il suo contenuto è calcolato "on demand“ a seconda delle richieste

dei processi utenti� proc deve implementare una struttura di directory e il contenuto

dei file; questo significa anche definire un inode number univocoe persistente per ogni directory e file contenuto nel file system

• il numero di inode identifica l’operazione richiesta da un utente checerchi di leggere un certo file o di esaminare una certa directory

• quando i dati vengono letti, proc raccogliere le informazioniappropriate, le formatta in forma testuale e le copia nel buffer di lettura del processo richiedente

� Esempio: il comando ps• Invece di essere un processo privilegiato con accesso alla

descrizione dei processi direttamente in memoria virtuale• È un processo ordinario che legge i dati contenuti nel file system

proc

File System di LinuxProc File System


File System di LinuxNetwork File System

System Call Layer

VFS Layer

Buffer Cache

LocalFS 1

LocalFS 2

NFSClient

NFSServer

Driver Driver Messageto server

Messagefrom client

Localdisk

Localdisk

System Call Layer

VFS Layer

Buffer Cache

LocalFS 1

LocalFS 2

Driver Driver

Localdisk

Localdisk

Client kernel Server kernel


EsempioDati tre file system indipendenti



Montaggio di S1:/usr/shared in U:/usr/local

Montaggio in cascata diS2:/usr/dir2 inU:/usr/local/dir1ottenuto al passo precedente



Gestione dell’I/O� Gestione dei dispositivi di I/O

• Hardware dei dispositivi di I/O• Controller dei dispositivi di I/O• Driver dei dispositivi di I/O• Sottosistema per l’I/O del Kernel• Ciclo di vita di una richiesta di I/O

� Gestione dell’Unità a Disco• Struttura del disco• Scheduling del disco• Gestione del disco• Strutture RAID

� Gestione dell’I/O in Linux• Struttura• Tipi di dispositivi• Scheduling del disco


Struttura Relativa all’I/O del Kernel


Una Tipica Struttura a BUS di un PC


Hardware dei Dispositivi di I/O� Esiste una incredibile varietà di dispositivi di I/O� Concetti comuni

• Porta • Bus• Controller

� I dispositivi hanno indirizzi usati da• istruzioni dirette di I/O• memory-mapped I/O


Indirizzi delle Porte dei Dispositivi di I/O nei PC(elenco parziale)


Caratteristiche dei Dispositivi di I/O


Dispositivi a Blocchi e a Caratteri� Dispositivi a Blocchi

I dispositivi a blocchi comprendono i dischi• Sono a disposizione istruzioni quali read, write, seek. • Le applicazioni comunicano attraverso l’interfaccia del File System

oppure attraverso l’I/O a basso livello. • È possibile l’accesso memory-mapped

� Dispositivi a CaratteriI dispositivi a carattere comprendono tastiere, mouse, porte seriali

• Sono a disposizione istruzioni quali get, put.

• Esistono librerie che permettono operazioni di editing (quali l’accesso riga per riga o il backspace)

� Dispositivi di ReteI dispositivi di rete sono profondamente diversi dagli altri, tanto da avere una interfaccia propria.

• Ad esempio le applicazioni comunicano atraverso l’interfaccia dellesocket.


Velocità di Trasferimento di alcuni Dispositivi


DecodificatoreDecodificatoreindirizziindirizzi

Circuiti diCircuiti dicontrollocontrollo

Registro StatoRegistro Stato

Dispositivo Dispositivo

BusBus IndirizziIndirizziDatiDatiControlloControllo

Controller dei Dispositivi di I/O

ControllerController

Registro ComandoRegistro Comando

BufferBuffer

Registro IndirizzoRegistro Indirizzo


Ogni dispositivo e’ collegato al bus di sistema tramite un’interfacciadove risiedono alcuni registri (di controllo, per permettere lasincronizzazione CPU-Dispositivo, buffer per contenere i dati iningresso/uscita). Questa interfaccia e’ chiamata controller.

La CPU colloquia con il controller scrivendo/leggendo i suoi registri:

-utilizzando apposite istruzioni (IN / OUT) che avranno comeparametro un “indirizzo” che identifica un particolare controller-utilizzando normali istruzioni LOAD/STORE a indirizzi associati ai registri del controller: questa tecnica si chiama Memory Mapped I/O



Nelle architetture più semplici si trovano normalmente tre tipi di schemi per eseguire le azioni di I/O

•I/O programmato con Busy-Waiting

•I/O guidato dalle interruzioni (Interrupt)

•I/O con accesso diretto alla memoria (DMA)



Assunzioni semplificative� La periferica è un dispositivo di input di tipo carattere.

� i registri comando e stato si riducono ad un unico registro flag (flag = 0 equivale a richiesta di operazione e flag = 1equivale a operazione completata)

� La sola operazione possibile è il trasferimento di un carattere in ingresso.� attraverso il registro di interfaccia dati.

� Il driver non esegue controlli su eventuali malfunzionamenti.� La procedura leggi_linea restituisce in uscita il numero dei

caratteri effettivamente trasferiti.� L’operazione è considerata conclusa se giunge un carattere di

fine linea o se il buffer è pieno.

(continua …)

Driver dei Dispositivi di I/OEsempio: driver di una tastiera


(… continua)

� La lunghezza della linea di caratteri e il carattere da interpretare come fine linea possono essere selezionati attraverso la procedura inizializza.

� La mutua esclusione nell’esecuzione delle procedure viene realizzata attraverso il meccanismo di disabilitazione delle interruzioni.




#define BUFFER_SIZE 10

/* Device Control Block */typedef struct {

/* buffer di memorizzazione dei caratteri */char buffer[BUFFER_SIZE];/* numero caratteri trasferiti */int count;/* carattere di fine linea */char eol;/* lunghezza massima di una linea */int lungh_linea;/* coda di attesa per processo richiedente */PCB *trasf_avvenuto;/* operazione in corso */boolean occupato;

} t_DCB;



/* registri hardware del controller */typedef struct {

/* registro di lettura e scrittura dati */char dati;/* registro di comando e di stato */boolean flag;

} t_registri;

t_DCB DCB;t_registri registri;



/* Procedura di richiesta operazione –richiamato dalla system call */

int leggi_linea(PCB p; char *local_buffer){if (DCB.occupato)return –1;

else{DCB.occupato = 1; /* inizializzazione */DCB.count = 0;registri.flag = 0; /*comando iniz. controller *//* attesa del completamento operazione */add p to DCB.trasf_avvenuto;local_buffer = DCB.buffer /*trasferimento dati*/DCB.occupato = 0;return DCB.count;

}}



/* Interrupt handler: richiamato dall’interrupt HW */void risposta_interruzione(){/* acquisizione di un carattere */DCB.count++;DCB.buffer[DCB.count] = registri.dati;if (DCB.count == 80) ||

(DCB.buffer[DCB.count] == DCB.eol)/* fine dell’operazione */resume p from DCB.traf_avvenuto;

else/* nuovo comando al controller */registri.flag = 0;

}



/* Procedura di inizializzazione */void inizializza(int lunghezza; char eol){DCB.lungh_linea = lunghezza;DCB.eol = eol;DCB.occupato = 0;

}


Sottosistema per l’I/O del Kernel� Scheduling - stabilire un ordine d’esecuzione efficace ad un insieme di

richieste di I/O. Si applicano criteri simili a quelli visti per la CPU� Buffering – memorizzazione transitoria dei dati in memoria mentre essi

sono trasferiti fra due dispositivi o tra una applicazione ed un dispositivo. • Il produttore ed il consumatore hanno velocità diverse (doppio buffer)• I dispositivi trasferiscono dati in blocchi di dimensioni diverse• Per garantire la “semantica delle copie”

� Caching – memoria veloce per tenere una copia dei dati che si stanno utilizzando

• La cache contiene sempre una copia, il buffer non è detto� Spooling – è una coda contenente dati per un dispositivo (per es. la

stampante) che non può accettare flussi di dati intercalati• I dati provenienti da una singola applicazione si registrano in un specifico file

su disco, quando il flusso è terminato, si inserisce il file nello spool� Prenotazione dei dispositivi - sistema di prenotazione ed accodamento

dei processi che richiedono l’uso di dispositivi non condivisibili� Gestione degli errori – dovuti a motivi contingenti o permanenti. Gli errori

spesso vengono riportati in un error log• Errori contingenti: il SO ritenta• Errori permanenti: viene restituito un codice di errore


Sottosistema per l’I/O del KernelBuffering


Sottosistema per l’I/O del KernelCaching

� Un’area della memoria centrale viene riservata per tenere una copia dei settori del disco che si stanno utilizzando

� Si ha bisogno di un algoritmo di sostituzione dei blocchi quando la cache è piena.� Least Recently Used – viene sostituito il blocco che non viene

utilizzato da più tempo. La cache è una pila (stack) di blocchi.� Least Frequently Used – viene sostituito il blocco che è stato

utilizzato di meno. Ad ogni blocco viene associato un contatore che viene incrementato ad ogni accesso.






� Il kernel mantiene le informazioni relative allo stato deidispositivi di I/O, per esempio la tabella dei file aperti, la tabelladelle connessioni di rete, lo stato dei dispositivi a carattere.

� In alcuni SO l’I/O viene realizzato adottando il paradigma ad oggetti e lo scambio dei messaggi, meno efficiente ma di più facile progettazione

Sottosistema per l’I/O del KernelStrutture Dati


Strutture Dati di Unix

Sistemi di Elaborazione A.A. 2004/2005 26Cic

lo d

i Vita

di u

na R

ichi

esta

di I

/O



� Hardware dei dispositivi di I/O� Controller dei dispositivi di I/O� Driver dei dispositivi di I/O� Sottosistema per l’I/O del Kernel� Ciclo di vita di una richiesta di I/O

� Gestione dell’Unità a Disco• Struttura del disco• Scheduling del disco• Gestione del disco• Strutture RAID



Struttura del Disco� A basso livello, le unità a disco sono suddivise in settori

individuati dalla seguente tripletta < superfice, cilindro, settore >.


Struttura del Disco� Le unità a disco sono indirizzate come un unico grande array

mono-dimensionale di blocchi logici, dove i blocchi logici sonol’unità di trasferimento più piccola.

� I blocchi logici dell’array mono-dimensionale vengono associatiai settori del disco in modo sequenziale.

0 1 2 3 4 5 6 7 N• • • • •Indirizzo blocchi del disco: I

•n : superficiec : cilindros : settore

Indirizzo fisico: <n,c,s>

I = (n*C*S) + (c*S) + ss = I mod Sc = (I div S) mod Cn = (I div S) div C

= I div C*S

S = settori/cilindroC = cilindri/superficie


Scheduling del DiscoGarantire un uso efficiente dell’unità a disco significa avere tempi di accesso contenuti e ampiezza di banda elevata.� Tempo di accesso è composto principalmente da:

• Tempo di ricerca (seek time): il tempo necessario alle testine per posizionarsi nel cilindro contenente il settore desiderato.

• Latenza di rotazione: il tempo necessario affinché il disco ruotifino a quando il settore desiderato si trova sotto la testina.

Minimizzare il tempo di accesso di fatto significa minimizzare iltempo di ricerca (è difficile minimizzare il tempo di latenza in quanto le moderne unità a disco non rivelano la posizione fisica dei blocchi logici).Per minimizzare il tempo di ricerca si considera

tempo di ricerca ≈ distanza di ricerca� L’ampiezza di banda è il numero di byte trasferiti diviso il

tempo intercorso fra la prima richiesta e il completamentodell’ultimo trasferimento.


� I diversi algoritmi di scheduling vengono illustrati prendendo in considerazione i cilindri che contengono i blocchi richiesti. Questo è dovuto alla scelta di considerare solo il tempo di ricerca.

� L’esempio di riferimento è il seguente:• supponiamo di avere la seguente coda di richieste (espresse dal

numero di cilindro corrispondente)

98, 183, 37, 122, 14, 124, 65, 67

• supponiamo che la testina si trovi inizialmente al cilindro 53

Scheduling del Disco


First Come First Served (FCFS)�Seleziona la richiesta secondo l’ordine di arrivo.�Nell’esempio in figura la testina si muove in totale per 640 cilindri


�Seleziona la richiesta con il minimo tempo di ricerca rispetto alla posizione corrente della testina.�SSTF è una specie di SJF; èuò causare starvation.�Nell’esempio in figura la testina si muove in totale per 236 cilindri

Shortest Seek Time First (SSTF)


Scheduling per Scansione (SCAN)�Il braccio del disco parte da un estremo del disco e si muove verso l’altro estremo per poi tornare indietro, servendo le richieste mano a mano che le incontra (algoritmo dell’ascensore).�Nell’esempio in figura la testina si muove in totale per 208 cilindri


Scheduling per Scansione Circolare (C-SCAN)�Come SCAN, solo che arrivato ad un estremo del disco, riparteverso l’altro senza servire richieste durante il viaggio di ritorno.�Tratta i cilindri come una lista circolare.


LOOK e C-LOOK�Varianti di SCAN e C-SCAN. Il braccio si sposta verso una

estremità solo fino a quando ci sono altre richieste da servire in quella direzione.

� In figura è riportato un esempio di C-LOOK.


Scheduling del Disco


Gestione dell’Unità a Disco� Formattazione a basso livello, o formattazione fisica —

Suddivisione del disco in settori che il controller del disco puòleggere e scrivere.

� Partizioni – Suddivisione del disco in uno o più gruppi di cilindri. Ogni partizione viene gestita dal SO come una unità disco a se stante.

� Formattazione logica – Creazione del File System.� Blocco d’avviamento (boot block) – Contiene il programma di

bootstrap (la ROM contiene il bootstrap loader).� Area di swap – È l’area del disco utilizzata dal SO per la

memoria virtuale. Può essere collocata:• all’interno del normale file system• in una partizione a se stante


Strutture RAID(Redundant Array of Inexpensive Disks)

I dischi RAID sono batterie ridondanti di dischi� Miglioramento delle prestazioni tramite il parallelismo:

• Sezionamento dei dati (data striping) – consiste nel distribuire i bitdi ciascun byte su più dischi.

� Miglioramento dell’affidabilità tramite la ridondanza:• Copiatura speculare (mirroring o shadowing) - ogni disco logico

consiste di due dischi fisici e ogni scrittura si effettua su entrambi i dischi. Se uno dei dischi si guasta, si possono utilizzare i datidell’altro disco.

• Sezionamento + bit di parità (o + codici di correzione degli errori) –per diminuire il grado di ridondanza richiesto si può pensare dicombinare il sezionamento con l’uso dei codici di correzione degli errori (o con l’uso dei bit di parità). Questi codici associano ad ognibyte uno o più bit il valore dei quali dipende dai valori dei bit contenuti nel byte stesso.


Live

lliR

AID

da

0 a

6


Livelli RAID (0 + 1) e (1 + 0)



� Hardware dei dispositivi di I/O� Controller dei dispositivi di I/O� Driver dei dispositivi di I/O� Sottosistema per l’I/O del Kernel� Ciclo di vita di una richiesta di I/O

� Gestione dell’Unità a Disco� Struttura del disco� Scheduling del disco� Gestione del disco� Strutture RAID



Gestione dell’I/O in Linux� Linux classifica tutti i dispoisitivi in tre categorie:

• Dispositivi a blocchi, permettono l’accesso diretto a blocchi di dati di dimensione fissa.

• Dispositivi a caratteri, comprendono gran parte dei dispositivi, nonsono in grado di fornire le funzionalità dei file ordinari.

• Dispositivi di rete, sono interfacciati con il sottosistema di gestione delle reti del kernel.


Gestione dell’I/O in LinuxStruttura


� È la principale interfaccia a tutti i dischi del sistema.� Linux accede ai dischi attraverso due cache:

• I dati sono memorizzati nella page cache, che è unita alla memoria virtuale del sistema;

• I metadati sono memorizzati nella buffer cache, una cacheseparata indicizzata dal blocco fisico del disco.

� Il block buffer cache serve principalmente a due cose:• come pool di buffer per I/O attivo,• come cache per l’I/O completato.

� Il request manager gestisce la scrittura e la lettura del buffer condati provenienti da/diretti verso un driver di un dispositivo ablocchi.

Gestione dell’I/O in LinuxDispositivi a Blocchi


� Un driver di un dispositivo a caratteri deve avere un insieme di funzioni che realizzano le varie operazioni sui file.

� Il kernel non esegue quasi nessuna operazione alla richiesta di leggere o scrivere su un dispositivo a caratteri, semplicemente passa la richiesta al dispositivo.

� La sola eccezione è rappresentata dai terminali, nei confronti dei quali il kernel mantiene una interfaccia standard.

Gestione dell’I/O in LinuxDispositivi a Caratteri


� I dispositivi di rete in Linux permettono di gestire:• Il protocollo standard di Internet (TCP/IP) per la comunicazione tra

macchine Unix,• Protocolli per macchine con SO non Unix, come Appletalk e IPX.

� È realizzato con tre strati di software:• L’interfaccia delle socket (permette la gestione della rete come se

fosse un file)• I driver dei protocolli• I driver dei dispositivi di rete

Gestione dell’I/O in LinuxDispositivi di Rete


� Elevator scheduler• Utilizza una coda sola sia per le richieste di lettura che di scrittura.• Le richieste sono ordinate per numero di blocco.• Si muove in una sola direzione

Gestione dell’I/O in LinuxScheduling del disco


� Deadline scheduler• Utilizza tre code

> Incoming request – coda dove vengono inserite tutte le richieste ordinate per numero di blocco.

> Read request – coda gestita FIFO dove vengono inserite tutte le richieste di lettura presenti nella incoming request.

> Write request – coda gestita FIFO dove vengono inserite tutte le richieste di scrittura presenti nella incoming request.

• Le richieste sono rimosse dalle code read request e write requestse sono state servite dall’elevetor scheduler.

• Ogni richiesta ha una scadenza (expiration time), alla scadere della quale se non è stata servita il controllo passa al FIFO scheduler(evita la starvation).



� Deadline scheduler



� Anticipatory I/O scheduler• I programmi spesso utilizzano settori consecutivi.• Dopo aver soddisfatto una richiesta aspetta per un breve periodo

(fino a 6ms) per vedere se arriva una richiesta di un settore vicino.


Date post:	29-Jun-2015
Category:	Documents
Upload:	michele-scipioni
View:	443 times
Download:	1 times

Dispense

Documents