US5289588A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Interlock acquisition for critical code section execution in a shared memory common-bus individually cached multiprocessor system
Assignee: Advanced Micro Devices Inc
•
Filing: 1990-04-24
•
Granted: 1994-02-22
•
Expires: 2010-04-24
Abstract
Abstract There is disclosed an interlock variable acquisition system and method for use in a processing system of the type including a plurality of processors coupled by a common bus which permits exclusive execution of critical sections by each of the processors while limiting traffic on the common bus. A cache associated with each of the processors stores the value of the interlock variable and locally tests the interlock variable state responsive to an instruction from its processor. If the cache determines that the interlock variable is in the available state, it conveys the available value of the interlock variable to its associated processor and writes, over the common bus, the busy state to each cache associated with the other processors. When its processor completes its critical section, the cache writes, over the common bus, the available state of the interlock variable to each cache associated with the other processors. The other caches update their copies of the interlock variable and do not invalidate them.
Inventors
- 👤 Seungyoon P. Song
- 👤 Stephen C. Horne
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 17:44
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/52; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0815; G06F13/00; G06F13/14; G06F13/36; G06F15/00; G06F15/16; G06F15/163; G06F15/167
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
420 words
An interlock variable acquisition system for use in a processing system of the type including a plurality of processors coupled to a common bus, selected processors of said plurality of processors having a data cache and being arranged to execute program instructions including at least one particular critical section requiring exclusive execution thereof, said interlock variable acquisition system being arranged to permit exclusive execution of said at least one particular critical section by each of said selected processors while limiting traffic on said common bus and comprising: storage means associated with said data cache of each one of said selected processors for storing an interlock variable related to said at least one particular critical section executable by said one selected processor, said interlock variable having either an available value indicating that no processor of said plurality of processors other than said one selected processor is currently executing said at least one particular critical section or a busy value indicating that another processor of said plurality of processors other than said one selected processor is currently executing said at least one particular critical section, said storage means being arranged to store a plurality of status bits associated with said interlock variable, said plurality of status bits including a first status bit having a first value when said interlock variable has a valid value and a second status bit having a second value when said interlock variable is shared by said other said storage means storing said interlock variable, said storage means being arranged to provide said common bus with the value of said interlock variable stored therein responsive to said first status bit having said first value; interlock variable detect means associated with said data cache of each one of said selected processors and responsive to a command instruction from its associated said one selected processor for detecting the value of said interlock variable in its associated storage means; and write means associated with said data cache of each one of said selected processors and responsive to its associated interlock variable detect means detecting said available value of said interlock variable in its associated storage means for conveying said available value of said interlock variable to its associated said one selected processor and writing, over said common bus, said busy value of said interlock variable to said storage means associated with processors of said plurality of processors other than said one selected processor, for updating the value of said interlock variable stored in said other storage means to said busy value.
Claim 2
Dependent Claim
420 words
An interlock variable acquisition system for use in a processing system of the type including a plurality of processors coupled to a common bus, selected processors of said plurality of processors having a data cache and being arranged to execute program instructions including at least one particular critical section requiring exclusive execution thereof, said interlock variable acquisition system being arranged to permit exclusive execution of said at least one particular critical section by each of said selected processors while limiting traffic on said common bus and comprising: storage means associated with said data cache of each one of said selected processors for storing an interlock variable related to said at least one particular critical section executable by said one selected processor, said interlock variable having either an available value indicating that no processor of said plurality of processors other than said one selected processor is currently executing said at least one particular critical section or a busy value indicating that another processor of said plurality of processors other than said one selected processor is currently executing said at least one particular critical section, said storage means being arranged to store a plurality of status bits associated with said interlock variable, said plurality of status bits including a first status bit having a first value when said interlock variable has a valid value and a second status bit having a second value when said interlock variable is shared by said other said storage means storing said interlock variable, said storage means being arranged to provide said common bus with the value of said interlock variable stored therein responsive to said first status bit having said first value; interlock variable detect means associated with said data cache of each one of said selected processors and responsive to a command instruction from its associated said one selected processor for detecting the value of said interlock variable in its associated storage means; and write means associated with said data cache of each one of said selected processors and responsive to its associated interlock variable detect means detecting said available value of said interlock variable in its associated storage means for conveying said available value of said interlock variable to its associated said one selected processor and writing, over said common bus, said busy value of said interlock variable to said storage means associated with processors of said plurality of processors other than said one selected processor, for updating the value of said interlock variable stored in said other storage means to said busy value.
Claim 3
Dependent Claim
66 words
A system as defined in claim 1 further comprising bus detecting means associated with each of said selected processors for detecting means associated with each of said selected processors for detecting the availability of said common bus responsive to its associated interlock variable detect means detecting said available value of said interlock variable in its associated storage means and responsive to said interlock variable being shared.
Claim 4
Dependent Claim
26 words
A system as defined in claim 2 wherein said write means are responsive to its associated bus detecting means detecting that said common bus is available.
Claim 5
Dependent Claim
44 words
A system as defined in claim 2 wherein said interlock variable detect means are arranged for detecting a change in the value of said interlock variable to said busy value while its associated bus detect means detects for the availability of said common bus.
Claim 6
Dependent Claim
52 words
A system as defined in claim 4 wherein said bus detecting means are arranged to terminate detecting the availability of said bus responsive to its associated interlock variable detect means detecting said busy value in its associated storage means prior to said bus detecting means detecting that said common bus is available.
Claim 7
Dependent Claim
53 words
A system as defined in claim 5 wherein said write means are arranged to convey said busy value to its associated selected processor responsive to said interlock variable detect means detecting said busy value in its associated storage means prior to its associated bus detecting means detecting that said common bus is available.
Claim 8
Dependent Claim
37 words
A system as defined in claim 1 wherein said write means are also arranged to write said busy value into its associated storage means when said write means conveys said available value to its associated selected processor.
Claim 9
Dependent Claim
84 words
A system as defined in claim 1 wherein said write means are responsive to a critical section complete instruction from its associated processor for writing said available value from its associated selected processor to its associated storage means and writing, over said common bus, said available value of said interlock variable from its associated selected processor to each said other storage means storing said interlock variable for updating the value of said interlock variable stored in said other storage means to said available value.
Claim 10
Dependent Claim
30 words
A system as defined in claim 1 wherein said interlock variable detect means are arranged to determine if its associated storage means contains a valid value of said interlock variable.
Claim 11
Dependent Claim
51 words
A system as defined in claim 9 further comprising bus detecting means associated with each of said selected processors for detecting the availability of said common bus responsive to its associated interlock variable detect means detecting that its associated storage means does not contain a valid value of said interlock variable.
Claim 12
Dependent Claim
81 words
A system as defined in claim 10 further comprising a read means associated with each said selected processor for reading information from said common bus, each said read means being coupled with its associated interlock variable detect means, with its associated bus detecting means, and with its associated write means, said read means being arranged to read the valid value of said interlock variable from said common bus when its associated bus detecting means detects that said common bus is available.
Claim 13
Dependent Claim
58 words
A system as defined in claim 11 further including a memory coupled to common bus and wherein each said storage means is arranged to provide said common bus with the value of said interlock variable stored therein if its value is a valid value and its value is more up to date than the value in said memory.
Claim 14
Dependent Claim
32 words
A system as defined in claim 11 wherein said write means are arranged to convey the valid value of said interlock variable to its associated storage means from its associated read means.
Claim 15
Dependent Claim
45 words
A system as defined in claim 13 wherein said interlock variable detect means are arranged to detect the value of said interlock variable in its associated storage means after said write means conveys the valid value of said interlock variable to its associated storage means.
Claim 16
Dependent Claim
72 words
A system as defined in claim 14 wherein said write means are responsive to said available value being detected by its associated interlock variable detect means for conveying said available value to its associated selected processor, said busy value to its associated storage means, and writing, over said common bus, said busy value to said other storage means storing said interlock variable for updating said other storage means to said busy value.
Claim 17
Dependent Claim
66 words
A system as defined in claim 15 wherein said write means are responsive to a critical section complete instruction from its associated selected processor for conveying said available value from its associated selected processor to its associated storage means and writing, over said common bus, said available value of said interlock variable from its associated selected processor to said other storage means storing said interlock variable.
Claim 18
Independent Claim
385 words
A method for use in a processing system of the type including a plurality of processors coupled to a common bus, selected processors of said plurality of processors having a data cache and being arranged to execute program instructions including at least one particular critical section requiring exclusive execution thereof, said method for permitting exclusive execution of said at least one particular critical section by each of said selected processors while limiting traffic on said common bus and comprising: providing a storage means associated with said data cache of each one of said selected processors; storing within said storage means an interlock variable related to said at least one particular critical section executable by said one selected processor, said interlock variable having either an available value indicating that no processor of said plurality of processor other than said one selected processor is currently executing said at least one particular critical section or a busy value indicating that another processor of said plurality of processors other than said one selected processor is currently executing said at least one particular critical section; storing within said storage means a plurality of status bits associated with said interlock variable, said plurality of status bits including a first status bit having a first value when said interlock variable has a valid value and a second status bit having a second value when said interlock variable is shared by said other said storage means storing said interlock variable, said storage means being arranged to provide said common bus with the value of said interlock variable stored therein responsive to said first status bit having said first value; detecting the value of said interlock variable in one of said storage means responsive to a command instruction from one of said selected processors; and conveying said available value of said interlock variable to said one selected processor and writing, over said common bus, said busy value of said interlock variable to said storage means associated with processors of said plurality of processors other than said selected processor issuing said command instruction, for updating the value of said interlock variable stored in said other storage means to said busy value in response to detecting said available value of said interlock variable in said storage means associated with said selected processor issuing said command instruction.
Claim 19
Independent Claim
385 words
A method for use in a processing system of the type including a plurality of processors coupled to a common bus, selected processors of said plurality of processors having a data cache and being arranged to execute program instructions including at least one particular critical section requiring exclusive execution thereof, said method for permitting exclusive execution of said at least one particular critical section by each of said selected processors while limiting traffic on said common bus and comprising: providing a storage means associated with said data cache of each one of said selected processors; storing within said storage means an interlock variable related to said at least one particular critical section executable by said one selected processor, said interlock variable having either an available value indicating that no processor of said plurality of processor other than said one selected processor is currently executing said at least one particular critical section or a busy value indicating that another processor of said plurality of processors other than said one selected processor is currently executing said at least one particular critical section; storing within said storage means a plurality of status bits associated with said interlock variable, said plurality of status bits including a first status bit having a first value when said interlock variable has a valid value and a second status bit having a second value when said interlock variable is shared by said other said storage means storing said interlock variable, said storage means being arranged to provide said common bus with the value of said interlock variable stored therein responsive to said first status bit having said first value; detecting the value of said interlock variable in one of said storage means responsive to a command instruction from one of said selected processors; and conveying said available value of said interlock variable to said one selected processor and writing, over said common bus, said busy value of said interlock variable to said storage means associated with processors of said plurality of processors other than said selected processor issuing said command instruction, for updating the value of said interlock variable stored in said other storage means to said busy value in response to detecting said available value of said interlock variable in said storage means associated with said selected processor issuing said command instruction.
Claim 20
Dependent Claim
54 words
A method as defined in claim 17 comprising the further steps of detecting whether said interlock variable is shared by said other storage means and detecting the availability of said common bus after detecting said available value of said interlock variable in said storage means associated with said selected processor issuing said command instruction.
Claim 21
Dependent Claim
28 words
A method as defined in claim 18 comprising the further step of repeatedly detecting the value of said interlock variable while detecting the available of said common bus.
Claim 22
Dependent Claim
60 words
A method as defined in claim 19 comprising the further step of terminating the detecting of the availability of said common bus upon detecting that said value of said interlock value stored in said storage means associated with said selected processor issuing said command signal has changed to said busy value prior to detecting that said common bus is available.
Claim 23
Dependent Claim
63 words
A method as defined in claim 20 comprising the further step of conveying said busy value to said selected processor issuing said command instruction responsive to detecting that said value of said interlock variable stored in said storage means associated with said selected processor issuing said command instruction has changed to said busy value prior to detecting that said common bus is available.
Claim 24
Dependent Claim
50 words
A method as defined in claim 17 comprising the further step of writing said busy value of said interlock variable into said storage means associated with said selected processor issuing said command instruction when conveying said available value of said interlock variable to said selected processor issuing said command instruction.
Claim 25
Dependent Claim
75 words
A method as defined in claim 17 comprising the further steps of writing from said selected processor issuing said command instruction said available value of said interlock variable to its associated storage means and, over said common bus, to each said other storage means storing said interlock variable for updating the value of said interlock variable to said available value responsive to said selected processor issuing said command instruction issuing a critical section complete instruction.
Claim 26
Dependent Claim
34 words
A method as defined in claim 17 comprising the further step of determining if the storage means associated with said selected processor issuing said command instruction contains a valid value of said interlock variable.
Claim 27
Dependent Claim
42 words
A method as define in claim 24 comprising the further step of detecting whether said common bus is available when said storage means associated with said selected processor issuing said command instruction does not contain a valid value of said interlock variable.
Claim 28
Dependent Claim
30 words
A system as defined in claim 25 further comprising the step of reading a valid value of said interlock variable from said common bus when said common bus is available.
Claim 29
Dependent Claim
38 words
A method as defined in claim 26 comprising the further step of writing the valid value of said interlock variable read from said common bus to said storage means associated with said selected processor issuing said command instruction.
Claim 30
Dependent Claim
48 words
A method as defined in claim 27 comprising the further step of detecting the value of said interlock variable contained within said storage means associated with said selected processor issuing said command instruction after writing said valid value read from said common bus to said associated storage means.
Claim 31
Dependent Claim
85 words
A method as defined in claim 28 comprising the further step of writing, over said common bus, said busy value to said other storage means storing said interlock variable and associated with each said selected processor other than said selected processor issuing said command instruction and writing said busy value into said storage means associated with said selected processor issuing said command instruction after detecting said available value of said interlock variable within said storage means associated with said selected processor issuing said command instruction.
Claim 32
Dependent Claim
29 words
A method as defined in claim 29 comprising the further step of conveying said available value to said selected processor issuing said command instruction from its associated storage means.
Claim 33
Dependent Claim
71 words
A method as defined in claim 30 comprising the further step of writing, over said common bus, said available value of said interlock variable from said selected processor issuing said command instruction to each said other storage means storing said interlock variable for updating the value of said interlock variable stored therein to said available value responsive to said selected processor issuing said command instruction issuing a critical section complete instruction.
Claim 34
Dependent Claim
31 words
A method as defined in claim 31 comprising the further step of conveying said available value from said selected processor issuing said critical section complete instruction to its associated storage means.
References Cited (Backward Citations)
US4249241A
Cited
US4394731A
Cited
US4574350A
Cited
US4901230A
Cited
US4775955A
Cited
US5129089A
Cited
US5050072A
Cited
US5043886A
Cited
US4965717A
Cited
US4965717B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-02-21 | 1997-08-23 | 1998-02-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-02-21 | 2001-08-23 | 2002-02-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-02-21 | 2005-08-23 | 2006-02-22 | $7700.00 | Window Closed / Lapsed |