短信营业厅指令匹配算法初探

《短信营业厅指令匹配算法初探》由会员分享，可在线阅读，更多相关《短信营业厅指令匹配算法初探（11页珍藏版）》请在装配图网上搜索。

1、短信营业厅指令匹配算法初探作者：李文强摘要：短信营业厅指令的匹配直接影响到短信营业厅的整体性能，为了能达到快速高效的匹配用户的指令，需要对短信营业厅指令按照用户使用量支持动态优先级指令排序。关键字：短信营业厅；指令集；哈希算法；优先级排序引言随着手机用户数据的增加和科技的发展，使用短信营业厅受理业务的用户也越来越多，短信营业厅处理的数据量也急剧增加。对短信营业厅的性能要求也越来越高。而短信匹配是短信营业厅的一个关键性的环节，匹配短信的效率直接的影响着短信营业厅的整体性能。因此，对于优化短信营业厅的指令集也势在必行。1 内存数据结构1.1 指令结构体指令结构体是存放短信营业厅配置在表里的短信指令

2、和对应的服务和数据。struct sms_order_struct string strSms; /短信指令，key struct sms_order *p_data; /短信指令对应的服务组件以及配置数据（使用者自行设计） struct sms_order_struct *p_next; /hash table 指向下一个指令结构体 struct sms_order_struct *p_next_used; /用户指令使用动态排序;其中，strSms数据库中配置的短信指令。*p_data是短信指令对应的数据结构（使用者根据业务自己定义）。*p_next指针用于把指令结构体挂载到哈希数组中，形

3、成单向链表。*p_next_used指针用来排序最近使用的指令结构。初始化时，指针应都为NULL。1.2 哈希数组哈希数组为指针数组，指向短信指令集结构体。用户挂载所有的配置指令。#define HASH_COUNT 7 /hash数组的大小struct sms_order_struct *hash_tableHASH_COUNT; /哈希数组#define _hashfn(strSms) /哈希函数HASH_COUNT哈希数组的大小定义成常量，使用者可根据短信营业厅的指令的数量级进行调整。*hash_table用来存储和挂载短信指令结构体。_hashfn哈希函数，根据指令计算对应的指令结构体

4、应该挂载到哈希数组的那个数组下。哈希函数的算法由使用者自己定义，原则上应该能保证所有指令集挂载完毕后，每个哈希数组上挂载的指令集基本相等。目前，我设计的哈希函数的算法是根据短信指令的字母转换为大写取ASCII码的平均值，然后对HASH_COUNT取余。该方法可能不是最优的，但是至少可以保证每个哈希数组上挂载的指令结构体数组基本相等。1.3 最常使用指令链表最常使用指令链表结构，是用来维护和查找最常使用的指令。struct sms_used_struct int ilock; /更新锁，0-没有更新锁定。1-更新锁定 struct sms_order_struct *p_next_used; /

5、最常使用指令链表头指针 int inum; /最常使用指令链表长度（默认为10，可以通过配置文件更改）该值也可以定义为常量，从该结构体抽离出去。;ilock更新队列锁。读取该队列时不需要获得该锁，只有更新该队列才必须获得该锁。*p_next_used该指针指向最常使用指令队列的第一个指令结构体，即指向最常使用的队列。每次需要更新该队列是，总更新队列的头部。每次匹配指令时从该指针指向的指令结构体开始匹配。inum最常使用指令链表长度，该值默认为10，可以通过配置文件进行修改，修改的大小可以根据短信营业厅指令集指令数量来定。1.4 哈希数组指示结构体该结构体是为了动态更新指令集而设计的。sturc

6、t hashTable_head int ilock; /更新锁（0-没有更新锁定，1-更新锁定） void *plockList; /等待队列 int iuserNum; /正在使用指令集线程数量（初始化为0）;ilock更新锁用来动态更新哈希数组上挂载的所有指令集来使用。线程获取文件锁夺取配置文件上更新标识，如果需要动态更新，则必须获得该锁并且锁定。*plockList等待锁的线程队列。iuserNum正在遍历该哈希数组的线程数量。1.5 内存指令集预览该内存预览图为定义的哈希数组长度为4，即：hash_table3。该内存指令集共有16个指令结构体。其中最常使用指令链表维护长度为4。内存

