[OS] 스케줄링 알고리즘과 우선순위

프로그램은 디스크에 저장이 되어있고, 더블클릭을 하여 프로그램이 운영체제의 자원을 할당받아 메모리에 올라오며 실행되는 상태가 프로세스.

이러한 프로세스는 우리 컴퓨터의 메모리에 하나만 올라와있는것이 아니고 여러개가 존재하기에, CPU는 이 모든 프로세스를 돌아가며 실행시켜야 한다.

그 일을 담당하는 것이 바로 스케줄러. 

 

선점형 OS와 비선점형 OS

프로세스의 실행을 다른 프로세스로 넘기는 방식에 따라 선점형 OS와 비선점형 OS를 구분한다.

먼저 비선점형 OS는 현재 실행중인 프로세스보다 높은 우선순위의 프로세스가 등장한다고 해서 실행의 대상을 바로 변경하지 않는다.

새로 등장했거나 높은 우선순위의 프로세스가 실행되기 위해서는 현재 실행중인 프로세스가 CPU 타임 슬라이스를 다 사용했거나 I/O작업으로 인한 블록킹 상태(대기 상태에 들어간다)에 놓일 때까지 기다려야 한다.

 -> 지금은 거의 사용되지 않는 방식의 OS

 

반대로 선점형 OS는 현재 실행 중인 프로세스보다 높은 우선순위의 프로세스가 등장하면 스케줄러에 의한 실행순서 조정이 가해진다. (비선점형 OS의 스케줄러보다 하는일이 많다.)

이러한 특징은 둘 이상의 프로세스를 동작시키는 멀티 프로세스 기반 OS에 적합하다.

 -> 스케줄러에 의해 실행순서가 적절히 조절되니 프로그래머가 신경쓸 일이 적어지기에.

 -> Windows OS도 선점형 OS. (대부분의 OS는 선점형 OS라고 한다. 애초에 선점형 OS가 시분할 방식을 고려해서 만들어짐.)

 

이제 Windows에서 채택하고 있는 대표적인 선점형 스케줄링 알고리즘 두 가지를 보자.

 

- 우선순위(Priority) 스케줄링 알고리즘

우선순위 스케줄링 알고리즘은 각각의 프로세스마다 우선순위를 부여해 우선순위가 높은 프로세스를 먼저 실행시키는 방식.

우선순위가 높은 A프로세스와 낮은 B프로세스가 있다고 보자. CPU는 하나(싱글코어)이며 위 우선순위 스케줄링 알고리즘에서 누가먼저 선택되어 실행되냐고 묻느냐면 당연히 A프로세스.

보편적인 상황에서 우선순위가 낮은 B프로세스는 결코 실행되지 않는다. 

 -> 이러한 상황을 가리켜 기아(Starvation)상태라 한다. (자신의 차례가 영원히 오지를 않아 실행되지 않으므로)

우선순위 스케줄링 알고리즘에서는 스케줄러가 우선순위가 높은 프로세스를 선택해 실행한다. 즉 우선순위가 높은 프로세스가 작업을 마쳐야 그 다음 우선순위의 프로세스가 실행된다.

 

그렇다면 프로세스B는 100% 영원히 실행되지 않을까? 프로그램에서 I/O가 차지하는 비중은 생각보다 높다.

즉 프로세스A에서 I/O를 처리하기 위해 Blocking(대기)상태에 빠진다면 우선순위가 낮은 프로세스가 실행될 수 있는 기회를 얻는 것.

 -> 기아 상태의 문제를 해결하기 위한 에이징(aging)이론도 있다. 

 -> 간단히 말하면 우선순위가 낮은 프로세스의 무한대기를 막기 위해서 우선순위를 한단계씩 높이는 방식.

이러한 우선순위 스케쥴링 알고리즘은 Windows에서도 채택하고 있는 알고리즘. 위는 선점형 OS의 대표적인 특징이다.

 

- 라운드 로빈(Round-Robin) 스케줄링 알고리즘

