前一段时间碰到一个面试题，问题是ping命令使用的是什么协议，这个问题的答案就是今天的主角ICMP协议。但是那个时候只知其名不知其今天就查阅资料简要总结ICMP协议。

一 ICMP简介

 ICMP协议是一个网络层协议。 一个新搭建好的网络，往往需要先进行一个简单的测试，来验证网络是否畅通；但是IP协议并不提供可靠传输。如果丢包了，IP协议并不能通知传输层是否丢包以及丢包的原因。
所以我们就需要一种协议来完成这样的功能–ICMP协议。

 ICMP协议的功能主要有：

1. 确认IP包是否成功到达目标地址
2. 通知在发送过程中IP包被丢弃的原因

 需要注意的是ICMP是基于IP协议工作的，但是它并不是传输层的功能，因此仍然把它归结为网络层协议 。所以如果我们问ping的端口时什么的时候，我们应该回答的是ping命令基于ICMP是一个网络层的概念，而端口是传输层的概念，所以ICMP不需要关注端口号。

二 报文格式

 用来传送ICMP 报文的IP 数据包上实际上有不少字段。但是实际上与ICMP 协议相关的只有7 个子段。

1）协议；2）源IP 地址；3）目的IP 地址；4）生存时间；这四个包含在IP 首部的字段。
5）类型；6）代码；7）选项数据；这三个包含在ICMP数据部分的字段。

 这里面，1)协议字段值是1。2)和3)是用来交流ICMP 报文的地址信息，没有特殊意义。对于理解ICMP 本身，重要的是5)，6)，7)三个字段。这里面的可以称为核心的重要字段是5)类型，6)代码这两个字段。所有ICMP 用来交流错误通知和信息询问的报文，都是由类型和代码的组合来表示的。RFC 定义了15种类型。“报文不可到达”这样的错误通知和“回送请求”这样的信息查询是由类型字段来区分的。ICMP报文由类型来表达它的大概意义，需要传递细小的信息时由代码来分类。进一步，需要向对方传送数据的时候，用7）选项数据字段来放置。引用自_毛台

三 常用的ICMP协议命令

1. ping
   
   （1）能验证网络的连通性
   
   （2）会统计响应时间和TTL(IP包中的Time To Live，生存周期)
2. tracert
   
    打印出可执行程序主机，一直到目标主机之前经历多少路由器。

四 安全问题

引用自_毛台

 作为恶意使用ICMP 的最有代表性的例子，也就是所谓的 “ping 洪水”的攻击。它利用ping 的原理，向目标服务器发送大量的ICMP 回送请求。这是黑客向特定的机器连续发送大量的ICMP 回送请求报文。目标机器回答到达的ICMP 回送请求已经用尽全力了，原来的通信处理就变得很不稳定了。进一步，目标机器连接的网络也可能由于大量的ICMP 数据包而陷入不可使用的状态。

 与ping 洪水相似，以更加恶劣的使用方法而闻名的是称为“smurf”的攻击手法。smurf 同样，黑客恶意的使用ICMP 回送请求报文。这一点同ping 洪水是相同的。不过在smurf，对ICMP 回送请求实施了一些加工。源IP 地址被伪装成攻击对象服务器的地址，目标地址也不是攻击对象服务器的地址，而是成为中转台的网络的广播地址。

 再次简介一下这个算法LRU全称是Least Recently Used,即最近最久未使用的意思。算法每一次将最久未使用的块更新出去。但是呢上一篇笔记附上的百度的代码复杂度实在不堪入目，所以该写还是得写，刚好也分享给大家这个百度前几页没有的O(1)算法。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include<iostream>
#include<vector>

using namespace std;

const int cache_size = 10;
const int memory_size = 100;

struct cache_node
{
    cache_node* l_link;   // 栈的链接
    cache_node* r_link;
    int cache_id;       // cache_id
    int cache_val;      // chache 映射位置
};

void init(cache_node*&head,cache_node*&tail)
{
    head=new cache_node({nullptr,nullptr,0,-1});
    cache_node *tmp=head;
    for(int i(1); i<cache_size; i++)
    {
        cache_node *x = new cache_node({tmp,nullptr,0,-1});
        tmp->r_link=x;
        tmp = x;
    }
    tail = tmp;
}

