Understanding Core Operating System Concepts: Processes, Memory, Scheduling, and Synchronization

Operating System Fundamentals

Key OS services are process management, memory management, file management, and device management. A user‑mode process invokes kernel services via a system call, causing a mode switch to kernel mode.

Kernel Architectures

Monolithic kernels place all services in a single address space, offering high performance due to shared data. Microkernels move many services to user space, reducing kernel size but incurring overhead from frequent mode switches.

Interrupt Types

External interrupts – generated by I/O completion, timers, consoles, etc.

Exceptions – internal CPU events such as illegal opcodes or arithmetic overflow.

Traps – caused by explicit system‑call instructions.

Process Management

A process is the basic unit of resource allocation and is described by a Process Control Block (PCB). Threads are the basic unit of scheduling within a process and share the process’s resources.

Process States

Ready – waiting to be scheduled.

Running – currently executing on the CPU.

Waiting – blocked for a resource.

Only Ready↔Running transitions are bidirectional; other transitions are one‑way.

Scheduling Algorithms

Batch systems : FCFS, Shortest Job First (SJF), Shortest Remaining Time Next (SRTN).

Interactive systems : Round‑Robin (time‑slice), Priority scheduling, Multilevel feedback queue.

Real‑time systems : hard vs. soft deadlines.

Process Synchronization

Critical sections protect shared resources. Synchronization mechanisms include mutexes, semaphores (P/V operations), monitors, and condition variables.

Semaphore Example

typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // critical section
    up(&mutex);
}
void P2() {
    down(&mutex);
    // critical section
    up(&mutex);
}

Producer‑Consumer with Semaphores

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while (TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while (TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

Monitor Example (Pseudo‑Pascal)

monitor ProducerConsumer
    integer i;
    condition c;
    procedure insert();
    begin
        // ...
    end;
    procedure remove();
    begin
        // ...
    end;
end monitor;

Dining Philosophers (Deadlock‑free)

#define N 5
#define LEFT (i + N - 1) % N
#define RIGHT (i + 1) % N
#define THINKING 0
#define HUNGRY   1
#define EATING   2

typedef int semaphore;
int state[N];
semaphore mutex = 1;   // protects state[]
semaphore s[N];        // one semaphore per philosopher

void philosopher(int i) {
    while (TRUE) {
        think(i);
        take_two(i);
        eat(i);
        put_two(i);
    }
}

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    check(i);
    up(&mutex);
    down(&s[i]);   // wait until allowed to eat
}

void put_two(int i) {
    down(&mutex);
    state[i] = THINKING;
    check(LEFT);
    check(RIGHT);
    up(&mutex);
}

void check(int i) {
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

Readers‑Writers (Writer‑priority)

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex  = 1;
int count = 0;

void reader() {
    while (TRUE) {
        down(&count_mutex);
        count++;
        if (count == 1) down(&data_mutex);
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if (count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}

void writer() {
    while (TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

Inter‑Process Communication (IPC)

IPC mechanisms differ from synchronization: IPC transfers data, while synchronization orders execution.

Pipes – half‑duplex, parent‑child only ( #include <unistd.h>).

FIFOs (named pipes) – remove parent‑child restriction.

Message queues – asynchronous, typed messages.

Semaphores – counting access control.

Shared memory – fastest IPC, requires explicit synchronization.

Sockets – network‑wide communication.

Memory Management

Virtual memory expands physical memory into a larger logical address space. Each virtual address is split into a page number and offset; the MMU translates via page tables.

Page Replacement Algorithms

OPT (Optimal) – replaces the page whose next use is farthest in the future (theoretical).

LRU (Least Recently Used) – evicts the least recently accessed page; often implemented with a linked list.

NRU (Not Recently Used) – classifies pages by reference (R) and modify (M) bits and selects a random page from the lowest non‑empty class.

FIFO – evicts the oldest loaded page.

Second‑Chance – FIFO with a reference‑bit check; gives a page a second chance before eviction.

Clock – circular list implementation of Second‑Chance.

Segmentation divides the address space into variable‑size segments; segmented paging combines segmentation (protection/sharing) with paging (virtual memory).

Device Management

Disk components: platter, track, sector, head, actuator arm, spindle. Disk‑scheduling algorithms aim to minimize average seek time:

FCFS – first‑come‑first‑served.

SSTF – shortest seek time first (may cause starvation).

SCAN (elevator) – moves in one direction servicing requests, then reverses.

Linking and Loading

Compilation stages: preprocessing → compilation → assembly → linking.

Static linking resolves all symbols and produces a single executable.

Dynamic linking uses shared libraries (.so on Linux, .dll on Windows) so that multiple programs can share a single copy of library code in memory.

Deadlock

Four necessary conditions: mutual exclusion, hold‑and‑wait, no preemption, circular wait.

Detection

Detect cycles in a resource‑allocation graph (single‑resource case) or use the Banker's safety algorithm (multiple resources) by checking if a sequence of process completions exists.

Recovery

Preempt resources from selected processes.

Rollback processes to a safe checkpoint.

Terminate one or more processes.

Prevention

Break mutual exclusion (e.g., spooling).

Break hold‑and‑wait by requiring all resources up front.

Allow preemption of resources.

Impose a total ordering on resources to avoid circular wait.

Avoidance (Banker’s Algorithm)

Maintain vectors:

E – total resources.

A – available resources.

C – current allocation per process.

R – remaining need per process.

When a request arrives, simulate allocation; if the resulting state is safe (there exists an order in which all processes can finish), grant the request; otherwise, deny it.