Sistemi Operativi VIII · 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

schedulazione ed allocazione delle risorse
- il problema è dovuto al fatto che non sempre i processi dispongono delle risorse di cui necessitano
  - è necessario definire delle modalità secondo le quali i processi acquisiscono le proprie risorse e riescono a condividerne un insieme limitato in modo efficiente
- schedulazione ed allocazione delle risorse sono due funzioni sono strettamente correlate
  - le scelte relative alle priorità dei processi possono dipendere dal tipo di impegno delle risorse
  - l'inserimento di nuovi processi nel sistema risente chiaramente dell'entità del potenziale di risorse residue
- la schedulazione in sostanza riguarda l'allocazione delle CPU
osservazioni di caratteri generale
- le risorse non sono illimitate, occorre pertanto condividerle tra più processi in competizione tra loro
- ogni tecnica di condivisione delle risorse persegue i seguenti obiettivi
  - 1. attuare la mutua esclusione dei processi rispetto a risorse non condivisibili;
  - 2. prevenire situazioni di stallo derivanti dalle richieste di utilizzo delle risorse;
  - 3. assicurare un alto livello di utilizzazione delle risorse;
  - 4. dare modo a tutti i processi di acquisire, entro un arco di tempo "ragionevole", le risorse di cui hanno necessità
- nota: l'obiettivo (4), in cui è implicito il soddisfacimento dell'utente, generalmente è raggiungibile solo a scapito dell'obiettivo (3)
  - con l'innalzamento del livello di utilizzazione delle risorse, aumenta anche il tempo medio di attesa per l'accoglimento delle richieste ad esse relative
  - l'alternarsi di situazioni soddisfacenti per l'utente con l'utilizzo ottimale delle risorse rappresenta uno dei criteri su cui si può basare la valutazione delle metodiche di schedulazione e di allocazione delle risorse
    - un sistema real time vedrà prevalere l'obiettivo (4) mentre un sistema batch l'obiettivo (3)
      - nei sistemi che offrono entrambe le modalità di funzionamento questo crea un problema di difficile soluzione
- l'allocazione delle risorse conviene esaminarla sotto due punti di vista:
  - 1) meccanismi
    - si intende l'aspetto più pratico relativo al modo in cui viene effettuata l'allocazione, includendo particolari quali la struttura dati per la descrizione dello stato delle risorse, le tecniche per garantire l'uso esclusivo di risorse non condivisibili ed i metodi per mettere in code d'attesa quelle richieste di utilizzo che non possono essere soddisfatte immediatamente
  - 2) metodiche
    - regolano le modalità di applicazione dei meccanismi.
    - si occupano del modo più accorto per soddisfare le richieste, anche quando sono disponibili risorse adeguate, comprendendo quindi anche le questioni relative alle situazioni di stallo ed al bilanciamento del sistema, in quanto un'allocazione poco prudente potrebbe portare a situazioni in cui alcuni processi non riescono ad evolversi o in cui il sistema è sovraccarico di richieste rispetto ad una determinata categoria di risorse.
      - è proprio in relazione a quest'ultimo punto che l'allocazione delle risorse viene a collegarsi con la schedulazione, poiché si possono ridurre le probabilità di sovraccarico prendendo decisioni accurate di schedulazione inerenti le priorità dei processi e l'introduzione di nuovi processi nel sistema
i meccanismi di allocazione
- risorsa
  - è qualsiasi elemento di un sistema di elaborazione presente in disponibilità limitate e con la necessità di essere condiviso
- le risorse di solito rientrano in una delle seguenti categorie
  - 1) CPU
    - una CPU viene assegnata, mediante la routine di smistamento, al primo processo non ancora in esecuzione presente nella coda d'attesa al processore
    - descrittore di processore
      - contiene tutti i dati che definiscono un processore
        
        a. l'identificazione del processore;
        
        b. lo stato attuale (modo privilegiato o non privilegiato);
        
        c. un puntatore relativo al descrittore del processo corrente.
      - i descrittori di processore possono essere contenuti a loro volta nella tabella centrale, oppure essere individuati da un suo puntatore
    - in una configurazione con CPU di tipi diversi, i descrittori di processore possono essere ampliati includendovi un'indicazione circa le caratteristiche della singola unità (per esempio se è dotata o meno di dispositivi hardware per la virgola mobile).
      - in tal caso, ciascun processore potrebbe essere più idoneo all'esecuzione di un tipo particolare di processo ed avere quindi la propria coda d'attesa a cui punterebbe il suo descrittore.
    - le code d'attesa al processore sono analoghe alle code di richieste delle periferiche.
  - 2) memoria
    - nel capitolo 5 abbiamo visto come può essere allocata la memoria dalla componente del nostro sistema operativo che si occupa della sua gestione, sia nel caso di paginazione che in assenza di essa.
    - le strutture dati che definiscono lo stato della memoria sono le page table, le segment table o le liste di blocchi disponibili, a seconda dell'architettura della macchina.
    - un processo, in attesa del trasferimento di una nuova pagina o segmento dalla memoria secondaria, viene messo in attesa d'eventi, ed i bit di stato nel suo descrittore ne indicano il motivo.
    - le richieste per il trasferimento di pagine o segmenti vengono accodate dal sistema di gestione della memoria sotto forma di blocchi di richiesta (IORB), gestiti dal gestore relativo alla periferica interessata su cui risiede la memoria secondaria
  - 3) periferiche
    - nel capitolo 6 abbiamo descritto il modo in cui, nei sistemi con I/O basato su stream, ad un processo viene assegnata una periferica non condivisibile al momento dell'apertura dello stream corrispondente.
    - nei sistemi che non fanno uso di stream, una periferica può essere assegnata a seguito di una richiesta inviata direttamente al sistema operativo.
    - in entrambi i casi il meccanismo di assegnazione è lo stesso.
    - la struttura dati che definisce una periferica è il relativo descrittore ed i processi in attesa dell'assegnazione di una periferica possono essere accodati ad un semaforo compreso in tale descrittore.
    - la mutua esclusione dall'utilizzo della periferica è garantita tramite l'inizializzazione ad uno del valore del semaforo
  - 4) memoria ausiliaria
    - la memoria ausiliaria utilizzata nell'implementazione della memoria virtuale viene allocata dal sistema di gestione della memoria, mentre quella impiegata per i file è allocata dal file system.
    - alcuni sistemi operativi (in particolare il MULTICS) non fanno distinzione tra file e segmenti, integrando così lo spazio di memorizzazione dei file nella memoria virtuale, mentre il compito di effettuare tutte le allocazioni viene svolto dal file system.
    - la struttura dati utilizzata per l'allocazione consiste in un qualche tipo di lista dei blocchi disponibili o di mappa binaria, come descritto nel capitolo 7
    - le richieste di spazio per i file vengono respinte solo se il singolo utente interessato ha superato la sua quota, oppure se l'intera memoria ausiliaria è piena.
      - in nessuno dei due casi risulta pratico accodare le richieste: la prima delle due situazioni è risolvibile solo tramite l'intervento dell'utente stesso, mentre, per quanto riguarda la seconda, non si può garantire un mutamento entro un breve arco di tempo.
  - 5) file
    - si può considerare come risorsa anche un singolo file, nel senso che più processi possono mirare a condividerlo.
      - fintantoché tutti i processi operano nel modo di "solo lettura", la risorsa è condivisibile;
      - se un processo intende scrivere dentro al file, la risorsa diventa non condivisibile.
    - l'allocazione di un file per un processo viene effettuata dal file system al momento dell'apertura del file stesso e i meccanismi di interlock per le operazioni di scrittura vengono messi in pratica tramite i metodi descritti nel capitolo 7.
    - le strutture dati che definiscono i file naturalmente sono le directory.
    - di solito i sistemi di tipo batch non accodano le richieste di accesso ai file in quanto richieste contemporanee (di non lettura) solitamente indicano che l'utente ha commesso un errore.
    - nella trattazione delle transazioni e nel controllo dei processi, comunque, può essere conveniente fissare delle code d'accesso all'interno del file system.
      - tali code possono essere associate a semafori
