Computer Engineering - Architettura dei Calcolatori e Sistemi Operativi

Full exam

Politecnico di Milano Dipartimento di Elettronica, Informazione e Bioingegneria prof.ssa Anna Antola prof. Luca Breveglieri prof.ssa Donatella Sciuto prof.ssa Cristina Silvano AXO – Architettura dei Calcolatori e Sistemi Operativi SECONDA PARTE – mercoledì 1 luglio 2020 Cognome ________________________ Nome _______________________ Matricola _____________ Codice Persona ___________________________ Istruzioni – ESAME ONLINE È vietato consultare libri, eserciziari e appunti, nonché cellulari e altri dispositivi mobili di calcolo o comunica- zione. Chiunque non dovesse attenersi alla regola vedrà annullata la propria prova. La prova va sempre consegnata completando la procedura prevista nel modulo (form) dell’esame con INVIO (SUBMIT) del testo risolto. Se lo studente intende RITIRARSI deve inviare messaggio di posta elettronica (email) al docente dopo avere completata la procedura. Dallo HONOR CODE In qualsiasi progetto o compito, gli studenti devono dichiarare onestamente il proprio contributo e devono indicare chiaramente le parti svolte da altri studenti o prese da fonti esterne. Ogni studente garantisce che eseguirà di persona tutte le attività associate all'esame senza alcun aiuto di altri; la sostituzione di identità è un reato perseguibile per legge. Durante un esame, gli studenti non possono accedere a fonti (libri, note, risorse online, ecc) diverse da quel- le esplicitamente consentite. Durante un esame, gli studenti non possono comunicare con nessun altro, né chiedere suggerimenti. In caso di esame a distanza, gli studenti non cercano di violare le regole a causa del controllo limitato che il docente può esercitare. L’accettazione dello Honor Code costituisce prerequisito per l’iscrizione agli esami. Tempo a disposizione 1 h : 30 m Valore indicativo di domande ed esercizi, voti parziali e voto finale: esercizio 1 (4 punti) _________________________ esercizio 2 (6 punti) _________________________ esercizio 3 (6 punti) _________________________ voto finale: (16 punti) ______________________ CON SOLUZIONI (in corsivo) AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 2 di 12 esercizio n. 1 – programmazione concorrente Si consideri il programma C seguente (gli “#include” e le inizializzazioni dei mutex sono omessi, come an- che il pref isso pthread delle primitive di libreria NPTL): pthread_mutex_t here sem_t near, far int global = 0 void ∗ alpha (void ∗ arg) { mutex_lock (&here) sem_wait (&far) mutex_unlock (&here) /∗ statement A ∗ / global = 1 sem_wait (&near) mutex_lock (&here) sem_post (&near) /∗ statement B ∗ / mutex_unlock (&here) return NULL } /∗ end alpha ∗/ void ∗ omega (void ∗ arg) { mutex_lock (&here) sem_post (&far) global = 2 /∗ statement C ∗ / sem_wait (&near) mutex_unlock (&here) /∗ statement D ∗/ sem_wait (&near) return (void ∗) 3 } /∗ end omega ∗/ void main ( ) { pthread_t th_1, th_2 sem_init (&near, 0, 2) sem_init (&far, 0, 0) create (&th_1, NULL, alpha, NULL) create (&th_2, NULL, omega, NULL) join (th_2, &global) /∗ statement E ∗ / join (th_1, NULL) return } /∗ end main ∗/ AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 3 di 12 Si completi la tabella qui sotto indicando lo stato di esistenza del thread nell’istante di tempo specifi- cato da ciascuna condizione, così: se il thread esiste, si scriva ESISTE; se non esiste, si scriva NON ESI- STE; e se può essere esistente o inesistente, si scriva PUÒ ESISTERE. Ogni casella della tabella va riempi- ta 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 assume tra lo statement X e lo statement immediatamente successivo del thread indicato. condizione thread th_1 – alpha th_2 – omega subito dopo stat. A ESISTE PUÒ ESISTERE subito dopo stat. C ESISTE ESISTE subito dopo stat. D PUÒ ESISTERE ESISTE subito dopo stat. E PUÒ ESISTERE NON ESISTE Si completi la tabella qui sotto, indicando i valori delle variabili globali (sempre esistenti) nell’istante di tempo specif icato da ciascuna condizione. Il valore della variabile va indicato così: • intero, carattere, stringa, quando la variabile ha un valore def inito; oppure X quando è indef inita • 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 supponga che il mutex valga 1 se occupato, e valga 0 se libero Si badi bene alla colonna “condizione”: con “subito dopo statement X” si chiede il valore (o i valori) che la variabile ha tra lo statement X e lo statement immediatamente successivo del thread indicato. condizione variabili globali here near far subito dopo stat. A 0 0 / 1 0 subito dopo stat. B 1 0 / 1 0 subito dopo stat. C 1 2 1 subito dopo stat. D 0 / 1 0 / 1 0 / 1 Il sistema può andare in stallo ( deadlock ), con uno o più thread che si bloccano, in (almeno) due 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 e i corrispondenti valori di global : caso th_1 – alpha th_2 – omega global 1 wait far lock here 0 2 wait near 1 / 3 3 AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 4 di 12 esercizio n. 2 – processi e nucleo prima parte – gestione dei processi // programma prova.c main ( ) { pid1 = fork ( ) if (pid1 == 0) { // codice eseguito da Q execl (“/acso/prog_x”, “prog_x”, NULL) exit (-1) } /∗ if ∗/ pid2 = fork ( ) fd = open (“/acso/esame”, ORDWR) // lettura di 2 bloc chi if (pid2 == 0) { // codice eseguito da R write (fd, vett, 4096) // scrive 4 blocchi exit (-2) } else { pid1 = waitpid (pid1, &status, 0) } /∗ if ∗/ exit (0) ` / prova / // programma prog_x.c // dichiarazione e inizializzazione dei mutex presenti nel codice // dichiarazione dei semafori presenti nel codice void soft (void arg ) ^ void hard (void arg ) ^ sem_post (&gas ) mutex_lock (&liquid ) mutex_lock (&liquid ) sem_wait (& gas ) sem_wait (& gas ) mutex_unlock (&liquid ) mutex_unlock (& liquid ) sem_post (&gas ) return NULL return NULL ` // soft ` // hard main ( ) ^ // codice eseguito da Q pthread _t th_1, th_2 sem_init (& gas , 0, 1) create (&th_1, NULL, soft , NULL) nanosleep (6) create (&th_2, NULL, hard , NULL) join (th_ 2, NULL) join (th_1 , NULL) exit (1) ` // main Un processo P esegue il programma prova e crea un processo f iglio Q che esegue una mutazione di codice (programma prog_x ) e un f iglio R. La mutazione di codice va a buon f ine e Q crea i thread th_1 e th_2 . Si simuli l’esecuzione dei processi completando tutte le righe presenti nella tabella così come risulta dal codice dato, dallo stato iniziale e dagli eventi indicati, e nell’ipotesi che th_1 , che esegue soft , abbia già eseguito la mutex_lock ma non ancora la sem_w ait . Si completi la tabella riportando quanto segue: • 〈 PID , TGID 〉 di ciascun processo che viene creato • 〈 identificativo del processo-chiamata di sistema / libreria 〉 nella prima colonna, dove necessario e in funzione del codice proposto • in ciascuna riga lo stato dei processi al termine dell’evento o della chiamata associata alla riga stessa; si noti che la prima riga della tabella potrebbe essere solo parzialmente completata AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 5 di 12 TABELLA DA COMPILARE (numero di colonne non signif icativo) identificativo simbolico del processo IDLE P Q th_1 R th_2 PID 1 2 3 4 5 6 evento oppure processo-chiamata TGID 1 2 3 3 5 3 P –pid2=fork () 0 pronto esec A nanosleep pronto pronto NE P - open 1 pronto A open A nanosleep esec pronto NE th_1 – sem_wait 2 pronto A open A nanosleep esec pronto NE 2 interrupt da DMA_in, tutti i blocchi richiesti da open trasferiti 3 pronto esec A nanosleep pronto pronto NE P – pd1=waitpid 4 pronto A waitpid A nanosleep pronto esec NE R - open 5 pronto A waitpid A nanosleep esec A open NE interrupt da RT_clock e scadenza quanto di tempo 6 pronto A waitpid A nanosleep esec A open NE interrupt da RT_clock e scadenza timer di nanosleep 7 pronto A waitpid esec pronto A open NE Q – create th_2 8 pronto A waitpid esec pronto A open pronto 2 interrupt da DMA_in, tutti i blocchi richiesti da open trasferiti 9 pronto A waitpid pronto pronto esec pronto R - write 10 pronto A waitpid pronto esec A write pronto Th1 - unlock 11 pronto A waitpid pronto esec A write pronto Th1 - return 12 pronto A waitpid pronto NE A write esec AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 6 di 12 seconda parte – scheduler CFS Si consideri uno Scheduler CFS con 2 task caratterizzato da queste condizioni iniziali (da completare): CONDIZIONI INIZIALI (da completare) RUNQUEUE NRT PER RQL CURR VMIN 2 6 2 t1 100 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t1 1 0.5 3 1 10 101.0 RB t2 1 0.5 3 1 30 100.5 Durante l’esecuzione dei task si verif icano i seguenti eventi: Events of task t1: CLONE at 0.5; EXIT at 2.5; Events of task t2: WAIT at 0.5; WAKEUP after 2.5; Simulare l’evoluzione del sistema per 4 eventi riempiendo le seguenti tabelle. Indicare la valutazione delle condizioni di preemption per l’evento di WAKEUP nell’apposito spazio alla f ine dell’esercizio. EVENTO TIME TYPE CONTEXT RESCHED 0.5 CLONE t1 false RUNQUEUE NRT PER RQL CURR VMIN 3 6 3 t1 100.5 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t1 1 0.33 2 1 10.5 101.5 RB t2 1 0.33 2 1 30 100.5 t3 1 0.33 2 1 0 102.5 WAITING EVENTO TIME TYPE CONTEXT RESCHED 2 Q_SCADE t1 true RUNQUEUE NRT PER RQL CURR VMIN 3 6 3 t2 100.5 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t2 1 0.33 2 1 30 100.5 RB t3 1 0.33 2 1 0 102.5 t1 1 0.33 2 1 12 103 WAITING AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 7 di 12 EVENTO TIME TYPE CONTEXT RESCHED 2.5 WAIT t2 true RUNQUEUE NRT PER RQL CURR VMIN 2 6 2 t3 101 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t3 1 0.5 3 1 0 102.5 RB t1 1 0.5 3 1 12 103 WAITING t2 1 30.5 101 EVENTO TIME TYPE CONTEXT RESCHED 5 WUP t3 true RUNQUEUE NRT PER RQL CURR VMIN 3 6 3 t2 103 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t2 1 0.33 2 1 30.5 101 RB t1 1 0.33 2 1 12 103 t3 1 0.33 2 1 2.5 105 WAITING Condizioni di rescheduling a clone del task t1: clone: 102,50+1,00*0,33=102,83 < curr.vrt=101,50?  false Condizioni di rescheduling a wake_up del task t2: wake_up: 101,00+1,00*0,33=101,33 < curr.vrt=105,00?  true AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 8 di 12 esercizio n. 3 – memoria e file system prima parte – gestione dello spazio di memoria È dato un sistema di memoria caratterizzato dai seguenti parametri generali: MAXFREE = 1 MINFREE = 1 Situazione iniziale (esiste un processo P): PROCESSO: P ********************************************************* VMA : C 000000400, 2, R, P, M, M0 000010000, 1, W, S, M, P 7FFFFFFFC, 3, W, P, A, PT: process P - NPV of PC and SP: c1, p0 ____MEMORIA FISICA____(pagine libere: 5)_________________________ 00 : || 01 : Pc1 / || 02 : Pp0 || 03 : ---- || 04 : ---- || 05 : ---- || 06 : ---- || 07 : ---- || ____STATO del TLB________________________________________________ Pc1 : 01 - 0: 1: || Pp0 : 02 - 1: 1: || ----- || ----- || ----- || ----- || ----- || ----- || LRU ACTIVE: PP0, PC1, LRU INACTIVE: evento 1: mmap (0x000030000000, 3, W, P, M, “F”, 2), mmap (0x000040000000, 2, W, P, A, −1, 0) VMA del processo P (compilare solo le righe relative alle nuove VMA create) AREA NPV iniziale dimensione R/W P/S M/A nome f ile offset M1 0000 3000 0 3 W P M F 2 M2 0000 4000 0 2 W P A -1 0 AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 9 di 12 evento 2: read (Pm20, Pm21, Pm11), w rite (Pm20, Pm00) PT del processo: P (completare con pagine di VMA) c0 : - - c1 : 1 R p0 : 2 W p1 : - - p2 : - - m00: 05 W m10: - - m11: 03 R m12: - - m20: 04 W m21: 00 R MEMORIA FISICA 00: Pm21 01: Pc1 / 02: Pp0 03: Pm11 / 04: Pm2 0 05: Pm00 / 06: 07: LRU ACTIVE: PM00, PM11, PM21, PM20, PP0, PC1, _________________________ LRU INACTIVE: _______________________________________________________ evento 3: read (Pc1, Pp0, Pm20), 4 ksw apd LRU ACTIVE: PM20, PP0, PC1, _________________________________________ LRU INACTIVE: pm00, pm11, pm21, _______________________________________ evento 4: w rite (Pm10) PFRA - Required: 1, Free: 1, To Reclaim: 1 viene liberata da page cache la pagina fisica 3 MEMORIA FISICA 00: Pm21 01: Pc1 / 02: Pp0 03: Pm10 04: Pm20 05: Pm00 / 06: 07: LRU ACTIVE: PM10, PM20, PP0, PC1, ____________________________________ LRU INACTIVE: pm00, pm21, _____________________________________________ Indicare la decomposizione dell’indirizzo della prima pagina della VMA M0 nella TP: PGD PUD PMD PT 0 0 128 0 AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 10 di 12 L’indirizzo della pagina è 000010000 in esadecimale, quindi i 36 bit sono: 0000 0000 0000 0000 0001 0000 0000 0000 0000 la suddivisione dei 36 bit in gruppi di 9 bit fornisce il risultato: 0000 0000 0|000 0000 00|01 0000 000|0 0000 0000 AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 11 di 12 seconda parte – file system È dato un sistema di memoria caratterizzato dai seguenti parametri generali: MAXFREE = 3 MINFREE = 2 Si consideri la seguente situazione iniziale: ____MEMORIA FISICA____(pagine libere: 5)_________________________ 00 : || 01 : Pc2 / || 02 : Pp0 || 03 : ---- || 04 : ---- || 05 : ---- || 06 : ---- || 07 : ---- || ____STATO del TLB________________________________________________ Pc2 : 01 - 0: 1: || Pp0 : 02 - 1: 1: || ----- || ----- || Per ognuno dei seguenti eventi compilare le Tabelle richieste con i dati relativi al contenuto della memoria f isica, delle variabili del FS relative al f ile F e al numero di accessi a disco effettuati in lettura e in scrittura. È in esecuzione il processo P. ATTENZIONE: il numero di pagine lette o scritte di un f ile è cumulativo, quindi è la somma delle pagine lette o scritte su quel f ile da tutti gli eventi precedenti oltre a quello considerato. eventi 1 e 2: fd = open (“F”), w rite (fd, 10000) MEMORIA FISICA 00: 01: Pc2 / 02: Pp0 03: D 04: D 05: D 06: ---- 07: ---- f_pos f_count numero pagine lette numero pagine scritte file F 10000 1 3 0 eventi 3 e 4: fork (“Q” ), context sw itch (“Q”) Qp0 deve essere allocata. 2 pagine libere e quindi interviene PFRA che libera NPF 3 e NPF 4. Pp0 allocata in 3 e per il context switch (vedi TLB) diventa D MEMORIA FISICA 00: 01: Pc2 / Qc2 / 02: Qp0 D 03: Pp0 D 04: ---- 05: D 06: ---- 07: ---- f_pos f_count numero pagine lette numero pagine scritte file F 10000 2 3 2 AXO – prova 2 di mercoledì 1 luglio 2020 – CON SOLUZIONI pagina 12 di 12 evento 5: w rite (fd, 2000) f_pos f_count numero pagine lette numero pagine scritte file F 12000 2 3 2 eventi 6 e 7: close (fd), context sw itch (“P”) f_pos f_count numero pagine lette numero pagine scritte file F 12000 1 3 2 evento 8: w rite (fd, 16000) Devono essere accedute le pagine del file F3, F4, F5 e F6. Caricamento di F3 in NPF 04 e scrittura. Caricamento di F4: 2 pagine libere, PFRA libera NPF 4 e NPF 5. Caricata F4 in 4 e quindi F5 in 5. Caricamento di F6: 2 pagine libere, PFRA libera NPF 4 e NPF 5. Caricata F6 in 4. MEMORIA FISICA 00: 01: Pc2 / Qc2 / 02: Qp0 D 03: Pp0 D 04: D 05: ---- 06: ---- 07: ---- f_pos f_count numero pagine lette numero pagine scritte file F 28000 1 7 6 evento 9: close (fd) f_pos f_count numero pagine lette numero pagine scritte file F ---- 0 7 7