AXO - Prova 4 Febbraio 2016 - Con Sol

8/19/2019 AXO - Prova 4 Febbraio 2016 - Con Sol

1/19

Politecnico di MilanoDipartimento di Elettronica, Informazione e Bioingegneria

prof.ssa Anna Antolaprof. Luca Breveglieriprof. Roberto Negrini

prof. Giuseppe Pelagattiprof.ssa Donatella Sciutoprof.ssa Cristina Silvano

AXO – Architettura dei Calcolatori e Sistemi OperativiProva di giovedì 4 febbraio 2016

Cognome ________________________ Nome _______________________

Matricola _____________________ Firma ___________________________

Istruzioni

- Si scriva solo negli spazi previsti nel testo della prova e non si separino i fogli.

- Per la minuta si utilizzino le pagine bianche inserite in fondo al fascicolo distribuito con il testo dellaprova. I fogli di minuta se staccati vanno consegnati intestandoli con nome e cognome.

- È vietato portare con sé libri, eserciziari e appunti, nonché cellulari e altri dispositivi mobili di calcoloo comunicazione. Chiunque fosse trovato in possesso di documentazione relativa al corso – anche senon strettamente attinente alle domande proposte – vedrà annullata la propria prova.

- Non è possibile lasciare l’aula conservando il tema della prova in corso.

- Tempo a disposizione 2 h : 15 m

Valore indicativo di domande ed esercizi, voti parziali e voto finale:

esercizio 1 (4 punti) _________________________

esercizio 2 (3 punti) _________________________

esercizio 3 (2 punti) _________________________

esercizio 4 (2 punti) _________________________

esercizio 5 (3 punti) _________________________

esercizio 6 (2 punti) _________________________

voto finale: (16 punti) ______________________

CON SOLUZIONI (in corsivo)


2/19

AXO – prova di giovedì 4 febbraio 2016 – CON SOLUZIONI pagina 2 di 19

esercizio n. 1 – programmazione concorrente

