Palestra L12: preparazione per l’esercitazione T12

Codice e soluzioni esercizi di programmazione

Esercizio 1 (selection sort)

Tradurre in IA32 la seguente funzione C selection_sort definita in E1-selection-sort/e1.c che, dato un array di short v e la sua lunghezza n, ordina l’array usando l’algoritmo di ordinamento per selezione. La funzione richiama un’altra funzione swap già fornita in E1-selection-sort/e1_main.c.

e1.c

void selection_sort(short *v, int n) {
    int i,j, min;
    for (i=0; i<n-1; ++i) {
        min = i;
        for (j=i+1; j<n; ++j)
            if (v[j]<v[min]) min = j;
        swap(v+i, v+min);
    }
}

Scrivere la soluzione nel file E1-selection-sort/e1.s. Usare il file E1-selection-sort/e1_eq.c per sviluppare la versione C equivalente e E1-selection-sort/e1_main.c come programma di prova.

Esercizio 2 (misurazione tempo processi)

Scrivere nel file E2-multi-proc/e2.c una funzione proc_gettime che prende come parametri il pathname di un eseguibile file, un puntatore a una funzione callback get_arg fornita dall’utente, un puntatore a dei dati data da fornire alla funzione callback, e un numero di ripetizioni n. La funzione proc_gettime esegue file per n volte, misurando il tempo in secondi (double) richiesto dall’esecuzione e restituisce la media dei tempi richiesti sulle n esecuzioni. Ad ogni esecuzione, la funzione chiama la callback per ottenere gli argomenti argv da passare al processo in modo da rendere possibile comportamenti diversi del processo ad ogni ripetizione. La callback deve ricevere il puntatore data preso come parametro da proc_gettime e il numero della ripetizione i con i compreso tra 0 e n-1.

double proc_gettime(const char* file, char** (*get_argv)(int i, void* data), void *data, int n);

Suggerimento: usare clock_gettime per misurare il tempo.

Compilare il programma con make ed eseguirlo con ./e2.

Esercizio 3 (misurazione tempo accessi a disco)

Si vuole scrivere una funzione che misura il tempo medio in millisecondi per accesso a disco in lettura e scrittura in modo casuale e in modo sequenziale. La funzione, che deve essere scritta in E3-files/e3.c, ha il seguente prototipo:

e3.c

void file_access_time(const char* file, unsigned trials, time_rec_t *t)

dove file è il file da accedere (sovrascrivendolo), trials è il numero di accessi casuali da effettuare sia per le letture che per le scritture, e t è una struttura definita come segue in E3-files/e3.h:

e3.h

typedef struct {
    unsigned file_size;
    double seq_read_t;
    double seq_write_t;
    double rnd_read_t;
    double rnd_write_t;
} time_rec_t;

I campi della struttura vanno interpretati come segue:

1. file_size è la dimensione in byte del file
2. seq_read_t è il tempo medio in millisecondi per lettura sequenziale di 4 byte
3. seq_write_t è il tempo medio in millisecondi per scrittura sequenziale di 4 byte
4. rnd_read_t è il tempo medio in millisecondi per lettura casuale di 4 byte
5. rnd_write_t è il tempo medio in millisecondi per scrittura casuale di 4 byte

Tutti i campi della struttura devono essere riempiti dalla funzione file_access_time. Le letture e le scritture sequenziali devono scorrere l’intero file. I valori che vengono scritti nel file non sono rilevanti e possono essere arbitrari. L’eseguibile può essere compilato con make ed eseguito con ./e3 file trials dove file e trials sono definiti come sopra. E’ possibile generare un file di prova di file.dat da 390 MB con make file. Per ripulire la directory alla fine dell’esperimento usare make clean.

Esercizio 4 (domande)

Domanda 1 (processi)

Una sola delle seguenti affermazioni sui processi è falsa. Quale?

1. Un processo è nello stato waiting se è in attesa di un evento come la terminazione di un’operazione di I/O
2. Un processo è nello stato zombie se è terminato, ma il genitore non ha ancora effettuato una wait per recuperarne lo stato di terminazione
3. Un processo è nello stato ready se non è in esecuzione solo perché tutti i core della CPU sono impegnati ad eseguire altri processi
4. Un processo è nello stato running se sta correntemente impegnando un core della CPU
5. I sistemi operativi reali hanno un numero maggiore di stati per descrivere situazioni come ready in modalità supervisore (ad esempio se avviene preemption mentre un processo sta eseguendo una system call)
6. Nessuna delle precedenti

