Inquadrare Il Problema

• Grande sviluppo tecnologico– Potenza di calcolo– Costi contenuti

Utenti con scarse

conoscenze informaticheNecessita di :

User friendly

Cos’e’ Un Sistema Operativo

Il Sistema operativo è un programma, o meglio, un insieme di programmi, scritto allo scopo di rendere disponibili all’uso del risorse di calcolo e i dispositivi collegati al computer

User 1 User 2 User 3 User n

compiler assembler text editor data base system

PROGRAMMI APPLICATIVI

SISTEMA OPERATIVO

COMPUTER

HARDWARE

Funzioni Svolte Dal S.O.Gestione delle risorse sia hardware (tempo di CPU, spazio di memoria, dispositivi di I/O,etc) che software (file, strutture dati, etc). Il S.O. assegna le risorse ai processi utenti in base a prefissate politiche di gestione.

Definizione di una macchina virtuale di più semplice uso da parte degli utenti , in grado di nascondere tutta una serie di particolarità del funzionamento del sistema legate alla struttura hardware (es. gestione degli interrupt). La macchina virtuale mette a disposizione dell’utente apposite operazioni che gli consentono di operare ad un livello di astrazione maggiore.

•Assegnazione delle Risorse in modo da rendere Efficiente il loro uso•Risoluzione dei conflitti •Scelta dei criteri

Esempio : Controllore di floppy

disk

Struttura S.O.

GERARCHICA

MODULO

PRIMITIVA

MACCHINA VIRTUALE

PORTABILITA’

I PROGRAMMI CHE LO COMPONGONO SI COLLOCANO A LIVELLI DIVERSI , SI

SERVONO DI PROGRAMMI CHE STANNO A LIVELLI SOTTOSTANTI E SERVONO I

PROGRAMMI A LIVELLI SUPERIORI

Un insieme di routine scritte per risolvere un problema (attivano i meccanismi fisici

necessari )

Una procedura standard per mezzo della quale il modulo mette a disposizione i

servizi

La sua attitudine ad essere eseguito su

macchine diverse

Evoluzione S.O.• Prima generazione (1945-1955)

– Programmazione in LM– Controllo dell’esecuzione da parte dell’operatore– Introduzione di programmi e dati tramite lettura di schede

• Seconda generazione (1955-1965)– Sistemi batch– Buffer I/O– Spooling

• Terza generazione (1965-1980)– Multiprogrammazione– Timesharing– Sistemi interattivi

• Quarta generazione(1980-1990)– Personal computer e Workstation– Sistemi distribuiti– Sistemi operativi di rete– Sistemi operativi distribuiti

Criteri di base :L’evoluzione dei S.O. è stata guidata dalla necessità di soddisfare, in modo sempre più efficace, le esigenze degli utenti. Ciò è stato possibile grazie allo sviluppo tecnologico e al continuo potenziamento del software di base e dei linguaggi di programmazione

Criteri di base :L’evoluzione dei S.O. è stata guidata dalla necessità di soddisfare, in modo sempre più efficace, le esigenze degli utenti. Ciò è stato possibile grazie allo sviluppo tecnologico e al continuo potenziamento del software di base e dei linguaggi di programmazione

Classificazione Dei S.O.

Organizzazione interna

Monoprogrammato

Multiprogrammato

A divisione di tempo

Visibilità utente

Batch

Interattivo

General Purpose

Transazionale

Elaborazione a distanza

Il Concetto Di Processo

Il concetto di Processo è fondamentale in sistemi caratterizzati da più attività che possono essere svolte logicamente in parallelo. Esso descrive, in termine di operazione eseguite dalla CPU, il comportamento di un programma in esecuzione.

Programma entità statica (passiva) che descrive le azioni da compiere

Processo entità dinamica (attiva) che rappresenta l’esecuzione di tali azioni.

Più processi possono essere associati allo stesso programma : ciascuno rappresenta l’esecuzione dello stesso codice con dati diversi

Ogni processo ha un insieme di dati ad esso riferiti: è un’area dati contenente informazioni relative all’identità del processo ed alla sua eventuale priorità e altro. Viene chiamato Descrittore del Processo

Stati Di Un Processo• Run : il processo è in esecuzione sul

processore• Wait : il processo non può avanzare

in quanto non ha a disposizione tutte le risorse necessarie ma non è ancora stato ultimato (attesa I/O)

• Ready : il processo ha a disposizione tutto ciò che gli serve per essere eseguito ma non essendo disponibile il processore deve aspettare il proprio turno

• Terminate:il processo ha avuto termine

• Hold : il nome del programma è inserito nell’elenco di quelli in attesa di esecuzione e gli vengono associate tutte le informazioni necessarie al S.O. Perché possa farlo diventare un processo attivo hold

run

terminate

ready

wait

Ciclo di avanzamento di un processo

Il concetto di RisorsaPerché un processo posso evolvere nel tempo, occorre che possa disporre di tutti gli “oggetti” necessari per l’esecuzione di quanto descritto nel programma.

RISORSA = qualsiasi elemento hardware o software che viene usato da un processo e che ne condiziona l’avanzamento.

Le risorse possono essere classificate in vari modi :

•Hardware o Software

•Permanenti(può essere utilizzata ripetutamente) o Consumabili (viene creata da un processo e utilizzata da un altro)

•Seriali (un solo processo alla volta) o Parallele (più processi in parallelo)

•Interrompibili ( è seriale ma è possibile che passi ciclicamente da un processo ad un altro)

