紫梦沁香

一、Git是什么

​ Git是当前最先进、最主流的分布式版本控制系统，免费、开源！核心能力就是版本控制。再具体一点，就是面向代码文件的版本控制，代码的任何修改历史都会被记录管理起来，意味着可以恢复到到以前的任意时刻状态。

主要特点

• 开源免费，使用广泛
• 强大的文档（代码）的历史版本管理，直接记录完整快照（完整内容，而非差异），支持回滚、对比
• 分布式多人协作的的代码协同开发，几乎所有操作都是本地执行的，支持代码合并、代码同步
• 简单易用的分支管理，支持高效的创建分支、合并分支

二、概念汇总

三、基本操作

1
2
3
4
5
6
7
8
9

git config --global user.name "name"	# 设置用户名
git config --global user.name "email"	# 设置邮箱
git init 	# 设置当前目录为git仓库
git commit -a	# 指令省略了add到暂存区的步骤，直接提交工作区的修改内容到版本库，不包括新增的文件。
git fetch, git pull	# 都是从远程服务端获取最新记录，区别是git pull多了一个步骤，就是自动合并更新工作区。
git checkout ., git checkout [file]	# 会清除工作区中未添加到暂存区的修改，用暂存区内容替换工作区。
git checkout HEAD ., git checkout HEAD [file]	# 会清除工作区、暂存区的修改，用HEAD指向的当前分支最新版本替换暂存区、工作区。
git diff	# 用来对比不同部分之间的区别，如暂存区、工作区，最新版本与未提交内容，不同版本之间等。
git reset	# 是专门用来撤销修改、回退版本的指令，替代上面checkout的撤销功能。

四、配置文件

Git有三个主要的配置文件：三个配置文件的优先级是① < ② < ③

• ① 系统全局配置(–system)：包含了适用于系统所有用户和所有仓库（项目）的配置信息，存放在Git安装目录下C:\Program Files\Git\etc\gitconfig。
• ② 用户全局配置(–global)：当前系统用户的全局配置，存放用户目录：C:\Users\[系统用户名]\.gitconfig。
• ③ 仓库/项目配置(–local)：仓库（项目）的特定配置，存放在项目目录下.git/config

1
2
3
4
5
6
7
8
9

# 查看git配置
git config --list
git config -l
# 查看系统配置
git config --system --list
# 查看当前用户（global）全局配置
git config --list --global
# 查看当前仓库配置信息
git config --local  --list

gitignore 文件示例

1
2
3
4
5

