排序类问题：

• 海量数据排序：
  • 外部排序：归并 + 败者树
  • 基数排序：https://time.geekbang.org/column/article/42038
• 海量数据查询：
  • 布隆过滤器判断是否存在
  • 构建索引：B+ 树、跳表

• TCP和UDP的区别？

  • 用户数据报协议 UDP（User Datagram Protocol）是无连接的，尽最大可能交付，没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部），支持一对一、一对多、多对一和多对多的交互通信

    传输控制协议 TCP（Transmission Control Protocol）是面向连接的，提供可靠交付，有流量控制，拥塞控制，提供全双工通信，面向字节流（把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块），每一条 TCP 连接只能是点对点的（一对一）

  高手解答：

  • 从tcp udp报文格式就看出差别：tcp头部比udp头部字节更多，说明相同情况下控制开销更多，在一定时间内，传输数据的时延更大，所以tcp不适合用于即时场景

  • 从TCP报文格式还可以看出，tcp存在多个控制位，意味着会交互更多的控制信息；从控制位字段可以看出，比如syn fin ack，tcp会发送控制消息进行握手，这样一来传输信息更加可靠，是面向连接的；窗口位，意味着tcp有拥塞控制优势

  • udp报文头部有数据长度字段，而tcp没有，只有头部偏移字段，意味着udp是一包一包数据传输，发端和收端不会分片或者重组，能很快识别这包数据；而tcp是流，每次是个数据块，也就是沾包，这是tcp独有的特性

  • 任何一个协议的机制有优点肯定有缺点，就像tcp，发送数据前增加了握手，虽然保证了可靠性，但是同样带来了更多的控制开销和数据时延，怎样平衡它们的优缺点就是看应用场景；任何一个协议，它的特点或者想实现什么功能，最终都会体现在报文格式或者底层叫做帧格式上面

• 描述三次握手的过程

  假设 A 为客户端，B 为服务器端。

  • 首先 B 处于 LISTEN（监听）状态，等待客户的连接请求。
  • A 向 B 发送连接请求报文，SYN=1，ACK=0，选择一个初始的序号 x。
  • B 收到连接请求报文，如果同意建立连接，则向 A 发送连接确认报文，SYN=1，ACK=1，确认号为 x+1，同时也选择一个初始的序号 y。
  • A 收到 B 的连接确认报文后，还要向 B 发出确认，确认号为 y+1，序号为 x+1。
  • B 收到 A 的确认后，连接建立

• 为什么要进行三次握手？

  原因一：TCP 是全双工可靠的传输协议，全双工意味着双方能够同时向对方发送数据，可靠意味着我发送的数据必须确认对方完整收到。TCP 通过序列号来保证这两种性质的，三次握手就是互换序列号的一次过程，可以确保双方的发信和收信能力都是正常的

  原因二：第三次握手是为了防止失效的连接请求到达服务器，让服务器错误打开连接。客户端发送的连接请求如果在网络中滞留，那么就会隔很长一段时间才能收到服务器端发回的连接确认。客户端等待一个超时重传时间之后，就会重新请求连接。但是这个滞留的连接请求最后还是会到达服务器，如果不进行三次握手，那么服务器就会打开两个连接。如果有第三次握手，客户端会忽略服务器之后发送的对滞留连接请求的连接确认，不进行第三次握手，因此就不会再次打开连接

• 三次握手的第三次握手发送ACK能携带数据吗？

  答：可以。第三次握手，在客户端发送完ACK报文后，就进入 ESTABLISHED 状态，当服务器收到这个，服务器变为ESTABLISHED状态，可以直接处理携带的数据。

• 不携带数据的 ACK 不会超时重传

