周一周二是复习的外文，总结如下。

声明：本部分参考徐学长的面试基础学习笔记

AVL 以发明者的名字命名的平衡二叉树（ Adelson-Velskii 以及 Landis）。AVL树是一种平衡的二叉搜索树，在添加和删除节点后，通过树旋转再次达到平衡。右旋转是以某个节点为中心，将其入当前右节点的位置，使当前左节点作为新树的根节点，也称为顺时针旋转。同样，左旋以某个节点为中心，沉入当前左节点的位置，使当前右节点作为新树的根节点，也称为逆时针旋转。

红黑树是1972年发明的，称为对称二叉B树，1978年正式命名为红黑树。主要特点是在每个节点添加一个属性来表示节点的颜色，可以是红色或黑色、红黑树和AVL类似的树在插入和删除时通过旋转保持平衡，从而获得更高的搜索性能。与AVL与树相比，红黑树不追求所有递归子树的高差不超过1，确保从根节点到叶尾的最长路径不超过最短路径的2倍，因此最差时间的复杂性是O(logn)。通过重新着色和左右旋转，红黑树在插入和删除后更有效地完成了自平衡调整。

红黑树本质上是二叉搜索树，它引入了五个额外的约束：

• 节点只能是红色或黑色

• 根节点必须是黑色的

• 所有NIL节点是黑色的

• 相邻的两个红色节点不能出现在一条路径上

• 在任何递归子树中，从根节点到叶节点的所有路径都包含相同数量的黑色节点

这五种约束保证了红黑树的新增、删除和搜索的最坏时间复杂性O(logn)。如果一个树的左子节点和右子节点不存在，则均认定为黑色。红黑树的任何旋转在3次之内均可完成。

红黑树的平衡性不如AVL树，它只保持一般平衡，不严格保证左右子树的高差不超过1。这导致红黑树的高度可能更高，即平均搜索次数高于同一情况AVL树。

红黑树和插入时AVL树木可以在最多两次旋转中恢复平衡。删除时，红黑树最多可以恢复平衡，因为红黑树只追求一般平衡。AVL树最多需要O(logn)次。AVL插入和删除树木时，将向上追溯以确定是否需要旋转。这种追溯的时间成本最低O(logn)，红黑树每次向上追溯的步长为2，追溯成本低。因此，红黑树更适合频繁插入和删除。

B 树是一种特殊的平衡多路树，是B树的优化改进版，它将所有数据存储在叶节点上，中间节点保存索引。这样，与B树相比，减少了数据对中间节点的空间占用，使中间节点可以存储更多的指针，使树更短，更小的深度，从而减少了磁盘的查询IO提高查询效率。另一种是由于叶节点之间有指针连接，因此可以进行范围查询，方便区间访问。

红黑树是二叉的，其深度相对较深B 树更大，更深意味着搜索更多，磁盘更频繁IO，因此，红黑树更适合在内存中搜索。

B同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存同时存key和data，而B 只有叶节点存储在树上data，只存储非叶节点key。且B 指向相邻叶节点的链表指针节点的链表指针，形成了有序指针的链表指针B 提高区间访问性能的树木。由于B 树的数据存储在叶节点中，分支节点是索引，便于扫描图书馆，只需要扫描叶节点，但B树因为分支节点也存储数据，我们想找到具体的数据，需要按顺序扫描，所以B 树更适合区间查询，所以通常B 数据库索引采用树木，文件索引采用B树木。

1、 由于B 树木在非叶节点上不含数据信息，因此可以在内存页面中存储更多数据信息key，数据存储更紧密，空间利用率更好，叶节点上相关数据的访问也有更好的缓存命中率。

2、 B 树的叶节点是相连的，所以整棵树的遍历只需要一次性遍历叶节点。B树需要每层递归遍历，相邻元素在内存中可能不相邻，因此没有缓存命中性B 树好。

但是B树也有优点，因为每个节点都包含key和value，因此，经常访问的元素可能更接近根节点，访问速度更快。

1、 根节点至少有两个孩子

2、 每个中间节点都包k-一个元素和k个孩子，其中m/2 <= k <= m

