리눅스 - 프로세스 스케줄링
프로세스 스케줄링
1. 개요
대부분의 운영체제가 그러하듯 리눅스 역시 시분할 처리를 통해 멀티태스킹을 구현한다.
시분할 처리란 cpu 동작시간이란 유한한 자원을 특정 시간만큼 쪼개어 각 프로세스에 할당하는 것이다.
이 cpu를 어떤 프로세스에 얼마나 오랫동안 할당 할 것인지 결정하는 방법론이 필요한데 이러한 것을 프로세스 스케줄링이라 한다. 이전에 스케줄링에 대한 간략한 개요에 대해서 포스팅한 적이 있으니 이곳 을 참고하면 좋다 이전 포스팅에서 정의한 내용은 별도로 정의하지 않을 것이니 미리 넘어가서 보고 오는게 읽는데 편할 것이다.
이번 포스팅에서는 리눅스에서 어떤 방식을 통해 스케줄링을 하는지 알아보도록 하겠다.
2. 리눅스의 프로세스 스케줄러의 변천사
a. 첫버전 ~ 2.4
가장 첫버전부터 2.4 커널까지 리눅스 스케줄러는 간단하고 평범하게 설계되었다. 때문에 프로세스가 많거나 프로세서가 많은 시스템에서는 확장성있게 구동되지 않았다.
b. 2.5 : O(1) 스케줄러
2.5 커널 시리즈부터 스케줄러 정비 작업에 들어갔는데, 이때 만들어진 새로운 스케줄러는 O(1) 스케줄러라고 불렸다.
시간복잡도를 나타내는 Big O 표기법에서 따온 이 스케줄렁 이름은 입력 크기와 상관없이 일정한 시간안에 작업을 수행한다는 뜻인데, 타임 슬라이스 계산 과정에서 상수 시간 알고리즘을 저용했고, 프로세서마다 별도의 실행 대기열을 만들어 이전 스케줄러에 있었던 확장성 떨어지는 제약을 제거했다.
수십개의 프로세서를 가진 커다란 시스템을 리눅스가 지원할 수 있게 되고 O(1) 스케줄러는 사용할만한 성능을 보여주었으나 응답시간에 민감한 애플리케이션에 대해서는 큰 문제가 발견되었다. 대화형 어플리케이션이 주된 데스크톱 시스템에서는 써먹지 못할 정도로 느렸던 것이다.
c. 2.6 ~ 최신
대화형 성능을 개선하기 위해 새로운 스케줄러가 도입되었다. 회단 계단식 기한 스케줄러(Rotating Staircase Deadline Scheduler)로 공정 스케줄링 개념을 큐잉 이론에서 가져다 적용했다. 여기서 발전하여 2.6.23버전부터 CFS(Completely Fair Scheduler)라고 불리는 완전 공정 스케줄러가 O(1) 스케줄러를 대신하게 되었다.
3. CFS(Completely Fair Scheduler)의 탄생 배경
기본에 CFS에 대해서 논하기 위해서는 NICE값을 알아야한다.
각 프로세스는 NICE 값을 갖고 있고, NICE 값과 우선순위는 반 비례한다. Nice가 높은 프로세스는 관대(Nice)하기 때문에 다른 프로세스에게 순위를 양보한다는 뜻이다.
이 말인 즉슨 NICE값이 낮을 수록 우선순위가 높다. 이 값은 -20에서 +19사이의 값을 가지며 기본값은 0이다.
이전 알고리즘의 경우 이러한 NICE 값에 정비례해서 시간을 할당 받았다. 그렇게하니 몇가지 문제점이 발견되었는데
- CPU 시간을 할당하는 단위에 타임슬라이스라하는데 이 NICE값에 비례하여 타임 슬라이스를 부여하면 작업 전환 최적화가 어렵다.
- 나이스 값의 절대값이 클수록 타임 슬라이스의 차이가 커질 수 있다(ex:nice값이 0에서 100이고, 1마다 5씩 차이날시, 18일때 10, 19일때 5밀리초로 2배 차이)
- 타임슬라이스의 절대값을 할당 할 수 있어야하는데, 절대값이 타이머틱에 종속적이기에 시스템마다 달라질 수 있다.
또한 이전 스케줄링 방식인 우선 순위 기반 방식 일 경우 즉시 실행해야하는 프로세스때문에 기아 현상이 발생 할 수 있다. 따라서 CFS는 위의 경우를 모두 생각하여 아래와 같이 스케줄러 개념을 잡았다.
4. CFS(Completely Fair Scheduler)의 개념
실행 가능한 프로세스가 n개 라고한다면 각 프로세스에 1/n의 프로세스 시간을 할당하면 모든 프로세스를 공정하게 구동할 수 있다. 따라서 CFS는 실행 가능한 전체 프로세스 개수와 관련된 함수를 이용해 프로세스를 얼마동안 실행해야하는지 계산한다.
또한 별도의 나이스값을 통해 타임슬라이스 크기를 계산하지 않고, 프로세스에 할당할 프로세서 시간 비율의 가중치를 나이스 값으로 사용한다.
각 프로세스는 자신의 가중치를 실행 가능한 전체 프로세스 가중치 총합으로 나눈 비율에 해당하는 시간만큼의 시간만큼 실행되는데 CFS는 실제 할당 시간을 계산하기 위해 완전 멀티 태스킹의 무한히 작은 스케줄링 단위를 근사 할 수 있는 목표치를 정해둔다. 이 목표치를 목표 응답시간이라고 하며 목표치가 작을 수록 완전 멀티태스킹에 가깝고 대화형 성능에 좋지만 프로세스 전환이 많아지기때문에 전환 비용이 높아져서 전체 시스템 효율은 나빠진다. 아무래도 전체 프로세스 개수만큼으로 나눠서 실행하기 때문에 일정 임계를 넘어서면 전환 비용을 받아 들일 수 없는 수준까지 오게되는데 이를 방지하기 위해 최소 세밀도(minimum granualarity)라고 최소 값을 지정했으며 이 값의 기본값은 1밀리초이다.
따라서 아무리 프로세스가 많아진다고 하더라도 이 미만으로 떨어지지 않는다.
이렇게 완전 멀티태스킹을 근사하는 알고리즘이므로 진짜 완벽하게 공정할수는 없지만 n개의 지연 시간 조건내에서 n개의 프로세스를 실행하는 조건에서는
참고문헌
- 리눅스 커널 심층분석 (에이콘 임베디드 시스템프로그래밍 시리즈 33, 로버트 러브 저자(글) · 황정동 번역)