软件设计师笔记

第一章、计算机组成与结构

1.计算机硬件组成

• 计算机的基本硬件系统，由运算器，控制器，存储器，输入设备和输出设备5大部件组成。
• 运算器/控制器等部件被集成在一起统称中央处理单元（CPU）。CPU是硬件系统的核心，用于数据的加工处理，能完成各算数，逻辑运算及控制功能。
• 存储器是计算机系统中的记忆设备，分为内部存储器和外部存储器。
• 存储器。前者速度高容量小，一般用于临时存放层序，数据及中间结果。后者容量大，速度慢，可以长期保存程序和数据。
• 输入设备和输出设备合称为外部设备（简称外设），输入设备用于输入原始数据及各种命令，二输出设备则用于输出计算机运行的结果。

2.中央处理单元

• CPU的功能
  • 程序控制：CPU通过执行指令来控制程序的执行顺序。
  • 操作控制：一条指令功能的实现需要若干个操作信号配合来完成，CPU产生每条指令的操作信号并将操作信号送往对应的部件，控制相应的部件按指令的功能要求进行操作。
  • 时间控制：CPU对各种操作进行时间上的控制，即指令执行过程中操作信号的出现时间，持续时间及出现的时间顺序都需要进行严格的控制。
  • （运算器）数据处理：CPU通过对数据进行算数运算及逻辑运算等方式进行加工处理，数据加工处理的结果被人们所利用。所以，对数据的加工处理也是CPU最根本的任务。
  • 对系统内部和外部的中断（异常）做出响应，进行相应的处理。
  • CPU的组成：CPU主要由运算器、控制器、寄存器组和内部总线等部件组成
  • 运算器：由算术逻辑单元ALU（实现对数据的算术和逻辑运算）、累加寄存器AC（运算结果或源操作数的存放区）、数据缓冲寄存器DR（暂时存放内存的指令或数据）、和状态条件寄存器PSW（保存指令运行结果的条件码内容，如溢出标志等）组成。执行所有的算术运算，如加减乘除等；执行所有的逻辑运算并进行逻辑测试，如与、或、非、比较等。
  • 控制器：由指令寄存器IR（暂存CPU执行指令）、程序计数器PC（存放指令执行地址）、地址寄存器AR（保存当前CPU所访问的内存地址）、指令译码器ID（分析指令操作码）等组成。控制整个CPU的工作，最为重要。
  • CPU依据指令周期的不同阶段来区分二进制的指令和数据，因为在指令周期的不同阶段，指令会命令CPU分别去取指令或者数据。

练习题

1. CPU执行算术运算或者逻辑运算时，常将源操作数和结果暂存在（B）中。 A.程序计数器（PC） B.累加器（AC） C.指令寄存器（IR）

   D.地址寄存器（AR）

2. 执行CPU指令时，在一个指令周期的过程中，首先需从内存读取要执行的指令，此时先要将指令的地址即（C）的内容送到地址总线上。 A.指令寄存器（IR）

   C.程序计数器（PC）

   B.通用寄存器（GR） D.状态寄存器（PSW）

3.数据的表示

进制的转换

• 进制的表示：二进制、十六进制，一般在题目中会给出中文说明，如果没给出，注意二进制符号为0b，一般表示为0b0011，十六进制符号为0x或H，可表示为0x18F或18FH，（十六进制可表示0-15，其中10-15用A-F来表示）

• R进制整数转十进制：位权展开法，用R进制数的每一位乘以R的n次方，n是变量，从R进制数的整数最低位开始，依次为0，1，2，3...累加。

  • 例如有6进制数5043，此时R=6，用6进制数的每一位乘以6的n次方，n是变量，从6进制数的整数最低位开始（5043从低位到高位排列：3，4，0，5），n依次为0，1，2，3，
  • 那么最终5043=3 * 6^0+4 * 6^1+0 * 6^2+5 * 6^3=1107.

• 十进制转R进制：十进制整数（除以R倒取余数），用十进制整数除以R，记录每次所得余数，若商不为0，则继续除以R，直至商为0，而后将所有余数从下至上记录，排列成从左至右顺序，即为转换后的R进制数；

  • 例：有十进制数200，转换为6进制，此时R=6，将200/6，得商为33，余数为2；因为商不等于0，因此再将商33/6，得商为5，余数为3；再将5/6，得商为0，余数为5；此时商为0，将所有余数从下到上记录，得532。

• m进制转n进制：先将m进制转化为十进制数，再将十进制数转化为n进制数，中间需要通过十进制中转，但下面两种进制间可以直接转化：

  • 二进制转八进制：每三位二进制数转换为一位八进制数，二进制数位个数不是三的倍数，则在前面补0（原则是数值不变），如二进制数01101有五位，前面补一个0就有六位，为001 101，每三位转换为一位八进制数，001=1，101=1+4=5，也即01101=15
  • 二进制转十六进制：每四位二进制数转换为一位十六进制数，二进制数位个数不是四的倍数，则在前面补0，如二进制数101101有六位，前面补两个0就有八位，为0010 1101，每四位转换为一位十六进制数，0010=2，1101=13=D，也即101101=2D

重点：二进制 十进制 十六进制互相转换

数据表示 -编码方式

• 机器数：各种数值在计算机中表示的形式，其特点是使用二进制计数制，数的符号用0和1表示，小数点则隐含，不占位置。

  机器数有无符号数和带符号数之分。无符号数表示正数，没有符号位。带符号数最高位为符号位，正数符号位为0，负数符号位为1。

• 定点表示法分为纯小数和纯整数两种，其中小数点不占存储位，而是按照以下约定：

  • 纯小数：约定小数点的位置在机器数的最高数值位之前。
  • 纯整数：约定小数点的位置在机器数的最低数值位之后。

• 真值：机器数对应的实际数值。

• 带符号数有下列编码方式，当真值为-45时：

  • 原码：一个数的正常二进制表示，最高位表示符号，数值0的源码有两种形式： +0（00000000）和-0（10000000）。-45对应原码为10101101
  • 反码：正数的反码即原码；**负数的反码是在原码的基础上，除符号位外，其他各位按位取反。**数值0的反码也有两种形式：+0（00000000），-0（11111111）。-45对应反码为11010010
  • 补码：正数的补码即原码；负数的补码是在原码的基础上，除符号位外，其他各位按位取反，而后末位+1，若有进位则产生进位。因此数值0的补码只有一种形式+0 =-0= 0 0000000。-45对应补码为11010011
  • 移码：用作浮点运算的阶码，无论正数负数，都是将该原码的补码的首位（符号位）取反得到移码。-45对应移码为01010011

• 浮点数：表示方法为N=F** 2^E，其中E称为阶码，E称为尾数；类似于十进制的科学计数法，如85.125=0.8512510^2，二进制如101.011= 0.1010112^3.

  • 在浮点数的表示中，阶码为带符号的纯整数，尾数为带符号的纯小数，要注意符号占最高位（正数0负数1），其表示格式如下： 阶符 阶码 数符 尾数 很明显，与科学计数法类似，一个浮点数的表示方法不是唯一的，浮点数所能表示的数值范围由阶码确定，所表示的数值精度由尾数确定。

• 尾数的表示采用规格化方法，也即带符号尾数的补码必须为1.0xxxx（负数）或者0.1xxxx（正数），其中x可为0或1.

  • 浮点数的运算： 对阶（使两个数的阶码相同，小阶向大阶看齐，较小阶码增加几位，尾数就右移几位）

    尾数计算（相加，若是减运算，则加负数） 结果规格化（即尾数表示规格化，带符号尾数转换为1.0xxxx或0.1xxxx）

例题：

1. 如果“2X”的补码是“90H”，那么x的真值是（B） A.72 B.-56 C.56 D.111

解析：这里主要是考察补码的表示，补码中无正负之分，符号位作为数值参与计数。2X的补码90H转换为二进制为1001 0000，可知最高位符号位为1，也就是负数，按照负数转化为补码规则 （先取反后加1），求真值应该逆向转化即对补码先-1再取反，得出2x的源码为1111 0000，在真值中区分正负，最高位作为符号独立显示，不参与计数（与补码的区别），因此为-1110000=-112，X就是-56.

1. 设16位浮点数，其中阶符1位、阶码值6位、数符1位、尾数8位。若阶码用移码表示，尾数用补码表示，则该浮点数所能表示的数值范围是（B）难点

   A:-264 ~（1-2*）264 B:-263~（1-28）263 C:-264 ~（1-2-（1-2*）264 ~（1-28）264 D:-（1-28）263 ~（1-28）263

阶码用移码表示，共8位，则有2^8=64位来表示阶码，取n=64计算出移码可表示最太2^63，而尾数用补码表示，因为尾数是小数，因此代入补码小数范围的公式，可表示-1-（1-2^-8），然后首尾分别和2的63次方相乘得出答案是B

4.效验码

• 码距：就单个编码A：00而言，其码距为1，因为其只需要改变一位就变成另一个编码。在两个编码中，从A码到B码转换所需要改变的位数称为码距，如A：00要转换为B：11，码距为2。一般来说，码距越大，越利于纠错和检错。

• 奇偶校验码：在编码中增加1位校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变为2。例如：

  • 奇校验：编码中，含有奇数个1，发送给接收方，接收方收到后，会计算收到的编码有多少个1，如果是奇数个，则无误，是偶数个，则有误。
  • 偶校验同理，只是编码中有偶数个1，由上述，奇偶校验只能检1位错，并且无法纠错。

• CRC :循环冗余校验码： 只能检错，不能纠错。使用CRC编码，需要先约定一个生成多项式G（x）。 生成多项式的最高位和最低位必须是1。假设原始信息有m位，则对应多项式M（x），生成校验码思想就是在原始信息位后追加若干校验位，使得追加的信息能被G（x）整除。接收方接收到带校验位的信息，然后用G（x）整除。余数为0，则没有错误；反之则发生错误。

  • 例：假设原始信息串为10110，CRC的生成多项式为G（x）=x^4+x+1，求CRC校验码。 （1）在原始信息位后面添0，假设生成多项式的阶为r，则在原始信息位后添加口r个0，本题中，G（x）阶为4，则在原始信息串后加4个0，得到的新串为101100000，作为被除数。 （2）由多项式得到除数，多项中x的幂指数存在的位置1，不存在的位置0。本题中，x的幂指数为0，1，4的变量都存在，而幂指数为2，3的不存在，因此得到串10011. （3）生成CRC校验码，将前两步得出的被除数和除数进行模2除法运算（即不进位也不借位的除法运算）。除法过程如下图所示。

