8-2. 디스크 스케줄링

1. 디스크 스케줄링의 필요성

디스크는 컴퓨터 시스템에서 데이터를 저장하는 중요한 장치입니다. 하드 디스크 드라이브(HDD)는 플래터(platter)라고 불리는 원판이 회전하면서 데이터를 읽고 쓰는 방식으로 작동합니다. 플래터 위에서 데이터를 읽거나 쓰기 위해 헤드가 움직여야 하는데, 이 과정에서 상당한 시간이 소요됩니다. 디스크 접근 시간은 탐색 시간 (seek time)(헤드를 원하는 트랙으로 이동하는 시간), 회전 지연 시간 (rotational latency)(원하는 섹터가 헤드 아래로 올 때까지 기다리는 시간), 그리고 전송 시간 (transfer time)(데이터를 실제로 읽거나 쓰는 시간)으로 구성됩니다. 이 중 탐색 시간과 회전 지연 시간은 디스크 I/O 성능에 큰 영향을 미칩니다.

디스크 스케줄링은 이러한 디스크 접근 시간을 최소화하여 디스크 I/O 성능을 향상시키는 것을 목표로 합니다. 여러 개의 I/O 요청이 대기 중일 때, 어떤 요청을 먼저 처리할지 결정하는 알고리즘을 말합니다. 효율적인 디스크 스케줄링은 시스템 전체의 응답 시간을 줄이고, 처리량을 늘리는 데 기여합니다.

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

다양한 디스크 스케줄링 알고리즘이 존재하며, 각 알고리즘은 성능과 구현 복잡성 면에서 차이를 보입니다. 각 알고리즘의 동작 방식과 성능 특징을 이해하는 것은 시스템의 성능을 최적화하는 데 필수적입니다.

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

FCFS는 가장 단순한 스케줄링 알고리즘으로, 요청이 들어온 순서대로 처리합니다. 요청 큐에 들어온 순서대로 헤드를 움직여 서비스를 제공합니다.

• 장점: 구현이 간단하고, 공정성을 보장합니다.
• 단점: 헤드 이동 거리가 길어져 성능 저하를 유발할 수 있습니다. 특히, 요청들이 디스크의 서로 다른 위치에 흩어져 있는 경우, 헤드가 불필요하게 많이 움직이게 됩니다.

2) SSTF (Shortest Seek Time First)

SSTF는 현재 헤드 위치에서 가장 가까운 트랙에 대한 요청을 먼저 처리하는 알고리즘입니다.

• 장점: 헤드 이동 거리를 최소화하여 평균 탐색 시간을 줄여줍니다.
• 단점: 기아(starvation) 현상이 발생할 수 있습니다. 멀리 떨어진 트랙에 대한 요청은 지속적으로 서비스 받지 못할 수 있습니다.

3) SCAN

SCAN 알고리즘은 엘리베이터 알고리즘이라고도 불립니다. 헤드가 디스크의 한쪽 끝에서 다른 쪽 끝으로 이동하면서, 그 경로 상에 있는 요청들을 처리합니다. 헤드가 디스크 끝에 도달하면 방향을 바꾸어 반대 방향으로 이동합니다.

• 장점: SSTF에 비해 기아 현상을 완화하고, 비교적 공정한 서비스를 제공합니다.
• 단점: 헤드가 디스크 끝까지 이동해야 하기 때문에, 요청이 디스크의 중앙 부분에 집중되어 있는 경우 비효율적일 수 있습니다.

4) C-SCAN (Circular SCAN)

C-SCAN은 SCAN 알고리즘의 변형입니다. SCAN과 마찬가지로 헤드가 한쪽 끝에서 다른 쪽 끝으로 이동하지만, 디스크의 끝에 도달하면 반대 방향으로 이동하는 대신, 반대쪽 끝으로 즉시 이동합니다. 이 과정에서 어떤 요청도 처리하지 않습니다.

• 장점: SCAN보다 균등한 서비스를 제공하며, 응답 시간의 편차를 줄입니다.
• 단점: 헤드가 디스크의 한쪽 끝에서 다른 쪽 끝으로 이동하는 동안에는 요청을 처리하지 않기 때문에, SCAN보다 약간의 오버헤드가 발생할 수 있습니다.

5) LOOK

