Sistemi Operativi IV · Appunti Universitari

01 Jul 2004

Riassunto gerarchico delle nozioni del corso 2003-2004 di Sistemi Operativi del Prof. Francesco Aymerich - Università degli Studi di Cagliari, Facoltà di Scienze Matematiche Fisiche Naturali, Dipartimento di Matematica ed Informatica, Corso di Laurea in Informatica

Il nucleo del sistema operativo
- il nostro sistema operativo ipotetico assomiglierà ad una cipolla nella quale ogni strato fornisce un insieme di funzioni che dipendono esclusivamente dagli strati più interni.
  - Al centro della cipolla si trovano le risorse fornite dall'hardware della macchina stessa.
  - Gli altri strati possono essere considerati come se implementassero macchine virtuali successive, cosicché la cipolla nel suo complesso rappresenterà la macchina virtuale richiesta dall'utente.
- L'interfaccia principale tra l'hardware di base della macchina ed il sistema operativo è fornita dal nucleo (kernel) del sistema, che rappresenta lo strato più interno della cipolla.
- Lo scopo del nucleo è quello di fornire un ambiente nel quale possano esistere i processi;
  - ciò comporta la gestione degli interrupt, la commutazione di processori tra i processi e l'implementazione dei meccanismi per la comunicazione tra i processi.
Risorse hardware essenziali per un Sistema Operativo
- Meccanismo degli interrupt
  - l'elaboratore deve fornire un meccanismo di interruzione che, per lo meno, salvi il valore del program counter per il processo interrotto e trasferisca il controllo ad una locazione fissa di memoria. Quest'ultima verrà utilizzata come punto di partenza per un (segmento di) programma che va sotto il nome di interrupt routine o di interrupt handler (gestore degli interrupt), il cui scopo consiste nell'individuare la fonte dell'interrupt e nel rispondervi in modo idoneo.
  - In un elaboratore che non implementa un meccanismo esplicito di gestione degli interrupt, uno o più processori devono essere dedicati alla supervisione dello stato dei dispositivi di I/O per rilevare il completamento dei trasferimenti.
    - Per esempio nel CYBER tale funzione è svolta da un certo numero di cosiddetti "processori periferici", che sgravano così la CPU da tutta la gestione dell'I/O.
    - Esiste comunque, anche in questo caso, una forma ristretta di interrupt, poiché i processori periferici possono costringere la CPU a saltare ad una locazione diversa.
- Protezione della memoria
  - Consente di proteggere la parte di memoria utilizzata da un processo contro l'accesso non consentito ad opera di un altro processo.
  - I meccanismi di protezione che devono essere inclusi nell'hardware di indirizzamento della memoria sono oggetto di descrizione particolareggiata nel prossimo capitolo; per il momento daremo per scontata la loro esistenza.
- Set di istruzioni privilegiate
  - è un insieme di istruzioni riservate all'uso esclusivo da parte del sistema operativo.
    - consentono di rendere impossibili le interferenze reciproche di processi concorrenti
  - Queste istruzioni privilegiate svolgono funzioni quali:
    - a) abilitazione e disabilitazione degli interrupt;
    - b) commutazione di un processore tra processi;
    - c) accesso ai registri utilizzati dall'hardware di protezione della memoria;
    - d) esecuzione dell'input o dell'output;
    - e) arresto del processore centrale.
  - La maggioranza degli elaboratori opera in due modi, di solito denominati modo privilegiato (supervisor mode) e modo utente o non privilegiato (user mode).
    - Le istruzioni privilegiate sono permesse solamente nel modo privilegiato.
  - Il passaggio dal modo utente al modo privilegiato ha luogo automaticamente al verificarsi di una delle seguenti situazioni:
    - 1. un processo utente richiama il sistema operativo per eseguire una qualche funzione che richieda l'impiego di un'istruzione privilegiata;
      - tale richiamo viene definito extracode o supervisor call;
    - 2. si verifica un interrupt;
    - 3. si verifica una condizione d'errore all'interno di un processo utente.
      - La situazione può essere considerata come un "interrupt interno" ed essere gestita in primo luogo da una routine per la gestione degli interrupt;
    - 4. viene fatto un tentativo di eseguire un'istruzione privilegiata mentre ci si trova nel modo non privilegiato.
      - Il tentativo può essere visto come un tipo particolare di errore e gestito come nel precedente punto.
  - Il ritorno dal modo privilegiato a quello non privilegiato viene effettuato tramite un'istruzione, privilegiata essa stessa.
  - alcuni elaboratori (per esempio l'ICL 2900, il CYBER 180 e l'Honeywell 645) includono livelli multipli di privilegio.
- Orologio in tempo reale
  - Per mettere in atto i meccanismi di schedulazione e per addebitare le risorse utilizzate dai vari utenti è fondamentale che l'hardware includa un orologio il quale provveda ad eseguire degli interrupt ad intervalli prefissati di tempo reale
    - di tempo, quindi, misurato nel mondo esterno e distinto da quello richiesto dalle attività di calcolo messe in atto da un qualsiasi processo particolare
Presupposti di partenza
- ogni processore presente nella macchina sulla quale è in corso di costruzione il nostro sistema operativo ipotetico possiede
  - Meccanismo degli interrupt
  - Protezione della memoria
  - Set di istruzioni privilegiate
- esiste un unico orologio in grado di intervenire in tempo reale per interrompere i processi stessi.
- Per di più, ci limiteremo alle configurazioni strettamente accoppiate, nelle quali i processori sono identici e condividono una memoria comune.
  - si esclude di prendere in considerazione le reti di calcolo, in cui i processori hanno memorie distinte e comunicano tramite un qualche tipo di trasmissione dei dati, nonché i sistemi dove processori differenti sono organizzati così da suddividersi un certo carico di lavoro nel modo che più si confà alle loro caratteristiche specifiche.
