自我介绍
毕业院校、项目经历、实习工作经历,简单介绍掌握的技能。
算法题
将多个有序链表合并为一个有序链表;
询问了经典的排序算法;
改进:要求运行时间复杂度 $O(n\cdot log n)$,使用堆排序;
问答环节
什么是死锁?如何避免死锁?
死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进。
死锁的形成主要有两个原因:
- 系统资源不足;
- 进程推进顺序不当。
死锁产生的四个必要条件:
- 互斥条件:一个资源每次只能被一个进程使用,即在某一个时间段内仅为一个进程所占用。此时有其他进程请求该资源,则请求进程只能等待。
- 请求保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源 已被其他进程占有,此时请求进程被阻塞,但对自己已获得的资源保持不放。
- 资源不可剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能 由获得该资源的进程自己来释放(只能是主动释放)。
- 循环等待:若干进程间形成首尾相接循环等待资源的关系。
死锁避免的基本思想:只要发生死锁,以上条件必然成立,若有一个条件不成立,则不会发生死锁。系统对进程发出每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,如果分配后系统可能发生死锁,则不予分配,否则予以分配。这是一种保证系统不进入死锁状态的动态策略。
死锁预防:破坏死锁产生的四个必要条件之一,严格地防止死锁的出现。
死锁避免与死锁预防的区别:死锁预防严格限制产生死锁的必要条件,而死锁避免不那么严格,因为即使死锁的必要条件存在,也不一定发生死锁。
TCP和UDP的区别
TCP与UDP的基本区别,:
- 基于有连接和无连接;
- 系统占用资源多少;
- UDP程序结构较为简单;
- 字节流模式(TCP)与数据报模式(UDP);
- TCP保证数据正确性,UDP可能丢包;
- TCP保证数据顺序,UDP不保证。
UDP应用场景:实时场景,RIP路由表更新,DNS、SNMP等都是运行在UDP之上。
- 面向数据报方式;
- 网络数据大多为短消息;
- 拥有大量client;
- 对数据安全性没有特殊要求;
- 网络负担重,但是对响应速度要求高。
总体来说,TCP与UDP的区别如下:
- TCP面向连接(如打电话要先拨号建立连接);UDP是无连接的,即发送数据之前不需要建立连接。
- TCP提供可靠的服务。也就是说,通过TCP连接传送的数据,无差错,不丢失,不重复,且按序到达;UDP尽最大努力交付,即不保证可靠交付。
- TCP面向字节流,实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的。UDP没有拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如IP电话,实时视频会议等)。
- 每一条TCP连接只能是点到点的;UDP支持一对一,一对多,多对一和多对多的交互通信。
- TCP首部开销20字节;UDP的首部开销小,只有8个字节。
- TCP的逻辑通信信道是全双工的可靠信道,UDP则是不可靠信道。
ps: UDP一般不说全双工、半双工,因为这些说法都是指面向连接才有的说法,而对于UDP这种不建立连接的传输协议,没有明确的全双工、半双工的说法。
TCP拥塞控制
TCP的四种拥塞控制算法:
-
慢启动
发送端在最初建立连接后,拥塞窗口值为1,接收方收到该报文后,将拥塞窗口的值变为2,每个传输轮次依次增加(指数方式增加),直至发生拥塞。
-
拥塞避免
每个传输轮次线性增加拥塞窗口值。
-
快重传
接收方收到未按需到达的报文段后,要求发送方重传之前的报文段,而不是等超时重传计数器超时再重传。
-
快恢复
发送方知道丢失了个别字段的报文段后,不启慢启动算法,执行快恢复算法,将拥塞窗口值修改为当前窗口的一般,开始执行拥塞避免算法。