Neo's Blog

题目描述

给出一个二叉树，输入两个树节点，求它们的最低公共祖先。

一个树节点的祖先节点包括它本身。

注意：

输入的二叉树不为空；
输入的两个节点一定不为空，且是二叉树中的节点；
样例
二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
8
/ \
12 2
/ \
6 4

1. 如果输入的树节点为2和12，则输出的最低公共祖先为树节点8。

2. 如果输入的树节点为2和6，则输出的最低公共祖先为树节点2。

最普通的实现思路

实现考虑容易想到的实现思路：

第一步，找到从root到节点A的路径，计作pa；时间复杂度$O(n)$，空间复杂度$O(n)$

第二步，找到从root到节点B的路径，计作pb；时间复杂度$O(n)$，空间复杂度$O(n)$

第三步，同时遍历pa、pb，找到最后一个相同的元素，便是A、B的最低公共祖先。时间复杂度$O(n)$

综上，总的时间复杂度为$O(3n)$，空间复杂度$O(2n)$

常规的二叉树遍历讨论

拿到一个二叉树遍历的题目，

（1）我们首先要思考的是：要解决这个问题，哪种遍历方式最合适？

前序遍历、后序遍历、中序遍历还是层次遍历？

（2）其次，我们做出一个假设：假设我已经调用了dfs(child),并解决了这个子问题

（3）最后，基于上面的假设去思考如何解决整个问题。

针对上面的第一个问题，我们想要从下往上遍历整棵树，所以我们需要后序遍历。

同时我们做出假设，dfs(child,p,q)会返回p,q在child子树中的最低公共祖先。那么我们的代码大概会长这样：

1
2
3
4
5
6

TreeNod* dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
    //基本情况
    TreeNode* left = dfs(root->left, p, q);
    TreeNode* right = dfs(root->right, p, q);
    //更多处理：要充分理解题目的要求，明确每一个概念的定义，将其转换为代码。
}

如果在left中找到了p/q， 并且在right中也找到了p/q, 那么显然root就是最低公共祖先。

如果left中p/q, 而right没有找到，显然遍历left得到的返回值就是最低公公祖先。

另外需要注意，此处你有一个假设：p\q一定在tree中能够找到；如果该假设被打破的话，这段代码会出问题。

最终代码

1
2
3
4
5
6
7

TreeNod* dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == p || root == q || root == null) return root;
    TreeNode* left = dfs(root->left, p, q);
    TreeNode* right = dfs(root->right, p, q);
    if (left && right) return root;
    if (left) return left; else return right;
}

traceroute

ICMP ttl递减

差错控制
1、主机可达
发送一个type = 8,code = 0的ICMP Request包，表示这是一个请求包，如果顺利的到达对应的主机，主机会发送一个type = 0，code = 0的ICMP Reply包。

如果发送方收到Reply包，就说明主机可达。

2、主机不可达
发送一个type = 8,code = 0的ICMP Request包，如果路由器中不存在到达目的IP的路由的时候，会返回一个type = 3，code = 1的ICMP包，表示主机不可达。

当发送方收到包后，发现type = 3， code = 1，说明主机不可达。

3、超时
当一个ICMP包中TTL等于0的时候，路由器会将其抛弃，然后给发送端发送一个ICMP包，对应的type = 11，code = 0。

给目标主机的不可达端口（30000+）发送UDP数据包，并且设置TTL

他从源主机到目的主机发送一连串的IP数据报p1-pn，并且数据报是无法交付的udp数据报。第一个数据报的TTL设置为1，这样当这个数据报转发到第一个路由器的时候，路由器收到后TTL减1，减完1之后发现TTL变为0，路由器会向源主机发送一个超时差错报告报文。

然后是第二个，第二个数据报的TTL设置为2，这样转发到第二个路由器的时候，TTL变为0，并会向源主机在发送一个超时差错报告报文，依次进行此操作。直到第n个数据报pn到达目的主机，但是由于数据报无法交付，因此目的主机会向源主机发送终点不可达差错报告报文。
通过这种方式，源主机就可以通过发送过来的超时差错报告报文和终点不可达差错报告报文来的得到经过的路由器以及往返时间等信息，达到路由跟踪的目的。

