Sistemi operativi - Esercizi ed Esercitazione

Problema di sincronizzazione tra processi

Si consideri il seguente problema di sincronizzazione tra processi formato da un processo produttore P e da due processi consumatore C1 e C2, che condividono un'area di memoria (buffer) con 10 locazioni.

Il processo produttore P genera ciclicamente un numero intero arbitrario e lo aggiunge al buffer di memoria condivisa. Il processo P si pone in attesa quando tenta di accedere al buffer pieno.

I processi consumatori C1 e C2 consumano ciclicamente un elemento del buffer. I processi C1 e C2 possono accedere al buffer solo se il buffer stesso non è vuoto, e possono consumare un elemento del buffer solo se il numero attuale di elementi nel buffer stesso è dispari (pari).

Si propone una soluzione con semafori al problema di sincronizzazione proposto. Si richiede la descrizione dei dati condivisi, lo pseudocodice delle procedure Produttore() e Consumatore1() e una discussione sulle eventuali differenze tra Consumatore2() e Consumatore1(). Si assuma l'esistenza

Il problema consiste nell'implementare un sistema di processi concorrenti con memoria condivisa a buffer limitato. Il sistema è composto da n produttori e un consumatore, che condividono un'area di memoria con 10 locazioni.

Ogni produttore genera un numero intero arbitrario e lo deposita nel buffer di memoria condivisa. Se un produttore tenta di accedere al buffer quando è pieno, allora stampa tutto il contenuto del buffer e si mette in attesa.

Il consumatore ciclicamente consuma un elemento dal buffer, al quale può accedere solo quando il buffer stesso non è vuoto.

La soluzione proposta prevede l'implementazione delle seguenti procedure:

• Genera(): genera un numero intero arbitrario
• Aggiungi_Al_Buffer(int x): aggiunge il numero x al buffer di memoria condivisa
• Estrai_Dal_Buffer(): estrae un elemento dal buffer
• Consuma(int x): consuma il numero x
• Consuma_Buffer(): consuma tutti gli elementi presenti nel buffer

La soluzione proposta risolve il problema multi-produttore/consumatore garantendo la sincronizzazione tra i processi. I produttori generano i numeri e li aggiungono al buffer solo se questo non è pieno, altrimenti si mettono in attesa. Il consumatore consuma gli elementi dal buffer solo se questo non è vuoto, altrimenti si mette in attesa.

Per quanto riguarda i problemi di deadlock e starvation, la soluzione proposta non ne è affetta. Non ci sono situazioni in cui i processi rimangono bloccati indefinitamente o in cui un processo viene sempre preferito rispetto agli altri. Ogni processo ha la possibilità di accedere al buffer e di eseguire le proprie operazioni in modo equo.

Si proponga una soluzione con semafori al problema del multi-produttore/consumatore. Si richiede una descrizione accurata dei dati e lo pseudocodice delle procedure Produci(), usata dal generico produttore per generare e depositare un numero nel buffer (non si fanno ipotesi sulla frequenza di chiamata di Produci da parte di un produttore) e Consumatore(). Si assuma l'esistenza delle procedure Genera(), Consuma(int x), Aggiungi_Al_Buffer(int x), Estrai_Dal_Buffer() e Stampa_Buffer() con gli ovvi significati. Commentare adeguatamente la soluzione proposta.

Esercizio 3

Si consideri il seguente problema di sincronizzazione tra processi con memoria condivisa a buffer limitato:

Sia dato un sistema di processi concorrenti composto da 2 processi produttori P e P, e da un processo consumatore C, che condividono un'area di memoria con 10 locazioni.

Il processo P (P) genera un numero intero arbitrario e lo deposita nel buffer di memoria condivisa. Il processo P (P) può

accedere al buffer solo quando quest'ultimo non è pieno.

Il processo C consuma ciclicamente una coppia di elementi del buffer al quale può accedere solo quando il buffer stesso contiene almeno 2 elementi.