Si consideri il programma C seguente (gli “#include” e le inizializzazioni dei mutex sono omessi):

pthread_mutex_t black, white

sem_t new, old

int global = 0

void left (void arg)

pthread_mutex_lock (&black)

sem_post (&new) / statement A /

global = 1

pthread_mutex_unlock (&black)

return NULL

/ end left /

void mid (void arg)

pthread_mutex_lock (&black)

sem_wait (&new)

sem_wait (&old)

pthread_mutex_lock (&white) / statement B /

pthread_mutex_unlock (&white)

sem_post (&old)

pthread_mutex_unlock (&black)

return (int ) arg

/ end mid /

void right (void arg)

pthread_mutex_lock (&white) / statement C /

sem_wait (&old)

pthread_mutex_unlock (&white)

global = 3

return NULL

/ end right /

void main ( )

pthread_t th_1, th_2, th_3

sem_init (&new, 0, 0)sem_init (&old, 0, 1)

pthread_create (&th_2, NULL, mid, (void ) 2)

pthread_create (&th_1, NULL, left, NULL)

pthread_create (&th_3, NULL, right, NULL)

pthread_join (th_1, NULL)

pthread_join (th_2, &global) / statement D /

pthread_join (th_3, NULL)

return

/ end main /


3/19


Si completi la tabella qui sotto indicando lo stato di esistenza del thread nell’istante di tempospecificato da ciascuna condizione, così: se il thread esiste, si scriva ESISTE; se non esiste, si scriva NONESISTE; e se può essere esistente o inesistente, si scriva PUÒ ESISTERE. Ogni casella della tabella variempita in uno dei tre modi (non va lasciata vuota).

Si badi bene alla colonna “condizione”: con “subito dopo statement X” si chiede lo stato che il thread assumetra lo statement X e lo statement immediatamente successivo del thread indicato.

condizionethread

th_1 th_2 th_3

subito dopo stat. A ESISTE ESISTE PUÒ ESISTERE

subito dopo stat. B PUÒ ESISTERE ESISTE PUÒ ESISTERE

subito dopo stat. C PUÒ ESISTERE PUÒ ESISTERE ESISTE

subito dopo stat. D NON ESISTE NON ESISTE PUÒ ESISTERE

Si completi la tabella qui sotto, indicando i valori delle variabili globali (sempre esistenti) nell’istantedi tempo specificato da ciascuna condizione. Il valore della variabile va indicato così:

intero, carattere, stringa, quando la variabile ha un valore definito; oppure X quando è indefinita

se la variabile può avere due o più valori, li si riporti tutti quanti

il semaforo può avere valore positivo o nullo (non valore negativo)

Si badi bene alla colonna “condizione”: con “subito dopo statement X” si chiede il valore (o i valori) che lavariabile ha tra lo statement X e lo statement immediatamente successivo del thread indicato.

condizione variabili globali

new old global

subito dopo stat. A 1 0 / 1 0 / 3

subito dopo stat. B 0 0 1

subito dopo stat. D 0 0 / 1 2 / 3

Il sistema può andare in stallo (deadlock), con uno o più thread che si bloccano, in tre casi diversi (con deadlock si intende anche un blocco dovuto a un solo thread che non potrà mai proseguire). Si

indichino gli statement dove avvengono i blocchi, con il valore (o i valori) della variabile global:

caso th_1 th_2 th_3 global

! lock black wait new 0 / 3

" lock white wait old 1

# wait old 1 / 3


4/19


5/19


TABELLA DA COMPILARE (numero di colonne non significativo)

identificativo simbolico del processo IDLE S P TH1 Q TH2 R

PID 1 2 3 4 5 6 7

evento processo-chiamata TGID 1 2 3 2 5 2 7

S – sem_init 0 pronto esec pronto NE NE NE NE

S – pthread_create TH1 10 pronto esec pronto pronto NE NE NE

interrupt da RT _clock,scadenza quanto di tempo 20

pronto pronto esec pronto NE NE NE

P – pid1 fork 30 pronto pronto esec pronto pronto NE NE

P – open 40 pronto pronto A (open) esec pronto NE NE

TH1 – sem_wait 50 pronto esec A A(s_wait) pronto NE NE

S – pthread_create TH2 60 pronto esec A A pronto pronto NE

interrupt da DMA_in , tuttii blocchi richiesti trasferiti 70

pronto pronto esec A pronto pronto NE

P – pid2 fork 80 pronto pronto esec A pronto pronto pronto

P – waitpid (pid1) 90 pronto pronto A (wait) A esec pronto pronto

Q – execl 100 pronto pronto A (wait) A esec pronto pronto

interrupt da RT _clock,scadenza quanto di tempo

110 pronto pronto A (wait) A pronto esec pronto

TH2 – mutex_lock 120 pronto pronto A (wait) A pronto esec pronto

TH2 – sem_post 130 pronto pronto A (wait) esec pronto pronto pronto

TH1 – mutex_lock 140 pronto esec A (wait) A (lock) pronto pronto pronto

S – pthread_join (TH2) 150 pronto A (join) A (wait) A (lock) pronto pronto esec

R – write 160 pronto A (join) A (wait) A (lock) esec pronto A(write)

Q – exit 170 pronto A (join) esec A (lock) NE pronto A(write)

P – exit 180 pronto A (join) NE A (lock) NE esec A(write)

TH2 – mutex_unlock 190 pronto A (join) NE esec NE pronto A(write)

TH1 – sem_post 200 pronto A (join) NE esec NE pronto A(write)


6/19


esercizio n. 3 – funzioni di scheduling

È data la tabella di scheduling mostrata alla pagina successiva, con un elenco di attività e tempi. Valgono leconvenzioni seguenti:

i tempi di esecuzione sono misurati in millisecondi (ms )

i parametri di CFS hanno i valori di default: LT 6 ms , GR 0,75 ms e WGR 1 ms

Le attività già specificate o ancora da specificare si annotano così:

exe U x ms ti .nome_funzione_di_SO ... csw ti tj un task (da determinare) haeseguito codice utente (modo U )dal tempo assoluto precedentefino al tempo assoluto x ms

il task ti ha eseguita lafunzione_di_SO ; se serve, si specificaun oggetto ... (argomento oindicazione utile); se il tempo non èdato, la funzione consuma un tempotrascurabile

avviene la commutazione dicontesto dal task ti al task tj ; iltempo di commutazione dicontesto è sempre trascurabile

Si effettui lo scheduling CFS dei task (classe NORMAL ) indicati sulla base di azioni e tempi indicati nellecolonne ATTIVITÀ e TEMPI, compilando i campi vuoti non oscurati. Per ogni riga, vanno riportati i valoriche si avranno alla fine dell’attività.

La colonna TASK e CONDIZIONI è per le eventuali annotazioni ausiliarie: a ciascuna attività specificata siaggiunge il nome del task che la svolge, si calcola il VRT di risveglio, si valuta una condizione di preemption ,o si dice se scade il quanto. Se è implicato dalle azioni specificate, task esistenti possono terminare e task nuovi possono essere creati (in quest’ultimo caso si usino le eventuali colonne lasciate vuote in partenza).

PER RISOLVERE L’ESERCIZIO SI USI LA TABELLA PREPARATA A PAGINA SEGUENTE.


7/19


TABELLA DI SCHEDULING DA COMPLETARE

ATTIVITÀ TEMPOTASK e

CONDIZIONIRUNQUEUE

TASK

L0 1 t1 LOAD 1

t2 LOAD 3

t3 LOAD 1

inizio 0 ms

NRT LC

PER Q

RQL VRTC

CURR t2 DELTA 0 0 0

RB t3, t1 SUM 1,2 0 1,2

VMIN 0 VRT 1,2 0 1,2

exe U 4,6 ms

NRT LC

PER Q

RQL VRTC

CURR DELTA

RB SUM

VMIN VRT

wait_event

exe U 5,6 ms

NRT LC

PER Q

RQL VRTC

CURR DELTA

RB SUM

VMIN VRT

sys_exit

exe U 8,6 ms

NRT LC

PER Q

RQL VRTC

CURR DELTA

RB SUM

VMIN VRT

wake_up

exe U 9,8 ms

NRT LC

PER Q

RQL VRTC

CURR DELTA

RB SUM

VMIN VRT


8/19


SOLUZIONE

ATTIVITÀ TEMPOTASK e

CONDIZIONI RUNQUEUE TASK

L0 1 t1 LOAD 1

t2 LOAD 3

t3 LOAD 1

inizio 0 ms

NRT 3 LC 1 / 5 0,2 3 / 5 0,6 1 / 5 0,2PER 6 Q 61/5 1,2 63/5 3,6 61/5 1,2RQL 5 VRTC 1 / 1 1 1 / 3 0,33 1 / 1 1

CURR t2 DELTA 0 0 0

RB t3, t1 SUM 1,2 0 1,2 VMIN 0 VRT 1,2 0 1,2

exe U 4,6 ms

t2.exe U 3,6t2.Q scade

csw t2 t3t3.exe U 4,6

NRT 3 LC 0,2 0,6 0,2PER 6 Q 1,2 3,6 1,2RQL 5 VRTC 1 0,33 1

CURR t3 DELTA 0 3,6 1RB t1, t2 SUM 1,2 3,6 2,2

VMIN 1,2 VRT 1,2 1,2 2,2

wait_event

exe U 5,6 ms

t3.wait_eventcsw t3 t1

t1.exe U 5,6

NRT 2 LC 1 / 4 0,25 3 / 4 0,75

IN ATTESA

PER 6 Q 61/4 1,5 63/4 4,5RQL 4 VRTC 1 0,33

CURR t1 DELTA 1 0RB t2 SUM 2,2 3,6 VMIN 1,2 VRT 2,2 1,2

sys_exit

exe U 8,6 ms

t1.sys_exitcsw t1 t2t2.exe U 8,6

NRT 1 LC

TERMINATO

3 / 3 1

IN ATTESA

PER 6 Q 63/3 6RQL 3 VRTC 0,33

CURR t2 DELTA 3RB vuota SUM 6,6

VMIN 2,2 VRT 2,2

wake_up

exe U 9,8 ms

t2.wake_up t3t3.VRT max (2,2,

2,2 6/2) 2,2

t2.cond_pr2,210,252,2

falsa t2.exe U 9,8

NRT 2 LC

TERMINATO

3 / 4 0,75 1 / 4 0,25PER 6 Q 63/4 4,5 61/4 1,5RQL 4 VRTC 0,33 1

CURR t2 DELTA 4,2 0RB t3 SUM 7,8 2,2

VMIN 2,2 VRT 2,6 2,2

Il sistema parte con tre task in round robin, con pesi diversi ma con incrementi di VRT uguali per quanto,ossia VRT 1,2 ms per tutti e tre i task. Ecco i passaggi salienti:

all’inizio il task t2 esegue per 3,6 ms, poi scade il quanto di t2 e il sistema commuta a t3, che è il taskLFT in coda RB

il task t3 esegue per 1 ms; poi chiama un servizio di SO, si autosospende con wait_event e il sistemacommuta a t1, che è il task LFT in coda RB; i parametri vengono ricalcolati

il task t1 esegue per 1 ms; poi termina con sys_exit e il sistema commuta t2, che è il task LFT (e anzi èl’unico task) in coda RB, la quale dunque resta vuota; i parametri vengono ricalcolati

il task t2 esegue per 3 ms; poi risveglia il task t3 (l’unico in attesa – dunque può essere solo t3 il task darisvegliare), lo rimette in coda RB (che era vuota – dunque il task t3 risvegliato diventa il task LFT), mamantenendogli il VRT che aveva poiché si ha:

t3.VRT max (t3.VRT, VMIN LT / 2) max (2,2, 2,2 6 / 2) 2,2 (l’attesa di t3 è stata breve)

e infine il task t2 valuta per il task t3 risvegliato la condizione di preemption:

t3.VRT WGR t3.LC CURR.VRT ossia (ora il task CURR è t2) 2,2 1 0,25 2,2

che risulta falsa (di nuovo poiché l’attesa di t3 è stata breve), e così il task t2 NON imposta larischedulazione; i parametri vengono ricalcolati

il task t2 si avvia al rientro modo U, il sistema NON rischedula, pertanto il task t2 prosegue ed esegue per altri 1,2 ms (DELTA arriva a 4,2), poi la simulazione finisce senza che il task t2 abbia consumatotutto il suo quanto (infatti ha consumato 4,2 ms su un quanto che correntemente è di 4,5 ms)

Si noti che in tre momenti il numero di task runnable NRT varia e alcuni parametri globali del sistema (NRT eRQL) e locali di task (LC e Q) vengono ricalcolati.


9/19


esercizio n. 4 – memoria e paginazione

Regole generali:

il codice e i dati dell’eseguibile iniziano agli indirizzi standard

viene sempre allocata una pagina per le costanti all’inizio dell’area dati le pagine iniziali delle aree randomizzate vanno ricavate dalle indicazioni fornite

gli indirizzi virtuali e fisici sono espressi in esadecimale

le componenti degli indirizzi decomposti sono espresse in decimale

nel caricamento iniziale le pagine vengono allocate nell’ordine di indirizzi virtuali crescenti

il contenuto della tabella delle pagine (TP ) viene riportato in ordine di allocazione, anche se noncoincide con l’ordine di indirizzi virtuali crescenti

Un programma X ha le caratteristiche seguenti:

indirizzo virtuale di argv : 0x 0000 7FFF C090 0080 dimensione codice: 3 K byte dimensione costanti: 1 K byte dimensione dati: 2 K byte dimensione iniziale pila: 1 K byte

In tutte le domande seguenti le pagine fisiche richieste dal programma vengono messe a disposizione nel

seguente ordine: A04, A05, A06, A07, A08, A09, A0A, A0B, ecc.

Domanda 1: si decomponga l’indirizzo di argv per ottenere la pagina iniziale della pila.

PGD PUD PMD PT OFFSET

255 511 4 256 128

Domanda 2: Un processo P ha svolto queste operazioni in sequenza:

lancio in esecuzione del programma X (exec di X ) allocazione di 2 pagine aggiuntive di pila allocazione di 6 K byte di dati dinamici

Si indichi il contenuto della tabella delle pagine di P , sapendo che il risultato dell’esecuzione di sbrk (0)DOPO l’allocazione dei dati dinamici è: 0x 0000 0000 00B0 7000.

L’indirizzo finale (casualizzato) dell’area dati dinamici, decomposto, è 0:0:5:263. Ecco la TP di P:

PGD PUD PMD PT NPF FLAG

RO/RW X/NX

0 0 2 0 A04 RO X

0 0 3 0 A05 RO NX0 0 3 1 A06 RW NX

255 511 4 256 A07 RW NX

255 511 4 255 A08 RW NX

255 511 4 254 A09 RW NX

0 0 5 261 A0A RW NX

0 0 5 262 A0B RW NX


10/19


Domanda 3: I processi hanno svolto queste operazioni in sequenza:

il processo P ha creato un processo figlio Q tramite fork

il processo Q ha scritto nella cella in cima alla pila

Si indichi il contenuto della tabella delle pagine del processo P (padre).

I processi padre (normale) P e figlio (normale) Q condividono le pagine, tutte marcate in sola lettura (se giànon lo erano, come p. es. il codice) per permettere l’eventuale separazione on demand a tempo debito(quando venissero accedute in scrittura – si veda poi la domanda 4), tranne la pagina in cima alla pila dovela funzione fork scrive il risultato (cioè il pid del figlio o zero), la quale pagina viene dunque separata subito

al momento della creazione: il padre P ne prende una nuova, numero A0C, il figlio Q (qui non mostrato)mantiene quella vecchia (numero A09), ed entrambe sono marcate in RW. Ecco la tabella delle pagine di P:


RO/RW X/NX

0 0 2 0 A04 RO X

0 0 3 0 A05 RO NX

0 0 3 1 A06 RO NX

255 511 4 256 A07 RO NX

255 511 4 255 A08 RO NX

255 511 4 254 A0C RW NX

0 0 5 262 A0A RO NX

0 0 5 263 A0B RO NX


11/19


Domanda 4 I processi hanno svolto queste operazioni in sequenza:

il processo P ha creato un processo figlio R tramite pthread_create

il processo R ha modificato una variabile globale del programma

Si indichi il contenuto della tabella delle pagine del processo R (figlio).

Si ricorda che i processi padre (normale) P e figlio (thread) R hanno una sola tabella delle pagine, condivisa.Prima, da parte di pthread_create, viene allocata una pagina fisica (numero A0D) per la pagina di pila del

processo thread R creato (la entry del PGD è 254, come sempre per le pile dei thread nel modello virtualestandard dei processi di Linux). Poi, si osservi che modificare una variabile globale causa la separazione della

pagina dei dati statici di P / R rispetto al figlio Q creato in precedenza (domanda 3), il quale ha pagina datistatici ancora condivisa con P. Dunque tale modifica di variabile causa l’allocazione di una nuova pagina didati statici (numero A0E) in RW, naturalmente sempre condivisa tra i due processi P / R poiché R è un

processo thread secondario del processo normale P. Ecco la tabella delle pagine di R (che è anche di P):


RO/RW X/NX

0 0 2 0 A04 RO X

0 0 3 0 A05 RO NX

0 0 3 1 A0E RW NX

255 511 4 256 A07 RO NX

255 511 4 255 A08 RO NX

255 511 4 254 A0C RW NX

0 0 5 262 A0A RO NX

0 0 5 263 A0B RO NX

254 511 511 511 A0D RW NX


12/19


esercizio n. 5 – memoria e allocazione

Si consideri una memoria fisica di 32 K byte disponibile per i processi di modo U , con MIN_FREE 2 eMAX_FREE 3. In memoria sono presenti due processi P e Q , e il processo P è in esecuzione.

Ecco la dimensione iniziale delle aree virtuali degli eseguibili dei programmi X e Y che verranno utilizzati:

XC 8 K byte XS 4 K byte XM 2 K byte

YC 4 K byte YS 8 K byte YM 2 K byte

La pagina M dei due programmi X e Y è condivisa.

stato iniziale per la gestione della memoria fisica

Processi esistenti: P e Q , il processo P esegue il programma X e il processo Q è in stato di pronto. Si fal’ipotesi che le pagine di pila di Q abbiano dirty bit D 1, e che la pagina condivisa abbia dirty bit D 0.

liste LRU

attivazioni processi active inactive

iniziale P Q PC0 PP0 qc0 qp1 qm0 qp0

memoria fisica (solo modo U )

NPF NPV NPF NPV NPF NPV NPF NPV

0 qc0 1 qp0 2 qp1 3 pc0

4 pp0 5 qm0 6 7

swap file inizialmente vuoto

TLB (solo righe di modo U )

NPV NPF D A NPV NPF D A

pc0 3 1

pp0 4 1 1


13/19


Domanda 1

Il processo P esegue una chiamata a funzione il cui record di attivazione richiede una nuova pagina di pila.

Si compilino la tabella delle pagine, il TLB e le liste LRU .

L’evento di chiamata a funzione utente comporta l’aggiunta della pagina virtuale di pila pp1 e la suaallocazione, in quanto la pagina viene acceduta dalla chiamata a funzione. Ora vale FREE 2. Poiché valeFREE 1 1 MIN_FREE, è necessario invocare PFRA per portarsi a MAX_FREE 1 4. Dunque occorrerilasciare due pagine prima di potere allocare la nuova pagina di pila. Prima si rilascia la pagina qp0 (che è incoda alla inactive), liberando la pagina fisica 1, e si copia qp0 nello swap file poiché il suo dirty bit D vale 1(ipotesi iniziale), e poi si rilascia anche la pagina qm0 (che ora è in coda alla lista inactive), liberando la

pagina f isica 5, senza copiare qm0 nello swap file poiché il suo dirty bit D vale 0 (ipotesi iniziale). Nel TLB siregistra la pagina pp1 aggiunta, poiché viene acceduta come detto prima con dirty bit D uguale a 1 (lafunzione scrive nell’area di attivazione). La pagina pp1 aggiunta entra in testa alla lista active, con referenza.



0 qc0 1 pp1 2 qp1 3 pc0

4 pp0 5 6 7

swap file qp0



pc0 3 1

pp0 4 1 1

pp1 1 1 1

liste LRU


iniziale P Q PC0 PP0 qc0 qp1 qm0 qp0

finale P Q PP1 PC0 PP0 qc0 qp1


14/19


Domanda 2

Il processo P crea il processo figlio R (P esegue fork ); il processo P rimane in esecuzione.

Si compilino la tabella delle pagine, il TLB e le liste LRU .

L’evento di creazione comporta la duplicazione della cima delle pila, con il processo padre P che deveallocare la pagina nuova (pp1 in pagina fisica 5) e il processo figlio R che tiene la vecchia (rp1 che resta in

pagina f isica 1); per il momento tutte le altre pagine di P restano condivise tra padre P e f iglio R. Ora valeFREE 3. Poiché NON vale FREE 1 2 MIN_FREE, l’algoritmo PFRA NON viene attivato. Dunque vieneallocata una sola pagina fisica (la prima libera ossia la numero 5) per pp1. Il TLB cambia, poiché ora la

pagina virtuale pp1 è associata alla pagina f isica 5 con il suo dirty bit D uguale a 1. Le pagine di R (rc0, rp0e rp1) entrano in testa alla lista active, con referenza, nell’ordine virtuale noto.



0 qc0 1 rp1 2 qp1 3 pc0 / rc0

4 pp0 / rp0 5 pp1 6 7

swap file qp0



pc0 3 1

pp0 4 1 1

pp1 5 1 1

liste LRU


iniziale P Q PP1 PC0 PP0 qc0 qp1

finale P Q R RC0 RP0 RP1 PP1 PC0 PP0 qc0 qp1


15/19


Domanda 3

Il processo P accede al codice e alla pagina in cima alla pila. Durante questo periodo viene eseguita ildaemon kswapd .

Si compilino la tabella delle pagine e le liste LRU .

Il daemon kswapd esegue l’algoritmo Controlla_liste: le pagine pc0 e pp1 di P, già in lista active, conreferenza, e ora accedute, vanno in testa alla lista active, con referenza; le altre pagine con referenza inactive perdono la referenza, tranne pp0 che da TLB risultava anch’essa essere stata acceduta e che quindi va

pure in testa alla lista active mantenendo la referenza; mentre la pagina qc0, in active senza referenza, va intesta a inactive con referenza. Poiché vale FREE 2 MAX_FREE, il daemon kswapd attiva l’algoritmo PFRAe questo deve scaricare una pagina per ritornare a MAX_FREE; dunque si scarica la pagina qp1 (che è incoda a inactive), e la si copia in testa alla swap file poiché il suo dirty bit D vale 1 (ipotesi iniziali). Nota: lostato del TLB non è richiesto, comunque l’algoritmo Controlla_liste azzererebbe tutti i bit A delle pagine nelTLB, tranne i bit A di quelle che vengono accedute (poiché vengono accedute sia prima sia dopo l’attivazionedi kswapd).



0 qc0 1 rp1 2 3 pc0 / rc0

4 pp0 / rp0 5 pp1 6 7

swap file qp1 qp0

liste LRU


iniziale P Q R RC0 RP0 RP1 PP1 PC0 PP0 qc0 qp1

finale P Q R PP1 PC0 PP0 rc0 rp0 rp1 QC0


16/19


Domanda 4

Il processo P esegue una wait e va in stato di attesa, il processo R viene posto in esecuzione e chiama unaexecl per mandare in esecuzione il programma Y .

Si compilino la tabella delle pagine e le liste LRU .

Il processo P esce dall’esecuzione (e si avrebbe flush completo del TLB). Prima la execl di R deve separare il processo R dal processo padre P, poiché le pagine rc0 e rp0 sono ancora condivise con P (si noti che il processo R ha già una pagina di pila separata, rp1). Poi, considerando il modello virtuale del programma Y, la

execl di R deve allocare due nuove pagine per R: una nuova di codice e una nuova di pila (per ora le due pagine dei dati statici di R non vengono allocate – la loro eventuale allocazione avverrebbe in seguito surichiesta). Pertanto la execl di R smarca le pagine rc0 e rp0 condivise con P, e rilascia la pagina rp1; inoltre laexecl di R le toglie tutte e tre della lista active, poiché essa ha successo e non si rientra al vecchio codice diR; così ora ci sono quattro pagine libere, cioè vale FREE 4. Poiché NON vale FREE 2 2 MIN_FREE,l’algoritmo PFRA NON viene attivato. Ora si allocano rc0 (in pagina fisica 1) e rp0 (in pagina fisica 2). Le

pagine rc0 e rp0 nuove vengono inserite in testa alla lista active, con referenza, nell’ordine virtuale noto.



0 qc0 1 rc0 2 rp0 3 pc0

4 pp0 5 pp1 6 7

swap file qp1 qp0

liste LRU


iniziale P Q R PP1 PC0 PP0 rc0 rp0 rp1 QC0

finale P Q R RC0 RP0 PP1 PC0 PP0 QC0


17/19


esercizio n. 6 – file system e I/O

Un processo P esegue il programma mostrato di seguito, creando un processo figlio Q , che a sua volta creaun processo figlio R .

int main ( ) / processo P /

/ dichiarazioni varie /

fd1 = open ("/cat1/cat3/file1", O_RDONLY)

read (fd1, bufP1, 3)

pid = fork ( )

if (pid == 0) / processo Q /


read (fd2, bufQ1, 3)

lseek (fd2, -3, 2) / 2 = rif. relativo a fine del file /

pid = fork ( )

if (pid == 0) / processo R /


read (fd3, bufR3, 6)


fd4 = dup (fd3)


exit (0)

/ end if /

pid = wait (NULL)read (fd2, bufQ2, 1)

close (fd2)

close (fd1)

exit (0)

/ end if /

exit (0)

/ end main /

A un certo istante di tempo T 1 si sono verificati i tre eventi seguenti:

1) dopo l’esecuzione della prima fork è andato subito in esecuzione il processo Q

