Lezioni Anno Accademico 2017/18 I semestre

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

Lezione del 26 settembre 2017

W⁴ H Y

• What:
• Who:

---

Noi studenti ed "entrambi" i professori.

• When:

---

Il corso ha durata annuale. Verrà svolto ogni martedì e venerdì dalle 15:30 alle 18:30.

• La lezione del martedì sarà dedicata alla programmazione concorrente;
• La lezione del venerdì sarà dedicata alla parte generale. Terminerà circa 15 minuti prima dell'orario stabilito.

• Where:

---

Sempre in Aula 1 Ercolani (E1): DISI, Scuole Ercolani, Mura Anteo Zamboni 2B.

• How:

---

Il corso si svolgerà tramite:

• Lezioni frontali in aula.
• Attività di laboratorio.
• Esercitazioni.

Inoltre, durante l'ultimo periodo di lezioni del secondo semestre, vi sarà un periodo di ripasso del programma tramite esercizi, in vista dell'esame. Durante la lezione del 3/10 sono state indicate alcune propedeuticità del corso. tra cui: programmazione, algoritmi e architettura degli elaboratori in primis. Importanti sono anche i corsi di Analisi matematica e Algebra e geometria. Per farla breve, il primo anno è propedeutico al secondo.

• Why:

Fonti e strumenti del corso

• wiki creata di gruppo, lezioni frontali e esercitazioni.
• Non esiste un vero e proprio testo consigliato. Tutte le informazioni sono date DURANTE il corso.
• Per domande specifiche scrivere su mailing list (so@cs.unibo.it);
• Per esercizi, appunti e programma svolto rivolgersi al wiki (so.v2.cs.unibo.it);
• Per live streaming (www.cs.unibo.it/~renzo/live/).

Modalità di esame

esame scritto (diviso in due parti: una parte generale e una di programmazione concorrente) + progetto + orale (facoltativo), possibilità di dare solo lo scritto per ottenere un massimo di 18. La modalità per studenti in "difficoltà" è disponibile solo fino agli appelli autunnali.

• Si parlerà del progetto indicativamente a partire da Dicembre 2017.
• L'orale può essere sostenuto da chi vuole migliorare (peggiorare) il voto ottenuto, o da chi vuole ottenere la lode.

Orario di ricevimento per il primo semestre (fino al 15/09/17)

martedì alle 11:30.

• Università = docenti + studenti.
• Informatica = come generare informazione automatica.
• Hardware, Software, Elaborazione, Comunicazione, Memorizzazione, Digitale/Analogico.

Introduzione

La principale distinzione che facciamo tra dato e informazione è che il dato, da solo, è privo di significato. Se, tuttavia, viene interpretato in un particolare contesto allora può diventare informazione significativa per chi sta interpretando i dati.

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

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

Un linguaggio è un entità software, ed è definito come una quadrupla (alfabeto, sintassi, lessico, semantica) dove:

• l'alfabeto è l'insieme di simboli che compone il linguaggio.
• il lessico si può vedere come una funzione che va dai simboli a un booleano e ci dice quali sono le frasi ben formate.
• la sintassi determina quali delle sequenze scritte sono effettivamente corrette.
• la semantica associa un significato alle parole ben formate.

Lezione del 29 settembre 2017

Cos'è un sistema operativo

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

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

A cosa serve un sistema operativo? Principalmente, ha i seguenti scopi:

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

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

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

Storia dei sistemi operativi

Nella generazione zero (1800 ca.) possiamo includere Babbage con la sua macchina analitica e lady Ada Lovelace.

Macchina analitica di Babbage

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

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

Diversi tipi di Transistor

---

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

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

• READY pronto per essere eseguito ma, il processore è già occupato;
• RUNNING in esecuzione;
• WAIT in attesa di I/O.

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

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

Lezione del 3 ottobre 2017

Introduzione alla programmazione concorrente

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

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

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

Più processi possono eseguire lo stesso programma ma, ognuno di essi, ha i propri dati su cui operare e il suo stato di avanzamento. In particolare:

