protothreads 정리

들어가기

protothreads는 멀티스레드가 아닌 이벤트 모델을 기반으로 일반적인 쓰레드 형태의 제한된 제어 흐름을 구현하는 라이브러리이다.

멀티쓰레드에 비교하면, 이벤트 중심 프로그래밍에서는 쓰레드당 할당할 메모리가 필요 없다. 이벤트 중심 모델은 동기식 처리가 지원되지 않기 때문에 상태머신을 사용해서 높은 수준의 제어흐름을 구현할 때에 단일 이벤트 핸들러로 처리하기 힘들다. 또한 이벤트 중심 모델에서 상태머신의 제어흐름을 관리하는게 어렵다. 이로인해 버그가 발생하고 에러발생 가능성이 높아지게 된다.

protothreads는 이런 이벤트 중심 프로그래밍의 복잡도로 인한 에러 발생 가능을 쓰레드 형태의 제어 흐름을 구현함으로써 줄이며, 자원을 효율적으로 활용하게 만든다.

이 글은 Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems[1] 글을 요약 정리한 내용이다.

작성자: ospace114@empal.com, http://ospace.tistory.com/

효용성 측정

prothreads 효용성을 측정하기 위해 세가지 측정치를 사용

• 명시적 상태 머신 개수
• 명시적 전이 개수
• 코드 라인수

Protothreads는 새로운 형태의 프로그래밍을 제공하고 있으며 이를 위한 몇가지 구문들이 있다.

• 조건별 블럭킹 대기 구문 PT_WAIT_UNTIL()을 제공한다.
  • 실행하다가 PT_WAIT_UNTIL()을 만나게되면 인터럽트되는게 아니라 실행이 계속된다.
  • PT_WAIT_UNTIL() 조건은 매번 protothreads에 의해서 호출된다.
• protothread는 스택없다. 그래서 함수 호출에 대한 이력이 없는 대신에 모든 protothread는 같은 스택을 공유해서 사용한다.
• protothread는 시작과 끝은 PT_BEGIN과 PT_END 구문으로 선언한다. progothread 구문은 이 선언 사이에 존재해야 한다.
• protothread 종료를 위해서는 PT_EXIT 구문을 사용한다.

protothread는 이벤트와 쓰레드를 조합해서 사용 가능.

• Scheduling
  • protothreads 작동방식은 실행을 호출하거나 스케줄할 메소드가 별도로 없다.
• Protothreads as Blocking EventHandlers
  • protothreads는 블럭킹 이벤트 핸들러처럼 보임.

예: Hypothetical MAC Protocol

state: {ON, WAITING, OFF}
radio_wake_eventhandler:
    if(state = ON)
        if(expired(timer))
            timer <- t_sleep
            if (not communication_complete())
                state <- WAITING
                wait_timer <- t_wait_max
            else
                radio_off()
                state <- OFF
        elseif (state = WAITING)
            if (communication_complete() or expired(wait_timer))
                state <- OFF
                radio_off()
            elseif (state = OFF)
                if (expired(timer))
                    radio_on()
                    state <- ON
                    timer <- t_awake

아래는 protothread로 구현한 의사코드

radio_wake_protothread:
    PT_BEGIN
    while(true)
        radio_on()
        timer <- t_awake
        PT_WAIT_UNTIL(expired(timer))
        timer <- t_sleep
        if (not communication_complete())
            wait_timer <- t_wait_max
            PT_WAIT_UNTIL(communication_complete() or expired(wait_timer))
        radio_off()
        PT_WAIT_UNTIL(expired(timer))
    PT_END

센서 네트워크에서 MAC 프로토콜의 역할 중에 하나는 장치의 전체 에너지 소비 감소를 위해서 라디오를 오프할 수 있게 허용한다.

그래서 MAC 프로토콜은 스케줄된 슬립 주기를 가지면 라디오를 완벽하게 끈다.

여기에 사용된 hypothetical MAC 프로토콜은 T-MAC 프로토콜과 유사하며 스케줄된 간격마다 라디오를 온과 오프를 수행한다.

실행 과정은 다음과 같다.

1. 라디오를 켬
2. \(t = t_0 + t_{awake}\) 만큼 대기
3. 라디오를 끔, 단 모든 통신이 종료된 경우에만
4. 통신이 종료되지 않았다면, 종료할때까지 대기하거나 \(t=t_0 + t_{awake} + t_{wait_{max}}\) 만큼 대기
5. 라디오를 끔. \(t=t_0 + t_{awake} + t_{sleep}\) 만큼 대기
6. 1단계부터 시작

