后台开发面经

C++

virtual 关键字的作用、构造和析构函数能不能定义虚函数?为什么?

基类希望其派生类覆盖的函数,通常将其定义为虚函数,通过指针或引用调用虚函数时,会在运行时解析该调用,在这种情况下对象的动态类型有可能与静态类型不同。这便是 OOP 的核心思想:多态性。

构造函数不能为虚函数,而析构函数可以且常常是虚函数。

首先,虚函数的实现原理是:在定义具有虚函数的类或者继承类的继承的时候,会相应建立一个虚函数表 vtable,即每个类都对应一个虚函数表,而在定义类的对象的时候,每个对象都会有一个指向相应类的虚表指针 vptr,vptr 指向虚表的入口地址,在调用相应的虚函数的时候,根据该入口地址寻找对应的函数。

对于构造函数,其作用是在对象实例化的时候自动调用,对该对象进行初始化操作。前述中提到,虚函数是通过 vptr 来调用的,而调用构造函数的时候实例化并未完成,也就是说此时并不存在vptr,因而,无法使用 vptr 来调用构造函数。

另一方面,虚函数的调用是虚调用,通过在运行时查询虚函数表得到具体函数入口地址,相当于只需要有部分信息就可以调用该函数。然而定义具体类的对象的时候,需要明确指定对象类型,而且在定义子类对象的时候首先调用的是父类的构造函数然后才是调用子类构造函数,如果使用了虚函数,那么仅仅是调用子类构造函数并不能完成对象的初始化。

而对于析构函数,则需要定义为虚析构函数,防止内存泄露的发生。在继承的时候, 我们通常通过基类的指针来销毁对象,如果析构函数不为虚的话,就不能正确识别对象类型,从而不能正确销毁对象。

static 关键字修饰类的成员作用,和其他成员函数的区别?

当使用 static 修饰成员变量和成员函数时,表示该变量或函数属于一个类,而不是该类的某个实例化对象。

C++ 调用 C 的关键字 extern 的作用?

extern可以置于变量或者函数前,以标示变量或者函数的定义在别的文件中,提示编译器遇到此变量和函数时在其他模块中寻找其定义。此外extern也可用来进行链接指定。也就是说extern有两个作用,

  • 第一,当它与 “C” 一起连用时,如: extern "C" void fun(int a, int b); 则告诉编译器在编译 fun 这个函数名时按着 C 的规则去翻译相应的函数名而不是 C++ 的,C++ 的规则在翻译这个函数名时会把 fun 这个名字变得面目全非,可能是 fun@aBc_int_int#%$ 也可能是别的,这要看编译器的”脾气”了(不同的编译器采用的方法不一样),为什么这么做呢,因为 C++ 支持函数的重载。
  • 第二,当 extern 不与 “C” 在一起修饰变量或函数时,如在头文件中: extern int g_Int; 它的作用就是声明函数或全局变量的作用范围的关键字,其声明的函数和变量可以在本模块活其他模块中使用,记住它是一个声明不是定义!也就是说 B 模块(编译单元)要是引用模块(编译单元) A 中定义的全局变量或函数时,它只要包含 A 模块的头文件即可。在编译阶段,模块 B 虽然找不到该函数或变量,但它不会报错,它会在连接时从模块 A 生成的目标代码中找到此函数。

map 和 unodered_map 的区别,底层的实现

  • map:自动排序,底层数据结构为红黑树。
  • unoredered_map:乱序,底层数据结构为哈希表(开链法解决哈希冲突)。
    • 用一个 vector 来作为一个指针数组来存储节点的指针,_size 来保存当前哈希表中的有效元素个数。
    • 由于是 K/V 结构,所以选择一个 pair 的结构来存储 K/V。
    • vector 中的每一个元素都指向一个链表,所有节点中需要一个 next 域的指针来指向下一个节点(采用单链表表结构)。
    • 采用模板来实现哈希表可以存储任意数据类型的目的。
    • 使用了仿函数技术。

哈希冲突如何解决

  • 开放定址法
    • 线性探测再散列
    • 二次探测再散列
    • 伪随机探测再散列:增量序列伪随机
  • 再哈希法:同时构造多个不同的哈希函数
  • 开链(哈希桶)
  • 建立公共溢出区:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

C++ 的重载

  • 函数名字相同但形参列表不同,称之为函数重载(overloaded)
  • main 函数不能重载
  • 顶层 const 的形参和另一个没有顶层 const 不能区分,底层 const 则相反

C 程序的编译过程

