[운영체제] CPU 스케줄링 - (1) 프로세스 우선순위와 스케줄링 큐

프로세스 우선순위

운영체제에서 프로세스(및 스레드)가 실행되기 위해선 자원이 필요로 한다. 운영체제가 공정하고 합리적으로 자원을 배분하는 방법을 `스케줄링`이라고 한다.

 

여기서 CPU(=자원)을 할당받아 배분하는 방법을 `CPU 스케줄링`이라 한다.

 

CPU 자원을 공정하게 배분하는 방법이란 단순히 돌아가면서 CPU를 프로세스들에게 할당하는 것을 의미하지 않는다. CPU의 자원을 할당받는 자원들은 우선순위를 가지고 있고, 운영체제는 프로세스 별 `우선순위(priority)`를 판단하여 우선순위가 높은 프로세스에 CPU의 자원을 더 빨리, 더 많이 할당하게 된다. 

프로세스의 우선순위는 이전 포스팅에서 정리한 내용과 같이 PCB에 명시되어 있다.

 

유닉스 계열의 운영체제에서는 ps 명령어를 통해 우선순위 확인이 가능하다. 

PR, NI가 낮을수록 높은 우선순위를 나타낸다. 

 

윈도우에선 `Process Explorer`라는 소프트웨어에 `Priority`항목을 통해 확인이 가능하다.

 

우선순위의 차이를 보이는 대표적인 프로세스 유형

대표적으로 아래 2가지로 나눠진다.

• 입출력 집중 프로세스(I/O bound process)
• CPU 집중 프로세스(CPU bound process)

 

먼저 두 프로세스 유형을 알아보기 전에 운영체제가 자원 할당에 있어 대표적으로 고려하는 `CPU활용률(CPU utilization)`에 대해 알아보자. 

 

CPU활용률이란 전체 CPU의 가동 시간 중 작업을 처리하는 시간의 비율을 의미한다. 운영체제는 높은 CPU활용률을 유지해야 하며, 기본적으로 입출력 작업이 많은 프로세스의 우선순위를 높게 유지하게 된다.

 

프로세스는 다음과 같이 CPU를 사용하는 구간과 입출력 장치를 대기하는 구간이 반복되며 실행하게 된다. 여기서 CPU를 사용하는 구간을 `CPU 버스트(CPU burst)`라고 하며, 입출력 장치를 대기하는 구간을 `입출력 버스트(I/O burst)`라고 한다.

 

 

그런데 프로세스마다 입출력 구간이 많은 작업이 있을 수 있고, CPU 작업이 많은 프로세스가 존재할 수 있다. 전자를 `입출력 집중 프로세스`라고 하고, 후자를 `CPU 집중 프로세스`라고 한다.

 

입출력 집중 프로세스의 경우 실행 상태보다 입출력을 위한 대기 상태에 더 많이 머물게 되며, CPU 집중 프로세스의 경우 대기 상태보다 실행 상태에 더 많이 머물게 된다. 

 

각자 주로 머무르는 상태가 다르기 때문에 모든 프로세스가 동일한 시간의 빈도로 CPU를 사용하는 것은 합리적이지 않다. 

 

입출력 집중 프로세스와 CPU 집중 프로세스가 동시에 CPU자원을 요구했다면, 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 끊임없이 입출력장치를 작동시킨 다음, CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 합리적이 방법이 된다.

 

그 이유는 다음과 같다. 

• 입출력에 경우 실행 상태보다 입출력을 위한 대기 상태에 더 많이 머물게 된다. 그렇기 때문에 빨리 처리하고 다른 프로세스를 실행시켜서 CPU활용률을 높이는 게 좋은 방법이 될 수 있다.
• 그래서 일반적으로 입출력 집중 프로세스가 CPU 집중 프로세스보다 우선순위가 높은 것이다.

 

 

스케줄링 큐

자원은 한정적인데 실행 중인 프로세스는 여러 개다. 이런 경우 운영체제는 '자원을 이용하고 싶으면 줄을 서서 기다릴 것'을 요구한다. 

 

프로세스는 비단 CPU 뿐 아니라 메모리, I/O장치 등 이용하고 싶은 자원을 요청하며, 이러한 각기 다른 자원을 요구하는 상황 속 프로세스들의 요구사항을 일목요연하게 관리하는 방법이 `스케줄링 큐`이다. 

 

