Algoritmi di pianificazione della CPU nei sistemi operativi

Cos'è la pianificazione della CPU?

La pianificazione della CPU è un processo per determinare quale processo possiederà la CPU per l'esecuzione mentre un altro processo è in attesa. Il compito principale della pianificazione della CPU è assicurarsi che ogni volta che la CPU rimane inattiva, il sistema operativo seleziona almeno uno dei processi disponibili nella coda pronta per l'esecuzione. Il processo di selezione sarà effettuato dallo scheduler della CPU. Seleziona uno dei processi in memoria pronti per l'esecuzione.

In questo tutorial sulla pianificazione della CPU imparerai:

• Cos'è la pianificazione della CPU?
• Tipi di pianificazione della CPU
• Terminologie importanti per la pianificazione della CPU
• Criteri di pianificazione della CPU
• Timer intervallo
• Cos'è Dispatcher?
• Tipi di algoritmo di pianificazione della CPU
• Primo arrivato primo servito
• Tempo rimanente più breve
• Pianificazione basata su priorità
• Pianificazione round-robin
• Primo lavoro più breve
• Pianificazione delle code a più livelli
• Lo scopo di un algoritmo di pianificazione

Tipi di pianificazione della CPU

Ecco due tipi di metodi di pianificazione:

Pianificazione preventiva

Nella pianificazione preventiva, le attività sono per lo più assegnate con le loro priorità. A volte è importante eseguire un'attività con una priorità più alta prima di un'altra attività con priorità più bassa, anche se l'attività con priorità più bassa è ancora in esecuzione. L'attività con priorità più bassa dura per qualche tempo e riprende quando l'attività con priorità più alta termina la sua esecuzione.

Pianificazione non preventiva

In questo tipo di metodo di pianificazione, la CPU è stata assegnata a un processo specifico. Il processo che mantiene la CPU occupata rilascerà la CPU cambiando contesto o terminando. È l'unico metodo che può essere utilizzato per varie piattaforme hardware. Questo perché non necessita di hardware speciale (ad esempio, un timer) come la pianificazione preventiva.

Quando la pianificazione è preventiva o non preventiva?

Per determinare se la pianificazione è preventiva o non preventiva, considera questi quattro parametri:

1. Un processo passa dallo stato di esecuzione allo stato di attesa.
2. Il processo specifico passa dallo stato di esecuzione allo stato di pronto.
3. Il processo specifico passa dallo stato di attesa allo stato di pronto.
4. Il processo ha terminato la sua esecuzione e terminato.

Si applicano solo le condizioni 1 e 4, la programmazione è definita non preventiva.

Tutte le altre programmazioni sono preventive.

Terminologie importanti per la pianificazione della CPU

• Burst Time / Execution Time: è il tempo richiesto dal processo per completare l'esecuzione. È anche chiamato tempo di esecuzione.
• Ora di arrivo: quando un processo entra in uno stato pronto
• Ora di fine: quando il processo è completo e si esce da un sistema
• Multiprogrammazione: più programmi che possono essere presenti in memoria contemporaneamente.
• Lavori: è un tipo di programma senza alcun tipo di interazione da parte dell'utente.
• Utente: è una sorta di programma con l'interazione dell'utente.
• Processo: è il riferimento utilizzato sia per il lavoro che per l'utente.
• Ciclo CPU / IO burst: caratterizza l'esecuzione del processo, che alterna tra CPU e attività I / O. I tempi della CPU sono generalmente più brevi del tempo di I / O.

Criteri di pianificazione della CPU

Un algoritmo di pianificazione della CPU cerca di massimizzare e ridurre al minimo quanto segue:

Massimizza:

Utilizzo della CPU: l'utilizzo della CPU è l'attività principale in cui il sistema operativo deve assicurarsi che la CPU rimanga il più occupata possibile. Può variare da 0 a 100 percento. Tuttavia, per l'RTOS, può variare dal 40 percento per il sistema di basso livello e dal 90 percento per il sistema di alto livello.

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

Minimizzare:

Tempo di attesa: il tempo di attesa è un importo che un processo specifico deve attendere nella coda Pronto.

