[CPU 스케줄링 #1] FCFS, SJF, STCF , RR , MLFQ

CPU 스케줄링이 필요한 이유

시스템에는 동시에 실행을 요청하는 여러 프로세스가 존재하므로 한정된 CPU 자원을 효율적·공정하게 분배하기 위해 프로세스의 실행 순서를 관리하는 CPU 스케줄링이 필요하다.

스케줄링 정책 평가 항목

• 워크로드 에 대한 가정
  • 일련의 프로세스들이 실행하는 상황을 워크로드(workload)라고 부름.
  • 정책 개발에 매우 중요한 부분
  • 워크로드를 잘 알수록 그에 맞게 정책을 정교하게 손질할 수 있음.
• 스케쥴링 평가 항목 
  • 반환 시간 : 작업이 완료된 시각 - 작업이 시스템에 도착한 시간으로 정의
  • 모든 작업은 동시에 도착한다고 workload에서 가정한다면 Tarrival 은 0 , turnaround = completion
  • 반환 시간은 성능 측면에서 평가 기준임. 다른 평가 기준으로는 정성(fairness) 이 있음.

선입 선출 ( First Come First Served, FCFS ) 스케줄링

• 단순하고 구현하기 쉬움
• 시스템에 3개의 작업 A, B, C가 거의 도착했다고 가정
• 이 작업들의 평균 반환 시간은 ?
  • (10 + 20 + 30 ) / 3 = 20
• FIFO 가 그렇게 좋은 스케쥴링이 아닌 이유

• 만약 A가 100초 , B와 C는 10초 동안 실행 된다면 ?
  • ( 100 + 110 + 120 ) / 3 = 110
  • 평균 반환 시간은 110초
• 이 문제점은 convoy effect 라고 칭해지며 짧은 시간 동안 자원을 사용할 프로세스들 (B, C) 이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상이 발생.

최단 작업 우선 ( Shortest Job First, SJF ) 스케줄링

• FCFS 의 문제점을 해결하기 위해 가장 짧은 실행 시간을 가진 작업을 먼저 실행

• 아까 전 예시에서 보였던 순서를 가장 짧은 실행 시간을 가진 작업으로 실행
• A, B, C를 실행 시킬 경우 평균 반환 시간은 ?
  • ( 10 + 20 + 120 ) / 3 = 50, 2배 이상 향상 됨
• 모든 작업이 동시에 도착한다면 SJF 가 최적의 스케쥴링 알고리즘
  • But 만약 모든 작업이 동시에 도착하는 것이 아니라 임의의 시간에도착할 수 있다고 가정하면 ?

• 이전 FCFS 와 똑같은 문제인 convoy 문제가 다시 발생한다.
• ( 100 + (110 - 10 ) + (120 - 10) ) / 3 = 103.33

 

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

• 선점형 최단 작업 우선( PSJF ) 라고도 불리는 스케쥴러
• 언제든 새로운 작업이 시스템에 들어오면, 남아있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 실행 시간을 가진 작업을 스케줄한다.

• A 를 선점하고 있다가 , B와 C가 10초가 지난 후 도착한다고 가정
• 평균 반환 시간은 ( (120-0) + (20-10) + (30-10)) / 3 ) = 50초
• 새로운 가정 하에 STCF가 최적의 스케줄러

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

• 작업의 길이를 미리 알고 있고, 작업이 오직 CPU만 사용하고, 평가 기준이 반환시간 하나라면 STCF 는 매우 훌륭한 정책이다.
• 그러나 시분할 컴퓨터의 등장이 모든 것을 바꿈
• 사용자는 터미널에서 작업하게 되어 시스템에게 상호작용을 원할히 하기 위한 성능을 요구하게 되었다.
• 응답시간 (Response Time) 이라는 새로운 평가 기준이 태어나게 됨
  
  
  

라운드 로빈 (Round-Robin, RR) 스케줄링

• 응답 시간 문제를 해결하기 위해 나온 스케줄링 알고리즘
• 작업이 끝날 때 까지 기다리지 않는다.
  • 대신 일정 시간 동안 실행(타임 슬라이스, time slice)한 후 실행 큐의 다음 작업으로 전환한다.
• RR은 타임 슬라이싱 이라고 불림.
  • 타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야 한다.
    • 타이머가 10msec 마다 인터럽트를 발생시킨다면 , 타임 슬라이스는 10, 20 등 10msec 의 배수가 될 수있다.
• RR 동작방식 이해 , A, B, C 가시스템에 동시에 도착하고 각각 5초간 실행된다고 가정한다.
  • SJF 스케줄러는 다른 작업을 실행하기 전에 각 작업을 종료할 때 까지 실행한다.
    • 평균 응답 시간 = (0 + 5 + 10 ) / 3 = 5
  • 1초의 타임 슬라이스를 가지는 RR은 작업을 빠르게 순환하ㅣ게 된다.
    • 평균 응답 시간 = (0 + 1 + 2 ) / 3 = 1