Si proponga una soluzione con semafori al problema descritto. Si richiede una descrizione accurata dei dati e il pseudocodice delle funzioni Produci(), usata dal generico produttore per generare e depositare un numero nel buffer (non si fanno ipotesi sulla frequenza di chiamata di Produci() da parte di un produttore) e Consumatore(). Si assuma l'esistenza delle procedure Genera(), AggiungiAlBuffer(int x), EstraiCoppiaDalBuffer() e Consuma() con gli ovvi significati. Commentare adeguatamente la soluzione proposta e descrivere il suo comportamento rispetto alle problematiche di deadlock e starvation.

Esercizio 4

Un locale pubblico è dotato di un'unica toilette cui possono accedere sia uomini che donne e che viene gestita in base alle seguenti regole:

toilette può essere libera, occupata da donne o occupata da uomini

Se la toilette è libera, allora la prima persona che arriva può entrare

Se la toilette è occupata da donne, allora un'altra donna può entrare ma nessun uomo può fare altrettanto e quindi deve aspettare

Se la toilette è occupata da uomini, allora un altro uomo può entrare ma nessuna donna può fare altrettanto e quindi deve aspettare

Progettare una soluzione al problema di sincronizzazione tra processi per la gestione della toilette utilizzando il meccanismo di sincronizzazione preferito. Non si fa alcuna ipotesi sul numero di persone (uomini o donne) che possono stare contemporaneamente nella toilette.

Esercizio 5

Si proponga una soluzione con semafori al problema di sincronizzazione tra processi denominato coda iniqua e descritto nel seguito:

Un processo Servente fornisce un servizio ad un insieme di n processi Clienti (numerati da 1 a n) secondo una politica FIFO.

Se non ci sono clienti il processo Servente si pone in attesa. Il generico cliente per ottenere il servizio si accoda e aspetta il suo turno. Esiste inoltre un processo Potente che può spedire una raccomandazione per uno dei clienti. Se il cliente raccomandato è presente nella coda di attesa, allora viene mosso in testa alla coda e sarà il prossimo cliente a essere servito, altrimenti la raccomandazione non ha effetto. Si richiede la definizione della memoria condivisa e lo pseudocodice delle funzioni Servente, Cliente e Potente. Si assuma l'esistenza delle funzioni AggiungiInCoda(int i), EstraiDallaTesta(), EseguiServizio(int i) e RiceviServizio() con gli ovvi significati, e la funzione Raccomanda(int i) che muove il cliente i-esimo in testa alla coda se presente, altrimenti non fa niente. Commentare adeguatamente la soluzione proposta. Domanda 1 Descrivere in maniera dettagliata il meccanismo di gestione della memoria denominato paginazione e l'architettura.

1. dibase per l'implementazione della paginazione tramite la tabella delle pagine. Discutere il comportamento dellapaginazione rispetto alle problematiche di frammentazione della memoria.

2. Descrivere in maniera dettagliata l'algoritmo round robin con quanto di tempo per lo scheduling della CPU. Discutere pregi e difetti di tale tecnica e l'influenza del tempo di context switch sulle sue prestazioni.

3. Descrivere la struttura generale di una porta di I/O e come i suoi registri vengono usati nel meccanismo di negoziazionetra la CPU e il controllore di un dispositivo di I/O nel caso di interrogazione ciclica.

4. Descrivere il metodo di gestione della memoria denominato segmentazione e l'architettura di base perl'implementazione della segmentazione tramite la tabella dei segmenti.

5. Descrivere il problema della gestione dello spazio libero su disco e i due metodi principali per la soluzione di taleproblema. Descrivere pregi e difetti dei

Domanda 6

Descrivere la nozione di stallo tra processi. Enunciare le condizioni necessarie perché esista uno stallo. Descrivere un metodo a piacere per la gestione dello stallo.

Domanda 7

