CPU 스케줄링

도서 쉽게 배우는 운영체제와 강의 운영체제-반효경 를 보고 정리한 글입니다.

 

 

스케줄링은 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일을 말한다.

 

📌 스케줄링 수준

고수준 스케줄링

장기 스케줄링 이라고도 한다.

 

고수준 스케줄링은 시스템 내의 전체 작업 수를 조절하는 것을 말한다.

 

시스템 상황을 고려하여 어떤 작업을 승인할지, 거부할지를 결정하기 때문에 동시에 실행 가능한 프로세스의 총 개수가 정해진다.

 

저수준 스케줄링

어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다.

 

주로, 프로세스의 상태를 관리하고 단기 스케줄링 이라고도 한다.

 

중간 수준 스케줄링

시스템에 동시에 실행 가능한 프로세스의 수를 고수준 스케줄링이 정한다면

 

중간 수준 스케줄링은 활성화된 프로세스의 수를 조절하여 과부하를 막는다.

 

일부 프로세스를 중지 상태로 옮겨 나머지 프로세스가 원만하게 작동하도록 지원한다.

 

 

📌 스케줄링 알고리즘

스케줄링 알고리즘은 크게 선점형 알고리즘과 비선점형 알고리즘으로 나뉜다.

- 선점형 스케줄링 : 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
- 비선점형 스케줄링 : 다른 프로세스가 CPU를 뺴앗을 수 없는 스케줄링 방식

 

선점형 스케줄링은 시분할 방식, 비선점형 스케줄링은 일괄 작업 방식으로 생각하면 된다.

 

 

FCFS (First Come First Served) 스케줄링

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식이다.

 

큐에 도착한 순서대로 실행되어 단순하고 공평하다고 볼 수 있지만,

 

비선점형 방식이기 때문에, 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스는 대기 시간이 길어져 효율성이 떨어진다.

 

 

SJF (Shortest Job First) 스케줄링

실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다.

 

🚨 단, 프로세스의 종료 시간을 예측하기 어렵고 작업 시간이 길다는 이유로 순위가 계속 밀려 아사 현상이 발생할 수 있다.

 

아사 현상 : 프로세스의 작업이 계속 미뤄지는 현상

 

HRN (Highest Response Ratio Next) 스케줄링

최고 응답률 우선 스케줄링이라고 불리는 비선점형 방식이다.

 

HRN 스케줄링은 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식이다.

 

따라서, SJF 의 문제였던 아사 현상을 어느정도 해결해줄 수 있다.

 

라운드 로빈 스케줄링

할당받은 시간 (타임 슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다.

 

할당 된 시간이 끝나면 CPU를 빼앗기기 때문에 선점형 알고리즘 중 가장 단순하고 대표적인 방식이다.

 

FCFS 방식에서 각 프로세스가 CPU 를 점유할 수 있는 시간 제한이 추가된 방식으로 볼 수 있다.

 

단, 각 프로세스에게 부여하는 CPU 사용 시간을 적절하게 설정해두어야 한다.

 

🚨 타임 슬라이스가 너무 크면 FCFS 방식과 다를게 없어진다. 타임 슬라이스가 너무 작으면 문맥 교환이 너무 자주 일어나 전반적인 성능이 떨어지게 된다.

 

SRT (Shortest Remaining Time) 우선 스케줄링

SJF 스케줄링과 라운드 로빈 스케줄링 방식을 혼합한 방식이다.

 

SJF 스케줄링의 선점형 버전이다.

 

CPU를 할당받을 프로세스를 선택할 때, 작업 시간이 가장 적게 남은 프로세스를 우선으로 선택하고 타임 슬라이스 시간 동안 CPU를 사용할 수 있도록 한다.

 

SJF 의 단점과 유사하게 종료 시간을 예측하기 어렵고 아사 현상이 발생하고 남은 시간을 주기적으로 계산해야 한다.

 

 

다단계 큐 스케줄링

 

우선순위에 따라 준비 큐를 여러개 사용하는 방식이다.

 

각 프로세스는 운영체제로부터 부여받은 우선순위에 따라 큐에 삽입된다.

 

상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

 

🚨 단, 이 방식은 상위 큐에 작업이 계속 들어오면 하위 큐에 있는 작업은 아사 현상이 발생한다.

 

다단계 피드백 큐 스케줄링

 

다단계 피드백 큐 스케줄링은 CPU를 사용하고 작업이 남은 프로세스는 프로세스의 우선순쉬가 하나 낮은 큐의 끝으로 들어간다.

 

또한, 우선 순위에 따라 큐의 타임 슬라이스의 크기가 다르다.

 

 

우선 순위가 낮을 수록 타임 슬라이스가 크다.

 

우선 순위가 낮을 수록 CPU를 얻을 확률이 낮기 때문에, 오랫동안 사용할 수 있도록 하기 위한 목적이다.

 

📌 CPU가 여러개인 경우

1. Queue에 한줄로 세워서 알아서 꺼내가게 한다. (반드시, 특정 CPU에서 수행되어야 하는 경우 프로세스가 있는 경우에 복잡해진다.)

2. 별개의 큐를 사용한다. (일부 CPU의 큐에 작업이 몰리지 않도록 하는 메커니즘이 필요하다.)

3. 여러개의 CPU에 작업을 분배하는 역할만 담당하는 CPU를 정한다.