Difference between revisions of "ProvaTeorica 2012.05.24"
Jump to navigation
Jump to search
(19 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
<h1>http://www.cs.unibo.it/~renzo/so/compiti/2012-05-24.tot.pdf</h1> | <h1>http://www.cs.unibo.it/~renzo/so/compiti/2012-05-24.tot.pdf</h1> | ||
+ | <syntaxhighlight lang="C"> | ||
+ | monitor santuario | ||
+ | { | ||
+ | #define ANDATA 0 | ||
+ | #define RITORNO 1 | ||
+ | condition oktoenterponte, oktoexitponte ; | ||
+ | int waiting, crossing, medita ; | ||
+ | |||
+ | procedure entry enterponte(ANDATA) | ||
+ | { | ||
+ | |||
+ | if ( crssing(ritorno) > = 0 || crossing(ANDATA) > maxSantuario || waiting (RITORNO)>0 ) # per evitare deadlock | ||
+ | # deve essere maxSantuario >= maxPonte | ||
+ | waiting (ANDATA)++ ; # crossing(ANDATA) >= maxSantuario | ||
+ | oktoenterponte(ANDATA).wait(); | ||
+ | waiting(ANDATA)-- ; | ||
+ | crossing(ANDATA)++ ; | ||
+ | } | ||
+ | |||
+ | procedure entry exitponte(ANDATA) # Entra nel santuario | ||
+ | { | ||
+ | if ( medita == maxSantuario ) | ||
+ | oktoexitponte(ANDATA).wait() ; | ||
+ | crossing(ANDATA)--; | ||
+ | medita++ ; | ||
+ | if (waiting(RITORNO) > 0 ) && (crossing(ANDATA)==0) | ||
+ | oktoenterponte(RITORNO).signal(); | ||
+ | oktoenterponte(ANDATA).signal(); | ||
+ | } | ||
+ | |||
+ | rocedure entry enterponte(RITORNO) # Esci dal santuario | ||
+ | { | ||
+ | if (crossing(ANDATA)>0 || crossing(RTORNO) >= maxPonte) | ||
+ | wiiting(RITORNO)++; | ||
+ | oktoenterponte(RITORNO).wait(); | ||
+ | waiting(RITORNO)--; | ||
+ | medita--; | ||
+ | crossing(RITORNO)++; | ||
+ | } | ||
+ | |||
+ | procedure entry exitponte(RITORNO) | ||
+ | { | ||
+ | crossing(RITORNO)--; | ||
+ | if (waiting(RITORNO)>0) | ||
+ | oktoexitponte(RITORNO).signal() | ||
+ | oktoenterponte(ANDATA).signal() ; | ||
+ | } | ||
+ | } | ||
+ | /* Correggetemi se sbaglio. | ||
− | + | STARVATION : non l'ho individuata. | |
− | + | Io penso che se al santuario recitassero tutti il rosario e confessassero molti peccati, allora si. | |
− | + | DEADLOCK : se la portata del ponte era piu' grande della portata del santuario si aveva deadlock. | |
− | + | L'ho eliminato mettendo in wait se crossing(ANDATA) > maxSantuario | |
*/ | */ | ||
+ | save | ||
+ | </syntaxhighlight> | ||
+ | <syntaxhighlight lang="C"> | ||
monitor santuario | monitor santuario | ||
{ | { | ||
− | + | Go = 0; // andare al santuario | |
− | + | Back = 1; // tornare indietro | |
− | + | condition ok[2]; // 2 condizioni | |
− | + | crossing[2] = {0, 0}; // numero di persone sul ponte | |
− | + | visiting = 0; // numero di persone nel santuario | |
− | + | waiting[2] = {0, 0}; // numero di persone in attesa | |
− | |||
− | procedure entry entraponte( | + | procedure entry entraponte(dir) |
{ | { | ||
− | // [ | + | /* Mi blocco se: |
− | + | - il numero di persone sul ponte ha raggiunto il massimo; oppure | |
+ | - la direzione e' il santuario e il numero di visitatori | ||
+ | (compresi quelli che stanno raggiungendo il santuario) ha raggiunto il massimo; oppure | ||
+ | - qualcuno sta attraversando il ponte in direzione opposta; oppure | ||
+ | - qualcuno sta attendendo di attraversare nel senso opposto */ | ||
+ | if (crossing[dir] == MAXPONTE || | ||
+ | (dir == Go && visiting + crossing[dir] == MAXSANTUARIO) || | ||
+ | crossing[1 - dir] > 0 || | ||
+ | waiting[1 - dir] > 0) | ||
{ | { | ||
− | / | + | waiting[dir]++; |
− | + | ok[dir].wait(); | |
− | + | waiting[dir]--; | |
− | if ( | + | } |
− | + | crossing[dir]++; | |
− | + | ||
− | + | if (dir == Back) | |
− | + | visiting--; | |
− | + | } | |
+ | |||
+ | procedure entry esciponte(dir) | ||
+ | { | ||
+ | crossing[dir]--; | ||
+ | |||
+ | if (dir == Go) | ||
+ | visiting++; | ||
+ | |||
+ | // [Case 1] Nessuno sta attraversando il ponte | ||
+ | if (crossing[dir] == 0) | ||
+ | ok[1 - dir].signal(); | ||
+ | // [Case 2] Qualcuno sta attraversando il ponte | ||
+ | else | ||
+ | ok[dir].signal(); | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | -TomOgn | ||
+ | |||
+ | |||
+ | <syntaxhighlight lang="C"> | ||
+ | monitor santuario{ | ||
+ | #define ANDATA 0 | ||
+ | #define RITORNO 1 | ||
+ | |||
+ | int waiting[2]; | ||
+ | int crossing[2]; | ||
+ | condition oktoenter[2]; | ||
+ | int count; /* persone dentro al santuario */ | ||
+ | |||
+ | procedure entry entraponte(int dir){ | ||
+ | if (dir == ANDATA){ | ||
+ | if (crossing[1-dir] > 0 || crossing[dir] >= MAXPONTE || cout+crossing[dir] >= MAXSANTUARIO){ | ||
+ | waiting[dir]++; | ||
+ | oktoenter[dir].wait(); | ||
+ | waiting[dir]--; | ||
+ | } | ||
+ | } | ||
+ | else { | ||
+ | if (crossing[1-dir] > 0 || crossing[dir] >= MAXPONTE){ | ||
+ | waiting[dir]++; | ||
+ | oktoenter[dir].wait(); | ||
+ | waiting[dir]--; | ||
} | } | ||
− | |||
− | |||
} | } | ||
− | // [ | + | crossing[dir]++; |
+ | if ((crossing[dir]+count < MAXSANTUARIO) && crossing[dir] < MAXPONTE) | ||
+ | oktoenter[dir].signal(); | ||
+ | } | ||
+ | |||
+ | procedure entry esciponte(int dir){ | ||
+ | crossing[dir]--; | ||
+ | if (dir == ANDATA){ | ||
+ | count++; | ||
+ | if (count+crossing[dir] < MAXSANTUARIO) /* voi che siete in attesa andate sul ponte */ | ||
+ | oktoenter[dir].signal(); | ||
+ | } | ||
else | else | ||
− | + | count--; | |
− | + | ||
− | + | if (crossing[dir] == 0) | |
− | + | oktoenter[1-dir].signal(); | |
− | + | } | |
− | if ( | + | } |
− | + | </syntaxhighlight> | |
− | // | + | Gabriele & Giulia (se non va colpa di Gabriele) |
− | + | ||
− | + | ||
− | + | ||
+ | |||
+ | |||
+ | <syntaxhighlight lang="C"> | ||
+ | |||
+ | monitor santuario{ | ||
+ | int CurrentDir /* 0 = arriving , 1 = leaving */ | ||
+ | int crossing | ||
+ | condition oktoenter | ||
+ | condition oktoleave | ||
+ | //queue enter | ||
+ | //queue ponte | ||
+ | //queue leave | ||
+ | int fidelis /* fedeli nel tempio */ | ||
+ | |||
+ | procedure entry entraponte(CrossingDir){ | ||
+ | if(CrossingDir != CurrentDir){ | ||
+ | if(CrossingDir == 0){ | ||
+ | //enter.enqueue() | ||
+ | oktoenter.wait() | ||
+ | //enter.dequeue() | ||
+ | } | ||
+ | if(CrossingDir == 1){ | ||
+ | //leave.enqueue() | ||
+ | oktoleave.wait() | ||
+ | //leave.dequeue() | ||
+ | } | ||
+ | } | ||
+ | if(CrossingDir == 0){ | ||
+ | if(fidelis == MAXSANTUARIO || crossing == MAXPONTE){ | ||
+ | //ponte.enqueue() | ||
+ | oktoenter.wait() | ||
+ | //ponte.dequeue() | ||
+ | } | ||
+ | fidelis++ | ||
+ | crossing++ | ||
+ | } | ||
+ | if(CrossingDir == 1){ | ||
+ | if(crossing == MAXPONTE){ | ||
+ | //ponte.enqueue() | ||
+ | oktoleave.wait() | ||
+ | //ponte.dequeue() | ||
} | } | ||
− | + | fidelis-- | |
+ | crossing++ | ||
} | } | ||
} | } | ||
− | + | precedure entry esciponte(CrossingDir){ | |
− | + | crossing-- | |
− | + | if(crossing == 0){ | |
− | + | if(CrossingDir == 0){ | |
− | if ( | + | if(fidelis < MAXSANTUARIO /*&& !enter.isempty()*/){ |
− | + | oktoenter.signal() | |
− | + | } | |
− | + | else{ | |
− | + | CurrentDir = 1 - CurrentDir | |
− | + | oktoleave.signal() | |
− | + | } | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | else | ||
− | |||
} | } | ||
− | + | else{ | |
− | else | + | CurrentDir = 1 - CurrentDir |
− | + | oktoenter.signal() | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
} | } | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | |||
+ | santuario{ | ||
+ | crossing = 0 | ||
+ | CurrentDir = 0 | ||
+ | fidelis = 0 | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | Fede & Mirko | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | <syntaxhighlight lang="C"> | ||
+ | |||
+ | |||
+ | monitor santuario { | ||
+ | condition okpassa; // vai sul ponte secondo metodo FIFO | ||
+ | int turn=2; // turno di attraversamento | ||
+ | int visitatori[2]; // contatori andata ritorno | ||
+ | visitatori[0]=0; | ||
+ | visitatori[1]=0; | ||
+ | int fedeli=0; | ||
+ | int i=0; | ||
+ | Queue q; // coda dei visitatori in attesa | ||
+ | |||
+ | procedure entry entraponte(dir){ | ||
+ | /* se il turno è della direzione opposta o | ||
+ | i visitatori in transito sono MAXPONTE o | ||
+ | la coda non è vuota aspetta */ | ||
+ | if( (dir==0 && fedeli==MAXSANTUARIO ) || turn==(1-dir) || visitatori[dir]==MAXPONTE || !q.empty()){ | ||
+ | q.enqueue(dir); // inserisci in coda | ||
+ | okpassa.wait(); // aspetta | ||
+ | if( q.head()==dir && (visitatori[dir] + i) < (MAXPONTE - 1) ){ // questa condizione | ||
+ | i++; | ||
+ | q.dequeue(); // mi serve per far passare | ||
+ | okpassa.signal(); // MAXPONTE visitatori nella direzione | ||
+ | } // in attesa quando nella direzione opposta | ||
+ | i=0; // i visitatori in transito erano N | ||
+ | } | ||
+ | turn=dir; // setto il turno della direzione | ||
+ | visitatori[dir]++; //incremento visitatori in transito | ||
+ | if(dir==0){fedeli++;} | ||
+ | if(dir==1){fedeli--;} | ||
+ | } | ||
+ | |||
+ | |||
+ | procedure entry esciponte(dir){ | ||
+ | visitatore[dir]--; //decremento visitatori in transito | ||
+ | /* se il primo visitatore in attesa va nella stessa direzione | ||
+ | di chi è uscito può entrare sul ponte poichè questo | ||
+ | si verifica solo se il visitatore uscito era il numero N | ||
+ | o il visitatore che esce è l'ultimo fa passare il primo in attesa | ||
+ | che sarà sicuramente della direzione opposta */ | ||
+ | primo = (dir == 0 && fedeli < MAXSANTUARIO) && ( q.head()==0 || visitatori[0]==0 )) | ||
+ | secondo = (dir == 1 && (q.head()==0 || visitatori[1]==0 ) | ||
+ | |||
+ | if(primo || secondo){ | ||
+ | if(visitatore[dir]==0){ | ||
+ | turn=2; // ponte vuoto | ||
+ | } | ||
+ | q.dequeue(); | ||
+ | okpassa.signal(); // causa il passaggio sul ponte | ||
+ | // del primo visitatore in attesa | ||
+ | // (secondo una politica FIFO) | ||
+ | } | ||
+ | |||
+ | } | ||
+ | |||
+ | </syntaxhighlight> | ||
+ | Alessandro | ||
+ | |||
+ | <syntaxhighlight lang="C"> | ||
+ | #define ANDARA 0; | ||
+ | #define RITORNO 1; | ||
+ | monitor santuario{ | ||
+ | int cross; | ||
+ | condition oktocross[2]; | ||
+ | int fidelis; | ||
+ | entraponte(dir){ | ||
+ | if( cross != 0 || (dir == 0 && MAXSANTUARIO == fidelis)){ | ||
+ | wait[dir]++; | ||
+ | oktocross[dir].wait(); | ||
+ | wait[dir]--; | ||
+ | } | ||
+ | cross++; | ||
+ | if(dir == 0){ | ||
+ | fidelis++; | ||
+ | if(cross < MAXPONTE && MAXSANTUARIO > fidelis){ | ||
+ | oktocross[dir].signal; | ||
+ | } | ||
+ | }else{ | ||
+ | fidelis--; | ||
+ | if(cross < MAXPONTE){ | ||
+ | oktocross[dir].signal; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | esciponte(dir){ | ||
+ | cross--; | ||
+ | if(cross == 0 && MAXSANTUARIO == fidelis){ | ||
+ | oktocross[RITORNO].signal(); | ||
+ | }else if(cross == 0 && wait[1-dir]){ | ||
+ | oktocross[1-dir].signal(); | ||
+ | }else if(cross == 0){ | ||
+ | oktocross[dir].signal(); | ||
} | } | ||
} | } | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | -Midolo |
Latest revision as of 19:05, 1 June 2014
http://www.cs.unibo.it/~renzo/so/compiti/2012-05-24.tot.pdf
monitor santuario
{
#define ANDATA 0
#define RITORNO 1
condition oktoenterponte, oktoexitponte ;
int waiting, crossing, medita ;
procedure entry enterponte(ANDATA)
{
if ( crssing(ritorno) > = 0 || crossing(ANDATA) > maxSantuario || waiting (RITORNO)>0 ) # per evitare deadlock
# deve essere maxSantuario >= maxPonte
waiting (ANDATA)++ ; # crossing(ANDATA) >= maxSantuario
oktoenterponte(ANDATA).wait();
waiting(ANDATA)-- ;
crossing(ANDATA)++ ;
}
procedure entry exitponte(ANDATA) # Entra nel santuario
{
if ( medita == maxSantuario )
oktoexitponte(ANDATA).wait() ;
crossing(ANDATA)--;
medita++ ;
if (waiting(RITORNO) > 0 ) && (crossing(ANDATA)==0)
oktoenterponte(RITORNO).signal();
oktoenterponte(ANDATA).signal();
}
rocedure entry enterponte(RITORNO) # Esci dal santuario
{
if (crossing(ANDATA)>0 || crossing(RTORNO) >= maxPonte)
wiiting(RITORNO)++;
oktoenterponte(RITORNO).wait();
waiting(RITORNO)--;
medita--;
crossing(RITORNO)++;
}
procedure entry exitponte(RITORNO)
{
crossing(RITORNO)--;
if (waiting(RITORNO)>0)
oktoexitponte(RITORNO).signal()
oktoenterponte(ANDATA).signal() ;
}
}
/* Correggetemi se sbaglio.
STARVATION : non l'ho individuata.
Io penso che se al santuario recitassero tutti il rosario e confessassero molti peccati, allora si.
DEADLOCK : se la portata del ponte era piu' grande della portata del santuario si aveva deadlock.
L'ho eliminato mettendo in wait se crossing(ANDATA) > maxSantuario
*/
save
monitor santuario
{
Go = 0; // andare al santuario
Back = 1; // tornare indietro
condition ok[2]; // 2 condizioni
crossing[2] = {0, 0}; // numero di persone sul ponte
visiting = 0; // numero di persone nel santuario
waiting[2] = {0, 0}; // numero di persone in attesa
procedure entry entraponte(dir)
{
/* Mi blocco se:
- il numero di persone sul ponte ha raggiunto il massimo; oppure
- la direzione e' il santuario e il numero di visitatori
(compresi quelli che stanno raggiungendo il santuario) ha raggiunto il massimo; oppure
- qualcuno sta attraversando il ponte in direzione opposta; oppure
- qualcuno sta attendendo di attraversare nel senso opposto */
if (crossing[dir] == MAXPONTE ||
(dir == Go && visiting + crossing[dir] == MAXSANTUARIO) ||
crossing[1 - dir] > 0 ||
waiting[1 - dir] > 0)
{
waiting[dir]++;
ok[dir].wait();
waiting[dir]--;
}
crossing[dir]++;
if (dir == Back)
visiting--;
}
procedure entry esciponte(dir)
{
crossing[dir]--;
if (dir == Go)
visiting++;
// [Case 1] Nessuno sta attraversando il ponte
if (crossing[dir] == 0)
ok[1 - dir].signal();
// [Case 2] Qualcuno sta attraversando il ponte
else
ok[dir].signal();
}
}
-TomOgn
monitor santuario{
#define ANDATA 0
#define RITORNO 1
int waiting[2];
int crossing[2];
condition oktoenter[2];
int count; /* persone dentro al santuario */
procedure entry entraponte(int dir){
if (dir == ANDATA){
if (crossing[1-dir] > 0 || crossing[dir] >= MAXPONTE || cout+crossing[dir] >= MAXSANTUARIO){
waiting[dir]++;
oktoenter[dir].wait();
waiting[dir]--;
}
}
else {
if (crossing[1-dir] > 0 || crossing[dir] >= MAXPONTE){
waiting[dir]++;
oktoenter[dir].wait();
waiting[dir]--;
}
}
crossing[dir]++;
if ((crossing[dir]+count < MAXSANTUARIO) && crossing[dir] < MAXPONTE)
oktoenter[dir].signal();
}
procedure entry esciponte(int dir){
crossing[dir]--;
if (dir == ANDATA){
count++;
if (count+crossing[dir] < MAXSANTUARIO) /* voi che siete in attesa andate sul ponte */
oktoenter[dir].signal();
}
else
count--;
if (crossing[dir] == 0)
oktoenter[1-dir].signal();
}
}
Gabriele & Giulia (se non va colpa di Gabriele)
monitor santuario{
int CurrentDir /* 0 = arriving , 1 = leaving */
int crossing
condition oktoenter
condition oktoleave
//queue enter
//queue ponte
//queue leave
int fidelis /* fedeli nel tempio */
procedure entry entraponte(CrossingDir){
if(CrossingDir != CurrentDir){
if(CrossingDir == 0){
//enter.enqueue()
oktoenter.wait()
//enter.dequeue()
}
if(CrossingDir == 1){
//leave.enqueue()
oktoleave.wait()
//leave.dequeue()
}
}
if(CrossingDir == 0){
if(fidelis == MAXSANTUARIO || crossing == MAXPONTE){
//ponte.enqueue()
oktoenter.wait()
//ponte.dequeue()
}
fidelis++
crossing++
}
if(CrossingDir == 1){
if(crossing == MAXPONTE){
//ponte.enqueue()
oktoleave.wait()
//ponte.dequeue()
}
fidelis--
crossing++
}
}
precedure entry esciponte(CrossingDir){
crossing--
if(crossing == 0){
if(CrossingDir == 0){
if(fidelis < MAXSANTUARIO /*&& !enter.isempty()*/){
oktoenter.signal()
}
else{
CurrentDir = 1 - CurrentDir
oktoleave.signal()
}
}
else{
CurrentDir = 1 - CurrentDir
oktoenter.signal()
}
}
}
santuario{
crossing = 0
CurrentDir = 0
fidelis = 0
}
}
Fede & Mirko
monitor santuario {
condition okpassa; // vai sul ponte secondo metodo FIFO
int turn=2; // turno di attraversamento
int visitatori[2]; // contatori andata ritorno
visitatori[0]=0;
visitatori[1]=0;
int fedeli=0;
int i=0;
Queue q; // coda dei visitatori in attesa
procedure entry entraponte(dir){
/* se il turno è della direzione opposta o
i visitatori in transito sono MAXPONTE o
la coda non è vuota aspetta */
if( (dir==0 && fedeli==MAXSANTUARIO ) || turn==(1-dir) || visitatori[dir]==MAXPONTE || !q.empty()){
q.enqueue(dir); // inserisci in coda
okpassa.wait(); // aspetta
if( q.head()==dir && (visitatori[dir] + i) < (MAXPONTE - 1) ){ // questa condizione
i++;
q.dequeue(); // mi serve per far passare
okpassa.signal(); // MAXPONTE visitatori nella direzione
} // in attesa quando nella direzione opposta
i=0; // i visitatori in transito erano N
}
turn=dir; // setto il turno della direzione
visitatori[dir]++; //incremento visitatori in transito
if(dir==0){fedeli++;}
if(dir==1){fedeli--;}
}
procedure entry esciponte(dir){
visitatore[dir]--; //decremento visitatori in transito
/* se il primo visitatore in attesa va nella stessa direzione
di chi è uscito può entrare sul ponte poichè questo
si verifica solo se il visitatore uscito era il numero N
o il visitatore che esce è l'ultimo fa passare il primo in attesa
che sarà sicuramente della direzione opposta */
primo = (dir == 0 && fedeli < MAXSANTUARIO) && ( q.head()==0 || visitatori[0]==0 ))
secondo = (dir == 1 && (q.head()==0 || visitatori[1]==0 )
if(primo || secondo){
if(visitatore[dir]==0){
turn=2; // ponte vuoto
}
q.dequeue();
okpassa.signal(); // causa il passaggio sul ponte
// del primo visitatore in attesa
// (secondo una politica FIFO)
}
}
Alessandro
#define ANDARA 0;
#define RITORNO 1;
monitor santuario{
int cross;
condition oktocross[2];
int fidelis;
entraponte(dir){
if( cross != 0 || (dir == 0 && MAXSANTUARIO == fidelis)){
wait[dir]++;
oktocross[dir].wait();
wait[dir]--;
}
cross++;
if(dir == 0){
fidelis++;
if(cross < MAXPONTE && MAXSANTUARIO > fidelis){
oktocross[dir].signal;
}
}else{
fidelis--;
if(cross < MAXPONTE){
oktocross[dir].signal;
}
}
}
esciponte(dir){
cross--;
if(cross == 0 && MAXSANTUARIO == fidelis){
oktocross[RITORNO].signal();
}else if(cross == 0 && wait[1-dir]){
oktocross[1-dir].signal();
}else if(cross == 0){
oktocross[dir].signal();
}
}
}
-Midolo