CPU 스케쥴링

CPU 스케쥴링은 크게 선점형, 비선점형으로 나누어져있다.
1. 선점형
=> 스케쥴러가 프로세스를 강제적으로 스위칭한다.
2. 비선점형
=> 프로세스가 실행이 끝날 때까지 기달린다.

1. CPU utilization : cpu를 가장 많이 사용하게 유지
2. Throughput : 단위시간 내 완료한 프로세스 수를 늘리자
3. Turnaround time : 도착하고 실행까지 걸린 시간
4. Waiting time : 큐에서 대기하고 있는 시간

ready queue에 있는 프로세스들 중 어느 프로세스에 CPU를 할당할 것인가가 CPU 스케쥴링 문제이다.

비선점형

1. FIFO

1. FCFS 먼저 온 사람을 먼저 처리해주겠다.
   => 아주 초창기 운영체제이다.
   ready큐를 FIFO 큐로 쉽게 구현
   평균 대기 시간이 길어질 수 있음
   
   P1은 도착하자마자 바로 시작했으므로 waiting time은 0이 된다.
   P2는 P1이 끝난시간 24에 바로 시작했으므로 waiting time은 24가 된다.
   P3는 waiting time 27이 된다.
   
   위와 반대로 순서만 바꼈는데도 Waiting time이 줄어들었다.
   이러한 효과를 호위 효과를 한다.
   긴 CPU busrt를 가진 프로세스에게 CPU가 할당되기를 다른 프로세스들이 기다린다.

2. SJF

2. SJF(Shortest Job First)

• 다음에 수행할 프로세스들 중 가장 짧은 CPU burst를 갖는 프로세스를 우선 선택
• 동일한 수행시간을 갖는다면 FCFS로 처리
  
  P4가 가장 짧게 끝나므로 먼저 수행
  P1는 그 다음 짧게 끝나므로 2번째로 수행 3초 -> 9초
  P3는 그 다음 짧게 끝나므로 3번째로 수행 9초 -> 16초
  P2는 4번째로 수행 16초 -> 24초
• 특징

1. 평균 대기 시간이 가장 작음
2. 다음 CPU burst의 길이 파악이 어려움 작업이 얼마나 걸릴지 CPU는 알 방법이 없음, 현실적이지 않음

3. HRN 스케쥴링

SJF 기법의 단점인 긴 작업과 짧은 작업 간의 지나친 불평등을 어느 정도 보완한 기법
비선점형 스케쥴링 기법

즉 서비스 받을 시간이 낮을 수록 우선순위가 높아진다.
서비스 받을 시간이 똑같다 하면 대기한 시간(오랫동안 기달렸다.)하면 우선순위가 높아진다.

1. 0초 => P1이외에 어떠한 잡이 없으므로 P1을 실행한다.
2. 2초 => 현재 P1이 할당되어 있고 P2가 큐에 대기한다. 비선점형이기에 계속 실행
3. 3초 => P1의 스케쥴이 끝나고 현재 남아 있는 P2를 할당한다.
4. 4초 => 비선점형이기에 P3를 큐에 대기한다.
5. 6초 => P4를 큐에 대기한다.
6. 8초 => P5를 큐에 대기한다.
7. 9초 => 현재 P2가 끝나고 남아있는 P3, P4, P5의 우선순위를 계산한다.
P3 => (9-4) + 4/4, P4 => (9-6)+5/5, P5 => (9-8)+2/2
P3 => 2.25, P4 => 1.6, P5 => 1.5 가장 높은 P3를 실행한다.
8. 13초 => 현재 P3가 끝나고 남아있는 P4, P5의 우선순위를 계산한다.
P4 => (13-6)+5/5, P5 => (13-8)+2/2
P4 => 2.4, P5 => 3.5, P5를 실행한다.
9. 15초 => 남아있는 P4를 실행한다.
10. 20초 => 모든 프로세스 종료

---

선점형

3. SRTF

SRTF (Shortest Remaining Time First)
SJF는 비선점형 알고리즘이다. SRTF는 선점형 SJF이다. 더 짧은 CPU burst를 가진 프로세스를 선점하게 된다.

