poeun 🔅

Original Artwork © Henri Matisse (1869 ~ 1954), Le Cheval L’Ecuyere et le Clown, 1947, 64.6 x 42.5, Centre Georges-Pompidou

개인 저장공간입니다.
도움이 되길 바랍니다.
Since 2021.10

4 분 소요

본 글은 Operating System Concepts 10th (운영체제) 책을 보며 내용을 개인 공부에 목적으로 정리했습니다.
이전에 운영체제 관련 강의들을 들으면서 정리한 시리즈 글들이 있는데,
지식을 습득하는 데 있어 가장 느리지만 가장 빠른 방법이 원본책을 자세히 보는 것이라 생각됩니다.
책 내용들을 최대한 이해하기 위해 거의 모든 내용을 담고 있습니다.

책 pdf 링크 : Operating System Concepts 10th Edition by Abraham Silberschatz Peter B Galvin Greg Gagne pdf free download
연습 문제 정답지 : Solutions of Practice Exercises, Tenth Edition of Operating System Concepts, AVI SILBERSCHATZ



5.4 Thread Scheduling

  • 대부분 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다.
  • 사용자 수준 스레드는 스레드 라이브러리에 의해 관리되고 커널은 그들의 존재를 알지 못한다.
  • 사용자 수준 스레드는 궁극적으로 연관된 커널 수준 스레드에 사상되어야 한다.
  • 이 절에서는 사용자 수준과 커널 수준 스레드의 스케줄링에 관한 쟁점을 탐구하고 Pthreads의 스케줄링 사례를 알아본다.


5.4.1 Contention Scope

  • 사용자 수준과 커널 수준 스레드의 차이 중 하나는 그들이 어떻게 스케줄 되느냐에 있다.
  • 다대일과 다대다 모델을 구현하는 시스템에서는 스레드 라이브러리는 사용자 수준 스레드를 가용한(available) LWP상에서 스케줄 한다.


이미지출처 1

  • 이러한 기법은 동일한 프로세스에 속한 스레드들 사이에서 CPU를 경쟁하기 때문에 프로세스-경쟁-범위(process-contention scope, PCS)로 알려져 있다.
  • 우리가 스레드 라이브러리가 사용자 수준 스레드를 가용한 LWP상에서 스케줄(schedule) 한다고 말하는 경우, 스레드가 실제로 CPU상에서 실행(running) 중이라는 것을 의미하지 않는다.
  • 실제로 CPU상에서 실행되기 위해서는 운영체제가 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄 하는 것을 필요로 한다.
  • CPU상에 어느 커널 스레드를 스케줄 할 것인지 결정하기 위해서 커널은 시스템-경쟁 범위(system-contention scope, SCS)를 사용한다.
    • SCS 스케줄링에서의 CPU에 대한 경쟁은 시스템상의 모든 스레드 사이에서 일어난다.
    • Windows와 Linux 같은 일대일 모델을 사용하는 시스템은 오직 SCS만을 사용하여 스케줄한다.


  • 전형적으로, PCS는 우선순위에 따라 행해진다. 즉, 스케줄러는 가장 높은 우선순위를 가진 실행 가능한 프로세스를 선택한다.
  • 사용자 수준 스레드의 우선순위는 프로그래머에 의해 지정되고 스레드 라이브러리에 의해 조정되지 않는다.
    • 그러나 몇몇 스레드 라이브러리는 프로그래머가 스레드의 우선순위를 변경하는 것을 허용한다.
  • PCS는 통상 더 높은 우선순위의 스레드를 위하여 현재 실행 중인 스레드를 선점(preemptive)한다는 것을 주의해야 한다.



5.5 Multiple-Processor Scheduling

  • 만일 여러 개의 CPU가 사용 가능하다면, 여러 스레드가 병렬로 실행될 수 있으므로 부하 공유(load sharing)가 가능해진다.
  • 멀티 프로세서는 여러 개의 물리적 프로세서를 제공하는 시스템을 말하며, 각 프로세서에는 하나의 싱글 코어 CPU가 포함되어 있다.
  • 그러나 멀티 프로세서의 정의는 크게 발전했으며 최신 컴퓨팅 시스템에서는 다음 시스템 아키텍처들에 이것을 사용할 수 있다.
    • 멀티 코어 CPU
    • 멀티 스레드 코어
    • NUMA 시스템
    • 이기종(Heterogeneous) 멀티 처리


5.5.1 Approaches to Multiple-Processor Scheduling

  • 멀티 프로세서 시스템의 CPU 스케줄링에 관한 한 가지 해결 방법은 마스터 서버(master server)라는 하나의 프로세서가 모든 스케줄링 결정과 I/O 처리 그리고 다른 시스템의 활동을 취급하게 하는 것이다.
  • 다른 프로세서들은 사용자 코드만을 수행하는데, 이러한 비대칭 멀티 프로세싱(asymmetric multiprocessing)는 오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다.
    • 이 접근 방식의 단점은 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 것이다.


  • 멀티 프로세서를 지원하기 위한 표준 접근 방식은 대칭 멀티프로세싱(symmetric multiprocessing, SMP)이며 각 프로세서는 스스로 스케줄링 할 수 있다.

    image
    이미지출처 2

  • 각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행된다.
  • 이는 스케줄 대상이 되는 스레드를 관리하기 위한 2가지 가능한 전략을 제공한다.
    1. 모든 스레드가 공통 준비 큐에 있을 수 있다.
    2. 각 프로세서는 자신만의 스레드 큐를 가질 수 있다.

image

  • 2번째 옵션은 각 프로세서가 자신만의 실행 큐에서 스레드를 스케줄 할 수 있도록 허용하므로 공유 실행 큐와 관련되어 발생할 수 있는 성능 문제를 겪지 않는다.
  • 따라서, SMP를 지원하는 시스템에서 가장 일반적인 접근 방식이다.
  • 자신만의 프로세스별 큐가 있으면 캐시 메모리를 보다 효율적으로 사용할 수 있다.


