[면접 준비 - CS]프로세스 스케줄러

프로세스 스케줄러(Process Scheduler)는 OS의 핵심 기능으로서

 

동시에 실행되는 프로세스의 실행순서와 우선순위를 관리하는 역할을 한다.

 

조금 더 자세히 말하자면 여러 프로세스가 시스템의 리소스에 접근할 때 필연적으로 경쟁상태에 놓이게 되는데,

 

프로세스 스케줄러는 이 경쟁상태를 적절히 조율해서 리소스의 사용 효율성과 짧은 응답시간,

 

처리량과 처리율 등을 극대화시키기 위해 다양한 알고리즘을 이용해 프로세스의 스케줄을 관리한다.

 

이와 같은 프로세스 스케줄링 알고리즘은 크게 아래의 두 가지로 나뉘며,

 

• 선점형 스케줄링
  특정 프로세스가 CPU를 점유하고 있더라도 우선순위가 높은 다른 프로세스가 실행되면
  강제로 기존 프로세스를 중단시키고 새로운 프로세스를 실행시키는 방식이다.
  우선순위 기반, 라운드 로빈 스케줄링, SRTF(Shortest Remaining Time First)가 이에 포함된다.
• 비선점형 스케줄링
  특정 프로세스가 CPU를 점유하고 있을 때 다른 프로세스가 CPU를 점유하려면 기존 프로세스가 종료되거나
  I/O 이벤트와 같은 예외가 발생해야 하는 스케줄링 방식이다.
  FCFS(First Come First Served) 스케줄링, SJF(Shortest Job First) 스케줄링 등이 이에 포함된다.

시스템의 성능과 응답시간, 현재 상황에 대해 효율적인 알고리즘을 판단하는 것이 중요하다.

 

이어서 프로세스 스케줄링을 구현하기 위한 큐는 크게 세 가지 종류가 존재하며,

 

해당 큐를 이어주는 프로세스 스케줄러 역시 세 가지가 존재하는데

 

계속해서 정리해 보자.

 

 

• Job Queue
  시스템에 올라온 모든 프로세스가 들어가는 대기열이다. 메모리가 할당되었건 그렇지 않건 일단 모두 들어가기 때문에,
  말 그대로 시스템상의 모든 프로세스의 집합이라고 봐도 틀리지 않다.
• Ready Queue
  프로세스 중 메모리를 할당받았으면서 CPU의 할당을 기다리는 프로세스의 집합이다.
  CPU 할당이 일어나면 바로 실행될 수 있는 상태로 대기하며, 해당 큐에 속한 프로세스에게 CPU를 할당하는
  스케줄링 알고리즘이 바로 위에서 언급한 선점/비선점 스케줄링이다.
• Device Queue
  입출력 장치의 자원을 사용하는 프로세스를 저장하는 큐이다. 해당 자원의 사용 이벤트를 위해 대기하고 있으며,
  해당 이벤트 발생 시, 측 입출력 Interrupt 발생 시 Ready상태가 되어 Ready Queue로 이동한다.

이어서 각 큐 사이에서 프로세스를 이동시키는 역할을 하는 스케줄러는 아래와 같다.

 

• Long-term Scheduler
  메모리는 한정되어 있기 때문에 많은 프로세스가 동시에 실행될 경우 메모리가 아닌 대용량 디스크에 임시로 저장된다.
  장기 스케줄러는 디스크에서 이 새로운 프로세스를 가져와 메모리에 할당하는 역할(디스크와 메모리 사이의 스케줄링)을 한다.
  프로세스 입장에서 보자면 'new'에서 'ready'로 상태를 바꿔주는 역할을 하며, 궁극적으로는
  '실행 중인 프로세스 개수'를 관리한다고 볼 수도 있다.
  당연한 말이지만 메모리에 너무 많은 프로세스가 올라가는 것만큼이나 너무 적은 프로세스가 올라가는 것 역시
  성능에는 좋지 않기 때문에, 시스템 성능에 큰 영향을 주는 스케줄러라 볼 수 있다.
  하지만 현대 운영 체제에서는 장기 스케줄러의 역할이 대부분 단기 스케줄러에 의해 수행되는데,
  이는 메모리 용량과 CPU 성능이 대폭 증가해 대부분의 프로세스가 단기 스케줄러에서 바로 실행되기 때문이라고 한다.
