串讲1 硬件知识和数据结构串讲(已打)

专题串讲一计算机系统知识和数据结构一、计算机系统知识计算机体系结构和主要部件的基本工作原理•CPU和存储器的组成、性能、基本工作原理CPU主要由运算器和控制器组成。大家要明白运算器和控制器的作用以及工作原理。运算器负责对数据的算术运算和逻辑运算的加工处理。基本结构由算术/逻辑运算单元(ALU)、累加器ACC、寄存器组、多路转换器和数据总线等逻辑部件组成。控制器功能是从内存中取出指令，并指出下一条指令在内存中的位置。将指令经指令寄存器送往指令译码器，经过对指令的分析发出相应的控制和定时信息，控制协调计算机的各个部件的工作，以完成指令所规定的操作。控制器执行指令的过程：1、取指令：从内存中取出一条指令2、 指令译码：将指令的操作码部分送入指令译码器进行分析，然后根据指令的功能向有关部分发出控制命令。3、 按指令操作码执行：实现指令的具体功能。4、形成下一条指令地址CPU功能程序控制(重要职能)：CPU通过执行指令来控制程序的执行顺序。操作控制：产生每条指令的操作信号并将操作信号送往不同的部件，控制相应的部件按指令的功能要求进行操作。时间控制：对各种操作进行时间上的控制。数据处理(根本任务)：对数据进行算术运算及逻辑运算等方式进行加工处理，处理结果由人们直接利用。•I/O接口的功能、类型和特点I/O系统在CPU、存储器和各种外部设备之间负责协调和控制数据的输入/输出。I/O系统控制器基本结构有：数据寄存器、状态寄存器、控制寄存器、控制电路。I/O系统的工作方式有以下几种：微型计算机中最常用的内存与接口编址方式(该知识点要求掌握两种编址方式的原理及其优缺点)内存与接口地址独立的编址方法.内存地址和接口地址是完全独立的两个地址空间，内存用于存放程序和数据，而接口就用于寻址外设。它们是完全独立的并且是相互隔离的。该方式由于二者使用的指令完全不同，因此易于编程，但指令少，功能弱内存与接口地址同一的编制方法内存地址和接口地址统一在一个公共的地址空间里，内存空间里每一个地址都可以分配给接口也可以分配给内存使用。但是，分配给内存的只能用于内存，接口绝不允许使用。同样，分配给接口的地址内存也决不能再用。大大增强了对接口的操作功能，但不易于编程。(2)直接程序控制该知识点的关键在于整个输入输出过程在CPU执行程序的控制下完成，以及两种控制方式的比较：•无条件传送：外设无条件的随时接收CPU发来的输出数据，也无条件的随时向CPU提供需要输入的数据。程序查询方式：由CPU通过执行程序查询外设的状态，判断外设是否准备好接收数据或准备好了向CPU输入的数据。其优点在于容易实现，但降低了CPU的效率，对外部的突发事件无法作出实时响应。（3）中断方式（明白中断控制机制，以及5种中断处理方法原理）中断控制机制：计算机系统通常提供了中断机制，允许某一事件中止CPU正在执行的程序，转去对该事件进行处理，然后再返回原程序被中止处继续执行。其作用是提高CPU的处理效率，使CPU与I/O设备并行工作，还可以实现分时操作过程。中断处理方法：多中断信号线法：每个中断源都有属于自己的一根中断请求信号线向CPU提出中断请求。中断软件查询法：当CPU检测到一个中断请求信号以后，即轮询每个中断源以确定是谁发出中断请求信号。雏菊链法：所有I/O模块共享一根共同的中断请求线。当CPU检测到中断请求信号，则发出中断确认信号。中断确认信号依次在I/O模块间传递，直到发出请求的模块，该模块则把它的ID送往数据线由CPU读取。总线仲裁法：一个I/O设备在发出中断请求之前，必须先获得总线控制权。所以可由总线仲裁机制来裁定谁可以发出中断请求信号。中断向量表法：中断向量表用来保存各个中断源的中断服务程序的入口地址。当外设发出中断请求信号后，由中断控制器确定其中断号，并根据中断号查找中断向量表来取得其中断服务程序的入口地址。中断优先级控制：当不同优先级的多个中断源同时提出中断请求时，CPU应优先响应优先级最高的中断源。当CPU正在对某一个中断源服务时，当比它优先级更高的中断源提出中断请求时，CPU应暂时中断当前的服务，去对优先级更高的中断源服务，服务结束后再回到原先被中断的优先级较低的中断服务程序继续执行。这种情况称为中断嵌套。（4） 直接存储器存取方式（重点）直接存储器存取（DMA）是指数据在内存与I/O设备间直接成块传送，不需要CPU的干预。该知识点的关键在于DMA的工作方式。（5）输入输出处理机重点在于它也不需要CPU的干预，且不影响计算机的整体性能。输入输出处理机适合有较多外设的大型计算机。输入输出处理机是一个专用处理机，主机的输入输出操作都由它来完成。・CISC/RISC,流水线操作，多处理机，并行处理重点：CISC和RISC的比较、流水线技术、多处理的原理、并行处理和并行处理机的原理CISC和RISC的比较:

指令数量众多指令使用频率相差悬殊指令数量众多指令使用频率相差悬殊支持很多种寻址方式变长的指令格式指令可以对存储器中数据直接进行处理指令数量少指令的寻址方式少指令长度固定只提供了Load/Store指令访问存储器以硬布线逻辑控制为主单周期指令执行拥有相当多的寄存器优化的编译器流水线技术：可能会给出一组指令执行过程所需时间，要求计算全部指令完成时间、指令完成周期和流水线处理机的吞吐率和建立时间。多处理的原理：多处理机具有两个或两个以上的处理机，共享输入/输出子系统，在统一的操作系统控制下，通过共享主存或高速通信网络进行通信，协同求解一个大而复杂的问题。多处理机具有共享存储器和分布存储器两种不同的结构。并行处理机的原理：(绝对重点)并行性(parallelism)就是指在同一时刻或同一时间间隔内完成两种或两种以上性质相同或不同的工作，只要时间上相互重叠，就都蕴含了并行性。并行性有两重含义：同时性(simultaneity)：两个或两个以上事件在同一时刻发生并发性(concurrency)：两个或两个以上事件在同一时间间隔内发生提高计算机系统并行性的措施主要有3类。♦时间重叠在并行性概念中导入时间因素，让多个处理过程在时间上错开，轮流重叠的使用同一套硬件设备的各个部件，以加快硬件周转，提高处理速度。♦资源重复在并行性概念中导入空间因素，基于“以数量取胜”的原则，通过重复设置硬件资源来提高系统可靠性或性能。♦资源共享多个用户按一定时间顺序轮流的使用同一套资源，以提高其利用率，从而相应的提高整个系统的性能。并行处理机(也称为阵列处理机)使用按地址访问的RAM,主要用于要求大量高速进行向量或矩阵运算的应用领域。并行处理机的并行性来源于资源重复，它依靠操作级的并行处理来提高系统性能。属于SIMD计算机存储系统•虚拟存储器基本工作原理，多级存储体系虚拟存储器：虚拟存储系统的作用是给程序员一个更大的虚拟的存储空间，其容量可远远超过主存储器的容量，而与辅助存储器容量相当。我们提供给用户的这个存储器，即在软件编程上可以使用的存储器，就称为虚拟存储器。它的容量即虚拟存储空间，简称虚拟空间。面向虚拟存储器的编程地址称为虚拟地址，或称为逻辑地址。与主存和辅助存储器地址相对应。在存储技术中，存在以下制约关系：存储器读写速率越高，每位的成本也较高；存储器容量越大，每位的成本也越低存储器容量越大，读写速率越低。解决这一难点的方法就是采用多级存储体系结构。典型的三级存储体系结构如下图所示，分为“高速缓冲存储器（Cache）-主存-外存”三个层次。1） 主存■辅存层次：主存中存放当前执行的程序及所需数据，可供CPU直接访问。而外存中存放的是暂时不用的程序及数据。当CPU需要执行外存中的某一程序时，首先将该程序由外存调入主存，然后再执行。因为CPU不能直接访问外存。2） 主存-Cache层次：主存存取速度与CPU的速度的差距很大，为了弥补主存速度的不足，使之与CPU速度相匹配，则在CPU和主存之间增设一个容量不大，速度很高的“高速缓冲存储器”，简称Cache。这样较好的解决了速度与价格之间的矛盾。辅助存储器方面的计算：（重点）存储容量为capacity=n*t*s*b,n为存放数据的总盘面数；t为每面的磁道数；s为每道的扇区数；b为每个扇区存储的字节数寻道时间为磁头移动到目标磁道所需的时间。等待时间为待读写的扇区旋转到磁头下方所用的时间。一般用磁道旋转一周所用的时间的一半作为平均等待时间。4．磁盘存取时间=寻道时间+等待时间。5．位密度：沿磁道方向，单位长度存储二进制信息的个数；6．道密度：沿磁盘半径方向，单位长度内磁道的数目；7.数据传输速率R=B/T，B为一个磁道上记录的字节数，T为每转一周的时间安全性、可靠性与系统性能评测基础知识（重点）•诊断与容错（a） 计算机的故障：可以分为永久性、间歇性及瞬时性3类：（b） 故障诊断方法：包括故障检测和故障定位两个方面。（c） 故障诊断主要有下述三种方法：对电路直接进行测试的故障定位测试法“检查诊断程序”法：利用机器指令的功能来对系统的某些部件进行测试。微诊断法：在微程序控制的计算机中用微指令来对系统进行诊断。（d）计算机容错技术：容错是采用冗余方法来消除故障影响。针对硬件，有时间冗余和元器件冗余两种方法。（e）容错系统简单的双机备份：将关键的元件或整机设置两套，其中一套用作备份。>热备份（双重系统）：两套系统同时同步运行，当联机子系统检测到错误时，退出服务进行检修，而由“热备份”子系统接替工作。>冷备份（双工系统）：冷备份子系统平时停机或运行与联机系统无关的运算，当联机子系统产生故障时，人工或自动进行切换，使冷备份系统成为联机系统。操作系统支持的双机容错：在操作系统的层次上，支持联机维修，即故障部分退出运行、进行维修并重新投入运行都不影响正在运行的应用程序。•系统可靠性分析评价和计算机系统性能评测方法重点：可靠性与失效率的概念和关系，平均无故障时间MTBF和平均修复时间MTRF的计算，串联系统和并联系统的可靠性和失效律计算，N模冗余系统的可靠性计算二、数据结构与算法我们在课件中介绍的各种常用数据结构和算法都要求掌握。数据结构（1） 线性表：重点掌握存储结构中的链表（包括单链表、双向链表和循环链表）。（2） 栈：重点掌握栈的后进先出的特点（3） 队列：重点掌握队列的先进先出的特点（4） 树（重点）：关键掌握树的3种链式存储结构（双亲表示法、孩子表示法、孩子兄弟表示法）、树的前序、后序和中序遍历、（5） 二叉树（绝对重点）：应该是必考的内容。重点掌握：二叉树的特性（有5条）、二叉树的遍历（前序、后序和中序）、哈夫曼树的构造（哈夫曼算法）、三种二叉树的区分（满二叉树、完全二叉树和非完全二叉树）、二叉树的顺序存储结构和链式存储结构、树和森林转换为二叉树（见教程86页）（6） 图：关键掌握：图的性质、图的出处存储结构（重点是邻接矩阵和邻接链表）、图的遍历（深度优先和广度优先）、最小生成树的两个算法（Prim算法和Kruskal算法）、最短路径算法（Dijkstra算法）查找和排序算法：所有涉及到的算法的思想和时间复杂度都要求掌握。其中折半查找中的判定树和二叉排序树要会构造，平衡二叉树上的插入操作的4种调整手段要求掌握。常见算法设计方法要求一般掌握，即了解它们的思想。例题：

