Difference between revisions of "ProvaPratica 2010.07.12"

From Sistemi Operativi
Jump to navigation Jump to search
 
(26 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
<h1>http://www.cs.unibo.it/~renzo/so/compiti/2010-07-12.tot.pdf</h1>
 
<h1>http://www.cs.unibo.it/~renzo/so/compiti/2010-07-12.tot.pdf</h1>
  
 +
 +
== Esercizio 1 ==
  
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
 +
int aggiorna_maxprio(int maxprio,int prio,int waiting[]){
 +
int i;
 +
if(waiting[maxprio] == 0)
 +
{
 +
      maxprio=0;
 +
for(i=prio;i>=0;i--)
 +
{
 +
if(waiting[i]!=0)
 +
{
 +
maxprio=i;
 +
break;
 +
}
 +
}
 +
return maxprio;
 +
}
 +
  
 
monitor priocoop{
 
monitor priocoop{
−
condition run[9];
+
condition run[10];
−
int waiting[9]=0,0,0,0,0,0,0,0,0;
+
int waiting[10]=0,0,0,0,0,0,0,0,0,0;
 
int maxprio=0;
 
int maxprio=0;
 
int occupato=0;
 
int occupato=0;
Line 20: Line 38:
 
run[prio].wait();
 
run[prio].wait();
 
waiting[prio]--;
 
waiting[prio]--;
 +
maxprio=aggiorna_maxprio(maxprio,prio,waiting);
 
}
 
}
 
occupato=1;
 
occupato=1;
Line 33: Line 52:
 
run[prio].wait();
 
run[prio].wait();
 
waiting[prio]--;
 
waiting[prio]--;
 +
maxprio=aggiorna_maxprio(maxprio,prio,waiting);
 
}
 
}
  
 
procedure entry fini(prio){
 
procedure entry fini(prio){
−
int i;
 
 
occupato=0;
 
occupato=0;
 
waiting[prio]--;
 
waiting[prio]--;
−
if(waiting[maxprio] == 0)
+
maxprio=aggiorna_maxprio(maxprio,prio,waiting);
−
{
+
run[maxprio].signal();
−
maxprio=0;
 
−
for(i=prio;i>=0;i--)
 
−
{
 
−
if(waiting[i]!=0)
 
−
{
 
−
maxprio=0;
 
−
}
 
−
}
 
−
run[maxprio].signal();
 
−
}
 
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
Line 62: Line 71:
 
condition oktogo[10];
 
condition oktogo[10];
 
int wait[10] = 0,0,0,0,0,0,0,0,0;
 
int wait[10] = 0,0,0,0,0,0,0,0,0;
−
int waits = 0;
+
int running;
−
int running = 0;
 
−
 
 
 
priocoop.init(prio) {
 
priocoop.init(prio) {
−
if(running != 0 || waits !=0 ) {
+
if(running != 0) {
 
wait[prio]++;
 
wait[prio]++;
−
waits++;
 
 
oktogo[prio].wait;
 
oktogo[prio].wait;
−
waits--;
 
 
wait[prio]--;
 
wait[prio]--;
 
}
 
}
Line 79: Line 84:
 
priocoop.yield(prio) {
 
priocoop.yield(prio) {
 
running--;
 
running--;
−
if(waits != 0) {
+
for(int i = 0;i<10;i++) {
−
for(int i = 0;i<10;i++) {
+
if(wait[i] != 0) {
−
if(wait[i] != 0) {
+
oktogo[i].signal();
−
oktogo[i].signal();
+
wait[prio]++;
−
wait[prio]++;
+
oktogo[prio].wait;
−
waits++;
+
wait[prio]--;
−
oktogo[prio].wait;
+
break();
−
waits--;
 
−
wait[prio]--;
 
−
break();
 
−
}
 
 
}
 
}
 
}
 
}
Line 97: Line 98:
 
priocoop.fini() {
 
priocoop.fini() {
 
running--;
 
running--;
−
if(waits != 0) {
+
for(int i = 0;i<10;i++) {
−
for(int i = 0;i<10;i++) {
+
if(wait[i] != 0) {
−
if(wait[i] != 0) {
+
oktogo[i].signal();
−
oktogo[i].signal();
+
break();
−
break();
 
−
}
 
 
}
 
}
 
}
 
}
 +
 +
}
 +
}
 +
</syntaxhighlight>
 +
-Midolo
 +
 +
 +
 +
<syntaxhighlight lang="C">
 +
//0: priorita' maggiore
 +
//9: priorita' minore
 +
cond oktoenter[10];
 +
int count[10];
 +
bool running = false;
 +
 +
//restituisce la priorita' maggiore che ha un processo in attesa
 +
getprio() {
 +
      for(i=0;i<10;i++) {
 +
if(count[i]>0)
 +
break;
 +
}
 +
return i;
 +
}
 +
 +
priocoop() {
 +
init (prio) {
 +
if (running) {
 +
count[prio]++;
 +
oktoenter[prio].wait();
 +
count[prio]--;
 +
}
 +
running = true;
 +
}
 +
yield(prio) {
 +
i=getprio();
 +
if (i < 10) {
 +
// running = false;
 +
oktoenter[i].signal();
 +
count(prio)++
 +
oktoenter[proc].wait();
 +
                // running = true;
 +
                count[prio]--;
 +
}
 +
}
 +
fini(prio){
 +
i=getprio();
 +
if(i<10)
 +
oktoenter[i].signal;
 +
else
 +
running=false;
 +
}
 +
}
 +
</syntaxhighlight>
 +
-Stefano B.
 +
 +
 +
 +
----
 +
 +
 +
<syntaxhighlight lang="C">
 +
monitor priocoop{
 +
condition oktoenter[10];
 +
queue waiting[10];
 +
 +
procedure entry init(int prio){
 +
if(!(prio >= 0 && prio<=9))
 +
exit(0);
 +
}
 +
 +
procedure entry yield(int prio){
 +
int priority=-1;
 +
for (i=0; i<10; i++) {
 +
if (! waiting[i].isempty())
 +
priority=i;
 +
}
 +
oktoenter[priority].signal();
 +
if(priority>=0){ /* se non ci fosse questo controllo avremmo un caso di deadlock
 +
  * in quanto le code sono vuote */
 +
waiting[prio].enqueue();
 +
oktoenter[prio].wait();
 +
waiting[prio].dequeue();
 +
}
 +
}
 +
 +
procedure entry fini(){
 +
int priority=-1;
 +
for (i=0; i<10; i++) {
 +
if (! waiting[i].isempty())
 +
priority=i;
 +
}
 +
oktoenter[priority].signal();
 +
}
 +
}
 +
</syntaxhighlight>
 +
Francesca e Giulia
 +
 +
== Esercizio 2 ==
 +
<syntaxhighlight lang="C">
 +
db.getpriortymax(); //funzione che restituisce il messaggio con prioritá maggiore e lo rimuove dal db o 0 nel caso il db sia vuoto
 +
Process n: {
 +
 +
psend(dest, prio,msg) {
 +
asend((msg, prio),dest);
 +
}
 +
 +
precv(sender) {
 +
while((msg,prio) = arecv(sender)) {
 +
db[sender].insert((msg,prio));
 +
}
 +
return (db[sender].getpriortymax());
 
}
 
}
 +
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 
-Midolo
 
-Midolo
 +
 +
 +
==Esercizio 3 ==
 +
<syntaxhighlight lang="C">
 +
lock=-1;
 +
 +
Process P[i]{
 +
while(true){
 +
  do{;}
 +
  while(twomult.op(lock)==lock);
 +
  //critical section
 +
  lock = -lock;
 +
  //no critical section
 +
}
 +
}
 +
</syntaxhighlight>
 +
 +
Inizialmente:  a=1;  b=1;
 +
 +
Primo processo:
 +
lock=-1  a=-1  b=1
 +
Siccome lock!=b esce dal while.
 +
 +
Secondo processo:
 +
lock=-1  a=1  b=-1
 +
Siccome lock==b non esce dal while e continua:
 +
lock=-1  a=1  b=-1
 +
Si ripeterano sempre gli stessi valori,
 +
fino al cambio di valore di lock che passa da
 +
-1 a 1  così :
 +
lock=1  a=-1  b=-1;
 +
Siccome lock!=b esce dal while.
 +
Mentre l'altro processo si bloccherà poichè:
 +
lock=1  a=1  b=1;
 +
fino al ritorno di lock al valore -1;
 +
lock=-1  a=-1  b=1;
 +
C.V.D
 +
 +
----Alessandro
 +
 +
<h1>Parte generale</h1>
 +
 +
== Esercizio 1 ==
 +
<syntaxhighlight lang="C">
 +
P1: 1ms IoR, 7ms CPU, 1ms IoW, 1ms IoR, 7ms CPU, 1ms IoW, 1ms IoR, 7ms CPU, 1ms IoW, 1ms IoR, 7ms CPU, 1ms IoW
 +
P2: 2ms IoR, 2ms CPU, 2ms IoW, 2ms IoR, 2ms CPU, 2ms IoW, 2ms IoR, 2ms CPU, 2ms IoW, 2ms IoR, 2ms CPU, 2ms IoW
 +
 +
time 1234567890123456789012345678901234567890
 +
CPU  111111122111111122111111122111111122
 +
IO  122    112222  112222  112222  1 22
 +
 +
time 1234567890123456789012345678901234567890
 +
CPU  11221111122111122111 2211111111  11111
 +
IO  122  2222 112222  22221122      11    1
 +
</syntaxhighlight>
 +
 +
== Esercizio 2 ==
 +
a) Lo stato è SAFE per x >= 8
 +
 +
Esempio di sequenza:
 +
 +
[[File:So1.png]]
 +
 +
COH valuta 2 = 20 → 15 → 30 → 0 → 30+x → 10+x → 32+x il seguito dipende dal valore di x
 +
 +
La sequenza è: 2 - 1 - 3 - 4
 +
 +
b1) con x = 8 e la sequenza: 2 - 4 si arriva in uno stato UNSAFE
 +
 +
b2) con x = 7 e la sequenza: 2 - 1 si è in uno stato SAFE
 +
 +
 +
Giulia N.

Latest revision as of 15:48, 9 April 2014

http://www.cs.unibo.it/~renzo/so/compiti/2010-07-12.tot.pdf


Esercizio 1

int aggiorna_maxprio(int maxprio,int prio,int waiting[]){
int i;
if(waiting[maxprio] == 0)
	{
       	maxprio=0;
		for(i=prio;i>=0;i--)
		{
			if(waiting[i]!=0)
			{
			maxprio=i;
			break;
			}
		}
return maxprio;
}


monitor priocoop{
condition run[10];
int waiting[10]=0,0,0,0,0,0,0,0,0,0;
int maxprio=0;
int occupato=0;

procedure entry init(prio){	
	if(occupato==1)
	{
		if(maxprio < prio)
		{
		maxprio=prio;
		}
	waiting[prio]++;			
	run[prio].wait();
	waiting[prio]--;
	maxprio=aggiorna_maxprio(maxprio,prio,waiting);
	}
occupato=1;
}

procedure entry yield(prio){
run[maxprio].signal();
        if(maxprio < prio)
	{
	maxprio=prio;
	}
waiting[prio]++;
run[prio].wait();
waiting[prio]--;
maxprio=aggiorna_maxprio(maxprio,prio,waiting);
}

procedure entry fini(prio){
occupato=0;
waiting[prio]--;
maxprio=aggiorna_maxprio(maxprio,prio,waiting);		
run[maxprio].signal();
}

Alessandro 


//Processo con prioritá 0 = Processo con piú alta prioritá
//Processo con prioritá 9 = Processo con meno prioritá
monitor priocoop {
	condition oktogo[10];
	int wait[10] = 0,0,0,0,0,0,0,0,0;
	int running;
	priocoop.init(prio) {
		if(running != 0) {
			wait[prio]++;
			oktogo[prio].wait;
			wait[prio]--;
		}

		running++;
	}

	priocoop.yield(prio) {
		running--;
		for(int i = 0;i<10;i++) {
			if(wait[i] != 0) {
				oktogo[i].signal();
				wait[prio]++;
				oktogo[prio].wait;
				wait[prio]--;
				break();
			}
		}
		running++;
	}

	priocoop.fini() {
		running--;
		for(int i = 0;i<10;i++) {
			if(wait[i] != 0) {
				oktogo[i].signal();
				break();
			}
		}

	}
}

-Midolo 


//0: priorita' maggiore
//9: priorita' minore
cond oktoenter[10];
int count[10];
bool running = false;

//restituisce la priorita' maggiore che ha un processo in attesa
getprio() {
      	for(i=0;i<10;i++) {
		 if(count[i]>0)
			 break;
	 }
	 return i;
}

priocoop() {
	init (prio) {
		if (running) {
			count[prio]++;
			oktoenter[prio].wait();
			count[prio]--;
		}
		running = true;
	}
	yield(prio) {
		i=getprio();
		if (i < 10) {
			// running = false; 
			oktoenter[i].signal();
			count(prio)++
			oktoenter[proc].wait();
	                // running = true;
        	        count[prio]--;
		}
	}
	fini(prio){
		i=getprio();
		if(i<10)
			oktoenter[i].signal;
		else
			running=false;
	}
}

-Stefano B. 



monitor priocoop{
	condition oktoenter[10];
	queue waiting[10];
	
	procedure entry init(int prio){
		if(!(prio >= 0 && prio<=9))
			exit(0);
	}
	
	procedure entry yield(int prio){
		int priority=-1;
		for (i=0; i<10; i++) {
			if (! waiting[i].isempty())
				priority=i;
		}
		oktoenter[priority].signal();
		if(priority>=0){ /* se non ci fosse questo controllo avremmo un caso di deadlock
						  * in quanto le code sono vuote */
			waiting[prio].enqueue();
			oktoenter[prio].wait();
			waiting[prio].dequeue(); 
		}
	}
	
	procedure entry fini(){
		int priority=-1;
		for (i=0; i<10; i++) {
			if (! waiting[i].isempty())
				priority=i;
		}
		oktoenter[priority].signal();
	}
}

Francesca e Giulia

Esercizio 2

db.getpriortymax(); //funzione che restituisce il messaggio con prioritá maggiore e lo rimuove dal db o 0 nel caso il db sia vuoto
Process n: {

	psend(dest, prio,msg) {
		asend((msg, prio),dest);
	}

	precv(sender) {
		while((msg,prio) = arecv(sender)) {
			db[sender].insert((msg,prio));
		}
		return (db[sender].getpriortymax());
	}

}

-Midolo


Esercizio 3

lock=-1;

Process P[i]{
while(true){
  do{;}
  while(twomult.op(lock)==lock);
  //critical section
  lock = -lock;
  //no critical section
}
}

Inizialmente: a=1; b=1;

Primo processo: lock=-1 a=-1 b=1 Siccome lock!=b esce dal while.

Secondo processo: lock=-1 a=1 b=-1 Siccome lock==b non esce dal while e continua: lock=-1 a=1 b=-1 Si ripeterano sempre gli stessi valori, fino al cambio di valore di lock che passa da -1 a 1 così : lock=1 a=-1 b=-1; Siccome lock!=b esce dal while. Mentre l'altro processo si bloccherà poichè: lock=1 a=1 b=1; fino al ritorno di lock al valore -1; lock=-1 a=-1 b=1; C.V.D

Alessandro

Parte generale

Esercizio 1

P1: 1ms IoR, 7ms CPU, 1ms IoW, 1ms IoR, 7ms CPU, 1ms IoW, 1ms IoR, 7ms CPU, 1ms IoW, 1ms IoR, 7ms CPU, 1ms IoW
P2: 2ms IoR, 2ms CPU, 2ms IoW, 2ms IoR, 2ms CPU, 2ms IoW, 2ms IoR, 2ms CPU, 2ms IoW, 2ms IoR, 2ms CPU, 2ms IoW

time 1234567890123456789012345678901234567890
CPU   111111122111111122111111122111111122
IO   122     112222   112222   112222   1 22

time 1234567890123456789012345678901234567890
CPU   11221111122111122111 2211111111  11111
IO   122  2222 112222  22221122      11     1

Esercizio 2

a) Lo stato è SAFE per x >= 8

Esempio di sequenza:

So1.png

COH valuta 2 = 20 → 15 → 30 → 0 → 30+x → 10+x → 32+x il seguito dipende dal valore di x

La sequenza è: 2 - 1 - 3 - 4

b1) con x = 8 e la sequenza: 2 - 4 si arriva in uno stato UNSAFE

b2) con x = 7 e la sequenza: 2 - 1 si è in uno stato SAFE


Giulia N.

Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=ProvaPratica_2010.07.12&oldid=567"