CPU Scheduling

멀티프로그래밍(멀티프로세싱, 멀티태스킹)의 목적은 프로세스를 동시에 실행시켜 CPU 이용률을 극대화하는 것이다.

그럼 메모리에 로드된 프로세스들 중 어떤 프로세스를 CPU에게 할당하는 것이 최선일까?

 

---

CPU Scheduling을 위한 기본 개념

스케줄러와 디스패처

CPU scheduler: Ready 상태의 프로세스들 중 CPU에게 할당해 실행할 프로세스를 선택

dispatcher: context switching (dispatcher latency는 가급적 짧아야 한다!)

 

선점형과 비선점형 스케줄링

Non-preemptive scheduling: 프로세스가 종료되거나 I/O waiting 상태로 넘어갈 때까지 CPU 작업 계속 진행

• 과거 일괄 작업 방식에서 사용하던 방식
• 스케줄러의 작업량이 적고 문맥 교환에 의한 낭비도 적다
• CPU 사용 시간이 긴 프로세스 때문에 여러 프로세스가 기다리게 되어 전체 시스템 처리율 떨어짐

Preemptive scheduling: 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 OS가 CPU를 강제로 빼앗을 수 있는 방식

• ex) 인터럽트 처리, 타임 슬라이스
• 문맥 교환 같은 부가적인 작업으로 인해 낭비가 생기는 단점
• 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합

 

CPU 집중 프로세스와 입출력 집중 프로세스

실제 작업이 일어나는 것은

CPU를 사용하는 excute 상태와 입출력을 요청하여 완료되기까지 기다리는 waiting 상태로 나뉜다.

즉, 프로세스는 CPU burst 작업과, I/O burst 작업으로 나뉘는데, 생각보다 CPU burst 작업은 많지 않다.

입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템 효율이 향상된다.

입출력 프로세스는 잠깐 CPU를 사용한 후 대기 상태로 이동하기 때문에 다른 프로세스가 CPU 사용 가능하므로!

 

전면 프로세스와 후면 프로세스

전면 프로세스: 화면의 맨 앞에 놓인 프로세스. 현재 입력과 출력을 사용하는 프로세스 (=상호작용 프로세스)

후면 프로세스: 사용자와 상호작용이 없는 프로세스 (=일괄 작업 프로세스)

 

전면 프로세스는 사용자에 요구에 즉각 반응해야해서 전면 프로세스의 우선순위가 후면 프로세스보다 높다

 

프로세스 우선순위(by 효율성, 사용성)

우선순위가 높은 프로세스가 CPU를 먼저, 더 오래 차지하게 된다.

• 커널 프로세스 >  일반 프로세스
• 전면 프로세스 > 후면 프로세스
• 대화형 프로세스 > 일괄 작업 프로세스
• 입출력 집중 프로세스 > CPU 집중 프로세스

Scheduling Criteria

• CPU utilization (측정하기 어렵다)
• Turnaround time (submission~completion)
• Waiting time
• Response time

 

---

Scheduling Algorithms

ready queue에 있는 어떤 프로세스를 선택해야 할 것인가?

Non-preemptive	Preemptive
FCFS	RR (preemptive FCFS)
SJF	SRTF (preemptive SJF)
Priority-based	Priority-based (MLQ, MLFQ)

 

FCFS Scheduling: First-Come, First-Served

FIFO queue로 구현

convoy effect: CPU 작업 시간이 긴 프로세스가 먼저 배치되면 waiting time이 길어지게 된다.

 

SJF Scheduling: Shortest-Job-First

CPU 작업 시간이 짧은 프로세스를 먼저 실행해 waiting time을 줄인다.

그러나, CPU 작업 시간이 얼마나 남은지 알 수 없으며, 공평성에 위배되어 아사 현상이 발생한다.

 

SRTF Scheduling: Shortest-Remaining-Time-First

SJF의 선점형 버전.

새로운 프로세스가 들어왔을 때, 남은 시간이 더 짧다면 switching한다. waiting time을 더 줄일 수 있다.

 

RR Scheduling: Round-Robin

time quantum(time slice)만큼만 CPU 사용하고 쫓겨나는(interrupted) 선점형 FCFS.

준비 큐는 circular queue로 구현.

convey 효과와 아사 현상이 줄어든다.

 

문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 한다

• 타임 슬라이스가 크면 반응 속도가 매우 느릴 것이고,
• 타임 슬라이스가 작으면 동시에 실행되는 것처럼 느껴지나 문맥 교환이 너무 자주 일어나 시스템 성능이 떨어진다.

Priority-base Scheduling

프로세스의 중요도에 따라 우선순위를 반영하여 높은 우선순위를 가진 프로세스가 먼저 실행된다.

선점형 알고리즘과 비선점형 알고리즘으로 나뉜다. (SJT/SRTF)

 

프로세스의 우선순위를 배정하는 방식

• 고정 우선순위 방식: 시스템이 시시각각 변하는데 우선순위를 고정하면 변화에 대응하기 어려워 효율이 떨어진다
• 변동 우선순위 방식: 우선순위가 프로세스 작업 중간에 변해 시스템의 효율을 높일 수 있다

 

문제점: 우선순위 낮은 프로세스의 starvation (indefinite blocking)

해결책: 사용한 프로세스의 우선순위를 높이는 aging.

 

MLQ Scheduling: Multi-Level Queue (다단계 큐 - 고정 우선순위)

우선순위에 따라 준비 큐를 여러 개 사용하는 방식

상단의 큐에 있는 모든 프로세스의 작업이 작업이 끝나야 다음 우선순위 큐의 작업이 시작됨

우선순위가 낮은 프로세스의 작업이 연기되는 문제

프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입된다

검색 효율을 높이기 위해서 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아놓는다

 

MLFQ Scheduling: Multi-Level Feedback Queue (다단계 피드백 큐 - 변동 우선순위)

CPU를 사용하고 난 프로세스는 우선순위가 낮아져(aging) 원래 큐로 돌아가지 않고 다음 우선순위의 큐에 들어간다.

우선순위에 따라 타임 슬라이스의 크기가 다르다.

어렵게 얻은 CPU를 오랫동안 사용할 수 있도록 하여, 결국 최하위 우선순위 프로세스는 FCFS 스케줄링 방식으로 동작.

 

변동 우선순위: starvation을 해결하기 위한 aging.

 

---

Thread Scheduling

현재는 멀티코어, 멀티스레드로 동작하므로, CPU 스케줄링을 프로세스가 아닌 커널 스레드를 가지고 한다.

사용자 스레드는 스레드 라이브러리가 관리하고 커널은 뭐가 돌아가고 있는지 모른다.

사용자 스레드는 그저 커널 스레드에게 맵핑되어 서비스받을 뿐이다.

 

 

 

 

---

 

참고 자료 & 이미지 출처
운영체제 공룡책 강의 (주니온 님)
Operating System Concepts, 10th Ed (Silberschatz et al)
쉽게 배우는 운영체제 (조성호 님)