总结总结笔试不会的题

发表于 更新于 分类于
失败不是什么丢人的事情，从失败中全无收获才是。

非科班找工作，计算机基础问啥啥也不会啊，只能啃书啃视频，一样一样总结咯。

强烈推荐这份Git资料，作者非常良心。

https://github.com/CyC2018/CS-Notes

在线阅读更清爽：https://cyc2018.github.io/CS-Notes/#/

程序设计

排序算法

方法 平均 最坏 最好 空间复杂度 稳定性
插入排序 O(n^2^) O(n^2^) O(n) O(1) 稳定
希尔排序 O(n^1/3^) O(n^2^) O(n) O(1) 不稳定
选择排序 O(n^2^) O(n^2^) O(n) O(1) 不稳定
冒泡排序 O(n^2^) O(n^2^) O(n) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(n^2^) O(n) O(nlogn) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定

稳定性的意义

1、如果只是简单的进行数字的排序，那么稳定性将毫无意义。
2、如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？）
3、如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
4、除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。

设计模式

学习材料和推荐博文：23种设计模式全面解析（超级详细）

单例模式

单例模式(Singleton Pattern，也称为单件模式)，使用最广泛的设计模式之一。其意图是保证一个类仅有一个实例，并提供一个访问它的全局访问点，该实例被所有程序模块共享。

定义：

  1. 私有化它的构造函数，以防止外界创建单例类的对象
  2. 使用类的私有静态指针变量指向类的唯一实例
  3. 使用一个公有的静态方法获取该实例

懒汉版：单例实例在第一次被使用时才进行初始化，叫做延迟初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Singleton
{
private:
    static Singleton* instance;	// 私有静态指针
private:
    Singleton() {};	// 私有化构造函数
    ~Singleton() {};
    Singleton(const Singleton&);
    Singleton& operator=(const Singleton&);
public:
    static Singleton* getInstance(){
        if(instance == NULL){
            instance = new Singleton();
        }
        return instance;
    }
}

Lazy Singleton存在内存泄漏问题，解决办法：

  1. 使用智能指针
  2. 使用静态的嵌套类对象

STL相关

学习材料和推荐博文：STL教程：C++ STL快速入门（非常详细）

多线程

学习材料和推荐博文：秒杀多线程第一篇 多线程笔试面试题汇总

C/C++关键字

volatile 的作用

为应对编译器优化（release模式）出现的问题：当遇到多线程编程时，变量的值可能因为别的线程而改变，而寄存器的值不会相应改变，从而造成程序读取的值与实际的变量值不一致。举例来说，为了使读取变量时提高存储速度，编译器优化过程中把变量读到寄存器内，当以后再取时，直接从寄存器取；当变量在本线程改变时，变量值直接更新到寄存器。而当该变量被别的线程改变时，本线程相当于没有收到通知，造成信息不一致。

volatile是一个类型修饰符，用来修饰被不同线程访问和修改的变量。系统每次用到它的时候直接从对应的内存中提取，不走cache和寄存器。所以，volatile一般修饰多线程间被多个任务共享的变量和并行设备硬件寄存器等。

const 的作用

  1. 定义const常量
  2. 进行类型检查
  3. 定义意义确定的数字，比如const max=0xFFFF. 不变则已一变俱变。
  4. 保护被修饰的对象，防止意外修改
  5. 提示进行函数重载
  6. 相比于#define，const更加节省内存空间
  7. 提高程序效率，编译器不为普通const常量分配存储空间，而是将他们存在符号表中，没有存储与读内存操作，可以提高使用效率。

new/delete与malloc/free的区别

  1. new能够自动计算需要分配的内存空间，而malloc需要手工计算字节数；
  2. new与delete直接带具体类型的指针，malloc与free返回void类型的指针；
  3. new是类型安全的（类型错误会报错），而malloc不是；
  4. new一般由两步构成，分别是new操作和构造。new操作对应于malloc，但new操作可以重载，可以自定义内存分配策略，不做内存分配，甚至分配到非内存设备上，而malloc不行；
  5. new将调用构造函数，而malloc不能；delete将调用析构函数，而free不能；
  6. malloc/free需要<stdlib.h>，new和delete不需要头文件支持。

备注：free和delete之后，虽然释放了内存，但需要将指针指向NULL，否则会出现野指针的状况。

extern和export

为了访问其他代码文件中的变量或对象：

  • extern：普通类型（基本数据类、结构和类）
  • export：模板类型

explicit

关键字explicit可以阻止不应该允许的经过构造函数进行隐式转换的发生，声明为explicit的构造函数不能在隐式转换中使用。

异常处理try-catch-throw-finally

使用try{}catch{}语句捕获异常，把可能发生异常的代码放在try{}语句中，如果本级没有catch到，异常会向上一级传递，函数调用处如果没有捕获住，则向更高一层的调用者，一直没有直到main函数跳出，并导致程序异常终止。

catch的作用是捕获异常，finally不管代码是否有异常都执行。try中如果有return，仍然需要执行finally语句。该情况下：

  1. 执行return返回语句（return之后的语句内容），计算返回值，暂时存在一个临时变量中。
  2. 执行finally语句块。
  3. return原来已经计算得到的结果值。
  4. 如果finally中又调用return语句，则try中的return会被忽略覆盖。

回调函数

要定义和实现一个类的成员函数为回调函数需要做3件事：

  1. 声明
  2. 定义
  3. 设置触发条件：在函数中把回调函数名作为一个参数，以便系统调用。就是函数指针

指针和引用的区别

  1. 指针是一个变量，只不过这个变量存储的是一个地址，指向内存的一个存储单元；而引用跟原来的变量本质上是同一个东西，只不过是原变量的一个别名而已。
  2. 可以有const指针，但是没有const引用；
  3. 指针可以有多级，但是引用只能是一级。
  4. 指针的值可以为空，但是引用的值不能为NULL，并且引用在定义的时候必须初始化。
  5. 指针的值在初始化后可以改变，即指向其它的存储单元，而引用在进行初始化后就不会再改变了。
  6. “sizeof引用”得到的是所指向的变量(对象)的大小，而”sizeof指针”得到的是指针本身的大小；
  7. 指针和引用的自增(++)运算意义不一样；

结构体与类

C++类的大小计算

  • 首先，类大小的计算遵循结构体的对齐原则
  • 类的大小与普通数据成员有关，与成员函数和静态成员无关。即普通成员函数，静态成员函数，静态数据成员，静态常量数据成员均对类的大小无影响
  • 虚函数对类的大小有影响，是因为虚函数表指针带来的影响
  • 虚继承对类的大小有影响，是因为虚基表指针带来的影响
  • 空类的大小是一个特殊情况,空类的大小为1
  • 64位 int大小为4字节，指针大小为8字节。

已知String类定义，如何实现其函数体

已知String类定义

1
2
3
4
5
6
7
8
9
class String{
    public:
    		String(const char* str=NULL);	// 通用构造函数
    		String(const String &str);		// 拷贝构造函数
    		~String();						// 析构函数
    		String& operator=(const String& rhs);	// 赋值函数
    private:
    		char* m_data;					// 用于保存字符串
};

函数体实现代码如下：

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
39
40
41
42
43
44
45
#include <iostream>
using namespace std;

class String{
    public:
    		String(const char *str=NULL);	// 通用构造函数
    		String(const String& str);		// 拷贝构造函数
    		~String();						// 析构函数
    		String& operator=(const String& rhs);	// 赋值函数
    private:
    		char* m_data;					// 用于保存字符串
};

// 默认构造函数
String::String(const char* str){
    if(str==NULL){
        m_data = new char[1];
        m_data[0] = '\0';
    }else{
        m_data = new char[strlen(str)+1];
        strcpy(m_data, str);
    }
}
// 拷贝构造函数
String::String(const String& str){
    m_data = new char[strlen(str.m_data) + 1];
    strcpy(m_data, str.m_data);
}

// 析构函数
String::~String(){
    delete[] m_data;
    m_data = NULL;
}

// 赋值函数
String& String::operator=(const String& rhs){
    if(this==&rhs)
        return *this;	// 如果同一对象，直接返回
    delete[] m_data;
    // 拷贝构造 
    m_data = new char[strlen(rhs.m_data) + 1];
    strcpy(m_data, rhs.m_data);
    return *this;
}

内存分配

内存分配的形式

  • BBS段：存放程序中未初始化的全局数据和静态数据。BBS段术语静态内存分配，程序结束后静态变量资源由系统自动释放。
  • 数据段：存放程序中已经初始化的全局变量。数据段属于静态内存分配。
  • 代码段（文本段）：存放程序执行的代码和只读的常数变量，比如字符串常量。运行前已确认大小，通常只读。
  • 堆：存放进程运行中被动态分配的内存段，大小不固定，可扩张或缩减。堆向上增长。(小于2GB)
  • 栈：存放程序临时创建的局部变量，效率高，分配的内存容量有限。栈向下增长。（Win2MB,Linux8MB）

编译

编译和连接的区别

  • 编译：将预处理生成的文件，经过词法分析、语法分析、语义分析并经过优化后编译成若干个模块。即obj文件。
  • 链接：由链接程序将编译后形成的一组目标模块以及它所需要的库函数链接在一起，形成一个完整的载入模型，主要解决模块间的相互引用问题。分为：地址和内存分配、符号解析、重定位三个步骤。

C++和C兼容

extern “C”。