编译过程

  1. 预处理(Preprocessing):预处理用于将所有的 #include 头文件以及宏定义替换成其真正的内容,预处理之后得到的仍然是文本文件,但文件体积会大很多。
  2. 编译(Compilation):这里的编译不是指程序从源文件到二进制程序的全部过程,而是指将经过预处理之后的程序转换成特定汇编代码 (assembly code) 的过程。
  3. 汇编(Assemble):将上一步的汇编代码转换成机器码(machine code),这一步产生的文件叫做目标文件,是二进制格式。
  4. 链接(Linking):符号解析和重定位,将程序每一个全局变量和全局函数的引用和符号表里的一个符号对应起来,重定位确定每一个模板模块的全局变量和函数在可执行文件内存空间的位置,将多个目标文以及所需的库文件 (.so等) 链接成最终的可执行文件 (executable file)。

C 程序的内存空间

在多任务操作系统中,每个进程都运行在一个属于自己的虚拟内存中,而虚拟内存被分为许多页,并映射到物理内存中,被加载到物理内存中的文件才能够被执行。这里我们主要关注程序被装载后的内存布局,其可执行文件包含了代码段,数据段,BSS段,堆,栈等部分,其分布如下图所示。

内存分布

  • 代码段(.text):用来存放可执行文件的机器指令。存放在只读区域,以防止被修改。
  • 只读数据段(.rodata):用来存放常量存放在只读区域,如字符串常量、全局 const 变量等。
  • 可读写数据段(.data):用来存放可执行文件中已初始化全局变量,即静态分配的变量和全局变量。
  • BSS 段(.bss):未初始化的全局变量和局部静态变量一般放在 .bss 的段里,以节省内存空间。
  • 堆:用来容纳应用程序动态分配的内存区域。当程序使用 malloc 或 new 分配内存时,得到的内存来自堆。堆通常位于栈的下方。
  • 栈:用于维护函数调用的上下文。栈通常分配在用户空间的最高地址处分配。
  • 动态链接库映射区:如果程序调用了动态链接库,则会有这一部分。该区域是用于映射装载的动态链接库。
  • 保留区:内存中受到保护而禁止访问的内存区域。

malloc/free 与 new/delete 的区别

  • malloc 与 free 是 C/C++ 语言的标准库函数,new/delete 是 C++ 的运算符。它们都可用于申请和释放动态内存。
  • 对于非内部数据类型的对象而言,用 malloc/free 无法满足动态对象的要求。对象在创建的同时要自动执行构造函数,对象在消亡之前要自动执行析构函数。由于 malloc/free 是库函数而不是运算符,不在编译器控制权限之内,不能够把执行构造函数和析构函数的任务强加于 malloc/free,因此C++ 语言需要一个能完成动态内存分配和初始化工作的运算符 new,和一个能完成清理与释放内存工作的运算符 delete。
  • new 可以认为是 malloc 加构造函数的执行。new 出来的指针是直接带类型信息的。而 malloc 返回的都是 void* 指针。new/delete 在实现上其实调用了 malloc/free 函数。
  • new 建立的是一个对象;malloc 分配的是一块内存。

析构函数的作用

释放对象使用的资源,并销毁非 static 成员。

堆和栈的区别

  1. 申请管理方式
    • 栈:由编译器自动管理,无需我们手工控制。
    • 堆:堆的申请和释放工作由程序员控制,容易产生内存泄漏。
  2. 申请后系统的响应
    • 栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。
    • 堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的 delete 语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。
  3. 申请大小的限制
    • 栈:在 Windows 下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在 Windows 下,栈的大小是 1 M(可修改),如果申请的空间超过栈的剩余空间时,将提示 overflow。因此,能从栈获得的空间较小。
    • 堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。
  4. 申请效率的比较
    • 栈由系统自动分配,速度较快。但程序员是无法控制的。
    • 堆是由 new 分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便。另外,在 Windows 下,最好的方式是用 VirtualAlloc 分配内存,它不是在堆,也不是在栈而是直接在进程的地址空间中保留一块内存,虽然用起来最不方便。但是速度快,也最灵活。
  5. 堆与栈中的存储内容
    • 栈:在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址,然后是函数的各个参数,在大多数的 C 编译器中,参数是由右往左入栈的,然后是函数中的局部变量。注意静态变量是不入栈的。当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续运行。
    • 堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。

总结:堆和栈相比,由于大量 new/delete 的使用,容易造成大量的内存碎片;并且可能引发用户态和核心态的切换,内存的申请,代价变得更加昂贵。所以栈在程序中是应用最广泛的,就算是函数的调用也利用栈去完成,函数调用过程中的参数,返回地址,ebp 和局部变量都采用栈的方式存放。所以,推荐大家尽量用栈,而不是用堆。虽然栈有如此众多的好处,但是向堆申请内存更加灵活,有时候分配大量的内存空间,还是用堆好一些。

