Posting multiple reservations with a conditional store atomic operations in a multiprocessing environment

• US 5,742,785 A
• Filed: 11/20/1995
• Issued: 04/21/1998
• Est. Priority Date: 12/18/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Stone, Janice Murphy, Stone, Harold Stuart
• Primary Examiner(s): Donaghue, Larry D.
• Assistant Examiner(s): DAVIS JR, WALTER D
• Application Number:
  US08/562,539
• Time in Patent Office: 883 Days
• Field of Search: 395/800, 395/375, 395/427, 395/474, 395/471
• US Class Current: 712/217
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/30094 Condition code generation, e.g. Carry, Zero flag
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Using this invention, more than one variable that is shared in a multiprocessing environment can be updated atomically. Each computer processor operating in the multiprocessing environment contains more than one reservation register which, along with this novel method, are used to place reservations on each of more than one shared variable. During the execution of a program, a plurality of shared variables can be reserved, each by its respective reservation register. A reservation is placed on a shared variable by means of a special instruction. The reservation register keeps track of: the address of the shared variable that it is reserving, the value of the modified results that are to be updated in the shared variable address, whether the variable has been updated, whether the reservation is valid, and whether the processor containing the reservation register has a privilege to update the shared variable. A reservation can be invalidated if a second processor tries to read the address of the reserved shared variable. When an instruction is encountered that tries to update a shared variable, the set of reserved modified shared variables designated by that instruction that have unupdated modified results are updated atomically if and only if all the reservations in the designated set are valid. If any of the reservations in the set are invalid, no shared variable in the set is updated. A condition code reports if the update was successful or did not occur. The condition code can be tested so that the sequence of instructions can be repeated until it is successful.

Claims

1. A system of one or more computers in a multiprocessing environment, comprising:

one or more processors connected by an interconnection network to a main memory with one or more shared memory locations;

an arithmetic unit in each processor for calculating results;

a bank of one or more processor registers in each processor for storing calculated results;

a bank of more than one reservation register in each of one or more processors for reserving shared memory locations;

a control unit in each processor with control logic for controlling the arithmetic unit, processor registers, and reservation registers;

a cache memory for storing copies of the shared memory locations;

an address field, in each of the reservation registers, for storing the address of a shared memory location which will be reserved by the reservation register;

a validity field, in each of the reservation registers, for storing information indicating the validity of the reservation of the shared memory location;

a privilege field, in each of the reservation registers, for storing information indicating if the processor on which the reservation register resides has privilege to update the shared memory location of which the address is stored in the address field;

a data field, in each of the reservation registers, for storing modified results which are to update the shared memory location;

means for testing if each reservation in a designated set of reservations is valid during execution of a Write-if-Reserved instruction, the Write-if-Reserved instruction designating the designated set;

means for entering a commitment phase to atomically update the variables reserved by the designated set of reservations during the execution of the Write-if-Reserved instruction when all reservations are valid and the processors updating a set of two or more variables that have privilege to update those respective variables;

means for deferring the response to a request from a second processor for write privilege for access to an address of a reserved shared variable whose address is less than or equal to the last request for write privilege placed by a first processor when the first processor is executing a Write-if-Reserved instruction prior to entering the commitment phase;

means for deferring the response to a request from a second processor for write privilege for access to an address of a reserved shared variable when the first processor is executing a Write-if-Reserved instruction in its commitment phase; and

means for producing a deferred response to respond to a request, a first deferred response granting write privilege and all subsequent deferred responses associated with a same address of the first deferred response causing a receiving processor to rerequest.

2. A system of one or more computers in a multiprocessing environment, as in claim 1, where the reservation register has an additional update field for indicating if the modified results have been written back to the shared memory location.