Il S.O. come gestore delle risorse (1)

Dato che in generale in un sistema multiprogrammato più processi possono richiedere le medesime risorse e che quest’ultime sono numericamente limitate, uno dei compiti fondamentali del S.O. è quello di gestirle cercando, di volta in volta, di redimere gli eventuali conflitti che sorgono tra i vari processi in competizione per ottenere la stessa risorsa. Per fare ciò il S.O. dovrà :

Tener aggiornate le informazioni sullo stato di ciascuna risorsa, per poter verificare se questa è libera o è già assegnata ad un processo

Interpretare le richieste dei singoli processi e, in base alla politica di gestione, redimere eventuali situazioni di conflitto

Assegnare la singola risorsa ad un determinato processo

Riprendere il controllo della risorsa

Il S.O. Come Gestore Delle Risorse (2)I moduli del S.O. dedicati alla gestione delle risorse possono essere suddivisi in 4 blocchi :

Gestore delle periferiche

S.O.

Gestore della memoria

Gestore dei file

Gestore dei processori

nucleo

fine

Gestore Dei Processori (1)I moduli più significativi sono :

•Lo schedulatore di lavori (job scheduler o long term scheduling)

•Lo schedulatore dei processi (process scheduler o short term scheduling)

•Il controllore del traffico (traffic controller o dispatcher)

I 2 moduli di scheduling utilizzano particolari politiche di scelta che si possono fondare su vari criteri :

Utilizzo della CPU : massimizzarla

Produttività : massimizzare il numero dei programmi eseguiti nell’unità di tempo

Tempo di turnaround e di risposta : minimizzarlo

Non privilegio : garantire a tutti gli utenti un servizio omogeneo in termini di tempi di attesa

Nel caso di un sistema monoprogrammato il job scheduler e il process scheduler coincidono!!!

Job schedulerIl Job scheduler è il supervisore che assegna le risorse di un sistema a certi lavori. Sceglie , fra quelli proposti, i lavori da eseguire e li carica da memoria di massa in memoria centrale, creando i relativi processi.

I descrittori di tutti i lavori sono organizzati in una lista che lo schedulatore scandisce al fine di determinare quale lavoro portare in MC per l’esecuzione. Tale scelta si basa su una strategia direttamente implementata nell’algoritmo di schedulazione.

Politiche di schedulazione

FIFO : i lavori vengono eseguiti nell’ordine in cui giungono ( tempi di risposta imprevedibili)

Priorità statica : si assegna ad ogni lavoro un parametro che condiziona le decisioni dello schedulatore (può essere definito dal responsabile del centro oppure calcolato dal S.O. in base ad alcuni valori forniti dall’utente) un lavoro può rimanere in coda indefinitamente -starvation)

Priorità dinamica : il S.O. incrementa la priorità di un lavoro al crescere del tempi di attesa

Process SchedulerIl Process scheduler opera sulla lista dei processi in stato ready per scegliere, in base ad una certa politica, quale processo portare in stato di run.

Tipiche politiche usate sono :

Round Robin : il processore viene assegnato, a turno, ad ogni processo per un certo periodo di tempo e , se alla fine del periodo l’esecuzione non è terminata, il processo viene riportato nella coda dei pronti

Tecnica a rientro per percentuale di tempo usato : il processore viene assegnata a turno ad ogni processo ma, se il quanto di tempo viene usato solo in parte, quando il processo rientra nella coda dei pronti la sua posizione verrà determinata in rapporto alla percentuale di tempo usata

Round Robin a più livelli : inizialmente tutti i processi vengono posti nella coda 1 e a ciascuno di essi, a turno, viene assegnato un quanto di tempo dal processore; se alla fine del tempo concesso un processo non è terminato viene posto nella coda successiva che è a più basso livello di priorità. Le code vengono sempre scandite in ordine di priorità.

Traffic controller

Il traffic controller ha il compito di controllare l’avanzamento di un processo ed in particolare deve tener traccia di tutti i processi attivi e provvedere al cambio di stato dei diversi processi, oltre a coordinare la sincronizzazione e cooperazione tra i vari processi.

Sincronizzazione Cooperazione

Gestore della Memoria (1)La gestione della Memoria Centrale occupa un ruolo estremamente importante nella definizione

di un S.O. poiché una scadente organizzazione di questo modulo può provocare vere e proprie strozzature nell’esecuzione dei programmi. Un’efficiente gestione della memoria si prefigge alcuni obiettivi principali, individuabili nei seguenti termini :

RILOCAZIONE : traduzione degli indirizzi relativi in indirizzi assoluti

PROTEZIONE : controllo da parte del S.O. che non avvenga interazione negativa fra i processi

CONDIVISIONE : sincronizzare l’accesso a una stessa area in MC da parte di più processi

Si conviene di chiamare Spazio Fisico (SF) l’insieme degli indirizzi delle locazioni di MC accessibili a livello della macchina. D’altra parte è comodo pensare che ciascun processo operi su uno spazio di indirizzi più astratto che chiamiamo Spazio Logico (SL) del processo cui si può far corrispondere una memoria logica. In accordo a ciò ogni processore virtuale non genera indirizzi fisici ma logici. Da un punto di vista concreto occorrerà far corrispondere ad ogni indirizzo logico di un processo un preciso indirizzo fisico cioè implementare una funzione di mapping T : SL SF in modo da generare una mappa della memoria.