• 得到余数1111。 注意：余数不足r，则余数左边用若干个0补齐。如求得余数为11，r=4，则补两个0得到0011。 （4）生成最终发送信息串，将余数添加到原始信息后。上例中，原始信息为10110，添加余数1111后，结果为10110 1111，发送方将此数据发送给接收方。 （5）接收方进行校验。接收方的CRC校验过程与生成过程类似，接收方接收了带校验和的帧后，用多项式G（x）来除。余数为0，则表示信息无错；否则要求发送方进行重传。 注意：收发信息双方需使用相同的生成多项式。

例题：

1. 循环冗余校验码（Cyclic Redundancy Check，CRC）是数据通信领域中最常用的一种差错校验码，该校验方法中，使用多项式除法（模2除法）运算后的余数为校验字段。若数据信息为n位，则将其左移k位后，被长度为k+1位的生成多项式相除，所得的k位余数即构成k个校验位，构成n+k位编码。若数据信息为1100，生成多项式为X3+X+1（即1011），则CRC编码是（A） A.1100010

   B.1011010

   C.1100011

   D.1011110

• 海明码：本质也是利用奇偶性来检错和纠错的检验方法，构成方法是在数据位之间的确定位置上插入k个校验位，通过扩大码距实现检错和纠错。 设数据位是n位，校验位是k位，则n和k必须满足以下关系：2^k-1>=n+k

  例：求信息1011的海明码

1. 校验位的位数和具体的数据位的位数之间的关系

   所有位都编号，从最低位编号，从1开始递增，校验位处于2的n（n=0 12......）次方中，即处于第1，2，4，8，16，32，位上，其余位才能填充真正的数据位，若信息数据为1011，则可知，第1，2，4位为校验位，第3，5，6，7位为数据位，用来从低位开始存放1011，得出信息位和校验位分布如下：

2. 计算校验码

   将所有信息位的编号都拆分成 2的幂指数 表示，如下图所示：

​ 上图中，7=4+2+1，表示7由第4位校验位（r2）和第2位校验位（r1）和第1位校验位（r0）共同校验，同理，第6位数据位6=4+2，第5位数据位5=4+1，第3位数据位3=2+1，前面知道，这些2的n次方都是校验位，可知，第4位校验位校验第765三位数据位，因此，第4位校验位r2等于这三位数据位的值异或，第2位和第1位校验位计算原理同上. ​ 计算出三个校验位后，可知最终要发送的海明校验码为1010101.

3. 检错和纠错原理 接收方收到海明码之后，会将每一位校验位与其校验的位数分别异或，即做如下三组运算：

​ 如果是偶校验，那么运算得到的结果应该全为0，如果是奇校验，应该全为1，才是正确，假设是偶校验，且接收到的数据为1011101（第四位出错），此时，运算的结果为：

​ 这里不全为0，表明传输过程有误，并且按照r2r1r0排列为二进制100，这里指出的就是错误的位数，表示第100，即第4位出错，找到了出错位，纠错方法就是将该位逆转。

​ 例题：

1. 海明码是一种纠错码，其方法是为需要校验的数据位增加若干校验位，使得校验位的值决定于某些被校位的数据，当被校数据出错时，可根据校验位的值的变化找到出错位，从而纠正错误。对于32位的数据，至少需要加（ D ）个校验位才能构成海明码。 以10位数据为例，其海明码表示为D9D8D7D6D5D4P4D3D2D1P3D0P2P1中，其中Di（Osis9）表示数据位，Pj（1sjs4）表示校验位，数据位D9由P4、P3和P2进行校验（从右至左D9的位序为14，即等于8+4+2，因此用第8位的P4、第4位的P3和第2位的P2校验），数据位D5由（B）进行校验 A.3 B.4 C.5 D.6

   A.P4P1

   B.P4P2

   C.P4P3P1

   D.P3P2P1

体系结构

1.体系结构分类

• 按处理机的数量进行分类：单处理系统（一个处理单元和其他设备集成）、并行处理系统（两个以上的处理机互联）分布式处理系统（物理上远距离且松耦合的多计算机系统）
• Flynn分类法：分类有两个因素，即指令流和数据流，指令流由控制部分处理，每一个控制部分处理一条指令流，多指令流就有多个控制部分；数据流由处理器来处理，每一个处理器处理一条数据流，多数据流就有多个处理器；至于主存模块，是用来存储的，存储指令流或者数据流，因此，无论是多指令流还是多数据流，都需要多个主存模块来存储，对于主存模块，指令和数据都一样。
• 依据计算机特性，是由指令来控制数据的传输，因此，一条指令可以控制一条或多条数据流，但一条数据流不能被多条指令控制，否则会出错，就如同上级命令太多还互相冲突，不知道该执行哪个，因此多指令单数据MISD不可能。

2.指令系统

• 计算机指令的组成：一条指令由操作码和操作数两部分组成，操作码决定要完成的操作，操作数指参加运算的数据及其所在的单元地址。 在计算机中，操作要求和操作数地址都由二进制数码表示，分别称作操作码和地址码，整条指令以二进制编码的形式存放在存储器中。

• 计算机指令执行过程：取指令——分析指令——执行指令三个步骤，首先将程序计数器PC中的指令地址取出，送入地址总线，CPU依据指令地址去内存中取出指令内容存入指令寄存器IR；而后由指令译码器进行分析，分析指令操作码；最后执行指令，取出指令执行所需的源操作数。

• 指令寻址方式顺序寻址方式：当执行一段程序时，是一条指令接着一条指令地顺序执行。

  跳跃寻址方式：指下一条指令的地址码**不是由程序计数器给出，而是由本条指令直接给出。**程序跳跃后，按新的指令地址开始顺序执行。因此，程序计数器的内容也必须相应改变，以便及时跟踪新的指令地址。

• 指令操作数的寻址方式

  立即寻址方式：指令的地址码字段指出的不是地址，而是操作数本身。

  直接寻址方式：在指令的地址字段中直接指出操作数在主存中的地址。

  间接寻址方式：指令地址码字段所指向的存储单元中存储的是操作数的地址。

  寄存器寻址方式：指令中的地址码是寄存器的编号。

  基址寻址方式：将基址寄存器的内容加上指令中的形式地址而形成操作数的有效地址，其优点是可以扩大寻址能力。 变址寻址方式：变址寻址方式计算有效地址的方法与基址寻址方式很相似，它是将变址寄存器的内容加上指令中的形式地址而形成操作数的有效地址。

• CISC是复杂指令系统，兼容性强，指令繁多、长度可变，由微程序实现；

• RISC是精简指令系统，指令少，使用频率接近，主要依靠硬件实现（通用寄存器硬布线逻辑控制）。

• 具体区别如下：

例题：

1. Flynn分类法根据计算机在执行程序的过程中（A）的不同组合，将计算机分为4类。当前主流的多核计算机属于（D）计算机。 A.指令流和数据流 B.数据流和控制流 C.指令流和控制流 D.数据流和总线带宽 A.SISD B.SIMD C.MISD D.MIMD
2. 以下关于复杂指令集计算机（Complex Instruction Set Computer，CISC）的叙述中，正确的是（D）。 A.只设置使用频度高的一些简单指令，不同指令执行时间差别很小 B.CPU中设置大量寄存器，利用率低 C.常采用执行速度更快的组合逻辑实现控制器 D.指令长度不固定，指令格式和寻址方式多

流水线

• 指令流水线原理：将指令分成不同段，每段由不同的部分去处理，因此可以产生叠加的效果，所有的部件去处理指令的不同段

• RISC中的流水线技术： （1）超流水线（Super Pipe Line）技术。它通过细化流水、增加级数和提高主频，使得在每个机器周期内能完成一个甚至两个浮点操作。其实质是以时间换取空间。 （2）超标量（Super Scalar）技术。它通过内装多条流水线来同时执行多个处理，其时钟频率虽然与一般流水接近，却有更小的CPI。其实质是以空间换取时间。 （3）超长指令字（Very Long Instruction Word，VLIW）技术。 VLIW 和超标量都是20 世纪80 年代出现的概念，其共同点是要同时执行多条指令，其不同在于超标量依靠硬件来实现并行处理的调度，VLIW 则充分发挥软件的作用，而使硬件简化，性能提高。

• 流水线时间计算 *

  流水线周期：指令分成不同执行段，其中执行时间最长的段为流水线周期。

  流水线执行时间：1条指令总执行时间+（总指令条数-1）*流水线周期。

  流水线吞吐率计算：吞吐率即单位时间内执行的指令条数。

  公式：指令条数/流水线执行时间。

  流水线的加速比计算：加速比即使用流水线后的效率提升度，即比不使用流水线快了多少倍，越高表明流水线效率越高，

  公式：不使用流水线执行时间/使用流水线执行时间。

例题：

1. 流水线的吞吐率是指流水线在单位时间里所完成的任务数或输出的结果数。设某流水线有5段，有 1 段的时间为2ns，另外4 段的每段时间为1ns，利用此流水线完成 100 个任务的吞吐率约为（B）个/s。 A.500×10^6

   B.490×10^6

   C.250×10^6

   D.167×10^6

2. 假设磁盘块与缓冲区大小相同，每个盘块读入缓冲区的时间为15us，由缓冲区送至用户区的时间是5us，在用户区内系统对每块数据的处理时间为1us，若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区，并送至用户区进行处理，那么采用单缓冲区需要花费的时间为（D）us；采用双缓冲区需要花费的时间为（C）us。 A.150 B.151 C.156 D.201

   A.150 B.151 C.156 D.201

3. 流水线技术是通过并行硬件来提高系统性能的常用方法。对于一个k段流水线，假设其各段的执行时间均相等（设为t），输入到流水线中的任务是连续的理想情况下，完成n个连续任务需要的总时间为（B）。若某流水线浮点加法运算器分为5段，所需要的时间分别是6ns，7ns，8ns，9ns和6ns，则其最大加速比为（A）。 A.nkt B.（k+n-1）t C.（n-k）kt D.（k+n+1）t

   A.4 B.5 C.6 D.7

3.存储系统