重载 new 运算符:什么时候需要重载

  • 为了检测运用上的错误
  • 为了收集动态分配内存的使用统计信息
  • 为了增加分配和归还的速度
  • 为了降低缺省内存管理器带来的空间额外开销
  • 为了弥补缺省分配器中的非最佳齐位
  • 为了将相关对象成簇集中
  • 为了获得非传统的行为

  • lambda 的实质(编译器层面)

操作系统

大端小端的区别、应用以及如何判断大端小端?

低地址 --------------------> 高地址
0x12 | 0x34 | 0x56 | 0x78

  • 大端模式:Big-Endian 是指数据的高字节保存在内存的低地址中,而数据的低字节保存在内存的高地址中,这样的存储模式有点儿类似于把数据当作字符串顺序处理:地址由小向大增加,而数据从高位往低位放;这和我们的阅读习惯一致。

低地址 --------------------> 高地址
0x78 | 0x56 | 0x34 | 0x12

  • 小端模式:Little-Endian 是指数据的高字节保存在内存的高地址中,而数据的低字节保存在内存的低地址中,这种存储模式将地址的高低和数据位权有效地结合起来,高地址部分权值高,低地址部分权值低。

区别:大端小端没有谁优谁劣,各自优势便是对方劣势

  • 大端模式 :符号位的判定固定为第一个字节,容易判断正负。
  • 小端模式 :强制转换数据不需要调整字节内容,1、2、4字节的存储方式一样。

应用:一般操作系统都是小端,而通讯协议是大端的。

  • 常见 CPU 的字节序

    • Big Endian : PowerPC、IBM、Sun
    • Little Endian : x86、DEC
    • ARM既可以工作在大端模式,也可以工作在小端模式。
  • 常见文件的字节序

    • Big Endian:Adobe PS、JPEG、MacPaint
    • Little Endian:BMP、GIF、RTF

判断

  • 通过将 int 强制类型转换成 char 单字节,通过判断起始存储位置
1
2
3
4
5
6
7
8
9
10
bool IsBigEndian()
{
int a = 0x1234;
char b = *(char *)&a; //等于 取b等于a的低地址部分
if (b == 0x12)
{
return true;
}
return false;
}
  • 联合体 union 的存放顺序是所有成员都从低地址开始存放,利用该特性可以轻松地获得了 CPU 对内存采用 Little-endian 还是 Big-endian 模式读写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool IsBigEndian()
{
union NUM
{
int a;
char b;
}num;
num.a = 0x1234;
if (num.b == 0x12)
{
return true;
}
return false;
}

线程和进程的区别

进程是资源分配的基本单位;线程是独立调度的基本单位。

区别

Ⅰ 拥有资源

进程是资源分配的基本单位,但是线程不拥有资源,线程可以访问隶属进程的资源。

Ⅱ 调度

线程是独立调度的基本单位,在同一进程中,线程的切换不会引起进程切换,从一个进程内的线程切换到另一个进程中的线程时,会引起进程切换。

Ⅲ 系统开销

由于创建或撤销进程时,系统都要为之分配或回收资源,如内存空间、I/O 设备等,所付出的开销远大于创建或撤销线程时的开销。类似地,在进行进程切换时,涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置,而线程切换时只需保存和设置少量寄存器内容,开销很小。

Ⅳ 通信方面

进程间通信 (IPC) 需要进程同步和互斥手段的辅助,以保证数据的一致性。而线程间可以通过直接读/写同一进程中的数据段(如全局变量)来进行通信。

一个进程有 10 个线程,如果 down 掉一个线程会不会对其他的有影响?

有!因为线程没有自己单独的内存地址空间,所以一个线程挂掉会导致整个进程挂掉。

什么情况下会发生死锁,解决策略有哪些?

死锁的必要条件

  • 互斥:每个资源要么已经分配给了一个进程,要么就是可用的。
  • 占有和等待:已经得到了某个资源的进程可以再请求新的资源。
  • 不可抢占:已经分配给一个进程的资源不能强制性地被抢占,它只能被占有它的进程显式地释放。
  • 环路等待:有两个或者两个以上的进程组成一条环路,该环路中的每个进程都在等待下一个进程所占有的资源。

解决策略

  • 鸵鸟策略:忽略它。
  • 死锁检测与死锁恢复:不试图阻止死锁,而是当检测到死锁发生时,采取措施进行恢复。三种恢复手段:
    • 利用抢占恢复
    • 利用回滚恢复
    • 通过杀死进程恢复
  • 死锁预防:在程序运行之前预防发生死锁。
    • 破坏互斥条件
    • 破坏占有和等待条件
    • 破坏不可抢占条件
    • 破坏环路等待
  • 死锁避免:在程序运行时避免发生死锁。

