CS Distinguished Lecture Series: "Advancement of Buffer Management Research and Development in Computer and Data Processing Systems" by Prof. Xiaodong Zhang

Date: February 15, 2011
Time: 2:00 pm – 4:00 pm

Where: SB 4.01.20 (CS conference room)

"Advancement of Buffer Management Research and Development in Computer and Data Processing Systems"
by Prof. Xiaodong Zhang (The Ohio State University)


In any memory-capable digital systems, from small cell phones to a huge supercomputers and data centers, the performance of data buffer management is mainly determined by a replacement algorithm that decides which data block will be evicted when a new data block needs to be allocated as the memory space is full. The replacement concept is simple but its algorithmic optimization and system implementations are challenging and difficult. Since the LRU replacement algorithm was proposed and its approximation was implemented in 1960's, computer scientists and system engineers have made continuous and tireless efforts to improve replacement algorithms analytically and systematically.

Although LRU has several critical flaws, it has been widely used in production systems due to its merits of low complexity and low overhead implementation. After our concentrated efforts for several years, the dominant LRU-like algorithms have been gradually replaced by LIRS-like algorithms in major operating and data database systems, such as BSD, Linux, MySQL, Infinispan, and others. In this talk, I will present how the LIRS algorithm and its variations lay a foundation to address the limits of LRU, and how efficient system implementations turn our research results into reality in production systems. Four connected technical components in the presentation include:
  • the basics of LIRS,
  • approximations and variations of LIRS in practice,
  • lock-contention free implementations, and
  • a LIRS-like shared cache management in multi-core processors.


Xiaodong Zhang is the Robert M. Critchfield Professor in Engineering and Chair of the Computer Science and Engineering Department at the Ohio State University. His research interests focus on data management in computer, networking and distributed systems. He has made strong efforts to transfer his academic research into advanced technology to impact production systems.He received his Ph.D. in Computer Science from University of Colorado at Boulder, where he is receiving Distinguished Engineering Alumni Award in 2011. He is a Fellow of the IEEE.

Xiaodong Zhang was on faculty of Computer Science at UTSA from 1989 to 1997.