[OS] 5. Process Scheduling
CPU Scheduler는 memory에 적재할 process를 선택하고 적재된 Process를 관리한다.
- running $\to$ waiting
- running $\to$ ready
- waiting $\to$ ready
- terminate
위 4개의 상황은 nonpreemptive한 상황이다.
preemptive vs nonpreemptive
preemptive는 미리 empty 즉 실행중인 Process를 중단시키고 새로운 process를 실행하는 것이다. nonpreemptive는 실행중인 process의 중단을 기다리는 것이다.
Dispatcher
dispatch는 실행중인 process의 정보를 PCB에 저장하고 다른 process의 PCB에서 정보를 불러오는 것이다. 이 과정에서 context switching이 포함된다. 이때 걸리는 시간을 dispatch latency라고 한다.
Process Scheduling
Scheduling Criteria
- CPU utilization
CPU를 최대한 busy하게 만드는 것. - Throughput
정해진 시간에 얼마나 많은 Process가 수행되는지에 대한 척도. - Turnaround time
한 process의 arrival time으로 부터 종료 시간까지 걸린 시간. - Waiting time
ready queue에서 한 process가 기다린 시간. - Response time
한 process의 arrival로부터 처음 running되기까지 걸린 시간.
CPU utilization과 throughput을 최대로, turnaround time, waiting time, response time을 최소화 하는 것이 scheduling의 목적이다.
이를 도식화하는 것이 Gantt Chart이다.
FCFS(First Come First Served)
처음 도착하는 process부터 실행하는 것. FIFO queue를 이용한다.
문제점으로 Convoy effect가 있다. 만약 burst time이 긴 process가 먼저 도착하면 burst time이 작은 process는 오랫동안 기다려야 한다. 이는 누가봐도 비효율적인 상황이다.
SJF(Shortest Job First)
burst time이 작은 순으로 process를 실행하는 것. 가장 이상적이지만 실행하기도 전에 burst time을 알 수 있는 방법은 없다.
Preemptive(Shortest Remaining Job First)
새로운 process의 burst time이 짧아 실행중이던 process를 ready로 돌려보내고 새로운 process를 실행하는 것.
Nonpreemptive
실행중인 process가 종료한 다음 burst time이 가장 짧은 process를 실행하는 것.
Burst time prediction
실행하지도 않고 process의 burst time을 알수 있는 방법이 없다고 했는데 예측은 가능하다. 이전의 process의 예측값과 실제 burst time의 interpolation을 하는 것이다. 이때 비율에 따라 다른 예측방식이 될 수 있다.
RR(Round Robin)
FCFS와 비슷하지만 일정한 time quantum을 두고 process를 계속 교체하는 것(preemption). 이를 통해 Convoy effect를 방지할 수 있다.
하지만 time quantum이 너무 크면 FCFS와 다를게 없어지고 너무 작으면 context switching이 많이 발생해 overhead가 될 수 있다.
Priority
Process에 priority를 두고 scheduling하는 것. 가장 높은 priority process부터 실행한다.
- Equal priority
FCFS와 같다. - Priority $\propto$ Burst time
SJF와 같다.
이 방식은 Starvation이 생길 수 있는데, 계속 높은 Priority의 process가 도착한다면 priority가 낮은 process는 계속 실행되지 못할 것이다. 해결방법으로 aging을 적용하는데 waiting time이 길어질수록 priority을 높여주는 방식이다.
MultiLevel Queue
Priority를 모두 검색하고 가장 높은 process를 탐색하는데 시간이 걸린다. 이를 위해 priority에 따른 queue를 나누어 효율적으로 탐색할 수 있다. Queue마다 다른 scheduling algorithm을 사용할 수 있는데 foreground는 RR, background는 FCFS처럼 사용할 수 있다. 시간 측면에서 queue마다 time slice가 주어진다.
MultiLevel Feedback Queue
Mutlilevel queue에 feedback이 추가된 것. queue간에 process의 이동이 가능하다.
이를 구현하기 위해서 다음 요소들이 필요하다.
- queue의 개수
- 각 queue에 대한 scheduling algorithm
- Process가 어느 queue에 들어갈지 결정하는 알고리즘
- 어떤 Process를 promote, demote할지 결정하는 알고리즘
Multiple processor Scheduling
여러 processor의 scheduling은 더 복잡하다.
processor간에 어떤 process를 실행할지, race condition, cache coherency 등 고려할 문제가 많다.
Assymetric Multiprocessing
master-slave 관계로 한 processor가 모든것을 결정한다.
Symmetric Multiprocessing
각 processor가 알아서 scheduling한다. 이때 job queue를 common queue를 사용하거나 private queue를 사용할 수 있다.
Common Ready queue
공용으로 사용하기 때문에 race condition이 발생할 수 있지만 locking 기법을 통해 방지할 수 있다.
Private queue
각 process의 queue간에 load balancing이 필요하다. 이를 위한 balancing algorithm이 필요하다. 이때 push migration, pull migration이 사용되는데 주기적으로 push, pull migration을 통해 load balancing을 한다. 하지만 이 방식은 processor affinity에 반하는 개념이다.
processor affinity
process간 이동에서 cache 교체비용으로 인해 시간이 소요되기 때문에 한 processor에서 계속 실행되는 것을 선호하는것.
memory stall
processor가 memory에 접근할 때 시간이 소요되는데 이를 memory stall이라고 한다. 이를 multithreaded processing core가 해결해준다.
processor 내부에 여러 core가 존재하고 하나의 core에도 여러 physical thread가 존재하는데, OS의 입장에서는 physical thread도 CPU로 인식된다.
Multi-threading
coarse-grained multithreading
중요한 event가 발생했을 때만 thread를 교체한다. memory stall의 영향이 있다.
find-grained multithreading(interleaving)
내 cycle마다 thread를 교체하며 실행한다. memory stall의 영향이 없다.
Real-time CPU scheduling
soft, hard로 나누는데 soft는 deadline 내에 실행을 지향하지만 hard는 필수적이다.
Real-time 실행을 방해하는 latency가 두가지가 있는데 interrupt latency와 dispatch latency가 있다.
Priority-based
각 process의 period의 inverse를 priority로 사용한다. soft real-time을 할 수 있다.
Rate-monotonic
preemption이 있는 priority based scheduling기법. 하지만 이 방식은 여러 process의 경우에 실패할 확률이 상당히 높다.
EDF(Earliest Deadline First)
Deadline을 하나의 queue에 놓고 다음 period를 priority로 실행하는 것.