디스크 스케줄링
디스크 스케줄링
디스크 스케줄링(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 + 303.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
난이도 ⭐⭐
- 초기 헤드 위치와 트랙 이동 방향이 주어진다.
- 헤드는 현재 방향으로 요청이 있는 가장 먼 트랙까지 이동한다.
- 끝까지 무조건 가지 않고, 요청이 없는 트랙은 스킵한다.
- 가장 먼 요청을 처리한 뒤에는 반대편 요청이 있는 가장 가까운 트랙으로 점프해서 다시 같은 방향으로 이동하며 처리한다.
- 즉, 방향을 바꾸지 않고, 요청이 있는 구간만 왕복 없이 처리하는 방식이다.
