做直播网站有市场吗,中国室内设计大赛官网,php网站开发考试,网站建设毕业设计过程#x1f433;前言
考研笔记整理#xff0c;纯复习向#xff0c;思维导图基本就是全部内容了#xff0c;不会涉及较深的知识点~~#x1f95d;#x1f95d;
第1版#xff1a;查资料、画思维导图~#x1f9e9;#x1f9e9;
编辑#xff1a; 梅头脑#x1f338;
参考…前言
考研笔记整理纯复习向思维导图基本就是全部内容了不会涉及较深的知识点~~
第1版查资料、画思维导图~
编辑 梅头脑
参考用书王道考研《2024年 计算机组成原理考研复习指导》《2024年 操作系统考研复习指导》
参考视频3.1_存储系统基本概念_哔哩哔哩_bilibili 思维导图 思维导图为整理王道教材计组第3章 存储系统操作系统第3章内存管理操作系统第5.3章磁盘和固态硬盘如果看不清的话可以点赞博文【哎不点赞也行】试试存到本地然后放大~博文后面会以大纲的形式复述一遍面向复习不会写得很详细且可能有误如果想仔细了解知识点或许可以考虑以下两种方式~ 王道咸鱼老师的视频3.1_存储系统基本概念_哔哩哔哩_bilibili较为重要的内容有从网络找相关配图并给出原文链接点击配图的链接可以传送到各位大佬博文也很适合快速复习~计算题目部分未标注来源的图是我自己画的一张图1h在琢磨但很难保证正确性欢迎小伙伴拍砖~ 目录
前言
思维导图
目录
存储器概述
分类
性能指标
多级存储结构
高速缓冲存储器
技术原理程序访问的局部性
Cache
快表【TLB】
映射方式
写策略
替换算法
主存储器
硬件【计组】
存储结构
访问过程
芯片引脚
多模块存储器
容量扩展
计算小备注
软件【系统】
内存管理的功能
进程运行的基本原理
逻辑地址与物理地址
进程的内存映像【32位】
内存保护
内存共享
内存的分配与回收
虚拟存储器
基本概念
工作流程
请求分页存储管理
页框分配
页面置换算法
抖动和工作集
内存映射文件
外部存储器
磁盘存储器
固态硬盘【SSD】
计算题目
cache
主存
地址码【16年】【20年】
CPU平均每秒访存次数【12年】
主存带宽【12年】
访存时间【13年】
辅存
结语 存储器概述 分类 作用层次 高速缓冲存储器Cache主存储器内存辅助存储器外存 存取方式 随机存储器RAM 数据存取支持随机存取易失性存储器断电后存储信息消失信息读取后完整性 动态随机存储器DRAM存储元为栅极电容信息读出时原存储信息被破坏因此读出后需要以行为单位再生信息【例主存】静态随机存储器SRAM存储元为双稳态触发器信息读出时原存储信息不被破坏【例Cache】只读存储器ROM 数据存取随机读取早期不支持随机写入目前可采用电擦除方式【例EPROM、Flash存储器、固态硬盘SSD】也可反复重写但写入速度很慢非易失性存储器断电内容保留【例BIOS的引导程序】备注操作系统的引导程序在硬盘【ROM】防止掉电后丢失计算机启动后被引导至主存【RAM】使其可以与CPU交互串行访问存储器 顺序存取存储器SAM仅按某种顺序存取不支持随机读写【例磁带】直接存取存储器DAM介于顺序存取与随机存取类似于索引存取【例磁盘、光盘】 性能指标 存储容量 存储字数 x 存储字长存储字数表示存储器的地址空间大小字长表示一次存取操作的数据量单位成本总成本 / 总容量存储速度数据的宽度 / 存储周期 多级存储结构 Cache-主存层CPUCache【单位字或字节】CPU主存【单位字或字节】Cache主存【单位块可能为行、页、段等】主存-辅存层主存辅存【单位块可能为行、页、段等】 图源计算机组成原理存储器的层次结构_存储器层级结构的原理-CSDN博客 高速缓冲存储器 技术原理程序访问的局部性 时间局部性一旦一条指令被执行了则在不久的将来它可能再次被执行【例循环指令】空间局部性一旦一个存储单元被访问那么它附近的存储单元也很快被访问【例顺序指令、数组】 数组行优先存储【a[0][0]a[0][1]...】具备空间局部性数组列优先存储【a[0][0]a[1][0]...】不具备空间局部性 Cache 映射方式预测CPU在未来一段时间内欲访问的数据按照映射关系将存储器的数据块装入Cache的指定位置写策略若访存地址可命中Cache则转为Cache地址在Cache内读写数据若需修改Cache块数据则需要写策略更改对应的主存内容替换算法若访存地址未命中Cache则访问主存并将字块调入Cache此时若主存已满需要执行Cache块替换策略 图源Cache与主存之间的全相联映射直接映射和组相联映射的区别 快表【TLB】 描述根据局部性原理将部分页表存放在高速缓存器组成的快表TLB中映射方式全相联映射或组相联映射不支持直接映射数据结构 有效位/装入位标记 全相联映射时 标记虚页号组相联映射时 虚页号的高位部分为标记虚页号的低位为TLB组的组索引 图源内存管理 —— 快表TLB_快表和慢表-CSDN博客 映射方式 全相联映射 简介主存中的每一块只能装入Cache中的唯一位置特点非常灵活实现复杂标记速度慢冲突率低空间利用率高地址标记块内地址直接映射 简介主存中的每一块只能装入Cache中的任意位置特点实现简单不够灵活冲突率高空间利用率低映射关系Cache 行号 主存块数 mod Cache总行数地址标记Cache块号块内地址 标记 标记 主存块号 - Cache行号 log(主存行数 / Cache行数) 例如主存容量是Cache容量的4096倍则标志位为log 4096 12bit标记 地址码长度 - Cache行号 - 块内地址地址码长度由存储字长【或机器字长】、或主存容量决定Cache行号Cache行数决定例如容量16KB、每行16B的Cache其行数为16KB/16B 1K需要log 1K10位行号块内地址每行Cache包含的数据字段数字长决定 例1Cache行为16B按字节编址【寻址大小为1B】需要log 16 4位块内地址号例2Cache行为8个字每个字32位则行为8 x (32/8)B 32B按字节编址需要log 32 4位块内地址号组相联映射 简介主存中的每一块只能装入Cache中的固定组的任意一行即组间直接映射组内全相联映射特点选定适当的每组Cache行数量可以使成本接近直接映射性能接近全相联映射映射关系Cache 组号 主存块数 mod Cache组数地址标记Cache组号块内地址 标记 地址码长度 - Cache组号 - 块内地址地址码长度由存储字长【或机器字长】、或主存容量决定Cache组号Cache组数决定例如容量128KB、每行16B的Cache采用8位组相联其行数为128KB/16B 8K其组数为8K/8 1K需要log 1K10位组号块内地址每行Cache包含的数据字段数字长决定 图源计算机组成原理cache的三种映像_组相联cache_李昕羽的博客-CSDN博客 写策略 Cache写命中 全写法 同时把数据写入Cache和主存可保证数据的准确性但增加了访存次数在Cache和主存之间增加写缓冲CPU将数据写入Cache和写缓冲写缓冲将内容写入主存但频繁写时写缓冲会饱和溢出回写法 只需要把数据写入Cache只有Cache块被换出时才协会储存Cache行需要增加脏位减少了访存次数但存在数据不一致的隐患Cache写不命中 写分配法 加载主存的块到Cache中更新这个Cache块非写分配法 只写入主存不进行调块搭配 全写法非写分配法【例Cache块调换】回写法写分配法【例Cache块调换、页面调换】 图源计组之存储系统8、Cache写策略-CSDN博客 替换算法 随机算法【RAND】 算法随便选一个Cache块替换特点实现简单过于随意命中率较低先进先出算法【FIFO】 算法优先淘汰最早进入内存的页面特点实现简单具有抖动现象具体表述为所分配的物理块数增大而页故障数不减反增的现象最近最少使用算法【LRU】 算法设置访问字段记录页面被上次被访问的时间优先淘汰最长时间未访问过的页面特点性能较好不具有抖动现象但需要寄存器和栈的硬件支持最不常使用算法【LFU】 算法设置访问字段记录页面访问次数优先淘汰访问次数最少的存储行特点性能接近LRU算法但实际效果不如LRU因为计数器可能会是一个很大的数 图源计组之存储系统Cache替换算法 主存储器 硬件【计组】 存储结构 存储体存储矩阵存储单元的集合通过行选择线、列选择线选择访问单元。存储体的相同行、列上的位同时被读出或写入地址译码器将地址转换为译码输出线上的高电平以便驱动相应的读写线路I/O控制电路控制被选中的单元【控制电路片选线CS】的读出或写入【控制电路读写线WE】具有放大信息的作用以保证输出电信号稳定可靠【驱动器】片选控制信号在多个芯片中“选中”该存储字所在的芯片读/写控制信号根据CPU给出的读命令或写命令控制被选中的单元进行读写 图源主储存器的基本组成 - weblog 访问过程 CPU→数据→MDR【数据寄存器】数据线的宽度与MDR的宽度相同CPU→地址→MAR【地址寄存器】地址线的宽度与MAR的宽度相同决定了主存地址空间的最大可寻址范围CPU→读写信号→控制电路 芯片引脚 引脚最小数目 数据线 地址线 控制线数据线根据芯片的存储单元位数决定地址线根据芯片的存储单元数量决定 若未采用地址复用技术1024个存储单元行32个 x 列32个需要地址线5行地址线5列地址线 10根若已采用地址复用技术1024个存储单元行32个 x 列32个需要地址线10/2行、列地址线复用 5根控制线 若未采用地址复用技术控制线 片选线1根 读写控制线1【读写复用】或2根【读写独立】若已采用地址复用技术控制线 行、列通选线2根 读写控制线1或2根片选线的功能由通选线代替备注DRAM默认采用地址引脚复用技术以减少引脚数量 多模块存储器 单体多字存储器只有一个存储体一次并行读出m个字地址必须顺序排列在同一存储单元多体并行存储器 高位交叉编址方式模块内的地址是连续的存取方式为串行存取读取时间 访存次数 x 存储周期低位交叉编址方式模块号单元地址%模块数模块流水线存取读取时间 存储周期访存次数-1x总线传输周期充分流动时读取时间访存次数x总线传输周期 图源计算机组成原理 容量扩展 位扩展法 功能数据线数与存储芯片位数不相等时使用多个存储芯片扩充字长使 CPU数据线数 存储芯片数据位数地址采用8片8Kx1位的RAM芯片组成8Kx8位的存储器此时字长8 1【每片1位】x8【8个芯片】连线数据总线D0-D7【字长 8】、读写信号【读写复用1根独立2根】、地址总线A0-A12、片选信号【连接所有芯片】字扩展法 功能增加存储器中字的数量而位数不变增加片选信号并联地址线、数据线、读写控制线地址采用4片16Kx8位的RAM芯片组成64Kx8位的存储器此时总地址长度162【片选地址为log 42】14【片内字选地址为log 16K14】连线数据总线D0-D7【字长 8】、读写信号【读写复用1根独立2根】、地址总线A0-A13、片选信号A14-A15【log 42】、片选使能【控制选片开关】字位扩展法 功能既增加存储字的数量又增加存储字长举例采用8片16Kx4位的RAM芯片组成64Kx8位的存储器每组2片【字4位→8位】需要4组【位16K→64K】总地址长度162【片选】14【字选】连线数据总线D0-D7【字长 8】、读写信号【读写复用1根独立2根】、地址总线A0-A13、片选信号A14-A15【log 42】、片选使能【控制选片开关】 图源计算机的存储系统全方面、最详细_sam dam dam-CSDN博客 计算小备注 内存的芯片数量 内存位内存区间000~400H【H是16进制】这种表示内存的位16进制转2进制就是4x16^2 2^10 1K内存字按字编址-32bit【假设为32位系统】按半字编址-16bit【假设为32位系统】按字节编址-8bit内存容量内存字 x 内存位1K【单元数量】x 32bit【单元长度假设为按字编址】4KB内存的芯片地址 芯片地址片选地址片内地址对于固定芯片片选地址固定片内地址从全0~全1浮动例4个 64x8bit的芯片组成 256x8bit的存储器每个芯片的片内地址数量为log 64 4第2个芯片的片选地址为01则地址范围 01 0000 ~ 01 1111或10H~1FH 软件【系统】 内存管理的功能 内存空间的分配与回收存储器空间的分配与管理地址转换多道程序环境下程序中的逻辑地址与内存的物理地址不一致需将逻辑地址转化为物理地址内存空间的扩充利用虚拟存储技术或自动覆盖技术从逻辑上扩充内存内存共享允许多个进程访问内存的同一部分存储保护保证各道作业在各自的存储空间内运行互不干扰 进程运行的基本原理 程序的链接与装入 编译由编译程序将用户源代码编译成若干目标模块链接将编译后的一组模块及他们所需的库函数链接在一起形成装入模块【形成逻辑地址】装入由装入程序将装入模块装入内存运行【形成物理地址】 图源文件在高级操作系统环境正确装载执行_baiiu的博客-CSDN博客 链接的三种方式 静态链接将个目标模块及他们所需的库函数链接成一个完整的装配模块以后不再拆开装入时动态链接源程序编译后形成的一组目标模块在装入内存时采用边装入边链接的方式运行时动态链接对于目标模块的链接程序执行中需要该目标模块才进行 装入的三种方式 绝对装入 只适合单道程序环境程序驻留在内存的某个固定位置编译程序将产生绝对地址的目标代码静态重定位 在多道程序环境下作业一旦装入内存必须给它分配要求的全部内存空间整个运行期间不能在内存中移动地址经过一次变换将装入模块中的相对地址转换为绝对地址动态重定位 在多道程序环境下作业装入内存后地址转换推迟到程序要执行时才进行装入内存后的所有地址均为相对地址需要重定位寄存器的支持分页存储管理、段式存储管理装入时都使用动态重定位转换地址 逻辑地址与物理地址 逻辑地址 编译后每个目标模块都从0号单元开始编址这成为该目标模块的相对地址或逻辑地址对于32位系统逻辑地址空间的范围为物理地址 内存中物理单元的集合是地址转换的最终地址操作系统通过内存管理部件MMU将进程使用的逻辑地址转换为物理地址 进程的内存映像【32位】 0x0000 0000 ~ 0x0804 7FFF 未使用区0x0804 8000 ~ 0x3FFF FFFF 只读代码段可存放程序指令等读/写数据段可存放全局变量、静态变量static等堆【从低位到高位生长】可存放 C#malloc 或Cnew的变量0x4000 0000 ~ 0xBFFF FFFF 共享库的存储映射区可存放 #includestdio.h这样的函数库代码用户栈【从高位到低位生长】可存放局部变量0xC000 0000 ~ 0xFFFF FFFF 操作系统内核区操作系统可访问用户不可访问【PSW区分用户/内核态】 图源谈谈物理内存与虚拟内存之间的映射(超详细~) - 知乎 内存保护 目的确保每个进程都有一个单独的内存空间且用户进程与操作系统不会相互影响措施 在CPU设置一对上、下限寄存器地址号与两个寄存器的值相比判断有无越界采用重定位寄存器【物理地址最小值】和界地址寄存器【逻辑地址最大值】比较逻辑地址与界地址寄存器若未越界加上重定位寄存器的值形成物理地址 内存共享 并不是所有的进程内存空间都适合共享只有那些只读的区域才可以共享可重入代码允许多个进程同时访问但不允许被任何进程修改的代码 内存的分配与回收 连续分配 单一连续分配 描述在用户区内存中仅有一道用户程序即整个内存的用户空间由该程序独占特点 简单无外部碎片只能用于单用户、单任务的操作系统中存储器的利用率极低【内部碎片】优化当时计算机物理内存较小存储空间有限因此将进程活跃的部分放入固定区、可交替访问的部分放入覆盖区【覆盖技术】 固定分区分配 描述最简单的多道程序存储管理方式将用户内存空间划分为若干固定大小的区域每个分区只装入一道作业划分分区的方式 分区大小相等缺乏灵活性适合于一台计算机控制多个相同对象的场合分区大小不等划分为多个较小的分区、适量的中等分区和少量大分区管理分区使用表按分区大小排队各个表想包括每个分区的起始地址、大小及状态是否已分配特点 简单无外部碎片可能因为程序太大而放不进任何一个空间需要采用覆盖技术可能因为程序太小浪费内存空间【内部碎片】 动态分区分配 描述进程装入内存时根据进程的需要动态地为之分配内存特点随着时间推移内存中会产生越来越多小的内存块【外部碎片】可通过紧凑技术解决但需动态重定位寄存器的支持且费时分区分配策略 首次适应算法空闲分区以地址递增的次序链接【最简单最优秀】邻近适应算法分配内存时从上次查找结束的位置开始查找最佳适应算法空闲分区按容量递增的次序形成空闲分区链找到能满足的最小空间分配给作业实际易产生外部碎片最坏适应算法空闲分区以容量递减的次序链接 非连续分配 基本分页存储管理 描述把内存划分为大小相等且固定的块作为主存【页、页面】与进程【页框、页帧】的基本单位【分页在装作业时确定】特性固定分区技术不会产生外部碎片不完整的块申请一个主存块会浪费空间【内部碎片】地址结构 单级页表逻辑地址逻辑页号页内偏移量两级页表逻辑地址一级页号二级页号页内偏移量物理地址物理页号页内偏移量地址转换机构 逻辑→物理地址内存中的页表页表数据结构页号【隐含】块号备注进程的第一级页表常驻内存页表寄存器PTR存放页表的起始地址F、页表长度M【来源于本进程PCB】地址转换过程 (1) 逻辑页号P逻辑地址A/页面大小L页内偏移量W逻辑地址A%页面大小L(2) 将页号送入快表TLB若命中快表则直接取出物理块号b跳到(5)否则访问主存进行(3)(4)(5)(3) 比较逻辑页号P和页表长度M若P≥M则产生越界中断否则继续执行(4) 页表项地址页表始址F 页号Px页表项长度取出物理块号b(5) 物理地址E物理块号bx页表大小L页内偏移量W访存次数 单级页表访问页表1次【未命中TLB】访问目标单元1次【未命中Cache】默认访问2次两级页表访问页表1次【未命中TLB】访问二级页表1次【未命中TLB】访存内存单元1次【未命中Cache】默认访问3次备注若采用全写法则可能在写回数据时 访存次数1 图源基本分页存储管理方式 - 快懂百科 基本分段请求管理 描述按照用户进程中的自然段划分空间例如主程序段、子程序段、栈段、数据段作为主存与进程的基本单位【段长在编程时确定】特性 管理复杂内存利用率低段长不固定【外部碎片】方便编程、信息保护和共享动态增长及动态链接地址结构 逻辑地址逻辑段号段内偏移量物理地址物理始址段内偏移量地址转换机构 段表数据结构段号【隐含】段长本段在主存中的地址控制寄存器存放段表的起始地址F、段表长度M地址转换过程 与页的地址转换过程类似段的共享 段的共享两个作业的段表中相应表项指向被共享段的同一个物理副本共享要求 不能修改的代码称为纯代码或可重入代码不属于临界资源可以共享可修改的代码和数据不能共享段的保护 存取控制保护地址越界保护 段号 段表长度越界中断【猜测可能访问不到目标进程】段内偏移 段长越界中断【猜测可能访问不到目标段】访存次数访问段表1次【未命中TLB】访问目标单元1次【未命中Cache】 图源基本分段存储管理方式 - 快懂百科 段页式管理 描述每个进程一张段表每个段一张页表页作为主存与进程的基本单位特性 分段方法分配和管理用户地址空间分页方法管理物理存储空间【内部碎片】地址结构 逻辑地址逻辑段号逻辑页号段内偏移量物理地址物理始址段内偏移量地址转换机构 段表数据结构段号页表长度页表始址页表数据结构页块页号控制寄存器段表始址、段表长度访存次数访问段表1次【未命中TLB】访问页表1次【未命中TLB】访问目标单元1次【未命中Cache】默认访问3次 图源一文读懂存储管理之页式、段式、段页式存储及优缺点 - 知乎 虚拟存储器 基本概念 特征 传统内存 一次性作业必须一次性全部装入内存后才能开始运行驻留性作业被装入内存后就一直驻留在内存中其任何部分都不会被换出虚拟内存 多次性无须在作业运行时一次性地全部装入内存而允许被分成多次调入内存对换性无须在作业运行时一直常驻内存进程运行期间可以从内存调至外存的对换区换出虚拟性逻辑上扩充内存的容量【虚拟地址的容量】用户看到的内存容量远大于实际容量 图源虚拟内存的原理是什么 - 知乎 组成主存与辅存共同构成了虚拟存储器二者在硬件和系统软件的共同管理下工作编址虚拟存储器将主存或辅存的地址空间统一编址 虚地址用户变成允许涉及的地址实地址主存地址空间关系实际通常 虚地址空间 实地址空间但理论上 小于或等于也是允许的 条件 硬件支持 一定容量的内存和外存页表机制或段表机制作为主要的数据结构中断机构当用户要访问的部分尚未调入内存时则产生中断地址变换机构实现逻辑地址到物理地址的变换系统支持 请求调页页面置换功能 实现 请求分页存储管理请求分段存储管理请求段页式存储管理 工作流程 辅助硬件找出虚地址与实地址之间的对应关系判断虚地址对应的存储单元是否已装入主存 若已在主存通过地址变换CPU可直接访问快表或主存指示的实际单元若不在主存则把包含字的一页或一段调入主存后再有CPU访问若主存已满则采用替换算法置换主存中的交换块即页面 请求分页存储管理 描述 请求分页系统建立在基本分页系统基础之上增加了请求调页功能和页面置换功能 请求页表项 页表机制 与基本分页相同 页号【隐含】物理页框号虚拟页面存放的物理页框位置比基本分页新增 有效位 | 状态位 | 合法位指示该页是否已调入内存【程序访问参考】引用位 | 访问字段用于记录本页在一段时间内被访问的次数【置换算法参考】脏位 | 修改位标识该页调入内存后是否修改过【置换算法参考】保护位 | 权限位该页面的读、写权限【程序访问参考】外存地址 该页在外存的地址通常是物理块号【调入页面参考】 缺页中断机构 与一般中断的相似 保护CPU环境分析中断原理转入缺页中断处理程序恢复CPU环境与一般中断的区别 在指令执行期间【而非指令执行完后】产生中断和处理信号属于内部异常一条指令在执行期间可能产生多次缺页中断 地址变换机构 与基本分页相同 优先检索快表未命中时访问内存页表访问内存页表并将该页调入快表形成物理地址与基本分页不同 内存无目标页表进行缺页中断处理若内存已满则使用置换算法调换目标页修改快表的访问位与修改位【写指令】 页框分配 驻留集 描述操作系统给特定的进程分配的物理页框集合考虑因素 程序本身的缺页率内存驻留的进程数量 内存分配策略 固定分配局部置换 固定进程运行期间的物理块数目不变可采用以下算法 平均分配算法按比例分配算法优先权分配算法局部如果缺页从分配给该进程在内存的页面中选一页换出特点难以确定为每个进程分配的物理块数目 可变分配全局置换 可变进程运行期间的物理块数目根据情况适当地增加或减少全局如果缺页系统从空闲物理队列中取出一块分配给该进程特点如果盲目给进程增加物理块可能导致多道程序的并发性下降 可变分配局部置换 局部如果缺页从分配给该进程在内存的页面中选一页换出可变进程运行期间的物理块数目根据情况适当地增加或减少特点保证进程不会过多地调页的同时也保持了系统的多道程序并发能力 调入页面的时机 预调页策略预测不久之后便会被访问的页面优先调入内存但成功率仅50%请求调页策略进程在运行中需要访问的页面不再内存便提出请求由系统将所需的页面调入内存 从何处调入页面 外存划分 对换区存放对换页面的采用连续分配方式磁盘I/O速度比文件区高文件区采用离散分配方式缺页调入内存 系统拥有足够的对换区空间 进程运行前将与进程有关的文件从文件区复制到对换区进程运行时全部从对换区调入所需页面系统缺少足够的对换区空间 不会被修改的文件都直接从文件区调入可能被修改的部分在将它们换出时须调到对换区UNIX方式 与进程有关的文件都放在文件区未运行的页面都从文件区调入曾经运行过但又被换出的页面放在对换区下次从对换区调入 如何调入页面所访问的页面不再内存便向CPU发出缺页中断中断响应后转入缺页中断处理程序 计组系统01中断_梅头脑_的博客-CSDN博客 页面置换算法 最佳置换算法【OPT】 算法已知访问队列淘汰最长时间内不再访问的页面特点理想算法然而实际访问列队不可知因此不能实现但是可以作为标杆评价其他算法先进先出算法【FIFO】 算法优先淘汰最早进入内存的页面特点实现简单具有抖动现象具体表述为所分配的物理块数增大而页故障数不减反增的现象最近最少使用算法【LRU】 算法设置访问字段记录页面被上次被访问的时间优先淘汰最长时间未访问过的页面特点性能较好不具有抖动现象但需要寄存器和栈的硬件支持时钟置换算法【CLOCK】 简单CLOCK算法 所有页面在逻辑上视为循环队列被替换或被访问时访问位置为1指针指向被替换页面的下一页1若需替换页面指针循环扫描若指向的页面访问位为0将该页换出2指针此时指向的页面访问位为1暂时置为0本轮不替换指针指向下一页3检查到最列最后1个页面若其访问位还是为1则指针回到队首循环检查改进CLOCK算法 在简单CLOCK算法的基础上增加修改位1从指针当前位置开始扫描寻找A0【未访问】M0【未修改】的页面此轮不改变访问位A2若前一步失败进行第二轮扫描寻找A0【未访问】M1【已修改】的页面此轮将扫描过的页面访问位A置03若前一步失败重复步骤1若有必要重复步骤2特点 操作系统试图使用此算法接近LRU算法的性能并减少硬件开销改进CLOCK算法相比简单CLOCK算法可减少磁盘的IO数但会增加算法开销 图源【操作系统】页面置换算法 | 小猿聊编程-技术编程 抖动和工作集 抖动刚刚换出的页面马上又要换入主存刚刚换入的页面马上又要换出主存工作集某段时间间隔内进程要访问的页面集合一般来说分配给进程的物理块数要大于工作集大小 内存映射文件 与虚拟内存类似 磁盘与内存虚拟地址具有映射关系可以访问被映射的文件与虚拟内存不同 不必执行文件I/O操作也无须对文件内容进行缓存管理适合用来管理大尺寸文件所进行的实际交互是在内存中进行的并且是以标准的内存地址形式来访问的多个进程允许并发地映射同一文件进程可以通过共享内存来通信 图源你似乎来到了没有知识存在的荒原 - 知乎 性能影响因素 页面大小↑单个进程的缺页率↓内存空间利用率↓分配给进程的物理块数↑单个进程的缺页率↓进程并发数↓页面置换算法↑缺页率↓写回磁盘全写法访存效率↓、回写法访存效率↑编写程序的局部化程度↑缺页率↓ 外部存储器 磁盘存储器 原理磁头和磁性记录介质相对运动时通过电磁转换完成读/写操作组成磁盘控制器、磁盘驱动器、盘片寻址 寻址过程找到对应的硬盘【驱动器号】移动磁头臂寻道【磁道号】激活相应磁头【盘面号】旋转盘面【扇区号】磁盘地址码长度驱动器号 磁道号【也称柱面号】 盘面号 扇区号 图源理论磁盘管理与文件系统 - 系统运维 - 亿速云 性能 平均存取时间寻道时间 旋转延迟 传输时间 控制时间【公式详见计算题目 - 外存 - 访存时间】数据传输率磁盘转速r/s x 每条磁道容量B读写操作是串行的磁头每次写1bit注意磁盘存储器是以块【物理块即扇区】为单位读写的 性能提升 减少寻道时间 | 调度算法 先来先服务【FCFS】算法 描述根据进程请求访问磁盘的先后顺序进行调度优点公平不会导致磁臂黏着缺点平均寻道距离大如果大量进程竞争使用磁盘则这种算法在性能上往往接近于随机调度最短寻找时间优先【SSTF】算法 描述与当前磁头所在磁道距离最近的磁道以便使每次的寻找时间最短优点虽然不能保证平均时间最小但能提供比FCFS算法更好的性能缺点“饥饿”现象扫描算法【SCAN】算法 描述在最短寻找时间优先算法的基础上规定了磁头运动的方向优点规避了SSTF在小区域来回移动导致饥饿现象缺点对最近扫描过的区域不公平访问局部性不如FCFS算法和SSTF算法循环扫描算法【C-SCAN算法】 描述在扫描算法的基础上规定磁头单向移动来回服务回返时直接移动至快速起始端而不服务任何程序优点改进了SCAN算法偏向于处理那些接近最里或最外的磁道访问请求的问题LOOK、C-LOOK算法 描述相比SCAN算法磁头只需要移动到最远端的请求即可返回不需要达到磁盘端点备注若无特殊说明默认SCAN算法为LOOK算法C-SCAN算法为C-LOOK算法 减少延迟时间 原因磁盘是连续自转设备磁盘读/写物理块后需要经过短暂的时间处理才能开始读/写下一块影响文件的分配方式【顺序、链式、索引】等程序被分配到的磁盘不同区域也会影响磁盘的旋转时间措施盘面扇区交替编号磁盘片的不同盘组错位命名 管理 磁盘初始化 | 装机过程 初始化 物理格式化划分扇区【物理块】扇区的数据结构头部数据区域尾部 头部和尾部包含了一些磁盘控制器的使用信息例如扇区校验码、磁盘的链接指针等扇区的大小通常为512B坏块管理划分一些备用块检测损坏块区时使用备用块代替分区 MBR【主引导记录】磁盘引导程序分区表【起始扇区与分区大小】分区将磁盘分为一个或多个柱面组成的分区【例C盘、D盘】 备注1存放操作系统的分区称为主分区具有引导程序备注2不同的分区可以是独立的文件系统一般均含有根目录、空闲空间管理模块等UNIX可能含有索引节点表逻辑格式化 创建文件系统操作系统将初始的文件系统数据结构存储到磁盘上并为空间创建目录【空闲空间管理、根目录等】逻辑块 为了提高效率操作系统将多个相邻的扇区【物理块】组合在一起形成一簇【逻辑块】文件占用的空间只能是簇的整数倍簇号到物理地址的映射由厂家提供的驱动程序完成操作系统的安装 备注操作系统安装之前磁盘的逻辑格式化可能由引导加载程序或其它初始化程序暂时创建与维护操作系统安装后将接管文件管理的职责 系统初始化 | 开机过程 自举程序 功能初始化CPU、寄存器、设备控制器和内存等接着启动从操作系统存储ROM保留很小的自举装入程序完整功能的引导程序保存在磁盘的启动块上具有启动分区的磁盘成为启动磁盘或系统磁盘【例C盘】简化步骤 激活CPUCPU加电CSIP指向FFFF0H【主存ROM区】加载BIOS【引导程序】执行JUMP指令跳转到BIOS【引导程序或自举程序】硬件自检检查硬件是否出现故障并登记BIOS中断程序入口地址识别已连接的外设加载MBR【主引导记录】CPU将磁盘的第一块MBR读入内存执行MBR中的磁盘引导程序磁盘引导程序根据分区表读入启动盘的PBR【引导块】加载PBR【活动引导记录】CPU读入主分区的分区引导块PBR执行根目录下用于引导操作系统的程序加载操作系统CPU从根目录下找到完整的操作系统将内核部分加载到内存中初始化并开机 图源1.5_操作系统引导_哔哩哔哩_bilibili 可靠性 坏块 | 软件管理 简单磁盘坏块会在FAT表上标明因此程序不会使用它们复杂磁盘控制器维护磁盘内的坏块列表低级格式化将一些块保留作为备用阵列 | 硬件管理 描述RAID磁盘冗余阵列将多个物理磁盘组成一个独立的逻辑磁盘相互备份在磁盘损坏时提升系统的可靠性措施镜像、海明码、奇偶校验码等 固态硬盘【SSD】 原理 基于闪存技术【Flash Memory】的存储器使用固态电子存储芯片阵列制成 组成 闪存芯片替代传统旋转盘中的机械驱动器闪存翻译层替代传统旋转盘的磁盘控制器将来自CPU的逻辑块读写请求翻译成对底层物理设备的控制信号 访存 一个闪存由多个块组成每个块由多个页组成数据是以页为单位读写的只有一页所属的块被擦除后才能写这一页 图源5.3_5_固态硬盘SSD_哔哩哔哩_bilibili 性能 平均存取时间传输时间 控制时间【没有移动的机械部件不需要寻道、延迟】随机访问较快但是连续访问相比机械硬盘无优势随机写很慢擦除操作很慢且写入时页中的所有块都必须被复制到一个新的块中反复擦写后闪存块会磨损 磨损均衡技术 动态磨损均衡写入数据时自动选择较新的闪存块静态磨损均衡SSD自动监测并进行数据分配让老的闪存块承担无须写数据的存储任务平常的读写操作在较新的闪存块中进行 计算题目 cache Cache命中率【08年】 命中率 Cache命中次数 /Cache访问次数 主存访问次数 例1sum a[i]假设按行优先访问数组数据若每个Cache块内有8个数据那么每个数据读1次命中率为7/8 87.5%例2a[i] a[i]1假设按行优先访问数组数据若每个Cache块内有8个数据那么每个数据读写各1次命中率为15/16 93.75% 平均访问时间【13年】 CPU同时访问Cache和主存 访问时间 命中率 x Cache访问时间 1-命中率x 主存访问时间CPU未命中Cache再访问主存 访问时间 Cache访问时间 1-命中率x 主存访问时间 【默认】 主存 地址码【16年】【20年】 逻辑地址 逻辑地址 页号页内偏移量 页内地址 2^(页内偏移量位数)页面大小 2^(页内偏移量位数) x 编址单位【默认为字节编址1B】虚拟地址空间数量 2^(页号位数) 2^(页目录号位数页表索引位数)虚拟地址空间大小 2^(逻辑地址位数) x 编址单位【默认为字节编址1B】 每页容纳页表项个数 页面大小(B) / 页表项大小(B)虚拟地址转物理地址的过程【再次备注图是自己一笔一笔画的博主可能理解有误请大佬拍砖~~】 CPU取指令过程 物理地址与虚拟地址的异同 快表与慢表的地址结构划分 物理地址与Cache数据结构 单级虚拟页表 二级虚拟页表一 二级虚拟页表二 物理地址 物理地址 标记Cache 块号或组号块内地址 标记用于比较Cache行号、组号用于定位Cache块块内地址用于确定CPU在本行所取的字主存单元装入Cache的地址 Cache行/组号 块内地址比较器 用途比较物理地址的标记位与Cache表项的标记位标记位相等且有效则Cache命中比较器的位数 标记位数比较器的个数 组相联映射比较器的个数 每组包含的Cache行数全相联映射比较器的个数 Cache行数表示所有行同时比较直接映射比较器的个数 Cache行数表示每次仅比较一行 Cache映射表 每行位数有效位 标记 脏位替换位 数据 有效位1bit1表示有效0表示无效标记位CPU访存对比地址与Cache的标记位若相等且有效位为1则命中Cache与地址码的标记长度相同脏位 | 一致性维护位1bit用于回写法1表示Cache块已修改需要写回主存0表示未修改【详见Cache-写策略】替换位 log Cache块数 bit用于LRU、LFU替换算法统计上次最晚访问时间或已访问次数【详见Cache-替换算法】其中Cache块数为一组Cache的个数如果为组相连则LRU替换算法位数 log 每组Cache块数数据位Cache块的尺寸这个数值题目一般会直接给到或是用2^(块内偏移量)计算总容量bit每行位数 x Cache行数 CPU平均每秒访存次数【12年】 以下知识均与总线有关可参考总线、I/O系统与中断-CSDN博客CPU平均每秒执行的指令数IPS CPU每秒时钟频率Hz/ 每条指令时钟周期CPICPU平均每秒访存次数次 CPU每条指令访存次数次x CPU平均每秒执行的指令数IPS 主存带宽【12年】 满足CPU访存需求【最低】 主存带宽B/s CPU平均每秒访存次数次/sx Cache缺失率%x 页块大小B存储模式理想状态【最高】 低位交叉存储模式【流水线】主存带宽B/s 存储器的工作频率Hz x 存储总线宽度B 存储体数量个/ 存储体的存储周期sx 存储总线宽度B 访存时间【13年】 访存周期 发送地址和读命令周期 存储器准备周期 总线传输周期不支持猝发串行存取访存次数 x 每次的访存周期 访存次数 x 发送地址和读命令周期 存储器准备周期 总线传输周期支持猝发串行存取发首地址和读命令周期 访存次数 x存储器准备周期 总线传输周期支持猝发流水线存取发首地址和读命令周期 存储器准备周期 访存次数-1x 单个存储体准备周期 总线传输周期 发首地址和读命令周期 存储器准备周期 访存次数 x 总线传输周期【一般情况单个存储体准备周期 总线传输周期】 辅存 簇号物理地址【19年】 柱面与磁道磁盘有300个柱面每个柱面有10个磁道表示该磁头并行连接10个磁盘【即在同一个柱面上磁道的数量】每个磁盘的磁道号容量为300文件簇的顺序编号先以扇区递增再以盘面递增【减少寻道】再以磁道号递增呃【0,0,0】→【0,0,1】→【0,1,0】→【0,1,1】→【1,0,0】...柱面号、盘面号、扇区号 柱面号 簇号 / 单个柱面簇容量 簇号/【柱面磁道数 x 扇区数 x 扇区容量 / 簇容量】结果向下取整盘面号 【簇号 - 柱面号 x 单个柱面簇容量】 / 单个盘面簇容量 簇号% 单个柱面簇容量 / 单个盘面簇容量结果向下取整 扇区号 【簇号 - 柱面号 x 单个柱面数据容量 - 盘面号 x 单个盘面的容量】 / 单个扇区簇容量 簇号 % 单个扇区簇容量 地址码长度【22年】 磁盘地址码长度 驱动器号 磁道号 盘面号 扇区号 访存时间【22年】 访存时间 寻道时间 旋转延迟 传输时间 控制时间一般情况 寻道时间 延迟时间 传输时间 控制时间寻道时间若为平均寻道时间通常题目已知若求具体寻道时间则等于 磁头移动速度 x 移动距离旋转延迟平均每次访存磁盘旋转一半延迟时间s 1/2 * 单位时间s / 转速r/s传输时间磁盘旋转一周时磁头划过每个扇区的平均时间传输时间s 磁盘旋转一周的时间s/ 扇区数 1 / 转速r/s/ 扇区数控制时间磁盘控制器的信号传输延迟时间通常题目已知 结语
️博文到此结束写得模糊或者有误之处欢迎小伙伴留言讨论与批评督促博主优化内容~
博文若有帮助欢迎小伙伴动动可爱的小手默默给个赞支持一下博主肝文的动力~
博主可能会佛系更新思维导图在这里
计算机组成原理_梅头脑_的博客-CSDN博客https://blog.csdn.net/weixin_42789937/category_12434026.html?spm1001.2014.3001.5482操作系统_梅头脑_的博客-CSDN博客https://blog.csdn.net/weixin_42789937/category_12434025.html博主也有整理数据结构学习笔记在这里
数据结构_梅头脑_的博客-CSDN博客https://blog.csdn.net/weixin_42789937/category_12262100.html?spm1001.2014.3001.5482https://blog.csdn.net/weixin_42789937/category_12262100.html?spm1001.2014.3001.5482
