The Mutual Update Problem

John Hurst

Monash University

CHED Workshop, 24 Feb 2000

• This material taken from Module 6 of CSE2302 Operating Systems

• Context is Process Synchronization: How do we get two independent processes to synchronize their operations in a reliable, correct, fashion?

• Why is this difficult? To answer this question, first look at the Mutual Update Problem.

• Learning Objective:To understand the Mutual Update Problem, how it arises, and the need for atomic operations in its solution.

• Concurrent access to shared data may result in data inconsistency.

  • Example: Airline booking system

• Can characterize problem thus:

  1. Suppose we have two processes A and B that both want to update some shared variable n

  2. Each does n := n + 1, which involves reading the value of n, adding 1 to it, and then storing the result back to n. Call these operations R, I, S for read, increment, store.

  3. Process A performs operations R_A, I_A, S_A in order; while process B does R_B, I_B, S_B, also in order

  4. What happens when the speed of execution of R,I,S varies, and process A overlaps with process B?

• The problem arises because while the order of each R_A, I_A, S_A; and R_B, I_B, S_B is guaranteed by program semantics within a single process, it is not guaranteed between concurrent processes. This is called a race condition, since the actual result depends upon the interleaving of the instructions

• Consider the following scenarios, assuming n=3:

  Time Process A Process B 0 RA(=3) 1 RB(=3) 2 IA(=4) 3 IB(=4) 4 SA(=4) 5 SB(=4)

  Time Process A Process B 0 RA(=3) 1 IA(=4) 2 RB(=3) 3 SA(=4) 4 IB(=4) 5 SB(=4)

• In both cases, the value of n ends up as 4, when it should be 5

• How do we solve the Mutual Update Problem?

• Note that the correct behaviour is guaranteed if we make sure each R,I,S sequence is not overlapped with the other:

  Time Process A Process B 0 RA(=3) 1 IA(=4) 2 SA(=4) 3 RB(=4) 4 IB(=5) 5 SB(=5)

  Time Process A Process B 0 RB(=3) 1 IB(=4) 2 SB(=4) 3 RA(=4) 4 IA(=5) 5 SA(=5)

• The order of whether A goes first or B goes first does not matter, as long as they do not overlap

• The read, increment and store operations must be performed as an atomic operation.

• Sections of code that access shared variables (such as n) are known as critical regions

• No two processes can be executing in critical regions simultaneously. This ensures the operations in the critical region are performed atomically.

• This is the basis for understanding much of concurrent process synchronization, and database locking protocols (to follow).

249 accesses since 10 Oct 2008, HTML cache rendered at 20090821:0730