The Gateway to Computer Science Excellence
+2 votes
1.2k views
Suppose that a disk drive has 5,000 cylinders, numbered 0 to 4999. The
drive is currently serving a request at cylinder 143, and the previous
request was at cylinder 125. The queue of pending requests, in FIFO
order, is:

86,1470, 913, 1774, 948, 1509, 1022,1750,130

Starting from the current head position, what is the total distance (in
cylinders) that the disk arm moves to satisfy all the pending requests
for C-SCAN?
in Operating System by Active (1.6k points)
retagged by | 1.2k views
+1
9985?
0
Yes I think that is right considering the jump.

2 Answers

+3 votes
Best answer

9985.....

by Boss (19.7k points)
edited by
0
0 votes

The requests in sorted order are:

83, 130, 913, 948, 942, 1022, 1470, 1509, 1750, 1771

The head is currently position at 143 and previous head position was 125. So, its moving to right extreme.

So, it moves to 4999. That counts to 4999 - 143 = 4856

Then it jumps to 0 and starts serving in same direction as before.

So, 130 seeks after jumping.

So, total head movements = 4856 + 130 = 4986

REF: http://www.cs.iit.edu/~cs561/cs450/disksched/disksched.html

by Boss (18.4k points)
0

I think we should consider movement of head when jump is performed so answer will be your answer + 4999 Right?

Also see this, https://gateoverflow.in/39716/gate-2016-1-48?show=40035#c40035
The resource you provided don't consider jump into calculation though (while other do it is bit ambiguous).

I asked this because here answer is provided for same question and it is not condering 0 which I think is wrong! https://gateoverflow.in/39716/gate-2016-1-48?show=40164#c40164.

0
Nop, they have clearly mentioned on site I mentioned that this jump isnt considered when we count total head movement.
0
I makes no sense to count jump in total head movements. If thats the case, I will always go for SCAN and never for C-SCAN.

So, ignore it.
0

This is directly from Galvin

12.4.4
C-SCAN Scheduling
Circular SCAN (C-SCAN) scheduling is a variant of SCAN designed to provide
a more uniform wait time. Like SCAN, C-SCAN moves the head from one end
of the disk to the other, servicing requests along the way. When the head
reaches the other end, however, it immediately returns to the beginning of
the disk, without servicing any requests on the return trip (Figure 12.7). The
C-SCAN scheduling algorithm essentially treats the cylinders as a circular list
that wraps around from the final cylinder to the first one.

C-Scan

0
yes,it wraps around. It doesnt go in reverse direction like SCAN
0
Yes but the question here is we consider jump! as head have to move from outer track to inner track. Why we should ignore it as it is real movement!!
0
Then we would get even worst performance than SCAN
0

We are trying to minimize the waiting time of request that are at other end. As it is given

Circular SCAN (C-SCAN) scheduling is a variant of SCAN designed to provide a more uniform wait time.

So the main matric here is waiting time not head movement!

0

Also see example given in wikipedia:

https://en.wikipedia.org/wiki/Elevator_algorithm#Example

The following is an example of how to calculate average disk seek times for both the SCAN and C-SCAN algorithms.

  • Example list of pending disk requests (listed by track number): 100, 50, 10, 20, 75.
  • The starting track number for the examples will be 35.
  • The list will need to be sorted in ascending order: 10, 20, 50, 75, 100.

Both SCAN and C-SCAN behave in the same manner until they reach the last track queued. For the sake of this example let us assume that the SCAN algorithm is currently going from a lower track number to a higher track number (like the C-SCAN is doing). For both methods, one takes the difference in magnitude (i.e. absolute value) between the next track request and the current track.

  • Seek 1: 50 − 35 = 15
  • Seek 2: 75 − 50 = 25
  • Seek 3: 100 − 75 = 25

At this point both have reached the highest (end) track request. SCAN will just reverse direction and service the next closest disk request (in this example, 20) and C-SCAN will always go back to track 0 and start going to higher track requests.

  • Seek 4 (SCAN): 20 − 100 = 80
  • Seek 5 (SCAN): 10 − 20 = 10
  • Total (SCAN): 155
  • Average (SCAN): 155 ÷ 5 = 31
  • Seek 4 (C-SCAN): 0 − 100 = 100 (C-SCAN always goes back to the first track)
  • Seek 5 (C-SCAN): 10 − 0 = 10
  • Seek 6 (C-SCAN): 20 − 10 = 10
  • Total (C-SCAN): 185
  • Average (C-SCAN): 185 ÷ 5 = 37
0
I dont understand why to count that head movement.
0

What part you don't understand? I think it is totally reasonable to count that head movement as it is actual movement of head.

Anways a cool video! :D

0
Does it lift up the head and wraps around or travels serially in reverse ordr?
+1

Are you confusing cylinder with sectors? Disk will rotate only in one direction we just move head from inner track/cylinder track to outer cylinder or vice versa.

Related questions

0 votes
1 answer
2
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,159 answers
193,768 comments
93,769 users