• un processo è un'entità, un attore che ha delle proprietà e delle risorse associate;
• in ogni istante, il processo può essere interrotto.
  

Più thread che vengono eseguiti parallelamente, invece, condividono gli stessi dati su cui operare.
Codici di esempio:

processi

#include <stdio.h>
#include <unistd.h>

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

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

thread

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
#define NUM_THREADS     5
#define MAX 1000000

int sum;
 
void* perform_work(){
	int i;
	
	for(i = 0; i < MAX; i++) sum = sum + 1;
  	/* optionally: insert more useful stuff here */ 
  	return NULL;
}
 
int main( int argc, char** argv ){
	pthread_t threads[NUM_THREADS];
  	int thread_args[NUM_THREADS];
  	int result_code;
  	unsigned index;
 
	sum = 0;
  	// create all threads one by one
  	for(index = 0; index < NUM_THREADS; ++index ){
    		thread_args[index] = index;
    		printf("In main: creating thread %d\n", index);
    		result_code = pthread_create(&threads[index], NULL, perform_work, NULL);
    		assert(!result_code);
  	} 
  	// wait for each thread to complete
  	for(index = 0; index < NUM_THREADS; ++index ){
    		// block until thread 'index' completes
    		result_code = pthread_join(threads[index], NULL);
    		assert(!result_code);
    		printf("In main: thread %d has completed\n", index);
   	}
 
   	printf("In main: All threads completed successfully\n" );
	printf("Result: %d\n", sum);
   	exit( EXIT_SUCCESS );
}

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

---

Pthread (POSIX thread)

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

Le istruzioni fondamentali sono:

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

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

---

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

Questo accade principalmente per due motivi:

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

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

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

Mutex

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
#define NUM_THREADS     5
#define MAX 1000000

int sum;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
 
void* perform_work(){
	int i;
	
	for(i = 0; i < MAX; i++){ 
		pthread_mutex_lock(&mutex);		
		sum = sum + 1;
		pthread_mutex_unlock(&mutex);
	}
  	/* optionally: insert more useful stuff here */ 
  	return NULL;
}
 