*.txt	# 忽略所有“.txt”结尾的文件
!lib.txt	# lib.txt除外
/temp	# 仅忽略项目根目录下的temp文件,不包括其它目录下的temp，如不包括“src/temp”
build/	# 忽略build/目录下的所有文件
doc/*.txt	# 会忽略 doc/notes.txt 但不包括 doc/server/arch.txt

一、 卡特兰数

公式：$\frac{1}{n+1}C^n_{2n}$

适用于求出栈序列个数，不同形状的二叉树个数以及有多少种括号匹配序列

注：上述三种适用情形不能有其他额外限制

二、常用代码块

（1）快速排序

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

void qsort(int a[], int left, int right){
    if(left >= right) return;
    int i = left, j = right;
    int b = rand() % (right - left + 1);	
    swap(a[left], a[left+b]);	

    while(i < j){
        while(i < j && a[j] >= a[left]) j--;
        while(i < j && a[i] <= a[left]) i++;
        swap(a[i], a[j]);
    }
    swap(a[i], a[left]);
    qsort(a, left, i-1);
    qsort(a, j+1, right);
}

（2）归并排序

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

int temp[n];
void msort(int a[], int left, int right){
    if(left >= right) return;
    int mid = (left + right) / 2;
    msort(a, left, mid);
    msort(a, mid + 1, right);

    int i = left, j = mid + 1, p = left;
    while(i <= mid && j <= right){
        if(a[i] <= a[j]) temp[p++] = a[i++];
        else temp[p++] = a[j++];
    }

    while(i <= mid) temp[p++] = a[i++];
    while(j <= right) temp[p++] = a[j++];
    for(i = left; i <= right; i++) a[i] = temp[i];
}

（3）二分查找

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

// 在长度为n的有序数组a中寻找值为k的元素下标
// 返回-1则表明未找到
int(int a[], int n, int k){
    int l = 0, r = n - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(a[mid] < k) l = mid + 1;
        else if(a[mid] > k) r = mid - 1;
        else return mid;
    }
    return -1;
}

（4）邻接表

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

typedef struct EdgeNode{
    struct EdgeNode *next;
    int target;	// 被指向顶点的编号
    int weight;	// 边的权重
}EdgeNode;

typedef struct VertexNode{
    EdgeNode *first;
    char name;
}VertexNode;

typedef struct Graph{
    VertexNode list[10];
    int numVertex, numEdge;
}Graph;

// i -> j = w
void addEdge(Graph *g, int i, int j, int w){
    EdgeNode edge = {g->list[i].first, j, w};
    g->list[i].first = edge;
}

（5）层序遍历

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

const int N = 1e7;
typedef struct TNode{
    struct TNode *left, *right;
    int val;
}*TNode;

TNode nodes[N];
void func(TNode root){
    int l = r = 0;
    nodes[r++] = root;
    while(l<r){
        TNode node = nodes[l++];
        if(!node) continue;
        nodes[r++] = node->left;
        nodes[r++] = node->right;
        cout << node->val << " ";
    }
}

（6）树的定义

• 双亲表示法

  1 2 3 4 5 6

  typedef struct{ ElemType data; int parent; }PTNode; PTNode tree[10];

• 孩子表示法

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

  //Child表示下一个孩子的信息 typedef struct Child{ int index; //孩子编号 struct Child * next; //下一个孩子 } Child; //TreeNode用于保存结点信息 typedef struct TreeNode { char data; //结点信息 Child * firstChild; //指向第一个孩子 } TreeNode; TreeNode tree[10]; //定义一棵拥有10个结点的树（孩子表示法）

• 孩子兄弟表示法

  1 2 3 4

  typedef struct CSNode{ ElemType data; //数据域 struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针 }CSNode,*CSTree;

三、数据结构

• 逻辑结构
  • 线性结构
  • 非线性结构
    • 树形结构
    • 图状结构
• 物理(存储)结构
  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储

四、图论算法

五、红黑树

• 对于每个节点，从该节点到任意一个叶节点的简单路径上，所含黑节点的数量相同

• n个节点的红黑树的高度 h<= $2log_2(n+1)$

• 任何一棵红黑树都对应一棵四阶B树

六、B树和B+树

• 含有n个叶节点的B+树有n个关键字
• B+树无论查找成功与否，每次查找都必定查找到叶节点；而B树可能查找到中间节点就停止了。
• n阶B树每个节点至多n-1个关键字，至少(n-1)/2个关键字；n阶B+树每个节点至多n个关键字，至少(n+1)/2个关键字。
• n阶B树和n阶B+树除根节点外每个非叶结点至少含有(n+1)/2个子树
• B树的总关键字数 + 1 = 叶节点数，

七、散列表

（1）散列函数

• 直接定址法

  H(key) = a * key + b

• 除留余数法

  H(key) = key % p（p取小于等于表长的最大质数）

• 数字分析法

  选取数字中较为均匀分布的若干位作为散列地址，例如手机号后四位

• 平方取中法

  取关键字平方的中间几位作为散列地址

（2）处理冲突

• 开放定址法

  • 线性探测法

    • di = 0, 1, 2, 3, 4…

    • 会导致堆积

  • 平方探测法

    • di = 0, 1, -1, 4, -4, …, $k^2$, $-k^2$（k <= m / 2）
    • m必须是一个能表示成4k+3的素数
    • 可以避免堆积
    • 无法探测到散列表上的所有单元，但至少能探测到一半

  • 双散列法

    • di = i * h2(key)
    • Hi = (H(key) + i * h2(key)) % m
    • 初始探测位置为H0

  • 伪随机序列法

    • di = 伪随机数序列

  开放定址法不能随意删除元素，得先做逻辑删除。

• 拉链法

  • 避免了非同义词的冲突
  • 适用于经常插入删除的情况
  • 数组部分不计入查找长度

八、排序算法

九、外部排序

（1）初始归并段

生成初始归并段相当于先做了一次归并排序

（2）败者树

败者树可以有效减少多路归并排序时的比较次数

• 败者树每次维护会一直维护到根节点；堆排序可能维护到一半就停止。
• 败者树每上一层只需要和败者节点比较一次即可；堆排序每下一层需要和左右子节点共比较两次。
• 相同规模下，败者树所需的空间是堆排序所需空间的两倍。
• 败者树首次比较仍需k-1次比较，后续每次最多需要$log_2k$次比较
• 败者树是一棵完全二叉树

（3）置换选择排序

• 获得的归并段的平均长度是内存工作区大小的两倍
• 获得的初始归并段大小不受内存容量的限制

（4）最佳归并树

• 采用哈夫曼思想构建哈夫曼树
• 磁盘I/O次数 = 2 * WPL

十、杂项

（1）线性表可以是空表，树可以是空树，但图不能是空图，图至少包含一个顶点。

（2）AOV无边权，AOE有边权

（3）二叉平衡树的平衡因子 = 左子树高度 - 右子树高度

（4）链表插入删除要考虑特殊情况（链表为空）

（5）矩阵转数组存储注意下标

（6）连通图特指无向图，强连通图特指有向图

一、TCP连接

（1）TCP连接

（2）TCP释放

Server最快在 1.5RTT 后释放连接

Client最快在 1RTT+2MSL 后释放连接

MSS指的是TCP数据载荷的最大长度

二、服务访问点SAP

数据链路层：类型，例如0080代表上层是IP

网络层：协议，例如17代表上层是UDP，6代表上层是TCP

传输层：端口号，例如80代表上层是HTTP

三、常见网络协议汇总

注：ICMP、OSPF、IGMP、ARP虽然是网络层的协议，但前三者要封装在IP报文中传送，而ARP请求报文直接封装在以太网广播帧中。

补充：TELNET端口号为23，使用TCP连接。

四、IPV4地址

（1）私有地址

• A类：10.xx.xx.xx
• B类：172.16.xx.xx - 172.31.xx.xx
• C类：192.168.xx.xx

（2）IP地址分类

• A类：1-126
• B类：128-191
• C类：192-223
• D类（组播）：224-239
• E类（今后使用）：240-255

五、SDN

（1）从上到下依次是应用平面，控制平面和数据平面。SDN将数据平面与控制平面分离，将数据平面保留在网络层设备中，只包含转发功能；控制平面作为应用平面和数据平面的桥梁；应用平面用于实现路由选择功能。

（2）Openflow是南向接口（通信层）协议

六、介质访问控制

静态划分信道如频分复用，时分复用属于物理层范畴，而动态划分信道如CSMA，令牌环网属于数据链路层范畴。

七、HTTP

HTTP/1.0，HTTP/1.1，HTTP/2.0在运输层使用TCP，而HTTP/3.0在运输层使用UDP。

HTTP/1.0只支持非持续连接，所以每请求一个对象需要建立一次TCP连接。

八、常用公式

（1）奈氏准则

理想低通信道下的极限码元传输速率为$2W$波特

理想低通信道下的极限数据传输速率为$2Wlog_2V$（b/s）

其中低通是指没有噪声，带宽有限的信道

（2）香农定理

信道的极限数据传输速率为$Wlog_2(1+\frac{S}{N})$

信噪比(db) = $10log_{10}\frac{S}{N}$

八、编码与调制

（1）数字数据编码成数字信号

• 归零编码（RZ）
  • 高1低0（或相反）
  • 自同步
• 非归零编码（NRZ）
  • 高1低0
  • 若想同步，需要带有时钟线
• 反向非归零（NRZI）
  • 翻转为0，不变为1
  • 自同步
• 曼彻斯特
  • 前高后低为1；前低后高为0
  • 自同步
  • 两个码元表示1bit数据
• 差分曼彻斯特
  • 若码元为1，则前半个码元的电平与上一码元的后半个码元的电平相同
  • 自同步
  • 两个码元表示1bit数据
• 4B/5B
  • 五位编码表示16种数据和16种控制码

（2）数字数据调制成模拟信号

• 幅移键控（ASK）
• 频移键控（FSK）
• 相移键控（PSK）
• 正交振幅调制（QAM）

（3）模拟数据编码成数字信号

• 脉码调制（PCM）
  • 采样：采样频率要大于等于最大频率的两倍
  • 量化
  • 编码

（4）模拟数据调制成模拟信号

• 频分复用（FDM）

九、数据报和虚电路

十、NAT路由地址转换

（1）NAT

• 一个全球IP对应一个私有IP
• 若NAT共有n个全球IP，则最多同时有n台机器访问外网

（2）NAPT

• 一个全球IP+不同的端口号对应多个私有IP
• 通信仅限于TCP或UDP

十一、差错控制

（1）CRC冗余校验

• 可以检测出所有奇数个错误
• 可以检测出所有双比特的错误
• 可以检测出小于等于r位的错，r为多项式阶数

（2）海明码

• 检测n位错误需要n+1位码距
• 纠正n位错误需要2n+1位码距

十二、CSMA

• CSMA/CD

  • 只用于半双工通信
  • 截断二进制指数退避算法（已经发送k次冲突）
    • 若k>=16，丢弃该帧并向高层报告
    • 若10<k<16，取k=10
    • 从[0, $2^k-1$]中随机选取一个数r，等待2rτ时间后重传（2τ为RTT）

• CSMA/CA

  • 隐蔽站

    

    sta1和sta2同时向ap1发送数据，但他们彼此不能互相感知，就会在接收端造成数据冲突

  • 暴露站

    

    ap2向sta2发送数据，而ap1收到ap2的数据后会认为无法给sta1发数据，但其实是可以发送的。

十三、ICMP

（1）差错报告报文

• 终点不可达
• 源点抑制
• 时间超过
• 参数问题
• 改变路由（重定向）

（2）询问报文

• 回送请求和回答报文
• 时间戳请求和回答报文
• 地址掩码请求和回答报文
• 路由器询问和通告报文

十四、IPV4和IPV6

十五、各层PDU细节

十六、杂项

• 捎带确认要计算响应报文的发送时延，响应报文的长度与请求报文等长
• 路由器有几个接口就至少有几个路由表项

一、中断

故障（软件中断）：若可以解决（如缺页），则返回当前指令；若不能解决（如除0），则终止进程。

二、操作系统引导

1、 CPU从特定主存地址（ROM）开始读取指令，执行ROM中的引导程序，进行硬件自检，确定磁盘位置

2、 将磁盘的第一块——主引导记录（MBR）读入内存，MBR中包含磁盘引导程序和分区表

3、 执行磁盘引导程序，从主分区（C盘）读入分区引导记录（PBR），执行其中的程序

4、 从根目录下找到找到启动管理器（操作系统初始化程序）并执行，完成开机

三、读者写者问题

（1）读优先

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

// m 实现对n的互斥访问
// wmutex 实现读写互斥
semaphore m = 1, wmutex = 1;	
int rcnt = 0;
    
void writer(){
    P(wmutex);
    read();
    V(wmutex);
}

void reader(){
    P(m);
    if(!rcnt) P(wmutex);
    rcnt++;
    V(m);
    read();
    P(m);
    rcnt--;
    if(!rcnt) V(wmutex);
    V(m);
}

（2）写优先

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

// m1和m2实现对rcnt和wcnt的互斥访问
// rmutex和wmutex实现读写互斥
semaphore m1 = 1, m2 = 1, rmutex = 1, wmutex = 1;	
int rcnt = 0, wcnt = 0;
    
void writer(){
    P(m1);
    if(!wcnt) P(rmutex);
    wcnt++;
    V(m1);
    P(wmutex);
    write();
    V(wmutex);
    P(m1);
    wcnt--;
    if(!wcnt) V(rmutex);
    V(m1);
}

void reader(){
    P(rmutex);
    P(m2);
    if(!rcnt) P(wmutex);
    rcnt++;
    V(m2);
    V(rmutex);
    read();
    P(m2);
    rcnt--;
    if(!rcnt) V(wmutex);
    V(m2);
}

（3）读写公平

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

// m 实现对n的互斥访问
// lock实现读写互斥
// que用于实现读写公平
semaphore m = 1, wmutex = 1, que = 1;	
int rcnt = 0;
    
void writer(){
    P(que);
    P(wmutex);
    read();
    V(wmutex);
    V(que);
}

void reader(){
    P(que);
    P(m);
    if(!rcnt) P(wmutex);
    rcnt++;
    V(m);
    V(que);
    read();
    P(m);
    rcnt--;
    if(!rcnt) V(wmutex);
    V(m);
}

四、文件控制块

（1）顺序分配

FCB

顺序分配的寻道数和寻道时间最小。

（2）链式分配

• 隐式链接

  FCB

  文件名	起始块号	结束块号
  file1	0	2
  file2	2	3

  除最后一个盘块外，每个盘块都有指向下一个盘块的指针，这些指针对用户透明。

  一般可将几个盘块组成簇，按簇而不按块来分配。

• 显示链接

  FCB

  文件名	起始块号
  file1	0
  file2	2

  FAT

  盘块号（隐含）	下一块
  0	3
  1	4
  2	-1
  3	-1
  4	2
  5	-2

  FAT不仅记录了文件各块之间的先后关系，还标记了空闲的磁盘块，操作系统可以根据FAT对文件存储空间进行管理。此外，FAT常驻内存。

（3）混合索引分配

FCB

0号索引节点

inode区不常驻内存，故在查找到inode号之后，还需在inode区中根据读出对应的inode节点。

五、文件系统结构

应用程序 -> 逻辑文件系统 -> 文件组织模块 -> 基本文件系统 -> I/O控制 -> 设备

• 逻辑文件系统： 用于管理元数据信息。
• 文件组织模块： 组织文件及其逻辑块和物理块。
• 基本文件系统： 向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块。
• I/O控制： 包括设备驱动程序和中断处理程序，在内存和磁盘系统之间传输信息。

六、I/O接口

• 数据寄存器用于存放从设备送来的输入数据或从CPU送来的输出数据
• 控制/状态寄存器用于存放从CPU送来的控制信息或设备的状态信息
• I/O接口的主要功能有
  • 地址译码和设备选择
  • 主机和外设的通信
  • 数据缓冲
  • 信号格式转换
  • 传送控制命令和状态信息

I/O接口 = I/O端口 + 控制逻辑

• I/O端口是设备管理器中可被CPU直接访问的寄存器

七、中断响应

• 硬件执行
  • 关中断
  • 保存断点和程序状态
  • 引出中断服务程序
• 软件执行
  • 保存现场
  • 开中断
  • 执行中断服务程序
  • 关中断
  • 恢复现场
  • 开中断
  • 中断返回

八、DMA控制器

（1）DMA控制内部结构

• CR（命令/状态寄存器）：接收从CPU发来的I/O命令、有关控制信息或设备的状态。
• MAR（内存地址寄存器）：存储这批数据要传送到内存的起始目标地址。
• DR（数据寄存器）：暂存从设备到内存或从内存到设备的数据。
• DC（数据计数器）：存放本次要传送的字（节）数。

每完成一次数据交换，(MAR) + 1，(DC) - 1，直至(DC) = 0，代表此次数据传送完毕。

DMA与主存以字为单位交换数据，DMA与外设以字节或位为单位进行传送。

（2）DMA传送方式

外设向DMA控制器发送DMA请求，再由DMA控制器向CPU发出总线请求

• 停止CPU访存
• 周期挪用
  • 单字传送方式
  • DMA对于总线的使用权大于CPU对于总线的使用权
• DMA与CPU交替访存
  • 适用于CPU工作周期大于主存存取周期，可将一个CPU周期分成两个周期C1和C2，一个供CPU访存，一个供DMA访存。

九、I/O软件层次

9.1、设备独立性软件

1、设备分配的数据结构

（1）设备控制表（DCT）：系统为每个设备配置一张设备控制表。

（2）控制器控制表（COCT）：系统为每个控制器配置一张控制器控制表。

（3）通道控制表（CHCT）：系统为每个通道配置一张通道控制表。

（4）系统设备表（SDT）：整个系统只有一张系统设备表，每个设备占一个表目。

一个通道可以控制多个设备控制器，而每个设备控制器又可以控制多个设备（并发而非并行）。只有当通道、设备控制器、设备都成功分配时，进程才能正常使用设备。

设备分配程序为用户进程分配设备：先分配设备，再分配设备控制器，最后分配通道。

2、逻辑/物理设备映射的数据结构

（1）整个系统只设置一张逻辑设备表（LUT）

此方案无论是否是同一用户的逻辑设备，均不允许同名，仅适用于单用户系统。

（2）为每个用户设置一张逻辑设备表（LUT）

此方案允许使用相同的逻辑设备名，类似单级目录和多级目录的区别。

3、SPOOLing

输入井和输出井位于磁盘，输入缓冲区和输出缓冲区位于内存，井管理程序用于控制设备与输入井、输出井之间信息的交换。

SPOOLing具体功能如下：

• 缓冲区的设置缓和了CPU和磁盘之间速度不匹配的矛盾。
• 将独占设备改造为虚拟的共享设备。
• 将一个物理设备变换为多个对应的逻辑设备。

十、磁盘初始化

（1）物理格式化

• 将磁道划分扇区
• 为每个扇区使用特殊的数据结构，包括校验码

（2）分区

• 将磁盘分区，即C盘、D盘等

（3）逻辑格式化

• 创建文件系统
• 创建根目录
• 初始化存储空间管理所用的数据结构（如位示图、空闲分区表）

十一、常用公式

（1）带权周转时间 = 周转时间 / 执行时间 = 响应比

虽然二者在公式上是相等的，但带权周转时间是静态的概念，确定了就不会再改变；而响应比是动态的概念，会随着程序的执行而改变。

（2）磁盘平均存取时间 = 平均寻道时间 + 旋转延迟时间（一般取半转的时间） + 传输时间

（3）磁盘地址为（柱面号，盘面/磁道号，扇区号）

十二、操作系统结构

十三、虚拟机

十四、固态硬盘

十五、内存映射文件