Module 3: Process Concurrency
1. The Core of Concurrency: Interleaving & Resource Sharing
Concurrency refers to the execution of multiple processes over the same time period. The OS
must interleave their execution on a single CPU or overlap them on multiple CPUs.
● The Fundamental Problem: Because processes execute asynchronously, the exact
order of instruction execution is unpredictable (non-deterministic). When these
processes share global variables or hardware, this unpredictability leads to data
corruption.
● Race Condition: This occurs when two or more processes read and write to a shared
variable simultaneously. The final value depends entirely on which process executed its
write instruction last (the "loser" of the race overwrites the winner).
● Critical Section: This is the specific block of code within a program where shared
resources (variables, files, memory) are being accessed and modified.
2. The Critical-Section Problem & Requirements
To prevent race conditions, the OS must enforce strict rules around entering the Critical
Section. A valid solution must provide three guarantees:
1. Mutual Exclusion: (The absolute rule). If Process A is executing inside its critical section,
Process B is strictly forbidden from entering its own critical section that accesses the
same resource.
2. Progress: If the critical section is empty, and multiple processes want to enter, the
decision of who gets to enter next cannot be delayed indefinitely. The system must not
freeze.
3. Bounded Waiting: Once a process requests to enter its critical section, there must be a
strict limit on how many times other processes can "cut in line" before the requesting
process is allowed in. This prevents Starvation.
3. Synchronization Mechanisms
A. Hardware Approaches
● Interrupt Disabling: A process turns off all hardware interrupts right before entering the
critical section. Exam point: This only works on single-core processors. On multi-core
processors, disabling interrupts on Core 1 does not stop a process on Core 2 from
accessing the shared memory.
● Special Machine Instructions (Test & Set / Compare & Swap): The hardware provides a
special instruction that reads a memory location and writes to it in one single,
unbreakable (atomic) clock cycle.
○ Disadvantage (Busy Waiting): If a lock is held, the waiting process gets stuck in a
while() loop, continuously checking the lock. This is called "spin-locking" and wastes
massive amounts of CPU time.
B. Software Approaches
● Peterson’s Algorithm: A purely software-based solution for exactly two processes.
○ Mechanism: It uses two variables: a boolean array flag[2] (indicating if a process
wants to enter) and a variable turn (indicating whose turn it actually is). The turn
variable acts as the ultimate tie-breaker if both want to enter simultaneously.
4. Semaphores (The Standard OS Solution)
To solve the "busy waiting" problem of hardware locks, OS designers created Semaphores. A
semaphore S is an integer variable managed by the OS, accessed only via two atomic
operations:
● wait(S): Executed before entering the critical section. It decrements S. If S becomes
negative, the OS safely puts the process to sleep (blocks it) and puts it in the
semaphore's waiting queue. No CPU time is wasted!
● signal(S): Executed after leaving the critical section. It increments S. If S is less than or
equal to 0, the OS wakes up one of the sleeping processes from the queue so it can
enter.
5. Classical Synchronization Problems (Code & Logic)
A. Bounded-Buffer (Producer-Consumer) Problem
● The Scenario: A Producer creates data and puts it into a fixed-size buffer array. A
Consumer takes data out.
● The Constraints: The Producer must sleep if the buffer is 100% full. The Consumer must
sleep if the buffer is 100% empty. They cannot access the buffer at the exact same
microsecond.
The Code Implementation:
/* program boundedbuffer */
const int sizeofbuffer = /* buffer size */;
semaphore s=1, n=0, e=sizeofbuffer;
void producer()
{
while (true) {
produce();
semWait(e);
semWait(s);
append();
semSignal(s);
semSignal(n);
}
}
void consumer()
{
while (true) {
semWait(n);
semWait(s);
take();
semSignal(s);
semSignal(e);
consume();
}
}
void main()
{
parbegin (producer, consumer);
}
Step-by-Step Code Explanation:
● semaphore s = 1; This is the Binary Semaphore (Mutex). It acts as a lock for the buffer
array itself. Only one process can hold this lock at a time.
● semaphore n = 0; A Counting Semaphore tracking full slots (items ready to be
consumed). It starts at 0 because the buffer starts empty.
● semaphore e = sizeofbuffer; A Counting Semaphore tracking empty slots.
● Inside the Producer: The producer executes semWait(e). If e is greater than 0, it
decrements it. If e is 0 (buffer full), the Producer goes to SLEEP. It then locks the buffer
semWait(s), adds the item append(), unlocks the buffer semSignal(s), and finally signals
the consumer semSignal(n) to wake it up if it was waiting for a full slot.
● Exam Tip: Notice the Producer does semWait(e) before semWait(s). If reversed, it causes
a Deadlock! The producer would lock the buffer, realize it's full, go to sleep holding the
lock, and the consumer could never get in to empty it.
B. Readers-Writers Problem (Readers Priority)
● The Scenario: A database is shared. Many readers can read at the exact same time
safely. However, if a writer wants to write, they must have absolute, exclusive access (no
other writers, no other readers).
The Code Implementation:
/* program readersandwriters */
int readcount;
semaphore x=1, wsem=1;
void reader()
{
while (true) {
semWait (x);
readcount++;
if (readcount == 1) semWait (wsem);
semSignal (x);
READUNIT();
semWait (x);
readcount--;
if (readcount == 0) semSignal (wsem);
semSignal (x);
}
}
void writer()
{
while (true) {
semWait (wsem);
WRITEUNIT();
semSignal (wsem);
}
}
void main()
{
readcount = 0;
parbegin (reader, writer);
}
Step-by-Step Code Explanation:
● readcount: Tracks how many readers are currently inside the database.
● semaphore x = 1; A Mutex lock used only to protect the readcount variable from race
conditions when multiple readers update it simultaneously.
● semaphore wsem = 1; The main lock for the database. Writers must acquire this to write.
● The Clever Reader Logic: * The first reader to arrive (if (readcount == 1)) executes
semWait(wsem). This grabs the Writer's lock, slamming the door on any writers.
Subsequent readers can just walk right in and read concurrently during READUNIT().
○ The last reader to leave (if (readcount == 0)) executes semSignal(wsem). Because
the database is finally empty, this unlocks the database, waking up any writers
waiting at the door.
C. Dining Philosophers Problem
● The Scenario: 5 philosophers sit at a table. They alternate thinking and eating. They need
two chopsticks (the one on their left and right) to eat. This models resource allocation
and deadlock risk.
The Code Implementation:
C
// Philosopher i:
do {
wait(chopstick[i])
wait(chopstick[(i + 1) % 5])
...
eat
...
signal(chopstick[i]);
signal(chopstick[(i + 1) % 5]);
...
think
...
} while (1);
Step-by-Step Code Explanation & Deadlock Flaw:
● chopstick array: An array of 5 binary semaphores initialized to 1. A value of 1 means the
chopstick is on the table. 0 means a philosopher is holding it.
● The Flow: Philosopher 0 executes wait(chopstick[0]) to grab the left chopstick, then
wait(chopstick[1]) to grab the right. After eating, they signal both to drop them, waking up
any neighbors who were waiting.
● The Deadlock Flaw: This code mathematically guarantees a potential Deadlock. Imagine
the OS scheduler interrupts perfectly: all 5 philosophers execute wait(chopstick[i])
simultaneously. Now every philosopher is holding their left chopstick. When they attempt
to execute wait(chopstick[(i + 1) % 5]) for the right chopstick, they all find a 0. Every single
philosopher goes to sleep forever, waiting for a chopstick that will never be put down.
Solutions include restricting the table to 4 philosophers or making odd/even philosophers
grab chopsticks in a different order.
6. Deadlocks Deep Dive
A deadlock is a fatal system standstill. It ONLY happens if all four of these conditions occur
simultaneously:
1. Mutual Exclusion: Only one process can use a resource at a time.
2. Hold and Wait: A process holding at least one resource is waiting to acquire additional
resources held by others.
3. No Preemption: A resource can be released only voluntarily by the holding process.
4. Circular Wait: A closed chain of waiting processes exists (A waits for B, B waits for C, C
waits for A).
Handling Deadlocks:
● Prevention: Structurally break one of the four conditions (e.g., force processes to
request all resources at startup).
● Avoidance (Banker's Algorithm): Before granting a resource, the OS simulates the
future. It calculates: "If I give this resource away, will there be enough left to satisfy the
maximum needs of at least one process so it can finish?" If yes, the system is in a Safe
State, and the request is granted.
Module 5: File and I/O Management
1. File Organization Techniques
How data is structurally written inside the file to optimize access time and storage.
● Pile: A raw data dump. New data is just appended. Exam point: Searching a pile requires
scanning every single byte from the beginning (exhaustive search). Extremely slow.
● Sequential: Records are formatted identically and stored in order of a key field (e.g., Roll
Number). Pros: Great for bulk processing. Cons: Adding a new record in the middle
requires rewriting the file.
● Indexed Sequential: Solves the sequential problem by keeping a separate "Index" table
(like the back of a textbook). To find Record #500, you check the index to find the exact
block address, then jump straight to it.
● Direct/Hashed: Directly calculates a block address using a key field, bypassing any need
for searching.
2. Storage Tracking (Inodes vs. FCB)
The OS must keep metadata (permissions, size, dates) separate from the raw file data.
● Unix Inode: An index node containing all metadata and pointers to the disk blocks
containing the data. Crucial Exam Point: The Inode does not contain the file's name. The
directory file maps the name to the Inode number.
● MS-DOS FCB (File Control Block): Stores the metadata along with the 8-character
filename and 3-character extension.
3. File Space Allocation on Disk
How the OS maps a logical file onto physical disk blocks.
● Contiguous Allocation: The file is stored in a single, unbroken line of blocks.
○ Pros: Blazing fast sequential and direct access.
○ Cons: External Fragmentation. As files are deleted, gaps appear. A new large file
might not fit into smaller gaps, wasting disk space.
● Linked List Allocation: The file is scattered everywhere. Block 1 contains data and a
pointer to Block 2.
○ Pros: Zero external fragmentation. Every single free block can be used.
○ Cons: Random access is impossible. To read the 100th block, you must read the first
99 blocks to follow the pointers. Pointers also waste disk space.
● Indexed Allocation: The OS creates one special "Index Block" for the file. This block is an
array containing the addresses of all the scattered data blocks. To read block 50, look at
the 50th entry in the index block and jump directly there.
4. I/O Hardware Transfer Modes
How data moves from a device into the CPU's RAM.
● Memory Mapped I/O: The CPU asks the device for data, and then continuously polls
checking the device's status. Exam Point: Terribly inefficient. The CPU wastes cycles (busy
waiting) for slow mechanical I/O.
● Interrupt-Driven I/O: The CPU initiates I/O and does other work. When the device is
ready, it sends an electrical Interrupt signal. The CPU pauses, transfers the data, and
resumes its work.
● Direct Memory Access (DMA): For massive data transfers, the OS uses a DMA
controller. The CPU tells the DMA chip: "Move this data from Disk to RAM." The DMA
bypasses the CPU entirely, does the heavy lifting, and interrupts the CPU only when 100%
finished.
5. I/O Buffering
A buffer smooths out peaks in I/O demand because the CPU is millions of times faster than a
hard drive.
● Single Buffering: The OS assigns one buffer. The device fills it, and then control is handed
to the kernel to move it to user space.
● Double Buffering (Buffer Swapping): Uses two system buffers. The device fills Buffer A.
While the CPU empties Buffer A, the device immediately starts filling Buffer B, maximizing
concurrent execution.
● Circular Buffering: A queue of multiple buffers used when I/O operations are extremely
rapid.
6. Disk Scheduling Algorithms
The OS must schedule read/write requests intelligently to minimize Seek Time (the time it takes
the mechanical arm to move across tracks).
● FCFS (First Come First Serve): Services requests strictly in order. Exam Point: Fair, but
results in terrible performance due to wild arm swinging.
● SSTF (Shortest Seek Time First): The arm goes to the request physically closest to its
current position. Exam Point: Great performance, but causes Starvation for requests at
the edges of the disk.
● SCAN (Elevator Algorithm): The arm starts at one end, sweeps all the way to the other
end servicing requests, then reverses direction.
● C-SCAN (Circular SCAN): Sweeps from one end to the other. When it hits the end, it
immediately jumps back to the beginning without servicing requests on the return trip,
providing a more uniform wait time.
● LOOK / C-LOOK: Smarter versions of SCAN. The arm only travels as far as the last
request in a given direction before reversing, rather than going to the absolute physical
edge of the disk.
7. RAID (Redundant Array of Independent Disks)
● RAID 0 (Striping): Data is chopped up and spread across drives for speed. Cons: Zero
redundancy. One drive failure destroys all data.
● RAID 1 (Mirroring): Total data duplication. Safe, but expensive.
● RAID 4: Uses block-level parity stored on a dedicated parity disk. Cons: Every write
operation hits the parity disk, creating a bottleneck.
● RAID 5: Block-level distributed parity. Parity is spread equally across all drives, removing
the bottleneck. (Industry standard).
● RAID 6: Dual redundancy. Uses two distinct parity calculations, allowing the system to
survive two simultaneous disk failures.