Sistemi Operativi - Appunti Teoria Prima Parte

SCHEDULING DEI PROCESSI

L’obbiettivo della multiprogrammazione consiste nel disporre dell’esecuzione contemporanea di alcuni processi in modo da

massimizzare l’utilizzo della CPU. Se esistono più processi, quelli che non sono in esecuzione devono aspettare che la CPU sia libera

e la loro esecuzione possa essere ripresa. Lo scheduler dei processi seleziona un processo da eseguire tra quelli disponibili.

Code di scheduling

Ogni processo è inserito in una coda di processi del sistema. I processi

presenti nella memoria centrale, che sono pronti e nell’attesa d’essere eseguiti

si trovano in una lista concatenata detta coda dei processi pronti (Ready

Contiene puntatori al primo e all’ultimo PCB dell’elenco.

queue). Ogni PCB è

esteso con un campo puntatore che indica il successivo processo contenuto

nella coda dei processi pronti. Quando si assegna la CPU a un processo,

quest’ultimo rimane in esecuzione per un certo tempo e prima o poi termina,

viene interrotto, oppure si ferma nell’attesa di un evento particolare (es.

L’elenco dei processi che

completamento di una richiesta di I/O). attendono la

disponibilità di un particolare dispositivo di I/O si chiama coda del dispositivo;

ogni dispositivo ha la propria coda (Figura). Una comune rappresentazione dello

scheduling dei processi è il diagramma di accodamento (Figura). Ogni riquadro

rappresenta una coda. Ci sono due tipi di coda: la coda dei processi pronti e un

insieme di code di dispositivi. I cerchi rappresentano le risorse che servono le code,

le frecce indicano il flusso di processi nel sistema. Un nuovo processo si colloca

inizialmente nella coda dei processi pronti, dove attende finchè non è selezionato

per essere eseguito (dispatched). Una volta che il processo è assegnato alla CPU ed

è nella fase d’esecuzione, si può verificare uno di questi eventi: Il processo

 può emettere una richiesta di I/O e quindi essere inserito in una coda di I/O

 può creare un nuovo processo e attenderne la terminazione

 dalla CPU a causa di un’interruzione ed essere reinserito nella coda

può essere rimosso forzosamente dei processi pronti.

Nei primi due casi il processo passa dallo stato d’attesa allo stato pronto ed è nuovamente inserito nella coda dei processi pronti. Un

processo continua questo ciclo finche la sua esecuzione termina, cioè fino alla rimozione da tutte le code, e la rimozione il suo PCB e

si revocano le varie risorse.

Scheduler

Il sistema operativo incaricato di selezionare i processi dalle code, compie questa selezione per mezzo di uno scheduler. Ci sono tre

tipi di scheduler che si differenziano principalmente per la frequenza con la quale sono eseguiti:

 Scheduler a breve termine: Seleziona frequentemente un processo per la CPU tra i lavori pronti per essere eseguiti. Questo

processo può essere in esecuzione solo per pochi ms prima di passare ad attendere una richiesta I/O. Deve essere rapido.

 Scheduler a lungo termine: Nel caso di sistemi batch esiste uno scheduler che seleziona quali processi caricare in memoria

affinchè possano essere eseguiti. Deve entrare in azione ogni volta che avviene il completamento di un processo, in modo

che il numero di processi in memoria sia costante (controlla il grado di multiprogrammazione). E' necessario che selezioni

la giusta combinazione di processi cpu-bound (processo di elaborazione che richiede poche operazioni di I/O e impiega la

maggior parte del proprio tempo nelle elaborazioni) e I/O bound (processo con prevalenza di I/O che impiega la maggior

parte del proprio tempo nell’esecuzione di operazioni di I/O) per ottenere le prestazioni migliori. Si esegue con una

frequenza molto inferiore: tra la creazione di nuovi processi possono trascorrere diversi minuti.

 E’ introdotto solo in alcuni SO.

Scheduler a medio termine: Ha una funzionalità intermedia rispetto agli scheduler a breve e

lungo termine. Serve a limitare temporaneamente il numero di processi contemporaneamente in memoria (swapping -

figura). Può rimuovere processi dalla memoria e

così ridurre il grado di multiprogrammazione;

successivamente può reintrodurre il processo nella

memoria e riprendere la sua esecuzione dal punto

in cui era stata abbandonata.

Le politiche di scheduling sono:

 Non abbandonare un processo (giustizia)

 Eseguire prima i più importanti (priorità) senza

però trascurare gli altri

 Considerare le deadlines (real-time)

 Ottimizzazione (performance)

Context Switch (Cambio di contesto)

In presenza di una interruzione, il sistema deve salvare il

contesto del processo corrente, per poterlo poi ripristinare

quando il processo stesso potrà ritornare in esecuzione. Il contesto è rappresentato all’interno del PCB del processo, e comprende i

valori dei registi della CPU, lo stato del processo e informazioni relative alla gestione della memoria. Quindi, si esegue un salvataggio

dello stato corrente della CPU, sia in modalità utente o in modalità di sistema; in seguito si ripristinerà lo stato per poter riprendere

l’elaborazione dal punto in cui era stata interrotta. Quindi, il passaggio della CPU ad un nuovo processo implica la registrazione

(salvataggio) dello stato del vecchio nel suo PCB e il caricamento dello stato precedentemente registrato del nuovo. Questa procedura

