Range Minimum/Maximum Query (RMQ)

RMQ对于给定长度n的数列A，询问区间数列A在（i,j）内最大最小值。

解决方法：（A长度为n，q次查询）

1. 搜索 复杂度：O(n) - O(qn)
2. 线段树 预处理：O(n) - 查询：O(qlogn)
3. Sparse table(ST) 预处理：O(nlogn) - 查询：O(q)

ST算法

ST本质上是动态规划，适用的情况是数据不更新，因为更新需要重新建表，这种情况下就选择线段树啦。

复杂度：建表O(nlogn)，查询O(1)

预处理

f[i][j]保存每一块[i, i + $2^j$ - 1]的最大值，起点i、终点i + $2^j$ - 1共$2^j$个数

[i, i + $2^j$ - 1]可以拆分成等长的2块，[i, i + $2^{j-1}$ - 1]和[i + $2^{j-1}$, i + $2^j$ - 1]，递归结构显现，可以用DP啦

f[i][j]=max(f[i][j - 1], f[i + (1<<(j-1))][j - 1])

1
2
3
4
5
6

// j上限设为20
for (int j = 1; j < 20; j++) {
    for (int i = 0; i + (1<<(j-1)) <= size; i++) {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i + (1<<(j-1))][j - 1]);
    }
}

dp[i][0]记录的是原来数组的值，i从1开始是为了query时候方便，不用再改写成从0开始的index

Query

[l, r]区间可以按照[i, i + $2^j$ - 1]的模式划分成2块，[l, l + $2^k$ - 1]和[r - $2^k$ + 1, r]，

其中k = $\lfloor log_2(r - l + 1)\rfloor$ 向下取整

2段小区间长度相等，记为len，证明小区间有重叠：

$\lfloor log_2(len)\rfloor$ >= $log_2(len)$ - 1，所以$2^{\lfloor log_2(len)\rfloor}$ >= len/2, 这样2段小区间便有了重叠，保证query操作的正确性

1
2
3
4

public int query(int l, int r) {
    int k = (int) (Math.log(r - l + 1) / Math.log(2));
    return Math.max(dp[l][k], dp[r - (1<<k) + 1][k]);
}

Git Submodule

有可能会将代码根据功能拆解成不同的子模块。主项目对子模块有依赖关系，却又并不关心子模块的内部开发流程细节。

这种情况下，通常不会把所有源码都放在同一个 Git 仓库中。

有一种比较简单的方式，是在当前工作目录下，将子模块文件夹加入到 .gitignore 文件内容中，这样主项目就能够无视子项目的存在。这样做有一个弊端就是，使用主项目的人需要有一个先验知识：需要在当前目录下放置一份某版本的子模块代码。

还有另外一种方式可供借鉴，可以使用 Git 的 submodule 功能

1. 创建submodule

git submodule add <submodule_url> <directory>在项目中创建一个子模块

例如：在project目录下git submodule add github.com/username/projectA moduleA

此时主项目仓库会多出两个文件：.gitmodules和moduleA, .gitmodules包含submodule的主要信息

1
2
3

[submodule "ModuleA"]
path=moduleA
url=github.com/username/projectA

moduleA文件记录子模块的commit id。父项目并不会记录submodule的文件变动，只是按照commit id指定子模块的git HEAD。所以.gitmodules和moduleA都是需要提交到父项目的远程仓库中去的

1
2

git add .gitmodules moduleA
git commit -m 'add submodule projectA'

2. 克隆带子模块的repo

方法一：先clone父项目，再初始化submodule，最后更新submodule。初始化只做一次，之后每次只需要update。默认submodule不在任何分支上，它指向父项目保存的submodule commit id

1
2
3
4

git clone github.com/username/project && cd project
git submodule init
git submodule update
cd ..

方法二：带上参数--recursive-submodules

git clone github.com/username/project --recursive-submodules

3. 修改submodule

修改子模块代码只对子模块的版本库产生影响，对父项目的版本库不会产生任何影响。在子项目中修改代码并提交，之后在父项目中便可以看到子项目的新提交，正常add，commit就好。如果父项目需要用到最新版本的子模块，我们需要更新.gitmodules中submodule commit id。

4. 更新submodule

子模块的默认分支不是master

方法一：先pull父项目，然后执行git submodule update，注意moduleA的分支

1
2
3

cd project
git pull
git submodule update

方法二：先进入子模块，然后切换到需要的分支，在子模块中pull

1
2
3
4

cd project/moduleA
git checkout <branch-name>
cd ..
git submodule foreach git pull

