Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Patent
1995-07-31
1998-07-28
Chan, Eddie P.
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
395826, 395672, 395673, 395607, 395859, 395874, 711112, 348 7, G06F 1300, G06F 1328
Patent
active
057874824
ABSTRACT:
A disk control mechanism for controlling the operations of a movable arm disk drive. The disk control mechanism contains a disk access scheduler which accepts disk access requests having a deadline and a disk location. The disk access scheduler further consists of a queue data structure for storing the requests. The queue contains a predefinded window that contains a certain number of requests with deadlines to expire sooner than all other requests. The request that is most soon to expire, the most urgent request, is located at the head of the queue. The disk access scheduler contains logic to determine whether the most urgent request has a deadline to expire sooner than tolerated by a set threshold, and in such cases the disk access scheduler schedules for service the most urgent request prior to any other request, otherwise it scans towards the most urgent request and schedules requests with a disk location between the current arm location and the most urgent request.
REFERENCES:
patent: 4604687 (1986-08-01), Abbott
patent: 5522054 (1996-05-01), Gunlock et al.
patent: 5544313 (1996-08-01), Shachnai et al.
patent: 5581784 (1996-12-01), Tobagi et al.
patent: 5592612 (1997-01-01), Birk
patent: 5644786 (1997-07-01), Gallagher et al.
Carlos A. G. Pico et al., "Dynamic Scheduling of Computer Tasks Using Genetic Algorithms", 1994, Evolutionary Computation, 1994 Conference, pp. 829-833.
Huanxu Pan et al., "A Time-Scale Depedent Disk Scheduling Scheme for Multimedia-on-Demand-Servers", Multimedia Computing and Systems, 1996 Int'l. Conference pp. 572-579.
Lon-Chan Chu, et al., "Optimization in Real Time", Real-Time Systems, 1991 symposium, pp. 150-159.
Alberto Avritzer et al., "A Load Sharing Interconnection Network for Hard* Real-Time Systems", Parallel Processing, 1991 Symposium, pp. 591-598.
Seltzer, M. et al. "Disk Scheduling Revisited, " Proc. of the Winrter '90 USENIX Conf., pp. 22-26, Jan. 1990.
Yu, P. et al., "Grouped Sweeping Scheduling for DASD-based Multimedia Storage Management", Multimedia Systems Journal, 1:9-109, 1993.
Gemmel, D.J. et al., Multimedia Network Serves: Multi-Channel Delay Sensitive Data Retrieval, Multimnedia Systems, 1(6):240-252, 1994.
Denning, Peter J., "Effects of Scheduling on File Memory Operations,"Proc. of the AFIPS Spring Joint Computer Conf. pp. 9-21, 1967.
Teory, T. J., "Poperties of Disk Scheduling Policies in Multiprogrammed Computer Systems,"Proc. of the AFIPS Fall Joint COmputer Conf. pp. 1-11, 1972.
Teory, T. J. et al., A Comparative Analysis of Disk Scheduling Policies, Comm. of the ACM, vol. 15, No. 3, pp. 177-184, Mar. 1972.
Peterson, J. L. et al., Operating System Concepts, 2nd. Ed. Addison-Wesley Publishing Company, 1985.
Coffman, E.G. et al., Analysis of Scanning Policies for Reucing Disk Seek Times, SIAM J. of Computing, vol. 1, No.3, Sep. 1972.
Wilhelm, N.C. "An Anomaly in Disk Scheduling: A Comparioson of FCFS and SSTF Seek Scheduling using an Empirical Model for Disk Accesses," Comm. of the ACM, vol. 19, No. 1, pp. 13-17, Jan. 1976.
Hofri, M., "Disk Scheduling: FCFS vs. SSTF Revisted,"Comm. of the ACM, vol. 23, No. 11, pp. 645-653, Nov. 1981.
Frank, H., "Analysis and Otimization of Disk Storage Devices for Time-Sharing Systes," J. of ACM, vol. 16, NO. 4, pp. 602-620, Oct. 1969.
Gotlieb, C.C. et al., "Performance of Movable-Head Disk Scheduling Disciplines," J. of the ACM, vol. 20, No. 4, pp. 604-623, Oct. 1973.
Fuller, S.H., "Minimal-Total-Processing-Time Drum and Disk Scheduling Disciplines," Comm. of the ACM, vol. 17, No. 7, pp. 376-381, Jul. 1974.
Perros, H.G., "A Regression Model for Predicting the Response Time of a Disk I/O System," Computer J., vol. 23, No. 1, pp. 34-36, Feb. 1980.
Liu, C. L. et al., "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment," J. ACM vol. 20, pp. 46-61, No. 1, Jan. 1973.
Abbott, R. et al., Scheduling I.O Request with Deadlines: A Performance Evaluation, Proc. of Real-Time Systems Symposium, pp. 113-124, 1990.
Reddy, A.L. et al. . et al. ., "I/O Issues in a Mulitimedia System," Computer, 27(30):69-74, 1994.
Chen Shenze
Thapar Manu
Chan Eddie P.
Croll Timothy Rex
Hewlett--Packard Company
Kim Hong C.
LandOfFree
Deadline driven disk scheduler method and apparatus with thresho does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deadline driven disk scheduler method and apparatus with thresho, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deadline driven disk scheduler method and apparatus with thresho will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-35306