7、中哈希数组上挂载的指令集不会因为指令使用重新排列，只有在内存指令加载时，加载一次。加载时，指令也不会排序。根据读取数据库配置的指令先后，计划哈希值后，挂载对应的哈希数组项上。最常使用单链表会根据用户使用动态更新。2 指令集挂载2.1 指令集初始化读取数据库中的配置指令数据集。根据配置的指令关键值，调用哈希函数，计算哈希值。根据计算结果找到哈希数组中的数组项，遍历该项链表，挂载到链表结尾。新挂载的结构体的所有指针都指向NULL。当配置的指令标识有效时，需要初始化指令集。指令集初始化时，必须获得hashTable_head结构体中的更新锁（ilock），并且要锁定，锁定以后需要判断正在使用指令集数

8、量（iuserNum）是否为0，如果不为0，需要等待。如果为0，为了减少还有进程或线程正在匹配指令就更新需要再判断一次是否为0。如果此次判断不为0，则跳出到等待的标识处继续等待。如果判断为0，则进行更新。更新前判断哈希数组是否为空，不为空则需要先释放哈希数组链表内存。为空则挂载指令集。挂载指令集完毕后释放锁并唤醒等待队列上的线程或进程。获得文件锁，修改指令标识置为无效。2.2 最常使用链表更新每个线程或进程匹配成功指令后，都需要判断sms_used_struct结构体的更新锁（ilock）是否已经锁定，如果锁定则不处理。如果未锁定则获得该锁，并锁定。把匹配到指令更新到最常使用链表头。并更新sm

9、s_used_struct结构体指针，指向最常使用链表头，即本次使用的指令结构体。更新完毕后释放该锁。更新队列的时候，需要有个技巧，更新的时候不要断了原来的链表，防止其他线程遍历时产生异常。并且更的时候也不是每个未匹配的指令都会更新，更新前如果获得锁就更新，没有获得锁就不更新，直接跳过受理业务。这样节省了等待的时间。3 指令匹配3.1 从最常用链表中匹配匹配指令时，首先判断hashTable_head结构体中的ilock是否被锁定，如果锁定则随眠把自己加到等待队列plockList。如果没有被锁定，则根据sms_used_struct结构体中最常使用指令链表头指针（*p_used）指向的最常用

10、指令链表，遍历该链表进行匹配。如果匹配成功，则跳出受理业务。如果遍历次数已经超过最常使用指令链表长度（inum）或者指针队列上指令结构体中的指令使用动态排序指针（*p_next_used）为空还没有匹配到，则需要从指令集中匹配。3.2 从指令集中匹配根据指令调用哈希函数，得到哈希值。取对应哈希数组中的指针，遍历该链表匹配指令。如果队列遍历完毕没有匹配成功，则返回失败（此处也可根据使用情况特殊处理）。如果匹配成功，则获取hashTable_head结构体的更新锁（ilock），如果获得则需要锁定，锁定成功后更新最常使用队列后处理业务逻辑。如果没有获得该锁，直接处理业务。4 指令挂载和匹配流程整个

11、设计流程上会有两个锁机制。当程序处理逻辑进入匹配指令环节时，首先查看哈希数组头结构的锁是否被别的线程锁住。如果已经被锁，则本线程被加到等待队列上睡眠，等待锁住该资源的线程唤醒。如果没有被锁住，则判断指令集是否需要更新。如果需要更新，则判断使用该指令集的线程数，如果大于0则等待。此处线程不能睡眠，否则所有的线程都将睡眠。如果等于0，为了保险起见，需要再次判断一次是否等于0，如果不等于0，则回到首次判断等于0处，等待。如果等于0，则释放原指令结构体所分配的内存，初始化哈希数组和最常使用指令结构体。重新分配内存，加载指令集。加载完毕后释放哈希数组头结构的锁，唤醒等待队列所有的线程。本线程则和其他被唤

12、醒的线程重新匹配指令。如果不需要更新，则哈希数组头结构指针上正在使用指令集线程数加1，然后根据最常使用指令的头指针出遍历该单链表，如果链表指令结构体指向的下个指令为NULL，或遍历次数大于链表长度（此处的长度限制是必须的，否则该链表可能会把所有的指令串起来，如果这样遍历一次花费的时间就有点长了。），则表示没有从最常使用的指令中匹配到指令。此时，就需要根据指令计算哈希值，获得哈希数组上对应的链表，遍历该链表进行匹配。如果匹配成功，则判断最常使用头指针上的锁是否被锁定，如果被锁定则表示已经有其他线程正在更新，本线程不等待，正在使用指令集线程数减1后直接根据匹配到的指令受理业务。如果没有被锁定则锁定

