COMS W4118 Operating Systems I

Spring 2023 Course Overview

• TR 5:40pm-6:55pm, 501 Schermerhorn Hall
  • CourseWorks open to whole Columbia first few weeks - search on Vergil
• Three synchronous and in-person exams for all sections:
  • Exam 1: Thursday Feb 16, 5:40pm
  • Exam 2: Tuesday Apr 18, 5:40pm
  • Exam 3: Tuesday May 9, 7:30pm

  (Exams can be switched to online format if necessary.)

  All students in all sections MUST take the exams at those times. There are no make-up or alternate exams. If you cannot make any of those exams, please take the course next semester.

• Instructors: Jae Woo Lee and Hans Montero
• Office hours: Calendar
• REQUIRED READING: ACADEMIC HONESTY POLICIES
• Anonymous feedback form
• 4118 Dev Guides

HW Due Dates

Date	Assignment
F 1/20	HW0 due
F 1/27	HW1 due
Sa 2/11	HW3 due
Sa 2/25 Su 2/26	HW4 due
Sa 3/11 Su 3/12 (Hard Deadline)	HW5 due
Su 4/2 T 4/4 (Hard Deadline)	HW6 due
F 4/14 (Hard Deadline)	HW7 due
T 5/2 (Hard Deadline)	HW8 due

Course Schedule

1/17

Course overview and logistics

• Lecture:
  • L00-overview

• Assignments:

  1. Subscribe to 4118 ListServ – see L00 above for detail

  2. Read the following two documents:
     • http://www.cs.columbia.edu/education/honesty
     • http://www.cs.columbia.edu/~jae/honesty.html

  3. HW0 (50 points, individual assignment) – due Fri 1/20, 11:59pm

     Send an email to Jae and Hans containing:

     • To: jae@cs.columbia.edu, hans@cs.columbia.edu
     • Subject: “[4118] hw0-UNI” – without quotes, sole space before hw0, UNI replaced with your actual UNI in lowercase
     • Your name, major & school program, year – ex) Jae Woo Lee, Physics, Columbia College, class of 1994
     • Your pledge – see http://www.cs.columbia.edu/~jae/honesty.html
     • CS classes taken and/or other programming background
     • Optionally anything else you want to let me know
     • Optionally attach a picture of you, but please reduce image file size to about 100KB
  4. HW1 (100 points, individual assignment) – due Fri, 1/27, 11:59pm
     • see details below
  5. Reading assignment:
     • APUE: chapter 1, 2.3, 2.4
     • OSTEP: chapter 2
     • LKD: chapter 1
  6. Start forming your group of three people

---

HW1: VM Setup & Linux Linked List

• Individual assignment, 100 points, due Fri 1/27
  • Part A: Setup Debian Linux VM
  • Part B: Linux Linked List

---

1/19

Introduction to UNIX

• Lecture:
  • L01-unix-intro

1/24

Linux System Overview

• Lecture:
  • L02-boot-to-panic
  • Source code

1/26

UNIX File I/O

• Reading:
  • APUE 3.1 - 3.13
  • APUE 8.1 - 8.10
  • APUE chapter 5 (skim)
• Lecture:
  • L03-file-io
  • Source code

---

HW2

• There is no HW2
  • Just like Windows 9 xD
  • A couple of years ago, Jae removed one of the earlier assignments. Instead of shifting the rest of the assignments by one, Jae decided to skip HW2 to make it easier on the teaching staff.

Recitation: Sockets API and HTTP 1.0 in preparation for HW3

• Sunday 1/29: Zoom recitation led by TAs Jeremy and Joy
  • See Zoom Class Sessions on Courseworks or OH calendar for the link
  • Will be recorded and uploaded to Video Library
• Topics covered:
  • Sockets API by walking through a basic web server code
  • HTTP 1.0 protocol by connecting to the web sever using netcat
  • HW3 overview
  • HW3 - stress testing with siege
• Recitation notes & files:
  • B-Sockets-ServerTesting
• Please watch it if:
  • you don’t know sockets API
  • you don’t know HTTP 1.0
  • you don’t know how to use netcat (nc)
• References:
  • Beej’s Guide to Network Programming
  • HTTP Made Really Easy
  • APUE, Chapter 16

HW3: Multi-Server

• Group assignment, 150 points, due Sat 2/11
  • Multi-Server
  • Test web page & scripts