用户态和内核态

  • 用户态:上层应用程序的活动空间,应用程序的执行必须依托于内核提供的资源。只能受限的访问内存, 且不允许访问外围设备. 占用 CPU 的能力被剥夺, CPU 资源可以被其他程序获取
  • 内核态:控制计算机的硬件资源,并提供上层应用程序运行的环境。CPU 可以访问内存所有数据, 包括外围设备, 例如硬盘, 网卡. CPU 也可以将自己从一个程序切换到另一个程序

用户态切换为内核态的三种情况

  1. 系统调用:为了使上层应用能够访问到这些资源,内核为上层应用提供访问的接口。系统调用的本质其实也是中断,相对于外围设备的硬中断,这种中断称为软中断。
  2. 异常事件: 当 CPU 正在执行运行在用户态的程序时,突然发生某些预先不可知的异常事件,这个时候就会触发从当前用户态执行的进程转向内核态执行相关的异常事件,典型的如缺页异常。
  3. 外围设备的中断:当外围设备完成用户的请求操作后,会向 CPU 发出中断信号,此时,CPU 就会暂停执行下一条即将要执行的指令,转而去执行中断信号对应的处理程序,如果先前执行的指令是在用户态下,则自然就发生从用户态到内核态的转换。

从触发方式和效果上来看,这三种切换方式是完全一样的,都相当于是执行了一个中断响应的过程。但是从触发的对象来看,系统调用是进程主动请求切换的,而异常和硬中断则是被动的。

执行一个系统调用时,OS 发生的过程,越详细越好

系统调用, 在 CPU 中的实现称之为陷阱指令 (Trap Instruction),工作流程如下:

  1. 用户态程序将一些数据值放在寄存器中, 或者使用参数创建一个堆栈(stack frame), 以此表明需要操作系统提供的服务.
  2. 用户态程序执行陷阱指令
  3. CPU 切换到内核态, 并跳到位于内存指定位置的指令, 这些指令是操作系统的一部分, 他们具有内存保护, 不可被用户态程序访问
  4. 这些指令称之为陷阱 (trap) 或者系统调用处理器 (system call handler). 他们会读取程序放入内存的数据参数, 并执行程序请求的服务
  5. 系统调用完成后, 操作系统会重置 CPU 为用户态并返回系统调用的结果

执行一个 IO 调用读/写文件,到把数据写进磁盘发生的所有过程,越详细越好

读文件

  1. 进程调用库函数向内核发起读文件请求;
  2. 内核通过检查进程的文件描述符定位到虚拟文件系统的已打开文件列表表项;
  3. 调用该文件可用的系统调用函数 read()
  4. read() 函数通过文件表项链接到目录项模块,根据传入的文件路径,在目录项模块中检索,找到该文件的 inode;
  5. 在 inode 中,通过文件内容偏移量计算出要读取的页;
  6. 通过 inode 找到文件对应的 address_space;
  7. 在 address_space 中访问该文件的页缓存树,查找对应的页缓存结点:
    • 如果页缓存命中,那么直接返回文件内容;
    • 如果页缓存缺失,那么产生一个页缺失异常,创建一个页缓存页,同时通过inode 找到文件该页的磁盘地址,读取相应的页填充该缓存页;重新进行第 7 步查找页缓存;
  8. 文件内容读取成功。

写文件

前 6 步和读文件一致,在 address_space 中查询对应页的页缓存是否存在:

  1. 如果页缓存命中,直接把文件内容修改更新在页缓存的页中。写文件就结束了。这时候文件修改位于页缓存,并没有写回到磁盘文件中去。
  2. 如果页缓存缺失,那么产生一个页缺失异常,创建一个页缓存页,同时通过inode 找到文件该页的磁盘地址,读取相应的页填充该缓存页。此时缓存页命中,进行第 7 步。
  3. 一个页缓存中的页如果被修改,那么会被标记成脏页。脏页需要写回到磁盘中的文件块。有两种方式可以把脏页写回磁盘:
    • 手动调用 sync() 或者 fsync() 系统调用把脏页写回
    • pdflush 进程会定时把脏页写回到磁盘
      同时注意,脏页不能被置换出内存,如果脏页正在被写回,那么会被设置写回标记,这时候该页就被上锁,其他写请求被阻塞直到锁释放。

  • 内核态的函数调用和用户态的函数调用有何区别?

  • 一个二进制文件从执行到打印结果操作系统做了什么(从切换(PCB、寄存器)、权限、内存(缺页异常、地址转化之类的)、磁盘(inode之类的)、用户态内核态之类的说了一遍,把还记着的操作系统知识全部编进去了)

  • 项目里如何设计缓存来减少不必要的 IO?

  • GDB 用过吗?怎么下断点,怎么追踪?死锁应该怎么调试?

    • GDB:UNIX及UNIX-like下的调试工具。
  • 查内存泄露用什么工具?

    • Leakdiag.

