Apparatus and method for controlling exclusive access to portions of addressable memory in a multiprocessor system

• US 5,408,629 A
• Filed: 08/13/1992
• Issued: 04/18/1995
• Est. Priority Date: 08/13/1992
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Kregness, Glen R., Tsuchiva, Kenichi, Price deceased, Ferris T., Lucas, Gary J.
• Primary Examiner(s): Gossage, Glenn A.
• Assistant Examiner(s): Kim, Matthew M.
• Application Number:
  US07/929,329
• Time in Patent Office: 978 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/200, 395/425
• US Class Current: 711/151
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 13/18 based on priority control G06F13/1605 takes precedence
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A method and apparatus for granting exclusive access to a selected portion of addressable memory to a requesting processor in a large scale multiprocessor system. An instruction processor having a store-through operand cache executes an instruction requiring exclusive access to an address in a shared memory. If the address upon which the lock is requested is not in the local cache, the instruction processor simultaneously sends a lock and read request to the coupled storage controller. Otherwise, a no-operand-read and lock request is sent to the storage controller. If, while processing the lock request, no conflict is detected by the storage controller, the address is marked as locked and a lock granted signal is issued to the requesting processor. Concurrent with the processing the lock request the storage controller processes the read request. The lock granted signal and requested data are returned to the requesting processor asynchronously. The requesting processor can continue processing the lock instruction when the lock granted and required data have been returned from the storage controller. When two or more processors contend for a lock on a the same portion of addressable memory, one processor is granted the lock while the other contending processor(s) are forced to wait. Lock contention is arbitrated by a round robin priority scheme.

Claims

1. An apparatus for coordinating exclusive access to selectable portions of addressable memory in a data processing system having a first storage controller, a second storage controller, a first addressable memory unit coupled to the first storage controller and a second addressable memory unit coupled to the second storage controller, wherein each of the storage controllers controls access to the coupled addressable memory unit and the first storage controller is coupled to the second storage controller, the system further including a first processor and a second processor coupled to the first storage controller, and a third processor coupled to the second storage controller, wherein the first, second, and third processors execute instructions and generate memory access requests to manipulate portions of the addressable memory, whereby the intercoupling of the first and second storage controllers provides access to the second addressable memory unit for the first and second processors and further provides access to the first addressable memory unit for the third processor, the apparatus comprising:

first storage request priority control means disposed within the first storage controller for selecting among memory access requests referencing the first addressable memory unit;

second storage request priority control means disposed within the second storage controller for selecting among memory access requests referencing the second addressable memory unit;

first lock control means disposed within the first storage controller and coupled to said first storage request priority means for coordinating memory access requests for exclusive access to a portion of memory in the first addressable memory unit;

second lock control means disposed within the second storage controller and coupled to said second storage request priority means for coordinating memory access requests for exclusive access to a portion of memory in the second addressable memory unit;

a first set of lock address registers disposed within the first storage controller and coupled to said first lock control means, wherein each one of said lock address registers in said first set stores an address referencing the first addressable memory unit and for which exclusive use is requested by a predetermined one and only one of the first, second, and third processors;

a second set of lock address registers disposed within the second storage controller and coupled to said second lock control means, wherein each one of said lock address registers in said second set stores an address referencing the second addressable memory unit and for which exclusive use is requested by a predetermined one and only one of the first, second, and third processors;

a first set of locked-bit registers disposed within the first storage controller and coupled to said first lock control means, wherein each one of said locked-bit registers in said first set of locked-bit registers indicates whether a predetermined one and only one of said lock address registers in said first set of lock address registers references a portion of addressable memory which is exclusively held;

a second set of locked-bit registers disposed within the second storage controller and coupled to said second lock control means, wherein each one of said locked-bit registers in said second set of locked-bit registers indicates whether a predetermined one and only one of said lock address registers in said second set of lock address registers references a portion of addressable memory which is exclusively held;

a first set of lock-requested-bit registers disposed within the first storage controller and coupled to the first lock control means, wherein each one of said lock-requested-bit registers in said first set of lock-request-bit registers indicates whether a predetermined one and only one of said lock address registers in said first set of lock address registers references a portion of addressable memory for which exclusive access is requested;