Il Manager della Memoria affronta un duplice problema legato alla mappa della memoria :

1. Tradurre i nomi simbolici degli indirizzi in locazioni in MC ( rilocazione)

2. Allocare ai processi la quantità di memoria necessaria

Gestore della Memoria (2)

Le funzioni principali del Memory Management sono :

•Tenere aggiornato lo stato di ogni locazione di memoria della MC

•Decidere in base alla politica di allocazione a quale processo debba essere assegnata la memoria, con che priorità e per quanto tempo

•Selezionare le specifiche locazioni da assegnare ad un processo e provvedere alla memorizzazione reale delle informazioni associate

•Gestire la politica del recupero del controllo della memoria, decidendo a quale processo togliere la risorsa

Gestore Della Memoria (Tecniche Di Allocazione1)Allocazione a singola partizione : è la tecnica più semplice; viene utilizzata in ambiente di monoprogrammazione. La memoria centrale è occupata in parte dal S.O. e in parte dal processo utente. Una parte della memoria rimane spesso completamente inutilizzata e i lavori effettivamente eseguibili sono solo quelli che richiedono come spazio degli indirizzi un’area minore o uguale di quella a disposizione dell’utente. Per gli altri lavori occorrerà ricorrere alle tecniche di overlay.

Allocazione a partizioni statiche : è una delle più semplici tecniche adottabili in ambiente di multiprogrammazione. Si basa essenzialmente sulla suddivisione della MC in aree separate, chiamate partizioni, di dimensione fissata a priori in ciascuna delle quali è possibile allocare un processo. L’ampiezza delle aree viene decisa in base alle caratteristiche e alla dimensione dei lavori che normalmente sono in esecuzione. Il descrittore della memoria sarà formato da una semplice tabella che conterrà, per ciascuna partizione, la lunghezza della partizione, l’indirizzo di partenza e l’indicatore di stato (libera o no) e il nome del processo che eventualmente la occupa.

Allocazione a partizioni dinamiche : ogni volta che un processo deve essere caricato in MC è il SO che crea la partizione dimensionandola opportunamente. La suddivisione della memoria in partizioni varia , quindi, dinamicamente, in rapporto al numero e alla dimensione dei processi schedulati. Anche in questo caso è necessario disporre di opportune tabelle di descrizione, una per le partizioni definite e occupate, una per le aree libere.

Problemi

ProblemiAlgoritmi di miglioramento

Gestore Della Memoria (Tecniche Di Allocazione 2)

Una soluzione al problema della frammentazione può essere rappresentato dal compattamento periodico di tutte le aree occupate verso la parte alta della memoria centrale così da permettere la creazione di un’area libera sul fondo della stessa. Questa operazione è molto complessa in quando lo spostamento di un programma da un’area all’altra implica l’uso della rilocazione dinamica. Tale tecnica viene chiamata allocazione a partizioni rilocabili.

In tale modo si riduce la frammentazione ma si complica la gestione con il ricalcolo degli indirizzi e con la necessaria valutazione sulla opportunità di ricompattare lo spazio.

In tutti i metodi visti finora permane il vincolo della contiguità

Gestore Della Memoria (Tecniche Di Allocazione 3)Eliminando il vincolo di contiguità si riduce certamente la frammentazione e si permette di allocare processi che diversamente non potrebbero essere caricati a meno di non ricorrere alla riconfigurazione della memoria. Tale tecnica viene chiamata Paginazione.

Le parti fisiche della memoria, o pagine, nelle quali allocare le parti logiche del programma sono di dimensioni fisse (ad esempio 4k o multipli di 2). In questo modo mentre le pagine del programma sono logicamente contigue, i blocchi di memoria possono anche non esserlo.

Poiché il processo deve mantenere una sua unità logica, l’indirizzamento non è più lineare ma bidimensionale; il sistema deve infatti disporre dell’indirizzo di pagina e dell’indirizzo all’interno della pagina. Poiché pagina logica e pagina fisica hanno la stessa dimensione la traduzione degli indirizzi da parte del sistema avviene consultando un’apposita tabella di traduzione (tabella di mappa di pagina) che contiene l’indirizzo base di ogni pagina della memoria fisica. Il gestore della memoria deve inoltre tenere aggiornata una tabella di occupazione delle pagine fisiche per conoscere dove allocare le nuove richieste.

La rilocazione è obbligatoriamente dinamica in quanto quando avviene il caricamento di una pagina il sistema non è in grado di sapere dove le altre pagine verranno allocate.

Naturalmente la dimensione delle pagine e dei blocchi deve essere fatta tenendo conto dei lavori da effettuare e della struttura hardware del sistema : se la misura di una pagina è troppo grande ci si ritrova con gli stessi problemi delle partizioni, se la misura è troppo ridotta si dovrà gestire una grossa tabella di mappa che porterebbe ad un overhead di sistema

Rilocazione nel meccanismo di paginazione(1)

Pag 0 di PippoPag 1 di PippoPag 2 di PippoPag 3 di Pippo

Pippo : 13k

Le pagine fisiche e logiche sono di 4k

All’indirizzo 1100 (indirizzo relativo della pagina 0 del processo) si trova l’istruzione Jp 5200

Il processo viene caricato in Mc secondo le specifiche descritte nella seguente tabella di mappa di pagina :

0 0

1

4

3

2

2

7

Pag.logica Pag.fisica

Supponiamo che la pagina fisica 0 abbia indirizzo base IB = 0