计算机网络

网络的 4 层结构?TCP协议属于哪一层?


五层协议

  • 应用层 :为特定应用程序提供数据传输服务,例如 HTTP、DNS 等。数据单位为报文。

  • 运输层 :提供的是进程间的通用数据传输服务。由于应用层协议很多,定义通用的运输层协议就可以支持不断增多的应用层协议。运输层包括两种协议:传输控制协议 TCP,提供面向连接、可靠的数据传输服务,数据单位为报文段;用户数据报协议 UDP,提供无连接、尽最大努力的数据传输服务,数据单位为用户数据报。TCP 主要提供完整性服务,UDP 主要提供及时性服务。

  • 网络层 :为主机间提供数据传输服务,而运输层协议是为主机中的进程提供服务。网络层把运输层传递下来的报文段或者用户数据报封装成分组。

  • 数据链路层 :网络层针对的还是主机之间的数据传输服务,而主机之间可以有很多链路,链路层协议就是为同一链路的主机提供服务。数据链路层把网络层传下来的分组封装成帧。

  • 物理层 :考虑的是怎样在传输媒体上传输数据比特流,而不是指具体的传输媒体。物理层的作用是尽可能屏蔽传输媒体和通信手段的差异,使数据链路层感觉不到这些差异。

TCP 和 UDP 的区别

  • 用户数据报协议 UDP(User Datagram Protocol)是无连接的,尽最大可能交付,没有拥塞控制,面向报文(对于应用程序传下来的报文不合并也不拆分,只是添加 UDP 首部),支持一对一、一对多、多对一和多对多的交互通信。
  • 传输控制协议 TCP(Transmission Control Protocol)是面向连接的,提供可靠交付,有流量控制,拥塞控制,提供全双工通信,面向字节流(把应用层传下来的报文看成字节流,把字节流组织成大小不等的数据块),每一条 TCP 连接只能是点对点的(一对一)。

TCP 和 UDP 的优缺点

  • TCP

    • 优点:可靠,稳定。TCP 的可靠体现在 TCP 在传递数据之前,会有三次握手来建立连接,而且在数据传递时,有确认、窗口、重传、拥塞控制机制,在数据传完后,会断开连接用来节约系统资源。
    • 缺点:慢,效率低,占用系统资源高,易被攻击。TCP 在传递数据之前,要先建连接,这会消耗时间,而且在数据传递时,确认机制、重传机制、拥塞控制机制等都会消耗大量的时间,而且要在每台设备上维护所有的传输连接,事实上,每个连接都会占用系统的 CPU、内存等硬件资源。 而且,因为 TCP 有确认机制、三次握手机制,这些也导致 TCP 容易被人利用,实现 DOS、DDOS、CC 等攻击。
    • 使用场景:当对网络通讯可靠性有要求的时候。比如:整个数据要准确无误的传递给对方,这往往用于一些要求可靠的应用,比如 HTTP、HTTPS、FTP 等传输文件的协议,POP、SMTP 等邮件传输的协议。 在日常生活中,常见使用 TCP 协议的应用如下: 浏览器,用的 HTTP;FlashFXP,用的 FTP;Outlook,用的POP、SMTP;Putty,用的 Telnet、SSH QQ 文件传输
  • UDP

    • 优点:快,比TCP稍安全。UDP 没有 TCP 的握手、确认、窗口、重传、拥塞控制等机制,UDP 是一个无状态的传输协议,所以它在传递数据时非常快。没有 TCP 的这些机制,UDP 较 TCP 被攻击者利用的漏洞就要少一些。但 UDP 也是无法避免攻击的,比如:UDP Flood攻击
    • 缺点:不可靠,不稳定。因为 UDP 没有 TCP 那些可靠的机制,在数据传递时,如果网络质量不好,就会很容易丢包。
    • 使用场景: 当对网络通讯可靠性要求不高的时候,要求网络通讯速度能尽量的快,这时就可以使用 UDP。 比如,日常生活中,常见使用U DP 协议的应用如下: QQ 语音、QQ 视频、TFTP、长视频等

UDP 如何实现可靠性传输

UDP 它不属于连接型协议,因而具有资源消耗小,处理速度快的优点,所以通常音频、视频和普通数据在传送时使用 UDP 较多,因为它们即使偶尔丢失一两个数据包,也不会对接收结果产生太大影响。

传输层无法保证数据的可靠传输,只能通过应用层来实现了。实现的方式可以参照 TCP 可靠性传输的方式,只是实现不在传输层,实现转移到了应用层。

实现确认机制、重传机制、窗口确认机制。

