3) Scheduling

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Quali classi di scheduling si occupano dei processi real-time in Linux?

SCHED FIFO e SCHED RR (correct)

SCHED OTHER e SCHED RR

SCHED FIFO e SCHED OTHER

SCHED RR e SCHED OTHER

Qual è il range di priorità per le classi SCHED FIFO e SCHED RR?

1 a 99 (correct)

100 a 139

1 a 140

0 a 100

In quali condizioni può verificarsi la preemption di un processo in esecuzione?

Un processo consuma tutto il suo tempo quantico

I processi di tipo I/O-bound sono sempre privilegiati

Un processo in stato blocked diventa runnable

Entrambi A e B (correct)

Quale priorità è assegnata ai processi SCHED OTHER in Linux?

100 a 139 Signup and view all the answers

Cosa accade quando un nuovo processo diventa eseguibile?

Generalmente soppianta il processo precedentemente in esecuzione Signup and view all the answers

Qual è la funzione principale delle wait queues nel sistema di scheduling di Linux?

Gestire i processi in attesa di richieste di I/O. Signup and view all the answers

Cosa succede alla priorità di un processo in esecuzione nel sistema di scheduling di Linux?

Decresce man mano che il processo viene eseguito. Signup and view all the answers

Qual è la durata ideale del timer interrupt per le applicazioni real-time in Linux?

1 ms Signup and view all the answers

Quali sono i tre tipi di processi gestiti dal sistema di scheduling di Linux?

Interattivi, batch e real-time. Signup and view all the answers

Qual è la principale differenza tra runqueues e wait queues in Linux?

Le runqueues sono specifiche per processore mentre le wait queues sono condivise tra processori. Signup and view all the answers

Qual è l'effetto di un timer interrupt più lungo di 1 ms per le applicazioni real-time?

Causa problemi e ritardi nelle applicazioni real-time. Signup and view all the answers

In che modo il sistema di scheduling di Linux penalizza i processi batch?

Limitando la loro accessibilità alla CPU. Signup and view all the answers

Cosa indica la priorità dinamica nel sistema di scheduling di Linux?

La priorità aumenta o diminuisce a seconda dello stato del processo. Signup and view all the answers

Qual è il problema principale del round robin se i processi vengono eseguiti per troppo tempo?

Degenera in FCFS Signup and view all the answers

Quale affermazione è vera riguardo ai processi CPU-bound in un sistema di round-robin?

Utilizzano tutto il loro quanto di tempo Signup and view all the answers

Qual è una caratteristica del round-robin virtuale rispetto al round-robin semplice?

Favorisce i processi completati che richiedono I/O Signup and view all the answers

Che cosa significa 'Shortest Process Next' (SPN)?

Il processo con il tempo di esecuzione stimato più breve è il prossimo Signup and view all the answers

Qual è un potenziale svantaggio della politica SPN?

Possibilità di starvation per processi lunghi Signup and view all the answers

Cosa si intende per 'predicibilità' dei processi lunghi in un sistema operativo con SPN?

Difficoltà nel prevedere quando verranno eseguiti Signup and view all the answers

Come possono essere stimati i tempi di esecuzione per un processo nella politica SPN?

Basandosi su stime statistica di comportamento passato Signup and view all the answers

Qual è l'effetto del round-robin semplice sulle performance dei processi I/O bound?

Aumenta la variabilità della risposta Signup and view all the answers

Qual è l'obiettivo principale dello scheduling in un sistema operativo?

Assegnare risorse tra processi contemporanei ottimizzando diversi aspetti Signup and view all the answers

Quale tipo di scheduling decide quali programmi sono ammessi nel sistema?

Long-term scheduling Signup and view all the answers

Che cosa si intende per 'starvation' nei sistemi operativi?

Condizione in cui un processo non riceve mai tempo di esecuzione Signup and view all the answers

Quale tra le seguenti affermazioni è VERA riguardo il short-term scheduling?

