[CS] CPU의 스케쥴링 Scheduling 이란 무엇일까? 그리고 종류를 알아보자!
1. CPU와 스케줄링의 연관성
우선 CPU의 구성은 총 3가지로 이뤄져있습니다.
1. ALU (Arithmetic Logic Unit) 산술 논리 연산 장치
2. CU (Control Unit) 제어부와 내부버스
3. 메모리 유닛(레지스터 & 캐쉬메모리L1)
이번 글에서 중요한 것은 CU입니다. 스케줄링을 하는 주체이기 때문이죠.
CU의 이름에는 컨트롤이라는 말이 들어갑니다. 도대체 무엇을 컨트롤 한다는걸까요?
그것은 바로 cpu의 핵심 기능인 자원배정입니다.
(개인적으로는 일정을 완벽하게 짜주는 비서역할이라 표현하겠습니다.)
CU는 CPU가 연산해야할 각각의 프로세스를 "어떤 순서"로 "얼마만큼의 시간동안" 혹은 "얼마만큼의 처리량"을 감당할지에 대한 비서역할(스케쥴링)을 합니다.
이로써 CPU는 더 효율적으로 일을 처리할 수 있게 되었습니다.
2. 스케쥴링의 분류
스케쥴링은 어떠한 기준에 의하여 크게 2가지로 분류할 수 있습니다.
"한 프로세스가 cpu 점유를 자진 반납할때까지 실행을 보장하는 경우" 비선점 스케쥴링
"OS의 cpu 선점으로 인해 (호출 종료, 시분할 시스템) 등으로 우선순위의 강제성이 있는 경우" 선점 스케쥴링
비선점 스케쥴링
프로세스의 문맥전환이 적어 오버헤드(CPU의 사치)가 적으며, 처리시간 예측이 쉽습니다.
그러나 앞선 프로세스들의 자원점유가 길어지면, 다음 차례에서 실행되어야할 프로세스들이 기아상태(연산처리를 장시간 못받는 상태)가 될 수 있습니다.
선점 스케쥴링
우선순위가 높은(혹은 긴급한) 프로세스들을 신속하게 처리할 수 있습니다. 프로세스 기아가 적습니다.
그러나 문맥전환이 잦아 오버헤드가 상대적으로 많이 발생하며 처리시간을 예측하기 어렵습니다.
3. 비선점 스케쥴링의 종류
1.FCFS (first come, first serve)
"먼저 온 놈, 먼저 준다"
FIFO(먼저 들어온거, 먼저 출력)를 이용한 가장 기본적인 스케쥴링 방식입니다.
Convoy Effect(호위효과)라는 것이 발생하는데, 쉽게 말하면 앞 프로세스의 처리 시간이 길어짐에 따라 나머지 프로세스들이 오래 기다리게 되는 것을 말합니다.
또한 이로 인하여 프로세스간의 평균 대기시간 편차가 심해집니다.
2. SJF(Shorted Job First)
"작은일부터 먼저"
서로 다른 프로세스가 같은 cpu버스트 시간(실질적으로 처리하는 시간)을 가졌다면 FIFO를 따릅니다.
("같은 시간이면, 먼저 온 놈이 먼저")
/ cpu를 점유중인 프로세스의 잔여 버스트 시간과, 새로 들어온 프로세스의 cpu버스트를 비교하여 더 짧은 버스트시간을 가진 프로세스를 우선합니다.
평균적으로 FCFS방식 보단 대기시간이 줄어듭니다.
3. HRN (Highest Response-ratio Next)
우선순위를 계산하여 먼저 처리하는 방식입니다. SJF의 불평등 점유를 개선한 방식입니다.
우선순위 : (대기시간 + 실행시간) / (실행시간)
4. 선점 스케쥴링의 종류
1. Priority Scheduling (우선순위 스케쥴링)
HRN 스케쥴링과 비교하여 좀 더 동적/정적인 다양한 방식을 사용하여 우선순위를 계산하는 방식입니다.
이때 우선순위가 낮은 프로세스는 무한정 대기하여 기아가 발생할 수 있겠죠??
그래서 Aging 방식이라는 것이 있습니다. 이것은 기다리는 시간에 따라 우선 순위를 좀 더 높게 배정해줍니다.
2. Round Robin(라운드로빈)
"사이좋게 돌아가며"
각 프로세스가 정해진 할당시간 만큼만 점유를 하고,
시간이 끝나면 준비완료 큐의 마지막으로 가서 다시 재할당을 기다립니다.
이때 정해진 시간할당량이 너무 적으면, 빈번한 문맥전환으로 인해 오버헤드가 발생하며,
FCFS와 유의미한 차이를 발생시키지 못합니다.
3. Multilevel-Queue(다단계 큐)
각 상황에 맞게 프로세스들을 점유하기 위하여,
준비완료 큐(준비된 프로세스 대기열)를 여러개의 큐로 분류합니다.
각각의 큐들은 각자 다른 스케쥴링 알고리즘을 갖게 됩니다.
이때 큐들은 우선순위에 따라 Forground Queue(우선점유)/ Background queue(후순위 점유) 로 구별됩니다.
(프로세스 스케쥴링 +큐의 우선순위를 배정하는 스케쥴링도 필요)