Scheduling 알고리즘

CPU 스케줄링 알고리즘에는 대표적으로 7가지 방식이 존재한다.

• 알고리즘은 매우 다양하고, OS마다 사용하는 알고리즘도 다르다.

• 여기서는 OAN, CFS 등 다루지 않는 알고리즘도 있다.

스케줄링 알고리즘을 달달 외울 필요는 없다. 각 스케줄링 알고리즘에서 사용된 아이디어, 작동 방식, 장단점에 집중하는 것이 좋다.

1. 선입 선처리 스케줄링 (FCFS, First-Come First Served)

단순하게 준비 큐에 삽입된 순서대로 처리해주는 스케줄링이다.

• 비선점 스케줄링

• 먼저 CPU를 요청한 프로세스부터 CPU를 할당한다.

공정해 보이지만, 큰 부작용을 야기할 수 있다.

• 프로세스들이 CPU를 할당받기 위해 대기하는 시간이 매우 길어질 수 있다. (=호위 효과)

앞에서 실행시간이 긴 프로세스가 존재하면 뒤에 기다리고 있는 프로세스의 처리 시간이 늦어질 수 있다.

예를 들어 A, B, C 프로세스가 순차적으로 준비 큐에 있다고 가정하자. C가 실행되기 위해서는 앞의 A, B의 처리가 끝나야 한다. 즉, C가 처리되기 위해서는 A+B 시간 만큼 기다려야 한다.

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

FCFS 스케줄링에서 호위 효과를 방지 하려면?

단순하게 생각하면, CPU 사용시간이 긴 프로세스를 나중에 실행하고 사용시간이 짧은 프로세스를 먼저 실행하는 것이다.

이런식으로 SJF는 CPU 작업 시간이 짧은 프로세스부터 처리하는 방식이다.

• SJF는 선점/비선점 방식으로 모두 구현이 가능하다. 기본적으로는 비선점이다.

SJF는 기본적으로 비선점이다.

• CPU를 사용중인 프로세스가 있을 때, 작업이 더 짧은 프로세스가 큐에 삽입되어도, 기존 프로세스가 끝날 때까지 기다린다.

3. 라운드 로빈 스케줄링 (RR, Round Robin)

라운드 로빈은 “돌아가면서 무엇을 한다.”라는 것을 의미한다.

• RR은 FCFS 스케줄링에 타임 슬라이스라고 하는 개념이 더해진 개념이다.

• 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

즉, 정해진 시간만큼만 사용하는 선점형 스케줄링이다.

• 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되, 정해진 시간만큼만 사용한다.

• 정해진 시간을 모두 사용하고도 프로세스가 완전히 처리되지 못했다면 다시 큐의 맨 뒤에 삽입 한다.

  • 이 과정에서 컨텍스트 스위칭이 발생한다.

RR 스케줄링에서는 타임 슬라이스 크기의 적절한 설정이 매우 중요하다.

• 크기가 너무 크면, 선입 선처리(FCFS)와 거의 똑같아진다. (호의 효과 발생 가능)

• 너무 작으면, 빈번한 문맥 교환에서 발생하는 오버헤드 때문에 CPU의 부담이 커질 수 있다.

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

SRT 스케줄링은 SJF + RR이 합쳐진 스케줄링 방식이다.

• 기본적으로 선점형 방식이다.

• 즉, 정해진 시간만큼 CPU를 사용하되, 다음 작업은 CPU 사용시간이 가장 적은 프로세스를 선택하는 방식이다.

SRT는 선점형이기 때문에,

새로운 프로세스가 도착할 때마다 현재 실행 중인 프로세스의 남은 시간과 비교해서 더 짧은 프로세스가 있으면 즉시 선점하여 교체한다.

• 평균 대기 시간이 짧아질 수 있지만, 컨텍스트 스위칭이 많이 발생할 수 있다.

5. 우선순위 스케줄링 (Priority)

우선순위 스케줄링은 프로세스에 우선순위를 부여하고, 높은 순서부터 실행하는 방식이다.

• 우선순위가 같으면 선입 선처리로 스케줄링된다. (먼저 준비 큐에 들어간 프로세스부터)

• SJF, SRT은 넓은 의미에서 우선순위 스케줄링이라고 볼 수 있다.

  • SJF는 작업시간이 짧은 프로세스한테 높은 우선순위를 부여하고,

  • SRT는 남은 처리 시간이 가장 짧은 프로세스에 높은 우선순위를 부여하고, 즉시 CPU를 할당한다.

  • 두 방식 모두 긴 작업이 계속해서 짧은 작업에 밀리면 기아(Starvation) 현상이 발생할 수 있다.

우선순위 스케줄링은 근본적인 문제점을 내포한다. 바로 기아 현상이다.

“우선순위가 높은 프로세스 먼저 무조건 실행하겠다.”라는 스케줄링 방식이기 때문에 우선순위가 낮은 프로세스는 준비 큐에 먼저 삽입되었음에도 계속해서 실행이 지연될 수 있다.

• 기아 현상. 즉, 우선순위가 낮은 프로세스는 마지막까지 실행이 안될 수 있다. 라는 문제를 의미한다.

기아 현상을 해결하는 방법에는 대표적으로 에이징(aging)이라는 방식이 있다.

• 에이징은 나이를 먹게하는 효과라고 이해하면 된다.

• 오랫동안 대기한 프로세스의 우선순위를 점차 증가시키는 방식이다.

  • ex) 일정 이상 실행되지 않은 우선순위를 한 칸씩 높이기

6. 다단계 큐 스케줄링 (MLQ, MultiLevel Queue)

멀티레벨 큐 스케줄링은 우선순위 스케줄링의 발전된 형태라고 볼 수 있다.

• 우선순위 별로 여러 개의 준비 큐를 사용하는 방식이다. 즉, 큐를 여러 개 만든다.

큐 구조:

• 각 큐는 서로 다른 우선순위를 갖는다.

• 프로세스는 생성 시 특성에 따라 특정 큐에 영구 할당된다.

• 큐 간에는 이동이 불가능하다.

MLQ 스케줄링 규칙

1. 상위 우선순위 큐가 비어있을 때만 하위 큐를 실행한다.

2. 각 큐는 고정된 스케줄링 알고리즘을 사용할 수 있다.

3. 프로세스는 생성 시 특성에 따라 특정 큐에 영구 할당된다.

4. 큐 간에는 이동이 불가능하다. (고정된 우선순위)

장점: 예측 가능한 성능, 시스템 프로세스 우선 처리 가능

단점: 하위 큐 기아 현상(Starvation) 발생 가능성이 존재한다.

이렇게 큐를 여러 개 두면 장점이, 프로세스 유형별로 우선순위 구분이 쉬워진다.

• 어떤 큐에는 우선순위가 비교적 높아야 하는 I/O 집중 프로세스가 삽입될 수 있고,

• 어떤 큐에는 우선순위가 비교적 낮아도 괜찮은 CPU 집중 프로세스가 삽입 될 수 있다.

• 어떤 큐에는 타임슬라이스를 크게/작게 지정할 수 있다.

• 어떤 큐에는 FCFS를, 어떤 큐에는 RR을 이용할 수 있게 할 수 있다.

  • 큐별로 스케줄링을 달리 적용해 프로세스를 유형별로 처리하는 게 쉬워진다.

MLQ 문제:

• 기본적으로 프로세스가 큐 간 이동이 불가능하다.

• 우선순위가 낮은 프로세스는 계속해서 우선순위가 낮은 큐에 머무를 수밖에 없어서 기아 현상이 발생할 수 있다.

7. 다단계 피드백 큐 스케줄링 (MLFQ, MultiLevel Feedback Queue)

MLFQ는 MLQ의 기아 현상 문제를 해결하기 위해 발전된 형태의 스케줄링 방식이다.

• 큐 간 이동이 가능한, MLQ 스케줄링이라고 볼 수 있다.

MLFQ 스케줄링 규칙

1. 상위 우선순위 큐가 비어있을 때만 하위 큐를 실행한다.

2. 새 프로세스는 항상 최고 우선순위 큐에 삽입된다.

3. 타임 슬라이스 소진 시 한 단계 하위 큐로 강등

4. I/O 작업 완료 시 상위 큐로 승격 (대화형 프로세스 우대)

5. 하위 큐일수록 더 긴 타임 슬라이스를 할당

6. 기아 현상 방지를 위한 주기적인 승격(Aging)

장점:

• 공정성: 기아 현상 방지

• 적응성: 프로세스 특성에 맞는 동적 조정

• 응답성: 대화형 프로세스 우선 처리

단점:

• 복잡성: 구현이 복잡하고 변수들의 조정 필요

• 오버헤드: 우선순위 조정으로 인한 추가 연산의 오버헤드

• 예측 어려움: 동적으로 조정되는 특성으로 성능 예측 곤란

대화형 프로세스란 사용자와 컴퓨터가 실시간으로 상호작용하는 환경에서 실행되는 프로세스를 의미한다. 즉, 시스템이 빠르게 반응하여 결과를 즉시 출력하는 방식이 특징이다.

• 사용자 반응에 즉시 응답해야 하는 키보드, 마우스 같은 입력

• I/O bound 작업이 많다.

즉, CPU를 많이 사용해야 하는 프로세스일수록 우선순위가 자연스럽게 낮아진다.

• CPU 집중 프로세스는 CPU를 많이 사용한다. 그런 프로세스의 경우에는 처음에 높은 우선순위에 삽입 되더라도, 이후에 낮은 우선순위 큐로 이동한다.

• CPU를 적게 사용하는 I/O 집중 프로세스는 높은 우선순위 큐에서 실행이 끝나버릴 것이다.

• 이를 통해 CPU 집중 프로세스는 점차 우선순위가 낮아지고, I/O 집중 프로세스의 우선순위는 상대적으로 높아진다.

MLFQ에서도 에이징(Aging)을 적용해서 기아 현상을 예방할 수 있다.

CPU 집중 프로세스는 최종적으로 가장 낮은 우선순위 큐로 이동할 확률이 높은데, 결국 CPU를 할당 받지 못해서 실행 못할 가능성이 있다.

• 하위 큐에서 오래 대기한 프로세스를 주기적으로 우선순위를 높이면서 상위 큐로 승격시킨다.

• 이를 통해 모든 프로세스가 결국 CPU를 할당받을 수 있도록 보장한다.