Day44: Master OS Fundamentals—Processes, Threads, PV, Deadlock, Memory & I/O

Operating System Core Concepts

The OS sits between applications and hardware and manages four objects: CPU (create, schedule, terminate processes/threads), memory (allocate, reclaim, map, protect), files (name, directory, access, space, permissions) and devices (allocate, buffer, driver, I/O control).

User Mode vs. Kernel Mode

Typical applications run in user mode with limited privileges and cannot access physical memory or devices directly. The kernel runs in kernel mode with full privileges, can execute privileged instructions, and performs memory, device, interrupt and process management.

System Calls

A system call forces a controlled transition from user mode to kernel mode: the application prepares arguments, executes the call, the CPU switches to kernel mode, the kernel checks parameters and performs the operation, then returns to user mode. Accessing hardware, creating processes, reading/writing files or network communication usually requires a system call.

Process and Thread

A process is a running instance of a program and the basic unit of resource allocation and protection. It owns an independent virtual address space, code, data, heap, open files, network sockets and control information.

A thread is an execution path inside a process. Threads in the same process share code, global data, heap and opened files, but each thread has its own thread ID, program counter, register state and stack. Threads are the basic unit of CPU scheduling.

Process vs. Thread Comparison

Role: process = resource container, thread = execution path.

Address space: processes are isolated, threads share the process address space.

Creation/switch cost: relatively high for processes, relatively low for threads.

Communication: processes need IPC, threads can directly access shared data (must synchronize).

Fault impact: a fault in a process is usually isolated; a severe fault in a thread can affect the whole process.

Process States

The exam‑focused three‑state model:

Ready : conditions for running are satisfied except for CPU.

Running : the thread currently occupies the CPU.

Blocked : waiting for I/O, lock, resource or other event.

Correct transitions:

Ready --scheduler grants CPU--> Running
Running --time slice expires or preempted--> Ready
Running --wait for I/O, lock, event--> Blocked
Blocked --event completes--> Ready
Running --completion or abnormal termination--> Terminated

CPU Scheduling Algorithms

FCFS – first‑come‑first‑served; simple and fair but long jobs can delay short ones.

SJF – shortest‑job‑first; reduces average waiting time but may starve long jobs and needs accurate run‑time estimates.

Priority – higher priority runs first; low‑priority jobs may starve.

Round‑Robin – each task receives a time slice in turn; fast response for time‑sharing systems, slice size affects overhead.

Multilevel Feedback Queue – several queues with different time slices and dynamic priority adjustment; balances interactive and long jobs but is complex to tune.

Starvation is not deadlock. In priority scheduling, aging (gradually increasing a waiting task’s priority) mitigates long‑term starvation.

Synchronization, Mutual Exclusion, and Critical Section

Multiple worker threads share a bounded task queue. The code that accesses the shared queue is the critical section . Mutual exclusion guarantees that at any moment only one thread can be inside the critical section. Synchronization orders the execution of threads (e.g., the consumer may run only after the producer has placed an item).

Semaphores and P/V Operations

A semaphore represents either a count of available resources or a binary condition. The classic abstract definitions are:

P(S):
  S = S - 1;
  if S < 0 then block the calling process;

V(S):
  S = S + 1;
  if S <= 0 then wake one waiting process;

Binary semaphore (initial value 1) protects a single resource; counting semaphore (initial value N) protects N identical resources (e.g., 3 GPUs → gpu = 3).

Producer‑Consumer (PV) Standard Model

For a bounded queue of capacity N three semaphores are used:

empty = N   // number of free slots
full  = 0   // number of occupied slots
mutex = 1   // queue mutex

Producer:

P(empty);   // ensure a free slot
P(mutex);   // acquire exclusive access
enqueue item;
V(mutex);   // release queue
V(full);    // signal that an item is available

Consumer:

P(full);    // ensure an item exists
P(mutex);   // acquire exclusive access
dequeue item;
V(mutex);   // release queue
V(empty);   // signal that a slot is free

empty

and full solve synchronization (ordering), while mutex solves mutual exclusion (exclusive access).

Deadlock

Four necessary conditions must hold simultaneously for deadlock:

Mutual exclusion : a resource can be used by only one thread/process at a time.

Hold and wait : a thread holds at least one resource while requesting additional ones.

No preemption : allocated resources cannot be forcibly taken away.

Circular wait : a circular chain of threads each waiting for a resource held by the next.

Three handling strategies:

Deadlock prevention – break at least one of the four conditions in advance (e.g., enforce a uniform resource‑request order such as “request disk first, then GPU”).

Deadlock avoidance – before granting a request, the system checks whether a safe sequence still exists (the Banker’s algorithm is a classic example).

Deadlock detection & recovery – allow deadlock, periodically detect wait‑for cycles, then terminate or roll back processes, preempt resources, or reschedule.

Paging and Address Translation