C++调用被C编译器编译后的函数，为什么要加extern “C”？ 为了支持重载，C++会转换函数名，但是C没有函数重载，函数名不变。如果不加区别，C++编译器找不到C的函数名，就无法调用。

面向对象

基本特征

除了抽象外

  • 封装：访问控制符

  • 继承：使用现有类的所有功能，而不重新编写原来的类，目的是为了进行代码复用和支持多态。

    • 实现继承：使用基类的属性和方法而无需额外编码
    • 可视继承：子窗体使用父窗体的外观和实现代码
    • 接口继承：仅使用属性和方法，具体实现滞后到子类进行实现。

    前两种为类继承，后一种为（对象组合->接口继承以及纯虚函数）。

  • 多态：一个实体同时具有多种形式，可以将父类对象设置成子对象的技术，父对象可以根据当前赋值给它的子对象的特性以不同的方式运作。

复制构造函数和赋值运算符的区别

  1. 复制构造函数生成新的类对象，赋值运算符不行（赋予的对象原来就有值）
  2. 由于复制构造函数是直接构造一个新的对象，初始化该对象时不用检验原对象是否和新对象相同。赋值运算符需要判断。
  3. 当类中有指针类型的成员变量时，一定要重写复制构造函数和赋值构造函数，不能使用默认的。

类成员的初始化顺序

类成员变量的初始化顺序只与变量在类中的声明顺序有关，与在构造函数中的初始化列表的顺序无关。同时，静态成员变量先于实例变量，父类成员变量先于子类成员变量，父类构造函数先于子类构造函数。

从全局看，变量的初始化顺序如下：

  1. 基类的静态变量或全局变量
  2. 派生类的静态变量或全局变量
  3. 基类的成员变量
  4. 派生类的成员变量

构造函数没有返回值，如何得知对象是否构造成功？

通知对象构造失败的唯一方法是在构造函数中抛出异常，抛出异常将导致对象的析构函数不被执行，当对象发生部分构造时，已经构造完毕的子对象将会逆序地被析构。

C++中的空类默认产生哪些成员函数

C++中空类默认会产生以下6个函数：

  1. 默认构造函数
  2. 复制构造函数
  3. 析构函数
  4. 赋值运算符重载函数
  5. 取址运算符重载函数
  6. const取址运算符重载函数
1
2
3
4
5
6
7
8
9
class Empty{
	public:
    	Empty();
    	Empty(const Empty& );
    	~Empty();
    	Empty& operator=(const Empty&);
    	Empty* operator&();
    	const Empty* operator&() const;
};

public、protected、private的区别是什么？

基类性质 继承性质 派生类形式
public public public
protected public protected
private public 不能访问
public protected protected
protected protected protected
private protected 不能访问
public private private
protected private private
private private 不能访问

C++有哪些情况只能用初始化列表而不能用赋值

  1. 当类中含有const（常量）、reference（引用）成员变量时，只能初始化，不能对它们进行赋值。常量不能被赋值，只能被初始化，所以必须在初始化列表中完成，C++的引用也一定要初始化，所以必须在初始化列表中完成。
  2. 基类的构造函数都需要初始化列表。构造函数的意思是先开辟空间然后为其赋值，只能算是赋值，不算初始化。
  3. 成员类型没有默认构造函数的类。

虚函数

什么是虚函数？

指向基类的指针在操作它的多态类对象时，会根据不同的类对象调用其相应的函数，这个函数就是虚函数。

虚函数用virtual修饰函数名。

虚函数的作用是在程序运行阶段动态地选择合适的成员函数，在定义了虚函数后，可以在基类的派生类中对虚函数进行重新定义。

在派生类中重新定义的函数应与虚函数具有相同的形参个数和形参类型，来实现统一的接口。如果派生类中没有对虚函数重新定义，则继承基类的虚函数。

虚函数的实现机制

虚函数是通过一张虚函数表（virtual table）来实现的。该表是一个类的虚函数的地址表，解决了继承、覆盖的问题，保证它能真实反映实际的函数。

在有虚函数的类的实例中，虚函数表被分配在实例的内存中，所以当父类的指针操作一个子类的时候，这张虚函数表就显得非常重要，它指明了实际所应该调用的函数。

C++的编译器能够保证虚函数表的指针存在与对象实例中最前面的位置，通过对象实例的地址的得到这张虚函数表，然后就可以遍历其中的函数指针，并调用相应的函数。

举例来说，

1
2
3
4
5
6
7
class Base
{
    public:
    	virtual void f() {cout << "Base::f" << endl;}
    	virtual void g() {cout << "Base::g" << endl;}
    	virtual void h() {cout << "Base::h" << endl;}
}
1
2
3
4
5
6
7
8
// 虚函数表的得到方式
typedef void(*Fun)(void);
Base b;
Fun pfun = NULL;
cout << "虚函数表地址：" << (int*)(&b) << endl;
cout << "虚函数表-第一个函数地址：" << (int*)*(int*)(&b) << endl;
pfun = (Fun)*((int)*(int*)(&b));
pfun();	// 运行第一个虚函数

具体怎么运行的呢？

应在构造函数中进行虚函数表的创建和虚函数指针的初始化。根据构造函数的调用顺序，在构造子类对象时，要先调用父类的构造函数，此时编译器只“看到了”父类，并不知道后面是否还有继承者，它初始化父类对象的虚函数表的指针，该虚函数表指针指向父类的虚函数表。当执行子类的构造函数时，子类对象的虚函数表指针被初始化，指向自身的虚函数表。

当编译器发现一个类中有虚函数，便会立即为此类生成虚函数表，虚函数表的各表项为指向对应虚函数的指针。编译器还会在此类中隐含插入一个指针vptr指向虚函数表。调用此类的构造函数时，在类的构造函数中，编译器会隐含执行vptr与table的关联代码，将vptr指向对应的vtable，将类与此类的vtable联系起来，另外，在调用类的构造函数时，指向基础类的指针此时已经变为指向具体类的this指针，这样依靠此this指针即可得到正确的vtable。

多继承

多继承情况下，派生类中有多个虚函数表，虚函数的排列方式和继承的顺序一致。

派生类重写函数将会覆盖所有虚函数表的同名内容。

派生类自定义新的徐哈书将会在第一个类的虚函数表后进行扩充。

C++如何实现多态

C++通过虚函数实现多态。虚函数的本质就是通过基类访问派生类定义的函数。

每一个含有虚函数的类，其实例对象内部都有一个虚函数表指针。

该虚函数表指针被初始化为本类的虚函数表的内存地址，所以在程序中，不管对象类型如何转换，但该对象内部的虚函数表指针是固定的，这样才能实现动态地对对象函数进行调用，这就是C++多态的原理。

纯虚函数

由于在很多情况下，基类中不能对虚函数给出有意义的实现，只能把函数的实现留给该类的派生类去做。此时，就可以将函数定义为纯虚函数，编译器要求存在若干派生的非抽象类，则在派生类中必须予以重载以实现多态性。

对于纯虚函数，编译器要求在派生类中予以重载以实现多态性。含有纯虚函数的类成为抽象类，抽象类不能生成对象。

纯虚函数永远不会被调用，它们主要用来统一管理子类对象。

C++多态种类

  1. 参数多态：采用参数化模板，通过给定不同的类型参数，使得一个结构有多种类型、模板。
  2. 引用多态：同样的操作可以用于一个类型及其子类型。
  3. 过载多态：指同一个名字在不同的上下文中有不同的类型。
  4. 强制多态：指把操作对象的类型强加以变换，以符合函数或操作符的要求。

什么函数不能声明为虚函数？

一个类中将所有的成员函数都尽可能地设置为虚函数总是有益的，但是设置虚函数需要注意以下5个方面的内容：

  1. 只有类的成员函数才能说明为虚函数。
  2. 静态成员函数不能为虚函数，因为调用静态成员函数不要实例，但调用虚函数需要从一个实例中指向虚函数表的指针以得到函数的地址，因此调用虚函数需要一个实例，两者相互矛盾。
  3. 内联函数不能为虚函数。
  4. 构造函数不能为虚函数。因为构造函数是在对象完全构造之前运行的，换句话说，运行析构函数前，对象还没有生成，谈不上动态类型，会出现矛盾。
  5. 析构函数可以为虚函数，而且通常声明为虚函数。

是否可以把每个函数都声明为虚函数

代价就是：每个虚函数的对象在内存中都必须维护一个虚函数表，产生系统开销。

C++中如何阻止一个类被实例化

C++中可以通过使用抽象类，或者将构造函数声明为private阻止一个类被实例化。

一般在什么时候将构造函数声明为private

要阻止编译器生成默认的复制构造函数的时候

什么时候编译器会生成默认的复制构造函数

只要自己没写，而程序需要，都会生成。

计算机网络

OSI七层模型和TCP/IP四层模型，每层列举2个协议

OSI七层模型及其包含的协议

  1. 物理层: 通过媒介传输比特,确定机械及电气规范,传输单位为bit，主要包括的协议为：IEE802.3 CLOCK RJ45
  2. 数据链路层: 将比特组装成帧和点到点的传递,传输单位为帧,主要包括的协议为MAC VLAN PPP
  3. 网络层：负责数据包从源到宿的传递和网际互连，传输单位为包,主要包括的协议为IP ARP ICMP
  4. 传输层：提供端到端的可靠报文传递和错误恢复，传输单位为报文,主要包括的协议为TCP UDP
  5. 会话层：建立、管理和终止会话，传输单位为SPDU，主要包括的协议为RPC NFS
  6. 表示层：对数据进行翻译、加密和压缩,传输单位为PPDU，主要包括的协议为JPEG ASII
  7. 应用层: 允许访问OSI环境的手段,传输单位为APDU，主要包括的协议为FTP HTTP DNS

