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 – lunedì 14 febbraio 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 lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 2 di 15 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 sun, moon sem_t star int global = 0 void ∗ day (void ∗ arg) { mutex_lock (&sun) sem_post (&star) global = 1 /∗ statement A ∗ / mutex_unlock (&sun) global = 2 mutex_lock (&moon) sem_wait (&star) mutex_unlock (&moon) return (void ∗) 3 } /∗ end day ∗/ void ∗ night (void ∗ arg) { mutex_lock (&sun) sem_wait (&star) mutex_lock (&moon) global = 4 /∗ statement B ∗/ mutex_unlock (&moon) sem_post (&star) global = 5 /∗ statement C ∗/ mutex_unlock (&sun) return NULL } /∗ end night ∗/ void main ( ) { pthread_t th_1, th_2 sem_init (&star, 0, 0) create (&th_2, NULL, night, NULL) create (&th_1, NULL, day, NULL) join (th_1, &global) /∗ statement D ∗ / join (th_2, NULL) return } /∗ end main ∗/ AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 3 di 15 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 – day th_2 – night subito dopo stat. A ESISTE ESISTE subito dopo stat. B ESISTE ESISTE subito dopo stat. C PUÒ ESISTERE ESISTE subito dopo stat. D 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. condizione variabili globali sun moon star global subito dopo stat. A 1 0 1 1 subito dopo stat. B 1 1 0 2 / 4 subito dopo stat. C 1 0 / 1 0 / 1 2 / 3 / 5 subito dopo stat. D 0 / 1 0 0 3 / 5 Il sistema può andare in stallo ( deadlock ), con uno o più thread che si bloccano, in (almeno) tre 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 – day th_2 – night global 1 lock sun wait star 0 2 wait star lock moon 2 3 wait star 2 / 3 AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 4 di 15 esercizio n. 2 – processi e nucleo prima parte – gestione dei processi // programma foo.c int main ( ) { pid1 = fork ( ) // creazione del processo Q if (pid1 == 0) { // codice eseguito da Q write (stdo ut, "proc Q", 6) execl ("/acso/progXY", "progXY", NULL) exit (-1) } else { // codice eseguito da P write (stdout, "Avvio Prog", 10 ) pid2 = fork ( ) // creazione del processo R } /* if */ if (pid2 == 0) { // codice eseguito da R write (stdout, "proc R", 6) execl ("/acso/progXY", "progXY", NULL) exit (-2) } /* if */ pid2 = waitpid (pid2, NULL, 0) // codice eseguito da P pid1 = waitpid (pid2, NULL, 0) } /* main */ // programma progXY.c pthread_mutex_t fence = PTHREAD_MUTEX_INITIALIZER sem_t flag void * routine1 (void * arg) { void * r outine2 (void * arg) { sem_wait (&flag) sem_post (&flag) sem_post (&flag) pthread_mutex_lock (&fence) return NULL sem_wait (&flag) } /* routine1 */ pthread_mutex_unlock (&fence) sem_post (&flag) ret urn NULL } /* routine2 */ // codice eseguito da R int main ( ) { pthread_t TH_1, TH_2 sem_init (&flag, 0, 0) pthread_create (&TH_1, NULL, routine1, NULL) pthread_create (&TH_2, NULL, routine2, NULL) write (stdout, "Fine!" , 5) pthread_join (TH_2, NULL) pthread_join (TH_1, NULL) exit (1) } /* main */ Un processo P esegue il programma foo.c e crea i processi Q e R. Il processo Q esegue una mutazione di codice che non va a buon fine. Il processo R effettua con successo una mutazione di codice ed esegue il programma progXY.c, creando i thread TH_1 e TH_2. Si simuli l’esecuzione dei processi così come risulta dal codice dato, dagli eventi indicati. Si completi la tabella riportando quanto segue: • PID e TGID di ogni processo che viene creato • identificativo del processo-chiamata di sistema / libreria nella prima colonna, dove necessario • in funzione del codice proposto in ciascuna riga, lo stato dei processi al termine del tempo indicato AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 5 di 15 TABELLA DA COMPILARE (numero di colonne non signif icativo) identif icativo simbolico del processo IDLE P Q R TH_1 TH_2 PID 1 2 3 4 5 6 evento oppure processo-chiamata TGID 1 2 3 4 4 4 P – write 1 esec attesa (write) attesa (write) NE NE NE 10 interrupt da stdout 2 pronto attesa (write) ese c NE NE NE Q – execl 3 pronto attesa (write) esec NE NE NE interrupt da RT_clock scadenza QdT (Q resta esec) 4 pronto attesa (write) esec NE NE NE 6 interrupt da stdout (tutti i caratteri trasferiti) 5 pronto esec pronto NE NE NE P – pid2 = fork 6 pronto esec pronto pronto NE NE P – waitpid pid2 7 pronto attesa (wait pid2) esec pronto NE NE Q – exit 8 pronto attesa (wait pid2) NE esec NE NE R – write 9 esec attesa (wait pid2) NE attesa (write) NE NE 6 interrupt da stdout 10 pronto attesa (wait pid2) NE esec NE NE R – execl 11 pronto attesa (wait pid2) NE esec NE NE R – pthread_create TH_1 12 pronto attesa (wait pid2) NE esec pronto NE R – pthread_create TH_2 13 pronto attesa (wait pid2) NE esec pronto pronto R – write 14 pronto attesa (wait pid2) NE attesa (write) esec pronto TH_1 – wait flag 15 pronto attesa (wait pid2) NE attesa (write) attesa (wait) esec TH_2 – post flag 16 pronto attesa (wait pid2) NE attesa (write) esec pronto TH_1 – post flag 17 pronto attesa (wait pid2) NE attesa (write) esec pronto TH_1 – return 18 pronto attesa (wait pid2) NE attesa (write) NE esec TH_2 – lock fence 19 pronto attesa (wait pid2) NE attesa (write) NE esec AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 6 di 15 seconda parte – moduli, pila e strutture dati HW Si consideri il seguente stato di esecuzione: CURR = P Q = WAIT (write) La runqueue contiene un solo task dato dal processo P, mentre il processo Q è in stato di attesa da stdout per la scrittura di 10 caratteri a seguito dell’esecuzione di una write (...) della libreria glibc . Il sistema non contiene altri task. Si consideri questo evento: il processo P è in esecuzione in modo U, e si attivano 10 interruzioni da stdout risvegliando il processo Q; di esse si considera solo l’ultima. La condizione di preemption è verificata . Domanda: • Mostrare le invocazioni di tutti i moduli (ed eventuali relativi ritorni) eseguiti nel contesto del pro- cesso P e del processo Q, per gestire l’evento indicato f ino al ritorno di Q nella write (...) della glibc . • Mostrare (in modo simbolico) l’evoluzione dello stack di sistema del processo P al termine della ge- stione dell’evento considerato (parte dello stack f inale di P è già mostrata). È mostrato per intero lo stack di sistema iniziale del processo Q. invocazione moduli – numero di righe non significativo processo modo modu lo P U – S >R_Int (stdout) P S >wakeup P S >check_preempt_curr P S >resched< P S check_preempt_curr< P S wakeup< P S >schedule P S >pick_next_task< P – Q S schedule: context switch Q S schedule< Q S wait_event< Q S sys_write Q S – U System _Ca ll: SYSRET Q U syscall Q U write sS tack_P finale sStack_Q iniziale USP a schedule da pick_next_task USP a R_Int da schedule a schedule da pick_next_task a check_preempt_curr da resched a wait_event da schedule a wakeup da check_preempt _curr a sys_write da wait_event a R_Int da wakeup a System_Call da sys_write PSR (u) PSR (u) a codice utente da R_Int a syscall da System_Call AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 7 di 15 PAGINA BIANCA DI ALLINEAMENTO – usabile per continuazione o brutta copia AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 8 di 15 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 = 2 situazione iniziale (esistono un processo P, un processo Q e un processo R) PROCESSO: P ********************************************************* VMA : C 000000400, 2 , R , P , M , D 000000600, 4 , W , P , A , P 7FFFFFFFC, 3 , W , P , A , PT: process P - NPV of PC and SP: c0, p1 PROCESSO: Q *****SOLO LE INFORMAZIONI RILEVANTI ********************** process Q - NPV of PC and SP: c0, p0 PROCESSO: R *****SOLO LE INFORMAZIONI RILEVANTI ********************** process R - NPV of PC and SP: c0, p0 ____MEMORIA FISICA____(pagine libere: 3)_________________________ 00 : || 01 : Pc0 / Qc0 / Rc0 / || 02 : Pd2 || 03 : Rp0 D || 04 : ---- || 05 : Pp1 / Rp1 || 06 : Pp0 || 07 : Pd1 || 08 : ---- || 09 : ---- || ____STATO del TLB________________________________________________ Pc0 : 01 - 0: 1: || Pp0 : 06 - 1: 1: || Pd2 : 02 - 1: 0: || Pp1 : 05 - 1: 1: || Pd1 : 07 - 1: 0: || ----- || ----- || ----- || SWAP FILE: Qp0 ,Pd0/Rd0, ----, ----, ----, ----, LRU ACTIVE: PP0, PC0, PP1, LRU INACTIVE: pd2, pd1, rp0, rc0, rp1, qc0, AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 9 di 15 evento 1: read (Pp2) w rite (Pp3) La pagina Pp2 da leggere è di growsdown (non ancora allocata in memoria f isica), pertanto si modif ica la VMA di P (aggiungendo la pagina virtuale Pp3 come growsdown), e si alloca Pp2 in pagina ZP con accesso a R per abilitare COW in successive scritture. La pagina Pp3 da scrivere è di growsdown (non ancora allocata in memoria f isica), pertanto si modif ica la VMA di P (aggiungendo la pagina virtuale Pp4 come growsdown), si genera un COW (in linea di principio da ZP)e deve essere allocata una nuova pagina. Si alloca Pp3 in pagina 4 con accesso a W. Ad ogni caricamento di pagina si modif ica la lista Active (Pp2 e Pp3 in testa). VMA del processo P (è da compilare solo la riga relativa alla VMA P) AREA NPV iniziale dimensione R/W P/S M/A nome f ile offset P 7FFF FFFF A 5 W P A -1 0 PT del processo: P p0 : 6 W p1: 5 R p2: 0 R p3 :4 W p4 : - - process P NPV of PC : c0 NPV of SP : p3 MEMORIA FISICA 00: / Pp2 / Pp3 01: Pc0 / Qc0 / Rc0 02: Pd2 03: Rp0 D 04: Pp3 05: Pp1 / Rp1 06: Pp0 07: Pd1 08 : ----- 09 : ----- SWAP FILE s0: Qp0 s1: Pd 0 / Rd0 s2: s3: s4: s5: LRU ACTIVE : PP3, PP2, PP0, PC0, PP1 _________________________ LRU INACTIVE : pd2, pd1, rp0, rc0, rp1, qc0 ___________________ evento 2: read (Pd0) w rite (Pp1) La lettura di Pd0 genera uno swap_in, ma free = 2 e quindi scatta PFRA che libera la pagina f isica 03 (Rp0) e la 07 (Pd1). Entrambe devono essere salvate nello swap f ile (negli slot s2 e s3) ed eliminate dalla lista Inactive. Pd0 (e Rd0) viene caricata in 03 (e naturalmente resta anche nello swap f ile, dato che non viene modif icata). Si aggiornano le liste (Pd0 in Active, testa, e Rd0 in Inactive, coda). La scrittura di Pp1 causa un COW e deve essere allocata una nuova pagina. Si alloca Pp1 in pagina 07 con accesso a W. La pagina 05 con Rp1 viene marcata D a causa dello stato del TLB di Pp1 precedente a questa scrittura (infatti nel TLB la pagina Rp1 f igurava dirty, quando era ancora condivisa con Pp1). PT del processo: P d0: 3 R d1: s3 W process P NPV of PC : c0 NPV of SP : p1 MEMORIA FISICA 00: / Pp2 01: Pc0 / Qc0 / Rc0 02: Pd2 03: Rp0 Pd0 / Rd0 04: Pp3 05: Rp1 D 06: Pp0 07: Pd1 Pp1 AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 10 di 15 08 : ----- 09 : ----- SWAP FILE s0: Qp0 s1: Pd 0 / Rd0 s2: Rp0 s3: Pd1 s4: s5: LRU ACTIVE : PD0, PP3, PP2, PP0, PC0, PP1 ___________________ LRU INACTIVE : pd2, rc0, rp1, qc0 , rd0 __________________________ AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 11 di 15 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: c2, p0 ____MEMORIA FISICA____(pagine libere: 1)_________________________ 00 : || 01 : Pc2 / Qc2 / || 02 : Qp0 D || 03 : D || 04 : D || 05 : D || 06 : Pp0 || 07 : ---- || ____STATO del TLB________________________________________________ Pc2 : 01 - 0: 1: || Pp0 : 06 - 1: 1: || ----- || ----- || ----- || ----- || processo/i file f_pos f_count numero pag. lette numero pag. scritte P, Q F 90 00 2 3 0 ATTENZIONE : è presente la colonna “processo” in cui 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 fd = 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 memo- ria f isica, delle variabili del FS relative ai f ile aperti e al numero di accessi a disco effettuati in lettura e in scrittura. eventi 1 e 2: context sw itch (Q) close (fd) La pagina 06 con Pp0 viene marcata D a causa del flush (svuotamento) del TLB indotto dal context switch che mette in esecuzione il processo Q (tutte le PTE relative a P nel TLB vengono cancellate). MEMORIA FISICA 00: 01: Pc2 / Qc2 / 02: Qp0 D 03: D 04: D 05: D 06: Pp0 D 07: ---- processo/i file f_pos f_count numero pag. lette numero pag. scritte P F 9000 1 3 0 AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 12 di 15 eventi 3 e 4: context sw itch (P) w rite (fd, 5000) Il context switch modif ica solo il TLB (flush, svuotamento). La write implica l’accesso ai blocchi F2 e F3 del f ile (la posizione 9000 cade nel blocco F2 e la posizione 9000+5000 = 14000 cade nel blocco F3). Il blocco F2 è già in memoria e viene scritto in memoria, mentre il blocco F3 deve prima essere caricato. Si ha minfree = 1 e free = 1, pertanto si attiva PFRA che libera le pagine di page cache 03 e 04, eseguendo anche due scritture su disco (poiché entrambe queste pagine sono marcate D). Poi il blocco F3 viene caricato in pagina f isica 03, e quindi scritto in memoria, dunque questa pagina viene marcata D. Una lettura da disco e due scritture su disco. MEMORIA FISICA 00: 01: Pc2 / Qc2 / 02: Qp0 D 03: D 04: ---- 05: D 06: Pp0 D 07: ---- processo/i file f_pos f_count numero pag. lette numero pag. scritte P F 14000 1 4 2 evento 5: close (fd) Il contatore f_count del file F scende a 0, pertanto vengono scritti su disco i blocchi del f ile F presenti in memoria e marcati D (sono quelli nelle pagine f isiche 03 e 05, ossia F3 e F2). I blocchi in memoria restano li (come pagine di page cache), ma perdono la marcatura D. Due scritture su disco. MEMORIA FISICA 00: 01: Pc2 / Qc2 / 02: Qp0 D 03: 04: ---- 05: 06: Pp0 D 07: ---- processo/i file f_pos f_count numero pag. lette numero pag. scritte - F ----- 0 4 4 AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 13 di 15 esercizio n. 4 – strutture dati del file system La f igura sottostante è una rappresentazione dello stato del VFS raggiunto dopo l’esecuzione in sequenza di un certo numero di chiamate di sistema (non riportate): tabelle file struct file struct dentry struct inode P→ files.fd_array /dir1/file0 0 stdin 1 stdout f_pos = 0 f_count = 2 2 stderr 3 metadati di FILEA Q→ files.fd_array /dir1/file1 0 stdin 1 stdout f_pos = 0 f_count = 2 2 metadati di FILEB 3 /dir1/file2 R→ fi les.fd_array 0 stdin 1 stdout 2 3 Il processo P ha creato il processo f iglio Q, che a sua volta ha creato il processo f iglio R. Ora si supponga di partire dallo stato del VFS mostrato nella f igura iniziale e si risponda alla domanda alla pagina seguente, riportando una possibile sequenza di chiamate di sistema che può avere generato la nuova situazione di VFS mostrata nella f igura successiva. Il numero di eventi è esattamente 7 e questi sono eseguiti, nell’ordine, dai processi indicati. Le sole chiamate di sistema usabili sono: open (nomef ile, …), close (numfd), link (oldf ilename, newf ile- name), read (numfd, numchar). AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 14 di 15 domanda tabelle file struct file struct dentry struct inode P→ files.fd_array /dir1/file0 0 stdin 1 stdout f_pos = 0 f_count = 1 2 stderr 3 metadati di FILEA Q→ files.fd_array /dir1/file1 0 stdin 1 stdout 2 f_pos = 8 f_count = 1 metadati di FILEB 3 /dir1/file2 R→ fi les.fd_array 0 stdin 1 stdout f_pos = 0 f_count = 1 2 3 /dir2/file3 sequenza di chiamate di sistema # processo chiamata di sistema 1 P close (3) 2 P open ( “/dir1/f ile0”, ...) 3 Q close (3) 4 Q link ( “/dir1/f ile2”, “/dir2/f ile3”) 5 R read (2, 8) 6 R close (2) 7 R open ( “/dir2/f ile3”, ...) Nota: gli eventi 3 e 4 sono commutabili, gli eventi 4 e 5 sono commutabili. AXO – prova 2 di lunedì 14 febbraio 2022 – CON SOLUZIONI pagina 15 di 15 spazio libero per brutta copia o continuazione