Welcome to Operating Systems¶
You have reached the home of Operating Systems (COMP 310-410) at Loyola University Chicago in the Computer Science Department.
Note
These notes are being updated for Fall 2021.
- About the Book
- Introduction
- Introduction to Processes
- Process Memory Layout
- Process Memory Layout
- Multithreaded Memory Layout
- Preliminaries
- Examine Process Layout Example
- Loading Programs
- Loading shared libraries (.so)
- more about GCC pic option
- Loading shared libraries (.so)
- Position Independent Code Example
- main.cc
- main.nopic.s - non-position independent code (gcc -fno-pic)
- main.nopic.s - position independent code (gcc -fpic, default option)
- What’s the difference?
- Shared Libraries - Evaluation
- Static Libraries - Evaluation
- Libraries vs. Statically-Linked Programs
- Process Protection
- Process Creation with fork()
- fork() example
- Process Creation with clone()
- Windows CreateProcess() and CreateThread()
- Emulating fork() on Windows
- Causes of process termination
- wait() and waitpid() examples
- Files and I/O
- Common attributes of all (UNIX) files
- Types of Files in Unix
- Regular Files
- Folders
- Symbolic Links
- Block Device Files
- Character Device Files
- Named Pipes/FIFOs
- Unix Domain Sockets
- Filesystem System Calls
- Filesystem System Calls
- More Filesystem System Calls
- Opening Files with open()
- Closing files with close()
- Writing to a File
- Typical Write Algorithm
- Reading from a File
- Typical Read Algorithm
- Seeking within a File
- Standard File Descriptors
- Duplicating File Descriptors
- Redirecting File Descriptors
- Redirecting File Descriptors code example
- Reading Folders
- Looking Ahead: I/O Performance
- Performance
- Simple I/O Performance Experiment
- Reading/Writing Performance
- Performance Example
- Process/Thread Scheduling
- Kernel Mode vs. User Mode
- Interrupts
- Hardware Interrupts - PC Architecture
- Hardware Interrupts - Sources
- Software Interrupts
- Goals of a Process Scheduler
- Types of Scheduling Strategies
- OS Support
- Types of Processes to Schedule
- Preemptive Scheduling Key Terms
- Process states
- Choosing a Quantum
- Context Switches
- Context switching - How it works
- Degrees of Preemption
- Round - Robin Process Scheduling
- Scheduling with Multiple Queues
- Real-time Schedulers
- Example Real World RTS Problem
- Solution to Example Real World RTS Problem
- Types of Real-Time Scheduler Implementations
- Additional Concerns in Advanced Scheduler Implementations
- Process Priority and Scheduling in Linux
- Linux Real Time Scheduler
- Linux Preemptive Scheduler
- Nice Values
- Process Scheduling in Windows
- User-Mode Schedulers
- User-Mode Threads: Why?
- User-Mode Threads: Why Not?
- GNU - Pth - User Mode Pthreads
- PThreads - Kernel Threads
- Mutual Exclusion
- Critical Sections
- Identifying the Critical Section
- Execution Orders and Atomicity
- Execution Orders and Atomicity
- Characteristics of a Good Locking Solution
- Achieving Atomicity / Serializability
- Types of Pessimistic Locks
- Types of Optimistic Locks
- When to Consider Optimistic Locking
- Disabling Interrupts
- Strict Alternation
- Spin Locks
- Spin Locks - Implementation
- Spin Locks - Implementation
- Spin Locks - Implementation
- Spin Locks - Implementation
- Pthreads - Mutex
- Mutexes in Windows
- Semaphores - some history
- Semaphores
- Semaphores - Implementation
- Binary semaphores
- Event semaphores
- Semaphores - Implementation
- Semaphores - Implementation
- Semaphores - reader / writer locks
- Semaphores - reader/writer locks
- Semaphores - pthreads
- Windows - Semaphores
- Monitors / Condition Variables
- Monitors
- Monitor - bounded buffer
- Monitor - bounded buffer
- Semaphore - reader/writer lock
- Monitors - Reader / Writer locks
- Pthreads - Condition Variables
- Windows - Condition Variables
- Deadlock
- Deadlock - definition
- Dining Philosophers Problem
- Dining Philosophers - deadlock scenario
- Dining Philosophers - Lock Graph
- Dining Philosophers
- Dining Philosophers - solution 1
- Dining Philosophers - solution 2
- Dijkstra’s Solution / Bankers Algorithm
- Optimization to Dijkstra’s Solution
- Deadlock Avoidance Implementation
- Deadlock Prevention Implementation
- Example of Deadlock
- Multi-Lock Solutions in Windows
- Multi-Lock Solutions in Linux/Minix
- Deadlock with Lock Ordering
- Starvation
- Guidlines to Avoid Starvation
- Livelock
- Lock Fairness
- Lock Fairness. Pros / Cons
- IPC Topics
- IPC Performance Hierarchy
- Pipes
- Pipes
- Pipes - Linux
- Pipes - Context Switches
- Named Pipes / FIFOs
- Example usage of a regular pipe in Linux
- Named Pipes - Common Usages
- Named Pipes - Atomic Reads / Writes
- Signals
- List of Important Signals
- Handling Signals - Example
- Sending Signals - Example
- Signals - Interrupted System Calls
- Signals - Reentrant Functions
- Signals - Reentrant Functions
- Signals - Sending In Code
- Example - implementing sleep() with alarm
- Example - “better” sleep implementation
- Demonstrating the sleepFor problem
- History of sleep and why signals are scary.
- Other uses for alarm(…)
- Memory Mapped Files
- Memory Mapped Files
- Memory Mapped Files
- Memory Mapped Files - Virtual Addresses
- Absolute Memory Addressing
- Relative Memory Addressing
- Linux / Minix - Use of mmap()
- mmap - simple example
- mmap - simple example
- Memory Mapped Files - Atomicity
- Memory Mapped Files - Bounded Buffer
- Memory Mapped Files - Bounded Buffer
- Memory Mapped Files - Bounded Buffer
- Memory Mapped Files - Bounded Buffer
- Memory Mapped Files - Bounded Buffer
- Memory Mapped Files - Bounded Buffer
- Memory Mapped Files - Fast I/O
- Memory Mapped Files - Fast I/O
- Files - IPC
- Files - Exposing Current State
- Spool Folders
- Spool Folders - Cron
- Spool Folders - CUPS
- Lock Files
- Doors
- Server Code
- Client Code
- Domain Sockets
- Domain Sockets - Example
- Domain Sockets - Example
- Domain Sockets - Example
- Virtual Memory
- What is Virtual Memory?
- Memory Management Units
- Pages and Page Tables
- Pages and Page Tables
- Pages and Page Tables
- What’s in a Page Table Entry?
- Page Table Entries
- Page Table Entries
- Two Level Page Table (thanks Wikipedia)
- MMU - Address Translation Algorithm
- Page Faults
- Page Faults - UNIX
- Page Faults - Windows
- Page Replacement / Swapping
- Page Replacement / Swapping
- Page Replacement / Swapping
- Swapper Algorithms
- Swapper Algorithms - Page Classification
- Swapper Algorithms - NRU
- Swapper Algorithms - FIFO
- Swapper Algorithms - Second Chance FIFO
- Swapper Algorithms - Clock
- Swapper Algorithms - LRU
- Swapper Algorithms - LRU/NFU
- Swapper Algorithms - LRU/NFU - Aging
- Swapper Algorithms - LRU/NFU - Aging
- Belady’s Anomoly
- Belady’s Anomoly (thanks Wikipedia)
- Belady’s Anomoly
- Modeling Page Replacement
- Modeling Page Replacement
- Modeling LRU
- Modeling LRU
- Modeling - Distance Strings
- Modeling - Distance Strings
- Modeling - Distance Strings
- Design Considerations for Paging Systems
- Working Sets
- Taking Advantage of Locality
- Costs of Paging Different Page Classes
- Costs of Paging Different Page Classes
- Costs of Paging Different Page Classes
- Local vs Global Paging
- Page Locking
- COW: Copy on Write
- COW: Copy on Write
- Backing Store
- Hibernation
- VM Performance - Hot Memory
- Modeling - Distance Strings
- Summary: Page Fault Handling
- Summary: Page Fault Handling
- Userland Memory Management
- Why Userland Memory Management?
- Why Userland Memory Management?
- Heap Management
- The Heap
- The Memory Manager
- Characteristics of Memory Allocation
- Characteristics of Memory Allocation
- Characteristics of a Good Memory Manager
- A Refresher on the Memory Hierarchy
- Program Locality
- Fragmentation
- Reducing Fragmentation of the Heap
- Best-Fit vs Next-Fit
- Best-Fit
- Managing Free Space
- Bugs and Explicit Allocators
- Debugging malloc / free
- Expanding the Heap
- Recommended Reading
- Problems with manual deallocation
- Problems with manual deallocation
- Avoiding problems with manual deallocation
- A simple Malloc / Free Implementation (Example from IBM Developer Works)
- A simple Malloc / Free Implementation
- A simple Malloc / Free Implementation
- A simple Malloc / Free Implementation
- A simple Malloc / Free Implementation
- Garbage Collection
- Garbage Collection
- Requirements for Garbage Collectors
- Goals for a Garbage Collector
- Disadvantages to Garbage Collection
- Disadvantages to Garbage Collection
- Reachability
- Reference Counting Garbage Collectors
- Pros-Cons of Reference Counting Garbage Collectors
- Mark-and-Sweep Garbage Collection
- Mark-and-Compact Garbage Collection
- Garbage Collection Costs
- Incremental Garbage Collection
- Incremental Garbage Collection
- Generational Garbage Collection
- Generational Garbage Collection
- Buyer Beware
- Storage and Devices
- Storage Devices
- IDE/ATA
- ATAPI
- SATA - Serial ATA
- Hard Disk Geometry - CHS
- Hard Disk Geometry - CHS
- Hard Disk Geometry - LBA
- Storage and Failure
- Maximizing Availability - RAID
- RAID
- RAID - 0
- RAID - 1
- RAID - 5
- RAID - 5 Parity
- RAID - 5 Parity
- RAID - 5 Parity
- RAID - 5 Parity
- RAID 5 - Parity and Recovery
- Disk Partitioning
- Disk Partitioning
- Disk Arms / Heads
- Hard Disk Geometry - CHS
- Characteristics of a Good Disk Scheduling Algorithm
- Disk Scheduling Algorithms
- FIFO
- Shortest Seek First
- Shortest Seek First
- Elevator Algorithm
- Elevator Algorithm
- Evaluation of the Elevator Algorithm
- FSCAN
- Implementing Files and Folders
- Implementing Files and Folders
- Linked-Lists
- Linked-Lists
- File Allocation Tables (FAT)
- File Allocation Tables (FAT)
- inodes
- Minix - inode
- Minix - inode
- inodes
- Block Caches
- Block Caches
- Block Caches
- Folders and Path Traversal
- Path Traversal
- Virtual Filesystems / VFS
- Virtual Filesystems / VFS
- Virtual Filesystems and Stacking
- Virtual Filesystems and User-Mode
- User-Mode Filesystems
- User-Mode Filesystems
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- Example pass-through FUSE Filesystem
- FUSE
- Storage Research at Loyola
- Filesystems Research at Loyola
- NOFS
- NOFS
- An Example NOFS Filesystem in 3 Slides
- An Example NOFS Filesystem in 3 Slides
- An Example NOFS Filesystem in 3 Slides
- NOFS - Running the Sample
- NOFS
- NOFS - Architecture - Relation to FUSE and the OS
- NOFS - Architecture - Translation of Domain Model to Files
- NOFS - Architecture - Method Execution
- RestFS
- RestFS - Service Composition
- RestFS
- RestFS - Communications
- RestFS - Google Search
- RestFS - Authentication
- RestFS - Authentication
- RestFS - Authentication
- RestFS
- RestFS - Future Directions
- Installing a Linux Virtual Machine with VMware
- VMware Fusion vs Player vs Workstation
- Step 1: Create a VM
- Step 2: Create the VM with an installer disk
- Step 3: Locate the ISO file
- Step 4: Fill out Easy-Install details
- Step 5: Customize settings
- Step 6: Processors and memory
- Step 7: Start the VM
- Step 8: Wait for Easy-Install to complete
- Step 9: Log into the new VM and Launch a terminal
- Step 10: Install course software
- Step 11: Install security updates
- Step 12: Reboot
- Installing a Windows Virtual Machine with VMware
- VMware Fusion vs Player vs Workstation
- Create a new VM
- Choose the install disk
- Fill out Easy-Install settings
- Customize VM settings
- Start the VM
- Wait for Easy-Install to complete
- Easy-Install is finished
- Install Visual Studio - attaching the disk file
- Install Visual Studio - start the installer
- Launch and sign into Visual Studio
- Install VMware Player
- Install Mercurial
- Configuring and installing software and security updates
- Reboot the VM