System and method for implementing hierarchical queue-based locks using flat combining
US8458721B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 2, 2011 |
| Grant date | Jun 4, 2013 |
| Priority date | — |
| Expiry date | Dec 1, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/526
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The system and methods described herein may be used to implement a scalable, hierarchal, queue-based lock using flat combining. A thread executing on a processor core in a cluster of cores that share a memory may post a request to acquire a shared lock in a node of a publication list for the cluster using a non-atomic operation. A combiner thread may build an ordered (logical) local request queue that includes its own node and nodes of other threads (in the cluster) that include lock requests. The combiner thread may splice the local request queue into a (logical) global request queue for the shared lock as a sub-queue. A thread whose request has been posted in a node that has been combined into a local sub-queue and spliced into the global request queue may spin on a lock ownership indicator in its node until it is granted the shared lock.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.