FormularioSistemi Operativi e Reti di Calcolatori: definizioni, teoremi e formule delle note, in ordine di capitolo

I. Introduzione ai sistemi operativi

Sistema operativo - ruolo, struttura e system call

Definizione (sistema operativo). Un sistema operativo (operating system, OS) è un programma che agisce da intermediario tra l'utente e l'hardware. Ha tre scopi: eseguire i programmi dell'utente e rendere facile risolvere i suoi problemi, rendere comodo l'uso del calcolatore, usare l'hardware in modo efficiente.

Definizione (system call). Una system call (chiamata di sistema) è l'interfaccia di programmazione verso i servizi del sistema operativo. È eseguita dal kernel; il programma passa dalla modalità utente alla modalità kernel con un interrupt software (trap) e ritorna con il risultato.

II. Processi e thread

Processi - stati, PCB, creazione con fork ed exec

Definizione (processo). Un processo (process) è un programma in esecuzione. Il programma è un'entità passiva (il file eseguibile sul disco); il processo è un'entità attiva, che esiste quando l'eseguibile viene caricato in memoria. Un programma può generare più processi (più utenti che lanciano lo stesso editor).

Definizione (cambio di contesto). Il contesto di un processo è rappresentato nel suo PCB. Un context switch (cambio di contesto) avviene quando la CPU passa da un processo all'altro: il sistema salva lo stato del processo uscente nel suo PCB e carica lo stato salvato del processo entrante.