5. 删除submodule

先unregister需要删除的子模块，之后可以git-rm移除子模块代码文件

1
2
3
4

cd project
git submodule deinit <submodule-name>
git rm <submodule-name>
git commit -m 'delete submodule <submodule-name>'

--force选项会强制删除子模块，即便子模块已经有本地修改

.git/config和.gitmodules中相应内容自动被删除。在之后的git submodule和git submodule foreach都会跳过unregister的子模块

Reference

Git Submodule管理项目子模块

Git中submodule的使用

Git Submodule使用完整教程

Josephus Problem

问题描述

Josephus problem (or Josephus permutation), 简单说，N个人围成一圈，从某一人（比如第k个）开始报数，报到m的人退出，如此循环，直到最后一个人

People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.

解法1: circular linked list

循环链表解法很直接，复杂度O(n)

每个Node就是问题中的一个人，数到谁就删除相应的Node，最后只剩一个Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Node {
    int data;
    Node next;
    public Node(int data){
        this.data = data;
    }
}

public Node createCirLinkedList(int N) {
     Node head = new Node(1);
     Node next = head;
     for (int i = 2; i <= N; i++){
         Node tmp = new Node(i);
         next.next = tmp;
         next = next.next;
      }
      next.next = head;
      return head;
}

public int solve(int N, int m) {
     /* create circurlar linked list */
     Node head = createCirLinkedList(N);
     /* remove node recursively */ 
     while (head != head.next){
         /* move head point to the previous node before to-be-deleted node */
         /* head.next is the node to be deleted */
         for (int i = 1; i < m - 1; i++){
             head = head.next;
         }
         System.out.print(head.next.data+"->");
         /* remove the m-th node */
         head.next = head.next.next;
         head = head.next;
         }
         System.out.print("Done!\n");
         return head.data;
}

解法2: 数学方法递推公式

求Josephus的递推就比较有意思啦，正向不行，得反着来。所有人围成一个圆，整个序列从任意一点开始都可，0点（index是0）是谁都一样可以数下去。那么每轮都把上一次被删除的那个人的下一个位置作为新的0点，开始新一轮数数。这样子，每一轮都是重复一样的模式在数数，recursion来了。

$J(n)$表示n个人玩最后胜利者的编号（编号从0开始），按照这样设定初始条件$J(1) = 0$

过程：

$J(n)$:

编号m % ( n - 1 )出局，剩下的人组成一个新的环，从k = m % n开始

0, 1, 2, 3, 4, …, k-2, k-1, k, k+1, k+2, k+3, k+4, …, n-1

$J(n-1)$:

n-k, n-k+1, n-k+2,…, n-2, 0, 1, 2, 3, 4, …, n-k-1,

编号做一下转换：

        J(n)编号 --> J(n-1)编号

               k --> 0

             k+1 --> 1

             k+2 --> 2

                 ...

             k-2 --> n-2

             k-1 --> n-1

