Memory Management
Semaphores
• A semaphore is a synchronization tool in operating
systems, acting as an integer variable that
manages access to shared resources in concurrent
systems to prevent race conditions.
• Using atomic operations wait()/ (P) and signal() (V)
• Types:
• Binary Semaphores
• Counting Semaphores
Counting semaphores
// Down (wait/P) Operation: //Up (Signal/V) Operation:
void down(Semaphore S) void up(Semaphore S)
{ {
[Link] = [Link] - 1; [Link] = [Link] + 1;
// Decrement resource count // Increment resource count
if ([Link] < 0) { if ([Link] <= 0) {
// Block the process, add to waiting // Wake up a process from the
queue waiting queue
block(); wakeup();
} }
} }
Binary Semaphores
// Down (wait/P) Operation:
void down(Semaphore S) //Up (Signal/V) Operation:
{
while (S == 0); void up(Semaphore S)
// Busy wait: Loop until the resource is {
free S++;
// Release the resource (unlock it)
S--; }
// Acquire the resource (lock it)
}
Monitor
Monitor MonitorName {
// Shared variables
// Procedures
{
Logic
}
// Condition variables
condition x, y;
}
Reader and writer problem
semaphore wrt = 1;
void reader() // Controls access for writer
{ semaphore mutex = 1;
while(true) { // Protects readCount
wait(mutex); int readCount = 0;
// Lock to update readCount // Number of readers currently reading
readCount++;
if (readCount == 1)
wait(mutex);
wait(wrt);
// Lock to update readCount
// First reader locks writer
readCount--;
signal(mutex);
if (readCount == 0)
// Release lock to update readCount
signal(wrt);
// Last reader unlocks writer
// --- CRITICAL SECTION: signal(mutex);
Reading --- // Release lock to update readCount
}
}
void writer() {
while(true) {
wait(wrt);
// Request exclusive access
// --- CRITICAL SECTION: Writing ---
signal(wrt);
// Release access
}
}
Producer Consumer Problem
producer() consumer() {
{ while (TRUE)
while (TRUE) { {
item = produce_item(); while(count ==0);
// Generate an item item = buffer[out];
// Remove an item from the buffer
While(count == n);
buffer[in] = item; out = (out + 1) % BUFFER_SIZE;
// Add the item to the buffer // Update index for circular buffer
in = (in + 1) % BUFFER_SIZE; count = count - 1;
// Update index for circular buffer // Update the count variable
count = count + 1; consume_item(item);
// Update the count variable // Consume the item
} }
} }
Problem
// To update Count : Producer // To update Count : Consumer
1. read(Rp, m[count]) 1. read(Rc, m[count])
2. INCR Rp 2. DNCR Rc
3. Store(m[count], Rp) 3. Store(m[count], Rc)
Drawback:
Producer (I1,I2), Consumer(I1,I2), Producer(I3), Consumer(I3)
Dining Philosopher Problem
// Each chopstick is a binary // Each chopstick is a binary semaphore
void philosopher(int i) { (0=held, 1=free)
while(true) { Semaphore chopstick[5] = {1, 1, 1, 1, 1};
think();
void philosopher(int i) {
// Pick up chopsticks while(true) {
chopstick[i]; // Left think();
chopstick[(i + 1) % 5]); // Right
// Pick up chopsticks
eat(); wait(chopstick[i]); // Left
wait(chopstick[(i + 1) % 5]); // Right
// Put down chopsticks
chopstick[i]; // Left eat();
chopstick[(i + 1) % 5]; // Right
// Put down chopsticks
think(); signal(chopstick[i]); // Left
} signal(chopstick[(i + 1) % 5]);
} // Right
think();
}
}