[OS] CPU 스케줄링 - 2 (스케줄링 알고리즘)

스케줄링 알고리즘

1. 선입선출 스케줄링(First-Come First-Servied: FCFS)

• 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 시간
  
  
• 먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라진다
  
  
• 콘보이 현상이 나타날 수 있다.
  • 콘보이 현상 ? CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야하는 현상
    
    
    

2. 최단작업 우선 스케줄링(Shortest-Job First: SJF)

• CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
  
  
• SJF 알고리즘은 비선점형 방식과 선점형 방식 두 가지로 구현될 수 있다.
  • 비선점형 방식(nonpreemptive)
    : 일단 CPU를 획득하면 그 프로세스가 CPU를 자진 반납하기 전까지는 CPU를 빼앗지 않는 방식
    
    
  • 선점형(preemptive)방식
    : 준비 큐에서 CPU 버스트가 가장 짧은 프로세스에게 CPU를 할당했다 하더라도, CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식
    • SRTF(Shortest Remaining Time First)라고도 부름
      
      
• 평균 대기시간을 가장 짧게하는 최적 알고리즘으로 알려져 있음
  
  
• 프로세스의 CPU 버스트 시간을 미리 예측할 수 없다.
  
  
• 기아현상(starvation)이 나타날 수 있음
  • 기아현상(starvation) ? CPU 버스트가 짧은 프로세스가 계속 도착할 경우 프로세스 A는 영원히 CPU를 할당받지 못할 수도 있는 현상
    
    

3. 우선순위 스케줄링(Priority scheduling)

• 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
  
  
• 우선순위는 우선순위값(priority number)을 통해 표시하며 우선순위값이 작을수록 높은 우선순위를 가지는 것으로 가정한다.
  
  
• 비선점형 방식과 선점형 방식 두 가지로 구현될 수 있다.
  • 선점형(preemptive)방식
    : 현재 CPU에서 수행 중인 프로세스보다 우선순위가 높은 프로세스가 도착하여 CPU를 선점해서 새롭게 도착한 프로세스에게 할당할 경우
    
    
  • 비선점형 방식(nonpreemptive)
    : 일단 CPU를 얻었으면 비록 우선순위가 높은 프로세스가 도착하더라도 CPU를 자진 반납하기 전까지 선점하지 않는다
• 기아 현상이 발생할 수 있다.
  → 해결: 노화 aging기법을 사용할 수 있다.
  • 노화(aging) 기법? 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법
    
    

4. 라운드 로빈 스케줄링(RR)

• 시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식
  
  
• 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경화하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다.
  
  
• time quantum: 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간
  • 할당시간이 너무 길면 FCFS와 같은 결과를 나타나게 된다.
    
    
  • 할당시간이 너무 짧으면 CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥 교환의 오버헤드가 커진다.
    
    

5. 멀티레벨 큐(multi-level queue)

우선순위가 낮은 큐들이 실행 못하는 것을 방지하고자 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법

본인의 운명대로 e.g)계급제

• Ready queue를 여러 개로 분할
  • foreground(interactive)
    
    
  • background(batch - no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
    
    
  • background - FCFS
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling
    
    • 큐에 고정적인 우선순위를 부여해 우선순위 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어 있을 때만 서비스하게 됨
      
      
  • Time Slice
    • 각 큐에 CPU time을 적절한 비율로 할당
      
      

6. 멀티레벨 피드백 큐

CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.

• 다단계 큐에서 자신의 Time Quantum을 다 채운 프로세스는 밑으로 내려가고 자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로
  
  
• 짧은 작업에 유리, 입출력 위주(interrupt가 잦은) 작업에 우선권을 줌
  
  
• 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 Turnaround 평균 시간을 줄여줌

7. 다중처리기 시스템(Multi-processor system)

CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐

e.g) 헤어디자이너가 여러 명 있는 미용실에서 먼저 도착한 순서대로 헤어디자이너가 결정되어 서비스를 받는 것이 아니라, 특정 손님이 특정 헤어디자이너에게 서비스를 받겠다고 하는 경우

• Homegeneous processor 인 경우
  
  • queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
    
    
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
    
    
• 부하 균형 Loda sharing
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
    
    
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
    
    
• 대칭형 다중처리 Symmetric Multiprocessiong(SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정
    
    
• 비대칭형 다중처리 Asymmetric multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
    
    

8. 실시간 스케줄링

각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야한다. 

• Hard real-time systems
  
  • 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
    
    
• Soft real-time computing
  
  • 일반 프로세스에 비해 높은 priority 를 갖도록 해야 함
    
    

Thread Scheduling

• Local Scheduling
  • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
    
    
• Global Scheduling
  • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
    
    

스케줄링 알고리즘의 평가 Algorithm Evaluation

1. Queueing models
   
   • 확률 분포로 주어지는 arrival rate 와 service rate등을 통해 각종 performance index 값을 계산
     
     
2. Implementaion & Measurement
   • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
     
     
3. Simulation
   • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교

 

 

---

출처  https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/CPU%20Scheduling.md