1、假设一个有3个盘片的硬盘，共有4个记录面，转速为7200转/分，盘面有效记录区域的外直径为30cm,内直径为10cm,记录位密度为250位/mm，磁道密度为8道/mm，每磁道分16个扇区，每扇区512字节，则该硬盘的非格式化容量和格式化容量约为__(58)__，数据传输率约为__(58)__若一个文件超出一个磁道容量，剩下的部分__(60)A.120MB和A.120MB和100MBB.30MB和25MBA.2356KB/s B.3534KB/sA.存于同一盘面的其它编号的磁道上C.60MB和50MB D.22.5MB和25MBC.7069KB/s D.1178KB/s存于其它盘面的同一编号的磁道上C.存于其它盘面的其它编号的磁道上C.存于其它盘面的其它编号的磁道上D.存放位置随机(58)B(59)D(60)B非格式化容量二面数X(磁道数/面)X内圆周长X最大位密度磁道数=(内外半径之差)X磁道密度=(30宁2—10宁2)X80=800内圆周长=2冗r=2X冗X5最大位密度二2500位/cm非格式化容量=4X800X2X冗X5X2500宁10242宁8=30mb格式化容量=面数X(磁道数/面)X(扇区数/道)X(字节数/扇区)=4X800X16X512宁10242=25mb数据传输速率=一个磁道上记录的字节数/每转一周的时间=512X16宁(60宁7200)位密度：沿磁道方向，单位长度存储二进制信息的个数；道密度：沿磁盘半径方向，单位长度内磁道的数目；数据传输速率R=B/T,B为一个磁道上记录的字节数，T为每转一周的时间2、利用并行处理技术可以缩短计算机的处理时间,所谓并行性是指__(51)__。可以采用多种措施来提高计算机系统的并行性,它们可分成三类,即__(52)__。提供专门用途的一类并行处理机(亦称阵列处理机)以__(53)__方式工作,它适用于__(54)__。多处理机是目前较高性能计算机的基本结构,它的并行任务的派生是__(55)__。:A.多道程序工作:A.多道程序工作C.非单指令流单数据流方式工作:A.多处理机,多级存储器和互连网络C.微指令,虚拟存储和I/0通道:A.SISD B.SIMD:A.事务处理 B.工业控制D.在同一时间完成两种或两种以上工作B.流水结构,高速缓存和精简指令集D.资源重复,资源共享和时间重叠。MISD D.MB4D矩阵运算 D.大量浮点计算:A.需要专门的指令来表示程序中并发关系和控制并发执行B.靠指令本身就可以启动多个处理单元并行工作只执行没有并发约束关系的程序先并行执行,事后再用专门程序去解决并发约束(51)D (52)D (53)B (54)C (55)A52：SIMD是单指令流多数据流计算机，通过资源重复实现并行性多处理机属于MIMD计算机3、发展容错技术可提高计算机系统的可靠性。利用元件冗余可保证在局部有故障情况下系统的正常工作。带有热备份的系统称为__(56)__系统。它是__(57)__,因此只要有一个子系统能正常工作,整个系统仍能正常工作。当子系统只能处于正常工作和不工作两种状态时,我们可以采用图A的并联模型,若单个子系统的可靠性都为0.8时,图示的三个子系统并联后的系统可靠性为__(58)__。若子系统能处于正常和不正常状态时,我们可以采用图B所示的表决模型,若图中有任何二个或三个子系统输出相同时,则选择该相同的输出作为系统输出,设单个子系统的可靠性为0.8时,整个系统的可靠性为__(59)__;若单个子系统的可靠性为0.5时,整个系统的可靠性为__(60)__。[图A] [图B]子系统1子系统1输入子系统2——输出输入——子系统2输出子系统3子系统3:A•并发 B.双工 C.双重 D.并行。:A.两子系统同时同步运行,当联机子系统出错时,它退出服务,由备份系统接替备份系统处于电源开机状态,一旦联机子系统出错时,立即切换到备份系统两子系统交替处于工作和自检状态,当发现一子系统出错时,它不再交替到工作状态两子系统并行工作,提高机器速度,一旦一个子系统出错,放弃并行工作。(58):A.0.9B.O.94C.O.992D.O.996(59):A.0.882B.O.896C.O.925D.O.94(60):A.0.5B.O.54 C.O.62D.O.65(56)C(57)A(58)C(59)B(60)A并联系统可靠性：R=l-(1-R)(l-R)„(1—R)=l—0.2X0.2X0.2=0.99212nN模冗余系统：N=2n+1。可靠性为：R xRi(1-R)n-iN00可靠性： i=n+卜丿 =C2*0.82*0.2+C3*0.83334、直接存储器访问(DMA)是一种快速传递大量数据常用的技术。工作过程大致如下：向CPU申请DMA传送；获CPU允许后，DMA控制器接管_A_的控制权；在DMA控制器的控制下，在存储器和_B_之间直接进行数据传送，在传送过程中不需要_CJ勺参与。开始时需提供要传送的数据的_D_和_E_0传送结束后，向CPU返回DMA操作完成信号。供选择的答案：A：①系统控制台 ②系统总线 ③I/O控制器 ④中央处理器

B：①外部设备②运算器③缓存④中央处理器C：①外部设备②系统时钟③系统总线④中央处理器D：①结束地址②起始地址③设备类型④数据速率E：①结束地址②设备类型③数据长度④数据速率214214232 14 2 35、现采用四级流水线结构分别完成一条指令的取指令、指令译码和取操作数、运算以及送回运算结果四个基本操作，每步操作时间依次为60ns,100ns,50ns和70ns。该流水线的操作周期应为—A_ns。若有一小段程序需要用20条基本指令完成（这些指令完全适合于流水线上执行），则得到第一条指令结果需_B_ns，完成该段程序需_C_ns。供选择的答案：A：①50②70③100④280B：①100②200③280④400C：①1400②