24.03.03 운영체제, 백준

운영체제

6. 스케줄링 : 멀티 레벨 피드백 큐(MLFQ : Multi-Level Feedback Queue)

• 멀티 레벨 피드백 큐 스케줄러는 Compatible Time-Sharing System(CTSS)에 사용된다.
• MLFQ가 해결하려고 하는 기본적인 문제는 두 가지이다.
  • 첫째, 짧은 작업을 먼저 실행시켜 반환시간을 최적화 하고자 한다.
  • 둘째, 응답 시간을 최적화한다.

6.1 MLFQ : 기본 규칙

• MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선 순위(Priority level)가 배정된다. 실행준비가 된 프로세스는 이 중 하나의 큐에 존재한다. MLFQ는 실행할 프로세스를 결정하기 위하여 우선순위를 사용한다. 높은 우선 순위를 가진 작업이 선택된다.
• 큐에 둘 이상의 작업이 존재 할 수 있다. 이들은 모두 같은 우선순위를 가진다. 이 작업들 사이에서는 라운드 로빈(Round-Robin, RR) 스케줄링 알고리즘이 사용된다.
• MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식이다. MLFQ 각 작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다.
• MLFQ의 두 가지 기본 규칙은 다음과 같다.
  • 규칙1 : Priority(A) > Priority(B)이면, A가 실행된다.
  • 규칙2 : Priority(A) = Priority(B)이면, A와 B는 RR방식으로 실행된다.

6.2 시도1 : 우선 순위의 변경

• 규칙 3 : 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위 큐에 놓여진다.
• 규칙 4-a : 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
• 규칙 4-b : 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.
• 스케줄러는 작업이 짧은 작업인지 긴 작업인지 알 수 없기 떄문에 일단 짧은 작업이라고 가정하며 높은 우선순위를 부여한다. 진짜 짧은 작업이면 빨리 실행되고 바로 종료할 것이다. 짧은 작업이 아니라하면 천천히 아래 큐로 이동하게 되고 스스로 간 배치형 작업이라는 것을 증명하게 된다. 이러한 방식으로 MLFQ는 SJF를 근사할 수 있다.

현재 MLFQ의 문제점

• 첫째, 기아 상태(Stavation)가 발생할 수 있다.
• 둘째, 똑똑한 사용자라면 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성할 수 있다. 스케줄러를 자신에게 유리하게 동작하도록 하는것은 일반적으로 스케줄러를 속여서 지정된 몫보다 더 많은 시간을 할당하도록 만드는 것을 가리킨다.

6.3 시도2 : 우선 순위의 상향 조정

• 주기적으로 모든 작업의 우선순위를 상향 조정(boost)한다.
• 간단한 방법으로는 모두 최상위 큐로 보내는 것이다.
  • 규칙 5 : 일정시간 s가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

6.4 시도3 : 더 나은 시간 측정

• 스케줄러를 자신에게 유리하게 동작 시키는 것을 어떻게 막을 수 있는가?
  • 여기서의 해결책은 MLFQ의 각 단계에서 CPU 총 사용시간을 측정하는 것이다. 스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용시간을 저장한다. 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등된다. 타임슬라이스를 한번에 소진하든 짧게 여러번 소진하든 상관없다. 규칙 4a와 4b를 합쳐 하나의 규칙으로 재정의 한다.
  • 규칙 4 : 주어진 단계에서 시간 할당량을 소진하면(CPU를 몇 번 양도하였는지 상관없이), 우선순위는 낮아진다.

7. 스케줄링 : 비례 배분 (Proportional Share) 스케줄러, 공정 배분(fair share) 스케줄러

• 반환 시간이나 응답시간을 최적화 하는 대신 스케줄러가 각 작업에게 CPU의 일정 비율을 보장하는 것이 목적이다.
• 비례 배분 스케줄링의 좋은예로 추첨 스케줄링(lottery scheduling)이 있다. 기본 아이디어는 다음 실행될 프로세스를 추첨을 통해 결정하고 더 자주 수행되어야 할 프로세스는 당첨기회를 더 많이 주는 것이다.

7.1 기본 개념 : 추첨권이 당신의 지분이다.

• 추첨권(티켓)이라는 기본적인 개념이 추첨 스케줄링의 근간을 이룬다. 추첨권은 경품권의 개념과 유사하다.
• 추첨권은 특정 자원에 대한 프로세스에게(또는 사용자 또는 그 무엇이든) 할당될 몫(지분)을 나타낸다. 프로세스가 소유한 티켓 개수와 전체 티켓 간의 비율이 자신의 몫이다.

무작위성의 이용

• 추첨권 스케줄링의 큰 장점 중 하나는 무작위성이다.
• 무작위 방식은 전통적인 결정 방식에 비해 세 가지 장점이 있다.
  • 첫째, 무작위 추첨 방식은 전통적인 방식이 잘 해결하지 못하는 특이상황을 잘 대응한다.
  • 둘째, 무작위 추첨 방식은 매우 가볍다. 관리해야 할 상태정보가 거의 없기 때문이다.
  • 셋째, 무작위 추첨 방식은 매우 빠르다. 난수 발생 시간이 빠르기만 하면 결정 역시 빠르게 되고, 따라서 속도가 요구되는 많은 경우 사용될 수 있다.
