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. ***