운영체제 : 아주 쉬운 세 가지 이야기(2판) #2

스케줄링

선입 선출(FIFO, FCFS)

선도착 선처리의 경우, 한 예로 A,B,C 의 처리시간이 100, 10, 10인 경우  CPU를 많이 필요로 하지 않는 프로세스들이,

오랫동안 기다려야 하는 현상이 생긴다.(convoy effect)

 

최단 작업 우선(Shortest Job First, SJF)

가장 짧은 실행 시간을 가진 작업을 먼저 실행시킨다.

하지만 이 경우에도, 도착시간이 다른경우, 즉 A가 10초 먼저 도착한 경우에 똑값이 convoy effect가 발생한다.

 

# 이 문제를 해결하기 위해서는 "작업은 실행 도중에 중단 될 수 있다." 라는 기능을 추가 해야한다. 

 

최소 잔여시간 우선(Shortest Time-to-Completion First, STCF)

SJF에 선점 기능을 추가한 스케줄러이다.

현재 실행중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행시간을 비교하여, 잔여 실행시간이 가장 작은 작업을 스케줄한다.

 

# 새로운 평가 기준: 응답시간

응답시간 : 작업이 도착하는 시점부터 처음 스케줄 될 때 까지의 시간

예를 들어, 3개의 작업이 동시에 도착한 경우, 세 번째 작업은 딱 한번 스케줄 되기 위해 먼저 실행된 두 작업이 끝날때 까지 기다려야 한다.

반환 시간 기준으로는 매우 훌륭하지만, 응답 시간과 상호작용 측면에서는 매우 나쁜 방법이다.

터미널에서, 다른 작업이 먼저 실행되었다는 이유로 시스템의 응답이 올때까지 10초 기다리는 것은 상상해 보자

 

라운드 로빈(Round-Robin, RR)

RR은 작업이 끝날때 까지 기다리지 않는다.

대신 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다.

이러한 이유로 RR은 때로 타임 슬라이싱이라고 불린다. (또는 스케줄링 퀀텀)

 

타임 슬라이스의 길이는 RR에게 매우 중요하다!

짧은 수록 - 응답시간 기준으로 좋은 성능을 보인다. 하지만 문맥 교환 비용이 전체 성능에 큰 영향을 미치게 된다.

* 문맥 교환 비용에는 레지스터를 저장/복원 뿐 아니라, CPU 캐시, TLB, 분기 예측 등 다양한 작업정보들이 저장되어 있다.

 

일반적으로 RR과 같은 공정한 정책, 즉 작은 시간 단위로 모든 프로세스에게 CPU 를 분배하는 정책은

반환 시간 평가기준에서는 성능이 나쁘다.

 

두 가지 유형의 스케줄러를 다시 정리하면

첫째 유형 : SJF, STCF 는 반환 시간 측면에서는 좋은 성능 / 응답 시간은 좋지 않음.

둘째 유형 : RR 은 응답 시간 측면에서는 좋은 성능 / 반환 시간은 좋지 않음.

또한 위의 유형들은 다음과 같은 비현실적인 가정을 하고 있다.

1) 작업은 입출력을 하지 않는다.

2) 각 작업의 실행 시간을 알고있다.

이제 이 가정을 완화 시킬 방식을 보자.

 

멀티 레벨 피드백 큐 (p.84)

MLFQ 는 미래를 예측하기 위해 과거의 경험을 활용하는 훌륭한 예이다!

멀티 레벨 피드백 큐 (MLFQ) 는 여러 개의 큐로 구성 되며 각각 다른 우선순위가 배정된다.

핵심은, 우선순위를 정하는 방식이다.

각 작업에 고정된 우선순위를 부여하는게 아니라, 작업 특성에 따라 동적으로 우선순위를 부여한다.

 

기본규칙

• 규칙 1 : Priority(A)  > Priority(B) 면, A가 실행된다.
• 규칙 2 : Priority(A) = Priority(A)  면, RR 방식으로 실행된다.
• 규칙 3 : 작업이 시스템에 진입하면, 가장 높은 우선순위를 같는다.
• 규칙 4a : 주어진 타임 슬라이스를 사용하면 우선순위는 낮아진다. (한 단계 아래 큐로 이동)
• 규칙 4b : 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

⋇ 짧은 작업

스케줄러는 일단 짧은 작업이라고 가정하고 높은 우선순위를 부여한다. 

진짜 짧은 작업이면 빨리 실행되고 바로 종료할 것이다.

짧은 작업이 아니라면, 천천히 아래 큐로 이동하게 되고 스스로 긴 배치형 작업이라는 것을 증명하게 된다.

⋇  입출력 작업

규칙 4b 에 의해 CPU 를 계속 해서 양도하기 때문에 같은 우선순위를 갖는다.

 

⋇ 단점

1)  기아 상태가 발생 할 수 있다.

시스템에 너무 많은 대화형 작업이 존재 하면 긴 배치형 작업은 CPU 를 할당 받지 못한다.

2)  사용자가 유리하게 동작하도록 프로그램을 작성 할 수 있다.

타임슬라이스의 99% 실행후 CPU 양도하게 하면 CPU를 거의 독점할 수 있다.

3)  특성 변경시 같은 대우를 받을 수 없다.

프로그램은 시간 흐름에 따라 CPU위주 작업에서 대화형 작업으로 바뀔수 있지만, 같은 대우를 받을 수 없다.

 

 

 

⋇ 보완 시도

우선순위의 상향 조정

주기적으로 모은 작업의 우선순위를 상향 조정(boost) 하는 것이다.

• 규칙 5 : 일정기간 S 가 지나면, 모든 작업을 최상위 큐로 이동시킨다.

이런 새 규칙으로 위의 1,3 단점 2가지를 모두 해결할 수 있다! 

 

더 나은 시간 측정 

아직 2의 단점이 남아있다.

해결책은 MLFQ의 각 단계에서 CPU 총 사용시간을 측정하는 것이다.

스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장한다.

그 후 시간 할당량을 소진하면 우선순위를 강등한다. (몇 번 양도했는지 상관 없이.)

따라서 새 규칙으로 재정의 한다.

• 규칙 1 : Priority(A)  > Priority(B) 면, A가 실행된다.
• 규칙 2 : Priority(A) = Priority(A)  면, RR 방식으로 실행된다.
• 규칙 3 : 작업이 시스템에 진입하면, 가장 높은 우선순위를 같는다.
• 규칙 4 : 주어진 단계에서 시간 할당량을 소진하면, 우선순위는 낮아진다.
• 규칙 5 : 일정기간 S 가 지나면, 모든 작업을 최상위 큐로 이동시킨다.