PHP面试网

1、应用程序中调用read() 方法，这里会涉及到一次上下文切换（用户态->内核态），底层采用DMA（direct memory access）读取磁盘的文件，并把内容存储到内核地址空间的读取缓存区。

操作系统检测到进程向I/O设备发起请求后就暂停进程的运行，怎么暂停运行呢？

很简单：只需要记录下当前进程的运行状态并把CPU的PC寄存器指向其它进程的指令就可以了。
进程有暂停就会有继续执行，因此操作系统必须保存被暂停的进程以备后续继续执行，显然我们可以用队列来保存被暂停执行的进程。

注意：现代磁盘向内存copy数据时无需借助CPU的帮助，这就是所谓的DMA（Direct Memory Access）。

实际上：操作系统中除了有阻塞队列之外也有就绪队列，所谓就绪队列是指队列里的进程准备就绪可以被CPU执行了。
你可能会问为什么不直接执行非要有个就绪队列呢？

答案很简单：那就是僧多粥少，在即使只有1个核的机器上也可以创建出成千上万个进程，CPU不可能同时执行这么多的进程，因此必然存在这样的进程，即使其一切准备就绪也不能被分配到计算资源，这样的进程就被放到了就绪队列。

当进程A被暂停执行后CPU是不可以闲下来的，因为就绪队列中还有嗷嗷待哺的进程B，这时操作系统开始在就绪队列中找下一个可以执行的进程，也就是这里的进程B。
此时操作系统将进程B从就绪队列中取出，找出进程B被暂停时执行到的机器指令的位置，然后将CPU的PC寄存器指向该位置，这样进程B就开始运行啦。

此后磁盘终于将全部数据都copy到了进程A的内存中，这时磁盘通知操作系统任务完成啦，你可能会问怎么通知呢？这就是中断。
操作系统接收到磁盘中断后发现数据copy完毕，进程A重新获得继续运行的资格，这时操作系统小心翼翼的把进程A从阻塞队列放到了就绪队列当中。

注意：从前面关于就绪状态的讨论中我们知道，操作系统是不会直接运行进程A的，进程A必须被放到就绪队列中等待，这样对大家都公平。

此后进程B继续执行，进程A继续等待，进程B执行了一会儿后操作系统认为进程B执行的时间够长了，因此把进程B放到就绪队列，把进程A取出并继续执行。

注意：操作系统把进程B放到的是就绪队列，因此进程B被暂停运行仅仅是因为时间片到了而不是因为发起I/O请求被阻塞。

进程A继续执行，此时buff中已经装满了想要的数据，进程A就这样愉快的运行下去了，就好像从来没有被暂停过一样

2、由于应用程序无法读取内核地址空间的数据，如果应用程序要操作这些数据，必须把这些内容从读取缓冲区拷贝到用户缓冲区。这个时候，read() 调用返回，且引发一次上下文切换（内核态->用户态），现在数据已经被拷贝到了用户地址空间缓冲区，这时，如果有需要，应用程序可以操作修改这些内容。

3、我们最终目的是把这个文件内容通过Socket传到另一个服务中，调用Socket的send()方法，这里又涉及到一次上下文切换（用户态->内核态），同时，文件内容被进行第三次拷贝，被再次拷贝到内核地址空间缓冲区，但是这次的缓冲区与目标套接字相关联，与读取缓冲区没有半点关系。

4、send()调用返回，引发第四次的上下文切换，同时进行第四次的数据拷贝，通过DMA把数据从目标套接字相关的缓存区传到协议引擎进行发送。

"在整个过程中，过程1和4是由DMA负责，并不会消耗CPU，只有过程2和3的拷贝需要CPU参与

如果在应用程序中，不需要操作内容，过程2和3就是多余的，如果可以直接把内核态读取缓存冲区数据直接拷贝到套接字相关的缓存区，是不是可以达到优化的目的？

TCP(Transmission Control Protocol)　传输控制协议

三次握手

