L04-Mutual Exclusion

Preface

  • The MUTEX problem
    • the shared memory model
    • problem definition
  • The unbounded algorithm
    • The bakery algorithm
  • The unbounded algorithm

Shared Memory Model

Processes communicate via a set of shared variables (also called shared registers), each shared variable has a type, defining a set of primitive operations (performed atomically)

image_1busp6ur1kh31rf41r7t12kl1kd66h.png-17.6kB

Several types of shared variable can be employed, e.g.

  • read/write
  • read-modify-write (RMW)
  • compare&swap (CAS)

Each register has a type, which specifies:

  • Values to be taken on by registers
  • Operations performed on the registers
  • Values to be returned by operations (if any)
  • New values of the register resulting from the operation

A configuration in the shared memory model is a vector: C =

image_1buspq3steuh1t3n1r031h7o1ufb6u.png-14kB

where q_i is a state of p_i and r_j is a value of register R.

The events in a shared memory system are:

  • computation steps taken by the processors and are denoted by the index of the processor;
  • At each computation step, the shared variable is accessed.

In asynchronous shared memory systems, an execution is admissible if each processor has an infinite number of computation steps.

Complexity measures

Obviously in shared memory systems there are no messages to measure. Instead we focus on the space complexity, the amount of shared memory needed to solve problems.

  • Number of distinct shared variables required
  • and the amount of shared space (e.g., # of bits)

Changes from the MSG model

  • Communication medium changes
    • No inbuf and outbuf state components
    • Configuration includes values for shared variables
  • Execution manner changes
    • One event type: one computation step by a process
      • pi’s state in old configuration specifies which shared variable is to be accessed and with which primitive
      • shared variable’s value in the new configuration changes according to the primitive’s semantics
      • pi’s state in the new configuration changes according to its old state and the result of the primitive

The Mutual Exclusion Problem

Each processor’s code is divided into four sections:

image_1buvcdt98c3u18sea2qpgp1funda.png-13.1kB

  • Entry (trying): the code executed in preparation for entering the critical section
  • Critical: the code to be protected from concurrent execution
  • Exit (release): the code executed on leaving the critical section
  • Remainder: the rest of the code

Each processor cycles through these sections in the order: remainder –> entry –> critical –> exit –> remainder.

An algorithm for a shared memory system solves the mutual exclusion problem with no deadlock (or no lockout) if the following holds (three properties):

  • Mutual exclusion: In every configuration of every execution, at most one processor is in the critical section.
  • No deadlock: In every admissible execution, if some processor is in the entry section in a configuration, then there is a later configuration in which some processor is in the critical section.
  • No lockout: In every admissible execution, if some processor is in the entry section in a configuration, then there is a later configuration in which that same processor is in the critical section.

Mutex progress conditions:

  • no deadlock
  • no lockout
  • bounded waiting: no lockout + while a processor is in its entry section, other processors enter the critical section no more than a certain number of times.

These three conditions are increasingly strong.

The code for the entry and exit sections is allowed to assume that:

  • no processor stays in its critical section forever
  • shared variables used in the entry and exit sections are not accessed during the critical and remainder sections

Mutual Exclusion Using Powerful Primitives

We will show that

  • one bit suffices for guaranteeing mutual exclusion with no deadlock
  • while O(logn) bits are necessary (and sufficient) for providing stronger fairness properties.

Binary Test&Set Registers

The test&set operation atomically reads and updates the variable.

image_1but75uk01ess19052u2137912u87o.png-18.8kB

There is a simple mutual exclusion algorithm with no deadlock that uses one test&set register(Algorithm 7).

image_1but7idl41nh27an18jv15541opb8i.png-28.8kB

  • One processor could always grab V (i.e., win the test&set competition) and starve the others.
  • No Lockout does not hold.
  • Thus Bounded Waiting does not hold.

Read-Modify-Write Registersz

The RMW operation read-modify-write all in one atomic operation.
Clearly, the test&set operation is a special case of rmw, where f(V) = 1 for any V.
image_1but76ho2njp1kuvp1t1ujv1fki85.png-13kB

image_1but836531d6418131m9isfn12h8v.png-48.3kB
Detailed analysis about algorithm 8 please refer to the textbook.


Mutual Exclusion Using Read/Write Registers

The Bakery Algorithm

Basic idea:

  • Tell others “I want to enter the critical section”
  • Get tickets and wait for my turn

We employ the following shared data structures:

  • Number: an array of n integers, which holds in its ith entry the number of p_i
  • Choosing: an array of n Boolean values; Choosing[i] is true while p_i is in the process of obtaining its number.

Because several processors can read Number concurrently it is possible for several procesors to obtain the same number!.

To break symmetry, we define p_i's ticket be the pair (Number[i], i) (uniqueness)(tickets之间的序比较可以使用字典序).

image_1but8u55uj361l3m1qh5em71qvc9s.png-44.6kB

Algorithm 10 provides mutual exclusion and no lockout. (proof pls refer to the textbook)

The numbers can grow without bound, unless when every processor is in the remainder section.

How to achieve MUTEX when variables have finite size.

A Bounded Mutual Exclusion Algorithm for 2 Processors

Algorithm 11 provides mututual exclusion and no deadlock for two processors p_0 and p_1. Each processor p_i has a Boolean shared variable Want[i].

  • Want[i]=1: if p_i wants to enter the critical section.

However, the algorithm gives prioirty to one of the processors and the other one can starve.

image_1butan78f14791ir1h7ot2f1ih1a9.png-54.2kB

We then convert this algorithm to one that provides no lockout as well.
To achieve no lockout, we modify the alrgorithm so that instead of always giving priority to p_0, each processor gives priority to the other processor on leaving the critical section.

  • Priority: Shared variable, contains the id of the processor that has the priority at the moment.

In the entry, wait until:

  • Case 1: the other processor has the priority (but does not want to enter the critical section)
  • Case 2: I have the priority.

    image_1butanrpuomi9ru1je1101o1pooam.png-76.4kB

A Bounded Mutual Exclusion Algorithm for n Processors (recursively use the [2, no lockout] algorithm)

To construct a solution for the general case of n processors we employ the algorithm for two processors.

  • Proceessors compete pairwise, using the two-processor algorithm described above, in a tournament tree (锦标赛树) arrangement.
  • The pairwise competitions are arranged in a complete binary tree.
  • Each processor begins at a specific leaf of the tree.
  • At each level, the winner gets to proceed to the next higher level, where it competes with the winner of the competition on the other side of the tree.
  • The processor that wins at the root enters the critical section.

image_1butapds11jguce1nt31dtp1q1qb3.png-17.7kB

  • v: node number; we associate shared variable Want^v[0], Want^v[1], and Priority^v (all initialized to 0)
  • To begin the competition for the (real) critical section, processor p_i executes Node(2^k + i/2, i mod 2)

    • note that the leaves of the tree are numbered 2^k, 2^k + 1, …, 2^(k+1) - 1 (see Fig. 4.7).
    • the processor on the left (right) side play the role of p_0 (p_1)

      image_1butapvs01k681mh31j781dti6a9bg.png-56.2kB

References

[1] Attiya, Hagit, and Jennifer Welch. Distributed computing: fundamentals, simulations, and advanced topics. Vol. 19. John Wiley & Sons, 2004.

坚持原创技术分享,您的支持将鼓励我继续创作!