Esercizi Sistemi operativi

Esercizi e prove sistemi operativi

Anno: 2020-2021

Professore: Domenico Cotroneo

Autore: Marco Di Fiandra pag. 1

Indice

• Esercitazione 3. Produttori-Consumatori con consumo multiplo e Monitor 3
• Esercitazione 4. Pthread lettori-scrittori su più oggetti monitor 15
• Pipeline di buffer singoli, con probabilità di modifica 22
• Lettori/scrittori con versioning 28
• Lettori/scrittori con priorità 33
• Simulazione d’Esame del 18/12/2020 43
• Prova pratica del 22/12/2020 - Turno 2 52
• Prova pratica del 16/6/2015 64
• Prova pratica del 16/10/201470
• Prova pratica del 21/12/2020 - Turno 182
• Prova pratica del 24/06/201187 pag. 2

Esercitazione 3. Produttori-Consumatori con consumo multiplo e Monitor

Testo

Si realizzi in linguaggio C/C++ un'applicazione multi-processo in cui P produttori e C consumatori scambiano dati attraverso una buffer circolare di 10 elementi di tipo long, allocato in una memoria condivisa.

I processi produttori produrranno un solo elemento ad ogni produzione, mentre i processi consumatori consumeranno tre elementi ad ogni consumazione. Un produttore deve bloccarsi se il buffer a cui tenta di accedere è pieno, finché non c'è spazio disponibile. I consumatori possono prelevare dal buffer se ci sono elementi disponibili; se il buffer è vuoto, i consumatori devono bloccarsi fino a quando non ci sono nuovi elementi nel buffer. L'accesso al buffer e ai relativi puntatori di testa e coda deve essere disciplinato attraverso il costrutto Monitor di Hoare.

Il programma dovrà istanziare 5 processi produttori, ciascuno dei quali produrrà un elemento per 9 volte, attendendo due secondi tra una produzione e l'altra. Inoltre, si dovranno istanziare 5 processi consumatori, ciascuno dei quali preleverà tre elementi dal buffer per 3 volte, attendendo un secondo tra una consumazione e l'altra; gli elementi prelevati saranno stampati a video. Una volta istanziati i processi, tramite la primitiva fork(), il programma principale ne attende la terminazione e termina a sua volta. pag. 3

prodcons.h

#ifndef _PRODCONS_H_
#define _PRODCONS_H_
#include "monitor_hoare.h"
#define DIM 10
typedef struct {
long vettore[DIM];
int testa;
int coda;
/* TBD: Definire il Monitor e le altre variabili per la sincronizzazione */
int totale_elementi;
int spazio_disponibile;
Monitor m;
} ProdCons;
/* TBD: Definire delle macro per identificare le variabili condition */
#define OK_CONSUMATORE 0
#define OK_PRODUTTORE 1
void inizializza(ProdCons * p);
void consuma(ProdCons * p);
void produci(ProdCons * p, int val);
void rimuovi(ProdCons * p);
#endif

prodcons.c