Rilocazione nel meccanismo di paginazione(2)Quando deve essere rilocata l’istruzione jp 5200 occorre :

1. Determinare a quale pagina logica del processo fa riferimento tale indirizzo relativo

N° pagina logica (NPL) = indirizzo relativo div dimensione pagina

NPL = 5200 div 4096 = 1

2. Trovare in quale pagina fisica è stata caricata la pagina logica NPF

Per fare ciò si scorre la tabella di mappa di pagina NPF =2

3. Determinare l’indirizzo base della pagina fisica NPF (indirizzo assoluto)

Indirizzo di NPF (INPF) = Indirizzo base (pag 0) + dimensione pagina *NPF

INPF = 0 + 4096*2 = 9192

4. Determinare l’offset ovvero rapportare l’indirizzo relativo che devo rilocare alla dimensione della pagina :

Offset = Indirizzo relativo mod dimensione pagina

Offset = 5200 mod 4096 = 1104

5. Calcolo indirizzo assoluto come INPF + offset = 9192 + 1104 = 10296

Gestore Della Memoria (Tecniche Di Allocazione 4)

Fino a questo momento un lavoro poteva essere caricato in MC solo se era possibile caricare l’intero lavoro. E’chiaro che il livello di multiprogrammazione ottenibile è condizionato dalla disponibilità della MC. E’ possibile avere contemporaneamente in memoria, in stato ready, un elevato numero di processi anche di dimensioni considerevoli ma non si può comunque andare oltre la capienza massima dello spazio fisico. Poiché lo spazio fisico è limitato, mentre lo spazio logico non lo è prima o poi capiterà che la memoria non sia sufficiente.

E’ stata individuata una nuova tecnica di gestione della memoria centrale chiamata Memoria virtuale. La memoria virtuale non è un’effettiva memoria ma il risultato di un’opportuna gestione della memoria reale con l’ausilio di una memoria periferica ad accesso veloce (disco).

Sul fatto che un processo per essere eseguito debba risiedere in MC non ci sono dubbi; tuttavia un processo interrotto può rilasciare la MC ed essere conservato, con tutti i dati che lo caratterizzano, su una periferica ad accesso diretto veloce. Prima del successivo passaggio in running verrà riportato in memoria. Tale complesso di trasferimenti si chiama swapping. I processi non disponibili in memoria si dicono sospesi.

E’ troppo vincolante imporre che la successiva allocazione coincida con la precedente. Inoltre con la tecnica di paginazione siamo in grado di effettuare una suddivisione sia logica che fisica di un programma

Gestore Della Memoria (Tecniche Di Allocazione 5)Se la contiguità fisica non è più un requisito essenziale, si può sfruttare il fatto che il processo, avendo una natura sequenziale, richiede azioni che vengono svolte dalla CPU in sequenza e mai in parallelo. E’ quindi inutile tenere in memoria le pagine non ancora coinvolte nell’esecuzione. Si considera così eseguibile un processo di cui sia caricata almeno una pagina. Si distinguono così le pagine logiche corrispondenti a pagine fisiche (residenti) dalla pagine non ancora caricate in memoria (sospese). Si viene così a disporre di uno spazio logico decisamente superiore a quello reale fisico , introducendo il concetto di memoria virtuale.

Problemi :

•Si carica solo la prima pagina di ogni processo o, se possibile, l’intero processo?(problema del

frame allocation)

•Come si comporta il sistema se non c’è più spazio per caricare una pagina non ancora caricata ma necessaria per la prosecuzione di un processo ? (problema del

Page Fault e Page Replacement)

Se dopo l’aggiornamento del pc accade che l’indirizzo logico previsto non corrisponde un effettivo indirizzo fisico allora si genera un’interruzione : il processo viene interrotto con la segnalazione di Page Fault e non può riprendere fintanto chela pagina richiesta non venga caricata in memoria.

Gestore delle periferiche Le funzioni di base di questo modulo sono :

•Conservare su un opportuno supporto lo stato di tutte le periferiche

•Decidere in base ad un’opportuna politica di gestione a quale processo assegnare una periferica, quando assegnargliela e per quanto tempo

•Assegnare la periferica e le relative interfacce al processo prescelto

•Gestire la politica e le tecniche di rilascio delle risorse, sia a livello di processo che di lavoro.

Quando una periferica viene assegnata a livello di lavoro, essa viene associata al processo dal momento in cui questo viene generato fino a quando giunge al termine; quando invece viene fatta a livello di processo , la periferica viene associata solo per il tempo necessario al suo utilizzo.

Le principali tecniche utilizzate per allocare e gestire le periferiche sono :

•A Periferiche dedicate

•A periferiche condivise

•A Periferiche virtuali

Tecnica di allocazione a periferiche dedicate

Alcune periferiche, come le stampanti e i nastri magnetici, per loro stessa natura possono essere usate solo serialmente e devono quindi essere assegnate ad un lavoro per volta. In questo caso la migliore strategia di allocazione consiste nell’assegnare la periferica in modo dedicato ad un preciso lavoro per l’intera durata dello stesso. Questo però provoca notevoli problemi nello schedulatore dei lavori che non può far avanzare un lavoro finchè la risorsa seriale è occupata, anche se questa verrà usata solo nelle ultime fasi del lavoro stesso.Inoltre l’assegnamento dedicato presenta lo svantaggio di mantenere occupata la periferica per l’intero tempo d’esecuzione del lavoro anche nel caso in cui questo la utilizza solo per piccole porzioni di tempo

