Difference between revisions of "Prove scritte 2018"
Jump to navigation
Jump to search
| (2 intermediate revisions by the same user not shown) | |||
| Line 538: | Line 538: | ||
==== Soluzione "schiacciasassi" ==== | ==== Soluzione "schiacciasassi" ==== | ||
| − | + | visto da [https://t.me/llibera LiberaL] in data 2023/05/12, perchè nel primo if della V() si fa value >= - maxval? non dovrebbe essere + maxval? | |
<syntaxhighlight lang="java"> | <syntaxhighlight lang="java"> | ||
Latest revision as of 16:00, 12 May 2023
Esame 19/09/2018
Esercizio c.2 (da controllare)
- Controllato dall'utente ? in data ?
- ...
Nello pseudocodice seguente, il termine this fa riferimento al processo corrente, mentre ANY ad uno qualunque.
stack<message> messages;
void lifo_send(string m, process dest) {
do {
asend(m, dest);
} while (areceive(dest).text != "ACK");
}
message lifo_receive(process source) {
if (source != ANY) {
message m = areceive(source);
asend("ACK", source);
return m;
} else {
message m;
asend("END", this);
m = areceive(ANY);
while (m.text != "END" || m.sender != this) {
messages.push(m);
asend("ACK", m.sender);
m = areceive(ANY);
}
/* Bisogna tenere conto dei casi in cui lifo_receive() viene invocata quando nessun
* messaggio è stato ancora spedito da altri processi. In tal caso si attende il
* il primo e lo si restituisce.
*/
if (messages.empty()) {
m = areceive(ANY);
asend("ACK", m.sender);
return m;
} else {
return messages.pop();
}
}
}
Esame 17/07/2018
Esercizio c.1
A Bruxelles c'è un locale chiamato Delirium Café. Alla vigilia del FOSDEM tutti gli anni gli sviluppatori europei di software libero si ritrovano a bere birra (il locale è nel guinnes dei primati con più di duemila tipi di birra). Il prossimo appuntamento è fissato per il 1 febbraio 2019 ore 20. Numerosi sono i tipi di birra alla spina. I baristi (tanti) prendono gli ordini (es. mezza pinta, 1 o 2 pinte) e riempiono i bicchieri. Quando un fusto e' vuoto avvertono i magazzinieri che prendono un nuovo fusto che contiene più di cento pinte e lo sostituiscono, a questo punto il barista può completare il riempimento del bicchiere. La vita di un barista del Delirium è:
while True: (type, quantity) = get_order() delirium.pour(type, quantity)
La vita di un Magazziniere è:
while True: type = delirium.isempty() capacity = change_keg(type) delirium.loaded(type, capacity)
Attenzione: se il fusto (keg) è quasi vuoto il barista dovrà riempire parzialmente il bicchiere, occorrerà attivare il magazziniere che cambierà il fusto e poi il barista riempirà il bicchiere fino alla quantità richiesta dal cliente. Mentre un barista sta attendendo il cambiamento di un fusto altri baristi potrebbero ricevere ordini per lo stesso tipo di birra: gestire opportunamente questo caso. Scrivere il monitor Delirium.
Proposta di soluzione 1
- ERRORE: Secondo me c'è un leggero errore nella parte di load, nel caso in cui la nuova pinta non riesca a soddisfare completamente la richiesta ossia quando vale availableBeer[t] <= requests[t].head(), allora non lo risveglio nemmeno, invece dovrei risvegliare il pour, fargli versare quanto può, e richiedere una altra pinta, perché questo era un requisito del problema. Flecart (talk) 12:00, 15 January 2023 (CET)
/* Monitor Delirum: */
// Condition: Ok2Load;
// Condition: Ok2Pour[]; // Un elemento per Type
int availableBeer[]; // Un elemento per Type
Queue requests[]; // Un elemento per Type
Queue pendingRequests;
Procedure entry: void Pour(Type t, Quantity c)
{
if (c > availableBeer[t]) // Richiesta maggiore della birra disponibile
{
c -= availableBeer[t];
availableBeer[t] = 0;
requests[t].Enqueue(c);
if (requests[t].Length == 1) // Risveglio un magazziniere solo se è la prima richiesta di questo tipo di birra
{
pendingRequests.Enqueue(t);
Ok2Load().Signal();
}
Ok2Pour[t].Wait();
requests[t].Dequeue(); // Quando ho ottenuto la birra che voglio, elimino la mia richiesta
}
availableBeer[t] -= c;
}
Procedure entry: Type isEmpty()
{
if (pendingRequests.Length == 0)
{
Ok2Load.Wait();
}
return pendingRequests.Dequeue();
}
Procedure entry: Loaded(Type t, Capacity c)
{
availableBeer[t] += c;
while (requests[t].Length > 0 && availableBeer[t] > requests[t].head())
{
Ok2Pour[t].Signal();
}
if (requests[t].Length > 0) // serve per evitare che a causa di un magazziniere lento si accodino cosi tante richieste che mentre si sta caricando si svuota subito il fusto
{
pendingRequests.Enqueue(t);
Ok2Load.Signal();
}
}
Proposta di soluzione 2
extern int MAX_TYPE;
class Delirium {
int keg[MAX_TYPE]; // qnty fusto attuale
int orders[MAX_TYPE]; // qnty richiesta
bool worked[MAX_TYPE]; // 1 se magazziniere sta lavorando su questo.
condition type_wait[MAX_TYPE];
int num_wait[MAX_TYPE];
queue<int> empty_type;
condition is_empty;
entry pour(type, quantity) {
while (keg[type] < quantity) {
quantity -= keg[type];
keg[type] = 0;
if (!empty_type.find(type) && !worked[type]) {
empty_type.enqueue(type);
is_empty.signal();
}
num_wait[type]++;
type_wait[type].wait();
num_wait[type]--;
}
keg[type] -= quantity;
quantity = 0; // questo è inutile, ma concettualmente è corretto, l'ordine è completato.
}
entry loaded(type, capacity) {
keg[type] += capacity;
worked[type] = false;
for (int i = num_wait[type]; i > 0; i--) {
type_wait[type].signal();
}
}
// si suppone che un singolo tipo di fusto è lavorabile da un solo magazziniere alla volta.
// worked impedisce di avere nella coda un fusto su cuisi sta già lavorando.
entry isempty() {
if (empty_type.size() <= 0) {
is_emtpy.wait();
}
int type = emtpy_type.dequeue();
worked[type] = true;
return type;
}
}
Esercizio c.2
Proposta di soluzione 1
- Visto e corretto dall'utente Acsor in data 23/08/2020
- Visto e corretto dall'utente ? in data ?
- Visto, ritenuto corretto Flecart (talk) 09:27, 15 January 2023 (CET)
class LIFOBuffer {
stack<T> s;
semaphore mutex(1); // mutua esclusione
semaphore ok2consume(0);
void push (T value) {
mutex.P();
s.push(value);
// (1)
mutex.V()
ok2consume.V() // Curiosità: che succede se spostiamo quest'istruzione in (1)? Edit: funziona lo stesso, solo che aggiorni il valore del semaforo prima di uscire dalla mutex.
}
T pop () {
T value;
ok2consume.P();
mutex.P();
value = s.pop();
mutex.V();
return value;
}
}
Proposta di soluzione 2
Proposto da Flecart (talk) 09:27, 15 January 2023 (CET)
class lifobuf {
semaphore mutex(1);
stack<int> values; // empty initialized
stack<semaphore> waiting;
push(int value) {
mutex.P();
values.push(value);
if (waiting.size() > 0) {
semaphore s = waiting.pop();
s.V();
return;
}
mutex.V();
}
pop() {
int ret_val;
mutex.P();
if (values.size() <= 0) {
semaphore s = new semaphore(0);
waiting.push(s);
mutex.V();
s.P();
free(s);
}
ret_val = values.pop();
mutex.V();
return ret_val;
}
}
Esercizio g.1
Possiamo notare subito che il sistema ha due processori ed un dispositivo di I/O.
A e B partono insieme al tempo 0.
C parte tra il tempo 0 ed il tempo 2 (non possiamo sapere di preciso quando perchè entrambe le CPU sono occupate).
D parte tra il tempo 0 ed il tempo 3.
A questo punto possiamo supporre che tutti e 4 i processi partano in sequenza (A, B, C, D) nello stesso momento, e ognuno prende la prima CPU libera che trova.
A lavora per 3ms, poi scade il time slice.
Nel frattempo B lavora per 2ms, poi richiede I/O per 4ms.
La CPU su cui lavora B quindi si libera, e si manda in esecuzione il processo C.
Scaduto il time slice per A, si da il controllo ad un nuovo processo. B è occupato con I/O, C sta già lavorando, quindi è il turno di D.
C lavora per 3ms, poi richiede I/O per 3ms, che però è occupato da B, quindi si mette in coda per utilizzarlo.
La CPU su cui lavorava C si libera ed il controllo torna ad A, che doveva lavorare ancora per 2ms prima di chiedere il controllo di I/O, quindi lavora e si mette in coda dietro a C.
Tornando a D, questo lavora per 3ms prima che scada il time slice. Anche B ha finito il lavoro e ha bisogno di una CPU.
In questo momento sia D che B sono nella coda dei processi in stato ready, ma dal diagramma possiamo notare che il controllo torna a D.
La CPU ha scelto a caso un processo tra i due, perchè arrivati a questo punto possiamo supporre che lo scheduler sia Round-Robin.
B prende possesso della prima CPU che si libera, ovvero quella occupata da A, poi lavora per 2ms e termina il suo lavoro.
Nel momento in cui B termina il lavoro, scade anche il time slice per D, e C termina di usare I/O.
Abbiamo due processi (C e D) in coda ready. Ma abbiamo anche due CPU libere, perchè A è in coda per I/O e ci entra appena C finisce di usarlo.
Lo scheduler sceglie di mandare C sul primo processore e D sul secondo.
A nel frattempo, lavora per 4ms con I/O.
C lavora per 3ms, poi termina il suo lavoro.
D lavora per 3ms, poi scade il time slice. Ci sono due processori liberi, quindi D riparte subito in esecuzione.
D doveva lavorare ancora per 1ms prima di aver bisogno di I/O, quindi finisce e si mette in coda.
Ma nello stesso momento A termina di usare I/O, si prende un processore libero e lavora per i suoi ultimi 2ms.
D lavora per 1ms con I/O, poi prende il secondo processore libero e lavora per 1ms prima di terminare il suo lavoro.
Il time slice è di 3ms, lo scheduler è di tipo Round-Robin.
Il dispositivo di I/O è FIFO. L'ordine con cui partono i processi è quello alfabetico.
A(){
compute_a1(); // 5ms
io_a(); // 4ms
compute_a2(); // 2ms
}
B(){
compute_b(); // 2ms
io_b(); // 4ms
compute_b(); // 2ms
}
C(){
compute_c(); // 3ms
io_c(); // 3ms
compute_c(); // 3ms
}
D(){
compute_d1(); // 10ms
io_d(); // 1ms
compute_d2(); // 1ms
}
Lo scheduler potrebbe anche essere a priorità:
Priorità B < priorità D < priorità C
Priorità A = ?
B fatto partire prima di C e D.
Esercizio g.2 (da controllare)
- In sistemi dove dispositivi di archiviazione o supporti hardware per la memoria virtuale (e dunque per la paginazione, spesso utilizzata per realizzare il supporto di memoria virtuale) non sono presenti (es. sistemi embedded). (In sistemi real-time la memoria virtuale è praticabile? Annotare.)
- Perchè ad esempio sulle chiavette USB quasi mai abbiamo il problema di dover utilizzare file di dimensione maggiore ai 4GB. Non utilizza il journaling, che richiede molteplici scritture per ogni azione ed in dispositivi portatili può ridurre di molto la durata. Non supporta i permessi sui file, e questo è un vantaggio per le chiavette USB, pensate per trasferire dati tra PC diversi.
- Per fornire parallelismo e ridondanza. Non è necessario fare backup dei dati sul disco, nel senso di mantenere una copia identica di dati già memorizzati altrove, in quanto diversi sistemi di codici permettono il rilevamento e/o la correzione di errori.
- Se in un grafo di Holt multirisorsa esiste un ciclo tra più processi e risorse, ciò non significa che allo stesso tempo non siano coinvolti processi con archi esclusivamente entranti. Ogni processo appartenente a questa categoria non è in attesa di risorse, e può dunque procedere con i suoi calcoli; quando avrà terminato rilascerà le risorse precedentemente allocategli, eventualmente sbloccando uno dei processi coinvolti nel ciclo.
Esame 21/06/2018
Esercizio c.1 (sbagliato)
/* Monitor tmon */
define MAX n;
define TERRAFERMA 1;
define ISOLA 2;
semaphore ok2unload;
semaphore ok2load;
semaphore ok2ship;
semaphore mutex(1); // la rampa è zona critica --> mutua esclusione
stack ferry;
int current_port = 0;
Procedure entry: al_porto(int location)
{
current_port = location; // traghetto arriva a destinazione
ok2unload.signal(); // da il via per far sbarcare le macchine
ok2ship.wait(); // si ferma
current_port = 0; // traghetto sta viaggiando tra i due porti
}
Procedure entry: imbarca(int location)
{
mutex.wait(); // prende possesso della rampa
ferry.push(1); // sale sul traghetto
mutex.signal(); // libera la rampa
}
Procedure entry: imbarcato(int location)
{
if(ferry.lenght() == MAX) // se il traghetto è pieno da il via per farlo salpare
{
ok2load.wait();
ok2ship.signal();
}
}
Procedure entry: sbarca(int location)
{
mutex.wait(); // prende possesso della rampa
ferry.pop(); // scende dal traghetto
mutex.signal(); // libera la rampa
}
Procedure entry: sbarcato(int location)
{
if(ferry.lenght() == 0) // se il traghetto è vuoto da il via per far imbarcare le macchine
{
ok2unload.wait();
ok2load.signal();
}
}
Esercizio c.1
/* Monitor tmon */
#define MAX n
#define NONE 0
#define TERRAFERMA 1
#define ISOLA 2
condition ok2unload;
condition ok2load[2];
condition ok2ship;
condition empty;
int onboard = 0;
int onramp = 0;
int current_port = NONE;
Procedure entry: al_porto(int location)
{
//arrivando
current_port = location;
ok2unload.signal();
if (onboard > 0)
empty.wait()
ok2load[location].signal()
if (onboard < MAX)
ok2ship.wait()
//partendo
current_port = NONE;
}
Procedure entry: imbarca(int location)
{
if (current_port != location || onramp > 0 || onboard >= MAX)
ok2load[location].wait()
onramp = 1;
}
Procedure entry: imbarcato(int location)
{
onramp = 0; onboard++;
if (onboard < MAX)
ok2load[location].signal();
else
ok2ship.signal();
}
Procedure entry: sbarca(int location)
{
if (current_port != location || onramp > 0)
ok2unload.wait()
onramp = 1;
}
Procedure entry: sbarcato(int location)
{
onramp = 0; onboard--;
if (onboard == 0)
empty.signal();
else
ok2unload.signal();
}
Esercizio c.2 (sbagliato)
#define N n // limite operazioni
semaphore mutex(1); // sezione critica
class lim_semaphore()
{
int value;
semaphore plus;
semaphore minus;
P()
{
mutex.P();
if(value < N)
{
if (value >= 0)
{
plus.P();
}
else
{
minus.V();
}
value--;
}
mutex.V();
}
V()
{
mutex.P();
if(value > -N)
{
if (value <= 0)
{
minus.P();
}
else
{
plus.V();
}
value++;
}
mutex.V();
}
}
Esercizio c.2
Soluzione "furba e facile"
- Visto dall'utente Acsor (talk) in data 18:53, 9 September 2020 (CEST). Ritengo sia: corretto (perché l'ho fatto pressappoco uguale). (Ritengo anche che possedere strumenti di analisi formale per verificare la correttezza di codice simile sarebbe di grande ausilio.)
class bounded_semaphore {
semaphore plus;
semaphore minus;
int value; // serve per significato
bounded_semaphore (int initval, unsigned maxval) {
value = initval;
plus = new semaphore(maxval + initval);
minus = new semaphore(maxval - initval);
}
void P() {
plus.P();
value--;
minus.V();
}
void V() {
minus.P();
value++;
plus.V();
}
}
Soluzione "schiacciasassi"
visto da LiberaL in data 2023/05/12, perchè nel primo if della V() si fa value >= - maxval? non dovrebbe essere + maxval?
class bounded_semaphore {
semaphore mutex;
queue<semaphore> okmin, okmax;
int value;
unsigned maxval;
bounded_semaphore (int initval, unsigned maxval) {
value = initval;
this.maxval = maxval;
}
void P() {
mutex.P();
if (value <= -maxval) {
s=semaphore(0);
okmin.enqueue(s);
mutex.V();
s.P();
} else if (okmax.length() > 0) {
s = okmax.dequeue()
s.V();
mutex.V();
} else {
value--;
mutex.V();
}
}
void V() {
mutex.P();
if (value >= -maxval) { //qui...
s=semaphore(0);
okmax.enqueue(s);
mutex.V();
s.P();
} else if (okmin.length() > 0) {
s = okmin.dequeue()
s.V();
mutex.V();
} else {
value++;
mutex.V();
}
}
}
Esercizio g.1
IC = 10,10,10 // Capitale iniziale
COH = 4,4,4 // Saldo in cassa
MAX ATT RES AVAIL
P1 | 6,6,6 | 1,1,1 | 5,5,5 | 4,4,4
P2 | 6,6,6 | 1,1,1 | 5,5,5 | 5,5,5
P3 | 9,9,9 | 4,4,4 | 5,5,5 | 6,6,6
Minimizzato
IC = 4,4,4
COH = 1,1,1
MAX ATT RES
P1 | 3,3,3 | 1,1,1 | 2,2,2
P2 | 3,3,3 | 1,1,1 | 2,2,2
P3 | 3,3,3 | 1,1,1 | 2,2,2
Esercizio g.2 (da controllare)
- Il calcolo del working set serve a determinare il numero di processi che possono essere mantenuti attivi sulla base del limite della memoria principale, più precisamente del suo numero di frame. Può essere svolto ad ogni page fault, ossia quando un processo tra quelli attivi richiede una pagina non presente in memoria, o prima di avviare un nuovo processo.
- La lunghezza massima di un file che può essere memorizzato su un file system di tipo FAT viene calcolata moltiplicando il massimo numero di cluster (dimensione dell'unità di allocazione) identificabili per la loro dimensione. Il massimo numero di cluster identificabili dipende da quanti bit sono allocati per numerarli, e per questa distinzione esistono varie versioni di FAT (FAT12, FAT16, FAT32).
- FAT32 memorizza la dimensione dei file in un intero unsigned da 32bit, e non può quindi gestire un file di dimensione superiore ai 2^32 bit = ~4GB.
- FAT16, allocando 16bit per identificare i cluster, può contarne al massimo 2^16 (65536). Prendendo quindi, ad esempio, un file system FAT16 con cluster da 32KB, possiamo avere file grandi al massimo 32KB*65536 = ~2GB.
- FAT12 di conseguenza può numerare al massimo 2^12 (4096) cluster, ma dato che il numero dei settori del disco viene memorizzato in un intero signed a 16bit, la massima dimensione del disco è 2^15 = 32MB. Ovviamente, non si può memorizzare un file di grandezza superiore alla dimensione dell'unità di memorizzazione stessa, e quindi anche i file in FAT12 possono avere dimensione massima di 32MB.
- Entrambi condividono l'intento di infettare host con codice malevolo, ma differiscono fondamentalmente nella modalità: i virus infettano programmi già esistenti mediante un virus dropper, mentre i worm diffondono copie di se stessi, solitamente attraverso la rete.
- In vari casi sulla base della natura del sistema. Innanzitutto, in sistemi batch ciò avviene se non sono stati inseriti più processi per un certo lasso di tempo. In sistemi general-purpose (es. per PC o dispositivi mobili) tale condizione è verificabile se tutti i processi sono in attesa su una coda che non è quella dello scheduler (ad. es. di un semaforo o di una periferica di I/O); casi concreti sono pertanto il deadlock (di tutti i processi del sistema) o attesa generale di I/O. Infine sempre in sistemi general-purpose tale condizione può manifestarsi, stavolta in condizioni patologiche, se ogni processo è assegnato ad una propria CPU/core, lasciando pertanto la coda d'attesa vuota.
Esame 28/05/2018
Esercizio c.1
Stack<int> entriesStack;
int vid[MAX];
condition ok2esci[MAX]
int in = 0;
int out = -1;
Procedure-entry: entra(int id) {
if (in >= MAX)
ok2entra.wait()
vid[in++] = id;
if (in < MAX)
ok2entra.signal()
else
out = MAX - 1;
}
Procedure-entry: esci(int id) {
int i;
for (i = 0; i < in; i++)
if (vid[i] == id)
break; //cerco l'indice di id nel vettore vid
if (i != out)
ok2esci[i].wait();
if (out > 0) {
out--;
ok2esci[out].signal();
} else {
out--;
in = 0;
ok2entra.signal();
}
}
Esercizio c.1 (da controllare)
Monitor riempisvuota {
Int MAXPROCESSI;
Stack s;
condition ok2enter;
condition ok2exit;
p.e void entra(getPid()){
if( s.size() >= MAXPROCESSI)
ok2enter.wait();
s.insert(getPid());
if(s.size() > MAXPROCESSI)
ok2exit.signal()
}
p.e void esci(getPid()){
if(s.size() > MAXPROCESSI && s.top == getPid()) {
s.pop();
ok2entra.signal()
}
else
ok2exit.wait();
}
Esercizio c.2 (ERRATO)
- Soluzione proposta è errata, non puoi riceve in modo greedy e printare subito il carattere Flecart (talk) 11:33, 18 January 2023 (CET)
proc[x]: x='a',...,'z'
while True:
//c sarà il carattere stampato dal processo precedente
(c, string) = arecv(*)
if(string == wait){
//mi metto in attesa di ricevere l'ACK da proc[x]
m=arecv(x);
}
if (c == NONE){
//significa che sei il primo a ricevere quella stringa
print(x);
if (len(string) > 1){
//mando la wait a tutti, il primo che riceve qualcosa da stampare manda una wait a tutti
asend(wait,*);
int l = len(string);
int i = 1;
while(l != 0){
asend(proc[string[i]], (x, string[i...]));
//si mette in attesa di ricevere l'ACK dal processo dell'ultima lettera della parola
m=areceive(proc[string[i]]);
//rimando la wait al processo per ribloccarlo
asend(wait, proc[string[i]])
l--;
i++;
}
//dopo aver finito la stampa della stringa sblocco tutti i processi
asend(ACK, *);
}
}else{
print(x);
asend(ACK, x);
//ricomincia il ciclo while, si rimette in attesa e il 'gestore gli rimanda la wait'
}
Esercizio c.2
Flecart friend (talk) cedo la proprità intellettuale di questa soluzione a flecart
process [x]: x='a'..'z'
if(x=='a'){
asend(<NULL,NULL>,'b');
asend(<NULL,NULL>,'b');
}
While True:
<c,string>=arecv(x-1+26%26);
if(string==NULL):
<c,string>=arecv(*);
if(string!=NULL):
<c,string>=arecv(x-1+26%26);
if(string!=NULL):
if(string[0]==x):
print(string[0]);
if(string.len()>1):
aasend(<NULL,string[1:]>,(x+1)%26);
else:
aasend(<NULL,NULL>,(x+1)%26);
aasend(<NULL,NULL>,(x+1)%26);
else:
aasend(<NULL,string>,(x+1)%26);
else:
aasend(<NULL,NULL>,(x+1)%26);
aasend(<NULL,NULL>,(x+1)%26);
Proposta c2
proc[a]:
bool occupied = false;
queue<string> s;
while True {
(c, string) = arecv(*);
if (c == NONE) {
if (occupied) {
s.enqueue(string);
} else {
if (string.len() < 1)
continue;
occupied = true;
asend(string[0], (MIDDLE, string));
}
} else if (c == END) {
if (s.size() > 0) {
string ss = s.dequeue();
asend(string[0], (MIDLLE, string));
} else {
occupied = false;
}
} else {
print(x);
if (len(string) > 1)
asend(proc[string[0]], (MIDDLE, string[1:]));
else:
asend(proc[a], (END, ""));
}
}
proc[x]: x = 'b', ... 'z';
while True {
(c, string) = arecv(*);
if (c == NONE) {
asend(proc['a'], (NONE, string));
} else { // potrà essere solo MIDDLE
print(x);
if (len(string) > 1)
asend(proc[string[0]], (MIDDLE, string[1:]));
else:
asend(proc[a], (END, ""));
}
}
Esame 12/02/2018
Esercizio c.1 (da controllare)
monitor bridge:
int ncar
bool boat_on_0
bool boat_on_1 // per semplicità, quando nel codice si trova boat_on_(direction) oppure isBoat(direction)(),
// si valuta il valore booleano di direction e lo si applica sotto forma di stringa al simbolo
// ad esso adiacente
bool is_raised
queue waiting_mean // i valori possibili sono: boat0, boat1 oppure car
condition ok2go
entry car_enter(direction):
if is_raised || ncar == MAXCAR:
waiting_mean.enqueue(car)
ok2go.wait()
is_raised = false
++ncar
entry car_exit(direction):
--ncar
if (waiting_mean.top().isBoat() && ncar == 0) || waiting_mean.top().isCar(): // isBoat ritorna true se l'oggetto su cui
waiting_mean.dequeue() // è invocata è boat0 oppure boat1
ok2go.signal()
entry boat_enter(direction):
if !is_raised || boat_on_(direction):
waiting_mean.enqueue(boat)
ok2go.wait()
if waiting_mean.top().isBoat(!direction)():
waiting_mean.dequeue()
ok2go.signal()
is_raised = true
boat_on_(direction) = true
entry boat_exit(direction):
boat_on_(direction) = false
if !boat_on_(!direction):
waiting_mean.dequeue()
ok2go.signal()
Esercizio c.1
monitor bridge {
int carsOnBridge = 0;
int shipping[2] = {0, 0}; //navi da entrambe le direzioni
int status = NONE; //UP DOWN NONE
int last2pass = 0; //ultimo che ha passato il ponte
int waitingC = 0; //coda delle macchine che aspettano
int waitingS[2] = {0,0}; //navi che stanno aspettando
condition ok2ship[2]
condition ok2drive
entry car_enter(int direction){
if(carsOnBridge >= MAX || status == UP || waitingS[0] + waitingS[1] > 0 ){
waitingC++;ok2drive.wait;waitingC--;}
status = DOWN;
carsOnBridge++
if (carsOnBridge < MAX)
ok2drive.signal(); //vanno tutte le MAX car che stanno aspettando
}
entry car_exit(int direction){
carsOnBridge--
if (waitingS[0] + waitingS[1] == 0)
ok2drive.signal();
if(carsOnBridge == 0){
ok2ship[0].signal(); ok2ship[1].signal();
}
if(carsOnBridge + waitingS[0] + waitingS[1] == 0)
status = NONE
}
entry ship_enter(int direction){
if (bridge = DOWN || shipping[direction] != 0 || waitingC > 0)
{
waitingS[i]++; ok2ship[i].wait(); waitingS[i]--;
}
isBridgeUp = false;
shipping[i] = 1;
entry ship_exit(int direction){
shipping[i] = 0;
if (waitingC == 0)
ok2ship[i].signal()
else if(shipping[1-i] == 0)
ok2drive.signal();
if(carsOnBridge + waitingS[0] + waitingS[1] == 0)
status = NONE
}
Esercizio c.1 (da controllare)
monitor bridge {
UP=0;
DOWN=1;
bridgeis = DOWN;
bool carAreExiting = false;
condition ok2drive;
condition ok2barca[2];
waitingCar = 0;
carOnBridge = 0;
boatWaiting[2] = {0,0};
boatIsPassing[2] = {false,false}
entry car_enter(direction) {
if (bridgeis == DOWN)
if(carOnBridge == MAXCAR)
waitingCar++;
ok2drive.wait();
waitingCar--;
else if (carAreExiting)
waitingCar++;
ok2drive.wait();
waitingCar--;
else
if (boatIsPassing[0] || boatIsPassing[1])
waitingCar++;
ok2drive.wait();
waitingCar--;
bridgeis = DOWN;
carOnBridge++;
carAreExiting = false;
if(carOnBridge < MAXCAR && !carAreExiting)
ok2drive.signal();
}
entry car_exit(direction) {
carOnBridge--;
carAreExiting = true;
if(carOnBridge == 0)
carAreExiting = false;
if(boatWaiting[0] > 0)
bridgeis = UP;
ok2barca[0].signal();
else if (boatWaiting[1] > 0)
bridgeis = UP;
ok2barca[1].signal();
else
ok2drive.signal();
}
entry boat_enter(direction) {
if (bridgeis == UP)
| if (boatIsPassing[direction] == true)
| | boatWaiting[direction]++;
| | ok2barca.wait();
| | boatWaiting[direction]--;
else
| if (carOnBridge > 0)
| | boatWaiting[direction]++;
| | ok2barca.wait();
| | boatWaiting[direction]--;
| | bridgeis = UP;
boatIsPassing[direction] = true;
if(boatIsPassing[1-direction] == false && boatWaiting[1-direction] > 0)
ok2barca[1-direction].signal();
}
entry boat_exit(direction) {
boatIsPassing[direction] = false;
if (boatIsPassing[1-direction] == false)
if (waitingCar > 0)
bridgeis = DOWN;
ok2drive.signal();
else
if (waitingCar == 0)
ok2barca[direction].signal();
}
Esercizio c.1 (sbagliato)
monitor bridge
condition ok2passCar;
condition ok2passBoat;
condition ok2up;
condition ok2down;
int carOnBridge[2] = 0; //2 sensi di marcia
int boatUnderBridge[2] = 0;
boolean bridge_down = false; //vuol dire che il ponte parte alzato, true ponte abbassato
procedure entry car_enter(direction){
if(bridge_down && carOnBridge[direction] < MAXCAR){
carOnBridge[direction]++;
ok2passCar.signal();
}else if (bridge_down && boatUnderBridge[0] == 0 && boatUnderBridge[1] == 0){
//se non ci sono navi in transito e arriva una macchina abbassa ponte
ok2down.signal();
ok2passCar.signal();
ok2passBoat.wait();
}else{
ok2passCar.wait();
}
}
procedure entry car_exit(direction){
carOnBridge[direction]--;
if(carOnBridge[0] == 0 && carOnBridge[1] == 0){
bridge_down = false;
ok2up.signal();
}else{
ok2up.wait();
}
}
procedure entry boat_enter(direction){
if(!bridge_down && boatUnderBridge[direction] < 1){
boatUnderBridge[direction]++;
ok2passBoat.signal();
}else if(!bridge_down && carOnBridge[0] == 0 && carOnBridge[1] == 0){
ok2up.signal();
ok2passBoat.signal();
ok2passCar.wait();
}else {
ok2passBoat.wait();
}
}
procedure entry boat_exit(direction){
boatUnderBridge[direction]--;
if(boatUnderBridge[0] == 0 && boatUnderBridge[1] == 0){
bridge_down = true;
ok2down.signal();
}else{
ok2down.wait();
}
}
Esercizio c.1 2o (sbagliato)
#define car 1
#define ship 2
#define fromDX 1
#define fromSX 0
monitor bridge {
int carsOnBridge = 0;
int shippingDX = 0; //nave che sta passando dal lato destro
int shippingSX = 0; //nave che sta passando dal lato sinistro
bool isBridgeUp = false;
int last2pass = 0; //ultimo che ha passato il ponte
int waitingS = 0; //navi che stanno aspettando
int waitingC = 0 ; //auto che stanno aspettando
condition ok2ship
condition ok2drive
entry car_enter(int direction){
//un auto si ferma se il numero di auto sul ponte è massimo
//e se l'ultima a passare è stata un auto mentre ci sono navi in attesa
if(carsOnBridge == MAX || isBridgeUp || (last2pass==car && waitingS > 0) ){
waitingC++;
ok2drive.wait;
}
carsOnBridge++;
waitingC--;
}
entry car_exit(int direction){
carsOnBridge--;
last2pass = car;
if(carsOnBridge == 0 && waitingS>0){
isBrigdeUp = true;
ok2ship.signal;
}
}
entry ship_enter(int direction){
//se la barca viene da destra
if(direction == fromDX){
//si ferma anche quando c'è una nave che sta già attraversando nella sua stessa direzione
if (isBridgeup == false || shippingDX || (last2pass==ship && waitingC > 0) ){
waitingS++;
ok2ship.wait;
}
if (waitingS > 0)
waitingS--;
shippingDX = 1;
}
//se la barca viene da sinistra
else if(direction == fromSX){
if (isBridgeup == false || shippingSX || ( (last2pass==ship && waitingC > 0))){
waitingS++;
ok2ship.wait;
}
if (waitingS > 0)
waitingS--;
shippingSX = 1;
}
}
entry ship_exit(int direction){
if(direction == fromDX)
shippingDX = 0;
else if (direction == fromSX)
shippingSX = 0;
last2pass = ship;
if(shippingDX == 0 && shippingSX == 0 && waitingC)
isBrigdeUp == false;
ok2drive.signal;
else if(shippingDX == 0 && shippingSX == 0 && waitingS > 0)
ok2ship.signal;
}
}
Esercizio c.2 (sbagliato)
list printed_msg; # questa è una variabile condivisa che ai fini dell'esercizio non si può utilizzare (message passing)
process server[i]:
while true:
<msg, pid> = arecv(*)
if printed_msg.length == 0 or <msg, pid> is not in printed_msg:
printed_msg.append(<msg,id>)
print(msg)
Esercizio c.2 (da controllare)
Nello svolgimento seguente, receiver incapsula l'ambiente privato del processo; _peers rappresenta il vettore di processi "fratelli" ai quali può essere chiesto di stampare un messaggio, mentre _printed contiene l'hash di tutti i messaggi stampati dal processo locale. Si suppone che istanze della classe receiver possano essere passate come parametro ad areceive() ed asend() (non implementate).
class receiver:
def __init__(self, peers):
"""
:param peers: list of processes this process communicates with.
"""
self._peers = tuple(peers)
self._printed = list()
def run(self):
while True:
process, message = areceive(ANY)
if process in self._peers:
self._reply_query(process, message)
else:
self._print(process, message)
def _print(self, sender, message):
h = hash(message.text)
if h not in self._printed and not self._printed_from_peers(message):
self._printed.append(h)
print(message.text)
def _reply_query(self, sender, h):
"""
Invoked when the current process receive a "query" from a peer process.
`h` contains the hash of a message which may or may have not been
sent from this process; if it was sent, the reply is `Yes`, otherwise `No`.
"""
reply = "Yes" if int(h) in self._printed else "No"
asend(sender, reply)
def _printed_from_peers(self, message):
"""
:return: `True` if this message has already been printed from any of the
peer processes, `False` otherwise.
"""
h = hash(message)
for p in self._peers:
asend(p, str(h))
for p in self._peers:
_, reply = areceive(p)
if reply.text == "Yes":
return True
else if reply.text != "No":
# If the response is neither "Yes" nor "No", then we have got a query
self._reply_query(p, reply)
return False
Esercizio g.1 (da controllare)
Sulla base dei valori in entrata, è possibile costruire le matrici Allocation (q.tà di risorse allocate per processo e per tipo), Need (q.tà di risorse che ogni processo potrebbe ancora chiedere) e il vettore Available (num. di risorse correntemente disponibili).
| Allocation | ||
|---|---|---|
| A | B | |
| p1 | 4 | 5 |
| p2 | 3 | 3 |
| p3 | 2 | 4 |
| Need | ||
|---|---|---|
| A | B | |
| p1 | 6 | 8 |
| p2 | 6 | 3 |
| p3 | 6 | 8 |
| Available | |
|---|---|
| A | B |
| x | y |
Nel caso delle risorse di tipo A, deve aversi x >= 6 in quanto un processo dovrà essere selezionato come primo nella permutazione dell'algoritmo del banchiere multivaluta, e tutti quelli correnti hanno lo stesso valore Need(i)(1); per ciò che riguarda le risorse di tipo B, possiamo ragionare per esaustione
- Se il primo processo della permutazione è p1, allora y >= 8 (con questo valore posso soddisfare la richiesta di p1 e in seguito tutte le altre)
- Se il primo processo della permutazione è p2, allora y >= 5: con questo valore è possibile soddisfare la richiesta di p2; una volta che esso avrà finito, restituirà 3 unità della risorsa B, che permetteranno di soddisfare sia le richieste di A sia quelle di C
- Se il primo processo della permutazione è p3, allora y >= 8 (ragionamento analogo come per p1)
Volendo scegliere il minimo, y >= 5, ed in conclusione (x, y) >= (6, 5).
Svolgimento basato in parte sull'approccio di Operating System Concepts di Silberschatz. et al, 9th edition, cap. 7.
Esercizio g.2 (da controllare)
- Può accadere che il sistema torni in uno stato di safety o che invece porti a deadlock. Diversamente uno stato di safety non può portare direttamente ad uno stato di deadlock, ma solo ad uno di non-safety.
- Selezionare uno o più tra i processi attivi e sospenderli, salvando il loro stato su memoria secondaria operando delle operazioni di swap-out, finché l'insieme dei frame nella memoria centrale non è in grado di soddisfare tutti i processi rimasti attivi.
- La scelta è determinata perlopiù dal fattore costo. Con un sistema RAID 1 è possibile ripristinare un disco guasto molto brevemente, in quanto le operazioni coinvolte prevedono una semplice ricopiatura dal disco di backup; con un sistema RAID 5 il ripristino del disco guasto deve coinvolgere tutti i dischi dell'intero array, e ciò può richiedere anche ore per dischi di grandi dimensioni. D'altra parte RAID 1 è più costoso (con n dischi, posso memorizzare tanta informazione quanto potrei con n / 2 dischi) rispetto a RAID 5 dove, tra gli n dischi, complessivamente soltanto uno è destinato alle informazioni di ridondanza.
- Completare.