SCAN 스케줄링 알고리즘은 디스크 스케줄링에서 요청이 들어온 순서대로 처리하는 FCFS(First Come, First Served) 방식에서 발생할 수 있는 기아 상태(Starvation)를 해결하기 위해 개발되었습니다. 아래에서는 SCAN이 FCFS의 단점을 어떻게 개선했는지 설명합니다.
SCAN 스케줄링 알고리즘의 목적
• FCFS(First Come, First Served): 디스크 스케줄링에서 요청이 들어온 순서대로 처리하는 방식입니다. 공평하게 요청을 처리하는 장점이 있으나, 특정 트랙에서 자주 요청이 발생할 경우 바깥쪽이나 안쪽 트랙의 요청이 오래 대기하게 되어 기아 상태가 발생할 수 있습니다.
• SCAN(엘리베이터 알고리즘): 디스크 헤드가 한쪽 끝에서 다른 쪽 끝으로 이동하면서 요청을 처리하고, 끝에 도달하면 반대 방향으로 이동하여 대기 중인 요청을 처리하는 방식입니다. 특정 요청이 계속 대기하지 않도록 하여 기아 상태를 완화하는 목적이 있습니다.개념
• FCFS: 요청이 들어온 순서대로 처리하지만, 트랙 위치와 상관없이 순차적으로 처리하므로 특정 위치의 요청이 계속 지연될 수 있습니다.
• SCAN: 디스크 헤드가 이동할 때 양쪽 끝까지 왕복하며 중간의 요청들을 처리합니다. 이를 통해 트랙이 멀리 떨어져 있는 요청들도 이동 중에 순차적으로 처리하게 되어 기아 상태가 줄어듭니다.원리 및 작동 순서
SCAN의 작동 원리는 다음과 같습니다:
1. 디스크 헤드가 시작 위치에서 한쪽 방향으로 이동하며 해당 방향에 있는 모든 요청을 처리합니다.
2. 해당 방향 끝에 도달하면 방향을 바꾸어 반대쪽 끝으로 이동하며 그 방향에 위치한 요청을 처리합니다.
3. 이 과정을 반복하여 대기 중인 모든 요청을 처리합니다.장점
• 기아 상태 개선: SCAN 알고리즘은 헤드가 이동하는 방향에 따라 요청을 처리하기 때문에, 모든 요청이 일정한 시간 내에 처리됩니다. 이는 FCFS에서 발생할 수 있는 기아 상태를 완화합니다.
• 응답 시간의 예측 가능성: SCAN은 일정한 패턴으로 헤드가 이동하므로, 요청 처리 시간을 예측할 수 있어 응답 시간이 비교적 안정적입니다.단점
• 초기 대기 시간 증가 가능성: 헤드의 이동 방향에 따라 한쪽 끝에 있는 요청이 처리되는 동안 반대쪽 끝에 있는 요청이 오래 기다려야 할 수 있습니다.
• 비효율적인 이동: 끝에서 끝으로 이동하는 방식이므로, 디스크 헤드의 전체 이동 거리가 증가할 수 있습니다.FCFS와 SCAN의 비교
FCFS와 비교 시 SCAN은 기아 상태를 해결할 수 있는 장점이 있지만, 특정 상황에서는 여전히 한쪽 끝에서 대기하는 요청이 지연될 수 있습니다. 이러한 문제를 해결하기 위해 C-SCAN(Circular SCAN)이라는 알고리즘이 등장하였습니다.
개선된 전망 및 다른 알고리즘
• C-SCAN (Circular SCAN): SCAN의 개선된 버전으로, 한 방향으로만 이동하며 요청을 처리하고, 끝에 도달하면 반대쪽 끝으로 이동하여 다시 같은 방향으로 요청을 처리하는 방식입니다.