a second set of lock-requested-bit registers disposed within the second storage controller and coupled to the second lock control means, wherein each one of said lock-requested-bit registers in said second set of lock-requested-bit registers indicates whether a predetermined one and only one of said lock address registers in said second set of lock address registers references a portion of addressable memory for which exclusive access is requested;

first lock priority control means disposed within the first storage controller and coupled to the first lock control means for selecting memory access requests for exclusive access to a portion of memory in the first addressable memory unit, for sending a first lock granted signal to the first processor when exclusive access to a portion of addressable memory is granted to tile first processor, for sending a second lock granted signal to the second processor when exclusive access to a portion of addressable memory is granted to the second processor, for sending a third lock granted signal to the third processor when exclusive access to a portion of addressable memory is granted to the third processor, and for sending a fourth lock granted signal to the fourth processor when exclusive access to a portion of addressable memory is granted to the fourth processor; and

second lock priority control means disposed within the second storage controller and coupled to the second lock control means for selecting memory access requests for exclusive access to a portion of memory in the second addressable memory unit, for sending a first lock granted signal to the first processor when exclusive access to a portion of addressable memory is granted to the first processor, for sending a second lock granted signal to the second processor when exclusive access to a portion of addressable memory is granted to the second processor, for sending a third lock granted signal to the third processor when exclusive access to a portion of addressable memory is granted to the third processor, and for sending a fourth lock granted signal to the fourth processor when exclusive access to a portion of addressable memory is granted to the fourth processor.

2. The apparatus of claim 1,

wherein the memory access request include a read-with-lock request and said read-with-lock request includes an address code that indicates the portion of addressable memory to read and a lock code that indicates that exclusive access to the portion of addressable memory referenced by said address code is requested;

the apparatus further including

first initiation means disposed within the first storage controller and coupled to said first storage request priority control means for initiating a read from the first addressable memory unit of the portion of addressable memory referenced by said address code, before said first lock granted signal is sent, before said second lock granted signal is sent, before said third lock granted signal is sent, and before said fourth lock granted signal is sent; and

second initiation means disposed within the second storage controller and coupled to said second storage request priority control means for initiating a read from the second addressable memory unit of the portion of addressable memory referenced by said address code, before said first lock granted is sent, before said second lock granted signal is sent, before said third lock granted signal is sent, and before said fourth lock granted signal is sent.

3. The apparatus of claim 1, further including:

first detection means disposed in said first lock control means for detecting when the first processor is inoperative, detecting when the second processor is inoperative, detecting when the third processor is inoperative, and detecting when the fourth processor is inoperative, clearing said first locked-bit register when the first processor is inoperative, clearing said second lock-bit register when the second processor is inoperative, clearing said third lock-bit register when the third processor is inoperative, and clearing said fourth lock-bit register when the fourth processor is inoperative, wherein the first processor is prohibited from retaining access to said portion of addressable memory if it is inoperative, the second processor is prohibited from retaining access to said portion of addressable memory if it is inoperative, the third processor is prohibited from retaining access to said portion of addressable memory if it is inoperative, and the fourth processor is prohibited from retaining access to said portion of addressable memory if it is inoperative; and

second detection means disposed in said second lock control means for detecting when the first processor is inoperative, detecting when the second processor is inoperative, detecting when the third processor is inoperative, and detecting when the fourth processor is inoperative, clearing said first locked-bit register when the first processor is inoperative, clearing said second lock-bit register when the second processor is inoperative, clearing said third lock-bit register when the third processor is inoperative, wherein the first processor is prohibited from retaining access to said portion of addressable memory if it is inoperative, the second processor is prohibited from retaining access to said portion of addressable memory if it is inoperative, the third processor is prohibited from retaining access to said portion of addressable memory if it is inoperative, and the fourth processor is prohibited from retaining access to said portion of addressable memory if it is inoperative.

4. An apparatus for coordinating exclusive access to selectable portions of an addressable memory in a data processing system having a storage controller for controlling access to the addressable memory and a first processor and a second processor coupled to the storage controller for executing instructions and processing data stored in the addressable memory, the apparatus comprising:

storage request priority control means disposed within the storage controller for receiving requests from the first and second processors and selecting one of the processors to receive access to the addressable memory unit;

lock control means coupled to said storage request priority control means for coordinating requests by the first and second processors for exclusive access to the selectable portions of the addressable memory unit, for sending a first lock granted signal to the first processor when exclusive access to a portion of addressable memory is granted to the first processor, and for sending a second lock granted signal to the second processor when exclusive access to a portion of addressable memory is granted to the second processor;