#include <stdio.h>
#include <unistd.h>
#include "prodcons.h"
void inizializza(ProdCons * p) {
/* TBD: Inizializzazione del monitor */
 pag. 4
init_monitor(&(p->m),2);
p->coda = 0;
p->testa = 0;
p->totale_elementi = 0;
p->spazio_disponibile = DIM;
}
void consuma(ProdCons * p) {
/* TBD: Ingresso nel monitor */
enter_monitor(&(p->m));
printf("[%d] Ingresso consumatore\n", getpid());
/* TBD: Sospendere qui il consumatore se non ci sono
* *almeno* 3 elementi disponibili nel vettore*/
if(p->totale_elementi < 3){
wait_condition(&(p->m),OK_CONSUMATORE);
}
p->totale_elementi = p->totale_elementi - 3;
for(int i = 0; i<3;i++){
printf("[CONSUMATORE]: L'elemento consumato in posizione %d e': %ld \n",p->coda,p->vettore[p->coda]);
p->coda = (p->coda + 1)%DIM;
}
p->spazio_disponibile = p->spazio_disponibile + 3;
/* TBD: Effettuare signal_condition() per svegliare i produttori
* in accordo al numero di elementi consumati*/
signal_condition(&(p->m),OK_PRODUTTORE);
printf("[%d] Uscita consumatore\n", getpid());
/* TBD: Uscita dal monitor */
leave_monitor(&(p->m));
}
void produci(ProdCons * p, int val) {
/* TBD: Ingresso nel monitor */
enter_monitor(&(p->m));
printf("[%d] Ingresso produttore\n", getpid());
/* TBD: Sospendere qui il produttore se il vettore è già pieno */
if(p->spazio_disponibile == 0){
wait_condition(&(p->m),OK_PRODUTTORE);
}
p->spazio_disponibile--;
p->vettore[p->testa] = val;
p->testa = (p->testa + 1) % DIM;
p->totale_elementi++;
 pag. 5
printf("[%d] Produzione: val=%d\n", getpid(), val);
/* TBD: Svegliare un consumatore *solo se* sono disponibili almeno 3 messaggi.
* Poiché è richiesto di utilizzare la semantica di Hoare, il consumatore
* sarà attivato immediatamente al momento della signal_condition().*/
if(p->totale_elementi >= 3){
signal_condition(&(p->m),OK_CONSUMATORE);
}
else{
signal_condition(&(p->m),OK_PRODUTTORE);
}
printf("[%d] Uscita produttore\n", getpid());
/* TBD: Uscita dal monitor */
leave_monitor(&(p->m));
}
void rimuovi(ProdCons * p) {
/* TBD: Deallocazione del sotto-oggetto monitor */
remove_monitor(&(p->m));
}

monitor_hoare.h

/***PROTOTIPI DELLE PROCEDURE PER LA REALIZZAZIONE DEL COSTRUTTO MONITOR***/
typedef struct {
//id del semaforo per realizzare il mutex del monitor
int mutex;
//id del semaforo per realizzare la coda urgent
int urgent_sem;
//numero di variabili condition
int num_var_cond;
//id del gruppo sem associati alle var.cond
int id_conds;
//id della memoria condivisa per i contatori delle variabili condition e della coda urgent
int id_shared;
//array delle variabili condition_count
int *cond_counts;
//contatore del numero di processi sospesi sulla coda urgent
int *urgent_count;
 pag. 6
} Monitor;
//monitor e numero di variabili condition
void init_monitor (Monitor*, int);
void enter_monitor(Monitor*);
void leave_monitor(Monitor*);
void remove_monitor(Monitor*);
void wait_condition(Monitor*,int);
void signal_condition(Monitor*,int);
int queue_condition(Monitor*,int);

monitor_hoare.c

/*************************************Monitor*************************************************/
// Implementazione di un Monitor signal-and-wait, con coda urgent (soluzione di Hoare)
#include <sys/ipc.h>
#include <sys/types.h>
#include <sys/sem.h>
#include <sys/shm.h>
#include <stdio.h>
#include <unistd.h>
#include "monitor_hoare.h"
//Funzioni di utilita' private alla libreria Monitor
static void Wait_Sem(int, int);
static void Signal_Sem (int,int);
static int Queue_Sem (int,int); //restituisce il num di processi in attesa su un semaforo
/********************IMPLEMENTAZIONE DELLE PROCEDURE***********************/
void init_monitor (Monitor *M,int num_var){
int i;
//alloca e inizializza il mutex per l'accesso al monitor
M->mutex=semget(IPC_PRIVATE,1,IPC_CREAT|0664);
semctl(M->mutex,0,SETVAL,1);
//alloca e inizializza il semaforo per la coda urgent
 pag. 7
M->urgent_sem=semget(IPC_PRIVATE,1,IPC_CREAT|0664);
semctl(M->urgent_sem,0,SETVAL,0);
//alloca e inizializza i semafori con cui realizzare le var.condition
M->id_conds=semget(IPC_PRIVATE,num_var,IPC_CREAT|0664);
for (i=0;i<num_var;i++)
semctl(M->id_conds,i,SETVAL,0);
//alloca un contatore per ogni var.condition, più un contatore per la coda urgent
M->id_shared=shmget(IPC_PRIVATE,(num_var+1)*sizeof(int),IPC_CREAT|0664);
//effettua l'attach all'array di contatori appena allocato
M->cond_counts=(int*) (shmat(M->id_shared,0,0));
M->num_var_cond = num_var;
M->urgent_count = M->cond_counts + M->num_var_cond;
//inizializza i contatori per le var.condition e per la coda urgent
for (i=0; i<num_var; i++)
M->cond_counts[i]=0;
*(M->urgent_count)=0;
#ifdef DEBUG_
printf("Monitor inizializzato con %d condition variables. Buona Fortuna ! \n",num_var);
#endif
}
void enter_monitor(Monitor * M){
#ifdef DEBUG_
printf("<%d> Tentativo di ingresso nel monitor... \t",getpid() );
#endif
Wait_Sem(M->mutex,0);
#ifdef DEBUG_
printf("<%d> Entrato nel monitor \n",getpid() );
#endif
}
 pag. 8
