[운영체제] CPU 스케줄링 알고리즘

cosmos-JJ·2023년 9월 28일

CS 운영체제

Computer Science

목록 보기

11/15

CPU 스케줄링 알고리즘

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

선입 선처리 스케줄링 / FCFS 스케줄링 :준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식

선입 선처리 스케줄링은 호위 효과가 발생할 수 있다는 단점이 있다.
- 호위 효과(convoy effect) : 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것

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

최단 작업 우선 스케줄링 / SJF 스케줄링 : 준비 큐에 삽입된 프로세스들 중 CPU이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식

최단 작업 우선 스케줄링은 기본적으로 비선점형 스케줄링 알고리즘으로 분류되지만, 선점형으로 구현될 수 있다. ➡ 최소 잔여 시간 우선 스케줄링

라운드 로빈 스케줄링 (round robin scheduling)

라운드 로빈 스케줄링 : 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링 방식

타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다.
프로세스들은 정해진 시간만큼만 CPU를 이용하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다. (= 문맥 교환 발생)
타임 슬라이스가 지나치게 크면 선입 선처리 스케줄링과 같이 호위효과가 생길 여지가 있다.

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

최소 잔여 시간 우선 스케줄링 / SRT 스케줄링 : 최단 작업 우선 스케줄링 알고리즘과 라운드 로빈 알고리즘을 합친 스케줄링 방식

프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택된다.

우선순위 스케줄링 (priority scheduling)

우선순위 스케줄링 : 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘

우선순위 스케줄링의 근본적인 문제 ➡ 기아현상 발생
- 기아 현상 (starvation) : 우선순위가 낮은 프로세스들이 우선순위가 높은 프로세스들에 의해 실행이 계속해서 연기되는 현상
우선순위가 같은 프로세스들은 선입 선처리로 스케줄링된다.
기아현상을 방지하기 위한 대표적인 기법 ➡ 에이징
- 에이징 (aging) : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

다단계 큐 스케줄링 (multilevel queue scheduling)

다단계 큐 스케줄링 : 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식

우선순위 스케줄링의 발전된 형태이다.
우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 그다음 우선순위 큐에 있는 프로세스를 처리한다.
프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리하다는 장점이 있다.
큐별로 타임 슬라이스를 여러 개 지정 가능하다.
큐마다 다른 스케줄링 알고리즘을 사용할 수 있다.
프로세스들이 큐 사이를 이동할 수 없다.

다단계 피드백 큐 스케줄링 (multilevel feedback queue scheduling)

다단계 피드백 큐 스케줄링 : 다단계 큐 스케줄링 + 프로세스들이 큐 사이를 이동할 수 있는 스케줄링

다단계 큐 스케줄링의 발전된 형태이다.
⬇ 흐름 ⬇

    1. 새로운 프로세스가 들어왔을 때 가장 높은 우선순위 큐에 삽입되고 일정 시간 (타임 슬라이스) 동안 실행
    2. 프로세스가 실행이 일정 시간동안 끝나지 않는 다면 다음 우선순위 큐에 삽입되어 실행
    
    => CPU를 오래 사용해야 하는 프로세스는 우선순위가 점차 낮아짐