TCP/IP四层模型

  1. 网络接口层：MAC VLAN
  2. 网络层:IP ARP ICMP
  3. 传输层:TCP UDP
  4. 应用层:HTTP DNS SMTP

TCP/IP

UDP协议报头和TCP协议报头

UDP

TCP

TCP保证可靠性

  1. 校验和

  2. 序列号

  3. 确认应答

  4. 重发控制

  5. 连接管理

    1. 三次握手
    2. 四次挥手

  6. TCP以段为单位发送数据

  7. 窗口控制

    1. 利用窗口控制提高速度：窗口大小指无需等待确认应答而可以继续发送数据的最大值。
    2. 窗口控制与重发控制

  8. 流控制：限流

  9. 拥塞控制如果把窗口定的很大，发送端连续发送大量的数据，可能会造成网络的拥堵（大家都在用网，你在这狂发，吞吐量就那么大，当然会堵），甚至造成网络的瘫痪。所以TCP在为了防止这种情况而进行了拥塞控制。

    慢启动：定义拥塞窗口，一开始将该窗口大小设为1，之后每次收到确认应答（经过一个rtt），将拥塞窗口大小*2。

    拥塞避免：设置慢启动阈值，一般开始都设为65536。拥塞避免是指当拥塞窗口大小达到这个阈值，拥塞窗口的值不再指数上升，而是加法增加（每次确认应答/每个rtt，拥塞窗口大小+1），以此来避免拥塞。

    将报文段的超时重传看做拥塞，则一旦发生超时重传，我们需要先将阈值设为当前窗口大小的一半，并且将窗口大小设为初值1，然后重新进入慢启动过程。

    快速重传：在遇到3次重复确认应答（高速重发控制）时，代表收到了3个报文段，但是这之前的1个段丢失了，便对它进行立即重传。

    然后，先将阈值设为当前窗口大小的一半，然后将拥塞窗口大小设为慢启动阈值+3的大小。

    这样可以达到：在TCP通信时，网络吞吐量呈现逐渐的上升，并且随着拥堵来降低吞吐量，再进入慢慢上升的过程，网络不会轻易的发生瘫痪。

HTTP

HTTP responce code

分类：

  • 1** 信息，服务器收到请求，需要请求者继续执行操作
  • 2** 成功，操作被成功接收并处理
  • 3** 重定向，需要进一步的操作以完成请求
  • 4** 客户端错误，请求包含语法错误或无法完成请求
  • 5** 服务器错误，服务器在处理请求的过程中发生了错误

常用状态码

  • 200 请求成功
  • 301 资源（网页等）被永久转移到其他URL
  • 404 请求的资源不存在
  • 500 内部服务器错误

GET/POST区别

  • GET在浏览器回退时是无害的，而POST会再次提交请求。
  • GET产生的URL地址可以被Bookmark，而POST不可以。
  • GET请求会被浏览器主动cache，而POST不会，除非手动设置。
  • GET请求只能进行url编码，而POST支持多种编码方式。
  • GET请求参数会被完整保留在浏览器历史记录里，而POST中的参数不会被保留。
  • GET请求在URL中传送的参数是有长度限制的，而POST么有。
  • 对参数的数据类型，GET只接受ASCII字符，而POST没有限制。
  • GET比POST更不安全，因为参数直接暴露在URL上，所以不能用来传递敏感信息。
  • GET参数通过URL传递，POST放在Request body中。

HTTP和HTTPS的区别，以及HTTPS的缺点

HTTP协议和HTTPS协议区别如下：

  1. HTTP协议是以明文的方式在网络中传输数据，而HTTPS协议传输的数据则是经过TLS加密后的，HTTPS具有更高的安全性
  2. HTTPS在TCP三次握手阶段之后，还需要进行SSL 的handshake，协商加密使用的对称加密密钥
  3. HTTPS协议需要服务端申请证书，浏览器端安装对应的根证书
  4. HTTP协议端口是80，HTTPS协议端口是443

HTTPS优点：

  • HTTPS传输数据过程中使用密钥进行加密，所以安全性更高
  • HTTPS协议可以认证用户和服务器，确保数据发送到正确的用户和服务器

HTTPS缺点：

  • HTTPS握手阶段延时较高：由于在进行HTTP会话之前还需要进行SSL握手，因此HTTPS协议握手阶段延时增加
  • HTTPS部署成本高：一方面HTTPS协议需要使用证书来验证自身的安全性，所以需要购买CA证书；另一方面由于采用HTTPS协议需要进行加解密的计算，占用CPU资源较多，需要的服务器配置或数目高

Socket和Socket编程

学习材料和推荐博文：C/C++ socket编程教程：1天玩转socket通信技术

https://github.com/CyC2018/CS-Notes/blob/master/notes/Socket.md

I/O模型（转）

一个输入操作通常包括两个阶段：

  • 等待数据准备好
  • 从内核向进程复制数据

对于一个套接字上的输入操作，第一步通常涉及等待数据从网络中到达。当所等待数据到达时，它被复制到内核中的某个缓冲区。第二步就是把数据从内核缓冲区复制到应用进程缓冲区。Unix的5种IO模型是：

  • 阻塞式 I/O
    应用进程被阻塞，直到数据从内核缓冲区复制到应用进程缓冲区中才返回。

    应该注意到，在阻塞的过程中，其它应用进程还可以执行，因此阻塞不意味着整个操作系统都被阻塞。因为其它应用进程还可以执行，所以不消耗 CPU 时间，这种模型的 CPU 利用率会比较高。

  • 非阻塞式 I/O
    应用进程执行系统调用之后，内核返回一个错误码。应用进程可以继续执行，但是需要不断的执行系统调用来获知 I/O 是否完成，这种方式称为轮询（polling）。

    由于 CPU 要处理更多的系统调用，因此这种模型的 CPU 利用率比较低。

  • I/O 复用
    （select 和 poll）使用 select 或者 poll 等待数据，并且可以等待多个套接字中的任何一个变为可读。这一过程会被阻塞，当某一个套接字可读时返回，之后再使用 recvfrom 把数据从内核复制到进程中。

    它可以让单个进程具有处理多个 I/O 事件的能力。又被称为 Event Driven I/O，即事件驱动 I/O。

    如果一个 Web 服务器没有 I/O 复用，那么每一个 Socket 连接都需要创建一个线程去处理。如果同时有几万个连接，那么就需要创建相同数量的线程。相比于多进程和多线程技术，I/O 复用不需要进程线程创建和切换的开销，系统开销更小。

  • 信号驱动式 I/O（SIGIO）
    应用进程使用 sigaction 系统调用，内核立即返回，应用进程可以继续执行，也就是说等待数据阶段应用进程是非阻塞的。内核在数据到达时向应用进程发送 SIGIO 信号，应用进程收到之后在信号处理程序中调用 recvfrom 将数据从内核复制到应用进程中。

    相比于非阻塞式 I/O 的轮询方式，信号驱动 I/O 的 CPU 利用率更高。

  • 异步 I/O（AIO）
    应用进程执行 aio_read 系统调用会立即返回，应用进程可以继续执行，不会被阻塞，内核会在所有操作完成之后向应用进程发送信号。

    异步 I/O 与信号驱动 I/O 的区别在于，异步 I/O 的信号是通知应用进程 I/O 完成，而信号驱动 I/O 的信号是通知应用进程可以开始 I/O。

这五种I/O模型的区别是：

  • 同步 I/O：将数据从内核缓冲区复制到应用进程缓冲区的阶段（第二阶段），应用进程会阻塞。
  • 异步 I/O：第二阶段应用进程不会阻塞。

同步 I/O 包括阻塞式 I/O、非阻塞式 I/O、I/O 复用和信号驱动 I/O ，它们的主要区别在第一个阶段。

非阻塞式 I/O 、信号驱动 I/O 和异步 I/O 在第一阶段不会阻塞。

数据传输方式

  • SOCK_STREAM 表示面向连接的数据传输方式。数据可以准确无误地到达另一台计算机，如果损坏或丢失，可以重新发送，但效率相对较慢。常见的 http 协议就使用 SOCK_STREAM 传输数据，因为要确保数据的正确性，否则网页不能正常解析。
  • SOCK_DGRAM 表示无连接的数据传输方式。计算机只管传输数据，不作数据校验，如果数据在传输中损坏，或者没有到达另一台计算机，是没有办法补救的。也就是说，数据错了就错了，无法重传。因为SOCK_DGRAM 所做的校验工作少，所以效率比 SOCK_STREAM 高。视频聊天和语音聊天就是用SOCK_DGRAM。备注：SOCK_DGRAM 没有想象中的糟糕，不会频繁的丢失数据，数据错误只是小概率事件。

IP地址和端口能够在广袤的互联网中定位到要通信的程序，协议和数据传输方式规定了如何传输数据，有了这些，两台计算机就可以通信了。

Socket程序演示

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 服务端
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>
#include <netinet/in.h>

