免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12345下一页
最近访问板块 发新帖
查看: 134346 | 回复: 41

也谈谈这四年来对内核的研究 [复制链接]

论坛徽章:
0
发表于 2011-06-30 15:29 |显示全部楼层
本人刚从事嵌入式领域的开发,也是刚从校园步入社会,但是对于内核并不陌生,接触内核已经4年多了,对于研究内核来讲,四年的时间其实不算长,也不算短,可是自己对于内核的理解也就局限于一小部分,我相信也很少有人对整个内核的细节都非常熟悉,刚开始接触内核时候觉得很神秘,就像男人第一次接触女人一样,可是时间长了,总会有厌倦的时候,我接触内存管理的时间最长,也是本人自认为研究的比较深的一个点了,因为曾经参与过一个项目,给一个微内核的操作系统设计了并实现了虚拟内存管理,当时为了这个项目把Linux虚拟内存管理的源代码和相关书籍至少看了7-8遍,其实从启动部分开始看起的,惭愧的是现在居然忘了一大半了!当然,这个项目也花了我们不少时间,5个人,2年左右!说实在话,这两年的时间痛苦的滋味只有自己知道,因为,我们发现内存管理是Linux系统最复杂的部分,她和其他的模块的关系非常紧密,到目前为止,还有许多流程我不清楚,在什么情况下会触发。最痛苦的是:遇到问题的时候没有任何人给你任何的答复,尤其是一些流程性的细节,这些流程在什么情况下发生,为什么要考设计这样的流程?因为,这不仅需要你了解程序的设计基本思想,也要你了解硬件的体系结构,比如slab的设计,就是典型的代表!
这两年来:我们不光研究了,Linux内存管理的架构,而且也去研究了其他一些实验性的操作系统架构,典型的的是CMU的mac的虚拟内存管理系统的架构,这样对于我们后来设计自己内存管理的架构起了很大作用,现在回首看看,发现自己对于内存管理的代码基本忘了差不多了,但是架构还是很清晰,依然清晰的记得linux内存管理的几大模块之间的关联!
对于刚准备做内核的兄弟们,结合自身这几年的经历,提出几点经验性的参考:
第一:首先,做Linux内核不能光局限于软件本身,要结合硬件去思考一些问题,比如:流水线,什么是指令冒险,它解决了什么问题?每种CPU在这方面的处理都不一样
第二:要经常去动手验证自己的想法,刚开始,我们花了一年的时间做了理论方面的研究,主要是从代码的角度,架构,模块的设计方面,突然发现,很容易忘记自己看过的东西,但是通过自己动手验证的东西,不太容易忘记
第三:一定要记得静下心来,尤其是遇到复杂的流程处理的时候:因为,对于内核来讲,有可能一个流程的处理,代码量可能达到数千行,甚至万行,而且代码写的都非常精简,非常优化,所以读起来会觉得非常困难
第四:一定要有女朋友!这个大家都懂的,哈哈!
今天在论坛上,看到一个兄弟提的问题,说10个基础而深刻的问题来了解内核,其实我对于这样的兄弟,我身同感受,因为,我当时也是这么想的,可是当你对内核了解越来越多的时候,你会有觉得内核越来越复杂,越来越难懂,和你刚接触内核不同的是,你也许不会那么陌生!这样说的目的并不是夸大内核就是洪水猛兽不可克服,我想说的是,这其实就是我们做研究,搞技术的人所经历的过程,兄弟,我尽量从10个问题的角度回答你的问题,
10个问题来概括内核的基础,那是不可能的,但是了解内核的设计思想,我觉得应该从下面几个点去深刻了解:
1.        硬件体系结构
2.        程序设计的基本思想
3.        程序优化的基本思想
4.        系统的架构思想
个人觉得上面四点在很多情况下都联系在一起的
其实还有很多,我暂时想这么多,还希望大家继续补充,在此,我就全当抛砖引玉了!
那好了,废话少说,我尽量从这几个方面,给出一些所谓的深刻的问题:

评分

参与人数 1可用积分 +6 收起 理由
Godbach + 6 感谢分享

查看全部评分

论坛徽章:
0
发表于 2011-06-30 15:30 |显示全部楼层
本帖最后由 chenrvmldd 于 2011-06-30 15:32 编辑

