next up previous contents
Next: Non-Blocking Synchronization Implementation Up: The Synergy Between Non-blocking Previous: Data Structures that

Minimizing the Window of Inconsistency

 

The Cache Kernel was also structured to minimize the window in which a data structure was inconsistent. This provides temporal locality to a critical section. Again, we use familiar techniques. The basic pattern is to read all the values, compute the new values to be written, and then write these new values all at once after verifying that the values read have not changed. Since a structure is generally inconsistent from the time of the first write to the point that the last write completes, removing the computation from this phase minimizes the window of inconsistency. To minimize the cost of verifying that the read values have not changed, we use a version number that covers the data structure and is updated whenever the data structure changes. The use of a version number also avoids keeping track of the actual location read as part of the operation.

The window of inconsistency is also minimized by structuring to minimize physical contention as part of data structure access.

Physical contention increases the time for a processor to perform an operation because it increases the effective memory access time.

These techniques allow efficient non-blocking synchronization. In particular, an update typically consists of a DCAS operation that updates the version number plus one other location, with the version number ensuring that the data structure has not been changed by another concurrent update. That is, the window of inconsistency is reduced to the execution of the DCAS operation itself.

These techniques have other benefits as well. In particular, the reduced window of inconsistency reduces the probability of a failure, such as a thread termination, corrupting the system data structures. They also reduce the complexity of getting critical section code right because it is shorter with fewer separate control paths through it and therefore easier to test. Some of this structuring would be beneficial, if not required, for an implementation using lock-based synchronization because it reduces lock hold time, thereby further reducing contention.



next up previous contents
Next: Non-Blocking Synchronization Implementation Up: The Synergy Between Non-blocking Previous: Data Structures that



Michael Greenwald
Thu Sep 19 12:18:20 PDT 1996