Riassunto esame Sistemi Operativi

Terminologia e concetti base

• Kernel
• Bootstrap
• System call
• Dual-mode
• Login
• Shell
• Filesystem
• Filename
• Pathname
• Home directory
• Root directory
• Working directory
• Programma
• Processo
• Thread
• Pipe
• Deadlock
• Livelock
• Starvation
• File
• Serializzazione
• I/O
• Direttori
• Directory a un livello
• Directory a due livelli
• Directory ad albero
• Directory a grafo aciclico
• Directory a grafo ciclico
• Allocazione
• Allocazione indicizzata - schema combinato
• Funzioni utili per direttori
• Comandi utili
• List
• Copy, remove, move
• Gestione permessi
• Visualizzazione testo
• Differenze
• Word count
• Link
• Gestione archivi
• Alternative a tar
• Occupazione spazio su disco
• Spell checker
• Strumenti per la programmazione C
• Compiler: GCC
• Compiler: makefile
• Debugger: GDB
• Espressioni regolari
• Letterale
• Metacarattere
• Sequenza di escape
• Comando find
• Filtri
• Cut © BCPTe
• TR
• UNIQ
• Basename
• Sort
• Grep
• Processi
• Processi sequenziali
• Processi concorrenti
• Caratteristiche
• Identificazione di un processo
• Creazione di un processo
• Risorse di un processo
• Terminazione di un processo
• Syscall wait
• Syscall waitpid
• Processi zombie
• Processi orfani
• Teoria aggiuntiva
• Stato di un processo
• Process control block (PCB)
• Context switching
• Scheduling dei processi
• Controllo avanzato
• Sostituzione di un processo
• Syscall exec
• Syscall execv[p]
• Syscall exec[lv]e
• Considerazioni
• Scheletro di una shell UNIX
• Esecuzione di un comando
• Syscall system
• Segnali
• Gestione dei segnali
• Syscall signal
• Syscall kill
• Syscall raise
• Syscall pause
• Syscall alarm
• Memoria limitata
• Funzioni rientranti
• Race conditions
• Comandi di shell per processi
• Comunicazione tra processi
• Modelli di comunicazione
• Canali di comunicazione
• Pipe
• Syscall pipe
• I/O su pipe
• Threads
• Modelli di programmazione multi-thread
• Kernel-level thread
• User-level thread
• Implementazione ibrida
• Coesistenza di processi e thread
• Utilizzo della syscall fork
• Utilizzo della syscall exec
• La libreria pthread © BCPTe
• Syscall pthread_equal
• Syscall pthread_self
• Syscall pthread_create
• Syscall pthread_exit
• Syscall pthread_join
• Syscall pthread_cancel
• Syscall pthread_detach
• Terminologia
• Concorrenza
• Parallelismo
• Shell
• Parentesi (), [], {}
• Quoting
• History
• Aliasing
• Script di shell
• Esecuzione diretta
• Esecuzione indiretta
• Debug di uno script
• Sintassi
• Parametri
• Variabili
• Variabili locali (o di shell)
• Variabili globali (o d'ambiente)
• Lettura (read)
• Scrittura (output)
• Espressioni aritmetiche
• Costrutto condizionale if-then-fi
• Costrutto iterativo for-in
• Costrutto iterativo while-do-done
• Break, continue e `:`
• Vettori
• Sincronizzazione
• LIFO - stack
• FIFO - queue - buffer circolare
• Sezioni critiche
• Soluzioni software
• Soluzione 1
• Soluzione 2
• Soluzione 3
• Soluzione 4
• Soluzioni hardware
• Sistemi senza diritto di prelazione
• Sistemi con diritto di prelazione
• Meccanismi di lock - unlock
• Soluzioni ad-hoc (semafori)
• Operazioni standard su semafori
• Funzione init
• Funzione wait
• Funzione signal
• Funzione destroy
• Implementazione di un semaforo
• Semafori tramite pipe
• Semaphoreinit (S)
• Semaphoresignal (S)
• Semaphorewait (S)
• Semafori POSIX
• Sem_wait © BCPTe
• Sem_trywait
• Sem_post
• Sem_getvalue
• Sem_destroy
• Semafori mutex pthread
• Pthread_mutex_init
• Pthread_mutex_lock
• Pthread_mutex_trylock
• Pthread_mutex_unlock
• Pthread_mutex_destroy
• Scheduling CPU
• Algoritmi
• Algoritmi senza prelazione
• FCFS (first-come first-served)
• SJF (shortest-job first)
• PS (priority scheduling)
• RR (round robin)
• SRTF (shortest-remaining-time first)
• MQS (multilevel queue scheduling)
• Considerazioni aggiuntive
• Scheduling dei thread
• Scheduling per sistemi multiprocessore
• Scheduling per sistemi real-time
• Funzioni di costo

Terminologia e concetti base

Kernel

Si tratta della parte centrale dell'OS. Il compito principale è quello di gestire memoria e processori. Esistono diversi tipi di kernel:

• A livelli o stratificati costituiti da diversi livelli, il più basso è l'HW.
• Micro-kernel forniscono solo funzionalità di base.
• Kernel monolitici utilizzo di driver dispositivi (più comuni).

Bootstrap

Programma di inizializzazione. Si occupa di caricare il kernel in memoria centrale all'accensione del computer, e successivamente lo esegue. Il programma di bootstrap si trova solitamente in ROM o EEPROM.

System call

Forniscono l'interfaccia ai servizi forniti dall'OS (entry-point dell'OS). Offrono solitamente funzionalità "di base" e non possono essere modificate.

Dual-mode

L'OS lavora in dual-mode, cioè permette una user mode che non possiede tutti i privilegi, complementare alla kernel mode che invece possiede privilegi amministrativi. Il dual-mode assicura che lo user NON possa assumere il controllo del computer in kernel mode. © BCPTe

Login

Si tratta della procedura di accesso/autenticazione a un sistema o a una sua applicazione. Solitamente occorre fornire username e password.

Shell

Non fa parte dell'OS. Legge i comandi utente e li esegue. Può eseguire:

• Comandi da terminale.
• Comandi da file eseguibili (script).

Filesystem

Struttura gerarchica a grafo aciclico in cui sono organizzati:

• Direttori (directory).
• File.

Filename

Nome dei file. In UNIX gli unici caratteri non utilizzabili in un filename sono:

• Lo slash "/".
• Il carattere "null".

Pathname

Sequenza di nomi separati da slash "/". Possono essere specificati in maniera:

• Assoluta.
• Relativa.

Caratteri particolari:

• "." indica la directory corrente.
• ".." indica la directory padre.

Home directory

Directory a cui si accede dopo il login. Contiene il materiale dello user loggato.

Root directory

Directory principale. È la radice dell'albero directory, si tratta del punto di origine per interpretare i path assoluti.

Working directory

È il punto di origine per interpretare i path relativi. Ci si riferisce automaticamente qualora non si specifichi un path.

Programma

© BCPTe File eseguibile che risiede su disco. Specifica una serie di operazioni per realizzare un procedimento definito (algoritmo). Un'operazione si dice atomica se nessun processore può interromperla. I programmi sono divisi in:

• Programma sequenziale → operazioni da eseguire in sequenza (ogni nuova istruzione inizia al termine della precedente).
• Programma concorrente o parallelo → individua operazioni che possono procedere in parallelo (ogni operazione può essere eseguita senza attendere il completamento della precedente).

Processo

Si tratta di un programma in esecuzione. È un'entità attiva.

Thread

Un processo può avere al suo interno uno o più flussi di controllo in esecuzione. Ciascun flusso di esecuzione è un thread.

Pipe

Una pipe è un flusso dati tra due processi.

Deadlock

Un insieme di entità attendono il verificarsi di un evento che può essere causato solo da un'altra entità dell'insieme.

Livelock

Situazione simile al deadlock in cui le entità non sono effettivamente bloccate ma non fanno alcun progresso (quello che solitamente definiamo loop infinito).

Starvation

A un'entità viene ripetutamente rifiutato l'accesso a una risorsa necessaria al suo progresso.

N.B.:

• Starvation NON IMPLICA deadlock.
• Deadlock IMPLICA starvation.

File

Dal punto di vista logico un file può essere visto come:

• Insieme di informazioni correlate.
• Uno spazio di indirizzamento contiguo.

Normalmente i file si distinguono in:

• File di testo (o ASCII).

Vantaggi:

• Portabilità © BCPTe.
• Possibilità di utilizzare editor standard.

Svantaggi:

• Dimensione media relativamente alta.

• File binari.

Vantaggi:

• Minore dimensione media (compattezza).
• Facilità di posizionarsi e modificare il file.

Svantaggi:

• Portabilità limitata.
• Impossibilità di utilizzare editor standard.

Serializzazione

Si tratta di un processo di traduzione di una struttura in un formato memorizzabile. Utilizzando la serializzazione la struttura può essere memorizzata o trasmessa come un'unica entità. La lettura della sequenza si fa in accordo con la serializzazione effettuata così da poter ricostruire la struttura in maniera identica a quella di partenza.

I/O

L'I/O ANSI C può avvenire in diversi modi:

• Un carattere alla volta → getchar(), putchar().
• Una riga alla volta → gets(), puts().
• I/O formattato → printf(), scanf().
• R/W diretto → fread(), fwrite().

L'I/O UNIX si può effettuare interamente mediante solo 5 funzioni:

• Open() apre un file dato il path, definendone modalità di accesso e permessi.
• Read() legge dal file fd un numero di bytes pari a nbytes, memorizzandoli in buf.
• Write() scrive nbytes byte contenuti in buf nel file descrittore fd.
• Lseek() ogni file ha associata una posizione corrente del file offset. La funzione lseek() assegna un nuovo valore (offset) al file offset.
• Close() chiude il file descrittore fd.

© BCPTe

Direttori

I file sono organizzati in direttori. Un direttorio è un nodo (o vertice) contenente informazioni sugli elementi in esso contenuti. Su un direttorio si possono effettuare operazioni simili a quelle effettuabili sui file (creazione, cancellazione, ricerca, ecc.).

La struttura di un direttorio dipende da ragioni di:

• Efficiency (efficienza) → es. velocità nel localizzare un file.
• Naming (convenienza) → es. evitare che lo stesso nome attribuito a più file crei problemi.
• Grouping (organizzazione) → es. raggruppare le informazioni in base alle relative caratteristiche.

Directory a un livello

I file sono contenuti all'interno dello stesso (unico) direttorio.

In termini di prestazioni, con questa organizzazione:

Efficiency

• Struttura facilmente comprensibile e gestibile.
• Gestione del file system semplice ed efficiente.

Naming

• I file devono avere nomi univoci (problema con grandi quantità di file).

Grouping

• Complessa gestione dei file di un singolo utente.
• Impossibilità di gestire utenti multipli.

Directory a due livelli

Ogni utente può avere il proprio direttorio (a un livello).

Prestazioni in questo caso:

Efficiency

• Visione del file system user-oriented.
• Ricerche efficienti agendo su singoli utenti.

Naming

• Possibilità di avere file con lo stesso nome purché appartenenti a diversi utenti (specificare path-name per ogni file).

Grouping

• Semplificato tra diversi utenti.
• Complesso per ciascun utente.

Directory ad albero

I file sono contenuti in un albero. Ogni utente può gestire più directory e subdirectory.

Prestazioni con questa organizzazione:

Efficiency

• Ricerche vincolate alla struttura ad albero (quindi profondità e ampiezza).

Naming © BCPTe

• Permesso in maniera estesa.

Grouping

• Permesso in maniera estesa.

Directory a grafo aciclico

Si inizia ad intravedere il concetto di link, cioè la possibilità di riferirsi allo stesso file con due nomi diversi o in due directory diverse. In particolare, così è possibile la condivisione di informazioni tra utenti diversi. La presenza di link aumenta la difficoltà di gestione del file system in quanto occorrerà distinguere gli oggetti nativi dai relativi collegamenti, in fase di creazione, manipolazione e cancellazione.

Directory a grafo ciclico

A differenza delle directory a grafo aciclico, in questo caso viene permessa la creazione di cicli. È importante gestire opportunamente i cicli esistenti in tutte le fasi.

Allocazione

Con allocazione si intendono tutte le tecniche di utilizzo dei blocchi dei dischi per la memorizzazione di file. Esistono 3 tecniche principali:

• Contigua (contiguous) → ogni file occupa un insieme contiguo di blocchi.

Vantaggi:

• Strategia di allocazione molto semplice.
• Permette accessi sequenziali immediati.
• Permette accessi diretti semplici.

Svantaggi:

• Occorre decidere una politica di allocazione (first-fit, best-fit, ecc.).
• Nessun algoritmo di allocazione risulta privo di difetti, quindi la tecnica sprecherà spazio (frammentazione esterna).
• Problemi di allocazione dinamica (se il file cresce, potrebbe non entrare più nello spazio allocato).

• Concatenata (linked) → ogni file può essere allocato gestendo una lista concatenata di blocchi.

Vantaggi:

• Permette allocazione dinamica.
• Elimina frammentazione esterna.
• Evita l'utilizzo di algoritmi di allocazione complessi.

Svantaggi:

• Ogni lettura implica un accesso sequenziale ai blocchi.
• Un accesso diretto richiederebbe percorrere la catena di puntatori fino a raggiungere l'indirizzo desiderato.

• Indicizzata (indexed) → per permettere un accesso diretto è possibile inglobare tutti i puntatori in una tabella di puntatori (blocco indice o index-node o i-node). Ogni file ha la sua tabella, ovvero un vettore di indirizzi dei blocchi in cui il file è contenuto.

Allocazione indicizzata - schema combinato

© BCPTe Lo schema combinato è utilizzato nei sistemi UNIX/Linux. A ogni file è associato un blocco i-node contenente diverse informazioni, tra cui 15 puntatori ai blocchi dati del file. In particolare:

• I primi 12 puntatori sono diretti, ovvero puntano a blocchi dei file.
• I puntatori 13, 14, 15 sono indiretti con livello di indirizzamento crescente (puntatori a puntatori nel blocco individuato dal puntatore 13, o ancora puntatori a puntatori a puntatori nel blocco individuato dal puntatore 14, ecc.).

In questa configurazione, abbiamo:

• Hard link → link effettivo o fisico (attenzione: se modifico l'hard link, modifico anche il file nativo).
• Soft-link → link simbolico, si tratta di un file contenente nel suo i-node il riferimento al file nativo.

Funzioni utili per direttori

• Stat → permette di capire di che tipo di "entry" si tratta (directory, file, link, ecc.).
• Getcwd, chdir → ottiene/modifica il path della working directory.
• Mkdir, rmdir → crea/cancella una directory.
• Opendir, readdir, closedir → funzioni di visita.

Comandi utili

List

ls [ opzioni ] [ file... ]

Opzioni:

Copy, remove, move

cp [ opzioni ] src1 src2 ... dest

rm [ opzioni ] src1 src2 ...

mv [ opzioni ] src1 src2 ... dest

Opzioni: © BCPTe

Gestione permessi

chmod [ opzioni ] permessi file

Opzioni:

Visualizzazione testo

cat file1 file2 ...

head [ opzioni ] file ...

tail [ opzioni ] file

Opzioni:

Altri comandi di visualizzazione:

pg [ opzioni ] file

more [ opzioni ] file

less [ opzioni ] file

Opzioni: © BCPTe

Differenze

diff [ opzioni ] entry1 entry2

Opzioni:

Word count

wc [ opzioni ] [ file ]

Opzioni:

Link

ln [ opzioni ] source [ destination ]

Opzioni: © BCPTe

Gestione archivi

Archiviazione e compressione del direttorio dir:

tar -czvf < file >.tgz < dir >

Estrazione del c