a first lock address register coupled to said lock control means, for storing an address for which exclusive use is requested by the first processor;

a second lock address register coupled to said lock control means for storing an address for which exclusive use is requested by the first processor;

a first locked-bit register coupled to said lock control means, for indicating when said lock control means has granted exclusive access to a portion of addressable memory to the first processor;

a second locked-bit register coupled to said lock control means for indicating when said lock control means has granted exclusive access to a portion of addressable memory to the second processor;

a first lock-requested-bit register coupled to said lock control means with for indicating whether the first processor awaits exclusive access to the portion of addressable memory referenced by said first address register; and

a second lock-requested-bit register coupled to said lock control means for indicating whether the second processor awaits exclusive access to the portion of addressable memory referenced by said second lock address register

5. The apparatus of claim 4, further comprising initiation means coupled to said storage request priority control means for initiating a read request for a selected address before said first lock granted signal is sent and before said second lock granted signal is sent.

6. The apparatus of claim 4, wherein said lock control means further includes processor-inoperative detection means for detecting when the first processor is inoperative, detecting when the second processor is inoperative, clearing said first locked-bit register when the first processor is inoperative, and clearing said second lock-bit register when the second processor is inoperative, wherein the first processor is prohibited from retaining access to said portion of addressable memory if it is inoperative and the second processor is prohibited from retaining access to said portion of addressable memory if it is inoperative.

7. A method for granting exclusive access to a selectable portion of an addressable memory to a processor in a data processing system having a plurality of directly intercoupled storage controllers for controlling access to the addressable memory, and a plurality of processors for processing instructions and data stored in the addressable memory, wherein predetermined ones of the processors are directly coupled to predetermined ones of the storage controllers, and each storage controller controls access to a directly coupled addressable memory unit, whereby each processor, through the storage controller to which a processor is directly coupled, has access to addressable memory units controlled by the other storage controllers, each of the storage controllers further including a plurality of lock address registers, a plurality of locked-bit registers, and a plurality of lock-requested-bit registers, wherein each of the lock address registers within a storage controller is dedicated to storing an address code from one and only one of the processors, each of the locked-bit registers is dedicated to storing the status of one and only one of the address codes in the lock address registers, and each of the lock-requested-bit registers is dedicated to storing the status of one and only one of the address codes in the lock address registers, the method comprising the steps of:

transmitting a lock request and an address code from a first processor to a first storage controller, wherein said address code specifies a portion of the addressable memory to which said first processor requires exclusive access, and-said lock request specifies a request for exclusive access to said portion of addressable memory;

prohibiting said first processor from processing said portion of addressable memory until a first lock granted signal is received by said first processor;

sending said lock request and said address code from said first storage controller to a destination storage controller, wherein said destination storage controller controls access to said portion of addressable memory referenced by said address code;

storing said address code in a first lock address register at said destination storage controller;

testing whether said address code matches the contents of any of the plurality of lock address registers at said destination storage controller other than said first lock address register;

setting a first locked-bit register corresponding to said first lock address register if said address code does not match the contents of any of the plurality of lock address registers at said destination storage controller other than said first lock address register;

setting a first lock-requested-bit register corresponding to said first lock address register if said address code matches the contents of any of the plurality of lock address registers at said destination controller other than said first lock address register;

sending said first lock granted signal from said destination storage controller to said first storage controller when said first locked-bit register is set;

sending said first lock granted signal from said first storage controller to said first processor;

processing said portion of addressable memory at said first processor;

transmitting a lock release request from said first processor to said first storage controller when said first processor has completed processing on said portion of addressable memory, wherein said lock release request indicates that said first processor no longer requires exclusive access to said portion of the addressable memory;

transmitting said lock release request from said first storage controller to said destination storage controller;

clearing said first locked-bit register upon receipt of said lock release request;

selecting at said destination storage controller a second lock address register whose contents matches said first register and whose corresponding lock-requested-bit register is set when said lock release request is received by said destination storage controller;

setting at said destination storage controller a second locked-bit register corresponding to said second lock address register to indicate that said second processor has exclusive access to said portion of addressable memory;

sending a second lock granted signal from said first storage controller to said second processor; and

