Compare and exchange operation using sleep-wakeup mechanism

Patent metadata

Field	Value
Publication number	US-9733937-B2
Application number	US-201313843305-A
Country	US
Kind code	B2
Filing date	Mar 15, 2013
Priority date	Jun 30, 2004
Publication date	Aug 15, 2017
Grant date	Aug 15, 2017

Abstract

A method, apparatus, and system are provided for performing compare and exchange operations using a sleep-wakeup mechanism. According to one embodiment, an instruction at a processor is executed to help acquire a lock on behalf of the processor. If the lock is unavailable to be acquired by the processor, the instruction is put to sleep until an event has occurred.

First claim

What is claimed is:

1. A method in a processor, comprising:
decoding, with a decoder of the processor, a compare and exchange instruction to perform a compare and exchange operation for acquisition of a lock by the processor, the compare and exchange operation including an atomic compare and exchange operation;
executing the compare and exchange instruction with an execution unit of the processor, which includes at least some hardware, to attempt to acquire the lock; and
putting the compare and exchange instruction at the processor to sleep if the lock is unavailable as part of performing the compare and exchange instruction;
performing other instructions of a same thread as the compare and exchange instruction speculatively while the compare and exchange instruction is put to sleep; and
waking the compare and exchange instruction when an event occurs as part of performing the compare and exchange instruction.

2. The method of claim 1 , further comprising monitoring a memory address corresponding to the lock, wherein the lock is to control access to a shared memory space of a memory.

3. The method of claim 1 , further comprising:
monitoring a destination having a lock value to determine whether the event has occurred, the monitoring of the destination including observing one or more of the following:
(1) a change in the lock value and value; and (2) an attempt to change the lock value, wherein the destination includes a register or a memory location;
detecting the occurrence of the event;
waking up the compare and exchange instruction when the event has occurred, wherein the event comprises one or more of the following: (1) the lock becoming available if the lock value has changed; and (2) the lock potentially becoming available if the attempt to change the lock value has occurred; and
the processor acquiring the available lock.

4. The method of claim 1 , wherein the putting of the compare and exchange instruction to sleep comprises relinquishing of resources for the processor to use to perform other tasks including one or more of the following:
load a plurality of instructions; and
execute the plurality of instructions.

5. The method of claim 4 , wherein the relinquishing of the resources comprises:
relinquishing of a plurality of registers in a register pool;
relinquishing of a plurality of instruction queue entries in an instruction queue;
relinquishing of a plurality of store buffer entries in a store buffer; and
relinquishing of a plurality of re-order buffer entries in a re-order buffer.

6. A processor, comprising:
a plurality of registers;
a decoder to decode a compare and exchange instruction to perform a compare and exchange operation to attempt to acquire a lock, the compare and exchange operation including an atomic compare and exchange operation;
an execution unit coupled with the decoder and the plurality of registers, the execution unit including at least some hardware, the execution unit to execute the compare and exchange instruction to attempt to acquire a acquire the lock; and
a sleep-wakeup mechanism to put the compare and exchange instruction to sleep, as part of performing the compare and exchange instruction, if the attempt to acquire the lock fails; and
at least one other execution unit of the processor to perform other instructions of a same thread as the compare and exchange instruction speculatively while the compare and exchange instruction is put to sleep.

7. The processor of claim 6 , further comprising:
monitor logic to monitor a destination that is to have a lock value to determine whether an event has occurred, wherein to monitor the destination is to include to observe one or more of the following: (1) a change in the lock value; and (2) an attempt to change the lock value, wherein the destination includes a dedicated register or a memory location;
detection logic to detect the occurrence of the event; and
the sleep-wakeup mechanism to wakeup the compare and exchange instruction when the event has occurred, wherein the event comprises one or more of the following: (1) the lock becoming available if the lock value has changed; and (2) the lock potentially becoming available if the attempt to change the lock value has occurred.

8. The processor of claim 6 , wherein the processor when the compare and exchange instruction is put to sleep is to relinquish resources for the processor to use to perform other tasks including one or more of the following: (1) load a plurality of instructions; and (2) execute the plurality of instructions.

9. The processor of claim 8 , wherein the processor is to relinquish resources comprising:
a plurality of registers in a register pool;
a plurality of instruction queue entries in an instruction queue;
a plurality of store buffer entries in a store buffer; and
a plurality of re-order buffer entries in a re-order buffer.

10. The processor of claim 6 , further comprising a bus interface unit to couple the processor to a memory, the bus interface unit further includes a dedicated register associated with the compare and exchange instruction.

11. The processor of claim 6 , further comprising an instruction set having a plurality of instructions including the compare and exchange instruction.

12. A processor comprising:
a plurality of registers;
a decoder to decode a compare and exchange instruction of a thread;
an execution unit coupled with the decoder and the plurality of registers, the execution unit responsive to the compare and exchange instruction being decoded to attempt to acquire a lock;
a sleep-wakeup mechanism to put the compare and exchange instruction to sleep, as part of performing the compare and exchange instruction, if the attempt to acquire the lock fails, wherein while the compare and exchange instruction is put to sleep other instructions of the thread, including instructions after the compare and exchange instruction, are to be performed out-of-order but not retired until after the compare and exchange instruction is waked up.

13. The processor of claim 12 , further comprising a timeout counter to count a time while the compare and exchange instruction is put to sleep.

14. The processor of claim 12 , wherein the compare and exchange instruction is to be put to sleep in a memory order buffer.

15. The processor of claim 12 , wherein the sleep-wakeup mechanism is to wake the compare and exchange instruction upon detection of an invalidation snoop for a cache line associated with the lock.

Assignees

• Intel Corp

Inventors

• Saha Bratin
• Merten Matthew C
• Hammarlund Per

Classifications

• G06F2209/521

  Atomic · CPC title

• G06F9/30087

  Synchronisation or serialisation instructions · CPC title

• G06F9/526

  Mutual exclusion algorithms · CPC title

• G06F9/3857

  Physics · mapped topic

• G06F9/3004

  to perform operations on memory · CPC title