Linux操作系统中通用双向循环链表的实现分析-西华师范大学学报第33卷Vol.33第2期No.2西华师范大学学报(自然科学版)JournalofChinaWestNormalUniversity(NaturalSciences)2022年6月Jun．2022:1673-5073(2022)02-0213-05收稿日期:2022－09－09资助项目:四川省科技厅应用基础项目(010JY0151)，四川省社科联项目“如何保护网络消费者的消费权益”，四川省教育厅教改项目(P09262)，四川省教改重点项目(川教［2022］512号，Z11103)，西华师范大学教改项目(JGXM0945)作者简介:何先波(1971－)，男，四川苍溪人，西华师范大学计算机学院教授，主要从事嵌入式系统与通信网络研究．Linux操作系统中通用双向循环链表的实现分析何先波，李明东，王锦，李宝林，张刚园(西华师范大学计算机学院，四川南充637009)摘要:Linux内核源代码设计体现了大型计算机软件设计成熟的理论和高超的计算机语言编程技巧．本文从源代码级上分析了Linux内核通用双向循环链表的定义和常用操作实现，并基于实例对其应用给以描述．本文内容可作为案例引入C语言程序设计、数据结构等相关课程的教学中．---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---关键词:双向循环链表;Linux内核;开源软件:TP319文献标识码:A1前言Linux是一个支持多用户、多任务、多线程和多CPU的开源操作系统，其内核功能强大、性能稳定并具有丰富的应用软件支持．Linux内核源代码主要由C语言和少量的汇编语言组成，其内核代码设计充分体现了大型计算机软件设计成熟的理论和高超的计算机语言编程技巧．对Linux内核源代码的学习成为程序设计人员，特别是C语言和汇编语言程序设计人员提高编程水平的有效途径．本文从Linux内核(内核版本为2．6．18)源代码中摘取其通用双向循环链表实现部分进行分析，并基于实例对其应用给以描述．双向循环链队列是数据结构的重要内容，而指针操作是C语言程序设计的重点和难点．因此，本文内容可作为案例引入C语言程序设计、数据结构等相关课程的教学中．2Linux通用双向循环链表的定义在Linux操作系统内核实现中，出于时间性能的考虑，使用双向循环链表的数据结构很多，如进程就绪队列、专用内存缓冲管理队列，物理内存页面管理队列和定时器队列等等．这些队列中元素虽然结点类型各异，但都是双向循环链表的应用实例．基于面向对象的思想，Linux内核中实现了一个通用的双向循环链表对象list_head，该对象的定义主要在list．h文件中实现．2．1通用双向循环链表结点类型list_headstructlist_head{structlist_head*next，*prev;};如上面的定义所示，list_head为一结构类型，其中包含两个指针域:next指向本结点在双向循环链表中的后继结点，prev指向前驱结点．在具体使用时，---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---通常使用带头结点(头结点又称为占位结点，其直接后继为第一个有效结点，本文称之为首元结点)的双向循环链表形式．因此，在Linux内核中定义了一个表头初始化的操作INIT_LIST_HEAD和判空操作list_empty:staticinlinevoidINIT_LIST_HEAD(structlist_head*list){list－＞next=list;//后继结点为头结点DOI:10.16246/j.issn.1673-5073.2022.02.016第33卷Vol.33第2期No.2西华师范大学学报(自然科学版)JournalofChinaWestNormalUniversity(NaturalSciences)2022年6月Jun．2022:1673-5073(2022)02-0213-05收稿日期:2022－09－09资助项目:四川省科技厅应用基础项目(010JY0151)，四川省社科联项目“如何保护网络消费者的消费权益”，四川省教育厅教改项目(P09262)，四川省教改重点项目(川教［2022］512号，Z11103)，西华师范大学教改项目(JGXM0945)作者简介:何先波(1971－)，男，四川苍溪人，西华师范大学计算机学院教授，主要从事嵌入式系统与通信网络研究．Linux操作系统中通用双向循环链表的实现分析何先波，李明东，王锦，李宝林，张刚园(西华师范大学计算机学院，四川南充637009)摘要:Linux内核源代码设计体现了大型计算机软件设计成熟的理论和高超的计算机语言编程技巧．本文从源代码级上分析了Linux内核通用双向循环链表的定义和常用操作实现...