OS-week3 [Multi-level Feedback]

CH 8. Multi-level Feedback

"완벽한 지식없이 어떻게 스케쥴 할까?"

8.1 MLFQ: Basic Rules

- 목표

   ㄴ turnaround time 최적화

   ㄴ response time 최소화 (job 길이에 대한 사전 정보 없이)

- MLFQ는 구별되는 큐들을 가진다 각각의 큐들은 다른 우선순위 레벨을 가진다.

- 주어진 시간에 실행할 준비가 된 작업이 하나의 큐에 있다.

- Rround-robin scheduling 사용

- MLFQ의 두 가지 기본 규칙

  Rule 1: 만약 Priority(A) > Priority(B), A가 작동 

  Rule 2: 만약 Priority(A) = Priority(B), A&B가 RoundRobin에 따라 작동

- 즉, MLFQ는 우선순위를 어떻게 정하느냐에 따라 다름

- 한 job이 키보드 입력을 기다리는 동안 CPU를 포기하면 (MLFQ는 상호작용하는 프로세스가 작동하는 방식이므로) 우선 순위를 (높게) 유지한다.

- 만약 어떤 job이 집중적으로 오랜 시간 CPU를 사용하면 MLFQ는 이것의 우선 순위를 줄인다. 

- 이러한 방법으로, MLFQ는 프로세스들의 작동을 배우고 job의 역사를 사용해 이들의 미래 행동을 예측한다.

*

- I/O bound job : response time이 중요 -> priority 높여줘야 함

- CPU bound job : turnaround time이 중요

8.2 How to MLFQ change priority

- 우선 순위 조정 알고리즘

Rule 3: job이 시스템에 들어올 때, 가장 높은 우선 순위를 가진다.

Rule 4a: 만약 job이 작동하는 동안의 time slice를 다 써버리면 우선 순위가 낮아진다

Rule 4b: 만약 job이 time slice가 끝나기 전에 CPU를 포기하면 이것은 같은 우선 순위로 남는다.

- job이 많은 I/O를 하고 이것의 time slice가 완성되기 전에 CPU를 포기한다면 우선 순위는 그대로 유지된다

- CPU는 오랜 시간 동안 실행되는 작업 사이에서 공정하게 처리하고 I/O 중심의 상호적인 job들을 빠르게 실행한다.

- 문제점:

1. Starvation

    시스템에 상호적인 job들이 많으면 그들이 모든 CPU 시간을 소비해서 장시간 실행되는 job이 CPU 시간을 받지 못함.

2. Gaming the scheduler

    스케쥴러를 속여 자원의 공정한 분배보다 더 많은 것을 제공하도록 하는 것.

    time slice가 끝나기 전에 I/O 작업을 실행하여 CPU를 양도함. 이렇게하면 동일한 우선순위로 남아있게 되어 높은 CPU 시간 비율을        얻을 수 있다. (예를 들어, CPU를 양도하기 전에 99%의 time slice를 실행함으로써) CPU를 독점 할 수 있다.

3. 프로그램은 시간이 지남에 따라 행동을 바꿀 수 있다.

    CPU-bound process가 I/O bound process로 전환 될 수 있다.

    이렇게 바뀌어도 priority가 계속 (낮게) 유지되므로 많은 CPU를 할당 받을 수 없다

   

* 스케쥴링 정책은 시스템 보안의 중요한 부분을 구성한다.

8.3 The priority Boost ->starvation, change behavior을 해결함

- Rule 5: 어떤 S기간 후, 모든 job들을 시스템에서 최고 우선순위로 올린다.

- 위의 새 규칙은 두가지 문제를 해결한다.

1. 프로세스들이 starve하지 않는 것을 보장한다.  

       큐의 top에 있으면 CPU를 다른 우선 순위 job들과 RR 방식으로 공유하므로 궁극적으로 서비스를 받게 됨.

2. 만약 CPU bound job이 I/O bound job으로 바뀌면 스케쥴러는 이것의 우선순위를 올려줘 적절하게 다룬다.

8.4 Better Accounting -> gaming 해결

- CPU 사용량을 누적해서 기록한다

   그 할당량을 다 쓰면 우선 순위가 낮아진다     <- new Rule4

- ex) 

   time slice를 100ms 준다고 하면 이것을 80ms만 쓰고 CPU 포기하면

   다음에는 20ms 주고, 이 것을 다 쓰면 우선순위를 낮춤

8.5 Tuning MLFQ And Other Issues

- 우선 순위가 낮을수록 CPU time을 많이 할당해준다

- high-priority 큐들은 보통 time slice가 짧고, interactive job을 구성한다. 

- low-priority 큐들은 보통 CPU-bound가 긴 job들로 구성된다. 그러므로 긴 time slice가 잘 작동된다.

Summary : MLDQ rules

- Rule1. 우선순위가 높은 작업을 먼저 실행시킨다

- Rule2. 우선순위가 같으면 Round Robin을 통해 결정한다

- Rule3. 작업이 시스템에 들어올 때, 우선순위를 최고로 둔다.

- Rule4. 작업이 주어진 CPU 시간 할당량을 다 사용하면 우선순위를 낮춘다.

- Rule5. 일정 시간이 지나면 작업의 우선순위를 최고로 올린다.

출처: http://pages.cs.wisc.edu/~remzi/OSTEP/