CPU 스케줄링
메모리에 올라온 프로세스들 중 어떤 프로세스를 먼저 처리할지 순서를 정하는 것. 즉, Ready Queue에 있는 프로세스들 중에 누구에게 CPU를 할당해 줄 것인지 정한다.
왜 필요할까?
CPU는 한번에 하나의 프로세스만 실행시킬 수 있다. 따라서 특정 프로세스가 I/O 요청에 의해 대기해야할 경우 CPU는 그저 놀고 있게 된다.
다중 프로그래밍에서는 이러한 시간을 생산적으로 활용하고자 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다.
그 외 여러가지 예시들도 있겠지만 CPU 스케줄링이 필요한 이유는 하나로 통일되는데, 바로 CPU 이용률 극대화 이다.
선점 및 비선점 스케줄링
CPU 스케줄러는 다음 네 가지 상황에서 동작한다.
- 한 프로세스가 실행상태에서 대기 상태로 전환될 때
ex) I/O 요청에 의한 대기
- 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때
ex) 할당된 시간이 다 끝났을 때 (타이머 인터럽트가 발생했을 때)
- 프로세스가 대기 상태에서 준비완료 상태로 전환될 때
ex) I/O 종료 시
- 프로세스가 종료될 때
비선점 (nonpreemptive)
1, 4번 상황과 같이 프로세스가 자발적으로 CPU를 반납하는 경우, 우리는 이러한 스케줄링 방법을 비선점 이라고 한다.
비선점 스케줄링하에서는, 일단 CPU가 한 프로세스에게 할당되면 프로세스가 종료되든지, 또는 대기 상태로 전환해 CPU를 방출할 때 까지 점유한다.
선점 (preemptive)
2, 3번 상황과 같이 강제적으로 CPU를 빼앗기는 경우, 우리는 이러한 스케줄링 방법을 선점 이라고 한다.
Windows, macOS, Linux를 포함한 거의 모든 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.
스케줄링 기준
서로 다른 CPU 스케줄링 알고리즘들은 다른 특성이 있으며 특정 상황에서 어떠한 알고리즘을 선택하려면, 우리는 다양한 알고리즘들의 서로 다른 특성을 반드시 고려해야 한다.
CPU 스케줄링 알고리즘들을 비교하기 위한 기준은 다음과 같다.
CPU 이용률 (utilization)
전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율을 말한다.
CPU 이용률이 높을 수록 CPU가 바쁘게 일을 하고 있다는 것을 뜻한다.
처리량 (throughput)
단위 시간당 완료된 프로세스의 개수로,
긴 프로세스인 경우 이 비율을 몇 초 동안 한 프로세스가 될 수도 있고, 짧은 프로세스인 경우 처리량은 초당 수십 개의 프로세스가 될 수도 있다.
총처리 시간 (turnaround time)
프로세스가 시작해서 끝날 때까지 걸리는 시간으로,
준비큐에서 대기한 시간, CPU에서 실행하는 시간, I/O 시간을 합한 시간이다.
대기 시간 (waiting time)
프로세스가 준비 큐에서 대기하면서 보낸 시간의 합이다.
응답 시간 (response time)
하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간이다. 이 기준은 응답이 시작되는 데까지 걸리는 시간이지, 그 응답을 출력하는 데 걸리는 시간은 포함하지 않는다.
어떤게 좋을까
CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화 하는 것이 바람직하다.
스케줄링 알고리즘
선입 선처리 (FCFS)
가장 간단한 CPU 스케줄링 알고리즘으로, CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. (비선점)
모든 다른프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 convoy effect (호위 효과) 라고 하는데, 선입 선처리 방식에서는 convoy effect가 발생하여 CPU와 장치 이용률이 저하되는 결과를 낳을 수 있다.
SJF (Shortest Job First)
가장 작은 CPU 버스트 시간을 가진 프로세스에게 우선적으로 CPU를 할당한다. 버스트 시간이 동일하다면 FCFS 방식으로 동작한다.
SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균대기 시간을 가진다는 점에서 최적의 알고리즘임을 증명할 수 있다.
하지만 컴퓨터 입장에서는 프로세스가 얼만큼의 CPU 버스트 길이를 가지는지 미리 알 수가 없다.
왜냐하면, I/O를 요청하는 명령어가 언제 나올 지 모르기 때문이다. 따라서 SJF 스케줄링 알고리즘은 사실상 구현이 불가능 하다.
추가적으로,
위 사진에서는 SJF가 비선점으로 작동하지만, 선점으로도 작동할 수 있는데, 이 경우에는 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가진 프로세스가 CPU를 선점할 수 있다.
RR (Round Robin)
라운드 로빈 스케줄링 알고리즘은 FCFS과 유사하지만 시간 할당량(time quantum)을 정의하여 선점형으로 동작한다.
동작 방식은 다음과 같다.
-
프로세스의 CPU 버스트가
시간 할당량보다 작으면 프로세스는 CPU를 자발적으로 방출한다. -
프로세스의 CPU 버스트가
시간 할당량보다 크면 타이머가 끝나고 운영체제에 인터럽트를 발생할 것이다.문맥교환이 일어나고 준비 큐의 다음 프로세스가 CPU를 사용한다.
라운드 로빈 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다.
-
시간 할당량이 매우 작다면
문맥교환하는 데 시간을 다 쓰게 된다. -
시간 할당량이 매우 크다면
FCFS와 똑같이 동작하게 된다.
우선순위 스케줄링 (Priority Scheduling)
운영체제 혹은 사용자에 의해 프로세스에 우선순위를 부여하고, CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다.
우선순위 스케줄링은 선점형이거나 또는 비선점형이 될 수 있다.
-
선점형은 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높으면 CPU를 선점한다.
-
비선점형은 단순히 준비완료 큐의 머리부분에 새로운 프로세스를 넣는다.
우선순위 스케줄링의 주요 문제는 무한 봉쇄(indefinite blocking) 또는 기아 상태(startvation) 이다.
높은 우선순위의 프로세스가 계속 들어올 경우, 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생할 수 있다.
starvation 문제에 대한 한 가지 해결 방안은 노화(aging) 이다.
오랫동안 시스템에서 대기한는 프로세스들의 우선순위를 점진적으로 증가시키는 방법이다.
다단계 큐 (Multilevel Queue) 스케줄링
여러개의 준비 큐를 가지는 스케줄링 방법이다. 각 큐는 자기만의 스케줄링 알고리즘을 가질 수 있고, 큐와 큐 사이의 스케줄링도 존재한다.
각 큐는 절대적인 우선순위를 가진다. 우선순위가 높은 큐에 존재하는 프로세스부터 실행되며 우선순위가 높은 큐가 비어있어야 그 아래 단계의 큐를 실행할 수 있다.
프로세스가 생성될 때 정해지는 우선순위에 따라서 해당 우선순위에 해당하는 준비 큐에 등록된다.
작업은 한 큐에서 다른 큐로 옮겨지지 않기 때문에 스케줄링 부담이 적지만 융통성이 떨어진다.
큐 간의 절대적인 우선순위 때문에 startvation이 발생할 수도 있다. 이 경우에 큐들 사이에 시간을 나누어 사용할 수도 있다.
다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링
다단계 피드백 큐 스케줄링 알고리즘 에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.
큐 사이를 이동하는 아이디어는 다음과 같다.
-
프로세스들을 CPU 버스트 성격에 따라 구분한다.
-
어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동된다.
-
I/O 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣는다. (이들은 통상적으로 짧은 CPU 버스트가 특징이다.)
-
마찬가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동할 수 있다. 이 방법으로
startvation을 예방한다.
참고한 곳
