디스크 스케줄링 알고리즘 (FCFS, SSTF, SCAN, C-SCAN)

디스크 스케줄링 알고리즘

1. 디스크 스케줄링이란?

운영체제(OS)에서 디스크는 데이터를 읽고 쓰는 중요한 역할을 담당한다. 하지만, 여러 개의 입출력(I/O) 요청이 동시에 발생하면 디스크가 어떤 순서로 요청을 처리할지 결정해야 한다. 이때, 디스크 스케줄링(Disk Scheduling) 알고리즘을 사용하여 디스크 헤드의 이동을 최적화하고 성능을 향상시킬 수 있다.

 

✅ 디스크 스케줄링이 필요한 이유

• 디스크 접근 시간을 최소화하여 시스템 성능 향상
• I/O 대기 시간을 줄여 CPU가 효율적으로 작업할 수 있도록 지원
• 요청이 많은 환경에서 공정하게 자원을 배분

📌 실생활 예시: "엘리베이터 운영 방식"
엘리베이터가 여러 층에서 호출되었을 때, 호출된 순서대로 이동하면 비효율적이다. 대신, 가까운 층부터 이동하면 이동 거리가 줄어든다. 디스크도 같은 원리로, 적절한 순서로 요청을 처리해야 성능이 향상된다.

 

---

2. 디스크 스케줄링 알고리즘의 종류

운영체제에서 디스크 스케줄링 알고리즘은 여러 가지가 있으며, 각 알고리즘은 특정 환경에서 성능이 다르게 나타난다.

알고리즘	설명	장점	단점
FCFS (First Come, First Served)	먼저 요청된 순서대로 처리	구현이 간단함	탐색 시간이 비효율적일 수 있음
SSTF (Shortest Seek Time First)	현재 헤드 위치에서 가장 가까운 요청을 먼저 처리	탐색 시간 최소화 가능	특정 요청이 지나치게 오래 대기할 가능성(기아 상태)
SCAN (Elevator Algorithm)	디스크 헤드가 한쪽 방향으로 이동하며 요청을 처리하고 끝에 도달하면 반대 방향으로 이동	모든 요청이 공평하게 처리됨	끝쪽 요청이 우선 처리되기 어려울 수도 있음
C-SCAN (Circular SCAN)	SCAN과 비슷하지만, 한 방향으로만 이동하고 끝에 도달하면 처음으로 돌아감	요청이 균등하게 처리됨	끝에서 처음으로 돌아갈 때 추가적인 이동이 필요

 

---

3. 디스크 스케줄링 알고리즘 상세 설명

3-1. FCFS (First-Come, First-Served)

FIFO(선입선출) 방식으로 요청이 들어온 순서대로 처리하는 가장 단순한 디스크 스케줄링 알고리즘이다.

 

✅ FCFS의 특징

• 요청이 들어온 순서대로 처리하여 공정성을 유지
• 구현이 쉽고 간단한 방식

📌 예제 (초기 헤드 위치: 50, 요청 순서: 98, 183, 37, 122, 14, 124, 65, 67)

1. 50 → 98 (이동 거리: 48)
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)

📌 총 이동 거리: 48 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 643

🚨 단점: 디스크 헤드가 불필요하게 많이 이동할 가능성이 있음 (예: 183에서 37로 이동하는 경우)

3-2. SSTF (Shortest Seek Time First)

디스크 헤드가 현재 위치에서 가장 가까운 요청을 먼저 처리하는 방식이다.

 

✅ SSTF의 특징

• 디스크 이동 거리를 최소화하여 성능을 향상시킴
• 하지만 특정 요청이 계속 대기할 가능성이 있어 기아 현상(Starvation) 발생 가능

📌 예제 (초기 헤드 위치: 50, 요청 순서: 98, 183, 37, 122, 14, 124, 65, 67)

1. 현재 위치 50에서 가장 가까운 요청: 65 (이동 거리: 15)
2. 65에서 가장 가까운 요청: 67 (이동 거리: 2)
3. 67에서 가장 가까운 요청: 37 (이동 거리: 30)
4. 37에서 가장 가까운 요청: 14 (이동 거리: 23)
5. 14에서 가장 가까운 요청: 98 (이동 거리: 84)
6. 98에서 가장 가까운 요청: 122 (이동 거리: 24)
7. 122에서 가장 가까운 요청: 124 (이동 거리: 2)
8. 124에서 가장 가까운 요청: 183 (이동 거리: 59)

📌 총 이동 거리: 15 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 239 ➡ FCFS보다 이동 거리가 훨씬 적음!

🚨 단점: 멀리 있는 요청이 계속 대기하는 기아 현상(Starvation) 발생 가능

3-3. SCAN (엘리베이터 알고리즘)

디스크 헤드가 한 방향으로 이동하면서 요청을 처리한 후, 끝에 도달하면 반대 방향으로 이동하는 방식이다.

 

✅ SCAN의 특징

• 디스크 헤드 이동을 줄이면서도 공정성을 유지
• 특정 방향으로 이동하면서 처리하므로 요청이 밀리는 문제 해결

📌 예제 (초기 헤드 위치: 50, 요청 순서: 98, 183, 37, 122, 14, 124, 65, 67)

1. 50 → 37 (이동 거리: 13)
2. 37 → 14 (이동 거리: 23)
3. 14 → 0 (이동 거리: 14) → 끝에 도달 후 방향 변경
4. 0 → 65 (이동 거리: 65)
5. 65 → 67 (이동 거리: 2)
6. 67 → 98 (이동 거리: 31)
7. 98 → 122 (이동 거리: 24)
8. 122 → 124 (이동 거리: 2)
9. 124 → 183 (이동 거리: 59)

📌 총 이동 거리: 13 + 23 + 14 + 65 + 2 + 31 + 24 + 2 + 59 = 233

🚨 단점: 끝에 있는 요청은 대기 시간이 길어질 수 있음

3-4. C-SCAN (Circular SCAN)

SCAN 알고리즘과 유사하지만, 한 방향으로만 이동하며 요청을 처리하고 끝까지 도달하면 처음으로 돌아와 다시 진행하는 방식이다.

 

✅ C-SCAN의 특징

• 모든 요청을 처리하는 시간이 균일해짐
• 특정 요청이 너무 오래 대기하는 문제 해결

📌 예제 (초기 헤드 위치: 50, 요청 순서: 98, 183, 37, 122, 14, 124, 65, 67)

1. 50 → 65 (이동 거리: 15)
2. 65 → 67 (이동 거리: 2)
3. 67 → 98 (이동 거리: 31)
4. 98 → 122 (이동 거리: 24)
5. 122 → 124 (이동 거리: 2)
6. 124 → 183 (이동 거리: 59)
7. 183 → 0 (이동 거리: 183) → 처음으로 이동
8. 0 → 14 (이동 거리: 14)
9. 14 → 37 (이동 거리: 23)

📌 총 이동 거리: 15 + 2 + 31 + 24 + 2 + 59 + 183 + 14 + 23 = 353

🚨 단점: 불필요한 이동 거리가 발생할 수 있음

---

4. 어떤 알고리즘이 가장 좋을까?

• FCFS: 공정하지만 성능이 낮음
• SSTF: 성능이 좋지만 기아 현상 발생 가능
• SCAN: 전체적인 균형 유지
• C-SCAN: 일정한 응답 속도 보장

💡 운영체제와 환경에 따라 적절한 알고리즘을 선택해야 한다!