SCHEDULER: componente del sistema operativo che seleziona un processo in stato di ready e lo elegge in stato di running
Fairness: la CPU deve essere distribuita in modo equo tra i processi.
Policy Enforcement: la politica di scheduling è l’unica a assegnare alla CPU dei processi da eseguire
Balance: il sistema di scheduling deve tenere occupata la CPU sempre
I PROCESSI HANNO 2 STATI
I processi si distinguono in 2 tipologie:
CPU-bound → uso prolungato della CPU
I/O-bound → breve uso di cpu (detto burst di CPU) pk nel complesso prioritizzano l’acceso alle periferiche che impiegano del tempo a svolgere le operazioni richieste dai processi
TIPI DI SISTEMI DI SCHEDULING
Si sono evoluti insieme ai sistemi di calcolo per soddisfare esigenze specifiche di ciascun modello
Diagramma di Gantt
L'analisi delle prestazioni di un meccanismo di scheduling viene rappresentata attraverso un diagramma di Gantt, che mostra quale processo sta usando la CPU in un determinato momento.
Asse X: Il tempo che scorre.
asse y:Processi che accedono alla CPU
per BATCH MULTIPROGRAMMATI:smaltire il maggior numero di job nell’unità di tempo
PARAMETRI DI VALUTAZIONE
Throughput
Numero jobs eseguiti completamente nell’unità di tempo
Turnaround-Time
intervallo di tempo tra l’istante in cui è sottomesso al sistemae la fine della sua esecuzione
istante di sottomissione dal sistema: momento in cui il sistema operativo viene informato della necessità di un processo per un preciso compito
CPU Utilization: tasso di utilizzo della CPU, che deve sempre essere al lavoro
MECCANISMI DI SCHEDULING SUI SITEMI BATCH MULTIPROGRAMMATI
FCFS (First Come First Served)
FUNZIONAMENTO
non preemptive significa che nn fa allocazione dinamica: una volta che un processo ottiene la CPU, rimane in esecuzione fino al completamento
I processi sono schedulati nell'ordine di arrivo.
Se due processi hanno lo stesso tempo di arrivo, il sistema può scegliere arbitrariamente quale processo eseguire per primo
SENSIBILITA’
L'algoritmo FCFS funziona, ma è altamente sensibile all'ordine con cui i processi vengono schedulati.
Se i processi vengono ordinati in modo diverso,
ad esempio: prima P2, poi P3, infine P1, I risultati dei tempi di risposta medi e dei tempi di turnaround medi saranno completamente diversi rispetto a un altro ordine di esecuzione.
Ogni volta che un processo arriva, l'algoritmo controlla tutti i processi disponibili e sceglie quello con il tempo di esecuzione rimanente più breve.
VANTAGGI
Questo sistema migliora drasticamente sia il tempo di risposta medio che il tempo di turnaround medio.
UTOPIA
Nella realtà , quando un processo nasce, non è possibile sapere con esattezza quanto durerà la sua esecuzione.
quindi viene utilizzato come punto di riferimentoper valutare quanto un algoritmo di scheduling si avvicina alle prestazioni ottimali fornite dall'SRTF.
per risposta INTERATTIVA: minimizzare il tempo di risposta dell'interfaccia utente (senza vincoli temporali)
PARAMETRI DI VALUTAZIONE
Response Time (Tempo di Risposta)
È il tempo che intercorre tra l’istante in cui si sottomette un processoal sistema e l’istante in cui questo comincia a produrre output
Esempio: Nel caso di un'applicazione come Microsoft Word, il tempo di risposta è il tempo che intercorre tra il doppio clic per avviare il programma e il momento in cui possiamo iniziare a scrivere.
Proportionality (Proporzionalità )
Il sistema deve rispondere velocemente e deve adattarsi alle aspettative dell’utente in base al contesto
Esempi:
In un videogioco, ci si aspetta che il sistema risponda in meno di 1/60 di secondo, altrimenti l’esperienza di gioco sarà compromessa.
Ogni processo ha diritto a un turno sulla CPU per una durata massima pari al quanto di tempo
Esempio: Se il quanto di tempo è di 20 unità , ogni processo può utilizzare la CPU per 20 unità di tempo consecutive
Prelazione:
Se un processo esaurisce il quanto di tempo senza terminare, viene interrotto e rimesso in coda
La CPU passa al processo successivo nella coda Ready
CODA READY
per memorizzare i processi in attesa e definire un ordine di partenza, basato sul tempo di arrivo: chi arriva prima ha accesso alla CPU, a parità di tempo di arrivo si prioritizza il processo con tempo di burst più breve
Quando il quanto di tempo scade, il processo non ancora terminato viene rimesso in fondo alla coda, mentre il processo successivo nella coda viene schedulato immediatamente.
OTTIMIZZAZIONE ULTERIORE
Il tempo medio di risposta può essere migliorato riducendo il quanto di tempo
Questo miglioramento è rappresentato dall’area del triangolo che si forma all’inizio del diagramma di Gantt. Ridurre il quanto di tempo equivale a schiacciare il triangolo, migliorando il tempo di risposta medio.
SENZA ESAGERARE
Ridurre eccessivamente il quanto di tempo può aumentare il tempo di commutazione del contesto (context switch): ovvero salvataggio stato del processore e caricamento risorse per il processore successivo
Queste operazioni sono veloci, ma non a tempo zero, quindi un quanto troppo breve può causare un tempo di risposta maggiore
SCHEDULING CON PRIORITA’
STATICO: quando arriva un processo, definisco da subito il suo livello di priorità e rimane permanente per tutto il suo ciclo di vita
DINAMICO: il livello di priorità di un processo è mutevole nek tempo in base a determinata parametri monitorati dallo scheduler:
definisco più code, ciascuna associata a un livello di priorità .
Quando un processo viene creato o monitorato, viene inserito nella coda corrispondente in base alla sua prioritÃ
Il livello di priorità viene stabilito monitorando le sue prestazioni dai primi quanti di tempo e memorizzati nel PCB
I/O -bouond: priorità alta
CPU-bound: priorità bassa
scheduler sceglie sempre il primo processo nella coda a priorità più alta
quando i processi in basso aspettano da troppo tempo il loro turno gli si alza di livello per evitare lo stato di starvation
altre varianti
GUARANTEED SCHEDULING
Se ci sono n processi in esecuzione, ogni processo dovrebbe ricevere circa 1/n del tempo della CPU
n = numero di processi
1/n*100 = valore percentuale di tempo garantito per ogni processo
Il 100% del tempo CPU non è un valore fisso, ma è deciso dal sistema operativo ad esempio 1 secondo
Priorità più alta: Viene scelto il processo che ha ricevuto meno tempo CPU rispetto alla sua quota prevista, da nn confondere col qusanto
questo sistema è applicabile solo quando lo scheduler ha accumulato delle statiche affidabili basate su un sistema di priorità preesistente
PROBLEMA
inefficiente se il numero di PCB da controllare è alto
LOTTERY
sistema operativo = lotteria.
Il sistema genera un numero di ticket (biglietti)
I processi che devono essere schedulati, ricevono questi biglietti in modo non uniforme, cioè alcuni processi possono ricevere più biglietti di altri, a seconda delle loro esigenze o priorità .
Durante il periodo di schedulazione, viene effettuata una estrazione casuale per determinare quale processo avrà il diritto di eseguire.
l’estrazione casuale evita la starvation pk non garantisce la selezione dei processi con più biglietti
l’estrazione è imprevedibile ed imparziale
FAIR SHARING
è simile al Guaranteed Scheduling, ma pone un cambio di prospettiva. La distribuzione equa del tempo per usare la CPU non avviene su ogni processo, ma su ogni utente che usa il processo.
Quindi per garantire che ogni utente usi la sua quota, la priorità nn è calcolata sul processo ma sull’utente (in un contesto in presenza di più utenti che usano la stessa macchina)
N thread in spazio kernel, comandano M thread in spazio utente
FUNZIONAMENTO
lo scheduler del sistema decide quale thread in spazio kernel eseguire
lo scheduler specifico del programma (situato nella libreria thread) determina quale thread in spazio utente eseguire nello specifico (il sistema operativo nn vede i thread in spazio utente)
libreria dei thread
software che gestisce i thread in spazio utente
è una componente interna di un'applicazione
per risposta Real-Time: garantire il rispetto delle scadenze temporali per operazioni sensibili al tempo.
HARD REAL-TIME→ può causare il fallimento completo del sistema o gravi danni. Ad esempio, un airbag che non si attiva in tempo durante un incidente.
SOFT REAL-TIME → può solo ridurre la qualità del servizio. Ad esempio lo streaming di un videogioco
Predictability: capacità di sapere in anticipo se un sistema sarà in grado di gestire il carico di lavoro previsto e rispettare tutte le scadenze richieste.
MECCANISMI DI SCHEDULING PER I SISTEMI REAL-TIME
RMS → senza prelazione
EDF(Earliest Deadline First) → sistemi REAL-TIME
Non esistono ancora scheduler real-time che garantiscano un funzionamento ottimale in tutte le situazioni.
FUNZIONAMENTO
viene mandato in esecuzione il processo a cui manca meno tempo per raggiungere la sua scadenza
Made with Bullet