ProvaTeorica 2013.01.24

testo: http://www.cs.unibo.it/~renzo/so/compiti/2013-01-24.tot.pdf

Esercizio C1: (a) Scrivere un monitor nmbb che realizzi un buffer limitato (di ampiezza BUFSIZE) che consenta alle chiamate write (inserimento nel buffer) e read (lettura da buffer) di operare su vettori di piu' elementi. In particolare l'interfaccia delle procedure entry da implementare e' la seguente: procedure entry write(int n, struct elem *v); procedure entry read(int m, struct elem *w); se n o m sono maggiori di BUFSIZE le funzioni non devono fare nulla (caso di errore). La funzione write deve attendere che ci sia spazio nel buffer per inserire n elementi (il vettore v conterra' n elementi). Solo quando e' possibile completare l'operazione vengono inseriti tutti gli elementi di v nel buffer. La funzione read attende che vi siano almeno m elementi nel buffer quindi estrae dal buffer (in ordine FIFO) m elementi e li copia nel vettore w . (b) sono possibili casi di deadlock? (motivare dettagliatamente la risposta)

La mia Soluzione:

read(): legge dalla coda un elemento senza rimuoverlo
queue(elem v,int n): inserisce nella coda n elementi v;
dequeue(int n): legge n elementi dalla coda e li rimuove;

monitor  mnbb{
	conditon oktowrite, oktoread;
	queue qwrite,qread;

	procedure entry write(int n, struct elem *v){
		if(n > BUFSIZE){
			return(ERROR);
		}
		if( n > (BUFSIZE - buff.lengh)){
			qwrite.queue( n, 1 );
			oktowrite.wait();
		}
		buff.queue( v, n );
		if(qread.read() <= buff.lengh){
			qread.dequeue(1);
			oktoread.signal();
		}
}

	procedure entry read(int m, struct elem *w){
		if(m > BUFSIZE){
			return(ERROR);
		} 
		if(m > buff.lengh){
			qread.queue( m, 1 );
			oktoread.wait();
		}
		w = buff.dequeue(m);
		if(qwrite.read() <= (BUFSIZE - buff.lengh)){
			qwrite.dequeue(1);
			oktowirte.signal();
		}
	}
}

- Midolo

---

monitor nmbb{
	queue buffer;
	condition oktowrite;
	condition oktoread;
	
	/* assumiamo che essendo un buffer limitato ci sia un solo processo che vuole scrivere e un solo processo che vuole leggere */
	int N, M;
	
	procedure entry write(int n, struct elem *v){
		if(n>BUFSIZE) return;
		N=n;
		if((BUFSIZE - buffer.len) < N)
			oktowrite.wait();
		
		for(i=0; i<N; i++)
			buffer.enqueue(v[i]);
			
		if(buffer.len >= M)
			oktoread.signal();
		}
		
	procedure entry read(int m, struct elem *w){
		if(m>BUFSIZE) return;
		M=m;
		if((BUFSIZE - buffer.len) < M)
			oktoread.wait();
		
		for(i=0; i<M; i++)
			w[i] = buffer.dequeue;
		
		if((BUFSIZE - buffer.len) >= N)
			oktowrite.signal();
		}
	}

Si può verificare deadlock. Esempio: un lettore vuole leggere un tot di elementi, ma quelli presenti non sono sufficienti. Uno scrittore a sua volta non può più scrivere un certo numero di elementi in quanto il buffer è parzialmente occupato. Lo scrittore aspetterà che il lettore legga; il lettore aspetterà invece lo scrittore: deadlock.

L'eventualità che si verifichi deadlock tuttavia è contemplata dalla traccia, come fa capire il punto b)

Gabriele e Giulia

Esercizio g1

TEMPO

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

CPU 1

P1

P1

P1

P4

P4

P4

P3

P2

P2

P1

P1

P3

P3

P3

P4

P1

P1

P1

P1

P1

CPU 2

P2

P2

P3

P3

P3

P1

P1

P4

P4

P4

P4

P4

P4

P4

P4

P4

P2

P2

P2

P2

P2

P3

P3

P3

I/O

P2

P2

P2

P2

P1

P1

P1

P1

P3

P3

P3

P2

P1

P1

P1

P1

P3

P3

P4

GiuliaN.

Mak

  SMP |1|1|1|4|4|4|3|2|2| | |1|1| |3|3|3|4| |1|1|1|1|1|
      |2|2|3|3|3|1|1|4|4|4|4|4|4|4|4|4|2|2|2|2|2|3|3|3|
  RQ  |3|3| |1|1|3|2| | | | | | | | | | | | | | | | | |
      |4|4|4| | | |4| | | | | | | |3|2|4| | | | | | | |
  IO  | | |2|2|2|2| |1|1|1|1|3|3|3|2|1|1|1|1|3|3|4| | |