Tecnica di allocazione a periferiche condivise

Alcuni tipi di periferiche, come i dischi, possono essere usati “parallelamente” da più processi, nel senso che l’interferenza tra i processi concorrenti risulta molto limitata. Ciò è dovuto essenzialmente da 2 fattori :

•I meccanismi di accesso permettono ai vari processi di accedere a turno ad aree diverse senza che ciò provochi confusione nella trasmissione (lettura e scrittura) delleinformazioni

•L’elevata velocità del dispositivo di I/O permette di operare una sorta di “time-sharing” tra i vari processi, che possono così avanzare parallelamente, pur utilizzando la risorsa uno per volta.

In questo caso la strategia di allocazione più idonea consiste nell’assegnare dinamicamente la risorsa ai vari processi solo per il tempo necessario al suo uso e gestire le eventuali situazioni di conflitto.

Tecnica di allocazione a periferiche virtualiIl problema di utilizzare in modo ottimizzato le periferiche di tipo dedicato ha suggerito l’idea di simulare le apparecchiature di I/O con opportune aree di memoria su disco, su cui depositare temporaneamente i dati in ingresso o in uscita, creando così delle periferiche virtuali. La gestione delle periferiche virtuali ed il loro collegamento con quelle reali viene effettuato tramite i programmi di SPOOL.

Esempio : supponiamo di avere più lavori che richiedono l’uso della stessa stampante. In fase di generazione dei processi associate, a ciascuno di essi verrà assegnata, anziché la stampante, un’area di memoria su disco in cui verranno di volta in volta depositate le informazioni in uscita. Ogni volta che un processo chiede di effettuare una stampa, attraverso il programma di gestione dello Spool i dati da stampare vengono depositati nell’area del disco assegnatagli e il processo viene fatto avanzare come se la stampa fosse avvenuta. Solo quando il lavoro è giunto a conclusione, tutto il contenuto dell’area di spool ad esso assegnata, viene trasferito alla stampante, che rimane quindi assegnata al alvor solo per il tempo strettamente necessario alla stampa effettiva. Ovviamente se la stampante al momento del trasferimento è già occupata, il contenuto dell’area di spool verrà posto in una cosa in attesa che la stampante si renda disponibile

Gestore dei file

Ha lo scopo di fornire ai programmatori un’interfaccia software per l’uso dei dati memorizzati sui supporti magnetici, esonerandolo quindi dalla maggior parte dei problemi di allocazione fisica e da quelli legati alle caratteristiche dei particolari supporti fisici a disposizione.Il programmatore cioè agisce solo in termini di strutture ed operazioni logiche, senza preoccuparsi della loro reale implementazione.

Il file system ha quindi il compito di gestire in modo opportuno tutte le informazioni permanenti e temporanee registrate su memoria di massa e di rendere possibile l’utilizzo, da parte di più utenti, della stessa risorsa informazione (file), proteggendola da accessi non autorizzati.

Ha una struttura gerarchica e ogni modulo interagisce col modulo precedente e successivo.

Moduli del file system

Moduli del file systemRichieste

File system simbolico

File system di base

Modulo di controllo sull’accesso

File system logico

File system fisico

Modulo di lettura Modulo di scrittura

Esamina la richiesta dell’utente e localizza dove sono memorizzate le informazioni

relative al file a cui la richiesta fa riferimento ( usa delle tabelle : directory)

Estrae dalla directory tutte le informazioni

associate al file, rendendole disponibili

Effettua un controllo sulla richiesta per verificare se esistono discrepanze o condizioni di errore (es: operazione

coerente con il tipo di accesso)

Trasforma il numero del record logico richiesto in un riferimento alla

posizione (indirizzo logico) del primo byte del record all’interno del file

Definisce, a partire dall’indirizzo logico fornito dal modulo precedente,

la posizione fisica effettiva dell’elemento del file coinvolto

Trasforma l’indirizzo di blocco in indirizzo effettivo

strutturato nella forma richiesta dalla particolare periferica

Problemi della tecnica di allocazione a

partizione statiche

C’è il rischio di lasciare inutilizzata una grande percentuale di memoria soprattutto se i lavori sono molti o con dimensioni molto diverse tra loro.

Esempio :

S.O.Pippo

Qui

Pluto

80k

115k

140k

170k

Partizioni : Processi :

P1 : 35k Pippo : 10k

P2 : 25k Pluto : 15k

P3 : 30k Qui : 5k

Qua : 40k

90k

130k

145k

Memoria disponibile : 90 k

Memoria usata : 30 k

Memoria inutilizzata : 60 k

Il processo Qua non può essere caricato !!!

Problema Della

frammentazione

Problemi della tecnica di allocazione a

partizione dinamiche

S.O.

Pippo

Pluto

Poldo

Peppo

0 k

80k

190k

170k

230 k

115 k

140 k

Arrivano

Asso : 12k

Milo : 15k

Lupo : 30k

S.O.

Pippo

Pluto

Poldo

Peppo

0 k

80k

115 kAsso

140 k

170k

190k

127 k

Milo205k

230 k

Esce

Poldo : 20 k

Non entra

LUPO!!!

S.O.

Pippo

Asso

Pluto

Milo

Peppo

0 k

80k

115 k

127 k140 k

170k

190k

205k

230 k

Pur essendoci complessivamente ben 58 k disponibili non è possibile caricare un processo di 30 k!!!

Problema Della

frammentazione