- risulta chiaro dal precedente quadro d'insieme che i meccanismi di allocazione vengono implementati ai vari livelli del sistema operativo, in quanto ogni meccanismo si trova al livello più opportuno per la risorsa allocata.
  - vedremo, comunque, che le metodiche di impiego dei meccanismi devono essere intese globalmente per il sistema nel suo complesso
le situazioni di stallo
- è facile che si verifichino se le risorse vengono assegnate ai processi esclusivamente sulla base della loro disponibilità
- nella sua forma più semplice una situazione di stallo avviene nelle seguenti circostanze:
  - il processo A, cui è concessa la risorsa X, in seguito richiede anche la risorsa Y;
  - il processo B, cui è assegnata la risorsa Y, in seguito richiede anche la risorsa X.
  - se entrambe le risorse non sono condivisibili e se nessun processo rilascia la risorsa impegnata, sorge una situazione di stallo
- in generate, le condizioni necessarie e sufficienti per una situazione di stallo (Coffman et al., 1971) sono le seguenti:
  - 1. le risorse interessate non sono condivisibili;
  - 2. i processi impegnano le risorse già loro assegnate, mentre ne attendono di nuove;
  - 3. le risorse non possono essere interdette durante l'uso;
  - 4. esiste una catena circolare di processi tale che ogni processo impegna le risorse che al momento vengono richieste da parte del processo che segue nella catena.