Sistema Operativo ipotetico
- hardware - livello più basso
- istruzioni privilegiate relative alla protezione della memoria e l'I/O
- il nucleo del sistema operativo
  - 1. il first-level interrupt handler (gestore degli interrupt di primo livello)
    - svolge la funzione di gestire inizialmente tutti gli interrupt
  - 2. il (dispatcher (routine di smistamento)
    - distribuisce i processori centrali tra i processi;
  - 3. due procedure (routine) che implementano le primitive riguardanti la comunicazione tra processi (wait e signal )
    - queste procedure vengono richiamate tramite supervisor call nei processi interessati.
Descrizione del nucleo
- è quella parte del sistema operativo più pesantemente dipendente dalla macchina.
  - si tratta probabilmente dell'unica parte del sistema operativo che necessita di essere scritta sostanzialmente in linguaggio Assembler;
  - a parte poche eccezioni di scarso rilievo, prevalentemente riferite all'I/O, per gli altri strati è più conveniente la codifica per mezzo di un linguaggio ad alto livello.
- I linguaggi più idonei alla programmazione dei sistemi sono
  - RCPI (Richards, 1969)
  - BLISS (Wulfetal., 1971)
  - C (Kernighan e Ritchie, 1978).
- Vi sono altri linguaggi, quali il Concurrent Pascal (Hansen, 1975) ed il Modula (Wirth, 1977 e 1983), che sono intesi specificamente per la stesura dei sistemi operativi, benché impongano certe limitazioni al progettista di sistemi.
- Il fatto che il linguaggio assembler sia limitato ad una piccola parte (presumibilmente non oltre le 400 istruzioni) del sistema operativo, cosa resa possibile dalla struttura gerarchica del sistema, può contribuire in modo determinante a realizzare un prodotto senza errori, comprensibile e di facile manutenzione
Rappresentazione dei processi
- descrittore di processo (blocco di controllo o vettore di stato)
  - struttura dati che rappresenta un processo
  - è una zona di memoria contenente tutte le informazioni importanti riguardanti il processo stesso
    - identificatore del processo (il nome del processo)
    - indicazione del suo stato
    - ambiente volatile del processo (context block o process state)
      - è dato da tutte le informazioni concernenti il processo che bisogna salvare quando quest'ultimo perde il controllo di un processore
      - è quel sottoinsieme di risorse di sistema, condivisi e modificabili a cui il processo stesso può avere accesso
      - comprende
        
        i valori di tutti i registri di macchina
        
        contatore di programma
        
        accumulatori
        
        registri indice
        
        i valori di eventuali registri usati per l'indirizzamento della memoria che fa capo al processo (si veda il capitolo 5)
        
        il puntatore allo stack
        
        lo stato dei file aperti
        
        il tempo di CPU utilizzato
        
        le informazioni di scheduling
    - altre informazioni
  - Il descrittore di ciascun processo viene inserito in una lista dei processi che contiene una descrizione di tutti i processi esistenti all'interno del sistema
- Un processo può trovarsi in uno dei tre seguenti stati principali:
  - 1) in esecuzione
    - quando ha a disposizione un processore;
  - 2) in attesa di esecuzione (in stato di pronto)
    - stato da cui potrebbe evolves se gli venisse dedicato un processore;
  - 3) in attesa di eventi (non eseguibile)
    - impossibilitato a fare uso di un processore anche se quest'ultimo gli fosse dedicato.
- Il motivo più comune per cui un processo non è eseguibile è che si trovi in attesa del completamento di un trasferimento tra periferiche.
- Lo stato di un processo è un'informazione essenziale per la routine di smistamento, quando quest'ultima arriva al punto di allocare un determinato processore centrale.
- Processo corrente
  - è un processo in corso di esecuzione su un processore centrale
  - il numero dei processi correnti all'interno del sistema in ogni dato momento è minore o uguale al numero dei processori disponibili
- Lista dei processi
  - Per il momento adotteremo un modello elementare di lista dei processi, nel quale i descrittori sono collegati tramite una lista semplice.
- Tabella centrale
  - consente l'accesso a tutte le strutture di sistema.
    - la prima, ma non sarà l'unica, è la lista dei processi
  - La tabella centrale conterrà un puntatore per ciascuna struttura dati e potrà anche essere impiegata per conservare altre informazioni globali, quali la data, l'ora ed il numero della versione del sistema, che potrebbero essere richieste di tanto in tanto.
- Tabella dei processi
  - In molti sistemi operativi la gestione dei processi, della memoria e dei file è realizzata separatamente da moduli diversi all'interno del sistema; di conseguenza la tabella dei processi è partizionata, e ogni modulo gestisce i campi di sua pertinenza.
  - Un esempio può essere il seguente
    - Gestione dei processi (modulo)
      - Registri
      - Program counter
      - Parola di stato del programma - PSW
      - Stack pointer
      - Stato del processo
      - Priorità
      - Parametri di schedulazione
      - ID del processo
      - Processo genitore
      - Gruppo del processo
      - Segnali
      - Tempo al quale è stato fatto partire il processo
      - Tempo di CPU usato
      - Tempo di CPU dei figli
      - Tempo del prossimo allarme
    - Gestione della memoria (modulo)
      - Puntatore al segmento del codice
      - Puntatore al segmento dei dati
      - Puntatore al segmento dello stack
    - Gestione dei file (modulo)
      - Directory radice
      - Directory di lavoro
      - Identificatore dell'utente - UID
      - Identificatore del gruppo - GID
I thread o processi lightweight
- In un tradizionale modello a processi c'è una singola sequenza di controllo e un solo program counter per ogni processo.
- alcuni moderni sistemi operativi, forniscono il supporto per definire sequenze di controllo multiple all'interno di un processo, i thread.
- Esempio di 3 thread
  - nel caso tradizionale
    - Ogni processo ha il suo spazio di indirizzamento e una sola sequenza di controllo
  - nel caso moderno
    - si ha un solo processo con tre sequenze di controllo.
    - tutti e tre condividono lo stesso spazio di indirizzamento.