第一题:
有关slab方面的:
在大学的操作系统课程上:在提到内存管理的时候:会强调两点:解决好外部碎片和内部碎片!
1.        slab是为了解决内部碎片提出的,还是外部碎片?
2.        Slab算法的核心思想是什么?请简述
3.        在什么情况下,会用到slab,请你举几个具体的例子!
4.        Slab中算法中提到了着色,请问着色问题,主要是解决什么的?
5.        你觉得slab算法有什么缺点,如果让你来设计,你怎么去改进它的缺点?
第一个小问,是考察slab提出的背景是什么,基于一个什么样的前提提出的,
第二个小问,是考察对slab算法思想,整个算法架构的理解
第三个小问,是考察slab在系统中实际中的应用,提供给其他模块的接口
第四个小问,考察了slab算法中的一个技术细节,这个细节背后的知识
第五个小问,这个难度稍微有点大
关于答案,没有具体的,希望大家积极响应,到时候我会按照我的理解,将我自己理解的东西贴出,今天先搞一个问题,明天把第二个问题贴出来!

论坛徽章:
0
发表于 2011-06-30 16:45 |显示全部楼层
回复 6# 瀚海书香


第四个回答,太泛了,能不能详细一点,再深入一点,结合cache的结构来解答了?

论坛徽章:
0
发表于 2011-06-30 16:53 |显示全部楼层
回复 11# T-Bagwell


差不多了,如果你看过slub,那就知道slab的缺点,可是,大家有没有其他的看法了?

论坛徽章:
0
发表于 2011-06-30 17:01 |显示全部楼层
回复 13# 瀚海书香


这是书上的解释,书上的解释也不够详细,希望兄弟你能结合计算机组成原理中关于cache的结构来分析slab着色的问题

论坛徽章:
0
发表于 2011-06-30 17:33 |显示全部楼层
回复 15# 瀚海书香

其实这个也不难理解,给点提示,兄弟你可以结合cache和主存储块之间的关系,其实着色在有的结构下是不起作用的,你沿着这个思路去思考,应该就不难了啊

论坛徽章:
0
发表于 2011-07-01 08:45 |显示全部楼层
早上刚到公司,在我理解的答案之前,首先回答几个兄弟的问题:
T-BAG兄弟和smalloc觉得内存管理复杂,这个我必须承认,在两年的时间里,我几乎天天在搞内存,可是里面还是有些东西还并不是特别的确定,还有smalloc兄弟说的懂内存管理的没几个人,这个“懂”就高深了呀,呵呵。其实对于内核来讲,我前面说过了,她不是洪水猛兽,你可以把她看成你未来的女朋友,我相信对于爷们来讲,想把自己心仪的女人变成自己的女朋友的那钟欲望和动力是无穷的,突然想到freud曾经说过,一切社会进步的根源就是Libido!看来这句话还真有道理啊!
再回答一下瀚海书香兄弟的问题,对于我们搞内核的人来讲:如果我作为面试官,我觉得对于硬件你必须要懂,我也必须要问,如果不懂,不可能设计出高效操作系统出来,就比如:Linux在设计进程却换这个问题的时候,曾经用了两种方法:其实也就10几行代码左右的样子,从这点可以看出内核设计之复杂,和之谨慎,对于进程切换,我会作为一个单独的问题在以后的问题中列出来!
回答xiaobo620_2011,关于动手,怎么去动手,这个问题其实只要你动手编过简单的代码,就应该知道如何去动手了,通过做实验去验证你自己一些简单的想法,比如:在我的第一个问题中还有,没有列出来的问题,slab既然作为碎片处理的一个算法,那么它提供的最大的块应该是多大,你可以简单的去验证一下啊!其实太多太多了。。。。
好了,我想我尽量找出10个基础而深刻的问题,可是我昨晚想了很久,发现确实太难了,如果10个基础而深刻的问题能概括Linux内核,那么她也不能成为Linux了,我想,估计Linus本人看到那位兄弟提的10个关于linux内核的问题,一定会“内牛满面”,这可是人家花了多少年,多少心血搞的东东,你10个问题来概括,呵呵!

评分

参与人数 1可用积分 +6 收起 理由
Godbach + 6 感谢分享

查看全部评分

