[운영체제] Ch11. CPU 스케줄링

CPU 자원을 분배하는 방법

1. CPU 스케줄링
2. CPU 스케줄링 알고리즘

 

---

 

1.  CPU 스케줄링 

운영체제가 프로세스에 공정하고 합리적으로 CPU 자원을 배분하는 것을 CPU 스케줄링이라고 한다. 이때, 프로세스의 우선순위 즉, 빨리 처리해야 하는 프로세스 순서에 따라 배분을 하게 된다.

◈  프로세스 우선순위

우선순위가 높은 프로세스에 CPU를 먼저 할당한다. 예를 들어 입출력 작업이 많아 대기 상태에 많이 머무르는 입출력 집중 프로세스는 우선순위가 높다. 반면 CPU 작업이 많은 CPU 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머무르므로 우선순위가 낮다. CPU 사용 빈도가 낮은 프로세스를 먼저 할당하여 빨리 완료시킨 후 CPU 사용 빈도가 높은 프로세스를 실행하는 게 더 효율적이기 때문이다. 이렇게 규칙에 따라 프로세스에 우선순위를 부여하여 PCB에 저장하고, 우선순위가 높은 프로세스를 더 빨리, 더 자주 실행한다.

◈  스케줄링 큐

CPU 사용 우선순위를 포함해 메모리 적재, 입출력 장치 사용 등 자원 배분을 위해 PCB를 매번 조회하여 우선순위를 확인하는 작업은 리소스 낭비가 많다. 따라서 CPU를 사용하고 싶은 프로세스, 메모리에 적재되고 싶은 프로세스, 특정 입출력 장치를 사용하고 싶은 프로세스 등을 줄 세워서 스케줄링 큐로 구현하고 관리한다. (스케줄링 큐는 큐이지만 FIFO이 아니어도 된다). 운영체제가 관리하는 큐에는 CPU를 이용하려는 프로세스의 줄인 준비 큐(Ready Queue), 입출력 장치를 이용하려는 프로세스의 줄인 대기 큐(Waiting Queue) 등이 있다.

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

프로세스가 자원을 사용하고 있는 도중 운영체제가 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는지 여부에 따라 선점형 스케줄링과 비선점형 스케줄링으로 나뉜다. 만약 가능하다면 선점형 스케줄링(Preemptive scheduling)이라고 하며, 자원 독점을 막고 골고루 분배할 수 있다는 장점이 있지만 context switching 과정에서 오버헤드가 발생할 위험이 있다. 만약 강제로 빼앗기가 불가능하다면 비선점형 스케줄링(Non-preemptive scheduling)이라고 하며, context switching으로 인한 오버헤드는 적지만 자원 사용이 급한 상황에도 먼저 사용 중인 프로세스가 사용을 종료할 때까지 기다려야 한다는 단점이 있다.

 

2. CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘은 운영체제마다 서로 다른 알고리즘을 사용하는 만큼 매우 다양하다. 용어보다는 아이디어에 집중하면서 공부한다.

[1] 선입 선처리 스케줄링

선입 선처리 스케줄링은 FCFS 스테줄링(First Come First Served Scheduling)이라고도 불린다.이는 단순히 준비 큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식이다. 자원을 오래 사용하는 프로세스(우선순위가 높은 프로세스)가 와서 자원을 사용하기 시작하면, 사용이 종료될 때까지 기다려야 하는 단점(호위효과: Convoy Effect)이 있다.

[2] 최단 작업 우선 스케줄링

호위효과를 방지하기 위해 자원 사용 시간이 짧은 프로세스를 먼저 실행하는 방식을 최단 작업 우선 스케줄링 혹은 SJF 스케줄링(Shortest Job First Scheduling)이라고 한다.

[3] 라운드 로빈 스케줄링

라운드 로빈 스케줄링(Round Robin Scheduling)은 선입 선처리 스케줄링에 타임 슬라이스(각 프로세스가 자원을 사용할 수 있는 정해진 시간)라는 개념이 더해진 알고리즘이다. 즉, 타임 슬라이스만큼 돌아가면서 자원을 이용하는 선점형 스케줄링 알고리즘이다. 타임 슬라이스 크기가 매우 중요하다.

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

최단 작업 우선 스케줄링과 라운드 로빈을 더하면 최소 잔여 시간 우선 스케줄링 또는 SRT 스케줄링(Shortest Remaining Time Scheduling)이 된다. 즉, 정해진 타임 슬라이스만큼 자원을 사용하되, 다음 순서는 남아있는 작업 시간이 가장 적은 프로세스로 정하는 알고리즘이다.

[5] 우선순위 스케줄링

우선순위 스케줄링(priority scheduling)은 프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 알고리즘이다. 하지만 우선순위가 낮은 프로세스가 준비 큐에 먼저 삽입되었음에도 우선순위가 밀리는 기아 현상(Starvation)이 발생할 수 있다.  이를 방지하기 위해 오래 대기한 프로세스의 우선순위를 점차 높이는 에이징(Aging) 기법이 있다.

[6] 다단계 큐 스케줄링

다단계 큐 스케줄링(miltilevel queue scheduling)에서는 우선순위 순위별로 큐를 따로 두고, 높은 우선순위의 큐부터 처리하는 방식이다. 이때, 큐마다 서로 다른 스케줄링 알고리즘을 적용할 수 있다.

[7] 다단계 피드백 큐 스케줄링

다단계 큐 스케줄링에서 발생하는 기아 현상을 보완하기 위해 나온 것이 다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)이다. 다단계 큐 스케줄링과 다른 점은 프로세스가 큐 사이를 이동할 수 있다는 것으로, 우선순위가 낮은 큐에서 준비 상태가 된 프로세스가 생기면 우선순위가 높은 큐로 이동할 수 있고, 반대로 CPU를 오래 사용해야 하는 프로세스는 우선순위가 낮은 큐로 이동할 수 있다. 구조는 복잡하지만 가장 일반적인 CPU 스케줄링 알고리즘으로 알려져 있다.