int main()
{
    vector<cache_node*>memory_to_cache(memory_size,nullptr);
    cache_node *head,*tail;
    init(head,tail);
    int n;
    cin>>n;
    //n代表输入的数组组数，然后x代表这一次访问的对象，平均每次访问更新需要6次赋值，所以这个不是一个原子操作。假如cpu内部实现真的存在这种模式,内部大概会有许多门电路来使这多次赋值成为一个原子操作。
    for(int i(0); i<n; i++)
    {
        int x; 
        cin>>x;
        if(memory_to_cache[x]==nullptr)
        {
            cout<<tail->cache_val<<"被清出"<<endl;
            cout<<x<<"移入栈顶"<<endl;
            if(tail->cache_val!=-1)
                memory_to_cache[tail->cache_val]=nullptr;
            tail->l_link->r_link=nullptr;
            tail->r_link=head;
            head->l_link=tail;
            tail=tail->l_link;
            head=head->l_link;
            head->l_link=nullptr;
            head->cache_val=x;
            memory_to_cache[x]=head;
        }
        else
        {
            if(head==memory_to_cache[x])
                continue;
            else
            {
                cout<<x<<"移入栈顶"<<endl;
                memory_to_cache[x]->l_link->r_link=memory_to_cache[x]->r_link;
                if(memory_to_cache[x]->r_link!=nullptr)
                    memory_to_cache[x]->r_link->l_link=memory_to_cache[x]->l_link;
                else
                {
                    tail=memory_to_cache[x]->l_link;
                }
                memory_to_cache[x]->l_link=nullptr;
                memory_to_cache[x]->r_link=head;
                head->l_link=memory_to_cache[x];
                head=memory_to_cache[x];
            }
        }
    }
    return 0;
}

 完整的代码就是上面附的这一些了，然后由于代码比较简单主要是考察逻辑，所以也不再附更多的注释了。值得注意的是上面的代码的第一层if else中有数行功能相同，其实可以通过调整代码位置使其合并。但是过度合并可能会造成一些可读性缺失，这里就不再做深层次的代码优化了。

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

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

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

 然后说实话看到这个问题简直是惊呆了，课程里面确实没有详细学习过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。加油！！！！！！

 这里主要有四个概念，分别是同步io、异步io、阻塞io、非阻塞io。本文主要参照tengteng_的博客，简单总结这四个基本概念的含义。

一 同步

 所谓同步，就是在发出一个功能调用时，在没有得到结果之前，该调用就不返回。也就是必须一件一件事做,等前一件做完了才能做下一件事。

 例如普通B/S模式（同步）：提交请求->等待服务器处理->处理完毕返回 这个期间客户端浏览器不能干任何事

二 异步

 异步的概念和同步相对。当一个异步过程调用发出后，调用者不能立刻得到结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者。

 例如 ajax请求（异步）: 请求通过事件触发->服务器处理（这是浏览器仍然可以作其他事情）->处理完毕

三 阻塞

 阻塞调用是指调用结果返回之前，当前线程会被挂起（线程进入非可执行状态，在这个状态下，cpu不会给线程分配时间片，即线程暂停运行）。函数只有在得到结果之后才会返回。

 有人也许会把阻塞调用和同步调用等同起来，实际上他是不同的。对于同步调用来说，很多时候当前线程还是激活的，只是从逻辑上当前函数没有返回,它还会抢占cpu去执行其他逻辑，也会主动检测io是否准备好。

四 非阻塞

 非阻塞和阻塞的概念相对应，指在不能立刻得到结果之前，该函数不会阻塞当前线程，而会立刻返回。

再简单点理解就是：

1. 同步，就是我调用一个功能，该功能没有结束前，我死等结果。
2. 异步，就是我调用一个功能，不需要知道该功能结果，该功能有结果后通知我（回调通知）。
3. 阻塞，就是调用我（函数），我（函数）没有接收完数据或者没有得到结果之前，我不会返回。
4. 非阻塞，就是调用我（函数），我（函数）立即返回，通过select通知调用者