viene chiamata cambio di contesto (che comporta un calo delle prestazioni). Cosa salvare? Dipende dalla macchina: registri general-

purpose & floating point, stato del processore, altri registri. Il tempo necessario per il cambio di contesto è il sovraccarico (Overhead)

e più è complesso il SO più lavoro si deve svolgere durante un cambio di contesto. Infatti il sistema non compie nessun lavoro utile

durante la commutazione e varia da calcolare a calcolatore secondo la velocità della memoria, il numero di registri che si devono

copiare e l’esistenza di istruzioni speciali. Come salvare lo stato senza corrompere nessun registro?

 CISC: istruzioni singole per salvare i registri nello stack

 RISC: tecniche particolari per salvarne uno alla volta

Come l'SO prende il controllo sottraendo il kernel nei processi di esecuzione in quel momento?

Traps: eventi generati dal processo corrente

 system calls

 errori (istruzioni illegali)

 page faults

Interrupts: eventi esterni al processo

 I/O interrupt

 timer interrupt (ogni 100 millisecondi circa)

Dal punto di vista del processo:

 esplicito: il processo lascia il processore ad un altro

 implicito: a causa di un evento bloccante (switched)

OPERAZIONI SUI PROCESSI

Creazione dei processi

Durante la propria esecuzione, un processo può creare nuovi processi tramite una chiamata (system calls). Colui che crea un processo

viene chiamato processo padre, il nuovo processo invece figlio. Ogni processo crea un altro processo e si inizia a formare un albero di

processi. Le risorse del figlio sono date dal SO oppure da un sottoinsieme delle risorse del padre. Limitando le risorse del processo

genitore, si può evitare il sovraccarico del sistema dovuto alla creazione di troppi sottoprocessi. Oltre alle varie risorse fisiche e

logiche, un processo appena creato ottiene dal genitore dati di inizializzazione. Quando un

processo crea un nuovo processo, riguardo all’esecuzione ci sono due possibilità:

 Il processo genitore continua l’esecuzione in modo concorrente con i propri

processi figli

 Il processo genitore aspetta (wait) che alcuni o tutti i suoi processi figli terminino

Ci sono due possibilità anche per lo spazio d’indirizzi del nuovo processo:

 Il processo figlio è un duplicato del processo genitore

 Nel processo figlio si carica un nuovo programma (exec)

Un altro esempio è fork/exec in Unix dove un nuovo processo si crea

per mezzo della chiamata del sistema fork() ed è composto di una copia

dello spazio degli indirizzi di un processo. Ciò permette al genitore di

comunicare con il figlio. Entrambi i processi continuano l’esecuzione

successiva alla chiamata del sistema fork().

dell’istruzione Dopo di

essa uno dei due processi esegue una exec () per sostituire lo spazio di

memoria del programma, in file binario, contenente la stessa chiamata

del sistema exec() del processo con un nuovo programma, quindi avvia

la sua esecuzione. I pro sono: Semplice, pulito; i contro: operazioni

duplicate. Il prototipo è: pid_t fork(); dove pid t è definito negli

include di sistema e di solito corrisponde ad un tipo intero. Il valore

restituito da fork può essere usato per distinguere processo genitore e

processo figlio, assegnando questo valore al pid del padre: se pid è < 0

è fallito la creazione del processo, stampo il messaggio di errore,

perché -1 è il valore del pid del padre; se è = 0, sono nel figlio ed eseguo la ls; altrimenti se è > 0, la creazione è andata a buon fine,

perché il padre ha come PID quello del figlio, il figlio ha come valore 0, con wait blocco il padre finchè il processo figlio non termina.

Terminazione di processi

Un processo termina quando finisce l’esecuzione della sua ultima istruzione e chiede al SO di essere cancellato usando exit(). Tutte le

risorse del processo sono liberate così dal SO. E’ possibile che un processo causi la terminazione di un altro processo con

TerminateProcess() (solo il padre al figlio). Il padre conosce l'identità del figlio (PID) e può terminare il suo processo per vari motivi:

1. Troppe risorse

2. Non è più necessario

3. Il padre termina e OS non lascia continuare il figlio (terminazione a cascata - es: VMS, UNIX)

4. LINUX: sen un processo genitore termina, tutti i suoi processi figli sono affidati al processo init(), che assume il ruolo di

nuovo genitore, cui processi figli possono riportare i risultati delle proprie attività.

COMUNICAZIONE FRA PROCESSI

Comunicazione tra processi (IPC)

I processi devono condividere lo stesso accesso a un vettore di memoria e il codice deve essere scritto esplicitamente dal

programmatore che crea l’applicazione. Attraverso le funzioni di IPC, i processi possono comunicare tra loro e sincronizzare le

proprie azioni senza condividere lo stesso spazio di indirizzi. IPC è utile dove i processi comunicanti possono risiedere in diversi

calcolatori connessi ad una rete. OS fornisce strumenti per la comunicazione (IPC): Pipes, FIFOs, Semafori, Messaggi, Regioni di

memoria condivisa

Interazione dei Processi

I processi in esecuzione nel SO possono essere:

 Processi indipendenti: Non condividono dati e non si influenzano tra di loro

 Processi cooperanti:

Condivisione d’informazioni:

1. Influenza e può essere influenzato da altri processi in esecuzione nel sistema