Pianificazione della CPU Algorithms in Operasistemi di ting

Cos'è la pianificazione della CPU?

Pianificazione della CPU La pianificazione della CPU è un processo che determina quale processo occuperà la CPU per l'esecuzione mentre un altro processo è in attesa. Il compito principale della pianificazione della CPU è garantire che, ogni volta che la CPU rimane inattiva, il sistema operativo selezioni almeno uno dei processi disponibili nella coda dei processi pronti per l'esecuzione. Il processo di selezione viene effettuato dallo scheduler della CPU, che seleziona uno dei processi in memoria pronti per l'esecuzione.

Tipi di pianificazione della CPU

Ecco due tipi di metodi di pianificazione:

Programmazione preventiva

Nella pianificazione preemptive, le attività vengono assegnate principalmente in base alle loro priorità. Talvolta è importante eseguire un'attività con priorità più alta prima di un'altra attività con priorità inferiore, anche se quest'ultima è ancora in esecuzione. L'attività con priorità inferiore rimane in attesa per un certo periodo di tempo e riprende l'esecuzione quando l'attività con priorità più alta termina la sua esecuzione.

Pianificazione non preventiva

In questo tipo di metodo di pianificazione, la CPU viene assegnata a uno specifico processo. Il processo che mantiene la CPU occupata la rilascerà cambiando contesto o terminando. È l'unico metodo utilizzabile su diverse piattaforme hardware, poiché non richiede hardware speciale (ad esempio, un timer) come la pianificazione preemptive.

Quando la pianificazione è preventiva o non preventiva?

Per determinare se la pianificazione è preemptive o non preemptive, si considerino questi quattro parametri:

1. Un processo passa dallo stato di esecuzione allo stato di attesa.
2. Un processo specifico passa dallo stato di esecuzione allo stato di pronto.
3. Un processo specifico passa dallo stato di attesa allo stato di pronto.
4. Un processo termina la sua esecuzione e si conclude.

Se si verificano solo le condizioni 1 e 4, la pianificazione è detta non prelativa. Tutte le altre situazioni di pianificazione sono prelative.

Terminologia importante relativa alla pianificazione della CPU

• Tempo di burst/Tempo di esecuzione: Il tempo necessario a un processo per completare l'esecuzione. È anche detto tempo di esecuzione.
• Orario di arrivo: Il momento in cui un processo entra nello stato di pronto.
• Tempo finale: Il momento in cui un processo si completa ed esce dal sistema.
• Multiprogrammazione: Numero di programmi che possono essere presenti in memoria contemporaneamente.
• Lavori: Un tipo di programma che non prevede alcuna interazione con l'utente.
• Utente: Un tipo di programma che prevede l'interazione con l'utente.
• Processo: Il riferimento utilizzato sia per un lavoro che per un utente.
• Ciclo burst CPU/IO: Descrive l'esecuzione del processo, che alterna attività della CPU e attività di I/O. I tempi della CPU sono generalmente più brevi dei tempi di I/O.

Criteri di pianificazione della CPU

Un algoritmo di pianificazione della CPU cerca di massimizzare e minimizzare quanto segue:

Massimizzare

Utilizzo della CPU: L'utilizzo della CPU è il compito principale per cui il sistema operativo deve assicurarsi che la CPU rimanga il più occupata possibile. Può variare dallo 0 al 100%. Tuttavia, per un RTOS, può variare dal 40% per un sistema di basso livello al 90% per un sistema di alto livello.

Throughput: Il numero di processi che terminano la loro esecuzione per unità di tempo è noto come throughput. Quindi, quando la CPU è impegnata nell'esecuzione di un processo, viene svolto del lavoro e il lavoro completato per unità di tempo è chiamato throughput.

Ridurre al minimo

Tempo di attesa: Il tempo di attesa è la quantità di tempo che un determinato processo deve attendere nella coda dei processi pronti.

Tempo di risposta: Si tratta del lasso di tempo che intercorre tra l'invio della richiesta e la ricezione della prima risposta.

Tempo di consegna: Il tempo di completamento è il tempo necessario per eseguire un processo specifico. Comprende il tempo totale impiegato in attesa di essere caricato in memoria, in coda e in esecuzione sulla CPU. Il periodo che intercorre tra l'invio del processo e il suo completamento è il tempo di completamento.

Timer intervallo

L'interruzione del timer è un metodo strettamente correlato alla prelazione. Quando un determinato processo ottiene l'allocazione della CPU, un timer può essere impostato su un intervallo specificato. Sia l'interruzione del timer che la prelazione forzano un processo a restituire la CPU prima che il burst della CPU sia completo.

La maggior parte dei sistemi operativi multiprogrammati utilizza una qualche forma di timer per impedire che un processo blocchi il sistema indefinitamente.

Cos'è il dispatcher?

Il dispatcher è un modulo che fornisce il controllo della CPU al processo. Il dispatcher deve essere veloce, in modo da poter essere eseguito ad ogni cambio di contesto. La latenza di dispatch è il tempo necessario allo scheduler della CPU per arrestare un processo e avviarne un altro.

Funzioni svolte dal centralinista:

• Cambio di contesto.
• Passaggio alla modalità utente.
• Spostamento nella posizione corretta nel programma appena caricato.

Tipi di pianificazione della CPU Algorithms

Esistono principalmente sei tipi di algoritmi di schedulazione dei processi:

