Operating sysetem - MLFQ
◼︎ MLFQ
멀티 레벨 피드백 큐(Multi-level Feedback Queue, MLFQ)를 다뤄볼 것이다. 이것이 해결하려는 기본적인 문제는 두 가지이다.
- 짧은 작업을 먼저 실행시켜 반환 시간을 최적화 앞에서 한 알고리즘을 쓴다. 그런데 실행 시간 정보를 모르는 것이 문제이다.
- 응답 시간을 최적화 그런데 이렇게 응답 시간 최적화 알고리즘을 쓰면 반환 시간이 최악이다.
◼︎ MLFQ : 기본규칙
MLFQ는 여러 개의 큐로 구성되며 각각 다른 우선순위(priority level)을 가진다. 높은 우선순위의 큐에 존재하는 작업을 실행하게 되는 것이다. 이 큐 안에는 여러개의 작업이 존재하는 것도 가능한다. 이 작업들은 모두 같은 우선순위를 가져 RR 스케줄링 알고리즘이 적용된다. MLFQ에서 제일 중요한건 우선순위를 정하는 방식이다. 고정된 우선순위를 부여하는 게 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다. 오래 대기하게 되면 우선순위가 높아지고 오래 실행되면 우선순위가 낮아진다.
다음은 MLFQ의 두 가지 기본 규칙이다.
- 규칙 1: Priority(A) > Priority(B) 이면, A가 실행
- 규칙 2: Priority(A) = Priority(B) 이면, A와 B는 RR방식으로 실행
◼︎ 시도 1: 우선 순위 변경
우선 순위를 변경하는 규칙은 다음과 같다.
- 규칙 3: 작업이 시스템에 진입하면 맨 위의 큐(가장 높은 우선순위)에 놓인다
- 규칙 4a: 주어진 타임 슬라이스를 다 사용하면 한 단계 아래 큐로 이동(우선순위가 낮아진다)
- 규칙 4b: 타임 슬라이스를 소진하기 전 CPU 양도하면 우선순위 유지
예시 1: 한 개의 긴 실행 시간을 가진 작업
이것을 보면 알 수 있듯 Q2에 최고 우선 순위로 진입 후 해닥 작업을 10동안 한다. 이렇게 타임 슬라이스가 끝나면 Q1으로 이동해서 또 타임 슬라이스가 끝날 때 까지 Q1에서 실행한다. 끝나고 나면 가장 낮은 Q0로 이동하여 계속 머무르게 된다.
예시 2: 짧은 작업과 함께
A는 오래 실행된 CPU 작업이고 B는 짧은 대화형 작업이다. 이 경우에는 SJF와 같이 동작하게 된다. 짧은 B를 Q2, Q1에서 두 번의 타임 슬라이스동안 실행되고 바닥의 큐에 도착하기 전에 종료하고 A를 다시 실행한다. 여기서 알 수 있는 것은 일단 짧은 작업이라고 가정을 해 높은 우선 순위를 부여하였다는 것이다. 만약 진짜 짧은 작업이면 빨리 실행되고 종료되고 아니라면 천천히 아래 큐로 이동하게 되어 스스로 긴 작업인 것을 알려주게 된다. 이렇게 MLFQ는 SJF를 근사한다.
예시 3: 입출력 작업은 어떻게?
프로세스가 타임 슬라이스르 소진하기 전에 프로세서를 양도하면 우선순위를 유지한다고 하였다. 사용자 입력을 대기하며 입출력을 수행하면 타임 슬라이스가 종료되기 전에 CPU를 양도하여 우선순위를 유지한다. B(회색)은 대화형 작업으로 입출력을 수행하기 전 1동안만 실행되고 A는 CPU를 사용하기 위해 B와 경쟁한다. B는 CPU를 계속 양도하여 우선 순위를 유지하게 된다.
문제점
지금 보면 CPU를 긴 작업들과 짧은 작업들 사이에 잘 공유하고 입출력 중점 짧은 대화형 작업을 빨리 실행시키고 있어서 잘 동작하는 것 처럼 보이지만 치명적인 결점이 있다.
- 기아 상태(starvation) 시스템에 너무 많은 대화형 작업이 있으면 긴 실행 시간의 작업은 CPU를 할당 받지 못해 굶어죽을 것이다.
- 스케줄러를 바꾸지 않는다 스케줄러를 속여 지정된 몫보다 더 많은 시간을 사용하게 할 수 있다. 하지만 스케줄러를 바꾸지 않기 때문에 속은 상태로 계속 실행되게 된다.
- 시간 흐름에 따라 특성이 변한다.
CPU 작업이 대화형으로 바뀌어도 같은 대우를 받을 수 없다.
◼︎ 시도 2: 우선순위의 상향 조정
기아 문제를 해결해 보려고 한다. 이것을 해결하는 간단한 방법은 주기적으로 모든 작업의 우선순위를 상향 조정(boost)하는 것이다. 간단하게 모두 최상위 큐로 보낼 것이다.
- 규칙 5: 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킬 것이다
이 규칙을 이용하면 두 가지 문제가 해결된다. 프로세스는 굶지 않고 CPU위주 작업이 대화형으로 바뀌면 우선 순위가 상향되었끼 때문에 적합한 스케줄링 방법이 적용되게 된다.
왼쪽은 우선순위 향상이 없을 때고 오른쪽은 있는 경우이다. 명도에 따라 A, B, C 작업이라고 할 것이다. A는 긴 작업이기 때문에 우선순위가 점점 낮아진다. 하지만 B와 C는 짧기 때문에 RR이 적용되어 우선순위가 유지된다.그래서 왼쪽의 경우 긴 작업은 100이후 굶게된다. 하지만 오른쪽의 경우 일정 시간마다 최상위 큐로 올려주기 때문에 굶지 않고 실행이 되는 것을 확인 할 수 있다.
이를 위해 S의 값을 결정해주어야한다. 이 값을 부두 상수(voo-doo constants)라고 하였다. S가 너무 크면 작업이 굶고 너무 작으면 대화형 작업이 적절한 양의 CPU시간을 사용할 수 없기 때문에 적절한 값을 찾기 힘들어 부두 상수라고 한다.
◼︎ 시도 3: 더 나은 시간 측정
해결하지 못한 문제가 있다. 바로 스케줄러가 자신에게 유리하게 동작하도록 속이는 상황이다. 규칙 4a와 4b때문에 이런 상황이 일어나게 된다. 이것의 해결책은 MLFQ의 각 단계에서 CPU 총 사용 시간을 측정하는 것이다. 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장하고 프로세스가 해당하는 시간을 모두 소진하면 다음 우선 순위 큐로 강등을 시키는 것이다. 그래서 규칙 4a와 4b를 합쳐 하나의 규칙으로 재정의 할 것이다.
- 규칙 4:주어진 단계에서 주어진 타임 슬라이스를 소진하면 우선순위를 낮춘다
왼쪽은 규칙 4가 적용되지 않았을 때이고 오른쪽은 적용됐을 때이다. 프로세스가 입출력 행동을 해도 아래 단계 큐로 천천히 이동해 CPU를 혼자 독점하지 않게 된다.
◼︎ MLFQ 조정과 다른 쟁점
MLFQ 스케줄링은 여러 다른 쟁점들을 불러오게 된다. 모든 것을 해결해주는 그런 방법은 없다. 계속해서 균형점을 찾아 조정해나아가야한다. 그러한 예시로 큐 별로 타임 슬라이스를 다르게 하는 방법이 있다. 우선 순위가 높은 큐는 짧은 타임 슬라이스를 주고 아래로 내려갈 수록 점점 늘어나게 된다.
◼︎ MLFQ: 요약
- 규칙 1: Priority(A) > Priority(B) 이면, A가 실행
- 규칙 2: Priority(A) = Priority(B) 이면, A와 B는 RR방식으로 실행
- 규칙 3: 작업이 시스템에 진입하면 맨 위의 큐(가장 높은 우선순위)에 놓인다
- 규칙 4:주어진 단계에서 주어진 타임 슬라이스를 소진하면 우선순위를 낮춘다
- 규칙 5: 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킬 것이다
◼︎ 비례 배분(Proprotianal share)
추가적으로 비례 배분(Proprotianal share)혹은 공정 배분(fair share)라고 불리는 스케줄러에 대해 알아볼 것이다. 반환 시간이나 응답 시간을 최적화하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적이다. 이 예시로 추첨 스케줄링(lottery scheduling)이 유명하다. 이름에서 알 수 있듯 다음 실행될 프로세스를 추첨을 통해 결정되는 것이다. 자주 수행될 프로세스는 당첨 기회를 많이준다.
◼︎ 기본 개념: 추첨권이 당신의 몫을 나타낸다
추첨권(티켓)이라는 개념이 스케줄링을 근간을 이룬다. 이는 프로세스가 받아야 할 자원의 몫과 같다.
A와 B 두 프로세스가 있을때 A는 75장의 추첨권을 가지고 B는 25개의 추첨권을 가지고 있다고 하면 A에게 75%의 CPU를, B에게는 25%의 CPU를 할당하는게 목적이다. 추천 스케줄링은 타임 슬라이스가 끝날 때 마다 추첨권을 선택하게 된다. 추첨권은 0~99의 숫자이고 A는 0~74의 티켓을, B는 75~99의 티켓을 가지고 있다. 어떤 티켓을 뽑았냐에 따라 어떤 프로세스를 실행할지 결정되는 것이다. 위의 사진은 그 예시이다. 그런데 여기에서 확인할 수 있듯 20개의 타임 슬라이드 중 B는 4개라서 목표였던 25%가 아닌 20%를 할당받았다. 하지만 이 작업이 정말 많이 이루어졌을 때는 원하는 비율에 수렴하게 된다.
◼︎ 추첨 기법
- 추첨권 화폐(ticket currency): 자신의 화폐 가치로 추첨권을 자유롭게 할당
A는 500장의 지역 티켓이 50개의 전역 티켓에 대응되고 Bsms 10장의 지역 티켓이 100개의 전역 티켓에 대응된다.
- 추첨권 양도(ticket transfer): 추첨권을 일시적으로 다른 프로세스에 양도
- 추첨권 팽창(ticket inflation): 일시적으로 자신이 소유한 추첨권 수를 늘이거나 줄인다
◼︎ 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// counter: 당첨자를 발견했는지 추적하는 데 사용됨
int counter = 0;
// winner: 0부터 총 추첨권의 수 사이의 임의의 값을 얻기 위해 난수 발생기를 호출함
int winner = getrandom(0, totaltickets);
// current: 작업 목록을 탐색하는 데 사용
node_t *current = head;
// 티켓 값 > winner를 만족할 때까지 반복
while (current)
{
counter = counter + current->tickets;
if (counter > winner)
break; // 당첨자 발견
current = current->next;
}
// "current" 는 당첨자를 가리킴: 당첨자가 실행될 수 있도록 준비
당첨 번호 winner를 랜덤으로 추출하고 만약 counter가 winner보다 커지면 당첨되며 루프가 종료되게 된다.
◼︎ 불공정 지표
우리의 목표는 두 작업을 거의 동시에 종료시키는 것이다. 그래서 이것을 보기위한 지표를 설정해둔다. 그것이 바로 불공정 지표이다.
- 불공정지표(U) = (첫 작업 종료시간) / (두번째 작업 종료 시간)
◼︎ 결정론적(Deterministic) 방법을 사용하지 않는 이유
무작위성을 이용하면 스케줄러는 간단히 만들지만 신뢰도가 떨어진다. 그래서 공정 배분 스케줄러인 보폭 스케줄링(stride scheduling)이 고안 되었다. 각 작업은 가지고 있는 추첨권 수에 반비례하는 보폭을 가지고 있다. A, B, C가 각각 100, 50, 250의 추첨권을 가지고 있다고 했을 떄 10,000개의 전체 추첨권 개수가 있다고하면 A, B, C는 순서대로 100, 200, 40의 보폭을 가지게 된다. 그리고 프로세스가 실행될 때마다 pass라는 값을 보폭만큼씩 증가시킨다.
