【笔记】408刷题笔记

为了区分队空队满，可以使用三种处理方式
1）牺牲一个单元 队头指针在队尾指针的下一位置作为队满的标志

• 队满条件：(Q.rear+1)%MaxSize==Q.front
• 队空条件：Q.front==Q.rear
• 队列中元素的个数:(Q.rear-Q.front+MaxSize)%MaxSize

2. 设置tag数据队员 区分队满队空
3. 类型中增设表示元素个数的数据队员

森林转换为二叉树时满足左孩子，右兄弟，如果二叉树中左指针为空，说明在森林中该界定啊没有孩子，即该节点在森林中为叶子节点。

B树中所有结点的孩子结点数最大值称为B树的阶（m）

• 树中每个节点至多有m棵子树，即m-1个关键字
• 若根节点不是终端结点，至少有2棵子树
• 除根结点外的所有非叶结点至少有⌈m/2⌉ 棵子树，（即至少含有⌈m/2⌉-1个关键字）
• 结点中关键字个数n满足⌈m/2⌉ 1<=n<=m-1
• 所有叶节点都在同一层次上

平衡二叉树的查找：平均查找长度为$O(lo{g}_{2}n)$

• 每个结点最多有m-1个关键字（m指阶数，阶代表B树中所有节点的孩子个树的最大值），至少有m棵子树；
• 根节点最少可以只有1个关键字（若根节点为非终端结点，最少有两棵子树）；
• 非根节点至少有⌈m/2⌉-1个关键字；
• 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键都大于它；
• 所有叶子节点都位于同一层，并且不携带信息（即绝对平衡）；
• 每个节点都存有索引和数据，也就是对应的key和value。

三对角

小根堆的调整操作：插入关键字x时候，先将其放在小顶堆的末端，再将该关键字向上进行调整。

平衡二叉树
链接

B-树删除操作：

• 被删关键字所在结点中的关键字数目不小于「m/2]，直接删
• 兄弟够借，被删关键字所在结点中的关键字数目等于「m/2]-1，与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目【大于】「m/2]-1，将其兄弟结点中的最小（或最大）的关键字上移至双亲结点中，
• 兄弟不够借，被删关键字所在结点和其相邻的兄弟结点中的关键字数目【均等于】「m/2]-1。假设该结点有右兄弟， 且其右兄弟结点地址由双亲结点中的指针pi 所指，则在删去关键字之后， 它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起， 合并到pi 所指兄弟结点中
  
  参考文章
  链接

三叉树求最小带权路径

2、3、4、5、6、7

需要补一个0权值的结点
最小带权路径
链接
为啥补零

段是不定长的连续区域

slab分配器，采用伙伴关系内存管理方式。有以下三个基本目标：

1. 减少伙伴算法在分配小块连续内存是所产生的内部碎片
2. 将频繁使用的对象缓存起来，减少分配，初始化和释放对象的时间开销
3. 通过着色技术调整对象以更好地使用硬件高速缓存

为了使用磁盘存储文件，操作系统还需要将数据结构记录在磁盘上。
磁盘格式化

• 物理格式化 分区 为每个扇区采用特别的数据结构，包括校验码。
• 逻辑格式化（创建文件系统）
  • 将初始化的文件系统数据结构存储到磁盘上，这些数据结构包括空闲和已分配的空间及一个初始为空的目录。

以簇为单位进行空间分配

软链接新增文件时计数值直接复制
硬链接就是多个指针指向一个索引节点
文件的物理地址和其他文件属性信息放在索引节点中
硬链接不可用于跨文件系统
硬链接查找速度比软链接快

平均查找扇区时间是磁盘【转半圈】的时间
平均寻道时间

索引节点个数就是文件的总数，与单个文件的长度无关
单个文件长度主要取决于两个因素：

• 文件系统索引节点中地址项个数
• 间接地址索引的级数

不会导致磁臂黏着的是：先来先服务（FCFS）

