Operating Systems History Overview

OS History and Overview

• Operating Systems manage computer hardware and software resources.
• ENIAC was one of the first electronic computers developed in the 1940s.
• GM-NAA I/O was an early OS created for the IBM 709 in the 1950s.
• CTSS, developed at MIT in the 1960s, was the first time-sharing operating system.
• Unix, launched in the 1970s, introduced multitasking and multi-user capabilities, forming the basis for modern OS.
• Windows emerged in the 1980s as a graphical user interface OS targeted at general users.
• Linux, introduced in the 1990s, is an open-source OS popular in servers and embedded systems.
• Android and iOS became the dominant mobile operating systems in the 2000s.

Scheduling Algorithms

• First-Come, First-Served (FCFS) processes execute in the order of arrival.
• Shortest Job First (SJF) prioritizes processes with the shortest burst time.
• Round Robin (RR) allocates a fixed time quantum to each process in rotation.
• Priority Scheduling can lead to starvation, where lower-priority processes wait indefinitely.
• Multilevel Feedback Queue organizes multiple queues based on priority levels and burst characteristics.
• Real-Time Scheduling involves Rate-Monotonic and Earliest Deadline First (EDF) methods for time-sensitive tasks.
• Fair Share Scheduling allocates resources equally among user groups.
• Priority Inversion occurs when a lower-priority process blocks a higher-priority one, resolved through Priority Inheritance.

Deadlock

• Deadlock refers to a state where processes wait indefinitely for resources held by one another.
• Coffman Conditions outline four necessary criteria for deadlocks:
  • Mutual Exclusion: Resource held in a non-sharable mode.
  • Hold and Wait: Processes holding resources are waiting for additional resources.
  • No Preemption: Resources cannot be taken forcibly from processes.
  • Circular Wait: A circular chain of processes waiting on each other.
• Deadlock detection involves checking for cycles in a Resource Allocation Graph (RAG).
• Recovery methods include aborting processes or resource preemption to reallocate resources.
• Deadlock prevention can be computationally intensive.

Cache

• Caching reduces the time needed to access frequently used data.
• Cache levels vary by speed and size:
  • L1 is the fastest but smallest.
  • L2 is larger and slower than L1.
  • L3 is shared among CPU cores and the largest but slowest.
• Cache associativity types include:
  • Direct-Mapped,
  • Fully Associative,
  • Set-Associative.
• Cache misses occur in three forms:
  • Compulsory Miss: First-time data access.
  • Capacity Miss: Cache lacks space for all needed data.
  • Conflict Miss: Data evicted due to associativity rules.
• Least Recently Used (LRU) is a common policy for cache replacement.
• Cache coherence in multi-core systems employs protocols like MSEI.
• Write-Back caches write data to cache first and to memory later, whereas Write-Through ensures simultaneous writing to both.

Time Concepts in Scheduling

• Arrival Time: When a process is added to the ready queue.
• Burst Time: Total CPU time required for a single process.
• Completion Time: When a process execution finishes.
• Turnaround Time: The total time from arrival to completion.
• Waiting Time: Time a process waits in the ready queue.
• Response Time: Time taken from arrival until the first response, particularly important for interactive systems.
• CPU Utilization: Percentage of time the CPU is actively processing tasks.
• Throughput: Number of processes completed within a specified time frame.
• Context Switch: Overhead incurred when switching between processes.

Graphs (Vertices and Edges)

• Vertices represent entities such as processes, resources, or data points.
• Edges are connections between vertices, indicating relationships or interactions; they may be directed or undirected, sometimes weighted.
• A Resource Allocation Graph (RAG) assists in detecting deadlocks, with cycles indicating potential deadlocks.
• Weighted Directed Graphs utilize edge weights for algorithms like Dijkstra's for shortest paths.
• Directed Acyclic Graphs (DAG) are employed for scheduling tasks without cycles.
• Depth-First Search (DFS) is useful for cycle detection in graphs.
• Topological Sorting in a DAG helps determine task execution order.
• Multigraphs allow for multiple edges connecting the same pair of vertices.

Process Synchronization

• Race Condition: Unpredictable outcomes from unsynchronized access to shared data.
• Semaphore: A synchronization tool that regulates access to shared resources through a counter.
• Monitors: High-level constructs providing synchronized access to resources.
• Critical Section Problem: Ensures exclusive access for one process in critical sections.
• Readers-Writers Problem: Allows multiple readers access but grants exclusive access to writers.
• Spinlocks allow a process to wait (or spin) while trying to acquire a lock.
• Barriers ensure that all processes reach a sync point before continuing.
• Effective process synchronization prevents conflicts and data corruption.

Memory Management

• Paging divides memory into equal-sized blocks, reducing fragmentation issues.
• Segmentation organizes memory into logical units like functions or arrays.
• Virtual Memory employs disk space to extend perceived memory capacity.
• Memory Protection restricts access among processes, safeguarding data integrity.
• Fragmentation types include:
  • Internal Fragmentation: Wasted space within allocated blocks.
  • External Fragmentation: Unallocated gaps between allocated blocks post-deallocation.

Additional Concepts

• Preemptive Scheduling allows the CPU to interrupt processes before completion.
• Non-Preemptive Scheduling mandates that processes keep the CPU until they finish.
• Throughput measures the number of processes finalized in a set timeframe.