Problema della frammentazione

Il maggior problema della allocazione a partizioni della memoria è quello dovuto alla frammentazione della memoria, cioè alla creazione di aree inutilizzabili di memoria sparse tra le partizioni occupate.

Si parla di 2 tipi di frammentazione :

Frammentazione interna : quando all’interno di una partizione di m byte viene allocato un processo di n byte ( con n< m) e resta libera un’area di m-n byte troppo piccola per essere riutilizzata

Frammentazione esterna : quando nella MC si vengono a creare aree libere non contigue talmente piccole da renderle inutilizzabili.

Nella tecnica a partizioni statiche il problema è quello della frammentazione interna, mentre nella tecnica a partizioni dinamiche si presenta il problema della frammentazione sia interna che esterna.

Algoritmi di miglioramento

Algoritmi di miglioramentoL’uso di algoritmi ben calibrati per scegliere quale area assegnare ai diversi processi che ne fanno richiesta può ridurre il problema della frammentazione.

Algoritmo first fit : La tabella delle aree libere viene costantemente riordinata in base agli indirizzi di partenza delle singole aree e quando risulta necessario allocare un processo, la si scandisce assegnando al lavoro la prima area di dimensione maggiore o uguale a quella necessaria. Nell’allocazione a partizioni fisse provoca una forte frammentazione interna, mentre nell’allocazione a partizioni dinamiche permette la formazione di una grande area libera verso il fondo della memoria, pur non eliminando il problema della frammentazione esterna.

Algoritmo best fit : la tabella delle aree libere viene costantemente riordinata in base alla dimensione delle stesse: all’arrivo di un processo si scandisce la tabella per cercare la prima area libera che sia maggiore o uguale alla dimensione del programma cioè quella che si adatta meglio al processo. Nell’allocazione a partizioni fisse migliora la frammentazione interna ; nell’allocazione a partizioni dinamiche la frammentazione esterna rimane un problema.

Algortimo worst fit : si sceglie in tutte le partizioni libere quella che lascia più spazio libero residuo. E’ assolutamente negativa nell’allocazione a partizioni fisse,mentre può fornire ottimi risultati nell’allocazione a partizioni dinamiche.

Esempi

Esempi degli algoritmi di scelta partizione(1)First fit : allocazione statica

P1:20k

P2:50k

P3:30k

Arrivano :

Pippo : 15 k in P1

Pluto : 25 k in P2

Qui : 40 k non può essere caricato

pippo

pluto

Spreco memoria : 30 k di frammentazione interna + una partizione inutilizzata

Best fit : allocazione statica

pippo

Qui

P1:20k

P2:50k

P3:30k

Arrivano :

Pippo : 15 k in P1

Pluto : 25 k in P3

Qui : 40 k in P2Pluto

Spreco memoria : 5k + 10k + 5k = 20k ma tutti i processi caricati

Esempi degli algoritmi di scelta partizione (2)First fit : allocazione dinamica

Pippo

Pluto

qui

0

40

100

130140150

Arrivano :

Qua : 10 k

quo : 30 k

Papero : 25 k non può essere caricato

quaquo

50

80

Spreco memoria : 10 k + 20 k di frammentazione esterna e un processo non caricato

Best fit : allocazione dinamicaPippo

Pluto

Quaqui

0

40

100

130140

150

Arrivano : Qua : 10 k ; Quo : 30 k ; Papero : 25 k Quo

Papero

Spreco memoria : 5k e tutti i processi caricati

Esempi degli algoritmi di scelta partizione (3)First fit e Best fit : allocazione dinamica

Pippo

Pluto

20k

80k

Arrivano :

Qui : 15k

Quo : 62k

Qua : 20 k non può essere caricato

qui

Quo Spreco memoria : 5 k +18k k di frammentazione esterna e un processo non caricato

Worst fit : allocazione dinamicaQua

Pippo

Pluto

20k

80k

Arrivano :

Qui : 15k ; Quo : 62k; Qua : 20 kQui

QuoSpreco memoria : 5 k di frammentazione esterna e tutti i processi caricati

Frame allocation, Page Fault e Page Replacement(1)

I due aspetti (frame allocation e page fault) sono legati in quanto se si sceglie di caricare subito tutte le pagine possibili di ogni processo, allora più facilmente si verifica un’occupazione totale di memoria al momento del page fault di qualche altro processo sopravvenuto nel frattempo; se invece si caricano solo alcune pagine allora capiterà quasi subito un page fault anche per i primi processi accodati in ready.

Esistono diverse soluzioni a tali questioni, ma tutte si basano sempre su considerazioni relative al comportamento medio dei programmi. Statisticamente si può rilevare in ogni programma un’attitudine a conservare costante nello spazio e nel tempo l’insieme degli indirizzi logici generati in esecuzione. Si parla di località nel tempo e nello spazio.

Un programma esibisce una località relativa al fattore spazio, in quanto, indirizzata una certa locazione, è molto probabile che vengano indirizzate le locazioni adiacenti.

Un programma esibisce una località relativa al fattore tempo in quanto, indirizzata una certa locazione, è molto probabile che la stessa venga nuovamente indirizzata in tempo breve.

La strategia più semplice (demand page) prevede che all’atto della creazione di un processo venga caricata in memoria solo la pagina contenente la prima istruzione da eseguire e che ogni altra pagina venga poi allocata su richiesta. ( vantaggio : il n° massimo di processi virtuali corrisponde al n° di pagine fisiche; svantaggio : alto numero di page fault)

