头条三面凉经分析

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

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

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

 然后说实话看到这个问题简直是惊呆了,课程里面确实没有详细学习过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、非阻塞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编程

 对于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()

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

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

一 非阻塞IO

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

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模型主要存在以下的问题 3

  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源码。 4

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(2)——加密版本的http协议https协议

 紧随初窥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 的通信。

数据结构基础总结

 经过漫长的等待后,果然头条的面试挂掉了。突然发现自己打了这么久的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.需要更稳定安全时,适合选择进程;需要速度时,选择线程更好。

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

初窥http(1)——浏览器中输入url后到底发生了什么

 在学校里学习计算机网络的过程中,由于《计算机网络》课本内容较为底层基础,许多人在学习完这本书后都会产生一定的困惑。譬如,现在互联网有哪些地方运用到了哪些协议,这些协议最新的标准是什么样子的等等。为了解决心中的困惑,我决定先对日常中最常用的http-web中所采用的协议进行更深一步的了解,为此我在图灵社区中购置了《图解http》一书。接下来将按照自己的思路从书中获取一些问题的答案。

 本文是购置该书籍后发表的第一篇记录,在这篇记录里,我将揭秘在浏览器中输入url后发生的一系列事情。

浏览器中输入url后主要会发生下面的几件事

一 负责域名解析的DNS服务

 计算机可以被赋予ip地址,同样的也可以被赋予主机名和域名。例如本博客的ip地址是185.199.109.153(github io服务器地址),域名地址为 blog.100innovate.com。我们通常使用域名去访问不同的计算机和网站,域名相比一串数字来说更有利于人们的记忆,但是计算机更擅长于处理ip地址这样的数字。

 为了解决计算机和人的矛盾,DNS服务在这个时候就产生了,通过DNS服务我们可以通过域名查询ip,或者利用ip查询域名。(通常而言,人们仅利用域名查询ip,很少利用ip查询域名)

 在浏览器中输入url并键入回车后的第一步,浏览器将会向DNS服务器发送查询请求,从而获取目标服务器的ip地址。

二 互联网的基础TCP/IP协议

 计算机想要相互通信,就需要一个标准的数据交换协议,这个协议就是TCP/IP协议。通常而言浏览器访问web网站时采用的是TCP协议,TCP协议是一种面向连接的、可靠的、基于字节流的传输层通信协议,为了保证通信的可靠新,首先需要进行三次握手,三次握手的主要流程为:

1.客户端向服务器端发送SYN标记的数据包

2.服务器端向客户端发送SYN/ACK标记的数据包

3.客户端向服务器端发送ACK标记的数据包

 采用三次握手而不是两次握手有许多原因,原因之一是防止延期到达的数据包传输到服务器,服务器会因此创建一个无效的连接。

三 通过HTTP协议传输数据

 HTTP协议的职责是生成针对目标Web服务器的HTTP请求报文,主要有如下的请求方法:

GET:获取资源

POST:传输实体主体

HEAD:获取报文首部

PUT:传输文件

DELETE:删除文件

OPTIONS:询问支持的方法

TRACE:追踪路径

……

 利用上述的数种请求报文向服务器发送请求报文,从而获取用户需要访问的内容。请求报文主要包含请求方法、URI、协议版本三个信息。

 在向服务器发送完请求报文后,服务器会返回请求的结果。当然每一次返回的结果并非绝对正确,为了表达服务器对用户请求的各种状态,http协议设置了规定了状态码,通过返回状态码告知浏览器服务器处理的情况,状态码通常的定义如下:

状态码 类别 含义
1XX Informational(信息性状态码) 接收的请求正在处理
2XX Success(成功状态码) 请求正常处理完毕
3XX Redirection(重定向状态码) 需要进行附加操作以完成请求
4XX Client Error(客户端错误状态码) 服务器无法处理请求
5XX Server Error(服务器错误状态码) 服务器处理请求出错

 通常来说,只要遵守上述状态码的规则,服务提供商可以自行创建状态码。

 通过上述请求协议和服务器返回报文,最终浏览器可以获得用户需要的数据和信息。

四 浏览器解析并渲染页面

 在浏览器成功获取html信息后,将会按照顺序从头至尾解析html文件,在解析到外部的css、js等其他外部资源文件的时候,根据服务器、浏览器的版本不同将会直接向服务器请求资源文件,或者重新建立TCP连接,然后请求资源文件。值得一提的是,在解析html文件时,浏览器将会构建DOM树,为了加速这一过程,浏览器还会使用预解析等功能。

 在完成html的解析后,浏览器还需要根据浏览器的窗口位置等信息,逐像素的将网页绘制出来。最终我们可以获得想要看到的网页。

五 小结

 通过对《图解http》进行全篇大致浏览,解决了一大问题。但是需要学习的仍然还有人多,譬如现代浏览器一些处理机制问题以及近年来我们常常使用的https与http有什么不同,这些疑惑就留到日后逐一破解。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×