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. Roberto Negrini prof. Giuseppe Pelagatti prof.ssa Donatella Sciuto prof.ssa Cristina Silvano AXO – Architettura dei Calcolatori e Sistemi Operativi SECONDA PARTE di 7 luglio 2017 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 (6 punti) _________________________ esercizio 3 (6 punti) _________________________ voto finale: (16 punti) ______________________ CON SOLUZIONI (in corsivo) AXO – SECONDA PARTE di 7 luglio 2017 – 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): pthread_mutex_t particle sem_t force int global = 0 void ∗ plus (void ∗ arg) { sem_wait (&force) sem_post (&force) /∗ statement A ∗/ pthread_mutex_lock (&particle) sem_post (&force) /∗ statement B ∗/ pthread_mutex_unlock (&particle) return 1 } /∗ end plus ∗/ void ∗ minus (void ∗ arg) { global = 2 /∗ statement C ∗/ pthread_mutex_lock (&particle) sem_wait (&force) pthread_mutex_unlock (&particle) return NULL } /∗ end minus ∗/ void main ( ) { pthread_t th_1, th_2, th_3 sem_init (&force, 0, 1) pthread_create (&th_1, NULL, plus, NULL) pthread_create (&th_2, NULL, minus, NULL) pthread_join (th_2, NULL) pthread_create (&th_3, NULL, minus, NULL) pthread_join (th_1, &global) /∗ statement D ∗/ pthread_join (th_3, NULL) return } /∗ end main ∗/ AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 3 di 12 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 – plus th_2 – minus th_3 – minus subito dopo stat. A ESISTE PUÒ ESISTERE PUÒ ESISTERE subito dopo stat. C in th_2 PUÒ ESISTERE ESISTE NON 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’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) • una variabile mutex assume valore 0 per mutex libero e valore 1 per mutex occupato 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 particle force global subito dopo stat. A 0 / 1 0 / 1 0 / 2 subito dopo stat. B 1 1 / 2 0 / 2 subito dopo stat. C in th_3 0 / 1 0 / 1 1 / 2 Il sistema può andare in stallo ( deadlock ), con uno o più thread che si bloccano, in due casi diversi (con deadlock si intende anche un blocco dovuto a un solo thread che non potrà mai proseguire). Si indichi- no gli statement dove avvengono i blocchi e il valore (o i valori) della variabile global : caso th_1 – plus th_2 – minus th_3 – minus 1 wait terminato wait 2 lock terminato wait AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 4 di 12 esercizio n. 2 – gestione dei processi prima parte – stati dei processi // programma prova.c main ( ) { pid1 = fork ( ) if (pid1 == 0) { // codice eseguito dal figlio Q execl ( “/acso/prog_x”, “prog_x”, NULL) exit (-1) } else { // codice eseguito dal padre P write (fd, vet, 5) // scrittura di 1 blocco su file precedentemente aperto pid1 = waitpid (pid1, ...) exit (0) } // if } // prova // programma prog_X.c int num pthread_mutex_t DOOR= PTHREAD_MUTEX_INITIALIZER sem_t CHECK void ∗ UNO (void ∗ arg) { void ∗ DUE (void ∗ arg) { sem_wait (&CHECK) if (num > 0) { pthread_mutex_lock (&DOOR) pthread_mutex_lock (&DOOR) sem_wait (&CHECK) sem_post (&CHECK) pthread_mutex_unlock (&DOOR) pthread_mutex_unlock (&DOOR) return NULL } else { } // UNO sem_post (&CHECK) } return NULL } // DUE main ( ) { // codice eseguito da Q pthread_t TH_1, TH_2 sem_init (&CHECK, 0, 0) // viene letto da standard input il valore di num pthread_create (&TH_1, NULL, UNO, NULL) pthread_create (&TH_2, NULL, DUE, NULL) pthread_join (TH_2, NULL) pthread_join (TH_1, NULL) exit (1) } // main Un processo P esegue il programma prova creando il figlio Q, che esegue una mutazione di codice che va a buon fine. Nel codice mutato prog_X, Q crea i thread TH_1 e TH_2 . Si ipotizzi che il valore di num letto da Q sia maggiore di 0. Si simuli l’esecuzione dei processi (fino a udt = 160) così come risulta dal codice dato, dagli eventi indicati e facendo bene attenzione allo stato iniziale considerato per la simulazione. 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 del tempo indicato; si noti che la prima riga della tabella potrebbe essere solo parzialmente completata AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 5 di 12 TABELLA DA COMPILARE (numero di colonne non signif icativo) identificativo simbolico del processo IDLE P Q TH_1 TH_2 PID 1 2 3 4 5 evento/processo-chiamata TGID 1 2 3 3 3 0 Pronto ESEC NON ESISTE Non esiste Non esiste P – fork 10 Pronto ESEC Pronto Non esiste Non esiste P – write 20 Pronto Attesa (write) ESEC Non esiste Non esiste Q - execl 30 Pronto Attesa (write) ESEC Non esiste Non esiste interrupt da RT _clock, scadenza quanto di tempo 40 Pronto Attesa (write) ESEC Non esiste Non esiste 1 interrupt da DMA_in (operazione write completata) 50 Pronto ESEC Pronto Non esiste Non esiste interrupt da RT _clock, scadenza quanto di tempo 60 Pronto Pronto ESEC Non esiste Non esiste Q – create TH_1 70 Pronto Pronto ESEC Pronto Non esiste interrupt da RT _clock, scadenza quanto di tempo 80 Pronto ESEC Pronto Pronto Non esiste P – waitpid 90 Pronto Attesa (waitpid) Pronto ESEC Non esiste TH_1 – sem_wait 100 Pronto Attesa (waitpid) ESEC Attesa (sem_wait) Non esiste Q – create TH_2 110 Pronto Attesa (waitpid) ESEC Attesa (sem_wait) Pronto Q – join TH_2 120 Pronto Attesa (waitpid) Attesa (join) Attesa (sem_wait) ESEC TH_2 – lock 130 Pronto Attesa (waitpid) Attesa (join) Attesa (sem_wait) ESEC TH_2 – sem_post 140 Pronto Attesa (waitpid) Attesa (join) ESEC Pronto TH_1 – lock 150 Pronto Attesa (waitpid) Attesa (join) Attesa (lock) ESEC TH_2 – unlock 160 Pronto Attesa (waitpid) Attesa (join) ESEC Pronto AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 6 di 12 seconda parte – scheduling dei processi Si consideri uno Scheduler CFS con 3 task caratterizzato da queste condizioni iniziali (da completare): CONDIZIONI INIZIALI (da completare) NRT PER RQL CURR VMIN RUNQUEUE 3 6 4,00 t1 100 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t1 1 0,25 1,5 1,00 10 100,00 t2 1 0,25 1,5 1,00 30 100,50 RB t3 2 0,5 3,0 0,50 20 101,00 Durante l’esecuzione dei task si verif icano i seguenti eventi: Events of task t1: EXIT at 1.0; Events of task t2: WAIT at 0.5; WAKEUP after 2.5; Events of task t3: CLONE at 2.0 Simulare l’evoluzione del sistema per 4 eventi riempiendo le seguenti tabelle (per scrivere le eventuali condizioni di preemption, si usi lo spazio tra le tabelle degli eventi): TIME TYPE CONTEXT RESCHED EVENTO 1.00 EXIT t1 true NRT PER RQL CURR VMIN RUNQUEUE 2 6 3 t2 100,5 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t2 1 0.33 2 1 30 100.5 t3 2 0.67 4 0.5 20 101.0 RB WAITING TIME TYPE CONTEXT RESCHED EVENTO 1.50 WAIT t2 true NRT PER RQL CURR VMIN RUNQUEUE 1 6 2 t3 101.0 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t3 2 1 6 0.5 20 101.0 RB t2 1 30.5 101.0 WAITING AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 7 di 12 TIME TYPE CONTEXT RESCHED EVENTO 3.5 CLONE t3 false NRT PER RQL CURR VMIN RUNQUEUE 2 6 4 t3 102 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t3 2 0.5 3 0.5 22 102 t4 2 0.5 3 0.5 0 103.5 RB t2 1 30.5 101.0 WAITING tnew.vrt+WGR*tnew.LC=103,50+1,00*0,50=104,00 < curr.vrt=102,00 TIME TYPE CONTEXT RESCHED EVENTO 4.0 W_UP t3 true NRT PER RQL CURR VMIN RUNQUEUE 3 6 5 t2 102.25 TASK ID LOAD LC Q VRTC SUM VRT CURRENT t2 1 0,2 1.2 1.0 30.5 101.00 t3 2 0.4 2.4 0.5 22.5 102.25 RB t4 2 0.4 2.4 0,5 0 103.5 WAITING tw.vrt+WGR*tw.LC=101,00+1,00*0,20=101,20 < curr.vrt=102,25 AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 8 di 12 esercizio n. 3 – gestione della memoria prima parte – gestione dello spazio virtuale È dato un sistema di memoria caratterizzato dai seguenti parametri generali: MAXFREE = 3, MINFREE = 2. Si consideri la seguente situazione iniziale: 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, p0 ____MEMORIA FISICA____(pagine libere: 3)_________________________ 00 : || 01 : Pc0 / || 02 : Pp0 || 03 : Pp1 || 04 : ---- || 05 : Pd0 || 06 : ---- || 07 : ---- || ____STATO del TLB________________________________________________ Pc0 : 01 - 0: 1: || Pp0 : 02 - 1: 1: || ----- || Pd0 : 05 - 1: 0: || Pp1 : 03 - 1: 0: || ----- || SWAP FILE: Ps0, ----, ----, ----, ----, ---- LRU ACTIVE: PP0, PC0 LRU INACTIVE: pp1, pd0 Si rappresenti l’effetto dei seguenti eventi consecutivi sulle strutture dati della memoria compilando esclusi- vamente le tabelle fornite per ciascun evento (l’assenza di una tabella signif ica che non è richiesta la compi- lazione della corrispondente struttura dati). ATTENZIONE: le Tabelle sono PARZIALI – riempire solamente le celle indicate evento 1: fork (Q) PT del processo: P C0: 1 R S0: s0 R D0: 5 R P0: 4 W P1: 3 R PT del processo: Q C0: 1 R S0: s0 R D0: 5 R P0: 2 D W P1: 3 R MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Qp0 D 03: Pp1 / Qp1 04: Pp0 05: Pd0 / Qd0 06: 07: TLB NPV NPF D A NPV NPF D A Pc0: 1 0 1Pp0: 4 1 1 AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 9 di 12 SWAP FILE s0: Ps0 / Qs0 s1: s2: s3: Active: QP0, QC0, PP0, PC0 _______________________________ Inactive: qp1, qd0, pp1, pd0 __________________________ evento 2: write (Pd0) PT del processo: P C0: 1 R S0: s0 R D0: 3 W P0: 4 W P1: s2 R MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Qp0 D 03: Pd0 04: Pp0 05: 06: 07: TLB NPV NPF D A NPV NPF D A Pc0: 1 0 1 Pp0: 4 1 1 SWAP FILE s0: Ps0 / Qs0 s1: Qd0 s2: Qp1 / Pp1 s3: Active: PD0,QP0,QC0,PP0,PC0 _______________________________ Inactive: __________________________ evento 3: indicare il contenuto delle liste LRU dopo ognuna delle seguenti invocazioni consecutive di kswapd a) Read (pc0), 1 kswapd Active: PD0, PP0, PC0, qp0, qc0 ________________________________ Inactive: __________________________ b) Read (pc0), 1 kswapd Active: PC0, pd0, pp0 ________________________________ Inactive: QP0, QC0 __________________________ c) Read (pc0), 1 kswapd Active: PC0 ________________________________ Inactive: PD0,PP0,qp0,qc0 __________________________ AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 10 di 12 d) Read (pc0, pp0), 1 kswapd Active: PC0, pp0 ________________________________ Inactive: pd0, qp0, qc0 __________________________ seconda parte – gestione del file system È dato un sistema di memoria caratterizzato dai seguenti parametri generali: MAXFREE = 3 MINFREE = 1  Si consideri la seguente situazione iniziale:  ____MEMORIA FISICA____(pagine libere: 4)_________________________ 00 : || 01 : Pc0 / Qc0 / || 02 : Qp0 D || 03 : Pp0 || 04 : ---- || 05 : ---- || 06 : ---- || 07 : ---- || 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. È sempre 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); fd1 = open (G) f_pos f_count numero pagine lette numero pagine scritte file F 0 1 file G 0 1 evento 3 – write (fd, 11000) MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Qp0 D 03: Pp0 04: D 05: D 06: D 07: ---- f_pos f_count numero pagine lette numero pagine scritte file F 11000 1 3 0 AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 11 di 12 evento 4 – write (fd1, 6000) MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Qp0 D 03: Pp0 04: D 05: D 06: 07: ---- f_pos f_count numero pagine lette numero pagine scritte file F 11000 1 3 3 file G 6000 1 2 0 eventi 5 e 6 – lseek (fd, −4000); write (fd, 100) MEMORIA FISICA 00: 01: Pc0 / Qc0 / 02: Qp0 D 03: Pp0 04: D 05: D 06: D 07: ---- f_pos f_count numero pagine lette numero pagine scritte file F 7100 1 4 3 eventi 7 e 8 – close (fd); close (fd1) f_pos f_count numero pagine lette numero pagine scritte file F 4 4 file G 2 2 AXO – SECONDA PARTE di 7 luglio 2017 – CON SOLUZIONI pagina 12 di 12 spazio libero per brutta copia o continuazione