Linux内核学习笔记(三)Block

块设备(Block Device)简介 块设备是一种以块(block)为单位可以进行随机存取的硬件设备。常见的块设备有硬盘,软盘,闪存等。 块设备的最小寻址单元是扇区(sector),一个扇区是2\^n个字节,512Bytes是最常见的扇区大小。内核的文件系统使……

阅读全文

Linux内核学习笔记(二)内存管理

综述 本文首先介绍和内存管理相关的一些概念如page,zone,然后介绍多种获得内存的方式,最后介绍Linux的slab层(slab分配器)。 页(page) 页是Linux内核进行内存管理的基本单元。MMU和虚拟内存也都使用页作为基本管理单元。不同的架构有不同……

阅读全文

Linux内核学习笔记(一)虚拟文件系统(VFS)

什么是VFS Vritual Filesystem 是给用户空间程序提供统一的文件和文件系统访问接口的内核子系统。借助VFS,即使文件系统的类型不同(比如NTFS和ext3),也可以实现文件系统之间交互(移动、复制文件等), 从用户空间程序的角度来看,VFS提供了一个统一的抽象、接口。这使得用……

阅读全文

VFS中的数据结构(superblock、dentry、inode、file)

VFS简介 VFS的理念是使用统一的数据结构在内核中保存不同类型文件系统的信息(含操作)。 VFS是一个介于用户程序和文件系统实现之间的一个抽象层,VFS既给了不同类型的文件系统支持Linux系统的公共接口,也给用户程序提供了一个统一的调用接口。 VFS背后的核……

阅读全文

《C和C++程序员面试秘笈》中存在的错误

最近在复习C++面试的考点,所以购买了《C和C++程序员面试秘笈》这本书(人民邮电出版社2014.3 ISBN:978-7-115-34113-6)。 书整体上是非常不错的,知识点覆盖比较全面,很符合我的需求。美中不足的是书中的错误有点多。阅读的过程中自己做了……

阅读全文

Linux进程状态码总结

在Linux中执行ps aux命令时,STAT列表示的是进程的状态。最近研究了一下进程状态码,这里做一个简单的总结。 下面是是ps的manual中给出的信息,本文将分别介绍每个状态 PROCESS STATE CODES Here are the different values that the s, stat and state output specifiers (header "STAT" or "S") will display to describe the state of a process: D uninterruptible sleep (usually IO) R running or runnable (on run……

阅读全文

最小生成树(MST):Prim算法与Kruskal算法

什么是最小生成树 最小生成树是一副连通加权无向图中一棵权值最小的生成树[维基百科] 常见的应用例子有铺设道路连接所有城市、铺设管道等,目标都是使总长度最短。 求解最小生成树的基本原理 Prim算法和Kruskal算法是求解最小生成树的两种经典算法,这两个算法都是贪……

阅读全文

二叉树的遍历(先序遍历,中序遍历,后序遍历,层次遍历)

二叉树简介 维基百科对二叉树的定义:二叉树(英语:Binary tree)是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序,不能颠倒。 二叉树的遍历有4种方式,先序遍历,中序遍历,后序……

阅读全文

Trie,单词查找树

Trie简介 Trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情……

阅读全文

九种经典排序算法详解(冒泡排序,插入排序,选择排序,快速排序,归并排序,堆排序,计数排序,桶排序,基数排序)

综述 最近复习了各种排序算法,记录了一下学习总结和心得,希望对大家能有所帮助。本文介绍了冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序、计数排序、桶排序、基数排序9种经典的排序算法。针对每种排序算法分析了算法的主要思路,每个算法都附上了伪代码和C+……

阅读全文