- si può risolvere il problema delle situazioni di stallo adottando una delle seguenti strategie:
  - 1. tecniche di prevenzione
    - prevengono situazioni di stallo garantendo sempre che almeno una delle quattro condizioni precedenti non sia valida
    - la condizione (1) è difficile da invalidare
      - poiché alcune risorse per loro stessa natura non sono condivisibili.
      - tuttavia, l'impiego della funzione di spool può eliminare potenziali situazioni di stallo insite nelle periferiche non condivisibili
    - la condizione (2) può essere invalidata
      - occorre stabilire che i processi richiedano tutte assieme le risorse loro necessarie e che non possano evolversi fino a che tutte le richieste non siano state soddisfatte.
      - (svantaggio) risorse utilizzate anche solo per poco tempo vengono allocate e diventano inaccessibili per lunghi periodi
      - (vantaggio) è facile da implementare e, a lunga scadenza, può rivelarsi più economico di certi algoritmi maggiormente complessi.
    - la condizione (3) viene invalidata semplicemente
      - imponendo la regola che, se ad un processo viene respinta la richiesta di utilizzo di una risorsa, questo deve rilasciare tutte le risorse impegnate al momento e, se necessario, richiederle nuovamente assieme a quelle aggiuntive.
      - svantaggi
        
        all'atto pratico può dimostrarsi poco funzionale, in quanto l'interdizione, poniamo, di una stampante parallela potrebbe dar luogo all'interfoliazione dell'output proveniente da più lavori.
        
        anche se una risorsa può essere interdetta in modo conveniente, si può incorrere in un appesantimento piuttosto considerevole dovuto alla memorizzazione ed al ripristino del suo stato al momento dell'interdizione.
        
        nel caso di una sola CPU l'appesantimento del sistema è relativamente limitato (più precisamente, alla memorizzazione dell'ambiente volatile del processo corrente) e l'interdizione del processore si può considerare sempre possibile
    - la condizione (4) può essere invalidata
      - imponendo ai vari tipi di risorse un ordinamento tale per cui, se ad un processo sono state assegnate risorse del tipo k, può richiedere solo quelle risorse corrispondenti ai tipi successivi a k.
      - (vantaggio) non si verifica mai una condizione di attesa in circolo (circular wait).
      - (svantaggio) è imposta una restrizione alla sequenza naturale delle richieste di risorse
        
        è possibile moderare tale effetto negativo mettendo le risorse di uso più comune in posizione più avanzata all'interno della sequenza
    - OS/360 (Havender, 1968)
      - è un esempio interessante inerente a questi tre metodi di prevenzione delle situazioni di stallo
      - i lavori sono suddivisi in passi (job steps) e una routine di inizializzazione dei passi stessi è responsabile dell'ottenimento delle risorse necessarie ad ogni passo.
      - l'attivazione concorrente di più passi relativi a lavori diversi è ottenuta tenendo a disposizione varie copie della routine d'inizializzazione.
      - si previene l'insorgere di situazioni di stallo tra le copie della routine garantendo che ognuna di esse acquisisca le risorse sempre nel seguente ordine:
        
        file
        
        memoria
        
        periferiche
      - si previene d'altra parte l'insorgere di situazioni di stallo tra i diversi passi di lavoro che intendono accedere agli stessi file facendo sì che la routine di inizializzazione acquisisca in una volta sola tutti i file necessari ad un intero lavoro.
      - si noti che in questo caso l'interdizione non sarebbe opportuna, in quanto un lavoro non vorrebbe vedersi manomettere i propri file da parte di passi ad esso estranei, mentre si trova esso stesso in un qualche passo intermedio tra l'inizio ed il suo completamento.
      - non è nemmeno possibile stabilire una sequenza sensata per le richieste d'accesso ai file.
      - si previene l'insorgere di situazioni di stallo per quanto riguarda l'allocazione delle periferiche costringendo i job a rilasciare tutte le risorse, tranne il file, dopo ogni passo ed a richiederle nuovamente per il passo successivo, se necessario
  - 2. tecniche di riconoscimento e recupero
    - sono meno restrittive delle tecniche di prevenzione delle situazioni di stallo
    - consentono l'eventuale verificarsi di situazioni di stallo, ma fanno affidamento sulla loro individuazione e sulla capacità di promuoverne il recupero.
    - la velocità di tale impostazione è funzione della frequenza con cui insorgono situazioni di stallo e del tipo di recupero che è possibile effettuare
    - gli algoritmi di riconoscimento si basano sul rilevamento delle situazioni di attesa in circolo espresse dalla precedente condizione (4)
    - si può rappresentare lo stato del sistema in ogni istante mediante un grafico di stato
      - i cui nodi indicano le risorse
      - un eventuale arco tra due nodi A e B comporta l'esistenza di un processo che impegna la risorsa A, mentre richiede nel contempo la risorsa B
    - nel grafico di stato la condizione di attesa in circolo è rappresentata da una curva chiusa
      - se abbiamo 3 risorse A, B, C è presente un arco tra i nodi A e B, B e C, C e A
    - l'algoritmo di riconoscimento
      - mantiene una rappresentazione del grafico di stato nella maniera più opportuna e la controlla di tanto in tanto per verificare l'esistenza di curve chiuse.
      - il controllo può avvenire a seguito
        
        di ogni allocazione oppure
        
        l'appesantimento di questa operazione probabilmente risulterebbe troppo oneroso
        
        di intervalli di tempo prefissati
      - il riconoscimento di situazioni di stallo è utile solo se si può effettuare un tentativo "soddisfacente" per recuperarle.
        
        la definizione di "soddisfacente" può essere ampliata a seconda delle circostanze includendo una qualsiasi delle tecniche di recupero
    - tecniche di recupero (elencate in ordine di complessità crescente)
      - a. interruzione di tutti i processi in situazioni di stallo
        
        questo è il metodo adottato nella maggioranza dei sistemi universali
      - b. riattivazione dei processi in situazione di stallo a partire da qualche punto di controllo intermedio, sempre che esista
        
        se applicato in modo semplicistico può ripresentarsi tale e quale la situazione originaria di stallo, anche se la non-determinatezza del sistema solitamente garantisce che ciò non avvenga.
      - c. interruzione successiva di tutti i processi in situazioni di stallo fino a che queste ultime non sussistano più.
        
        l'ordine delle interruzioni può essere tale da minimizzare i costi relativi alla perdita dell'investimento fatto in termini dì risorse già utilizzate.
        
        tale metodica comporta il richiamo dell'algoritmo di riconoscimento a seguito di ogni singola interruzione, per verificare se persistono ancora situazioni di stallo.
      - d. interdizione successiva delle risorse dai processi in situazioni di stallo, fino a che queste ultime non sussistano più.
        
        come nel punto (c), l'ordine delle interdizioni può essere tale da minimizzare qualche funzione di costo.
        
        il richiamo dell'algoritmo di riconoscimento è necessario dopo ogni interdizione.
        
        un processo che ha subito l'interdizione di una risorsa deve effettuare successivamente una richiesta per la riallocazione della stessa
    - nota: il riconoscimento di situazioni di stallo spesso viene affidato agli operatori di sistema, anziché essere eseguito dal sistema stesso.
      - un operatore dotato di spirito d'osservazione noterà alla fine che certi processi sembrano essere bloccati e, ad un più attento esame, si renderà conto che si è verificata una situazione di stallo.
      - l'intervento consueto volto al recupero di tale condizione consiste nell'interruzione e nella riattivazione (se possibile) dei processi in stallo
  - 3. tecniche per evitare situazioni di stallo, tramite opportuni interventi preventivi
    - prevede l'impiego di un algoritmo che avverta anticipatamente del probabile verificarsi di una situazione di stallo e che, pertanto, respinga una richiesta di risorse, altrimenti accettata
    - questo concetto è diverso da quello di prevenzione, la quale garantisce aprioristicamente l'impossibilità del verificarsi di situazioni di stallo, invalidando una delle condizioni necessarie
    - un criterio che si può applicare è il seguente:
      - prima di accettare una richiesta d'utilizzo di risorse, si prova sperimentalmente a cambiare il grafico di stato per vedere cosa accadrebbe se la richiesta fosse accettata
      - si applica quindi un algoritmo di riconoscimento delle situazioni di stallo.
        
        se l'algoritmo dà il "cessato allarme", la richiesta viene accolta
        
        in caso contrario, viene respinta ed il grafico di stato viene riportato al suo aspetto originario
      - (difetto) non è detto che una situazione di stallo si verifichi immediatamente come ha dimostrato Dijkstra
        
        abbiamo un sistema fondato su due processi A, B e due risorse Plotter e Printer (stampante)
        
        l'asse orizzontale e verticale rappresentano il numero di istruzioni eseguite da A e B rispettivamente
        
        I1 - A richiede la stampante
        
        I2 - A richiede il plotter
        
        I3 - A rilascia la stampante
        
        I4 - A rilascia il plotter
        
        I5 - B richiede la stampante
        
        I6 - B richiede il plotter
        
        I7 - B rilascia la stampante
        
        I8 - B rilascia il plotter
        
        ogni punto del diagramma rappresenta uno stato congiunto dei due processi
        
        p - è lo stato iniziale
        
        nessuno dei due processi ha eseguito ancora un'istruzione
        
        q - è il punto in cui si arriva se lo scheduler esegue A per primo
        
        A ha eseguito un certo numero di istruzione e B nessuna
        
        in questo punto la traiettoria diventa verticale ad indicare che lo scheduler ha scelto di eseguire B
        
        con un singolo processore tutti i cammini devono essere orizzontali o verticali
        
        un cammino obliquo indica l'esecuzione contemporanea dei due processi
        
        inoltre i processi non possono tornare indietro per cui lo spostamento avviene sempre verso l'alto o verso destra
        
        quando A attraversa la linea I1 nel cammino r-s significa che ha chiesto e ottenuto la stampante
        
        quando B raggiunge il punto t richiede il plotter
        
        le regioni tratteggiate
        
        con linee inclinate a destra rappresentano lo stato in cui entrambi i processi detengono la stampante
        
        con linee inclinate a sinistra rappresentano lo stato in cui entrambi i processi detengono il plotter
        
        sono regioni rese inaccessibili dalla regola di mutua esclusione
        
        se il sistema entra nell'area delimitata da I1,I2,I5,I6 si bloccherebbe nell'intersezione tra I2 e I6
        
        in questo punto A sta richiedendo il plotter e B la stampante
        
        entrambe le risorse sono gia state assegnata
        
        questa è un area non sicura e non vi si deve mai entrare
        
        al punto t la sola cosa sicura da fare è far eseguire A fino a I4
        
        a questo punto qualunque traiettoria che arrivi a u può essere scelta con successo
        
        al punto t il sistema potrebbe assegnare la risorsa a B entrando in un'area non sicura ed andando incontro ad un probabile deadlock
        
        per evitare il deadlock il B deve essere sospeso finché A non ha chiesto e rilasciato il plotter
      - un algoritmo volto ad evitare situazioni di stallo, per essere efficace, deve avere in anticipo qualche cognizione sul possibile schema evolutivo degli eventi futuri
        
        deve essere in grado di distinguere situazioni in cui è insito un potenziale di stallo
        
        il tipo di conoscenza a priori rappresenta la caratteristica distintiva dei vari algoritmi
      - banker's algorithm - l'algoritmo del banchiere (Dijkstra, 1965)
        
        è forse l'algoritmo più noto
        
        il tipo di conoscenza a priori richiesta dal banker's algorithm riguarda la disponibilità massima di ogni risorsa che richiederà un processo durante il suo ciclo di vita.
        
        denominiamo questa quantità la claim (rivendicazione) di un processo su una risorsa.
        
        nei sistemi di tipo batch, tale claim è piuttosto razionale, in quanto si può far uso delle descrizioni dei job per specificare anticipatamente il fabbisogno massimo di risorse.
        
        l'algoritmo accoglie una richiesta di risorse solo se:
        
        la richiesta sommata alla quantità gia in uso dal processo è inferiore alla claim;
        
        in seguito a ciò, sussiste una sequenza secondo la quale tutti i processi sono in grado di essere eseguiti fino al completamento, anche se tutti avanzano le relative claim per intero.
        
        in buona sostanza il funzionamento di questo algoritmo si basa sul fatto che i processi non richiedono contemporaneamente e subito tutte le risorse indicate dalle proprie claim
        
        prima di effettuare un'allocazione l'algoritmo verifica che in seguito alla stessa rimangano risorse a sufficienza per consentire la costruzione di una simile sequenza
        
        riconsideriamo la precedente figura
        
        le claim di A e B sono costituite per entrambi dalla stampante e dal plotter
        
        se ci troviamo nel punto r esistono risorse sufficienti ad accogliere le claim sia di A che di B
        
        nel punto s la stampante è stata allocata ad A mentre il plotter è ancora disponibile
        
        esistono ancora risorse residue sufficienti a portare a termine entrambi i processi pure se richiedono per intero la propria claim
        
        in tal caso la sequenza corretta consiste nel far eseguire il processo A e successivamente il processo B
        
        nell'area I1,I2,I5,I6 invece la stampante è allocata ad A e il plotter a B
        
        non si hanno risorse sufficienti a portare a termine entrambi i processi se richiedono per intero la propria claim
        
        il banker's algorithm, pertanto, evita l'ingresso in quest'area respingendo la richiesta di utilizzo del plotter da parte di B
        
        B verrà sospeso finché A non avrà rilasciato le risorse impegnate
        
        l'ingresso in quest'area è vietato a causa dell'eventualità che A possa esercitare la sua claim sul plotter proprio quando B esercita la sua sulla stampante.
        
        se di fatto nessuno dei due processi scegliesse di avanzare la rispettiva claim in un momento rischioso, quest'area risulterebbe del tutto sicura
        
        i principali inconvenienti relativi all'impiego di questo algoritmo sono dati dalla sua tendenza all'eccessiva prudenza, nonché dall'appesantimento del sistema conseguente alla sua applicazione.
        
        è stato dimostrato (Habermann, 1969) che l'attività concernente l'effettuazione delle verifiche è proporzionale al quadrato del numero dei processi esistenti nel sistema