int main(){
    // Windows下，需要加载Windows Socket的DLL，并且使用WSAStartup()函数进行初始化来指明版本
    // int WSAStartup(WORD wVersionRequested, LPWSADATA lpWSAData);
  
    // 创建套接字
    // AF_INET表示使用IPV4地址，
    // SOCK_STREAM表示使用面向连接的数据传输方式，IPPROTO_TCP表示使用TCP协议
    // Linux下SOCKET是一种文件，有文件描述符，socket返回int类型
    int serv_sock = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);
    // Windows下使用文件句柄概念，返回SOCKET类型，
    // SOCKET servSock = socket(PF_INET, SOCK_STREAM, IPPROTO_TCP);
    // 两者都是用write()/read()或者recv()/send()对进行IO操作
  

    //将套接字和IP、端口绑定
    struct sockaddr_in serv_addr;
    memset(&serv_addr, 0, sizeof(serv_addr));  //每个字节都用0填充
    serv_addr.sin_family = AF_INET;  //使用IPv4地址
    serv_addr.sin_addr.s_addr = inet_addr("127.0.0.1");  //具体的IP地址
    serv_addr.sin_port = htons(1234);  //端口
    // 将套接字serv_sock与特定的IP地址和端口进行绑定
    // socket函数确定了套接字的各种属性，
    // bind函数让套接字与特定的IP和端口对应起来，、客户端才能连接到该套接字
    bind(serv_sock, (struct sockaddr*)&serv_addr, sizeof(serv_addr));

    //进入监听状态，等待用户发起请求
    // listen是进入被动监听状态，指套接字一直处于“睡眠中”，指导客户端发起请求才能连接到该套接字
    listen(serv_sock, 20);

    //接收客户端请求
    struct sockaddr_in clnt_addr;
    socklen_t clnt_addr_size = sizeof(clnt_addr);
    // accept函数用来接受客户端请求，一旦执行到这里就会被阻塞（暂停运行），直到客户端发起请求
    int clnt_sock = accept(serv_sock, (struct sockaddr*)&clnt_addr, &clnt_addr_size);

    // 向套接字中写入数据就是向客户端发送数据
    char str[] = "Hello World!";
    write(clnt_sock, str, sizeof(str));
   
    // 关闭套接字
    // 跟普通文件操作一样，socket在使用完毕后也要close关闭
    // Windows中使用closesocket()
    close(clnt_sock);
    close(serv_sock);

    return 0;
}
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
// 客户端
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/socket.h>

int main(){
    //创建套接字
    int sock = socket(AF_INET, SOCK_STREAM, 0);

    //向服务器（特定的IP和端口）发起请求
    struct sockaddr_in serv_addr;
    memset(&serv_addr, 0, sizeof(serv_addr));  //每个字节都用0填充
    serv_addr.sin_family = AF_INET;  //使用IPv4地址
    serv_addr.sin_addr.s_addr = inet_addr("127.0.0.1");  //具体的IP地址
    serv_addr.sin_port = htons(1234);  //端口
    // 客户端通过connect向服务端发起请求，服务端的IP和端口保存在sockaddr_in结构体中
    // 直到服务器传回数据后，connect才运行结束
    connect(sock, (struct sockaddr*)&serv_addr, sizeof(serv_addr));
   
    //读取服务器传回的数据
    char buffer[40];
    // 从套接字文件读物数据
    read(sock, buffer, sizeof(buffer)-1);
   
    printf("Message form server: %s\n", buffer);
   
    //关闭套接字
    close(sock);

    return 0;
}

参数、函数说明

socket()函数创建套接字

socket() 函数用来创建套接字，确定套接字的各种属性。

1
int socket(int af, int type, int protocol);
  • af 为地址族（Address Family），也就是 IP 地址类型，常用的有 AF_INET 和 AF_INET6。AF 是“Address Family”的简写，INET是“Inetnet”的简写。AF_INET 表示 IPv4 地址，例如 127.0.0.1；AF_INET6 表示 IPv6 地址，例如 1030::C9B4:FF12:48AA:1A2B。也可以使用PF前缀，PF是“Protocol Family”的简写，它和AF是一样的。例如，PF_INET 等价于 AF_INET，PF_INET6 等价于 AF_INET6。
  • type 为数据传输方式，常用的有 SOCK_STREAM 和 SOCK_DGRAM.
  • protocol 表示传输协议，常用的有 IPPROTO_TCP 和 IPPTOTO_UDP，分别表示 TCP 传输协议和 UDP 传输协议。

bind()和connect()函数

服务器端要用 bind() 函数将套接字与特定的IP地址和端口绑定起来，只有这样，流经该IP地址和端口的数据才能交给套接字处理；而客户端要用 connect() 函数建立连接。

bind原型

1
2
int bind(int sock, struct sockaddr *addr, socklen_t addrlen);  //Linux
int bind(SOCKET sock, const struct sockaddr *addr, int addrlen);  //Windows
1
2
3
4
5
6
7
8
9
10
11
12
//创建套接字
int serv_sock = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);

//创建sockaddr_in结构体变量
struct sockaddr_in serv_addr;
memset(&serv_addr, 0, sizeof(serv_addr));  //每个字节都用0填充
serv_addr.sin_family = AF_INET;  //使用IPv4地址
serv_addr.sin_addr.s_addr = inet_addr("127.0.0.1");  //具体的IP地址
serv_addr.sin_port = htons(1234);  //端口

//将套接字和IP、端口绑定
bind(serv_sock, (struct sockaddr*)&serv_addr, sizeof(serv_addr));

我们使用 sockaddr_in 结构体定义信息，然后再强制转换为 sockaddr 类型，送给函数。是因为sockaddr_in 和 sockaddr大小一致，但是不方便直接给sockaddr赋值。

connect原型,含义与bind相同

1
2
int connect(int sock, struct sockaddr *serv_addr, socklen_t addrlen);  //Linux
int connect(SOCKET sock, const struct sockaddr *serv_addr, int addrlen);  //Windows

listen()和accept()函数

对于服务器端程序，使用 bind() 绑定套接字后，还需要使用 listen() 函数让套接字进入被动监听状态，再调用 accept() 函数，就可以随时响应客户端的请求了。

listen函数

1
2
int listen(int sock, int backlog);  //Linux
int listen(SOCKET sock, int backlog);  //Windows

sock 为需要进入监听状态的套接字，backlog 为请求队列的最大长度。所谓被动监听，是指当没有客户端请求时，套接字处于“睡眠”状态，只有当接收到客户端请求时，套接字才会被“唤醒”来响应请求。

请求队列 当套接字正在处理客户端请求时，如果有新的请求进来，套接字是没法处理的，只能把它放进缓冲区，待当前请求处理完毕后，再从缓冲区中读取出来处理。如果不断有新的请求进来，它们就按照先后顺序在缓冲区中排队，直到缓冲区满。这个缓冲区，就称为请求队列（Request Queue）。

缓冲区的长度（能存放多少个客户端请求）可以通过 listen() 函数的 backlog 参数指定，但究竟为多少并没有什么标准，可以根据你的需求来定，并发量小的话可以是10或者20。

如果将 backlog 的值设置为 SOMAXCONN，就由系统来决定请求队列长度，这个值一般比较大，可能是几百，或者更多。

当请求队列满时，就不再接收新的请求，对于 Linux，客户端会收到 ECONNREFUSED 错误，对于 Windows，客户端会收到 WSAECONNREFUSED 错误。

注意：listen() 只是让套接字处于监听状态，并没有接收请求。接收请求需要使用 accept() 函数。

accept() 函数

当套接字处于监听状态时，可以通过 accept() 函数来接收客户端请求

1
2
int accept(int sock, struct sockaddr *addr, socklen_t *addrlen);  //Linux
SOCKET accept(SOCKET sock, struct sockaddr *addr, int *addrlen);  //Windows

它的参数与 listen() 和 connect() 是相同的：sock 为服务器端套接字，addr 为 sockaddr_in 结构体变量，addrlen 为参数 addr 的长度，可由 sizeof() 求得。

accept() 返回一个新的套接字来和客户端通信，addr 保存了客户端的IP地址和端口号，而 sock 是服务器端的套接字，大家注意区分。后面和客户端通信时，要使用这个新生成的套接字，而不是原来服务器端的套接字。

最后需要说明的是：listen() 只是让套接字进入监听状态，并没有真正接收客户端请求，listen() 后面的代码会继续执行，直到遇到 accept()。accept() 会阻塞程序执行（后面代码不能被执行），直到有新的请求到来。

数据发送与接收

Linux 不区分套接字文件和普通文件，使用 write() 可以向套接字中写入数据，使用 read() 可以从套接字中读取数据。两台计算机之间的通信相当于两个套接字之间的通信，在服务器端用 write() 向套接字写入数据，客户端就能收到，然后再使用 read() 从套接字中读取出来，就完成了一次通信。

write()

1
ssize_t write(int fd, const void *buf, size_t nbytes);

fd 为要写入的文件的描述符，buf 为要写入的数据的缓冲区地址，nbytes 为要写入的数据的字节数。

write() 函数会将缓冲区 buf 中的 nbytes 个字节写入文件 fd，成功则返回写入的字节数，失败则返回 -1。

read()

1
ssize_t read(int fd, void *buf, size_t nbytes);

fd 为要读取的文件的描述符，buf 为要接收数据的缓冲区地址，nbytes 为要读取的数据的字节数。

read() 函数会从 fd 文件中读取 nbytes 个字节并保存到缓冲区 buf，成功则返回读取到的字节数（但遇到文件结尾则返回0），失败则返回 -1。

迭代服务器和客户端

像Web服务器那样一直接受客户端的请求呢？能，使用 while 循环即可。