Definizione (pipe). Una pipe è un canale che permette a due processi di comunicare. Le pipe ordinarie (anonime) sono unidirezionali (un'estremità per scrivere, una per leggere) e richiedono un legame padre-figlio: non si possono usare da fuori del processo che le ha create. Le named pipe (o FIFO) usano un file speciale, sono bidirezionali, non richiedono parentela e possono servire più processi (su UNIX e Windows; mkfifo).

Thread e concorrenza - modelli, Pthreads e goroutine

Definizione (thread). Un thread è l'unità di utilizzo della CPU: ha un identificatore, un program counter, un insieme di registri e uno stack propri, e condivide con gli altri thread dello stesso processo il codice, i dati globali, l'heap e le risorse del sistema operativo (come i file aperti).

Teorema (legge di Amdahl). Se una frazione $S$ del programma è seriale (non parallelizzabile) e il sistema ha $N$ core, lo speedup massimo è $$\text{speedup} \le \frac{1}{S + \dfrac{1-S}{N}}$$

III. Scheduling della CPU

Scheduling della CPU - FCFS, SJF, priorità e round robin

Definizione (media esponenziale). Siano $t_n$ la lunghezza effettiva dell'$n$-esimo burst e $\tau_n$ la stima. La stima successiva è $$\tau_{n+1} = \alpha\, t_n + (1-\alpha)\,\tau_n, \qquad 0 \le \alpha \le 1.$$

Scheduling multiprocessore e real-time

Definizione (Rate Monotonic, RMS). Nello scheduling Rate Monotonic la priorità (fissa, con prelazione) è l'inverso del periodo: periodo più breve, priorità più alta.

Definizione (EDF). Nello scheduling Earliest Deadline First le priorità sono dinamiche: si esegue il compito con la scadenza più vicina. Vale anche per compiti non periodici. Le scadenze sono garantite finché l'utilizzo totale è inferiore al 100%.

IV. Sincronizzazione

Sincronizzazione - sezione critica, race condition e mutex

Definizione (race condition). Si ha una race condition (corsa critica) quando più processi o thread accedono agli stessi dati e il risultato dipende dall'ordine in cui le operazioni si intrecciano (interleaving).

Definizione (soluzione di Peterson, due processi). I processi condividono boolean flag[2] e int turn. flag[i] = true significa «$P_i$ vuole entrare»; turn dice a chi spetta se entrambi vogliono.

Definizione (spinlock). Un mutex che aspetta con un ciclo (busy waiting, attesa attiva) è detto spinlock: il thread resta in esecuzione senza fare lavoro utile. Pregio: leggero e adatto quando l'attesa prevista è molto breve (niente cambio di contesto). Difetto: spreca CPU se l'attesa è lunga.

Semafori, monitor e problemi classici di sincronizzazione

Definizione (semaforo). Un semaforo $S$ è una variabile intera che si può usare solo con due operazioni atomiche: wait(S) (storicamente $P$, "proberen") e signal(S) (storicamente $V$, "verhogen"; in POSIX sem_post).

Definizione (monitor). Un monitor è un tipo di dato astratto che incapsula dati condivisi e procedure per usarli; le variabili interne sono accessibili solo dal codice delle procedure, e solo un processo alla volta può essere attivo dentro il monitor. La mutua esclusione è garantita dalla costruzione.

V. Deadlock

Deadlock - condizioni, prevenzione, evitamento e rilevamento

Definizione (deadlock). Un insieme di processi è in deadlock (stallo, blocco critico) se ogni processo dell'insieme sta aspettando un evento (il rilascio di una risorsa) che può essere causato solo da un altro processo dello stesso insieme.

Definizione (grafo di allocazione delle risorse). È un grafo diretto con insieme di vertici $V = T \cup R$, dove $T = \{T_1, \dots, T_n\}$ sono i processi (nodi circolari) e $R = \{R_1, \dots, R_m\}$ i tipi di risorse (nodi rettangolari, con un punto per ogni istanza). Un arco di richiesta $T_i \to R_j$ dice che $T_i$ ha chiesto un'istanza di $R_j$ e la attende; un arco di assegnazione $R_j \to T_i$ dice che un'istanza di $R_j$ è assegnata a $T_i$.

Definizione (stato sicuro). Uno stato è sicuro se esiste una sequenza sicura $\langle T_1, \dots, T_n \rangle$ di tutti i processi tale che, per ogni $T_j$, le risorse che può ancora chiedere si possono soddisfare con le risorse disponibili ora più quelle possedute da tutti i $T_i$ con $i < j$.

VI. Gestione della memoria centrale

Memoria centrale - allocazione contigua, paginazione e segmentazione

Definizione (registri base e limite). Il registro base contiene il più piccolo indirizzo fisico legale del processo, il registro limite la dimensione dell'intervallo. L'accesso all'indirizzo $a$ è legale se $\text{base}\le a<\text{base}+\text{limite}$.

Definizione (indirizzo logico e fisico). L'indirizzo logico (o virtuale) è quello generato dalla CPU; l'indirizzo fisico è quello visto dall'unità di memoria. Coincidono con l'associazione in compilazione e in caricamento, differiscono con quella in esecuzione. L'insieme degli indirizzi logici di un programma è il suo spazio degli indirizzi logici, quello dei corrispondenti fisici è il suo spazio degli indirizzi fisici.

Definizione. La frammentazione interna è la memoria assegnata a un processo ma non usata, interna alla sua partizione (tipica delle partizioni fisse e della paginazione). La frammentazione esterna è la memoria libera totale sufficiente a una richiesta, ma divisa in buchi troppo piccoli, non contigui (tipica delle partizioni variabili).

Definizione (paginazione). La memoria fisica è divisa in blocchi di dimensione fissa chiamati frame (cornici), la memoria logica in blocchi della stessa dimensione chiamati pagine. Un processo di $N$ pagine, per girare, occupa $N$ frame liberi, ovunque si trovino: lo spazio fisico di un processo è non contiguo. La dimensione è una potenza di 2.

Definizione (TLB). Il TLB è una memoria associativa veloce che conserva le coppie (numero di pagina, numero di frame) usate di recente. La ricerca avviene in parallelo su tutte le righe. Se $p$ è nel TLB (TLB hit) si ottiene subito il frame; altrimenti (TLB miss) si legge la tabella in memoria e si carica la riga nel TLB, eventualmente sostituendone un'altra.

Definizione (hit ratio e EAT). Il hit ratio $h$ è la frazione di accessi in cui la pagina si trova nel TLB. Se un accesso alla memoria costa $t$, il tempo di accesso effettivo è

$$\text{EAT}=h\cdot t+(1-h)\cdot 2t.$$

Se si conta anche il tempo $\tau$ di ricerca nel TLB: $\text{EAT}=h\,(\tau+t)+(1-h)\,(\tau+2t)$.

Definizione (segmentazione). L'indirizzo logico è una coppia $\langle s, d\rangle$: numero di segmento e scostamento. La tabella dei segmenti ha per ogni segmento una base (indirizzo fisico dell'inizio) e un limite (lunghezza). Si controlla $d<\text{limite}_s$; se vale, l'indirizzo fisico è $\text{base}_s+d$; altrimenti c'è un trap (errore di segmentazione).

VII. Memoria virtuale

Memoria virtuale - paginazione su richiesta e sostituzione delle pagine

Definizione (memoria virtuale). La memoria virtuale è la separazione tra la memoria logica vista dall'utente e la memoria fisica: solo una parte delle pagine di un processo deve stare in RAM, il resto sta su disco. Lo spazio degli indirizzi virtuali (la visione logica di come il processo è in memoria) parte di solito da 0 ed è contiguo, e può essere molto più grande di quello fisico; la MMU lo mappa sulla RAM (e non solo: anche sul disco).

Definizione (demand paging). Invece di caricare l'intero processo, si caricano solo le pagine che servono, nel momento in cui il processo le riferisce.

Definizione (FIFO). Si sostituisce la pagina da più tempo in memoria (la prima caricata). Basta una coda.

Definizione (OPT). Si sostituisce la pagina che non sarà usata per il periodo più lungo. Ha il minimo numero di fault possibile.

Definizione (LRU). Si sostituisce la pagina non usata da più tempo: si usa il passato come stima del futuro.

Definizione (working set). Sia $\Delta$ la finestra del working set: gli ultimi $\Delta$ riferimenti. Il working set $WS$ è l'insieme delle pagine riferite in quella finestra: un'approssimazione della località. $WSS_i$ è la sua dimensione per il processo $P_i$.

VIII. Memoria di massa

Memoria di massa e scheduling del disco

Definizione (tempo di accesso e di I/O). Il tempo medio di accesso è $T_{\text{acc}}=T_{\text{seek}}+T_{\text{lat}}$, dove la latenza media è il tempo di mezza rotazione:

$$T_{\text{lat}}=\frac{0{,}5}{\text{RPM}/60}=\frac{30}{\text{RPM}}\ \text{s}.$$

Il tempo medio di I/O è $T_{I/O}=T_{\text{acc}}+T_{\text{trasf}}+T_{\text{ctrl}}$, con $T_{\text{trasf}}=\dfrac{\text{quantità da trasferire}}{\text{velocità di trasferimento}}$ e $T_{\text{ctrl}}$ l'overhead del controller.

Definizione (RAID). RAID (redundant array of inexpensive/independent disks) usa più dischi insieme per ottenere affidabilità tramite ridondanza e maggiore velocità con l'accesso in parallelo.

IX. File system

File system - interfaccia, directory e implementazione

Definizione (file). Un file è uno spazio di indirizzi logici contigui, il cui contenuto è deciso da chi lo crea: dati (numerici, caratteri, binari) o programmi. Il tipo si riconosce spesso dall'estensione, che di solito non è obbligatoria: UNIX usa invece un numero magico (magic number) all'inizio del file.

Definizione (directory). Una directory è un file speciale che contiene una raccolta di voci con le informazioni sui file. Le directory e i file risiedono su disco.

Definizione (hard link e link simbolico). Un hard link è un altro nome (una voce di directory) per lo stesso inode: ha la stessa identità del file, non si distingue dall'originale. Un link simbolico (symbolic link) è un file speciale che contiene il percorso di un altro file: un puntatore a un puntatore. In Linux: ln nome_file nome_link crea un hard link, ln -s nome_file nome_simbolico un link simbolico.

