스레드 스케줄링

스레드 스케줄링

스레드 라이브러리

• 프로그래머에게 스레드 생성 및 관리를 위한 API를 제공

• 커널 지원없이 동작하는 사용자 수준 라이브러리

• 커널 수준 라이브러리는 OS에 의해 지원됨

  • 코드 및 데이터 구조는 커널 공간에 존재
  • API함수 호출은 일반적으로 시스템 호출로 변환
  
  

사용자 수준 스레드와 커널 수준 스레드

• 사용자 수준 스레드(User-level threads)

  • 스레드 동작이 사용자 공간에서 발생
  • 스레드는 런타임 라이브러리에 의해 관리됨

• 커널 수준 스레드(Kernel-level threads)

  • 각 스레드는 자신의 실행 문맥을 가짐
  • 스레드는 OS에 의해 관리됨
  
  

N:1 사상

• 사용자는 다수의 스레드를 생성

• OS는 하나의 스레드만 생성

  • 시스템 호출은 전체 프로세스를 멈춤

• 장점

  • 사용자 수준 스케줄링
  • 쉬운 성능 조율
  • OS에 의한 문맥교환을 피할 수 있음
  • 이식싱이 높음

• 단점

  • OS는 스레드를 하나의 프로세스로 인식
  • 프로세스 내 모든 스레드가 단체로 멈춤
  • 멀티프로세서를 이용할 수 없음
  
  

1:1 사상

• 각 사용자 수준 스레드가 하나의 커널 스레드로 사상

• 사용자와 OS는 모두 다수의 스레드를 생성

• 장점

  • 멀티프로세서 환경에서 동시에 여러 스레드가 실행될 수 있음
  • 하나의 스레드가 멈춰도 다른 스레드는 실행 가능

• 단점

  • 너무 많은 커널 스레드를 생성하면 성능이 저하될 수 있음
  • 문맥 교환 오버헤드가 있음
  • 이식성이 저하

• 리눅스의 접근법

  • 스케줄링이 발생하면 프로세스와 스레드를 구분하지 않음. 즉, 1:1 사상
  • Pthreads
  
  

M:N 사상

• 다수의 사용자 스레드가 다수의 커널 스레드로 사상

• 사상은 고정적이지 않기 때문에, 사용자 수준의 스레드 스케줄러가 필요

• 장점

  • 동시성 증가
  • 유연함

• 단점

  • 구현하기 힘듦
  
  

리눅스 스케줄러

• CFS(Completely Fair Scheduler)

• 스케줄링 시 프로세스와 스레드간의 구분이 없음

• 프로세스들에게 공정한 시간 배분을 위해 사용

• 각 프로세스마다 run-queue를 가짐

  • 준비상태인 프로세스들을 가지고 있음

• Nice values

  • -20 ~ 19
  • CFS에서 사용하는 프로세스의 상대적 가중치
  • 낮은 nice value -> 높은 가중치 ----> 높은 우선 순위
  
  

스케줄링 정책

• CFS는 다음 세가지 스케줄링 정책을 구현함

  • SCHED_NORMAL(SCHED_OTHER)
  • SCHED_BATCH
  • SCHED_IDLE
  
  

타임 슬라이스(Time Silce)

• 타임 슬라이스(time silece)

  • 하나의 프로세스가 선점없이 실행할 수 있는 시간 간격
  • 프로세스의 가중치(nice value)에 비례함
  • 지정된 시간에 run-queue에 있는 모든 프로세스를 스케줄 함
  
  

가상 런타임

• 하나의 프로세스에게 제공된 시간 양

  • 프로세스의 가상 런타임이 적을수록 프로세서에 대한 요구는 커짐
  • 프로세스의 누적 실행시간을 가중치를 적용시켜 계산

• 스케줄링 시 가장 작은 가상 런타임을 가진 작업이 다음 작업으로 선택됨

  
  

레드-블랙 트리(Red-black Tree)

• self-balanced tree

• 한 경로의 길이는 어떤 다른 경로의 두 배가 넘지 않음

• 트리에서 발생하는 연산에 걸리는 시간은 O(long n)

  • n은 트리 내 노드 수

• CFS는 레드-블랙 트리로 가상 런타임을 관리

  • run-queue

• 각 프로세서별로 독립적으로 관리

• 가장 작은 가상 런타임을 가진 값은 가장 왼쪽에 있는 리프 노드

  • 가장 큰 값은 가장 오른쪽에 있는 리프 노드

• 스케줄러는 공정성을 위해 가장 왼쪽에 있는 노드를 다음 작업으로 선택

  • 작업 실행 후 그 작업의 가상 런타임을 다시 계산한 후 트리에 삽입
  
  

CFS Algorithm

• 각 scheduling tick에서 스케줄링 수행

• 현재 실행되고 있는 프로세스 P에 할당된 타임 슬라이스를 tick 주기만큼 감소시킴

  • 타임 슬라이스가 0이면 플래그를 셋

• P의 가상 런타임을 업데이트

• 플래그가 셋 되어 있으면 P를 CPU에서 내리고 run-queue를 삽입

  • 그 후 레드-블랙 트리의 가장 왼쪽 노드를 CPU에 스케줄함

• 프로세스들은 CPU 시간을 가장 작게 사용한 순으로 정렬됨(가상 시간)

• 빠른 검색과 삽입을 위해 레드-블랙 트리를 이용해 구현

  
  

SMP 스케줄링

• CFS

  • 단일 프로세서를 위한 스케줄링 방법

• Run-queue 로드 밸런싱(load balancing)

  • 다수의 프로세서를 위한 스케줄링 방법
  
  

스케줄링 도메인(Scheduling Domain)

• 프로세서의 작업량은 커널에 의해 균형있게 관리되어야 함

• 하나 또는 그 이상의 그룹으로 분할됨

• 계층적으로 조직됨

  • 최상위 스케줄링 도메인 : 시스템에 있는 모든 프로세스의 집합
  
  

Run-queue Balancing

• 리밸런싱 틱(rebalancing tick)때 로드 밸런싱 수행

  • Push migration

• 한 스케줄링 도메인의 로드 밸런싱이 매우 불균형하면 계층적으로 점검하여 로드 밸런싱을 이름

  • 도메인에서 가장 바쁜 run-queue 탐색
  • 각 프로세서 또는 그룹별로 업무량을 계산
  • 업무량 : run-queue의 길이
  • 가장 바쁜 run-queue에 있는 프로세스를 다른 run-queue로 이동
  
  

Push vs Pull

• Push migration

  • 주기적으로 각 프로세서의 업무량을 체크하여 업무량이 과도한 프로세서의 프로세스를 업무량이 많지 않은 다른 프로세서로 이동시키는 작업

• Pull migration

  • 유휴 프로세서가 바쁜 프로세서에서 대기하고 있는 프로세스를 가져오는 작업

• 리눅스 스케줄러는 두 기술 모두를 구현

  • 리눅스는 로드 밸런싱 알고리즘을 리밸런싱 틱마다 실행(Push migration)하거나 프로세서의 run-queue가 비면 실행(Pull migration)
  
  

프로세스 이동의 부정적인 효과

• 새 프로세서의 캐시는 이동한 프로세스의 데이터를 갖고 있지 않음
• 데이터를 새 프로세서의 캐시로 가져와야 함