[Sistemi Operativi] Problema sincronizzazione

[Lotus2]

Salve, vorrei chiedervi un parere circa il seguente esercizio di sincronizzazione tra processi concorrenti. Per la soluzione mi sono ispirato al classico problema lettori-scrittori.
Ho utilizzato come dati condivisi 3 semafori (donne, uomini, mutex) e 2 contatori, uno per le donne e uno per gli uomini. Mutex controlla l'accesso ai contatori.

TESTO:
Un locale pubblico è dotato di un’unica toilette cui possono accedere sia uomini che donne e che viene gestita in base alle seguenti regole:
1- La toilette può essere libera, occupata da donne o occupata da uomini
2- Se la toilette è libera, allora la prima persona che arriva può entrare
3- Se la toilette è occupata da donne, allora un’altra donna può entrare ma nessun uomo può fare altrettanto e quindi deve aspettare
4- 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.

MIA SOLUZIONE:

Semaforo donne, uomini, mutex;
int contD, contU;

Void donna ()
{
	if (contU > 0)
	   wait(donne);

	wait(mutex);
	if (contD == 0)
	   wait(uomini);
	contD++;
	signal(mutex);

	usa bagno;

	wait(mutex);
	contD--;
	if (contD == 0)
	   signal(uomini);
	signal(mutex);
}

La funzione “uomo” è speculare a questa. Il mio dubbio è il seguente: se ad esempio il bagno è occupato da uomini, si creerà una coda processi donna che chiamerà più volte la seconda istruzione ovvero wait(donna). Usciti tutti gli uomini questi processi donna bloccati riusciranno a rientrare? Penso di dover bilanciare la prima wait(donna) ma non so come...
Ogni suggerimento è ben accetto. Grazie.

[apatriarca]

Puoi dare un occhiata a questa specie di presentazione per trovare qualche idea su come risolvere il tuo problema.

[Lotus2]

Grazie della segnalazione. Ho una nuova idea che proverò a sviluppare domani.
Però mi è sorto un dubbio più elementare sull'uso dei semafori... Per i più esperti sarà semplicissimo.
Ho un processo ad esempio

void P1 ()
{
istruzione 1;
istruzione 2;

WAIT (semaforo);

istruzione 3;
istruzione 4;
}

se il programma viene bloccato alla WAIT sarà rimosso dalla coda dei processi pronti. Quando verrà risvegliato (con una signal) riprenderà l'esecuzione da capo o dall'istruzione seguente la wait?

[Rggb1]

"da capo"?

[Lotus2]

Intendo: quando P1 torna in esecuzione, viene eseguito di nuovo dalla ISTRUZIONE1 oppure riprende l'esecuzione dalla ISTRUZIONE3?
Se riprendesse dall'istruzione3 vuol dire che il suo stato deve essere stato salvato al momento della WAIT, ma il mio testo non fa riferimento a nessun salvataggio di stato o context switch...
Qualcuno mi sa spiegare cosa avviene?

[Rggb1]

La mia shocking-face era per dire "come è possibile tu abbia un dubbio simile?" Leggendo la tua precisazione, mi rendo conto che alle volte non è così ovvio.

Naturalmente, il processo riprende da dove si era interrotto. Ed ovviamente sì, il SO deve gestire il cambio di contesto - salvando lo stato, aggiornando la readyqueue e così via.

Perché il tuo testo non vi faccia riferimento è cosa ardua da dire. Ma presumo che, semplicemente, lo dia per assunto: probabilmente in precedenza c'è qualcosa al riguardo.

[hamming_burst]

Non mi piace molto come hai risolto il problema. Fai dipendere troppo il processo donna() ai semafori di uomini().

Ti propongo un'alternativa più "raffinata".
Devi pensare che è la risora toilette che si occupa di chi può entrare o meno. Non sono le donne o gli uomini direttamente.
Perciò una possibilità è utilizzare i semafori privati e scrivere una struttura toilette. Se noti il tuo codice ha possibilità di starvation (vedi in fondo).

#define NPEOPLE 2
typedef enum {DONNE,UOMINI} People;

