2021年面试常问的死锁、三次握手、四次挥手
3.6 操作系统3.6.1 死锁1 产生死锁的原因（1） 竞争资源（2） 进程推进顺序不当2 产生死锁的必要条件互斥条件：进程对所分配到的资源进行排他性使用，即在一段时间内某资源只能被一个进程占用。请求保持条件：进程已经获得了至少一个资源，但是又提出了新的请求，而请求的资源已被其他进程占有，此时请求进程被阻塞，但是它对自己已获得的资源又不释放。不可抢占条件：进程已获得的资源在未使用完之前不可被抢占，只能在进程使用完之后自己释放。循环等待条件：存在进程-资源循环链。3 处理死锁的方法预防死锁：是一种简单且直观的事先预防方法。该方法是通过某些限制条件，破坏产生死锁的必要条件，从而避免产生死锁。避免死锁：在动态分配资源的过程中，用某种方法防止系统进入不安全的状态，从而避免产生死锁。如银行家算法。检测死锁：允许进程在运行过程中产生死锁，但可通过系统的检测机构及时的检测出死锁，并精确定位和死锁有关的进程和资源，然后采取措施，清除死锁。解除死锁：和检测死锁搭配使用，检测到产生死锁时，采取措施，清除死锁，一般是撤销挂起一些进程，以便回收一些资源，再将这些资源分配给阻塞的进程，使其继续执行。4 银行家算法思想：某一时刻一个进程请求一个资源时，判断如果满足该进程，则是否能找出一个安全序列，如果能则满足该进程的请求。数据结构：Max：最大需求矩阵Allocation：分配矩阵Need：需求矩阵Available：可利用资源向量Needi,j=maxi,j-allocationi,j算法：Requesti,j=k ：i进程请求k个j资源。第一步：判断Requesti,j<= Needi,j，是则进行第二步，否则报错第二步：判断Requesti,j<= Available i,j，是则进行第三步，否则i进程阻塞。第三步：系统试着将该资源分配给进程，并修改数据结构：Needi,j=needi,j-requesti,jAllocationi,j=allocationi,j+requesti,jAvailablei,j= Availablei,j- requesti,j第四步：系统执行安全性算法，检查此次分配之后系统是否处于安全状态，若安全则分配，不安全则恢复原来的资源分配状态，让进程等待。5 死锁的检测和解除死锁的检测：资源分配图，方框表示一类资源，圆圈代表进程，方框中的空心圆代表一个资源，当资源分配图是不可完全简化的时候，存在死锁。完全简化的：通过一系列简化后，能消去资源分配图中所有的边，使所有进程节点都成为孤立节点。死锁的解除：1）抢占资源，从一个或多个进程中抢占足够的资源，分配给死锁进程，以解除死锁；2）终止或撤销进程，终止或撤销系统中的一个或多个处于死锁状态的进程，直至打破循环。使系统从死锁状态解脱。3.7 计算网络3.7.1三次握手1 三次握手的原理最初客户端和服务端都处于 CLOSED(关闭) 状态。本例中 A（Client） 主动打开连接，B（Server） 被动打开连接。一开始，B 的 TCP 服务器进程首先创建传输控制块TCB，准备接受客户端进程的连接请求。然后服务端进程就处于 LISTEN(监听) 状态，等待客户端的连接请求。如有，立即作出响应。第一次握手：A 的 TCP 客户端进程也是首先创建传输控制块 TCB。然后，在打算建立 TCP 连接时，向 B 发出连接请求报文段，这时首部中的同步位 SYN=1，同时选择一个初始序号 seq = x。TCP 规定，SYN 报文段（即 SYN = 1 的报文段）不能携带数据，但要消耗掉一个序号。这时，TCP 客户进程进入 SYN-SENT（同步已发送）状态。第二次握手：B 收到连接请求报文后，如果同意建立连接，则向 A 发送确认。在确认报文段中应把 SYN 位和 ACK 位都置 1，确认号是 ack = x + 1，同时也为自己选择一个初始序号 seq = y。请注意，这个报文段也不能携带数据，但同样要消耗掉一个序号。这时 TCP 服务端进程进入 SYN-RCVD（同步收到）状态。第三次握手：TCP 客户进程收到 B 的确认后，还要向 B 给出确认。确认报文段的 ACK 置 1，确认号 ack = y + 1，而自己的序号 seq = x + 1。这时 ACK 报文段可以携带数据。但如果不携带数据则不消耗序号，这种情况下，下一个数据报文段的序号仍是 seq = x + 1。这时，TCP 连接已经建立，A 进入 ESTABLISHED（已建立连接）状态。2 为什么要进行三次握手？四次和两次为什么不行?两次不可行的原因：为了防止已经失效的连接请求报文段突然又传送到了 B，因而产生错误。比如下面这种情况：A 发出的第一个连接请求报文段并没有丢失，而是在网路结点长时间滞留了，以致于延误到连接释放以后的某个时间段才到达 B。本来这是一个早已失效的报文段。但是 B 收到此失效的链接请求报文段后，就误认为 A 又发出一次新的连接请求。于是就向 A 发出确认报文段，同意建立连接。对于上面这种情况，如果不进行第三次握手，B 发出确认后就认为新的运输连接已经建立了，并一直等待 A 发来数据。B 的许多资源就这样白白浪费了。四次不可行的原因：我们需要明白一点，完全可靠的通信协议是不存在的。在经过三次握手之后，客户端和服务端已经可以确认之前的通信状况，都收到了确认信息。所以即便再增加握手次数也不能保证后面的通信完全可靠，所以是没有必要的。3.7.2 四次挥手1 四次挥手的原理第一次挥手：A 的应用进程先向其 TCP 发出连接释放报文段，并停止再发送数据，主动关闭 TCP 连接。A 把连接释放报文段首部的终止控制位 FIN 置 1，其序号 seq = u（等于前面已传送过的数据的最后一个字节的序号加 1），这时 A 进入 FIN-WAIT-1（终止等待1）状态，等待 B 的确认。请注意：TCP 规定，FIN 报文段即使不携带数据，也将消耗掉一个序号。第二次挥手：B 收到连接释放报文段后立即发出确认，确认号是 ack = u + 1，而这个报文段自己的序号是 v（等于 B 前面已经传送过的数据的最后一个字节的序号加1），然后 B 就进入 CLOSE-WAIT（关闭等待）状态。TCP 服务端进程这时应通知高层应用进程，因而从 A 到 B 这个方向的连接就释放了，这时的 TCP 连接处于半关闭（half-close）状态，即 A 已经没有数据要发送了，但 B 若发送数据，A 仍要接收。也就是说，从 B 到 A 这个方向的连接并未关闭，这个状态可能会持续一段时间。A 收到来自 B 的确认后，就进入 FIN-WAIT-2(终止等待2)状态，等待 B 发出的连接释放报文段。第三次挥手：若 B 已经没有要向 A 发送的数据，其应用进程就通知 TCP 释放连接。这时 B 发出的连接释放报文段必须使 FIN = 1。假定 B 的序号为 w（在半关闭状态，B 可能又发送了一些数据）。B 还必须重复上次已发送过的确认号 ack = u + 1。这时 B 就进入 LAST-ACK(最后确认)状态，等待 A 的确认。第四次挥手：A 在收到 B 的连接释放报文后，必须对此发出确认。在确认报文段中把 ACK 置 1，确认号 ack = w + 1，而自己的序号 seq = u + 1（前面发送的 FIN 报文段要消耗一个序号）。然后进入 TIME-WAIT(时间等待) 状态。请注意，现在 TCP 连接还没有释放掉。必须经过时间等待计时器设置的时间 2MSL（MSL：最长报文段寿命）后，A 才能进入到 CLOSED 状态，然后撤销传输控制块，结束这次 TCP 连接。当然如果 B 一收到 A 的确认就进入 CLOSED 状态，然后撤销传输控制块。所以在释放连接时，B 结束 TCP 连接的时间要早于 A。2 为什么TIME-WAIT必须等待2MSL？为了保证 A 发送的最后一个 ACK 报文段能够到达 B。这个 ACK 报文段有可能丢失，因而使处在 LAST-ACK 状态的 B 收不到对已发送的 FIN + ACK 报文段的确认。B 会超时重传这个 FIN+ACK 报文段，而 A 就能在 2MSL 时间内（超时 + 1MSL 传输）收到这个重传的 FIN+ACK 报文段。接着 A 重传一次确认，重新启动 2MSL 计时器。最后，A 和 B 都正常进入到 CLOSED 状态。如果 A 在 TIME-WAIT 状态不等待一段时间，而是在发送完 ACK 报文段后立即释放连接，那么就无法收到 B 重传的 FIN + ACK 报文段，因而也不会再发送一次确认报文段，这样，B 就无法按照正常步骤进入 CLOSED 状态。防止已失效的连接请求报文段出现在本连接中。A 在发送完最后一个 ACK 报文段后，再经过时间 2MSL，就可以使本连接持续的时间内所产生的所有报文段都从网络中消失。这样就可以使下一个连接中不会出现这种旧的连接请求报文段。
