프로세서 스케줄링의 종류
멀티프로그래밍 (Multiprogramming) = 인터리빙
단일 프로세서 시스템 내에서 여러 프로세스를 관리하는 것
멀티프로세싱 (Multiprocessing) = 오버래핑
다중 프로세서 시스템 내에서 여러 프로세스를 관리하는 것
분산 처리 (Distributed Processing)
여러 대의 분산된 컴퓨터 시스템에서 여러 프로세스를 관리하는 것
멀티프로그래밍의 핵심은 스케줄링이다
멀티프로그래밍의 목표는
- (항상 어떤 프로세스가 실행 중이도록 하는 것)
- CPU Utilization을 극대화하는 것
CPU–I/O 버스트 사이클 : 프로세스의 실행은 CPU 실행과 I/O 대기 사이클로 이루어져 있다.
- CPU 버스트가 끝나면 I/O 버스트가 뒤따른다
- 짧은 버스트는 많고, 긴 버스트는 적다
프로세서 스케줄링의 종류
- 스케줄링: 큐를 관리하여 큐잉 지연(대기 시간)을 최소화하는 것이다.
- 프로세서를 통해 실행할 프로세스를 시스템의 목표에 맞게 할당하는 것
System objectives
- 프로세서 효율(processor efficiency)
- 처리량(throughput)
- 응답 시간(response time)
장기 스케줄링 (Long-term scheduling)
실행될 프로세스 풀에 새로운 프로세스를 추가할지 결정하는 것
중기 스케줄링 (Medium-term scheduling)
메인 메모리에 부분적으로 또는 완전히 존재하는 프로세스의 수를 조절하는 결정
(예: 프로세스를 메모리에서 제거하거나 다시 불러오는 것)
단기 스케줄링 (Short-term scheduling)
프로세서가 실행할 수 있는 프로세스들 중에서 어떤 것을 실행할지 결정하는 것
(가장 자주 이루어지는 스케줄링)
입출력 스케줄링 (I/O scheduling)
대기 중인 I/O 요청들 중 어떤 것을 사용 가능한 I/O 장치로 처리할지 결정하는 것
장기 스케줄링과 중기 스케줄링은 주로 다중 프로그래밍의 정도에 의해 결정
장기 스케줄링
프로세스가 생성될 때 수행
새로운 프로세스를 Ready queue에 추가할지 결정하는 것
New ↔ Ready
중기 스케줄링
스와핑(Swapping) 기능의 일부로 수행
프로세스를 메인 메모리에 포함시킬지 결정
Suspended/Ready ↔ Ready
Suspended/Blocked ↔ Blocked
단기 스케줄링
Ready 큐에 있는 프로세스 중에서, 어떤 프로세스를 다음에 실행할 지 결정하는 것
Ready ↔ Running
장기 스케줄러(Long-Term Scheduler)
어떤 프로그램을 시 받아들일지 결정
다중 프로그래밍의 정도를 제어
만약 프로세서의 idle time이 특정 thresholde(임계값)을 초과하면,
장기 스케줄러가 호출되어 하나 이상의 작업을 추가
실행 중인 프로세스들에게 만족스러운 서비스를 제공하기 위해
다중 프로그래밍의 정도는 제한될 수 있다
장기 스케줄러는 Job Queue에 대한 프로세스를 생성하면서 다음을 결정해야 함:
- 운영체제가 추가 프로세스를 수용할 수 있는 시점
- 어떤 Job을 수락하여 프로세스로 전환할 것인지: FCFS. Priority 예상 실행 시간, I/O 요구사항
중기 스케줄링(Medium-Term Scheduling)
스와핑(Swapping) 기능의 일부.
다중 프로그래밍의 정도를 줄이기 위해, 프로세스를 메모리에서 스왑-아웃
- 일정 시간 동안 비활성 상태였던 프로세스
- 우선순위가 낮은 프로세스
- 페이지 폴트가 자주 발생하는 프로세스
- 메모리를 과도 사용하는 프로세스
스왑 인(Swap In)
- 더 많은 메모리 사용 가능 할 때
- unblocked 되어서 더 이상 자원을 기다리지 않을 때
단기(Short-Term, CPU) 스케줄링
가장 자주 실행되는 스케줄링
어떤 프로세스를 다음에 실행할지에 대한 결정
CPU 스케줄러가 수행
Ready Queue에 있는 프로세스들 중에서 하나를 선택하여 코어를 할당
준비 큐 정렬:, FIFO 큐, Priority Queue, Tree, Linked List
비선점(Nonpreemptive) & 선점(Preemptive)
결정 방식(Decision mode)
스케줄링 알고리즘이 언제 실행되는지를 정의
1. 비선점(Nonpreemptive)
일단 프로세스가 Running 상태가 되면, 다음 중 하나가 일어나기 전까지 계속 실행:
- 프로세스가 종료되거나
- I/O를 기다리기 위해 스스로 blocking될 때
2. 선점(Preemptive)
실행 중인 프로세스가 인터럽트될 수 있으며, Ready 상태로 이동 가능
Preempitive가 발생하는 경우:
- 새로운 프로세스가 도착
- blocked 상태 프로세스가 Ready 상태로 전환될 때 발생하는 인터럽트
(I/O 이벤트를 기다리던 우선 순위가 더 높은 프로세스가 Ready 큐로 돌아오는 경우)
- Clock Interrupt
선점 방식은 비선점 방식보다 오버헤드가 더 클 수 있지만, 하나의 프로세스가 CPU를 독점하는 것을 방지할 수 있다
디스패처(Dispatcher)
디스패처는 단기 스케줄러가 선택한 프로세스에게 CPU 제어권을 넘겨주는 역할
디스패처는 다음과 같은 이벤트가 발생했을 때 호출됩니다:
System Calls
신호(Signals, 예: 세마포어)
Clock Interrupt
I/O 인터럽트
디스패치 지연 시간: 한 프로세스를 멈추고 다른 프로세스를 실행 시작할 때까지 걸리는 시간
단기 스케줄링 평가 기준 (Short-Term Scheduling Criteria)
CPU 이용률(CPU Utilization)
CPU를 가능한 한 바쁘게 유지하는 것
처리량(Throughput)
단위 시간당 완료된 프로세스의 수
반환 시간(Turnaround Time)
하나의 프로세스를 완료하는 데 걸리는 전체 시간
프로세스가 제출된 시점부터 종료될 때까지의 시간 간격
대기 시간(Waiting Time)
프로세스가 Ready Queue에서 기다린 총 시간
응답 시간(Response Time)
사용자가 요청한 후 시스템이 응답을 시작할 때까지 걸리는 시간
스케줄링 알고리즘 (Scheduling Algorithm)
CPU 스케줄링(CPU Scheduling)
Ready Queue에 있는 프로세스들 중에서
어느 프로세스에 CPU 코어를 할당할지를 결정하는 문제를 다룹니다.
최적화 기준 (Optimization Criteria)
CPU 이용률 최대화 (Max CPU utilization)
처리량 최대화 (Max throughput)
반환 시간 최소화 (Min turnaround time)
대기 시간 최소화 (Min waiting time)
응답 시간 최소화 (Min response time)
(1) FCFS 스케줄링
가장 단순한 비선점(Nonpreemptive) CPU 스케줄링 정책
CPU를 먼저 요청한 프로세스에게 먼저 CPU를 할당합니다.
FIFO(First-In, First-Out) 큐를 사용하여 간단하게 구현할 수 있습니다.
현재 실행 중인 프로세스가 자발적으로 실행을 멈추면,
Ready Queue에 가장 오래 있었던 프로세스가 선택되어 실행됩니다.
Average waiting time : 17
Average turnaround time: 27
Average waiting time: 3
Average turnaruound time: 13
호위 효과(Convoy Effect):
짧은 작업이 긴 작업 뒤에 줄 서서 오래 기다리는 현상
예: 하나의 CPU-bound 프로세스와, 여러 개의 I/O-bound processes가 있는 상황
FCFS는 CPU-bound 프로세스에 유리하고,
I/O-bound 프로세스에는 불리하게 작용
그 결과, 프로세서와 I/O 장치 모두 비효율적으로 사용되는 문제가 발생
(2) SJF 스케줄링
SJF = SPN(Shortest Process Next)
다음 CPU burst time이 가장 짧은 프로세스를 선택하는 비선점형(Nonpreemptive) 정책
CPU가 사용 가능해지면, 다음 CPU burst 시간이 가장 짧은 프로세스에게 CPU를 할당합니다.
만약 같다면 → FCFS스케줄링을 사용
Average Waiting Time: 7
Average Turaround Time: 13
장점:
- SJF 스케줄링 알고리즘은 수학적으로 Optimal임이 입증됨 → 평균 대기 시간을 최소화
- 응답 시간이 크게 향상됨
단점:
- 다음 CPU 버스트 길이를 알 수 있는 방법이 없으므로
각 프로세스 필요 처리 시간을 예측해야 함
- Starvation(특정 프로세스가 CPU를 오랫동안 할당받지 못해 실행되지 못하고 계속 대기하는 상황) 발생 가능
→ 짧은 작업들이 계속 들어오면 긴 작업은 오랫동안 대기하게 됨
- 선점이 없기 때문에 시분할 시스템에는 적합하지 않음
SJF 스케줄링을 근사적으로 구현하기
다음 CPU 버스트의 길이를 예측하여 SJF 스케줄링을 흉내낼 수 있습니다.
다음 CPU 버스트는 이전 CPU 버스트들과 유사할 것이라고 가정합니다.
따라서, 예측된 CPU 버스트 시간이 가장 짧은 프로세스를 선택합니다.
CPU 버스트 예측 방법
다음 CPU 버스트 길이는
이전 CPU 버스트들의 측정값을 기반으로 한 지수 평균으로 예측
t(n): 실제로 측정된 n번째 CPU 버스트의 길이
τ(n): 이전까지 예측한 n번째 CPU 버스트 길이
τ(n+1) : 다음 CPU 버스트에 대한 예측값
α: 0과 1 사이의 가중치 계수
가 1에 가까울수록 → 최근 값을 더 반영, 가 0에 가까울수록 → 과거 평균을 더 반영
예측 공식
τ(n+1)=α⋅t(n)+(1−α)⋅τ(n)
When 최근 값은 전혀 반영되지 않음
When α=1 가장 최근 값만 반영됨
α와 (1−α)는 둘 다 1 이하의 값이므로, 각 항(term)은 앞 항보다 가중치가 작아짐 → 최근 데이터에 더 큰 비중을 둠
(3) SRTF(Shortest Remaining Time First) 스케줄링
SRTF 스케줄링은 잔여버스트 타임이 가장 짧은 프로세스를 우선적으로 선택하는 선점형 스케줄링 정책
SJF의 선점형(Preemptive) 버전, SJF처럼 burst-time을 예측해야 함
잔여 처리 시간이 가장 짧은 프로세스를 항상 선택
→ 실행 중인 프로세스보다 더 짧은 잔여 시간을 가진 새 프로세스가 오면,
실행 중인 프로세스를 선점하고 새 프로세스로 교체
장점
우수한 Turnaround Time
→ 짧은 작업이 즉시 처리되어 전체 처리 시간이 줄어듦
→ 긴 작업 도중에도 짧은 작업이 오면 즉시 선점
단점
- 실행된 시간을 지속적으로 기록해야 하므로 오버헤드(overhead) 발생
- 긴 작업은 계속 선점당해서 기아현상이 발생할 수 있음
SJF
Average waiting time : 7.75
Average turnaround time: 14.25
SRTF
Average waitimg time : 6.5
Average turnaround time: 13
(4) RR 스케줄링
버스트 타임이 타임 퀀텀보다 긴 경우,
인터럽트를 발생시켜 컨텍스트 스위치를 수행하고 다음 프로세스로 CPU를 넘기는 선점형 스케줄링 정책
FCFS의 선점형(preemptive) 버전
각 프로세스는 Time Quantum을 할당받음 (보통 10~100밀리초)
Ready Queue는 원형 큐로 취급됨
CPU 스케줄러는 큐를 순차적으로 돌며, 각 프로세스에 최대 1개의 time quantum만큼 CPU를 할당함
CPU 버스트 시간이 time quantum보다 짧을 경우:
프로세스가 자발적으로 CPU를 반납하고 스케줄러는 다음 프로세스로 진행
CPU 버스트 시간이 time quantum보다 길 경우:
타이머가 동작하여 운영체제에 인터럽트 발생 context switch 수행
해당 프로세스는 레디 큐의 뒤로 이동하고 스케줄러는 다음 프로세스를 선택
RR (When Time Quantum = 4)
Average waiting time: 5.66
Average turnaround time: 15.66
SJF
Average waiting time: 3
Average turnaround time: 13
보통 SJF보다 turnaround time과 waiting time이 더 길지만, response time은 더 우수
RR 성능은 타임 퀀텀의 크기에 크게 의존
타임 퀀텀이 너무 크면 → FCFS처럼 동작
타임 퀀텀이 너무 작으면 → 잦은 context switch로 오버헤드가 커짐
타임 퀀텀은 컨텍스트 스위치 시간보다 충분히 커야 함 그렇지 않으면 오버헤드가 지나치게 증가함
* 타임 퀀텀 당 컨텍스트 스위치가 일어나는데, 타임 퀀텀은 (+), 컨텍스트 스위치는 (-)
전체 CPU 버스트의 80%는 타임 퀀텀보다 짧아야 한다.
우선순위 스케줄링
우선순위가 가장 높은 프로세스에게 CPU를 할당하는 스케줄링 정책
(숫자가 작을수록 우선순위가 높음)
선점형 / 비선점형으로 운영 가능
같은 우선순위 FCFS(선입선출) 방식으로 처리
SJF(Shortest Job First)도 우선순위 기반 알고리즘의 일종 (우선순위는 다음 CPU 버스트 시간의 역수)
Proiority Scheduling (Non-Preempitive)
Average waiting time: 8.2
Average turnaround time: 12
SJF
Average waiting time: 3.2
Average turnaround time: 7
문제: 낮은 우선순위 프로세스를 무한히 대기시키는 기아현상을 초래할 수 있다
해결: 에이징(Aging) - 오랫동안 기다리는 프로세스의 우선순위를 점차 높여주는 방식
Prority Scheduling with Round-Robin
- Execute the highest-priority process
- Runs process with the same priority using round-robin scheduling
Average wait time = 13.8
Average turnaround time = 19.2
SJF
Average wait time = 8.2
Average trunaround time = 13.6
Multilevel Queue
우선순위마다 별도의 큐를 사용, 가장 높은 우선순위 큐에 있는 프로세스를 먼저 스케줄링
Multilevel Feedback Queue
프로세스가 여러 큐 사이를 이동할 수 있도록 하는 방식 → 에이징(Aging) 기법을 이런 방식으로 구현
다음과 같은 파라미터들로 정의:
- 큐의 개수
- 각 큐에 사용할 스케줄링 알고리즘
- 상위 큐로의 승격기준
- 하위 큐로의 강등기준
- 어느 큐에 들어갈지 결정하는 기준
