Finite State Machine (FSM)
유한 상태 기계
- Stack을 사용하는 Automata의 일종으로, 복잡한 Case를 처리하기에 용이하다.
- 복잡한 동작을 모두 if-else 또는 switch로 처리할 경우
프로그램의 복잡도가 매우 높아져 유지·보수가 불가능해지는 수준에 이르게되므로,
이러한 경우에는 State Machine을 통한 구현으로 유지 보수성을 높일 것이 권고된다.
* Automata Theory (URL)
* Moore Model and Mealy Model (무어 모델과 밀리 모델) (URL)
[Digital Logic] Moore Model and Mealy Model | 무어 모델과 밀리 모델
Moore Model and Mealy Model 무어 모델과 밀리 모델 * Analysis of Clocked Sequential Circuit 1) 회로에서 Flip-Flop의 Input/Output에 대한 State Equation을 구한다. 2) State Equation들로부터 State Table..
dad-rock.tistory.com
FSM Diagram
 |
 |
| State Diagram for Moore Model |
State Diagram for Mealy Model |
| FSM Diagram Component | Description |
| State | - Object의 '상태'를 의미한다. |
| Transition | - 한 State에서 다른 State로의 '전이'를 의미한다. |
| Transition Condition (Event) |
- Transition이 발생되기 위한 조건이다. |
| Entry Action | - 새로운 State로 Transition될 때 행해지는 어떠한 동작이다. [Moore Model] - 한 State에서는 오직 하나의 Action만 취해진다. [Mealy Model] - 어떤 State에서 Transition되는지에 따라 행해지는 Action이 다르다. |
Example. FSM for Vending Machine
Requirement
- 자판기에서 판매하는 모든 음료의 가격은 200원이다.
- 자판기는 100원짜리 동전만 인식할 수 있으며, 이외의 모든 화폐는 인식하지 못한다.
- LED Indicator로 현재 투입된 금액을 표시한다.
- '반환' 버튼을 누르면 현재까지 투입한 모든 금액을 반환한다.
- 현재 상태에서 구입 가능한 음료에는 음료 버튼에 조명이 켜진다.
State Diagram
* Legend
| Event (Transition Condition) |
Description | Entry Action | Description |
| 1 | - 100원 동전 투입 | A(n) | - 금액 n 표시 |
| 2 | - 반환 버튼 누름 | B(n) | - 동전 n 반환 |
| 3 | - 음료 버튼 누름 | C(x) | - 음료버튼 점등 여부 |
| D | - 음료 내보내기 |
Implementation (C++)
// VendingMachine.h
#include <iostream>
#define NUMBER_OF_TABLE_ENTRIES 100 // event-action table의 현재 entry 갯수
#define MAX_NUMBER_OF_ACTIONS 3 // transition 시 실행되는 최대 action 갯수
using namespace std;
// State 열거형 정의
typedef enum {
STATE_READY,
STATE_100_INSERTED,
STATE_200_INSERTED,
STATE_END
} State;
// Event 열거형 정의
typedef enum {
EVENT_INSERT_100,
EVENT_REFUND_BUTTON_PRESSED,
EVENT_BEVERAGE_BUTTON_PRESSED,
EVENT_QUIT
} Event;
// 음료 자동판매기를 위한 StateMachine 클래스 정의
class StateMachine
{
private:
State curState; // 현재 상태
// event-action table structure 정의
typedef struct {
State curState; // 현재 상태
Event event; // 사용자로부터 발생된 이벤트
int number_of_actions; // 해당 transition에 실행되는 action 함수의 갯수
void (StateMachine::*action[MAX_NUMBER_OF_ACTIONS])(int); // action 함수 포인터의 배열
int action_parameter[MAX_NUMBER_OF_ACTIONS]; // action 함수의 매개변수 배열
State nextState; // transition 후에 변경될 다음 상태
} EventActionTable;
// vending machine에서 사용할 event-action table 초기화
EventActionTable table[NUMBER_OF_TABLE_ENTRIES] {
{STATE_READY, EVENT_INSERT_100, 1, {&StateMachine::displayInsertedMoney}, {100}, STATE_100_INSERTED},
{STATE_100_INSERTED, EVENT_INSERT_100, 2, {&StateMachine::displayInsertedMoney, &StateMachine::turnLight}, {200, 1}, STATE_200_INSERTED},
{STATE_100_INSERTED, EVENT_REFUND_BUTTON_PRESSED, 2, {&StateMachine::displayInsertedMoney, &StateMachine::refundCoins}, {0, 100}, STATE_READY},
{STATE_200_INSERTED, EVENT_INSERT_100, 1, {&StateMachine::refundCoins}, {100}, STATE_200_INSERTED},
{STATE_200_INSERTED, EVENT_REFUND_BUTTON_PRESSED, 3, {&StateMachine::displayInsertedMoney, &StateMachine::refundCoins, &StateMachine::turnLight}, {0, 200, 0}, STATE_READY},
{STATE_200_INSERTED, EVENT_BEVERAGE_BUTTON_PRESSED, 3, {&StateMachine::displayInsertedMoney, &StateMachine::turnLight, &StateMachine::releaseBeverage}, {0, 0, 0}, STATE_READY}
};
void displayInsertedMoney(int displayedMoneyAmount); // LED 화면에 현재 투입된 금액을 표시함
void refundCoins(int refundedMoneyAmount); // 반환 버튼을 눌렀을 때 투입된 금액을 반환함
void turnLight(int lightOn); // 음료 버튼에 조명을 켜거나 끄는 동작 수행함. -> on = 1, off = 0;
void releaseBeverage(int dummy); // 선택한 음료를 외부로 내보냄 -> dummy parameter
Event getNextEvent(); // 사용자로부터 다음 이벤트를 입력받음
string getCurrentStateString(); // 현재 상태에 해당하는 문자열을 생성해서 반환함
public:
void run(); // state machine 실행
};
// VendingMachine.cpp
#include <string>
#include "StateMachine.h"
/*
함수 이름 : StateMachine::run()
기능 : STATE_END 상태가 될 때까지 event-action 테이블에 정의된 규칙과 사용자에 의해 발생되는 이벤트에 따라 state machine을 동작시킴
전달 인자 : 없음
반환값 : 없음
*/
void StateMachine::run()
{
int i, j;
Event curEvent; // 현재 이벤트
curState = STATE_READY; // 상태 초기화
while (curState != STATE_END) // EVENT_QUIT이 입력될 때까지 반복 수행함
{
curEvent = getNextEvent(); // 다음 이벤트를 입력받음
for (i = 0; i < NUMBER_OF_TABLE_ENTRIES; i++) // 테이블에 정의된 전각체 행(transition 내용)에 대해 비교함
{
if (curState == table[i].curState) // 현재 상태와 일치하는지 검사
{
if (curEvent == table[i].event) // 입력된 현재 이벤트와 일치하는지 검사
{
// 해당 transition이 발생할 때 수행해야 할 action 함수들을 실행시킴
for (j = 0; j < table[i].number_of_actions; j++)
(this->*table[i].action[j])(table[i].action_parameter[j]);
curState = table[i].nextState; // 테이블에 정의된 다음 상태로 현재 상태를 변경함
break;
}
}
}
cout << endl << endl;
}
}
/*
함수 이름 : StateMachine::getNextEvent()
기능 : 사용자로부터 다음 이벤트를 입력받음
전달 인자 : 없음
반환값 : Event -> 입력받은 이벤트 값
*/
Event StateMachine::getNextEvent()
{
Event selectedEvent; // 반환할 이벤트
int inputEvent; // 사용자로부터 입력받은 이벤트
// 입력 안내 메세지 출력
cout << "[현재 상태 : " << getCurrentStateString() << "]" << endl;
cout << "1. Deposit a 100 won coin" << endl;
cout << "2. Press the refund button" << endl;
cout << "3. Press the beverage button you want" << endl;
cout << "4. Quit" << endl;
cout << "Select an event # : ";
// 사용자로부터 이벤트 입력받음
cin >> inputEvent;
// 입력 값에 따라 반환할 이벤트 값을 결정함
switch (inputEvent)
{
case 1:
selectedEvent = EVENT_INSERT_100;
break;
case 2:
selectedEvent = EVENT_REFUND_BUTTON_PRESSED;
break;
case 3:
selectedEvent = EVENT_BEVERAGE_BUTTON_PRESSED;
break;
case 4:
default :
selectedEvent = EVENT_QUIT;
curState = STATE_END;
}
return selectedEvent;
}
/*
함수 이름 : StateMachine::displayInsertedMoney()
기능 : LED 화면에 현재 투입된 금액을 표시함
전달 인자 : displayedMoneyAmount -> 화면에 출력될 금액
반환값 : 없음
*/
void StateMachine::displayInsertedMoney(int displayedMoneyAmount)
{
cout << "현재 투입된 금액은 " << displayedMoneyAmount << "원입니다." << endl;
}
/*
함수 이름 : StateMachine::refundCoins()
기능 : 반환 버튼을 눌렀을 때 투입된 금액을 반환함
전달 인자 : refundedMoneyAmount -> 반환될 금액
반환값 : 없음
*/
void StateMachine::refundCoins(int refundedMoneyAmount)
{
cout << "반환되는 금액은 " << refundedMoneyAmount << "원입니다." << endl;
}
/*
함수 이름 : StateMachine::turnLight()
기능 : 음료 버튼에 조명을 켜거나 끄는 동작 수행함.
전달 인자 : lightOn -> 1: on, 0: off
반환값 : 없음
*/
void StateMachine::turnLight(int lightOn)
{
if(lightOn == 1)
cout << "음료 버튼의 조명이 켜졌습니다." << endl;
else
cout << "음료 버튼의 조명이 꺼졌습니다." << endl;
}
/*
함수 이름 : StateMachine::releaseBeverage()
기능 : 선택한 음료를 외부로 내보냄.
전달 인자 : 매개변수는 필요 없지만 다른 함수와 매개변수를 맞추기 위해 동일하게 정의됨(dummy parameter)
반환값 : 없음
*/
void StateMachine::releaseBeverage(int dummy)
{
cout << "음료가 나왔습니다." << endl;
}
/*
함수 이름 : StateMachine::getCurrentStateString()
기능 : 현재 상태에 해당하는 출력용 문자열을 생성해서 반환함
전달 인자 : 없음
반환값 : string -> 출력용 상태 문자열
*/
string StateMachine::getCurrentStateString()
{
string returnedString;
switch (curState)
{
case STATE_READY:
returnedString = "STATE_READY";
break;
case STATE_100_INSERTED:
returnedString = "STATE_100_INSERTED";
break;
case STATE_200_INSERTED:
returnedString = "STATE_200_INSERTED";
}
return returnedString;
}
Reference: Software Engineering 10th Edition
(Ian Sommerville 저, Pearson, 2016)
Reference: Object-Oriented Systems Analysis and Design Using UML 4th Edition
(Simon Bennett, Steve McRobb, Ray Farmer 저, McGrawHill, 2010)
Reference: Wikipedia, State diagram, 2022.06.20, URL, 2022.06.21 검색
Finite State Machine (FSM)
유한 상태 기계
- Stack을 사용하는 Automata의 일종으로, 복잡한 Case를 처리하기에 용이하다.
- 복잡한 동작을 모두 if-else 또는 switch로 처리할 경우
프로그램의 복잡도가 매우 높아져 유지·보수가 불가능해지는 수준에 이르게되므로,
이러한 경우에는 State Machine을 통한 구현으로 유지 보수성을 높일 것이 권고된다.
* Automata Theory (URL)
* Moore Model and Mealy Model (무어 모델과 밀리 모델) (URL)
[Digital Logic] Moore Model and Mealy Model | 무어 모델과 밀리 모델
Moore Model and Mealy Model 무어 모델과 밀리 모델 * Analysis of Clocked Sequential Circuit 1) 회로에서 Flip-Flop의 Input/Output에 대한 State Equation을 구한다. 2) State Equation들로부터 State Table..
dad-rock.tistory.com
FSM Diagram
|
|
| State Diagram for Moore Model |
State Diagram for Mealy Model |
| FSM Diagram Component | Description |
| State | - Object의 '상태'를 의미한다. |
| Transition | - 한 State에서 다른 State로의 '전이'를 의미한다. |
| Transition Condition (Event) |
- Transition이 발생되기 위한 조건이다. |
| Entry Action | - 새로운 State로 Transition될 때 행해지는 어떠한 동작이다. [Moore Model] - 한 State에서는 오직 하나의 Action만 취해진다. [Mealy Model] - 어떤 State에서 Transition되는지에 따라 행해지는 Action이 다르다. |
Example. FSM for Vending Machine
Requirement
- 자판기에서 판매하는 모든 음료의 가격은 200원이다.
- 자판기는 100원짜리 동전만 인식할 수 있으며, 이외의 모든 화폐는 인식하지 못한다.
- LED Indicator로 현재 투입된 금액을 표시한다.
- '반환' 버튼을 누르면 현재까지 투입한 모든 금액을 반환한다.
- 현재 상태에서 구입 가능한 음료에는 음료 버튼에 조명이 켜진다.
State Diagram
* Legend
| Event (Transition Condition) |
Description | Entry Action | Description |
| 1 | - 100원 동전 투입 | A(n) | - 금액 n 표시 |
| 2 | - 반환 버튼 누름 | B(n) | - 동전 n 반환 |
| 3 | - 음료 버튼 누름 | C(x) | - 음료버튼 점등 여부 |
| D | - 음료 내보내기 |
Implementation (C++)
// VendingMachine.h
#include <iostream>
#define NUMBER_OF_TABLE_ENTRIES 100 // event-action table의 현재 entry 갯수
#define MAX_NUMBER_OF_ACTIONS 3 // transition 시 실행되는 최대 action 갯수
using namespace std;
// State 열거형 정의
typedef enum {
STATE_READY,
STATE_100_INSERTED,
STATE_200_INSERTED,
STATE_END
} State;
// Event 열거형 정의
typedef enum {
EVENT_INSERT_100,
EVENT_REFUND_BUTTON_PRESSED,
EVENT_BEVERAGE_BUTTON_PRESSED,
EVENT_QUIT
} Event;
// 음료 자동판매기를 위한 StateMachine 클래스 정의
class StateMachine
{
private:
State curState; // 현재 상태
// event-action table structure 정의
typedef struct {
State curState; // 현재 상태
Event event; // 사용자로부터 발생된 이벤트
int number_of_actions; // 해당 transition에 실행되는 action 함수의 갯수
void (StateMachine::*action[MAX_NUMBER_OF_ACTIONS])(int); // action 함수 포인터의 배열
int action_parameter[MAX_NUMBER_OF_ACTIONS]; // action 함수의 매개변수 배열
State nextState; // transition 후에 변경될 다음 상태
} EventActionTable;
// vending machine에서 사용할 event-action table 초기화
EventActionTable table[NUMBER_OF_TABLE_ENTRIES] {
{STATE_READY, EVENT_INSERT_100, 1, {&StateMachine::displayInsertedMoney}, {100}, STATE_100_INSERTED},
{STATE_100_INSERTED, EVENT_INSERT_100, 2, {&StateMachine::displayInsertedMoney, &StateMachine::turnLight}, {200, 1}, STATE_200_INSERTED},
{STATE_100_INSERTED, EVENT_REFUND_BUTTON_PRESSED, 2, {&StateMachine::displayInsertedMoney, &StateMachine::refundCoins}, {0, 100}, STATE_READY},
{STATE_200_INSERTED, EVENT_INSERT_100, 1, {&StateMachine::refundCoins}, {100}, STATE_200_INSERTED},
{STATE_200_INSERTED, EVENT_REFUND_BUTTON_PRESSED, 3, {&StateMachine::displayInsertedMoney, &StateMachine::refundCoins, &StateMachine::turnLight}, {0, 200, 0}, STATE_READY},
{STATE_200_INSERTED, EVENT_BEVERAGE_BUTTON_PRESSED, 3, {&StateMachine::displayInsertedMoney, &StateMachine::turnLight, &StateMachine::releaseBeverage}, {0, 0, 0}, STATE_READY}
};
void displayInsertedMoney(int displayedMoneyAmount); // LED 화면에 현재 투입된 금액을 표시함
void refundCoins(int refundedMoneyAmount); // 반환 버튼을 눌렀을 때 투입된 금액을 반환함
void turnLight(int lightOn); // 음료 버튼에 조명을 켜거나 끄는 동작 수행함. -> on = 1, off = 0;
void releaseBeverage(int dummy); // 선택한 음료를 외부로 내보냄 -> dummy parameter
Event getNextEvent(); // 사용자로부터 다음 이벤트를 입력받음
string getCurrentStateString(); // 현재 상태에 해당하는 문자열을 생성해서 반환함
public:
void run(); // state machine 실행
};
// VendingMachine.cpp
#include <string>
#include "StateMachine.h"
/*
함수 이름 : StateMachine::run()
기능 : STATE_END 상태가 될 때까지 event-action 테이블에 정의된 규칙과 사용자에 의해 발생되는 이벤트에 따라 state machine을 동작시킴
전달 인자 : 없음
반환값 : 없음
*/
void StateMachine::run()
{
int i, j;
Event curEvent; // 현재 이벤트
curState = STATE_READY; // 상태 초기화
while (curState != STATE_END) // EVENT_QUIT이 입력될 때까지 반복 수행함
{
curEvent = getNextEvent(); // 다음 이벤트를 입력받음
for (i = 0; i < NUMBER_OF_TABLE_ENTRIES; i++) // 테이블에 정의된 전각체 행(transition 내용)에 대해 비교함
{
if (curState == table[i].curState) // 현재 상태와 일치하는지 검사
{
if (curEvent == table[i].event) // 입력된 현재 이벤트와 일치하는지 검사
{
// 해당 transition이 발생할 때 수행해야 할 action 함수들을 실행시킴
for (j = 0; j < table[i].number_of_actions; j++)
(this->*table[i].action[j])(table[i].action_parameter[j]);
curState = table[i].nextState; // 테이블에 정의된 다음 상태로 현재 상태를 변경함
break;
}
}
}
cout << endl << endl;
}
}
/*
함수 이름 : StateMachine::getNextEvent()
기능 : 사용자로부터 다음 이벤트를 입력받음
전달 인자 : 없음
반환값 : Event -> 입력받은 이벤트 값
*/
Event StateMachine::getNextEvent()
{
Event selectedEvent; // 반환할 이벤트
int inputEvent; // 사용자로부터 입력받은 이벤트
// 입력 안내 메세지 출력
cout << "[현재 상태 : " << getCurrentStateString() << "]" << endl;
cout << "1. Deposit a 100 won coin" << endl;
cout << "2. Press the refund button" << endl;
cout << "3. Press the beverage button you want" << endl;
cout << "4. Quit" << endl;
cout << "Select an event # : ";
// 사용자로부터 이벤트 입력받음
cin >> inputEvent;
// 입력 값에 따라 반환할 이벤트 값을 결정함
switch (inputEvent)
{
case 1:
selectedEvent = EVENT_INSERT_100;
break;
case 2:
selectedEvent = EVENT_REFUND_BUTTON_PRESSED;
break;
case 3:
selectedEvent = EVENT_BEVERAGE_BUTTON_PRESSED;
break;
case 4:
default :
selectedEvent = EVENT_QUIT;
curState = STATE_END;
}
return selectedEvent;
}
/*
함수 이름 : StateMachine::displayInsertedMoney()
기능 : LED 화면에 현재 투입된 금액을 표시함
전달 인자 : displayedMoneyAmount -> 화면에 출력될 금액
반환값 : 없음
*/
void StateMachine::displayInsertedMoney(int displayedMoneyAmount)
{
cout << "현재 투입된 금액은 " << displayedMoneyAmount << "원입니다." << endl;
}
/*
함수 이름 : StateMachine::refundCoins()
기능 : 반환 버튼을 눌렀을 때 투입된 금액을 반환함
전달 인자 : refundedMoneyAmount -> 반환될 금액
반환값 : 없음
*/
void StateMachine::refundCoins(int refundedMoneyAmount)
{
cout << "반환되는 금액은 " << refundedMoneyAmount << "원입니다." << endl;
}
/*
함수 이름 : StateMachine::turnLight()
기능 : 음료 버튼에 조명을 켜거나 끄는 동작 수행함.
전달 인자 : lightOn -> 1: on, 0: off
반환값 : 없음
*/
void StateMachine::turnLight(int lightOn)
{
if(lightOn == 1)
cout << "음료 버튼의 조명이 켜졌습니다." << endl;
else
cout << "음료 버튼의 조명이 꺼졌습니다." << endl;
}
/*
함수 이름 : StateMachine::releaseBeverage()
기능 : 선택한 음료를 외부로 내보냄.
전달 인자 : 매개변수는 필요 없지만 다른 함수와 매개변수를 맞추기 위해 동일하게 정의됨(dummy parameter)
반환값 : 없음
*/
void StateMachine::releaseBeverage(int dummy)
{
cout << "음료가 나왔습니다." << endl;
}
/*
함수 이름 : StateMachine::getCurrentStateString()
기능 : 현재 상태에 해당하는 출력용 문자열을 생성해서 반환함
전달 인자 : 없음
반환값 : string -> 출력용 상태 문자열
*/
string StateMachine::getCurrentStateString()
{
string returnedString;
switch (curState)
{
case STATE_READY:
returnedString = "STATE_READY";
break;
case STATE_100_INSERTED:
returnedString = "STATE_100_INSERTED";
break;
case STATE_200_INSERTED:
returnedString = "STATE_200_INSERTED";
}
return returnedString;
}
Reference: Software Engineering 10th Edition
(Ian Sommerville 저, Pearson, 2016)
Reference: Object-Oriented Systems Analysis and Design Using UML 4th Edition
(Simon Bennett, Steve McRobb, Ray Farmer 저, McGrawHill, 2010)
Reference: Wikipedia, State diagram, 2022.06.20, URL, 2022.06.21 검색
