[CS / 운영체제] 3.4 CPU 스케줄링 알고리즘

 

 

안녕하세요! 개발감자입니다.

오늘은 CS의 운영체제 중에서도 3.4 CPU 스케줄링 알고리즘에 대해서 정리해보았습니다.

 

---

3.4 CPU 스케줄링 알고리즘

CPU 스케줄러 : CPU 스케줄링 알고리즘에 따라 해야 하는 일을 스레드 단위로 CPU에 할당함

이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하도록, 준비 큐에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 함.

3.4.1 비선점형 방식

• 프로세스가 스스로 CPU 소유권 포기
• 강제로 프로세스 중지 X → 컨텍스트 스위칭으로 인한 부하가 적음
• FCFS (First Come, First Served)
  • 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘
  • 단점 : convoy effect (길게 수행되는 프로세스로 인해 준비 큐에서 오래 기다림)
• SJF(Shortest Job First)
  • 실행시간이 가장 짧은 프로세르를 가장 먼저 처리하는 알고리즘
  • 단점 : 긴 시간을 가진 프로세스가 실행되지 않음
  • 실제 : 실행 시간을 예측할 수 없어 과거 실행 시간을 토대로 추측해 사용함
• 우선순위
  • 기존 SJF 스케줄링의 단점을 보완하기 위하여 오래된 작업 수록 우선순위를 높이는 알고리즘

3.4.2 선점형 방식

현재 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 중단 시킴 → 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식

• 라운드 로빈 (RR, Round Robin)
  • 우선순위 스케줄리의 일종
  • 현대 컴퓨터가 쓰는 스케줄링
  • 각 프로세스는 동일한 할다아 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘
  • 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰임
• SRF
  • SJF : 중간에 실행시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 다음 작업을 함
  • 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행함.
• 다단계 큐
  • 우선순위에 따른 준비 큐를 여러 개 사용
  • 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용
  • 스케줄링 부담이 적지만 유연성이 떨어짐

---

면접을 위한 CS 전공지식 노트 | 주홍철 - 교보문고

 

이 포스팅은 면접을 위한 CS 전공지식 노트를 기반으로 작성되었습니다.