CPU, I/O Burst
Program 실행 시 CPU Burst와 I/O Burst가 번갈아가며 진행
Program 따라 Burst 비율이나 진행 양상이 다르다.
따라서 CPU Scheduling이 필요.
결국 CPU를 어떤 Program에게 뺏고 줄 것인가?
선점형, 비선점형 스케줄링
Non-preemptive : CPU 할당 시 CPU를 다 쓰고 자진반납 때까지 사용을 보장
Preemptive : CPU 할당 시 강제로 빼앗기 가능 (timer interrupt 등으로, 일반적인 방식)
스케줄링 성능 척도 (Scheduling Criteria)
시스템 입장의 성능 척도
CPU utilizaition (이용률)
: 전체 시간 중 CPU가 놀지 않고 일한 시간의 비율
Throughout(처리량)
: 전체 시간 중 처리한 작업의 양
프로그램 입장의 성능 척도
Turnaround time (소요시간, 반환시간)
: CPU 사용 대기부터 I/O burst 전까지의 시간
Waiting Time(대기시간)
: 처음 대기 시간 + CPU Burst 중에 CPU 뺏겨서 Ready Queue에서 기다린 시간
Response Time(응답 시간)
: 처음 CPU 얻을 때 Ready Queue에서 기다린 시간
중국 음식 레스토랑의 예시
고용인 입장(시스템 입장)에서
- 주방장이 전체 노동 시간 중에서 몇 시간 일하는지(이용률)
- 몇 건의 주문을 받는지(처리량)
사용자 입장에서는
- 음식이 나와서 다 먹고 나갈 때 까지(반환시간)
- 코스 요리를 다 먹을 때까지 총 기다린 시간(대기 시간)
- 처음 먹을 게 나온 시간까지(응답 시간)
CPU Scheduling Alogorithm
FCFS (First-Come First-Served)
- 먼저 들어온대로 처리
- 비선점형 (CPU 뺏기 불가능)
- 비효율적 (시간 많이 걸리는 Process 하나로 이후 시간 적게 걸리는 Process 모두 오래 걸림 : Convoy Effect)
SJF (Shortest Job Firtt)
- 시간 짧은 순서대로 처리
- 더 짧은 Process가 오면 CPU 뺏을지(Preemptive) 말지(Non) 두 가지 존재
- 평균 대기 시간이 가장 짧음 (Preemptive 방식이 Optimal)
- Starvation 문제 발생 (시간 긴 Process는 시작 안될수도)
- 사실 실제 시간이 얼마나 필요한지 알 수도 없음 (과거 기준으로 예측은 가능)
Priority Scheduling
- 우선순위(정수)가 높은 Process 먼저
- SJF는 일종의 Priority Scheduling이다. (우선순위가 CPU bursttime)
- SJF와 비슷한 문제가 있다. (우선순위 큰 Process가 지나치게 오래 기다릴 수도)
- 기다리는 시간이 본인이 사용하는 시간만큼 비례해서 증가함
- 해결책
- Aging (노화)
오래 기다리는 Process의 우선순위를 조금씩 높여준다 - Round Robin
CPU 할당 시 동일 시간(Q) 부여, 끝나면 ready Queue 후순위로
응답 시간이 빨라진다(모든 Process가 조금만 기다리면 CPU 잠시 사용 가능)
짧은 Process 빠르게 종료 가능
Q가 크면 사실상 FCFS
- Aging (노화)
Multilevel Queue
- 우선순위가 다른 여러 개의 Queue 설정!
- 하위 우선순위 Queue는 Starvation 발생 가능
- 해결책
Queue의 성질에 따라 알고리즘을 다르게 적용
Queue에 대한 스케줄링이 필요 (Fixed priority / 시간 할당량 조정)foreground(interactive) : RR (응답시간 적게, 사용자 편의 개선)
background : FCFS (Context Switch Overhead 감소)
Multilevel Feedback Queue
- Multilevel Queue와 같지만, Process가 Queue 사이에서 우선순위 승격, 하락 가능
Multiple-Processor Scheduling
- CPU가 여러 개인 경우의 스케줄링
- Homogeneous Processor의 경우 : 순서대로 Processor가 할당
- Load Sharing : 특정 CPU에 업무가 몰리지 않도록 배분해야 함
- Symmetric MultiProcessing (SMP) :
각 프로세서가 각자 알아서 스케줄링 결정 - Asymmetric MultiProcessing :
한 프로세서가 업무 배분, 나머지 프로세서들은 그대로 업무 수행
Real-time Queue
- DeadLine의 존재
- Hard (무조건) - Soft (살짝 넘겨도 OK)
알고리즘 성능 평가
- Queueing Models
확률 분포로 주어지는 처리율 등의 계산을 통해 performance index값 계산 - Implementation & Measurement
실제 시스템에 알고리즘 구현하여 실제 작업에 대해 성능 측정 비교 - Simultaion
모의 실험 - 알고리즘을 모의 프로그램으로 작성, trace를 입력하여 결과 비교
