L9: Interprocess Communication Flashcards
4 Classical Problems
of
Synchronization
- Bounded Buffer Problem
- Readers and Writers Problem
- Dining Philosophers Problem
- Sleepy Barber Problem
Bounded Buffer
Problem
- This is a producer/consumer problem
- A “Producer” creates a product for use by the “Consumer”
- They act concurrently, synchronization is required since nothing can be consumed unless it has first been produced
- There is a finite amount of resource(memory) in which to store the products between production and consumption
Readers and Writers
Problem
- Two kinds of processes are attempting to use a common resource
- Readers and Writers
- No process may use the resource concurrently with a writer:
- Only one writer allowed at a time
- Readers cannot read while writers write
- The problem is to coordinate access for the many readers and writers, without allowing deadlock or starvation
Dining Philosophers
Problem
- 5 “Philosophers” (processes) are seated at a round table
- There are 5 “chopsticks”(resources) distributed evenly,
- one between each philosopher
- Each philosopher alternates between eating and thinking
- To eat, the philosopher must posess 2 chopsticks, those on their left and right
- The problem is to synchronize the philosopher’s acquisition of the chopsticks
- Must prevent deadlock and indefinite starvation
Sleepy Barber Problem
- A Barber shop has a fixed number of chairs in a waiting room
- It has a separate room containing the barber chair
- The barber sleeps when there are no customers
- When a customer enters:
- If all chairs are full, the customer leaves
- If the barber is busy, customer takes a chair
- else, customer wakes up the barber and sits in the barber chair
- The goal is to synchronize the actions of the barber and the customers
Semaphores:
wait( s ) operation
wait(s):
s.value– ; //decrement the semaphore value
if (s.value < 0 ){
add this process to S.L;
block this process;
}
Semaphores:
signal( S ) operation
signal( S ):
S.value++; //increment the semaphore value
if( S.value > 0 ){
S.value–;
remove a process P from S.L;
wakeup( P );
}
Using a
Semaphore
to
Synchronize Processes
- Processes use the “wait()” and “signal()” functions to coordinate usage of a resource
- A semaphore( call it “flag” in this case) is initialized to 0
- Process B calls “wait(flag)”. This causes the processes to stop until flag is set to 1
- Process A performs work, then calls “signal( flag )”, which sets flag = 1
- Process B then can perform it’s work
Using a Semphore
for
Mutual Exclusion
(code)
semaphore mutex; //initially mutex = 1
In Each Process:
do{
wait(mutex); //Wait until resource available
// Critical Section - Where work is done
signal(mutex): // “let go” of the resource
//Remainder Section - housekeeping
} while (whatever == true);
Two Types
of
Semaphores
- Counting Semaphore
- Integer value
- Can range over an unrestricted domain
- Binary Semaphore
- Binary Value, 0 or 1
- Simpler to implement
- Essentially “held” or “available”
*A counting semaphore could technically be used as a binary semaphore
Semaphores:
Access Operations
- wait()
- called “P”
- signal()
- Proceed
- called “V”
Both operations are atomic
The weird representation is because Djikstra came up with this and is Dutch.
Semaphores:
Basic Idea
Primitive structure used for:
- Dealing with n-process critical-section problems
- Various synchronization problems
They:
- Track how many instances of a resource are available
- Keep a list of processes that are waiting
Semaphore:
Values in the struct
- int value;
- A counter which indicates how many instances of the resource are currently available
- struct process *L;
- A list of processes that are currently waiting on the semaphore
Synchronization Techniques:
Test and Set Instruction:
Use in Code
If “lock” is true, a process stays in busy loop until the “lock” is false.
Then it enters the critical section, does required work.
When finished, sets “lock” to false, allowing another process to have access.
Shared Data:
boolean lock=false; //lock defaults to false
Process Pi:
do{
while( TestAndSet(&lock) ); //busy loop
//critical section
lock = false; //done with lock
//remainder section
}
Hardware Support
for
Mutual Exclusion
- Any implementation ultimately relies on mutual exclusion provided by the hardware
- All computers offer a basic form of mutual exclusion called Storage Interlock
- Storage Interlock prohibits the concurrent execution of two instructions which access the same storage location
- This is the last line of defense against concurrent access
