CPU 스케줄링
운영 체제는 다양한 프로세스와 스레드에 cpu 사용을 배분함으로서 CPU 자원을 관리한다. 이때 사용하는 방법이 CPU 스케줄링이다. CPU 스케줄링 알고리즘은 CPU 스케줄링 절차를 의미하며, 수행하는 OS 일부분이 CPU 스케줄러이다.
프로세스 뿐 아니라 스레드도 CPU 스케줄링의 대상이다. 실행의 문맥을 가지고 있는 모든 것은 스케줄링이 가능하기 때문이다.
CPU 스케줄링의 우선순위
모든 프로세스는 CPU 자원을 필요로 하기 때문에 공정하고 합리적으로 할당해야 한다. 하지만, 언제나 우선순위가 있는 법. 운영체제는 프로세스 별 우선순위를 판단하여 PCB에 명시하고, 우선순위가 높은 프로세스에는 CPU의 자원을 더 빨리 많이 할당한다. 혹은, 사용자가 직접 우선순위를 높일 수도 있다.
운영체제는 어떤 기준으로 우선순위를 판단할까? CPU 활용률이 대표적인 고려 기준이다. 전체 CPU 가동 시간 중 작업 처리 시간의 비율이 높을 수록 우선순위에 두어 프로세스가 실행하게 되도록 한다.
대부분 프로세스들은 CPU와 입출력 장치를 통해 실행과 대기 상태를 오가며 실행한다. 이때 프로세스가 CPU를 이용하는 작업이 CPU Burst, 입출력 장치를 기다리는 작업을 I/O Burst라고 한다. 그런데 프로세스마다 입출력 장치를 이용하는 시간과 CPU를 이용하는 시간의 양에 차이가 있다. 예로 들면 비디오 재생이나 백업의 경우 입출력 작업이 많고, 연산이나 그래픽 처리는 CPU 작업이 많을 것이다. 따라 전자는 입출력 집중 프로세스, 후자는 CPU 집중 프로세스로 분리한다.
입출력 집중 프로세스는 실행 상태보다 입출력을 위한 대기 상태에 더 많이 머무른다. 다만 CPU 집중 프로세스는 대기 상태보다 실행 상태에 더 많이 머무른다. 주로 머무르는 상태가 다르기 때문에 똑같이 CPU를 할당하면 합리적이지 않다. 그러기에 입출력 집중 프로세스를 가장 빨리 실행시켜 끊임 없이 입출력 장치를 작동 시키고 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것으로 합리적 방식을 택한다. 왜냐하면 입출력 장치를 빨리 처리해버리고 CPU 자원을 집중하면 CPU 활용률을 올릴 수 있기 떄문이다. 따라서 입출력 집중 프로세스가 CPU 집중 프로세스 보다 일반적으로 우선순위가 높을 수 밖에 없다.
스케줄링 큐
모든 것은 순서가 있는 법. 자원을 이용하기 위해선 프로세스 들도 줄을 서서 기다려야 한다. CPU를 이용하고 싶거나 메모리에 적재되고 싶은 프로세스 등등은 모두 줄을 서야 한다. 이 줄은 **스케줄링 큐**를 통해 구현된다.
운영체제가 관리하는 큐에는 준비 큐와 대기 큐가 있다. CPU를 이용하고 싶은 프로세스의 PCB가 서는 줄은 준비 큐. 대기 상태에 접어든 프로세스의 PCB가 서는 줄이 대기 큐다. 주로 입출력 작업을 수행 중 일 경우, 대기 큐에서 대기 상태로 입출력 완료 인터럽트를 기다리게 된다.
선점형 스케줄링과 비선접형 스케줄링
스케줄링은 기본적으로 프로세스의 실행이 끝나면 이루어진다. 하지만 프로세스 실행 도중 스케줄링이 수행되는 두 시점이 있다. 실행 상태에서 입출력 작업을 위해 대기 상태로 전환되거나, 실행 상태에서 타이머 인터럽트가 발생해 준비 상태로 변경될 때 다.
앞서 말한 두 상황에서 수행되는 스케줄링 유형은 선점형 스케줄링, 전자의 상황에서 발생하는 것이 비선점형 스케줄링이다. 선점형 스케줄링은 어떤 프로세스가 CPU를 할당 받아 사용하더라도 운영 체제가 프로세스로부터 CPU 자원을 빼앗아 다른 프로세스에게 할당할 수 있는 스케줄링을 의미한다. CPU의 독점을 막고 분배하기 때문에 여러 프로세스에 합리적으로 나눠 쓸 수 있다. 하지만 문맥 교환에 오류가 날 가능성이 높다.
반대로 비선점형 스케줄링은 어떤 프로세스가 종료되거나 대기 상태에 접어 들기 전 까지 건들지 않는 스케줄링이다. 문맥 교환이 상대적으로 적어 오버헤드 발생은 적지만, CPU가 사용을 위해 무작정 기다려야 한다는 단점 또한 존재한다.
스케줄링 알고리즘
운영 체제가 CPU를 할당하는 방법은 CPU 스케줄링 알고리즘이라고 한다.
- 선입 선처리 스케줄링
단순히 준비 큐에 삽입된 순서대로 CPU를 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식이다. 때때로 프로세스가 기다리는 시간이 길어질 수 있다는 단점이 있고, 먼저 삽입된 프로세스로 인해 밀리는 현상을 호위 효과라고 한다.
- 최단 작업 우선 스케줄링
준비 큐에 삽입된 프로세스 중 CPU를 이용하는 시간의 길이가 가장 짧은 프로세스부터 먼저 실행하는 방식이다. 비선점형 스케줄링 알고리즘 이지만, “최소 잔여 시간 우선 스케줄링”처럼 선점형으로 구현이 될 수 있다.
- 라운드 로빈 스케줄링
선입 선처리 스케줄링에 타임 슬라이스가 포함된 방식이다. 타임 슬라이스는 CPU를 사용하도록 정해진 시간을 의미한다. 큐에 삽입된 프로세스들이 삽입된 순서대로 CPU를 이용하고, 정해진 타임 슬라이스 만큼만 이용하는 선점형스케줄링이다. 정해진 시간을 사용하지 못하고 완료 시 문맥 교환이 발생하여 큐 맨 마지막으로 삽입된다.
- 최소 잔여 시간 우선 스케줄링
최단 작업 우선 스케줄링과 라운드 로빈 스케줄링을 포함한 방법이다. 라운드 로빈 스케줄링과 동일하게 이용하되, 남아 있는 작업시간이 가장 적은 프로세스를 다음으로 CPU를 이용할 프로세스로 선택한다.
- 우선 순위 스케줄링
프로세스에 우선 순위를 부여하고 실행하는 방식이다. 문제는 우선순위가 높은 프로세스부터 처리하기에 실행이 연기될 수 있다는 것이다. 즉, 자원을 먹지 못하고 죽어버리는 아사, starvation현상이 일어나는데, 이는 에이징, Aging으로 해결이 가능하다. 오랫동안 대기한 프로세스의 우선순위를 높여 수행하게 하면 해결이 가능하기 때문이다.
- 다단계 큐 스케주링 우선 순위 스케줄링의 발전된 형태로, 준비 큐를 여러개 준비하여 우선순위에 맞게 처리하는 방식이다. 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 비어있으면 그 다음 우선순위가 높은 큐의 프로세스를 처리한다.
하지만 프로세스들이 큐 사이를 이동할 수 없기 때문에 결국 지연되는 것은 동일하다.
7. 다단계 피드백 큐 스케줄링
따라서 이를 해결하기 위해 만들어 진 것이 다단계 피드백 큐 스케줄링이다. 프로세스들은 큐 들 사이를 이동할 수 있어 자연스럽게 CPU 집중 프로세스들의 우선순위는 낮아지고 입출력 집중 프로세스의 우선순위가 높아진다. 타임 슬라이스 동안 실행이 끝나지 않으면 큐를 이동해가면서 낮아지기 때문이다.
참고자료
※ 이 글은 『이것이 컴퓨터 과학이다』 책을 기반으로, 다양한 자료를 참고해 작성했습니다.