第一章 计算机组成原理与体系结构
- 数据的表示
- 计算机结构
- Flynn分类法
- CISC与RISC
- 流水线技术
- 存储系统
- 总线系统
- 可靠性
- 校验码
1-1 数据的表示
1-1-1 数据的表示
R进制转十进制使用按权展开法
具体操作方式 :将R进制数的每一位数值用R的k次方形式表示
当该位位于小数点右边,k值是负值,其绝对值是该位和小数点之间数码的个数+1
- 十进制转R进制使用短除法(例如: 将94 转换为二进制数)
- 二进制转八进制与十六进制数
1-1-2 数据的表示—原码,反码,补码,移码
移码— 用来浮点运算中的接码
数值的取值范围 (27 = 128)
··· 整数 原码 -(2n-1 - 1) ~ 2n-1-1 【8个位,一个字节码,表示范围(-127-127)】 反码 -(2n-1 - 1) ~ 2n-1-1 补码 -2n-1 - 1 ~ 2n-1-1
1-1-3 数据的表示—浮点数运算
- 浮点数表示:N = M*Re(1000 = 1X103)
- 其中M称为尾数,e是指数, R为基数。
- 对阶 ——-> 尾数计算 ————> 结果格式化
1-2 计算机结构
1-2-1
- 主机包含 : 主存储器和CPU
- CPU包含 运算器和控制器
- 运算器:
- 算术逻辑单元ALU
- 累加寄存器AC
- 数据缓冲寄存器DR :
- 状态条件寄存器PSW :
- 控制器:
- 程序计数器PC
- 指令寄存器IR
- 指令译码器
- 时序部件
- 运算器:
1-2-2 计算机体系结构分类
体系结构类型 结构 关键特性 代表 单指令流单数据流SISD 控制部分 : 一个
处理器 : 一个
主存模块: 一个单处理器系统 单指令流多数据流SIMD 控制部分 : 一个
处理器 : 多个
主存模块: 多个个处理器以异步的形式执行同一条指令 并行处理机
阵列处理机
超级向量处理机多指令流单数据流MISD 控制部分 : 多个
处理器 : 一个
主存模块: 多个不实际 有文献称流水线计算机为此类 多指令流多数据流MIMD 控制部分 : 多个
处理器 : 多个
主存模块: 多个能够实现作业、任务、指令等各级全面并行 多处理机系统
多计算机CISC与RISC
指令系统类型 指令 寻址方式 实现方式 其它 CISC(复杂) 数量多,使用频率差别大 支持多种 微程序控制技术(微码) 研制周期长 RISC(精简) 数量少,使用频率接近定长格式,大部分为单周期指令,操作寄存器,只有Load/Store操作内存 支持方式少 增加了通用寄存器,硬布线逻辑控制为主,适合采用流水线 优化编译,有效支持高级 语言
1-2-3 流水线(!!!!!)
概念: 流水线是指在程序执行时 多条指令重叠进行操作 的一种准并行处理实现技术。
- 各种部件同时处理是针对不同指令而言的
- 他们可同时为多条指令的不同部分进行工作,以提高各部件的利用率和指令的平均执行速度
流水线计算
- 取指 —> 分析 —-> 执行
流水线周期为执行最长得一段
流水线计算公式:
一条指令执行时间+(指令条数 - 1)*流水线周期
理论公式 :(t1+t2+…+tk)+(n-1)*▲t
实践公式 :(k+n-1)*▲t
1-2-4 流水线吞吐率计算
流水线得吞吐率(Though Put rate, TP)是指在单位时间内流水线所完成的任务数量或输出的结果数量。计算流水线吞吐率的最基本的公式:
TP = 指令条数/流水线执行时间
流水线最大吞吐率 :
1-2-5 流水线的加速比(加速比越高越好)
加速比定义: 完成同样一批任务 ,不使用流水线的时间与使用流水线的 时间的比值
计算流水线加速比的基本公式:
S = 不使用流水线执行时间/使用流水线执行时间
例子:
流水线的效率:
流水线的效率是指流水线的设备利用率。在时空图上,流水线的效率定义为n个任务占用的时空区与k个流水段总的时空区之比
计算流水线效率的公式为:
E = n个任务占用的时空区/ k个流水段的总的时空区 = T0/kTk
1-2-6 计算机层次化存储结构
- Cache : 性价比方案,提高速度的同时(成本没有增加多少);并且按内容存取
- Cache 的功能 : 提高CPU数据输入输出的速率,突破冯诺伊曼 瓶颈,即CPU与存储系统间数据传送带宽限制
- 在计算机的存储系统体系中,Cache是访问速度最快的层次
- 使用Cache改善系统性能的依据是程序的局部性原理
1-2-7 局部性原理与空间局部性
- 时间局部性
- 空间局部性
- 工作集理论: 工作集是进程运行时被频繁访问的页面集合
1-2-7 随机存储器与只读存储器 — 主存
随机存取存储器
- DRAM(Dynamic RAM ,动态RAM) - SDRAM
- SRAM(Static RAM , 静态)
只读存储器
- MROM(Mask ROM, 掩模式ROM)
- PROM(Programmable ROM,一次可编程ROM)
- EPROM(Erasable PROM,可擦除的PROM)
- 闪速存储器(flash memory , 内存)
主存— 编址
1-2-8 磁盘结构与参数
- 存取时间 = 寻道时间 + 等待时间【旋转延迟时间】(平均定位时间+转动延迟)
- 注意 : 寻道时间是指磁头移动到磁道所需的时间: 等待时间为等待读写的扇区转到磁头下方所用的时间
问题 + 解决:
处理这11个记录的最长时间是()
最少时间 :
6 X 11 = 66
1-2-8 计算机总线
- 格局总线所处的位置不同,总线通常被分为三种类型:
- 内部总线
- 系统总线
- 数据总线
- 地址总线
- 控制总线
- 外部总线
1-2 -10 串联系统与并联系统可靠性计算
系统可靠性分析: 串联系统和并联系统
串联模型
- 例如: 每个子系统可靠性: 0.9;失效率: 0.1
- R 是 可考虑;λ是失效率(失效率的公式适用有限)
并联模型
模冗系统和混合系统
1-2-11 CRC与海明校验码【我不会】
- 什么是检错和纠错
- 增大码距的方式来实现
- 什么是码距
- 一个编码系统的码距是整个编码系统中任意(所有)两个码字的最小距离
- 码距与检错、纠错有何关系
- 在一个玛组内为了检测e个误码,要求最小码距d应该满足: d >= e+1
- 在一个玛组内为了纠正t个误码,要求最小码距d应该满足 : d>= 2t+1
循环校验码
- 模2除法是指在做触发运算的过程中不计其进位的除法
海明校验码
第二章 操作系统
2-1 操作系统基本原理
- 作用
- 管理系统的硬件、软件、数据资源
- 控制程序运行
- 人机之间的接口
- 应用软件与硬件之间的接口(API)
- 操作系统具有哪些方面的管理呢?
- 进程管理
- 进程的状态
- 前驱图
- PV操作
- 死锁问题
- 存储管理
- 段页式存储
- 页面置换算法
- 文件管理
- 索引文件
- 位示图
- 作业管理
- 设备管理
- 微内核操作系统
- 虚设备与SPOOLING技术
- 进程管理
2-2 进程管理
2-2-1 进程的状态
2-2-2 前驱图
2-2-3 进程的同步与互斥
生产者与消费者的同步与互斥问题
2-2-4 进程管理 – PV操作【不会】
- 临界资源: 诸进程间需要互斥方法对其进行共享的资源 ,如打印机、磁带机等
- 临界区: 每个进程中访问临界资源的那段代码称为临界区
- 信号量: 是一种特殊的变量
单缓存区生产者、消费者问题PV源于描述:
- 生产者 :
- 生产一个产品
- 送产品到缓存区
- 消费者
- 从缓存区取产品
- 消费产品
- S1初值为1,S处置为0
- 生产者 :
2-2- 5 PV操作与前驱图的关系
2-2- 6 死锁问题
进程管理是操作系统的核心,如果设计不当,就会出现死锁的问题
- 例如: 系统有3个进程: A、B、C。这3个进程都需要5个系统资源。如果系统hi少有多少个资源,则不可能发生死锁
- 解决: 每个进程有n个资源,总共有k个进程,
- 不发生死锁 占用 的最少资源 ,答案 : k*(n-1)+1
A B C
银行家算法 : 分配资源的原则【P32,我不会,没听懂】
- 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程
- 进程可以分期请求资源,但请求的总数不能超过最大需求量
- 当系统现有的资源不能满足进程尚需资源数时,对进程的请求可以推迟分配,但总能使进程在有限的时间里得到资源
2-3 存储管理
2-3-1 分区存储组织
问题: 某计算机系统的内存大小为128k,采用可变分区分配方式进行内存分配,当前系统的内存分块情况如下图所示,现有作业4申请内存9k,几种不同的存储分配算法在分配中,会产生什么样的结果呢?
【作业1(33k);作业2(22k);作业3(10k)】
解决:
- 分配前:
- 首次适应法:
- 最佳适应法:(保留大的内存区,但是会留下很小的空白区)
- 最差适应法
- 循环首次适应法(连成环状,顺次分配)
2-3-2 页式存储组织【我不会】
页号 —— 页面地址
- 优点: 利用率高,碎片小,分配及管理简单
- 缺点:增加了系统开销;可能产生抖动现象
- 高级程序语言使用逻辑地址;
- 运行状态,内存中使用物理地址
题目【我更不明白了】
2-3-3 段式存储组织
段号 | 段内地址
- 优点: 多道程序共享内容,各段程序修改互不影响
- 缺点: 内存利用率低,内存碎片浪费大
2-3-4 段页式存储组织
- 段表寄存器: 段表大小 | 段表始址
- 优点 : 空间浪费小、存储共享容易、存储保护容易、能动态连接
- 缺点: 由于管理软件的增加,复杂性和开销也随之增加,需要的硬件以及占用的内存也有所增加,使得执行速度大大下降
2-3-5 块表
- 块表: 是一种小容量的相联存储器(Associative Memory),由高速缓存器组成,速度快,并且可以从硬件上保存内容并行查找,一般用来存放当前访问最高频繁的少数活动页面的页号
2-3-6 页面淘汰算法【我不会】
页面置换算法
练习题:
2-3-7 文件管理
索引文件结构
- 直接索引
- 一级间接索引
- 二级间接索引
- 三次间接索引
注意:
- 10号位置:(每个地址假设占4个字节)
- 一个物理盘块可以存多少地址:4k / 4字节 = 1024
- 4k X 1024
- 11号位置可以存的文件大小
- 4kX1024X1024
- 10号位置:(每个地址假设占4个字节)
练习题:
- 第二题答案为B
2-3-8 文件和属性目录结构
- 文件属性:
- R 只读文件属性
- A 存档属性
- S 系统文件
- H 隐藏文件
- 文件名的组成
- 驱动器号
- 路径
- 著文件名
- 扩展名
- 绝对路径: 是从盘符开始的路径
- 相对路径: 是从当前路径开始的路径
- 如当前目前为: D1, 要求F2路径,则: 绝对路径: /D1/W2/F2 , 相对路径: W2/F2
2-3-9 空闲存储空间的管理【还不明白】
- 空闲区表法(空闲文件目录)
- 空闲链表法
- 位示图法
- 成组链接法
2-4 设备管理
- 数据传输控制方式
- 程序控制方式
- 程序中断方式
- DMA方式
- 通道
- 输入输出处理机
2-4-1虚设备与Spooling 技术
- spooling: 开辟了缓存区,把要输出或输入的数据先缓存起来,解决了外设的低速和
- 出现了打印队列
2-4 微内核操作系统
- 用户态和核心态
- 单体内核和微内核
第三章 数据库系统
课程提要:
- 数据库模型
- ER模型
- 关系代数与元组演算
- 规范化理论(A)
- 并发控制
- 数据库完整性约束
- 分布式数据库
- 数据仓库与数据挖掘
3-1 三级模式-两级映射
- 用户级数据库
- 概念级数据库
- 物理级数据库
数据库设计过程
3-2 ER模型【本来以为回了,但是不会做题,奇了怪了】
集成的方法:
多个局部 E- R图一次集成
逐步集成,用累加的方式一次集成两个局部E- R
集成产生的冲突及解决方法:
- 属性冲突: 包括属性域冲突与属性取值冲突
- 命名冲突: 包括同名异义与异名同义
- 结构冲突: 包括同一对象在不同应用中具有不同的抽象,以及同一实体在不同局部E-R图中所包含的属性个数和属性排列次序不完全相同
- 一个实体型转换为一个关系模型
- 1: 1 联系
- 1: 联系
- m: n联系
- 三个以上实体间的一个多元联系
- 一个实体型转换为一个关系模型
练习题:
3-3 关系代数
- 并,交,差,笛卡尔积,投影,选择,联接
3-4 规范化理论 – 函数依赖 以及 价值与用途
- 设R(U)是属性U上的一个关系模式,X和Y是U的自己,r为R的任一关系,如果对于r中的任意两个元组 u,v, 只要有u[X] = v[X],就有u[Y] = v[Y], 则称X函数 决定Y,或称Y 函数依赖于X,记为X -> Y
- 组件是函数的组合件
- 价值与用途:
- 非规范化的关系模型,可能存在的问题包括 : 数据冗杂、更新异常、插入异常、删除异常
3-5 规范化理论– 求候选关键字
键:
超键(可能存在冗杂在属性,唯一标识元组) —–消除多余属性–> 候选键 —> 主键
求候选键
- 将关系模式的函数依赖关系用“有向图”的方式表示
- 找入度为0的属性,并以该属性集合为起点,尝试遍历有向图,若能正常遍历图中所有结点,则该属性集即为关系模式的候选键
- 若入度为0的属性集不能遍历图中所有结点,则需要尝试性的将一些中间结点(既有入度,也有出度的结点)并入入度为0的属性集中,直至该集合能遍历所有结点,集合为候选键
求候选键实例
3-6 规范化理论 – 范式
- 1NF ,2NF, 3NF, BCNF
第一范式(1NF) : 在关系模式R中,当且仅当所有域只包含原子值,即每个分量都是不可再分的数据项,则称R是第一范式
例子: 下表中关系R是否满足 1NF,如果不满足,应如何调整?(不满足)
第二范式(2NF):当且仅当R是1NF,且每一个非主属性完全依赖主键(不存在部份依赖)时,则称R为第二范式
- 思考题: 该关系模式会存在哪些问题(从数据冗杂、更新异常、插入异常、删除异常这几个方面来考虑),解决方案是什么?
第三范式(3NF) : 当且仅当R是1NF,且E中没有非主属性传递依赖于码时,则称R是第三范式
BC范式: 设R是一个关系模式,F是它的依赖集,R属于BCNF当且仅当其F中每个依赖的决定因素必定包含R的某个候选码