Non-Blocking Algorithm - Introduction

hellwolf

Author: ZC Miao <>

Revision:

- 2008-12-04

   Add revision information.

- 2008-11-29

   First revision.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
  Non-Blocking Algorithm Introduction
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-


In computer science, non-blocking synchronization ensures that threads
competing for a shared resource do not have their execution indefinitely
postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is
guaranteed system-wide progress; wait-free if there is also guaranteed
per-thread progress[1].


This simple diagram shows more clearly the idea:

1. 
   
2.     +------------------------------+--------------------------------+
   
3.     |                              |                                |
   
4.     |      Mutual Exclusion        |  Non-Blocking                  |
   
5.     |                              |                                |
   
6.     |                              |    +-------------------------+ |
   
7.     |          |     |             |    |                         | |
   
8.     |          |  H  |             |    |   Lock-Freedom          | |
   
9.     |          |  y  |             |    |                         | |
   
10.     |          |  b  |             |    |    +------------------+ | |
    
11.     | Blocking |  r  | Busy-Waiting|    |    |                  | | |
    
12.     |          |  i  |  (Polling)  |    |    |   Wait-Freedom   | | |
    
13.     |          |  d  |             |    |    |                  | | |
    
14.     |          |  s  |             |    |    +------------------+ | |
    
15.     |          |     |             |    |                         | |
    
16.     |                              |    +-------------------------+ |
    
17.     |                              |                                |
    
18.     +------------------------------+--------------------------------+
    

复制代码

Using mutual exclusion is the most instinctive and easiest way to protect data
from corruption in concurrent multi-threaded programming, which simply creates a
critical region around the operations of data structure. It works fine most of
the situations, but in some situations, lock is just too expensive or even not
available. One example is for some ISR(Interrupt Service Routines), if it
disables the interruption, then the scheduler will not be run until they open
the interruption again, if it also waits for some resources which is hold by
some task, then it will never available because scheduler stops. Another example
is in RTOS, higher priority wait for the lower priority task to release the
resource, then it causes priority-inversion. So, non-blocking algorithms are
born to solve these problem without using mutual exclusions.

Valois published his most cited paper talking about lock-free data structure at
1995[2]. But unfortunately, there are some mistakes with the memory management
method introduced by Valois[3].

But algorithms from Valois needs special memory management, and it's just too
complicated to use. Michael and Scott published their own algorithms based on
the idea of cooperative task from Valois[4].

There's another more detailed notes on lock-free and wait-free algorithms area
from Internet[5].

==================== Footnote ====================
[1]  Non-blocking synchronization from Wikipedia
&nbsp;    http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms#Wait-freedom
[2]  J.D. Valois, Lock-Free Data Structures PhD Thesis, Rensselaer Polytechnic
&nbsp;    Institute, Department of Computer Science, 1995.
[3]  Maged M. Michael, Michael L. Scott Correction of a Memory Management Method
&nbsp;    for Lock-Free Data Structures, Department of Computer Science University of
&nbsp;    Rochester, 1995.
[4]  Maged M. Michael Michael L. Scott, Simple, Fast, and Practical Non-Blocking
&nbsp;    and Blocking Concurrent Queue Algorithms,, Department of Computer Science
&nbsp;    University of Rochester, 1995.
[5]  Some notes on lock-free and wait-free algorithms
&nbsp;    http://www.audiomulch.com/~rossb/code/lockfree