Taking concurrency seriously (position paper)
Maurice P. Herlihy · 1988
I'd like to propose a challenge to language designers interested in concurrency: how well do your favorite constructs support highly-concurrent data structures? For example, consider a real-time system consisting of a pool of sensor and actuator processes that communicate via a priority queue in shared memory. Processes execute asynchronously. When a sensor process detects a condition requiring a response, it records the condition, assigns it a priority, and places the record in the queue. Whenever an actuator process becomes idle, it dequeues the highest priority item from the queue and takes appropriate action. The conventional way to prevent concurrent queue operations from interfering is to execute each operation as a critical section: only one process at a time is allowed to access the data structure. As long as one process is executing an operation, any other needing to access the queue must wait. Although this approach is widely used, it has significant drawbacks.