2-6. 스케줄링 알고리즘 비교 및 실습

1. 스케줄링 알고리즘 비교의 중요성

운영체제에서 프로세스 스케줄링은 시스템 자원을 효율적으로 관리하고, 사용자에게 최적의 응답 시간을 제공하는 핵심적인 기술입니다. 다양한 스케줄링 알고리즘들이 존재하며, 각 알고리즘은 서로 다른 성능 특성을 보입니다. 이러한 특성을 이해하고, 시스템의 요구사항에 맞는 알고리즘을 선택하는 것은 시스템의 전체적인 성능을 결정짓는 중요한 요소입니다. 스케줄링 알고리즘의 성능을 비교 분석하고, 실제 환경에서 적용해 보는 과정을 통해, 각 알고리즘의 장단점을 파악하고, 최적의 선택을 할 수 있는 능력을 키울 수 있습니다.

2. 스케줄링 알고리즘 성능 평가 지표

스케줄링 알고리즘의 성능을 평가하기 위한 주요 지표들은 다음과 같습니다.

1) CPU 사용률 (CPU Utilization)

CPU가 작업을 처리하는 시간의 비율을 나타냅니다. CPU 사용률이 높을수록 시스템의 효율성이 좋다고 할 수 있지만, 너무 높으면 오버헤드가 발생할 수 있습니다.

2) 처리량 (Throughput)

단위 시간당 완료된 프로세스의 수입니다. 처리량이 높을수록 시스템이 더 많은 작업을 처리할 수 있음을 의미합니다.

3) 대기 시간 (Waiting Time)

프로세스가 준비 큐에서 대기하는 시간의 총합입니다. 대기 시간이 짧을수록 프로세스가 더 빠르게 실행될 수 있습니다.

4) 응답 시간 (Response Time)

사용자 요청이 도착한 후, 첫 번째 응답이 나올 때까지의 시간입니다. 응답 시간은 사용자 인터랙션의 만족도에 직접적인 영향을 미칩니다.

5) 반환 시간 (Turnaround Time)

프로세스가 시스템에 들어와서 완료될 때까지의 총 시간입니다. 반환 시간은 프로세스의 전체 실행 시간을 나타냅니다.

3. 스케줄링 알고리즘 비교 분석

다양한 스케줄링 알고리즘들을 위에서 언급한 성능 지표들을 기준으로 비교 분석해 보겠습니다.

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

FCFS는 프로세스가 도착한 순서대로 CPU를 할당하는 가장 간단한 스케줄링 알고리즘입니다.

• 장점: 구현이 간단하고, 공정합니다.
• 단점: 긴 작업이 먼저 도착하면, 짧은 작업들이 오랫동안 기다려야 하는 "호위 효과"가 발생하여 평균 대기 시간과 반환 시간이 길어질 수 있습니다. CPU 사용률이 낮아질 수 있으며, 응답 시간이 좋지 않습니다.

2) SJF (Shortest Job First)

SJF는 실행 시간이 가장 짧은 프로세스에게 CPU를 할당하는 알고리즘입니다.

• 장점: 평균 대기 시간과 반환 시간을 최소화할 수 있습니다.
• 단점: 실행 시간을 정확하게 예측해야 하며, 긴 작업은 무한정 기다릴 수 있는 "기아 현상"이 발생할 수 있습니다. 선점형 SJF (SRT, Shortest Remaining Time)는 현재 실행 중인 프로세스보다 남은 실행 시간이 짧은 프로세스가 도착하면 CPU를 뺏어옵니다.

3) Priority Scheduling

우선순위를 기반으로 프로세스를 스케줄링합니다. 우선순위가 높은 프로세스에게 CPU를 할당합니다.

• 장점: 중요하거나 긴급한 프로세스를 먼저 처리할 수 있습니다.
• 단점: 우선순위가 낮은 프로세스는 기아 현상에 직면할 수 있으며, 우선순위 배정에 따른 오버헤드가 발생할 수 있습니다.

4) Round Robin

각 프로세스에 일정한 시간 할당량 (time quantum)을 부여하여, 시간 할당량이 만료되면 다음 프로세스로 CPU를 넘겨주는 방식입니다.

• 장점: 모든 프로세스가 CPU를 공정하게 사용할 수 있으며, 응답 시간이 비교적 짧습니다.
• 단점: 시간 할당량이 너무 크면 FCFS와 유사해지고, 너무 작으면 문맥 교환 (context switch) 오버헤드가 커져 성능이 저하될 수 있습니다.