n个人玩J(n)时的序号转换成n-1个人玩J(n-1)的序号，这样之，当我们知道子问题J(n-1）的胜利者编号就可以转换成J(n)时的编号，J(1)->J(2)->…->J(n-1)->J(n), 递推公式就来了

1
2
3

   J(n) = (J(n-1) + k) % n, k = m % n
=> J(n) = (J(n-1) + m % n) % n
        = (J(n-1) + m) % n

递推公式:
J(1) = 0
J(n) = (J(n-1) + m) % n

recursive

1
2
3
4
5
6
7
8
9
10

public int solve(int N, int m) {
     /* index begin at 0 */
     if (N == 1) {
         return 0;
     }
     return (recursiveSolve(N - 1, m) + m) % N;
}

/* when index begins at 1 */
int res = solve(N, m) + 1;

iterative

1
2
3
4
5
6
7
8
9
10

public int solve(int N, int m) {
     /* index begin at 0 */
     int res = 0;
     for (int i = 2; i <= N; i++){
         res = (res + m) % i;
     }
     /* when index begin at 1 */
     res = res + 1;
     return res;
}

Reference

Josephus problem wikipedia

Josephus Problem的详细算法

Java I/O

I/O流 概念： 流数据从一端传到另一端

Java I/O流分为三大类：

• 按照读写单元（bit or byte）：字节流，字符流
• 按照流的方向：输入流，输出流
• 按照功能分：节点流，处理流

字节流和字符流：

• 当我们读取文件然后再写入其他文件时，不用过多的关注读取的内容时，通常使用的是字节流，因为这相当于是在处理二进制文件。读取数据效率高，并且保持数据的完整性；当我们读取文件的内容，并对文件的内容进行加工时，通常使用字符流。

节点流和处理流：

• 节点流：即从特定的数据源读取写入数据
• 处理流：在已经存在的节点流或者处理流上，进行装饰提供更强大的读写功能
  1. 缓冲流（Buffered）带缓冲区，在节点流上添加缓冲区（例如：new BufferedInputStream(new FileInputStream())），这样避免读取文件时，大量进行硬盘的读写，提高读写效率
  2. 转换流（StreamReader）即字节流和字符流的相互转换，比如：在进行读写字节流时，想调用读取字符流的函数，就可以通过转换流。InputStreamReader in = new InputStreamReader(new InputStream()) 注意只能字节流=>字符流
  3. 数据流（Data）当读取写入具体的数值数据时，DataInputStream可以让你从InputStream读取Java基本类型来代替原始字节。如果读取的数据是由大于一个字节的Java基本类型构成，如int，long，float，double等，那么用DataInputStream是很方便的。读取的时候记住先读先写的原则，顺序不能乱，因为Java基本类型都是大于一个字节的，顺序不对，读取出来会出现乱码。所以在用DataInputStream的时候要么为文件中的数据采用固定格式，要么将额外信息保存到文件中，以便解析的时候确定数据位置和类型使用。

Java IO类结构

InputStream, OutputSteam, Reader, Writer都是抽象类

贴张图：

References

Java流机制详解
Java IO流学习总结一：输入输出流

Java泛型 类型擦除

正确理解泛型概念的首要前提是理解类型擦除(type erasure)。Java中的泛型基本上都是在编译器这个层次来实现的。在生成的Java字节代码中是不包含泛型中的类型信息的。使用泛型的时候加上的类型参数，会被编译器在编译的时候去掉。这个过程就称为类型擦除。如在代码中定义的List<Object>和List<String>等类型，在编译之后都会变成List。JVM看到的只是List，而由泛型附加的类型信息对JVM来说是不可见的。Java编译器会在编译时尽可能的发现可能出错的地方，但是仍然无法避免在运行时刻出现类型转换异常的情况。

Java泛型特性

• 泛型类并没有自己独有的Class类对象。比如并不存在List<String>.class或是List<Integer>.class，而只有List.class。

• 静态变量是被泛型类的所有实例所共享的。对于声明为MyClass<T>的类，访问其中的静态变量的方法仍然是 MyClass.myStaticVar。不管是通过new MyClass<String>还是new MyClass<Integer>创建的对象，都是共享一个静态变量。

• 泛型的类型参数不能用在Java异常处理的catch语句中。因为异常处理是由JVM在运行时刻来进行的。由于类型信息被擦除，JVM是无法区分两个异常类型MyException<String>和MyException<Integer>的。对于JVM来说，它们都是 MyException类型的。也就无法执行与异常对应的catch语句。

  不允许创建参数化类型数组

  1	Pair<String>[] table = new Pair<String>[10]; // Error

  擦除之后，table的类型是Pair[]。可以把它转换为Object[]:Object[] objarray = table;

  数组会记住它的元素类型，如果试图存储其他类型的元素，就会抛出一个ArrayStoreException异常：objarray[0] = "hello"; // Error--component tye is Pair

  不过对于泛型类型， 擦除会使这种机制无效。

  objarray[0] = new Pair<Employee>()能够通过数组存储检查，不过仍会导致一个类型错误。

  处于安全考虑呢，Java不允许创建参数化类型的数组。

Java泛型与C++模板 差异之处

“泛型编程”这个概念最早就是来源于C++当初设计STL时所引入的模板（Template），而为什么要引入模板呢，因为STL要完成这样一个目标：设计一套通用的，不依赖类型的，高效的的算法（例如std::sort）和数据结构（例如std::list）。关于通用性，运行时多态（Polymorphism）可以做到（例如很多高级语言的继承（Inheritance）机制，接口（Interface）机制），但是C++作为一门相对底层的语言，对运行效率的要求是很严格的，而运行时多态会影响效率（例如成员函数只有在运行时才知道调用哪个），所以设计STL的人就创造了一种编译时多态技术，即模板。

那什么又是编译时多态呢，简单点说就是让编译器帮我确定类型，我写程序时只要标记下这里我要用“某种类型”的对象，至于具体是什么类型我不关心，你编译器帮我确定，编译完成后在运行时绝对是类型确定的，这样就大大提高了运行效率，反之对编译就增加了很多工作，而且生成的目标代码也会大大增加。所以对C++来说，所谓“泛型（Generics）”，并不是说编译器不知道类型，而是针对程序员来说的，这也正是通用性的体现。

在 C++ 模板中，编译器使用提供的类型参数来扩充模板，因此，为 List<A> 生成的 C++ 代码不同于为 List<B> 生成的代码，List<A> 和 List<B> 实际上是两个不同的类。而 Java 中的泛型则以不同的方式实现，编译器仅仅对这些类型参数进行擦除和替换。类型 ArrayList<Integer> 和 ArrayList<String> 的对象共享相同的类，并且只存在一个 ArrayList 类

References:

1. Java核心技术
2. Java泛型：类型檫除、模板和泛型传递

字符编码

起源

计算机不能直接识别字符（文本的最小组成单位）。
抽象字符和数字成对编码用于在计算机系统中表示的信息单位。虽然字符本身是抽象的，但它一旦存在与计算机系统中，它就对应了某种特定字符编码方式。计算机可以识别二进制数，于是采用一个二进制数来指代一个字符。

编码与解码

• 编码过程：字符转换成二进制刘表示的过程
• 解码过程： 二进制刘转换成字符的过程
• 编码规则：编码和解码过程中遵循的规则，例如GBK编码，UTF-8编码

区分几个基本概念：

字符是各种文字和符号的总称，包括各个国家文字、标点符号、图形符号、数字等。字符集是多个字符的集合，字符集种类较多，每个字符集包含的字符个数不同，常见字符集有：ASCII字符集、ISO 8859字符集、GB2312字符集、BIG5字符集、GB18030字符集、Unicode字符集等。计算机要准确的处理各种字符集文字，需要进行字符编码，以便计算机能够识别和存储各种文字。

编码(encoding)和字符集不同。字符集只是字符的集合，不一定适合作网络传送、处理，有时须经编码(encode)后才能应用。如Unicode可依不同需要以UTF-8、UTF-16、UTF-32等方式编码。字符编码就是以二进制的数字来对应字符集的字符。使用哪些字符。也就是说哪些汉字，字母和符号会被收入标准中。所包含“字符”的集合就叫做“字符集”。规定每个“字符”分别用一个字节还是多个字节存储，用哪些字节来存储，这个规定就叫做“编码”。

各个国家和地区在制定编码标准的时候，“字符的集合”和“编码”一般都是同时制定的。因此，平常我们所说的“字符集”，比如：GB2312, GBK, JIS 等，除了有“字符的集合”这层含义外，同时也包含了“编码”的含义。

注意：Unicode字符集有多种编码方式，如UTF-8、UTF-16等；ASCII只有一种；大多数MBCS（包括GB2312）也只有一种。

字符编码的历史

ASCII

美国信息交换标准代码，最早的通用编码方案。开始时，只用7个比特位就表示完了所用拉丁文子没有和一些符号，共128个。后来发现不够用，又启用了第8位，刚好一个字节的长度，共256个字符。

但是，不同的公司/组织吧这拓展出来的128个码位指派给了不同的字符，文档交流就困难了。于是ANSI这个组织站出来了，制定了ANSI标准。

而且人们也发现，ASCII这种单字节（因为它占8个比特位）编码满足不了更多的字符需求，那必须得用多个字节编码。多字节字符集（MBCS）概念就诞生了。

ANSI

美国国家标准协会认可的标准。注意，它是一种标准，而不是某种具体编码，可以看做是编码的一种分类。ANSI的标准就是，ASCII码占用的码位及其所指代的字符不许改变，剩下的自己扩展。

中国人在这个规定上有自己的扩展（如GBK），英国人也有自己的扩展（如ISO-8859-1,即latin-1）。所以ISO-8859-1和GBK都可以称之为ANSI编码，因为它们符合ANSI规定。以Windows系统为例，中文系统中所指的ANSI编码就是GBK，英文系统中的ANSI编码就是ISO-8859-1。

MBCS

多字节字符集(Multi-Byte Character Set)，采用不定长度可以是一个字节，也可以是两个字节，也可以是三个字节来进行编码。大多数情况下2个字节就够用了，汉字就分配两个字节，称之为DBCS（Double-Byte Chactacter Set）。

在Linux系统中看得到MBCS说法，在Windows中呢？其实就是ANSI，ANSI只规定了第一个字节的位置是ASCII，超出这个范围的，肯定也是多字节的了。

Unicode字符集

通过以上的介绍知道，各种解决方案都是各自为政，解决不了 “同一个系统中同时显示全宇宙的所有字符” 这个问题。

于是就有两个组织，他们开始着手做这件事情，UCS和Unicode诞生了。

通用字符集（UCS，Universal Character Set）是由国际标准化组织（ISO）制定的 ISO 10646标准所定义的字符集。通常也译为通用多八位编码字符集。统一码（Unicode）是由统一码联盟指定的。

后来发现，一山不容二虎，世界人民不需要两个目的相同但是具体实现却有差异的编码方案。UCS和Unicode握手言和，从 Unicode 2.0 起，采用了和ISO 10646-1的编码方案，它们在相同的码位上都对应同样的字符。尽管这两个组织目前还在相互独立的在发布字符编码标准。

可能是Unicode名字好记，所以采用更为广泛。关于UCS-2，UCS-4这些概念不再赘述。

Unicode，UTF-8，UTF-16它们是什么关系

UTF-8（Unicode Transformation Format）即Unicode转换格式，8的意思是使用8比特为单位来进行编码。码位小于128时，就是对应的字节值；大于等于128时，就会转换成2、3、4字节的序列。每个字节的序列值介于128~255。

GBK，GB2312，Latin-1，Big-5，ASCII等，它们的字符集和具体编码实现方式绑定（如GBK字符集就采用GBK编码方式），即字符和存储在介质上的二进制流一一对应。缺陷很明显，字符集扩展性差。Unicode考虑了这个问题，所以它的编码与编码的实现方式没有绑定。而是有多种实现方式，如UTF-8，UTF-16，UTF-32。

例如字符‘A’在Unicode中的编码是65，但存储在介质上时，二进制流的十六进制表示采用UTF-8时是0x41，而UTF-16大端模式是0x00 0x41。

Reference:

深度剖析java编码

字符编码详解——彻底理解掌握编码知识，“乱码”不复存在

Linux内核空间，用户空间

用户界面是操作系统的外在表象，内核才是操作系统的内在核心。系统其他部分必须依靠内核这部分软件提供的服务，像管理硬件设备、分配系统资源等。内核有时候被称作是管理者或者是操作系统核心。通常一个内核由负责响应中断的中断服务程序、负责管理多个进程从而分享处理器时间的调度程序，负责管理进程地址空间的内存管理程序和网络、进程间通信等系统服务程序共同组成。对于提供保护机制的现代系统来说，内核独立于普通应用程序，他一般处于系统态，拥有受保护的内存空间和访问硬件设备的所有权限。这种系统态和被保护起来的内存空间，统称为内核空间。相对的，应用程序在用户空间执行。它们只能看到允许它们使用的部分系统资源，并且只使用某些特定的系统功能，不能直接访问硬件，也不能访问内核划给别人的内存范围，还有其他一些使用限制。当内核运行的时候，系统以内核态进入内核空间执行。而执行一个普通用户程序时，系统将以用户态进入用户空间执行。

1. 用户空间、内核空间

   现代操作系统都是采用虚拟存储器，对于32位操作系统，它的逻辑内存（虚拟存储空间）为4G（2^32）。为了保护内核，将其与用户应用程序代码隔离开来，操作系统将逻辑内存划分为两部分，一部分为内核空间，一部分为用户空间。针对linux操作系统而言，将最高的1G字节（从虚拟地址0xC0000000到0xFFFFFFFF），供内核使用；将较低的3G字节（从0x00000000到0xBFFFFFFF）供用户进程使用。每个进程可以通过系统调用进入内核。

   

   内核空间存放linux内核代码和数据，用户空间存放的是用户的程序代码和数据。Linux只使用Intel的Ring0和Ring3两级保护机制（Ring0供内核使用，Ring3供用户空间使用）

   

   但一个进程执行系统调用而陷入内核代码中执行时，称进程处于内核运行态（内核态）。此时内核正在代其执行，在这种情况下，进程被称为通过系统调用在内核空间运行，而内核被称为运行于进程上下文中。当进程处于内核态时，执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。

   当进程在执行用户程序代码时，则称其处于用户运行态（用户态）。

2. 进程上下文，中断上下文
   上下文（context）简单来说就是一个环境。对于进程来说就是进程执行时的环境。
   用户空间的程序通过系统调用进入内核空间。这个时候用户空间的进程要传递很多变量、参数给内核，内核态运行的时候也要保存用户进程的一些寄存器的值、变量等。相对于进程而言，具体就是各个变量和数据，包括所有的寄存器变量、进程打开的文件、内存信息等。一个进程的上下文可以分为三个部分：用户级上下文、寄存器上下文以及系统上下文。

   • 用户级上下文：正文、数据、用户堆栈以及共享存储器；
   • 寄存器上下文：通用寄存器、程序寄存器、处理器状态寄存器、栈指针；
   • 系统级上下文：进程控制块（task_struct)、内存管理信息（mm_struct, vm_area_struct, pgd, pte）、内核栈
     当发生进程调度时，进行进程切换就是上下文切换（context switch）。操作系统必须对上面提到的全部信息进行切换，新调度的进程才能运行。而系统调用进行的模式切换（mode switch），模式切换相较于进程切换，容易很多，而且节省时间，因为模式切换最主要的任务时切换进程寄存器。

   硬件通过触发信号，导致内核调用中断处理程序，进入内核空间。这个过程中，硬件的一些变量和参数也要传递给内核，内核通多这些参数进行中断处理。所谓中断上下文，其实也可以看作硬件传递过来的参数和内核需要保存的一些环境。中断时，内核不代替任何进程运行，而是执行中断处理，与之没有进程相关联，也就没有进程上下文。内核运行与中断上下文时，不会被阻塞，因为此时没有与之关联的进程上下文，也就没有进程。

