Pianificazione della CPU Algorithms in Operasistemi di ting

Tipi di pianificazione della CPU

Ecco due tipi di metodi di pianificazione:

Programmazione preventiva

Nella pianificazione preventiva, le attività vengono per lo più assegnate con le relative priorità. A volte è importante eseguire un'attività con 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 viene mantenuta per un certo periodo e riprende quando l'attività con priorità più alta termina l'esecuzione.

Pianificazione non preventiva

In questo tipo di metodo di pianificazione, la CPU è stata allocata a un processo specifico. Il processo che mantiene occupata la CPU 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, considerare questi quattro parametri:

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

Si applicano solo le condizioni 1 e 4, la pianificazione è detta non preventiva.

Tutte le altre pianificazioni sono preventive.

Terminologie importanti per la pianificazione della CPU

• Tempo di burst/Tempo di esecuzione: È il tempo richiesto dal processo per completare l'esecuzione. Si chiama anche tempo di esecuzione.
• Orario di arrivo: quando un processo entra nello stato pronto
• Tempo finale: quando il processo viene completato e si esce da un sistema
• Multiprogrammazione: Numerosi programmi che possono essere presenti in memoria contemporaneamente.
• Lavori: È un tipo di programma senza alcun tipo di interazione con l'utente.
• Utente: È un tipo di programma con interazione con l'utente.
• Processo: È il riferimento utilizzato sia per il lavoro che per l'utente.
• Ciclo burst CPU/IO: Caratterizza l'esecuzione del processo, che alterna l'attività della CPU e quella di 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 minimizzare quanto segue:

Massimizzare

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

Throughput: Il numero di processi che terminano la loro esecuzione per unità di tempo è noto come Throughput. Pertanto, 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.

Ridurre al minimo

Tempo di attesa: Il tempo di attesa è la quantità di tempo che un processo specifico deve attendere nella coda pronta.

Tempo di risposta: È l'intervallo di tempo in cui è stata presentata la richiesta fino a quando non viene prodotta la prima risposta.

Tempo di consegna: Il tempo di consegna è una quantità di tempo necessaria per eseguire un processo specifico. È il calcolo del tempo totale trascorso aspettando di entrare in memoria, aspettando in coda ed eseguendo sulla CPU. Il periodo che intercorre tra il momento dell'invio 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, 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 per sempre.

Cos'è il dispatcher?

È un modulo che fornisce il controllo della CPU al processo. Il Dispatcher dovrebbe essere veloce in modo che possa essere eseguito a 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 eseguite dal Dispatcher:

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

Tipi di algoritmo di pianificazione della CPU

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

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 pronta, il suo PCB (Process Control Block) è collegato alla coda della coda. Pertanto, quando la CPU diventa libera, dovrebbe essere assegnata al processo all'inizio della coda.

Caratteristiche del metodo FCFS

• Offre un algoritmo di pianificazione non preventivo e preventivo.
• 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

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

Caratteristiche del metodo di pianificazione SRT

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

Pianificazione basata sulle priorità

Pianificazione prioritaria è un metodo di pianificazione dei processi basato sulla priorità. In questo metodo, lo scheduler seleziona le attività da eseguire in base alla 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 pari priorità 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

Il Round Robin è l'algoritmo di pianificazione più antico e più semplice. Il nome di questo algoritmo deriva dal principio del round robin, secondo il quale ogni persona riceve a turno una quota uguale di qualcosa. Viene utilizzato principalmente per gli algoritmi di pianificazione nel multitasking. Questo metodo di algoritmo aiuta a eseguire i processi senza fame.

Caratteristiche della pianificazione Round-Robin

• Il Round Robin è un modello ibrido basato sull'orologio
• L'intervallo di tempo deve essere minimo, assegnato per l'elaborazione di un'attività specifica. Tuttavia, può variare a seconda dei diversi processi.
• È un sistema in tempo reale che risponde all'evento entro un limite di tempo specifico.

Prima il lavoro più breve

SJF è una forma completa di (Il lavoro più breve prima) è 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 significativamente il tempo medio di attesa per altri processi in attesa di esecuzione.

Caratteristiche della pianificazione SJF

• È associato a ciascun 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 algoritmo è utile per l'elaborazione di tipo batch, dove l'attesa del completamento dei lavori non è critica.
• Migliora la produzione lavorativa offrendo lavori più brevi, che dovrebbero essere eseguiti per primi, e che nella maggior parte dei casi hanno tempi di consegna più brevi.

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é necessita di utilizzare altri tipi di algoritmi per pianificare i lavori.

Caratteristica della pianificazione delle code a più livelli

• Dovrebbero essere mantenute più code per processi con alcune caratteristiche.
• Ogni coda può avere i propri algoritmi di pianificazione separati.
• Le priorità vengono assegnate per ciascuna 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 propria efficienza.
• Ti aiuta ad allocare le risorse tra processi concorrenti.
• Il massimo utilizzo della CPU può essere ottenuto con la multiprogrammazione.
• I processi che devono essere eseguiti sono in coda pronti.

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à vengono per lo più assegnate con le relative priorità.
• Nel metodo di pianificazione non preventiva, la CPU è stata allocata a un processo specifico.
• Il tempo di burst è il tempo necessario affinché il processo completi l'esecuzione. Si chiama anche tempo di esecuzione.
• L'utilizzo della CPU è il compito principale in cui il sistema operativo deve garantire che la CPU rimanga il più occupata possibile.
• Il numero di processi che terminano la loro esecuzione per unità di tempo è noto come Throughput.
• Il tempo di attesa è la quantità di tempo che un processo specifico deve attendere nella coda pronta.
• È l'intervallo di tempo in cui è stata inviata la richiesta fino a quando non viene prodotta la prima risposta.
• Il tempo di consegna è la quantità di tempo necessaria 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 dei processi sono: First Come First Serve (FCFS), 2) Shortest-Job-First (SJF) Scheduling, 3) Shortest Remaining Time, 4) Priority Scheduling, 5) Round Robin Scheduling, 6) Multilevel Queue Scheduling .
• Nel Metodo First Come First Serve, il processo che richiede la CPU ottiene per primo l'allocazione della CPU.
• Nel tempo più breve rimanente, il processo verrà assegnato all'attività più vicina al suo completamento.
• Nella pianificazione prioritaria, lo scheduler seleziona le attività da eseguire in base alla priorità.
• Pianificazione round robin funziona secondo il principio secondo cui ogni persona riceve a turno una quota uguale di qualcosa.
• Nel lavoro più breve si dovrebbe selezionare prima il tempo di esecuzione più breve per l'esecuzione successiva.
• Il metodo di pianificazione multilivello 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 propria efficienza.