COMS W4118 Operating Systems I

Spring 2018

TR 11:40am–12:55pm
501 Northwest Corner Building
Instructor: Jae Woo Lee
Office hours:
- Jae’s office hours
- TA office hours
REQUIRED READING: ACADEMIC HONESTY POLICIES

Important dates

~~R 1/18~~	~~HW0 due~~
~~T 1/23~~	~~HW1 due~~
~~T 2/6 (hard deadline)~~	~~HW2 due~~
~~Sa 2/24~~	~~HW3 due~~
~~Su 3/4~~	~~HW4 due~~
~~R 3/8~~	~~Exam #1~~
~~W 3/28~~	~~HW5 due~~
~~T 4/10~~	~~HW6 due~~
~~T 4/17~~	~~HW7 due~~
~~R 4/19~~ T 4/24	Exam #2
R 5/3 (hard deadline)	HW8 due (24-hr late submission not available)
	No final exam

Syllabus

T 1/16: Course overview and logistics

Lecture:
- L00-overview
Assignments:
1. Subscribe to 4118 ListServ – see L00-overview 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/18 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 (100 points, individual assignment) – due Tue 1/23 11:59pm
  - Part A: Setup Arch Linux VM
  - Part B: Write launchx program
5. Reading assignment:
  - APUE: chapter 1, 2.3, 2.4
  - OSCE2/OSC9: 1.2, 1.4, 1.5, 1.8.3, 2.7, 2.10
  - LKD: chapter 1
6. Start forming your group of three people

R 1/18: Introduction to UNIX

Lecture:
- L01-osc-ch1-ch2-summary – review of OSC chapters 1 & 2 – skipped in class
- L02-unix-intro

R 1/18, T 1/23: Linux System Overview

Lecture:
- L03-boot-to-panic
- Source code

R 1/25, T 1/30: UNIX File I/O

Reading:
- APUE 10.1 - 10.6 (skim signal descriptions in 10.2)
- APUE 3.1 - 3.13
- APUE 8.1 - 8.10
Lecture:
- L04-file-io
- Source code

HW2: Linux Linked List

Reading:
- OSC: 3.1, 3.2
- LKD: Chapter 6, page 85–96
- ULK: page 87–90
- see hw2 instruction for details
Assignment:
- HW2-linked-list – due Sun 2/4

T 1/30, R 2/1: 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

T 2/6: Signals

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-signal

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

Each of the following two sessions will cover the same topics:
- Tuesday Feb 6th, 8:00pm–9:30pm, Pupin 329, led by John Hui
- Sunday Feb 11th, 5:00pm–6:30pm, Math 312, led by JiaYan Hu
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, 250 points, due Sat Feb 24th

Assignment:
- HW3-multi-server
- Test web page & scripts

R 2/8, T 2/13: 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:

T 2/13, R 2/15: 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

R 2/15, T 2/20: 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

T 2/20, T 2/27: Linux system calls

Reading:
- LKD chapter 2
- LKD chapter 3: skim pages 37–40
- LKD chapter 5
Lecture:
- L10-syscall

R 2/22: Class canceled - Instructor attending conference

HW4: Linux System Calls – Individual assignment, 100 points, due Sun Mar 4th

Assignment:
- HW4-syscall

R 3/1, T 3/6: Synchronization I

Reading:
- OSC: 5.1 - 5.5
Lecture:
- L11-synchro–1

T 3/6: Synchronization II

Reading:
- OSC: 5.6 - 5.7
- OSC: 5.8
  - 5.8.3 is optional; the section is so badly written that it won’t make any sense; last few slides of this will help
  - In 5.8.4, only read “Java Monitors” box on page 232 (same page in both OSCE2 & OSC9)
- Read java.lang.Object API doc about wait(), notify(), notifyAll() if you haven’t already
Lecture:
- L12-synchro–2

R 3/8: Exam #1

T 3/13, R 3/15: Spring break – No classes

HW5: Fridge – Group project, 220 points, due Wed Mar 28th

Assignment:
- HW5-fridge

T 3/20, R 3/22: Run queues & Wait queues, Interrupts, Spin Locks

Reading:
- LKD chapter 3 (previously assigned; you can skim pages 37–40)
- 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:
- L13-run-wait-queues
- L14-interrupt-spinlock

T 3/27: Scheduling algorithms

Reading:
- OSCE2/OSC9:
  - 6.1 - 6.3
  - 6.5 (6.5.4 is optional)
  - 6.6.0 - 6.6.2
  - 6.7.1
  - 6.7.2: optional but recommended
Lecture:
- L15-scheduling–1

R 3/29, T 4/3: Scheduling in Linux

Reading:
- 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 Tue Apr 10th

Assignment:
- HW6-freezer

R 4/5, T 4/10: Memory management: Paging

Reading from OSCE2 chapter 7 (note that it is chapter 8 in OSC9)
- Required:
  - 7.5
  - 7.6.1, first half (before they start talking about VAX)
  - pages 25–26 from http://pdos.csail.mit.edu/6.828/2012/xv6/book-rev7.pdf
- Optional, if you want to know x86 memory management in more detail:
  - 7.4
  - 7.7
  - http://duartes.org/gustavo/blog/post/memory-translation-and-segmentation/
  - 7.8 (describes paging in ARM)
- Optional, if you’re curious about alternate page table structures used in other CPUs
  - 7.6.1, 2nd half - 7.6.4
Lecture:
- L17-paging

R 4/12: Memory management: Virtual Memory

Reading from OSCE2 chapter 8 (note that it is chapter 9 in OSC9)
- 8.1
- 8.2
- optionally read OSCE2 9.6 (OSC9 10.6) swap-space management
- 8.3
- 8.4: skim or skip 8.4.6 - 8.4.8
- 8.6: skim - just need to know what thrashing and working set mean
- 8.7.1
- 8.7.3
- optionally read 8.8
- 8.9.5
- 8.9.6
Lecture:
- L18-virt-mem

HW7: Cabinet – Group project, 100 points, due Mon Apr 16th

Assignment:
- HW7-cabinet

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

Reading:
- OSCE2 9.1, 9.2, 9.4 - optional
  - Note that in OSC9 they are 10.1, 10.2, 10.4
Lecture:
- L19-disk

T 4/17: Block allocation methods & UNIX file system

Reading:
- OSCE2 11.4, 11.5 (skim or skip 11.5.5)
  - Note that in OSC9 they are 12.4, 12.5
- APUE 4.14, 4.15
Lecture:
- L20-fs–1

R 4/19: Journaling and log-structured file system

Reading:
- OSCE2 10.4 (OSC9 11.4)
- OSCE2 11.7 (skip 11.7.4)
  - Note that in OSC9 this is 12.7 (skip 12.7.4)
Lecture:
- L21-fs–2

T 4/24: Exam #2

HW8: Pantry – Group project, 250 points, due Thu May 3rd

Assignment:
- HW8-pantry
- 5/3 is a hard deadline, i.e. 24-hr late submission is not available

R 4/26: 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:
- L22-fs–3
- Page cache overview

R 4/26: Semester review

L23-review

Last updated: 2018–04–26