y-log

CPU 스케줄링

메모리에 올라온 프로세스들 중 어떤 프로세스를 먼저 처리할지 순서를 정하는 것
Ready Queue에 있는 프로세스들 중에 누구에게 CPU를 할당해 줄 것인지 정하는 것

왜 필요한가?

CPU는 한 번에 하나의 프로세스만을 실행시킬 수 있다. --> 특정 프로세스가 I/O 요청으로 대기할 경우, CPU는 놀게됨

시간을 생산적으로 활용하고자 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다.

CPU 이용률 극대화

선점 및 비선점 스케줄링

CPU 스케줄러가 작동되는 4가지 상황

비선점 nonpreemptive

: 상황 1,4와 같이 프로세스가 자발적으로 CPU를 반납하는 경우

CPU가 한 프로세스에 할당되면 프로세스가 종료되든지, 또는 대기상태로 전환해 CPU를 방출할 때까지 점유한다.

선점 preemptive

: 상황 2,3과 같이 강제적으로 CPU를 빼앗기는 경우

Windows, macOS, Linux를 포함한 거의 모든 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.

스케줄링 기준

CPU 이용률

전체 시스템 사용 시간 중 CPU가 작업을 처리하는 시간의 비율 

처리량

단위 시간당 완료된 프로셋의 개수

총 처리 시간

프로세스가 시작해서 끝날 때까지 걸리는 시간 ( 준비 큐에서 대기 시간 + CPU 실행 시간 + I/O 시간 )

대기 시간

프로세스가 준비 큐에서 대기하며 보낸 시간의 합

응답 시간

하나의 요구를 제출한 후 첫번째 응답이 나올 때까지의 시간 ( 응답이 출력되는 시간은 포함하지 않는다 )

CPU 이용률과 처리량을 최대화하고 총 처리 시간, 대기 시간, 응답 시간을 최소화 하는 것으로~!

스케줄링 알고리즘

선입 선처리 FCFS (First Come First Served)

특징

• 먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로 처리.
• 비선점형(Non-Preemptive) 스케줄링
  일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 반환하지 않는다. 할당되었던 CPU 가 반환될 때만 스케줄링이 이루어진다.

문제점

• convoy effect
  소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.

SJF(Shortest - Job - First)

특징

• 다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 선 할당
• 비선점형(Non-Preemptive) 스케줄링

문제점

• starvation
  효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없다.

SRTF(Shortest Remaining Time First)

특징

• 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
• 선점형 (Preemptive) 스케줄링
  현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.

문제점

• starvation
• 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수가 없다.

Priority Scheduling

특징

• 우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
• 선점형 스케줄링(Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
• 비선점형 스케줄링(Non-Preemptive) 방식
  더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.

문제점

• starvation
• 무기한 봉쇄(Indefinite blocking)
  실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태

해결책

• aging
  아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.

Round Robin

특징

• 현대적인 CPU 스케줄링
• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
• 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
• RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
• RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.

장점

• Response time이 빨라진다.
  n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
• 프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가한다.
  공정한 스케줄링이라고 할 수 있다.

주의할 점

설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead 가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.

< 참고 >

https://velog.io/@mu1616/CPU-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81