Frame allocation, Page Fault e Page Replacement(2)

Un’altra strategia è quella di cercare di sfruttare la località dei programmi per diminuire il numero di page fault. Si carica in memoria l’insieme delle pagine che il processo indirizza più frequentemente in un certo intervallo di tempo. (working set).Il comportamento futuro può solo essere previsto e mai con certezza. Sulla base di previsioni statistiche circa l’andamento del working set viene stabilito il numero di pagine da caricare per ogni nuovo processo.

Quando si verifica un page fault , se ci sono ancora pagine fisiche disponibili non ci sono problemi. In caso contrario occorre togliere una pagina di un processo non in esecuzione. Il cambio di pagina (page swapping) avviene seguendo un apposito algoritmo di sostituzione in base al quale una pagina viene tolta per permettere l’allocazione di un’altra.

La scelta dell’algoritmo di page replacemente deve mediare l’esigenza di semplicità con l’esigenza di contenere entro limiti accettabili il page swapping. Occorre evitare che il sistema sostituisca una pagina che servirà subito dopo e che è preferibile cercare la pagina che non verrà usata per il periodo di tempo più lungo.

Frame allocation, Page Fault e Page Replacement(3)

Gli algoritmi più usati sono :

FIFO : rimuove la pagina in memoria da più tempo

LRU (least recently used) : si seleziona la pagina da sostituire considerando il fattore tempo, ossia viene eliminata la pagina non usata da più tempo.

LFU (least frequently used) : si seleziona la pagina col minor numero di accessi

RilocazioneEsistono 3 tipi di Rilocazione :

Assoluta : è la forma più semplice; avviene al momento della traduzione del programma da sorgente ad oggetto (fase di compilazione o link). Il risultato è un prg in linguaggio assoluto che può essere caricato per l’esecuzione soltanto nelle locazioni di memoria a partire dall’indirizzo base scelto. Questa tecnica è applicabile solo in caso di monoprogrammazione

Vantaggi : semplicità; Svantaggi : memoria sprecata e impossibilità di gestire prg più grandi della capacità della MC

Statica : viene effettuata al momento del caricamento del prg in MC per l’esecuzione. Durante la compilazione gli indirizzi del prog vengono fatti iniziare da un valore relativo riferito alla prima istruzione. Lo stesso prg può essere caricato di volta in volta in aree differenti della MC. Ciò significa che è possibile operare in ambiente di multiprogrammazione.

Svantaggio : una volta caricato un prg in una determinata area non è più possibile spostarlo

Dinamica : avviene al momento dell’esecuzione di ogni singola istruzione. Il codice oggetto viene caricato in MC senza effettuare la rilocazione.

Ciclo Di Avanzamento Di Un ProgrammaIl ciclo di svolgimento del processo di esecuzione può essere rappresentato dalle transizioni tra i diversi stati di avanzamento che può attraversare.

Quando un utente richiede che il proprio programma venga prelevato dalla M.d.M ed inviato al computer per l’elaborazione , il lavoro viene inserito nell’elenco di quelli in attesa di diventare processi in esecuzione (HOLD).

A questo punto il job scheduler avrà il compito di scegliere quale lavoro dovrà essere portato nella M.C. per l’esecuzione. Una volta che lo schedulatore ha scelto il lavoro viene generato il processo associato ed il programma viene caricato in M.C. Il processo passa così dallo stato Hold allo stato Ready.

Sarà poi compito del process scheduler scegliere, tra tutti quelli che si trovano in stato Ready, quello a cui assegnare il processore. Il processo scelto passa così da stato Ready a stato Run.

Quando il processo in Run richiede di accedere a una risorsa esterna, il processo non può avanzare finchè non viene ultimata l’operazione di I/O; pertanto viene rilasciato il processore ed il processo passa da Run a Wait e viene attivato il processo di I/O.

Il compito di definire lo stato dei vari processi è assolto da un particolare modulo del nucleo : il traffic controller.

Al termine dell’operazione di I/O verrà inviato al controllore del traffico un segnale di “operazione conclusa”, il quale provvederà a portare il processo sospeso nuovamente da Wait a stato Ready, in attesa della disponibilità del processore centrale per proseguire l’esecuzione.

Mentre il processo si trova in stato Run si può verificare il superamento del quanto di tempo concesso al processo. In tal caso l’esecuzione viene interrotta, il processo passa da Run a Ready e viene scelto un nuovo processo da porre in esecuzione.

Quando il processo giunge al termine , passa da Run in stato di Terminate , rilasciando le periferiche, la memoria ed il processore, in modo che possano essere usati da altri processi.

Sistemi monoprogrammati

• Gestione sequenziale nel tempo dei programmi

• Tutte le risorse hardware e software del sistema sono dedicate ad un solo programma per volta

• Utilizzo della CPU = Tp/Tt dove Tp è il tempo dedicato dalla CPU alla esecuzione del programma e Tt è il tempo totale di permanenza del programma nel sistema

• Throughput = numero di programma eseguiti per unità di tempo

• Bassa utilizzazione delle risorse

Sistemi General Purpose• Centri di Calcolo di grandi dimensioni

• Utenze di tipo differenziato

• Modalità di uso batch e interattivo

Sistemi Transazionali• Sistemi di tipo interattivo che consentono solo accesso e modifica ad

archivi di dati

• Transazione successione di operazioni elementari a ciascuna delle quali corrisponde l’esecuzione di un programma