LOOK 알고리즘은 SCAN 알고리즘과 유사하지만, 헤드가 디스크의 끝까지 이동하는 대신, 가장 안쪽 또는 바깥쪽 요청까지만 이동합니다. 즉, 헤드가 이동해야 할 요청이 더 이상 없을 때 방향을 전환합니다.

• 장점: SCAN보다 헤드 이동 거리를 줄여 성능을 향상시킵니다.
• 단점: SCAN과 동일한 기아 현상의 가능성이 있습니다.

6) C-LOOK (Circular LOOK)

C-LOOK은 LOOK 알고리즘의 변형입니다. LOOK과 마찬가지로 가장 안쪽 또는 바깥쪽 요청까지만 이동하지만, 해당 방향으로 요청을 처리한 후에는 헤드가 즉시 가장 안쪽 또는 바깥쪽 요청으로 이동합니다.

• 장점: C-SCAN과 마찬가지로 균등한 서비스와 더 짧은 헤드 이동 거리를 제공합니다.
• 단점: C-SCAN과 유사한 오버헤드가 발생할 수 있습니다.

3. 알고리즘 비교

각 디스크 스케줄링 알고리즘의 성능은 요청의 특성, 디스크의 트래픽, 그리고 디스크의 물리적 구조에 따라 달라집니다. 아래 표는 각 알고리즘의 특징을 요약하여 비교합니다.

4. 성능 평가 및 선택 기준

디스크 스케줄링 알고리즘의 성능은 다음과 같은 지표로 평가할 수 있습니다.

• 평균 탐색 시간: 헤드가 요청된 트랙을 찾는 데 걸리는 시간.
• 처리량: 단위 시간당 처리할 수 있는 요청의 수.
• 응답 시간: 요청이 도착한 시점부터 서비스가 완료될 때까지의 시간.
• 대기 시간: 요청이 큐에서 대기하는 시간.
• 디스크 활용률: 디스크가 실제로 데이터를 읽거나 쓰는 시간의 비율.

어떤 알고리즘을 선택할지는 시스템의 특성과 요구 사항에 따라 달라집니다.

• 성능 중시 시스템: SSTF, LOOK, C-LOOK 알고리즘이 유리할 수 있습니다. 하지만, 기아 현상을 방지하기 위해 추가적인 메커니즘을 고려해야 합니다.
• 공정성 중시 시스템: SCAN, C-SCAN 알고리즘이 적합합니다.
• 단순성 중시 시스템: FCFS 알고리즘을 사용할 수 있지만, 성능 저하를 감수해야 합니다.

5. 실무에서의 고려 사항

실무 환경에서는 디스크 스케줄링 알고리즘의 선택 외에도 다음과 같은 사항을 고려해야 합니다.

• 하드웨어 특성: SSD(Solid State Drive)와 HDD의 성능 특성이 다르므로, 사용하는 저장 장치에 맞는 스케줄링 알고리즘을 선택해야 합니다. SSD는 임의 접근 속도가 빠르므로 SSTF와 같은 알고리즘이 HDD보다 효과적이지 않을 수 있습니다.
• 운영체제 지원: 대부분의 운영체제는 다양한 디스크 스케줄링 알고리즘을 지원하며, 사용자는 시스템 설정에서 알고리즘을 선택하거나 변경할 수 있습니다.
• 혼합된 워크로드: 다양한 유형의 I/O 요청이 동시에 발생하는 환경에서는, 특정 알고리즘이 모든 요청에 대해 최적의 성능을 제공하지 못할 수 있습니다. 이 경우, 워크로드의 특성에 따라 동적으로 알고리즘을 변경하거나, 여러 알고리즘을 조합하는 방법을 고려할 수 있습니다.
• 예측 기반 스케줄링: 최신 시스템에서는 I/O 요청의 패턴을 예측하여 스케줄링을 최적화하는 기술이 사용되기도 합니다. 이러한 기술은 헤드 이동 거리를 더욱 줄이고, 디스크 성능을 향상시킬 수 있습니다.

6. 결론

디스크 스케줄링은 디스크 I/O 성능을 향상시키는 핵심 기술입니다. 다양한 알고리즘을 이해하고, 시스템 환경에 맞는 알고리즘을 선택하는 것은 효율적인 운영체제를 구축하는 데 필수적입니다. 각 알고리즘의 장단점을 고려하고, 시스템의 요구 사항과 하드웨어 특성을 종합적으로 고려하여 최적의 선택을 해야 합니다.