Tesine sui sistemi operativi

Problemi di mutua esclusione nel modello a memoria comune

Descrizione

Scrivere una applicazione concorrente che generi due processi figlio che competano per l’uso di un buffer di memoria (un processo figlio si comporti da lettore e l’altro da scrittore).

Il programma seguente implementa il problema dei Lettori/Scrittori nel caso particolare in cui ci sia un solo processo lettore ed un solo processo scrittore, ai quali si estendono i seguenti vincoli:

• Processo lettore: la lettura del buffer di memoria comune (allocato dal processo padre) da parte del lettore può avvenire solo dopo la scrittura da parte del processo scrittore e, chiaramente, il lettore non ha facoltà di modificare il contenuto del buffer.
• Processo scrittore: il processo scrittore opera ogni volta una "sovrascrittura" del contenuto del buffer.
• A garanzia della consistenza del contenuto del buffer condiviso, lettore e scrittore devono accedervi in mutua esclusione.

Semafori

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

void Init_Sem(int, int); // Inizializza Semaforo
void Wait_Sem(int, int); // Wait su Semaforo
void Signal_Sem(int, int); // Signal su Semaforo
int Awaiting_Sem(int, int); // Restituisce il numero di processi in attesa su Semaforo

Semafori.C

#include "semafori.h"

struct sembuf Sem_Buf; // sembuf è un tipo predefinito contenente perlomeno i seguenti campi...
// short sem_num; Numero del semaforo
// short sem_op; Valore da sommare algebricamente al semaforo
// short sem_flg; Flag dell'operazione

union semun Sem_Union; // semun è una unione predefinita contenente i seguenti elementi...
// int val;
// struct semid_ds* buf;
// unshort_t* array;

// ----- Nelle funzioni seguenti ID identifica il gruppo di semafori, N il singolo semaforo nel gruppo -----
void Init_Sem(int ID, int N, int Val) {
    Sem_Union.val = Val;
    semctl(ID, N, SETVAL, Sem_Union); // Imposta il semaforo a Val
}
void Wait_Sem(int ID, int N) {
    Sem_Buf.sem_num = N;
    Sem_Buf.sem_op = -1; // Decrementa il semaforo
    Sem_Buf.sem_flg = 0;
    semop(ID, &Sem_Buf, 1); // NB: Se il semaforo è rosso il chiamante verrà sospeso!
}
void Signal_Sem(int ID, int N) {
    Sem_Buf.sem_num = N;
    Sem_Buf.sem_op = 1; // Incrementa il semaforo
    Sem_Buf.sem_flg = 0;
    semop(ID, &Sem_Buf, 1);
}
int Awaiting_Sem(int ID, int N) {
    return semctl(ID, N, GETNCNT, 0);
}

Programma I.C

Di seguito il codice per implementare il problema dei Lettori/Scrittori:

#include <stdio.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include "semafori.h"

#define DIM 1 // Dimensione dell'area di memoria condivisa
#define NUM_OPS 4 // Numero di letture/scritture
#define MUTEX 0 // Definizione di MACRO per l'accesso al semaforo
#define INITIALIZE(S, V) Init_Sem(ID_Sem, S, V)
#define WAIT(S) Wait_Sem(ID_Sem, S)
#define SIGNAL(S) Signal_Sem(ID_Sem, S)