• Funzioni richieste all’utente : interrogazione ed aggiornamento archivi

Sistemi per l’elaborazione a distanza• Accesso remoto : di tipo batch (remote job entry); di tipo interattivo (TP )

• L’utente accede al sistema tramite terminali collegati da un sottosistema di comunicazione

• Il S.O. deve gestire le comunicazioni sulle linee, accodare le richieste di servizio, etc

Multiprogrammazione

Più programmi presenti contemporaneamente in memoria centrale

Mentre un programma è in attesa del completamento dell’operazione di I/O, la CPU può iniziare l’esecuzione di un altro programma

vantaggi svantaggi

Migliore utilizzazione delle risorse (riduzione dei tempi morti)

Maggiore complessità del S.O. :

•Algoritmi per la gestione delle risorse

•Protezione degli ambienti dei diversi programmi

Confronto Fra Monoprogrammazione E Multiprogrammazione (1)

Programma P1 : legge 100 record da disco, li elabora e li scrive su stampante

Programma P2 : legge 100 record da disco , li elabora e li scrive su stampante

scrittura

lettura

elabora

tempo

Situazione in monoprogrammazione senza buffer di I/O

lettura

elabora

scrittura

Situazione in monoprogrammazione con buffer di I/O

avanti

Confronto Tra monoprogrammazione E multiprogrammazione (2)

lettura

elabora

scrittura

Sistemi Time sharing (Divisione Di Tempo)

• Estensione della multiprogrammazione

• Ad ogni programma il S.O. Assegna ciclicamente un intervallo (quantum) di tempo di CPU fino al suo completamento

• Al termine dell’intervallo ( o durante, se il programma inizia un’operazione di I/O) la CPU viene assegnata ad un altro programma

• Un S.O. Time sharing consente a più utenti di condividere il sistema di calcolo contemporaneamente ed in modo interattivo

• Interattività : comunicazione diretta tra l’utente ed il sistema di calcolo

SISTEMI BATCH( a Lotti)

• I programmi sono inseriti a lotti nella memoria di massa (occorre un linguaggio di controllo particolare, JCL, che comanda il caricamento del programma, la sua compilazione, la sua esecuzione e altre operazioni; I lavori degli utenti devono essere “autonomi” cioè contenere tutti i comandi necessari per attivare i job step che consentono di eseguire e portare a compimento un programma senza

intervento di un operatore umano)

• Non c’è alcuna interazione tra macchina e utente

vantaggisvantaggi

Sfruttamento intelligente delle risorse in quei casi in cui l’intervento dell’operatore non è strettamente necessario

•Assoluta mancanza di interattività

•Bassa utilizzazione della CPU

Problema Della Mancanza Di Interattività Nei Sistemi batch

• Il problema della mancanza di interattività non rappresenta una limitazione rilevante nel calcolo di tipo scientifico, matematico, etc, mentre è più problematico per alcune applicazioni di tipo gestionale, come pure per una serie di attività comuni nel lavoro di ufficio o, ad esempio, per uno sportello bancario.

• Tuttavia la modalità batch viene ancora utilizzata, anche nei sistemi moderni, ogni qualvolta si voglia eseguire lavori che devono essere eseguiti sempre con gli stessi comandi , nello stesso ordine e spesso in orari prefissati.

1° Soluzione Problemi BATCH

Operazioni di I/O fuori linea (off-line)

CPU

LETTORE DI SCHEDE

STAMPANTENASTRO NASTRO

VANTAGGI

•Maggiore velocità del nastro in confronto al lettore di schede e alla stampante

•Più lettori di schede collegati ad una stessa unità a nastro

•Più stampanti collegate ad una stessa unità a nastro2° SOLUZIONE

2° Soluzione Problema batch : Buffer Di I/O• Il buffer è un’area di memoria per ciascun diapositivo di

I/O

• Il dispositivo di ingresso introduce nel buffer nuovi dati mentre la CPU sta elaborando i dati precedenti (analogamente per l’uscita)

• I buffer sono gestiti dal S.O. (device drivers) : una richiesta di I/O del programma chiama la corrispondente device driver (meccanismo di interrupt)

Quale utilità?

•LIMITATA se la velocità della CPU è molto più elevata di quella dei dispositivi di I/O

•Programmi con prevalente attività di I/O : i buffer sono di poca utilità e la CPU ha periodi di attesa

•Programmi con prevalente attività di CPU : i buffer di input sono quasi sempre pieni e quelli di output vuoti 3° SOLUZIONE

3° Soluzione Problema Batch : spooling• Spooling è un acronimo per Simultaneous Peripheral

Operation on line

• Sostituzione dei nastri magnetici con i dischi (maggiore velocità di lettura e scrittura)

• Il disco è usato come un buffer di grandi dimensioni

Vantaggi :

•Possibilità di sovrapporre le operazioni di I/O e di esecuzione di più programmi

•Più programmi in memoria pronti per l’esecuzione

•Possibilità di scelta da parte del S.O. di quale programma mettere in esecuzione

Il Problema Della Bassa Utilizzazione Della CPU in Un Sistema batch

Lettore di schede 20 schede/sec

Compilazione 300 schede/sec

Programma di 1200 schede

4 sec di CPU, 60 sec. di lettura

UTILIZZAZIONE CPU : 6,25%

OPERAZIONI DI I/O IN LINEA

CPU

LETTORE DI SCHEDE

STAMPANTE

1° SOLUZIONE