常常被人问到，会不会写C++，曾经以为了解对面对象编程，了解qt等开源的库之后，就可以称之为会写C++了。但是深入了解之后就会发现，C++其实并不是这么简单。作为本专题的第一篇记录，将从内存分配机制开始深入的剖析C++。

一 C++ 内存分配方式

 在C++中内存被分为五个区分别是：堆、栈、自由存储区、全局/静态存储区、常量存储区。

• 栈：是分配给函数局部变量的存储单元，函数结束后，该变量的存储单元自动释放，效率高，分配的空间有限。
• 堆：由new创建，由delete释放的动态内存单元。如果用户不释放该内存，程序结束时，系统会自动回收。
• 自由存储区：由malloc创建，由free释放的动态内存单元，与堆类似。
• 全局（静态）存储去：全局变量和静态变量占一块内存空间。
• 常量存储区：存储常量，内容不允许更改。
  
  引用自ladybai

 一般而言对于程序员，我们只需要去关注堆和栈的概念。相比堆，栈大量减少了内存的碎片问题，并且计算机在系统底层提供专门的指令执行，而new的机制相比更为复杂所以分配效率相较于栈更慢。

二 内存分配失败

 根据许多血一般的教训，下列的代码在动态分配内存的时候至关重要。

1
2
3
4
5

object* c = new object();
//在较新的标准中，使用 new（nothrow） 才会出现分配失败时返回nullptr 
if(c==nullptr){
    //错误处理机制
}

 但是其实在较新的C++标准中，出现内存分配失败时会抛出

1

std::bad_alloc

 但是针对这个我们主要需要意识到一个问题，内存的分配可能失败。

三 new/operator new/placement new

 为了防止反复的释放内存，C++除了最基本的new操作之外还提供了placement new的操作。下面简单介绍这三种不同的new操作

• 运算符 new = 先调用函数 operator new 分配空间 + 然后调用构造函数。
• 对于operator new 函数内部，他是通过再调用malloc函数，进行空间分配的（当然也可以重写一个自己的空间分配器）。
• placement new 指的是，不进行分配空间，而是在指定的空间上面进行调用构造函数。当然，在析构的时候，也只能显示的调用析构函数。（因为并不是真正的释放空间）
  
  引用自爱秋刀鱼的猫

 下面简单给出new的代码。

1
2
3

object* a = new object(); 
char* chunk = new(nothrow) char[10];
object* b = new (chunk) object();

 那么其实来说就是上面的两种new，然后operator new的含义应该是仅分配内存但是不初始化函数。

 针对大多数场景，我们使用普通的new可以完成绝大多数任务。但是极少数情况，我们可能需要反复利用一块极大的内存空间，此时利用placement new可以减少内存空间的申请释放所消耗的时间。

四 总结

 本篇主要简要介绍了C++内存分配的机制，并且了解了针对大块内存反复申请释放采用placement new的操作。本模块将持续更新，介绍更多关于C++更为深入的内容。

 发现时间久了脑子稍微有点糊，今天不想总结新的面试知识了，为了保持工作热度，回顾一下以前学习的知识。所以在在这里稍微总结一下迪杰斯特拉算法。也称最短路算法。

一 基础版n^2实现

1
2
3
4
5
6
7
8
9
10
11
12

memset(v, 0, sizeof(v)); 
for(int i = 0; i < n; i++) 
    d[i] = (i==0 ? 0 : INF); 
for(int i = 0; i < n; i++) {  
    int x, m = INF;  
    for(int y = 0; y < n; y++) 
        if(!v[y] && d[y] <= m) 
            m = d[y], x = y; 
    v[x] = 1;  
    for(int y = 0; y < n; y++) 
        d[y] = min(d[y], d[x] + w[x][y]); 
}

二 利用边集和优先级队列Mlog(N)实现

 首先需要定义边，边的定义如下。

1
2
3
4
5
6

struct DistNode {
  int d, u;
  bool operator < (const HeapNode& rhs) const {
    return d > rhs.d; //这样一来，队列中在最顶层的是最小值
  }
}

 使用优先级队列进行优化。

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

priority_queue<Node> q;
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;i++)
    d[i] = INF;
