Operating System: Definition, Components & Multitasking

• Lecture support provided by StudCee, with special mentions to Mihai David & Boyan Karakostov, dated April 2, 2025

OS Definition

• Conceptual mediator between hardware and tasks.
• It abstracts physical components.
• Provides structured space for processes to interact.
• Main function includes managing process interactions, preventing hardware conflicts.

OS Components

• Resource Allocator: Resolves conflicts between resource requests for efficiency and fairness.
• Control Program: Also known as "supervisor."
  • Manages user program execution.
  • Prevents errors and misuse.
  • Reduces I/O time via spooling/buffering.

Multiprogramming

• Allows concurrent execution of multiple programs on a single CPU.
• Enhances CPU utilization by keeping it constantly busy.
• Avoids CPU idling during I/O operations.

Multitasking

• Enables the OS to execute multiple processes concurrently.
• It allows users to perform multiple operations at once via time sharing.
• Time quantum involved is typically less than 1 second.

Multiprogramming vs. Multitasking

• Multiprogramming maximizes CPU usage.
• Multitasking handles the execution of multiple programs.

Spooling

• Leverages storage (disk/memory) as a buffer for slower I/O devices.
• Example: Sending files to disk before printing.
• Gives users the perception of dedicated access to resources.

Processes

• A program in execution.
• Types of processes:
  • Batch: Does not interact with users.
  • Real-time: Requires response from user/application.
  • Interactive: Requires user input and provides output.
• Process Control Block (PCB):
  • Stores process state, program counter, CPU registers.
  • Contains pointer to page table and scheduling info.
• Process Creation: Via System initialization, or A creation system call (e.g., fork), or User request (batch jobs), or spawned by another process
• Process Termination: Can be voluntary (normal or error exit) or involuntary (fatal error or termination by another process).

Context Switching

• CPU switches to another process when a process is preempted or blocks.
• Steps Include:
  • Save current process state in its PCB.
  • Move PCB to appropriate queue.
  • Select next process and load that PCB.
  • Restore CPU context so execution can resume.
• Overhead: CPU does no useful work during context switch.

Threads

• Lighter weight than processes which improves parallelism.
• User-Level Threads(Green Threads)
  • Managed by a thread library in user space.
  • Faster to create/switch.
  • Avoid kernel overhead.
  • If one thread blocks, all threads in the process block.
• Kernel-Level Threads
  • Supported/managed directly by the OS.
  • True concurrency on multicore; if a single blocks others can run.
  • More overhead for creation and management.
• Threading Models: Many-to-One, One-to-One, Many-to-Many.
• Thread Pool: A pre-created list of threads to handle incoming tasks.

Scheduling Basics

• Determines which process gets CPU next.
• Criteria Includes CPU Utilization, Throughput, Turnaround Time, Waiting Time, Response Time.

Scheduling Algorithms

• FCFS (First-Come, First-Served):
  • Non-preemptive.
  • Simple, but can lead to poor average turnaround time.
• SJF (Shortest Job First):
  • Minimizes average turnaround time.
  • May cause starvation for longer jobs.
• SRTF (Shortest Remaining Time First): Preemptive version of SJF, dynamically updates remaining time .
• Round Robin (RR):
  • All processes get small, fixed time quantum in turn.
  • Good for time-sharing; easy to implement.
• Priority Scheduling:
  • Higher-priority processes run first.
  • Aging can prevent low-priority process starvation.
  • SJF with aging priority = 1 / (execution time + 0.1 * wait time).
• Lottery Scheduling:
  • Probabilistic selection of processes using tickets.
  • Random draws approximate proportional resource sharing.

Race Conditions & Mutual Exclusion

• Race Condition: Multiple processes accessing shared data concurrently, where the outcome depends on execution order.
• Requirements for Correctness in order to ensure mutual exclusion (Peterson’s / general):
  • Mutual exclusion: Ensure only one process is in critical section at a time.
  • No assumptions on CPU speed/number.
  • Progress: No process outside its critical section blocks others.
  • Bounded waiting: Ensure no process waits forever.

Synchronization Mechanisms

• Peterson’s Algorithm: Classic software solution for two processes.
• TSL (Test-and-Set Lock): Hardware instruction to set a lock atomically.
• Semaphores:
  • wait() and signal() operations.
  • Can be binary (mutex) or counting.