TCP是主机对主机层的传输控制协议，提供可靠的连接服务，采用三次握手确认建立一个连接:

位码即tcp标志位,有6种标示:

SYN(synchronous建立联机) 同步报文段

ACK(acknowledgement 确认)

PSH(push传送)

FIN(finish结束) 结束报文段

RST(reset重置) 复位报文段

URG(urgent紧急) 紧急指针

Sequence number(顺序号码)

Acknowledge number(确认号码)

客户端TCP状态迁移：

CLOSED->SYN_SENT->ESTABLISHED->FIN_WAIT_1->FIN_WAIT_2->TIME_WAIT->CLOSED

服务器TCP状态迁移：

CLOSED->LISTEN->SYN收到->ESTABLISHED->CLOSE_WAIT->LAST_ACK->CLOSED

各个状态的意义如下： 

LISTEN - 侦听来自远方TCP端口的连接请求； 

SYN-SENT -在发送连接请求后等待匹配的连接请求； 

SYN-RECEIVED - 在收到和发送一个连接请求后等待对连接请求的确认； 

ESTABLISHED- 代表一个打开的连接，数据可以传送给用户； 

FIN-WAIT-1 - 等待远程TCP的连接中断请求，或先前的连接中断请求的确认；

FIN-WAIT-2 - 从远程TCP等待连接中断请求； 

CLOSE-WAIT - 等待从本地用户发来的连接中断请求； 

CLOSING -等待远程TCP对连接中断的确认； 

LAST-ACK - 等待原来发向远程TCP的连接中断请求的确认； 

TIME-WAIT -等待足够的时间以确保远程TCP接收到连接中断请求的确认； 

CLOSED - 没有任何连接状态；

TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接，如图1所示。

（1）第一次握手：建立连接时，客户端A发送SYN包（SYN=j）到服务器B，并进入SYN_SEND状态，等待服务器B确认。

（2）第二次握手：服务器B收到SYN包，必须确认客户A的SYN（ACK=j+1），同时自己也发送一个SYN包（SYN=k），即SYN+ACK包，此时服务器B进入SYN_RECV状态。

（3）第三次握手：客户端A收到服务器B的SYN＋ACK包，向服务器B发送确认包ACK（ACK=k+1），此包发送完毕，客户端A和服务器B进入ESTABLISHED状态，完成三次握手。

完成三次握手，客户端与服务器开始传送数据。

确认号：其数值等于发送方的发送序号 +1(即接收方期望接收的下一个序列号)。

图1 TCP三次握手建立连接  

这样就会出现很多长条的分割，对于KDTree来说是很不利的。

为了避免这种情况，需要修改一下算法，纬度的选择的依据为数据范围最大的那一维作为分割纬度，之后也是选中这个纬度的中间节点作为轴点，然后进行分割，分割出来的结果是：

这样的结果对于最邻近搜索是非常友好的。

但是这样做还是有一些不好，就是在树上很可能有一些空的节点，当要限制树的高度的时候，这种方法就不合适了。

构建示例

二维样例：{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}

构建步骤：

1、初始化分割轴：

发现x轴的方差较大，所以，最开始的分割轴为x轴。

2、确定当前节点：

对{2，5，9，4，8，7}找中位数，发现{5,7}都可以，这里我们选择7，也就是(7,2);

3、划分双支数据：

在x轴维度上，比较和7的大小，进行划分：

左支：{(2,3)，(5,4)，(4,7)}

右支：{(9,6)，(8,1)}

4、更新分割轴：

一共就两个维度，所以，下一个维度是y轴。

5、确定子节点：

左节点：在左支中找到y轴的中位数(5,4)，左支数据更新为{(2,3)}，右支数据更新为{(4,7)}

右节点：在右支中找到y轴的中位数(9,6)，左支数据更新为{(8,1)}，右支数据为null。

6、更新分割轴：

下一个维度为x轴。

7、确定(5,4)的子节点：

左节点：由于只有一个数据，所以，左节点为(2,3)

