CPU 스케줄링(2)

이번시간에는 실제로 CPU 스케줄링을 할 때 사용되는 알고리즘에대해서 알아보도록 하겠습니다. 

⭐️CPU 스케줄링의 종류

저번 시간에 배웠듯이 CPU 스케줄러는 준비 상태에 있는 프로세스들 중에서 어떤 프로세스에게 CPU를 할당할 것인지 결정하는 운영체제 코드라고 하였습니다. 그리고 스케줄링 방식에는 선점 스케줄링과 비선점 스케줄링 기법이 있었습니다. *선점 스케줄링은 프로세스로부터 CPU를 강제로 빼앗을 수 있는 방식이고, 비선점 스케줄링은 프로세스가 CPU를 자진 반납하기 전까지 빼앗을 수 없는 방식. 

그렇다면 CPU 스케줄링 알고리즘은 어떤 종류가 있을까요?

비선점 스케줄링: 강제로 빼앗을 수 없는 방식

• FCRS(First Come First Served) - 선입선출 스케줄링
  • 준비 큐에 도착한 순서대로 CPU를 할당 받는다.
  • But, 실행시간은 짧은 프로세스가 뒤에 있고 실행시간이 긴 프로세스가 앞에 있으면 평균 대기 시간이 길어진다.
• SJF(Shortest Job First) - 최단작업 스케줄링
  • 평균 대기 시간의 문제 보완으로 수행시간이 가장 짧은 작업부터 먼저 수행한다. 
  • 따라서, FCFS 보다 평균 대기 시간이 줄어들고, 짧은 작업에 유리하다.
  • 하지만, 이런 방식은 CPU burst가 긴 프로세스는 준비 큐에 줄을 서서 무한정 기다려야하는 문제가 발생할 수 있다.
• HRN(Hightest Response-ratio Next)
  • 우선 순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
  • 우선 순위 = (대기시간 + 실행시간) / (실행시간)

선점 스케줄링: 강제로 빼앗을 수 있는 방식

• Priority 스케줄링
  • 정적/동적으로 우선순위를 부여하여 우선순위가 가장 높은 프로세스에게 CPU를 할당하는 방식이다.
  • 하지만 이러한 방식은 우선순위가 낮은 프로세스가 계속 도착하는 상황에서 우선 순위가 낮은 프로세스는 무한정 기다리는 기아현상 즉, Starvation 이 발생할 수 있다. 
  • 이러한 문제를 노화(Aging) 기법을 통해 해결할 수 있다. 노화 기법이란 기다리는 시간이 길어질 수록 우선순위를 높여주고 결국에는 CPU를 할당받을 수 있게하는 방식이다. 
• Round Robin 스케줄링
  • 시분할 시스템의 성질을 가장 잘 활용한 방식이다.
  • 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄서있는 또다른 프로세스에게 CPU를 할당한다. 그러면 이 프로세스는 준비 큐의 맨 뒤에 가서 줄을 서게 되고 다음 번 차례가 올 때까지 기다리게 된다.
  • 이때 CPU를 갖고 있는 프로세스가 CPU를 연속적으로 사용할 수 있는 최대 시간을 Time Quantum 이라고 한다.
  • 할당 시간(Time Quantum)이 너무 크면 FCFS와 같고, 너무 작으면 문맥교환이 잦아져서 오버헤드가 증가한다.
• Multi-level-queue 
  • 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법이다. 즉 프로세스들이 CPU를 기다리기 위해 한 줄로 서 있는 것이 아니라 여러줄로 기다리는 것을 말합니다. 
  • 하지만 CPU는 하나밖에 없으므로 어떤 줄에 있는 프로세스에게 우선적으로 스케줄링할 것인가 하는 문제 발생, 또한 프로세스가 도착했을 때 어느 줄에 세워야할 지 결정하는 메커니즘도 필요하다.
  • 우선 순위가 낮은 큐들이 실행 못하는 걸 방지하고자 각 큐마다 다른 Time Quantum을 설정해 주는 방식 이용
  • 우선 순위가 높은 큐는 작은 Time quantum 할당. 우선순위가 낮은 큐는 높은 Time quantum 할당
• Multi-level-Feedback-Queue(다단계 피드백 큐)
  • 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time quantum을 다 채우지 못한 프로세스는 원래 큐 그대로 둔다.
  • 짧은 작업에 유리, 입출력 위주 작업에 우선권 부여
  • 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Trunaroud 평균 시간을 줄여줌.