• 타임 슬라이스 가 짧을수록 응답 시간 기준으로 RR의 성능은 더 좋아진다.
  • 그러나 타임 슬라이스를 짧게 지정하면 문맥 교환 비용이 전체 성능에 큰 영향을 미치게 된다.
  • 시스템 설계자는 시스템이 최적의 상태로 동작할 수 있도록 타임 슬라이스의 길이를 결정해야 한다.
  • 타임 슬라이스와 문맥 교환 비용을 정책적으로 잘 결정해야한다.
• 반환 시간은 ?
  • A B C 각 작업은 5초간 실행되고 동시에 도착하며 RR은 1초의 타임 슬라이스를 가진다.
  • A는 13, B는 14, C는 15에 종료하고 ㅇ균 14의 반환 시간을 보인다. 매우안좋다.
  • 반환 시간이 유일한 측정 기준 인 경우 RR이 확실히 거의 최악이며 많은 경우 단순한 FIFO 보다도 성능이 좋지 않다.
• 일반적으로 RR과 같은 공정한 정책, 즉 작은 시간 단위로 모든 프로세스에게 CPU를 분배하는 정책은 반환 시간과 같은 평가 기준에서 성능이 나쁘다.

 

입출력 연산의 고려

• 입출력 작업을 요청한 경우, 스케줄러는 다음에 어떤 작업을 실행할 지를 결정해야한다.
• 현재 실행 중인 작업은 입출력이 완료될 때 까지 CPU를 사용하지 않기 때문이다.
• 입출력 요청 과 입출력 완료 시에 대한 스케줄링 의사 결정이 필요

• A 와 B의 작업이 50msec의 CPU 시간을 필요로하고, A는 입출력 요청을하고, B는 입출력 요청이 없다는 가정하에, STCF 스케줄러를 구축하려고 한다고 가정.
• 입출력을 고려하지 않고 작업을 하나씩 실행시키는 것은 비효율적
• 일반적인 접근 방법으로는 A의 작업이 10msec 로 독립적인 작업으로 다루는 것
  
  

• A가 10msec의 입출력 작업을 하는 동안 B를 실행시켜 CPU의 연산의 중첩이 가능하고, 시스템이 좀 더 효율적으로 활용됨
• But 이건 스케줄러가 각 작업의 실행 시간을 알고있다는 가정이다. (사실 범용 운영체제에서 작업의 길이에 대해서 알 수 있는 방법은 없다.)

멀티 레벨 피드백 큐 (Multi-level Feedback Queue, MLFQ )

• 반환 시간을 최적화 한다.
• 응답 시간을 최적화 한다.
• MLFQ 스케줄링의 핵심은 우선순위를 정하는 방식이다.
• MLFQ는 각 작업에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여한다.
• 예를 들어 어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보하면 MLFQ는 해당 작업의 우선순위를 높게 유지한다. 이러한 패턴은 대화형 프로세스가 나타내느 ㄴ패턴이다.
• 대신에 한 작업이 긴 시간 동안 CPU를 집중적으로 사용하면 MLFQ는 해당 작업의 우선순위를 낮춘다.
• MLFQ는 작업이 진행되는 동안 해당 작업의 정보를 얻고, 이 정보를 이용하여 미래 행동을 예측한다.

규칙 1. Priority(A) > Priority(B) 이면, A가 실행된다 (B는 실행되지 않는다).

규칙 2: Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다

규칙 3: 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다.

규칙 4a: 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.

규칙 4b: 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다.

 

 

예 1) 한 개의 긴 실행 시간을 가진 작업

 

• 세 개의 큐로 이루어진 스케줄러이다.
• 작업이 처음에 에 최고 우선 순위로 진입한다.
• 10 msec 타임 슬라이스가 하나 지나면 스케줄러는 작업의 우선순위를 한 단계 낮추어해당 작업을 Q1으로 이동시킨다.
• 다시 하나의 타임 슬라이스 동안 Q1에서 실행한 후 작업은 마침내 가장 낮은 우선순위를 가지게 되고 Q0로 이동한다.

 

예2) 짧은 작업과 함께

 

• 2개의 작업이 존재한다.
• A(검은색)는 오래 실행되는 CPU 위주의 작업이고, B(회색)는 짧은 대화형 작업이다.
• A는 얼마 동안 이미 실행해 온 상태이고, B는 이제 도착했다고 가정하자
• B는 실행 시간이 짧기 때문에 (단지 20ms) 두 번의 타임 슬라이스를 소모하면 B는 Q0에 도착하기 전에 종료한다. 그런 후에 A는 낮은 우선 순위에서 실행을 재개한다.
• 이 스케줄러는 작업이 짧은 작업인지 긴 작업인 지 알 수 없기 떄문에, 일단 짧은 작업이라고 가정하여 높은 우선순위를 부여한다.
  • 진짜 짧은 작업이면 빨리 실행되고 종료될 것이다.
  • 짧은 작업이 아니라면 천천히 아래 큐로 이동하고긴 배치형 작업이라는 것을 증명하게 된다.
  • 이러한 방식으로 MLFQ는 SJF를 근사할 수 있다.

 

