Dynamic Scheduling and Resource Management in Computer Systems

这个项目的动机是IBM T.J. Watson研究中心关于计算机操作系统中的调度和资源管理的两个最新发展：(1)在OS/400 （IBM的AS/400产品线的操作系统）和AIX （IBM的RS/6000产品线的基于unix的操作系统）中实现所谓的“时间函数调度”；(2)一个用于分布式内存、多处理器环境（例如IBM的SP2和工作站集群）的原型调度程序，它集成了一些调度范例，如组调度和负载共享调度。在这两种情况下，通过广泛的理论研究和实证研究，发现调度程序提供了有效和灵活的资源控制，实现了多种调度目标，并提高了大型复杂科学和工程应用中各种应用程序的性能。本文旨在探索和建立这些调度程序的控制理论基础，从而进一步完善高性能操作系统中的动态调度和资源管理协议。具体来说，我们建议研究离散事件系统中调度程序的数学结构。PI最近在该领域的一些工作已经建立了一类广泛的离散事件系统的简单控制规则的最优性与离散数学结构（如拟阵和反拟阵）之间的联系。在这里，我们想要探索与许多随机系统的守恒定律和广义守恒定律相关的多拟阵和扩展多拟阵等相关结构，从而揭示调度程序的有效性，或者在某些情况下，最优性。我们还建议通过在Watson的原型测试平台中添加新功能来实现实证研究的理论结果。

ECS-9705392 Yao This project is motivated by two recent developments at the IBM T.J. Watson Research Center concerning the scheduling and resource management in computer operating systems: (1) implementation of the so-called "time-function scheduling" in both OS/400 (the operating system for IBM's AS/400 product line) and AIX (the UNLX-based operating system for IBM's RS/6000 product line); and (2) a prototype scheduler for distributed-memory, multiprocessor environments (e.g., IBM's SP2 and clusters of workstations), which integrates several scheduling paradigms such as gang scheduling and load-sharing scheduling. In both cases, through extensive theoretical studies, in addition to empirical studies, it has been found that the schedulers provide effective and flexible control of resources that achieves a diverse set of scheduling objectives and improves the performance of a variety of applications in large and complex scientific and engineering applications. What we propose here is to explore and establish the control-theoretic foundation of these schedulers, and in return further enhance the dynamic scheduling and resource management protocols in high-performance operating systems. Specifically, we propose to study the mathematical structure of the schedulers in the context of discrete-event systems. Some of the PI's recent works in this area have established the connection between the optimality of simple control rules of a wide class of discrete-event systems and discrete mathematical structures such as matroid and antimatroid. Here, we want to explore related structures such as polymatroid and extended polymatroid, which are associated with conservation laws and generalized conservation laws of many stochastic systems, so as to bring out the effectiveness, or in some cases, optimality, of the schedulers. We also propose to implement the theoretical results for empirical studies, by way of adding new features to the prototype testbeds at Watson.