int main( int argc, char** argv ){
	pthread_t threads[NUM_THREADS];
  	int thread_args[NUM_THREADS];
  	int result_code;
  	unsigned index;

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

---

MUTEX

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

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

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

---

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

Consideriamo ora due scenari leggermente più complicati:

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

La prima condizione si chiama deadlock, la seconda condizione si chiama starvation. Il deadlock (stallo) è un problema che non può scomparire autonomamente, mentre la starvation ("inedia") si può risolvere da sola. A tal proposito ci viene incontro l'assioma di finite progress: "ogni processo che può avanzare, prima o poi lo farà".

In ogni caso, per parlare in maniera più approfondita di queste tematiche:

• avremo bisogno di un modello di riferimento
• avremo bisogno di paradigmi in grado di esprimere la concorrenza (alcuni paradigmi saranno rivolti alla concorrenza a memoria privata; altri al multithreading a risorse condivise)
• dovremo imparare a scrivere programmi

Nel nostro modello di riferimento l'assegnamento di costanti è un operazione atomica. Dagli esempi precedenti, infatti, si evince come ci sia bisogno di creare atomicità in sezioni critiche. Inoltre, il nostro modello dovrà rispettare le proprietà di safety e di liveness, ovvero:

• Tutti i processi danno la stessa risposta;
• Ogni processo corretto da come risposta una tra quelle proposte;
• Ogni processo prima o poi fornisce una risposta.

Lezione del 6 ottobre 2017

Il linguaggio C

Il linguaggio C nasce nei primi anni 70 grazie al lavoro di Dennis Ritchie con lo scopo di scrivere il sistema operativo Unix. Quali sono le caratteristiche di C e cosa lo rende un linguaggio adatto per scrivere un sistema operativo? Un linguaggio per scrivere un sistema operativo deve:

• essere indipendente dalla macchina su cui viene scritto
• dare la possibilità di lavorare direttamente con la memoria
• permette di andare a modificare i singoli bit in memoria
• essere semplice da usare
• essere massimamente produttivo
• essere veloce, efficiente

C presenta le caratteristiche dette sopra e alcune altre:

• in C, dal punto di vista sintattico, tutto è funzione. Si può vedere un programma in C come un insieme di funzioni. La funzione principale è il main. L'unica cosa che la distingue è il nome, a parte quello il main è una funzione come le altre. Prende due argomenti: argcount e argvalue, che contengono rispettivamente il numero degli argomenti e un array contenente gli argomenti stessi. L'interfaccia del main è tipicamente:

   int main(int argc, char *argv[])
  

• il costrutto fondamentale è l'espressione. expression ; = instruction
• sono previste istruzioni di struttura

  if, while, switch, etc.
  

• le variabili, per poter essere utilizzate, devono essere sempre definite
• il C è un linguaggio fortemente tipato, però con un certo numero di eccezioni: ad esempio, è possibile fare il casting esplicito di un puntatore void * in qualsiasi tipo, senza che il compilatore dia errori o warnings, con conseguente perdita di type safety
• C è un linguaggio "per adulti": non impone una struttura ordinata al codice, come ad esempio fa invece Python, ed è piena responsabilità del programmatore scrivere programmi ordinati/leggibili. Inoltre molte operazioni che in altri linguaggi non sarebbero permesse lo sono invece in C: anche in questo caso è responsabilità del programmatore fare corretto uso del linguaggio
• C è un linguaggio molto semplice. Come si sopperisce alle mancanze imposte da questa semplicità? Grazie alle librerie: in C tutte le funzionalità aggiuntive (non fornite dal linguaggio stesso, come l'allocazione di memoria, la stampa a schermo, la gestione di input e output) sono fornite dalle librerie
• C è anche sintatticamente semplice. Dove va a finire la complessità sintattica? Nel preprocessore: prima di essere compilato un programma in C passa attraverso un preprocessore, che produce codice in base alle direttive di preprocessione date nel codice stesso

  #ifdef VAR ... #endif, # e ## operator, __LINE__,etc
  

• in C vi sono fondamentalmente due tipi di dato: int e float. Tutti gli altri "tipi" di dato sono derivati da essi. Si hanno diversi modificatori, che vanno a modificare la quantità di memoria allocata per la variabile. Alcuni di questi sono

  long, short, char, etc
  

  Un dato di tipo long int ha, solitamente, la dimensione di una parola di memoria della macchina su cui è eseguito il programma. char alloca 8 bits. Se si prende una variabile di un certo tipo e lo si assegna ad una di tipo più ampio, il valore viene mantenuto. Viceversa quando si assegna una variabile di un tipo ad una di tipo meno ampio, una volta "superato il limite" si torna indietro ciclicamente al valore iniziale. Per queste situazioni il compilatore non dà né warnings né errors: sono perfettamente lecite in C
• in C si passa una varibile ad una funzione solo per valore; per passare "per riferimento" una variabile si passa per valore l'indirizzo della variabile
• in C si può fare uso di puntatori alla memoria. Dato un puntatore p, un'istruzione del tipo p+i va letta come: vai avanti di i posizioni della grandezza del tipo del puntatore ognuno. Un vettore in C non è altro che un puntatore che non può essere assegnato. Una scrittura del tipo array[i] è una abbreviazione di *(array + i). Non c'è controllo in C se vado oltre la memoria allocata per l'array. Perché? In Pascal, ad esempio, c'è un tale controllo. Il motivo per cui in C questo manca è che questo controllo genera ulteriore codice macchina. Dovendo C essere efficiente, non ci si può permettere un tale costo aggiuntivo. La responsabilità di non andare oltre è lasciata al programmatore

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

#define _GNU_SOURCE
#include <unistd.h>
#include <sys/syscall.h>

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

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

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

  return buf + len + 1;
}

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

Lezione del 10 ottobre 2017

Programmazione concorrente: notazione e un primo problema

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

A
cobegin
  B
//
  C
//
  D
coend
E

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

Un esempio che si presta molto bene ad illustrare la programmazione concorrente è quello del merge sort concorrente:

leggi vettore
cobegin
  ordina la prima metà del vettore
//
  ordina la seconda metà del vettore
coend
merge (miscela) i risultati

Versione errata del merge sort concorrente:

leggi vettore
cobegin
  ordina la prima metà del vettore
//
  ordina la seconda metà del vettore
//  
  merge (miscela) i risultati
coend

Avendo un numero N di processi, vorremmo avere una notazione che ci permetta di definire una porzione di codice come atomica (la sezione critica). Come possiamo procedere?
Teoricamente, vorremmo avere due funzioni, csenter() e csexit() che ci permettano di entrare e uscire dalla sezione critica del codice senza causare errori nella computazione.
Quali sono le proprietà che queste funzioni debbono rispettare?

1. Devono garantire la mutua esclusione (1 solo processo esegue la critical section alla volta). Contando n csenter() completate e m csexit() completate la differenza deve essere <=1
2. Non devono fare deadlock tra di loro
3. Non devono fare starvation tra loro
4. (no unnecessary delay) un processo che non sta usando la critical section {csenter()..csexit()} non deve bloccare un altro processo dall'entrarvi.

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

Soluzione di Dekker

Vorremmo avere programmi che abbiano la seguente struttura:

process[i], i=1,...,N

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

Ad esempio, tornando al problema dei thread che sommavano 1 a sum MAX volte, avremo:

process A:

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

process B:

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

Soluzione 1: A turni

Qual è il problema?

• mutex OK
  
• deadlock OK
  
• starvation OK
  
• no unnecessary delay NO
  

Perché se P ha bisogno spesso della critical section, P non deve aspettare che Q chieda la critical section e, all'uscita, lo autorizzi di nuovo ad usarla impostando turn = P. Se Q una volta richiesta la sezione non la usa ma si ferma, P non può richiederla ancora perché appartiene ancora a Q.

turn=P

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

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

Soluzione 2: con 2 variabili

Cerchiamo di risolvere il problema dei turni

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

• starvation OK
• deadlock OK
• no unnecessary delay OK
• mutex NO

Possono essere entrambi come false, escono insieme nel while, tutti e due mettono a true ed entrano assieme nel while.

inP = false;
inQ = false;

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

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

Soluzione 3

Il problema di soluzione 2 è che i processi non sono al corrente dell'intenzione dell'altro di entrare nel while quindi si crea il problema.

• mutex OK
• deadlock NO (potrebbero entrambi richiedere, contemporaneamente, l'ingresso alla critical section)
• starvation OK
• non unnecessary delay OK

needP = false;
needQ = false;

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

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

Soluzione 4

• mutex OK
• deadlock OK
• no unnecessary delay OK
• starvation NO

Perché può esistere il processo che prova sempre a chiedere nel momento sbagliato e non esegue mai.

inP = false;
inQ = false;

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

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

Soluzione finale

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

• mutex OK
• deadlock OK
• starvation OK
• non unnecessary delay OK

needP = false;
needQ = false;
turn = P

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

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

Lezione del 13 ottobre 2017

Il linguaggio C: PREPROCESSORE

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

Un primo esempio è dato dalla direttiva #define, la quale crea una macro, ovvero l’associazione di un identificatore (con o senza parametri) con una stringa di token. Le macro così definite possono assumere quindi diverse funzioni:

1. condizione per l’inclusione o meno di codice nel file che verrà passato al compilatore;
2. inserimento di costanti all’interno del codice (notare che questa direttiva nasce molto prima della keyword const del linguaggio C);
3. creazione di abbreviazioni a porzioni di codice più lunghe.

Caso 1

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

#include <stdio.h>

#define DEBUG

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

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

    return 0;
}

Da notare in questo caso l’utilizzo della macro __linux__, una macro predefinita nei sistemi Linux-based, che consente di discriminare il sistema operativo su cui il programma viene compilato, dando quindi la possibilità di compilare del codice diverso in base alla piattaforma utilizzata.

Caso 2

Il secondo caso prevede la presenza di un valore in seguito all’identificatore, che quindi verrà sostituito in ogni sua occorrenza all’interno del codice. È da far notare come questo meccanismo sia simile all’utilizzo della keyword const del linguaggio, ma quest’ultima nasce solo successivamente come alternativa type-safe (dal momento che le macro potrebbero essere utilizzate ovunque senza alcun tipo di controllo). Questo meccanismo torna ad esempio quando si vuole effettuare un’operazione un numero di volte prefissato; in questo modo, è sufficiente modificare il valore della macro nella sua definizione, per aggiornare tutto il programma che utilizzava quella macro al nuovo valore.

#include <stdio.h>

#define ITER_NUM 5

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

    return 0;
}

