面经


个人的 面试经验整理。

C++

C 和 C++ 的区别

说实话这是个比较宏大的问题。要考虑这个问题,首先得明白什么才算「区别」。就面向对象而言,C 中也可以实现封装(成员函数可以用函数指针代替,构造/析构函数可以用工厂函数代替)、继承(在结构体的最开始直接定义一个基类对象)、多态(可以自定义虚函数表),无非看着别扭了点就是了,所以这算不上「区别」。

我认为,只用 C 语言无法模拟出,或者人工模拟代价很大的 C++ 的特性,这才是能称之为「区别」。

  1. 确定性析构: 虽然 C 可以模拟析构函数,但很难保证每次都能够在一个对象生命周期即将结束时调用模拟的析构函数,搞不好就容易出 Bug。而 C++ 的析构函数则完美解决了这个问题,并且实现更加优雅,将「释放对象」这一行为交给编译器,同时基于此还将 RAII 哲学应用到了语言上,进一步产生了各种容器、智能指针、锁管理者这些标准库对象,不得不说析构函数是 C++ 的几大根基之一了;
  2. 右值和移动语义: 虽然 C 中可以通过「指针常量」模拟左值引用,但却无法实现对右值/匿名对象的「引用」(因为右值没有地址,无法被指针指向),函数调用中传入一个匿名的 struct 会涉及到数据拷贝,影响性能。而 C++11 之后引入了「右值」这一概念,同时加入了右值引用、万能引用、std::forwardstd::move 等内容;
  3. 模板: C++ 编译器会自动对模板类/函数生成相应的代码,C 想实现诸如 max()/swap() 这种函数代价就太大了。同时 C++ 还在模板的基础上引入了「模板元编程」之类的技巧,将一些计算提到编译期,提高了运行时性能;
  4. ...

说下 C++ 内存布局?以及堆和栈的区别?为什么不能只用其中一个?

具体可参考 C++ の 内存分配

C++ 的内存布局中,从低到高依次为代码区、常量存储区、全局存储区、堆区、栈区。

堆的地址从低到高增长,是程序员通过 new/delete 手动分配和释放的,其生命周期与整个程序相同。

栈的地址从高到低增长,由编译器自动管理分配,以栈帧(Frame)为单位,存放函数局部变量、函数参数值等。一旦函数结束,对应的栈帧也就被 pop,里面的变量生命周期也就结束了。

栈的优势在于将变量的管理交付给编译器,不需要麻烦程序员了;并且在栈上分配变量开销低——直接移动栈顶指针就好了。相比而言,在堆上分配内存还要涉及到不同的内存分配策略,开销就会很高。

而堆的优势在于延长变量的生命周期。试想一下如果只用栈,该如何实现树、链表这样的需要动态维护的数据结构?

整数除以 0 会发生什么?浮点数呢?

如果是直接以比如 1/0; 进行编码会报编译错误。

如果是将 0 存到变量中除以一个变量,那么通常会触发运行时错误。

如果是浮点数之间除以 0,则会生成一个 NAN

struct 和 class 的区别

具体可参考 C++ の OOP

主要区别在于默认访问权限、继承方式,以及 struct 不能用模板。

在类的不同函数中执行 delete this; 语句会发生什么?

delete this 除了释放上的内存,还会调用析构函数。

如果是在栈上分配的对象,调用相关函数会 crash。

如果是在析构函数中执行,则会导致栈溢出

而如果在成员函数中执行,则需要保证后续不会访问类的成员变量以及虚函数表,否则会导致段错误

如果是在构造函数中执行,则会导致未定义行为。因为此时对象未完全构造,可能导致资源泄漏或数据损坏,同时构造函数后续的任何访问将导致访问违规。

左值和右值的区别?

左值可以取地址并具有变量名。

剩下的都是右值,又称匿名对象,只存在于寄存器中,无法在内存中寻址,不具有持久性。

什么是右值引用(T&&)?

左值引用 T& 可以修改形参但无法用右值传值。

常量左值引用 const T& 可以用右值传值但无法在函数内部对形参进行修改。

可以选择在栈上开一个左值的内存然后赋予右值,再用前者,也就是 T& 传值,但存在拷贝开销。右值引用 T&& 能够解决这一问题——既可以传入右值,又可以修改形参。并在此基础上支持类的移动构造函数,以实现移动语义(转移所有权)。

右值引用绑定的对象为右值,其具有变量名,所以是左值。

拷贝构造和移动构造的区别?

前者相当于在内存中创建一个副本

如果成员对象中有指针,则存在潜在的浅拷贝的问题。

后者是在内存中转移数据所有权(被移动的对象失去底层数据,如指针置空),基于 std::move 和右值引用。

std::move 和 std::forward 的区别?

具体可参考 Effective Modern C++ Item23

std::move 仅仅做了个 become 右值引用的类型转换,并没有真正的「移动」。即

template <typename T>
typename remove_reference<T>::type&& move(T&& param) {
  return static_cast<remove_reference<T>::type&&>(param);
}

std::forward 仅仅是将实参转为对应的引用版本,适用于万能引用下类型不明确的情况。