3、 每个叶子节点都包含k-其中一个元素m/2 <= k <= m

4、 所有的叶子节点都位于同一层

5、 每个节点的元素从小到大排序，节点k-一个元素正好是k个儿童所含元素的值域划分。

B-其实树在查询中的比较次数并不比二叉查找树少，尤其是单个节点的元素数量多的时候。但与磁盘相比IO只要树的高度足够低，内存乎可以忽略，所以只要树的高度足够低，IO足够少的次数可以提高搜索性能。相比之下，节点中的内部元素更多并不重要，只要不超过磁盘页面的大小，就会有更多的内存交互。这就是B-树的优点之一。

1、 k个子树的中间节点包含k元素（B树中是k-每个元素不保存数据，只用于索引，所有数据都保存在叶节点。

2、 所有的叶节点都包含所有元素的信息，并指向包含这些元素记录的指针，叶节点本身按照关键字的大小和大顺序链接。

3、 所有中间节点元素都存在于子节点中，是子节点中最大(或最小)元素。

需要注意的是，根节点的最大元素相当于整个节点B 树的最大元素。以后无论插入删除多少元素，都要始终保持根节点中最大元素。

在B-在树中，中间节点和叶节点都有卫星数据。B 在树上，只有带有卫星数据的叶子节点，其他中间节点只是索引，没有数据关联。

• 首先，B 树的中间节点没有卫星数据，所以相同大小的磁盘页面可以容纳更多的节点元素。这意味着当数据量相同时，B 树的结构比B-树更加“矮胖”，因此查询时IO次数也较少。

• 其次，B 树的查询必须最终找到叶节点，B-无论匹配元素在中间节点还是叶节点，树只需要找到匹配元素。B-树的搜索性能不稳定(最好只查根节点，最坏的是查叶节点)。B 每的每一次搜索都是稳定的。

• 最后，B-树的范围查询只能依靠繁琐的中序遍历。B 树只需先找到下限，再通过链表指针遍历即可。

1、 单个节点存储更多的元素这样节点下分支更多，树木变矮变胖)，使查询IO次数更少。

2、 所有查询都要找到叶节点，查询性能稳定。

3、 所有叶子节点形成有序链表，便于范围查询。

• 选pivot，i = 0
• j = size - 1，将比pivot小的数放在pivot，j–，大于或等于它的数字留在右边
• 重复左右区间的第二步，直到每个区间只有一个数字

//快速排序 void quick_sort(int s[], int l, int r) { 
             if (l < r) { 
           //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1 int i = l, j = r, x = s[l]; while (i < j) { 
           while(i < j && s[j] >= x) // 从右向左找第一个小于x的数 j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // 递归调用  quick_sort(s, i + 1, r); } } 

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

• 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
• 解决（Conquer）：用合并排序法对两个子序列递归的排序。
• 合并（Combine）：合并两个已排序的子序列已得到排序结果。

递归法

• 开辟一个辅助数组用来存放临时结果，然后将其给原数组赋值

template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end) { 
        
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;//移位操作，等效为除以2
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;//将一个数组划分成两个子区间，分别调用归并排序
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)//将两个数组较小的值填入辅助数组
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)//第二块子区间元素已填完，将第一子区间整体填入辅助数组
        reg[k++] = arr[start1++];
    while (start2 <= end2)//第一块子区间元素已填完，将第二子区间整体填入辅助数组
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)//给原数组赋值
        arr[k] = reg[k];
}

// merge_sort
template<typename T>
void merge_sort(T arr[], const int len) { 
        
    T reg[len];//开辟临时数组
    merge_sort_recursive(arr, reg, 0, len - 1);
}

在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：

① 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点 ② 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序 ③ 堆排序（Heap_Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

#include <iostream>
#include <algorithm>
using namespace std;