• 计算机采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾问题。
• 两级存储：Cache-主存、主存-辅存（虚拟存储体系）。
• 局部性原理：总的来说，在CPU运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括下面两个方面：
  • 时间局部性原理：如果一个数据项正在被访问，那么在近期它很可能会被再次访问，即在相邻的时间里会访问同一个数据项。
  • 空间局部性原理：在最近的将来会用到的数据的地址和现在正在访问的数据地址很可能是相近的，即相邻的空间地址会被连续访问。

• 高速缓存Cache用来存储当前最活跃的程序和数据，直接与CPU交互，位于CPU和主存之间，容量小，速度为内存的5-10倍，由半导体材料构成。其内容是主存内存的副本拷贝，对于程序员来说是透明的。

• Cache由控制部分和存储器组成，存储器存储数据，控制部分判断CPU要访问的数据是否在Cache中，在则命中，不在则依据一定的算法从主存中替换。

• 地址映射：在CPU工作时，送出的是主存单元的地址，而应从Cache存储器中读/写信息。这就需要将主存地址转换为Cache存储器地址，这种地址的转换称为地址映像，由硬件自动完成映射，分为下列三种方法：

  • 直接映像：将Cache存储器等分成块，主存也等分成块并编号。主存中的块与Cache中的块的对应关系是固定的，也即二者块号相同才能命中。地址变换简单但不灵活，容易造成资源浪费。（如图所示）

    

  • 全相联映像：同样都等分成块并编号。主存中任意一块都与Cache中任意一块对应。因此可以随意调入Cache任意位置，但地址变换复杂，速度较慢。因为主存可以随意调入Cache任意块，只有当Cache满了才会发生块冲突，是最不容易发生块冲突的映像方式。

    

  • 组组相连映像：前面两种方式的结合，将Cache存储器先分块再分组，主存也同样先分块再分组，组间采用直接映像，即主存中组号与Cache中组号相同的组才能命中，但是组内全相联映像，也即组号相同的两个组内的所有块可以任意调换。

• 替换算法的目标就是使Cache获得尽可能高的命中率。常用算法有如下几种。

  （1）随机替换算法。就是用随机数发生器产生一个要替换的块号，将该块替换出去。 （2）先进先出算法。就是将最先进入Cache的信息块替换出去。 （3）近期最少使用算法。这种方法是将近期最少使用的Cache中的信息块替换出去。 （4）优化替换算法。这种方法必须先执行一次程序，统计Cache的替换情况。

  ​ 有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换。

• 命中率及平均时间 Cache有一个命中率的概念，即当CPU所访问的数据在Cache中时，命中，直接从Cache中读取数据，设读取一次Cache时间为1ns，若CPU访问的数据不在Cache中则需要从内存中读取，设读取一次内存的时间为1000ns，若在CPU多次读取数据过程中，有90%命中Cache，则CPU读取一次的平均时间为（90%*1+10%*1000）ns

  

  例题：

1. 按照Cache地址映像的块冲突概率，从高到低排列的是（B）。 A.全相联映像→直接映像→组相联映像

   B.直接映像→组相联映像→全相联映像

   C.组相联映像→全相联映像→直接映像

   D.直接映像→全相联映像→组相联映像

2. 以下关于Cache与主存间地址映射的叙述中，正确的是（D）。

   A.操作系统负责管理Cache与主存之间的地址映射

   B.程序员需要通过编程来处理Cache与主存之间的地址映射

   C.应用软件对C ache与主存之间的地址映射进行调度

   D.由硬件自动完成Cache与主存之间的地址映射

基本概念：K、M、G是数量单位，在存储器里相差1024倍。

b，B是存储单位，1B = 8b

​ 例题：地址编号从80000H到BFFFFH且按字节编址的内存容量为（B）KB，若用016K*4bit的存储器芯片构成该内存，共需（C）片

​ A.128 B.256 C.512 D.1024

​ A.8 B.16 C.32 D.64

答案：BC解析：首先计算出地址段包含的存储空间数，为BFFFFH-80000H+1=40000H，按字节编制，即一个存储空间占一个字节，共40000H个字节，转换为十进制即256KB；该存储芯片总容量为16K*0.5B=8KB，因此共需256/8=32片该芯片才够存储。

特别提醒：不要硬算，要化简为2的幂指数来算。

• 磁盘结构和参数

  • 磁盘有正反两个盘面，每个盘面有多个同心圆，每个同心圆是一个磁道，每个同心圆又被划分为多个扇区，数据就被存放在一个个扇区中。

  • 磁头首先要寻找到对应的磁道，然后等待磁盘进行周期旋转，旋转到指定的扇区，才能读取到对应的数据，因此，会产生寻道时间和等待时间。

    公式为：存取时间=寻道时间+等待时间（平均定位时间+转动延迟）。

  • 注意：寻道时间是指磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间。

• 磁盘调度算法 之前已经说过，磁盘数据的读取时间分为寻道时间+旋转时间，也即先找到对应的磁道，而后再旋转到对应的扇区才能读取数据，其中寻道时间耗时最长，需要重点调度，有如下调度算法：

  • 先来先服务FCFS：根据进程请求访问磁盘的先后顺序进行调度。
  • 最短寻道时间优先SSTF：请求访问的磁道与当前磁道最近的进程优先调度，使得每次的寻道时间最短。会产生“饥饿”现象，即远处进程可能永远无法访问。
  • 扫描算法SCAN：又称“电梯算法”，磁头在磁盘上双向移动，其会选择离磁头当前所在磁道最近的请求访问的磁道，并且与磁头移动方向一致，磁头永远都是从里向外或者从外向里一直移动完才掉头，与电梯类似。
  • 单向扫描调度算法CSCAN：与SCAN不同的是，其只做单向移动，即只能从里向外或者从外向里。

例题：

1. 假设某磁盘的每个磁道划分成11个物理块，每块存放1个逻辑记录。逻辑记录R0，R1，，，，，R9，R10存放在同一个磁道上，记录的存放顺序如下表所示：

​ 如果磁盘的旋转周期为33ms，磁头当前处在R0的开始处。若系统使用单缓冲区顺序处理这些记录，每个记录处理时间为3ms，则处理这11个记录的最长时间为（C）；若对信息存储进行优化分布后，处理11个记录的最少时间为（B）。 ​ A.33ms B.336ms C.366ms D.376ms

​ A.33ms B.66ms C.86ms D.93ms

2. 在磁盘调度管理中，应先进行移臂调度，再进行旋转调度。假设磁盘移动臂位于21号柱面上，进程的请求序列如下表所示。如果采用最短移臂调度算法，那么系统的响应序列应为（D）。

4.输入输出技术

• 计算机系统中存在多种内存与接口地址的编址方法，常见的是下面两种： 1）内存与接口地址独立编址方法 内存地址和接口地址是完全独立的两个地址空间。访问数据时所使用的指令也完全不同，用于接口的指令只用于接口的读/写，其余的指令全都是用于内存的。 因此，在编程序或读程序时很易使用和辨认。这种编址方法的缺点是用于接口的指令太少、功能太弱。 2）内存与接口地址统一编址方法 内存地址和接口地址统一在一个公共的地址空间里，即内存单元和接口共用地址空间。优点是原则上用于内存的指令全都可以用于接口，这就大大地增强了对接口的操作功能，而且在指令上也不再区分内存或接口指令。该编址方法的缺点就在于整个地址空间被分成两部分，其中一部分分配给接口使用，剩余的为内存所用，这经常会导致内存地址不连续。

计算机和外设间的数据交互方式：

• 程序控制（查询）方式：CPU主动查询外设是否完成数据传输，效率极低。
• 程序中断方式：外设完成数据传输后，向CPU发送中断，等待CPU处理数据，效率相对较高。中断响应时间指的是从发出中断请求到开始进入中断处理程序；中断处理时间指的是从中断处理开始到中断处理结束。中断向量提供中断服务程序的入口地址。多级中断嵌套，使用堆栈来保护断点和现场。
• DMA方式（直接主存存取）：CPU只需完成必要的初始化等操作，数据传输的整个过程都由DMA控制器来完成，在主存和外设之间建立直接的数据通路，效率很高。
• 在一个总线周期结束后，CPU会响应DMA请求开始读取数据；CPU响应程序中，断方式请求是在一条指令执行结束时。

• 总线（Bus），是指计算机设备和设备之间传输信息的公共数据通道。总线是连接计算机硬件系统内多种设备的通信线路，它的一个重要特征是由总线上的所有设备共享，因此可以将计算机系统内的多种设备连接到总线上。
• 从广义上讲，任何连接两个以上电子元器件的导线都可以称为总线，通常分为以下三类：
  • 内部总线：内部芯片级别的总线，芯片与处理器之间通信的总线。
  • 系统总线：是板级总线，用于计算机内各部分之间的连接，具体分为**【数据总线（并行数据传输位数）、地址总线（系统可管理的内存空间的大小）、控制总线（传送控制命令）】**。代表的有ISA总线、EISA总线、PCI总线。
  • 外部总线：设备一级的总线，微机和外部设备的总线。代表的有RS232（串行总线）、SCSI（并行总线）、USB（通用串行总线，即插即用，支持热插拔）。

例题：

1. 计算机系统中常用的输入/输出控制方式有无条件传送、中断、程序查询和DMA方式等。当采用 （D）方式时，不需要CPU执行程序指令来传送数据。 A.中断 B.程序查询 C.无条件传送 D.DMA

2. 以下关于总线的说法中，正确的是（C）。 A.串行总线适合近距离高速数据传输，但线间串扰会导致速率受限

   B.并行总线适合长距离数据传输，易提高通信时钟频率来实现高速数据传输

   C.单总线结构在一个总线上适应不同种类的设备，设计复杂导致性能降低

   D.半双工总线只能在一个方向上传输信息

5.计算机可靠性

• 可靠性指标

  平均无故障时间MTTF = 1/失效率。

  平均故障修复时间MTTR=1/修复率。

  平均故障间隔时间MTBF=MTTF+MTTR。

  系统可用性=MTTF/（MTTF+MTTR）*100%。

• 串并联系统可靠性 无论什么系统，都是由多个设备组成的，协同工作，而这多个设备的组合方式可以是串联、并联，也可以是混合模式，假设每个设备的可靠性为R1，R2.....Rn，则不同的系统的可靠性公式如下：

  串联系统，一个设备不可靠，整个系统崩溃，整个系统可靠性R=R1 R2 * ... Rn。

