Operating Systems
Lecture 10 Process Synchronization
Synchronization
Copyright By PowCoder代写 加微信 powcoder
Railways in the Andes Critical section problem Peterson’s algorithm
Semaphores
Lecture 10
COMP 2432 2021/2022
Cooperating Processes
Recap: a set of cooperating processes can affect or be affected by the execution of other processes in the set.
Cooperating processes need to access shared data.
Simultaneous access to shared data may result in data inconsistency.
Consider the scenario when two processes are inserting an item to a linked list.
Lecture 10
behavior. COMP 2432 2021/2022
Data inconsistency is caused by the race condition.
Maintaining data consistency requires mechanisms to
ensure orderly execution of cooperating processes.
Synchronization is the mechanism that ensures the orderly execution of cooperating processes to guarantee data consistency and correct process
Producer/Consumer Recap
A very common view point of cooperating processes is the model of a producer and a consumer.
Producer process produces information (called item) that is consumed by a consumer process.
Information (item) produced by producer must be stored up for consumer usage later (since consumer may not be running at the same speed as producer).
Producer-consumer problem is related to a problem to coordinate producer(s) and consumer(s), especially when the buffer to hold the intermediate data is not unlimited.
consumer Producer could store data into a shared array or shared queue and consumer takes it out there.
Producer may send a message containing the data to consumer for consumer to read.
Lecture 10
COMP 2432 2021/2022
Synchronization
Execution of concurrent processes
Lecture 10 COMP 2432 2021/2022
Synchronization
Need of synchronization
Lecture 10
COMP 2432 2021/2022
Synchronization
Concurrent access to shared data may make data inconsistent.
In producer-consumer problem, what would happen if a producer is producing an item when the consumer is attempting to take it at the same time?
What would happen if multiple consumers are taking out the same item?
Synchronization ensures the orderly execution of cooperating processes.
Synchronization requests processes to wait for the signal to go ahead, to avoid the race condition.
Examples include sleeping barber problem, society room problem.
Lecture 10
COMP 2432 2021/2022
Lecture 10
Synchronization in Lab 6
Parent creates n children:
Parent asks child 1 for its card.
Parent asks child 2 for its card and so on.
How can you enforce the order?
Solution 1:
Child 1 sleeps for 1 sec, child 2 sleeps for 2 sec, child 3 sleeps for 3 sec before discarding the first card and each will sleep for n sec afterwards.
Very messy, and what about communication of card info?
Solution 2:
Parent controls: ask child 1 for its card and then child 2.
All children must always listen to parent, regardless of their willingness.
All children must report to parent about their card or response.
Parent needs to keep track of cards and pass them around.
Solution 3:
Child 1 decides on a card and passes on to child 2.
Child 2 decides on a card and passes on to child 3.
Child needs to ask for a card from parent if no card can be paid.
The direction of play can be reversed.
Children have to communicate to next in a ring-like structure, plus a star with parent, like the spokes and a wheel, not a good approachC.OMP 2432 2021/2022
Race Condition
Suppose we have a car park and want to monitor the number of cars inside the car park.
Define an integer variable count, initially zero.
When a car enters the entrance, count count + 1.
When a car leaves the exit, count count – 1.
In assembly code, count count + 1 would be implemented as
register1 = count; register1 = register1 + 1; count = register1;
countcount–1wouldbeimplementedas
register2=count;register2=register2–1;count=register2;
When car1 is entering the car park (assume currently with 5 cars) and car2 is leaving the car park at around the same time. Consider this sample execution sequence:
Lecture 10
{count = 4}
COMP 2432 2021/2022
car1: execute register1 = count
car1: execute register1 = register1 + 1 car2: execute register2 = count
car2: execute register2 = register2 – 1 car1: execute count = register1
car2: execute count = register2
{register1 = 5} {register1 = 6} {register2 = 5} {register2 = 4} {count = 6}
Lecture 10
Producer/Consumer Problem
A solution to the producer/consumer problem is to use a few shared buffers.
A shared buffer can be viewed as a drawer to store money that a parent is passing to a child.
Parent puts money into an empty drawer.
Child takes money out of a filled drawer.
A simple solution is to have parent put money into a random drawer and child take money randomly out of the drawers.
Problem of livelock.
Another solution is to have parent put money starting from
the first drawer and child take money from the first drawer.
That should continue to bottom drawer and restart from top.
This is the concept of a circular queue implementation.
COMP 2432 2021/2022
Producer/Consumer Problem
Producer
while (true) do {
// produce an item and put in // nextProduced
while (count == NUM_BUF) do { };
// wait for an unused buffer
buffer[in] = nextProduced; in = (in + 1) % NUM_BUF; count = count + 1;
Consumer while (true) do {
while (count == 0) do { };
// wait for an item
nextConsumed = buffer[out]; out = (out + 1) % NUM_BUF; count = count – 1;
// consume item stored in
// nextConsumed
Circular queue implementation: in
Lecture 10 Initially, count = 0, in = 0, out = 0 COMP 2432 2021/2022
Producer/Consumer Problem
Isthissolutioncorrect?
Race condition occurs when the count is increased or decreased.
Can you show a sequence of CPU execution events that make the solution incorrect?
Now assume that we use a high quality CPU that provides an Inc instruction and a Dec instruction so that count = count + 1 and count = count – 1 can be implemented in one single instruction.
That is a better arrangement.
Race condition in the car park example will not happen.
Lecture 10
children taking money at around the same moment? We need a solution that will work in all conditions.
The key problem is that the count, in and out variables are used by more than one processes at any moment.
This is similar to the problem of concurrent insertion of items into a linked list. COMP 2432 2021/2022
Isthissolutioncorrect?
What would happen if there are two parents putting money or two
Railways in the Andes
High in the Andes mountains (Inca Empire), there are two circular railway lines.
One line is in Peru; the other is in Bolivia.
They share a common section of track where the lines cross
Lecture 10
The trouble is that the drivers of the Peruvian and Bolivian trains are both blind and deaf, so they can neither see nor hear each other.
Unfortunately, the two trains collide when they simultaneously enter the common section of track (mountain pass).
COMP 2432 2021/2022
a mountain pass on international border near Lake Titicaca.
Railways in the Andes
The drivers agreed on the following method to prevent collision.
They set up a large bowl at the entrance to the pass.
Before entering the pass, a driver must stop his train, walk over to the bowl, and check that it contains a rock.
If the bowl is empty, the driver finds a rock and drops the rock in the bowl, indicating that his train is entering the pass.
Once his train has exited the pass, he walks back to the bowl and removes his rock, indicating that the pass is no longer being used.
Lecture 10
COMP 2432 2021/2022
Finally, he walks back to the train and continues.
If a driver arriving at the pass finds a rock in the bowl, he takes a
nap and rechecks the bowl randomly until he finds it empty.
If the bowl is found empty, he drops a rock in the bowl and drives his
train into the pass.
A student from PolyU discovered a problem with the solution: a
train may be blocked forever.
A CityU student laughed and said that could not be true because
it never happened.
Unfortunately, on the mid-term day, the trains crashed.
Railways in the Andes
Following the crash, the PolyU student was asked as a consultant to ensure that no crash would occur.
She explained that the bowl was used in the wrong way.
The Bolivian driver must wait at the entry to the pass until the bowl is empty, drive through the pass and walk back to put a rock in the bowl.
The Peruvian driver must wait at the entry until the bowl contains a rock, drive through the pass and walk back to remove the rock from the bowl.
Her method prevented crashes, but …
Before this arrangement, the Peruvian train ran twice a day
and the Bolivian train ran once a day.
The Peruvians were now very unhappy with the new arrangement.
Lecture 10
COMP 2432 2021/2022
Railways in the Andes
The PolyU student was called in again and was told to prevent crashes while avoiding the other problem.
Lecture 10
COMP 2432 2021/2022
This method worked fine until the judgment day, when the two trains were simultaneously blocked at the entry when the drivers take naps.
She suggested to use two bowls, one for each driver. When a driver reaches the entry, he first drops a rock in his
bowl, then checks the other bowl to see if it is empty.
If so, he drives his train through the pass, stops and walks
back to remove his rock.
But if he finds a rock in the other bowl, he goes back to his
bowl and removes his rock.
Then he takes a nap, drops a rock in his bowl and re-checks
the other bowl, until he finds the other bowl empty.
Railways in the Andes
Can you continue with the story?
The PolyU and CityU students together suggest to use three bowls, one for each driver, plus a shared bowl to control who goes first.
When a driver reaches the entry, he first drops a rock in his bowl.
If he is from Bolivia, he drops a rock in the shared bowl.
If he is from Peru, he empties the shared bowl.
He checks the other bowl to see if it is empty and also the
If he is from Bolivia, he ensures that the shared bowl is empty.
If he is from Peru, he ensures that the shared bowl contains a rock.
If either checking step succeeds, he drives his train through the pass, stops and walks back to remove the rock in his bowl.
But if both checking steps fail, he takes a nap, and re-checks the other bowl and the shared bowl, until the checking succeeds.
Lecture 10
COMP 2432 2021/2022
shared bowl.
Lecture 10
Critical Section Problem
In the car park problem, producer/consumer problem and the Andes train problem, multiple processes or users are accessing a shared resource simultaneously.
The car park entrance/exit, the shared buffer and the common rail section are shared resources.
This shared resource can only be shared in such a way that at any moment, only one can use it and it cannot be used by another one before its current usage is completed.
This is consistent with our treatment of resource allocation when we deal with deadlocks.
Resources are used through the request / use / release cycle.
In this lecture, we call the shared resource the critical section. Its name comes from a section of shared program code that can only be executed by a process at any moment, without any sharing or intermixing.
The shared critical section is used through a similar cycle of request-to-enter-critical-section / inside-critical-section / exit-from-critical-section. COMP 2432 2021/2022
Critical Section Problem
Producer
while (true) do {
// produce an item and put in // nextProduced
while (count == NUM_BUF) do { };
// wait for an unused buffer
Consumer while (true) do {
while (count == 0) do { };
// wait for an item
nextConsumed = buffer[out]; out = (out + 1) % NUM_BUF; count = count – 1;
buffer[in] = nextProduced; in = (in + 1) % NUM_BUF; count = count + 1;
Group the buffer handling code into a critical section. Lecture 10 The problem is solved! COMP 2432 2021/2022
// consume item stored in // nextConsumed
Critical Section Problem
A solution to the critical section problem must avoid the problems in the Andes trains.
The solution is made up of two separate sections of code around the critical section: entry section and exit section.
while (true) do {
// entry section: part of the solution Critical section of the process
// exit section: part of the solution Remainder section of the process
Lecture 10
We can only make two very simple assumptions.
Each process executes at a non-zero speed.
There is no limitation on the relative speed of the processes. COMP 2432 2021/2022
Critical Section Problem
A solution should satisfy three properties. Mutual Exclusion
If process is executing in its critical section, then no other processes can be executing in their critical sections. That is, at most one process could be in CS.
Progress
If no process is executing in its critical section and there exist some processes that wish to enter their critical sections, then some of the waiting processes will eventually enter the critical section. That is, at least one process could enter CS.
Bounded Waiting
Lecture 10
and before that request is granted. That is, there is no starvation. COMP 2432 2021/2022
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
Peterson’s Algorithm
Peterson’s algorithm for two processes. Two processes share two variables.
int turn = 1; // indicate whose turn it is to enter the critical section.
boolean flag[2] = false; // indicate whether the process is ready to enter the critical section.
Process Pi: // use j to mean the other process (j = 1-i) while (true) do {
flag[i] = true;
while (flag[j] and turn == j) do { }; // j wants to enter CS
// and it is j’s turn, so i waits
< critical section >
flag[i] = false;
< remainder section > }
Lecture 10
COMP 2432 2021/2022
Peterson’s Algorithm
A better way to look at the algorithm by spelling it out more clearly.
Lecture 10
COMP 2432 2021/2022
Process P0
while (true) do {
flag[0] = true;
while (flag[1] and turn == 1) do { };
< critical section >
flag[0] = false;
Process P1
while (true) do {
flag[1] = true;
while (flag[0] and turn == 0) do { };
< critical section >
flag[1] = false;
< remainder section >
< remainder section > }}
Process Pi: // j means other process while (true) do {
1: flag[i] = true;
2: turn = j;
3: while (flag[j] and turn == j) do { }; 4: < critical section >
Peterson’s Algorithm
flag[i] = false;
< remainder section >
1: flag[0] = true;
2: turn = 1;
3: while (flag[1] and turn == 1) do {};
4: < critical section >
5: flag[0] = false;
6: < remainder section >
1: flag[1] = true;
2: turn = 0;
3: while (flag[0] and turn == 0) do {};
4: < critical section >
5: flag[1] = false;
6: < remainder section >
1: flag[1] = true;
2: turn = 0;
3: while (flag[0] and turn == 0) do {};
Lecture 10
COMP 2432 2021/2022
4: < critical section >
Process Pi: // j means other process while (true) do {
1: flag[i] = true;
2: turn = j;
3: while (flag[j] and turn == j) do { }; 4: < critical section >
Peterson’s Algorithm
flag[i] = false;
< remainder section >
1: flag[0] = true;
2: turn = 1;
3: while (flag[1] and turn == 1) do {};
4: < critical section >
4: < critical section >
5: flag[0] = false;
6: < remainder section >
1: flag[1] = true;
2: turn = 0;
3: while (flag[0] and turn == 0) do {};
3: while (flag[0] and turn == 0) do {};
3: while (flag[0] and turn == 0) do {};
4: < critical section >
5: flag[1] = false;
6: < remainder section >
Lecture 10 6: < remainder section > COMP 2432 2021/2022
Process Pi: // j means other process while (true) do {
1: flag[i] = true;
2: turn = j;
3: while (flag[j] and turn == j) do { }; 4: < critical section >
Peterson’s Algorithm
flag[i] = false;
< remainder section >
1: flag[0] = true;
2: turn = 1;
3: while (flag[1] and turn == 1) do {};
3: while (flag[1] and turn == 1) do {};
3: while (flag[1] and turn == 1) do {};
3: while (flag[1] and turn == 1) do {};
4: < critical section >
5: flag[0] = false;
Lecture 10 6: < remainder section > COMP 2432 2021/2022
1: flag[1] = true;
2: turn = 0;
3: while (flag[0] and turn == 0) do {};
4: < critical section >
4: < critical section >
5: flag[1] = false;
6: < remainder section >
Process Pi: // j means other process while (true) do {
flag[i] = false;
< remainder section >
Is there any impact if turn = 0 initially? Peterson’s Algorithm
1: flag[i] = true;
2: turn = j;
3: while (flag[j] and turn == j) do { }; 4: < critical section >
1: flag[0] = true;
2: turn = 1;
3: while (flag[1] and turn == 1) do {};
already finished while loop
4: < critical section >
5: flag[0] = false;
6: < remainder section >
1: flag[0] = true;
2: turn = 1;
3: while (flag[1] and turn == 1) do {};
3: while (flag[1] and turn == 1) do {};
1: flag[1] = true;
2: turn = 0;
3: while (flag[0] and turn == 0) do {};
4: < critical section >
5: flag[1] = false;
Lecture 10 4: < critical section > COMP 2432 2021/2022
Lecture 10
Busy Waiting Solution
Problems with common solutions to the critical section problem, including Peterson’s algorithm:
There are while-loops for processes to wait until they can enter the critical section.
This is called busy waiting: a process is busy in waiting and this uses up and wastes the precious CPU cycle.
If you are the CPU scheduler, you will not know whether a process is waiting to enter the critical section (CPU is wasted) or just running healthily in the remainder section (CPU is used).
We should provide better solutions so that any process waiting to enter critical section should release the CPU to other processes because …
The waiting process is waiting for something to happen, but that something will not happen if it continues to hold the
CPU and not allow other processes to use the CPU to make the event that it is waiting for happen. COMP 2432 2021/2022
Semaphores
We want a synchronization tool that does not require busy waiting.
Instead, the OS could suspend the process waiting to enter the critical section.
The most common tool is the semaphore.
A semaphore S is an integer variable.
It provides two standard operations: P(S) and V(S).
Originally, semaphore means flag signal (for Andes trains?)
P(S) means that the process will wait on S until S becomes positive.
while (S <= 0) do { }; // wait until S becomes positive S = S – 1;
V(S) means that S will be increased by one and the process waiting on S could proceed.
Lecture 10
S = S + 1; COMP 2432 2021/2022
Semaphores
Two types of semaphores
Binary semaphores: integer value can only be 0 or 1.
Counting semaphores: integer value can be any positive number.
Binary semaphores are easy to implement.
They are also called mutex locks (they look like locks and
they help to ensure mutual exclusion or mutex).
Providing critical section with semaphore S initialized to 1. while (true) do {
P(S); // entry section
< critical section >
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com