[OS] Scheduling

스케줄링

: CPU를 누구에게 할당할 것인가

 

워크로드에 대한 가정

1. 모든 작업은 같은 시간 동안 실행된다.
2. 모든 작업은 동시에 도착한다.
3. 작업은 일단 시작하면 최종적으로 종료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용한다(즉, 입출력을 수행하지 않는다).
5. 각 작업의 실행 시간은 사전에 알려져 있다.

 

스케줄링 평가 항목

정책을 평가할 수 있는 기준

1. 반환 시간(turnaround time)
   • 반환 시간 = 작업이 완료된 시간 - 작업이 도착한 시간
   • 성능 측면에서의 평가 기준
2. 응답 시간(response time)
   • 응답 시간 = 작업이 처음 스케줄링되는 시간 - 작업이 도착한 시간

 

스케줄링 기법

비선점형 스케줄링

- 프로세스에게 이미 할당된 CPU를 강제로 빼앗을 수 없고, 그 프로세스의 사용이 끝난 후에 스케줄링해야 하는 방법
- 모든 프로세스들에 대한 요구를 공정히 처리한다.
- 응답 시간의 예측이 용이하다.
- 짧은 작업이 긴 작업을 기다리는 경우가 종종 발생한다.

1. FIFO(선입선출)
   • 선도착선처리
   • convoy effect: CPU를 많이 필요로 하지 않는 프로세스들이, CPU를 오랫동안 사용하는 프로세스가 끝나기를 기다리는 현상
2. STCF(최소 잔여시간 우선)
   • 현재 실행 중인 작업의 잔여 실행 시간과 새로운 작업의 잔여 실행 시간을 비교하여, 잔여 실행 시간이 가장 작업을 스케줄
   • ex) A: 0초 도착, CPU 100 사용 / B, C: 10초 도착, CPU 10 사용 A의 실행을 중지하고 B와 C를 끝날 때까지 실행 후 A를 다시 실행
   • 최적의 스케줄링
3. MLFQ(멀티 레벨 피드백 큐)
   •  목적
     • 반환 시간 최적화
       • SJF, STCF는 실행 시간을 미리 알아야하기 때문에 현실적으로 불가능
     • 응답 시간 최적화
       • RR은 응답 시간은 좋지만 반환 시간이 안좋음.
   • 기본 규칙
     1. 우선순위 A > B 이면, A가 실행된다(B는 실행되지 않는다).
     2. 우선순위 A = B이면, A와 B는 RR 방식으로 실행된다. => 공평함, 응답 시간 줄이는 효과
     3. 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다. =>  실행 시간을 미리 알 수 없어 구현 불가능한 SJF를 극복
     4. 작업이 지정된 단계에서 배정받은 시간을 소진하면(CPU를 포기한 횟수와 상관없이), 작업의 우선순위는 감소한다(즉, 한 단계 아래 큐로 이동). => short job이 우대되는 것이 무력화되는 것을 방지
        1. 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
        2. 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다. => 반환 시간 줄이는 효과
     5. 일정 주기 S가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킨다. => short job이 들어오면 CPU를 많이 써야하는 job이 불리해지는 것을 극복
        • Running → Blocked (I/O 요청): "Short Job"
        • Running → Ready (time out): "Long Job"
   • 문제점 및 해결
     1. 기아 상태(startvation): 짧은 실행 시간을 가진 작업들이 계속 실행되면 긴 실행 시간 작업은 CPU 시간을 할당받지 못하는 것 → 규칙 5. 우선순위 상향 조정(Boost)
        • S 값(부두 상수) 결정 필요
          • 부두 상수는 피하는 것이 좋음
          • Solaris MLFQ 구현
     2. 스케줄러를 자신에게 유리하게 동작하도록 프로그램을 다시 작성 → 규칙 4. 할당량(allotment) 사용

 

선점형 스케줄링