• 并联系统，所有设备都不可靠，整个系统才崩溃，整个系统可靠性R=1-（1-R1）*（1-R2） …（1-Rn）。

• N模冗余系统：N 模冗余系统由N个（N-2n+1）相同的子系统和一个表决器组成，表决器把N个子系统中占多数相同结果的输出作为输出系统的输出，如图所示。在N个子系统中，只要有n+1个或n+1个以上子系统能正常工作，系统就能正常工作，输出正确的结果。 -了解

例题：

1. 某系统的可靠性结构框图如下图所示，假设部件1、2、3的可靠度分别为0.90；0.80；0.80（部件2、 3为冗余系统）若要求该系统的可靠度不小于0.85，则进行系统设计时，部件4的可靠度至少应为 （A）。

第二章、操作系统知识

1.操作系统的概述

• 操作系统定义：能有效地组织和管理系统中的各种软/硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口。

• 操作系统有两个重要的作用：第一，通过资源管理提高计算机系统的效率；第二，改善人机界面向用户提供友好的工作环境。

• 操作系统的4个特征是并发性、共享性、虚拟性和不确定性。

• 操作系统的功能： （1）进程管理。实质上是对处理机的执行“时间”进行管理，采用多道程序等技术将CPO的时间合理地分配给每个任务，主要包括进程控制、进程同步、进程通信和进程调度。 （2）文件管理。主要包括文件存储空间管理、目录管理、文件的读/写管理和存取控制。 （3）存储管理。存储管理是对主存储器“空间”进行管理，主要包括存储分配与回收、存储保护、地址映射（变换）和主存扩充。 （4）设备管理。实质是对硬件设备的管理，包括对输入/输出设备的分配、启动、完成和回收。 （5）作业管理。包括任务、界面管理、人机交互、图形界面、语音控制和虚拟现实等。

• 操作系统的分类：

  批处理操作系统：单道批处理和多道批处理（主机与外设可并行）。

  分时操作系统：一个计算机系统与多个终端设备连接。将CPU的工作时间划一分为许多很短的时间片，轮流为各个终端的用户服务。

  实时操作系统：实时是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。实时系统对交互能力要求不高，但要求可靠性有保障。

  网络操作系统：是使联网计算机能方便而有效地共享网络资源，为网络用户提供各种服务的软件和有关协议的集合。三种模式：集中模式、客户端/服务器模式、对等模式。

  分布式操作系统：分布式计算机系统是由多个分散的计算机经连接而成的计算机系统，系统中的计算机无主、次之分，任意两台计算机可以通过通信交换信息。

  微型计算机操作系统：简称微机操作系统，常用的有Windows，Mac OS、Linux。

  嵌入式操作系统主要特点： （1）微型化。从性能和成本角度考虑，希望占用的资源和系统代码量少，如内存少、字长短、运行速度有限、能源少（用微小型电池）。 （2）可定制。从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置，以满足不同应用需要。 （3）实时性。嵌入式操作系统主要应用于过程控制、数据采集、传输通信、多媒体信息及关键要害领域需要迅速响应的场合，所以对实时性要求较高。 （4）可靠性。系统构件、模块和体系结构必须达到应有的可靠性，对关键要害应用还要提供容错和防故障措施。 （5）易移植性。为了提高系统的易移植性，通常采用硬件抽象层和板级支撑包的底层设计技术。

  嵌入式系统初始化过程按照自底向上、从硬件到软件的次序依次为：片级初始化→板级初始化→系统初始化。

2.进程组成和状态

• 进程的组成：进程控制块PCB（唯一标志）、程序（描述进程要做什么）、数据（存放进程执行时所需数据）。
• 进程基础的状态是下左图中的三态图。需要熟练掌握左下图中的进程三态之间的转换。

• 运行：表示进程正在运行 需要CPU
• 就绪：除了CPU之外其余都可以了，等待分配CPU
• 阻塞：没有CPU，其余也没准备好
• 新建：新建一个进程
• 终止：释放资源

例题：

1. 在单处理机系统中，采用先来先服务调度算法。系统中有4个进程P1、P2、P3、P4（假设进程按此顺序到达），其中P1为运行状态，P2为就绪状态，P3和P4为等待状态，且P3等待打印机，P4等待扫描仪。若P1（A），则P1、P2、P3和P4的状态应分别为（C）。 A.时间片到 B.释放了扫描仪

   C.释放了打印机 D.已完成 A.等待、就绪、等待和等待

   B.运行、就绪、运行和等待

   C.就绪、运行、等待和等待

   D.就绪、就绪、等待和运行

3.前趋图

• 用来表示哪些任务可以并行执行，哪些任务之间有顺序关系，具体如下图：可知，ABC可以并行执行，但是必须ABC都执行完后，才能执行D，这就确定了两点：任务间的并行、任务间的先后顺序。

进程资源图

• 用来表示进程和资源之间的分配和请求关系，如下图所示：

• P代表进程，R代表资源，R方框中有几个圆球就表示有几个这种资源，在上图中，R1指向P1，表示R1有一个资源已经分配给了P1，P1指向R2，表示P1还需要请求一个R2资源才能执行。
• 阻塞节点：某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图中P2
• 非阻塞节点：某进程所请求的资源还有剩余，可以分配给该进程继续运行。 如上图中P1、P3。
• 当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态。

例题：

1. 在如下所示的进程资源图中，（ C ）；该进程资源图是（ B ）。

   

   A.P1、P2、P3都是阻塞节点

   B.P1是阻塞节点、P2、P3是非阻塞节点

   C.P1、P2是阻塞节点、P3是非阻塞节点

   D.P1、P2是非阻塞节点、P3是阻塞节点

   A.可以化简的，其化简顺序为P1→P2→P3

   B.可以化简的，其化简顺序为P3-P1→P2

   C.可以化简的，其化简顺序为P2-P1-P3

   D.不可以化简的，因为P1、P2、P3申请的资源都不能得到满足

进程资源图化简的方法是：先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞的，接着把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来，这样，系统剩余的空闲资源便多了起来，接着又去看看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。最后，所有的资源和进程都变成孤立的点。图中P3是不阻塞的，故P3为化简图的开始，把P3孤立，再回收分配给他的资源，可以看到P1也变为不阻塞节点了，故P3.P1.P2是可以的。

4.进程同步与互斥

• 临界资源：各进程间需要以互斥方式对其进行访问的资源。
• 临界区：指进程中对临界资源实施操作的那段程序。本质是一段程序代码。
• 互斥：某资源（即临界资源）在**同一时间内只能由一个任务单独使用，**使用时需要加锁，使用完后解锁才能被其他任务使用；如打印机。
• 同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况下停下等待，不存在资源是否单独或共享的问题；如自行车和汽车。
• 互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1。
• 同步信号量：对共享资源的访问控制，初值一般是共享资源的数量。

进程同步与互斥

• **P操作：申请资源，S-S-1，若S>=0，**则执行P操作的进程继续执行；若S<0，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。
• **V操作：释放资源，S=S+1，若S>0，**则执行v操作的进程继续执行；若S<=0，则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被P操作一阻塞的进程可以继续执行），然后执行V操作的进程继续。

• 经典问题：生产者和消费者的问题 三个信号量：互斥信号量S0（仓库独立使用权），同步信号量S1（仓库空闲个数），同步信号量S2（仓库商品个数）。

  

考试真题

答案：C B B 解析：这种题型常考，并且也很简单。五个信号量对应前趋图上五根连线，如下图：

答案： C B D

5.进程调度

• 进程调度方式是指当有更高优先级的进程到来时如何分配CPU。分为可剥夺和不可剥夺两种，可剥夺指当有更高优先级进程到来时，强行将正在运行进程的CPU分配给高优先级进程；不可剥夺是指高优先级进程必须等待当前进程自动释放CPU。
• 在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。 （1）高级调度。高级调度又称“长调度" "作业调度"或“接纳调度"，它决定处于输入池中的哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。在系统中一个作业只需经过一次高级调度。 （2）中级调度。中级调度又称“中程调度”或“对换调度”，它决定**处于交换区中的哪个就绪进程可以调入内存，以便直接参与对CPU的竞争。 （3）低级调度。低级调度又称"短程调度”或“进程调度”，它决定处于内存中的哪个就绪进程可以占用CPU，**低级调度是操作系统中最活跃、最重要的调度程序，对系统的影响很大。

调度算法：

• 先来先服务FCFS：先到达的进程优先分配CPU，用于宏观调度。
• 时间片轮转：分配给每个进程CPU时间片，轮流使用CPU，每个进程时间片大小相同，很公平，用于微观调度。
• 优先级调度：每个进程都拥有一个优先级，优先级大的先分配CPU。
• 多级反馈调度：时间片轮转和优先级调度结合而成，设置多个就绪队列1，2，3.n，每个队列分别赋予不同的优先级，分配不同的时间片长度；新进程先进入队列1的末尾，按FCFS原则，执行队列1的时间片；若未能执行完进程，则转入队列2的末尾，如此重复。 降低优先级

6.死锁

• 当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态，就会造成系统死锁。
• 死锁产生的四个必要条件：资源互斥、每个进程占有资源并等待其他资源、系统不能剥夺进程资源、进程资源图是一个环路。

死锁产生后，解决措施是打破四大条件，有下列方法：

• 死锁预防：采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一，使系统任何时刻都不满足死锁的条件。
• 死锁避免：一般采用银行家算法来避免，银行家算法，就是提前计算出一条不会死锁的资源分配方法，才分配资源，否则不分配资源，相当于借贷，考虑对方还得起才借钱，提前考虑好以后，就可以避免死锁。
• 死锁检测：允许死锁产生，但系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加以解除。
• 死锁解除：即死锁发生后的解除方法，如强制剥夺资源，撤销进程等。
• 死锁资源计算：系统内有n个进程，每个进程都需要R个资源，那么其发生死锁的最大资源数为n * （R-1），其不发生死锁的最小资源数为n * （R-1）+1。

考试真题

• 某系统中有3个并发进程竞争资源R，每个进程都需要5个R，那么至少有（）个R，才能保证系统不会发生死锁。

  A.12 B.13 C.14 D.15

  答案：B解析：每个进程需要5个R才能执存，则当每个进程都只有4个R时是死锁最坏的情况，即3*4=12个资源是死锁发生的最大资源数，再加1就能保证不发生死锁，因此是13.

