Data Ownership

Also called: MutualExclusionPattern?, MutexPattern? or MonitorPattern?.

In some cases, independent instances of data structures can be assigned to particular CPUs or processes, so that each CPU or process accesses or modifies only its own data. Algorithms that can tolerate stale data, such as stochastic relaxation methods used in numerical analysis, may allow CPUs/processes to access each other's data.

DataOwnership eliminates the need for locking, although DisableInterrupts? may be needed if the locus of ownership is the CPU in a kernel or real-time system.

Another way of looking at DataOwnership is to pretend that each CPU/process acquired a lock that is otherwise unused upon entry and released it upon exit. Then, since the data is accessed and modified only by its owning CPU/process, any locks that might be used to protect it would be subsumed into the imaginary per-process/CPU lock. From this viewpoint, DataOwnership is a special case of SubsumeLock?.

An example data-ownership algorithms is described in:

``Efficient Kernel Memory Allocation on Shared-Memory Multiprocessors'', Paul E. McKenney and Jack Slingwine, Winter'93 USENIX.

This paper describes a partially-partitioned algorithm that uses data ownership. The effect is that explicit locks need be required only a few percent of the time, greatly increasing performance despite the fact that the algorithm is not fully partitionable.

CategoryConcurrency