---

1/31

Signals

• Reading:
  • APUE 9.4 - 9.6: skim, just to get a sense of process group, session, and controlling terminal
  • APUE 9.7: skim pages 299-301, skip rest – just to get a sense of jobs running in foreground and background
  • APUE 10.1 - 10.6 (skim signal descriptions in 10.2)
  • APUE 10.8 - 10.9
  • APUE 10.10: you can skip pages 340-341 & 343 (but interesting read if you know setjmp() / longjmp() or willing to find out)
  • APUE 10.11 - 10.13
  • APUE 10.14: skip page pages 352-353
• Lecture:
  • L04-signals
  • Source code

2/2

Interprocess communication in UNIX

• Reading:
  • APUE 15.2, 15.5
  • APUE 15.10
    • APUE 15.8 (just pgs 565-566): semaphore semantics
  • APUE 7.6 - 7.7
  • APUE 7.8: a little bit off-topic, so optional
  • APUE 14.8: read page 525-527, skim the rest
  • APUE 15.9: page 576-578
• Lecture:
  • L05-ipc
  • Source code

2/7

POSIX threads

• Reading:
  • APUE 11.1 - 11.4
  • APUE 11.5: read page 388-393; skip the rest of 11.5
  • APUE 11.6: read up to (and including) 11.6.6
• Lecture:
  • L06-thread
  • Source code

2/9

Nonblocking I/O and I/O multiplexing

• Reading:
  • APUE 14.2
  • APUE 14.4.0 (i.e., page 500-501)
  • APUE 14.4.1
• Lecture:
  • L07-adv-io
  • Source code

UNIX domain sockets

• Reading:
  • APUE 17.1
  • APUE 17.2: pages 631-633 are optional, but recommended
  • APUE 17.2.1
  • APUE 17.3: pages 637-641 are optional, but recommended
  • APUE 17.4: read 642-643, skip the rest
• Lecture:
  • L08-dom-sock
  • Source code

2/14

Exam 1 Review

2/16

Exam 1

• Coverage
  • HW1 and HW3
  • All lecture materials up to and including L08-dom-sock
  • All ANN emails
  • All assigned textbook readings

---

HW4: Tabletop

• Individual assignment, 100 points, due Sat 2/25 Sun 2/26
  • Tabletop

---

2/21

Linux system calls

• Reading:
  • OSTEP chapter 4 (previously assigned)
  • OSTEP chapter 6 (previously assigned)
  • LKD chapter 2
  • LKD chapter 3: skim pages 37-40
  • LKD chapter 5
• Lecture:
  • L09-syscalls

2/23

Run queues and wait queues

• Reading
  • Process states (previously assigned)
    • OSTEP 4.4
    • LKD pages 27-28
  • Scheduling basics & wait queues
    • LKD pages 57-61
• Lecture
  • L10-run-wait-queues

---

HW5: Fridge

• Group project, 200 points, due Sat 3/11 Sun 3/12 (Hard Deadline)
  • Fridge

---

2/28

Interrupts & Spin Locks

• Reading:
  • Interrupts: LKD chapter 7
  • Kernel locks: LKD chapter 10: pages 183 (from Spin Locks) - 202
  • Preemption: LKD pages 62 - 64 (before Real-Time Scheduling Policies)
• Lecture:
  • L11-interrupt-spinlock

3/2, 3/7

Synchronization

• Reading:
  • OSTEP chapter 28 (sections 28.9, 28.10, 28.11, and 28.15 are optional)
  • OSTEP chapter 30
  • OSTEP chapter 31
  • Optionally, read java.lang.Object API doc about wait(), notify(), notifyAll() if you haven’t already
• Lecture:
  • L12-synchro-1
  • L13-synchro-2

3/9

Scheduling algorithms

• Reading:
  • OSTEP chapters 7, 8
• Lecture:
  • L14-sched-algo

3/14, 3/16

Spring Break – No Class

---

HW6: Freezer

• Group project, 250 points, due Sun 4/2 Tue 4/4 (Hard Deadline)
  • Freezer

---

3/21

Scheduling in Linux

• Reading:
  • OSTEP chapters 9, 10
  • LKD chapter 4:
    • pages 42 (Linux’s Process Scheduler) - 50
    • optional, but recommended: pages 50 - 56
    • pages 57 - 64: previously assigned, but read again
    • pages 64 - 67