5.5.2 Multicore Processors

  • SMP 시스템은 다수의 물리 프로세서를 제공함으로써 다수의 프로세스가 병렬로 실행되게 한다.
  • 그러나 현대 컴퓨터 하드웨어는 동일한 물리적인 칩 안에 여러 개의 처리 코어를 장착하여 멀티 코어 프로세서(multicore processor)가 된다.
  • 멀티코어 프로세서를 사용하는 SMP 시스템은 각 CPU가 자신의 물리 칩을 가지는 시스템과 비교해 속도가 빠르고 적은 전력을 소모한다.


image

  • 프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비하는, 메모리 스톨(memory stall)이라고 하는 이 상황은 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하기 때문에 자주 발생한다.
  • Figure 5.12 같은 시나리오에서 프로세서는 메모리의 데이터를 사용할 수 있을 때까지 기다리느라 최대 50%의 시간을 허비할 수 있다.


image

  • 이러한 상황을 해결하기 위해 최근의 많은 하드웨어 설계는 멀티 스레드 처리 코어를 구현하였다.
  • 이러한 설계에서 하나의 코어에 2개 이상의 하드웨어 스레드가 할당된다.
    • 이렇게 하면 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있다.


image

  • 운영체제 관점에서 각 하드웨어 스레드는 명령어 포인터 및 레지스터 집합과 같은 구조적 상태를 유지하므로 소프트웨어 스레드를 실행할 수 있는 논리적 CPU로 보인다.
    • 이 기술을 칩 멀티 스레딩(chip multithreading, CMT)라 부른다.


  • 일반적으로 프로세서를 멀티 스레드화 하는 데에는 거친(coarse-grained) 멀티 스레딩과 세밀한(fine-grained) 멀티 스레딩의 2가지 방법이 있다.
  • 거친 멀티 스레딩에서는 스레드가 메모리 스톨과 같은 긴 지연시간을 가진 이벤트가 발생할 때까지 한 코어에서 수행된다.
    • 긴 지연시간을 가진 이벤트에 의한 지연 때문에 코어는 다른 스레드를 실행하게 된다.
    • 그러나 그 프로세서 코어에서 다른 스레드가 수행되기 전에 명령어 파이프라인이 완전히 정리되어야 하므로 스레드 간 교환은 비용이 많이 든다.
    • 이 새로운 스레드가 실행을 시작하게 되면 자신의 명령어들로 파이프라인을 채우기 시작한다.
  • 세밀한 멀티 스레딩은 보통 명령어 주기의 경계에서 같이 좀 더 세밀한 정밀도를 가진 시점에서 스레드 교환이 일어난다.
    • 그러나 세밀한 시스템의 구조적 설계는 스레드 교환을 위한 회로를 포함한다.
    • 그 결과 스레드 간 교환의 비용이 적어진다.


image

  • 물리적 코어(캐시 및 파이프라인 등)의 자원은 하드웨어 스레드 간에 공유되어야 하므로 처리 코어는 한 번에 하나의 하드웨어 스레드만 실행할 수 있다.
  • 결과적으로 멀티 스레드 멀티 코어 프로세서는 Figure 5.15와 같이 현실적으로 2개의 다른 스케줄링 단계가 필요하다.


5.5.3 Load Balancing

  • 부하 균등화(load balancing)는 SMP 시스템의 모든 프로세서 사이에 부하가 고르게 배분되도록 시도한다.
    • 부하 균등화는 통상 각 프로세서가 실행할 스레드를 위한 자기 자신만의 준비 큐를 가지고 있는 시스템에서만 필요한 기능임을 알아야 한다.
  • 부하 균등화를 위해서는 push 이주(migration)와 pull 이주 방식의 2가지 접근법이 있다.
  • push 이주에서는 특정 태스크가 주기적으로 각 프로세서의 부하를 검사하고 만일 불균형 상태로 밝혀지면 과부하인 프로세서에서 쉬고 있거나 덜 바쁜 프로세서로 스레드를 이동(push)시킴으로써 부하를 분배한다.
  • pull 이주 방식은 쉬고 있는 프로세서가 바쁜 프로세서를 기다리고 있는 프로세스를 pull할 때 일어난다.


5.5.4 Processor Affinity

  • 스레드에 의해 가장 최근에 접근된 데이터가 그 프로세서의 캐시를 채우게 된다.
  • 그 결과 스레드에 의한 잇따른 메모리 접근은 캐시 메모리에서 만족한다.
    • 이것을 warm cache라고 한다.
  • 만약 스레드가 다른 프로세서로 이주한다면 어떻게 되는가.
  • 첫 번째 프로세서의 캐시 메모리의 내용은 무효화 되어야 하며 두 번째 프로세서의 캐시는 다시 채워져야 한다.
  • 캐시 무효화 및 다시 채우는 비용이 많이 들기 때문에 SMP를 지원하는 대부분의 운영체제는 스레드를 한 프로세서에서 다른 프로세서로 이주시키지 않고 대신 같은 프로세서에서 계속 실행시키면서 warm cache를 이용하려고 한다.
    • 이를 프로세서 선호도(processor affinit)라고 한다.
    • 즉, 프로세스는 현재 실행 중인 프로세서에 대한 선호도를 보인다.





References

  1. process, lightweight process, thread - ‘_^乃 ↩

  2. Zabatta, Fabian, and Kevin Ying. “A thread performance comparison: Windows NT and Solaris on a symmetric multiprocessor.” Proceedings of the 2nd USENIX Windows NT Symposium. 1998. ↩

댓글남기기

참고