std::move 中为什么要使用 remove_reference

为了防止「引用折叠」,导致传入左值时返回值被折叠为左值引用。

std::shared_ptr 和 std::unique_ptr 的异同?

具体可参考 C++11 の 智能指针

这两个都是智能指针,均满足 RAII 准则,在析构时自动释放堆上分配的内存。

shared ptr 为共享指针,允许拷贝构造,允许多个 shared ptr 指向同一块内存,经拷贝方式生成的 shared ptr 共享一个引用计数器,每引用一个对象计数器加 1;每释放一个对象计数器减 1。当计数器为 0 时该内存才会被释放。

可以通过 use_count() 函数获取引用计数值。

unique ptr 为独占指针,不允许拷贝构造,同时只能有一个 unique ptr 指向某块内存,只能通过移动语义来进行更改所有权。

std::shared_ptr 有什么缺陷?如何解决?

shared ptr 存在「循环引用」的问题,可以用 std::weak_ptr 解决。比如下面这段代码,分别有两个 shared ptr 指向 a 和 b 所在的内存空间,outPa/inPa 与 outPb/inPb 的计数器均为 2

func() 退出时,栈变量 outPa 和 outPb 结束生命周期,调用析构函数,分别使得 outPa/inPa 和 outPb/inPb 的计数值 -1。然而,类成员变量 inPa/inPb (的所有数据)还位于 a/b 所在的堆空间中,它们的计数器并没有归零,而是 1。那么永远得不到释放,这就造成了内存泄漏

