CAREER: Multi-threaded Research and Education

许多计算机系统都是多线程的。传统的在线问题抽象了多线程的存在，要么将多个线程压缩成一个线程，要么将每个线程减少到一个请求。本课题研究一类新的问题：具有多线程输入的在线系统。为了对多线程输入建模，引入了多客户端输入模型，其中每个客户端（线程）由有向无环图（DAG）表示。研究了三个实际问题：多线程分页问题，其中进程竞争中央处理单元（CPU）时间和快速内存位置；多线程磁盘调度问题，其中进程和/或数据库事务竞争对磁盘的访问；而多线程操作系统的问题，自然结合了这两个问题。这些问题概括为k-client问题，这是经过深入研究的k-server问题的双重版本，以及k-server l-client问题。本研究的一个重要目标是学习如何设计一个复杂的系统，如快速内存管理器、CPU调度器和磁盘调度器。特别是，确定通过孤立地考虑每个系统组件获得的算法和结果是否可以很容易地结合起来，为整个系统产生新的算法和结果。在教育方面，有两个互补的项目。第一个项目涉及学习如何教学的过程。PI申请并获得了竞争激烈的密歇根州立大学礼来捐赠教学奖学金。在这个为期一年的密集项目中，PI将与五名有前途的年轻教师一起学习由来自大学和全国各地的顶尖教育学者教授的基本教育原则。第二个项目是建立一个更有凝聚力的课程，强调所有主题的实际重要性，特别是理论。这是通过领导一个部门的努力，以超文本标记语言（HTML）编写一个全面的计算机科学教科书来实现的。本HTML教材将利用超链接来突出课程之间和课程内部的联系。例如，链接将数据结构课程中的堆栈和队列模块与使用这些结构的操作系统课程中的模块连接起来。这个HTML教科书项目也可以补充部门为非传统学生提供远程学习课程的努力。

Many computer systems are multi-threaded. Traditional on-line problems abstract away the existence of multiple threads, either by collapsing multiple threads into a single thread or by reducing each thread to a single request. This project studies a new class of problems: on-line systems with multi-threaded inputs. To model multi-threaded inputs, multiple client input model where each client (thread) is represented by a directed acyclic graph (DAG) are introduced. Three practical problems investigated are the multi-threaded paging problem, where processes compete for both central processing unit (CPU) time and fast memory locations; the multi-threaded disk scheduling problem where processes and/or database transactions compete for access to the disk; and the multi-threaded operating system problem, the natural combination of these two problems. These problems generalize into the k-client problem, a dual version of the well-studied k-server problem, and the k-server l-client problem. One important goal of this research is to learn how to design a complex system such as a fast memory manager, a CPU scheduler, and a disk scheduler. In particular, determine if the algorithms and results obtained by considering each system component in isolation can be easily combined to produce new algorithms and results for the complete system. In education, there are two complementary projects. The first project deals with the process of learning how to teach. The PI applied for and received a highly competitive MSU Lilly Endowment Teaching Fellowship. In this intensive year-long program, the PI will work together with a group of five promising young faculty to learn fundamental educational principles taught by leading education scholars from around the University and around the country. The second project is to build a more cohesive curriculum emphasizing the practical importance of all topics, especially theory. This is achieved by leading a departmental effort to wr ite a comprehensive computer science textbook written in hypertext markup language (HTML). This HTML textbook will utilize hyperlinks to highlight the connections between and within courses. For example, links will connect a module on stacks and queues from a data structures course with modules from an operating systems course where these structures are used. This HTML textbook project may also supplement departmental efforts to offer distance learning courses to nontraditional students.