5 - CPU 스케줄링

✔️ CPU 스케줄링이란?

여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일

1. 스케줄링의 종류

1️⃣ 고수준 스케줄링(장기 스케줄링, 작업 스케줄링)

• 시스템 내의 전체 작업 수를 조절하는 것
  • 여기서 작업은 운영체제에서 다루는 일의 가장 큰 단위를 뜻함. 1개 또는 여러개의 프로세스로 이루어짐
• 작업 요청이 들어오면 스케줄러가 시스템의 상황을 고려하여 작업을 승인할지, 거부할지를 결정함(그래서 승인 스케줄링이라고도 함)
• 스케줄러의 이러한 결정에 따라 시스템 내에서 동시에 실행가능한 프로세스의 수가 결정되는데 이를 degree of multiprogramming이라고 함

2️⃣ 저수준 스케줄링(단기 스케줄링)

• 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정

3️⃣ 중간 수준 스케줄링

• 고수준 스케줄링과 저수준 스케줄링 사이에 일어나는 스케줄링
• 시스템의 과부하를 조절하기 위해 활성화된 프로세스 중 일부를 보류 상태로 보냄
• 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화 됨

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

선점: 빼앗을 수 있음
비선점: 빼앗을 수 없음

✔️ 선점형 스케줄링

• 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식 ex) 인터럽트
• 시분할 시스템을 고려하여 만들어진 알고리즘
• 문맥 교환과 같은 작업으로 인해 오버헤드 발생

✔️ 비선점형 스케줄링

• 어떤 프로세스가 실행 상태에 들어가 CPU를 사용하면 그 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지는 계속 실행되는 스케줄링 방식
• 기다리는 프로세스가 많아 처리율이 떨어지기 때문에 지금은 거의 사용되지 않음

3. 스케줄링 알고리즘

구분	종류
비선점형	FCFS 스케줄링, SJF 스케줄링
선점형	라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링
둘 다 가능	우선순위 스케줄링

3.1 FCFS 스케줄링(First Come First Served)

• 선입선출 스케줄링
• 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식
• 초기의 일괄 작업 시스템에서 사용됨
• 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스 실행 가능
• 큐가 하나라서 모든 프로세스의 우선순위가 동일함
• 단점: 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져서 작업 효율이 떨어짐

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

• 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
• SPF(Shortest Process First) 또는 최단 프로세스 우선 스케줄링이라고도 함

단점

• 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움
  • 현대의 프로세스는 사용자와 빈번하게 상호작용하기 때문에 프로그램 종료 시간을 파악하기 어려움
• 공평성에 위배된다!
  • 작업 시간이 짧은 프로세스가 계속해서 준비 큐에 들어오면 작업시간이 긴 프로세스는 계속해서 연기되는데 이를 기아(아사) 또는 무한 봉쇄 현상이라고 함
  • 이러한 기아 상태는 에이징으로 완화 가능

기아 상태란?

특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태

에이징

• 프로세스가 양보할 수 있는 상한선을 정하는 방식
• 프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지만 양보하도록 규정하는 방식
• 에이징 값을 어떤 기준으로 정할 것인지 문제가 있어 한계가 있음

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

• 한 프로세스가 할당 받은 시간(타임 슬라이스)동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
• 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행됨
• 선입선출 알고리즘과 유사하지만, 각 프로세스마다 CPU를 사용할 수 있는 최대 시간(타임 슬라이스)가 있음
• 문맥 교환 시간이 추가됨

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

• SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식(SJF의 선점형 버전)
• 라운드 로빈은 준비 큐에 있는 순서대로 CPU를 할당한다면 SRT 우선 스케줄링은 남은 작업 시간이 적은 프로세스에 CPU를 먼저 할당함

단점

• 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 작업이 추가됨
• SJF 스케줄링과 마찬가지로 운영체제가 프로세스 종료 시간을 예측하기 어렵고 아사 현상이 발생함

3.5 우선순위 스케줄링

• 프로세스의 우선순위에 따라 스케줄링하는 방식. 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현 가능함
• 시스템의 효율성이 아니라 프로세스의 중요도를 기준으로 결정됨(커널 > 일반 프로세스)
• 우선순위 스케줄링은 비선점형과 선점형 방식에 모두 적용 가능함!
  • SJF 스케줄링(비선점형): 작업 시간이 짧은 프로세스에 높은 우선순위 부여
  • SRT 스케줄링(선점형): 남은 시간이 짧은 프로세스에 높은 우선 순위 부여
• 고정 우선순위 알고리즘
  • 한 번 우선순위를 부여받으면 종료될 때까지 우선순위가 고정됨
  • 단순하게 구현 가능하지만 시시각각 변하는 시스템 상황을 반영하지 못해 효율성 떨어짐
• 변동 우선순위 알고리즘
  • 일정시간마다 변하는 우선순위를 새로 계산함
  • 시스템이 복잡하지만 상황을 시시각각 반영하여 효율적으로 운영가능함

3.6 다단계 큐 스케줄링(MLQ Multi-Level Queue)

• 우선순위에 따라 준비 큐를 여러 개 사용하는 방식
• 프로세스는 운영체제에게 부여받은 우선순위(고정형 우선순위)에 따라 해당 우선순위의 큐에 삽입됨
• 상단 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작됨
• 각 단계의 큐에 라운드 로빈 방식을 사용함

3.7 다단계 피드백 큐 스케줄링(MLFQ Multi-Level Feedback Queue)

• 오늘날 운영체제가 CPU 스케줄링을 할 때 일반적으로 사용하는 방식
• MLQ 방식에서 우선순위가 낮은 프로세스의 작업이 연기되는 문제점을 보완한 방식
• 프로세스가 CPU를 사용한 후 우선순위가 낮아져서 원래 큐로 되돌아가지 않고 하나 낮은 큐의 끝으로 들어감(그렇다고 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않음)
• 우선순위에 따라 타임 슬라이스의 크기가 다름(우선순위가 낮을수록 타임슬라이스 커짐)
• 따라서 마지막 큐(우선순위가 가장 낮은) 프로세스는 무한대의 타임 슬라이스를 얻게됨(프로세스가 실행 상태에 들어가면 CPU를 빼앗기지 않고 끝까지 작업을 마친다는 뜻) -> FCFS 스케줄링 방식으로 동작함

참조
📚 쉽게 배우는 운영체제