5. 프로세스 스케줄링
CPU Scheduling
프로세스의 특성 분류
- 프로세스는 그 특성에 따라 다음 두 가지로 나눔
- I/O-bound process
- CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 Job
- (many short CPU bursts)
- CPU-bound process
- 계산 위주의 Job
- (few very long CPU bursts)
- I/O-bound process
CPU Scheduler & Dispatcher
- CPU Scheduler
- Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
- Dispatcher
- CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다
- 이 과정을 Context switch(문맥 교환)라고 한다
- CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다
- Running → Blocked (ex) I/O system call)
- Running → Ready (ex) timer interrupt)
- Blocked → Ready (ex) I/O 끝나고 interrupt)
- Terminate
→1,4는 nonpreemptive(자진반납)
→나머지 preemptive(=강제로 빼앗음)
Scheduling Criteria
→Performance Index ( = Performance Measure, 성능 척도)
- CPU utilization (이용률)
- keep the CPU as busy as possible (CPU가 놀지않고 작업을 수행)
- Throughput(처리량)
of processes that complete their execution per time unit( 단위시간 당 수행한 작업 수)
- Turnaround time(소요시간, 변환시간)
- amount of time to execute a particular process (CPU를 사용하기 시작해서 I/O나 종료까지 걸린 시간의 총 합)
- 메모리 적재를 기다리는 시간, Ready 큐에서 대기 시간, CPU에서 실행시간, IO 시간의 총합
- Waiting time(대기 시간)
- amount of time a process has been waiting in the ready queue ( CPU 사용하기 위해 대기한 시간의 총합)
- Response time(응답 시간)
- amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment) (최초로 CPU를 사용하기까지 걸린 시간)
→ 이용률, 처리량 : 시스템 입장에서의 성능 척도
→ 소요시간, 대기시간, 응답시간 : 프로그램 입장에서의 성능 척도
Scheduling Algorithms
FCFS(First-Come First-Served)
- 먼저 오면 먼저 사용
ex) P1 - 24 , P2 - 3, P3 - 3
프로세스 도착 순서 P1, P2, P3
P1 = 0~24, P2 = 24~27, P3 = 27~30
→Average waiting time : (0 + 24 + 27)/3 = 17
- Convoy effect : short process behind long process
SJF(Shortest-Job-First)
- 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
- CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
- Two schemes:
- Nonpreemptive
- 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음
- Preemptive
- 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
- 이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부른다
- Nonpreemptive
- SJF is optimal
- 주어진 프로세스들에 대해 minimum average waiting time을 보장(preemptive 버전)
ex) Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF(non-preemptive)
P1 : 0~ 7 P3 : 7~8 P2 : 8~12 P4 : 12~16
Average waiting time = (0 + 6 + 3 + 7)/4 = 4
ex) Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
SJF(preemptive)
P1 : 0~2 P2 : 2~4 P3 : 4~5 P2 : 5~7 P4 : 7~11 P1 : 11~16
Average waiting time = (9 + 1 + 0 + 2)/4 = 3
→ long process가 Starvation(기아)상태에 빠질 수 있음
→실제론 CPU burst time을 알 수 없기 때문에 예측해야함
다음 CPU Burst Time의 예측
- 다음번 CPU burst time을 어떻게 알 수 있는가? (input data, brance, user...)
- 추정(estimate)만이 가능하다
- 과거의 CPU burst time을 이용해서 추정 (exponential averaging)
- Tn = actual length of nth CPU burst
- T(타우)n+1 = predicted value for the next CPU burst
- a , 0 ≤ a ≤ 1
- Define : Tn+1 = aTn + (1-a)T’n
Priority Scheduling
- A priority number(integer) is associated with each process
- highest priority를 가진 프로세스에게 CPU 할당 (smallest integer - highest priority)
- Preemptive
- nonpreemptive
- SJF는 일종의 priority scheduling이다
- priority = predicted next CPU burst time
- Problem
- Starvation(기아 현상) : low priority process may never execute
- Solution
- Aging(노화) : as time progresses increase the priority of the process
Round Robin (RR)
- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10-100 ms)
- 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다
- n 개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. → 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
- Performance
- q large → FCFS
- q small → context switch 오버헤드가 커진다
ex) Process Burst Time
P1 53
P2 17
P3 68
P4 24
- 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다.
Multilevel Queue
- Ready Queue를 여러 개로 분할
- foreground (interactive)
- background (batch - no human interaction)
- 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground - RR
- background - FCFS
- 큐에 대한 스케줄링이 필요
- Fixed priority scheduling
- server all from foreground then from background
- Prossibility of starvation
- Time slice
- 각 큐에 CPU time을 적절한 비율로 할당
- Eg., 80% to foreground in RR, 20% to background in FCFS
- Fixed priority scheduling
Multilevel Feedback Queue
- 프로세스가 다른 큐로 이동 가능
- 에이징(aging)을 이와 같은 방식으로 구현할 수 있다.
- Multilevel-feedback-queue scheduler를 정의하는 파라미터들
- Queue의 수
- 각 큐의 scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫓는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
Multiple-Processor Scheduling
- CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
- Homogeneous processor인 경우 (프로세스의 기능이 동일)
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
- Load sharing (부하 공유)
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
- Symmetric Multiprocessing (SMP, 모든 CPU가 대등)
- 각 프로세서가 각자 알아서 스케줄링 결정
- Asymmetric multiprocessing (하나의 CPU가 전체적인 컨트롤을 담당)
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
Real-Time Scheduling
- Hard real-time systems
- task가 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
- Soft real-time computing
- task가 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
Thread Scheduling
- Local Scheduling
- User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
- Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
Algorithm Evaluation
- Queueing models
- 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
- 예전에 많이 썼음
- Implementation (구현) & Measurement (성능 측정)
- 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
- 가장 정확하나 구현이 쉽지않음
- Simulation (모의 실험)
- 알고리즘을 모의 프로그램으로 작성후 trace를 입력으로 하여 결과 비교
Author And Source
이 문제에 관하여(5. 프로세스 스케줄링), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mraz0210/5.-프로세스-스케줄링저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)