引言

在8086/8088时代，CPU只有实模式这一种运行模式，本来16位的CPU只有2^16=64KB的寻址能力，但是通过20个地址总线以及”段：偏移”这样的处理，使其达到2^20=1MB的寻址能力.在实模式下，操作系统对于程序能够访问的地址没有任何限制，所以任意程序可以访问甚至修改任意地址的变量，显然这样容易发生严重的错误。

到了80386时代，CPU具有32位寄存器，使其寻址能力达到2^32=4GB。为了更灵活地进行存储管理，并且对程序能够访问的物理地址进行限制，Intel引入了使用至今的保护模式.

前言

这是操作系统系列的第一篇blog，后面会陆续完成操作系统的理论分析，并且提供相应的实现，最终实现一个接近Linux 0.11版本的操作系统。

计算机的启动过程是异常复杂的，要在很短的时间内完成从BIOS自检到加载操作系统内核，进入保护模式的过程。概括起来，计算机的启动过程主要分为以下4个阶段。

1. BIOS

1.1 按下电源

我们按下电源之后，首先是CPU重置。主板加电之后，在电压尚未稳定之前，主板上的北桥控制芯片会向CPU发出重置信号，此时CPU进行初始化。当电压稳定后，控制芯片会撤销Reset信号，CPU便开始了模式化的工作。此时 形成的第一条指令的地址是0xFFFFFFF0,从这里开始，CPU就进入了一个“取指令-翻译指令-执行”的循环了。

Google-Year in Search 2015

Facebook 2015 Year in Review-Story of the Year

从WuMenlei童鞋那里”借”用了几张冬游的图。

希望低调如你不会见怪。

引言

Dijkstra算法是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。Dijkstra算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径

引言

Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效

引言

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法

引言

图是由顶点的非空集合V和边的集合E构成的，可表示为 G=(V,E). 若图的每一条边都是无方向的，则称为无向图，反之为有向图。
图的应用非常广泛，如电子线路分析,工程计划分析，寻找最短路径，甚至估算互联网的直径

引言

霍夫曼编码（英语：Huffman Coding），又译为哈夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）算法。由大卫·霍夫曼在1952年发明。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现概率的方法得到的，出现概率高的字母使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

引言

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