È inviato alla base di eventi Signup and view all the answers

Qual è il criterio prestazionale per il sistema nello short-term scheduling?

Throughput Signup and view all the answers

In quali situazioni il long-term scheduler può essere attivato?

Quando un processo termina Signup and view all the answers

Quale tra questi tipi di scheduling decide quale processo eseguire tra quelli pronti?

Short-term scheduling Signup and view all the answers

Qual è una delle strategie tipiche del long-term scheduling?

Accodare i lavori batch per l'esecuzione Signup and view all the answers

Cosa significa 'turn-around time' in un sistema operativo?

Tempo tra avvio e completamento di un processo Signup and view all the answers

Quale di queste opzioni descrive meglio il response time?

Tempo che intercorre tra richiesta e inizio della risposta Signup and view all the answers

Quali sono i criteri di prestazione correlati al sistema nello short-term scheduling?

Throughput e utilizzo del processore Signup and view all the answers

Qual è una caratteristica del Medium-Term Scheduling?

Include il passaggio di processi da memoria principale a secondaria Signup and view all the answers

Qual è un criterio non prestazionale per il sistema nello short-term scheduling?

Equità Signup and view all the answers

Cosa deve evitare il sistema operativo per garantire un buon scheduling?

Starvation dei processi Signup and view all the answers

Qual è l'obiettivo principale del throughput?

Maximizzare il numero di processi completati per unità di tempo Signup and view all the answers

Cosa indica l'utilizzo del processore?

Percentuale di tempo in cui il processore è utilizzato Signup and view all the answers

Qual è uno degli obiettivi principali dello scheduler?

Assicurare che le risorse siano utilizzate al massimo Signup and view all the answers

Cosa accade in una politica di scheduling non-preemptive?

Un processo in esecuzione termina solo se richiede I/O Signup and view all the answers

Qual è una caratteristica del metodo Round-Robin?

Applica la preemption basata su un clock Signup and view all the answers

Quale delle seguenti affermazioni è vera riguardo alla starvation?

Si verifica quando un processo a bassa priorità non ottiene mai tempo di CPU Signup and view all the answers

Quale degli aspetti è considerato nella funzione di selezione dei processi?

Il tempo trascorso in attesa e in esecuzione Signup and view all the answers

In che cosa consiste il time slicing nel contesto del Round-Robin?

Assegnare un tempo fisso a ciascun processo Signup and view all the answers

Qual è l'effetto di avere un tempo di preemption troppo breve?

Può causare inefficienze e aumentare l'overhead Signup and view all the answers

Qual è una caratteristica di un sistema preemptive?

I processi possono essere sospesi in qualsiasi momento Signup and view all the answers

Cosa implica una politica di scheduling equa?

Evitare favoritismi e garantire accesso equo Signup and view all the answers

Qual è un vantaggio del metodo FCFS?

Semplicemente implementabile Signup and view all the answers

Cosa si intende per 'starvation' in un sistema operativo?

Un processo attende troppo a lungo senza avere accesso alla CPU Signup and view all the answers

Quale dei seguenti non è un criterio di bilanciamento delle risorse?

Favorire i processi CPU-bound Signup and view all the answers

Qual è la formula per predire il tempo di esecuzione in un sistema che utilizza il metodo batch?

Sn+1 = αTn + (1 − α)Sn Signup and view all the answers

In quale scenario un processo può essere interrotto in modo preemptive?

Quando ne arriva uno nuovo Signup and view all the answers

Qual è l'obiettivo principale dell'algoritmo HRRN?

Massimizzare il rapporto risposta Signup and view all the answers

Quale affermazione riguarda correttamente il processo di scheduling tradizionale di UNIX?

Combina priorità e round robin Signup and view all the answers

Qual è la principale differenza tra l'assegnamento statico e l'assegnamento dinamico dei processi nelle architetture multiprocessore?

