[운영체제] 4. CPU Scheduling (3)

키워드

multiple-processor scheduling, real-time scheduling, thread scheduling, algorithms evaluation, 알고리즘 평가

 

Scheduling Algorithms

Multiple-Processor Scheduling

• CPU가 여러 개 있는 시스템에서의 스케줄링
• Homogeneous processor
  • 어떤 Job은 특정 CPU가 실행해야 되는 경우
  • ex) 미용실 갔을 때 제일 눈 앞에 보이는 사람한테 깎지 않고 지명한 사람한테 깎는 경우
• Load sharing
  • 특정 CPU만 일하고 나머지 CPU는 놀지 않도록 부하를 적절히 조절하는 메커니즘 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
• Symmetric Multiprocessing(SMP)
  • 모든 CPU들이 대등
  • 각 프로세서(CPU)가 각자 알아서 스케줄링 결정
• Asymmetric Multiprocessing
  • 하나의 프로세서가 전체적인 컨트롤 담당(시스템 데이터의 접근과 공유를 책임짐)
  • 나머지 프로세서는 거기에 따름

 

Real-Time Scheduling

• 데드라인을 보장하는게 중요한 스케줄링 방법
• Hard real-time systems
  • 정해진 시간 안에 반드시 끝내도록 스케줄링
• Soft real-time computing
  • 데드라인을 반드시 지키기 보단
    일반 프로세스에 비해 우선순위만 높여 CPU를 먼저 얻을 수 있게 스케줄링

 

Thread Scheduling

• Local Scheduling
  • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
  • * User level thread: 사용자 프로세스가 직접 스레드를 관리. 운영체제는 스레드의 존재를 모름
  • local scheduling은 OS가 하는게 아닌 사용자 프로세스가 직접 결정
• Global Scheduling
  • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
  • * Kernel level thread: 운영체제가 스레드의 존재를 이미 알고 있음
  • 운영체제가 스레드의 존재를 알고 있기 때문에 프로세스 스케줄링을 하듯 어떤 알고리즘에 근거해 결정

 

Algorithms Evaluation

(알고리즘 평가)

server -> CPU 라고 생각

• Queueing models
  • 이론적인 방법
  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 
    각종 performance index 값 계산
  • 예전엔 많이 썼으나 최근에는 실제 시스템에서 직접 돌려보는 방식을 더 의미있게 보기 때문에
    많이 사용하지는 않음
• Implementation(구현) & Measurement(성능 측정)
  
  • 실측하는 방법
  • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해 성능을 측정 비교
  • 운영체제 내부에 있는걸 고치는건 쉬운일이 아니기 때문에 
    이 방법을 쓰기 어려우면 아래의 simulation 방법을 사용
• Simulation(모의 실험)
  • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
  • * trace: 실제 프로그램을 통해 추출한 input data
    즉, simulation 프로그램에 input으로 들어갈 데이터
    임의로 만들수도 있고 실제 프로그램을 돌리면서 뽑을 수도 있음. 
    후자의 경우가 더 실제 상황을 잘 반영할듯
    trace만 있다면 누구나 simulation이 가능