- le situazioni di stallo vanno gestite a diversi livelli del sistema operativo a seconda delle tecniche applicate
  - se si fa uso di una strategia di prevenzione, tutte le parti del sistema destinate all'allocazione delle risorse sottostanno ad una o più delle limitazioni descritte in precedenza
    - le quali si possono implementare come elementi dei meccanismi di allocazione delle risorse ai livelli più idonei.
  - se si fa uso dei metodi di riconoscimento, non è necessaria alcuna modifica dei meccanismi di allocazione.
    - l'algoritmo di riconoscimento che deve poter accedere a tutte le strutture dati concernenti l'allocazione, può essere implementato ad alto livello, se possibile nello stesso ambito del gestore dei processi
  - nel caso si miri ad evitare situazioni di stallo, tutte le richieste di risorse devono essere sottoposte a verifica da parte dell'algoritmo relativo, ad esempio attraverso il gestore dei processi, il quale diviene così la sede naturale per l'implementazione dell'algoritmo
il gestore dei processi
- schedulazione
  - concerne la determinazione dei tempi di introduzione dei nuovi processi nel sistema e l'ordine di esecuzione che dovrebbero seguire quelli esistenti
    - questi argomenti sono intimamente connessi all'allocazione delle risorse
- gestore dei processi
  - è un processo che si occupa sia dell'allocazione delle risorse che della schedulazione dei processi
