[운영체제 아주 쉬운 세 가지 이야기 - Virtualization] 9. Lottery Scheduling
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
이 장에서는 비례 배분(proportional share) 스케줄러 혹은, 공정 배분(fair share) 이라고도 하는 유형의 스케줄러에 대해 다루도록 하겠다. 비례 배분의 개념은 반환 시간이나 응답 시간을 최적화하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적이다.
비례 배분 스케줄링의 좋은 예가 추첨 스케줄링(lottery scheduling)이다. 기본 아이디어는 매우 간단한데, 다음 실행될 프로세스를 추첨을 통해 결정한다. 더 자주 수행되어야 하는 프로세스는 당첨 기회를 더 많이 준다.
그렇다면 어떻게 CPU를 정해진 비율로 배분할 수 있는가?
기본 개념 : 추첨권이 당신의 몫을 나타낸다
추첨권(티켓)이라는 기본적인 개념이 추첨 스케줄링의 근간을 이룬다. 프로세스가 소유한 추첨권의 개수와 전체 추첨권에 대한 비율이 자신이 받아야 할 자원의 몫을 나타낸다.
추첨 스케줄링은 타임 슬라이스가 끝날 때마다 확률적으로 추첨한다. 스케줄러는 전체 몇 장의 추첨권이 있는지 알아야만 하고, 스케줄러는 추첨권을 선택한다.
예를 들어 A, B 프로세스가 있고 A는 75장의 추첨권을 B는 25장의 추첨권을 가지고 있다면 A에게 CPU의 75%를, B에게 25%를 할당하는 것이다. 추첨권이 0~99의 숫자라면 A가 0~74, B가 75~99의 추첨권을 가지게 된다.
추첨 스케줄러의 당첨 추첨권이
63 85 70 39 76 17 29 41 36 39 10 99 68 83 63 62 43 0 49 49
라면, 스케줄링 결과는 다음과 같다.
A B A A B A A A A A A A B A B A A A A A
이 예에서 볼 수 있듯이 무작위성은 원하는 비율을 정확하게 보장하지는 않는다. B는 20개의 타임 슬라이스 중에 20%에 해당하는 4개의 타임 슬라이스를 얻었기에 원래 목표인 25%와 다르다. 하지만 추첨이 장시간 실행될수록, 원하는 비율을 달성할 가능성이 높아진다.
왜 무작위성을 이용할까?
추첨 스케줄링의 가장 큰 장점은 무작위성인데, 세 가지 장점이 있다.
- 전통적인 방식이 잘 해결하지 못하는 특별한 상황을 잘 대응한다.
예를 들어 Least Recently Used(LRU) 교체 알고리즘은 좋은 성능을 보이지만, 반복되는 순차적인 접근 패턴을 보이는 오버헤드에 대해서는 최악의 성능을 보인다. 하지만 무작위 방식에서는 그러한 최악의 경우가 발생하지 않는다. - 매우 가볍다.
전통적인 공정 배분 스케줄링 알고리즘에서는 각 프로세스가 사용한 CPU 양을 기록해야 하고, 이 정보는 각 프로세스를 실행시킬 때마다 갱신된다. 하지만 무작위 방식에서는 각 프로세스가 가진 추첨권의 개수 같은 프로세스의 상태 정보만 필요하다. - 매우 빠르다
난수 발생 시간이 빠르기만 하면 결정 역시 빠르기에 속도가 중요한 경우에 사용될 수 있다.
추첨 기법
추첨권 화폐 (ticket currency)
이 개념은 사용자가 추첨권을 자신의 화폐 가치로 추첨권을 자유롭게 할당할 수 있도록 허용하고, 시스템은 자동적으로 화폐 가치를 변환한다. 예를 들어, 사용자 A, B가 각각 100장의 추첨권을 받았다고 가정하자. 사용자 A는 A1과 A2의 두 개의 작업을 실행 중이고 자신이 정한 화폐로 전체 1000장의 추첨권 중에 각각 500장의 추첨권을 할당하였다. 사용자 B는 하나의 작업을 실행 중이고 자신의 기준 화폐 10장 중에 10장을 할당하였다.
시스템은 A1과 A2의 몫을 A의 기준 화폐 500장에서 전역 기준 화폐 각각 50장으로 변환하고, B의 추첨권 10장은 전역 기준 화폐 100장으로 변환한다. 그리고 전역 추첨권 화폐량 총 200장을 기준으로 추첨한다.추첨권 양도(ticket transfer)
양도를 통하여 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다. 이 기능은 클라이언트/서버 환경에서 특히 유용하다.
클라이언트 프로세스는 서버에게 메세지를 보내 자신을 대신해 특정 작업을 해달라고 요청한다. 작업이 빨리 완료될 수 있도록 클라이언트는 서버에게 자신의 추첨권을 양도하여 서버가 자신의 요청을 수행하는 동안 서버의 성능을 극대화하려고 한다. 요청을 완료하면 서버는 추첨권을 다시 클라이언트에게 되돌려 주고 먼저와 같은 상황이 된다.추첨권 팽창(ticket inflation)
이 기법에서 프로세스는 일시적으로 자신이 소유한 추첨권의 수를 늘이거나 줄일 수 있다. 물론 서로 신뢰하지 않는 프로세스들이 상호 경쟁하는 시나리오에서는 의미가 없고, 프로세스들이 서로 신뢰할 때 유용하다. 어떤 프로세스가 더 많은 CPU 시간을 필요로 한다면 시스템에게 이를 알리는 방법으로 다른 프로세스들과 통신하지 않고 혼자 추첨권의 가치를 상향 조정한다.
구현
추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 점이다.
필요한 것은 난수 발생기와 프로세스들의 집합을 표현하는 리스트 같은 자료 구조, 추첨권 전체 개수 뿐이다.
A, B, C 프로세스가 있고 리스트를 사용하여 프로세스를 관리하는 예시이다. 스케줄을 결정하기 위해 먼저 총 400개의 추첨권 중에서 한 숫자를 선택해야 한다.
숫자 300이 선택되었다면, 스케줄러는 프로세스 A, B, C의 추첨권을 순서대로 더해가며 300번째 추첨권에 해당하는 프로세스를 선택한다. 이 예시에서는 A가 100장, B가 50장, C가 250장을 가지고 있으므로, C가 선택된다.
일반적으로 리스트를 내림차순으로 정렬하면 이 과정이 가장 효율적이게 되고, 특히 적은 수의 프로세스가 대부분의 추첨권을 소유하고 있는 경우에 효과적이다.
예제
CPU를 공유하는 두 개의 작업 수행 시간을 살펴보자. 각 프로세스는 100개의 추첨권을 가지고 있으며 동일한 수행 시간 R(값 변경 가능)을 가진다.
우리는 두 작업을 거의 동시에 종료시키고자 하지만, 추첨 스케줄링은 무작위성이 있기에 각 작업이 종료되는 시점은 다를 수 있다.
불공정 지표(unfairness metric) U는 이 차이를 정량화하는 수치이다. U는 첫 번째 작업이 종료된 시간을 두 번째 작업이 종료된 시간으로 나눈 값이다. 두 작업이 거의 동시에 종료하면 U는 1에 근접해진다.
그림에서 두 작업의 수행 시간은 1에서 1000까지 변경시켰으며 30번씩 실행시켰다. 그래프에서 보듯 작업 길이가 길지 않은 경우 평균 불공정 정도는 심각하고, 작업이 충분한 기간 동안 실행되어야 추첨 스케줄러는 원하는 결과에 가까워진다.
추첨권 배분 방식
추첨권을 작업에게 나누어주는 방식을 생각해보자. 작업들에게 추첨권을 몇 개씩 분배해야 하는가? 시스템 동작이 추첨권 할당 방식에 따라 크게 달라지기 때문에 상당히 어려운 문제이다.
한 가지 접근 방식은 사용자가 가장 잘 알고 있다고 가정하는 것이다. 각 사용자에게 추첨권을 나누어 준 후 사용자가 알아서 실행시키고자 하는 작업들에게 추첨권을 배분하는 것이다.
하지만 어떤 일을 해야 하는지 전혀 제시하지 않기에 해결책이 아니고, 주어진 작업들에 대한 “추첨권 할당 문제”는 여전히 미해결 상태이다.
보폭 스케줄링 : 왜 결정론적(Deterministic) 방법을 사용하지 않는가?
추첨 스케줄링은 단순하게 구현 가능하지만, 짧은 기간만 실행되는 경우는 정확한 비율을 보장할 수 없다. 그렇기에 결정론적 공정 배분 스케줄러인 보폭 스케줄링(step scheduling)이 고안되었다.
보폭 스케줄링에서 각 작업은 추첨권 수에 반비례하는 보폭(stride)과 pass 값을 가지고, 프로세스가 실행될 때마다 pass 값을 보폭만큼 증가시켜 CPU 사용량을 추적한다. 보폭은 10,000과 같은 임의의 큰 값을 각자의 추첨권 개수로 나눈 값이다.
그리고 스케줄러는 가장 작은 pass 값을 가진 프로세스를 선택한다.
A, B, C가 각각 100, 50, 250개의 추첨권을 가지고 있다면 보폭은 100, 200, 40이 된다. 각자의 pass 값은 0에서 시작하며, pass가 동일하다면 알파벳 순으로 시작한다고 해보자.
- A가 실행되고 A의 pass 값은 100이 된다. (A:100, B:0, C:0)
- B가 실행되고 B의 pass 값은 200이 된다. (A:100, B:200, C:0)
- C가 실행되고 C의 pass 값은 40이 된다. (A:100, B:200, C:40)
- C가 실행되고 C의 pass 값은 80이 된다. (A:100, B:200, C:80)
- C가 실행되고 C의 pass 값은 120이 된다. (A:100, B:200, C:120)
- A가 실행되고 A의 pass 값은 200이 된다. (A:200, B:200, C:120)
- C가 실행되고 C의 pass 값은 160이 된다. (A:200, B:200, C:160)
- C가 실행되고 C의 pass 값은 200이 된다. (A:200, B:200, C:200)
- 이 시점에서 모든 pass 값은 다시 같아지게 되고 이런 과정이 반복된다.
위 과정에서 C는 5번, A는 2번, B는 1번 실행되었다. 이 횟수는 각 프로세스가 가진 추첨권의 개수 250, 100, 50과 정확히 비례한다.
이렇듯 보폭 스케줄링은 각 스케줄링 주기마다 정확한 비율로 CPU를 배분하지만, 추첨 스케줄링은 정해진 비율에 따라 확률적으로 CPU를 배분하는 차이가 있다.
그렇다면 보폭 스케줄링의 정확도가 훨씬 높은데 왜 추첨 스케줄링을 사용할까? 이유는 추첨 스케줄링은 상태 정보가 필요없기 때문이다. 보폭 스케줄링의 스케줄링 중간에 새로운 작업이 시스템에 도착한다면 pass 값이 얼마가 되어야 하는지 정하기 어렵다. 0으로 지정하기 된다면 CPU를 독점하게 될 것이다.
하지만 추첨 스케줄링은 CPU 사용량이나 pass 값과 같은 프로세스 상태를 가지고 있을 필요가 없다. 새 프로세스가 도착한다면 프로세스의 추첨권의 개수, 전체 추첨권의 개수만 갱신하고 스케줄하기에 쉽게 새 프로세스를 추가할 수 있다.
정리
비례 배분 스케줄링(proportional share)
비례 배분 스케줄링 혹은 공정 배분(fair share) 스케줄링은 각 프로세스에 CPU 시간의 비율을 할당하여 보장받는 방식이다. MLFQ는 과거 프로세스의 CPU 점유율을 기반으로 우선순위를 조정하는 식으로 학습하여 적응하였다면, 비례 배분 방식은 미리 정해진 CPU 점유율을 보장하려 한다는 차이점이 있다. 비례 배분 스케줄링의 대표적인 구현은 추첨 스케줄링과 보폭 스케줄링이 있다.
추첨 스케줄링(lottery scheduling)
추첨 스케줄링은 각 프로세스에 티켓의 개수를 할당해 매번 스케줄링 시마다 추첨으로 실행할 프로세스를 선택하는 방식이다. 티켓이 많을수록 실행될 확률이 높아진다.
추첨 스케줄링은 구현이 매우 간단하고, 무작위성을 이용하여 예측할 수 없는 상황에서도 공정하게 CPU를 분배할 수 있다. 추첨 기법으로는 추첨권 화폐(ticket currency), 추첨권 양도(ticket transfer), 추첨권 팽창(ticket inflation)이 있다.
- 추첨권 화폐는 사용자가 추첨권을 자신의 화폐 가치로 자유롭게 할당할 수 있도록 허용하고, 시스템은 자동적으로 화폐 가치를 변환한다.
- 추첨권 양도는 프로세스가 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있는 기능이다.
- 추첨권 팽창은 프로세스가 일시적으로 자신이 소유한 추첨권의 수를 늘이거나 줄일 수 있는 기능이다.
보폭 스케줄링(stride scheduling)
보폭 스케줄링은 각 프로세스에 보폭 값을 할당하고, 프로세스가 실행될 때마다 pass 값을 보폭만큼 증가시켜 CPU 사용량을 추적하는 방식이다. 스케줄러는 가장 작은 pass 값을 가진 프로세스를 선택한다.
보폭 스케줄링은 결정론적인 방법으로 항상 정확한 비율로 CPU를 배분할 수 있지만, 구현이 복잡하고 새로운 프로세스가 도착할 때 pass 값을 어떻게 설정할지 결정하기 어렵다.
참고