• 为什么 TCP4 次挥手时等待为 2MSL？

  原因一：A 发送完释放连接的应答并不知道 B 是否接到自己的 ACK，所以有两种情况 1）如果 B 没有收到自己的 ACK，会超时重传 FIN，那么 A 再次接到重传的 FIN，会再次发送 ACK 2）如果 B 收到自己的 ACK，也不会再发任何消息，包括 ACK 无论是 1 还是 2，A都需要等待，要取这两种情况等待时间的最大值，以应对最坏的情况发生，这个最坏情况是：去向ACK消息最大存活时间（MSL) + 来向 FIN 消息的最大存活时间(MSL)， 这就是2MSL( Maximum Segment Life)。等待 2MSL 时间，A 就可以放心地释放 TCP 占用的资源、端口号，此时可以使用该端口号连接任何服务器。

  **原因二：**等待一段时间是为了让本次连接持续时间内所产生的报文都从网络中消失，否则存活在网络里的老的TCP报文可能与新TCP连接报文产生冲突（比如连接同一个端口），为避免此种情况，需要耐心等待网络老的 TCP 连接的活跃报文全部消失，2MSL 时间可以满足这个需求（尽管非常保守）

• 为什么连接的时候是三次握手，关闭的时候却是四次握手？

  答：因为当 Server 端收到 Client 端的 SYN 连接请求报文后，可以直接发送 SYN+ACK 报文。其中 ACK 报文是用来应答的，SYN 报文是用来同步的。但是关闭连接时，当 Server 端收到 FIN 报文时，很可能数据还没有处理完成，所以只能先回复一个 ACK 报文，告诉 Client 端，"你发的 FIN 报文我收到了"。只有等到 Server 端所有的报文都发送完了，才能发送 FIN 报文，因此不能一起发送。故需要四步握手

• TCP 协议如何保证可靠传输？

• 从浏览器地址栏输入 URL 到请求返回发生了什么？
  • 进行 URL 解析，进行编码
  • DNS 解析，顺序是先查 hosts 文件是否有记录，有的话就会把相对应映射的 IP 返回，然后去本地 DNS 缓存中寻找，然后去找计算机上配置的 DNS 服务器上有或者有缓存，最后去找全球的根 DNS 服务器，直到查到为止
  • 查找到 IP 之后，进行 TCP 协议的三次握手，发出 HTTP 请求
  • 服务器处理请求，返回响应
  • 浏览器解析渲染页面

• 操作系统？

  控制和管理计算机硬件与软件资源的，并合理的组织和调度计算机工作的程序

  特征：并发、异步、共享、虚拟

• 什么是系统调度？

  在用户程序中调用操作系统提供的核心态级别的子功能，结合用户态和核心态区别回答，一般使用陷入（trap），按调用功能分为：设备管理、文件管理、进程控制、进程通信、内存管理

• 进程线程？

  进程：程序是静止的，进程是程序的一次执行过程，是系统资源分配的基本单位

  线程：轻量级进程，是CPU的执行单元，是独立调度的最小单位，只拥有一点必不可少的资源

  关系：一个进程中包含多个线程，线程之间共享进程的资源，进程之间是相互独立

  区别：资源、并发、切换、通信、

  进程特征：并发、异步、动态、独立

• 进程通信的方式？

  同一台计算机的进程通信称为 IPC（Inter-process communication）

  • 信号量：信号量是一个计数器，用于多进程对共享数据的访问，解决同步相关的问题并避免竞争条件
  • 共享存储：多个进程可以访问同一块内存空间，需要使用信号量用来同步对共享存储的访问
  • 管道通信：管道是用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，pipe文件
    • 匿名管道(Pipes) ：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信，只支持半双工通信
    • 命名管道(Names Pipes)：以磁盘文件的方式存在，可以实现本机任意两个进程通信，遵循FIFO
  • 消息队列：内核中存储消息的链表，由消息队列标识符标识，能在不同进程之间提供全双工通信，对比管道：
    • 匿名管道存在于内存中的文件；命名管道存在于实际的磁盘介质或者文件系统；消息队列存放在内核中，只有在内核重启（操作系统重启）或者显示地删除一个消息队列时，该消息队列才被真正删除
    • 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收

  不同计算机之间的进程通信，需要通过网络，并遵守共同的协议，例如 HTTP

  • 套接字：与其它通信机制不同的是，它可用于不同机器间的进程通信

• 临界资源？

  临界资源：一次允许一个进程使用的资源

  临界区：访问临界资源的代码，必须互斥的进行

  • 同步：多个进程先后执行关系
  • 互斥：多个进程在同一时刻只有一个进程能进入临界区

