Enhancement to the MCS lock for increased functionality and improved programmability

摘要

A method for allowing a system programmer using a computing system to efficiently use a queuing lock without the requirement of pre-allocating qnode structures for each possible thread of computation expecting to use the lock. More specifically, the lock structure of this invention uses two pointers: a head pointer that points to the next qnode structure representing the next thread or process interested in acquiring the lock, and a tail pointer pointing to the qnode structure representing the last thread or process in a queue of threads or processes awaiting to acquire the lock. When the lock is released, a flag is changed in the qnode structure of the next thread in line (pointed to by the head of the lock) indicating that thread now has the lock and may proceed. A thread or process obtains the lock by spinning on a flag in a qnode structure representing such thread or process. That is, when the flag of a qnode structure is observed to be in a certain state, the thread represented by that qnode structure acquires that lock. The lock now points to the next qnode structure representing the next thread or process that has acquired the lock and to the last qnode structure representing the last thread or process interested in acquiring the lock. A joining thread joins the queue of threads waiting to acquire the lock by changing the tail pointer of the lock to point to a qnode structure representing the joining thread and the head pointer of the previous last thread's qnode structure in the queue to point to the joining thread.