• Monitors:
  • High-level construct with condition variables.
  • Can allow Safer, more structured synchronization.
• Message Passing: Processes communicate using send/receive.

Memory Management

• Fragmentation: Can be internal (unused space within allocated block) or external (available memory is fragmented into unusable chunks).

Memory Management Overview

• Address Binding: Can occur at compile time, load time, or run time
  • Types: Symbolic, relocatable, or absolute addresses.
• Contiguous Allocation:
  • Each process gets one contiguous block.
  • Allocation strategies: First Fit, Best Fit, Worst Fit.
  • Is subject to Fragmentation issues.

Paging

• Divides logical memory into pages and physical memory into frames.
• A page table maps pages to frames.
• Eliminates external fragmentation.
• TLB (Translation Lookaside Buffer):
  • A cache for page-table lookups.
  • If there is no TLB hit, then to access page table in memory.

Virtual Memory and Page Replacement

• Virtual Memory is managed through:
  • Demand paging: Pages are only loaded on demand.
  • Page fault triggers page load, with possible replacement.
• Replacement Algorithms:
  • FIFO: Simple, potentially suffers from Belady's Anomaly.
  • LRU: Replaces page not used for the longest time.
  • Second Chance (Clock): Tracks usage bit, prefer unreferenced, unmodified.
• Thrashing:
  • Constant paging and page-fault state.
  • Slows application-level processing;
  • Causes high paging activity and low CPU utilization, occuring when processes do not have enough frames.

Memory Allocation Algorithms

• Intended for an OS to allocate memory blocks to processes, by:
  • Managing limited physical memory efficiently.
  • Reducing fragmentation (internal & external).
  • Common strategies for algos: First Fit, Best Fit, Worst Fit.
• Best Fit:
  • Allocates smallest available which minimizes leftover space.
  • Can lead to many small, unusable gaps and requires searching the entire list of free blocks.
• Worst Fit:
  • Allocates largest available block.
  • Leaves large leftover space , creates fewer, larger holes, requiring searching the whole list.
• First Fit:
  • Allocates the first block that is big enough.
  • Faster than Best/Worst fit, may lead to scattered small holes at the beginning of memory, can have a good trade-off between speed and fragmentation.
• Compaction: Reduces external fragmentation by moving processes to make memory contiguous and consolidate free memory; it can also be time-consuming.

Direct Memory Access (DMA)

• Allows devices to directly transfer data to/from memory.
• Frees CPU from data transfer operations, improves I/O performance, used for disk drives and graphics cards.

File and Directory Concepts

• File: Abstract data type to create, write, read, delete, etc.
• Directory Structure: Organizes files. Acyclic graph directories allow users to share files/folders.
• Permissions: Owner/Group/Others (e.g., Unix style, octal), plus Locking: shared/exclusive, mandatory or advisory.

Allocation Methods

• Contiguous Allocation:
  • All file blocks are stored in consecutive sectors on disk.
  • Provides simple, good performance, with possible External fragmentation, thus is hard to grow file
• Linked Allocation:
  • Each block points to the next.
  • Easy to grow, random access is slow.
• Indexed Allocation: An index block holds pointers to file blocks allowing Fast access but with extra overhead for index block.

File System Layout & Journaling

• Boot Block:
  • Contains the bootloader.
• Superblock:
  • Stores metadata about file system (size, block counts, etc.)
• Journaling:
  • Write-ahead logging of metadata changes.
  • Fast recovery from crashes.
• Examples: FAT32, NTFS, ext4, etc.

I/O (Input/Output)

• Memory-Mapped I/O:
  • Device registers mapped into address space, and standard load/store instructions can access the hardware.
• DMA (Direct Memory Access):
  • Offloads data transfer to a DMA controller, and Allows CPU to continue while transferring data.
• Interrupts:
  • Device signals completion via interrupt, then context switch to ISR (Interrupt Service Routine), Precise vs. Imprecise interrupts

I/O Software Layers and Device Drivers

• Layers:
  • User-Level I/O routines (e.g., read, write).
  • Device-Independent OS software (Naming, protection).
  • Device drivers (Knows device registers, commands.
  • Interrupt handlers for (Handle completion).
  • Buffering improves performance or reliability. May need page locking to prevent pages from being swapped.