struct toilette{
	sem people[NPEOPLE]
	int busy[NPEOPLE]

	sem mutex;

};

inizializziamo tutti i sem a 0 (ci mettiamo in wait), utilizziamo la politica dei contatori, come hai fatto te va bene. Ed un mutex per la consistenza dei dati della risorsa.

void init_tolette(struct toilette& bath){
 
	for(int i=0;i<NPEOPLE;i++){

		sem_init(bath.people[i],0);
		bath.busy[i] = 0; //bagno libero
		
	}

	sem_init(bath.mutex,1);
}

Ora dobbiamo creare una funzione che richiede la risorsa ed una che la rilasci. La base di ciò che hai scritto va bene, ma prova a riportarlo in due funzioni:

void req_toilette(struct toilette& bath,People genre)

void ril_toilette(struct toilette& bath,People genre)

che chiamerai nei tuoi processi:

struct toilette bath;
void donne(){

req_toilette(bath,DONNE);

/*vai in bagno*/

ril_toilette(bath,DONNE);

}

void uomini(){

req_toilette(bath,UOMINI);

/*vai in bagno*/

ril_toilette(bath,UOMINI);

}

Prova se hai problemi ne discutiamo. Questa strutturazione della concorrenza con due funzioni è abb un classico.

Per il tuo codice vediamo di sistemarlo un po'.

Semaforo donne, uomini, mutex;
int contD, contU;

Void donna () {
wait(mutex); 

devi asquisire subito il mutex perchè contU è una variabile globale, c'è possibilità di incosistenza se nell'istante successivo che hai controllo che è >0, uomini() diventa 0

if (contU > 0) {
      signal(mutex);//liberiamo il mutex così da lasciar spazio ad altri
      wait(donne); 
      wait(mutex); //lo riprendiamo avendolo liberato, lo riprendiamo all'interno dell'if perchè se contU==0 lo possediamo dalla prima riga.
  }

   if (contD == 0) //questo non ha senso, se la donna è appena entrata contD non sarà mai 0 e perchè se è 0 gli uomini devono attendere? è il contrario
      wait(uomini);
    //un bellissimo starvation non hai fatto una signal prima della wait ATTENZIONE, per risolvere fai come sopra

   contD++; 
   signal(mutex);

   usa bagno;

   wait(mutex);
   contD--;
   if (contD == 0)
      signal(uomini);
   signal(mutex);
}

il resto è in parte giusto ma troppo incroci fai, così non va affatto bene. Se si ha una risorsa in comune come con i lettori-scrittori, cioè molti lettori (divisi in n gruppi mutualmente esclusivi) per una singola risora è meglio fare come ti ho proposto.

[Lotus2]

@Rggb immagino che possano sembrare domande banali ma affronto i semafori solo da alcuni giorni Cmq grazie del chiarimento!

@hamming_burst Grazie mille della tua analisi approfondita. Sto studiando la tua soluzione, ti disturberò di nuovo se mi perdo in qualche punto
Per quanto riguarda la starvation nella mia soluzione non sono così convinto... Innanzitutto avevo omesso una cosa importante: tutti i semafori della mia soluzione sono inizializzati a 1. Per questo ho invocato una WAIT prima della SIGNAL. Riassumendo la mia idea era: quando una donna accede al bagno, verifica tramite il contatore se è la prima; se lo è allora invoca WAIT sul semaforo degli uomini per impedirgli accesso, usa il bagno e, all'uscita, se non ci sono altre donne dentro libera l'accesso degli uomini con la SIGNAL. Forse ci potrebbe essere starvation con un flusso continuo di donne... non so se tu intendevi questo.
Grazie.

[Rggb1]

Piccolo appunto finale.

"Lotus":Per quanto riguarda la starvation nella mia soluzione non sono così convinto...

Secondo me ha ragione hamming_burst. E poi sottolineo questo semplice consiglio:

"hamming_burst":devi acquisire subito il mutex perchè contU è una variabile globale, c'è possibilità di incosistenza

