System and method for avoiding deadlocks when performing storage updates in a multi-processor environment

• US 7,953,932 B2
• Filed: 02/13/2008
• Issued: 05/31/2011
• Est. Priority Date: 02/13/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Webb, Charles F., Tsai, Aaron, Shum, Chung-Lung Kevin, Barrick, Brian D.
• Primary Examiner(s): Farrokh; Hashem
• Application Number:
  US12/030,627
• Publication Number:
  US 20090204763A1
• Time in Patent Office: 1,203 Days
• Field of Search: 711/124, 711/122
• US Class Current: 711/124
• CPC Class Codes: G06F 12/0828 with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3867 using instruction pipelines

Abstract

A system and method for avoiding deadlocks when performing storage updates in a multi-processor environment. The system includes a processor having a local cache, a store queue having a temporary buffer with capability to reject exclusive cross-interrogates (XI) while an interrogated cache line is owned exclusive and is to be stored, and a mechanism for performing a method. The method includes setting the processor into a slow mode. A current instruction that includes a data store having one or more target lines is received. The current instruction is executed, with the executing including storing results associated with the data store into the temporary buffer. The store queue is prevented from rejecting an exclusive XI corresponding to the target lines of the current instruction. Each target line is acquired with a status of exclusive ownership, and the contents from the temporary buffer are written to each target line after instruction completion.

Claims

1. A processor in a multi-processor shared data environment having a cache memory structure involving various ownership states as to a cache line, which state includes a read-only or shared state and an exclusive state for holding the line exclusively, with such processor comprising:

a local cache adapted for communication with one or more shared higher level caches for sourcing cache lines;

a store queue having a temporary buffer with capability to reject exclusive cross-interrogates (XI) while an interrogated cache line is owned exclusive and is to be stored; and

a mechanism for performing a method comprising;

setting the processor into a slow mode to fetch, decode and execute a single instruction at a time;

receiving a current instruction that includes a data store of data to one or more target lines;

executing the current instruction, the executing including storing the data into the temporary buffer;

preventing the store queue from rejecting an exclusive XI corresponding to the target lines of the current instruction; and

acquiring each of the target lines with a status of exclusive ownership and writing contents from the temporary buffer to each target line after instruction completion.

2. The processor of claim 1 wherein the preventing the store queue from rejecting an exclusive XI is performed by blocking a XI reject valid bit for target lines associated with the data store even if the processor already has line exclusive in response to receiving the current instruction.

3. The processor of claim 2 wherein the preventing is further accomplished by only acquiring target lines of read-only or shared status associated with the data store from the local cache, and marking it as read-only status in the store queue in response to receiving the instruction.

4. The processor of claim 1 wherein the processor is set into the slow mode in response to detecting a deadlock on a previous attempt in normal mode to execute instructions by requesting each target line with a status of exclusive ownership.

5. The processor of claim 1 wherein when the instruction is an atomic Instruction. Each of the target lines is acquired with a status of exclusive ownership in response to receiving the instruction and the acquiring each of the target lines with a status of exclusive ownership after the execution has completed is not performed.

6. The processor of claim 1 wherein the method further comprises resetting the processor into a fast or normal mode to execute multiple instructions at a time.

7. The processor of claim 1 wherein the processor is a pipelined processor.

8. The processor of claim 7 wherein the pipelined processor is also out of order.

9. The processor of claim 1 wherein the writing to the target line is performed using a write-through scheme.

10. The processor of claim 1 wherein the writing is performed using a write-back scheme.

11. A method for avoiding deadlocks when performing storage updates in a multi-processor environment, the method comprising:

setting a processor into a slow mode to fetch, decode and execute a single instruction at a time;

receiving a current instruction that includes a data store of data to one or more target lines;

executing the current instruction, the executing including storing the data into a temporary buffer;

preventing the store queue from rejecting an exclusive XI corresponding to the target lines of the current instruction; and

acquiring each of the target lines with a status of exclusive ownership and writing contents from the temporary buffer to each target line after instruction completion.

12. The method of claim 11 wherein the processor is set into the slow mode in response to detecting a deadlock on a previous attempt in normal mode to execute instructions by requesting each target line with a status of exclusive ownership.

13. The method of claim 11 wherein when the instruction is an atomic instruction, each of the target lines is acquired with a status of exclusive ownership in response to receiving the instruction and the acquiring each of the target lines with a status of exclusive ownership after the execution has completed is not performed.

14. The method of claim 11 wherein the method further comprises resetting the processor into a fast or normal mode to execute multiple instructions at a time.

15. The method of claim 11 wherein the processor is a pipelined processor.

16. The method of claim 15 wherein the pipelined processor is also out of order.

17. A processor in a multi-processor, shared data environment, the processor comprising:

a local cache adapted for communication with one or more shared higher level caches for sourcing cache lines; and

a mechanism for performing a method comprising;

receiving an instruction that includes a data store;

setting the processor to a fast mode where multiple instructions are executed in parallel and a target cache line associated with the data store is acquired from the local cache with a status of exclusive ownership prior to execution of the instruction;

initiating execution of the instruction in the fast mode;

in response to detecting a possible deadlock during the execution in fast mode;

aborting execution of the instruction in the fast mode;

setting the processor to a slow mode where a single instruction at a time is executed and the target cache line is acquired from the local cache with a status of exclusive ownership prior to execution of the instruction; and

initiating execution of the instruction in the slow mode; and

in response to detecting a possible deadlock during the execution in slow mode;

aborting execution of the instruction in the slow mode;

setting the processor to an enhanced slow mode where a single instruction at a time is executed and the target cache line is acquired from the local cache with a status of read only prior to execution of the instruction and in a status of exclusive ownership after execution of the instruction has completed; and

initiating execution of the instruction in the enhanced slow mode.

18. The processor of claim 17 wherein the method further comprises resetting the processor into a fast mode after the instruction has completed in the enhanced slow mode.

19. The processor of claim 17 wherein a possible deadlock is detected when a threshold number of exclusive XI rejects have been performed without an instruction being completed.

20. The processor of claim 19 wherein a possible deadlock is prevented by qualifying the exclusive XI rejects with current local cache misses while acquiring one or more cache lines from shared cache for either read-only or exclusive status.