processing said portion of addressable memory at said second processor.

8. The method of claim 7, further comprising the step of initiating a read of said portion of addressable memory before said testing step is complete;

and

returning said portion of addressable memory to said first processor independent of whether said portion of addressable memory is locked by another of the plurality of processors.

9. The method of claim 7, further comprising the steps of:

comprising the steps of;

detecting an inoperative processor at said destination storage controller;

clearing a third locked-bit register corresponding to a third lock address register which has an address code that was transmitted with a lock request by said inoperative processor;

selecting a fourth lock address register whose contents matches an address code which was transmitted with a lock request by said inoperative processor;

setting a fourth locked-bit register corresponding to said fourth lock address register;

sending a third lock granted signal from said destination storage controller to said fourth processor; and

processing said portion of addressable memory at said fourth processor.

10. A method for granting exclusive access to a selectable portion of an addressable memory to a processor in a data processing system having a storage controller for controlling access to the addressable memory, and a plurality of processors for processing instructions and data stored in the addressable memory, the method comprising the steps of:

transmitting an operation code from a first processor to a storage controller, wherein said operation code specifies a portion of the addressable memory to which said first processor requires exclusive access and a first lock request for exclusive access to said portion of addressable memory;

prohibiting said first processor from processing said portion of addressable memory until a lock granted signal is received from the storage controller;

testing whether said portion of addressable memory is locked by another of the plurality of processors;

initiating a read of said portion of addressable memory before said testing step is complete;

returning said portion of addressable memory to said first processor independent of whether said portion of addressable memory is locked by another of the plurality of processors;

locking said portion of addressable memory if said portion of addressable memory is not already locked by one of the plurality of processors;

enqueuing said first lock request in a queue of lock requests if said portion of addressable memory is already locked by one of the plurality of processors;

sending said lock granted signal from the storage controller to said first processor when said d portion of addressable memory has been loked;

processing said portion of addressable memory at said first processor;

selecting a second lock request from said queue of lock requests when a lock release request is received from the first processor by the storage controller;

granting exclusive access to said portion of addressable memory to a second processor that transmitted said second lock request.

11. The method of claim 10, further comprising the steps of:

detecting an inoperative processor;

unlocking said portion of addressable memory locked by said inoperative processor; and

selecting a third lock request from said queue of lock requests when said inoperative processor is detected;

granting exclusive access to said portion of addressable memory to a third processor that transmitted said third lock request.

12. A method for granting exclusive access to a selectable portion of an addressable memory to a processor in a data processing system having a storage controller for controlling access to the addressable memory, and a plurality of processors for processing instructions and data stored in the addressable memory, the storage controller further including a plurality of lock address registers, a plurality of locked-bit registers, and a plurality of lock-requested-bit registers, wherein each of the lock address registers is dedicated to storing an address code from one and only one of the processors, each of the locked-bit registers is dedicated to storing the status of one and only one of the address codes in the lock address registers, and each of the lock-requested-bit registers is dedicated to storing the status of one and only one of the address codes in the lock address registers, the method comprising the steps of:

transmitting a lock request and an address code from a first processor to a storage controller, wherein said address code specifies a portion of the addressable memory to which said first processor requires exclusive access, and said lock request specifies a request for exclusive access on said portion of addressable memory;

prohibiting said first processor from processing said portion of addressable memory until a first lock granted signal is received by said first processor from the storage controller;

storing said address code in a first lock address register;

testing whether said address code matches the contents of any of the plurality of address registers other than said first lock address register;

setting a first locked-bit register corresponding to said first lock address register if said address code did not match the contents of any of the plurality of lock address registers other than the first lock address register;

setting a first lock-requested-bit register corresponding to said first lock address register if said address code matches the contents of any of the plurality of lock address registers other than the first lock address register;

sending said first lock granted signal from the storage controller to said first processor when said first locked-bit register is set;

processing said portion of addressable memory at said first processor;

transmitting a lock release request from said first processor to the storage controller, wherein said lock release request indicates that said first processor no longer requires exclusive access to said portion of addressable memory;

clearing said first locked-bit register when said lock release request is received by the storage controller;

selecting a second lock address register whose contents matches said address code and whose corresponding lock-requested-bit register is set, when said lock release request is received by the storage controller;

