# 12. 디스크 스케쥴링
### **디스크 스케쥴링**
#### **디스크 스케쥴링 알고리즘**
다중 프로그래밍 환경에서 여러개의 프로세스를 실행하려 한다고 할때, 보조기억장치에 저장된 여러개의 프로그램들을 메인메모리에 올려야 한다. 이때 프로세스 작업 처리 속도에 비해 **보조기억장치에서 읽어오는 시간이 굉장히 오래 걸린다.** 따라서 **작업의 처리 효율을 위해 디스크 접근 시간을 최대한 절약**하는게 중요하다.
이렇게 디스크에서 발생하는 처리 시간을 줄이는 알고리즘을 **디스크 스케줄링 알고리즘**이라 한다.
#### **디스크 접근 시간**
t = **Seek time** + rotational delay + transfer time
헤드가 물리적으로 이동하는 시간이 있기 때문에 지연 발생.
**Seek time 이 가장 크다.**
따라서 seek time을 낮추면 지연시간을 줄일 수 있다.
→ HOW? FCFS, SSTF, …
추가
SSD는 반도체에 전자가 이동하므로 물리적인 이동이 없다.
따라서 ssd는 물리적인 지연 발생 안함. (hdd에 비해 더 빠름)
#### **1. FCFS (First-Come First-Served)**
먼저 들어온 순서대로 읽어오는 방법.
ex)
Cylinder disk range = 0\~199
Disk queue = \[98, 183, 37, 122, 14, 124, 65, 67]
Seek : 53(now)→ 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
Total head movement : **640 cylinders**
→ **비 효율적**
#### **2. SSTF (Shortest-Seek-Time-First)**
현재 헤드 위치에서 가까운 순서대로 읽어오는 방법.
ex)
Cylinder disk range = 0\~199
Disk queue = \[98, 183, 37, 122, 14, 124, 65, 67]
Seek : 53(now)→ 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
Total head movement : **236 cylinders**
→ 가깝지 않은 프로그램은 탐색 안됨. **Starvation 발생**
→ 최적의 알고리즘이 아님 (53→ 37 → SSTF → … : **208 cylinders**)
#### **3. SCAN**
헤드가 디스크의 앞뒤 순서대로 읽어오는 방법. (방향성)
ex)
Cylinder disk range = 0\~199
Disk queue = \[98, 183, 37, 122, 14, 124, 65, 67]
Seek : 53(now)→ 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183
Total head movement : **236 cylinders**
→ **프로세스가 디스크에 요청하는 위치들이 실린더에 골고루 퍼져있음.**
```
*따라서 앞뒤로 움직이기보다 한 방향을 유지해서 원형으로 탐색하면 더 효과적이지 않을까?*
*혹은 끝까지 도달하지 않고 큐의 최대 최소까지만 탐색하면 더 효과적이지 않을까?*
```
#### **4. SCAN Variants**
#### **4-1. C-Scan**
헤드가 한 방향을 유지해서 원형으로 읽어오는 방법. (눈 치우는 원리)
ex)
Cylinder disk range = 0\~199
Disk queue = \[98, 183, 37, 122, 14, 124, 65, 67]
Seek : 53(now)→ 65 → 67 → 98 → 122 → 124 → 183 → 199 → 0 → 14 → 37
Total head movement : **183 cylinders**
→ 움직이는 거리는 더 길어질 수 있지만 더 빠른 속도로 움직일 수 있다.
#### **4-2. Look**
헤드가 끝까지 도달하지 않고 큐의 최대 최소까지만 읽어오는 방법. (탐색 범위 감소)
ex)
Cylinder disk range = 0\~199, **Disk queue range = 14\~183**
Disk queue = \[98, 183, 37, 122, 14, 124, 65, 67]
Seek : 53(now)→ 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183
Total head movement : **208 cylinders**
→ 실린더의 최소 범위와 최대 범위만 탐색하기 때문에 0까지 도달 안 함.
#### **4-3. C-Look**
헤드가 한 방향을 원형으로 탐색 & 큐의 최대 최소까지만 읽어오는 방법.
ex)
Cylinder disk range = 0\~199, **Disk queue range = 14\~183**
Disk queue = \[98, 183, 37, 122, 14, 124, 65, 67]
Seek : 53(now)→ 65 → 67 → 98 → 122 → 124 → 183 → 14 → 37
Total head movement : **153 cylinders**
→ C-SCAN + LOOK
→ 효율 좋다.
#### **2-5. Elivator Algorithm**
SCAN에 파생되어 나온 알고리즘(C-Scan, Look, C-Look)이 **90도 회전해서 보면 엘리베이터처럼 위아래로 움직인다고 해서 붙여진 이름이다.**
***
**참고 및 사진 출처**
[**http://blog.skby.net/%EC%97%98%EB%A6%AC%EB%B2%A0%EC%9D%B4%ED%84%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%EC%97%90%EC%84%BC%EB%B0%94%ED%9D%90-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/**](http://blog.skby.net/%EC%97%98%EB%A6%AC%EB%B2%A0%EC%9D%B4%ED%84%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%EC%97%90%EC%84%BC%EB%B0%94%ED%9D%90-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/)
