Sistemi Operativi - User contributions [en]

Prova pratica 2016.05.31

2017-05-13T18:40:03Z

Alexp: Aggiunte le soluzioni degli es1 e es2 della prova pratica del 2016.05.31.

[http://www.cs.unibo.it/~renzo/so/pratiche/2016.05.31.pdf Link al testo]

==Esercizio 1==
<source lang="text">
Scrivere un programma che preso come parametro a linea comando il path di una directory elenchi solamente I file
che hanno un nome che ha come suffisso un numero (es. Prova.10). I file devono essere ordinati in ordine
numerico.
Esempio se la directory
test contiene I file prova5, giovanni, aaa.1000, bb.2000, ccc.dd.500 l'output del programma deve essere:
ccc.dd.500
aaa.1000
bb.2000
(in quanto 500 numericamente e' minore di 1000, prova5 non si considera: manca il punto prima del numero).
</source>
=== Soluzione di Alexp ===
<source lang="c">
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <dirent.h>
#include <ctype.h>
#include <stdint.h>
#include <sys/stat.h>

/*
Assumes that filename contains a digit in the suffix
*/
uint64_t getSuffixNumber(const char* filename){
size_t len = strlen(filename)-1;
size_t pos = len;
uint64_t number = 0;
uint64_t decimal = 1;
//while there are digits to read
while(pos>=0 && isdigit(filename[pos])){
//number+=digit converted to int, multiplied by decimal position
number+=(filename[pos] - '0')*decimal;
decimal*=10;
pos--;
}
return number;
}

/*
Returns 1 if the given filename ends with a number, 0 otherwise
*/
int endsWithNumber(const char* filename){
size_t len = strlen(filename)-1;
size_t pos = len;
//stating from last character, go backwards until there are digits
while(pos>=0 && isdigit(filename[pos])) pos--;
//if the suffix is actually a number, preceeded by a '.'
if(pos>=0 && pos != len && filename[pos] == '.') return 1;
else return 0;
}

int sortbysuffix(const struct dirent **e1, const struct dirent **e2) {
const char *a = (*e1)->d_name;
const char *b = (*e2)->d_name;
uint64_t suffixA = getSuffixNumber(a);
uint64_t suffixB = getSuffixNumber(b);
//compare two suffixes
return suffixA < suffixB;
}

int filter(const struct dirent* ent){
//exclude "." and ".." and files not ending with a ".(number)+"
if(strcmp(ent->d_name,".") && strcmp(ent->d_name,"..") && endsWithNumber(ent->d_name)){
return 1;
}
else return 0;
}

void printFilenames(char* path){
struct dirent **namelist;
int n;
n = scandir(path, &namelist, filter, sortbysuffix);
if (n < 0)
perror("scandir");
else {
while (n--) {
printf("%s\n", namelist[n]->d_name);
free(namelist[n]);
}
free(namelist);
}
}

int isDirectory(const char *path) {
struct stat statbuf;
//if unable to get file status
if (stat(path, &statbuf) != 0) return 0;
//otherwise if we got the file status, check if it's a directory
return S_ISDIR(statbuf.st_mode);
}

int main(int argc, char* argv[]){
if(argc == 2 && isDirectory(argv[1])){
printFilenames(argv[1]);
}
else{
printf("Error, input a directory name.\n");
}
return 0;
}
</source>

==Esercizio 2==
<source lang="text">
Come nell'esercizio 1 occorre cercare in una directory (passata come parametro) I file che hanno come suffisso un
numero. Nell'esercizio 2 I file sono eseguibili e l numero indica il numero di millisecondi da attendere a partire dalla attivazione del programma prima di attivarli.
Nell'esempio dell'esercizio precedente occorre aspettare mezzo secondo e lanciare ccc.dd.500, poi a 1 secondo
dall'attivazione (cioe' dopo approssimativamente ulteriori 0.5 secondi) si lancia aaa.1000 e allo scadere del
secondo secondo bbb.2000.
I file eseguibili nella directory vengono eseguiti in background (non si attende la fine dell'esecuzione per
continuare). Quindi se due file hanno lo stesso prefisso numerico vengono eseguiti in modo concorrente.
</source>
=== Soluzione di Alexp ===
<source lang="c">
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <dirent.h>
#include <ctype.h>
#include <stdint.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include <unistd.h>

/*
Assumes that filename contains a digit in the suffix
*/
uint64_t getSuffixNumber(const char* filename){
size_t len = strlen(filename)-1;
size_t pos = len;
uint64_t number = 0;
uint64_t decimal = 1;
//while there are digits to read
while(pos>=0 && isdigit(filename[pos])){
//number+=digit converted to int, multiplied by decimal position
number+=(filename[pos] - '0')*decimal;
decimal*=10;
pos--;
}
return number;
}

int endsWithNumber(const char* filename){
size_t len = strlen(filename)-1;
size_t pos = len;
//stating from last character, go backwards until there are digits
while(pos>=0 && isdigit(filename[pos])) pos--;
//if the suffix is actually a number, preceeded by a '.'
if(pos>=0 && pos != len && filename[pos] == '.') return 1;
else return 0;
}

int sortbysuffix(const struct dirent **e1, const struct dirent **e2) {
const char *a = (*e1)->d_name;
const char *b = (*e2)->d_name;
uint64_t suffixA = getSuffixNumber(a);
uint64_t suffixB = getSuffixNumber(b);
//compare two suffixes
return suffixA < suffixB;
}

/*
Returns 1 if the file is an executable file, 0 otherwise
*/
int isExecutable(const char* path){
struct stat buf;
//if unable to get file status
if (stat(path, &buf) != 0) return 0;
//if the file is executable by user
if (buf.st_mode & S_IXUSR) return 1;
return 0;
}

int filter(const struct dirent* ent){
//exclude "." and ".." and files not ending with a ".(number)+"
if(strcmp(ent->d_name,".") && strcmp(ent->d_name,"..") && endsWithNumber(ent->d_name)){
return 1;
}
else return 0;
}

void runExecutables(char* path){
struct dirent **namelist;
int n;
//delay time in ms
uint64_t waitingMS;
char* fullpath;
//forked child's pid
pid_t pid;
//used to wait all the children
int status = 0;
n = scandir(path, &namelist, filter, sortbysuffix);
if (n < 0) perror("scandir");
else {
while (n--) {
waitingMS = getSuffixNumber(namelist[n]->d_name);
//get the full dirname+filename path
asprintf(&fullpath, "%s%s", path, namelist[n]->d_name);
if(isExecutable(fullpath)){
printf("Calling %s\n",fullpath);
if( pid != fork() ){
//child
//wait for the required time(in microseconds)
usleep(waitingMS*1000);
char *args[] = {fullpath,(char *)0};
printf("Starting%s\n", args[0]);
execvp(fullpath,args);
}
}
free(fullpath);
free(namelist[n]);
}
//wait till all the children terminate
while ((pid = wait(&status)) > 0);
free(namelist);
}
}

int isDirectory(const char *path) {
struct stat statbuf;
//if unable to get file status
if (stat(path, &statbuf) != 0) return 0;
//otherwise if we got the file status, check if it's a directory
return S_ISDIR(statbuf.st_mode);
}

int main(int argc, char* argv[]){
if(argc == 2 && isDirectory(argv[1])){
runExecutables(argv[1]);
}
else{
printf("Error, input a directory name.\n");
}
return 0;
}
</source>

Prove pratiche

2017-05-13T18:19:18Z

Alexp: Aggiunto link alla prova pratica del 2016.05.31

''Qui troverete alcune prove teoriche pratiche (laboratorio), in modo da poter discutere sull'elaborato''

''Le prove sono svolte da studenti e servono come base per la discussione. Le soluzioni possono essere errate''

[[Prova pratica 2017.01.17]]

[[Prova pratica 2016.05.31]]

[[Prova pratica 2015.05.20]]

[[Prova pratica 2015.01.21]]

[[Prova pratica 2014.09.25]]

[[Prova pratica 2014.07.17]]

[[Prova Pratica 2014.07.02]]

[[Prova Pratica 2014.06.17]]

[[Prova pratica 2014.05.29]]

[[Prova Pratica 2014.02.20]]

[[ProvaPratica 2014.01.23]]

[[ProvaPratica 2013.09.13]]

[[ProvaPratica 2013.07.18]]

[[ProvaPratica 2013.06.21]]

[[ProvaPratica 2013.05.29]]

[[ProvaPratica 2013.02.15]]

[[ProvaPratica 2013.01.25]]

[[ProvaPratica 2012.09.19]]

[[ProvaPratica 2012.07.17]]

[[ProvaPratica 2012.06.20]]

[[Prova Pratica 2012.05.30]]

[[ProvaPratica 2011.09.12]]

[[Prova Pratica 2011.06.22]]

[[ProvaPratica 2011.05.30]]

[[ProvaPratica 2011.01.19]]

[[ProvaPratica 2010.07.19]]

[[ProvaPratica_2010.07.12]]

[[ProvaPratica 2010.02.03]]

[[ProvaPratica 2009.09.23]]

[[ProvaPratica 2009.06.23]]

[[ProvaPratica 2009.02.12]]

[[ProvaPratica 2009.01.15]]

[[ProvaPratica 2005.02.10]]

[[Prova pratica 2002.01.24]]

Prova teorica 2014.07.16

2017-05-06T16:40:09Z

Alexp: /* Esercizio c.2 */

Testo: [http://www.cs.unibo.it/~renzo/so/compiti/2014.07.16.tot.pdf]

== Esercizio c.1 ==
===Soluzione di S.G===
<syntaxhighlight lang="C">
/*
* Esercizio c.1: scrivere il monitor mMbb che realizzi un meccanismo di un minmax bounded buffer.
* Dopo le prime MIN operazioni di scrittura, un minmax bounded buffer deve sempre avere almeno MIN elementi e mai piu' di MAX
* elementi (e' quindi limitato sia nell'ampiezza massima, sia nell'ampiezza minima).
* Le funzioni (procedure entry) read e write del minmax bounded buffer hanno gli stessi argomenti e valori di ritorno di quelle del
* producer/consumer o del bounded buffer ordinario.
*/
#define MIN
#define MAX
#define SIZE // con SIZE >= MAX

monitor mMbb{

generic_type bb[];
int front, rear, count;
condition R, W;

void mMbb(void){
bb = new generic_type[SIZE];
front = rear = count = 0;
}

procedure_entry generic_type read(){
while(count < MIN) // Controllo che il buffer abbia MIN elementi per poter leggere
R.wait();

generic_type ret = bb[rear];
count--;
rear = (rear + 1) % SIZE;
W.signal();
return ret;
}

procedure_entry write(generic_type c){
while(count >= MAX) // Controllo che il buffer non abbia MAX elementi per poter scrivere
W.wait();

bb[front] = c;
count++;
front = (front + 1) % SIZE;
R.signal();
}

}

</syntaxhighlight>
[[User:S.G|S.G]] ([[User talk:S.G|talk]]) 17:21, 2 December 2016 (CET)

Non è fifo. Perché? [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 07:43, 3 December 2016 (CET)

Nel caso in cui MIN vale 3 e arrivino tre processi lettori nel seguente ordine, L1, L2, L3, avremmo che la coda di R è la seguente:

R: L1, L2, L3

Ora arriva un processo scrittore S1, viene eseguito liberando un lettore (R.signal) cioè L1. A questo punto L1 riprende la sua esecuzione, riesegue il ciclo e rientra nello stato di attesa. Quindi ora la coda di R è la seguente:

R: L2, L3, L1

Si potrebbe risolvere il problema modificando le funzioni write e read nel seguente modo:

<syntaxhighlight lang="C">
procedure_entry generic_type read(){
if(count < MIN) // Controllo che il buffer abbia MIN elementi per poter leggere
R.wait();

generic_type ret = bb[rear];
count--;
rear = (rear + 1) % SIZE;
if(count < MAX)
W.signal();
return ret;
}

procedure_entry write(generic_type c){
if(count >= MAX) // Controllo che il buffer non abbia MAX elementi per poter scrivere
W.wait();

bb[front] = c;
count++;
front = (front + 1) % SIZE;
if(count > MIN)
R.signal();
}
</syntaxhighlight>
[[User:S.G|S.G]] ([[User talk:S.G|talk]]) 10:37, 3 December 2016 (CET)
===Soluzione di Stefano Zaniboni===
<source lang="c">
/*esercizio 1*/

monitor mMbb{
object[] buffer; //spazio di memorizzazione

final int MAXELEM; // numero massimo di elementi che ci possono essere nel buffer
final int MINELEM; //numero minimo di elementi --> numero di scritture minime

condition okW; // dove mi fermo se non posso scrivere
condition okR; // dove mi fermo se non posso leggere

int count; // elementi presenti nel buffer
int front; // contatore al elemento prodotto
int rear; // contatore al elemento consumato

mMbb(){
buffer = new Object[MAXELEM];
count = rear = front = 0;
}

procedure entry object read(){
if ((count < MINELEM)) //se il buffer e' pieno oppure non ci sono min elem chiamo la wait
okR.wait();
eltype val = buffer[rear]; // assegno al val l'elemento che ho letto e poi aggiorno rear
rear = ((rear + 1) % (MAXELEM -1 )); // aggiorno rear;
count--; // decremento count per dire che ho consumato un elemento
okW.signal(); // qui faccio signal sui produttori che adesso possono scrivere
return retval;
}
procedure entry void write(int val){
if (count == buffer.length) //se il buffer e' pieno mi fermo
okW.wait();
buffer[front] = val; //scrivo elemento
count++; //aggiorno i prodotti disponibili
front = ((front+1)%(MAXELEM - 1)); // aggiorno il contatore front a puntare nella prossima posizione

okR.signal();
}

}
</source>
== Esercizio c.2 ==
===Soluzione di S.G===
<syntaxhighlight lang="C">
/*
* Esercizio c.2: Facendo uso di semafori scrivere la funzione rendezvous che consenta ai processi di sincronizzarsi secondo le
* seguenti specifiche:
* – Ogni processo indica come parametro della funzione rendezvous con quanti altri processi vuole sincronizzarsi.
* – M processi che chiamano la rendezvous con parametro N rimangono bloccati se M<N.
* – Quando l'N-mo processo richiama la rendezvous specificando N come parametro, lui e gli N-1 sospesi devono proseguire
* nelle propria esecuzione
*/

struct S {
Semaphore sem;
int N; // parametro della funzione rendezvous con quanti altri processi vuole sincronizzarsi
int I; // Contatore dei processi che richiamano rendezvous con paramentro N
}

List<S> listS = new List[]; // Lista di possibili semafori

Semaphore mutex = new Semaphore(1); // Variabile che consente la mutua esclusione

rendevouz(int n){
mutex.P(); // Ottengo la mutua esclusione

find = FALSE;
for(s in listS){ // Cerco il semaforo nella lista
if(s.N == n){
find = TRUE;
break;
}
}
if(find == FALSE){ // se non è presente nella lista lo creo
struct S s;
s.sem = new semaphore(0);
s.N = n;
s.I = 0;
listS.insert(s);
}

s.I++;
if(s.I == s.N){ // Quando l'N-mo processo richiama la rendezvous specificando N come parametro
while(s.I--) // lui e gli N-1 sospesi devono proseguire nelle propria esecuzione
s.sem.V();
}
else if(s.I < s.N){ // M processi che chiamano la rendezvous con parametro N rimangono bloccati se M<N
s.sem.P();
}

mutex.V(); // Rilascio la mutua esclusione
}
</syntaxhighlight>
Ho qualche dubbio su questa soluzione, riguardo la linea presente l'istruzione s.sem.P(), il processo viene immediatamente bloccato? Se si dovrei rilasciare la mutua esclusione prima quindi? [[User:S.G|S.G]] ([[User talk:S.G|talk]]) 16:43, 3 December 2016 (CET)

Si, la mutua esclusione va, in linea di principio, sempre rilasaciata prima di un' operazione P() poichè il processo che la chiama potrebbe bloccarsi tenendo con se la mutua esclusione e causando quindi deadlock.--[[User:FedericoP|FedericoP]] ([[User talk:FedericoP|talk]]) 10:37, 15 January 2017 (CET)
===Soluzione di MV===
<source lang="c">
// ------------------------- SOLUZIONE DI MV -------------------------

void rendezvous(int N)
{
struct S { Semaphore sem; int N; int M };

static List<struct S> L = new List<struct S>();
static Semaphore mutex = new Semaphore(1);

if(N <= 1) // se N==1 significa che non vuole sincronizzarsi
return; // se N<1 non ha senso => esce dalla funzione

bool trovato = false;
mutex.P(); // prende la mutua esclusione per evitare incoerenze
// scorre la lista in cerca di un semaforo per N
for(List<struct S> el = L.head(); !L.last(el) && !trovato; el = L.next(el) )
if(el.content.N == N) // se esiste
{
trovato = true;
if(el.content.M == N-1) // se è l'N-esimo processo
{
while(el.content.M) // sblocca tutti gli altri
{
el.content.sem.V();
el.content.M--;
}
mutex.V();
}
else // altrimenti si mette in attesa
{
el.content.M++;
mutex.V();
el.content.sem.P();
}
break;
}

if(!trovato) // se non esiste lo crea
{
// NB: ho ancora la mutua esclusione
struct S s;
s.N = N;
s.M = 1;
s.sem = new Semaphore(0);
L.insert_tail(S) // inserisce nella lista (in coda)

mutex.V():
// si mette in attesa sul semaforo appena creato (NB: N!=1)
L.tail().content.sem.P();
}
}

/* NOTA: gli elementi della lista non vengono deallocati una volta liberato
il semaforo; questo perchè è ancora possibile una race condition (rara)
nel caso in cui un processo P1 stia per inserirsi su un semaforo già esistente
(ha appena fatto mutex.V() ) e un altro P2 riesca ad entrare nel ciclo e
liberare tutti => P2 effettua una V in più e P1 esce subito dalla P
*/
</source>

===Soluzione di Alexp===
<source lang="c">
List<Queue<Semaphore>> waiting; //Lista di code di semafori
Semaphore mutex = 1; //Semaforo per modificare la lista delle code

void rendezvous(int N){
if(N >= 2){
//semaforo da accodare(e su cui si dovrà bloccare il thread nel caso waiting[N].size() < N)
Semaphore s = 0;
int i;
//entriamo nella critical section per modificare una struttura condivisa
mutex.P();
//se il chiamante non è l'N-esimo thread
if(waiting[N].size()+1 < N){
//accodiamo il semaforo nel caso non ci siano esattamente N thread con cui sincronizzarsi
waiting[N].enqueue(s);
//usciamo dalla critical section per non causare deadlock
mutex.V();
//fermiamo il thread sul semaforo accodato prima, nel caso in cui debba aspettare
//questo thread verrà risvegliato dall'N-esimo thread che si sincronizzerà
s.P();
}
//se il thread chiamante è proprio l'N-esimo(quindi dovrà sbloccare tutti)
else{
//per ogni thread accodato sulla coda in cui si sincronizzano N thread
/*
(in realtà nella coda ci sono N-1 semafori dei thread fermi
mentre il thread che entra in questo ramo else sarà l'N-esimo)
*/
for(i = 0; i < N-1; i++){
//togliamo dalla coda il semaforo e risvegliamo il thread che lo aspettava
waiting[N].dequeue().V();
}
//struttura condivisa modificata, usciamo dalla critical section
mutex.V();
}
}
}
</source>

Coding Contest 25 novembre 2016

2016-12-08T12:50:34Z

Alexp: /* Esercizio 3 */

== Esercizio 1 ==

scrivere un programma che passato come parametro il path di una directory (cwd se manca il paramtro) stampi il path relativo di tutti i file con nome palindromo presenti nel sottoalbero.

2720c84e673c75c20a27a07ffcd6826b31c8babc esercizio1.c [[User:Leonardo|Leonardo]] ([[User talk:Leonardo|talk]]) 17:23, 25 November 2016 (CET)

86aca4384a296bf12c69541fc5418fe4b6656e0d es1.c [[User:Fabio.capucci|Fabio.capucci]] ([[User talk:Fabio.capucci|talk]]) 17:30, 25 November 2016 (CET)

071fccfe63b8121f951444cb57001ccdd4ec02d0 Es1.c [[User:FilippoB|FilippoB]] ([[User talk:FilippoB|talk]]) 17:31, 25 November 2016 (CET)

235f2414cfe5b81973b1d388ce9431aa02b5f305 [[User:MatteoC|MatteoC]] ([[User talk:MatteoC|talk]]) 17:43, 25 November 2016 (CET)

168d3422b92fc78519e19d6a8e156b260a7798a6 testdir.c [[User:Tamino|Tamino]] ([[User talk:Tamino|talk]]) 18:06, 25 November 2016 (CET)

== Esercizio 2 ==

lancia tutti gli eseguibili della directory passata come primo paramtro e concatena gli output.
(i parametri rimanenti devono essere passati a tutti gli eseguibili)

<pre>
lanciatutti dir 1 2 3
</pre>

se nella directory ''dir'' sono presenti ''a'', ''b'' e ''c'' (eseguibili) lancia '''a 1 2 3''', '''b 1 2 3''', ''c 1 2 3'''

== Esercizio 3 ==

Scrivere un programma che deve ottenere il pid passato come parametro.
indicare se e' impossibile

fdf7b609e470c43a32a50801e76e78c32aebfbb1 main.tar.gz [[User:Alexp|Alexp]] ([[User talk:Alexp|talk]]) 17:22, 25 November 2016 (CET)

In seguito il codice dell'esercizio --[[User:Alexp|Alexp]] ([[User talk:Alexp|talk]]) 13:50, 8 December 2016 (CET) :
<syntaxhighlight lang=C>
#include <unistd.h>
#include <stdio.h>
#include <signal.h>
#include <errno.h>
#include <sys/wait.h>

#define PID 6300

void do_something(){
//print something
printf("---doing something---\n");
}

int main(int argc, char* argv[]) {
int sPID = PID;
if (argc > 1) {
sPID = atoi(argv[1]);
}
pid_t pid;
if (getpid() == sPID) {
//if sPID matched
printf("GOT PID (%d)!\n", sPID);
//do something
do_something();
} else {
if (kill(sPID, 0) != 0 && errno == ESRCH) {
//while generated child has wrong sPID
while ((pid = fork()) != sPID) {
//if child
if (pid == 0) {
if (getpid() == sPID) {
printf("GOT PID (%d)!\n", sPID);
//do something
do_something();
}
break;
}
//if parent and error occoured
else if (pid == -1) {
printf("Error: process table is full.\n");
break;
}
//if parent and no error occoured
else {
//wait for child process to finish
wait(NULL);
}
}
//we must wait for the last child
if (pid == sPID) {
printf("Waiting for the last child.");
wait(NULL);
}
} else {
printf("Impossible to get pid %d(another process has it).\n", sPID);
}
}
return 0;
}
</syntaxhighlight>

== Esercizio 4 ==

Trovare i file di contenuto uguale nella directory corrente e convertirli in link dello stesso file.

Esempio di soluzione dell'esercizio [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 09:06, 6 December 2016 (CET).
(in aula sembrava avere un bug ma non era vero. Alcuni file in /tmp non sono stati convertiti in link perché appartenevano ad altro utente).

<syntaxhighlight lang=C>
#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdarg.h>
#include <string.h>
#include <libgen.h>
#include <errno.h>
#include <dirent.h>
#include <mhash.h>
#include <sys/types.h>
#include <sys/stat.h>

struct file {
struct file *next;
unsigned char hash[20];
char *name;
};

struct file *head;

static int ckcontents(int fd1, int fd2) {
char buf1[BUFSIZ],buf2[BUFSIZ];
ssize_t n1, n2;
do {
n1 = read(fd1, buf1, BUFSIZ);
n2 = read(fd2, buf2, BUFSIZ);
} while (n1 == n2 && n1 > 0 && memcmp(buf1, buf2, n2 == 0));
return n1 == n2;
}

static int cksize(int fd1, int fd2) {
struct stat st1, st2;
return
fstat(fd1, &st1) == 0 &&
fstat(fd2, &st2) == 0 &&
st1.st_size == st2.st_size;
}

int filecmp(char *path1, char *path2) {
int fd1 = open(path1, O_RDONLY);
int fd2 = open(path2, O_RDONLY);
int rval =
fd1 >= 0 && fd2 >=0 && cksize(fd1, fd2) && ckcontents(fd1, fd2);
close(fd1);
close(fd2);
return rval;
}

#if 0
void printhash(unsigned char * hash) {
int i;
for (i = 0; i < mhash_get_block_size(MHASH_SHA1); i++)
printf("%.2x", hash[i]);
}
#endif

void compute_sha1sum(char *path, char *hash) {
int fd;
MHASH td;
if ((fd = open(path, O_RDONLY)) >= 0) {
if ((td = mhash_init(MHASH_SHA1)) != MHASH_FAILED) {
ssize_t n;
char buf[BUFSIZ];
while ((n = read(fd, buf, BUFSIZ)) > 0)
mhash(td, buf, n);
mhash_deinit(td, hash);
}
close(fd);
}
}

static void check_n_link(char *name) {
struct file **scan;
unsigned char hash[20];
compute_sha1sum(name, hash);
for (scan = &head; *scan != NULL; scan = &((*scan) -> next)) {
//printhash((*scan)->hash); printf(" - "); printhash(hash); printf("\n");
if (memcmp((*scan)->hash, hash, 20) == 0 &&
filecmp((*scan)->name, name)) {
unlink(name);
link((*scan)->name, name);
printf("%s and %s have the same contents\n", (*scan)->name, name);
return;
}
}
*scan = malloc(sizeof(struct file));
if (*scan) {
(*scan)->next = NULL;
memcpy((*scan)->hash, hash, 20);
(*scan)->name = name;
//printf("%s\n",name);
}
}

static void freefilelist() {
while (head) {
struct file *delenda;
delenda = head;
head = head->next;
free(delenda);
}
}

void err_exit(char *fmt, ...) {
va_list ap;

va_start(ap, fmt);
vfprintf(stderr, fmt, ap);
va_end(ap);
exit(2);
}

static int regular_only(const struct dirent *d) {
const char *name = d->d_name;
struct stat st;
return stat(name, &st) == 0 && S_ISREG(st.st_mode);
}

int main(int argc, char *argv[]) {
struct dirent **list;
int n;
int i;
n = scandir(".", &list, regular_only, alphasort);
if (n > 0) {
for (i=0; i<n; i++) {
char *name = list[i]->d_name;
check_n_link(name);
}
freefilelist();
for (i=0; i<n; i++)
free(list[i]);
free(list);
}
}

</syntaxhighlight>

Coding Contest

2016-11-25T16:22:28Z

Alexp: /* Esercizio 3 */

Questa pagina serve per la gare di programmazione in aula.

Io (a.k.a. il prof.) mettero' alcuni testi di esercizi.

Le squadre potranno scegliere l'esercizio/gli esercizi da svolgere.

Attenzione: la squadra che completa un esercizio '''non''' pubblica qui il codice ma mette solamente una hash sha1 del file contenente la soluzione (un singolo sorgente o un tile tar.gz/tgz comprendente la directory contenente tutti i file necessari) seguito da quattro caratteri tilde (~) che mediawiki traduce con il nome dell'autore e il timestamp.

Esempio:

725a6bc1afe1853a7990935a7c66894563ca086f /tmp/cadrop.tgz [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 13:13, 25 November 2016 (CET)

In fase di correzione il gruppo deve rendere disponibile (per esempio nella directory /public del cluster cs.unibo.it) un file corrispondente alla chiave sha1 pubblicata.

= Nov. 25, 2016 =

== Esercizio 1 ==

scrivere un programma che passato come parametro il path di una directory (cwd se manca il paramtro) stampi il path relativo di tutti i file con nome palindromo presenti nel sottoalbero.

== Esercizio 2 ==

lancia tutti gli eseguibili della directory passata come primo paramtro e concatena gli output.
(i parametri rimanenti devono essere passati a tutti gli eseguibili)

<pre>
lanciatutti dir 1 2 3
</pre>

se nella directory ''dir'' sono presenti ''a'', ''b'' e ''c'' (eseguibili) lancia '''a 1 2 3''', '''b 1 2 3''', ''c 1 2 3'''

== Esercizio 3 ==

Scrivere un programma che deve ottenere il pid passato come parametro.
indicare se e' impossibile

fdf7b609e470c43a32a50801e76e78c32aebfbb1 main.tar.gz [[User:Alexp|Alexp]] ([[User talk:Alexp|talk]]) 17:22, 25 November 2016 (CET)

== Esercizio 4 ==

Trovare i file di contenuto uguale nella directory corrente e convertirli in link dello stesso file.

Lezioni Anno Accademico 2016/17

2016-11-08T23:16:08Z

Alexp: terminated a sentence

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

== Lezione del 23 settembre 2016 ==

'''YY'''

* Presentazione del corso.
* Strumenti del corso: web, wiki.mailing list
* Indice dei contenuti
* Prove di esame (Scritto, Prova Pratica, Progetto).

* Hardware Software
* Informatica
* Informazione/Dato
* Rivoluzione digitale (secondo rinascimento, Terza rivoluzione Industriale).
* Software Libero

== Lezione del 27 settembre 2016 ==

'''OS:Y'''

* '''Organizzazione (martedi' vs. venerdi')'''
In genere la lezione del martedì sarà più teorica mentre quella del venerdì più orientata agli aspetti pratici di laboratorio. Questa suddivisione potrebbe cambiare in quanto qualche martedì verrà saltato.
* '''Università'''
Università = studenti + docenti
* '''Digitale/Analogico'''
Digit significa cifra. Nell'informatica è fondamentale il passaggio dal continuo al discreto.
* '''Binario/Decimale'''
Nei calcolatori l'informazione è memorizzata utilizzando il sistema binario ...
(''in quanto in passato i relè consentivano di avere due stati: " 1 e 0 "'': è impreciso, qualcuno sa dare una definizione migliore? [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 12:00, 29 September 2016 (CEST)) 
In quanto è molto semplice implementare le operazioni aritmetiche con dei circuiti elettronici utilizzando la codifica binaria. Per esempio è possibile creare un [https://it.wikipedia.org/wiki/Half-adder circuito] che somma due bit con riporto con solo due porte logiche. [[User:FedericoB|FedericoB]] ([[User talk:FedericoB|talk]]) 17:05, 29 September 2016 (CEST)
* '''I linguaggi e i problemi dell'Informatica'''
**Processing dell'informazione (Linguaggi di programmazione)
**Comunicazione (Il problema che i dati che mi servono sono in un altro luogo) (Linguaggi dei protocolli di rete, che però sono dei linguaggi temporizzati)
**Memorizzazione (Il problema che i dati mi serviranno in futuro) (Linguaggio del formato dei dati)
* '''Conoscenze a lungo, medio e breve termine nell'Informatica.'''
**BREVE: tecnologia, determinati programmi di sviluppo.
**MEDIO: singoli linguaggi, singoli OS, protocolli di comunicazione.
**LUNGO: algoritmi, informatica teorica, fondamenti costruttivi di reti e di OS.

* '''Cos'è una distribuzione'''
E' un antologia di applicazioni e librerie in modo che siano compatibili tra loro.

* '''Sistema Operativo: perché'''
Un sistema operativo è un programma che controlla l’esecuzione di programmi applicativi e agisce come interfaccia tra le applicazioni e l’hardware del calcolatore. 
E' uno strumento software complesso ed implementabile in diversi modi (monolitico, microkernel, etc.). I microcontroller non hanno OS.
Permette: contabilità delle risorse (consente a sua volta attività di benchmarking); continuità dei servizi; controllo errori
(programmi, dispositivi); multiuser (gli utenti hanno diversi diritti e proprietà sulle risorse); protezione delle attività dei
processi; astrazione file system.
* '''Struttura a livelli (layer)'''

---------------
---------------
---------------
OS
---------------L'
hw
---------------L

Consente di: separare la complessità, di avere portabilità.
Ogni livello rappresenta un cambio di linguaggio.
Più aggiungiamo livelli più aumenta il livello di astrazione.
* '''Programma/processo'''
Algoritmo: sequenza finita di istruzioni non ambigue, atta a risolvere un problema.

Programma: traduzione degli algoritmi in un linguaggio di programmazione.

Processo: istanza esecutiva di un programma. Il programma è testo statico, quando viene eseguito diviene processo. Possiamo avere
uno stesso programma in esecuzione su più processi (e.g apertura di più terminali che eseguono un editor di testo).

System call: richieste di processi al OS. e.g. printf (visto nel codice compilato in assembly tramite gcc -s), invoca write().
vi è una sequenza di azioni del tipo: richiesta di stampa al kernel --> attesa --> risposta.
* '''Storia dell'Informatica prima dei transistor'''

La storia dei calcolatori non ha un inizio preciso. Nel 1900 venne trovato sul relitto di una nave greca risalente al II secolo a.C un meccanismo in grado di calcolare i movimenti degli astri, si ipotizza con una sorprendente meccanica. Oggi questo sistema viene conosciuto come Macchina di Anticitera. Negli ultimi anni di ricerche archeologiche e storiche è venuta sempre più in superficie una vena pionieristica nel mondo classico per quanto riguarda lo studio sul calcolo automatizzato e addirittura di automi (si veda Erone di Alessandria). Ma facciamo un salto in avanti di qualche secolo... 
Già nel XVII secolo Pascal teorizza e mette in pratica uno strumento in grado di addizionare e sottrarre, e nel 1672 G.W. von Leibniz lo perfeziona con l'aggiunta della moltiplicazione e della divisione. Ma è solamente nei primi anni del 1800 che entra in scena la macchina analitica di Babbage. Estremamente complessa, la macchina era dotata di un sistema di input e di elaborazione dati e di un sistema di output. Ed è con Babbage che nascono le schede perforate. La macchina analitica venne presentata per la prima volta in Italia, durante un convegno torinese del 1840. Tra i vari collaboratori scientifici alla macchina è da annotare la presenza di Luigi Federico Menabrea, che tra le altre cose fu Ministro della Marina Militare, ingegnere e Presidente del Consiglio dei Ministri del Regno d'Italia (1867-1869). Il primo vero programmatore della storia, collaboratrice di Babbage, è Ada Lovelace (figlia del poeta Lord Byron!): progettò un algoritmo in grado di elaborare i numeri di Bernulli. 
Nel 1896 viene fondata la Tabulating Machine Company (futura IBM) e agli albori del '900, vari scienziati (trai quali Thomas Edison e Guglielmo Marconi) portarono avanti gli studi sulla valvola termoionica, elemento indispensabile dei primi calcolatori elettronici. La valvola incrementò vertiginosamente i tempi di calcolo ma l'estrema fragilità della stessa causò una serie di problematiche che si risolsero solamente con l'entrata in gioco del transistor.

== Lezione del 30 settembre 2016 ==

'''YC'''

(Storia dopo l'avvento del transistor)

Tre innovazioni indipendenti:
* Multitasking: Inizialmente ideato per mantenere la CPU occupata con altri processi mentre si faceva Input/Output. Permette di dare l'idea al utente di poter eseguire più processi contemporaneamente anche se questi in realtà sono eseguiti dalla cpu in modo intervallato. Ci sono certi computer che hanno più esecutori e quindi possono realmente eseguire multipli processi contemporaneamente.
* Supporto Multiuser
* Interattività:l'interazione con l'utente cambia il flusso del programma.

Queste tre proprietà sono ortogonali quindi possono esistere nei sistemi varie combinazioni di queste.

Iniziano anche a separarsi i ruoli tra programmatori e utenti.Prima i computer venivano utilizzati solo da chi creava programmi ora anche da chi li utilizza senza avere le conoscenze per crearli.

Il Time Sharing.

Sistemi Paralleli (SIMD/MIMD)
Sistemi Real Time

Dal 1969: UNIX.

Il linguaggio C e la portabilità dei sistemi operativi.
Caratteristiche del linguaggio C:
* grande controllo sul codice generato
* costrutti per l'elaborazione a basso livello
* supporto per la programmazione strutturata
* linguaggio "leggero": poche parole chiave, I/O gestito tramite librerie
* Il compilatore C è scritto in C.

Portabilità di un compilatore. I cross-compiler.

Il comando UNIX cc (o gcc): un comando unico per attivare l'intera toolchain per generare un eseguibile.

Il punto e virgola trasforma espressioni in istruzioni (terminatore).

1975? l'avvento dei personal computer. (in realtà il primo PC forse e' la Perrottina Olivetti del 1964).

Compiti a casa:
Portare esperimenti in C ritenuti "difficili".

[[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 10:41, 1 October 2016 (CEST)

== Lezione del 7 ottobre 2016 ==
Audio Lezione: [https://drive.google.com/open?id=0B8G3NNuJ7MA7TzJXUTJZM3RBUlE 7\10\16]
* '''Esempi di programmi in linguaggio C'''
Abbiamo commentato i programmi dal 1.1 al 1.7 che si possono trovare in questa [[2016-17_Programmi_C|pagina]].
* '''Economia Push/Economia Pull'''
Nell'economia push si basa la produzione sulla previsione di domanda e la si cerca di aumentare tramite la pubblicità. Questa è stata la principale metodologia utilizzata nei secoli scorsi.
Al giorno d'oggi si sta facendo avanti un differente approccio chiamato "economia pull" dove la produzione è basata sulla domanda effettiva. Per esempio per richiedere un finanziamento per l'economia push l'approccio comune è tramite una banca a cui si chiede un prestito in base alle previsioni di ricavo. Invece nell'economia pull è esemplare il fenomeno del crowdfounding dove si riceve un finanziamento dalla "folla" cioè da un gruppo di persone che dona una piccola parte di denaro ciascuna in base al reale interesse per il prodotto/servizio.
* '''Sistemi Operativi e parallelismo'''
Più processi si dicono in esecuzione concorrente quando accedono a risorse condivise.
Un programma è multithread quando tutti i thread condividono la stessa memoria. Ogni thread deve avere un suo stack.
La concorrenza si studia in particolare in sistemi operativi in quanto un sistema operativo multitasking è un sistema concorrente.
Concorrenza di processi in architetture SMP (Symmetric multiprocessor system) e non. (RD: non mi pare di aver spiegato cosa sia l'SMP) 
Simulazione del fenomeno della '''race condition'''. Si ha '''race condition''' quando un programma concorrente può puo' produrre diversi risultati se eseguito piu' volte per colpa della diversa evoluzione temporale delle elaborazioni. 
Per risolvere questo dovremmo raggruppare le istruzioni in ''sezioni critiche'' (sequenze inscindibili di istruzioni che devono essere eseguite come se fossero atomiche, tutta la sequenza o niente).
* '''Architettura a livelli e virtualizzazione'''
Dato un A e un A’ e riusciamo a usare A’ come A, allora A’ lo possiamo chiamare A virtuale.
L'idea che alla base delle macchine virtuali è di creare un interprete di un ISA differente o uguale a quello del sistema in modo da virtualizzare una reale macchina hardware e quindi poterla usare per gli stessi scopi di una macchina reale. E' quindi possibile, per esempio, installare sistemi operativi su hardware virtuale. 
L'insieme dei componenti hardware virtuali e il software installato su di questi prende il nome di ''macchina virtuale''.
Uno dei principali vantaggi, oggi molto utilizzato in ambito cloud, è quello di poter suddividere facilmente risorse hardware fisiche, per esempio spazio su disco e potenza di elaborazione, tra macchine virtuali differenti.
* '''Laboratorio di cross-compiling'''
Nel ultima parte della lezione abbiamo fatto un esperimento sulla portabilità dei compilatori. 
Abbiamo a disposizione un linguaggio ad alto livello che chiameremo L, due interpreti hw0 e hw1 per linguaggi a basso livello che chiameremo lhw0 e lhw1 e infine due compilatori L->lhw0 uno scritto in python e l'altro in L. 
Se compiliamo con il compilatore scritto in python (abbiamo un interprete python installato sulla macchina che stiamo utilizzando) il compilatore scritto in L otteniamo un compilatore scritto in lhw0 L->lhw0. 
Se ora modifichiamo il compilatore scritto in L L->lhw0 in modo che crei codice per hw1 (basta modificare gli indici numerici delle istruzioni) otteniamo un compilatore in L L->lhw1. Se lo compiliamo con il compilatore L->lhw0 otteniamo un ''cross-compiler'' scritto in lhw0 L->lhw1, cioè un compilatore che crea codice eseguibile su una macchina diversa da quella attuale. 
Se ora utilizziamo il cross compiler L->lhw1 per compilare il compilatore scritto in L L->hw1 otteniamo invece un compilatore che può essere eseguito su hw1. 
A questo punto su hw1 potremmo utilizzare l'ultimo compilatore creato per compilare sempre il compilatore scritto in L L->hw1 ma vedremo che otterremo sempre lo stesso file perché avremo raggiunto il limite.
 
Il materiale per poter replicare l'esperimento sulla portabilità dei compilatori è [http://www.cs.unibo.it/~renzo/so/tools/portability3.tgz qui].
[[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 13:42, 8 October 2016 (CEST)

== Lezione del 11 ottobre 2016 ==
*'''C'''
<syntaxhighlight lang=C>
#include <stdio.h>

void dump (void* f, size_t len){ //size_t is the sizeof() return type
unsigned char *s = f;
size_t i;
for (i = 0; i < len; i++)
printf("%02x",s[i]); //%02x means print at least 2 digits and add 0's if there are less
printf("\n");
}

int main(){

int v[] = {1, 2, 3, 4}; //v is (int*) 0x32ef...
v[2] = 42; //*((int*) 0x32ef) + 2 = 42, moves the address by 2 "positions", aka 4+4 bytes
v = 0x33;//(int*) 0x32ef.. = 0x33 (i.e.) 4 = 42

char s[] = "ciao";
int t[] = {0x63, 0x69, 0x61, 0x6f, 0x00}; //ciao in ASCII hex. if int OUT:'c'. if char OUT:"ciao"
char u[] = {99, 105,97, 111, 0 }; //ciao in ASCII dec. OUT:"ciao"

char *q = "ciao";
char *w = "mare";

printf("%s", s);
printf("%s", t);
printf("%s", u);

dump(s, sizeof(s));
dump(t, sizeof(t));
dump(q, sizeof(*q)); //*q size is 1B (it points to 1 char). OUT: 63('c')
dump(q, sizeof(q)); //q size is 8B. OUT: 5B of "ciao" + 3B of contiguous string "mare"
}
</syntaxhighlight>

OUTPUT:
<pre>
ciao
c
ciao
63 69 61 6f 00
63 00 00 00 69 00 00 00 61 00 00 00 6f 00 00 00 00 00 00 00 //int are 4B, char 1B, so we have empty bytes.
Little endian pattern is evident. %s allow to print untill the first null, so printf prints just 'c' with int declaration of t[]
63
63 69 61 6f 00 6d 61 72 // 6d = m, 61 = a, 72 = r.
</pre>

* '''Assioma di finite progress.'''
"Tutto è vero purchè ogni statement abbia durata sconosciuta, ma finita"
* '''Modalità di concorrenza.'''
1- Inconsapevolmente concorrenti: ogni processo elabora ciò per cui è stato creato. Il kernel si occupa di coordinazione e comunicazione.

2- Indirettamente concorrenti: processi che accedono a file condivisi.

3- Consapevolmente concorrenti: il programma ha diversi processi in esecuzione.
*''' Convenzioni usate nel corso (e negli esami) relative alle istruzioni atomiche'''
Le istruzioni atomiche vengono compiute in modo indivisibile, garantendo che l'azione non interferisca con altri processi durante la sua esecuzione.
Vengono rappresentate nel seguente modo:
<pre>
<istruzione atomica>
</pre>
Anche gli statement sono istruzioni atomiche(escluso il caso long long).
*''' Proprieta' di Safety e Liveness'''
-Safety: se il programma evolve, evolve bene(S)

"''Something good'' happens"

-Liveness: il programma va avanti(L)

"''Something eventually'' happens"

* '''Problema del consenso.'''
Il problema è così definito: ci sono n processi, ognuno propone un valore. Al termine tutti i processi devono accordarsi su di 1 dei valori proposti.Il suddetto problema è risolvibile se e solo se vengono rispettate le seguenti proprietà (2 di Safety + 1 di Liveness)

Proprietà:

S(1)- Tutti i processi devono ritornare lo stesso valore

S(2)- Ogni processo corretto decide uno tra i valori proposti

L(1)- Ogni processo corretto deve dare una risposta

w/o S(1): f(x) = x

w/o S(2): f(x) = 42

w/o L(1): f(x) = while(1)

*w/o = without

* '''Problemi delle elaborazioni concorrenti. Prima definizione (non formale) di Deadlock e Starvation'''
Introduzione alla notazione per la rappresentazione dei processi concorrenti

ESEMPIO 1.0

process p {
...
...
}

process q {
...
...
}

Due processi eseguiti in concorrenza.

...
cobegin
...
//
...
//
...
coend

cobegin e coend indicano la sezione di codice con le istruzioni (rappresentate da "..." e separate da "//")che verranno eseguite in concorrenza.

ESEMPIO 1.1 - Merge sort
cobegin
sort(v[1 : N])
//
sort(v[N : N])
//
merge(v[1 : N]), v[N : M])
coend

Se isoliamo le istruzioni senza considerare cobegin e coend, lo pseudocodice è corretto.
Se consideriamo anche cobegin e coend il programma esegue la funzione di merge() in concorrenza con le due chiamate a sort(), utilizzando risorse in comune e pertanto cercando di ordinare elementi non ancora ordinati nelle due metà dell'array.
Se spostiamo l'invocazione di merge al di fuori della sezione cobegin ... coend, lo pseudocodice (vedi in basso) è corretto.

cobegin
sort(v[1 : N])
//
sort(v[N : N])
coend
merge(v[1 : N]), v[N : M])

In particolare nella programmazione concorrente si devono affrontare due problemi che riguardano la liveness, parliamo di deadlock e starvation.

'''DEADLOCK''': uno o più processi non possono continuare l'esecuzione perchè ognuno di essi è in attesa che gli altri facciano qualcosa

ESEMPIO 1.2

process p {
while 1:
prendi a
prendi b
calcola f(a,b)
lascia a
lascia b
}

process q {
while 1:
prendi a
prendi b
calcola f(a,b)
lascia a
lascia b
}

Supponiamo di invertire l'ordine di prendi a e prendi b nel processo p. Dopo che entrambi i processi eseguono la prima istruzione lo scenario che si sviluppa è il seguente: al processo p serve la risorsa a, presa dal processo q, al quale servirebbe la risorsa b, presa dal processo p. I processi aspettano a vicenda che uno rilasci la risorsa che possiede l'altro. Risorsa necessaria ad entrambi i processi per eseguire l'istruzione (f(a,b)) che le richiederebbe entrambe. I processi sono deadlocked.

'''STARVATION''': quando un processo attende una risorsa indefinitamente, e questa non gli viene mai allocata

ESEMPIO 1.3
process p {
while 1:
prendi a
calcola f(a)
lascia a
}

process q {
while 1:
prendi a
calcola f(a)
lascia a
}

Supponiamo che i processi per realizzare "prendi a" verifichino la disponibilità di a tramite polling (provando ripetutamente se a è libero). Il processo q può essere sfortunato e non riuscire mai ad avere accesso ad a (tutte le volte che cerca di "prenderlo" lo troverà impegnato da p). Il processo q è in starvation.

ESEMPIO 1.4
"Supponiamo di avere tre processi (P1, P2, P3) i quali richiedono periodicamente accesso alla risorsa R. Consideriamo la situazione nella quale P1 è in possesso della risorsa, e sia P2 che P3 attendono per quella risorsa. Quando P1 esce dalla sua sezione critica, a P2 o P3 dovrebbe essere permesso l'accesso a R. Assumiamo che il SO garantisca l'accesso a P3 e che P1 richieda nuovamente la risorsa prima che P3 termini la sua sezione critica. Se il SO dovesse garantire l'accesso a P1 dopo che P3 abbia finito, e successivamente dovesse garantire alternativamente a P1 e P3 l'accesso alla risorsa, allora P2 potrebbe vedersi indefinitamente negato l'accesso alla risorsa, sebbene non vi sia una situazione di deadlock" (Stallings W.(2015). ''Operating System: internals and design principles''. (8th ed). Pearson)

'''Problema: posso creare sezioni critiche, tramite la programmazione, senza aiuti hardware?'''

ESEMPIO

process p
/*enter_cs*/
A = A + 1
/*exit_cs*/

process q
/*enter_cs*/
A = A - 1
/*exit_cs*/

'''Le 4 proprietà della critical section(CS)'''

SAFETY(1): una operazione all'interno della CS

ESEMPIO
process p
while 1:
/*enter_cs*/
A = A + 1
/*exit_cs*/
... <--- process q deve poter "entrare" qui

LIVENESS(1): no deadlock

LIVENESS(2): no starvation

LIVENESS(3): no useless wait

''Dekker(1st attempt) //KEY: turno''

turn = p //var globale condivisa

process p{
while (turn != p)
;
/*A = A + 1*/
turn = q
...
}

process q{
while(turn != q)
;
/*A = A - 1*/
turn = p
...
}

Non rispetta la proprietà di liveness(3), infatti uno dei due processi può dover attendere a lungo il suo turno eseguendo ciclicamente l'empty statement all'interno
del corpo del while. Questa situazione può verificarsi se l'altro processo fallisce dentro o fuori la sua CS (in questo caso l'attesa è infinita). Inoltre visto che i processi si alternano strettamente nell'utilizzo della loro critical section, il ritmo di esecuzione è dettato dal processo più lento dei due.

''Dekker(2nd attempt) //KEY: flag, ma senza turno''

inp = false

inq = false

process p{
while 1:
while(inq)
;
inp = true
/*A = A + 1*/
inp = false
...
}

process q{
while 1:
while(inp)
;
inq = true
/*A = A - 1*/
inq = false
...
}

In questo caso se uno dei processi fallisce fuori dalla CS (dopo aver settato il flag a false) l'altro processo non viene bloccato. Se invece un processo fallisce nella sua CS oppure dopo aver settato il flag a true allora l'altro processo resta bloccato indefinitamente. Non è garantita inoltre la mutua esclusione in quanto entrambi potrebbero essere al contempo nelle loro rispettive CS, ad esempio:

p valuta la condizione del while e trova inq a false

q valuta la condizione del while e trova inp a false

p assegna true a inp ed entra nella sua CS

q assegna true a inq ed entra nella sua CS

....entrambi sono nella rispettiva CS --> no liveness(1)

''Dekker(3nd attempt) //KEY: come 2nd ma con due istruzioni scambiate di ordine''

process p{
while 1:
inp = true
while(inq)
;
/*A = A + 1*/
inp = false
...
}

process q{
while 1:
inq = true
while(inp)
;
/*A = A - 1*/
inq = false
...
}

Scambiando l'ordine di due istruzioni vi è la mutua esclusione, tuttavia se entrambi i processi assegnano true al loro rispettivo flag, prima di valutare la condizione
del while, entrambi resteranno all'interno del while in attesa che l'altro processo "esca dalla CS" (non vi è mai entrato) --> deadlock

''Dekker(4nd attempt) //KEY: flag + delay''

process p{
while 1:
inp = true
while(inq){
inp = false; < delay >; inp = true;
}
/*A = A + 1*/
inp = false
...
}

process q{
while 1:
inq = true
while(inp){
inq = false; < delay >; inq = true;
}
/*A = A - 1*/
inq = false
...
}

In questo caso il settare il proprio flag a true è indice del desiderio di entrare nella propria CS. Vi è ancora mutua esclusione. Se però dovesse verificarsi una sequenza del tipo:

p imposta flag inp a true

q imposta falg inq a true

p valuta la condizione del while

q valuta la condizione del while

p imposta flag inp a false

q imposta flag inq a false

p imposta flag inp a true

q imposta flag inq a true

allora c'è la possibilità che si ripeta all'infinito (entrambi i processi potrebbero rimanere nel while). Essendo però una condizione che dipende dalla velocità relativa dei due processi, esiseranno delle situazioni nelle quali uno dei due processi potrà entrare, così come vi saranno delle situazioni nelle quali nessun processo avrà accesso alla propria CS --> livelock

'''Dekker...finally //KEY: flag + turni ("cambio delay con turno)'''

needp = false

needq = false

turn = p

process p{
while 1:
needp = true
while (needq) {
needp = false
while(turn == q)
;
needp = true
}
/*A = A + 1*/
needp = false
turn = q
...
}

process q{
while 1:
needq = true
while(needp) {
needq = false;
while(turn == p)
;
needq = true
}
/*A = A - 1*/
needq = false
turn = p
...
}

In questo caso il processo che vuole entrare nella sua CS ne manifesta il bisogno settando need a true. Se entrambi i processi entrano nel corpo del while il tie-break è espletato dal while la cui condizione è un turn che sarà uguale soltanto ad uno dei due processi (in questo caso turn è inizializzata a p), e dunque non si verificherànno situazioni di deadlock o livelock.
*'''Proprietà della sezione critica'''
Mutua esclusione 
Assenza di deadlock 
Assenza di starvation 
Assenza di delay non necessari

*'''La test&set'''
E' un istruzione atomica per impostare il valore di una variabile a 1 (lock) ma ritornare il vecchio valore. Questa istruzione può essere utilizzata per gestire sezioni critiche. 
Il valore ritornato dalla test and set viene comparato a 1, se è uguale si aspetta altrimenti si procede. 
In questo modo il primo processo che cercherà di entrare nella sezione critica ci riuscirà e imposterà il lock a 1, gli altri processi si troveranno il lock a 1 e dovranno aspettare. Quando il primo processo avrà finito ripristinerà il vecchio valore di lock e permetterà a uno degli altri processi di eseguire la test and set e di entrare nella sezione critica.
----
Altri argomenti trattati che non sono stati qui riportati in forma di appunti:
Gestione algoritmica della critical section.
Algoritmo di Dekker.
Gestione architetturale della critical section.

[[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 10:35, 17 October 2016 (CEST)

== Lezione del 14 ottobre 2016 ==
Audio Lezione: [https://drive.google.com/open?id=0B8G3NNuJ7MA7UlJadTRVbzhWRFE 14\10\16]
* Sistemi Operativi per elaboratori multiprocessore SMP/non SMP
* Macchine di von Neumann (e di Harvard).
* Il bus.
* Interrupt e Trap
* Gestione degli interrupt
* Mascheramento degli interrupt
* Interrupt Nidificati
* DMA
* Device a carattere e device a blocchi
* System call come trap.
* La gerarchia delle memorie
* cache

== Lezione del 18 ottobre 2016 ==
Audio Lezione: [https://drive.google.com/open?id=0B8G3NNuJ7MA7eVlFdWR0cUkxd2M 18/10/16]

Argomenti trattati:
*'''Implementazione in C della Test&Set, degli Algoritmi di Dekker e Peterson.'''
Codice sorgente disponibile [[Dekker,_Peterson_e_Test%26Set_in_C|qui]].
*'''Definizione di Semaforo.'''
Un semaforo è una variabile intera che può essere modificata solo da 2 operazioni atomiche: P(Proberen) e V(Verhogen). 
P aspetta che il valore sia minore o uguale a zero. Quando lo diventa decrementa il valore. 
S incrementa il valore. 
*'''Invariante del Semaforo.'''
Il numero di Proberen deve essere minore o uguale al numero di Verhogen più il valore d'inizializzazione del semaforo. 
In questo modo si può gestire per esempio l'allocazione di risorse. Il semaforo viene inizializzato al numero di risorse e ogni volta che un processo ha bisogno della risorsa esegue un proberen, quindi decrementa il valore se la risorsa è disponibile. Quando un processo rilascia la risorsa esegue un verhogen.
*'''Esempio: implementazione di sezione critica e di semplice sincronizzazione con semafori.'''

== Lezione del 21 ottobre 2016 ==
*'''Make'''
Make è un sistema per la compilazione intelligente dei programmi. 
Permette invece di compilare tutto il programma tutte le volte di compilarne solo una parte, solo quella che è stata modificata.
Per capirne il funzionamento è utile un parallelismo con le ricette di cucina. Si specificano dei target che sono gli obbiettivi della ricetta.Per fare una ricetta servono degli ingredienti e magari quegli ingredienti hanno a loro volta delle ricette. Make allo stesso modo definisce dei target che possono avere come dipendenze altri target. 
Nel installazione del programma il programma ./configure cerca nel sistema se le librerie da cui è dipendente il programma sono presenti. 
*'''Git'''
Git è un sistema di versioning, serve a tener traccia delle modifiche apportante a un progetto nel tempo. E' utile per collaborare a un progetto condiviso. 
Possibilità per ogni membro del repository di lavorare in maniera indipendente e poi aggiornare il progetto comune. 
Ce ne sono stati tanti di sistemi di versioning tipo SVN, Mercurial ma attualmente Git è il più utilizzato. 
Git non serve solo per scrivere programmi ma per esempio anche libri, in modo collaborativo. 
Git è completamente distribuito, non esiste in un repository una copia principale e delle copie secondarie ma ogni copia può essere principale. 
Per iniziare un repository git si utilizza il comando ''git init''. 
Per aggiungere un file al repository si utilizza il comando ''git add''. 
Ma ad ogni singola modifica git non aggiorna automaticamente il repository ma è l'utente che tramite il comando git commit indica che una certa versione del progetto deve essere salvata. 
Il comando ''git log'' serve a visualizzare la storia del repository. 
Il comando ''git diff'' serve a vedere la differenza tra ciò che è nel repository e le modifiche di cui non si è ancora fatto il commit. 
Dopo aver dato il comando add si dice che i file sono 'on stage' prima del commit. 
Il comando ''git checkout'' serve a spostarsi nella storia del repository. 
Il comando ''git clone'' serve a copiare un repository remoto. 
Il comando ''git push'' serve a inviare le modifiche al repository remoto mentre il comando ''git pull'' serve a ricevere le modifiche più aggiornate dal repository remoto. 
Il ''merge'' è il processo in cui uno degli utenti che crea un conflitto deve "a mano" scegliere quali parti dei due commit in conflitto vuole tenere. 
Git è utile per trovare i bug che non erano presenti in versioni precedenti del progetto. Si può tornare alla versione precedente stabile e avanzare nella storia fino a trovare una versione instabile. A questo punto è probabile che l'origine del bug sia nelle modifiche che hanno creato questa versione instabile. 
Github è una piattaforma di repository dove possono essere mantenuti dei progetti gratuitamente se sono con licenza libera. 
In una directory in cui è presente un repository git e sempre la presente la cartella ''.git'' dove il sistema di versioning mantiene il database della storia. 

== Lezione del 25 ottobre 2016 ==
Audio Lezione: [https://drive.google.com/open?id=0B8G3NNuJ7MA7WjZJMm11cjhuQXc 25/10/16]

Argomenti trattati:
* '''Semafori fair'''
Un semaforo è "fair" quando tende a non sbloccare dallo stato di attesa sempre lo stesso processo ma cerca di distribuire la possibilità di esecuzione a più processi.
* '''Problemi classici della concorrenza risolti con semafori'''
** '''Produttore/consumatore'''
::Due processi: produttore e consumatore. Il produttore genera continuamente dei valori e il consumatore continuamente li legge. Il consumatore deve leggere i valori nello stesso ordine in cui il produttore li genera. 
::Un meccanismo di sincronizzazione e richiesto perchè sorgono immediatamente due problemi:
::* Produttore troppo veloce: il consumatore non fa in tempo a consumare il valore e c'è la possibilità che i valori non ancora letti vengano sovrascritti.
::* Consumatore troppo veloce: possibilità che il consumatore legga un valore che ha già letto perchè il produttore non ha fatto in tempo a produrne uno nuovo.
::Per risolvere il problema utilizziamo due semafori: empty e full. 
::Il produttore aspetta che il segnale del semaforo empty (Proberen), scrive il valore e dà segnale sul semaforo full (Verhogen). 
::Il consumatore aspetta il segnale del semaforo full (Proberen), legge il valore e dà segnale sul semaforo empty (Verhogen). 
:* '''Buffer-limitato'''
::Simile al problema produttore/consumatore ma qui lo scambio avviene tramite un buffer limitato. 
::In questo modo nel caso di rallentamento temporaneo del consumer il producer non deve aspettare ma può produrre più unità e viceversa nel caso di rallentamento del producer, se il buffer ha più di un elemento, il consumer può utilizzare il tempo in attesa del producer per consumare più dati. 
::Nel caso il buffer sia completamente pieno/vuoto rimangono comunque i problemi di sincronizzazione tipici del problema: il producer non deve sovrascrivere dei valori che il consumer non ha ancora letto e il consumer non deve leggere più volte lo stesso valore se il producer non è stato abbastanza veloce da cambiarlo. 
::Come soluzione al problema si può utilizzare un coda circolare. Il produttore esegue una enqueue e il consumatore una dequeue. 
::Il problema può essere generalizzato facilmente a produttori/consumatori multipli ma in questo caso dobbiamo creare un semaforo per rendere atomiche la enqueue e la dequeue altrimenti incorriamo in una race condition nel accesso alla coda.

== Lezione del 28 ottobre 2016 ==

'''Implementazione dei semafori''' 
Un processo che esegue una Proberen in teoria dovrebbe aspettare continuando a controllare se può entrare nella sezione critica. Questo meccanismo si chiama "busy waiting" e consuma molte istruzioni della CPU. 
Il busy waiting è diverso dal polling in quando il polling prevede di eseguire altre azioni mentre si aspetta tra un tentativo e l'altro. 
Di solito si utilizza il busy waiting solo quando il tempo di lock di un processo è molto breve. Questo perchè anche se esoso di risorse del processore il busy waiting non comporta un context switch, cioè salvare tutto lo stato del processo in memoria, e quindi permette di risparmiare memoria.
Se invece il tempo di lock è più lungo allora è preferibile utilizzare un context-switch dove il processo si blocca da solo e chiama un processo di blocking che lo mette in una coda di attesa associata al semaforo che sta aspettando. Il controllo passa poi allo scheduler della CPU che seleziona un altro processo da eseguire.
Le primitive suspend and wakeup indicano rispettivamente lo spostamento di un processo nella/dalla coda dei processi ready.
* nei kernel monoprocessore
: Implementazione dei semafori tramite mutex che possono essere a loro volta implementate con un sistema di mascheramento degli interrupt.
* nei kernel multiprocessore
: Utilizzo di soluzioni hardware come test and set. Sono soluzioni che utilizzano il busy waiting ma in questo caso solo per rendere atomico le operazioni del semaforo, che sono poche istruzioni.
Certe implementazioni dei semafori potrebbero permettere di far andare il valore in negativo. Questo serve per misurare il numero dei processi in attesa di quel semaforo. 
'''Il problema della cena dei filosofi''': 
5 filosofi passano la loro vita pensando e mangiando. Condividono un tavolo circolare con 5 sedie e ogni sedia appartiene a un solo filosofo. Alla sinistra e alla destra di ogni piatto c'è una bacchetta per un totale di 5 bacchette. La bacchetta destra che un filosofo usa per mangiare viene quindi utilizzata come bacchetta sinistra dal filosofo alla sua destra e simmetricamente è uguale per il filosofo che siede a sinistra. 
Ogni tanto un filosofo smette di pensare e cerca di prendere le rispettive bacchette, se ci riesce può mangiare e poi rilasciare le bacchette. 
Questo problema è un modello di problema ad accesso a ''insiemi'' di risorse. Mentre nel produttore/consumatore e buffer limitato gli attori in gioco avevano la necessità di avere l'accesso esclusivo a una sola risorsa in questo problema è richiesto l'accesso a insiemi di risorse (le bacchette) le cui parti possono essere desiderate da altri richiedenti.
* soluzione con contesa sulle posate e casi di deadlock
:Poniamo un semaforo per ogni bacchetta. Può succedere però, se nel implementazione i filosofi "prendono in mano" prima la bacchetta destra e poi quella sinistra, che tutti prendono in mano contemporaneamente la bacchetta destra e rimangono in un'attesa infinita della bacchetta sinistra che non gli verrà mai rilasciata perché anche il rispettivo filosofo alla propria sinistra è in attesa. Questo è un caso di deadlock. 
:Una soluzione può essere quella di imporre che un filosofo sia "mancino" cioè prenda prima la bacchetta a sinistra e poi la destra. 
* soluzione con acquisizione atomica di entrambe le posate, casi di starvation
:Un'altra soluzione è quella di rendere atomico l'acquisizione di entrambe le posate. 
:Può succede che 4 filosofi compiano una "congiura", cioè siano d'accordo a non lasciar risorse a un quinto filosofo. Questo è un caso di starvation e non è irreale in quando i 4 filosofi potrebbero essere processi malevoli che siano stati programmati di proposito per questo.
'''System Call''':
* POSIX.
:Il POSIX è uno standard (IEEE 1003) che definisce le signature delle system call. Un sistema operativo deve rispettare il POSIX per essere definito "Unix-like". 
:Di solito i parametri delle system call sono pensati per essere contenuti in un registro. Quasi sempre le system call ritornano un intero: 0 se la procedura è stata eseguita correttamente, -1 se c'è un errore. Quando una system call ritorna -1 la variabile "globale" errno (error number) contiene il codice di errore. La variabile errno non è realmente globale perché ne esiste una per ogni processo. 
:Unix è un sistema operativo file-system centrico quindi quando facciamo input/output anche da periferiche come stampanti e lettori CD usiamo le system call per la scrittura/lettura dei file. 
:Un catalogo delle system call principali può essere trovato [[Il ''catalogo'' delle System Call | qui]].
* fork/exec
:fork e exec sono system call importanti e servono per creare un nuovo processo: 
:fork: genera un processo clone di quello che ha chiamato fork. 
:exec: "cambia" il codice eseguito dal processo corrente. 
:Quindi per "aprire un nuovo programma" si utilizza una fork seguita da un exec.

== Lezione del 4 novembre 2016 ==

* '''Problema della Cena dei filosofi'''. Soluzione con acquisizione atomica delle bacchette (con starvation)
* '''Tecnica del passaggio del testimone''' (Passing the Baton).
: Non uscire dalla mutua esclusione se c'è qualcun altro che vuole entrarci e semplicemente fare in modo che lui l'acquisisca. La mutua esclusione termina solo se non c'è nessuno che più la richiede.
* '''Cena dei filosofi, acquisizione atomica delle bacchette con passaggio del testimone'''.
* '''Implementazione della congiura dei filosofi'''

* '''Le system call di gestione file (open, read, write, close, lseek)'''
Quando lavoriamo con dei file dobbiamo sempre specificare se vogliamo solo leggerli oppure anche scrivere, magari in append mode. Ci sono quindi varie modalità con cui possiamo interagire con i file. 
Un utente potrebbe essere autorizzato a gestire il file in certe modalità oppure no. 
Il descrittore di un file è un intero. 
Le system call, a differenza delle chiamate di funzioni di libreria, non sono bufferizzate.

ESEMPIO

Se si decommenta printf stampa 2 volte hello world perchè la stringa resta nel buffer.

Se si decommenta write stampa 1 volta hello world.

Per vedere le chiamate di sistema effettuate in fase di esecuzione, compilare il codice sorgente e poi utilizzare strace -f "eseguibile".
<syntaxhighlight lang=C>
#include<stdio.h>
#include<unistd.h>

int main(int argc, char* argv[]){
//printf("hello world"); //if you ends the strings with \n is like to "fflushing" the buffer
//write(1, "hello world", 11); // 1 and 11 are file descriptors
switch(fork()) {
case 0: //child
break;
default: //parent
wait(NULL);
break;
case -1: //error
break;
}
printf("\n");
return 0;
}
</syntaxhighlight>

Copia il file passato come primo argomento (argv[1]) nel file passato come secondo argomento (argv[2]), se quest'ultimo non esiste, allora lo crea.
<syntaxhighlight lang=C>
#include<stdio.h>
#define BUFSIZE 2048
char buffer[BUFSIZE];
int main(int argc, char *argv[]){
int fdin = open(argv[1], O_RDONLY);
int fdout = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, 0666); //0666 is the umask used to modify the permissions of new files

int n;
while((n = read(fdin, buffer, BUFSIZE)) > 0)
write(fdout, buffer, n);

close(fdin);
close(fdout);
return 0;
}
</syntaxhighlight>

'''umask''' 
Con la open possiamo usare dei permessi al massimo per quelli garantiti dal umask. 
Un numero composto da quattro cifre ottali. Controlla la maschera di creazione dei file. I bit di permesso contenuti nella maschera NON vengono settati nel nuovo file creato. Corrisponde all'opereazione:

R:(D &(~M))

Può essere vista come una sottrazione, i bit accesi nella umask vengono spenti nel file creato.

e.g. se i permessi di default corrispondono a 0666(D) e la maschera corrisponde a 0022(M), R è uguale a 0666-0022 = 0644. Infatti

0022 = |000|000|010|010|
~0022 = |111|111|101|101|(7755)
0666 = |000|110|110|110|
~0022 & 0666 = |000|110|100|100|(0644)

Tabella significato cifre umask

OTTALE BINARIO SIGNIFICATO
0 000 Nessun permesso
1 001 Solo esecuzione
2 010 Solo scrittura
3 011 Scrittura ed esecuzione
4 100 Solo lettura
5 101 Lettura ed esecuzione
6 110 Lettura e scrittura
7 111 Lettura, scrittura ed esecuzione

I permessi sono rappresentati in simboli come segue:

r: read
w: write
x: execute

'''umask - S''' da shell per visualizzare la umask attuale con rappresentazione simbolica

'''ls -l "nomefile"''' da shell per visualizzare i permessi del file in notazione simbolica: '-' seguito da 3 triple che indicano i permessi di accesso per '''ugo''', ovvero, rispettivamente, per user, per group, per other.

ESEMPIO
-rw-r--r--

* '''File aperti durante fork/exec'''https://www.kernel.org/

I file aperti vengono ereditati dai processi figli.
Processo padre e processo figlio condividono lo stesso offset nei file comuni. In questo modo si evita di sovrascriversi a vicenda. Ogni volta che il padre o il figlio scrivono sul file aggiornano l'offset comune.In questo modo se l'altro processo vuole anche lui scrivere in quel file partirà dal offset aggiornato e non sovrascriverà i dati scritti dal altro processo. 

* '''La system call dup e la ridirezione'''
E' possibile fare in modo che più file descriptor siano associati a un unico file (per la precisione a un unica file table, che serve per gestire un file). 
La system call dup permette di fare ciò. Ritorna un nuovo file descriptor che punta a una file table già esistente. 
Possiamo quindi "ridirezionare" l'output o l'input di un processo figlio modificando i file descriptor prima di creare il processo figlio. Per esempio possiamo modificare un file descriptor che puntava a un normale file in modo che punti a un file di standard output e quindi anche se al processo figlio sembrerà di scrivere in un normale file starà scrivendo nel terminale.

ESEMPIO

<syntaxhighlight lang=C>
#include<sys/types.h>
#include<sys/stat.h>
#include<fcntl.h>
#include<stdio.h>
#include<unistd.h>

int main(int argc, char * argv[]){
int fdout;
if(argc > 1);
fdout = open (argv[1], O_WRONLY | O_CREAT | O_TRUNC, 0666);
switch(fork()) {
case 0: //child
dup2(fdout, 1); // duplica descrittore file, posso ridirezionare l'output. E' come fare '>' dalla shell
execlp(”ls”, “-l”, 0);
close(fdout);
break;
default: // parent
wait(NULL);
break;
case -1: // error
break;
}
printf(“\n”);
return 0;
}
</syntaxhighlight>

== Lezione del 8 novembre 2016 ==
'''Codice per la congiura dei filosofi'''
<syntaxhighlight lang=C>
#include <stdio.h>
#include <stdint.h>
#include <pthread.h>
#include "semaphore.h"

semaphore philowait[5];
semaphore mutex;
semaphore cospsem;
char philo_status[]="TTTTT";

void baton(int i){
int j = 0;
//iterate through remaining philosophers
for(j = 1; j < 5;j++){
//if there's any waiting philosopher, and no other philosophers(on his left and right side) are eating
if(philo_status[(i+j)%5]=='W' && philo_status[(i+j+1)%5]!= 'E' && philo_status[(i+j+4)%5]!='E'){
semaphore_V(philowait[(i+j)%5]);
return;
}
}
semaphore_V(mutex);
}

void ok2eat(int i){
semaphore_P(mutex);
philo_status[i]='W';
if(philo_status[(i+1)%5] == 'E' || philo_status[(i+4)%5] == 'E'){
semaphore_V(mutex);
semaphore_P(philowait[i]); //wait for baton
}
philo_status[i] = 'E';
printf("philo eating: %d |%s|\n",i,philo_status);
baton(i);
}

void ok2think(int i){
semaphore_P(mutex);
philo_status[i] = 'T';
printf("philo thinking: %d |%s|\n",i,philo_status);
baton(i);
}

void conspiracy_in(){
static int first_time = 1; //this variable's value is preserved between calls to this function
semaphore_P(mutex);
if(first_time){
//first conspirator entering here will act like nothing happened
first_time = 0;
}
else{
//conspire
semaphore_V(cospsem);
}
semaphore_V(mutex);
}

void conspiracy_out(){
semaphore_P(cospsem);
}

void *philo(void *arg) {
int i = (uintptr_t)arg;
while (1) {
//thinking/still thinking
usleep(random() % 200000);
ok2eat(i);
//eating

//conspirators need to be synchronized to conspire
if(i==1 || i==3) conspiracy_in();
if(i==1 || i==3) conspiracy_out();
usleep(random() % 200000);
ok2think(i);
//thinking again
}
}

int main(int argc, char *argv[]) {
int i;
pthread_t philo_t[5];
srandom(time(NULL));
mutex = semaphore_create(1);
cospsem = semaphore_create(0);
for (i=0; i<5; i++)
philowait[i]=semaphore_create(0);
for (i=0; i<5; i++)
pthread_create(&philo_t[i], NULL, philo, (void *)(uintptr_t) i);
for (i=0; i<5; i++)
pthread_join(philo_t[i], NULL);
}
</syntaxhighlight>

* '''Problema dei lettori e scrittori'''
* '''Semafori Binari(Introduzione)'''
: Un semaforo binario è un semaforo ordinario che rispetta la seguente invariante: '''nP<=nV+Init<=nP+1''', ovvero è un semaforo che può assumere solo valori 0 o 1.
: Si può dimostrare che i semafori ordinari sono espressivi tanto quanto quelli binari(e viceversa) fornendo una implementazione di semafori binari tramite i semafori ordinari.

== Lezione del 11 novembre 2016 ==
== Lezione del 15 novembre 2016 ==
== Lezione del 18 novembre 2016 ==
== Lezione del 22 novembre 2016 ==
== Lezione del 25 novembre 2016 ==
== Lezione del 29 novembre 2016 ==
== Lezione del 2 dicembre 2016 ==
== Lezione del 6 dicembre 2016 ==
== Lezione del 9 dicembre 2016 ==
== Lezione del 13 dicembre 2016 ==
== Lezione del 16 dicembre 2016 ==

Lezioni Anno Accademico 2016/17

2016-11-08T23:14:24Z

Alexp: /* Lezione del 8 novembre 2016 */

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

== Lezione del 23 settembre 2016 ==

'''YY'''

* Presentazione del corso.
* Strumenti del corso: web, wiki.mailing list
* Indice dei contenuti
* Prove di esame (Scritto, Prova Pratica, Progetto).

* Hardware Software
* Informatica
* Informazione/Dato
* Rivoluzione digitale (secondo rinascimento, Terza rivoluzione Industriale).
* Software Libero

== Lezione del 27 settembre 2016 ==

'''OS:Y'''

* '''Organizzazione (martedi' vs. venerdi')'''
In genere la lezione del martedì sarà più teorica mentre quella del venerdì più orientata agli aspetti pratici di laboratorio. Questa suddivisione potrebbe cambiare in quanto qualche martedì verrà saltato.
* '''Università'''
Università = studenti + docenti
* '''Digitale/Analogico'''
Digit significa cifra. Nell'informatica è fondamentale il passaggio dal continuo al discreto.
* '''Binario/Decimale'''
Nei calcolatori l'informazione è memorizzata utilizzando il sistema binario ...
(''in quanto in passato i relè consentivano di avere due stati: " 1 e 0 "'': è impreciso, qualcuno sa dare una definizione migliore? [[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 12:00, 29 September 2016 (CEST)) 
In quanto è molto semplice implementare le operazioni aritmetiche con dei circuiti elettronici utilizzando la codifica binaria. Per esempio è possibile creare un [https://it.wikipedia.org/wiki/Half-adder circuito] che somma due bit con riporto con solo due porte logiche. [[User:FedericoB|FedericoB]] ([[User talk:FedericoB|talk]]) 17:05, 29 September 2016 (CEST)
* '''I linguaggi e i problemi dell'Informatica'''
**Processing dell'informazione (Linguaggi di programmazione)
**Comunicazione (Il problema che i dati che mi servono sono in un altro luogo) (Linguaggi dei protocolli di rete, che però sono dei linguaggi temporizzati)
**Memorizzazione (Il problema che i dati mi serviranno in futuro) (Linguaggio del formato dei dati)
* '''Conoscenze a lungo, medio e breve termine nell'Informatica.'''
**BREVE: tecnologia, determinati programmi di sviluppo.
**MEDIO: singoli linguaggi, singoli OS, protocolli di comunicazione.
**LUNGO: algoritmi, informatica teorica, fondamenti costruttivi di reti e di OS.

* '''Cos'è una distribuzione'''
E' un antologia di applicazioni e librerie in modo che siano compatibili tra loro.

* '''Sistema Operativo: perché'''
Un sistema operativo è un programma che controlla l’esecuzione di programmi applicativi e agisce come interfaccia tra le applicazioni e l’hardware del calcolatore. 
E' uno strumento software complesso ed implementabile in diversi modi (monolitico, microkernel, etc.). I microcontroller non hanno OS.
Permette: contabilità delle risorse (consente a sua volta attività di benchmarking); continuità dei servizi; controllo errori
(programmi, dispositivi); multiuser (gli utenti hanno diversi diritti e proprietà sulle risorse); protezione delle attività dei
processi; astrazione file system.
* '''Struttura a livelli (layer)'''

---------------
---------------
---------------
OS
---------------L'
hw
---------------L

Consente di: separare la complessità, di avere portabilità.
Ogni livello rappresenta un cambio di linguaggio.
Più aggiungiamo livelli più aumenta il livello di astrazione.
* '''Programma/processo'''
Algoritmo: sequenza finita di istruzioni non ambigue, atta a risolvere un problema.

Programma: traduzione degli algoritmi in un linguaggio di programmazione.

Processo: istanza esecutiva di un programma. Il programma è testo statico, quando viene eseguito diviene processo. Possiamo avere
uno stesso programma in esecuzione su più processi (e.g apertura di più terminali che eseguono un editor di testo).

System call: richieste di processi al OS. e.g. printf (visto nel codice compilato in assembly tramite gcc -s), invoca write().
vi è una sequenza di azioni del tipo: richiesta di stampa al kernel --> attesa --> risposta.
* '''Storia dell'Informatica prima dei transistor'''

La storia dei calcolatori non ha un inizio preciso. Nel 1900 venne trovato sul relitto di una nave greca risalente al II secolo a.C un meccanismo in grado di calcolare i movimenti degli astri, si ipotizza con una sorprendente meccanica. Oggi questo sistema viene conosciuto come Macchina di Anticitera. Negli ultimi anni di ricerche archeologiche e storiche è venuta sempre più in superficie una vena pionieristica nel mondo classico per quanto riguarda lo studio sul calcolo automatizzato e addirittura di automi (si veda Erone di Alessandria). Ma facciamo un salto in avanti di qualche secolo... 
Già nel XVII secolo Pascal teorizza e mette in pratica uno strumento in grado di addizionare e sottrarre, e nel 1672 G.W. von Leibniz lo perfeziona con l'aggiunta della moltiplicazione e della divisione. Ma è solamente nei primi anni del 1800 che entra in scena la macchina analitica di Babbage. Estremamente complessa, la macchina era dotata di un sistema di input e di elaborazione dati e di un sistema di output. Ed è con Babbage che nascono le schede perforate. La macchina analitica venne presentata per la prima volta in Italia, durante un convegno torinese del 1840. Tra i vari collaboratori scientifici alla macchina è da annotare la presenza di Luigi Federico Menabrea, che tra le altre cose fu Ministro della Marina Militare, ingegnere e Presidente del Consiglio dei Ministri del Regno d'Italia (1867-1869). Il primo vero programmatore della storia, collaboratrice di Babbage, è Ada Lovelace (figlia del poeta Lord Byron!): progettò un algoritmo in grado di elaborare i numeri di Bernulli. 
Nel 1896 viene fondata la Tabulating Machine Company (futura IBM) e agli albori del '900, vari scienziati (trai quali Thomas Edison e Guglielmo Marconi) portarono avanti gli studi sulla valvola termoionica, elemento indispensabile dei primi calcolatori elettronici. La valvola incrementò vertiginosamente i tempi di calcolo ma l'estrema fragilità della stessa causò una serie di problematiche che si risolsero solamente con l'entrata in gioco del transistor.

== Lezione del 30 settembre 2016 ==

'''YC'''

(Storia dopo l'avvento del transistor)

Tre innovazioni indipendenti:
* Multitasking: Inizialmente ideato per mantenere la CPU occupata con altri processi mentre si faceva Input/Output. Permette di dare l'idea al utente di poter eseguire più processi contemporaneamente anche se questi in realtà sono eseguiti dalla cpu in modo intervallato. Ci sono certi computer che hanno più esecutori e quindi possono realmente eseguire multipli processi contemporaneamente.
* Supporto Multiuser
* Interattività:l'interazione con l'utente cambia il flusso del programma.

Queste tre proprietà sono ortogonali quindi possono esistere nei sistemi varie combinazioni di queste.

Iniziano anche a separarsi i ruoli tra programmatori e utenti.Prima i computer venivano utilizzati solo da chi creava programmi ora anche da chi li utilizza senza avere le conoscenze per crearli.

Il Time Sharing.

Sistemi Paralleli (SIMD/MIMD)
Sistemi Real Time

Dal 1969: UNIX.

Il linguaggio C e la portabilità dei sistemi operativi.
Caratteristiche del linguaggio C:
* grande controllo sul codice generato
* costrutti per l'elaborazione a basso livello
* supporto per la programmazione strutturata
* linguaggio "leggero": poche parole chiave, I/O gestito tramite librerie
* Il compilatore C è scritto in C.

Portabilità di un compilatore. I cross-compiler.

Il comando UNIX cc (o gcc): un comando unico per attivare l'intera toolchain per generare un eseguibile.

Il punto e virgola trasforma espressioni in istruzioni (terminatore).

1975? l'avvento dei personal computer. (in realtà il primo PC forse e' la Perrottina Olivetti del 1964).

Compiti a casa:
Portare esperimenti in C ritenuti "difficili".

[[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 10:41, 1 October 2016 (CEST)

== Lezione del 7 ottobre 2016 ==
Audio Lezione: [https://drive.google.com/open?id=0B8G3NNuJ7MA7TzJXUTJZM3RBUlE 7\10\16]
* '''Esempi di programmi in linguaggio C'''
Abbiamo commentato i programmi dal 1.1 al 1.7 che si possono trovare in questa [[2016-17_Programmi_C|pagina]].
* '''Economia Push/Economia Pull'''
Nell'economia push si basa la produzione sulla previsione di domanda e la si cerca di aumentare tramite la pubblicità. Questa è stata la principale metodologia utilizzata nei secoli scorsi.
Al giorno d'oggi si sta facendo avanti un differente approccio chiamato "economia pull" dove la produzione è basata sulla domanda effettiva. Per esempio per richiedere un finanziamento per l'economia push l'approccio comune è tramite una banca a cui si chiede un prestito in base alle previsioni di ricavo. Invece nell'economia pull è esemplare il fenomeno del crowdfounding dove si riceve un finanziamento dalla "folla" cioè da un gruppo di persone che dona una piccola parte di denaro ciascuna in base al reale interesse per il prodotto/servizio.
* '''Sistemi Operativi e parallelismo'''
Più processi si dicono in esecuzione concorrente quando accedono a risorse condivise.
Un programma è multithread quando tutti i thread condividono la stessa memoria. Ogni thread deve avere un suo stack.
La concorrenza si studia in particolare in sistemi operativi in quanto un sistema operativo multitasking è un sistema concorrente.
Concorrenza di processi in architetture SMP (Symmetric multiprocessor system) e non. (RD: non mi pare di aver spiegato cosa sia l'SMP) 
Simulazione del fenomeno della '''race condition'''. Si ha '''race condition''' quando un programma concorrente può puo' produrre diversi risultati se eseguito piu' volte per colpa della diversa evoluzione temporale delle elaborazioni. 
Per risolvere questo dovremmo raggruppare le istruzioni in ''sezioni critiche'' (sequenze inscindibili di istruzioni che devono essere eseguite come se fossero atomiche, tutta la sequenza o niente).
* '''Architettura a livelli e virtualizzazione'''
Dato un A e un A’ e riusciamo a usare A’ come A, allora A’ lo possiamo chiamare A virtuale.
L'idea che alla base delle macchine virtuali è di creare un interprete di un ISA differente o uguale a quello del sistema in modo da virtualizzare una reale macchina hardware e quindi poterla usare per gli stessi scopi di una macchina reale. E' quindi possibile, per esempio, installare sistemi operativi su hardware virtuale. 
L'insieme dei componenti hardware virtuali e il software installato su di questi prende il nome di ''macchina virtuale''.
Uno dei principali vantaggi, oggi molto utilizzato in ambito cloud, è quello di poter suddividere facilmente risorse hardware fisiche, per esempio spazio su disco e potenza di elaborazione, tra macchine virtuali differenti.
* '''Laboratorio di cross-compiling'''
Nel ultima parte della lezione abbiamo fatto un esperimento sulla portabilità dei compilatori. 
Abbiamo a disposizione un linguaggio ad alto livello che chiameremo L, due interpreti hw0 e hw1 per linguaggi a basso livello che chiameremo lhw0 e lhw1 e infine due compilatori L->lhw0 uno scritto in python e l'altro in L. 
Se compiliamo con il compilatore scritto in python (abbiamo un interprete python installato sulla macchina che stiamo utilizzando) il compilatore scritto in L otteniamo un compilatore scritto in lhw0 L->lhw0. 
Se ora modifichiamo il compilatore scritto in L L->lhw0 in modo che crei codice per hw1 (basta modificare gli indici numerici delle istruzioni) otteniamo un compilatore in L L->lhw1. Se lo compiliamo con il compilatore L->lhw0 otteniamo un ''cross-compiler'' scritto in lhw0 L->lhw1, cioè un compilatore che crea codice eseguibile su una macchina diversa da quella attuale. 
Se ora utilizziamo il cross compiler L->lhw1 per compilare il compilatore scritto in L L->hw1 otteniamo invece un compilatore che può essere eseguito su hw1. 
A questo punto su hw1 potremmo utilizzare l'ultimo compilatore creato per compilare sempre il compilatore scritto in L L->hw1 ma vedremo che otterremo sempre lo stesso file perché avremo raggiunto il limite.
 
Il materiale per poter replicare l'esperimento sulla portabilità dei compilatori è [http://www.cs.unibo.it/~renzo/so/tools/portability3.tgz qui].
[[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 13:42, 8 October 2016 (CEST)

== Lezione del 11 ottobre 2016 ==
*'''C'''
<syntaxhighlight lang=C>
#include <stdio.h>

void dump (void* f, size_t len){ //size_t is the sizeof() return type
unsigned char *s = f;
size_t i;
for (i = 0; i < len; i++)
printf("%02x",s[i]); //%02x means print at least 2 digits and add 0's if there are less
printf("\n");
}

int main(){

int v[] = {1, 2, 3, 4}; //v is (int*) 0x32ef...
v[2] = 42; //*((int*) 0x32ef) + 2 = 42, moves the address by 2 "positions", aka 4+4 bytes
v = 0x33;//(int*) 0x32ef.. = 0x33 (i.e.) 4 = 42

char s[] = "ciao";
int t[] = {0x63, 0x69, 0x61, 0x6f, 0x00}; //ciao in ASCII hex. if int OUT:'c'. if char OUT:"ciao"
char u[] = {99, 105,97, 111, 0 }; //ciao in ASCII dec. OUT:"ciao"

char *q = "ciao";
char *w = "mare";

printf("%s", s);
printf("%s", t);
printf("%s", u);

dump(s, sizeof(s));
dump(t, sizeof(t));
dump(q, sizeof(*q)); //*q size is 1B (it points to 1 char). OUT: 63('c')
dump(q, sizeof(q)); //q size is 8B. OUT: 5B of "ciao" + 3B of contiguous string "mare"
}
</syntaxhighlight>

OUTPUT:
<pre>
ciao
c
ciao
63 69 61 6f 00
63 00 00 00 69 00 00 00 61 00 00 00 6f 00 00 00 00 00 00 00 //int are 4B, char 1B, so we have empty bytes.
Little endian pattern is evident. %s allow to print untill the first null, so printf prints just 'c' with int declaration of t[]
63
63 69 61 6f 00 6d 61 72 // 6d = m, 61 = a, 72 = r.
</pre>

* '''Assioma di finite progress.'''
"Tutto è vero purchè ogni statement abbia durata sconosciuta, ma finita"
* '''Modalità di concorrenza.'''
1- Inconsapevolmente concorrenti: ogni processo elabora ciò per cui è stato creato. Il kernel si occupa di coordinazione e comunicazione.

2- Indirettamente concorrenti: processi che accedono a file condivisi.

3- Consapevolmente concorrenti: il programma ha diversi processi in esecuzione.
*''' Convenzioni usate nel corso (e negli esami) relative alle istruzioni atomiche'''
Le istruzioni atomiche vengono compiute in modo indivisibile, garantendo che l'azione non interferisca con altri processi durante la sua esecuzione.
Vengono rappresentate nel seguente modo:
<pre>
<istruzione atomica>
</pre>
Anche gli statement sono istruzioni atomiche(escluso il caso long long).
*''' Proprieta' di Safety e Liveness'''
-Safety: se il programma evolve, evolve bene(S)

"''Something good'' happens"

-Liveness: il programma va avanti(L)

"''Something eventually'' happens"

* '''Problema del consenso.'''
Il problema è così definito: ci sono n processi, ognuno propone un valore. Al termine tutti i processi devono accordarsi su di 1 dei valori proposti.Il suddetto problema è risolvibile se e solo se vengono rispettate le seguenti proprietà (2 di Safety + 1 di Liveness)

Proprietà:

S(1)- Tutti i processi devono ritornare lo stesso valore

S(2)- Ogni processo corretto decide uno tra i valori proposti

L(1)- Ogni processo corretto deve dare una risposta

w/o S(1): f(x) = x

w/o S(2): f(x) = 42

w/o L(1): f(x) = while(1)

*w/o = without

* '''Problemi delle elaborazioni concorrenti. Prima definizione (non formale) di Deadlock e Starvation'''
Introduzione alla notazione per la rappresentazione dei processi concorrenti

ESEMPIO 1.0

process p {
...
...
}

process q {
...
...
}

Due processi eseguiti in concorrenza.

...
cobegin
...
//
...
//
...
coend

cobegin e coend indicano la sezione di codice con le istruzioni (rappresentate da "..." e separate da "//")che verranno eseguite in concorrenza.

ESEMPIO 1.1 - Merge sort
cobegin
sort(v[1 : N])
//
sort(v[N : N])
//
merge(v[1 : N]), v[N : M])
coend

Se isoliamo le istruzioni senza considerare cobegin e coend, lo pseudocodice è corretto.
Se consideriamo anche cobegin e coend il programma esegue la funzione di merge() in concorrenza con le due chiamate a sort(), utilizzando risorse in comune e pertanto cercando di ordinare elementi non ancora ordinati nelle due metà dell'array.
Se spostiamo l'invocazione di merge al di fuori della sezione cobegin ... coend, lo pseudocodice (vedi in basso) è corretto.

cobegin
sort(v[1 : N])
//
sort(v[N : N])
coend
merge(v[1 : N]), v[N : M])

In particolare nella programmazione concorrente si devono affrontare due problemi che riguardano la liveness, parliamo di deadlock e starvation.

'''DEADLOCK''': uno o più processi non possono continuare l'esecuzione perchè ognuno di essi è in attesa che gli altri facciano qualcosa

ESEMPIO 1.2

process p {
while 1:
prendi a
prendi b
calcola f(a,b)
lascia a
lascia b
}

process q {
while 1:
prendi a
prendi b
calcola f(a,b)
lascia a
lascia b
}

Supponiamo di invertire l'ordine di prendi a e prendi b nel processo p. Dopo che entrambi i processi eseguono la prima istruzione lo scenario che si sviluppa è il seguente: al processo p serve la risorsa a, presa dal processo q, al quale servirebbe la risorsa b, presa dal processo p. I processi aspettano a vicenda che uno rilasci la risorsa che possiede l'altro. Risorsa necessaria ad entrambi i processi per eseguire l'istruzione (f(a,b)) che le richiederebbe entrambe. I processi sono deadlocked.

'''STARVATION''': quando un processo attende una risorsa indefinitamente, e questa non gli viene mai allocata

ESEMPIO 1.3
process p {
while 1:
prendi a
calcola f(a)
lascia a
}

process q {
while 1:
prendi a
calcola f(a)
lascia a
}

Supponiamo che i processi per realizzare "prendi a" verifichino la disponibilità di a tramite polling (provando ripetutamente se a è libero). Il processo q può essere sfortunato e non riuscire mai ad avere accesso ad a (tutte le volte che cerca di "prenderlo" lo troverà impegnato da p). Il processo q è in starvation.

ESEMPIO 1.4
"Supponiamo di avere tre processi (P1, P2, P3) i quali richiedono periodicamente accesso alla risorsa R. Consideriamo la situazione nella quale P1 è in possesso della risorsa, e sia P2 che P3 attendono per quella risorsa. Quando P1 esce dalla sua sezione critica, a P2 o P3 dovrebbe essere permesso l'accesso a R. Assumiamo che il SO garantisca l'accesso a P3 e che P1 richieda nuovamente la risorsa prima che P3 termini la sua sezione critica. Se il SO dovesse garantire l'accesso a P1 dopo che P3 abbia finito, e successivamente dovesse garantire alternativamente a P1 e P3 l'accesso alla risorsa, allora P2 potrebbe vedersi indefinitamente negato l'accesso alla risorsa, sebbene non vi sia una situazione di deadlock" (Stallings W.(2015). ''Operating System: internals and design principles''. (8th ed). Pearson)

'''Problema: posso creare sezioni critiche, tramite la programmazione, senza aiuti hardware?'''

ESEMPIO

process p
/*enter_cs*/
A = A + 1
/*exit_cs*/

process q
/*enter_cs*/
A = A - 1
/*exit_cs*/

'''Le 4 proprietà della critical section(CS)'''

SAFETY(1): una operazione all'interno della CS

ESEMPIO
process p
while 1:
/*enter_cs*/
A = A + 1
/*exit_cs*/
... <--- process q deve poter "entrare" qui

LIVENESS(1): no deadlock

LIVENESS(2): no starvation

LIVENESS(3): no useless wait

''Dekker(1st attempt) //KEY: turno''

turn = p //var globale condivisa

process p{
while (turn != p)
;
/*A = A + 1*/
turn = q
...
}

process q{
while(turn != q)
;
/*A = A - 1*/
turn = p
...
}

Non rispetta la proprietà di liveness(3), infatti uno dei due processi può dover attendere a lungo il suo turno eseguendo ciclicamente l'empty statement all'interno
del corpo del while. Questa situazione può verificarsi se l'altro processo fallisce dentro o fuori la sua CS (in questo caso l'attesa è infinita). Inoltre visto che i processi si alternano strettamente nell'utilizzo della loro critical section, il ritmo di esecuzione è dettato dal processo più lento dei due.

''Dekker(2nd attempt) //KEY: flag, ma senza turno''

inp = false

inq = false

process p{
while 1:
while(inq)
;
inp = true
/*A = A + 1*/
inp = false
...
}

process q{
while 1:
while(inp)
;
inq = true
/*A = A - 1*/
inq = false
...
}

In questo caso se uno dei processi fallisce fuori dalla CS (dopo aver settato il flag a false) l'altro processo non viene bloccato. Se invece un processo fallisce nella sua CS oppure dopo aver settato il flag a true allora l'altro processo resta bloccato indefinitamente. Non è garantita inoltre la mutua esclusione in quanto entrambi potrebbero essere al contempo nelle loro rispettive CS, ad esempio:

p valuta la condizione del while e trova inq a false

q valuta la condizione del while e trova inp a false

p assegna true a inp ed entra nella sua CS

q assegna true a inq ed entra nella sua CS

....entrambi sono nella rispettiva CS --> no liveness(1)

''Dekker(3nd attempt) //KEY: come 2nd ma con due istruzioni scambiate di ordine''

process p{
while 1:
inp = true
while(inq)
;
/*A = A + 1*/
inp = false
...
}

process q{
while 1:
inq = true
while(inp)
;
/*A = A - 1*/
inq = false
...
}

Scambiando l'ordine di due istruzioni vi è la mutua esclusione, tuttavia se entrambi i processi assegnano true al loro rispettivo flag, prima di valutare la condizione
del while, entrambi resteranno all'interno del while in attesa che l'altro processo "esca dalla CS" (non vi è mai entrato) --> deadlock

''Dekker(4nd attempt) //KEY: flag + delay''

process p{
while 1:
inp = true
while(inq){
inp = false; < delay >; inp = true;
}
/*A = A + 1*/
inp = false
...
}

process q{
while 1:
inq = true
while(inp){
inq = false; < delay >; inq = true;
}
/*A = A - 1*/
inq = false
...
}

In questo caso il settare il proprio flag a true è indice del desiderio di entrare nella propria CS. Vi è ancora mutua esclusione. Se però dovesse verificarsi una sequenza del tipo:

p imposta flag inp a true

q imposta falg inq a true

p valuta la condizione del while

q valuta la condizione del while

p imposta flag inp a false

q imposta flag inq a false

p imposta flag inp a true

q imposta flag inq a true

allora c'è la possibilità che si ripeta all'infinito (entrambi i processi potrebbero rimanere nel while). Essendo però una condizione che dipende dalla velocità relativa dei due processi, esiseranno delle situazioni nelle quali uno dei due processi potrà entrare, così come vi saranno delle situazioni nelle quali nessun processo avrà accesso alla propria CS --> livelock

'''Dekker...finally //KEY: flag + turni ("cambio delay con turno)'''

needp = false

needq = false

turn = p

process p{
while 1:
needp = true
while (needq) {
needp = false
while(turn == q)
;
needp = true
}
/*A = A + 1*/
needp = false
turn = q
...
}

process q{
while 1:
needq = true
while(needp) {
needq = false;
while(turn == p)
;
needq = true
}
/*A = A - 1*/
needq = false
turn = p
...
}

In questo caso il processo che vuole entrare nella sua CS ne manifesta il bisogno settando need a true. Se entrambi i processi entrano nel corpo del while il tie-break è espletato dal while la cui condizione è un turn che sarà uguale soltanto ad uno dei due processi (in questo caso turn è inizializzata a p), e dunque non si verificherànno situazioni di deadlock o livelock.
*'''Proprietà della sezione critica'''
Mutua esclusione 
Assenza di deadlock 
Assenza di starvation 
Assenza di delay non necessari

*'''La test&set'''
E' un istruzione atomica per impostare il valore di una variabile a 1 (lock) ma ritornare il vecchio valore. Questa istruzione può essere utilizzata per gestire sezioni critiche. 
Il valore ritornato dalla test and set viene comparato a 1, se è uguale si aspetta altrimenti si procede. 
In questo modo il primo processo che cercherà di entrare nella sezione critica ci riuscirà e imposterà il lock a 1, gli altri processi si troveranno il lock a 1 e dovranno aspettare. Quando il primo processo avrà finito ripristinerà il vecchio valore di lock e permetterà a uno degli altri processi di eseguire la test and set e di entrare nella sezione critica.
----
Altri argomenti trattati che non sono stati qui riportati in forma di appunti:
Gestione algoritmica della critical section.
Algoritmo di Dekker.
Gestione architetturale della critical section.

[[User:Renzo|Renzo]] ([[User talk:Renzo|talk]]) 10:35, 17 October 2016 (CEST)

== Lezione del 14 ottobre 2016 ==
Audio Lezione: [https://drive.google.com/open?id=0B8G3NNuJ7MA7UlJadTRVbzhWRFE 14\10\16]
* Sistemi Operativi per elaboratori multiprocessore SMP/non SMP
* Macchine di von Neumann (e di Harvard).
* Il bus.
* Interrupt e Trap
* Gestione degli interrupt
* Mascheramento degli interrupt
* Interrupt Nidificati
* DMA
* Device a carattere e device a blocchi
* System call come trap.
* La gerarchia delle memorie
* cache

== Lezione del 18 ottobre 2016 ==
Audio Lezione: [https://drive.google.com/open?id=0B8G3NNuJ7MA7eVlFdWR0cUkxd2M 18/10/16]

Argomenti trattati:
*'''Implementazione in C della Test&Set, degli Algoritmi di Dekker e Peterson.'''
Codice sorgente disponibile [[Dekker,_Peterson_e_Test%26Set_in_C|qui]].
*'''Definizione di Semaforo.'''
Un semaforo è una variabile intera che può essere modificata solo da 2 operazioni atomiche: P(Proberen) e V(Verhogen). 
P aspetta che il valore sia minore o uguale a zero. Quando lo diventa decrementa il valore. 
S incrementa il valore. 
*'''Invariante del Semaforo.'''
Il numero di Proberen deve essere minore o uguale al numero di Verhogen più il valore d'inizializzazione del semaforo. 
In questo modo si può gestire per esempio l'allocazione di risorse. Il semaforo viene inizializzato al numero di risorse e ogni volta che un processo ha bisogno della risorsa esegue un proberen, quindi decrementa il valore se la risorsa è disponibile. Quando un processo rilascia la risorsa esegue un verhogen.
*'''Esempio: implementazione di sezione critica e di semplice sincronizzazione con semafori.'''

== Lezione del 21 ottobre 2016 ==
*'''Make'''
Make è un sistema per la compilazione intelligente dei programmi. 
Permette invece di compilare tutto il programma tutte le volte di compilarne solo una parte, solo quella che è stata modificata.
Per capirne il funzionamento è utile un parallelismo con le ricette di cucina. Si specificano dei target che sono gli obbiettivi della ricetta.Per fare una ricetta servono degli ingredienti e magari quegli ingredienti hanno a loro volta delle ricette. Make allo stesso modo definisce dei target che possono avere come dipendenze altri target. 
Nel installazione del programma il programma ./configure cerca nel sistema se le librerie da cui è dipendente il programma sono presenti. 
*'''Git'''
Git è un sistema di versioning, serve a tener traccia delle modifiche apportante a un progetto nel tempo. E' utile per collaborare a un progetto condiviso. 
Possibilità per ogni membro del repository di lavorare in maniera indipendente e poi aggiornare il progetto comune. 
Ce ne sono stati tanti di sistemi di versioning tipo SVN, Mercurial ma attualmente Git è il più utilizzato. 
Git non serve solo per scrivere programmi ma per esempio anche libri, in modo collaborativo. 
Git è completamente distribuito, non esiste in un repository una copia principale e delle copie secondarie ma ogni copia può essere principale. 
Per iniziare un repository git si utilizza il comando ''git init''. 
Per aggiungere un file al repository si utilizza il comando ''git add''. 
Ma ad ogni singola modifica git non aggiorna automaticamente il repository ma è l'utente che tramite il comando git commit indica che una certa versione del progetto deve essere salvata. 
Il comando ''git log'' serve a visualizzare la storia del repository. 
Il comando ''git diff'' serve a vedere la differenza tra ciò che è nel repository e le modifiche di cui non si è ancora fatto il commit. 
Dopo aver dato il comando add si dice che i file sono 'on stage' prima del commit. 
Il comando ''git checkout'' serve a spostarsi nella storia del repository. 
Il comando ''git clone'' serve a copiare un repository remoto. 
Il comando ''git push'' serve a inviare le modifiche al repository remoto mentre il comando ''git pull'' serve a ricevere le modifiche più aggiornate dal repository remoto. 
Il ''merge'' è il processo in cui uno degli utenti che crea un conflitto deve "a mano" scegliere quali parti dei due commit in conflitto vuole tenere. 
Git è utile per trovare i bug che non erano presenti in versioni precedenti del progetto. Si può tornare alla versione precedente stabile e avanzare nella storia fino a trovare una versione instabile. A questo punto è probabile che l'origine del bug sia nelle modifiche che hanno creato questa versione instabile. 
Github è una piattaforma di repository dove possono essere mantenuti dei progetti gratuitamente se sono con licenza libera. 
In una directory in cui è presente un repository git e sempre la presente la cartella ''.git'' dove il sistema di versioning mantiene il database della storia. 

== Lezione del 25 ottobre 2016 ==
Audio Lezione: [https://drive.google.com/open?id=0B8G3NNuJ7MA7WjZJMm11cjhuQXc 25/10/16]

Argomenti trattati:
* '''Semafori fair'''
Un semaforo è "fair" quando tende a non sbloccare dallo stato di attesa sempre lo stesso processo ma cerca di distribuire la possibilità di esecuzione a più processi.
* '''Problemi classici della concorrenza risolti con semafori'''
** '''Produttore/consumatore'''
::Due processi: produttore e consumatore. Il produttore genera continuamente dei valori e il consumatore continuamente li legge. Il consumatore deve leggere i valori nello stesso ordine in cui il produttore li genera. 
::Un meccanismo di sincronizzazione e richiesto perchè sorgono immediatamente due problemi:
::* Produttore troppo veloce: il consumatore non fa in tempo a consumare il valore e c'è la possibilità che i valori non ancora letti vengano sovrascritti.
::* Consumatore troppo veloce: possibilità che il consumatore legga un valore che ha già letto perchè il produttore non ha fatto in tempo a produrne uno nuovo.
::Per risolvere il problema utilizziamo due semafori: empty e full. 
::Il produttore aspetta che il segnale del semaforo empty (Proberen), scrive il valore e dà segnale sul semaforo full (Verhogen). 
::Il consumatore aspetta il segnale del semaforo full (Proberen), legge il valore e dà segnale sul semaforo empty (Verhogen). 
:* '''Buffer-limitato'''
::Simile al problema produttore/consumatore ma qui lo scambio avviene tramite un buffer limitato. 
::In questo modo nel caso di rallentamento temporaneo del consumer il producer non deve aspettare ma può produrre più unità e viceversa nel caso di rallentamento del producer, se il buffer ha più di un elemento, il consumer può utilizzare il tempo in attesa del producer per consumare più dati. 
::Nel caso il buffer sia completamente pieno/vuoto rimangono comunque i problemi di sincronizzazione tipici del problema: il producer non deve sovrascrivere dei valori che il consumer non ha ancora letto e il consumer non deve leggere più volte lo stesso valore se il producer non è stato abbastanza veloce da cambiarlo. 
::Come soluzione al problema si può utilizzare un coda circolare. Il produttore esegue una enqueue e il consumatore una dequeue. 
::Il problema può essere generalizzato facilmente a produttori/consumatori multipli ma in questo caso dobbiamo creare un semaforo per rendere atomiche la enqueue e la dequeue altrimenti incorriamo in una race condition nel accesso alla coda.

== Lezione del 28 ottobre 2016 ==

'''Implementazione dei semafori''' 
Un processo che esegue una Proberen in teoria dovrebbe aspettare continuando a controllare se può entrare nella sezione critica. Questo meccanismo si chiama "busy waiting" e consuma molte istruzioni della CPU. 
Il busy waiting è diverso dal polling in quando il polling prevede di eseguire altre azioni mentre si aspetta tra un tentativo e l'altro. 
Di solito si utilizza il busy waiting solo quando il tempo di lock di un processo è molto breve. Questo perchè anche se esoso di risorse del processore il busy waiting non comporta un context switch, cioè salvare tutto lo stato del processo in memoria, e quindi permette di risparmiare memoria.
Se invece il tempo di lock è più lungo allora è preferibile utilizzare un context-switch dove il processo si blocca da solo e chiama un processo di blocking che lo mette in una coda di attesa associata al semaforo che sta aspettando. Il controllo passa poi allo scheduler della CPU che seleziona un altro processo da eseguire.
Le primitive suspend and wakeup indicano rispettivamente lo spostamento di un processo nella/dalla coda dei processi ready.
* nei kernel monoprocessore
: Implementazione dei semafori tramite mutex che possono essere a loro volta implementate con un sistema di mascheramento degli interrupt.
* nei kernel multiprocessore
: Utilizzo di soluzioni hardware come test and set. Sono soluzioni che utilizzano il busy waiting ma in questo caso solo per rendere atomico le operazioni del semaforo, che sono poche istruzioni.
Certe implementazioni dei semafori potrebbero permettere di far andare il valore in negativo. Questo serve per misurare il numero dei processi in attesa di quel semaforo. 
'''Il problema della cena dei filosofi''': 
5 filosofi passano la loro vita pensando e mangiando. Condividono un tavolo circolare con 5 sedie e ogni sedia appartiene a un solo filosofo. Alla sinistra e alla destra di ogni piatto c'è una bacchetta per un totale di 5 bacchette. La bacchetta destra che un filosofo usa per mangiare viene quindi utilizzata come bacchetta sinistra dal filosofo alla sua destra e simmetricamente è uguale per il filosofo che siede a sinistra. 
Ogni tanto un filosofo smette di pensare e cerca di prendere le rispettive bacchette, se ci riesce può mangiare e poi rilasciare le bacchette. 
Questo problema è un modello di problema ad accesso a ''insiemi'' di risorse. Mentre nel produttore/consumatore e buffer limitato gli attori in gioco avevano la necessità di avere l'accesso esclusivo a una sola risorsa in questo problema è richiesto l'accesso a insiemi di risorse (le bacchette) le cui parti possono essere desiderate da altri richiedenti.
* soluzione con contesa sulle posate e casi di deadlock
:Poniamo un semaforo per ogni bacchetta. Può succedere però, se nel implementazione i filosofi "prendono in mano" prima la bacchetta destra e poi quella sinistra, che tutti prendono in mano contemporaneamente la bacchetta destra e rimangono in un'attesa infinita della bacchetta sinistra che non gli verrà mai rilasciata perché anche il rispettivo filosofo alla propria sinistra è in attesa. Questo è un caso di deadlock. 
:Una soluzione può essere quella di imporre che un filosofo sia "mancino" cioè prenda prima la bacchetta a sinistra e poi la destra. 
* soluzione con acquisizione atomica di entrambe le posate, casi di starvation
:Un'altra soluzione è quella di rendere atomico l'acquisizione di entrambe le posate. 
:Può succede che 4 filosofi compiano una "congiura", cioè siano d'accordo a non lasciar risorse a un quinto filosofo. Questo è un caso di starvation e non è irreale in quando i 4 filosofi potrebbero essere processi malevoli che siano stati programmati di proposito per questo.
'''System Call''':
* POSIX.
:Il POSIX è uno standard (IEEE 1003) che definisce le signature delle system call. Un sistema operativo deve rispettare il POSIX per essere definito "Unix-like". 
:Di solito i parametri delle system call sono pensati per essere contenuti in un registro. Quasi sempre le system call ritornano un intero: 0 se la procedura è stata eseguita correttamente, -1 se c'è un errore. Quando una system call ritorna -1 la variabile "globale" errno (error number) contiene il codice di errore. La variabile errno non è realmente globale perché ne esiste una per ogni processo. 
:Unix è un sistema operativo file-system centrico quindi quando facciamo input/output anche da periferiche come stampanti e lettori CD usiamo le system call per la scrittura/lettura dei file. 
:Un catalogo delle system call principali può essere trovato [[Il ''catalogo'' delle System Call | qui]].
* fork/exec
:fork e exec sono system call importanti e servono per creare un nuovo processo: 
:fork: genera un processo clone di quello che ha chiamato fork. 
:exec: "cambia" il codice eseguito dal processo corrente. 
:Quindi per "aprire un nuovo programma" si utilizza una fork seguita da un exec.

== Lezione del 4 novembre 2016 ==

* '''Problema della Cena dei filosofi'''. Soluzione con acquisizione atomica delle bacchette (con starvation)
* '''Tecnica del passaggio del testimone''' (Passing the Baton).
: Non uscire dalla mutua esclusione se c'è qualcun altro che vuole entrarci e semplicemente fare in modo che lui l'acquisisca. La mutua esclusione termina solo se non c'è nessuno che più la richiede.
* '''Cena dei filosofi, acquisizione atomica delle bacchette con passaggio del testimone'''.
* '''Implementazione della congiura dei filosofi'''

* '''Le system call di gestione file (open, read, write, close, lseek)'''
Quando lavoriamo con dei file dobbiamo sempre specificare se vogliamo solo leggerli oppure anche scrivere, magari in append mode. Ci sono quindi varie modalità con cui possiamo interagire con i file. 
Un utente potrebbe essere autorizzato a gestire il file in certe modalità oppure no. 
Il descrittore di un file è un intero. 
Le system call, a differenza delle chiamate di funzioni di libreria, non sono bufferizzate.

ESEMPIO

Se si decommenta printf stampa 2 volte hello world perchè la stringa resta nel buffer.

Se si decommenta write stampa 1 volta hello world.

Per vedere le chiamate di sistema effettuate in fase di esecuzione, compilare il codice sorgente e poi utilizzare strace -f "eseguibile".
<syntaxhighlight lang=C>
#include<stdio.h>
#include<unistd.h>

int main(int argc, char* argv[]){
//printf("hello world"); //if you ends the strings with \n is like to "fflushing" the buffer
//write(1, "hello world", 11); // 1 and 11 are file descriptors
switch(fork()) {
case 0: //child
break;
default: //parent
wait(NULL);
break;
case -1: //error
break;
}
printf("\n");
return 0;
}
</syntaxhighlight>

Copia il file passato come primo argomento (argv[1]) nel file passato come secondo argomento (argv[2]), se quest'ultimo non esiste, allora lo crea.
<syntaxhighlight lang=C>
#include<stdio.h>
#define BUFSIZE 2048
char buffer[BUFSIZE];
int main(int argc, char *argv[]){
int fdin = open(argv[1], O_RDONLY);
int fdout = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, 0666); //0666 is the umask used to modify the permissions of new files

int n;
while((n = read(fdin, buffer, BUFSIZE)) > 0)
write(fdout, buffer, n);

close(fdin);
close(fdout);
return 0;
}
</syntaxhighlight>

'''umask''' 
Con la open possiamo usare dei permessi al massimo per quelli garantiti dal umask. 
Un numero composto da quattro cifre ottali. Controlla la maschera di creazione dei file. I bit di permesso contenuti nella maschera NON vengono settati nel nuovo file creato. Corrisponde all'opereazione:

R:(D &(~M))

Può essere vista come una sottrazione, i bit accesi nella umask vengono spenti nel file creato.

e.g. se i permessi di default corrispondono a 0666(D) e la maschera corrisponde a 0022(M), R è uguale a 0666-0022 = 0644. Infatti

0022 = |000|000|010|010|
~0022 = |111|111|101|101|(7755)
0666 = |000|110|110|110|
~0022 & 0666 = |000|110|100|100|(0644)

Tabella significato cifre umask

OTTALE BINARIO SIGNIFICATO
0 000 Nessun permesso
1 001 Solo esecuzione
2 010 Solo scrittura
3 011 Scrittura ed esecuzione
4 100 Solo lettura
5 101 Lettura ed esecuzione
6 110 Lettura e scrittura
7 111 Lettura, scrittura ed esecuzione

I permessi sono rappresentati in simboli come segue:

r: read
w: write
x: execute

'''umask - S''' da shell per visualizzare la umask attuale con rappresentazione simbolica

'''ls -l "nomefile"''' da shell per visualizzare i permessi del file in notazione simbolica: '-' seguito da 3 triple che indicano i permessi di accesso per '''ugo''', ovvero, rispettivamente, per user, per group, per other.

ESEMPIO
-rw-r--r--

* '''File aperti durante fork/exec'''https://www.kernel.org/

I file aperti vengono ereditati dai processi figli.
Processo padre e processo figlio condividono lo stesso offset nei file comuni. In questo modo si evita di sovrascriversi a vicenda. Ogni volta che il padre o il figlio scrivono sul file aggiornano l'offset comune.In questo modo se l'altro processo vuole anche lui scrivere in quel file partirà dal offset aggiornato e non sovrascriverà i dati scritti dal altro processo. 

* '''La system call dup e la ridirezione'''
E' possibile fare in modo che più file descriptor siano associati a un unico file (per la precisione a un unica file table, che serve per gestire un file). 
La system call dup permette di fare ciò. Ritorna un nuovo file descriptor che punta a una file table già esistente. 
Possiamo quindi "ridirezionare" l'output o l'input di un processo figlio modificando i file descriptor prima di creare il processo figlio. Per esempio possiamo modificare un file descriptor che puntava a un normale file in modo che punti a un file di standard output e quindi anche se al processo figlio sembrerà di scrivere in un normale file starà scrivendo nel terminale.

ESEMPIO

<syntaxhighlight lang=C>
#include<sys/types.h>
#include<sys/stat.h>
#include<fcntl.h>
#include<stdio.h>
#include<unistd.h>

int main(int argc, char * argv[]){
int fdout;
if(argc > 1);
fdout = open (argv[1], O_WRONLY | O_CREAT | O_TRUNC, 0666);
switch(fork()) {
case 0: //child
dup2(fdout, 1); // duplica descrittore file, posso ridirezionare l'output. E' come fare '>' dalla shell
execlp(”ls”, “-l”, 0);
close(fdout);
break;
default: // parent
wait(NULL);
break;
case -1: // error
break;
}
printf(“\n”);
return 0;
}
</syntaxhighlight>

== Lezione del 8 novembre 2016 ==
'''Codice per la congiura dei filosofi'''
<syntaxhighlight lang=C>
#include <stdio.h>
#include <stdint.h>
#include <pthread.h>
#include "semaphore.h"

semaphore philowait[5];
semaphore mutex;
semaphore cospsem;
char philo_status[]="TTTTT";

void baton(int i){
int j = 0;
//iterate through remaining philosophers
for(j = 1; j < 5;j++){
//if there's any waiting philosopher, and no other philosophers(on his left and right side) are eating
if(philo_status[(i+j)%5]=='W' && philo_status[(i+j+1)%5]!= 'E' && philo_status[(i+j+4)%5]!='E'){
semaphore_V(philowait[(i+j)%5]);
return;
}
}
semaphore_V(mutex);
}

void ok2eat(int i){
semaphore_P(mutex);
philo_status[i]='W';
if(philo_status[(i+1)%5] == 'E' || philo_status[(i+4)%5] == 'E'){
semaphore_V(mutex);
semaphore_P(philowait[i]); //wait for baton
}
philo_status[i] = 'E';
printf("philo eating: %d |%s|\n",i,philo_status);
baton(i);
}

void ok2think(int i){
semaphore_P(mutex);
philo_status[i] = 'T';
printf("philo thinking: %d |%s|\n",i,philo_status);
baton(i);
}

void conspiracy_in(){
static int first_time = 1; //this variable's value is preserved between calls to this function
semaphore_P(mutex);
if(first_time){
//first conspirator entering here will act like nothing happened
first_time = 0;
}
else{
//conspire
semaphore_V(cospsem);
}
semaphore_V(mutex);
}

void conspiracy_out(){
semaphore_P(cospsem);
}

void *philo(void *arg) {
int i = (uintptr_t)arg;
while (1) {
//thinking/still thinking
usleep(random() % 200000);
ok2eat(i);
//eating

//conspirators need to be synchronized to conspire
if(i==1 || i==3) conspiracy_in();
if(i==1 || i==3) conspiracy_out();
usleep(random() % 200000);
ok2think(i);
//thinking again
}
}

int main(int argc, char *argv[]) {
int i;
pthread_t philo_t[5];
srandom(time(NULL));
mutex = semaphore_create(1);
cospsem = semaphore_create(0);
for (i=0; i<5; i++)
philowait[i]=semaphore_create(0);
for (i=0; i<5; i++)
pthread_create(&philo_t[i], NULL, philo, (void *)(uintptr_t) i);
for (i=0; i<5; i++)
pthread_join(philo_t[i], NULL);
}
</syntaxhighlight>

* '''Problema dei lettori e scrittori'''
* '''Semafori Binari(Introduzione)'''
: Un semaforo binario è un semaforo ordinario che rispetta la seguente invariante: '''nP<=nV+Init<=nP+1''', ovvero è un semaforo che può assumere solo valori 0 o 1.
: Si può dimostrare che i semafori ordinari sono espressivi tanto quanto quelli binari(e viceversa) fornendo una implementazione di semafori binari tramite i semafori ordinari

== Lezione del 11 novembre 2016 ==
== Lezione del 15 novembre 2016 ==
== Lezione del 18 novembre 2016 ==
== Lezione del 22 novembre 2016 ==
== Lezione del 25 novembre 2016 ==
== Lezione del 29 novembre 2016 ==
== Lezione del 2 dicembre 2016 ==
== Lezione del 6 dicembre 2016 ==
== Lezione del 9 dicembre 2016 ==
== Lezione del 13 dicembre 2016 ==
== Lezione del 16 dicembre 2016 ==

Esperimenti con semafori e monitor in C

2016-10-26T18:55:31Z

Alexp: Corretto il link al materiale

Ho messo a vostra disposizione alcuni sorgenti che implementano in C le astrazioni di semaforo e monitor come le abbiamo viste (o vedremo presto) a lezione.

Ho messo il materiale in [http://www.cs.unibo.it/~renzo/so/tools/sm.tgz questo file].

La directory comprende:
* un Makefile
* tlist.[ch] un modulo di implementazione di liste circolari di thread_id (usate per gestire i processi bloccati). Le liste possono essere usate come code o stack.
* suspend.[ch] è il modulo che implementa la sospensione e riattivazione dei pthread (usando il segnale SIGUSR1).
* semaphore.[ch] implementazione dei semafori '''fair'''
* monitor.[ch] implementazione dei monitor (con semantica '''signal urgent''' per le variabili di condizione).
* prod_cons.c esempio: produttore consumatore con i semafori
* bounded_buf.c esempio: bounded_buffer con i semafori
* bounded_buf_mon.c esempio: bounded buffer con i monitor
* philo.c: cena dei filosofi (la soluzione è volutamente errata e può generare deadlock

== uso dei semafori ==

Se volete fare altri esperimenti con i semafori dovete includere il file semaphore.h nei vostri sorgenti C.

Un semaforo ha tipo ''semaphore'' e viene creato in questo modo
<syntaxhighlight lang=C>
semaphore mutex;
mutex = mutex_create(1);
</syntaxhighlight>
(ovviamente le variabili semaphore devono essere condivise e 1 è solo l'esempio di valore iniziale per un semaforo mutex)

Le operazioni P e V su mutex si scrivono così:
<syntaxhighlight lang=C>
semaphore_P(mutex);
semaphore_V(mutex);
</syntaxhighlight>

== produttore e consumatore ==

Il file ''prod_cons.c'' implementa una soluzione del problemadel produttore/consumatore.

Il buffer e i semafori sono definiti come variabili condivise.
<syntaxhighlight lang=C>
semaphore full;
semaphore empty;
volatile int buffer;
</syntaxhighlight>

Il main inizializza i semafori e crea i thread.
<syntaxhighlight lang=C>
int main(int argc, char *argv[]) {
pthread_t prod_t;
pthread_t cons_t;
full=semaphore_create(0);
empty=semaphore_create(1);

pthread_create(&prod_t, NULL, producer, NULL);
pthread_create(&cons_t, NULL, consumer, NULL);
pthread_join(prod_t, NULL);
pthread_join(cons_t, NULL);
}
</syntaxhighlight>

La sincronizzazione fra produttore e il consumatore viene realizzata come segue:
<syntaxhighlight lang=C>
void *producer(void *arg) {
while (1) {
int value;
// produce value
semaphore_P(empty);
buffer = value;
semaphore_V(full);
}
}

void *consumer(void *arg) {
while (1) {
int value;
semaphore_P(full);
value = buffer;
semaphore_V(empty);
// consume value
}
}
</syntaxhighlight>

== Uso dei monitor ==

Un monitor viene creato con la funzione:
<syntaxhighlight lang=C>
monitor mymon;
mymon = monitor_create()
</syntaxhighlight>

Le variabili di condizione vengono create nel seguente modo:
<syntaxhighlight lang=C>
condition oktoproceed;
oktoproceed = condition_create(mymon);
</syntaxhighlight>
(NB: le variabili di condizione sono '''sempre''' riferite ad uno specifico monitor).

Le procedure entry sono normali funzioni C ma occorre mettere all'entrata e all'uscita le chiamate
''monitor_{enter,exit}':
<syntaxhighlight lang=C>
int mymon_dosomething(/* params */) {
rval int;
monitor_enter(mymon);
....
monitor_exit(mymon);
return rval;
}
</syntaxhighlight>

Le operazioni wait e signal sulle variabili di condizione si scrivono così:
<syntaxhighlight lang=C>
condition_wait(oktoproceed);
condition_signal(oktoproceed);
</syntaxhighlight>

== Bounded buffer con i monitor ==
Vengono definite come variabili condivise il monitor e le variabili di condizione
<syntaxhighlight lang=C>
monitor bb;
condition ok2write;
condition ok2read;
</syntaxhighlight>
oltre al buffer e alle varibili per la gestione delle strutture dati, fra le quali il contatore ''buflen''.

Il monitor viene creato da questa funzione:
<syntaxhighlight lang=C>
void bb_create(void) {
bb = monitor_create();
ok2write = condition_create(bb);
ok2read = condition_create(bb);
}
</syntaxhighlight>

che viene richiamata dal main prima di far partire i thread:
<syntaxhighlight lang=C>
int main(int argc, char *argv[]) {
pthread_t prod_t;
pthread_t cons_t;
bb_create();

pthread_create(&prod_t, NULL, producer, NULL);
pthread_create(&cons_t, NULL, consumer, NULL);
pthread_join(prod_t, NULL);
pthread_join(cons_t, NULL);
}
</syntaxhighlight>

Il monitor implementa due procedure entry put e get:
<syntaxhighlight lang=C>
void bb_put(int value) {
monitor_enter(bb);
if (buflen >= SIZE)
condition_wait(ok2write);
// enqueue value in the buffer
buflen++;
condition_signal(ok2read);
monitor_exit(bb);
}

int bb_get(void) {
int rval;
monitor_enter(bb);
if (buflen <= 0)
condition_wait(ok2read);
// dequeue value from the buffer
buflen--;
condition_signal(ok2write);
monitor_exit(bb);
return rval;
}
</syntaxhighlight>

Il codice dei processi produttore e del consumatore usa le procedure entry del monitor bb in questo modo:
<syntaxhighlight lang=C>
void *producer(void *arg) {
while (1) {
int value;
// produce value
bb_put(value);
}
}

void *consumer(void *arg) {
while (1) {
int value;
value = bb_get();
// consume value
}
}
</syntaxhighlight>