五 总结

同步IO和异步IO的区别就在于：数据拷贝的时候进程是否阻塞

阻塞IO和非阻塞IO的区别就在于：应用程序的调用是否立即返回

 综上所述对此进行一些总结，通过学习生活中的观察我们可以发现，在我们日常生活中写的程序大多数都是同步的，通常来说我们的程序都需要立即执行得到结果。但是我们可以利用多线程或者进程设计一个异步的程序，在程序运行到一定的时候通过创建进程、线程来处理耗时较长的程序。而后在需要运算结果的时候对运算状态进行查询，这样可以使一个进程同时处理多种不同的任务。

本文引用自https://blog.csdn.net/crazy_tengt/article/details/79225913

 真的是太懵圈了，突然发现操作系统还有调度算法这么一说。虽说操作系统课程已经过去了一年多了但是这种基础知识着实不能忘。

一 先来先服务算法

 先来先服务算法是操作系统调度算法中最简单的算法，该算法可以用于作业调度，同样也可以用于进程调度，调度的策略非常简单，就是先来先服务。

二 短作业优先算法

 短作业有限算法，同样作为操作系统调度算法中非常简单的算法，调度策略是优先选取运行所需时间短的任务。

三 高权值优先算法

 这里分为抢占式和非抢占式算法，抢占式算法在高权值的任务进入时直接挤掉当前运行的任务。非抢占式算法在任务执行结束后，选取权值最高的任务执行。

四 高响应比优先算法

 由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先权又相当于响应比RP。作业优先级随等待时间增高而增高。随着等待时间增加，将会越来越快的被分配到cpu

五 时间片轮转算法

 给队列中的每一个任务分配固定的时间片，然后每个任务执行完固定的时间片后将被轮出。但是这种算法如果时间片大小过大，则会造成cpu资源的浪费，如果时间片过小进程间不断切换也会浪费cpu资源。

六 多级反馈队列算法

 与时间片轮转算法非常相似，但是与其不同的式，拥有多个队列，当任务在第一个队列分配的时间片中无法完成全部任务时，将会被置入第二个队列中，分配给其的时间片大小会越来越大。由于大多数任务我们没有办法知道确切的运行时间。所以这种调度算法是目前最被广泛使用的调度算法。

 下午马上就迎来新一轮面试了，突然想到昨天面试官提问关于数据库的问题，自己对这方面可以说是一窍不通，那么针对现代数据库，最重要的一环是建立索引值。索引可以极大的提升搜索的效率。下面以mysql为例，总结五种不同的索引方式。

一 普通索引

 普通索引是最常见最基础的索引，建立一个普通索引没有任何限制条件，是我们平时最常利用的索引方式。

二 唯一索引

 唯一索引与普通索引类似，不同的是唯一索引的值必须唯一，但允许存在空值。

三 主键索引

 与唯一索引类似，但是主键索引除了内容必须唯一以外，内容不允许存在空值，而且一张表中只能包含一个主键索引。

四 组合索引

 组合索引使用多个列的值构成索引，专门用于组合搜索的情况，其要求组合情况唯一。组合索引的效率大于索引合并。

五 全文索引

 主要用来查找文本中的关键字，而不是直接与索引中的值相比较。全文索引跟其它索引大不相同，它更像是一个搜索引擎，而不是简单的where语句的参数匹配。对于较大的表，全文索引需要消耗大量的硬盘空间，这是一种需要慎重使用的索引方式。

 本来以为自己的对于操作系统的基本理解应该是没有什么欠缺的，但是去搜刮了一波资料后发现自己好像啥都不会，本篇将主要总结：进程状态，CPU调度单位，中断实现机制，软硬中断的区别。

一 进程状态

 通常而言，进程的状态分为两大类，一种是三模态，一种是五模态，它们的简介分别如下：

一个进程从创建而产生至撤销而消亡的整个生命期间，有时占有处理器执行，有时虽可运行但分不到处理器、有时虽有空闲处理器但因等待某个事件的发生而无法执行，这一切都说明进程和程序不相同，它是活动的且有状态变化的，这可以用一组状态加以刻画。为了便于管理进程，一般来说，按进程在执行过程中的不同情况至少要定义三种不同的进程状态：

