[운영체제] 프로세서 스케줄링

본 자료는 인하대학교 정진만 교수님의 Operating System 강의 자료를 참고하여 제작되었습니다.

Terminologies

• Burst (time)

  • CPU Burst: CPU 실행 시간
  • I/O Burst: I/O 실행 시간

• CPU-I/O burst cycle

  • CPU 실행과 I/O wait 시간의 cycles

• Processor(CPU) bound

  • CPU를 자주 사용하는 시스템

• I/O bound

  • I/O를 자주 사용하는 시스템

Types of Processor Scheduling

• Long-term scheduling

  • 처음 초기화할 때 사용

• Medium-term scheduling

  • Multi-programming
  • 프로세서 일을 load-balancing

• Short-term scheduling

  • Processor switch

Scheduling Criteria

• System Oriented

  • Throughput: 단위 시간 당 수행한 일
  • Processor Utilization
  • Fairness

• User Oriented

  • Turnaround time: 일을 끝날 때까지 전체시간
  • Response time: CPU 응답 시간
  • Deadlines

Selection Function

다음에 수행할 프로세스를 선택하는 함수

• w: waiting time
• e: execution time
• s: total service time
• TAT(Turn-around time): w + s

Decision Mode

• Non-preemptive

  • 프로세스가 종료될 때까지 실행함

• Preemptive

  • 여러 스케줄러에 의해, 우선순위에 의해 선점 가능함

FIFO (First In, First Out)

Ready queue에서 기다린 시간이 가장 긴 프로세스를 선택한다.

• Selection Function: max[w]
• Decision Mode: Non-preemption

장/단점

• 심플함
• Long process일 때가 유리함.
• Processor-bound process일 때 유리함.
• Convoy effect: 하나의 느린 프로세스 때문에 뒤에 있는 다른 프로세스들이 기다림.

Shortest Process Next (SPN)

짧은 프로세스 먼저 수행한다.

• Selection Function: min[s]
• Decision Mode: Non-preemption

장/단점

• TAT가 개선됨
• Long process에서 starvation이 발생 가능
• Service time을 알기 어려움

Shortest Remaining Time (SRT)

Remaining time으로 선택을 한다.

• Selection Function: min[s-e]
• Decision Mode: Preemption

장/단점

• 평균 turnaround time이 좋다.
• response time이 좋다.
• Starvation이 발생할 수 있다.
• 오버헤드가 크다.
• 긴 작업에 불리하다.
• 남은 실행 시간 예측이 어렵다.

Highest Response Ratio Next (HRRN)

오래 기다린 프로세스일수록 우선순위를 점점 높여주자.

• Response Ratio: R = (w + s)/s
• Selection Function: max[(w+s)/s]
• Decision Mode: Non-preemptive

장/단점

• Service time을 예측하기 어렵다.
• 적당히 조절하면서 실행한다.

Round-Robin

일정 시간마다 돌아가면서 일을 하게 한다.

• Selection Function: constant
• Decision Mode: Preemption

장/단점

• 공정함(fairness)
• No starvation
• Response time이 좋음

Time slice 기준

1. The shorter time slice

• Response time이 좋아짐
• 스케줄 오버헤드가 증가
• SPN

2. The longer time slice

• Response time이 안좋아짐
• 스케줄 오버헤드가 감소
• FIFO

Virtual Round Robin (VRR)

기존 round-robin은 long process에 조금 더 유리했다.
왜냐? 항상 time-slice를 소진하기 때문이다.

기존에 I/O가 끝난 프로세스도 ready queue 맨 뒤로 보내졌는데,
이를 보조 큐(auxiliary queue)에 넣고 먼저 처리시킨다.

그러면 스케줄러는 먼저 auxiliary queue를 먼저 본다.

Muti-Level Feedback Queue

이것도 RR를 개선하기 위해 나왔다.
Dynamic scheduler라고 한다.

Time-slice를 다 안쓰면? short process
Time-slice를 다 쓰면 demotion 한다.

Short process를 우대한다.
시간에 따라 큐를 나눈다.
시간에 따라 promotion할 수도 있다.