Patent US3675217A successfully refreshed from Google Patents.
US3675217A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Sequence interlocking and priority apparatus
Assignee: International Business Machines Corp
•
Filing: 1969-12-23
•
Granted: 1972-07-04
•
Expires: 1989-12-23
Abstract
Abstract Described is a sequence interlock generator and priority apparatus combination suitable for use in a storage control system for a two-level storage, wherein the storage system includes a high-speed storage against which requests for data are processed and a slower, larger-capacity main storage. Requests can be received and serviced concurrently at a plurality of request ports in the system where they are buffered in request stacks. A tag storage serves as an index to the data currently resident in high-speed storage and a directory storage acts as an index to data currently in main storage. The sequence interlock generator interlocks requests in the plurality of request stacks to insure that requests to the same storage area are performed in proper sequence to insure data integrity. A sequence interlock vector is computed when the request first enters its request port and is appended to the request until the request is clear to request service. A request is received in terms of a logical address. The logical address is transformed into a plurality of physical addresses in high-speed storage. The physical addresses are used to address corresponding tags from the tag storage to determine the contents of the desired addresses in high-speed storage. The priority apparatus essentially splits the request into two priority determinations, one for priority to access the tag storage and the second for priority to access the data storage. The ideal situation is for tags and storage to be accessed concurrently. However, the invention makes provision for action to begin upon the tags if the tag storage can be accessed due to conflicts for accessing the addressable entity in highspeed storage. As a consequence of the invention, initiation of service of a given request is begun at the earliest possible time.
Inventors
- 👤 Philip S Dauber
- 👤 Russell J Robelen
- 👤 John R Wierzbiski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-22 20:38
CPC Classifications
G; G06; G06F; G06F13/00; G06F13/14; G06F13/16; G06F13/18; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0862
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
191 words
In a storage system including a plurality of input ports for receiving access requests from a plurality of requestors, request stacks for temporarily storing said requests while they are being serviced, high-speed storage means against which said requests are processed, tag storage means serving as an index to the information in said high-speed storage, main storage means containing system information, priority contention means for allowing requests to contend for access to tag and high-speed storages, decision means for determining whether said desired information is resident in said high-speed storage means, and interstorage transfer means for transferring said data from said main storage to said high-speed storage if said desired data is not resident in high-speed storage, the improvement comprising: sequence interlock generating means connected to said inputs and to said request stacks and including means for comparing each incoming request with prior requests stored in said request stacks and with any concurrent request from any other requestor and means for calculating, a single time only for each incoming request, a sequence interlock vector identifying with other requests in said request stacks must be serviced before an incoming request can be serviced.
Claim 2
Dependent Claim
191 words
In a storage system including a plurality of input ports for receiving access requests from a plurality of requestors, request stacks for temporarily storing said requests while they are being serviced, high-speed storage means against which said requests are processed, tag storage means serving as an index to the information in said high-speed storage, main storage means containing system information, priority contention means for allowing requests to contend for access to tag and high-speed storages, decision means for determining whether said desired information is resident in said high-speed storage means, and interstorage transfer means for transferring said data from said main storage to said high-speed storage if said desired data is not resident in high-speed storage, the improvement comprising: sequence interlock generating means connected to said inputs and to said request stacks and including means for comparing each incoming request with prior requests stored in said request stacks and with any concurrent request from any other requestor and means for calculating, a single time only for each incoming request, a sequence interlock vector identifying with other requests in said request stacks must be serviced before an incoming request can be serviced.
Claim 3
Dependent Claim
112 words
The combination of claim 1, further including means for concurrently feeding an incoming request into an empty request stack level in the respective request stacks in said request ports; means for appending each said sequence interlock vector to its request; means for setting a sequence interlock bit in each incoming request whose sequence interlock vector is not zero; means for periodically resetting to zero individual bits in the sequence interlock vector for each individual request as individual requests to which said individual requests are interlocked are serviced; and means for allowing an interlocked request to contend for service when all of the bits in its interlock vector have been reset to zero.
Claim 4
Dependent Claim
22 words
accessing, in response to said second request, said storage entities other than the one which said first request has priority to access;
Claim 5
Dependent Claim
22 words
accessing, in response to said second request, said storage entities other than the one which said first request has priority to access;
Claim 6
Dependent Claim
21 words
setting a mark indicating that priority has been given to said second request to access said storage entities in step (2);
Claim 7
Dependent Claim
21 words
setting a mark indicating that priority has been given to said second request to access said storage entities in step (2);
Claim 8
Dependent Claim
128 words
The combination of claim 1 comprising: a plurality of registers for holding said plurality of incoming requests; said comparing means includes a plurality of comparators connected to said plurality of registers and to each level in said plurality of request stacks for comparing the address portions of said incoming requests to the address portions of each of said requests in each of said levels of any of said plurality of request stacks; means responsive to an equal comparison in any of said comparators for setting a bit in said interlock vector for said request, said bit corresponding to the request stack designation and request stack level to which said request is interlocked; and means responsive to any comparison for setting a sequence interlock bit in said incoming request.
Claim 9
Dependent Claim
225 words
In a storage system including a plurality of input ports for receiving requests from a plurality of requestors, multi-level request stacks for temporarily storing said requests while they are being serviced each level of said request stacks having associated therewith an interlock vector including a settable sequence interlock indicator, high-speed storage means against which said requests are processed, tag storage means serving as an index to the information in said high-speed storage, main storage means containing system information, priority contention means for allowing requests to contend for access to tag and high-speed storages, decision means for determining whether said desired information is resident in said high-speed storage means, interstorage transfer means for transferring said data from said main storage to said high-speed storage if said desired data is not resident in high-speed storage, and sequence interlock generating means, the improvement comprising: means for providing a signal if any of said plurality of request stacks to which said incoming requests are destined are empty; means responsive to said signal for gating said incoming requests destined for said empty request stacks directly to said priority contention means and to said sequence interlock generator; testing means in said decision means for providing a signal if said sequence interlock indicator is set; and means responsive to said last-named signal for invalidating requests gated directly to said priority contention means.
Claim 10
Dependent Claim
225 words
In a storage system including a plurality of input ports for receiving requests from a plurality of requestors, multi-level request stacks for temporarily storing said requests while they are being serviced each level of said request stacks having associated therewith an interlock vector including a settable sequence interlock indicator, high-speed storage means against which said requests are processed, tag storage means serving as an index to the information in said high-speed storage, main storage means containing system information, priority contention means for allowing requests to contend for access to tag and high-speed storages, decision means for determining whether said desired information is resident in said high-speed storage means, interstorage transfer means for transferring said data from said main storage to said high-speed storage if said desired data is not resident in high-speed storage, and sequence interlock generating means, the improvement comprising: means for providing a signal if any of said plurality of request stacks to which said incoming requests are destined are empty; means responsive to said signal for gating said incoming requests destined for said empty request stacks directly to said priority contention means and to said sequence interlock generator; testing means in said decision means for providing a signal if said sequence interlock indicator is set; and means responsive to said last-named signal for invalidating requests gated directly to said priority contention means.
Claim 11
Dependent Claim
15 words
and causing said second request to re-contend for priority to access said one storage entity.
Claim 12
Dependent Claim
15 words
and causing said second request to re-contend for priority to access said one storage entity.
Claim 13
Dependent Claim
97 words
The combination of claim 4 further including: testing means providing a signal if any non-empty ones of said plurality of request stacks has no request available for priority contention; means responsive to said signal for gating said requests destined for said any of said non-empty ones of said plurality of said request stacks directly to said priority contention means, to said sequence interlock generator and to a level in said request stack; and testing means in said decision area for invalidating any request gated directly to said priority contention means if said sequence interlock bit is on.
Claim 14
Dependent Claim
192 words
In a storage system including a plurality of input ports for receiving requests from a plurality of requestors, request stacks for temporarily storing said requests while they are being serviced, high-speed storage means against which said requests are processed, tag storage means serving as an index to the information in said high-speed storage, main storage means containing system information, priority contention means for allowing requests to contend for access to tag and high speed storages, access conflict resolution means, decision means for determining whether said desired information is resident in said high-speed storage means, and interstorage transfer means for transferring said data from said main storage to said high-speed storage if said desired data is not resident in high-speed storage and sequence interlocking means, an improvement in said plurality of priority contention means comprising: storage register means for receiving a request for priority contention; testing means for testing said conflict resolution means to determine whether a cOnflict exists with a higher priority port; means for accessing said tag storage and high-speed storage if no conflict exists; and means for resetting said request in said storage register in preparation for a subsequent request.
Claim 15
Dependent Claim
192 words
In a storage system including a plurality of input ports for receiving requests from a plurality of requestors, request stacks for temporarily storing said requests while they are being serviced, high-speed storage means against which said requests are processed, tag storage means serving as an index to the information in said high-speed storage, main storage means containing system information, priority contention means for allowing requests to contend for access to tag and high speed storages, access conflict resolution means, decision means for determining whether said desired information is resident in said high-speed storage means, and interstorage transfer means for transferring said data from said main storage to said high-speed storage if said desired data is not resident in high-speed storage and sequence interlocking means, an improvement in said plurality of priority contention means comprising: storage register means for receiving a request for priority contention; testing means for testing said conflict resolution means to determine whether a cOnflict exists with a higher priority port; means for accessing said tag storage and high-speed storage if no conflict exists; and means for resetting said request in said storage register in preparation for a subsequent request.
Claim 16
Dependent Claim
57 words
The combination of claim 6 further including means for accessing the tag storage only if a conflict in the data storage access has occurred; means for setting a marker in said storage register indicating that tag storage has been accessed; and means for enabling the request in said storage register for contending again for high-speed storage priority.
Claim 17
Dependent Claim
57 words
The combination of claim 7 further including means for accessing the high-speed storage only if a conflict in the data storage access has occurred; means for setting a marker in said storage register indicating that high-speed storage has been accessed; and means for enabling the request in said storage register for contending again for tag storage priority.
Claim 18
Independent Claim
83 words
The method, carried out in a data processing system, of accessing first and second storage entities wherein plural access requests, of different priorities, are allowed to simultaneously contend for access to both of said entities, comprising the steps of: determining relative to each request whether a higher priority request exists for accessing both of said storage entities; and, in response to each request, accessing of said storage entities if the determination from said prior step is that no such higher priority request exists.
Claim 19
Independent Claim
83 words
The method, carried out in a data processing system, of accessing first and second storage entities wherein plural access requests, of different priorities, are allowed to simultaneously contend for access to both of said entities, comprising the steps of: determining relative to each request whether a higher priority request exists for accessing both of said storage entities; and, in response to each request, accessing of said storage entities if the determination from said prior step is that no such higher priority request exists.
Claim 20
Independent Claim
40 words
The method, carried out in a data processing system, of accessing plural storage entities in said system, wherein plural access requests of different priorities, simultaneously contend for access to one or more of said storage entities, comprising the steps of:
Claim 21
Independent Claim
40 words
The method, carried out in a data processing system, of accessing plural storage entities in said system, wherein plural access requests of different priorities, simultaneously contend for access to one or more of said storage entities, comprising the steps of:
Claim 22
Dependent Claim
41 words
The method of claim 10 wherein said storage entities comprise a first high-speed storage device having a multiplicity of addressable storage locations, and a second tag storage containing entries serving as indicies to the contents of said first high-speed storage device.
References Cited (Backward Citations)
US3310785A
Cited
US3377579A
Cited
US3373408A
Cited
US3395394A
Cited
US3444525A
Cited
US3434111A
Cited
US3456244A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1975-07-04 | 1976-01-03 | 1976-07-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1979-07-04 | 1980-01-03 | 1980-07-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1983-07-04 | 1984-01-03 | 1984-07-04 | $7700.00 | Window Closed / Lapsed |