[CS 전공지식 #11] 챕터3-4. CPU 스케줄링 알고리즘

 

목차

4. CPU 스케줄링 알고리즘

3.4.1 비선점형 방식

3.4.2 선점형 방식

 

챕터3. 운영체제

 

4. CPU 스케줄링 알고리즘

• CPU 스케줄러:
  • CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당
  • 프로그램이 실행될 때, CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정

 

3.4.1 비선점형 방식

• 프로세스가 스스로 CPU 소유권을 포기하는 방식
  • 강제로 프로세스 중지 x
  • → 컨텍스트 스위칭으로 인한 부하가 적음
• FCFS First Come, First Served:
  • 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘
  • 단점) 길게 수행되는 프로세스 → 준비 큐에서 오래 기다리는 현상 발생
• SJF Shortest Job First
  • 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘
  • 긴 시간을 가진 프로세스가 실행되지 않는 현상 starvation 발생
  • 평균 대기 시간 가장 짧음
  • 실제) 실행시간 알 수 없음 → 과거 실행시간 토대로 추측해 사용
• 우선순위
  • SJF의 starvation
  • → 오래된 작업일수록 우선순위를 높이는 방법

 

3.4.2 선점형 방식

• 현대 운영체제가 쓰는 방식
• 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단 → 강제로 다른 프로세스에 CPU 소유권 할당하는 방식
• 라운드 로빈 Round Robin
  • 현대 컴퓨터가 쓰는 스케줄링인 우선 순위 스케줄링의 일종
  • 각 프로세스는 동일한 할당 시간, 그 시간 안에 끝나지 않으면 → 준비 큐의 뒤로 가는 알고리즘
• SRF Shortest Remaining Time First
  • 중간에 더 짧은 작업이 들어오면 수행하던 프로세스 중지, 해당 프로세스 수행
• 다단계 큐
  • 우선순위에 따른 준비 큐를 여러 개 사용
  • 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘 적용
  • 큐 간의 프로세스 이동 불가
  • → 스케줄링 부담 적지만, 유연성도 떨어짐