- compiti del gestore dei processi
  - 1) introduzione di nuovi processi
    - in un sistema di tipo batch, i job in attesa di esecuzione vengono immagazzinati in un pool dei lavori che è tenuto su memoria di massa
    - il gestore dei processi avvia l'esecuzione di un job dando inizio al processo opportuno
    - la scelta relativa al lavoro successivo da avviare dipende dalle risorse richieste da ogni singolo job (in base a quanto definito nella relativa descrizione) nonché dallo schema complessivo di allocazione delle risorse entro il sistema.
    - al fine di raggiungere una produttività elevata, il gestore dei processi dovrebbe avviare quelli nuovi non appena lo consente la disponibilità di risorse.
    - in un sistema ad accesso multiplo, i processi vengono creati nel momento in cui gli utenti effettuano il login.
      - poichè ogni nuovo utente rende maggiore la domanda complessiva di risorse, l'accesso può essere respinto quando il numero di utenti collegati al sistema è tale da aumentare il tempo di risposta fino a limiti non più tollerabili
  - 2) assegnazione delle priorità ai processi
    - l'ordine concernente l'esecuzione dei vari processi viene determinato sia dalla sequenza presente nella coda d'attesa al processore sia dalla successione con cui la routine di smistamento seleziona per il prelievo i processi della coda.
    - per contenere al massimo gli appesantimenti dovuti allo smistamento, la routine che si occupa di tale attività dovrebbe prelevare dalla coda sempre il primo processo avente i requisiti necessari;
      - l'ordine della coda diviene così implicitamente il fattore determinante.
    - il gestore dei processi è responsabile dell'assegnazione delle priorità ai processi, così da inserirli in coda nella posizione più opportuna allorché vengono messi in stato di pronto.
  - 3) implementazione dei metodi di allocazione delle risorse
    - si fa riferimento ai metodi relativi a come evitare situazioni di stallo e bilanciare il sistema:
      - garantendo che nessun genere di risorsa sia né sottoutilizzata, né sovrautilizzata.
    - i criteri per la valutazione del bilanciamento del sistema saranno esaminati nel paragrafo che segue.
    - poiché il comportamento del sistema è determinato in larga misura dalle attività del gestore dei processi, è importante che quest'ultimo abbia una priorità più alta rispetto agli altri processi.
      - se il gestore dei processi possiede la priorità massima, la routine di smistamento lo manderà in esecuzione ogniqualvolta si trova in stato di pronto, dandogli la precedenza rispetto agli altri processi.
      - ciò assicura che il sistema reagisca prontamente al mutare delle situazioni, in particolare ai cambiamenti della domanda complessiva di risorse.
    - gli eventi che possono causare l'attivazione del gestore dei processi sono le seguenti:
      - viene richiesta una risorsa;
      - viene rilasciata una risorsa;
      - termina un processo;
      - giunge nel pool dei lavori in attesa d'esecuzione un nuovo lavoro (oppure un nuovo utente prova ad effettuare il login).
    - è istruttivo notare l'analogia esistente tra gli interrupt e gli eventi di schedulazione precedentemente riportati.
      - si verificano ad intervalli imprevedibili ed entrambi possono provocare un cambiamento nel comportamento del sistema.
      - nel caso degli eventi di schedulazione, le modifiche avvengono ad alto livello, influenzando parametri globali, quali le priorità dei processi ed il loro numero entro il sistema.
      - le modifiche dovute agli interrupt, invece, si verificano a basso livello
    - gli algoritmi di schedulazione saranno in funzione dell'aspetto che si vuole privilegiare nel sistema operativo
    - algoritmi basati sul presupposto che le CPU siano risorse di primaria importanza
      - un modello generico di sistema limitato dalla CPU è caratterizzato da:
        
        i nuovi processi giungono nella coda d'attesa al processore e vengono gestiti da svariati processori (avanziamo l'ipotesi che siano identici).
        
        dopo essere stato in certa misura soggetto ad interventi gestionali, un processo potrebbe essere completato, nel qual caso lascia il sistema;
        
        in caso contrario, potrebbe essere reimmesso nella coda per ottenere di venir ripreso in una fase successiva.
        
        il modello rappresenta solamente quei processi che si trovano in stato di pronto ed in corso d'esecuzione:
        
        l'assenza dei processi in stato di blocco rispecchia il fatto che, in un sistema limitato dalla CPU, gli unici ritardi significativi eventualmente sono dovuti all'attesa nella coda al processore.
      - ogni particolare algoritmo di schedulazione è caratterizzato dall'ordine che hanno i processi in coda d'attesa e dalle condizioni in cui vi vengono reimmessi.
      - di seguito prenderemo in considerazione vari algoritmi tra i più noti:
        
        1) il primo lavoro è il più breve
        
        l'ordine della coda d'attesa è disposto in base al tempo di esecuzione richiesto da ogni processo
        
        questo algoritmo è idoneo solamente ai sistemi di tipo batch, nei quali si può ricavare una stima del tempo d'esecuzione derivandola dalla descrizione del job
        
        il suo scopo consiste nel contenere al massimo il tempo d'esecuzione (turnaround time) dei lavori più brevi
        
        se ne consiglia l'impiego in quegli ambienti in cui il grosso dell'attività è formato da job limitati.
        
        esistono più varianti di questo algoritmo
        
        forma più semplice
        
        consente l'esecuzione di tutti i processi fino al loro completamento
        
        preemptive shortest jobfirst (variante della forma semplice)
        
        un nuovo processo può interdire un processore nel caso il suo tempo d'esecuzione sia inferiore a quello necessario per portare a termine il processo corrente
        
        è ancora più favorevole ai job brevi.
        
        un'altra modifica, che garantisce che i lavori più lunghi non vengano ritardati all'infinito, consiste nell'aumento graduale della priorità di un processo in base al suo tempo d'attesa in coda
        
        2) round robin
        
        è stato ideato per fornire rapidamente risposta a richieste di gestione contenute nel tempo, quando non siano noti in anticipo i tempi d'esecuzione.
        
        ogni processo presente nel sistema gode di una determinata quantità di attenzione prima di essere reimmesso in coda, in ultima posizione.
        
        la coda è quindi circolare ed il suo ordine si basa sul tempo trascorso dall'ultima esecuzione
        
        i processi che necessitano di gestioni di lunga durata rimarranno in coda e ripeteranno il ciclo varie volte prima di essere completati
        
        i processi con tempi d'esecuzione inferiori alla quantità prevista saranno portati a termine durante il primo ciclo.
        
        l'algoritmo round robin è stato usato nel primo sistema operante in time-sharing, il CTSS (Corbatò et aI., 1962) ed è stato successivamente implementato in parecchie varianti su molti altri sistemi.
        
        la maggior parte delle varianti rispondono allo scopo di ridurre la tendenza del sistema a collassare se sottoposto a carico troppo consistente.
        
        l'analisi e l'esperienza mostrano che, se il carico si appesantisce eccessivamente rispetto ad una data capacità, le prestazioni del sistema si degradano immediatamente.
        
        un modo per risolvere il problema consiste nell'aumentare la capacità con il crescere del numero dei processi.
        
        ciò fa aumentare anche le probabilità di portare a termine un processo entro l'intervallo di tempo prestabilito, riducendo l'appesantimento dovuto alla commutazione dei processi.
        
        3) coda a due livelli
        
        è un'altra variante dell'algoritmo round robin volta a superare il problema del degrado immediato dovuto al carico.
        
        i processi non completati entro un numero prefissato di cicli vengono dirottati su una coda secondaria che viene presa in considerazione solo se nel sistema non ci sono altri processi.
        
        la coda secondaria stessa può poi essere trattata sulla base dell'algoritmo round robin, però con un intervallo di tempo maggiore, oppure può operare sul principio FIFO.
        
        il sistema a due livelli viene impiegato spesso negli ambienti misti operanti nel modo batch e ad accesso multiplo, dove i processi di tipo batch, essendo più lunghi, tendono a cedere la precedenza e vengono eseguiti solo quando non sono presenti processi avviati da terminale.
        
        se si ritiene opportuno, l'algoritmo può essere generalizzato ed adattato ad un sistema a livelli multipli.
        
        si ha un esempio di ciò nel DEC System-10 Monitor, in cui ci sono tre code basate sul principio round robin, con intervalli impostati rispettivamente su 0,02 secondi, 0,25 secondi e 2 secondi (valori che in realtà possono essere cambiati).
      - è difficile determinare analiticamente i valori ottimali dei parametri dell'algoritmo round robin e dei relativi derivati, quali la misura massima di carico ed i tempi di inserimento dei processi in coda secondaria, anche se sono stati effettuati tentativi verso questa direzione (Coffman e Denning, 1973).
        
        tramite simulazione sono ricavabili delle approssimazioni che si possono poi mettere a punto in base alle condizioni reali di funzionamento esperite
      - gli algoritmi riportati in precedenza costituiscono la base delle più diffuse metodiche di schedulazione.
      - si possono trovare altri algoritmi e varianti nel validissimo studio ad opera di Coffman e Kleinrock (1968).
        
        una variante particolare degna di nota consiste nel consentire l'inserimento di priorità specifiche dall'esterno.
        
        Il risultato che ne consegue fa sì che i processi con priorità esterna più alta vengano gestiti in modo migliore di quanto accadrebbe con la forma pura di un algoritmo.
        
        ciò mette gli utenti con scadenze strette o di rango superiore in condizioni di ottenere dal sistema una risposta migliore, benché per godere di questo privilegio possano subire maggiori addebiti
    - algoritmi basati sul presupposto che le CPU non sono le sole risorse importanti
      - si possono descrivere con l'ausilio di un modello simile al caso precedente che includa uno stato di blocco, durante il quale i processi sono in attesa di richieste di risorse o di trasferimento di I/O.
      - l'aggiunta di questo stato aumenta enormemente la complessità del modello.
        
        in primo luogo, lo stato di blocco è caratterizzato non da un'unica coda, bensì da molteplici code d'attesa associate ai vari semafori che provocano l'insorgere del blocco.
        
        in secondo luogo, i processi passano dallo stato di blocco a quello di pronto a seguito di eventi, quali le operazioni di signal su semafori, che si verificano ad intervalli non prevedibili.
      - in relazione alle diverse strategie, il movimento dei processi tra le code d'attesa si può studiare sia tramite analisi formale che con la simulazione (Coffman e Denning, 1973; Svobodova, 1976), nonostante la complessità del modello renda difficile applicare entrambe le tecniche
      - uno degli scopi di un algoritmo di schedulazione potrebbe consistere nel limitare al massimo il numero delle transizioni dallo stato di esecuzione a quello di blocco.
      - poiché le transizioni, però, se dovute ai trasferimenti di I/O, sono indipendenti da esso, ne risulta che l'algoritmo dovrebbe solamente rendere minimo il numero delle richieste di risorse respinte.
        
        ciò comporta che si dovrebbero introdurre nuovi processi nel sistema solo se i loro probabili fabbisogni di risorse potranno essere soddisfatti tramite quelle disponibili in quel momento.
      - è più facile implementare questo metodo nei sistemi di tipo batch, dove la domanda complessiva di risorse può essere specificata anticipatamente
        
        nel sistema operativo dell'Atlas, i job venivano divisi in tre classi:
        
        job corti, che richiedevano tempi brevi dì CPU e nessuna periferica esterna;
        
        job da nastro magnetico, il cui nome si spiega da sé;
        
        job lunghi, che comprendevano tutto il resto.
        
        il gestore dei processi tentava di mantenere sempre nel sistema almeno un job per ogni classe.
      - rispetto ai sistemi ad accesso multiplo, nei quali le domande non sono praticamente prevedibili
      - è opportuno notare che metodi simili a questo non danno necessariamente luogo ad un'utilizzazione elevata delle risorse.
        
        è improbabile che durante la sua vita un processo faccia uso di tutte quelle risorse che ha indicato.
        
        le risorse oggetto di claim e concesse dal gestore dei processi possono restare, pertanto, inattive per periodi considerevoli.
        
        se è richiesta un'utilizzazione più elevata, il gestore dei processi deve prendere decisioni di metodo circa l'allocazione delle risorse non solo al momento dell'introduzione di nuovi processi, ma anche al verificarsi di ciascuna richiesta o rilascio di risorsa.
        
        i criteri alla base di tale processo decisionale e dell'assegnazione delle priorità ai processi sono generalmente empirici, ne prendiamo in esame alcuni qui di seguito:
        
        1. nel tentativo di accelerarne il completamento, si può dare una priorità alta a quei processi che detengono risorse numerose, rendendole così nuovamente disponibili ad essere sfruttate diversamente.
        
        il pericolo insito nell'applicazione di questa strategia consiste nel fatto che i job più consistenti possono monopolizzare la macchina o che gli utenti possono generare richieste fittizie di risorse al fine di ricevere un trattamento privilegiato.
        
        in un sistema batch si può evitare quest'ultimo rischio con la garanzia che verranno mandati in esecuzione i job con fabbisogni limitati di risorse, preferendoli agli altri.
        
        2. ogni volta che è possibile, si potrebbero accogliere ulteriori richieste provenienti da processi che detengono risorse già numerose.
        
        la giustificazione è analoga alla precedente ed anche qui si presenta il pericolo che i job più consistenti possano monopolizzare il sistema.
        
        3. nelle macchine dotate di paginazione, si può effettuare l'allocazione della memoria conformemente al principio dell'area di lavoro, descritto nel capitolo 5.
        
        4. ai processi del sistema operativo dovrebbero essere assegnate priorità che riflettono il carattere d'urgenza delle funzioni da essi svolte.
        
        la scala vede al primo posto lo stesso gestore dei processi, per finire con processi meno impellenti, come quello che effettua il dump incrementale dei file.
        
        la maggior parte dei processi di sistema avrà così priorità maggiori rispetto ai processi degli utenti.
        
        5. come caso particolare del punto (4), i gestori delle periferiche dovrebbero avere priorità elevata.
        
        in generale, tanto più veloce è la periferica, tanto più alta dovrebbe essere la priorità del gestore relativo.
        
        ciò assicura la maggiore occupazione possibile delle periferiche, riducendo conseguentemente il potenziale verificarsi di situazioni di ingorgo relative all'I/O.
        
        se si impiega la funzione di spool, anche gli spooler dovrebbero avere una priorità alta.
        
        6. salvo che non siano previste misure relative alla prevenzione di situazioni di stallo, tutte le richieste di risorse dovrebbero essere assoggettate ad un algoritmo volto ad evitare situazioni di stallo.
        
        7. l'appesantimento inerente il processo decisionale di schedulazione non dovrebbe essere sproporzionato rispetto ai vantaggi che ne derivano.
        
        si possono applicare le considerazioni suesposte per modificare uno degli algoritmi descritti in precedenza e volti alla schedulazione delle attività di CPU.
        
        ne risulterà un algoritmo in cui le priorità dei processi sono aggiornate con continuità in base a come si configurano i fabbisogni di risorse e lo stato del sistema.
        
        è difficile poter fare una valutazione del rendimento di un tale algoritmo, se non tramite l'osservazione diretta;
        
        spesso lo si può migliorare considerevolmente apportando ai suoi parametri solo lievi cambiamenti.
        
        un esempio interessante di questo fenomeno si è avuto sul DEC System-10 Monitor.
        
        in una delle prime versioni dell'algoritmo di schedulazione, i processi che rientravano nello stato di pronto, dopo essere stati bloccati in attesa di I/O da terminale, venivano messi alla fine della coda d'attesa al processore di primo livello.
        
        successivamente tale procedimento fu modificato in modo da mettere i processi in questione alla sommità della coda d'attesa di primo livello.
        
        il miglioramento della risposta del sistema agli utenti operanti in accesso multiplo risultò eccezionale.
  - possiamo riassumere questo paragrafo dicendo che il numero dei possibili algoritmi di schedulazione è vastissimo, ma che al momento non abbiamo modo di scegliere l'algoritmo ottimale per un caso specifico, tranne che per mezzo della sperimentazione.
    - l'analisi e la simulazione possono essere utili in certa misura, ma la loro validità è limitata a causa della complessità della maggioranza dei sistemi