- Esempi di come possano utilizzare i thread
  - File server
    - un processo file server riceve richieste di lettura e scrittura sui file e rimanda indietro i dati richiesti o accetta i dati aggiornati.
    - Per migliorare le prestazioni, il server gestisce in memoria una cache dei file usati più di recente, leggendo da e scrivendo sulla cache per quanto possibile.
    - Quando arriva una richiesta viene passata a un thread che la elabora, mentre gli altri thread restano a disposizione, in modo che il server possa continuare a soddisfare le nuove richieste anche mentre sta eseguendo un I/O da disco.
    - è essenziale che tutti i thread del file server accedano alla stessa cache in memoria e possono farlo solo se condividono lo stesso spazio di indirizzamento
  - Browser Web
    - Molte pagine Web contengono un buon numero di piccole immagini.
    - Per ogni immagine contenuta in una pagina Web il browser deve stabilire una diversa connessione verso il sito relativo alla pagina e richiedere quindi l'immagine.
    - Una gran quantità di tempo viene persa per aprire e chiudere tutte queste connessioni.
    - Se il browser comprende più thread è possibile richiedere molte immagini allo stesso tempo, migliorando sostanzialmente le prestazioni nella maggior parte dei casi, visto che, nel caso di immagini piccole, il fattore dominante diventa il tempo necessario allo stabilirsi della connessione e non la velocità della linea di trasmissione.
- La tabella dei processi
  - Quando vi sono più thread nello stesso spazio di indirizzamento, alcuni dei campi della tabella non sono relativi al processo, ma al thread, e impongono quindi la presenza di una separata tabella dei thread.
- La tabella per i thread
  - ha una voce per ogni thread.
  - Tra le informazioni necessarie a ogni thread vi sono:
    - program counter
      - è necessario in quanto i thread, così come i processi, possono essere sospesi e poi ripresi
    - i registri
      - devono essere salvati
    - lo stato:
      - esecuzione (running)
      - pronto (ready)
      - bloccato (blocked).
- In alcuni sistemi, il sistema operativo non si accorge dell'esistenza dei thread.
  - essi vengono completamente gestiti nello spazio utente.
  - quando un thread sta per bloccarsi sceglie e avvia il suo successore prima di sospendersi.
  - Diversi package che gestiscono i thread a livello utente sono entrati nell'uso comune:
    - P-thread POSIX
    - C-threads di Mach
- In altri sistemi, il sistema operativo è a conoscenza dell'esistenza di più thread per ogni processo
  - quando un thread si blocca, è il sistema operativo a scegliere il thread successivo da mandare in esecuzione, sia esso parte dello stesso processo o di uno diverso.
- Per effettuare lo scheduling, il nucleo deve avere una tabella che elenca tutti i thread presenti nel sistema, in modo analogo alla tabella dei processi.
- queste due alternative differiscono considerevolmente in termini di prestazioni
  - Una commutazione di thread è molto più veloce quando la loro gestione viene effettuata nello spazio utente piuttosto che nel caso in cui sia necessaria una chiamata al nucleo.
  - D'altra parte, quando i thread vengono gestiti interamente nello spazio utente e un thread si blocca il nucleo blocca l'intero processo, non essendo a conoscenza dell'esistenza degli altri thread
    - ad esempio in attesa di I/O o aspettando che termini la gestione di un'eccezione provocata dalla mancanza di frame di pagina in memoria, detta anche page fault
  - entrambi i sistemi sono utilizzati, e oltre ad essi diversi schemi ibridi sono stati proposti (Anderson et al., 1992).
- Sia che i thread vengano gestiti a livello utente che a livello del nucleo, essi introducono numerosi problemi che devono essere risolti e che modificano in modo significativo il modello di programmazione:
  - ad esempio nel caso di una FORK
    - Se il processo genitore ha più di un thread, anche il figlio deve contenerne altrettanti?
      - Se così non fosse, il processo potrebbe non funzionare correttamente, poiché ognuno di essi potrebbe essere essenziale al funzionamento.
      - Se così fosse, cosa accade se, in quel momento, uno dei thread è bloccato su di una READ da tastiera?
        
        Si avrebbero due thread bloccati in attesa di input da tastiera?
        
        Quando dal terminale viene inserita una riga, entrambi i thread ne ottengono una copia?
        
        Solo il genitore? O solo il figlio?
      - Lo stesso problema si ha con le connessioni di rete già aperte.
  - Un altro insieme di problemi nasce dal fatto che i thread condividono un gran numero di strutture dati
    - Cosa succede se un thread chiude un file mentre un altro thread sta ancora leggendo da esso?
    - Supponiamo che un thread si accorga di aver bisogno di memoria e inizi ad allocarsi più memoria, quindi, a metà strada, un nuovo thread viene mandato in esecuzione.
      - Il nuovo thread si accorge della scarsità di memoria disponibile e inizia ad allocarsi memoria.
      - L'allocazione avviene una o due volte?
  - In quasi tutti i sistemi la cui progettazione è avvenuta senza tener conto dei thread, le librerie (come le procedure di allocazione di memoria) non sono rientranti, e provocano un crash se si effettua una seconda chiamata mentre la prima è ancora attiva.
  - La segnalazione degli errori può generare un ulteriore problema.
    - In UNIX, dopo una chiamata di sistema, lo stato della chiamata viene inserito in una variabile globale, errno.
      - Cosa succede se un thread effettua una chiamata di sistema e, prima che sia in grado di leggere errno, un altro thread effettua una chiamata di sistema sovrascrivendo il valore originario?
  - Consideriamo adesso i segnali
    - Alcuni sono specifici per i thread mentre altri no
      - se un thread chiama una ALARM, la logica vuole che il risultato ritorni al thread che ha effettuato la chiamata.
        
        Se il nucleo è a conoscenza dell'esistenza dei thread, esso si preoccupa che il thread giusto riceva il segnale.
        
        Quando il nucleo non è a conoscenza dei thread, è il package dei thread che deve in qualche modo tener conto degli allarmi.
    - Un'ulteriore complicazione per i thread a livello utente si ha quando (come in UNIX) un processo può avere un solo allarme pendente per volta e diversi thread chiamano indipendentemente la ALARM.
    - Altri segnali, come le interruzioni di tastiera, non fanno esplicito riferimento ad alcun thread.
      - Chi li deve intercettare?
        
        Un thread designato?
        
        Tutti i thread?
        
        Un thread creato appositamente?
      - Tutte queste soluzioni comportano dei problemi.
    - Inoltre, cosa accade se un thread cambia la procedura di gestione dei segnali senza avvisare gli altri thread?
  - L'ultimo problema introdotto dai thread è la gestione dello stack.
    - In molti sistemi, quando si ha un overflow dello stack, il nucleo, in modo automatico, fornisce spazio di stack in aggiunta.
    - Quando un processo ha più thread, deve anche avere più stack.
    - Se il nucleo non è a conoscenza di tutti questi stack non li può neanche incrementare automaticamente in seguito a un traboccamento dello stack (stack fault).
    - In effetti, non può neanche accorgersi che un errore nell'assegnazione della memoria (memory fault) è collegato a una crescita dello stack.
