Process Scheduling - Scheduler, Criteria, Scheduling algorithm, Multiple-processor

Process Scheduling

CPU Scheduler

- 메모리에 있는 실행할 준비가 된 Process를 선택해 CPU를 할당해줌

- CPU Scheduling은 4가지 경우에 일어날 수 있음

1) Running -> Waiting으로 상태가 변했을 때

2) Running -> Ready로 상태가 변했을 때

3) Waiting -> Ready로 상태가 변했을 때

4) Running -> Terminate로 상태가 변했을 때

- Dispatcher Module

-> short-term scheduler에 의해 선택된 프로세스에 대해 CPU 제어를 함

1) context switching이 일어났을 때

2) user mode로의 변환이 일어났을 때

3) 해당 프로그램을 재시작하기 위해 점프했을 때

Scheduling Criteria(기준)

1) CPU Utilization

- CPU의 이용률

2) Throughput

- 시간당 실행을 완료한 프로세스 수

3) Turnaround time

- 프로세스 완료 시간

4) Waiting time

- ready queue에 머무른 시간

5) Response time

- 요청 후 처음 Response가 올때 까지의 시간

Scheduling Algorithm

1) FCFS(First-Come, First-Serve)

- 먼저 도착한 프로세스 순으로 CPU를 할당하는 방법

- Process가 P1->P2->P3 순으로 들어왔을 때 들어온 순서대로 처리함

- Waiting time : P1 = 0, P2 = 10, P3 = 22

-> 만약 P1보다 CPU Burst Time이 더 짧은 P2, P3가 먼저 들어온다면 평균 Wating time이 감소한다.

Convoy effect

- 짧은 프로세스가 긴 프로세스보다 뒤에 처리되어 Waiting time이 길어져 CPU 이용률이 감소하는 현상

2) SJF(Shortest-Job-First)

- 도착한 프로세스 중 CPU Burst time이 가장 작은 프로세스를 먼저 처리하는 방법

- preemption과 non-preemption에서 다르게 작동함

1. preemption -> SRTF(Shortest-Remaining-Time-First)

- 수행되고 있던 프로세스가 있더라도 더 짧은 프로세스가 들어오면 현재 프로세스의 남은 시간이 더 길다면 새로운 프로세스로 CPU를 넘겨줌

- P1이 수행되던 도중 P2가 들어오는데 이 때 P1은 5가 남았고 P2는 4가 남았기 때문에 P2를 수행함

- P2 수행 도중 P3가 들어오지만 P2=P3이므로 그대로 P2 수행.

- P4가 들어왔지만 P3가 더 짧기 때문에 P3 수행

- P1의 남은 시간보다 P4가 더 짧기 때문에 P4를 수행하고 마지막에 P1을 수행함

2. non-preemption

- 더 짧은 프로세스가 오더라도 현재 수행중이라면 현재 수행중인 프로세스가 끝날때 까지 CPU를 넘겨주지 않음

- P1이 수행될 당시 다른 프로세스가 없기 때문에 P1이 수행되고 수행동안 다른 프로세스가 들어오더라도 끝날때 까지 계속함

- P1이 끝난 후에는 P2, P3, P4가 모두 들어와 있어 이때부터 가장 짧은 수행시간을 먼저함

- P2와 P4같이 같은 경우에는 먼저 들어온 프로세스 수행

- SJF의 단점 : Starvation이 일어날 수 있음

-> 긴 프로세스가 짧은 프로세스가 계속 들어오면서 수행될 수 없는 상태가 될 수 있음

-> 프로세스가 자원을 기다리고 있는 시간에 비례해 우선순위를 부여하는 Aging기법을 사용해 해결할 수 있음

3) Priority Scheduling

- 각각의 프로세스에 우선순위를 할당해 수행하는 방법

- 동적으로 priority를 부여하는 방법과 고정된 priority를 사용하는 방법이 있음

- 이 방법도 SJF와 마찬가지로 Starvation이 발생할 수 있고 마찬가지로 Aging 기법으로 해결 가능

4) RR Scheduling(Round-Robin)

- 특정한 시간(Time quantum)을 두어 해당 시간만큼만 수행 후 다른 프로세스에게 CPU를 주는 방법

- Time quantum이 큰 경우 FCFS와 같은 방식처럼 될 수 있고, 너무 작을 경우는 자주 일어나는 Context switching때문에 overhead가 커질 수 있음

- Time quantum = 5인 경우 5만큼 수행 후 다른 CPU에게 넘겨줌

- 계속 번갈아가며 수행함

5) Multilevel Queue

- 각 프로세스를 그룹에 따라 나눠 각기 다른 queue를 사용하는 방법

- Queue간의 우선순위를 나눔

6) Multilevel Feedback queue

- Multilevel queue와 마찬가지로 프로세스가 그룹에 따라 다른 queue로 나눠 우선순위가 생기지만프로세스들이 다른 큐로 이동할 수 있음

Multiple-Processor

1) Symmetric MultiProcessing(SMP)

- 모든 프로세서가 동등한 권한을 가지고 공유데이터를 가지고 있음

2) Asymmetric MultiProcessing   

- 하나의 마스터 프로세서가 나머지 프로세서에 작업을 할당함

- 마스터 프로세서만 시스템 데이터에 접근 가능

Process Affinity(친밀도)

1. Soft Affinity : Affinity가 약해 다른 프로세서로 이동이 가능

2. Hard Affinity : Affinity가 강해 해당 프로세서에서만 수행 가능. 이동 불가

Load Balancing

1. Push migration

- CPU Utilization을 모너티랑 하는 프로세스가 imbalance한 이용률을 보고 Load가 약한쪽으로 작업을 옮김

2. Pull migration

- CPU가 스스로 자신의 Load가 약하다고 생각하면, 다른 프로세서의 작업을 가져옴