CPU Scheduling 알고리즘

이번 포스팅은 CPU가 프로세스를 대상으로 어떤 방식으로 CPU를 할당할 것인지에 대한 포스팅입니다.

단순 필기목적으로 적은 글이라 후에 업데이트 예정입니다.

FIFO(First In First Out)

먼저 들어온 작업이 먼저 나간다는 뜻으로 큐 자료구조를 생각하면 편합니다.
먼저 온 프로세스가 종료되어야만 다른 프로세스가 실행됩니다.

하지만 프로세스의 실행 시간에 따라 성능 차이가 심하게 나는 단점이 있어 현재 운영체제에서 잘 안쓰입니다.

SJF(Shortest Job First)

FIFO에서 단점을 보고 뒤집어서 생각한 방식입니다.
실행 시간이 짧은 프로세스를 먼저 실행시키는 방식입니다.

이 방식은 크게 2가지의 문제점이 있습니다.

• 실행 시간이 긴 프로세스는 실행되지않거나 오랜 시간동안 기다려야합니다.
  • 실행 시간이 짧은 프로세스들이 계속 먼저 처리되어 긴 프로세스들은 CPU를 할당 받지 못하는 경우가 생깁니다.(혹은 굉장히 오랜시간 가다려야합니다.)
• 프로세스의 실행 시간을 예측하기란 불가능에 가깝습니다.
  • ex 사용자가 유튜브를 실행시키고 인터넷 쇼핑을 합니다. 하지만 인터넷 쇼핑 어플을 빨리 종료할수도있고 종료하지않고 볼 수 도있습니다.

이러한 한계를 가지고있어 사용되지 않는 알고리즘입니다.

RR(Round Robin)

프로세스들 사이에 우선순위를 두지않고 시간단위로 프로세스를 실행시키는 방식의 알고리즘입니다.(흔히 말하는 시분할 시스템)
시간 단위동한 실행하고 남은 프로세스는 대기큐의 마지막에 넣습니다.
오버헤드가 크다는 단점이 있지만 응답시간이 짧아지는 장점이 있습니다. 시간단위는 20ms ~ 100ms 사이입니다.

MLFQ(Multi Level Feedback Queue)

RR의 업그레이드 알고리즘입니다.
우선순위에 시간단위를 배분받은 따른 큐를 여러개 만듭니다.(우선순위가 낮을 수록 시간단위가 커집니다.)
CPU Bound Process와 I/O Bound Process를 구분하여 우선순위 큐에 넣습니다.
만약 시간단위를 초과하여 CPU를 뺏기는 프로세스가 있다면 우선순위가 낮은 큐를 배정받습니다. 만약 이래도 부족하다면 시간단위가 더 큰(우선순위가 낮은)큐에 배정받습니다.