Appunti Sistemi operativi

VOLONTARIAMENTE INVOLONTARIAMENTE

Termina Quanto di tempo scaduto

Operazione I/O Page fault

Lancio di una sottoattività con priorità maggiore

Operazione P con semaforo < 1

È possibile che un processo P che gira su un sistema A dotato di memoria virtuale venga eseguito più velocemente che su un sistema

B del tutto identico ad A ma non dotato di memoria virtuale?

Si è possibile, perché i programmi non devono essere completamente caricati in memoria. Ad esempio un processo P che non genera

mai un page fault non deve essere caricato completamente in memoria per essere eseguito.

Come funziona l’algoritmo della seconda chance? Perché l’algoritmo della seconda chance viene considerato una approssimazione di

quello LRU?

L’algoritmo della seconda chance è un FIFO dove viene dato un reference bit ad ogni pagina. Se il valore di tale bit è 0 la pagina viene

sostituita, se è 1 si porta la pagina a 0(si esaurisce la seconda chance), ma non si elimina la pagina, passando quindi a quella successiva

nella coda. La pagina viene eliminata la prossima volta.

Viene considerato un approssimazione all’LRU perché usando il reference bit si riesce a discriminare tra pagine riferite di recente e non

riferite di recente.

Per il CPU scheduling, supponiamo che un certo insieme di processi debba essere trattato con la politica Shortest Job First (SJF) non

preemptive. Esiste un assegnamento di priorità ai processi in modo che la loro esecuzione con la politica a priorità produca

esattamente la stessa sequenza di esecuzione? Se si, come?

Si, utilizzando la tecnica di aging viene assegnata una priorità crescente ai processi.

Quando si parla di gestione della memoria centrale (RAM), cosa si intende con gestione di tipo “contiguo”(Contiguous Memory

Allocation)? Che svantaggi principali presenta?

Ogni file occupa un insieme di blocchi contigui del disco. Il vantaggio è quello di poter accedere a qualsiasi blocco con un solo accesso. Lo

svantaggio è che l’allocazione contigua presenta il problema della frammentazione esterna.

Cos’è un algoritmo di rimpiazzamento?

Un algoritmo di page replacement serve a selezionare in maniera appropriata la pagina “vittima” da eliminare, cioè al verificarsi di un

page fault, la pagina P presente su un frame F da eliminare per fare posto alla nuova pagina.

Quali informazioni sicuramente conterrà ciascuna entry di una page table di un sistema che usa l’algoritmo della seconda chance?

Numero di un frame, bit di validità, bit di riferimento.

Cos’è la multiprogrammazione?

La nozione di multiprogrammazione permette la possibilità di mantenere in memoria più processi contemporaneamente, in modo da

mantenere la CPU occupata il maggior tempo possibile. Questa tecnica si può usare sia su mono che multi processore.

E corretto dire che in un sistema che implementa la memoria virtuale, i processi partono più velocemente (in media)?

Si, perché non devono essere completamente caricati in memoria RAM.

ESERCIZIO SEMAFORI

−N ≤ ≤ N

–

Fare in modo che: numero stampate A numero stampate B

Semafori inizializzati a S = N ,T = N

Come si ovvia allo svantaggio delle permutazioni nella crittografia simmetrica?

Si utilizza un cifrario a blocchi. Nella crittografia, un cifrario a blocchi è un algoritmo deterministico che opera su gruppi di bit a lunghezza

fissa, chiamati blocchi, con una trasformazione invariabile che viene specificata da una chiave simmetrica.

Perché i moderni sistemi operativi usano una gestione paginata della memoria primaria?

I sistemi operativi moderni usano delle tecniche chiamate segmentazione e paginazione (anche usate insieme), che consentono di usare

la memoria principale con efficienza e senza sprechi.

Per una periferica di I/O, cosa e' il controller? E il device driver? Fanno entrambi parte del sistema operativo?

Un dispositivo di I/O è costituito da due componenti:

-Il dispositivo fisico effettivo (mouse, video, ecc..);

-Il device controller, che gestisce tutte le operazioni che il dispositivo è in grado di svolgere.

Il device controller è collegato attraverso il bus di sistema con CPU e memoria principale e fornisce eventuali registri dove possono

essere appoggiati i dati del trasferimento ed i comandi ai dispositivi. Un device driver è un programma per computer che gestisce o

controlla un particolare tipo di dispositivo collegato a un computer. Un driver fornisce un'interfaccia software ai dispositivi hardware,

consentendo ai sistemi operativi e ad altri programmi per computer di accedere alle funzioni hardware senza dover conoscere dettagli

precisi sull'hardware utilizzato. A fronte di una richiesta di I/O, il processore tramite il device driver invia al DMA controller:

-Tipo di operazione richiesta

-Indirizzo di memoria da cui iniziare a leggere/scrivere i dati

-Numero di byte da leggere/scrivere

Cos'è il problema della frame allocation? Descrivere brevemente 2 politiche per questa situazione

Il problema della frame allocation ci si presenta quando abbiamo un quantitativo fisso di memoria libera da allocare ad i vari processi del

Sistema. Ad esempio, se abbiamo 93 frame e 5 processi, quanti frame ogni processo utilizzerà?

Tramite algoritmi di allocazione dei frame, possiamo decidere quanti frame allocare a ciascun processo. Il modo più semplice per

suddividere m frame tra n processi e quello per cui a ciascuno si da una parte uguale, m/n frame. Dati 93 frame e cinque processi, ogni

