5. CPU 스케줄링(CPU Scheduling)

프로세스의 특성 분류

I/O bound process

주로 입출력 작업에 많은 시간을 소비하는 프로세스. 예를 들어 파일 입출력, 네트워크 통신, 데이터베이스 접근 등의 작업이 해당한다.

• CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
• many short CPU bursts
• CPU 사용이 비교적 낮음 : IO작업이 주로 시간을 소비하므로 CPU 사용이 비교적 낮다
• 대기 상태가 많음 : 입출력 작업이 완료되기를 기다리는 대기상태가 발생할 수 있다
• 입출력 작업이 빈번하게 발생 : 파일 입출력, 네트워크 통신, 데이터베이스 접근 등의 작업이 빈번하게 발생할 수 있따
• 다중스레드를 활용하여 입출력 작업을 동시에 처리하는 경우가 많음 : 여러 개의 스레드를 사용하여 입출력 작업을 동시에 처리하는 경우가 많아, 병렬성을 활용하여 입출력 성능을 향상시킬 수 있다

CPU-bound process

주로 CPU 연산에 많은 시간을 소비하는 프로세스. 예를 들어 고성능 계산, 암호화, 압축 등의 작업이 해당한다

• 계산 위주의 job
• few very long CPU bursts
• CPU 사용이 높음 : 연산이 많이 필요한 작업이므로, CPU 사용이 높다
• 입출력 작업이 비교적 적음 : 주로 CPU 연산에 시간이 소비되기 때문에, 입출력 작업은 비교적 적게 발생할 수 있따
• 대기 상태가 적음 : 입출력 작업이 적기 때문에, 대기 상태가 적게 발생할 수 있다
• 단일 스레드 또는 몇 개의 스레드를 사용하는 경우가 많음 : CPU 연산이 주로 수행되기 때문에, 단일 스레드 또는 몇 개의 스레드를 사용하여 처리하는 경우가 많다

CPU Scheduler & Dispatcher

CPU Scheduler

CPU 스케줄러는 여러 프로세스 중에 어떤 프로세스에 CPU를 할당하여 실행할지를 결정하는 역할을 한다. 시스템의 자원인 CPU를 효율적으로 활용하기 위해 프로세스들을 스케줄링하여 실행 순서를 조절한다. 프로세스들의 우선순위, CPU 사용량, 대기 시간등을 고려하여 CPU 할당을 결정하며, 공정한 자원 분배와 시스템의 성능 향상을 위해 중요한 역할을 한다

• Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다

Dispatcher

디스패처(또는 스케줄러)는 CPU 스케줄러가 결정한 프로세스를 실제로 CPU에 할당하여 실행시키는 역할을 한다. CPU가 어떤 프로세스를 실행하고 있는 동안에도, 다른 프로세스들의 상태를 감시하고 CPU를 선점하여 실행을 중단하고 다른 프로세스를 실행시킬 수 있다. 디스패처는 이런 프로세스의 전환 작업(컨텍스트 스위치)을 수행하여 여러 프로세스가 공유하는 CPU를 효율적으로 관리한다.

• I/O에 요청하는 시스템 콜이나 Terminate의 스케줄링은 강제로 빼앗지 않고 자진 반납한다 (nonpreemptive) , 할당시간 만료로 타이머 인터럽트나 IO 완료 후 인터럽트 하는 스케줄링은 강제로 빼앗는다(preemptive)

CPU Scehduling Criteria (성능 척도)

시스템 입장과 사용자 입장은 음식점에서 사장과 손님의 입장으로 비유할 수 있다. 사장은 가게에 손님을 많이 받기를 원하고 손님은 음식을 빨리 받기를 원한다.

알고리즘에 대한 성능평가 기준 5가지

1) 시스템 입장에서의 성능 척도

• CPU 이용률(CPU Utilization)
  • 시간당 CPU를 사용한 시간의 비율
  • 프로세서를 실행상태로 항상 유지하여 유휴상태가 되지 않도록 한다. 가능하면 입출력(I/O) 중심의 작업보다 프로세서 중심의 작업을 실행해야한다.
• 처리율(Throughput)
  • 시간당 처리한 작업의 비율
  • 단위 시간당 완료되는 작업 수가 많도록 짧은 작업을 우선 처리하거나 인터럽트 없이 작업을 실행한다.

2) 사용자 입장에서의 성능 척도

• 반환시간 또는 소요시간(Turnaround Time)
  • CPU burst time(쓰고 나갈때까지의 시간, 누적되지 않음)
  • 작업이 시스템에 맡겨져서 메인 메모리에 들어가기까지의 시간, 준비 큐에 있는 시간, 실행시간, 입출력시간 등 작업 제출 후 완료되는 순간까지의 소요시간이 최소화되도록 일괄 처리 작업을 우선 처리한다.
• 대기시간(Waiting Time)
  • 프로세스가 대기열(Ready Queue)에 들어와 CPU를 할당받기까지 기다린 시간
  • 작업의 실행시간이나 입출력시간에는 실제적인 영향을 미치지 못하므로 준비 큐애서 기다리는 시간이 최소화되도록 사용자 수를 제한한다.
• 반응시간 또는 응답시간(Response Time)
  • 프로세스가 대기열에서 처음으로 CPU를 얻을때까지 걸린시간
  • 반응시간은 의뢰한 시간에서부터 반응이 시작되는 시간까지의 간격으로 대화형 시스템에서 중요한 사항이다. 따라서 대화식 작업을 우선 처리하고 일괄 처리 작업은 대화식 작업의 요구가 없을때까지 처리한다.

FCFS (First-Come, First-Served)

• 특징
  • 가장 간단한 스케줄링 알고리즘
  • 먼저 도착한 프로세스가 먼저 CPU를 할당받는다
• 장점
  • 구현이 간단하고 공정한 방식으로 프로세스들을 스케줄링한다
• 단점
  • 프로세스의 실행 시간에 상관없이 먼저 도착한 프로세스가 CPU를 점유
  • 실행 시간이 긴 프로세스가 먼저 도착하면 뒤에 있는 짧은 실행 시간을 가진 프로세스들이 오래 기다리게 되는 “기아”현상이 발생할 수 있다

SJF (Shortest Job First)

• 특징
  • 실행 시간이 가장 짧은 프로세스를 우선으로 실행하는 스케줄링 알고리즘
  • 실행 시간이 짧은 프로세스를 먼저 처리한다. 비선점형(SJF)과 선점형(SRTF) 방식이 있다
• 장점
  • 최소 평균 대기 시간 보장
  • 프로세스의 실행 시간을 예측하기 어렵거나 예측이 불가능한 경우에도 상대적으로 좋은 성능 발휘
• 단점
  • 실행 시간이 짧은 프로세스에게 우선적으로 CPU를 할당하므로, 실행 시간이 긴 프로세스가 기아현상에 빠질 수 있다
  • 실행 시간을 정확하게 예측하지 않으면 잘못된 프로세스를 선택하게 되어 오버헤드가 발생할 수 있다

SRTF 또는 SRF(Shortest Remaining Time First)

• 특징
  • SJF의 선점형 스케줄링 방식
  • 남은 프로세스의 burst time보다 더 짧은 process가 도착하면 CPU를 빼앗음
  • 프로세스가 새로 들어올때마다 갱신됨
• 장점
  • 프로세스의 실행 시간을 정확하게 예측할 필요가 없다
  • 평균 응답 시간이 최소화 된다
  • 기아현상이 발생하지 않는다
• 단점
  • 새로운 프로세스가 들어올때마다 스케줄링이 변경되므로 CPU 사용 시간(burst time)을 정확히 예측하기 어렵다.
  • 프로세스의 실행 시간을 계속 모니터링하고 비교해야해서 CPU 오버헤드가 크게 발생할 수 있다
  • 실행 시간이 긴 프로세스가 계속해서 짧은 프로세스에게 밀려 컨텍스트 스위칭이 빈번하게 발생할 수 있어 CPU 이용률이 저하될 수 있다

Priority Scheduling

• 특징
  • highest priority를 가진 프로세스에게 CPU를 할당👉🏻 highest priority = smallest inteager
  • 선점형 방식에서는 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스보다 높으면 CPU를 선점한다.
  • 비선점형 방식에서는 더 높은 우선순위의 프로세스가 들어오면 Ready queue의 head 부분에 넣는다.
• 단점
  • Starvation (기아현상)
  • 무한 정지(infinite blocking) : 프로세스가 CPU를 사용할 준비가 되었지만 우선순위가 낮을 경우 무한 대기하는 상태가 되는 것 → Aging 기법으로 큐에 남아있었던 시간으로 가중치를 부여해, 해당 문제점을 해결할 수 있다.

Round Robin (RR)

• 특징
  • 각 프로세스에게 일정한 시간 할당량인 타임 슬라이스를 부여하고, 각 프로세스는 할당된 시간 동안 CPU를 사용한 뒤 다음 프로세스로 CPU를 넘긴 후 Ready queue의 맨 뒤로 가게 된다
• 장점
  • 모든 프로세스에게 CPU 사용 시간이 공평하게 할당되므로 “기아”현상이 발생하지 않는다.
  • 응답 시간이 짧아 사용자의 대화형 시스템에서 유용함.
  • 타임 슬라이스의 크기를 조절하여 우선 순위를 조절할 수 있다
• 단점
  • 프로세스의 실행 시간이 타임 슬라이스보다 긴 경우, 프로세스가 여러번의 타임 슬라이스를 사용하게 되면 컨텍스트 스위칭 오버헤드가 증가함.
  • 타임 슬라이스의 크기를 너무 작게 설정하면 컨텍스트 스위칭이 빈번하게 발생하여 CPU 오버헤드가 증가 할 수 있다

MLQ (Multi Level Queue)

• 특징
  • 우선순위마다 준비 큐 형성
  • 항상 가장 높은 우선순위 큐의 프로세스에 CPU를 할당 (우선 순위가 낮은 큐에서 작업 실행중이더라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗는 선점형 스케줄링)
  • 각 큐는 라운드 로빈이나 FCFS 등 독자적 스케줄링 사용 가능
  • 대화형, 배치(background)등의 프로세스 성격에 따라 우선순위 부여
• 단점
  • 큐들 간의 프로세스 이동이 불가하기 때문에 스케줄링 부담이 적지만 유연성이 떨어짐
  • 우선 순위가 낮은 프로세스가 오랫동안 CPU 할당을 기다리는 기아 현상이 발생할 수 있음

MLFQ (Multi Level Feedback Queue)

• 특징
  • 다단계 큐 + 동적인 프로세스 우선 순위 변화 적용
  • 프로세스 생성 시 가장 높은 우선 순위 준비 큐에 등록되며 등록된 프로세스는 FCFS 순서로 CPU를 할당받아 실행된다. 해당 큐의 CPU시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어간다
  • 단계가 내려갈수록 시간 할당량이 증가함
  • 큐 사이에 프로세스 이동이 가능하며 CPU burst는 낮은 우선순위의 큐, I/O Burst는 높은 우선순위의 큐에 배치한다
  • 다단계 큐 스케줄링 (MLQ) 알고리즘에서 프로세스는 시스템 진입 시 큐에 영구적으로 할당되며 프로세스는 큐 사이를 이동할 수 없었다
  • 맨 아래 큐에서 너무 오래 대기하면 다시 상위 큐로 이동한다 (에이징 기법을 통한 기아상태 예방)
  • 가장 하위 큐는 FCFS 스케줄링
  • 프로세스가 대기열에 영구적으로 할당되기 때문에 이 설정은 일정 오버헤드가 낮다는 이점이 있다.
  • 그러나 반면에 융통성이 없다는 단점이 있다.
• 장점
  • 더 유연하다
  • 서로 다른 프로세스가 서로 다른 대기열 사이를 이동 할 수 있다
• 단점
  • CPU 오버헤드를 생성한다
  • 가장 복잡한 알고리즘이다

MLQ와 MLFQ의 차이점이 뭘까?

1. 작업의 스케줄링 방식

• MLQ : 각 큐마다 미리 정의된 우선순위에 따라 작업을 스케줄링하고, 우선 순위가 높은 큐의 작업이 먼저 실행된다.
• MLFQ : 작업의 동적인 특성에 따라 큐를 이동하면서 작업을 스케줄링한다. 작업의 우선순위가 낮은 큐에서 높은 큐로 이동하여 더 높은 우선순위로 실행될 수 있다

2. 큐 간의 작업 이동

• MLQ : 큐 간의 작업 이동이 없이 각 큐가 독립적으로 작업을 실행한다
• MLFQ : 작업의 특성에 따라 큐 간의 이동이 가능하며, 작업들의 우선순위가 동적으로 조절된다

3. 자원 활용률

• MLQ : 작업들이 각자의 큐에서 독립적으로 실행. 전체 시스템의 자원 활용률이 떨어질 수 있다
• MLFQ : 작업들의 우선순위를 동적으로 조절하여 자원 활용률을 높일 수 있다

4. 스케줄링 알고리즘의 다양성

• MLQ : 각 큐마다 다른 스케줄링 알고리즘 사용
• MLFQ : 큐 간의 이동을 통해 작업들의 우선순위를 조절. 큐 내에서 다양한 스케줄링 알고리즘이 사용될 수 있다

5. 복잡성

• MLQ : 큐 간의 작업 이동이 없어 상대적으로 간단한 구현이 가능
• MLFQ : 큐 간의 작업 이동이 많아질 수 록 시스템 복잡성 증가