CSE Colloquium: Challenges in Operating Systems and Concurrent Algorithms

 ABSTRACT

Operating systems (OS) and concurrency is at the heart of the modern software stack. As hardware and software have become increasingly sophisticated, they pose additional challenges to performance, security, and reliability. On the one hand, faster I/O requirements increase pressure on traditional OS layers, which have become significant performance bottlenecks. On the other hand, increasingly complex and third-party written software, both inside OSs (e.g., modern device drivers) and outside OSs (e.g., modern server applications), require better isolation, componentization, compatibility, and recoverability. The ubiquity of many-core systems present new challenges in building efficient concurrent algorithms that can achieve high performance, memory efficiency, and non-blocking progress. 

In this talk, I will present my work on OS design and architecture. 

LibrettOS, my recent work, revisits multiple OS design paradigms and reconciles them in a single OS. It builds on my experience with VirtuOS, my prior work in this area. LibrettOS acts as a microkernel OS that runs servers in an isolated manner. LibrettOS can also act as a library OS when, for better performance, selected applications are granted exclusive access to virtual hardware resources such as for storage and networking. Furthermore, applications can switch between the two OS modes with no interruption at runtime. LibrettOS has a uniquely distinguishing advantage in that the two paradigms seamlessly coexist in the same OS, enabling users to simultaneously exploit their respective strengths (i.e., greater isolation, high performance). Systems code, such as device drivers, network stacks, and file systems remain identical in the two modes, enabling dynamic mode switching and reducing development and maintenance costs. 

I will also discuss my work on lock-free and wait-free data structures and algorithms. My past and ongoing work enables scalable performance for some of the most fundamental concurrent data structures which are used by systems. Furthermore, part of my work is dedicated to memory reclamation, the most fundamental problem with any concurrent data structure that uses dynamic memory allocation. My reclamation algorithms advance prior art with a number of unique properties that (were previously overlooked and) are necessary for scalable performance as well as specific non-blocking progress requirements: 

wait-freedom, snapshot-freedom, balanced reclamation workload, and bounded memory usage. 

Finally, I will outline my future vision for persistent file systems, secure OSs, and persistent concurrent data structures — exciting problem spaces as persistent storage and file systems are increasingly available at the commodity-scale. 

BIOGRAPHY 

Ruslan Nikolaev is a Research Assistant Professor in the Systems Software Research Group (SSRG) in the Department of Electrical and Computer Engineering at Virginia Tech, where he is mentored by Prof. Binoy Ravindran. He received his Ph.D. in Computer Science at Virginia Tech in December 2013, advised by Prof. Godmar Back. 

After receiving his Ph.D., he worked in the industry full-time during 2014-2017, first as a software engineer with Microsoft Corporation, and then as a senior software engineer with Pure Storage, Inc. During his Ph.D., he held summer internships with VMware and Microsoft. 

Dr. Nikolaev's research interests are in computer systems, with a particular focus on operating systems, concurrency including lock-free and wait-free data structures and safe memory reclamation, and OS security. Recently, as part of an IARPA-funded project, he led the effort in designing LibrettOS, an operating system that reconciles different OS paradigms — library OS, multiserver OS, and microkernels — in the same OS environment for better performance, security, and reliability. LibrettOS was transitioned to IARPA's industry performers and U.S. Government technology evaluators. As part of an ONR-funded effort, he designed a class of lock-free and wait-free algorithms with better performance, memory efficiency, and transparency than prior art. Results from his research have been published at SOSP, PLDI, PPoPP, PODC, DISC, and VEE. He served as a reviewer for IEEE Transactions on Parallel and Distributed Systems in 2020 and 2021, and as an external reviewer for DISC 2018, DISC 2019, and SYSTOR 2020. 

More details about Dr. Nikolaev are available at: https://rusnikola.github.io/