Sistemi Operativi - User contributions [en]

2017.09.11

2018-05-09T15:51:39Z

Matt: Created page with "Pdf completo qui: [http://www.cs.unibo.it/~renzo/so/compiti/2017.09.11.tot.pdf 2017.09.11.tot.pdf] =Esercizio c1= <syntaxhighlight lang=c> Un semaforo intelligente controlla ..."

Pdf completo qui: [http://www.cs.unibo.it/~renzo/so/compiti/2017.09.11.tot.pdf 2017.09.11.tot.pdf]

=Esercizio c1=
<syntaxhighlight lang=c>
Un semaforo intelligente controlla un incrocio al quale si può accedere da 4 direzioni N, E, S, W.
Un solo veicolo alla volta deve occupare l’area dell’incrocio.
Se sono presenti veicoli da tutte le direzioni, il semaforo fa avanzare ciclicamente un veicolo da ogni direzione (NESWNESWNESW…).
Se nessun veicolo è in attesa da una direzione, il turno viene saltato.
Quella che segue è la porzione di di programma eseguita dai veicoli per passare attraverso l’incrocio:

crossing.enter(direction)
…critical section
crossing.exit(direction)

Nonostante sia un semaforo, questo esercizio deve venir risolto coi monitor.
</syntaxhighlight>

'''Soluzione proposta 1'''
<syntaxhighlight lang=c>
monitor crossing{

enum direction = {N, E, S, W};
condition ok2cross[4];
boolean busy;
int waiting[4];

procedure_entry void enter(enum direction d){
waiting[d]++;
if(waiting[d] > 1) ok2cross[d].wait();
busy = true;
waiting[d]--;

}

procedure_entry void exit(enum direction d){
busy = false;
for(int i = 1; i < 5; i++){
if(waiting[(d + i) % 4]) ok2cross[(d + i) % 4].signal();
}
}

crossing(){
for(int i = 0; i < 4; i++) waiting[i] = 0;
busy = false;
}
}
</syntaxhighlight>

Prove svolte e soluzioni proposte

2018-05-09T15:48:06Z

Matt:

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.

[[2017.09.11]]

[[2017.07.17]]

2017.07.17

2018-05-09T13:25:01Z

Matt: /* Soluzione proposta 1 */

Pdf completo qui: [http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf]

=Esercizio c.1=
<syntaxhighlight lang=c>
In una conferenza il coordinatore decide l’ordine degli oratori e li chiama uno ad uno per poter fare il proprio intervento.
Se l’oratore arriva in ritardo (non sta attendendo al momento della chiamata) perde il diritto di poter parlare.

Coordinatore: process
while True:
chiamato = next(); //next è la funzione che restituisce il nome del prossimo oratore
print(“Chiamo ora a parlare “,chiamato);
if (conf.chiama(chiamato))
print(“ringrazio “, chiamato,” per la relazione”);
else
print(“mi dispiace che “, chiamato, “non sia presente”);

Oratore[nome]: for nome in set_of_speakers
if conf.arrivato(nome):
//presentazione
conf.finepresentazione(nome)

Scrivere il monitor conf.
La funzione chiama aspetta che il relatore chiamato abbia completato l’intervento, se prensente, e restituisce vero altrimenti restituisce falso.
La funzione arrivato segnala la presenza e pone il relatore in attesa del proprio turno.
Se il relatore è già stato chiamato ed era assente restituisce falso.
</syntaxhighlight>

==== Soluzione proposta 1 ====

<syntaxhighlight lang=c>
Monitor conf{

boolean called[N_SPEAKERS];
condition ok2speak[N_SPEAKERS];
condition ok2call;

procedure_entry boolean chiama(int chiamato){
ok2call.wait();
if(ok2speak[chiamato].signal()) {
called[nome] = true;
return true;
}else return false;
}

procedure_entry boolean arrivato(int nome){
if(called[nome]) return false;
else ok2speak[nome].wait();
return true;
}

procedure_entry void finepresentazione(int nome){
ok2call.signal();
}

conf(int N_SPEAKERS){
for(int i = 0; i < N_SPEAKERS; i++) called[i] = false;
}

}
</syntaxhighlight>

2017.07.17

2018-05-09T13:17:44Z

Matt: /* Esercizio c.1: */

Pdf completo qui: [http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf]

=Esercizio c.1=
<syntaxhighlight lang=c>
In una conferenza il coordinatore decide l’ordine degli oratori e li chiama uno ad uno per poter fare il proprio intervento.
Se l’oratore arriva in ritardo (non sta attendendo al momento della chiamata) perde il diritto di poter parlare.

Coordinatore: process
while True:
chiamato = next(); //next è la funzione che restituisce il nome del prossimo oratore
print(“Chiamo ora a parlare “,chiamato);
if (conf.chiama(chiamato))
print(“ringrazio “, chiamato,” per la relazione”);
else
print(“mi dispiace che “, chiamato, “non sia presente”);

Oratore[nome]: for nome in set_of_speakers
if conf.arrivato(nome):
//presentazione
conf.finepresentazione(nome)

Scrivere il monitor conf.
La funzione chiama aspetta che il relatore chiamato abbia completato l’intervento, se prensente, e restituisce vero altrimenti restituisce falso.
La funzione arrivato segnala la presenza e pone il relatore in attesa del proprio turno.
Se il relatore è già stato chiamato ed era assente restituisce falso.
</syntaxhighlight>

==== Soluzione proposta 1 ====

<syntaxhighlight lang=c>
Monitor conf{

boolean called[N_SPEAKERS];
condition ok2speak[N_SPEAKERS];
condition ok2call;

procedure_entry boolean chiama(chiamato){
ok2call.wait();
if(ok2speak[chiamato].signal()) {
called[nome] = true;
return true;
}else return false;
}

procedure_entry boolean arrivato(nome){
if(called[nome]) return false;
else ok2speak[nome].wait();
return true;
}

procedure_entry void finepresentazione(nome){
ok2call.signal();
}

conf(){
for(int i = 0; i < N_SPEAKERS; i++) called[i] = false;
}

}
</syntaxhighlight>

2017.07.17

2018-05-09T13:15:35Z

Matt: Created page with "Pdf completo qui: [http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf] == Esercizio c.1: == <syntaxhighlight lang=c> In una conferenza il coordi..."

Pdf completo qui: [http://www.cs.unibo.it/~renzo/so/compiti/2017.07.17.tot.pdf 2017.07.17.tot.pdf]

== Esercizio c.1: ==

<syntaxhighlight lang=c>
In una conferenza il coordinatore decide l’ordine degli oratori e li chiama uno ad uno per poter fare il proprio intervento.
Se l’oratore arriva in ritardo (non sta attendendo al momento della chiamata) perde il diritto di poter parlare.

Coordinatore: process
while True:
chiamato = next(); //next è la funzione che restituisce il nome del prossimo oratore
print(“Chiamo ora a parlare “,chiamato);
if (conf.chiama(chiamato))
print(“ringrazio “, chiamato,” per la relazione”);
else
print(“mi dispiace che “, chiamato, “non sia presente”);

Oratore[nome]: for nome in set_of_speakers
if conf.arrivato(nome):
//presentazione
conf.finepresentazione(nome)

Scrivere il monitor conf.
La funzione chiama aspetta che il relatore chiamato abbia completato l’intervento, se prensente, e restituisce vero altrimenti restituisce falso.
La funzione arrivato segnala la presenza e pone il relatore in attesa del proprio turno.
Se il relatore è già stato chiamato ed era assente restituisce falso.
</syntaxhighlight>

==== Soluzione proposta 1 ====

<syntaxhighlight lang=c>
Monitor conf{

boolean called[N_SPEAKERS];
condition ok2speak[N_SPEAKERS];
condition ok2call;

procedure_entry boolean chiama(chiamato){
ok2call.wait();
if(ok2speak[chiamato].signal()) {
called[nome] = true;
return true;
}else return false;
}

procedure_entry boolean arrivato(nome){
if(called[nome]) return false;
else ok2speak[nome].wait();
return true;
}

procedure_entry void finepresentazione(nome){
ok2call.signal();
}

conf(){
for(int i = 0; i < N_SPEAKERS; i++) called[i] = false;
}

}
</syntaxhighlight>

Prove svolte e soluzioni proposte

2018-05-09T13:06:54Z

Matt: /* Prove d'esame svolte e/o soluzioni proposte */

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.

[[2017.07.17]]

Prove svolte e soluzioni proposte

2018-05-09T13:06:31Z

Matt: Created page with "=Prove d'esame svolte e/o soluzioni proposte= Questa pagina serve a raccogliere prove d'esame svolte (che possono essere utili alla preparazione) e soluzioni proposte a tali ..."

=Prove d'esame svolte e/o soluzioni proposte=

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.

[[2017.07.17]]

Main Page

2018-05-09T13:02:07Z

Matt: /* ANNO ACCADEMICO 2017/18 */

Questo è il Wiki del Corso di Sistemi Operativi

== ANNO ACCADEMICO 2017/18 ==

[[Lezioni Anno Accademico 2017/18 I semestre]]

[[Lezioni Anno Accademico 2017/18 II semestre]]

[[Esercizi ed Esperimenti 2017/18]]

-----

[[Prove svolte e soluzioni proposte]]

== ANNI PRECEDENTI ==
[[Materiale dell'AA 2016-17]]

[[Materiale dell'AA 2015-16]]

[[Materiale dell'AA 2014-15]]

[[Materiale dell'AA 2013-14]]

----
Ricordate che per creare un account o quando viene richiesto di risolvere un semplice calcolo occorre ricordare quanto scritto [[qui]]

Lezioni Anno Accademico 2017/18 II semestre

2018-04-04T18:17:53Z

Matt:

== Lezione del 28 febbraio 2018 ==
Inizia oggi la seconda parte del corso di Sistemi Operativi che si terrà dal 28/02/18 al 25/05/18. 
Le lezioni si svolgeranno, il mercoledì e il giovedì, in aula E1. Il venerdì invece ci sposteremo in M1. 
La suddivisione degli argomenti trattati sarà: '''mercoledì''' teoria, '''giovedì''' tendenzialmente parte progettuale (potrebbe iniziare con un po' di teoria) e '''venerdì''', data la scarsa dotazione dell'aula assegnataci, verranno svolti esercizi scritti in preparazione all'esame.

Nel corso della lezione ci siamo chiesti, riprendendo un po' il filo logico delle lezioni dello scorso semestre, quali siano i servizi che ci aspettiamo da un sistema operativo. 
Questa volta, tuttavia, non li analizzeremo dal punto di vista dell'utilizzatore, ma da un punto di vista interno al sistema stesso. 
I servizi elencati sono stati:
* Scheduling (Gestione CPU)
* Gestione dei processi
* Gestione della memoria primaria
* Gestione dei device di I/O
* Gestione della memoria secondaria
* Filesystem
* Networking
* Protezione
* Shell

Come in tutta l'informatica spesso succede, la complessità di questi servizi viene gestita tramite la creazione di livelli di astrazione. 
Il livello zero di astrazione, quello più basso, sarà l''''hardware''' che noi dovremo considerare come un linguaggio (l'ISA del processore). 
Seguito poi da due blocchi:
* '''Kernel'''
* '''Utente'''

Cosa va incluso nel kernel di un S.O.? Cosa nella parte utente? Meglio massimizzare o minimizzare le operazioni nello livello kernel? '''KERNEL MONOLITICO''' O '''MICRO-KERNEL'''?

I kernel monolitici (tipo Linux) hanno il vantaggio di essere leggermente più performanti, mentre i microkernel (che presentano più livelli di astrazione) sono molto più flessibili e facili da manutenere.
Ad esempio, nei microkernel un bug non obbliga necessariamente a riavviare la macchina perché è possibile riavviare il singolo "modulo" che presenta l'errore.

== Lezione del 1 marzo 2018 ==
La lezione tace come concordato con gli studenti.

== Lezione del 2 marzo 2018 ==
La lezione tace causa chiusura dell'intero Ateneo per condizioni climatiche avverse.

== Lezione del 7 marzo 2018 ==
Tutto incomincia dal boot, la fase che carica il kernel, la quale termina subito dopo la creazione del primo processo (init) tramite la compilazione della tabella (come si vede sotto) che verrà passata allo scheduler. Una volta caricato, il kernel ha davanti una gradissima diversità di modelli hardware, ma come utilizzare tutti questi dispositivi hardware? Una prima soluzione sarebbe quella di includere nel kernel tutti i relativi device driver, tuttavia il kernel diventerbbe davvero corposo, a meno che non si crei un kernel ad hoc per una specifica macchina. Un'altra soluzione (quella comunemente adottata) utilizza i moduli. I moduli vengono caricati dal kernel all'occorrenza senza essere inseriti direttamente in esso (non è quindi necessaria la ricompilazione).
Tuttavia con quest'ultima soluzione si viene a creare un dilemma, ovvero: 
Chi carica i moduli? Il kernel. 
Chi carica il kernel? Il boot tramite moduli.

In verità non esiste solo il kernel ma anche un filesystem che contiene i moduli chiamato "init.rd" (inutile se il kernel è configurato per una specifica macchina).
Arrivati a questo punto ci si chiede: come si compila un kernel? Prima di tutto occorrono i sorgenti (quelli di linux sono reperibili su https://www.kernel.org). Una volta scaricati, si deve configurare il file “.config” che sostanzialmente descrive le specifiche del kernel. Questo file lo si può configurare a mano o tramite il “menuconfig” che dovrà essere prima di tutto opportunatamente compilato. All'interno del menuconfig tra le altre cose c'è una lista di tutti i device driver supportati e possono essere spuntati con: * (driver inserito nel kernel) o M (creazione del relativo modulo). Una volta configurato il “.config” non resta che compilare il kernel per la macchina ospite o per una specifica architettura. Ad esempio:

wget link_of_kernel_source #scarica i sorgenti 
tar xf source_compressed_file # decomprime i relativi sorgenti, in questo caso dal file.tar.xz 
cd linux #entra nella directory dei sorgenti 
(Di regola esiste già un .config standard ma per configurarlo) 
make menuconfig 
make #compila il kernel per la macchina ospite 
(make -arch=armhf, compila secondo l'architettura dei processori armhf) 
( make -j n, compila il kernel per la macchina ospite utilizzando i suoi n-1 core) 

Una volta compilato l'immagine del kernel si troverà in arch/nome_architettura/boot/bzImage. 

Ora si ricordi la differenza tra processo e thread: Il processo è l'entità titolare delle risorse, mentre il thread è la componente sequenziale dell'elaborazione.
Nei sistemi monothread il concetto di thread si sovrappone al concetto di processo ma in linea generale un processo può avere anche più di un thread. Ma quali sono le caratteristiche principali dei processi e dei thread?

<table>
<tr>
<th>Processo (PCB)</th><th>Thread (TCB)</th>
</tr>
<tr>
<th>ID (self, parent,child etc)</th><th>ID</th>
</tr>
<tr>
<th>Info sulla memoria (puntatore alla tabella dei segmenti)</th><th>Stato del processore</th>
</tr>
<tr>
<th>File aperti</th><th>Stato: Ready, Running,Block</th>
</tr>
<tr>
<th>Ownership</th><th>Puntatori</th>
</tr>
<tr>
<th>Interprocess comunication</th><th></th>
</tr>
<tr>
<th>Informazioni sull'accounting </th><th></th>
</tr>
</table>

Modo Kernel e Modo User 
Si definisce Mode Switch il passaggio da Kernel Mode a User Mode e viceversa (esiste tale differenza per motivi di sicurrenzza). Attenzione però a non confondere la kernel mode con i permessi di root (root è l'utente con più permessi in assoluto ma è comunque gestito in user mode).
Si definisce Context Switch il passaggio di processi. Ad esempio un processo A in user mode si ferma e passa il controllo al trap che tramite lo scheduler chiama un altro processo.
Da qui si capische che è lo scheduler a decidere il prossimo processo da mandare avanti (tramite la Ready Queue). Un tipico scheduler è lo scheduler FIFO non preemptive (ossia il processo in esecuzione utilizzerà il processore finché non passerà allo stato di wait o termina l'esecuzione) per sistemi batch.
I thread posso essere creati sia in modo kernel che in modo user.

== Lezione del 8 marzo 2018 ==
Lo scheduler è quella parte del sistema operativo che si occupa di assegnare le risorse (specialmente il processore) ai vari processi, decidendone l'ordine e il tempo di esecuzione. Di scheduler ne esistono di 2 tipi; quelli non-preemptive (o cooperative) dove il context switch avviene solo se il processo in esecuzione fa I/O o una system call bloccante passando allo stato di wait o termina e quelli preemptive quando il processo in esecuzione può passare allo stato ready mediante un interrupt.

I criteri con cui vengono scelti gli scheduler sono:

* Throughput: la quantità di processi completati per unità di tempo 
* Turnaround: il tempo che intercorre da quando un processo entra nella coda ready fino alla fine della sua esecuzione 
* Percentuale di utilizzo del processore 
* Tempo di attesa: quanto tempo tempo un processo rimane nella coda ready prima di iniziare la sua esecuzione 

Partendo dal più semplice da realizzare, troviamo lo scheduler FCFS (First Come, First Served), il quale usa una politica FIFO quindi i processi vengono eseguiti in ordine di arrivo, è cooperative e non è per nulla efficiente.

Uno scheduler più avanzato, ma sempre cooperative, è lo SJF (Shortest Job First) che da la priorità ai processi con meno tempo di CPU burst (tempo di utilizzo del processore). Il tempo di utilizzo della CPU viene stimato basandosi sulle precedenti esecuzioni e calcolato mediante la media esponenziale dando maggior peso alle esecuzioni più recenti.
Una variante preemptive del SJF è lo Shortest-Remeaning-Time First il quale fa passare dallo stato running a ready un processo se nel frattempo arriva nella coda ready un altro processo con un tempo di CPU burst più breve. Il problema principale però è che entrambi possono generare starvation.

Lo scheduler Round-Robin, di tipo preemptive, fa uso della Time-Slice (ovvero un quanto di tempo). I processi vengono eseguiti in ordine di arrivo ma possono rilasciare il processore anticipatamente nel caso in cui finisca la time-slice a loro disposizione. Per implementare questo scheduler, tuttavia, è necessario un supporto hardware chiamato "interval time", il quale non fa altro che generare un input ogni tot tempo scelto dal sistema operativo, questo input non ha nessuno scopo se non quello di generare un interrupt che possa interrompere l'esecuzione di un processo. La time-slice non piò essere troppo breve perché il context-switch ha un costo, non è istantaneo, ma nemmeno un troppo lunga altrimenti non si avrebbe l'idea di un sistema fluido ed istantaneo.

Esistono anche gli scheduler che assegnano una priorità ai processi ed eseguono prima quelli con priorità più elevata. Questi scheduler esistono sia con priorità statica, che con priorità dinamica, ma potendo generare starvation, quelli con priorità dinamica possono utilizzare l'aging, ossia un processo con priorità bassa aumenta di volta in volta la sua priorità fino a diventare massima per poi, una volta eseguito, tornare alla priorità originaria.
Un po' più complessi sono gli scheduler con classi di priorità, in cui la coda ready è divisa in diverse sottocode, una per ogni classe di processi. Gli scheduler multilivello utilizzano sempre le classi di priorità ma assegnano ad ogni classe delle politiche diverse, adatte per i processi che contiene.

Per applicazioni particolari, in cui la correttezza del programma dipende da tempo entro i quale viene data la risposta, esistono gli scheduler real-time.

== Lezione del 9 marzo 2018 ==
Esercizi su monitor e semafori degli esami di gennaio e febbraio 2018.

Testo:
<syntaxhighlight lang=c>
Monitor bridge
boolean bridge_is_down
int crossingCars
int crossingBoat
int waitingCars
int waitingBoats
condition ok2cars
condition ok2boats

procedure_entry car_enter(direction)
if(crossingBoat || waitingBoats > 0){
waitingCars++
ok2cars.wait()
waitingCars--
}
bridge_is_down = true
crossingCars++
ok2cars.signal()

procedure_entry car_exit(direction)
crossingCars--
if(crossingCars == 0) ok2boat.signal()

procedure_entry boat_enter(direction)
if(crossingCars > 0 || crossingBoat > 0){
waitingBoats++
ok2boat.wait()
waitingBoats--
}
bridge_is_down = false
crossingBoat++

procedure_entry boat_exit(direction)
crossingBoat--
ok2cars.signal()
if(crossingCars == 0) ok2boat.signal()
</syntaxhighlight>
 
Testo: implementare, utilizzando semafori ordinari, i semafori ternari
<syntaxhighlight lang=c>
class ternarySemaphore

semaphore pos
semaphore neg

void ternarySemaphore(int init)
void P(void)
void V(void)

void ternarySemaphore(void init)
// init is -1 or 1
pos = new semaphore(1 + init)
neg = new semaphore(1 - init)

void P(void)
pos.P()
neg.V()

void V(void)
neg.P()
pos.V()
</syntaxhighlight>
Soluzione alternativa, meno di stile ma ugualmente funzionante
<syntaxhighlight lang=c>
class ternarySemaphore

semaphore queue
semaphore mutex
int value

void ternarySemaphore(int init)
void P(void)
void V(void)

void ternarySemaphore(void init)
mutex = new semaphore(1)
value = init
queue = new sem_queue

void P(void)
mutex.P()
if(value == 1 && !queue.empty()){
s = queue.dequeue()
s.V()
}else{
if(value == -1){
s = new semaphore(0)
queue.enqueue(s)
mutex.V()
s.P()
}else{
value--
mutex.V()
}
}

void V(void)
mutex.P()
if(value == -1 && !queue.empty()){
s = queue.dequeue()
s.V()
}else{
if(value == -1){
s = new semaphore(0)
queue.enqueue(s)
mutex.V()
s.P()
free(s)
}else{
value++
mutex.V()
}
}
</syntaxhighlight>

== Lezione del 14 marzo 2018 ==
'''RISORSE'''

Cosa intendiamo per risorsa? Quali sono i problemi comuni e le tecniche per risolverli? 
Nel frattempo definiamo come '''CLASSI DI RISORSE''' l'insieme formato da risorse tra loro equivalenti (byte della memoria, stampanti dello stesso tipo, etc.).
 
Una prima distinzione può essere fatta tra risorse ad assegnazione '''''statica''''' e ad assegnazione '''''dinamica''''': le prime, una volta assegnate, non possono essere più prelevate finché il processo che le possiede non termina. Nel secondo caso, invece, l'assegnazione può mutare nel tempo.
 
Si può distinguere il tipo di richiesta che viene fatta alla risorsa: '''''singola''''' o '''''multipla''''', '''''bloccante''''' o '''''non bloccante'''''. Intuitivamente, la prima distinzione si riferisce alla molteplicità di richieste che la risorsa può eseguire nello stesso momento mentre, la seconda distinzione, si riferisce al comportamento della richiesta.
 
Altre distinzioni possono essere fatte tra risorse '''''non condivisibili''''' (dette anche seriali) e risorse '''''condivisibili''''' (o non seriali), tra risorsa '''''non pre-emptible''''' e '''''pre-emptible'''''. Una risorsa può essere pre-emptible se e solo se non ha uno stato interno o se lo stato può essere salvato per poi essere ripristinato.
 
Può accadere che un processo A effettui una ''richiesta bloccante'' ad una ''risorsa non-preemptible'' e ''non condivisibile'' che al momento è utilizzata da un qualche processo B. B, a sua volta, fa la stessa cosa ma, con una risorsa in possesso di A. Cosa accade?
 
'''DEADLOCK'''
 
Le condizioni necessarie affinché un deadlock si verifichi sono:
*'''RICHIESTA BLOCCANTE'''
*'''RISORSA NON CONDIVISIBILE'''
*'''RISORSA NON-PREEMPITIBLE'''
*'''ATTESA CIRCOLARE'''

work in progress

== Lezione del 15 marzo 2018 ==
Nessuna lezione.

== Lezione del 16 marzo 2018 ==
== Lezione del 21 marzo 2018 ==
== Lezione del 22 marzo 2018 ==

Alcuni errori comuni della fase 1 del progetto:
* file sparsi nell'archivio, invece di una sola cartella che li contiene tutti
* uso del Makefile senza regole automatiche
* uso di sentinelle globali nella ricorsione
* uso di licenze non compatibili tra di loro
* indentazione sbagliata

=== Memoria Principale ===

La MMU è una componente hardware che implementa una funzione che associa gli indirizzi usati dal
sorgente (logici) a quelli reali in memoria (fisici).

Un modo per calcolare gli indirizzi fisici corrispondenti agli indirizzi logici di un processo è
dare un registro base ad ogni processo; quando un processo accede all'indirizzo della variabile A,
ad esempio, la MMU calcola il suo indirizzo fisico aggiungendo al suo indirizzo logico il
valore del registro base.

Qual è il problema con questo approccio? Non si hanno indirizzi più piccoli dell'indirizzo
base, ma si può sforare nello spazio di indirizzi di un altro processo, dato che non c'è un limite
superiore. Questo problema si risolve facilmente aggiungendo al registro base un registro limite.
Un processo può accedere a tutti gli indirizzi compresi tra i due indirizzi, e, se va fuori, si
genera una trap di memoria. Questo fornisce anche un meccanismo di protezione della memoria.

Se adottiamo questo approccio quando allochiamo spazio in memoria per un processo dobbiamo farlo in
maniera contigua.
Come? Ci sono vari metodi:

* '''Partizionamento statico''': in una sezione iniziale della memoria sta il kernel, il resto della memoria è divisa in parti; man mano che arrivano i processi vengono assegnati alle varie parti di memoria. Che problemi ha questo approccio? È statico, ovvero la disposizione iniziale è quella definitiva. Inoltre dobbiamo scegliere il segmento dove inserire il nuovo processo allocato. Spesso la memoria disponibile è maggiore di quella necessaria; di conseguenza ci sarà uno spreco. Quando ci sono aree di memoria inutilizzate all'interno di porzioni di memoria di dimensioni stabilite a priori si parla di '''frammentazione interna'''. È' un problema che vogliamo risolvere;

* '''Partizionamento dinamico''': potremmo, ad esempio, stackare i blocchi di memoria dei processi, così da non sprecare memoria. Problema: come facciamo quando un processo termina? In questo caso avremmo degli spazi di memoria inutilizzati sparsi per la memoria, che potrebbero dare spazio ad un altro processo se uniti assieme, ma che da soli non riescono perché sono troppo piccoli. Si parla in questo caso di '''frammentazione esterna'''. Si può risolvere il problema compattando le zone di memoria. Per fare ciò è necessario:
** copiare il PCB dal posto in cui si trova alla cima dello stack;
** cambiare base register e limit register;
** aspettare che il processo sia "fermo"; se fosse in esecuzione spostarlo ovviamente creerebbe delle inconsistenze.

Se il processo è interattivo e si prova a fare compattazione, si parla di Giga da muovere: altamente
inefficiente. L'approccio migliore è quello di limitare la frammentazione esterna. Come?
Scegliendo, tra le varie aree libere, quella migliore per contenere un processo. Per fare queste
operazioni è necessario qualcuno che tenga traccia della contabilità della memoria del sistema. Ci
pensa un programma chiamato Memory Manager. Come fa? Con una lista delle aree di memoria libere.
Questo permette di vedere se esistono zone di memoria libere contigue e di unirle assieme
eventualmente. Si possono usare anche le tabelle di bit: se consideriamo la memoria divisa in unita'
di allocazione possiamo associare ad ogni unità un bit, acceso o spento se libera o meno.

Per scegliere le aree di memoria ci sono vari approcci:
* Best Fit: scelgo l'area più piccola che contiene il mio processo;
* First Fit: scelgo la prima area capace di contenere il mio processo che trovo dall'inizio della memoria;
* Next Fit: come First Fit ma parto dall'ultimo processo a cui sono arrivato con la precedente scansione;
* Worst Fit: scelgo l'area più grande che contiene il mio processo.
Quale tecnica è la migliore? Statisticamente First Fit.

Questi meccanismi funzionavano per sistemi batch; per sistemi molto dinamici queste cose ci fanno
sprecare memoria o è richiesta la compattazione, che richiede tempo. La MMU con base register e
limit register non permettono altro. Si può fare di meglio? Sì.

Come? Con la paginazione della memoria. La memoria viene divisa in blocchi di dimensione fissata
dette '''pagine'''. Ovviamente l'ampiezza della pagina è una potenza di 2. L'indirizzo logico visto dal
programma viene diviso in due parti: il numero di pagina e l'offset all'interno della pagina. La MMU
usa il numero della pagina come indice all'interno di una tabella. A quell'indice è associato,
nella tabella, l'indirizzo fisico che contiene la pagina. La parte di memoria fisica che contiene la
pagina è detta '''frame'''. L'indirizzo fisico corrispondente sarà dato, una volta ottenuto
l'indirizzo del frame che lo contiene, dai bit che precedono l'offset e, subito dopo, dall'offset
stesso, che viene copiato identico alla fine dell'indirizzo fisico.

Questo meccanismo è molto più flessibile del partizionamento della memoria. C'è frammentazione
interna? Sì, ma poca: nel peggiore dei casi abbiamo un processo che ha bisogno di n pagine + 1 bit.
In questo caso verranno allocate n+1 pagine. Quindi la frammentazione interna che abbiamo sarà al
massimo dell'ordine della dimensione di una pagina per ogni processo. C'è frammentazione esterna?
Potrebbe, ma sarebbe irrisoria: potrebbe esserci all'inizio della memoria dove risiede il kernel.

Il problema della frammentazione è risolto. Ma dove sta il costo nascosto? Nella MMU. Come si
gestisce la sua tabella? La cosa migliore sarebbe una matrice associativa, sarebbe molto veloce, e
questa caratteristica è necessaria visto che la tabella va gestita ad ogni accesso in memoria.
Problema: il costo elevato di una componente hardware capace di mantenere una tabella delle pagine.
Mettiamo la tabella in memoria? Non è ideale, perché dopo servirebbero due accessi in memoria per
ogni accesso in memoria. Le prestazioni della memoria risultano quindi dimezzate.

La soluzione? Una cache: il '''Translation Lookahead Buffer'''. È una matrice associativa, ma fa da
cache alla tabella della MMU, che è salvata in memoria. È quindi molto più piccola della tabella.
Quando viene fatta una operazione in memoria si può avere un TLB hit: la velocità è alta.
Potremmo avere un TLB miss. In questo caso l'indirizzo richiesto non è in cache. Questo genera un
interrupt, quindi il controllo passa al kernel, che va a vedere nella tabella in memoria se
l'indirizzo richiesto è legale, nel qual caso lo carica. Questo meccanismo è ragionevolmente
veloce e ha prezzi accessibili. Va tuttavia fatto notare che una macchina che usa allocazione
contigua senza paginazione è più veloce di una macchina con paginazione. Ovviamente quello che
abbiamo con questo meccanismo è un tradeoff. Paghiamo due prezzi: uno in termini di performance, un
altro in termini di linearità di esecuzioni, in cambio di un miglior utilizzo della memoria.

Gli effetti positivi della paginazione sono tanti, ma rimangono alcuni problemi da risolvere. Se noi
abbiamo una libreria dinamica con la paginazione tradizionale avremmo tante copie della stessa
libreria in memoria, e quindi un enorme spreco. Per fare questo si usa il codice reentrant. La
memoria allocata per un processo è così divisa:
* area text: testo dell'eseguibile; solitamente read-only, dato che può anche essere sharable;
* area data: variabili globali; condivisibile per scelta;
* area stack: area dove cresce lo stack; MAI condivisibile.

Come risolviamo questo problema? Col loading dinamico, ovvero loading di codice dalla memoria a
run-time. È una funzionalità fornita agli sviluppatori per scrivere codice più efficiente.

Un'altra funzionalità è il linking dinamico. Le librerie dinamiche servono a questo: quando il
codice usa una libreria non la linka nell'eseguibile, ma si segna che è presente e si segna la
versione che usa; a run time, raggiunta quella parte di codice, si va a recuperare la libreria
dinamica già caricata in memoria (o casomai si carica); questo viene fatto dal linker.

È possibile attaccarsi alla libreria già caricata in memoria grazie a memory mapping. Questo pero'
non è possibile con la paginazione tradizionale. Occorre introdurre un nuovo concetto: la
'''segmentazione'''. L'idea è di dividere l'area richiesta dai processi in segmenti adibiti a scopi
specifici. Si possono avere segmenti testo, data, stack, shared data, etc., ognuno con le sue
proprietà di leggibilità o di scrittura. Una MMU che supporta segmentazione è così
fatta: la parte iniziale (piccola) dell'indirizzo identifica il segmento, la parte finale identifica
l'offset all'interno del segmento. Per ogni segmento vi è una entry in una tabella, in cui vengono
mantenute le varie proprietà del segmento. Tra le varie cose viene mantenuto l'indirizzo base del
segmento (da sommare all'offset). Di segmenti ce ne sono pochi, di pagine tante.

Facciamo un confronto tra paginazione e segmentazione:

{|class="wikitable"
! Pagine
! Segmenti
|-
|Limita frammentazione
|Permette la condivisione e la protezione
|-
|Hanno tutte la stessa ampiezza (e.g. 4k)
|Hanno ampiezza (molto) variabile O(k),....,O(G)
|-
|Hanno un indirizzo
|Hanno un nome
|-
|Possono contenere dati disomogenei
|Contengono informazioni omogenee
|-
|Divisione in pagine automatica
|Divisione in segmenti; alcune divisioni sono strutturali,
altre sono decise dal programmatore
|}

Nella pratica che tecnica si usa? Entrambe: paginiamo i segmenti. Gli indirizzi logici contengono
l'identificatore del segmento, della pagina, l'offset ed il contesto. In caso di miss si usa il numero
di segmento per accedere ad una tabella con i bit di controllo. Se l'indirizzo è legale la entry
punta ad una page table. Si usa poi il numero di pagina per identificare la pagina e l'offset per
ottenere la parte di memoria desiderata.

== Lezione del 23 marzo 2018 ==
== Lezione del 28 marzo 2018 ==
== Lezione del 29 marzo 2018 ==
Pausa di primavera.

== Lezione del 30 marzo 2018 ==
Pausa di primavera.

== Lezione del 4 aprile 2018 ==

Lezioni Anno Accademico 2017/18 II semestre

2018-03-28T20:11:28Z

Matt: /* Lezione del 30 marzo 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-28T20:11:07Z

Matt: /* Lezione del 29 marzo 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-20T23:25:26Z

Matt: /* Lezione del 14 marzo 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-20T23:24:18Z

Matt: /* Lezione del 14 marzo 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-20T21:37:50Z

Matt: /* Lezione del 9 marzo 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-20T21:25:53Z

Matt: /* Lezione del 9 marzo 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-20T21:16:39Z

Matt: /* Lezione del 9 marzo 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-01T16:01:27Z

Matt: /* Lezione del 28 febbraio 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-01T15:43:04Z

Matt: /* Lezione del 2 marzo 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-01T15:41:36Z

Matt: /* Lezione del 1 marzo 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-01T15:41:04Z

Matt: /* Lezione del 28 febbraio 2018 */

Lezioni Anno Accademico 2017/18 II semestre

2018-03-01T15:34:33Z

Matt: Created page with "== Lezione del 28 febbraio 2018 == == Lezione del 1 marzo 2018 == == Lezione del 2 marzo 2018 == == Lezione del 7 marzo 2018 == == Lezione del 8 marzo 2018 == == Lezione del 9..."

== Lezione del 28 febbraio 2018 ==
== Lezione del 1 marzo 2018 ==
== Lezione del 2 marzo 2018 ==
== Lezione del 7 marzo 2018 ==
== Lezione del 8 marzo 2018 ==
== Lezione del 9 marzo 2018 ==
== Lezione del 14 marzo 2018 ==
== Lezione del 15 marzo 2018 ==
== Lezione del 16 marzo 2018 ==
== Lezione del 21 marzo 2018 ==
== Lezione del 22 marzo 2018 ==
== Lezione del 23 marzo 2018 ==
== Lezione del 28 marzo 2018 ==
== Lezione del 29 marzo 2018 ==
== Lezione del 30 marzo 2018 ==

Main Page

2018-03-01T15:30:34Z

Matt:

Questo è il Wiki del Corso di Sistemi Operativi

== ANNO ACCADEMICO 2017/18 ==

[[Lezioni Anno Accademico 2017/18 I semestre]]

[[Lezioni Anno Accademico 2017/18 II semestre]]

[[Esercizi ed Esperimenti 2017/18]]

== ANNI PRECEDENTI ==
[[Materiale dell'AA 2016-17]]

[[Materiale dell'AA 2015-16]]

[[Materiale dell'AA 2014-15]]

[[Materiale dell'AA 2013-14]]

----
Ricordate che per creare un account o quando viene richiesto di risolvere un semplice calcolo occorre ricordare quanto scritto [[qui]]

Lezioni Anno Accademico 2017/18 I semestre

2017-10-19T22:44:17Z

Matt: /* Lezione del 17 ottobre 2017 */

''scrivete qui idee, riassunti dei concetti espressi, commenti approfondimenti sulle lezioni.''

== Lezione del 26 settembre 2017 ==
'''Titolo della lezione: W⁴ H Y'''

* What:
* Who:
----
Noi studenti ed "entrambi" i professori.
 
* When:
----
Il corso ha durata annuale. Verrà svolto ogni martedì e venerdì dalle 15:30 alle 18:30.
* La lezione del martedì sarà dedicata alla programmazione concorrente;
* La lezione del venerdì sarà dedicata alla parte generale. Terminerà circa 15 minuti prima dell'orario stabilito.
 
* Where:
----
Sempre in Aula 1 Ercolani (E1): DISI, Scuole Ercolani, Mura Anteo Zamboni 2B.
 
* How:
----
Il corso si svolgerà tramite:
* Lezioni frontali in aula.
* Attività di laboratorio.
* Esercitazioni.

Inoltre, durante l'ultimo periodo di lezioni del secondo semestre, vi sarà un periodo di ripasso del programma tramite esercizi, in vista dell'esame.
Durante la lezione del 3/10 sono state indicate alcune propedeuticità del corso. tra cui: programmazione, algoritmi e architettura degli elaboratori in primis.
Importanti sono anche i corsi di Analisi matematica e Algebra e geometria. Per farla breve, il primo anno è propedeutico al secondo.
 
* Why:
----
* '''Fonti e strumenti del corso:''' wiki creata di gruppo, lezioni frontali e esercitazioni.
**Non esiste un vero e proprio testo consigliato. Tutte le informazioni sono date DURANTE il corso.
** Per domande specifiche scrivere su mailing list (so@cs.unibo.it);
** Per esercizi, appunti e programma svolto rivolgersi al wiki (so.v2.cs.unibo.it);
** Per live streaming (www.cs.unibo.it/~renzo/live/).
* '''Modalità di esame:''' esame scritto (diviso in due parti: una parte generale e una di programmazione concorrente) + progetto + orale (facoltativo), possibilità di dare solo lo scritto per ottenere un massimo di 18. La modalità per studenti in "difficoltà" è disponibile solo fino agli appelli autunnali.
** Si parlerà del progetto indicativamente a partire da Dicembre 2017.
** L'orale può essere sostenuto da chi vuole migliorare (peggiorare) il voto ottenuto, o da chi vuole ottenere la lode.
* '''Orario di ricevimento per il primo semestre (fino al 15/09/17):''' martedì alle 11:30.
* Università = docenti + studenti.
* Informatica = come generare informazione automatica.
* Hardware, Software, Elaborazione, Comunicazione, Memorizzazione, Digitale/Analogico.
La principale distinzione che facciamo tra '''dato''' e '''informazione''' è che il dato, da solo, è privo di significato. Se, tuttavia, viene interpretato in un particolare contesto allora può diventare informazione significativa per chi sta interpretando i dati.

Un '''algoritmo''' è una o più sequenze non ambigue di passi che, dato un problema, ci permette di risolverlo.

Il nostro algoritmo, scritto in un qualche linguaggio formale, diventa un '''programma''' (sostanzialmente un testo, un insieme di istruzioni).

Un linguaggio è un entità software, ed è definito come una quadrupla (alfabeto, sintassi, lessico, semantica) dove:
*l'''alfabeto'' è l'insieme di simboli che compone il linguaggio.
*il ''lessico'' si può vedere come una funzione che va dai simboli a un booleano e ci dice quali sono le frasi ben formate.
*la ''sintassi'' determina quali delle sequenze scritte sono effettivamente corrette.
*la ''semantica'' associa un significato alle parole ben formate.

== Lezione del 29 settembre 2017 ==
'''Cos'è un sistema operativo e un po' di storia'''

Un ''sistema operativo'' è un programma che gestisce i processi, le risorse e interfaccia le applicazioni con l'hardware dell'elaboratore.

In particolare, il sistema operativo (laddove esiste) è il primo processo ad essere attivato e resta in vita fino allo spegnimento del calcolatore o al sopraggiungere di un errore fatale per il sistema.

A cosa serve un sistema operativo?
Principalmente, ha i seguenti scopi:
# Facilitare l'utilizzo del sistema (senza S.O. sarebbe a carico del programmatore conoscere tutti i linguaggi con cui si comunica con l'architettura della macchina);
# Rendere affidabile, protetto e sicuro l'utilizzo del sistema (e.g. un processo potrebbe recar danno all'intero sistema se non controllato o gestito, potrebbe ignorare i permessi di visualizzazione di un file);
# Astrarre l'hardware (e.g. filesystem);
# Garantire l'efficienza (e.g. non tenere la CPU in idle adottando opportuni algoritmi di scheduling);
# Assicurare portabilità ;

Un approccio molto usato è il cosiddetto approccio a strati ("a livelli") in cui ogni strato utilizza i servizi forniti al livello inferiore e ne fornisce di nuovi a quello superiore.
Astraendo il nostro calcolatore possiamo piazzare al livello più basso l'hardware e, subito sopra, il sistema operativo. I due layer comunicano usando il linguaggio ISA (Instruction Set Architecture), nativo della CPU stessa, al quale si aggiungono quelli che permettono di comunicare con i vari controllori dei dispositivi come la scheda di rete, la stampante, etc. Sopra il livello del sistema operativo possiamo collocare quello delle librerie e, infine, quello degli applicativi.

* '''Systemcall''' = meccanismo usato da un processo per richiedere al SO una qualche funzionalità a livello kernel. Un esempio è la funzione printf() del linguaggio C (stampa a video) che utilizza la systemcall write() (una delle systemcall per la gestione dei dispositivi).
 
----
'''Storia dei sistemi operativi'''

Nella generazione '''zero''' (1800 ca.) possiamo includere Babbage con la sua macchina analitica e lady Ada Lovelace. [[File:290px-AnalyticalMachine Babbage London.jpg |200px|thumb|right|Macchina analitica di Babbage]]

Nella generazione '''uno''' vediamo la comparsa delle valvole con tutti i problemi connessi. Non c'erano utilizzatori delle macchine, le stesse persone che le costruivano erano anche programmatori e fruitori delle stesse.

Nella generazione '''due''' (fine anni '60) arriva il transistor. Quest'ultimo è molto più veloce e piccolo della valvola e, soprattutto, meno incline a guasti. Le macchine iniziano ad essere più economiche grazie alla possibilità di avere un'economia di scala e quindi accessibili al grande pubblico. Questo fa si che, in queste prime fasi, i costruttori non siano più gli unici utilizzatori. [[File:Transistors.jpg |300px|thumb|right|Diversi tipi di Transistor]]

----

A questo punto poiché, pur essendo diventata più accessibile, una macchina costava ancora molto, nasce l'esigenza di non lasciare mai un processore senza lavoro (al fine di massimizzare i ricavi) e di condividere i dati.
In questa fase, infatti, abbiamo sistemi operativi di tipo ''batch'' (che collezionano tutto l'input all'inizio per calcolare e restituire l'output) dove l'inserimento di programmi e dati veniva fatto tramite schede perforate e non c'era interazione. Dai sistemi batch nasce lo ''SPOOL'' (Simultaneous Peripheral Operations On-Line).

Si comincia a pensare di utilizzare i tempi di I/O per poter eseguire altri processi. Questo però solleva almeno due problematiche: da un lato serve un modo per sapere quando un input è davvero finito mentre, dall'altro, bisogna fare in modo che un processo che non richieda I/O non occupi la CPU per un tempo indefinito.
Per la prima problematica la soluzione è rappresentata dall'introduzione degli '''interrupt''', segnali elettrici inviati alla CPU alla fine di ogni input.
Per la seconda, invece, è stato introdotto il cosiddetto '''interval timer''' che non è altro che un dispositivo che invia interrupt dopo un determinato quanto di tempo assicurando che un processo non occupi per troppo tempo il processore.
Questo consente di realizzare sistemi time sharing (il cui più semplice algoritmo è il round-robin) dove un processo può essere in uno dei seguenti tre stati:
*'''READY''' pronto per essere eseguito ma, il processore è già occupato;
*'''RUNNING''' in esecuzione;
*'''WAIT''' in attesa di I/O.

[[File:Dds.png]]

Nella '''quarta''' generazione (anni '70 ca.) vediamo la nascita di molte innovazioni importanti. Si riesce a rimpicciolire di molto i processori facendoli divenire a tutti gli effetti micro-processori. Nei laboratori Bell nasce Unix, un sistema operativo rivoluzionario con time sharing e clonazione dei processi (un processo non viene mai creato dal nulla ma viene prima clonato da uno già esistente e poi, alla copia, viene fatto eseguire un programma). A causa di problemi di portabilità da PDP-9, macchina su cui Unix è nato, a PDP-11 nasce il linguaggio C e il suo compilatore (scritto anch'esso in C).
Mentre Apple I "porta" una nuova idea di pc per tutte le famiglie, nascono molte versioni di Unix.
Per impedire una deriva proprietaria in cui ogni produttore offriva tutto quello che offrivano gli altri ma con qualche feature in più, Richard Stallman fonda il progetto GNU (GNU's Not Unix) per il quale scrive tutta una serie di utilities come il famoso compilatore gcc.
A GNU, per essere operativo, manca però un kernel. Non volendo aspettare i tempi di sviluppo del kernel che Stallman aveva in mente, Linus Torlvalds scrive il kernel '''Linux''' da cui nasce il sistema operativo GNU/Linux.

Nei tempi più recenti nascono i processori multi-core.

== Lezione del 3 ottobre 2017 ==

'''Introduzione alla programmazione concorrente: processi, thread e librerie'''

In programmazione concorrente le nozioni apprese di "algoritmo", "programma" e "processo" devono essere aggiornate. Questo perché non vi è più un programma con un'unica sequenza esecutiva [o meglio, un unico filo (= thread) di esecuzione]. Appare ovvio come servino dei meccanismi per organizzare e sincronizzare tali fili esecutivi, in modo da evitare il verificarsi di eventi non desiderati.

Quando parliamo di ''sistema concorrente'', ci riferiamo ad un sistema in cui due o più "attori" sono eseguiti parallelamente. 

Questi attori possono essere '''processi''' o '''thread'''.
La differenza sostanziale tra queste due tipologie di attori riguarda la condivisione della memoria e dei dati su cui operano. 

Più processi possono eseguire lo stesso programma ma, ognuno di essi, ha i propri dati su cui operare e il suo stato di avanzamento. In particolare:
* un processo è un'entità, un attore che ha delle proprietà e delle risorse associate;
* in ogni istante, il processo può essere interrotto. 
Più thread che vengono eseguiti parallelamente, invece, condividono gli stessi dati su cui operare. 
Codici di esempio:

'''processi'''

<syntaxhighlight lang=C>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[]){
if(fork()) printf("Yes");
else printf("No");
}
</syntaxhighlight>

L'output generato sarà "YesNo" poiché, usando la systemcall ''fork()'', abbiamo creato una nuova copia del processo (un processo figlio). Il processo padre, che ha eseguito con successo la fork(), stamperà "Yes" mentre il figlio stamperà "No".

'''thread'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++) sum = sum + 1;
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

Prima di discutere l'output generato dall'esecuzione di questo codice, è opportuno introdurre, brevemente, gli strumenti utilizzati.

----
'''Pthread (POSIX thread)'''

Citazione dal Silberschatz, Galvin, Gagne:
''Pthread si riferisce allo standard POSIX (IEEE 1003.1c) che definisce una API per la creazione e sincronizzazione dei thread.''

Le istruzioni fondamentali sono:
* '''int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);''' che crea un thread;
* '''int pthread_join(pthread_t thread, void **retval);''' che aspetta che un thread sia completato prima di continuare l'esecuzione.

Da ricordare che, per utilizzare pthread, va incluso l'header ''<pthread.h>'' e durante la compilazione va inclusa la libreria esterna tramite l'opzione ''-pthread''.
----

Torniamo all'output generato dall'esecuzione del secondo codice. 
Nel codice vengono generati cinque thread ed ognuno somma MAX (=1000000) volte 1 a sum. Ci aspettiamo un output di 5000000 ma, in realtà, viene stampato un valore molto minore. 

Questo accade principalmente per due motivi:
*sommare una costante ad una variabile non è un'operazione atomica (richiede almeno tre istruzioni assembler: due mov ed una sum).
*l'interval timer può fermare l'esecuzione del thread mentre sta effettuando una delle tre operazioni richieste per aggiungere uno a sum e provocare un risultato errato.

Questo è uno dei possibili problemi della programmazione concorrente conosciuto come ''race condition''. 
Un sistema di processi multipli presenta una '''race condition''' qualora il risultato finale dell'esecuzione dipenda dalla temporizzazione, o dall'ordine con cui i processi vengono eseguiti.

Per risolvere questo problema possiamo adoperare ancora una volta pthread.
Nello specifico, ci venogono offerte istruzione per realizzare una '''mutua esclusione''' sulle risorse condivise in modo che l'operazione che prima non era atomiche,ora, lo sia e non porti più ad una computazione errata. 
Codice di esempio: 
'''Mutex'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++){
pthread_mutex_lock(&mutex);
sum = sum + 1;
pthread_mutex_unlock(&mutex);
}
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

----
'''MUTEX'''

Un mutex è un dispositivo di MUTual EXclusion (mutua esclusione), ed è utile per proteggere le strutture dati condivise da modifiche concorrenti, implementare sezioni critiche e monitor.

Un mutex ha due possibili stati: sbloccato (non posseduto da nessun thread) e bloccato (posseduto da un thread). Un mutex non può mai essere posseduto da due thread contemporaneamente. Se un thread provasse ad acquisire il mutex, mentre quest'ultimo è già in possesso di un altro thread, dovrebbe aspettare finché non viene rilasciato.
La variabile che realizza il mutex, di tipo ''pthread_mutex_t'', viene inizializzata staticamente assegnandogli PTHREAD_MUTEX_INITIALIZER.
'''pthread_mutex_lock''' acquisisce immediatamente il mutex, se libero. Altrimenti aspetta fino a trovarla, prima o poi, libera. 
'''pthread_mutex_unlock''' rilascia il mutex.

[da: https://sourceware.org/pthreads-win32/manual/pthread_mutex_init.html]
----

Con questa soluzione abbiamo raggiunto un risultato esatto pur avendo pagato in prestazioni: la computazione infatti è più lenta a causa del tempo richiesto dalla sincronizzazione tra i thread.

Consideriamo ora due scenari leggermente più complicati:
* nel primo abbiamo due processi, A e B, che devono accedere a due risorse, X e Y, contemporaneamente prima di poter terminare. Cosa succede se, mentre A acquisisce X, B acquisisce Y?
* nel secondo abbiamo tre processi, A, B e C, che devono accedere alla risorsa X. Che succede se A e B, essendo più veloci, occupano insistentemente la risorsa e non permettono a C di utilizzarla?

La prima condizione si chiama '''deadlock''', la seconda condizione si chiama '''starvation'''. Il deadlock (stallo) è un problema che non può scomparire autonomamente, mentre la starvation ("inedia") si può risolvere da sola. A tal proposito ci viene incontro l'assioma di '''finite progress''': "ogni processo che può avanzare, prima o poi lo farà".
 
In ogni caso, per parlare in maniera più approfondita di queste tematiche:
* avremo bisogno di un modello di riferimento
* avremo bisogno di paradigmi in grado di esprimere la concorrenza (alcuni paradigmi saranno rivolti alla concorrenza a memoria privata; altri al multithreading a risorse condivise)
* dovremo imparare a scrivere programmi
Nel nostro modello di riferimento l'assegnamento di costanti è un operazione atomica. Dagli esempi precedenti, infatti, si evince come ci sia bisogno di creare atomicità in sezioni critiche. Inoltre, il nostro modello dovrà rispettare le proprietà di safety e di liveness, ovvero:
* Tutti i processi danno la stessa risposta;
* Ogni processo corretto da come risposta una tra quelle proposte;
* Ogni processo prima o poi fornisce una risposta.

== Lezione del 6 ottobre 2017 ==
'''Il linguaggio C'''

Il linguaggio C nasce nei primi anni 70 grazie al lavoro di Dennis Ritchie con lo scopo di scrivere il
sistema operativo Unix. Quali sono le caratteristiche di C e cosa lo rende un linguaggio adatto per scrivere un sistema
operativo? Un linguaggio per scrivere un sistema operativo deve:
* essere indipendente dalla macchina su cui viene scritto
* dare la possibilità di lavorare direttamente con la memoria
* permette di andare a modificare i singoli bit in memoria
* essere semplice da usare
* essere massimamente produttivo
* essere veloce, efficiente
C presenta le caratteristiche dette sopra e alcune altre:
* in C, dal punto di vista sintattico, tutto è funzione. Si può vedere un programma in C come un insieme di funzioni. La funzione principale è il '''main'''. L'unica cosa che la distingue è il nome, a parte quello il main è una funzione come le altre. Prende due argomenti: argcount e argvalue, che contengono rispettivamente il numero degli argomenti e un array contenente gli argomenti stessi. L'interfaccia del main è tipicamente: <syntaxhighlight lang=C> int main(int argc, char *argv[]) </syntaxhighlight>
* il costrutto fondamentale è l'espressione. ''expression'' ; = ''instruction''
* sono previste istruzioni di struttura <syntaxhighlight lang=C>if, while, switch, etc.</syntaxhighlight>
* le variabili, per poter essere utilizzate, devono essere sempre definite
* il C è un linguaggio fortemente tipato, però con un certo numero di eccezioni: ad esempio, è possibile fare il casting esplicito di un puntatore void * in qualsiasi tipo, senza che il compilatore dia errori o warnings, con conseguente perdita di type safety
* C è un linguaggio "per adulti": non impone una struttura ordinata al codice, come ad esempio fa invece Python, ed è piena responsabilità del programmatore scrivere programmi ordinati/leggibili. Inoltre molte operazioni che in altri linguaggi non sarebbero permesse lo sono invece in C: anche in questo caso è responsabilità del programmatore fare corretto uso del linguaggio
* C è un linguaggio molto semplice. Come si sopperisce alle mancanze imposte da questa semplicità? Grazie alle librerie: in C tutte le funzionalità aggiuntive (non fornite dal linguaggio stesso, come l'allocazione di memoria, la stampa a schermo, la gestione di input e output) sono fornite dalle librerie
* C è anche sintatticamente semplice. Dove va a finire la complessità sintattica? Nel preprocessore: prima di essere compilato un programma in C passa attraverso un preprocessore, che produce codice in base alle direttive di preprocessione date nel codice stesso <syntaxhighlight lang=C>#ifdef VAR ... #endif, # e ## operator, __LINE__,etc</syntaxhighlight>
* in C vi sono fondamentalmente due tipi di dato: int e float. Tutti gli altri "tipi" di dato sono derivati da essi. Si hanno diversi modificatori, che vanno a modificare la quantità di memoria allocata per la variabile. Alcuni di questi sono <syntaxhighlight lang=C>long, short, char, etc</syntaxhighlight> Un dato di tipo long int ha, solitamente, la dimensione di una parola di memoria della macchina su cui è eseguito il programma. char alloca 8 bits. Se si prende una variabile di un certo tipo e lo si assegna ad una di tipo più ampio, il valore viene mantenuto. Viceversa quando si assegna una variabile di un tipo ad una di tipo meno ampio, una volta "superato il limite" si torna indietro ciclicamente al valore iniziale. Per queste situazioni il compilatore non dà né warnings né errors: sono perfettamente lecite in C
* in C si passa una varibile ad una funzione solo per valore; per passare "per riferimento" una variabile si passa per valore l'indirizzo della variabile
* in C si può fare uso di puntatori alla memoria. Dato un puntatore p, un'istruzione del tipo p+i va letta come: vai avanti di i posizioni della grandezza del tipo del puntatore ognuno. Un vettore in C non è altro che un puntatore che non può essere assegnato. Una scrittura del tipo array[i] è una abbreviazione di *(array + i). Non c'è controllo in C se vado oltre la memoria allocata per l'array. Perché? In Pascal, ad esempio, c'è un tale controllo. Il motivo per cui in C questo manca è che questo controllo genera ulteriore codice macchina. Dovendo C essere efficiente, non ci si può permettere un tale costo aggiuntivo. La responsabilità di non andare oltre è lasciata al programmatore

Esercizio svolto che prende in input due valori tramite i parametri del metodo '''main''', li converte da sequenze di caratteri ad interi, per poi stamparli utilizzando delle '''System Call'''. Lo scopo dell’esercizio è dimostrare come sia possibile utilizzare il linguaggio C senza l’utilizzo di librerie particolari (ad eccezione di quelle per le System Call).

<syntaxhighlight lang=C>
#define _GNU_SOURCE
#include <unistd.h>
#include <sys/syscall.h>

int _uatoi(char *s, int value){
if (*s == 0)
return value;
else if (*s >= '0' && *s <= '9'){
value = value * 10 + (*s - '0');
return _uatoi(s+1, value);
}
}

int uatoi(char *s){
return _uatoi(s, 0);
}

char *uitoa(int val, char *buf, int len){
int i;
for (len = len - 1; len >= 0 && val > 0; len--, val /= 10){
buf[len] = '0' + (val %10);
}

return buf + len + 1;
}

#define MAXOUTLEN 10
int main (int argc, char *argv[]) {
int tot = 0;
int i;
char buf[MAXOUTLEN];
char *result;
for (i = 1; i < argc; i++)
tot += uatoi(argv[i]);
result = uitoa(tot, buf, MAXOUTLEN);
syscall(__NR_write, 1, result, MAXOUTLEN - (result - buf));
syscall(__NR_write, 1, "\n", 1);
return tot;
}
</syntaxhighlight>

== Lezione del 10 ottobre 2017 ==
'''Programmazione concorrente: notazione e un primo problema'''

Esempio di possibile rappresentazione (che non useremo) di codice concorrente. 
'''''A'', ''B'', ''C'', ''D'', ''E''''' rappresentano porzioni di codice. 
'''''//''''' rappresenta esecuzione parallela

<syntaxhighlight lang='c'>
A
cobegin
B
//
C
//
D
coend
E
</syntaxhighlight>

Il codice sarà eseguito come: ''A'' -> ''BCD'' -> ''E''. ''E'' quindi verrà eseguito solo dopo la fine dell'esecuzione di ''BCD''.

Un esempio che si presta molto bene ad illustrare la programmazione concorrente è quello del '''merge sort''' concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
coend
merge (miscela) i risultati
</syntaxhighlight>

Versione errata del merge sort concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
//
merge (miscela) i risultati
coend
</syntaxhighlight>

Avendo un numero ''N'' di processi, vorremmo avere una notazione che ci permetta di definire una porzione di codice come atomica (la sezione critica). Come possiamo procedere? 
Teoricamente, vorremmo avere due funzioni, '''csenter()''' e '''csexit()''' che ci permettano di entrare e uscire dalla sezione critica del codice senza causare errori nella computazione. 
Quali sono le proprietà che queste funzioni debbono rispettare?
# Devono garantire la mutua esclusione (1 solo processo esegue la critical section alla volta). Contando ''n'' csenter() completate e ''m'' csexit() completate la differenza deve essere <=1
# Non devono fare deadlock tra di loro
# Non devono fare starvation tra loro
# ''(no unnecessary delay)'' un processo che non sta usando la critical section {csenter()..csexit()} non deve bloccare un altro processo dall'entrarvi.

La soluzione a questo problema è nota come '''soluzione di Dekker''' (scritta e pubblicata da Dijkstra) che venne presentata in modo graduale attraverso l'utilizzo di quattro possibili, ma sbagliate, soluzioni.

Vorremmo avere programmi che abbiano la seguente struttura:

<syntaxhighlight lang='c'>
process[i], i=1,...,N

while(1):
csenter() //entrata nella sezione critica (critical section)
critical code
csexit() //uscita dalla sezione critica
non-critical code
</syntaxhighlight>

Ad esempio, tornando al problema dei thread che sommavano 1 a ''sum'' MAX volte, avremo:
<syntaxhighlight lang='c'>
process A:

for (i = 0; i < MAX; i++)
csenter()
sum += 1 //atomicità descritta da csenter(), csexit()
// < sum += 1 > atomicità lasciata al processore
csexit()

process B:

for (i = 0; i < MAX; i++)
csenter()
sum += 1
csexit()
</syntaxhighlight>
 
----
'''Soluzione 1: A turni'''

Qual è il problema? 
*'''mutex''' OK 
*'''deadlock''' OK 
*'''starvation''' OK 
*'''no unnecessary delay''' NO 
:: Perché se P ha bisogno spesso della critical section, P non deve aspettare che Q chieda la critical section e, all'uscita, lo autorizzi di nuovo ad usarla impostando ''turn = P''. Se Q una volta richiesta la sezione non la usa ma si ferma, P non può richiederla ancora perché appartiene ancora a Q.

<syntaxhighlight lang='c'>

turn=P

process P:
while(1)
while (turn != P)
;
critical code
turn = Q
non-critical code

process Q:
while(1)
while (turn != Q)
critical code
turn = P
non-critical code
</syntaxhighlight>
----

'''Soluzione 2: con 2 variabili''', cerchiamo di risolvere il problema dei turni

Finché Q usa la sezione P aspetta, quando Q ha finito P prende la sezione critica e non ci sono ritardi indesiderati.

*'''starvation''' OK
*'''deadlock''' OK
*'''no unnecessary delay''' OK
*'''mutex''' NO
:: Possono essere entrambi come false, escono insieme nel while, tutti e due mettono a true ed entrano assieme nel while.

<syntaxhighlight lang='c'>

inP = false;
inQ = false;

process P:
while(1)
while (inQ)
;
inP = true
critical code
inP = false
non-critical code

process Q:
while(1)
while (inP)
;
inQ = true
critical code
inQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione 3: il problema di soluzione 2 è che i processi non sono al corrente dell'intenzione dell'altro di entrare''' nel while quindi si crea il problema.
*'''mutex''' OK
*'''deadlock''' NO (potrebbero entrambi richiedere, contemporaneamente, l'ingresso alla critical section)
*'''starvation''' OK
*'''non unnecessary delay''' OK

<syntaxhighlight lang='c'>
needP = false;
needQ = false;

process P:
while(1)
needP = true
while (needQ)
;
critical code
needP = false
non-critical code

process Q:
while(1)
needQ = true
while (needP)
;
critical code
needQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione 4''':

*'''mutex''' OK
*'''deadlock''' OK
*'''no unnecessary delay''' OK
*'''starvation''' NO
:: Perché può esistere il processo che prova sempre a chiedere nel momento sbagliato e non esegue mai.

<syntaxhighlight lang='c'>
inP = false;
inQ = false;

process P:
while(1)
inP = true
while (inQ){
inP = false;
delay
inP = true;
}
critical code
inP = false
non-critical code

process Q:
while(1)
inQ = true
while (inQ){
inQ = false;
delay
inQ = true;
}
critical code
inQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione finale''': 
Uniamo soluzione 1 (poco simmetrica) e soluzione 4 (troppo simmetrica) usando quello che ci serve (attraverso ''needP'' e ''needQ'') e, se dovessimo essere tutti e due contemporaneamente a voler entrare, usiamo i turni (''turn'') per entrare nella critical section (settando il need dell'altro processo a false).

*'''mutex''' OK
*'''deadlock''' OK
*'''starvation''' OK
*'''non unnecessary delay''' OK

<syntaxhighlight lang='c'>
needP = false;
needQ = false;
turn = P

process P:
while(1)
needP = true
while (needQ)
if (turn != P) {
needP = false;
while ( turn != P)
; /* busy wait */
needP = true;
}
/*critical code*/
turn = Q
needP = false
/*non-critical code*/

process P:
while(1)
needQ = true
while (needP)
if (turn != Q) {
needQ = false;
while ( turn != Q)
; /* busy wait */
needQ = true;
}
/*critical code*/
turn = P
needQ = false
/*non-critical code*/
</syntaxhighlight>

== Lezione del 13 ottobre 2017 ==
'''Il linguaggio C: PREPROCESSORE'''

Il '''preprocessore''' è uno strumento contenuto nella toolchain di '''gcc''' che esamina il codice sorgente prima che questo venga compilato, e "trasforma" il programma prima della compilazione; è propriamente definito come ''macro processor'', ovvero un esaminatore di '''macro'''.
Le '''macro''' sono delle abbreviazioni che in realtà definiscono delle strutture di codice più grandi, e tornano molto utili in diversi casi nello sviluppo di un programma in C (è buona norma scrivere l’identificatore completamente in '''MAIUSCOLO'''). Il preprocessore esamina le cosiddette '''direttive'''; per conoscere l’output del preprocessore è possibile digitare il comando <kbd>'''gcc -E''' ''{nomeDelSorgente}''</kbd>.

Un primo esempio è dato dalla direttiva '''<kbd>#define</kbd>''', la quale crea una ''macro'', ovvero l’associazione di un identificatore (con o senza parametri) con una stringa di ''token''. Le macro così definite possono assumere quindi diverse funzioni:
# condizione per l’inclusione o meno di codice nel file che verrà passato al compilatore;
# inserimento di '''costanti''' all’interno del codice (notare che questa direttiva nasce molto prima della keyword '''const''' del linguaggio C);
# creazione di abbreviazioni a porzioni di codice più lunghe.

* '''Caso 1''' Il primo caso, che potrebbe essere definito come il più semplice, prevede la dichiarazione di un valore costante, su cui ci si baserà in seguito per includere o meno parti di codice. Per fare ciò occorre introdurre anche altre direttive del preprocessore: '''#ifdef''', '''ifndef''' ed '''endif''', le quali identificano un blocco di codice che deve essere incluso nel file da compilare solo se rispettivamente una macro è definita ''(#ifdef)'' o una macro non è definita ''(#ifndef)'', mentre la direttiva ''#endif'' indica la fine del blocco condizionale.
<syntaxhighlight lang="C">
#include <stdio.h>

#define DEBUG

int main() {
#ifdef DEBUG
printf("In main\n");
#endif

// la macro __linux__ è definita solamente nei sistemi Linux-based
#ifndef __linux__
printf("WARNING: not a Linux system\n");
#endif

return 0;
}
</syntaxhighlight>
:Da notare in questo caso l’utilizzo della macro '''__linux__''', una macro predefinita nei sistemi ''Linux-based'', che consente di discriminare il sistema operativo su cui il programma viene compilato, dando quindi la possibilità di compilare del codice diverso in base alla piattaforma utilizzata. 
*'''Caso 2''' Il secondo caso prevede la presenza di un valore in seguito all’identificatore, che quindi verrà sostituito in ogni sua occorrenza all’interno del codice. È da far notare come questo meccanismo sia simile all’utilizzo della keyword '''const''' del linguaggio, ma quest’ultima nasce solo successivamente come alternativa ''type-safe'' (dal momento che le macro potrebbero essere utilizzate ovunque senza alcun tipo di controllo). Questo meccanismo torna ad esempio quando si vuole effettuare un’operazione un numero di volte prefissato; in questo modo, è sufficiente modificare il valore della macro nella sua definizione, per aggiornare tutto il programma che utilizzava quella macro al nuovo valore.
<syntaxhighlight lang="C">
#include <stdio.h>

#define ITER_NUM 5

int main() {
int i;
for (i = 0; i < ITER_NUM; i++)
printf("Iterazione numero %d\n", i);

return 0;
}
</syntaxhighlight> 
*'''Caso 3''' L’ultimo caso analizzato è quello che può essere definito il più complesso tra i tre. L’identificatore della macro ora presenta anche dei parametri formali, all’interno di parentesi e separati da virgole. Tali parametri compaiono anche nella token string in cui vengono utilizzati (anche più volte) e su cui vengono eseguite delle operazioni. Questa particolarità è utile per permettere di ridurre porzioni di codice che vengono definite così una volta sola, e per essere utilizzate sarà sufficiente scrivere il nome dell’identificatore con i relativi parametri. Da notare come ci sia un numero considerevole di parentesi, che potrebbero quasi sembrare superflue. In realtà sono essenziali per assicurare il corretto ordine di esecuzione delle istruzioni una volta che la stringa di token sarà sostituita alle occorrenze dell’identificatore.
<syntaxhighlight lang="C">
#include <stdio.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

int main() {
printf("%d\n", MAX(10, 20));

return 0;
}
</syntaxhighlight>
:Che produrrà, in seguito all’esecuzione del preprocessore:
<syntaxhighlight lang="C">

int main() {
printf("%d\n", ((10) > (20) ? (10) : (20)));

return 0;
}
</syntaxhighlight>
:Occorre far notare che quella effettuata dal preprocessore non è altro che una '''string substitution''', cioè si limita a sostituire le macro utilizzate nel codice con la rispettiva definizione (ovviamente includendo eventuali parametri formali), ma non effettua alcun tipo di controllo. Ciò significa che occorre prestare molta attenzione quando si utilizzano le macro come nell’ultimo caso illustrato, perché potrebbero comparire dei '''side-effect''' inaspettati. Se si modifica l’esempio precedente in questo modo
<syntaxhighlight lang="C">
#include <stdio.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

int main() {
int i = 100;
printf("%d\n", MAX(10, i++));
printf("%d\n", MAX(10, i));

return 0;
}
</syntaxhighlight>
:si otterrà un risultato che in un primo momento potrebbe essere inaspettato:
<kbd>
101 102
</kbd>
:Ad un’analisi più approfondita tuttavia, è possibile accorgersi dell’errore: il preprocessore effettua una sostituzione testuale dei parametri al momento dell’utilizzo della macro; ciò significa che sostituisce ogni occorrenza del primo parametro nella ''token string'' con il primo valore fornito, e dualmente per il secondo parametro. Il codice che verrà sottoposto al compilatore conterrà quindi due incrementi della variabile <kbd>i</kbd>. Un esempio a grandi linee delle operazioni eseguite dal compilatore è la seguente (per capirlo è necessario aver ben compreso la nozione di '''post-incremento''' della variabile i):
#assegno alla variabile i il valore 100
#10 è maggiore di i?
#NO, incremento i (ora i vale 101)
#scrivo i (101)
#incremento i (ora i vale 102)
#10 è maggiore di i?
#NO, scrivo i (102)

----

Esistono molti altri operatori che si possono utilizzare all’interno delle macro, due esempi sono:
* l’operatore '''#''' che, se anteposto al nome di un parametro nella stringa di token, viene riconosciuto dal processore, che rimpiazza il parametro con il simbolo '''#''' anteposto con il proprio valore letterale convertito in una stringa costante;
* l’operatore '''##''' "combina" due token in uno: unisce il token alla sinistra e quello alla destra dell’operatore per farlo diventare un’unico token. Questo torna molto utile se uno dei due token proviene da un parametro della macro. 
Per un esempio su questi ultimi due operatori: [http://so.v2.cs.unibo.it/wiki/index.php?title=Esercizi_di_%22lettura%22_di_in_linguaggio_C_2017/18#tables_and_preprocessor_tricks tables and preprocessors tricks]
----
 

Per ulteriori approfondimenti sul preprocessore del C: [https://gcc.gnu.org/onlinedocs/cpp/ Approfondimenti sul preprocessore del C]

== Lezione del 17 ottobre 2017 ==

'''Oltre la soluzione di Dekker'''

Nella scorsa lezione di teoria abbiamo visto la soluzione di Dekker dove due processi, per poter entrare ed eseguire la critical section, manifestano prima questo loro bisogno (<code>needP/needQ = true</code>), controllano poi se anche l'altro processo ha comunicato questo bisogno e, in caso affermativo, verrà utilizzata una politica a turni per gestire l'entrata e l'uscita alla sezione critica.

P.S. Nei sistemi reali (specialmente multi-core) la soluzione di Dekker necessita di istruzioni aggiuntive come <code>__syn_synchronize()</code> e <code>sched_yeld()</code>: la prima sincronizza il contenuto delle cache (assicurando la correttezza del risultato) mentre la seconda fa sì che il thread rinunci al suo tempo di CPU permettendo a qualche altro processo di avere la priorità.

Questa soluzione ha però due limiti:
*non funziona con un numero di processi > 2
*è relativamente complicato da capire, si può fare di meglio!

Un'evoluzione più lineare e facilmente adattabile a più di due processi è l''''algoritmo di Peterson''' che, nel caso base, ha la seguente struttura:

<syntaxhighlight lang='c'>
needP = false;
needQ = false;
turn;

process P:
while(1)
/* entry protocol */
needP = true
turn = Q
while(needQ && turn != P)
; /* busy wait */
/* critical section */
needP = false
/* non-critical section */

process Q:
while(1)
/* entry protocol */
needQ = true
turn = P
while(needP && turn != Q)
; /* busy wait */
/* critical section */
needQ = false
/* non-critical section */
</syntaxhighlight>

Questa soluzione è più snella poiché i processi, invece di assegnare la variabile <code>turn</code> all'altro processo come in Dekker, lo fanno prima. 
Possiamo vedere questa soluzione come se avesse una sorta di "anticamera" da cui bisogna necessariamente passare per poter accedere alla sezione critica. 
Entra nella critical section sempre l'ultimo processo a non essere entrato nell'anticamera. 
Questi concetti possono bessimo essere estesi nel caso in cui abbiamo più di due processi a patto di estendere l'anticamera con tanti "stage" quanti sono i processi.

Queste soluzioni funzionano in pratica ma, ci sono ancora tutti i difetti di prima: '''busy wait''' che spreca cicli di CPU e una grande difficoltà nello scrivere programmi concorrenti in questo modo. Ci farebbero davvero comodo dei paradigmi di più alto livello.

Davanti a noi si aprono principalmente due possibilità:
*l'hardware della macchina ci viene in aiuto mascherando gli interrupt (nei sistemi mono-core)
*l'hardware (e gli ingegneri) ci aiuta fornendoci un'apposita istruzione atomica: la '''TEST&SET'''

L'idea che sta alla base della T&S è quella di avere una variabile globale che ci dica se la critical section è libera (0) o occupata (1). 
La T&S viene invocata con due parametri, una variabile locale che serve per verificare lo stato precedente e la variabile globale, e realizza la seguente funzionalità:

'''<code>T&S(x,y) = <x = y; y = 1></code>'''

Quindi, intuitivamente, possiamo avere due casi: o la variabile globale è 0, e la T&S assegna 0 a x e setta la variabile globale a 1, o la variabile globale è a 1 e la funzione semplicemente immagazzina 1 in x.
Questa semplice funzione è abbastanza per realizzare i protocolli csenter() e csexit() e realizzare le critical section:
<syntaxhighlight lang='c'>
G = 0; /* global variable */
csenter():
L;
do{
T&S(L, G)
}while(L == 1)

csexit():
G = 0
</syntaxhighlight>

Questo approccio ci fornisce diversi vantaggi: è nativamente adatto a gestire un numero arbitrario di processi, è semplice e ci garantisce le 4 proprietà fondamentali delle critical section. 
Però c'è ancora busy wait (chiamata anche spin-lock in questo contesto), potrebbe esserci starvation in casi speciali ed è ancora una gestione di basso livello. 
Vorremo un paradigma che permetta di scrivere ancor più facilmente programmi concorrenti e che siano allo stesso tempo semplicemente implementabili.

Il primo paradigma che vediamo è quello dei '''semafori''', proposto da Dijksta nel 1965. (P.S. quasi tutti gli appunti di Dijkstra sono stati scansionati e sono scaricabili da qui: http://www.cs.utexas.edu/users/EWD). 

== Lezione del 20 ottobre 2017 ==
== Lezione del 24 ottobre 2017 ==
== Lezione del 27 ottobre 2017 ==
== Lezione del 31 ottobre 2017 ==
== Lezione del 3 novembre 2017 ==
== Lezione del 7 novembre 2017 ==
== Lezione del 10 novembre 2017 ==
== Lezione del 14 novembre 2017 ==
== Lezione del 17 novembre 2017 ==
== Lezione del 21 novembre 2017 ==
== Lezione del 24 novembre 2017 ==
== Lezione del 28 novembre 2017 ==
== Lezione del 1 dicembre 2017 ==
== Lezione del 5 dicembre 2017 ==
== Lezione del 12 dicembre 2017 ==
== Lezione del 15 dicembre 2017 ==

Lezioni Anno Accademico 2017/18 I semestre

2017-10-18T20:21:37Z

Matt: /* Lezione del 17 ottobre 2017 */

''scrivete qui idee, riassunti dei concetti espressi, commenti approfondimenti sulle lezioni.''

== Lezione del 26 settembre 2017 ==
'''Titolo della lezione: W⁴ H Y'''

* What:
* Who:
----
Noi studenti ed "entrambi" i professori.
 
* When:
----
Il corso ha durata annuale. Verrà svolto ogni martedì e venerdì dalle 15:30 alle 18:30.
* La lezione del martedì sarà dedicata alla programmazione concorrente;
* La lezione del venerdì sarà dedicata alla parte generale. Terminerà circa 15 minuti prima dell'orario stabilito.
 
* Where:
----
Sempre in Aula 1 Ercolani (E1): DISI, Scuole Ercolani, Mura Anteo Zamboni 2B.
 
* How:
----
Il corso si svolgerà tramite:
* Lezioni frontali in aula.
* Attività di laboratorio.
* Esercitazioni.

Inoltre, durante l'ultimo periodo di lezioni del secondo semestre, vi sarà un periodo di ripasso del programma tramite esercizi, in vista dell'esame.
Durante la lezione del 3/10 sono state indicate alcune propedeuticità del corso. tra cui: programmazione, algoritmi e architettura degli elaboratori in primis.
Importanti sono anche i corsi di Analisi matematica e Algebra e geometria. Per farla breve, il primo anno è propedeutico al secondo.
 
* Why:
----
* '''Fonti e strumenti del corso:''' wiki creata di gruppo, lezioni frontali e esercitazioni.
**Non esiste un vero e proprio testo consigliato. Tutte le informazioni sono date DURANTE il corso.
** Per domande specifiche scrivere su mailing list (so@cs.unibo.it);
** Per esercizi, appunti e programma svolto rivolgersi al wiki (so.v2.cs.unibo.it);
** Per live streaming (www.cs.unibo.it/~renzo/live/).
* '''Modalità di esame:''' esame scritto (diviso in due parti: una parte generale e una di programmazione concorrente) + progetto + orale (facoltativo), possibilità di dare solo lo scritto per ottenere un massimo di 18. La modalità per studenti in "difficoltà" è disponibile solo fino agli appelli autunnali.
** Si parlerà del progetto indicativamente a partire da Dicembre 2017.
** L'orale può essere sostenuto da chi vuole migliorare (peggiorare) il voto ottenuto, o da chi vuole ottenere la lode.
* '''Orario di ricevimento per il primo semestre (fino al 15/09/17):''' martedì alle 11:30.
* Università = docenti + studenti.
* Informatica = come generare informazione automatica.
* Hardware, Software, Elaborazione, Comunicazione, Memorizzazione, Digitale/Analogico.
La principale distinzione che facciamo tra '''dato''' e '''informazione''' è che il dato, da solo, è privo di significato. Se, tuttavia, viene interpretato in un particolare contesto allora può diventare informazione significativa per chi sta interpretando i dati.

Un '''algoritmo''' è una o più sequenze non ambigue di passi che, dato un problema, ci permette di risolverlo.

Il nostro algoritmo, scritto in un qualche linguaggio formale, diventa un '''programma''' (sostanzialmente un testo, un insieme di istruzioni).

Un linguaggio è un entità software, ed è definito come una quadrupla (alfabeto, sintassi, lessico, semantica) dove:
*l'''alfabeto'' è l'insieme di simboli che compone il linguaggio.
*il ''lessico'' si può vedere come una funzione che va dai simboli a un booleano e ci dice quali sono le frasi ben formate.
*la ''sintassi'' determina quali delle sequenze scritte sono effettivamente corrette.
*la ''semantica'' associa un significato alle parole ben formate.

== Lezione del 29 settembre 2017 ==
'''Cos'è un sistema operativo e un po' di storia'''

Un ''sistema operativo'' è un programma che gestisce i processi, le risorse e interfaccia le applicazioni con l'hardware dell'elaboratore.

In particolare, il sistema operativo (laddove esiste) è il primo processo ad essere attivato e resta in vita fino allo spegnimento del calcolatore o al sopraggiungere di un errore fatale per il sistema.

A cosa serve un sistema operativo?
Principalmente, ha i seguenti scopi:
# Facilitare l'utilizzo del sistema (senza S.O. sarebbe a carico del programmatore conoscere tutti i linguaggi con cui si comunica con l'architettura della macchina);
# Rendere affidabile, protetto e sicuro l'utilizzo del sistema (e.g. un processo potrebbe recar danno all'intero sistema se non controllato o gestito, potrebbe ignorare i permessi di visualizzazione di un file);
# Astrarre l'hardware (e.g. filesystem);
# Garantire l'efficienza (e.g. non tenere la CPU in idle adottando opportuni algoritmi di scheduling);
# Assicurare portabilità ;

Un approccio molto usato è il cosiddetto approccio a strati ("a livelli") in cui ogni strato utilizza i servizi forniti al livello inferiore e ne fornisce di nuovi a quello superiore.
Astraendo il nostro calcolatore possiamo piazzare al livello più basso l'hardware e, subito sopra, il sistema operativo. I due layer comunicano usando il linguaggio ISA (Instruction Set Architecture), nativo della CPU stessa, al quale si aggiungono quelli che permettono di comunicare con i vari controllori dei dispositivi come la scheda di rete, la stampante, etc. Sopra il livello del sistema operativo possiamo collocare quello delle librerie e, infine, quello degli applicativi.

* '''Systemcall''' = meccanismo usato da un processo per richiedere al SO una qualche funzionalità a livello kernel. Un esempio è la funzione printf() del linguaggio C (stampa a video) che utilizza la systemcall write() (una delle systemcall per la gestione dei dispositivi).
 
----
'''Storia dei sistemi operativi'''

Nella generazione '''zero''' (1800 ca.) possiamo includere Babbage con la sua macchina analitica e lady Ada Lovelace. [[File:290px-AnalyticalMachine Babbage London.jpg |200px|thumb|right|Macchina analitica di Babbage]]

Nella generazione '''uno''' vediamo la comparsa delle valvole con tutti i problemi connessi. Non c'erano utilizzatori delle macchine, le stesse persone che le costruivano erano anche programmatori e fruitori delle stesse.

Nella generazione '''due''' (fine anni '60) arriva il transistor. Quest'ultimo è molto più veloce e piccolo della valvola e, soprattutto, meno incline a guasti. Le macchine iniziano ad essere più economiche grazie alla possibilità di avere un'economia di scala e quindi accessibili al grande pubblico. Questo fa si che, in queste prime fasi, i costruttori non siano più gli unici utilizzatori. [[File:Transistors.jpg |300px|thumb|right|Diversi tipi di Transistor]]

----

A questo punto poiché, pur essendo diventata più accessibile, una macchina costava ancora molto, nasce l'esigenza di non lasciare mai un processore senza lavoro (al fine di massimizzare i ricavi) e di condividere i dati.
In questa fase, infatti, abbiamo sistemi operativi di tipo ''batch'' (che collezionano tutto l'input all'inizio per calcolare e restituire l'output) dove l'inserimento di programmi e dati veniva fatto tramite schede perforate e non c'era interazione. Dai sistemi batch nasce lo ''SPOOL'' (Simultaneous Peripheral Operations On-Line).

Si comincia a pensare di utilizzare i tempi di I/O per poter eseguire altri processi. Questo però solleva almeno due problematiche: da un lato serve un modo per sapere quando un input è davvero finito mentre, dall'altro, bisogna fare in modo che un processo che non richieda I/O non occupi la CPU per un tempo indefinito.
Per la prima problematica la soluzione è rappresentata dall'introduzione degli '''interrupt''', segnali elettrici inviati alla CPU alla fine di ogni input.
Per la seconda, invece, è stato introdotto il cosiddetto '''interval timer''' che non è altro che un dispositivo che invia interrupt dopo un determinato quanto di tempo assicurando che un processo non occupi per troppo tempo il processore.
Questo consente di realizzare sistemi time sharing (il cui più semplice algoritmo è il round-robin) dove un processo può essere in uno dei seguenti tre stati:
*'''READY''' pronto per essere eseguito ma, il processore è già occupato;
*'''RUNNING''' in esecuzione;
*'''WAIT''' in attesa di I/O.

[[File:Dds.png]]

Nella '''quarta''' generazione (anni '70 ca.) vediamo la nascita di molte innovazioni importanti. Si riesce a rimpicciolire di molto i processori facendoli divenire a tutti gli effetti micro-processori. Nei laboratori Bell nasce Unix, un sistema operativo rivoluzionario con time sharing e clonazione dei processi (un processo non viene mai creato dal nulla ma viene prima clonato da uno già esistente e poi, alla copia, viene fatto eseguire un programma). A causa di problemi di portabilità da PDP-9, macchina su cui Unix è nato, a PDP-11 nasce il linguaggio C e il suo compilatore (scritto anch'esso in C).
Mentre Apple I "porta" una nuova idea di pc per tutte le famiglie, nascono molte versioni di Unix.
Per impedire una deriva proprietaria in cui ogni produttore offriva tutto quello che offrivano gli altri ma con qualche feature in più, Richard Stallman fonda il progetto GNU (GNU's Not Unix) per il quale scrive tutta una serie di utilities come il famoso compilatore gcc.
A GNU, per essere operativo, manca però un kernel. Non volendo aspettare i tempi di sviluppo del kernel che Stallman aveva in mente, Linus Torlvalds scrive il kernel '''Linux''' da cui nasce il sistema operativo GNU/Linux.

Nei tempi più recenti nascono i processori multi-core.

== Lezione del 3 ottobre 2017 ==

'''Introduzione alla programmazione concorrente: processi, thread e librerie'''

In programmazione concorrente le nozioni apprese di "algoritmo", "programma" e "processo" devono essere aggiornate. Questo perché non vi è più un programma con un'unica sequenza esecutiva [o meglio, un unico filo (= thread) di esecuzione]. Appare ovvio come servino dei meccanismi per organizzare e sincronizzare tali fili esecutivi, in modo da evitare il verificarsi di eventi non desiderati.

Quando parliamo di ''sistema concorrente'', ci riferiamo ad un sistema in cui due o più "attori" sono eseguiti parallelamente. 

Questi attori possono essere '''processi''' o '''thread'''.
La differenza sostanziale tra queste due tipologie di attori riguarda la condivisione della memoria e dei dati su cui operano. 

Più processi possono eseguire lo stesso programma ma, ognuno di essi, ha i propri dati su cui operare e il suo stato di avanzamento. In particolare:
* un processo è un'entità, un attore che ha delle proprietà e delle risorse associate;
* in ogni istante, il processo può essere interrotto. 
Più thread che vengono eseguiti parallelamente, invece, condividono gli stessi dati su cui operare. 
Codici di esempio:

'''processi'''

<syntaxhighlight lang=C>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[]){
if(fork()) printf("Yes");
else printf("No");
}
</syntaxhighlight>

L'output generato sarà "YesNo" poiché, usando la systemcall ''fork()'', abbiamo creato una nuova copia del processo (un processo figlio). Il processo padre, che ha eseguito con successo la fork(), stamperà "Yes" mentre il figlio stamperà "No".

'''thread'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++) sum = sum + 1;
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

Prima di discutere l'output generato dall'esecuzione di questo codice, è opportuno introdurre, brevemente, gli strumenti utilizzati.

----
'''Pthread (POSIX thread)'''

Citazione dal Silberschatz, Galvin, Gagne:
''Pthread si riferisce allo standard POSIX (IEEE 1003.1c) che definisce una API per la creazione e sincronizzazione dei thread.''

Le istruzioni fondamentali sono:
* '''int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);''' che crea un thread;
* '''int pthread_join(pthread_t thread, void **retval);''' che aspetta che un thread sia completato prima di continuare l'esecuzione.

Da ricordare che, per utilizzare pthread, va incluso l'header ''<pthread.h>'' e durante la compilazione va inclusa la libreria esterna tramite l'opzione ''-pthread''.
----

Torniamo all'output generato dall'esecuzione del secondo codice. 
Nel codice vengono generati cinque thread ed ognuno somma MAX (=1000000) volte 1 a sum. Ci aspettiamo un output di 5000000 ma, in realtà, viene stampato un valore molto minore. 

Questo accade principalmente per due motivi:
*sommare una costante ad una variabile non è un'operazione atomica (richiede almeno tre istruzioni assembler: due mov ed una sum).
*l'interval timer può fermare l'esecuzione del thread mentre sta effettuando una delle tre operazioni richieste per aggiungere uno a sum e provocare un risultato errato.

Questo è uno dei possibili problemi della programmazione concorrente conosciuto come ''race condition''. 
Un sistema di processi multipli presenta una '''race condition''' qualora il risultato finale dell'esecuzione dipenda dalla temporizzazione, o dall'ordine con cui i processi vengono eseguiti.

Per risolvere questo problema possiamo adoperare ancora una volta pthread.
Nello specifico, ci venogono offerte istruzione per realizzare una '''mutua esclusione''' sulle risorse condivise in modo che l'operazione che prima non era atomiche,ora, lo sia e non porti più ad una computazione errata. 
Codice di esempio: 
'''Mutex'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++){
pthread_mutex_lock(&mutex);
sum = sum + 1;
pthread_mutex_unlock(&mutex);
}
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

----
'''MUTEX'''

Un mutex è un dispositivo di MUTual EXclusion (mutua esclusione), ed è utile per proteggere le strutture dati condivise da modifiche concorrenti, implementare sezioni critiche e monitor.

Un mutex ha due possibili stati: sbloccato (non posseduto da nessun thread) e bloccato (posseduto da un thread). Un mutex non può mai essere posseduto da due thread contemporaneamente. Se un thread provasse ad acquisire il mutex, mentre quest'ultimo è già in possesso di un altro thread, dovrebbe aspettare finché non viene rilasciato.
La variabile che realizza il mutex, di tipo ''pthread_mutex_t'', viene inizializzata staticamente assegnandogli PTHREAD_MUTEX_INITIALIZER.
'''pthread_mutex_lock''' acquisisce immediatamente il mutex, se libero. Altrimenti aspetta fino a trovarla, prima o poi, libera. 
'''pthread_mutex_unlock''' rilascia il mutex.

[da: https://sourceware.org/pthreads-win32/manual/pthread_mutex_init.html]
----

Con questa soluzione abbiamo raggiunto un risultato esatto pur avendo pagato in prestazioni: la computazione infatti è più lenta a causa del tempo richiesto dalla sincronizzazione tra i thread.

Consideriamo ora due scenari leggermente più complicati:
* nel primo abbiamo due processi, A e B, che devono accedere a due risorse, X e Y, contemporaneamente prima di poter terminare. Cosa succede se, mentre A acquisisce X, B acquisisce Y?
* nel secondo abbiamo tre processi, A, B e C, che devono accedere alla risorsa X. Che succede se A e B, essendo più veloci, occupano insistentemente la risorsa e non permettono a C di utilizzarla?

La prima condizione si chiama '''deadlock''', la seconda condizione si chiama '''starvation'''. Il deadlock (stallo) è un problema che non può scomparire autonomamente, mentre la starvation ("inedia") si può risolvere da sola. A tal proposito ci viene incontro l'assioma di '''finite progress''': "ogni processo che può avanzare, prima o poi lo farà".
 
In ogni caso, per parlare in maniera più approfondita di queste tematiche:
* avremo bisogno di un modello di riferimento
* avremo bisogno di paradigmi in grado di esprimere la concorrenza (alcuni paradigmi saranno rivolti alla concorrenza a memoria privata; altri al multithreading a risorse condivise)
* dovremo imparare a scrivere programmi
Nel nostro modello di riferimento l'assegnamento di costanti è un operazione atomica. Dagli esempi precedenti, infatti, si evince come ci sia bisogno di creare atomicità in sezioni critiche. Inoltre, il nostro modello dovrà rispettare le proprietà di safety e di liveness, ovvero:
* Tutti i processi danno la stessa risposta;
* Ogni processo corretto da come risposta una tra quelle proposte;
* Ogni processo prima o poi fornisce una risposta.

== Lezione del 6 ottobre 2017 ==
'''Il linguaggio C'''

Il linguaggio C nasce nei primi anni 70 grazie al lavoro di Dennis Ritchie con lo scopo di scrivere il
sistema operativo Unix. Quali sono le caratteristiche di C e cosa lo rende un linguaggio adatto per scrivere un sistema
operativo? Un linguaggio per scrivere un sistema operativo deve:
* essere indipendente dalla macchina su cui viene scritto
* dare la possibilità di lavorare direttamente con la memoria
* permette di andare a modificare i singoli bit in memoria
* essere semplice da usare
* essere massimamente produttivo
* essere veloce, efficiente
C presenta le caratteristiche dette sopra e alcune altre:
* in C, dal punto di vista sintattico, tutto è funzione. Si può vedere un programma in C come un insieme di funzioni. La funzione principale è il '''main'''. L'unica cosa che la distingue è il nome, a parte quello il main è una funzione come le altre. Prende due argomenti: argcount e argvalue, che contengono rispettivamente il numero degli argomenti e un array contenente gli argomenti stessi. L'interfaccia del main è tipicamente: <syntaxhighlight lang=C> int main(int argc, char *argv[]) </syntaxhighlight>
* il costrutto fondamentale è l'espressione. ''expression'' ; = ''instruction''
* sono previste istruzioni di struttura <syntaxhighlight lang=C>if, while, switch, etc.</syntaxhighlight>
* le variabili, per poter essere utilizzate, devono essere sempre definite
* il C è un linguaggio fortemente tipato, però con un certo numero di eccezioni: ad esempio, è possibile fare il casting esplicito di un puntatore void * in qualsiasi tipo, senza che il compilatore dia errori o warnings, con conseguente perdita di type safety
* C è un linguaggio "per adulti": non impone una struttura ordinata al codice, come ad esempio fa invece Python, ed è piena responsabilità del programmatore scrivere programmi ordinati/leggibili. Inoltre molte operazioni che in altri linguaggi non sarebbero permesse lo sono invece in C: anche in questo caso è responsabilità del programmatore fare corretto uso del linguaggio
* C è un linguaggio molto semplice. Come si sopperisce alle mancanze imposte da questa semplicità? Grazie alle librerie: in C tutte le funzionalità aggiuntive (non fornite dal linguaggio stesso, come l'allocazione di memoria, la stampa a schermo, la gestione di input e output) sono fornite dalle librerie
* C è anche sintatticamente semplice. Dove va a finire la complessità sintattica? Nel preprocessore: prima di essere compilato un programma in C passa attraverso un preprocessore, che produce codice in base alle direttive di preprocessione date nel codice stesso <syntaxhighlight lang=C>#ifdef VAR ... #endif, # e ## operator, __LINE__,etc</syntaxhighlight>
* in C vi sono fondamentalmente due tipi di dato: int e float. Tutti gli altri "tipi" di dato sono derivati da essi. Si hanno diversi modificatori, che vanno a modificare la quantità di memoria allocata per la variabile. Alcuni di questi sono <syntaxhighlight lang=C>long, short, char, etc</syntaxhighlight> Un dato di tipo long int ha, solitamente, la dimensione di una parola di memoria della macchina su cui è eseguito il programma. char alloca 8 bits. Se si prende una variabile di un certo tipo e lo si assegna ad una di tipo più ampio, il valore viene mantenuto. Viceversa quando si assegna una variabile di un tipo ad una di tipo meno ampio, una volta "superato il limite" si torna indietro ciclicamente al valore iniziale. Per queste situazioni il compilatore non dà né warnings né errors: sono perfettamente lecite in C
* in C si passa una varibile ad una funzione solo per valore; per passare "per riferimento" una variabile si passa per valore l'indirizzo della variabile
* in C si può fare uso di puntatori alla memoria. Dato un puntatore p, un'istruzione del tipo p+i va letta come: vai avanti di i posizioni della grandezza del tipo del puntatore ognuno. Un vettore in C non è altro che un puntatore che non può essere assegnato. Una scrittura del tipo array[i] è una abbreviazione di *(array + i). Non c'è controllo in C se vado oltre la memoria allocata per l'array. Perché? In Pascal, ad esempio, c'è un tale controllo. Il motivo per cui in C questo manca è che questo controllo genera ulteriore codice macchina. Dovendo C essere efficiente, non ci si può permettere un tale costo aggiuntivo. La responsabilità di non andare oltre è lasciata al programmatore

Esercizio svolto che prende in input due valori tramite i parametri del metodo '''main''', li converte da sequenze di caratteri ad interi, per poi stamparli utilizzando delle '''System Call'''. Lo scopo dell’esercizio è dimostrare come sia possibile utilizzare il linguaggio C senza l’utilizzo di librerie particolari (ad eccezione di quelle per le System Call).

<syntaxhighlight lang=C>
#define _GNU_SOURCE
#include <unistd.h>
#include <sys/syscall.h>

int _uatoi(char *s, int value){
if (*s == 0)
return value;
else if (*s >= '0' && *s <= '9'){
value = value * 10 + (*s - '0');
return _uatoi(s+1, value);
}
}

int uatoi(char *s){
return _uatoi(s, 0);
}

char *uitoa(int val, char *buf, int len){
int i;
for (len = len - 1; len >= 0 && val > 0; len--, val /= 10){
buf[len] = '0' + (val %10);
}

return buf + len + 1;
}

#define MAXOUTLEN 10
int main (int argc, char *argv[]) {
int tot = 0;
int i;
char buf[MAXOUTLEN];
char *result;
for (i = 1; i < argc; i++)
tot += uatoi(argv[i]);
result = uitoa(tot, buf, MAXOUTLEN);
syscall(__NR_write, 1, result, MAXOUTLEN - (result - buf));
syscall(__NR_write, 1, "\n", 1);
return tot;
}
</syntaxhighlight>

== Lezione del 10 ottobre 2017 ==
'''Programmazione concorrente: notazione e un primo problema'''

Esempio di possibile rappresentazione (che non useremo) di codice concorrente. 
'''''A'', ''B'', ''C'', ''D'', ''E''''' rappresentano porzioni di codice. 
'''''//''''' rappresenta esecuzione parallela

<syntaxhighlight lang='c'>
A
cobegin
B
//
C
//
D
coend
E
</syntaxhighlight>

Il codice sarà eseguito come: ''A'' -> ''BCD'' -> ''E''. ''E'' quindi verrà eseguito solo dopo la fine dell'esecuzione di ''BCD''.

Un esempio che si presta molto bene ad illustrare la programmazione concorrente è quello del '''merge sort''' concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
coend
merge (miscela) i risultati
</syntaxhighlight>

Versione errata del merge sort concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
//
merge (miscela) i risultati
coend
</syntaxhighlight>

Avendo un numero ''N'' di processi, vorremmo avere una notazione che ci permetta di definire una porzione di codice come atomica (la sezione critica). Come possiamo procedere? 
Teoricamente, vorremmo avere due funzioni, '''csenter()''' e '''csexit()''' che ci permettano di entrare e uscire dalla sezione critica del codice senza causare errori nella computazione. 
Quali sono le proprietà che queste funzioni debbono rispettare?
# Devono garantire la mutua esclusione (1 solo processo esegue la critical section alla volta). Contando ''n'' csenter() completate e ''m'' csexit() completate la differenza deve essere <=1
# Non devono fare deadlock tra di loro
# Non devono fare starvation tra loro
# ''(no unnecessary delay)'' un processo che non sta usando la critical section {csenter()..csexit()} non deve bloccare un altro processo dall'entrarvi.

La soluzione a questo problema è nota come '''soluzione di Dekker''' (scritta e pubblicata da Dijkstra) che venne presentata in modo graduale attraverso l'utilizzo di quattro possibili, ma sbagliate, soluzioni.

Vorremmo avere programmi che abbiano la seguente struttura:

<syntaxhighlight lang='c'>
process[i], i=1,...,N

while(1):
csenter() //entrata nella sezione critica (critical section)
critical code
csexit() //uscita dalla sezione critica
non-critical code
</syntaxhighlight>

Ad esempio, tornando al problema dei thread che sommavano 1 a ''sum'' MAX volte, avremo:
<syntaxhighlight lang='c'>
process A:

for (i = 0; i < MAX; i++)
csenter()
sum += 1 //atomicità descritta da csenter(), csexit()
// < sum += 1 > atomicità lasciata al processore
csexit()

process B:

for (i = 0; i < MAX; i++)
csenter()
sum += 1
csexit()
</syntaxhighlight>
 
----
'''Soluzione 1: A turni'''

Qual è il problema? 
*'''mutex''' OK 
*'''deadlock''' OK 
*'''starvation''' OK 
*'''no unnecessary delay''' NO 
:: Perché se P ha bisogno spesso della critical section, P non deve aspettare che Q chieda la critical section e, all'uscita, lo autorizzi di nuovo ad usarla impostando ''turn = P''. Se Q una volta richiesta la sezione non la usa ma si ferma, P non può richiederla ancora perché appartiene ancora a Q.

<syntaxhighlight lang='c'>

turn=P

process P:
while(1)
while (turn != P)
;
critical code
turn = Q
non-critical code

process Q:
while(1)
while (turn != Q)
critical code
turn = P
non-critical code
</syntaxhighlight>
----

'''Soluzione 2: con 2 variabili''', cerchiamo di risolvere il problema dei turni

Finché Q usa la sezione P aspetta, quando Q ha finito P prende la sezione critica e non ci sono ritardi indesiderati.

*'''starvation''' OK
*'''deadlock''' OK
*'''no unnecessary delay''' OK
*'''mutex''' NO
:: Possono essere entrambi come false, escono insieme nel while, tutti e due mettono a true ed entrano assieme nel while.

<syntaxhighlight lang='c'>

inP = false;
inQ = false;

process P:
while(1)
while (inQ)
;
inP = true
critical code
inP = false
non-critical code

process Q:
while(1)
while (inP)
;
inQ = true
critical code
inQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione 3: il problema di soluzione 2 è che i processi non sono al corrente dell'intenzione dell'altro di entrare''' nel while quindi si crea il problema.
*'''mutex''' OK
*'''deadlock''' NO (potrebbero entrambi richiedere, contemporaneamente, l'ingresso alla critical section)
*'''starvation''' OK
*'''non unnecessary delay''' OK

<syntaxhighlight lang='c'>
needP = false;
needQ = false;

process P:
while(1)
needP = true
while (needQ)
;
critical code
needP = false
non-critical code

process Q:
while(1)
needQ = true
while (needP)
;
critical code
needQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione 4''':

*'''mutex''' OK
*'''deadlock''' OK
*'''no unnecessary delay''' OK
*'''starvation''' NO
:: Perché può esistere il processo che prova sempre a chiedere nel momento sbagliato e non esegue mai.

<syntaxhighlight lang='c'>
inP = false;
inQ = false;

process P:
while(1)
inP = true
while (inQ){
inP = false;
delay
inP = true;
}
critical code
inP = false
non-critical code

process Q:
while(1)
inQ = true
while (inQ){
inQ = false;
delay
inQ = true;
}
critical code
inQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione finale''': 
Uniamo soluzione 1 (poco simmetrica) e soluzione 4 (troppo simmetrica) usando quello che ci serve (attraverso ''needP'' e ''needQ'') e, se dovessimo essere tutti e due contemporaneamente a voler entrare, usiamo i turni (''turn'') per entrare nella critical section (settando il need dell'altro processo a false).

*'''mutex''' OK
*'''deadlock''' OK
*'''starvation''' OK
*'''non unnecessary delay''' OK

<syntaxhighlight lang='c'>
needP = false;
needQ = false;
turn = P

process P:
while(1)
needP = true
while (needQ)
if (turn != P) {
needP = false;
while ( turn != P)
; /* busy wait */
needP = true;
}
/*critical code*/
turn = Q
needP = false
/*non-critical code*/

process P:
while(1)
needQ = true
while (needP)
if (turn != Q) {
needQ = false;
while ( turn != Q)
; /* busy wait */
needQ = true;
}
/*critical code*/
turn = P
needQ = false
/*non-critical code*/
</syntaxhighlight>

== Lezione del 13 ottobre 2017 ==
'''Il linguaggio C: PREPROCESSORE'''

Il '''preprocessore''' è uno strumento contenuto nella toolchain di '''gcc''' che esamina il codice sorgente prima che questo venga compilato, e "trasforma" il programma prima della compilazione; è propriamente definito come ''macro processor'', ovvero un esaminatore di '''macro'''.
Le '''macro''' sono delle abbreviazioni che in realtà definiscono delle strutture di codice più grandi, e tornano molto utili in diversi casi nello sviluppo di un programma in C (è buona norma scrivere l’identificatore completamente in '''MAIUSCOLO'''). Il preprocessore esamina le cosiddette '''direttive'''; per conoscere l’output del preprocessore è possibile digitare il comando <kbd>'''gcc -E''' ''{nomeDelSorgente}''</kbd>.

Un primo esempio è dato dalla direttiva '''<kbd>#define</kbd>''', la quale crea una ''macro'', ovvero l’associazione di un identificatore (con o senza parametri) con una stringa di ''token''. Le macro così definite possono assumere quindi diverse funzioni:
# condizione per l’inclusione o meno di codice nel file che verrà passato al compilatore;
# inserimento di '''costanti''' all’interno del codice (notare che questa direttiva nasce molto prima della keyword '''const''' del linguaggio C);
# creazione di abbreviazioni a porzioni di codice più lunghe.

* '''Caso 1''' Il primo caso, che potrebbe essere definito come il più semplice, prevede la dichiarazione di un valore costante, su cui ci si baserà in seguito per includere o meno parti di codice. Per fare ciò occorre introdurre anche altre direttive del preprocessore: '''#ifdef''', '''ifndef''' ed '''endif''', le quali identificano un blocco di codice che deve essere incluso nel file da compilare solo se rispettivamente una macro è definita ''(#ifdef)'' o una macro non è definita ''(#ifndef)'', mentre la direttiva ''#endif'' indica la fine del blocco condizionale.
<syntaxhighlight lang="C">
#include <stdio.h>

#define DEBUG

int main() {
#ifdef DEBUG
printf("In main\n");
#endif

// la macro __linux__ è definita solamente nei sistemi Linux-based
#ifndef __linux__
printf("WARNING: not a Linux system\n");
#endif

return 0;
}
</syntaxhighlight>
:Da notare in questo caso l’utilizzo della macro '''__linux__''', una macro predefinita nei sistemi ''Linux-based'', che consente di discriminare il sistema operativo su cui il programma viene compilato, dando quindi la possibilità di compilare del codice diverso in base alla piattaforma utilizzata. 
*'''Caso 2''' Il secondo caso prevede la presenza di un valore in seguito all’identificatore, che quindi verrà sostituito in ogni sua occorrenza all’interno del codice. È da far notare come questo meccanismo sia simile all’utilizzo della keyword '''const''' del linguaggio, ma quest’ultima nasce solo successivamente come alternativa ''type-safe'' (dal momento che le macro potrebbero essere utilizzate ovunque senza alcun tipo di controllo). Questo meccanismo torna ad esempio quando si vuole effettuare un’operazione un numero di volte prefissato; in questo modo, è sufficiente modificare il valore della macro nella sua definizione, per aggiornare tutto il programma che utilizzava quella macro al nuovo valore.
<syntaxhighlight lang="C">
#include <stdio.h>

#define ITER_NUM 5

int main() {
int i;
for (i = 0; i < ITER_NUM; i++)
printf("Iterazione numero %d\n", i);

return 0;
}
</syntaxhighlight> 
*'''Caso 3''' L’ultimo caso analizzato è quello che può essere definito il più complesso tra i tre. L’identificatore della macro ora presenta anche dei parametri formali, all’interno di parentesi e separati da virgole. Tali parametri compaiono anche nella token string in cui vengono utilizzati (anche più volte) e su cui vengono eseguite delle operazioni. Questa particolarità è utile per permettere di ridurre porzioni di codice che vengono definite così una volta sola, e per essere utilizzate sarà sufficiente scrivere il nome dell’identificatore con i relativi parametri. Da notare come ci sia un numero considerevole di parentesi, che potrebbero quasi sembrare superflue. In realtà sono essenziali per assicurare il corretto ordine di esecuzione delle istruzioni una volta che la stringa di token sarà sostituita alle occorrenze dell’identificatore.
<syntaxhighlight lang="C">
#include <stdio.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

int main() {
printf("%d\n", MAX(10, 20));

return 0;
}
</syntaxhighlight>
:Che produrrà, in seguito all’esecuzione del preprocessore:
<syntaxhighlight lang="C">

int main() {
printf("%d\n", ((10) > (20) ? (10) : (20)));

return 0;
}
</syntaxhighlight>
:Occorre far notare che quella effettuata dal preprocessore non è altro che una '''string substitution''', cioè si limita a sostituire le macro utilizzate nel codice con la rispettiva definizione (ovviamente includendo eventuali parametri formali), ma non effettua alcun tipo di controllo. Ciò significa che occorre prestare molta attenzione quando si utilizzano le macro come nell’ultimo caso illustrato, perché potrebbero comparire dei '''side-effect''' inaspettati. Se si modifica l’esempio precedente in questo modo
<syntaxhighlight lang="C">
#include <stdio.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

int main() {
int i = 100;
printf("%d\n", MAX(10, i++));
printf("%d\n", MAX(10, i));

return 0;
}
</syntaxhighlight>
:si otterrà un risultato che in un primo momento potrebbe essere inaspettato:
<kbd>
101 102
</kbd>
:Ad un’analisi più approfondita tuttavia, è possibile accorgersi dell’errore: il preprocessore effettua una sostituzione testuale dei parametri al momento dell’utilizzo della macro; ciò significa che sostituisce ogni occorrenza del primo parametro nella ''token string'' con il primo valore fornito, e dualmente per il secondo parametro. Il codice che verrà sottoposto al compilatore conterrà quindi due incrementi della variabile <kbd>i</kbd>. Un esempio a grandi linee delle operazioni eseguite dal compilatore è la seguente (per capirlo è necessario aver ben compreso la nozione di '''post-incremento''' della variabile i):
#assegno alla variabile i il valore 100
#10 è maggiore di i?
#NO, incremento i (ora i vale 101)
#scrivo i (101)
#incremento i (ora i vale 102)
#10 è maggiore di i?
#NO, scrivo i (102)

----

Esistono molti altri operatori che si possono utilizzare all’interno delle macro, due esempi sono:
* l’operatore '''#''' che, se anteposto al nome di un parametro nella stringa di token, viene riconosciuto dal processore, che rimpiazza il parametro con il simbolo '''#''' anteposto con il proprio valore letterale convertito in una stringa costante;
* l’operatore '''##''' "combina" due token in uno: unisce il token alla sinistra e quello alla destra dell’operatore per farlo diventare un’unico token. Questo torna molto utile se uno dei due token proviene da un parametro della macro. 
Per un esempio su questi ultimi due operatori: [http://so.v2.cs.unibo.it/wiki/index.php?title=Esercizi_di_%22lettura%22_di_in_linguaggio_C_2017/18#tables_and_preprocessor_tricks tables and preprocessors tricks]
----
 

Per ulteriori approfondimenti sul preprocessore del C: [https://gcc.gnu.org/onlinedocs/cpp/ Approfondimenti sul preprocessore del C]

== Lezione del 17 ottobre 2017 ==

'''Oltre la soluzione di Dekker'''

Nella scorsa lezione di teoria abbiamo visto la soluzione di Dekker dove due processi, per poter entrare ed eseguire la critical section, manifestano prima questo loro bisogno (<code>needP/needQ = true</code>), controllano poi se anche l'altro processo ha comunicato questo bisogno e, in caso affermativo, verrà utilizzata una politica a turni per gestire l'entrata e l'uscita alla sezione critica.

P.S. Nei sistemi reali (specialmente multi-core) la soluzione di Dekker necessita di istruzioni aggiuntive come <code>__syn_synchronize()</code> e <code>sched_yeld()</code>: la prima sincronizza il contenuto delle cache (assicurando la correttezza del risultato) mentre la seconda fa sì che il thread rinunci al suo tempo di CPU permettendo a qualche altro processo di avere la priorità.

Questa soluzione ha però due limiti:
*non funziona con un numero di processi > 2
*è relativamente complicato da capire, si può fare di meglio!

Un'evoluzione più lineare e facilmente adattabile a più di due processi è l''''algoritmo di Peterson''' che, nel caso base, ha la seguente struttura:

<syntaxhighlight lang='c'>
needP = false;
needQ = false;
turn;

process P:
while(1)
/* entry protocol */
needP = true
turn = Q
while(needQ && turn != P)
; /* busy wait */
/* critical section */
needP = false
/* non-critical section */

process Q:
while(1)
/* entry protocol */
needQ = true
turn = P
while(needP && turn != Q)
; /* busy wait */
/* critical section */
needQ = false
/* non-critical section */
</syntaxhighlight>

Questa soluzione è più snella poiché i processi, invece di assegnare la variabile <code>turn</code> all'altro processo come in Dekker, lo fanno prima. 
Possiamo vedere questa soluzione come se avesse una sorta di "anticamera" da cui bisogna necessariamente passare per poter accedere alla sezione critica. 
Entra nella critical section sempre l'ultimo processo a non essere entrato nell'anticamera. 
Questi concetti possono bessimo essere estesi nel caso in cui abbiamo più di due processi a patto di estendere l'anticamera con tanti "stage" quanti sono i processi.

Queste soluzioni funzionano in pratica ma, ci sono ancora tutti i difetti di prima: '''busy wait''' che spreca cicli di CPU e una grande difficoltà nello scrivere programmi concorrenti in questo modo. Ci farebbero davvero comodo dei paradigmi di più alto livello.

Davanti a noi si aprono principalmente due possibilità:
*l'hardware della macchina ci viene in aiuto mascherando gli interrupt (nei sistemi mono-core)
*l'hardware (e gli ingegneri) ci aiuta fornendoci un'apposita istruzione atomica: la '''TEST&SET'''

== Lezione del 20 ottobre 2017 ==
== Lezione del 24 ottobre 2017 ==
== Lezione del 27 ottobre 2017 ==
== Lezione del 31 ottobre 2017 ==
== Lezione del 3 novembre 2017 ==
== Lezione del 7 novembre 2017 ==
== Lezione del 10 novembre 2017 ==
== Lezione del 14 novembre 2017 ==
== Lezione del 17 novembre 2017 ==
== Lezione del 21 novembre 2017 ==
== Lezione del 24 novembre 2017 ==
== Lezione del 28 novembre 2017 ==
== Lezione del 1 dicembre 2017 ==
== Lezione del 5 dicembre 2017 ==
== Lezione del 12 dicembre 2017 ==
== Lezione del 15 dicembre 2017 ==

Lezioni Anno Accademico 2017/18 I semestre

2017-10-18T19:28:12Z

Matt: /* Lezione del 17 ottobre 2017 */

''scrivete qui idee, riassunti dei concetti espressi, commenti approfondimenti sulle lezioni.''

== Lezione del 26 settembre 2017 ==
'''Titolo della lezione: W⁴ H Y'''

* What:
* Who:
----
Noi studenti ed "entrambi" i professori.
 
* When:
----
Il corso ha durata annuale. Verrà svolto ogni martedì e venerdì dalle 15:30 alle 18:30.
* La lezione del martedì sarà dedicata alla programmazione concorrente;
* La lezione del venerdì sarà dedicata alla parte generale. Terminerà circa 15 minuti prima dell'orario stabilito.
 
* Where:
----
Sempre in Aula 1 Ercolani (E1): DISI, Scuole Ercolani, Mura Anteo Zamboni 2B.
 
* How:
----
Il corso si svolgerà tramite:
* Lezioni frontali in aula.
* Attività di laboratorio.
* Esercitazioni.

Inoltre, durante l'ultimo periodo di lezioni del secondo semestre, vi sarà un periodo di ripasso del programma tramite esercizi, in vista dell'esame.
Durante la lezione del 3/10 sono state indicate alcune propedeuticità del corso. tra cui: programmazione, algoritmi e architettura degli elaboratori in primis.
Importanti sono anche i corsi di Analisi matematica e Algebra e geometria. Per farla breve, il primo anno è propedeutico al secondo.
 
* Why:
----
* '''Fonti e strumenti del corso:''' wiki creata di gruppo, lezioni frontali e esercitazioni.
**Non esiste un vero e proprio testo consigliato. Tutte le informazioni sono date DURANTE il corso.
** Per domande specifiche scrivere su mailing list (so@cs.unibo.it);
** Per esercizi, appunti e programma svolto rivolgersi al wiki (so.v2.cs.unibo.it);
** Per live streaming (www.cs.unibo.it/~renzo/live/).
* '''Modalità di esame:''' esame scritto (diviso in due parti: una parte generale e una di programmazione concorrente) + progetto + orale (facoltativo), possibilità di dare solo lo scritto per ottenere un massimo di 18. La modalità per studenti in "difficoltà" è disponibile solo fino agli appelli autunnali.
** Si parlerà del progetto indicativamente a partire da Dicembre 2017.
** L'orale può essere sostenuto da chi vuole migliorare (peggiorare) il voto ottenuto, o da chi vuole ottenere la lode.
* '''Orario di ricevimento per il primo semestre (fino al 15/09/17):''' martedì alle 11:30.
* Università = docenti + studenti.
* Informatica = come generare informazione automatica.
* Hardware, Software, Elaborazione, Comunicazione, Memorizzazione, Digitale/Analogico.
La principale distinzione che facciamo tra '''dato''' e '''informazione''' è che il dato, da solo, è privo di significato. Se, tuttavia, viene interpretato in un particolare contesto allora può diventare informazione significativa per chi sta interpretando i dati.

Un '''algoritmo''' è una o più sequenze non ambigue di passi che, dato un problema, ci permette di risolverlo.

Il nostro algoritmo, scritto in un qualche linguaggio formale, diventa un '''programma''' (sostanzialmente un testo, un insieme di istruzioni).

Un linguaggio è un entità software, ed è definito come una quadrupla (alfabeto, sintassi, lessico, semantica) dove:
*l'''alfabeto'' è l'insieme di simboli che compone il linguaggio.
*il ''lessico'' si può vedere come una funzione che va dai simboli a un booleano e ci dice quali sono le frasi ben formate.
*la ''sintassi'' determina quali delle sequenze scritte sono effettivamente corrette.
*la ''semantica'' associa un significato alle parole ben formate.

== Lezione del 29 settembre 2017 ==
'''Cos'è un sistema operativo e un po' di storia'''

Un ''sistema operativo'' è un programma che gestisce i processi, le risorse e interfaccia le applicazioni con l'hardware dell'elaboratore.

In particolare, il sistema operativo (laddove esiste) è il primo processo ad essere attivato e resta in vita fino allo spegnimento del calcolatore o al sopraggiungere di un errore fatale per il sistema.

A cosa serve un sistema operativo?
Principalmente, ha i seguenti scopi:
# Facilitare l'utilizzo del sistema (senza S.O. sarebbe a carico del programmatore conoscere tutti i linguaggi con cui si comunica con l'architettura della macchina);
# Rendere affidabile, protetto e sicuro l'utilizzo del sistema (e.g. un processo potrebbe recar danno all'intero sistema se non controllato o gestito, potrebbe ignorare i permessi di visualizzazione di un file);
# Astrarre l'hardware (e.g. filesystem);
# Garantire l'efficienza (e.g. non tenere la CPU in idle adottando opportuni algoritmi di scheduling);
# Assicurare portabilità ;

Un approccio molto usato è il cosiddetto approccio a strati ("a livelli") in cui ogni strato utilizza i servizi forniti al livello inferiore e ne fornisce di nuovi a quello superiore.
Astraendo il nostro calcolatore possiamo piazzare al livello più basso l'hardware e, subito sopra, il sistema operativo. I due layer comunicano usando il linguaggio ISA (Instruction Set Architecture), nativo della CPU stessa, al quale si aggiungono quelli che permettono di comunicare con i vari controllori dei dispositivi come la scheda di rete, la stampante, etc. Sopra il livello del sistema operativo possiamo collocare quello delle librerie e, infine, quello degli applicativi.

* '''Systemcall''' = meccanismo usato da un processo per richiedere al SO una qualche funzionalità a livello kernel. Un esempio è la funzione printf() del linguaggio C (stampa a video) che utilizza la systemcall write() (una delle systemcall per la gestione dei dispositivi).
 
----
'''Storia dei sistemi operativi'''

Nella generazione '''zero''' (1800 ca.) possiamo includere Babbage con la sua macchina analitica e lady Ada Lovelace. [[File:290px-AnalyticalMachine Babbage London.jpg |200px|thumb|right|Macchina analitica di Babbage]]

Nella generazione '''uno''' vediamo la comparsa delle valvole con tutti i problemi connessi. Non c'erano utilizzatori delle macchine, le stesse persone che le costruivano erano anche programmatori e fruitori delle stesse.

Nella generazione '''due''' (fine anni '60) arriva il transistor. Quest'ultimo è molto più veloce e piccolo della valvola e, soprattutto, meno incline a guasti. Le macchine iniziano ad essere più economiche grazie alla possibilità di avere un'economia di scala e quindi accessibili al grande pubblico. Questo fa si che, in queste prime fasi, i costruttori non siano più gli unici utilizzatori. [[File:Transistors.jpg |300px|thumb|right|Diversi tipi di Transistor]]

----

A questo punto poiché, pur essendo diventata più accessibile, una macchina costava ancora molto, nasce l'esigenza di non lasciare mai un processore senza lavoro (al fine di massimizzare i ricavi) e di condividere i dati.
In questa fase, infatti, abbiamo sistemi operativi di tipo ''batch'' (che collezionano tutto l'input all'inizio per calcolare e restituire l'output) dove l'inserimento di programmi e dati veniva fatto tramite schede perforate e non c'era interazione. Dai sistemi batch nasce lo ''SPOOL'' (Simultaneous Peripheral Operations On-Line).

Si comincia a pensare di utilizzare i tempi di I/O per poter eseguire altri processi. Questo però solleva almeno due problematiche: da un lato serve un modo per sapere quando un input è davvero finito mentre, dall'altro, bisogna fare in modo che un processo che non richieda I/O non occupi la CPU per un tempo indefinito.
Per la prima problematica la soluzione è rappresentata dall'introduzione degli '''interrupt''', segnali elettrici inviati alla CPU alla fine di ogni input.
Per la seconda, invece, è stato introdotto il cosiddetto '''interval timer''' che non è altro che un dispositivo che invia interrupt dopo un determinato quanto di tempo assicurando che un processo non occupi per troppo tempo il processore.
Questo consente di realizzare sistemi time sharing (il cui più semplice algoritmo è il round-robin) dove un processo può essere in uno dei seguenti tre stati:
*'''READY''' pronto per essere eseguito ma, il processore è già occupato;
*'''RUNNING''' in esecuzione;
*'''WAIT''' in attesa di I/O.

[[File:Dds.png]]

Nella '''quarta''' generazione (anni '70 ca.) vediamo la nascita di molte innovazioni importanti. Si riesce a rimpicciolire di molto i processori facendoli divenire a tutti gli effetti micro-processori. Nei laboratori Bell nasce Unix, un sistema operativo rivoluzionario con time sharing e clonazione dei processi (un processo non viene mai creato dal nulla ma viene prima clonato da uno già esistente e poi, alla copia, viene fatto eseguire un programma). A causa di problemi di portabilità da PDP-9, macchina su cui Unix è nato, a PDP-11 nasce il linguaggio C e il suo compilatore (scritto anch'esso in C).
Mentre Apple I "porta" una nuova idea di pc per tutte le famiglie, nascono molte versioni di Unix.
Per impedire una deriva proprietaria in cui ogni produttore offriva tutto quello che offrivano gli altri ma con qualche feature in più, Richard Stallman fonda il progetto GNU (GNU's Not Unix) per il quale scrive tutta una serie di utilities come il famoso compilatore gcc.
A GNU, per essere operativo, manca però un kernel. Non volendo aspettare i tempi di sviluppo del kernel che Stallman aveva in mente, Linus Torlvalds scrive il kernel '''Linux''' da cui nasce il sistema operativo GNU/Linux.

Nei tempi più recenti nascono i processori multi-core.

== Lezione del 3 ottobre 2017 ==

'''Introduzione alla programmazione concorrente: processi, thread e librerie'''

In programmazione concorrente le nozioni apprese di "algoritmo", "programma" e "processo" devono essere aggiornate. Questo perché non vi è più un programma con un'unica sequenza esecutiva [o meglio, un unico filo (= thread) di esecuzione]. Appare ovvio come servino dei meccanismi per organizzare e sincronizzare tali fili esecutivi, in modo da evitare il verificarsi di eventi non desiderati.

Quando parliamo di ''sistema concorrente'', ci riferiamo ad un sistema in cui due o più "attori" sono eseguiti parallelamente. 

Questi attori possono essere '''processi''' o '''thread'''.
La differenza sostanziale tra queste due tipologie di attori riguarda la condivisione della memoria e dei dati su cui operano. 

Più processi possono eseguire lo stesso programma ma, ognuno di essi, ha i propri dati su cui operare e il suo stato di avanzamento. In particolare:
* un processo è un'entità, un attore che ha delle proprietà e delle risorse associate;
* in ogni istante, il processo può essere interrotto. 
Più thread che vengono eseguiti parallelamente, invece, condividono gli stessi dati su cui operare. 
Codici di esempio:

'''processi'''

<syntaxhighlight lang=C>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[]){
if(fork()) printf("Yes");
else printf("No");
}
</syntaxhighlight>

L'output generato sarà "YesNo" poiché, usando la systemcall ''fork()'', abbiamo creato una nuova copia del processo (un processo figlio). Il processo padre, che ha eseguito con successo la fork(), stamperà "Yes" mentre il figlio stamperà "No".

'''thread'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++) sum = sum + 1;
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

Prima di discutere l'output generato dall'esecuzione di questo codice, è opportuno introdurre, brevemente, gli strumenti utilizzati.

----
'''Pthread (POSIX thread)'''

Citazione dal Silberschatz, Galvin, Gagne:
''Pthread si riferisce allo standard POSIX (IEEE 1003.1c) che definisce una API per la creazione e sincronizzazione dei thread.''

Le istruzioni fondamentali sono:
* '''int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);''' che crea un thread;
* '''int pthread_join(pthread_t thread, void **retval);''' che aspetta che un thread sia completato prima di continuare l'esecuzione.

Da ricordare che, per utilizzare pthread, va incluso l'header ''<pthread.h>'' e durante la compilazione va inclusa la libreria esterna tramite l'opzione ''-pthread''.
----

Torniamo all'output generato dall'esecuzione del secondo codice. 
Nel codice vengono generati cinque thread ed ognuno somma MAX (=1000000) volte 1 a sum. Ci aspettiamo un output di 5000000 ma, in realtà, viene stampato un valore molto minore. 

Questo accade principalmente per due motivi:
*sommare una costante ad una variabile non è un'operazione atomica (richiede almeno tre istruzioni assembler: due mov ed una sum).
*l'interval timer può fermare l'esecuzione del thread mentre sta effettuando una delle tre operazioni richieste per aggiungere uno a sum e provocare un risultato errato.

Questo è uno dei possibili problemi della programmazione concorrente conosciuto come ''race condition''. 
Un sistema di processi multipli presenta una '''race condition''' qualora il risultato finale dell'esecuzione dipenda dalla temporizzazione, o dall'ordine con cui i processi vengono eseguiti.

Per risolvere questo problema possiamo adoperare ancora una volta pthread.
Nello specifico, ci venogono offerte istruzione per realizzare una '''mutua esclusione''' sulle risorse condivise in modo che l'operazione che prima non era atomiche,ora, lo sia e non porti più ad una computazione errata. 
Codice di esempio: 
'''Mutex'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++){
pthread_mutex_lock(&mutex);
sum = sum + 1;
pthread_mutex_unlock(&mutex);
}
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

----
'''MUTEX'''

Un mutex è un dispositivo di MUTual EXclusion (mutua esclusione), ed è utile per proteggere le strutture dati condivise da modifiche concorrenti, implementare sezioni critiche e monitor.

Un mutex ha due possibili stati: sbloccato (non posseduto da nessun thread) e bloccato (posseduto da un thread). Un mutex non può mai essere posseduto da due thread contemporaneamente. Se un thread provasse ad acquisire il mutex, mentre quest'ultimo è già in possesso di un altro thread, dovrebbe aspettare finché non viene rilasciato.
La variabile che realizza il mutex, di tipo ''pthread_mutex_t'', viene inizializzata staticamente assegnandogli PTHREAD_MUTEX_INITIALIZER.
'''pthread_mutex_lock''' acquisisce immediatamente il mutex, se libero. Altrimenti aspetta fino a trovarla, prima o poi, libera. 
'''pthread_mutex_unlock''' rilascia il mutex.

[da: https://sourceware.org/pthreads-win32/manual/pthread_mutex_init.html]
----

Con questa soluzione abbiamo raggiunto un risultato esatto pur avendo pagato in prestazioni: la computazione infatti è più lenta a causa del tempo richiesto dalla sincronizzazione tra i thread.

Consideriamo ora due scenari leggermente più complicati:
* nel primo abbiamo due processi, A e B, che devono accedere a due risorse, X e Y, contemporaneamente prima di poter terminare. Cosa succede se, mentre A acquisisce X, B acquisisce Y?
* nel secondo abbiamo tre processi, A, B e C, che devono accedere alla risorsa X. Che succede se A e B, essendo più veloci, occupano insistentemente la risorsa e non permettono a C di utilizzarla?

La prima condizione si chiama '''deadlock''', la seconda condizione si chiama '''starvation'''. Il deadlock (stallo) è un problema che non può scomparire autonomamente, mentre la starvation ("inedia") si può risolvere da sola. A tal proposito ci viene incontro l'assioma di '''finite progress''': "ogni processo che può avanzare, prima o poi lo farà".
 
In ogni caso, per parlare in maniera più approfondita di queste tematiche:
* avremo bisogno di un modello di riferimento
* avremo bisogno di paradigmi in grado di esprimere la concorrenza (alcuni paradigmi saranno rivolti alla concorrenza a memoria privata; altri al multithreading a risorse condivise)
* dovremo imparare a scrivere programmi
Nel nostro modello di riferimento l'assegnamento di costanti è un operazione atomica. Dagli esempi precedenti, infatti, si evince come ci sia bisogno di creare atomicità in sezioni critiche. Inoltre, il nostro modello dovrà rispettare le proprietà di safety e di liveness, ovvero:
* Tutti i processi danno la stessa risposta;
* Ogni processo corretto da come risposta una tra quelle proposte;
* Ogni processo prima o poi fornisce una risposta.

== Lezione del 6 ottobre 2017 ==
'''Il linguaggio C'''

Il linguaggio C nasce nei primi anni 70 grazie al lavoro di Dennis Ritchie con lo scopo di scrivere il
sistema operativo Unix. Quali sono le caratteristiche di C e cosa lo rende un linguaggio adatto per scrivere un sistema
operativo? Un linguaggio per scrivere un sistema operativo deve:
* essere indipendente dalla macchina su cui viene scritto
* dare la possibilità di lavorare direttamente con la memoria
* permette di andare a modificare i singoli bit in memoria
* essere semplice da usare
* essere massimamente produttivo
* essere veloce, efficiente
C presenta le caratteristiche dette sopra e alcune altre:
* in C, dal punto di vista sintattico, tutto è funzione. Si può vedere un programma in C come un insieme di funzioni. La funzione principale è il '''main'''. L'unica cosa che la distingue è il nome, a parte quello il main è una funzione come le altre. Prende due argomenti: argcount e argvalue, che contengono rispettivamente il numero degli argomenti e un array contenente gli argomenti stessi. L'interfaccia del main è tipicamente: <syntaxhighlight lang=C> int main(int argc, char *argv[]) </syntaxhighlight>
* il costrutto fondamentale è l'espressione. ''expression'' ; = ''instruction''
* sono previste istruzioni di struttura <syntaxhighlight lang=C>if, while, switch, etc.</syntaxhighlight>
* le variabili, per poter essere utilizzate, devono essere sempre definite
* il C è un linguaggio fortemente tipato, però con un certo numero di eccezioni: ad esempio, è possibile fare il casting esplicito di un puntatore void * in qualsiasi tipo, senza che il compilatore dia errori o warnings, con conseguente perdita di type safety
* C è un linguaggio "per adulti": non impone una struttura ordinata al codice, come ad esempio fa invece Python, ed è piena responsabilità del programmatore scrivere programmi ordinati/leggibili. Inoltre molte operazioni che in altri linguaggi non sarebbero permesse lo sono invece in C: anche in questo caso è responsabilità del programmatore fare corretto uso del linguaggio
* C è un linguaggio molto semplice. Come si sopperisce alle mancanze imposte da questa semplicità? Grazie alle librerie: in C tutte le funzionalità aggiuntive (non fornite dal linguaggio stesso, come l'allocazione di memoria, la stampa a schermo, la gestione di input e output) sono fornite dalle librerie
* C è anche sintatticamente semplice. Dove va a finire la complessità sintattica? Nel preprocessore: prima di essere compilato un programma in C passa attraverso un preprocessore, che produce codice in base alle direttive di preprocessione date nel codice stesso <syntaxhighlight lang=C>#ifdef VAR ... #endif, # e ## operator, __LINE__,etc</syntaxhighlight>
* in C vi sono fondamentalmente due tipi di dato: int e float. Tutti gli altri "tipi" di dato sono derivati da essi. Si hanno diversi modificatori, che vanno a modificare la quantità di memoria allocata per la variabile. Alcuni di questi sono <syntaxhighlight lang=C>long, short, char, etc</syntaxhighlight> Un dato di tipo long int ha, solitamente, la dimensione di una parola di memoria della macchina su cui è eseguito il programma. char alloca 8 bits. Se si prende una variabile di un certo tipo e lo si assegna ad una di tipo più ampio, il valore viene mantenuto. Viceversa quando si assegna una variabile di un tipo ad una di tipo meno ampio, una volta "superato il limite" si torna indietro ciclicamente al valore iniziale. Per queste situazioni il compilatore non dà né warnings né errors: sono perfettamente lecite in C
* in C si passa una varibile ad una funzione solo per valore; per passare "per riferimento" una variabile si passa per valore l'indirizzo della variabile
* in C si può fare uso di puntatori alla memoria. Dato un puntatore p, un'istruzione del tipo p+i va letta come: vai avanti di i posizioni della grandezza del tipo del puntatore ognuno. Un vettore in C non è altro che un puntatore che non può essere assegnato. Una scrittura del tipo array[i] è una abbreviazione di *(array + i). Non c'è controllo in C se vado oltre la memoria allocata per l'array. Perché? In Pascal, ad esempio, c'è un tale controllo. Il motivo per cui in C questo manca è che questo controllo genera ulteriore codice macchina. Dovendo C essere efficiente, non ci si può permettere un tale costo aggiuntivo. La responsabilità di non andare oltre è lasciata al programmatore

Esercizio svolto che prende in input due valori tramite i parametri del metodo '''main''', li converte da sequenze di caratteri ad interi, per poi stamparli utilizzando delle '''System Call'''. Lo scopo dell’esercizio è dimostrare come sia possibile utilizzare il linguaggio C senza l’utilizzo di librerie particolari (ad eccezione di quelle per le System Call).

<syntaxhighlight lang=C>
#define _GNU_SOURCE
#include <unistd.h>
#include <sys/syscall.h>

int _uatoi(char *s, int value){
if (*s == 0)
return value;
else if (*s >= '0' && *s <= '9'){
value = value * 10 + (*s - '0');
return _uatoi(s+1, value);
}
}

int uatoi(char *s){
return _uatoi(s, 0);
}

char *uitoa(int val, char *buf, int len){
int i;
for (len = len - 1; len >= 0 && val > 0; len--, val /= 10){
buf[len] = '0' + (val %10);
}

return buf + len + 1;
}

#define MAXOUTLEN 10
int main (int argc, char *argv[]) {
int tot = 0;
int i;
char buf[MAXOUTLEN];
char *result;
for (i = 1; i < argc; i++)
tot += uatoi(argv[i]);
result = uitoa(tot, buf, MAXOUTLEN);
syscall(__NR_write, 1, result, MAXOUTLEN - (result - buf));
syscall(__NR_write, 1, "\n", 1);
return tot;
}
</syntaxhighlight>

== Lezione del 10 ottobre 2017 ==
'''Programmazione concorrente: notazione e un primo problema'''

Esempio di possibile rappresentazione (che non useremo) di codice concorrente. 
'''''A'', ''B'', ''C'', ''D'', ''E''''' rappresentano porzioni di codice. 
'''''//''''' rappresenta esecuzione parallela

<syntaxhighlight lang='c'>
A
cobegin
B
//
C
//
D
coend
E
</syntaxhighlight>

Il codice sarà eseguito come: ''A'' -> ''BCD'' -> ''E''. ''E'' quindi verrà eseguito solo dopo la fine dell'esecuzione di ''BCD''.

Un esempio che si presta molto bene ad illustrare la programmazione concorrente è quello del '''merge sort''' concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
coend
merge (miscela) i risultati
</syntaxhighlight>

Versione errata del merge sort concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
//
merge (miscela) i risultati
coend
</syntaxhighlight>

Avendo un numero ''N'' di processi, vorremmo avere una notazione che ci permetta di definire una porzione di codice come atomica (la sezione critica). Come possiamo procedere? 
Teoricamente, vorremmo avere due funzioni, '''csenter()''' e '''csexit()''' che ci permettano di entrare e uscire dalla sezione critica del codice senza causare errori nella computazione. 
Quali sono le proprietà che queste funzioni debbono rispettare?
# Devono garantire la mutua esclusione (1 solo processo esegue la critical section alla volta). Contando ''n'' csenter() completate e ''m'' csexit() completate la differenza deve essere <=1
# Non devono fare deadlock tra di loro
# Non devono fare starvation tra loro
# ''(no unnecessary delay)'' un processo che non sta usando la critical section {csenter()..csexit()} non deve bloccare un altro processo dall'entrarvi.

La soluzione a questo problema è nota come '''soluzione di Dekker''' (scritta e pubblicata da Dijkstra) che venne presentata in modo graduale attraverso l'utilizzo di quattro possibili, ma sbagliate, soluzioni.

Vorremmo avere programmi che abbiano la seguente struttura:

<syntaxhighlight lang='c'>
process[i], i=1,...,N

while(1):
csenter() //entrata nella sezione critica (critical section)
critical code
csexit() //uscita dalla sezione critica
non-critical code
</syntaxhighlight>

Ad esempio, tornando al problema dei thread che sommavano 1 a ''sum'' MAX volte, avremo:
<syntaxhighlight lang='c'>
process A:

for (i = 0; i < MAX; i++)
csenter()
sum += 1 //atomicità descritta da csenter(), csexit()
// < sum += 1 > atomicità lasciata al processore
csexit()

process B:

for (i = 0; i < MAX; i++)
csenter()
sum += 1
csexit()
</syntaxhighlight>
 
----
'''Soluzione 1: A turni'''

Qual è il problema? 
*'''mutex''' OK 
*'''deadlock''' OK 
*'''starvation''' OK 
*'''no unnecessary delay''' NO 
:: Perché se P ha bisogno spesso della critical section, P non deve aspettare che Q chieda la critical section e, all'uscita, lo autorizzi di nuovo ad usarla impostando ''turn = P''. Se Q una volta richiesta la sezione non la usa ma si ferma, P non può richiederla ancora perché appartiene ancora a Q.

<syntaxhighlight lang='c'>

turn=P

process P:
while(1)
while (turn != P)
;
critical code
turn = Q
non-critical code

process Q:
while(1)
while (turn != Q)
critical code
turn = P
non-critical code
</syntaxhighlight>
----

'''Soluzione 2: con 2 variabili''', cerchiamo di risolvere il problema dei turni

Finché Q usa la sezione P aspetta, quando Q ha finito P prende la sezione critica e non ci sono ritardi indesiderati.

*'''starvation''' OK
*'''deadlock''' OK
*'''no unnecessary delay''' OK
*'''mutex''' NO
:: Possono essere entrambi come false, escono insieme nel while, tutti e due mettono a true ed entrano assieme nel while.

<syntaxhighlight lang='c'>

inP = false;
inQ = false;

process P:
while(1)
while (inQ)
;
inP = true
critical code
inP = false
non-critical code

process Q:
while(1)
while (inP)
;
inQ = true
critical code
inQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione 3: il problema di soluzione 2 è che i processi non sono al corrente dell'intenzione dell'altro di entrare''' nel while quindi si crea il problema.
*'''mutex''' OK
*'''deadlock''' NO (potrebbero entrambi richiedere, contemporaneamente, l'ingresso alla critical section)
*'''starvation''' OK
*'''non unnecessary delay''' OK

<syntaxhighlight lang='c'>
needP = false;
needQ = false;

process P:
while(1)
needP = true
while (needQ)
;
critical code
needP = false
non-critical code

process Q:
while(1)
needQ = true
while (needP)
;
critical code
needQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione 4''':

*'''mutex''' OK
*'''deadlock''' OK
*'''no unnecessary delay''' OK
*'''starvation''' NO
:: Perché può esistere il processo che prova sempre a chiedere nel momento sbagliato e non esegue mai.

<syntaxhighlight lang='c'>
inP = false;
inQ = false;

process P:
while(1)
inP = true
while (inQ){
inP = false;
delay
inP = true;
}
critical code
inP = false
non-critical code

process Q:
while(1)
inQ = true
while (inQ){
inQ = false;
delay
inQ = true;
}
critical code
inQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione finale''': 
Uniamo soluzione 1 (poco simmetrica) e soluzione 4 (troppo simmetrica) usando quello che ci serve (attraverso ''needP'' e ''needQ'') e, se dovessimo essere tutti e due contemporaneamente a voler entrare, usiamo i turni (''turn'') per entrare nella critical section (settando il need dell'altro processo a false).

*'''mutex''' OK
*'''deadlock''' OK
*'''starvation''' OK
*'''non unnecessary delay''' OK

<syntaxhighlight lang='c'>
needP = false;
needQ = false;
turn = P

process P:
while(1)
needP = true
while (needQ)
if (turn != P) {
needP = false;
while ( turn != P)
; /* busy wait */
needP = true;
}
/*critical code*/
turn = Q
needP = false
/*non-critical code*/

process P:
while(1)
needQ = true
while (needP)
if (turn != Q) {
needQ = false;
while ( turn != Q)
; /* busy wait */
needQ = true;
}
/*critical code*/
turn = P
needQ = false
/*non-critical code*/
</syntaxhighlight>

== Lezione del 13 ottobre 2017 ==
'''Il linguaggio C: PREPROCESSORE'''

Il '''preprocessore''' è uno strumento contenuto nella toolchain di '''gcc''' che esamina il codice sorgente prima che questo venga compilato, e "trasforma" il programma prima della compilazione; è propriamente definito come ''macro processor'', ovvero un esaminatore di '''macro'''.
Le '''macro''' sono delle abbreviazioni che in realtà definiscono delle strutture di codice più grandi, e tornano molto utili in diversi casi nello sviluppo di un programma in C (è buona norma scrivere l’identificatore completamente in '''MAIUSCOLO'''). Il preprocessore esamina le cosiddette '''direttive'''; per conoscere l’output del preprocessore è possibile digitare il comando <kbd>'''gcc -E''' ''{nomeDelSorgente}''</kbd>.

Un primo esempio è dato dalla direttiva '''<kbd>#define</kbd>''', la quale crea una ''macro'', ovvero l’associazione di un identificatore (con o senza parametri) con una stringa di ''token''. Le macro così definite possono assumere quindi diverse funzioni:
# condizione per l’inclusione o meno di codice nel file che verrà passato al compilatore;
# inserimento di '''costanti''' all’interno del codice (notare che questa direttiva nasce molto prima della keyword '''const''' del linguaggio C);
# creazione di abbreviazioni a porzioni di codice più lunghe.

* '''Caso 1''' Il primo caso, che potrebbe essere definito come il più semplice, prevede la dichiarazione di un valore costante, su cui ci si baserà in seguito per includere o meno parti di codice. Per fare ciò occorre introdurre anche altre direttive del preprocessore: '''#ifdef''', '''ifndef''' ed '''endif''', le quali identificano un blocco di codice che deve essere incluso nel file da compilare solo se rispettivamente una macro è definita ''(#ifdef)'' o una macro non è definita ''(#ifndef)'', mentre la direttiva ''#endif'' indica la fine del blocco condizionale.
<syntaxhighlight lang="C">
#include <stdio.h>

#define DEBUG

int main() {
#ifdef DEBUG
printf("In main\n");
#endif

// la macro __linux__ è definita solamente nei sistemi Linux-based
#ifndef __linux__
printf("WARNING: not a Linux system\n");
#endif

return 0;
}
</syntaxhighlight>
:Da notare in questo caso l’utilizzo della macro '''__linux__''', una macro predefinita nei sistemi ''Linux-based'', che consente di discriminare il sistema operativo su cui il programma viene compilato, dando quindi la possibilità di compilare del codice diverso in base alla piattaforma utilizzata. 
*'''Caso 2''' Il secondo caso prevede la presenza di un valore in seguito all’identificatore, che quindi verrà sostituito in ogni sua occorrenza all’interno del codice. È da far notare come questo meccanismo sia simile all’utilizzo della keyword '''const''' del linguaggio, ma quest’ultima nasce solo successivamente come alternativa ''type-safe'' (dal momento che le macro potrebbero essere utilizzate ovunque senza alcun tipo di controllo). Questo meccanismo torna ad esempio quando si vuole effettuare un’operazione un numero di volte prefissato; in questo modo, è sufficiente modificare il valore della macro nella sua definizione, per aggiornare tutto il programma che utilizzava quella macro al nuovo valore.
<syntaxhighlight lang="C">
#include <stdio.h>

#define ITER_NUM 5

int main() {
int i;
for (i = 0; i < ITER_NUM; i++)
printf("Iterazione numero %d\n", i);

return 0;
}
</syntaxhighlight> 
*'''Caso 3''' L’ultimo caso analizzato è quello che può essere definito il più complesso tra i tre. L’identificatore della macro ora presenta anche dei parametri formali, all’interno di parentesi e separati da virgole. Tali parametri compaiono anche nella token string in cui vengono utilizzati (anche più volte) e su cui vengono eseguite delle operazioni. Questa particolarità è utile per permettere di ridurre porzioni di codice che vengono definite così una volta sola, e per essere utilizzate sarà sufficiente scrivere il nome dell’identificatore con i relativi parametri. Da notare come ci sia un numero considerevole di parentesi, che potrebbero quasi sembrare superflue. In realtà sono essenziali per assicurare il corretto ordine di esecuzione delle istruzioni una volta che la stringa di token sarà sostituita alle occorrenze dell’identificatore.
<syntaxhighlight lang="C">
#include <stdio.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

int main() {
printf("%d\n", MAX(10, 20));

return 0;
}
</syntaxhighlight>
:Che produrrà, in seguito all’esecuzione del preprocessore:
<syntaxhighlight lang="C">

int main() {
printf("%d\n", ((10) > (20) ? (10) : (20)));

return 0;
}
</syntaxhighlight>
:Occorre far notare che quella effettuata dal preprocessore non è altro che una '''string substitution''', cioè si limita a sostituire le macro utilizzate nel codice con la rispettiva definizione (ovviamente includendo eventuali parametri formali), ma non effettua alcun tipo di controllo. Ciò significa che occorre prestare molta attenzione quando si utilizzano le macro come nell’ultimo caso illustrato, perché potrebbero comparire dei '''side-effect''' inaspettati. Se si modifica l’esempio precedente in questo modo
<syntaxhighlight lang="C">
#include <stdio.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

int main() {
int i = 100;
printf("%d\n", MAX(10, i++));
printf("%d\n", MAX(10, i));

return 0;
}
</syntaxhighlight>
:si otterrà un risultato che in un primo momento potrebbe essere inaspettato:
<kbd>
101 102
</kbd>
:Ad un’analisi più approfondita tuttavia, è possibile accorgersi dell’errore: il preprocessore effettua una sostituzione testuale dei parametri al momento dell’utilizzo della macro; ciò significa che sostituisce ogni occorrenza del primo parametro nella ''token string'' con il primo valore fornito, e dualmente per il secondo parametro. Il codice che verrà sottoposto al compilatore conterrà quindi due incrementi della variabile <kbd>i</kbd>. Un esempio a grandi linee delle operazioni eseguite dal compilatore è la seguente (per capirlo è necessario aver ben compreso la nozione di '''post-incremento''' della variabile i):
#assegno alla variabile i il valore 100
#10 è maggiore di i?
#NO, incremento i (ora i vale 101)
#scrivo i (101)
#incremento i (ora i vale 102)
#10 è maggiore di i?
#NO, scrivo i (102)

----

Esistono molti altri operatori che si possono utilizzare all’interno delle macro, due esempi sono:
* l’operatore '''#''' che, se anteposto al nome di un parametro nella stringa di token, viene riconosciuto dal processore, che rimpiazza il parametro con il simbolo '''#''' anteposto con il proprio valore letterale convertito in una stringa costante;
* l’operatore '''##''' "combina" due token in uno: unisce il token alla sinistra e quello alla destra dell’operatore per farlo diventare un’unico token. Questo torna molto utile se uno dei due token proviene da un parametro della macro. 
Per un esempio su questi ultimi due operatori: [http://so.v2.cs.unibo.it/wiki/index.php?title=Esercizi_di_%22lettura%22_di_in_linguaggio_C_2017/18#tables_and_preprocessor_tricks tables and preprocessors tricks]
----
 

Per ulteriori approfondimenti sul preprocessore del C: [https://gcc.gnu.org/onlinedocs/cpp/ Approfondimenti sul preprocessore del C]

== Lezione del 17 ottobre 2017 ==

'''Oltre la soluzione di Dekker'''

Nella scorsa lezione di teoria abbiamo visto la soluzione di Dekker dove due processi, per poter entrare ed eseguire la critical section, manifestano prima questo loro bisogno (<code>needP/needQ = true</code>), controllano poi se anche l'altro processo ha comunicato questo bisogno e, in caso affermativo, verrà utilizzata una politica a turni per gestire l'entrata e l'uscita alla sezione critica.

Questa soluzione ha però due limiti:
*non funziona con un numero di processi > 2
*è relativamente complicato da capire, si può fare di meglio!

Un'evoluzione più lineare e facilmente adattabile a più di due processi è l''''algoritmo di Peterson''' che, nel caso base, ha la seguente struttura:

<syntaxhighlight lang='c'>
needP = false;
needQ = false;
turn;

process P:
while(1)
/* entry protocol */
needP = true
turn = Q
while(needQ && turn != P)
; /* busy wait */
/* critical section */
needP = false
/* non-critical section */

process Q:
while(1)
/* entry protocol */
needQ = true
turn = P
while(needP && turn != Q)
; /* busy wait */
/* critical section */
needQ = false
/* non-critical section */
</syntaxhighlight>

== Lezione del 20 ottobre 2017 ==
== Lezione del 24 ottobre 2017 ==
== Lezione del 27 ottobre 2017 ==
== Lezione del 31 ottobre 2017 ==
== Lezione del 3 novembre 2017 ==
== Lezione del 7 novembre 2017 ==
== Lezione del 10 novembre 2017 ==
== Lezione del 14 novembre 2017 ==
== Lezione del 17 novembre 2017 ==
== Lezione del 21 novembre 2017 ==
== Lezione del 24 novembre 2017 ==
== Lezione del 28 novembre 2017 ==
== Lezione del 1 dicembre 2017 ==
== Lezione del 5 dicembre 2017 ==
== Lezione del 12 dicembre 2017 ==
== Lezione del 15 dicembre 2017 ==

Lezioni Anno Accademico 2017/18 I semestre

2017-10-10T20:27:11Z

Matt: /* Lezione del 10 ottobre 2017 */

''scrivete qui idee, riassunti dei concetti espressi, commenti approfondimenti sulle lezioni.''

== Lezione del 26 settembre 2017 ==
'''Titolo della lezione: W⁴ H Y'''

* What:
* Who:
----
Noi studenti ed "entrambi" i professori.
 
* When:
----
Il corso ha durata annuale. Verrà svolto ogni martedì e venerdì dalle 15:30 alle 18:30.
* La lezione del martedì sarà dedicata alla programmazione concorrente;
* La lezione del venerdì sarà dedicata alla parte generale. Terminerà circa 15 minuti prima dell'orario stabilito.
 
* Where:
----
Sempre in Aula 1 Ercolani (E1): DISI, Scuole Ercolani, Mura Anteo Zamboni 2B.
 
* How:
----
Il corso si svolgerà tramite:
* Lezioni frontali in aula.
* Attività di laboratorio.
* Esercitazioni.

Inoltre, durante l'ultimo periodo di lezioni del secondo semestre, vi sarà un periodo di ripasso del programma tramite esercizi, in vista dell'esame.
Durante la lezione del 3/10 sono state indicate alcune propedeuticità del corso. tra cui: programmazione, algoritmi e architettura degli elaboratori in primis.
Importanti sono anche i corsi di Analisi matematica e Algebra e geometria. Per farla breve, il primo anno è propedeutico al secondo.
 
* Why:
----
* '''Fonti e strumenti del corso:''' wiki creata di gruppo, lezioni frontali e esercitazioni.
**Non esiste un vero e proprio testo consigliato. Tutte le informazioni sono date DURANTE il corso.
** Per domande specifiche scrivere su mailing list (so@cs.unibo.it);
** Per esercizi, appunti e programma svolto rivolgersi al wiki (so.v2.cs.unibo.it);
** Per live streaming (www.cs.unibo.it/~renzo/live/).
* '''Modalità di esame:''' esame scritto (diviso in due parti: una parte generale e una di programmazione concorrente) + progetto + orale (facoltativo), possibilità di dare solo lo scritto per ottenere un massimo di 18. La modalità per studenti in "difficoltà" è disponibile solo fino agli appelli autunnali.
** Si parlerà del progetto indicativamente a partire da Dicembre 2017.
** L'orale può essere sostenuto da chi vuole migliorare (peggiorare) il voto ottenuto, o da chi vuole ottenere la lode.
* '''Orario di ricevimento per il primo semestre (fino al 15/09/17):''' martedì alle 11:30.
* Università = docenti + studenti.
* Informatica = come generare informazione automatica.
* Hardware, Software, Elaborazione, Comunicazione, Memorizzazione, Digitale/Analogico.
La principale distinzione che facciamo tra '''dato''' e '''informazione''' è che il dato, da solo, è privo di significato. Se, tuttavia, viene interpretato in un particolare contesto allora può diventare informazione significativa per chi sta interpretando i dati.

Un '''algoritmo''' è una o più sequenze non ambigue di passi che, dato un problema, ci permette di risolverlo.

Il nostro algoritmo, scritto in un qualche linguaggio formale, diventa un '''programma''' (sostanzialmente un testo, un insieme di istruzioni).

Un linguaggio è un entità software, ed è definito come una quadrupla (alfabeto, sintassi, lessico, semantica) dove:
*l'''alfabeto'' è l'insieme di simboli che compone il linguaggio.
*il ''lessico'' si può vedere come una funzione che va dai simboli a un booleano e ci dice quali sono le frasi ben formate.
*la ''sintassi'' determina quali delle sequenze scritte sono effettivamente corrette.
*la ''semantica'' associa un significato alle parole ben formate.

== Lezione del 29 settembre 2017 ==
'''Cos'è un sistema operativo e un po' di storia'''

Un ''sistema operativo'' è un programma che gestisce i processi, le risorse e interfaccia le applicazioni con l'hardware dell'elaboratore.

In particolare, il sistema operativo (laddove esiste) è il primo processo ad essere attivato e resta in vita fino allo spegnimento del calcolatore o al sopraggiungere di un errore fatale per il sistema.

A cosa serve un sistema operativo?
Principalmente, ha i seguenti scopi:
# Facilitare l'utilizzo del sistema (senza S.O. sarebbe a carico del programmatore conoscere tutti i linguaggi con cui si comunica con l'architettura della macchina);
# Rendere affidabile, protetto e sicuro l'utilizzo del sistema (e.g. un processo potrebbe recar danno all'intero sistema se non controllato o gestito, potrebbe ignorare i permessi di visualizzazione di un file);
# Astrarre l'hardware (e.g. filesystem);
# Garantire l'efficienza (e.g. non tenere la CPU in idle adottando opportuni algoritmi di scheduling);
# Assicurare portabilità ;

Un approccio molto usato è il cosiddetto approccio a strati ("a livelli") in cui ogni strato utilizza i servizi forniti al livello inferiore e ne fornisce di nuovi a quello superiore.
Astraendo il nostro calcolatore possiamo piazzare al livello più basso l'hardware e, subito sopra, il sistema operativo. I due layer comunicano usando il linguaggio ISA (Instruction Set Architecture), nativo della CPU stessa, al quale si aggiungono quelli che permettono di comunicare con i vari controllori dei dispositivi come la scheda di rete, la stampante, etc. Sopra il livello del sistema operativo possiamo collocare quello delle librerie e, infine, quello degli applicativi.

* '''Systemcall''' = meccanismo usato da un processo per richiedere al SO una qualche funzionalità a livello kernel. Un esempio è la funzione printf() del linguaggio C (stampa a video) che utilizza la systemcall write() (una delle systemcall per la gestione dei dispositivi).
 
----
'''Storia dei sistemi operativi'''

Nella generazione '''zero''' (1800 ca.) possiamo includere Babbage con la sua macchina analitica e lady Ada Lovelace. [[File:290px-AnalyticalMachine Babbage London.jpg |200px|thumb|right|Macchina analitica di Babbage]]

Nella generazione '''uno''' vediamo la comparsa delle valvole con tutti i problemi connessi. Non c'erano utilizzatori delle macchine, le stesse persone che le costruivano erano anche programmatori e fruitori delle stesse.

Nella generazione '''due''' (fine anni '60) arriva il transistor. Quest'ultimo è molto più veloce e piccolo della valvola e, soprattutto, meno incline a guasti. Le macchine iniziano ad essere più economiche grazie alla possibilità di avere un'economia di scala e quindi accessibili al grande pubblico. Questo fa si che, in queste prime fasi, i costruttori non siano più gli unici utilizzatori. [[File:Transistors.jpg |300px|thumb|right|Diversi tipi di Transistor]]

----

A questo punto poiché, pur essendo diventata più accessibile, una macchina costava ancora molto, nasce l'esigenza di non lasciare mai un processore senza lavoro (al fine di massimizzare i ricavi) e di condividere i dati.
In questa fase, infatti, abbiamo sistemi operativi di tipo ''batch'' (che collezionano tutto l'input all'inizio per calcolare e restituire l'output) dove l'inserimento di programmi e dati veniva fatto tramite schede perforate e non c'era interazione. Dai sistemi batch nasce lo ''SPOOL'' (Simultaneous Peripheral Operations On-Line).

Si comincia a pensare di utilizzare i tempi di I/O per poter eseguire altri processi. Questo però solleva almeno due problematiche: da un lato serve un modo per sapere quando un input è davvero finito mentre, dall'altro, bisogna fare in modo che un processo che non richieda I/O non occupi la CPU per un tempo indefinito.
Per la prima problematica la soluzione è rappresentata dall'introduzione degli '''interrupt''', segnali elettrici inviati alla CPU alla fine di ogni input.
Per la seconda, invece, è stato introdotto il cosiddetto '''interval timer''' che non è altro che un dispositivo che invia interrupt dopo un determinato quanto di tempo assicurando che un processo non occupi per troppo tempo il processore.
Questo consente di realizzare sistemi time sharing (il cui più semplice algoritmo è il round-robin) dove un processo può essere in uno dei seguenti tre stati:
*'''READY''' pronto per essere eseguito ma, il processore è già occupato;
*'''RUNNING''' in esecuzione;
*'''WAIT''' in attesa di I/O.

[[File:Dds.png]]

Nella '''quarta''' generazione (anni '70 ca.) vediamo la nascita di molte innovazioni importanti. Si riesce a rimpicciolire di molto i processori facendoli divenire a tutti gli effetti micro-processori. Nei laboratori Bell nasce Unix, un sistema operativo rivoluzionario con time sharing e clonazione dei processi (un processo non viene mai creato dal nulla ma viene prima clonato da uno già esistente e poi, alla copia, viene fatto eseguire un programma). A causa di problemi di portabilità da PDP-9, macchina su cui Unix è nato, a PDP-11 nasce il linguaggio C e il suo compilatore (scritto anch'esso in C).
Mentre Apple I "porta" una nuova idea di pc per tutte le famiglie, nascono molte versioni di Unix.
Per impedire una deriva proprietaria in cui ogni produttore offriva tutto quello che offrivano gli altri ma con qualche feature in più, Richard Stallman fonda il progetto GNU (GNU's Not Unix) per il quale scrive tutta una serie di utilities come il famoso compilatore gcc.
A GNU, per essere operativo, manca però un kernel. Non volendo aspettare i tempi di sviluppo del kernel che Stallman aveva in mente, Linus Torlvalds scrive il kernel '''Linux''' da cui nasce il sistema operativo GNU/Linux.

Nei tempi più recenti nascono i processori multi-core.

== Lezione del 3 ottobre 2017 ==

'''Introduzione alla programmazione concorrente: processi, thread e librerie'''

In programmazione concorrente le nozioni apprese di "algoritmo", "programma" e "processo" devono essere aggiornate. Questo perché non vi è più un programma con un'unica sequenza esecutiva [o meglio, un unico filo (= thread) di esecuzione]. Appare ovvio come servino dei meccanismi per organizzare e sincronizzare tali fili esecutivi, in modo da evitare il verificarsi di eventi non desiderati.

Quando parliamo di ''sistema concorrente'', ci riferiamo ad un sistema in cui due o più "attori" sono eseguiti parallelamente. 

Questi attori possono essere '''processi''' o '''thread'''.
La differenza sostanziale tra queste due tipologie di attori riguarda la condivisione della memoria e dei dati su cui operano. 

Più processi possono eseguire lo stesso programma ma, ognuno di essi, ha i propri dati su cui operare e il suo stato di avanzamento. In particolare:
* un processo è un'entità, un attore che ha delle proprietà e delle risorse associate;
* in ogni istante, il processo può essere interrotto. 
Più thread che vengono eseguiti parallelamente, invece, condividono gli stessi dati su cui operare. 
Codici di esempio:

'''processi'''

<syntaxhighlight lang=C>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[]){
if(fork()) printf("Yes");
else printf("No");
}
</syntaxhighlight>

L'output generato sarà "YesNo" poiché, usando la systemcall ''fork()'', abbiamo creato una nuova copia del processo (un processo figlio). Il processo padre, che ha eseguito con successo la fork(), stamperà "Yes" mentre il figlio stamperà "No".

'''thread'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++) sum = sum + 1;
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

Prima di discutere l'output generato dall'esecuzione di questo codice, è opportuno introdurre, brevemente, gli strumenti utilizzati.

----
'''Pthread (POSIX thread)'''

Citazione dal Silberschatz, Galvin, Gagne:
''Pthread si riferisce allo standard POSIX (IEEE 1003.1c) che definisce una API per la creazione e sincronizzazione dei thread.''

Le istruzioni fondamentali sono:
* '''int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);''' che crea un thread;
* '''int pthread_join(pthread_t thread, void **retval);''' che aspetta che un thread sia completato prima di continuare l'esecuzione.

Da ricordare che, per utilizzare pthread, va incluso l'header ''<pthread.h>'' e durante la compilazione va inclusa la libreria esterna tramite l'opzione ''-pthread''.
----

Torniamo all'output generato dall'esecuzione del secondo codice. 
Nel codice vengono generati cinque thread ed ognuno somma MAX (=1000000) volte 1 a sum. Ci aspettiamo un output di 5000000 ma, in realtà, viene stampato un valore molto minore. 

Questo accade principalmente per due motivi:
*sommare una costante ad una variabile non è un'operazione atomica (richiede almeno tre istruzioni assembler: due mov ed una sum).
*l'interval timer può fermare l'esecuzione del thread mentre sta effettuando una delle tre operazioni richieste per aggiungere uno a sum e provocare un risultato errato.

Questo è uno dei possibili problemi della programmazione concorrente conosciuto come ''race condition''. 
Un sistema di processi multipli presenta una '''race condition''' qualora il risultato finale dell'esecuzione dipenda dalla temporizzazione, o dall'ordine con cui i processi vengono eseguiti.

Per risolvere questo problema possiamo adoperare ancora una volta pthread.
Nello specifico, ci venogono offerte istruzione per realizzare una '''mutua esclusione''' sulle risorse condivise in modo che l'operazione che prima non era atomiche,ora, lo sia e non porti più ad una computazione errata. 
Codice di esempio: 
'''Mutex'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++){
pthread_mutex_lock(&mutex);
sum = sum + 1;
pthread_mutex_unlock(&mutex);
}
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

----
'''MUTEX'''

Un mutex è un dispositivo di MUTual EXclusion (mutua esclusione), ed è utile per proteggere le strutture dati condivise da modifiche concorrenti, implementare sezioni critiche e monitor.

Un mutex ha due possibili stati: sbloccato (non posseduto da nessun thread) e bloccato (posseduto da un thread). Un mutex non può mai essere posseduto da due thread contemporaneamente. Se un thread provasse ad acquisire il mutex, mentre quest'ultimo è già in possesso di un altro thread, dovrebbe aspettare finché non viene rilasciato.
La variabile che realizza il mutex, di tipo ''pthread_mutex_t'', viene inizializzata staticamente assegnandogli PTHREAD_MUTEX_INITIALIZER.
'''pthread_mutex_lock''' acquisisce immediatamente il mutex, se libero. Altrimenti aspetta fino a trovarla, prima o poi, libera. 
'''pthread_mutex_unlock''' rilascia il mutex.

[da: https://sourceware.org/pthreads-win32/manual/pthread_mutex_init.html]
----

Con questa soluzione abbiamo raggiunto un risultato esatto pur avendo pagato in prestazioni: la computazione infatti è più lenta a causa del tempo richiesto dalla sincronizzazione tra i thread.

Consideriamo ora due scenari leggermente più complicati:
* nel primo abbiamo due processi, A e B, che devono accedere a due risorse, X e Y, contemporaneamente prima di poter terminare. Cosa succede se, mentre A acquisisce X, B acquisisce Y?
* nel secondo abbiamo tre processi, A, B e C, che devono accedere alla risorsa X. Che succede se A e B, essendo più veloci, occupano insistentemente la risorsa e non permettono a C di utilizzarla?

La prima condizione si chiama '''deadlock''', la seconda condizione si chiama '''starvation'''. Il deadlock (stallo) è un problema che non può scomparire autonomamente, mentre la starvation ("inedia") si può risolvere da sola. A tal proposito ci viene incontro l'assioma di '''finite progress''': "ogni processo che può avanzare, prima o poi lo farà".
 
In ogni caso, per parlare in maniera più approfondita di queste tematiche:
* avremo bisogno di un modello di riferimento
* avremo bisogno di paradigmi in grado di esprimere la concorrenza (alcuni paradigmi saranno rivolti alla concorrenza a memoria privata; altri al multithreading a risorse condivise)
* dovremo imparare a scrivere programmi
Nel nostro modello di riferimento l'assegnamento di costanti è un operazione atomica. Dagli esempi precedenti, infatti, si evince come ci sia bisogno di creare atomicità in sezioni critiche. Inoltre, il nostro modello dovrà rispettare le proprietà di safety e di liveness, ovvero:
* Tutti i processi danno la stessa risposta;
* Ogni processo corretto da come risposta una tra quelle proposte;
* Ogni processo prima o poi fornisce una risposta.

== Lezione del 6 ottobre 2017 ==
'''Il linguaggio C'''

Il linguaggio C nasce nei primi anni 70 grazie al lavoro di Dennis Ritchie con lo scopo di scrivere il
sistema operativo Unix. Quali sono le caratteristiche di C e cosa lo rende un linguaggio adatto per scrivere un sistema
operativo? Un linguaggio per scrivere un sistema operativo deve:
* essere indipendente dalla macchina su cui viene scritto
* dare la possibilità di lavorare direttamente con la memoria
* permette di andare a modificare i singoli bit in memoria
* essere semplice da usare
* essere massimamente produttivo
* essere veloce, efficiente
C presenta le caratteristiche dette sopra e alcune altre:
* in C, dal punto di vista sintattico, tutto è funzione. Si può vedere un programma in C come un insieme di funzioni. La funzione principale è il '''main'''. L'unica cosa che la distingue è il nome, a parte quello il main è una funzione come le altre. Prende due argomenti: argcount e argvalue, che contengono rispettivamente il numero degli argomenti e un array contenente gli argomenti stessi. L'interfaccia del main è tipicamente: <syntaxhighlight lang=C> int main(int argc, char *argv[]) </syntaxhighlight>
* il costrutto fondamentale è l'espressione. ''expression'' ; = ''instruction''
* sono previste istruzioni di struttura <syntaxhighlight lang=C>if, while, switch, etc.</syntaxhighlight>
* le variabili, per poter essere utilizzate, devono essere sempre definite
* il C è un linguaggio fortemente tipato, però con un certo numero di eccezioni: ad esempio, è possibile fare il casting esplicito di un puntatore void * in qualsiasi tipo, senza che il compilatore dia errori o warnings, con conseguente perdita di type safety
* C è un linguaggio "per adulti": non impone una struttura ordinata al codice, come ad esempio fa invece Python, ed è piena responsabilità del programmatore scrivere programmi ordinati/leggibili. Inoltre molte operazioni che in altri linguaggi non sarebbero permesse lo sono invece in C: anche in questo caso è responsabilità del programmatore fare corretto uso del linguaggio
* C è un linguaggio molto semplice. Come si sopperisce alle mancanze imposte da questa semplicità? Grazie alle librerie: in C tutte le funzionalità aggiuntive (non fornite dal linguaggio stesso, come l'allocazione di memoria, la stampa a schermo, la gestione di input e output) sono fornite dalle librerie
* C è anche sintatticamente semplice. Dove va a finire la complessità sintattica? Nel preprocessore: prima di essere compilato un programma in C passa attraverso un preprocessore, che produce codice in base alle direttive di preprocessione date nel codice stesso <syntaxhighlight lang=C>#ifdef VAR ... #endif, # e ## operator, __LINE__,etc</syntaxhighlight>
* in C vi sono fondamentalmente due tipi di dato: int e float. Tutti gli altri "tipi" di dato sono derivati da essi. Si hanno diversi modificatori, che vanno a modificare la quantità di memoria allocata per la variabile. Alcuni di questi sono <syntaxhighlight lang=C>long, short, char, etc</syntaxhighlight> Un dato di tipo long int ha, solitamente, la dimensione di una parola di memoria della macchina su cui è eseguito il programma. char alloca 8 bits. Se si prende una variabile di un certo tipo e lo si assegna ad una di tipo più ampio, il valore viene mantenuto. Viceversa quando si assegna una variabile di un tipo ad una di tipo meno ampio, una volta "superato il limite" si torna indietro ciclicamente al valore iniziale. Per queste situazioni il compilatore non dà né warnings né errors: sono perfettamente lecite in C
* in C si passa una varibile ad una funzione solo per valore; per passare "per riferimento" una variabile si passa per valore l'indirizzo della variabile
* in C si può fare uso di puntatori alla memoria. Dato un puntatore p, un'istruzione del tipo p+i va letta come: vai avanti di i posizioni della grandezza del tipo del puntatore ognuno. Un vettore in C non è altro che un puntatore che non può essere assegnato. Una scrittura del tipo array[i] è una abbreviazione di *(array + i). Non c'è controllo in C se vado oltre la memoria allocata per l'array. Perché? In Pascal, ad esempio, c'è un tale controllo. Il motivo per cui in C questo manca è che questo controllo genera ulteriore codice macchina. Dovendo C essere efficiente, non ci si può permettere un tale costo aggiuntivo. La responsabilità di non andare oltre è lasciata al programmatore

Esercizio svolto che prende in input due valori tramite i parametri del metodo '''main''', li converte da sequenze di caratteri ad interi, per poi stamparli utilizzando delle '''System Call'''. Lo scopo dell’esercizio è dimostrare come sia possibile utilizzare il linguaggio C senza l’utilizzo di librerie particolari (ad eccezione di quelle per le System Call).

<syntaxhighlight lang=C>
#define _GNU_SOURCE
#include <unistd.h>
#include <sys/syscall.h>

int _uatoi(char *s, int value){
if (*s == 0)
return value;
else if (*s >= '0' && *s <= '9'){
value = value * 10 + (*s - '0');
return _uatoi(s+1, value);
}
}

int uatoi(char *s){
return _uatoi(s, 0);
}

char *uitoa(int val, char *buf, int len){
int i;
for (len = len - 1; len >= 0 && val > 0; len--, val /= 10){
buf[len] = '0' + (val %10);
}

return buf + len + 1;
}

#define MAXOUTLEN 10
int main (int argc, char *argv[]) {
int tot = 0;
int i;
char buf[MAXOUTLEN];
char *result;
for (i = 1; i < argc; i++)
tot += uatoi(argv[i]);
result = uitoa(tot, buf, MAXOUTLEN);
syscall(__NR_write, 1, result, MAXOUTLEN - (result - buf));
syscall(__NR_write, 1, "\n", 1);
return tot;
}
</syntaxhighlight>

== Lezione del 10 ottobre 2017 ==
'''Programmazione concorrente: notazione e un primo problema'''

Esempio di possibile rappresentazione (che non useremo) di codice concorrente. 
'''''A'', ''B'', ''C'', ''D'', ''E''''' rappresentano porzioni di codice. 
'''''//''''' rappresenta esecuzione parallela

<syntaxhighlight lang='c'>
A
cobegin
B
//
C
//
D
coend
E
</syntaxhighlight>

Il codice sarà eseguito come: ''A'' -> ''BCD'' -> ''E''. ''E'' quindi verrà eseguito solo dopo la fine dell'esecuzione di ''BCD''.

Un esempio che si presta molto bene ad illustrare la programmazione concorrente è quello del '''merge sort''' concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
coend
merge (miscela) i risultati
</syntaxhighlight>

Versione errata del merge sort concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
//
merge (miscela) i risultati
coend
</syntaxhighlight>

Avendo un numero ''N'' di processi, vorremmo avere una notazione che ci permetta di definire una porzione di codice come atomica (la sezione critica). Come possiamo procedere? 
Teoricamente, vorremmo avere due funzioni, '''csenter()''' e '''csexit()''' che ci permettano di entrare e uscire dalla sezione critica del codice senza causare errori nella computazione. 
Quali sono le proprietà che queste funzioni debbono rispettare?
# Devono garantire la mutua esclusione (1 solo processo esegue la critical section alla volta). Contando ''n'' csenter() completate e ''m'' csexit() completate la differenza deve essere <=1
# Non devono fare deadlock tra di loro
# Non devono fare starvation tra loro
# ''(no unnecessary delay)'' un processo che non sta usando la critical section {csenter()..csexit()} non deve bloccare un altro processo dall'entrarvi.

La soluzione a questo problema è nota come '''soluzione di Dekker''' (scritta e pubblicata da Dijkstra) che venne presentata in modo graduale attraverso l'utilizzo di quattro possibili, ma sbagliate, soluzioni.

Vorremmo avere programmi che abbiano la seguente struttura:

<syntaxhighlight lang='c'>
process[i], i=1,...,N

while(1):
csenter() //entrata nella sezione critica (critical section)
critical code
csexit() //uscita dalla sezione critica
non-critical code
</syntaxhighlight>

Ad esempio, tornando al problema dei thread che sommavano 1 a ''sum'' MAX volte, avremo:
<syntaxhighlight lang='c'>
process A:

for (i = 0; i < MAX; i++)
csenter()
sum += 1 //atomicità descritta da csenter(), csexit()
// < sum += 1 > atomicità lasciata al processore
csexit()

process B:

for (i = 0; i < MAX; i++)
csenter()
sum += 1
csexit()
</syntaxhighlight>
 
----
'''Soluzione 1: A turni'''

Qual è il problema? 
*'''mutex''' OK 
*'''deadlock''' OK 
*'''starvation''' OK 
*'''no unnecessary delay''' NO 
:: Perché se P ha bisogno spesso della critical section, P non deve aspettare che Q chieda la critical section e, all'uscita, lo autorizzi di nuovo ad usarla impostando ''turn = P''. Se Q una volta richiesta la sezione non la usa ma si ferma, P non può richiederla ancora perché appartiene ancora a Q.

<syntaxhighlight lang='c'>

turn=P

process P:
while(1)
while (turn != P)
;
critical code
turn = Q
non-critical code

process Q:
while(1)
while (turn != Q)
critical code
turn = P
non-critical code
</syntaxhighlight>
----

'''Soluzione 2: con 2 variabili''', cerchiamo di risolvere il problema dei turni

Finché Q usa la sezione P aspetta, quando Q ha finito P prende la sezione critica e non ci sono ritardi indesiderati.

*'''starvation''' OK
*'''deadlock''' OK
*'''no unnecessary delay''' OK
*'''mutex''' NO
:: Possono essere entrambi come false, escono insieme nel while, tutti e due mettono a true ed entrano assieme nel while.

<syntaxhighlight lang='c'>

inP = false;
inQ = false;

process P:
while(1)
while (inQ)
;
inP = true
critical code
inP = false
non-critical code

process Q:
while(1)
while (inP)
;
inQ = true
critical code
inQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione 3: il problema di soluzione 2 è che i processi non sono al corrente dell'intenzione dell'altro di entrare''' nel while quindi si crea il problema.
*'''mutex''' OK
*'''deadlock''' NO (potrebbero entrambi richiedere, contemporaneamente, l'ingresso alla critical section)
*'''starvation''' OK
*'''non unnecessary delay''' OK

<syntaxhighlight lang='c'>
needP = false;
needQ = false;

process P:
while(1)
needP = true
while (needQ)
;
critical code
needP = false
non-critical code

process Q:
while(1)
needQ = true
while (needP)
;
critical code
needQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione 4''':

*'''mutex''' OK
*'''deadlock''' OK
*'''no unnecessary delay''' OK
*'''starvation''' NO
:: Perché può esistere il processo che prova sempre a chiedere nel momento sbagliato e non esegue mai.

<syntaxhighlight lang='c'>
inP = false;
inQ = false;

process P:
while(1)
inP = true
while (inQ){
inP = false;
delay
inP = true;
}
critical code
inP = false
non-critical code

process Q:
while(1)
inQ = true
while (inQ){
inQ = false;
delay
inQ = true;
}
critical code
inQ = false
non-critical code
</syntaxhighlight>
----

'''Soluzione finale''': 
Uniamo soluzione 1 (poco simmetrica) e soluzione 4 (troppo simmetrica) usando quello che ci serve (attraverso ''needP'' e ''needQ'') e, se dovessimo essere tutti e due contemporaneamente a voler entrare, usiamo i turni (''turn'') per entrare nella critical section (settando il need dell'altro processo a false).

*'''mutex''' OK
*'''deadlock''' OK
*'''starvation''' OK
*'''non unnecessary delay''' OK

<syntaxhighlight lang='c'>
needP = false;
needQ = false;
turn = P

process P:
while(1)
needP = true
while (needQ)
if (turn != P) {
needP = false;
while ( turn != P)
needP = true;
}
/*critical code*/
turn = Q
needP = false
/*non-critical code*/

process P:
while(1)
needQ = true
while (needP)
if (turn != Q) {
needQ = false;
while ( turn != Q)
needQ = true;
}
/*critical code*/
turn = P
needQ = false
/*non-critical code*/
</syntaxhighlight>

== Lezione del 13 ottobre 2017 ==
== Lezione del 17 ottobre 2017 ==
== Lezione del 20 ottobre 2017 ==
== Lezione del 24 ottobre 2017 ==
== Lezione del 27 ottobre 2017 ==
== Lezione del 31 ottobre 2017 ==
== Lezione del 3 novembre 2017 ==
== Lezione del 7 novembre 2017 ==
== Lezione del 10 novembre 2017 ==
== Lezione del 14 novembre 2017 ==
== Lezione del 17 novembre 2017 ==
== Lezione del 21 novembre 2017 ==
== Lezione del 24 novembre 2017 ==
== Lezione del 28 novembre 2017 ==
== Lezione del 1 dicembre 2017 ==
== Lezione del 5 dicembre 2017 ==
== Lezione del 12 dicembre 2017 ==
== Lezione del 15 dicembre 2017 ==

Lezioni Anno Accademico 2017/18 I semestre

2017-10-10T20:12:39Z

Matt: /* Lezione del 10 ottobre 2017 */

''scrivete qui idee, riassunti dei concetti espressi, commenti approfondimenti sulle lezioni.''

== Lezione del 26 settembre 2017 ==
'''Titolo della lezione: W⁴ H Y'''

* What:
* Who:
----
Noi studenti ed "entrambi" i professori.
 
* When:
----
Il corso ha durata annuale. Verrà svolto ogni martedì e venerdì dalle 15:30 alle 18:30.
* La lezione del martedì sarà dedicata alla programmazione concorrente;
* La lezione del venerdì sarà dedicata alla parte generale. Terminerà circa 15 minuti prima dell'orario stabilito.
 
* Where:
----
Sempre in Aula 1 Ercolani (E1): DISI, Scuole Ercolani, Mura Anteo Zamboni 2B.
 
* How:
----
Il corso si svolgerà tramite:
* Lezioni frontali in aula.
* Attività di laboratorio.
* Esercitazioni.

Inoltre, durante l'ultimo periodo di lezioni del secondo semestre, vi sarà un periodo di ripasso del programma tramite esercizi, in vista dell'esame.
Durante la lezione del 3/10 sono state indicate alcune propedeuticità del corso. tra cui: programmazione, algoritmi e architettura degli elaboratori in primis.
Importanti sono anche i corsi di Analisi matematica e Algebra e geometria. Per farla breve, il primo anno è propedeutico al secondo.
 
* Why:
----
* '''Fonti e strumenti del corso:''' wiki creata di gruppo, lezioni frontali e esercitazioni.
**Non esiste un vero e proprio testo consigliato. Tutte le informazioni sono date DURANTE il corso.
** Per domande specifiche scrivere su mailing list (so@cs.unibo.it);
** Per esercizi, appunti e programma svolto rivolgersi al wiki (so.v2.cs.unibo.it);
** Per live streaming (www.cs.unibo.it/~renzo/live/).
* '''Modalità di esame:''' esame scritto (diviso in due parti: una parte generale e una di programmazione concorrente) + progetto + orale (facoltativo), possibilità di dare solo lo scritto per ottenere un massimo di 18. La modalità per studenti in "difficoltà" è disponibile solo fino agli appelli autunnali.
** Si parlerà del progetto indicativamente a partire da Dicembre 2017.
** L'orale può essere sostenuto da chi vuole migliorare (peggiorare) il voto ottenuto, o da chi vuole ottenere la lode.
* '''Orario di ricevimento per il primo semestre (fino al 15/09/17):''' martedì alle 11:30.
* Università = docenti + studenti.
* Informatica = come generare informazione automatica.
* Hardware, Software, Elaborazione, Comunicazione, Memorizzazione, Digitale/Analogico.
La principale distinzione che facciamo tra '''dato''' e '''informazione''' è che il dato, da solo, è privo di significato. Se, tuttavia, viene interpretato in un particolare contesto allora può diventare informazione significativa per chi sta interpretando i dati.

Un '''algoritmo''' è una o più sequenze non ambigue di passi che, dato un problema, ci permette di risolverlo.

Il nostro algoritmo, scritto in un qualche linguaggio formale, diventa un '''programma''' (sostanzialmente un testo, un insieme di istruzioni).

Un linguaggio è un entità software, ed è definito come una quadrupla (alfabeto, sintassi, lessico, semantica) dove:
*l'''alfabeto'' è l'insieme di simboli che compone il linguaggio.
*il ''lessico'' si può vedere come una funzione che va dai simboli a un booleano e ci dice quali sono le frasi ben formate.
*la ''sintassi'' determina quali delle sequenze scritte sono effettivamente corrette.
*la ''semantica'' associa un significato alle parole ben formate.

== Lezione del 29 settembre 2017 ==
'''Cos'è un sistema operativo e un po' di storia'''

Un ''sistema operativo'' è un programma che gestisce i processi, le risorse e interfaccia le applicazioni con l'hardware dell'elaboratore.

In particolare, il sistema operativo (laddove esiste) è il primo processo ad essere attivato e resta in vita fino allo spegnimento del calcolatore o al sopraggiungere di un errore fatale per il sistema.

A cosa serve un sistema operativo?
Principalmente, ha i seguenti scopi:
# Facilitare l'utilizzo del sistema (senza S.O. sarebbe a carico del programmatore conoscere tutti i linguaggi con cui si comunica con l'architettura della macchina);
# Rendere affidabile, protetto e sicuro l'utilizzo del sistema (e.g. un processo potrebbe recar danno all'intero sistema se non controllato o gestito, potrebbe ignorare i permessi di visualizzazione di un file);
# Astrarre l'hardware (e.g. filesystem);
# Garantire l'efficienza (e.g. non tenere la CPU in idle adottando opportuni algoritmi di scheduling);
# Assicurare portabilità ;

Un approccio molto usato è il cosiddetto approccio a strati ("a livelli") in cui ogni strato utilizza i servizi forniti al livello inferiore e ne fornisce di nuovi a quello superiore.
Astraendo il nostro calcolatore possiamo piazzare al livello più basso l'hardware e, subito sopra, il sistema operativo. I due layer comunicano usando il linguaggio ISA (Instruction Set Architecture), nativo della CPU stessa, al quale si aggiungono quelli che permettono di comunicare con i vari controllori dei dispositivi come la scheda di rete, la stampante, etc. Sopra il livello del sistema operativo possiamo collocare quello delle librerie e, infine, quello degli applicativi.

* '''Systemcall''' = meccanismo usato da un processo per richiedere al SO una qualche funzionalità a livello kernel. Un esempio è la funzione printf() del linguaggio C (stampa a video) che utilizza la systemcall write() (una delle systemcall per la gestione dei dispositivi).
 
----
'''Storia dei sistemi operativi'''

Nella generazione '''zero''' (1800 ca.) possiamo includere Babbage con la sua macchina analitica e lady Ada Lovelace. [[File:290px-AnalyticalMachine Babbage London.jpg |200px|thumb|right|Macchina analitica di Babbage]]

Nella generazione '''uno''' vediamo la comparsa delle valvole con tutti i problemi connessi. Non c'erano utilizzatori delle macchine, le stesse persone che le costruivano erano anche programmatori e fruitori delle stesse.

Nella generazione '''due''' (fine anni '60) arriva il transistor. Quest'ultimo è molto più veloce e piccolo della valvola e, soprattutto, meno incline a guasti. Le macchine iniziano ad essere più economiche grazie alla possibilità di avere un'economia di scala e quindi accessibili al grande pubblico. Questo fa si che, in queste prime fasi, i costruttori non siano più gli unici utilizzatori. [[File:Transistors.jpg |300px|thumb|right|Diversi tipi di Transistor]]

----

A questo punto poiché, pur essendo diventata più accessibile, una macchina costava ancora molto, nasce l'esigenza di non lasciare mai un processore senza lavoro (al fine di massimizzare i ricavi) e di condividere i dati.
In questa fase, infatti, abbiamo sistemi operativi di tipo ''batch'' (che collezionano tutto l'input all'inizio per calcolare e restituire l'output) dove l'inserimento di programmi e dati veniva fatto tramite schede perforate e non c'era interazione. Dai sistemi batch nasce lo ''SPOOL'' (Simultaneous Peripheral Operations On-Line).

Si comincia a pensare di utilizzare i tempi di I/O per poter eseguire altri processi. Questo però solleva almeno due problematiche: da un lato serve un modo per sapere quando un input è davvero finito mentre, dall'altro, bisogna fare in modo che un processo che non richieda I/O non occupi la CPU per un tempo indefinito.
Per la prima problematica la soluzione è rappresentata dall'introduzione degli '''interrupt''', segnali elettrici inviati alla CPU alla fine di ogni input.
Per la seconda, invece, è stato introdotto il cosiddetto '''interval timer''' che non è altro che un dispositivo che invia interrupt dopo un determinato quanto di tempo assicurando che un processo non occupi per troppo tempo il processore.
Questo consente di realizzare sistemi time sharing (il cui più semplice algoritmo è il round-robin) dove un processo può essere in uno dei seguenti tre stati:
*'''READY''' pronto per essere eseguito ma, il processore è già occupato;
*'''RUNNING''' in esecuzione;
*'''WAIT''' in attesa di I/O.

[[File:Dds.png]]

Nella '''quarta''' generazione (anni '70 ca.) vediamo la nascita di molte innovazioni importanti. Si riesce a rimpicciolire di molto i processori facendoli divenire a tutti gli effetti micro-processori. Nei laboratori Bell nasce Unix, un sistema operativo rivoluzionario con time sharing e clonazione dei processi (un processo non viene mai creato dal nulla ma viene prima clonato da uno già esistente e poi, alla copia, viene fatto eseguire un programma). A causa di problemi di portabilità da PDP-9, macchina su cui Unix è nato, a PDP-11 nasce il linguaggio C e il suo compilatore (scritto anch'esso in C).
Mentre Apple I "porta" una nuova idea di pc per tutte le famiglie, nascono molte versioni di Unix.
Per impedire una deriva proprietaria in cui ogni produttore offriva tutto quello che offrivano gli altri ma con qualche feature in più, Richard Stallman fonda il progetto GNU (GNU's Not Unix) per il quale scrive tutta una serie di utilities come il famoso compilatore gcc.
A GNU, per essere operativo, manca però un kernel. Non volendo aspettare i tempi di sviluppo del kernel che Stallman aveva in mente, Linus Torlvalds scrive il kernel '''Linux''' da cui nasce il sistema operativo GNU/Linux.

Nei tempi più recenti nascono i processori multi-core.

== Lezione del 3 ottobre 2017 ==

'''Introduzione alla programmazione concorrente: processi, thread e librerie'''

In programmazione concorrente le nozioni apprese di "algoritmo", "programma" e "processo" devono essere aggiornate. Questo perché non vi è più un programma con un'unica sequenza esecutiva [o meglio, un unico filo (= thread) di esecuzione]. Appare ovvio come servino dei meccanismi per organizzare e sincronizzare tali fili esecutivi, in modo da evitare il verificarsi di eventi non desiderati.

Quando parliamo di ''sistema concorrente'', ci riferiamo ad un sistema in cui due o più "attori" sono eseguiti parallelamente. 

Questi attori possono essere '''processi''' o '''thread'''.
La differenza sostanziale tra queste due tipologie di attori riguarda la condivisione della memoria e dei dati su cui operano. 

Più processi possono eseguire lo stesso programma ma, ognuno di essi, ha i propri dati su cui operare e il suo stato di avanzamento. In particolare:
* un processo è un'entità, un attore che ha delle proprietà e delle risorse associate;
* in ogni istante, il processo può essere interrotto. 
Più thread che vengono eseguiti parallelamente, invece, condividono gli stessi dati su cui operare. 
Codici di esempio:

'''processi'''

<syntaxhighlight lang=C>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[]){
if(fork()) printf("Yes");
else printf("No");
}
</syntaxhighlight>

L'output generato sarà "YesNo" poiché, usando la systemcall ''fork()'', abbiamo creato una nuova copia del processo (un processo figlio). Il processo padre, che ha eseguito con successo la fork(), stamperà "Yes" mentre il figlio stamperà "No".

'''thread'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++) sum = sum + 1;
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

Prima di discutere l'output generato dall'esecuzione di questo codice, è opportuno introdurre, brevemente, gli strumenti utilizzati.

----
'''Pthread (POSIX thread)'''

Citazione dal Silberschatz, Galvin, Gagne:
''Pthread si riferisce allo standard POSIX (IEEE 1003.1c) che definisce una API per la creazione e sincronizzazione dei thread.''

Le istruzioni fondamentali sono:
* '''int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);''' che crea un thread;
* '''int pthread_join(pthread_t thread, void **retval);''' che aspetta che un thread sia completato prima di continuare l'esecuzione.

Da ricordare che, per utilizzare pthread, va incluso l'header ''<pthread.h>'' e durante la compilazione va inclusa la libreria esterna tramite l'opzione ''-pthread''.
----

Torniamo all'output generato dall'esecuzione del secondo codice. 
Nel codice vengono generati cinque thread ed ognuno somma MAX (=1000000) volte 1 a sum. Ci aspettiamo un output di 5000000 ma, in realtà, viene stampato un valore molto minore. 

Questo accade principalmente per due motivi:
*sommare una costante ad una variabile non è un'operazione atomica (richiede almeno tre istruzioni assembler: due mov ed una sum).
*l'interval timer può fermare l'esecuzione del thread mentre sta effettuando una delle tre operazioni richieste per aggiungere uno a sum e provocare un risultato errato.

Questo è uno dei possibili problemi della programmazione concorrente conosciuto come ''race condition''. 
Un sistema di processi multipli presenta una '''race condition''' qualora il risultato finale dell'esecuzione dipenda dalla temporizzazione, o dall'ordine con cui i processi vengono eseguiti.

Per risolvere questo problema possiamo adoperare ancora una volta pthread.
Nello specifico, ci venogono offerte istruzione per realizzare una '''mutua esclusione''' sulle risorse condivise in modo che l'operazione che prima non era atomiche,ora, lo sia e non porti più ad una computazione errata. 
Codice di esempio: 
'''Mutex'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++){
pthread_mutex_lock(&mutex);
sum = sum + 1;
pthread_mutex_unlock(&mutex);
}
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

----
'''MUTEX'''

Un mutex è un dispositivo di MUTual EXclusion (mutua esclusione), ed è utile per proteggere le strutture dati condivise da modifiche concorrenti, implementare sezioni critiche e monitor.

Un mutex ha due possibili stati: sbloccato (non posseduto da nessun thread) e bloccato (posseduto da un thread). Un mutex non può mai essere posseduto da due thread contemporaneamente. Se un thread provasse ad acquisire il mutex, mentre quest'ultimo è già in possesso di un altro thread, dovrebbe aspettare finché non viene rilasciato.
La variabile che realizza il mutex, di tipo ''pthread_mutex_t'', viene inizializzata staticamente assegnandogli PTHREAD_MUTEX_INITIALIZER.
'''pthread_mutex_lock''' acquisisce immediatamente il mutex, se libero. Altrimenti aspetta fino a trovarla, prima o poi, libera. 
'''pthread_mutex_unlock''' rilascia il mutex.

[da: https://sourceware.org/pthreads-win32/manual/pthread_mutex_init.html]
----

Con questa soluzione abbiamo raggiunto un risultato esatto pur avendo pagato in prestazioni: la computazione infatti è più lenta a causa del tempo richiesto dalla sincronizzazione tra i thread.

Consideriamo ora due scenari leggermente più complicati:
* nel primo abbiamo due processi, A e B, che devono accedere a due risorse, X e Y, contemporaneamente prima di poter terminare. Cosa succede se, mentre A acquisisce X, B acquisisce Y?
* nel secondo abbiamo tre processi, A, B e C, che devono accedere alla risorsa X. Che succede se A e B, essendo più veloci, occupano insistentemente la risorsa e non permettono a C di utilizzarla?

La prima condizione si chiama '''deadlock''', la seconda condizione si chiama '''starvation'''. Il deadlock (stallo) è un problema che non può scomparire autonomamente, mentre la starvation ("inedia") si può risolvere da sola. A tal proposito ci viene incontro l'assioma di '''finite progress''': "ogni processo che può avanzare, prima o poi lo farà".
 
In ogni caso, per parlare in maniera più approfondita di queste tematiche:
* avremo bisogno di un modello di riferimento
* avremo bisogno di paradigmi in grado di esprimere la concorrenza (alcuni paradigmi saranno rivolti alla concorrenza a memoria privata; altri al multithreading a risorse condivise)
* dovremo imparare a scrivere programmi
Nel nostro modello di riferimento l'assegnamento di costanti è un operazione atomica. Dagli esempi precedenti, infatti, si evince come ci sia bisogno di creare atomicità in sezioni critiche. Inoltre, il nostro modello dovrà rispettare le proprietà di safety e di liveness, ovvero:
* Tutti i processi danno la stessa risposta;
* Ogni processo corretto da come risposta una tra quelle proposte;
* Ogni processo prima o poi fornisce una risposta.

== Lezione del 6 ottobre 2017 ==
'''Il linguaggio C'''

Il linguaggio C nasce nei primi anni 70 grazie al lavoro di Dennis Ritchie con lo scopo di scrivere il
sistema operativo Unix. Quali sono le caratteristiche di C e cosa lo rende un linguaggio adatto per scrivere un sistema
operativo? Un linguaggio per scrivere un sistema operativo deve:
* essere indipendente dalla macchina su cui viene scritto
* dare la possibilità di lavorare direttamente con la memoria
* permette di andare a modificare i singoli bit in memoria
* essere semplice da usare
* essere massimamente produttivo
* essere veloce, efficiente
C presenta le caratteristiche dette sopra e alcune altre:
* in C, dal punto di vista sintattico, tutto è funzione. Si può vedere un programma in C come un insieme di funzioni. La funzione principale è il '''main'''. L'unica cosa che la distingue è il nome, a parte quello il main è una funzione come le altre. Prende due argomenti: argcount e argvalue, che contengono rispettivamente il numero degli argomenti e un array contenente gli argomenti stessi. L'interfaccia del main è tipicamente: <syntaxhighlight lang=C> int main(int argc, char *argv[]) </syntaxhighlight>
* il costrutto fondamentale è l'espressione. ''expression'' ; = ''instruction''
* sono previste istruzioni di struttura <syntaxhighlight lang=C>if, while, switch, etc.</syntaxhighlight>
* le variabili, per poter essere utilizzate, devono essere sempre definite
* il C è un linguaggio fortemente tipato, però con un certo numero di eccezioni: ad esempio, è possibile fare il casting esplicito di un puntatore void * in qualsiasi tipo, senza che il compilatore dia errori o warnings, con conseguente perdita di type safety
* C è un linguaggio "per adulti": non impone una struttura ordinata al codice, come ad esempio fa invece Python, ed è piena responsabilità del programmatore scrivere programmi ordinati/leggibili. Inoltre molte operazioni che in altri linguaggi non sarebbero permesse lo sono invece in C: anche in questo caso è responsabilità del programmatore fare corretto uso del linguaggio
* C è un linguaggio molto semplice. Come si sopperisce alle mancanze imposte da questa semplicità? Grazie alle librerie: in C tutte le funzionalità aggiuntive (non fornite dal linguaggio stesso, come l'allocazione di memoria, la stampa a schermo, la gestione di input e output) sono fornite dalle librerie
* C è anche sintatticamente semplice. Dove va a finire la complessità sintattica? Nel preprocessore: prima di essere compilato un programma in C passa attraverso un preprocessore, che produce codice in base alle direttive di preprocessione date nel codice stesso <syntaxhighlight lang=C>#ifdef VAR ... #endif, # e ## operator, __LINE__,etc</syntaxhighlight>
* in C vi sono fondamentalmente due tipi di dato: int e float. Tutti gli altri "tipi" di dato sono derivati da essi. Si hanno diversi modificatori, che vanno a modificare la quantità di memoria allocata per la variabile. Alcuni di questi sono <syntaxhighlight lang=C>long, short, char, etc</syntaxhighlight> Un dato di tipo long int ha, solitamente, la dimensione di una parola di memoria della macchina su cui è eseguito il programma. char alloca 8 bits. Se si prende una variabile di un certo tipo e lo si assegna ad una di tipo più ampio, il valore viene mantenuto. Viceversa quando si assegna una variabile di un tipo ad una di tipo meno ampio, una volta "superato il limite" si torna indietro ciclicamente al valore iniziale. Per queste situazioni il compilatore non dà né warnings né errors: sono perfettamente lecite in C
* in C si passa una varibile ad una funzione solo per valore; per passare "per riferimento" una variabile si passa per valore l'indirizzo della variabile
* in C si può fare uso di puntatori alla memoria. Dato un puntatore p, un'istruzione del tipo p+i va letta come: vai avanti di i posizioni della grandezza del tipo del puntatore ognuno. Un vettore in C non è altro che un puntatore che non può essere assegnato. Una scrittura del tipo array[i] è una abbreviazione di *(array + i). Non c'è controllo in C se vado oltre la memoria allocata per l'array. Perché? In Pascal, ad esempio, c'è un tale controllo. Il motivo per cui in C questo manca è che questo controllo genera ulteriore codice macchina. Dovendo C essere efficiente, non ci si può permettere un tale costo aggiuntivo. La responsabilità di non andare oltre è lasciata al programmatore

Esercizio svolto che prende in input due valori tramite i parametri del metodo '''main''', li converte da sequenze di caratteri ad interi, per poi stamparli utilizzando delle '''System Call'''. Lo scopo dell’esercizio è dimostrare come sia possibile utilizzare il linguaggio C senza l’utilizzo di librerie particolari (ad eccezione di quelle per le System Call).

<syntaxhighlight lang=C>
#define _GNU_SOURCE
#include <unistd.h>
#include <sys/syscall.h>

int _uatoi(char *s, int value){
if (*s == 0)
return value;
else if (*s >= '0' && *s <= '9'){
value = value * 10 + (*s - '0');
return _uatoi(s+1, value);
}
}

int uatoi(char *s){
return _uatoi(s, 0);
}

char *uitoa(int val, char *buf, int len){
int i;
for (len = len - 1; len >= 0 && val > 0; len--, val /= 10){
buf[len] = '0' + (val %10);
}

return buf + len + 1;
}

#define MAXOUTLEN 10
int main (int argc, char *argv[]) {
int tot = 0;
int i;
char buf[MAXOUTLEN];
char *result;
for (i = 1; i < argc; i++)
tot += uatoi(argv[i]);
result = uitoa(tot, buf, MAXOUTLEN);
syscall(__NR_write, 1, result, MAXOUTLEN - (result - buf));
syscall(__NR_write, 1, "\n", 1);
return tot;
}
</syntaxhighlight>

== Lezione del 10 ottobre 2017 ==
'''Programmazione concorrente: notazione e un primo problema'''

Esempio di possibile rappresentazione (che non useremo) di codice concorrente. 
'''''A'', ''B'', ''C'', ''D'', ''E''''' rappresentano porzioni di codice. 
'''''//''''' rappresenta esecuzione parallela

<syntaxhighlight lang='c'>
A
cobegin
B
//
C
//
D
coend
E
</syntaxhighlight>

Il codice sarà eseguito come: ''A'' -> ''BCD'' -> ''E''. ''E'' quindi verrà eseguito solo dopo la fine dell'esecuzione di ''BCD''.

Un esempio che si presta molto bene ad illustrare la programmazione concorrente è quello del '''merge sort''' concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
coend
merge (miscela) i risultati
</syntaxhighlight>

Versione errata del merge sort concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
//
merge (miscela) i risultati
coend
</syntaxhighlight>

Avendo un numero ''N'' di processi, vorremmo avere una notazione che ci permetta di definire una porzione di codice come atomica (la sezione critica). Come possiamo procedere? 
Teoricamente, vorremmo avere due funzioni, '''csenter()''' e '''csexit()''' che ci permettano di entrare e uscire dalla sezione critica del codice senza causare errori nella computazione. 
Quali sono le proprietà che queste funzioni debbono rispettare?
# Devono garantire la mutua esclusione (1 solo processo esegue la critical section alla volta). Contando ''n'' csenter() completate e ''m'' csexit() completate la differenza deve essere <=1
# Non devono fare deadlock tra di loro
# Non devono fare starvation tra loro
# ''(no unnecessary delay)'' un processo che non sta usando la critical section {csenter()..csexit()} non deve bloccare un altro processo dall'entrarvi.

La soluzione a questo problema è nota come '''soluzione di Dekker''' (scritta e pubblicata da Dijkstra) che venne presentata in modo graduale attraverso l'utilizzo di quattro possibili, ma sbagliate, soluzioni.

Vorremmo avere programmi che abbiano la seguente struttura:

<syntaxhighlight lang='c'>
process[i], i=1,...,N

while(1):
csenter() //entrata nella sezione critica (critical section)
critical code
csexit() //uscita dalla sezione critica
non-critical code
</syntaxhighlight>

Ad esempio, tornando al problema dei thread che sommavano 1 a ''sum'' MAX volte, avremo:
<syntaxhighlight lang='c'>
process A:

for (i = 0; i < MAX; i++)
csenter()
sum += 1 //atomicità descritta da csenter(), csexit()
// < sum += 1 > atomicità lasciata al processore
csexit()

process B:

for (i = 0; i < MAX; i++)
csenter()
sum += 1
csexit()
</syntaxhighlight>
 
----
'''Soluzione 1: A turni'''

Qual è il problema? 
*'''mutex''' OK 
*'''deadlock''' OK 
*'''starvation''' OK 
*'''no unnecessary delay''' NO 
:: Perché se P ha bisogno spesso della critical section, P non deve aspettare che Q chieda la critical section e, all'uscita, lo autorizzi di nuovo ad usarla impostando ''turn = P''. Se Q una volta richiesta la sezione non la usa ma si ferma, P non può richiederla ancora perché appartiene ancora a Q.

<syntaxhighlight lang='c'>

turn=P

process P:
while(1)
while (turn != P)
;
critical code
turn = Q
non-critical code

process Q:
while(1)
while (turn != Q)
critical code
turn = P
non-critical code
</syntaxhighlight>
 
----

/*Soluzione 2: Con 2 variabili, cerchiamo di risolvere il problema dei turni

finché Q usa la sezione P aspetta, quando Q ha finito P prende la sezione critica
non ci sono ritardi indesiderati

starvation OK
deadlock OK
no unnecessary delay OK
mutex NO possono essere entrambi come false, escono insieme nel while
tutti e due mettono a true ed entrano assieme nel while.
*/
inP = false;
inQ = false;

process P:
while(1)
while (inQ)
;
inP = true
critical code
inP = false
non-critical code

process Q:
while(1)
while (inP)
;
inQ = true
critical code
inQ = false
non-critical code

/*Soluzione 3: il problema di soluzione 2 è che i processi non sono al corrente
dell'intenzione altrui di entrare nel while quindi crea un problema.
mutex OK
deadlock NO (unisono entrambi richiedono "mia" loop)
starvation OK
non unnecessary delay OK
*/

needP = false;
needQ = false;

process P:
while(1)
needP = true
while (needQ)
;
critical code
needP = false
non-critical code

process Q:
while(1)
needQ = true
while (needP)
;
critical code
needQ = false
non-critical code

/*Soluzione 4:

mutex OK
deadlock OK
non unnecessary delay OK
starvation NO perché può esistere il processo che prova sempre a
chiedere nel momento sbagliato e non esegue mai.
*/
inP = false;
inQ = false;

process P:
while(1)
inP = true
while (inQ){
inP = false;
delay
inP = true;
}
critical code
inP = false
non-critical code

process Q:
while(1)
inQ = true
while (inQ){
inQ = false;
delay
inQ = true;
}
critical code
inQ = false
non-critical code

/*Soluzione finale:
uniamo soluzione 1 (poco simmetrica) e soluzione 4 (troppo simmetrica)
usiamo quello che ci serve e se siamo troppi a voler entrare usiamo i turni
per entrare nella critical section il need opposto deve essere diventato falso

mutex OK
deadlock OK
starvation OK
non unnecessary delay OK
*/

needP = false;
needQ = false;
turn = P

process P:
while(1)
needP = true
while (needQ)
if (turn != P) {
needP = false;
while ( turn != P)
needP = true;
}
/*critical code*/
turn = Q
needP = false
/*non-critical code*/

process P:
while(1)
needQ = true
while (needP)
if (turn != Q) {
needQ = false;
while ( turn != Q)
needQ = true;
}
/*critical code*/
turn = P
needQ = false
/*non-critical code*/

</syntaxhighlight>

== Lezione del 13 ottobre 2017 ==
== Lezione del 17 ottobre 2017 ==
== Lezione del 20 ottobre 2017 ==
== Lezione del 24 ottobre 2017 ==
== Lezione del 27 ottobre 2017 ==
== Lezione del 31 ottobre 2017 ==
== Lezione del 3 novembre 2017 ==
== Lezione del 7 novembre 2017 ==
== Lezione del 10 novembre 2017 ==
== Lezione del 14 novembre 2017 ==
== Lezione del 17 novembre 2017 ==
== Lezione del 21 novembre 2017 ==
== Lezione del 24 novembre 2017 ==
== Lezione del 28 novembre 2017 ==
== Lezione del 1 dicembre 2017 ==
== Lezione del 5 dicembre 2017 ==
== Lezione del 12 dicembre 2017 ==
== Lezione del 15 dicembre 2017 ==

Lezioni Anno Accademico 2017/18 I semestre

2017-10-10T20:00:12Z

Matt: /* Lezione del 10 ottobre 2017 */

''scrivete qui idee, riassunti dei concetti espressi, commenti approfondimenti sulle lezioni.''

== Lezione del 26 settembre 2017 ==
'''Titolo della lezione: W⁴ H Y'''

* What:
* Who:
----
Noi studenti ed "entrambi" i professori.
 
* When:
----
Il corso ha durata annuale. Verrà svolto ogni martedì e venerdì dalle 15:30 alle 18:30.
* La lezione del martedì sarà dedicata alla programmazione concorrente;
* La lezione del venerdì sarà dedicata alla parte generale. Terminerà circa 15 minuti prima dell'orario stabilito.
 
* Where:
----
Sempre in Aula 1 Ercolani (E1): DISI, Scuole Ercolani, Mura Anteo Zamboni 2B.
 
* How:
----
Il corso si svolgerà tramite:
* Lezioni frontali in aula.
* Attività di laboratorio.
* Esercitazioni.

Inoltre, durante l'ultimo periodo di lezioni del secondo semestre, vi sarà un periodo di ripasso del programma tramite esercizi, in vista dell'esame.
Durante la lezione del 3/10 sono state indicate alcune propedeuticità del corso. tra cui: programmazione, algoritmi e architettura degli elaboratori in primis.
Importanti sono anche i corsi di Analisi matematica e Algebra e geometria. Per farla breve, il primo anno è propedeutico al secondo.
 
* Why:
----
* '''Fonti e strumenti del corso:''' wiki creata di gruppo, lezioni frontali e esercitazioni.
**Non esiste un vero e proprio testo consigliato. Tutte le informazioni sono date DURANTE il corso.
** Per domande specifiche scrivere su mailing list (so@cs.unibo.it);
** Per esercizi, appunti e programma svolto rivolgersi al wiki (so.v2.cs.unibo.it);
** Per live streaming (www.cs.unibo.it/~renzo/live/).
* '''Modalità di esame:''' esame scritto (diviso in due parti: una parte generale e una di programmazione concorrente) + progetto + orale (facoltativo), possibilità di dare solo lo scritto per ottenere un massimo di 18. La modalità per studenti in "difficoltà" è disponibile solo fino agli appelli autunnali.
** Si parlerà del progetto indicativamente a partire da Dicembre 2017.
** L'orale può essere sostenuto da chi vuole migliorare (peggiorare) il voto ottenuto, o da chi vuole ottenere la lode.
* '''Orario di ricevimento per il primo semestre (fino al 15/09/17):''' martedì alle 11:30.
* Università = docenti + studenti.
* Informatica = come generare informazione automatica.
* Hardware, Software, Elaborazione, Comunicazione, Memorizzazione, Digitale/Analogico.
La principale distinzione che facciamo tra '''dato''' e '''informazione''' è che il dato, da solo, è privo di significato. Se, tuttavia, viene interpretato in un particolare contesto allora può diventare informazione significativa per chi sta interpretando i dati.

Un '''algoritmo''' è una o più sequenze non ambigue di passi che, dato un problema, ci permette di risolverlo.

Il nostro algoritmo, scritto in un qualche linguaggio formale, diventa un '''programma''' (sostanzialmente un testo, un insieme di istruzioni).

Un linguaggio è un entità software, ed è definito come una quadrupla (alfabeto, sintassi, lessico, semantica) dove:
*l'''alfabeto'' è l'insieme di simboli che compone il linguaggio.
*il ''lessico'' si può vedere come una funzione che va dai simboli a un booleano e ci dice quali sono le frasi ben formate.
*la ''sintassi'' determina quali delle sequenze scritte sono effettivamente corrette.
*la ''semantica'' associa un significato alle parole ben formate.

== Lezione del 29 settembre 2017 ==
'''Cos'è un sistema operativo e un po' di storia'''

Un ''sistema operativo'' è un programma che gestisce i processi, le risorse e interfaccia le applicazioni con l'hardware dell'elaboratore.

In particolare, il sistema operativo (laddove esiste) è il primo processo ad essere attivato e resta in vita fino allo spegnimento del calcolatore o al sopraggiungere di un errore fatale per il sistema.

A cosa serve un sistema operativo?
Principalmente, ha i seguenti scopi:
# Facilitare l'utilizzo del sistema (senza S.O. sarebbe a carico del programmatore conoscere tutti i linguaggi con cui si comunica con l'architettura della macchina);
# Rendere affidabile, protetto e sicuro l'utilizzo del sistema (e.g. un processo potrebbe recar danno all'intero sistema se non controllato o gestito, potrebbe ignorare i permessi di visualizzazione di un file);
# Astrarre l'hardware (e.g. filesystem);
# Garantire l'efficienza (e.g. non tenere la CPU in idle adottando opportuni algoritmi di scheduling);
# Assicurare portabilità ;

Un approccio molto usato è il cosiddetto approccio a strati ("a livelli") in cui ogni strato utilizza i servizi forniti al livello inferiore e ne fornisce di nuovi a quello superiore.
Astraendo il nostro calcolatore possiamo piazzare al livello più basso l'hardware e, subito sopra, il sistema operativo. I due layer comunicano usando il linguaggio ISA (Instruction Set Architecture), nativo della CPU stessa, al quale si aggiungono quelli che permettono di comunicare con i vari controllori dei dispositivi come la scheda di rete, la stampante, etc. Sopra il livello del sistema operativo possiamo collocare quello delle librerie e, infine, quello degli applicativi.

* '''Systemcall''' = meccanismo usato da un processo per richiedere al SO una qualche funzionalità a livello kernel. Un esempio è la funzione printf() del linguaggio C (stampa a video) che utilizza la systemcall write() (una delle systemcall per la gestione dei dispositivi).
 
----
'''Storia dei sistemi operativi'''

Nella generazione '''zero''' (1800 ca.) possiamo includere Babbage con la sua macchina analitica e lady Ada Lovelace. [[File:290px-AnalyticalMachine Babbage London.jpg |200px|thumb|right|Macchina analitica di Babbage]]

Nella generazione '''uno''' vediamo la comparsa delle valvole con tutti i problemi connessi. Non c'erano utilizzatori delle macchine, le stesse persone che le costruivano erano anche programmatori e fruitori delle stesse.

Nella generazione '''due''' (fine anni '60) arriva il transistor. Quest'ultimo è molto più veloce e piccolo della valvola e, soprattutto, meno incline a guasti. Le macchine iniziano ad essere più economiche grazie alla possibilità di avere un'economia di scala e quindi accessibili al grande pubblico. Questo fa si che, in queste prime fasi, i costruttori non siano più gli unici utilizzatori. [[File:Transistors.jpg |300px|thumb|right|Diversi tipi di Transistor]]

----

A questo punto poiché, pur essendo diventata più accessibile, una macchina costava ancora molto, nasce l'esigenza di non lasciare mai un processore senza lavoro (al fine di massimizzare i ricavi) e di condividere i dati.
In questa fase, infatti, abbiamo sistemi operativi di tipo ''batch'' (che collezionano tutto l'input all'inizio per calcolare e restituire l'output) dove l'inserimento di programmi e dati veniva fatto tramite schede perforate e non c'era interazione. Dai sistemi batch nasce lo ''SPOOL'' (Simultaneous Peripheral Operations On-Line).

Si comincia a pensare di utilizzare i tempi di I/O per poter eseguire altri processi. Questo però solleva almeno due problematiche: da un lato serve un modo per sapere quando un input è davvero finito mentre, dall'altro, bisogna fare in modo che un processo che non richieda I/O non occupi la CPU per un tempo indefinito.
Per la prima problematica la soluzione è rappresentata dall'introduzione degli '''interrupt''', segnali elettrici inviati alla CPU alla fine di ogni input.
Per la seconda, invece, è stato introdotto il cosiddetto '''interval timer''' che non è altro che un dispositivo che invia interrupt dopo un determinato quanto di tempo assicurando che un processo non occupi per troppo tempo il processore.
Questo consente di realizzare sistemi time sharing (il cui più semplice algoritmo è il round-robin) dove un processo può essere in uno dei seguenti tre stati:
*'''READY''' pronto per essere eseguito ma, il processore è già occupato;
*'''RUNNING''' in esecuzione;
*'''WAIT''' in attesa di I/O.

[[File:Dds.png]]

Nella '''quarta''' generazione (anni '70 ca.) vediamo la nascita di molte innovazioni importanti. Si riesce a rimpicciolire di molto i processori facendoli divenire a tutti gli effetti micro-processori. Nei laboratori Bell nasce Unix, un sistema operativo rivoluzionario con time sharing e clonazione dei processi (un processo non viene mai creato dal nulla ma viene prima clonato da uno già esistente e poi, alla copia, viene fatto eseguire un programma). A causa di problemi di portabilità da PDP-9, macchina su cui Unix è nato, a PDP-11 nasce il linguaggio C e il suo compilatore (scritto anch'esso in C).
Mentre Apple I "porta" una nuova idea di pc per tutte le famiglie, nascono molte versioni di Unix.
Per impedire una deriva proprietaria in cui ogni produttore offriva tutto quello che offrivano gli altri ma con qualche feature in più, Richard Stallman fonda il progetto GNU (GNU's Not Unix) per il quale scrive tutta una serie di utilities come il famoso compilatore gcc.
A GNU, per essere operativo, manca però un kernel. Non volendo aspettare i tempi di sviluppo del kernel che Stallman aveva in mente, Linus Torlvalds scrive il kernel '''Linux''' da cui nasce il sistema operativo GNU/Linux.

Nei tempi più recenti nascono i processori multi-core.

== Lezione del 3 ottobre 2017 ==

'''Introduzione alla programmazione concorrente: processi, thread e librerie'''

In programmazione concorrente le nozioni apprese di "algoritmo", "programma" e "processo" devono essere aggiornate. Questo perché non vi è più un programma con un'unica sequenza esecutiva [o meglio, un unico filo (= thread) di esecuzione]. Appare ovvio come servino dei meccanismi per organizzare e sincronizzare tali fili esecutivi, in modo da evitare il verificarsi di eventi non desiderati.

Quando parliamo di ''sistema concorrente'', ci riferiamo ad un sistema in cui due o più "attori" sono eseguiti parallelamente. 

Questi attori possono essere '''processi''' o '''thread'''.
La differenza sostanziale tra queste due tipologie di attori riguarda la condivisione della memoria e dei dati su cui operano. 

Più processi possono eseguire lo stesso programma ma, ognuno di essi, ha i propri dati su cui operare e il suo stato di avanzamento. In particolare:
* un processo è un'entità, un attore che ha delle proprietà e delle risorse associate;
* in ogni istante, il processo può essere interrotto. 
Più thread che vengono eseguiti parallelamente, invece, condividono gli stessi dati su cui operare. 
Codici di esempio:

'''processi'''

<syntaxhighlight lang=C>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[]){
if(fork()) printf("Yes");
else printf("No");
}
</syntaxhighlight>

L'output generato sarà "YesNo" poiché, usando la systemcall ''fork()'', abbiamo creato una nuova copia del processo (un processo figlio). Il processo padre, che ha eseguito con successo la fork(), stamperà "Yes" mentre il figlio stamperà "No".

'''thread'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++) sum = sum + 1;
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

Prima di discutere l'output generato dall'esecuzione di questo codice, è opportuno introdurre, brevemente, gli strumenti utilizzati.

----
'''Pthread (POSIX thread)'''

Citazione dal Silberschatz, Galvin, Gagne:
''Pthread si riferisce allo standard POSIX (IEEE 1003.1c) che definisce una API per la creazione e sincronizzazione dei thread.''

Le istruzioni fondamentali sono:
* '''int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);''' che crea un thread;
* '''int pthread_join(pthread_t thread, void **retval);''' che aspetta che un thread sia completato prima di continuare l'esecuzione.

Da ricordare che, per utilizzare pthread, va incluso l'header ''<pthread.h>'' e durante la compilazione va inclusa la libreria esterna tramite l'opzione ''-pthread''.
----

Torniamo all'output generato dall'esecuzione del secondo codice. 
Nel codice vengono generati cinque thread ed ognuno somma MAX (=1000000) volte 1 a sum. Ci aspettiamo un output di 5000000 ma, in realtà, viene stampato un valore molto minore. 

Questo accade principalmente per due motivi:
*sommare una costante ad una variabile non è un'operazione atomica (richiede almeno tre istruzioni assembler: due mov ed una sum).
*l'interval timer può fermare l'esecuzione del thread mentre sta effettuando una delle tre operazioni richieste per aggiungere uno a sum e provocare un risultato errato.

Questo è uno dei possibili problemi della programmazione concorrente conosciuto come ''race condition''. 
Un sistema di processi multipli presenta una '''race condition''' qualora il risultato finale dell'esecuzione dipenda dalla temporizzazione, o dall'ordine con cui i processi vengono eseguiti.

Per risolvere questo problema possiamo adoperare ancora una volta pthread.
Nello specifico, ci venogono offerte istruzione per realizzare una '''mutua esclusione''' sulle risorse condivise in modo che l'operazione che prima non era atomiche,ora, lo sia e non porti più ad una computazione errata. 
Codice di esempio: 
'''Mutex'''

<syntaxhighlight lang=C>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define NUM_THREADS 5
#define MAX 1000000

int sum;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void* perform_work(){
int i;

for(i = 0; i < MAX; i++){
pthread_mutex_lock(&mutex);
sum = sum + 1;
pthread_mutex_unlock(&mutex);
}
/* optionally: insert more useful stuff here */
return NULL;
}

int main( int argc, char** argv ){
pthread_t threads[NUM_THREADS];
int thread_args[NUM_THREADS];
int result_code;
unsigned index;

sum = 0;
// create all threads one by one
for(index = 0; index < NUM_THREADS; ++index ){
thread_args[index] = index;
printf("In main: creating thread %d\n", index);
result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
assert(!result_code);
}
// wait for each thread to complete
for(index = 0; index < NUM_THREADS; ++index ){
// block until thread 'index' completes
result_code = pthread_join(threads[index], NULL);
assert(!result_code);
printf("In main: thread %d has completed\n", index);
}

printf("In main: All threads completed successfully\n" );
printf("Result: %d\n", sum);
exit( EXIT_SUCCESS );
}
</syntaxhighlight>

----
'''MUTEX'''

Un mutex è un dispositivo di MUTual EXclusion (mutua esclusione), ed è utile per proteggere le strutture dati condivise da modifiche concorrenti, implementare sezioni critiche e monitor.

Un mutex ha due possibili stati: sbloccato (non posseduto da nessun thread) e bloccato (posseduto da un thread). Un mutex non può mai essere posseduto da due thread contemporaneamente. Se un thread provasse ad acquisire il mutex, mentre quest'ultimo è già in possesso di un altro thread, dovrebbe aspettare finché non viene rilasciato.
La variabile che realizza il mutex, di tipo ''pthread_mutex_t'', viene inizializzata staticamente assegnandogli PTHREAD_MUTEX_INITIALIZER.
'''pthread_mutex_lock''' acquisisce immediatamente il mutex, se libero. Altrimenti aspetta fino a trovarla, prima o poi, libera. 
'''pthread_mutex_unlock''' rilascia il mutex.

[da: https://sourceware.org/pthreads-win32/manual/pthread_mutex_init.html]
----

Con questa soluzione abbiamo raggiunto un risultato esatto pur avendo pagato in prestazioni: la computazione infatti è più lenta a causa del tempo richiesto dalla sincronizzazione tra i thread.

Consideriamo ora due scenari leggermente più complicati:
* nel primo abbiamo due processi, A e B, che devono accedere a due risorse, X e Y, contemporaneamente prima di poter terminare. Cosa succede se, mentre A acquisisce X, B acquisisce Y?
* nel secondo abbiamo tre processi, A, B e C, che devono accedere alla risorsa X. Che succede se A e B, essendo più veloci, occupano insistentemente la risorsa e non permettono a C di utilizzarla?

La prima condizione si chiama '''deadlock''', la seconda condizione si chiama '''starvation'''. Il deadlock (stallo) è un problema che non può scomparire autonomamente, mentre la starvation ("inedia") si può risolvere da sola. A tal proposito ci viene incontro l'assioma di '''finite progress''': "ogni processo che può avanzare, prima o poi lo farà".
 
In ogni caso, per parlare in maniera più approfondita di queste tematiche:
* avremo bisogno di un modello di riferimento
* avremo bisogno di paradigmi in grado di esprimere la concorrenza (alcuni paradigmi saranno rivolti alla concorrenza a memoria privata; altri al multithreading a risorse condivise)
* dovremo imparare a scrivere programmi
Nel nostro modello di riferimento l'assegnamento di costanti è un operazione atomica. Dagli esempi precedenti, infatti, si evince come ci sia bisogno di creare atomicità in sezioni critiche. Inoltre, il nostro modello dovrà rispettare le proprietà di safety e di liveness, ovvero:
* Tutti i processi danno la stessa risposta;
* Ogni processo corretto da come risposta una tra quelle proposte;
* Ogni processo prima o poi fornisce una risposta.

== Lezione del 6 ottobre 2017 ==
'''Il linguaggio C'''

Il linguaggio C nasce nei primi anni 70 grazie al lavoro di Dennis Ritchie con lo scopo di scrivere il
sistema operativo Unix. Quali sono le caratteristiche di C e cosa lo rende un linguaggio adatto per scrivere un sistema
operativo? Un linguaggio per scrivere un sistema operativo deve:
* essere indipendente dalla macchina su cui viene scritto
* dare la possibilità di lavorare direttamente con la memoria
* permette di andare a modificare i singoli bit in memoria
* essere semplice da usare
* essere massimamente produttivo
* essere veloce, efficiente
C presenta le caratteristiche dette sopra e alcune altre:
* in C, dal punto di vista sintattico, tutto è funzione. Si può vedere un programma in C come un insieme di funzioni. La funzione principale è il '''main'''. L'unica cosa che la distingue è il nome, a parte quello il main è una funzione come le altre. Prende due argomenti: argcount e argvalue, che contengono rispettivamente il numero degli argomenti e un array contenente gli argomenti stessi. L'interfaccia del main è tipicamente: <syntaxhighlight lang=C> int main(int argc, char *argv[]) </syntaxhighlight>
* il costrutto fondamentale è l'espressione. ''expression'' ; = ''instruction''
* sono previste istruzioni di struttura <syntaxhighlight lang=C>if, while, switch, etc.</syntaxhighlight>
* le variabili, per poter essere utilizzate, devono essere sempre definite
* il C è un linguaggio fortemente tipato, però con un certo numero di eccezioni: ad esempio, è possibile fare il casting esplicito di un puntatore void * in qualsiasi tipo, senza che il compilatore dia errori o warnings, con conseguente perdita di type safety
* C è un linguaggio "per adulti": non impone una struttura ordinata al codice, come ad esempio fa invece Python, ed è piena responsabilità del programmatore scrivere programmi ordinati/leggibili. Inoltre molte operazioni che in altri linguaggi non sarebbero permesse lo sono invece in C: anche in questo caso è responsabilità del programmatore fare corretto uso del linguaggio
* C è un linguaggio molto semplice. Come si sopperisce alle mancanze imposte da questa semplicità? Grazie alle librerie: in C tutte le funzionalità aggiuntive (non fornite dal linguaggio stesso, come l'allocazione di memoria, la stampa a schermo, la gestione di input e output) sono fornite dalle librerie
* C è anche sintatticamente semplice. Dove va a finire la complessità sintattica? Nel preprocessore: prima di essere compilato un programma in C passa attraverso un preprocessore, che produce codice in base alle direttive di preprocessione date nel codice stesso <syntaxhighlight lang=C>#ifdef VAR ... #endif, # e ## operator, __LINE__,etc</syntaxhighlight>
* in C vi sono fondamentalmente due tipi di dato: int e float. Tutti gli altri "tipi" di dato sono derivati da essi. Si hanno diversi modificatori, che vanno a modificare la quantità di memoria allocata per la variabile. Alcuni di questi sono <syntaxhighlight lang=C>long, short, char, etc</syntaxhighlight> Un dato di tipo long int ha, solitamente, la dimensione di una parola di memoria della macchina su cui è eseguito il programma. char alloca 8 bits. Se si prende una variabile di un certo tipo e lo si assegna ad una di tipo più ampio, il valore viene mantenuto. Viceversa quando si assegna una variabile di un tipo ad una di tipo meno ampio, una volta "superato il limite" si torna indietro ciclicamente al valore iniziale. Per queste situazioni il compilatore non dà né warnings né errors: sono perfettamente lecite in C
* in C si passa una varibile ad una funzione solo per valore; per passare "per riferimento" una variabile si passa per valore l'indirizzo della variabile
* in C si può fare uso di puntatori alla memoria. Dato un puntatore p, un'istruzione del tipo p+i va letta come: vai avanti di i posizioni della grandezza del tipo del puntatore ognuno. Un vettore in C non è altro che un puntatore che non può essere assegnato. Una scrittura del tipo array[i] è una abbreviazione di *(array + i). Non c'è controllo in C se vado oltre la memoria allocata per l'array. Perché? In Pascal, ad esempio, c'è un tale controllo. Il motivo per cui in C questo manca è che questo controllo genera ulteriore codice macchina. Dovendo C essere efficiente, non ci si può permettere un tale costo aggiuntivo. La responsabilità di non andare oltre è lasciata al programmatore

Esercizio svolto che prende in input due valori tramite i parametri del metodo '''main''', li converte da sequenze di caratteri ad interi, per poi stamparli utilizzando delle '''System Call'''. Lo scopo dell’esercizio è dimostrare come sia possibile utilizzare il linguaggio C senza l’utilizzo di librerie particolari (ad eccezione di quelle per le System Call).

<syntaxhighlight lang=C>
#define _GNU_SOURCE
#include <unistd.h>
#include <sys/syscall.h>

int _uatoi(char *s, int value){
if (*s == 0)
return value;
else if (*s >= '0' && *s <= '9'){
value = value * 10 + (*s - '0');
return _uatoi(s+1, value);
}
}

int uatoi(char *s){
return _uatoi(s, 0);
}

char *uitoa(int val, char *buf, int len){
int i;
for (len = len - 1; len >= 0 && val > 0; len--, val /= 10){
buf[len] = '0' + (val %10);
}

return buf + len + 1;
}

#define MAXOUTLEN 10
int main (int argc, char *argv[]) {
int tot = 0;
int i;
char buf[MAXOUTLEN];
char *result;
for (i = 1; i < argc; i++)
tot += uatoi(argv[i]);
result = uitoa(tot, buf, MAXOUTLEN);
syscall(__NR_write, 1, result, MAXOUTLEN - (result - buf));
syscall(__NR_write, 1, "\n", 1);
return tot;
}
</syntaxhighlight>

== Lezione del 10 ottobre 2017 ==
'''Programmazione concorrente: notazione e un primo problema'''

Esempio di possibile rappresentazione (che non useremo) di codice concorrente. 
'''''A'', ''B'', ''C'', ''D'', ''E''''' rappresentano porzioni di codice. 
'''''//''''' rappresenta esecuzione parallela

<syntaxhighlight lang='c'>
A
cobegin
B
//
C
//
D
coend
E
</syntaxhighlight>

Il codice sarà eseguito come: ''A'' -> ''BCD'' -> ''E''. ''E'' quindi verrà eseguito solo dopo la fine dell'esecuzione di ''BCD''.

Un esempio che si presta molto bene ad illustrare la programmazione concorrente è quello del '''merge sort''' concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
coend
merge (miscela) i risultati
</syntaxhighlight>

Versione errata del merge sort concorrente:
<syntaxhighlight lang='c'>
leggi vettore
cobegin
ordina la prima metà del vettore
//
ordina la seconda metà del vettore
//
merge (miscela) i risultati
coend
</syntaxhighlight>

Avendo un numero ''N'' di processi, vorremmo avere una notazione che ci permetta di definire una porzione di codice come atomica (la sezione critica). Come possiamo procedere? 
Teoricamente, vorremmo avere due funzioni, '''csenter()''' e '''csexit()''' che ci permettano di entrare e uscire dalla sezione critica del codice senza causare errori nella computazione. 
Quali sono le proprietà che queste funzioni debbono rispettare?
# Devono garantire la mutua esclusione (1 solo processo esegue la critical section alla volta). Contando ''n'' csenter() completate e ''m'' csexit() completate la differenza deve essere <=1
# Non devono fare deadlock tra di loro
# Non devono fare starvation tra loro
# ''(no unnecessary delay)'' un processo che non sta usando la critical section {csenter()..csexit()} non deve bloccare un altro processo dall'entrarvi.

La soluzione a questo problema è nota come '''soluzione di Dekker''' (scritta e pubblicata da Dijkstra) che venne presentata in modo graduale attraverso l'utilizzo di quattro possibili, ma sbagliate, soluzioni.

Vorremmo avere programmi che abbiano la seguente struttura:

<syntaxhighlight lang='c'>
process[i], i=1,...,N

while(1):
csenter() //entrata nella sezione critica (critical section)
critical code
csexit() //uscita dalla sezione critica
non-critical code
</syntaxhighlight>

Ad esempio, tornando al problema dei thread che sommavano 1 a ''sum'' MAX volte, avremo:
<syntaxhighlight lang='c'>
process A:

for (i = 0; i < MAX; i++)
csenter()
sum += 1 //atomicità descritta da csenter(), csexit()
// < sum += 1 > atomicità lasciata al processore
csexit()

process B:

for (i = 0; i < MAX; i++)
csenter()
sum += 1
csexit()
</syntaxhighlight>

<syntaxhighlight lang='c'>
/*Soluzione 1: A turni
Qual è il problema?
mutex OK
deadlock OK
starvation OK
no unnecessary delay NO perché se P ha bisogno di molte volte la critical
section, P non deve aspettare che Q chieda la critical section. Qui se Q una
volta richiesta la sezione non la usa ma si ferma, P non può richiederla ancora
perché appartiene a Q
*/
turn=P

process P:
while(1)
while (turn != P)
;
critical code
turn = Q
non-critical code

process Q:
while(1)
while (turn != Q)
critical code
turn = P
non-critical code

/*Soluzione 2: Con 2 variabili, cerchiamo di risolvere il problema dei turni

finché Q usa la sezione P aspetta, quando Q ha finito P prende la sezione critica
non ci sono ritardi indesiderati

starvation OK
deadlock OK
no unnecessary delay OK
mutex NO possono essere entrambi come false, escono insieme nel while
tutti e due mettono a true ed entrano assieme nel while.
*/
inP = false;
inQ = false;

process P:
while(1)
while (inQ)
;
inP = true
critical code
inP = false
non-critical code

process Q:
while(1)
while (inP)
;
inQ = true
critical code
inQ = false
non-critical code

/*Soluzione 3: il problema di soluzione 2 è che i processi non sono al corrente
dell'intenzione altrui di entrare nel while quindi crea un problema.
mutex OK
deadlock NO (unisono entrambi richiedono "mia" loop)
starvation OK
non unnecessary delay OK
*/

needP = false;
needQ = false;

process P:
while(1)
needP = true
while (needQ)
;
critical code
needP = false
non-critical code

process Q:
while(1)
needQ = true
while (needP)
;
critical code
needQ = false
non-critical code

/*Soluzione 4:

mutex OK
deadlock OK
non unnecessary delay OK
starvation NO perché può esistere il processo che prova sempre a
chiedere nel momento sbagliato e non esegue mai.
*/
inP = false;
inQ = false;

process P:
while(1)
inP = true
while (inQ){
inP = false;
delay
inP = true;
}
critical code
inP = false
non-critical code

process Q:
while(1)
inQ = true
while (inQ){
inQ = false;
delay
inQ = true;
}
critical code
inQ = false
non-critical code

/*Soluzione finale:
uniamo soluzione 1 (poco simmetrica) e soluzione 4 (troppo simmetrica)
usiamo quello che ci serve e se siamo troppi a voler entrare usiamo i turni
per entrare nella critical section il need opposto deve essere diventato falso

mutex OK
deadlock OK
starvation OK
non unnecessary delay OK
*/

needP = false;
needQ = false;
turn = P

process P:
while(1)
needP = true
while (needQ)
if (turn != P) {
needP = false;
while ( turn != P)
needP = true;
}
/*critical code*/
turn = Q
needP = false
/*non-critical code*/

process P:
while(1)
needQ = true
while (needP)
if (turn != Q) {
needQ = false;
while ( turn != Q)
needQ = true;
}
/*critical code*/
turn = P
needQ = false
/*non-critical code*/

</syntaxhighlight>

== Lezione del 13 ottobre 2017 ==
== Lezione del 17 ottobre 2017 ==
== Lezione del 20 ottobre 2017 ==
== Lezione del 24 ottobre 2017 ==
== Lezione del 27 ottobre 2017 ==
== Lezione del 31 ottobre 2017 ==
== Lezione del 3 novembre 2017 ==
== Lezione del 7 novembre 2017 ==
== Lezione del 10 novembre 2017 ==
== Lezione del 14 novembre 2017 ==
== Lezione del 17 novembre 2017 ==
== Lezione del 21 novembre 2017 ==
== Lezione del 24 novembre 2017 ==
== Lezione del 28 novembre 2017 ==
== Lezione del 1 dicembre 2017 ==
== Lezione del 5 dicembre 2017 ==
== Lezione del 12 dicembre 2017 ==
== Lezione del 15 dicembre 2017 ==

Lezioni Anno Accademico 2017/18 I semestre

2017-10-10T19:36:15Z

Matt: /* Lezione del 10 ottobre 2017 */

Lezioni Anno Accademico 2017/18 I semestre

2017-10-04T15:54:11Z