Operating Systems History Overview

OS History and Overview

• Operating systems (OS) manage computer hardware and software resources.
• ENIAC was an early computer developed in the 1940s.
• GM-NAA I/O was the first OS for the IBM 709 in the 1950s.
• CTSS, developed at MIT in the 1960s, was the first time-sharing OS.
• Unix emerged in the 1970s, introducing multitasking and multi-user capabilities.
• Windows, released in the 1980s, provided a GUI-based OS for general users.
• Linux, launched in the 1990s, is an open-source OS popular in servers and embedded systems.
• Android and iOS, both released in the 2000s, dominate the mobile operating system market.

Scheduling Algorithms

• First-Come, First-Served (FCFS) executes processes in the order they arrive.
• Shortest Job First (SJF) prioritizes processes with the shortest burst time.
• Round Robin (RR) allocates a fixed time quantum for each process.
• Priority Scheduling can lead to starvation of lower-priority processes.
• Multilevel Feedback Queue uses multiple queues to balance long and short processes.
• Real-Time Scheduling techniques include Rate-Monotonic and Earliest Deadline First (EDF).
• Fair Share Scheduling distributes resources equally among user groups.
• Priority Inversion occurs when a lower-priority process holds a resource for a higher-priority one; resolved by Priority Inheritance.

Deadlock

• Deadlock occurs when processes wait indefinitely for resources held by each other.
• Coffman Conditions for deadlock include:
  • Mutual Exclusion: At least one resource is held non-sharably.
  • Hold and Wait: A process waits for additional resources while holding some.
  • No Preemption: Resources cannot be forcibly removed from a process.
  • Circular Wait: Processes form a chain waiting on each other.
• Deadlock detection involves checking for cycles in a Resource Allocation Graph (RAG).
• Recovery methods include aborting processes or preempting resources.
• Preventing deadlocks can be computationally expensive.

Cache

• Purpose of cache: Reduce access time to frequently used data.
• Cache levels:
  • L1: Smallest, closest, fastest.
  • L2: Larger, slower than L1.
  • L3: Shared among CPU cores, largest, and slowest.
• Cache Associativity types include Direct-Mapped, Fully Associative, and Set-Associative.
• Cache miss types:
  • Compulsory Miss: Data accessed for the first time.
  • Capacity Miss: Cache cannot accommodate all data.
  • Conflict Miss: Eviction occurs due to associativity rules.
• Replacement policies: Least Recently Used (LRU), First-In First-Out (FIFO), and Least Frequently Used (LFU).
• Cache coherence in multi-core systems is maintained using protocols like MSEI.
• Write policies: Write-Back (caches first, writes later) vs. Write-Through (caches and writes simultaneously).

Time Concepts in Scheduling

• Arrival Time: Moment a process enters the ready queue.
• Burst Time: Total CPU time needed for process execution.
• Completion Time: When a process finishes execution.
• Turnaround Time: Total time from arrival to completion.
• Waiting Time: Duration spent in the ready queue.
• Response Time: Time until the first response is received.
• CPU Utilization: Percentage of CPU active time.
• Throughput: Count of processes completed per time unit.
• Context Switch: Overhead from switching between processes.

Graphs (Vertices and Edges)

• Vertices (nodes) represent entities or points in a graph, like processes or resources.
• Edges (arcs) are connections between vertices, signifying relationships.
• Edges can be directed (one-way) or undirected (two-way) and may have weights.
• Resource Allocation Graph (RAG) is used for deadlock detection, showing processes and resources.
• Cycles in RAG indicate potential deadlocks.
• Weighted Directed Graphs apply costs in shortest path calculations, such as Dijkstra's Algorithm.
• Directed Acyclic Graph (DAG) is used for scheduling tasks; it has no cycles.
• Depth-First Search (DFS) detects cycles in graphs.
• Topological Sorting determines the order of tasks in a DAG.
• Multigraphs allow multiple edges between the same vertices.

Process Synchronization

• Race Condition occurs when shared data is accessed unsynchronized, leading to unpredictable outcomes.
• Semaphore: A counter controlling access to shared resources.
• Monitors encapsulate shared resources for high-level synchronization.
• Critical Section Problem ensures mutual exclusion in shared access.
• Readers-Writers Problem allows multiple readers but mandates exclusive access for writers.
• Spinlocks: Processes wait while spinning for a lock, inefficient for long waits.
• Barriers synchronize processes to ensure they reach specific milestones concurrently.
• Process synchronization prevents data corruption by controlling process execution order using semaphores and locks.

Memory Management

• Paging divides memory into fixed blocks, mitigating fragmentation.
• Segmentation organizes memory into logical segments (e.g., functions, arrays).
• Virtual Memory uses disk space to create an illusion of larger memory.
• Memory Protection ensures one process cannot access another's memory.
• Fragmentation types include:
  • Internal Fragmentation: Wasted space within allocated memory blocks.
  • External Fragmentation: Unused gaps between allocated memory sections.

Additional Concepts

• Preemptive Scheduling allows the CPU to be taken from processes before completion.
• Non-Preemptive Scheduling means a process holds the CPU until it finishes.
• Throughput quantifies total process completions in a specified timeframe.