Patent US271781A successfully refreshed from Google Patents.
US6023720A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Simultaneous processing of read and write requests using optimized storage partitions for read and write request deadlines
Assignee: Panasonic Holdings Corp
•
Filing: 1998-02-09
•
Granted: 2000-02-08
•
Expires: 2018-02-09
Abstract
Abstract The disk scheduling system supports the processing of simultaneous storage device read and write requests in a video server environment, thereby supporting both video-on-demand and non-linear editing applications. Read requests are the result of movie viewing, while write requests are the result of video clip editing or movie authoring procedures. Due to real-time demands of movie viewing, read requests have to be fulfilled within certain deadlines, otherwise they are considered lost. Since the data to be written into the storage device is stored in main memory buffers (or write buffers), write requests can be postponed until critical read requests are processed. However, write requests still have to be proceeded within reasonable delays and without the possibility of indefinite postponement. This is due to the physical constraint of the limited size of the main memory buffers. The new process treats both read and write requests in a homogenous manner in order to ensure that the deadlines are met and avoids indefinite postponement and large buffer sized in the case of storage device writes utilizing a single queue of requests.
Inventors
- 👤 Walid G. Aref
- 👤 Ibrahim Kamel
- 👤 Thirumale N. Niranjan
- 👤 Shahram Ghandeharizadeh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 14:31
CPC Classifications
H; H04; H04N; H04N21/00; H04N21/20; H04N21/23; H04N21/232; H04N21/2326; G; G11; G11B; G11B27/00; G11B27/02; G11B27/031; G11B27/034
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
184 words
A method of supporting the processing of simultaneous read requests and write requests of a storage device in the presence of real-time requirements that are associated with these requests, comprising the steps of: constructing a storage device data structure with a plurality of partitions that correspond to a plurality of seek paths, the storage device data structure storing both read requests and write requests; generating read request deadlines for the read requests that are based at least in part on a user-desired response time for handling the read requests; generating write request deadlines for the write requests that are based at least in part on the capacity of a write buffer that stores data associated with the write requests until the data is written to the storage device; and placing the read requests and the write requests within the storage device data structure based at least in part on the read request deadlines and write request deadlines, such that an optimal seek path is maintained for each of the plurality of partitions while minimizing violations of the read request deadlines and write request deadlines.
Claim 2
Independent Claim
184 words
A method of supporting the processing of simultaneous read requests and write requests of a storage device in the presence of real-time requirements that are associated with these requests, comprising the steps of: constructing a storage device data structure with a plurality of partitions that correspond to a plurality of seek paths, the storage device data structure storing both read requests and write requests; generating read request deadlines for the read requests that are based at least in part on a user-desired response time for handling the read requests; generating write request deadlines for the write requests that are based at least in part on the capacity of a write buffer that stores data associated with the write requests until the data is written to the storage device; and placing the read requests and the write requests within the storage device data structure based at least in part on the read request deadlines and write request deadlines, such that an optimal seek path is maintained for each of the plurality of partitions while minimizing violations of the read request deadlines and write request deadlines.
Claim 3
Dependent Claim
33 words
The method of claim 1 wherein the write request deadlines are based at least in part on an estimate of the time in which the write buffer will become full (λ W ).
Claim 4
Dependent Claim
15 words
The method of claim 2, further comprising the step of dynamically computing λ W .
Claim 5
Dependent Claim
25 words
The method of claim 3, wherein the step of dynamically computing λ W includes maintaining a running average of computed values of λ W .
Claim 6
Dependent Claim
24 words
The method of claim 3, further comprising the step of regenerating the write request deadlines when λ W has changed beyond a predetermined threshold.
Claim 7
Dependent Claim
26 words
The method of claim 5, further comprising the step of reorganizing the placement of the read and write requests based upon the regenerated write request deadlines.
Claim 8
Dependent Claim
233 words
An article of manufacture for supporting the processing of simultaneous read requests and write requests of a storage device in the presence of real-time requirements that are associated with these requests, comprising: a memory for storing data that is accessed by an application program being executed by a multimedia system; a data structure stored in said memory that contains data corresponding to both read requests and write requests of said storage device, said data structure including: a plurality of partitions that subdivide said data structure and that correspond to a plurality of seek paths of said storage device; a plurality of read request data stored in said data structure, said plurality of read request data having read request deadlines that are based at least in part on a user-desired response time for handling the read request; and a plurality of write request data stored in said data structure, said plurality of write request data having write request deadlines that are based at least in part on the capacity of a write buffer that stores data associated with the write requests until the data is written to the storage device, whereby said plurality of read request data and write request data are organized in said data structure such that an optimal seek path is maintained for each of said plurality of partitions while minimizing violations of said read request deadlines and write request deadlines.
Claim 9
Dependent Claim
233 words
An article of manufacture for supporting the processing of simultaneous read requests and write requests of a storage device in the presence of real-time requirements that are associated with these requests, comprising: a memory for storing data that is accessed by an application program being executed by a multimedia system; a data structure stored in said memory that contains data corresponding to both read requests and write requests of said storage device, said data structure including: a plurality of partitions that subdivide said data structure and that correspond to a plurality of seek paths of said storage device; a plurality of read request data stored in said data structure, said plurality of read request data having read request deadlines that are based at least in part on a user-desired response time for handling the read request; and a plurality of write request data stored in said data structure, said plurality of write request data having write request deadlines that are based at least in part on the capacity of a write buffer that stores data associated with the write requests until the data is written to the storage device, whereby said plurality of read request data and write request data are organized in said data structure such that an optimal seek path is maintained for each of said plurality of partitions while minimizing violations of said read request deadlines and write request deadlines.
Claim 10
Dependent Claim
44 words
The article of manufacture of claim 7, further comprising a storage device access scheduler that receives said read and write requests, calculates said read request deadlines, calculates said write request deadlines, and places each of said read and write requests within said data structure.
Claim 11
Dependent Claim
30 words
The article of manufacture of claim 8, wherein said storage device access scheduler includes a write request deadline generator that receives said write requests and calculates said write request deadlines.
Claim 12
Dependent Claim
30 words
The article of manufacture of claim 8, wherein said storage device access scheduler includes a read request deadline assigner that receives said read requests and calculates said read request deadlines.
Claim 13
Dependent Claim
57 words
The article of manufacture of claim 9, wherein said storage device access scheduler includes a data storage organizer that places each of the read and write requests within the queue data structure such that an optimal seek path is maintained for each of the plurality of partitions while minimizing violations of the read and write requests deadlines.
Claim 14
Dependent Claim
207 words
A storage device access scheduler for supporting video-on-demand and non-linear editing of a storage device in the presence of real-time requirements that are associated with the read requests and write requests of video-on-demand and non-linear editing, comprising: a memory having a storage device data structure with a plurality of partitions that correspond to a plurality of seek paths, the storage device data structure storing both read requests and write requests; a read request deadline assigner for generating read request deadlines for the read requests that are based at least in part on a user-desired response time for handling the read requests; a write request deadline assigner for generating write request deadlines for the write requests that are based at least in part on the capacity of a write buffer that stores data associated with the write requests until the data is written to the storage device; and a disk queue organizer for placing the read requests and the write requests within the storage device data structure based at least in part on the read request deadlines and write request deadlines, such that an optimal seek path is maintained for each of the plurality of partitions while minimizing violations of the read request deadlines and write request deadlines.
Claim 15
Dependent Claim
207 words
A storage device access scheduler for supporting video-on-demand and non-linear editing of a storage device in the presence of real-time requirements that are associated with the read requests and write requests of video-on-demand and non-linear editing, comprising: a memory having a storage device data structure with a plurality of partitions that correspond to a plurality of seek paths, the storage device data structure storing both read requests and write requests; a read request deadline assigner for generating read request deadlines for the read requests that are based at least in part on a user-desired response time for handling the read requests; a write request deadline assigner for generating write request deadlines for the write requests that are based at least in part on the capacity of a write buffer that stores data associated with the write requests until the data is written to the storage device; and a disk queue organizer for placing the read requests and the write requests within the storage device data structure based at least in part on the read request deadlines and write request deadlines, such that an optimal seek path is maintained for each of the plurality of partitions while minimizing violations of the read request deadlines and write request deadlines.
Claim 16
Dependent Claim
36 words
The storage device access scheduler of claim 12 wherein the write request deadlines are based at least in part on an estimate of the time in which the write buffer will become full (λ W ).
Claim 17
Dependent Claim
14 words
The storage device access scheduler of claim 13, wherein λ W is dynamically computed.
Claim 18
Dependent Claim
28 words
The storage device access scheduler of claim 13, wherein said write request deadline assigner regenerates the write request deadlines when λ W has changed beyond a predetermined threshold.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-02-07 | 2003-08-09 | 2004-02-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-07 | 2007-08-09 | 2008-02-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-07 | 2011-08-09 | 2012-02-08 | $7700.00 | Window Closed / Lapsed |