[운영체제] CPU 스케줄링 - (2) CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘 

운영체제가 프로세스에 CPU를 배분하는 방법을 CPU 스케줄링 알고리즘을 통해 이루어진다. CPU 스케줄링 알고리즘의 종류는 매우 다양하다. 대표적으로 7가지 CPU 알고리즘에 대해 알아보자. 

 

1. 선입 선처리 스케줄링 (FIFO 스케줄링)

`선입 선처리(FCFS) 스케줄링`은 말 그대로 준비 큐에 삽입된 순서대로 CPU를 할당하는 스케줄링 방식이다. 먼저 들어온 애들은 필수적으로 처리함으로 비선점형 스케줄링 방식이다.

 

부작용으론 `호위 효과(Convet Effect)`가 있다. 비선점 방식이기 때문에 공정하고 합리적인 실행이 되지 않는다. 아래 그림을 보면 프로세스 B가 실행되기 위해선 프로세스 A가 끝날 때까지 기다려야 하므로 17ms를 기다려야 한다. 프로세스 C의 경우는 A, B 모두가 끝나는 시간인 22ms를 기다려야 한다. 

선입 선처리 스케줄링 동작 방식

실행 시간이 짧은 C, B, A 순으로 실행하면 대기 시간을 적게 처리가 가능한대, 순차 처리가 필수임으로 실행시간이 긴 프로세스를 우선 처리함에 따라 뒤에 프로세스들의 실행이 밀리는 경우가 발생되며, 이것이 호위 효과라고 한다.

호위 효과(convoy effect)는 운영체제의 CPU 스케줄링에서 발생하는 현상으로, 낮은 우선순위의 프로세스가 높은 우선순위의 프로세스를 지연시키는 상황을 말합니다. 이는 주로 FIFO(First In, First Out) 스케줄링에서 발생하며, 하나의 긴 작업이 큐의 앞부분에 위치하여 뒤따르는 짧은 작업들이 모두 지연되는 문제를 일으킵니다. 이로 인해 시스템의 전반적인 응답 시간이 증가할 수 있습니다.

 

2. 최단 작업 우선 스케줄링(SJF 스케줄링)

`최단 작업 우선 스케줄링`은 준비 큐 프로세스 중에서 실행 시간이 짧은 프로세스부터 실행하는 스케줄링 방식이다. 실행 시간이 짧은 프로세스부터 실행됨에 따라 위에서 발생한 호위효과를 방지할 수 있다. 

 

기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 뒤에서 언급할 `최소 잔여 시간 우선 스케줄링`처럼 선점형으로 구현될 수 있다. 다음 그림과 같이 실행시간이 짧은 프로세스들을 우선 실행하므로 대기 시간이 줄어든 것을 확인할 수 있다.

 

3. 라운드 로빈 스케줄링 (Round Robin)

라운드 로빈이라는 용어는 CS를 통틀어 많이 사용되는 용어이다. 다음과 같이 정의된다.


라운드 로빈(Round Robin)은 컴퓨터 과학에서 공정하고 균등한 자원 분배를 위해 사용되는 알고리즘입니다. 주로 CPU 스케줄링에서 사용되며, 각 프로세스는 준비 큐에 삽입된 순서대로 일정한 시간 간격(타임슬라이스) 동안 CPU를 할당받습니다. 이 방식은 모든 프로세스가 공평하게 CPU 시간을 얻을 수 있도록 하여, 특정 프로세스가 과도하게 자원을 독점하는 것을 방지합니다. 라운드 로빈은 네트워크 패킷 스케줄링, 운영체제의 작업 스케줄링 등 다양한 분야에서 활용됩니다.

`라운드 로빈 스케줄링`은 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다. `타임 슬라이스`란 프로세스가 CPU를 사용하도록 정해진 시간을 의미한다.

 

즉, 라운드 로빈 방식은 준비 큐에 삽입된 프로세스들이 순차적으로 CPU를 이용하되, 정해진 타임 슬라이스만큼만 CPU를 이용하는 선점형 스케줄링이다. 프로세스가 정해진 시간을 모두 사용하고도 완료되지 않으면 문맥 교환이 발생해 다시 큐의 맨 뒤로 삽입된다.

 

4. 최소 잔여 시간 우선 스케줄링 (SRT 스케줄링)

