Operating System Fundamentals: Core Concepts & Algorithms

Posted on Jul 30, 2025 in Computers

Operating System Introduction & Types

Operating systems manage CPU, memory, storage, and I/O resources.

Types of Operating Systems

• OS-less
• Batch Processing
• Multiprogramming
• Time-sharing

Multiprogramming

Increases CPU utilization; memory and security management are crucial.

Time-sharing

Enables user interaction and provides quicker system response.

Computing Resources & OS Services

Key Operating System Services

• User Interface (CLI/GUI)
• Program Execution
• I/O Operations
• File System Manipulation
• Inter-process Communication
• Error Detection
• Resource Allocation
• Accounting
• Security

System Calls

System calls provide kernel services through APIs, ensuring portability and simplicity.

Dual-Mode Operation (User/Kernel)

The dual-mode (user/kernel) operation protects system resources and hardware integrity.

Processes

Process Definition & States

A process is a program in execution. Its common states include:

• New
• Running
• Waiting
• Ready
• Terminated

Process Control Block (PCB)

The Process Control Block (PCB) stores vital process information, such as its state, program counter, CPU registers, and scheduling information.

Context Switching

Context switching refers to the overhead incurred when the CPU switches between different processes.

Interprocess Communication (IPC)

Interprocess Communication (IPC) methods include:

• Shared Memory
• Message Passing

Threads

Threads are multiple lightweight processes that exist within a single process, significantly improving concurrency and resource utilization efficiency.

CPU Scheduling

Scheduling Objectives

The primary objectives of CPU scheduling are to:

• Maximize CPU Utilization
• Maximize Throughput
• Minimize Waiting Time
• Minimize Response Time

CPU Scheduling Algorithms

First-Come, First-Served (FCFS)

Simple to implement, but can suffer from the convoy effect.

Shortest Job First (SJF)

Considered optimal as it yields the minimal average waiting time.

Priority Scheduling

Can lead to starvation for low-priority processes; aging is a technique to mitigate this problem.

Round Robin (RR)

Provides fairness and good response time by using a time quantum.

Multilevel Queue & Multilevel Feedback Queue

These advanced scheduling algorithms support dynamic priority adjustments and aging.

Process Synchronization

Critical-Section Problem

The critical-section problem requires solutions that satisfy three conditions:

• Mutual Exclusion
• Progress
• Bounded Waiting

Solutions to Critical-Section Problem

Peterson’s Algorithm

A software-based solution for two processes.

Test-and-Set Lock

A hardware-supported solution for mutual exclusion.

Semaphores

Semaphores (using wait() and signal() operations) help avoid busy waiting by employing queues.

Classic Synchronization Problems

• Bounded-Buffer Problem
• Readers-Writers Problem
• Dining Philosophers Problem

Deadlocks

Deadlock Conditions

A deadlock can occur if all four of these conditions are met simultaneously:

• Mutual Exclusion
• Hold and Wait
• No Preemption
• Circular Wait

Handling Deadlocks

Deadlock Prevention

Achieved by ensuring that at least one of the four necessary conditions for deadlock cannot hold.

Deadlock Avoidance

Requires the system to have some a priori information about resource usage (e.g., Banker’s Algorithm, Resource-Allocation Graph Algorithm).

Deadlock Detection

Involves detecting if a deadlock has occurred (e.g., using a wait-for graph or a detection algorithm).

Deadlock Recovery

Strategies include terminating processes involved in the deadlock or resource preemption.

Main Memory Management

Address Spaces & Protection

Logical address spaces are distinct from physical address spaces. Memory protection is often achieved using base and limit registers.

Contiguous Memory Allocation

Fixed-Size Partitions

Simple to implement, but can lead to internal fragmentation.

Variable-Size Partitions

More flexible, but prone to external fragmentation, which can be resolved through compaction.

Non-Contiguous Memory Allocation

Paging

Divides logical memory into pages and physical memory into frames. Uses a page table for mapping and a TLB (Translation Lookaside Buffer) as a cache for faster lookups.

Segmentation

Provides a logical structuring of processes based on user views. Segment tables map logical addresses to physical addresses.

Practical Calculations & Examples

First-Come, First-Served (FCFS) Scheduling Example

Process Burst Times

Gantt Chart

P1    P2    P3
0     24    27    30

Average Waiting Time (AWT): (0 + 24 + 27) / 3 = 51 / 3 = 17

Shortest Job First (SJF) – Preemptive (SRTF) Example 1

Process Burst Times

Gantt Chart

P4    P1    P3    P2
0     3     9     16    24

Average Waiting Time (AWT): (0 + 3 + 9 + 16) / 4 = 28 / 4 = 7

Shortest Job First (SJF) – Preemptive (SRTF) Example 2

Process Arrival and Burst Times

Banker’s Algorithm: Safe State Check Example

Resource Allocation State

Need Matrix Calculation

Need = Max - Allocated

Address Binding in Paging Example

Page Size: 4 KB

Logical Address Format: (Page Number, Offset)

Physical Address Calculation Formula

Physical Address = (Frame Number × Page Size) + Offset

Address Binding in Segmentation Example

Segment Table

Logical Address Format: (Segment ID, Offset)

• (0, 200): 1400 + 200 = 1600
• (1, 6): 6300 + 6 = 6306
• (2, 500): Error! (Exceeds limit)
• (3, 900): 3200 + 900 = 4100

Little Man Computer (LMC) Programs

LMC Program 1: Summation/Multiplication Example

        INP
        STA NUM1
        INP
        STA NUM2
LOOP    LDA TOTAL
        ADD NUM1
        STA TOTAL
        LDA NUM2
        SUB ONE
        STA NUM2
        BRP LOOP
        LDA TOTAL
        SUB NUM1
        STA TOTAL
        OUT
        HLT
NUM1    DAT
NUM2    DAT
ONE     DAT 1
TOTAL   DAT 0

LMC Program 2: Subtraction/Counter Example

        INP
        STA X
        INP
        STA Y
LOOP    LDA X
        BRZ END
        SUB Y
        STA X
        LDA ANS
        ADD ONE
        STA ANS
        BRA LOOP
END     LDA ANS
        OUT
        HLT
X       DAT
Y       DAT
ANS     DAT 0
ONE     DAT 1

LMC Program 3: Division with Remainder Example

        LDA ZERO
        STA QUOTIENT
        INP
        STA REMAINDER
        INP
        STA DIVISOR
        BRZ ERROR
LOOP    LDA REMAINDER
        SUB DIVISOR
        BRP CONTINUE
END     LDA QUOTIENT
        OUT
        LDA REMAINDER
        OUT
        HLT
CONTINUE STA REMAINDER
        LDA QUOTIENT
        ADD ONE
        STA QUOTIENT
        BRA LOOP
ERROR   LDA BIG
        OUT
        OUT
        HLT
REMAINDER DAT
DIVISOR DAT
QUOTIENT DAT
ZERO    DAT 0
ONE     DAT 1
BIG     DAT 999 ; Placeholder for an error message value