void leave_monitor(Monitor* M){
#ifdef DEBUG_
printf("<%d> Uscito dal monitor \n", getpid());
#endif
if( *(M->urgent_count) > 0 ) {
#ifdef DEBUG_
printf("<%d> -Monitor- signal sulla coda urgent \n", getpid());
#endif
Signal_Sem(M->urgent_sem,0);
} else {
#ifdef DEBUG_
printf("<%d> -Monitor- signal sul mutex del monitor \n", getpid());
#endif
Signal_Sem(M->mutex,0);
}}
void remove_monitor(Monitor* M){
semctl(M->mutex,0,IPC_RMID,0);
semctl(M->urgent_sem,0,IPC_RMID,0);
semctl(M->id_conds,M->num_var_cond,IPC_RMID,0);
shmctl(M->id_shared,IPC_RMID,0);
#ifdef DEBUG_
printf(" \n Il Monitor è stato rimosso ! Arrivederci \n");
#endif
}
void wait_condition(Monitor* M,int id_var){
#ifdef DEBUG_
if(id_var<0 || id_var>=M->num_var_cond) {
printf("<%d> -Monitor- errore nell'invocazione della wait (idvar=%d)\n", getpid(), id_var);
}
#endif
#ifdef DEBUG_
printf("<%d> -Monitor- invocata la wait sulla condition numero %d\n", getpid(), id_var);
#endif
M->cond_counts[id_var]=M->cond_counts[id_var]+1;
if( *(M->urgent_count) > 0 ) {
#ifdef DEBUG_
printf("<%d> -Monitor- signal sulla coda urgent \n", getpid());
#endif
Signal_Sem(M->urgent_sem,0);
} else {
 pag. 9
#ifdef DEBUG_
printf("<%d> -Monitor- signal sul mutex del monitor \n", getpid());
#endif
Signal_Sem(M->mutex,0);
}
Wait_Sem(M->id_conds,id_var);
M->cond_counts[id_var]=M->cond_counts[id_var]-1;
}
void signal_condition(Monitor* M,int id_var){
#ifdef DEBUG_
if(id_var<0 || id_var>=M->num_var_cond) {
printf("<%d> -Monitor- errore nell'invocazione della signal (idvar=%d)\n", getpid(), id_var);
}
#endif
#ifdef DEBUG_
printf("<%d> -Monitor- tentativo di signal; n.ro proc. in attesa sulla cond. n. %d = %d\n",getpid(), id_var,M->cond_counts[id_var]);
#endif
(*(M->urgent_count))++;
if(M->cond_counts[id_var]>0) {
Signal_Sem(M->id_conds,id_var);
#ifdef DEBUG_
printf("<%d> -Monitor- invocata la signal sulla condition numero %d\n", getpid(), id_var);
#endif
#ifdef DEBUG_
printf("<%d> -Monitor- processo in attesa sulla coda urgent \n", getpid());
#endif Wait_Sem(M->urgent_sem,0);
#ifdef DEBUG_
printf("<%d> -Monitor- processo uscito dalla coda urgent \n", getpid());
#endif
}
(*(M->urgent_count))--;
}
int queue_condition(Monitor * M, int id_var){
return M->cond_counts[id_var];
 pag. 10
}
/********************IMPLEMENTAZIONE DELLE PROCEDURE SEMAFORICHE***********************/
void Wait_Sem(int id_sem, int numsem) {
struct sembuf sem_buf;
sem_buf.sem_num=numsem;
sem_buf.sem_flg=0;
sem_buf.sem_op=-1;
semop(id_sem,&sem_buf,1); //semaforo rosso
}
// restituisce il numero di processi in attesa sul semaforo
int Queue_Sem(int id_sem, int numsem) {
return (semctl(id_sem,numsem,GETNCNT,NULL));
}
void Signal_Sem (int id_sem,int numsem) {
struct sembuf sem_buf;
sem_buf.sem_num=numsem;
sem_buf.sem_flg=0;
sem_buf.sem_op=1;
semop(id_sem,&sem_buf,1); //semaforo verde
}

