非常惨淡的倒在了北京头条的三面上，首先觉得这个提前批的城市选择策略可能有误，太多人投递导致难度激增。第二个就是对操作系统算法的理解有天坑。这里需要弥补一下算法知识和一些深层的概念知识。

一 进程与线程在操作系统内核中的体现

 这个问题首先问的是进程和线程是什么样子的，由于前面已经对这个问题进行过总结，所以在此不再进行复述。

 然后说实话看到这个问题简直是惊呆了，课程里面确实没有详细学习过linux系统。基于操作系统调度的基本单位是进程，所以当时直接答出来线程应该在内核中没有体现。但是时候查阅资料发现这个问题回答的实在不规范。下面贴出标准答案的回复。

 首先需要肯定的是进程和线程在操作系统内核中确实概念相似。在linux系统中，进程和线程或者其他调度单元都是利用 task_struct 这个结构体表示。

1
2
3
4
5
6
7

struct task_struct {
...
    pid_t pid;  //标识不同的进程和线程
    pid_t tgid; //用于标识线程组id，在同一进程中所有线程都具有同一tgid
...
    struct *group_leader;   //线程组中主线程的指针。
}

 进程还是线程的创建都是由父进程/父线程调用系统调用接口实现的。创建的主要工作实际上就是创建task_strcut结构体，并将该对象添加至工作队列中去。而线程和进程在创建时，通过CLONE_THREAD flag的不同，而选择不同的方式共享父进程/父线程的资源，从而造成在用户空间所看到的进程和线程的不同。

引用自Zpeg

 然后更加深入的去看待这个问题，无论以任何方式创建进程或者线程，在linux系统中最终都是去调用do_fork()函数。这个函数的原型是：

1
2
3
4
5

long do_fork(unsigned long clone_flags,
    unsigned long stack_start,
    unsigned long stack_size,
    int __user *parent_tidptr,
    int __user *child_tidptr)

• clone_flags是一个标志集合，用来指定控制复制过程的一些属性。最低字节指定了在子进程终止时被发给父进程的信号号码。其余的高位字节保存了各种常数。
• stack_start是用户状态下栈的起始地址。
• stack_size是用户状态下栈的大小。
• arent_tidptr和child_tidptr是指向用户空间中地址的两个指针，分别指向父子进程的PID。NPTL（Native Posix Threads Library）库的线程实现需要这两个参数。

 线程跟进程的区别主要就在于do_fork函数首先执行的copy_process中，当上层以pthread_create接口call到kernel时，clone_flag是有CLONE_PTHREAD标识

但CLONE_PTHREAD标识只在最后一个步骤（设置各个ID、进程关系）时体现：（current为当前进程/线程的task_struct结构体 ，p为新创建的结构体对象）

1
2
3
4
5
6
7

if (clone_flags & CLONE_THREAD) {
    p->group_leader = current->group_leader;
    p->tgid = current->tgid;
} else {
    p->group_leader = p;
    p->tgid = p->pid;
}

1
2
3
4
5

const int clone_flags = (CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SYSVSEM
	   | CLONE_SIGHAND | CLONE_THREAD
	   | CLONE_SETTLS | CLONE_PARENT_SETTID
	   | CLONE_CHILD_CLEARTID
	   | 0);

 通过判断clone_flags中标记，即可控制子线程会与父线程共享虚拟地址空间、文件、信号等。

 本段的内容主要参考了Zpeg的博客，对博客中的部分内容进行精简，透过这里可以简要了解整体的流程。面对面试官的问题可以简要做如下回答：对于系统内核来说，进程和线程没有显著区别，它们在系统中都是一个task_struct结构体，他们的的主要差距是在主进程或者主线程进行系统调用的时候调用了do_fork()函数，然后do_fork函数中执行copy_process。在copy_process中有一个clone_flags，在创建线程的时候clone_flag是据有CLONE_PTHREAD标识的。

二 数据结构 b+树与跳表

 b+树的最大优势是可以利用叶子节点相互链接的特性来进行区间查询。这个特性无法被普通排序二叉树前序遍历使用链表链接替代。因为普通排序二叉树使用链表链接时更新下一跳的系统消耗可能过大。

 跳表在非尾部进行插入删除时更新索引开销较大。这里与排序二叉树链表链接时更新下一跳类似。

 关于这两个数据结构更多的内容不再进行展开描述。具体可以参考各大搜索引擎的介绍（推荐google）

