[OS] CPU Scheduling (1) - CPU 스케줄링

• Multiprogramming 환경에서 CPU 이용률을 최대한으로 이끌어내기 위함
• CPU - I/O Burst Cycle은 하나의 프로세스이다. CPU 실행과 I/O wait 과정이 반복되는 Cycle형태
• I/O 처리를 진행할 때 CPU가 아무 일도 하지 않으면 이용률이 떨어진다.
• 그래서 CPU Scheduling을 통해 효율성을 극대화하는 것이다.

 

 

• CPU 이용률인데 처음에만(2ms) 많이 사용하고 그 뒤로는 I/O 작업을 하여 이용률이 떨어진다. 

 

 

 

• 메모리에 ready상태로 올라와 있는 작업을 선택한 후 CPU에게 할당
  • process가 running -> waiting state일 때
  • process가 running -> ready state일 때
  • process가 waiting -> ready 상태일 때
  • 종료되었을 때
• ready queue 상태가 변경되는 2, 3번째만 preemptive라고 하고 그 외는 nonpreemptive라고 한다.
• 개념적으로 nonpreemptive (=noninterrupt : 방해할 수 없는 상태)로 이해 해도 됨
• 1, 4번은 당연히 scheduling을 해야하는 상태 
• 2, 3번은 지금 실행 중인 process와 ready queue상태 우선순위를 판단하여 실행시킬 수 있기 때문에 interrput받을 수 있음

 

 

 

• 스케줄링을 한 후 실행해야 하는 프로세스에서 컨트롤러를 넘겨주어야 한다. 넘겨주는 역할을 하는 것이 Dispatcher
• Short-tem scheduler에 의해 선정된 프로세스한테 Control을 넘겨준다.
• 한 프로세스를 중지시키고 다른 프로세스를 실행시키는 데 걸리는 시간 - Dispatch latency
• 이러한 과정은 kernel mode에서 실행된다.

 

 

• Scheduling을 하는 다섯 가지 기준

1. [MAX] CPU utilization - CPU 이용률 극대화를 위해
2. [MAX] Throughput - 정해진 시간 내 처리할 수 있는 Process 개수
3. [MIN] Turnaround time - 어느 한 Process를 시작하고 종료할 때까지 걸리는 시간
4. [MIN] Waiting time - Ready Queue에서 기다리는 시간 기준 
5. [MIN] Response time - 작업에 대한 반응 시간

 

 

• Ready Queue안에 먼저 들어온 Process가 CPU를 먼저 할당 받는다.

 

• 순서를 바꿔서 Burst Time이 작은 것들을 먼저 하면 Average waiting Time이 작아진다.
• Convoy effect : Long Process를 Short Process가 기다리는 것

 

• 위에서 확인한 것 처럼 좀더 효율적인 방법을 위한 알고리즘
  • Nonpreemptive(NonInterrput 방식) : CPU가 처리하고 있는 Process는 건드리지 않는다.
  • preemptive : 지금 CPU가 처리하고 있는 Process의 나머지 작업량까지 같이 Scheduling하는 것
• Shortest-Job-First(SJF) 방식이 Average-Waiting-Time이 가장 작은 값을 구할 수 있는 최적화방법

 

 

• NonPreemptive이므로 한 작업을 할당하면 끝날 때까지 진행

 

• Preemptive이므로 작업 중이어도 더 빨리 끝낼 수 있는 것이 존재하면 진행

 

 

• 지금까지는 주어진 BurstTime으로 처리했었다. 이제는 다음 CPU Burst를 예측하여 진행하는 방식이다.
• t(n)은 실제 주어진 CPU Burst
• 타우(n+1)은 다음 CPU Burst 값을 예측한 것
• 알파는 측정한 값과 예측한 값 사이 비중을 어디에 둘지

 

 

• 알파값이 0이면 다음 Burst 값이 현재 타우값과 같다.
• 알파값이 1이면 다음 단계 Burst 값이 전 Burst 값과 같다.

 

 

• 위 주어진 식들로 실제 예측한 값들에 대한 표

 

 

• 우선순위를 따져 Scheduling하는 것 - 우선순위는 integer로 매김
• 이 방식도 1) Preemptive와 2)Nonpreempive 방식으로 나눌 수 있음
• SJF도 우선순위에 기반한 알고리즘
• 발생할 수 있는 문제점 [Starvation] : 낮은 우선순위 Process가 실행이 되지 못하는 문제점
• 해결방안 [Agin] : 시간이 지남에 따라 우선순위를 조금씩 올려주는 방식

 

• 모든 Process가 CPU를 할당받으면 CPU를 사용할 수 있는 시간을 정해주는 것 → Time Quantum : 10-100 milliseconds
• 그 시간이 경과되면 다시 Ready Queue에서 대기해야함
• 만약 Ready Queue안에 N개의 Process가 존재하고 Time quantum이 q라면 CPU Time을 N개의 Process가 나눠서 사용, 그러므로 process는 time-quantum이 끝나면 최소 (n-1)*q시간 만큼 기다려야함
  • q값이 크면 FIFO과 똑같은 방식임, 한 번하고 거의 끝이므로
  • 작으면 Context Switch가 자주 일어나므로 Overhead가 커질 수 있다.

 

 

• 일반적으로 SJF보다 turnaround시간은 높지만, response는 좋은 점을 가지고 있다.
• Burst Time이 끝나면 미리 정해진 다음 작업을 바로 수행하기 때문에 response가 좋다

 

• process time이 10이고 quantum 값이 달라짐에 따라 CPU Context Switch 횟수가 달라진다.
• 너무 짧은 q값을 가지면 CPU는 많은 Context Switch가 일어나야하기 때문에 Overhead가 커지고 성능이 저하된다.

 

 

• 그렇다고 quantum값을 크게 준다고 무조건 성능이 좋아지는 것은 아니다.
• 모든 작업들의 90%가 주어진 Quantum값 내에서 끝내도록 Quantum값을 설정하는 것이 최고 효율이다.