Semaphores Augmented with a Waiting Array

Semaphores are a widely used and foundational synchro- nization and coordination construct used for shared memory multithreaded programming. They are a keystone concept, in the sense that most other synchronization constructs can be implemented in terms of semaphores, although the con- verse does not generally hold. Semaphores and the quality of their implementation are of consequence as they remain heavily used in the Linux kernel and are also available for application programming via the pthreads programming interface. We first show that semaphores can be implemented by borrowing ideas from the classic ticket lock algorithm. The resulting ticket-semaphore algorithm is simple and compact (space efficient) but does not scale well because of the detri- mental impact of global spinning. We then transform ticket- semaphore into the TWA-semaphore by the applying tech- niques derived from the TWA - Ticket Locks Augmented with a Waiting Array algorithm, yielding a scalable semaphore that remains compact and has extremely low latency.