Domanda 2 (memorie cache)

Si consideri la seguente sequenza di indirizzi acceduti da un processo: 980, 408, 984, 612, 410, 412, 500. Quali blocchi verrebbero a trovarsi alla fine della sequenza in una piccola cache completamente associativa con 3 linee da 32 byte ciascuna e politica di rimpiazzo LRU? (l’ordine degli indici di blocco non conta)

1. 30, 12, 19
2. 15, 12, 19
3. 15, 19, 20
4. 15, 30, 19
5. 12, 30, 15
6. Nessuna delle precedenti

Domanda 3 (pipelining)

Si consideri la seguente sequenza di istruzioni:

movl $12, %eax
addl %ecx, %edx
movl %eax, %ebx

Quanti cicli di clock vengono richiesti da una semplice pipeline a 5 stadi (Fetch, Decode, Execute, Memory, Write-Back) per completare tutte le istruzioni assumendo che gli hazard vengano risolti con stalli?

1. 0
2. 5
3. 9
4. 7
5. 3
6. 11

Domanda 4 (memoria virtuale)

Si consideri un sistema di memoria virtuale con pagine da 2 KB e spazio logico a 24 bit. Quanti byte occuperebbe la tabella delle pagine assumendo di avere indici dei frame a 32 bit?

1. 65536 byte
2. 32768 byte
3. 262144 byte
4. 16384 byte
5. 131072 byte
6. Nessuna delle precedenti

Domanda 5 (allineamento e padding)

Si consideri la seguente struct C:

struct A {
    char a;
    double b;
    char c;
    double d;
    char e;
};

Come riordineresti la struttura per minimizzarne la dimensione assumendo che il compilatore inserisca padding per garantire l’allineamento dei campi e quale dimensione otterresti?

1. char, char, char, double, double => 19 byte
2. char, double, double, char, char => 32 byte
3. char, char, char, double, double => 24 byte
4. char, char, double, char, double => 32 byte
5. char, char, double, char, double => 24 byte
6. Nessuna delle precedenti

Domanda 6 (memory layout)

Si consideri il seguente frammento di programma:

int x;
int main(int argc, char** argv) {
    int* p = malloc(10*sizeof(int));
    char* s1 = "hello";
    char s2[] = "hello";
    ...
    return 0;
}

Il un moderno sistema Linux, una sola fra le seguenti affermazioni è corretta. Quale?

1. x denota un oggetto allocato in bss, p denota un oggetto allocato in heap, s1 denota un oggetto allocato in rodata e *s2 denota un oggetto allocato in data.
2. x denota un oggetto allocato in bss, *p denota un oggetto allocato in heap, *s1 denota un oggetto allocato in rodata e *s2 denota un oggetto allocato in stack.
3. x denota un oggetto allocato in data, p denota un oggetto allocato in stack, s1 denota un oggetto allocato in stack e *s2 denota un oggetto allocato in heap.
4. argc denota un oggetto allocato in stack, *argv denota un oggetto allocato in heap
5. p denota un oggetto allocato in stack, argv denota un oggetto allocato in stack, **argv denota un oggetto allocato in heap
6. Nessuna delle precedenti

Domanda 7 (schedulazione dei processi)

Una sola fra le seguenti affermazioni è falsa. Quale?

1. La schedulazione dei processi serve a selezionare un processo in stato ready per metterlo in esecuzione
2. In un sistema multiprogrammato time-sharing come Linux, la schedulazione avviene contestualmente a un context switch innescato dallo scadere di una time slice
3. Uno degli algoritmi di schedulazione più usati è il Round-Robin, che assegna la CPU (un core) a un processo alla volta, a rotazione.
4. Un sistema operativo fa preemption se è il processo che spontaneamente rilascia la CPU per consentire allo scheduler di mandare in esecuzione un altro processo
5. Lo scadere di una time slice viene segnalata al sistema da un interrupt generato da un timer
6. Nessuna delle precedenti

Domanda 8 (manipolazioni numeriche)

Si consideri il seguente frammento di programma C:

int x = 0xDEADBEEF & ...