• 线程间的同步的方式有哪些呢?

  信号量(Semphares) ：是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作，

  • down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断
  • 如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex）

  管程：Java 中的 synchronized

• 进程状态转换：

• 死锁问题：

  预防死锁：

  • 破坏互斥条件：有些资源必须互斥使用，无法破环互斥条件
  • 破坏不剥夺条件：增加系统开销，降低吞吐量
  • 破坏请求和保持条件：严重浪费系统资源，还可能导致饥饿现象
  • 破坏循环等待条件：浪费系统资源，并造成编程不便

  避免死锁：

  • 安全状态：能找到一个分配资源的序列能让所有进程都顺序完成
  • 银行家算法：采用预分配策略检查分配完成时系统是否处在安全状态

  检测死锁：利用死锁定理化简资源分配图以检测死锁的存在

  解除死锁：

  • 资源剥夺法：挂起某些死锁进程并抢夺它的资源，以便让其他进程继续推进
  • 撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源
  • 进程回退法：让一个或多个进程回退到足以回避死锁的地步

• 操作系统的内存管理主要是做什么？

  操作系统的内存管理主要负责内存的分配与回收，地址转换也就是将逻辑地址转换成相应的物理地址

• 内存管理有哪几种方式？

  连续分配管理方式：块式管理，将内存分为几个固定大小的块，每个块中只包含一个进程

  非连续分配管理方式：分页存储，分段存储，段页式管理

• 分页机制和分段机制有哪些共同点和区别呢？

  共同点 ：

  • 分页机制和分段机制都是为了提高内存利用率，较少内存碎片

    分页、段页式：内部碎片

  • 以两者都是离散分配内存的方式。但是，每个页和段中的内存是连续的

  不同点：

  • 分页对程序员是透明的，但是分段需要程序员显式划分每个段
  • 分页是一维地址空间，分段是二维地址空间
  • 页的大小是固定的，由操作系统决定；而段的大小不固定，取决于我们当前运行的程序
  • 分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护

• 快表和多级页表

  快表：虚拟地址到物理地址的转换要快

  • CPU给出逻辑地址，地址转换后先去快表（高速缓存寄存器）中查询，如果有就直接读取物理地址
  • 如果没有就去访问主存中的页表，读出以后同时存入快表
  • 当快表填满，就按照淘汰策略淘汰旧的页表项

  多级页表：为了避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中

• 什么是CPU寻址？

  现代处理器使用的是一种称为虚拟寻址（Virtual Addressing）的寻址方式。使用虚拟寻址 CPU 将虚拟（逻辑）地址翻译成物理地址，这样才能访问到真实的物理内存。 实际上完成虚拟地址转换为物理地址转换的硬件是 CPU 中含有一个被称为内存管理单元（Memory Management Unit, MMU）的硬件

  虚拟地址空间好处：防止用户程序可以访问任意内存，寻址内存的每个字节，这样很容易破坏操作系统，造成操作系统崩溃

• 局部性原理？

  时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作

  空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的

• 虚拟存储器？

  虚拟存储器又叫做虚拟内存，都是 Virtual Memory 的翻译，属于同一个概念

  基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其他部分留在外存，就可以启动程序执行；由于外存往往比内存大很多，所以我们运行的软件的内存大小实际上是可以比计算机系统实际的内存大小大的。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序；另一方面，操作系统将内存中暂时不使用的内容换到外存上，从而腾出空间存放将要调入内存的信息。这样，计算机好像为用户提供了一个比实际内存大的多的存储器就是虚拟存储器

  因为这中存储器实际上不存在，只是系统提供了部分载入、请求调入和置换功能后，是对用户透明的

• 虚拟内存技术的实现呢？

  请求分页存储管理、请求分段存储管理、请求段页式存储管理

  请求分页与分页存储管理的不同点：根本区别是是否将程序全部所需的全部地址空间都装入主存

  • 在载入程序的时候，只需要将程序的一部分装入内存，而将其他部分留在外存，然后程序就可以执行了

  • 缺页中断：如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序；

  • 虚拟地址空间：逻辑地址到物理地址的变换