COMS W4118 Operating Systems I

Spring 2017

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/19~~	~~HW0 due~~
~~T 1/24~~	~~HW1 due~~
~~Sa 2/4~~	~~HW2 due~~
~~T 2/21~~	~~HW3 due~~
~~T 2/28~~	~~HW4 due~~
~~T 3/7~~	~~Exam #1~~
~~R 3/9~~	~~Class canceled - Instructor attending conference~~
~~T 3/14, R 3/16~~	Spring break – No class
~~Su 3/26~~	~~HW5 due~~
~~F 4/7~~	~~HW6 due~~
~~R 4/20~~	~~Exam #2~~
M 4/24	HW7 due
T 5/2	HW8 due

Syllabus

T 1/17: 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/19 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/24 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/19: Introduction to OS

Lecture:
- L01-intro1-osc-ch1
- L02-intro2-osc-ch2

T 1/24: Linux System Overview

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

R 1/26, T 1/31: 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

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

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 Sat 2/4
- Makefile & simple.c

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

Each of the following two sessions will cover the same topics:
- Sunday 2/5, 8:20pm–9:35pm
  - CLIC lab (CS 486 - enter thru Fairchild Building)
  - Led by Andy Xu
- Friday 2/10, 5:40pm–6:55pm
  - 633 Mudd
  - Led by Kevin Chen
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 in 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: HTTP Server – Group project

Assignment:
- HW3-http-server – due ~~Sun Feb 19th~~ Tue Feb 21st
- Test web page & scripts

T 2/7: 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

R 2/9: Class canceled due to snow storm

T 2/14: 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

R 2/16: 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/16, T 2/21: 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/21, R 2/23: Linux system calls

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

HW4: Linux System Calls – Individual assignment

Assignment:
- HW4-syscall – due Tue, Feb 28th

T 2/28: Synchronization I

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

R 3/2: Linux processes, Run queues & Wait queues, 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:
- L12-proc-queues
- L13-spinlock

T 3/7: Exam #1

R 3/9: Class canceled - Instructor attending conference

T 3/14, R 3/16: Spring break – No class

HW5: Fridge – Group project

Assignment:
- HW5-fridge
- Skeleton code
- Due date: Sun, Mar 26th

T 3/21: Interrupts, Spin Locks, and Preemption

Lecture:
- L13-spinlock

R 3/23: 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:
- L14-sched–1

T 3/28: 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:
- L15-sched–2

HW6: Freezer – Group project

Assignment:
- HW6-freezer
- Due date: Fri, Apr 7th – new deadline

R 3/30: 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:
- L16-disk

R 3/30, T 4/4: 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:
- L17-fs–1

R 4/6: 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:
- L18-fs–2

T 4/11: Linux file system architecture

Reading:
- LKD chapter 13
- LKD chapter 14: pages 289 - 294
- See HW7 Part 2 for more resources you can read and reference.
Lecture:
- L19-fs–3
- Page cache overview

HW7: Pantry – Group project

Assignment:
- HW7-pantry
- Skeleton code
- Due date: Mon, Apr 24th

Thread design and implementation – Optional – not covered in class

Reading:
- OSC: 4.1 - 4.3
- OSC: Optionally 4.5
- OSC: 4.6 - 4.7
Lecture:
- L20-thread-impl

R 4/13: 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:
- L21-synchro–2

T 4/18: 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:
- L22-paging

R 4/20: Exam #2

HW8: Cabinet – Group project

Assignment:
- HW8-cabinet
- Skeleton code
- Due date: Tue, May 2nd

T 4/25: 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:
- L23-virt-mem

R 4/27: Semester review

L24-review

Last updated: 2017–04–27