Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, III piano
Aula Seminari

Abstract:
Lo scheduling di lavori rilasciati nel tempo il cui tempo di servizio e` noto solo al momento del completamento degli stessi e` un classico problema nell'assegnamento della CPU in sistemi operativi concorrenti. Una classica misura della qualita` della politica di scheduling del sistema e` il Flow time medio dei lavori, cioe` il tempo medio trascorso dai lavori nel sistema tra l'istante di rilascio e quello di completamento. Le politiche di scheduling dei sistemi operativi Windows NT e Unix sono basati sull'algoritmo Multi-level feedback, che organizza i lavori in attesa di essere serviti in un insieme di code a piu` livelli. In questo lavoro dimostriamo che una versione randomizzata dell'algoritmo Multi-level Feedback ottiene un rapporto di competitivita` ottimale per sistemi a singolo processore e vicino all'ottimalita` per sistemi multi-processore. Cio` fornisce secondo la nostra opinione una validazione teorica di un'idea la cui efficacia e' nota da piu` di venti anni. (Lavoro in collaborazione con Stefano Leonardi)