CPU 스케줄링 알고리즘

song·2023년 5월 5일

혼자 공부하는 운영체제

목록 보기

7/17

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

단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링

문제점: CPU 사용 시간이 긴 프로세스가 들어오면 기다리는 시간이 길어짐 (호위 효과)

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

CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식

호위 효과 방지 가능

선점, 비선점 방식 둘 다 가능하지만 보통 비선점형으로 분류

라운드 로빈 스케줄링 (RR - Round Robin)

선입 선처리 스케줄링(FCFS) + 타임 슬라이스(Time Slice)
타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 시간

FCFS하되 타임 슬라이스(TS)가 끝나면 다시 큐로 삽입 (문맥 교환)

🚨주의

타임 슬라이스가 너무 크면 FCFS랑 다를게 없음

타임 슬라이스가 너무 작으면 자주 문맥 교환이 일어나 오버헤드가 발생

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

최단 작업 우선 스케줄링(SJF) + 라운드 로빈 스케줄링(RR)

정해진 시간만큼 CPU를 이용하되(TS), 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스를 선택

우선순위 스케줄링

프로세스들에 우선순위를 부여하고 우선순위가 높은 프로세스부터 실행

우선순위가 같다면 선입 선처리 스케줄링(FCFS)

크게보면 SJF, SRT도 우선순위 스케줄링에 포함

문제점: 기아 현상
우선순위 높은 프로세스만 계속 실행되고 우선순위가 낮은 프로세스는 실행 계속 연기

방지 기법: 에이징
오랫동안 대기한 프로세스의 우선순위를 점차 높여줌

다단계 큐 스케줄링 (Multilevel Queue)

우선순위 스케줄링의 발전된 형태

우선순위별로 준비 큐를 여러 개 사용하는 스케줄링

우선순위가 가장 높은 큐부터 처리하고 큐가 비면 다음 우선순위 큐를 처리

장점

프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리

큐별로 타임 슬라이스 여러 개 지정 가능

큐마다 다른 스케줄링 알고리즘 사용 가능

단점

프로세스들이 큐 사이를 이동할 수 없음
즉, 우선순위가 낮은 프로세스는 계속 밀려서 기아 현상 발생할 수 있음

다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue)

다단계 큐 스케줄링의 발전된 형태

큐 간의 이동 가능 (에이징 기법 사용 가능)

프로세스를 우선순위가 가장 높은 큐에 삽입하고 타임 슬라이스 동안 완료하지 못하면 다음 우선순위가 높은 큐에 삽입함
즉, CPU를 오래 사용하는 CPU 집중 프로세스는 우선순위가 낮아지고, CPU를 적게 사용하는 입출력 집중 프로세스는 우선순위가 높은 큐에서 실행이 끝남

구현이 복잡하지만, 가장 일반적인 CPU 스케줄링 알고리즘으로 알려짐