Prova teorica 2015.02.14

Testo: [1]

Esercizio c.1

Soluzione di Silas

#define MAX 

monitor altcolbb{
	queue buff;
	color_t last_color; //0: red, 1:blue, -1:"superstate", means that both red and blue are accepted
	int wait_red, wait_blue;
	condition ok2read, redok, blueok;

	void altcolbb(void){
		buff = new queue();
		last_color = -1;
		wait_red = wait_blue = 0;
	}
	
	procedure entry void write(color_t color, generic_type val){
		if(last_color == color || buff.length() == MAX){ //we can't enqueue if the colors are the same or if the buffer is full
			if(color == 0){ //enqueue to "reds"
				wait_red++;
				redok.wait();
				wait_red--;
			}else{ //enqueue to "blues"
				wait_blue++;
				blueok.wait();
				wait_blue--;
			}
		}
		buff.enqueue(val); //append val and update last_color
		last_color = color;
		ok2read.signal();
	}
	
	procedure entry generic_type read(void){
		if(buff.length() == 0)
			ok2read.wait();
		generic_type ret = buff.dequeue();
		if(buff.length() == 0)
			last_color = -1; //if buff is empty both colors can now be added
		switch(last_color){
			case -1: {
					if(wait_red>wait_blue) //if there are more "reds" waiting to write we signal them
						redok.signal();
					else
						blueok.signal(); //otherwise we signal "blues"
					break;
			}
			case 0: {
					blueok.signal();
					break;
			}
			case 1: {
					redok.signal();
					break;
			}
		}
	}
	
}

Soluzione di MarcoNegrini

I corrected Silas's version

#define MAX 
 
monitor altcolbb{
	queue buff;
	color_t last_color; //0: red, 1:blue, -1:"superstate", means that both red and blue are accepted
	condition ok2read, ok2write, redok, blueok;

	void altcolbb(void){
		buff = new queue();
		last_color = -1;
	}
 
	procedure entry void write(color_t color, generic_type val){
		if(buff.length() == MAX){ //here waits if buff is full
			ok2write.wait();
		if(last_color==-1){ //if buff was empty it can just enqueue and exit
			buff.enqueue(val);
			last_color = color;
		}
		else{	
			if(color == 0){ //red section
				if (last_color == 0) //if last was red it needs to wait
					redok.wait();
				buff.enqueue(val); 
				last_color = color; // it must set last color before signaling other writers
				blueok.signal(); //blue can now enqueue his value
			}else{ //blue section, same as above
				if (last_color == 1)
					blueok.wait();
				buff.enqueue(val);
				last_color = color;
				redok.signal();
			}
		}
		ok2read.signal(); // reader can now read
	}
 
	procedure entry generic_type read(void){
		//here waits if needed, then dequeue
		if(buff.length() == 0) 
			ok2read.wait();
		generic_type ret = buff.dequeue();

		//here signal the one that has been waiting for more time
		// it MUST be of the last_color color
		if(buff.length() == 0){
			color_t tmp=last_color;
			last_color = -1; 
			// last color MUST be set to -1 here because 
			// if there were writers waiting on ok2write.wait() (full buffer case)
			// they woundn't be signaled here, this happens if MAX=1
			
			if (tmp == 1) //
				blueok.signal();
			else
				redok.signal();
		}
		ok2write.signal();
	}
 
}

Soluzione di FedericoB

relating to Silas and Marco solution. A bounded buffer is a queue, so i think is wrong to use last_color as head element color when it's used as tail element color.

#define MAX

monitor altcobb {
	deque buffer
	condition waitRed, waitBlue, ok2read, ok2write
	altcobb() {
		buffer = new Deque()
		
	}
	procedure entry void write(colot_t color,generic_type val) {
		if (deque.getSize()==MAX) ok2write.wait()
		if (buffer.getSize==0) queue.addLast((val,color))
		else 
			if (color==RED)
				if (buffer.getLast().color==BLUE)
					queue.addLast((val,color))
					waitRed.signal()
				else 
					waitBlue.wait()
					queue.addLast((val,color))
			else
				if (buffer.getLast().color==RED)
					queue.addLast((val,color))
					waitBlue.signal()
				else 
					waitRed.wait()
					queue.addLast((val,color))
		ok2read.signal()
	}
	procedure entry generic_type read() {
		if (deque.isEmpty()) ok2read.wait()
		element = deque.dequeueFirst();
		ok2write.signal()
		return element;
                #needed explanation: after the ok2write.signal() the current process will be put in wait state in the urgent stack, 
                #but after the woke up process has exited the monitor this process will be woke up and it will return the element.
	}
}

Esercizio c.2

Soluzione di Silas

I semafori garantiscono che A e B vengano eseguiti in maniera sequenziale e che accedano in maniera mutualmente esclusiva ad n, quindi l'unica variazione possibile è il thread di inizio per la sequenza.
Nel caso sia A ad accedere per primo alla CS si ha: n = ((1*2)+2)*3 = 12
Nel caso sia invece B ad accedere per primo alla C si ha: n = (((0*2)+1)*3)+2 = 5
Quindi n = 12 e n = 5 sono i due possibili valori.

Anche secondo me è così --FedericoB (talk) 20:58, 13 June 2017 (CEST)

In realtà i possibili valori sono: 12 5 9 e 8. In quanto è vero che possono solo alternarsi i due thread. ma i semafori partono da 1. pertanto al "secondo giro può partire chiunque dei due, in quanto avrà il suo semaforo a 1 e non bloccato nella P".

Le sequenze possibili sono: A AB A AB, AB A AB A, AB A A AB, A AB AB A