[운영체제] 9장: Uniprocessor Scheduling

Aim of Scheduling

• Response time: 빠른 응답 속도
• Throughput: 작업 효율성
• Processor efficiency: 유저 프로세서 작업 정도
• Fairness: 프로세스에 대한 공정성

• 4가지 조건을 동시에 만족하는 스케줄링 기법은 존재하지 않는다.
• 공정성을 만족시키면 response time이 느려질 수 밖에 없다.

Types of Scheduling

• Long-term Scheduling: 새로운 프로세스가 생성되었을 때
  • Ready queue VS Ready/Suspend queue
  • batch job을 위한 스케줄링
• Medium-term Scheduling: swapping 관련
  • 언제 어떤 프로세스를 하드 디스크로 버릴까?
  • 언제 어떤 프로세스를 메모리로 올릴까?
• Short-term Scheduling: Ready queue에 있는 프로세스 중 어떤 걸 다음에 실행할까?
  • User-oriented
    • 짧은 response time
    • 짧은 turnaround time: 실행 시작 ~ 종료
  • System-oriented
    • 효율적 프로세서 사용: OS 작업 최소화, 유저 프로세스 많이 실행
    • 많은 throughput: 단위 시간동안 많은 프로세스 실행 완료
  • Performance-related
    • response time, throughput 처럼 측정 가능한 양적 척도
  • Not performance-related
    • 예측 가능성, 공정성처럼 측정 불가능한 질적 척도

Priorities

• 스케줄러는 항상 높은 우선순위를 가진 프로세스를 선택한다.
• 우선순위 레벨에 따라 여러 개의 Ready queue를 가진다.
• 낮은 우선순위를 가진 프로세스는 starvation이 발생할 가능성이 있다.

Scheduling Algorithms

response time = 대기 시간 + 실행 시간

First-Come-First-Served

• Ready queue에 도착한 순서대로 프로세스가 실행된다.
• Non-Preemption: 한 번 프로세서를 잡으면 타임 아웃 등에 의한 이유로 중단되지 않고 계속 실행된다.
• 실행 시간이 짧은 프로세스가 실행하기까지 오래 기다려야할 수 있다.
• response time은 최악이지만 가장 공정하고 예측 가능성이 높다.

Round-Robin (Time Slicing)

• 타임 아웃 이용
• Preemption: 타임 아웃이 되면 다른 프로세스에게 프로세서가 넘어가고 실행되던 프로세스는 Ready queue에 들어간다.
• 타임 아웃 간격에 따라서 response time이 달라진다.
• 공정하고 예측 가능성이 높다.

Calculating Program 'BURST'

• Burst time: 프로세스의 실제 실행 시간
  1. Simple Average: 실행 시간의 산술 평균
     • S1 값은 임의로 설정된다.
  2. Exponential Averaging
     • $S_{n+1} = \alpha T_n + (1 - \alpha )S_n$

Burst time이 예측 가능하므로 SPN과 SRT의 구현이 가능하다.

• 실행 시간이 짧은 프로세스에게 우선 순위를 주는 이유
  • 실행 시간은 고정이므로 대기 시간을 줄여야 한다.
  • 대기 시간은 곧 다른 프로세스의 실행 시간이므로 실행 시간이 짧은 프로세스가 먼저 실행되어야 대기 시간을 줄일 수 있다.

Shortest Process Next

• Ready queue에 있는 프로세스 중에서 실행 시간이 가장 짧은 프로세스를 먼저 실행한다.
• Non-Preemption: 프로세스 실행 도중에 실행 시간이 더 짧은 프로세스가 큐에 도착해도 프로세서를 뺏기지 않는다.
• response time은 짧지만 공정하지 않고 예측 가능성이 감소한다.
• 실행 시간이 긴 프로세스는 starvation이 발생할 가능성이 있다.
• 프로세스의 실행 시간을 미리 알아야 하는 문제가 있다.