References:

Linux内核设计与实现（第三版）
用户空间与内核空间，进程上下文与中断上下文

Linux系统结构

Linux系统有4个主要部分：内核，shell，文件系统和应用程序。内核，shell和文件系统一起形成了基本的操作系统，它们使用户可以运行程序、管理文件并使用系统。

1. Linux内核

   内核是操作系统的核心，负责管理系统的进程、内存、设备驱动程序、文件和网络系统。

   

   **系统调用接口: **SCI层提供了某些机制执行从用户空间到内核的函数调用。SCI实际上是一个非常有用的函数调用多路复用和多路分解服务。

   • 内存管理

     Linux采用了虚拟内存的内存管理方式。Linux将内存划分为容易处理的“内存页”（对于大部分体系结构来说都是4KB）。Linux包括了管理内存的方式，以及物理和虚拟映射所使用的硬件机制。

     不过内存管理要管理的可不止4KB缓冲区。Linux提供了对4KB缓冲区的抽象。这种内存管理模式使用4KB缓冲区为基数，然后从中分配结构，并跟踪内存页使用情况，比如哪些内存页是满的，哪些页面没有完全使用，哪些页面为空。这样就允许该模式根据系统需要来动态调整内存使用。

     为了支持多个用户使用内存，有时会出现可用内存被消耗光的情况。因此，页面可以一处内存并放入磁盘中。这个过程称为交换，因为页面会从内存交换到硬盘上。

   • 进程管理

     进程实际是某个特定应用程序的一个运行实体。在Linux系统中，能够同时运行多个进程，Linux通过在短时间间隔内轮流运行这些进程而实现“多任务”。这一短时间间隔称为“时间片”，让进程轮流运行的方法称为“进程调度”。

     进程调度控制进程对CPU的访问。当需要选择下一个进程运行时，由调度程序选择最值得运行的进程。可运行进程实际上是仅等待CPU资源的进程，如果某个进程在等待其他资源，着该进程是不可运行进程。Linux使用了比较简单的基于优先级的进程调度算法选择新的进程。

     通过多任务机制，每个进程可认为只有自己独占计算机，从而简化程序的编写。每个进程有自己单独的地址空间，并且

   • 文件系统

   • 设备驱动程序

   • 网络接口（NET）

   ---

