静态数组的妙用--IPVS集群中的TCP状态机

说到状态机，那可以写一大本书了，很复杂的一个概念，说到数组，可能仅仅能写几页，它只是编程意义上的一个概念，很多关于数组和指针的区别的文章讲述了数组名其实就是一个指针，然而这些说法背后的意义却很少有文章提及，而实际上，数组这个概念只是借助了指针的概念，它是一系列地址连续的指针，而指针则是个更具有一般意义的概念，并不要求连续性，由此可见它们并不相同，在C语言结构体中，用数组还是用指针取决于你是想浅拷贝还是深拷贝，若该字段更多的被共享或者写时复制，那么在拷贝时则用浅拷贝更加有效率，反之独享的字段则最好用深拷贝。

数组可不是仅仅和指针有联系，它更大的意义在于存储上，众所周知，数组整体上分为下标和元素值，它们在存储的意义上可以和索引和值类同。如果我们将索引和值的概念分开，那么数组仅仅可以被存储数据，也就是说是完全静态的，当然别的存储结构比如链表，二叉树，B+树等等最后都可以被归结到数组，就看你的存储策略是什么了。另一个众所周知的思想就是冯氏机器上的程序分为代码和数据，数据只是规定了个性的策略，而执行流程由代码控制，代码和数据到底谁是动态谁是静态，这是一个问题，在执行期间，代码是动态的，而在存储上，数据是动态的，所以我们刚才说数组是静态的，这是在程序执行的意义上说的。这就好比一台铣床，它可以加工出不同形状的东西。

那么数组在程序执行时仅仅可以表示静态的数据吗？它能否被给与一些动态的意义呢，实际上是可以的，如果我们将它的索引和值联系起来的话，那么它是什么？它是状态机。状态机就是在一种状态下如果接受到一个事件的话那么可以切换到另一个状态，具体切换到什么状态取决于你接收到的事件和前一个状态，也就是取决于两个因素，我们可以把这两个因素分别作为行和列，这就成了数学上的二维矩阵，在编程上可以用二维数组表示，接下来看看怎么巧妙的将数组的索引和值相关联。状态机中的一个状态不是由前一个状态和事件决定吗？那么我们就将行作为事件，列的索引作为前一个状态的值，而列的值是下一个状态的索引，这样看看有什么问题，每个状态的下一个状态不一定一个，上一个状态也不一定一个，比如状态s1的下一个状态可能是s2和s3，这怎么办呢？在确定的事件被接收到的那一刻，状态就是确定的，实际上状态机就是一个连通的图，并且一个节点的入度和出度在确定的事件下都是唯一的，虽然在E-R模型上是不唯一的，但是在图论上它的下一个状态和上一个状态确实是唯一的。

接下来就着手实现这个数组。注意，根据上面的E-R模型的讨论和图论的讨论，数组的各个值的填充将是一个确定的动态的过程，也就是说填充顺序必须按照一定的顺序，什么顺序呢？就是状态机这个连通图的遍历顺序，一边遍历一遍填充数组，所有的路径遍历完了，数组也就填充完了，如果有剩余的元素没有被填充，那么就填上非法值就可以了。起初我一直想不通为何不能按照从左到右从上到下的顺序填充，而非要按照图的遍历顺序填充，使得我一直不能很好的为这个事情建模，后来发现，原来这个数组已经不再是个简单的存储装置了，而成了一个状态转换装置，索引和值已经有了明确的联系，既然有了联系当然就不能乱填了。

我十分佩服linux代码的作者，ipvs是linux上的一个基于netfilter的集群，内部就配置了一个以上说的那种数组，使用这样一个数组便省去了将代码写死到程序中带来的维护上的麻烦，如果将回调函数扩展进去，那么也就省去了状态机转换时的switch-case或者if-else if的麻烦，数据代码化，代码数据化，二维数组将索引和值结合这个做法做到了二者的统一，奇妙无比，最后欣赏一下这个ipvs作者的杰作：

#define sNO IP_VS_TCP_S_NONE

#define sES IP_VS_TCP_S_ESTABLISHED

#define sSS IP_VS_TCP_S_SYN_SENT

#define sSR IP_VS_TCP_S_SYN_RECV

#define sFW IP_VS_TCP_S_FIN_WAIT

#define sTW IP_VS_TCP_S_TIME_WAIT

#define sCL IP_VS_TCP_S_CLOSE

#define sCW IP_VS_TCP_S_CLOSE_WAIT

