杭州网站建设很棒,企业网站建设流程图,如何选择网站营销公司,建站到网站收录到优化简单题#xff08;本题共30分#xff09;
请简述Tcp-ip的3次握手以及4次挥手过程#xff1f;并解释为何关闭连接需要4次挥手(10分)
详细答案参见TCP/IP协议三次握手与四次握手流程解析
TCP三次握手、四次挥手过程如下: 通常情况下#xff0c;一个正常的TCP连接#xf…简单题本题共30分
请简述Tcp-ip的3次握手以及4次挥手过程并解释为何关闭连接需要4次挥手(10分)
详细答案参见TCP/IP协议三次握手与四次握手流程解析
TCP三次握手、四次挥手过程如下: 通常情况下一个正常的TCP连接都会有三个阶段:1、TCP三次握手; 2、数据传送; 3、TCP四次挥手 SYN: (同步序列编号,Synchronize Sequence Numbers)该标志仅在三次握手建立TCP连接时有效。表示一个新的TCP连接请求。ACK: (确认编号,Acknowledgement Number)是对TCP请求的确认标志,同时提示对端系统已经成功接收所有数据。FIN: (结束标志,FINish)用来结束一个TCP回话.但对应端口仍处于开放状态,准备接收后续数据。四次挥手的原因 这是因为服务端的LISTEN状态下的SOCKET当收到SYN报文的建连请求后它可以把ACK和SYNACK起应答作用而SYN起同步作用放在一个报文里来发送。但关闭连接时当收到对方的FIN报文通知时它仅仅表示对方没有数据发送给你了但未必你所有的数据都全部发送给对方了所以你可以未必会马上会关闭SOCKET,也即你可能还需要发送一些数据给对方之后再发送FIN报文给对方来表示你同意现在可以关闭连接了所以它这里的ACK报文和FIN报文多数情况下都是分开发送的。不能两次握手连接的原因 3次握手完成两个重要的功能既要双方做好发送数据的准备工作(双方都知道彼此已准备好)也要允许双方就初始序列号进行协商这个序列号在握手过程中被发送和确认。 现在把三次握手改成仅需要两次握手死锁是可能发生的。作为例子考虑计算机S和C之间的通信假定C给S发送一个连接请求分组S收到了这个分组并发送了确认应答分组。按照两次握手的协定S认为连接已经成功地建立了可以开始发送数据分组。可是C在S的应答分组在传输中被丢失的情况下将不知道S是否已准备好不知道S建立什么样的序列号C甚至怀疑S是否收到自己的连接请求分组。在这种情况下C认为连接还未建立成功将忽略S发来的任何数据分组只等待连接确认应答分组。而S在发出的分组超时后重复发送同样的分组。这样就形成了死锁。SYN攻击 在三次握手过程中服务器发送SYN-ACK之后收到客户端的ACK之前的TCP连接称为半连接(half-open connect).此时服务器处于Syn_RECV状态.当收到ACK后服务器转入ESTABLISHED状态. Syn攻击就是 攻击客户端 在短时间内伪造大量不存在的IP地址向服务器不断地发送syn包服务器回复确认包并等待客户的确认由于源地址是不存在的服务器需要不断的重发直 至超时这些伪造的SYN包将长时间占用未连接队列正常的SYN请求被丢弃目标系统运行缓慢严重者引起网络堵塞甚至系统瘫痪。 Syn攻击是一个典型的DDOS攻击。检测SYN攻击非常的方便当你在服务器上看到大量的半连接状态时特别是源IP地址是随机的基本上可以断定这是一次SYN攻击.在Linux下可以如下命令检测是否被Syn攻击 netstat -n -p TCP | grep SYN_RECV 一般较新的TCP/IP协议栈都对这一过程进行修正来防范Syn攻击修改tcp协议实现。主要方法有SynAttackProtect保护机制、SYN cookies技术、增加最大半连接和缩短超时时间等.但是不能完全防范syn攻击。2MSL TIME_WAIT状态 TIME_WAIT状态的存在有两个理由1让4次握手关闭流程更加可靠4次握手的最后一个ACK是是由主动关闭方发送出去的若这个ACK丢失被动关闭方会再次发一个FIN过来。若主动关闭方能够保持一个2MSL的TIME_WAIT状态则有更大的机会让丢失的ACK被再次发送出去。2防止lost duplicate对后续新建正常链接的传输造成破坏。lost duplicate在实际的网络中非常常见经常是由于路由器产生故障路径无法收敛导致一个packet在路由器ABC之间做类似死循环的跳转。IP头部有个TTL限制了一个包在网络中的最大跳数因此这个包有两种命运要么最后TTL变为0在网络中消失要么TTL在变为0之前路由器路径收敛它凭借剩余的TTL跳数终于到达目的地。但非常可惜的是TCP通过超时重传机制在早些时候发送了一个跟它一模一样的包并先于它达到了目的地因此它的命运也就注定被TCP协议栈抛弃。另外一个概念叫做incarnation connection指跟上次的socket pair一摸一样的新连接叫做incarnation of previous connection。lost duplicate加上incarnation connection则会对我们的传输造成致命的错误。大家都知道TCP是流式的所有包到达的顺序是不一致的依靠序列号由TCP协议栈做顺序的拼接假设一个incarnation connection这时收到的seq1000, 来了一个lost duplicate为seq1000, len1000, 则tcp认为这个lost duplicate合法并存放入了receive buffer导致传输出现错误。通过一个2MSL TIME_WAIT状态确保所有的lost duplicate都会消失掉避免对新连接造成错误。 该状态为什么设计在主动关闭这一方 1发最后ack的是主动关闭一方 2只要有一方保持TIME_WAIT状态就能起到避免incarnation connection在2MSL内的重新建立不需要两方都有 如何正确对待2MSL TIME_WAIT RFC要求socket pair在处于TIME_WAIT时不能再起一个incarnation connection。但绝大部分TCP实现强加了更为严格的限制。在2MSL等待期间socket中使用的本地端口在默认情况下不能再被使用。若A 10.234.5.5:1234和B 10.55.55.60:6666建立了连接A主动关闭那么在A端只要port为1234无论对方的port和ip是什么都不允许再起服务。显而易见这是比RFC更为严格的限制RFC仅仅是要求socket pair不一致而实现当中只要这个port处于TIME_WAIT就不允许起连接。这个限制对主动打开方来说是无所谓的因为一般用的是临时端口但对于被动打开方一般是server就悲剧了因为server一般是熟知端口。比如http一般端口是80不可能允许这个服务在2MSL内不能起来。解决方案是给服务器的socket设置SO_REUSEADDR选项这样的话就算熟知端口处于TIME_WAIT状态在这个端口上依旧可以将服务启动。当然虽然有了SO_REUSEADDR选项但sockt pair这个限制依旧存在。比如上面的例子A通过SO_REUSEADDR选项依旧在1234端口上起了监听但这时我们若是从B通过6666端口去连它TCP协议会告诉我们连接失败原因为Address already in use.
操作系统的内存管理淘汰算法有哪些,请列出并简要说明(10分)
进程运行时若其访问的页面不在内存而需将其调入但内存已无空闲空间时就需要从内存中调出一页程序或数据送入磁盘的兑换区。选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率。
最佳OPT置换算法是理论算法它将不再使用的页面换出而实际中不能预知哪个页面不再使用但是这个算法是最优算法可以作为评测其他算法的性能。先进先出(FIFO)置换算法优先淘汰最先进入内存中的页面。该算法实现简单但算法跟内存的实际运行规律不符不管该页面是否经常使用这样就有可能导致缺页率增加导致页面置换次数增加。最近最少(LRUleast recently used)使用置换算法当需要淘汰某页选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。在这里采用一个页面集大小的栈存储最近访问的页面。页面按时间顺序压如栈中。如果被访问的页在栈中则从栈中移出页面压入栈顶。这样栈底记录离当前时间最近的一段时间内最久没有使用过的页。最不经常使用(LFU:least frequently used)置换算法 LFU在需要淘汰某一页时首先淘汰到当前时间为止、被访问次数最少的那一页。这只要在页面集中给每一页增设一个访问计数器即可实现。每当该页被访问时访问计数器加1而发生一次缺页中断时则淘汰计数值最小的那一页并将所有的计数器清零。最近最不经常使用(NRU:not recently used)算法 NRU在需要淘汰某一页时从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访问时访问位置1。否则访问位置0。系统周期性地对所有引用位清零。当需淘汰一页时从那些访问位为零的页中选一页进行淘汰。如果引用位全0或全1NRU算法退化为FIFO算法。
详解可参照:操作系统内存管理淘汰算法的实现 和 内存管理的页面置换算法有哪些
进行数据库设计时通常需要遵守哪些范式,请列举并说明?(10分)
设计关系数据库时遵从不同的规范要求设计出合理的关系型数据库这些不同的规范要求被称为不同的范式各种范式呈递次规范越高的范式数据库冗余越小。
目前关系数据库有六种范式第一范式1NF、第二范式2NF、第三范式3NF、巴斯-科德范式BCNF、第四范式(4NF和第五范式5NF还又称完美范式。
第一范式 所有的域都应该是原子性的即数据库表的每一列都是不可分割的原子数据项而不能是集合数组记录等非原子数据项。即实体中的某个属性有多个值时必须拆分为不同的属性。在符合第一范式1NF表中的每个域值只能是实体的一个属性或一个属性的一部分。简而言之第一范式就是无重复的域。第二范式要求实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性如果存在那么这个属性和主关键字的这一部分应该分离出来形成一个新的实体新实体与原实体之间是一对多的关系。为实现区分通常需要为表加上一个列以存储各个实例的唯一标识。简而言之第二范式就是在第一范式的基础上属性完全依赖于主键。第三范式 在1NF基础上任何非主属性不依赖于其它非主属性[在2NF基础上消除传递依赖]
详细讲解参见数据库范式
算法与程序设计题(本题共45分)
寻找一个简单链表的中项,如果存在两个则返回前一个.请给出算法描述并给出代码(15分)
分析:可以借助于两个指针快慢指针快指针一次走两步慢指针一次走一步当快指针走到尾端时慢指针即指向中项位置。空间复杂度为01时间复杂度为O(n).
struct ListNode
{struct ListNode *next;int key;
};ListNode* getMID(ListNode* head)
{if (NULL head)return NULL;ListNode *first head;ListNode *second head;while(NULL ! second-next){if(NULL second-next-next)break;first first-next;second second-next-next;}return first;
}
拓展借助快慢指针可以判断单向链表中是否有环依据就是如果有环快指针与慢指针总会相遇
在由N个正数的集合S中:找出最大元素C,满足CAB,其中A,B都是集合S中元素.请给出算法描述、代码与时间复杂度分析(15分)
算法步骤:
首先对集合进行排序,从小到大排序,可以选择排序算法较快的快速|归并|堆排序,n∗log(n)n*log(n)复杂度找最大满足条件的元素C。两层循环外层循环从大到小依次寻找C。内层循环分别从头尾向中间寻找元素A B,是的 C A B找到后即跳出两层循环。时间复杂度O(n2)O(n^2)。
程序复杂度为O(n2)O(n^2)
int FindSum(int A[],int n){sort(A,An);int left,right,sum;for(int i n - 1;i 2;--i){left 0,right i - 1;while(left right){sum A[left] A[right];if(sum A[i]){return A[i];}else if(sum A[i]){--right;}else{left;}}}return -1;
}
使用堆栈(Stack)来模拟队列(FIFO)功能,要求数据必须存储在堆栈内部.需要实现enqueue(入栈),dequeue(出栈),isEmpty(判空)三个功能,并给出单元测试.(15分)
思路两个堆栈实现队列 s1为入栈的s2为出栈的 1. 入队列直接压入s1即可 2. 出队列如果s2不为空把s2中的栈顶元素直接弹出否则把s1的所有元素全部弹出压入s2中再弹出s2的栈顶元素.
stackint A;
stackint B;
//入队
void enqueue(int value[],int len)
{for (int i 0; i len; i){A.push(value[i]);}if (B.empty()){while(!A.empty()){B.push(A.top());A.pop();}}
}
出队
void dequeue()
{while(!B.empty()){B.pop();//其他操作} while(!A.empty()){B.push(A.top());A.pop();}while(!B.empty()){B.pop();//其他操作}
}
//判断是否为空
bool isEmpty()
{return (A.empty() B.empty());
}
拓展通过队列实现栈
两个队列A与B两个队列指针指针qQueue指向一个非空队列(当然如果A、B都是空的话指向其一指针tmp始终指向另外一个空队列 1. 入栈: 直接进入qQueue指向的队列 2. 出栈: qQueue指向的队列是否为空非空时将其指向的队列数据移动pop到tmp指向的队列获取最后一个数据即可交换qQueue与tmp。
详细讲解参见两个栈实现队列 两个队列实现栈
系统设计题(本题共25分)
手机推送服务设计,在各个手机端应用都有一定的云控制能力,可以再某些情况下云端发送各种数据或者命令道手机端,例如发送一个强制升级的命令或者手机app配置变换的数据包,以及发送一个信息给特定人群(某个地区) 请设计一个以长链接为主的云端控制服务,为了聚焦主要问题,可以忽略掉低速手机网络(例如:2g网络)手机终端等因素\用户登录的需求.服务需要承担定向、定量的推送需求,在设计中要尽量高的吞吐能力和容错能力。 需要完成 a)基本的模块视图 b)链接管理主要设计思路。单台机器承担更多链接但是链接多了后管理链接(链接中断、链接查找)都会出现性能瓶颈请尝试给出思路。 c)尝试给出提高容错能力(避免因为某台物理机器或者某个机器上的程序挂掉导致整个系统不可用)的思路
后续分析…
参考
http://www.cnblogs.com/newpanderking/p/3972280.html深入浅出TCP协议的2MSL TIME_WAIT状态Linux中TCP连接过程简介