论坛徽章:
0
发表于 2011-07-01 09:14 |显示全部楼层
好了,下面我来公布一下我的理解:
第一个小问:slab是为了解决内部碎片提出的,还是外部碎片?
这个显然是内部碎片,ULK这本书上明确的提到了,可是解决内部碎片的方法有很多种,为什么会用slab这种算法了?这个在第二个小问会提到,其实我看到的任何书上都没有提到slab算法背后的理论支撑,据我的了解:windows,solaris都使用了slab算法,如果我没有记错的话,最早使用的应该是solaris首先使用的!
第二个小问:Slab算法的核心思想是什么?请简述
瀚海书香兄弟的回答是“ slab的核心思想是以对象的观点来管理内存”,我觉得这个回答非常的好,可是我不知道瀚海书香兄弟能不能理解“对象”这个观点了?那么为什么“对象”这个方法会高效了?这个我还希望大家继续去思考,那好,我来归纳一下这个问题:其实是在网上摘抄的别人的一个概括,我觉得概括的很全面,所以直接拿过来用了!
Linux 内核在运行过程中,常常会需要经常使用一些内核的数据结构(对象)。例如,当进程的某个线程第一次打开一个文件的时候,内核需要为该文件分配一个称为 file 的数据结构;当该文件被最终关闭的时候,内核必须释放此文件所关联的 file 数据结构。这些小块存储空间并不只在某个内核函数的内部使用,否则就可以使用当前线程的内核栈空间。同时,这些小块存储空间又是动态变化的,不可能像物理内存页面管理使用的 page 结构那样,有多大内存就有多少个 page 结构,形成一个静态长度的队列。而且由于内核无法预测运行中各种不同的内核对象对缓冲区的需求,因此不适合为每一种可能用到的对象建立一个“缓冲池”,因为那样的话很可能出现有些缓冲池已经耗尽而有些缓冲池中却又大量空闲缓冲区的现象。因此,内核只能采取更全局性的方法。
我们可以看出,内核对象的管理与用户进程中的堆管理比较相似,核心问题均是:如何高效地管理内存空间,使得可以快速地进行对象的分配和回收并减少内存碎片。但是内核不能简单地采用用户进程的基于堆的内存分配算法,这是因为内核对其对象的使用具有以下特殊性:
1.        内核使用的对象种类繁多,应该采用一种统一的高效管理方法。
2.        内核对某些对象(如 task_struct)的使用是非常频繁的,所以用户进程堆管理常用的基于搜索的分配算法比如First-Fit(在堆中搜索到的第一个满足请求的内存块)和 Best-Fit(使用堆中满足请求的最合适的内存块)并不直接适用,而应该采用某种缓冲区的机制。
3.        内核对象中相当一部分成员需要某些特殊的初始化(例如队列头部)而并非简单地清成全 0。如果能充分重用已被释放的对象使得下次分配时无需初始化,那么可以提高内核的运行效率。
4.        分配器对内核对象缓冲区的组织和管理必须充分考虑对硬件高速缓存的影响。
5.        随着共享内存的多处理器系统的普及,多处理器同时分配某种类型对象的现象时常发生,因此分配器应该尽量避免处理器间同步的开销,应采用某种 Lock-Free 的算法。
第三个问题:在什么情况下,会用到slab,请你举几个具体的例子!
其实这个问题,前面已经有兄弟回答了,我想问大家的是:既然你知道在什么情况下用slab,那么你用过slab提供的接口吗?你对这些接口的用法熟悉吗?
关于slab提供的接口,大家可以参考ULK这本书上提供的,其实我想说的,在我们驱动程序设计和内核模块设计的过程中,经常会用的kmalloc,可是对于kmalloc这个接口,大家
有没有测试过,如果你分配一些数据,slab是如何来管理你请求的内存了?
第四个小问:Slab中算法中提到了着色,请问着色问题,主要是解决什么的?
前面也有几个兄弟回答了这个问题,但是我感觉和书上阐述的差不多,或者换一个角度去阐述,个人感觉不是很深刻!
SLAB的着色问题,一般书上讲的都比较简单,就是说解决cache缓存行冲突的问题,那么为什么冲突了?着色有是如何解决冲突问题的了?,这就要看一下我们cache与主存块的工作结构!
、1.        全相联
任一主存块能映射到Cache中任意行(主存块的容量等于Cache行的容量)

优点:灵活,不易产生冲突;
缺点:比较电路难于实现,且效率低,速度慢。
2.        直接映射
某一主存块只能能映射到Cache的特定行


优点:硬件简单,成本低;
缺点:容易产生冲突,易"颠簸",不能有效利用Cache空间
3.组相联

组间直接映射,组内全相联映射。
• 优点:结合上面两种的优点。
① 因为组内行数较少,比较器容易实现;
② 组内又有灵活性,冲突大大减少
看完这三种结构,下面就要阐述为什么会冲突,细心的朋友肯定会发现:在直接映射和组相联映射的工作结构下会产生冲突,我们的SLAB就是为了解决这样的冲突而提出来的,所以说SLAB着色问题对于全相联的工作结构的效率没有什么帮助,这一点大家要明白,那么冲突的原因是什么了?虽然从直接映射的那张图可以看出来,这里还是要举一个具体的例子来阐述一下,让我们看一下直接映射的图:
假设有两个一样的对象A1,A2,他们大小一样假设A1在主存第0区的偏移为1,也就是说在第个区的第一个块,A2在第1个区中,偏移也为1,这个时候假设A1在cache中,这个时候需要访问A2,那么A2必须要被掉入到CACHE的A1此时所在的位置,A1被调入到主存中,如果A2访问结束之后又要访问A1,那么A2又要被换出,极端情况下cache的工作效率就会很低。相信说到这,大家应该明白了冲突的原因了吧。
其实知道冲突的原因之后,我们要解决冲突就很简单了,我们首先想到的就是不让相同的对象在不同的区中有相同的偏移,其实着色就是的核心思想就是让相同的对象在不同区中的偏移不一样,所以在Linux的着色的实现的思想就是:给在不同区中的相同对象进行着色,着色的本质其实就是加填充一个偏移(一个缓存行),那么这就势必带来一个问题,浪费了一定的存储空间!试想一下如果同一类对象很多很多的情况下,那是不是有巨大的内存浪费了,这个问题在下一个问题中会阐述出来!

