Real world Examples of read-write in parallel software
I am looking for real world examples requiring read and write access to the same value on parallel systems.
In my opinion, many semaphores or locks are present because there is no known alternative (to the developer), but do you know any patterns where mutexes seem to be a requirement?
To some extent, I'm asking candidates for a standard set of HARD problems for parallel software in the real world.
a source to share
Which locks are used depends on how multiple threads are accessing the data. If you can fine tune the use case, you can eliminate the need for exclusive locks altogether.
Exclusive locking is only necessary if your use case requires the shared data to be 100% accurate at all times. This is the default, most developers start with what we usually think of data.
However, if what you are using for data may suffer from some "weakness", there are several methods of exchanging data between threads without using exclusive locks on each access.
For example, if you have a linked list of data, and if using this linked list will not be upset, if you scan the same node several times bypassing the list and will not be upset if it does not see insert immediately after insertion (or similar artifacts) , you can perform list inserts and deletions using atomic pointer swaps without having to lock the full stop mutex around the insert or delete operation.
Another example: if you have an array or list object that is mostly read by threads and only occasionally updated by the main thread, you can implement non-blocking updates by maintaining two copies of the list: one that is "live" "that other threads can read and the other is "offline", which you can write to the privacy of your stream. To perform an update, you copy the contents of the "live" list to the "offline" list, update the offline list, and then change the offline list pointer to the live list pointer using atomic pointer exchange Then you need some mechanism to allow readers to "merge" from the now self-contained list.In garbage collection, you can simply drop the offline list reference - when the last consumer is done with it, it will be GC'd. On a non-GC system, you can use reference counting to keep track of how many readers are still using the list. In this example, it would be ideal to have only one thread designated as the list update agent. If multiple updates are required, you will need to block the update operation, but only to serialize the updates - without blocking and performance impact on list readers.If multiple updates are required, you will need to block the update operation, but only to serialize the updates - without blocking and performance impact on list readers.If multiple updates are required, you will need to block the update operation, but only to serialize the updates - without blocking and impacting performance on list readers.
All of the loose resource sharing techniques I know of require the use of atomic swaps (aka InterlockedExchange). This usually means a specific instruction on the CPU and / or a hardware bus lock (lock prefix for read or write code in x86 assembler) for a very short period of time. On multiprocessor systems, atomic swaps can invalidate caches on other processors (this was the case with two Pentium II processors), but I don't think this is the same problem for current multi-core chips. Even with these performance limitations, locking is much faster than using the full-featured kernel event object. Simply calling a kernel API function takes several hundred clock cycles (to switch to kernel mode).
Examples of real scenarios:
- production / consumer workflows. The web service receives HTTP requests for data, puts the request on an internal queue, the worker thread pulls the work item from the queue and does the work. The queue is read / written and must be thread safe.
- Data shared between threads with a change in owner. Topic 1 selects an object, drops it on thread 2 for processing, and never wants to see it again. Topic 2 is responsible for deleting an object. The memory management system (malloc / free) must be thread safe.
- File system. This is almost always an OS service and is already completely thread safe, but it is worth listing.
- Counting links. Releases the resource when the link count drops to zero. Increment / decment / test operations must be thread safe. They can usually be implemented using atomic primitives rather than locking full stop mutexes.
a source to share
Most real, parallel programs have some form of synchronization at some level. Often, the best writing software will go to great lengths to reduce the blocking required, but is still required at some point.
For example, I often do simulations where some form of aggregation operation occurs. Generally there are ways to prevent blocking during the modeling phase itself (i.e.: using thread-local state data, etc.), but the actual part of the aggregation usually requires some form of blocking at the end.
Fortunately, this becomes a lock per thread, not per unit of work. This is important in my case, since I usually perform operations of hundreds of thousands or millions of units of work, but most of the time this happens on systems with 4-16 PEs, which means that I usually limit the same number of units of work. Using this type of mechanism, you are still blocking, but you are blocking dozens of elements, not potentially millions.
a source to share