Operating Systems Synchronization - Complete Pseudocode
Reference
1. IPC Shared Memory
Shared Data Structure
#define BUFFER_SIZE 10
typedef struct {
int item;
int buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
} shared_data;
Note: Solution is correct, but can only use BUFFER_SIZE-1 elements
2. Producer-Consumer Problem
Producer Process - Shared Memory
item next_produced;
while (true) {
/* produce an item in next_produced */
while (((in + 1) % BUFFER_SIZE) == out)
; /* do nothing - buffer full */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
}
Consumer Process - Shared Memory
c
item next_consumed;
while (true) {
while (in == out)
; /* do nothing - buffer empty */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
/* consume the item in next_consumed */
}
Producer-Consumer: Message Passing
Producer:
message next_produced;
while (true) {
/* produce an item in next_produced */
send(next_produced);
}
Consumer:
message next_consumed;
while (true) {
receive(next_consumed);
/* consume the item in next_consumed */
}
3. Peterson's Solution for Critical Section
Algorithm Structure
c
while (true) {
while (turn != j);
/* critical section */
turn = j;
/* remainder section */
}
Complete Peterson's Algorithm
while (true) {
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
;
/* critical section */
flag[i] = false;
/* remainder section */
}
Requirements Satisfied:
Mutual Exclusion ✓
Progress ✓
Bounded Waiting ✓
4. Test and Set Lock
Definition
c
boolean test_and_set(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
Properties:
Executed atomically
Returns the original value of passed parameter
Sets the new value of passed parameter to true
Solution Using test_and_set()
Shared boolean variable: lock , initialized to false
do {
while (test_and_set(&lock))
; /* do nothing - busy wait */
/* critical section */
lock = false;
/* remainder section */
} while (true);
Does it solve the critical-section problem? Yes, but uses busy waiting.
5. Compare and Swap Lock
Definition
c
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
Properties:
Executed atomically
Returns the original value of passed parameter value
Sets the variable value to new_value but only if *value == expected is true
Solution using compare_and_swap
Shared integer: lock initialized to 0
while (true) {
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing - busy wait */
/* critical section */
lock = 0;
/* remainder section */
}
Does it solve the critical-section problem? Yes, but uses busy waiting.
6. Mutex Locks
Basic Structure
c
while (true) {
acquire_lock();
/* critical section */
release_lock();
/* remainder section */
}
Implementation
acquire() {
while (!available)
; /* busy wait */
available = false;
}
release() {
available = true;
}
Note: Calls to acquire() and release() must be atomic. Uses busy waiting (spinlock).
7. Semaphores
Definition
Synchronization tool that provides more sophisticated ways than Mutex locks for processes to
synchronize their activities.
Semaphore S: Integer variable
Two atomic operations:
wait() and signal()
Originally called P() and V()
wait() Operation
c
wait(S) {
while (S <= 0)
; // busy wait
S--;
}
signal() Operation
signal(S) {
S++;
}
Semaphore Implementation with No Busy Waiting
Waiting Queue: Each semaphore has an associated waiting queue
Each entry has two data items:
Value (of type integer)
Pointer to next record in the list
Two operations:
block - place the process invoking the operation on the appropriate waiting queue
wakeup - remove one of processes in the waiting queue and place it in the ready queue
Data Structure:
typedef struct {
int value;
struct process *list;
} semaphore;
wait() Implementation (No Busy Waiting)
c
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
// add this process to S->list
block();
}
}
signal() Implementation (No Busy Waiting)
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
// remove a process P from S->list
wakeup(P);
}
}
8. Monitors
Definition
A high-level abstraction that provides a convenient and effective mechanism for process
synchronization.
Key Properties:
Abstract data type with internal variables only accessible by code within the procedure
Only one process may be active within the monitor at a time
Pseudocode Syntax
c
monitor monitor-name
{
// shared variable declarations
procedure P1 (..) { ... }
procedure P2 (..) { ... }
procedure Pn (..) { ... }
initialization_code (..) { ... }
}
9. Condition Variables
Operations
Two operations are allowed on a condition variable:
[Link]():
A process that invokes the operation is suspended until [Link]()
[Link]():
Resumes one of processes (if any) that invoked [Link]()
If no [Link]() on the variable, then it has no effect on the variable
Usage Example
Consider: P₁ and P₂ that need to execute two statements S₁ and S₂, with requirement that S₁ to happen
before S₂
Setup:
Create a monitor with two procedures F₁ and F₂ that are invoked by P₁ and P₂ respectively
One condition variable "x" initialized to 0
One Boolean variable "done"
P1:
c
S1;
done = true;
[Link]();
P2:
if (done == false)
[Link]();
S2;
10. Single Resource Allocator
Description
Allocate a single resource among competing processes using priority numbers that specify the
maximum time a process plans to use the resource.
The process with the shortest time is allocated the resource first.
Basic Usage
[Link](t);
...
access the resource;
...
[Link]();
Where:
R is an instance of type ResourceAllocator
t is the maximum time a process plans to use the resource
Monitor Implementation
c
monitor ResourceAllocator
{
boolean busy;
condition x;
void acquire(int time) {
if (busy)
[Link](time);
busy = true;
}
void release() {
busy = false;
[Link]();
}
initialization_code() {
busy = false;
}
}
Key Feature: The process with shortest time is allocated the resource first.
