Back to Subject

Unit 1 - Notes

CSE357 6 min read

Unit 1: Operating System Basics

1. Foundations of Operating Systems

1.1 Definition and Purpose

An Operating System (OS) is system software that acts as an intermediary between the computer hardware and the computer user. It manages the computer's resources and provides a convenient environment for the execution of programs.

  • Primary Goal: Convenience (User ease of use).
  • Secondary Goal: Efficiency (Optimal resource utilization).

1.2 Core Components

  1. Kernel: The core component of the OS that resides in the main memory. It has complete control over everything in the system and handles low-level tasks like disk management, memory management, and task management.
  2. Shell: An interface that allows users to interact with the kernel (e.g., Bash in Linux, PowerShell in Windows).
  3. System Calls: The programmatic interface between a running application and the OS.

1.3 Key Functions

  • Process Management: Creating, scheduling, and terminating processes.
  • Memory Management: Allocating and deallocating memory space.
  • File Management: Creating, deleting, and organizing files and directories.
  • I/O Management: Managing communication between hardware devices and applications.
  • Security & Protection: Preventing unauthorized access to data and resources.

1.4 User Mode vs. Kernel Mode

To ensure system stability, modern processors operate in two modes:

  • User Mode (Mode 1): Applications run here with restricted access to hardware. If an app crashes, the OS survives.
  • Kernel Mode (Mode 0): The OS runs here with unrestricted access to all hardware instructions.
  • Mode Switch: Occurs via a system call, interrupt, or trap.

2. Types of Operating Systems

2.1 Batch Operating Systems

  • Concept: Jobs with similar needs are batched together and executed sequentially without user interaction.
  • Mechanism: Users submit jobs (on punch cards historically) to an operator.
  • Pros: Shifts CPU time between jobs automatically.
  • Cons: Hard to debug; CPU is often idle during I/O operations.

2.2 Multiprogramming Operating Systems

  • Concept: Keeps several jobs in memory simultaneously. When one job waits for I/O, the CPU switches to another job.
  • Goal: Maximize CPU utilization.
  • Key Requirement: Requires memory management to hold multiple programs.

2.3 Time-Sharing (Multitasking) Operating Systems

  • Concept: A logical extension of multiprogramming. The CPU switches jobs so frequently that users can interact with each program while it is running.
  • Mechanism: Uses Time Quantums (slices).
  • Goal: Minimize response time.

2.4 Real-Time Operating Systems (RTOS)

Designed for applications where timing is critical.

  • Hard RTOS: Time constraints are strict. Missing a deadline results in total system failure (e.g., Airbag systems, Missile guidance).
  • Soft RTOS: Time constraints are prioritized but missing a deadline only degrades performance (e.g., Video streaming).

2.5 Distributed Operating Systems

  • Concept: Loosely coupled systems that communicate via a network.
  • Function: Several independent computers appear as a single system to the user.
  • Pros: Resource sharing, load balancing, reliability.

3. Memory Management

Memory management is the functionality of an OS which handles or manages primary memory and moves processes back and forth between main memory and disk during execution.

3.1 Logical vs. Physical Address Space

  • Logical Address (Virtual Address): Generated by the CPU.
  • Physical Address: The actual address in the memory unit (RAM).
  • MMU (Memory Management Unit): Hardware device that maps virtual to physical addresses at runtime.

3.2 Memory Allocation Techniques

  1. Contiguous Allocation:

    • Fixed Partitioning: Memory is divided into fixed-size partitions. Suffering from Internal Fragmentation (wasted space inside a partition).
    • Dynamic Partitioning: Partitions are created dynamically to fit the process size. Suffers from External Fragmentation (total free space is enough, but not contiguous).

  2. Paging (Non-contiguous):

    • Physical memory is divided into fixed-size blocks called Frames.
    • Logical memory is divided into blocks of the same size called Pages.
    • Page Table: A data structure used to map Page Numbers to Frame Numbers.
    • Solves External Fragmentation.

  3. Segmentation:

    • Memory is viewed as a collection of variable-sized segments (e.g., Code segment, Stack segment, Heap segment).
    • Logical address = <segment-number, offset>.

3.3 Virtual Memory

Allows the execution of processes that are not completely in memory.

  • Demand Paging: Pages are loaded into memory only when they are needed.
  • Page Fault: Occurs when a program tries to access a page not currently in RAM. The OS must swap it in from the disk (backing store).

3.4 Page Replacement Algorithms

When memory is full and a page fault occurs, a victim page must be swapped out.

  1. FIFO (First-In-First-Out): Replaces the oldest page. Suffers from Belady’s Anomaly (more frames can sometimes lead to more faults).
  2. LRU (Least Recently Used): Replaces the page that has not been used for the longest time. Good approximation of optimal.
  3. Optimal: Replaces the page that will not be used for the longest period of time (theoretical, requires future knowledge).

4. Processor Scheduling Algorithms

The process scheduler selects an available process for program execution on the CPU.

