[OS] CPU 스케쥴링

CPU 스케쥴링
멀티프로그래밍 상에서는 CPU는 순서에 대한 규칙을 가지는 것은 필수!
이러한 CPU의 이용률을 최대화하는 것이 목적!

메모리에 적재된 프로세스들 사이에서 프로세스를 선택하는 것
- 실행을 ready 단계에 있거나 CPU가 프로세스에 할당된 애들만!

다음 프로세스를 정하는 데 규칙을 어떻게 둘 것인가?
- 프로세스들을 링크드리스트? 이진 트리 방식으로 순서를 처리할까?
- FIFO(First In First Out) : 먼저 온 프로세스가 먼저 나간다.
- 우선순위 큐 : 규칙?! 프로세스의 우선순위를 두는데 필요한 규칙을 정해줘야 한다.

선점 VS 비선점 방식
비선점 방식 스케쥴링
CPU가 대기 상태나 종료상태가 되기 전까지 실행중인 프로세스를 계속 유지하는 방식
선점 방식 스케쥴링
스케쥴러에 의해서 CPU가 실행하는 프로세스를 변경한다.

CPU 스케쥴링을 위한 결정
1. 프로세스가 running -> waiting
2. 프로세스가 running -> ready
3. 프로세스가 waiting -> ready
4. 프로세스가 종료

1, 4 : 딱히 할 수 있는 게 없다 -> 비선점
2, 3 : 끼어들 수 있다. -> 선점

dispatcher : CPU이 코어의 제어를 줄 수 있는 그런 모듈
- CPU 스케쥴러에 의해서 프로세스가 선택될 수 있음을 하드웨어 단계에서 보장한다.

디스패쳐가 하는 일?
1. 프로세스가 다른 프로세스로 문맥 변환을 할 수 있게 해준다.
2. 유저 모드로 변환!
3. 유저 프로그램으로 올바른 위치로 돌아올 수 있게 해준다.

디스패처에게 제일 필요한 요소 -> 속도!
모든 문맥 변환(context switching)이 동안 디스패처가 할 일이 일어나기 때문에 속도가 필요하다.
즉 디스패서 지연시간은 하나의 프로세스를 멈추고, 다른 프로세스의 running을 시작하는 사이에 들어가는 시간

시사점
1. CPU 이용률 : CPU는 놀면 안 된다.
2. 처리량 : 단위 시간마다 완료되는 프로세스의 양
3. Turnaround time : 프로세스를 실행함에 있어서 얼마나 오래 걸리냐? 요청받은 시간부터 처리하는 시간까지를 해야한다.
4. 대기 시간 : 프로세스가 ready queue에서 기다리는 시간 
5. 응답 시간 : 응답을 시작하는 데까지 걸리는 시간

다시 돌아가서 CPU 스케쥴링 문제
- ready queue안에 프로세스를 무엇을 고를 것이냐!
1. FCFS(First Come First Served)
- 온 순서대로 처리한다. 제일 간단하다.
- 프로세스는 CPU가 할당된 순서대로 처리를 한다. FIFO Queue을 사용을 해서 쉽게 구현한다.

2. SJF(Shortest job first)
- 제일 짧은 시간을 가진 프로세스를 제일 먼저 처리를 한다.

3. RR(Round Robin)

4. 우선순위를 기반으로 한 큐잉