第五个小问:你觉得slab算法有什么缺点,如果让你来设计,你怎么去改进它的缺点?
如果看过slub算法的人会知道,slub就是对slab的改进,关于slub:
SLAB 分配器多年以来一直位于 Linux 内核的内存管理部分的核心地带,内核黑客们一般不愿意主动去更改它的代码,因为它实在是非常复杂,而且在大多数情况下,它的工作完成的相当不错。但是,随着大规模多处理器系统和 NUMA系统的广泛应用,SLAB 分配器逐渐暴露出自身的严重不足:
1.        较多复杂的队列管理。在 SLAB 分配器中存在众多的队列,例如针对处理器的本地对象缓存队列,slab 中空闲对象队列,每个 slab 处于一个特定状态的队列中,甚至缓冲区控制结构也处于一个队列之中。有效地管理这些不同的队列是一件费力且复杂的工作。
2.        slab 管理数据和队列的存储开销比较大。每个 slab 需要一个 struct slab 数据结构和一个管理所有空闲对象的 kmem_bufctl_t(4 字节的无符号整数)的数组。当对象体积较少时,kmem_bufctl_t 数组将造成较大的开销(比如对象大小为32字节时,将浪费 1/8 的空间)。为了使得对象在硬件高速缓存中对齐和使用着色策略,还必须浪费额外的内存。同时,缓冲区针对节点和处理器的队列也会浪费不少内存。测试表明在一个 1000 节点/处理器的大规模 NUMA 系统中,数 GB 内存被用来维护队列和对象的引用。
3.        缓冲区内存回收比较复杂。
4.        对 NUMA 的支持非常复杂。SLAB 对 NUMA 的支持基于物理页框分配器,无法细粒度地使用对象,因此不能保证处理器级缓存的对象来自同一节点。
5.        冗余的 Partial 队列。SLAB 分配器针对每个节点都有一个 Partial 队列,随着时间流逝,将有大量的 Partial slab 产生,不利于内存的合理使用。
6.        性能调优比较困难。针对每个 slab 可以调整的参数比较复杂,而且分配处理器本地缓存时,不得不使用自旋锁。
7.        调试功能比较难于使用。
为了解决以上 SLAB 分配器的不足之处,内核开发人员 Christoph Lameter 在 Linux 内核 2.6.22 版本中引入一种新的解决方案:SLUB 分配器。SLUB 分配器特点是简化设计理念,同时保留 SLAB 分配器的基本思想:每个缓冲区由多个小的 slab 组成,每个 slab 包含固定数目的对象。SLUB 分配器简化了kmem_cache,slab 等相关的管理数据结构,摒弃了SLAB 分配器中众多的队列概念,并针对多处理器、NUMA 系统进行优化,从而提高了性能和可扩展性并降低了内存的浪费。为了保证内核其它模块能够无缝迁移到 SLUB 分配器,SLUB 还保留了原有 SLAB 分配器所有的接口 API 函数。
上面的回答算的上是官方的回答了,在这里,其实slub本身,还是有继承了很多slab的问题,遗憾的是,我没有看到有兄弟提出这样的问题,其实slub本身还是有缺点的!
总结:slab算法很复杂,很强大!
参考:
深入理解Linux内核
Linux内核源码分析
计算机组成原理
有一篇关于slab算法的提出的论文,大家可以去google一下,这篇文章是当年大概1970-1980之间TOP1的文章
http://www.ibm.com/developerworks/cn/linux/l-cn-slub/
全相连.jpg
直接映射.jpg
组相连.jpg

评分

参与人数 1可用积分 +10 收起 理由
Godbach + 10 感谢分享

查看全部评分

论坛徽章:
0
发表于 2011-07-01 11:05 |显示全部楼层
回复 27# VIP_fuck

其实大牛谈不上,只是在内存管理比一般人下的功夫要多一点,自然理解也就比别人深刻一点

论坛徽章:
0
发表于 2011-07-01 11:06 |显示全部楼层
回复 28# asuka2001


其实,我希望通过我自己的理解,可以让更多的兄弟提出自己的理解,然后,去引导更多的人去思考,去思考多的问题
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP