2016년 7월 25일 월요일

An activity-selection problem

16.1-2

Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

->

시작 시간이 가장 늦은 activity를 선택하고 해당 activity의 시작 시간보다 끝나는 시간이 더 큰 activity를 제외한 나머지 activity들로 subset을 구성한 뒤 다시 그 중 시작 시간이 가장 늦은 activity를 선택하는 행동을 반복한다. 주어진 상황에서 최적의 답을 선택하고 나머지 subset 에서 다시 최적을 선택하는 행위를 반복하면서 주어진 문제를 해결할 수 있기 때문에 이는 greedy 알고리즘이다.

-

Activity-selection problem 에서 S 가 시작하는 시간이 가장 늦은 activity 부터 가장 빠른 activity 까지 순서대로 정렬되어 있다고 가정한다.
S에서 시작 시간이 가장 늦은 activity를 am 라고 한다.
S에서 파생되는 임의의 maximum-size subset을 Ak 라고 한다. 그리고 이 Ak에서 시작 시간이 가장 늦은 activity를 aj라고 한다.
만약 am == aj 라면, S의 첫 번째 원소가 Ak의 첫 번째 원소이기 때문에 (시작 시간이 가장 늦은) 이야기는 끝난다.
만약 am != aj 라면, Ak에서 aj를 빼고 am을 넣은 또 다른 subset A'k를 구성한다.
이 때 startTime of am >= startTime of aj 이기 때문에, Ak의 activity들의 시간이 겹치지 않았다면, A'k의 시간도 겹칠 수 없게 된다. A'k의 나머지 원소들의 끝나는 시간은 당연히 aj와 am의 시작 시간보다 빠를 것이기 때문에. 따라서 여전히 A'k는 maximum-size subset이고, A'k는 am을 포함하는 S의 maximum-size subset이라고 할 수 있다. 따라서 earliest start time activity를 선택하는 greedy 알고리즘은 항상 maximum-size subset을 구성할 수 있다.




16.1-3 

Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of least duration from among those that are compatible with previously selected activities does not work. Do the same for the approaches of always selecting the compatible activity that overlaps the fewest other remaining activities and always selecting the compatible remaining activity with the earliest start time.

->

가장 시간이 짧은 activity를 선택하는 경우
A: 0~5
B: 4~7
C: 6~10
이 경우 가장 시간이 짧은 B를 먼저 선택한다면 시간은 가장 짧지만 다른 두 activity의 중간에 겹치고 시간이 짧은 것을 선택함으로 인해서 생기는 공간에 들어갈 수 있는 다른 activity가 없으므로 maximum-size subset을 구할 수 없게 된다.

-

가장 겹치는 activity가 적은 activity를 선택하는 경우

      |--------|                   |-------|
      |--------|                   |-------|
      |--------|                   |-------|
|---------|  |---------| |----------| |--------|
                    |--------|
위 그림과 같이 optimal maximum-size subset 사이에 불필요한 blocker가 있어서 overlap 개수를 높이고, 그 blocker와 겹치지 않은 activity가 있다면 해당 activity가 optimal choice가 아님에 도 불구하고 선택되는 현상이 발생할 수 있다.

-

시작 시간이 가장 빠른 activity를 선택하는 경우

간단하게 반례를 찾을 수 있다. 시작 시간이 가장 빠른 activity가 만약 모든 사용 가능 시간을 점유하는 경우 (끝나는 시간이 가장 길다면) optimal 하지 않다.




2016년 7월 3일 일요일

DB Join algorithm

Introduction to Join Evaluation

  • Join 명령어는 데이터베이스에서 두 테이블을 연결하여 구체화 시키거나 (중간 단계 테이블로 저장) 즉석에서 사용 (이번에는 후자의 경우만 고려한다) 할 수 있게 만들어준다.
  • 가장 많이 사용되는 명령어 중 하나로 최적화가 잘 돼있다.
  • 조인 알고리즘의 목표는 이러한 연결을 더 효율적으로 잘 하는 것이다.

Simple Nested Loops Join

For each tuple r in R do
     For each tuple s in S do
        If r and s satisfy the join condition
           Then output the tuple <r,s>


Block Nested Loops Join

  • 기존의 SNLJ에서 |R| < |S| 라고 가정한다면, S는 R의 모든 튜플에 대하여 한 번씩 스캔이 될 것이다. 만약 조건을 만족하는 R 튜플이 많다면, 그리고 S에 조인을 위한 인덱스가 없다면 이 비용은 배우 비쌀 것이다.
  • BNLJ는 R 튜플의 "묶음" 당 한 번의 S 스캔을 실행함으로 효율을 높인다.
  • 예를 들면 BNLJ의 방식 중 하나는 R 튜플의 모든 페이지를 메모리로 읽고 hash table 으로 로드한다. 그리고 S를 스캔할 때 hash table을 이용하여 현재 로드된 R의 페이지의 어떤 튜플이라도 매치하는 S의 튜플을 찾는다. 이렇게 하여 S의 스캔 횟수를 줄일 수 있다.
    • DB에서 성능에 중요한 부분은 디스크 I/O가 일어나는 횟수인데 이가 줄어든다.
  • 또 다른 변형은 R의 페이지를 가능한 많이 메모리에 로드하여 모두 hash table화 하는 것이다. 그리고 반복적으로 S를 스캔한다. 이렇게 하면 S의 스캔 횟수를 더 줄일 수 있다. 
    • 사실 이러한 알고리즘은 따로 분류되어 hash join 알고리즘이라 불린다.

Index Nested Loops Join

  • 기존의 접근 방법은 R x S 을 항상 실행하고 존재하는 인덱스를 사용하지 않는 문제가 있다.
  • 만약 한 릴레이션 (S라고 하자)의 join 열에 인덱스가 있다면 이 릴레이션을 inner로 만들고 이 인덱스를 사용하지 않을 이유가 없다.
    • outer 릴레이션 R을 스캔 한다 (한 번에 한 페이지씩).
    • R의 각 튜플 r에 대해 인덱스를 이용하여 S에서 일치하는 튜플을 찾아낸다.
  • eqi-join 인 경우에 사용한다. 다른 경우에도 사용할 수는 있지만 매우 효율이 좋지 않음.
  • Nested Loop Join과 같은 방식으로 읽어오고 비교한다.
  • Cost of Indexed-Nested Loop
    • worst cast (r 테이블의 한 개 블록만 메모리에 수용)
      • C = bi + nr * c
        • c는 r의 튜플과 조인조건을 만족하는 s의 튜플을 찾는 비용이며, 접근한 인덱스의 노드 블록의 수가 비용이 됨.
    • 만약 r과 s 두 개 릴레이션 모두에 조인 애트리뷰트에 대한 인덱스가 사용 가능하다면?
      • 큰 릴레이션을 inner로(인덱스를 사용하는 쪽으로) 보낸다.
      • 비용 c의 높이는 인덱스 트리의 높이에 비례해서 급격하게 줄어든다.
        • 트리에서 찾는 비용은 O(lg n) 이니까..

