盛趣游戏提前批面试记录

总面试时间34分钟，8成凉面

1.项目问题：令牌桶添加令牌怎么实现的？

2.多线程实际问题：线程怎么创建需要传入什么参数，线程怎么退出，主线程如何等待子线程退出，可以顺便思考一下：进程怎么创建传参，进程怎么退出，主进程怎样等待子进程退出？

线程创建方式及传参：pthread_create是UNIX环境创建线程函数
头文件 #include<pthread.h>

函数声明 int pthread_create(pthread_t  *restrict tidp, const  pthread_attr_t  *restrict_attr,   void*（*start_rtn)(void*),   void   *restrict   arg);
返回值 若成功则返回0，否则返回出错编号

参数 1.第一个参数为指向线程标识符的指针 2.第二个参数用来设置线程属性 3.第三个参数是线程运行函数的地址。4.最后一个参数是运行函数的参数。
在编译时注意加上-lpthread参数，以调用静态链接库。因为pthread并非Linux系统的默认库。

线程的几种状态：1）就绪：参与调度，等待被执行，一旦被调度选中，立即开始执行
2）运行：占用CPU，正在运行中
3）休眠：暂不参与调度，等待特定事件发生

4）中止：已经运行完毕，等待回收线程资源

进程内典型全局资源如下：
1）代码区：这意味着当前进程空间内所有的可见的函数代码，对于每个线程来说，也是可见的
2）静态存储区：全局变量，静态空间
3）动态存储区：堆空间

主线程等待子线程退出：当thread::join()函数被调用后，调用它的线程会被block，join的作用是让主线程等待直到线程的执行被完成。基本上，这是一种可以用来知道一个线程已结束的机制。main是等待子线程结束才继续执行。当thread::join()返回时，OS的执行的线程已经完成，C++线程对象可以被销毁。

线程的锁：1.mutex是用来保证线程同步的，防止不同的线程同时操作同一个共享数据。

2.使用lock_guard则相对安全，它是基于作用域的，能够自解锁，当该对象创建时，它会像m.lock()一样获得互斥锁，当生命周期结束时，它会自动析构(unlock)，不会因为某个线程异常退出而影响其他线程。

sleep_until: 线程休眠至某个指定的时刻(time point)，该线程才被重新唤醒。

sleep_for: 线程休眠某个指定的时间片(time span)，该线程才被重新唤醒，不过由于线程调度等原因，实际休眠时间可能比sleep_duration 所表示的时间片更长。

线程怎么退出：

1.线程函数返回（最好使用该方法）。
2.同一个进程或另一个进程中的线程调用TerminateThread函数（应避免使用该方法）。
3.通过调用ExitThread函数，线程将自行撤消（最好不使用该方法）。
4.ExitProcess和TerminateProcess函数也可以用来终止线程的运行（导致该进程中的所有线程全部终止）。
进程的创建：fork()。

进程的退出：exit()或main函数return。

主进程等待子进程：waitpad()用于防止孤儿进程。

3.同步和异步的区别？epoll是同步还是异步？这个问题到目前网上好像还在争论，我给他分析了一波我觉得异步的原因epoll回调函数

epoll是同步IO，我理解是同步阻塞，因为所谓同步就是没有信号通知，epoll虽然用了回调函数，但本质上还是让线程或进程等着回调函数通知，并没有在内核中设置信号来通知

epoll有消息返回了。从操作系统层面来讲，一个进程去做另外一件事，然后内核通过信号量来通知进程，任务已经完成，这种行为可以称为异步，但epoll是回调函数所以是同步。

4.C++用过哪些库？stl中的map的数据结构是什么？红黑树介绍一下？红黑树的查找和插入的时间复杂度？

map和multimap底层都是红黑树，unordermap底层是hash表，红黑树的查找时间复杂度是logn同二叉排序树一样，可以理解为二分查找，插入时间复杂度为nlogn(网上查到的不知道为啥呢)

5.const的用法？

const表示常量不可修改，const的常用方式有指针常量和常量指针，指针常量表示该指针指向的地址是个常量不可修改，常量指针表示该指针指向的值是一个常量不可修改。

6.多态是什么？静态多态和动态多态介绍一下？

多态：基类指针指向派生类，让同一指针可以指向不同类的相同方法实现不同功能，静态多态是重载编译时多态，动态多态是重写即虚函数是运行时多态。

7.栈是否有大小？

栈有大小的，linux下进程栈的默认大小是10M，可以通过ulimit-s来查看并修改默认栈的大小，默认一个线程要预留1M左右的栈的大小，所以一个进程拥有多个线程，堆的大小理论上近似等于进程虚拟空间的大小，linux下，进程虚拟空间一般为4G，进程的高位1G留给内核，低位3G留给用户，所以进程堆大小小于3G，32位linux下，进程4G空间，内核1G，用户3G，线程默认8M，所以最多380个线程。

Windows下进程栈默认1M，32位系统下一个进程空间4G，内核2G，用户2G，座椅最多开2048个线程。

8.哲学家进餐问题

解决死锁问题的办法就是同时只允许四位哲学家同时拿起同一边的筷子，这样就能保证一定会有一位哲学家能够拿起两根筷子完成进食并释放资源，供其他哲学家使用，从而实现永动，避免了死锁。举个最简单的栗子，假定0~3号哲学家已经拿起了他左边的筷子，然后当4号哲学家企图去拿他左边的筷子的时候，将该哲学家的线程锁住，使其拿不到其左边的筷子，然后其左边的筷子就可以被3号哲学家拿到，然后3号哲学家进餐，释放筷子，然后更多的哲学家拿到筷子并进餐。

如何才能实现当4号哲学家企图拿起其左边的筷子的时候将该哲学家的线程阻塞？这个时候就要用到该问题的提出者迪杰斯特拉（这货还提出了迪杰斯特拉最短路径算法，著名的银行家算法也是他发明的）提出的信号量机制。因为同时只允许有四位哲学家同时拿起左筷子，因此我们可以设置一个信号量r，使其初始值为4，然后每当一位哲学家企图去拿起他左边的筷子的时候，先对信号量做一次P操作，从而当第五位哲学家企图去拿做筷子的时候，对r做一次P操作，r = -1，由r < 0得第五位哲学家的线程被阻塞，从而不能拿起左筷子，因此也就避免了死锁问题。然后当哲学家放下他左边的筷子的时候，就对r做一次V操作。