le gerarchie dei processi
- il gestore dei processi è responsabile dell'avvio dei nuovi processi e quindi risulta esserne il padre, inoltre è responsabile del benessere della sua prole, in quanto presiede ai metodi d'allocazione delle risorse e schedulazione
- questo ruolo paterno può essere esteso anche ad altri processi, concedendo loro la possibilità di:
  - 1. creare sottoprocessi;
  - 2. allocare per i propri sottoprocessi un sottoinsieme delle proprie risorse (le quali vengono restituite al termine del sottoprocesso);
  - 3. determinare la priorità relativa dei propri processori
- lo scopo di tutto ciò è rendere possibile una gerarchia dei processi, con il gestore dei processi alla sommità
  - la forma naturale della struttura dei processi non è più, quindi, la semplice lista esposta nel capitolo 4, bensì è costituita da un albero nel quale si insinua in parte la coda d'attesa al processore che collega tutti i nodi (processi) correntemente in stato di pronto
- i vantaggi delle struttura gerarchica sono di duplice natura
  - 1) consente ad un processo che svolge vari compiti indipendenti di creare un processo ausiliario per ogni singolo compito, rendendo possibile l'esecuzione parallela.
    - naturalmente, non si guadagna nulla nel caso di una macchina ad una sola CPU, in quanto si può ottenere solamente concorrenza virtuale;
    - ma quando sono a disposizione svariati processori ne possono conseguire vantaggi reali
  - 2) consente di far girare autonomamente ed in parallelo varie versioni del sistema operativo, ciascuna finalizzata ad una diversa applicazione.
    - ciascuna delle diverse versioni, o sottosistemi, si baserà sulle prestazioni fornite dal nucleo del sistema (vedi capitolo 4), ma può servirsi di algoritmi diversi per l'implementazione delle funzioni di sistema di più alto livello che compaiono negli strati esterni.
    - ogni sottosistema rappresenta così una versione particolare della nostra "cipolla"
      - benché tutti i sottosistemi abbiano lo stesso nucleo ciascuno di essi implementa una macchina virtuale idonea ad una particolare categoria di utenti e tutte le macchine virtuali coesistono nella stessa configurazione fisica.
    - consente di sviluppare nuove versioni di un sistema operativo mentre la vecchia versione gira in parallelo
- svantaggi
  - perdita del controllo globale sull'allocazione delle risorse
  - le risorse allocate per un sottosistema o per un processo subordinato, e che non vengono usate, non possono essere trasferite altrove nel sistema, a meno che non vengano prima restituite al progenitore comune.
    - poiché i processi hanno la facoltà di assegnare a proprio piacimento sottoinsiemi delle loro risorse, non vi è garanzia che lo schema generale dell'utilizzazione delle stesse sia comunque ottimale
  - l'assegnazione delle priorità da parte di un processo ai propri figli può creare dei problemi, salvo che non siano imposte restrizioni
    - è possibile che un processo ottenga slealmente vantaggi inerenti la schedulazione delegando il proprio compito ad un sottoprocesso cui assegni una priorità molto alta.
    - si può risolvere il problema imponendo che i figli abbiano priorità relativa a quella del processo d'origine e che il campo delle possibili variazioni per le priorità relative diminuisca successivamente mano a mano che si passa ai livelli inferiori della gerarchia
      - per esempio, supponiamo che nella figura precedente, al massimo livello, l'intervallo delle priorità relative vada da O a 99, mentre al secondo livello vari da O a 9, e così via.
      - se la priorità del processo B è 20, nessun sottoprocesso di B può avere una priorità che vada oltre l'intervallo [11,29] (20 + o - 9)
      - ciò comporta che, se la priorità del processo A è superiore a 29, suddividendosi in sottoprocessi, B non è in grado di ottenere nessun vantaggio rispetto ad A.
      - se la priorità di A è maggiore di 39, a tutti i suoi sottoprocessi sarà garantita la precedenza rispetto ai sotto-processi di B.