void main() {
    pid_t pid; // Variabili locali
    int i;
    char value = 'A';
    int status;

    // ----- ALLOCAZIONE BUFFER DI MEMORIA CONDIVISA -----
    key_t Key_Buf = IPC_PRIVATE; // Chiave del buffer
    int ID_Buf; // Identificatore del buffer
    char* Ptr_Buf; // Puntatore al buffer

    ID_Buf = shmget(Key_Buf, DIM, IPC_CREAT | 0664); // Viene allocato un segmento di memoria di dimensione almeno pari a DIM
    // RW per User, RW per Gruppo, R only per Others
    if (ID_Buf == -1) {
        perror("SHMGET\n"); // In caso di errore...
        exit(-1);
    }
    Ptr_Buf = shmat(ID_Buf, 0, 0); // Il segmento allocato viene annesso al segmento dati del processo
    if (Ptr_Buf == (char*)-1) {
        perror("SHMAT\n"); // In caso di errore...
        shmctl(ID_Buf, IPC_RMID, 0); // Rimuove l'ID della Shared Memory
        exit(-1);
    }

    // ----- CREAZIONE SEMAFORO -----
    key_t Key_Sem = IPC_PRIVATE; // Chiave del semaforo
    int ID_Sem; // Identificatore del semaforo

    ID_Sem = semget(Key_Sem, 1, IPC_CREAT | 0664); // Viene allocato un gruppo di semafori di cardinalità 1
    if (ID_Sem == -1) {
        perror("SEMGET\n"); // In caso di errore...
        exit(-1);
    }
    INITIALIZE(MUTEX, 1); // Setta MUTEX a 1

    // ----- GENERAZIONE FIGLIO SCRITTORE -----
    pid = fork(); // Generazione del figlio Scrittore
    if (pid == -1) {
        perror("Impossibile creare un nuovo processo\n"); // In caso di errore...
        exit(-1);
    } else if (!pid) { // Codice del figlio Scrittore
        printf("Sono lo Scrittore, PID = %d\n", getpid());
        for (i = 0; i < NUM_OPS; i++) {
            WAIT(MUTEX);
            printf("Scrivo: %c\n", value); // Sezione Critica di SCRITTURA
            *Ptr_Buf = value;
            SIGNAL(MUTEX);
            value++; // Avanza nell'alfabeto
            sleep(5); // Simula un tempo di produzione
        }
        exit(0); // Il figlio Scrittore termina correttamente
    }

    // ----- GENERAZIONE FIGLIO LETTORE -----
    pid = fork();
    if (pid == -1) {
        perror("Impossibile creare un nuovo processo\n"); // In caso di errore...
        exit(-1);
    } else if (!pid) { // Codice del figlio Lettore
        printf("Sono il Lettore, PID = %d\n", getpid());
        sleep(3); // Attende prima di tentare di leggere
        for (i = 0; i < NUM_OPS; i++) {
            WAIT(MUTEX);
            value = *Ptr_Buf; // Sezione Critica di LETTURA
            printf("Leggo: %c\n", value);
            SIGNAL(MUTEX);
            sleep(5); // Simula un tempo di consumo
        }
        exit(0); // Il figlio Lettore termina correttamente
    }

    // ----- SINCRONIZZAZIONE DEL PADRE CON I FIGLI -----
    for (i = 0; i < 2; i++) { // Il padre rimane in attesa che i figli terminino...
        pid = wait(&status);
        printf("Il figlio con PID %d è terminato!\n", pid);
    }

    // ----- RILASCIO MEMORIA CONDIVISA E SEMAFORO -----
    shmctl(ID_Buf, IPC_RMID, 0);
    semctl(ID_Sem, 0, IPC_RMID);
}

Problemi di cooperazione nel modello a memoria comune

Descrizione

Scrivere una applicazione concorrente che implementi il problema del Produttore/Consumatore. In particolare, il programma crei due processi che agiscono, rispettivamente, da produttore e consumatore, comunicando attraverso un unico buffer di memoria.

Il programma seguente implementa il problema dei Produttori/Consumatori nel caso particolare in cui ci sia un solo processo produttore ed un solo processo consumatore, ai quali si estendono i seguenti vincoli:

• Processo consumatore: il consumo del buffer di memoria comune (allocato dal processo padre) da parte del consumatore non può avvenire se non dopo che il processo produttore vi abbia depositato un contenuto, e al consumo il contenuto viene cancellato.
• Processo produttore: il produttore non può depositare nel buffer di memoria comune un nuovo contenuto se il precedente non è stato ancora consumato.
• A garanzia della consistenza del contenuto del buffer condiviso, consumatore e produttore devono accedervi in mutua esclusione.

Semafori

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

void Init_Sem(int, int); // Inizializza Semaforo
void Wait_Sem(int, int); // Wait su Semaforo
void Signal_Sem(int, int); // Signal su Semaforo
int Awaiting_Sem(int, int); // Restituisce il numero di processi in attesa su Semaforo

Programma II.C

Codice per implementare il problema del Produttore/Consumatore:

#include <stdio.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include "semafori.h"

#define DIM 1 // Dimensione dell'area di memoria condivisa
#define NUM_OPS 4 // Numero di produzioni/consumi
#define SPAZIO_DISPONIBILE 0 // Definizione di MACRO per l'accesso ai semafori
#define MESSAGGIO_DISPONIBILE 1
#define INITIALIZE(S, V) Init_Sem(ID_Sem, S, V)
#define WAIT(S) Wait_Sem(ID_Sem, S)
#define SIGNAL(S) Signal_Sem(ID_Sem, S)

void main() {
    pid_t pid; // Variabili locali
    int i;
    char value = 'A';
    int status;

    // ----- ALLOCAZIONE BUFFER DI MEMORIA CONDIVISA -----
    key_t Key_Buf = IPC_PRIVATE; // Chiave del buffer
    int ID_Buf; // Identificatore del buffer
    char* Ptr_Buf; // Puntatore al buffer

    ID_Buf = shmget(Key_Buf, DIM, IPC_CREAT | 0664); // Viene allocato un segmento di memoria di dimensione almeno pari a DIM
    // RW per User, RW per Gruppo, R only per Others
    if (ID_Buf == -1) {
        perror("SHMGET\n"); // In caso di errore...
        exit(-1);
    }
    Ptr_Buf = shmat(ID_Buf, 0, 0); // Il segmento allocato viene annesso al segmento dati del processo
    if (Ptr_Buf == (char*)-1) {
        perror("SHMAT\n"); // In caso di errore...
        shmctl(ID_Buf, IPC_RMID, 0); // Rimuove l'ID della Shared Memory
        exit(-1);
    }

    // ----- CREAZIONE SEMAFORI -----
    key_t Key_Sem = IPC_PRIVATE; // Chiave del semaforo
    int ID_Sem; // Identificatore del semaforo

    ID_Sem = semget(Key_Sem, 2, IPC_CREAT | 0664); // Viene allocato un gruppo di semafori di cardinalità 2
    if (ID_Sem == -1) {
        perror("SEMGET\n"); // In caso di errore...
        exit(-1);
    }
    INITIALIZE(SPAZIO_DISPONIBILE, 1); // Setta SPAZIO_DISPONIBILE a 1
    INITIALIZE(MESSAGGIO_DISPONIBILE, 0); // Setta MESSAGGIO_DISPONIBILE a 0

    // ----- GENERAZIONE FIGLIO PRODUTTORE -----
    pid = fork(); // Generazione del figlio Produttore
    if (pid == -1) {
        perror("Impossibile creare un nuovo processo\n"); // In caso di errore...
        exit(-1);
    } else if (!pid) { // Codice del figlio Produttore
        printf("Sono il Produttore, PID = %d\n", getpid());
        for (i = 0; i < NUM_OPS; i++) {
            WAIT(SPAZIO_DISPONIBILE);
            printf("Produco: %c\n", value); // Sezione Critica di PRODUZIONE
            *Ptr_Buf = value;
            SIGNAL(MESSAGGIO_DISPONIBILE);
            value++; // Avanza nell'alfabeto
            sleep(5); // Simula un tempo di produzione
        }
        exit(0); // Il figlio Produttore termina correttamente
    }

    // ----- GENERAZIONE FIGLIO CONSUMATORE -----
    pid = fork();
    if (pid == -1) {
        perror("Impossibile creare un nuovo processo\n"); // In caso di errore...
        exit(-1);
    } else if (!pid) { // Codice del figlio Consumatore
        printf("Sono il Consumatore, PID = %d\n", getpid());
        sleep(3); // Attende prima di tentare di consumare
        for (i = 0; i < NUM_OPS; i++) {
            WAIT(MESSAGGIO_DISPONIBILE);
            value = *Ptr_Buf; // Sezione Critica di CONSUMO
            printf("Leggo: %c\n", value);
            SIGNAL(SPAZIO_DISPONIBILE);
            sleep(5); // Simula un tempo di consumo
        }
        exit(0); // Il figlio Consumatore termina correttamente
    }

    // ----- SINCRONIZZAZIONE DEL PADRE CON I FIGLI -----
    for (i = 0; i < 2; i++) { // Il padre rimane in attesa che i figli terminino...
        pid = wait(&status);
        printf("Il figlio con PID %d è terminato!\n", pid);
    }

    // ----- RILASCIO MEMORIA CONDIVISA E SEMAFORO -----
    shmctl(ID_Buf, IPC_RMID, 0);
    semctl(ID_Sem, 0, IPC_RMID);
}