Sort-Merge Join

  • R x S의 생성을 피하는 또 다른 방법으로 SMJ가 있다.
  • 인덱스가 없을 때 SNLJ 보다 좋은 성능을 내기 위해 사용.
  • 동등 조인 조건에 대해서만 수행이 가능하다.
    • 동등 조인이란: Equi 조인이라고도 하며, 공통 컬럼의 동등 비교만을 한다.
    • 즉 <, > 등의 부등호는 사용하지 않고 ON a.col1 = b.col2 처럼 동등한 경우만을 고려한다.
  • SMJ는 두 단계로 나뉜다.
    • 정렬 단계
      • external sort 알고리즘을 사용하여 R과 S를 조인 속성을 기준으로 정렬한다.
    • 병합 단계
      • 두 릴레이션을 병합하며 R과 S에 속해있는 튜플을 찾아낸다.
      • 병합 단계는 SNLJ과 비슷하지만 차이는 정렬되어 있다는 것이고, 동등 조인 조건에서만 가능하므로 동등 조건이 아니면 병합을 시도하지 않는 것이다.

Hash Join

  • 비용이 가장 많이 들어가는 조인 방법이지만 대용량 데이터 조인 시 Sorted 나 Nested Loop 보다 좋은 성능을 나타낸다.
  • 조인에 참여한 두 집합 중 작은 집합 (Build input) 의 해쉬 테이블을 메모리상에 만들고  큰 집합 (Probe Input) 은 조인을 위해 해쉬 테이블을 검색한다.
  • 따라서 조인 과정에서 발생하는 부하가 없으나, hash table 생성 비용이 크다. 따라서 Build Input이 작을 때라야 효과적이다.
  • 이용 가능한 hash area의 크기에 따라 성능에 영향을 받는다.
  • 이용 가능한 메모리가 작은 집합을 유지할 정도로 충분히 크지 않다면 두 집합을 좀 더 작은 단위로 나누게 되는데, 이를 파티션이라고 한다.

2016년 6월 24일 금요일

XOR을 이용한 암호화

XOR은 CPU에서 제공하는 연산으로, 이 연산의 [A ^ B = C 의 경우 두 값을 알면 나머지 한 값도 알 수 있다]는 성질을 이용하여 암호화를 할 수 있다.

XOR을 이용하여 암호화를 진행하면 다음과 같은 모양이 된다.


평문을 16진수로 바꾸어(아스키 코드) 키와 XOR 연산을 했고, 그 결과를 가지고 있다가 복호화 해야 하는 경우 다시 나만 알고 있는 키로 XOR 하여 원문을 구할 수 있다.

아주 빠른 속도로 암호화/복호화를 할 수 있지만 단점이 많다. 가장 큰 문제는 뚫기가 쉽다는 것. 키의 크기와 키 자체를 알아내기가 쉽다.

만약 어떤 프로그램에서 채팅을 암호화 한다고 하면(난이도를 쉽게 하기 위해) 채팅창에  "AAAAAAAAAAAAAAAAAAA"라고 써본다. 그리고 날라가는 패킷을 보면

6E2AE83 6E2AE83 6E2AE83 6E2AE83 .... 6E2AE83 6E2AE83 6E2AE83 6E2AE83

이렇게 돼 있는 것을 볼 수 있을 것이다. 만약 XOR을 사용해서 암호화 했다는 것을 알면 (가장 흔한 방법임으로 한 번 시도해볼 수 있음) 패킷을 보면 같은 문자인데 4바이트 단위로 암호화된 문자가 반복되고 있다는 것을 알 수 있다. 

그러면 이제 다음을 계산해본다.

6E2AE83 XOR 41414141 (AAAA의 아스키 코드 값)

그럼 계산기에 다음과 같은 값이 나오고, 그 값은 KEY가 된다.

47A3EFC2

이렇듯 쉽게 키를 알아낼 수 있고, 키를 알아내지 않더라도 전달되는 데이터의 일부를 변경할 수 있다는 문제점도 있다. 단순히 특정 비트-바이트의 값을 수정하는 것 만으로도 원하는 데이터를 변형할 수 있다.


2016년 6월 20일 월요일

Storing(데이터 저장)


Database in Files

  • 데이터베이스는 파일의 집합으로 저장된다. 각 파일은 레코드의 연속이고, 레코드는 필드의 연속이다.
  • 간단한 접근
    • 레코드의 크기가 정해져 있다
    • 각 파일은 한 가지 타입의 레코드로만 이루어져 있다
    • 서로 다른 파일은 서로 다른 릴레이션을 위해 사용된다. 이 경우가 가장 구현하기 쉽다. 가변 길이 레코드는 나중에 살펴본다
  • Fixed-Length Records (고정 길이 레코드, 크기 n)
    • i 번째 레코드는 byte n * (i - 1) 에 위치한다
    • 레코드의 접근은 간단하지만 레코드가 디스크 블록에 걸쳐서 나뉘어질 수 있다
      • 하지만 레코드가 경계에 걸쳐있지 않게 해야 한다
  • 레코드의 삭제
    • 레코드를 실제로 지우는 것이 아니라 삭제할 레코드를 free list 에 링크한다


Free List

  • 첫 번째로 삭제된 레코드의 주소를 파일의 헤더에 저장한다
  • 이 첫 번째 레코드에 두 번째로 삭제된 레코드의 주소가 저장된다. 계속 반복한다 (linked list)
  • 주소가 저장된다는 것은 해당 레코드의 주소를 가리키는 "포인터"를 저장한다는 것이다
  • 공간 효율을 높이기 위해서
    • 일반 값들을 저장하기 위해 있는 공간을 재사용 하여 다음 빈 레코드의 포인터를 저장한다
    • 사용 중인(값이 들어있는) 레코드에는 포인터를 저장하지 않는다
  • 새 레코드를 추가할 때 free list의 항목들을 사용한다

Variable-Length Records

  • 가변 길이 레코드는 데이터베이스 시스템에서 몇 가지 경우에 가끔 사용된다
    • 한 파일에 여러 타입의 레코드를 저장할 때
    • 레코드의 타입이 한 개 이상의 필드에서 가변 길이를 허용할 때
  • 가변 길이 레코드는 Slotted Page Structure를 가진다
    • 파일은 페이지의 집합이다
    • Slotted Page의 헤더는 다음의 정보를 포함한다
      • 레코드 엔트리의 개수
      • 블록의 빈 공간의 마지막의 위치
      • 각 레코드의 위치와 크기
      • 페이지 안에서 레코드의 위치가 옮겨질 수 있다. 이렇게 하면 각 레코드 사이에 빈 공간이 없이 유지할 수 있다. 이를 위해 헤더의 레코드에 대한 진입점이 업데이트 되어야 한다
    • 포인터는 레코드를 직접적으로 가리키면 안 된다
      • 대신 레코드는 헤더에 저장된 레코드에 대한 진입점을 가리켜야 한다