- esempi applicativi
  - uno dei primi sistemi operativi con una struttura gerarchica dei processi lo ritroviamo sull'elaboratore RC-4000 (Hansen, 1970).
    - il suo nucleo veniva denominato Monitor ed alla sommità della gerarchia si trovava quello che veniva chiamato il Basic Operating System, corrispondente al nostro gestore dei processi.
    - la struttura dei processi poteva comprenderne fino a 23 (la limitatezza era dovuta a ragioni di spazio) e le risorse venivano trasferite dai processi padre a quelli derivati, così come descritto in precedenza.
    - una differenza tra il sistema RC-4000 e quello da noi delineato consiste nel fatto che i processi progenitori non potevano assegnare priorità ai propri figli;
      - tutti i processi avevano uguale priorità, se si esclude il fatto che potevano essere selezionati dalla routine di smistamento sulla base di un algoritmo round robin.
  - una gerarchia limitata è implementata anche sul sistema operativo IBM VM/370 (VM sta per il termine inglese corrispondente a macchina virtuale).
    - la lista in questo caso è limitata a 3 livelli:
      - alla base vi è proprio il VM/370;
      - al livello successivo si può trovare uno qualsiasi dei vari altri sistemi operativi standard dell'IBM (che fungono da sottosistemi);
      - mentre al livello più basso vi sono i task degli utenti.
    - i sistemi operativi standard del secondo livello presentano varie macchine virtuali sulla stessa configurazione.
    - la routine di smistamento opera in base ad un algoritmo round robin a due livelli che può essere modificato assegnando delle priorità relative a ciascun sottosistema.
- l'implementazione di una struttura gerarchica dei processi richiede la disponibilità delle seguenti procedure di sistema:
  - 1) crea processo (nome, priorità relativa)
    - consiste nell'impostare un descrittore per il nuovo processo e nell'aggregarlo alla struttura dei processi
  - 2) cancella processo (nome)
  - 3) avvia processo (nome)
    - aggiunge il descrittore di processo alla coda d'attesa al processore, cioè provvede a contraddistinguere il processo in quanto dotato dei requisiti per essere messo in esecuzione
  - 4) arresta processo (nome)
  - arresta processo e cancella processo svolgono invece funzioni inverse e consentono ad un processo padre di controllare i propri processi figli, i quali naturalmente possono terminare spontaneamente, nel qual caso l'impiego di arresta processo diventa superfluo
  - tutte le quattro procedure manipolano i descrittori e le code d'attesa dei processi e, pertanto, dovrebbero essere implementate all'interno del nucleo del sistema.
    - le procedure richiedi risorsa e rilascia risorsa, vengono modificate in modo da richiamare il processo padre invece del gestore delle risorse.
    - il processo padre diviene così responsabile delle allocazioni per i suoi derivati
controllo e contabilità delle risorse
- controllo delle risorse
  - sono così definiti gli aspetti a più lungo termine riguardanti l'allocazione delle risorse, quali:
    - l'addebito relativo all'utilizzo delle risorse
    - la valutazione e l'influsso sull'articolarsi delle richieste
    - la garanzia che tutti gli utenti ottengano una quota adeguata delle risorse di calcolo disponibili
  - nel senso stretto del termine, il controllo delle risorse riguarda più il responsabile dell'elaboratore che il progettista del sistema operativo
    - ma il primo può far ben poco se il secondo non prevede gli strumenti opportuni.
    - in particolare, il progettista deve fornire strumenti atti alla misurazione, poiché senza di questa non è possibile alcun controllo
- gli obiettivi del controllo delle risorse dipendono dalla configurazione interessata:
  - in generale, le configurazioni rientrano in due categorie:
    - per conto terzi
      - il cui scopo consiste nel fornire servizi di calcolo a svariati utenti dietro il pagamento di un corrispettivo
      - sull'utenza non sono imposte limitazioni
      - il controllo delle risorse, pertanto, si riduce alla contabilità, ovvero alla registrazione delle quantità di ogni risorsa addebitabile effettivamente utilizzata ed al conseguente addebito ai clienti
      - sono un esempio di questa categoria le macchine dei centri di elaborazione
    - private
      - è di proprietà di una singola società, università o altro ente e fornisce servizi soltanto a chi ne fa parte.
      - a causa dei vincoli imposti al bilancio, l'amministratore si trova ad affrontare il problema riguardante il soddisfacimento di una domanda di servizi che quasi sempre supera la capacità delle configurazioni
      - contrariamente al centro di elaborazione dati, non si trae nessun profitto dalla fornitura dei servizi e, quindi, solitamente non è aperta la via che porta all'aumento delle potenzialità della macchina, al fine di far fronte alla domanda.
      - l'amministratore dovrà così razionare le risorse disponibili in base all'importanza o ai fabbisogni relativi ai diversi utenti
        
        in tal caso il controllo delle risorse rappresenta uno strumento per differenziare gli utenti che deve adempiere alla duplice funzione di contabilizzare le risorse, garantendo che nessun utente superi la propria quota.
  - i meccanismi di controllo necessari per le configurazioni adibite al servizio per conto terzi sono un sottoinsieme di quelle necessarie per le configurazioni private
- meccanismi di controllo nelle configurazioni private
  - 1) Restrizione dell'accesso
    - l'accesso a quei servizi di sistema che comportano un utilizzo notevole di risorse può essere negato a determinate categorie di utenza, quali i programmatori più giovani o gli studenti.
    - d'altronde, si potrebbe limitare l'attività di utenti operanti in accesso multiplo all'editing ed a prove su piccola scala, mentre agli utenti batch potrebbe essere concesso di spaziare per l'intera gamma delle risorse.
  - 2) Razionamento
    - un metodo di razionamento può essere strutturato sia a lungo che a breve termine, oppure con una soluzione intermedia.
    - il razionamento a breve termine applica un limite alla quantità di risorse, quali il tempo di CPU o lo spazio di memoria, che si possono utilizzare per un singolo lavoro.
    - nel razionamento a lungo termine viene destinata ad ogni utente una determinata riserva (budget) indicante la quantità di risorse di cui può fare uso entro un dato periodo, per esempio in una settimana o in un mese.
    - Qualora l'utente tenti di andare oltre la propria quota si determina l'interruzione del lavoro o il mancato consenso all'accesso al sistema.
  - Entrambi questi metodi di controllo si possono implementare mantenendo un file di contabilità contenente le seguenti informazioni per ogni utente accreditato presso il sistema:
    - 1) identificazione dell'utente.
      - Si tratta di un "numero di conto" citato dall'utente al momento del login o all'inizio della descrizione di un lavoro.
      - Serve al sistema per identificare l'utente.
    - 2) sigla di riconoscimento
      - nota solo al sistema ed all'utente, il quale la presenta a riprova della propria identità.
      - Normalmente nei sistemi di tipo batch non sono necessarie sigle di riconoscimento, in quanto è difficile mantenerne la riservatezza se sono perforate su schede o supporti analoghi
    - 3) "vettore di permessi"
      - in cui ogni bit rappresenta il permesso ad usare una certa risorsa, il quale è accordato solo se il bit relativo è settato a 1.
    - 4) i limiti delle risorse per ogni lavoro.
    - 5) il budget delle risorse per il periodo attuale di contabilizzazione
    - 6) le risorse ancora da utilizzare presenti nel budget per il periodo corrente