Caso 3

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

#include <stdio.h>

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

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

    return 0;
}

Che produrrà, in seguito all’esecuzione del preprocessore:

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

    return 0;
}

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

#include <stdio.h>

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

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

    return 0;
}

si otterrà un risultato che in un primo momento potrebbe essere inaspettato:

101
102

Ad un’analisi più approfondita tuttavia, è possibile accorgersi dell’errore: il preprocessore effettua una sostituzione testuale dei parametri al momento dell’utilizzo della macro; ciò significa che sostituisce ogni occorrenza del primo parametro nella token string con il primo valore fornito, e dualmente per il secondo parametro. Il codice che verrà sottoposto al compilatore conterrà quindi due incrementi della variabile i. Un esempio a grandi linee delle operazioni eseguite dal compilatore è la seguente (per capirlo è necessario aver ben compreso la nozione di post-incremento della variabile i):

1. assegno alla variabile i il valore 100
2. 10 è maggiore di i?
3. NO, incremento i (ora i vale 101)
4. scrivo i (101)
5. incremento i (ora i vale 102)
6. 10 è maggiore di i?
7. NO, scrivo i (102)

Approfondimenti

Esistono molti altri operatori che si possono utilizzare all’interno delle macro, due esempi sono:

• l’operatore # che, se anteposto al nome di un parametro nella stringa di token, viene riconosciuto dal processore, che rimpiazza il parametro con il simbolo # anteposto con il proprio valore letterale convertito in una stringa costante;
• l’operatore ## "combina" due token in uno: unisce il token alla sinistra e quello alla destra dell’operatore per farlo diventare un’unico token. Questo torna molto utile se uno dei due token proviene da un parametro della macro.
  
  

