CS 공부

CS) CPU 스케줄링 알고리즘

tmddnr3503 2024. 12. 26. 22:21

1. CPU 스케줄링

 CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야하는 일을 스레드 단위로 CPU에 할당합니다. CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정합니다. 이 알고리즘을 이용해 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐( ready queue )에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 합니다.

 

2. 비선점형 방식

 비선점형 방식( non-preemptive )은 프로세스가 스스로 CPU 소유권을 포기하는 방식입니다. 따라서 컨텍스트 스우ㅣ칭으로 인한 부하가 적습니다.

  • FCFS : 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘입니다.
    • 장점
      • 단순성 : 구현이 간단합니다.
      • 공정성 : 먼저 요청한 프로세스부터 처리하므로 모든 프로세스가 대기 순서대로 실행됩니다.
    • 단점
      • Convoy 효과 : 긴 프로세스가 CPU를 오랫동안 점유할 경우 뒤의 프로세스들이 오래 기다려야합니다.
      • 비효율성 : 실행 시간이 길수록 평군 대기 시간이 증가합니다.
  • SJF : 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘입니다.
    • 장점
      • 최적의 평균 대기시간 : 이론적으로 평균 대기 시간을 가장 낮게 만드는 알고리즘입니다.
      • 짧은 작업 우선 : 빠르게 종료된 작업을 먼저 처리하여 전체 시스템 효율을 높입니다.
    • 단점
      • 실행 시간 예측 : 작업의 실행 시간을 미리 알기 어렵거나 부정확한 추정이 문제로 작용합니다.
      • 기아 문제 : 긴 작업이 계속 대기 상태로 밀릴 가능성이 있습니다.
  • 우선순위 : 오래된 작업일수록 '우선순위를 높이는 방법( aging )'을 사용하여 SJF 스케줄링의 단점을 사용해 보완한 알고리즘입니다.
    • 장점
      • 중요 작업 우선 처리 : 특정 작업을 우선적으로 처리할 수 있습니다.
      • 유연성 : 우선순위를 상황에 맞게 동적으로 변경이 가능합니다.
    • 단점
      • 기아 문제 : 우선순위가 낮은 작업은 영원히 처리되지 않을 수 있습니다.
      • 우선순위 설정의 어려움 : 잘못된 우선순위 설정은 비효율적인 결과를 초래할 수 있습니다.

 

3. 선점형 방식

 선점형 방식 현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식입니다.

  • 라운드 로빈 : 현대 컴퓨터가 쓰는 선점형 알고리즘 스케줄링 방법으로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐( ready queue )의 뒤로 가는 알고리즘입니다.
    • 장점
      1. 응답 시간 보장 : 모든 프로세스가 정기적으로 CPU 시간을 할당받아 대기 시간이 짧습니다.
      2. 공정성 : 모든 프로세스에 동일한 시간 퀀텀을 제공하여 CPU 자원을 평등하게 분배합니다.
      3. 단순성 : 구현이 쉽고 예측 가능한 스케줄링입니다.
    • 단점
      1. 퀀텀 선택의 중요성 : 퀀텀이 너무 짧으면 오버헤드 증가, 너무 길면 FCFS와 비슷한 동작입니다.
      2. 효율성 감소 : 오버헤드( 문맥 교환 비용 )가 높아질 가능성
      3. 긴 작업 처리 속도 저하 : 짧은 퀀텀으로 인해 긴 작업이 자주 중단되면 처리시간이 늘어납니다.
  • SRF : 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘입니다.
    • 장점
      1. 최소 평균 대기 시간 : 현재 남은 작업 시간이 가장 적은 프로세스를 우선 처리하여 전체 대기 시간 감소
      2. 효율적 자원 활용 : 짧은 작업을 먼저 끝내므로 시스템 자원이 빨리 해제됨
    • 단점
      1. 기아 문제 : 긴 작업은 짧은 작업들에 밀려서 실행이 계속 지연도리 수 있습니다.
      2. 실행 시간 예측의 어려움 : 남은 작업 시간을 정확히 추정해야합니다.
      3. 문맥 교환 오버헤드 : 선점형이므로 문맥 교환이 자주 발생할 수 있습니다.
  • 다단계 큐 : 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것입니다.
    • 장점
      1. 작업 분류 : 작업을 우선순위 또는 유형별로 구분하여 처리할 수 있습니다.
      2. 정책 다양성 : 각 큐에 적합한 스케줄링 정책( 예시로 FCFS, SJF )을 적용이 가능합니다.
      3. 효율성 : 중요한 작업에 더 높은 우선순위를 부여하여 빠르게 처리 가능합니다.
    • 단점
      1. 비탄력성 : 프로세스가 한 번 큐에 배치되면 다른 큐로 이동하기 어렵습니다.
      2. 기아 문제 : 낮은 우선순위 큐의 작업이 높은 우선순위 큐에 계속 밀릴 수 있습니다.
      3. 복잡성 증가 : 큐의 설계와 관리가 복잡하며, 적절한 우선순위 정책 설정이 필요합니다.