Tempo di risposta: è la quantità di tempo in cui è stata inviata la richiesta fino a quando non viene prodotta la prima risposta.

Tempo di risposta: il tempo di risposta è una quantità di tempo per eseguire un processo specifico. È il calcolo del tempo totale trascorso in attesa di entrare in memoria, in attesa in coda ed in esecuzione sulla CPU. Il periodo tra il momento della presentazione del processo e il tempo di completamento è il tempo di consegna.

Timer intervallo

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

La maggior parte del sistema operativo multi-programmato utilizza una qualche forma di timer per evitare che un processo blocchi il sistema per sempre.

Cos'è Dispatcher?

È un modulo che fornisce il controllo della CPU al processo. Il Dispatcher dovrebbe essere veloce in modo che possa essere eseguito su ogni cambio di contesto. La latenza di invio è la quantità di tempo necessaria allo scheduler della CPU per arrestare un processo e avviarne un altro.

Funzioni svolte da Dispatcher:

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

Tipi di algoritmo di pianificazione della CPU

Esistono principalmente sei tipi di algoritmi di pianificazione dei processi

1. Primo arrivato, primo servito (FCFS)
2. Pianificazione Shortest-Job-First (SJF)
3. Tempo rimanente più breve
4. Pianificazione prioritaria
5. Round Robin Scheduling
6. Pianificazione della coda multilivello

Primo arrivato primo servito

First Come First Serve è la forma completa di FCFS. È l'algoritmo di pianificazione della CPU più semplice e semplice. 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 il processo entra nella coda di pronto, il suo PCB (Process Control Block) è collegato alla coda della coda. Quindi, quando la CPU diventa libera, dovrebbe essere assegnata al processo all'inizio della coda.

Caratteristiche del metodo FCFS:

• Offre algoritmi di pianificazione non preventivi e preventivi.
• I lavori vengono sempre eseguiti in base all'ordine di arrivo
• È facile da implementare e utilizzare.
• Tuttavia, questo metodo è scarso in termini di prestazioni e il tempo di attesa generale è piuttosto elevato.

Tempo rimanente più breve

La forma completa di SRT è il tempo rimanente più breve. È anche noto come pianificazione preventiva SJF. In questo metodo, il processo verrà assegnato all'attività, che è più vicina al suo completamento. Questo metodo impedisce a un processo di stato pronto più recente di mantenere il completamento di un processo precedente.

Caratteristiche del metodo di schedulazione SRT:

• Questo metodo viene applicato principalmente in ambienti batch in cui è necessario dare la preferenza a lavori brevi.
• Questo non è un metodo ideale per implementarlo in un sistema condiviso in cui il tempo di CPU richiesto è sconosciuto.
• Associa a ciascun processo la durata del successivo burst della CPU. In modo che il sistema operativo utilizzi queste lunghezze, il che aiuta a pianificare il processo nel minor tempo possibile.

Pianificazione basata su priorità

La pianificazione delle priorità è un metodo di pianificazione dei processi in base alla priorità. In questo metodo, lo scheduler seleziona le attività per lavorare secondo la priorità.

La pianificazione delle priorità aiuta anche il sistema operativo a coinvolgere le assegnazioni di priorità. I processi con priorità più alta dovrebbero essere eseguiti per primi, mentre i lavori con priorità uguali vengono eseguiti su base round robin o FCFS. La priorità può essere decisa in base ai requisiti di memoria, ai requisiti di tempo, ecc.

Pianificazione round-robin

Round robin è l'algoritmo di pianificazione più vecchio e semplice. Il nome di questo algoritmo deriva dal principio round-robin, in cui ogni persona riceve una quota uguale di qualcosa a sua volta. Viene utilizzato principalmente per la pianificazione di algoritmi in multitasking. Questo metodo di algoritmo aiuta per l'esecuzione dei processi senza fame.

Caratteristiche della schedulazione round-robin

• Il round robin è un modello ibrido basato su un orologio
• L'intervallo di tempo dovrebbe essere minimo, assegnato all'elaborazione di un'attività specifica. Tuttavia, può variare a seconda dei processi.
• È un sistema in tempo reale che risponde all'evento entro un determinato limite di tempo.