Cosa bisogna inserire al posto di ... affinché x prenda il valore 0xD0A0?

1. (252645135 << 16)
2. (4042322160 >> 16)
3. (3735928559 >> 8)
4. (256736178 | 0xFF)
5. (3462378762 >> 16)
6. Nessuna delle precedenti

Domanda 9 (Ottimizzazioni dei programmi)

Si consideri questo frammento di programma:

int f(int x) { 
    return 2*x; 
}

int g() {
    return f(10) + 5;
}

e la sua versione ottimizzata:

int f(int x) { 
    return 2*x; 
}

int g() {
    return 25;
}

Quali ottimizzazioni sono state applicate? Una sola delle seguenti risposta è corretta.

1. common subexpression elimination + constant folding
2. function inlining + dead code elimination
3. loop-invariant code motion + constant folding
4. register allocation + constant folding
5. function inlining + constant folding
6. Nessuna delle precedenti

Domanda 10 (interrupt)

Una sola delle seguenti affermazioni è falsa, quale?

1. Un’interruzione hardware alla CPU può essere generata da un dispositivo esterno per segnalare l’occorrenza di un evento come la pressione di un tasto sulla tastiera, il click del mouse, o il completamento di un’operazione di I/O
2. E’ possibile avere interruzioni software, chiamate trap, generate da un programma, ad esempio eseguendo l’istruzione IA32 int
3. Le interruzioni possono essere sia recuperabili che non recuperabili
4. Le interruzioni possono essere sia sincrone che asincrone
5. Un’interruzione provoca l’esecuzione di un frammento di codice di gestione del sistema operativo puntato dal vettore delle interruzioni (interrupt vector) indicizzato dal numero dell’interruzione
6. Nessuna delle precedenti

Domanda 11 (ottimizzazioni)

Che speedup otterremmo per un programma dimezzando il tempo di esecuzione di una sua porzione che richiede il 10% del tempo complessivo?

1. 1.56x
2. 1.32x
3. 1.05x
4. 2.31x
5. 1.15x
6. 1.27x

Domanda 12 (segnali)

Una sola fra le seguenti affermazioni è falsa, quale?

1. I segnali sono un semplice meccanismo di comunicazione fra processi che serve per notificare eventi
2. Un segnale può essere innescato da un’interrupt
3. Alcuni segnali possono essere catturati o ignorati, mentre altri no
4. Ogni segnale ha un gestore di default sul lato del ricevente che può essere ripristinato in ogni momento
5. Diversamente dalle interruzioni, i segnali sono interamente gestiti dal sistema operativo e dal programmatore
6. Un segnale è accompagnato da un puntatore a un dato che può essere comunicato al destinatario insieme al segnale, o NULL se non è necessario inviare alcun dato

Domanda 13 (ottimizzazioni)

Supponiamo di essere in grado di dimezzare il tempo di esecuzione di una porzione di un programma mediante delle ottimizzazioni. Che percentuale del tempo complessivo deve prendere quella porzione per ottenere uno speedup di 1.5x?

1. 0.77777
2. 0.5
3. 0.66667
4. 0.13333
5. 0.22223
6. 0.812

Domanda 14 (memorie cache)

Si consideri una cache associativa a 2 vie con 4 linee da 8 byte ciascuna e politica di rimpiazzo LRU. Potendo scegliere durante un cold miss, selezionare sempre la linea con indice più basso. Data la seguente sequenza di accessi a indirizzi di memoria, qual è il contenuto delle linee di cache alla fine della sequenza: 96, 98, 124, 86, 104, 120, 68, 138?

1. 12, 10, 15, 17
2. 12, 10, 15, 8
3. 17, 10, 15, 8
4. 8, 10, 15, 17
5. 12, 10, 15, 11
6. 10, 12, 13, 15

Domanda 15 (allocazione dinamica della memoria)

Si consideri un semplice allocatore di memoria malloc/free dove, potendo scegliere, la malloc riusa il blocco libero con l’indirizzo più basso. Assumere per semplicità che non vi sia alcuna header e che i blocchi allocati vengano arrotondati a una dimensione multiplo di 4 byte. Qual è il contenuto dell’heap alla fine della seguente sequenza di operazioni (dove X denota 4 byte allocati e . denota 4 byte liberi)?