granting exclusive access to a second processor that transmitted said second lock request; and

setting a second locked-bit register corresponding to said second lock address register to indicate that said second processor has exclusive access to said portion of addressable memory.

13. The method of claim 12, further comprising the step of initiating a read said portion of addressable memory before said testing step is complete;

and

returning said portion of addressable memory to said first processor independent of whether said portion of addressable memory is locked by another of the plurality of processors.

14. The method of claim 12, further comprising the steps of:

detecting an inoperative processor;

clearing a third locked-bit register corresponding to a third lock address register which has an address code which that transmitted with a lock request by said inoperative processor;

selecting a fourth address register whose contents matches an address code that was previously transmitted with a lock request by said inoperative processor;

setting a fourth locked-bit register corresponding to said fourth address register;

sending a second lock granted signal to a fourth processor that transmitted an address code which is stored in said fourth address register; and

processing the selected portion of addressable memory at said fourth processor.

15. A method for granting exclusive access to a selectable portion of an addressable memory to a processor in a data processing system having a plurality of directly intercoupled storage controllers for controlling access to the addressable memory, and a plurality of processors for processing instructions and data stored in the addressable memory, wherein predetermined ones of the processors are directly coupled to predetermined ones of the storage controllers, and each storage controller controls access to a directly coupled addressable memory unit, whereby each processor, through the storage controller to which a processor is directly coupled, has access to addressable memory units controlled by the other storage controllers, the method comprising the steps of:

transmitting a lock request and an address code from a first processor to a first storage controller, wherein said address code specifies a portion of the addressable memory to which said first processor requires exclusive access; and

said lock request specifies the request for exclusive access on said portion of memory;

prohibiting said first processor from processing said portion of addressable memory until a lock granted signal is received from the first storage controller;

transmitting said lock request and said address code from said first storage controller to a destination storage controller, wherein said destination storage controller controls access to said portion of addressable memory referenced by said address code;

testing, at said destination storage controller, whether said portion of addressable memory is locked by any another of the plurality of processors;

locking said portion of addressable memory if no others of the plurality of processors have said portion of addressable memory locked;

sending said lock granted signal from said destination storage controller to said first storage controller if said portion of memory is not locked by another of the plurality of processors; and

sending said lock granted signal front said first storage controller to said first processor.

16. A method for granting exclusive access to a selectable portion of an addressable memory to a processor in a data processing system having a plurality of directly intercoupled storage controllers for controlling access to the addressable memory, and a plurality of processors for processing instructions and data stored in the addressable memory, wherein predetermined ones of the processors are directly coupled to predetermined ones of the storage controllers, and each storage controller controls access to a directly coupled addressable memory unit, whereby each processor, through the storage controller to which a processor is directly coupled, has access to addressable memory controlled by the other storage controllers, the method comprising the steps of:

transmitting a lock request and an address code from a first processor to a first storage controller, wherein said address code specifies a portion of the addressable memory to which said first processor requires exclusive access, and said lock request specifies the request for exclusive access on said portion of memory;

prohibiting said first processor from processing said portion of addressable memory until a first lock granted signal is received by said first processor;

transmitting said lock request and said address code from said first storage controller to a destination storage controller, wherein said destination storage controller controls access to said portion of addressable memory referenced by said address code;

testing, at said destination storage controller, whether said portion of addressable memory is locked by another of the plurality of processors;

enqueuing said lock request in a queue of lock requests in said destination storage controller if a second processor has said portion of addressable memory locked, wherein each lock request in said queue of lock requests is associated with one and only one of the plurality of processors;

locking said portion of addressable memory if said portion of addressable memory is not locked by another of the plurality of processors;

sending said lock granted signal from said destination storage controller to said first storage controller if said portion of memory is not locked by another of the plurality of processors;

transmitting said lock granted signal from said first storage controller to said first processor;

transmitting a lock release request from said first processor to said first storage controller when said first processor has completed processing on said portion of addressable memory, wherein said lock release request indicates that exclusive access to said portion of the addressable memory is no longer necessary;

transmitting said lock release request from said first storage controller to said destination storage controller;

releasing a lock on said portion of addressable memory at said destination storage controller upon receipt of said lock release request; and

selecting one lock request from said queue of lock requests after said releasing step; and

granting exclusive access to another of said plurality of processors associated with said one lock request.