언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업 → CPU 이용률을 극대화하기 위해서 멀티프로그래밍(multiprogramming) 필요함. 제한된 CPU core 개수를 가지고 효율적으로 프로세스를 수행하기 위해 CPU 스케줄링 필요함
📌 목적
1️⃣ 공평성 : 프로세스에게 자원을 배분하는 과정이 공평해야 함.
2️⃣ 효율성 : 시스템 자원이 쉬는 시간이 없어야 함.
3️⃣ 안정성 : 중요 프로세스들은 우선권을 주고 프로세스가 증가해도 안정적으로 운영되어야 함.
4️⃣ 확장성 : 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되어야 함.
5️⃣ 반응 시간 보장 : 프로세스의 요구가 있을 경우 적절한 시간 안에 반응해야 함.
6️⃣ 무한 연기 방지 : 특정 프로세스의 작업이 무한정 연기되면 안됨.
📌 선점형, 비선점형 스케줄링
1️⃣실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때 ( ex : I/O 발생 ) → 비선점형 스케줄링 2️⃣실행(running) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : intterupt 발생 ) → 선점형 스케줄링 3️⃣대기(waiting) 상태에서 준비(ready) 상태로 전환(switching)될 때 ( ex : I/O 완료 시 ) → 선점형 스케줄링 4️⃣종료(Terminated, Exit)될 때 → 비선점형 스케줄링
💡 ✓ 승인 (Admitted) : 프로세스 생성이 가능하여 승인됨.
✓ 스케줄러 디스패치 (Scheduler Dispatch) : 준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.
✓ 인터럽트 (Interrupt) : 예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.
✓ 입출력 또는 이벤트 대기 (I/O or Event wait) : 실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.
✓ 입출력 또는 이벤트 완료 (I/O or Event Completion) : 입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것.
1️⃣ 비선점형 스케줄링
• 프로세스가 CPU를 점유하고 있따면 이를 뺏을 수 없는 방식
• 필요한 문맥 교환만 일어나므로 오버헤드(overhead)가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 남.
2️⃣ 선점형 스케줄링
• 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺏을 수 있는 방식
• CPU 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영 가능
• 잦은 문맥 교환으로 오버헤드(Overhead)가 커질 수 있음.
📌 CPU 스케줄링 평가 기준
1️⃣ CPU 이용률(CPU utilization)
• 시간당 CPU를 사용한 시간의 비율
• 프로세서를 실행상태로 항상 유지하도록 해야 함.
2️⃣ 처리율(Throughput)
• 시간당 처리한 작업의 비율
• 단위 시간당 완료되는 작업 수가 많도록 해야 함.
3️⃣ 반환시간(Turnaround Time)
• 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
• 작업이 준비 큐(ready queue)에서 기다린 시간부터 CPU에서 실행된 시간, I/O 작업 시간의 합
4️⃣ 대기시간(Waiting Time)
• 대기열에 들어와 CPU를 할당받기 까지 기다린 시간
• 준비 큐에서 기다린 시간의 총합
5️⃣ 반응시간(Response Time)
• 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간
• CPU를 할당받은 최초의 순간까지 기다린 시간 한번 만을 측정함.
➡️ “CPU 이용률, 처리율 극대화 / 반환시간, 대기시간, 반응시간 최소화”
📌 CPU 스케줄링 알고리즘
✅ 비선점 스케줄링
1️⃣FCFS (First Come First Served)
• 큐에 도착한 순서대로 CPU 할당
• 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐.
2️⃣ SJF(Shortest Job First)
• 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
• FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
3️⃣ HRN (Hightest Response-ratio Next)
• 우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
• 우선순위 = (대기시간 + 실행시간) / (실행시간)
✅ 선점 스케줄링
1️⃣ Priority Scheduling
• 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
• 우선 순위가 낮은 프로세스가 무한정 기다리는 Starvation 이 생길 수 있음
• Aging 방법으로 Starvation 문제 해결 가능
2️⃣ Round Robin
• FCFS에 의해 프로세스들이 보내지면 각 프로세스는 동일한 시간의 Time Quantum 만큼 CPU를 할당 받음.
‣ Time Quantum 또는 Time Slice : 실행의 최소 단위 시간
• 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 Context Switching이 잦아져서 오버헤드 증가
3️⃣ Multilevel-Queue(다단계 큐)
• 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법
• 우선순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정 해주는 방식 사용
• 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당.
4️⃣ Multilevel-Feedback-Queue (다단계 피드백 큐)
• 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로 있음.
→ Time Quantum을 다 채운 프로세스는 CPU burst 프로세스로 판단하기 때문
