Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 6: Synchronization (Monitors (Two operations (x.wait() (a process…
Chapter 6: Synchronization
Critical section problem
Each process has critical section segment of code in which the process may be changing common variables, updating tables, writing files, etc. When one process in critical section, no other may be in its critical section
Could be solved easily in a single-processor environment if we could disallow interrupts to occur while a shared variable or resource is being modified.
Solution
Mutual exclusion
If process P1 is executing in its critical section,. then no other processes can be executing in their critical sections.
Progress
If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.
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 and before that request is granted
assume that each process executes at a nonzero speed
no assumption concerning relative speed of the n processes
Critical section handling
Two approaches
Preemptive
allows preemption of process when running in kernel mode
non-preemptive
runs until exits kernel mode, blocks or voluntarily yields CPU. Essentially free of race conditions in kernel mode.
Hardware support
Many systems provide hardware support for critical section code. The critical section problem could be solved easily in a single-processor environment if we could disallow interrupts to occur while a shared variable or resource is being modified.
Uni-processors could disable interrupts
currently running code would execute without preemption
too inefficient on multiprocessor systems and it is not broadly scalable
Three forms of hardware support
Memory barriers
Memory model
memory guaranteed a computer architecture makes to application programs
Two types
Strongly ordered
Where a memory modification of one processor is immediately visible to all other processors
weakly ordered
where a memory modification of one processor may not be immediately visible to all other processors
Definition
An instruction that forces any change in memory to be propagated (made visible) to all other processors
Hardware instructions
The critical section problem could be solved easily in a single-processor environment if we could disallow interrupts to occur while a shared variable or resource is being modified.
Type of instructions
Test-and-Set instruction
executed atomically
Returns the original value of passed parameter
Set the new value of passed parameter to true
Compare-and-Swap instruction
1.Executed atomically
Returns the original value of passed parameter value
Set the variable value the value of the passed parameter new_value but only if *value == expected is true. That is, the swap takes place only under this condition.
Atomic variables
provides atomic (uninterruptible) updates on basic data types such as integers and booleans.
Example
increment()
operation on the atomic variable sequence ensures sequence is incremented without interruption
increment(&sequence);
Semaphores
Definition
technique for managing concurrent processes by using the value of a simple integer variable to synchronize the progress of interacting processes. It can hold only a non-negative Integer value, shared between all the threads, with operations wait and signal
Two indivisible operations
Wait()
Decrements the value of its argument S, as soon as it would become non-negative(greater than or equal to 1)
Signal()
Increments the value of its argument S, as there is no more process blocked on the queue
Properties
It's simple and always have a non-negative Integer value.
Works with many processes
Can have many different critical sections with different semaphores.
Each critical section has unique access semaphores.
Can permit multiple processes into the critical section at once, if desirable.
Type
Binary Semaphore
For implementing mutual exclusion (Mutex)
A binary semaphore is initialized to 1 and only takes the values 0 and 1 during execution of a program
Counting Semaphores
to implement bounded concurrency.
Limitations
Priority Inversion is a big limitation of semaphores
Their use is not enforced, but is by convention only
With improper use, a process may block indefinitely. Such a situation is called Deadlock
Monitors
Definition
A high-level abstraction that provides a convenient and effective mechanism for process synchronization
Abstract data type, internal variables only accessible by code within the procedure
Only one process may be active within the monitor at a time
Two operations
x.wait()
a process that invokes the operation is suspended until x.signal()
x.signal()
resumes one of processes (if any) that invoked x.wait()
If process P invokes x.signal(), and process Q is suspended in x.wait(), what should happen next?
Options include
Signal and wait
P waits until Q either leaves the monitor or it waits for another condition
Signal and continue
Q waits until P either leaves the monitor or it waits for another condition
Classical problems of synchronization
Type
Bounded Buffer (Producer-Consumer) Problem
A finite buffer pool is used to exchange messages between producer and consumer processes.
Because the buffer pool has a maximum size, this problem is often called the Bounded buffer problem.
Solution
creating two counting semaphores "full" and "empty" to keep track of the current number of full and empty buffers respectively.
The Readers Writers Problem
readers-read the shared data
writers-change the data in addition to reading
most centred on relative priorities of readers and writers.
Dining Philosophers Problem
involves the allocation of limited resources to a group of processes in a deadlock-free and starvation-free manner
There are five philosophers sitting around a table, in which there are five chopsticks/forks kept beside them and a bowl of rice in the centre, When a philosopher wants to eat, he uses two chopsticks - one from their left and one from their right. When a philosopher wants to think, he keeps down both chopsticks at their original place