Primo lavoro più breve

SJF è una forma completa di (Shortest job first) è un algoritmo di pianificazione in cui il processo con il tempo di esecuzione più breve deve essere selezionato per l'esecuzione successiva. Questo metodo di pianificazione può essere preventivo o non preventivo. Riduce notevolmente il tempo medio di attesa per altri processi in attesa di esecuzione.

Caratteristiche della pianificazione SJF

• È associato a ogni lavoro come unità di tempo da completare.
• In questo metodo, quando la CPU è disponibile, verrà eseguito per primo il processo o il lavoro successivo con il tempo di completamento più breve.
• È implementato con una politica non preventiva.
• Questo metodo di algoritmo è utile per l'elaborazione di tipo batch, dove l'attesa del completamento dei lavori non è fondamentale.
• Migliora la produzione di lavoro offrendo lavori più brevi, che dovrebbero essere eseguiti per primi, che per lo più hanno un tempo di consegna più breve.

Pianificazione delle code a più livelli

Questo algoritmo separa la coda pronta in varie code separate. In 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, ecc.

Tuttavia, questo non è un algoritmo del sistema operativo di pianificazione indipendente poiché deve utilizzare altri tipi di algoritmi per pianificare i lavori.

Caratteristica della pianificazione di code a più livelli:

• È necessario mantenere più code per processi con alcune caratteristiche.
• Ogni coda può avere i suoi algoritmi di pianificazione separati.
• Le priorità sono date per ogni coda.

Lo scopo di un algoritmo di pianificazione

Ecco i motivi per utilizzare un algoritmo di pianificazione:

• La CPU utilizza la pianificazione per migliorare la sua efficienza.
• Ti aiuta ad allocare le risorse tra i processi concorrenti.
• Il massimo utilizzo della CPU può essere ottenuto con la multi-programmazione.
• I processi che devono essere eseguiti sono in coda Pronto.

Sommario:

• La pianificazione della CPU è un processo per determinare quale processo possiederà la CPU per l'esecuzione mentre un altro processo è in attesa.
• Nella pianificazione preventiva, le attività sono per lo più assegnate con le loro priorità.
• Nel metodo di pianificazione non preventiva, la CPU è stata assegnata a un processo specifico.
• Il tempo di burst è un tempo necessario per completare l'esecuzione del processo. È anche chiamato tempo di esecuzione.
• L'utilizzo della CPU è l'attività principale in cui il sistema operativo deve assicurarsi che la CPU rimanga il più occupata possibile
• Il numero di processi che terminano la loro esecuzione per unità di tempo è noto Throughput.
• Il tempo di attesa è una quantità che un processo specifico deve attendere nella coda Pronto.
• È un periodo di tempo in cui la richiesta è stata presentata fino a quando non viene prodotta la prima risposta.
• Il tempo di consegna è una quantità di tempo per eseguire un processo specifico.
• L'interruzione del timer è un metodo strettamente correlato alla prelazione,
• Un dispatcher è un modulo che fornisce il controllo della CPU al processo.
• Sei tipi di algoritmi di pianificazione del processo sono:
• First Come First Serve (FCFS), 2) Scheduling Shortest-Job-First (SJF) 3) Tempo rimanente più breve 4) Pianificazione prioritaria 5) Pianificazione Round Robin 6) Pianificazione coda multilivello
• Nel metodo First Come First Serve, il processo che richiede la CPU ottiene per primo l'allocazione della CPU.
• Nel più breve tempo rimanente, il processo verrà assegnato all'attività, che è più vicina al suo completamento.
• In Pianificazione prioritaria, lo scheduler seleziona le attività da lavorare secondo la priorità.
• In, questa programmazione Round robin funziona in linea di principio, in cui ogni persona riceve una quota uguale di qualcosa a sua volta
• In Shortest job first il tempo di esecuzione più breve dovrebbe essere selezionato per l'esecuzione successiva
• Nella pianificazione multilivello, il metodo separa la coda pronta in varie code separate. In questo metodo, i processi vengono assegnati a una coda in base a una proprietà specifica
• La CPU utilizza la pianificazione per migliorare la sua efficienza.