[알고리즘] scan (엘리베이터 알고리즘) 이란?

문득 엘리베이터의 작동방법이 궁금해져서 검색해 보다 scan이라는 알고리즘을 알게 됐습니다. 

scan이란?

scan은 디스크 헤드의 움직임을 최적화하여 읽기/쓰기 요청을 효율적으로 처리하는 방식입니다.
알고리즘의 작동 방식이 마치 엘리베이터가 한 방향으로 쭉 "스캔(scan)" 하면서 요청된 층들을 처리하는 모습과 유사하다고 해서 붙여진 이름이며 '엘리베이터 알고리즘'으로 불리기도 합니다.

 

SCAN 알고리즘의 작동 방식

1. 디스크 헤드는 현재 위치에서 한쪽 방향(안쪽 또는 바깥쪽)으로 이동을 시작합니다.
2. 이동하는 방향에 있는 요청들을 순서대로 처리합니다. 이때 요청의 도착 순서와는 상관없이 현재 헤드의 위치와 가까운 요청부터 처리하는 것이 아니라, 이동 방향에 따라 순서대로 처리합니다.
3. 디스크의 가장 끝 트랙에 도달하거나, 더 이상 해당 방향으로 처리할 요청이 없으면 헤드는 이동 방향을 반대로 바꿉니다.
4. 방향을 바꾼 후에는 다시 그 방향으로 이동하면서 요청들을 순서대로 처리합니다.
5. 이러한 방식으로 디스크 헤드는 양 끝을 오가며 모든 요청을 처리합니다

SCAN 알고리즘의 특징

SCAN 알고리즘의 장점:

• 기아 현상 방지: 디스크 전체를 스캔하며 요청을 처리하기 때문에 특정 트랙의 요청이 오랫동안 처리되지 못하는 기아(starvation) 현상을 방지할 수 있습니다.
• 비교적 균등한 대기 시간: FCFS(First Come First Served)나 SSTF(Shortest Seek Time First) 알고리즘에 비해 요청들의 대기 시간이 비교적 균등합니다.
• Seek Time 감소 효과: 헤드의 이동 방향을 일정하게 유지하면서 요청을 처리하므로 불필요한 헤드 이동을 줄여 Seek Time을 감소시키는 효과가 있습니다.

SCAN 알고리즘의 단점:

• 가장자리에 있는 요청의 불이익: 디스크 암이 한쪽 끝에 도달한 후 방향을 바꾸기 때문에, 가장자리에 있는 요청들은 중간에 있는 요청들보다 대기 시간이 길어질 수 있습니다.
• 방향 전환 시 약간의 비효율성: 끝까지 이동한 후 방향을 바꾸는 과정에서 실제 요청이 없는 트랙까지 이동할 수 있어 약간의 비효율성이 발생할 수 있습니다.

SCAN 알고리즘의 구현

아래 요구사항을 충족하는 scan 알고리즘을 구현해 보도록 하겠습니다. 

Initial direction: right

Initial position: 50

Requests: [82, 170, 43, 140, 24, 16, 190]

Processed order (SCAN): [82, 140, 170, 190, 43, 24, 16]

먼저 초기 위치가 50인 상태에서 진행 방향이 right이기 때문에 50보다 큰 숫자인 82, 140, 170, 190 순으로 차례대로 이동합니다. 더 이상의 큰 수는 없기 때문에 이동 방향을 left로 바꿉니다. left로 이동하면서 순서대로 처리되는 숫자는 43, 24, 16이기 때문에 최종 처리 order는 [82, 140, 170, 190, 43, 24, 16]과 같습니다.

 

이를 코틀린으로 구현해보겠습니다. 

fun scanAlgorithm(initialPosition: Int, requests: MutableList<Int>, direction: String): List<Int> {
    val sortedRequests = requests.sorted().distinct().toMutableList()
    val result = mutableListOf<Int>()
    var currentPosition = initialPosition

    if (direction == "right") {
        // 현재 위치부터 오른쪽 끝까지 처리
        sortedRequests.filter { it >= currentPosition }.forEach {
            result.add(it)
            currentPosition = it
        }
        // 왼쪽으로 이동하며 남은 요청 처리
        sortedRequests.filter { it < initialPosition }.reversed().forEach {
		    result.add(it)
            currentPosition = it
        }
    } else if (direction == "left") {
        // 같은 원리 
        sortedRequests.filter { it <= currentPosition }.reversed().forEach {
            result.add(it)
            currentPosition = it
        }
        sortedRequests.filter { it > initialPosition }.forEach {
			result.add(it)
            currentPosition = it
        }
    }
    return result
}