1. 运行(running)态：进程占有处理器正在运行。
2. 就绪(ready)态：进程具备运行条件，等待系统分配处理器以便运行。
3. 等待(wait)态：又称为阻塞(blocked)态或睡眠(sleep)态，指进程不具备运行条件，正在等待某个事件的完成。

通常，一个进程在创建后将处于就绪状态。每个进程在执行过程中，任意时刻当且仅当处于上述三种状态之一。同时，在一个进程执行过程中，它的状态将会发生改变。引起进程状态转换的具体原因如下：

1. 运行态一一等待态：等待使用资源或某事件发生，如等待外设传输;等待人工干预。
2. 等待态一一就绪态：资源得到满足或某事件己经发生，如外设传输结束；人工干预完成。
3. 运行态一一就绪态：运行时间片到，或出现有更高优先权进程。
4. 就绪态一一运行态：CPU空闲时被调度选中一个就绪进程执行。

 在实际的工作中，进程的状态转化通常比三模态更加复杂一些，所以这里就引入了一个五模态的概念。

在一个实际的系统里进程的状态及其转换比上节叙述的复杂一些，例如，引入专门的新建态(new)和终止态(exit )。

引入新建态和终止态对于进程管理来说是非常有用的。新建态对应于进程刚刚被创建的状态，创建‘个进程要通过两个步骤，首先，是为一个新进程创建必要的管理信息；然后，让该进程进入就绪态。此时进程将处于新建态，它并没有被提交执行，而是在等待操作系统完成创建进程的必要操作。必须指出的是，操作系统有时将根据系统性能或主存容量的限制推迟新建态进程的提交。

类似地，进程的终止也要通过两个步骤，首先，是等待操作系统进行善后；然后，退出主存。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止态。进入终止态的进程以后不再执行，但依然保留在操作系统中等待善后。一旦其他进程完成了对终止态进程的信息抽取之后，操作系统将删除该进程。引起进程状态转换的具体原因如下：

1. NULL一一新建态:执行一个程序，创建一个子进程。
2. 新建态一一就绪态:当操作系统完成了进程创建的必要操作，并且当前系统的性能和内存的容量均允许。
3. 运行态一一终止态:当‘个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结。
4. 终止态一一NULL:完成善后操作。
5. 就绪态一一终止态:未在状态转换图中显示，但某些操作系统允许父进程终结子进程。
6. 等待态一一终止态:未在状态转换图中显示，但某些操作系统允许父进程终结子进程。

 但是在linux系统中，进程的五种状态与上述的五模态还有一定的差别。linux系统中进程主要包含下面的五种状态：

1. Linux进程状态：R (TASK_RUNNING)，可执行状态&运行状态(在run_queue队列里的状态)
2. Linux进程状态：S (TASK_INTERRUPTIBLE)，可中断的睡眠状态, 可处理signal
3. Linux进程状态：D (TASK_UNINTERRUPTIBLE)，不可中断的睡眠状态,　可处理signal,有延迟
4. Linux进程状态：T (TASK_STOPPED or TASK_TRACED)，暂停状态或跟踪状态,　不可处理signal,　因为根本没有时间片运行代码
5. Linux进程状态：Z (TASK_DEAD - EXIT_ZOMBIE)，退出状态，进程成为僵尸进程。不可被kill,　即不响应任务信号,　无法用SIGKILL杀死

 上述linux的五种状态在linux编程中有着非常重要的作用，这里很难三言两语将每个状态的作用详细介绍，日有有机会该部分将作为专题介绍。

二 CPU调度的最小单位

 我们知道，在操作系统中，进程是操作系统分配的最小单位，对于cpu调度的最小单位不同地方有不同的答案。许多人认为线程是执行流的最小单位，但是对于cpu调度来说，每次执行并不一定完成一个线程的全部任务。我们可以发现所有的cpu调度算法都是为进程分配时间片，所以这里可以认为，时间片是cpu调度的基本单位。

