[⚙️ OS] CPU 스케줄링

CPU 스케줄링

👉 어느 프로세스가 사용될 것인지 결정 

 

 

🔹 CPU 스케줄러

• Ready 상태의 프로세스 중에서 이번에 CPU에 줄 프로세스 선정

🔹 Dispatcher

• CPU 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘김 = context switching

🔹 고려사항

1. 누구한테 CPU를 줄 것인지
2. 중간에 CPU를 뺏어올 수 있게 할 것인지 또는 계속 쓰게 할 것인지

🔹 scheduling criteria 

• CPU utilization ➔ 최대한 사용
• Throughput 
• Turnaround Time (총 소요시간)
• Waiting Time
• Response time (CPU를 최초 얻을 때까지 걸린 시간)

 

 

스케줄링 알고리즘

🔹 nonpreemptive (비선점형)

🔹 preemptive (선점형)

 

🔸 FCFS (First Come First Served) 

• 비선점형
• 먼저 온 순서대로 처리 ➔ 효율적 X
• 앞에 어떤 프로세스가 오느냐에 따라 waiting time 결정됨
• convoy effect : short process behind long process

 

 

🔸 SJF (Shortest Job First) 

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
• 비선점형 or 선점형(더 짧은 것이 오면 걔한테 넘김)
• average waiting time 최소화
• CPU burst time이 긴 것은 starvation 발생
• CPU 사용 시간을 미리 알 수 없음 (예측 가능 방법 존재)

 

 

 

🔸 Priority Scheduling 

• 우선순위가 가장 높은 프로세스
• 비선점형 or 선점형
• starvation 👉 aging 으로 해결

 

 

🔸 Round Robin 

• 동일한 할당 시간 설정 & ready queue에서 대기
• 선점형
• response time 빠름
• 할당 시간이 짧으면 overhead of context switching
• 할당 시간이 길면 = FCFS

 

 

---

🔹 Multilevel Queue 

• ready queue를 여러 개로 분할
  • foreground = RR
  • background = FCFS
• Multilevel Feedback Queue 👉 CPU 사용시간을 짧게 주고 아래로 갈수록 길게 줌. 그 후에는 FCFS

🔹 Multi-Processor Scheduling 

• Load sharing : 일부 프로세서에 몰리지 않도록 부하를 적절히 공유
• Symmetric Multiprocessing : 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric Multiprocessing : 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름