Logical address space and physical memory are divided into fixed‑size pages (e.g., 1 KB). A logical address consists of a page number and an offset . The page table maps a page number to a physical page‑frame number. Physical address = (frame × page‑size) + offset.

Full Example

Given:
  Logical address space = 64 KB (2^16 bytes)
  Page size = 1 KB = 400H
  Logical address = 2010H

1. Split address:
   2010H ÷ 400H = quotient 8 (page number), remainder 10H (offset)
2. Look up page table: logical page 8 → physical frame 1
3. Physical address = 1 × 400H + 10H = 0410H

Translation Lookaside Buffer (TLB)

Because each address translation would otherwise require a memory access to the page table, the TLB caches recent page‑table entries. On a TLB hit the physical frame is obtained quickly; on a miss the page table is consulted and the result is inserted into the TLB.

Segmentation and Segmented Paging

Segmentation expresses a program as logical modules (code, data, stack). Each segment has a base address and length; a segment table maps segment number → (base, length). Segmentation suffers external fragmentation because segments require contiguous physical space.

Segmented paging first divides a program into segments, then pages each segment. Logical address = segment number + page‑within‑segment + offset. This combines the logical clarity of segmentation with the allocation flexibility of paging.

Virtual Memory

Virtual memory gives each process the illusion of a large, contiguous address space that may exceed physical RAM. Only pages that are needed are resident; accessing a non‑resident page triggers a page‑fault. The OS loads the page from secondary storage, possibly evicting another page according to a replacement algorithm. Excessive paging (thrashing) dramatically reduces performance.

Page Replacement Algorithms

FIFO – evicts the page that entered memory earliest; simple but can exhibit Belady’s anomaly (more frames → more faults).

LRU – evicts the least‑recently‑used page; good performance but costly to implement.

OPT – evicts the page whose next use is farthest in the future; theoretical optimum, not implementable.

Clock – approximates LRU with a circular pointer and a use bit; lower implementation cost.

LFU – evicts the least‑frequently‑used page; may keep historically hot pages that are currently idle.

FIFO Example

Reference string: 0,0,1,1,3,1,2   Frames = 2
Step   Fault?   Frames after step   FIFO order
0      Yes      0,-                0
0      No       0,-                0
1      Yes      0,1                0→1
1      No       0,1                0→1
3      Yes      3,1   (evict 0)    1→3
1      No       3,1                1→3
2      Yes      3,2   (evict 1)    3→2
Total page faults = 4

File Allocation Methods

Contiguous allocation – file occupies consecutive disk blocks; fast sequential/random access but hard to extend and can cause external fragmentation.

Linked allocation – each block stores a pointer to the next; easy to grow, but random access is slow and pointer corruption can affect later data.

Indexed allocation – an index block stores addresses of all data blocks; supports direct access and scattered blocks, at the cost of extra index space.

With a 1 KB block size and 4‑byte block addresses, an index block holds 256 addresses. Direct pointers give 1 KB data, a single‑indirect pointer gives 256 KB, and a double‑indirect pointer gives 64 MB.

I/O Models (Application Level)

Blocking (synchronous) I/O – the calling thread waits inside the system call until the operation completes.

Non‑blocking I/O – the system call returns immediately if data is not ready; the application must poll later.

I/O multiplexing – a single thread uses select, poll or epoll to wait for readiness on many descriptors, then performs normal reads/writes on the ready ones.

Asynchronous I/O – the application submits a request and continues; the kernel completes the operation and notifies the application (e.g., via a completion event).

Model Comparison

Model          When data not ready                Who completes the follow‑up
Blocking       Thread blocks inside the call      Application after return
Non‑blocking   Call returns immediately; app polls later   Application after poll
Multiplexing   One thread blocks waiting for many descriptors   Application reads ready descriptors
Asynchronous   Submit request, continue work; kernel notifies when done   Kernel

Case Study: Regional Medical Imaging Platform

The platform illustrates all the concepts above:

Process vs. Thread : a single imaging‑service process owns its address space, files and network sockets; multiple worker threads (receive, parse, AI analysis, write) share code, heap and opened files but have private stacks and registers.

State transitions : a thread waiting for CPU is Ready; when scheduled it becomes Running; waiting for disk read or for a queue slot makes it Blocked; completion of the I/O or queue availability moves it back to Ready.

Producer‑Consumer : upload threads are producers, AI analysis threads are consumers; the bounded queue uses empty, full and mutex as described.

Deadlock mitigation : all tasks request the disk channel first and the GPU second, breaking the circular‑wait condition.

Paging : threads use virtual addresses; the page table maps logical pages to physical frames; a missing page causes a page‑fault and the OS brings the page in, possibly evicting another page using FIFO/LRU/Clock.

File I/O : large DICOM files are stored with indexed allocation (direct, single‑indirect, double‑indirect) to allow fast random access.

Network I/O : a dedicated thread monitors tens of thousands of client connections with I/O multiplexing (e.g., epoll), then reads and processes ready connections.