프로세스 스케줄링 개념
- 스케줄링: 여러 작업이 있을 때 처리 순서를 결정하는 작업
- 프로세스 스케줄링: 여러 프로세스 가운데 어떤 프로세스를 먼저 실행할지 결정하는 작업
- 운영체제는 준비 상태의 여러 프로세스 중에서 CPU를 할당할 대상을 선택해야 함
- 프로세스 스케줄링은 CPU 사용 순서를 정하는 문제로 볼 수 있음
운영체제 스케줄링 단계 구분
- 상위 단계 스케줄링
- 중간 단계 스케줄링
- 하위 단계 스케줄링
상위 단계 스케줄링 개요
- 시스템에 새로운 작업이 들어오면 먼저 작업 큐에 저장 가능
- 상위 단계 스케줄링은 이 작업들 가운데 어떤 작업을 프로세스로 생성할지 결정하는 단계
- 목적은 시스템 자원을 효율적으로 사용할 수 있도록 조절하는 데 있음
상위 단계 스케줄링 동작
- CPU 사용량이 너무 높으면 새 작업의 프로세스 생성을 잠시 늦출 수 있음
- 입출력 장치 사용량이 과도하면 해당 작업을 잠시 대기시킬 수 있음
- 시스템 전체 부하를 고려하여 프로세스 생성 자체를 조절하는 역할 수행
하위 단계 스케줄링 개요
- 하위 단계 스케줄링은 준비 큐에 들어 있는 프로세스들 가운데 어떤 프로세스에게 CPU를 줄지 결정하는 단계
- 일반적으로 운영체제에서 가장 핵심적으로 다루는 스케줄링이 이 단계에 해당함
- 실제 CPU 배정 동작은 디스패치(dispatch) 와 연결됨
하위 단계 스케줄링 수행 과정
- 준비 큐에서 하나의 프로세스 선택
- 선택된 프로세스를 실행 상태로 전환
- CPU를 실제로 할당하여 명령 수행 시작
중간 단계 스케줄링 개요
- 중간 단계 스케줄링은 시스템 부하를 조절하기 위해 일부 프로세스를 잠시 중지시키는 단계
- 실행 중이거나 준비 상태인 일부 프로세스를 메모리에서 내보낸 뒤 나중에 다시 불러올 수 있음
- 목적은 단기적인 부하 조절에 있음
중간 단계 스케줄링 동작
- 시스템에 프로세스가 너무 많을 때 일부 프로세스를 잠시 중단 가능
- CPU나 메모리에 여유가 생기면 다시 적재하여 실행 가능
- 중간 단계 스케줄링은 프로세스 수를 조절하여 시스템을 안정적으로 유지하는 역할 수행
프로세스 스케줄링 기본 목표
프로세스 스케줄링은 단순히 순서를 정하는 작업이 아니라 다음과 같은 목표를 가짐
- 공정성 확보
- 균형성 유지
공정성 확보 의미
- 모든 프로세스가 적절하게 CPU를 사용할 수 있어야 함
- 특정 프로세스만 계속 실행되고 다른 프로세스가 계속 밀려나면 바람직하지 않음
균형성 유지 의미
- CPU뿐 아니라 입출력 장치 등 시스템 자원이 고르게 활용되어야 함
- 어떤 자원은 지나치게 바쁘고 어떤 자원은 계속 놀고 있다면 균형 잡힌 스케줄링이라고 보기 어려움
일괄 처리 운영체제 목표
일괄 처리 운영체제에서는 다음 목표가 중요함
- 처리량 극대화
- 반환 시간 최소화
- CPU 활용 극대화
처리량 개념
- 주어진 시간 동안 처리된 프로세스 수를 의미함
- 같은 시간 동안 더 많은 작업을 끝낼수록 처리량이 높다고 판단함
반환 시간 개념
- 프로세스가 생성된 시점부터 종료될 때까지 걸린 전체 시간을 의미함
- 반환 시간이 짧을수록 사용자는 더 빨리 결과를 받을 수 있음
시분할 운영체제 목표
시분할 운영체제에서는 다음 목표가 중요함
- 빠른 응답 시간 확보
- 과도한 대기 시간 방지
응답 시간 개념
- 사용자가 요청한 시점부터 시스템이 처음 반응을 보일 때까지의 시간
- 전체 처리 완료 시간이 아니라, 반응 시작까지 걸린 시간을 의미함
대기 시간 개념
- 프로세스가 준비 큐에서 CPU를 받지 못하고 기다린 시간
- 대기 시간이 지나치게 길어지면 사용자 입장에서 시스템이 느리게 느껴짐
실시간 운영체제 목표
- 실시간 운영체제에서는 처리 기한 준수가 가장 중요함
- 요청된 작업이 정해진 시간 안에 반드시 끝나야 함
- 스케줄링은 마감 시한을 만족시키는 방향으로 이루어져야 함
선점 스케줄링 정의
- 선점 스케줄링은 실행 중인 프로세스로부터 CPU를 강제로 빼앗을 수 있는 방식
- 더 중요한 프로세스가 들어오면 현재 실행 중인 프로세스를 중단시키고 새로운 프로세스에게 CPU를 줄 수 있음
선점 스케줄링 적용 환경
- 실시간 운영체제
- 시분할 운영체제
선점 스케줄링 장점
- 높은 우선순위 프로세스를 빠르게 처리할 수 있음
- 응답 시간을 줄이는 데 유리함
선점 스케줄링 단점
- 문맥 교환이 자주 일어나면 오버헤드가 커질 수 있음
오버헤드란
- 시스템 동작을 위해 부가적으로 발생하는 처리 비용
- 실제 프로그램 실행과는 직접적인 작업이 아닌 추가 작업
- 본래 작업 외에 추가로 소비되는 시간, 자원, 처리 비용
비선점 스케줄링 정의
- 비선점 스케줄링은 한 번 CPU를 할당받은 프로세스가 스스로 CPU를 놓을 때까지 계속 실행되는 방식
- 실행 중인 프로세스를 강제로 준비 상태로 되돌릴 수 없음
비선점 스케줄링 가능한 상태 전이
- 실행 상태에서 종료 상태로 이동 가능
- 실행 상태에서 대기 상태로 이동 가능
비선점 스케줄링 불가능한 상태 전이
- 실행 중인 프로세스를 강제로 준비 상태로 되돌리는 전이 불가능
비선점 스케줄링 장점
- 강제 문맥 교환이 없으므로 오버헤드가 적음
비선점 스케줄링 단점
- 긴 프로세스가 실행 중이면 짧은 프로세스나 중요한 프로세스가 오래 기다릴 수 있음
문맥 교환 개념
- 문맥 교환은 CPU가 한 프로세스에서 다른 프로세스로 바뀔 때 필요한 상태 정보를 저장하고 복원하는 작업
- 현재 실행 중인 프로세스의 레지스터 값 등을 PCB에 저장하고, 다음 프로세스의 정보를 CPU에 복원함
PCB란
- 운영체제가 각 프로세스를 관리하기 위해 유지하는 데이터 구조
- 프로세스가 생성될 때 만들어지고, 종료 시 삭제됨
문맥 교환 발생 의미
- 선점 스케줄링에서는 문맥 교환이 자주 발생할 수 있음
- 문맥 교환은 실제 작업 처리 시간이 아니라 부가적으로 드는 시간이므로 오버헤드에 해당함
스케줄링 알고리즘 평가 기준
스케줄링 알고리즘을 비교할 때 주로 다음 두 기준 사용
- 평균 대기 시간
- 평균 반환 시간
평균 대기 시간 정의
- 각 프로세스가 준비 큐에서 기다린 시간을 모두 구한 뒤 평균을 낸 값
평균 반환 시간 정의
- 각 프로세스가 생성된 시점부터 종료될 때까지 걸린 시간을 구한 뒤 평균을 낸 값
FCFS 스케줄링 개념
- FCFS는 First Come First Served의 약자
- 준비 큐에 먼저 도착한 프로세스를 먼저 처리하는 방식
- 가장 기본적인 스케줄링 방식
- 비선점 방식에 해당함
FCFS 스케줄링 특징
- 큐 자료구조를 사용하면 쉽게 구현 가능
- 도착 순서가 곧 실행 순서가 됨
FCFS 스케줄링 장점
- 구현이 매우 단순함
FCFS 스케줄링 단점
- 긴 프로세스가 먼저 들어오면 짧은 프로세스가 오래 기다리게 됨
- 중요한 프로세스가 나중에 들어와도 바로 처리할 수 없음
- 도착 순서에 따라 평균 대기 시간과 평균 반환 시간이 크게 달라질 수 있음
SJF 스케줄링 개념
- SJF는 Shortest Job First의 약자
- 준비 큐에 있는 프로세스들 가운데 실행 시간이 가장 짧다고 예상되는 프로세스를 먼저 처리하는 방식
- 비선점 방식에 해당함
SJF 스케줄링 특징
- 전체 실행 예상 시간이 짧은 작업을 먼저 처리함
- 평균 대기 시간을 줄이는 데 유리한 방식으로 알려져 있음
SJF 스케줄링 장점
- 짧은 작업을 빠르게 끝낼 수 있음
- 일괄 처리 환경에서 효율적일 수 있음
SJF 스케줄링 단점
- 각 프로세스의 실행 예상 시간을 알아야 함
- 실제로는 예상 실행 시간을 정확히 알기 어려움
- 긴 작업은 계속 뒤로 밀릴 위험이 있음
- 비선점 방식이므로 시분할 환경에는 부적합함
SRT 스케줄링 개념
- SRT는 Shortest Remaining Time의 약자
- 준비 큐에 있는 프로세스들 가운데 남은 실행 시간이 가장 짧은 프로세스를 선택하는 방식
- SJF를 선점 방식으로 바꾼 형태로 볼 수 있음
SRT 스케줄링 특징
- 실행 중인 프로세스보다 더 짧은 남은 시간을 가진 프로세스가 들어오면 CPU를 빼앗아 올 수 있음
- 선점 방식에 해당함
SRT 스케줄링 장점
- SJF보다 평균 대기 시간과 평균 반환 시간을 더 줄일 가능성이 있음
SRT 스케줄링 단점
- 남은 실행 시간을 계속 계산하고 비교해야 함
- 문맥 교환이 자주 발생할 수 있음
- 실제 실행 시간 예측이 어렵기 때문에 구현이 쉽지 않음
RR 스케줄링 개념
- RR은 Round Robin의 약자
- 준비 큐에 도착한 순서대로 CPU를 배정하되, 각 프로세스는 정해진 시간 할당량만큼만 CPU를 사용할 수 있는 방식
- 선점 방식에 해당함
RR 스케줄링 핵심 동작
- 시간 할당량을 다 쓰기 전에 종료하면 그대로 끝남
- 시간 할당량을 다 썼는데도 종료하지 못하면 준비 큐의 뒤로 이동함
RR 스케줄링 장점
- CPU를 비교적 공평하게 분배할 수 있음
- 시분할 운영체제에 가장 적합한 방식
- 응답 시간을 빠르게 만드는 데 유리함
RR 스케줄링 단점
- 시간 할당량이 너무 크면 FCFS와 비슷해짐
- 시간 할당량이 너무 작으면 문맥 교환이 지나치게 많아짐
- 따라서 적절한 시간 할당량 설정이 중요함
HRN 스케줄링 개념
- HRN은 Highest Response Ratio Next의 약자
- 준비 큐에서 응답 비율이 가장 큰 프로세스를 먼저 처리하는 방식
- 비선점 방식에 해당함
HRN 스케줄링 응답 비율 의미
- 응답비율 = (대기시간 / 예상실행시간) + 1
- 대기 시간이 길수록 응답 비율이 커짐
- 예상 실행 시간이 짧을수록 응답 비율이 커짐
HRN 스케줄링 동작 의의
- 짧은 작업을 우선 처리하는 성질 유지
- 오래 기다린 작업의 우선순위도 점점 높여 줌
HRN 스케줄링 장점
- SJF에서 긴 작업이 지나치게 오래 기다릴 수 있는 문제를 어느 정도 완화함
HRN 스케줄링 단점
- 여전히 실행 예상 시간을 알아야 함
- 실제 시스템에서는 이 값을 정확히 알기 어려움
다단계 피드백 큐 스케줄링 개념
- 다단계 피드백 큐 스케줄링은 여러 개의 준비 큐를 사용하는 방식
- 각 큐마다 서로 다른 시간 할당량을 가짐
- 일반적으로 상위 큐일수록 우선순위가 높고 시간 할당량은 짧음
- 하위 큐로 갈수록 우선순위는 낮아지고 시간 할당량은 길어짐
다단계 피드백 큐 스케줄링 동작 방식
- 새 프로세스는 보통 가장 높은 우선순위 큐로 들어감
- 시간 할당량을 다 쓰고도 끝나지 않으면 더 낮은 단계의 큐로 내려감
- 시간 할당량을 다 쓰기 전에 입출력 등으로 CPU를 스스로 놓으면 현재 단계에 머물 수 있음
다단계 피드백 큐 스케줄링 의미
- 입출력 중심 프로세스는 높은 우선순위를 유지하기 쉬움
- 연산 중심 프로세스는 아래 단계로 내려가면서 더 긴 시간 할당량을 받게 됨
다단계 피드백 큐 스케줄링 장점
- 시분할 환경에서 반응성과 효율성을 함께 고려할 수 있음
- 입출력 중심 작업과 CPU 중심 작업을 어느 정도 구분하여 처리할 수 있음
스케줄링 알고리즘 상호 관계
프로세스 스케줄링 알고리즘은 서로 완전히 독립된 것이 아니라 일부가 연결된 형태로 이해 가능
- FCFS에 시간 할당량 개념을 넣으면 RR로 볼 수 있음
- RR을 여러 단계 큐로 확장하면 다단계 피드백 큐가 됨
- SJF를 선점 방식으로 바꾸면 SRT가 됨
- SJF에 오래 기다린 프로세스의 우선순위를 높이는 개념을 넣으면 HRN이 됨
정리
- 프로세스 스케줄링은 여러 프로세스 가운데 CPU를 누구에게 줄지 결정하는 작업
- 스케줄링은 상위 단계, 중간 단계, 하위 단계로 구분 가능
- 스케줄링 정책은 선점 방식과 비선점 방식으로 구분 가능
- 선점 방식은 응답성을 높이는 데 유리하지만 문맥 교환 오버헤드 발생
- 비선점 방식은 단순하지만 긴 작업 때문에 다른 프로세스가 오래 기다릴 수 있음
- 스케줄링 알고리즘 평가에는 평균 대기 시간과 평균 반환 시간을 많이 사용함
- 대표 알고리즘으로는 FCFS, SJF, SRT, RR, HRN, 다단계 피드백 큐가 있음
- HRN 스케줄링의 응답 비율은 예상 실행시간이 짧을수록, 그리고 대기시간이 길수록 커짐
- 다단계 피드백 큐 스케줄링은 입출력 위주의 프로세스가 연산 위주의 프로세스보다 우선권을 갖도록 함
- 각 알고리즘은 운영체제의 목적과 환경에 따라 서로 다른 장단점 가짐