FAT12文件系统
紧接着引导扇区的是两个完全相同的FAT表，每个FAT表占用9个扇区

1. UNIX系统中，文件的索引结构存放在inode节点中，每个文件都有一个inode节点，包含了文件的元数据信息，如文件大小，创建时间，访问权限等。
2. 超级块存储的是文件系统的元数据信息
3. 目录块存储的是文件或目录的名称和inode指针等信息
4. 空闲块存储的是未被分配的磁盘块信息

文件目录的重要作用是按名存取

open函数需要文件名（包含路径），之后会给一个文件描述符返回给进程

• 设备独立性程序：实现逻辑设备名到物理设备名的映射
• 设备驱动程序:将I/O请求转换为具体信号（物理I/O操作）

read系统调用和write系统调用均在open调用之后，仅需提供文件描述符fd和其他参数，不用文件名

read系统调用要求用户提供三个输入参数：

• 文件描述符
• buf缓冲区首址
• 传送的字节数n 没有文件名

TCP中，发送窗口的大小为N,意味着在没有收到确认的情况下可以连续发送N个字节。
可靠的传输协议：使用确认机制保证传输数据的不丢失

拥塞窗口到12发生超时，门限值为6
慢启动从1，2，4开始，然后到6之后以公差为1进行递增

UDP报文首部和TCP报文首部

udp报文首部不包含目的地址，目的地址是在检验时候加上去的伪首部。
udp报文之后使用ip头进行封装，ip头有目的ip地址
tcp报文的头也是没有目的ip地址的

IP报文首部

TCP报文首部

TCP报文由首部和数据两部分组成。首部一般由20-60字节（Byte）构成，长度可变。其中前20B格式固定，后40B为可选。

1、源端口号（Source Port）
16位的源端口字段包含初始化通信的端口号。源端口和IP地址的作用是标识报文的返回地址。

2、目的端口号（Destination Port）
　16位的目的端口字段定义传输的目的。这个端口指明接收方计算机上的应用程序接口。

3、序列号（Sequence Number）
该字段用来标识TCP源端设备向目的端设备发送的字节流，它表示在这个报文段中的第几个数据字节。序列号是一个32位的数。

4、确认号（Acknowledge Number）
　　TCP使用32位的确认号字段标识期望收到的下一个段的第一个字节，并声明此前的所有数据已经正确无误地收到，因此，确认号应该是上次已成功收到的数据字节序列号加1。收到确认号的源计算机会知道特定的段已经被收到。确认号的字段只在ACK标志被设置时才有效。
5、首部长度
长度为4位，用于表示TCP报文首部的长度。用4位（bit）表示，十进制值就是[0,15]，一个TCP报文前20个字节是必有的，后40个字节根据情况可能有可能没有。如果TCP报文首部是20个字节，则该位应是20/4=5。
6、保留位（Reserved）
长度为6位，必须是0，它是为将来定义新用途保留的。
7、标志（Code Bits）
长度为6位，在TCP报文中不管是握手还是挥手还是传数据等，这6位标志都很重要。6位从左到右依次为：
• URG：紧急标志位，说明紧急指针有效；
• ACK：确认标志位，多数情况下空，说明确认序号有效； 取1时表示应答字段有效，也即TCP应答号将包含在TCP段中，为0则反之。
• PSH：推标志位，置位时表示接收方应立即请求将报文交给应用层；
• RST：复位标志，用于重建一个已经混乱的连接，用来复位产生错误的连接，也会用来拒绝错误和非法的数据包。
• SYN：同步标志，该标志仅在三次握手建立TCP连接时有效
• FIN：结束标志，表示发送端已经发送到数据末尾，数据传送完成，发送FIN标志位的TCP段，连接将被断开。
8、窗口大小（Window Size）
长度为16位，TCP流量控制由连接的每一端通过声明的窗口大小来提供。
9、检验和（Checksum）
长度为16位，该字段覆盖整个TCP报文端，是个强制性的字段，是由发送端计算和存储，到接收端后，由接收端进行验证。
10、紧急指针（Urgent Pointer）
长度为16位，指向数据中优先部分的最后一个字节，通知接收方紧急数据的长度，该字段在URG标志置位时有效。
11、选项（Options）
长度为0-40B（字节），必须以4B为单位变化，必要时可以填充0。通常包含：最长报文大小（MaximumSegment Size，MSS）、窗口扩大选项、时间戳选项、选择性确认（Selective ACKnowlegement，SACK）等。
12、数据
可选报文段数据部分。

