Details problems that are common in IPC and multiple ways we can fix them with and without busy waiting. Details: Lock Variables, Strict Alternation, Peterson Algorithm, Test and Set Lock, Sleep and Wakeup, Semaphores, Mutexes, Monitors, Barriers and Read-Copy-Update.
Interprocess Communication (IPC)
Processes need to be able to communicate to:
-Pass information which is relevant for a given multiprocess task
-Prevent trying to access exclusive resources simultaneously
-Work with an appropriate sequencing of events when there are dependencies (eg if A can
only run then B is finished, then B must be running first)
Inter Thread
Threads share memory so they can communicate through this.
However, they also need to prevent trying to access resources simultaneously, and work
with appropriate sequencing.
Race Conditions
Takes place when two or more processes are reading or writing some shared data, the final
result depends on which processes are running when. This can happen with processes as
they have some shared stored such as main memory.
Mutual Exclusion
A technique commonly used to avoid RC. It identifies the parts of the program - called critical
regions - where processes access shared resources and ensure that these processes are
not in their critical regions at the same time.
Critical Region Rules:
1. No two processes may be simultaneously inside their critical regions
2. No assumptions may be made about speeds to the number of CPUs
3. No process running outside its critical region may block other processes
4. No process should have to wait forever to enter its critical region
IPC with Busy Waiting
Lock Variable
● Var shared among processes
● When value is 0, means no process is in critical region
● Before process enters critical region, must check the lock
● Busy waiting as the while loop is waiting for the lock to change
, This has a problem as another process can read the lock before the original one has
changed its value. This allows two processes to proceed to their critical regions.
Strict Alternation
● Two processes share a variable “turn”. Program starts with it set to 0
● The process will only be allowed to enter its critical region when the variable is set to
its turn. Eg process a can only perform its critical tasks when turn is 0
● After one process has left the critical region, the variable will be set to a different
value, allowing another process to enter cr
● Guarantees that no matter the order in which the two processes are scheduled,
they’ll never be in critical region at the same time
● Only reasonable to apply strict alternation when the time a process spends waiting is
short
○ If a process is much slower than the other one, the fast one will be blocked for
a long time whilst the slow one is still in its non-critical region and cannot set
“turn” back to the other process.
○ Doesn’t comply with the rule that no process running outside its critical region
may block other processes
Peterson Algorithm
Before entering a critical region, a process indicates its interest in entering but offers the
opportunity to another one first. It calls enter_region with its own id number and might have
to wait until it is safe to enter. After leaving the region, the process calls leave_region to
notify it is done.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller amyengelbrecht. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £2.99. You're not tied to anything after your purchase.
