Sistemi operativi - Appunti

Problemi di mutua esclusione nel modello a memoria comune

Descrizione

Scrivere un'applicazione concorrente che generi due processi figlio che competano per l'uso di un buffer di memoria. Un processo figlio si comporta 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 processo 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: opera ogni volta una "sovrascrittura" del contenuto del buffer.

A garanzia della consistenza del contenuto del buffer condiviso, il processo lettore e il processo scrittore devono accedervi in mutua esclusione tramite semafori.

Codice 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

Implementazione Semafori

#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;
// ushort_t* array;

// Inizializzazione e gestione semafori
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 Lettore/Scrittore

#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 DIM
    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
    if (Ptr_Buf == (char*)-1) {
        perror("SHMAT\n"); // In caso di errore...
        shmctl(ID_Buf, IPC_RMID, 0); // Dealloca il segmento di memoria
        exit(-1);
    }

    // CREAZIONE SEMAFORO
    key_t Key_Sem = IPC_PRIVATE; // Chiave del semaforo/i
    int ID_Sem; // Identificatore del semaforo/i
    ID_Sem = semget(Key_Sem, 1, IPC_CREAT|0664); // Alloca 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++) {
        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 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:

• Consumo: il consumo del buffer di memoria comune da parte del processo consumatore non può avvenire se non dopo che il processo produttore vi abbia depositato un contenuto, e all'atto del consumo tale contenuto viene cancellato.
• Produzione: il processo 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, il processo consumatore e il processo produttore devono accedervi in mutua esclusione tramite semafori.

Programma 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 DIM
    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
    if (Ptr_Buf == (char*)-1) {
        perror("SHMAT\n"); // In caso di errore...
        shmctl(ID_Buf, IPC_RMID, 0); // Dealloca il segmento di memoria
        exit(-1);
    }

    // CREAZIONE SEMAFORI
    key_t Key_Sem = IPC_PRIVATE; // Chiave del semaforo/i
    int ID_Sem; // Identificatore del semaforo/i
    ID_Sem = semget(Key_Sem, 2, IPC_CREAT|0664); // Alloca 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++) {
        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: produttore/consumatore con pool di buffer

Descrizione

Scrivere un'applicazione concorrente che implementi il problema 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 da parte di un processo consumatore non può avvenire se non dopo che almeno un processo produttore abbia depositato un contenuto, e all'atto del consumo tale contenuto viene cancellato.
• Produzione: 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 i processi produttori, globalmente, devono accedere al singolo buffer in mutua esclusione, tuttavia l'accesso al pool di buffer nella sua totalità avviene comunque in concorrenza tramite semafori.

Codice 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

Definizione Coda Circolare

#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

Implementazione Coda Circolare

#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 Produttore/Consumatore con Pool di Buffer

#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 una Queue
    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); // Dealloca il segmento di memoria
        exit(-1);
    }
    Init_Queue(Ptr_Buf); // Inizializzazione della Queue

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

Il codice continua con l'allocazione e gestione specifica per più produttori e consumatori...