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
Most basic form of
Mutual Exclusion mechanism
- Storage Interlock
- Implemented on all computers
- Prevents multiple instructions from accessing the same storage location at the same time.
- Last line of defense against this, so it should not be relied on.
Synchronization Techniques:
Test and Set Instruction
Overview
- Uses “hardware locks”
- These can be as simple as a single bit boolean flag
- The “lock” is true while a process is accessing a resource
- “lock” is false when the resource is available
- A process checks the lock to see if it can proceed with accessing a resource
- Either way, the process will set the lock to true, because it is either already true, or will be true because the process will now access the resource
- When process is finished with the resource, it sets the lock to false
Definition:
Critical Resource
A resource that allows only one user(process) at a time to use it.
Multiple processes may compete for a single Critical Resource and must be synchronized.
Definition:
Critical Section
A code segment in a process that requires the use of a critical resource.
Race Condition:
Overview
- Several processes access and manipulate shared data at the same time.
- The final value of the shared data depends on which process finishes last and cannot be predicted.
- To prevent race conditions, concurrent processes must be synchronized.
Critical Section Problem:
Definition:
Mutual Exclusion
Only one process is allowed to be inside it’s critical section,
meaning it is using the critical resource,
at one time.
The Critical Section Problem
Must ensure that when one process is executing in it’s Critical Section,
NO other process is allowed to execute in THEIR Critical Section with the critical resource.
Critical-Section Problem:
Definition:
Bounded Waiting
- A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section, before the request is granted.
- Basically, the requesting process becomes “next in line”
- No process can remain inside of its critical section indefinitely
Critical-Section Problem:
Definition:
Progress
If no process is executing in its Critical Section,
then no process outside of its critical section should block other processes, indefinitely, from entering their critical section.
“Don’t lock the bathroom door on the way out”
Critical-Section Problem:
True or False:
A process should try to predict/assume the time that another process will spend in its critical section
False!
No assumption concerning relative speed of the n-processes, or the number of CPUs can be made
Critical-Section Problem:
Definition:
Deadlock
Deadlock
When two or more processes are each waiting for an event to occur, but that event can never occur.
Critical-Section Problem:
Definition:
Starvation
Processes are not deadlocked, but are waiting for events that may never occur, due to biases in resource scheduling.
The processes are indefinitely postponed.
Semaphores:
semget()
Overview
Required Libaries
Used to create a semaphore set, initializes each semaphore to 0.
int semget( key_t key, int nsems, int semflg);
- The integer returned is a semaphore ID
Required Libraries:
- sys/types
- sys/ipc
- sys/sem
- sys/stat
Semaphores:
semop()
Overview
int semop( int semid, struct sembuf *sops, int nsops);
Performs operations on semaphores: increment, decrement or test for 0
- Specific operation depends on the sops structure
- semid is the specific semaphore to be operated on
- can send multiple operations at once
Semaphore Operation,
semop() :
Fields of the sops struct
sops:
- sem_num
- sem_op
- sem_flg
Semaphore Operations:
Possible Semaphore Operations when
calling “semop()”
Depends on the sem_op field of sops structure:
- if sem_op > 0:
- semop() adds value to the semaphore
- awakens process that was waiting for the semaphore to increase
- if sem_op < 0:
- semop() decrements the semaphore, but not past 0
- if sem_op == 0, and semaphore == 0:
- semop() blocks calling process until value becomes 0
- if semop() is interrupted by a signal, returns -1 w/ error = EINTR
Semaphores:
Important Libraries
- sys/types.h
- sys/ipc.h
- sys/sem.h
- sys/stat.h
Semaphores:
Important Methods
- semget(key_t key, int nsems, int semflg);
- creates semaphore set
- initializes each element to 0
- returns semaphore ID
- semop( int semid, struct sembuf *sops, int nsops);
- Increment, decrement, or test semaphore elements for 0 value