需要注意的是：server.cpp 中调用 closesocket() 不仅会关闭服务器端的 socket，还会通知客户端连接已断开，客户端也会清理 socket 相关资源，所以 client.cpp 中需要将 socket() 放在 while 循环内部，因为每次请求完毕都会清理 socket，下次发起请求时需要重新创建。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 服务器
	bind(servSock, (SOCKADDR*)&sockAddr, sizeof(SOCKADDR));
    //进入监听状态
    listen(servSock, 20);
    //接收客户端请求
    SOCKADDR clntAddr;
    int nSize = sizeof(SOCKADDR);
    char buffer[BUF_SIZE] = {0};  //缓冲区
    while(1){
        SOCKET clntSock = accept(servSock, (SOCKADDR*)&clntAddr, &nSize);
        int strLen = recv(clntSock, buffer, BUF_SIZE, 0);  //接收客户端发来的数据
        send(clntSock, buffer, strLen, 0);  //将数据原样返回
        closesocket(clntSock);  //关闭套接字
        memset(buffer, 0, BUF_SIZE);  //重置缓冲区
    }
    //关闭套接字
    closesocket(servSock);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 客户端
    char bufSend[BUF_SIZE] = {0};
    char bufRecv[BUF_SIZE] = {0};
    while(1){
        //创建套接字
        SOCKET sock = socket(PF_INET, SOCK_STREAM, IPPROTO_TCP);
        connect(sock, (SOCKADDR*)&sockAddr, sizeof(SOCKADDR));
        //获取用户输入的字符串并发送给服务器
        printf("Input a string: ");
        gets(bufSend);
        send(sock, bufSend, strlen(bufSend), 0);
        //接收服务器传回的数据
        recv(sock, bufRecv, BUF_SIZE, 0);
        //输出接收到的数据
        printf("Message form server: %s\n", bufRecv);
     
        memset(bufSend, 0, BUF_SIZE);  //重置缓冲区
        memset(bufRecv, 0, BUF_SIZE);  //重置缓冲区
        closesocket(sock);  //关闭套接字
    }

scoket缓冲区

TCP套接字缓冲区

I/O缓冲区特性可整理如下：

  • I/O缓冲区在每个TCP套接字中单独存在；
  • I/O缓冲区在创建套接字时自动生成；
  • 即使关闭套接字也会继续传送输出缓冲区中遗留的数据；
  • 关闭套接字将丢失输入缓冲区中的数据。

阻塞模式

对于TCP套接字（默认情况下），当使用 write()/send() 发送数据时：

  1. 首先会检查缓冲区，如果缓冲区的可用空间长度小于要发送的数据，那么 write()/send() 会被阻塞（暂停执行），直到缓冲区中的数据被发送到目标机器，腾出足够的空间，才唤醒 write()/send() 函数继续写入数据。
  2. 如果TCP协议正在向网络发送数据，那么输出缓冲区会被锁定，不允许写入，write()/send() 也会被阻塞，直到数据发送完毕缓冲区解锁，write()/send() 才会被唤醒。
  3. 如果要写入的数据大于缓冲区的最大长度，那么将分批写入。
  4. 直到所有数据被写入缓冲区 write()/send() 才能返回。

这就是TCP套接字的阻塞模式。所谓阻塞，就是上一步动作没有完成，下一步动作将暂停，直到上一步动作完成后才能继续，以保持同步性。

TCP的粘包问题和数据的无边界性

这就是数据的“粘包”问题，客户端发送的多个数据包被当做一个数据包接收。也称数据的无边界性，read()/recv() 函数不知道数据包的开始或结束标志（实际上也没有任何开始或结束标志），只把它们当做连续的数据流来处理。

假设我们希望客户端每次发送一位学生的学号，让服务器端返回该学生的姓名、住址、成绩等信息，这时候可能就会出现问题，服务器端不能区分学生的学号。例如第一次发送 1，第二次发送 3，服务器可能当成 13 来处理，返回的信息显然是错误的。

TCP数据报结构和三次握手

数据报

数据报

  • 序号：Seq（Sequence Number）序号占32位，用来标识从计算机A发送到计算机B的数据包的序号，计算机发送数据时对此进行标记。
  • 确认号：Ack（Acknowledge Number）确认号占32位，客户端和服务器端都可以发送，Ack = Seq + 1。
  • 标志位
    • URG：紧急指针（urgent pointer）有效。
    • ACK：确认序号有效。
    • PSH：接收方应该尽快将这个报文交给应用层。
    • RST：重置连接。
    • SYN：建立一个新连接。
    • FIN：断开一个连接。

对英文字母缩写的总结：Seq 是 Sequence 的缩写，表示序列；Ack(ACK) 是 Acknowledge 的缩写，表示确认；SYN 是 Synchronous 的缩写，愿意是“同步的”，这里表示建立同步连接；FIN 是 Finish 的缩写，表示完成。

TCP三次握手和Socket中的建立流程

三次握手

  1. 客户端调用 socket() 函数创建套接字后，因为没有建立连接，所以套接字处于 CLOSED状态；服务器端调用 listen() 函数后，套接字进入 LISTEN状态，开始监听客户端请求。

  2. 当客户端调用 connect() 函数后，TCP协议会组建一个数据包，并设置 SYN 标志位，表示该数据包是用来建立同步连接的。

    同时生成一个随机数字 1000，填充“序号（Seq）”字段，表示该数据包的序号。完成这些工作，开始向服务器端发送数据包，客户端就进入了 SYN-SEND状态。

  3. 服务器端收到数据包，检测到已经设置了 SYN 标志位，就知道这是客户端发来的建立连接的“请求包”。服务器端也会组建一个数据包，并设置 SYN 和 ACK 标志位，SYN 表示该数据包用来建立连接，ACK 用来确认收到了刚才客户端发送的数据包。服务器生成一个随机数 2000，填充“序号（Seq）”字段。2000 和客户端数据包没有关系。

    服务器将客户端数据包序号（1000）加1，得到1001，并用这个数字填充“确认号（Ack）”字段。

    服务器将数据包发出，进入 SYN-RECV状态。

  4. 客户端收到数据包，检测到已经设置了 SYN 和 ACK 标志位，就知道这是服务器发来的“确认包”。客户端会检测“确认号（Ack）”字段，看它的值是否为 1000+1，如果是就说明连接建立成功。

    接下来，客户端会继续组建数据包，并设置 ACK 标志位，表示客户端正确接收了服务器发来的“确认包”。同时，将刚才服务器发来的数据包序号（2000）加1，得到 2001，并用这个数字来填充“确认号（Ack）”字段。

    客户端将数据包发出，进入 ESTABLISED状态，表示连接已经成功建立。

  5. 服务器端收到数据包，检测到已经设置了 ACK 标志位，就知道这是客户端发来的“确认包”。
    服务器会检测“确认号（Ack）”字段，看它的值是否为 2000+1，如果是就说明连接建立成功，服务器进入 ESTABLISED状态。

至此，客户端和服务器都进入了 ESTABLISED状态，连接建立成功，接下来就可以收发数据了。

TCP数据的传输过程

正常情况

传输过程

上图给出了主机A分2次（分2个数据包）向主机B传递200字节的过程。首先，主机A通过1个数据包发送100个字节的数据，数据包的 Seq 号设置为 1200。主机B为了确认这一点，向主机A发送 ACK 包，并将 Ack 号设置为 1301。

为了保证数据准确到达，目标机器在收到数据包（包括SYN包、FIN包、普通数据包等）包后必须立即回传ACK包，这样发送方才能确认数据传输成功。

此时 Ack 号为 1301 而不是 1201，原因在于 Ack 号的增量为传输的数据字节数。假设每次 Ack 号不加传输的字节数，这样虽然可以确认数据包的传输，但无法明确100字节全部正确传递还是丢失了一部分，比如只传递了80字节。因此按如下的公式确认 Ack 号：

Ack号 = Seq号 + 传递的字节数 + 1

与三次握手协议相同，最后加1是为了告诉对方要传递的Seq号。

数据包丢失情况

TCP套接字数据传输过程中发生错误

上图表示通过 Seq 1301 数据包向主机B传递100字节的数据，但中间发生了错误，主机B未收到。经过一段时间后，主机A仍未收到对于 Seq 1301 的ACK确认，因此尝试重传数据。
为了完成数据包的重传，TCP套接字每次发送数据包时都会启动定时器，如果在一定时间内没有收到目标机器传回的 ACK 包，那么定时器超时，数据包会重传。

上图演示的是数据包丢失的情况，也会有 ACK 包丢失的情况，一样会重传。

重传超时时间（RTO, Retransmission Time Out)

这个值太大了会导致不必要的等待，太小会导致不必要的重传，理论上最好是网络 RTT 时间，但又受制于网络距离与瞬态时延变化，所以实际上使用自适应的动态算法（例如 Jacobson 算法和 Karn 算法等）来确定超时时间。

往返时间（RTT，Round-Trip Time）表示从发送端发送数据开始，到发送端收到来自接收端的 ACK 确认包（接收端收到数据后便立即确认），总共经历的时延。

重传次数

TCP数据包重传次数根据系统设置的不同而有所区别。有些系统，一个数据包只会被重传3次，如果重传3次后还未收到该数据包的 ACK 确认，就不再尝试重传。但有些要求很高的业务系统，会不断地重传丢失的数据包，以尽最大可能保证业务数据的正常交互。