4.1 Process States

  • New: Process is being created.
  • Ready: Waiting to be assigned to a processor.
  • Running: Instructions are being executed.
  • Waiting (Blocked): Waiting for some event (like I/O) to occur.
  • Terminated: Finished execution.

4.2 Scheduling Criteria

  • CPU Utilization: Keep CPU as busy as possible.
  • Throughput: Number of processes completing execution per time unit.
  • Turnaround Time: Time from submission to completion.
  • Waiting Time: Total time spending in the ready queue.
  • Response Time: Time from submission to first response.

4.3 Algorithms

A. First-Come, First-Served (FCFS)

  • Logic: The process that requests the CPU first gets it first.
  • Type: Non-preemptive.
  • Issue: Convoy Effect (short processes wait behind a long process).

B. Shortest Job First (SJF)

  • Logic: Assign CPU to the process with the smallest next CPU burst.
  • Type: Can be Preemptive (Shortest Remaining Time First) or Non-preemptive.
  • Pros: Gives minimum average waiting time.
  • Cons: Requires prediction of next burst; risk of Starvation for long processes.

C. Priority Scheduling

  • Logic: CPU assigned to process with highest priority.
  • Issue: Starvation (low priority jobs never execute).
  • Solution: Aging (gradually increasing priority of waiting processes).

D. Round Robin (RR)

  • Logic: Each process gets a small unit of CPU time (Time Quantum), usually 10-100 milliseconds. After this time, the process is preempted and added to the end of the ready queue.
  • Type: Preemptive.
  • Best for: Time-sharing systems.

E. Multilevel Queue Scheduling

  • Logic: Partitions the ready queue into several separate queues (e.g., foreground interactive queue, background batch queue). Each queue has its own scheduling algorithm.

5. Process Synchronization

5.1 The Critical Section Problem

When multiple processes access and manipulate shared data concurrently, the outcome depends on the order of access (Race Condition). To prevent this, we identify Critical Sections (code segments accessing shared data).

Solution Requirements:

  1. Mutual Exclusion: If process is executing in its critical section, no other processes can be executing in their critical sections.
  2. Progress: If no process is in the critical section, only those in the "entry section" can decide who enters next (decision cannot be postponed indefinitely).
  3. Bounded Waiting: There must be a limit on the number of times other processes are allowed to enter their critical sections after a process has made a request to enter its own.

5.2 Synchronization Tools

A. Mutex Locks

A boolean variable indicating if the lock is available or not.

  • acquire(): Wait until available, then set to unavailable.
  • release(): Set to available.
  • Requires Busy Waiting (spinlock) if not implemented with sleep queues.

B. Semaphores

An integer variable accessed only through two atomic operations: wait() (or P) and signal() (or V).

  • Binary Semaphore: Value 0 or 1 (same as Mutex).
  • Counting Semaphore: Value ranges over an unrestricted domain (used for resource management).

Pseudo-code for Semaphore:

C
wait(S) {
    while (S <= 0); // busy wait
    S--;
}

signal(S) {
    S++;
}

5.3 Deadlocks

A situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

Four Necessary Conditions (Coffman Conditions):

  1. Mutual Exclusion: Resources cannot be shared.
  2. Hold and Wait: Process holding at least one resource is waiting for others.
  3. No Preemption: Resources cannot be taken away forcibly.
  4. Circular Wait: waits for , waits for ... waits for .

Deadlock Handling:

  • Prevention: Invalidate one of the 4 conditions.
  • Avoidance: OS checks allocation state to ensure circular wait never happens (e.g., Banker's Algorithm).
  • Detection & Recovery: Let deadlock occur, detect it via a resource graph, and terminate a process to break the cycle.

6. Inter-process Communication (IPC)

Processes executing concurrently may be independent or cooperating. Cooperating processes require IPC.

6.1 Why IPC?

  • Information sharing.
  • Computation speedup (parallelism).
  • Modularity.

6.2 IPC Models

A. Shared Memory

  • Mechanism: A region of memory that is shared by cooperating processes is established. Processes can then read and write data to this region.
  • Speed: Faster (memory access speed).
  • Complexity: Requires synchronization mechanisms (like semaphores) to manage concurrent access.

B. Message Passing

  • Mechanism: Communication takes place by means of exchanging messages between cooperating processes.
  • Operations: send(message) and receive(message).
  • Speed: Slower (requires Kernel intervention/System calls).
  • Benefit: Easier to implement for distributed systems; no conflicts (OS handles synchronization).

6.3 Specific IPC Mechanisms (UNIX/Linux context)

  1. Pipes:
    • Anonymous Pipe: Unidirectional, used between parent and child processes (e.g., ls | grep txt).
    • Named Pipe (FIFO): Bidirectional, exists in the filesystem, unrelated processes can communicate.
  2. Message Queues: Linked list of messages stored within the kernel.
  3. Sockets: Endpoints for communication. Can be used between processes on the same machine or different machines over a network (TCP/UDP).
Next
Unit 2