kfifo算法原理



  • kfifo的算法原理

    kfifo本质上就是一个无锁队列,它的结构体如下:

    struct __kfifo {
        unsigned int in;
        unsigned int out;
        unsigned int mask;
        unsigned int esize;
        void         *data;
    };
    

    inout分别指向入队和出队的位置。mask等于队列长度减一。esize是元素长度,也就是这个队列的颗粒度。队列默认的颗粒度是字节。

    讨论mask的作用,就不得不提及kfifo的一个潜规则——队列长度一定为2的整数次幂。这样一来,对队列长度取模就可以直接利用mask & offset的方法快速求得(取模运算耗时远高于位操作)。

    环形队列的一个关键问题就是——如何判断队列为空或者队列已经满了。一般的处理办法或许会在inout超过队列长度之后进行取模,让inout两个指针始终保持在合法范围内。但是这就会产生一个难题——无法很简洁地区分队列为空和队列已满,因为这两个情况下都满足in==out。此时就不得不在结构体里添加一个occupied_size字段用来表示当前已入队的元素数量,这样显然并非最优解。

    kfifo里是这样解决这个问题的:

    • inout不需要保证在合法范围内。此时就可以使用in-out表示当前入队的元素数量。
    • kfifo_putkfifo_get的时候,需要对数组进行读写操作,此时数组的索引用in & maskout & mask保证索引within range
    • inout的类型都是unsigned int,它们溢出后不会有任何影响。因为对于unsigned int这个类型而言,相减得到的结果是绝对值,所以比如说in溢出后小于out,但是in - out得到的还是入队的元素数量。
    • in == out代表队列为空;in - out == mask + 1表示队列已经满了。


  • 相关源码链接:bootlin kfifo.h source


 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

Looks like your connection to Dian was lost, please wait while we try to reconnect.