The following schedule is tentative and subject to change without notice.

Credit: Some of the slides are borrowed from the authors’ presentations.

Projects

Assignment #1: System Call

Add a new system call named readbytes() that returns the total number of bytes returned by the read() system call so far. Set the system call number of readbytes() to 500.

Due: 11:55PM, September 26.

Submission: Click here to upload your compressed patch file and design document (Note: The submission is closed on 11:55PM September 26). Note that you should also upload a 1-page design document file (in PDF format) that briefly describes your implementation.

How to setup your Linux kernel

• Install VirtualBox 6.1.26 on your machine
• Install Ubuntu 20.04.3 LTS in your VirtualBox
• Download the reference Linux kernel 5.10.61

$ wget https://kernel.org/pub/linux/kernel/v5.x/linux-5.10.61.tar.xz
$ tar xvf linux-5.10.61.tar.xz

• Install prerequisite packages

$ sudo apt install build-essential ncurses-dev libssl-dev flex bison libelf-dev

• Compile the Linux kernel 5.10.61 (use x86_64_defconfig to configure your kernel)

$ cd linux-5.10.61
$ make x86_64_defconfig
$ make all
$ sudo make modules_install
$ sudo make install

How to prepare your compressed patch file

You can prepare a compressed patch file as follows. Assume that the vanilla 5.10.61 kernel is in the ./linux-5.10.61-vanilla directory, while your modified kernel is in the ./linux-5.10.61 directory.

$ (cd linux-5.10.61-vanilla; make distclean)
$ (cd linux-5.10.61; make distclean)
$ diff -uprN linux-5.10.61-vanilla linux-5.10.61 > studentID.patch
$ gzip studentID.patch

Please double-check your patch file whether it contains some unnecessary materials. Also, please make sure that you should build your kernel with the x86_64_defconfig configuration file.

For more details on generating a patch file, please refer to here.

Reference Platform

The following shows the reference platform used in this course.

• VirtualBox 6.1.26
• Ubuntu 20.04.3 LTS
• Kernel version 5.10.61

Linux Kernel Resources

• The Linux Kernel Archives
• The Linux Kernel Documentation
• Linux Cross Rereference
• Kernel Page in LWN.net
• Ftrace: 1, 2, 3
• Linux Performance Tools (Also see here)
• How to use vim with ctags and cscope

Historical Perspective

• (H1) ⭐️ D. Ritchie and K. Thompson, “The UNIX Time-Sharing System,” CACM, 1974. (The SIGOPS Hall of Fame Award ‘05)

Computer Systems Research

• (I1) ⭐️ Butler W. Lampson, “Hints for Computer System Design,” SOSP, 1983. (The SIGOPS Hall of Fame Award ‘05)

• (I2) Roy Levin and David D. Redell, “An Evaluation of the Ninth SOSP Submissions or How (and How Not) to Write a Good Systems Paper,” ACM Operating Systems Review, 1983.

• (I3) Aaron B. Brown, Anupam Chanda, Rik Farrow, Alexandra Fedorova, Petros Maniatis, and Michael L. Scott, “The Many Faces of Systems Research - And How to Evaluate Them,” HotOS, 2005.

File Systems

• (FS1) ⭐️ Marshall K. McKusick, William N. Joy, and Samuel J. Leffler, “A Fast File System for UNIX,” ACM TOCS, 1984. (The SIGOPS Hall of Fame Award ‘15)

• (FS2) ⭐️ Mendel Rosenblum and John K. Ousterhout, “The Design and Implementation of a Log-Structured File System,” SOSP, 1991. (The SIGOPS Hall of Fame Award ‘12)

• (FS3) ⭐️ Changman Lee, Dongho Sim, Joo-Young Hwang, and Sangyeun Cho, “F2FS: A New File System for Flash Storage,” FAST, 2015.

SSDs

• (SSD1) ⭐️ Jeong-Uk Kang, Jeeseok Hyun, Hyunjoo Maeng, and Sangyeun Cho, “The Multi-streamed Solid-State Drive,” HotStorage, 2014.

• (SSD2) ⭐️ Jaeyoung Do, Sudipta Sengupta, and Steaven Swanson, “Programmable Solid-State Storage in Future Cloud Datacenters,” CACM, 2021.

• (SSD3) Matias Bjorling, Abutalib Aghayev, Hans Holmberg, Aravind Ramesh, Damien Le Moal, Gregory R. Ganger and George Amvrosiadis, “ZNS: Avoiding the Block Interface Tax for Flash-based SSDs,” Usenix ATC, 2021.