#define sLA IP_VS_TCP_S_LAST_ACK

#define sLI IP_VS_TCP_S_LISTEN

#define sSA IP_VS_TCP_S_SYNACK

struct tcp_states_t {

int next_state[IP_VS_TCP_S_LAST];

};

static struct tcp_states_t tcp_states [] = {

/* INPUT */

/* sNO, sES, sSS, sSR, sFW, sTW, sCL, sCW, sLA, sLI, sSA */

/*syn*/ {{sSR, sES, sES, sSR, sSR, sSR, sSR, sSR, sSR, sSR, sSR }},

/*fin*/ {{sCL, sCW, sSS, sTW, sTW, sTW, sCL, sCW, sLA, sLI, sTW }},

/*ack*/ {{sCL, sES, sSS, sES, sFW, sTW, sCL, sCW, sCL, sLI, sES }},

/*rst*/ {{sCL, sCL, sCL, sSR, sCL, sCL, sCL, sCL, sLA, sLI, sSR }},

/* OUTPUT */

/*syn*/ {{sSS, sES, sSS, sSR, sSS, sSS, sSS, sSS, sSS, sLI, sSR }},

/*fin*/ {{sTW, sFW, sSS, sTW, sFW, sTW, sCL, sTW, sLA, sLI, sTW }},

/*ack*/ {{sES, sES, sSS, sES, sFW, sTW, sCL, sCW, sLA, sES, sES }},

/*rst*/ {{sCL, sCL, sSS, sCL, sCL, sTW, sCL, sCL, sCL, sCL, sCL }},

/* INPUT-ONLY */

/*fin*/ {{sCL, sFW, sSS, sTW, sFW, sTW, sCL, sCW, sLA, sLI, sTW }},

/*rst*/ {{sCL, sCL, sCL, sSR, sCL, sCL, sCL, sCL, sLA, sLI, sCL }},

关于uc/os ii的调度就不多说那么多了，本文仅仅谈论思想。为了在确定的时间进行实时调度，坚决杜绝的就是任何动态算法，所谓动态算法就是时间不确定的算法，即使再高效再花哨也不行，必须是O(1)的才可以，因此ucos采用了静态数组存储调度信息，用一个8*8的矩阵来存储64个位，可以用8个char来表示，如果任务就绪就将该任务所在的位置设置为1，当然ucos不允许任何两个以及两个以上的任务优先级相同，这就是基础设施，最后在基础设施之上，调度算法变得非常简单，就是确定这个8*8图中最右上的为1的位置，这样呢就需要确定行和列，因此引入了两个基础设施的辅助设施，也就是两个一维数组，我们记为L和R，L数组确定行信息，R并不是确定列信息，这个说法显然不是那么对称，因此你要学会欣赏不对称美！我们说L确定了行信息，那么可以肯定的是这个被确定的行一定是最上面的行，也就是说L数组可以得到最上面有1的行号，想想看一共有8行，L可以确定，那么当确定了行之后，只需要在该行确定最右边的为1的那个位置即可，这个操作和确定行的操作一样，列的数量也是8，因此就没有必要再来一个确定列的数组了，不对称美就在这里体现，数据对称时代码不必对称，代码就是指操作，因此才有了批量生产，一台机器能生产一样的东西，而不必为每样相同的东西都造一台机器。言归正传，R数组是做什么用的呢？我们一直说L确定了一个最值，但是没有说怎么确定的，因此R就是确定最值的策略，当然也可以不用R，用位运算即可，不就是挑选一个8位数最右边的1是第几位吗？是的，但是要考虑细致一些，如果一台机器上没有位运算操作的指令，那么这个操作的时间就会是不确定的，即使有一个移位指令，那么移2位和移7位时间是不同的，因此就用了静态的数组，总之数组R就是一个元素个数为256的数组，记录了从0到255中最右边为1的位是第几个，这样就很好确定行和列了，当然如果一个任务就绪的话，它需要做的就是将L中从右开始的代表它的行号的那个位置为1即可，取出行号很简单，优先级模8即可。

既然可以使用静态数组，为何不平铺成一个64位的大数呢，这样就不用确定行和列了，只用确定列就好了，理论上是可以的，但是这个讲台数组将是2的64次方这么大，现在的机器能受了吗？因此将大数化小，额外增加了维度就可以了，就好比木头棍子太长无法携带，那么折上几折，它就不是棍子了，成了板子了，一维变成了二维，再叠几叠，就成一个木头块了，一维变成三维。

 本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1274004