• 

  答案：B D

• 

  答案：D B

7.线程

• 传统的进程有两个属性：可拥有资源的独立单位；可独立调度和分配的基本单位。
• 引入线程的原因是进程在创建、撤销和切换中，系统必须为之付出较大的时空开销，故在系统中设置的进程数目不宜过多，进程切换的频率不宜太高，这就限制了并发程度的提高。引入线程后，将传统进程的两个基本属性分开，**线程作为调度和分配的基本单位，进程作为独立分配资源的单位。**用户可以通过创建线程来完成任务，以减少程序并发执行时付出的时空开销。
• 线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本一上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈），它可与同属一个进程的其他线程共享进程所拥有的全部资源，例如进程的公共数据、全局变量、代码、文件等资源，但不能共享线程独有的资源，如线程的栈指针等标识数据。

分区存储管理

• 所谓分区存储组织，就是整存，将某进程运行所需的内存整体一起分配给它，然后再执行。有三种分区方式：
• 固定分区：静态分区方法，将主存分为若干个固定的分区，将要运行的作业装配进去，由于分区固定，大小和作业需要的大小不同，会产生内部碎片。
• 可变分区：动态分区方法主存空间的分区是在作业转入时划分，正好划分为作业需要的大小，这样就不存在内部碎片，但容易将整片主存空间切割成许多块，会产生外部碎片。可变分区的算法如下：
  • 可重定位分区：可以解决碎片问题，移动所有已经分配好的区域，使其成为一个连续的区域，这样其他外部细小的分区碎片可以合并为大的分区，满足作业要求。只在外部作业请求空间得不到满足时进行。
  • 系统分配内存的算法有很多，如下图所示，根据分配前的内存情况，还需要分配9K空间，对不同算法的结果介绍如下：
    • 首次适应法：按内存地址顺序从头查找，找到第一个>=9K空间的空闲块，即切割9K空间分配给进程。
    • 最佳适应法：将内存中所有空闲内存块按从小到大排序，找到第一个>=9K空间的空闲块，切割分配，这个将会找到与9K空间大小最相近的空闲块。
    • 最差适应法：和最佳适应法相反，将内存中空闲块空间最大的，切割9K空间分配给进程，这是为了预防系统中产生过多的细小空闲块。
    • 循环首次适应法：按内存地址顺序查找，找到第一个>=9K空间的空闲块，而后若还需分配，则找下一个，不用每次都从头查找，这是与首次适应法不同的地方
    • 

分页存储管理

• 逻辑页分为页号和页内地址，页内地址就是物理偏移地址，而页号与物理块号并非按序对应的，需要查询页表，才能得知页号对应的物理块号，再用物理块号加上偏移地址才得出了真正运行时的物理地址。 优点：利用率高，碎片小，分配及管理简单。缺点：增加了系统开销，可能产生抖动现象厚理

页面置换算法

• 最优算法：OPT，理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。
• 先进先出算法：FIFO，先调入内存的页先被置换淘汰，会产生抖动现象，即分配的页数越多，缺页率可能越多（即效率越低）.
• 最近最少使用：LRU，在最近的过去，进程执行过程中，过去最少使用的页面被置换淘汰，根据局部性原理，这种方式效率高，且不会产生抖动现象，使用大量计数器，但是没有LFU多。
• 淘汰原则：优先淘汰最近未访问的，而后淘汰最近未被修改的页面。

快表

• 是一块小容量的相联存储器，由快速存储器组成**，按内容访问，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。**
• 快表是将页表存于Cache中；慢表是将页表存于内存上。慢表需要访问两次内存才能取出页，而快表是访问一次Cache和一次内存，因此更快。.

考试真题

• 某计算机系统页面大小为4K，若进程的页面变换表如下所示，逻辑地址为十六进制1D16H，该地址经过变换后，其物理地址应为十六进制（）。

  

  A.1024H B.3D16H C.4DI6H D.6D16H

  答案：B

  解析：页面大小为4K，则页内偏移地址为12位，才能表示4大小空间；由此，可知逻辑地址1D16H的低12位D16H为偏移地址，高位1为逻辑丙号，在页表中对应物理块号3，因此物理地址为3D16H。

• 某进程有4个页面，页号为0~3，页面变换表及状态位、访问位和修改位的含义如下图所示，若系统给该进程分配了3个存储块，当访问前页面1不在内存时，淘汰表中页号为（）的页面代价最小。

  

  A.0 B.1 C.2 D.3

  答案：D

  解析：根据局部性原理，应该优先淘汰最近未被访问过的，而后淘汰最近未被修改过的，由页表可知，023最近都被访问过，而只有3最近未被修改过，应该淘汰3。

  然而其实这种题目，就算不知道上述原理，也能做出，答案只有一个，肯定是与其他不同的，具有唯一性的一个，在023中，02的访问位和修改位一样，只有3不同，答案就是3.

分段存储管理

• 将进程空间分为一个个段，每段也有段号和段内地址，与页式存储不同的是，每段物理大小不同，分段是根据逻辑整体分段的，因此，段表也与页表的内容不同，页表中直接是逻辑页号对应物理块号，而下图所示，段表有段长和基址两个属性，才能确定一个逻辑段在物理段中的位置。

  • 优点：多道程序共享内存，各段程序修改互不影响。
  • 缺点：内存利用率低，内存碎片浪费大。

  

考试真题

答案：B

段页式存储管理

• 对进程空间先分段，后分页，具体原理图和优缺点如下：

  • 优点：空间浪费小、存储共享容易、存储保护容易、能动态链接。
  • 缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降。

  

8.设备管理

1.设备管理概述

• 设备是计算机系统与外界交互的工具，具体负责**计算机与外部的输入/输出工作，所以常称为外部设备（简称外设）。**在计算机系统中，将负责管理设备和输入/输出的机构称为I/O系统。因此，I/O系统由设备、控制器、通道（具有通道的计算机系统）、总线和I/O软件组成。
• 设备的分类：
  • 按数据组织分类：块设备、字符设备。
  • 按照设备功能分类：输入设备、输出设备、存储设备、网络联网设备、供电设备。
  • 资源分配角度分类：独占设备、共享设备和虚拟设备。
  • 数据传输速率分类：低速设备、中速设备、高速设备。
• 设备管理的任务是保证在多道程序环境下，**当多个进程竞争使用设备时，按一定的策略分配和管理各种设备，**控制设备的各种操作，完成1/0设备与主存之间的数据交换。
• 设备管理的主要功能是动态地掌握并记录设备的状态、设备分配和释放、缓冲区管理、实现物理1/0设备的操作、提供设备使用的用户接口及设备的访问和控制。

2.I/O软件

• I/O设备管理软件的所有层次及每一层功能如下图：
• 实例：当用户程序试图读一个硬盘文件时，需要通过操作系统实现这一操作。与设备无关软件检查高速缓存中有无要读的数据块，若没有，**则调用设备驱动程序，向I/O硬件发出一个请求。**然后，用户进程阻塞并等待磁盘操作的完成。 **当磁盘操作完成时，硬件产生一个中断，转入中断处理程序。中断处理程序检查中断的原因，认识到这时磁盘读取操作已经完成，于是唤醒用户进程取回从磁盘读取的信息，从而结束此次I/O请求。**用户进程在得到了所需的硬盘文件内容之，后继续运行。

设备管理技术

• 一台独占设备，在同一时间只能由一个进程使用，其他进程只能等待，且不知道什么时候打印机空闲，此时，极大的浪费了外设的工作效率。

• 引入SPOOLING（外围设备联机操作）技术，就是在外设上建立两个数据缓冲区，分别称为输入井和输出井，这样，无论多少进程，都可以共用这一台打印机，只需要将打印命令发出，数据就会排队存储在缓冲区中，打印机会自动按顺序打印，实现了物理外设的共享，使得**每个进程都感觉在使用一个打印机，这就是物理设备的虚拟化。**如下图所示：

  

考试真题

• 以下关于/0软件的叙述中，正确的是（）

  A、I/O软件开放了I/O操作实现的细节，方便用户使用I/O设备

  B、I/O软件隐藏了I/O操作实现的细节，向用户提供物理接口

  C、I/O软件隐藏了I/O操作实现的细节，方便用户使用I/O设备

  D、I/O软件开放了I/O操作实现的细节，用户可以使用逻辑地址访问I/O设备

  答案: C

文件管理概述

• 文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。

• 信息项是构成文件内容的基本单位，可以是一个字符，也可以是一个记录，记录可以等长，也可以不等长。一个文件包括**文件体和文件说明。**文件体是文件真实的内容。文件说明是操作系统为了管理文件所用到的信息，包括文件名、文件内部标识、文件的类型、文件存储地址、文件的长度、访问权限、建立时间和访问时间等。

• 文件管理系统，就是**操作系统中实现文件统一管理的一组软件和相关数据的集合，专门负责管理和存取文件信息的软件机构，**简称文件系统。文件系统的功能包括按名存取；统一的用户接口；并发访问和控制；安全性控制；优化性能；差错恢复。

• 文件的类型： （1）按文件性质和用途可将文件分为系统文件、库文件和用户文件。 （2）按信息保存期限分类可将文件分为临时文件、档案文件和永久文件。 （3）按文件的保护方式分类可将文件分为只读文件、读/写文件、可执行文件和不保护文件。 （4）UNIX系统将文件分为普通文件、目录文件和设备文件（特殊文件）。

• 文件的逻辑结构可分为两大类：有结构的记录式文件；无结构的流式文件。

• 文件的物理结构是指文件在物理存储设备上的存放方法，包括：

  （1）连续结构。连续结构也称顺序结构，它将逻辑上连续的文件信息（如记录）依次存放在连续编号的物理块上。 （2）链接结构。链接结构也称串联结构，它是将逻辑上连续的文件信息（如记录）存放在不连续的物理块上，每个物理块设有一个指针指向下一个物理块。 （3）索引结构。将**逻辑上连续的文件信息（如记录）存放在不连续的物理块中，**系统为每个文件建立一张索引表。**索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录项中。 （4）多个物理块的索引表。索引表是在文件创建时由系统自动建立的，**并与文件一起存放在同一文件卷上。根据一个文件大小的不同，其索引表占用物理块的个数不等，一般占一个或几个物理块。

