다양한 CPU 스케줄링 알고리즘
핵심 내용 요약
- 선입선처리 스케줄링 (FCFS):
준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식. - 최단작업우선 스케줄링 (SJF):
CPU 사용 시간이 짧은 프로세스를 우선으로 실행하는 비선점형 스케줄링 방식. - 라운드로빈 스케줄링 (Round Robin):
각 프로세스가 정해진 시간 동안 CPU를 사용할 수 있는 선점형 스케줄링 방식. - 우선순위 스케줄링 (Priority Scheduling):
프로세스에 우선순위를 부여하고, 가장 높은 우선순위의 프로세스부터 실행. - 다단계 큐 스케줄링 (Multilevel Queue Scheduling):
우선순위 별로 준비 큐를 여러 개 사용하는 스케줄링 방식. - 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling):
프로세스들이 큐 사이를 이동할 수 있는 다단계 큐 스케줄링 방식.
스케줄링 알고리즘의 종류
운영체제는 다양한 스케줄링 알고리즘을 통해 프로세스에 CPU를 배분합니다.
여기서는 여러 전공서에서 다루는 기본적인 스케줄링 알고리즘을 설명합니다.
선입선처리 스케줄링 (FCFS)
선입 선처리 스케줄링(FCFS, First Come First Served Scheduling)은
준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식입니다.
이는 단순히 먼저 도착한 프로세스부터 CPU를 할당받는 방식입니다.
그러나 이 방식은 CPU 사용 시간이 긴 프로세스가 먼저 도착하면
다른 프로세스는 오랜 시간 대기해야 하는 호위 효과(convoy effect)가 발생할 수 있습니다.
최단작업우선 스케줄링 (SJF)
최단작업우선 스케줄링(SJF, Shortest Job First Scheduling)은
CPU 사용 시간이 짧은 프로세스를 우선으로 실행하는 비선점형 스케줄링 방식입니다.
이 방식은 CPU 사용 시간이 긴 프로세스로 인해 짧은 프로세스가 오랜 시간 대기하는 문제를 해결합니다.
라운드로빈 스케줄링 (Round Robin)
라운드로빈 스케줄링(Round Robin Scheduling)은
각 프로세스가 정해진 시간(타임 슬라이스) 동안 CPU를 사용할 수 있는 선점형 스케줄링 방식입니다.
정해진 시간을 모두 사용한 프로세스는 큐의 맨 뒤로 이동하고, 다음 프로세스가 CPU를 사용하게 됩니다.
타임 슬라이스가 너무 크면 선입 선처리 스케줄링과 다를 바 없고, 타임 슬라이스가 너무 작으면 문맥 교환의 오버헤드가 커집니다.
최소 잔여 시간 우선 스케줄링 (SRT)
최소 잔여 시간 우선 스케줄링(SRT, Shortest Remaining Time Scheduling)은
최단작업우선 스케줄링과 라운드로빈 스케줄링을 결합한 방식입니다.
남아있는 작업 시간이 가장 적은 프로세스가 CPU를 사용합니다.
우선순위 스케줄링 (Priority Scheduling)
우선순위 스케줄링(Priority Scheduling)은
프로세스에 우선순위를 부여하고, 가장 높은 우선순위의 프로세스부터 실행하는 방식입니다.
그러나 우선순위가 낮은 프로세스는 계속 실행이 연기되는 기아 현상(starvation)이 발생할 수 있습니다.
이를 해결하기 위해 에이징(aging) 기법을 사용하여 오랫동안 대기한 프로세스의 우선순위를 점차 높입니다.
다단계 큐 스케줄링 (Multilevel Queue Scheduling)
다단계 큐 스케줄링(Multilevel Queue Scheduling)은
우선순위 별로 준비 큐를 여러 개 사용하는 스케줄링 방식입니다.
각 큐는 서로 다른 스케줄링 알고리즘을 사용할 수 있습니다.
다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)
다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)은
다단계 큐 스케줄링의 발전된 형태로, 프로세스들이 큐 사이를 이동할 수 있는 방식입니다.
CPU 사용 시간이 긴 프로세스는 점차 우선순위가 낮아지고,
낮은 우선순위 큐에서 오래 기다린 프로세스는 점차 높은 우선순위 큐로 이동합니다.
확인 문제
- 준비 큐에 프로세스 A, B, C, D 순으로 삽입되었다고 가정했을 때,
선입 선처리 스케줄링 알고리즘을 적용한다면 어떤 프로세스 순서대로 CPU를 할당받게 될까요? - 다음 보기에서 올바른 정의를 찾아 써 보세요. ‘기아 현상, 에이징, 타임 슬라이스’
- 우선순위가 낮아 실행이 계속 연기되는 문제를 무엇이라고 하나요?
- 우선순위가 낮아 실행이 계속 연기되는 문제를 해결하기 위해 점차 우선순위를 높이는 기법을 무엇이라고 하나요?