Bài 16.322 phút đọc

Máy trạng thái

Sau bài này bạn sẽ làm được

Mô hình hóa một bài toán bằng máy trạng thái
Cài bảng chuyển trạng thái bằng enum và mảng hai chiều
So sánh bảng với chuỗi if lồng nhau
Kiểm chứng máy trạng thái bằng bộ kiểm thử

Máy trạng thái là cách mô hình hóa mọi chương trình phản ứng với sự kiện: giao thức mạng, trình phân tích cú pháp, giao diện người dùng, thiết bị nhúng. Với enum, C cho bạn cách cài nó vừa gọn vừa an toàn.

#Máy trạng thái là gì

Máy trạng thái

Một mô hình gồm tập trạng thái hữu hạn, tập sự kiện, và quy tắc cho biết ở trạng thái nào gặp sự kiện nào thì chuyển sang trạng thái nào.

Bốn trạng thái của một kết nối. Mỗi mũi tên là một quy tắc chuyển, và nhãn trên mũi tên là sự kiện gây ra nó.

khai-bao.c

typedef enum {
    TT_CHO,
    TT_DANG_NOI,
    TT_DA_NOI,
    TT_LOI,
    TT_SO_LUONG,
} TrangThai;

typedef enum {
    SK_BAT_DAU,
    SK_OK,
    SK_HONG,
    SK_DUNG,
    SK_SO_LUONG,
} SuKien;

Thành phần	Trong ví dụ này
Tập trạng thái	CHO, DANG_NOI, DA_NOI, LOI
Trạng thái đầu	CHO
Tập sự kiện	BAT_DAU, OK, HONG, DUNG
Quy tắc chuyển	Bảng 4 nhân 4, mỗi ô là trạng thái kế tiếp
Hành động	Việc cần làm khi một bước chuyển xảy ra

#Bảng chuyển trạng thái

bang.c

/* Bảng hai chiều: dòng là trạng thái hiện tại, cột là sự kiện. */
static const TrangThai BANG[TT_SO_LUONG][SK_SO_LUONG] = {
    /*                     SK_BAT_DAU     SK_OK         SK_HONG    SK_DUNG  */
    [TT_CHO]      = { [SK_BAT_DAU] = TT_DANG_NOI,
                      [SK_OK]      = TT_CHO,
                      [SK_HONG]    = TT_CHO,
                      [SK_DUNG]    = TT_CHO },

    [TT_DANG_NOI] = { [SK_BAT_DAU] = TT_DANG_NOI,
                      [SK_OK]      = TT_DA_NOI,
                      [SK_HONG]    = TT_LOI,
                      [SK_DUNG]    = TT_CHO },

    [TT_DA_NOI]   = { [SK_BAT_DAU] = TT_DA_NOI,
                      [SK_OK]      = TT_DA_NOI,
                      [SK_HONG]    = TT_LOI,
                      [SK_DUNG]    = TT_CHO },

    [TT_LOI]      = { [SK_BAT_DAU] = TT_DANG_NOI,
                      [SK_OK]      = TT_LOI,
                      [SK_HONG]    = TT_LOI,
                      [SK_DUNG]    = TT_CHO },
};

/* Toàn bộ máy trạng thái gọn trong một hàm bốn dòng. */
TrangThai chuyen(TrangThai tt, SuKien sk)
{
    if (tt < 0 || tt >= TT_SO_LUONG) return TT_LOI;
    if (sk < 0 || sk >= SK_SO_LUONG) return tt;

    return BANG[tt][sk];
}

dung.c

#include <stdio.h>

static const char *TT_TEN[TT_SO_LUONG] = {
    [TT_CHO]      = "CHO",
    [TT_DANG_NOI] = "DANG_NOI",
    [TT_DA_NOI]   = "DA_NOI",
    [TT_LOI]      = "LOI",
};

static const char *SK_TEN[SK_SO_LUONG] = {
    [SK_BAT_DAU] = "BAT_DAU",
    [SK_OK]      = "OK",
    [SK_HONG]    = "HONG",
    [SK_DUNG]    = "DUNG",
};

