二．光盘
CD/CD-ROM/CD-R/CD-RW/DVD/DVD-R/DVD-RW/Blue-Ray 1.CD 与CD-ROM
母盘，用高强度激光烧盘 压盘，台、凹坑
激光打向背面，根据反射强弱读取信息 不同点：CD有检验码 而CD-ROM没有 优点：方便，成本低，便于携带 缺点：无法更新数据，读取较慢
2.CD-R 感光元器件，可写一次 CD-RW 可擦写
3.DVD数字通用盘 相比较CD 1.双面读，反射层在中间 2.半反射，同样写记录数据 3.对波长要求更短，信号更密集 4.蓝光 运用更短的波长，使得刻录更加密集
强调：光盘为螺旋线（光驱旋转，线速度相同）（与磁盘不同） 三．磁带
使用与磁盘相同的存储机制 离线备份，容量大，存取快 使用磁性材料
并行&串行（蛇形排列）
例题：
1. 考虑一个有N个磁道的磁盘，磁道编号由0到N-1，并假定所要求的扇区随机均匀分布 在盘上。
a) 假设磁头当前位于磁道t上，计算越过的磁道数为j的概率。 b) 假设磁头可能出现在任意磁道上，计算越过的磁道数为k的概率。 c) 计算越过的平均磁道数的期望：
其中，i为跨越的磁道数，Pr[x=i]为跨越的磁道数为i的概率。 解：a) 磁头到达每个磁道的几率为1/N
1:若 j-1 2:若t<=j-1或者t>=N-j 则概率为1/N 2. 为一个磁盘系统定义如下参数： TS = 寻道时间，即磁头定位在磁道上的平均时间 r = 磁盘的旋转速度（单位：转/秒） n = 每个扇区的位数 N = 一个磁道的容量（单位：位） TA = 存取一个扇区的时间 请推导TA的表达式。 TA=TS+1/2r+n/rN 3. 考虑一个单片磁盘，它有如下参数：旋转速率是7200rpm，一面上的磁道数是30000，每 道扇区数是600，寻道时间是每越过一百个磁道用时1ms。假定开始时磁道位于磁道0， 收到一个存取随机磁道上随机扇区的请求。 a) 平均寻道时间是多少？ b) 平均旋转延迟是多少？ c) 一个扇区的传送时间是多少？ d) 完成存取请求的总的平均时间是多少？ 解： a) 平均寻道时间是越过一半磁道的时间也就是30000/2*100=150ms=0.15s b) 7200rpm=120rps 所以平均旋转延迟=1/2r=1/240s c) 1/120/600=1/72000s d) T=0.15+1/240+1/72000 4. 已知逻辑记录是相关数据元素的集合，作为概念性的单位，它与信息如何存储和在何处 存储无关；物理记录是由存储设备特性和操作系统定义的存储空间的一个连续区域。假 定在一个磁盘系统中，每个物理记录容纳30个120字节长的逻辑记录。若此磁盘系统 有8面，每面110个磁道，96扇/道，512B/扇。假设不考虑文件头部记录和磁道索引， 并认为记录不能跨越两个扇区，请计算存储300000个逻辑记录需要多大的磁盘空间（用 扇区、磁道、面数来表示）。 解： 每扇512/120=4个逻辑记录 300000/4=75000扇 750000/96=781余24 782/110=7余11 一共需要7面11磁道24扇 5. 假定一个程序重复完成将磁盘上一个4KB的数据块读出，进行相应处理后，写回到磁盘 的另外一个数据区。各数据块内信息在磁盘上连续存放，并随机地位于磁盘的一个磁道 上。磁盘转速为7200rpm，平均寻道时间为10ms，磁盘最大数据传输率为40MBps，没有 其他程序使用磁盘和处理器，并且磁盘读写操作和磁盘数据的处理时间不重叠。若程序 对磁盘数据的处理需要20000个时钟周期，处理器时钟频率为500MHz，则该程序完成一 次数据块“读出-处理-写回”操作所需要的时间为多少？每秒钟可以完成多少次这样 的数据块操作？ 解：7200rpm=120rps 处理：t=1/500/10^6=2*10^-9 所以对磁盘数据的处理需要20000*2*10^-9=4*10^-5s 读出：10+1/240+4/(40*1024) 写入时间与读出相同 计算略去。。。。 6. 假设有一个磁盘，每面有200个磁道，盘面总存储容量为1.6MB，磁盘旋转一周时间为 25ms，每道有4个区，每两个区之间有一个间隙，磁头通过每个间隙需要1.25ms。请问： 从该磁盘上读取数据时的最大数据传输率是多少（单位：字节/秒）？ 解： 1.6MB=1600KB 所以每个磁道8KB 旋转一周需要时间25ms 其中25-1.25*4=20ms来读取数据 所以最大传输速率 8*1000/20ms=4*10^5B/s VI RAID 磁盘冗余阵列 基本思想：单个或者多个I/O处理任务被平均分配给多个盘（以一种较高的速度来处理，降低各个磁盘负担） 数据分布在多个盘上 特性： 1.看上去像是一个盘 2.数据被分配在多个盘上 3.增加冗余信息，得到额外的好处（以空间换时间），多存一些东西来提高可靠性 恢复数据 RAID的七中技术 RAID Level0 将每个磁盘切成大小一样的块，每个磁盘上的同一行看成一个整体（条带）同时工作。 优点：在数据量较大的情况下能够达到更高的传输速度与响应速率。 缺点：1.面临更大的出错风险。（没有提供任何规避风险的措施） 2.一块地方挂，全部挂。 RAID Level1 （镜像） 组成方式与RAID 0相似 相比RAID 0 RAID1增加完全一样的镜像储存部分，这样就有一个完全一样的备份。 好处：1.提高安全性，非常可靠。 2.若出错，处理过程非常简单。 坏处：1.严重浪费空间，冗余特别大。 2.有一个盘特别慢，带动整个系统变慢。（木桶效应，无法发挥所有硬盘的最高效率） RAID Level2 （并发） 使用海明码校验（2^k>=m+k+1) 条带被划分得很细小（一个字或者一个字节），处理数据更精细 缺点：同一时刻只能支持一个I/O 随着磁盘稳定性的提高，逐渐被抛弃。 RAID Level 3（并发） 同样采用小的条带。 校验盘更小（使用恒定数量的盘——一个盘） p=b0⊙b1⊙b2⊙b3 所以p⊙p=p⊙b1⊙b2⊙b3⊙b0=0 计算机组织结构 Ⅰ Introduction 总述 结构 architecture 对程序员可见（程序员必须清楚） 包括：指令集、各种数据类型的大小 组织 organization(内部实现) 对程序员透明（程序员没有必要清楚） 包括：控制信号、存储技术 计算机发展史: 第一代 电子管/真空管 ENIAC 十进制 IAS 二进制 存储程序思想 亦叫做冯诺依曼模型 分为 ? Central Arithmetical (CA) 运算器 ? Central Control (CC) 控制器 ? Memory (M) 存储器 ? Input (I) / Output (O) 输入输出 四部分组成 第二代 晶体管 第三代到N代 集成电路 摩尔定律(Moore's law): 在一个芯片上所放的晶体管数目每年翻倍(69年前)/18个月翻倍(69年后) 说明计算机逻辑内存单元制作更加便宜/会变得更小/提高了运算速度/降低了电源和散热要求/ 集成电路的可靠性更高 计算机性能: CPU:速度 Memory:容量/速度 I/O:容量/速度 主要目的是提高CPU速度 CPU的性能: 时钟: 时钟率(Hz):每秒能处理的基本指令 时钟周期(s):1/时钟率 Clock tick? 指令处理 每秒钟执行的百万指令数(MIPS) 每秒百万个浮点操作指令数(MFLOPS) 例题： 1. 在逛商店时，你听到一位顾客问店主，他在商店里能买到的最快的计算机是什么。店主回答说“你正在看的是Macintosh，最快的Mac机以1.2GHz时钟速率运行，如果你想要最快的机器，你应该购买我们的2.4GHz的Intel Pentium 4计算机。”店主的说法对吗？为什么？ 解： 不能依靠时钟频率来衡量一台计算机的性能，更科学的衡量标准是每秒所执行的浮点数计算有多少百万次。 相同的功能在不同的指令集中需要的指令数量是不同的，同一条指令在不同计算机上需要的时钟周 期是不同的。而且，即便在指令相同的情况下，如果采用并行或者流水线等技术，也可以加速程序的执行 2. ENIAC是一个十进制机器，用10个真空管来代表一个寄存器。任何时刻只有一个真空管处于ON状态，表示10个数字中的一个。假定，ENIAC有能力使多个真空管同时处于ON和OFF态，这种表示方法是否合理？为什么？ 不合理，当ENIAC有能力使得多个真空管同时处于ON或者OFF状态，应该采用二进制，可以减 少所需要的真空管数量，而且如果10个真空管中出现了多个处于ON状态，则会无法判断是哪个数字。 3. IBM 360Model 75的指令周期的时间是360Model 30的5倍，而相对性能确提高为原来的50倍。为什么会出现这种现象？ 计算机系统性能衡量的常用标准是每秒进行多少百万次的浮点数运算，虽然IBM 360Model 75的 指令周期是360Model 30的5倍，但它可能采用不同的指令集使得完成相同功能的指令数目减少，或者采用了流水线、并行等技术，使得计算机的性能得到了提高。 4. 时钟以固定频率f（或等价地说，以固定周期时间t）来驱动处理器，这里t=1/f。程序的规模能用程序所包含的机器指令数，或者指令计数IC来衡量。不同的指令会要求不同的时钟周期数来执行。一个重要参数是程序的平均每条指令周期数（average cycles per instruction，CPI）。执行一个给定程序所需的处理器时间能表示成： T=IC×CPI×t 在指令执行期间处理器只是做了部分工作，一部分时间是花费在处理器与存储器之间的字传送上。在后一种情况下，传送时间取决于存储器周期时间，而它会比处理器周期大很多。我们能将上面等式改写成： T=IC×[p+(m×k)]×t 这里，p 是用于译码和执行指令所需的处理器周期数，m 是所需的存储器访问次数，k是存储器周期时间和处理器周期时间之比。 上面等式中5个性能因子(IC,p,m,k,t)受到4个系统属性影响：(1)指令集设计（亦称指令集体系结构）；(2)编译技术（在由高级语言程序产生机器语言程序时编译器如何有效）；(3)处理器实现；(4)Cache和存储器的层次。 请用表格形式说明这4个系统属性对这5个性能因子的影响。 指令集规模小 编译技术好 IC P M K T 变多 变多 变多 变少 变少 变少 处理器快 无影响 无影响 无影响 变大 变小 存储层次多 无 影响 无影响 变多 变小 无影响 无影响 无影响 无影响 无影响 5. 处理器性能的一个普通度量是指令执行的速率，表示为每秒百万条指令（MIPS）。请用时钟速率和CPI来表示MIPS速率。 解：设时钟频率为f，平均每条指令周期数为CPI. 所以平均每条指令所需要的时间为CPI/f 1/(CPI/f)*10^6=f/CPI*10^-6 即每秒指令的百万条指令数 6. 一个测试程序在一个40MHz的处理器上运行，其目标代码有100000条指令，由如下各 类指令及其时钟周期计数混合组成： 请确定这个程序的有效CPI、MIPS速率和执行时间。 CPI=(45000+32000*2+15000*2+8000*2)/(45000+32000+15000+8000) MIPS=f/CPI*10^-6 T=100000/MIPS Ⅱ A Top-Level View of Computer Function and Interconnection 总观计算机功能及内部联系 冯诺依曼模型(the von Neumann machine): 计算机组成: I/O 主存(Main memory) CPU 顺序执行指令 系统总线(System bus) 内存: 数据和指令被存贮在内存中 I/O: 内存中的数据按地址寻找 问题: 主存与CPU之间的传输速度差距越来越大 解决: 包含寄存器(cache)缓冲数据减少对内存访问量 增加每次读取的字节数 和CPU/内存交换数据 问题: 和CPU/内存的速度差距越来越大 解决: 缓冲 新的接口技术 按地址寻找数据 CPU: 顺序执行指令 数据和指令被存贮在内存中 问题: 等待I/O设备时CPU的空闲问题 解决: 中断(Interrupt): 嵌套中断处理(Nested interrupt processing) 总线: 连续中断处理(Sequential interrupt processing) 是一种共用的传输介质 链接两个或更多设备 数据传输类型: 地址线 数据线 控制线 总线类型:专用总线(高效传输/规模成本高) 复用总线(节省空间和成本/复杂的机制) 总线仲裁:总线可被多个设备监听但每次只能由其中一个发出信息 集中式/分布式 a) 假定存取时间是 60ns，刷新时间是 40ns。问：存储周期是多少？假定 1 位 输出，这个 DRAM 所支持的最大数据传输率是多少？ 解： 60+40=100ns V=1*10^9/100*1=10^7bit/s=0.125*10^7B/s=1.25MB/s b) 使用这些芯片构成一个 32 位宽的存储器系统，其产生的数据传输率是多 少？ 解：V’=1.25*32=40MB/s 对海明码的应用 4. 一个 8 位字 00111001，采用海明码生成校验位后存储。假定由存储器读出数据时，计算出的校验位是 1101，那么由存储器读出的数据字是什么？ 00111001 产生的海明码为 C1=D1⊕D2⊕D4⊕D5⊕D7=1 C2=D1⊕D3⊕D4⊕D6⊕D7=1 C3=D2⊕D3⊕D4⊕D8=1 C4=D5⊕D6⊕D7⊕D8=0 0111 与1101异或的结果是1010可知第十位出错 原来的是0011 0 100 1 1 11 第十位出错可知读出的数据字是 00011001 关于寻址单元以及字扩展位扩展 5.已知某机主存容量为 64KB，按字节编址。假定用 1K×4 位的 DRAM 芯片构成该存储器， 请问： a) 需要多少个这样的 DRAM 芯片？ 1B=8bit 所以N=64KB/(1K*4it)=16*8=128个 b) 主存地址共多少位？哪几位用于选片？哪几位用于片内选址？ 按字节选址的话64K=2^6*2^10=2^16B 所以主存地址一共16位 一共有2^7个芯片 所以前七位用于选片，后9位用于片内选址 6. 假定用 8K×8 位的 EPROM 芯片组成 32K×16 位的只读存储器，请问 a) 数据寄存器（用于存放数据）最少应有多少位？ 16位，与每个寻址单元中数据的长度相同 b) 地址寄存器（用于存放地址）最少应有多少位？ 32K=2^15bit 所以最少15位 c) 共需要多少个EPROM芯片 32/8*16/8=8个 Ⅴ External Memory 外部存储器 外存的需求 1.大容量.（不会一直被使用） 2.不易失 外存的种类 包括磁盘、磁带、光盘、USB、SSD 一．磁盘 类型：软盘、硬盘 物理特性： 1.衬底：铝、铝合金、玻璃 使用玻璃的好处：稳定性高，减少读写错误、支持更低的飞行高度，不容易损坏 2.磁头——读写磁盘数据 ·可运动 ·不可运动（需要多个磁头） 3.磁盘 ·可移动 ·不可移动 （读写过程中，磁头做径向运动，磁盘旋转） 4.面 ·双面 ·单面 5. 盘片： 单盘、 多盘 柱面：位于同一圆柱表面上的圈 影响多盘效率的因素： 多盘的情况下，每个盘的磁头只能位于盘面的同一个柱面。 6.磁头机制： 接触式（软盘） 固定悬空高度、 可变悬空高度 磁头通过电磁感应进行读写，为增加数据量，可将圈变窄，相应磁头就得变小，此时电磁感 应变弱，必须降低磁盘高度，即飞行高度） 关于Winchester head 温氏磁盘、磁头封装在一个无污染的密封装置中。和常规磁头相比， 可以更加贴近磁表面，数据密度更大。磁盘不动时，以气垫的形式使磁头轻停在磁盘表面。磁盘旋转时，产生的气压使气垫升高而将磁头与盘面分离。 磁盘的工作机制： ·根据极性记录数据 ·读写时，磁头固定，磁盘旋转 ·写： 正负电流产生不同的脉冲信号传至磁头，表面上产生不同磁性的磁化域，分别代表0、1 ·读：磁场相对磁头运动，在磁头中产生电流，不同的极性产生不同方向的电流 磁盘的数据组织 ·磁道：数据由同心圆组成，每个同心圆即磁道 ·扇区：每个磁道被分隔为多个区域，存储大小一定，一般为512B ·匀角速度：增加外圈数据间的空间，使得相同角度经过的扇区数目相同（浪费空间） ·多带记录数据：把磁盘分为多个带，同一个带中采取相同的划分方式，不同带之间的划分方 式不同 优点：增加存储量 缺点：需要更加复杂的电路。 扇区内的数据组织：GAP间隙：为磁头提供反应时间 ID FILED： 同步信息，判断是否到达新的扇区（格式化就是划分扇区， 给ID Field写入信息） 数据区域（515B）其中1B为同步信息，512存储数据，2B为CPR产生 校验码 数据传输时间的计算 1.寻道时间：移动磁头定位到要访问的磁道所花费的时间 2.旋转等待时间 3.传输时间：T=b/(rN) b为需要存储的数据量，r为转速，N为每个磁道上的数据 4.存取时间=寻道时间+旋转等待时间+传送时间 Ta=Ts+1/2r+b/rN 例：假设一个磁盘的平均寻道时间为4ms，旋转速度为15000 rpm， 每个扇区有512byte每个磁道有500个扇区，如果我们需要读一个文件包含2500个扇区共1.28Mbytes 1.假设是连续的：则文件占据了5个磁道 2.随机分布的 对于情况1: 15000rpm=2500rps 1/2500=4ms 所以t=2+4/2+4+4*(4/2+4)=34ms 对于情况2: 因为是随机的 t=2500*(4+4/2+0.008)=15020ms (1)直接映射Cache的地址格式，(2)全关联映射Cache的地址格式，(3)两路组关联Cache的地址格式。（提示：每个映射方式下，需要将标记、 块内地址等分开表示。） 解： Cache字数：4K=4*2^10=2^12 总共12位地址 块的大小32=2^5 5位字长 行数2^7 用7位表示 主存地址为6位16进制即24位二进制，其中5位表示字长. 一．直接映射： 标记位：19-7=12 行数: 7 块内地址：5 二．全关联映射 标记为 19 块内地址 5 三．两路组关联映射 组数 2^6 6位表示组数 标记为 19-6=13 块内地址 5位 以BBBBBB为例 化为二进制位1011 1011 1011 1011 1011 1011 直接映射 101110111011 1011101 11011 BBB 5D 1B 全关联映射 101 1101 1101 1101 1101 11011 5DDDD 1B 两路组关联映射 1 0111 0111 0111 01 1101 11011 1777 1D 1B 对命中的判断以及LRU算法的应用 2. 计算机系统包含容量为32K×16位的主存，按字编址，每字16位。Cache采用4路组关 联的映射方式，数据区大小为4K字，主存块大小为64字。假设Cache初始时是空的， 处理器顺序地从存储单元（每个存储单元中包含1个字）0,1,…,4351中取数，然后再 重复这一顺序9次，并且Cache的速度是主存的10倍，同时假设块替换用LRU算法。 请说明使用Cache后的改进。 主存共32K=2^15个字，每块2^6=64个字，所以一共2^9块. Cache 共2^12 字 所以一共 2^6=64 行 采用4路组关联 组数=2^4=16 所以标记位为9-4=5 组： 4 设Cache的速度为t，则主存的速度为10t 采用cache: 第一次： 0 miss 11t 1-63 hit 1t*15 64 miss 11t 64-127 hit 1t*15 4351/64 = 68 所以一共有68次miss. 第二次： 因为第一次中 0 1 2 3 行中的内容被替换成了 64 65 66 67 块. 根据LRU原则 0 1 2 3 换下的是 16 17 18 19 那一路，以此类推、 0123 16171819 32333435 48495051 64656667永远miss 所以综上p= ( 4352*10-68-20*9)/43520 = 99.43% 时间10V/(V+10*（1-0.9943))=9.5倍 LRU算法与FIFO算法的应用与比较 3.假设主存中的5 个块{1,2,3,4,5}映射到cache 的同一组，对于主存块访问地址流 {1,2,3,4,1,2,5,1,2,3,4,5}，在3-路组关联、4-路组关联、5-路组关联方式下，分别 说明LRU算法和FIFO算法的命中情况。 下面只考虑3-路组关联： LRU 算法 1 1 2 1 2 3 最近最少使用的 FIFO 1 1 2 1 2 3 最先进的 1 1 4 2 3 2 4 1 3 3 4 1 2 4 5 1 2 1 5 1 2 1 5 1 2 1 5 3 2 2 5 3 4 5 5 3 4 5 1 4 2 3 2 4 1 3 3 4 1 2 4 5 1 2 1 5 1 2 2 5 1 2 5 3 1 2 1 3 4 2 2 3 4 5 多层次Cache的计算 4：对一个有两级Cache的系统，定义：TC1 = 第一级Cache存取时间；TC2 = 第二级Cache 存取时间；H1 = 第一级Cache命中率；H2 = 组合的第一/二级Cache命中率。请给出读 操作时间的表示。（提示：需要假设主存的存取时间） 解： 设主存存取时间为Tm T=Tc1+(1-H2)Tm+(1-H1)Tc2 5:假设某处理器的时钟频率为1.2GHz，当L1 cache无缺失时的CPI为1（即CPU可以快 速地从L1 cache中读取指令，并在1个时钟周期内完成）。访问一次主存的时间为100ns （包括所有缺失处理），L1 cache的局部缺失率为2%。若增加一个L2 cache，并假定 L2 cache的访问时间为5ns，而且其容量足够大到使全局缺失率仅为0.5%。分析增加 L2 cache后处理器执行程序的效率提高了多少？ 解： 1.2Ghz=1.2*10^9次/s 所以处理一次需要1/1.2 = 0.833nm 未增加L2时平均读取一条指令的时间为 0.833+0.02*100= 2.833nm 增加L2后平均读取一条指令的时间为 0.833+0.005*100+0.02*5=1.433nm 2.833/1.433=1.97倍 Ⅳ Internal Memory 主存 存储位元: 有0/1两个稳定状态 可以至少被写入一次 可以读取状态 RAM(Random Access Memory,随机访问存储器): 特性: 可以简单迅速地读取和写入数据 类型: DRAM(Dynamic RAM,动态随机访问存储器):电容存储 需要刷新 相似: 易失性 都需要提供电能来维持数据 区别: SRAM(Static RAM,静态随机访问存储器):门 易失性(volatile) DRAM设计简单但是需要刷新 SRAM比DRAM更快，但是集成度低造价高 DRAM多用于主存 SRAM多用于寄存器 ROM(Read Only Memory,只读存储器): 特性: 非易失性(Nonvolatile) 可读取但是不可写入数据 应用: 问题: 无出错空间 成本高 微编程 系统程序 函数表 PROM(Programmable ROM,可编程只读存储器): 特性: 非易失性(Nonvolatile) 只能写入一次:电子写入并且需要特殊的环境 与ROM的区别: 更加灵活方便 Read-Mostly Memory: 读的次数比写的次数多很多 类型: 非易失 EPROM(Erasable PROM,可擦除编程只读存储器): 特性:可读写 紫外线擦除整块 比PROM更贵 EEPROM(Electrically EPROM, 可电擦除编程只读存储器): 特性:可写入并且无需擦除数据 可按字节写入（覆盖） 比EPROM擦除速度快但 造价更高 Flash Memory(闪存): 特性:电擦除 可擦除几块 集成度高 寻址单元(Addressing Unit): 包含同样类型的几个位元 寻址模式:字(Byte) 更加常见/字节(Word) 先行后列 停止读写，集中刷新，会有一段时间停止工作：死区 不会出现死区但是时间过长 高效 存储阵列:线的复用 刷新: 集中刷新(Centralized Fresh) 分散刷新(Decentralized Fresh) 异步刷新(Asynchronous Fresh) 芯片的引脚: Address/Data/Vcc(power supply)/Vss(ground pin)/CE(chip enable)/Vpp(program voltage) WE(write enable)/OE(output enable)/RAS(row address select)/CAS(column address select) 模块的扩展:字扩展/位扩展/字位扩展 位扩展：增加数据量。 地址线数量不变，数据线数量增加 例如：使用8个 4K*1的芯片来组成4K*8的芯片 字扩展：增加寻址空间 地址线数目增加 数据线数目不变 例如：使用 4个16K*8bit的芯片组成64K*8bit的主存 内存是字扩展 主存 = RAM + ROM 主存大小 = RAM 大小 其他的DRAM: SDRAM(Synchronous DRAM,同步动态访问存储器):只允许在一个特定时刻传输 DDR SDRAM(Double-data-rate SDRAM,两倍速率SDRAM) Rambus DRAM/Cache DRAM 纠错: 奇偶校验: 奇校验: 校验位=所有位作异或后再与1异或 若1的个数为奇数，则校验码为0, 偶校验: 校验位=所有位异或 若1的个数为偶数，则校验码为0 出错条件：比较C’（新读出的校验码）与C’’（重新计算后得到的校验码）（作异 或），注意，与原先的数据无关。结果为1时，有奇数位出错，为0，没有出错或者偶数位出错。 优点:成本低 缺点:只能知道出错不能找出错误之处 海明码:分K组产生校验码 将一个M字节的数据分成K组，则有K位校验码 2^k>=M+k+1 规则： 1.将两次海明码作异或，若所有位上都是0，则没有 错误 2.若有一位是1，则海明码错误，不需要纠正 3.超过一位是1，根据相应规则可以判断哪一位出错，并纠正。 记8字节数 D=D8D7D6D5D4D3D2D1，它的四位校验码是C=C4C3C2C1 C1=D1⊕D2⊕D4⊕D5⊕D7 C2=D1⊕D3⊕D4⊕D6⊕D7 C3=D2⊕D3⊕D4⊕D7 C4=D5⊕D6⊕D7⊕D8 纠错码 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001 数据位 D8 D7 D6 D5 C4 D4 D3 D2 C3 D1 C2 C1 记八字节的数,海明码为4位. D8D7D6D5C4D4D3D2C3D1C2C1 包括校验码的12位的储存顺序 例1： D=01101010 使用偶校验 C1=D1⊕D2⊕D4⊕D5⊕D7=1 C2=D1⊕D3⊕D4⊕D6⊕D7=1 C3=D2⊕D3⊕D4⊕D8=0 C4=D5⊕D6⊕D7⊕D8=0 所以为011001010011 例2: 若取得时12位为0110 0 101 0 0 11 D’=01101010得到C’=0011 C’’=0011 S=C’’⊕C’=0000 所以没有出错 若取得时12位为0111 0 101 0 0 11 D’=0111 1010 C’=1010 C’‘=0011 S=C’’⊕C’=1001 所以第五位出错 SEC 只能纠错一位 SEC-DEC 增加一位校验码C5=D1⊕D2⊕D3⊕D5⊕D6⊕D8 如果有一位数据发生错误，则有三位的校验码将发生改变 CRC(Cyclic Redundancy Check,循环冗余校验码): 例子说明一切： 数据：100111。生成校验码 1001（x^3+1) 校验码 111 例题分析： 关于各种存储器的比较以及应用 1.说明下面概念间的区别 RAM和 ROM RAM,随机访问存储器，可读可写，但是易失 ROM，只读存储器，只能读不能写，不具有易失性 两者的共同点都是半导体存储器 SRAM和SDRAM SRAM 静态随机访问存储器，相对于动态的DRAM，不需要刷新电路来维持位元的状态 SDRAM是DRAM的一种，需要刷新来维持位元状态，但是相比普通的DRAM，它采用外部时钟与处理器同步，具有更高的数据传输速率 PROM、EPROM、和EEPROM PROM， 可编程只读存储器，非易失，可以一次电写入，但之后无法修改 EPROM 可擦除可编程只读存储器，可以写入多次，但需要通过紫外光擦除整个芯片的信息，时间长，但是造价相对较低集成度高 EEPROM 电子EPROM,可以擦除单个字节，消耗时间相对较短，但是造价贵且集成度低 SDRAM和DDR DDR是一种特殊的SDRAM，也采用外部时钟与处理器同步，但是与SDRAM相比，DDR允许在一个时钟周期内读/写两次数据，可以加快数据传输速率 2.传统的 RAM 组织成每芯片只有一位，而 ROM 通常组织成每芯片多位，请说明原因。 当RAM组织成每芯片只有一位时，所需要的地址线只要一根，这样有利于减少芯片的引脚数 和出错的概率，提高芯片的集成度。 与RAM相比，ROM容量相对较小，集成度要求较低，组成每个芯片多位可以减少芯片数 量，有利于降低成本。 3.假设采用分散式刷新，下图表示一个 DRAM 经由总线的读操作的简化时序，存取时间认为是由t1到t2.由t2到t3是刷新时间，此期间DRAM芯片必须再充电，然后处理器才能再次存取它们。 b2⊙0 = b2⊙p⊙b0⊙b1⊙b2⊙b3 b2=p⊙b0⊙b1⊙b3 无论哪个磁盘坏掉，都可以将它恢复。（但只能判断一个磁盘坏掉的情况） 缺点：同一时刻只能支持一个I/O （在网络服务中不适用） RAID Level 4 数据量更大 允许磁盘独立写。 依然只用一个盘做校验。 当只有一个盘上的数据（假设b2）发生改变时，校验码进行计算： p'=b0⊙b1⊙b2'⊙b3 p =b0⊙b1⊙b2⊙b3 b2⊙p = b0⊙b1⊙b3 p'=b2⊙p⊙b2' 数据盘进行读写时往往需要等待校验盘计算完毕。 当小的块进行改写时，速度要比Level 3慢 校验盘成为Level 4 系统的瓶颈。 RAID Level 5 对于每个条带，每个盘轮流做校验盘。 防止I/O瓶颈的出现。 RAID Level 6 ( 3 4 5 只能处理一个盘出错的情况，或者两个盘出错的间隔时间要小于处理时间） 针对之前 只能判断一个盘出错的缺点 再加一个校验盘Q， 和P分开独立进行计算 可以处理至多三个盘出错的情况 例题： 1. 假定有两个用来存储10TB数据的RAID系统，每个磁盘的大小均为2TB。系统A使用RAID 1技术，系统B使用RAID 5技术。请问： a) 系统A需要比系统B多用多少存储容量？ b) 假定一个应用需要向磁盘写入一块数据，若磁盘读或写一块数据的时间为30ms， 则最坏情况下，在系统A和系统B上写入一块数据分别需要多少时间？ c) 哪个系统更加可靠？为什么？ 解： a) 10/2=5个 若采用RAID 1 需要5*2=10个，若采用RAID 5， 则需要5+1=6个。 所以A比B多用4*2=8TB b) 对于RAID 1 只需要30ms 对于RAID 5 最坏情况 两读两写 120ms C) 更可靠，RAID1对所有的数据进行了备份，其中一份磁盘数据出错，通过另一份就可以很方便的恢复，而B系统中，如果两块磁盘的同一个对应位置同时出错，便无法恢复 2. 假定在一个使用RAID 5的系统中，采用先更新数据块、再更新校验快的信息更新方式。 如果在更新数据块和更新校验块的操作之间突然发生了断电现象，那会出现什么问题？ 是否可以通过更改信息更新方式来避免这一问题的发生？如果可以的话，请说明如何更 改及更改后的方式如何发挥作用。 解：数据块更新了，而校验快没有更新，导致校验快与数据块不匹配，无法通过校验位对其他数据块进行恢复操作。 可以先更新校验块，如果断电了，可以通过已更新的校验块来恢复数据块 VII Virtual Memory 虚拟内存 为了载入更多的程序，计算机必须有更大的内存 1.采用交换技术 分区、分页 2.采用虚拟内存 一．交换技术 1.分区 a) 操作系统：固定的分页大小 b) 用户程序：不同大小的固定分区（一个分区内只能放一个程序） 当加载一个程序时，把它放在所能容纳它的最小的那个分区 缺点：浪费空间 变长分区方式： 操作系统：固定分区大小 用户程序：根据需求分配 缺点：增加碎片，利用率越来越低。 2.分页 一．先将内存划分成等大的块（页框），把程序切成等大的块（页） 二．将页存进页框 三．逻辑地址：在指令中的地址 物理地址：在内存中的地址 二．虚拟内存 问题：内存的大小有限，但是对内存的需求与日俱增 思想：仅仅加载当前需要使用的页（其他不需要使用的页放在硬盘上） 虚拟内存实质上将物理内存与磁盘上的一小块空间组织在一起，形成一个比物理内存本身更大的被 该用户独占的内存。 问题： 1.页的大小（4KB,8KB 注意：Cache速度大概是内存的10背，而内存速度是硬盘的十万倍，所以 块的大小应大点） 2.映射方式：关联映射 3.写的策略：写回（过一段时间统一写，尽量减少同步操作） 类型： 1.页式虚拟内存: 强调物理内存与虚拟内存之间的映射关系 将虚拟内存分成与物理内存大小相同页（虚页或者说是逻辑页) 物理内存中的页：物理页（实页） 页表：记录所有的虚页所对应的位置，是否有效，脏位等等，存在主存中 虚拟地址：虚拟内存的页号以及页内偏移量 快表 将目前可能会用到的页表中的几块记录移动到Cache中 关联映射 组关联映射 随机替代。 段：将不同的程序分成不同的段 段的虚拟地址：段数+偏移量 好处：程序在段中得到保护 段与页的结合 每个段都有一个页表 虚拟地址： 段数+页数+偏移量 有点：程序被共享并且在段中被保护 缺点：虚拟地址变得冗长，需要更多的表查找时间。 例题： 1.虚拟内存的大小是否等于主存的容量加上磁盘的容量？为什么？ 不对，一个系统的虚拟内存由两方面决定。 1.系统寻址空间的大小，如系统的寻址宽度为32位，则能支持的虚拟内存最大为2^32，即4G 2.虚拟内存借助磁盘空间来实现，所以虚拟内存一定小于磁盘大小。 在满足以上两条限制条件的情况下，具体的虚拟内存大小会根据具体设置而定，但磁盘的容量通常 远大于虚拟内存 2.在使用了快表（TLB）和cache的情况下，CPU读写一个数据，需要访问多少次主存？（需 要假设各种情况的概率） 假设快表的命中率为Pt, Cache的命中率为Pc, 虚页载入的命中率为Pv 简单算法：最坏情况2次，1次页表查找，1次是存取数据，如果TLB命中，则不需要页表查找， 如果虚页已加载且Cache命中，则不用访问主存 所以2-Pt-Pv*Pc 3.假设一个分页虚拟存储系统的虚拟地址为40位，物理地址为36位，页大小为16KB，按 字节编址。若页表中的有效位、存储保护位、修改位、使用位共占4位，磁盘地址不在 页表中。则该存储系统中每个程序的页表大小为多少？（说明：1.假设每个程序都能使 用全部的虚拟内存；2.页表项的长度必须为字节的整数倍） 解：16KB=2^14B；共有2^（40-14）=2^26个页表，2^（36-14）=2^22个页 页表项的最小长度22+4=26，根据说明2，页表项的长度必须为字节的整数倍 所以长度取32，所以页表大小为：2^26*4B=256MB 4. 假设一个计算机系统中有一个TLB和一个L1 data cache。该系统按字节编址，虚拟地 址16位，物理地址12位；页大小为128B，TLB为4-路组相连，共有16个页表项；L1 data cache采用直接映射方式，块大小为4B，共16行。在系统运行的某一时刻，TLB、页表 和L1 data cache中的部分内容如下图所示（16进制表示） 请问： (1) 虚拟地址中哪几位表示虚拟页号？哪几位表示页内偏移量？虚拟页号的哪几位表 示TLB标记？哪几位表示TLB组号？ 虚拟地址共16位 页大小为128B，2^16/128=2^9 个虚拟页 所以前9位表示虚拟页号，后7位表示页内偏移量 TLB为4路组共16行。 9-2=7 所以前七位表示TLB标记，后2位表示组号。 (2) 物理地址中哪几位表示物理页号？哪几位表示页内偏移量？在访问cache时，物理 地址如何划分成标记字段、行号字段和块内地址字段？ 物理地址共12位 页大小为128B，所以一共有2^5个物理页 所以前5位表示物理页号，后7位表示页内偏移量 访问Cache时候，物理地址一共12位，按字节寻址，块大小为2^2B ，Cache共2^4行 主存共2^10个块，所以10-4=6位为标记字段，中间4位为行号字段，后2位为块内地址字段。 (3) CPU从地址067AH中取出的值为多少？请对取值过程进行说明。 CPU传出的为虚拟地址，从快表中查找067AH=0000 0110 0111 1010 高9位 0000 0110 0 为虚拟页号 在快表中的组号为00 查找快表中00组，丢失03, 所以快表丢失 查找页表 00C 得出页框号19，即1 1001 页内偏移量为111 1010 与页框号组成物理地址 1100 1111 1010 中间四位为1110即Cache的行号 标记为33 吻合，且有效位为1，块内地址为10=2 所以取出4A Ⅷ Bus 总线 总线是用来连接两个或者多个设备的介质。 每个总线都可以听，同一个时刻只能由一个设备发送信息 类型:芯片内总线/系统总线/通讯总线 按照功能分为三类: 数据总线：数据总线的数量决定了一次性能够传输的数据大小 地址总线：地址总线的数量决定了最大寻址空间 控制总线：传输一些控制信号，包括时钟、总线请求、接收、中断请求、中断允许等 总线类型:专用总线/复用总线 专用总线：优点：更快速高效 缺点：规模花费增加 复用总线：优点：需要更少的线节省空间与花费 缺点：需要更复杂的电路，共用总线降低效率 仲裁: 分布式/集中式 集中式仲裁: 菊花链: 每个设备依次按照优先级连接,由仲裁器发出信号依次询问 优点:简单/方便添加设备 缺点:不能保证公平/对错误敏感/速度限制 计数器: 由仲裁器在总线上叫号询问 优点:公平/对错误不敏感 缺点:增加了线路/需要解码来匹配每个设备ID 独立请求式: 分布式 计时:同步/异步/半同步/分割 同步: 异步: 总线上:地址+数据1+数据2…… 优点:简单 缺点:所有设备需要使用同一个时钟周期 总线上:地址+数据1+数据2…… 握手(handshaking) 每个设备连到总线上发送请求,自我决定(N根线连N个设备,线越少的优先级高) 冲突探测:自动停止数据传输,经过一个随机的时间后再开始工作 每个设备与仲裁器由两根线连接一根请求一根回复 仲裁器决定响应:方法:固定的顺序/LRU/FIFO 优点:响应快/可编程 缺点:复杂控制电路/更多的控制线 半同步:在每次时钟周期的两边都可传输 分割:把一次操作变成两次 例：假设同步总线的时钟周期是50ns并且每次传输需要一个时钟周期，异步总线每次握手需要40ns.两种总线都有32位总线宽度，并且主存的数据准备时间为200ns，计算当从主存中读取一个字（32位）时候的带宽 解：对于同步总线： 给主存发送命令以及地址需要 50ns 主存准备数据200ns 传输数据给CPU：50ns 所以带宽=4B/(50+200+50)ns=13.3MB/s 对于异步总线： 总线带宽:单位时间传输的最大数据量 区别于总线宽度(每次传输几位) 第一次握手：40ns 第2、3、4次握手：max(40ns*3,200ns)=200ns; 第5、6、7次握手: 40ns*3 = 120ns; 带宽：4B/(40+200+120)ns=11.1MB/s 另：假设同步总线的时钟周期为50ns每次传输需要一个周期，异步总线每次握手需要40ns，两种 总线的总线宽度均为32位，数据准备的时间是230ns，计算带宽（传输一个字） 同步总线：4B/(50+250+50)ns=11.4MB/s 异步总线：4B/(40+230+120)ns=10.3MB/s 假设一个系统有以下的特性： 1.支持4到16字的块（每个字32位） 2.同步总线有64位的总线宽度，和200MHz的时钟频率，每次传输一个地址或者64位需要一个 周期 3.在每次总线处理之间有2个闲散的时钟周期 4.前4个字需要200ns，之后减少到20ns每4个字 5.当之前的数据在总线上传输的时候，主存同时读接下来的数据。 如果读256个字，计算带宽，传输时间，以及当一次传输4个字或者一次传输16个字时每秒的总线处理次数。 解：一个时钟周期1/200*10^6=5ns 1.一次传输4个字： 总线处理：地址+4个字的数据 地址传输：1个时钟周期 数据读取：200ns（40个时钟周期） 数据传送：2个时钟周期 闲散时间：2个时钟周期 总共需要 256/(4*(1+40+2+2)=2880个时钟周期 传输时间=2880*5=14400ns 64*1s/14400ns=4.44M次 带宽：256*4B/14400ns=71.11MB/s 2.一次传输16个字 总线操作：地址+16个字 地址传输：1个时钟周期 数据读取：前4个200ns，之后每次读取可以在之后的4个周期内完成 数据传输：2个时钟周期 闲散时间：2个时钟周期 总共需要256/16*(1+40+3*max(4,4)+2+2)=912个时钟周期 增加带宽的方式: 提高时钟率/增加宽度/分开数据地址线 Bus Hierarchy 总线结构 单总线结构：CPU，主存和I/O模块都连接到系统总线上 好处：简单，易扩展 缺点：总线是个瓶颈 双总线结构：1.在CPU与主存之间增加一个主存总线 好处：增加CPU与总线之间的传输效率，减少系统总线的负担 2.将系统总线通过IPO（输入输出处理器）分成主存总线和I/O总线 好处：减少I/O的负担 3.将系统总线通过DMA总线分成主存总线和I/O总线， 好处：增加I/O的效率 多总线结构： 1.增加一个本地总线来连接CPU于Cache 优势：将CPU于I/O交流分离 2.增加一个高速I/O总线来连接一个高速的设备 优势：增加I/O的效率 例题： 1. 假设一个同步总线的时钟频率为50MHz，总线宽度为32位，每个时钟周期传送一个数据， 该总线的带宽为多少？若要将该总线的带宽提高一倍，有哪几种方案？ 不考虑命令以及地址的传输：32bit*50MHz=200MB/s 想要将带宽提高一倍，可以考虑增加总线宽度为64位，或者将始终频率增加一倍 2. 一个32位的微处理器，它有16位的外部数据总线，由40MHz输入时钟驱动。假设一个 总线事务需要的最短时间等于4个输入时钟周期，这个处理器可能维持的最大数据传输 率是多少？如果将它的外部数据总线扩展为32位，那么该总线的最大数据传输率提高 到多少？这种措施与加倍外部处理器总线时钟频率的措施相比，哪种更好？ 解：一个总线事务需要的最短时间为4个输入时钟周期，说明其中3个用来传送其他信息，1个用来传输数据。 假设一个总线事务消耗了n个 时钟周期，那么最大传输率为： (n-3)*16bit/n*40MHz=80(n-3)n MB/s 例如当n=16的时候，就是65MB/s 若将外部数据总线扩展为32位 则最大传输速率变成160（n-3)n MB/s 与加倍外部处理器总线时钟频率效果一样 3. VAX SBI总线采用分布式的自举裁决方案，总线上每个设备有唯一的优先级，而且有一 根独立的总线请求线REQ，SBI有16根这样的请求线（REQ0，…，REQ15），其中REQ0 优先级最高，请问最多可有多少个设备连到这样的总线上？为什么？ 答：一共有16条线，其中一条设置总线忙，另外15条为请求线，则可以连接16个设备 4. 假设某存储器总线采用同步定时方式，时钟频率为50MHz，每个总线事务传输8个字， 每字4字节。对读操作，访问顺序是1个时钟周期接受地址，3个时钟周期等待存储器 读数，8个时钟周期用于传输8个字。对于写操作，访问顺序是一个时钟周期接受地址， 2个时钟周期延迟等待，8个时钟周期用于传输8个字，3个时钟周期恢复和写入纠错码。 对于以下访问模式，求出该存储器读写时在存储总线上的数据传输率。 a) 全部访问为连续的读操作。 b) 全部访问为连续的写操作。 c) 65%的访问为读操作，35%的访问为写操作。 解： a) 在一个总线事务中，一共需要1+3+8=12个时钟周期，所以数据传输率为4B*8/12*50MHz=133.3M/s b) 在一个总线事务中，一共乣1+2+8+3=14个时钟周期，所以需要 4B*8/14*50MHz=114.3MB/S c) 133.3*0.65+114.3*0.35=126.7MB/s 5. 假定在一个字长为32位的计算机系统中，存储器分别连接以下两种同步总线。 总线1是64位数据和地址复用的同步总线，能在1个时钟周期内传输一个64位的数据 或地址。支持最多连续8个字的存储器读操作和存储器写操作总线事务。任何一个读写 操作总是先用1个时钟周期传送地址，然后有2个时钟周期的延迟等待，从第4个时钟 周期开始，存储器准备好数据，总线以每个时钟周期2个字的速度传送，最多传送8个 字。 总线2是分离的32位地址和32位数据的总线。支持最多连续8个字的存储器读操作和 写操作总线事务，读操作的过程为：1个时钟周期传送地址，2个时钟周期延迟等待， 从第4个时钟周期开始，存储器准备好数据，总线以每个时钟周期一个字的速度传输最 多8个字；对于写操作，在第1个时钟周期内第1个数据字和地址一起传输，经过2个 时钟周期的等待延迟后，以每个时钟周期1个字的速度传输，最多传输7个余下的数据 字。 假设这两种总线的时钟频率都是100MHz，请问： a) 两种总线的带宽分别为多少？ b) 连续进行单个字的存储器读操作总线事务，两种总线的数据传输率分别为多少？ c) 连续进行单个字的存储器写操作总线事务，两种总线的数据传输率分别为多少？ d) 每次传输8个字的数据块，其中60%的访问是读操作总线事务，40%的访问是写操 作总线事务，两种总线的数据传输率分别是多少？ A) 非严格计算：总线1：每个时钟周期2个字，最大传输速率为2*32bit*100MHz=800MB/s 总线2:每个时钟周期1个字，400MB/s B)读操作：对于总线1：一次读操作需要1+2+1=4个时钟周期 所以数据传输率为 1*32bit/4*100MHz=100MB/s 对于总线2：也是100MB/s C)写操作：对于总线1，仍然为100MB/s 对于总线2，1*32/3*100MHz=133.3MB/s D) 对于总线1：一次传输8个数据块需要1+2+4=7个时钟周期，读写是一样的， 所以数据传输率为8*32bit/7*100MHz=457.1MB/s 对于总线2：读：1+2+8=11个时钟周期 所以为8*32bit/11*100MHz 写：1+2+7=10个时钟周期 所以为8*32bit/10*100MHz 取下加权平均数.... 6. 假定连接主存和CPU之间的同步总线具有以下特性：支持4字块和16字块（字长32位） 两种长度的块传输，总线时钟频率为200MHz，总线宽度为64位，每个64位数据的传送 需要1个时钟周期，向主存发送一个地址需要1个时钟周期，每个总线事务之间有2个 空闲时钟周期。若访问主存时最初4个字的存取时间为148ns，随后每读4个字的时间 为26ns，则在4字块和16字块两种传输方式下，该总线上传输512个字时的数据传输 率分别为多少？ 解：时钟周期=1/200MHz=5ns 若一个总线事务传输4个字块: 需要1+（150）/5+2+2=35个周期 传输速率为4*32bit/35*200MHz=91.43MB/s 若一个总线事务传输16个字块，需要1+（150）/5+3*max(30/5,2)+2+2=53个周期 传输速率为16*32bit/53*200MHz=241.51MB/s 7. 与单总线相比，使用多总线有什么好处？ 解：多总线结构有利于减少总线冲突和传输延迟，并将不同传输速率的设备分离，提高系统 的传输性能。 IX I/O 输入/输出 问：为什么不直接把外部I/O设备连接到总线 1.设备种类繁多，相应的操作方法繁多 2.很多I/O设备的数据传递很慢，如果连接到总线，会拖慢处理器或者主存的速度。 3.很多I/O设备的数据传递太快，使得主存或者处理器没有办法处理。 4.外部设备可能会使用不同的数据格式，不同的字长。 I/O模块 外部设备 种类： 1.人可读：显示器、打印机 2.机器可读：磁盘、磁带 位于外部设备与总线之间（桥梁作用） 3.用于通讯 同I/O模块的交互途径 控制与计时： 1.CPU与外部设备以一种非预期的方式进行交互。 2.一些资源得到共享。 1.控制信号 2.状态信号 两者连在控制逻辑上。 3.数据交换 缓冲区（8-16位） 例：从外部设备传输数据到处理器 1.处理器讯问I/O模块检查设备状态 2.I/O模块返回设备状态 3.如果准备好了，处理器通过对I/O模块的命令提出传送数据传输的要求 4.I/O模块从外部设备中获取数据 5.数据从I/O模块传送到处理器 I/O模块与处理器之间的通信： 1.解码 2.数据交换 3.状态报告 4.地址识别 I/O模块与外部设备之间的通信： 命令、状态、数据交换 数据缓冲以及检错。。 I/O模块的其他称呼： 百度搜索“yundocx”或“云文档网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，云文档网，提供经典综合文库计算机组织结构 期中复习在线全文阅读。
最新更新：