Problemi di cooperazione nel modello a memoria comune

Descrizione

Scrivere un’applicazione concorrente che implementi il problema del Produttore/Consumatore nella variante che prevede più produttori e consumatori che comunicano attraverso un pool di buffer di memoria gestito come vettore circolare.

Il programma seguente implementa il problema dei Produttori/Consumatori (più di uno) nel caso in cui essi si contendano un pool di buffer organizzato come coda circolare (inserimento in coda, prelievo in testa), posto che ad essi si applichino i seguenti vincoli:

• Consumo: il consumo di un singolo buffer di memoria comune (l'insieme del pool è allocato dal processo padre) da parte di un processo consumatore non può avvenire se non dopo che almeno un processo produttore vi abbia depositato un contenuto, e all'atto del consumo il contenuto viene cancellato.
• Processo produttore: un processo produttore non può depositare in un buffer di memoria comune un nuovo contenuto se non è disponibile alcun buffer libero.
• A garanzia della consistenza del contenuto del buffer condiviso, i processi consumatori e produttori, globalmente, devono accedere al singolo buffer in mutua esclusione, tuttavia l'accesso al pool di buffer nella sua totalità avviene comunque in concorrenza.

Semafori

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

void Init_Sem(int, int); // Inizializza Semaforo
void Wait_Sem(int, int); // Wait su Semaforo
void Signal_Sem(int, int); // Signal su Semaforo
int Awaiting_Sem(int, int); // Restituisce il numero di processi in attesa su Semaforo

Prod_Cons_Queue.H

#include <stdio.h>
#include “semafori.h”

#define DIM_QUEUE 4 // Cardinalità della Coda circolare
#define VUOTO 0 // Stati del singolo buffer della Coda circolare
#define IN_USO 1
#define PIENO 2

typedef struct { // Definizione della Coda circolare
    char buffer[DIM_QUEUE];
    char stato[DIM_QUEUE]; // VUOTO, IN_USO o PIENO
    int testa;
    int coda;
} Queue;

void Init_Queue(Queue*); // Inizializza la Coda circolare
void Init_Semafori_Queue(int); // Inizializza i semafori
int Richiesta_Produzione_Queue(Queue*, int); // Richiesta di un buffer libero per la produzione
void Produzione_Queue(int, char, Queue*); // Produzione di un carattere nella Coda circolare
void Rilascio_Produzione_Queue(int, Queue*, int); // Rilascio di un buffer pieno
int Richiesta_Consumo_Queue(Queue*, int); // Richiesta di un buffer pieno per il consumo
char Consumo_Queue(int, Queue*); // Consumo di un carattere dalla Coda circolare
void Rilascio_Consumo_Queue(int, Queue*, int); // Rilascio di un buffer vuoto

Prod_Cons_Queue.C

#include “prod_cons_queue.h”

#define SPAZIO_DISPONIBILE 0 // Definizione di MACRO per l'accesso ai semafori
#define MESSAGGIO_DISPONIBILE 1
#define MUTEX_PROD 2
#define MUTEX_CONS 3
#define INITIALIZE(S, V) Init_Sem(ID_Sem, S, V)
#define WAIT(S) Wait_Sem(ID_Sem, S)
#define SIGNAL(S) Signal_Sem(ID_Sem, S)

void Init_Queue(Queue* Q) {
    for(int i = 0; i < DIM_QUEUE; i++) Q->stato[i] = VUOTO;
    Q->testa = 0;
    Q->coda = 0;
}

void Init_Semafori_Queue(int ID_Sem) {
    INITIALIZE(SPAZIO_DISPONIBILE, DIM_QUEUE);
    INITIALIZE(MESSAGGIO_DISPONIBILE, 0);
    INITIALIZE(MUTEX_PROD, 1);
    INITIALIZE(MUTEX_CONS, 1);
}

int Richiesta_Produzione_Queue(Queue* Q, int ID_Sem) {
    WAIT(SPAZIO_DISPONIBILE);
    WAIT(MUTEX_PROD);
    int i = Q->coda;
    do {
        Q->coda = (Q->coda + 1) % DIM_QUEUE;
    } while (Q->stato[Q->coda] != VUOTO);
    Q->stato[i] = IN_USO;
    SIGNAL(MUTEX_PROD);
    printf("Buffer %d in uso\n", i);
    return i;
}

void Produzione_Queue(int i, char value, Queue* Q) {
    Q->buffer[i] = value;
    printf("Ho prodotto %c nel buffer %d\n", value, i);
}

void Rilascio_Produzione_Queue(int i, Queue* Q, int ID_Sem) {
    Q->stato[i] = PIENO;
    printf("Buffer %d riempito\n", i);
    SIGNAL(MESSAGGIO_DISPONIBILE);
}

int Richiesta_Consumo_Queue(Queue* Q, int ID_Sem) {
    WAIT(MESSAGGIO_DISPONIBILE);
    WAIT(MUTEX_CONS);
    int i = Q->testa;
    while (Q->stato[i] != PIENO) {
        i = (i + 1) % DIM_QUEUE;
    }
    if (i == Q->testa) Q->testa = (Q->testa + 1) % DIM_QUEUE;
    Q->stato[i] = IN_USO;
    SIGNAL(MUTEX_CONS);
    printf("Buffer %d in uso\n", i);
    return i;
}

char Consumo_Queue(int i, Queue* Q) {
    char value = Q->buffer[i];
    printf("Ho consumato %c nel buffer %d\n", value, i);
    return value;
}

void Rilascio_Consumo_Queue(int i, Queue* Q, int ID_Sem) {
    Q->stato[i] = VUOTO;
    printf("Buffer %d rilasciato\n", i);
    SIGNAL(SPAZIO_DISPONIBILE);
}

Programma III.C

#include <stdio.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include "prod_cons_queue.h"

#define DIM sizeof(Queue) // Dimensione dell'area di memoria condivisa
#define NUM_PROD 3 // Numero di processi produttori
#define NUM_PRODUZ 5 // Numero di produzioni per ogni processo produttore
#define NUM_CONS 5 // Numero di processi consumatori
#define NUM_CONSUM 3 // Numero di consumi per ogni processo consumatore

void main() {
    pid_t pid; // Variabili locali
    int i, j, k;
    char value = 'A';
    int status;

    // ----- ALLOCAZIONE BUFFER DI MEMORIA CONDIVISA -----
    key_t Key_Buf = IPC_PRIVATE; // Chiave del buffer
    int ID_Buf; // Identificatore del buffer
    Queue* Ptr_Buf; // Puntatore al buffer

    ID_Buf = shmget(Key_Buf, DIM, IPC_CREAT | 0664); // Viene allocato un segmento di memoria atto a contenere
    // RW per User, RW per Gruppo, R only per Others
    if (ID_Buf == -1) {
        perror("SHMGET\n"); // In caso di errore...
        exit(-1);
    }
    Ptr_Buf = (Queue*)shmat(ID_Buf, 0, 0); // Il segmento allocato viene annesso al segmento dati
    if (Ptr_Buf == (Queue*)-1) {
        perror("SHMAT\n"); // In caso di errore...
        shmctl(ID_Buf, IPC_RMID, 0); // Rimuove l'ID della Shared Memory
        exit(-1);
    }

    Init_Queue(Ptr_Buf); // Inizializzazione della Queue

    // ----- CREAZIONE SEMAFORI -----
    key_t Key_Sem = IPC_PRIVATE; // Chiave del semaforo
    int ID_Sem; // Identificatore del semaforo

    ID_Sem = semget(Key_Sem, 4, IPC_CREAT | 0664); // Viene allocato un gruppo di semafori di cardinalità 4
    if (ID_Sem == -1) {
        perror("SEMGET\n"); // In caso di errore...
        exit(-1);
    }
    Init_Semafori_Queue(ID_Sem);
}