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