Minimizing Expected Head Movement in One-Dimensional and Two-Dimensional Mass Storage Systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Minimizing Expected Head Movement in One-Dimensional and Two-Dimensional Mass Storage Systems

Full text

Pdf (949 KB)

Source

ACM Computing Surveys (CSUR) archive
Volume 12 , Issue 2 (June 1980) table of contents

Pages: 167 - 178

Year of Publication: 1980

ISSN:0360-0300

Author

C. K. Wong

Computer Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 38, Citation Count: 19

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/356810.356814 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BERG72	BERGMANS, P P. "Minimizing expected travel time on geometrical patterns by optional probability rearrangements," Inf. Control 20 (1972), 331-350
	BITN79	BITNER, J R., AND WONG, C. K "Optimal and near-optimal scheduling algorithms for batched processing m linear storage," SIAM J. Comput. 8, 4 (1979), 479-498
	BLAC62	BLACKWELL, D. "Discrete dynamic programmmg," Annals Math Star. 33 (1962), 719-726.
	CHAN79	CHANDRA, A. K., CHANG, HSU, AND WONG, C. K. "Two-dimensional magnetm bubble memory," U.S. Patent No. 4, 174,538 (1979).
	COFF73	Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
	COPP79	COPPERSMITH, D., LEE, D. T., AND WONG, C.K. "An elementary proof of non-extstence of lsometries between Lpk and L~," IBM J. Res. Dev. 23, 6 (1979), 696-699.
	GROS73	David D. Grossman , Harvey F. Silverman, Placement of Records on a Secondary Storage Device to Minimize Access Time, Journal of the ACM (JACM), v.20 n.3, p.429-438, July 1973 [doi>10.1145/321765.321775]
	HARD52	HARDY, G. H., LITTLEWOOD, J. E., AND P6LYA, G. Inequalitws, Cambridge Umversity Press, Cambridge, England, 1952.
	HEMP77	HEMPY, H. "IBM 3850 mass storage systems, performance evaluation using a channel monitor," in Computer performance, K. M. Chandy and M. Reiser, Eds., North-Holland, Amsterdam, 1977, pp. 177-196.
	JOHN77	JOHNSON, C. "IBM 3850--Mass storage system," m Memory and storage technology, S. W. Miller, Ed., AFIPS Press, Arhngton, Va., 1977, pp. 93-98.
	KARP75	KARP, R. M., MCKELLER, A. C., AND WONG, C.K. "Near,optimal solutions to a 2-dimensional placement problem," SIAM J. Comput. 4, 3 (1975), 271-286.
	KOLL78	KOLLIAS, J.G. "An estimate of seek time for batched searching of random or index sequential structured fries," Comput. J. 21, 2 (1978), 122-123.
	LEE80	LEE, D. T., AND WONG, C.K. "Vorono~ diagrams in L~, (L~) metrics with 2-dimensional storage applications," SIAM J. Comput. 9, 1 (1980), 200-211.
	MARS67	MARSHALL, A. W., OLKIN, I., AND PROS- CHAN, F. "Monotonicity of ratios of means and other applications of majorization," in Inequalities, O. Shisha, Ed., Academic Press, New York, 1967.
	MCKE78	A. C. McKellar , C. K. Wong, Dynamic Placement of Records in Linear Storage, Journal of the ACM (JACM), v.25 n.3, p.421-434, July 1978 [doi>10.1145/322077.322085]
	OSTR52	OSTROWSK1, A. "Sur quelques applicatmns des fonctions conveNes et concaves au sens de I. Schur," J. Math. Pures Appl. 31 (1952), 253-292.
	SCHN76	Ben Shneiderman, Batched searching of sequential and tree structured files, ACM Transactions on Database Systems (TODS), v.1 n.3, p.268-275, Sept. 1976 [doi>10.1145/320473.320487]
	SCHU23	SCHUR, I "Uber em Klasse yon Mittlebfldungen mit Anwendungen auf die Determmatentheorie," Sitzber. Berl. Math. Ges. 22 (1923), 9-20.
	TEOR72a	TEOREY, T j "Properties of disk scheduhng policies in multiprogrammed computer systems," in Fall Jt. Computer Conf., Vol. 41, Pt. 1, 1972, pp. 1-11.
	TEOR72b	Toby J. Teorey , Tad B. Pinkerton, A comparative analysis of disk scheduling policies, Communications of the ACM, v.15 n.3, p.177-184, March 1972 [doi>10.1145/361268.361278]
	WEIN68	WEINGARTEN, A "The analytmal design of real-time dmk systems," m Proc IFIP Congress 1968, North-Holland, Amsterdam, 1968, pp D131-D137
	WIED77	Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1977
	WONG73	WON(}, C K, AND YUE, P C. "A majorization theorem for the number of distract outcomes in N mdependent trials," Discrete Math. 6 (1973), 391-398
	WONG77	WONG, C. K, AND CHU, K C. "Average distances m Lp disks," SIAM Rev 19 (1977), 320-324.
	YUE73	P. C. Yue , C. K. Wong, On the Optimality of the Probability Ranking Scheme in Storage Applications, Journal of the ACM (JACM), v.20 n.4, p.624-633, Oct. 1973 [doi>10.1145/321784.321790]
	YUE75	YuE, P C., AND WONG, C K. "Near-optimal heunstms for an assign _ment problem m mass storage," Int. J Comput. Inf Sct 4, 4 (1975), 281-294.