traceroute命令利用了“TTL超时”的报文。当使用traceroute命令时，发送使用UDP故意发送一
份TTL为1的IP数据包给目标主机，
处理，处理这根数据包的第一个路由器将TTL值减1，然后丢弃该数据包，并向发送返回一份
超时lCMP报文。这样trace命令就
得到了该路径中第一个路由器的地址，然后traceroute命令发送一份TTL值为2的数据包，第一
个路由器将数据包转发给第二个路
由器。而在第二个路由器上，数据包的TTL值被减为0，因此这个路由器将丢弃这个数据包并
向发送方返回ICMP超时信息，这
样就可以得到第二个路由器的地址。traceroute命令继续上述过程直至数据包到达目标主机。
traceroute命令如何判断数据包是否已经到达目标主机呢？实际上执行traceroute命令的设备发
送原始数据包时，它会选择一个几乎
不可能的值作为目标UDP端口号（大于30000），目标主机的任何一个应用程序都不可能使用该
端口。那么当该数据包到达目标主机
时，目标主机的UDP将产生一份代码为“端口不可达”的1CMP报文。而之前路由器返回的是“超
时”ICMP报文，这要traceroute
命令只要区分所接收到的CMP报文是“超时”还是“端口不可达”，就可以判断数据包是否已经到
达目的地了。

相关技术要点：

1. 数据结构/算法优化
2. 架构分层

一篇比较好的文章：
https://blog.csdn.net/ArtAndLife/article/details/121001656

正常一个fd会有等待队列，表示有哪一些进程在等待fd可用；

当一个进程在等待一个fd时，内核会把进程结构体从运行队列摘除，放在fd的等待队列上【这样子内核就不会调度到该进程了】

当某个端口有数据可读时，内核会跟进端口查索引表，找到对应的fd

对于select，会频繁的将进程挂在所有FD的等待队列上，然后在select返回的时候，再重新将进程从等待队列中移除，放回到运行队列上。

当进程被唤醒的时候，用户程序也需要遍历fd array，去GET哪些FD可读。

性能极其差！

eventpoll作为一个中间结构，替代进程，挂在对应的等待队列

而调用epoll_wait的进程当被阻塞的时候是挂在在eventpoll的等待队列上。

select低效的另一个原因在于程序不知道哪些socket收到数据，只能一个一个的遍历。如果内核维护一个“就绪列表”，引用收到的数据的socket，就能避免遍历。

当一个FD就绪后，需要做的事

红黑树在epoll中就保存在linux内核中的一块cache，然后通过在这个cache来进行文件描述符的插入删除等操作，由于红黑树的插入删除速度比较良好，查找效率也比较优秀，所以epoll性能提升的很大一个原因就在于此。红黑树只是数据的一个载体：当我们需要频繁的对数据进行插入删除而且还需要保证查找效率的时候，就应该想到使用红黑树。

rdllist
答案：epoll 实例中包含就绪事件的 fd 组成的链表。

rbn
答案：epoll 实例所关心的fd。

使用场景：

epoll 在应对大量网络连接时，只有活跃连接很少的情况下才能表现的性能优异。换句话说，epoll 在处理大量非活跃的连接时性能才会表现的优异。如果15000个 socket 都是活跃的，epoll 和 select 其实差不了太多。

epoll 的 edge-trigger 和 level-trigger 模式处理逻辑差异极小，性能测试结果表明常规应用场景 中二者性能差异可以忽略。
? 使用 edge-trigger 的 user app 比使用 level-trigger 的逻辑复杂，出错概率更高。
? edge-trigger 和 level-trigger 的性能差异主要在于 epoll_wait 系统调用的处理速度，是否是 user app 的性能瓶颈需要视应用场景而定，不可一概而论。

但从 kernel 代码来看，edge-trigger/level-trigger 模式的处理逻辑几乎完全相同，差别仅在于 level-trigger 模式在 event 发生时不会将其从 ready list 中移除，略为增大了 event 处理过程中 kernel space 中记录数据的大小。
[最后看看epoll独有的两种模式LT和ET。无论是LT和ET模式，都适用于以上所说的流程。区别是，LT模式下，只要一个句柄上的事件一次没有处理完，会在以后调用epoll_wait时次次返回这个句柄，而ET模式仅在第一次返回。]

然而，edge-trigger 模式一定要配合 user app 中的 ready list 结构，以便收集已出现 event 的 fd，再通过 round-robin 方式挨个处理，以此避免通信数据量很大时出现忙于处理热点 fd 而导致非热点 fd 饿死的现象。统观 kernel 和 user space，由于 user app 中 ready list 的实现千奇百怪，不一定都经过仔细的推敲优化，因此 edge-trigger 的总内存开销往往还大于 level-trigger 的开销。

