Competitive analysis of on-line disk scheduling

被引：0

作者：

Yeh, TH ^{[1
]}

Kuo, CM ^{[1
]}

Lei, CL ^{[1
]}

Yen, HC ^{[1
]}

机构：

[1] Natl Taiwan Univ, Dept Elect Engn, Taipei 10764, Taiwan

来源：

ALGORITHMS AND COMPUTATION | 1996年 / 1178卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a detailed competitive analysis of a popular on-line disk scheduling algorithm, namely, LOOK. Our analysis yields a tight competitive ratio for the LOOK algorithm. By comparing and contrasting the competitive ratio of LOOK with the lower bounds of FCFS and SSTF (which are equally popular in disk scheduling), our results provide strong evidence to suggest that when the workload of disk access is heavy, LOOK outperforms SSTF and FCFS. As a by-product, our analysis also reveals (quantitatively) the role played by the degree of lookahead in disk scheduling.

引用

页码：356 / 365

页数：10

共 50 条

[41] On-line scheduling with precedence constraints
Azar, Y
Epstein, L
ALGORITHM THEORY - SWAT 2000, 2000, 1851 : 164 - 174
[42] On-line scheduling with setup costs
Gambosi, G
Nicosia, G
INFORMATION PROCESSING LETTERS, 2000, 73 (1-2) : 61 - 68
[43] On-line scheduling on uniform multiprocessors
Funk, S
Goossens, J
Baruah, S
22ND IEEE REAL-TIME SYSTEMS SYMPOSIUM, PROCEEDINGS, 2001, : 183 - 192
[44] On-line scheduling in assembly processes
Chauvet, F
Proth, JM
INFOR, 2001, 39 (03) : 245 - 256
[45] On the on-line maintenance scheduling problem
Shamsaei, Fahimeh
Telha, Claudio
Van Vyve, Mathieu
OPTIMIZATION LETTERS, 2018, 12 (02) : 387 - 397
[46] On-line scheduling with forbidden zones
Khammuang, K.
Abdekhodaee, A.
Wirth, A.
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2007, 58 (01) : 80 - 90
[47] Batch list on-line scheduling
Huo, Manchen
Tang, Lixin
2006 INTERNATIONAL CONFERENCE ON SERVICE SYSTEMS AND SERVICE MANAGEMENT, VOLS 1 AND 2, PROCEEDINGS, 2006, : 1144 - 1149
[48] On-line bicriteria interval scheduling
Baille, F
Bampis, E
Laforest, C
Thibault, N
EURO-PAR 2005 PARALLEL PROCESSING, PROCEEDINGS, 2005, 3648 : 312 - 322
[49] On-line scheduling meets MES
Tinham, Brian
Control and Instrumentation, 1996, 28 (04):
[50] On-line scheduling of parallel jobs
Ye, D
Zhang, GC
STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, PROCEEDING, 2004, 3104 : 279 - 290

← 1 2 3 4 5 →