📌 CPU 스케줄링이란?
운영체제가 여러 프로세스 또는 스레드 중에서 CPU를 어떤 순서로 선택하여 실행시킬지 결정하는 작업을 말합니다. 하나의 CPU는 하나의 프로세스만을 실행할 수 있기 때문에, 여러 개의 프로세스가 동시에 실행을 요청하면 운영체제는 이들 사이에서 CPU 시간을 분배하여 작업을 처리합니다.
이러한 CPU 스케줄링은 CPU 시간을 효율적으로 분배하기 위해 수행되며, 프로세스의 우선순위, 작업량, 입출력 대기 등으르 고려하여 적절한 프로세스를 선택합니다.
CPU 스케줄링 발생 상황
- 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (I/O 발생)
- 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (인터럽트 발생)
- 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (I/O 종료)
- 프로세스가 종료할 때
1, 4(비선점 스케줄링) / 2, 3(선점 스케줄링)
스케줄링 기준
- CPU 이용률(Utilization): 어느 기간 동안 또는 특정 SNAPSHOT에서의 CPU의 이용률
- 처리량(Throughput): 단위 시간당 완료된 프로세스의 개수
- 총처리 시간(Turnaround Time): 프로세스의 제출 시간과 완료 시간의 간격
- 대기 시간(Waiting Time): 대기 시간은 프로세스가 준비 큐에서 대기하면서 보낸 시간의 합
- 응답 시간(Response Time): 하나의 Request를 제출한 후 첫 번째 Response가 나올 때까지의 시간
📌 비선점(nonpreemptive) 스케줄링
한 프로세스가 CPU를 할당받아 실행중이라면 다른 프로세스들이 CPU를 강제적으로 뺏을 수 없는 스케줄링 방식
FCFS(First Come First Served)
대기 큐에 도착한 순서대로 CPU를 할당하는 방식
- 작성이 간단하고 쉬운 이해도
- 긴 평균 대기 시간(Average Waiting Time), 응답 시간(Response Time)
- 반환시간(Turnaround Time) 면에서는 좋을 수 있음
- Convoy Effect(호위 효과) 발생
- 처리 시간이 긴 프로세스가 CPU를 차지하면, 다른 프로세스의 대기 시간이 길어진다.
SJF(Shortest Job First)
대기 큐에 있는 프로세스 중에서 처리 시간이 가장 짧은 프로세스부터 CPU에 할당
- 실행되고 있는 프로세스는 끝까지 실행한다.
- 선점형에서는 현재 실행되고 있는 프로세스의 남은 시간보다 도착한 다음 프로세스가 더 빨리 끝날 수 있는 프로세스라면 다음 프로세스를 실행하도록 바꾸게 된다.
- SJF 스케줄링은 평균 대기 시간을 줄일 수 있음
- 하지만 처리 시간이 긴 프로세스는 우선순위가 뒤로 밀려 starvation 현상 발생 -> 현실적으로 큐에 있는 프로세스들의 작업량을 알 수 있는 방법이 없다.
HRN(Highest Response Ratio Next)
대기 시간과 처리 시간을 고려하여 CPU를 할당
우선순위 = (대기 시간 + 처리 시간) / 처리 시간
- SJF 스케줄링 기법의 약점인 긴 작업과 짧은 작업 사이의 불평등을 보완하기 위한 방법
- 시스템 처리 시간이 커질수록 우선순위가 높아짐
📌 선점(Preemptive) 스케줄링
한 프로세스가 CPU를 할당받아 실행중이더라도 다른 프로세스가 CPU를 할당 받을 수 있는 스케줄링 방식
Round Robin
한 프로세스가 할당 받은 시간(time slice)동안 작업을 하다가 작업을 완료하지 못하면 대기 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식
- 각각의 프로세스에 동일한 CPU 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 한다.
- n개의 프로세스가 있을 때 할당 시간을 q로 설정하면, 어떤 프로세스도 (n-1)q 시간 이상을 기다리지 않아도 된다.
- 응답 시간을 빠르게 할 수 있다는 장점
SRT(Shortest Remaining Time)
SJF에 선점형 스케줄링을 혼합한 방식
- 최단 잔여시간을 우선으로 하는 스케줄링.
- 진행 중인 프로세스가 있어도, 최단 잔여시간인 프로세스를 위해 중단시키고 짧은 프로세스를 먼저 할당
Multi-Level Feedback Queue
여러 개의 waiting queue를 두고, 각 Queue에 우선 순위를 부여해, 우선 순위가 높은 Queue에 있는 프로세스에게 CPU를 할당하는 방식
동작 방식
- 우선 순위가 높은 Queue에 있는 프로세스가 먼저 실행
- 우선 순위가 같은 Queue 내부에서는 Round Robin 방식을 이용
- 프로세스는 맨 처음 우선순위가 가장 높은 Queue로 진입
- 프로세스가 주어진 CPU time slice를 모두 소진하면 한 단계 낮은 Queue로 이동
- 프로세스가 time slice안에 CPU를 양도하면 현재 Queue에 그대로 앉는다.
참고
피드백 및 개선점은 댓글을 통해 알려주세요😊
배움을 글로 기록하는 개발자가 되겠습니다.