OS_ch6_CPU Scheduling

1. 기본 컨셉은?

 - 멀티프로그래밍을 하면서 최대로 CPU 활용을 하자!

 - CPU/IO 반복되는 Burst Cycle, 즉 하나의 자연현상(?) 인데, 스케줄링을 하면 응답속도가 빨라지고.. 그럼 멀티프로세싱이 가능해짐

 - CPU burst를 분산시키고 싶다.. 병렬처리 하고싶다.

1) CPU/IO cycle:

LDA 메모리에(레지스터에) 값을 로딩해라

ADD 레지스터 ++;

I/O 요청 : 디스크 컨트롤러가 I/O 처리

STA 레지스터에 값 저장

다시 I/O 반복...

=> 그냥 두개 반복되는게 프로그램의 일반적 현상이다...

2) CPU burst time histogram

cpu가 메모리 access 하는 빈도: 0~8msec 때 가장 높다. => time quantum을 여기까지 주면 되겠지요.

그때그때 다름. 적정 time quantum 알아내기 위해 시도 

3) CPU scheduler

1> running -> wait: I/O 들어왔을 때

2> running -> ready: Time Quantum 끝났을 때

3> wait -> ready: I/O 끝났을 때

4> terminates: 프로세스 종료되었을 때

1,4는 nonpreemtive(비선점, 바꾸지 않음. 즉 자기 시간 다 씀)

2.3은 preemtive(선점, 중간에 바꿔치기 될 수 있음)

4) Dispatcher

스케줄러가 CPU control 가지고 있다가 (short-term 스케줄러에 의해 선택된)Process에게 넘겨줌 : Dispatcher

스케줄러가 돌고 그 다음 프로세스가 돌기 전까지의 latency 있음.

2. 스케줄링하는 기준?

- CPU 활용도가 높고, 처리량이 좋고, 프로그램 수행시간이 짧고, 레디큐에서 기다리는 시간이 짧고, 사용자 응답시간이 빠른!!

3. 스케줄링 알고리즘들

1) FCFS(First Come, Fisrt Served) : 먼저 온 애가 제일 처음 큐에 들어감. 수행 시간 길어도 상관 없음, Time Quantum 개념 없음

2) SJF(Shortest Job Fisrt): CPU 수행시간 계산해서 가장 짧은 것 부터 먼저함.  가장 Ideal한 알고리즘 But.. 수행시간 예측 불가임

- 선점형: CPU Burst Time이 더 짦은 프로세스가 나타나면 스위칭! SRTF(Shortest Remaining Time First)

- 비선점형: 일단 CPU가 일을 시작하면 방해받지 않음

* CPU Busrt Time 측정 어려운 이유? 프로그램 코드는 여러 분기점(if-else)에서 달라지므로 수행시간 다양해짐

* Convoy Effect(군대 물자수송?):  긴 작업을 필요로 하는 프로세스는 계속 뒤로 밀리고 밀리고 밀리고... 결국 못하고 기아(Starvation)될수도..

3)Priority Scheduling:

- 정수(integer) 번호를 둬서 우선순위 정함, 0번이 가장 높음(스케줄러)

- SJF는 수행시간을 Priority로 한 스케줄링의 일종

 - 문제점: Starvation: 우선순위 낮은 애는 영영 못돈다 ㅜㅜ

 - 해결방법: Aging: 프로세스가 일을 해갈수록 나이를 먹는다(우선순위가 뒤로 밀림) 즉, 오래 기다린 애는 우선순위 높아짐

4)Round Robin(RR):

- Convoy Effect 막기위해서 FCFS에 Time Quantum 개념 도입한 것.

- 레디큐 크기가 n개이고 TimeQuantum이 q라면, 각 프로세스들은 CPU 시간의 1/n씩 가지고, (n-1)q이상 기다리는 프로세스는 없음

- q가 크면:FCFS처럼 되고, 응답속도 느리고, CPU 효율성 좋아짐

- q가 작으면: 스위칭 여러번 되는 되신에 오버헤드 많아져서 CPU 효율성은 떨어지고 응답속도 빨라짐. SJF효과가 나서 좋음

- higher average turnaround than SJF, but better response: 

-> 오버헤드 들어가서 느려짐, 사실 kernel mode에서 조금만 돌면 좋음!(지금은 거의 user:kernel 반반)

-> turnaround time: 프로세스 시작할때부터 종료될때까지 시간

5) Multilevel Queue

- 앞에선 대화형 프로세스 돌리고 뒤에선 배치 프로세스 돌림

- 대화형 : I/O 많다.. 배치형: CPU연산 많다..

- 대화형: RR방식으로! 배치형: FCFS 방식으로 해도 무리 없음. waiting 있어도 크게 상관 안함

- Time Quantum이 다른 여러개 큐를 씀. 큐들 사이에도 aging 일어남

4. Multiple- Processor Scheduling

- 여러개의 CPU 쓰는경우, 듀얼코어.. 쿼드코어..

- Homogeneous processors(듀얼코어, 쿼드코어)

- Heterogeneous processors(CPU와 GPU 서로 다른일함) 독립적임 (= Asymmetric multiprocessing)

5. Real-Time Scheduling

- Hard Real Time: 공유기, 스위치 등 수행시간 보장되어야 하는것. 중대한 일 수행해야함. 가령 미사일 발사시간 ㅋㅋㅋ이런겈ㅋㅋ

- Soft Real Time: 중요한 프로세스가 높은 우선순위를 갖게 해주는것. 

 * Realtime OS: WindRiver, GreenHills, Linuxworks

 * Dispatch Latency:

이벤트발생-> 인터럽트프로세싱 -> 디스패치지연(아까 슬립한애 깨워옴) -> 리얼타임프로세스실행 -> 이벤트에응답

6. Algorithm Evaluation 

 - 모델링 등으로 알고리즘 평가