Organization of Records in Files

  • Heap
    • 레코드의 위치는 파일 안에 공간이 있다면 어디던 위치할 수 있다
  • Sequential
    • 각 레코드의 search-key를 기준으로 레코드를 순서대로 저장한다
  • Hashing
    • 각 레코드의 일부 속성에 해시 함수가 계산되어 있다
      • 결과는 파일 내 어떤 블록에 레코드가 위치해야 할지 알려준다
  • 각 릴레이션의 레코드는 서로 다른 파일에 저장될 수 있다. 
  • multi-table clustering file organization 에서는 서로 다른 릴레이션의 레코드가 같은 파일에 저장될 수 있다
    • 연관된 레코드를 같은 블록에 저장함으로써 I/O를 최소화하기 위함이다

Sequential File Organization

  • 모든 파일을 순서대로 접근해야 하는 경우에 적합하다
  • search-key를 기준으로 레코드 내 파일이 정렬된다
    • 정렬된 파일은 효율적으로 검색이 가능하지만 유지하기가 어렵다
  • 삭제
    • 포인터 체인을 이용하여 삭제된 튜플을 건너뛴다
  • 삽입
    • 레코드가 삽입되어야 할 위치를 찾는다
      • 만약 빈 공간이 있으면 그 곳에 삽입한다
      • 만약 없다면, overflow block에 삽입한다
      • 두 경우 모두 포인터 체인이 갱신 되어야 한다

Multi-table Clustering


  • 멀티 테이블 클러스터링을 사용하여 여러 개의 관계를 한 개의 파일에 저장한다
    • 여러 개의 릴레이션을 모두 조회해야 하는 쿼리에는 적합하다
    • 한 개의 릴레이션만 조회해야 하는 쿼리에는 좋지 않다
  • 다양한 크기의 레코드가 결과로 나온다
  • 포인터 체인을 추가하여 특정 릴레이션의 레코드를 연결할 수 있다


Data Dictionary Storage

  • Data Dictionary( 혹은 system catalog )는 메타데이터를 저장한다
    • 릴레이션들에 대한 정보
      • 릴레이션의 이름
      • 각 릴레이션의 속성의 타입의 이름
      • 뷰의 정의와 이름
      • 제약 조건
    • 사용자와 비밀번호 같은 접근 정보
    • 뷰와 그 뷰의 정의
    • 물리적인 파일 구조 정보
      • 어떻게 릴레이션이 저장되어 있는가(sequential/hash/...)
      • 릴레이션의 물리적 위치
      • 인덱스
    • 카탈로그식 구조
      • 디스크의 관계적 표현
    • 카탈로그 표현의 예
      • 릴레이션의 집합

2016년 5월 26일 목요일

공간 변환: 투영 행렬 정리

공간 변환


Object Space(Local Space or Model Space) : 물체가 기준인 공간

World Space : 모든 물체가 공유하는 공간. 실제 세상 공간.

View Space(Camera Space) : 카메라가 세상의 중심인 공간. 카메라 기준으로 World를 바라본 공간.

Projection Space : View Space를 투영한 공간. x, y는 -1~1까지의 좌표를, z는 0~1까지의 좌표를 가짐.

Screen Space : 화면 공간. 왼쪽 상단이 (0, 0)으로 시작하여 (w-1, h-1)까지의 좌표를 가짐.


Local Space -> World Space


물체가 중심인 세상에서 월드 공간으로 나온다는 것은
크기(Scale), 회전(Rotation), 이동(Translation)
즉 W=SRT라고 할 수 있고 행렬은 다음과 같다


World Space -> Camera Space


월드 공간에서 어느 하나의 오브젝트가 중심인 공간으로 공간 변환을 한다는 것은 World Space에서 해당 오브젝트의 Local Space로 이동하는 것과 같다.

다시 말해, World Marix는 해당 오브젝트가 세상에 나오기 위한 행렬이었으므로, 특정 오브젝트가 중심인 공간으로 변환한다는 것은 해당 오브젝트의 World Matrix의 역 행렬을 사용하면 된다.

그래서 카메라가 중심인 Local Space에서 World Space로 나오기 위한 행렬 W의 역 행렬을 구하면 그 행렬이 카메라가 중심인 공간(Camera Space)으로의 변환 행렬을 뜻한다고 할 수 있다.

또한 World Space와 Camera Space는 동일 공간상의 변환이므로 크기 변환은 제외되어 있다고 할 수 있다. 즉 W=SRT 이므로, W=RT로 생각해볼 수 있으며, 그 역행렬은 W-1 = T-1R-1으로 표현 가능하다.


Camera Space -> Projection Space


FOV(field of view) : 시야각

Aspect Ratio(종횡비) : screen width/ screen height

Projection Window는 Near Plane과 Far Plane과 동일한 비율을 가지므로 실제 크기는 중요치 않다.

그래서 Near Plane과 Projection Window를 동일하게 보는 경우가 많다.

그런 이유로 r(=width/height)을 구할 때 실제 크기보다 비율이 중요하므로 height를 2로 하여(위/아래 각각 1) 단순화 시켜서 계산하도록 한다.






d와 r이 구해지면 β를 구할 수 있다. 식의 r에 의해 β는 계속 변화한다.


