프로세스는 일생동안 CPU burst와 I/O burst를 반복한다.
이때 프로그램마다 CPU 사용 시간이 다르므로, 자원의 효율적 관리를 위해 CPU 스케줄링이 필요하다.
프로세스의 특성 분류
-
I/O-bound process
: CPU 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
: many short CPU bursts -
CPU-bound process
: 계산 위주의 job
: few very long CPU bursts
CPU Scheduler & Dispatcher
누구에게 CPU를 넘겨줄지 고민하고, 실제로 넘겨준다.
-
Dispatcher
: 실제로 CPU를 넘겨주는 역할!
: CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다 (= 문맥 교환) -
CPU Scheduler : Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다
-
아래와 같은 프로세스 상태변화에서 CPU 스케줄링이 필요하다.
(1) Running -> Blocked (Ex. I/O 요청하는 시스템 콜)
(2) Running -> Ready (Ex. 할당시간 만료로 timer interrupt)
(3) Blocked -> Ready (Ex. I/O 완료 후 인터럽트)
(4) Terminate -
(1), (4) 는 nonpreemptive (강제로 빼앗는게 아니라 자진 반납)
-
(2), (3) 은 preemptive (강제로 빼앗음)
-
Sheduling Criteria
Performance Index (= Performance Measure, 성능 척도)
스케줄링 알고리즘의 적합성 판단 기준
시스템 입장
CPU가 얼마나 많은 일을 했느냐?
-
CPU utilization (이용률)
: 전체 시간 중에서 CPU가 일한 시간의 비율
: 높을수록 좋다 -
Throughput (처리량)
: 단위시간당 프로세스 처리량.
: 많을수록 좋다
사용자 입장
사용자가 기다리는 시간. 모두 빠를수록 좋다
-
Turnaround time (소요시간, 반환시간)
: 지금까지 걸린 전체 시간
: CPU 실제 쓴 시간 + CPU 기다린 시간 -
Waiting time (대기 시간)
: CPU를 쓰러 와서 기다린 전체 시간
: 줄 섰던 시간 다 합친거. CPU 쓰고 반납 후 I/O 처리하고 다시 기다린 시간들 다 합친 시간 -
Response time (응답 시간)
: 프로세스가 CPU를 쓰러 들어와서 최초로 CPU를 얻기까지 걸린 시간
: I/O 마친 후 Ready queue에 들어와서 최초로 CPU를 얻기까지의 시간
Scheduling Algorithms
FCFS (First-Come First-Served)
먼저 도착한 프로세스에게 먼저 CPU 준다. nonpreemtive
선착순으로 처리하며, 한 프로세스가 완료될 때 까지 다음 프로세스들은 기다린다.
- Convoy efffect (호위 효과)
: short process가 long process 때문에 오래 걸린다
: 먼저 오는 프로세스의 CPU 사용시간에 따라 Waiting time이 엄청나게 길어질 수 있다!
SJF (Shortest-Job-First) & SRTF (Shortest-Remaining-Time-First)
짧은 프로세스에게 먼저 CPU 준다.
optimal한 방법 = 대기시간의 평균이 모든 알고리즘 중 제일 짧다.
-
각 프로세스의 다음번 CPU burst time을 기준으로 스케줄링한다.
: CPU burst time이 제일 짧은 프로세스를 제일 먼저 스케줄!
: 일종의 priority scheduling -
Schemes
-
Nonpreemptive
: 일단 CPU 잡으면 해당 CPU burst 완료될 때까지 CPU를 preemption 당하지 않는다. -
Preemptive (Optimal)
: Shortest-Remaining-Time-First (=SRTF)
: 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가진 새로운 프로세스가 도착하면 CPU를 빼앗긴다
-
-
단점
(1) Starvation 발생 : CPU burst 긴 프로세스는 언제까지고 기다려야한다
(2) CPU burst time의 예측 : 다음의 CPU burst time을 정확하게 알 수 없고, 과거의 CPU burst time으로부터 추정만 가능하다.
Priority Scheduling
우선순위가 높은 프로세스에게 먼저 CPU를 준다
- smallest integer = highest priority
- preemptive와 nonpreemptive가 있다.
- 단점 : Starvation
- 해결 : Aging. 기다린 시간만큼 우선순위를 높여주는 방식으로 starvation을 해소한다.
RR (Round Robin)
실제 CPU 스케줄링에서 제일 많이 사용한다
타이머에 세팅된 시간동안 CPU 사용후 다음으로 넘겨주는 preemptive 방법
-
각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖는다.
: 할당 시간이 지나면 다음 프로세스에게 CPU 넘어가고, 만약 아직 작업이 끝나지 않았다면 다시 ready queue의 제일 뒤로 가서 줄 선다.
: 반복이 RR의 철학! -
n개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit인 경우
: 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다
: 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다! -
SJF에 비해 평균 대기 시간은 길지만, 응답 시간이 짧다
: time sharing 환경에서 큰 장점
: 단, long job과 short job이 섞여있을 때 좋다.
: 전체 프로세스의 burst time이 비슷한 경우 비효율적인 상황이 생길 수 있다! -
성능
: q large => FCFS
: q small => context switch 오버헤드가 커진다
Multilevel Queue
Ready queue를 여러 개로 분할하여, 여러 줄에서 대기한다.
-
Ready queue의 분할
(1) foreground (interative) : RR 스케줄링 알고리즘
(2) background (batch - no human interaction) : FCFS 스케줄링 알고리즘. 줬다 뺐었다 하는게 더 비효율적이니까! -
큐에 대한 스케줄링 필요
(1) Fixed priority scheduling :
(2) Time slice : 각 큐에 CPU time을 적절한 비율로 할당
Multilevel Feedback Queue
여러 줄에서 대기하는데, 프로세스가 다른 줄로 넘어갈 수 있다.
-
프로세스가 다른 큐로 이동 가능한 방식
: Aging을 이런 방식으로 구현할 수 있다.
: 큐의 우선순위는 위로 갈수록 높으며, 각 큐마다 파라미터를 정해야 한다. -
Multilevel-feedback-queue scheduler를 정의하는 파라미터
(1) Queue의 수
(2) 각 큐의 scheduling algorithm
(3) Process를 상위 큐로 보내는 기준
(4) Process를 하위 큐로 보내는 기준
(5) 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준 -
Multilevel Queue와의 차이점
: Aging을 사용, MQ와 달리 Starvation을 해소할 수 있다.
Multiple-Processor Scheduling
CPU가 여러개인 환경에서의 스케줄링
-
Homogeneous processor
: 큐에 한 줄로 세워서 프로세서가 알아서 꺼내가도록 한다
: 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우, 더 문제 복잡해짐 -
Load sharing (= Load Balancing)
: 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요
: 별개의 큐를 두는 방법 vs 공동 큐를 두는 방법 -
Symmetric Multiprocessing (SMP)
: 각 프로세서가 알아서 각자 스케줄링 결정
: 모든 프로세스가 균일한 일을 수행하는 경우엔 비효율적 -
Asymmetric multiprocessing
: 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 그에 따른다
Real-Time Scheduling
빨리 처리하는게 아닌, 데드라인 안에 끝내는게 중요한 시스템
-
Hard real-time systems
: 정해진 시간(데드라인) 안에 반드시 끝내도록 스케줄링 필요
: CPU 용량도 데드라인에 맞춰서! 오프라인으로 미리 스케줄링 해두고 시스템은 그에 따라가도록 한다. -
Soft real-time computing
: 일반 프로세스에 비해 높은 priority를 갖도록 한다
: 가능한 CPU 먼저 얻을 수 있게 처리
Thread Scheduling
-
Local Scheduling
: OS가 모르는 경우, 스레드에게 맡긴다
: User level thread의 경우 사용자 수준의 thread library에 의해 어떤 스레드를 스케줄할지 결정 -
Global Scheduling
: OS가 누구에게 줄지 미리 알고 있는 경우
: Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄할지 결정
Algorithm Evaluation
어떤 CPU 스케줄링 알고리즘이 제일 좋은가?
-
Queueing models
: 확률 분포로 주어지는 값들을 통해 각종 성능 index 값을 계산한다
: 단위시간 당 얼마나 CPU가 일을 하느냐, job의 분포 등을 기반으로 계산 -
Implementation (구현) & Measurement (성능 측정)
: 실제 시스템에 알고리즘을 구현 - 실제 작업 (workload)에 대한 성능을 측정하여 비교 -
Simulation (모의 실험)
: 알고리즘을 모의 프로그램으로 작성한 후 trace을 입력으로 하여 결과를 비교한다
