Sistemi Operativi - User contributions [en]

Prove svolte e soluzioni proposte

2020-05-19T14:39:59Z

Laufragor: Aggiunto il c.1 (mbuf) dell'esame 2019.09.13 (e l'esame stesso)

Questa pagina serve a raccogliere prove d'esame svolte (che possono essere utili alla preparazione) e soluzioni proposte a tali prove da sottoporre a peer-review. Una proposta di soluzione si considera corretta quando

* È stata sottoposta a verifica del docente, o
* È stata sottoposta a verifica di (almeno) tre compagni di corso

Chi abbia visionato e corretto una prova altrui, è pregato di segnalarlo all'interno della sezione corrispondente riportando nome utente e data di correzione.

Al fine di verificare la correttezza delle proprie proposte, segnaliamo la presenza di [[Tool_per_semafori_e_monitor|strumenti di programmazione concorrente]] per i linguaggi C e Python.

== Esame 13/09/2019 ==
Testo: [https://www.cs.unibo.it/~renzo/so/compiti/2019.09.13.tot.pdf 2019.09.13.tot.pdf]
=== Esercizio c.1 ===
Controllato dal professor Davoli durante la lezione del 19/05/2020.

<source lang="python">
# Original author: Andrea R.

monitor mbuf:
waiting = 0
queue<pair<T, int>> q # (dato, molteplicità)
condition ok2add # q.length() < MAXELEM
condition ok2get # q.length() > 0

entry void add(T data, int n):
if q.length() >= MAXELEM:
ok2add.wait()

q.enqueue({data, n})

if waiting >= q.front().second:
ok2get.signal()

entry T get():
waiting++ # vuole ricevere
if q.empty() or waiting < q.front().second: # cortocircuitato
ok2get.wait()

x = q.front().first
q.front().second--
waiting-- # riceve

if q.front().second > 0: # cascata
ok2get.signal()
else: # ultimo che riceve
q.dequeue()
ok2add.signal()
return x
</source>

== Esame 15/07/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.07.15.tot.pdf 2019.07.15.tot.pdf]
=== Esercizio c.1 (verifiche rimanenti: 2) ===
Una semplice realizzazione in Python dello pseudocodice seguente è disponibile [https://github.com/pollomarzo/rdso1920/tree/master/2019exams/samepc qui].

<source lang="python">
# Original authors: Mattia Guazzaloca, Paolo Marzolo
#
# Contributors: utente Acsor

monitor pair_buffer:
int nw, nr;
queue buffer;
condition same_number;

pair_buffer():
nw = nr = 0
buffer = queue()
same_number = condition()

@entry
put(T x):
nw++;
buffer.enqueue(x);

if nw != nr:
same_number.wait();

same_number.signal();
nw--;

@entry
T get(void):
nr++;

if nw != nr:
same_number.wait();
else:
same_number.signal();

T val = buffer.dequeue();
same_number.signal();
nr--;

return val;
</source>

==== Peer-review ====
# Verifica del 18/05/2020 dell'utente [[User:Acsor |Acsor ]]. Ritengo sia: corretto
# Verifica del ... dell'utente ... . Ritengo sia: ...
# Verifica del ... dell'utente ... . Ritengo sia: ...

=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor pairbuf{

condition ok2read;
condition ok2write;
in count
queue writers

void put(T x){
writers.enqueue(x);
if(count == 0)
ok2write.wait(); 
ok2read.signal();
}

T get(void){
ok2write.signal()
count++;
if(writers.empty == true)
ok2read.wait()
T x = writers.dequeue;
count—
return x
}

</source>

 
 

== Esame 18/06/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.06.18.tot.pdf 2019.06.18.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor pg{

int waitingReader = 0;
int waitingWriter = 0;

condition ok2write;
condition ok2read;

T datobuf;

entry put (T dato) {

if (waitingReader > 0)
datobuf = dato;
while (waitingReader > 0)
ok2read.signal();
else if (waitingWriter >= 0)
waitingWriter++;
ok2write.wait();
waitingWriter--;
datobuf = dato;

}

entry T get (void) {

if (waitingReader > 0 || waitingWriter == 0)
waitingReader++;
ok2read.wait();
waitingReader--;
else if (waitingWriter > 0)
ok2write.signal();
return datobuf;

}

}
</source>
 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor taon {
condition ok2w, ok2r;
int nw, nr = 0;
T buf;

entry void put (T dato){
nw++;
if( nw != 1 || nr == 0)
ok2w.wait();
buf = dato;
for (i=0, i++, i < nr)
ok2r.signal();
nw--;
}

entry T get(){
nr++;
if(nw==0)
ok2r.wait();
ok2w.signal();
T dato = buf;
nr --;
return dato;
}
</source>
 

=== Esercizio c.2 ===
<source lang="c">
/* MP sincrono dato quello asincrono */

void ssend(obj msg, process q)
{
asend(msg, q);
ack = areceive(q);
}

obj sreceive(process p)
{
obj msg = areceive(p);
asend(ack, p);
return msg;
}
</source>
 
Soluzione:
<source lang="c">
dati asend/arecv devo implementare lssend lsrecv

lssend(dst, msg):
asend(dst, (MSG, myid(), msg))
arecv(dst)

lsrecv(snd):
asend(myid(), (TAG, myid(), NULL)) // mi mando un messaggio che riesco a riconoscere
while True:
(T, s, m) = arecv(ANY) // continua a ricevere finchè non ricevi il mio messaggio
if (T != TAG) data.push(s, m)
else break
while (((s,m) = data.pop(snd) == NULL): // c'è il messaggio di src definito?
(T, s, m) = arecv(ANY)
data.push(s, m)
asend(s, (ACK, myid(), NULL)
return m
</source>
 

=== Esercizio g.1 (sbagliato) ===
<nowiki>
x = long_compute()/short_compute()
X = io()

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 8 8 8
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
P1 |x|x|x|x|x|X|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|x|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|-|-|
P2 |-|-|x|x|x|-|-|-|-|-|-|x|x|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|x|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|x|-|-|
P3 |-|-|x|x|x|-|-|-|-|-|-|x|x|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|x|-|-|-|-|-|-|-|-|X|X|X|-|-|-|X|X|x|x|
</nowiki>
 

=== Esercizio g.1 ===
<nowiki>
P1(start=0): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
P2(start=4): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
P3(start=7): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
P|1 1 1|1 1|2 2 2|3 3 3|2 2|1 1 1|3 3|1 1|2 2 2*3 3 3|2 2|3 3|1 1|-|2 2|- - -|3 3|
I |1 1 1 1 1| |2 2 2 2 2|3 3 3 3 3|1 1 1 1 1|2 2 2 2 2|3 3 3 3 3|

r - - - - 2 - - 3 2 2 2 1 1 3 3 3 1 1 2 2 - - - 2 2 2 3 3 1 1
1 3 3

* 3 ha finito input output e 2 è ancora in esecuzione quindi c'è da scegliere
</nowiki>
 

=== Esercizio g.2 (da controllare) ===
a) Può richiedere supporto hardware. Se implementato con contatori o stack questi devono essere aggiornati ad ogni riferimento alla memoria. L'intero sistema viene appesantito e rallentato. 
b) Il journaling si assicura che i dati sul filesystem siano consistenti, ma non aggiornati. Assicura la coerenza dei dati, ma non la perdita dei file se il filesystem si danneggia. 
c) Si dice che un programma A ha lo stesso potere espressivo di un programma B quando è possibile esprimere ogni programma scritto con B mediante A. Per implementare MP sincrono dato quello asincrono basta aggiungere una libreria. Per implementare MP asincrono dato quello sincrono bisogna aggiungere un processo server. 
d) In questi casi tutte le istruzioni vengono eseguite con la massima autorità, con problemi di sicurezza nel caso un utente estraneo prenda il controllo del sistema o rischio di commettere gravi errori semplicemente sbagliando a digitare un comando.

== Esame 14/02/2019 ==
[https://www.cs.unibo.it/~renzo/so/compiti/2019.02.14.tot.pdf testo esame]
=== Esercizio c.1 (possibile soluzione corretta) ===
<source lang="python">
# Original authors: Mattia Guazzaloca & Paolo Marzolo
#
# Contributors:
#

class monobinarysem(monitor):
def __init__(self, val):
self.iszero = condition(self)
self.val = val

@entry
def monoP(self):
if self.val == 0:
self.iszero.wait()

self.val -= 1

@entry
def monoV(self):
if self.val == 0:
self.val += 1
self.iszero.signal()
</source>
=== Esercizio c.2 (soluzione corretta) ===
<source lang="python">
# Original author: Renzo Davoli (durante la lezione)
#
# Contributors:
#

def pssend(message, destination):
asend((self(),message),destination)
while(1):
snd, message = arecv(ANY)
if(message == ACK):
break
datastruct.add(snd, message)

def psreceive(sender):
dummy = Message(null)
asend(self(),dummy) //self is my id

while(1):
snd, message = arecv(ANY)
if(message == dummy):
break
datastruct.add(snd, message)

if (datastruct.match(sender)):
src, msg = datastruct.get(sender)
asend((self(),ACK), src)
return msg
else:
return None
</source>

== Esame 17/07/2018 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2018.07.17.tot.pdf 2018.07.17.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
/* 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();
}
}
</source>
 

=== Esercizio c.2 ===
<source lang="c">
stack s;
semaphore mutex(1); // mutua esclusione
semaphore ok2consume(0);

Procedure entry: void push(int value)
{
mutex.P();
s.push(value)
mutex.V()
ok2consume.V()
}

Procedure entry: int pop()
{
int value;
ok2consume.P();
mutex.P();
value = s.pop();
mutex.V();
return value;
}
</source>
 

=== 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.

<source lang="c">
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
}
</source>
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) ===
a) Nei sistemi embedded o in computer ad uso specifico in cui sono richiesti tempi di risposta molto rapidi. La memoria virtuale può generare ritardi imprevedibili e può richiedere un supporto hardware per la traduzione da indirizzi virtuali ad indirizzi fisici. Ma in sistemi embedded non sempre c'è spazio fisico per implementare questi supporti hardware. 
b) 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. 
c) Serve ad aumentare le performance, rendere il sistema resiliente alla perdita di uno o più dischi e poterli rimpiazzare senza interrompere il servizio. RAID serve per tutelarsi dai problemi hardware, non sostituisce i backup in quanto ci permette solo di proseguire il lavoro, non ci permette di recuperare file cancellati o bloccati da ransomware. 
d) Per dimostrare questo occorre una variante del grafo di Holt, detto grafo Wait-For, che si costruisce eliminando i nodi di tipo risorsa e collassando gli archi appropriati, per cui il grafo di Holt contiene un ciclo se e solo se il grafo Wait-For contiene un ciclo e pertanto si ha l'attesa circolare (deadlock).
 

== Esame 28/05/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.05.18.tot.pdf 2019.05.18.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor storage{
int stored[16]
int components[16]
condition ok2make[16]
boolean required[16] //false

void add(components){
stored += components;
for(i=0; i< 16; i ++){
if(required[i] == true)
ok2make(i).signal();
}
}

void get(components){
for(i = 0; i< 16; i++){
if (stored[i] >= components[i])
stored[i] -= components[i]
else
required[i] = true
ok2make(i).wait();
required[i] = false
i—;

}
}
</source>

 
 

== Esame 21/06/2018 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2018.06.21.tot.pdf 2018.06.21.tot.pdf]
=== Esercizio c.1 (sbagliato) ===
<source lang="c">
/* 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();
}
}

</source>
 

=== Esercizio c.1 ===
<source lang="c">
/* 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();
}
</source>
 

=== Esercizio c.2 (sbagliato) ===
<source lang="c">

#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();
}
}
</source>
 

=== Esercizio c.2 ===
Soluzione "furba e facile"
<source lang="c">
#define N n // limite operazioni
class lim_semaphore()
{
semaphore plus;
semaphore minus;
int value; //serve per significato

init(x) : { value=x; plus.init(N+x); minus.init(N-x);} //costruttore
P() : { plus.P(); value--; minus.V(); }
V() : { minus.P(); value++; plus.V(); }
}
</source>
 

Soluzione "schiacciasassi"
<source lang="c">
#define N n // limite operazioni

class lim_semaphore()
{
semaphore mutex;
queue of semaphore okmin, okmax;
int value;
init(x) : { value=x; }
P() {
mutex.P();
if (value <= -N) {
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();
}
}
V() {
mutex.P();
if (value >= -N) {
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();
}
}
}
</source>
 

=== Esercizio g.1 ===
<nowiki>
IC = 10,10,10
COH = 4,4,4

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</nowiki>
 

Minimizzato

<nowiki>
IC = 4,4,4 //massimo
COH = 1,1,1 //soldi in cassa

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</nowiki>
 

=== Esercizio g.2 (da controllare) ===
a) L'algoritmo di calcolo del working set serve a limitare il problema del trashing assicurandosi che le pagine di cui ha bisogno un processo (una loro approssimazione) siano già caricate in memoria prima di far partire il processo stesso. L'algoritmo viene eseguito ogni volta che avviene un page fault, cercando una pagina "vittima" non presente nel working set e sfrattandola, facendo posto alla pagina che occorre al processo in esecuzione. 
b) 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. 
c) Un virus necessità l'intervento umano per essere avviato o per essere diffuso. Si attacca a programmi o file per potersi diffondere. Un worms è in grado di riprodursi e di diffondersi autonomamente, sfruttando le informazioni presenti sul computer. 
d) La ready queue di uno scheduler può essere vuota quando tutti i processi sono in esecuzione su diversi processori, oppure quando tutti i processi hanno terminato la loro esecuzione. È un caso fisiologico della vita di un sistema.

== Esame 28/05/2018 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2018.05.28.tot.pdf 2018.05.28.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
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();
}
}
</source>
 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
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();
}
</source>
 
=== Esercizio c.2 (da controllare) ===
<source lang="c">
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'
}
</source>
 
== Esame 12/02/2018 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2018.02.12.tot.pdf 2018.02.12.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
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
}
</source>

=== Esercizio c.1 (da controllare) ===
<source lang="c">
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();

}
</source>

=== Esercizio c.1 (sbagliato) ===
<source lang="c">
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();
}
}
</source>

=== Esercizio c.1 2o (sbagliato) ===
<source lang="c">
#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;
}
}
</source>
 
=== Esercizio c.2 (da controllare) ===
<source lang="c">
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)

</source>

== Esame 11/09/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.09.11.tot.pdf 2017.09.11.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
monitor crossing

ok2dir[4]; //NESW
bool busy = false;

pe entra(int dir)
if (busy)
ok2dir[dir].wait();
busy = true;

pe esci(int dir)
busy = false;
ok2dir[(dir + 1) % 4].signal();
if (!busy)
ok2dir[(dir + 2) % 4].signal();
if (!busy)
ok2dir[(dir + 3) % 4].signal();
if (!busy)
ok2dir[(dir + 4) % 4].signal(); //dir

//alternativa più compatta
pe esci(int dir)
busy = false;
for (i = 0; i < 4; i++)
if (!busy)
ok2dir[(dir + i + 1) % 4].signal();

</source>
 

=== Esercizio c.2 (da controllare) ===
<source lang="c">
// server[] = array contenente il PID di tutti i server

#define BROADCAST server[0]

server[0]
{
while(true)
{
<msg, sender> = arecv(*); // ricevo il messaggio
if (sender == BROADCAST)
print(msg); // se il messaggio l'ho ricevuto da me stesso allora lo stampo
else
asend(*, <msg, getpid()>); // se il messaggio l'ho ricevuto da un client o da un altro server lo inoltro a tutti i server (compreso me stesso)
}
}

server[x] // x = 1...N-1
{
while(true)
{
<msg, sender> = arecv(*); // ricevo il messaggio
if (sender == BROADCAST)
print(msg); // se il messaggio l'ho ricevuto dal server[0] allora lo stampo
else
asend(BROADCAST, <msg, getpid()>) // se il messaggio l'ho ricevuto da un client lo inoltro al server[0]
}
}
</source>
 

== Esame 17/07/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
monitor conf {
condition finished;
condition ready2present[max];
bool arrived[max] = false;
bool giachiamato[max] = false;

entry chiama(chiamato){
if(arrived[chiamato] == true)
ready2present[chiamato].signal;
finished.wait;
return true;
else
giachiamato[chiamato]= true
return false;
}

entry arrivato(nome){
if(giachiamato[nome] == true)
return false;

arrived[nome] = true;
ok2present[nome].wait;
return true;
}

entry finepresentazione(nome){
finished.signal;
}
}

</source>

=== Esercizio c.2 (da controllare) ===
<source lang="c">
si, è possibile:

Implementare asend e arecv date bsend e brecv

asend(pid_t, msg_type msg){
bsend (<pid_t dst, msg>);
}

arecv(*){
pid_t act = getpid(); \\ act = proprio pid
do{
<dst, msg> = brecv(*);
}while (dst =! act)
return msg;
}

</source>
 

== Esame 19/06/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.06.19.tot.pdf 2017.06.19.tot.pdf]
=== Esercizio c.1 (da controllare)===
<source lang="c">
#define NATLETI n

condition ok2lancia[NATLETI];
condition ok2giudice;

int counter[NATLETI];
int ultimo_tiro;
float registro[NATLETI][3];

Procedure entry: boolean pronto(int i)
{
if(!(i == 0 && counter[i] == 0)) // se è il primo lancio non devo metterlo in wait
ok2lancia[i].wait()
if(counter[i] < 3)
return true;
else
return false;
}

Procedure entry: void lanciato (int i)
{
counter[i]++;
ultimo_tiro = i;
ok2giudice.signal();
}

Procedure entry: int lanciofatto()
{
ok2giudice.wait()
if(ultimo_tiro == NATLETI-1 && counter[0] == 3)
return -1; // devo invalidare la condizione per uscire dal while, quindi se nessuno deve più lanciare ritorno -1
else
return ultimo_tiro;
}

Procedure entry: void registraechiama(int i, float m)
{
registro[i][counter[i]-1] = m; // il secondo indice indica l'iesimo lancio -1 (perchè iniziamo a contare da zero)
if(i == NATLETI-1) // se ha appena tirato l'ultimo atleta non posso dare il via a NATLETI (perchè non esiste), quindi faccio ricominciare il giro
ok2lancia[0].signal();
else
ok2lancia[i+1].signal();
}

Procedure entry: int classifica()
{
int best[NATLETI];
for(int i = 0; i < NATLETI; i++)
{
for(int j = 0; j < 3; j++)
{
if(registro[i][j] > best[i])
best[i] = registro[i][j];
}
}
best.sort_in_descending_order(); // supponiamo nel nostro pseudolinguaggio esista una funzione di ordinamento qualunque
return best;
}
</source>
 

== Esame 29/05/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.05.29.tot.pdf 2017.05.29.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
condition okpartita
condition ok2chiama
condition ok2punteggio
condition ok2run[2][MAX]
int numpronti
int punteggio[2]
boolean partita=false
boolean partitafinita=false
chiamati = []
contabandiera[2]
int winner

entry nuovapartita():
{
punteggio[A] = punteggio[B] = 0;
numpronti = 0;
partita=true;
okpartita.signal()
chiamati = [];
}
entry chiama(l):
{
if (numpronti<2*MAX)
{
ok2chiama.wait();
}
chiamati = l;
contabandiera[A] = contabandiera[B] = 0
winner = -1;
for (s in n)
{
ok2run[A][s].signal();
ok2run[B][s].signal()
}
ok2punteggio.wait();
punteggio[winner++]
if (max(punteggio) == 10)
{
partitafinita = true;
for (s in A,B)
{
for (n in range(MAX))
{
ok2run[s][n].signal();
}
}
}
return punteggio;
}
entry pronto(s, n):
{
if (partitafinita) return 1;
if (!partita)
{
okpartita.wait();
}
numpronti++;
if (numpronti>=2*MAX)
{
ok2chiama.signal();
}
if (!(n in chiamati))
{
ok2run[s][n].wait();
}
numpronti--;
return 0 if partita else 1;
}
allabandiera(s, n):
{
contabandiera[s]++;
if (winner == -1 && contabandiera[s] == len(chiamati))
{
winner = s;
}
if (contabandiera[A] == len(chiamati) && contabandiera[B] == len(chiamati))
{
ok2punteggio.signal();
}
}

casi da discutere:
se arrivano studenti a pronto prima che il prof dichiara nuovapartita succedono guai.
</source>
 

== Esame 14/02/2015 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2015.02.14.tot.pdf 2015.02.14.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor altcolbb {

generic_type valueBuf[MAX];
int front = rear = 0;

bool isFull = false;

condition ok2write[2]; //gli indici sono i colori (red=0, blue=1)

lastColor = None;

entry void write(color_t color, generic_type val) {

if (front == rear)
if(isFull)
ok2write[color].wait();
else
if (lastColor == color)
ok2write[color].wait();

valueBuf[front] = val;
front = (front+1) % MAX;
lastColor = color;

if (front == rear)
isFull = true;
else
ok2write[1-color].signal();

ok2read.signal();

}

entry generic_type read(void) {

if (rear == front)
if (!isFull)
ok2read.wait();

generic_type tmpValue = valueBuf[rear];

rear = (rear + 1) % MAX;
if (rear == front)
isFull = false;
color_t tmpColor = lastColor;
lastColor = None;
ok2write[tmpColor].signal(); //quando un lettore legge l'ultimo elemento
//dal buffer, ci possono solo essere scrittori
//in attesa che abbiano lo stesso colore
//dell'ultimo elemento.
else
ok2write[1-lastColor].signal();

return tmpValue;

}

}
</source>
 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
#define MAX n

condition ok2read;
condition ok2write;
condition ok2red;
condition ok2blue;

queue buffer;

Procedure entry: void write(color_t color, generic_type val)
{
if(buffer.lenght() >= MAX)
ok2write.wait();
if((<color> == buffer.last()) == color)
{
if(color == red)
ok2red.wait();
else
ok2blue.wait();
}
buffer.enqueue(<color, val>);
ok2read.signal();
if(buffer.lenght() < MAX)
{
if(color == red)
ok2blue.signal();
else
ok2red.signal();
}
}

Procedure entry: generic_type read(void)
{
generic_type val;
if(buffer.lenght == 0)
ok2read.wait();
<val> = buffer.dequeue();
ok2write.signal()
return val;
}
</source>
 

=== Esercizio g.1 (da controllare) ===
a) 
MIN:
<nowiki>
Stringa di riferimenti: 0 1 2 3 4 5 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0
Frame 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Frame 2: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Frame 3: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Frame 4: 3 4 5 5 5 5 3 4 4 4 4 3 3 3 3 3 3 3
</nowiki>

FIFO:
<nowiki>
Stringa di riferimenti: 0 1 2 3 4 5 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0
Frame 1: 0 0 0 0 4 4 4 4 2 2 2 2 1 1 1 1 1 1 1 1 1
Frame 2: 1 1 1 1 5 5 5 5 3 3 3 3 2 2 2 2 2 2 2 2
Frame 3: 2 2 2 2 0 0 0 0 4 4 4 4 3 3 3 3 3 3 3
Frame 4: 3 3 3 3 1 1 1 1 0 0 0 0 0 0 0 0 0 0
</nowiki>

B) 
MIN:
<nowiki>
Stringa di riferimenti: 0 1 2 3 4 0 1 2 3 0 1 4 2 0 3 4 1 2 3 4
Frame 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
Frame 2: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
Frame 3: 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3
Frame 4: 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
</nowiki>
 

== Esame 20/01/2015 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2015.01.20.tot.pdf 2015.01.20.tot.pdf]

=== Esercizio c.1 (da controllare) ===
<source lang="c">
#define MAX n

condition ok2read;
condition ok2write;

queue buffer;
int waiting_write = 0;
int waiting_read = 0;

Procedure entry: void write(generic_type val)
{
if (buffer.lenght() >= MAX)
{
if (waiting_write >= MAX)
{
buffer.dequeue(); // il valore va perso
ok2write.signal();
}
waiting_write++;
ok2write.wait();
waiting_write--;
}
buffer.enqueue(val);
ok2read.signal();
}

Procedure entry: generic_type read(void)
{
generic_type val;
if (buffer.lenght() == 0)
{
if (waiting_read >= MAX)
{
ok2read.signal();
}
waiting_read++;
ok2read.wait();
waiting_read--:
}
if (buffer.lenght() == 0)
val = NULL;
else
val = dequeue;
ok2write.signal()
return val;
}
</source>
 

=== Esercizio g.1 (da controllare) ===
a) 
MIN:
<nowiki>
Stringa di riferimenti: 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1
Frame 1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Frame 2: 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Frame 3: 3 4 5 5 5 3 4 4 4 3 3 3 3
</nowiki>

LRU:
<nowiki>
Stringa di riferimenti: 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1
Frame 1: 1 1 1 4 4 4 2 2 2 1 1 1 1 1 1
Frame 2: 2 2 2 5 5 5 3 3 3 2 2 2 2 2
Frame 3: 3 3 3 1 1 1 4 4 4 3 3 3 3
</nowiki>

B) 
Il problema si può risolvere utilizzando l'algoritmo LRU e la seguente stringa di riferimenti:
<nowiki>
Stringa di riferimenti: 4 3 2 1 5 3 2 4 1 5 4 3 2
Frame 1: 4 4 4 4 5 5 5 5 1 1 1 1 1
Frame 2: 3 3 3 3 3 3 3 3 5 5 5 2
Frame 3: 2 2 2 2 2 2 2 2 2 3 3
Frame 4: 1 1 1 1 4 4 4 4 4 4
</nowiki>
 

== Esame 16/07/2014 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2014.07.16.tot.pdf 2014.07.16.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
/* Monitor Bounded Buffer: (non richiesto dall'esercizio) */
queue q;
condition oktoread; // q.length() > 0
condition oktowrite; // q.length() < MAX

procedure entry type read():
if (q.length() == 0) oktoread.wait(); // controllo
retval = q.dequeue(); // cambio lo stato
// abilito coloro che possono essere abilitati dal cambiamento di stato
oktowrite.signal()
return retval;

procedure entry void write(type elem):
if (q.length() >= MAX) oktowrite.wait(); //controllo
q.enqueue(elem); // cambio lo stato
oktoread.signal(); // abilito chi può essere abilitato

/* NOTE:
* procedure entry ==> dichiarazione di funzioni (senza vedere l'implementazione
* dall'esterno)
*/
</source>
 
<source lang="c">
/* Min-Max Monitor Bounded Buffer: */

Queue Q;

// Condition: OKTOREAD: Q.Length > MIN
// Condition: OKTOWRITE: Q.Length < MAX

procedure entry: Type Read():
{
if (Q.Length <= MIN) OKTOREAD.Wait(); // Controllo
retval = Q.Dequeue(); // Cambio di stato
OKTOWRITE.Signal(); // Abilito chi vuole scrivere
return retval; // Qui sono sicuro perchè ne ho eliminato uno prima
}

procedure entry: void Write(Type elem):
{
if (Q.Length >= MAX) OKTOWRITE.Wait() // Controllo
Q.Enqueue(elem); // Cambio di stato
if (Q.Length > MIN) OKTOREAD.Signal(); // Abilito chi vuole leggere
}
</source>
 
=== Esercizio c.2 ===
<source lang="c">
Semaphore mutex = 1;

struct Elem
{
Semaphore s;
int counter;
}

struct Elem V[]; // Vettore a dimensione variabile. I nuovi elementi sono initializzati a s = 0, counter = 0.

void RendezVouz(int n)
{
mutex.P(); // Blocco, decremento di 1 (il processo si blocca se il semaforo vale 0)
V[n].counter++;
if (V[n].counter < n)
{
mutex.V(); // Rilascia, incrementa di 1
V[n].s.P();
}
V[n].counter--;
if (V[n].counter > 0)
V[n].s.V();
else
mutex.V();
}
</source>
 

=== Esercizio g.1 ===
<source lang=html5>
0241302 ==> soluzione corretta
(0)2 2200
(1)3 1111
(2)4 4442
(3)0 0333

2 3 4 0 1 2 3 4 0 1 2 3 ==> soluzione proposta, non corretta perchè non è la stringa più corta
2 1 1 1 1 0 0 0 0
3 3 2 2 2 2 1 1 1
4 4 4 3 3 3 3 2 2
0 0 0 0 4 4 4 4 3
</source>
 

== Esame 03/06/2014 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2014.06.03.tot.pdf 2014.06.03.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor sabelev
{
#define N n //numero dei piani

condition ok2enter[N][2]; //piano di partenza e direzione
condition ok2exit[N]; //piano di arrivo

procedure entry: void atfloor(int floor, int direction)
{
ok2exit[floor].signal(); //da il via al primo del piano che deve uscire
ok2enter[floor][direction].signal(); //da il via al primo del piano che deve entrare e deve andare in questa direzione
}

procedure entry: void enter(int from, int to)
{
int direction;
if(to > from) //controllo sulla direzione
direction = 0;
else
direction = 1;

ok2enter[from][direction].wait(); //mi fermo in attesa che arrivi l'ascensore
ok2enter[from][direction].signal(); //quando arriva l'ascensore do il via a quello in attesa dopo di me
ok2exit[to].wait(); //mi fermo dentro all'ascensore in attesa di uscire
}

procedure entry: void exit(int from, int to)
{
ok2exit[to].signal(); //do il via ad un altro che deve uscire a questo piano come me
}

}
</source>
 

== Esame 21/02/2014 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2014.02.21.tot.pdf 2014.02.21.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor bbwl
{
#define MAXELEM n

condition ok2read;
condition ok2write;
condition ok2log;

queue q1;
queue q2;

procedure entry: void write(eltype elem)
{
if (q1.size() >= MAXELEM)
ok2write.wait();
q1.enqueue(elem);
ok2log.signal();
}

procedure entry: eltype read()
{
if (q2.size == 0)
ok2read.wait();
eltype elem = q2.dequeue();
ok2write.signal();
return elem;
}

procedure entry: eltype log()
{
if (q1.size() == 0)
ok2log.wait();
eltype elem = q1.dequeue();
q2.enqueue(elem);
ok2read.signal()
return elem;
}
}
</source>
 

== Esame 11/05/2011 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2011-05-11.con.pdf 2011-05-11.con.pdf]
=== Esercizio 2 (da controllare) ===
<source lang="c">
stack s;
semaphore mutex(1);

lifocs_enter()
{
s.push(getpid());
mutex.p();
while(s.lastElement() != getpid())
{
mutex.v();
mutex.p();
}
s.pop();
}

lifocs_exit()
{
mutex.v();
}
</source>
 

== Esame Pratico 21/09/2018 ==
http://www.cs.unibo.it/~renzo/so/pratiche/2018.09.21.pdf
=== Esercizio 1 ===
<source lang="c">
#define _GNU_SOURCE
#include <sys/signalfd.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <unistd.h>
#include <time.h>
#include <string.h>

int main(int argc, char * argv[]){
sigset_t mask;
struct signalfd_siginfo fdsi;
int fd;
char* t;
char* filename;

sigemptyset(&mask);
sigaddset(&mask, SIGUSR1);
sigaddset(&mask, SIGUSR2);
sigprocmask(SIG_SETMASK, &mask, NULL);

int sigfd = signalfd(-1, &mask, 0);

for(;;){
read(sigfd, &fdsi, sizeof(struct signalfd_siginfo));
if(fdsi.ssi_signo == SIGUSR1){
asprintf(&filename, "./%u", fdsi.ssi_pid);
fd = open(filename, O_APPEND | O_CREAT | O_WRONLY);
time_t stime = time(NULL);
t = ctime(&stime);
write(fd, t, sizeof(char)*strlen(t));
close(fd);
}
if(fdsi.ssi_signo == SIGUSR2){
asprintf(&filename, "./%u", fdsi.ssi_pid);
fd = open(filename, O_APPEND | O_CREAT | O_WRONLY);
time_t stime = time(NULL);
t = ctime(&stime);
write(fd, t, sizeof(char)*strlen(t));
close(fd);
}
}
}

dovrebbe stampare anche il nome del segnale prima di stampare il tempo ma per il resto va bene

</source>
 

=== Esercizio 3 ===
<source lang="python">
#!/usr/bin/env python
import sys
import os
import re
dict = {}

def func(a):
os.chdir(a)
for root, dirs, files in os.walk("."):
for filename in files:
try:
fl =file(filename)
firstline = fl.readline()
fl.close()
except IOError: # caso di file che non riesce ad aprire
#print("could not read", file)
pass
if (re.match('^#!', firstline)):
dict.setdefault(firstline, []) #firstline include anche il carattere \n, quindi quando si stampa va anche a capo
dict[firstline].append(filename)
for k in dict.keys():
print k
for v in dict[k]:
print v
#print(" ")

if __name__ == '__main__':
if (len(sys.argv)==1):
dir = "."
else:
dir = sys.argv[1]
func(dir)

</source>

== Esame Pratico 22/01/2016 ==
http://www.cs.unibo.it/~renzo/so/pratiche/2016.01.22.pdf
=== Esercizio 1 ===
<source lang="c">
#include <stdlib.h>
#include <stdio.h>
#include <dirent.h>
#include <sys/types.h>
#include <string.h>
#include <unistd.h>

typedef struct nameNumber {
char *name;
int value;
} nameNumber;

int prefixToInt (char *string) {

int i = 0;
int num = 0;
while (string[i] >= '0' && string[i] < '9' && i < strlen(string)) {
num = (num*10) + (string[i]-'0');
i++;
}
return num;

}

void fileSort(struct nameNumber **files) {

}

int comp (const void * el1, const void * el2) {
struct nameNumber *f = *((nameNumber**)el1);
struct nameNumber *s = *((nameNumber**)el2);
if (f->value > s->value) return 1;
if (f->value < s->value) return -1;
return 0;
}

int main(int arg, char* argv[]) {

struct nameNumber **files;

DIR *dir;
struct dirent *ent;

int count = 0;

if((dir = opendir(argv[1])) != NULL)
{
while( (ent = readdir(dir)) != NULL )
{
if (ent->d_name[0] < '9' && ent->d_name[0] >= '0')
{
files = (struct nameNumber**)realloc(files , (count+1) * sizeof(struct nameNumber*));
files[count] = (struct nameNumber*)malloc(sizeof(struct nameNumber));
files[count]->name = (char*)malloc(sizeof(char)*strlen(ent->d_name) + 1);
strcpy(files[count]->name, ent->d_name);
files[count]->value = prefixToInt(files[count]->name);
printf("name : %s , value : %d\n", files[count]->name , files[count]->value);
count++;
}
}
}

qsort(files, count, sizeof(nameNumber*), comp);

int i;
for (i=0; i < count; i++) {
printf("%s\n",files[i]->name);
}

}

</source>

== Esame di Concorrenza del 13/01/2005 ==
Il testo degli esercizi è disponibile alla pagina http://www.cs.unibo.it/~renzo/so/compiti/2005-01-13.con.pdf.

=== Esercizio 1 ===
Il codice di questo esercizio può essere eseguito scaricando il sorgente Python e l'archivio relativo agli [[Tool_per_semafori_e_monitor|strumenti di concorrenza per il linguaggio Python]].

<source lang="python">
#!/usr/bin/env python3
import threading
import random
import time
from pysm.semaphore import semaphore

class mod_counter:
def __init__(self, mod, start=0):
self._mod = mod
self._val = start

def inc(self):
self._val = (self._val + 1) % self._mod

def get(self):
return self._val

class process(threading.Thread):
def __init__(self, to_print, c: mod_counter, a, t, r):
threading.Thread.__init__(self, name="proc" + to_print)

if to_print not in "tar":
raise ValueError("Unexpected printable character:", to_print)

self._counter = c
self._x = to_print
self._semaphores = {'t': t, 'a': a, 'r': r}
self._enter = True

if self._x == 't':
self._semaphores[self._x].V()

def run(self):
while True:
self.sync()
print("[%s] %c" % (self.name, self._x))

# Print a trailing newline
if (self._counter.get() == 7):
print()

time.sleep(random.random() * 0.5)

def sync(self):
if (self._enter):
self._semaphores[self._x].P()
self._enter = False
else:
self._counter.inc()
curr = "taratata"[self._counter.get()]

self._semaphores[curr].V()

self._enter = True
self.sync()

def main():
counter = mod_counter(8)
semaphores = (semaphore(0), semaphore(0), semaphore(0))
procs = [process(c, counter, *semaphores) for c in "tar"]

for p in procs:
p.daemon = True
p.start()

for p in procs:
p.join()

return 0

if __name__ == "__main__":
exit(main())
</source>

File:SistemiOperativi1920.pdf

2020-04-26T12:00:07Z

Laufragor: Laufragor uploaded a new version of "File:SistemiOperativi1920.pdf": Aggiornamento al 26/04/2020

Primo caricamento della conversione in PDF delle dispense del corso.

Dispense del Corso - Appunti Condivisi

2020-04-26T08:42:08Z

Laufragor: Reorganised page based on relevance

Gli studenti del corso di Sistemi Operativi a.a. 2019-2020 hanno collaborato alla creazione di appunti-dispense condivisi, scritti durante le ore di lezione e spesso rimaneggiati in un secondo momento. La stesura degli appunti è disponibile alla pagina [https://etherpad.wikimedia.org/p/so1920.cs.unibo.it so1920.cs.unibo.it], un'istanza Etherpad pubblica di Wikimedia.

== Download ==
* [[Media:SistemiOperativi1920.pdf|SistemiOperativi1920.pdf]]: versione PDF delle note del pad [https://etherpad.wikimedia.org/p/so1920.cs.unibo.it so1920.cs.unibo.it].
* [[Media:Converter1920.tgz|Converter1920.tgz]]: strumenti per la conversione PDF di [https://etherpad.wikimedia.org/p/so1920.cs.unibo.it so1920.cs.unibo.it].

=== Realizzazione ===
La conversione di queste note in formato PDF è avvenuta tramite il convertitore [https://pandoc.org/ pandoc], configurandolo con le opportune opzioni. È possibile scaricare l'archivio contenente il materiale (script di conversione, intestazioni LaTeX, logo ecc.) utile alla conversione specificamente per le note del pad [https://etherpad.wikimedia.org/p/so1920.cs.unibo.it so1920.cs.unibo.it] dalla sezione [[#Download|Download]].

== Portare avanti la tradizione ==
Se siete studenti di anni accademici successivi al 2019-2020, gestire un pad di appunti convidisi per l'anno corrente è facile! [https://pandoc.org/ pandoc] fornisce miriadi di personalizzazioni e la possibilità di scaricare in automatico testo grezzo da indirizzi URL.

=== Testo grezzo Etherpad ===
Per ottenere il testo in formato testuale da un pad Etherpad, è sufficiente seguire dall'interfaccia web il percorso <code>Tasto Import/Export > Plain Text</code>. Tale opzione è utile per chi volesse, ad esempio, passare l'URL di scaricamento testuale a [https://pandoc.org/ pandoc].

Main Page

2020-04-26T08:34:14Z

Laufragor: Reorganised "A.A. 2019/20" section based on relevance, and minor edits

Questo è il Wiki del Corso di [http://www.cs.unibo.it/~renzo/so Sistemi Operativi] della LT in Informatica dell'[https://www.unibo.it/it Università di Bologna].

== ANNO ACCADEMICO 2019/20 ==
=== Dispense condivise ===
* [[Dispense del Corso - Appunti Condivisi]]: raccolta di appunti gestita su [https://etherpad.org/ Etherpad] liberamente scaricabile.

=== Materiale didattico ===
* [[Esempi, Esercizi ed Esperimenti 2019/20]]
* [[Decalogo di Programmazione Concorrente]]: suggerimenti e regole di massima sul come sviluppare correttamente codice concorrente.
* [[Prove svolte e soluzioni proposte]]
* [[Documenti 2019/20]]

=== Registro Lezioni ===
Registro semestrale sulle attività svolte a lezione

* [[Lezioni Anno Accademico 2019/20 I semestre]]
* [[Lezioni Anno Accademico 2019/20 II semestre]]

Per informazioni più esaustive, rifarsi alle [[Dispense del Corso - Appunti Condivisi|dispense del corso]].

=== Annunci e servizi ===
* [[Lezioni ONLINE: limitiamo i danni del software proprietario]]

== ANNI PRECEDENTI ==
* [[Materiale dell'AA 2018-19]]
* [[Materiale dell'AA 2017-18]]
* [[Materiale dell'AA 2016-17]]
* [[Materiale dell'AA 2015-16]]
* [[Materiale dell'AA 2014-15]]
* [[Materiale dell'AA 2013-14]]

== ISCRIZIONE AL WIKI ==
Quando viene richiesto di risolvere un semplice calcolo artimetico per creare un account occorre ricordare quanto scritto [[qui]].

Prove svolte e soluzioni proposte

2020-04-23T07:59:29Z

Laufragor: /* Esame 15/07/2019 */

Questa pagina serve a raccogliere prove d'esame svolte (che possono essere utili alla preparazione) e soluzioni proposte a tali prove da sottoporre a peer-review.

== Esame 15/07/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.07.15.tot.pdf 2019.07.15.tot.pdf]
=== Esercizio c.1 (possibile soluzione corretta) ===
<source lang="python">
# Original authors: Mattia Guazzaloca & Paolo Marzolo
#
# Contributors:
#

monitor pair_buffer:
int nw = 0, nr = 0;
queue buffer;
condition same_number;

@entry
put(T x):
nw++;
buffer.enqueue(x);

if nw != nr:
same_number.wait();

same_number.signal();
nw--;

@entry
T get(void):
nr++;
if nw != nr:
same_number.wait();
else:
same_number.signal();

T val = buffer.dequeue();

same_number.signal();

nr--;

return val;
</source>

Real python implementation and simple test program is available [https://github.com/pollomarzo/rdso1920/tree/master/2019exams/samepc here]

=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor pairbuf{

condition ok2read;
condition ok2write;
in count
queue writers

void put(T x){
writers.enqueue(x);
if(count == 0)
ok2write.wait(); 
ok2read.signal();
}

T get(void){
ok2write.signal()
count++;
if(writers.empty == true)
ok2read.wait()
T x = writers.dequeue;
count—
return x
}

</source>

 
 

== Esame 18/06/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.06.18.tot.pdf 2019.06.18.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor pg{

int waitingReader = 0;
int waitingWriter = 0;

condition ok2write;
condition ok2read;

T datobuf;

p.e. put (T dato) {

if (waitingReader > 0)
datobuf = dato;
while (waitingReader > 0)
ok2read.signal();
else if (waitingWriter >= 0)
waitingWriter++;
ok2write.wait();
waitingWriter--;
datobuf = dato;

}

p.e. T get (void) {

if (waitingReader > 0 || waitingWriter == 0)
waitingReader++;
ok2read.wait();
waitingReader--;
else if (waitingWriter > 0)
ok2write.signal();
return datobuf;

}

}
</source>
 

 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor taon {
condition ok2w, ok2r;
int nw, nr = 0;
T buf;

p.e.: void put (T dato){
nw++;
if( nw != 1 || nr == 0)
ok2w.wait();
buf = dato;
for (i=0, i++, i < nr)
ok2r.signal();
nw--;
}

p.e.: T get(){
nr++;
if(nw==0)
ok2r.wait();
ok2w.signal();
T dato = buf;
nr --;
return dato;
}
</source>
 

=== Esercizio c.1 ===
<source lang="c">
monitor dispatch
condition go_cart;
condition ok2station; // quando la stazione può caricare
current_station = None
// dizionario con chiave destinazione
luggages = {}

def countl(luggages):
n=0
for d in luggages:
n += len(luggages[d]);

p.e. cartat(code):
current_station = code // carrello arriva alla stazione
if (code == BLQ || len(luggages[code]) > 0):
ok2station[code].signal()
go_cart.wait()
current_station = None // il carrello sta viaggiando tra le stazioni

p.e. load(dst, owner):
if (current_station != BLQ || countl(luggages) >= MAX):
ok2station(BLQ).wait()
luggages[dst].append(owner)
if (countl(luggages) >= MAX)
go_cart.signal()

p.e. unload(dst):
if (current_station != dst || len(luggages[dst]) == 0)
// lunghezza lista dei bagagli con questa destinazione
ok2station(dst).wait()
owner = luggages[dst].pop()
if len(luggages[dst]) == 0)
go_cart.signal()
return owner
</source>
 

=== Esercizio c.2 ===
<source lang="c">
/* MP sincrono dato quello asincrono */

void ssend(obj msg, process q)
{
asend(msg, q);
ack = areceive(q);
}

obj sreceive(process p)
{
obj msg = areceive(p);
asend(ack, p);
return msg;
}
</source>
 
Soluzione:
<source lang="c">
dati asend/arecv devo implementare lssend lsrecv

lssend(dst, msg):
asend(dst, (MSG, myid(), msg))
arecv(dst)

lsrecv(snd):
asend(myid(), (TAG, myid(), NULL)) // mi mando un messaggio che riesco a riconoscere
while True:
(T, s, m) = arecv(ANY) // continua a ricevere finchè non ricevi il mio messaggio
if (T != TAG) data.push(s, m)
else break
while (((s,m) = data.pop(snd) == NULL): // c'è il messaggio di src definito?
(T, s, m) = arecv(ANY)
data.push(s, m)
asend(s, (ACK, myid(), NULL)
return m
</source>
 

=== Esercizio g.1 (sbagliato) ===
<nowiki>
x = long_compute()/short_compute()
X = io()

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 8 8 8
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
P1 |x|x|x|x|x|X|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|x|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|-|-|
P2 |-|-|x|x|x|-|-|-|-|-|-|x|x|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|x|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|x|-|-|
P3 |-|-|x|x|x|-|-|-|-|-|-|x|x|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|X|X|X|-|-|-|-|-|-|X|X|x|-|-|-|-|-|-|x|x|x|-|-|-|-|-|-|x|-|-|-|-|-|-|-|-|X|X|X|-|-|-|X|X|x|x|
</nowiki>
 

=== Esercizio g.1 ===
<nowiki>
P1(start=0): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
P2(start=4): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU
P3(start=7): 5ms CPU, 5ms IO, 5ms CPU, 5ms IO, 2ms CPU

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
P|1 1 1|1 1|2 2 2|3 3 3|2 2|1 1 1|3 3|1 1|2 2 2*3 3 3|2 2|3 3|1 1|-|2 2|- - -|3 3|
I |1 1 1 1 1| |2 2 2 2 2|3 3 3 3 3|1 1 1 1 1|2 2 2 2 2|3 3 3 3 3|

r - - - - 2 - - 3 2 2 2 1 1 3 3 3 1 1 2 2 - - - 2 2 2 3 3 1 1
1 3 3

* 3 ha finito input output e 2 è ancora in esecuzione quindi c'è da scegliere
</nowiki>
 

=== Esercizio g.2 (da controllare) ===
a) Può richiedere supporto hardware. Se implementato con contatori o stack questi devono essere aggiornati ad ogni riferimento alla memoria. L'intero sistema viene appesantito e rallentato. 
b) Il journaling si assicura che i dati sul filesystem siano consistenti, ma non aggiornati. Assicura la coerenza dei dati, ma non la perdita dei file se il filesystem si danneggia. 
c) Si dice che un programma A ha lo stesso potere espressivo di un programma B quando è possibile esprimere ogni programma scritto con B mediante A. Per implementare MP sincrono dato quello asincrono basta aggiungere una libreria. Per implementare MP asincrono dato quello sincrono bisogna aggiungere un processo server. 
d) In questi casi tutte le istruzioni vengono eseguite con la massima autorità, con problemi di sicurezza nel caso un utente estraneo prenda il controllo del sistema o rischio di commettere gravi errori semplicemente sbagliando a digitare un comando.

== Esame 14/02/2019 ==
[https://www.cs.unibo.it/~renzo/so/compiti/2019.02.14.tot.pdf testo esame]
=== Esercizio c.1 (possibile soluzione corretta) ===
<source lang="python">
# Original authors: Mattia Guazzaloca & Paolo Marzolo
#
# Contributors:
#

class monobinarysem(monitor):
def __init__(self, val):
self.iszero = condition(self)
self.val = val

@entry
def monoP(self):
if self.val == 0:
self.iszero.wait()

self.val -= 1

@entry
def monoV(self):
if self.val == 0:
self.val += 1
self.iszero.signal()
</source>
=== Esercizio c.2 (soluzione corretta) ===
<source lang="python">
# Original author: Renzo Davoli (durante la lezione)
#
# Contributors:
#

def pssend(message, destination):
asend((self(),message),destination)
while(1):
snd, message = arecv(ANY)
if(message == ACK):
break
datastruct.add(snd, message)

def psreceive(sender):
dummy = Message(null)
asend(self(),dummy) //self is my id

while(1):
snd, message = arecv(ANY)
if(message == dummy):
break
datastruct.add(snd, message)

if (datastruct.match(sender)):
src, msg = datastruct.get(sender)
asend((self(),ACK), src)
return msg
else:
return None
</source>

== Esame 17/07/2018 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2018.07.17.tot.pdf 2018.07.17.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
/* 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();
}
}
</source>
 

=== Esercizio c.2 ===
<source lang="c">
stack s;
semaphore mutex(1); // mutua esclusione
semaphore ok2consume(0);

Procedure entry: void push(int value)
{
mutex.P();
s.push(value)
mutex.V()
ok2consume.V()
}

Procedure entry: int pop()
{
int value;
ok2consume.P();
mutex.P();
value = s.pop();
mutex.V();
return value;
}
</source>
 

=== 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.

<source lang="c">
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
}
</source>
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) ===
a) Nei sistemi embedded o in computer ad uso specifico in cui sono richiesti tempi di risposta molto rapidi. La memoria virtuale può generare ritardi imprevedibili e può richiedere un supporto hardware per la traduzione da indirizzi virtuali ad indirizzi fisici. Ma in sistemi embedded non sempre c'è spazio fisico per implementare questi supporti hardware. 
b) 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. 
c) Serve ad aumentare le performance, rendere il sistema resiliente alla perdita di uno o più dischi e poterli rimpiazzare senza interrompere il servizio. RAID serve per tutelarsi dai problemi hardware, non sostituisce i backup in quanto ci permette solo di proseguire il lavoro, non ci permette di recuperare file cancellati o bloccati da ransomware. 
d) Per dimostrare questo occorre una variante del grafo di Holt, detto grafo Wait-For, che si costruisce eliminando i nodi di tipo risorsa e collassando gli archi appropriati, per cui il grafo di Holt contiene un ciclo se e solo se il grafo Wait-For contiene un ciclo e pertanto si ha l'attesa circolare (deadlock).
 

== Esame 28/05/2019 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2019.05.18.tot.pdf 2019.05.18.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor storage{
int stored[16]
int components[16]
condition ok2make[16]
boolean required[16] //false

void add(components){
stored += components;
for(i=0; i< 16; i ++){
if(required[i] == true)
ok2make(i).signal();
}
}

void get(components){
for(i = 0; i< 16; i++){
if (stored[i] >= components[i])
stored[i] -= components[i]
else
required[i] = true
ok2make(i).wait();
required[i] = false
i—;

}
}
</source>

 
 

== Esame 21/06/2018 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2018.06.21.tot.pdf 2018.06.21.tot.pdf]
=== Esercizio c.1 (sbagliato) ===
<source lang="c">
/* 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();
}
}

</source>
 

=== Esercizio c.1 ===
<source lang="c">
/* 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();
}
</source>
 

=== Esercizio c.2 (sbagliato) ===
<source lang="c">

#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();
}
}
</source>
 

=== Esercizio c.2 ===
Soluzione "furba e facile"
<source lang="c">
#define N n // limite operazioni
class lim_semaphore()
{
semaphore plus;
semaphore minus;
int value; //serve per significato

init(x) : { value=x; plus.init(N+x); minus.init(N-x);} //costruttore
P() : { plus.P(); value--; minus.V(); }
V() : { minus.P(); value++; plus.V(); }
}
</source>
 

Soluzione "schiacciasassi"
<source lang="c">
#define N n // limite operazioni

class lim_semaphore()
{
semaphore mutex;
queue of semaphore okmin, okmax;
int value;
init(x) : { value=x; }
P() {
mutex.P();
if (value <= -N) {
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();
}
}
V() {
mutex.P();
if (value >= -N) {
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();
}
}
}
</source>
 

=== Esercizio g.1 ===
<nowiki>
IC = 10,10,10
COH = 4,4,4

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</nowiki>
 

Minimizzato

<nowiki>
IC = 4,4,4 //massimo
COH = 1,1,1 //soldi in cassa

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</nowiki>
 

=== Esercizio g.2 (da controllare) ===
a) L'algoritmo di calcolo del working set serve a limitare il problema del trashing assicurandosi che le pagine di cui ha bisogno un processo (una loro approssimazione) siano già caricate in memoria prima di far partire il processo stesso. L'algoritmo viene eseguito ogni volta che avviene un page fault, cercando una pagina "vittima" non presente nel working set e sfrattandola, facendo posto alla pagina che occorre al processo in esecuzione. 
b) 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. 
c) Un virus necessità l'intervento umano per essere avviato o per essere diffuso. Si attacca a programmi o file per potersi diffondere. Un worms è in grado di riprodursi e di diffondersi autonomamente, sfruttando le informazioni presenti sul computer. 
d) La ready queue di uno scheduler può essere vuota quando tutti i processi sono in esecuzione su diversi processori, oppure quando tutti i processi hanno terminato la loro esecuzione. È un caso fisiologico della vita di un sistema.

== Esame 28/05/2018 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2018.05.28.tot.pdf 2018.05.28.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
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();
}
}
</source>
 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
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();
}
</source>
 
=== Esercizio c.2 (da controllare) ===
<source lang="c">
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'
}
</source>
 
== Esame 12/02/2018 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2018.02.12.tot.pdf 2018.02.12.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
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

p.e. 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
}
p.e. 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
}

p.e. ship_enter(int direction){
if (bridge = DOWN || shipping[direction] != 0 || waitingC > 0)
{
waitingS[i]++; ok2ship[i].wait(); waitingS[i]--;
}
isBridgeUp = false;
shipping[i] = 1;

p.e. 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
}
</source>

=== Esercizio c.1 (da controllare) ===
<source lang="c">
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}

p.e. 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();

}

p.e. 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();
}

p.e. 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();

}

p.e. 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();

}
</source>

=== Esercizio c.1 (sbagliato) ===
<source lang="c">
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();
}
}
</source>

=== Esercizio c.1 2o (sbagliato) ===
<source lang="c">
#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

p.e. 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--;
}

p.e. car_exit(int direction){
carsOnBridge--;
last2pass = car;
if(carsOnBridge == 0 && waitingS>0){
isBrigdeUp = true;
ok2ship.signal;
}
}

p.e. 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;

}
}

p.e. 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;
}
}
</source>
 
=== Esercizio c.2 (da controllare) ===
<source lang="c">
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)

</source>

== Esame 11/09/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.09.11.tot.pdf 2017.09.11.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
monitor crossing

ok2dir[4]; //NESW
bool busy = false;

pe entra(int dir)
if (busy)
ok2dir[dir].wait();
busy = true;

pe esci(int dir)
busy = false;
ok2dir[(dir + 1) % 4].signal();
if (!busy)
ok2dir[(dir + 2) % 4].signal();
if (!busy)
ok2dir[(dir + 3) % 4].signal();
if (!busy)
ok2dir[(dir + 4) % 4].signal(); //dir

//alternativa più compatta
pe esci(int dir)
busy = false;
for (i = 0; i < 4; i++)
if (!busy)
ok2dir[(dir + i + 1) % 4].signal();

</source>
 

=== Esercizio c.2 (da controllare) ===
<source lang="c">
// server[] = array contenente il PID di tutti i server

#define BROADCAST server[0]

server[0]
{
while(true)
{
<msg, sender> = arecv(*); // ricevo il messaggio
if (sender == BROADCAST)
print(msg); // se il messaggio l'ho ricevuto da me stesso allora lo stampo
else
asend(*, <msg, getpid()>); // se il messaggio l'ho ricevuto da un client o da un altro server lo inoltro a tutti i server (compreso me stesso)
}
}

server[x] // x = 1...N-1
{
while(true)
{
<msg, sender> = arecv(*); // ricevo il messaggio
if (sender == BROADCAST)
print(msg); // se il messaggio l'ho ricevuto dal server[0] allora lo stampo
else
asend(BROADCAST, <msg, getpid()>) // se il messaggio l'ho ricevuto da un client lo inoltro al server[0]
}
}
</source>
 

== Esame 17/07/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
monitor conf {
condition finished;
condition ready2present[max];
bool arrived[max] = false;
bool giachiamato[max] = false;

p.e. chiama(chiamato){
if(arrived[chiamato] == true)
ready2present[chiamato].signal;
finished.wait;
return true;
else
giachiamato[chiamato]= true
return false;
}

p.e. arrivato(nome){
if(giachiamato[nome] == true)
return false;

arrived[nome] = true;
ok2present[nome].wait;
return true;
}

p.e. finepresentazione(nome){
finished.signal;
}
}

</source>

=== Esercizio c.2 (da controllare) ===
<source lang="c">
si, è possibile:

Implementare asend e arecv date bsend e brecv

asend(pid_t, msg_type msg){
bsend (<pid_t dst, msg>);
}

arecv(*){
pid_t act = getpid(); \\ act = proprio pid
do{
<dst, msg> = brecv(*);
}while (dst =! act)
return msg;
}

</source>
 

== Esame 19/06/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.06.19.tot.pdf 2017.06.19.tot.pdf]
=== Esercizio c.1 (da controllare)===
<source lang="c">
#define NATLETI n

condition ok2lancia[NATLETI];
condition ok2giudice;

int counter[NATLETI];
int ultimo_tiro;
float registro[NATLETI][3];

Procedure entry: boolean pronto(int i)
{
if(!(i == 0 && counter[i] == 0)) // se è il primo lancio non devo metterlo in wait
ok2lancia[i].wait()
if(counter[i] < 3)
return true;
else
return false;
}

Procedure entry: void lanciato (int i)
{
counter[i]++;
ultimo_tiro = i;
ok2giudice.signal();
}

Procedure entry: int lanciofatto()
{
ok2giudice.wait()
if(ultimo_tiro == NATLETI-1 && counter[0] == 3)
return -1; // devo invalidare la condizione per uscire dal while, quindi se nessuno deve più lanciare ritorno -1
else
return ultimo_tiro;
}

Procedure entry: void registraechiama(int i, float m)
{
registro[i][counter[i]-1] = m; // il secondo indice indica l'iesimo lancio -1 (perchè iniziamo a contare da zero)
if(i == NATLETI-1) // se ha appena tirato l'ultimo atleta non posso dare il via a NATLETI (perchè non esiste), quindi faccio ricominciare il giro
ok2lancia[0].signal();
else
ok2lancia[i+1].signal();
}

Procedure entry: int classifica()
{
int best[NATLETI];
for(int i = 0; i < NATLETI; i++)
{
for(int j = 0; j < 3; j++)
{
if(registro[i][j] > best[i])
best[i] = registro[i][j];
}
}
best.sort_in_descending_order(); // supponiamo nel nostro pseudolinguaggio esista una funzione di ordinamento qualunque
return best;
}
</source>
 

== Esame 29/05/2017 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2017.05.29.tot.pdf 2017.05.29.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
condition okpartita
condition ok2chiama
condition ok2punteggio
condition ok2run[2][MAX]
int numpronti
int punteggio[2]
boolean partita=false
boolean partitafinita=false
chiamati = []
contabandiera[2]
int winner

p.e. nuovapartita():
{
punteggio[A] = punteggio[B] = 0;
numpronti = 0;
partita=true;
okpartita.signal()
chiamati = [];
}
p.e. chiama(l):
{
if (numpronti<2*MAX)
{
ok2chiama.wait();
}
chiamati = l;
contabandiera[A] = contabandiera[B] = 0
winner = -1;
for (s in n)
{
ok2run[A][s].signal();
ok2run[B][s].signal()
}
ok2punteggio.wait();
punteggio[winner++]
if (max(punteggio) == 10)
{
partitafinita = true;
for (s in A,B)
{
for (n in range(MAX))
{
ok2run[s][n].signal();
}
}
}
return punteggio;
}
p.e. pronto(s, n):
{
if (partitafinita) return 1;
if (!partita)
{
okpartita.wait();
}
numpronti++;
if (numpronti>=2*MAX)
{
ok2chiama.signal();
}
if (!(n in chiamati))
{
ok2run[s][n].wait();
}
numpronti--;
return 0 if partita else 1;
}
allabandiera(s, n):
{
contabandiera[s]++;
if (winner == -1 && contabandiera[s] == len(chiamati))
{
winner = s;
}
if (contabandiera[A] == len(chiamati) && contabandiera[B] == len(chiamati))
{
ok2punteggio.signal();
}
}

casi da discutere:
se arrivano studenti a pronto prima che il prof dichiara nuovapartita succedono guai.
</source>
 

== Esame 14/02/2015 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2015.02.14.tot.pdf 2015.02.14.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor altcolbb {

generic_type valueBuf[MAX];
int front = rear = 0;

bool isFull = false;

condition ok2write[2]; //gli indici sono i colori (red=0, blue=1)

lastColor = None;

p.e. void write(color_t color, generic_type val) {

if (front == rear)
if(isFull)
ok2write[color].wait();
else
if (lastColor == color)
ok2write[color].wait();

valueBuf[front] = val;
front = (front+1) % MAX;
lastColor = color;

if (front == rear)
isFull = true;
else
ok2write[1-color].signal();

ok2read.signal();

}

p.e. generic_type read(void) {

if (rear == front)
if (!isFull)
ok2read.wait();

generic_type tmpValue = valueBuf[rear];

rear = (rear + 1) % MAX;
if (rear == front)
isFull = false;
color_t tmpColor = lastColor;
lastColor = None;
ok2write[tmpColor].signal(); //quando un lettore legge l'ultimo elemento
//dal buffer, ci possono solo essere scrittori
//in attesa che abbiano lo stesso colore
//dell'ultimo elemento.
else
ok2write[1-lastColor].signal();

return tmpValue;

}

}
</source>
 

=== Esercizio c.1 (da controllare) ===
<source lang="c">
#define MAX n

condition ok2read;
condition ok2write;
condition ok2red;
condition ok2blue;

queue buffer;

Procedure entry: void write(color_t color, generic_type val)
{
if(buffer.lenght() >= MAX)
ok2write.wait();
if((<color> == buffer.last()) == color)
{
if(color == red)
ok2red.wait();
else
ok2blue.wait();
}
buffer.enqueue(<color, val>);
ok2read.signal();
if(buffer.lenght() < MAX)
{
if(color == red)
ok2blue.signal();
else
ok2red.signal();
}
}

Procedure entry: generic_type read(void)
{
generic_type val;
if(buffer.lenght == 0)
ok2read.wait();
<val> = buffer.dequeue();
ok2write.signal()
return val;
}
</source>
 

=== Esercizio g.1 (da controllare) ===
a) 
MIN:
<nowiki>
Stringa di riferimenti: 0 1 2 3 4 5 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0
Frame 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Frame 2: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Frame 3: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Frame 4: 3 4 5 5 5 5 3 4 4 4 4 3 3 3 3 3 3 3
</nowiki>

FIFO:
<nowiki>
Stringa di riferimenti: 0 1 2 3 4 5 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0
Frame 1: 0 0 0 0 4 4 4 4 2 2 2 2 1 1 1 1 1 1 1 1 1
Frame 2: 1 1 1 1 5 5 5 5 3 3 3 3 2 2 2 2 2 2 2 2
Frame 3: 2 2 2 2 0 0 0 0 4 4 4 4 3 3 3 3 3 3 3
Frame 4: 3 3 3 3 1 1 1 1 0 0 0 0 0 0 0 0 0 0
</nowiki>

B) 
MIN:
<nowiki>
Stringa di riferimenti: 0 1 2 3 4 0 1 2 3 0 1 4 2 0 3 4 1 2 3 4
Frame 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
Frame 2: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
Frame 3: 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3
Frame 4: 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
</nowiki>
 

== Esame 20/01/2015 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2015.01.20.tot.pdf 2015.01.20.tot.pdf]

=== Esercizio c.1 (da controllare) ===
<source lang="c">
#define MAX n

condition ok2read;
condition ok2write;

queue buffer;
int waiting_write = 0;
int waiting_read = 0;

Procedure entry: void write(generic_type val)
{
if (buffer.lenght() >= MAX)
{
if (waiting_write >= MAX)
{
buffer.dequeue(); // il valore va perso
ok2write.signal();
}
waiting_write++;
ok2write.wait();
waiting_write--;
}
buffer.enqueue(val);
ok2read.signal();
}

Procedure entry: generic_type read(void)
{
generic_type val;
if (buffer.lenght() == 0)
{
if (waiting_read >= MAX)
{
ok2read.signal();
}
waiting_read++;
ok2read.wait();
waiting_read--:
}
if (buffer.lenght() == 0)
val = NULL;
else
val = dequeue;
ok2write.signal()
return val;
}
</source>
 

=== Esercizio g.1 (da controllare) ===
a) 
MIN:
<nowiki>
Stringa di riferimenti: 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1
Frame 1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Frame 2: 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Frame 3: 3 4 5 5 5 3 4 4 4 3 3 3 3
</nowiki>

LRU:
<nowiki>
Stringa di riferimenti: 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1
Frame 1: 1 1 1 4 4 4 2 2 2 1 1 1 1 1 1
Frame 2: 2 2 2 5 5 5 3 3 3 2 2 2 2 2
Frame 3: 3 3 3 1 1 1 4 4 4 3 3 3 3
</nowiki>

B) 
Il problema si può risolvere utilizzando l'algoritmo LRU e la seguente stringa di riferimenti:
<nowiki>
Stringa di riferimenti: 4 3 2 1 5 3 2 4 1 5 4 3 2
Frame 1: 4 4 4 4 5 5 5 5 1 1 1 1 1
Frame 2: 3 3 3 3 3 3 3 3 5 5 5 2
Frame 3: 2 2 2 2 2 2 2 2 2 3 3
Frame 4: 1 1 1 1 4 4 4 4 4 4
</nowiki>
 

== Esame 16/07/2014 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2014.07.16.tot.pdf 2014.07.16.tot.pdf]
=== Esercizio c.1 ===
<source lang="c">
/* Monitor Bounded Buffer: (non richiesto dall'esercizio) */
queue q;
condition oktoread; // q.length() > 0
condition oktowrite; // q.length() < MAX

procedure entry type read():
if (q.length() == 0) oktoread.wait(); // controllo
retval = q.dequeue(); // cambio lo stato
// abilito coloro che possono essere abilitati dal cambiamento di stato
oktowrite.signal()
return retval;

procedure entry void write(type elem):
if (q.length() >= MAX) oktowrite.wait(); //controllo
q.enqueue(elem); // cambio lo stato
oktoread.signal(); // abilito chi può essere abilitato

/* NOTE:
* procedure entry ==> dichiarazione di funzioni (senza vedere l'implementazione
* dall'esterno)
*/
</source>
 
<source lang="c">
/* Min-Max Monitor Bounded Buffer: */

Queue Q;

// Condition: OKTOREAD: Q.Length > MIN
// Condition: OKTOWRITE: Q.Length < MAX

procedure entry: Type Read():
{
if (Q.Length <= MIN) OKTOREAD.Wait(); // Controllo
retval = Q.Dequeue(); // Cambio di stato
OKTOWRITE.Signal(); // Abilito chi vuole scrivere
return retval; // Qui sono sicuro perchè ne ho eliminato uno prima
}

procedure entry: void Write(Type elem):
{
if (Q.Length >= MAX) OKTOWRITE.Wait() // Controllo
Q.Enqueue(elem); // Cambio di stato
if (Q.Length > MIN) OKTOREAD.Signal(); // Abilito chi vuole leggere
}
</source>
 
=== Esercizio c.2 ===
<source lang="c">
Semaphore mutex = 1;

struct Elem
{
Semaphore s;
int counter;
}

struct Elem V[]; // Vettore a dimensione variabile. I nuovi elementi sono initializzati a s = 0, counter = 0.

void RendezVouz(int n)
{
mutex.P(); // Blocco, decremento di 1 (il processo si blocca se il semaforo vale 0)
V[n].counter++;
if (V[n].counter < n)
{
mutex.V(); // Rilascia, incrementa di 1
V[n].s.P();
}
V[n].counter--;
if (V[n].counter > 0)
V[n].s.V();
else
mutex.V();
}
</source>
 

=== Esercizio g.1 ===
<source lang=html5>
0241302 ==> soluzione corretta
(0)2 2200
(1)3 1111
(2)4 4442
(3)0 0333

2 3 4 0 1 2 3 4 0 1 2 3 ==> soluzione proposta, non corretta perchè non è la stringa più corta
2 1 1 1 1 0 0 0 0
3 3 2 2 2 2 1 1 1
4 4 4 3 3 3 3 2 2
0 0 0 0 4 4 4 4 3
</source>
 

== Esame 03/06/2014 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2014.06.03.tot.pdf 2014.06.03.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor sabelev
{
#define N n //numero dei piani

condition ok2enter[N][2]; //piano di partenza e direzione
condition ok2exit[N]; //piano di arrivo

procedure entry: void atfloor(int floor, int direction)
{
ok2exit[floor].signal(); //da il via al primo del piano che deve uscire
ok2enter[floor][direction].signal(); //da il via al primo del piano che deve entrare e deve andare in questa direzione
}

procedure entry: void enter(int from, int to)
{
int direction;
if(to > from) //controllo sulla direzione
direction = 0;
else
direction = 1;

ok2enter[from][direction].wait(); //mi fermo in attesa che arrivi l'ascensore
ok2enter[from][direction].signal(); //quando arriva l'ascensore do il via a quello in attesa dopo di me
ok2exit[to].wait(); //mi fermo dentro all'ascensore in attesa di uscire
}

procedure entry: void exit(int from, int to)
{
ok2exit[to].signal(); //do il via ad un altro che deve uscire a questo piano come me
}

}
</source>
 

== Esame 21/02/2014 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2014.02.21.tot.pdf 2014.02.21.tot.pdf]
=== Esercizio c.1 (da controllare) ===
<source lang="c">
monitor bbwl
{
#define MAXELEM n

condition ok2read;
condition ok2write;
condition ok2log;

queue q1;
queue q2;

procedure entry: void write(eltype elem)
{
if (q1.size() >= MAXELEM)
ok2write.wait();
q1.enqueue(elem);
ok2log.signal();
}

procedure entry: eltype read()
{
if (q2.size == 0)
ok2read.wait();
eltype elem = q2.dequeue();
ok2write.signal();
return elem;
}

procedure entry: eltype log()
{
if (q1.size() == 0)
ok2log.wait();
eltype elem = q1.dequeue();
q2.enqueue(elem);
ok2read.signal()
return elem;
}
}
</source>
 

== Esame 11/05/2011 ==
[http://www.cs.unibo.it/~renzo/so/compiti/2011-05-11.con.pdf 2011-05-11.con.pdf]
=== Esercizio 2 (da controllare) ===
<source lang="c">
stack s;
semaphore mutex(1);

lifocs_enter()
{
s.push(getpid());
mutex.p();
while(s.lastElement() != getpid())
{
mutex.v();
mutex.p();
}
s.pop();
}

lifocs_exit()
{
mutex.v();
}
</source>
 

== Esame Pratico 21/09/2018 ==
http://www.cs.unibo.it/~renzo/so/pratiche/2018.09.21.pdf
=== Esercizio 1 ===
<source lang="c">
#define _GNU_SOURCE
#include <sys/signalfd.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <unistd.h>
#include <time.h>
#include <string.h>

int main(int argc, char * argv[]){
sigset_t mask;
struct signalfd_siginfo fdsi;
int fd;
char* t;
char* filename;

sigemptyset(&mask);
sigaddset(&mask, SIGUSR1);
sigaddset(&mask, SIGUSR2);
sigprocmask(SIG_SETMASK, &mask, NULL);

int sigfd = signalfd(-1, &mask, 0);

for(;;){
read(sigfd, &fdsi, sizeof(struct signalfd_siginfo));
if(fdsi.ssi_signo == SIGUSR1){
asprintf(&filename, "./%u", fdsi.ssi_pid);
fd = open(filename, O_APPEND | O_CREAT | O_WRONLY);
time_t stime = time(NULL);
t = ctime(&stime);
write(fd, t, sizeof(char)*strlen(t));
close(fd);
}
if(fdsi.ssi_signo == SIGUSR2){
asprintf(&filename, "./%u", fdsi.ssi_pid);
fd = open(filename, O_APPEND | O_CREAT | O_WRONLY);
time_t stime = time(NULL);
t = ctime(&stime);
write(fd, t, sizeof(char)*strlen(t));
close(fd);
}
}
}

dovrebbe stampare anche il nome del segnale prima di stampare il tempo ma per il resto va bene

</source>
 

=== Esercizio 3 ===
<source lang="python">
#!/usr/bin/env python
import sys
import os
import re
dict = {}

def func(a):
os.chdir(a)
for root, dirs, files in os.walk("."):
for filename in files:
try:
fl =file(filename)
firstline = fl.readline()
fl.close()
except IOError: # caso di file che non riesce ad aprire
#print("could not read", file)
pass
if (re.match('^#!', firstline)):
dict.setdefault(firstline, []) #firstline include anche il carattere \n, quindi quando si stampa va anche a capo
dict[firstline].append(filename)
for k in dict.keys():
print k
for v in dict[k]:
print v
#print(" ")

if __name__ == '__main__':
if (len(sys.argv)==1):
dir = "."
else:
dir = sys.argv[1]
func(dir)

</source>

== Esame Pratico 22/01/2016 ==
http://www.cs.unibo.it/~renzo/so/pratiche/2016.01.22.pdf
=== Esercizio 1 ===
<source lang="c">
#include <stdlib.h>
#include <stdio.h>
#include <dirent.h>
#include <sys/types.h>
#include <string.h>
#include <unistd.h>

typedef struct nameNumber {
char *name;
int value;
} nameNumber;

int prefixToInt (char *string) {

int i = 0;
int num = 0;
while (string[i] >= '0' && string[i] < '9' && i < strlen(string)) {
num = (num*10) + (string[i]-'0');
i++;
}
return num;

}

void fileSort(struct nameNumber **files) {

}

int comp (const void * el1, const void * el2) {
struct nameNumber *f = *((nameNumber**)el1);
struct nameNumber *s = *((nameNumber**)el2);
if (f->value > s->value) return 1;
if (f->value < s->value) return -1;
return 0;
}

int main(int arg, char* argv[]) {

struct nameNumber **files;

DIR *dir;
struct dirent *ent;

int count = 0;

if((dir = opendir(argv[1])) != NULL)
{
while( (ent = readdir(dir)) != NULL )
{
if (ent->d_name[0] < '9' && ent->d_name[0] >= '0')
{
files = (struct nameNumber**)realloc(files , (count+1) * sizeof(struct nameNumber*));
files[count] = (struct nameNumber*)malloc(sizeof(struct nameNumber));
files[count]->name = (char*)malloc(sizeof(char)*strlen(ent->d_name) + 1);
strcpy(files[count]->name, ent->d_name);
files[count]->value = prefixToInt(files[count]->name);
printf("name : %s , value : %d\n", files[count]->name , files[count]->value);
count++;
}
}
}

qsort(files, count, sizeof(nameNumber*), comp);

int i;
for (i=0; i < count; i++) {
printf("%s\n",files[i]->name);
}

}

</source>

Dispense del Corso - Appunti Condivisi

2020-03-23T08:25:14Z

Laufragor: /* Formato PDF */

Gli studenti del corso di Sistemi Operativi a.a. 2019-2020 hanno collaborato alla creazione di appunti-dispense condivisi, scritti durante le ore di lezione e spesso rimaneggiati in un secondo momento. La stesura degli appunti è disponibile alla pagina [https://etherpad.wikimedia.org/p/so1920.cs.unibo.it so1920.cs.unibo.it], un'istanza Etherpad pubblica di Wikimedia.

== Formato PDF ==
Per una consultazione offline e più agevole delle note, ne viene fornita una versione PDF, liberamente consultabile e scaricabile dalla sezione [[#Download|Download]].

=== Realizzazione ===
La conversione di queste note in formato PDF è avvenuta tramite il convertitore [https://pandoc.org/ pandoc], configurandolo con le opportune opzioni. È possibile scaricare l'archivio contenente il materiale (script di conversione, intestazioni LaTeX, logo ecc.) utile alla conversione specificamente per le note del pad [https://etherpad.wikimedia.org/p/so1920.cs.unibo.it so1920.cs.unibo.it] dalla sezione [[#Download|Download]].

== Portare avanti la tradizione ==
Se siete studenti di anni accademici successivi al 2019-2020, gestire un pad di appunti convidisi per l'anno corrente è facile! [https://pandoc.org/ pandoc] fornisce miriadi di personalizzazioni e la possibilità di scaricare in automatico testo grezzo da indirizzi URL.

=== Testo grezzo Etherpad ===
Per ottenere il testo in formato testuale da un pad Etherpad, è sufficiente seguire dall'interfaccia web il percorso <code>Tasto Import/Export > Plain Text</code>. Tale opzione è utile per chi volesse, ad esempio, passare l'URL di scaricamento testuale a [https://pandoc.org/ pandoc].

== Download ==
* [[Media:SistemiOperativi1920.pdf|SistemiOperativi1920.pdf]]: conversione in PDF delle note del pad [https://etherpad.wikimedia.org/p/so1920.cs.unibo.it so1920.cs.unibo.it].
* [[Media:Converter1920.tgz|Converter1920.tgz]]: strumenti per la conversione PDF di [https://etherpad.wikimedia.org/p/so1920.cs.unibo.it so1920.cs.unibo.it].

Esercizi di "lettura" programmi in Python 2019/20

2019-12-04T14:30:48Z

Laufragor: /* 5 */

Gli esercizi proposti sono programmi funzionanti.

Come svolgimento dell'esercizio si deve:
* determinare lo scopo del programma
* modificare, migliorare discutere le soluzioni proposta. Proporre soluzioni alternative dello stesso problema.

==1==
<source lang=python>
def dd(s):
d,m,y = s.split('.')
d,m,y = int(d),int(m),int(y)
md = [0,31,28,31,30,31,30,31,31,30,31,30,31]
if y % 4 == 0:
md[2]=29
dy = d
for i in range(1,m):
dy += md[i]
return dy

if __name__ == "__main__":
data=input("Dammi una data (es. 14.03.2014): ")
print("il risultato della funzione misteriosa e' ", dd(data))
</source>

==2==
<source lang=python>
def imin(l):
im,mn = 0,l[0]
for i in range(1,len(l)):
if l[i]<mn:
im,mn = i,l[i]
return im

if __name__ = "__main__":
l = input('dammi in input una lista di elementi (es: [1,2,3]): ')
print("l'output della funzione misteriosa e': ", imin(l))
</source>

==3==
<source lang=python>
def r13(s):
e = ''
for c in s:
if 'A' <= c <= 'Z':
e += chr(((ord(c)-ord('A')) + 13)%26 + ord('A'))
elif 'a' <= c <= 'z':
e += chr(((ord(c)-ord('a')) + 13)%26 + ord('a'))
else:
e += c
return e

if __name__ == "__main__":
s = input("scrivi una semplice frase (es: 'Ciao Mondo') ")
r = r13(s)
print("il risultato della funzione misteriosa e': ", r)
print("consiglio: prova a eseguire nuovamente il programma scrivendo")
print("la frase: ", r)
</source>

==4==
<source lang=python>
def pf(n):
f = []
for i in range(2,n+1):
while n % i == 0:
f.append(i)
n //= i
if n == 1:
break
return f

if __name__ == "__main__":
n = int(input("dammi un numero (consigliato da 2 a 1000): "))
print("il risultato della funzione misteriosa e' ", pf(n))
</source>

==5==
(richiede il modulo turtle)

<source lang=python>
import turtle
import random

def cy(r):
turtle.setup(400,400)
turtle.penup()
turtle.hideturtle()
turtle.speed(0)
for i in range(1000):
x,y = random.randint(-200,200),random.randint(-200,200)
if (x*x + y*y)**0.5 < r:
color = "red"
else:
color = "blue"
turtle.goto(x,y)
turtle.dot(5,color)

if __name__ == "__main__":
r = float(input("scrivi un numero (consigliato da 100 a 200): "))
print("guarda il risultato della funzione misteriosa")
cy(r)
turtle.exitonclick()
</source>

==6==
(richiede il modulo turtle)

<source lang=python>
import turtle

def poly(n):
for i in range(n):
turtle.forward(50)
turtle.left(360/n)

if __name__=="__main__":
n=int(input("dammi un intero (consigliato da 3 a 12): "))
poly(n)
turtle.exitonclick()
</source>

==7==
Questo e' contorto. Se vi piace... iniziate a preoccuparvi: state diventando informatici ;-)
<source lang=python>
f="f={0}{1}{0};print(f.format(chr(34),f))";print(f.format(chr(34),f))
</source>
NB: non e' necessario capire questo programma, e' solo per chi si vuole cimentare in una sfida...

==8==
<source lang=python>
def pf(n):
f=[]
for i in range(2,n+1):
while n % i == 0:
f.append(i)
n //= i
if n == 1:
break
return f

def fgcd(a,b):
def rgcd(fa,fb):
if fa and fb:
if fa[0]==fb[0]:
return fa[:1]+rgcd(fa[1:],fb[1:])
elif fa[0]<fb[0]:
return rgcd(fa[1:],fb)
else:
return rgcd(fa,fb[1:])
else:
return []
return rgcd(pf(a),pf(b))

def flcm(a,b):
def rlcm(fa,fb):
if fa and fb:
if fa[0]==fb[0]:
return fa[:1]+rlcm(fa[1:],fb[1:])
elif fa[0]<fb[0]:
return fa[:1]+rlcm(fa[1:],fb)
else:
return fa[:1]+rlcm(fa,fb[1:])
else:
return fa if fa else fb
return rlcm(pf(a),pf(b))

def mul(l):
rv=1
for el in l:
rv *= el
return rv

def gcd(x,y):
return mul(fgcd(x,y))

def lcm(x,y):
return mul(flcm(x,y))

if __name__=="__main__":
a,b=input("Inserisci due numeri (es: 48 36): ").split()
a,b=int(a),int(b)
print("pf({})={}".format(a,pf(a)))
print("pf({})={}".format(b,pf(b)))
print("fgcd({},{})={}".format(a,b,fgcd(a,b)))
print("flcm({},{})={}".format(a,b,flcm(a,b)))
print("gcd({},{})={}".format(a,b,gcd(a,b)))
print("lcm({},{})={}".format(a,b,lcm(a,b)))
</source>

==9==
<source lang=python>
def div(n):
return {x for x in range(1,n+1) if n % x == 0}

#alternativa:
#def div(n):
# d=set()
# for x in range(1,n+1):
# if n % x == 0: d.add(x)
# return d

def gcd(a,b):
return max(div(a) & div(b))

def mul(n,limit):
return {x*n for x in range(1,limit//n + 1)}

#alternativa
#def mul(n,limit):
# d=set()
# for x in range(1,limit//n + 1):
# d.add(x*n)
# return d

def lcm(a,b):
return min(mul(a,a*b) & mul(b,a*b))

if __name__=="__main__":
a,b=input("Inserisci due numeri (es: 48 36): ").split()
a,b=int(a),int(b)
print("div({})={}".format(a,div(a)))
print("div({})={}".format(b,div(b)))
print("mul({},{})={}".format(a,a*b,mul(a,a*b)))
print("mul({},{})={}".format(b,a*b,mul(b,a*b)))
print("gcd({},{})={}".format(a,b,gcd(a,b)))
print("lcm({},{})={}".format(a,b,lcm(a,b)))
</source>

==10==
<source lang=python>
def sdiv(n):
return {x for x in range(2,n) if n % x == 0}

#alternativa:
#def sdiv(n):
# d=set()
# for x in range(2,n):
# if n % x == 0: d.add(x)
# return d

def pr(n):
return not sdiv(n)

def pdiv(n):
return {x for x in sdiv(n) if pr(x)}

#alternativa:
#def pdiv(n):
# d=set()
# for x in sdiv(n):
# if pr(x): d.add(x)
# return d

def gcd(a,b):
csdiv=pdiv(a) & pdiv(b)
r=1
for x in csdiv:
while a % (r*x) == 0 and b % (r*x) == 0:
r *= x
return r

def lcm(a,b):
return a * b // gcd(a,b)

if __name__=="__main__":
a,b=input("Inserisci due numeri (es: 48 36): ").split()
a,b=int(a),int(b)
print("pdiv({})={}".format(a,pdiv(a)))
print("pdiv({})={}".format(b,pdiv(b)))
print("gcd({},{})={}".format(a,b,gcd(a,b)))
print("lcm({},{})={}".format(a,b,lcm(a,b)))
</source>
==11==
<source lang=python>
def tartline(l):
l[:0]=[1]
for i in range(1,len(l)-1):
l[i] += l[i+1]

l=[]
for i in range(12):
tartline(l)
print("{:^60}".format(str(l)))
</source>

==12==
<source lang=python>
def sdiv(n):
return {x for x in range(2,n) if n % x == 0}

#alternativa:
#def sdiv(n):
# d=set()
# for x in range(2,n):
# if n % x == 0: d.add(x)
# return d

def pr(n):
return not sdiv(n)

N=int(input("dammi il numero massimo (es 100): "))
print("ecco i numeri ***** fino a",N,":",[n for n in range(1,N+1) if pr(n)])
</source>

==13==
<source lang=python>
vf=[("Nella vecchia fattoria","Quante bestie ha zio Tobia","C'e' la capra","capra","ca"),
("Attaccato a un carrettino","C'è un quadrupede piccino","L'asinel","nel","nè"),
("Tra le casse e i ferri rotti", "Dove i topi son grassotti","C'è un bel gatto","gatto","ga"),
("Tanto grasso e tanto grosso", "Sempre sporco a più non posso", "C'è il maiale","iale","ia"),
("Poi sull'argine del fosso", "Alle prese con un osso", "C'è un bel cane","cane","ca"),
("Nella stalla silenziosa", "Dopo aver mangiato a iosa", "Dorme il bue","bue","bu")]
refrain="ia ia o"

def recverse(m,n):
v1,v2,an1,an2,an3=vf[m]
if n==m:
print(v1,refrain)
print(v2,refrain)
else:
recverse(m+1,n)
print(an1,an2,an3,an3,an2)

for i in range(len(vf)):
recverse(0,i)
print(vf[0][0],refrain)
print()
</source>

==14==
<source lang=python>
import turtle

def hser(size, level):
if level==0:
turtle.forward(size)
else:
hser(size,level-1)
turtle.left(45)
turtle.forward(size * 2**0.5)
turtle.left(45)
hser(size,level-1)
turtle.right(90)
turtle.forward(size)
turtle.right(90)
hser(size,level-1)
turtle.left(45)
turtle.forward(size * 2**0.5)
turtle.left(45)
hser(size,level-1)

def ser(size, level):
turtle.penup()
pos=(2**(level+2)-3) * size // 2 #posizione iniziale
turtle.setpos(-pos,pos)
turtle.pendown()
hser(size,level)
turtle.right(90)
hser(size,level)
turtle.right(90)
hser(size,level)
turtle.right(90)
hser(size,level)
turtle.right(90)

turtle.speed(0)
turtle.hideturtle()
ser(2,1)
ser(2,2)
ser(2,3)
ser(2,4)
turtle.exitonclick()
</source>
==15==
<source lang=python>
import turtle
import colorsys
import sys

def arrowstep(level, length, angle):
if level:
arrowstep(level-1, length/2, -angle)
turtle.left(angle)
arrowstep(level-1, length/2, angle)
turtle.left(angle)
arrowstep(level-1, length/2, -angle)
else:
turtle.forward(length)

def arrow(level, length):
if level & 1:
turtle.left(60)
arrowstep(level, length, -60)
else:
arrowstep(level, length, -60)

turtle.speed(0)
turtle.hideturtle()
turtle.colormode(1)
nmax=6
width=256
xmin= -width//2
ymin= -width*(3**0.5)//4
for n in range(nmax):
turtle.penup()
turtle.setposition(xmin,ymin)
turtle.setheading(0)
turtle.pencolor(colorsys.hls_to_rgb(1.0*n/6,0.5,1))
turtle.pendown()
arrow(n,256)

turtle.exitonclick()
</source>
==16==
<source lang=python>
def av(l):
return sum(l)/len(l)

def rg(l):
return max(l)-min(l)

def md(l):
lx=len(l)
ls=sorted(l)
if lx%2:
return ls[lx//2]
else:
return (ls[lx//2-1]+ls[lx//2])/2

if __name__=="__main__":
l=input("dammi una lista di numeri separati da virgole (es: 1,2,3,4.4): ")
l=[float(x) for x in l.split(',')]
print("i valori trovati dalle tre funzioni sono: {:.4f} {:.4f} {:.4f}".format(av(l),rg(l),md(l)))
</source>

==17==
<source lang=python>
import turtle
import sys

rows,cols=4,4
buttonsize=50
topdisplay=2*buttonsize

stack=[0]
fresh=True

def num(x):
global fresh,stack
if fresh:
stack[:0]=[x]
fresh=False
else:
stack[0]=stack[0]*10+x

enter,add,sub,mul,div=0,int.__add__,int.__sub__,int.__mul__,int.__floordiv__

def op(x):
global fresh,stack
if x!=enter and len(stack)>1:
stack=[x(stack[1],stack[0])]+stack[2:]
fresh=True

def off(x):
sys.exit(0)

buttons={
(0,0):('0',num,0), (1,0):('1',num,1), (1,1):('2',num,2), (1,2):('3',num,3), (2,0):('4',num,4),
(2,1):('5',num,5), (2,2):('6',num,6), (3,0):('7',num,7), (3,1):('8',num,8), (3,2):('9',num,9),
(3,3):('+',op,add), (2,3):('-',op,sub), (1,3):('*',op,mul), (0,3):('/',op,div),
(0,2):('ent',op,enter), (0,1):('off',off,0)}

def click(x,y):
col=x//buttonsize
row=y//buttonsize
if (row,col) in buttons:
label,op,val=buttons[row,col]
op(val)
drawcalc()

def drawcalc():
def drawbutton(col,row,label):
turtle.setpos(row*buttonsize,col*buttonsize)
turtle.pendown()
for _ in range(4):
turtle.forward(buttonsize)
turtle.left(90)
turtle.penup()
turtle.setpos(row*buttonsize+buttonsize//2,col*buttonsize+buttonsize//2)
turtle.write(label,align="center")
turtle.clear()
turtle.penup()
for row,col in buttons:
drawbutton(row,col,buttons[row,col][0])
turtle.setpos(row*buttonsize*(rows-1),col*buttonsize*(cols+1))
turtle.write(str(stack[0]),align="right")
turtle.update()

turtle.screensize(cols*buttonsize+1, rows*buttonsize+topdisplay+1)
turtle.setup(cols*buttonsize+1, rows*buttonsize+topdisplay+1)
turtle.setworldcoordinates(0,0,cols*buttonsize, rows*buttonsize+topdisplay)
turtle.hideturtle()
turtle.speed(10)
turtle.tracer(0)
drawcalc()
turtle.onscreenclick(click)
turtle.listen()
turtle.mainloop()
</source>

==18==
<source lang=python>
import turtle
import colorsys
import time

N=6
frompin=list(range(N,0,-1))
auxpin=[]
topin=[]

def rectangle(size, level, pin):
turtle.penup()
turtle.setpos(2*N*10*pin,level*10)
turtle.setheading(0)
turtle.pendown()
turtle.fillcolor(colorsys.hls_to_rgb(1.0*(size-1)/N,0.5,1))
turtle.begin_fill()
turtle.forward(size*10)
turtle.left(90)
turtle.forward(10)
turtle.left(90)
turtle.forward(size*20)
turtle.left(90)
turtle.forward(10)
turtle.left(90)
turtle.forward(size*10)
turtle.end_fill()

def showhanoi():
turtle.clear()
lf,la,lt=map(len,(frompin,auxpin,topin))
for i in range(lf):
rectangle(frompin[i], i, -1)
for i in range(la):
rectangle(auxpin[i], i, 0)
for i in range(lt):
rectangle(topin[i], i, 1)
turtle.update()
time.sleep(0.2)

def hanoi(n,f,a,t):
if n==1:
t.append(f.pop())
showhanoi()
else:
hanoi(n-1,f,t,a)
hanoi(1,f,a,t)
hanoi(n-1,a,f,t)

turtle.hideturtle()
turtle.speed(10)
turtle.tracer(0)
showhanoi()
hanoi(N,frompin,auxpin,topin)
turtle.exitonclick()
</source>
==19==
<source lang=python>
#!/usr/bin/env python3
# Copyright 2014 Renzo Davoli University of Bologna - Italy
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License along
# with this program; if not, write to the Free Software Foundation, Inc.,
# 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
#
import sys

class num:
def __init__(self,n):
self.val=n

class mul(num):
pass

class onemul(mul):
pass

class plus():
pass

class times():
pass

class numlanguage():
def __init__(self):
self.dict={}
def __setitem__(self,s,op):
self.dict[s]=op
for l in range(len(s)-1,0,-1):
if s[:l] in self.dict:
break
else:
self.dict[s[:l]]=None
return op
def match(self,s):
matchlen,obj=0,None
for l in range(1,len(s)+1):
if s[:l] in self.dict:
matchlen,obj=l,self.dict[s[:l]]
else:
break
return matchlen,obj

def str2num(langnum,s):
hi=mid=lo=last=0
lastop=None
while s:
if s[0] in " -\t\n":
s=s[1:]
else:
ml,obj=langnum.match(s)
if obj:
if isinstance(obj,num):
if isinstance(obj,mul):
if isinstance(obj,onemul) and lo == 0:
lo = 1
if (last <= obj.val or isinstance(lastop,times)) and not isinstance(lastop,plus):
hi,mid,lo = (hi+mid+lo)*obj.val,0,0
else:
hi,mid,lo = hi+(lo+mid)*obj.val,0,0
last=obj.val
else:
if obj.val == 100:
mid,lo = lo*obj.val if lo else obj.val,0
elif obj.val <= lo or isinstance(lastop,plus):
lo += obj.val
else:
lo = lo*obj.val if lo else obj.val
lastop=None
else:
lastop=obj
#print(s[:ml],hi,mid,lo,last,lastop)
s=s[ml:]
else:
return -1
return hi+mid+lo

def num_it():
nl=numlanguage()
nl["zero"]=num(0)
nl["uno"]=nl["un"]=nl["una"]=num(1)
nl["due"]=num(2)
nl["tre"]=num(3)
nl["quattro"]=num(4)
nl["cinque"]=num(5)
nl["sei"]=num(6)
nl["sette"]=num(7)
nl["otto"]=num(8)
nl["nove"]=num(9)
nl["dieci"]=num(10)
nl["undici"]=num(11)
nl["dodici"]=num(12)
nl["tredici"]=num(13)
nl["quattordici"]=num(14)
nl["quindici"]=num(15)
nl["sedici"]=num(16)
nl["diciassette"]=num(17)
nl["diciotto"]=num(18)
nl["diciannove"]=num(19)
nl["venti"]=nl["vent"]=num(20)
nl["trenta"]=nl["trent"]=num(30)
nl["quaranta"]=nl["quarant"]=num(40)
nl["cinquanta"]=nl["cinquant"]=num(50)
nl["sessanta"]=nl["sessant"]=num(60)
nl["settanta"]=nl["settant"]=num(70)
nl["ottanta"]=nl["ottant"]=num(80)
nl["novanta"]=nl["novant"]=num(90)
nl["cento"]=num(100)
nl["mille"]=onemul(10**3)
nl["mila"]=nl["migliaia"]=mul(10**3)
nl["milioni"]=nl["milione"]=mul(10**6)
nl["miliardi"]=nl["miliardo"]=mul(10**9)
nl["dozzine"]=nl["dozzina"]=mul(12)
nl["decine"]=mul(10)
nl["centinaia"]=mul(100)
nl["di"]=times()
nl["e"]=plus()
return nl

def num_en():
nl=numlanguage()
nl["zero"]=nl["null"]=num(0)
nl["one"]=nl["a"]=num(1)
nl["two"]=num(2)
nl["three"]=num(3)
nl["four"]=num(4)
nl["five"]=num(5)
nl["six"]=num(6)
nl["seven"]=num(7)
nl["eight"]=num(8)
nl["nine"]=num(9)
nl["ten"]=num(10)
nl["eleven"]=num(11)
nl["twelve"]=num(12)
nl["thirteen"]=num(13)
nl["fourteen"]=num(14)
nl["fifteen"]=num(15)
nl["sixteen"]=num(16)
nl["seventeen"]=num(17)
nl["eighteen"]=num(18)
nl["nineteen"]=num(19)
nl["twenty"]=num(20)
nl["thirty"]=num(30)
nl["forty"]=num(40)
nl["fifty"]=num(50)
nl["sixty"]=num(60)
nl["seventy"]=num(70)
nl["eighty"]=num(80)
nl["ninety"]=num(90)
nl["hundred"]=num(100)
nl["thousand"]=mul(10**3)
nl["million"]=mul(10**6)
nl["billion"]=mul(10**9)
nl["trillion"]=mul(10**12)
nl["dozen"]=mul(12)
nl["and"]=plus()
nl["of"]=times()
return nl

def num_fr():
nl=numlanguage()
nl["zero"]=num(0)
nl["un"]=num(1)
nl["deux"]=num(2)
nl["trois"]=num(3)
nl["quatre"]=num(4)
nl["cinq"]=num(5)
nl["six"]=num(6)
nl["sept"]=num(7)
nl["huit"]=num(8)
nl["neuf"]=num(9)
nl["dix"]=num(10)
nl["onze"]=num(11)
nl["douze"]=num(12)
nl["treize"]=num(13)
nl["quatorze"]=num(14)
nl["quinze"]=num(15)
nl["seize"]=num(16)
nl["vingt"]=num(20)
nl["trente"]=num(30)
nl["quarante"]=num(40)
nl["cinquante"]=num(50)
nl["soixante"]=num(60)
nl["cent"]=num(100)
nl["mille"]=onemul(10**3)
nl["million"]=mul(10**6)
nl["milliard"]=mul(10**9)
nl["douzaine"]=mul(12)
nl["et"]=plus()
nl["de"]=times()
return nl

def num_de():
nl=numlanguage()
nl["null"]=num(0)
nl["eins"]=nl["ein"]=num(1)
nl["zwei"]=nl["zwo"]=num(2)
nl["drei"]=num(3)
nl["vier"]=num(4)
nl["fÃ¼nf"]=num(5)
nl["sechs"]=num(6)
nl["sieben"]=num(7)
nl["acht"]=num(8)
nl["neun"]=num(9)
nl["zehn"]=num(10)
nl["elf"]=num(11)
nl["zwÃ¶lf"]=num(12)
nl["dreizehn"]=num(13)
nl["vierzehn"]=num(14)
nl["fÃ¼nfzehn"]=num(15)
nl["sechzehn"]=num(16)
nl["siebzehn"]=num(17)
nl["achtzehn"]=num(18)
nl["neunzehn"]=num(19)
nl["zwanzig"]=num(20)
nl["dreiÎ²ig"]=num(30)
nl["dreiÃig"]=num(30)
nl["vierzig"]=num(40)
nl["fÃ¼nfzig"]=num(50)
nl["sechzig"]=num(60)
nl["siebzig"]=num(70)
nl["achtzig"]=num(80)
nl["neunzig"]=num(90)
nl["hundert"]=num(100)
nl["tausend"]=mul(10**3)
nl["million"]=mul(10**6)
nl["milliard"]=mul(10**9)
nl["und"]=plus()
return nl

def num_es():
nl=numlanguage()
nl["cero"]=num(0)
nl["uno"]=num(1)
nl["dos"]=num(2)
nl["tres"]=num(3)
nl["cuatro"]=num(4)
nl["cinco"]=num(5)
nl["seis"]=num(6)
nl["siete"]=num(7)
nl["ocho"]=num(8)
nl["nueve"]=num(9)
nl["diez"]=num(10)
nl["once"]=num(11)
nl["doce"]=num(12)
nl["trece"]=num(13)
nl["catorce"]=num(14)
nl["quince"]=num(15)
nl["diecisÃ©is"]=num(16)
nl["diecisiete"]=num(17)
nl["dieciocho"]=num(18)
nl["diecinueve"]=num(19)
nl["veinte"]=nl["veinti"]=num(20)
nl["treinta"]=num(30)
nl["cuarenta"]=num(40)
nl["cincuenta"]=num(50)
nl["sesenta"]=num(60)
nl["setenta"]=num(70)
nl["ochenta"]=num(80)
nl["noventa"]=num(90)
nl["cien"]=nl["cientos"]=num(100)
nl["quinientos"]=num(500)
nl["setecientos "]=num(700)
nl["novecientos"]=num(900)
nl["mil"]=onemul(10**3)
nl["millÃ³n"]=nl["millones"]=mul(10**6)
nl["billÃ³n"]=nl["billones"]=mul(10**12)
nl["y"]=plus()
return nl

if __name__ == "__main__":
itnum=num_it()
print("it",str2num(itnum,sys.argv[1]))
ennum=num_en()
print("en",str2num(ennum,sys.argv[1]))
frnum=num_fr()
print("fr",str2num(frnum,sys.argv[1]))
denum=num_de()
print("de",str2num(denum,sys.argv[1]))
esnum=num_es()
print("es",str2num(esnum,sys.argv[1]))
</source>
==20==
trace.py:
<source lang=python>
def trace(f):
f.indent = 0
def strtuple(x):
return "("+str(x[0])+")" if len(x)==1 else str(x)
def g(*x):
print('| ' * f.indent + '/-- ', f.__name__, strtuple(x), sep='')
f.indent += 1
value = f(*x)
f.indent -= 1
print('| ' * f.indent + '\-- ', 'return', repr(value))
return value
return g

def memoize(f):
cache = {}
def g(*x):
if x not in cache:
cache[x] = f(*x)
return cache[x]
return g
</source>
main.py:
<source lang=python>
#!/usr/bin/env python3
import sys
import trace

# try to uncomment the following statements:
#@trace.trace
#@trace.memoize
def fib(i):
if i<=0:
return 0
elif i==1:
return 1
else:
return fib(i-1)+fib(i-2)

if __name__=="__main__":
for i in range(int(sys.argv[1])):
print(i,fib(i))
</source>

Esercizi di "lettura" programmi in Python 2019/20

2019-12-04T14:28:37Z

Laufragor:

Esercizi di "lettura" programmi in Python 2019/20

2019-12-04T14:21:50Z

Laufragor: /* 5 */

Gli esercizi proposti sono programmi funzionanti.

Come svolgimento dell'esercizio si deve:
* determinare lo scopo del programma
* modificare, migliorare discutere le soluzioni proposta. Proporre soluzioni alternative dello stesso problema.

==1==
<source lang=python>
def dd(s):
d,m,y=s.split('.')
d,m,y=int(d),int(m),int(y)
md=[0,31,28,31,30,31,30,31,31,30,31,30,31]
if y % 4 == 0: md[2]=29
dy=d
for i in range(1,m):
dy += md[i]
return dy

if __name__=="__main__":
data=input("Dammi una data (es. 14.03.2014) ")
print("il risultato della funzione misteriosa e' ",dd(data))
</source>

==2==
<source lang=python>
def imin(l):
im,mn=0,l[0]
for i in range(1,len(l)):
if l[i]<mn: im,mn=i,l[i]
return im

if __name__="__main__":
l=input('dammi in input una lista di elementi (es: [1,2,3]): ')
print("l'output della funzione misteriosa e': ",imin(l))
</source>

==3==
<source lang=python>
def r13(s):
e=''
for c in s:
if 'A'<=c<='Z':
e+=chr(((ord(c)-ord('A'))+13)%26+ord('A'))
elif 'a'<=c<='z':
e+=chr(((ord(c)-ord('a'))+13)%26+ord('a'))
else:
e+=c
return e

if __name__=="__main__":
s=input("scrivi una semplice frase (es: 'Ciao Mondo') ")
r=r13(s)
print("il risultato della funzione misteriosa e': ",r)
print("consiglio: prova a eseguire nuovamente il programma scrivendo")
print("la frase: ",r)
</source>

==4==
<source lang=python>
def pf(n):
f=[]
for i in range(2,n+1):
while n % i == 0:
f.append(i)
n //= i
if n == 1:
break
return f

if __name__=="__main__":
n=int(input("dammi un numero (consigliato da 2 a 1000): "))
print("il risultato della funzione misteriosa e' ",pf(n))
</source>

==5==
(richiede il modulo turtle)

<source lang=python>
import turtle
import random

def cy(r):
turtle.setup(400,400)
turtle.penup()
turtle.hideturtle()
turtle.speed(0)
for i in range(1000):
x,y = random.randint(-200,200),random.randint(-200,200)
if (x*x + y*y)**0.5 < r:
color = "red"
else:
color = "blue"
turtle.goto(x,y)
turtle.dot(5,color)

if __name__ == "__main__":
r = float(input("scrivi un numero (consigliato da 100 a 200): "))
print("guarda il risultato della funzione misteriosa")
cy(r)
turtle.exitonclick()
</source>

==6==
(richiede il modulo turtle)

<source lang=python>
import turtle

def poly(n):
for i in range(n):
turtle.forward(50)
turtle.left(360/n)

if __name__=="__main__":
n=int(input("dammi un intero (consigliato da 3 a 12): "))
poly(n)
turtle.exitonclick()
</source>

==7==
Questo e' contorto. Se vi piace... iniziate a preoccuparvi: state diventando informatici ;-)
<source lang=python>
f="f={0}{1}{0};print(f.format(chr(34),f))";print(f.format(chr(34),f))
</source>
NB: non e' necessario capire questo programma, e' solo per chi si vuole cimentare in una sfida...

==8==
<source lang=python>
def pf(n):
f=[]
for i in range(2,n+1):
while n % i == 0:
f.append(i)
n //= i
if n == 1:
break
return f

def fgcd(a,b):
def rgcd(fa,fb):
if fa and fb:
if fa[0]==fb[0]:
return fa[:1]+rgcd(fa[1:],fb[1:])
elif fa[0]<fb[0]:
return rgcd(fa[1:],fb)
else:
return rgcd(fa,fb[1:])
else:
return []
return rgcd(pf(a),pf(b))

def flcm(a,b):
def rlcm(fa,fb):
if fa and fb:
if fa[0]==fb[0]:
return fa[:1]+rlcm(fa[1:],fb[1:])
elif fa[0]<fb[0]:
return fa[:1]+rlcm(fa[1:],fb)
else:
return fa[:1]+rlcm(fa,fb[1:])
else:
return fa if fa else fb
return rlcm(pf(a),pf(b))

def mul(l):
rv=1
for el in l:
rv *= el
return rv

def gcd(x,y):
return mul(fgcd(x,y))

def lcm(x,y):
return mul(flcm(x,y))

if __name__=="__main__":
a,b=input("Inserisci due numeri (es: 48 36): ").split()
a,b=int(a),int(b)
print("pf({})={}".format(a,pf(a)))
print("pf({})={}".format(b,pf(b)))
print("fgcd({},{})={}".format(a,b,fgcd(a,b)))
print("flcm({},{})={}".format(a,b,flcm(a,b)))
print("gcd({},{})={}".format(a,b,gcd(a,b)))
print("lcm({},{})={}".format(a,b,lcm(a,b)))
</source>

==9==
<source lang=python>
def div(n):
return {x for x in range(1,n+1) if n % x == 0}

#alternativa:
#def div(n):
# d=set()
# for x in range(1,n+1):
# if n % x == 0: d.add(x)
# return d

def gcd(a,b):
return max(div(a) & div(b))

def mul(n,limit):
return {x*n for x in range(1,limit//n + 1)}

#alternativa
#def mul(n,limit):
# d=set()
# for x in range(1,limit//n + 1):
# d.add(x*n)
# return d

def lcm(a,b):
return min(mul(a,a*b) & mul(b,a*b))

if __name__=="__main__":
a,b=input("Inserisci due numeri (es: 48 36): ").split()
a,b=int(a),int(b)
print("div({})={}".format(a,div(a)))
print("div({})={}".format(b,div(b)))
print("mul({},{})={}".format(a,a*b,mul(a,a*b)))
print("mul({},{})={}".format(b,a*b,mul(b,a*b)))
print("gcd({},{})={}".format(a,b,gcd(a,b)))
print("lcm({},{})={}".format(a,b,lcm(a,b)))
</source>

==10==
<source lang=python>
def sdiv(n):
return {x for x in range(2,n) if n % x == 0}

#alternativa:
#def sdiv(n):
# d=set()
# for x in range(2,n):
# if n % x == 0: d.add(x)
# return d

def pr(n):
return not sdiv(n)

def pdiv(n):
return {x for x in sdiv(n) if pr(x)}

#alternativa:
#def pdiv(n):
# d=set()
# for x in sdiv(n):
# if pr(x): d.add(x)
# return d

def gcd(a,b):
csdiv=pdiv(a) & pdiv(b)
r=1
for x in csdiv:
while a % (r*x) == 0 and b % (r*x) == 0:
r *= x
return r

def lcm(a,b):
return a * b // gcd(a,b)

if __name__=="__main__":
a,b=input("Inserisci due numeri (es: 48 36): ").split()
a,b=int(a),int(b)
print("pdiv({})={}".format(a,pdiv(a)))
print("pdiv({})={}".format(b,pdiv(b)))
print("gcd({},{})={}".format(a,b,gcd(a,b)))
print("lcm({},{})={}".format(a,b,lcm(a,b)))
</source>
==11==
<source lang=python>
def tartline(l):
l[:0]=[1]
for i in range(1,len(l)-1):
l[i] += l[i+1]

l=[]
for i in range(12):
tartline(l)
print("{:^60}".format(str(l)))
</source>

==12==
<source lang=python>
def sdiv(n):
return {x for x in range(2,n) if n % x == 0}

#alternativa:
#def sdiv(n):
# d=set()
# for x in range(2,n):
# if n % x == 0: d.add(x)
# return d

def pr(n):
return not sdiv(n)

N=int(input("dammi il numero massimo (es 100): "))
print("ecco i numeri ***** fino a",N,":",[n for n in range(1,N+1) if pr(n)])
</source>

==13==
<source lang=python>
vf=[("Nella vecchia fattoria","Quante bestie ha zio Tobia","C'e' la capra","capra","ca"),
("Attaccato a un carrettino","C'è un quadrupede piccino","L'asinel","nel","nè"),
("Tra le casse e i ferri rotti", "Dove i topi son grassotti","C'è un bel gatto","gatto","ga"),
("Tanto grasso e tanto grosso", "Sempre sporco a più non posso", "C'è il maiale","iale","ia"),
("Poi sull'argine del fosso", "Alle prese con un osso", "C'è un bel cane","cane","ca"),
("Nella stalla silenziosa", "Dopo aver mangiato a iosa", "Dorme il bue","bue","bu")]
refrain="ia ia o"

def recverse(m,n):
v1,v2,an1,an2,an3=vf[m]
if n==m:
print(v1,refrain)
print(v2,refrain)
else:
recverse(m+1,n)
print(an1,an2,an3,an3,an2)

for i in range(len(vf)):
recverse(0,i)
print(vf[0][0],refrain)
print()
</source>

==14==
<source lang=python>
import turtle

def hser(size, level):
if level==0:
turtle.forward(size)
else:
hser(size,level-1)
turtle.left(45)
turtle.forward(size * 2**0.5)
turtle.left(45)
hser(size,level-1)
turtle.right(90)
turtle.forward(size)
turtle.right(90)
hser(size,level-1)
turtle.left(45)
turtle.forward(size * 2**0.5)
turtle.left(45)
hser(size,level-1)

def ser(size, level):
turtle.penup()
pos=(2**(level+2)-3) * size // 2 #posizione iniziale
turtle.setpos(-pos,pos)
turtle.pendown()
hser(size,level)
turtle.right(90)
hser(size,level)
turtle.right(90)
hser(size,level)
turtle.right(90)
hser(size,level)
turtle.right(90)

turtle.speed(0)
turtle.hideturtle()
ser(2,1)
ser(2,2)
ser(2,3)
ser(2,4)
turtle.exitonclick()
</source>
==15==
<source lang=python>
import turtle
import colorsys
import sys

def arrowstep(level, length, angle):
if level:
arrowstep(level-1, length/2, -angle)
turtle.left(angle)
arrowstep(level-1, length/2, angle)
turtle.left(angle)
arrowstep(level-1, length/2, -angle)
else:
turtle.forward(length)

def arrow(level, length):
if level & 1:
turtle.left(60)
arrowstep(level, length, -60)
else:
arrowstep(level, length, -60)

turtle.speed(0)
turtle.hideturtle()
turtle.colormode(1)
nmax=6
width=256
xmin= -width//2
ymin= -width*(3**0.5)//4
for n in range(nmax):
turtle.penup()
turtle.setposition(xmin,ymin)
turtle.setheading(0)
turtle.pencolor(colorsys.hls_to_rgb(1.0*n/6,0.5,1))
turtle.pendown()
arrow(n,256)

turtle.exitonclick()
</source>
==16==
<source lang=python>
def av(l):
return sum(l)/len(l)

def rg(l):
return max(l)-min(l)

def md(l):
lx=len(l)
ls=sorted(l)
if lx%2:
return ls[lx//2]
else:
return (ls[lx//2-1]+ls[lx//2])/2

if __name__=="__main__":
l=input("dammi una lista di numeri separati da virgole (es: 1,2,3,4.4): ")
l=[float(x) for x in l.split(',')]
print("i valori trovati dalle tre funzioni sono: {:.4f} {:.4f} {:.4f}".format(av(l),rg(l),md(l)))
</source>

==17==
<source lang=python>
import turtle
import sys

rows,cols=4,4
buttonsize=50
topdisplay=2*buttonsize

stack=[0]
fresh=True

def num(x):
global fresh,stack
if fresh:
stack[:0]=[x]
fresh=False
else:
stack[0]=stack[0]*10+x

enter,add,sub,mul,div=0,int.__add__,int.__sub__,int.__mul__,int.__floordiv__

def op(x):
global fresh,stack
if x!=enter and len(stack)>1:
stack=[x(stack[1],stack[0])]+stack[2:]
fresh=True

def off(x):
sys.exit(0)

buttons={
(0,0):('0',num,0), (1,0):('1',num,1), (1,1):('2',num,2), (1,2):('3',num,3), (2,0):('4',num,4),
(2,1):('5',num,5), (2,2):('6',num,6), (3,0):('7',num,7), (3,1):('8',num,8), (3,2):('9',num,9),
(3,3):('+',op,add), (2,3):('-',op,sub), (1,3):('*',op,mul), (0,3):('/',op,div),
(0,2):('ent',op,enter), (0,1):('off',off,0)}

def click(x,y):
col=x//buttonsize
row=y//buttonsize
if (row,col) in buttons:
label,op,val=buttons[row,col]
op(val)
drawcalc()

def drawcalc():
def drawbutton(col,row,label):
turtle.setpos(row*buttonsize,col*buttonsize)
turtle.pendown()
for _ in range(4):
turtle.forward(buttonsize)
turtle.left(90)
turtle.penup()
turtle.setpos(row*buttonsize+buttonsize//2,col*buttonsize+buttonsize//2)
turtle.write(label,align="center")
turtle.clear()
turtle.penup()
for row,col in buttons:
drawbutton(row,col,buttons[row,col][0])
turtle.setpos(row*buttonsize*(rows-1),col*buttonsize*(cols+1))
turtle.write(str(stack[0]),align="right")
turtle.update()

turtle.screensize(cols*buttonsize+1, rows*buttonsize+topdisplay+1)
turtle.setup(cols*buttonsize+1, rows*buttonsize+topdisplay+1)
turtle.setworldcoordinates(0,0,cols*buttonsize, rows*buttonsize+topdisplay)
turtle.hideturtle()
turtle.speed(10)
turtle.tracer(0)
drawcalc()
turtle.onscreenclick(click)
turtle.listen()
turtle.mainloop()
</source>

==18==
<source lang=python>
import turtle
import colorsys
import time

N=6
frompin=list(range(N,0,-1))
auxpin=[]
topin=[]

def rectangle(size, level, pin):
turtle.penup()
turtle.setpos(2*N*10*pin,level*10)
turtle.setheading(0)
turtle.pendown()
turtle.fillcolor(colorsys.hls_to_rgb(1.0*(size-1)/N,0.5,1))
turtle.begin_fill()
turtle.forward(size*10)
turtle.left(90)
turtle.forward(10)
turtle.left(90)
turtle.forward(size*20)
turtle.left(90)
turtle.forward(10)
turtle.left(90)
turtle.forward(size*10)
turtle.end_fill()

def showhanoi():
turtle.clear()
lf,la,lt=map(len,(frompin,auxpin,topin))
for i in range(lf):
rectangle(frompin[i], i, -1)
for i in range(la):
rectangle(auxpin[i], i, 0)
for i in range(lt):
rectangle(topin[i], i, 1)
turtle.update()
time.sleep(0.2)

def hanoi(n,f,a,t):
if n==1:
t.append(f.pop())
showhanoi()
else:
hanoi(n-1,f,t,a)
hanoi(1,f,a,t)
hanoi(n-1,a,f,t)

turtle.hideturtle()
turtle.speed(10)
turtle.tracer(0)
showhanoi()
hanoi(N,frompin,auxpin,topin)
turtle.exitonclick()
</source>
==19==
<source lang=python>
#!/usr/bin/env python3
# Copyright 2014 Renzo Davoli University of Bologna - Italy
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License along
# with this program; if not, write to the Free Software Foundation, Inc.,
# 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
#
import sys

class num:
def __init__(self,n):
self.val=n

class mul(num):
pass

class onemul(mul):
pass

class plus():
pass

class times():
pass

class numlanguage():
def __init__(self):
self.dict={}
def __setitem__(self,s,op):
self.dict[s]=op
for l in range(len(s)-1,0,-1):
if s[:l] in self.dict:
break
else:
self.dict[s[:l]]=None
return op
def match(self,s):
matchlen,obj=0,None
for l in range(1,len(s)+1):
if s[:l] in self.dict:
matchlen,obj=l,self.dict[s[:l]]
else:
break
return matchlen,obj

def str2num(langnum,s):
hi=mid=lo=last=0
lastop=None
while s:
if s[0] in " -\t\n":
s=s[1:]
else:
ml,obj=langnum.match(s)
if obj:
if isinstance(obj,num):
if isinstance(obj,mul):
if isinstance(obj,onemul) and lo == 0:
lo = 1
if (last <= obj.val or isinstance(lastop,times)) and not isinstance(lastop,plus):
hi,mid,lo = (hi+mid+lo)*obj.val,0,0
else:
hi,mid,lo = hi+(lo+mid)*obj.val,0,0
last=obj.val
else:
if obj.val == 100:
mid,lo = lo*obj.val if lo else obj.val,0
elif obj.val <= lo or isinstance(lastop,plus):
lo += obj.val
else:
lo = lo*obj.val if lo else obj.val
lastop=None
else:
lastop=obj
#print(s[:ml],hi,mid,lo,last,lastop)
s=s[ml:]
else:
return -1
return hi+mid+lo

def num_it():
nl=numlanguage()
nl["zero"]=num(0)
nl["uno"]=nl["un"]=nl["una"]=num(1)
nl["due"]=num(2)
nl["tre"]=num(3)
nl["quattro"]=num(4)
nl["cinque"]=num(5)
nl["sei"]=num(6)
nl["sette"]=num(7)
nl["otto"]=num(8)
nl["nove"]=num(9)
nl["dieci"]=num(10)
nl["undici"]=num(11)
nl["dodici"]=num(12)
nl["tredici"]=num(13)
nl["quattordici"]=num(14)
nl["quindici"]=num(15)
nl["sedici"]=num(16)
nl["diciassette"]=num(17)
nl["diciotto"]=num(18)
nl["diciannove"]=num(19)
nl["venti"]=nl["vent"]=num(20)
nl["trenta"]=nl["trent"]=num(30)
nl["quaranta"]=nl["quarant"]=num(40)
nl["cinquanta"]=nl["cinquant"]=num(50)
nl["sessanta"]=nl["sessant"]=num(60)
nl["settanta"]=nl["settant"]=num(70)
nl["ottanta"]=nl["ottant"]=num(80)
nl["novanta"]=nl["novant"]=num(90)
nl["cento"]=num(100)
nl["mille"]=onemul(10**3)
nl["mila"]=nl["migliaia"]=mul(10**3)
nl["milioni"]=nl["milione"]=mul(10**6)
nl["miliardi"]=nl["miliardo"]=mul(10**9)
nl["dozzine"]=nl["dozzina"]=mul(12)
nl["decine"]=mul(10)
nl["centinaia"]=mul(100)
nl["di"]=times()
nl["e"]=plus()
return nl

def num_en():
nl=numlanguage()
nl["zero"]=nl["null"]=num(0)
nl["one"]=nl["a"]=num(1)
nl["two"]=num(2)
nl["three"]=num(3)
nl["four"]=num(4)
nl["five"]=num(5)
nl["six"]=num(6)
nl["seven"]=num(7)
nl["eight"]=num(8)
nl["nine"]=num(9)
nl["ten"]=num(10)
nl["eleven"]=num(11)
nl["twelve"]=num(12)
nl["thirteen"]=num(13)
nl["fourteen"]=num(14)
nl["fifteen"]=num(15)
nl["sixteen"]=num(16)
nl["seventeen"]=num(17)
nl["eighteen"]=num(18)
nl["nineteen"]=num(19)
nl["twenty"]=num(20)
nl["thirty"]=num(30)
nl["forty"]=num(40)
nl["fifty"]=num(50)
nl["sixty"]=num(60)
nl["seventy"]=num(70)
nl["eighty"]=num(80)
nl["ninety"]=num(90)
nl["hundred"]=num(100)
nl["thousand"]=mul(10**3)
nl["million"]=mul(10**6)
nl["billion"]=mul(10**9)
nl["trillion"]=mul(10**12)
nl["dozen"]=mul(12)
nl["and"]=plus()
nl["of"]=times()
return nl

def num_fr():
nl=numlanguage()
nl["zero"]=num(0)
nl["un"]=num(1)
nl["deux"]=num(2)
nl["trois"]=num(3)
nl["quatre"]=num(4)
nl["cinq"]=num(5)
nl["six"]=num(6)
nl["sept"]=num(7)
nl["huit"]=num(8)
nl["neuf"]=num(9)
nl["dix"]=num(10)
nl["onze"]=num(11)
nl["douze"]=num(12)
nl["treize"]=num(13)
nl["quatorze"]=num(14)
nl["quinze"]=num(15)
nl["seize"]=num(16)
nl["vingt"]=num(20)
nl["trente"]=num(30)
nl["quarante"]=num(40)
nl["cinquante"]=num(50)
nl["soixante"]=num(60)
nl["cent"]=num(100)
nl["mille"]=onemul(10**3)
nl["million"]=mul(10**6)
nl["milliard"]=mul(10**9)
nl["douzaine"]=mul(12)
nl["et"]=plus()
nl["de"]=times()
return nl

def num_de():
nl=numlanguage()
nl["null"]=num(0)
nl["eins"]=nl["ein"]=num(1)
nl["zwei"]=nl["zwo"]=num(2)
nl["drei"]=num(3)
nl["vier"]=num(4)
nl["fÃ¼nf"]=num(5)
nl["sechs"]=num(6)
nl["sieben"]=num(7)
nl["acht"]=num(8)
nl["neun"]=num(9)
nl["zehn"]=num(10)
nl["elf"]=num(11)
nl["zwÃ¶lf"]=num(12)
nl["dreizehn"]=num(13)
nl["vierzehn"]=num(14)
nl["fÃ¼nfzehn"]=num(15)
nl["sechzehn"]=num(16)
nl["siebzehn"]=num(17)
nl["achtzehn"]=num(18)
nl["neunzehn"]=num(19)
nl["zwanzig"]=num(20)
nl["dreiÎ²ig"]=num(30)
nl["dreiÃig"]=num(30)
nl["vierzig"]=num(40)
nl["fÃ¼nfzig"]=num(50)
nl["sechzig"]=num(60)
nl["siebzig"]=num(70)
nl["achtzig"]=num(80)
nl["neunzig"]=num(90)
nl["hundert"]=num(100)
nl["tausend"]=mul(10**3)
nl["million"]=mul(10**6)
nl["milliard"]=mul(10**9)
nl["und"]=plus()
return nl

def num_es():
nl=numlanguage()
nl["cero"]=num(0)
nl["uno"]=num(1)
nl["dos"]=num(2)
nl["tres"]=num(3)
nl["cuatro"]=num(4)
nl["cinco"]=num(5)
nl["seis"]=num(6)
nl["siete"]=num(7)
nl["ocho"]=num(8)
nl["nueve"]=num(9)
nl["diez"]=num(10)
nl["once"]=num(11)
nl["doce"]=num(12)
nl["trece"]=num(13)
nl["catorce"]=num(14)
nl["quince"]=num(15)
nl["diecisÃ©is"]=num(16)
nl["diecisiete"]=num(17)
nl["dieciocho"]=num(18)
nl["diecinueve"]=num(19)
nl["veinte"]=nl["veinti"]=num(20)
nl["treinta"]=num(30)
nl["cuarenta"]=num(40)
nl["cincuenta"]=num(50)
nl["sesenta"]=num(60)
nl["setenta"]=num(70)
nl["ochenta"]=num(80)
nl["noventa"]=num(90)
nl["cien"]=nl["cientos"]=num(100)
nl["quinientos"]=num(500)
nl["setecientos "]=num(700)
nl["novecientos"]=num(900)
nl["mil"]=onemul(10**3)
nl["millÃ³n"]=nl["millones"]=mul(10**6)
nl["billÃ³n"]=nl["billones"]=mul(10**12)
nl["y"]=plus()
return nl

if __name__ == "__main__":
itnum=num_it()
print("it",str2num(itnum,sys.argv[1]))
ennum=num_en()
print("en",str2num(ennum,sys.argv[1]))
frnum=num_fr()
print("fr",str2num(frnum,sys.argv[1]))
denum=num_de()
print("de",str2num(denum,sys.argv[1]))
esnum=num_es()
print("es",str2num(esnum,sys.argv[1]))
</source>
==20==
trace.py:
<source lang=python>
def trace(f):
f.indent = 0
def strtuple(x):
return "("+str(x[0])+")" if len(x)==1 else str(x)
def g(*x):
print('| ' * f.indent + '/-- ', f.__name__, strtuple(x), sep='')
f.indent += 1
value = f(*x)
f.indent -= 1
print('| ' * f.indent + '\-- ', 'return', repr(value))
return value
return g

def memoize(f):
cache = {}
def g(*x):
if x not in cache:
cache[x] = f(*x)
return cache[x]
return g
</source>
main.py:
<source lang=python>
#!/usr/bin/env python3
import sys
import trace

# try to uncomment the following statements:
#@trace.trace
#@trace.memoize
def fib(i):
if i<=0:
return 0
elif i==1:
return 1
else:
return fib(i-1)+fib(i-2)

if __name__=="__main__":
for i in range(int(sys.argv[1])):
print(i,fib(i))
</source>