• 如图所示，系统中有13个索引节点，0-9**为直接索引，即每个索引节点存放的是内容，**假设每个物理盘大小为4KB，共可存4KB * 10=10KB数据；
• 10号索引节点**为一级间接索引节点，大小为4KB，存放的并非直接数据，而是链接到直接物理盘块的地址，**假设每个地址占4B，则共有1024个地址，对应1024个物理盘，可存1024 * 4KB=4098KB数据。
• **二级索引节点类似，直接盘存放一级地址，一级地址再存放物理盘快地址，而后链接到存放数据的物理盘块，**容量又扩大了一个数量级，为1024 * 1024 * 4KB数据。

考试真题

• 设文件索引节点中有8个地址项，每个地址项大小为4字节，其中5个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，磁盘索引块和磁盘数据块大小均为1KB，若要访问文件的逻辑块号分别为5和518，则系统应分别采用（），而且可表示的单个文件最大长度是（）KB。

  A、直接地址索引和一级间接地址索引 B、直接地址索引和二级间接地址索引 C、一级间接地址索引和二级间接地址索引 D、一级间接地址索引和一级间接地址索引

  A、517 B、1029 C、16513 D、66053

  答案：CD 解析：依题意，有5个地址项为直接地址索引，所以直接地址索引涉及到的逻辑块号为：0-4。2个地址项为一级间接索引，每个一级间接索引结点对应的逻辑块个数为：1KB/4B-256个。所以一级间接索引涉及到的逻辑块号为：5-516。二级间接索引所对应的逻辑块号即为：517以上。可表示的单个文件长度，首先计算直接地址索引，就是5个数据块，为5KB，而后一级间接地址索引，可表示256个数据块，即256KB，二级间接地址索引可存储1KB/4B=256个一级间接地址索引，每个一级间接地址索引又可存储256KB，因此是256 * 256KB，全部加起来共5+256 * 2+256 * 256=66053

文件目录

• 文件控制块中包含以下三类信息：基本信息类、存取控制信息类和使用信息类。 （1）基本信息类。例如文件名、文件的物理地址、文件长度和文件块数等。 （2）存取控制信息类。文件的存取权限，像UNIX用户分成文件主、同组用户和一般用户三类，这三类用户的读/写执行RWX权限。 （3）使用信息类。文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的信息（如打开文件的进程数、在文件上的等待队列）等。
  • 文件控制块的有序集合称为文件目录。
  • 相对路径：是从当前路径开始的路径。
  • 绝对路径：是从根目录开始的路径。
  • 全文件名=绝对路径+文件名。要注意，绝对路径和相对路径是不加最后的文件名的，只是单纯的路径序列。

考试真题

答案：D B

文件存储空间管理

• 文件的存取方法是指读/写文件存储器上的一个物理块的方法。通常有顺序存取和随机存取两种方法。顺序存取方法是指对文件中的信息按顺序依次进行读/写；随机存取方法是指对文件中的信息可以按任意的次序随机地读/写。

• 文件存储空间的管理： （1）空闲区表。将外存空间上的一个连续的未分配区域称为“空闲区”。操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区，适用于连续文件结构。

  

  （2）（位示图这种方法是在外存上建立一张位示图（Bitmap），记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。

  

  （3）空闲块链。每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，链表的头指针放在文件存储器的特定位置上（如管理块中），不需要磁盘分配表，节省空间。 （4）成组链接法。例如，在实现时系统将空闲块分成若干组，每100个空闲块为一组，每组的第一个空闲块登记了下一组空闲块的物理盘块号和空闲块总数。一假如某个组的第一个空闲块号等于0，意味着该组是最后一组，无下一组空闲块。

考试真题

• 某文件管理系统采用位示图（bitmap）记录磁盘的使用情况。如果系统的字长为32位，磁盘物理块的大小为4MB，物理块依次编号为：0、1、2、...，位示图字依次编号为：0、1、2、.，那么16385号物理块的使用情况在位示图中的第（25）个字中描述：如果磁盘的容量为1000GB，那么位示图需要（26）个字来表示。

  (25)A、 -128 B、 256 C、512 D、1024 (26)A、 1200 B、3200 C、6400 D、 8000

  答案 ： C D

第三章、数据库技术基础

1.数据库系统

• 数据：是数据库中存储的基本对象，是描述事物的符号记录。

• 数据的种类：文本、图形、图像、音频、视频、学生的档案记录、货物的运输情况等。

• 数据库DB：是长期存储在计算机内、有组织的、可共享的大量数据的集合。

• 数据库的基本特征：数据按一定的数据模型组织、描述和存储；可为各种用户共享；冗余度较小；数据独立性较高；易扩展。

• 数据库系统DBS：是一个采用了数据库技术，有组织地、动态地存储大量相关一数据，方便多用户访问的计算机系统。其由下面四个部分组成：数据库（统一管理、长期存储在计算机内的，有组织的相关数据的集合） 硬件（构成计算机系统包括存储数据所需的外部设备） 软件（操作系统、数据库管理系统及应用程序） 人员（系统分析和数据库设计人员、应用程序员、最终用户、数据库管理员DBA）

• 数据库管理系统DBMS的功能 实现对共享数据有效的组织、管理和存取。 包括数据定义、数据库操作、数据库运行管理、数据的存储管理、数据库的建立和维护等。

2.三级模式-两级映像

• 内模式：管理如何存储物理的数据，对应具体物理存储文件。
• 概念模式：又称为概念模式，就是我们通常使用的基本表，根据应用、需求将物理数据划分成一张张表。
• 外模式：对应数据库中的视图这个级别，将表进行一定的处理后再提供给用户使用
• 外模式一模式映像：是表和视图之间的映射，存在于概念级和外部级之间，若表中数据发生了修改，只需要修改此映射，而无需修改应用程序。
• 概念模式一内模式映像：是表和数据的物理存储之间的映射，存在于概念级和内部级之间，若修改了数据存储方式，只需要修改此映射，而不需要去修改应用程序。

3.数据库设计

• 需求分析：即分析数据存储的要求，产出物有数据流图、数据字典、需求说明书。
• 概念结构设计：就是设计E-R图，也即实体-联系图，与物理实现无关，说明有哪些实体，实体有哪些属性。
• 逻辑结构设计：**将E-R图，转换成关系模式，**也即转换成实际的表和表中的列属性，这里要考虑很多规范化的东西。
• 物理设计：根据生成的表等概念，生成物理数据库。

考试真题

• 在数据库系统中，数据库的视图、基本表和存储文件的结构分别与（）对应；数据的物理独立性和数据的逻辑独立性是分别通过修改（）来完成的。 A.模式、外模式、内模式 B.模式、内模式、外模式 C.外模式、模式、内模式 D.外模式、内模式、模式

  A.模式与内模式之间的映像、外模式与模式之间的映像

  B.外模式与内模式之间的映像、外模式与模式之间的映像

  C.外模式与模式之间的映像、模式与内模式之间的映像

  D.外模式与内模式之间的映像、模式与内模式之间的映像

  答案：C A

• 在数据库逻辑结构设计阶段，需要（）阶段形成的（）作为设计依据。

  A.需求分析 B.概念结构设计 C.物理结构设计 D.数据库运行和维护

  A.程序文档、数据字典和数据流图。

  B.需求说明文档、程序文档和数据流图

  C.需求说明文档、数据字典和数据流图

  D.需求说明文档、数据字典和程序文档

  答案：A C

4.数据模型

• 关系模型是二维表的形式表示的实体-联系模型，是将实体-联系模型转换而来的，经过开发人员设计的；

• 概念模型是从用户的角度进行建模的，是现实世界到信息世界的第一抽象，是真正的实体-联系模型。

• 网状模型表示实体类型及其实体之间的联系，一个事物和另外几个都有联系，形成一张网。

• 面向对象模型是采用面向对象的方法设计数据库，以对象为单位，每个对象包括属性和方法，具有类和继承等特点。

• 数据模型三要素：数据结构（所研究的对象类型的集合）、数据操作（对数据库中各种对象的实例允许执行的操作的集合）、数据的约束条件（一组完整性规则的集合）。

• 用E-R图来描述概念数据模型，世界是由一组称作实体的基本对象和这些对象之间的联系构成的。

• 在E-R模型中，使用**椭圆表示属性（一般没有）、长方形表示实体、菱形表示联系，联系的两端要填写联系类型，**示例如下图：

  

• 实体：**客观存在并可相互区别的事物。**可以是具体的人、事、物或抽象概念。如人、汽车、图书、账户、贷款。

• 弱实体和强实体：弱实体依赖于强实体的存在而存在。

• 实体集：具有相同类型和共享相同属性的实体的集合，如学生、课程。

• 属性：实体所具有的特性。

• 属性分类：简单属性和复合属性；单值属性和多值属性；NULL属性；派生属性。

• 域：属性的取值范围称为该属性的域。

• 码（key）：唯一标识实体的属性集。

• 联系：现实世界中事物内部以及事物之间的联系，在E-R图中反映为实体内部的联系和实体之间的联系。

• 联系类型：一对一1：1、一对多1：N、多对多M:N。

• 两个以上实体型的联系：

​ 两个以上实体型间1：n联系 两个以上实体型间m:n联系

• 关系模型中数据的逻辑结构是一张二维表，由行列组成。用表格结构表达实体集，用外键标识实体间的联系。如下图：

  

• 优点：建立在严格的数学概念基础上；概念单一、结构简单、清晰，用户易懂易用；存取路径对用户透明，从而数据独立性、安全性好，简化数据库开发工作。

• 缺点：由于存取路径透明，查询效率往往不如非关系数据模型。

• E-R模型转换为关系模型：每个实体都对应一个关系模式；联系分为三种：

  1：1联系中，联系可以放到任意的两端实体中，作为一个属性（要保证1：1的两端关联），也可以转换为一个单独的关系模式；

  1：N的联系中，联系可以单独作为一个关系模式，也可以在N端中加入1端实体的主键；

  M:N的联系中，联系必须作为一个单独的关系模式，其主键是M和N端的联合主键。

考试真题