最后需要说明的是，发送端只有在收到对方的 ACK 确认包后，才会清空输出缓冲区中的数据。

TCP四次握手断开连接

断开连接

  1. 建立连接后，客户端和服务器都处于 ESTABLISED状态。
  2. 客户端发起断开连接的请求，客户端调用 close() 函数后，向服务器发送 FIN 数据包，进入 FIN_WAIT_1状态。FIN 是 Finish 的缩写，表示完成任务需要断开连接。
  3. 服务器收到数据包后，检测到设置了 FIN 标志位，知道要断开连接，于是向客户端发送“确认包”，进入 CLOSE_WAIT状态。
    注意：服务器收到请求后并不是立即断开连接，而是先向客户端发送“确认包”，告诉它我知道了，我需要准备一下才能断开连接。
  4. 客户端收到“确认包”后进入 FIN_WAIT_2状态，等待服务器准备完毕后再次发送数据包。
  5. 等待片刻后，服务器准备完毕，可以断开连接，于是再主动向客户端发送 FIN 包，告诉它我准备好了，断开连接吧。然后进入 LAST_ACK状态。
  6. 客户端收到服务器的 FIN 包后，再向服务器发送 ACK 包，告诉它你断开连接吧。然后进入 TIME_WAIT状态。
  7. 服务器收到客户端的 ACK 包后，就断开连接，关闭套接字，进入 CLOSED状态。

关于 TIME_WAIT 状态的说明

客户端最后一次发送 ACK包后进入 TIME_WAIT 状态，而不是直接进入 CLOSED 状态关闭连接，这是为什么呢？

TCP 是面向连接的传输方式，必须保证数据能够正确到达目标机器，不能丢失或出错，而网络是不稳定的，随时可能会毁坏数据，所以机器A每次向机器B发送数据包后，都要求机器B”确认“，回传ACK包，告诉机器A我收到了，这样机器A才能知道数据传送成功了。如果机器B没有回传ACK包，机器A会重新发送，直到机器B回传ACK包。

客户端最后一次向服务器回传ACK包时，有可能会因为网络问题导致服务器收不到，服务器会再次发送 FIN 包，如果这时客户端完全关闭了连接，那么服务器无论如何也收不到ACK包了，所以客户端需要等待片刻、确认对方收到ACK包后才能进入CLOSED状态。那么，要等待多久呢？

数据包在网络中是有生存时间的，超过这个时间还未到达目标主机就会被丢弃，并通知源主机。这称为报文最大生存时间（MSL，Maximum Segment Lifetime）。TIME_WAIT 要等待 2MSL 才会进入 CLOSED 状态。ACK 包到达服务器需要 MSL 时间，服务器重传 FIN 包也需要 MSL 时间，2MSL 是数据包往返的最大时间，如果 2MSL 后还未收到服务器重传的 FIN 包，就说明服务器已经收到了 ACK 包。

socket优雅地断开连接–shutdown()

调用 close()/closesocket() 函数意味着完全断开连接，即不能发送数据也不能接收数据，这种“生硬”的方式有时候会显得不太“优雅”。

1
2
int shutdown(int sock, int howto);  //Linux
int shutdown(SOCKET s, int howto);  //Windows

至于什么时候需要调用 shutdown() 函数，下节我们会以文件传输为例进行讲解。

close()/closesocket()和shutdown()的区别

  1. 确切地说，close() / closesocket() 用来关闭套接字，将套接字描述符（或句柄）从内存清除，之后再也不能使用该套接字，与C语言中的 fclose() 类似。应用程序关闭套接字后，与该套接字相关的连接和缓存也失去了意义，TCP协议会自动触发关闭连接的操作。
  2. shutdown() 用来关闭连接，而不是套接字，不管调用多少次 shutdown()，套接字依然存在，直到调用 close() / closesocket() 将套接字从内存清除。

默认情况下，close()/closesocket() 会立即向网络中发送FIN包，不管输出缓冲区中是否还有数据，而shutdown() 会等输出缓冲区中的数据传输完毕再发送FIN包。也就意味着，调用 close()/closesocket() 将丢失输出缓冲区中的数据，而调用 shutdown() 不会。

socket网络字节序+htons()函数以及大端序小端序

CPU向内存保存数据的方式有两种，假设在 0x20 号开始的地址中保存4字节 int 型数据 0x12345678

  • 大端序（Big Endian）：高位字节存放到低位地址（高位字节在前）。
    大端序
  • 小端序（Little Endian）：高位字节存放到高位地址（低位字节在前）。
    小端序

不同CPU保存和解析数据的方式不同（主流的Intel系列CPU为小端序），小端序系统和大端序系统通信时会发生数据解析错误。因此在发送数据前，要将数据转换为统一的格式——网络字节序（Network Byte Order）。网络字节序统一为大端序。

主机A先把数据转换成大端序再进行网络传输，主机B收到数据后先转换为自己的格式再解析。

htons() 函数用来将当前主机字节序转换为网络字节序，其中 h代表主机（host）字节序，n代表网络（network）字节序，s代表short，htons 是 h、to、n、s 的组合，可以理解为”将short型数据从当前主机字节序转换为网络字节序“。

常见的网络字节转换函数有：

  • htons()：host to network short，将short类型数据从主机字节序转换为网络字节序。
  • ntohs()：network to host short，将short类型数据从网络字节序转换为主机字节序。
  • htonl()：host to network long，将long类型数据从主机字节序转换为网络字节序。
  • ntohl()：network to host long，将long类型数据从网络字节序转换为主机字节序。

注意：为sockaddr_in成员赋值时需要显式地将主机字节序转换为网络字节序，而通过 write()/send() 发送数据时TCP协议会自动转换为网络字节序，不需要再调用相应的函数。

在socket中使用域名

客户端中直接使用IP地址会有很大的弊端，一旦IP地址变化（IP地址会经常变动），客户端软件就会出现错误。

而使用域名会方便很多，注册后的域名只要每年续费就永远属于自己的，更换IP地址时修改域名解析即可，不会影响软件的正常使用。

通过域名获取IP地址

域名仅仅是IP地址的一个助记符，目的是方便记忆，通过域名并不能找到目标计算机，通信之前必须要将域名转换成IP地址。

1
struct hostent *gethostbyname(const char *hostname);
1
2
3
4
5
6
7
struct hostent{
    char *h_name;// 官方域名（Official domain name）。官方域名代表某一主页
    char **h_aliases;  //别名，可以通过多个域名访问同一主机。同一IP地址可以绑定多个域名
    int  h_addrtype;  // 不仅支持 IPv4，还支持 IPv6，可以通过此成员获取IP地址的地址族
    int  h_length;  //保存IP地址长度。IPv4 的长度为4个字节，IPv6 的长度为16个字节。
    char **h_addr_list;  //通过该成员以整数形式保存域名对应的IP地址。对于用户较多的服务器，可能会分配多个IP地址给同一域名，利用多个服务器进行均衡负载。
}

理解UDP套接字

UDP 是非连接的传输协议，没有建立连接和断开连接的过程，它只是简单地把数据丢到网络中，也不需要ACK包确认。

UDP 传输数据就好像我们邮寄包裹，邮寄前需要填好寄件人和收件人地址，之后送到快递公司即可，但包裹是否正确送达、是否损坏我们无法得知，也无法保证。UDP 协议也是如此，它只管把数据包发送到网络，然后就不管了，如果数据丢失或损坏，发送端是无法知道的，当然也不会重发。

如果只考虑可靠性，TCP的确比UDP好。但UDP在结构上比TCP更加简洁，不会发送ACK的应答消息，也不会给数据包分配Seq序号，所以UDP的传输效率有时会比TCP高出很多，编程中实现UDP也比TCP简单。

UDP 的可靠性虽然比不上TCP，但也不会像想象中那么频繁地发生数据损毁，在更加重视传输效率而非可靠性的情况下，UDP是一种很好的选择。比如视频通信或音频通信，就非常适合采用UDP协议；通信时数据必须高效传输才不会产生“卡顿”现象，用户体验才更加流畅，如果丢失几个数据包，视频画面可能会出现“雪花”，音频可能会夹带一些杂音，这些都是无妨的。

与UDP相比，TCP的生命在于流控制，这保证了数据传输的正确性。

最后需要说明的是：TCP的速度无法超越UDP，但在收发某些类型的数据时有可能接近UDP。例如，每次交换的数据量越大，TCP 的传输速率就越接近于 UDP。

操作系统

推荐博文：《CPU与内存的那些事》

十一篇文章讲解了计算机系统的重要内容，补知识靠他了。

  • 1. CPU的等待有多久?
  • 2. CPU如何操作内存
  • 3. 主板芯片组与内存映射
  • 4. 计算机的引导过程
  • 5. 内核引导过程
  • 6. 内存地址转换与分段
  • 7. CPU的运行环, 特权级与保护
  • 8. Cache: 一个隐藏并保存数据的场所
  • 9. 剖析程序的内存布局
  • 10. 内核是如何管理内存的
  • 11. 页面缓存-内存与文件的那些事

进程与线程

进程与线程的区别

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，它是系统进行资源分配和调度的一个独立单位。线程是进程的一个实体，是CPU调度和分配的基本单位，线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源，但是它可以为同属一个进程的其他的线程共享进程所拥有的全部资源。

引入线程的优点：

  1. 易于调度；
  2. 提高并发性。通过线程可以方便有效地实现并发；
  3. 开销小。创建线程比创建进程要快，所需要的开销也更少；
  4. 有利于发挥多处理器的功能。通过创建多线程，每个线程都在一个处理器上运行，从而实现应用程序的并行，使每个处理器都得到充分运行。

