Computer Engineering - Architettura dei Calcolatori e Sistemi Operativi

Second partial 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 – giovedì 20 febbraio 2020 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 (6 punti) _________________________ esercizio 4 (1 punti) _________________________ voto finale: (16 punti) ______________________ CON SOLUZIONI (in corsivo) AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 2 di 17 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 solid, liquid sem_t gas int global = 0 void ∗ soft (void ∗ arg) { mutex_lock (&solid) sem_wait (&gas) mutex_unlock (&solid) /∗ statement A ∗/ global = 1 mutex_lock (&liquid) sem_post (&gas) /∗ statement B ∗/ mutex_unlock (&liquid) return NULL } /∗ end soft ∗/ void ∗ hard (void ∗ arg) { mutex_lock (&liquid) sem_post (&gas) global = 2 /∗ statement C ∗/ sem_wait (&gas) mutex_unlock (&liquid) mutex_lock (&solid) sem_post (&gas) mutex_unlock (&solid) /∗ statement D ∗/ return NULL } /∗ end hard ∗/ void main ( ) { pthread_t th_1, th_2 sem_init (&gas, 0, 0) create (&th_1, NULL, soft, NULL) create (&th_2, NULL, hard, NULL) join (th_1, NULL) /∗ statement E ∗/ join (th_2, NULL) return } /∗ end main ∗/ AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 3 di 17 Si completi la tabella qui sotto indicando lo stato di esistenza del thread nell’istante di tempo specif i- 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. thread condizione th_1 – soft th_2 – hard subito dopo stat. A ESISTE PUÒ ESISTERE subito dopo stat. C ESISTE ESISTE subito dopo stat. D PUÒ ESISTERE ESISTE subito dopo stat. E NON ESISTE 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. variabili globali condizione solid liquid gas subito dopo stat. A 0 0 / 1 0 subito dopo stat. B 0 1 1 subito dopo stat. C 0 / 1 1 0 / 1 subito dopo stat. E 0 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 – soft th_2 – hard global 1 wait gas lock solid 2 2 lock liquid wait gas 1 / 2 3  L’unico modo di evitare deadlock è che TH2 esegua i due mutex prima di TH1. AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 4 di 17 esercizio n. 2 – processi e nucleo prima parte – gestione dei processi // programma prova.c main ( ) { pid1 = fork ( ) // P crea Q if (pid1 == 0) { // codice eseguito da Q execl (“/acso/prog_x”, “prog_x”, NULL) exit (-1) } else { // codice eseguito da P read (stdin, msg, 5) pid = wait (&status) } // end_if pid1 exit (0) } // prova // programma prog_x.c // dichiarazione e inizializzazione dei mutex presenti nel codice // dichiarazione dei semafori presenti nel codice void ∗ me (void ∗ arg) { void ∗ you (void ∗ arg) { sem_post (&busy) nanosleep (2) mutex_lock (&lonely) mutex_lock (&lonely) sem_wait (&busy) sem_wait (&busy) mutex_unlock (&lonely) mutex_unlock (&lonely) return NULL sem_post (&busy) } // me return NULL } // you main ( ) { // codice eseguito da Q pthread_t th_1, th_2 sem_init (&busy, 0, 0) create (&th_1, NULL, me, NULL) create (&th_2, NULL, you, NULL) pid = fork ( ) // Q crea R if (pid == 0) { // codice eseguito da R read (stdin, msg, 24) exit (-1) } else { // codice eseguito da Q join (th_2, NULL) join (th_1, NULL) } // if pid 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 ). La mutazione di codice va a buon f ine e Q crea i thread th_1 e th_2 , e un processo f iglio R. 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. 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 giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 5 di 17 TABELLA DA COMPILARE (numero di colonne non signif icativo) identificativo simbolico del processo IDLE P Q th_1 th_2 R PID 1 2 3 4 5 6 evento oppure processo-chiamata TGID 1 2 3 3 3 6 Q –create th_2 (*) th_1 è pronto già da tempo 0 pronto A read da stdinesec pronto (*) pronto NE interrupt da RT_clock e scadenza quanto di tempo 1 pronto A read pronto esec pronto NE th_1 – post 2 pronto A read pronto esec pronto NE 5 interrupt da std_in, tutti i 5 caratteri richiesti trasferiti 3 pronto esec pronto pronto pronto NE P – wait 4 pronto A wait pronto pronto esec NE th_2 – nanosleep 5 pronto A wait esec pronto A nanoslee p NE Q – fork 6 pronto A wait esec pronto A nanosleep pronto Q – join th_2 7 pronto A wait A join th2 esec A nanosleep pronto interrupt da RT_clock e scadenza quanto di tempo 8 pronto A wait A join pronto A nanosleep esec R – read 9 pronto A wait A join esec A nanoslee p A read th_1 lock 10 pronto A wait A join esec A nanosleep A read interrupt da RT_clock e scadenza timeout 11 pronto A wait A join pronto esec A read th_2 lock 12 pronto A wait A join esec A lock A read AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 6 di 17 seconda parte – moduli, pila e strutture dati HW Si consideri un processo P in esecuzione in modo U della funzione main. La f igura sotto riportata e i valori nella tabella successiva descrivono compiutamente, ai f ini dell’esercizio, il contesto di P. Un processo Q è in attesa di un evento. I processi P e Q sono gli unici di interesse nel sistema Si assuma che i valori della situazione iniziale di interesse siano i seguenti: processo P PC X // è all’interno di main SP Y SSP Z USP W descrittore di P.stato PRONTO RUNQUEUE CURR P RB.LFT NULL Si consideri la seguente serie di eventi. AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 7 di 17 evento A&B A. Durante l’esecuzione del codice utente si verif ica Interrupt_1 che manda in esecuzione la routine di risposta all’interrupt R_int_1. B. Durante l’esecuzione della routine di risposta R_int_1 si verif ica Interrupt_2 che viene accettato e manda in esecuzione la routine di risposta all’interrupt R_int_2. Completare le tabelle seguenti con i valori assunti dagli elementi subito dopo il verif icarsi di evento A&B. processo P sPila di P PC // non di interesse SP Z – 4 SSP Z PSR (S) USP W a R_int_1 da R_int_2 descrittore di P.stato PRONTO PSR (U) a codice utente da R_int_1 RUNQUEUE CURR P RB.LFT NULL evento C La routine di risposta all’interrupt R_int_2 risveglia il processo Q che viene portato in stato di pronto. Il processo Q ha maggiori diritti di esecuzione di P. Completare le tabelle seguenti con i valori assunti dagli elementi subito dopo l’esecuzione dell’istruzione IRET che termina la routine di risposta all’interrupt R_int_2. processo P sPila di P PC // non di interesse SP Z – 2 SSP Z USP W descrittore di P.stato PRONTO PSR (U) a codice utente da R_int_1 RUNQUEUE CURR P RB.LFT Q AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 8 di 17 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 = 3 MINFREE = 1  situazione iniziale (esistono un processo P e un processo Q) PROCESSO: P ********************************************************* VMA : C 000000400, 1 , 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: c0, p1 PROCESSO: Q ***** non di interesse per l’esercizio ****************** ____MEMORIA FISICA____(pagine libere: 3)_________________________ 00 : || 01 : Pc0 / Qc0 / || 02 : Pp0 / Qp0 || 03 : ---- || 04 : Ps0 / Qs0 || 05 : Pd0 / Qd0 || 06 : Qp1 D || 07 : Pp1 || 08 : ---- || 09 : ---- || ____STATO del TLB________________________________________________ Pc0 : 01 - 0: 1: || Pp0 : 02 - 1: 0: || Ps0 : 04 - 1: 0: || Pd0 : 05 - 1: 0: || Pp1 : 07 - 1: 1: || ----- || ----- || ----- || SWAP FILE: ----, ----, ----, ----, ----, ----, LRU ACTIVE: PC0, PP1, LRU INACTIVE: pp0, pd0, ps0, qp1, qd0, qs0, qp0, qc0, evento 1: write (Pp2, Pp3) la pagina Pp2 è di growsdown, quindi modifica di VMA P e poi allocazione in 03. La  pagina Pp3 è di growsdown, quindi modifica di VMA P e poi allocazione in 08. Le liste  LRU sono aggiornate di conseguenza.  PT del processo: P p0: 2 R p1: 7 W p2: 3 W p3: 8 W p4: - - MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Pp0 / Qp0 03: Pp2 04: Ps0 / Qs0 05: Pd0 / Qd0 06: Qp1 D 07: Pp1 08: Pp3 09: LRU ACTIVE: PP3, PP2, PC0, PP1,___________________________________ AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 9 di 17 LRU INACTIVE: pp0, pd0, ps0, qp1, qd0, qs0, qp0, qc0,_____________ AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 10 di 17 evento 2: mmap (0x000050000000, 3, W, S, M, “F”, 2) evento 3: write (Pp4) La pagina Pp4 è di growsdown, quindi modifica di VMA P . Free = 1, quindi la  scrittura di Pp4 causa PFRA che libera le pagine 06 (Qp1 in swapfile), 04 (Ps0 / Qs0 in  swapfile), 05 (Pd0 / Qd0 in swapfile). Poi carica Pp4 in 04. e aggiornamento LRU list.  VMA del processo P AREA NPV iniziale dimensione R/W P/S M/A nome f ile offset M 0000 5000 0 3 W S M F 2 P 7FFF FFFF 9 6 W P A -1 0 PT del processo: P s0: s1 R s1: d0: s2 R d1: p0: 2 R p1: 7 W p2: 3 W p3: 8 W p4: 4 W p5: - - m00: - - m01: - - m02: - - process P – NPV of PC and SP: c0, p4 MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Pp0 / Qp0 03: Pp2 04: Pp4 05: 06: 07: Pp1 08: Pp3 09: SWAP FILE s0: Qp1 s1: Ps0 / Qs0 s2: Pd0 / Qd0 s3: s4: s5: LRU ACTIVE: PP4, PP3, PP2, PC0, PP1,_____________________________ LRU INACTIVE: pp0, qp0, qc0,________________________________________ evento 4: write (Pm01) Pagina Pm01 allocata in 05. PT del processo: P m00: - - m01: 5 W m02: - - MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Pp0 / Qp0 03: Pp2 04: Pp4 05: Pm01 / AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 11 di 17 06: 07: Pp1 08: Pp3 09: AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 12 di 17 seconda parte – file system È dato un sistema di memoria caratterizzato dai seguenti parametri generali: MAXFREE = 2 MINFREE = 1  Si consideri la seguente situazione iniziale:  process P - NPV of PC and SP: c0, p0 process Q - NPV of PC and SP: c0, p1 __MEMORIA FISICA____(pagine libere: 1)____________________________ 00 : || 01 : Pc0 / Qc0 / || 02 : Pp0 / Qp0 || 03 : Qp1 D || 04 : Pp1 || 05 : || 06 : D || 07 : ---- || processo file f_pos f_count numero pag. lette numero pag. scritte P F 6500 1 2 0 ATTENZIONE : è presente la colonna “processo” in cui va specificato il nome del processo a cui si riferiscono le informazioni “f_pos” e “f_count” (campi di struct file) relative al file indicato 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. Si ricorda che close scrive le pagine dirty di un f ile solo se f_count diventa = 0. È in esecuzione il processo P. Per ciascuno degli eventi seguenti, 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. eventi 1 e 2: write (fd1, 5500), read (fd1, 4000) PFRA ‐ Required: 1, Free: 1, To Reclaim: 2. P libera le pagine fisiche 5  e 6 (dirty) e scrive su disco la 6, poi legge da disco la pagina 2 di F  e la carica nella pagina fisica 5,e cambia la posizione corrente.  P legge da disco la pagina 3 di  F e la carica nella pagina fisica 6,e  cambia la posizione corrente.  MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Pp0 / Qp0 03: Qp1 D 04: Pp1 05: D 06: 07: processo file f_pos f_count numero pag. lette numero pag. scritte P F 16000 1 4 1 AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 13 di 17 evento 3: context_switch (“Q”) NOTA BENE : la pagina p0 di P (condivisa con Q) e la pagina p1 di P risultano marcate dirty nel TLB, che non è mostrato Svuotamento del TLB, le pagine di pila p0 (condivisa con Q) e p1 di P  vengono marcate dirty nella PT e nei descrittori di pagina fisica.   MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Pp0 / Qp0 D 03: Qp1 D 04: Pp1 D 05: D 06: 07: eventi 4 e 5: fd2 = open (“F”), lseek (fd2, 13000) Q apre il file F, creando una nuova riga nella tabella globale dei file  aperti, diversa da quella di P, poi cambia la posizione corrente.   processo file f_pos f_count numero pag. lette numero pag. scritte P F 16000 1 Q F 13000 1 4 1 evento 6: write (fd2, 100) Q scrive in memoria la pagina 3 di F e cambia la posizione corrente.   MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Pp0 / Qp0 D 03: Qp1 D 04: Pp1 D 05: D 06: D 07: processo file f_pos f_count numero pag. lette numero pag. scritte P F 16000 1 Q F 13100 1 4 1 evento 7: close (fd2) Poiché f_count nella riga di F per Q scende a zero, Q scrive su disco le  pagine (dirty) 2 e 3 di F. f_count = 0 e f_pos non significativo.   MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Pp0 / Qp0 D 03: Qp1 D AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 14 di 17 04: Pp1 D 05: 06: 07: processo file f_pos f_count numero pag. lette numero pag. scritte P F 16000 1 Q F ---- 0 4 3 AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 15 di 17 esercizio n. 4 – 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 dover modif icare la dimensione della TP 6. il rapporto relativo VMA del processo P AREA NPV iniziale dimensione R/W P/S M/A nome f ile offset C 0000 0040 0 1 R P M X 0 K 0000 0060 0 1 R P M X 3 S 0000 0060 1 4 W P M X 4 D 0000 0060 5 256 W P A -1 0 M1 0000 3000 0 3 W P M F 2 P 7FFF FFFF A 5 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 5 0 0 3 5  M1 0000 3000 0 0 0 384 0  P 7FFF FFFF A 255 511 511 506  2. Numero di pagine necessarie # pag PGD: 1 # pag PUD: 2 # pag PMD: 2 # pag PT: 4 # pag totali: 9 3. Numero di pagine virtuali occupate dal processo: 270 4. Rapporto di occupazione: 9/270 = 1/30 = 0.033 = 3,3 % 5. Dimensione massima del processo in pagine virtuali: Con la stessa dimensione di TP il processo può crescere f ino a 4 x 512 = 2048 pagine virtuali 6. Rapporto di occupazione con dimensione massima: 9 / 2048 = 0,0044 (circa 4.4 millesimi) AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 16 di 17 spazio libero per brutta copia o continuazione AXO – prova 2 di giovedì 20 febbraio 2020 – CON SOLUZIONI pagina 17 di 17 spazio libero per brutta copia o continuazione