The Address Space The address space is the abstraction that OS is providing to the running program. The address space of a process contains all of the memory state of the running program. For example, the code of the program, the stack and the heap. In the sight of the program, it loaded into at a particular address and has a potentially very large address space, thus, we say that the OS is virtualizing memory. ...

Linking Linking is the process of collecting and combining various pieces of code and data into a single file that can be loaded (copied) into memory and executed. Linking can be performed at compile time, when the source code is translated into machine code; at load time, when the program is loaded into memory and executed by the loader; and even at run time, by application programs. On modern systems, linking is performed automatically by programs called linkers. ...

Optimization Writing an efficient program requires several type of activities. First, we must select an appropriate set of algorithms and data structures. Second, we must write source code that the compiler can effectively optimize to turn into efficient executable code. A third technique for dealing with especially demanding computations is to divide a task into portions that can be computed in parallel, on some combination of multiple cores and multiple processors. ...

Assembler Computer execute machine code, sequences of bytes encoding the low-level operations that manipulate data manage memory, read and write data on storage devices, and communicate over networks. We will focus on x86-64, the commonest machine language used in processor with laptop and PC, also it’s widely used in supercomputer and lager data center. the x86-64 machine code is much different with the corresponding C code, the processor states below are everywhere: ...

Hardware Organization of A System A typical system has those hadrware below: Buses: Running throughout the system is a collection of electrical conduits called buses that carry bytes of ingormation back and forth betweent the components. Buses are typically designed to transfer fiexed sized chunks of bytes know as words. The number of bytes in a word is a fundamental system parameter that varies across systems. Most have word sizes of 8 bytes (64 bits)today ...

字符串处理算法具有很高的重要性以及应用领域的多样性. 以下讨论默认的是扩展的ASCII字符集(R=256). 字符串排序算法 对于许多排序应用而言, 决定顺序的键都是字符串. 利用字符串的特殊性质来将其排序通常能够获得更高的效率. 键索引计数法 我们首先介绍一种适用于小整数键的简单排序算法. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class KeyIndexedCount { public static void sort(char[] chr, int R) { int[] count = new int[R + 1]; char[] temp = new char[chr.length]; for (char aChr : chr) { count[aChr + 1]++; } for (int i = 0; i < R; i++) { count[i + 1] += count[i]; } for (char aChr : chr) { temp[count[aChr]] = aChr; count[aChr]++; } System.arraycopy(temp, 0, chr, 0, chr.length); } public static void sort(char chr[]) { sort(chr, 256); } } 进行频率统计, 将频率转换为索引, 任意一个键的起始位置总是在比它小的键的频率之和的后面, 用一个辅助数组进行排序, 将排序好的内容回写到原来的数组. 很容易发现, 算法仅仅使用了四个循环, 所以其时间复杂度是线性的(四次循环共访问数组10N+3R次). 上述算法的另一个显而易见的特性是排序的稳定性(因为该算法 按顺序遍历数组来排序). ...

One day ago, I started upgrading my Ubuntu 16.04 to 18.04, after I see the update from website. The most diffrience betwen 16.04 and 18.04 is that the 18.04 use GNOME desktop rather than Unity. I had heard that the GNOME desktop is better than Unity, so I tried 18.04 for the new desktop. Unfortunately, after I upgraded my OS, I found that the GNOME desktop wasjust so uncomfortable. And after one hour I gone back to 16.04:(, and content of this article is about the problems I met while reinstalling the OS. ...

采用哪种数据结构来表示图, 主要考虑以下两个方面: 必须为可能在应用中碰到的各种类型的图预留出足够的空间, 以及 Graph的实例方法一定要高效. 常见的表示方法有以下几种: 邻接矩阵, 对于有N个顶点的图而言, 邻接矩阵需要$ N^2 $的空间. 边的数组, 通过定义边来定义图, 这种方法在寻找相邻的点时需要遍历整个数组. 邻接表数组, 使用一个顶点为索引的列表数组, 其中每个元素都是和该顶点相邻的顶点列表. 这种结构能够满足上述的两个条件. 常见实现的性能比较(V表示结点数, E表示边数): 数据结构 所需空间 添加边 检查顶点是否相邻 遍历所有相邻顶点 边的列表 E 1 E E 邻接矩阵 $ V^2 $ 1 1 V 邻接表 E+V 1 degree(V) degree(V) 非稠密图的标准表示是邻接表, 这种表示具有以下特性: 使用的空间和V+E成正比, 添加一条边所需要的时间为常数, 以及 遍历顶点v的所有相邻顶点所需要的时间和v的度数成正比. 无向图 无向图只定义了顶点以及顶点之间的关系. 深度优先搜索 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public class DepthFirstSearch { private boolean[] marked; private int count; public DepthFirstSearch(Graph G, int s) { marked = new boolean[G.V()]; dfs(G, s); } private void dfs(Graph G, int v) { marked[v] = true; count++; for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w); } } } public boolean marked(int w) { return marked[w]; } public int count() { return count; } } 深度优先搜索能够所有与起点相连的顶点, 且所需时间和所有连通顶点的度数之和成正比. ...