老实说，LeetCode在我眼中的地位并不是很高，今天偶然刷了一下，没想到，写三个不会三个…… 是我变菜了，还是本来就不是那么简单，不过就结论来说，LeetCode对现在的我来说有刷一刷的价值。 这是三道成套的问题。提供题号 141,142,287。 1. 如何判断一个链表中是否存在环。不允许修改链表，不允许申请O(N)及以上的空间。 2. 在第一个问题的基础上，找到环的入口点。限制相同。 3. 给 n+1 个数字，范围是 [1,n] ，找出重复的那一个数字。只允许使用O(1)的空间，不允许修改数组，复杂度低于 $ O(N^2) $ 先剧透一下，第三个问题和第二个问题是一样的……我特么……惊了。 直接说解法，第一个问题。创建两个指针，一个指针走两步，一个指针走一步，…
之前的文章有提到，PC（一般为32位）的启动过程为 BIOS -> MBR -> loader -> kernel。 BIOS在休眠后的最后任务是从硬盘中的第0柱面第0磁头第1扇区中读取MBR，其实就是逻辑0扇区。因为扇区是从1开始计数的。 BIOS所做的内部原理对我来说是从来不去涉及的，所以也就不讨论这个。 从MBR开始才是我们程序猿所能任意写的内容，而MBR同BIOS一样，也需要对下一阶段loader进行过渡。 而一个特别麻烦的地方就是，没有任何库与函数供我们调用……因此我们只能在汇编层面从硬盘读取数据。 老实说，我也不清楚应该从哪开始讲，后续内容都建立在以下基础知识之上： * CPU通过端口访问设备 * 硬盘中的块表示有CHS和LBA方式 * 通道的概念 * 一个PATA线可以挂两个硬盘，一个主盘，一个从盘 * 以前一般主板只支持４个PATA硬盘，所以只需两个通道，这里也只提两个通道 * 硬盘的IO接口称为硬盘控制器 硬盘控制器的主要端口寄存器 Primary 通道Secondary 通道读操作 写操作0x1F00x170DataData…
以前嫌麻烦留着没看，今天补了一下，发现其实只是一些api的调用罢了，这里做个笔记。 对于我们用户来来说，获取物理内存的容量一般用内核调用即可，比如Linux 2.6中使用的detect_memory函数调用。其本质就是使用BIOS的中断0x15检测的。 这里稍微解释一下BIOS(可跳过)，BIOS，基本输入输出系统，PC启动加载的第一个软件，介于操作系统与硬件的抽象层，可用于检测，加载引导程序或者操作系统。显然，PC的启动流程应该是 BIOS -> MBR -> loader -> kernel。 简要说明 开始正文。中断0x15有三个子功能，子功能号放到EAX或者AX中，其简要说明： * EAX = 0xE820 遍历所有内存 * AX = 0xE801 分别检测低 15 MB 和 16 MB ~ 4 GB的内存，最大支持 4 GB。 * AX…
或许是因为这种黑暗的剧情看的少了，在看完恶魔人之后，我基本是呆滞的，我不知道该说些什么，但是我在心里觉得我必须得写下点什么。 悲剧就是把美好的东西撕碎给人看 这句话在这部动漫中得到了很好的体现。 明的父母每年都会在国外给他寄来一双鞋子，明穿着最新的鞋子去见父母，等来的却是恶魔化的父亲，在明不得不杀死自己的父亲的时候，还给了一个鞋子的特写。 害怕的人们拿起武器杀人，不害怕的人手无寸铁，反遭其害。 在了爆出明是恶魔人的时候，他的朋友最后仍然接受了他，他的泪水与执着仍然感动了一部分人。但那有怎么样，然而这些所有象征着善良的人物，在第9集全部死光了。被肢解的尸体被人们高举着，在美树家燃烧的火焰中欢舞。 整部动漫给我印象最深刻的地方，无异于爱与希望的传递。第9集美子为美树殿后希望美树跑起来，传递着生的希望，美树跑向明，想将信任与希望传递给明，但是没跑多久，就被“善良”的人们带着朋友的尸体拦下，被一刀从肩撕到腰。迟来的明抱着美树的头，尝试说服了，最后还是反目成仇。在第10集中，反复出现的接力，在明与了之间的掉棒一开始让我十分困惑，但是和这里联系起来，一切都说的…
终于看懂系列………… 本菜鸡这次主要讲的内容是对三个特权级DPL，CPL，RPL在x86下的理解，如果大佬想看的不是这个就请关上这个标签页。 一些自我理解与背景 负责任地说，操作系统是一个死循环，其间有很多确定和与不确定的中断与调用，最后再被不确定地break掉。在中断与调用中，我们作为用户自然是不可能随意触碰，因为用户不都是满怀好意并且是极其细心的。因此操作系统需要对资源进行保护，而特权级就是保护模式最大的体现。 特权级简介 特权级使用两位4个级别，特权级0通常赋予内核，特权级1,2则是一些系统级服务，常见的就是外设，而我们的应用程序全都在特权级3。 值得注意的是，任何对段寄存器的修改都会触发CPU进行特权级检测，以防任务越权访问。 特权级字段有以下4个： DPL： 段描述符特权级，最好理解的特权级，位于段描述符的高32位，表示的是这个段描述符所表示的段的特权级。 RPL： 请求特权级。位于选择子的最后两位。字面意思，表示请求时的特权级。这里强调，选择子可以保存在任意段寄存器中。 CPL： 当前特权级。当前任务/cpu/系统所处的特权级，永远位于当…
刚看完网易公开课上算法导论中的平衡搜索树，传送门，讲的真的炒鸡好，这里就稍微总结一下。 另一方面，视频是英文板书，在一些地方讲述有点慢，这时候就凸显了文章的优势了。 红黑树性质 红黑树的性质判定红黑树的充要条件，性质见下： 1. 每个节点不是红色就是黑色。 2. 根节点和叶子节点必须为黑色。 3. 每个红色节点的父亲节点必须为黑色节点。 4. 对于每个节点，在它到每一个子树的叶子节点的所有路径中，所经过的黑色节点数量相同。并定义这个数量为黑高(black height)。 补充一条推论，由性质3易得，一颗红黑树的红色节点不会超过总节点数的一半。 而对于第2条性质，我们一般会使最后指向的空节点染色成黑色即可。 红黑树的树高 先说结论，红黑树的树高 height 不会超过 $ 2log_2{(n+1)} $，即 $ height \leq 2 log_2{(n+1)} $。 证明如下： 将所有红色节点合并到其父亲节点，同时使该节点的孩子节点也合并成为其父亲节点的孩子节点。 这时候我们会得到一棵特别的树，…
Phonton OS 专注于容器，是一个非常出色的平台。 —— Jack Wallen 容器在当下的火热，并不是没有原因的。正如之前讨论的，容器可以使您轻松快捷地将新的服务与应用部署到您的网络上，而且并不耗费太多的系统资源。比起专用硬件和虚拟机，容器都是更加划算的，除此之外，他们更容易更新与重用。 更重要的是，容器喜欢 Linux（反之亦然）。不需要太多时间和麻烦，你就可以启动一台 Linux 服务器，运行Docker，然后部署容器。但是，哪种 Linux 发行版最适合部署容器呢？我们的选择很多。你可以使用标准的 Ubuntu 服务器平台（更容易安装 Docker 并部署容器）或者是更轻量级的发行版 —— 专门用于部署容器。 Photon 就是这样的一个发行版。这个特殊的版本是由 VMware 于 2005 年创建的，它包含了 Docker 的守护进程，并可与容器框架（如…
回过头来看以前写的代码居然有点看不懂了，还是应该写一下笔记啊……顺便吧第四章复习一下。 《真象》是指《操作系统真象还原》这是第四章笔记，保护模式入门。 1. 保护模式起于80286,为16位的CPU，兴起于80386，32位的CPU。保护模式下一般都是32位及以上。 2. CPU有三种模式：实模式，虚拟8086模式，保护模式。严格意义上32位CPU无实模式。 3. 制定运行模式编译：使用法 [bits] 16/32 4. 运行模式反转：指运行模式在16位实模式，操作数为32位；或者当前运行模式是32为保护模式，操作数为16位。操作系统兼容两种运行模式，所以支持两种操作，一般临时的反转会在指令前自动加上’66’或者’67’。（不过这实际上是编译器的工作，我们只需要知道就好了 5. 在保护模式下，必须用ecx表示循环次数，其他都兼容。 6. 对于段寄存器的入栈，无论指定在哪种模式下运行，都是按照当前模式的默认操作数大小压入的。而对于通用寄存器和内存，入栈是sp移动大小有操作数决定。…