Definizione (schema combinato, inode UNIX). L'inode contiene 15 puntatori: i primi 12 diretti ai blocchi dati, il 13° punta a un blocco indiretto singolo (puntatori a blocchi dati), il 14° a un blocco indiretto doppio (puntatori a blocchi di puntatori), il 15° a un blocco indiretto triplo.

X. Input e output

Sistemi di I-O e memory-mapped I-O

Definizione (file mappato in memoria). È un modo di fare I/O che non richiede system call (tranne per l'inizializzazione): il file è mappato nello spazio di indirizzi del processo, in modo che a ogni indirizzo corrisponda una parola del file. Il file è accessibile come qualunque altro dato in memoria, con istruzioni di load e store, e permette anche la comunicazione fra processi tramite file.

XI. Sicurezza e tolleranza ai guasti

Sicurezza e protezione nei sistemi operativi

Definizione (buffer overflow). Secondo il glossario del NIST: una condizione, a un'interfaccia, in cui si può mettere in un buffer o in un'area di dati più input della capacità allocata, sovrascrivendo altre informazioni. Gli attaccanti la sfruttano per mandare in crash il sistema o per inserire codice costruito apposta che gli dia il controllo.

Definizione (crittografia). Metodo per limitare i possibili mittenti e destinatari dei messaggi: è lo strumento di sicurezza più generale. Si basa su chiavi segrete e consente di confermare la sorgente, di far ricevere il messaggio solo a certi destinatari, e di creare una relazione di fiducia tra mittente e destinatario.

Definizione (tolleranza ai guasti). La tolleranza ai guasti è la capacità di un sistema o componente di continuare a funzionare normalmente nonostante guasti hardware o software. Richiede in genere un certo grado di ridondanza, per aumentare l'affidabilità; ha un costo (economico o di prestazioni), e il grado va deciso in base a quanto è critica la risorsa.

XII. Sistemi embedded e real-time per l'IoT

Sistemi operativi embedded e real-time per l'IoT

Definizione (sistema embedded). Un sistema embedded è l'uso di elettronica e software dentro un prodotto che ha una funzione, o un insieme di funzioni, specifiche, a differenza di un calcolatore di uso generale. Equivale a qualunque dispositivo con un chip di calcolo che non è una workstation, un desktop o un portatile.

XIII. Programmazione di sistema e architetture di rete

Richiami di C per la programmazione di rete - memoria, puntatori, struct ed endianness

Definizione (network byte order). Tutti i campi numerici a più byte dei protocolli Internet (porte, lunghezze, indirizzi IPv4, campi di TCP, UDP, DNS) viaggiano in big endian, detto network byte order. Il formato della macchina è l'ordine host.

Modello ISO-OSI, data plane e control plane, architetture client-server e publish-subscribe

Definizione (PDU e SDU). La PDU (Protocol Data Unit) è l'unità di dati scambiata fra due entità dello stesso livello su sistemi diversi: intestazione del protocollo più dati. La SDU (Service Data Unit) è il blocco di dati che un livello riceve dal livello superiore, da trasportare così com'è. Vale PDU(n) = intestazione(n) + SDU(n) e la PDU del livello n diventa la SDU del livello n-1.

Definizione (SAP). Un SAP (Service Access Point) è il punto in cui un livello offre i suoi servizi al livello superiore: l'interfaccia logica fra due livelli adiacenti. Ogni SAP ha un indirizzo che dice a quale utente del servizio vanno consegnati i dati.

Definizione (data plane e control plane). Il data plane (piano dati, anche forwarding plane) è la parte che inoltra i pacchetti, uno per uno e alla velocità della linea, applicando regole già decise: consultare la tabella di inoltro, commutare, filtrare, tradurre indirizzi. Il control plane (piano di controllo) è la parte che decide quelle regole: costruire e aggiornare le tabelle di instradamento scambiando messaggi con gli altri nodi, scegliere i percorsi, gestire la QoS.

System call POSIX, file descriptor e API delle socket

Definizione (file descriptor). Un file descriptor è un piccolo intero non negativo che il kernel restituisce quando un processo apre una risorsa di I/O. Indicizza la tabella dei descrittori del processo, che punta alla risorsa aperta nel kernel. Vale per file normali, pipe, terminali e socket: tutti si leggono e si scrivono con le stesse read e write.

Definizione (socket). Un socket è un punto finale di comunicazione, identificato nel programma da un file descriptor. Un socket TCP o UDP è associato a un indirizzo locale (indirizzo IP + porta). Una connessione TCP è identificata dalla quaterna (IP locale, porta locale, IP remoto, porta remota).

XIV. Il protocollo HTTP

HTTP 0.9 e 1.0 - struttura dei messaggi, header e parsing

Definizione (Simple-Request e Simple-Response, RFC 1945 par. 4.1). Simple-Request = "GET" SP Request-URI CRLF; Simple-Response = [ Entity-Body ]. La richiesta è una sola riga; la risposta è soltanto il documento.

HTTP 1.1 - connessioni persistenti, Content-Length e chunked transfer encoding

Definizione (connessione persistente). In HTTP/1.1 la connessione resta aperta dopo la risposta e si riusa per le richieste successive, senza che il client lo chieda. Chi vuole chiuderla dopo il messaggio corrente lo dichiara con l'header Connection: close, nella richiesta (il server chiude dopo la risposta) o nella risposta (il server chiude e lo dice prima).

Definizione (chunked). Con Transfer-Encoding: chunked il corpo è inviato come una sequenza di chunk: ciascuno preceduto dalla propria lunghezza in esadecimale e terminato da CRLF. L'ultimo chunk ha lunghezza zero. Sintassi (RFC 9112 par. 7.1):

Caching, autenticazione, tipi MIME e URI in HTTP

Definizione (media type). tipo/sottotipo[; parametro=valore]. Il tipo indica la famiglia (text, image, audio, video, application, multipart), il sottotipo il formato preciso. I valori sono registrati presso IANA e non distinguono maiuscole e minuscole.

XV. Applicazioni web dinamiche e web service

Web service, XML, JSON, SOAP e REST

Definizione (web service). Un sistema software progettato per supportare l'interazione fra macchine attraverso una rete, in cui le richieste e le risposte sono messaggi in un formato standard, di solito trasportati da HTTP.

XVI. Servizi di supporto di Internet

DNS, proxy web, HTTP CONNECT e gateway applicativi

Definizione (proxy e gateway, RFC 9110 par. 3.7). Un intermediario è un nodo che sta fra client e server e inoltra i messaggi. Un proxy è un intermediario scelto dal client (configurato nel browser o nel sistema) che inoltra le richieste verso i server di origine. Un gateway, o reverse proxy, è un intermediario scelto dal server: per il client sembra il server di origine e inoltra le richieste ad altri sistemi.

Definizione (CONNECT). CONNECT host:porta HTTP/1.1: chiede al proxy di aprire una connessione TCP verso host:porta e, se ci riesce, di inoltrare senza interpretarli i byte in entrambe le direzioni finché una delle due parti chiude. Il request-target è in authority-form: solo host e porta, e la porta è obbligatoria.

XVIII. Servizi multimediali

Servizi multimediali e loro requisiti

Definizione (medium). Un medium (plurale media) è un mezzo per rappresentare, immagazzinare o trasportare informazione. Sono media il testo, i dati, il suono, l'immagine, il video. Multimedia indica un flusso di informazione rappresentato o trasportato da più media insieme; le comunicazioni multimediali sono la tecnologia per manipolare, trasmettere e controllare questi contenuti attraverso una rete.

Definizione. Nello streaming la fruizione del contenuto può iniziare prima di aver ricevuto tutto il file: i dati si trasmettono e si consumano man mano che vengono prodotti. Nel bulk transfer (trasferimento in blocco) i dati viaggiano in modo "atomico" e si possono usare solo a file completo.

XIX. Digitalizzazione dei segnali

Digitalizzazione dei segnali multimediali - campionamento, quantizzazione e binarizzazione

Definizione (campionamento). Si preleva il valore del segnale a intervalli regolari di durata $T_c$ (periodo di campionamento): $s_c(n)=s(nT_c)$, $n\in\mathbb Z$. La frequenza di campionamento è $F_c=\frac1{T_c}$.

Teorema del campionamento di Shannon. Un segnale $s(t)$ a banda limitata con frequenza massima $f_M$ può essere ricostruito con errore nullo dalla successione dei campioni $s_c(n)=s(nT_c)$ se e soltanto se la frequenza di campionamento è almeno il doppio della frequenza massima: $$\boxed{F_c\ge2f_M}\qquad\text{(criterio di Nyquist).}$$ Quando vale, la formula di interpolazione ideale restituisce il segnale: $$s(t)=\sum_{n\in\mathbb Z}s(nT_c)\,\mathrm{sinc}\!\left(\frac{t-nT_c}{T_c}\right).$$

Definizione (aliasing). L'aliasing è lo spostamento in frequenza di un segnale ricostruito da campioni presi con $F_c$ che non rispetta il criterio di Nyquist: componenti ad alta frequenza si presentano, dopo la ricostruzione, come componenti a frequenza più bassa.

XXII. Codifica lossless

Codifica lossless - entropia, Huffman e codifiche a dizionario

Definizione (codice). Un codice $C$ è una mappa dall'alfabeto all'insieme delle stringhe di bit di lunghezza finita: $C:x_i\mapsto c_i\in\{0,1\}^*$. Le stringhe $c_i$ sono le codeword, di lunghezza $\ell_i$. Nei codici a lunghezza fissa tutte le codeword hanno la stessa lunghezza; altrimenti il codice è a lunghezza variabile. La lunghezza media è $$\mathcal L=\sum_{i=1}^Mp_i\,\ell_i\quad\text{(bit per simbolo)}.$$

Teorema di Shannon sulla codifica di sorgente. La lunghezza media $\mathcal L^*$ del codice istantaneo ottimo per una sorgente $X$ soddisfa $$H(X)\le\mathcal L^*<H(X)+1,$$ e l'uguaglianza a sinistra vale se e solo se tutte le probabilità sono potenze intere negative di due (distribuzione diadica).

XXV. Metriche e prestazioni di rete

Metriche e prestazioni di rete per i servizi multimediali

Definizione (BDP). Numero di bit (o pacchetti) che possono essere contemporaneamente "in transito" nella connessione: anche il numero di bit ricevuti (a regime) in un tempo pari al RTT. $$\mathrm{BDP}_{\text{bit}}=S\cdot\mathrm{RTT},\qquad\mathrm{BDP}_{\text{pkt}}=\frac{\mathrm{BDP}_{\text{bit}}}{|\mathrm{PDU}|}.$$

XXVII. QoS e QoE

Qualità del servizio (QoS) e qualità dell'esperienza (QoE)

Definizione (QoS, ITU-T E.800, 2008). La QoS è l'insieme delle caratteristiche di un servizio di telecomunicazioni che influiscono sulla sua capacità di soddisfare le esigenze dichiarate e implicite dell'utente del servizio.

Definizione (QoE). La QoE è la qualità del servizio percepita dall'utente. La definizione ufficiale (Qualinet): "il grado di gradimento o fastidio dell'utente di un'applicazione o servizio".

XXVIII. Streaming adattativo e DASH

Streaming adattativo e DASH

Definizione. $B(t)$ è il numero di secondi di video ricevuti ma non ancora riprodotti all'istante $t$. Si misura in secondi di video, non in bit o byte. È l'autonomia del player: se la rete "muore" all'istante $t$, il video continua per esattamente $B(t)$ secondi. Quando $B(t)=0$ la riproduzione si ferma: freezing, stallo o rebuffering.