循环引用
class B; class A { public: std::shared_ptr<B> inPb; }; class B { public: std::shared_ptr<A> inPa; } void func() { auto outPa = std::make_shared<A>(); // 视为指向堆空间 a auto outPb = std::make_shared<B>(); // 视为指向堆空间 b outPa->inPb = outPb; outPa->inPa = outPa; }

如果使用 std::weak_ptr<B> inPb 来代替 std::shared_ptr<B> inPb,则可以解决该问题。这是因为 weak ptr 并不影响 指向该内存的 shared ptr 的计数器,它只作为一个观测者,用于监测对应的空间是否被释放(通过 expired() 函数),同时提供了一个 lock() 函数来访问地址。根据这一特性,尽管 outPa/inPa 的计数器为 2,但是 outPb 的计数器为 1,那么其在函数退出后可以对 b 的内存进行释放,从而使 inPa 的计数器 counterA-=1,而 outPa 又因为函数退出而再次使计数器 counterA-=1,进而释放 a 的内存。

此时,a/b 的内存均被释放。

上面是第一个缺陷,第二个缺陷在于,如果用非拷贝非移动的方式,创建两个 shared ptr 指向同一块内存,则可能会出现 「悬垂指针」与「Double free」 的问题。

悬垂指针 & Double free
#include <iostream> #include <memory> #define DOUBLE_FREE int main() { int* a = new int(1); { std::shared_ptr<int> p1(a); #ifdef DOUBLE_FREE std::shared_ptr<int> p2(a); #endif } #ifndef DOUBLE_FREE std::cout << *a; #endif return 0; }

如果同时使用 p1 和 p2,则 p2 先析构,计数器归零,释放 a 指向的内存,然后 p1 析构,计数器归零,又释放 a 指向的内存,造成 double free 的错误。

如果仅使用 p1,则 p1 析构后释放 a 的内存,后续解引用 a 时出现 Undefined Behavior,输出可能是任意数。

int* 和 void* 的区别?

int* 类型的变量会有类型信息,告诉编译器「我指向的这块内存是个 int 变量,如果你要读取就只能一次性读 4 字节」。其他的 double*long long* 同理。

void* 意为无类型指针,可以指向任意类型的数据,但赋值给 int* 这种的就要配合类型转换了。直接读取是读 1 字节,毕竟也是指向了一个内存地址。

若干 STL 容器的区别与特点、使用场景、迭代器失效问题等

具体可参考 C++ の STL

map 中使用 at() 和用 operator[] 有什么异同?

两者都是基于 key 去索引 value。区别在于,如果 key 不存在,前者会抛异常,后者不会,并且还会插入一个 item,以及调用 value 的默认构造函数。

static 关键字的用法?

具体可参考 C++ の static

extern 关键字的用法?

第一种用法是为一个全局变量、函数或模板赋予外部链接(external linkage)属性,即编译器在某个 .cpp 文件中遇到一个声明为 extern 的变量或函数,就会试图去其他文件中寻找该符号的定义。

第二种用法是以指定编译器(C or C++)来处理接下来这部分内容。因为 C++ 为了处理函数重载,会以与 C 函数不同的方式(函数名+参数名)进行符号命名,而 C 不会,因此会造成链接时无法找到对应函数的情况。所以如果要对编译器提示使用C的方式来处理函数的话,那么就要使用 extern "C" 来说明。

volatile 关键字的用法?

volatile 声明的类型变量表示可以被某些编译器未知的因素更改,此时编译器就不会对其进行优化,从而总是从它所在的内存读取数据。

一些可能的优化策略有:如果发现两次读变量(比如 i)的代码之间,没有对 i 进行过操作,那就会自动把第一次读的 i 值交给第二次的读取。尽管,在这期间内存中变量的值发生了变化。

感觉有点像数据库的可重复读?而 volitale 反而是禁止了可重复读。

new 和 malloc 的区别?

具体可参考 C++11 の 内存分配

new: 操作符;支持传入类型/构造函数参数;会调用构造函数;直接返回对应类型的指针;用 delete 释放;分配失败时抛异常;

malloc: 函数;只能传入需要分配的字节数;不会调用构造函数;以 void* 形式返回已分配内存的首地址;用 free 释放;分配失败时返回空指针;

信号量和锁的区别?

两者都用于多线程并发场景。

锁通常用于互斥场景,即多个线程同时访问某一共享变量。

信号量既可以用于互斥,也可以用于同步(生产者 & 消费者问题)。可以认为锁是信号量计数值为 1 时候的特例。

使用模板(template)的优缺点?

优点: 提升开发效率;减少编码时间。

缺点: 难以调试;声明和实现必须都放在同一个文件里,否则报 undefined reference 编译错误;拖慢编译时间。

内联函数和普通函数的区别?

具体可参考 C++11 の 内联函数

内联函数在编译期会被直接展开,减少了函数调用开销(参数压栈、地址跳转等)。

虚函数的机制?一个类中可以把所有函数设为虚函数吗?如果把除了构造函数以外的函数设为虚函数会有什么问题?

具体可参考 C++11 の 面向对象

如果本类或父类中有虚函数,内存最开始就会有一个虚表指针,指向一个存放所有声明为虚函数的函数指针的数组。如果用基类指向派生类,并调用虚函数,就会去虚表中查,取出相应的函数指针并调用,从而实现多态。

除了构造函数,其它的函数都能设为虚函数,并且析构函数必须设为虚函数。

有些函数不需要实现多态特性,那么就没必要声明为虚函数。即便没有在子类中重写,也需要去虚表中查询,多了一次访存开销。

析构函数中能调用虚函数吗?

具体可参考 条款 9. 绝不在构造和析构过程中调用 virtual 函数

一般来说,存在虚函数的类派生链中,基类的析构函数都会设置成 virtual,以在出现基类指针指向派生类的情况时,对派生类进行正确的析构(否则只会调用基类的析构函数)。所以最后的执行顺序为:派生类析构函数 > 基类析构函数。

问题可以分成两种情况:在派生类析构函数中能否调用虚函数?在基类析构函数中能否调用虚函数?

两种情况在语法上都是可行的。

对于第一种情况,在运行上由于虚函数表仍存在,自身的成员变量并没有释放,所以是没有问题的,调用的虚函数将会是派生类的版本。

对于第二种情况,由于在调用基类的析构函数时,派生类已经析构,内存中只剩下基类部分,此时将不使用动态联编,也就是将当前对象视为基类对象,调用的虚函数将会是基类的版本而非派生类。不难发现,此时对虚函数的调用已经失去了多态性。

总结来说就是语法和运行上都不会报错,只不过在基类的析构函数中中调用虚函数不会起到我们想要的效果。

RTTI 保存在哪里?

具体可参考 C++11 の 面向对象

在虚函数表的负值索引处,除了 runtime typeinfo,其实还会存虚继承的虚基类 offset

简单介绍智能指针

具体可参考 C++ の 智能指针

如何实现一个支持引用计数的类?

具体可参考 如何手撕智能指针

基本思想是类内有一个 Counter* 指针指向计数器,每次拷贝时 Counter 内部计数值增加,析构时减少,为 0 时才释放资源。计数值可以采用 std::atomic 来实现无锁版本。

智能指针的优缺点是什么?或者说哪些情况下非得用裸指针?

优点自然是利用 RAII 思想自动进行内存分配与释放,降低内存泄漏的可能性。

(缺点我也是临时想的)在用 dynamic_cast 的时候不得不用裸指针了。

但是也可以用 dynamic_pointer_cast 来解决,面试官没反驳我倒是。

或者可以说 shared_ptr 存在循环引用问题,但可以用 weak_ptr 解决。暂时没想到好的回答,感觉像是上压力看看应对能力。

对三种智能指针分别应用 sizeof,输出值是多少?

直接上代码:

sizeof(三种智能指针)
#include <iostream> #include <memory> using namespace std; int main() { unique_ptr<int> a; shared_ptr<int> b; weak_ptr<int> c; cout << sizeof(a) << ' ' << sizeof(b) << ' ' << sizeof(c) << endl; }

64 位机器下,上面的代码输出结果为 8 16 16,即 8B、16B、16B。

分析:unique_ptr 只保有一个对象指针;shared_ptrweak_ptr 都是除了对象指针还保有一个计数器指针(两者的计数器类型不同)。

重载、重写、覆盖三者的区别?

重载:在同一个作用域内,函数名相同但参数列表不同的多个函数,包括函数的参数类型、参数个数或参数顺序的不同。即静态多态

重写:派生类重新定义基类中的虚函数,以便在运行时动态调用派生类的函数。即动态多态

覆盖:派生类中声明了与基类相同名称的成员变量或方法,使得基类中的同名成员在子类中不可见。如果此时需要调用基类的同名方法,则需要使用 Base::func() 的形式(假设基类为 Base)。

如何实现一个线程池?

具体可参考 并发应用 —— 线程池

操作系统

进程和线程的区别?

进程: 资源分配的单位,拥有独立地址空间,切换时需修改页表基地址寄存器,清空 TLB 以及 CS、IP 等寄存器。新进程一开始访页时大概率会 cache miss,从而开销大。

线程: 调度的单位,同一进程下所有线程共享地址空间,但线程之间拥有独立的程序计数器与栈空间,切换时仅需修改相关寄存器,无需修改页表,故开销小。另外,不同进程之间的线程切换也会涉及到进程切换,开销变大。

本质区别在于是否和其它单位共享页表

哪些情况会导致进程 crash?

主要是段错误,比如

