Riassunto esame Sistemi Operativi

ESPRESSIONI ARITMETICHE

Per esprimere espressioni aritmetiche è possibile utilizzare diverse notazioni:

• il comando let
• le doppie parentesi tonde (( ... ))
• le parentesi quadre [ ... ]
• il costrutto expr

COSTRUTTO CONDIZIONALE IF-THEN-FI © BCPTe

Verifica se lo stato di uscita (exit status) di una sequenza di comandi è uguale a 0; in caso affermativo esegue uno o più comandi.

Il costrutto può essere esteso:

• per includere la condizione else if-then-else-fi
• per effettuare controlli annidati if-then-elif-then-else-fi ecc.

COSTRUTTO ITERATIVO FOR-IN

Esegue i comandi specificati, una volta per ogni valore assunto dalla variabile var. L'elenco dei valori [list] può essere indicato:

• in maniera esplicita (elenco)
• in maniera implicita (comandi di shell, wild-cards, ecc.)

Syntax 1:

for var in [list]
do
  statements
done

Syntax 2:

for var in [list]; do
  statements
done © BCPTe

COSTRUTTO ITERATIVO WHILE-DO-DONE

Si itera fino a quando la condizione è vera.

I costrutti break e continue hanno comportamenti standard con i cicli for e while:

• uscita non strutturata dal ciclo
• passaggio all'iterazione successiva

Il carattere : può essere utilizzato per creare "istruzioni nulle". Esempio:

In bash è possibile utilizzare variabili vettoriali mono-dimensionali. Ogni variabile può essere definita come vettoriale (non necessaria ma comunque possibile la dichiarazione esplicita con declare).

Non esiste limite alla dimensione di un vettore.

Definizione:

• elemento per elemento: name[index]="value"
• tramite elenco di valori: name=(lista valori separati da spazio)

Riferimento:

• al singolo elemento: ${name[index]}
• a tutti gli elementi: ${name[*]}

Numero di elementi: ${#name[*]}

Lunghezza dell'elemento index (numero caratteri): ${#name[index]}

Eliminazione:

<p>© BCPT</p>
<p>edi un singolo elemento: unset name[index]</p>
<p>di un intero vettore: unset name</p>

<h3>SINCRONIZZAZIONE</h3>
<h4>LIFO - STACK</h4>
<pre>
void push (int val) {
    if(top >= SIZE)
        return;
    stack[top] = val;
    top--;
}

void pop (int *val) {
    if(top <= 0)
        return;
    *val = stack[top];
    top++;
}
</pre>

<p>le funzioni push e pop agiscono sulla stessa estremità dello stack</p>
<p>la variabile top è condivisa</p>

<h4>FIFO - QUEUE - BUFFER CIRCOLARE</h4>
<pre>
void enqueue (int val) {
    if (n >= SIZE)
        return;
    queue[tail] = val;
    tail = (tail + 1) % SIZE;
    n++;
}

int dequeue (int *val) {
    if (n <= 0)
        return;
    *val = queue[head];
    head = (head + 1) % SIZE;
    n--;
}
</pre>

<p>le funzioni enqueue e dequeue agiscono su estremità "diverse" della cosa usando variabili diverse (head e tail)</p>
<p>la variabile n è comunque condivisa</p>

<h3>SEZIONI CRITICHE</h3>
<p>Una sezione critica (SC) o regione critica (RC) è una sezione di codice, comune a più processi o threads competono per l'uso (in lettura e scrittura) di risorse comuni (es. dati condivisi).</p>

<p>Le corse</p>

• non si avessero mai più P (o T) nella stessa SC contemporaneamente
• quando un P (o T) è in esecuzione nella sua SC nessun altro P (o T) potesse fare altrettanto
• il codice nella SC fosse eseguito da un singolo P (o T) alla volta
• l'esecuzione del codice nella SC fosse effettuata in mutua esclusione

• per entrare in una SC, un processo esegue codice di prenotazione
• per uscire da una SC, un processo esegue codice di rilascio della regione occupata

• una sezione di ingresso (di prenotazione o prologo)
• una sezione di uscita (di rilascio)

• mutua esclusione (ME) - un solo P (o T) alla volta deve ottenere l'accesso alla SC
• progresso - se nessun P (o T) si trova nella SC e un P (o T) desidera entrarci, deve poterlo fare
• non deadlock - se un P (o T) desidera entrare nella SC, alla fine deve riuscirci

fare in→un tempo definito (bisogna evitare deadlock tra P (o T))attesa definita deve esistere un numero definito di volte per cui altri P (o T) riescano ad→accedere alla SC prima che un P (o T) specifico e che ha fatto una richiesta di accesso possa farlo(bisogna evitare starvation di P (o T))simmetria la selezione di chi deve accedere alla SC non dovrebbe dipendere dalla priorità→relativa tra P (o T) o dalla velocità relativa tra P (o T)

Possiamo trovare diverse soluzioni a questo problema, di diversi tipi:

• software logica dell'algoritmo→
• hardware soluzioni architetturali→
• ad-hoc (semafori) l'OS fornisce strutture e funzioni per ovviare al problema→

SOLUZIONI SOFTWARE

Si basano sull'utilizzo di variabili globali.

SOLUZIONE 1

Variabili globali:

int flag[2] = {FALSE, FALSE};

P /T P /Ti i j j

------------------------ ------------------------

while (TRUE) {
    while (TRUE) {
        while (flag[j]);
        while (flag[i]);
        flag[i] = TRUE;
        flag[j] = TRUE;
        SC

SCflag[i] = FALSE; flag[j] = FALSE;
sezione non critica
sezione non critica
}
}

SOLUZIONE 2
Variabili globali:
int flag[2] = {FALSE, FALSE};

P /T P /Ti i j j
------------------------
while (TRUE) {
    while (TRUE) {
        flag[i] = TRUE;
        flag[j] = TRUE;
        while (flag[j]);
        while (flag[i]);
        SC
        flag[i] = FALSE;
        flag[j] = FALSE;
        sezione non critica
        sezione non critica
    }
}

SOLUZIONE 3
Variabili globali:
int turn = i;

P /T P /Ti i j j
------------------------
while (TRUE) {
    while (TRUE) {
        while (turn!=i);
        while (turn!=j);
        SC
        flag[i] = FALSE;
        flag[j] = FALSE;
        sezione non critica
        sezione non critica
    }
}

SCturn = j; turn = i;
sezione non critica sezione non critica
} }