Per un esempio su questi ultimi due operatori: tables and preprocessors tricks

---

Per ulteriori approfondimenti sul preprocessore del C: Approfondimenti sul preprocessore del C

Lezione del 17 ottobre 2017

Oltre la soluzione di Dekker

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

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

Questa soluzione ha però due limiti:

• non funziona con un numero di processi > 2
• è relativamente complicato da capire, si può fare di meglio!

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

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

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

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

Davanti a noi si aprono principalmente due possibilità:

• l'hardware della macchina ci viene in aiuto mascherando gli interrupt (nei sistemi mono-core)
• l'hardware (e gli ingegneri) ci aiuta fornendoci un'apposita istruzione atomica: la TEST&SET

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

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

Quindi, intuitivamente, possiamo avere due casi: o la variabile globale è 0, e la T&S assegna 0 a x e setta la variabile globale a 1, o la variabile globale è a 1 e la funzione semplicemente immagazzina 1 in x. Questa semplice funzione è abbastanza per realizzare i protocolli csenter() e csexit() e realizzare le critical section:

G = 0; /* global variable */
csenter():
    L;
    do{
        T&S(L, G)
    }while(L == 1)

csexit():
    G = 0

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

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

Lezione del 20 ottobre 2017

Complementi sul linguaggio C e cenni sulle librerie standard

• strutture con vettore di dimensione nulla come ultimo campo.
• funzioni a numero variabile di parametri
• formattazione (printf/scanf), uso avanzato
• allocazione dinamica

Lezione del 24 ottobre 2017

Implementazione dei semafori nei sistemi operativi

Un costrutto è un'entità del linguaggio che implementa un'astrazione. La semantica del semaforo può essere in larga parte descritta dal suo invariante:

nP <= nV + init
init + nV - nP >= 0