d[1] = 0;
q.push(make_pair(d[1],1));
while(!q.empty()) {
    Node t = q.top();q.pop();
    if(vis[t.second])continue;
    vis[t.second] = 1;
    for(int i = 1;i <= n;i++)
        if(!vis[i] && d[i] > t.first+G[t.second][i]) {
            d[i] = t.first+G[t.second][i];
            q.push(make_pair(d[i],i));
   }
}

 算法比较简单暂时先不做过多的讲解，然后更新这个主要还有一个原因就是回家了但是不想划水太严重。所以暂时先更新这个不带过多讲解的版本啦。等23号正式开始给暑期集训讲课的时候在对内容进行更深一步的优化。

 再次简介一下这个算法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如何利用内核模型进行编程，但是由于缺少编程经验，暂时尚未掌握这些操作在实习开发时如何运用。希望未来能对这个领域进行更深一步的理解，届时将再次更新总结对内核模型的理解。

 紧随初窥http（1），这次探索的是现代网站常用的加密协议https。https的主要功能是确保web安全。它主要弥补了http下面的几个不足：

使用明文通信，内容可能会被窃听

无法验证通信方的身份，可能存在伪装的情况

无法验证报文的完整性，报文可能遭到修改。

 这些问题通常会出现在所有非加密的信息传输协议中。为了解决上述的三个问题https应运而生。

一 什么是https

 利用SSL或者TLS的组合使用，加密HTTP的通信内容。通过SSL建立安全通信线路之后，就可以在这条线路上进行HTTP通信。与SSL组合使用的HTTP被称为HTTPS或者HTTP over SSL。

二 对称加密非对称加密

 对称加密和非对称加密是我们常常使用的加密算法，对称加密时通信双方使用同一个密钥，此时如何保障该密钥的传输成为一个重大难题，通常来说在一些必要的情况下设备厂商会在设备内预置一些密钥对，这样在一定程度上保证通信安全。而非对称加密，一对密钥由公钥和私钥组成，私钥解密公钥加密数据，公钥解密私钥加密数据。私钥只能由一个设备保管，但是公钥可以公开给所有人，根据算法相关的知识我们可以知道，这种通信方式更为安全，但是传输速度收到加密解密速度的影响。

 所以在https中，同时使用到了对称加密和非对称加密，非对称加密主要用于服务器的验证，对称加密主要用于大量数据的传输，利用对称加密和非对称加密的特点，共同解决http数据传输时的安全问题。

三 https过程详解

 关于HTTPS安全通信机制和HTTPS的通信步骤，不同人有不同的理解办法，这里引用《图解http》里面的内容来详细介绍这一过程。

摘选书中的内容主要分为下面12个步骤。

1. 客户端通过发送Client Hello报文开始SSL通信。报文中包含客户端支持的SSL的指定版本、加密组件（Cipher Suite）列表（所使用的加密算法及密钥长度等）。
2. 服务器可进行SSL通信时，会以Server Hello报文作为应答。和客户端一样，在报文中包含SSL版本以及加密组件。服务器的加密组件内容是从接收到的客户端加密组件内筛选出来的。
3. 之后服务器发送Certificate 报文。报文中包含公开密钥证书。
4. 最后服务器发送Server Hello Done报文通知客户端，最初阶段的SSL握手协商部分结束。
5. SSL第一次握手结束之后，客户端以Client Key Exchange 报文作为回应。报文中包含通信加密中使用的一种被称为 Pre-master secret的随机密码串。该报文已用步骤3中的公开密钥进行加密。
6. 接着客户端继续发送Change Cipher Spec报文。该报文会 提示服务器，在此报文之后的通信会采用Pre-master secret 密钥加密。
7. 客户端发送Finished报文。该报文包含连接至今全部报文 的整体校验值。这次握手协商是否能够成功，要以服务器是否能够正确解密该报文作为判定标准。
8. 服务器同样发送Change Cipher Spec报文。
9. 服务器同样发送Finished报文。
10. 服务器和客户端的Finished 报文交换完毕之后，SSL连接就算建立完成。当然，通信会受到SSL的保护。从此处开始进行应用层协议的通信，即发送HTTP请求。
11. 应用层协议通信，即发送HTTP响应。
12. 最后由客户端断开连接。断开连接时，发送close_notify报文。上图做了一些省略，这步之后再发送TCP FIN报文来关闭与TCP 的通信。