13、，锁定后更新最常使用链后释放锁，最常使用线程数减1，退出受理业务。5 技术实现本算法用到了锁机制和信号量，如果要自己写锁则需要考虑用到信号量，如果要用linux线程库提供的锁，则可以把重点放在业务和流程上。下面介绍一下使用linux线程库提供的锁：linux线程库提供了三种锁，本算法使用其中的两种锁：互斥锁和读写锁。首先说一下读写锁，读写锁是一种特殊的自旋锁，在没有得到锁时，会不停的循环判断，即自旋。所以此锁比较浪费CPU时间。既然这样为什么还用此锁呢？考虑到短信营业厅业务上的需要，更新整个指令集不是很频繁的操作，大概一周一次或许更长时间，所以此处使用读写锁并不会太影响效率。读写锁的特性是写者

14、排他性的。一个读写锁同时只能有一个写者或多个读者。当读写锁是写加锁状态时，在这个锁被解锁之前，所有试图对这个锁加锁的线程都会被阻塞。当读写锁在读加锁状态时，所有试图以读模式对它进行加锁的线程都可以得到访问权，但是如果线程希望以写模式对此锁进行加锁，它必须直到所有的线程释放锁。而本算法的设计思路基本是这样的，当指令集需要更新时，需要得到写锁，得到锁以后，所有的需要匹配指令的线程都要被阻塞，而在更新前需要判断是否还有线程正在使用哈希数组上的指令集匹配指令。没有线程使用才可以更新。而读写锁还有另外一个特性，通常，当读写锁处于读模式锁住状态时，如果有另外线程试图以写模式加锁，读写锁通常会阻塞随后的读模

15、式锁请求，这样可以避免读模式锁长期占用。这就可以解决，如果有线程需要更新指令集，此时就会阻塞后续的匹配指令的线程。所以，根据读写锁的特性和本设计思路。在哈希数组上使用读写锁是在好不过的了。那么另外更新动态链表时需要用到互斥锁。更新动态链表时，会有这样几个特性，并不是每个线程都会更新动态指令链表，即使不更新动态指令链表也并不影响业务。此时就需要用到互斥锁，尤其是互斥锁的trylock的方法。线程在动态指令链表上没有匹配到对应的指令，而在哈希数组上匹配到了，此时就需要把指令更新到动态链表上，而更新的时候需要检查是否有其他线程在更新，如果有其他线程更新，则本线程就放弃本次更新。那么此时就需要用到tr

16、ylock，该函数是pthread_mutex_lock函数的非阻塞版本。如果mutex参数所指定的互斥锁已经被锁定的话，调用pthread_mutex_trylock函数不会阻塞当前线程，而是立即返回一个值来描述互斥锁的状况。如果是失败表示有线程更新动态链表，此时，就放弃更新。而更新链表的时候并不会把链表打乱或截断，所以匹配指令时就不需要获得互斥锁。综上所述，算法的锁机制，用这两个锁再好不过。基本解决了算法上的需求。结语本算法在一定程度上解决了短信指令匹配效率。整个算法上还是比较严谨的，但是在没有获得锁后就对临界资源（正在使用指令集线程数量）进行了操作，个人考虑这也无可大碍，因为只是更新一个

17、数量（这个数量是很重要的，处理不正确会发生严重缺陷），不过没有经过测试。如果使用linux线程库提供的锁机制，则不存在这种问题。哈希函数也不是很完美，目前也没有想到更好的算法，但是至少可以保证每个哈希数组上挂的链表长度基本一致。还有哈希数组的长度和最常使用指令链表的长度不应该是随便定的，应该根据短信指令的多少算出一个值，使得数据量大了以后平均匹配指令时间达到最优。参考文献赵炯， Linux内核完全剖析M，北京：机械工业出版社，2011.9W.Richard Stevens Stephen A.Rago. UNIX环境高级编程M. 尤晋元，张亚英，戚正伟， 译。 北京：人民邮电出版社 2006.文档可能无法思考全面，请浏览后下载，另外祝您生活愉快，工作顺利，万事如意!11 / 11