ITKeyword,专注技术干货聚合推荐

注册 | 登录

Linux内核工程导论——数据结构:其他

ljy1988123 分享于 2015-10-08

推荐:Linux内核工程导论——数据结构:链表与哈希

1 链表与哈希表 链表可以把离散时间到达的数据结构串起来,使其可以被更容易的索引。Linux内核中全部使用双向链表。那为何链表要与哈希表放在一起介绍呢?因为哈

2018阿里云全部产品优惠券(新购或升级都可以使用,强烈推荐)
领取地址https://promotion.aliyun.com/ntms/yunparter/invite.html

KFIFO

        缓冲区在文件系统中经常用到,通过缓冲区缓解cpu读写内存和读写磁盘的速度。例如一个进程A产生数据发给另外一个进程B,进程B需要对进程A传的数据进行处理并写入文件,如果B没有处理完,则A要延迟发送。为了保证进程A减少等待时间,可以在A和B之间采用一个缓冲区,A每次将数据存放在缓冲区中,B每次冲缓冲区中取。这是典型的生产者和消费者模型,缓冲区中数据满足FIFO特性,因此可以采用队列进行实现。Linux内核的kfifo正好是一个环形队列,可以用来当作环形缓冲区。生产者与消费者使用缓冲区如下图所示:


优先级堆

位数组bitmap

    位数组叫做bitmap,是以位为单位存储值的方式。很多情况下,一些值只有两个取值,而这些值又很多,就可以用位数组,也可以看成是bool类型的数组,但是提供了更多的相关操作。

推荐:Linux内核源码学习之 数据结构

本篇记录在学习Linux内核源码过程中对一些知道但不熟悉不会用的数据结构进行记录。 union 是在学习进程复制函数do_fork中遇到的: <sched.h>  union thread_unio

    位数组可以用来执行排序算法,利用的就是数组中的索引值,对某个索引值进行设置1,就表示记录,然后顺序输出索引值就是排序后的结果。更多的,位数组用在文件系统中充当位图。几乎大部分的文件系统都有位图的概念,例如ext2中就有inode位图和数据块位图,用来表示对应序号的inode或者数据块有没有被使用。还有在raid系统中,例如raid1的数据一致性保障,由于系统有两份拷贝,不一致的情况就有可能发生,当保证一致时就会设置对应的位图位。如此后续的更新都是增量的,只需要查看位图就知道哪些是未能保证一致的数据。

   


llist


推荐:Linux内核数据结构(一)

  链表,队列,映射,二叉树等数据结构是程序设计中常用的数据结构。为了统一这些数据结构的操作接口,Linux内核开发者实现了一些标准的操作接口及实现(使用了

KFIFO         缓冲区在文件系统中经常用到,通过缓冲区缓解cpu读写内存和读写磁盘的速度。例如一个进程A产生数据发给另外一个进程B,进程B需要对进程A传的数据进行处理并写入文件,如果B没有处

相关阅读排行


用户评论

游客

相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。