40 votes 40 votes Consider a disk with the $100$ tracks numbered from $0$ to $99$ rotating at $3000$ rpm. The number of sectors per track is $100$ and the time to move the head between two successive tracks is $0.2$ millisecond. Consider a set of disk requests to read data from tracks $32, 7, 45, 5$ and $10$. Assuming that the elevator algorithm is used to schedule disk requests, and the head is initially at track $25$ moving up (towards larger track numbers), what is the total seek time for servicing the requests? Consider an initial set of $100$ arbitrary disk requests and assume that no new disk requests arrive while servicing these requests. If the head is initially at track $0$ and the elevator algorithm is used to schedule disk requests, what is the worse case time to complete all the requests? Operating System gatecse-2001 operating-system disk normal descriptive + – Kathleen asked Sep 14, 2014 • edited Jun 21, 2018 by kenzou Kathleen 10.9k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply mohan123 commented Oct 19, 2019 reply Follow Share @Akash Kanase @Bikram why we are not trvl only given track like 25 -- 32--45--99--10--7--5 please clear 0 votes 0 votes KUSHAGRA गुप्ता commented Nov 30, 2019 reply Follow Share @mohan123 We are moving on all the given tracks: $25\overset{7}{\rightarrow}32\overset{13}{\rightarrow}45\overset{54}{\rightarrow}99\overset{89}{\rightarrow}10\overset{3}{\rightarrow}7\overset{2}{\rightarrow}5=168$ 1 votes 1 votes JAINchiNMay commented Jul 20, 2022 reply Follow Share In the previous year exam paper this question is an mcq without any options @Counsellorlink 1 votes 1 votes Please log in or register to add a comment.
Best answer 42 votes 42 votes Answer for (A): We are using SCAN - Elevator algorithms. We will need to go from $25\rightarrow 99 \rightarrow 5$. (As we will move up all the way to $99$,servicing all request, then come back to $5$.) So, total seeks $= 74+94= 168$ Total time $= 168 \times 0.2 = 33.60000$ Answer for (B): We need to consider rotational latency too $\rightarrow $ $3000$ rpm I.e. $50$ rps $1 \ r = 1000 /50 \ msec = 20 \ msec$ So, rotational latency $= 20/2 = 10 \ msec$ per access. In worst case we need to go from tracks $0-99.$ I.e. $99$ seeks Total time $= 99 \times 0.2 + 10 \times 100 = 1019.8 \ msec = 1.019 \ sec$ Akash Kanase answered Nov 22, 2015 • edited Jun 26, 2018 by Milicevic3306 Akash Kanase comment Share Follow See all 52 Comments See all 52 52 Comments reply Gate Mm commented Dec 2, 2015 reply Follow Share @Akash 0-99 is 99 seeks..Plz clarify why its 100 1 votes 1 votes Akash Kanase commented Dec 2, 2015 reply Follow Share Updated. 1 votes 1 votes Gate Mm commented Dec 17, 2015 reply Follow Share In worst case we need to go from tracks 0-99. I.e. 100 seeks 0-99 why 100 still not clear.plz xplain 0 votes 0 votes Akash Kanase commented Dec 17, 2015 reply Follow Share You are right. Check now ! 0 votes 0 votes Bishnu Agrawal commented Jan 16, 2016 reply Follow Share 100 arbitrary requests means it would be 99,1,98,2,97,3...like this for worst case time. Can anybody add something clear to 2nd bit of this question ? 0 votes 0 votes Ram Sharma1 commented Sep 11, 2016 reply Follow Share I understood 99 seeks. But why rotational latency is calculated 100 times. please explain. 1 votes 1 votes vijaycs commented Oct 2, 2016 reply Follow Share Since, we are asked to calculate, what is the worse case time to complete all the requests, So, Ans should be - 99 * 0.2( total seek time) + 100 * 10( rotational latency) + 100 * 20 ( service time). shouldn't we add service time for all 100 disk, but I am not sure, whether we have to take service time of a single sector on all requested disk or service time of all 100 sector on all requested disk ?? 1 votes 1 votes Prashant. commented Nov 7, 2016 reply Follow Share I have doubt arbitary order in worst case if request like 0 ,99, 98,97,........ so it takes 99 +99 = 196 isnot? 1 votes 1 votes ana commented Dec 2, 2016 reply Follow Share Its asking for worst case time,u took average rotational latency .Why didn't u take full rotational latency? Isn't it? 6 votes 6 votes Shreya Roy commented Dec 4, 2016 reply Follow Share yes exactly in wost case the full rotational latency should be taken 2 votes 2 votes ana commented Dec 4, 2016 reply Follow Share Isn' t here average latency been taken in the solution as. 1 r = 1000 /50 msec = 20 msec So rotational latency = 20/2 = 10 msec per access. .20ms should be taken in place of 10ms is it so?? please explain? 0 votes 0 votes reena_kandari commented Jul 26, 2017 reply Follow Share @Arjun sir,in worst case ,avg or full rotational latency should be taken? I also think in worst case we have to take full rotational latency rather than avg. 0 votes 0 votes joshi_nitish commented Jul 26, 2017 i edited by joshi_nitish Jul 26, 2017 reply Follow Share avg rotational latency is taken when we have to position head on correct sector, full rotational latency is taken to read that track(because we can read that complete track only when we will comletely move round that track)... now in this case avg rotational latency is to be ignored, because here it does not matter, on which sector to put head, it has to ultimately read entire sectors of that track... moreover, there is one confusion, on going to particular track, if it has to read all sectors of that track then it will require full rotational latency else if only one sector of that track is to be read than avg latency is to be taken.. 7 votes 7 votes reena_kandari commented Jul 26, 2017 reply Follow Share So, for part b) you want to say that full must be taken? In worst case it might happen that the sector to be read in the last sector of that track(from the rotational direction). 1 votes 1 votes joshi_nitish commented Jul 26, 2017 reply Follow Share here worst case has nothing to do with avg or full rotational latency, more generally we can say it has nothing do with rotation, no matter whether best case, average case or worst case, it will take same rotational time for 100 tracks(now avg or full rotational time depends on whether it is reading all sectors or just one sector of that track) worst case is taken into account for selection of tracks which will give maximum time, for eg 100 request could be like this 0,0,0,0.......0(now here seek time will be 0 since head does not move across track, only movement will be within a track's sector i.e rotation) or it could be like this 0,1,1,1,1.....1(now here seek time will be 1 since there is one track movmnt, but inter-track roatioanl time will be same as above), now max track movement will be when 0,1,2,3...........99.. 9 votes 9 votes reena_kandari commented Jul 27, 2017 reply Follow Share How can we assume in exam that worst case to be consider only for seek time.Total time is asked in the qsn, so for worst case it should be worst case seek time+ worst case latency. 0 votes 0 votes rahul sharma 5 commented Aug 29, 2017 reply Follow Share @joshi_nitish ,then why we have taken average latency if it has nothing to do? Why cant we solve it like first part only considering only seek time?Please explain 0 votes 0 votes Ahwan commented Sep 4, 2017 i edited by Ahwan Oct 13, 2017 reply Follow Share For those who are having doubts on why in rotational latency 2 is divided but why not in total seek time. We have to move from track 0 to 99, 99 seek. So we calculated total seek time. But rotational latency is for finding the sector. Nothing is mentioned about the sector, for each track, it can be found anywhere, either in the next or in last. So take average rotational latency. Simple. When we do not know where is the sector exactly we take average rotational latency. Similarly, when we do not know where is the track exactly, we take average seek time. But here we are certain about the track(move from 0-99), so we calculated total seek time but we are not certain about sector so we calculated average rotational latency. 32 votes 32 votes MiNiPanda commented Oct 13, 2017 reply Follow Share Thanks for the explanation..a good one.. But I guess track no. should be from 0-99 and not 0-100.. 1 votes 1 votes MiNiPanda commented Oct 13, 2017 i edited by MiNiPanda Oct 13, 2017 reply Follow Share @Bishnu Agrawal That would have been the worst case in case of FCFS scheduling. In elevator algorithm whatever be the order of requests, the disk arm scans through all the requests that come along it's way while moving to an end. So in your case, the arm is going to service request 1,2,...99 in this order only. 1 votes 1 votes Ahwan commented Oct 13, 2017 reply Follow Share Yes, that is 0-99 thank you. 1 votes 1 votes VS commented Nov 1, 2017 reply Follow Share @rahul @joshi_nitish What is the final conclusion then ? In these types of questions should we consider the average rotational latency or not ? Because, the reasoning as given by joshi_nitish above also seems to be valid. 0 votes 0 votes rahul sharma 5 commented Nov 4, 2017 reply Follow Share @Ahwan,you mentioned Nothing is mentioned about the sector, for each track, it can be found anywhere, either in the next or in last. So take average rotational latency. Simple. So in the worst case,it can be in the last. By worst time it mean ,that my system should not take any time more than worst case time under all scenarios. Now if i have such a request ,where we always need to do one complete rotation for each request so we should not consider average rotational latency. 0 votes 0 votes Ahwan commented Nov 4, 2017 reply Follow Share @rahul sharma 5 No, I did not mean worst case as total time in the worst case. In worst case where can be the sector, in best case where can be the sector. So I took the average of them. I guess the answer will be same if you find total time if all sectors are last and total time if all sectors are in current position..if you will take average of them you will get same answer. 0 votes 0 votes srestha commented Nov 23, 2017 reply Follow Share @rahul @joshi Generally we do 100*(10+0.2) But if we do such way, will ans be wrong? 0 votes 0 votes srestha commented Nov 23, 2017 reply Follow Share or it could be like this 0,1,1,1,1.....1(now here seek time will be 1 since there is one track movmnt, but inter-track roatioanl time will be same as above), @reena here only one track movement? I am not getting, what u mean in this example?? could u elaborate it a bit? 0 votes 0 votes Chhotu commented Dec 1, 2017 i edited by Chhotu Dec 8, 2017 reply Follow Share what is the worse case time to complete all the requests? Hi Guys, I think instead of average rotational latency we should take time taken in full rotation. What is your opinion ? 1 votes 1 votes bhuv commented Dec 5, 2017 i edited by bhuv Dec 5, 2017 reply Follow Share If we are taking rotational latency because of "we do not know which sector is to be selected in those 100 random track request", then also in part - a) if request completion time asked instead of "seek time" then we have to consider the same avg. rotational latency in addition? 1 votes 1 votes srestha commented Dec 6, 2017 reply Follow Share @bruv depends on question 0 votes 0 votes srestha commented Dec 6, 2017 reply Follow Share One thing to notice here request should go from 25 ->99 ->10 isnot it? why upto 5 track request is taking? Is there calculation mistake or am I missing somewhere? Plz chk 0 votes 0 votes Chhotu commented Dec 8, 2017 reply Follow Share @srestha ji, Is there calculation mistake No am I missing somewhere? Yes 0 votes 0 votes rahul sharma 5 commented Dec 9, 2017 reply Follow Share @srestha 25 ->99 ->5 .Means staring from 25 goto 99 and service all request and come back to 5 ans service all request on the way. 0 votes 0 votes aspirant_18 commented Jan 24, 2018 reply Follow Share In the worst case, can the requests come in the form - 0, 99, 0, 99 .... so on. In that case for every two requests 99 seek would be needed. Correct me If I am wrong here... 0 votes 0 votes dhingrak commented Sep 2, 2018 reply Follow Share Why 99 seeks ? In worst case Request can be from tracks 0, 99, 1, 98,... Plz clarify. 1 votes 1 votes saiprabhas128 commented Sep 13, 2018 reply Follow Share because it is elevator algortihm dude..it wont follow the order of requests...it goes in a flow...till end and come back 2 votes 2 votes sushmita commented Dec 27, 2018 reply Follow Share NO not at all 1 votes 1 votes suchithreddy commented Sep 20, 2019 i edited by suchithreddy Sep 21, 2019 reply Follow Share @Akash Kanase @rahul sharma 5 Servicing a request means reading a particular sector or reading whole track? 0 votes 0 votes Shubhm commented Dec 1, 2019 i edited by Shubhm Dec 1, 2019 reply Follow Share If requests like - 0, 1, 2, ----, 99 (100 requests) Let head is at track number 1 and given that head is moving towards larger track number. then in worst case, total seek = 98 + 99 = 197 So why it is 99? ------------------------------------------------------------------------- P.S - sorry, I missed it If the head is initially at track 0 0 votes 0 votes Shivateja MST commented Dec 22, 2019 reply Follow Share In case of (b) (Assume sectors are numbered from 0 to 99) when we consider rotational delay,(assume R-W head in track 0 is at sector 0) Consider like in Track no. 0 we have to read 99th sector.Then from 0th to 99th sector we have to move head.It means 99*0.2 ms In Track no. 1 assume we have to read 0th sector.Now we have to move head to 0 from 99th sector.So again 99*0.2 ms. And so on......................................(this pattern alternates for all 100 tracks) So finally worst case Rotational delay will be 99*0.2 ms for each track. I think this type of access pattern would be worst case as it is taking more movements. So if we consider worst case time = 99*(0.2 ms + R) = 99( 0.2 ms +99*0.2 ms) =1980 ms =1.980 sec Anyone please clarify whether this is correct or not. 0 votes 0 votes rohith1001 commented Dec 25, 2019 reply Follow Share We need not consider sector number. And multiplying sector number with rotational latency will not give us the worst case rotational delay. (I meant the one highlighted here 99( 0.2 ms +99*0.2 ms)) The question does not specify the track number, so we take average rotational delay = R/2. We have 99 seeks (for tracks from 0 to 99), seek time = 99 * 0.2 ms = 19.8 ms = 0.0198 s Each of the 100 track requests (0 to 99) will have some rotational delay. We take average rotational delay here as we are not provided with the information about the sectors. Rotational delay = 100 * R/2 = 100 * 10 ms = 1 s Total delay in servicing all 100 requests = 0.0198 s + 1 s = 1.0198 s You can actually argue and take full rotational delay(=R) instead of average(=R/2), because in the worst case we will have to rotate the disk completely for each track request. In that case the answer would be 2.0198s. (There is a lot of discussion about this in the previous comments. I am not sure what to consider. If asked in exam my answer would be 2.0198s :P) 1 votes 1 votes mrinmoyh commented Apr 30, 2020 reply Follow Share rohith1001 why we are eliminating transfer time,is it because nothing mentioned about which or how many sector to read ??? I think it should be 19.8 + (100*10) + (100*0.2) 0.2 ms is the transfer time for 1 sector. 0 votes 0 votes pranavsettaluri9 commented May 13, 2020 reply Follow Share @Akash Servicing a request means going to a particular surface,cylinder,track and sector right? Hence we are considering avg. rotational latency in (b)? 0 votes 0 votes Soumyabrata Chatterj commented Jul 31, 2020 reply Follow Share I was having doubt why rotational latency is considered in 2nd part. Is it because 2nd part asks for worst case time and 1st part just asks for seek time ? 0 votes 0 votes Jithendra319 commented Aug 26, 2020 reply Follow Share For everyone who are wondering worst case scenario 0,99,1,98,2,97,….49,50 then before accessing the other requests from the current head you sort the list and go to only specified direction before revsersing head i.e it is given we should move towards higher side in this question ...since 0 to 99 all are consecutive we requre just 99 seeks and when head reverses no requests are pending..Hope it helps you 1 votes 1 votes chinmay_rajpurohit commented Jun 22, 2021 reply Follow Share @arjun sir can you tell me , why rotational time is being taken in this , bcoz in 1st part only seek time taken??? 0 votes 0 votes chinmay_rajpurohit commented Jun 22, 2021 reply Follow Share CAN you tell me why rotational time not taken in 1st question??? 0 votes 0 votes Haywire commented Nov 6, 2021 reply Follow Share @ chinmay_rajpurohit coz we are asked to calculate the seek time only. 0 votes 0 votes Manisha Jaishwal commented Jun 12, 2022 reply Follow Share @Akash Kanase why you don't consider Data transfer time ? 0 votes 0 votes Thadymademe commented Oct 4, 2022 reply Follow Share @Manisha Jaishwal because nowhere in the question it is mentioned anything about data . 0 votes 0 votes samarpita commented Nov 23, 2022 i edited by samarpita Nov 24, 2022 reply Follow Share @Arjun @Deepak Poonia @Sachin Mittal 1 sirif FCFS has been asked:Consider a set of disk requests to read data from tracks 1,99,1,99,1,99,……….1,99.So, total seek time will be (50 * 99 * 0.2)ms Total avg latency is (10 ms * 100) So total time will be (seek time + avg latency) = 1990 ms 0 votes 0 votes Deepak Poonia commented Nov 23, 2022 reply Follow Share @samarpita Elevator algorithm is used, Not FCFS. Using Elevator algorithm, you can service ALL requrest in a Single Traversal from Track 0 to 99. 0 votes 0 votes samarpita commented Nov 24, 2022 reply Follow Share @Deepak Poonia yes sir...i don’t know what i was thinking on that time. 0 votes 0 votes Please log in or register to add a comment.
–2 votes –2 votes a) 5,7,10,32,45 end track: 99 current:25 total seeks=(99-25)+(99-5)=74+94=168 total seek time = 0.2 * 168 ms b) from 0 to 99 worst case time = 0.2 * 99 ms jayendra answered Jan 2, 2015 jayendra comment Share Follow See all 2 Comments See all 2 2 Comments reply Akash Kanase commented Nov 22, 2015 reply Follow Share You missed rotational latency 1 votes 1 votes Pranavpurkar commented Aug 15, 2022 reply Follow Share Akash Kanase why rotational latency is needed here? 0 votes 0 votes Please log in or register to add a comment.
–3 votes –3 votes B. Question is about how much time required to satisfied 100 requests... 1 request time is = Tseek +TrotLatency + data transfer time Datatransfer time = 0(as not given any info) 99 seeks and 100 rotations required in worst case... So 99 * seek time + 100*rotational latency... GateRank1 answered Dec 22, 2015 GateRank1 comment Share Follow See all 0 reply Please log in or register to add a comment.