2) dopo l’esecuzione della seconda fork è andato subito in esecuzione il processo R

3) il processo R è arrivato alla funzione exit , ma non la ha ancora eseguita

A un certo istante di tempo successivo T 2 T 1 si è aggiunto il seguente evento:

4) il processo Q ha eseguita la funzione exit


18/19


Il contenuto del volume durante l’esecuzione è il seguente:

i-lista: < 0, dir ,8 > < 3, dir, 9 > < 7, dir, 20 > < 10, dir, 12 > < 72, norm, 60 >< 86, norm, 72 > < 92, norm, 90 >

blocco 8: … < 1, dev > < 3, cat1 > …

blocco 9: … < 7, cat3 > … < 10, cat2 >…

blocco 12: … < 72, file3 >

blocco 20: … < 92, file1 > … < 86, file2 >…

blocco 60: ITALIANOblocco 72: INGLESE

blocco 90: FRANCESE

Nota bene: lo i-node associato al catalogo radice “/” ha 0 come i-number , la i-lista contiene terne< i-number , tipo_file , indice_blocco >, e i cataloghi contengono coppie < i-number , nome_file >.

Si svolgano i punti seguenti:

1) Si indichi il contenuto delle variabili seguenti all’istante di tempo T1:

bufR2: ES ___________________ bufR3: ITALIA ______________ bufR4: NO _________________

