[Software Engineering] Finite State Machine | 유한 상태 기계

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 | 무어 모델과 밀리 모델

---

FSM Diagram

 

State Diagram for Moore Model
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 검색