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:
- Facilitare l'utilizzo del sistema (senza S.O. sarebbe a carico del programmatore conoscere tutti i linguaggi con cui si comunica con l'architettura della macchina);
- Rendere affidabile, protetto e sicuro l'utilizzo del sistema (e.g. un processo potrebbe recar danno all'intero sistema se non controllato o gestito, potrebbe ignorare i permessi di visualizzazione di un file);
- Astrarre l'hardware (e.g. filesystem);
- Garantire l'efficienza (e.g. non tenere la CPU in idle adottando opportuni algoritmi di scheduling);
- Assicurare portabilità ;
Un approccio molto usato è il cosiddetto approccio a strati ("a livelli") in cui ogni strato utilizza i servizi forniti al livello inferiore e ne fornisce di nuovi a quello superiore. Astraendo il nostro calcolatore possiamo piazzare al livello più basso l'hardware e, subito sopra, il sistema operativo. I due layer comunicano usando il linguaggio ISA (Instruction Set Architecture), nativo della CPU stessa, al quale si aggiungono quelli che permettono di comunicare con i vari controllori dei dispositivi come la scheda di rete, la stampante, etc. Sopra il livello del sistema operativo possiamo collocare quello delle librerie e, infine, quello degli applicativi.
- Systemcall = meccanismo usato da un processo per richiedere al SO una qualche funzionalità a livello kernel. Un esempio è la funzione printf() del linguaggio C (stampa a video) che utilizza la systemcall write() (una delle systemcall per la gestione dei dispositivi).
Storia dei sistemi operativi
Nella generazione zero (1800 ca.) possiamo includere Babbage con la sua macchina analitica e lady Ada Lovelace.
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.
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
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;
}