Processi e Scheduling in Informatica

Ricordiamo brevemente che un processo non è altro che un programma in esecuzione, una “attività” che possiede un ingresso,una uscita ed uno stato.

Un processo puo’ essere in tre stati:

in esecuzione: sta utilizzando la CPU in quell’istante
pronto : può essere messo in esecuzione ma è temporaneamente sospeso poiché la CPU non è disponibile poiché usata da un altro processo
bloccato: ossia è impossibilitato ad andare in esecuzione poiché ad esempio attende dei dati di ingresso forniti da un altro processo ( una pipe…)

Una CPU (single-core) ad ogni singolo istante può far girare un solo processo. Tuttavia nell’arco di un secondo può lavorare su programmi diversi dando all’utente l’illusione del parallelismo. Questo pseudoparallelismo è realizzato grazie al time-sharing:

supponiamo di avere 3 processi A,B,C che devono essere eseguiti da una CPU; mediante il timesharing l’elaborazione dei tre viene spezzettata in “quanti di esecuzione” ed l’uso della CPU alternato secondo regole stabilite dallo scheduler.

Quindi possiamo affermare che ciascun processo dispone di una propria CPU virtuale, anche se in realtà lo scheduler si occupa di passare continuamente da un processo all’altro per garantire il multitasking.

La parte del sistema operativo che si occupa di mandare o meno in esecuzione un processo viene chiamata scheduler. Esistono due categorie di schedulazione: con e senza prerilascio. Nella schedulazione senza prerilascio (non preemptive scheduling) un processo viene eseguito fino al suo completamento. Non essendo questo metodo adatto a sistemi general purpose è evidente che ci occuperemo di schedulazioni con prerilascio.

SCHEDULAZIONE ROUND ROBIN
A ogni processo viene assegnato un intervallo di tempo (chiamato quanto) in cui “girare” sul processore. L’implementazione è molto semplice: lo schedulatore deve solo avere una lista di processi da eseguire a turno…

Risulta interessante analizzare quanto debba essere lungo il quanto di esecuzione ideale: infatti se fosse troppo piccolo la CPU sprecherebbe tempo prezioso nei cambi da un processo all’altro (overhead di gestione), se invece fosse eccessivamente grande, i tempi di risposta potrebbero diventare così lunghi da rendere difficoltosa l’interattività dell’utente.

SCHEDULAZIONE CON PRIORITA’
A ogni processo viene assegnata una priorità di esecuzione. Vengono create delle classi di priorità e ciascuna classe viene gestita con il Round Robin. Per evitare che vengano eseguiti solo i processi della prima classe lo scheduler decrementa automaticamente le priorità.

Lo svantaggio di questo metodo è che il continuo aggiornamento delle classi genera uno spreco di calcolo e tempo.

UTILIZZO DI CODE MULTIPLE
Risulta essere evidente che per l’esecuzione di un singolo processo, risulta più efficiente un quanto di esecuzione lungo che tanti più corti. Questo poiché saltando troppo spesso da un processo all’altro vi è una perdita tempo della CPU (ad esempio per svuotare e riempire i registri).

Con il metodo delle code multiple il quanto di esecuzione di un processo aumenta dinamicamente e quanto vi è una richiesta di interattività da parte dell’utente il quanto viene ridimensionato-

Supponiamo che un processo A abbia bisogno di 100 quanti di CPU per essere eseguito, allora se il quanto è fissato dovrebbe accedere 100 volte alla CPU per concludere il suo computo. Se facciamo raddoppiare la durata del quanto per il processo in questione allora dovrebbe accedere solo 7 volte alla CPU anziché 100 (infatti i quanti di esecuzione saranno 1-2-4-8-16-32-64 :con 7 accessi il processo ha sicuramente concluso poiché ha avuto l’equivalente di 127 quanti precedenti). Se un utente richiedesse interattività, ad esempio digitando qualcosa sulla tastiera, i quanti ”lunghi” verrebbero immediatamente ridimensionati.

SHORTEST JOB FIRST
Risulta essereun sistema di schedulino adatto a sistemi batch ossia che eseguono dei lavori i cui tempi di esecuzione sono noti in precedenza. Il nome dell’algoritmo (SJF) ne spiega già il metodo.