CS (Computer Science) - 콘보이 효과, 기아 현상

운영체제는 스케줄링을 통해, 여러 프로세스가 효율적으로 실행될 수 있도록 하고 있다.

효율적이지 못한 스케줄링으로 인해 발생할 수 있는 두 가지 문제 (콘보이 효과, 기아 현상)에 대해 알아보자.

 

만약, 스케줄링이 먼저 들어온 프로세스를 먼저 처리하는 방식이라고 해보자.

 

숫자는 작업 처리에 소요되는 시간이다.

이 때, 3개의 작업이 대기하는 시간을 구해보자.

 

첫 번째 프로세스는 0초를 대기한 뒤, 1초동안 작업을 할 것이다.

두 번째 프로세스는 1초간 대기한 뒤, 15초간 작업을 할 것이다.

세 번째 프로세스는 16초간 대기한 뒤, 3초간 작업을 할 것이다.

 

평균 대기시간은 17 / 3초 (5.66666초)이며, 대기시간 + 작업시간의 평균은 12초이다.

 

이 번엔, 세 작업의 순서만 바꿔보자.

 

첫 번째 프로세스는 0초를 대기한 뒤, 15초간 작업을 할 것이다.

두 번째 프로세스는 15초를 대기한 뒤, 3초간 작업을 할 것이다.

세 번째 프로세스는 18초를 대기한 뒤, 1초간 작업할 것이다.

 

평균 대기시간은 11초이며, 대기시간 + 작업시간의 평균은 52 / 3 초 (17.33333초) 이다.

 

평균적으로 작업이 처리되는 시간이 기존보다 훨씬 길어진 것을 알 수 있다.

이 것이 콘보이 효과이다.

 

작업시간이 긴 프로세스를 우선적으로 처리하느라, 작업시간이 짧은 프로세스가 오랜 기간을 대기하며 평균 대기시간이 높아져 비효율적으로 작업하게 되는 것을 콘보이 효과라고 한다.

 

이를 해결하기 위해선, 짧은 프로세스를 먼저 실행해야 할 것이다.

 

 

이렇게 순서를 바꾸니, 평균 대기시간은 4 / 3 초 (1.333초)이며, 대기시간 +작업시간의 평균은 8초가 되었다.

기존보다 훨씬 효율적으로 작업이 실행되는 것을 알 수 있다.

 

하지만, 이처럼 짧은 프로세스를 우선적으로 실행하기 위해선 계속적인 정렬이 필요하다.

 

 

계속적인 정렬 없이 실행하게 되면, 결국 실행시간이 짧은 프로세스가 뒤에 위치하는 순간이 존재하기 떄문에 실행시간을 기준으로 계속적인 정렬이 필요하다.

 

(실제로는 우선순위 큐를 사용하기 때문에, 정렬이라는 말은 다소 맞지 않을 수도 있다.)

 

그렇다면, 이런 상황을 보자.

2개의 프로세스를 계속 번갈아가며 반복해서 실행하고자 한다.

A프로세스는 1초면 작업을 완료하고, B프로세스는 2초면 작업을 완료한다.

 

A와 B를 동시에 실행시킨다면, A가 실행시간이 더 짧기때문에 우선적으로 실행될 것이다.

A가 끝나고, B가 실행될 차례이다. 하지만, 작업 큐에 A가 다시 삽입되는 순간 A의 실행시간이 더 짧기 때문에 A가 앞으로 오도록 정렬될 것이며 A를 다시 실행하게 될 것이다.

 

A의 작업이 마친 뒤, 다시 B를 실행하고 싶어도 똑같이 A를 실행하게 될 것이다.

 

즉, 작업 시간을 기준으로 계속적인 정렬을 하다보니 작업시간이 긴 프로세스는 영원히 실행되지 않는 상황이 벌어지는 것이다.

 

이를 기아현상 (Starvation)이라고 한다.

 

정리해보자.

콘보이 효과란, 실행시간이 긴 프로세스를 우선적으로 처리하게 되면 다른 프로세스들이 대기하는 기간이 길어져 전체적은 효율이 떨어지는 상황을 의미한다.

기아 현상이란, 실행시간이 짧은 프로세스를 우선적으로 처리하려다 실행시간이 긴 프로세스를 영원히 처리하지 못하는 상황을 의미한다.

기아 현상은 실행 시간을 기준으로 한 스케줄링에서만 문제가 되는 것이 아니라, 어떤 기준이든 우선 순위가 부여된 상황이라면 발생할 수 있는 현상이다. 

 

이를 해결하기 위한 여러가지 알고리즘 중 라운드 로빈이라는 알고리즘이 있다.

 

라운드 로빈 알고리즘이란, 어떤 기준이든 우선순위를 두지 않고 정해진 실행 시간에 맞게 모든 프로세스를 균등하게 실행하는 알고리즘이라고 한다.

 

예를 들어, 작업 시간을 30ms로 설정하였다면 현재 실행중인 프로세스의 작업이 30ms를 초과하는 순간 작업을 강제로 멈추고 대기 큐의 끝으로 밀어넣는다고 한다.