scheduling schemes

머릿속에 잘 구조화해서 정리

• Scheduling criteria,컨셉 한 줄 요약, 풀 네임,preemption 여부, 어떤 시스템에 유리,
• 👍장점,🥲문제점-> 😆극복
• ⭐️MFQ⭐️

A.T 기준(fairness)

FCFS

순정 그 자체, R.Q에 들어오는대로 First-come-First-service

• A.T 기준, preemption X
• context switching ⬇️ rsc utilization⬆️
  - batch sys > interactive
  
• 🥲 convoy effct
  • 짱 큰 CPU 있으면 다른 프로세스들 다 기다리고 있어야
  • mean response time ⬆️

RR

FCFS + preemption

• A.T 기준, preemption O (time quantum O)
• context switching overhead ⬆️
  • interactive, timesharing에 굿
• time quantum - RR 성능 결정
  • system param
• very small time quantum 이면 -> process sharing 거의 1/n
  • 🥲 context switching overhead ⬆️⬆️

B.T 기준(효율)

SPN(=SJF)

짧은 것부터 후딱 후딱 shortest-process-next

• B.T 기준, preemption X

• 👍 W.T 최소화

• 👍 시스템에 있는 프로세스 수 최소화

  • R.Q 사이즈 ⬇️, 필요 space, 메모리 ⬇️
  • 스케줄링 부하 ⬇️

• 👍 fast to response to many proc

• 🥲 starvation : long B.T .. 계속 밀림

  • indefinite postponement(blocking)

• 🥲 B.T estimation?

  • 보통 exponential avg(기하 평균)
  • 직전 거에서 영향 더 많이 받음

SRTN

SPN + preemption 이라 남은 시간 기준!
shortest-remaining-time-next

• remaing B.T 기준, preemption X

• 🥲 B.T estimation 마찬가지

• 🥲 B.T tracing overhead

• 🥲 context switching overhead ⬆️

• Q. starvation 문제는 어떻게 됨??

HRRN

SPN + Aging concepts ( W.T 고려 -> long B.T에게도 기회를 !)
High Response ratio next

• Response ratio 높은 것 부터, preemption??(Q.)
• Aging
• Response ratio = (W.T + B.T)/ B.T = 1 + W.T / B.T
  • B.T ⬇️ -> priority ⬆️(SPN과 같음)
  • W.T ⬆️ -> priority ⬆️
• 🥲 B.T estimation 마찬가지

Priority 기준

priority scheduling

• priority 기준(tie breaking: FCFS), preemption 상관 x
• 🥲starvation: 우선 순위 낮은 애들

Ready Queue

MLQ

⭐️MFQ⭐️ 특징(5가지), mechanism, 변형

MLQ +  feedback을 통한 프로세스의 R.Q 이동

특징(5가지)

• Dynamic priority
• Preemptive scheduling
• short B.T 선호
  • B.T 예상 없이 SPN, SRTN, HRRN 효과
• I/O bound 선호
• improved adaptability

mechanism

1. 처음 생성 프로세스(created) RQ0
2. I/O로 sleep 했다가 wake up 한 건 RQ 우선순위 그대로
3. timerunout(preempted)된건 RQ 우선순위 하나 아래로
4. 가장 낮은 RQn은 갈데가 없어요. timerunout이어도 그대로

변형

1. 각 R.Q 마다 다른 time quantum

2. Aging : W.T 길어지면 PR⬆️

3. moveup the i/o bound process
   -> adpatable

10.13 정리 완 (사실 MLQ 안함)