• 某本科高校新建教务管理系统，支撑各学院正常的教学教务管理工作。经过初步分析，系统中包含的实体有学院、教师、学生、课程等。考虑需要将本科学生的考试成绩及时通报给学生家长，新增家长实体；考虑到夜大、网络教育学生管理方式的不同，需要额外的管理数据，新增进修学生实体：规定一个学生可以选择多门课程，每门课程可以被多名学生选修；一个教师可以教授多门课程，一门课程只能被一名教师讲授。（）实体之间为多对多联系，（）属于弱实体对强实体的依赖联系。

  A、学生、学院 B、教师、学院 C、学生、课程 D、教师、课程 A、家长、学生 B、学生、教师 C、学生、学院 D、教师、学院

  答案 C A

• 54-56·部门、员工和项目的关系模式及它们之间的E-R图如下所示，其中关系模式中带实下划线的属性表示主键属性。图中： 部门（部门代码，部门名称，电话） 员工（员工代码，姓名，部门代码，联系方式，薪资） 项目（项目编号，项目名称，承担任务）

  

  若部门和员工关系进行自然连接运算，其结果为（54）元关系。由于员工和项目之间的联系类型为（55），所以员工和项目之间的联系需要转换成一个独立的关系模式，该关系模式的主键是（56）

  （54）A、5 B、6 C、7 D、8 （55）A、1对1 B、1对多 C、多对1 D、多对多 （56）A、（项目名称，员工代码） B、（项目编号，员工代码）

  ​ C、（项目名称，部门代码） D、（项目名称，承担任务）

  答案：C D B

5.关系代数

• 并：结果是两张表中所有记录数合并，相同记录只显示一次。

• 交：结果是两张表中相同的记录。

• 差：S1-52，结果是S1表中有而S2表中没有的那些记录。

  

  • 笛卡尔积：S1 * S2，产生的结果包括s1和S2的所有属性列，并且S1中每条记录依次和S2中所有记录组合成一条记录，最终属性列为S1+S2属性列，记录数为S1 * S2记录数。
  • 投影：实际是按条件选择某关系模式中的某列，列也可以用数字表示。
  • 选择：实际是按条件选择某关系模式中的某条记录。

  

• 自然连接的结果显示全部的属性列，但是相同属性列只显示一次，显示两个关系模式中属性相同且值相同的记录。

• 设有关系R、S如下左图所示，自然连接结果如下右图所示：

  

考试真题

答案 B D

函数依赖

1.函数依赖

• 给定一个x，能唯一确定一个Y，就称X确定Y，或者说Y依赖于x，例如Y=X*X函数。

• 函数依赖又可扩展以下两种规则：

  • 部分函数依赖：**A可确定C，（A，B）也可确定C，（A，B）中的一部分（即A）可以确定C，**称为部分函数依赖。
  • 传递函数依赖：**当A和B不等价时，A可确定B，B可确定C，则A可确定C，**是传递函数依赖；若A和B等价，则不存在传递，直接就可确定C。

  

2.键与约束

• 超键：能唯一标识此表的属性的组合。
• 候选键：超键中**去掉冗余的属性，**剩余的属性就是候选键。
• 主键：任选一个候选键，即可作为主键。
• 外键：其他表中的主键。
• 主属性：**候选键内的属性为主属性，**其他属性为非主属性。
• 实体完整性约束：即主键约束，主键值不能为空，也不能重复。
• 参照完整性约束：即外键约束，外键必须是其他表中已经存在的主键的值，或者为空。
• 用户自定义完整性约束：自定义表达式约束，如设定年龄属性的值必须在0到150之间。

3.范式

• 第一范式1NF

  **关系中的每一个分量必须是一个不可分的数据项。**通俗地说，第一范式就是表中不允许有小表的存在。比如，对于如下的员工表，就不属于第一范式：

  

• 实例：用一个单一的关系模式学生来描述学校的教务系统：学生（学号，学生姓名，系号，系主任姓名，课程号，成绩）

• 依赖关系（学号->学生姓名，学号->系号，所在系->系主任姓名，学号->课程号，（学号，课程号）->成绩）

  

• 第二范式 如果关系R属于1NF，且每一个非主属性完全函数依赖于任何一个候选码，则R属于2NF。 通俗地说，2NF就是在1NF的基础上，表中的每一个非主属性不会依赖复合主键中的某一个列。 按照定义，上面的学生表就不满足2NF，因为学号不能完全确定课程号和成绩（每个学生可以选多门课）。

• 将学生表分解为： 学生（学号，学生姓名，系编号，系名，系主任） 选课（学号，课程号，成绩）。 每张表均属于2NF。

• 第三范式 在满足1NF的基础上，表中不存在非主属性对码的传递依赖。 继续上面的实例，学生关系模式就不属于3NF，因为学生无法直接决定系主任和系名，是由学号->系编号，再由系编号->系主任，系编号->系名，因此存在非主属性对主属性的传递依赖，

• 将学生表进一步分解为：

  学生（学号，学生姓名，系编号） 系（系编号，系名，系主任）

  选课（学号，课程号，成绩） 每张表都属于3NF。

• BC范式BCNF，是指在第三范式的基础上进一步消除主属性对于码的部分函数依赖和传递依赖。

• 通俗的来说，就是在每一种情况下，每一个依赖的左边决定因素都必然包含候选键，如下：

  

• 上图中，候选键有两种情况：组合键（S，T）或者（S，J），依赖集为{SJ-T，T一J}，可知，STJ三个属性都是主属性，因此其达到了3NF（无非主属性），然而，第二种情况，即（S，J）为候选键的时候，对于依赖T->J，T在这种情况不是候选键，即T-J的决定因素不包含任意候选码，因此上图不是BCNF。

• 要使上图关系模式转换为BCNF也很简单，只需要将依赖T->J变为TS->J即可，这样其左边决定因素就包含了候选键之一S。

考试真题