1. Primo arrivato, primo servito (FCFS)
2. Pianificazione del lavoro più breve (SJF).
3. Il tempo rimanente più breve
4. Pianificazione prioritaria
5. Pianificazione Round Robin
6. Pianificazione della coda multilivello

Programmazione Algorithms

Primo arrivato primo servito

FCFS sta per Primo arrivato primo servitoÈ l'algoritmo di pianificazione della CPU più semplice e immediato. In questo tipo di algoritmo, il processo che richiede la CPU ottiene per primo l'allocazione della CPU. Questo metodo di pianificazione può essere gestito con una coda FIFO.

Quando un processo entra nella coda dei processi pronti, il suo PCB (Process Control Block) viene collegato alla coda. Pertanto, quando la CPU si libera, dovrebbe essere assegnata al processo in cima alla coda.

Caratteristiche del metodo FCFS

• Si tratta di un algoritmo di pianificazione non preemptive.
• I lavori vengono sempre eseguiti in base all'ordine di arrivo.
• È facile da implementare e utilizzare.
• Tuttavia, questo metodo ha prestazioni scadenti e il tempo di attesa generale è piuttosto elevato.

Il tempo rimanente più breve

L'acronimo SRT sta per Shortest Remaining Time (tempo rimanente più breve). È anche noto come pianificazione preemptive SJF. Con questo metodo, il processo viene assegnato all'attività più vicina al suo completamento. Questo metodo impedisce che un processo più recente, pronto per l'esecuzione, blocchi il completamento di un processo precedente.

Caratteristiche del metodo di pianificazione SRT

• Questo metodo viene applicato principalmente in ambienti batch, dove è necessario dare la precedenza ai processi di breve durata.
• Questo non è un metodo ideale da implementare in un sistema condiviso in cui il tempo di CPU richiesto è sconosciuto.
• A ciascun processo è associata la durata del successivo ciclo di utilizzo della CPU, pertanto il sistema operativo utilizza queste durate per pianificare l'esecuzione del processo nel modo più breve possibile.

Pianificazione basata sulle priorità

Pianificazione prioritaria È un metodo di pianificazione dei processi basato sulla priorità. In questo metodo, chi pianifica seleziona le attività da svolgere in base alla loro priorità.

La pianificazione delle priorità aiuta il sistema operativo ad assegnare le priorità ai processi. I processi con priorità più alta vengono eseguiti per primi, mentre i processi con priorità uguale vengono eseguiti secondo un ordine di priorità (round-robin o FCFS). La priorità può essere determinata in base ai requisiti di memoria, ai requisiti di tempo e ad altri fattori.

Pianificazione Round-Robin

round robin È uno degli algoritmi di pianificazione più antichi e semplici. Il nome di questo algoritmo deriva dal principio del round-robin, in cui ogni persona riceve a turno una quota uguale di qualcosa. Viene utilizzato principalmente per la pianificazione in sistemi multitasking. Questo metodo contribuisce a garantire un'esecuzione dei processi senza interruzioni.

Caratteristiche della pianificazione Round-Robin

• Il round robin è un modello ibrido basato sull'orologio.
• Il lasso di tempo assegnato per l'elaborazione di una specifica attività dovrebbe essere minimo. Tuttavia, può variare a seconda del processo.
• Si comporta come un sistema time-sharing che risponde a ciascun processo entro un limite di tempo specifico.

Prima il lavoro più breve

SJF (Shortest Job First) è un algoritmo di pianificazione in cui il processo con il tempo di esecuzione più breve viene selezionato per essere eseguito successivamente. Questo metodo di pianificazione può essere preemptive o non preemptive. Riduce significativamente il tempo medio di attesa per gli altri processi in attesa di esecuzione.

Caratteristiche della pianificazione SJF

• Ad ogni lavoro è associata un'unità di tempo per il completamento.
• Con questo metodo, quando la CPU è disponibile, viene eseguito per primo il processo o l'attività successiva con il tempo di completamento più breve.
• Viene implementato con una politica non preventiva.
• Questo algoritmo è utile per l'elaborazione in batch, dove l'attesa del completamento dei processi non è critica.
• Migliora la produttività eseguendo prima i lavori più brevi, che in genere hanno tempi di completamento più brevi.

Pianificazione delle code a più livelli

Questo algoritmo suddivide la coda dei processi pronti in diverse code separate. Con questo metodo, i processi vengono assegnati a una coda in base a una proprietà specifica del processo, come la priorità del processo, la dimensione della memoria e così via.

Tuttavia, questo non è un algoritmo di pianificazione indipendente, poiché necessita di utilizzare altri tipi di algoritmi per programmare i lavori.

Caratteristiche della pianificazione di code multilivello

• Per i processi con caratteristiche comuni è opportuno mantenere più code.
• Ogni coda può avere un proprio algoritmo di pianificazione separato.
• A ciascuna coda viene assegnata una priorità.

Lo scopo di un algoritmo di pianificazione

Ecco i motivi per utilizzare un algoritmo di pianificazione:

• La CPU utilizza la pianificazione per migliorare la propria efficienza.
• Consente di allocare le risorse tra processi concorrenti.
• Il massimo utilizzo della CPU si ottiene con il multiprogrammazione.
• I processi da eseguire vengono mantenuti nella coda dei processi pronti.

DOMANDE FREQUENTI