[Operating System] Seek Time Algorithm: First-come, first served/Closest Cylinder Next/Elevator Algorithm Examples

Seek Time Algorithm: Firstcome, first served/Closest Cylinder Next/Elevator Algorithm Examples

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

# Example 1

Question) Disk requests come in to the dis driver for cylinders 10, 22, 20, 2, 40, 6, and 38, in that order. A seek takes 6 msec percylinder moved. How much seek time is needed for First-come, first served, Closest cylinder next and Elevator algorithm? In all cases, the arm is initially at cylinder 20.

Answer)

Frist-come, first served: 876 msec

Closest Cylinder next: 360 msec

Elevator algorithm: 348 msec.

---

이 문제는 Seek time 알고리즘마다 걸리는 시간을 구하는 문제이다.

전제 조건들을 살펴보면 Disk에 요청된 작업의 순서는 10-22-20-2-40-6-38 순이다.

또한 잊어버려서 안 되는 부분이 시작되는 실린더가 어디인지인데, 20에서 시작된다고 제시되어 있다.

따라서 20에서 시작해서 요청된 작업을 수행했을 때 각 seek time algorithms들이 걸리는 시간을 구하면 된다.

마지막으로 한 가지 더 알아두어야 할 것은 각 실린더가 찾는 데 걸리는 시간이 6 msec라고 나와있기에 마지막 결과에 6을 곱해주면 된다.

이러한 전제 조건을 기준으로 First-come, first served를 먼저 살펴보자.

---

First-come, frist served의 경우는 주어진 작업 순서대로 작업이 이루어지는 알고리즘이기에 10+12+2+18+38+34+32가 되며, 총 실린더 수는 146이 된다.

따라서 걸리는 시간은 146*6 = 876 msec가 나온다.

---

다음으로 Closet cylinder next 또는 Shortest seek first라고 불리는 알고리즘을 통해 이 문제를 해결하면 아래와 같은 결과가 나온다.

0+2+12+4+4+36+2=60 cylinders가 되는데, 그 이유는 가까운 실린더부터 작업 수행이 이루어지는 특징을 가지고 있기 때문이다.

여기서 헷갈리는 부분 중에 하나가 첫 번째 0이 나오는 이유인데, 처음 시작하는 실린더가 20으로 주어졌고 요청된 작업에 20이 있기 때문에 제일 가까운 20-20이 되어서 0이 나오게 된 것이다.

결과적으로 60*6을 하게되면 360 msec가 나온다.

---

마지막으로 Elevator algorithm 또는 initially moving upward를 적용하면 아래와 같은 결과가 나온다.

0+2+16+2+30+4+4  = 58 cylinders가 된다.

Elevator라는 의미답게 시작하는 실린더부터 가까운 순서대로 올라가며 작업을 수행하는 특징을 가지고 있다.

문제 안에서 제일 높은 숫자인 40까지 작업이 이루어진 다음에는 역순으로 남은 작업들을 처리한다.

따라서 중간에 30 실린더가 나온 이유는 40-10=30 이 되었기 때문이고 순서대로 6과 2의 작업이 이루어졌다.

결과적으로 58*6 = 348 msec가 된다.

비슷한 유형 문제를 통해 문제가 요구하는 내용을 이해할 수 있다.

---

# Example 2

Question) Disk requests come in to the dis driver for cylinders 12, 22, 25, 29, 40, 7, and 48, in that order. A seek takes 2 msec percylinder moved. How much seek time is needed for First-come, first served, Closest cylinder next and Elevator algorithm? In all cases, the arm is initially at cylinder 20.

Answer)

Frist-come, first served:

8+10+3+4+11+33+41=110 cylinders => 110*2 = 220 msec

Closest Cylinder next:

2+3+4+11+8+36+5=69 cylinders => 69*2 = 138 msec

Elevator algorithm:

2+3+4+11+8+36+5= 69 cylinders => 69*2 = 138 msec

---

# Example 3

Question) Disk requests come in to the dis driver for cylinders 3, 50, and 2, in that order. A seek takes 5 msec percylinder moved. How much seek time is needed for First-come, first served, Closest cylinder next and Elevator algorithm? In all cases, the arm is initially at cylinder 10.

Answer)

First-come, first served:

7+47+48=102 cylinders => 102*5 = 510 msec

Closest Cylinder next:

7+1+48=56 cylinders => 56*2 = 112 msec

Elevator algorithm:

40+47+1= 88 cylinders => 88*2 = 176 msec

---