  1. 访问空指针;
  2. 数组越界访问;
  3. 除以零;
  4. 内存耗尽,比如栈溢出、内存泄漏等;

用户级线程和内核级线程的区别?

用户级线程,或者说协程,如 coroutine,由应用程序实现,调度在用户态完成,不需要内核介入,所以开销较小。缺点在于一旦一个用户及线程阻塞,那整个进程都将被阻塞。

内核级线程,如 thread,由操作系统实现,调度也由操作系统完成,意味着对内核级线程的调度要从用户态陷入内核,开销较大。优点在于即使自我阻塞,整个进程也能正常运转。

切换地址空间是怎样实现的?

修改页表基地址寄存器,以访问正确的页表;以及清空 TLB,防止进行错误的地址转换。当然如果 TLB 支持 ASID 就不用清空了。

虚拟地址和物理地址区别?为什么要用虚拟地址?

具体可参考 这篇文章

物理地址是指实际存储在内存中的地址,它可以直接被硬件访问。物理地址是固定的,并且受到物理内存大小的限制。

虚拟地址是指软件视图中的内存地址,它是逻辑地址,不受物理内存大小的限制。通常是连续的,因此程序员可以使用连续的虚拟地址,而不必考虑实际内存中的分布情况。

如果只有物理地址,那么程序员编程时必须足够小心,以防使用了其它程序的地址,更不能访问内核空间。在页面置换时,也必须将其放到固定的位置。而引入了虚拟地址,就可以将编程与访存分离,将内存访问交给操作系统去实现(页表),进而实现进程空间隔离,保证了安全性。

进程访页过程?

在支持二级页表的 32 位机器中取指令为例。

首先进程根据当前 CS:IP 寄存器,进行指令地址的计算(CS<<4 + IP),从而获得相应代码段中的指令地址。注意这是一个虚拟地址,需要根据硬件转换为物理地址。

注意: 假设该虚拟地址的前 10 位 PD_Index 是页目录条目的索引,中间 10 位 PT_Index 是页表条目的索引,后 12 位是页内偏移 Offset

先访问 TLB,TLB 实际存储的是虚拟页号 VPN 到物理页帧号 PFN 的转换。如果 TLB 命中,就直接根据 PFN<<10 | Offset 得到物理地址了。如果没有命中,就要获取正确的 PFN 并更新 TLB 条目以便未来的访问同一物理页时降低开销。

那么首先去页目录基地址寄存器中获取页目录的地址 PD_Addr,这是个物理地址,可以直接访问,然后根据 PD_Addr + 4*PD_Index (一个条目为 4 字节)获得相应页目录项条目。这一条目中存放的是相应页表的地址 PT_Addr,还有一些状态位(如果该页表中没有任何一个页面分配,那么有效位就是 0,反之为 1)。

这里假设页目录项有效,那么我们得到了页表,用同样的方法,我们访问地址 PT_Addr + 4*PT_Index 可以得到 PFN,假设页表项仍然有效,那就赶紧更新 TLB 然后重新访问一遍。

由于上次的插入,这次必定能获得物理地址,那么就可以愉快地访存了。

如果页目录项/页表项无效,说明我们要访问的物理页帧并没有存放我们想要的数据(页表也占据了一整个物理页帧),那么此时此刻就要去磁盘上获取数据,然后根据一定的置换规则(如 LRU)进行换页。

为什么要用多级页表?

32 位机器下,如果一个页面为 4KB 并且采用单级页表,那就要整整 4MB 的连续空间,而且不一定这 2^20 个页面都得到分配,会有很大一部分页表项是浪费的。

二级页表就不会有这种情况。假设前 10 位为页目录索引,中间 10 位为页表索引,如果某个页表所指向的 2^10 个页面都没得到分配,那么就不会为这个页表分配物理页帧,页目录中会将该页表的有效位设为 0。这样就大大节省了空间,还防止了无法分配过大连续内存的问题。

用户态和内核态的区别?怎么切换?为什么要区分这两个级别?

用户态和内核态是操作系统的两种运行级别,两者最大的区别就是特权级不同。用户态拥有最低的特权级,内核态拥有最高的特权级。运行在用户态的程序不能直接访问内核,例如不能使用系统调用。Due to the complexity of developing and maintaining the kernel, only the most essential and performance-critical code are placed in the kernel. Other things, such as GUI, management and control code, typically are programmed as user-space applications. This practice of splitting the implementation of certain features between kernel and user space is quite common in Linux.(引用自 Linux Journal

处于用户态的进程可以通过 1.请求系统调用 2.硬件中断 3.软件异常 等方式陷入内核态,然后再利用 ret 指令返回用户态。

如果只有用户态,那就完全没法利用操作系统的内核功能;如果只有内核态,那所有进程都可以访问内核数据,甚至修改内核,不安全。

进程有几个栈?

两个。用户态一个,内核态一个。两个栈的数据不互通,也是为了安全性考虑。

执行系统调用的过程?

  1. 将系统调用号放到寄存器 EAX 中,执行 int 0x80 指令发出中断;
  2. CPU 收到中断后,根据中断号 0x80 到中断向量表中查找对应中断描述符,其中包含中断服务程序 system_call 的代码段选择子;
  3. 根据该段选择子去全局描述符表 GDT 里取得段描述符,段描述符 SD 里保存了中断服务程序的段基址和属性信息,此时 CPU 就得到了中断服务程序的起始地址。这里,CPU 会检查 CS.CPL 和 SD.DPL,以确保中断服务程序的特权级是高于当前用户程序的,或者说当前程序有权限使用中断服务程序,这可以避免用户应用程序访问特殊的中断门;
  4. 在执行 system_call 前,CPU 会先从当前进程的 TSS 字段里取得内核栈地址,然后保存用户进程现场(CS、IP、SS、ESP 等信息),并将新的内核栈信息赋给 SS 和 ESP;
  5. 开始执行 system_call,根据 EAX 寄存器存储的系统调用号,从系统调用表上找到相应的系统调用并调用;
  6. 执行 itret 指令返回用户态,取出内核栈中保存的用户进程信息,重新赋值给相关寄存器,至此系统调用完成;

堆和栈的区别?

堆和栈是内存模型中的两片不同区域。

堆存放程序员动态分配的数据,同时需要程序员手动释放,由低向高增长,空间较大。

栈存放一般函数局部变量,一个函数调用对应一个栈帧,由操作系统自动管理栈空间的分配与释放,由高向低增长,空间较小,需要预防栈溢出的异常。

调用 malloc 分配一个 100B 大小的空间,内存会发生怎样的变化?

事实上内存并不会发生变化。

如果只调用了 malloc(),那么只会在该进程的虚拟地址空间中划分出 100B,新增一个页表项,设置 flag=0,表明未分配物理地址。

等到实际访问这个虚拟地址时,会发现对应的物理地址并不存在,触发缺页中断,这个时候才会在堆上进行实际的内存分配(brk),并再次修改那个页表项。后续的访问就能正常进行。

mmap 的流程?和 read 的区别?是零拷贝吗?

调用 mmap() 时,首先分配一片相应大小的虚拟地址,并在页表中添加相应页表项。

当第一次访问该虚拟地址时,产生缺页中断,陷入内核,根据 inode 号将相应文件中的某一段通过 I/O 读入内核的 Page Cache 中(虽然叫 cache 但其实是在内存里的),然后通过修改用户态进程中页表的方式赋予用户态进程读写这段内存的权利。

回到用户态后,此时进程就可以通过该页表项直接对文件内容进行读写了(如果是脏写还需要将 Page Cache 的内容刷回磁盘),而无需进行额外的内核态与用户态的数据拷贝操作,所以零拷贝。

read() 则在 I/O 到内核缓冲区后还要拷贝到用户空间,写回时亦然。相比而言 mmap() 省去了不必要的拷贝操作,效率更高。

僵尸进程、孤儿进程分别指什么?如何处理?

进程终止执行时,进程表中还会保留一段时间其进程控制块(PCB),直至父进程执行 wait()waitpid() 系统调用,这会阻塞父进程直至子进程结束,其间操作系统会释放子进程的 PCB。这是正常的父子进程管理流程。

如果子进程比父进程先结束,父进程又没有执行 wait()/waitpid() 时,子进程的 PCB 将滞留在进程表中,无法得到释放,直至父进程结束。这就成了「僵尸进程」。

而当父进程比子进程先结束时(意味着并没有执行 wait()/waitpid()),此时子进程会成为「孤儿进程」,并由 init 进程(pid=1)收养,管理子进程的结束行为。

相比于僵尸进程,孤儿进程的 PCB 由于被 init 进程接管,能够及时释放 PCB,所以无伤大雅。

但僵尸进程则不同了,出现大量僵尸进程会占用系统资源,虽然 init 进程会定期检查并清理僵尸进程,释放它们占用的系统资源,但这是不可控的。系统所能使用的进程号是有限的,如果大量的产生僵尸进程,将因为没有可用的进程号而导致系统不能产生新的进程。

这是真实可能发生的,它有一定的概率,特别当存在一个编码糟糕的程序开始大量产生僵尸进程的时候。

更严重的是,我们还不能通过 kill 来杀死僵尸进程——进程都结束了,还怎么处理信号呢?

对于父进程已结束的僵尸进程,可以直接执行 kill -9 杀死父进程,这样所有的僵尸进程就会变成孤儿进程了,被 init 收养、清理。

上面是亡羊补牢式的解决方案,正确的策略是尽可能在代码层面预防这种现象。事实上,当子进程终止时,内核就会向它的父进程发送一个 SIGCHLD 信号,而对于这种信号的系统默认动作是忽略它,但我们可以修改父进程的信号处理函数,让父进程中收 SIGCHLD 信号后调用 wait()/waitpid(),比如下面这样:

预防僵尸进程
#include <errno.h> #include <signal.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/wait.h> #include <unistd.h> void deal_child(int sig_no) { pid_t id; while ((id = (waitpid(-1, NULL, WNOHANG)) > 0)) { // WNOHANG 表示非阻塞 // 这里意思是以非阻塞形式等待任意一个子进程 // 而 SIGCHLD 是不可靠信号,即信号不会排队等待 // 也就是说,如果父进程收到了一个 SIGCHLD // 信号,那么表明至少有一个子进程已终止或已停止 // 因此,在每次处理信号时都应该尽可能多地回收子进程,所以这里用了 while 循环 } } int main() { signal(SIGCHLD, deal_child); // 设置对 SIGCHLD 信号的处理函数为 deal_child pid_t pid; for (int i = 0; i < 5; i++) { if ((pid = fork()) < 0) { printf("fork error, %s\n", strerror(errno)); exit(-1); } /* child */ if (pid == 0) { sleep(1); exit(0); } } /* parent */ sleep(5); return 0; }

计算机网络

如何判断一台机器是大端序还是小端序?

简单的代码示例

判断是否为小端序
bool isSmallEndian() { int num = 0x1234; char* c = (char*)&num; return c[0] == 0x34; }

如果内存中第一个字节是 0x12 则说明是大端序

说一下五层网络模型,并且指出 TCP 处于哪一层?

应用层,传输层,网络层,数据链路层,物理层。TCP 位于传输层。

TCP 和 UDP 的区别?

TCP

  • 为了满足可靠传输,数据传输前要用三次握手建立连接,数据传输过程中提供拥塞控制,用滑动窗口控制有序性(序列号和确认号),牺牲了效率;
  • 首部存在各种控制字段;
  • 如果 payload 长度过大,TCP 会进行分片;
  • 面向字节流,不关心 payload 的内容,是直接从缓冲区中取出字节加上首部组成报文段后发送,接收方可能无法区分消息边界,导致粘包问题

UDP

  • 无需连接,不计后果地发送,即便丢包也无所谓,虽然不可靠,但效率很高,一般用于视频、DNS 查询等;
  • 首部仅仅包含四个字段——{源端口,目标端口,长度,校验和};
  • 一个 UDP 对应一个用户消息,即便乱序到达,接收方也可以区分消息边界;

为什么视频可以用 UDP?

因为即使丢包也可以用插值算法补帧,允许这种不可靠,同时更要追求视频的实时性。

点击 url 到显示网页之间发生了什么?

具体可参考 点击 Url 到显示网页之间发生了什么?

TCP 和 UDP 都是怎么处理数据量较大的包的(如 5KB)?

因为以太网 MTU=1500MB 的缘故,IP 层会将过大的包进行分片,处理方式为在头部设置标识位片偏移。TCP 和 UDP 都不负责分片工作,而是将其交付给下一层去做。

特别的,IP 首部的长度字段为 16 位,意味着同一个分片组最大可以容纳 64KB 的 TCP/UDP 数据,那对 TCP/UDP 而言 5KB 简直是小意思,不会分片。而如果超过 64 KB,那就要分成多个 TCP/UDP 包发送了。

如果应用层基于 TCP 发送了两个分别为 100B 和 200B 大小的数据包,接收方可能的情况有哪些?换成 UDP 呢?

理想情况下,接收方会先收到 100B 的包(记为 「包1」),再收到 200B 的包(记为 「包2」)。

非理想情况下:

  1. 数据包可能是乱序到达的,硬件层面可能会先收到「包2」,一层层往上交付后,TCP 模块会发现这个包的序列号与期望值不匹配,将其数据缓存,等到后续收到后「包1」,解包后再和之前缓存的「包2」数据一并交给上层;
  2. 由于 TCP 基于字节流,在传输层无法确认消息边界,总是在字节流冲满 buffer 后再被上层一次性取走,所以上层拿到的数据并不一定是完整的「包1」或者「包2」,这就是出现了粘包;

如果使用 UDP:

  1. 对于乱序到达的情况,则先到的「包2」会直接被交付,而不用等「包1」有没有到,因为 UDP 本身是不提供可靠传输的,不用保证数据的有序性;
  2. 对于粘包情况,UDP Header 指明了数据长度,一个 UDP 包就是一个用户消息,所以即便「包1」和「包2」同时到达,UDP 也能正确分清数据的边界,不会产生粘包现象;

select/poll/epoll 的区别

具体可参考 这篇文章

网络层如何转发数据包?路由器是如何进行自学习的?

交换机根据源 MAC 地址建立转发表,根据目的 MAC 地址转发,如果目的 MAC 地址不在,就发一个 ARP 广播请求来获取。

路由器根据目的 IP 地址进行将数据包由特定端口发出。对于静态路由而言,转发表需管理员手动配置;而动态路由则会根据路由协议(如 RIP)定时与其他路由器交换路由信息,从而建立转发表。

HTTP 和 HTTPS 的区别

  1. HTTP 协议的数据传输是明文的,是不安全的;HTTPS 是 HTTP 协议的安全版本,使用了 SSL/TLS 协议进行了加密处理,相对更安全;

  2. HTTP 和 HTTPS 使用连接方式不同,默认端口也不一样,HTTP是 80,HTTPS是 443;

  3. HTTPS 由于需要设计加密以及多次握手,性能方面不如 HTTP;

    这里指的是在三次握手之后,使用 HTTPS 协议的双方需要用四次(TLS v1.2)/两次(TLS v1.3)握手进行密钥的交换,后续所有消息都通过密钥加密传输。

为什么要使用三次握手?

具体可参考 TCP Things,其实还有一些其他的作用。

  1. 确认双方初始序列号,以确保后续接收到的报文段位于同一个连接中;
  2. 使发送方确认拥塞窗口,控制发送速率;

为什么 TIMEWAIT 要等 2MSL

具体可参考 TCP Things

数据库系统

说下 ACID 分别代表什么意思?

A: Atomic 原子性

C: Consistency 一致性

I: Isolation 隔离性

D: Durability 持久性

事务隔离级别分别有哪些?分别解决了什么问题?

读未提交: 这种隔离级别不加任何锁,有可能读事务 reader 读取到了写事务 writer 写入数据库但未提交的数据。这就是脏读

读提交: 这种隔离级别上了写锁,但同一事务 reader 对同一个键的前后两次读取之间可能会因为穿插了另一事务 writer 的写入,从而读取到了不一样的数据。这就是不可重复读

可重复读: 这种隔离级别下,对某个键的读取开始后不再允许任何写入,因而不会出现不可重复读,前后两次读结果必定相同。但在某些场景比如 select * from table; insert values {k1, v1} into table; 中,两个语句之间由于另一事务也插入了 {k1, v1} 这一键值对,导致 insert 失败,原因是键冲突,但 select 时并没有看到这一条数据。这就是幻读

可序列化: 这种隔离级别下,事务串行化顺序执行,可以避免脏读、不可重复读与幻读。但是这种事务隔离级别效率低下,比较耗数据库性能,一般不使用。

B 树、B+ 树、红黑树的区别?为什么索引中使用 B+ 树?

B Tree: 内部节点存数据,从而可存储的用于索引子节点的指针数变少,整棵树趋于高瘦;查询效率不稳定(时快时慢),并且不支持范围查询。

B+ Tree: 内部节点仅存索引指针,数据仅由叶子节点存放,整棵树趋于矮胖,能够减少 I/O 次数,有利于提高查找性能;查询效率稳定(都去叶子节点上查),并且支持范围查询(叶子节点之间之间相当于双向链表)。

红黑树: 属于平衡二叉树,节点分红/黑两种,保证不存在任意两个红色节点相邻,并且根到叶的最长路径不超过最短路径的两倍,查找为 \(O(\log N)\),增删都只需要常数次自旋。

索引用 B+ 树主要还是因为其能够大幅减少磁盘 I/O 次数,并且支持范围查询。

除了 B+ 树,还有哪些用于索引的数据结构?

  1. Hash 索引:使用哈希函数将索引键映射到实际数据的存储位置。这种索引结构通常能够提供非常快速的数据查找,特别是对于等值查询(即精确匹配)而言。缺点是支持范围查询,且存在潜在的哈希冲突
  2. LSM Tree:一种对磁盘写进行优化的结构。核心思想是「批量 & 顺序」写而非单次随机写,具体可参考此文。缺点是存在空间放大(不同 SSTable 存同一 Key 的副本)和读放大(需要在多层 SSTable 中查数据,可能产生更多开销)。
  3. ...

时序数据库的特点是什么?和在关系型数据库中把 Timestamp 作为主键有什么区别?

时序数据库(TSDB)的关键特点在于数据按时间顺序到达时间戳为主键,专注于时间序列数据的存储和管理,支持按时间范围处理数据。由于数据更新频繁,TSDB 需要更高的性能,处理引擎必须是 Online 的,常用于实时监控与报警场景。可以认为时序数据库是为特定 Workload 做出的定向优化。

而普通的关系型数据库则更偏向对数据进行离线分析,无法满足 TSDB 的使用场景。

分布式系统

简单介绍一下 Raft 算法的实现

主要是基于「过半原则」的「选举」和「日志」两大模块。

选举:每个节点有选举定时器,仅当收到 Leader 的 heartbeat/appendEntry 请求,或满足条件(当前 Term 没给其它成员投过票,且投票请求中包含的日志更新)的投票请求时重置。一旦超时,则增加 Term,成为 Candidate 并发起选举,向其他成员发送投票请求。如果超过半数成员(包括自己)同意投票,则当选 Leader,反之退为 Follower

日志:上层会给 Leader 推送请求,打包为日志后检查是否有其他成员需要发送日志(通过 next 变量),如果有就从 Index=next[peer] 处开始发送,其间会有冲突检查,一旦对方接收成功就更新 match 变量。当某一 Index 的日志被超过半数成员持有(通过 match 变量),则认为这条日志的状态是 COMMITTEDLeader 需要在与 Follower 的交互中告知有哪些日志是 COMMITTED。所有成员定期将所有 COMMITTED 的日志推给上层,然后将这些日志的状态改为 APPLIED。在这基础上还引入了 snapshot,用于内存优化。

如何提高一个分布式系统的写性能

算是一个开放性问题,可以从多种角度去回答

  1. 分库分表。一个集群能够提供的写性能是有限的,一旦超过了某个阈值,那么后续的写请求必然被之前的写请求所阻塞。一个合理的做法是将整个 Key 集合划分为多个 Shard,一个 Shard 由一个集群负责,这样就将整个服务的负载分散到多个集群,有利于提高写性能;
  2. 非阻塞写。当集群收到写请求时,允许直接返回消息而非阻塞直至写操作 apply;
  3. 利用缓冲区。磁盘 I/O 也是一大性能瓶颈,可以在写入过程中使用 buffer,并且异步地将 buffer 中的数据落盘,减少对持久化存储的写入次数,可以减少对底层存储系统的压力,提高写入性能;
  4. ...

游戏场景

玩家攻击,如何判断武器打到怪物?如果武器速度过快,前后两帧恰好在怪物两侧,如何处理这种异常?

第一个问题是三维空间碰撞检测

第二个问题涉及到连续碰撞检测

给定若干怪物的二维坐标 (x, y),如何确定离玩家最近的那个怪物?

用到了最近邻检索算法

给定若干怪物的二维坐标 (x, y),选择哪个坐标释放半径为 r 的圆形范围 aoe,使得攻击到的怪物最多?

固定半径圆最大覆盖问题

如何实现一个高效的 Timer Manager

参考时间轮算法

现在要设计一个新手引导关,有若干新手引导点,如何对「某个玩家是否完成某个引导点」进行快速存取?要求尽可能精简内存,并可以认为「引导点」由一个整数 id 表示。

第一步是引导点 id 的设计。

一开始说认为新手引导是单线的,可以直接用一个从 0 开始递增的无符号数来表示,面试官提出可能有多条线,因为不同功能模块可能都需要设计引导。

然后说可以将 id 划分为高低位,高位表示模块类型,低位表示该模块的引导点序号,但是考虑到最后是用数组做的,可以在从 0 开始递增的基础上,为不同模块设置一个 BEGIN 和 END(比如战斗模块的 BEGIN 和 END 分别是 3 和 7,那么 id 3~7 就对应战斗模块的引导点 1~5)。

(这个方案被认可)接下去就可以用 vector<bool> 去支持判断是否完成了。

(进一步提出如果只有 30 个引导点,可以如何优化)用一个 uint32 变量 FLAG 即可,每个二进制位 1/0 来表示是否完成。那么存取就是位运算了,完成第 i 个引导点就是 FLAG |= (1 << i),查询是 FLAG &= (1 << i)

(进一步提问如何统计完成了多少个引导点)这个问题其实就是统计二进制中 1 的个数,这个算法比较经典,可以看这篇

但是后面要求不能用循环、迭代、递归、模板元编程、额外成员变量,就没回答上了。

UE

AActor / APawn / ACharacter 三者的区别与联系?

类派生关系为 AActor -> APawn -> ACharacter

Actor:Actor 是可以放到关卡中的任何对象;

Pawn:在 Actor 基础上集成了 Controller 类,允许玩家或 AI 进行控制;

Character:Character 在 Pawn 的基础上引入了三大组件,SkeletalMeshComponentCharacterMovementComponent 以及 CapsuleComponent,这些组件提供了角色实现基于骨骼的高级动画移动基本逻辑功能以及移动碰撞检测的能力。

那么,当对象逻辑简单、不需要过多的逻辑动作(比如方块、飞船)那么可以选择继承 Pawn 而不是继承 Character 类。

UCharacterMovementComponent 做了哪些事?

先看官方注释:

/**
 * CharacterMovementComponent handles movement logic for the associated Character owner.
 * It supports various movement modes including: walking, falling, swimming, flying, custom.
 *
 * Movement is affected primarily by current Velocity and Acceleration. Acceleration is updated each frame
 * based on the input vector accumulated thus far (see UPawnMovementComponent::GetPendingInputVector()).
 *
 * Networking is fully implemented, with server-client correction and prediction included.
 */

FName / FText / FString 的区别?

UE 字符串处理

USkeletalMesh / USkeletalMeshComponent / ASkeletalMeshActor 三者的区别与联系?

UE 的垃圾回收机制?

Lua

Lua 如何实现面向对象?不用 metatable 呢?

Lua 的垃圾回收机制?为什么做后续优化?

Lua 虚拟栈是什么?

Lua 和 C 之间如何互相调用?


  目录