edited by
22,801 views
94 votes
94 votes

The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. 

What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are $2048$ and the head can start from any track?

  1. $9$
  2. $10$
  3. $11$
  4. $12$
edited by

16 Answers

2 votes
2 votes
We can start from any track.

$1366\overset{-1}{\rightarrow}1365\overset{+(1+2)}{\rightarrow}1368\overset{-(3+4)}{\rightarrow}1361\overset{+(7+8)}{\rightarrow}1376\overset{-(15+16)}{\rightarrow}1345\overset{+(31+32)}{\rightarrow}$$1408\overset{-(63+64)}{\rightarrow}1281\overset{+(127+128)}{\rightarrow}1536\overset{-(255+256)}{\rightarrow}1025\overset{+(511+512)}{\rightarrow}2048\overset{-(1023+1024)}{\rightarrow}1$

 

$-$ indicates we are going in left direction

$+$ indicates we are going in right direction.

$new\ distance = previous\ distance +( previous\ distance + 1)$

$+1$ is used to remove ambiguity when choosing next track.

 

Hence Option $D. \ 12 $ is correct answer.
edited by
1 votes
1 votes
Answer: B

Let the head start from 1024.

Requests are: 344, 854, 982, 1014, 1022, 1025, 1028, 1045, 1109, 1364

Cardinality: 10
Answer:

Related questions