Descrivere il metodo di base di gestione della memoria tramite paginazione. Che cosa è la paginazione su richiesta?

Domanda 8

Descrivere il meccanismo di allocazione indicizzata dello spazio su disco. Evidenziare i vantaggi/svantaggi di tale meccanismo rispetto all'allocazione contigua e a quella concatenata.

Domanda 9

Descrivere in maniera dettagliata la nozione di thread e le motivazioni alla base del suo utilizzo. Quali sono i vantaggi della programmazione multi-threads rispetto al caso di thread singolo?

This document was created with Win2PDF available at http://www.daneprairie.com.

The unregistered version of Win2PDF is for evaluation or non-commercial use only.

Esercizi di Sistemi Operativi

Collezione di esercizi svolti di sistemi operativi

Si consideri un sistema di processi

concorrentiScomposto dall'insieme = {S , S , …, S }, e dal1 2 nprocesso P . Il sistema è definito come segue:

Il generico processo S , denominato produttore, generaiciclicamente un numero intero arbitrario e lo deposita inun'area di memoria condivisa con 10 locazioni disponibili.

Se S tenta di accedere all'area di memoria condivisa quandoiquest'ultima è piena, allora S deve aspettare che la memoriaicondivisa venga svuotata.

Il processo P , denominato svuotatore, ha il compito disstampare e svuotare l'area di memoria condivisa e puòaccedere alla memoria condivisa stessa solo quandoquest'ultima è piena.

© Daniele Frigioni Sistemi Operativi - Esercizi svolti 2 1

Descrizione della memoria condivisa

#define dim 10 // dimensione del buffer condivisosemaforo mutex = 1; // semaforo di mutua esclusione// sulla sezione criticasemaforo svuota = 0; // semaforo di attesa per il processo// svuotatore quando il buffer non è

pienosemaforo vuote = 1; // semaforo di attesa per i processi
// produttori quando il buffer è pieno
int contatore = 0; // contatore delle posizioni piene
// nel buffer
© Daniele Frigioni Sistemi Operativi - Esercizi svolti 3

void Produci() {
    int elemento;
    while (1) {
        elemento = Genera();
        wait(vuote);
        wait(mutex);
        Aggiungi_Al_Buffer(elemento);
        contatore++;
        if signal(svuota);
        (contatore == dim)
        else signal(vuote);
        signal(mutex);
    }
}
© Daniele Frigioni Sistemi Operativi - Esercizi svolti 4

void Svuota() {
    while (1) {
        wait(svuota);
        wait(mutex);
        Stampa_Svuota_Buffer();
        contatore=0;
        signal(mutex);
        signal(vuote);
    }
}
© Daniele Frigioni Sistemi Operativi - Esercizi svolti 5

Analizzare la seguente applicazione concorrente composta da
2 processi concorrenti P e P . Commentare il funzionamento
1 2
dell'applicazione e mostrare l'output prodotto

#define Max1 2
#define Max2 4

semaforo s1 = Max1, s2 = 0;

void P () {
    int K = 0 ;
    while(cont){
        bool cont = 1;
        wait(s2);
        void K++;
        P () {
            cout
            while(cont){

<< "P2: " << K);
if (K ==(Max1+Max2)){
    wait(s1);
    cont = 0;
    K++;
    cout signal(s1);
    << "P1: " << K);
}
if (K == Max1) else signal(s2);
signal(s2);
}}

© Daniele Frigioni Sistemi Operativi - Esercizi svolti 6 3L'applicazione concorrente proposta stampa i valori assunti dalla variabile condivisa K come segue:

void P () {
    #define Max1 2
    1P :1while(cont){
        #define Max2 4
        wait(s1);
        semaforo s1 = Max1;
        2P :K++;
        1cout << "P1: " << K);
        semaforo s2 = 0;
        if (K == Max1) int K = 0 ;
        3P :signal(s2);
        bool cont = 1;
    }
    2}}
    4P :