-
💻 [OS 오퍼레이팅시스템] #7 | Process Scheduling 1 | Long-Term, Medium-Term, Short-Term, FCFS, SJF, SPN, Rount-Robin, SRT, HRRNCS/OS 2022. 4. 17. 18:50
💻 프로세스 스케쥴링의 종류
- Long-Term Scheduling (job scheduler)
장기 스케줄러. 프로세스가 처음 생성됐을 때 제일 처음으로 관여.
어떤 프로그램이 프로세싱을 위해 시스템에 추가될지 말지 결정. (큐 적재)
어떤 직업이 시스템의 자원을 차지할 것인지 결정 (New에서 ready 큐로 들어갈지 말지, Exit)
- Medium-Term Scheduling (swapper)
중기 스케줄러. 어떤 프로세스들이 CPU를 할당받을 것인지 결정.
메인 메모리에 올라갈 프로세스의 수를 결정. 멀티프로그래밍 정도를 결정 (Blocked할지 말지)
- Short-Term Scheduling (CPU scheduler)
단기 스케줄러. 프로세서에 의해 실행될 프로세스를 결정.
프로세스에 CPU할당. CPU스케줄러인 디스패처에 의해 동작됨. (Running <-> Ready <- Blocked)
- 스케줄링 레벨 구조 그림
💻 스케쥴링 알고리즘
- Selection Function
선택함수. 레디 상태인 프로세스들 중에 어떤 프로세스를 다음 실행을 위해 고를 것인지. schedule() 함수 내 알고리즘
w : 시스템에서 지금까지 보낸 시간
e : 실행을 위해서만 사용한 시간
s : 프로세스가 마치기 위한 요구되는 서비스 타임(실제로는 끝나야 알지만, 통계내서 미리 안다고 가정)
ex.) max[W] -> FIFO : 가장 시스템에 오래 있던 거 선택
- Decision Mode
결정 모드. 선택함수의 Decision mode에 따라 다르게 동작
비선점 모드(Nonpreemptive) : 한번 프로세스가 running상태가 되면, 끝날 때까지 또는 블락될 때까지 계속 실행되게 내버려둠.
선점 모드(Preemptive) : 특정조건(선택함수 조건 만족, timer)에 따라 실시간으로 빼앗음. 실행중이던 프로세스는 OS에 의해 인터럽트 되고, ready상태가 됨. 프로세스 스위치가 빈번하게 발생
* Arrival time : 시스템에 들어온 시간
* Service time : 요구되는 소요시간(길이), require process time, processing time
* Turnaround time : 반환시간. 들어온 뒤, 종료될 때 까지의 시간(길이), [service time + 기다린시간] 또는 [종료시간 - 들어온시간]
service time과 turnaround time이 같으면 최적! 기다리지 않고 바로 실행된거니까
- 1️⃣ FIFO (Firtst In, First Out), FCFS
레디큐에서 가장 오래된 프로세스가 선택됨. FCFS (first-come-first-served)라고 부름
선택함수 : Max[w] -> w(시스템에서 보낸 시간) 최대인거 선택
결정모드 : Non-preemption -> 실행이 끝날 때 까지 기다림
장점 : 단순하고 구현이 쉽다. overhead X
단점 : 가장 오래된 프로세스가 우선시 되어서 공정하지는 않다. convoy effect발생 가능(lower burst time인 프로세스들이 계속 기다림)
- 2️⃣ SPN (Shortedst-Process-Next), SJF
service time이 가장 작은 것부터(빨리 처리되는 것부터). SJF (Shortest-Job-First)라고도 부름
선택함수 : min[s]
결정모드 : Non-preemption
장점 : turnaround time 관점에서 제일 성능 향상
단점 : starvation 발생 가능(longer 프로세스 계속 CPU 못받을수도). 각 프로세스의 required time 알아야 하는 것이 어려움.
required time을 이전에 수행했던 결과를 바탕으로 산술평균내도 되는데, 더 향상된 방법은 재귀적으로 구하는 방법이다 (하단)
- 3️⃣ Round-Robin
인터럽트 일어나면, 현재 실행중인 프로세스를 레디 큐에 넣고, 다음 실행될 job은 FCFS 기반으로 선택함 (FCFS + Timer slicing)
선택함수 : constant -> 그냥 앞에 있는거 택함
결정모드 : Preemption -> 할당량 다 쓰면 뺏음
time quantum 길이를 결정하는 것이 중요한 디자인 이슈.
-> 짧게 할수록 SPN과 비슷해지고, 핸들러 overhead 증가한다.
-> 길게 할수록 FIFO와 비슷해진다.
n개의 프로세스, 타임 퀀텀 길이 q일 때, 최악의 경우 (n-1)q time 기다린다.
- 4️⃣ SRT (Shortest-Remaining-Time)
SPN의 선점 버전. shortest expected remaining time인 프로세스를 선택함
선택함수 : min[s-e] -> 매번 계산해야해서 overhead증가
결정모드 : Preemption
장점 : SPN에 최적의 turnaround time 성능을 보여준다.
단점 : overhead가 커질 수 있고, starvation이 일어날 가능성이 있다.
- 5️⃣HRRN (Highest-Response-Ratio-Next)
Response Ratio(응답 비율)이 가장 높은 ready 프로세스 선택함
R = (q+s)/s = turnaround time / actual service time = (기다린시간+서비스시간) / 서비스시간
선택함수 : max[(q+s)/s]
결정모드 : Non-preemption
장점 : starvation 해결 (longer 프로세스도 시간 지나면 결국 CPU를 할당받을 수 있다.)
단점 : expected service time이 측정되어야하는데 알기가 어렵다.
'CS > OS' 카테고리의 다른 글