一般号称 edge-trigger 模式的优势在于能够减少 epoll 相关系统调用，这话不假，但 user app 里可不是只有 epoll 相关系统调用吧？为了绕过饿死问题，edge-trigger 模式的 user app 要自行进行 read/write 循环处理，这其中增加的系统调用和减少的 epoll 系统调用加起来，有谁能说一定就能明显地快起来呢？

当然操作系统开发人员也会意识到这些缺陷，并且在设计poll接口时解决了大部分问题，因此你会问，还有任何理由使用select吗？为什么不直接淘汰它了？其实还有两个理由使用它：

1.第一个原因是可移植性。select已经存在很长时间了，你可以确定每个支持网络和非阻塞套接字的平台都会支持select，而它可能还不支持poll。另一种选择是你仍然使用poll然后在那些没有poll的平台上使用select来模拟它。
2.第二个原因是select的超时时间理论上可以精确到微秒级别。而poll和epoll的精度只有毫秒级。这对于桌面或者服务器系统来说没有任何区别，因为它们不会运行在纳秒精度的时钟上，但是在某些与硬件交互的实时嵌入式平台，降低控制棒关闭核反应堆．可能是需要的。(这就可以作为一个更加精确的sleep()来用)

什么时候应该选择使用Poll：
跨平台
同一时刻你的应用程序监听的套接字少于1000（这种情况下使用epoll不会得到任何益处）。
您的应用程序需要一次监视超过1000个套接字，但连接非常短暂（这是一个接近的情况，但很可能在这种情况下，您不太可能看到使用epoll的任何好处，因为epoll 的加速将这些新描述符添加到集合中会浪费等待 - 见下文
您的应用程序的设计方式不是在另一个线程正在等待它们更改事件（即您没有使用kqueue或IO完成端口移植应用程序）。

EPoll的缺点：
1.改变监听事件的类型（例如从读事件改为写事件）需要调用epoll_ctl系统调用，而这在poll中只需要在用户空间简单的设置一下对应的掩码。如果需要改变5000个套接字的监听事件类型就需要5000次系统调用和上下文切换（直到2014年epoll_ctl函数仍然不能批量操作，每个描述符只能单独操作），这在poll中只需要循环一次pollfd结构体。
2.每一个被accept()的套接字都需要添加到集合中，在epoll中必须使用epoll_ctl来添加–这就意味着每一个新的连接都需要两次系统调用，而在poll中只需要一次。如果你的服务有非常多的短连接它们都接受或者发送少量数据，epoll所花费的时间可能比poll更长。(解释了上文)
3.epoll是Linux上独有的，虽然其他平台上也有类似的机制但是他们的区别非常大，例如边沿触发这种模式是非常独特的（FreeBSD的kqueue对它的支持非常粗糙）。
什么情况下使用Epoll：
1.你的程序通过多个线程来处理大量的网络连接。如果你的程序只是单线程的那么将会失去epoll的很多优点。并且很有可能不会比poll更好。
2.你需要监听的套接字数量非常大（至少1000）；如果监听的套接字数量很少则使用epoll不会有任何性能上的优势甚至可能还不如poll。
3.你的网络连接相对来说都是长连接；就像上面提到的epoll处理短连接的性能还不如poll因为epoll需要额外的系统调用来添加描述符到集合中。
4.你的应用程序依赖于Linux上的其他特性

相关技术要点：

1. 时空错配-Copy On Write

（1） 了解虚拟内存
物理内存是系统硬件提供的内存大小，是真正的内存，相对于物理内存，在Linux下还有一个虚拟内存的概念。虚拟内存的存在就是为了满足物理内存的不足而提出的策略，它利用磁盘空间虚拟出的一块逻辑内存。用作虚拟内存的磁盘空间被称为交换空间。

进程中看到的地址都是逻辑地址;

虚拟内存提供的三个重要的能力：

1） 它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，根据需要在磁盘和主存之间来回传送数据，使得能够运行比内存大的多的进程。

2） 它为每个进程提供了一致的地址空间，从而简化了存储器管理;

3） 它保护每个进程的地址空间不被其他进程破坏 ;

（2）写时拷贝技术
传统的fork系统调用直接把所有的资源复制给新创建的进程。这种实现过于简单并且效率低下，因为它拷贝的数据也许并不共享，更糟糕的情况是，如果新进程打算立即执行一个新的映像，那么所有的拷贝都将前功尽弃。

