Dynamic Scheduling and Resource Management in Computer Systems

ECS-9705392这个项目是由IBM T.J.沃森研究中心在计算机操作系统的调度和资源管理方面的两项最新进展推动的：(1)在OS/400(IBM的AS/400产品线的操作系统)和AIX(IBM的RS/6000产品线的基于UNLX的操作系统)上实现所谓的“时间-函数调度”；以及(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.