- 생산자와 소비자 코드가 서로 데이터를 주고받을 때 한쪽을 피호출자 형태로 뒤집어 쓰면, 원래 보이던 알고리듬 구조가 상태 전이에 묻히기 쉬움
- Knuth식 코루틴은 두 루틴이 실행 위치를 저장하며 제어를 주고받는 모델이지만, C의 스택 기반 호출 구조에서는 이식 가능한 방식으로 직접 구현하기 어려움
- 이 글의 핵심 트릭은
switch하위 블록에case를 둘 수 있는 C 문법과__LINE__매크로를 이용해,return이후 위치로 재진입하는 암묵적 상태 기계를 만드는 것임 crBegin,crReturn,crFinish매크로로 압축 해제기와 파서의 원래 루프 구조를 유지할 수 있지만, 보존할 지역 변수는static이어야 하고crReturn을 명시적switch안이나 같은 줄에 두면 안 됨- 실제 코드에서는 재진입성과 멀티스레드 제약 때문에 컨텍스트 구조체를 넘기는 개선형이 필요하며,
coroutine.h는 단순scr매크로와 재진입 가능한ccr매크로를 함께 제공함
생산자와 소비자를 연결할 때 생기는 구조 문제
- 큰 프로그램에서는 한 코드가 데이터를 만들고 다른 코드가 소비하는 경우가 많으며, 이때 어느 쪽이 호출자가 되고 어느 쪽이 피호출자가 될지가 설계를 어렵게 만듦
- 예시는 두 개의 작은 루틴으로 구성됨
- 실행 길이 압축 해제 코드는
getchar()로 입력을 읽고emit()으로 문자를 하나씩 출력함 - 파서 코드는
getchar()로 문자를 읽어 알파벳 연속 구간은WORD, 그 외 문자는PUNCT로 처리함
- 실행 길이 압축 해제 코드는
- 두 루틴은 따로 보면 자연스럽지만, 압축 해제기의
emit()출력이 파서의getchar()입력으로 바로 이어지려면 둘 사이를 연결할 구조가 필요함 - 두 프로세스나 두 스레드 사이의 파이프로도 풀 수 있음
- 압축 해제기의
emit()은 파이프에 쓰고, 파서의getchar()는 반대편에서 읽음 - 이 방식은 단순하고 견고하지만 무겁고 이식성이 낮아, 단순한 작업에 스레드를 나누고 싶지 않은 경우가 많음
- 압축 해제기의
함수 재작성으로 생기는 가독성 손실
- 전통적인 해법은 통신 채널의 한쪽 끝을 호출 가능한 함수 형태로 재작성하는 것임
- 압축 해제기를 매 호출마다 문자 하나를 반환하는 함수로 바꾸면, 기존 파서는
getchar()대신decompressor()를 호출할 수 있음 - 반대로 파서를 문자 하나를 받을 때마다 호출되는 함수로 바꾸면, 기존 압축 해제 코드는
emit()대신parser()를 호출하면 됨 - 둘 다 바꿀 필요는 없고 한쪽만 바꿔도 연결은 가능하지만, 재작성된 코드는 원본보다 훨씬 읽기 어려워짐
- 원래 압축 해제기와 파서는 알고리듬 흐름이 루프 안에 자연스럽게 드러남
- 재작성된 형태는
static상태 변수와switch상태 전이에 의존해, 압축 형식이나 파서 문법을 코드에서 읽어내기 어려움
- 목표는 어느 쪽도 명시적 상태 기계처럼 뒤집어 쓰지 않고 연결하는 것임
Knuth식 코루틴과 C의 한계
- Donald Knuth의 코루틴 해법은 호출자와 피호출자 구분을 버리고, 두 프로세스를 협력하는 동등한 존재로 다룸
- 이 모델의 호출 원리는 일반 함수 호출과 다름
- 현재 실행 위치를 스택이 아닌 별도 위치에 저장함
- 다른 루틴이 마지막으로 저장해 둔 실행 위치로 점프함
- 압축 해제기가 문자를 방출할 때는 자신의 프로그램 카운터를 저장하고 파서의 저장 위치로 이동함
- 파서가 다음 문자를 필요로 할 때는 자신의 프로그램 카운터를 저장하고 압축 해제기의 저장 위치로 이동함
- 제어는 두 루틴 사이를 필요한 만큼 왕복함
- 이 방식은 이론적으로 좋지만, 실제로는 어셈블리어에서만 가능함
- C 같은 고수준 언어는 스택 기반 구조에 의존하므로, 함수 간 제어 이동에서는 한쪽이 호출자이고 다른 한쪽이 피호출자여야 함
- 이식 가능한 C 코드에서 순수 코루틴 방식은 Unix 파이프 해법만큼 실용성이 떨어짐
C에서 흉내 내는 “return and continue”
- C에서 필요한 동작은 피호출자 함수가
return한 뒤, 다음 호출 때 그return바로 다음 위치에서 이어 실행되는 return and continue임 - 예를 들어
for (i = 0; i < 10; i++) return i;형태의 함수가 10번 호출될 때 0부터 9까지 순서대로 반환하면 이상적임 - 첫 구현은 상태 변수와
goto를 사용함- 함수 시작과 각
return뒤에 라벨을 둠 - 호출 간 유지되는
state변수가 다음 재개 라벨을 가리킴 - 함수 시작 시
switch(state)로 적절한 라벨로 이동함 return직전에는 다음 호출 때 돌아올 라벨을state에 저장함
- 함수 시작과 각
- 이 방식은 동작하지만 라벨 관리가 수동이라 유지보수 부담이 큼
return을 추가할 때마다 새 라벨을 만들고 초기switch에도 추가해야 함return을 제거할 때는 대응 라벨도 제거해야 함- 함수 본문과
switch목록의 일관성을 계속 맞춰야 함
Duff’s device로 숨긴 상태 기계
- C의 유명한 Duff’s device는
switch에 대응하는case문을 그 하위 블록 안에도 둘 수 있다는 문법을 활용함 - 이 성질을 코루틴 트릭에 적용하면,
switch가 어떤goto를 실행할지 고르는 대신switch자체가 재진입 점프처럼 작동함 - 기본 형태는 다음과 같음
static int state가 다음 재개 지점을 저장함- 함수 시작에서
switch(state) { case 0: ... }로 진입함 return직전state에 다음case값을 저장함return바로 뒤에 해당case라벨을 둠
- 이를 매크로로 감싸면 코루틴처럼 보이는 인터페이스가 됨
crBegin:static int state=0; switch(state) { case 0:를 숨김crReturn:state를 저장하고 값을 반환한 뒤, 같은 위치에case라벨을 배치함crFinish: 열린 블록을 닫음
crReturn은do ... while(0)로 감싸져 있어if와else사이에서 중괄호 없이 써도 문법 문제가 생기지 않음- 처음에는
crReturn(1, i)처럼 상태 번호를 직접 줘야 하지만, ANSI C의__LINE__매크로를 쓰면 현재 소스 줄 번호를 상태 값으로 사용할 수 있음 - 이 개선 뒤에는
crReturn(x)만 쓰면 되지만, 한 줄에crReturn을 두 개 두면 안 된다는 규칙이 추가됨
매크로 사용 규칙과 예시
- 매크로 기반 코루틴은 몇 가지 규칙을 전제로 함
- 함수 본문을
crBegin과crFinish로 감쌈 crReturn을 넘어서 보존되어야 하는 지역 변수는static으로 선언함- 명시적인
switch문 안에는 절대crReturn을 넣지 않음 __LINE__기반 구현에서는 같은 줄에crReturn을 두 개 넣지 않음
- 함수 본문을
- 압축 해제기 예시는 원래 루프 구조를 유지한 채, 문자를 방출할 때
emit(c)대신crReturn(c)를 사용함 - 파서 예시는 새 문자가 필요할 때
crReturn()으로 호출자에게 돌아가고, 다음 호출에서 매개변수c에 새 문자를 받은 상태로 이어 실행함 - 파서에는 작은 구조 변경이 있음
- 첫 문자가 함수 진입 시 이미
c에 들어 있으므로, 원래 루프 시작 부분의getchar()에 해당하는crReturn이 루프 끝으로 이동함 - 원한다면 파서에 초기화 호출이 필요하다고 정할 수도 있음
- 첫 문자가 함수 진입 시 이미
- 두 루틴을 모두 코루틴 매크로로 바꿀 필요는 없으며, 한쪽만 바꾸고 다른 한쪽은 호출자로 남겨도 됨
- 결과적으로 ANSI C와 전처리기,
switch의 덜 쓰이는 문법을 결합해 생산자와 소비자 사이의 데이터 전달을 명시적 상태 기계 재작성 없이 처리함
코딩 표준과 알고리듬 명확성의 충돌
- 이 기법은 일반적인 코딩 표준을 심하게 위반함
- 매크로 안에 맞지 않는 중괄호가 들어감
- 하위 블록 안의
case를 사용함 crReturn은switch,return,case를 한 매크로 안에 숨김
- 문법 구조를 숨기는 매크로는 코딩 표준상 명확성을 해친 것으로 볼 수 있음
- 그러나 명시적 상태 기계로 재작성한 함수도 작은
case STATE블록과 상태 전이로 구성되어,goto라벨 블록을 나열한 함수와 시각적 구조가 크게 다르지 않음 - 함수가 길어질수록 상태 기계 재작성은 원래 알고리듬 구조를 더 많이 훼손함
- 이 기법은 문법적 구조를 일부 숨기는 대신 알고리듬 구조를 더 잘 드러내려는 절충임
재진입 가능한 개선형과 제공 코드
- 단순한 장난감 구현은
static변수에 의존하므로 재진입 가능하지 않고 멀티스레드에도 적합하지 않음 - 실제 애플리케이션에서는 같은 함수를 여러 컨텍스트에서 호출하고, 각 컨텍스트마다 마지막
return뒤에서 이어 실행할 수 있어야 함 - 개선 방식은 컨텍스트 구조체 포인터를 추가 매개변수로 넘기는 것임
- 지역 상태와 코루틴 상태 변수를 모두 구조체 멤버로 둠
- 루프 카운터 같은 변수도
i대신ctx->i처럼 접근해야 함 - 코드가 조금 더 못생겨지지만, 재진입성 문제를 제거하면서 루틴의 전체 구조는 유지함
- C++ 사용자는 코루틴을 클래스 멤버로 만들고 지역 변수에 해당하는 상태를 클래스 안에 두어 스코프를 더 자연스럽게 처리할 수 있음
- 제공되는
coroutine.h는 이 코루틴 트릭을 미리 정의된 매크로 세트로 구현함scr접두사의 매크로는static변수를 쓰는 단순형임ccr접두사의 매크로는 재진입 가능한 고급형임- 자세한 문서는 헤더 파일 안의 주석에 포함됨
- Visual C++ 6은 기본 디버그 설정인 “Program Database for Edit and Continue”에서
__LINE__매크로를 이상하게 처리해 이 트릭을 싫어함- VC++ 6에서 코루틴 사용 프로그램을 컴파일하려면 Edit and Continue를 꺼야 함
- 프로젝트 설정의 “C/C++” 탭, “General” 범주, “Debug info” 설정에서 “Program Database for Edit and Continue”가 아닌 옵션을 선택해야 함
- 헤더 파일은 MIT 라이선스로 제공됨
관련 참고와 실제 사용
- Donald Knuth의 The Art of Computer Programming, Volume 1, Section 1.4.2는 순수 형태의 코루틴을 다룸
- Tom Duff의 Duff’s device 논의에는 유사한 코루틴 트릭을 독립적으로 떠올렸을 가능성을 시사하는 내용이 있으며, 2005-03-07 업데이트에서 Tom Duff가 블로그 댓글로 이를 확인함
- PuTTY의 SSH 프로토콜 코드는 이 코루틴 트릭을 실제로 사용함
- PuTTY 사례는 심각한 프로덕션 코드에서 보기 드문 강한 C 해킹 수준임