右节点：由于只有一个数据，所以，右节点为(4,7)

8、确定(9,6)的子节点：

左节点：由于只有一个数据，所以，左节点为(8,1)

右节点：右节点为空。

最终，就可以构建整个的kd-tree了。

邻近搜索

给定一个KDTree和一个节点，求KDTree中离这个节点最近的节点.(这个节点就是最临近点)

这里距离的求法用的是欧式距离。

基本的思路很简单：首先通过二叉树搜索（比较待查询节点和分裂节点的分裂维的值，小于等于就进入左子树分支，等于就进入右子树分支直到叶子结点），顺着“搜索路径”很快能找到最近邻的近似点，也就是与待查询点处于同一个子空间的叶子结点；然后再回溯搜索路径，并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点，如果有可能，则需要跳到其他子结点空间中去搜索（将其他子结点加入到搜索路径）。重复这个过程直到搜索路径为空。

这里还有几个细节需要注意一下，如下图，假设标记为星星的点是 test point， 绿色的点是找到的近似点，在回溯过程中，需要用到一个队列，存储需要回溯的点，在判断其他子节点空间中是否有可能有距离查询点更近的数据点时，做法是以查询点为圆心，以当前的最近距离为半径画圆，这个圆称为候选超球（candidate hypersphere），如果圆与回溯点的轴相交，则需要将轴另一边的节点都放到回溯队列里面来。

判断轴是否与候选超球相交的方法可以参考下图：

下面再用一个例子来具体说一下查询的过程。

假设我们的k-d tree就是上面通过样本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}创建的。
我们来查找点(2.1,3.1)，在(7,2)点测试到达(5,4)，在(5,4)点测试到达(2,3)，然后search_path中的结点为<(7,2), (5,4), (2,3)>，从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141；
然后回溯至(5,4)，以(2.1,3.1)为圆心，以dist=0.141为半径画一个圆，并不和超平面y=4相交，如下图，所以不必跳到结点(5,4)的右子空间去搜索，因为右子空间中不可能有更近样本点了。
于是在回溯至(7,2)，同理，以(2.1,3.1)为圆心，以dist=0.141为半径画一个圆并不和超平面x=7相交，所以也不用跳到结点(7,2)的右子空间去搜索。
至此，search_path为空，结束整个搜索，返回nearest(2,3)作为(2.1,3.1)的最近邻点，最近距离为0.141。

再举一个稍微复杂的例子，我们来查找点(2,4.5)，在(7,2)处测试到达(5,4)，在(5,4)处测试到达(4,7)，然后search_path中的结点为<(7,2), (5,4), (4,7)>，从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202；
然后回溯至(5,4)，以(2,4.5)为圆心，以dist=3.202为半径画一个圆与超平面y=4相交，如下图，所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中，现在search_path中的结点为<(7,2), (2, 3)>；另外，(5,4)与(2,4.5)的距离为3.04 < dist = 3.202，所以将(5,4)赋给nearest，并且dist=3.04。
回溯至(2,3)，(2,3)是叶子节点，直接平判断(2,3)是否离(2,4.5)更近，计算得到距离为1.5，所以nearest更新为(2,3)，dist更新为(1.5)
回溯至(7,2)，同理，以(2,4.5)为圆心，以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索。

至此，search_path为空，结束整个搜索，返回nearest(2,3)作为(2,4.5)的最近邻点，最近距离为1.5。

所以在搜索中可能会出现不同的情况，比如下面的两张图就是比较极端的两个例子。

代码清单

以下是k-d树的c++代码实现，包括建树过程和搜索过程。算法main函数输入k-d树训练实例点，算法会完成建树操作，随后可以输入待查询的目标点，程序将会搜索K-d树找出与输入目标点最近邻的训练实例点。本程序只实现了1近邻搜索，如果要实现k近邻搜索，只需对程序稍作修改。比如可以对每个结点添加一个标记，如果已经输出该结点为最近邻结点，那么就继续查找次近邻的结点，直到输出k个结点后算法结束。