- CPU burst: 프로세스가 CPU를 사용하여 작업 수행하는 단계
- I/O burst: 입출력 작업을 수행하는 단계
- 사용자 프로그램은 CPU burst와 I/O burst를 반복하며 실행됨
프로세스의 분류
- CPU bound process: CPU를 활용한 처리가 많은 프로세스
- I/O bound process: I/O 요청이 빈번해 CPU burst가 짧은 프로세스, 주로 사용자 interaction이 높은 경우
CPU 스케줄링이 필요한 이유
- CPU를 잠깐 사용하고 I/O 작업을 수행하는 프로세스가 많다. -> interaction한 작업에 적절한 응답 시간을 제공하고, 효율성과 성능 향상을 위해서
CPU Scheduling
- CPU scheduler
: 운영체제 안에서 스케줄링을 수행하는 코드 블럭
Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고름- Dispatcher
: CPU를 넘겨주는 코드 블럭
CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘김. context switch(문맥 교환)
CPU 스케줄링이 필요한 경우
non-preemptive
: 강제로 빼앗지 않고 자진 반납
CPU를 한번 줬으면 다 쓰고 자진 반납을 할 때까지 보장하는 방법, 비선점형.
다른 프로세스가 실행을 시작하기 위해서는 현재 실행 중인 프로세스가 종료되거나 대기 상태로 들어가야 함
- Running -> Blocked (예: I/O에 요청하는 시스템 콜)
: 프로세스가 실행 중인 상태에서 I/O 작업이 필요한 경우, I/O 요청을 위해 블록된 상태로 전환, 다른 준비 상태의 프로세스에게 CPU를 할당 - Terminate: 프로세스가 종료된 경우, CPU 반납
preemptive
: 강제로 빼앗음
선점형 스케줄링, 현대에는 대부분 비선점형
다른 프로세스가 실행해야 할 작업이 더 중요하거나 긴급할 경우, 현재 실행 중인 프로세스를 중단하고 CPU를 다른 프로세스에게 넘김.
- Running -> Ready (예: 할당시간 만료로 time interrupt)
: 할당된 CPU 시간이 지나면 타이머 인터럽트가 발생하고, 현재 실행 중인 프로세스는 CPU를 반납하고 다른 준비 상태의 프로세스에게 양도 - Blocked -> Ready (예: I/O 완료 후 인터럽트)
: 우선순위가 있는 스케줄링의 경우 우선순위에 따라 프로세스 할당 가능.
:현재 실행 중인 프로세스를 중단하고 CPU를 다른 프로세스에게 할당 가능
Scheduling Criteria
CPU 스케줄링 성능 척도
- 시스템 입장에서의 성능 척도
- CPU Utilization, 이용률
- 전체 시간 중 CPU가 실제로 작업을 처리한 시간의 비율을 높게 할수록 성능 good, CPU 자원을 최대한 활용할 수록 좋다.
- Throughput, 처리량
- 단위 시간 당 많은 작업을 처리할수록 성능이 좋다.
- 프로그램 입장에서의 성능 척도
- Turnaround time, 소요시간
- 프로세스가 시스템에 진입하여 완료될 때까지의 전체 경과 시간
- ready queue 대기 시간 + cpu 실행 시간 + i/o 시간
- Waiting time, 대기 시간
: 프로세스가 ready 상태에서 cpu를 할당받기를 기다리는 시간- Response time, 응답 시간
: 프로세스가 처음으로 요청을 시작한 후 시스템에서 첫 번째 응답을 받을 때까지 걸리는 시간
- 선점형 스케줄링의 경우 프로세스는 CPU를 여러 번 얻고 뺏기는 상황이 발생 - 이러한 성능 척도들이 중요하게 고려된다.
- time sharing : 여러 사용자가 시스템 자원 공유, CPU를 시간적으로 나눠서 각 사용자에게 할당 -> 짧은 응답시간은 시스템의 효율성을 높이고 사용자들에게 공평한 CPU 접근 기회
Scheduling Algorithms
FCFS(First-Come First-Served)
- 먼저 들어온 순서대로 처리
- 비선점형 스케줄링
- cpu를 오래 쓰는 프로그램이 먼저 오게 되면 계속 기다려야 하므로 비효율적
- Convoy effect: 작은 프로세스들이 큰 프로세스를 기다리는 동안 작은 프로세스들의 실행이 지연되고 평균 대기 시간이 증가하는 현상
SJF(Shortest-Job-First)
- CPU burst time 가장 짧은 프고세스를 가장 먼저 스케줄링하는 방식
- Nonpreemptive SJF(비선점):
- 프로세스가 CPU를 할당받으면 해당 프로세스의 CPU burst가 완료될 때까지 CPU를 선점받지 않음
- 프로세스가 한 번 CPU를 할당받으면 그 프로세스의 실행이 완료될때까지 다른 프로세스들은 wait
Preemptive SJF(선점형)
- 현재 실행 중인 프로세스의 남은 CPU burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면, CPU를 선점하여 더 짧은 프로세스를 실행
- 이는 현재 실행 중인 프로세스보다 더 짧은 작업이 도착하면 빠르게 작업을 전환하여 최소한의 대기 시간을 보장하는 방식
- Shortest-Remaining-Time-First(SRTF): 가장 짧은 시간이 프로세스를 우선적으로 실행
SJF의 단점 2가지
- SJF는 일종의 우선 순위 스케줄링
- 우선 순위는 예상되는 next CPU burst time이 낮은 순서로 높음
: 1. starvation 2. CPU 사용시간을 미리 알 수 없다는 점.
Priority Scheduling
- 우선순위가 높은 순서부터 낮은 순서의 프로세스 순으로 CPU 할당
- 발생 가능한 문제: Starvation
: 우선 순위가 낮은 프로세스가 계속해서 높은 우선 순위를 가진 프로세스에게 밀려 CPU를 할당받지 못하고 대기하게 된다.
=> Aging: 시간이 지남에 따라 우선순위 증가시킴
- 오랜 시간 동안 실행되지 못한 낮은 우선 순위의 프로세스의 우선 순위가 점점 상승하여 CPU를 할당받을 수 있는 기회가 증가
- Aging을 통해 프로세스의 우선순위를 조절 가능
다음 CPU Burst Time을 예측하려면?
- 과거의 CPU 수행 시간을 이용해서 추정할 수 밖에!
- 방법 1) 지수 평균 사용하기
- 새로운 추정 값 = (가중치 이전 추정값) + ((1-가중치)현재 burst time)
: 최근 값에 더 많은 가중치를 주는 방식으로 예측 -> 오래전 값 보다 최대한 최근의 값에 기반해서 추정하기 위함
RR(Round Robin)
- 각 프로세스가 동일한 크기의 할당 시간인 타임 퀀텀(Time Quantum)을 가지고 실행
- 할당 시간이 지나면 프로세스는 선점되어 ready queue의 맨 뒤로 가서 다시 줄을 섬
- 응답시간이 빨라진다는 장점
- 각 프로세스는 할당 시간만큼 CPU 번갈아가면서 사용, 프로세스가 CPU를 기다리는 시간이 감소
- n개의 프로세스가 ready queue에 있고 할당 시간이 q인 경우, 각 프로세스는 최대 q 시간 단위로 CPU 시간의 1/n을 얻음
- 어떤 프로세스도 (n-1)*q 이상 기다리지 않는다.
- 프로세스가 동등하게 CPU 시간을 나눠 사용하며, 프로세스간의 공정한 실행을 보장
각 프로세스는 최대 q 시간까지만 사용 가능
: 만약 프로세스는 CPU 사용 도중 타임 퀀텀이 만료되면 해당 프로세스는 준비 큐의 맨 뒤로 이동 -> 다른 프로세스에게 CPU 를 양보, 마지막 프로세스가 타임 퀀텀만큼 CPU 사용하고 나서 다시 첫번째 프로세스로 돌아가는 형식
- 큰 타임 퀀텀
: FCFS(First-Come First-Served) 스케줄링과 유사- 작은 타임 퀀텀
: 컨텍스트 스위치가 매우 빈번하게 발생하게 되어 오버헤드가 커지고 시스템 전체 성능이 저하될 수 있음
-> 적당한 타임 퀀텀의 크기를 선택하는 것이 중요
: 일반적으로 10-100 m/s 정도의 크기가 좋은 성능
일반적으로 SJF 보다 평균 turnaround time(소요시간)이 길지만 RR는 응답 시간은 짧다는 특징이 있음. 시간이 오래걸리는 job, 짧게 걸리는 job이 섞여 있을 때는 효율적이지만 모든 시간이 동일한 job만 있을 때는 비효율적.
📝 It's been waiting for you