Sistemi di Calcolo

Corso di Laurea in Ingegneria Informatica e Automatica

Home | Avvisi | Diario Lezioni | Esercitazioni | Esami | Materiale Didattico | Valutazioni Studenti | Lezioni di Camil Demetrescu |

[T10] Esercitazione del 17 maggio 2019

Istruzioni per l’esercitazione:

Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.

Esercizio 1 (prefisso di stringa)

Tradurre in IA32 la seguente funzione is_prefix definita in E1-is-prefix/e1.c che, date due stringhe s1 e s2, verifica se la s1 è un prefisso di s2. Ad esempio ham è prefisso di hamburger, mentre hum non lo è.

e1.c

int is_prefix(const char* s1, const char* s2){
    while (*s1 && *s1++ == *s2++);
    return *s1 == 0;
}

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

Esercizio 2 (un semplice allocatore di memoria)

L’obiettivo dell’esercizio è implementare l’operazione di deallocazione di un semplice allocatore di memoria. L’operazione mymalloc è fornita e si richiede di scrivere l’operazione myfree nel file E2-free/e2.c. L’operazione deve prendere il blocco deallocato e inserirlo in testa alla lista di blocchi liberi puntata dalla variabile globale free_list come descritto nella dispensa del corso. I blocchi liberi dell’allocatore hanno una header di 4 byte che contiene la dimensione del blocco, seguita da un campo next come definito nel file e2.h:

e2.h (estratto)

#pragma pack(1)
typedef struct header_t {
    unsigned size;
    struct header_t* next;
} header_t;

Si ricorda che la direttiva del compilatore #pragma pack(1) evita l’inserimento di padding tra il campo size e il campo next, che quindi sono contigui in memoria. L’implementazione della mymalloc (che non deve essere modificata) è riportata di seguito:

e2.c

header_t* free_list = NULL;

void* mymalloc(size_t m) {                           // prende size del payload da allocare
    header_t *p, *q = NULL;
    m = ((m+3)/4)*4;                                 // arrotonda al più piccolo multiplo di 4 maggiore o uguale a m
    if (m < 8) m = 8;                                // garantisce spazio per il puntatore next
    for (p=free_list; p != NULL; q = p, p = p->next) // cerca blocco libero first-fit
        if (p->size >= m) break;
    if (p == NULL) p = sbrk(4 + m);                  // nessun blocco libero, si espande l'heap
    else                                             // toglie nodo dalla lista dei blocchi liberi
        if (q == NULL) free_list = free_list->next;
        else q->next = q->next->next;
    ((header_t*)p)->size = m;                        // size misura il blocco a meno del campo size stesso  
    return (char*)p+4;                               // restituisce puntatore al payload
}

void myfree(void* p) {                               // prende puntatore al payload
    // completare la funzione...
}

Si compili il programma con make. Se myfree è realizzata correttamente, l’output del programma di prova E2-free/e2_main.c deve essere il seguente (ovviamente gli indirizzi saranno diversi):

--- heap size: 76 byte
1   [0x10289f000][size=16  ][free]
2   [0x10289f014][size=24  ][used]
3   [0x10289f030][size=8   ][free]
4   [0x10289f03c][size=12  ][used]
=== free_list: 0x10289f000
*   [0x10289f000][size=16  ][next=0x10289f030]
*   [0x10289f030][size=8   ][next=0x0]

Se l’output (a meno degli indirizzi dei blocchi) è questo, inserire 1 nel form di consegna, e 0 altrimenti.

L’output elenca dapprima i blocchi presenti in heap e poi mostra il contenuto della lista di blocchi liberi dopo aver eseguito la seguente sequenza di operazioni:

    void* p1 = mymalloc(16);
    void* p2 = mymalloc(22);
    void* p3 = mymalloc(8);
    void* p4 = mymalloc(12);
    myfree(p1);
    myfree(p3);
    void* p5 = mymalloc(4);
    void* p6 = mymalloc(14);
    myfree(p5);
    myfree(p6);
Esercizio 3 (Domande)

Domanda 1 Quale delle seguenti affermazioni è VERA?

Domanda 2 Dato il seguente codice, quale tra le seguenti affermazione è VERA?

Domanda 2

Domanda 3 Dato il seguente output di valgrind, quale delle seguenti affermazioni è VERA?

Domanda 3

Domanda 4 Dato il seguente output di valgrind, quale delle seguenti affermazioni è FALSA?

Domanda 4

Domanda 5 Dato il seguente output di valgrind, quale delle seguenti affermazioni è FALSA?

Domanda 5

Domanda 6 Quale delle seguenti affermazioni è VERA?

Domanda 7 Quale delle seguenti affermazioni è FALSA?

Domanda 8 Quale delle seguenti affermazioni è FALSA?

Soluzioni

Esercizio 1 (prefisso di stringa)

e1_eq.c

#include "e1.h"

int is_prefix(const char* s1, const char* s2){
    const char* c = s1;
    const char* d = s2;
L:; char a = *c;
    if (a == 0)
        goto E;
    char b = *d;
    c++;
    d++;
    if (a != b)
        goto E;
    goto L;
E:  a = *c;
    a = a == 0;
    return a;
}

e1.s

.globl is_prefix

is_prefix: # int is_prefix(const char* s1, const char* s2)
    pushl %ebx
    movl 8(%esp), %ecx              # const char* c = s1;
    movl 12(%esp), %edx             # const char* d = s2;
L:  movb (%ecx), %al                # char a = *c;
    testb %al, %al                  # if (a == 0)
    je E                            #     goto E;
    movb (%edx), %bl                # char b = *d;
    incl %ecx                       # c++;
    incl %edx                       # d++;
    cmpb %bl, %al                   # if (a != b)
    jne E                           #     goto E;
    jmp L                           # goto L;