processo riceve 18 frame. I tre frame lasciati liberi si potrebbero usare come gruppo dei frame liberi.

Questo schema e chiamato allocazione uniforme. Un’alternativa consiste nel riconoscere che diversi processi hanno bisogno di quantità

di memoria diverse. Si consideri un sistema con frame di 1 KB. Se un piccolo processo utente di 10 KB e una base di dati interattiva di

127 KB sono gli unici due processi in esecuzione su un sistema con 62 frame liberi, non ha senso allocare a ciascun processo 31 frame. Al

processo utente non ne servono più di 10, quindi gli altri 21 sarebbero semplicemente sprecati.

Per risolvere questo problema e possibile ricorrere all’allocazione proporzionale, secondo cui la memoria disponibile si assegna a ciascun

processo secondo la propria dimensione. Sia nell’allocazione uniforme sia in quella proporzionale, l’allocazione a ogni processo puo ̀

variare rispetto al livello di multiprogrammazione. Se tale livello aumenta, ciascun processo perde alcuni frame per fornire la memoria

necessaria per il nuovo processo. D’altra parte, se il livello di multiprogrammazione diminuisce, i frame allocati al processo allontanato si

possono distribuire tra quelli che restano.

Cos’e’ un semaforo binario?

i semafori che sono limitati ai valori 0 e 1 (o bloccati / sbloccati, non disponibili / disponibili) sono chiamati semafori binari e vengono

utilizzati per implementare i lock. In generale gestisce “una sola” risorsa condivisa, con mutual exclusion, e i processi possono essere

tanti, qualsiasi numero .

Priority scheduling

algoritmo che esegue prima i processi con priorità più alta. Se hanno stessa priorità vengono eseguiti in ordine di arrivo.

Esistono i semafori in Java? Perche’?

No, non esistono. Java adotta dei meccanismi di sincronizzazione più ad alto livello (synchonised methods) che facilitano la

programmazione, per esempio limitano la possibilità di avere dei deadlock.

Algoritmo optimal guardo futuro

→

Algoritmo LRU guardo passato

→

ALIASING

I sistemi Unix fanno largo uso di link: dei file speciali che sono semplici collegamenti o alias di file esistenti.

Servono per identificare lo stesso file o directory con nomi diversi, avendo anche path diversi.

Su Unix esistono due tipi di link: Hard link e Symbolic link (soft link).

Hard Link

Sono di fatto una copia di una voce di directory, hanno nomi diversi ma puntano allo stesso inode e quindi condividono esattamente lo

stesso dato (oltre agli stessi permessi, data di modifica, owner ecc.).

Dal momento che originale e link sono indistinguibili e condividono lo stesso inode, non si possono fare hard link fra file system diversi.

Pur essendo la gestione dei link comunque molto rapida da parte del kernel, gli hard link sono leggermente più "economici" in quanto

risparmiano più spazio su disco (stesso i-node, stessi dati) e richiedono una lettura in meno sul file system (i symlink hanno i-node

diverso e puntatore, che va letto, ad un altro file).

Symbolic Link o Symlink

Sono dei piccoli file che contengono un puntamento ad altri file o directory. Questi file hanno i-node autonomo e possono puntare a file

di altri file system (sia locali, che di rete). I symlink sono generalmente molto più utilizzati nell'amministrazione di sistemi Unix e

corrispondono come concetto e come implementazione ai collegamenti (shortcut) del mondo Windows. Un symlink appare come

avente tutti i permessi aperti a tutti gli utenti, di fatto è trasparente rispetto a permessi e ownership e riflette quelli del file o directory a

cui punta.

La differenza sostanzialmente è questa:

▪ un hard link è un "file vero e proprio", che viene autoaggiornato se viene aggiornato quello originale, e non viene cancellato se viene

cancellato quello originale (è una specie di copia sincronizzata); dal punto di vista tecnico, condividono lo stesso inode, e questo fa si

che abbiano gli stessi attributi (dimensioni, permessi, date di creazione / modifica), ma fa anche si che non si possono creare su

filesystem diversi

▪ un symoblic link è il classico collegamento, quindi un puntamento al file originale

ESERCIZIO:

Si consideri un file system che permette aliasing (cioe’ links). Supponi- amo che abbiamo i file:

/home/john/file.txt

/user/local/temp.txt

dove "temp.txt" e "file.txt" fanno riferimento agli stessi insiemi di blocchi di dati su disco (cioe’: lo stesso file). Se "temp.txt" era un

“hard-link”, cosa succederebbe se il file "file.txt" fosse cancellato? E se "temp.txt" era un soft-link ?

Risposta: Se temp.txt era un hard-link e si toglie file.txt, si decrementerebbe il reference count del file descriptor cui il file.txt fa

riferimento. Si potrebbe ancora accedere a temp.txt normalmente. Se temp.txt fosse un soft-link, togliendo file.txt, si toglierebbe il

descrittore e i data blocks cui fa riferimento. Non si farebbe nulla su temp.txt. Ma quando si cercasse poi di accedere a temp.txt, il

sistema si lamenterebbe dando "invalid filename" o qualcosa del genere, indicando che fa riferimento ad un file che non esiste.

Quelli sotto sono alcuni tra gli algoritmi per page-replacement visti a lezione. Indicare per almeno 2 di essi il problema principale che

comporta.

• First-In First-Out

• Optimal Algorithm

• L