三 深度学习lstm如何解决梯度爆炸

 这个问题我很吃惊，毕竟确实是本科生，制作深度学习模型的时候通常都是进行调库调试等操作。所以这里暂时不对这个模块进行扩展。来日方长，如果日后从事算法研究再战。

四 socket编程epoll模型的具体实现

 针对select模型和epoll模型，前段时间已经有过了解，select模型是通过轮询来获取活跃的连接的。但是仅知道epoll模型不会轮询所以效率高，但是并不了解epoll模型内部具体实现，这里对epoll模型内部实现机制进行一点介绍。

1

int epoll_create(int size);

 首先我们需要关注的是epoll的创建函数，参照晚风_清扬的博客对该函数进行下面的描述。

epoll_ create时，内核除了帮我们在epoll文件系统里建了新的文件结点，将该节点返回给用户。并在内核cache里建立一个红黑树用于存储以后epoll_ctl传来的需要监听文件fd外，这些fd会以红黑树节点的形式保存在内核cache里，以便支持快速的查找、插入、删除操作。

1

int int epoll_ctl(int epfd, intop, int fd, struct epoll_event *event);

内核还会再建立一个list链表，用于存储事件就绪的fd。内核将就绪事件会拷贝到传入参数的events中的用户空间。就绪队列的事件数组events需要自己创建，并作为参数传入这样才可以在epoll_wait返回时接收需要处理的描述符集合。

当epoll_wait调用时，仅仅观察这个list链表里有没有数据即可。

1

int epoll_wait(int epfd,struct epoll_event *events,int maxevents, int timeout);

所以epoll模型的整体工作流程如下：

1. 执行epoll_create时，创建了红黑树
2. 执行epoll_ctl时，创建就绪list链表，如果增加fd添加到红黑树上，然后向内核注册有事件到来时的回调函数，当设备上的中断事件来临时这个回调函数会向list链表中插入就绪的fd。
3. 执行epoll_wait时立刻返回准备就绪链表里的数据即可

 这里真的是吃了一个没有学过网络编程的亏，所有的内容几乎都是面试前突击的，但是通过这样重重面试对这些模型内部细节逐步有了一个清晰的认识。

五 linux copy-on-write特性

 其实很想跟面试官说，我真的真的真的没有系统的学习过linux操作系统，但是确实我学没学过跟你需要什么样的人才没有啥关系，只能吃一个哑巴亏回去赶紧补着点。

 copy-on-write 简单来说就是写时拷贝技术，该技术的主要目的时减少fork时复制主进程内存内容的时间开销。linux系统调用fork函数时，当进程未对内存内容进行修改的时候，此时将直接共享主进程的内存，此时子进程仅拥有对内存进行只读的权限。当需要对内存内容进行修改的时候，操作系统会先将内存copy一份，然后再进行写操作。

在页根本不会被写入的情况下—举例来说，fork()后立即调用exec()—它们就无需复制了。fork()的实际开销就是复制父进程的页表以及给子进程创建惟一的进程描述符。

六 连续抛硬币问题

问题描述:

连续抛硬币，问出现正反反 和反反正的概率谁的更大概率是多少。

 面试的时候脑子有点糊，但是最后还是做出来了。分析过程大致如下：

 首先考虑下面四种情况：

1/4 NN

1/4 NF

1/4 FN

1/4 FF

 我们可以快速的发现，如果出现了正，后续只可能出现正反反胜利的情况。所以反反正胜利的概率仅存在于前两次抛出反的情况。然后对于情况反反，只要出现一次正，则反反正胜利，所以正反反胜利的概率则是 1-1/4 = 3/4。 反反正的概率是1/4。