표를 사용하여 각 알고리즘의 성능 특성을 정리해 보겠습니다.

4. 실습: 간단한 스케줄링 알고리즘 구현

각 스케줄링 알고리즘을 직접 구현해 보면서, 앞서 설명한 개념들을 더욱 깊이 있게 이해할 수 있습니다. 아래는 Python을 이용한 간단한 FCFS 스케줄링 알고리즘 구현 예시입니다.

class Process:
    def __init__(self, pid, burst_time):
        self.pid = pid
        self.burst_time = burst_time
        self.waiting_time = 0
        self.turnaround_time = 0

def fcfs_scheduling(processes):
    n = len(processes)
    total_waiting_time = 0
    total_turnaround_time = 0
    current_time = 0

    for process in processes:
        process.waiting_time = current_time
        process.turnaround_time = current_time + process.burst_time
        current_time += process.burst_time
        total_waiting_time += process.waiting_time
        total_turnaround_time += process.turnaround_time

    avg_waiting_time = total_waiting_time / n
    avg_turnaround_time = total_turnaround_time / n

    print("Process\tBurst Time\tWaiting Time\tTurnaround Time")
    for process in processes:
        print(f"{process.pid}\t\t{process.burst_time}\t\t{process.waiting_time}\t\t{process.turnaround_time}")

    print(f"\nAverage Waiting Time: {avg_waiting_time:.2f}")
    print(f"Average Turnaround Time: {avg_turnaround_time:.2f}")

# Example usage
processes = [
    Process("P1", 6),
    Process("P2", 2),
    Process("P3", 8),
    Process("P4", 3)
]

fcfs_scheduling(processes)

위 코드는 Process 클래스를 정의하고, 각 프로세스의 burst_time (실행 시간)을 입력받아 FCFS 방식으로 스케줄링을 수행합니다. 각 프로세스의 대기 시간과 반환 시간을 계산하고, 평균 대기 시간과 평균 반환 시간을 출력합니다.

1) 코드 분석

• Process 클래스는 각 프로세스의 ID (pid), 실행 시간 (burst_time), 대기 시간 (waiting_time), 반환 시간 (turnaround_time)을 저장합니다.
• fcfs_scheduling 함수는 프로세스 리스트를 입력받아 FCFS 스케줄링을 수행합니다.
• 각 프로세스의 대기 시간은 이전 프로세스의 실행 시간의 합입니다.
• 각 프로세스의 반환 시간은 대기 시간과 실행 시간을 더한 값입니다.
• 평균 대기 시간과 평균 반환 시간을 계산하여 출력합니다.

2) 확장 및 추가 실습

• 다른 스케줄링 알고리즘 (SJF, Round Robin 등)을 구현해 보고, 성능을 비교해보세요.
• 우선순위 스케줄링을 구현하여, 우선순위가 높은 프로세스에 더 많은 CPU 시간을 할당하도록 해보세요.
• 실행 시간 예측 알고리즘을 구현하여 SJF 알고리즘의 성능을 향상시켜보세요.
• 다양한 입력 데이터(프로세스 수, 실행 시간 분포 등)를 사용하여 각 알고리즘의 성능 변화를 관찰하고, 그래프로 시각화해보세요.

5. 실습 결과 분석 및 결론

실습 결과를 분석하고, 각 알고리즘의 장단점을 파악하는 것이 중요합니다. 예를 들어, FCFS는 간단하지만, 호위 효과로 인해 평균 대기 시간과 반환 시간이 길어질 수 있습니다. SJF는 평균 대기 시간과 반환 시간을 최소화하지만, 실행 시간 예측의 어려움과 기아 현상의 가능성이 있습니다. Round Robin은 공정성이 뛰어나지만, 문맥 교환 오버헤드로 인해 성능이 저하될 수 있습니다.

위 이미지와 같이, 시뮬레이션 결과를 시각화하여 각 알고리즘의 성능을 비교 분석하고, 시스템의 특성과 요구사항에 맞는 스케줄링 알고리즘을 선택하는 것이 중요합니다.

각 알고리즘의 성능을 비교 분석하고, 실제 환경에서 적용해 보는 과정을 통해, 각 알고리즘의 장단점을 파악하고, 최적의 선택을 할 수 있는 능력을 키울 수 있습니다. 스케줄링은 운영체제의 핵심적인 기능 중 하나이며, 스케줄링 알고리즘에 대한 이해는 시스템 성능 최적화에 필수적입니다.