디스크 스케줄링 완벽 가이드

운영체제가 하드디스크의 읽기/쓰기 요청을 효율적으로 처리하는 방법을 알아봅니다. 디스크 구조부터 FCFS, SSTF, SCAN, LOOK 알고리즘까지 실무 예제와 함께 쉽게 설명합니다.

1. 디스크 구조

신입 개발자 김개발 씨가 서버실에서 하드디스크를 처음 봤습니다. "이 동그란 원판들이 어떻게 데이터를 저장하는 거죠?" 옆에 있던 박시니어 씨가 웃으며 대답했습니다.

"디스크 스케줄링을 이해하려면 먼저 이 구조부터 알아야 해요."

하드디스크는 플래터, 트랙, 섹터라는 세 가지 핵심 구성 요소로 이루어져 있습니다. 마치 LP 레코드판처럼 생긴 원판 위에 동심원 형태의 트랙이 있고, 각 트랙은 부채꼴 모양의 섹터로 나뉘어 있습니다.

이 구조를 이해하면 왜 디스크 접근 시간이 오래 걸리는지, 그리고 왜 스케줄링이 필요한지 알 수 있습니다.

다음 코드를 살펴봅시다.

# 디스크 구조를 표현하는 간단한 클래스
class DiskStructure:
    def __init__(self, platters=2, tracks_per_surface=1000, sectors_per_track=63):
        self.platters = platters              # 플래터 개수
        self.surfaces = platters * 2           # 표면 개수 (양면)
        self.tracks = tracks_per_surface       # 표면당 트랙 수
        self.sectors = sectors_per_track       # 트랙당 섹터 수

    def total_capacity(self, bytes_per_sector=512):
        # 총 용량 계산: 표면 x 트랙 x 섹터 x 섹터크기
        total_sectors = self.surfaces * self.tracks * self.sectors
        return total_sectors * bytes_per_sector

    def locate_sector(self, logical_address):
        # 논리 주소를 물리 위치로 변환
        surface = logical_address // (self.tracks * self.sectors)
        track = (logical_address // self.sectors) % self.tracks
        sector = logical_address % self.sectors
        return {"surface": surface, "track": track, "sector": sector}

김개발 씨는 입사 첫 주에 데이터베이스 성능 이슈를 담당하게 되었습니다. 쿼리가 느리다는 보고가 계속 들어왔는데, 원인을 찾다 보니 디스크 I/O가 병목이라는 것을 알게 되었습니다.

하지만 디스크가 어떻게 동작하는지 몰랐기에 어디서부터 손을 대야 할지 막막했습니다. 박시니어 씨가 화이트보드 앞에 섰습니다.

"디스크를 이해하려면 LP 레코드판을 떠올려 보세요." 하드디스크의 가장 기본적인 구성 요소는 플래터입니다. 플래터는 얇은 원형 금속판으로, 자성 물질로 코팅되어 있습니다.

마치 CD나 LP판처럼 생겼지만, 훨씬 더 정밀하게 만들어졌습니다. 일반적인 하드디스크에는 여러 장의 플래터가 층층이 쌓여 있습니다.

각 플래터의 표면에는 트랙이라는 동심원이 존재합니다. 레코드판의 홈처럼 생겼다고 생각하면 됩니다.

바깥쪽 트랙은 번호가 작고, 안쪽으로 갈수록 트랙 번호가 커집니다. 현대 하드디스크는 수만 개의 트랙을 가지고 있습니다.

트랙은 다시 섹터라는 부채꼴 조각으로 나뉩니다. 섹터가 바로 데이터가 실제로 저장되는 최소 단위입니다.

전통적으로 한 섹터의 크기는 512바이트였지만, 최근에는 4KB 섹터를 사용하는 디스크도 많습니다. 그렇다면 데이터를 읽으려면 어떻게 해야 할까요?

여기서 읽기/쓰기 헤드가 등장합니다. 헤드는 플래터 위를 떠다니며 데이터를 읽거나 씁니다.

레코드 플레이어의 바늘과 비슷하지만, 실제로 플래터에 닿지 않고 공기층 위에 떠 있습니다. 각 플래터의 표면마다 하나씩 헤드가 배치됩니다.

헤드들은 디스크 암이라는 구조물에 함께 연결되어 있습니다. 마치 빗처럼 생긴 이 암은 모든 헤드를 동시에 움직입니다.

따라서 한 헤드가 100번 트랙에 있으면, 다른 모든 헤드도 100번 트랙에 위치하게 됩니다. 모든 플래터의 같은 번호 트랙들을 묶어서 실린더라고 부릅니다.

이 개념은 나중에 디스크 스케줄링을 이해할 때 중요해집니다. 실린더 단위로 데이터를 저장하면 헤드를 움직이지 않고도 연속해서 데이터를 읽을 수 있기 때문입니다.

박시니어 씨가 덧붙였습니다. "이제 왜 디스크가 느린지 이해가 되죠?

원하는 데이터에 접근하려면 헤드가 해당 트랙으로 이동하고, 플래터가 회전해서 원하는 섹터가 헤드 아래로 와야 합니다." 김개발 씨는 고개를 끄덕였습니다. 물리적인 부품이 움직여야 하니 당연히 시간이 걸릴 수밖에 없었습니다.

그리고 이 시간을 줄이는 것이 바로 디스크 스케줄링의 목표라는 것을 알게 되었습니다.

실전 팁

💡 - 플래터 수가 많을수록 용량은 커지지만 발열과 소음도 증가합니다

SSD는 이런 기계적 구조가 없어서 빠르지만, 여전히 많은 서버가 HDD를 사용합니다
실린더 개념을 이해하면 디스크 최적화의 핵심을 파악할 수 있습니다

2. 디스크 접근 시간

김개발 씨가 성능 모니터링 도구에서 디스크 지연 시간이 15ms라는 수치를 보았습니다. "이 15밀리초가 어디서 오는 거죠?" 박시니어 씨가 화이트보드에 세 개의 박스를 그리며 설명을 시작했습니다.

"이 시간은 크게 세 가지 요소로 나뉘어요."

디스크 접근 시간은 탐색 시간, 회전 지연, 전송 시간의 합으로 구성됩니다. 탐색 시간은 헤드가 원하는 트랙으로 이동하는 시간이고, 회전 지연은 플래터가 돌아 원하는 섹터가 헤드 아래로 올 때까지 기다리는 시간입니다.

이 중에서 탐색 시간이 가장 크고, 디스크 스케줄링은 바로 이 탐색 시간을 최소화하는 것이 목표입니다.

다음 코드를 살펴봅시다.

# 디스크 접근 시간 계산기
class DiskAccessTime:
    def __init__(self, rpm=7200, avg_seek_ms=9, transfer_rate_mbps=150):
        self.rpm = rpm                          # 분당 회전수
        self.avg_seek_ms = avg_seek_ms          # 평균 탐색 시간 (ms)
        self.transfer_rate = transfer_rate_mbps # 전송 속도 (MB/s)

    def rotational_latency(self):
        # 회전 지연 = 평균적으로 반 바퀴 회전하는 시간
        rotation_time_ms = (60 / self.rpm) * 1000
        return rotation_time_ms / 2

    def transfer_time(self, size_kb):
        # 전송 시간 계산
        return (size_kb / 1024) / self.transfer_rate * 1000

    def total_access_time(self, size_kb=4):
        seek = self.avg_seek_ms
        rotation = self.rotational_latency()
        transfer = self.transfer_time(size_kb)
        return {"seek": seek, "rotation": rotation,
                "transfer": transfer, "total": seek + rotation + transfer}

김개발 씨는 데이터베이스 쿼리가 왜 이렇게 느린지 분석하고 있었습니다. 메모리 캐시 히트율은 높은데도 일부 쿼리는 여전히 느렸습니다.

박시니어 씨는 이것이 디스크 I/O 때문이라고 설명했습니다. "디스크에서 데이터를 읽으려면 세 단계를 거쳐야 해요." 첫 번째는 **탐색 시간(Seek Time)**입니다.

읽기/쓰기 헤드가 현재 위치에서 원하는 트랙까지 이동하는 데 걸리는 시간입니다. 마치 도서관에서 원하는 책장까지 걸어가는 것과 같습니다.

책장이 멀리 있으면 더 오래 걸리겠죠? 탐색 시간은 이동해야 할 트랙 수에 따라 달라집니다.

바로 옆 트랙으로 이동하는 것은 빠르지만, 디스크 가장 바깥쪽에서 가장 안쪽으로 이동하는 것은 오래 걸립니다. 일반적인 하드디스크의 평균 탐색 시간은 8~12밀리초 정도입니다.

두 번째는 **회전 지연(Rotational Latency)**입니다. 헤드가 원하는 트랙에 도착했더라도, 아직 원하는 섹터가 헤드 아래에 있지 않을 수 있습니다.

플래터가 회전해서 해당 섹터가 헤드 아래로 올 때까지 기다려야 합니다. 회전 지연은 디스크의 RPM(분당 회전수)에 따라 결정됩니다.

7200 RPM 디스크는 1분에 7200번, 즉 1초에 120번 회전합니다. 한 바퀴 도는 데 약 8.3밀리초가 걸립니다.

평균적으로는 반 바퀴를 기다리므로 약 4밀리초가 회전 지연이 됩니다. 세 번째는 **전송 시간(Transfer Time)**입니다.

원하는 섹터가 헤드 아래로 왔을 때, 실제로 데이터를 읽어서 메모리로 전송하는 시간입니다. 현대 하드디스크의 전송 속도는 100~200MB/s 정도입니다.

4KB 데이터를 전송하는 데는 0.02밀리초 정도밖에 걸리지 않습니다. 박시니어 씨가 계산해 보았습니다.

"7200 RPM 디스크에서 4KB를 읽는다고 하면, 탐색 시간 9ms, 회전 지연 4ms, 전송 시간 0.02ms로 총 약 13ms가 걸려요." 여기서 중요한 점이 드러납니다. 전체 접근 시간 중 탐색 시간이 약 70%를 차지합니다.

회전 지연은 디스크 RPM으로 결정되어 바꿀 수 없고, 전송 시간은 이미 매우 짧습니다. 결국 디스크 성능을 높이려면 탐색 시간을 줄여야 합니다.

"그래서 디스크 스케줄링이 중요한 거예요. 여러 요청이 동시에 들어왔을 때 어떤 순서로 처리하느냐에 따라 헤드의 총 이동 거리가 크게 달라지거든요." 김개발 씨가 물었습니다.

"그럼 어떤 순서로 처리해야 가장 효율적인가요?" 박시니어 씨가 웃으며 대답했습니다. "바로 그걸 결정하는 게 디스크 스케줄링 알고리즘이에요.

이제 하나씩 알아볼까요?"

실전 팁

💡 - 15000 RPM 고속 디스크는 회전 지연이 절반으로 줄어들지만 가격이 비쌉니다

SSD는 기계적 동작이 없어 접근 시간이 0.1ms 이하입니다
순차 읽기가 랜덤 읽기보다 빠른 이유가 바로 탐색 시간 때문입니다

3. FCFS 스케줄링

"가장 간단한 방법부터 시작해볼까요?" 박시니어 씨가 말했습니다. 김개발 씨 앞에는 53, 98, 183, 37, 122, 14, 124, 65, 67이라는 트랙 요청 목록이 있었습니다.

"먼저 들어온 요청을 먼저 처리하면 되지 않나요?" 김개발 씨의 질문에 박시니어 씨가 고개를 끄덕이며 대답했습니다.

**FCFS(First Come First Served)**는 이름 그대로 먼저 도착한 요청을 먼저 처리하는 가장 단순한 스케줄링 방식입니다. 마치 은행 창구에서 번호표 순서대로 고객을 응대하는 것과 같습니다.

구현이 간단하고 공정하지만, 헤드가 디스크 전체를 왔다 갔다 하면서 비효율적으로 움직일 수 있습니다.

다음 코드를 살펴봅시다.

# FCFS 디스크 스케줄링 알고리즘
def fcfs_scheduling(requests, head_position):
    """
    FCFS: 요청이 들어온 순서대로 처리
    requests: 트랙 요청 리스트
    head_position: 현재 헤드 위치
    """
    sequence = [head_position]  # 처리 순서 기록
    total_movement = 0          # 총 이동 거리
    current = head_position

    for track in requests:
        movement = abs(track - current)  # 이동 거리 계산
        total_movement += movement
        sequence.append(track)
        current = track

    return {"sequence": sequence, "total_movement": total_movement}

# 예시 실행
requests = [98, 183, 37, 122, 14, 124, 65, 67]
result = fcfs_scheduling(requests, head_position=53)
print(f"처리 순서: {result['sequence']}")  # [53, 98, 183, 37, ...]
print(f"총 헤드 이동: {result['total_movement']} 트랙")  # 640 트랙

김개발 씨는 처음으로 디스크 스케줄링 알고리즘을 배우게 되었습니다. 박시니어 씨는 가장 기본적인 것부터 시작하자고 했습니다.

"FCFS는 말 그대로 선착순이에요. 먼저 온 요청을 먼저 처리합니다." 이해하기 쉽게 은행 창구를 예로 들어봅시다.

고객들이 번호표를 뽑고 순서대로 창구에서 업무를 봅니다. 1번 고객, 2번 고객, 3번 고객 순서대로 처리됩니다.

뒤에 온 사람이 간단한 업무라고 해서 먼저 처리받지 않습니다. 이것이 바로 FCFS 방식입니다.

디스크에 적용해보면 이렇습니다. 현재 헤드가 53번 트랙에 있고, 98, 183, 37, 122, 14, 124, 65, 67번 트랙에 대한 읽기 요청이 순서대로 들어왔다고 가정합니다.

FCFS 방식에서는 이 요청들을 들어온 순서 그대로 처리합니다. 53에서 98로, 98에서 183으로, 183에서 37로, 이런 식으로 진행됩니다.

헤드의 이동 거리를 계산해보면 놀라운 결과가 나옵니다. 53에서 98까지 45트랙, 98에서 183까지 85트랙, 183에서 37까지 146트랙...

이렇게 계속 더하면 총 640트랙을 이동하게 됩니다. 박시니어 씨가 그림을 그려 보여주었습니다.

"보세요, 헤드가 디스크 안쪽에서 바깥쪽으로, 다시 안쪽으로 왔다 갔다 하고 있어요. 엄청난 낭비죠." FCFS의 장점은 구현이 매우 간단하다는 것입니다.

큐에 들어온 순서대로 처리하면 되니까요. 또한 공정합니다.

모든 요청이 도착 순서대로 처리되므로 특정 요청이 무한정 기다리는 기아 현상이 발생하지 않습니다. 하지만 단점도 명확합니다.

헤드가 불필요하게 많이 움직입니다. 우리 예시에서 37번 트랙과 14번 트랙 요청이 가까이 있는데도, 중간에 다른 요청들이 있어서 따로따로 방문합니다.

이것은 마치 서울에서 부산으로 갔다가, 다시 대전으로 갔다가, 또 부산으로 가는 것과 같습니다. "그럼 FCFS는 언제 쓰는 게 좋을까요?" 김개발 씨가 물었습니다.

디스크 부하가 적을 때는 FCFS로도 충분합니다. 요청이 하나씩 들어오면 어차피 순서대로 처리해야 하니까요.

하지만 요청이 많이 몰리는 상황에서는 다른 알고리즘이 필요합니다. 김개발 씨가 코드를 보며 말했습니다.

"단순하긴 한데, 뭔가 비효율적이라는 게 느껴지네요." 박시니어 씨가 고개를 끄덕였습니다. "맞아요.

그래서 더 똑똑한 방법들이 나온 거예요. 다음으로 SSTF를 알아볼까요?"

실전 팁

💡 - FCFS는 디스크 부하가 낮을 때 적합합니다

기아 현상이 없다는 장점이 있어 공정성이 중요할 때 고려할 수 있습니다
실제 운영체제에서는 거의 사용되지 않습니다

4. SSTF 스케줄링

"640트랙이나 움직이다니, 분명 더 좋은 방법이 있을 것 같은데요." 김개발 씨가 말했습니다. 박시니어 씨가 웃으며 대답했습니다.

"당연히 있죠. 현재 위치에서 가장 가까운 요청부터 처리하면 어떨까요?" 이것이 바로 SSTF, 최단 탐색 시간 우선 알고리즘입니다.

**SSTF(Shortest Seek Time First)**는 현재 헤드 위치에서 가장 가까운 트랙 요청을 먼저 처리하는 방식입니다. 마치 배달 기사가 현재 위치에서 가장 가까운 배달지부터 방문하는 것과 같습니다.

헤드 이동 거리가 크게 줄어들지만, 멀리 있는 요청이 계속 무시되는 기아 현상이 발생할 수 있습니다.

다음 코드를 살펴봅시다.

# SSTF 디스크 스케줄링 알고리즘
def sstf_scheduling(requests, head_position):
    """
    SSTF: 현재 위치에서 가장 가까운 요청부터 처리
    """
    pending = requests.copy()   # 처리 대기 중인 요청들
    sequence = [head_position]
    total_movement = 0
    current = head_position

    while pending:
        # 가장 가까운 요청 찾기
        closest = min(pending, key=lambda x: abs(x - current))
        movement = abs(closest - current)
        total_movement += movement
        sequence.append(closest)
        current = closest
        pending.remove(closest)  # 처리 완료

    return {"sequence": sequence, "total_movement": total_movement}

# FCFS와 동일한 예시로 비교
requests = [98, 183, 37, 122, 14, 124, 65, 67]
result = sstf_scheduling(requests, head_position=53)
print(f"처리 순서: {result['sequence']}")  # [53, 65, 67, 37, 14, ...]
print(f"총 헤드 이동: {result['total_movement']} 트랙")  # 236 트랙

FCFS의 비효율성을 확인한 김개발 씨는 더 나은 방법을 고민하기 시작했습니다. 박시니어 씨가 새로운 아이디어를 제시했습니다.

"배달 기사를 생각해보세요. 주문이 여러 개 들어왔을 때, 무조건 먼저 들어온 주문부터 배달하나요?" 김개발 씨가 잠시 생각했습니다.

"아니요, 보통 가까운 곳부터 배달하지 않나요? 효율적으로 동선을 짜서요." "바로 그거예요!

SSTF도 같은 원리입니다." SSTF는 현재 헤드 위치에서 가장 가까운 트랙 요청을 먼저 처리합니다. 탐색 시간이 가장 짧은 요청을 선택한다는 의미에서 Shortest Seek Time First라는 이름이 붙었습니다.

같은 예시로 계산해봅시다. 헤드가 53번 트랙에 있고, 같은 요청 목록이 있습니다.

SSTF에서는 53에서 가장 가까운 65로 먼저 이동합니다. 12트랙 이동입니다.

그 다음 65에서 가장 가까운 67로 이동합니다. 2트랙 이동입니다.

이런 식으로 계속 가장 가까운 곳을 선택하면, 처리 순서는 53, 65, 67, 37, 14, 98, 122, 124, 183이 됩니다. 총 이동 거리를 계산하면 236트랙입니다.

"640트랙에서 236트랙으로 줄었네요!" 김개발 씨가 놀라며 말했습니다. 거의 3분의 1 수준으로 줄어든 것입니다.

SSTF의 장점은 명확합니다. 평균 대기 시간과 헤드 이동 거리가 FCFS보다 훨씬 짧습니다.

처리량도 높아집니다. 하지만 박시니어 씨가 중요한 단점을 지적했습니다.

"여기서 문제가 있어요. 만약 헤드가 디스크 중앙 부근에 있고, 계속해서 중앙 부근에 새 요청이 들어오면 어떻게 될까요?" 김개발 씨가 생각해보았습니다.

중앙 부근의 요청들이 계속 처리되면서, 디스크 가장자리에 있는 요청은 영원히 처리되지 않을 수 있습니다. 이것이 바로 **기아 현상(Starvation)**입니다.

실제로 부하가 높은 시스템에서 SSTF를 사용하면, 특정 트랙의 요청이 무한정 대기하는 상황이 발생할 수 있습니다. 이것은 심각한 문제입니다.

"SSTF가 최적인 것 같은데, 기아 문제라니..." 김개발 씨가 아쉬워했습니다. 박시니어 씨가 덧붙였습니다.

"참고로, SSTF가 항상 최적의 해를 보장하지도 않아요. 탐욕적(Greedy) 알고리즘이라서 지금 당장 가장 좋은 선택을 하지만, 전체적으로 보면 더 나은 해가 있을 수 있어요." SSTF는 FCFS보다 확실히 효율적이지만, 공정성 문제 때문에 실제 시스템에서 그대로 사용하기는 어렵습니다.

이 문제를 해결하기 위해 더 발전된 알고리즘이 필요합니다.

실전 팁

💡 - SSTF는 탐욕 알고리즘이므로 전역 최적해를 보장하지 않습니다

높은 부하 환경에서는 기아 현상에 주의해야 합니다
SJF CPU 스케줄링과 비슷한 개념으로 이해할 수 있습니다

5. SCAN과 C-SCAN

"기아 문제를 해결하면서도 효율적인 방법이 없을까요?" 김개발 씨가 물었습니다. 박시니어 씨가 엘리베이터를 떠올려 보라고 했습니다.

"엘리베이터가 한 방향으로 쭉 올라갔다가 끝에서 방향을 바꾸잖아요. 그 방식을 디스크에 적용한 게 SCAN이에요."

SCAN 알고리즘은 엘리베이터처럼 한 방향으로 이동하면서 그 경로에 있는 모든 요청을 처리하고, 디스크 끝에 도달하면 방향을 바꾸는 방식입니다. **C-SCAN(Circular SCAN)**은 한 방향으로만 서비스하고, 끝에 도달하면 반대편 끝으로 점프해서 다시 같은 방향으로 진행합니다.

두 알고리즘 모두 기아 현상을 방지하면서 효율적인 디스크 접근을 제공합니다.

다음 코드를 살펴봅시다.

# SCAN 디스크 스케줄링 알고리즘
def scan_scheduling(requests, head_position, disk_size=200, direction="up"):
    """
    SCAN: 한 방향으로 이동하며 요청 처리, 끝에서 방향 전환
    """
    sequence = [head_position]
    total_movement = 0
    current = head_position

    # 현재 위치 기준으로 분리
    lower = sorted([r for r in requests if r < head_position], reverse=True)
    upper = sorted([r for r in requests if r >= head_position])

    if direction == "up":
        # 위로 이동 -> 끝까지 -> 방향 전환 -> 아래로
        for track in upper:
            total_movement += abs(track - current)
            current = track
            sequence.append(track)
        if lower:  # 방향 전환이 필요하면
            total_movement += abs(disk_size - 1 - current)
            current = disk_size - 1
            for track in lower:
                total_movement += abs(track - current)
                current = track
                sequence.append(track)

    return {"sequence": sequence, "total_movement": total_movement}

# 예시 실행
requests = [98, 183, 37, 122, 14, 124, 65, 67]
result = scan_scheduling(requests, head_position=53, direction="up")
print(f"총 헤드 이동: {result['total_movement']} 트랙")

SSTF의 기아 문제를 듣고 김개발 씨는 고민에 빠졌습니다. 효율성도 중요하지만 공정성도 포기할 수 없습니다.

박시니어 씨가 해결책을 제시했습니다. "엘리베이터를 타본 적 있죠?

엘리베이터가 어떻게 동작하는지 생각해보세요." 엘리베이터는 한 방향으로 계속 이동합니다. 예를 들어 위로 올라가는 중이라면, 중간에 아래층 호출이 있어도 무시하고 위층 호출만 처리합니다.

맨 위층에 도달하면 그제야 방향을 바꿔서 아래로 내려오면서 호출을 처리합니다. SCAN 알고리즘도 똑같이 동작합니다.

헤드가 한 방향으로 이동하면서 그 경로에 있는 모든 요청을 처리합니다. 디스크 끝에 도달하면 방향을 바꿉니다.

그래서 SCAN을 엘리베이터 알고리즘이라고도 부릅니다. 같은 예시로 계산해봅시다.

헤드가 53번 트랙에서 위쪽(큰 번호 방향)으로 이동한다고 가정합니다. 먼저 65, 67, 98, 122, 124, 183 순서로 처리합니다.

199(또는 디스크 끝)에 도달하면 방향을 바꿉니다. 그리고 37, 14 순서로 처리합니다.

SCAN의 장점은 기아 현상이 발생하지 않는다는 것입니다. 헤드가 반드시 디스크 전체를 훑기 때문에, 어떤 요청도 무한정 기다리지 않습니다.

최대 대기 시간은 디스크 두 번 왕복하는 시간으로 제한됩니다. 그런데 SCAN에도 문제가 있습니다.

박시니어 씨가 설명했습니다. "방금 헤드가 지나간 위치에 새 요청이 들어오면 어떻게 될까요?" 헤드가 100번 트랙을 지나 위로 올라가는 중에 99번 트랙 요청이 들어왔다고 합시다.

이 요청은 헤드가 디스크 끝까지 갔다가 방향을 바꿔서 다시 내려올 때까지 기다려야 합니다. 거의 디스크 전체를 왕복하는 시간을 기다리는 것입니다.

이 불공정함을 해결한 것이 **C-SCAN(Circular SCAN)**입니다. C-SCAN은 한 방향으로만 서비스를 제공합니다.

끝에 도달하면 방향을 바꾸는 대신, 반대편 끝으로 점프해서 다시 같은 방향으로 진행합니다. 마치 회전초밥집의 컨베이어 벨트와 같습니다.

초밥이 항상 같은 방향으로만 돌아갑니다. 지나간 초밥을 잡으려면 한 바퀴를 돌 때까지 기다리면 됩니다.

대기 시간이 더 균등해집니다. C-SCAN에서 끝에서 끝으로 점프하는 시간은 서비스 시간으로 계산하지 않습니다.

점프하는 동안 아무 요청도 처리하지 않기 때문입니다. 이 점프는 매우 빠르게 수행됩니다.

"SCAN과 C-SCAN 중 뭐가 더 좋은가요?" 김개발 씨가 물었습니다. 박시니어 씨가 대답했습니다.

"상황에 따라 다르지만, 대기 시간의 공정성이 중요하면 C-SCAN을 사용해요. 실제로 많은 운영체제가 C-SCAN 계열의 알고리즘을 사용합니다."

실전 팁

💡 - SCAN은 엘리베이터 알고리즘이라고도 불립니다

C-SCAN은 대기 시간 분산이 SCAN보다 균등합니다
실제 운영체제에서 가장 많이 사용되는 알고리즘 계열입니다

6. LOOK과 C-LOOK

"한 가지 의문이 있어요." 김개발 씨가 말했습니다. "SCAN에서 헤드가 꼭 디스크 끝까지 가야 하나요?

더 이상 요청이 없는데도요?" 박시니어 씨가 고개를 끄덕였습니다. "좋은 관찰이에요.

그래서 실제로는 LOOK이라는 개선된 버전을 더 많이 써요."

LOOK 알고리즘은 SCAN을 개선한 버전으로, 헤드가 디스크 끝까지 가지 않고 해당 방향의 마지막 요청까지만 이동한 뒤 방향을 바꿉니다. C-LOOK은 C-SCAN의 개선 버전으로 같은 원리를 적용합니다.

LOOK이라는 이름은 진행 방향에 더 이상 요청이 있는지 미리 살펴본다는 의미에서 붙었습니다.

다음 코드를 살펴봅시다.

# LOOK 디스크 스케줄링 알고리즘
def look_scheduling(requests, head_position, direction="up"):
    """
    LOOK: SCAN과 유사하지만 요청이 있는 곳까지만 이동
    """
    sequence = [head_position]
    total_movement = 0
    current = head_position

    lower = sorted([r for r in requests if r < head_position], reverse=True)
    upper = sorted([r for r in requests if r >= head_position])

    if direction == "up":
        # 위로 이동 -> 마지막 요청까지만 -> 방향 전환
        for track in upper:
            total_movement += abs(track - current)
            current = track
            sequence.append(track)
        # 디스크 끝까지 가지 않고 바로 방향 전환
        for track in lower:
            total_movement += abs(track - current)
            current = track
            sequence.append(track)

    return {"sequence": sequence, "total_movement": total_movement}

# C-LOOK 알고리즘
def c_look_scheduling(requests, head_position, direction="up"):
    """
    C-LOOK: 한 방향으로만 서비스, 마지막 요청에서 첫 요청으로 점프
    """
    sorted_requests = sorted(requests)
    lower = [r for r in sorted_requests if r < head_position]
    upper = [r for r in sorted_requests if r >= head_position]

    # 항상 같은 방향(위)으로만 서비스
    order = upper + lower  # 위쪽 처리 후 아래쪽 처음으로 점프

    sequence = [head_position]
    total_movement = 0
    current = head_position

    for track in order:
        total_movement += abs(track - current)
        current = track
        sequence.append(track)

    return {"sequence": sequence, "total_movement": total_movement}

김개발 씨의 날카로운 질문에 박시니어 씨가 감탄했습니다. SCAN의 비효율적인 부분을 정확히 짚어낸 것입니다.

SCAN에서 헤드가 53번 트랙에서 시작해 위로 이동한다고 합시다. 요청 중 가장 높은 트랙이 183번인데, SCAN은 199번(디스크 끝)까지 갔다가 방향을 바꿉니다.

183에서 199까지 16트랙을 의미 없이 이동하는 것입니다. LOOK 알고리즘은 이 문제를 해결합니다.

진행 방향에 더 이상 요청이 있는지 미리 살펴보고, 요청이 없으면 거기서 바로 방향을 바꿉니다. 영어로 look ahead, 즉 앞을 살펴본다는 의미에서 LOOK이라는 이름이 붙었습니다.

같은 예시에서 LOOK을 적용하면, 헤드는 183번 트랙까지만 이동하고 바로 방향을 바꿉니다. 디스크 끝까지 갈 필요가 없습니다.

이렇게 하면 왕복 32트랙을 절약할 수 있습니다. 박시니어 씨가 부연 설명을 했습니다.

"실제 운영체제에서 SCAN이라고 부르는 것은 대부분 LOOK을 의미해요. 진짜 SCAN처럼 끝까지 가는 구현은 거의 없습니다." C-LOOK은 C-SCAN에 같은 개선을 적용한 것입니다.

C-SCAN은 끝에서 반대편 끝으로 점프하지만, C-LOOK은 마지막 요청에서 첫 번째 요청으로 점프합니다. 예를 들어 위쪽 방향으로 서비스하면서 183번 트랙까지 처리했다면, 199번까지 가지 않고 바로 14번 트랙으로 점프합니다.

점프 거리도 줄어들고, 전체적인 효율이 높아집니다. "그럼 왜 처음부터 LOOK을 안 배우고 SCAN을 먼저 배우나요?" 김개발 씨가 물었습니다.

좋은 질문입니다. SCAN은 개념적으로 더 단순하고 이해하기 쉽습니다.

그리고 LOOK을 이해하려면 SCAN을 먼저 알아야 합니다. 또한 학술적인 분석에서는 SCAN의 동작이 더 예측 가능해서 분석하기 쉽습니다.

박시니어 씨가 정리했습니다. "실무에서는 거의 항상 LOOK 또는 C-LOOK 계열을 사용해요.

리눅스 커널의 디스크 스케줄러도 C-LOOK을 기반으로 한 다양한 변형을 제공합니다." 현대 운영체제에서는 더 발전된 스케줄러들이 사용됩니다. CFQ(Completely Fair Queuing), Deadline 스케줄러 등이 있습니다.

하지만 이들도 기본적으로 LOOK이나 C-LOOK의 아이디어를 기반으로 합니다. 김개발 씨가 마지막으로 물었습니다.

"SSD에서도 이런 알고리즘이 필요한가요?" 박시니어 씨가 대답했습니다. "SSD는 기계적인 탐색이 없어서 이런 스케줄링이 덜 중요해요.

하지만 I/O 병합이나 우선순위 같은 다른 형태의 스케줄링은 여전히 필요합니다." 디스크 스케줄링의 여정이 끝났습니다. FCFS부터 시작해서 SSTF, SCAN, C-SCAN, 그리고 LOOK과 C-LOOK까지.

김개발 씨는 이제 디스크 성능 문제를 만나도 자신 있게 분석할 수 있게 되었습니다.

실전 팁

💡 - 대부분의 현대 운영체제는 LOOK 또는 C-LOOK 계열을 기본으로 사용합니다

SSD에서는 NOOP(No Operation) 스케줄러가 더 효율적입니다
리눅스에서는 /sys/block/sda/queue/scheduler로 현재 스케줄러를 확인할 수 있습니다

이상으로 학습을 마칩니다. 위 내용을 직접 코드로 작성해보면서 익혀보세요!

#OperatingSystem#DiskScheduling#FCFS#SSTF#SCAN#Operating System

디스크 스케줄링 완벽 가이드

# 디스크 스케줄링 완벽 가이드 운영체제가 하드디스크의 읽기/쓰기 요청을 효율적으로 처리하는 방법을 알아봅니다. 디스크 구조부터 FCFS, SSTF, SCAN, LOOK 알고리즘까지 실무 예제와 함께 쉽게 설명합니다. --- ## 목차 1. [디스크 구조](#디스크-구조) 2. [디스크 접근 시간](#디스크-접근-시간) 3. [FCFS 스케줄링](#fcfs-스케줄링) 4. [SSTF 스케줄링](#sstf-스케줄링) 5. [SCAN과 C-SCAN](#scan과-c-scan) 6. [LOOK과 C-LOOK](#look과-c-look) --- ## 1. 디스크 구조 신입 개발자 김개발 씨가 서버실에서 하드디스크를 처음 봤습니다. "이 동그란 원판들이 어떻게 데이터를 저장하는 거죠?" 옆에 있던 박시니어 씨가 웃으며 대답했습니다. "디스크 스케줄링을 이해하려면 먼저 이 구조부터 알아야 해요." 하드디스크는 **플래터**, **트랙**, **섹터**라는 세 가지 핵심 구성 요소로 이루어져 있습니다. 마치 LP 레코드판처럼 생긴 원판 위에 동심원 형태의 트랙이 있고, 각 트랙은 부채꼴 모양의 섹터로 나뉘어 있습니다. 이 구조를 이해하면 왜 디스크 접근 시간이 오래 걸리는지, 그리고 왜 스케줄링이 필요한지 알 수 있습니다. 다음 코드를 살펴봅시다. ```python # 디스크 구조를 표현하는 간단한 클래스 class DiskStructure: def __init__(self, platters=2, tracks_per_surface=1000, sectors_per_track=63): self.platters = platters # 플래터 개수 self.surfaces = platters * 2 # 표면 개수 (양면) self.tracks = tracks_per_surface # 표면당 트랙 수 self.sectors = sectors_per_track # 트랙당 섹터 수 def total_capacity(self, bytes_per_sector=512): # 총 용량 계산: 표면 x 트랙 x 섹터 x 섹터크기 total_sectors = self.surfaces * self.tracks * self.sectors return total_sectors * bytes_per_sector def locate_sector(self, logical_address): # 논리 주소를 물리 위치로 변환 surface = logical_address // (self.tracks * self.sectors) track = (logical_address // self.sectors) % self.tracks sector = logical_address % self.sectors return {"surface": surface, "track": track, "sector": sector} ``` 김개발 씨는 입사 첫 주에 데이터베이스 성능 이슈를 담당하게 되었습니다. 쿼리가 느리다는 보고가 계속 들어왔는데, 원인을 찾다 보니 디스크 I/O가 병목이라는 것을 알게 되었습니다. 하지만 디스크가 어떻게 동작하는지 몰랐기에 어디서부터 손을 대야 할지 막막했습니다. 박시니어 씨가 화이트보드 앞에 섰습니다. "디스크를 이해하려면 LP 레코드판을 떠올려 보세요." 하드디스크의 가장 기본적인 구성 요소는 **플래터**입니다. 플래터는 얇은 원형 금속판으로, 자성 물질로 코팅되어 있습니다. 마치 CD나 LP판처럼 생겼지만, 훨씬 더 정밀하게 만들어졌습니다. 일반적인 하드디스크에는 여러 장의 플래터가 층층이 쌓여 있습니다. 각 플래터의 표면에는 **트랙**이라는 동심원이 존재합니다. 레코드판의 홈처럼 생겼다고 생각하면 됩니다. 바깥쪽 트랙은 번호가 작고, 안쪽으로 갈수록 트랙 번호가 커집니다. 현대 하드디스크는 수만 개의 트랙을 가지고 있습니다. 트랙은 다시 **섹터**라는 부채꼴 조각으로 나뉩니다. 섹터가 바로 데이터가 실제로 저장되는 최소 단위입니다. 전통적으로 한 섹터의 크기는 512바이트였지만, 최근에는 4KB 섹터를 사용하는 디스크도 많습니다. 그렇다면 데이터를 읽으려면 어떻게 해야 할까요? 여기서 **읽기/쓰기 헤드**가 등장합니다. 헤드는 플래터 위를 떠다니며 데이터를 읽거나 씁니다. 레코드 플레이어의 바늘과 비슷하지만, 실제로 플래터에 닿지 않고 공기층 위에 떠 있습니다. 각 플래터의 표면마다 하나씩 헤드가 배치됩니다. 헤드들은 **디스크 암**이라는 구조물에 함께 연결되어 있습니다. 마치 빗처럼 생긴 이 암은 모든 헤드를 동시에 움직입니다. 따라서 한 헤드가 100번 트랙에 있으면, 다른 모든 헤드도 100번 트랙에 위치하게 됩니다. 모든 플래터의 같은 번호 트랙들을 묶어서 **실린더**라고 부릅니다. 이 개념은 나중에 디스크 스케줄링을 이해할 때 중요해집니다. 실린더 단위로 데이터를 저장하면 헤드를 움직이지 않고도 연속해서 데이터를 읽을 수 있기 때문입니다. 박시니어 씨가 덧붙였습니다. "이제 왜 디스크가 느린지 이해가 되죠? 원하는 데이터에 접근하려면 헤드가 해당 트랙으로 이동하고, 플래터가 회전해서 원하는 섹터가 헤드 아래로 와야 합니다." 김개발 씨는 고개를 끄덕였습니다. 물리적인 부품이 움직여야 하니 당연히 시간이 걸릴 수밖에 없었습니다. 그리고 이 시간을 줄이는 것이 바로 디스크 스케줄링의 목표라는 것을 알게 되었습니다. **실전 팁** 💡 - 플래터 수가 많을수록 용량은 커지지만 발열과 소음도 증가합니다 - SSD는 이런 기계적 구조가 없어서 빠르지만, 여전히 많은 서버가 HDD를 사용합니다 - 실린더 개념을 이해하면 디스크 최적화의 핵심을 파악할 수 있습니다 --- ## 2. 디스크 접근 시간 김개발 씨가 성능 모니터링 도구에서 디스크 지연 시간이 15ms라는 수치를 보았습니다. "이 15밀리초가 어디서 오는 거죠?" 박시니어 씨가 화이트보드에 세 개의 박스를 그리며 설명을 시작했습니다. "이 시간은 크게 세 가지 요소로 나뉘어요." 디스크 접근 시간은 **탐색 시간**, **회전 지연**, **전송 시간**의 합으로 구성됩니다. 탐색 시간은 헤드가 원하는 트랙으로 이동하는 시간이고, 회전 지연은 플래터가 돌아 원하는 섹터가 헤드 아래로 올 때까지 기다리는 시간입니다. 이 중에서 탐색 시간이 가장 크고, 디스크 스케줄링은 바로 이 탐색 시간을 최소화하는 것이 목표입니다. 다음 코드를 살펴봅시다. ```python # 디스크 접근 시간 계산기 class DiskAccessTime: def __init__(self, rpm=7200, avg_seek_ms=9, transfer_rate_mbps=150): self.rpm = rpm # 분당 회전수 self.avg_seek_ms = avg_seek_ms # 평균 탐색 시간 (ms) self.transfer_rate = transfer_rate_mbps # 전송 속도 (MB/s) def rotational_latency(self): # 회전 지연 = 평균적으로 반 바퀴 회전하는 시간 rotation_time_ms = (60 / self.rpm) * 1000 return rotation_time_ms / 2 def transfer_time(self, size_kb): # 전송 시간 계산 return (size_kb / 1024) / self.transfer_rate * 1000 def total_access_time(self, size_kb=4): seek = self.avg_seek_ms rotation = self.rotational_latency() transfer = self.transfer_time(size_kb) return {"seek": seek, "rotation": rotation, "transfer": transfer, "total": seek + rotation + transfer} ``` 김개발 씨는 데이터베이스 쿼리가 왜 이렇게 느린지 분석하고 있었습니다. 메모리 캐시 히트율은 높은데도 일부 쿼리는 여전히 느렸습니다. 박시니어 씨는 이것이 디스크 I/O 때문이라고 설명했습니다. "디스크에서 데이터를 읽으려면 세 단계를 거쳐야 해요." 첫 번째는 **탐색 시간(Seek Time)**입니다. 읽기/쓰기 헤드가 현재 위치에서 원하는 트랙까지 이동하는 데 걸리는 시간입니다. 마치 도서관에서 원하는 책장까지 걸어가는 것과 같습니다. 책장이 멀리 있으면 더 오래 걸리겠죠? 탐색 시간은 이동해야 할 트랙 수에 따라 달라집니다. 바로 옆 트랙으로 이동하는 것은 빠르지만, 디스크 가장 바깥쪽에서 가장 안쪽으로 이동하는 것은 오래 걸립니다. 일반적인 하드디스크의 평균 탐색 시간은 8~12밀리초 정도입니다. 두 번째는 **회전 지연(Rotational Latency)**입니다. 헤드가 원하는 트랙에 도착했더라도, 아직 원하는 섹터가 헤드 아래에 있지 않을 수 있습니다. 플래터가 회전해서 해당 섹터가 헤드 아래로 올 때까지 기다려야 합니다. 회전 지연은 디스크의 RPM(분당 회전수)에 따라 결정됩니다. 7200 RPM 디스크는 1분에 7200번, 즉 1초에 120번 회전합니다. 한 바퀴 도는 데 약 8.3밀리초가 걸립니다. 평균적으로는 반 바퀴를 기다리므로 약 4밀리초가 회전 지연이 됩니다. 세 번째는 **전송 시간(Transfer Time)**입니다. 원하는 섹터가 헤드 아래로 왔을 때, 실제로 데이터를 읽어서 메모리로 전송하는 시간입니다. 현대 하드디스크의 전송 속도는 100~200MB/s 정도입니다. 4KB 데이터를 전송하는 데는 0.02밀리초 정도밖에 걸리지 않습니다. 박시니어 씨가 계산해 보았습니다. "7200 RPM 디스크에서 4KB를 읽는다고 하면, 탐색 시간 9ms, 회전 지연 4ms, 전송 시간 0.02ms로 총 약 13ms가 걸려요." 여기서 중요한 점이 드러납니다. 전체 접근 시간 중 탐색 시간이 약 70%를 차지합니다. 회전 지연은 디스크 RPM으로 결정되어 바꿀 수 없고, 전송 시간은 이미 매우 짧습니다. 결국 디스크 성능을 높이려면 **탐색 시간을 줄여야** 합니다. "그래서 디스크 스케줄링이 중요한 거예요. 여러 요청이 동시에 들어왔을 때 어떤 순서로 처리하느냐에 따라 헤드의 총 이동 거리가 크게 달라지거든요." 김개발 씨가 물었습니다. "그럼 어떤 순서로 처리해야 가장 효율적인가요?" 박시니어 씨가 웃으며 대답했습니다. "바로 그걸 결정하는 게 디스크 스케줄링 알고리즘이에요. 이제 하나씩 알아볼까요?" **실전 팁** 💡 - 15000 RPM 고속 디스크는 회전 지연이 절반으로 줄어들지만 가격이 비쌉니다 - SSD는 기계적 동작이 없어 접근 시간이 0.1ms 이하입니다 - 순차 읽기가 랜덤 읽기보다 빠른 이유가 바로 탐색 시간 때문입니다 --- ## 3. FCFS 스케줄링 "가장 간단한 방법부터 시작해볼까요?" 박시니어 씨가 말했습니다. 김개발 씨 앞에는 53, 98, 183, 37, 122, 14, 124, 65, 67이라는 트랙 요청 목록이 있었습니다. "먼저 들어온 요청을 먼저 처리하면 되지 않나요?" 김개발 씨의 질문에 박시니어 씨가 고개를 끄덕이며 대답했습니다. **FCFS(First Come First Served)**는 이름 그대로 먼저 도착한 요청을 먼저 처리하는 가장 단순한 스케줄링 방식입니다. 마치 은행 창구에서 번호표 순서대로 고객을 응대하는 것과 같습니다. 구현이 간단하고 공정하지만, 헤드가 디스크 전체를 왔다 갔다 하면서 비효율적으로 움직일 수 있습니다. 다음 코드를 살펴봅시다. ```python # FCFS 디스크 스케줄링 알고리즘 def fcfs_scheduling(requests, head_position): """ FCFS: 요청이 들어온 순서대로 처리 requests: 트랙 요청 리스트 head_position: 현재 헤드 위치 """ sequence = [head_position] # 처리 순서 기록 total_movement = 0 # 총 이동 거리 current = head_position for track in requests: movement = abs(track - current) # 이동 거리 계산 total_movement += movement sequence.append(track) current = track return {"sequence": sequence, "total_movement": total_movement} # 예시 실행 requests = [98, 183, 37, 122, 14, 124, 65, 67] result = fcfs_scheduling(requests, head_position=53) print(f"처리 순서: {result['sequence']}") # [53, 98, 183, 37, ...] print(f"총 헤드 이동: {result['total_movement']} 트랙") # 640 트랙 ``` 김개발 씨는 처음으로 디스크 스케줄링 알고리즘을 배우게 되었습니다. 박시니어 씨는 가장 기본적인 것부터 시작하자고 했습니다. "FCFS는 말 그대로 선착순이에요. 먼저 온 요청을 먼저 처리합니다." 이해하기 쉽게 은행 창구를 예로 들어봅시다. 고객들이 번호표를 뽑고 순서대로 창구에서 업무를 봅니다. 1번 고객, 2번 고객, 3번 고객 순서대로 처리됩니다. 뒤에 온 사람이 간단한 업무라고 해서 먼저 처리받지 않습니다. 이것이 바로 FCFS 방식입니다. 디스크에 적용해보면 이렇습니다. 현재 헤드가 53번 트랙에 있고, 98, 183, 37, 122, 14, 124, 65, 67번 트랙에 대한 읽기 요청이 순서대로 들어왔다고 가정합니다. FCFS 방식에서는 이 요청들을 들어온 순서 그대로 처리합니다. 53에서 98로, 98에서 183으로, 183에서 37로, 이런 식으로 진행됩니다. 헤드의 이동 거리를 계산해보면 놀라운 결과가 나옵니다. 53에서 98까지 45트랙, 98에서 183까지 85트랙, 183에서 37까지 146트랙... 이렇게 계속 더하면 총 640트랙을 이동하게 됩니다. 박시니어 씨가 그림을 그려 보여주었습니다. "보세요, 헤드가 디스크 안쪽에서 바깥쪽으로, 다시 안쪽으로 왔다 갔다 하고 있어요. 엄청난 낭비죠." FCFS의 장점은 **구현이 매우 간단**하다는 것입니다. 큐에 들어온 순서대로 처리하면 되니까요. 또한 **공정**합니다. 모든 요청이 도착 순서대로 처리되므로 특정 요청이 무한정 기다리는 기아 현상이 발생하지 않습니다. 하지만 단점도 명확합니다. 헤드가 불필요하게 많이 움직입니다. 우리 예시에서 37번 트랙과 14번 트랙 요청이 가까이 있는데도, 중간에 다른 요청들이 있어서 따로따로 방문합니다. 이것은 마치 서울에서 부산으로 갔다가, 다시 대전으로 갔다가, 또 부산으로 가는 것과 같습니다. "그럼 FCFS는 언제 쓰는 게 좋을까요?" 김개발 씨가 물었습니다. 디스크 부하가 적을 때는 FCFS로도 충분합니다. 요청이 하나씩 들어오면 어차피 순서대로 처리해야 하니까요. 하지만 요청이 많이 몰리는 상황에서는 다른 알고리즘이 필요합니다. 김개발 씨가 코드를 보며 말했습니다. "단순하긴 한데, 뭔가 비효율적이라는 게 느껴지네요." 박시니어 씨가 고개를 끄덕였습니다. "맞아요. 그래서 더 똑똑한 방법들이 나온 거예요. 다음으로 SSTF를 알아볼까요?" **실전 팁** 💡 - FCFS는 디스크 부하가 낮을 때 적합합니다 - 기아 현상이 없다는 장점이 있어 공정성이 중요할 때 고려할 수 있습니다 - 실제 운영체제에서는 거의 사용되지 않습니다 --- ## 4. SSTF 스케줄링 "640트랙이나 움직이다니, 분명 더 좋은 방법이 있을 것 같은데요." 김개발 씨가 말했습니다. 박시니어 씨가 웃으며 대답했습니다. "당연히 있죠. 현재 위치에서 가장 가까운 요청부터 처리하면 어떨까요?" 이것이 바로 SSTF, 최단 탐색 시간 우선 알고리즘입니다. **SSTF(Shortest Seek Time First)**는 현재 헤드 위치에서 가장 가까운 트랙 요청을 먼저 처리하는 방식입니다. 마치 배달 기사가 현재 위치에서 가장 가까운 배달지부터 방문하는 것과 같습니다. 헤드 이동 거리가 크게 줄어들지만, 멀리 있는 요청이 계속 무시되는 기아 현상이 발생할 수 있습니다. 다음 코드를 살펴봅시다. ```python # SSTF 디스크 스케줄링 알고리즘 def sstf_scheduling(requests, head_position): """ SSTF: 현재 위치에서 가장 가까운 요청부터 처리 """ pending = requests.copy() # 처리 대기 중인 요청들 sequence = [head_position] total_movement = 0 current = head_position while pending: # 가장 가까운 요청 찾기 closest = min(pending, key=lambda x: abs(x - current)) movement = abs(closest - current) total_movement += movement sequence.append(closest) current = closest pending.remove(closest) # 처리 완료 return {"sequence": sequence, "total_movement": total_movement} # FCFS와 동일한 예시로 비교 requests = [98, 183, 37, 122, 14, 124, 65, 67] result = sstf_scheduling(requests, head_position=53) print(f"처리 순서: {result['sequence']}") # [53, 65, 67, 37, 14, ...] print(f"총 헤드 이동: {result['total_movement']} 트랙") # 236 트랙 ``` FCFS의 비효율성을 확인한 김개발 씨는 더 나은 방법을 고민하기 시작했습니다. 박시니어 씨가 새로운 아이디어를 제시했습니다. "배달 기사를 생각해보세요. 주문이 여러 개 들어왔을 때, 무조건 먼저 들어온 주문부터 배달하나요?" 김개발 씨가 잠시 생각했습니다. "아니요, 보통 가까운 곳부터 배달하지 않나요? 효율적으로 동선을 짜서요." "바로 그거예요! SSTF도 같은 원리입니다." SSTF는 현재 헤드 위치에서 가장 가까운 트랙 요청을 먼저 처리합니다. 탐색 시간이 가장 짧은 요청을 선택한다는 의미에서 Shortest Seek Time First라는 이름이 붙었습니다. 같은 예시로 계산해봅시다. 헤드가 53번 트랙에 있고, 같은 요청 목록이 있습니다. SSTF에서는 53에서 가장 가까운 65로 먼저 이동합니다. 12트랙 이동입니다. 그 다음 65에서 가장 가까운 67로 이동합니다. 2트랙 이동입니다. 이런 식으로 계속 가장 가까운 곳을 선택하면, 처리 순서는 53, 65, 67, 37, 14, 98, 122, 124, 183이 됩니다. 총 이동 거리를 계산하면 236트랙입니다. "640트랙에서 236트랙으로 줄었네요!" 김개발 씨가 놀라며 말했습니다. 거의 3분의 1 수준으로 줄어든 것입니다. SSTF의 장점은 명확합니다. 평균 대기 시간과 헤드 이동 거리가 FCFS보다 훨씬 짧습니다. 처리량도 높아집니다. 하지만 박시니어 씨가 중요한 단점을 지적했습니다. "여기서 문제가 있어요. 만약 헤드가 디스크 중앙 부근에 있고, 계속해서 중앙 부근에 새 요청이 들어오면 어떻게 될까요?" 김개발 씨가 생각해보았습니다. 중앙 부근의 요청들이 계속 처리되면서, 디스크 가장자리에 있는 요청은 영원히 처리되지 않을 수 있습니다. 이것이 바로 **기아 현상(Starvation)**입니다. 실제로 부하가 높은 시스템에서 SSTF를 사용하면, 특정 트랙의 요청이 무한정 대기하는 상황이 발생할 수 있습니다. 이것은 심각한 문제입니다. "SSTF가 최적인 것 같은데, 기아 문제라니..." 김개발 씨가 아쉬워했습니다. 박시니어 씨가 덧붙였습니다. "참고로, SSTF가 항상 최적의 해를 보장하지도 않아요. 탐욕적(Greedy) 알고리즘이라서 지금 당장 가장 좋은 선택을 하지만, 전체적으로 보면 더 나은 해가 있을 수 있어요." SSTF는 FCFS보다 확실히 효율적이지만, 공정성 문제 때문에 실제 시스템에서 그대로 사용하기는 어렵습니다. 이 문제를 해결하기 위해 더 발전된 알고리즘이 필요합니다. **실전 팁** 💡 - SSTF는 탐욕 알고리즘이므로 전역 최적해를 보장하지 않습니다 - 높은 부하 환경에서는 기아 현상에 주의해야 합니다 - SJF CPU 스케줄링과 비슷한 개념으로 이해할 수 있습니다 --- ## 5. SCAN과 C-SCAN "기아 문제를 해결하면서도 효율적인 방법이 없을까요?" 김개발 씨가 물었습니다. 박시니어 씨가 엘리베이터를 떠올려 보라고 했습니다. "엘리베이터가 한 방향으로 쭉 올라갔다가 끝에서 방향을 바꾸잖아요. 그 방식을 디스크에 적용한 게 SCAN이에요." **SCAN 알고리즘**은 엘리베이터처럼 한 방향으로 이동하면서 그 경로에 있는 모든 요청을 처리하고, 디스크 끝에 도달하면 방향을 바꾸는 방식입니다. **C-SCAN(Circular SCAN)**은 한 방향으로만 서비스하고, 끝에 도달하면 반대편 끝으로 점프해서 다시 같은 방향으로 진행합니다. 두 알고리즘 모두 기아 현상을 방지하면서 효율적인 디스크 접근을 제공합니다. 다음 코드를 살펴봅시다. ```python # SCAN 디스크 스케줄링 알고리즘 def scan_scheduling(requests, head_position, disk_size=200, direction="up"): """ SCAN: 한 방향으로 이동하며 요청 처리, 끝에서 방향 전환 """ sequence = [head_position] total_movement = 0 current = head_position # 현재 위치 기준으로 분리 lower = sorted([r for r in requests if r = head_position]) if direction == "up": # 위로 이동 -> 끝까지 -> 방향 전환 -> 아래로 for track in upper: total_movement += abs(track - current) current = track sequence.append(track) if lower: # 방향 전환이 필요하면 total_movement += abs(disk_size - 1 - current) current = disk_size - 1 for track in lower: total_movement += abs(track - current) current = track sequence.append(track) return {"sequence": sequence, "total_movement": total_movement} # 예시 실행 requests = [98, 183, 37, 122, 14, 124, 65, 67] result = scan_scheduling(requests, head_position=53, direction="up") print(f"총 헤드 이동: {result['total_movement']} 트랙") ``` SSTF의 기아 문제를 듣고 김개발 씨는 고민에 빠졌습니다. 효율성도 중요하지만 공정성도 포기할 수 없습니다. 박시니어 씨가 해결책을 제시했습니다. "엘리베이터를 타본 적 있죠? 엘리베이터가 어떻게 동작하는지 생각해보세요." 엘리베이터는 한 방향으로 계속 이동합니다. 예를 들어 위로 올라가는 중이라면, 중간에 아래층 호출이 있어도 무시하고 위층 호출만 처리합니다. 맨 위층에 도달하면 그제야 방향을 바꿔서 아래로 내려오면서 호출을 처리합니다. SCAN 알고리즘도 똑같이 동작합니다. 헤드가 한 방향으로 이동하면서 그 경로에 있는 모든 요청을 처리합니다. 디스크 끝에 도달하면 방향을 바꿉니다. 그래서 SCAN을 **엘리베이터 알고리즘**이라고도 부릅니다. 같은 예시로 계산해봅시다. 헤드가 53번 트랙에서 위쪽(큰 번호 방향)으로 이동한다고 가정합니다. 먼저 65, 67, 98, 122, 124, 183 순서로 처리합니다. 199(또는 디스크 끝)에 도달하면 방향을 바꿉니다. 그리고 37, 14 순서로 처리합니다. SCAN의 장점은 **기아 현상이 발생하지 않는다**는 것입니다. 헤드가 반드시 디스크 전체를 훑기 때문에, 어떤 요청도 무한정 기다리지 않습니다. 최대 대기 시간은 디스크 두 번 왕복하는 시간으로 제한됩니다. 그런데 SCAN에도 문제가 있습니다. 박시니어 씨가 설명했습니다. "방금 헤드가 지나간 위치에 새 요청이 들어오면 어떻게 될까요?" 헤드가 100번 트랙을 지나 위로 올라가는 중에 99번 트랙 요청이 들어왔다고 합시다. 이 요청은 헤드가 디스크 끝까지 갔다가 방향을 바꿔서 다시 내려올 때까지 기다려야 합니다. 거의 디스크 전체를 왕복하는 시간을 기다리는 것입니다. 이 불공정함을 해결한 것이 **C-SCAN(Circular SCAN)**입니다. C-SCAN은 한 방향으로만 서비스를 제공합니다. 끝에 도달하면 방향을 바꾸는 대신, 반대편 끝으로 점프해서 다시 같은 방향으로 진행합니다. 마치 회전초밥집의 컨베이어 벨트와 같습니다. 초밥이 항상 같은 방향으로만 돌아갑니다. 지나간 초밥을 잡으려면 한 바퀴를 돌 때까지 기다리면 됩니다. 대기 시간이 더 균등해집니다. C-SCAN에서 끝에서 끝으로 점프하는 시간은 서비스 시간으로 계산하지 않습니다. 점프하는 동안 아무 요청도 처리하지 않기 때문입니다. 이 점프는 매우 빠르게 수행됩니다. "SCAN과 C-SCAN 중 뭐가 더 좋은가요?" 김개발 씨가 물었습니다. 박시니어 씨가 대답했습니다. "상황에 따라 다르지만, 대기 시간의 공정성이 중요하면 C-SCAN을 사용해요. 실제로 많은 운영체제가 C-SCAN 계열의 알고리즘을 사용합니다." **실전 팁** 💡 - SCAN은 엘리베이터 알고리즘이라고도 불립니다 - C-SCAN은 대기 시간 분산이 SCAN보다 균등합니다 - 실제 운영체제에서 가장 많이 사용되는 알고리즘 계열입니다 --- ## 6. LOOK과 C-LOOK "한 가지 의문이 있어요." 김개발 씨가 말했습니다. "SCAN에서 헤드가 꼭 디스크 끝까지 가야 하나요? 더 이상 요청이 없는데도요?" 박시니어 씨가 고개를 끄덕였습니다. "좋은 관찰이에요. 그래서 실제로는 LOOK이라는 개선된 버전을 더 많이 써요." **LOOK 알고리즘**은 SCAN을 개선한 버전으로, 헤드가 디스크 끝까지 가지 않고 해당 방향의 마지막 요청까지만 이동한 뒤 방향을 바꿉니다. **C-LOOK**은 C-SCAN의 개선 버전으로 같은 원리를 적용합니다. LOOK이라는 이름은 진행 방향에 더 이상 요청이 있는지 미리 살펴본다는 의미에서 붙었습니다. 다음 코드를 살펴봅시다. ```python # LOOK 디스크 스케줄링 알고리즘 def look_scheduling(requests, head_position, direction="up"): """ LOOK: SCAN과 유사하지만 요청이 있는 곳까지만 이동 """ sequence = [head_position] total_movement = 0 current = head_position lower = sorted([r for r in requests if r = head_position]) if direction == "up": # 위로 이동 -> 마지막 요청까지만 -> 방향 전환 for track in upper: total_movement += abs(track - current) current = track sequence.append(track) # 디스크 끝까지 가지 않고 바로 방향 전환 for track in lower: total_movement += abs(track - current) current = track sequence.append(track) return {"sequence": sequence, "total_movement": total_movement} # C-LOOK 알고리즘 def c_look_scheduling(requests, head_position, direction="up"): """ C-LOOK: 한 방향으로만 서비스, 마지막 요청에서 첫 요청으로 점프 """ sorted_requests = sorted(requests) lower = [r for r in sorted_requests if r = head_position] # 항상 같은 방향(위)으로만 서비스 order = upper + lower # 위쪽 처리 후 아래쪽 처음으로 점프 sequence = [head_position] total_movement = 0 current = head_position for track in order: total_movement += abs(track - current) current = track sequence.append(track) return {"sequence": sequence, "total_movement": total_movement} ``` 김개발 씨의 날카로운 질문에 박시니어 씨가 감탄했습니다. SCAN의 비효율적인 부분을 정확히 짚어낸 것입니다. SCAN에서 헤드가 53번 트랙에서 시작해 위로 이동한다고 합시다. 요청 중 가장 높은 트랙이 183번인데, SCAN은 199번(디스크 끝)까지 갔다가 방향을 바꿉니다. 183에서 199까지 16트랙을 의미 없이 이동하는 것입니다. **LOOK 알고리즘**은 이 문제를 해결합니다. 진행 방향에 더 이상 요청이 있는지 미리 살펴보고, 요청이 없으면 거기서 바로 방향을 바꿉니다. 영어로 look ahead, 즉 앞을 살펴본다는 의미에서 LOOK이라는 이름이 붙었습니다. 같은 예시에서 LOOK을 적용하면, 헤드는 183번 트랙까지만 이동하고 바로 방향을 바꿉니다. 디스크 끝까지 갈 필요가 없습니다. 이렇게 하면 왕복 32트랙을 절약할 수 있습니다. 박시니어 씨가 부연 설명을 했습니다. "실제 운영체제에서 SCAN이라고 부르는 것은 대부분 LOOK을 의미해요. 진짜 SCAN처럼 끝까지 가는 구현은 거의 없습니다." **C-LOOK**은 C-SCAN에 같은 개선을 적용한 것입니다. C-SCAN은 끝에서 반대편 끝으로 점프하지만, C-LOOK은 마지막 요청에서 첫 번째 요청으로 점프합니다. 예를 들어 위쪽 방향으로 서비스하면서 183번 트랙까지 처리했다면, 199번까지 가지 않고 바로 14번 트랙으로 점프합니다. 점프 거리도 줄어들고, 전체적인 효율이 높아집니다. "그럼 왜 처음부터 LOOK을 안 배우고 SCAN을 먼저 배우나요?" 김개발 씨가 물었습니다. 좋은 질문입니다. SCAN은 개념적으로 더 단순하고 이해하기 쉽습니다. 그리고 LOOK을 이해하려면 SCAN을 먼저 알아야 합니다. 또한 학술적인 분석에서는 SCAN의 동작이 더 예측 가능해서 분석하기 쉽습니다. 박시니어 씨가 정리했습니다. "실무에서는 거의 항상 LOOK 또는 C-LOOK 계열을 사용해요. 리눅스 커널의 디스크 스케줄러도 C-LOOK을 기반으로 한 다양한 변형을 제공합니다." 현대 운영체제에서는 더 발전된 스케줄러들이 사용됩니다. CFQ(Completely Fair Queuing), Deadline 스케줄러 등이 있습니다. 하지만 이들도 기본적으로 LOOK이나 C-LOOK의 아이디어를 기반으로 합니다. 김개발 씨가 마지막으로 물었습니다. "SSD에서도 이런 알고리즘이 필요한가요?" 박시니어 씨가 대답했습니다. "SSD는 기계적인 탐색이 없어서 이런 스케줄링이 덜 중요해요. 하지만 I/O 병합이나 우선순위 같은 다른 형태의 스케줄링은 여전히 필요합니다." 디스크 스케줄링의 여정이 끝났습니다. FCFS부터 시작해서 SSTF, SCAN, C-SCAN, 그리고 LOOK과 C-LOOK까지. 김개발 씨는 이제 디스크 성능 문제를 만나도 자신 있게 분석할 수 있게 되었습니다. **실전 팁** 💡 - 대부분의 현대 운영체제는 LOOK 또는 C-LOOK 계열을 기본으로 사용합니다 - SSD에서는 NOOP(No Operation) 스케줄러가 더 효율적입니다 - 리눅스에서는 /sys/block/sda/queue/scheduler로 현재 스케줄러를 확인할 수 있습니다 --- 이상으로 학습을 마칩니다. 위 내용을 직접 코드로 작성해보면서 익혀보세요!

카테고리: Operating System

언어: Python

태그: OperatingSystem, DiskScheduling, FCFS, SSTF, SCAN, Operating System

작성자: AI Generated

프리미엄 콘텐츠 - 3개월 무료 체험 가능

CodeDeck

디스크 스케줄링 완벽 가이드

목차

1. 디스크 구조

2. 디스크 접근 시간

3. FCFS 스케줄링

4. SSTF 스케줄링

5. SCAN과 C-SCAN

6. LOOK과 C-LOOK

댓글 (0)

함께 보면 좋은 카드 뉴스

파일 시스템 완벽 가이드

가상 메모리 완벽 가이드

페이징과 세그멘테이션 완벽 가이드

메모리 관리 기초 완벽 가이드

교착 상태 (Deadlock) 완벽 가이드