大家好,最近有位读者去虾皮面试啦,分享一下面试的真题~
给你链表的头结点head ,请将其按升序排列并返回排序后的链表 。
实例1:
输入:head = [4,2,1,3]
输出:[1,2,3,4]
实例2:
输入: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实现的零拷贝流程如下:
雪花算法