[CS] 운영체제 (3) CPU 스케줄링

CPU 스케줄링은 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것이다.

 

이 때 프로세스 우선순위를 봐야하는데 가장 공정한 CPU 스케줄링이라 하면 입출력 작업이 많은 프로세스(=입출력 집중 프로세스)의 우선순위는 CPU 작업이 많은 (=CPU 집중 프로세스)의 우선순위보다 높다. 입출력 집중 프로세스는 잠깐만 CPU를 쓰면 되기 때문에 먼저 우선순위를 높여서 먼저 처리하고 CPU 작업이 많은 프로세스에 CPU를 더 몰아주는게 효율이 좋다. 이 프로세스 우선 순위는 프로세스의 PCB에 저장 된다.

 

 

우선 순위를 알기 위해 모든 PCB를 다 뒤지는 건 비효울적이다. 많기도 하지만 프로세스도 계속해서 생겨나기 때문이다. 그래서 운영체제는 스케줄링 큐를 사용한다. 특정 자원을 요구하는 프로세스를 줄을 세우는 것이다. 다만 스케줄링에서의 큐는 반드시 선입선출 방식일 필요는 없다.

 

 

준비 큐와 대기 큐

준비 큐는 CPU를 이용하기 위해 기다리는 줄이고 대기 큐는 입출력 장치를 이용하기 위해 기다리는 줄이라고 할 수 있다. 대기 큐는 같은 장치를 요구한 프로세스들은 같은 큐에서 대기하게 된다. 스케줄링 큐에서는 같은 큐에 있어도 우선순위에 따라 먼저 처리된다.

 

프롯세스 상태 다이어그램

 

선점형과 비선점형 스케줄링

급한 프로세스가 발생했을 때 두 가지 방법이 있다. 첫 번째는 현재 CPU를 사용 중인 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에 할당하는 것이다. 이를 선점형 스케줄링이라고 한다. 두번째는 현재 CPU를 사용 중인 프로세스의 작업이 끝날 때까지 프로세스가 기다리는 것이다. 이를 비선점형 스케줄링 이라고 한다.

 

-선점형 스케줄링

어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분할 수 있다. 다만 그만큼 문맥 교환 과정에서 오버헤드가 발생할 수 있다.

 

-비선점형 스케줄링

선점형 스케줄링에 비해 문맥 교환에서 발생하는 오버헤드가 적다. 다만 모든 프로세스가 골고루 자원을 이용하기 어렵다.

 

 

CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘엔 다음과 같은 것들이 있다.

1. 선입 선처리 스케줄링
2. 최단 작업 우선 스케줄링
3. 라운드 로빈 스케줄링
4. 최소 잔여 시간 우선 스케줄링
5. 우선순위 스케줄링
6. 다단계 큐 스케줄링
7. 다단계 피드백 큐 스케줄링

 

선입 선처리 스케줄링

FCFS 스케줄링이라고도 한다. 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점형 스케줄링이다. 먼저 CPU를 요청한 프로세스부터 CPU를 할당하게 된다. 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용이 있는데 이를 호위효과라고 한다.

 

 

최단 작업 우선 스케줄링

SJF 스케줄링이라고도 하며 호위 효과를 방지하기 우해 CPU 사용이 긴 프로세스는 나중에 실행하고, CPU 사용 시간이 짧은 프로세스는 먼저 실행하게 한다. CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식이라고 할 수 있다.

 

 

라운드 로빈 스케줄링

RR 스케줄링. 차례대로 무엇을 한다는 뜻으로 선입 선처리 스케줄링 + 타임 슬라이스라고 할 수 있다. 타임 슬라이스는 각 프로세스가 CPU를 사용할 수 있는 정해진 시간이다. 즉 정해진 타임 슬라이스만큼의 시간 동안 돌아가면서 CPU를 이용하는 선점형 스케줄링이다. 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되 정해진 시간만큼만 이용하고 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다.(문맥 교환) 타임 슬라이스가 너무 크면 호위효과가 발생할 수도 있고 너무 작으면 문맥교환 오버헤드가 발생할 수 있기 때문에 타임 슬라이스의 크기가 중요하다.

 

 

최소 잔여 시간 우선 스케줄링

SRT 스케줄링. 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링이라고 할 수 있다. 최단 작업 우선 스케줄링은 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘이고 라운드 로빈 스케줄링은 정해진 타임 슬라이스만큼 돌아가며 사용하는 스케줄링 알고리즘이다. 즉 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스를 선택하는 것이다.

 

 

우선순위 스케줄링

프로세스들에 우선순위를 부여하고 우선순위가 높은 프로세스부터 실행한다. 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링한다. 최단 작업 우선 스케줄링, 최소 잔여 시간 스케줄링이 우선 순위 스케줄링에 포함된다. 다만 기아 현상(starvation)이라는 근본적인 문제점이 있다. 자세히 설명하면 우선 순위가 높은 프로세스만 주구장창 실행되며 우선 순위가 낮은 프로세는 준비 큐에 먼저 삽입 되었음에도 불구하고 주구장창 실행이 연기 될 수 있다. 이를 방지하기 위한 기법으로 에이징이 있다. 오랫동안 대시한 프로세스의 우선순위를 점차 높이는 방식이다. 대기 중인 프로세스의 우선순위를 마치 나이 먹듯이 점차 증가시키는 방식이다.

 

 

다단계 큐 스케줄링

Multilevel queue 스케줄링. 우선 순위 스케줄링의 발전된 형태이다. 우선 순위 별로 준비 큐를 여러 개 사용하는 스케줄링 방식으로 우선 순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고 우선 순위가 가장 높은 큐가 비어있으면 그 다음 우선 순위 큐에 있는 프로세스를 처리한다.

 

 

다단계 피드백 큐 스케줄링

Multilevel feedback queue 스케줄링. 다단계 큐 스케줄링의 발전된 형태인데 큐 간의 이동이 가능한 다단계 큐 스케줄링이다. 다단계 큐 스케줄링에서는 기본적으로 큐 간의 이동이 불가해 우선 순위가 낮은 프로세스는 계속해서 실행이 연기될 우려가 있다.(기아 현상 발생) 하지만 이 방법에서는 큐에서 이동이 가능하다. 일단 프로세스를 우선 순위가 제일 높은 큐에 넣고 실행이 끝나지 않았다면 우선 순위가 낮은 큐로 점점 낮게 이동한다. 자연스럽게 CPU 집중 프로세스의 우선순위는 상대적으로 낮아지고 입출력 집중 프로세스의 우선순위는 상대적으로 높아지게 된다. 여기서도 에이징 기법을 적용할 수 있다. 즉 정리하자면 어떤 프로세스의 CPU 시간이 길면 우선 순위가 낮아지고 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식이다.