OS

os.md

Chapter 6

I/O Bound Program

CPU Bound Program

Scheduling Criteria

• CPU Utilization
• Throughput
• Waiting Time
• Turnaround Time
• Response Time

Scheduling Algorithm

• FCFS
• SJF
• Priority
• RR
• Multilevel Queue
• Multilevel Feedback Queue

Thread Scheduling

• Process Contention Scope
• System Contention Scope

Multiprocessor Scheduling

• Asymmetric Multiprocessing
• Symmetric Multiprocessing
• Processor Affinity
  • Soft Affinity
  • Hard Affinity
• Load Balancing
  • Push Migration
  • Pull Migration
• Multicore Processor

Real-Time Scheduling

• Event Latency, Interrupt Latency, Dispatch Latency
• Proiority-based Scheduling
• Rate Monotonic Scheduling
• Earliest Deadline First Scheduling
• Proportional Share Scheduling

CFS

Chapter 7

Address Binding

• Compile Time
• Load Time
• Execution Time

Logical Address vs Physical Address

Dynamic Loading

Static Linking vs Dynamic Linking

• stubs
• shared libraries

Swapping

Contiguous Memory Allocation

• Multiple partition method
• Variable partition method
  • first-fit
  • best-fit
  • worst-fit

Fragmentation

• Internal Fragmentation
• External Fragmentation
• Compaction

Segmentation

logical address = <segment-number, offset>

entry = <segment limit, segment base>

Paging

• TLB
• ASID
• Effective memory access time
• Protection
  • R/W
  • Valid/Invalid
• PTLR
• Shared Pages

Page Table Structure

• Hierarchical Paging
• Hash Page Tables
• Inverted Page Tables

Chapter 8

Demand Paging

Copy on write

Page Replacement

• FIFO
• Belady's Anomaly
• Optimal
• LRU
  • Counters
  • Stack
• Second Chance Algorithm
• Enhanced Second Chance Algorithm
• MFU
• Page Buffering

Frame Allocation

• Equal vs Proportional
• Global vs Local Replacement
• NUMA

Thrashing

• Local Replacement
• Working Set Model
• Page Fault Rate

Allocating Kernel Memory

• Buddy System
• Slab Allocation

Chapter 9

Mass Storage Structure

• Hard disk
• Seek Time, Rotational Latency, Disk Bandwidth
• Host Controller, Device Controller
• SSD
• Magnetic Tapes

Disk Scheduling

• FCFS
• SSTF
• SCAN
• C-SCAN
• LOOK
• C-LOOK

Disk Formatting

• Physical Formatting
• Logical Formatting
• Boot Blocks
• Bad Blocks

Swap Space Management *

RAID

Stable Storage Implementation

Chapter 10

File

• Attributes
• Operations
• Open File Table
• Magic Number

Access Methods

• Sequential Access
• Direct Access

Directory Structure

• Single Level Directory
• Two Level Directory
• Tree Structured Directories
• Acyclic Graph Directories
• General Graph Directories

Chapter 11

File-System Implementation

• Boot Control Block
• Volume Control Block
• Open File Table
• VFS
  • superblock
  • inode
  • file
  • dentry

Directory Implementation

• Linked List
• Hash Table

Allocation Methods

• Contiguous Allocation
• Linked Allocation
  • Blocks
  • Clusters
  • FAT
• Indexed Allocation
  • Linked Scheme
  • Multilevel Index
  • Combined Scheme

Free Space Management

• Bit Vector
• Linked List
• Grouping
• Counting
• Space Maps

Log Structured File Systems

Chapter 12

I/O Hardware

• I/O Port Registers
  • data-in
  • data-out
  • status
  • control
• Polling
  • command register
  • busy, command-ready, error bits
• Interrupts
• DMA

Blocking vs Non Blocking I/O

Vectored I/O