int main(void)
{
    TrangThai tt = TT_CHO;

    SuKien chuoi[] = { SK_BAT_DAU, SK_OK, SK_HONG, SK_BAT_DAU, SK_OK, SK_DUNG };

    for (size_t i = 0; i < sizeof chuoi / sizeof chuoi[0]; ++i) {
        TrangThai truoc = tt;

        tt = chuyen(tt, chuoi[i]);

        printf("%-10s + %-8s -> %s\n",
               TT_TEN[truoc], SK_TEN[chuoi[i]], TT_TEN[tt]);
    }

    return 0;
}

terminal

./may-trang-thai

CHO        + BAT_DAU  -> DANG_NOI
DANG_NOI   + OK       -> DA_NOI
DA_NOI     + HONG     -> LOI
LOI        + BAT_DAU  -> DANG_NOI
DANG_NOI   + OK       -> DA_NOI
DA_NOI     + DUNG     -> CHO

Kiểm tra biên là bắt buộc

Sự kiện thường đến từ bên ngoài: từ mạng, từ bàn phím, từ phần cứng. Bài 16.2 đã nói: enum không giới hạn giá trị, nên tra thẳng BANG[tt][sk] mà không kiểm tra là mở đường cho lỗi vượt biên mảng.

/* Không kiểm tra: sk = 999 đọc ra ngoài bảng */
return BANG[tt][sk];

/* Có kiểm tra: an toàn với mọi giá trị */
if (tt < 0 || tt >= TT_SO_LUONG) return TT_LOI;
if (sk < 0 || sk >= SK_SO_LUONG) return tt;

return BANG[tt][sk];

#Thêm hành động vào mỗi bước chuyển

Bảng ở trên chỉ nói trạng thái kế tiếp. Trong thực tế, mỗi bước chuyển thường phải làm gì đó: mở kết nối, ghi log, gửi gói tin.

hanh-dong.c

/* Mỗi ô là một cặp: trạng thái kế tiếp và hành động cần chạy. */
typedef int (*HanhDong)(void *ngu_canh);

typedef struct {
    TrangThai tiep;
    HanhDong  lam;      /* NULL nếu không cần làm gì */
} BuocChuyen;

static int mo_ket_noi(void *nc);
static int gui_du_lieu(void *nc);
static int dong_ket_noi(void *nc);
static int ghi_log_loi(void *nc);

static const BuocChuyen BANG[TT_SO_LUONG][SK_SO_LUONG] = {
    [TT_CHO] = {
        [SK_BAT_DAU] = { TT_DANG_NOI, mo_ket_noi },
        [SK_OK]      = { TT_CHO,      NULL },
        [SK_HONG]    = { TT_CHO,      NULL },
        [SK_DUNG]    = { TT_CHO,      NULL },
    },
    [TT_DANG_NOI] = {
        [SK_BAT_DAU] = { TT_DANG_NOI, NULL },
        [SK_OK]      = { TT_DA_NOI,   gui_du_lieu },
        [SK_HONG]    = { TT_LOI,      ghi_log_loi },
        [SK_DUNG]    = { TT_CHO,      dong_ket_noi },
    },
    [TT_DA_NOI] = {
        [SK_BAT_DAU] = { TT_DA_NOI,   NULL },
        [SK_OK]      = { TT_DA_NOI,   gui_du_lieu },
        [SK_HONG]    = { TT_LOI,      ghi_log_loi },
        [SK_DUNG]    = { TT_CHO,      dong_ket_noi },
    },
    [TT_LOI] = {
        [SK_BAT_DAU] = { TT_DANG_NOI, mo_ket_noi },
        [SK_OK]      = { TT_LOI,      NULL },
        [SK_HONG]    = { TT_LOI,      NULL },
        [SK_DUNG]    = { TT_CHO,      dong_ket_noi },
    },
};

/* Trạng thái của máy gom vào một struct, không dùng biến toàn cục. */
typedef struct {
    TrangThai tt;
    void     *ngu_canh;
} May;

