Scheduling

Preemptive

선점형, 운영체제가 강제로 CPU를 회수할 수 있다.
혹은 정지했다가, 다시 재개될 수 있음.

• 어떤 프로세스가 CPU를 쓰고 있다가, 더 높은 우선순위의 프로세스가 준비되면 OS가 강제로 현재 프로세스를 중단시키고 CPU를 회수한다.

• 반응성이 좋고, 실시간이나 멀티 테스킹에 유리하다.

Non-Preemptive

비선점형, CPU를 자발적으로 반납할 때까지 기다린다.

• 현재 프로세스가 종료되거나 I/O 요청등으로 스스로 CPU를 놓을 때까지 다음 프로세스는 대기해야한다.

• 구현이 상대적으로 간단하지만, 반응성이 떨어진다.

• Starving : 하나의 프로세스가 오랫동안 CPU를 점유하고 있어 다른 프로세스는 동작하지 못하고 대기만 하는 상태가 될 수 있다.

정보

• 현대 OS는 대부분 Preemptive Cpu 스케쥴링을 사용한다.
• 비선점형 방식은 프로세스를 중단시키는 것이 불가능하기 때문에, 비용이 많이 들어가거나 중요한 프로세스인 경우에 사용한다.

CPU Scheduler 발동하는 시점

• 새로운 프로세스가 ready 상태에 들어올 때. (선점)
  : 현재 실행중인 프로세스가 아직 끝나지 않았지만, 운영체제가 강제로 CPU를 회수해서 다른 프로세스에게 넘기기 때문. (ready에 들어온 프로세스가 우선도가 높을 수 있음)

• 프로세스가 running에서 waiting으로 들어갈 때. (비선점)
  : 실행중이던 프로세스가 I/O 요청등으로 인해 스스로 running에서 waiting으로 가기 때문에 비선점이다.

• 프로세스가 waiting에서 ready로 돌아올 때. (선점)
  : I/O가 끝난 프로세스가 다시 ready로 올때, 우선순위가 높다면 우선적으로 운영체제가 기존 프로세스를 종료하고 CPU를 할당해줄 수 있기 때문에 선점이다.

• 프로세스가 running에서 ready로 돌아올 때. (선점)
  : 프로세스가 정해진 시간을 다 소모해 운영체제가 강제로 ready상태로 넣기 때문에 선점이다.

• 프로세스가 running에서 종료될 때. (비선점)
  : 운영체제가 강제로 종료시킨게 아니라 프로세스가 스스로 CPU를 내려놓기 떄문에 비선점이다.

Scheduling Criteria(평가 기준)

• CPU utilization : CPU가 얼마나 놀지 않고 잘 활용되는지.
• Throughput : 단위 시간당 완료된 프로세스 수를 뜻한다.(처리량)
• Turnaround Time : 특정 프로세스가 제출된 후 완료되기까지 걸리는 시간(반환 시간)
• Waiting Time : 프로세스가 readu queue에서 대기한 시간의 총합
• Response Time : 요청이 들어온 후 첫 번째 응답이 나올때 까지 걸리는 시간

Scheduling Policies

위에서 배운 Scheduling Criteria를 토대로 성능을 좋게 하기 위한 여러 알고리즘에 대해서 알아보도록 하자.

Policies : Non-Preemptive

First Come First Served

먼저 도착한 프로세스가 먼저 동작하고, 다 끝나면 그 후에 도착한 프로세스가 순차적으로 CPU를 점유하는 방식이다.

• Waiting time for P1 = 0; P2 = 24; P3 = 27
• Average waiting time (0+24+27)/3 = 17
• 평균 대기 시간은 각 대기 시간에서 평균을 구하면 된다.

Shortest-Job-First(SJF)

다음 CPU burst가 가장 짧은 것으로 예상되는 프로세스에 CPU를 할당한다.

• 평균 대기 시간을 최소화하는 최적의 알고리즘이지만, 실제로는 burst시간을 정확히 알기 어렵다.
• 예측은 이전 burst 시간의 지수평균으로 추정할 수 있다.

• Average Waiting Time : (0+3+9+16 = 28)/4 = 7

🤨 그렇다면 CPU Burst Time을 어떻게 예측할 수 있을까. 많은 방법이 있겠지만, 이전 결과를 이용해 가중치로 예측을 하는 것이 일반적이다.

😃 이 그림에서 a값은 가중치라고 생각하면 된다. 일반적으로 그냥 1/2로 대입한다.

이러한 예측 burst Time은 SJF또는 SRTF 스케쥴링에서 사용된다.

Policies : Preemptive

Shortest Remaining Time First (SRTF)

SJF는 짧은 일 순으로 Burst시키는 것이라고 우리가 배웠다. 그러면 여기에 선점형을 추가하면 어떻게 될까?

• 먼저 도착한 작업을 수행한다.
• 다른 프로세스가 도착하면 짧은 일을 비교하여 짧은 일은 우선적으로 처리한다.

• P1을 작동시키다가 더 짧은 일이 도착하면 그 일을 우선적으로 처리한다.

• 새로운 프로세스가 도착할때마다 확인한다.

• Average Waiting Time = P1(9) + P2(0) + P3(15) + P4(2) = 26 이를 4로 나누면 6.5가 나온다.

Priority Scheduling

프로세스의 우선순위를 기반으로 Burst순서를 세팅하는 것이다.

• 선점형일 경우 : 우선순위 높은 프로세스가 도착하면 프로세스를 교체한다.
• 비선점형일 경우 : 우선순위가 높은 프로세스가 도착해도 일단 하던거 끝내고 교체한다.
• SFJ를 구현할 수 있다. => Burst시간을 예측해 낮은 실행시간을 가진 프로세스에 높은 우선도를 설정해줄 수 있다.
• 우선순위가 낮을수록 우선도가 높다.

⚠️우선순위 스케줄링 의 문제점 : Starvation 발생 가능성 존재.
-> 우선순위가 낮은 프로세스는 영원히 실행되지 못할 수 있다.

✅Starvation 해결책 : Aging을 사용해 시간이 지남에 따라 우선도를 높여주는 방식이다.

• Average Waiting Time = P1(6) + P2(0) + P3(16) + P4(18) + P5(1) = 41 / 5 => 8.2

Round Robin

각 프로세스에 시간 할당량을 주고, 시간이 지나면 강제로 CPU를 빼앗아 ReadyQueue의 뒤로 보낸다.

• q(할당 시간)가 너무 커지면 FCFS와 유사해진다.
• q가 너무짧아지면 너무 자주 변경되기 때문에 Context switching으로 인한 오버헤드가 증가한다.

• 만약에 q가 4라고 한다면 정해진 시간만큼만 할당해주고, timeout이 되면 다음 작업으로 동작시킨다.

• 일반적으로 평균 반환 시간은 SJF보다 길지만, 응답 시간은 더 좋다.