Lezioni Anno Accademico 2017/18 I semestre

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

Lezione del 26 settembre 2017

Titolo della lezione: W⁴ H Y

• What:
• Who:

---

Noi studenti ed "entrambi" i professori.

• When:

---

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

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

• Where:

---

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

• How:

---

Il corso si svolgerà tramite:

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

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

• Why:

---

• Fonti e strumenti del corso: wiki creata di gruppo, lezioni frontali e esercitazioni.
  • Non esiste un vero e proprio testo consigliato. Tutte le informazioni sono date DURANTE il corso.
  • Per domande specifiche scrivere su mailing list (so@cs.unibo.it);
  • Per esercizi, appunti e programma svolto rivolgersi al wiki (so.v2.cs.unibo.it);
  • Per live streaming (www.cs.unibo.it/~renzo/live/).
• Modalità di esame: esame scritto (diviso in due parti: una parte generale e una di programmazione concorrente) + progetto + orale (facoltativo), possibilità di dare solo lo scritto per ottenere un massimo di 18. La modalità per studenti in "difficoltà" è disponibile solo fino agli appelli autunnali.
  • Si parlerà del progetto indicativamente a partire da Dicembre 2017.
  • L'orale può essere sostenuto da chi vuole migliorare (peggiorare) il voto ottenuto, o da chi vuole ottenere la lode.
• Orario di ricevimento per il primo semestre (fino al 15/09/17): martedì alle 11:30.
• Università = docenti + studenti.
• Informatica = come generare informazione automatica.
• Hardware, Software, Elaborazione, Comunicazione, Memorizzazione, Digitale/Analogico.

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

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

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

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

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

Lezione del 29 settembre 2017

Cos'è un sistema operativo e un po' di storia

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

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

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

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: processi, thread e librerie

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

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

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

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

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

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

processi

#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

Esempio di possibile rappresentazione 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.

Esempio 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