2. Linux Shell

   …

   ---

3. Linux文件系统

   …

   ---

4. 应用程序

   Linux系统一般都有一套称为应用程序的程序集，包括文本编辑器、编程语言、x window、Internet工具和数据库等。

   ---

5. 内核参数

   Linux内核提供了一种通过/proc文件系统，在运行时访问内核内部数据结构、改变内核设置的机制。proc文件系统是一个伪文件系统，它只存在内存当中，而不占用外存空间。它以文件系统的方式为访问系统内核数据的操作提供接口。

   用户和应用程序可以通过/proc得到系统的信息，并可以改变内核的某些参数。由于系统的信息，如进程，是动态改变的，所以用户或应用程序读取/proc文件时，/proc文件系统是动态从系统内核读出所需信息并提交的。在/proc下有三个很重要的目录：/net，/scsi和/sys。/sys目录是可写的，可一通过它来访问或修改内核的参数，而/net和/scsi则依赖于内核配置。例如，如果系统不支持scsi，则scsi目录不存在。

   除了这些，还有一些以数字命名的目录，它们是进程目录。系统中当前运行的每一个进程都有对应的一个目录在/proc下，以进程的PID为目录名，它们是读取进程信息的接口。而/self目录则是读取进程本身的信息接口，是一个link，不同进程访问该目录是获得的信息是不同的，内容等价于/proc/本进程pid/。进程可以通过访问/proc/self来获取自己的系统信息，而不用每次都获取pid。

