CPU 스케줄링 알고리즘

선입 선처리 스케줄링

FCFS(First Come First Served) 스케줄링

• 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
• 먼저 CPU를 요청한 프로세스부터 CPU 할당
• 단점 : 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용 (=호위 효과)

  최단 작업 우선 스케줄링

  SJF(Shortes Job First) 스케줄링

• 호위 효과를 방지하려면?
• CPU 사용이 긴 프로세스를 나중에 실행, CPU 사용 시간이 짧은 프로세스를 먼저 실행
• CPU 사용 시간이 가장 짧은 프로세스부터 처리하는 스케줄링 방식

  라운드 로빈 스케줄링

• RR (Round-Robin) 스케줄링
• 선입 선처리 스케줄링 + 타임 슬라이스 (time slice)
• 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
• 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
  • 큐에 삽입된 프로세스들은 순서대로 CPU를 이용하되, 정해진 시간만큼만 이용
  • 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면, 다시 큐의 맨 뒤에 삽입 (문맥 교환)

    타임 슬라이스의 크기가 중요 (너무 크면 FCFS처럼 호위 효과 발생 / 너무 작으면 문맥 교환 오버헤드가 발생하여 CPU 부담이 커짐)

    최소 잔여 시간 우선 스케줄링

• SRT(Shortest Remaining Time) 스케줄링
• 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
• 정해진 시간 만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 선택

  우선순위 스케줄링

• 프로세들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행
• 우선순위가 같은 프로세스들은 선입 선처리로 스케줄링
• 최단 작업 우선 / 최소 잔여 시간 스케줄링은 둘 다 우선순위 스케줄링의 한 종류
• 기아 현상 (Starvation) : 우선순위가 낮은 프로세스는 (준비 큐에 먼저 삽입되어도) 실행이 계속 연기될 수 있다.
  • 에이징 : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
  • 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
  • 처음엔 우선순위가 낮아도 언젠간 우선순위가 높아진다.

    다단계 큐 스케줄링

    MultilevelQueue 스케줄링

• 우선순위 스케줄링의 발전된 형태
• 우선순위별로 준비 큐를 여러개 사용하는 스케줄링 방식
  • 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리
  • 우선순위가 가장 높은 큐가 비어 있으면, 그 다음 우선순위 큐에 있는 프로세스를 처리
• 장점 : 프로세를 유형 (큐) 별로 처리 가능
• 단점 : 큐 간에 이동이 불가능하여, 기아 현상 발생 가능

  다단계 피드백 큐 스케줄링

  Multilevel feedback queue 스케줄링

• 다단계 큐 스케줄링의 발전된 형태
• 큐 간 이동이 가능한 다단계 큐 스케줄링

  • 일단 가장 우선 순위가 높은 큐에 넣고 실행
  • 안끝났으면 다음 우선 순위가 높은 큐에 넣고 실행
  • … 점점 우선순위가 낮아짐

• CPU를 집중 프로세스의 우선 순위가 상대적으로 낮아지고, 입출력 집중 프로세스의 우선 순위는 상대적으로 높아진다.
• 에이징 기법 적용 가능 (큐에서 대기가 길어지면, 우선 순위가 높은 큐로 이동)