• 给定关系模式R（U，F），U={A，B，C，D}，F={AB→C，CD→B）。关系R（），且分别有（）。

  A、只有1个候选关键字ACB B、只有1个候选关键字BCD

  C、有2个候选关键字ACD和ABD D、有2个候选关键字ACB和BCD

  A、0个非主属性和4个主属性 B、1个非主属性和3个主属性

  C、2个非主属性和2个主属性 D、3个非主属性和1个主属性

  候选关键字的求法：根据依赖集，**找出从未在右边出现过的属性，**必然是候选键之一，纵该属性为基础，根据依赖集依次扩展，看能否遍历所有属性，将无法遍历的加入候选键中。

  答案：C A

• 设有关系模式R（E，N，M，L，Q），其函数依赖集为F={E→N，EM→Q，M→L）。则关系模式R达到了（）；该关系模式（）。 A、1NF B、2NF C、3NF D、BCNF

  A、无需进行分解，因为已经达到了3NF B、无需进行分解，因为已经达到了BCNF

  C、尽管不存在部分函数依赖，但还存在传递依赖，所以需要进行分解

  D、需要进行分解，因为存在冗余、修改操作的不一致性、插入和删除异常

  答案：A D

4.模式分解

• 范式之间的转换一般都是通过拆分属性，即模式分解，将具有部分函数依赖和传递依赖的属性分离出来，来达到一步步优化，一般分为以下两种：

• 保持函数依赖分解 对于关系模式R，有依赖集F，若对R进行分解，**分解出来的多个关系模式，保持原来的依赖集不变，**则为保持函数依赖的分解。另外，注意要消除掉冗余依赖（如传递依赖）。

• 实例：设原关系模式R（A，B，C），依赖集F（A->B，B->C，A->C），将其分解为两个关系模式R1（A，B）和R2（B，C），此时R1中保持依赖A->B，R2保持依赖B->C，说明分解后的R1和R2是保持函数依赖的分解，因为A->C这个函数依赖实际是一个冗余依赖，可以由前两个依赖传递得到，因此不需要管。

• 保持函数依赖的判断（补充，第2点不强求）： 1、如果F上的每一个函数依赖都在其分解后的某一个关系上成立，则这个分解是保持依赖的（这是一个充分条件）。也即我们课堂上说的简单方法，看函数每个依赖的左右两边属性是否都在同一个分解的模式中。 2、如果上述判断失败，并不能断言分解不是保持依赖的，还要使用下面的通用方法来做进一步判断。 该方法的表述如下： 算法二： 对F上的每一个α→β使用下面的过程：

  result：=α；

  while（result发生变化）do

  for each 分解后的Ri t=（result ∩ Ri）+ ∩Ri

  result=result ∪ t

• 案例：假设关系模式R（U，F），属性集U={A，B，C），函数依赖集F={A→B，B→C）。若

  将其分解为p={R1（U1，F1），R2（U2，F2）），其中U1={A，B），U2={A，C）。那么，分解p（）。

  A.有损连接但保持函数依赖

  B.既无损连接又保持函数依赖

  C.有损连接且不保持函数依赖

  D.无损连接但不保持函数依赖 答案：D

  解析：首先，该分解，U1保持了依赖A→B，然而B→C没有保持，因此针对B→C需要用第2点算法来判断： result=B，result ∩ U1=B，B+=BC，BC ∩ U1=B，result=B ∪ B=B，result没变，然后，result再和U2交是空，结束了，不保持函数依赖。 注意，这里B+，+的意思是代表由B能够推导出的其他所有属性的集合，这里，B→C，因此B+ = BC。

• 无损分解：分解后的关系模式能够还原出原关系模式，就是无损分解，不能还原就是有损。

• 当分解为两个关系模式，可以通过以下定理判断是否无损分解： 定理：如果R的分解为p={R1，R2），F为R所满足的函数依赖集合，分解p具有无损连接性的充分必要条件是R1nR2->（R1-R2）或者R10R2->（R2-R1）。

• 当分解为三个及以上关系模式时，可以通过表格法求解，如下：

  

考试真题

• 给定关系模式R<U，F>，U={A，B，C，D，E}，F={B→A，D→A，A→E，AC→B}，则 R 的候选关键字为（），分解p={ R1（ABCE），R2（CD）}（）。 A、CD B、ABD C、ACD D、ADE

  A.具有无损连接性，且保持函数依赖

  B.不具有无损连接性，但保持函数依赖

  C.具有无损连接性，但不保持函数依赖

  D.不具有无损连接性，也不保持函数依赖

  答案：AD

5.并发控制

• 事务：由一系列操作组成，这些操作，要么全做，要么全不做，拥有四种特性，详解如下： 原子性：要么全做，要么全不做。 一致性：事务发生后数据是一致的，例如银行转账，不会存在A账户转出，但是8账户没收到的情况。 隔离性：任一事务的更新操作直到其成功提交的整个过程对其他事务都是不可见的，不同事务之间是隔离的，互不干涉。 持续性：事务操作的结果是持续性的。

• 事务是并发控制的前提条件，并发控制就是控制不同的事务并发执行，提高系统效率，但是并发控制中存在下面三个问题：

  • 丢失更新：事务1对数据A进行了修改并写回，事务2也对A进行了修改并写回，此时事务2写回的数据会覆盖事务1写回的数据，就丢失了事务1对A的更新。即对数据A的更新会被覆盖。
  • 不可重复读：事务2读A，而后事务1对数据A进行了修改并写回，此时若事务2再读A，发现数据不对。即一个事务重复读A两次，会发现数据A有误。
  • 读脏数据：事务1对数据A进行了修改后，事务2读数据A，而后事务1回滚，数据A恢复了原来的值，那么事务2对数据A做的事是无效的，读到了脏数据。

  

6.封锁协议

• x锁是排它锁（写锁）。若事务T对数据对象A加上X锁，则只允许T读取和修改A，**其他事务都不能再对A加任何类型的锁，**直到T释放A上的锁。

• S锁是共享锁（读锁）。若事务T对数据对象A加上S锁，则只允许T读取A，但不能修改A，**其他事务只能再对A加S锁（也即能读不能修改），**直到T释放A上的S锁。

• 共分为三级封锁协议，如下：

• 一级封锁协议：事务在修改数据R之前必须先对其加X锁，直到事务结束才释放。可解决丢失更新问题。

  

• 二级封锁协议：一级封锁协议的基础上加上事务T在**读数据R之前必须先对其加S锁，读完后即可释放S锁。**可解决丢失更新、读脏数据问题。

  

• 三级封锁协议：一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。可解决丢失更新、读脏数据、数据重复读问题。

  

考试真题

• "当多个事务并发执行时，任一事务的更新操作直到其成功提交的整个过程对其他事务都是不可见的"，这一性质通常被称为事务的（C）。 A、原子性

  B、一致性

  C、隔离性

  D、持久性

  答案：C

• 若事务T1对数据D1加了共享锁，事务T2、T3分别对数据D2、D3加了排它锁，则事务T1对数据（）；事务T2对数据（ ） A、D2、D3加排它锁都成功 B、D2、D3 加共享锁都成功 C、D2加共享锁成功，D3加排它锁失败 D、D2、D3加排它锁和共享锁都失败 A、D1、D3加共享锁都失败 B、D1、D3加共享锁都成功 C、D1加共享锁成功，D3加排它锁失败 D、D1加排它锁成功，D3加共享锁失败

  答案：D C

数据库新技术

1.数据库安全

• 静态转储：即冷备份，指在转储期间不允许对数据库进行任何存取、修改操作；

  • 优点是非常快速的备份方法、容易归档（直接物理复制操作）；
  • 缺点是只能提供到某一时间点上的恢复，不能做其他工作，不能按表或按用户恢复。

• 动态转储：即热备份，在转储期间允许对数据库进行存取、修改操作，因此，转储和用户事务可并发执行

  • 优点是可在表空间或数据库文件级备份，数据库扔可使用，可达到秒级恢复；
  • 缺点是不能出错，否则后果严重，若热备份不成功，所得结果几乎全部无效。

• 完全备份：备份所有数据。

• 差量备份：仅备份上一次完全备份之后变化的数据。

• 增量备份：备份上一次备份之后变化的数据。

• 日志文件：在事务处理过程中，DBMS把事务开始、事务结束以及对数据库的插入、删除和修改的每一次操作写入日志文件。一旦发生故障，DBMS的恢复子系统利用日志文件撤销事务对数据库的改变，回退到事务的初始状态。

2.分布式数据库

• 局部数据库位于不同的物理位置，使用一个全局DBMS将所有局部数据库联网管理，这就是分布式数据库。

• 分片模式

  • 水平分片：将表中水平的记录分别存放在不同的地方。
  • 垂直分片：将表中的垂直的列值分别存放在不同的地方。

• 分布透明性

  • 分片透明性：用户或应用程序不需要知道逻辑上访问的表具体是如何分块存储的。
  • 位置透明性：应用程序不关心数据存储物理位置的改变。
  • 逻辑透明性：用户或应用程序无需知道局部使用的是哪种数据模型。
  • 复制透明性：用户或应用程序不关心复制的数据从何而来。

  

3.数据仓库技术

• 数据仓库是一个面向主题的、集成的、非易失的、且随时间变化的数据集合，用于支持管理决策。

  • 面向主题：按照一定的主题域进行组织的。
  • 集成的：数据仓库中的数据是在对原有分散的数据库数据抽取、清理的基础上经过系统加工、汇总和整理得到的，必须消除源数据中的不一致性，以保证数据仓库内的信息是关于整个企业的一致的全局信息。
  • 相对稳定的：数据仓库的数据主要供企业决策分析之用，所涉及的数据操作主要是数据查询，一旦某个数据进入数据仓库以后，一般情况下将被长期保留，也就是数据仓库中一般有大量的查询操作，但修改和删除操作很少，通常只需要定期的加载、刷新。
  • 反映历史变化：数据仓库中的数据通常包含历史信息，系统记录了企业从过去某一时点（如开始应用数据仓库的时点）到目前的各个阶段的信息，通过这些信息，可以对企业的发展历程和未来趋势做出定量分析和预测。

• 数据仓库的结构通常包含四个层次，如下图所示：

  • 1.数据源：是数据仓库系统的基础，是整个系统的数据源泉。
  • 2.数据的存储与管理：是整个数据仓库系统的核心。
  • 3.OLAP（联机分析处理）服务器：对分析需要的数据进行有效集成，按多维模型组织，以便进行多角度、多层次的分析，并发现趋势。
  • 4.前端工具：主要包括各种报表工具、查询工具、数据分析工具、数据挖掘工具以及各种基于数据仓库或数据集市的应用开发工具。

  

商业智能.

• BI系统主要包括数据预处理、建立数据仓库、数据分析和数据展现四个主要阶段。
• 数据预处理是整合企业原始数据的第一步，它包括数据的抽取（Extraction）、转换（Transformation）和加载（Load）三个过程（ETL过程）；
• 建立数据仓库则是处理海量数据的基础；
• 数据分析是体现系统智能的关键，一般采用联机分析处理（OLAP）和数据挖掘两大技术。联机分析处理不仅进行数据汇总/聚集，同时还提供切片、切块、下钻、上卷和旋转等数据分析功能，用户可以方便地对海量数据进行多维分析。数据挖掘的目标则是挖掘数据背后隐藏的知识，通过关联分析、聚类和分类等方法建立分析模型，预测企业未来发展趋势和将要面临的问题；
• 在海量数据和分析手段增多的情况下，数据展现则主要保障系统分析结果的可视化。

4.反规范化技术

• 反规范化技术：规范化设计后，数据库设计者希望牺牲部分规范化来提高性能。

• 采用反规范化技术的益处：降低连接操作的需求、降低外码和索引的数目，还可能减少表的数目，能够提高查询效率。

• 可能带来的问题：数据的重复存储，浪费了磁盘空间；可能出现数据的完整性问题，为了保障数据的一致性，增加了数据维护的复杂性，会降低修改速度。 具体方法： （1）增加冗余列：在多个表中保留相同的列，通过增加数据冗余减少或避免查询时的连接操作。 （2）增加派生列：在表中增加可以由本表或其它表中数据计算生成的列，减少查询时的连接操作并避免计算或使用集合函数。 （3）重新组表：如果许多用户需要查看两个表连接出来的结果数据，则把这两个表重新组成一个表来减少连接而提高性能。 （4）水平分割表：根据一列或多列数据的值，把数据放到多个独立的表中，主要用于表数据规模很大、表中数据相对独立或数据需要存放到多个介质上时使用。

  （5）垂直分割表：对表进行分割，将主键与部分列放到一个表中，主键与其它列放到另一个表中，在查询时减少I/O次数。

5.大数据

• 特点：大量化、多样化、价值密度低、快速化。

• 大数据和传统数据的比较如下：

  

• 要处理大数据，一般使用集群平台，称为大数据处理系统，其特征为：

• 高度可扩展性、高性能、高度容错、支持异构环境、较短的分析延迟、易用且开放的接口、较低成本、向下兼容性。

考试真题

• 为了保证数据库中数据的安全可靠和正确有效，系统在进行事务处理时，对数据的插入、删除或修改的全部有关内容先写入（）；当系统正常运行时，按一定的时间间隔，把数据库缓冲区内容写入（）；当发生故障时，根据现场数据内容及相关文件来恢复系统的状态。 A.索引文件 B.数据文件 C.日志文件 D.数据字典 A.索引文件 B.数据文件 C.日志文件 D.数据字典

  答案：C B

• 数据仓库中数据（）的特点是指数据一旦进入数据仓库后，将被长期保留并定期加载和刷新，可以进行各种查询操作，但很少对数据进行修改和删除操作。

  A.面向主题 B.集成性 C.相对稳定性 D.反映历史变化

  答案：C

6.SQL语言

• SQL语言中的语法关键字，不区分大小写：
• 创建表create table；
• 指定主键primary key（）；
• 指定外键foreign key（）；
• 修改表alter table；
• 删除表drop table；
• 索引index；
• 视图view；

考试真题

• 某销售公司数据库的零件关系P（零件号，零件名称，供应商，供应商所在地，库存量），函数依赖集F={零件号→零件名称，（零件号，供应商）→库存量，供应商→供应商所在地）。零件关系P属于（）。查询各种零件的平均库存量、最多库存量与最少库存量之间差值的SOL语句如下：SELECT 零件号，() FROM P ()

  A.1NF B.2NF C.3NF D.4NF A.AVG（库存量）AS平均库存量，MAX（库存量）-MIN库存量）AS差值

  B.平均库存量AS AVG（库存量），差值AS MAX（库存量）-MIN（库存量）

  C.AVG库存量AS平均库存量，MAX库存量-MIN库存量AS差值

  D.平均库存量AS AVG库存量，差值AS MAX库存量-MIN库存量

  A.ORDER BY 供应商 B.ORDER BY 零件号

  C.GROUP BY 供应商 D.GROUP BY 零件号

  答案： A A D

  

  答案：C A D B