CPU 스케쥴링

1. 기본 개념

1-1. CPU 스케쥴러

• 메모리에 있는 프로세스들 중 실행할 준비가 되어 있는 ready 상태의 프로세스를 선택하고 그 프로세스에 CPU 를 할당하는 것입니다.
• 전형적인 프로세스는 하나의 프로세스가 입출력 완료되기를 기다리고 그 이후에 실행되는 메커니즘입니다. 그럼 입출력을 기다리는 대기시간 내내 아무것도 하지 못한 채 놀고 있게 되어 이런걸 생산적으로 하기위해 나온 것이 CPU 스케줄링입니다.

1-2. CPU 스케쥴링의 결정

1. 한 프로세스가 실행 상태에서 대기 상태로 전환 될 때 (ex. 입출력 요청할 때)
2. 프로세스가 실행 상태에서 준비완료 상태로 전환 될 때 (ex. 인터럽트 발생 할 때)
3. 프로세스가 대기 상태에서 준비완료 상태로 전환 될 때 (ex. 입출력 종료됐을 때)
4. 프로세스가 종료 될 때

1 & 4의 경우
 > 비선점형

2 & 3의 경우
 > 선전형
 > 이 경우 가끔 정합성 이슈가 있습니다. 먼저 온 프로세스가 데이터 업로드를 진행중인데, 다른 프로세스가 CPU를 점유하게 되면 데이터 일관성을 보장하지 못합니다.

1-3. 스케쥴링의 기준

1. CPU 이용률
   • cpu를 가능한 바쁘게 유지
   • 단위는 % 이며, 40-90의 범위를 가져야한다 라는 내용도 있지만 실제 필드에서는 CPU 상한선은 70퍼센트가 많기도 합니다(주관)
2. 처리량
   • 단위 시간 당 완료 된 프로세스의 개수
3. 총 처리 시간
   • 프로세스의 제출 시간과 완료 시간의 간격 (대기시간, CPU에서 실행한 시간, 입출력 등 모든 시간_
4. 대기 시간
   • 준비 완료 큐에서 대기하면서 보낸 시간의 합
5. 응답 시간
   • 하나의 요구를 제출 한 후 첫번째 응답이 발생할 때 까지의 시간

2. 스케쥴링 알고리즘

1. 선입 선처리 스케쥴링 (First-come, First-Served, FCFS)
   • CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받음
   • FIFO 큐로 관리
2. 최단 작업 우선 스케쥴링 (Shortest-Job-First, SJF)
   • CPU busrt가 짧을 수록 CPU를 먼저 할당 받음
3. 우선 순위 스케쥴링 (Priority)
   • 우선 순위가 프로세스들에 연관되어 있으며, 높은 우선순위를 가진 프로세스에게 CPU 할당
   • 여기서 우선 순위는 특성별로 다를 수 있음
4. 라운드 로빈 스케쥴링 (Round-Robin)
   • 시간 할당량이라고 일컫는 작은 단위의 시간
   • 일정한 할당량에 따라 프로세스들이 분배

2-1. 선입 선처리 스케쥴링

Process	Burst Time
P1	24
P2	3
P3	3

ver.1

대기시간  
P1 : 0  
P2 : 24  
P3 : 27

평균 대기시간 : 17

총 처리시간  
P1 : 24  
P2 : 27  
P3 : 30

평균 총 처리 시간 = 27

ver.2

대기시간  
P1 : 0  
P2 : 3  
P3 : 6

평균 대기시간 : 3

총 처리시간  
P1 : 3  
P2 : 6  
P3 : 30

평균 총 처리 시간 = 13

장점
  1) 가장 간단한 형태입니다.
  2) 코드 작성이 쉽고 이해하기 쉽습니다.

단점
  1) 순서에 따라 대기 시간의 차이가 큽니다.
  2) 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다려야 합니다. > 호위효과
  3) 비선점형이기 때문에 시분할 시스템(대화형)에서는 부적합합니다.

2-2. 최단 작업 우선 스케쥴링 (Shortest-Job-First, SJF)

Process	Burst Time
P1	6
P2	8
P3	7
P4	3

대기시간  
P4 : 0  
P1 : 3  
P2 : 9
P2 : 16

평균 대기시간 : 7

장점
  1) 최소의 평균 대기 시간이 걸립니다.

단점
  1) CPU 요청을 매번 처음부터 끝까지 알 수가 없습니다. 어디까지 뭐가 어떻게 들어올 지 알수가 없어서 최단 시간 기준으로 정렬 하기가 까다롭습니다.

2-3. 우선 순위 스케쥴링 (Priority Scheduling)

Process	Burst Time	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

Priority 가 1인 것이 제일 높다고 가정하면 순서는 P2 -> P5 > P1 > P3 > P4

대기시간  
P2 : 0  
P5 : 1  
P1 : 6
P3 : 16
P4 : 18

평균 대기시간 : 8.2

장점
  1) 내부적 정의(시간제한, 메모리요구 등) 활용 가능합니다.
  2) 외부적 정의(프로세스의 중요성 등) 활용 가능합니다.
  3) 즉, 우선순위에 부여한 순서에 따라 프로세스를 부여할 수 있다는 장점이 있습니다.

단점
  1) 중간에 우선 순위가 더 높은 새로운 프로세스가 들어오면 Priority 가 변경이 되면서 제일 마지막에 있는 프로세스는 실행이 되지 않은 채 계속 대기만 해야하는 단점이 있습니다. > 무한 봉쇄, 기아 상태

2-4. 라운드 로빈 스케쥴링 (Round-Robin)

Process	Burst Time
P1	24
P2	3
P3	3

Time Quantum = 4 (시간 할당량이 4라고 가정했을 때)

P2 의 경우 Busrt Time 이 3초이기 때문에 주어진 할당량인 4를 전부 쓰지 않고 3을 사용합니다. (P3)도 마찬가지
P1 은 24초의 Busrt Time 이 필요하기 남은 잔여량인 20을 수행하기 위해 P3 이후 작업을 지속합니다.

대기시간  
P1 : 6 (10-4) 
P2 : 4  
P3 : 7

평균 대기시간 : 5.6

총 처리시간  
P1 : 30
P2 : 7 
P3 : 10

평균 총 처리 시간 = 15.6

장점
  1) 시분할 시스템 최적화되어 있습니다.

단점
  1) 시간 할당량을 적절하게 잡지 못하면 오히려 비효율적입니다.