Structure of a Program Using Lock Variables for Synchronization

MakeH() // Each MakeH process creates 1 H atom { Make-Hydro();}

MakeO() // Each MakeO process creates 1 O atom { Make-Oxy();}

Lesson 2. The Old Bridge Problem

To avoid collapse, people only allow a maximum of 3 vehicles to pass through a very old bridge at the same time. Build the ArriveBridge(int direction) and ExitBridge() procedures to control traffic on the bridge so that:

At any one time, only a maximum of 3 vehicles are allowed on the bridge.

At any one time, only a maximum of 3 vehicles are allowed to travel in the same direction on the bridge.

Each vehicle when arriving at the bridge head will call ArriveBridge(direction) to check the bridge conditions, and when it has passed the bridge, it will call ExitBridge() to signal the end.

Suppose the operation of each car is described by the following Car() process :

Car(int direction) /* direction defines the direction of movement of each car.*/{

RuntoBridge(); // Go towards the bridge ArriveBridge(direction); PassBridge(); // Cross the bridge Exit Bridge(); RunfromBridge(); // Crossed the bridge

}

Lesson 3. Crossing the River Problem

To cross the river, Microsoft employees and Linux hackers use the same river dock and must share a number of special boats. Each boat can only carry one person.

4 people at a time, and there must be 4 people to start. To ensure safety for both sides, the following rules must be followed:

a. Don't put 3 Microsoft employees and 1 Linux hacker on the same boat.

b. Conversely, don't put 3 Linux hackers and 1 Microsoft employee on the same boat.

c. All other combinations are legal.

d. The boat will only depart when there are 4 passengers.

Need to build 2 procedures HackerArrives() and EmployeeArrives() which are called by a hacker or an employee respectively when they reach the river bank to check if the conditions allow them to get on the boat? These procedures will arrange the appropriate people to be able to get on the boat. Those who have been on the boat when the boat is not full will have to wait until the 4th person gets on the boat before they can start crossing the river. (Regardless of the number of boats or whether the boat crosses the river and returns… Assume there are always boats to arrange according to valid requests)

Suppose each hacker's activity is described by the following Hacker() process :

Hacker() {

RuntoRiver(); // Go to the river bank HackerArrives(); // Check the condition to get off the boatCrossRiver(); // Start crossing the river

}

and each employee's activity is described by the following Employee() process :

Employee() {

RuntoRiver(); // Go to the river bank EmployeeArrives(); // Check the condition to get off the boatCrossRiver(); // Start crossing the river

}

Lesson 4. Bus Passenger Coordination Problem

Imagine you are responsible for controlling passengers boarding a bus at a stop.

Each bus has enough space for 10 passengers. Of these, 4 seats are reserved for wheelchair users and the remaining 6 seats are reserved for regular passengers.

Your job is to let passengers board the bus according to the regulations, when the bus is full it will depart. There may be many buses and many passengers arriving at the station at the same time, the coordination principle is to put passengers on a bus, let this bus depart and then coordinate to another bus.

Suppose your passenger scheduling for a bus is described by the GetPassengers() process ; the activities of each passenger depending on the type are described by the following WheelPassenger() and NonWheelPassenger() processes, respectively . Modify the code, using the semaphore mechanism to implement the necessary synchronization principles.

GetPassenger() {

ArriveTerminal(); // receive a vehicle at the stationOpenDoor(); // open the vehicle door, this procedure is considered to existfor (int i=0; i<4; i++) // receive passengers in wheelchairs{ ArrangeSeat();

// seat a guest

}

for (int i=0; i<6; i++) // receive normal passengers { ArrangeSeat(); // put 1 passenger in a seat

}

CloseDoor(); // close the car door, this procedure is considered to have DepartTerminal(); // let a car leave the station

}

WheelPassenger() {

ArriveTerminal(); // arrive at the stopGetOnBus(); // get on the bus

}

NonWheelPassenger() {

ArriveTerminal(); // arrive at the stopGetOnBus(); // get on the bus

}

Lesson 5. Car equipment manufacturing problem

Pontiac has two parallel operating divisions:

- Production department of 1 car frame:

MakeChassis() { // create chassis Produce_chassis();

}

- Production department of 1 wheel:

MakeTires() { // create the wheel and attach it to the chassis Produce_tire(); Put_tire_to_Chassis();

}

Synchronize activities in car production according to the following principles: 1: Produce a car frame,

2: 4 wheels are needed for a frame to be produced, then another frame can be produced...

Synchronization solutions

This lesson will introduce specific solutions to the synchronization problem. There are many solutions to implement critical region access, which are divided into two classes depending on the approach in handling the blocked process: « busy waiting » solutions and « sleep and wakeup » solutions.

Solution « busy waiting »

Software solutions

Using flag variables:

Continuity : processes share a common variable called a “lock” that is initialized to 0. A process that wants to enter the critical section must first check the value of the variable lock. If lock = 0, the process resets lock to 1 and enters the critical section. If lock is holding the value 1, the process must wait outside the critical section until lock has the value 0. Thus, a lock value of 0 means that no process is in the critical section, and lock=1 when a process is in the critical section.

while (TRUE) {

while (lock == 1); // waitlock = 1; critical-section(); lock = 0 ; Noncritical-section();

}

Figure 3.5 Structure of a program using lock variables for synchronization

Discuss: This solution may violate the first condition: two processes can be in the critical region at the same time. Suppose a process finds that lock = 0 and prepares to enter the critical region, but before it can reset lock to 1, it is paused to allow another process to execute. This second process finds that lock is still 0, enters the critical region and resets lock = 1. Then the first process is reactivated, it sets lock = 1 again and enters the critical region. Thus at that moment both processes are in the critical region.

Use rotation testing:

Approach : Here is a proposed solution for two processes. The two processes share a common variable turn (reflecting which process session is allowed to enter the critical region), which is initialized with the value 0. If turn = 0 , process A enters the critical region. If turn = 1 , process A