정보처리산업기사, 정보처리기사 - 디스크 스케줄링 SSTF(Shortest Seek Time First) 알고리즘 집중 탐색!!

※ 공부 내용의 복습 개념으로 정리된 글입니다.

 

SSTF(Shortest Seek Time First) 알고리즘

SSTF 알고리즘은 디스크 요청 중 현재 헤드 위치에서 가장 짧은 탐색 거리를 갖는 요청을 먼저 처리하는 방식입니다.

즉, 디스크 헤드가 이동해야 하는 거리가 가장 짧은 요청을 우선적으로 처리하여 디스크 접근 시간을 최소화하는 것이 목표입니다.

 

SSTF의 작동 원리

1. 현재 디스크 헤드 위치 확인 : 현재 디스크 헤드가 위치한 트랙을 기준으로 합니다.
2. 요청 목록 확인 : 처리해야 할 디스크 요청들의 목록을 확인합니다.
3. 최단 거리 요청 선택 : 현재 디스크 헤드 위치에서 가장 가까운 요청을 선택합니다.
4. 요청 처리 : 선택된 요청을 처리한 후, 디스크 헤드를 해당 위치로 이동합니다.
5. 반복 : 처리해야 할 요청이 더 이상 없을 때까지 위 과정을 반복합니다.

 

 

SSTF의 장단점

• 장점
  1. 탐색 시간 최소화
     디스크 헤드의 이동 거리를 줄여 탐색 시간을 최소화할 수 있습니다.
  2. 간단한 구현
     SSTF 알고리즘은 구현이 비교적 간단하여 많은 시스템에서 쉽게 적용할 수 있습니다.
• 단점
  1. 기아 문제(Starvation)
     특정 요청이 계속해서 뒤로 밀릴 수 있습니다.
     예를 들어, 계속해서 가까운 요청이 들어오는 경우 먼 요청은 처리되지 못하고 대기 상태에 빠질 수 있습니다.
  2. 최적 해법이 아닙니다.
     항상 최적의 성능을 보장하지 않습니다.
     일부 경우 다른 알고리즘(FIFO, SCAN 등)이 더 나은 성능을 보일 수 있습니다.

 

※ Starvation 

Starvation(기아 현상)은 컴퓨터 시스템에서 특정 작업이나 프로세스가 필요한 자원을 오랫동안 할당받지 못해 무한정 대기 상태에 빠지는 문제를 의미합니다.

 

SSTF 예시

디스크 요청이 [53, 98, 183, 37, 122, 14, 124, 65, 67] 순으로 들어오고,

현재 디스크가 헤드가 53번 트랙에 위치해 있다고 가정해보겠씁니다.

디스크 요청 : 98, 183, 37, 122, 14, 124, 65, 67

 

1. 이동 현황

2. 작동 방식

1. 현재 헤드 위치 : 53
2. 가장 가까운 요청 : 65 (거리 12)
3. 현재 헤드 위치 : 53 → 65
4. 가장 가까운 요청 : 67 (거리 2)
5. 위 과정을 반복하여 모든 요청을 처리합니다.

요청 처리 순서 : 53 → 65  → 67  → 37  → 14  → 98  → 122  → 124  → 183

총 이동 거리 : 12 + 2  + 30  + 23  + 84  + 24  + 2  + 59 = 236