Operating Systems Review

Chapter 1: Operating System Goals and Components

• Primary Goal of the OS: Acts as an intermediary between the user and the hardware.

  • Main Goals:

  • Execute user programs and facilitate problem-solving.

  • Enhance system convenience.

  • Efficiently manage hardware resources.

  • Functions of OS:

  • Resource Allocator: Manages hardware resources, resolves conflicts.

  • Control Program: Manages program execution to prevent errors/misuse.

• Components of a Computer System:

  1. Hardware: CPU, memory, and I/O devices.

  2. Operating System: Controls and coordinates hardware use.

  3. Application Programs: Define resource usage (e.g. compilers, games).

  4. Users: Individuals, machines, or systems that use the computer.

Chapter 2: The Kernel

• The Kernel: Core of the OS, always running.

  • Components:

  • Other programs are either system programs (bundled with OS) or application programs.

• Traps/Exceptions: Software-generated interrupts due to:

  • Errors (e.g., division by zero).

  • User requests for OS services (system calls).

  • Key Points:

  • Handled by the OS via Interrupt Service Routines (ISRs).

  • The address of the interrupted instruction must be saved.

Chapter 3: Threads & Concurrency

• Benefits of Multithreading:

  1. Responsiveness: Keeps applications responsive when parts are blocked.

  2. Resource Sharing: Threads share memory, making communication efficient.

  3. Economy: Lower overhead for context switching and cheaper than process creation.

  4. Scalability: Threads can exploit multiple processors, running in parallel.

• User Threads vs. Kernel Threads:

  • User Threads: Managed by user-level libraries, faster, and can block other user threads.

  • Kernel Threads: Managed by the OS kernel, slower due to system calls, but allow true parallel execution.

• Blocking Behavior:

  • For user threads: If one blocks, they all block.

  • For kernel threads: Blocking of one does not affect others.

• Multithreading Models:

  1. Many-to-One: Multiple user threads to a single kernel thread.

  2. One-to-One: One user thread per kernel thread; allows true parallelism.

  3. Many-to-Many: Many user threads to many kernel threads—flexible.

  4. Two-Level Model: Variation allowing user threads to bind to specific kernel threads.

Chapter 4: CPU Scheduling

• Types of Scheduling:

  1. First-Come, First-Served (FCFS): Simple but leads to convoy effect.

  2. Shortest Job First (SJF): Minimizes average waiting time, can be preemptive (SRTF).

  3. Round Robin (RR): Time-sharing, each process gets a fixed time slice.

  4. Priority Scheduling: Allocates CPU to highest priority; may cause starvation.

  5. Multilevel Queue Scheduling: Queues based on process type/priority.

  6. Multilevel Feedback Queue: Adapts processes between queues; more flexible.

  7. Real-Time Scheduling: Manages tasks based on deadlines.

• Dispatch Latency: Time taken to stop/start processes, including context switching and jumping to the right location.

• Convoy Effect: Occurs when short processes wait behind long ones in FCFS scheduling; degrades system efficiency.

• Aging: Technique to prevent starvation by increasing the priority of waiting processes over time.

Chapter 5: Synchronization Tools

• Techniques for Critical Section Problem:

  1. Peterson’s Solution: Two processes, using flag[] and turn for mutual exclusion.

  2. Hardware Support: Atomic instructions like test-and-set and compare-and-swap.

  3. Mutex Locks: Require acquire()/release() for critical section entry/exit.

  4. Semaphores: Binary (mutual exclusion) and counting versions for resources.

  5. Monitors: High-level abstraction with automatic mutual exclusion.

• Mutual Exclusion: Only one process may execute in its critical section at a time to prevent race conditions.

• Three Requirements:

  1. Mutual Exclusion

  2. Progress

  3. Bounded Waiting

• Test-and-Set Function:

boolean test_and_set(boolean *target) { 
    boolean rv = *target;   
    *target = TRUE; 
    return rv; 
}

• Binary Semaphore: Takes values 0 and 1, behaves like a mutex lock for mutual exclusion.

• Disadvantages of Busy Waiting: Wastes CPU cycles and reduces system performance, especially with long critical sections or multiple processes.