Linux的fork（）使用写时拷贝页实现。写时拷贝是一种可以推迟甚至免除拷贝数据的技术。内核此时并不复制整个进程地址空间，而是让父进程和子进程共享同一个拷贝。

只有在需要写入的时候，数据才会被复制，从而使各个进程拥有各自的拷贝。也就是说，资源的复制只有在需要写入的时候才进行，在此之前，知识以只读方式共享。这种技术使地址空间上的页的拷贝被推迟到实际发生写入的时候才进行。在页根本不会被写入的情况下（举例：fork（）后立即调用exec（））他们就无需复制了。

fork（）的实际开销就是复制父进程的页表以及给子进程创建唯一的进程描述符。在一般情况下，进程创建后都会马上运行一个可执行的文件，这种优化可以避免拷贝大量根本就不会被使用的数据（地址空间里常常包含数十兆数据）。由于Unix强调进程快速执行的能力，所以这个优化是很重要的。

不采用写时拷贝技术,第一,复制开销比较大;第二,占用内存空间;

所以我们对fork复制进程的过程做了一个优化:———-写时拷贝技术。

引入了写时拷贝技术,就可以延迟页面的拷贝,甚至免除页面的拷贝

还有一个需要注意的地方:写时拷贝是以页为单位的,哪怕这个页中只有一个字节被修 改了,我们也需要将整个页面都复制出来一份

pid1 = fork()
pid2 = fork()

printf(“pid1:%d, pid2:%d”, pid2, pid2);

一共创建了四个进程

参考：
https://blog.csdn.net/weixin_59179454/article/details/127092115

信号是一种异步通信机制，它是在软件层面上对中断机制的一种模拟，

阻塞信号
信号有几种状态，首先是信号的产生 (Genertion)，而实际执行信号处理动作时，状态为递达 (Delivery)，信号在产生到递达中的状态被称为未决 (Pending)

进程可以选择阻塞 (Blocking)某些信号，被阻塞的信号在产生后将保持在未决状态，直到进程解除对该信号的阻塞，才执行递达的动作

1.4 信号的处理时机

信号是在什么时候被处理的呢？是在被投递的时候处理的吗，不是的。信号是在线程将要返回用户空间之前进行处理的。线程返回用户空间有两种情况，一是从系统调用返回，二是从中断返回。返回之前，线程会检查队列里有没有信号要处理，有的话就处理。

1.5 信号与多线程

信号的发送既可以发送给进程，也可以发送给线程，但是同步信号(也就是和当前线程执行相关而产生的信号)应当发送给当前线程。进程发送信号可以选择不同的接口函数，有的接口是发给进程的，有的接口是发给线程的。线程信号队列中的信号只能由线程自己处理，进程信号队列中的信号由进程中的线程处理，具体是由哪个线程处理是不确定的。

信号掩码(mask)的设置是线程私有的，每个线程都可以设置不同的信号掩码。

信号处理方式的设置是进程全局的，后面线程设置的方式会覆盖前面线程的设置。

信号处理的效果是进程全局的。

消息事务是指一系列的生产、消费操作可以要么都完成，要么都失败，类似数据库的事务。这个特性在0.10.2的版本是不支持的，从0.11版本开始才支持。华为云DMS率先提供Kafka 1.1.0的专享版服务，支持消息事务特性。

Basic-Paxos解决的问题：在一个分布式系统中，如何就一个提案达成一致。

https://blog.csdn.net/yangmengjiao_/article/details/120191314

raft将共识问题分解成两个相对独立的问题，leader election，log replication。

virtual destructor()

将Base析构函数声明为virtual函数时，执行delete base ;语句就会删除subModel的对象；

exception

try catch

void operator new (size_t size,void pbuffer)

可以做某一个类的静态成员函数

参考：
https://www.toutiao.com/article/6956573052414984712/?wid=1670850368129

bootstrap classloader
extension classloader
application classloader
custom classloader

双亲委派模型

当一个类收到了类加载请求，他首先不会尝试自己去加载这个类，而是把这个请求委派给父类去完成，每一个层次类加载器都是如此，因此所有的加载请求都应该传送到启动类加载其中，只有当父类加载器反馈自己无法完成这个请求的时候（在它的加载路径下没有找到所需加载的Class），子类加载器才会尝试自己去加载

参考：
https://blog.csdn.net/w1lgy/article/details/126434976