[운영체제] CPU 스케줄링과 알고리즘

CPU 스케줄링

CPU 스케줄러는 CPU 스케줄링에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당함. 프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU를 줄 것인지 결정함. 이때 비선점형 알고리즘과 선점형 알고리즘으로 나뉘며 CPU를 할당함.

 

비선점형 방식

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않음. 따라서 context switching으로 인한 부하가 적음

 

• FCFS(First Come First Served)
  • 큐에 도착한 순서대로 CPU를 할당함
  • 실행 시간이 짧은게 뒤로 가면 평균 대기 시간이 길어짐
• SJF(Shorest Job First)
  • 수행시간이 제일 짧다고 판단되는 작업을 먼저 수행함
  • FCFS보다 평균 대기 시간 감소, 짧은 작업에 유리
  • 이때 긴 시간을 가진 프로세스가 실행되지 않는 starvation(기아현상) 이  일어날 수 있음
• 우선순위(HRN)
  • SJF스케줄링의 경우, 긴 시간을 가진 프로세스가 실행되지 않는 현상을 보완하여 우선순위를 계산함
  • 우선순위 = (대기시간 + 실행시간) / 실행시간

선점형 방식

현대 운영체제가 사용하는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU소유권을 할당하는 방식임

• 라운드 로빈(Round Robin)
  • FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 Time Quantum(실행 최소 단위 시간)만큼 CPU를 할당받음
  • 할당 받는 시간이 크면 FCFS와 같아지며, 작으면 문맥 교환이 잦아져서 오버헤드가 증가함
• 다단계 큐(Multilevel-Queue)
  • 우선순위에 따른 준비 큐를 여러개 사용하며, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용함.
  • 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만, 유연성이 떨어짐
• SRTF(Shortest Remaning Time First)
  • SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 작업을 모두 수행하고 그 다음 짧은 작업을 이어나감.
  • SRTF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘
• 우선순위(Priority Scheduling)
  • 정적/동적으로 우선순위를 부여하며 우선순위가 높은 순서대로 처리
  • 우선순위가 낮은 프로세스는 무한정 기다리는 Starvation 현상이 생길 수 있음

CPU 스케줄링 척도

• Reponse Time(반응 시간)
  • 스케줄링에 프로세스가 준비큐에 들어와 작업이 처음 실행되기까지 걸린 시간
• Turnaround Time
  • 실행 시간과 대기 시간을 모두 합한 시간으로 작업이 완료될 때까지 걸린 시간