标签：队列 RAM 链表 出队 Verilog 空闲 指针
链表在缓存管理中有重要的应用，对所有输入的数据都放在一块大的RAM中缓存，并且根据一定的规则将数据分类并划归不同的队列，不同队列的数据可以分别控制输出，队列内，数据按严格先进先出的顺序操作
我们假设输入数据的位宽为256，并且开辟一个2^20深度的RAM用于缓存，那么RAM大小为32MB。将输入数据划归1024个队列，则需要对RAM进行链表操作，或者说是队列管理。
首先需要一个链表RAM，深度与数据RAM深度相同，队列链表RAM存放的是数据RAM的地址，所以位宽为20。其次，每个队列都需要维护对应的首指针和尾指针，队列的首尾指针需要依据链表规模决定使用RAM或者寄存器，对于本例，队列首指针（或者尾指针）大小为1024x20，需要使用RAM存储。此外，对于空闲链表，需要通过寄存器维护其首尾指针。
在初始状态，需要初始化链表及队列信息，包括
1、链表首指针指向链表RAM首地址0，链表尾指针指向链表RAM尾地址2^20-1
2、初始化链表RAM的值，往地址addr中写入数据addr+1
3、给所有队列空标记置1
初始化完毕后，可以进行队列的入队和出队操作，入队指的是接受数据，并加入队列的过程，出队即入队的逆过程
入队过程
入队是从数据队列的角度看，但是从空闲队列的角度看，其实是出队过程。将接收数据写入空闲队列首指针的地址即可，队列链表管理操作如下：
首先是空闲队列的操作，空闲队列为出队，出队需要更新队列首指针，取出当前队列首指针，并从链表中取得当前首指针的下一跳，将得到的下一跳作为新的首指针。
然后是数据队列的操作，数据队列为入队，对于入队，分为2种情况：队列为空与队列非空。这就需要用到前面初始化时提到的队列空标记。
当队列为空，将从空闲队列出队的值作为当前队列的首尾指针，空标记置0，无需对链表操作。
当队列非空，往链表当前队列尾指针地址写入从空闲队列出队的值，且将该值作为新的队列尾指针。
出队过程
同样的，这里说的出队是对数据队列而言，对空闲队列而言则是入队。从当前队列首指针把数据读出即完成了数据的处理，队列链表管理操作如下：
对于数据队列来说，也是需要分2种情况讨论：当前是否为队列的最后一个数据。这可以通过当前队列的首尾指针是否相等来判定，相等为最后一个数据，否则不是最后一个数据。
当为最后一个数据，将队列空标记置1即可，无需操作队列首尾指针。
当不为最后一个数据，从链表中取得当前队列首指针的下一跳，并将它作为新的首指针。
空闲队列的操作为，往当前空闲队列尾指针写入数据队列出队的首指针，并且将它作为新的空闲队列尾指针。
请注意，上述表述中未提及空闲队列的空标记操作过程，具体实现时按照数据队列的逻辑控制即可
标签：队列,
RAM,
链表,
出队,
Verilog,
空闲,
指针
From： https://www.cnblogs.com/qingkai/p/18316078