Concurrency Theory

by: Burt Rosenberg

at: university of miami

last-update: 30 sep 2021

6 oct 2023

Definitions

Synchronous: Events A and B can be related so that one must follow the other in time. If so, these events are synchronous. If B is determined to necessarily follow A, write: A < B.

Ways in which events can be synchronous:

(1) In a program, statements are assumed to act as if the are executed sequentially.

A:
    i = 2 ;
B:
    i = i + 1 :

In the above program A < B. We can assert B == 3 because we know the value of i at the time of event B.

(2) Between two programs, signals and messages can establish a synchronous relationship.

Program P                   Program Q
---------                   ---------
                            Q.A:                      
                                global.pass = k
                            Q.B:
                                global.signal = 1
P.A:
    while !global.signal ;
    global.signal = 0 ;
P.B: 
    j = global.pass

In this program pair, we can conclude that j, a value in program P, gets the value of k, a value in program Q, because it is passed via the global variable pass. I have written it to suggest an ordering, but the actual ordering is enforced by the shared signal variable.

By the program created ordering in P,

    (~P.A) < (~P.A) <  ... < (~P.A) <  P.A <  P.B

and in program Q,

    Q.A < Q.B

and the signalling is,

    Q.B < P.A

Which allows us to assert,

    Q.A < Q.B < P.A < P.B

This means that the value in k is passed to j through the shared global.pass

Concurrent: When there is no definite means of making events synchronous, they are concurrent.

Concurrent events might or might not happen simultaneously in time. It is the lack of assurance as to which happens first that makes the events concurrent.

Timeline: The synchronous relationships can be summarized in a timeline. In such a drawing it is important to distinguish which timeline relationships are enforced and which just happen to happen. Along a single program line, all the events are in an enforced ordering. The events of different programs might be enforced and if so, arrows show the time constraint.

         A     B
         |     |
Q:   ----+-----+--------------
                \
                 \
P:   ----+---+----+-----+-----
         |   |    |     |
         ~A  ~A   A     B

Safety: In a program that requires thread safety, that thread safety is achieved.

Liveness: That all threads will eventually proceed to completion.

Fairness: That all threads make sufficiently even progress.

Pthreads Mutex

The pthreads library provide a mutual exclusion primitive, called a mutex, that can be locked, unlocked. The mutex also supports wait/notify (a.k.a. signal) with condition variables.

The mutex has a lock and unlock primitive, between which events on a single thread the mutex is locked.

Liveness: If more than one thread requests the lock, a thread will get the lock.
Safety: If more than one thread requests the lock, only one thread will get the lock.
Fairness: A thread that requests the lock will eventually get the lock.

TIME LINES FOR MUTEX WITH NOTIFY/WAIT


EXAMPLE: The mutex is unlocked and two threads request the lock. By liveness, one 
gets the lock. By safety and fairness the other thread gets the lock after the 
first thread releases the lock.

 P1:  ~~~~~ req ~~~ contend ~~~ [---LOCKED---] ~~~~~~~
                                              \
 P2:  ~~ req ~~~~~~~~ contend ~~~~~~~~~~~~~~~~ [---LOCKED---] ~~~~~~~


EXAMPLE: wait/notify. P1 enters and eventually issues a wait. The wait immediately
and simultaneously releases the lock and sleeps P1. P2, having requested the lock, 
now gets the lock.

P2 issues a notify that prepares P1 to retake the lock. When P2 releases the lock, 
P1 simultaneously awakens and is given the lock.

 P1:  ~~req ~~~ [ ~~~ wait] ~~~~~~ waiting ~~~~~~~[ ~~ awakened ~~] ~~~~
                           \                     /
 P2:  ~~~~~ req ~~~~~~~~~~~ [ ~~~~~~~ notify ~~ ] ~~~~~~~~~~~~~

Test and set and the spin lock

The operating system provides synchronization primitives such as the mutex and semaphores. The operating system has to build these software widgets from more basic mechanisms. In the next section, the atomicity of a byte write is magnified into a mutual exclusion primitive for two processes.

However, a more practical mechanism is called the test-and-set. It is implemented in hardware and the details include issues of memory access and caching, which we exclude from this brief explanation.

The test and set is given a memory location and a value. The instruction writes the value into the location, and returns the old value of the location. Note that there are two actions,

The read of the old value
The write of the new value

The is essentially a mutex lock around these two actions. If there are two processes with a test and set at the same location, one will complete before the other.