p1=malloc(2)
p2=malloc(10)
p3=malloc(4)
free(p1)
p4=malloc(4)
p5=malloc(8)
free(p4)
free(p3)
p6=malloc(6)

1. X | XXX | . | XX
2. XX | XXX | . | XX
3. . | XXX | . | XX | XX
4. XXX | . | XX | . | XX
5. XX | . | XXX | . | XX
6. .. | . | XXX | . | XX

Domanda 16 (memoria virtuale)

Una sola fra le seguenti affermazioni è vera. Quale?

1. Un sistema di memoria paginato soffre di frammentazione esterna
2. La memoria virtuale è delegata a tenere traccia dei blocchi che vengono allocati con malloc e free
3. La memoria virtuale consente di evitare che un processo possa accedere allo spazio di indirizzi di un altro processo
4. La memoria virtuale è un ingrediente indispensabile in qualsiasi sistema di calcolo moderno
5. La dimensione di una pagina deve essere multiplo della dimensione di un frame
6. E’ possibile gestire uno spazio di indirizzi logico a 64 bit con una singola tabella delle pagine

Domanda 17 (spazio utente e spazio kernel)

Una sola fra le seguenti affermazioni è vera. Quale?

1. Una chiamata a strlen finisce per invocare una system call
2. Una chiamata a printf finisce per invocare una system call
3. In un ambiente Linux/IA32, una chiamata a write richiama una porzione di codice che gira in spazio utente che a sua volta invoca l’istruzione int $80
4. La libreria C (libc) è indispensabile per ottenere un eseguibile Linux usando gcc
5. La funzione main è la prima ad essere invocata all’avvio di un processo.
6. Nessuna delle precedenti

Domanda 18 (context switch)

Una sola fra le seguenti affermazioni sul context switch è falsa. Quale?

1. Un context switch avviene in situazioni di flusso del controllo eccezionale
2. Durante un context switch un’attività viene interrotta per passare ad un’altra
3. Durante un context switch viene salvato il contesto di esecuzione in modo da potere eventualmente riprendere in seguito un’attività interrotta.
4. Si ha un context switch quando un processo in un sistema operativo con time sharing viene interrotto per schedulare un altro processo.
5. Il PCB associato a un processo viene utilizzato per memorizzarne lo stato durante un context switch in modo da poterlo ripristinare in seguito
6. I context switch non hanno alcun impatto sulle prestazioni

Domanda 19 (scala degli eventi di un sistema di calcolo)

Approssimativamente, ignorando il parallelismo introdotto dalla pipeline della CPU, quante istruzioni macchina che coinvolgono solo registri potrebbero essere eseguite nel tempo richiesto da un’istruzione che accede a una DRAM?

1. 1
2. 10
3. 100
4. 1000
5. 10000
6. 100000

Domanda 20 (gerarchie di memoria)

Una sola fra le seguenti affermazione sulle gerarchie di memoria è vera. Quale? Per livelli più alti si intende quelli più vicini alla CPU.

1. I livelli più bassi hanno il costo maggiore per byte.
2. I livelli più alti hanno i tempi di accesso più bassi.
3. I livelli più bassi hanno la capienza minore.
4. Il trasferimento di dati tra livelli consecutivi avviene alla granularità del byte.
5. I vari livelli includono solo memorie SRAM e DRAM.
6. L’efficacia della gerarchia di memoria è indipendente dal livello di località che viene esposto da un programma.

Domanda 21 (potenze di due)

Si considerino le seguenti grandezze, nell’ordine: 1TB, 2KB, 8MB, 4GB, 16PB. A quali potenze di due corrispondono?

1. 2^42, 2^10, 2^24, 2^31, 2^54
2. 2^50, 2^12, 2^22, 2^42, 2^34
3. 2^50, 2^11, 2^23, 2^32, 2^44
4. 2^40, 2^11, 2^23, 2^32, 2^54
5. 2^39, 2^12, 2^22, 2^31, 2^53
6. Nessuna delle precedenti

Domanda 22 (paginazione)

Si consideri un sistema di memoria virtuale con uno spazio di indirizzi a 16 bit, pagine da 4 KB, e la seguente tabella delle pagine: {0x1, 0x6, 0xB, 0x3, 0xA, 0x7, 0xC, 0x5, 0x9, 0x2, 0xD, 0xF, 0x0, 0x4, 0xE, 0x8 }. A quali indirizzi fisici corrispondono i seguenti indirizzi logici: 0xF1D6, 0x4F02, 0x6000?