In questo caso, si utilizza una sola variabile che indica "di chi è il turno" per eseguire la SC.
Con questa soluzione, l'attesa non è definita, in quanto se P non è interessato, P va in starvation (o viceversa).

SOLUZIONE 4

Variabili globali:
int turn = i;
int flag[2] = {FALSE, FALSE};

P /T P /T
i i i
------------------------
------------------------
while (TRUE) {
    while (TRUE) {
        flag[i] = TRUE;
        flag[j] = TRUE;
        turn = j;
        turn = i;
        while (flag[j] && while (flag[i] && turn==j);
        turn==i);
        SC
        SC
        flag[i] = FALSE;
        flag[j] = FALSE;
        sezione non critica sezione non critica
    }
}

© BCPTe

Questa soluzione è l'unica corretta, cioè l'unica che garantisce:
- mutua esclusione
- progresso (no deadlock)
- attesa limitata (no starvation)
- simmetria

In generale, le soluzioni software al problema delle SC risultano complesse e inefficienti.

SOLUZIONI HARDWARE

Possono essere divise

SISTEMI SENZA DIRITTO DI PRELAZIONE

È un sistema tale per cui:

• i P (o T) in esecuzione nella CPU non possono essere interrotti
• il controllo verrà rilasciato al kernel solo quando il P (o T) lo lascerà volontariamente

Nei sistemi mono-processore e senza diritto di prelazione non esiste il problema delle SC.

Nei sistemi multi-processore o multi-core, il fatto che il kernel sia senza diritto di prelazione implica tempi di risposta eccessivi e non adatti alla programmazione "real-time".

SISTEMI CON DIRITTO DI PRELAZIONE

In sistemi di questo tipo:

1. un processo in esecuzione in modalità kernel può essere interrotto
2. l'arrivo di un interrupt sposta il controllo del flusso su un altro processo
3. il processo originario verrà terminato in seguito

Nei sistemi mono-processore con diritto di prelazione, è possibile risolvere il problema

delle SC mediante controllo dell'interrupt (disable interrupt nella sezione d'ingresso, enable interrupt nella sezione d'uscita).

while (TRUE) {
    disabilita interrupt
    SC
    abilita l'interrupt
    sezione non critica
}

In generale, disabilitare gli interrupt ha però diversi svantaggi:

• la procedura è intrinsecamente insicura (in caso di errori, come si segnalano?)
• nei sistemi multi-processore (o multi-core) occorre disabilitare gli interrupt su tutti i processori

MECCANISMI DI LOCK - UNLOCK

Vengono utilizzati:

• © BCPTelucchetti di protezione (lock)
• istruzioni indivisibili (atomiche) per manipolare tali lock

Esistono 2 principali istruzioni atomiche di lock:

• Test-And-Set setta e restituisce una variabile di lock globale, agisce in maniera atomica (in un solo ciclo indivisibile)
• Swap scambia due variabili, di cui una di lock globale, agisce in maniera atomica (in un solo ciclo indivisibile)

Entrambe le tecniche precedenti:

• assicurano la mutua esclusione
• assicurano il progesso

semaforo S→destroy (S) cancella (libera/free) il semaforo S

S→FUNZIONE INIT

Esistono 2 tipi di semafori: