[운영체제/OS] L18. CPU Scheduling (2)

Shortest-Remaing-Time (SRT)

: SRT는 SJF의 preemptive버전

Policy

• 가장 작은 다음 CPU burst를 가지는 프로세스를 고르고, 그 프로세스를 preemptive 하게 돌린다 ..
  • termination or block할 때 까지, 또는 →
  • 프로세스가 레디큐에 들어갈 때 까지(새로운 프로세스나 이전에 block된 프로세스)
• 이 시점에서 예상된 CPU burst 시간이 현재 CPU burst의 시간보다 작을 경우 실행할 다른 프로세스를 선택함

SRT Example

 

 

❓ Q. 수행도중 남은 잔여시간이 작은 프로세스에 CPU할당 , 실행하다가 멈추고 .. 이런건가 .. ?
→ ㅇㅇ 이론으로, 존재 실제로 존재한다면 오버헤드가 엄청날 것 …
Q. SRT에서 스케쥴러가 잔여시간 계산하고 프로세스 멈추기 전까지의 수행시간은 어떻게 잡는건지? 라운드 로빈처럼 타임퀀텀을 쓰는건가 ?
→  타임퀀텀 가지구 정한다.

SRT Evaluation

• Preemptive (레디 큐에 들어온 순서대로)
• Response time - good
  • provably optimal(최적임) - 주어진 프로세스 set의 평균 대기 시간을 최소화함
• Throughput - high
• Fairness - 긴 프로세스에게 패널티 있음
  • 긴 프로세스는 결과적으로 짧은 프로세스가 된다 ..
• Starvation - 긴 프로세스에서 가능
• Overhead - 높을거임 (CPU burst time 추정 및 기록)

---

Priority Sheduling

Policy :

• 각 프로세스의 우선순위 연결
  • 정책, 중요도, 돈을 기준으로 외부적으로 정의됨
  • 메모리 요구사항, 파일 요구사항, CPU요구 사항을 기준으로 내부적으로 정의됨
  • SJF는 우선순위 스케쥴링이며, 여기서 우선순위는 다음 CPU burst길이에 반비례한다.
• 모든 프로세스에 대해서 우선순위 정해놓고 각 다음 중 하나를 실행시킨다
  • preemptively or ,
  • non-preemptively

Evaluation

• Starvation - 우선순위가 낮은 프로세스에서 가능
  • aging프로세스를 통해 피할 수 있다 ! → 시스템에서 시간을 보낼 때 우선순위를 높임

---

참고 ) 이런 스케쥴링도 있다 !

Multilevel Queue Scheduling

Policy :

• 레디큐가 여러개 있는 것. 여러 준비 대기열을 사용하고 각 대기열에 다른 우선 순위를 연결
• occupied 큐에서 우선순위가 가장 높은 프로세스를 선택하고 다음 중 하나를 실행한다.
  • preemptively, or →
  • non-preemptively
  • ** priority 와 preemptive 서로 분리해서 생각하기 !
• 새로운 프로세스를 특정 대기열에 영구적으로 할당한다.
  • Foreground, Background
  • System, interactive, editing, computing
• 각각의 큐는 다른 스케쥴링 policy를 가질 수 있음
  • Ex. preemptive, using timer
    • 80% of CPU time to foreground(RR사용)
    • 20% of CPU time to background (FCFS사용)

Multilevel Feedback Queue Scheduling

Policy :

• 여러 준비 대기열을 사용하고 각 대기열에 다른 우선 순위 연결
• occupied 큐에서 우선순위가 가장 높은 프로세스를 선택하고 다음 중 하나를 실행
  • preemptively or
  • non-preemptively
• 각 프로세스를 높은 우선순위 대기열에서 시작, 각 CPU burst가 완료되면 낮은 우선순위 대기열로 이동
• aging - older 프로세스를 우선 순위가 높은 큐로 이동
• Feedback = 과거를 사용하여 미래 예측 → 과거 CPU를 많이 사용하지 않은 작업을 선호( SRT 와 유사 )

CPU Scheduling in UNIX using Multilevel Feedback Queue Scheduling

Policy :

• 각각 priority를 갖는 여러 대기열 :
  • 커널 프로세스 값이 음수 → I/O를 막 마치고 아직 사용자 모드로 돌아가지 않은 시스템 호출을 수행하는 프로세스 포함
  • 사용자 프로세스가 양수 값을 가짐
• 우선 순위가 가장 높은 occupied queue(점유 대기열)에서 프로세스를 선택하고 타이머(일반적으로 시간 슬라이스 약 100ms)를 사용하여 해당 프로세스 미리 실행
  • 각 대기열의 RR 스케쥴링 대기열 간 프로세스 이동
• 대기열 간 프로세스 이동
  • 시계 눈금 추적 (60/초)
  • 초당 한 번씩 우선 순위 값에 시계 눈금 추가
  • 또한 프로세스가 CPU 시간의 “fair share” 이상을 사용했는지 여부에 따라 우선 순위를 변경 (다른 프로세스와 비교)