10. 스케줄링 알고리즘

SJF 알고리즘

• SJF 는 optimal 한 방법이지만, 다음 CPU burst 길이를 알 방법이 없다
• 그래서 다음 CPU burst 길이를 예측을 해보자
• 이론적으론 최적이지만, 실제로 사용하는 알고리즘은 아님
• preemptive 할수도 있고 non-preemptive 할 수도 있다
  1. non-preemptive : 그래도 P0이 진행중이니 끝내고나서 P1을 진행하는것
  2. preemptive : P0의 남은 시간보다 P1의 시간이 적으니 P1을 먼저 진행하는것 ← 더 유리함
• ⇒ P0 이 진행중이고 5초 남았을 떄 P1 이 1초걸리는 일이라면,

next CPU burst 예측하는 방법

• 과거에 측정된 평균 길이로 판단할 수 있다
• 지수적 평균 : 과거로 평균길이로 잡는다고해서 정확한건 아니기 때문

SRTF 스케줄링

• 남아있는 시간이 더 짧은 걸 먼저 실행시키는 것 (선점형 SJF : preemptive SJF)
• SJF(비선점형) 랑 비교하면 더 효율적일수 있다

RR 스케줄링

• Round-Robin : preemptive FCFS with a time quantum (time slice)
• ⇒ 시간을 쪼개어서 그 시간만큼만 프로세스를 돌리는 것
• 타임퀀텀은 보통 10 ~ 100 밀리세컨드
• ready queue 는 서큘러 큐로 구현

만약 CPU burst가 time quantum보다 짧다면?

• time quantum 이 1sec 일때 P0이 0.5sec 이 걸린다면 프로세스는 CPU 를 자발적으로 빠져나온다.
• ⇒ voluntarily
• 반대로 CPU burst 가 더 길다면 타이머가 OS 에 interrupt 를 걸어준다

RR waiting time /

• 평균 waiting time 은 보통 길다
• RR 스케줄링 알고리즘은 preemptive 하다

RR 스케줄링 알고리즘의 time quantum

• time quantum 의 사이즈의 크기에 따라 성능이 달라진다
• quantum 이 작으면 작을 수록 context switches 가 많이 발생한다
• ⇒ 이때 dispatch latency 가 발생하는데 이는 적으면 적을수로 좋음

⇒ 너무 커도 안좋고, 너무 적어도 좋지 않다

Priority-base 스케줄링

• 각 프로세스의 우선순위를 주어서 실행시키는 스케줄링 알고리즘
• SJF 가 사실 priority-based 스케줄링과 같다
• Priority 스케줄링은 preemptive 하거나 non-preemptive 하다

Priority 스케줄링의 문제

• 기아 문제 (indefinite blocking) : ready 큐에 있는 프로세스가 우선순위가 낮아서 계속해서 기다림
• ⇒ 해결방법
  
  • aging : 오랜시간을 대기하고 있으면 우선순위를 높여준다

RR + Priority 스케줄링

• 우선 순위로 먼저 실행시킴
• 같은 우선순위에 있는 프로세스들은 rr 스케줄링으로 실행

Multi-Level Queue(MLQ) 스케줄링

• 분리된 ready queue에 n개의 priority를 부여하는 실행하는 것

• 따로주어서 우선순위가 높은것부터만 실행시켜도 문제가 될 수 있다

⇒ 퀀텀을 조금씩 늘려감

modern 운영체제

• 커널 스레드가 있기 때문에 CPU 스케줄링이 아닌 스레드 스케줄링을 한다
• 유저스레드는 스레드 라이브러리가 관리함

Real-Time 운영체제 스케줄링

• 실시간 운영체제 : 주어진 시간 내에 task 를 완료할 수 있어야함
• Soft Realtime : critical real-time process 가 있을 때 noncritical 프로세스보다 더 빨리 끝날 수 있도록 보장해주는 것
• ⇒ 엄청 빨리 끝나도 조금 놓쳐도 괜찮은 것 (예: 전화를 하다가 말이 중간에 끊겨도 큰 지장이 없는 것)
• Hard Realtime : 어떠한 task 가 반드시 deadline에 의해 실행되는 것 (Priority)