📃 CPU 스케줄링 알고리즘

CPU 스케줄링

• 운영체제가 CPU를 사용하기 위해 프로세스들 사이의 우선순위를 관리하는 작업이다.
• 프로세스들에게 자원을 공평하게 배분하여 처리율과 CPU 이용률을 증가시키고 오버헤드, 응답시간, 대기시간을 최소화 하기 위한 기법이다.

---

비선점형 스케줄링

• 비선점형 스케줄링은 실행 중인 프로세스가 자발적으로 종료하거나 블록이 될 때 까지 계속 실행된다. 즉, 다른 프로세스에 의해 영향을 받는게 아닌 실행 중인 프로세스 자체의 동작이나 외부 요인에 의해 발생하는 것들이다.

• 모든 프로세스에 대한 요구를 공정하게 처리할 수 있지만, 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기해야 할 수 있다. 그래서 처리시간 편차가 적은 특정 프로세스 환경에 용이하다.

---

비선점형 스케줄링 알고리즘

선입선출 스케줄링(FCFS : First Come Fist Served)

• 단순히 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식이다.
• 공정한 방식이지만 오래 사용하는 프로세스가 먼저 처리되는 경우 다른 프로세스는 그 프로세스가 CPU를 사용하는 동안 기다리는 수 밖에 없다.(호위 효과)

최단 작업 우선 스케줄링(SJF : Shortest Job First)

• 준비 큐에 삽입된 프로세스들 중 CPU 이용 기간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식이다.
• 최단 작업 우선 스케줄링은 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수 있다. (최소 잔여 시간 우선 스케줄링)

우선 순위 스케줄링(Priority Scheduling)

• 우선순위 스케줄링은 프로세스들에 우선 순위를 부여하고 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다. 우선순위가 같은 프로세스들은 선입 선처리로 처리한다.
• 하지만 우선 순위 스케줄링은 기아 현상이 발생한다. 높은 우선순위를 처리하는 방식이기 때문에 준비 큐에 먼저 삽입이 되어있더라도 우선순위가 낮은 프로세스는 계속 연기될 수 있다.
• 이를 해결하기 위한 방법은 에이징이다.

---

선점형 스케줄링

• 선점형 스케줄링은 실행 중인 프로세스가 다른 프로세스에 의해 중단될 수 있는 것이다.
• 비교적 응답이 빠르지만, 처리 시간을 예측하기 어렵고 우선순위 프로세스들이 계속 들어오면 오버헤드를 초래한다. 그래서 실시간 응답환경, DeadLine 응답환경 등 우선순위가 높은 프로세스를 빠르게 처리할 때 유용하다.

---

선점형 스케줄링 알고리즘

라운드 로빈 스케줄링(Round Robin)

• 라운드 로빈 스케줄링은 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링이다.
• 만약 정해진 시간이 끝났는데 해당 프로세스를 완료하지 못했다면 큐의 맨 뒤에 삽입된다. 이때 문맥 교환이 발생한다.

타임슬라이스
타임 슬라이스란 각 프로세스 CPU를 사용할 수 있는 정해진 시간을 의미한다.
타임 슬라이스의 크기가 너무 크다면 사실상 선입 선처리 스케줄링과 다를게 없어 호위 효과가 생길 수 있고, 타임 슬라이스가 너무 작다면 문맥 교환에 발생하는 비용이 커 CPU는 프로세스를 처리하는 일보다 프로세스를 전환하는데 집중하게 된다. 그래서 타임 슬라이스의 크기는 중요하다.

최소 잔여 시간 우선 스케줄링(Shortest Remaining Time)

• 최단 작업 우선 스케줄링 알고리즘(SJF)과 라운드 로빈 알고리즘을 합친 스케줄링 방식이다.
• 작업 시간이 짧은 프로세스부터 처리하는 스케줄링 알고리즘과 정해진 타임 슬라이스만큼 돌아가며 CPU를 사용하는 선점형 스케줄링 알고리즘을 합친 것이다.
• 최소 잔여 시간 우선 스케줄링에서 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

다단계 큐 스케줄링(Multilevel Queue Scheduling)

• 다단계 큐 스케줄링은 우선순위 스케줄링의 발전된 형태이다. 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식이다.
• 여러 개의 준비 큐를 사용할 경우 프로세스 유형별로 구분하여 실행하는 것이 편리하다.
• 또한, 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다.

다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

• 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링의 발전된 형태이다.
• 다단계 큐 스케줄링에서는 프로세스들이 큐 사이를 이동할 수 없기 때문에 기아현상이 발생한다. 하지만 다단계 피드백 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 있어 기아현상을 방지할 수 있다.
• 그래서 어떤 프로세스의 CPU 이용 시간이 길면 낮은 우선순위 큐로 이동시키고, 어떤 프로세스가 낮은 우선순위 큐에서 오래 기다린다면 높은 우선순위 큐로 이동시킬 수 있는 알고리즘이다.
• 다단계 피드백 큐 스케줄링은 구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘이다.