e si indichi il contenuto delle variabili seguenti all’istante di tempo T2, subito prima della funzione exit :

bufP1: FRA _______________ bufQ1: ING ______________ bufQ2: E _______________

2) Si completi il contenuto delle tabelle seguenti, indicando la sequenza di valori assunti fino all’istante T2 (si scriva L oppure NE per indicare che una cella si è liberata oppure non esiste più, rispettivamente):

tabella dei filedel processo P

tabella dei filedel processo Q

tabella dei filedel processo R

tabella globale dei file aperti

filedes

riferimentoa riga

filedes

riferimentoa riga

filedes

riferimentoa riga riga

posizionecorrente

numerodi riferimenti i-number

0

0

0

0

1 1 1 ..... ...... …... …...

2

2

2

14

3 15 3 15 L NE 3 15 L NE 15 0 3 1 2 3 2 1 92

4 4 16 L NE 4 16 L NE 16 0 3 4 6 7 L 1 2 1 L 86 L

5 5 5 17 L NE 17 0 6 8 L 1 2 L 72 L

6 6 6 17 L NE 18

Nota bene i nomi dei campi: file des indica il numero di descrittore di file; riferimento a riga indica il riferimento alla rigadella tabella globale dei file aperti dove si trova il descrittore del file; posizione corrente è l’indicatore di posizionecorrente all’interno del file; numero di riferimenti è il numero di riferimenti da parte dei processi che hanno aperto il file;i-number si riferisce allo i-node del file.

Il segno “

” indica che è presente un valore non significativo ai fini del problema. Le tabelle sono semplificate econtengono solamente le colonne che si chiede di riempire.


19/19

spazio libero per brutta copia o continuazione

AXO - Prova 4 Febbraio 2016 - Con Sol

Documents

Transcript of AXO - Prova 4 Febbraio 2016 - Con Sol