Scheduling

Da Wikiversità, l'apprendimento libero.
Jump to navigation Jump to search
lezione
Scheduling
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Sistemi operativi

Lo scheduler dei processi è quel componente del sistema operativo che si occupa di decidere quale processo va mandato in esecuzione. Nell'ambito della multiprogrammazione è pensato per mantenere la CPU occupata il più possibile, ad esempio avviando un processo mentre un altro è in attesa del completamento di un'operazione di I/O.

Tipi di scheduler[modifica]

  • scheduler a breve termine: seleziona il processo da eseguire tra i processi in stato ready. Questo può avvenire:
    • Con prelazione [1] , se il processo passa dallo running, waiting o new allo stato ready.
    • Senza prelazione se il processo passa da running a waiting oppure se termina.
Il processo selezionato dallo scheduler a breve termine ottiene poi il controllo della CPU grazie al dispatcher. In questo contesto si definisce anche la latenza di dispatch come il tempo necessario a fermare un processo e a riprenderne un altro. Si indica invece con turnaround il tempo totale impiegato per l'esecuzione di un processo.
  • scheduler a medio termine: si basa sull'idea che qualche volta può rivelarsi un vantaggio rimuovere un processo dalla memoria, ad esempio per migliorare il process mix o perché si ha la necessità di liberare della memoria. Togliere e reinserire un processo in memoria prende il nome di swapping, oppure context switch (cambio di contesto).
  • scheduler a lungo termine: seleziona i processi da portare nella ready queue.

Code[modifica]

Per gestire lo scheduling si utilizzano varie code:

  • coda dei job, che contiene tutti i processi del sistema.
  • coda dei processi pronti (ready queue), formata da una lista linkata in cui si ha un header che punta al primo PCB della lista, il quale punta al PCB successivo e così via.
  • coda del dispositivo: lista dei processi che sono in attesa di un particolare dispositivo di I/O.

Algoritmi di scheduling[modifica]

Gli obiettivi di un algoritmo di scheduling possono dipendere dall'ambiente (ad esempio se si ha a che fare con dei sistemi batch oppure con sistemi real-time). In generale un algoritmo di scheduling deve essere equo (cioè deve cercare di dare a tutti i processi lo stesso tempo CPU), deve rispettare le politiche di sistema e deve cercare di mantenere il sistema il più occupato possibile.

Scheduling First-Come, First-Served (FCFS)[modifica]

Si tratta di uno dei più semplici algoritmi di scheduling ed è senza prelazione. I processi vengono assegnati alla CPU nell'ordine in cui essi l'hanno richiesta (si ha una singola ready queue).

Scheduling a priorità[modifica]

Ad ogni processo si associa un numero intero che ne indica la priorità. Questo tipo di scheduling può comportare il problema della starvation: un processo a bassa priorità rischia di venir eseguito molto tardi (oppure mai nel peggiore dei casi) se esso incontra in continuazione processi a priorità maggiore. Per evitare questo problema si fa in modo di aumentare la priorità di un processo al passare del tempo (aging).

Round Robin (RR)[modifica]

Un processo viene eseguito per un piccolo lasso di tempo (detto quanto), dopodiché viene prelazionato e rimesso nella ready queue. La durata del quanto non deve essere troppo lunga (altrimenti si ritorna a un caso simile al FCFS), né troppo corta (in tal caso si avrebbe overhead troppo alto).

Shortest Job First (SJF)[modifica]

Algoritmo di scheduling che pone nella lista di ready i processi in base al loro CPU burst, minore sarà il tempo di burst e prima verrà eseguito dalla CPU. Tempo di attesa molto basso.

Note[modifica]

  1. Qui si usa il termine "prelazione" per rendere il termine inglese "preemption". Altro termine italiano usato in modo equivalente è "rilascio anticipato"