三 软中断、硬中断&&实现机制

 cpu和外部设备的速度总是不统一的，软件想要获取外部设备的状态主要有两种办法，一种是cpu不断地对所有的设备进行扫描，这样一旦设备发出信号，cpu就可以把时间告诉对应的应用程序。但是如果cpu同时连接了非常大量的外部设备，当一个设备发出信号时，cpu却在轮询其他设备，这中间的时间差会产生大量的延迟。而且cpu不断地访问空闲设备一定程序上也会浪费cpu的资源。

 所以在这里，操作系统会选择中断机制来解决这个问题。当没有中断产生的时候，cpu正常执行程序，当中断产生的时候，cpu会暂停当前进行的操作来处理中断，当中断处理完成后又将恢复执行正常程序。操作系统响应中断的基本流程如下。

产生中断——响应中断——关闭中断——保护中断——识别中断源——现场保护——中断服务——现场恢复。

 中断又常被分为软中断和硬中断对于他们的特点引用csdn博客内容：

硬中断：

1. 硬中断是由硬件产生的，比如，像磁盘，网卡，键盘，时钟等。每个设备或设备集都有它自己的IRQ（中断请求）。基于IRQ，CPU可以将相应的请求分发到对应的硬件驱动上（注：硬件驱动通常是内核中的一个子程序，而不是一个独立的进程）。
2. 处理中断的驱动是需要运行在CPU上的，因此，当中断产生的时候，CPU会中断当前正在运行的任务，来处理中断。在有多核心的系统上，一个中断通常只能中断一颗CPU（也有一种特殊的情况，就是在大型主机上是有硬件通道的，它可以在没有主CPU的支持下，可以同时处理多个中断。）。
3. 硬中断可以直接中断CPU。它会引起内核中相关的代码被触发。对于那些需要花费一些时间去处理的进程，中断代码本身也可以被其他的硬中断中断。
4. 对于时钟中断，内核调度代码会将当前正在运行的进程挂起，从而让其他的进程来运行。它的存在是为了让调度代码（或称为调度器）可以调度多任务。

软中断：

1. 软中断的处理非常像硬中断。然而，它们仅仅是由当前正在运行的进程所产生的。
2. 通常，软中断是一些对I/O的请求。这些请求会调用内核中可以调度I/O发生的程序。对于某些设备，I/O请求需要被立即处理，而磁盘I/O请求通常可以排队并且可以稍后处理。根据I/O模型的不同，进程或许会被挂起直到I/O完成，此时内核调度器就会选择另一个进程去运行。I/O可以在进程之间产生并且调度过程通常和磁盘I/O的方式是相同。
3. 软中断仅与内核相联系。而内核主要负责对需要运行的任何其他的进程进行调度。一些内核允许设备驱动的一些部分存在于用户空间，并且当需要的时候内核也会调度这个进程去运行。
4. 软中断并不会直接中断CPU。也只有当前正在运行的代码（或进程）才会产生软中断。这种中断是一种需要内核为正在运行的进程去做一些事情（通常为I/O）的请求。有一个特殊的软中断是Yield调用，它的作用是请求内核调度器去查看是否有一些其他的进程可以运行。

 这里引用百度百科介绍中断的概念。

虽然人们在谈到中断（Interrupt）时，总会拿轮询（Polling）来做“反面”例子，但中断和轮询并不是完全对立的两个概念，呃，它们是对立统一的。

“CPU执行完每条指令时，都会去检查一个中断标志位”，这句话是所有关于中断长篇大论的开场白，但很容易被人忽略，其实，这就是中断的本质。

举个例子，CPU老板是一家公司的光杆司令，所有的顾客都要他亲自跑去处理，还要跟有关部门打点关系，CPU觉得顾客和公关这两样事它一个人搞不来，这就是轮询；终于这家公司升级发展了，CPU老板请了一个秘书，所有的顾客都先由秘书经手，CPU心情好的时候就去看一下，大部分时间都忙着去公关了，这时它觉得轻松了很多，这就是中断了~~

也就是说，中断和轮询是从CPU老板的角度来看的，不管怎样，事件都还是有人来时刻跟踪才能被捕获处理，不过是老板还是秘书的问题。所有的中断（或者异步，回调等）背后都有一个轮询（循环，listener）。

 对于python的socket编程，在之前仅有非常基础的了解。通常来说我们会利用以下的代码完成我们的socket编程。