Reference:

[1] Linux系统结构 详解

[2] Linux下/proc目录简介

GPU加速版TensorFlow安装踩坑记录

System information:

• Ubuntu 18.04 LTS

• TensorFlow version: 1.13

• Python version: 3.6

• CUDA: 10.0

• cuDNN: 7.4

• GPU: Nvidia GeForce GTX 1050

1. 千万提前确定好需要使用的tensorflow版本，再下载版本匹配的CUDA, cuDNN

   幸好TensorFlow已经帮我们测试好了，在官网可以轻松找到推荐的构建配置。因为我平时都在用Ubuntu18.04，在这把Linux平台上合适的配置放出来

   

2. 确定好构建配置，这一步可以下载CUDA和cuDNN了

   CUDA安装指令在官网已经详细贴出来，我就不再重复（真正的坑在安装cuDNN的时候等着呢）

   安装cuDNN（这里还是以Linux平台为例）：

   • 下载cuDNN需要先注册

   • 解压tar包，先修改tar包文件权限

     $sudo chmod +x cudnn-10.0-linux-x64-v7.4.2.tgz

     $tar -xzvf cudnn-10.0-linux-x64-v7.4.2.24.tgz

   • 复制下列文件到CUDA Toolkit的文件夹，修改这些文件权限

     一般CUDA Toolkit会自动安装在/usr/local下面

     $sudo cp cuda/include/cudnn.h /usr/local/cuda/include

     $sudo cp cuda/lib64/libcudnn* /usr/local/cuda/lib64

     $sudo chmod a+r /usr/local/cuda/include/cudnn.h /usr/local/cuda/lib64/libcudnn*