• Yielding Protothreads
  • 무조건 차단 대기는 PT_YIELD()를 사용
  • 이는 임시로 블럭을 다음번 protothread 호출로 넘겨서 대기
  • stackless coroutines와 유사함
• Hierarchical Protothreads
  • 많은 프로그램이 단일 protothread를 사용하지만 복잡한 연산에서는 계층적 형태로 분리될 수 있음.
  • protothread에서는 PT_SPAWN() 연산을 제공
  • 이는 자식 protothread을 초기화하고 자식 protothread에서 PT_END나 PT_EXIT로 종료될때까지 자신은 실행을 멈춤.
• 세가지 형태의 상태 머신 패턴
  

  

protothread로 표현

• sequence

a_sequence:
    PT_BEGIN
        (* … *)
        PT_WAIT_UNTIL(cond1)
        (* … *)
    PT_END

• iteration

an_iteration:
    PT_BEGIN
        (* … *)
        while(cond1)
            PT_WAIT_UNTIL(cond1 or cond2)
        (* … *)
    PT_END

• selection

a_selection:
    PT_BEGIN
        (* … *)
        if (condition)
            PT_WAIT_UNTIL(cond2a)
        else
            PT_WAIT_UNTIL(cond2b)
        (* … *)
    PT_END

3가지 상태 머신 패턴으로 예제를 표현

C 전처리기로 구현

struct pt { lc_t lc };
#define PT_WAITING 0
#define PT_EXITED 1
#define PT_ENDED 2
#define PT_INIT(pt)          LC_INIT(pt->lc)
#define PT_BEGIN(pt)       LC_RESUME(pt->lc)_
#define PT_END(pt)         LC_END(pt->lc); return PT_ENDED
#define PT_WAIT_UNTIL(pt, c)  LC_SET(pt->lc); if(!(c)) return PT_WAITING
#define PT_EXIT(pt)           return PT_EXITED

#define PT_BEGIN(pt)   { int yielded = 1; LC_RESUME(pt->lc)
#define PT_YIELD(pt)    yielded = 0; PT_WAIT_UNTIL(pt, yielded)
#define PT_END(pt)     LC_END(pt->lc); return PT_ENDED; }

#define PT_SPAWN(pt, child, thread)   PT_INIT(child); PT_WAIT_UNTIL(pt, thread != PT_WAITING)

GCC label-as-value 확장으로 구현한 경우

typedef void *lc_t;
#define LC_INIT(c)   c = NULL
#define LC_RESUME(c)   if (c) goto *c
#define LC_SET(c)       { __label__ r; r: c = &&r; }
#define LC_END(c)

C의 switch 문으로 구현한 경우

typedef unsigned short lc_t;
#define LC_INIT(c)         c = 0
#define LC_RESUME(c)   switch(c) { case 0:
#define LC_SET(c)          c = __LINE__; case __LINE__:
#define LC_END©         }

제약사항

• 자동 변수
  • 함수 로컬에 있는 자동 변수는 사용 불가
• 스위치 사용 제한
  • C switch을 구현을 사용한 경우 switch문 사용 제약
  • 특정한 경우 컴파일 에러 발생
• C 컴파일러 문제
  • 내포된 switch 문에대해서는 제대로 테스트 안됨

대안 접근법

• 어셈블러 언어 사용
• C의 setjump와 longjmp 함수
• stackful 접근

평가

• 코드 복잡성 감소
• 메모리 오버헤드
• 실행 오버헤드

결론

protothread을 찾아본 이유는 넌블럭킹 방식은 코드가 복잡해지고 멀티쓰레드는 컨텍스트스위치나 쓰레드가 가지는 기본 메모리 공간이 소모가 커서 가벼운 멀티쓰레드 방식이 없을까해서 찾아보았다. 생각보다 나쁘지는 않았고 넌블럭킹 방식 코드로 멀티쓰레드 같은 느낌을 준다고 보면 된다. 한가지 걸리는 부분은 protothread도 자체에 문제가 발생할 경우 디버깅하기 쉽지 않겠다는 생각이 들었다.
이글이 여러분에게 도움이 되었으면 하네요. 즐프하세요. ospace.

참고

[1] Adam Dunkels, Oliver Schmidt, Thiemo Voigt, Muneeb Ali, Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems

[2] Adam Dunkels, Oliver Schmidt, Thiemo Voigt, Using Protothreads for Sensor Node Programming