面试必备：虾皮服务端15连问

大家好，最近有位读者去虾皮面试啦，分享一下面试的真题~

给你链表的头结点head ，请将其按升序排列并返回排序后的链表。

实例1：

代码语言：javascript复制

输入：head = [4,2,1,3]
输出：[1,2,3,4]

实例2：

代码语言：javascript复制

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

这道题可以用双指针归并排序算法解决，主要以下四个步骤

1. 快慢指针法，遍历链表找到中间节点

2. 中间节点切断链表

3. 分别用归并排序排左右子链表

4. 合并子链表

完整代码如下：

如果内核数据还没准备好，可以先返回错误信息给用户进程，让它不需要等待，而是通过轮询的方式再来请求。这就是非阻塞IO，流程图如下：

IO多路复用之select

应用进程通过调用select函数，可以同时监控多个fd，在select函数监控的fd中，只要有任何一个数据状态准备就绪了，select函数就会返回可读状态，这时应用进程再发起recvfrom请求去读取数据。

AIO实现了IO全流程的非阻塞，就是应用进程发出系统调用后，是立即返回的，但是立即返回的不是处理结果，而是表示提交成功类似的意思。等内核数据准备好，将数据拷贝到用户进程缓冲区，发送信号通知用户进程IO操作执行完毕。

流程如下：

分布式锁，是控制分布式系统不同进程共同访问共享资源的一种锁的实现。秒杀下单、抢红包等等业务场景，都需要用到分布式锁，我们项目中经常使用Redis作为分布式锁。

选了Redis分布式锁的几种实现方法，大家来讨论下，看有没有啥问题哈。

务还没执行完的问题（实际上，估算个业务处理的时间，一般没啥问题了）。

分布式锁可能存在锁过期释放，业务没执行完的问题。有些小伙伴认为，稍微把锁过期时间设置长一些就可以啦。其实我们设想一下，是否可以给获得锁的线程，开启一个定时守护线程，每隔一段时间检查锁是否还存在，存在则对锁的过期时间延长，防止锁过期提前释放。

当前开源框架Redisson就解决了这个分布式锁问题。我们一起来看下Redisson底层原理是怎样的吧：

可以发现，sendfile实现的零拷贝，I/O发生了2次用户空间与内核空间的上下文切换，以及3次数据拷贝。其中3次数据拷贝中，包括了2次DMA拷贝和1次CPU拷贝。那能不能把CPU拷贝的次数减少到0次呢？有的，即带有DMA收集拷贝功能的sendfile！

linux 2.4版本之后，对sendfile做了优化升级，引入SG-DMA技术，其实就是对DMA拷贝加入了scatter/gather操作，它可以直接从内核空间缓冲区中将数据读取到网卡。使用这个特点搞零拷贝，即还可以多省去一次CPU拷贝。

sendfile DMA scatter/gather实现的零拷贝流程如下：

想要获取monitor的线程,首先会进入_EntryList队列。
当某个线程获取到对象的monitor后,进入Owner区域，设置为当前线程,同时计数器count加1。
如果线程调用了wait()方法，则会进入WaitSet队列。它会释放monitor锁，即将owner赋值为null,count自减1,进入WaitSet队列阻塞等待。
如果其他线程调用 notify() / notifyAll() ，会唤醒WaitSet中的某个线程，该线程再次尝试获取monitor锁，成功即进入Owner区域。
同步方法执行完毕了，线程退出临界区，会将monitor的owner设为null，并释放监视锁。

雪花算法

0 人点赞