• (SSD4) Boncheol Gu, Andre S. Yoon, Duck-Ho Bae, Insoon Jo, Jinyoung Lee, Jonghyun Yoon, Jeong-Uk Kang, Moonsang Kwon, Chanho Yoon, Sangyeun Cho, Jaeheon Jeong, and Duckhyun Chang, “Biscuit: A Framework for Near-Data Processing of Big Data Workloads,” ISCA, 2016.

CPU Scheduling

• (S1) ⭐️ Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy, “Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism,” TOCS, 1992.

• (S2) ⭐️ Carl A. Waldspurger and William E. Weihl, “Lottery Scheduling: Flexible Proportional-Share Resource Management,” OSDI, 1994.

• (S3) Carl A. Waldspurger and William E. Weihl, “Stride Scheduling: Deterministic Proportional-Share Resource Management,” Technical Memorandum MIT/LCS/TM-528, MIT Laboratory for Computer Science, 1995.

• (S4) Jean-Pierre Lozi, Baptiste Lepers, Justin Funston, Fabien Gaud, Vivien Quema, and Alexandra Fedorova, “The Linux Scheduler: a Decade of Wasted Cores,” EuroSys, 2016.

Virtual Memory

• (MM1) ⭐️ Juan Navarro, Sitaram Iyer, Peter Druschel, and Alan Cox, “Practical, Transparent Operating System Support for Superpages,” OSDI, 2002.

• (MM2) ⭐️ Nimrod Megiddo and Dharmendra S. Modha, “ARC: A Self-Tuning, Low Overhead Replacement Cache,” FAST, 2003. (USENIX Test of Time Award ‘14)

• (MM3) Youngjin Kwon, Hangchen Yu, Simon Peter, Christopher J. Rossbach, and Emmett Witchel, “Coordinated and Efficient Huge Page Management with Ingens,” OSDI, 2016.

Virtual Machines

• (VM1) ⭐️ Edouard Bugnion, Scott Devine, and Mendel Rosenblum, “Disco: Running Commodity Operating Systems on Scalable Multiprocessors,” SOSP, 1997. (Best Paper Award, The SIGOPS Hall of Fame Award ‘08)

• (VM2) Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, and Andrew Warfield, “Xen and the Art of Virtualization,” SOSP, 2003.

• (VM3) Carl A. Waldspurger, “Memory Resource Management in VMware ESX Server,” OSDI, 2002. (Best Paper Award, The SIGOPS Hall of Fame Award ‘15)

• (VM4) Christopher Clark, Keir Fraser, Steven Hand, Jacob Corm Hansen, Eric Jul, Christian Limpach, Ian Pratt, and Andrew Warfield, “Live Migration of Virtual Machines,” NSDI, 2005. (USENIX Test of Time Award ‘05)

OS Design

• (OS1) The Tanenbaum-Torvalds Debate, 1992.

• (OS2) Jochen Liedtke, “On μ-Kernel Construction,” SOSP, 1995. (The SIGOPS Hall of Fame Award ‘15)

• (OS3) M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger, Hector M. Briceno, Russell Hunt, David Mazieres, Thomas Pinckney, Robert Grimm, John Jannotti, and Kenneth Mackenzie, “Application Performance and Flexibility on Exokernel Systems,” SOSP, 1997.

• (OS4) Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schupbach, and Akhilesh Singhania, “The Multikernel: A New OS Architecture for Scalable Multicore Systems,” SOSP, 2009.

• (OS5) Anil Madhavapeddy, Richard Mortier, Charalampos Rotsos, David Scott, Balraj Singh, Thomas Gazagnaire, Steven Smith, Steven Hand, and Jon Crowcroft, “Unikernels: Library Operating Systems for the Cloud,” ASPLOS, 2013.

• (OS6) Simon Peter, Jialin Li, Irene Zhang, Dan R. K. Ports, Doug Woos, Arvind Krishnamurthy, and Thomas Anderson, “Arrakis: The Operating System is the Control Plane,” OSDI, 2014. (Best Paper Award)

Distributed File Systems

• (DFS1) Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, “The Google File System,” SOSP, 2003. (The SIGOPS Hall of Fame Award ‘15)

• (DFS2) Sage A. Weil, Scott A. Brandt, Ethan L. Miller, Darrell D. E. Long, and Carlos Maltzahn, “Ceph: A Scalable, High-Performance Distributed File System,” OSDI, 2006.

Key-Value Stores

• (OS6) Simon Peter, Jialin Li, Irene Zhang, Dan R. K. Ports, Doug Woos, Arvind Krishnamurthy, and Thomas Anderson, “Arrakis: The Operating System is the Control Plane,” OSDI, 2014. (Best Paper Award) –>