CITED BY 19

	Sedat Akyürek , Kenneth Salem, Adaptive block rearrangement, ACM Transactions on Computer Systems (TOCS), v.13 n.2, p.89-121, May 1995
	Bruce K. Hillyer , Avi Silberschatz, On the modeling and performance characteristics of a serpentine tape drive, ACM SIGMETRICS Performance Evaluation Review, v.24 n.1, p.170-179, May 1996
	S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984
	Frank Olken , Doron Rotem, Rearranging data to maximize the efficiency of compression, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.78-90, March 24-26, 1986, Cambridge, Massachusetts, United States
	Y. Manolopoulos , J. G. Kollias, Performance of a two-headed disk system when serving database queries under the scan policy, ACM Transactions on Database Systems (TODS), v.14 n.3, p.425-442, Sept. 1989
	P. Triantafillou , S. Christodoulakis , C. A. Georgiadis, A Comprehensive Analytical Performance Model for Disk Devices under Random Workloads, IEEE Transactions on Knowledge and Data Engineering, v.14 n.1, p.140-155, January 2002
	Stavros Christodoulakis, Analysis of retrieval performance for records and objects using optical disk technology, ACM Transactions on Database Systems (TODS), v.12 n.2, p.137-169, June 1987
	Bruce K. Hillyer , Avi Silberschatz, Random I/O scheduling in online tertiary storage systems, ACM SIGMOD Record, v.25 n.2, p.195-204, June 1996
	Daniel Alexander Ford , Stavros Christodoulakis, Optimal placement of high-probability randomly retrieved blocks on CLV optical discs, ACM Transactions on Information Systems (TOIS), v.9 n.1, p.1-30, Jan. 1991
	Shahram Ghandeharizadeh , Douglas J. Ierardi, Management of disk space with REBATE, Proceedings of the third international conference on Information and knowledge management, p.304-311, November 29-December 02, 1994, Gaithersburg, Maryland, United States
	S. Ghandeharizadeh , L. Ramos, Continuous Retrieval of Multimedia Data Using Parallelism, IEEE Transactions on Knowledge and Data Engineering, v.5 n.4, p.658-669, August 1993
	Ray-I Chang , Wei-Kuan Shih , Ruei-Chuan Chang, Real-Time Disk Scheduling for Multimedia Applications withDeadline-Modification-Scan Scheme, Real-Time Systems, v.19 n.2, p.149-168, Sept. 2000
	Sakti P. Ghosh , Edward G. Grochowski, Dynamic Statistical Control of Manufacturing Test, IEEE Design & Test, v.7 n.4, p.39-51, July 1990
	Eitan Bachmat , Tao Kai Lam , Avner Magen, Analysis of set-up time models: A metric perspective, Theoretical Computer Science, v.401 n.1-3, p.172-180, July, 2008
	Hsung-Pin Chang , Ray-I Chang , Wei-Kuan Shih , Ruei-Chuan Chang, GSR: A global seek-optimizing real-time disk-scheduling algorithm, Journal of Systems and Software, v.80 n.2, p.198-215, February, 2007
	Mei-Ling Chiang , Jia-Shin Huang, Improving the performance of log-structured file systems with adaptive block rearrangement, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	Daniel Alexander Ford , Stavros Christodoulakis, Optimizing Random Retrievals from CLV format Optical Disks, Proceedings of the 17th International Conference on Very Large Data Bases, p.413-422, September 03-06, 1991
	Sunita Sarawagi, Query Processing in Tertiary Memory Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.585-596, September 11-15, 1995
	Medha Bhadkamkar , Jorge Guerra , Luis Useche , Sam Burnett , Jason Liptak , Raju Rangaswami , Vagelis Hristidis, BORG: block-reORGanization for self-optimizing storage systems, Proccedings of the 7th conference on File and stroage technologies, p.183-196, February 24-27, 2009, San Francisco, California