[OS] 스케줄링 (Scheduling)


floatFirstTOC: right

🖥️ 시작하며 🔍 CPU Scheduling?📌 스케줄링의 목표 📌 Starvation (기아)📌 Non-preemptive scheduling 📌 Preemptive scheduling 💡 CPU burst VS I/O burst 🔍 Process State Queue 📌 FCFS / FIFO (First-Come, First-Served)📌 SJF (Shortest Job First)📌 SRTF (Shortest Remaining Time First)📌 RR (Round Robin)💡 알고리즘 정리 🔍 Priority Scheduling 📌 Priority inversion problem 1️⃣ Priority inheritance protocol (PIP)2️⃣ Priority ceiling protocol (PCP)📌 Multi-Level Feedback Queue (MLFQ)💡 UNIX의 일반적 정책

🖥️ 시작하며

커널이 어떤 App에게 CPU를 할당할 것인가에 대한 스케줄링에 대해 알아봅니다.

🔍 CPU Scheduling?

💡

다음에 누구에게 코어를 줄 거냐? == 다음에 누구를 쉬게 할 거냐?

📌 스케줄링의 목표

모든 시스템에:

No starvation
Fairness: 공평해야 함
Balance: System Part가 골고루 바쁘도록, I/O 요청한 애한테 주면 안 됨

배치 시스템:

Throughput: 단위 시간당 하는 일
Turnaround time: 시작과 종료 사이의 시간 최소화
CPU utilization: CPU가 항상 바빠야 함

Interactive systems:

Response time: 반응이 빨라야 함

Real-time systems:

Meeting deadlines: 손실되는 데이터가 없어야 함
Predictability: 가능하면 예측 가능해야 함

📌 Starvation (기아)

💡

한 프로세스가 필요로 하는 자원을 다른 프로세스가 차지하고 있어 진행하지 못하는 상황

스케줄링 정책의 문제:

높은 우선순위 프로세스가 항상 CPU를 점유하여 낮은 우선순위 프로세스가 실행되지 못하는 경우 발생

동기화 문제:

특정 스레드가 항상 다른 스레드를 이겨 락을 획득하는 경우 발생

📌 Non-preemptive scheduling

💡

프로세스가 자발적으로 CPU를 양도할 때까지 대기

→ 적절한 시점에 CPU를 양도해야 함

📌 Preemptive scheduling

💡

스케줄러가 인터럽트를 유발해 강제로 context switch를 수행할 수 있음

→ 작업이 System call을 실행중이어도 가능, 동기화 문제 생길 수 있음

💡 CPU burst VS I/O burst

CPU를 많이 쓰는 프로세스와 I/O를 많이 쓰는 프로세스가 존재

대부분이 CPU를 조금 쓰는 프로세스

🔍 Process State Queue

Ready Queue에 존재하는 PCB를 꺼내는 순서로는 여러 방법이 존재한다.

📌 FCFS / FIFO (First-Come, First-Served)

💡

작업이 도착한 순서대로 스케줄링

특징

Non-preemptive: 비선점형, 자발적으로 양도하지 않는 한 실행이 끝난 후 반환
No Starvation

문제

평균적으로 대기시간이 길어짐
CPU를 잡고 I/O를 10초 호출하는 등 비효율적인 작업을 수행할 수 있음

📌 SJF (Shortest Job First)

💡

짧은 작업부터 먼저 스케줄링

특징

가장 짧은 작업부터 수행하므로 가장 짧은 평균 대기시간을 가짐
Non-preemptive

문제

누가 가장 짧게 사용하는지 어떻게 예측하나?
Starvation 가능성 존재

📌 SRTF (Shortest Remaining Time First)

💡

짧은 작업부터 스케줄링하는 선점형 알고리즘 → SJF의 선점형 버전

특징

프로세스가 새로 도착하면, 재선점 실행

→ 현재 실행 죽인 작업과 도착한 직업의 CPU burst 잔여 시간을 비교해 짧은 작업부터 수행

📌 RR (Round Robin)

💡

FIFO의 원형 큐, 각 작업에 일정한 time slice 를 할당해 작업을 순환해 처리하는 선점형 알고리즘

특징

Time slice 할당: 각 작업이 일정한 시간 슬라이스를 할당받음

시간 간격이 크면 context switch가 적어지므로 많은 처리량 가능
시간 간격이 작으면 빠른 반응 속도 가능

No Starvation
Preemptive

💡 알고리즘 정리

특징	FIFO (First-Come, First-Served)	SJF (Shortest Job First)	SRTF (Shortest Remaining Time First)	RR (Round Robin)
기본 개념	도착 순서대로 작업을 처리	가장 짧은 실행 시간을 가진 작업을 먼저 처리	가장 짧은 잔여 시간을 가진 작업을 먼저 처리	각 작업에 일정한 시간 슬라이스를 할당하여 순환 처리
선점 여부	비선점형	비선점형	선점형	선점형
복잡도	매우 간단	상대적으로 간단	복잡함	상대적으로 간단
평균 대기 시간	높을 수 있음	낮음	낮음	보통
응답 시간	보통	보통	낮음	낮음
처리량 (Throughput)	낮음	높음	높음	보통
기아 (Starvation)	없음	있을 수 있음	있을 수 있음	없음
장점	구현이 매우 단순, 기아 없음	평균 대기 시간 최소화	평균 대기 시간 최소화, 응답 시간 개선	기아 없음, 응답 시간 개선
단점	평균 대기 시간이 길어질 수 있음	기아 문제 발생 가능	구현 복잡성 증가, 잦은 문맥 전환	적절한 시간 양자 선택이 필요

🔍 Priority Scheduling

💡

작업의 우선순위에 따라 실행 순서 결정

FIFO와 SJF는 우선순위 스케줄링의 일종 (먼저 들어오거나 CPU burst 길이가 우선순위)

동일 우선순위 작업은 FIFO나 RR 방식으로 처리 가능

선점형이거나 비선점형일 수 있음

우선순위는 동적으로 조정될 수 있음

Multi-level Feedback Queue(MLFQ)로 모델링됨

🙋 굶주림 문제는 어떻게 해결하나? 우선순위에 밀려서 CPU를 할당받지 못하는 프로세스가 나올 수 있습니다. 이런 경우, Aging(에이징) 기법을 사용합니다.

📌 Priority inversion problem

💡

우선순위가 뒤집어지는 문제, 낮은 우선순위 때문에 높은 우선순위 프로세스가 잠김

1️⃣ Priority inheritance protocol (PIP)

낮은 우선순위에게 잠시 높은 우선순위를 빌려줘서 빨리 끝내도록 함

2️⃣ Priority ceiling protocol (PCP)

최고의 우선순위를 갖도록 설정해서 빨리 끝내도록 함

📌 Multi-Level Feedback Queue (MLFQ)

💡

여러 개의 큐를 사용해 작업의 우선순위를 동적으로 조정하는 스케줄링 알고리즘

각 큐는 다른 우선순위를 가짐

배치, 인터렉티브, 시스템, CPU 바운드, I/O 바운드 등등..

동적으로 우선순위 조정

너무 오래 사용하면 우선순위가 낮은 큐에 집어넣는 식으로 활용

→ Aging!

우선순위를 바꿈으로써 굶주림 방지

💡 UNIX의 일반적 정책

I/O 작업을 많이 하는 프로세스에게 더 높은 우선순위

굶주림을 방지하기 위해 Aging 기법 사용

선점형

Time-shared

MLFQ 사용