• 무작위성은 원하는 비율을 정확히 보장하지는 않는다. 하지만, 두 작업이 장시간 실행될수록, 원하는 비율을 달성하는 가능성이 높아진다.

7.2 추첨 기법

추첨권 화폐(ticket currency)

• 사용자가 추첨권을 자신의 화폐가치로 자유롭게 할당할 수 있도록 허용한다. 시스템은 자동적으로 화폐가치를 변환한다.

추첨권 양도(ticket transfer)

• 양도를 통하여 프로세스는 일시적으로 추첨권을 다른 프로세스에게 넘겨줄 수 있다.

추첨권 팽창(ticket inflation)

• 프로세스는 일시적으로 자신이 추첨권의 수를 늘이거나 줄일 수 있다. 물론 서로 신뢰하지 않는 프로세스들이 상호경쟁하는 시나리오에서는 의미가 없다.

7.3 구현

• 추첨 스케줄링의 가장 큰 장점은 구현이 단순하다는 점이다. 필요한 것은 난수 발생기와 프로세스들의 집합을 표현하는 자료구조, 추첨권의 전체 개수 뿐이다.

7.4 리눅스 CFS (Completely Fair Scheduler)

• 현재 리눅스는 기존과는 다른 방식으로 공정 배분 스케줄링을 구현했다. 이 스케줄러의 장점은 효율성과 확장성이다. 효율성을 위해, CFS는 최적의 내부 설계와 자료구조 사용을 통해, 스케줄링 결정을 매우 신속히 수행한다.

기본연산

• 대부분의 기존 스케줄러들은 고정된 길이의 타임 슬라이스를 사용한다. CFS는 이 점에서 기존 스케줄러와 다르다. CFS는 모든 프로세스들에게 CPU를 공평하게 배분하는 것을 목표로 한다. virtual runtime(vruntime)이라는 간단한 counting 기반 테크닉을 사용한다.
• 프로세서가 실행되서, 스케줄러는 해당 프로세서의 vruntime값을 누적시킨다. 가장 기본적인 경우, 각 프로세스의 vruntime은 실제 시간과 같은 속도로 증가한다. 스케줄링시 CFS는 가장 낮은 vruntime을 가진 프로세스를 다음에 실행할 프로세스로 선택한다.
• CFS가 자주 실행되면, 각 프로세스가 작은 시간 간격으로 CPU를 사용하게 되어 공정성이 좋아진다. 하지만, 많은 문맥교환이 발생하여 전체 시스템 성능에 악영향을 미칠 수 있다. 드물게 CFS가 실행되면, 문맥교환 횟수가 감소하여 전체 시스템 성능은 향상되지만, 공정성은 악화된다.
• CFS는 주기적으로 발생하는 타이머 인터럽트에 근간하여 작동한다. 즉 CFS는 특정시간 간격으로만 스케줄링 결정을 내릴 수 있다. 타이머 인터럽트는 짧은 간격으로 발생하여, CFS는 현재 작업의 타임 슬라이스 소진 여부를 판단한다.

가중치(Niceness)

• CFS는 사용자나 관리자가 프로세스의 우선 순위를 조정하여 다른 프로세스들 보다 더 많은 CPU시간을 할당받게 할 수 있다. 티켓이 아닌 프로세스의 nice 레벨이라는 고전적 UNIX 메커니즘을 사용한다. nice는 0을 기본 값으로 갖고 -20부터 19까지 가능하다 nice가 양수 값이면 낮은 우선순위를 의미하고 음수 값이면 높은 우선순위를 의미한다. 너무 친절하면 관심을 많이 못 받는 것과 같은 이치이다.
• 이 가중치는 프로세스의 실질적인 타임 슬라이스를 계산하는데 사용된다. 프로세스 간의 우선순위 차이까지 고려한다.
• 가중치 표의 장점은 nice값의 차이가 유지되면, CPU의 배분 비율도 유지된다는 것이다.

Red-Black 트리의 활용

• CFS는 프로세스 관리에 red-black 트리를 사용함으로써 이 효율성 문제를 해결했다.

I/O 와 잠자는 프로세스 다루기

• 장기간 잠자고 있는 프로세스의 경우 작업이 깨어날 때, vruntime을 적절히 재설정한다. 이를 통해 CFS는 큰 오버헤드 없이 기아현상을 방지하다.

백준

10451 순열 사이클

#include <bits/stdc++.h>
using namespace std;
vector<int> adj(1001);
int visited[1001];

void dfs(int x)
{
    visited[x] = 1;
    if (!visited[adj[x]])
    {
        dfs(adj[x]);
    }
}
int main() 
{
    int test_case, node, max = 0, check;
    cin >> test_case;

    for (int i = 0; i < test_case; ++i)
    {
        cin >> node;
        memset(visited, 0, sizeof(visited));
        for (int j = 1; j <= node; ++j)
        {
            int tmp;
            cin >> tmp;
            adj[j] = tmp;
        }
        check = 0;        
        for (int j = 1; j <= node; ++j)
        {
            if (!visited[j])
            {
                dfs(j);
                ++check;
            }
        }
        cout << check << '\\n';
    }
}

• DFS를 사용해서 풀었다.
• 사이클을 구하는 문제.
• 순열 사이클을 알아보면 쉽게 풀 수 있다.