Con l'assegnamento statico, un processo rimane su un solo processore Signup and view all the answers

In un sistema con Exponential Averaging, quale valore di α è corretto?

0 < α < 1 Signup and view all the answers

Cosa determina la priorità di un processo in UNIX?

Il valore di nice e base Signup and view all the answers

Qual è il principale vantaggio dell'assegnamento statico in un sistema multiprocessore?

Meno overhead Signup and view all the answers

Cosa distingue l'algoritmo SRT dagli altri metodi di scheduling?

E' un metodo preemptive Signup and view all the answers

Qual è l'effetto dell'esecuzione prolungata di un processo in UNIX?

Viene declassato in una coda di bassa priorità Signup and view all the answers

In un sistema SRT, quando un nuovo processo arriva, cosa deve accadere?

Il processo attuale può essere interrotto se il nuovo ha un tempo di esecuzione minore Signup and view all the answers

Qual è la definizione corretta di Exponential Averaging?

Sn+1 = αTn + (1-α)Sn Signup and view all the answers

Quale di queste non è una caratteristica dello scheduling tradizionale in UNIX?

Utilizza long-term e medium-term scheduling Signup and view all the answers

Study Notes

Sistemi Operativi - Modulo I - Lo Scheduling

Un sistema operativo deve allocare risorse tra diversi processi che ne fanno richiesta contemporaneamente.
Tra le risorse disponibili, c'è il tempo di esecuzione, fornito dal processore.
Questa risorsa viene allocata tramite lo scheduling (pianificazione).

Scopo dello Scheduling

Assegnare ad ogni processore i processi da eseguire, man mano che vengono creati e distrutti.
Ottimizzare vari aspetti per raggiungere questo obiettivo:
- Tempo di risposta
- Throughput
- Efficienza del processore

Obiettivi dello Scheduling

Distribuire equamente (fair) il tempo di esecuzione tra i processi, senza favoritismi.
Gestire le priorità dei processi quando necessario, ad esempio, in situazioni di tempo reale.
Essere equo tra processi con la stessa priorità, con favoritismi solo se giustificati.
Evitare la starvation (morte per fame) dei processi.
Usare il processore in modo efficiente.
Minimizzare l'overhead.

Tipi di Scheduling

Long-term scheduling (di lungo termine): decide quali programmi aggiungere al sistema per l'esecuzione. Spesso utilizza la strategia FIFO (First-In, First-Out).
Medium-term scheduling (di medio termine): gestisce il passaggio tra memoria principale e memoria secondaria (swapping).
Short-term scheduling (di breve termine): decide quale processo tra quelli pronti deve essere eseguito dal processore. E' chiamato anche dispatcher.
I/O scheduling (per input/output): decide a quale processo assegnare un dispositivo I/O quando necessario.

Stati dei Processi

Il sistema operativo gestisce i processi attraverso diversi stati, come illustrato dal modello a 7 stati.
Questi stati sono interconnessi tramite transizioni di decisione.

Code dei Processi e Scheduling

I processi vengono gestiti attraverso diverse code.
Queste code sono gestite da diversi scheduler, ognuno dei quali ha un ruolo specifico nello scheduling dei processi

Long-Term Scheduling

Decide quali programmi devono essere ammessi nel sistema.
Spesso utilizza la strategia FIFO (First-In, First-Out).
Considera criteri come le priorità, i requisiti per le operazioni di input/output (I/O) e i tempi di esecuzione stimati.
Controlla il grado di multiprogrammazione.
Più processi ci sono, più è piccola la percentuale di tempo per cui ogni processo viene eseguito.

Medium-Term Scheduling

Gestisce la swapping
Necessario per gestire il grado di multiprogrammazione

Short-Term Scheduling

Chiamato anche Dispatcher, è responsabile dell'allocazione del tempo di esecuzione del processore.
Invocato sulla base di eventi: interruzioni di clock, interruzioni I/O, chiamate di sistema o segnali.

