Operating Systems History Overview

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What does the Readers-Writers Problem ensure when multiple processes access shared data?

Multiple readers can access data simultaneously while writers need exclusive access. (correct)

Only one process can access shared data at a time.

Readers have priority over writers regardless of the situation.

Writers can read data while writing.

What is the main purpose of process synchronization?

To allow multiple processes to run independently without any restrictions.

To eliminate all forms of locking mechanisms in shared data access.

To increase the speed of all processes regardless of data integrity.

To ensure that multiple processes or threads can safely access shared resources. (correct)

What does paging in memory management aim to avoid?

Overloading memory by allowing unlimited allocations.

Recycle memory allocations immediately after use.

Fragmentation by dividing memory into fixed-size blocks. (correct)

Segmentation faults by keeping all memory contiguous.

Which type of scheduling allows a process to retain the CPU until it finishes execution?

Non-Preemptive Scheduling Signup and view all the answers

What is external fragmentation in memory management?

Memory gaps created when processes are allocated and then deallocated. Signup and view all the answers

What type of cache miss occurs when data is accessed for the first time?

Compulsory Miss Signup and view all the answers

Which cache replacement policy evicts the least recently used data?

Least Recently Used (LRU) Signup and view all the answers

In a write-back cache, when is the data written to the main memory?

Only when evicted from the cache Signup and view all the answers

Which operating system introduced multitasking and multi-user capabilities?

Unix Signup and view all the answers

What does turnaround time represent in process scheduling?

The duration from process arrival to completion Signup and view all the answers

What is the main condition that must hold true for a deadlock to occur?

Mutual Exclusion Signup and view all the answers

What does a cycle in a Resource Allocation Graph (RAG) indicate?

A potential or actual deadlock Signup and view all the answers

Which graph algorithm is commonly used to detect cycles in directed graphs?

Depth-First Search (DFS) Signup and view all the answers

Which scheduling algorithm can lead to starvation of lower-priority processes?

Priority Scheduling Signup and view all the answers

What is a semaphore used for in process synchronization?

To control access to a shared resource Signup and view all the answers

Which cache level is the largest and shared among CPU cores?

L3 Signup and view all the answers

What defines the First-Come, First-Served (FCFS) scheduling algorithm?

Processes are executed in the order they arrive. Signup and view all the answers

What characterizes a Directed Acyclic Graph (DAG)?

No cycles are present Signup and view all the answers

Which condition does NOT contribute to deadlock formation?

Resource Sharing Signup and view all the answers

Which recovery method for deadlock involves reallocating resources from some processes?

Resource Preemption Signup and view all the answers

What is a characteristic of real-time scheduling algorithms?

They focus on time-critical tasks. Signup and view all the answers

Study Notes

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.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Explore the evolution of operating systems from the early ENIAC and GM-NAA I/O systems to the contemporary giants like Android and iOS. This quiz covers key milestones in OS development, including significant innovations like Unix's multitasking capabilities and the rise of open-source software with Linux. Test your knowledge on how these systems manage computer hardware and software.