- la semplice introduzione dei thread in un sistema preesistente non è qualcosa che può funzionare senza una sostanziale riprogettazione del sistema.
  - almeno la semantica delle chiamate di sistema deve essere ridefinita e le librerie devono essere riscritte.
  - tutte queste cose devono essere poi realizzate in modo da mantenere la compatibilità all'indietro con i programmi esistenti e quindi con il caso restrittivo che prevede un thread per ogni processo.
Il first-level interrupt handler - FLIH
- è la parte di sistema operativo responsabile delle risposte da fornire ai segnali provenienti sia dal mondo esterno (interrupt) che dall'interno dello stesso sistema di calcolo (segnalazione di errori e supervisor call).
- Chiameremo due tipi di segnali con il nome di interrupt e faremo uso degli aggettivi "esterno" ed "interno" per distinguerli, se necessario.
- La funzione del FLIH è duplice:
  - 1) determina l'origine dell'interrupt;
  - 2) avvia la gestione dell'interrupt
- al meccanismo degli interrupt compete almeno il salvataggio del valore del program counter più alcuni registri per il processo interrotto.
  - Se ciò non viene fatto dal meccanismo degli interrupt, deve essere eseguito prima di ogni altra cosa da parte dello stesso FLIH.
  - Poiché il FLIH opera entro una zona di memoria riservata, l'insieme dei registri interessati non sarà vasto
    - potrebbe essere un singolo accumulatore.
  - certamente non occorre salvare l'intero ambiente volatile
- Una strategia alternativa al salvataggio dei valori dei registri consiste nel fornire un insieme aggiuntivo di registri da usarsi solamente nel modo privilegiato. Lo FLIH può, quindi, utilizzare questi registri lasciando intatti quelli del processo interrotto.
  - come accade sullo Zilog Z8O, sulla Serie 1 IBM e su alcuni modelli della gamma PDP-11