예3) 입출력 작업에 대해서는 어떻게 ?

 

• 규칙 4b가 말하는 것 처럼, 프로세스가 타임 슬라이스를 소진하기 전에 프로세서를 양도하면 같은 우선순위를 유지하게 한다.
  • 키보드나 마우스로 부터 사용자 입력을 대기하며 자주 입출력을 수행하면 타임 슬라이스가 종료되기 전에 CPU를 양도하게 될 것이다. 그런 경우 동일한 우선순위를 유지하는 것이다.
• B(회색)는 대화형 작업으로서 입출력을 수행하기 전에 1msec 동안만 실행된다.
• A(검정색)는 긴 배치형 작업으로 B와 CPU를 사용하기 위하여 경쟁한다.
• B는 CPU를 계속해서 양도하기 때문에 MLFQ 방식은 B를 가장 높은 우선순위로 유지한다.
• B가 대화형 작업이라면 MLFQ는 대화형 작업을 빨리 실행시킨다는 목표에 더 근접하게 된다.

MLFQ의 문제점

1. 기아 상태(starvation)
   1. 너무 많은 대화형 작업이 존재하면 그들이 CPU 시간을 소모하게 될 것이고, 긴 실행 시간 작업은 CPU 시간을 할당받지 못할 것이다.
2. 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 작성
   1. 타임 슬라이스의 99%를 실행하고 입출력 요청을 내려 CPU를 양도하게 되면 CPU를 거의 독점
3. CPU 위주 작업이 대화형 작업으로 바뀔 수 있다.
   1. 사용자가 고의로 혹은 어쩌다 CPU를 길게 쓰는 작업을 짧게 쪼개서 마치 대화형 작업처럼 행동하도록 코드를 작성할 수 있다.

 

해결 법 1) 우선 순위의 상향 조정

• 일정 기간 S가 지나면, 시스템의 모든 작업의 우선순위를 상향 조정하는 것이다.
• 프로세스는 굶지 않는 다는 것을 보장받는다.
  • 최상위 큐에 존재하는 동 작은 다른 높은 우선순위 작들과 라운드 로빈 방식으로 CPU를 공유하게 되고 서비스를 받게 된다.
• CPU 위주의 작업이 대화형 작으로 특성이 변할 경우 우선순위 상향을 통해 스케줄러가 변경된 특성에 적합한 스케줄링 방법을 적용한다.
  • 왼쪽 그래프 : 실행 시간 작업은 두 개의 짧은 작업이 도착한 이후에는 굶게 된다.
  • 오른쪽 그래프 : 50 mesc 마다 우선순위 상향이 일어나 긴 실행 시간 작업도 꾸준히 진행 보장

해결법 2) 더 나은 시간 측정

• 스케줄러를 자신에게 유리하게 동작시키는 것을 어떻게 막을 수 있는가?
  • 이러한 일을 가능하게 만든 주범은 규칙 4a와 4b 이다
• MLFQ의 각 단계에서 CPU 총 사용 시간을 측정
• 스케줄러는 현재 단계에서 프로세스가 소진한 CPU 사용 시간을 저장한다.
• 프로세스가 타임 슬라이스에 해당하는 시간을 모두 소진하면 다음 우선순위 큐로 강등된다.

규칙 4: 주어진 단계에서 시간 할당량을 소진하면 (CPU 를 몇 번 양도하였는지 상관이), 우선순위는 낮아진다 (즉, 아래 단계의 큐로 이동한다).

MLFQ 조정과 다른 쟁점들

MLFQ 스케줄링에는 여러 다른 쟁점들이 남아 있다. 필요한 변수들을 스케줄러가 어떻게 설정해야 하는지도 중요한 문제다. 예를 들어, 몇 개의 큐가 존재해야 하는가? 큐당 타임 슬라이스의 크기는 얼마로 해야 하는가? 기아를 피하고 변화된 행동을 반영하기 위하여 얼마나 자주 우선순위가 상향 조정되어야 하는가? 이러한 질문들에 대해 쉽게 대답할 수 없다. 워크로드에 대해 충분히 경험하고 계속 조정해 나가면서 균형점을 찾아야 한다. 예를 들어, 대부분의 MLFQ 기법들은 큐 별로 타임 슬라이스를 변경할 수 있다. 우선순위가 높은 큐는 보통 짧은 타임 슬라이스가 주어진다. 이 큐는 대화형 작업으로 구성되고, 결국 이 작업들을 빠르게 교체하는 것은 의미가 있다. 낮은 우선순위는 반대로 CPU-중심의 오래 실행되는 작업들을 포함한다. 긴 타임 슬라이스 가 적합하다.

 

 

출처 : 운영체제 아주 쉬운 세가지 이야기