void max_heapify(int arr[], int start, int end) { 
        
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { 
         // 若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { 
         // 否則交換父子內容再繼續子節點和孫節點比較
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) { 
        
    // 初始化，i從最後一個父節點開始調整即len/2，-1是因为数组下标从0开始
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先將第一個元素和已经排好的元素前一位做交換，再從新調整(刚调整的元素之前的元素)，直到排序完畢
    for (int i = len - 1; i > 0; i--) { 
        
        swap(arr[0], arr[i]);//大顶堆，最后的输出是升序排列
        max_heapify(arr, 0, i - 1);
    }
}

int main() { 
        
    int arr[] = { 
         3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

class Solution { 
        
public:
    int search(vector<int>& nums, int target) { 
        
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { 
         // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) { 
        
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) { 
        
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { 
         // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

整个工程只有一个开始点和一个完成点，所以在正常的情况（无环）下，网中只有一个入度为零的点，称为源点，也只有一个出度为零的点，称为汇点。在整个AOE(Activity On Edge)网中，一条路径各弧上的权值之和称为该路径的带权路径长度。要估算整项工程完成的最短时间，就是要找一条从源点到汇点的 带权路径最长 的路径，称为关键路径。关键路径上的活动叫做关键活动，这些活动是影响工程进度的关键，他们提前或拖延将使整个工程提前或拖延。

• 若网中有多条关键路径，则需要加快同时在几条关键路径上的活动。 如：a6、a9、a7、a10同时加速。

• 如果一个活动处于所有的关键路径上，那么提高这个活动的速度，才能缩短整个工程的完成时间。 如：a0、a3加速

• 处于所有关键路径上的活动完成时间不能缩短太多，否则会是的原来的关键路径变成非关键路径。这时，必须重新寻找关键路径。 如：a0 由 6天变成 1天，就会改变关键路径。

• OSI（Open System Interconnection，开放式系统互联）
• HTTP协议 (超文本传输协议HyperText Transfer Protocol)
• TCP协议（传输控制协议，Transmission Control Protocol）
• IP协议（Internet Protocol，互联网协议）
• UDP协议， User Datagram Protocol， 中文名是用户数据报协议

国际标准化组织ISO提出了OSI开放互连的七层计算机网络模型，从上到下分别是应用层、表示层、会话层、运输层、网络层、数据链路层和物理层。OSI模型的概念清楚，理论也比较完善，但是既复杂又不实用。还有一种是TCP/IP体系结构，它分为四层，从上到下分别是应用层、运输层、网际层和网络接口层，不过从实质上将只有三层，因为最下面的网络接口层并没有什么具体内容。因特网的协议栈使用一种五层的模型结构，从上到下依次是应用层、运输层、网络层、链路层和物理层，其中下层是为上层提供服务的，每层执行某些动作或使用下层的服务来提高服务。

• 物理层

物理层负责将信息编码成电流脉冲或其它信号用于网上传输。

RJ45等将数据转化成0和1

• 数据链路层

数据链路层通过物理网络链路提供数据传输。不同的数据链路层定义了不同的网络和协议特征，其中包括物理编址、网络拓扑结构、数据校验、数据帧序列以及流控。

可以简单的理解为：规定了0和1的分包形式，确定了网络数据包的形式。

• 网络层

网络层负责在源和终点之间建立连接。

可以理解为，此处需要确定计算机的位置，怎么确定？IPV4，IPV6！

• 传输层

传输层向高层提供可靠的端到端的网络数据流服务。

可以理解为：每一个应用程序都会在网卡注册一个端口号，该层就是端口与端口的通信！常用的（TCP/IP）协议。

• 会话层

会话层建立、管理和终止表示层与实体之间的通信会话。

建立一个链接（自动的手机信息、自动的网络寻址）

• 表示层

表示层提供多种功能用于应用层数据编码和转化，以确保以一个系统应用层发送的信息可以被另一个系统应用层识别。

可以理解为：解决不同系统之间的通信，Linux下的QQ和Windows下的QQ可以通信

• 应用层

OSI的应用层协议包括文件的传输、访问及管理协议（FTAM），以及文件虚拟终端协议（VIP）和公用管理系统信息（CMIP）等。

规定数据的传输协议

TCP是面向连接的运输层协议，一个应用进程在向另一个进程发送数据之前，两个进程必须先建立TCP连接，发送某些预备报文段，建立确保数据传输的参数。作为TCP连接建立的一部分，连接双方都将初始化与TCP连接相关的许多状态变量。这种连接不是电路交换网络中的端到端电路这种物理连接，而是一种逻辑连接，TCP报文要先传送到IP层加上IP首部后，再传到数据链路层，加上数据链路层的首部和尾部后才离开主机发送到物理层。

TCP连接提供全双工服务，允许通信双方的应用进程在任何时候都能发送数据。TCP连接的两端都有各自的发送缓存和接收缓存，用来临时存放通信数据。在发送前，应用程序把数据传送给TCP缓存后就可以做自己的事，而TCP在合适的时候会把数据发送出去。在接收时，TCP把收到的数据放入缓存，上层应用程序会在合适的时候读取缓存数据。

TCP连接是点对点的，每一条TCP连接只能有两个端点，即只能是单个发送方和单个接收方之间的连接。

TCP提供可靠的交付服务，通过TCP连接传送的数据无差错、不丢失、不重复，按序到达。

TCP是面向字节流的，流是指流入到进程或从进程中流出的字节序列。面向字节流的含义是：虽然应用程序和TCP的交互是一次一个数据块，但是TCP把应用程序交下来的数据仅仅看成一连串无结构的字节流。TCP不保证接收方应用程序收到的数据块和发送方应用程序发出的数据块具有对应大小的关系，但是接收方应用程序收到的字节流必须和发送方发出的字节流完全一样。接收方应用程序必须有能力识别收到的字节流，并把它还原成有意义的应用层数据。

如果某个应用程序读取数据的速度较慢，而发送方发送得太多、太快，发送的数据就会很容易使连接的接收缓存溢出，TCP 为它的应用程序提供了流量控制以消除发送方使接收方缓存溢出的可能性。流量控制是一个速度匹配服务，即发送方的发送速率与接收方的应用程序读取速率相匹配。

• SYN(synchronous建立联机)

• ACK(acknowledgement 确认)

• PSH(push传送)

• FIN(finish结束)

• RST(reset重置)

• URG(urgent紧急)

会产生Sequence number(顺序号码)和Acknowledge number(确认号码)

TCP是全双工通信，任何一方都可以发起建立连接的请求，假设A是客户端，B是服务器。

初始A和B均处于CLOSE状态，B会创建传输进程控制块TCB并进入LISTEND状态，监听端口是否收到了TCP请求以便及时响应。

第一次握手：客户端A发送位码为SYN=1，随机产生seq number=1234567的数据包到服务器B，B由SYN=1知道，客户端A要建立联机。此时客户端进入SYN发送状态，等待服务器确认。

第二次握手：服务器B收到请求后要确认联机信息，向A发送ack number=（客户端A的seq+1），SYN=1，ACK=1，随机产生seq=7654321的包。此时服务器进入SYN接收状态。

第三次握手：主机A收到后检查ack number是否正确，即第一次发送的seq number+1，以及位码ACK是否为1，若正确，客户端A会再发送ack number=（服务器B的seq+1），ACK=1（此时A的连接已经建立，可随即向B发送数据帧），服务器B收到后确认seq值与ACK=1则连接建立成功（B的连接稍晚建立）。客户端和服务器进入ESTABLISHED建立成功状态，完成三次握手。

从信息对等的角度看，双方只有确定4类信息才能建立连接，即客户端A和服务器B分别确认自己和对方的发送和接受能力正常。在第二次握手后，从服务器B的角度看不能确定自己的发送能力和对方的接受能力，只有在第三次握手后才能确认。

三次握手也是防止失效连接突然到达导致脏连接，网络报文的生存时间往往会超过TCP请求超时时间，客户端A的某个超时连接请求可能会在双方释放连接之后到达服务器B，B会误以为是A创建了新的连接请求，然后发送确认报文创建连接。因为客户端A的状态不是SYN发送状态，所以直接丢弃了B的确认数据。如果是两次握手，连接已经建立了，服务器资源被白白浪费。如果是三次握手，B由于长时间没有收到确认信息，最终超时导致创建连接失败，因此不会出现脏连接。

TCP分节可能由于路由器异常而“迷途”，在迷途期间，TCP发送端可能因确认超时而重发这个分节，迷途的分节在路由器修复后也会被送到最终目的地，这个迟到的迷途分节到达时可能会引起问题。在关闭“前一个连接”之后，马上又重新建立起一个相同的IP和端口之间的“新连接”，“前一个连接”的迷途重复分组在“前一个连接”终止后到达，而被“新连接”收到了。为了避免这个情况，TCP协议不允许处于TIME_WAIT状态的连接启动一个新的可用连接，因为TIME_WAIT状态持续2MSL，就可以保证当成功建立一个新TCP连接的时候，来自旧连接重复分组已经在网络中消逝。

TCP断开连接通常是由一方主动，一方被动的，这里我们假设客户端主动，服务器端被动

第一次挥手：当客户端没有数据要发送给服务端了，他会给服务端发送一个FIN报文，其中FIN=1，seq=u（客户端最后发送的一个序号+1），（告诉服务器，我已经没有数据要发送给你了，但是你要是还想给我发数据的话，你就接着发，但是你得告诉我你收到我的关闭信息了），发送完之后进入FIN-WAIT-1状态。

第二次挥手：当服务器收到客户端发来的FIN报文后（告诉客户端“我收到你的FIN消息了，但是你得等我发完的”），此时给客户端返回一个确认报文，ACK=1，ack number=u+1，seq=v，v为服务器之前发送的最后一个序号+1。此时客户端进入FIN-WAIT-2状态，服务器进入CLOSE-WAIT状态，但连接并未完全释放。

第三次挥手：当服务器发完所有数据时，他会给客户端发送一个FIN报文，（告诉客户端“我数据发完了，现在要关闭连接了”），FIN=1，ACK=1，ack number = u+1，seq=w（seq不是v的原因是在关闭状态服务器可能又发送了一些数据），之后服务器进入LAST_ACK状态，等着客户端最后的ACK信息。

第四次挥手：当客户端收到这个FIN报文后，必须发出确认（即给服务器发ACK信息，但是它不相信网络，怕服务器收不到信息，他会进入TIME-WAIT状态，万一服务器没收到ACK消息它可以重传），ACK=1，ack number = w+1，seq = u+1，发送完之后进入TIME-WAIT状态，而当服务器收到这个ACK消息后，就正式关闭了tcp连接，处于CLOSED状态。而客户端在等待2MSL（最长报文段寿命）之后进入CLOSED状态（客户端等待了这么长时间后还没等到消息，它知道服务器已经关闭连接了，于是乎它自己也断开了）。

建立连接时，ACK和SYN可以放在一个报文中发送，而关闭连接时，被动关闭方可能还需要发送一些数据后，再发送FIN报文表示同意现在可以关闭连接了，所以它这里的ACK报文和FIN报文多数情况下都是分开发送的。

第一点原因是为了保证被动关闭方可以进入CLOSED状态。MSL是最大报文段寿命，等待2MSL可以保证A发送的最后一个确认报文能被B接收，如果该报文丢失，B没有收到就会超时重传之前的FIN+ACK报文，而如果A在发送确认报文之后就立即释放连接就无法收到B超时重传的报文，因而也不会再一次发送确认报文段，B就无法正常进入CLOSED状态。

第二点原因是2MSL时间之后，本连接中的所有报文就都会从网络中消失，可以防止已失效连接的请求数据包与正常连接的请求数据包混淆而发生异常。

除此之外，TCP还设有一个保活计时器，用于解决客户端主机故障的问题，服务器每收到一次客户的数据就重新设置保活计时器，时间为2小时。如果2小时内没有收到就间隔75秒发送一次探测报文，连续10次都没有响应后就关闭连接。

1、 无法保证最后发送的ACK报文会一定被对方收到，所以需要重发可能丢失的ACK报文。

2、 关闭连接一段时间后可能会在相同的IP地址和端口建立新的连接，为了防止旧连接的重复分组在新连接已经终止后再现。2MSL足以让分组最多存活msl秒被丢弃。

• TCP是面向连接的协议，提供的是可靠传输，在收发数据前需要通过三次握手建立连接，使用ACK包对收发数据进行正确性检验。而UDP是无连接的协议，不管对方有没有收到或者收到的数据是否正确，减少了开销和发送数据之前的时延，所以速度更快。

• TCP保证数据的可靠传输，而UDP使用尽最大努力交付，即不保证可靠交付，因此主机不需要维持复杂的连接状态。

• TCP是面向字节流的，UDP是面向报文的。

• TCP是点到点的一对一通信，UDP支持一对一，一对多和多对多的交互通信。

• TCP提供流量控制和拥塞控制，而UDP没有。

1、 首先是域名解析，客户端使用DNS协议将URL解析为对应的IP地址

2、 然后建立TCP连接，客户端与服务器通过三次握手建立TCP连接

3、 接着是http连接，客户端向服务器发送http连接请求（http无需额外连接，直接通过已经建立的TCP连接发送）

4、 服务器对客户端发来的http请求进行处理，并返回相应

5、 客户端接收到http响应，将结果展示给用户

• 200-请求成功

• 301-资源（网页等）被永久转移到其他URL

• 404-请求的资源（网页等）不存在

• 500-内部服务器错误

• 400-请求无效

• 403-禁止访问

Http的请求方法包括GET，POST，PUT，DELETE四种基本方法。（四种方法中只有POST不是操作幂等性的，每次请求都有不同的URI（统一资源标志符））

1、 get方法不会修改服务器上的资源，它的查询是没有副作用的。而post有可能会修改服务器上的资源

2、 get可以保存为书签，可以用缓存来优化，而post不可以

3、 get请求附在url上，而post把参数附在http包的包体中

4、 浏览器和服务器一般对get方法所提交的url长度有限制，一般是1K或者2K，而对post方法所传输的参数大小限制为80k到4M不等

5、 post可以传输二进制编码的信息，get的参数一般只支持ASCII

操作系统（ Operating System，OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件。

• 进程管理
• 存储管理
• 设备管理
• 文件管理
• 作业管理

• 并发：指两个或多个事件在 同一时间间隔 内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。并行：指两个或多个事件在 同一时刻 同时发生。
• 共享：与并发一起成为最基本的特征，二者互为存在的条件
• 虚拟：是指把一个物理上的实体变为若干个逻辑上的对应物
• 异步：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进

从不同的角度，进程可以有不同的定义，比较典型的定义有：

• 进程是程序的一次执行过程。
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
• 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

线程是进程中执行运算的最小单位，是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程，同一进程中的多个线程之间可以并发执行。

• Linux理论上最多可以创建32768个进程，因为进程的pid是用pid_t来表示的，而pid_t的最大值是32768，所以理论上最多有32768个进程。

• 而进程最多可以创建的线程数是根据分配给调用栈的大小，以及操作系统（32位和64位不同）共同决定的。Linux32位下是300多个。

• 调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位
• 并发性：一个进程可以有多个线程，但是一个线程只能属于一个进程；进程之间可以并发执行，同一个进程的多个线程之间也可并发执行
• 拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源
• 系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销
• 崩溃的影响：进程之间不会相互影响；而一个线程崩溃会导致进程崩溃，从而影响同个进程里面的其他线程

线程是存在进程的内部，一个进程中可以有多个线程，一个线程只能存在一个进程中。同一进程的所有线程共享该进程的所有资源。

进程之间的通信方式主要有六种，包括管道，信号量，消息队列，信号，共享内存，套接字

管道：管道是半双工的，双方需要通信的时候，需要建立两个管道。管道的实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据：管道一段的进程顺序的将进程数据写入缓冲区，另一端的进程则顺序地读取数据，该缓冲区可以看作一个循环队列，读和写的位置都是自动增加的，一个数据只能被读一次，读出以后在缓冲区都不复存在了。当缓冲区读空或者写满时，有一定的规则控制相应的读进程或写进程是否进入等