EP0352050A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Single-keyed indexed file for TP queue repository
Assignee: Digital Equipment Corp
•
Filing: 1989-07-17
•
Granted: —
•
Expires: 2009-07-17
Abstract
Abstract A task queue is structured as a single-keyed indexed file in which the key has a most significant portion indicating a priority level and a less significant portion that is ordered with the loading of the tasks into the queue. For any given task record in the queue, the less significant portion of the key is determinable from a respective task identifier. Preferably the less significant portion of the key is a "time stamp" including the current date when the task was created and a representation of the data processor's internal 24 hour time clock, and a task identification number is formed by appending a node number to the time stamp in the event that the system has multiple processors capable of creating different tasks at the same time. This format of the single key causes an internal ordering of the records in the queue that is sequential with respect to the less significant portion of the key within blocks of records having the same priority. Therefore, due to the relationship between the key and the task identification number for each task record in the queue, it is possible to quickly search for the record having a requested task identification number. Conventional memory management facilities for accessing key-indexed files can be used for searching the queue. In this case the queue is searched by random or "key next" access to repeatedly step through the possible priority levels until a record having a matching key is found or the end of file is reached. When a record having a matching key is found, the requested task identification number is compared to the identification field of the record. If there is a match, the desired record has been found. If not, then searching continues by sequential access until there is a match of the identification numbers or until the keys no longer match.
Inventors
- 👤 James P. Emmond
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-28 01:17
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/4881; G06F16/00; G06F16/30; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
113 words
A memory device in a data processing system, said memory device holding a queue of data, said queue comprising an ordered set of a multiplicity of records of said data, each of said records including an identifier field holding a respective identifier different from the respective identifiers in the identifier fields of said other records, each of said records also including a key field holding a respective key value having a respective most significant portion indicating a priority level and a less significant portion that is a predetermined function of the respective identifier in the record, the order of said records in said queue being specified by the ordering of said key values.
Claim 2
Dependent Claim
113 words
A memory device in a data processing system, said memory device holding a queue of data, said queue comprising an ordered set of a multiplicity of records of said data, each of said records including an identifier field holding a respective identifier different from the respective identifiers in the identifier fields of said other records, each of said records also including a key field holding a respective key value having a respective most significant portion indicating a priority level and a less significant portion that is a predetermined function of the respective identifier in the record, the order of said records in said queue being specified by the ordering of said key values.
Claim 3
Dependent Claim
28 words
The memory device as claimed in claim 1, wherein said identifier field in each record includes a subfield holding the less significant portion of the respective key value.
Claim 4
Dependent Claim
24 words
The memory device as claimed in claim 1, wherein said identifier held in the identifier field of each record indicates a respective time value.
Claim 5
Dependent Claim
23 words
The memory device as claimed in claim 3, wherein said time value includes a date, and a time in a twenty-four hour format.
Claim 6
Dependent Claim
24 words
The memory device as claimed in claim 3, wherein said identifier further includes an identification number indicating a processor in said data processing system.
Claim 7
Dependent Claim
24 words
The memory device as claimed in claim 1, wherein said records include different records having the same key value in their respective key fields.
Claim 8
Independent Claim
197 words
A method of operating a data processor in a data processing system to search a queue for a data record having a requested identifier, said queue being held in a memory device in said data processing system, said queue comprising an ordered set of a multiplicity of records of data stored in said memory device, each of said records including an identifier field holding a respective identifier different from the respective identifiers in the identifier fields of said other records, each of said records also including a key field holding a respective key value having a respective most significant portion indicating a priority level and a less significant portion that is a predetermined function of the respective identifier in the record, the order of said records in said queue being specified by the ordering of said key values, said method comprising the steps of: a) searching said queue for records having in their respective key fields a less significant portion that is said predetermined function of said requested identifier; and b) determined whether the identifiers in the respective identifier fields of the records found by said searching in step a) are the same as the requested identifier.
Claim 9
Independent Claim
197 words
A method of operating a data processor in a data processing system to search a queue for a data record having a requested identifier, said queue being held in a memory device in said data processing system, said queue comprising an ordered set of a multiplicity of records of data stored in said memory device, each of said records including an identifier field holding a respective identifier different from the respective identifiers in the identifier fields of said other records, each of said records also including a key field holding a respective key value having a respective most significant portion indicating a priority level and a less significant portion that is a predetermined function of the respective identifier in the record, the order of said records in said queue being specified by the ordering of said key values, said method comprising the steps of: a) searching said queue for records having in their respective key fields a less significant portion that is said predetermined function of said requested identifier; and b) determined whether the identifiers in the respective identifier fields of the records found by said searching in step a) are the same as the requested identifier.
Claim 10
Dependent Claim
51 words
The method as claimed in claim 7, wherein said step a) of searching includes forming a requested key having a less significant portion that is said predetermined function of said requested identifier, and randomly accessing said queue in response to said requested key to obtain a next record from said queue.
Claim 11
Dependent Claim
72 words
The method as claimed in claim 8, wherein said random accessing is performed by a software service that returns either the first record in said queue having a key value matching the requested key, or if said queue does not have a record which has a key value matching the requested key then the next record in the queue next to where a record having a matching key value would have been.
Claim 12
Dependent Claim
70 words
The method as claimed in claim 9, wherein said step a) of searching includes comparing the less significant portion of said requested key to the less significant portion of the key value in the key field of said next record to determine whether said next record is one of said records having in their respective key fields a less significant portion that is said predetermined function of said requested identifier.
Claim 13
Dependent Claim
117 words
The method as claimed in claim 10, wherein said step a) of searching further includes the step of changing the most significant portion of the requested key by one level of priority and again randomly accessing said queue in response to said requested key when said comparing indicates that (1) the less significant portion of said requested key does not match the less significant portion of the key value in the key field of said next record and (2) said next record should have a most significant portion of its key value in its key field that is the same as the most significant portion of the requested key prior to said changing of the requested key.
Claim 14
Dependent Claim
121 words
The method as claimed in claim 10, wherein said step a) of searching further includes the step of changing the requested key by setting the most significant portion of the requested key to the most significant portion of the key value in the key field of said next record when said comparing indicates that (1) the less significant portion of said requested key does not match the less significant portion of the key value in the key field of said next record and (2) said next record should have a most significant portion of its key value in its key field that is different from the most significant portion of the requested key prior to said changing of the requested key.
Claim 15
Dependent Claim
89 words
The method as claimed in claim 7, wherein said step a) of searching is initially performed by random access of said queue in response to a requested key having a portion including a less significant portion that is said predetermined function of said requested identifier, and also by sequential access of said queue to obtain sequentially the next record in said queue when said step b) of determining determines that the requested identifier is different from the identifier in the identifier field of the record having the matching key.
Claim 16
Dependent Claim
150 words
The method as claimed in claim 13, wherein said step a) of searching further comprises comparing the less significant portion of the key value in the key field of said next record to the less significant portion that is said predefined function of said requested identifier, and when the less significant portion of the key value in the key field of said next record is different from the less significant portion that is said predetermined function of said requested identifier, then changing the most significant portion of the requested key by one level of priority and again randomly accessing said queue in response to said requested key when said comparing indicates that said next record should have a most significant portion of its key value in its key field that is the same as the most significant portion of the requested key prior to said changing of the requested key.
Claim 17
Dependent Claim
159 words
The method as claimed in claim 13, wherein said step a) of searching further comprises comparing the less significant portion of the key value in the key field of said next record to the less significant portion that is said predefined function of said requested identifier, and when the less significant portion of the key value in the key field of said next record is different from the less significant portion that is said predetermined function of said requested identifier, then changing the most significant portion of the requested key by setting the most significant portion of the requested key to the most significant portion of the key value in the key field of said next record when said comparing indicates that said next record should have a most significant portion of its key value in its key field that is different from the most significant portion of the requested key prior to said changing of the requested key.
Claim 18
Dependent Claim
239 words
A data processing system comprising, in combination; a nonvolatile memory device holding a task queue, said queue comprising an ordered set of a multiplicity of records of task data held in said memory device, each of said records including an identifier field holding a respective identifier different from the respective identifiers in the identifier fields of said other records, each of said records also including a key field holding a respective key value having a respective most significant portion indicating a priority level and a less significant portion that is a predetermined function of the respective identifier in the record, the order of said records in said queue being specified by the ordering of said key values; application processor means for performing data processing tasks using said task data; queued task initiator means for accessing said queue for task data for the next uninitiated task in the queue, and initiating that task by invoking said application processor means; and task queue searching means for searching said task queue for a record having a requested identifier in its identifier field, said task queue searching means including means for finding records in said task queue having in their key fields a less significant portion that is said predetermined function of said requested identifier, and means for determining whether a record found by said means for finding has an identifier in its identifier field that is the same as the requested identifier.
Claim 19
Dependent Claim
239 words
A data processing system comprising, in combination; a nonvolatile memory device holding a task queue, said queue comprising an ordered set of a multiplicity of records of task data held in said memory device, each of said records including an identifier field holding a respective identifier different from the respective identifiers in the identifier fields of said other records, each of said records also including a key field holding a respective key value having a respective most significant portion indicating a priority level and a less significant portion that is a predetermined function of the respective identifier in the record, the order of said records in said queue being specified by the ordering of said key values; application processor means for performing data processing tasks using said task data; queued task initiator means for accessing said queue for task data for the next uninitiated task in the queue, and initiating that task by invoking said application processor means; and task queue searching means for searching said task queue for a record having a requested identifier in its identifier field, said task queue searching means including means for finding records in said task queue having in their key fields a less significant portion that is said predetermined function of said requested identifier, and means for determining whether a record found by said means for finding has an identifier in its identifier field that is the same as the requested identifier.
Claim 20
Dependent Claim
29 words
The data processing system as claimed in claim 16, wherein said identifier field in each record includes a subfield holding the less significant portion of the respective key value.
Claim 21
Dependent Claim
22 words
The data processing system as claimed in claim 16, wherein said identifier includes a date, and a time in twenty-four hour format
Claim 22
Dependent Claim
107 words
The data processing system as claimed in claim 16, wherein said means for finding records includes means for forming a requested key having a most significant portion and a less significant portion that is said predetermined function of the requested identifier, means for randomly accessing said queue in response to said requested key to find a next record in the queue, and means for sequentially accessing said queue to find a next record in said queue when said means for determining determines that a next record found by said means for randomly accessing has an identifier in its identifier field that is different from the requested identifier.
Claim 23
Dependent Claim
107 words
The data processing system as claimed in claim 19, wherein said means for finding records further includes means for comparing the less significant portion of the key value of each next record found in the queue with said predetermined function of the requested identifier, and in response to said comparing indicating that the less significant portion of the key value of said each next record is different from said predetermined function of the requested identifier, either setting the most significant portion of the requested key to the priority value in the priority field of said each record, or changing the most significant portion of the requested key.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.