1
2
3
4
5
6
7

while True:
    # 接受一个新连接:
    sock, addr = s.accept() # 阻塞
    # 直接进行一些操作
    # or 创建新线程来处理TCP连接:
    t = threading.Thread(target=tcplink, args=(sock, addr))
    t.start()

 直接进行一些操作将会造成非常严重的阻塞问题，直观的来看，似乎采用多线程/进程的方式可以解决这个问题，但是其实并不然如果要同时响应成百上千路的连接请求，则无论多线程还是多进程都会严重占据系统资源，降低系统对外界响应效率，而线程与进程本身也更容易进入假死状态。¹

 很多人可能会采用线程池、进程池的方法减少创建和销毁进程线程的次数，降低系统因为销毁或者创建进程/线程消耗的系统资源。但是在大规模的系统中仍然可能会遇到瓶颈。所以这里我们会采用非阻塞式接口来解决这个问题。

一 非阻塞IO

 在python-socket编程中，设置setblocking的值为False(默认为True)，那么现在accept()将不再阻塞。常规的非阻塞式IO的代码如下 ²

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

while True:
    try:
        conn, addr = sock.accept()  # 被动接受TCP客户的连接，等待连接的到来，收不到时会报异常
        print('connect by ', addr)
        conn_list.append(conn)
        conn.setblocking(False)  # 设置非阻塞
    except BlockingIOError as e:
        pass

    tmp_list = [conn for conn in conn_list]
    for conn in tmp_list:
        try:
            data = conn.recv(1024) # 接收数据1024字节
            if data:
                print('收到的数据是{}'.format(data.decode()))
                conn.send(data)
            else:
                print('close conn',conn)
                conn.close()
                conn_list.remove(conn)
                print('还有客户端=>',len(conn_list))
        except IOError:
            pass

 但是从上述的代码我们可以观察到，虽然非阻塞式IO解决了阻塞的问题，一个进程可以同时干其他的任务，但是非阻塞式IO是非常不被推荐的，由于不断地while(True)可能会导致CPU资源占满，无故消耗了许多不需要消耗的系统资源。

二 多路复用IO

select模型

 把socket交给操作系统去监控，相当于找个代理人(select), 去收快递。快递到了,就通知用户，用户自己去取。

 阻塞I/O只能阻塞一个I/O操作，而I/O复用模型能够阻塞多个I/O操作，所以才叫做多路复用

 使用select以后最大的优势是用户可以在一个线程内同时处理多个socket的IO请求。用户可以注册多个socket，然后不断地调用select读取被激活的socket，即可达到在同一个线程内同时处理多个IO请求的目的。而在同步阻塞模型中，必须通过多线程的方式才能达到这个目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

s_list = [s.fileno(),]  #fileno()获取套接字的唯一描述符,每个套接字都是唯一不同的
s_dict = {}

while 1:
    list_readable,a,b = select(s_list,[],[]) #分别对应: 输入,输出,错误输出
    for i in list_readable:
        if i == s.fileno():
            conn,userinfo = s.accept()
            s_list.append(conn.fileno())
            s_dict[conn.fileno()] = conn
        else:
            cs = s_dict[i]
            recv_data = cs.recv(1024)
            if len(recv_data) <= 0:
                s_dict[i].close()
                s_dict.pop(i)
                s_list.remove(i)
            else:
                cs.send(recv_data)

 但是select模型的复杂度较高，每次会不断的轮询所负责的所有socket描述符，当某个socket有数据到达了，就通知用户进程。所以select模型主要存在以下的问题 ³