void may_khoi_tao(May *m, void *ngu_canh)
{
    m->tt       = TT_CHO;
    m->ngu_canh = ngu_canh;
}

int may_su_kien(May *m, SuKien sk)
{
    if (m == NULL)                   return -1;
    if (m->tt < 0 || m->tt >= TT_SO_LUONG) return -1;
    if (sk < 0 || sk >= SK_SO_LUONG) return -1;

    const BuocChuyen *b = &BANG[m->tt][sk];

    if (b->lam != NULL) {
        int kq = b->lam(m->ngu_canh);

        if (kq != 0) {          /* hành động thất bại: chuyển sang trạng thái lỗi */
            m->tt = TT_LOI;
            return kq;
        }
    }

    m->tt = b->tiep;

    return 0;
}

Thứ tự giữa hành động và đổi trạng thái là quyết định quan trọng

/* Cách 1: làm rồi mới chuyển. Hành động thấy trạng thái CŨ. */
b->lam(nc);
m->tt = b->tiep;

/* Cách 2: chuyển rồi mới làm. Hành động thấy trạng thái MỚI. */
m->tt = b->tiep;
b->lam(nc);

Cả hai đều dùng được, nhưng phải chọn một và ghi rõ trong tài liệu. Quan trọng hơn: nếu hành động có thể sinh sự kiện mới, cách 2 an toàn hơn vì máy đã ở trạng thái nhất quán trước khi hành động chạy.

#So với chuỗi if lồng nhau

Nhiều biến cờ và chuỗi if

int da_ket_noi = 0;
int dang_noi   = 0;
int bi_loi     = 0;

void xu_ly_su_kien(int sk)
{
    if (sk == SK_BAT_DAU) {
        if (!da_ket_noi && !dang_noi) {
            dang_noi = 1;
            mo_ket_noi();
        } else if (bi_loi) {
            bi_loi   = 0;
            dang_noi = 1;
            mo_ket_noi();
        }
    } else if (sk == SK_OK) {
        if (dang_noi) {
            dang_noi   = 0;
            da_ket_noi = 1;
        } else if (da_ket_noi) {
            gui_du_lieu();
        }
    } else if (sk == SK_HONG) {
        if (dang_noi || da_ket_noi) {
            dang_noi   = 0;
            da_ket_noi = 0;
            bi_loi     = 1;
            ghi_log_loi();
        }
    }
    /* ... và còn nữa ... */
}

Một biến trạng thái và một bảng

TrangThai tt = TT_CHO;

void xu_ly_su_kien(SuKien sk)
{
    tt = chuyen(tt, sk);
}

Tiêu chí	Chuỗi if với biến cờ	Bảng chuyển
Số trạng thái biểu diễn được	2 mũ số cờ, phần lớn vô nghĩa	Đúng số trạng thái thật
Trạng thái không hợp lệ	Có thể xảy ra, ví dụ vừa đang nối vừa đã nối	Không thể
Thêm một trạng thái	Rà lại mọi câu if	Thêm một dòng vào bảng
Thêm một sự kiện	Thêm một nhánh và rà lại mọi trạng thái	Thêm một cột vào bảng
Xem tổng quan hành vi	Phải đọc hết hàm	Nhìn bảng là thấy
Kiểm thử đầy đủ	Rất khó, không biết bao nhiêu tổ hợp	Dễ, đúng số ô của bảng

Vấn đề lớn nhất là trạng thái không hợp lệ

/* Ba biến cờ cho ra tám tổ hợp, nhưng chỉ bốn cái có nghĩa: */

da_ket_noi  dang_noi  bi_loi     Ý nghĩa
    0          0        0        đang chờ
    0          1        0        đang nối
    1          0        0        đã nối
    0          0        1        lỗi
    1          1        0        VÔ NGHĨA
    1          0        1        VÔ NGHĨA
    0          1        1        VÔ NGHĨA
    1          1        1        VÔ NGHĨA

/* Một lỗi ở đâu đó đưa chương trình vào một trong bốn trạng thái vô nghĩa,
   và từ đó mọi hành vi đều không đoán được. */

