Courses/Computer Science/CPSC 457.F2013/Lecture Notes

From wiki.ucalgary.ca
< Courses‎ | Computer Science‎ | CPSC 457.F2013
Revision as of 18:51, 2 December 2013 by Locasto (talk | contribs) (→‎Collected Readings)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

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
Retrieved from "http://wiki.ucalgary.ca/index.php?title=Courses/Computer_Science/CPSC_457.F2013/Lecture_Notes&oldid=67793"