本文对双向链表进行探讨，介绍的内容是Linux内核中双向链表的经典实现和用法。其中，也会涉及到Linux内核中非常常用的两个经典宏定义offsetof和container_of。内容包括： 1.Linux中的两个经典宏定义 2.Linux中双向链表的经典实现
在 Linux 源码 linux-5.6.18\include\linux\rculist.h 头文件中定义的就是 RCU 链表的操作 ,
RCU , 英文全称是 " Read-Copy-Update “ , 对应的中文名称是 ” 读取-拷贝-更新 “ , 这是 Linux 内核中的 ” 同步机制 " ;
Linux 内核源码 linux-5.6.18\kernel\sched\sched.h 中 , 定义的 struct sched_class 调度类结构体 , 就是 " 调度器 " 对应的类 ;
在linux内核中封装了一个通用的双向链表库，这个通用的链表库有很好的扩展性和封装性，它给我们提供了一个固定的指针域结构体，我们在使用的时候，只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了，具体的实现、链接并不需要我们关心，只要调用提供给我们的相关接口就可以完成了。
[121] 编写UNIX/Linux命令以列出目录中所有文件的名称（例如/usr/bin/dir/）（及其子目录），文件应该包含不区分大小写的“I am preparing for Interview”。
本文简介本文介绍Linux RCU的基本概念。这不是一篇单独的文章，这是《谢宝友：深入理解Linux RCU》系列的第3篇，前序文章：谢宝友： 深入理解Linux RCU之一——从硬件说起= 谢宝友：
操作系统为进程维护了打开的文件列表，每个进程维护了一个file数组字段（struct file * fd[NR_OPEN]）；每个元素指向一个file结构体。每个file结构体有一个字段指向inode结构体，inode管理这个文件的内容、权限等信息。这里分析的是file结构体的管理。
本文讲述了Linux中RCU（Read-Copy-Update）机制在内存管理中的重要作用，以及如何在Linux内核中实现和管理RCU。在Linux内核中，RCU用于在多个进程共享相同内存空间时，保证这些进程之间的数据一致性。本文首先介绍了RCU的基本原理，然后逐步深入介绍了Linux内核中RCU的实现细节。最后，通过一个具体的例子，展示了如何在Linux内核中实现一个简单的RCU。
/**************************************************************** 文件内容:内核之链队操作 版本V1.0 作者：HFL 时间：2013-12-22 说明：用户态中链表每个节点包含数据域和指针域，而内核态是每个数据中包含链表 因此内核态链表一般是嵌套在某个包含数据成员的结构体来实现。 内核的链表应用非常广泛：进程管理，定时器，工作队列，运行队列。总之 内核对于多个数据的组织和多个熟悉的描述都是通过链表串起来的。 *****************************************************************/ #include <linux/kernel.h> #include <linux/module.h> #include <linux/init.h> #include <linux/slab.h> #include <linux/list.h> MODULE_DESCRIPTION("My Module"); MODULE_ALIAS("My module"); MODULE_LICENSE("GPL"); MODULE_AUTHOR("HFL21014"); struct student { char name[100]; int counter; struct list_head list; }; struct student *Mystudent; struct student *Temp_student; struct list_head student_list; struct list_head *pos; int Kernel_list_init() { int j = 0; INIT_LIST_HEAD(&student_list); Mystudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL); memset(Mystudent,0,sizeof(struct student)*5); for(j=0;j<5;j++) { sprintf(Mystudent[i].name,"Student%d",j+1); Mystudent[j].counter = j+1; list_add( &(Mystudent[j].list), &student_list); } list_for_each(pos,&student_list) //遍历整个内核链表,pos其实就是一个for循环标量。中间临时使用，既不输入也不输出 { Temp_student = list_entry(pos,struct student,list); printk("hello,my student %d name: %s\n",Temp_student->counter,Temp_student->name); } return 0; } void Kernel_list_exit() { int k ; /* 模块卸载是要删除链表，并释放内存 */ for(k=0;k<10;jk++) { list_del(&(Mystudent[k].list)); } kfree(Mystudent); } module_init(Kernel_list_init);
在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在include/linux/list.h实现的一个相当精彩的链表数据结构。
在Linux内核中，对于数据的管理，提供了2种类型的双向链表：一种是使用list_head结构体构成的环形双向链表；另一种是使用hlist_head和hlist_node2个结构体构成的具有表头的链型双向链表。
作为世界最牛逼黑客之一，Linus Torvalds的特立独行就跟他的软件Linux一样受人瞩目，那你想知道Linux的创始人Linus Torvalds是怎么写C语言程序的吗？一起来感受下。
在 Linux 内核中使用最多的数据结构就是链表了，其中就包含了许多高级思想。 比如面向对象、类似C++模板的实现、堆和栈的实现。
RCU（Read-Copy Update）是数据同步的一种方式，在当前的Linux内核中发挥着重要的作用。RCU主要针对的数据对象是链表，目的是提高遍历读取数据的效率，为了达到目的使用RCU机制读取数据的时候不对链表进行耗时的加锁操作。这样在同一时间可以有多个线程同时读取该链表，并且允许一个线程对链表进行修改（修改的时候，需要加锁）。RCU适用于需要频繁的读取数据，而相应修改数据并不多的情景，例如在文件系统中，经常需要查找定位目录，而对目录的修改相对来说并不多，这就是RCU发挥作用的最佳场景。 Linux内核源码当中,关于RCU的文档比较齐全，你可以在 /Documentation/RCU/ 目录下找到这些文件。Paul E. McKenney 是内核中RCU源码的主要实现者，他也写了很多RCU方面的文章。他把这些文章和一些关于RCU的论文的链接整理到了一起。http://www2.rdrop.com/users/paulmck/RCU/ 在RCU的实现过程中，我们主要解决以下问题： 1，在读取过程中，另外一个线程删除了一个节点。删除线程可以把这个节点从链表中移除，但它不能直接销毁这个节点，必须等到所有的读取线程读取完成以后，才进行销毁操作。RCU中把这个过程称为宽限期（Grace period）。 2，在读取过程中，另外一个线程插入了一个新节点，而读线程读到了这个节点，那么需要保证读到的这个节点是完整的。这里涉及到了发布-订阅机制（Publish-Subscribe Mechanism）。 3， 保证读取链表的完整性。新增或者删除一个节点，不至于导致遍历一个链表从中间断开。但是RCU并不保证一定能读到新增的节点或者不读到要被删除的节点。 宽限期
伙伴系统是常用的内存分配算法，linux内核的底层页分配算法就是伙伴系统，伙伴系统的优点就是分配和回收速度快，减少外部碎片。算法描述:
Linux定时器分为低精度定时器和高精度定时器两种类型，内核对其均有实现。本文讨论的是我们在应用程序开发中比较常见的低精度定时器。作为常用的基础组件，定时器常用的几种实现方法包括：基于排序链表实现、基于小根堆实现、基于红黑树实现、基于时间轮实现。本文讲解的是时间复杂度最优，也是linux内核采用的基于时间轮的实现方式。
在上期文章中，已经给大家分享过offsetof()和container_of两个宏函数，这两个宏函数在Linux内核链表里面有大量的应用，对于我们平时工作写代码有很大的帮助。下面是Linux内核链表的内容分享。
在上一篇博客 【Linux 内核 内存管理】RCU 机制 ① ( RCU 机制简介 | RCU 机制的优势与弊端 | RCU 机制的链表应用场景 ) 中 , 分析了 RCU 机制的优势与弊端 ;
树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。先从整体上认识下二叉树及其他各种树的区别和用途。
节点既包含了后续节点的指针，也包含了前趋节点的指针，而且一般都设计成循环，这样就可以非常方便地从链表的任意一个位置开始遍历整个链表。
定时任务在很多场景都需要用到，比如游戏的 Buff 实现，Redis 中的过期任务，Linux 中的定时任务，电商未支付订单的关闭等等。
虽然看起来以上的说法很抽象，给人如坠雾里的感觉，其实就是用C语言进行遇到问题、分析问题和解决问题的过程。
Ask how something can be done rather than say it can't be done.
今天一个老外在邮件列表上问了一个问题，就是ip addr add和ifconfig的区别，我给他进行了解答，可能因为英语不好吧，解答的很简单，因此我还是要在这里详细说明一下。其实它们之间没有什么区别，只 是表述方式不同罢了。如果你非常理解网络协议的原理以及网络的分层架构那么我想你就不会有这个问题，实际上，每一个网卡设备都有一个mac地址，但是却可 以有多个网络层地址，比如IP地址，然而这个事实无法很好地像用户提供操作接口，所以就引出了ip别名（IP aliases）和辅助ip（secondary IP addresses）的概念。其实很容易理解这个事实，按照分层的思想，下层总是为上层服务，也就是为上层提供舞台，上层利用下层的服务，而不必让下层知 道自己的情况，如果一个拥有合理mac地址的网卡没有配置网络层地址（比如IP地址）这件事合理的话，那么为这个设备配置多个IP地址也是合理的，正好像 一个ip可以对应多个应用层端口一样，也就是说，下层对上层总是一对多的关系，在分层架构中这种关系是合理的。下面我们就看一下linux的网卡的ip地 址结构。刚才说了在linux中，一个网卡可以有多个IP，那么这多个ip有什么关系呢？其实这些ip组成了一个吊链结构，所谓吊链结构就是一些节点链接 成一条链，然后每个节点带有自己的一条链，如下图所示：
Linux内核实现了一批优雅而功能强大的双向循环列表操作宏，它们位于/usr/include/linux/list.h（请注意直接#include会报编译错误），这些宏可以直接扣出来，在需要时使用。
一、概念： 大多数内核子系统都是相互独立的，因此某个子系统可能对其它子系统产生的事件感兴趣。为了满足这个需求，也即是让某个子系统在发生某个事件时通知其它的子 系统，Linux内核提供了通知链的机制。通知链表只能够在内核的子系统之间使用，而不能够在内核与用户空间之间进行事件的通知。 通知链表是一个函数链表，链表上的每一个节点都注册了一个函数。当某个事情发生时，链表上所有节点对应的函数就会被执行。所以对于通知链表来说有一个通知 方与一个接收方。在通知这个事件时所运行的函数由被通知方决定，实际上也即是被通
链表是线性表的链式存储方式，逻辑上相邻的数据在计算机中的内存位置不必须相邻，给每一个元素 加一个指针域，指向下一个元素的位置。
多线程调试的主要任务是准确及时地捕捉被调试程序线程状态的变化的事件，并且GDB针对根据捕捉到的事件做出相应的操作，其实最终的结果就是维护一根叫thread list的链表。上面的调试命令都是基于thread list链表来实现的，后面会有讲到。
inotify是Linux中用于监控文件系统变化的一个框架，不同于前一个框架dnotify, inotify可以实现基于inode的文件监控。也就是说监控对象不再局限于目录，也包含了文件。不仅如此，在事件的通知方面，inotify摈弃了dnotify的信号方式，采用在文件系统的处理函数中放置hook函数的方式实现。
LRU是常见的缓存淘汰策略，用于分布式系统的缓存、页表置换等场景。然而，经典的哈希链表实现事实上并不是很好的实现策略。
这篇文章是对 Linux 内存相关问题的集合，工作中会有很大的帮助。关注公号的朋友应该知道之前我写过从内核态到用户态 Linux 内存管理相关的基础文章，在阅读前最好浏览下，链接如下：
关于空闲空间的管理，前面提到的是已被占用的数据块的组织和管理。接下来要解决的问题是，当我要保存一个数据块时，应该将其放在硬盘的哪个位置。难道需要扫描所有的块，随意找个空的地方放吗？
看 PHP7 底层源码的书，其中提到 PHP7 的数组使用逻辑链表在进行维护，所谓逻辑链表，就是不再使用指针进行管理，而是使用数组这种数据结构，数组中的成员中会维护下一个节点的数组的下标。这样让我想起了数据结构中学到的静态链表。
list是新队列的head指针, 包括的元素从原head队列的第一个元素到entry, head队列仅包括余下的元素
START ---- hello，大家好！我是木荣君。最近比较火的ChatGPT着实令人眼前一亮。先来说一说ChatGPT是什么？ChatGPT（全名：Chat Generative Pre-trained Transformer），美国OpenAI研发的聊天机器人程序，于2022年11月30日发布。ChatGPT是人工智能技术驱动的自然语言处理工具，它能够通过理解和学习人类的语言来进行对话，还能根据聊天的上下文进行互动，真正像人类一样来聊天交流，甚至能完成撰写邮件、视频脚本、文案、翻译、代码，写论文等任务
Read-copy update (RCU) 是一种 2002 年 10 月被引入到内核当中的同步机制。通过允许在更新的同时读数据，RCU 提高了同步机制的可伸缩性（scalability）。相对于传统的在并发线程间不区分是读者还是写者的简单互斥性锁机制，或者是哪些允许并发读但同时不 允许写的读写锁，RCU 支持同时一个更新线程和多个读线程的并发。RCU 通过保存对象的多个副本来保障读操作的连续性，并保证在预定的读方临界区没有完成之前不会释放这个对象。RCU定义并使用高效、可伸缩的机制来发布并读取 对象的新版本，并延长旧版本们的寿命。这些机制将工作分发到了读和更新路径上，以保证读路径可以极快地运行。在某些场合（非抢占内核），RCU 的读方没有任何性能负担。
输入输出(input/output)的对象可以是文件(file)， 网络(socket)，进程之间的管道(pipe)。在linux系统中，都用文件描述符(fd)来表示。
前言 上一篇《数据结构和算法之时间复杂度和空间复杂度》中介绍了时间复杂度的概念和常见的时间复杂度，并分别举例子进行了一一说明。这一篇主要介绍线性表。 线性表属于数据结构中逻辑结构中的线性结构。回忆一下，数据结构分为物理结构和逻辑结构，逻辑结构分为线性结构、几何结构、树形结构和图形结构四大结构。其中，线性表就属于线性结构。剩余的三大逻辑结构今后会一一介绍。 线性表 基本概念 线性表（List）：由零个或多个数据元素组成的有限序列。 注意： 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3
epoll有EPOLLLT和EPOLLET两种触发模式，水平触发和边缘触发. 此处略
链表是一种常用的组织有序数据的数据结构，它通过指针将一系列数据节点连接成一条数据链，是线性表的一种重要实现方式。相对于数组，链表具有更好的动态性，建立链表时无需预先知道数据总量，可以随机分配空间，可以高效地在链表中的任意位置实时插入或删除数据。 通常链表数据结构至少应包含两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型，下面分别给出这几类常见链表类型的示意图：
linux 内存是后台开发人员，需要深入了解的计算机资源。合理的使用内存，有助于提升机器的性能和稳定性。本文主要介绍 linux 内存组织结构和页面布局，内存碎片产生原因和优化算法，linux 内核几种内存管理的方法，内存使用场景以及内存使用的那些坑。从内存的原理和结构，到内存的算法优化，再到使用场景，去探寻内存管理的机制和奥秘。
munmap 系统调用函数 调用了 vm_munmap 函数 , 在 vm_munmap 函数 中 , 又调用了 do_munmap 函数 , do_munmap 函数 是 删除 内存映射 的 核心函数 ;
hi，大家好，我是阿荣，今天分享一些对数据结构和算法精华总结，希望对大家的面试或者工作有一定的帮助；
点击上方“芋道源码”，选择“设为星标” 管她前浪，还是后浪？ 能浪的浪，才是好浪！ 每天 10:33 更新文章，每天掉亿点点头发... 源码精品专栏 原创 | Java 2021 超神之路，很肝~ 中文详细注释的开源项目 RPC 框架 Dubbo 源码解析 网络应用框架 Netty 源码解析 消息中间件 RocketMQ 源码解析 数据库中间件 Sharding-JDBC 和 MyCAT 源码解析 作业调度中间件 Elastic-Job 源码解析 分布式事务中间件 TCC-Transaction
在上一节, 我们介绍了Linux内核怎么管理系统中的物理内存. 但有时候内核需要分配一些物理内存地址也连续的内存页, 所以Linux使用了 伙伴系统分配算法 来管理系统中的物理内存页.
1、简介： RCU（Read-Copy Update）是数据同步的一种方式，在当前的Linux内核中发挥着重要的作用。 RCU主要针对的数据对象是链表，目的是提高遍历读取数据的效率，为了达到目的使用RCU机制读取数据的时候不对链表进行耗时的加锁操作。这样在同一时间可以有多个线程同时读取该链表，并且允许一个线程对链表进行修改（修改的时候，需要加锁）。 2、应用场景： RCU适用于需要频繁的读取数据，而相应修改数据并不多的情景，例如在文件系统中，经常需要查找定位目录，而对目录的修改相对来说并不多，这就是RCU发
导语 linux 内存是后台开发人员，需要深入了解的计算机资源。合理的使用内存，有助于提升机器的性能和稳定性。本文主要介绍 linux 内存组织结构和页面布局，内存碎片产生原因和优化算法，linux
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