1. 0x90C1, 0xAF02, 0xE12B
2. 0xAFD4, 0xD071, 0xD011
3. 0x81D6, 0xAF02, 0xC000
4. 0xA0D1, 0xFF00, 0x9117
5. 0x10CE, 0x1E94, 0xA7D9
6. Nessuna delle precedenti

Domanda 23 (paginazione e manipolazioni numeriche)

Dato un’indirizzo x a 32 bit, come definiresti il numero di pagina p(x) e l’offset o(x) assumendo pagine di 8 KB?

1. p(x) = x / 2^13, o(x) = x & 0xFFFF
2. p(x) = x >> 13, o(x) = x & 0x1FFF
3. p(x) = x / 13, o(x) = x & 0xFFF
4. p(x) = x >> 2/13, o(x) = x & 0x8FF
5. p(x) = x >> 13, o(x) = x & 0x18FF
6. Nessuno dei precedenti

Domanda 24 (IA32)

Assumendo che il registro eax contenga inizialmente il valore 0xDEADBEEF, quale sarebbe il suo contenuto dopo l’esecuzione dell’istruzione movsbw %al, %ax?

1. 0xDEADFFEF
2. 0xFFFFFFEF
3. 0x0000FFEF
4. 0xDEAD00EF
5. 0xFFFF00EF
6. Nessuna delle precedenti

Domanda 25 (processi)

Si consideri il seguente frammento di programma che si origina da un singolo processo:

fork();
fork();
fork();

Quanti processi sono attivi alla fine del frammento?

1. 3
2. 4
3. 6
4. 8
5. 10
6. Nessuno dei precedenti

Domanda 26 (cache)

Una sola delle seguenti affermazioni è falsa. Quale?

1. Scorrere sequenzialmente una lista collegata provoca in generale un numero di cache miss non inferiore che scorrere sequenzialmente un array
2. Assumendo una cache con linee di dimensione L, scorrere sequenzialmente un array di N short genera sizeof(short)*N/L cache miss
3. Scorrere sequenzialmente una lista collegata con N nodi genera nel caso peggiore N cache hit
4. Assumendo una cache con linee di dimensione L, scorrere sequenzialmente un array di N short genera N-sizeof(short)*N/L cache hit
5. Indipendentemente dai vincoli di associatività, scorrere sequenzialmente un array genera lo stesso numero di cache miss
6. Indipendentemente dai vincoli di associatività, scorrere sequenzialmente una lista collegata genera nel caso peggiore lo stesso numero di cache miss

Domanda 27 (interrupt)

Una sola delle seguenti affermazioni è vera. Quale?

1. Un interrupt può essere generato da un’istruzione della forma movl %eax, %ecx
2. L’interrupt vector non può essere modificato in alcun modo da un programma utente
3. L’interrupt vector cambia in genere nel tempo durante l’esecuzione dei processi
4. Un interrupt segnala esclusivamente eventi generati da dispositivi esterni come il completamento di un’operazione di I/O
5. Gli interrupt sono un meccanismo che altera il normale flusso del controllo dei programmi con un tempismo generalmente prevedibile
6. Nessuna delle precedenti

Domanda 28 (variabili di ambiente)

Una sola delle seguenti affermazioni è falsa. Quale?

1. Una variabile d’ambiente è caratterizzata da una coppia di stringhe della forma (NOME, VALORE)
2. E’ possibile passare le variabili d’ambiente a un programma eseguibile al momento del suo lancio mediante le system call execve o execvpe
3. Il comando env permette di elencare le variabili di ambiente correntemente definite nella shell
4. Un programma lanciato da una shell può aggiungere all’ambiente della shell stessa nuove variabili mediante la chiamata setenv
5. La variabile d’ambiente PATH contiene i percorsi delle directory dove vengono cercati i programmi eseguibili i cui nomi sono digitati sulla shell o invocati con execvp.
6. Un programma può accedere alle variabili d’ambiente che gli vengono passate dal processo genitore mediante un terzo parametro del main.

Domanda 29 (permessi)

Che permessi dovrebbe avere un file per essere accessibile in lettura e scrittura dall’utente proprietario, in sola lettura dal gruppo proprietario, e nessun permesso per tutti gli altri utenti?