선점형 OS가 우선순위가 높은 프로세스가 먼저 실행된다고 했는제 그렇다면 우선순위가 동일한 프로세스의 경우에는 누가 먼저 실행이 되어야 할까.

여기서 우선순위가 동일함에도 불구하고 한쪽은 실행되는데 한쪽은 실행되지 않는다면 형편성에 어긋난다.

그렇기에 Windows에서는(대부분 선점형OS에서도) 라운드 로빈 스케줄링 알고리즘도 적용하고 있다.

 -> 라운드 로빈 스케줄링의 동작방식은 준비 상태에 있는 프로세스들이 준비 큐(FIFO)에 대기하고 있다가 실행상태가 되고 CPU 사용시간을 다 사용했다면 큐의 뒤쪽에 다시 삽입된다.(간단한 방식)

https://hyuntaekhong.github.io/blog/OperatingSystem03/

이 알고리즘은 같은 우선순위의 프로세스들간 형평성 유지를 위해, 정해진 시간 간격만큼만 실행을 하고 우선순위가 동일한 다른 프로세스에게 CPU의 할당을 넘기는 방식을 제공한다. (오로지 형편성을 위해서)

 -> 시분할 운영체제에서 프로세스는 CPU의 사용시간(타임 슬라이스)가 끝날 때 CPU의 할당을 넘긴다.

동일한 우선순위의 프로세스도 마찬가지로 이 타임 슬라이스를 기준으로 CPU의 할당을 넘기게 된다.

출처 - 윤성우님의 뇌를 자극하는 윈도우즈 시스템프로그래밍

정리하면 Windows운영체제에서 프로세스를 스케줄링하는데 있어서 우선순위,라운드 로빈 기반의 알고리즘을 적용한다.

 

스케줄링 알고리즘에 의해 스케줄링이 진행되는 시점

선점형 운영체제를 설계한느 상황에 놓였다고 생각해보면, 어느 시점에 스케줄러가 동작하도록 설계하면 좋을까.

세가지 관점에서 생각해볼 수 있다.

 

먼저 라운드 로빈 방식의 스케줄링 알고리즘 적용에 대한 관점.

정해진 시간(타임 슬라이스)이 지나면 다음 프로세스에게 CPU를 넘겨줘야 한다. 이렇게 실행순서를 넘기기 위해서는 스케줄러가 동작해야 한다. (실행상태의 프로세스를 준비상태로 바꾸고 준비상태에 있는 프로세스를 실행상태로 바꾸고)

즉. 프로세스의 실행시간 간격에 해당하는 타임 슬라이스가 종료되는 시점마다 스케줄러는 동작해야 한다.

 

그 다음은 우선순위 방식의 스케줄링 알고리즘의 관점.

우선순위가 높은 프로세스는 무조건 먼저 실행되어야 한다. 따라서 새로운 프로세스가 등장할 때마다 스케줄러는 현재 실행중인 프로세스와 새로운 프로세스를 비교해야 한다. 

즉 새로운 프로세스가 생성될 때마다 스케줄러는 동작해야 한다.

 -> 반대로 현재 실행상태인 프로세스가 종료되면 다른 프로세스의 상태를 실행상태로 바꿔야 하므로 이 경우에도 스케줄러가 동작해야 한다.

 

마지막으로 Blocking(대기)상태에 빠지는 경우. 현재 실행 중인 프로세스가 I/O에 의해 블록킹 상태에 빠진다면 다른 프로세스가 실행되어야 한다. 그렇기에 현재 실행중인 프로세스가 블록킹 상태에 놓인다면 다음 실행될 프로세스 선정을 위해 스케줄러는 동작해야 한다.

 

스케줄러가 동작해야 할 타이밍을 정리해보면

1. 매 타임 슬라이스마다 스케줄러 동작

2. 프로세스가 생성 및 소멸될 때마다 스케줄러 동작.

3. 현재 실행중인 프로세스가 블록킹 상태에 놓일 때마다 스케줄러 동작.