目录 基本实现 1、用无序向量实现 2、有序向量 3、无序列表 4、有序化列表 7、Complete Binary Heap 应用：堆排序 0、堆序性​​ 建堆​​  1、插入 2、删除 3、建堆 4、堆排序 5、左式堆 6、右侧链 7、合并     基本实现 1、用无序向量实现    2、有序向量   3、无序列表   4、有序化列表  5、平衡二叉搜索树  6、完全二叉树  7、Complete Binary Heap Complete Binary Heap = Complete Binary Tree + Vector  应用：堆排序 0、堆序性 建堆          1、插入  p...

10b2-4  完全二叉堆插入时， 父子词条之间的比较可有所改进。   在随机分布下，每个节点平均上升的高度是常数。   

  目录 ​ 流水线的性能指标​ 流水线的冲突  流水线的分类​ 流水线的多发技术 ​       流水线的性能指标        流水线的冲突         流水线的分类 流水线的多发技术     

     

1bit sliding window protocol 窗口大小：N = 1 ◼ 发送序号和接收序号的取值范围：0，1 go back n 发送窗口大于1，接收窗口为1   selective repeat 发送窗口大于1，接收窗口大于1 

dsa prim distracture不能出现权值为负的边。 kis

   BGP协议               

 算法效率  稳定性

目录 FCFS​  SSTF​  SCAN​  LOOK​  C-SCAN​  C-LOOK​     FCFS  SSTF  SCAN  LOOK  C-SCAN  C-LOOK

处理机调度算法 全局页面置换算法 局部页面置换算法 磁盘调度算法

TLB 因为页表存在主存中，得访问两次主存才能取出物理块号。第一次查询内存中的页表，第二次访问该物理地址对应的内存单元。根据局部性原理，把经常访问的下一页表项缓存到CPU里面，利用缓存机制来减少对内存的访问。  页号与页表页表长度对比，看是否发生越界； 未越界，快表未命中； 根据页表始址和页号查找相应的内存块号； 复制页表项到tlb中；     快表的地址变换过程       

the question of page table：   就像分散的物理内存给之编号顺序的逻辑页号，将其对应关系存入页表中，变离散为连续一样；将很大的、连续的页表分组，并给之编号。 将这些编号存入一级页表，称为页目录表，存放了二级页表的页号和存放地址的内存块号。    一个大的页表切成的块数和最后一级页表的宽度是一致的； 每一个子页表的起头作为上一级页表的物理页号；    多级页表地址变换   ptbr提供起始，第一级作为第一级页表项的偏移；找到第二级页表上的起始，其存储的数据作为偏移；找到第三级页表项的起始，找到物理块号。 根据存在位，把不需要的页表项拿掉，有效地节省内存。    

cache和主存的映射方式  cache行的行长和主存块大小一致。逻辑页面和物理内存块大小相等。翻译：前提已知page frame（帧）和page（页）大小是一样的，这是物理内存和虚拟内存里的说法；在物理内存和cache里cache一行存主存一行的内容。 主存  <caption> 主存地址 </caption>   标记 索引 块内偏移地址     <caption> cache地址 </caption>   有效位1位 标志位 数据     全相联映射：主存先到相联存储器的页目录表上查找主存块号（这是比较器），若有效位=1，去cache查对应...