Cachy, nuovo CPU scheduler per Linux basato su HRRN

Cachy è uno scheduler della CPU per Linux che sta generando una certa attenzione. L’obiettivo di Cachy, che si basa sulla policy HRRN (Highest Response Ration Next), è garantire un utilizzo ottimale della cache della CPU. Prima di parlare di Cachy facciamo un breve recap di alcuni concetti fondamentali.

Scheduler e scheduling

Lo scheduler è un componente molto importante di un sistema operativo. Si tratta di programma che implementa un algoritmo di scheduling il quale si occupa di gestire le richieste di accesso (da parte dei programmi) al processore (CPU). Lo scheduler privilegia le richieste che rispettano determinati parametri secondo una certa politica di scheduling, in modo da ottimizzare l’accesso a tale risorsa.

Quando si parla di politica di scheduling si fa riferimento al modo in cui viene gestito l’accesso alla risorsa. Politiche di scheduling molto basilari (ad oggi nessun sistema operativo le usa) possono essere, ad esempio, FIFO (First-in-First-out) o SJF (Shortes Job First). Politiche più avanzate si basano su principi statistici o sulla predizione per individuare un ordinamento delle richieste che si avvicini il più possibile a quello ottimale.

Cachy, scheduler Linux per ottimizzare l’uso della cache

Prima di dare uno sguardo alle scelte progettuali torniamo su HRRN che Cachy adotta con alcune modifiche. HRRN è una politica non-preemptive sviluppata per risolvere i problemi dell’algoritmo SJN (Shortest Job Next). Il job che verrà eseguito non è quello che avrà un tempo d’esecuzione minore (come avveniva in SJN causando starvation) bensì quello con il response ratio più elevato. Il response ratio è calcolato attraverso la seguente formula: (w_t + s_t) / s_t dove w_t sta per waiting-time mentre s_t sta per estimated-runtime.

Lo sviluppatore di Cachy ha fatto alcune scelte che sembrano funzionare. Ha eliminato tutto il codice di bilanciamento (tranne per le situazioni di idle) e il raggruppamento per attività. Non viene supportato NUMA che va disabilitato. Per chi non lo sapesse Non-Uniform Memory Access (NUMA) è un’architettura di memoria sviluppata per i sistemi multiprocessore dove i tempi di accesso dipendono dalla posizione della memoria rispetto al processore. Nelle architetture NUMA un processore può accedere rapidamente alla propria memoria locale, più lentamente alle memorie degli altri processori o alla memoria condivisa.

Inoltre, ogni CPU ha la propria coda di esecuzione e la preemption avviene ad ogni tick. Con preemption si fa riferimento all’operazione attraverso la quale un processo viene temporaneamente interrotto e portato al di fuori della CPU, al fine di permettere l’esecuzione di un altro processo. Nel caso di Cachy, ad esempio, se il tick è a 250 HZ (CONFIG_HZ_250=y) allora il processo sarà eseguito per 4 millisecondi dopodiché la CPU sarà assegnata al processo successivo della coda.

Lo scheduler fa della responsiveness il suo punto forte, è perfetto per sistemi desktop ma anche per dispositivi mobile (Android), anche se chiaramente manca, ad oggi, l’integrazione per funzionare sul robottino verde.

Lo sviluppatore ha pubblicato alcuni benchmark che confrontano Cachy con Cfs: i risultati sembrano molto incoraggianti. Per ulteriori dettagli su questo algoritmo e per la procedura di installazione vi rimando alla pagina GitHub ufficiale.

Seguiteci sul nostro canale Telegram, sulla nostra pagina Facebook e su Google News. Nel campo qui sotto è possibile commentare e creare spunti di discussione inerenti le tematiche trattate sul blog.