SJF
- waiting time을 줄일 수 있다.
그런데 구현을 할 수 없다.
next CPU burst time을 절대 알 수 없다.(예측불가)
그래서 next CPU burst를 예측.
how?
과거에 CPU burst로 예측을 한다.( 지수적으로 )
그런데 이것을 매번 기록할 수 없다.
만약 현재 실행중인 프로세스에서 더 짧은 신규 프로세스가 오는 경우 어떻게 처리?
- 현재 job 끝나고? 먼저 들어온 것부터?
SRTF Scheduling
- Shortest-Remaining-Time-First(Preemptive)
새로 도착한 프로세스의 CPU burst time이 현재 실행중인 프로세스의 Remaining time보다 짧은 경우 실행
RR Scheduling
Round Robin(preemptive FCFS with time quantum)
주어진 시간만큼만 딱 처리한다.(10ms)
circular queue로 실행.
그런데, 만약 time quantum보다 더 큰 process인 경우라면?
-> 자발적으로 release
그 역인 경우 interrupt를 실행(context switch가 발생.)
- preemptive, 선점적이다.
dispatch latency발생.
context switch는 작을수록 좋은데, 또 너무 작으면 작업처리도 못함.
quantum이 너무 크면 의미 없다.
Priority-base Scheduling
priority를 각 process에 할당하고, highest priority를 먼저 처리한다.
(SJF가 그 중 하나)
starvation(indefinite blocking) 문제
low-priority는 무한히 대기할 수도 있다.
(priority가 작은 것들 때문에)
그래서, aging으로 priority를 증가시키자.
일반적으로 RR + Priority 혼합
MLQ Scheduling
각각의 priority에 해당하는 ready queue를 만들자.
Multi-Level Feedback Queue(MLFQ) Scheduling
priority가 낮은 것만 계속 실행되면, 다른 priority queue는 실행되지 못할 수 있다.
그래서 quantum으로 분리.(계층형)
quantum 8인데 못처리하면, 그 다음 quantum 16만큼 할당을 받는다.
실전 OS 모델.
그런데 실제로는 thread scheduling을 하는데, kernel thread로 관리한다.
user threads는 thread library가 관리하고, kernel에서는 user에서 요청온 API만 처리해주면 된다.(맵핑)
Real-Time(주어진 시간 내에 어떤 task 완료)OS
-
Soft real-time
critical real-time process가 반드시 그 시간안에 안끝남.
그런데, 그게 non-critical보단 빨리 처리되는 것은 guarntee.
(조금 패킷 놓쳐도 ok) -
hard real-time
task가 반드시 deadline안에 무조건 실행