Scopo dello Short-Term Scheduling

Allocare il tempo di esecuzione per ottimizzare le prestazioni del sistema, basandosi su indici prestazionali.
Occorre definire criteri prima di valutare una politica di scheduling.

Criteri per lo Short-Term Scheduling

Utente vs Sistema:
- Per l'utente: tempo di risposta (da una richiesta all'output)
- Per il sistema: uso efficiente ed effettivo del processore
Prestazioni:
- Tempo di risposta
- Tempo di turnaround (tempo tra la creazione/invio di un processo e il suo completamento)
- Scadenza (deadline)
- Throughput (volume di lavoro in un determinato tempo)
- Utilizerro del processore
- Predicibilità
- Equità (fairness)
- Bilancia delle risorse

Turnaround Time

Tempo tra la creazione (invio) di un processo e il suo completamento.
Include i tempi di attesa per I/O e il processore.

Response Time

Tempo tra la richiesta di un'operazione e l'inizio della risposta.

Deadline e Predicibilità

Nei casi con scadenze predefinite, lo scheduler dovrebbe prima massimizzare il rispetto delle scadenze.
Importante evitare una variabilità eccessiva nei tempi di risposta/ritorno.

Throughput

Massimizzare il numero di processi completati per unità di tempo.

Utilizzo del Processore

Percentuale di tempo in cui il processore è impegnato.
Obiettivi: Maximizzare il tempo di utilizzo del processore Minimizzare il tempo di inattività del processore

Bilanciamento delle Risorse

Garantire l'utilizzo ottimale delle risorse di sistema.
Favorire i processi che utilizzano meno le risorse attualmente più occupate.

Fairness e Priorità

Tutti i processi devono essere trattati equamente senza favoritismi a meno di priorità esplicitamente indicate
In caso di priorità, si devono favorire i processi con priorità più alta.

Priorità e Starvation

Processi con bassa priorità possono essere soggetti a starvation.
Per ridurre tale problema, la priorità dei processi può essere incrementata con il tempo

Politiche di Scheduling

Diverse strategie di scheduling per gestire i processi (ad esempio: FCFS, Round Robin, SPN, SRT, HRRN, Feedback).
Ogni strategia presenta caratteristiche diverse (preemptività, tempo di risposta, overhead)

Funzione di Selezione

Sceglie il processo da mandare in esecuzione.
Considera caratteristiche di esecuzione, tempi di attesa e tempi di elaborazione, oltre ad eventuali parametri specifici.

Modalità di Decisione

Preemptive: Il SO può interrompere un processo in esecuzione per assegnare il processore ad un altro.
Non-preemptive: Il SO non interrompe un processo in esecuzione.

Preemptive e Non-Preemptive

Non-preemptive: Il processo mantiene il controllo del processore fino al completamento o fino a quando non richiede una I/O.
Preemptive: Il sistema operativo può interrompere la CPU a un processo in esecuzione. Eventi trigger quali I/O, arrivi di nuovi processi o interruzioni di clock possono causare tale interruzione. Questo evita che un processo monopolizzi il processore.

Concetti Fondamentali

Funzione di selezione: sceglie il processo da eseguire.
Modalità di decisione:
- Non-preemptive: processi restano in esecuzione fino al termine o alla richiesta I/O.
- Preemptive: processi possono essere interrotti dal sistema operativo per dare tempo ad altri processi.

Scenario Comune di Esempio

Esempio di 5 processi batch con tempi di arrivo e di esecuzione.

FCFS (First-Come-First Served)

Processi aggiunti alla coda dei processi pronti (ready queue) in ordine di arrivo
Processo che ha aspettato più a lungo viene selezionato per l'esecuzione.
Non preemptive: il processo resta in esecuzione fino alla fine o ad una richiesta di I/O.

Round-Robin

Impiega la preemption basata su un clock.
Ogni processo riceve un periodo di tempo (time slice) per l'esecuzione.

