Disk-Head Scheduling Algorithms

Introduction

These charts give an example of the various disk-head scheduling algorithms and how they affect servicing of requests. The set of requests is 98 183 37 122 14 124 65 67 and the disk head starts at cylinder 53. Where direction is important (LOOK and SCAN), the disk head is moving outward.

Order of Service

algorithm	request order
fcfs	98	183	37	122	14	124	65	67
pickup	65	67	98	122	124	183	37	14
sstf	65	67	37	14	98	122	124	183
scan	37	14	65	67	98	122	124	183
look	37	14	65	67	98	122	124	183
c-scan	65	67	98	122	124	183	14	37
c-look	65	67	98	122	124	183	14	37

Head Motion

This chart shows how far the disk heads move to service each request, and the mean and standard deviation of the head motion.

algorithm	total number of cylinders moved								total	avg	stdev
fcfs	45	85	146	85	108	110	59	2	640	80.00	44.47
pickup	12	2	31	24	2	59	146	23	299	37.38	47.57
sstf	12	2	30	23	84	24	2	59	236	29.50	28.62
scan	16	23	79	2	31	24	2	59	236	29.50	26.97
look	16	23	51	2	31	24	2	59	208	26.00	20.72
c-scan	12	2	31	24	2	59	231	23	384	48.00	76.18
c-look	12	2	31	24	2	59	169	23	322	40.25	55.16

Waiting Motion

This chart shows the (cumulative) number of cylinders the disk heads must move before servicing each request, and the mean and standard deviation.

algorithm	cumulative number of cylinders moved								total	avg	stdev
fcfs	45	130	276	361	469	579	638	640	3138	392.25	228.78
pickup	12	14	45	69	71	130	276	299	916	114.5	113.24
sstf	12	14	44	67	151	175	177	236	876	109.50	85.60
scan	16	39	118	120	151	175	177	236	1032	129.00	73.12
look	16	39	90	92	123	147	149	208	864	108.00	62.37
c-scan	12	14	45	69	71	130	361	384	1086	135.75	150.91
c-look	12	14	45	69	71	130	299	322	962	120.25	123.33

Send email to [email protected].

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562

Page last modified on 5/13/99