Competitive Analysis of Problems in Resource Allocation

点击翻译按钮获取中文摘要

This project focuses on algorithms that work with limited information. This research investigates on-line algorithms in the context of various resource allocation problems in operating systems. This project is taking a twofold approach to each problem. The first approach is to perform a theoretical study using competitive analysis. The competitive measure is used to evaluate on-line algorithms by measuring their performance in relation to the optimal off-line algorithm which has available to it complete information about the problem instance at hand. This effort plans to perform empirical tests to evaluate the performance of various on-line algorithms in a realistic setting. The first two problems addressed in this project are related to memory management. The first of these addresses ways in which information about the access pattern of a program available at compile time can be used to guide page replacement and prefetching policies. The investigator will develop methods which can take a program and automatically generate appropriate memory management instructions to be inserted in the code. The second problem addresses allocating memory resources among users in a multiprocessing environment. This work addresses this problem for general multiprocessing environments as well as methods specifically designed for database systems. The third problem examines preemptive load balancing strategies over local area networks under a probabilistic model for process duration. The last problem is an investigation of disk scheduling strategies. This work is motivated by the fact that the availability of larger cheap memory has made it possible to have long queues of disk updates which means that more sophisticated scheduling policies can have a greater impact on disk utilization. ***