3. 全部安装好后，检查版本是否正确

   • CUDA版本

     $cat /usr/local/cuda/version.txt 或者nvcc --version

   • cuDNN版本

     $cat /usr/local/cuda/include/cudnn.h | grep CUDNN_MAJOR -A 2

     ps: 有时候遇到failed call to cuInit: CUDA_ERROR_UNKNOWN: unknown error需要重启电脑

4. 最后的最后，检查TensorFlow是否能使用GPU加速

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   from tensorflow.python.client import device_lib import tensorflow as tf # list the avilable devices in local processes device_lib.list_local_devices() # matrix multiplying with GPU a = tf.constant([1.0, 2.0, 3.0, 4.0, 5.0, 6.0], shape=[2, 3], name='a') b = tf.constant([1.0, 2.0, 3.0, 4.0, 5.0, 6.0], shape=[3, 2], name='b') c = tf.matmul(a, b) sess = tf.Session(config=tf.ConfigProto(log_device_placement=True)) print(sess.run(c))

Socket编程

1. 网络中进程间通信

进程通信的概念最初来自于单机系统。网络间进程通信要解决的是不同主机进程间的相互通信问题（可把统计进程通信看做是其中的特列）。首先需要解决的是网络间进程标识的问题。同一主机上，不同进程可以用进程号（PID）来区分。但在局域网中，各主机独立分配进程号，不同主机不同基层可能拥有相同的进程号，所以无法用来唯一标识。

TCP/IP协议族可以解决这个问题，网络层的”ip地址“可以唯一标识网络中的主机，而传输层的”协议+端口号“可以唯一标识主机中的进程。这样一个三元组（IP地址，协议，端口）就可以标识网络的进程了，网络中的进程通信就可以利用这个标识与其他进程交互。

使用TCP/IP协议的程序通常采用应用编程接口：UNIX BSD的套接字（socket）来实现网络进程之间的通信。

2. socket套接字

socket起源于Unix，而Unix基本哲学之一就是”一切皆文件“， 都可以用”open -> write/read -> close“模式来操作。socket就是该模式的一个实现。socket即是一种特殊的文件，一些socket函数就是对其进行的操作。

socket是在应用层与TCP/IP之间的一个软件抽象层次，准确的说，它是一个接口。在设计模式中，socket使用了门面模式（Facade pattern）。它将复杂的TCP/IP协议族隐藏在socket接口后面，对用户来说，一组简单的接口就是全部，让socket去组织数据。

3. 客户端/服务器socket通信简单例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 客户端
import socket

# create socket descriptor
client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
# connect with local loopback address
client.connect(('127.0.0.1', 9999))