UDP报文首部

UDP数据报由首部和数据两部分组成，其中首部只有8B（字节）。
1、源端口号（Source Port）
长度为16位，指明发送数据的进程。
2、目的端口号（Destination Port）
长度为16位，指明目的主机接收数据的进程。
3、长度
长度为16位，该字段值为报头和数据两部分的总字节数。
4、检验和（Checksum）
长度为16位，UDP检验和作用于UDP报头和UDP数据的所有位。由发送端计算和存储，由接收端校验。
5、数据

参考链接

TCP既有流量控制也有拥塞控制。TCP在发送数据的时候要考虑拥塞窗口也要考虑接受窗口。TCP能够发送的最大字节数要受到两窗口最小值的限制

---

【TCP首部长度必须是4B的整数倍】
某TCP分组的选项字段长度为9B,该TCP分组的数据偏移字段1000
【TCP首部长度必须是4B的整数倍】，这里报头定长20B不定长选项9B之和为29B
并不是4B的整数倍，所以需要填充3B
此报文首部的长度为32B
32B/4=8 二进制表示为1000

---

门限值变成16后，超时后处于慢启动阶段的为4RTT
发送窗口的初始值设置为1，然后依次增大为2、4、8、16，需要经过4个RTT
UDP不适用于远程登录（需要可靠链接），适用于实时性高的应用(实时性应用，【远程调用rdp】，【客户/服务器领域】 编码简单，需要很少的信息)

一个udp用户数据包数据字段为8192B，链路层使用以太网来传输，应该分成6个ip数据报

以太网帧的最大数据负载是1500B，ip首部长度为20B，数据字段长度为1480B，udp数据字段可被分为8192/1480 -> 6

根域名-顶级域名-权限域名-本地域名
dns解析时过程：本地域名，根域名，顶级域名，权限域名

ftp：21控制和20数据连接0
邮件服务器的功能：监控邮件
电子邮件系统中用户代理的功能：

1. 处理邮件
2. 显示邮件
3. 撰写邮件

采用客户机/服务器模型的主要原因：
4. 更好实现资源共享
5. 通信的异步问题
客户机提交查询请求，服务器返回查询结果
网络传输线路上之传送【请求命令】和【执行结果】，从而降低通信开销

集中目录式p2p网络结构代表性软件：Napster,Maze
分布式非结构化p2p网络：Gnutella
分布式结构化：Pastry,Tapestry,Chord,CAN
混合式：Skype,eDonkey,BitTorent,PPLive

客户机是面向用户的（通常位于前端），服务器是面向任务的（通常位于后端）
客户机和服务器之间通过网络实现协同计算
p2p是网络结点之间采取对等方式直接交换信息的工作模式

域名和地址可以是一对多，多对一的关系
www不是一种协议，而是应用层提供的一种最为重要和普及的服务
www中网站唯一地址：统一资源定位符URL
http详细规定了浏览器和万维网服务器之间相互通信的规则

发送邮件使用的协议SMTP
收取邮件使用的协议：POP3和IMAP

刷新和再生的区别

参考地址
对于破坏性读出的存储器进行读/写操作时，为维持原信息不变，必须辅以的操作是：再生
刷新
DRAM中刷新和重写的区别
在DRAM(动态随机存取存储器)中，刷新和重写是两个不同的操作。

