学做网站的笔记本,那些做电影视频网站的赚钱吗,京东网站建设吗,厦门建设局官网文章目录 三对角三叉树求最小带权路径UDP报文首部和TCP报文首部IP报文首部TCP报文首部UDP报文首部 刷新和再生的区别地址译码 为了区分队空队满#xff0c;可以使用三种处理方式 1#xff09;牺牲一个单元 队头指针在队尾指针的下一位置作为队满的标志 队满条件#xff1a;(… 文章目录 三对角三叉树求最小带权路径UDP报文首部和TCP报文首部IP报文首部TCP报文首部UDP报文首部 刷新和再生的区别地址译码 为了区分队空队满可以使用三种处理方式 1牺牲一个单元 队头指针在队尾指针的下一位置作为队满的标志 队满条件(Q.rear1)%MaxSizeQ.front队空条件Q.frontQ.rear队列中元素的个数:(Q.rear-Q.frontMaxSize)%MaxSize
设置tag数据队员 区分队满队空类型中增设表示元素个数的数据队员
森林转换为二叉树时满足左孩子右兄弟如果二叉树中左指针为空说明在森林中该界定啊没有孩子即该节点在森林中为叶子节点。
B树中所有结点的孩子结点数最大值称为B树的阶m
树中每个节点至多有m棵子树即m-1个关键字若根节点不是终端结点至少有2棵子树除根结点外的所有非叶结点至少有⌈m/2⌉ 棵子树即至少含有⌈m/2⌉-1个关键字结点中关键字个数n满足⌈m/2⌉ 1nm-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 慢启动从124开始然后到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/45。 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 SizeMSS、窗口扩大选项、时间戳选项、选择性确认Selective ACKnowlegementSACK等。 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/48 二进制表示为1000 门限值变成16后超时后处于慢启动阶段的为4RTT 发送窗口的初始值设置为1然后依次增大为2、4、8、16需要经过4个RTT UDP不适用于远程登录需要可靠链接适用于实时性高的应用(实时性应用【远程调用rdp】【客户/服务器领域】 编码简单需要很少的信息)
一个udp用户数据包数据字段为8192B链路层使用以太网来传输应该分成6个ip数据报
以太网帧的最大数据负载是1500Bip首部长度为20B数据字段长度为1480Budp数据字段可被分为8192/1480 - 6
根域名-顶级域名-权限域名-本地域名 dns解析时过程本地域名根域名顶级域名权限域名
ftp21控制和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^32^3 2323
存储器采用部分译码法片选时会产生地址重叠
直接映像一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/416(组号4位) 块号块内地址(128个字 7位) 组相联主存标记主存地址大小-组号-块号19-4-78位
DRAM集中刷新刷新一行需要一个存储周期
位扩展之后作为【一个存储体】进行地址选择 块冲突概率最小的是全相联映射
LRU将在cache中驻留时间最长而且没有使用的块作为被替换的块
零操作数可能隐含操作数在【堆栈】中
JMP指令程序总是顺序执行指令本身无堆栈操作过程 CALL指令跳转到指定目标程序执行子程序执行完子程序后会返回CALL指令的【下一条指令处】执行程序执行CALL指令有堆栈过程。
中断返回被中断的那一条指令继续执行
操作码OP 操作数/地址码被执行的对象
处于硬件和软件交界面的是指令系统
返回指令RET和中断返回指令 returnRET可以是人为编写的可以携带操作数 中断返回指令是特权指令程序员不可以编写不携带操作数
DRAM即使不断电在规定时间内没有及时刷新存储信息也会丢失
低位交叉存储器
轮流启动 连续的地址分布在相邻的块中同一模块内的地址都是不连续的采用分时启动的方法。 连续读出4个字所需要的时间tT(m-1)*r,每1/4存储周期启动一个体每1/4个存储周期可以读出或写入一个数据存取速度提高m倍同时启动
高位交叉编址/连续编址方式主存地址的高位表示模块号体号低位表示模块内地址或体内地址。地址在模块内连续
cache与主存一致性
写回法直写法
cache完全由硬件实现不涉及软件 虚拟存储器由硬件和os共同完成 虚拟存储器中主存的内容只是辅存的一部分 虚拟存储器【失效】时处理器会【切换进程】来更新内存
