US5644786A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for scheduling the execution of disk I/O operations
Assignee: Taiwan Semiconductor Manufacturing Co TSMC Ltd
•
Filing: 1990-11-08
•
Granted: 1997-07-01
•
Expires: 2010-11-08
Abstract
Abstract A procedure for scheduling multiple process requests for read/write access to a disk memory device within a computer system. The procedure considers disk characteristics, such as the number of sectors per track, the number of tracks per cylinder, speed of disk rotation and disk controller queuing capability in determining the optimal order for executing process requests. Process requests are placed in packets within an execution queue, each packet including up to a predetermined maximum number of requests. Within the packets, the process requests are sorted in ascending/descending order by the cylinder number to which the requests desire access, while within each cylinder the requests are placed in next-closest-in-time sequence.
Inventors
- 👤 Michael J. Gallagher
- 👤 Ray M. Jantz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 18:53
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F13/00; G06F13/10; G06F13/12; G06F13/124; G06F13/126; G06F3/0602; G06F3/061; G06F3/0613; G06F3/0628; G06F3/0655; G06F3/0659; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0674; G06F3/0676
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
181 words
In a computer system including a multiple-platter disk memory device, said disk memory device being divided into a plurality of disk cylinders comprising concentric rings occupying the same position in each platter wherein each ring is further divided into a plurality of sectors which define angularly spaced recording areas and having a disk access time, rotational latency, rotational distance, and function return time associated therewith, a method for scheduling process requests for access to said disk memory device, the steps comprising: sorting said process requests in ascending/descending order by the disk cylinder numbers to which the requests desire access; sorting said process requests within each cylinder in next-closest-in-time sequence; wherein said step of sorting said process requests within a cylinder further comprises the steps of: determining the rotational latencies between each pairing of process requests desiring access to said cylinder; comparing said rotational latencies to the function return time of said disk device; and sorting said process requests desiring access to said cylinder such that successive process requests are separated by the minimum rotational latency which exceeds said function return time.
Claim 2
Dependent Claim
181 words
In a computer system including a multiple-platter disk memory device, said disk memory device being divided into a plurality of disk cylinders comprising concentric rings occupying the same position in each platter wherein each ring is further divided into a plurality of sectors which define angularly spaced recording areas and having a disk access time, rotational latency, rotational distance, and function return time associated therewith, a method for scheduling process requests for access to said disk memory device, the steps comprising: sorting said process requests in ascending/descending order by the disk cylinder numbers to which the requests desire access; sorting said process requests within each cylinder in next-closest-in-time sequence; wherein said step of sorting said process requests within a cylinder further comprises the steps of: determining the rotational latencies between each pairing of process requests desiring access to said cylinder; comparing said rotational latencies to the function return time of said disk device; and sorting said process requests desiring access to said cylinder such that successive process requests are separated by the minimum rotational latency which exceeds said function return time.
Claim 3
Dependent Claim
34 words
The method according to claim 1, further including the step of concatenating process requests desiring access to contiguous sectors within the same cylinder, said concatenated process requests being scheduled as a single process request.
Claim 4
Dependent Claim
152 words
In a computer system including a multiple-platter disk memory device, said disk memory device being divided into a plurality of disk cylinders comprising concentric rings occupying the same position in each platter wherein each ring is further divided into a plurality of sectors which define angularly spaced recording areas and having a disk access time, rotational latency, rotational distance, and function return time associated therewith, a method for scheduling process requests for access to said disk memory device, the steps comprising: sorting said process requests in ascending order by the sector number to which the requests desire access; grouping said sorted process requests into packets of requests, each of said packets including a predetermined maximum number of requests; sorting said process requests within each packet in ascending/descending order by the cylinder number to which the requests desire access; and sorting said process requests within each cylinder within a packet in next-closest-in-time sequence.
Claim 5
Dependent Claim
152 words
In a computer system including a multiple-platter disk memory device, said disk memory device being divided into a plurality of disk cylinders comprising concentric rings occupying the same position in each platter wherein each ring is further divided into a plurality of sectors which define angularly spaced recording areas and having a disk access time, rotational latency, rotational distance, and function return time associated therewith, a method for scheduling process requests for access to said disk memory device, the steps comprising: sorting said process requests in ascending order by the sector number to which the requests desire access; grouping said sorted process requests into packets of requests, each of said packets including a predetermined maximum number of requests; sorting said process requests within each packet in ascending/descending order by the cylinder number to which the requests desire access; and sorting said process requests within each cylinder within a packet in next-closest-in-time sequence.
Claim 6
Dependent Claim
32 words
The method according to claim 3, wherein: each of said process requests has a priority level associated therewith; and each one of said packets includes process requests having the same priority levels.
Claim 7
Dependent Claim
51 words
The method according to claim 4, further including the step of concatenating process requests desiring access to contiguous sectors within the same cylinder, said concatenated process requests being sorted and grouped as a single process request having an associated priority level equivalent to the highest priority level of the concatenated requests.
Claim 8
Dependent Claim
85 words
The method according to claim 3, wherein said step of sorting process requests within a cylinder within a packet comprises the steps of: determining the rotational latencies between each pairing of process requests within the packet desiring access to said cylinder; comparing said rotational latencies to the function return time of said disk device; and sorting said process requests within the packet desiring access to said cylinder such that successive process requests are separated by the minimum rotational latency which exceeds said function return time.
Claim 9
Dependent Claim
163 words
In a computer system including a multiple-platter disk memory device, said disk memory device being divided into a plurality of disk cylinders comprising concentric rings occupying the same position in each platter wherein each ring is further divided into a plurality of sectors which define angularly spaced recording areas and having a disk access time, rotational latency, rotational distance, and function return time associated therewith, a method for scheduling process requests for access to said disk memory device, the steps comprising: generating a first queue containing said process requests sorted in ascending order by the sector number to which the requests desire access; and generating a second queue wherein: said sorted requests are grouped into packets, each of said packets including a predetermined maximum number of requests; said process requests in each of said packets are sorted in ascending/descending order by the disk cylinder numbers to which the requests desire access; and said process requests within each cylinder are sorted in next-closest-in-time sequence.
Claim 10
Dependent Claim
163 words
In a computer system including a multiple-platter disk memory device, said disk memory device being divided into a plurality of disk cylinders comprising concentric rings occupying the same position in each platter wherein each ring is further divided into a plurality of sectors which define angularly spaced recording areas and having a disk access time, rotational latency, rotational distance, and function return time associated therewith, a method for scheduling process requests for access to said disk memory device, the steps comprising: generating a first queue containing said process requests sorted in ascending order by the sector number to which the requests desire access; and generating a second queue wherein: said sorted requests are grouped into packets, each of said packets including a predetermined maximum number of requests; said process requests in each of said packets are sorted in ascending/descending order by the disk cylinder numbers to which the requests desire access; and said process requests within each cylinder are sorted in next-closest-in-time sequence.
References Cited (Backward Citations)
US3702462A
Cited
US3623006A
Cited
US4403286A
Cited
US4901232A
Cited
US4604687A
Cited
US4680703A
Cited
US4858108A
Cited
US4875155A
Cited
US4979108A
Cited
US4831541A
Cited
US4888691A
Cited
US4949245A
Cited
US5140683A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-06-30 | 2000-12-30 | 2001-07-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-06-30 | 2004-12-30 | 2005-07-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-06-30 | 2008-12-30 | 2009-07-01 | $7700.00 | Window Closed / Lapsed |