Electrical computers and digital processing systems: memory – Storage accessing and control – Access timing
Reexamination Certificate
1996-09-20
2001-07-17
Bragdon, Reginald G. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Access timing
C711S158000, C711S151000
Reexamination Certificate
active
06263411
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a new disk scheduling algorithm for supporting simultaneous read and write requests that are made by the user in the presence of real-time requirements that are associated with these requests.
2. Description of Background Art
Video-on-demand and video authoring tools are emerging as very interesting and challenging multimedia applications. They require special hardware and networking protocols that can accommodate the real-time demands of these applications as well as the high bandwidth that they need.
Several video server architectures are proposed for handling video-on-demand applications. “A Video Server Using ATM Switching Technology,” Y. Ito and T. Tanaka, in
The
5
th International Workshop on Multimedia Communication
, pages 341-346, May 1994; “A File System for Continuous Media”, David Anderson, Yoshitomo Osawa, and Ramesh Govindan,
ACM Trans. Computer Systems,
10(4):311-337, 1992; “Designing An On-Demand Multimedia Service”, P. V. Rangan, H. M. Vin, and S. Ramanathan,
IEEE Communication Magazine
, pages 56-64, July 1992. The present invention is well adapted to work on a server architecture such as the one proposed in
The
5
th International Workshop on Multimedia Communication
that uses multiple disks and file servers that are internally connected by an ATM network. The invention may be implemented on other architectures, as well. Several performance studies and simulations have been conducted to estimate the performance of this system.
A video server can support a variety of applications. Among these applications are: video-on-demand, and video authoring or editing. Each application has its own system requirements. Our focus here is on the disk scheduling requirements of such systems. For example, from the disk's point of view, video-on-demand applications issue read-only requests to the disk, while video editing applications issue both read and write requests. Moreover, some applications may issue read and/or write requests that may or may not have real-time deadlines so that these requests have to be serviced before the deadlines. For example, in video-on-demand, each read request has to be fulfilled within a given deadline. Finally, some applications may allow some of its read or write requests to be lost by the system, i.e., they are not serviced or fulfilled by the disk. For example, some frames can be lost during video viewing due to congestion in the disk.
More formally, from the disk scheduling point of view, we classify read and write requests into four categories, where each category has different requirements and is useful for a certain class of applications. These categories are:
1. dl requests: these are read or write requests that have
d
eadlines and the requests may be
l
ost in the case of congestion. Read and write requests of this category are referred to as R
dl
, and W
dl
, respectively.
2. dn requests: these are read or write requests that have
d
eadlines and the requests may
n
ot be lost regardless of the congestion in the system. Read and write requests of this category are referred to as R
dn
and W
dn
, respectively.
3. nl requests: there are read or write requests that have
n
o deadlines and the requests may be
l
ost in case of congestion. Read and write requests of this category are referred to as R
nl
and W
nl
, respectively.
4. nn requests: these are read or write requests that have
n
o deadlines and the requests may
n
ot be lost regardless of the congestion in the system. Read and write requests of this category are referred to as R
nn
and W
nn
, respectively.
For example, the application requirement in the case of video-on-demand is that the disk scheduling process must support only R
dl
requests, i.e., read requests that have deadlines but can be lost in case the requests do not get serviced before their deadlines.
Different disk scheduling processes need to be designed for each category of requests. Notice that for the requests that belong to the category nl (whether W
nl
or R
nl
), since there are no deadlines, it is always true that these requests can be delayed until they are satisfied. Therefore, it makes no sense for the system to lose them as they can afford to wait until they get serviced. As a result, W
nl
and R
nl
are treated here as W
nn
and R
nn
, respectively, since they have no deadline and will never be lost. As a result, disk scheduling techniques for only the dl, dn, and nn categories are expressly considered here.
SUMMARY OF THE INVENTION
The present invention provides a new disk scheduling process that supports the R
dl
and R
nn
categories for read requests and the W
nn
category for write requests. This combination of categories fits naturally into some common applications for video servers.
Thus, the present invention is directed toward extending the functionality of video servers so that they can handle video authoring and editing simultaneously with video-on-demand requests. In this new environment, some users are requesting video streams (e.g., movies) that are already existing video streams. From the video server's point of view, the major difference is that video-on-demand is a read-only application, while video editing and authoring is a read/write application. This difference impacts the design of the processes in a video server.
These and other objects are obtained by providing a method of supporting simultaneous disk read and write requests in a video server, comprising the steps of: assigning a deadline to the write requests based on an amount of available space in a buffer pool; inserting the read requests and said the requests in a common disk queue; and processing said read and write requests which come to a head of the queue.
The objects of the present invention are also obtained by providing a video server architecture for supporting simultaneous disk read and write requests, comprising: a memory buffer pool in which the read and write requests are temporarily stored; a common disk queue in which the read and write requests are received from the memory buffer pool; and a file server for processing the read and write requests, the file server having at least one disk; control means for determining locations for inserting the read and write requests in the disk queue, wherein the write requests are assigned a deadline.
Further scope of applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.
REFERENCES:
patent: 5379379 (1995-01-01), Becker et al.
patent: 5524235 (1996-06-01), Larson et al.
patent: 5541912 (1996-07-01), Choudhury et al.
patent: 5737547 (1998-04-01), Zuravleff et al.
patent: 5809278 (1998-09-01), Watanabe et al.
Alonso Rafael
Aref Walid G.
Kamel Ibrahim
Anderson Matthew D.
Bragdon Reginald G.
Harness & Dickey & Pierce P.L.C.
Matsushita Electric - Industrial Co., Ltd.
LandOfFree
Video server scheduling for simultaneous read-write requests does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Video server scheduling for simultaneous read-write requests, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video server scheduling for simultaneous read-write requests will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2548982