디스크 스케줄링
디스크 스케줄링(Disk Scheduling)이란, 디스크에 요청된 입출력(I/O) 작업들을 효율적으로 처리하기 위해 작업 순서를 정하는 알고리즘
- 디스크는 물리적으로 회전하는 플래터와 이동하는 헤드로 구성된다.
- 따라서 헤드를 이동하는 거리(Seek Time)가 입출력 속도에 큰 영향을 준다.
디스크 스케줄링 종류
- FCFS(First Come First Served)
- SSTF(Shortests Seek Time First)
- SCAN
- C-SCAN
- LOOK
- C-LOOK
- Eschenbach (에셴바흐 기법)
- N-step SCAN
문제풀이
1.FCFS(First Come First Served)
난이도 ⭐
- 초기 헤드위치만 주어짐
- 헤드는 요청 순서대로 움직인다.
- 앞에 초기헤드만 추가하고 요청순서대로 문제풀이
- 이동거리는 절대값(현재위치 - 요청위치)의 합
- 초기 헤드 위치: 53
- 대기 큐 순서: 98, 183, 37, 122, 14, 124, 65, 67
- 이동 거리 계산:
1. |53 - 98| = 45
2. |98 - 183| = 85
3. |183 - 37| = 146
4. |37 - 122| = 85
5. |122 - 14| = 108
6. |14 - 124| = 110
7. |124 - 65| = 59
8. |65 - 67| = 2- 총 이동거리: 640 (요청 순서를 그대로 따라간 결과)
45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 6402.SSTF(Shortest Seek Time First)
난이도 ⭐
- 초기 헤드위치, 트랙 이동 방향 주어지나 트랙 이동방향은 중요하지 않음
- 초기헤드 위치에서 가장 가까운 트랙을 먼저 처리한다.
- 이후 매 단계마다 남은 요청 중 헤드에 가장 가까운 트랙을 선택한다.
SSTF는 단순하다.
"현재 헤드 위치에서 가장 가까운 트랙을 먼저 처리한다."
- 방향은 “우선순위에 영향을 줄 수 있지만”,SSTF 자체는 방향보다는 "거리"가 가장 중요하다.
- 현재 트랙 50에서 0방향으로 이동 중이다”라는 조건은 SCAN 계열 알고리즘에서는 의미가 크지만,
순수 SSTF에서는 참고 정보일 뿐 실제 결정에 영향을 주지 않음.
- 헤드 시작 위치: 50
- 디스크 범위: 0 ~ 150 (하지만 SSTF에는 직접 영향 없음)
- 대기 큐: 80, 20, 100, 30, 70, 130, 40
- 알고리즘: SSTF
- 목표: 요청들을 모두 처리할 때까지의 총 헤드 이동 거리 구하기
10 (50→40)
+ 10 (40→30)
+ 10 (30→20)
+ 50 (20→70)
+ 10 (70→80)
+ 20 (80→100)
+ 30 (100→130)
= 140- 총 이동거리: 140
10 + 10 + 10 + 50 + 10 + 20 + 30
3.SCAN(엘리베이터 알고리즘)
난이도 ⭐⭐
- 초기 헤드위치, 트랙이동방향 주어짐
- 디스크 헤드는 엘리베이터처럼 한 방향으로 이동하면서 요청을 처리하고,
- 끝에 도달하면 방향을 바꿔 되돌아오며 요청을 처리한다.
- SCAN은 반드시 한 쪽 끝(0번 트랙)까지 간다 (C-SCAN도 마찬가지이다.)
- 예: 헤드가 50에서 → 0 방향으로 이동 중이면
→ 50보다 작은 트랙들을 처리하고, 0까지 간 다음(끝까지 간다는게 중요) 방향을 바꿔 50보다 큰 요청들을 처리한다.
4. C-SCAN(Circular-Scan)
난이도 ⭐⭐⭐
- 초기 헤드위치, 트랙이동방향, 트랙 범위 주어짐
- C-SCAN은 끝까지 갔다가 방향을 바꾸지 않고, 끝에서 반대편으로 "점프"해서 같은 방향으로 다시 처리한다.
- 한 쪽 끝을 찍고 반대쪽 끝까지 간다. 즉, 같은 방향으로만 처리된다.
- C-SCAN은 끝까지 이동하는 것처럼 동작하므로, 요청이 있든 없든 끝까지 도달한 것으로 간주한다.
- 하지만 서비스 순서엔 요청이 있는 트랙만 포함된다.
C-SCAN은 요청이 없는 트랙은 "이동"만 하고 "처리"하지 않는다.
- 문제에서 '처리되는 트랙의 순서'를 물어보면 0을 포함해야 한다.
- 하지만, 헤드는 0까지 이동한 걸로 간주되지만, 0에 요청이 없으므로 → 서비스 순서에 포함되지 않음(서비스 순서 문제에서는 0을 안찍음)
5. LOOK
난이도 ⭐⭐
- 초기 헤드위치, 트랙이동방향 주어짐
- 끝까지 무조건 가지 않고 요청이 있는 마지막 트랙까지만 간다. (요청이 없는 트랙은 스킵한다.)
SCAN vs LOOK
SCAN은 헤드가 끝까지 왕복하며 모든 트랙을 훑고,
LOOK은 요청이 있는 구간까지만 왕복한다.
LOOK vs C-SCAN
LOOK은 요청이 있는 트랙까지만 헤드를 이동시키고 방향을 바꾸며,
C-SCAN은 요청 유무와 관계없이 끝까지 이동한 뒤 반대편 끝으로 점프한다.
LOOK vs C-LOOK
LOOK은 현재 방향으로 요청이 있는 가장 끝 트랙까지 이동 후 방향을 바꾸고,
C-LOOK은 현재 방향으로 요청이 있는 가장 끝 트랙까지 이동한 뒤 반대편 끝으로 점프해 같은 방향으로 계속 진행한다.
6. C-LOOK
난이도 ⭐⭐
- 초기 헤드 위치와 트랙 이동 방향이 주어진다.
- 헤드는 현재 방향으로 요청이 있는 가장 먼 트랙까지 이동한다.
- 끝까지 무조건 가지 않고, 요청이 없는 트랙은 스킵한다.
- 가장 먼 요청을 처리한 뒤에는 반대편 요청이 있는 가장 가까운 트랙으로 점프해서 다시 같은 방향으로 이동하며 처리한다.
- 즉, 방향을 바꾸지 않고, 요청이 있는 구간만 왕복 없이 처리하는 방식이다.
7. Eschenbach(에셴바흐 기법)
헤드가 진행하는 과정에서 각 실린더에 대해 디스크팩의 한 번의 회정 시간 동안만 입출력 요구들을 처리하는 기법이다.
즉, 한 회전 동안 서비스를 받지 못하는 요구들에 대한 처리는 다음으로 미루는 것이다.
이를 위해서는 한 실린더 내의 트랙이나 섹터들에 대한 요구들을 별도로 순서화 하는 메커니즘이 필요하다.
결국, 탐구시간의 최적화와 회전 지연 시간의 최적화를 동시에 추구하는 기본적인 기법인 것이다.
8. N-setp SCAN
SCAN의 무한 대기 발생 가능성을 제거한 것으로 SCAN보다 응답시간의 편차가 적고, SCAN과 같이 진행 방향상의 요청을 서비스하지만, 진행 중에 새로이 추가된 요청은 서비스하지 않고 다음 진행 시에 서비스하는 디스크 스케줄링 기법
참고 자료
- 1억뷰N잡 - 흥달쌤 계산식 특강