Computer Engineering - Architettura dei Calcolatori e Sistemi Operativi

Full exam

Politecnico di Milano Dipartimento di Elettronica, Informazione e Bioingegneria prof. Luca Breveglieri prof. Gerardo Pelosi prof.ssa Donatella Sciuto prof.ssa Cristina Silvano AXO – Architettura dei Calcolatori e Sistemi Operativi SECONDA PARTE – venerdì 15 luglio 2022 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 della prova. 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 calcolo o comunicazione. Chiunque fosse trovato in possesso di documentazione relativa al corso – anche se non 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 1 h : 30 m Valore indicativo di domande ed esercizi, voti parziali e voto finale: esercizio 1 (4 punti) _________________________ esercizio 2 (5 punti) _________________________ esercizio 3 (5 punti) _________________________ esercizio 4 (2 punti) _________________________ voto finale: (16 punti) ______________________ CON SOLUZIONI (in corsivo) AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 2 di 16 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 funzioni di libreria NPTL): pthread_mutex_t accept, reject sem_t comm int global = 0 void ∗ send (void ∗ arg) { mutex_lock (&accept) sem_post (&comm) global = 1 /∗ statement A ∗ / mutex_unlock (&accept) global = 2 mutex_lock (&reject) sem_wait (&comm) mutex_unlock (&reject) return NULL } /∗ end send ∗/ void ∗ receive (void ∗ arg) { mutex_lock (&accept) global = 3 /∗ statement B ∗/ sem_wait (&comm) mutex_unlock (&accept) sem_wait (&comm) mutex_lock (&reject) sem_post (&comm) global = 4 /∗ statement C ∗/ mutex_unlock (&reject) return NULL } /∗ end receive ∗/ void main ( ) { pthread_t th_1, th_2 sem_init (&comm, 0, 1) create (&th_1, NULL, send, NULL) create (&th_2, NULL, receive, NULL) join (th_1, NULL) /∗ statement D ∗ / join (th_2, NULL) return } /∗ end main ∗/ AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 3 di 16 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 – send th_2 – receive subito dopo stat. A ESISTE PUÒ ESISTERE subito dopo stat. B PUÒ ESISTERE ESISTE subito dopo stat. C ESISTE ESISTE subito dopo stat. D NON E SISTE PUÒ ESISTERE 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 accept rej ect comm subito dopo stat. A 1 0 / 1 0 / 1 / 2 subito dopo stat. B 1 0 / 1 1 / 2 subito dopo stat. C 0 / 1 1 1 subito dopo stat. D 0 / 1 0 0 / 1 Il sistema può andare in stallo ( deadlock ), con uno o più thread che si bloccano, in (almeno) due casi diversi. Si chiede di precisare il comportamento dei thread in due casi, indicando gli statement dove av- vengono i blocchi e i possibili valori della variabile global : caso th_1 – send th_2 – receive global 1 wait comm lock reject 2 / 3 2 - 2a wait comm 2 / 3 3 AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 4 di 16 esercizio n. 2 – processi e nucleo prima parte – gestione dei processi // programma ring_b .c sem_t vuoto , pieno int anello [3] int write_idx = 0, read_idx = 0, cont = 0, out pthread_mutex_t mux = PTHREAD_MUTEX_INITIALIZER void ∗ produttor e (void ∗ arg) { void ∗ consumatore (void ∗ arg) { sem_wait (& vuoto ) sem_wait (& pieno ) mutex_lock (& mux ) mutex_lock ( &mux ) anello [write_idx] = cont out = anello [read_idx] write _idx++ read_idx ++ cont++ mutex_unlock (& mux ) mutex_unlock (& mux ) sem_post (& vuoto ) sem_post (& pieno ) sem_wait (& pieno ) sem_wait (& vuoto ) out = out + anello [read_idx] anello [write_idx] = cont sem_post (& vuoto ) sem_post (& pieno ) return NULL return NULL } // consumatore } // produttore void ∗ help (void ∗ arg) { char msg [ 16 ] = ”Lung. attuale : ” nanosleep (10) for (int i = 0; i < 3; i++) { mutex_lock (&mux) write (stdout, msg, 15 ) printf (”%d”, write_idx - read_idx) mutex_unlock (&mux) } return NULL } // help main ( ) { // codice eseguito da P pthread_t th_1, th_2, th_3 sem_init (& vuoto , 0, 1) sem_init (& pieno , 0, 0) create (&th_ 1, NULL, help , NULL) create (&th_2, NULL, consumatore , NULL) cr eate (&th_ 3, NULL, produttore , NULL) join (th_ 1, NULL) join (th_2, NULL) join (th_ 3, NULL) exit (1) } // main Un processo P crea i tre thread TH_1 , TH_2 e TH_3 . 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 tenendo conto che il processo P non ha ancora creato nessun thread. Si completi la tabella riportando quanto se- gue: • I valori < PID , TGID > di ciascun processo che viene creato. • I valori < identif icativo 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 venerdì 15 luglio 2022 – CON SOLUZIONI pagina 5 di 16 TABELLA DA COMPILARE (numero di colonne non signif icativo) identificativo simbolico del processo IDLE P TH_1 TH_2 TH_3 PID 1 2 3 4 5 evento oppure processo -chiam ata TGID 1 2 2 2 2 P – create TH_1 1 pronto esec pronto NE NE P – create TH_2 2 pronto esec pronto pronto NE interrupt da RT_clock e scadenza del quanto di tempo 3 pronto pronto esec pronto NE TH_1 – nanosleep 4 pronto pronto attesa nanosleep esec NE TH_2 – sem_wait (pieno) 5 pronto esec attesa nanosleep attesa sem_wait NE P – create TH_3 6 pronto esec attesa nanosleep attesa sem_wait pronto P – join TH_1 7 pronto attesa join TH_1 attesa nanosleep attesa sem_wait esec TH_3 – sem_wait (vuoto) 8 pronto attesa join TH_1 attesa nanosleep attesa sem_wait esec TH_3 – mutex_lock (mux) 9 pronto attesa join TH_1 attesa nanosleep attesa sem_wait esec interrupt da RT_clock e scadenza del timer 10 pronto attesa join TH_1 esec attesa sem_wait pronto TH_1 – mutex_lock (mux) 11 pronto attesa join TH_1 attesa lock attesa sem_wait esec TH_3 – mutex_unlock (mux) 12 pronto attesa join TH_1 esec attesa sem_wait pronto TH_1 – write 13 pronto attesa join TH_1 attesa write attesa sem_wait esec TH_3 – sem_post( pieno) 14 pronto attesa join TH_1 attesa write esec pronto TH_2 – sem_wait (pieno) 15 pronto attesa join TH_1 attesa write esec pronto AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 6 di 16 seconda parte – moduli del SO stato iniziale: CURR = P, Q = ATTESA (E) della scadenza di un timer Si consideri il seguente evento: il processo P è in esecuzione in modo U e si verif ica un’interruzione da R_int_clock per scadenza del quanto di tempo, il quale risveglia anche il processo Q. Non ci sono altri processi attivi. domanda • mostrare le invocazioni di tutti i moduli (ed eventuali relativi ritorni) eseguiti nel contesto del processo P per gestire l’evento indicato • mostrare (in modo simbolico) il contenuto della pila di sistema del processo P al termine della gestione dell’evento considerato invocazione moduli processo modo modulo P U – S > R_int _clock P S > task_tick P S > resched < P S task_tick < P S > controlla_timer P S > wakeup_process P S > check_preempt_curr P S > resched < TIF_NEED = 1 P S check_preempt_curr < USP P S wakeup_process < rientro a schedule da pick_next_task P S controlla_timer < rientro a R_int_clock da schedule P S > schedule rientro a check_preempt_curr da resched P S > pick_next_task < rientro a wup_process da check_preempt_curr P – Q S context_switch rientro a timer.function da wakeup_process rientro a R_int_clock da controlla_timer rientro a task_tick da resched rientro a R_int_clock da task_tick PSR (u) rientro a codice utente da R_int_clock AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 7 di 16 PAGINA DI ALLINEAMENTO – spazio libero per brutta copia o continuazione AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 8 di 16 esercizio n. 3 – memoria virtuale e file system prima parte – gestione dello spazio di memoria È dato un sistema di memoria caratterizzato dai seguenti parametri generali: MAXFREE = 3 MINFREE = 2 situazione iniziale (esiste un processo P) processo: P **************************************************** VMA : C 000000400, 2 , R , P , M , K 000000600, 1 , R , P , M , S 000000601, 1 , W , P , M , D 000000602, 3 , W , P , A , P 7FFFFFFFC, 3 , W , P , A , PT: process P - NPV of PC and SP: c0, p1 ____MEMORIA FISICA____(pagine libere: 3)_________________________ 00 : || 01 : Pc0 / || 02 : Pp0 || 03 : Pd0 || 04 : Pd1 || 05 : Pd2 || 06 : Pp1 || 07 : ---- || 08 : ---- || 09 : ---- || SWAP FILE: ----, ----, ----, ----, ----, ---- LRU ACTIVE: PP1, PD2, PC0 LRU INACTIVE: pd1, pd0, pp0 evento 1: read (Pc0) – w rite (Pp1, Pp2, Pd2) – 4 ksw apd Legge pagina Pc0 (in memoria); scrive pagina Pp1 (in memoria), alloca pagina Pp2 (pagina di growsdown) in pagina f isica 7, la scrive (in memoria) e la mette in testa ad active (restano due pagine libere), scrive pagina Pd2 (in memoria), kswapd per riportare pagine libere a tre, scarica in swap pagina pp0 da inactive; aggiorna liste LRU (restano tre pagine libere). PT del processo: P p0 : s0 W p1: 6 W p2: 7 W p3 :- - MEMORIA FISICA 00: 01: Pc 0 / 02: Pp0 03: Pd0 04: Pd1 05: Pd2 06: Pp1 07: Pp2 08: 09: SWAP FILE s0: Pp0 s1: s2: s3: LRU ACTIVE : PP2, PP1, PD2, PC0 ___________________________________ LRU INACTIVE : pd1, pd0 ______________________________________________ AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 9 di 16 evento 2: read (Pc0) – w rite (Pp3) Legge pagina Pc0 (in memoria), alloca pagina Pp3 (pagina di growsdown) in pagina f isica 2 (restano due pagine libere), la scrive (in memoria) e la mette in testa ad active. PT del processo: P p0 : s0 W p1: 6 W p2: 7 W p3 : 2 W p4: - - MEMORIA FISICA 00: 01: Pc0 / 02: Pp3 03 : Pd0 04: Pd1 05: Pd2 06: Pp1 07: Pp2 08: 09: LRU ACTIVE : PP3, PP2, PP1, PD2, PC0 ______________________________ LRU INACTIVE : pd1, pd0 ______________________________________________ eventi 3: fork (Q) – context sw itch (Q) – read (Qc0, Qp3, Qd2) – 4 ksw apd Processo P crea processo f iglio Q, tutte le pagine di P vengono condivise separabilmente con Q e inserite in liste LRU, separa subito pagina di cima pila Pp3, ci sono due pagine libere; invoca PFRA e scarica pagine pd0 / qd0 e pd1 / qd1 da inactive in swap; alloca pagina Pp3 in pagina f isica 3; context switch (svuotamento TLB), marca pagine p1, p2 e d2 condivise dirty in quanto prima scritte da P e dunque dirty nel TLB. Processo Q legge pagine Qc0, Qp3 e Qd2 (in memoria); aggiorna liste LRU (pagine di P vanno in coda inactive); pagine d0, d1 (condivise in swap) e d2 (condivisa in memoria) predisposte per COW (marcate R in PT di Q) (restano 3 pagine libere). PT del processo: Q d0: s1 R d1: s2 R d2: 5 D R MEMORIA FISICA 00: 01: Pc0 / Qc0 02: Pp3Qp3 D 03: Pd0 / Qd0Pp3 D 04: Pd1 / Qd1 05: Pd2 / Qd2 D 06: Pp1 / Qp1 D 07: Pp2 / Qp2 D 08: 09: SWAP FILE s0: Pp0 / Qp0 s1: Pd0 / Qd0 s2: Pd1 / Qd1 s3: LRU ACTIVE : QP3, QD2, QC0 _________________________________________ LRU INACTIVE : qp2, qp1, pp3, pp2, pp1, pd2, pc0 ___________________ evento 4: read (Qc0) – w rite (Qd1) Legge pagina Qc0 (in memoria) e scrive pagina Qd1 (in swap condivisa con Pd1); swap_in di Pd1 / Qd1 in pagina f isica 4, scrive pagina Qd1; COW di Qd1, due pagine libere; invoca PFRA e scarica in swap da inactive pagina pp3 (pag f isica 3 non condivisa) e pagina qp1 (condivisa con pp1 pag f isica 6); alloca pagina Qd1 in pagina f isica 3; rende scrivibile pagina d1 (in PT di Q) (restano tre pagine libere) (Pd1 resta anche in swap in quanto non modif icata). PT del processo: Q d0: s1 R d1: 3 W d2: 5 D R AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 10 di 16 MEMORIA FISICA 00: 01: Pc0 / Qc0 02: Qp3 D 03: Pp3 DQd1 04: Pd1 05: Pd2 / Qd2 D 06: Pp1 / Qp1 D 07: Pp2 / Qp2 D 08: 09: SWAP FILE s0: Pp0 / Qp0 s1: Pd0 / Qd0 s2: Pd1 s3: Pp3 s4: Pp1 / Qp1 s5: AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 11 di 16 seconda parte – file system È dato un sistema di memoria caratterizzato dai seguenti parametri generali: MAXFREE = 3 MINFREE = 1 Si consideri la seguente situazione iniziale. PROCESSO: P *************************************************** VMA : C 000000400, 3 , R , P , M , S 000000600, 2 , W , P , M , D 000000602, 2 , W , P , A , P 7FFFFFFFC, 3 , W , P , A , PT: process P - NPV of PC and SP: c2, p0 ____MEMORIA FISICA____(pagine libere: 3)________________________ 00 : || 01 : Pc0 / || 02 : Pp0 || 03 : Pc1 / || 04 : Pc2 / || 05 : ---- || 06 : ---- || 07 : ---- || ____STATO del TLB_______________________________________________ Pc0 : 01 - 0: 0: || Pp0 : 02 - 1: 1: || Pc1 : 03 - 0: 0: || Pc2 : 04 - 0: 1: || ----- || ----- || SWAP FILE: ----, ----, ----, ---- LRU ACTIVE: PC2, PP0 LRU INACTIVE: pc1, pc0 processo/i file f_pos f_count numero pag. lette numero pag. scritte P F 0 1 0 0 ATTENZIONE : è presente la colonna “processo” dove va specificato il nome/i del/i processo/i a cui si riferiscono le informazioni “f_pos” e “f_count” (campi di struct file) relative al file indi- cato. Il processo P è in esecuzione. Il f ile F è stato aperto da P tramite chiamata fd1 = open (F). ATTENZIONE: il numero di pagine lette o scritte di un f ile è cumulativo, ossia è la somma delle pagine lette o scritte su quel f ile da tutti gli eventi precedenti oltre a quello considerato. Si ricorda inoltre che la primitiva close scrive le pagine dirty di un f ile solo se f_count diventa = 0. Per ciascuno degli eventi seguenti, compilare le tabelle richieste con i dati relativi al contenuto della memoria f isica, delle variabili del FS relative ai f ile aperti e al numero di accessi a disco effettuati in lettura e in scrittu- ra. AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 12 di 16 evento 1: read (fd1, 8000) Bisogna caricare due pagine di f ile F; carica pagina f ile in pagina f isica 5 e pagina f ile in pagina f isica 6; resta una sola pagina libera. Due letture e zero scritture su disco. MEMORIA FISICA 00: 01: Pc0 / 02: Pp0 03: Pc1 / 04: Pc2 / 05: 06: 07: processo/i file f_pos f_count numero pag. lette numero pag. scritte P F 8000 1 2 0 evento 2: read (fd1, 1000) Legge una pagina di f ile F; carica pagina f ile ; c’è una sola pagina libera, invoca PFRA per liberare tre pagine; libera pagine di page cache e senza scaricarle su disco (non sono dirty), e libera pagina di processo pc0 da inactive (non scarica in swap perché è pagina di codice); carica pagina f ile < F, 2 > da disco in pagina f isica 1; aggiorna lista inactive (toglie pagina pc0); aggiorna posizione di f ile F. Tre letture e zero scritture su disco. MEMORIA FISICA 00: 01: Pc0 / 02: Pp0 03: Pc1 / 04: Pc2 / 05: 06: 07: processo/i file f_pos f_count numero pag. lette numero pag. scritte P F 9000 1 3 0 LRU ACTIVE : PC2, PP0, _____________________________________________ LRU INACTIVE : pc1, ___________________________________________________ eventi 3: fork (Q) – context sw itch (Q) Processo P crea processo f iglio Q; condivide tutte pagine (di processo) separabilmente tra P e Q; separa pagina di pila p0 (cima di pila corrente); pagina Qp0 resta in pagina f isica 2 e pagina Pp0 viene allocata in pagina f isica libera 5; restano due pagine libere; context-switch; TLB svuotato e riempito con PTE di Qc2 e Qp0 (codice corrente e cima pila), vedi anche TLB iniziale; pagina codice corrente e cima pila di Q sono c2 e p0 (come P). MEMORIA FISICA 00: 01: 02: Pp0Qp0 03: Pc1 / Qc1 04: Pc2 / Qc2 05: Pp0 D 06: 07: process o Q NPV of PC : c2 NPV of SP : p0 TLB AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 13 di 16 NPV NPF D A NPV NPF D A Qc2 : 04 - 0: 1: Qp0 : 02 - 1: 1: ----- ----- AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 14 di 16 eventi 4: fd2 = open (G) – w rite (fd2, 4000) Processo Q apre f ile G e scrive una pagina di G; carica pagina di f ile in pagina libera 6, marcata dirty (viene scritta); aggiorna posizioni e count di f ile F e G (F è condiviso tra P e Q). Tre letture s zero scritture su disco per F, e una lettura e zero scritture su disco per G. MEMORIA FISICA 00: 01: 02: Qp0 03: Pc1 / Qc1 04: Pc2 / Qc2 05: Pp0 D 06: F 07: processo/i file f_pos f_count numero pag. lette numer o pag. scritte PQ F 9000 2 3 0 Q G 4000 1 1 0 eventi 5: context sw itch (P) � w rite (fd1, 4000) Context switch; processo P scrive in pagina di f ile ; una pagina libera; invoca PFRA per liberare tre pagine; libera pagine di page cache (fis 1) e (f is 6); scarica pagina f ile di G su disco (è dirty); libera anche pagina di processo qc1 (f is 3) da inactive (pc1 era in inactive dove era stata condivisa separabilmente con qc1) senza scaricarla in swap (pagina di codice); aggiorna posizione di f ile F; carica pagina f ile in pagina f isica 1, marcandola dirty (viene scritta). Quattro letture e zero scritture su disco per F, e una lettura e una scrittura su disco per G. MEMORIA FISICA 00: 01: > D 02: Qp0 03: Pc1 / Qc1 04: Pc2 / Qc2 05: Pp0 D 06: D 07: processo/i file f_pos f_count numero pag. lette numero pag. scritte PQ F 13000 2 4 0 Q G 4000 1 1 1 AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 15 di 16 esercizio n. 4 – domande su argomenti vari tabella delle pagine Date le VMA di un processo P sotto riportate, def inire: 1. la decomposizione degli indirizzi virtuali dell’NPV iniziale di ogni area secondo la notazione PGD : PUD : PMD : PT 2. il numero di pagine necessarie in ogni livello della gerarchia e il numero totale di pagine necessarie a rappresentare la Tabella delle Pagine (TP) del processo 3. il numero di pagine virtuali occupate dal processo 4. il rapporto tra l’occupazione della TP e la dimensione virtuale del processo in pagine 5. la dimensione virtuale massima del processo in pagine, senza dovere modif icare la dimensione della TP VMA del processo P AREA NPV iniziale dimensione R/W P/S M/A nome f ile offset C 0000 0040 0 3 R P M F 0 K 0000 0060 0 1 R P M F 3 S 0000 0060 1 5 W P M F 4 D 0000 0060 6 256 W P A -1 0 M1 0000 1000 0 1 W P M G 4 T0 7FFF F77F E 2 W P A -1 0 P 7FFF FFFF 5 10 W P A -1 0 1. Decomposizione degli indirizzi virtuali PGD : PUD : PMD : PT C 0000 0040 0 0 0 2 0 K 0000 0060 0 0 0 3 0 S 0000 0060 1 0 0 3 1 D 0000 0060 6 0 0 3 6 M1 0000 1000 0 0 0 128 0 T0 7FFF F77F E 255 511 443 510 P 7FFF FFFF 5 255 511 511 501 2. Numero di pagine necessarie # pag PGD: 1 # pag PUD: 2 # pag PMD: 2 # pag PT: 5 # pag totali: 10 3. Numero di pagine virtuali occupate dal processo: 278 4. Rapporto di occupazione: 10/278 = 0.035 = 3,5 % 5. Dimensione massima del processo in pagine virtuali: Con la stessa dimensione di TP il processo può crescere f ino a 5 x 512 = 2560 pagine virtuali AXO – prova 2 di venerdì 15 luglio 2022 – CON SOLUZIONI pagina 16 di 16 spazio libero per brutta copia o continuazione