Difference between revisions of "ProvaTeorica 2013.05.30"

From Sistemi Operativi
Jump to navigation Jump to search
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
<h1>[http://www.cs.unibo.it/~renzo/so/compiti/2013.05.30.tot.pdf Testo del compito]</h1>
 
<h1>[http://www.cs.unibo.it/~renzo/so/compiti/2013.05.30.tot.pdf Testo del compito]</h1>
−
 
+
<h2> Esercizio c.1</h2>
−
<h2>Esercizio c.1</h2>
 
−
 
 
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
−
 
+
monitor eventp {
−
/* Esercizio c.1: scrivere un monitor eventp che realizzi un servizio di sincronizzazione cosi' definito:
+
typedef struct EP {
−
procedure entry EP *create(unsigned value): crea un nuovo descrittore. Ogni descrittore ha un contatore associato.
+
unsigned int value;
−
 
+
condition okNotNull;
−
Value e' il valore iniziale del contatore.
+
condition okToaAdd;
−
 
+
intqueue q;
−
procedure entry void write(EP *d, unsigned value): se il contatore ha un valore tale che se si sommasse value causerebbe overflow,
+
} EP;
−
sospende il processo chiamante. In ogni caso
+
procedure entry EP* create (unsigned value){
−
(se la somma e' possibile senza overflow o quando la somma e' possibile senza overflow)  
+
if (d.value+value > MAXINT || !d.queue.isEmpty()) {
−
somma value al valore del contatore.
+
d.q.enqueue(value);
−
 
+
d.okToAdd.wait();
−
procedure entry unsigned read(EP *d): se il contatore ha valore nullo sospende il processo chiamante fino a che il contatore diventi
+
d.q.dequeue();
−
non nullo.  
+
}
−
In ogni caso restituisce il valore del contatore e riporta il contatore al valore zero.
+
d.value = d.value + value;
−
 
+
if (d.q.top() + value <= d.value.size()) //se il suo valore proposto non causa l’overflow del counter, sblocco lo scrittore successivo
−
procedure entry void close(EP *d): termina le operazioni del descrittore d e cancella il descrittore.
+
d.okToAdd.signal();
−
*/
+
else
−
 
+
d.okNotNull.signal();
−
 
 
−
monitor eventp{
 
−
 
 
−
#define OVERFLOW 999;
 
−
 
 
−
condition okToWrite, okToRead;
 
−
unsigned int oldValue;
 
−
 
 
−
struct EP {
 
−
unsigned int count;  
 
−
} d;
 
−
 
 
−
 
 
−
 
 
−
procedure entry EP *create(value){
 
−
 
 
−
 
 
−
d.count = value;
 
−
 
 
−
return d;  
 
−
 
 
 
}
 
}
  
−
 
+
procedure entry unsigned int read (EP* ep){
−
 
+
if (!ep.value)
−
procedure entry void write(EP *d, unsigned value){
+
ep.okNotNull.wait();
−
 
+
unsigned int toReturn = ep.value;
−
if(d.count+value > OVERFLOW)
+
ep.value = 0;
−
+
ep.okToAdd.signal();
−
okToWrite.wait();
+
return toReturn;
−
d.count= d.count + value;
 
−
okToRead.signal();
 
−
else
 
−
d.count = d.count + value;
 
−
 
 
 
}
 
}
  
−
+
procedure entry close(EP * ep){
−
 
+
free(ep);
−
procedure entry unsigned read (EP *d){
 
−
 
 
−
if(d.count == NULL)
 
−
 
−
okToRead.wait();
 
−
oldValue = d.count;
 
−
d.count = 0;
 
−
okToWrite.signal();
 
−
return oldValue;
 
−
else
 
−
oldValue=d.count;
 
−
d.count=0;
 
−
return oldValue;
 
 
}
 
}
  
−
procedure entry void close(EP* d){
 
−
 
−
close(d);
 
−
delete(d);
 
 
}
 
}
−
 
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
<h2> Esercizio g.1</h2>
  
−
<h2> Esercizio c.2 </h2>
+
<p> <b>PUNTO A:</b> (7+256+(256^2)+(256^3))*1kb =16.843.015kb quindi approssimativamente 16MB</p>
−
 
+
<p> <b> PUNTO B:</B> blocco indiretto triplo -> primo livello di idirizzamento 256 esimo blocco -> secondo livello di indirizzamento 256 esimo blocco -> terzo livello di indirizzamento al blocco 100000. Qundi in totale 4 blocchi </p>
−
<syntaxhighlight lang="C">
 
  
−
/* I semafori v2p hanno come invariante 2*np <= nv + Init, dove np e' il numero di operazioni P completate,
+
<h2> Esercizio g.2 </h2>
−
nv e' il numero delle operazioni V completate e Init e' il valore iniziale
+
[[File:Holt.png]]
−
(cioe' occorrono 2 operazioni V per sbloccare un processo che ha fatto P).
 
−
I semafori v2p hanno lo stesso potere espressivo dei semafori generali o no?
 
−
Produrre una dimostrazione della tesi sostenuta.*/
 
  
−
/* I semafori v2p non hanno lo stesso potere espressivo di quelli generali
 
  
−
DIMOSTRAZIONE: prendo due processi P e Q in questo modo qui: */
+
<syntaxhighlight lang="C">
 +
monitor eventp
 +
{
 +
typedef struct EP
 +
{
 +
unsigned int value;
 +
condition okNotNull;
 +
condition okToAdd;
 +
intqueue q;
 +
}
 +
}
  
−
process P{
+
procedure entry EP* create(unsigned value)
−
 
+
{
−
while (true){
+
EP *ep = new EP(value);
−
 
+
eps.enqueu(ep);
−
P();  
+
return ep;
−
 
+
}
−
printf(“sono p”);
 
  
 +
procedure entry write(EP *d,unsigned value)
 +
{
 +
if(d.value+value > d.value.size()|| !d.q.empty()) {
 +
d.q.enqueue(value);
 +
d.okToAdd.wait();
 +
d.q.dequeue();
 
}
 
}
 +
d.value = d.value + value;
 +
if (d.q.top()+value <= d.value.size())
 +
d.okToAdd.signal();
 +
else
 +
d.okNotNull.signal();
 
}
 
}
  
−
process Q{
+
// MAXINT - currentvalue < value
−
 
+
procedure entry unsigned int read(EP *ep)
−
while (true){
+
{
−
 
+
if(!ep.value)
−
printf(“sono q”);
+
ep.okNotNull.wait();
−
+
unsigned int toReturn = ep.value;
−
V();
+
ep.value = 0;
−
 
+
ep.okToAdd.signal();
−
}
+
return toReturn;
 
}
 
}
−
 
+
<syntaxhighlight>
−
/* inizializzo entrambi i semafori a 2 */
 
−
 
 
−
semaforo v2p(2)
 
−
semaforo generale(2)
 
−
 
 
−
PPPQQQ // sequenza di avvicendamento dei processi
 
−
 
 
−
 
 
−
v2p(2)       generale(2)  // v2p VS generale
 
−
 
 
−
sono p       sono p
 
−
sono p       sono p
 
−
sono q       sono q
 
−
sono q       sono p
 
−
sono p       sono q
 
−
sono q       sono q
 
−
 
 
−
/* con la stessa sequenza di avvicendamento dei processi possiamo notare che l'output generato da entrambi
 
−
i processi è diverso e quindi i semafori v2p non hanno lo stesso potere espressivo dei semafori generali */
 
−
 
 
−
</syntaxhighlight>
 
−
<h2> Esercizio g.1</h2>
 
−
 
 
−
<p> <b>PUNTO A:</b> (7+256+(256^2)+(256^3))*1kb =16.843.015kb quindi approssimativamente 16MB</p>
 
−
<p> <b> PUNTO B:</B> blocco indiretto triplo -> primo livello di idirizzamento 256 esimo blocco -> secondo livello di indirizzamento 256 esimo blocco -> terzo livello di indirizzamento al blocco 100000. Qundi in totale 4 blocchi </p>
 

Latest revision as of 17:00, 19 May 2014

Testo del compito

Esercizio c.1

monitor eventp {
	typedef struct EP {
		unsigned int value;
		condition okNotNull;
		condition okToaAdd;
		intqueue q;
	} EP;
procedure entry EP* create (unsigned value){
	if (d.value+value > MAXINT || !d.queue.isEmpty()) {
		d.q.enqueue(value);
		d.okToAdd.wait();
		d.q.dequeue();
	}
	d.value = d.value + value;
	if (d.q.top() + value <= d.value.size()) //se il suo valore proposto non causa l’overflow del counter, sblocco lo scrittore successivo
			d.okToAdd.signal();
	else
		d.okNotNull.signal();
}

procedure entry unsigned int read (EP* ep){
	if (!ep.value)
		ep.okNotNull.wait();
	unsigned int toReturn = ep.value;
	ep.value = 0;
	ep.okToAdd.signal();
	return toReturn;
}

procedure entry close(EP * ep){
	free(ep);
}

}

Esercizio g.1

PUNTO A: (7+256+(256^2)+(256^3))*1kb =16.843.015kb quindi approssimativamente 16MB

PUNTO B: blocco indiretto triplo -> primo livello di idirizzamento 256 esimo blocco -> secondo livello di indirizzamento 256 esimo blocco -> terzo livello di indirizzamento al blocco 100000. Qundi in totale 4 blocchi

Esercizio g.2

Holt.png


<syntaxhighlight lang="C"> monitor eventp { typedef struct EP { unsigned int value; condition okNotNull; condition okToAdd; intqueue q; } }

procedure entry EP* create(unsigned value) { EP *ep = new EP(value); eps.enqueu(ep); return ep; }

procedure entry write(EP *d,unsigned value) { if(d.value+value > d.value.size()|| !d.q.empty()) { d.q.enqueue(value); d.okToAdd.wait(); d.q.dequeue(); } d.value = d.value + value; if (d.q.top()+value <= d.value.size()) d.okToAdd.signal(); else d.okNotNull.signal(); }

// MAXINT - currentvalue < value procedure entry unsigned int read(EP *ep) { if(!ep.value) ep.okNotNull.wait(); unsigned int toReturn = ep.value; ep.value = 0; ep.okToAdd.signal(); return toReturn; } <syntaxhighlight>

Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=ProvaTeorica_2013.05.30&oldid=742"