如果你不利用 Linux 协议栈以及上层 socket 机制,自己通过抓包和发包的方式去实现可靠性传输,那么必须实现如下功能:

  • 发送:包的分片、包确认、包的重发
  • 接收:包的调序、包的序号确认

目前有如下开源程序利用 UDP 实现了可靠的数据传输。分别为 RUDP、RTP、UDT。

  • RUDP 提供一组数据服务质量增强机制,如拥塞控制的改进、重发机制及淡化服务器算法等,从而在包丢失和网络拥塞的情况下, RTP 客户机(实时位置)面前呈现的就是一个高质量的 RTP 流。在不干扰协议的实时特性的同时,可靠 UDP 的拥塞控制机制允许 TCP 方式下的流控制行为。
  • 实时传输协议(RTP)为数据提供了具有实时特征的端对端传送服务,如在组播或单播网络服务下的交互式视频音频或模拟数据。应用程序通常在 UDP 上运行 RTP 以便使用其多路结点和校验服务;这两种协议都提供了传输层协议的功能。但是 RTP 可以与其它适合的底层网络或传输协议一起使用。如果底层网络提供组播方式,那么 RTP 可以使用该组播表传输数据到多个目的地。RTP 本身并没有提供按时发送机制或其它服务质量(QoS)保证,它依赖于底层服务去实现这一过程。 RTP 并不保证传送或防止无序传送,也不确定底层网络的可靠性。 RTP 实行有序传送, RTP 中的序列号允许接收方重组发送方的包序列,同时序列号也能用于决定适当的包位置,例如:在视频解码中,就不需要顺序解码
  • 基于UDP的数据传输协议(UDP-basedData Transfer Protocol,简称UDT)是一种互联网数据传输协议。UDT的主要目的是支持高速广域网上的海量数据传输,而互联网上的标准数据传输协议TCP在高带宽长距离网络上性能很差。顾名思义,UDT建于UDP之上,并引入新的拥塞控制和数据可靠性控制机制。UDT是面向连接的双向的应用层协议。它同时支持可靠的数据流传输和部分可靠的数据报传输。由于UDT完全在UDP上实现,它也可以应用在除了高速数据传输之外的其它应用领域,例如点到点技术(P2P),防火墙穿透,多媒体数据传输等等。

TCP 首部格式


  • 序号 :用于对字节流进行编号,例如序号为 301,表示第一个字节的编号为 301,如果携带的数据长度为 100 字节,那么下一个报文段的序号应为 401。

  • 确认号 :期望收到的下一个报文段的序号。例如 B 正确收到 A 发送来的一个报文段,序号为 501,携带的数据长度为 200 字节,因此 B 期望下一个报文段的序号为 701,B 发送给 A 的确认报文段中确认号就为 701。

  • 数据偏移 :指的是数据部分距离报文段起始处的偏移量,实际上指的是首部的长度。

  • 确认 ACK :当 ACK=1 时确认号字段有效,否则无效。TCP 规定,在连接建立后所有传送的报文段都必须把 ACK 置 1。

  • 同步 SYN :在连接建立时用来同步序号。当 SYN=1,ACK=0 时表示这是一个连接请求报文段。若对方同意建立连接,则响应报文中 SYN=1,ACK=1。

  • 终止 FIN :用来释放一个连接,当 FIN=1 时,表示此报文段的发送方的数据已发送完毕,并要求释放连接。

  • 窗口 :窗口值作为接收方让发送方设置其发送窗口的依据。之所以要有这个限制,是因为接收方的数据缓存空间是有限的。

TCP 三次握手,四次挥手的过程?最后等待关闭连接要多长时间?

三次握手


假设 A 为客户端,B 为服务器端。

  • 首先 B 处于 LISTEN(监听)状态,等待客户的连接请求。

  • A 向 B 发送连接请求报文,SYN=1,ACK=0,选择一个初始的序号 x。

  • B 收到连接请求报文,如果同意建立连接,则向 A 发送连接确认报文,SYN=1,ACK=1,确认号为 x+1,同时也选择一个初始的序号 y。

  • A 收到 B 的连接确认报文后,还要向 B 发出确认,确认号为 y+1,序号为 x+1。

  • B 收到 A 的确认后,连接建立。

三次握手的原因

第三次握手是为了防止失效的连接请求到达服务器,让服务器错误打开连接。

客户端发送的连接请求如果在网络中滞留,那么就会隔很长一段时间才能收到服务器端发回的连接确认。客户端等待一个超时重传时间之后,就会重新请求连接。但是这个滞留的连接请求最后还是会到达服务器,如果不进行三次握手,那么服务器就会打开两个连接。如果有第三次握手,客户端会忽略服务器之后发送的对滞留连接请求的连接确认,不进行第三次握手,因此就不会再次打开连接。

