Preemption

  • 인터럽트에 의해 현재 동작 중인 스레드가 다른 thread로 바뀌는 스케쥴링

멀티 태스킹

  • cooperative multi-tasking:

시간 분할 스케쥴링이며, 서로 시간을 양보하며 협력하여 동작

  • preemptive multi-tasking

동작 중인 task를 협조 없이 긴급히 인터럽트하여 context switching을 발생시켜 긴급한 업무를 수행도록 Task B로의 스케쥴링을 한다.

Preemption 종류

1) user preemption in user mode

preempt1

2) user preemption in kernel mode

preempt2

  • syscall을 호출하여 커널 모드에서 동작 시 preemption 요청이 오는 경우 syscall의 완료 후 Task A의 잔여 루틴을 수행하지 않고 Task B로 전환

3) kernel preemption

preempt3

  • syscall을 호출하여 커널 모드에서 동작 시 preemption 요청이 오는 경우 syscall의 완료되기 전이라도 Task A의 잔여 커널 루틴을 수행하지 않고 Task B로 전환
  • 예외로 kernel mode에서 kernel critical sections(raw_spinlock)을 수행시에는 인터럽트가 disable되므로 인터럽트 요청조차 들어오지 않는다.

Preemption 이 일어나는 때?

  • user mode에 있는 경우 syscall(내부 인터럽트)이 호출되거나 외부 인터럽트가 발생 시 preempt 카운터를 확인하고 값이 0인 경우 스케쥴러를 호출하는데 이 때 우선순위 조정에 따라 preemption이 일어난다.
  • kernel mode에 있는 경우는 커널 코드에 설치된 explicit preemption point들이 실행될 때와 외부 인터럽트에 발생한다.

preemption이 일어나는 것을 막아야 할 때?

  • preemption은 동기화 문제를 수반한다.
  • critical section으로 보호받는 영역에서는 preemption이 발생하면 안되기 때문에 이러한 경우 preempt_disable()을  사용한다.
  • preempt_disable() 코드에서는 단순히 preempt 카운터를 증가시킨다.
  • 인터럽트 발생 시 preempt 카운터가 0이 아니면 스케쥴링이 일어나지 않도록 즉 다른 스레드로의 context switching이 일어나지 않도록 막는다.
  • 물론 interrupt를 원천적으로 disable하는 경우도 preemption 이 일어나지 않는다.

RT(Real-Time) Linux

  • 실시간으로 스케쥴링이 필요한 업무가 생기면서 리눅스에 Real Time 기능이 필요하여 RT(Real Time) 리눅스가 구현되고 있다.
  • RT 리눅스 시스템을 지원하게 되면서 preemption이 빠르게 일어날 수 있도록 lock, interrupt 관련 함수들이 복잡하게 수정되었다.
  •  두 개의 패치
    • 1) PREEMPT_RT 패치
      • 전부는 아니지만 많은 코드가 이미 linux mainline에 통합되었다.
      • spinlocks와 local_irq_save()는 더이상 h/w interrupt를 disable하지 않는다.
      • spinlocks는 더이상 preemption을 disable하지 않는다.
      • raw_로 시작하는 spinlocks와 local_irq_save()는 기존 방식을 사용한다.
      • semaphore와 spinlocks는 priority inheritance를 승계한다.
    • 2) Linux(realtime) extensions
      • Priority Scheduling
      • Real-Time signals
      • Clocks and Timers
      • Semaphores
      • Message Passing
      • Shared Memory
      • Asynchronous and Synchronous I/O
      • Memory Locking
    • 그외
      • Threaded Interrupt
      • RT-Mutexes (based priority inheritance protocol)
      • BKL(Big Kernel Lock)-free(2.6.37)

RT Mutex based Priority inheritance protocol

preemption options

PREEMPT_NONE:

  • No Forced Preemption (Server)
  • 성능위주의 스케쥴링으로 커널 preemption 되지 않게 한다.
  • 100hz → 250/1000hz의 낮은 타이머 주기를 사용.
  • context switching을 최소화

PREEMPT_VOLUNTARY:

  • Voluntary Kernel Preemption (Desktop)
  • 사용자 반응을 빠르게하여 일반 데스크탑 시스템에 사용
  • preemption points
    • 커널 모드에서 동작하는 여러 코드에 explicit preemption points를 추가하여 종종 reschedule이 필요한지 확인하여 preemption이 사용되어야 하는 빈도를 높힘으로 preemption latency를 작게하였다.
    • 이러한 preemption 포인트의 도움을 받아 급한 태스크의 기동에 필요한 latency가 100us 이내로 줄어드는 성과가 있었다.
    • preemption point는 보통 1ms(100us) 이상 소요되는 루틴에 보통 추가한다.

PREEMPT:

  • Preemptible Kernel (Low-Latency Desktop)
  • 커널 모드에서도 preemption이 일어나게 한다.
  • 밀리세컨드의 latency가 필요한 데스크탑이나 임베디드 시스템에 사용
  • throughput은 증가시키나 전체적인 성능은 떨어뜨린다.

PREEMPT_RT:

  • 아직 mainline에 등록되지 않았다.
  • 따라서 Real-tIme OS 기능이 필요한 경우 Real-time OS를 연구하는 그룹에서 유지보수하는 리눅스를 사용해야 한다. (계속되고 있는 프로젝트)
  • 사실 full preempt kernel에 대한 고민이 kernel mainliner들에게 있다. 바로 성능 저하인데 이 때문에 아직까지 mainline에 올리지 못하는 이유이기도 하다. (참고: Optimizing preemption | LWN.net)

커널 버전에 따른 preemption 기능