区别

  1. 一个线程必定属于也只能属于一个进程，而一个进程可以拥有多个线程并且至少拥有一个进程；
  2. 属于一个进程的所有线程共享该进程的所有资源，包括打开的文件、创建的Socket等。不同的进程互相独立。
  3. 线程又被成为轻量级进程，进程有进程控制块，线程也有线程控制块。
  4. 进程是程序的一次执行，线程可以理解为程序中一段程序片段的执行。
  5. 每个进程都有独立的内存空间，而线程共享所属进程的内存空间。

线程同步的机制

  1. 互斥量（mutex）：为协调对一个共享资源的单独访问而设计，只有拥有互斥量的线程才有权限去访问系统的公共资源，因为互斥量只有一个。
  2. 临界区（critical section）：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
  3. 事件（event）：用来通知线程有一些事件已经发生，从而启动后继任务的开始。
  4. 信号量（semaphore）：为控制一个具有有限数量的用户资源而设计，允许多个线程在同一个时刻去访问同一个资源，但一般需要限制同一时刻访问此类资源的最大线程数目。

Linux进程间通信方式（IPC: Inter-Process Communication）

进程通信的目的是什么？

  1. 数据传输
  2. 共享数据
  3. 通知事件
  4. 进程控制

通信方式有哪些？

  1. 管道（pipe）流管道（s_pipe）,有名管道（FIFO）：数据传输
    管道半双工，流管道双工，有名管道克服管道没有名字。
  2. 信号量：共享资源
    本质就是一个计数器。
  3. 消息队列：数据传输
    消息队列是消息的链表，克服了信号传递信息少的问题。
  4. 信号：通知事件/进程控制
    主要作为进程间以及同一进程不同线程间的同步手段
  5. 共享内存：共享数据
  6. 套接字：数据传输
    可以跨进程，也可以跨机器。

并发（concurrency）和并行（parallelism）

  • 并发（concurrency）：指宏观上看起来两个程序在同时运行，比如说在单核CPU上的多任务。但是从微观上看两个程序的指令是交织着运行的，你的指令之间穿插着我的指令，我的指令之间穿插着你的，在单个周期内只运行了一个指令。这种并发并不能提高计算机的性能，只能提高效率。
  • 并行（parallelism）：指严格物理意义上的同时运行，比如多核CPU，两个程序分别运行在两个核上，两者之间互不影响，单个周期内每个程序都运行了自己的指令，也就是运行了两条指令。这样说来并行的确提高了计算机的效率。所以现在的CPU都是往多核方面发展。

调度算法

先来先服务和短作业优先

调度算法

内存管理

内存管理的方式

主流：段页式管理。

  1. 块式管理：把主存分为一大块一大块的，当所需的程序片段不在主存时就分配一块主存空间，把程序片段载入主存。比较浪费
  2. 页式管理：把主存分为一页一页的，每一页的空间要比一块一块的空间小很多，显然这种方法的空间利用率要比块式管理高很多。
  3. 段式管理：把主存分为一段一段的，每一段的空间又要比一页一页的空间小很多，这种方法在空间利用率上又比也是管理高很多，但是缺点就是一个程序片段可能会被分为几十段，这样很多时间就会被浪费在计算每一段的物理地址上。
  4. 段页式管理：结合了段式管理和页式管理的优点。把主存先分成若干段，每个段又分成若干页。段页式管理每取一数据，要访问3次内存。

分页和分段存储管理有何区别？

(1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。

(2) 页的大小固定且由系统决定；而段的长度却不固定，决定于用户所编写的程序。

(3) 分页的地址空间是一维的，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

虚拟内存

虚拟内存简称虚存，是计算机系统内存管理的一种技术。相对与物理内存而言，是假内存。使得应用程序认为它拥有连续可用的内存（一个连续完整的地址空间），允许程序员编写运行比实际系统拥有的内存大得多的程序，这使得许多大型软件项目能够在有限内存资源的系统上实现。

实际上是被分割成多个物理内存碎片，还有部分暂时存储在外部存储磁盘上，在需要时进行数据交换，虚拟内存的好处：

  1. 扩大地址空间，无论段式虚存，还是页式虚存，或段式虚存，寻址空间都比实际内存大。
  2. 内存保护。每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。
  3. 公平分配内存。每个进程都相当于有同样大小的虚存空间。
  4. 当进行需要通信室，可以采用虚拟内存来实现。

缺点：

  1. 需要建立很多数据结构，占用额外内存。
  2. 虚拟地址到物理地址的转换，增加了指令执行时间。
  3. 页面的换入换出需要磁盘IO，很耗时间。
  4. 如果一页中只有一部分数据，会浪费内存。

首次适应算法-最佳适应算法-最坏适应算法

题目

  • 首次适应算法（first-fit）：
    从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法的目的在于减少查找时间。
  • 最佳适应算法（best-fit）：
    从全部空闲区中找出能满足作业要求的，且大小最小的空闲分区，这种方法能使碎片尽量小。
  • 最差适应算法（worst-fit）：
    它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的节点大小趋于均匀。

缺页中断-FIFO、LRU、OPT三种置换算法

  • 最佳置换（OPT）
    置换以后不再被访问，或者在将来最迟才回被访问的页面，缺页中断率最低。但是该算法需要依据以后各业的使用情况，而当一个进程还未运行完成是，很难估计哪一个页面是以后不再使用或在最长时间以后才会用到的页面。所以该算法是不能实现的。但该算法仍然有意义，作为很亮其他算法优劣的一个标准。
  • 先进先出置换算法（First In First Out, FIFO)
    置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。但是该算法会淘汰经常访问的页面，不适应进程实际运行的规律，目前已经很少使用。
  • 最近最久未使用置换算法（Least Recently Used， LRU）
    置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。
    LRU算法普偏地适用于各种类型的程序，但是系统要时时刻刻对各页的访问历史情况加以记录和更新，开销太大，因此LRU算法必须要有硬件的支持。

用户编程接口

静态链接和动态链接的不同

静态链接就是把要调用的函数或者过程直接链接到可执行文件中，成为可执行文件的一部分。函数和代码就在exe中，缺点就是当多个程序调用相同函数时，内存中就会存在这个函数的多个拷贝，浪费了内存资源。

动态链接是相对于静态链接而言的，当当成如被载入内存时，在操作系统的管理下，才在应用程序与DLL之间建立链接关系，当要执行DLL中的函数时，根据链接的重定位信息，转为执行DLL的函数代码。

用户态和核心态

用户栈与内核栈

数据库

数据库事务

参考文章：彻底理解数据库事务

  • 事务(Transaction)，一般是指要做的或所做的事情。在计算机术语中是指访问并可能更新数据库中各种数据项的一个程序执行单元(unit)。在计算机术语中，事务通常就是指数据库事务。

  • 一个数据库事务通常包含对数据库进行读或写的一个操作序列。

    • 为数据库操作提供了一个从失败中恢复到正常状态的方法，同时提供了数据库即使在异常状态下仍能保持一致性的方法。
    • 当多个应用程序在并发访问数据库时，可以在这些应用程序之间提供一个隔离方法，以防止彼此的操作互相干扰。

    当一个事务被提交给了DBMS（数据库管理系统），则DBMS需要确保该事务中的所有操作都成功完成且其结果被永久保存在数据库中，如果事务中有的操作没有成功完成，则事务中的所有操作都需要被回滚，回到事务执行前的状态（要么全执行，要么全都不执行）;同时，该事务对数据库或者其他事务的执行无影响，所有的事务都好像在独立的运行。

    但在现实情况下，失败的风险很高。在一个数据库事务的执行过程中，有可能会遇上事务操作失败、数据库系统/操作系统失败，甚至是存储介质失败等情况。这便需要DBMS对一个执行失败的事务执行恢复操作，将其数据库状态恢复到一致状态（数据的一致性得到保证的状态）。为了实现将数据库状态恢复到一致状态的功能，DBMS通常需要维护事务日志以追踪事务中所有影响数据库数据的操作。

  • 特性（事务应该具有的4个属性）：

    • 原子性（Atomicity）：事务作为一个整体被执行，包含在其中的对数据库的操作要么全部被执行，要么都不执行。
    • 一致性（Consistency）：事务应确保数据库的状态从一个一致状态转变为另一个一致状态。一致状态的含义是数据库中的数据应满足完整性约束。
    • 隔离性（Isolation）：多个事务并发执行时，一个事务的执行不应影响其他事务的执行。
    • 持久性（Durability）：一个事务一旦提交，他对数据库的修改应该永久保存在数据库中。

    举例

    用一个常用的“A账户向B账号汇钱”的例子来说明如何通过数据库事务保证数据的准确性和完整性。熟悉关系型数据库事务的都知道从帐号A到帐号B需要6个操作：

    1、从A账号中把余额读出来（500）。
    2、对A账号做减法操作（500-100）。
    3、把结果写回A账号中（400）。
    4、从B账号中把余额读出来（500）。
    5、对B账号做加法操作（500+100）。
    6、把结果写回B账号中（600）。

    原子性：

    保证1-6所有过程要么都执行，要么都不执行。一旦在执行某一步骤的过程中发生问题，就需要执行回滚操作。 假如执行到第五步的时候，B账户突然不可用（比如被注销），那么之前的所有操作都应该回滚到执行事务之前的状态。

    一致性

    在转账之前，A和B的账户中共有500+500=1000元钱。在转账之后，A和B的账户中共有400+600=1000元。也就是说，数据的状态在执行该事务操作之后从一个状态改变到了另外一个状态。同时一致性还能保证账户余额不会变成负数等。

    隔离性

    在A向B转账的整个过程中，只要事务还没有提交（commit），查询A账户和B账户的时候，两个账户里面的钱的数量都不会有变化。
    如果在A给B转账的同时，有另外一个事务执行了C给B转账的操作，那么当两个事务都结束的时候，B账户里面的钱应该是A转给B的钱加上C转给B的钱再加上自己原有的钱。

    持久性

    一旦转账成功（事务提交），两个账户的里面的钱就会真的发生变化（会把数据写入数据库做持久化保存）！

    原子性与隔离行

    一致性与原子性是密切相关的,原子性的破坏可能导致数据库的不一致，数据的一致性问题并不都和原子性有关。
    比如刚刚的例子，在第五步的时候，对B账户做加法时只加了50元。那么该过程可以符合原子性，但是数据的一致性就出现了问题。

    因此，事务的原子性与一致性缺一不可。