Shortest Remaining Time

• Preemption: 프로세스 실행 도중에 실행 시간이 더 짧은 프로세스가 큐에 도착하면 실행을 멈추고 프로세서를 넘겨준다.
• 전체 실행 시간이 아닌 남은 실행 시간과 비교하여 우선순위를 매긴다.
• 남은 실행 시간이 같다면 실행하고 있던 프로세스를 계속 실행한다.
• response time이 가장 짧은 기법이다.
• 공정하지 않고 starvation 발생 가능성이 있다.

Highest Response Ratio Next

• Ratio = 1 + (대기 시간 / 예상 실행 시간)
• Ratio가 높으면 높은 우선 순위를 가진다.
• Ratio가 높다는 것은 대기한 시간이 길거나 실행 시간이 짧다는 것을 의미한다.
• (FCFS, RR)의 장점인 공정성과, (SPN, SRT)의 장점인 실행 시간이 짧은 것 먼저 실행하기를 모두 가진 기법이다.
• 어떤 프로세스를 실행할 지 결정할 때마다 ratio를 새로 계산한다.
• Non-Preemption: Preemption으로 구현하면 ratio 계산이 너무 복잡하다.
• starvation 발생 가능성이 없다.

Feedback

실행 시간이 짧은 프로세스 먼저 실행하고는 싶은데 burst time 계산하기는 싫어!
→ Multi-level 큐를 사용한다.

• Preemption: 타임 아웃 사용
• 주어진 시간 만큼 실행하고 할 작업이 남았으면 낮은 레벨의 큐로 들어간다.
• 최하위 레벨 큐는 RR로 동작하고 나머지는 피드백 큐이다.
• 높은 레벨 큐에 있는 프로세스들을 우선적으로 실행한다.
• $q = 2^i$, 큐의 레벨이 낮아질수록 프로세스에게 할당되는 시간은 길어진다.
  • starvation을 방지하는 방법으로 공정하다.
• 큐에 대기 중인 프로세스가 없으면 타임 아웃에 걸려도 계속 실행한다.
• 실행 시간이 긴 프로세스들은 계속 하위 레벨의 큐로 내려가면서 우선순위가 낮아지므로 실행 시간이 짧은 프로세스들이 상대적으로 우선순위가 높아진다.

Fair-Share Scheduling

• 프로그램이 몇 개의 프로세스 혹은 thread로 구성되어 있든 간에 프로그램 별로 비슷한 시간을 할당 해주는 방식이다.
• 프로세스 집합에 기반하여 스케줄링을 한다.
• 공정성을 많이 고려한 방식이다.

Traditional UNIX Scheduling

• Multi-level feedback queue 사용
  • Preemption: 타임 아웃 사용
    • 실행 시간이 남았다고 해서 하위 레벨 큐로 내려가지 않는다.
  • 우선순위가 같은 프로세스들은 RR로 동작한다.
  • 프로세스 타입과 프로세서 사용 시간에 따라서 주기적으로 우선 순위를 새로 계산한다.
• Scheduling Formula

  $P_j(i) = Base_j + \frac{CPU_j(i)} 2 + nice_j, CPU_j(i) = \frac{CPU_j(i-1)}2$

  • $Base_j$: 기본 우선순위, 시스템 작업 프로세스 > 유저 프로세스
  • 주로 Base 값에 의해 작업 순서가 결정된다.
  • $nice_j$: 사용자가 지정할 수 있는 값으로, 우선순위를 낮추는 데에만 사용되고 높일 수 없다.
  • $CPU_j(i)$: 프로세스j의 i번째 타임의 CPU 값
  • $P_j(i)$ 값이 작을 수록 우선순위가 높다.
    • 프로세서를 거의 차지한 적 없는 프로세스가 높은 우선순위를 가진다. 공정하게!
  • starvation 발생 가능성이 없다.
  • 실행 시간이 짧은 프로세스에게 우선순위를 준다.