• Short-term Scheduler
  단기 스케줄러는 메모리에 올라온 프로세스 중 먼저 실행될 프로세스를 선택하는 역할을 한다.
  일반적으로 프로세스의 작업시간, 입출력 이벤트 등을 고려해 우선순위를 정하며,
  메모리와 CPU 사이의 스케줄링을 담당한다고 할 수 있다.
  일반적으로 프로세스 스케줄러라고 하면 가리키는 것이 바로 이 단기 스케줄러이며
  CPU를 최대한 놀지 않게 하는 역할을 한다.
  추가로 그림에서 보면 실행 단계의 프로세스가 Device Queue로 쫓겨나기도 하는데,
  이와 같은 Ready→Running→Waiting→Ready의 변화하는 상태를 관리하기도 한다.
• Medium-term Scheduler
  중기 스케줄러는 메모리에 너무 많은 프로세스가 올라왔을 경우 일부 프로세스에서 메모리를 할당해제하는 역할을 한다.
  이를 스왑 아웃이라고 부르기도 하며, 이를 통해 메모리 사용량과 CPU 사용 효율을 높일 수 있다.
  언급했듯 메모리 할당이 해제되기 때문에 프로세스가 통째로 디스크로 쫓겨나며, 이 경우는 자력으로 Ready State로
  돌아가는 것이 불가능하다. 추가로 중기 스케줄러 같은 경우는 OS에서 직접 처리해 주기 때문에 개발자는
  단기 스케줄링에 집중해서 프로그래밍을 진행하며, 심지어는 가상메모리가 잘 지원되기 때문에 중기 스케줄러
  자체가 필요 없는 경우도 많다.

마지막으로 처음에 언급했던 스케줄링 알고리즘에 대해 짧게 정리하고 글을 마치자.

 

• Priority Scheduling
  프로세스마다 우선순위를 부여한 뒤에 순서대로 실행(CPU 할당)하는 알고리즘.
  우선순위 값이 같은 경우 먼저 도착한 프로세스를 우선 실행하도록 설정할 수 있다.
  우선순위 스케줄링은 스케줄링 알고리즘 중에서 가장 간단하면서 유연한 방법이며,
  사용자의 사정에 의해 우선순위를 높게 설정하거나 낮게 설정하기가 쉽다.
  다만 우선순위에서 밀린 프로세스는 무기한 대기하게 되는 기아상태(Starvation)에 빠지기 쉽기 때문에
  해당 경우에 대한 처리가 필요하다.
• Round Robin
  라운드 로빈 알고리즘은 가장 현대적인 방법이며, 시분할 환경에서 가장 많이 사용되는 알고리즘이다.
  각 프로세스에 동일한 할당 시간(Time Quantum)을 부여하고 해당 시간이 지나면 프로세스를 중단한 뒤
  다음 프로세스로 전환한다. 즉, 할당 시간 내에 완료되지 못한 프로세스는 대기열의 끝으로 돌아가게 된다.
  따라서 한 프로세스가 CPU를 독점하거나 무기한 대기하는 것을 미연에 방지할 수 있다는 장점이 있으나,
  할당 시간보다 처리시간이 긴 프로세스를 처리할 때 문맥 전환에 오버헤드가 생기고 시간이 지연된다는 단점이 있다.
• SRTF(Shortest Remaining Time First)
  SRTF는 아래에 정리할 SJF의 변형 버전이다. 현재 실행 중인 프로세스의 남은 시간을 고려해,
  남은 실행 시간이 가장 짧은 프로세스에게 우선권을 부여한다.
  빠른 응답 시간과 짧은 대기시간을 자랑하지만, 역시 실행 시간의 정확한 추정이 어려워 구현이 쉽지 않다.
• FCFS(First Come First Served)
  FCFS는 말 그대로 프로세스의 도착 순서대로 CPU를 할당하는 알고리즘이다.
  따라서 먼저 도착한 프로세스가 끝날 때까지 다음 프로세스는 CPU를 사용하지 못하고 대기해야 한다.
  이 방식은 구현이 간단하며 가장 공정하고 직관적인 스케줄링 알고리즘이다. 하지만 프로세스의 실행시간이
  길수록 평균 대기시간이 늘어나며, 이를 해결하기 위해 나온 것이 우선순위 스케줄링 등이다.
• SJF(Shortest Job First)
  SJF는 도착 순서와 상관없이 실행 시간이 가장 짧은 프로세스에게 우선권을 주는 알고리즘이다.
  빨리 완료되는 순서대로 일을 처리하기 때문에 평균 대기시간이 짧다는 장점이 있지만
  실행 시간이 긴 프로세스의 경우 무기한 대기하는 일이 발생할 수 있으며,
  실제 실행 시간을 정확히 예측하는 것은 불가능하기 때문에 실제로 활용하기는 어렵다.
  추가로 SJF에도 선점형/비선점형 방식이 존재한다.