3차원 공간상의 점 (x, y, z)를 투영공간에 변환한 점 (x', y', z')은 비례값에 의해 
라고 할 수 있으므로, 다음의 식이 성립한다.


y값 또한 마찬가지로 x의 위치에 대신 올 수 있다.

이렇게 구한 값에 따라

x'는 -r <= x' <= r
y'는 -1 <= y' <= 1
z는 n <= z' <= f

일 때 절두체 내부에 있다고 할 수 있다.

앞선 방식은 r에 의해 x', y'의 값이 좌우된다. 즉 하드웨어에서 계산을 하기 위해서 항사 r(Aspect ratio)를 필요로 한다는 문제가 생긴다.

이를 단순화 하기 위해 NDC(Normalized Device Coordinates) 좌표로 변환을 한다.
x'와  y'에 대해서 r로 나누는 것이다.

이를 통해 범위는 다음으로 조정 가능하다.
r로 나눈 값에 의해 x'는 NDC 좌표계에서 다음과 같이 표현 가능하다.
x, y는 선형 연산이 가능하나 z는 선형 변환이 되지 않는다.(z로 나누어 투영을 처리하기 때문)
그래서 z 나누는 연산을 나중으로 미뤄두고 선형행렬을 구성한다.



z축 값에는 x, y의 값이 없으므로 0.
A, B는 무슨 값이 들어갈지 모르므로 상수 A, B를 설정

나중에 z로 나누기 위해서는 z값이 존재해야 하는데 동차 좌표상의 w값에 이 값을 잠시 복사해두면 된다. 
그래서 3행 4열 성분과 4행 4열 성분을 각각 1과 0으로 설정

계산의 편의를 위해 각 성분에 z를 곱해버린다.


최종적으로 구해진 (zx', zy', zz', z)를 w 값인 z로 나누면 다음과 같다.


투영된 z의 값(=z')은 0~1의 범위를 가져야 한다. (깊이 테스트를 위한 것)
이를 위해 구해진 다음의 식을 풀어야 한다.
z에 0과 1을 대입하여 B에 대해서 풀면 B = -An이 나오고 이에 따라 식을 풀면 다음과 같다.



이제 앞서 구해놓은 투영 행렬에 새로 구한 A, B의 값을 채운다.

이렇게 구해진 z의 값은 다음과 같은 그래프 모양으로 나타난다. 카메라에서의 거리가 가까울수록 깊이에 대한 묘사가 섬세해진다.


2016년 5월 16일 월요일

C++ 상태 머신 디자인

http://www.codeproject.com/Articles/1087619/State-Machine-Design-in-Cplusplus

의 글을 번역 및 정리하였습니다.




등장 배경


많은 개발자들이 사용하는 디자인 테크닉으로 유한상태머신(FSM)이 있습니다. 복잡한 프로그램을 상태와 상태 전이로 나누어 정복하는 것인데, 많은 구현 방법이 있습니다.

스위치 문을 사용하여 구현하는 것은 가장 쉽고 흔한 방법입니다. 보통 다음과 같이 구현합니다.

switch (currentState) {
   case ST_IDLE:
       // do something in the idle state
       break;
    case ST_STOP:
       // do something in the stop state
       break;
    // etc...
}

이 방법은 많은 경우에 적합한 방법이지만, 이벤트 기반의 멀티 스레드 프로젝트에 적용하려면 상당히 제한됩니다.
첫 번째 문제는 어떤 상태 전이가 유효하고 어떤 것이 유효하지 않은지 조절하는 것입니다. 모든 상태 전이는 어떤 상황에도 허용되는데 이 경우 적합하지 않습니다. 이러한 전이를 강제할 방법이 없습니다.
또 다른 문제는 특정 상태로 데이터를 전달하는 것입니다. 모든 상태 머신이 한 개의 함수에 존재하므로 추가적인 데이터를 주고받은 것이 어렵습니다.
마지막으로 멀티 스레드 환경에 적합하지 않습니다. 상태 머신이 싱글 스레드에서만 불려지도록 해야합니다.


상태 머신을 왜 사용할까요?


상태 머신을 사용하여 코딩을 하면 복잡한 문제를 단순화하기에 매우 좋습니다. 프로그램을 우리가 상태라고 불리는 것들로 나누고 각 상태는 제한된 동작만을 수행합니다. 이벤트 들은 자극으로, 상태머신이 상태 사이에서 이동하거나 전환하도록 합니다.

간단한 예제를 위해 자동차 프로그램을 만들어 봅시다. 자동차가 출발하고 정지해야 되고 속력도 바뀌어야 합니다. 클라이언트에 노출되는 이벤트는 다음과 같을 것입니다.

1. Set Speed - 자동차의 속력을 특정 속도로 조절합니다
2. Halt - 자동차를 멈춥니다

멈춰있는 자동차를 특정 속력으로 바꾸어 움직이기 시작하거나 이미 움직이고 있는 자동차의 속력을 바꿀 수 있습니다. 또한 멈출 수도 있죠. 자동차 프로그램에서 이 두 이벤트 혹은 함수는 외부 이벤트로 정의됩니다. 하지만 사용하는 클라이언트의 입장에서는 그냥 클래스 안의 함수이겠지요.

이 이벤트들이 상태머신은 아닙니다. 이 이벤트를 이용하는 방법은 상태마다 다릅니다. 이 경우 상태들은 다음과 같습니다.

1. Idle - 자동차가 움직이지 않고 있는 상태
   - 아무것도 하지 않음
2. Start - 멈춰있는 자동차를 움직임
   - 자동차에 전원을 넣음
   - 속력을 변경함
3. Change Speed - 이미 움직이고 있는 자동차의 속력을 조절함
   - 속력을 변경함
4. Stop - 자동차를 멈춤
   - 전원을 끔
   - Idle 상태로 변경함

이렇게 다양한 상태로 나누면 어떻게 자동차를 움직여야 할지, 그 규칙을 더 쉽게 정의할 수 있게 됩니다.

모든 상태머신은 "현재 상태"라는 개념이 있습니다. 현재 상태머신의 상태를 의미합니다. 프로그램이 실행 중일 때 상태머신은 단 한 개의 상태만 가질 수 있습니다. 상태머신 클래스가 생성될 때 construction에서 특정 상태가 주어집니다. 그런데 이 상태는 실행되지는 않고 이벤트가 주어져야만 실행됩니다.

이 자동차 제어 프로그램의 상태도는 다음과 같습니다. 각 상자는 상태를 나타내고 화살표로 연결되어 있습니다. 이름이 적혀있는 화살표는 외부 이벤트이고, 이름이 없는 화살표는 내부 이벤트입니다. 외부 이벤트와 내부 이벤트의 차이는 추후 설명합니다.


이벤트가 도착했을 때 상태변이는 현재 머신의 상태에 따라 달라집니다. SetSpeed 이벤트가 도착했을 때 만약 자동차가 Idle 상태이면 Start 상태로 변이됩니다. 하지만 같은 SetSpeed 이벤트가 오더라도, 자동차가 Start 상태이면 자동차가 ChangeSpeed 상태로 전이됩니다. 또한 모든 상태 변이가 가능한 것은 아님을 확인할 수 있습니다. 예를 들어 자동차는 ChangeSpeed 상태에서 Stop을 거치지 않고 바로 Idle 상태로 갈 수 없습니다.


외부 이벤트와 내부 이벤트


이벤트란 상태머신이 상태 사이에서 전이되게 하는 자극입니다. 예를 들면 버튼이 눌리는 것이 이벤트가 될 수 있죠. 이벤트는 두 종류로 나뉩니다. 외부 이벤트와 내부 이벤트죠.

외부 이벤트는 가장 기본적인 개념에서, 상태머신 오브젝트를 호출하는 함수입니다. 이러한 함수는 퍼블릭이고 상태머신 밖에서 불릴 수 있습니다. 시스템의 어떤 스레드나 작업이라도 외부 이벤트를 발생시킬 수 있죠. 반면 내부 이벤트는 상태머신의 상태 실행 도중 자동으로 생성되는 이벤트입니다.

외부 이벤트가 발생하면 상태머신의 현재 상태를 기반으로 어떤 전이가 일어나야 하는지 찾아집니다. 찾아지면 전이가 일어나고 그 상태의 코드가 실행됩니다. 상태 함수가 끝나면 내부 전이가 일어났는지 체크합니다. 만약 있었다면 다른 상태전이가 일어나서 새로운 상태가 실행됩니다. 이 과정은 상태머신이 더 이상 내부 이벤트를 생성하지 않을 때까지 반복됩니다. 즉, 첫 번째 외부 함수 호출이 리턴 될 때 까지요. 이 모든 것은 호출자의 스레드에서 일어납니다.

한 번 외부 이벤트가 발생해서 상태머신이 동작하면 다른 외부 이벤트에 의해서 방해받을 수 없습니다. 이러한 모델은 상태전이시 멀테스레드에서 안전한 동작을 제공합니다. 세마포나 뮤텍스를 사용하여 다른 스레드의 접근을 막습니다. 소스코드의 ExternalEvent()를 확인하세요.


이벤트 데이터


이벤트가 생성될 때 상태 함수가 이용할 수 있는 데이터를 추가적으로 가지고 갈 수 있습니다. 상태의 실행이 끝나면 이벤트 데이터는 다 사용됬다고 보고 삭제됩니다. 따라서 상태머신에 전송된 모든 데이터는 new를 통해서 힙 영역에 올라가야 합니다. 또한 이러한 구현을 위해서 이벤트 데이터는 EventData 베이스 클래스를 상속받아야 합니다. 이렇게 하면 상태머신이 어떤 데이터를 지울지 알 수 있습니다.

class EventData 
{
public:
    virtual ~EventData() {}
};


상태 전이

외부 이벤트가 생성될 때, 행동의 상태전이를 결정하기 위한 검색이 실행됩니다. 이벤트에 대한 결과는 세 가지 경우가 있습니다. 새로운 상태, 이벤트 무시, 실행될 수 없음. 새로운 상태는 실행 가능한 새로운 상태로의 전이를 일으킵니다. 지금 실행 중인 상태로의 전이도 가능합니다. 현재 상태가 재실행 됩니다. 이벤트 무시의 경우 상태가 실행되지 않습니다. 그리고 이벤트 데이터는 삭제됩니다. 마지막 실행될 수 없는 경우는 이벤트가 현재 상태에서 유효하지 않은 경우입니다. 시스템이 중지됩니다.

이것을 구현할 때 내부 이벤트는 전이 유효를 검사할 필요가 없습니다. 유효하다고 가정됩니다. 유효한 내부 이벤트를 검사할 수도 있지만 예제에서 이렇게 하는 것은 작은 효과를 위해 많은 공간과 시간을 낭비하는 것입니다. 전이 유효성을 검사하는 것은 비동기 외부 이벤트에서 클라이언트가 적합하지 않은 시간에 이벤트를 발생시키는 것을 검사하는 것입니다. 상태머신은 실행중에는 방해될 수 없습니다. 크래스의 프라이빗 구현이 컨트롤 하며 전이 체크가 무의미합니다. 이렇게 하면 많은 전이 테이블을 관리할 필요 없이 디자이너에게 자유롭게 내부 이벤트를 통해 상태를 바꿀 수 있게 해줍니다.


상태머신 클래스


여러분의 상태머신을 만들 때 두 가지 베이스 클래스가 필수적입니다. StateMachine과 EventData 입니다. StateMachine을 상속받는 클래스는 상태 전이에 필수적인 메커니즘과 이벤트 핸들링을 상속받습니다. 상태 함수에게 고유한 데이터를 전송하기 위해 해당 구조는 반드시 EventData를 베이스 클래스로 상속받아야 합니다.

class StateMachine 
{
public:
    enum { EVENT_IGNORED = 0xFE, CANNOT_HAPPEN };

    StateMachine(BYTE maxStates, BYTE initialState = 0);
    virtual ~StateMachine() {}

    BYTE GetCurrentState() { return m_currentState; }
    
protected:
    void ExternalEvent(BYTE newState, const EventData* pData = NULL);
    void InternalEvent(BYTE newState, const EventData* pData = NULL);
    
private:
    const BYTE MAX_STATES;
    BYTE m_currentState;
    BYTE m_newState;
    BOOL m_eventGenerated;
    const EventData* m_pEventData;

    virtual const StateMapRow* GetStateMap() = 0;
    virtual const StateMapRowEx* GetStateMapEx() = 0;
    
    void SetCurrentState(BYTE newState) { m_currentState = newState; }

    void StateEngine(void);     
    void StateEngine(const StateMapRow* const pStateMap);
    void StateEngine(const StateMapRowEx* const pStateMapEx);
};

StateMachine은 이벤트를 핸들링하고 상태 전이를 위해 사용되는 베이스 클래스입니다. 인터페이스는 다음 네 개의 함수 안에 담겨있습니다.

void ExternalEvent(BYTE newState, const EventData* pData = NULL);
void InternalEvent(BYTE newState, const EventData* pData = NULL);
virtual const StateMapRow* GetStateMap() = 0;
virtual const StateMapRowEx* GetStateMapEx() = 0;

ExternalEvent()는 상태 머신에게 외부 이벤트를 생성하며 새로운 상태와 EventData 오브젝트에 대한 포인터를 인자로 가지고 있습니다. InternalEvent() 함수는 같은 인자를 사용하여 내부 이벤트를 생성합니다.

GetStateMap()과 GetStateMapEx()함수는 StateMapRow이나 StateMapRowEx 객체의 배열을 반환하는 함수로 적당한 시점에 상태 엔진에 의해 호출됩니다. 상속받는 클래스는 이 중 하나의 함수를 사용하여 배열을 반환해야 합니다. 만약 상태머신이 상태 함수만 가지고 있다면 GetStateMap()을 사용하고, guard/entry/exit 기능이 필요하다면 GetStateMapEx()이 사용됩니다. 다른 사용하지 않는 버전은 반드시 NULL을 반환해야 합니다. 하지만 곧 설명할 멀티라인 매크로가 이 함수의 구현을 위해 제공됩니다.



자동차 예제



Motor와  MotorNM 클래스는 어떻게 StateMachine을 사용하는지에 대한 예제입니다. MotorNM(No Macro)는 Motor의 디자인과 정확히 일치하지만 매크로를 사용하지 않습니다. 모든 매크로를 사용된 코드를 더 쉽게 이해할 수 있게 해줍니다. 하지만 매크로는 필요한 소스를 기계적으로 감추어주어 사용성을 극대화합니다.

아래 구현된 MotorNM 클래스는 매크로를 포함하고 있지 않습니다.


class MotorNMData : public EventData
{
public:
    INT speed;
};

// Motor class with no macros
class MotorNM : public StateMachine
{
public:
    MotorNM();

    // External events taken by this state machine
    void SetSpeed(MotorNMData* data);
    void Halt();

private:
    INT m_currentSpeed; 

    // State enumeration order must match the order of state method entries
    // in the state map.
    enum States
    {
        ST_IDLE,
        ST_STOP,
        ST_START,
        ST_CHANGE_SPEED,
        ST_MAX_STATES
    };

    // Define the state machine state functions with event data type
    void ST_Idle(const NoEventData*);
    StateAction<MotorNM, NoEventData, &MotorNM::ST_Idle> Idle;

    void ST_Stop(const NoEventData*);
    StateAction<MotorNM, NoEventData, &MotorNM::ST_Stop> Stop;

    void ST_Start(const MotorNMData*);
    StateAction<MotorNM, MotorNMData, &MotorNM::ST_Start> Start;

    void ST_ChangeSpeed(const MotorNMData*);
    StateAction<MotorNM, MotorNMData, &MotorNM::ST_ChangeSpeed> ChangeSpeed;

    // State map to define state object order. Each state map entry defines a
    // state object.
private:
    virtual const StateMapRowEx* GetStateMapEx() { return NULL; }
    virtual const StateMapRow* GetStateMap() {
        static const StateMapRow STATE_MAP[] = { 
            &Idle,
            &Stop,
            &Start,
            &ChangeSpeed,
        }; 
        C_ASSERT((sizeof(STATE_MAP)/sizeof(StateMapRow)) == ST_MAX_STATES); 
        return &STATE_MAP[0]; }
};

비교를 위해 Motor 클래스는 매크로를 사용합니다.

class MotorData : public EventData
{
public:
    INT speed;
};

// Motor class using macro support
class Motor : public StateMachine
{
public:
    Motor();

    // External events taken by this state machine
    void SetSpeed(MotorData* data);
    void Halt();

private:
    INT m_currentSpeed; 

    // State enumeration order must match the order of state method entries
    // in the state map.
    enum States
    {
        ST_IDLE,
        ST_STOP,
        ST_START,
        ST_CHANGE_SPEED,
        ST_MAX_STATES
    };

    // Define the state machine state functions with event data type
    STATE_DECLARE(Motor,     Idle,            NoEventData)
    STATE_DECLARE(Motor,     Stop,            NoEventData)
    STATE_DECLARE(Motor,     Start,           MotorData)
    STATE_DECLARE(Motor,     ChangeSpeed,     MotorData)

    // State map to define state object order. Each state map entry defines a
    // state object.
    BEGIN_STATE_MAP
        STATE_MAP_ENTRY(&Idle)
        STATE_MAP_ENTRY(&Stop)
        STATE_MAP_ENTRY(&Start)
        STATE_MAP_ENTRY(&ChangeSpeed)
    END_STATE_MAP    
};

Motor는 이론적으로 우리의 자동차 제어 상태머신을 구현합니다. 고객은 특정한 속도로 자동차를 출발시키거나 멈출 수 있습니다. SetSpeed()와 Halt() 퍼블릭 함수는 외부 이벤트로 구분됩니다. SetSpeed()는 자동차의 속력을 의미하는 이벤트 데이터를 받습니다. 데이터 구조는 상태 과정이 끝나면 삭제됩니다. 따라서 그 구조가 반드시 EventData를 상속 받고 함수가 불리기 전에 operator new를 통해서 생성되야 합니다.

Motor 클래스가 생성되면 시작 상태는 Idle 입니다. 첫 번째 SetSpeed() 호출은 상태를 Start로 바꾸고 자동차는 움직이기 시작합니다. 이어지는 SetSpeed() 이벤트는 ChangeSpeed 상태로 전시시켜 이미 움직이는 자동차의 속도을 바꿉니다. Halt() 이벤트는 Stop 상태로 전이시키고 상태 실행 도중 내부 이벤트가 생성되어 Idle 상태로 돌립니다.

새로운 상태머신은 다음과 같은 단계를 밟습니다.

1. StateMachine 베이스 클래스를 상속받는다.
2. 각 상태 함수에 대해 States enum을 생성한다.
3. STATE 매크로를 사용하여 상태 함수를 생성한다.
4. 각 상태에 대해 매크로를 사용하여 guard/entry/exit를 생성한다. (옵션)
5. STATE_MAP 매크로를 사용하여 하나의 상태 맵 검색을 생성한다.
6. TRANSITION_MAP 매크로를 사용하여 각 외부 이벤트에 대하여 하나의 상태 맵 검색 테이블을 생성한다.



상태 함수



상태 함수는 각 상태를 구현합니다. 상태머신의 상태 당 한 개의 상태가 존재하고, 해당 구현에서 모든 상태 함수는 반드시 다음과 같은 상태 함수의 형태를 지녀야 합니다.

void <class>::<func>(const EventData*)

예를 들면 void Motor::ST_Start(const MotorData*)과 같이 구현합니다. 중요한 부분은 이 함수가 데이터를 리턴하지 않고 EventData* 만을 인자로 취한다는 것입니다.

STATE_DECLARE 매크로를 사용하여 상태 함수를 정의합니다. 매크로의 인자는 상태 머신의 클래스 이름, 상태 함수의 이름, 이벤트 데이터 타입입니다.

STATE_DECLARE(Motor,     Idle,            NoEventData)
STATE_DECLARE(Motor,     Stop,            NoEventData)
STATE_DECLARE(Motor,     Start,           MotorData)
STATE_DECLARE(Motor,     ChangeSpeed,     MotorData)

위 매크로의 실행 결과는 다음과 같습니다.

void ST_Idle(const NoEventData*);
StateAction<Motor, NoEventData, &Motor::ST_Idle> Idle;

void ST_Stop(const NoEventData*);
StateAction<Motor, NoEventData, &Motor::ST_Stop> Stop;

void ST_Start(const MotorData*);
StateAction<MotorNM, MotorData, &Motor::ST_Start> Start;

void ST_ChangeSpeed(const MotorData*);
StateAction<Motor, MotorData, &Motor::ST_ChangeSpeed> ChangeSpeed;

각 상태 함수의 이름 앞에 ST_가 붙어있습니다. 그리고 state/guard/entry/exit 함수가 자동으로 매크로에 의해 생성됩니다.  STATE_DECLARE(Motor, Idle, NoEventData)를 사용해 함수를 정의했다면 실제 상태함수의 이름은 ST_Idle()이 될 것입니다 .

1. ST_ 상태 함수 앞에 붙는 단어
2. GD_ 가드 함수 앞에 붙는 단어
3. EN_ 엔트리 함수 앞에 붙는 단어
4. EX_  종료 함수 앞에 붙는 단어

상태 함수가 정의되면 STATE_DEFINE 매크로를 사용하여 구현합니다. 인자는 상태 머신 클래 스이름, 상태 함수 이름, 이벤트 데이터 타입입니다. 상태의 구현부는 상태 함수 안으로 들어갑니다. 주의할 점은 모든 상태 함수 코드는 InternalEvent()을 사용하여 다른 상태로 스위치할 수 있다는 것입니다. Guard/entry/exit 함수는 InternalEvent()을 호출할 수 없습니다. 만약 호출하면 런타임 에러가 날 것입니다.


STATE_DEFINE(Motor, Stop, NoEventData)
{
    cout << "Motor::ST_Stop" << endl;
    m_currentSpeed = 0; 

    // perform the stop motor processing here
    // transition to Idle via an internal event
    InternalEvent(ST_IDLE);
}

위 매크로를 확장하면 상태 함수 구현은 다음과 같습니다.


void Motor::ST_Stop(const NoEventData* data)
{
    cout << "Motor::ST_Stop" << endl;
    m_currentSpeed = 0; 

    // perform the stop motor processing here
    // transition to Idle via an internal event
    InternalEvent(ST_IDLE);
}

각 상태 함수는 반드시 매칭되는 enum을 가지고있어야 합니다. 이 enum은 상태 머신의 현재 상태를 저장하기 위해 사용됩니다. Motor의 경우 States가 enum을 제공합니다. 이 부분은 전이 맵을 인덱싱 하는데 사용되고 상태 맵 룩업 테이블에도 사용됩니다.

enum States
{
    ST_IDLE,
    ST_STOP,
    ST_START,
    ST_CHANGE_SPEED,
    ST_MAX_STATES
};

enum의 순서가 상태 맵에 제공된 순서와 일치하는 것은 중요합니다. 이렇게 하면 상태 enum은 특정 상태 호출에 묶입니다. EVENT_IGNORED 와 CANNOT_HAPPEN은 이 상태들과 더불어 이용됩니다. EVENT_IGNORED 가 일어나면 바로 return 하고 아무것도 하지 않습니다. CANNOT_HAPPEN은 일반적으로 일어나면 안 되는 경우이고, 상태 엔진을 정지시킵니다.


상태 맵


상태 머신 엔진은 상태 맵을 이용해서 어떤 상태를 불러와야 할지 알게 됩니다. 상태 맵은 m_currentState 변수를 특정 상태와 매핑합니다. 예를 들어 만약 m_currentState의 값이 2 라면, 세 번째 상태 맵 함수 포인터의 시작점이 호출될 것입니다(0부터 셈으로). 상태 맵은 다음의 세 매크로를 통해 생성됩니다.


BEGIN_STATE_MAP
STATE_MAP_ENTRY
END_STATE_MAP

BEGIN_STATE_MAP은 상태 맵 순서를 시작합니다. 각 STATE_MAP_ENTRY는 상태 함수 이을 인자로 가집니다. END_STATE_MAP은 맵을 종료합니다. Motor의 상태 맵은 다음과 같습니다.


BEGIN_STATE_MAP
    STATE_MAP_ENTRY(&Idle)
    STATE_MAP_ENTRY(&Stop)
    STATE_MAP_ENTRY(&Start)
    STATE_MAP_ENTRY(&ChangeSpeed)
END_STATE_MAP    

완전한 상태 맵은 StateMachine 베이스 클래스의 순수 가상 함수인 GetStateMap()을 구현합니다. 이제 StateMachine 베이스 클래스는 이 호출을 통해 모든 StateMapRow 오브젝트를 가져올 수 있습니다. 매크로를 사용하지 않은 코드는 다음과 같습니다.


private:
    virtual const StateMapRowEx* GetStateMapEx() { return NULL; }
    virtual const StateMapRow* GetStateMap() {
        static const StateMapRow STATE_MAP[] = { 
            &Idle,
            &Stop,
            &Start,
            &ChangeSpeed,
        }; 
        C_ASSERT((sizeof(STATE_MAP)/sizeof(StateMapRow)) == ST_MAX_STATES); 
        return &STATE_MAP[0]; }

C_ASSERT 매크로를 유의하세요. 상태 맵이 잘못된 숫자의 시작점을 갖는 것을 컴파일 타임에 방지해 줍니다. 비주얼 스튜디오는 error C2118: negative subscript 에러를 표시합니다. 컴파일러마다 조금씩 다를 수 있습니다.

이완 다르게 guard/entry/exit 기능들은 _EX 버전의 매크로를 필요로 합니다.


BEGIN_STATE_MAP_EX
STATE_MAP_ENTRY_EX or STATE_MAP_ENTRY_ALL_EX 
END_STATE_MAP_EX

트랜지션 맵의 각 시작점은 StateMapRow에 들어있습니다.


struct StateMapRow
{
    const StateBase* const State;
};

StateBase 포인터는 StateEngine()에 의해 호출된 순수 가상 인터페이스를 가지고 있습니다.


class StateBase
{
public:
    virtual void InvokeStateAction(StateMachine* sm, const EventData* data) const = 0;
};

StateBase에서 파생된 StateAction의 유일한 임무는 InvokeStateAction()을 구현하고 StateMachine과 EventData의 포인터를 올바른 클래스 형태로 변환하고, 상태 멤버 함수를 호출하는 것입니다. 
따라서 각 상태 함수를 호출하는 상태 엔진의 오버헤드는 가상 함수 호출 하나,  static_cast<> 하나, 그리고 dynamic_cast<> 하나 입니다.


template <class SM, class Data, void (SM::*Func)(const Data*)>
class StateAction : public StateBase
{
public:
    virtual void InvokeStateAction(StateMachine* sm, const EventData* data) const 
    {
        // Downcast the state machine and event data to the correct derived type
        SM* derivedSM = static_cast<SM*>(sm);

        // Dynamic cast the data to the correct derived type        
        const Data* derivedData = dynamic_cast<const Data*>(data);
        ASSERT_TRUE(derivedData != NULL);

        // Call the state function
        (derivedSM->*Func)(derivedData);
    }
};

StateAction<>에 대한 템플릿 인자는 상태 머신 클래스(SM), 이벤트 데이터 타입(Data), 그리고 상태 함수에 대한 멤버 함수 포인터(Func) 입니다.



트랜지션 맵


마지막으로 덧붙일 세부사항은 트렌지션 규칙입니다. 상태 머신이 어떤 전이가 일어나야 할지 어떻게 알까요? 답은 전이 맵에 있습니다. 전이 맵은 룩업테이블로 m_currentState 변수를 상태 enum 상수에 매칭합니다. 모든 외부 이벤트는 상태 맵 테이블이 다음 세 가지 매크로로 구현되어 있습니다.


BEGIN_TRANSITION_MAP
TRANSITION_MAP_ENTRY
END_TRANSITION_MAP

Motor의 Halt() 함수는 다음과 같이 구현되어 있습니다.


void Motor::Halt()
{
    BEGIN_TRANSITION_MAP                                      // - Current State -
        TRANSITION_MAP_ENTRY (EVENT_IGNORED)                  // ST_IDLE
        TRANSITION_MAP_ENTRY (CANNOT_HAPPEN)                  // ST_STOP
        TRANSITION_MAP_ENTRY (ST_STOP)                        // ST_START
        TRANSITION_MAP_ENTRY (ST_STOP)                        // ST_CHANGE_SPEED
    END_TRANSITION_MAP(NULL)
}

매크로를 사용하지 않은 Halt() 함수는 다음과 같습니다.  이번에도, C_ASSERT 매크로가 컴파일 타임의 올바르지 않은 트랜지션 맵 도입 숫자가 사용되는 것을 막아줍니다.


void Motor::Halt()
{
    static const BYTE TRANSITIONS[] = {
        EVENT_IGNORED,                    // ST_IDLE
        CANNOT_HAPPEN,                    // ST_STOP
        ST_STOP,                          // ST_START
        ST_STOP,                          // ST_CHANGE_SPEED
    };
    ExternalEvent(TRANSITIONS[GetCurrentState()], NULL); 
    C_ASSERT((sizeof(TRANSITIONS)/sizeof(BYTE)) == ST_MAX_STATES);     
}



상태 엔진


상태엔진은 상태함수를 생성된 이벤트에 의거하여 실생합니다. 전이 맵은 StateMapRow 객체의 배열로 m_currentState 변수의 값에 의해 인덱싱 되어있습니다.  StateEngine() 함수가 실행되면 GetStateMap()를 호출하여 StateMapRow 배열을 살펴봅니다. 


void StateMachine::StateEngine(void)
{
    const StateMapRow* pStateMap = GetStateMap();
    if (pStateMap != NULL)
        StateEngine(pStateMap);
    else
    {
        const StateMapRowEx* pStateMapEx = GetStateMapEx();
        if (pStateMapEx != NULL)
            StateEngine(pStateMapEx);
        else
            ASSERT();
    }
}

StateMapRow 테이블에 새로운 상태 값을 인덱싱 하는 것은 InvokeStateAction()을 호출하여 이러우집니다.


const StateBase* state = pStateMap[m_newState].State;
state->InvokeStateAction(this, pDataTemp);

상태 함수가 실행될 기회를 가진 뒤 이벤트 데이터는 삭제됩니다. 그 뒤 내부 이벤트가 생성되었는지 확인합니다. 하나의 완전한 상태 엔진 함수는 아래 정의되어 있습니다. 다른 오버로드 된 상태 엔진 함수는 상태 머신을 StateMapRowEx 테이블로 다룹니다.


void StateMachine::StateEngine(const StateMapRow* const pStateMap)
{
    const EventData* pDataTemp = NULL;    
    
    // While events are being generated keep executing states
    while (m_eventGenerated)
    {
        // Error check that the new state is valid before proceeding
        ASSERT_TRUE(m_newState < MAX_STATES);
    
        // Get the pointer from the state map
        const StateBase* state = pStateMap[m_newState].State;
            
           // Copy of event data pointer
        pDataTemp = m_pEventData;

        // Event data used up, reset the pointer
        m_pEventData = NULL;

        // Event used up, reset the flag
        m_eventGenerated = FALSE;

        // Switch to the new current state
        SetCurrentState(m_newState);

        // Execute the state action passing in event data
        ASSERT_TRUE(state != NULL);
        state->InvokeStateAction(this, pDataTemp);

        // If event data was used, then delete it
        if (pDataTemp)
        {
             delete pDataTemp;
             pDataTemp = NULL;
        }
    }
}



이벤트 생성


이 시점에서 우리는 동작 가능한 상태 머신을 만들었습니다. 이제 이벤트를 어떻게 생성하는지 보겠습니다. 외부 이벤트는 new를 사용하여 이벤트 데이터 구조를 힙에 생성하고, 구조 멤버 변수를 대입하고, 외부 이벤트 함수를 호출함으로써 생성됩니다. 다음 코드는 비동기 콜이 만들어지는 방법입니다.

MotorData* data = new MotorData();
data->speed = 50;
motor.SetSpeed(data);

내부 이벤트를 상태 함수 안에서 생성하는 방법은 InternalEvent()를 호출하는 것입니다. 목적지가 이벤트 데이터를 받지 않는다면 함수는 필요한 상태만 가지고 호출됩니다.

InternalEvent(ST_IDLE);

위의 예제에서 상태 함수가 실행을 마치면 상태 머신은 Idle 상태로 전이할 것입니다. 하지만 이벤트 데이터가 목적 상태에서 필요로 한다면, 데이터 구조가 힙에 생성되고 인자로 전달되어야 합니다.


MotorData* data = new MotorData();
data->speed = 100;
InternalEvent(ST_CHANGE_SPEED, data);


멀티스레드 안전성


상태 머신이 실행중에 있을 때 다른 스레드에 의해서 영향 받는 것을 방지하기 위해 StateMachine 클래스는 ExternalEvent() 안에서 락을 사용할 수 있습니다. 외부 이벤트가 실행되기 전에 세마포가 락이 걸립니다. 그리고 외부 이벤트와 모든 내부 이벤트가 끝났을 때 소프트웨어 락이 풀리고, 다른 외부 이벤트가 상태 머신 안으로 들어올 수 있게 됩니다.

코드의 주석에 어디에 락과 언락이 들어가야 하는지 나와있습니다. 각 StateMachine은 각자의 소프트웨어 락을 가지고 있어야 합니다. 이렇게 해야 한 개의 객체가 다른 모든 StateMachine의 동작을 막는 현상을 방지할 수 있습니다. 주의할 점은 소프트웨어 락은 StateMachine이 멀티스레드 환경에서 동작할 때만 필요하다는 것입니다. 만약 그러지 않다면 락은 필요 없습니다.



장점


상태 머신을 이러한 방법으로 구현하는 것은 기존의 스위치 케이스 구현에 비해 많은 노력이 들어갑니다. 하지만 페이오프는 모든 멀티스레드 환경에서 동작 가능한 더 탄탄한 구조를 갖는다는 것입니다. 각 상태가 각자의 함수 안에 들어가있는 것은 하나의 큰 스위치 구문보다 읽기 쉽습니다. 그리고 각 상태별로 고유한 이벤트 데이터를 주고받을 수 있게 해줍니다. 추가적으로, 상태 전이의 유효성을 검사하는 것은 사용자가 원하지 않는 상태 전이를 사용함으로써 올 수 있는 에러들을 방지해줍니다.