七 LRU最近替换算法 O（1）

 看到这个问题实在是脑壳疼。操作系统课程上对这个内容学习的欠缺导致现在尴尬的局面。这个问题的解决非常非常的简单，利用一个映射数组和链表即可完成o（1）的更新和O（1）的访问。当然也可以利用hash_map和链表。个人推测cpu如果采用这种更新策略，应该使用的是映射数组的方式，这种方式更为稳定。这里需要 内存大小/页大小 的映射空间，在内存过大的时候可能并不是特别实用，所以推测现代cpu应该抛弃了这种方法，但是LRU算法仍然作为最经典的缓存算法被大家使用。

 因为心情郁闷这里就不对这个算法重新进行实现，摘选一个接近正确的代码放在下面:

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

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=500005;
int n,m,x,cnt,stk[110],pos[maxn];
int main(){
    while(cin>>n>>m){
        cnt=0;
        memset(pos,0,sizeof(pos));//标记页面在栈中的位置
        while(m--){
            cin>>x;
            if(pos[x]){//栈中已出现x，将x提到栈顶，剩下的页面往下移
                for(int i=pos[x];i<cnt;++i)stk[i]=stk[i+1],pos[stk[i]]=i;
                //!!!这个代码不是特别对的地方就是这里，这里不能使用for循环，采用链表可以提升效率。
                stk[cnt]=x,pos[x]=cnt;
            }
            else{//x未出现
                if(cnt!=n)stk[++cnt]=x,pos[x]=cnt;//栈未满则直接添加
                else{//栈满，移去最久未使用的页面，将x放栈顶
                    for(int i=1;i<n;++i)stk[i]=stk[i+1],pos[stk[i]]=i;
                //！！！与上述同理。堆栈需要手动实现一个链表！！！！
                    stk[n]=x,pos[x]=n;
                }
            }
        }
        for(int i=1;i<=cnt;++i)cout<<stk[i]<<(i==cnt?'\n':' ');//输出当前栈中的页面号
    }
    return 0;
}

 然后关于这次心态崩坏的头条三面就总结到这里了，希望能够尽快顺顺利利的获得一个保研offer或者薪水客观的校招offer。加油！！！！！！

 刚刚经历了大学以来的第一次面试，不得不说头条作为宇宙厂面试有非常高的难度，平日进行的简单开发和底层的深入理解不可而与，为了更加透彻的理解进程与线程，这里特别对进程和线程相关的知识进行总结。并且利用准确的术语来表述进程和线程的特点以及关系。

一 进程的基本概念

 进程是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念，竞争计算机系统资源的基本单位。作为一个程序执行的一个实体，是系统分配资源的基本单位。

 进程通信主要有五种通信方式，分别是管道、命名管道、信号量、消息队列、共享内存。

二 线程的基本概念

 线程是进程的一个执行单元，是进程的一个特定执行路径。当一个线程修改了进程的资源，同一个进程下的其他线程将会立即看到这种变化。

 相较于进程，由于线程共享进程中的全局变量，所以通常而言不需要特别的线程通信方式，在C/C++中我们常利用volatile关键词使编译器不对代码段进行优化，无需将该值放入寄存器中，使该值可以被外部改变。或者利用windows消息队列进行线程通信。此外还可以利用std中std::promise、std::packaged_task来进行线程通信。

三 进程和线程的主要区别及优势

区别：

1.代码段、内存:进程间相互独立，同一进程的各线程间共享。线程仅在同一个进程内可见。

2.通信：进程间通信IPC（管道、命名管道、信号量、共享内存、消息队列），线程间通信相对进程间通信更为简单，直接使用全局变量即可。但是使用时需要考虑锁机制和同步机制。

3.调度和切换：线程上下文切换比进程上下文切换快得多。

4.在多线程OS中，进程不是一个可执行的实体。

选择：

1.需要频繁创建销毁的优先使用线程；因为对进程来说创建和销毁一个进程的代价是很大的。

2.线程的切换速度快，所以在需要大量计算，切换频繁时使用线程，还有耗时的操作时用使用线程可提高应用程序的响应。

3.因为对CPU系统的效率使用上线程更占优势，所以可能要发展到多机分布的用进程，多核分布用线程。

4.并行操作时用线程，如C/S架构的服务器端并发线程响应用户的请求。

5.需要更稳定安全时，适合选择进程；需要速度时，选择线程更好。

资源引用：什么是进程？什么是线程？进程和线程之间的区别是什么？