Gwendolyn Einfeld: Learning to Share: Disk scheduling using a hierarchical token bucket filetering algorithm

Gwendolyn Einfeld worked in the Storage Systems Research Center under the guidance of Dr. Scott Brandt to improve an algorithm for disk sharing. In networks, and even on home computers, multiple processes must access the same hard drive space simultaneously. In order to assure performance, algorithms that assign processes and users the right to disk access are necessary. This becomes even more important with multimedia, such as video or music. Without disk sharing algorithms, these real-time programs would experience reduced performance – stopping and skipping during playback for example. The Hierarchical Disk Sharing (HDS) algorithm was developed to address this problem. Gwendolyn worked on modifications to make the algorithm more efficient.

HDS uses a hierarchy of token bucket filters that give each process or group of processes an allowance of “tokens”. These tokens can then be traded for disk time. In this way each process can send its requests to the hard drive as long as they come in, but no process can hog the disk space and prevent others from accessing. Additionally, the algorithm allows active processes to borrow tokens from processes that are temporarily inactive. Three modifications were made to the algorithm. Rather than distribute tokens based on a constant global rate, tokens are now recycled. This prevents the disk from wasting space if it is operating faster than the global rate is distributing tokens and from becoming overloaded, if it is operating more slowly. Secondly, the question of how many tokens to put in circulation was addressed. Finally, work was done on creating borrowing schemes that allow processes to borrow, but don’t allow them to monopolize another process’s tokens. The result is an improved HDS scheme that is flexible in responding to the constraints of the hard disk and contains limitations that prevent processes from overstepping their token quotas and hogging disk space.