Round-Robin: un Po’ per Ciascuno

Usa la preemption, basandosi su un clock (time slicing). Ogni processo ha un tempo limite di esecuzione.
Quando l'interruzione di clock si verifica, il processo in esecuzione viene ricollocato nella coda dei processi pronti.

Misura del Quanto di Tempo per la Preemption

Il quanto di tempo va determinato in modo da essere superiore al tipico tempo di interrogazione.
Se il quanto di tempo è inferiore al tempo di interrogazione, la preemption può portar a non ottimali prestazioni.

CPU-bound vs I/O bound

Processi CPU-bound richiedono gran parte del tempo di CPU.
Processi I/O-bound spendono tempo aspettando operazioni di I/O.
Con alcune strategie, i processi CPU-bound potrebbero essere favoriti rispetto agli I/O-bound
Per migliorare l'equità tra processi bound alla CPU e ai processi bound all'I/O, può essere usata un'operazione chiamata "round-robin virtuale".

Round-Robin Virtuale

I processi che terminano le operazioni di input/output (I/O) passano ad una coda di priorità più alta

SPN (Shortest Process Next)

Letteralmente: il prossimo processo è quello più breve.
Per "breve" si intende processo con tempo stimato di esecuzione minore rispetto agli altri.
Processi corti scavalcano processi più lunghi.
Non preemptive: il processo resta in esecuzione fino a completamento o I/O.

SPN: Come Stimare il Tempo di Esecuzione?

Utilizzare il tempo di esecuzione passato per stimare il tempo futuro.
La tecnica di Exponential Averaging gestisce diverse stime passate con diversi pesi a seconda della loro distanza temporale, così da dare più rilevanza alle ultime stime.

Exponential Averaging: Coefficienti

Metodi utilizzati per ponderare le osservazioni passate con diversi pesi, ad esempio i valori recenti, riducendo l'influenza delle osservazioni obsolete

SRT (Shortest Remaining Time)

Come SPN, ma preemptive.
Il processo più breve rimanente viene selezionato per l'esecuzione.
Il sistema può interrompere un processo in esecuzione per processarne uno nuovo ancora più breve.
Stima il tempo rimanente per l'esecuzione del processo e seleziona quello più breve

HRRN (Highest Response Ratio Next)

Massimizza un rapporto tra il tempo di attesa e il tempo richiesto per l'esecuzione del processo.

Confronto

Confronto delle varie strategie.

Scheduling tradizionale di UNIX

Combinazione di priorità e round robin.
Priorità dinamiche che diminuiscono con l'utilizzo.

Formula di Scheduling

Formula utilizzata per calcolare la priorità dei processi.
Si tiene conto del tempo di utilizzo della CPU in un intervallo di tempo, ponderando valori precedenti.

Esempio di Scheduling su UNIX

Esempio di scheduling su UNIX con diverse priorità e processi.

Architetture Multiprocessore

Cluster: processori indipendenti con rete veloce.
Multi-processore/multi-core: processori che condividono la RAM.

Scheduler su Architetture Multiprocessore

Assegnamento statico: ogni processo viene assegnato ad un processore specifico durante la sua durata di esecuzione.
Assegnamento dinamico: un processo può essere assegnato a diversi processori durante la sua durata per ridurre il tempo di attesa.

Scheduling in Linux

Strategie utilizzate in Linux per lo scheduling, con diversi tipi di processi (interattivi, batch, real-time) e le loro priorità.

###Scheduling in Linux: Regole Generali

Regole che guidano la gestione dei processi in Linux.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Questo quiz esplora le classi di scheduling in Linux, in particolare per i processi real-time. Scoprirai dettagli sulle priorità delle classi SCHED FIFO e SCHED RR, nonché sulle condizioni di preemption e sulle priorità dei processi SCHED OTHER. Testa e amplia la tua conoscenza sull'argomento con queste domande!