cioè, poni sempre le parti di codice dove c'è accesso a variabili condivise (le cd. critical sections ovvero sezioni critiche) all'interno delle coppie di istruzioni wait/signal (P/V).

@hamming_burst: in pratica hai creato un monitor con dei semafori.

[hamming_burst]

"Rggb":Piccolo appunto finale.

[quote="Lotus"]Per quanto riguarda la starvation nella mia soluzione non sono così convinto...

Secondo me ha ragione hamming_burst. E poi sottolineo questo semplice consiglio:

"hamming_burst":devi acquisire subito il mutex perchè contU è una variabile globale, c'è possibilità di incosistenza

cioè, poni sempre le parti di codice dove c'è accesso a variabili condivise (le cd. critical sections ovvero sezioni critiche) all'interno delle coppie di istruzioni wait/signal (P/V).
[/quote]
esatto. Bisogna sempre ricordarsi se è chiamata una wait, prima di chiamarne un'altra, deve esserci una signal (post) corrisondente, è un errore piuttosto comune... per questo sono nati i costrutti: monitor, path_expressions, e compagnia concorrente.

@hamming_burst: in pratica hai creato un monitor con dei semafori.

sì la base all'idea dei monitor c'è proprio questa struttura con sem privati
anche se quest'ultima è più malleabile ed estensibile a cose piuttosto complesse (a scapito di possibili errori di programmazione).

[zeussss1]

Secondo voi questa soluzione che utilizza semplici semafori senza utilizzare costrutti tipo monitor, potrebbe funzionare?
Scusate lo pseudolinguaggio mezzo basic-like e mezzo c-like.

Void main()
Begin
	Int donnedentro=0;
	Int uominidentro=0;
   Int donneattesa=0;
	Int uominiattesa=0;
	semaforo mutex(count=1);
	semaforo  xx(count=0);
	semaforo  xy(count=0);
	parbegin
		uomo(); ……; donna(); …….;
	parend;
End;

Void donna()
Begin
    	wait(mutex);
    	if uominidentro>0 then
  		donneattesa=donneattesa+1;
		signal(mutex);
		wait(xx);
		wait(mutex);
		donneattesa=donneattesa-1;
	endif;
	donnedentro=donnedentro+1;
	signal(mutex);
	utilizzabagno;
	wait(mutex);
	donnedentro=donnedentro-1;
	if donnedentro=0 then
		for i=1 to uominiattesa
			signal(xy);              //sblocco tutti i processi uomini in attesa
		next I
	endif;
	signal(mutex);
end;

[zeussss1]

Nessuno degli esperti si sbilancia per un sì o un no?

[hamming_burst]

Ciao
vediamo...

Void main()
Begin
	Int donnedentro=0;
	Int uominidentro=0;
   Int donneattesa=0;
	Int uominiattesa=0;
	semaforo mutex(count=1);
	semaforo  xx(count=0);
	semaforo  xy(count=0);

ok

	parbegin
		uomo(); ……; donna(); …….;
	parend;
End;

con questo cosa dichiareresti?

    
Void donna()
Begin
	wait(mutex);
    	if uominidentro>0 then
  		donneattesa=donneattesa+1;
		signal(mutex);
		wait(xx);
		wait(mutex);
		donneattesa=donneattesa-1;
	endif;
	donnedentro=donnedentro+1;
	signal(mutex);
	utilizzabagno;

fin qui mi pare ok.

	wait(mutex);
	donnedentro=donnedentro-1;
	if donnedentro=0 then
		for i=1 to uominiattesa
			signal(xy);              //sblocco tutti i processi uomini in attesa
		next I
	endif;
	signal(mutex);
end;

ed ok.

Hai pure considerato una politica di sicurezza. Solo la funziona donna() può scrivere le variabili di donne e leggere uomini, e contrario.

[zeussss1]

"hamming_burst":Ciao
vediamo...

	parbegin
		uomo(); ……; donna(); …….;
	parend;
End;

con questo cosa dichiareresti?

Questo è una scorciatoia sintattica per lanciare i thread in parallelo (parbegin=inizio-parallelo parend=fine-parallelo).
Grazie mille del parere.