# receive message from server, and send message from console input
# close the socket until input 'exit'
while True:
    data = client.recv(1024)
    print(data.decode('utf-8'))
    
    msg = input('>>> ')
    client.send(msg.encode('utf-8'))
    if msg == 'exit':
        break
client.close()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 服务器端
import socket
import time
import random

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind(('127.0.0.1', 9999))
s.listen(5)  # backlog number
print('Waiting for connection...')

# accept connection from client
# receive message from client and send a random integer back 
# until receive 'exit', close the connection and wait for next one
while True:
    conn, addr = s.accept()
    conn.send(b'Welcome')
    print('Connected with %s:%s' % addr)
    while True:
        data = conn.recv(1024)
        time.sleep(1)  # simple way to unpack block
        if not data or data.encode('utf-8') == 'exit':
            break
        else:
            msg = random.randint(1, 100)
            conn.send(str(msg).encode('utf-8'))
    conn.close()
    print('Connection from %s:%s closed\n' % addr)

4. Python socket编程

   a. 创建socket描述符

   socket.socket(address_family, socket_type, protocol)

   address_family选择协议族（都以AF_开头），决定地址格式。socket_type确定套接字的类型。protocol指定协议。

   b. 链接connect()

   c. 监听bind()

   accept()

   d. 接受recv() recvfrom()

   e. 发送 send() sendto()

5. Unix/linux下网络处理多连接

   解决多客户‘并发’的方式：

   a. 多线程

   每当有客户端连接，启动一个线程来处理客户端数据

   b. 异步I/O

   asyncio库使用单线程来处理多任务, 使用事件循环来管理任务

   c. I/O复用，同步非阻塞监听

先来理解下复用这个概念，复用也就是共用的意思。比较形象的解释，先看在通信领域中的使用，在通信领域中为了充分利用网络连接的物理介质，往往在同一条网络链路上采用时分复用或者频分复用的技术使其在同一链路上传输多路信号。对于网络编程来说，客户端发来的请求服务端会产生一个进程来对其服务，每当来一个客户请求就产生一个进程来服务，然而进程不可能无限制的产生，因此为了解决大量客户端访问的问题，引入了I/O复用技术：一个进程可以同时对多个客户请求进行服务。也就是说I/O复用的介质是进程，复用一个进程来对多个I/O进行服务，虽然客户端发来的I/O是并发的，但是I/O所需的读写数据多数情况下是没有准备好的，因此就可以利用select或者poll 来监听I/O所需的这些数据的状态，一旦I/O有数据可以进行读写了，进程就来对这样的I/O进行服务。

To support the implementation of servers, the socket interface also provides a function called select() that manages a set of sockets. A call to select() returns information about which sockets have a packet waiting to be received and which sockets have room to accept a packet to be sent. The use of select() eliminates the polling and busy waiting that would otherwise be necessary for network I/O.

假设一个进程同时见识多个设备，如果read(设备1) 是阻塞的，那么只要设备1没有数据到达，就会一直阻

塞在设备1的read调用上，即使设备2有数据到达也不能处理，使用非阻塞I/O就可以避免设备2得不到及时处理。

非阻塞I/O有一个缺点，如果所有设备都一直没有数据到达，调用者需要反复查询做无用功，如果阻塞在那里系统可以调度执行其他进程，就不会做无用功了。select() 函数可以阻塞地同时监视多个设备，还可以设定阻塞等待的超市时间，从而解决了这个问题。

python标准库提供I/O多路复用模块，包括基础的select 模块和高层的selectors 模块

6. 附录

• 进程的阻塞：
  正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作做等，则由系统自动执行阻塞原语（Block），使自己由运行状态变为阻塞状态。当进程调用一个阻塞（Block）的系统函数时，该进程被置于睡眠状态，这时内核调度其他进程运行，直到该进程等待的事件发生了（比如网络上接收到数据包，或者调用sleep制定的睡眠时间到了）它才有可能继续运行。与睡眠状态相对的是运行状态，在linux内核中处于运行状态的进程分为两种情况：正在被调用执行和就绪状态。
  
• Unix/Linux下可用的5种I/O模型：
  • 阻塞I/O
  • 非阻塞I/O
  • I/O多路复用 (select, poll)
  • 信号驱动I/O (SIGIO)
  • 异步I/O

Reference：

[1] Linux的SOCKET编程详解

[2] Python——Socket编程

[3] Python Socket编程

[4] Python中的Socket编程

[5] Linux IO模式及select, poll, epoll详解