四次挥手


以下描述不讨论序号和确认号,因为序号和确认号的规则比较简单。并且不讨论 ACK,因为 ACK 在连接建立之后都为 1。

  • A 发送连接释放报文,FIN=1。

  • B 收到之后发出确认,此时 TCP 属于半关闭状态,B 能向 A 发送数据但是 A 不能向 B 发送数据。

  • 当 B 不再需要连接时,发送连接释放报文,FIN=1。

  • A 收到后发出确认,进入 TIME-WAIT 状态,等待 2 MSL(最大报文存活时间)后释放连接。

  • B 收到 A 的确认后释放连接。

四次挥手的原因

客户端发送了 FIN 连接释放报文之后,服务器收到了这个报文,就进入了 CLOSE-WAIT 状态。这个状态是为了让服务器端发送还未传送完毕的数据,传送完毕之后,服务器会发送 FIN 连接释放报文。

TIME_WAIT

客户端接收到服务器端的 FIN 报文后进入此状态,此时并不是直接进入 CLOSED 状态,还需要等待一个时间计时器设置的时间 2MSL。这么做有两个理由:

  • 确保最后一个确认报文能够到达。如果 B 没收到 A 发送来的确认报文,那么就会重新发送连接释放请求报文,A 等待一段时间就是为了处理这种情况的发生。

  • 等待一段时间是为了让本连接持续时间内所产生的所有报文都从网络中消失,使得下一个新的连接不会出现旧的连接请求报文。

TCP 有哪些状态,CLOSED 状态出现在什么时候?

TCP 状态

全部共 11 种状态。

  • 客户端独有的:
    • SYN_SENT
    • FIN_WAIT1
    • FIN_WAIT2
    • CLOSING
    • TIME_WAIT
  • 服务器独有的:
    • LISTEN
    • SYN_RCVD
    • CLOSE_WAIT
    • LAST_ACK
  • 共有的
    • CLOSED
    • ESTABLISHED

客户端 TCP 状态迁移:
CLOSED -> SYN_SENT -> ESTABLISHED -> FIN_WAIT_1 -> FIN_WAIT_2 -> TIME_WAIT -> CLOSED

服务器 TCP 状态迁移:
CLOSED -> LISTEN -> SYN_RCVD -> ESTABLISHED -> CLOSE_WAIT -> LAST_ACK -> CLOSED

TCP 用了哪些措施保证其可靠性

  • 连接管理:TCP 是面向连接的,三次握手和四次挥手都是为了保证本次数据传送的可靠性
  • 序号:TCP 是面向字节流的,它对每一个字节都进行了编号,保证数据段的按序到达
  • 确认应答机制:TCP 通过确认应答机制实现可靠的数据传输。在 TCP 的首部中有一个标志位——ACK,此标志位表示确认号是否有效。接收方对于按序到达的数据会进行确认,当标志位 ACK = 1 时确认首部的确认字段有效。进行确认时,确认号的值表示这个值之前的数据都已经按序到达了。而发送方如果收到了已发送的数据的确认报文,则继续传输下一部分数据;而如果等待了一定时间还没有收到确认报文就会启动重传机制。
  • 超时重传机制:主机A发送给主机B数据报后一段时间内如果没有收到主机B对应的确认报文,就认为这一个或者这几个数据报都丢失了,即触发重传机制,重新发送没有被确认的报文。
  • 流量控制:接收端处理数据的速度是有限的,如果发送方发送数据的速度过快,导致接收端的缓冲区满,而发送方继续发送,就会造成丢包,继而引起丢包重传等一系列连锁反应。 因此 TCP 中引入了流量控制机制,意思就是根据接收端处理数据的能力来控制发送端发送数据的速度。
  • 拥塞控制:如果网络出现拥塞,分组将会丢失,此时发送方会继续重传,从而导致网络拥塞程度更高。因此当出现拥塞时,应当控制发送方的速率。这一点和流量控制很像,但是出发点不同。流量控制是为了让接收方能来得及接收,而拥塞控制是为了降低整个网络的拥塞程度。TCP 主要通过四个算法来进行拥塞控制:慢开始、拥塞避免、快重传、快恢复。

http 100 206 304 是什么? 304 中 xxxxx 的 header 有什么作用?

  • 100 Continue :表明到目前为止都很正常,客户端可以继续发送请求或者忽略这个响应。
  • 206 Partial Content :表示客户端进行了范围请求,响应报文包含由 Content-Range 指定范围的实体内容。
  • 304 Not Modified :如果请求报文首部包含一些条件,例如:If-Match,If-Modified-Since,If-None-Match,If-Range,If-Unmodified-Since,如果不满足条件,则服务器会返回 304 状态码。