SQL

SQL查询语句执行顺序

注意是执行顺序，而不是写法。写法如下，执行顺序已标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
--查询组合字段
(5)select (5-2) distinct(5-3) top(<top_specification>)(5-1)<select_list>
--连表
(1)from (1-J)<left_table><join_type> join <right_table> on <on_predicate>
        (1-A)<left_table><apply_type> apply <right_table_expression> as <alias>
        (1-P)<left_table> pivot (<pivot_specification>) as <alias>
        (1-U)<left_table> unpivot (<unpivot_specification>) as <alias>
--查询条件
(2)where <where_pridicate>
--分组
(3)group by <group_by_specification>
--分组条件
(4)having<having_predicate>
--排序
(6)order by<order_by_list>

脏读、幻读、不可重复读 + 事务隔离级别+SQL Server

  • 脏读：

    脏读是指在一个事务处理过程里读取了另一个未提交的事务中的数据。当一个事务正在多次修改某个数据，而在这个事务中这多次的修改都还未提交，这时一个并发的事务来访问该数据，就会造成两个事务得到的数据不一致。

  • 不可重复读：
    不可重复读是指在对于数据库中的某个数据，一个事务范围内多次查询却返回了不同的数据值，这是由于在查询间隔，被另一个事务修改并提交了。
    不可重复读和脏读的区别是，脏读是某一事务读取了另一个事务未提交的脏数据，而不可重复读则是读取了前一事务提交的数据。

  • 幻读：
    是指当事务不是独立执行时发生的一种现象，例如第一个事务对一个表中的数据进行了修改，这种修改涉及到表中的全部数据行。同时，第二个事务也修改这个表中的数据，这种修改是向表中插入一行新数据。那么，以后就会发生操作第一个事务的用户发现表中还有没有修改的数据行，就好象发生了幻觉一样。

隔离级别

隔离级别 脏读 不可重复读 幻读
未提交读（Read uncommitted） 可能 可能 可能
已提交读（Read committed） 不可能 可能 可能
可重复读（Repeatable read） 不可能 不可能 可能
可串行化（Serializable） 不可能 不可能 不可能
  • 未提交读(Read Uncommitted)：允许脏读，也就是可能读取到其他会话中未提交事务修改的数据
  • 提交读(Read Committed)：只能读取到已经提交的数据。Oracle等多数数据库默认都是该级别 (不重复读)
  • 可重复读(Repeated Read)：可重复读。在同一个事务内的查询都是事务开始时刻一致的，InnoDB默认级别。在SQL标准中，该隔离级别消除了不可重复读，但是还存在幻象读
  • 串行读(Serializable)：完全串行化的读，每次读都需要获得表级共享锁，读写相互都会阻塞

悲观锁和乐观锁

  • 悲观锁

    悲观锁，正如其名，它指的是对数据被外界（包括本系统当前的其他事务，以及来自外部系统的事务处理）修改持保守态度(悲观)，因此，在整个数据处理过程中，将数据处于锁定状态。 悲观锁的实现，往往依靠数据库提供的锁机制 （也只有数据库层提供的锁机制才能真正保证数据访问的排他性，否则，即使在本系统中实现了加锁机制，也无法保证外部系统不会修改数据）
    在数据库中，悲观锁的流程是：

    1. 在对任意记录进行修改前，先尝试为该记录加上排他锁（exclusive locking）。
    2. 如果加锁失败，说明该记录正在被修改，那么当前查询可能要等待或者抛出异常。 具体响应方式由开发者根据实际需要决定。
    3. 如果成功加锁，那么就可以对记录做修改，事务完成后就会解锁了。
    4. 其间如果有其他对该记录做修改或加排他锁的操作，都会等待我们解锁或直接抛出异常。

    优缺点：
    悲观并发控制实际上是“先取锁再访问”的保守策略，为数据处理的安全提供了保证。但是在效率方面，处理加锁的机制会让数据库产生额外的开销，还有增加产生死锁的机会；另外，在只读型事务处理中由于不会产生冲突，也没必要使用锁，这样做只能增加系统负载；还有会降低了并行性，一个事务如果锁定了某行数据，其他事务就必须等待该事务处理完才可以处理那行数

  • 乐观锁

    乐观锁（ Optimistic Locking ） 相对悲观锁而言，乐观锁假设认为数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会正式对数据的冲突与否进行检测，如果发现冲突了，则让返回用户错误的信息，让用户决定如何去做。

    相对于悲观锁，在对数据库进行处理的时候，乐观锁并不会使用数据库提供的锁机制。一般的实现乐观锁的方式就是记录数据版本。
    数据版本,为数据增加的一个版本标识。当读取数据时，将版本标识的值一同读出，数据每更新一次，同时对版本标识进行更新。当我们提交更新的时候，判断数据库表对应记录的当前版本信息与第一次取出来的版本标识进行比对，如果数据库表当前版本号与第一次取出来的版本标识值相等，则予以更新，否则认为是过期数据。

在乐观锁与悲观锁的选择上面，主要看下两者的区别以及适用场景就可以了。

1、乐观锁并未真正加锁，效率高。一旦锁的粒度掌握不好，更新失败的概率就会比较高，容易发生业务失败。

2、悲观锁依赖数据库锁，效率低。更新失败的概率比较低。

随着互联网三高架构（高并发、高性能、高可用）的提出，悲观锁已经越来越少的被使用到生产环境中了，尤其是并发量比较大的业务场景。

公平锁与非公平锁

太真实了，面试官问的专业名词听都没听过。

公平锁就是保障了多线程下各线程获取锁的顺序，先到的线程优先获取锁，而非公平锁则无法提供这个保障。

图转载自https://www.jianshu.com/p/f584799f1c77

公平锁与非公平锁

共享锁与排它锁

  • 共享锁【S锁】
    又称读锁，若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。这保证了其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改。
  • 排他锁【X锁】
    又称写锁。若事务T对数据对象A加上X锁，事务T可以读A也可以修改A，其他事务不能再对A加任何锁，直到T释放A上的锁。这保证了其他事务在T释放A上的锁之前不能再读取和修改A。

计算机视觉＆图像处理

  1. 相机标定和相机参数
    1. 相机外参 6 个参数：旋转矩阵3个，平移矩阵3个
    2. 相机内参：f, k, sx, sy, cx, cy
    3. 线阵相机的标定在《机器视觉算法与应用》P258.主要是考虑了运动状态。不做仔细研究了。
  2. 标定过程（机器视觉算法与应用P268）
    1. 标定板
      1. 书中和Halcon用的是圆形标定板：平面上有mxn个圆形标志点，标志点们外围有一个黑色矩形边界框，其中某个角落有一个方向标记，用于确定标定板的唯一方向。
      2. 张正友标定法用的是棋盘格
    2. 过程
      1. 利用黑色矩形框，将内部与背景区分
      2. 阈值操作分割，得到各个圆形标志区域
      3. 提取边缘，拟合为椭圆，最小外接四边形的中心为投影中心
    3. 计算
      1. 标定标记在世界坐标系中坐标为Mi,图像中坐标为mi，摄像机投影模型内外参c。标记要一一对应。用优化问题来求相机参数。但是求解参数过多，没有唯一解。其次，优化问题复杂，最好先用初始化参数进行初始化，比如出厂设置，平面坐标用尺子两个初始值。
        标定
      2. 容易出现没有唯一解，就要用多幅图像进行标定。同时为了使得参数准确度更高，所有图像中标定板的位置应该能够覆盖图像的四个角，主要是因为角落处镜头畸变最大，这样就可以得到经变系数k最准确的值。
        标定2

数学

  1. 置信区间计算

字节跳动面经整理

  1. https://www.nowcoder.com/discuss/241769
  2. https://www.nowcoder.com/discuss/238341?type=post&order=time&pos=&page=1&subType=2
  3. https://www.nowcoder.com/discuss/238308?type=post&order=time&pos=&page=1&subType=2
  4. https://www.nowcoder.com/discuss/235624?type=post&order=time&pos=&page=1&subType=2
  5. https://www.nowcoder.com/discuss/227379?type=post&order=time&pos=&page=1&subType=2
  6. https://www.nowcoder.com/discuss/207290?type=post&order=time&pos=&page=2&subType=2
  7. https://www.nowcoder.com/discuss/163590