OS - CPU Scheduling

CPU 스케줄링

- CPU가 대기 중인 프로세스들을 어떤 순서로 처리할지 결정하는 작업이다.

 

 

CPU 스케줄링 방법 결정 기준

- CPU의 입장과 CPU 할당을 기다리는 프로세스들의 입장을 고려해야 하며, 각 기준들은 보통 Trade-off 관계에 있으므로 절대적으로 좋은 스케줄링 방법이 고정되지 않는다.

(for CPU의 기준들을 높이면서, for PROCESS의 기준들을 낮추는 것이 목표)

for CPU

• CPU 이용률(CPU Utilizaiton) : 시스템 사용 (총 or 특정) 기간 동안의 실제 CPU 사용률
• 처리량(Throughput) : 단위 시간당 작업을 마친 프로세스 개수

for PROCESS

• 반환 시간, 총 처리 시간(Turn-around Time) : 프로세스가 요청한 시간 부터 프로세스 종료까지의 총 시간
• 대기 시간(Waiting Time) : 프로세스가 대기 큐에서 CPU할당을 기다린 시간
  • 프로세스가 스케줄링 방법에 따라 (대기 큐 → CPU할당 → 대기큐 ...)처럼 여러번 CPU할당이 반복되면 대기 시간도 여러개 존재한다.
• 응답 시간(Response Time) : '최초'로 CPU를 할당 받기까지 기다린 시간
  • 프로세스 마다 한 번 계산된다. 처음 CPU를 점유하는데 걸린 시간이다.

 

 

CPU 스케줄링 방식

- 선점형(Preemptive) 방식과 비선점형(Non-Preemptive) 방식이 있다.

 

비선점형 방식 

- 인터럽트 발생이 아닌 이상, 현재 CPU에서 처리 중인 프로세스가 끝나기 전까지 다른 어떤 프로세스도 CPU를 점유 할 수 없다.

• FIFO(First In First Out = FCFS : First Come First Served) : 먼저 요청한 프로세스 순서대로 처리한다.
• SJF(Shortest Job First) : 총 처리 시간이 짧은 프로세스를 우선으로 처리한다.
  • 처리 시간이 상대적으로 짧은 프로세스들의 요청이 지속되면 처리 시간이 긴 프로세스는 기아 현상(Starvation)에 빠진다. 
• HRN(Hightest Response-Ratio Next) : SJF 기반에 aging기법을 추가하여 기아 현상을 방지한 방법이다.
  • 우선순위 = (응답 대기 시간 + 총 처리시간) / 총 처리 시간

 

선점형 방식

- 특정 우선 순위에 따라 요청(또는 대기 중인) 프로세스가 현재 CPU에서 처리 중인 프로세스를 강제로 밀어내고 CPU를 점유 할 수 있다. 

• SRT(Shortest Remaining Time) : SJF과 같지만 선점이 가능하다.
  • 처리 시간이 더 짧은 프로세스가 선점
• RR(Round-Robin) : 모든 프로세스들이 같은 Priority를 가지며, 정해진 단위 시간을 기준으로 모든 프로세스를 번갈아 처리한다.(= 대기 큐에 있는 프로세스들을 순서대로 순회하며 정해진 단위 시간씩 처리) 
  • 단위 시간이 심하게 길어지면 FIFO와 같아진다.
  • 단위 시간이 심하게 짧아지면 switching하며 발생하는 overhead가 증가하여 비효율을 초래한다.
• MQ(Multilevel Queue) : 프로세스들을 우선순위에 따라 그룹으로 나눌 수 있다면, 그룹별로 다른 대기 큐를 사용한다. 그리고 (우선 순위가 높은 그룹이 대기하고 있는 큐 → 우선 순위가 낮은 그룹의 큐) 순서로 우선 순위를 가지며 선점을 할 수 있다.
  • 각 큐들은 서로 다른 방식으로 스케줄링 될 수 있다.
    • 큐마다 스케줄링 방식, CPU 점유 시간 등을 다르게 적용 가능 

      

      출처 : http://itnovice1.blogspot.com/2019/08/multi-level-queue.html

• MFQ(Multilevel Feedback Queue) : MQ와 마찬가지로 여러 대기큐가 존재한다. 대기 큐들은 각각 CPU 점유 시간이 다르며, 우선 순위가 높은 큐일수록 할당 시간(Time Quantum)이 적다. 만약 정해진 할당 시간 안에 프로세스가 완료되지 않으면 해당 프로세스는 한 단계 하위 우선 순위 대기 큐로 보내진다. 
  • 만약 낮은 우선 순위 대기 큐에서 대기 시간이 너무 길어지면 상위 대기 큐로 이동한다.(기아 현상 방지)

 

 

 

 

 

 

 

출처 : 

https://jwprogramming.tistory.com/17

https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-6.-CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81

https://bnzn2426.tistory.com/65