E:  movb (%ecx), %al                # a = *c;
    testb %al, %al                  # a = a == 0;
    sete %al
    movsbl %al, %eax
    popl %ebx
    ret
Esercizio 2 (un semplice allocatore di memoria)

e2.c

void myfree(void* p) {
    header_t* q = (header_t*)((char*)p-4);
    q->next = free_list;
    free_list = q;
}
Esercizio 3 (Domande)
  1. D. L’indirizzo passato alla free punta al payload del blocco allocato da malloc

    Spiegazione: alla funzione free occorre passare l’indirizzo restituito dalla corrispondente malloc, che punta al payload del blocco (cioè la parte effettivamente utilizzabile per i dati) e non al header del blocco (che è gestito internamente da malloc/free in modo totalmente trasparente per il programmatore).

  2. C. Il processo figlio entra nello stato zombie dopo aver terminato la propria esecuzione e fino al momento in cui il processo padre raccoglie il suo exit status

    Spiegazione: quando un processo termina, il kernel libera le risorse associate, ma deve conservarne alcune, come il PCB, per permettere al processo padre di raccogliere l’exit status tramite wait/waitpid. In questo intervallo di tempo il processo entra in uno stato denominato zombie. Quando il padre raccoglie l’exit status il kernel può rilasciare tutte le risorse associate al figlio, che esce dallo stato zombie e non compare più nella lista dei processi. Se il padre termina senza raccogliere l’exit status del figlio (con wait/waitpid) il processo figlio viene adottato da un processo antenato del processo padre (storicamente init, nei sistemi moderni un discendente di init) che raccoglie l’exit status del figlio permettendo così al kernel di liberare tutte le risorse associate (questi processi vengono detti anche reaper).

  3. B. Il programma accede in scrittura oltre la fine di un blocco allocato con malloc

    Spiegazione: La riga di errore di valgrind specifica “Invalid write of size 4”, cioè accesso in scrittura (di 4 byte) non valido. Tra i dettagli dell’errore troviamo “Address 0x5204054 is 0 bytes after a block of size 20 alloc'd”, cioè l’indirizzo di accesso non valido è a 0 byte di spiazzamento oltre la fine di un blocco di dimensione 20 (allocato con malloc). Quindi l’errore riguarda un accesso ai primi 4 byte oltre la fine del blocco allocato con malloc. Questo è un errore tipico che si presenta, ad esempio, quando si alloca un array di n elementi (indici da 0 a n-1) e si accede in scrittura all’elemento di indice n.

  4. A. Valgrind segnala un errore che riguarda lo heap

    Spiegazione: L’unico errore segnalato da valgrind è “Conditional jump or move depends on uninitialized value(s)”. Questo errore è relativo al fatto che una qualche istruzione condizionale (corrisponedente nel sorgente C a istruzioni if, while, for, ecc.) dipende da una variabile non inizializzata. Nello HEAP SUMMARY di valgrind si vede chiaramente che non è stato allocato alcun blocco nello heap. Dunque la variabile non inizializzata è nel segmento stack o data.

  5. B. Il programma profilato da valgrind esegue una sola malloc

    Spiegazione: Nello HEAP SUMMARY di valgrind si vede che sono state eseguite 2 malloc e una free.

  6. E. Nessuna delle precedenti

    Spiegazione: Tutte le altre risposte sono false. Infatti:

    • La frammentazione esterna si ha quando si avrebbe spazio libero sufficiente ad accogliere una richiesta di allocazione, ma poiché i blocchi liberi sono frammentati non è possibile accoglierla (ciascun blocco libero non è sufficientemente grande da soddisfare la richiesta di allocazione). Questa non ha niente a che vedere con il padding, perciò l’affermazione A è falsa.
    • L’allocatore malloc/free soffre di frammentazione esterna. Infatti, la malloc deve poter allocare blocchi di dimensioni diverse (dunque la free può lasciare buchi di dimensioni diverse) e, per ovvie ragioni, può restituire solo blocchi contigui di memoria. Dunque anche la risposta B è falsa.
    • Il meccanismo di paginazione della memoria, poiché alloca solo blocchi di dimensione fissa, non soffre del problema della frammentazione esterna, tuttavia soffre del problema della frammentazione interna (come tutti gli allocatori che possono allocare blocchi di memoria più grandi di quelli realmente richiesti). Dunque la risposta C è falsa.
    • Infine, l’area di swap permette di allocare più memoria virtuale di quanta ne sia disponibile in memoria fisica (in RAM). Non rappresenta un mezzo per contrastare la frammentazione interna, che invece rimane indipendentemente dall’area di swap. Dunque anche la risposta D è falsa.
  7. E. Non è possibile modificare il contenuto di una variabile d’ambiente esistente

    Spiegazione: è possibile. Il nome stesso “variabile” indica il fatto che il suo valore associato può variare nel tempo.

  8. D. setenv("ABC", "123", 1) assegna il valore 123 alla variabile ABC ma solo se ABC esiste già

    Spiegazione: il terzo parametro della setenv (overwrite) indica il comportamento che la setenv deve tenere nel caso in cui la variabile d’ambiente (in questo caso ABC) esista già. Tuttavia se la variabile d’ambiente non esiste, il terzo parametro viene completamente ignorato e viene creata una nuova variabile d’ambiente a cui viene assegnato il valore indicato nel secondo parametro. Dunque in qualunque caso, se la variabile non esiste, viene creata e assegnata. Perciò l’affermazione della risposta D è falsa (e dunque è la risposta corretta alla domanda 8).