- i particolari applicativi del controllo delle risorse variano da sistema a sistema
  - nei sistemi orientati verso applicazioni di tipo batch il saldo delle risorse residue disponibili viene addebitato alla fine di ciascun job ed i lavori sono accettati dal gestore dei processi solo se tale saldo è positivo.
    - in alternativa, si può prevedere l'accettazione di un lavoro solo se i relativi fabbisogni dichiarati di risorse sono inferiori al saldo attuale;
    - con ciò si impedisce che un utente superi la sua razione mettendo in esecuzione un lavoro di entità notevole quando il saldo delle risorse a sua disposizione è quasi nullo
  - in un sistema ad accesso multiplo il saldo può essere addebitato ad intervalli regolari durante una sessione di lavoro al terminale, costringendo l'utente al log-off (a seguito di un avviso in tal senso) nel caso in cui il suo saldo diventi nullo.
- contabilizzare le risorse
  - si può applicare il principio del razionamento singolarmente per ciascuna risorsa oppure, come avviene più comunemente, l'utilizzo di ogni risorsa può essere calcolato in modo composto tramite una formula specifica di addebito, espresso in un tipo di unità riferita al consumo globale di risorse.
    - in tal caso, il peso relativo assegnato ad ogni risorsa presente nella formula viene prescelto in modo da riflettere la scarsa rilevanza o l'importanza della risorsa stessa.
  - un esempio di una formula di addebito simile, presa dal DEC System-10 è il seguente:
    - numero di unità utilizzate = (133,0P + 6,0C + 13,3K + 5,5W)
  - dove
    - P = tempo di CPU in secondi
    - C = tempo di collegamento del terminale in secondi
    - K = occupazione di memoria, cioè l'intero relativo al numero dei blocchi di 1024 word utilizzati nell'intervallo del tempo di CPU
    - W = numero di trasferimenti da disco
  - i parametri di una formula d'addebito possono essere modificati al fine di influenzare il modo in cui lavorano gli utenti
    - ad esempio un aumento considerevole dell'addebito per il tempo di collegamento del terminale spingerebbe gli utenti a fare maggiormente uso delle risorse batch, mentre un aumento dell'addebito per l'occupazione di memoria potrebbe incentivare la riduzione delle dimensioni dei lavori
- un'altra caratteristica importante dei metodi di razionamento consiste nel porre in relazione la quantità totale allocata per ogni risorsa con quella che il sistema riesce a fornire entro un dato periodo di tempo.
  - non è necessario che queste due quantità siano uguali, poiché vi sono buone probabilità che la maggior parte degli utenti non consumi tutte le proprie disponibilità
  - grazie all'esperienza si potrà determinare con buon margine di sicurezza l'entità di un'allocazione eventualmente superiore al dovuto.
  - nel caso delle formule di addebito globale è più difficile far combaciare le allocazioni con le disponibilità, in quanto, se tutti gli utenti decidessero di impiegare la propria quota di allocazione sotto forma della stessa risorsa, il sistema non riuscirebbe più a farvi fronte.
    - in pratica, però, l'esistenza di un vasto numero di utenti rende improbabile questa evenienza
- metodi di razionamento più raffinati (per esempio, Hartley, 1970) possono impiegare tassi d'addebito differenziati a seconda deI momento della giornata.
  - ciò incoraggia l'uso della macchina negli orari meno richiesti e dà luogo ad una distribuzione più uniforme del carico di lavoro.
  - analogamente, gli addebiti possono variare in base alla priorità esterna richiesta da un utente per il proprio lavoro.
- compete al progettista di sistema fornire gli strumenti adeguati per l'implementazione di metodiche quali quelle appena descritte.
  - tra di essi si annoverano:
    - 1. routine per la gestione del file di contabilizzazione;
    - 2. meccanismi per misurare l'utilizzo delle risorse;
    - 3. meccanismi per negare le risorse a quegli utenti che hanno esaurito il budget loro assegnato.
  - la misurazione dell'utilizzo delle risorse è una funzione distribuita in tutto il sistema, in quei punti dove le risorse sono allocate.
    - può essere facilitata enormemente da un hardware opportuno, quale, ad esempio, un contatore nel controllore del disco per registrare il numero dei trasferimenti.
    - per un'accurata misurazione è ovviamente indispensabile un orologio in tempo reale
    - le misurazioni relative ad un singolo processo possono venir memorizzate come parte del descrittore relativo ed i dati statistici sull'impiego complessivo del sistema possono essere raccolti in un file centrale.
      - questi ultimi possono essere ritenuti indicativi delle prestazioni del sistema, ed usati come base di raffronto e di potenziamento.
    - si dovrebbe forse tener conto anche della questione riguardante l'eventuale addebito all'utente degli appesantimenti sul sistema operativo.
      - da un lato si potrebbe sostenere che il sistema operativo agisce per conto dell'utente e che, pertanto, quest'ultimo dovrebbe essere assoggettato ai relativi addebiti.
        
        in tal caso, si otterrebbe pure l'effetto marginale, ma vantaggioso, di stimolare gli utenti a redigere i programmi in modo da contenere al massimo l'aggravio del sistema, per esempio evitando accessi superflui ai file.
      - d'altra parte, gli appesantimenti variano in base al carico di lavoro istantaneo e si potrebbe ritenere ingiusto aumentare l'addebito ad un utente, semplicemente perché la macchina ha molto da fare o perché il suo lavoro interagisce negativamente con qualche altro che si dà il caso sia presente contemporaneamente nel sistema.
      - secondo un'altra argomentazione a sostegno di quest'ultima ipotesi, non è pensabile che l'utente comune acquisisca una conoscenza approfondita del sistema operativo tale da consentirgli di modificare le proprie attività in modo da ridurre gli appesantimenti sul sistema.
      - un compromesso possibile consiste nell'addebitare all'utente tutte quelle attività di sistema, come la gestione dell'I/O, svolte specificamente per lui, tralasciando, invece, le attività indipendenti dalla sua volontà, come, ad esempio, la commutazione dei processi.
        
        anche questa soluzione, comunque, lascia margini di discussione.
        
        per esempio, il movimento dovuto alla paginazione dipende sia dall'utente, il quale può aumentare la localizzazione dei suoi riferimenti in memoria, sia dall'entità delle richieste di memoria.
      - in ultima analisi, le decisioni prese in merito sono necessariamente arbitrarie e vanno lasciate al singolo progettista
riassunto
- in questo capitolo abbiamo visto come si possono implementare i metodi di schedulazione ed allocazione delle risorse nell'ambito di un unico processo, denominato gestore dei processi.
- abbiamo descritto come è possibile assegnare le funzioni di quest'ultimo anche ad altri processi, stabilendo così una lista gerarchica dei processi.
- il nucleo del sistema operativo ipotetico è stato ampliato inserendovi
  - le procedure per creare e cancellare processi
  - i meccanismi per l'allocazione delle risorse e per la misurazione del loro utilizzo
    - che vengono distribuiti in tutto il sistema, ai livelli più opportuni rispetto alle risorse interessate
- Le strutture dati aggiuntive sono:
  - 1. un record delle risorse disponibili;
  - 2. per ogni processo, una lista delle risorse allocate, cui fa riferimento un puntatore nel descrittore relativo;
  - 3. se si impiegano metodi per il riconoscimento di situazioni di stallo, una rappresentazione del grafico di stato;
  - 4. se si impiegano metodi volti ad evitare situazioni di stallo, un record con le richieste e le allocazioni delle risorse;
  - 5. un'eventuale elaborazione della coda d'attesa al processore con l'inclusione di svariati livelli;
  - 6. un'eventuale modifica della lista dei processi per trasformarla in un albero;
  - 7. un file di contabilizzazione