Makefile

all: prodcons
prodcons: main.o monitor_hoare.o prodcons.o
gcc -o prodcons main.o monitor_hoare.o prodcons.o
main.o: main.c prodcons.h
gcc -c -o main.o main.c
monitor_hoare.o: monitor_hoare.c monitor_hoare.h
gcc -c -o monitor_hoare.o monitor_hoare.c
prodcons.o: prodcons.c prodcons.h
gcc -c -o prodcons.o prodcons.c
clean:
rm -f *.o
rm -f prodcons pag. 11

main.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include <time.h>
#include "prodcons.h"
int main(){
int shm_id = shmget(IPC_PRIVATE,sizeof(ProdCons),IPC_CREAT | 0664);
/* TBD: Allocazione dellastruttura dati in shared memory */
if (shm_id < 0){
perror("Errore creazione shared memory");
exit(1);
}
ProdCons *p = shmat(shm_id,0,0);
/* TBD: Attach della shared memory */
if (p == (void *)-1){
perror("Errore attach shared memory");
exit(1);
}
inizializza(p);
/* TBD: Aggiungere codice per avviare Produttori e Consumatori */
for(int i = 0; i<10;i++){
pid_t pid = fork();
if(pid < 0){
perror("Errore nella creazione dei processi \n");
exit(1);
}
if(pid == 0){
if((i%2)==0){
srand(time(NULL)*getpid());
int elemento;
for(int j = 0; j<9;j++){
elemento = rand()%101;
//Genero un elemento da 0 a 100
produci(p,elemento); //Chiamo il produttore
sleep(2);
}}
else{
 pag. 12
for(int j = 0; j < 3;j++){
consuma(p); //Chiamo il consumatore
sleep(1);
}}
exit(0);
}}
printf("[%d] Processo padre in attesa...\n", getpid());
for (int i = 0; i < 10; i++){
wait(NULL);
}
printf("[%d] Terminazione\n", getpid());
rimuovi(p);
shmctl(shm_id,IPC_RMID,0);
return 0;
} pag. 13

Esercitazione 4. Pthread lettori-scrittori su più oggetti monitor

Testo

Si completi in linguaggio C o C++ un programma multi-thread che simuli il monitoraggio di traffico navale. Il programma dovrà essere basato sul costrutto Monitor e risolvere un problema lettori/scrittori con starvation di entrambi.

Si supponga di monitorare 5 navi, la cui posizione (il molo in cui si trova la nave) sia rappresentata da un valore intero compreso tra 0 e 10. La posizione della nave viene aggiornata da dei thread gestori del molo, e consultata da dei thread denominati viaggiatori. Ciascuna nave deve essere monitorata usando una istanza distinta del monitor così definito:

Il metodo leggi_molo() dovrà restituire la posizione attuale della nave, permettendo a più viaggiatori di leggere in contemporanea. Il metodo scrivi_molo() dovrà permettere ai gestori del molo di aggiornare la posizione della nave, garantendo la mutua esclusione tra i thread.

Il programma principale dovrà istanziare 5 istanze del monitor e 5 thread gestori del molo (una istanza e un thread per ogni nave). I gestori del molo dovranno invocare per 10 volte il metodo scrivi_molo(), modificando il valore della posizione ad ogni invocazione (incrementando il valore di 1) e attendendo 3 secondi tra le invocazioni. Il valore del molo deve essere inizialmente posto a 0.

Inoltre, dovranno essere istanziati 10 thread viaggiatori. I thread viaggiatori dovranno scegliere una nave a caso, e dovranno consultare la posizione della nave scelto per 3 volte, invocando il metodo leggi_molo() dopo avere atteso per un tempo casuale (tra 1 e 6 secondi) tra le invocazioni. pag. 14

header.h

#ifndef HEADER_H
#define HEADER_H
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <pthread.h>
#include <time.h>
#define N_GESTORI 5
#define N_VIAGGATORI 10
struct monitor {
int molo;
int id_nave;
pthread_cond_t ok_lettori;
pthread_cond_t ok_scrittori;
/* TBD: Aggiungere variabili per la sincronizzazione */
pthread_mutex_t mutex;
int n_lettori;
int n_scrittori;
int n_scrittori_w;
int n_lettori_w;
};
void inizializza(struct monitor * m);
void rimuovi (struct monitor * m);
void scrivi_molo(struct monitor * m, int molo);
int leggi_molo(struct monitor * m);
#endif

procedure.c

#include "header.h"
void inizializza(struct monitor* m){
m->molo=0;
m->id_nave=0;
/* TBD: Inizializzare le variabili dell'algoritmo, il mutex, e le variabili condition */
pthread_mutex_init(&(m->mutex),NULL);
pthread_cond_init(&(m->ok_lettori),NULL);
 pag. 15
pthread_cond_init(&(m->ok_scrittori),NULL);
m->n_lettori = 0;
m->n_scrittori = 0;
m->n_lettori_w = 0;
m->n_scrittori_w = 0;
}
void rimuovi (struct monitor* m){
/* TBD: Disattivare mutex e variabili condition */
pthread_mutex_destroy(&(m->mutex));
pthread_cond_destroy(&(m->ok_lettori));
pthread_cond_destroy(&(m->ok_scrittori));
}
//Scrittura. Aggiornamento della posizione del treno
void scrivi_molo(struct monitor* m, int molo){
pthread_mutex_lock(&(m->mutex));
while(m->n_lettori > 0 || m->n_scrittori > 0){
printf("Scrittore in wait \n");
m->n_scrittori_w++;
pthread_cond_wait(&(m->ok_scrittori),&(m->mutex));
m->n_scrittori_w--;
printf("Scrittore fuori wait \n");
}
m->n_scrittori++;
pthread_mutex_unlock(&(m->mutex));
sleep(2);
m->molo = molo;
pthread_mutex_lock(&(m->mutex));
if(m->n_scrittori_w > 0){
pthread_cond_signal(&(m->ok_scrittori));
}
else if(m->n_lettori_w > 0){
pthread_cond_broadcast(&(m->ok_lettori));
}
m->n_scrittori--;
pthread_mutex_unlock(&(m->mutex));
/* TBD: Implementare qui lo schema dei lettori-scrittori con starvation di entrambi.
* nella parte della SCRITTURA*/
}
//Lettura. Restituisce la posizione del treno
int leggi_molo(struct monitor* m){
pthread_mutex_lock(&(m->mutex));
while(m->n_scrittori > 0){
printf("Lettore in wait \n");
m->n_lettori_w++;
pthread_cond_wait(&(m->ok_lettori),&(m->mutex));
m->n_lettori_w--;
printf("Lettore fuori wait \n");
 pag. 16
}
m->n_