fun main() {
    val initialPosition = 50
    val requests = mutableListOf(82, 170, 43, 140, 24, 16, 190)
    val initialDirection = "right" // 또는 "left"

    val processedOrder = scanAlgorithm(initialPosition, requests, initialDirection)
    println("Initial position: $initialPosition")
    println("Requests: $requests")
    println("Initial direction: $initialDirection")
    println("Processed order (SCAN): $processedOrder")
}

C-SCAN 알고리즘의 탄생 배경

C-SCAN 알고리즘은 SCAN 알고리즘의 가장 큰 단점인 서비스 불균형 문제를 해결하기 위해 탄생했습니다. SCAN 알고리즘은 디스크 헤드가 한쪽 끝에서 다른 쪽 끝으로 이동하면서 요청을 처리한 후, 다시 반대 방향으로 이동합니다. 이 과정에서 헤드가 이동하는 방향의 끝부분에 있는 요청들은 중간에 있는 요청들보다 평균적으로 대기 시간이 길어지는 경향이 있습니다.

 

예를 들어, 오른쪽으로 이동하는 동안 도착한 오른쪽 끝의 요청은 바로 처리될 가능성이 높지만, 왼쪽 끝의 요청은 헤드가 오른쪽 끝까지 갔다가 다시 왼쪽으로 이동해야 처리될 수 있습니다. C-SCAN 알고리즘은 이러한 SCAN 알고리즘의 불균형성을 해소하고 모든 요청에 대해 보다 균등한 서비스 시간을 제공하고자 고안되었습니다.

특정 상황에서는 다른 양상을 보일 수 있으나 일반적인 경우 scan은 요청 수의 증가에 따라 평균 대기 시간이 선형적으로 증가하게 됩니다. 

반면 c-scan 알고리즘은 마치 원형을 돌듯 순환하기 때문에 평균 대기 시간이 대체로 완만하다는 특징이 있습니다.

일반적인 경향에서의 그래프

같은 문제를 c-scan으로 구현해보도록 하겠습니다. 

fun cScanAlgorithm(
    initialPosition: Int,
    requests: MutableList<Int>,
    direction: String,
    minTrack: Int = 0,
    maxTrack: Int = 199
): List<Int> {
    val sortedRequests = requests.sorted().distinct().toMutableList()
    val result = mutableListOf<Int>()
    var currentPosition = initialPosition

    if (direction == "right") {
        // 현재 위치부터 오른쪽 끝까지 처리
        sortedRequests.filter { it >= currentPosition }.forEach {
            result.add(it)
            currentPosition = it
        }
        // 오른쪽 끝으로 이동 (처리 없이)
        if (maxTrack > currentPosition) {
            currentPosition = maxTrack
        }
        // 왼쪽 끝으로 이동 (처리 없이)
        currentPosition = minTrack

        // 왼쪽 끝에서부터 오른쪽으로 처리
        sortedRequests.filter { it >= currentPosition }.forEach {
            if (!result.contains(it)) { // 이미 처리된 요청 제외
                result.add(it)
                currentPosition = it
            }
        }
    } else { // direction == "left"
        // 현재 위치부터 왼쪽 끝까지 처리 (내림차순)
        sortedRequests.filter { it <= currentPosition }.reversed().forEach {
            result.add(it)
            currentPosition = it
        }

        // 왼쪽 끝으로 이동 (처리 없이)
        if (minTrack < currentPosition) {
            currentPosition = minTrack
        }

        // 오른쪽 끝으로 이동 (처리 없이)
        currentPosition = maxTrack

        // 오른쪽 끝에서부터 왼쪽으로 처리 (내림차순)
        sortedRequests.filter { it <= currentPosition }.reversed().forEach {
            if (!result.contains(it)) { // 이미 처리된 요청 제외
                result.add(it)
                currentPosition = it
            }
        }
    }
    return result
}

c-scan에서 헤드는 항상 한 방향으로 디스크의 끝까지 이동한 후, 반대쪽 끝으로 돌아와 다시 스캔을 시작합니다. 이때, 이동하는 방향에 더 이상 처리할 요청이 없더라도 끝까지 이동합니다.

 

더 이상 요청이 없는데 왜 끝까지 이동 후 반대로 이동할까요? C-SCAN이 굳이 끝까지 이동하는 이유 중 하나는 예측 가능성입니다. 헤드의 움직임 범위를 디스크 전체로 고정함으로써 각 요청의 최대 대기 시간을 어느 정도 예측할 수 있습니다. 이는 실시간 시스템이나 서비스 품질 보장(QoS)이 중요한 환경에서 유리할 수 있습니다.