1. CPU Scheduler
멀티 프로그래밍의 목표는 CPU 를 쉴새없이 돌리는 것을 생각하자.
I/O bound Program 은 많고 짧은 CPU burst 가 있고, CPU bound Program 은 적지만 긴 CPU busrst 가 있다. 그래서 아래 같은 그래프를 생각할 수 있다.
이런 프로세스들은 CPU 스케듈러에 의해 4가지 변화를 겪는다.
Running -> Waiting
Running -> Ready (interrupt 시)
waiting -> Ready (I/O 끝날 때, 근데 여긴 CPU 스케듈러니까 이 예는 적용 안됨)
Terminate
Ready -> Running 은 Dispatcher 가 하므로 로 논외로 하자.
여기서 2, 3 번째 변화를 시키지 않으면 non preemptive 라고 하고, 시키면 preemptive 이다.
Dispatcher : Ready -> Running 으로 바꿔야함. 그래서 Switching User Mode 가 가능하고, 기존에 계산하던 환경을 저장하고 새로운 프로세스의 환경을 불러와서 실행 프로그램의 재시작할 주소로 갈 수 있음.
Dispatch Latency : Dispatcher 가 scheduler 선택한 애를 cpu 에 올리기 위해 걸리는 시간. 기존꺼는 저장하고 새로운걸 올려야함.
CPU Scheduling 의 기준은 5가지.
1. CPU Utilization : CPU 를 최대한 돌린다.
2. Throughput : 일정 시간당 끝나는 프로세스의 갯수
3. Turnaround Time : 요청하고 끝날 때 까지 걸리는 시간. 메모리에 올라가는 시간에 아래의 Waiting Time 에, CPU 에서 계산되는 시간에, I/O 처리하는 시간 등을 다 더한 거.
4. Waiting Time : 가장 중요한 것. Ready Queue 에서 기다리는 시간. 만약 다시 Ready Queue 로 들어가면 또 세야함.
5. 응답시간 : I/O input 처리하는 시간까지 포함한 현실에서 뭐 요청하고 답 얻는데 걸리는 시간.
FCFS (First Come First Served)
사실상 큐. non preemptive 함.
시간 오래걸리는 애가 먼저오면 전체적으로 기다리는 시간이 증가하는 Convoy Effect 에 시달림
SJF (Shortes Jop First)
그래서 제일 짧은걸 먼저 하자 라는 테마.
하지만 제일 짧은 게 뭔지 알 수 없어서 예측만 할 뿐임.
non preemptive 하게 구현하면 현재 돌리는 프로세스 보다 더 짧은 애가 들어와도 안멈춤
preemptive 하게 구현하면 끊고 제일 짧은 애를 먼저함. SRTF (Shortest Remaining Time First)
예측의 경우 exponential average 를 사용.
p 는 예측값, t 는 실제 값.
waiting time 에 관해서는 preemptive SJF 가 최적해임
Priority Scheduling
각 프로세스에 우선도가 붙어서 우선도 높은거 먼저 함. (대개 int 값이 낮은게 우선도가 높음)
SJF 는 Priority Scheduling 의 일종임.
같은 우선도면 FCFS 로 함.
우선도는 내부적, 외부적으로 정해지는데, 딱히 정해진건 없음
높은 우선도가 계속 처리안되는 문제 ( starvation ) 이 있는데, Ready Queue 에 오래 있으면 우선도를 높히는 (aging) 으로 해결함.
RR (Round Robin)
FCFS 와 같은데 특정 시간이 지나면 Ready Queue 맨 뒤로 감.
특정시간을 너무 길게잡으면 FCFS 와 같아지고, 너무 짧으면 오버헤드가 심함.
SJF 보단 Turnaround Time 이 길지만, response time 은 낫다고 평가됨.
MultiLevel Queue
이를 조합해서 MultiLevel Queue 를 만들 수 있다. 여러 큐를 만드는 것이다.
그럼 큐들 간에도 조정이 필요한데, 명백한 우선순위를 두거나, cpu 시간 비율을 두거나 할 수 있다.
MultiLevel Feedback Queue
MultiLevel Queue 는 한번 정해지면 그 큐에서만 놀아야함. 이를 극복하기 위해 대두.
에를 들어 CPU 시간을 오래잡아먹으면 점차 낮은 순위의 queue 로 내릴 수도 있음.
2. Multi Processer Scheduling
하지만 멀티 프로세서에서 scheduling 은 더 복잡함. 프로세서마다 할 수 있는게 다르면 더 복잡하고, 어떤 프로세서만 I/O 같은거에 연결 되기도 함.
Asymmetric multiprocessing 은 하나에 코어 외에 나머지 코어는 user code 만 처리하게 하고, 하나의 코어가 scheduling, I/O, 시스템 데이터를 관리함. 데이터 공유를 안해도 되서 간단함.
Symmetric multiprocessing 에선 각 프로세스가 스스로 scheduling 을 함.
Ready Queue 는 공유일 수도 있고 개인별로 가질 수도 있음.
그런데 한 프로세스가 다른 프로세서로 마구 이동하면 캐시도 바꾸고 해서 비용이 큼. 그래서 Affinity, 즉 한번 프로세서에게 선택되면 거기서만 처리되도록 함. 완전히 종속되면 Hard Affinity, 아니면 Soft Affinity 라고 함.
이는 프로세스간에 거리, 같은 칩에 있는 유무에 따라 NUMA(Non Uniform Memory Access) 가 일어나기 때문.
비는 프로세서가 있으면 Soft Affinity 의 경우 Load Balancing 을 위해서 migration 을 실행함.
어떤 작업이 프로세서의 작업들의 양을 감독하고 재분배하면 Push Migration, 자기가 비면 옆에 바쁜 프로세서 일을 가져오는 방식이 Pull Migration. 이는 Affinity 로 얻는 장점이 줄어들지만 그래도 최대한 CPU 를 써야하니까 전체적으론 장점.
Memory Stall 은 메모리에서 정보 얻는데 걸리는 대기하는 시간임. 하드웨어에서 Dual Thread Core 을 지원하면 해결됨, 한 스레드가 대기중일 때 다른 스레드에서 일하고 이를 반복하면 전체적으론 계속 일하게 됨.
3. Real Time CPU Scheduling
반응 속도가 빨라야하는게 Real Time CPU 이다.
deadline 의 유무에 따라 Soft real time System, Hard real time System 으로 나뉜다.
반응 속도의 오버헤드 중 큰 요소인 Event Latency 는 Interrupt 발생부터 Service Routine 까지 걸리는 시간인Interrupt Latency 와 CPU 에 올려진 프로세스를 바꾸는데 걸리는 시간인 Dispatch Latency 두가지로 구성된다.
Dispatch Latency 는 실행되기 전에 빠꾸 당하는 Conflicts 와 dispatch 로 구성됨.
총 Response Interval = interrupt latency + dispatch latency + excution
Priority Based Scheduling
최대한 중요한거 먼저 처리해야하므로 preemptive Priority Based Scheduling 을 사용함.
이는 그러나 데드라인을 지킨다는 보장이 없음
그래서 Hard 버전이면 프로세스의 시간을 세개로 나눔.
t: 고정된 프로세스 처리 시간.
d: 데드라인
p : latency 를 고려한 길이. p 이후 바로 다음 프로세스가 실행되야함.
rate of periodic task 는 1/p.
일정한 짧은 period 로 프로세스가 실행되므로 데드라인이 보장됨
Rate Monotonic Scheduling
t/p 가 큰거부터 먼저처리.
p 가 작을 수록 데드라인의 주기가 짧을 것임. 그러면 p 가 짧은 애를 먼저하고 p가 긴걸 하는 애를 나중에 하면, 데드라인에 둘다 맞출 수 있게 됨. 애초에 둘다 불가능 한 경우는 원래 처리를 못하지만 말임.
그런데 CPU 사용량이 한정됨. 아래에서 N 은 proecess 갯수.
EDF( Earliest Eeadline First Scheduling )
데드라인이 가까운 것부터 처리.