Courses/Computer Science/CPSC 457.F2013/Lecture Notes
Course notes are available from here.
- 1 Scribe Notes
- 2 Week 1
- 3 Week 2
- 4 Week 3
- 5 Week 4
- 6 Week 5
- 7 Week 6
- 8 Week 7
- 9 Week 8
- 10 Week 9
- 11 Week 10
- 12 Week 11
- 13 Week 12
- 14 Week 13
September 9: Course Overview
September 11: Background Assessment
Today you will take a brief assessment survey to gauge your background and help calibrate the course pacing and material.
September 13: What Problem Do Operating Systems Solve?
The unifying theme for this week is the focus question: "how does a program become a process?" In discussing the transformation of a program code to a running process, the environment of multiple processes supported by the OS and hardware, and the concept of CPU multiplexing, we arrive at a fundamental understanding of the operating system as a piece of software that enables a collection of software applications to make efficient use of the underlying hardware.
Sept 16: From Programs to Processes
You may also be interested in this material (note that this will bring you to the wiki pages for a past version of the course -- make sure you return to the F2013 set of wiki pages):
Sept 18: What is an Operating System?
Last week, we spoke about some of the primary responsibilities and concepts involved in operating systems. Today, we will consider the "big picture" of OS structure and try to define some key terms.
Sept 20: System Architecture
This session will draw a link between what you know (or should remember) from your Computer Architecture or Computer Organization class to the picture we discussed last session. It will provide the context for some of the fundamental services operating systems provide.
Sept 23: System Calls
In this session, we will consider the key layer between the kernel and userland processes: the API defined by the system call layer. We will observe how deep the call chains originating in the system call layer go into the kernel.
We will examine how to invoke system calls via assembly code. We will consider how to observe the events taking place at the system call layer (via the strace(1) tool).
Sept 25: Process Creation and the Process Control Block
In this session, we consider how the kernel represents and keeps track of the metadata about each process. A consideration of the task_struct in Linux. Also a consideration of how processes come into existence.
Sept 27: The Process Address Space (Memory Regions)
In this session, we consider what the components of a PAS are and how parts of an ELF are mapped to it. The process address space is one of the two major defining elements of a process (the other being the process control block, e.g., the Linux task_struct), which contains the CPU context of the process).
Sept 30: Memory Addressing in the Process Address Space
In this session, we discuss how the OS cooperates with hardware (specifically, the MMU) to support the existence of multiple independent process address spaces at the same time by breaking the direct mapping between a virtual address and a physical address. We will examine how this mechanism works on x86 Linux.
Oct 2: Test 1
Test 1 takes place October 2. It is a closed book, no notes written exam.
Oct 4: Virtual Memory
Oct 7: Page Replacement
How does the kernel help support virtual memory by picking which virtual page to evict from a physical page frame?
Oct 9: Recap
In this session, we'll take stock of where we've been and check our collective understanding of the concepts introduced so far.
- test 1 results
- HW2 overview
- the big picture
- think-pair-share questions
- If we didn't have computers, would we still need operating systems?
- What is the difference between:
- protected mode
- supervisor mode
- kernel space
- the root account
Oct 11: User--level Memory Management
Oct 14: No Class (Thanksgiving)
No class Oct 14 (Canadian Thanksgiving)
Oct 16: Intro to Kernel Memory Management
An introduction to the kernel side of memory management, starting from the kernel-side of the brk(2) interface. A tour of Linux kernel source code.
Oct 18: Kernel Memory Management (cont.)
A discussion of how the kernel manages its own memory, both from a kernel programming perspective as well as an internal organization (SLAB, SLUB, SLOB) perspective.
Oct 21: System Startup
A consideration of booting as an interesting activity in and of itself, with applications to the idea of concurrency and process scheduling. One of my favorite topics. We'll start with a look at booting (your VM) from the user's perspective.
Oct 23: HW1 Review and HW2 Hints
A discussion on ways to solve the HW1 problems (grades and answers will be distributed soon) and a preview of how HW2 might be approached.
- Scribe notes
Oct 25: Process Scheduling
We've seen how the OS can transition from sequential code execution to concurrent execution; it:
- initializes the scheduler
- creates two processes (via do_fork and via sys_execve)
- enables interrupts;
- and then allows the newly created scheduler to begin choosing between these two processes.
- In the meanwhile, one of the processes (the init process) begins creating children via do_fork() and sys_execve()
This procedure naturally brings up the question: as more processes are created, and some hundred or thousand processes come to exist, how does the OS choose which process should be given the CPU?
Oct 28: Clocks, Timing, Interrupts, and Scheduling
A consideration of the hardware and OS support necessary to enable scheduling.
Oct 30: Concurrency Concepts: Communication and Synchronization
Nov 1: Deadlock
Nov 4: Kernel Synchronization Primitives
The kernel is an excellent case study of the general and abstract synchronization primitives we learned about in our deadlock discussion.
Nov 6: Test 2
An in-class written exam. No text, no notes.
Nov 8: Threads (User--level Concurrency)
Concurrency with pthreads. Concurrency via clone(2)
Nov 11: Remembrance Day (no class)
Remembrance Day is 11 November. No class.
Nov 13: Signals
Signals provide a simple form of IPC that is, of course, mediated by the operating system; this is a capstone case study in our discussion of concurrency. Signals offer a form of asynchronous event notification for Unix processes.
Nov 15: Files and File I/O
We begin our discussion of persistent storage.
Nov 18: File Systems Overview
Nov 20: The Linux VFS
Nov 22: Extended Attributes in Ext4
Support for extended attributes, labels, and ACLs.
Nov 25: Example File Systems
Nov 27: Devices
Nov 29: Disk and I/O Scheduling
Dec 2: User--level Networking / USRI
Dec 4: Kernel Network Support
Dec 6: Final Exam Review
- concept map
- syllabus topic list
- major problem types
- file indexing / FS structure
- disk scheduling
- process scheduling
- memory allocation
- page replacement
- memory address translation
- performance questions (timing, I/O speed, etc.)
- all MOS readings
- entire semester
- 2 hours
- 200 points (20% of your grade)
- 1 sheet of notes
- MOS: 1.1: What is an Operating System?
- MOS: 1.2: History of Operating Systems
- MOS: 1.4: The Operating System Zoo
- MOS: 1.5: Operating System Concepts
- MOS: 10.1: History of Unix and Linux
- MOS: 13.1: The Nature of the Design Problem
- MOS: 1.3: Computer Hardware Review
- MOS: 1.6: System Calls
- MOS: 1.7: Operating System Structure
- MOS: Section 2.1: Processes (this should be partly review of what we've talked about in class)
- MOS: Section 3.2.1: The Notion of an Address Space
- MOS: Section 3.7 (all except 3.7.2) (this should review some of what we touched on in the previous class and lay some groundwork for talking about memory management)
- MOS: Section 10.2.5 (Linux kernel structure)
- MOS: Section 10.3.1 (about processes in Linux) should reinforce some class discussion
- MOS: 10.3.5: "Booting Linux"
- MOS: 2.4.1 "Introduction to Scheduling" (plus 2 intro paragraphs in S2.4)
- MOS: 2.4.5 "Policy vs. Mechanism"
- MOS: 10.3.4: "Scheduling in Linux"
- MOS: 2.7 "Summary" (this talks about some things we'll consider next)
- MOS: 5.5 "Clocks"
- MOS: 3.2.3
- MOS: 3.1 "No Memory Abstraction"
- MOS: 3.2 "A Memory Abstraction: Address Spaces"
- MOS: 3.3 "Virtual Memory" (this subsection also contains a review of paging and TLBs)
- MOS: 3.7.3 "Segmentation with Paging: The Intel Pentium"
- MOS: 3.4
- MOS: 2.2 "Threads"
- MOS: 2.3 "Interprocess Communication"
- MOS: 2.5 "Classical IPC Problems" Beware typos in Figure 2-23, pg 122 (semicolon placement)
- MOS: 6.2 "Introduction to Deadlocks" (NB: MOS 6.2.1 should be memorized!)
- MOS: 6.4 "Deadlock Detection and Recovery"
- MOS: 6.5 "Deadlock Avoidance"
- MOS: 6.6 "Deadlock Prevention"
- MOS: 4.1
- MOS: 4.2
- MOS, Chapter 4.3: File System Implementation
- MOS, Chapter 4.5: Example File Systems
- MOS, Chapter 10.6: The Linux File System
- MOS: 5.1 Principles of I/O Hardware
- MOS: 5.2 Principles of I/O Software
- MOS: 5.4 Disks