1. 0초 => P1 이외에는 없으므로 P1을 실행한다.
2. 1초 => 현재 실행하고 있는 P1과 새로 들어온 P2를 비교하니 P2가 더 작다. P2로 컨택스트 스위칭 해준다. (P1 = 7, P2 = 4)
3. 2초 => 현재 실행하고 있는 P2와 새로 들어온 P3를 비교하니 여전히 P2가 더 작다. 그대로 유지한다. (P1 = 7, P2 = 3, P3 = 9)
4. 3초 => 현재 실행하고 있는 P3와 새로 들어온 P4를 비교하니 여전히 P2가 더 작다. 그대로 유지한다. (P1 = 7, P2 = 2, P3 = 9, P4 = 5)
5. 5초 => 현재 실행하고 있는 P2가 종료 되었다. 큐에 있는 시간중 짧은 것을 실행시킨다. (P1 = 7, P3 = 9, P4 = 5)
6. 10초 => 현재 실행하고 있는 P4가 종료 되었다. 큐에 있는 시간 중 짧은 것을 실행시킨다. (P1 = 7, P3 = 9)
7. 17초 => 현재 실행하고 있는 P1이 종료 되었다. 큐에 있는 시간 중 짧은 것을 실행시킨다.
8. 26초 => 모든 프로세스 끝

칸트 차트로 그리면 위 이미지같이 된다.

4. 우선순위 스케쥴링

• 각 프로세스에 우선순위 지정
• 가장 높은 우선 순위를 가진 프로세스에게 CPU 할당
  (선점형 vs 비선점형) 둘 다 가능
  일종 우선순위 스케쥴링
• FCFC : ready 큐에 들어온 순서
• SJF : CPU burst의 길이
• SRTF : 잔여 CPU burst의 길이
  
  먼저 도착한 것이 누구인지, 가장 짧은 남은 시간이 누구인지 중요한 것이 아니라 Priority를 보고 구한다.
  
  간트 차트를 그리면 다음과 같다. 해당 작업은 비선점형이다.
  문제점
  기아/무한봉쇄 => 낮은 우선순위의 프로세스들이 무한히 대기
  해결책 => 에이징(오래도록 처리하지 못하고 남아있는 프로세스에 대해 점진적으로 우선순위를 올려주는 기법) 점점 우선순위가 올라감, 오래기달리면 우선순위가 올라가 낮은 우선순위도 실행됨

5. RR(Round Robin)

시분할 시스템을 위해 설계됨

• 규정 시간량, 각 프로세스에게 한 번에 할당되는 CPU시간이 있고 이 시간이 만료되면 다음 프로세스 할당
• 비선점형이 될 수 없다. 무조건 선점형, 규정 시간이 지나면 무조건 넘겨야 하기 때문이다.
• 일반적으로 평균 대기 시간이 길다.
• 사용자 응답성을 높이는 알고리즘이다.
• 빠르게 처리되는 알고리즘은 아니다.
• time quantum이 길면 FCFS가 될 것이고 too short하면 프로세서 공유
  
  
  
  시간 할당량은 컨텍스트 전환 시간보다 어느 정도 커야지 의미 있어진다.

6. MLQ(Multilevel Queue Scheduling)

ready큐를 하나의 큐로 구성하는 것이 아닌 다수의 독립적인 큐로 분류하여 구성

• 우선순위를 가진 큐이다.
  
  프로세스에 걸맞는 큐에 각각의 프로세스를 할당하는 방법이다.
  예를 들어 서버상 서비스를 제공하는 프로세스는 가장 높은 데 할당해주고
  학생 프로세스는 가장 낮은데 할당해준다. 중요도가 높은 프로세스가 먼저 처리해주는 스케쥴링이다.
  각 프로세스마다 고유의 스케쥴링 방법이 있다.
  문제점은 가장 낮은 프로세스에 있는 프로세스는 기아문제가 발생할 수 있다.

7. MLFQ(Multilevel Feedback Queue Scheduling)

MLQ와 같지만 다른 점은 MLQ는 프로세스가 더 높은 우선순위 레벨 큐로 올라가지 못한다. 하지만 MLFQ은 다른 레벨 큐에 옮길 수 있다.