1.刷新(Refresh):DRAM是一种易失性存储器，它的存储单元是由电容构成的。由于电容的特性，它们会逐渐丧失电荷，导致存储的数据逐渐衰减。为了防止数据丢失，DRAM需要定期进行刷新操作。刷新操作是将存储单元中的数据读出并重新写入，以恢复电荷状态并保持数据的完整性。刷新操作通常由DRAM控制器自动执行，遵循内存芯片制造商指定的刷新频率。

2.重写(Rewrite):重写是指将新的数据写入DRAM的过程。当CPU或其他设备需要将新的数据存储到DRAM中时，它会发送写入指令，将数据写入到指定的DRAM存储单元中。重写操作会覆盖原有的数据，并更新存储单元中的内容。重写可以是随机的，根据需要进行读写操作。

总结来说，刷新是为了防止数据丢失而对DRAM中的数据进行定期读取和重新写入操作，而重写是将新的数据写入到DRAM中，覆盖原有的数据。刷新是为了保持数据的完整性，而重写是为了更新数据。

–

地址译码

地址译码电路有单译码和双译码两个方式：
单译码只有一个译码器，双译码方式有两个译码器(X和Y地址译码器)
XY两个方向译码器输出线在存储体内部的一个记忆单元上交叉，以选择相应的记忆单元
单译码输入线6，译码输出线64($2^6$)根
双译码输入线6，译码输出线16（$2^3+2^3$）

存储器采用部分译码法片选时，会产生地址重叠

直接映像（一Cache对多主存）

直接映射就是一个Cache页面对应多个主存页面。
直接映射函数为: i = j % 2c，其中i是Cache页号；j是主存页号。

例如：主存的页面0 % 2c = 0 ，只能映射到Cache的页面0
例如：主存的页面（2c+ 1）% 2c =1，只能映射到Cache的页面1
在Cache中给每个页面设一个t位长的标记(t = m -c)，主存某一页调入了Cache后，就将主存页号的高t位放入Cache相应的那个页的标记中。

容量64块的cache采用组相联映射方式，字块大小为128个字，每4块为1组。如果主存为4k块，且按字编址，那么主存地址和主存标记的位数分别为
主存容量：4k*128字=2^19字(按字编址，主存地址19位)
组号：cache被分的组号 64/4=16(组号4位)
块号：块内地址(128个字 7位)
（组相联）主存标记=主存地址大小-组号-块号=19-4-7=8位

DRAM集中刷新刷新一行需要一个存储周期

位扩展之后作为【一个存储体】进行地址选择
块冲突概率最小的是全相联映射

LRU将在cache中驻留时间最长而且没有使用的块作为被替换的块

零操作数可能隐含操作数，在【堆栈】中

JMP指令程序总是顺序执行，指令本身无堆栈操作过程
CALL指令跳转到指定目标程序执行子程序，执行完子程序后，会返回CALL指令的【下一条指令处】执行程序，执行CALL指令有堆栈过程。

中断返回被中断的那一条指令继续执行

操作码OP 操作数/地址码（被执行的对象）

处于硬件和软件交界面的是：指令系统

返回指令RET和中断返回指令
return（RET）可以是人为编写的，可以携带操作数
中断返回指令是特权指令，程序员不可以编写，不携带操作数

DRAM即使不断电，在规定时间内没有及时刷新，存储信息也会丢失

低位交叉存储器

• 轮流启动 连续的地址分布在相邻的块中，同一模块内的地址都是不连续的，采用分时启动的方法。 连续读出4个字所需要的时间t=T+(m-1)*r,每1/4存储周期启动一个体，每1/4个存储周期可以读出或写入一个数据，存取速度提高m倍
• 同时启动

高位交叉编址/连续编址方式：主存地址的高位表示模块号（体号），低位表示模块内地址（或体内地址）。地址在模块内连续

cache与主存一致性：

1. 写回法
2. 直写法

cache完全由硬件实现，不涉及软件
虚拟存储器由硬件和os共同完成
虚拟存储器中，主存的内容只是辅存的一部分
虚拟存储器【失效】时处理器会【切换进程】来更新内存