Courses/Computer Science/CPSC 457.F2013/Lecture Notes
Course notes are available from here.
Contents
Scribe Notes
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Scribe1
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Scribe2
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Scribe3
Week 1
September 9: Course Overview
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/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?
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/ProblemOS
Week 2
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
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Prog2Proc
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):
Courses/Computer_Science/CPSC_457.W2012/Lecture Notes/Prog2Proc
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.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/WhatOS
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.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/SysArch
Week 3
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).
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/SystemCalls
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.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Creation
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).
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/ProcAddrSpace
Week 4
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.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/MemAddr
Oct 2: Test 1
Test 1 takes place October 2. It is a closed book, no notes written exam.
Oct 4: Virtual Memory
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/VirtualMemory
Week 5
Oct 7: Page Replacement
How does the kernel help support virtual memory by picking which virtual page to evict from a physical page frame?
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/PageReplacement
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
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/UserMem
Week 6
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.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/KernMem
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.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/KernMem
Week 7
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.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Startup
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
- s1
- s2
- s3
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?
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Scheduling
Week 8
Oct 28: Clocks, Timing, Interrupts, and Scheduling
A consideration of the hardware and OS support necessary to enable scheduling.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Timing
Oct 30: Concurrency Concepts: Communication and Synchronization
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Concurrency
Nov 1: Deadlock
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Deadlock
Week 9
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.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/KernSync
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)
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Threads
Week 10
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.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Signals
Nov 15: Files and File I/O
We begin our discussion of persistent storage.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/FileIO
Week 11
Nov 18: File Systems Overview
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Filesystems
Nov 20: The Linux VFS
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/VFS
Nov 22: Extended Attributes in Ext4
Support for extended attributes, labels, and ACLs.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/XAttr
Week 12
Nov 25: Example File Systems
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/ExampleFileSystems
Nov 27: Devices
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/Devices
Nov 29: Disk and I/O Scheduling
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/DiskScheduling
Week 13
Dec 2: User--level Networking / USRI
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/UserNetworking
Dec 4: Kernel Network Support
Netfilter, etc.
Courses/Computer_Science/CPSC_457.F2013/Lecture Notes/KernelNetworking
Dec 6: Final Exam Review
Agenda
- concept map
- syllabus topic list
- major problem types
- threading
- deadlock
- 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
Exam Parameters
- entire semester
- 2 hours
- 200 points (20% of your grade)
- 1 sheet of notes
Collected Readings
- 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