US3676860A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Interactive tie-breaking system
Assignee: International Business Machines Corp
•
Filing: 1970-12-28
•
Granted: 1972-07-11
•
Expires: 1990-12-28
Abstract
Abstract A multiple processor tie-breaking method separately and asynchronously used by each of any number of plural processors contending for a serially reusable resource (SRR). The contending processors independently and asynchronously interact in their use of the tie-breaking method to choose among themselves which processor will get the SRR. The method uses a common group of registers (or fields) accessible to all contending processors. The method permits uncoordinated fetching and storing of bits in those registers. Only one bit at a time need be fetched or changed by any processor. In fact, the plural independent processors can concurrently fetch or store the same bit in the common group of registers without affecting the reliability of the method. The priorities among processors dynamically change with every contention in a manner which gives each processor an equitable and equal chance of getting the SRR.
Inventors
- 👤 William W Collier
- 👤 Ronald M Smith
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-22 16:49
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/52; G06F13/00; G06F13/14; G06F13/16; G06F13/18
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
317 words
A method individually and asynchronously used by each of multiple processors for resolving contentions among them for a serially reusable resource, comprising the steps of setting a request bit for each processor contending for said resource, each request bit being assigned to a different processor, setting a wait bit for each contending processor which finds the resource not currently available, each wait bit being assigned to a different processor, reading a priority indicator to identify a specified request bit and a specified wait bit for a specified processor, sensing the set or unset state of the request bits and wait bits in a predetermined order to determine whether other processors are contending, another processor being contending if its request bit is set, said sensing step including: high-priority sensing whether any request bit is in set state within the range of bits from said specified request bit to a particular request bit assigned to a requesting processor in said predetermined order to determine whether a higher priority processor is requesting said resource, low-priority sensing the set state of both the request bit and wait bit for any processor within the range of bits from said particular request bit to said specified request bit in said predetermined order to determine whether any lower priority processor has requested priority but is not waiting, transferring control of said resource to a contending processor when its execution of said sensing steps determines it to be a successful contender, testing every corresponding request bit and wait bit except for those of the successful contender, and waiting until both bits become set if any other contending processor has its request bit set and its wait bit unset, using said resource by said successful contender, and releasing said resource by said successful contender when its use is completed, whereby the other contending processors continue independently to use this method to determine the next successful contender.
Claim 2
Independent Claim
317 words
A method individually and asynchronously used by each of multiple processors for resolving contentions among them for a serially reusable resource, comprising the steps of setting a request bit for each processor contending for said resource, each request bit being assigned to a different processor, setting a wait bit for each contending processor which finds the resource not currently available, each wait bit being assigned to a different processor, reading a priority indicator to identify a specified request bit and a specified wait bit for a specified processor, sensing the set or unset state of the request bits and wait bits in a predetermined order to determine whether other processors are contending, another processor being contending if its request bit is set, said sensing step including: high-priority sensing whether any request bit is in set state within the range of bits from said specified request bit to a particular request bit assigned to a requesting processor in said predetermined order to determine whether a higher priority processor is requesting said resource, low-priority sensing the set state of both the request bit and wait bit for any processor within the range of bits from said particular request bit to said specified request bit in said predetermined order to determine whether any lower priority processor has requested priority but is not waiting, transferring control of said resource to a contending processor when its execution of said sensing steps determines it to be a successful contender, testing every corresponding request bit and wait bit except for those of the successful contender, and waiting until both bits become set if any other contending processor has its request bit set and its wait bit unset, using said resource by said successful contender, and releasing said resource by said successful contender when its use is completed, whereby the other contending processors continue independently to use this method to determine the next successful contender.
Claim 3
Dependent Claim
121 words
A method for individually and asynchronously resolving contentions as defined in claim 1 in which a new requesting processor enters the contention, and said new requesting processor performs the steps of detecting a lock bit set by the successful contender to indicate that all currently unsuccessful contenders should set their wait bit, setting the wait bit of said new requesting processor, repeatedly examining the setting of said lock bit until it is detected to have been reset by said successful contender, repeating said high-priority sensing step until no other higher-priority contenders are found to exist, resetting said wait bit of said new requesting processor, and repeating said high-priority sensing step to determine whether any higher-priority contender has its request bit set.
Claim 4
Dependent Claim
69 words
A method for individually and asynchronously resolving contentions as defined in claim 1 in which a new requesting processor enters the contention, including the steps of setting a lock bit by said successful contender, testing the state of said lock bit by said new requesting processor, and setting a wait bit for said new requesting processor upon said testing step determining said lock bit is in its set state.
Claim 5
Dependent Claim
81 words
A method for individually and asynchronously resolving contentions as defined in claim 1 in which there is another contending processor performing the steps including entering said high-priority sensing step to determine whether the request bit is in set state for either the successful contender or a further contending processor, said detecting step being entered by said another contending processor, and whereby said another contending processor will set its wait bit pending completion of use of said resource by said successful contender.
Claim 6
Dependent Claim
97 words
A method for resolving contentions among multiple processors as defined in claim 1 including the steps of changing the setting of said priority indicator after said testing step finds the wait bit set for all other contending processors, the indicator having any initial arbitrary integer value in the range from ''''one'''' through N, in which N is equal to the number of processors, and stepping the current value of the priority indicator to the next higher integer value, unless the current value is N in which case the current value is replaced with the value of ''''one''''.
Claim 7
Dependent Claim
113 words
A method for resolving contentions among multiple processors as defined in claim 1 including the steps of changing the setting of said priority indicator after said testing step finds the wait bit set for all other contending processors, the indicator having any initial arbitrary integer value in the range from ''''one'''' through N, in which N is equal to the number of processors, and modifying the current value of the priority indicator by adding to it a value P, and subtracting N from their sum when the sum is greater than or equal to N, and adding ''''one'''' to the result, in which P + 1 is any integer mutually prime to N.
Claim 8
Independent Claim
198 words
A method individually and asynchronously used by each of two processors for resolving contentions between a given processor and another processor for a serially reusable resource, comprising the steps of setting the request bit for the given processor, sensing the request bit of the other processor and, upon finding it to be unset, making use of the serially reusable resource, sensing the request bit of the other processor, and, upon finding it to be set, setting the wait bit for the given processor, sensing the request bit of the other processor and, upon finding it to be unset, making use of the serially reusable resource, sensing the wait bit of the other processor, and, upon finding it to be unset, repeating the previous step, sensing the current value of a tie-breaker bit and continuing to sense the value of the tie-breaker bit for so long as the value of the tie-breaker corresponds to the other processor, using the serially reusable resource, setting the wait bit for the given processor to the reset state, setting the request bit for the given processor to the reset state, and setting the value of the tie-breaker to correspond to the other processor.
Claim 9
Independent Claim
198 words
A method individually and asynchronously used by each of two processors for resolving contentions between a given processor and another processor for a serially reusable resource, comprising the steps of setting the request bit for the given processor, sensing the request bit of the other processor and, upon finding it to be unset, making use of the serially reusable resource, sensing the request bit of the other processor, and, upon finding it to be set, setting the wait bit for the given processor, sensing the request bit of the other processor and, upon finding it to be unset, making use of the serially reusable resource, sensing the wait bit of the other processor, and, upon finding it to be unset, repeating the previous step, sensing the current value of a tie-breaker bit and continuing to sense the value of the tie-breaker bit for so long as the value of the tie-breaker corresponds to the other processor, using the serially reusable resource, setting the wait bit for the given processor to the reset state, setting the request bit for the given processor to the reset state, and setting the value of the tie-breaker to correspond to the other processor.
Claim 10
Dependent Claim
167 words
A method as defined in claim 1 permitting the successful contender to perform certain control functions in parallel with usage of the serially reusable resource, comprising the steps of setting a lock bit to its set state, testing every corresponding request bit and wait bit except for those of the successful contender, and waiting until both bits become set if any other contending processor has its request bit set and its wait bit unset, setting the lock bit to the reset state, setting a synchronization bit to its set state, terminating the independent performance of any furtheR function by a portion of the successful contender which performed the above steps, the preceding steps being executed in parallel with the following steps, using the serially reusable resource, sensing the state of the synchronization bit, such sensing to continue until the synchronization bit is determined to be set, setting the synchronization bit to its reset state, and setting the request bit for the successful contender to its reset state.
Claim 11
Dependent Claim
164 words
A method as defined in claim 1 for fixing the sequence in which subsequent contender processors will use a serially reusable resource while the successful contender is using the serially usable resource, in which a subsequent contender uses the steps of completing execution of said testing step, sensing an initial bit position in a queue field until it becomes reset, setting said initial bit position to its set state to provide an indicator bit that represents said subsequent processor''s position in the queue field, setting the request bit for said subsequent contender to its reset state to indicate it is no longer waiting to enter the queue field, moving said indicator bit to successively higher bit position in said queue field found not currently used as an indicator for another contender, until said indicator bit is located in the highest bit position in said queue field, using and serially reusable resource by said subsequent contender, and setting said indicator bit to its reset state.
Claim 12
Dependent Claim
126 words
A method as defined in claim 9 in which said moving step includes the steps of setting an index to correspond to the first bit position of the queue field, stepping the index to correspond to the next bit position in sequence in the queue field, sensing said next bit position in the queue field until it becomes reset, setting said next bit to its set state to represent said indicator bit, resetting the bit position prior to said indicator bit, detecting the value of the index to determine if it has been stepped to the last bit position in the queue field, and repeating the preceding five steps until said detecting step finds said indicator bit at said last bit position in said queue field.
References Cited (Backward Citations)
US3214739A
Cited
US3303474A
Cited
US3333252A
Cited
US3469239A
Cited
US3445819A
Cited
US3480914A
Cited
US3445822A
Cited
US3528062A
Cited
US3599162A
Cited
US3603935A
Cited
US3573856A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1975-07-11 | 1976-01-10 | 1976-07-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1979-07-11 | 1980-01-10 | 1980-07-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1983-07-11 | 1984-01-10 | 1984-07-11 | $7700.00 | Window Closed / Lapsed |