TEST AND SET

 P1:  ~~~set(1) ~~~~ test-and-set(2) ~~~~~~~~~~~~~~~~~~   ~{ 3 } ~~~~
              \                                        \ /
 MEM: ~~~~~~~~~{ 1 } ~~~~~~contend~~~~~~~~~{ 3 } ~~~~~ { 2 } ~~~~
                                           / \
 P2:  ~~~~~~~~~~~~~~~~~~ test-and-set(3) ~    ~{ 1 }~~~~~~~~~~ 


SPIN LOCK

 P1:  ~~~~ test-and-set(1) ~~~~~~~~~~~~~~   ~{ 1 }~    ~{ 1 }~~~~~   ~{ 0 } ~~~~
                                         \ /        \ /           \ / 
 MEM: ~~{ 0 }~~~~~~ contend ~~~~~~{ 1 }~~{ 1 }~~~~~~{ 1 }~~{ 0 }~~{ 1 }~~~~~
                                  / \                     /
 P2:  ~~~~~~~~ test-and-set(1) ~~    ~{ 0 }~~~~~~~~ set(0) ~~~~~~~~~~

How this makes a mutex: In a memory location initialize with a 0. To lock test-and-set(1). If the returned value is 0, the process has locked the resource; else if it returns a 1, the resource was already locked, the the process must wait.

When the process must wait, the process can try again immediately in a loop. This is called a spin lock. While a programmed wait is more efficient for long waits, those programmed waits themselves are implemented by a spin locked resource.

Peterson's Algorithm

The Peterson Algorithm for mutual exclusion among two processes.

Process P                    Process Q
---------                    ---------

P.FS:                        Q.FS:
    p.flag = 1                  q.flag = 1
    
P.CS:                        Q.CS:
    global.coin = Q             global.coin = P
    
P.T:                         Q.T:
    while (q.flag==1 &&         while (p.flag==1 &&  
       global.coin==Q) ;           global.coin==P) ;
       
P.X:                         Q.X:
    // critical section          // critical section
    
P.FC:                        Q.FC:
   p.flag = 0                    q.flag = 0

Process P required ordering,

P.FS < P.CS < ~P.T < ~P.T < ... < ~P.T < P.T < P.X < P.FC

Process Q required ordering,

Q.FS < Q.CS < ~Q.T < ~Q.T < ... < ~Q.T < Q.T < Q.X < Q.FC

where we define,

P.T = ~(Q.FS && P.CS)  // short circuited

and likewise,

Q.T = ~(P.FS && Q.CS)  // short circuited

The safety condition is that P.X and Q.X cannot obtain simultaneously. Events can obtain simultaneously if there is a time assignment where they occur simultaneously, consistent with any required orderings.

In this case: Can we mark a time X which is before the flag clearings (P.FC and Q.FC) announce the end of the critical sections and after the test loop (P.T and Q.T) that allows entry into the critical sections?

There are cases to consider.

Assume P.X obtains because P.T was satisfied as ~Q.FS, that is, P enters the critical section because it sees that Q's flag was not set. Then we have the timeline,

         FS   CS   T                 X
         |    |    |                 |
P:   ----+----+----+-----------------+-----
                    \
                     \
Q:   -----------------+----+----+----+--
                      |    |    |    |
                      FS   CS   T    X

The red indicates that the events are not possible since Q.T must be false. 
The flag for P is set and the coin is at Q.CS.

So in this case we have safety.

Assume however, P did see Q's set flag, but it in its critical section. Then it must have seen the coin set to P. This means Q.CS followed P.CS. We have this timeline,

         FS   CS    T         X
         |    |     |         |
P:   ----+----+-----+---------+-----
               \   /
                \ /
Q:   -------+----+-------+----+--
            |    |       |    |
            FS   CS      T    X

The red indicates that the events are not possible since Q.T must be false. 
The flag for P is set and the coin is at Q.CS.

Note that the only relations that we can relay on are 
   (1) those that follow on the timeline for P or Q or
   (2) those shown with a diagonal line that are signals between timelines.

For instance, Q.FS could happen after P.CS or before P.FS. The drawing might be
deceiving as it marks Q.FS as between P.FS and P.CS. But as there are no diagonal 
lines connecting Q.PS with P's timeline. We must refrain from inferring anything 
other than Q.FS proceeds Q.CS.

So in this case, we also have safety.

We should also argue liveness (as there is the safe trivial solution of no thread is ever allowed to enter the critical section). Additionally, Peterson's solution provides fairness — in fact, in contention, the threads will alternate entry into the critical section.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 30 sep 2021
update: 6 oct 2023