• Lecture:
  • L15-linux-rt-cfs
  • L16-linux-sched-class

3/22

Introduction to Paging

• Reading:
  • Address translation basics: OSTEP chapter 15
  • Segmentation: OSTEP chapter 16 (skim)
    • see this blog if you want to learn about x86 segmentation (optional)
  • Free-space management: OSTEP chapter 17 (optional)
    • read through this if you’re interested in how memory allocators like malloc() work
  • Paging: OSTEP chapter 18
• Lecture:
  • L17-paging-intro

3/28

x86 Page Tables

• Reading:
  • pages 25-26 from the xv6 OS guide
    • Note that xv6 is not Linux, it is another UNIX-like OS
  • OSTEP 20.3, skip rest of chapter 20
• Lecture:
  • L18-x86-paging

Translation Lookaside Buffer (TLB)

• Reading:
  • OSTEP chapter 19
• Lecture:
  • L19-TLB

3/30

Virtual Memory Beyond Physical Memory

• Reading:
  • OSTEP chapter 21
  • OSTEP chapter 22
• Lecture:
  • L20-virt-mem

---

HW7: Farfetch’d

• Group project, 125 points, due Fri 4/14 (Hard Deadline)
  • Farfetch’d

---

4/4

Linux Memory Management

• Lecture:
  • L21-linux-mm
  • Source code

4/6

Storage Devices: HDD and SSD

• Reading (all optional)
  • OSTEP chapters 36, 37, and 44
• Lecture
  • L22-ssd-hdd

Block Allocation Strategies

• Reading
  • OSTEP chapter 40
• Lecture
  • L23-block-allocation

4/11

UNIX File System

• Reading
  • APUE 4.14, 4.15
  • OSTEP chapter 41
• Lecture
  • L24-unix-fs

Journaling

• Reading:
  • OSTEP chapter 42
• Lecture:
  • L25-journaling

4/13

Exam 2 Review

4/18

Exam 2

• Coverage
  • HW4, HW5, and HW6
    • HW4: focus on syscall material, not the fdtable stuff
  • All lecture materials between L09-syscall and L16-linux-sched-class
    • Review semaphore material from L05-ipc
    • Review pthread material from L06-thread
  • All ANN emails
  • All assigned textbook readings

---

HW8: Pantry

• Group project, 250 points, due Tue 5/2 (Hard Deadline)
  • Pantry

---

4/20

Log-Structured File System

• Reading
  • OSTEP chapter 43
• Lecture:
  • L26-lfs

Linux file system architecture

• Reading:
  • LKD chapter 13
  • LKD chapter 14: pages 289 - 294
  • See HW8 Part 2 for more resources you can read and reference.
• Lecture:
  • L27-linux-vfs

Course Wrap Up

• Lecture:
  • L28-wrap-up

4/25

Speed read()-ing: The Quest to Accelerate RocksDB Reads Using eBPF

Guest lecture presented by Jeremy Carin and Tal Zussman, current OS TAs

Modern SSDs have improved substantially in recent decades, to the point where the kernel storage software stack is quickly becoming a bottleneck when issuing I/O requests. In response, Columbia researchers recently designed XRP, a framework to safely inject user code into the kernel with eBPF to speed up storage requests for structured data. We will describe our work integrating RocksDB, a highly-optimized key-value store, with XRP, and in the process take you on a whirlwind tour of several key kernel subsystems in this lecture with a narrative.

• slides

4/27

Virtualization: Concepts and Applications

Guest lecture presented by Kent Hall, VMware software engineer and former OS TA

You’ve been pulling your hair out over your virtual machines all semester, but ever wonder how they work? This lecture offers a general overview of virtualization concepts which have enabled the performant execution of isolated guest operating systems. We’ll then take a peek into KVM, the hypervisor built right into the Linux kernel, for an applied demonstration of these concepts.

• slides
• code

5/9

Exam 3

• Coverage
  • HW7 and HW8
  • All lecture materials between L17-paging-intro and L27-linux-vfs
  • Review memory/FS related material from earlier in the semester, i.e.,
    • L03-file-io: skip C std i/o and buffering
    • HW4: focus on the file i/o data structures, not the syscall stuff
    • L05-ipc: mmap()
  • All ANN emails
  • All assigned textbook readings

---

Last updated: 2023-05-09