Process Scheduling
- CPU위의 Process를 빠르게 바꾸는 것을 말한다.
Context Switch
- CPU가 다른 Process로 바꿀때, System은 반드시 현재 Process 상태를 PCB에 저장해야하고, 다음 Process의 상태를 PCB에서 로드해야한다.
Context Switch가 일어날 때 발생하는 Overhead
1. Ready Queue에서 프로세스를 탐색하는 비용
2. PCB에 현재 프로세스 내용을 저장하고, 다음 프로세스내용을 로드하는 비용
3. Interrupt나 System call로 유저모드에서 커널모드로 진입하고 나오는 비용
4. 현재 프로세스에서 사용한 Register들을 flush하고 다음 프로세스에서 사용되는 Register를 로드하는 비용
4. TLB를 Flush하는 비용
Scheduling Criteria
-
<높을 수 록 좋음>
CPU utilization: CPU의 바쁜 정도
Throughput: 수행을 완료하는 단위시간 -
<낮을 수록 좋음>
Turnaround Time: 프로세스가 수행을 완료하는 총 시간
Waiting Time: 프로세스가 Ready Queue에서 기다리는 총 시간
Response Time: 일이 처음 시작될 때 반응하는 시간
non-preemptive vs preemptive
non-preemptive: 비선점형 스케쥴링으로 프로세스가 종료되어야만 다음 프로세스가 실행된다. context switching의 오버헤드가 적다.
Preemptive: 선점형 스케쥴링으로 프로세스 실행중에 context-switching이 일어날 수 있다. context switching의 오버헤드가 크다.
FCFS/FIFO
- 가장 먼저 들어온 프로세스가 먼저 수행이 된다.
- Convey effect: waiting Time이나 Turnaround Time이 커질 수 있다.
Starvation
- 다른 Job이 계속들어와 Process의 수행을 막는 상황
SJF
-
가장 적은 일을 기대하는 프로세스를 우선적으로 고른다.
-
Waiting Time이 최소화 된다.
Starvation이 발생할 수 있다.
STCF
- SJF의 Preemptive버전
- Ready Queue에서 가장 수행시간이 적다고 기대하는 프로세스를 고른다.
RR
- FIFO를 따른다.
- time slice를 두어, preemptive하게 만든다.
Priority Scheduling
- 우선순위를 두어 프로세스를 선택한다.
- 우선순위가 높은 일만 들어오면, Starvation이 발생할 수 있다.
aging이나 priority boosting으로 해결한다.
priority inversion
우선순위가 낮은 프로세스가 공유자원을 사용하고 있고, 우선순위가 높은 프로세스가 CPU에서 공유 자원을 사용하려고 할 때, 우선순위가 낮은 공유자원의 사용이 끝날 때까지 Waiting상태에 들어간다. 하지만 이때 공유자원과 상관없고 우선순위가 중간인 프로세스가 들어오면 그 프로세스가 실행된다. 이때 우선순위가 높은 프로세스는 우선순위가 중간인 프로세스보다 우선순위가 높음에도 늦게 실행된다. 이를 priorty inversion이라 한다.
이를 해결하기 위해 PIP,PCP 스케쥴링을 사용한다.
PIP
- 같은 공유자원을 사용하려는 우선순위가 높은 프로세스가 접근하면, 우선순위가 낮은 프로세스의 우선순위를 우선순위가 높은 프로세스만큼 높여준다.
PCP
- 공유자원을 사용하려는 프로세스가 실행되면, 그 순간부터 우선순위를 매우 높여준다.
[참고] Operating Systems Three Easy Pieces/Remzi H.Arpaci-Dusseau/ CreateSpace Publishing