1. 最大并发数限制，因为一个进程所打开的 FD （文件描述符）是有限制的，由 FD_SETSIZE 设置，默认值是 1024/2048 ，因此 Select 模型的最大并发数就被相应限制了。当然我们也可以采用修改FD_SETSIZE从而增加最大并发数。
2. 效率问题， select 每次调用都会线性扫描全部的 FD 集合，这样效率就会呈现线性下降，把 FD_SETSIZE 改大的后果就是，大家都慢慢来，什么？都超时了。
3. 内核 / 用户空间 内存拷贝问题，如何让内核把 FD 消息通知给用户空间呢？在这个问题上 select 采取了内存拷贝方法，在FD非常多的时候，非常的耗费时间。

 上述三点可以总结为：1.连接数受限 2.查找配对速度慢 3.数据由内核拷贝到用户态消耗时间

epoll模型

 epoll模型是对select模型的改进，其效率非常高，但仅可用于Unix/Linux操作系统。由于其非常重要，这里完整摘取python源码。 ⁴

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#创建socket对象
serversocket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
#设置IP地址复用
serversocket.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
#ip地址和端口号
server_address = ("127.0.0.1", 8888)
#绑定IP地址
serversocket.bind(server_address)
#监听，并设置最大连接数
serversocket.listen(10)
print  "服务器启动成功，监听IP：" , server_address
#服务端设置非阻塞
serversocket.setblocking(False)  
#超时时间
timeout = 10
#创建epoll事件对象，后续要监控的事件添加到其中
epoll = select.epoll()
#注册服务器监听fd到等待读事件集合
epoll.register(serversocket.fileno(), select.EPOLLIN)
#保存连接客户端消息的字典，格式为{}
message_queues = {}
#文件句柄到所对应对象的字典，格式为{句柄：对象}
fd_to_socket = {serversocket.fileno():serversocket,}

while True:
  print "等待活动连接......"
  #轮询注册的事件集合，返回值为[(文件句柄，对应的事件)，(...),....]
  events = epoll.poll(timeout)
  if not events:
     print "epoll超时无活动连接，重新轮询......"
     continue
  print "有" , len(events), "个新事件，开始处理......"
  
  for fd, event in events:
     socket = fd_to_socket[fd]
     #如果活动socket为当前服务器socket，表示有新连接
     if socket == serversocket:
            connection, address = serversocket.accept()
            print "新连接：" , address
            #新连接socket设置为非阻塞
            connection.setblocking(False)
            #注册新连接fd到待读事件集合
            epoll.register(connection.fileno(), select.EPOLLIN)
            #把新连接的文件句柄以及对象保存到字典
            fd_to_socket[connection.fileno()] = connection
            #以新连接的对象为键值，值存储在队列中，保存每个连接的信息
            message_queues[connection]  = Queue.Queue()
     #关闭事件
     elif event & select.EPOLLHUP:
        print 'client close'
        #在epoll中注销客户端的文件句柄
        epoll.unregister(fd)
        #关闭客户端的文件句柄
        fd_to_socket[fd].close()
        #在字典中删除与已关闭客户端相关的信息
        del fd_to_socket[fd]
     #可读事件
     elif event & select.EPOLLIN:
        #接收数据
        data = socket.recv(1024)
        if data:
           print "收到数据：" , data , "客户端：" , socket.getpeername()
           #将数据放入对应客户端的字典
           message_queues[socket].put(data)
           #修改读取到消息的连接到等待写事件集合(即对应客户端收到消息后，再将其fd修改并加入写事件集合)
           epoll.modify(fd, select.EPOLLOUT)
        else:
           print 'closing', address, 'after reading no data'
           epoll.unregister(fd)
           connections[fd].close()
           del connections[fd]
     #可写事件
     elif event & select.EPOLLOUT:
        try:
           #从字典中获取对应客户端的信息
           msg = message_queues[socket].get_nowait()
        except Queue.Empty:
           print socket.getpeername() , " queue empty"
           #修改文件句柄为读事件
           epoll.modify(fd, select.EPOLLIN)
        else :
           print "发送数据：" , data , "客户端：" , socket.getpeername()
           #发送数据
           socket.send(msg)

#在epoll中注销服务端文件句柄
epoll.unregister(serversocket.fileno())
#关闭epoll
epoll.close()
#关闭服务器socket
serversocket.close()

 但客户端的代码基本与其他模型无疑，这里对客户端代码做基本记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#创建客户端socket对象
