文章目录
- 三对角
- 三叉树求最小带权路径
- UDP报文首部和TCP报文首部
- IP报文首部
- TCP报文首部
- UDP报文首部
- 刷新和再生的区别
- 地址译码
为了区分队空队满,可以使用三种处理方式
1)牺牲一个单元 队头指针在队尾指针的下一位置作为队满的标志
- 队满条件:
(Q.rear+1)%MaxSize==Q.front
- 队空条件:
Q.front==Q.rear
- 队列中元素的个数:
(Q.rear-Q.front+MaxSize)%MaxSize
- 设置tag数据队员 区分队满队空
- 类型中增设表示元素个数的数据队员
森林转换为二叉树时满足左孩子,右兄弟,如果二叉树中左指针为空,说明在森林中该界定啊没有孩子,即该节点在森林中为叶子节点。
B树中所有结点的孩子结点数最大值称为B树的阶(m)
- 树中每个节点至多有m棵子树,即m-1个关键字
- 若根节点不是终端结点,至少有2棵子树
- 除根结点外的所有非叶结点至少有⌈m/2⌉ 棵子树,(即至少含有⌈m/2⌉-1个关键字)
- 结点中关键字个数n满足⌈m/2⌉ 1<=n<=m-1
- 所有叶节点都在同一层次上
平衡二叉树的查找:平均查找长度为 O ( l o g 2 n ) O(log_2n) O(log2n)
- 每个结点最多有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分配器,采用伙伴关系内存管理方式。有以下三个基本目标:
- 减少伙伴算法在分配小块连续内存是所产生的内部碎片
- 将频繁使用的对象缓存起来,减少分配,初始化和释放对象的时间开销
- 通过着色技术调整对象以更好地使用硬件高速缓存
为了使用磁盘存储文件,操作系统还需要将数据结构记录在磁盘上。
磁盘格式化
- 物理格式化 分区 为每个扇区采用特别的数据结构,包括校验码。
- 逻辑格式化(创建文件系统)
- 将初始化的文件系统数据结构存储到磁盘上,这些数据结构包括空闲和已分配的空间及一个初始为空的目录。
以簇为单位进行空间分配
软链接新增文件时计数值直接复制
硬链接就是多个指针指向一个索引节点
文件的物理地址和其他文件属性信息放在索引节点中
硬链接不可用于跨文件系统
硬链接查找速度比软链接快
平均查找扇区时间是磁盘【转半圈】的时间
平均寻道时间
索引节点个数就是文件的总数,与单个文件的长度无关
单个文件长度主要取决于两个因素:
- 文件系统索引节点中地址项个数
- 间接地址索引的级数
不会导致磁臂黏着的是:先来先服务(FCFS)
FAT12文件系统
紧接着引导扇区的是两个完全相同的FAT表,每个FAT表占用9个扇区
- UNIX系统中,文件的索引结构存放在inode节点中,每个文件都有一个inode节点,包含了文件的元数据信息,如文件大小,创建时间,访问权限等。
- 超级块存储的是文件系统的元数据信息
- 目录块存储的是文件或目录的名称和inode指针等信息
- 空闲块存储的是未被分配的磁盘块信息
文件目录的重要作用是按名存取
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
邮件服务器的功能:监控邮件
电子邮件系统中用户代理的功能:
- 处理邮件
- 显示邮件
- 撰写邮件
采用客户机/服务器模型的主要原因:
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
2^6
26)根
双译码输入线6,译码输出线16(
2
3
+
2
3
2^3+2^3
23+23)
存储器采用部分译码法片选时,会产生地址重叠
直接映像(一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与主存一致性:
- 写回法
- 直写法
cache完全由硬件实现,不涉及软件
虚拟存储器由硬件和os共同完成
虚拟存储器中,主存的内容只是辅存的一部分
虚拟存储器【失效】时处理器会【切换进程】来更新内存