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도 회전해서 보면 엘리베이터처럼 위아래로 움직인다고 해서 붙여진 이름이다.
참고 및 사진 출처
https://limkydev.tistory.com/165
https://www.geeksforgeeks.org/difference-between-scan-and-cscan-disk-scheduling-algorithms/
Last updated
