面试八股文问题_游戏服务端八股文面试题

数据结构

计算机网络

应用层(HTTP）
传输层(TCP,UDP)
网络层(IP,ICMP)
数据链路层
物理层

TCP/IP协议五角星

面向连接的由传输层保证可靠传输。

三次握手，四次挥手

三次握手：保证客户的和服务端都能成功地发送和接收数据。

四次挥手：前两次挥手保证客户端不再发送数据，服务端不再接收数据；后两次挥手保证服务端不再发送数据，客户端不再接收数据。

最后一次挥手之后客户端为什么不直接关闭，且要等待2MSL？
保证服务端能正确接收到客户端发送的最后一次挥手能够正常关闭，没有接收到时需要重传。

为什么不采用两次握手？
防止产生错误的连接请求：若客户端第一个连接请求在网络中滞留时，客户端又发送了第二个连接请求，此时连接建立并传送完数据。之后，第一个连接请求到达，服务端以为客户端又要建立连接，就会造成服务端资源的浪费。如果采用三次握手，没有第三次握手，那么服务端就认为这是一个无效的连接请求，不予理睬。

为什么不采用三次挥手？
因为要保证客户端能正确接受完服务端发送的所有数据，如果第三次挥手就断开连接，那么发送缓存中的数据就不能超时重传，无法保证客户端正确接收所有的数据。

滑动窗口（流量控制，拥塞控制）

在发送缓存区维护一个滑动窗口，窗口在发送缓存区滑动，只有收到窗口前面的数据报的确认，窗口才会前移，没有收到ack的数据报的都等待重传。
发送窗口=min(接收窗口，拥塞窗口）

怎么实现可靠传输？

TCP使用校验，序号，确认和重传机制。
1.校验：IP协议只校验首部，TCP和UDP既校验首部又校验数据。
2.为每个报文段编号
3.累计确认：并不少收到一个报文就回复一个确认
4.重传：超时和冗余ack

滑动窗口（流量控制，拥塞控制）

在发送缓存区维护一个滑动窗口，窗口在发送缓存区滑动，只有收到窗口前面的数据报的确认，窗口才会前移，没有收到ack的数据报的都等待重传。
发送窗口=min(接收窗口，拥塞窗口）

UDP

无连接的，传输层并不保证可靠传输，由别的层实现最大交付。

网络层：网际控制报文（ICMP）

两种报文类型：
1.差错报文
2.询问报文
不再对差错报文发送差错斑纹

操作系统

进程调度算法

1.先来先服务
(1)规则:按作业和进程先后到达就绪队列的顺序进行服务
(2)非抢占
(3)优点：公平。缺点：长进程后的短作业要等很长的时间
(4)不会导致饥饿（饥饿：进程一得不到服务）

2.短时间片优先
(1)规则：最短的进程优先得到服务
(2)默认非抢占，也有抢占式版本
(3)优点：平均等待时间短。缺点：不公平，对短作业有利。
(4)会导致饥饿

3.高响应比优先( 同一个进程，等待时间越长，响应比越大）
(1)规则：最短的进程优先得到服务
(2)非抢占
(3)优点：避免长作业饥饿。
(4)不会导致饥饿

三个算法总结：不区分任务的紧急程度，和用户交互差，适合批处理系统。

4.时间片轮转
(1)规则：按进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，若一个时间片内进程没运行完，则剥夺处理剂，并把进程从新放入就绪队列的队尾。
(2)抢占
(3)优点：公平响应快。缺点：进程切换有开销，且不区分任务的紧急程度。
(4)不会导致饥饿

5.优先级调度
(1)规则：每个进程有各自的优先级，调度时选优先级最高的进程
(2)非抢占和抢占
(3)优点：区分进程的紧急程度。缺点：可能导致饥饿。
(4)会导致饥饿

6.多级反馈队列调度算法

(1)规则：
a.设置多级就绪队列，各队列优先级从高到低，时间片从小到大。
b.新进程到达时先进入第1级队列，按照先来先服务分配时间片。
c.若时间片用完还未结束，则进程放入下一级队列的队尾，如果已经在最下级队列，则从新放回队尾。
d.只有优先级为k的队列为空，才会为k+1级队列分配时间片
e.抢占式：被抢占的进程会放回原队列的队尾
(2)抢占和非抢占
(3)优点：对各进程公平；每个新到达的进程很快得到响应；短进程只用较少的时间可以完成；
(4)会导致饥饿

内存

逻辑地址(相对地址)
物理地址(绝对地址)

静态链接和动态链接相关知识

源代码文件到可运行文件到装入内存执行的过程。
区分：编译，链接，装入都在做什么

链接：把源代码文件组合成一个可执行文件

链接成装入模块的三种方式：
1.静态链接：在程序运行前把目标模块和所需的库函数连接成一个完整的可执行文件，同时形成完整的逻辑地址供装入模块装入内存时使用。

2.装入时动态链接：将各自目标模块装入内存时，边装入边链接

3.运行时动态链接：在程序执行时需要该模块时，才对它进行链接。

装入

三种装入方式完成逻辑地址到物理地址到转换
1.绝对装入
原理：在编译时就算出在程序在内存的物理地址
缺点：只适合单道程序
2.静态重定位(可重定位装入)
原理：装入时对逻辑地址进行从定位，把逻辑地址变换为物理地址
缺点：装入时分配要求的全部内存空间，内存不够就不能装入作业；运行期间不能再移动也不能申请内存空间。

3.动态重定位(动态运行时装入)
原理：维护重定位寄存器（进程的起始地址），把重定位推迟到程序要执行时进行
优点：允许程序在内存中移动；可以动态申请内存分配；可以提供一个比存储空间大的地址空间。

内存连续分配

内存分为系统区和用户区。
内部碎片：分配给进程的内存区域，有些部分没用上。
外部碎片：内存中空闲分区太小难以利用。

单一连续分配

单道程序连续放入内存，只适合单道程序。
无外部碎片，有内部碎片

固定分区分配

用户区分为若干个大小的分区，各分区只能有一个作业
无外部碎片，有内部碎片

动态分区分配：

支持多道程序，进程装入内存时，根据进程大小动态地建立分区。
无内部碎片，有外部碎片
进程结束时，这些分区就成了空闲分区。
1.要管理这些空闲分区，进行空闲分区合并和分配。
2.系统要使用空闲分区表或链表维护记录内存使用情况

1.首次适应算法

2.最佳适应算法

缺点：每次选最小的分区分配，每个分区都会有一部分用不上，因此会产生大量外部碎片

3.最坏适应算法

4.邻近适应算法（首次适应算法的改进）

总结

分页存储管理⭐️（离散内存分配）

1.页框,内存块(将内存空间氛围一个大小相等的分区)
2.页号(将用户进程划分为一个个和页框大小相等的页，每个页有一个编号，即页号)，
3.页内偏移量 ,相对于该页起始地址的偏移量

4.页表(操作系统为每个进程维护的一张记录页号和实际内存块的对应关系)

如何实现逻辑地址到物理地址到转换

1. 算出逻辑地址对应的页号：页号=逻辑地址/页面长度（向下取整）
2. 要知道页号对应的页面在内存中的起始地址
   页表：操作系统为每个进程创建一张页表记录进程页面和实际内存块的对应关系
3. 逻辑地址在页面内的偏移量： 移量=逻辑地址%页面长度
4. 物理地址=页面起始地址+页内偏移量

单级页表:基地址变换改进->快表（基于进程而言）

时间局部性：被执行的指令和被访问的数据很可能在不久之后再次被访问。(因为程序中存在大量循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也可能被访问。（因为数据在内存都是连续存放的）

基地址变换中，CPU每次访问一个逻辑地址都要查询内存中的页表。由于局部性原理可能连续多次查到同一个页表项。因此引入快表，基地址变化又称慢表。

维护一个更高速的快表，记录被使用过的进程页号，一旦在快表中查询到要访问的页号，就不需要再到慢表（页表）中去查询。
访问内存次数：
基地址变换两次：第一次访问页表，第二次访问目标内存单元
具有块表的地址变换(1或2）：第一次，在快表中访问到则不用访问页表，因此少一次。2.目标内存单元

两级页表

单级页表缺点：

二级页表结构和原理

基本分段存储管理

分页分段管理 对比

结合分页+分段 = 段页管理式方式

原理:

逻辑地址结构:

虚拟内存

传统存储管理缺点：
1.作业必须一次性全部装入内存才能允许。作业时很大无法运行，作业多就导致并发度下降。
2.一旦作业被装入就会一直驻留在内存中，直至运行结束，在一个时间段只有一小部分数据在运行，就会驻留大量无用数据，浪费资源。
因此根据时间局部性和空间局部性的特点引出->虚拟内存。

虚拟内存技术原理类似高速缓冲技术：
基于局部性原理，装入程序时，只装入很快要执行的部分到内存，用不到的留在外存。

数据库

存储引擎innodb和myisam

索引

事务

C++

网络编程