preempt4

  • 커널 버전 2.4에서는 user mode만 선점이 가능했었다. (user mode에서 동작중인 process가 system call API를 호출하여 kernel mode로 진입하여 동작 중인 경우에는 선점 불가능)
  • 버전 2.6에 이르러 kernel mode도 선점이 가능해졌다.  (드라이버 수행 중 또는 system call API를 호출하여 kernel mode에 있는 경우에도 다른 태스크로의 선점이 가능해졌다)
  • kernel mode에서 선점이 가능해졌지만 리눅스가 원래 Real-Time OS 설계가 아닌 관계로 big kernel lock(2중, 3중 critical section 등 사용)으로 인해 필요한 때 인터럽트 응답성이 빠르지 않았다.
  • Real-time 리눅스 커널 패치 PREEMPT_RT가 적용되면서 critical section 및 인터럽트 수행중에서도 preemption이 지원되었다.
    •  SMP 환경에서는 spinlock으로 제어되는 critical section에서 CPU들의 동시 접근 효율이 떨어지면서 문제가 되므로 이를 해결하기 위해 spinlock은 RT 리눅스에서는 preempt_disable을 하지 않도록 mutex를 사용한다. 물론 반드시 preemption이 disable되어야 하는 경우를 위해 그러한 루틴을 위해 raw_spin_lock에서 처리되게 이전하였다.
    • 인터럽트 latency를 줄이기 위해 인터럽트 핸들러를 top-half, bottom-half 두 개의 파트로 나누었다. (Two part interrupt handler | 문c)

소스 분석

preempt_disable()

  • preemption을 정지시키고자 할 때 호출하는데 preempt 카운터를 증가시킨다.
#define preempt_disable() 	\
do { 				\
    preempt_count_inc(); 	\
    barrier(); 		\
} while (0)

preempt_enable()

  • preemption을 동작시키고자 할 때 호출하는데 preempt 카운터를 감소시킨다. preempt 카운터가 0인 경우에만 preemption 기능이 동작한다.
#define preempt_enable() \
do { \
    barrier(); \
    if (unlikely(preempt_count_dec_and_test())) \
        __preempt_schedule(); \
} while (0)

preempt_count_inc()

  • preempt 카운터를 증가시키는 것은 현재 task의 스택 바닥에 위치하는 thread_info 스트럭처의 preempt_count를 증가시킴을 의미한다.
#define preempt_count_inc() preempt_count_add(1)

#define preempt_count_add(val)  __preempt_count_add(val)

static __always_inline void __preempt_count_add(int val)
{
    *preempt_count_ptr() += val;
}

static __always_inline int *preempt_count_ptr(void)
{
    return &current_thread_info()->preempt_count;
}

static inline struct thread_info *current_thread_info(void)
{
    return (struct thread_info *)
        (current_stack_pointer & ~(THREAD_SIZE - 1));
}

__irq_svc(인터럽트 핸들러)

  • TI_PREEMPT 카운터를 보고 svc_preempt루틴을 동작시킬지 결정
__irq_svc:
        svc_entry
        irq_handler

#ifdef CONFIG_PREEMPT
        get_thread_info tsk
        ldr     r8, [tsk, #TI_PREEMPT]          @ get preempt count
        ldr     r0, [tsk, #TI_FLAGS]            @ get flags
        teq     r8, #0                          @ if preempt count != 0
        movne   r0, #0                          @ force flags to 0
        tst     r0, #_TIF_NEED_RESCHED
        blne    svc_preempt
#endif

        svc_exit r5, irq = 1                    @ return from exception
 UNWIND(.fnend          )
ENDPROC(__irq_svc)

svc_preempt  루틴

svc_preempt:
        mov     r8, lr
1:      bl      preempt_schedule_irq            @ irq en/disable is done inside
        ldr     r0, [tsk, #TI_FLAGS]            @ get new tasks TI_FLAGS
        tst     r0, #_TIF_NEED_RESCHED
        reteq   r8                              @ go again
        b       1b
#endif

irq_handler 매크로

        .macro  irq_handler
#ifdef CONFIG_MULTI_IRQ_HANDLER
        ldr     r1, =handle_arch_irq
        mov     r0, sp
        adr     lr, BSYM(9997f)
        ldr     pc, [r1]
#else
        arch_irq_handler_default
#endif
9997:
        .endm

svc_entry 매크로

        .macro  svc_entry, stack_hole=0, trace=1
 UNWIND(.fnstart                )
 UNWIND(.save {r0 - pc}         )
        sub     sp, sp, #(S_FRAME_SIZE + \stack_hole - 4)
#ifdef CONFIG_THUMB2_KERNEL
 SPFIX( str     r0, [sp]        )       @ temporarily saved
 SPFIX( mov     r0, sp          )
 SPFIX( tst     r0, #4          )       @ test original stack alignment
 SPFIX( ldr     r0, [sp]        )       @ restored
#else
 SPFIX( tst     sp, #4          )
#endif
 SPFIX( subeq   sp, sp, #4      )
        stmia   sp, {r1 - r12}

        ldmia   r0, {r3 - r5}
        add     r7, sp, #S_SP - 4       @ here for interlock avoidance
        mov     r6, #-1                 @  ""  ""      ""       ""
        add     r2, sp, #(S_FRAME_SIZE + \stack_hole - 4)
 SPFIX( addeq   r2, r2, #4      )
        str     r3, [sp, #-4]!          @ save the "real" r0 copied
                                        @ from the exception stack

        mov     r3, lr
        stmia   r7, {r2 - r6}

        .if \trace
#ifdef CONFIG_TRACE_IRQFLAGS
        bl      trace_hardirqs_off
#endif
        .endif
        .endm

참고

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.