Electrical computers and digital processing systems: processing – Processing control – Logic operation instruction processing
Reexamination Certificate
1998-12-02
2001-08-28
An, Meng-Al T. (Department: 2154)
Electrical computers and digital processing systems: processing
Processing control
Logic operation instruction processing
C711S147000, C710S200000, C709S241000
Reexamination Certificate
active
06282637
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to execution of instructions that lock and unlock computer resources.
Examples of instructions that lock and unlock computer resources are a test-and-set instruction and a swap instruction, and a cas (compare and swap) instruction. A test-and-set instruction reads a memory location (to perform a test) and also writes the memory location (to perform a “set” operation). This instruction is used to implement semaphores and other software synchronization mechanisms. A swap instruction swaps the contents of a memory location and a register. A cas instruction compares a memory location with a register R
1
, stores the memory location value in register R
2
, and if the comparison was successful, the instruction also stores the previous value of the register R
2
in the memory location. Each of these instructions involves reading and writing a memory location. If between the reading and writing operations another instruction, executed by a different processor, writes the same memory location, the program executing the test-and-set or swap instruction and/or the program executed by the different processor may provide incorrect results. Therefore, the test-and-set and swap instructions are implemented as atomic instructions. These instructions lock the memory location during the reading operation to prevent other processors from writing the location. The location is unlocked when the memory location is written.
It is desirable to enable faster execution of instructions that lock and unlock computer resources.
SUMMARY
Some embodiments of the present invention allow fast execution of instructions that lock and unlock computer resources. In particular, an instruction is allowed to lock a computer resource before it becomes known whether the instruction will be executed to completion or canceled. By the time the instruction processing is complete, the resource becomes unlocked whether or not the instruction is canceled.
An instruction may have to be canceled if, for example, a trap condition occurs while the instruction is being executed. If the instruction is canceled after locking a computer resource but before unlocking the resource, the resource may become permanently locked, which is undesirable.
One solution to this problem is not to allow an instruction to lock a resource until it is determined that the instruction will be executed to completion. However, this delays instruction execution.
Therefore, according to the present invention, an instruction is allowed to lock a resource before it is determined whether the instruction will be executed to completion or canceled. Later in the instruction processing, the resource is unlocked even if the instruction is canceled, and even if the fact that the instruction is canceled is established by the processor before the instruction has unlocked the resource.
In some atomic instruction embodiments for which the resource is a memory location, the instruction is allowed to read the memory location before it is known whether the instruction will be canceled. Performing the reading operation early speeds up the instruction execution.
In some pipelined embodiments, the determination of whether or not an instruction is to be canceled is made before the pipeline stage or stages in which the instruction results are written to their destinations (e.g., architecture register or memory). If an instruction is canceled, writing to the destination(s) is suppressed. However, the instruction still goes through all the pipeline stages at least up to, and including, the stage in which the resource is unlocked. In some embodiments, the instruction goes through all the pipeline stages, but writing to the destinations is suppressed.
In some embodiments, the processor shares a cache with one or more other processors. The resource being locked is a cache memory location.
Other features and advantages of the invention are described below. The invention is defined by the appended claims.
REFERENCES:
patent: 4488217 (1984-12-01), Binder et al.
patent: 5168564 (1992-12-01), Barlow et al.
patent: 5175829 (1992-12-01), Stumpf et al.
patent: 5276847 (1994-01-01), Kohn
patent: 5499356 (1996-03-01), Eckert et al.
patent: 5524255 (1996-06-01), Beard et al.
patent: 5574922 (1996-11-01), James
patent: 5787486 (1998-07-01), Chin et al.
patent: 5968157 (1999-10-01), Joy et al.
patent: 0529536A2 (1993-03-01), None
Paez-Monzon G., et al, “The RISC Processor DMN-6: A unified Data-Control Flow Architecture,” Computer Architecture News, US, Association for Computing Machinery, New York, Vol. 24, No. 4, Sep. 1, 1996 , pp. 3-10 XP000639693 ISSN: 0163-5964.
Chan Jeffrey Meng Wah
Tremblay Marc
An Meng-Al T.
Lin Wen Ja
Skjerven Morrill & MacPherson LLP
Strawbrich Robert C.
Sun Microsystems Inc.
LandOfFree
Partially executing a pending atomic instruction to unlock... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Partially executing a pending atomic instruction to unlock..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partially executing a pending atomic instruction to unlock... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2547225