HTTP/2.0了解吗?做了什么优化处理?

HTTP/1.x 缺陷

HTTP/1.x 实现简单是以牺牲性能为代价的:

  • 客户端需要使用多个连接才能实现并发和缩短延迟;
  • 不会压缩请求和响应首部,从而导致不必要的网络流量;
  • 不支持有效的资源优先级,致使底层 TCP 连接的利用率低下。

HTTP/2.0 优化

(1) 二进制分帧层

HTTP/2.0 将报文分成 HEADERS 帧和 DATA 帧,它们都是二进制格式的。

在通信过程中,只会有一个 TCP 连接存在,它承载了任意数量的双向数据流(Stream)。

  • 一个数据流(Stream)都有一个唯一标识符和可选的优先级信息,用于承载双向信息。
  • 消息(Message)是与逻辑请求或响应对应的完整的一系列帧。
  • 帧(Frame)是最小的通信单位,来自不同数据流的帧可以交错发送,然后再根据每个帧头的数据流标识符重新组装。

(2) 服务端推送

HTTP/2.0 在客户端请求一个资源时,会把相关的资源一起发送给客户端,客户端就不需要再次发起请求了。例如客户端请求 page.html 页面,服务端就把 script.js 和 style.css 等与之相关的资源一起发给客户端。

(3) 首部压缩

HTTP/1.1 的首部带有大量信息,而且每次都要重复发送。

HTTP/2.0 要求客户端和服务器同时维护和更新一个包含之前见过的首部字段表,从而避免了重复传输。

不仅如此,HTTP/2.0 也使用 Huffman 编码对首部字段进行压缩。

SACK 和 MSS 这两个东西了解过吗?

  • SACK:SACK(Selective ACK) 是 TCP 选项,它使得接收方能告诉发送方哪些报文段丢失,哪些报文段重传了,哪些报文段已经提前收到等信息。根据这些信息 TCP 就可以只重传哪些真正丢失的报文段。需要注意的是只有收到失序的分组时才会可能会发送 SACK,TCP 的 ACK 还是建立在累积确认的基础上的。也就是说如果收到的报文段与期望收到的报文段的序号相同就会发送累积的 ACK,SACK 只是针对失序到达的报文段的。SACK 包括了两个 TCP 选项,一个选项用于标识是否支持 SACK,是在 TCP 连接建立时发送;另一种选项则包含了具体的 SACK 信息。当我们接收到 ACK 的时候,我们会判断 SACK 段,如果包含 SACK 段的话,我们就要进行处理。
  • MSS:最大报文段长度 MSS 选项是 TCP 协议定义的一个选项,MSS 选项用于在TCP 连接建立时,收发双方协商通信时每一个报文段所能承载的最大数据长度。

  • 如何完全消除 time await?

    • 当初回答的时候设置属性和reuse都是判错的,要求从最后挥手的阶段开始分析
  • 怎么样设计一个比较好的函数完全读出一个 socket 的所有数据

算法题

(1) 二叉树两个节点之间距离

假设 lca 是两个节点的最低公共祖先节点:
$Dist(n_1,n_2) = Dist(root,n_1) + Dist(root,n_2) - 2 \cdot Dist(root,lca)$


  • 一个不知道头节点的单链表,如何在 p 节点前插入一个节点?

  • 1 亿个数字取 Top K。分成多个小文件,用小跟堆,堆排取小文件 Top k。之后再用外排或者继续堆排取所有的 Top k。

  • 1000w个整数排序,范围0到100w,8g内存

  • 非递归完成二叉树的先序遍历

  • 实现查询链表的倒数第1000个节点

  • 1000万个关键字,每个关键字小于等于50字节,求前K个热词,内存为1M

  • 无向图两点之间最小跳数(深度优先)

  • 数字数组中最长连续递增序列

  • 100W个无序数中是否包含给出的K个元素

  • 100W个数字中前K大的数字

  • 两个 1T 文件使用 4G 内存比较相似度

  • 对单词进行排序,比如 aa cee ee bb a 排序过后为 a aa bb cee ee

  • 反转链表

数据库

  • 数据库有啥索引,区别是什么,哪个插入快?为什么?你刚才提到了 B+Tree 索引,介绍一下B TREE 和 B+TREE,他们的区别是啥?
  • 左连接

Linux

  • Linux 下改变文件权限的命令有哪些?

  • 硬链接和软链接的区别?

  • Linux 下查看程序内存状况

    • top 指令可以查看按内存大小排序的查询内存状况,或者查看 /proc/pid/status 文件,这个文件会记录进程 id 所代表的进程的内存状态
  • Linux 统计文本中每行第二个字段的和(awk搞定)