clientsocket = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
#服务端IP地址和端口号元组
server_address = ('127.0.0.1',8888)
#客户端连接指定的IP地址和端口号
clientsocket.connect(server_address)

while True:
    #输入数据
    data = raw_input('please input:')
    #客户端发送数据
    clientsocket.sendall(data)
    #客户端接收数据
    server_data = clientsocket.recv(1024)
    print '客户端收到的数据：'server_data
    #关闭客户端socket
    clientsocket.close()

 通过上述的这些样例，大致了解了python如何利用内核模型进行编程，但是由于缺少编程经验，暂时尚未掌握这些操作在实习开发时如何运用。希望未来能对这个领域进行更深一步的理解，届时将再次更新总结对内核模型的理解。

 经过漫长的等待后，果然头条的面试挂掉了。突然发现自己打了这么久的ACM，很多基础数据结构的概念掌握的还不是非常的牢固。这些数据结构可能并不难，特别是跳表和线段数组这样的数据结构，但是由于平日的疏忽导致这些概念有少许的以往。那么今天就要对这些掌握不是特别牢固的数据结构一一进行总结。

一 跳表

 跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。

 跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

 跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

 假设每M个元素构建索引，元素链表中总共有N个元素，那么构建的索引数如下：

第一级有：n/M 个
第二级有：n/(M^2)个元素
…….
第k级有：n/(M^k)个元素

 假设第k级为最后一级则可知，n/(M^k) = M, k = logn - 1, 再加上原始链表总共logn级平均每级搜索元素个数 = M + 1 ;

时间复杂度 = O(log(n))

空间复杂度 = n/M + n/(M^2) + … + n/(M^k) = O(n)

引用自简书liuzhengqiu

二 线段树

 了解线段树前我们需要了解二叉树，线段树是二叉树的一种，他是一颗二叉搜索树。线段树上的每一个节点代表一个区间，同样也可以理解为一个线段，搜索则是在这些线段上进行搜索从而获得答案。

 为了进一步的学习线段树，我们首先需要了解线段树的功能是什么，有过OI基础/ACM基础的同学们通常会认为线段树主要用于处理区间查询问题。但是在实际应用中可能线段树的功能比区间查询更加丰富，当然这里我们还是需要从区间查询问题开始说起。

更新点，查询区间

更新区间，查询点

更新区间，查询区间

 通常来说，利用线段树处理的问题分为上面三种，通常而言线段树的时间复杂度是O(log2(N))，线段树的空间复杂度<4n。下面通过一张图来显示线段树每个节点储存的信息，例子采用的是区间长度为10的数组。

 可以发现，每个叶子结点的值就是数组的值，每个非叶子结点的度都为二，且左右两个孩子分别存储父亲一半的区间。每个父亲的存储的值也就是两个孩子存储的值的最大值。

 通过对上图的观察我们现在可以清晰的了解线段树点更新，区间更新，点查询，区间查询的方法。具体的代码需要在网上寻找，每个人都有自己独特的写法，如果是竞赛选手，强烈建议形成自己的一套模板。

参考CSDN代码

三 线段数组

 要了解线段数组，我们需要先了解树状数组，顾名思义，树状数组即利用数组构建树形结构。这种结构相比树形结构可以极大程度的降低内存的消耗，故在比赛中我们常常利用树状数组来解决线段树的问题，而不是动态开点。

 与普通的线段树相同，利用线段数组可以轻松的完成区间的修改、查询。他的复杂度和线段树相同均为O(logN)，但是相比线段树，树状数组拥有更小的常数，所以最终运行的速度更快。

四 红黑树

红黑树具有下面五种特征：

性质1：每个节点要么是黑色，要么是红色。

性质2：根节点是黑色。

性质3：每个叶子节点（NIL）是黑色。

性质4：每个红色结点的两个子结点一定都是黑色。

性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

 红黑树是一种特殊的二叉平衡树，它通过左旋，右旋和变色来保持自平衡。他是一个非常负责的数据结构，在本篇中仅简单介绍其功能。更加丰富的内容日后会开专题介绍。

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

一 进程的基本概念

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

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

二 线程的基本概念

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

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

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

区别：

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

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

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

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

选择：

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

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

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

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

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

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