Back to results
US 8,279,885 B2Granted
Lockless processing of command operations in multiprocessor systems
AssigneePacketeer, Inc.
InventorGuy Riddle
Life of this patent
Estimating the term…
Abstract
A beltway mechanism that takes advantage of atomic locking mechanisms supported by certain classes of hardware processors to handle the tasks that require atomic access to data structures while also reducing the overhead associated with these atomic locking mechanisms. The beltway mechanisms described herein can be used to control access to software and hardware facilities in an efficient manner.
Claims20
An apparatus comprising
- N processors, where N is greater than 1;
- a work order module operative to provide work queue entries to the N processors, wherein the work queue entries correspond to respective tasks, and to provide, to a given processor of the N processors, exclusive access to one or more shared data structures for work queue entries including atomic tags;
- a memory operative to store one or more instances of a beltway data structure, each instance of a beltway data structure comprising N circular buffers for corresponding ones of the N processors, wherein the N circular buffers each comprise a plurality of entries;
- the memory further operative to store processor-readable instructions for a beltway producer function and a beltway consumer process;
- wherein the beltway producer function includes instructions operative to cause the N processors, when executing the beltway producer function, to
- add entries to corresponding ones of the circular buffers of an identified instance of a beltway data structure;
- conditionally submit work queue entries to the work order module including an atomic tag associated with the identified instance of the beltway data structure;
- and
- wherein the beltway consumer process includes instructions operative to cause a processor of the N processors, responsive to a work queue entry identifying the beltway consumer process and an atomic tag corresponding to the instance of a beltway data structure, to:
- identify the instance of the beltway data structure based on one or more attributes of the work queue entry;
- read entries from the circular buffers of the identified instance of the beltway data structure;
- and
- call a consumer function associated with the identified instance of the beltway data structure to process the read entries.
10 more elements
A method comprising
- maintaining a queue of work queue entries in a work order module, one or more of the work queue entries including a tag, wherein the work order module is operative to schedule work queue entries in the queue for N processors, wherein N is greater than 1, such that only a single processor of the N processors is provided a work queue entry labeled with a given tag;
- storing, in a memory, one or more instances of a beltway data structure, each instance of a beltway data structure comprising N circular buffers (rings) for corresponding ones of the N processors, wherein the N circular buffers each comprise a plurality of entries;
- executing a beltway producer function operative to
- add entries to corresponding ones of the circular buffers of an identified instance of a beltway data structure;
- conditionally submit work queue entries to the work order module including a tag associated with the identified instance of the beltway data structure;
- and
- executing, responsive to a work queue entry identifying a beltway consumer process and a tag corresponding to the instance of a beltway data structure, a beltway consumer process on a select processor of the N processors, the beltway consumer process operative to:
- identify the instance of the beltway data structure based on one or more attributes of the work queue entry;
- read entries from the circular buffers of the identified instance of the beltway data structure;
- and
- call a consumer function associated with the identified instance of the beltway data structure to process the read entries.
8 more elements
Dependencies are inferred from the claim text.