Với một biến enum duy nhất, bốn trạng thái vô nghĩa đó không tồn tại. Đây gọi là làm cho trạng thái sai không biểu diễn được, và nó là một trong những nguyên tắc thiết kế giá trị nhất.

#Kiểm chứng máy trạng thái

test.c

#include <assert.h>
#include <stdio.h>

static int so_luot = 0;

#define KT(bieu_thuc)                                          \
    do {                                                       \
        ++so_luot;                                             \
        if (!(bieu_thuc)) {                                    \
            printf("HONG dong %d: %s\n", __LINE__, #bieu_thuc); \
            return 1;                                          \
        }                                                      \
    } while (0)

/* Kiểm thử 1: mọi ô của bảng đều cho ra trạng thái hợp lệ */
static int kt_bang_hop_le(void)
{
    for (int t = 0; t < TT_SO_LUONG; ++t)
        for (int s = 0; s < SK_SO_LUONG; ++s) {
            TrangThai tiep = BANG[t][s];

            KT(tiep >= 0 && tiep < TT_SO_LUONG);
        }

    return 0;
}

/* Kiểm thử 2: mọi trạng thái đều tới được từ trạng thái đầu */
static int kt_toi_duoc(void)
{
    int toi_duoc[TT_SO_LUONG] = { 0 };
    int hang_doi[TT_SO_LUONG];
    int dau = 0, cuoi = 0;

    toi_duoc[TT_CHO] = 1;
    hang_doi[cuoi++] = TT_CHO;

    while (dau < cuoi) {
        int t = hang_doi[dau++];

        for (int s = 0; s < SK_SO_LUONG; ++s) {
            int tiep = BANG[t][s];

            if (!toi_duoc[tiep]) {
                toi_duoc[tiep]   = 1;
                hang_doi[cuoi++] = tiep;
            }
        }
    }

    for (int t = 0; t < TT_SO_LUONG; ++t)
        KT(toi_duoc[t]);

    return 0;
}

/* Kiểm thử 3: từ mọi trạng thái, sự kiện DUNG luôn đưa về CHO */
static int kt_dung_luon_ve_cho(void)
{
    for (int t = 0; t < TT_SO_LUONG; ++t)
        KT(BANG[t][SK_DUNG] == TT_CHO);

    return 0;
}

/* Kiểm thử 4: một chuỗi sự kiện cụ thể cho ra đúng dãy trạng thái mong đợi */
static int kt_chuoi(void)
{
    SuKien    vao[] = { SK_BAT_DAU, SK_OK,     SK_HONG, SK_DUNG };
    TrangThai ra[]  = { TT_DANG_NOI, TT_DA_NOI, TT_LOI,  TT_CHO };

    TrangThai tt = TT_CHO;

    for (size_t i = 0; i < sizeof vao / sizeof vao[0]; ++i) {
        tt = chuyen(tt, vao[i]);
        KT(tt == ra[i]);
    }

    return 0;
}

/* Kiểm thử 5: giá trị lạ không làm sập chương trình */
static int kt_gia_tri_la(void)
{
    KT(chuyen((TrangThai)999, SK_OK) == TT_LOI);
    KT(chuyen(TT_CHO, (SuKien)999)   == TT_CHO);
    KT(chuyen((TrangThai)-1, SK_OK)  == TT_LOI);

    return 0;
}

int main(void)
{
    if (kt_bang_hop_le())      return 1;
    if (kt_toi_duoc())         return 1;
    if (kt_dung_luon_ve_cho()) return 1;
    if (kt_chuoi())            return 1;
    if (kt_gia_tri_la())       return 1;

    printf("Tat ca %d luot kiem thu deu qua\n", so_luot);

    return 0;
}

terminal

gcc -std=c17 -Wall -Wextra -g -fsanitize=address,undefined test.c -o test && ./test

Tat ca 31 luot kiem thu deu qua

Năm loại kiểm thử này áp dụng cho mọi máy trạng thái

Kiểm thử	Bắt được lỗi gì
Mọi ô cho trạng thái hợp lệ	Ô để trống vô ý, hoặc gõ nhầm tên hằng
Mọi trạng thái tới được	Trạng thái chết, tức trạng thái không đường nào dẫn tới
Bất biến của một sự kiện	Vi phạm quy tắc nghiệp vụ, ví dụ lệnh dừng phải luôn dừng được
Chuỗi sự kiện cụ thể	Sai ở một ô cụ thể mà bốn kiểm thử kia không thấy
Giá trị lạ	Thiếu kiểm tra biên, lỗi vượt biên mảng

Số ô của bảng là hữu hạn và nhỏ, nên kiểm thử toàn diện là chuyện làm được. Đây là ưu điểm lớn nhất của mô hình này so với chuỗi if: bạn biết chắc mình đã phủ hết.

Kiểm tra thêm lúc biên dịch

/* Bảo đảm kích thước bảng khớp với số hằng enum */
_Static_assert(sizeof BANG / sizeof BANG[0] == TT_SO_LUONG,
               "So dong cua bang khong khop so trang thai");

_Static_assert(sizeof BANG[0] / sizeof BANG[0][0] == SK_SO_LUONG,
               "So cot cua bang khong khop so su kien");

Sinh sơ đồ từ bảng

sinh-so-do.c

/* In ra định dạng DOT để vẽ sơ đồ bằng Graphviz */
void in_so_do(void)
{
    printf("digraph {\n");
    printf("  rankdir=LR;\n");

    for (int t = 0; t < TT_SO_LUONG; ++t)
        for (int s = 0; s < SK_SO_LUONG; ++s) {
            int tiep = BANG[t][s];

            if (tiep != t)      /* bỏ qua các cạnh tự vòng cho gọn */
                printf("  %s -> %s [label=\"%s\"];\n",
                       TT_TEN[t], TT_TEN[tiep], SK_TEN[s]);
        }

    printf("}\n");
}

terminal

./may-trang-thai --so-do | dot -Tpng -o so-do.png

# Sơ đồ luôn khớp với mã, vì cả hai sinh từ một bảng

xdg-open so-do.png

Đây là lợi ích cuối cùng của mô hình bảng: hành vi của chương trình là dữ liệu, nên bạn kiểm tra được nó, vẽ được nó, và thậm chí đọc được nó từ file cấu hình lúc chạy.

Tự làm thử

Vẽ máy trạng thái của đèn giao thông ba màu ra giấy, rồi cài nó bằng bảng chuyển.
Cài máy trạng thái kết nối trong bài, chạy chuỗi sự kiện và in ra từng bước chuyển.
Bỏ phần kiểm tra biên trong hàm chuyen, truyền một giá trị lạ và chạy dưới -fsanitize=address.
Thêm trạng thái TT_DANG_DONG vào máy, xác nhận bảng và bảng tên tự lớn theo.
Cài bảng có hành động, viết bốn hàm hành động in ra tên của chúng.
Viết đủ năm loại kiểm thử trong bài, cố tình để trống một ô rồi xem kiểm thử nào bắt được.
Cài hàm sinh sơ đồ DOT, vẽ ra ảnh và đối chiếu với hình trong bài.
Cài trình phân tích số thực bằng máy trạng thái: nhận dạng chuỗi có dạng dấu, phần nguyên, dấu chấm, phần lẻ.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

Máy trạng thái gồm tập trạng thái, tập sự kiện và quy tắc chuyển. Enum biểu diễn hai tập đầu, mảng hai chiều biểu diễn quy tắc.
Dùng khởi tạo có chỉ định cho bảng, và đặt trạng thái đầu ở giá trị 0 để ô bỏ trống có ý nghĩa hợp lý.
Luôn kiểm tra biên trước khi tra bảng, vì sự kiện thường đến từ bên ngoài chương trình.
Một biến trạng thái thay được nhiều biến cờ, và nó làm những trạng thái sai trở nên không biểu diễn được.
Số ô của bảng là hữu hạn nên kiểm thử toàn diện làm được. Năm loại kiểm thử trong bài áp dụng cho mọi máy trạng thái.