COMS W4118 Operating Systems I

Spring 2019

• TR 11:40am-12:55pm
• 517 Hamilton Hall
• Instructor: Jae Woo Lee
• Office hours:
  • Jae’s office hours
  • TA office hours
• REQUIRED READING: ACADEMIC HONESTY POLICIES

Important dates

Syllabus

T 1/22: 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 Thu 1/24 11:59pm

     Send me an email containing:

     • 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 – coming soon

  5. Reading assignment:

     • APUE: chapter 1, 2.3, 2.4
     • OSTEP: chapter 2
     • LKD: chapter 1

  6. Start forming your group of three people

T 1/22: Introduction to UNIX

• Lecture:
  • L01-unix-intro

R 1/24: Linux System Overview

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

HW1: VM Setup & Linux Linked List

• Individual assignment, 100 points, due Sun 2/3
  • Part A: Setup Debian Linux VM
  • Part B: Linux Linked List

T 1/29, R 1/31: UNIX File I/O

• Reading:
  • APUE 3.1 - 3.13
  • APUE 8.1 - 8.10
• Lecture:
  • L03-file-io
  • Source code

R 1/31: Signals I

• Reading:
  • APUE 10.1 - 10.6 (skim signal descriptions in 10.2)
• Lecture:
  • L04-signals-1
  • Source code

R 1/31, T 2/5: Interprocess communication in UNIX

• Reading:
  • APUE 15.2
  • APUE 7.6 - 7.7
  • APUE 7.8: a little bit off-topic, so optional
  • APUE 14.8: read page 525–527, skim or skip the rest
  • APUE 15.9: skim or skip page 571–575, read page 576–578
  • APUE 15.10
• Lecture:
  • L05-ipc
  • Source code

R 2/7: Signals II

• Reading:
  • APUE 9.4 - 9.6: skim, just to get a sense of what are process group, session, and controlling terminal
  • 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 352–353
• Lecture:
  • L06-signals-2
  • Source code

HW2

• There is no HW2
  • Just like Windows 9 :)
  • Seriously, last year’s HW2 became this year’s HW1. Instead of shifting the rest of the assignments by one, I decided to skip HW2 to make it easier on the teaching staff and also on students who are referring to last year’s syllabus to look ahead.

Review Session: Sockets API and HTTP 1.0 in preparation for HW3

• Each of the following two sessions will cover the same topics:

  • Monday Feb 4th, 7:00pm - 8:30pm, CSB 480, led by Jennifer and Suhyun
  • Thursday Feb 7th, 7:00pm - 8:30pm, CSB 480, led by Jonas

• Topics covered:

  • Sockets API by walking through a basic web server code
  • HTTP 1.0 protocol by connecting to the web sever using nc

• Files:

  • Basic web server code available on Canvas
  • Test web page

• Attendance optional, but you should attend 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 project, 150 points, due Sun 2/17
  • Multi-Server
  • Test web page & scripts

R 2/7, T 2/12: 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:
  • L07-thread
  • Sample code - bank example
  • Sample code - mutex usage

R 2/14: 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:
  • L08-adv-io
  • Source code

T 2/19: 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:
  • L09-domain-sockets
  • Source code

HW4: Linux System Calls

• Individual assignment, 100 points, due Sat 2/23
  • Linux System Calls

T 2/19: 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:
  • L10-syscall

HW5: Fridge

• Group project, 200 points, due Sun 3/10
  • Fridge

R 2/28: Class canceled - Instructor attending conference

R 2/21, T 2/26, T 3/5: Run queues & Wait queues, Interrupts, Spin Locks

• Reading:
  • On wait queues: LKD pages 57 - 64 (before Real-Time Scheduling Policies)
  • On interrupts: LKD chapter 7
  • On kernel locks: LKD chapter 10: pages 183 (from Spin Locks) - 202
• Lecture:
  • L11-run-wait-queues
  • L12-interrupt-spinlock

R 3/7, T 3/12: Synchronization I

• Reading:
  • OSTEP chapter 28 (sections 28.9, 28.10, 28.11, and 28.15 are optional)
• Lecture:
  • L13-synchro-1

T 3/12: Synchronization II

• Reading:
  • OSTEP chapter 30
  • OSTEP chapter 31
  • Read java.lang.Object API doc about wait(), notify(), notifyAll() if you haven’t already
• Lecture:
  • L14-synchro-2

R 3/14: Exam #1

T 3/19, R 3/21: Spring break – No classes

T 3/26: Scheduling algorithms

• Reading:
  • OSTEP chapters 7, 8
• Lecture:
  • L15-scheduling-1

R 3/28: 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:
  • L16-scheduling-2

HW6: Freezer

• Group project, 200 points, due Mon 4/8
  • Freezer

T 4/2, R 4/4: Introduction to Paging

• Reading:
  • OSTEP chapter 15
  • OSTEP chapter 16 - skim
  • OSTEP chapter 17 - optional
  • OSTEP chapter 18
• Lecture:
  • L17-paging-intro

R 4/4, T 4/9: Paging in x86 and TLB

• Reading:
  • pages 25–26 from http://pdos.csail.mit.edu/6.828/2012/xv6/book-rev7.pdf
  • optional, if you’re curious about segmentation in x86: http://duartes.org/gustavo/blog/post/memory-translation-and-segmentation/
  • OSTEP chapter 19
• Lecture:
  • L18-TLB

HW7: Cabinet

• Group project, 100 points, due Wed 4/17
  • Cabinet

R 4/11, T 4/16: Virtual Memory Beyond Physical Memory

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

T 4/16: Disks – Optional topic – will be covered briefly

• Reading:
  • OSTEP chapter 36 - optional
  • OSTEP chapter 37 - optional
• Lecture:
  • L20-disk

HW8: Pantry

• Group project, 200 points, due Wed 5/8
  • Pantry

R 4/18: Block allocation methods & UNIX file system

• Reading:
  • OSTEP chapter 40
  • APUE 4.14, 4.15
  • OSTEP chapter 41
• Lecture:
  • L21-fs-1

T 4/23, R 4/25: Journaling and log-structured file system

• Reading:
  • OSTEP chapter 42
  • OSTEP chapter 43
• Lecture:
  • L22-fs-2

R 4/25: 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:
  • L23-linux-vfs
  • Page cache overview

T 4/30: Exam #2

R 5/2: Guest lecture: Google Production Environment

• By Howon Byun
  • A former OS TA
  • Currently a Site Reliability Engineer (SRE) at Google

R 5/2: Semester review

• L24-review

Last updated: 2019–05–02