my blogs

Process Resource

每一个进程都消耗系统上的cpu和内存资源,本文将详细介绍这些资源相关的系统调用。并且结合docker,简要介绍docker中对进程资源限制的支持。

红黑树(一) ——原理

在分析内核代码的过程中,发现很多内核子系统都会使用红黑树这个查找结构,本文由浅入深的总结了红黑树这个查找结构。

本文尽可能做到浅显易懂。最后,本文会基于C语言,自己实现一个红黑树,方便大家对其理解。

红黑树介绍

红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和Robert Sedgewick改成一个比较摩登的名字:红黑树

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。那既然已经有二叉查找树,为什么还需要红黑树呢?

了解过二叉查找树的同学应该都知道,随着不断的插入和删除结点,二叉查找树有可能会退化成一个长链。所以就有了AVL树的概念,目的就是在插入和删除结点时,保证查找树的平衡。而红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。

自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。

在centos7中使用高版本的GCC

centos上进行内核开发时,由于一些内核特性依赖于高版本的GCC特性gcc > 5.0),而centos默认的GCC一般为4.8.x

本文记录一种非常简单的在centos上使用高版本的GCC的方法。

Boyer-Moore majority vote algorithm(摩尔投票算法)

Boyer-Moore majority vote algorithm(摩尔投票算法)是一种在线性时间O(n)和空间复杂度的情况下,在一个元素序列中查找包含最多的元素。它是以Robert S.BoyerJ Strother Moore命名的,1981年发明的,是一种典型的流算法(streaming algorithm)。

在它最简单的形式就是,查找最多的元素,也就是在输入中重复出现超过一半以上(n/2)的元素。

tmux快捷键总结

tmux (Terminal Multiplexer的简称), 是一款优秀的终端复用软件,类似 GNU screen,但比screen更出色。

Tmux 用于在一个终端窗口中运行多个终端会话。不仅如此,你还可以通过 Tmux 使终端会话运行于后台或是按需接入、断开会话,这个功能非常实用。

本文总结了tmux常用的一些快捷键。