정리하자면, 특정 자원을 이용하고자 하는 프로세스들이 서는 줄을 이용해 프로세스한테 자원을 할당하는 것을 스케줄링 큐라 말한다. 

큐는 자료구조 관점에선 선입선출형태를 따르게 된다. 하지만 스케줄링 큐는 반드시 선입선출일 필요는 없다.

 

대표적인 스케줄링 큐

• 준비 큐 : CPU 이용을 기다리는 프로세스들의 큐
• 대기 큐 : 대기 상태 프로세스들의 큐 (입출력 요청)

준비상태 : 당장이라고 실행이 가능하나 자원이 할당되지 않아(내 차례가 오지 않아) 실행되고 있지 않은 상태
대기상태 : 보통 입출력 요청, 특정 이벤트가 올 때까지 기다리고 있는 상태를 의미한다.

 

`준비 큐(ready queue)`는 실행상태에서 `실행시간완료(타이머 인터럽트)`가 발생하게 되면 `준비 상태`가 되어 `준비 큐`의 마지막에 삽입되어 CPU사용에 대한 할당 차례를 기다리는 것을 의미한다. 

 

`대기 큐(waiting queue)`의 경우 실행상태에서 `입출력장치 요청`에 대한 명령을 받게 되면 입출력 장치가 작업이 완료(완료 인터럽트)를 되기까지 `대기상태`로 기다려야 한다. 이러한 대기상태가 되면 `대기 큐` 삽입되어 기다리게 된다. 

 

여기서 `입출력 완료 인터럽트`가 오게 되면 대기 큐에서 나와 `준비 상태`가 되어 `준비 큐`에 삽입되어 차례를 기다리게 된다.  

 

 

대기큐에 경우 

- 실행을 하다 `입출력장치 요청`을 받게 되면 당장은 실행할 수가 없다. 일출력 작업이 완료될 때까지 대기를 해야 한다. 그런 대기상태가 되며 대기큐에 삽입되어 기다리게 된다. 입출력 완료 인터럽트가 발생하게 되면 대기 큐에서 작업이 완료된 PCB를 찾고 이 PCB를 준비상태로 변경 후 큐에서 제거한다. 당연히 해당 PCB는 준비큐로 이동하게 된다.

 

 

입출력 장치가 여러 개인 것처럼 대기 큐의 종류도 다음과 같이 여려 개로 존재하게 된다. 이러한 구조로 통해 운영체제는 동시다발적인 자원의 요구를 효율적으로 관리할 수 있게 된다.

 

단, 주의할 점이 있는데 스케줄링 큐는 자료구조 큐와 달리 FIFO를 무조건적으로 따르지 않는다. 처리해야 할 프로세스마다 우선순위가 존재하며, 우선순위가 낮은 큐가 먼저 삽입되었다고 해도 우선순위가 높은 프로세스가 있다면 해당 프로세스가 먼저 처리될 수 있다.

 

 

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

한 프로세스 실행 도중 다른 급한 프로세스가 실행되어야 하는 상황이 있다면 다음과 같이 처리할 수 있을 것이다.

1. 현재 실행 중인 프로세스의 자원을 빼앗아 해당 프로세스에게 할당 
2. 현재 실행 중인 프로세스 실행이 끝날 때까지 해당 프로세스 대기

 

첫 번째 경우가 `선점형 스케줄링`을 의미하며 다음과 같은 특징을 가지게 된다. 

• 프로세스에 자원을 고루 할당이 가능하다. 
• 문맥교환이 자주 일어남으로 오버헤드가 발생될 가능성이 있다.

 

두 번째 경우인 `비선점형 스케줄링`은 다음과 같은 특징을 가진다. 

• 고르지 않은 자원분배(우선 실행 중인 작업이 끝날 때까지 기다려야 하므로)
• 문맥교환이 적기 때문에 오버헤드가 상대적으로 적다.

 

위에서 설명한 타임아웃 기반 문맥교환이 선점형 스케줄링을 나타낸다. 

 

참고

혼자 공부하는 컴퓨터 구조+운영체제