최소 잔여 시간 우선 스케줄링은 최단 작업 우선 스케줄링과 라운드 로빈 스케줄링을 합친 스케줄링 방식이다. 프로세스들이 정해진 타임 슬라이스만큼 CPU를 이용하되, 남아 있는 작업시간이 가장 적은 프로세스를 다음으로 CPU를 이용할 프로세스로 선택한다.

 

5. 우선순위 스케줄링 

`우선순위 스케줄링`은 프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 처리하는 스케줄링 방식이다. 기본적으론 숫자로 표기된 명시적 우선순위를 의미하지만, 다음 예시와 같이 범용적으로 표현되기도 한다. 

• 최단 작업 우선 스케줄링- 작업 시간이 짧은 순으로 우선순위 부여 
• 최소 잔여 시간 스케주링 - 남은 시간이 짧은 순으로 우선순위 부여

단, 우선순위 스케줄링의 한 가지 근본적인 문제를 내포하고 있다. 우선순위가 높은 순으로 처리되기 때문에 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되었더라도) 우선순위가 높은 프로세스로 인해 계속해서 실행이 연기될 수 있다. 이를 `아사(starvation)현상`이라 한다.

 

이를 방지하기 위한 방법으로 `에이징(aging`)이라는 기법이 있다. 에이징은 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다. 에이징은 적용하게 되면 우선순위가 낮아서 무턱 대고 기다리는 프로세스가 없어짐으로 이사현상을 방지할 수 있다.

 

6. 다단계 큐 스케줄링

`다단계 큐 스케줄링`은 우선순위 별로 준비 큐를 여러 개를 사용하는 스케줄링 방식이다. 우선순위 스케줄링의 발전된 방식으로 우선순위가 가장 높은 프로세스부터 처리하고, 다 처리가 되면 그다음 가장 높은 우선순위 큐를 처리하는 방식이다.

 

이점으론 다음과 같다.

• 프로세스 유형 별로 큐 구분 가능
  CPU 바운드, I/O 바운드, 백그라운드, 포그라운드 ...
• 큐 별로 다른 스케줄링 알고리즘 적용 가능
  선입 선처리 큐, 라운드 로빈 큐 ....
• 큐 별로 다른 타임 슬라이드 적용 가능

 

단, 다단계 큐 스케줄링은 프로세스가 큐 간의 이동이 불가능하다. 그렇기 때문에 우선순위가 낮은 작업은 지속적으로 연기가 되는 아사현상이 발생할 수 있다. 이를 보완하는 스케줄링 알고리즘이 바로 다단계 피드백 큐 스케줄링이다.

 

 

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

`다단계 피드백 큐 스케줄링`은 다단계 큐 스케줄링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있다는 점에서 차이가 있다. 

 

다음과 같은 방식으로 동작한다. 

• 새롭게 진입하는 프로세스는 먼저 가능 높은 우선순위 큐에 삽입되고, 타임 슬라이스만큼 실행이 된다.
• 해당 큐에서 작업이 완료되지 않았다면, 다음 우선순위 큐에 삽입되어 실행된다. 
• 작업이 끝날때까지 다음과 같은 방식으로 진행이 된다.

진행 방식에서 알 수 있듯이, 오래 CPU를 사용해야 하는 프로세스의 우선순위는 점차 낮아지게 된다. 이건 전 포스팅에 언급한 `CPU 집중 프로세스`의 경우 우선순위가 낮아지고, 비교적 CPU를 적게 사용하는 `입출력 집중 프로세스`들은 우선순위가 높은 큐에서 실행이 끝나게 된다. 

 

단. 이러면 여전히 아사 현상이 발생될 수 있음으로 낮은 우선순위 큐에서 오래 기다린 프로세스들은 높은 우선순위 큐로 이동시키는 에이징 기법이 적용된다. 따라서 비교적 CPU를 오래 사용하지 못한 프로세스의 우선순위는 자연스럽게 높아지게 된다.

 

 

참고 

현실 세상의 컴퓨터공학 지식 with 30가지 실무 시나리오 초격차 패키지 Online.

초격차 패키지 : 현실 세상의 컴퓨터공학 지식 with 30가지 실무 시나리오 | 패스트캠퍼스