- CPU가 어떤 프로세스에 의해 점유 중일 때, 우선 순위가 높은 프로세스가 CPU를 차지할 수 있음
- 우선 순위가 높은 프로세스를 빠르게 처리해야할 경우 유용.
- 선점이 일어날 경우, 오버헤드가 발생하며 처리시간을 예측하기 힘듦.

1. SJF(최단 작업 우선)
   • 가장 짧은 실행 시간을 가진 작업을 먼저 실행
   • 모든 작업이 동시 도착 시, 반환시간 면에서 최적의 알고리즘 → 최적의 결과를 낸다.
   • 도착 시간이 다른 경우, convoy effect 다시 발생
   • 응답 시간이 좋지 않다.
2. RR(라운드 로빈)
   • 작업이 끝날 때까지 기다리지 않고 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환
   • time slice: 작업이 실행되는 일정 시간
   • 공평함
   • 응답 시간이 좋다.
   • 반환 시간이 좋지 않다.

 

스케줄링 정책 - 공평함

비례 배분(Proportional Share) 혹은 공정 배분(Fair Share)

1. 추첨 스케줄링(lottery scheduling)
   • 추첨을 통해 결정
   • 자주 수행되어야하는 프로세스에게 당첨 기회를 더 많이 준다.
   • 비결정론적 스케줄링
   • 추첨 기법
     1. 추첨권 화폐(ticket currency)
        • 사용자가 추첨권을 자신의 화폐 가치로 하여금 자유롭게 할당할 수 있도록 허용
     2. 추첨권 양도(ticket transfer)
        • 클라이언트/서버 환경에서 유용
        • 작업이 빨리 완료될 수 있도록 클라이언트가 서버에게 추첨권 전달하고 요청을 완수하면 서버는 추첨권을 다시 클라이언트에게 되돌려준다.
     3. 추첨권 팽창(ticket inflation)
        • Global currency에서 일시적으로 자신이 소유한 추첨권의 수를 늘이거나 줄일 수 있다.
        • 프로세스들이 서로 신뢰할 때 유용
   • 불공정 지표 - 평가 기준
     • 불공정 지표 U = 작업 1이 완료된 시간 / 작업 2가 완료된 시간
     • 두 작업의 실행 시간 R은 동일
     • R이 매우 길다면 두 작업이 끝나는 시간이 거의 비슷 ⇒ 두 작업이 번갈아가면서 실행돼 U는 1에 가까워진다.
   • 작업이 늘어나고 줄어드는 것에 대해 유연하게 반응
2. 보폭 스케줄링(stride scheduling)
   • 결정론적 공정 배분 스케줄러
   • 보폭
   • pass
   • 새로운 작업이 추가됐을 때 문제
     • 적당한 pass 값을 줘야 함.(부두 상수)
3. CFS(Completely Faire Scheduler) 완전 공정 스케줄러
   • vruntime ( == 보폭 스케줄링에서의 pass)
   • sched_latency
     • CPU를 프로세스들에게 공정하게 배분, 1/n
     • == 보폭 스케줄링에서의 보폭
   • 가중치(Niceness)
     • nice > 0: 낮은 우선순위, nice < 0: 높은 우선순위
     • time slice = 작업의 가중치 / 전체 가중치 * sched_latency
     • vruntime = vruntime + 0번째 가중치 / 작업의 가중치 * vruntime
   • Red-Black 트리
     • 작업의 삽입 및 삭제 시 O(logn)만큼 소요
   • I/O와 잠자는 프로세스
     • Running → Blocked → Ready (새로운 작업의 추가와 같음.)
     • vruntime을 적절히 재설정
       • 새로운 작업이 CPU를 독점해서 기아 상태 발생
       • 트리에서 찾을 수 있는 가장 작은 값으로 설정

 

---

※ 국민대학교 소프트웨어학부 황선태 교수님의 운영체제 교과목을 공부하며 정리한 내용입니다.