5
$\begingroup$

I'm studying several disk scheduling algorithms; however, I'm kinda confused with SCAN. I understand the concept, but I don't understand the example given in the book. I think that the author made a mistake, but I want to be sure.

The example is the following:

Description of SCAN: The disk arm starts at one end of the disk, and moves toward the other end, servicing requests until it gets to the other end of the disk, where the head movement is reversed and servicing continues.

Suppose that the cylinder range goes from 0 to 199 and you have the following queue:
98, 183, 37, 122, 14, 124, 65, 67
Head pointer: 53

As seen in the image, the total head movement is of 208 cylinders

SCAN algorithm

I don't understand why 208 cylinders. If I understand correctly, the head will start at 53 and then move to 0 (that's 53 cylinders), then the head will move up and the last service requested is at 183 (that's another 183 cylinders). So the total head movement should be 53 + 183 = 236.

The book also has an image and description of C-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. The C-SCAN scheduling algorithm essentially treats the cylinders as a circular list that wraps around from the final cylinder to the first one.

enter image description here

Using the same example, with C-SCAN the cylinder would start at 53, then move up to 199 (146 cylinder movements), then go to 0 (199 movements), and then the last request would be at 37 (37 cylinder movements). The total cylinder movements would be 146+199+37=382. My question here is, do we also have to count the cylinders when the head goes back to 0 since it isn't servicing any requests?

Note: This information was extracted from Operating System Concepts with Java - 8th Edition by Silberschatz, Galvin, Gagne. You can also find this part of the chapter here.

Improve this question
$\endgroup$
2
  • $\begingroup$ The difference between 208 and 236 is 28, which amounts to twice the path 0-14. I guess the text assumed that after servicing 14, the head would not have gone down to 0, but reversed its direction instead since there was nothing in the queue for 0-14. $\endgroup$
    – chi
    Commented Jun 3, 2017 at 13:23
  • $\begingroup$ @chi Yeah, but I think that would be the C-LOOK algorithm. C-LOOK definition: Arm only goes as far as the last request in each direction, then reverses direction immediately, without first going all the way to the end of the disk. $\endgroup$
    – Jack
    Commented Jun 6, 2017 at 9:07

2 Answers 2

Reset to default
3
$\begingroup$

Here are the examples of various disk scheduling algorithms.

Yes you are correct in both the case. The author here has made mistake. For SCAN: The answer should be 236. For C-SCAN: The answer should be 146+37=183.(Note: The head movement when its not servicing any requests is not counted.) Refer the link, it gives a clear concept of how the different kinds of disk scheduling algorithms are used in practice.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ This doesn't seem to answer the question. $\endgroup$
    – Yuval Filmus
    Commented Sep 4, 2017 at 6:13
  • $\begingroup$ Than what according to you seems to be the answer to the question?? You can answer it and describe in detail here if you know. $\endgroup$
    – Parth Pandya
    Commented Sep 4, 2017 at 6:36
  • $\begingroup$ The post has two questions. Here is the first: I don't understand why 208 cylinders. If I understand correctly, the head will start at 53 and then move to 0 (that's 53 cylinders), then the head will move up and the last service requested is at 183 (that's another 183 cylinders). So the total head movement should be 53 + 183 = 236. $\endgroup$
    – Yuval Filmus
    Commented Sep 4, 2017 at 6:53
  • $\begingroup$ Here is the second: Using the same example, with C-SCAN the cylinder would start at 53, then move up to 199 (146 cylinder movements), then go to 0 (199 movements), and then the last request would be at 37 (37 cylinder movements). The total cylinder movements would be 146+199+37=382. My question here is, do we also have to count the cylinders when the head goes back to 0 since it isn't servicing any requests? $\endgroup$
    – Yuval Filmus
    Commented Sep 4, 2017 at 6:53
  • $\begingroup$ please see the whole answer. I mentioned both the cases up there. $\endgroup$
    – Parth Pandya
    Commented Sep 4, 2017 at 7:01
1
$\begingroup$

I want to add "Why return trip in C-SCAN should not be counted?" Actually the objective behind calculating total head movement is to find the total time spent by read write head to serve the given request, which is proportional to total head displacement. When we move quickly from one end of the disk to other end, there is a displacement; but the time required is negligible(as no requests are served in between) and hence this displacement is ignored.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.