- Determinare l'origine dell'interrupt
  - skip chain
    - è la forma caratteristica di hardware primitivo
    - tutti gli interrupt trasferiscono il controllo del processo ad una stessa locazione
    - si svolge una sequenza, denominata skip chain, di verifiche sui flag di stato relativi a tutte le possibili fonti di interrupt per giungere alla loro individuazione
    - Risulta vantaggioso codificare la skip chain in modo che le cause più frequenti d'interrupt si trovino vicino alla testa della stessa.
  - Alcuni calcolatori (come il Pentium) non usano la skip chain in quanto essi racchiudono un hardware particolare che distingue tra le fonti di interruzione, trasferendo il controllo a locazioni differenti a seconda della causa stessa.
    - Ciò riduce il tempo necessario per individuare un interrupt a scapito, però, delle locazioni aggiuntive necessarie per la gestione degli interrupt.
  - Altri calcolatori usano una soluzione di compromesso (come gli IBM 370)
    - forniscono un numero limitato di locazioni per la gestione degli interrupt, ciascuna delle quali viene condivisa da un gruppo di dispositivi.
    - Ad ogni classe di dispositivi di I/O viene di solito associata una locazione vicino al fondo della memoria, chiamata anche vettore di interruzione.
    - La prima fase dell'individuazione degli interrupt, quindi, si attua tramite l'hardware e, per completarla, è sufficiente una breve skip chain che si diparte da ciascuna locazione.
      - Questo è spesso il modo con cui si distinguono interrupt esterni, error trap e supervisor call.
    - Il meccanismo di interrupt (come sull'IBM 370) può offrire ulteriori ausili per l'individuazione delle cause relative all'interrupt allocando in una qualche locazione fissa della memoria informazioni aggiuntive.
- Gestire l'interrupt
  - Gli interrupt inviati ad un processore centrale normalmente vengono inibiti quando questo passa dal modo non privilegiato al modo privilegiato.
    - Ciò garantisce che i valori dei registri, salvati entrando nel FLIH, non vengano sovrascritti (e quindi perduti) ad opera di un successivo interrupt, verificatosi prima di lasciare il FLIH.
  - Un interrupt che si verifichi mentre è disabilitato il meccanismo degli interrupt viene tenuto in sospeso fino a che il meccanismo stesso non viene riabilitato ritornando al modo non privilegiato.
  - se un'unità periferica richiede risposte molto più veloci di altre il precedente meccanismo non funziona occorre introdurre il concetto di priorità tra gli interrupt
    - una routine per la gestione degli interrupt viene interrotta a sua volta da una richiesta di intervento proveniente da un'unità con priorità più alta.
    - Alcuni calcolatori (per esempio l'IBM 370) effettuano una disabilitazione selettiva degli interrupt all'interno del FLIH:
      - mentre quest'ultimo esegue l'intervento richiesto da un interrupt, provvede, nel contempo, a disabilitare tutti quelli con priorità minore o uguale.
    - Naturalmente si devono memorizzare i registri di programma del processo interrotto in locazioni differenti, in base al livello di priorità dell'interrupt pervenuto.
      - può essere fatto anche in hardware
  - Il CDE System IO, il PDP-11 e l'M6800 sono esempi di elaboratori dotati di meccanismo dì interrupt a 8 livelli di priorità
- Avviare la gestione degli interrupt
  - le routine di gestione degli interrupt girano nel modo privilegiato con gli interrupt stessi totalmente o parzialmente inibiti
    - le routine devono durare il minor tempo possibile
      - ogni routine svolgerà un intervento minimo (ad esempio, trasferendo un carattere proveniente da un'unità di input ad un buffer) e passerà la responsabilità di ulteriori interventi (per esempio, la risposta relativa al carattere ricevuto) ad un processo eseguibile normalmente nel modo non privilegiato (riabilitando gli interrupt)
  - il verificarsi di un interrupt, sia esterno che interno, spesso muta lo stato di qualche processo
    - un processo che ha richiesto un trasferimento tra periferiche e che si trova in attesa di eventi mentre quest'ultimo è ancora in corso sarà messo nuovamente in stato ready per mezzo dell'interrupt che si verifica al completamento del trasferimento stesso.
    - certe supervisor call, quali un'operazione di wait su un semaforo con valore zero, oppure una richiesta di I/O, metteranno il processo corrente nell'impossibilità di continuare.
    - In tutti questi casi il cambiamento di stato viene effettuato dalla routine per la gestione degli interrupt che modifica le informazioni di stato presenti nel descrittore del processo interessato
  - Dopo un cambiamento di stato il processo, in esecuzione sul processore relativo, prima dell'interrupt può non essere quello più idoneo ad essere eseguito successivamente
    - ad es. l'interrupt ha messo in stato ready un processo con una priorità più alta di quello correntemente in esecuzione
  - Dispatcher (routine di smistamento) o low level scheduler
    - ha il compito di allocare i processori centrali tra i vari processi esistenti nel sistema
  - in generale si entra nella routine di smistamento in seguito ad ogni interrupt
    - in realtà sarebbe necessario solo se l'interrupt cambia lo stato di un processo
      - 1. in seguito ad un interrupt esterno che cambia Io stato di qualche processo;
      - 2. in seguito ad una supervisor call che mette temporaneamente il processo corrente nell'impossibilità di continuare;
      - 3. in seguito ad un error trap che provoca la sospensione del processo corrente mentre l'errore è oggetto d'intervento.
    - l'overload sul sistema operativo conseguente all'attivazione della routine di smistamento nei casi in cui nessun processo ha cambiato stato è più che controbilanciato dai vantaggi ottenuti grazie alla gestione uniforme di tutti gli interrupt.
- Esempio di cosa accade ad un processo utente al verificarsi di un interrupt da disco
  - il program counter e eventuali altri registri sono inseriti nello stack (corrente)
    - ad opera dell'hardware che gestisce le interruzioni
  - il computer salta alla locazione di memoria specificata nel vettore delle interruzioni da disco
    - ad opera dell'hardware che gestisce le interruzioni
  - parte la procedura di servizio relativa all'interruzione
    - salva tutti i registri nella voce della tabella dei processi relativa al processo in esecuzione
    - l'indice del processo corrente e un puntatore alla sua struttura nella tabella dei processi vengono salvati in variabili globali
      - rende molto veloce il reperimento degli stessi
    - le informazioni depositate nello stack dall'interruzione vengono rimosse
    - il puntatore allo stack viene modificato in modo da riferire uno stack temporaneo utilizzato dal gestore delle interruzioni
    - operazioni come il salvataggio dei registri o l'impostazione del puntatore allo stack non possono essere espresse in linguaggio C e vengono pertanto eseguite da una piccola routine in linguaggio Assembler.
      - Al termine, questa routine chiama una procedura C che svolge il resto del lavoro.
  - viene costruito un segnale da inviare al processo di gestione del disco, che è bloccato in sua attesa.
    - Il messaggio contiene la segnalazione dell'avvenuta interruzione, per distinguersi dai messaggi che i processi utente inviano per richiedere la lettura di blocchi da disco e altre operazioni simili.
  - lo stato del processo del disco viene cambiato da bloccato a pronto
  - lo scheduler di basso livello viene invocato
    - se il processo di gestione del disco è ora il processo eseguibile a più alta priorità, sarà scelto dallo scheduler per l'esecuzione.
    - se il processo appena interrotto era altrettanto o maggiormente importante, sarà a sua volta scelto dallo scheduler per ritornare in esecuzione mentre il processo di gestione del disco dovrà attendere ancora un pò
  - la procedura C invocata dal codice di interruzione in linguaggio Assembler ritorna
  - il codice Assembler carica i registri e la mappa di memoria del processo destinato a diventare il nuovo processo corrente per poi avviarne l'esecuzione.
- gli interrupt sul Pentium
  - un chip controllore possiede
    - 64 linee di collegamento al bus dati
    - 1 linea INT - INTERRUPT, usata per segnalare un'interruzione)
    - 1 linea INTA - INTERRUPT_ACK, riceve l'acknowledgement da parte della CPU
    - 8 linee IRQ - INTERRUPT_REQUEST, ricevono le richieste di interrupt dalle periferiche
  - normalmente sono presenti 2 chip controllori:
    - ognuno di essi può controllare 8 ingressi
    - uno è master e l'altro è slave
    - la linea INT dello slave è connessa a una linea IRQ del master in modo da poter rilevare 15 diversi dispositivi esterni usando i due controllori
    - le linee INTA sono connesse alla CPU
  - la linea INT del master, connessa alla CPU, indica al processore che vi è stata un'interruzione.
  - Il segnale INTA, proveniente dalla CPU, fa sì che il controllore responsabile dell'interruzione metta sul bus dati le informazioni che indicano al processore quale routine di servizio eseguire.
  - I chip controllori delle interruzioni sono programmati durante l'inizializzazione del sistema.
    - La programmazione determina quale output debba essere inviato al processore in corrispondenza di un segnale ricevuto su una qualsiasi linea di input, insieme ad altri parametri operativi del controllore.
  - Il dato immesso sul bus è un numero a 8 bit, usato per indicizzare una tabella che contiene fino a 256 elementi.
  - i campi più importanti degli interrupt riferiscono il segmento di codice eseguibile corrispondente alla routine di servizio e l'indirizzo iniziale all'interno di esso.
  - la CPU esegue il codice riferito dal descrittore selezionato.
    - il risultato corrisponde all'esecuzione dell'istruzione in linguaggio assembler INT <nnn>
    - nel caso di un'interruzione hardware la <nnn> ha origine dal registro nel chip controllore delle interruzioni
  - Il livello di privilegio di ogni segmento codice è memorizzato all'interno del selettore del segmento
    - esso può essere esaminato di ritorno dall'interruzione per determinare cosa deve fare l'istruzione iret
      - il selettore di segmento è uno degli elementi salvati nello stack durante un'interruzione,
  - ci sono diversi modi per rispondere a un'interruzione:
    - semplice
      - viene attivato quando
        
        la CPU riceve interruzioni annidate
        
        la CPU riceve una nuova interruzione mentre un gestore (o altro codice di nucleo) è in esecuzione:
        
        si esegue un IRET mentre è in esecuzione codice di nucleo
        
        il processore sa come gestire un'istruzione IRET esaminando il selettore del segmento codice estratto dallo stack come parte dell'istruzione.
        
        il livello di privilegio del codice interrotto è uguale al livello di privilegio del codice da eseguirsi in risposta all'interruzione.
      - non si crea un nuovo stack, ma si immettono nello stack corrente i registri essenziali necessari al ripristino del codice interrotto.
    - complesso
      - viene attivato quando:
        
        la CPU riceve un'interruzione mentre sta eseguendo un processo
        
        il codice interrotto ha un livello di privilegio inferiore al codice di servizio dell'interruzione
      - si prepara un nuovo stack
        
        la locazione di questo stack corrisponde a una voce del Segmento di Stato del Processo (task) (TSS o Task State Segment)
        
        esiste una sola struttura TSS in tutto il sistema
        
        il codice del gestore dell'interruzione usa questa locazione come stack nella tabella dei processi
        
        L'hardware controlla che il nuovo stack sia grande a sufficienza da contenere almeno la quantità minima di informazioni che vi deve essere immessa.
        
        Questa precauzione protegge il codice di nucleo a più elevato privilegio dall'essere accidentalmente (o maliziosamente) distrutto da un processo utente che invochi una chiamata di sistema con uno stack inadeguato.
      - la CPU immette, automaticamente, nel nuovo stack (con altrettanti push) diversi registri chiave
        
        tra cui quelli necessari a ripristinare stack e program counter del processo interrotto
      - il gestore delle interruzioni salva nello stack il contenuto di altri registri riempiendo lo stackframe
      - il gestore delle interruzioni passa a uno stack fornito dal nucleo per svolgere la routine di servizio per l'interruzione
      - quando termina la routine di servizio accade che:
        
        si lascia lo stack di nucleo per tornare stackframe nella tabella dei processi
        
        non necessariamente è lo stesso stackframe che era stato creato nell'ultima interruzione
        
        si estraggono esplicitamente dallo stack i registri addizionali
        
        si esegue una istruzione "iret" (Return from interrupt).
    - in entrambi i casi:
      - nell'istante in cui riceve un'interruzione la CPU disabilita, in maniera automatica, tutte le interruzioni
        
        si evita un overflow dello stackframe relativo ad un elemento della tabella dei processi
        
        esistono delle istruzioni assembler per abilitare e disabilitare le interruzioni
      - il gestore delle interruzioni
        
        abilita le interruzioni dopo essere passato allo stack di nucleo, collocato al di fuori della tabella dei processi
        
        disabilita le interruzioni prima di ritornare allo stack all'interno della tabella dei processi
        
        mentre sta gestendo un'interruzione ne possono essere intercettate ed elaborate altre.
      - i livelli di privilegio determinano la risposta alle interruzioni ricevute quando un processo è in esecuzione e quando si esegue il codice di nucleo (comprese le routine di servizio delle interruzioni)
  - istruzione IRET - Interrupt_RETurn
    - forza la CPU ad invertire il procedimento, iniziato dall'interrupt
    - la CPU ripristina i registri che erano stati immessi nello stack dall'hardware
      - si ritorna allo stack in uso prima dell'interruzione
  - questi meccanismi sono appositamente costruiti all'interno del processore per essere usati nella realizzazione di sistemi operativi atti a supportare processi paralleli.
la routine di smistamento - dispatcher
- ha il compito di allocare i processori centrali tra i vari processi esistenti nel sistema
- dopo la gestione di un interrupt può accadere che
  - il processo corrente è ancora quello più idoneo, allora
    - restituiscigli il controllo al punto indicato dal program counter, memorizzato nell'hardware dedicato agli interrupt
  - il processo corrente non è più idoneo ad essere eseguito, allora
    - salva l'ambiente volatile del processo corrente nel suo descrittore.
    - recupera l'ambiente volatile del processo più idoneo dal suo descrittore.
      - si determina il processo più idoneo ordinando tutti i processi secondo criteri di priorità
        
        l'assegnazione delle priorità ai processi esula dal compito del dispatcher
        
        le priorità per il dispatcher sono un dato di fatto, fissate dal gestore dei processi di alto livello
    - trasferisci ad esso il controllo, alla posizione indicata dal program counter ripristinato.
- cenni sulle priorità
  - vengono calcolate anche in base ai seguenti fattori
    - ammontare delle risorse necessarie
    - tempo trascorso dall'esecuzione dell'ultimo processo
    - importanza dell'utente originario
- molti sistemi operativi suddividono i processi in stato ready in parecchie classi, differenziate attraverso criteri quali
  - il fabbisogno di risorse
  - il tempo massimo d'attesa ammissibile
  - l'entità del tempo di CPU da concedere prima dell'interdizione della risorsa
  - Il (programma) monitor del DEC System-10 possiede tre code d'attesa al processore
    - ciascuna delle quali è dedicata a quei processi cui sono concessi, rispettivamente, 2 secondi, 0,25 secondi e 0,02 secondi prima dell'interdizione della risorsa.
    - in ogni coda vige il principio secondo cui il primo processo ad arrivare è il primo anche ad essere soddisfatto, e la priorità più alta è assegnata alle code d'attesa aventi il minor tempo di interdizione.
    - inizialmente, un qualsiasi processo viene sistemato nella coda da 0,02 secondi;
      - se rimane in esecuzione per l'intero arco di tempo concessogli, viene retrocesso alla coda d'attesa da 0,25 secondi e, analogamente, se anche qui rimane in esecuzione per l'intero periodo concessogli (questa volta maggiore) viene declassato alla coda d'attesa da 2 secondi.
- nel nostro ipotetico sistema operativo
  - colleghiamo i descrittori di tutti i processi eseguibili in una "coda d'attesa al processore" ordinata per priorità decrescente
    - il processo preferenziale è il primo in cima
  - il ruolo svolto dalla routine di smistamento consiste nell'attivare il primo processo presente nella coda d'attesa al processore
    - il processo corrente su questo processore è ancora il primo processo non in esecuzione presente nella coda d'attesa al processore?
      - se si:
        
        riattivalo
      - se no:
        
        Salva l'ambiente volatile del processo corrente.
        
        Recupera l'ambiente volatile del primo processo non in esecuzione presente nella coda d'attesa al processore.
        
        Riattiva l'esecuzione di questo processo.
  - l'intervento svolto dal gestore degli interrupt per rendere eseguibile un processo è di duplice natura:
    - 1) deve cambiare l'entrata di stato nel descrittore di processo
    - 2) deve agganciare il descrittore alla coda d'attesa al processore
      - nella posizione indicata dalla sua priorità
    - questa operazione può essere svolta effettuando un'operazione di signal su un semaforo sul quale il processo interessato abbia eseguito un wait
  - può capitare che nella coda d'attesa vi siano meno processi di quanti sono i processori
    - può essere dovuto a vari motivi, tra cui cattiva schedulazione di alto livello
    - piuttosto che far girare a vuoto la routine di smistamento, viene creato un null process avente la priorità più bassa e sempre in stato di pronto
      - il null process può essere semplicemente un ciclo a vuoto infinito, idle loop oppure svolgere attività di verifica sul funzionamento del processore
  - i processi in stato ready non vengono suddivisi in classi differenti
rapporto tra il FLIH e routine di smistamento (dall'alto verso il basso)
- meccanismi di interrupt
  - salva il contatore al programma
  - salva gli altri registri (opzionale)
  - entra nel FLIH
- FLIH
  - salva i registri di programma (se non eseguito prima)
  - individua l'interrupt (con l'ausilio dell'hardware)
  - entra in qualche routine di servizio
- routine di servizio
  - gestisci l'interrupt, possibilmente modificando lo stato di qualche processo
- routine di smistamento
  - è necessario commutare il processore?
  - se no, riprendi il processo interrotto
  - altrimenti
    - salva l'ambiente volatile del processo corrente
    - recupera l'ambiente volatile del primo processo idoneo presente nella coda d'attesa al processore
    - trasferisci il controllo al nuovo processo
implementazione di wait e signal nel nostro sistema operativo ipotetico
- consentono la sincronizzazione tra i processi
- sono implementate nel kernel in quanto sono comuni a tutti i processi
- wait
  - potrebbe dar luogo all'arresto di un processo, provocando l'entrata nella routine di smistamento per provvedere alla riassegnazione del processore relativo
    - Pertanto, l'operazione di wait deve poter accedere alla routine di smistamento
  - in base alla definizione dei semafori deve accadere:
    - wait(s) : when s >0 do decremento di s (semaforo)
- signal
  - viene usata all'interno delle routine di gestione degli interrupt per risvegliare (mettere in stato di pronto) un processo
    - in pratica si esegue una signal su un semaforo sul quale un processo ha eseguito un wait
    - Pertanto, all'operazione di signal devono poter accedere le routine di gestione degli interrupt
  - in base alla definizione dei semafori deve accadere:
    - signal(s) : incremento di s (semaforo)
- raggruppamento dei processi
  - è dovuto al wait su un semaforo con valore 0
    - il raggruppamento cessa di esserci nel momento in cui un signal porta a 1 il valore del semaforo
  - questo meccanismo viene implementato associando ad ogni semaforo una "coda d'attesa al semaforo"
    - quando un processo esegue un wait su un semaforo con valore 0 viene aggiunto alla coda e rimane in attesa di eventi
    - quando viene eseguita una signal sul semaforo si può togliere qualche processo dalla coda, sempre che non sia vuota, e renderlo eseguibile
  - affinchè il meccanismo funzioni il semaforo deve essere implementato usando due elementi:
    - un intero
    - un puntatore alla coda di attesa, che può essere nullo
  - la nostra implementazione risulta
    - wait(s):
      - if s > 0 then s := s-1
      - else aggiungi il processo alla coda d'attesa la semaforo e mettilo in attesa d'eventi
    - signal(s):
      - if coda d'attesa è vuota then s := s+1
      - else togli qualche processo dalla coda di attesa al semaforo e mettilo in attesa di esecuzione
  - N.B. se un processo va rilasciato non è necessario incrementare il semaforo all'interno di una signal, poiché lo stesso processo dovrebbe effettuare un nuovo decremento dello stesso semaforo nel completare la sua operazione di wait
- inserimento e prelievo nella coda di attesa
  - per la maggior parte dei semafori risulta adeguata una coda first-in first-out, che preveda semplicemente il rilascio dei processi in ordine cronologico d'entrata
    - in questo modo tutti i processi raggruppati, alla fin fine, vengono liberati
  - in alcuni casi può essere preferibile dare alla coda d'attesa un ordine basato su altri criteri, quale ad esempio la priorità
    - questo metodo dà la garanzia che i processi con alta priorità di utilizzo del processore non rimangano inattivi a lungo nella coda d'attesa al semaforo
  - semafori diversi possono aver bisogno di implementazioni differenti relative alla propria coda d'attesa
    - è necessario introdurre un ulteriore elemento nella nostra implementazione dei semafori che indichi il tipo di coda d'attesa
  - alla luce di quanto esposto in precedenza l'implementazione del nostro semaforo sarà la seguente:
    - numero intero
    - puntatore alla coda d'attesa
    - organizzazione della coda d'attesa
      - nei casi semplici può essere una descrizione codificata del metodo organizzativo applicato
      - nei casi più complessi, può essere un puntatore relativo ad un piccolo (segmento di) programma atto all'esecuzione delle operazioni di inserimento e di prelievo dalla coda d'attesa
- allocazione dei processi
  - le operazioni di wait e signal possono modificare lo stato di un processo
    - la prima ponendolo in attesa di eventi
    - la seconda agendo in modo contrario
  - si deve prevedere, nell'implementazione di wait e signal, una exit diretta alla routine di smistamento per determinare quale sia il processo successivo da mettere in esecuzione
  - se non vi sono cambiamenti di stato nei processi la routine di smistamento riprende l'esecuzione del processo corrente
    - esso risulta essere il primo processo non in corso di esecuzione presente nella coda d'attesa del processore
    - in questo caso particolare si potrebbe scegliere di restituire il controllo direttamente al processo corrente senza passare dalla routine di smistamento
      - si aumenta la complessità dell'implementazione di wait e signal
      - si ottiene un guadagno in termini d'efficienza
    - nel nostro sistema operativo ipotetico preferiamo sacrificare l'efficienza in virtù di maggiore semplicità
- indivisibilità
  - wait e signal devono essere operazioni indivisibili
  - si può ottenere questo risultato implementandole come procedure che iniziano con un lock e si concludono con unlock
  - in una macchina monoprocessore
    - l'operazione di lock inibisce gli interrupt
    - l'operazione di unlock riattiva gli interrupt
  - in una macchina multiprocessore
    - due processi possono entrare contemporaneamente in wait o in signal, essendo eseguiti su processori distinti
    - meccanismo "test and set"
      - un'istruzione che verifica e modifica una locazione di memoria con un'operazione singola e indivisibile
      - durante l'esecuzione di questa istruzione vengono inibiti i tentativi compiuti da altri processi di accedere alla locazione interessata
      - in pratica si usa una locazione di memoria come flag che indichi se è permesso o meno eseguire una wait o signal
        
        poniamo che ciò sia permesso solo se il flag è diverso da zero, vietato in caso contrario
      - l'operazione di lock consiste nell'esecuzione di un'istruzione di "test and set" sul flag, che ne determina il valore e contemporaneamente lo azzera.
        
        se il valore del flag è diverso da zero, il processo prosegue, altrimenti inizia un'iterazione dell'istruzione di "test and set" fino a che il processo, in quel momento all'interno della procedura wait o signal, non sblocca il flag settandolo su un valore diverso da zero
      - è stato adottato su molti calcolatori, tra cui l'IBM 370
    - meccanismo di interscambio di due locazioni di memoria
      - è un'alternativa al "test and set"
      - l'operazione di lock ha inizio con l'interscambio dei valori relativi a un flag ed a una posizione precedentemente azzerata.
      - viene quindi esaminato il valore di questa seconda locazione per vedere se è permesso accedervi, mentre qualsiasi altro processo che tenti di entrarvi troverà lo zero lasciato dall'interscambio.
        
        se si verifica quest'ultima situazione, il processo ripete semplicemente l'operazione di lock, fino a che il flag non viene settato ad un valore diverso da zero ad opera di un qualche altro processo che esegue un'operazione di unlock.
      - è stato adottato sul Burroughs 6000 e nel Plessey 250
    - entrambi questi meccanismi comportano qualche forma di busy waiting, in base a cui un processo che non riesce a superare l'operazione di lock impegna il suo processore in un ciclo iterativo, tentando ripetutamente l'operazione fino a che il flag non viene modificato. Fintantoché le procedure wait e signal sono semplici, la durata del busy waiting dovrebbe essere piuttosto breve.
  - N.B. le operazioni di lock e unlock non possono essere impiegate in sostituzione delle wait e signal, ognuna di esse ha un suo ambito di utilizzo:
    - wait e signal
      - scopo: sincronizzazione generale dei processi
      - livello d'implementazione: software
      - meccanismo di ritardo: inserimento in coda d'attesa
      - tempo caratteristico di ritardo: savariati secondi
    - lock a unlock
      - scopo: muta esclusione dei processi dalle procedure di wait e signal
      - livello d'implementazione: hardware
      - meccanismo di ritardo: busy waiting/inibizione degli interrupt
      - tempo caratteristico d'attesa: svariati microsecondi
    - è possibile implementare le operazioni di wait e signal sotto forma di due procedure correlate, le quali saranno chiamate tramite supervisor call che, a loro volta, fanno parte del repertorio di istruzioni di tutti i processi