[OS] CPU 스케쥴링, CPU Scheduling

nnnyeong·2022년 9월 2일

CPUscheduling CS OS

OperatingSystem

목록 보기

10/11

CPU 스케쥴링이란

운영체제가 CPU 자원을 어떤 프로세스에게 할당해줄지 그 일정을 짜는 것
하나의 프로세스가 끝나고 다음으로 수행할 프로세스를 선택할 때 그 기준이 되는 알고리즘

스케쥴링의 목표

Batch System : 가능하면 많은 일을 수행, 시간 보다는 처리량이 중요
Interactive System : 빠른 응답 시간, 작은 대기 시간
Real-Time System : 기한 (deadline) 맞추기

스케쥴링 상황

프로세스가 종료(terminates) 될 때
프로세스가 실행 상태(running) 에서 대기 상태(waiting)으로 전환될 때

입출력 요청이나 자식 프로세스가 종료되기를 기다리기 위해 wait 호출 시

프로세스가 실행 상태(running) 에서 준비 완료(ready) 상태로 전환 될 때

인터럽트의 발생 혹은 time-slice 의 만료, 더 큰 우선순위의 프로세스가 들어올 경우

프로세스가 대기 상태(waiting) 에서 준비 완료 상태 (ready) 로 전환 될 때

입출력의 종료 시

프로세스의 상태 변화

Admitted, 승인

프로세스의 생성이 가능하며 승인 됨

Scheduler Dispatch

준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것

Interrupt

예외, 입출력, 이벤트 등이 발생해 현재 실행중인 프로세스를 준비 상태로 바꾸고 해당 작업을 먼저 처리 하는 것

입출력 / 이벤트 대기 상태

실행중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력 / 이벤트가 모두 끝날 때 까지 대기 상태로 만드는 것

입출력 / 이벤트 완료

입출력 / 이벤트가 끝난 프로세스를 준비 상태로 전환해 스케쥴러에 의해 선택될 수 있도록 만드는 것

스케쥴링 알고리즘 성능 지표

사용자 관점

반환 시간, turnaround time

프로세스 처음 시작부터 종료까지 걸린 시간
CPU 사용시간, waiting, 입출력 등 모든 시간을 포함

대기 시간, waiting time

CPU를 점유하기 위해 대기열 (ready queue) 에서 기다린 시간
다른 큐에서 기다린 시간 제외

응답 시간, response time

일반적으로 대화형 시스템에서 입력에 대한 반응 시간

시스템 관점

CPU 이용률

총 경과 시간 대비 프로세스에 CPU 가 이용되는 시간 비율

처리율, throughout

단위 시간당 처리하는 작업의 수

비선점(nonpreemptive) 알고리즘

프로세스 종료 or I/O 등의 이벤트가 있을 때까지 실행 보장 (처리시간 예측 용이함)

1. FCFS, First Come First Served

큐에 도착한 순서대로 CPU 시간 할당
일괄 처리 시스템에 적합함
대화형 시스템에는 부적합
실행 시간이 긴 프로세스가 앞에 있다면 평균 대기 시간이 길어짐

Convey Effect
CPU 처리 시간이 길지만 덜 중요한 작업이 CPU 처리 시간이 짧고 중요한 작업을 기다리게 하는 상태

2. SJF, Shortest Job First

수행 시간이 짧다고 판단되는 순서대로, 동일하다면 FCFS 로
평균 대기 시간이 짧음
다수의 프로세스에 빠른 응답
무한 대기가 발생할 수 있음
실제로 수행되기 전에는 CPU 점유 시간을 알 수 없기 때문에 비현실적

3. HRN, Highest Response Ratio Next

SJF 방식의 기아 현상을 해결하기 위해 고안
CPU 처리 시간과 ready queue 에서의 대기 시간을 함께 고려
우선순위 = (대기시간 + CPU 처리 시간) / CPU 처리 시간
선점이라면 대기시간이 계속해서 변경되어 반영되기 때문에 context switching 이 너무 자주 발생
역시 실제로 수행되기 전에는 CPU 점유 시간을 알 수 없기 때문에 비현실적

선점(preemptive) 알고리즘

OS가 CPU의 사용권을 선점할 수 있는 경우, 강제 회수하는 경우 (처리시간 예측 어려움)

1. SRT, Shortest Remaining Time

SJF 의 선점 버전
현재 CPU를 점유 중인 프로세스보다 남은 CPU 처리 시간이 짧은 프로세스가 ready queue 에 들어올 경우 CPU 점유 가져감

2. 우선 순위, Priority

정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
- 동적 부여 : 구현이 복잡, 오버헤드가 커짐, 시스템 응답 속도는 빠름
- 정적 부여 : 구현이 쉬움, 오버헤드 작음, 시스템 응답 속도 느림
우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있음
Aging 방법으로 Starvation 문제 해결 가능
동일한 우선순위라면 FCFS

3. Round Robin

FCFS + 선점 + time slice
모든 프로세스가 돌아가며 CPU 시간 할당 받음
time slice 시간이 경과하면 다음 프로세스로 CPU 할당 넘어감
시분할 시스템에서 사용
응답시간이 짧음, 대화형 시스템에서 사용됨
알고리즘 성능이 time slice에 의존적이다.
- time slice 가 크면 FCFS 와 유사해짐
- time slice 가 작으면 context switching 이 잦아져 오버헤드가 커짐

4. 다단계 큐, Multi-Level Queue

프로세스를 성격에 따라 여러 그룹으로 나누고 각 그룹마다 ready queue 가 존재
각 queue 마다 다른 스케쥴링 방식을 적용할 수 있음

Foreground Queue & Background Queue
운영체제는 프로세스를 분류할 때 사용자와 직접 상호작용하는 프로세스와 백그라운드에서 돌아가는 프로세스의 중요도를 다르게 분류한다. 사용자와 상호작용하는 프로세스는 빠르게 처리되어야 하고 백그라운드에서 돌아가는 프로세스는 조금 느리게 처리되어도 괜찮기 때문이다.
ex) Forground Queue 엔 Round Robin / Background Queue 엔 FCFS 적용