Elevator Algorithm Questions – 4 Marks
Version 1:
Let us compute the first part of the service completion schedule for the following table of incoming disk requests, using the Elevator Algorithm (with Look) – just like in class and the exercises. Take careful note of the arrival time for each request, as well as the amount of data to be read.
Assumptions: Suppose we are at cylinder 18000, and we are waiting for where to go next, since there were no more requests in the service list. Seek time is 1 ms for “setup time”, plus 1 ms for every 500 cylinders moved. Use average rotational latency. A change in direction, or start up, counts as one “setup time”, but don’t count anything for the slow-down time. A complete revolution takes 8 ms and for simplicity, the transfer time for transferring just one page is 0.0 ms. When traveling from one cylinder to another (e.g., cylinder 1500 to cylinder 7500), it is OK to be interrupted along the way by a request for cylinder 4000, and service it, providing you haven’t reached 4000 yet. But, don’t go backwards if you just missed it!
You don’t need to show your work.
We are requesting some data from cylinder #:
Arrival time of this request:
Amount of data to be read:
5000
0 ms
1 page
15000
8 ms
1 full track
2000
15 ms
1 full track
3000
17 ms
1 page
6000
25 ms
1 page
a) What is the first cylinder to be serviced?
b) What time is it (in ms.) when we first arrive at this cylinder in (a)?
c) What time is it (in ms.) immediately after we read the data that (a)’s request is for?
Answers:
a) 6000 gets serviced first. We bypassed the others.
b) It gets serviced at the 25 ms mark.
c) It takes 4 ms to read the data (rotational latency), so we’re now at 29 ms.
Marking Scheme:
a) 2 marks for saying 6000 got serviced first
b) 1 mark for saying 25 ms mark
c) 1 mark for saying it take 4 ms to read the data for 6000 … or that we’re now at 29 ms. In case
they got (a) or (b) wrong, it is OK to give 1 mark if they said 4 ms for 5000, 4 ms for 3000, or 8 ms for 15000 or 2000)
Version 2:
Let us compute the first part of the service completion schedule for the following table of incoming disk requests, using the Elevator Algorithm (with Look) – just like in class and the exercises. Take careful note of the arrival time for each request, as well as the amount of data to be read.
Assumptions: Suppose we are at cylinder 18000, and we are waiting for where to go next, since there were no more requests in the service list. Seek time is 1 ms for “setup time”, plus 1 ms for every 500 cylinders moved. Use average rotational latency. A change in direction, or start up, counts as one “setup time”, but don’t count anything for the slow-down time. A complete revolution takes 8 ms and for simplicity, the transfer time for transferring just one page is 0.0 ms. When traveling from one cylinder to another (e.g., cylinder 1500 to cylinder 7500), it is OK to be interrupted along the way by a request for cylinder 4000, and service it, providing you haven’t reached 4000 yet. But, don’t go backwards if you just missed it!
You don’t need to show your work.
We are requesting some data from cylinder #:
Arrival time of this request:
Amount of data to be read:
5000
0 ms
1 page
15000
8 ms
1 full track
7000
15 ms
1 full track
6000
17 ms
1 page
3000
25 ms
1 page
a) What is the first cylinder to be serviced?
b) What time is it (in ms.) when we first arrive at this cylinder in (a)?
c) What time is it (in ms.) immediately after we read the data that (a)’s request is for?
Answers:
a) 7000 gets serviced first. We bypassed the others.
b) It gets serviced at the 23 ms mark.
c) It takes 8 ms to read the data (one spin), so we’re now at 31 ms.
Marking Scheme
a) 2 marks for saying 7000 gets serviced first
b) 1 mark for saying 23 ms mark
c) 1markforsayingittake8mstoreadthedatafor7000…orthatweareat31ms. Incasethey
got (a) or (b) wrong, it is OK to give 1 mark if they said 4 ms for 5000, 4 ms for 6000, 4 ms for 3000, or 8 ms for 15000.
Version 3:
Let us compute the first part of the service completion schedule for the following table of incoming disk requests, using the Elevator Algorithm (with Look) – just like in class and the exercises. Take careful note of the arrival time for each request, as well as the amount of data to be read.
Assumptions: Suppose we are at cylinder 4000, and we are waiting for where to go next, since there were no more requests in the service list. Seek time is 1 ms for “setup time”, plus 1 ms for every 1000 cylinders moved. Use average rotational latency. A change in direction, or start up, counts as one “setup time”, but don’t count anything for the slow-down time. A complete revolution takes 6 ms and for simplicity, the transfer time for transferring just one page is 0.0 ms. When traveling from one cylinder to another (e.g., cylinder 1500 to cylinder 7500), it is OK to be interrupted along the way by a request for cylinder 4000, and service it, providing you haven’t reached 4000 yet. But, don’t go backwards if you just missed it!
You don’t need to show your work.
We are requesting some data from cylinder #:
Arrival time of this request:
Amount of data to be read:
5000
0 ms
1 page
15000
4 ms
1 full track
9000
15 ms
1 full track
3000
17 ms
1 page
6000
25 ms
1 page
a) What is the first cylinder to be serviced, and what is the time (in ms.) immediately after we finish reading its requested data?
b) What is the second cylinder to be serviced, and what is the time that we arrive at that cylinder?
c) What time is it immediately after we read the requested data for that second cylinder?
Answers:
a) 5000 gets serviced first. It is at 2 ms + 3ms of rotational delay; so, that’s 5 ms.
b) 15000 gets serviced second. It is at the 16 ms mark.
c) It takes 6 ms to read the data, so we’re now at 22 ms.
Marking Scheme
a) 1 mark for saying 5000 gets serviced first; 1 mark for saying that after we serviced it, we’re at the 5 ms mark (or you can break it into 0.5 marks for arriving at 2 ms and 0.5 for adding 3 ms of rotational latency time)
b) 0.5 marks for saying 15000 gets serviced second; 0.5 marks for saying we arrived at 16 ms
c) 1 mark for saying it takes 6 ms to read the data for 15000 … or that we’re now at 22 ms. In case they got (b) wrong, it is OK to give 1 mark if they added 3 ms for 5000, 3 ms for 6000, 3 ms for
3000, or 6 ms for 9000.
Version 4:
Let us compute the first part of the service completion schedule for the following table of incoming disk requests, using the Elevator Algorithm (with Look) – just like in class and the exercises. Take careful note of the arrival time for each request, as well as the amount of data to be read.
Assumptions: Suppose we are at cylinder 2000, and we are waiting for where to go next, since there were no more requests in the service list. Seek time is 1 ms for “setup time”, plus 1 ms for every 1000 cylinders moved. Use average rotational latency time. A change in direction, or start up, counts as one “setup time”, but don’t count anything for the slow-down time. A complete revolution takes 8 ms and for simplicity, the transfer time for transferring just one page is 0.0 ms. When traveling from one cylinder to another (e.g., cylinder 1500 to cylinder 7500), it is OK to be interrupted along the way by a request for cylinder 4000, and service it, providing you haven’t reached 4000 yet. But, don’t go backwards if you just missed it!
You don’t need to show your work.
We are requesting some data from cylinder #:
Arrival time of this request:
Amount of data to be read:
5000
0 ms
1 page
15000
4 ms
1 full track
9000
12 ms
1 full track
3000
17 ms
1 page
6000
25 ms
1 page
a) What is the first cylinder to be serviced, and what is the time (in ms.) immediately after we finish reading its requested data?
b) What is the second cylinder to be serviced, and what is the time that we arrive at that cylinder?
c) What time is it immediately after we read the requested data that (b)’s request is for?
Answers:
a) 5000 gets serviced first. It is at 4 ms + 4ms of rotational delay; so, that’s 8 ms.
b) 9000 gets serviced second. It is at the 13 ms mark.
c) It takes 8 ms to read the data, so we’re now at 21 ms.
Marking Scheme
a) 1 mark for saying 5000 gets serviced first; 1 mark for saying that after we serviced it, we’re at the 8 ms mark (can break this into 0.5 for the 4 ms rotational delay and 0.5 for the 4 ms arrival time)
b) 0.5 marks for saying 9000 gets serviced second; 0.5 marks for saying we arrived at 13 ms
c) 1 mark for saying it is 21 ms when we finish servicing 9000 (because it takes 8 ms to read the
data for 9000). In case they got (b) wrong, then it is OK to give 1 mark if they added 8 ms to 15000’s case from (b), or added 4 ms to any of 5000, 3000, or 6000 from their (b) answer.