디스크 성능 최적화를 위한 스케줄링 알고리즘 분석

1. 개요

디스크 스케줄링 알고리즘은 디스크 I/O 요청을 효율적으로 처리하기 위해 디스크 헤드의 이동을 최적화하는 기법이다. 디스크는 파일 시스템과 데이터베이스 등 다양한 애플리케이션에서 중요한 저장 장치로 사용되며, 성능 향상을 위해 디스크 헤드가 처리할 요청 순서를 결정하는 알고리즘이 필요하다.

이 글에서는 다양한 디스크 스케줄링 알고리즘과 그 원리, 특징, 장단점을 설명한다.

2. 디스크 스케줄링 알고리즘의 필요성

1. 효율성 극대화
   • 디스크 헤드 이동 거리를 최소화하여 평균 응답 시간을 줄인다.
2. 공평성 확보
   • 요청 처리에서 특정 요청이 무기한 대기하는 문제를 방지한다.
3. 시스템 성능 향상
   • 빠른 디스크 접근 시간과 높은 처리량을 제공한다.

3. 주요 디스크 스케줄링 알고리즘

3.1. FCFS(First Come First Serve)

• 원리: 요청이 들어온 순서대로 처리한다.
• 장점: 구현이 단순하며 공평하다.
• 단점: 디스크 헤드의 이동이 최적화되지 않아 비효율적이다.
• 예시: 요청 순서가 [98, 183, 37, 122, 14, 124, 65, 67]이고 헤드가 53에서 시작하면, 헤드 이동 경로는 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67이다.

3.2. SSTF(Shortest Seek Time First)

• 원리: 디스크 헤드와 가장 가까운 요청을 우선 처리한다.
• 장점: 헤드 이동 거리가 감소하여 평균 응답 시간이 줄어든다.
• 단점: 가까운 요청만 처리하므로 멀리 있는 요청은 대기 시간이 길어질 수 있다.
• 예시: 요청 순서가 [98, 183, 37, 122, 14, 124, 65, 67]이고 헤드가 53에서 시작하면, 헤드는 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183 순으로 이동한다.

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

• 원리: 디스크 헤드는 한 방향으로 이동하며 요청을 처리하고, 끝에 도달하면 방향을 바꾼다.
• 장점: 헤드 이동 거리를 줄이며, 요청의 대기 시간을 비교적 균등하게 한다.
• 단점: 끝부분 요청의 처리 시간이 길어질 수 있다.
• 예시: 요청 순서가 [98, 183, 37, 122, 14, 124, 65, 67]이고 헤드가 53에서 시작하여 안쪽 방향으로 이동하면, 경로는 53 → 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183이다.

3.4. C-SCAN(Circular SCAN)

• 원리: SCAN과 유사하지만, 끝에 도달한 후 처음으로 되돌아가 다시 같은 방향으로 이동하며 요청을 처리한다.
• 장점: 끝부분 요청의 처리 지연 문제를 완화한다.
• 단점: SCAN보다 평균 응답 시간이 다소 증가할 수 있다.
• 예시: 요청 순서가 [98, 183, 37, 122, 14, 124, 65, 67]이고 헤드가 53에서 시작하면, 경로는 53 → 65 → 67 → 98 → 122 → 124 → 183 → 14 → 37이다.

3.5. LOOK

• 원리: SCAN과 유사하지만, 끝까지 이동하지 않고 마지막 요청까지만 이동한다.
• 장점: 불필요한 헤드 이동을 줄인다.
• 단점: 구현이 SCAN보다 약간 복잡하다.
• 예시: 요청 순서가 [98, 183, 37, 122, 14, 124, 65, 67]이고 헤드가 53에서 시작하면, 경로는 53 → 65 → 67 → 98 → 122 → 124 → 183 → 37 → 14이다.

3.6. C-LOOK(Circular LOOK)

• 원리: LOOK과 유사하지만, 한 방향으로만 이동하고 마지막 요청을 처리한 후 처음으로 되돌아간다.
• 장점: 끝부분 요청 처리 문제를 완화한다.
• 단점: SCAN 및 LOOK보다 구현이 더 복잡하다.
• 예시: 요청 순서가 [98, 183, 37, 122, 14, 124, 65, 67]이고 헤드가 53에서 시작하면, 경로는 53 → 65 → 67 → 98 → 122 → 124 → 183 → 14 → 37이다.

4. 디스크 스케줄링 알고리즘의 비교

알고리즘	장점	단점
FCFS	공평하며 구현이 간단하다	헤드 이동이 비효율적
SSTF	헤드 이동 거리가 최소화된다	기아 문제 발생 가능
SCAN	공평하며 헤드 이동 거리를 줄인다	끝부분 요청 지연 가능
C-SCAN	끝부분 요청 지연 문제 완화	SCAN보다 평균 응답 시간 증가 가능
LOOK	불필요한 헤드 이동 감소	끝부분 요청 지연 가능
C-LOOK	끝부분 요청 지연 문제 완화	구현 복잡성 증가

5. 디스크 스케줄링 알고리즘의 선택 기준

1. 시스템 요구사항: 응답 시간이 중요한지, 처리량이 중요한지에 따라 선택한다.
2. 입출력 패턴: 요청이 랜덤한지, 순차적인지에 따라 적합한 알고리즘을 선택한다.
3. 공평성: 특정 요청의 대기 시간을 줄이려면 SCAN이나 C-SCAN을 고려한다.
4. 복잡성: 구현의 단순함이 중요한 경우 FCFS나 SSTF를 선택할 수 있다.

6. 결론

디스크 스케줄링 알고리즘은 디스크 성능을 최적화하는 데 중요한 역할을 한다. 각 알고리즘은 특정 시나리오에 적합하며, 시스템 요구사항과 요청 패턴을 고려하여 적절한 알고리즘을 선택해야 한다. 디스크 기술이 발전함에 따라 이러한 알고리즘은 SSD와 같은 새로운 저장 장치에서도 응용되고 있으며, 효율적인 데이터 처리를 위해 계속해서 연구되고 있다.