La V si può fare in qualsiasi momento, la P invece può non essere possibile da completare (nP = numero operazioni P completate) perché incrementandola potrebbe rendere la disuguaglianza non vera.

Se eseguo V il valore del semaforo = +1 se eseguo P il valore del semaforo = -1 quindi P può essere eseguito solo se il valore del semaforo > 0 e ridurrà il valore del semaforo di 1.

Una sezione critica può essere realizzata con un semaforo. Espressa con solo l'invariante non evitiamo la starvation.

semaphore s(1)

s.P()
critical code
s.V()

Iniziamo con un semaforo inizializzato a 0, A entra ma non può eseguire P, quindi subentra B che esegue V e da il segnale ad A in modo che A possa proseguire:

semaphore synch(0)

Process A:
//wait 4 B
synch.P()
  ....

Process B:
//signal B
synch.V()

Da ricordare:

• Con i semafori nessuna protezione di variabile condivisa è automatica (occorre inserire sezioni critiche!)
• I semafori hanno memoria, nel senso che se mandiamo una V adesso e una P tra mezz'ora il semaforo ricorderà di aver fatto una V. Se non abbiamo necessità di una determinata segnalazione la dobbiamo rimuovere.
• Una V autorizza l'attivazione di un processo bloccato. Se facciamo una V allora uno dei processi bloccati partirà, ma non sappiamo quando.
• Un programma con almeno un semaforo che abbia solo operazioni P o solo operazioni V è errato.
• Se un testo chiede di usare semafori si usano SOLO semafori!

Semafori binari

#include<stdio.h>
#include<pthread.h>
#include<semaphore.h>

semaphore full;
semaphore empty;
volatile int buffer;
/*aspetto un tempo random con massimo 2s e genero un intero, a questo punto
semaphore_P è empty, facendo in questo modo il produttore scopre che il buffer
è vuoto e lo dichiara non più vuoto, in questo momento non è né vuoto né pieno,
mette il valore nel buffer condiviso e setta semaphore_V a full permettendo al
consumatore di leggere.*/
void *producer(void *arg) {
	while (1) {
		int value;
		usleep(random() % 2000000);
		value = random() % 32768;
		printf("produced: %d\n",value);
		semaphore_P(empty);
		buffer = value;
		semaphore_V(full);
		printf("sent: %d\n",value);
	}
}
/*il consumatore arriva a quel semaphore_P che è pieno quando può va avanti, si
copia in una variabile locale il buffer e semaphore_P diventa non pieno e non
vuoto. Stampa il valore e si mette "a dormire" per un tempo arbitrario.*/
void *consumer(void *arg) {
	while (1) {
		int value;
		printf("\t\tconsumer ready\n");
		semaphore_P(full);
		value = buffer;
		semaphore_V(empty);
		printf("\t\tconsume %d\n", value);
		usleep(random() % 2000000);
	}
}

int main(int argc, char *argv[]) {
	pthread_t prod_t;
	pthread_t cons_t;
	full=semaphore_create(0);
	empty=semaphore_create(1);
	srandom(time(NULL));
	pthread_create(&prod_t, NULL, producer, NULL);
	pthread_create(&cons_t, NULL, consumer, NULL);
	pthread_join(prod_t, NULL);
	pthread_join(cons_t, NULL);
}

Se avessi più produttori e consumatori il codice funzionerebbe lo stesso in quanto i semafori valgono al più 1 quindi solo 1 produttore supera il blocco. Stessa cosa per quanto riguarda il consumatore.

Definizione di potere espressivo e dimostrazione dell'equivalenza di potere espressivo fra semafori binari e semafori generali.

Una generalizzazione della sezione critica è quella di inizializzare il semaforo ad un numero positivo anche maggiore di 1, ovvero consentiamo a "n" numero di processi che può prosegurie dopo una P ovvero:

semaphore s(4)

  s.P()
  use resource
  s.V()

Lezione del 27 ottobre 2017

Shell UNIX

Lista comandi shell UNIX

Struttura di uno script Shell

[comandi] [complementi] [complementi oggetto]