1. 0750
2. 0530
3. 0642
4. 0641
5. 0640
6. Nessuno dei precedenti

Domanda 30 (memoria virtuale)

Una sola delle seguenti affermazione è vera. Quale?

1. Due processi possono condividere un gruppo di pagine in modo che gli spazi logici degli indirizzi abbiano un’intersezione comune
2. La tabella delle pagine di un processo è accessibile dal processo stesso nel proprio spazio utente (spazio logico degli indirizzi)
3. Le entry di una tabella delle pagine contengono gli indirizzi fisici del primo byte dei frame
4. La dimensione tipica di una pagina di un sistema Linux è di 64 byte
5. Due processi A e B possono condividere dei frame fisici impostando opportunamente le rispettive tabelle delle pagine con il tramite del sistema operativo. Questo consente ad A di scrivere nel proprio spazio logico degli indirizzi in modo che B veda le modifiche effettuate accedendo al proprio, generalmente a un indirizzo logico diverso rispetto ad A.
6. Nessuna delle precedenti

Domanda 31 (ottimizzazioni)

Di quanto bisognerebbe velocizzare una funzione f che consuma il 10% del tempo di esecuzione di un programma P in modo da ottenere uno speedup complessivo per P pari a 2x?

1. 20x
2. 50x
3. 100x
4. 1000x
5. 10000x
6. E’ impossibile

Risposte alle domande

Le risposte sono state commentate e discusse a lezione.

Domanda 1 (processi)

1. Nessuna delle precedenti

Domanda 2 (memorie cache)

Indirizzi:              980, 408, 984, 612, 410, 412, 500
Blocchi (indirizzo/12): 30,  12,  30,  19,  12,  12,  15
Cache: (tra parentesi il tempo dall'ultimo accesso a un blocco in cache)
        0       1       2
30 -> | 30(0) |       |       | (cold miss)
12 -> | 30(1) | 12(0) |       | (cold miss)
30 -> | 30(0) | 12(1) |       | (hit)
19 -> ! 30(1) ! 12(2) ! 19(0) ! (cold miss)
12 -> ! 30(2) ! 12(0) ! 19(1) ! (hit)
12 -> ! 30(3) ! 12(0) ! 19(2) ! (hit)
15 -> ! 15(0) ! 12(1) ! 19(3) ! (capacity miss, rimpiazzo LRU)

Domanda 3 (pipelining)

movl $12, %eax   F D E M W
addl %ecx, %edx    F D E M W
stallo               * * * * *
stallo                 * * * * *
movl %eax, %ebx          F D E M W
                 |<-  9 cicli  ->|

Domanda 4 (memoria virtuale)

2 KB = 2^11 byte per pagina
24-11=13 => 2^13 pagine
32 bit per frame = 4 byte => 2^2*2^13 = 2^15 byte = 32768 byte

Domanda 5 (allineamento e padding)

1. char, char, char, double, double => 24 byte

Domanda 6 (memory layout)

1. x denota un oggetto allocato in bss, *p denota un oggetto allocato in heap, *s1 denota un oggetto allocato in rodata e *s2 denota un oggetto allocato in stack.

Domanda 7 (schedulazione dei processi)

1. Un sistema operativo fa preemption se è il processo che spontaneamente rilascia la CPU per consentire allo scheduler di mandare in esecuzione un altro processo

Domanda 8 (manipolazioni numeriche)

1. Nessuna delle precedenti

Domanda 9 ottimizzazioni dei programmi)

1. function inlining + constant folding

Domanda 10 (interrupt)

1. Nessuna delle precedenti

Domanda 11 (ottimizzazioni)

1. Applichiamo la legge di Amdahl con k=2 (dimezzato il tempo di esecuzione => speedup 2x sulla porzione ottimizzata) e a=0.1 (10%): speedup = 1/(a/k+1-a)=1/(0.1/2+1-0.1)=1.05x.

Domanda 12 (segnali)

1. Un segnale è accompagnato da un puntatore a un dato che può essere comunicato al destinatario insieme al segnale, o NULL se non è necessario inviare alcun dato

Domanda 13 (ottimizzazioni)

Partiamo dalla legge di Amdahl: speedup = 1/(a/k+1-a). Vogliamo ottenere il valore di a tale che speedup = 1.5:

a/k-a = 1/speedup-1
a*(1/k-1) = 1/speedup-1
a=(1/speedup-1)/(1/k-1)
a=(1/1.5-1)/(1/2-1)=0.66667

Domanda 14 (memorie cache)

Si noti che una in una cache associativa a 2 vie con 4 linee i blocchi di indice pari si mappano sulle linee 0, 1, mentre i blocchi con indice dispari si mappano sulle linee 2, 3.

Indirizzi:             96, 98, 124, 86, 104, 120, 68, 138
Blocchi (indirizzo/8): 12, 12, 15,  10, 13,  15,  08, 17
Cache: (tra parentesi il tempo dall'ultimo accesso a un blocco in cache)
        0       1       2       3
12 -> | 12(0) |       |       |       | (cold miss)
12 -> | 12(0) |       |       |       | (hit)
15 -> | 12(1) |       | 15(0) |       | (cold miss)
10 -> | 12(2) | 10(0) | 15(1) |       | (cold miss)
13 -> | 12(3) | 10(1) | 15(2) | 13(0) | (cold miss)
15 -> | 12(4) | 10(2) | 15(0) | 13(1) | (hit)
08 -> | 08(0) | 10(3) | 15(1) | 13(2) | (capacity miss)
17 -> | 08(1) | 10(4) | 15(3) | 17(0) | (capacity miss)

Domanda 15 (allocazione dinamica della memoria)

____________________
p1=malloc(2)
X
p1
____________________
p2=malloc(10)
X | XXX
p1  p2
____________________
p3=malloc(4)
X | XXX | X
p1  p2    p3
____________________
free(p1)
. | XXX | X
    p2    p3
____________________
p4=malloc(4)
X | XXX | X
p4  p2    p3
____________________
p5=malloc(8)
X | XXX | X  | XX
p4  p2    p3   p5
____________________
free(p4)
. | XXX | X  | XX
    p2    p3   p5
____________________
free(p3)
. | XXX | .  | XX
    p2    p3   p5
____________________
p6=malloc(6)
. | XXX | .  | XX | XX
    p2    p3   p5   p6

Domanda 16 (memoria virtuale)

1. La memoria virtuale consente di evitare che un processo possa accedere allo spazio di indirizzi di un altro processo

Domanda 17 (spazio utente e spazio kernel)

1. Una chiamata a printf finisce per invocare una system call

Domanda 18 (Context switch)

1. I context switch non hanno alcun impatto sulle prestazioni

Domanda 19 (scala degli eventi di un sistema di calcolo)

1. 100

Domanda 20 (gerarchie di memoria)

1. I livelli più alti hanno i tempi di accesso più bassi.

Domanda 21 (potenze di due)

1. 2^40, 2^11, 2^23, 2^32, 2^54

Domanda 22 (paginazione)

1. 0x81D6, 0xAF02, 0xC000

Domanda 23 (paginazione e manipolazioni numeriche)

1. p(x) = x >> 13, o(x) = x & 0x1FFF

Domanda 24 (IA32)

1. 0xDEADFFEF

Domanda 25 (processi)

  |
fork()--------------------+
  |                       |
fork()--------+         fork()--------+
  |           |           |           |
fork()--+   fork()--+   fork()--+   fork()--+
  |     |     |     |     |     |     |     |
  1     2     3     4     5     6     7     8

Domanda 26 (cache)

1. Scorrere sequenzialmente una lista collegata con N nodi genera nel caso peggiore N cache hit

Domanda 27 (interrupt)

1. L’interrupt vector non può essere modificato in alcun modo da un programma utente

Domanda 28 (variabili di ambiente)

1. Un programma lanciato da una shell può aggiungere all’ambiente della shell stessa nuove variabili mediante la chiamata setenv

Domanda 29 (permessi)

1. 0640

Domanda 30 (memoria virtuale)

1. Due processi A e B possono condividere dei frame fisici impostando opportunamente le rispettive tabelle delle pagine con il tramite del sistema operativo. Questo consente ad A di scrivere nel proprio spazio logico degli indirizzi in modo che B veda le modifiche effettuate accedendo al proprio, generalmente a un indirizzo logico diverso rispetto ad A.

Domanda 31 (ottimizzazioni)

1. E’ impossibile