CPU and I/O Bursts in Program Execution
CPU burst
- CPU만 연속적으로 사용하면서 instruction을 행하는 단계
I/O burst
- I/O를 실행하는 단계
- 프로그램은 CPU burst와 I/O burst를 반복하며 실행된다.
- 프로그램의 종류에 따라 그 빈도나 길이가 다르다.
CPU-burst Time의 분포
I/O bound job
- CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요
- CPU를 짧게 쓰고, 빈도가 잦음. 중간에 I/O가 끼어드는 프로세스
CPU bound job
- 계산 위주
- CPU를 오래 쓰고, I/O작업이 빈번하지 않음.
- 이렇게 여러 종류의 프로세스가 섞여있기 때문에 CPU scheduling이 필요하다.
- 사람과 상호작용하는 프로세스인 I/O bound의 경우 적절한 응답을 제공해야하기 때문.
CPU Scheduler & Dispatcher
독립적인 HW, SW가 아니라 운영체제 내의 해당 기능을 하는 커널 코드이다.
CPU Scheduler
- Ready상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
Dispatcher
- CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다.
- 이 과정이 문맥 교환임.
CPU Scheduling이 필요한 경우
- Running -> Blocked (I/O 시스템콜)
- Running -> Ready (timer interrupt발생)
- Blocked -> Ready (I/O 작업 완료)
- Terminate
1, 4번 : CPU를 자진 반납하는 경우 (nonpreemptive)
나머지 경우 : CPU 제어권을 강제로 빼앗는 경우 (preemptive)
비선점형 스케줄링 Nonpreemptive Scheduling
- 프로세스가 CPU 제어권을 자진반납 할 때까지 CPU 제어권을 보장해주는 스케줄링
선점형 스케줄링 Preemptive Scheduling
- CPU 제어권을 강제로 빼앗는 스케줄링
- 대부분의 현대 스케줄링
시스템 입장에서의 CPU 성능 척도
-> CPU가 최대한 많이 일할 수록 좋음
CPU utilization 이용률
- keep the CPU as busy as possible
- 주어진 시간동안 CPU가 일한 시간
Throughput 처리량
- 주어진 시간동안 CPU가 완료한 작업단위
프로세스 입장에서의 CPU 성능 척도
-> 처리시간이 빠를 수록 좋음
Turnaround Time
- 한 프로세스가 CPU 제어권을 얻어 작업을 하고 CPU 작업을 마칠 때까지 걸린 시간(I/O 작업으로 넘어감)
Waiting Time
- CPU 제어권을 얻기 위해 ready 큐에서 기다린 시간 (여러 번 발생)
Response Time
- Ready 큐에 들어와서 CPU를 처음 얻을 때까지 걸린 시간
CPU Scheduling Algorithms
FCFS (First-Come First-Served)
- 비선점형 스케줄링에 해당
- 먼저 온 프로세스를 먼저 처리한다
- 효율성이 떨어진다.
SJF (Shortest Job First)
- CPU burst가 가장 짧은 프로세스에게 먼저 CPU 제어권을 주는 것
- 큐가 전체적으로 짧아져 everage waiting time을 최소화한다.
(1) Nonpreemptive한 방법 - 일단 한 프로세스가 CPU를 잡으면 CPU burst가 더 짧은 프로세스가 후에 나타나더라도 CPU 제어권을 자진반납할 때까지는 보장해줌
(2) Preemptive한 방법 - CPU를 잡더라도 CPU burst가 더 짧은 프로세스가 나타나면 CPU 제어권을 빼앗아 그 프로세스에게 넘겨줌
- SRTF Shortest Remaining Time First라고 한다.
SJF의 문제점
- Starvation 기아 현상
- CPU 사용 시간이 긴 프로세스는 영원히 CPU 제어권을 받을 수 없을 수도 있음.
- CPU 사용시간을 미리 알 수 없음
- I/O 작업 등이 얼마나 이루어질지 매 번 CPU 사용시간을 알 수 없음
Priority Scheduling
- 우선순위가 제일 높은 프로세스에게 CPU 제어권을 준다.
- preemptive, nonpreemptive 두가지 존재
- SJF도 우선순위 스케줄링의 일종이다. (우선순위 = CPU 사용시간)
- 역시 Starvation문제가 있기 때문에, Aging기법을 도입한다.
- Aging : 아무리 우선순위가 낮은 프로세스라고 하더라도, 오래 기다린다면 우선순위를 높여주는 것
Round Robin (RR)
- 각 프로세스는 동일한 크기의 할당시간(time quantum)을 가진다.
- 할당 시간이 끝나면 그 프로세스는 timer interrupt에 의해서 preemptive당하고 ready queue에 줄을 선다.
- 응답시간이 빨라진다는 장점이 있다. (response time, CPU제어권을 처음 얻는 시간이 짧아진다.)
- 대기시간이 해당 프로세스의 CPU 사용시간에 비례한다.
Multilevel Queue
- Ready queue를 여러 개로 분할
- 각 큐는 독립적인 스케줄링 알고리즘을 갖는다.
foreground queue
- interactive job
- RR
background queue
- batch (no human interaction) job
- FCFS
큐에 대한 스케줄링
1. Fixed priority scheduling
- 우선선위가 높은 줄이 비어있을 때에만 우선순위가 낮은 줄에 부여
- starvation 가능성 있음
2. Time slice
- 각 큐에 CPU time을 적절한 비율로 할당
Multilevel Feedback Queue
- CPU 사용시간의 예측이 필요 없음
Multiple-Processor Scheduling
- CPU가 여러 개인 경우
Homogeneous processor
- 큐에 한줄로 세운다
Load sharing
- 특정 CPU만 일하지 않도록 하는 매커니즘 필요
Symmetric Multiprocessing (SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
Asymmetric Multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 담당, 나머지 프로세서는 거기에 따름
Real-Time Scheduling
- 정해진 시간 안에 반드시 실행되어야 하는 job ; 반드시 deadline을 보장해주어야 함
Hard real-time systems
- 정해진 시간 안에 반드시 끝내도록 스케줄링 해야 함
Soft real-time computing
- 일반 프로세스에 비해 높은 우선순위를 갖도록 함
- 반드시 데드라인이 보장되는 것은 아님
Thread Scheduling
Local Scheduling
- User level Thread의 경우
- 사용자 프로세스가 직접 thread library에 의해 어떤 thread를 스케줄 할지 결정
Global Scheduling
- Kernel level thread의 경우
- 일반 프로세스와 동일. 커널의 스케줄러가 어떤 thread를 스케줄할지 결정
알고리즘 평가방법
Queueing models
- 확률분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index값을 계산
Implementation(구현) & Measurement(측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해 성능을 측정
Simulation (모의 실현)
- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
SAP