数据的表示
1.进制转换
二进制(B） 基数 2 位权 2^k
（1）按权展开法：（转十进制）
二进制10100.01=1*2^4+1*2^2+1*2^(-2)
七进制604.01=6*7^2+4*7^0+1*7^(-2)
（2）短除法（除基取余法）：商为0截止，余数从下往上记录
2|94 余0
2|47 1
2|23 1
2|11 1
2|5 1
2|2 0
2|1 1
0
结果：1011110
（3）减法（十进制转二进制）：
（4）进制转换？
二进制三位——八进制一位 二进制四位——十六进制一位
2.码制（原码/反码/移码）
原码：最高位是符号位，其余低位表示数值的绝对值
反码：正数的反码与原码相同，负数的反码是其绝对值按位取反（符号位不变）
补码：正数的补码与原码相同，负数的补码是其反码末位加1（符号位不变）
移码：补码的符号位按位取反
计算过程中，用补码进行加减运算
| 码制 | 定点整数 | 定点小数 | 数码个数 |
|---|---|---|---|
| 原码 | -（2(n-1))~+(2(n-1)-1) | -（1-2(-(n-1)))~+(1-2(-(n-1))) | 2^n-1 |
| 反码 | -（2(n-1))~+(2(n-1)-1) | -（1-2(-(n-1)))~+(1-2(-(n-1))) | 2^n-1 |
| 补码 | -2(n-1)~+(2(n-1)-1) | -1~+(1-2^(-(n-1))) | 2^n |
| 移码 | -2(n-1)~+(2(n-1)-1) | -1~+(1-2^(-(n-1))) | 2^n |
定点整数取值范围如何取？
n=3 时，绝对值位数为2
原码与反码
有 (00,01,10,11)*2八种组合方式，最大值为 011，最小值为 111
11 + 1 = 100，即2^2-1 --> max = 2^(n-1) - 1;
反码正数与原码一样，负数与原码为绝对值按位取反，故取值范围相同
----------------------------------------------------------------------
补码与移码
由于 000 与 100 表示 +0 和 -0 会浪费一个数码个数，于是人为定义补码的最小值为 100(1既当做符号位又当做表示数码的一个数)
补码是在反码的绝对值部分+1（也可以这么理解）
定点小数取值范围如何取？
n=3 时，绝对值位数为2
原码与反码，略
补码与移码
绝对值的取值范围同上，此时的小数点默认在符号位之后（计算机里没有小数点）
此时 max = 0.11
因为 0.11 + 0.01 = 1.00 即 max + 2^-(n-1) = 1
故 max = 1 - 2^-(n-1);
min = 1.00 (1既做符号位又做数码的一部分) 故 min = -1
数码个数
原码与反码
因为绝对值位数为 n-1 每个位置有 0/1 两种选项 所以绝对值位有 2^(n-1)个选项，符号位有0和1，但是1000 0000 和 0000 0000是一样的所以，数码个数 = 2^n-1
----------------------------------------------------------------------
补码与移码
因为 -0用来扩充负数取值范围故比原码与反码多一个
3.浮点数的表示
浮点数表示：N=尾数*基数^指数
尾数：定点小数 指数：阶码
特点：
-
一般尾数用补码，阶码用移码
-
阶码的位数决定数的表示范围，位数越多范围越大
-
尾数的位数决定数的有效精度，位数越多精度越高
-
对阶时，小数向大数看齐
-
对阶是通过较小数的尾数右移实现的
数符：尾数部分的符号位 阶符：阶码的符号位
浮点数加减运算步骤：对阶->尾数运算->结果格式化
4.逻辑运算
关系运算符的优先级低于算术运算符 关系运算符的优先级高于赋值运算符
逻辑运算
逻辑异或：连接的两个逻辑值不相同时才取1，相同时取0
运算符优先顺序：
!>算术运算符(*/+-)>关系运算符(><>=<=!===)>&&>||>赋值运算符
校验码概述
1.校验码
码距：任何一种编码都有许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距
- 奇偶校验码（只能检查奇数位错，不可纠错）
方法：由若干位有效信息(如一个字节)，再加上一个二进制位(校验位)组成校验码
奇校验：整个校验码（有效信息位和校验位）中"1"的个数为奇数（若有奇数个数据位出错，则可以检测出该错误但无法纠正错误）
偶校验：整个校验码（有效信息位和校验位）中"1"的个数为偶数
- CRC循环冗余校验码（可检错，不可纠错）
方法：在k位信息码之后拼接r位校验码。应用CRC码的关键是如何从k位信息位简便地得到r位校验位（编码），以及如何从k+r位信息码判断是否出错
把接收到的CRC码用约定的生成多项式G(X)去除（模二除法），如果正确，则余数为0；如果某一位出错，则余数不为0。不同的位数出错其余数不同，余数和出错位序号之间有唯一的对应关系
- 海明校验码（可检错，也可纠错）
原理：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，可以指出错误的位置，为自动纠错提供了依据
公式：2^r>=m+r+1（m：信息位个数 r：检验码位数）
海明码码距大于1
| 校验码位数 | 校验码位置 | 校验方式 | |
|---|---|---|---|
| 奇偶校验 | 1 | 一般拼接在头部 | 奇校验：最终1的个数是奇数个；偶校验：最终1的个数是偶数个 |
| CRC循环冗余检验 | 生成多项式最高次幂决定 | 拼接在信息位尾部 | 模二除法求余数，拼接作为校验位 |
| 海明校验 | 2^r>=m+r+1 | 插入在信息位中间 | 分组奇偶校验 |
CPU的组成(运算器与控制器)
计算机结构：外设+主机
外设：输入设备(键盘)+辅助存储器、外存(U盘)+输出设备(显示屏)
主机：主存储器、内存+CPU(运算器+控制器)
运算器：
(1)算数逻辑单元ALU：数据的算术运算和逻辑运算
(2)累加存储器AC：通用寄存器，为ALU提供一个工作区，用在暂存数据
(3)数据缓冲寄存器DR：写内存时，暂存指令或数据
(4)状态条件寄存器PSW：存状态标志与控制标志
控制器：
(1)程序计数器PC：存储下一条要执行指令的地址
(2)指令寄存器IR：存储即s将执行的指令
(3)指令译码器ID：对指令中的操作字段进行分析解释
(4)时序部件 ：提供时序控制信号
地址寄存器：用来保存当前CPU所访问的内存单元的地址
寻址方式
1指令
格式：操作码字段（OP）+地址码字段（A1，A2）
寻址方式：
(1)立即寻址方式
特点：操作数(立即数)直接在指令中，速度快，灵活性差
(2)直接寻址方式
特点：指令中存放的是操作数的直接地址
(3)间接寻址方式
特点：指令中存放了一个地址，这个地址对应的内容是操作数的间接地址
(4)寄存器寻址方式
特点：寄存器存放操作数
(5)寄存器间接寻址方式
特点：寄存器内存放的是操作数的地址
2CISC与RISC(计算机指令集简称)
| 指令系统类型 | 指令 | 寻址方式 | 实现方式 | 其它 |
|---|---|---|---|---|
| CISC(复杂) | 数量大，使用频率差别大，可变长格式 | 支持多种 | 微程序控制技术（微码） | 研制周期长 |
| RISC(精简) | 数量少，使用频率接近，定长格式，大部分为单周期指令，操作寄存器，只有Load/Store操作内容 | 支持方式少 | 增加了通用寄存器；硬布线逻辑控制为主；适合采用流水线 | 优化编译，有效支持高级语言 |
CISC：复杂，指令数量多，频率差别大，多寻址
RISC：精简，指令数量少，操作寄存器，单周期，少寻址，多通用寄存器，流水线
2流水线技术
流水线是指程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度
步骤：取指令->分析指令->执行指令
流水线周期为执行时间最长的一段
流水线计算公式：1条指令执行时间+（指令条数-1）*流水线周期
理论公式(默认)：(t1+t2+...+tk)+(n-1)*t
实践公式：kt+(n-1)t
流水线吞吐率：单位时间内流水线所完成的任务数量或输出的结果数量
TP=指令条数/流水线执行时间
求流水线最大吞吐率时，用实践公式求流水线执行时间，当n趋向于无限大，t_max = 1/t
流水线吞吐率：指在单位时间内流水线所完成的任务数量或输出的结果数量
流水线方式下可同时执行多条指令（准并行）
存储系统
1层次化存储体系
层次化存储结构：
CPU(寄存器 最快，但容量小，成本高)->Cache(按内容存取)->内存/主存(分两类：随机存储器RAM 只读存储器ROM)->外存/辅存(硬盘、光盘、U盘等)
速度快，容量小，成本高<-->速度慢，容量大，成本低
局部性原理是层次化存储结构的支撑
时间局部性：刚被访问的内容，立即又被访问（循环体）
空间局部性：刚被访问的内容，临近的空间很快被访问（顺序）
层次化存储结构分类：
(1)存储器位置 内存&外存
(2)存取方式
按内容存取：相联存储器（如Cache）
按地址存取：随机存取存储器（如内存） 顺序存取存储器（如磁带） 直接存取存储器（如磁盘
(3)工作方式 随机存取存储器RAM（如内存DRAM）（内容掉电丢失） 只读存储器ROM（如BIOS）（内容掉电保留）
DRAM：动态随机存储器（定时刷新）
SRAM：静态随机存取存储器
Cache：高速缓存
EEPROM：电可擦可编程只读存储器
虚拟存储体系（主存-外存） 三级存储结构（Cache-主存-外存）
在微机系统中，BIOS（基本输入输出系统）保存在主板上的ROM中
2Cache
概念：在计算机的存储系统中，Cache是访问速度最快的层次（若有寄存器，则寄存器最快）
使用Cache改善系统性能的依据是程序的局部性原理（时间局部性，空间局部性）
Cache的命中率并不随其容量增大线性地提高1->2->4->8->16(非线性)
地址映像是将主存与Cache的存储空间划分为若干大小相同的页（或称为块）
直接相联映像：硬件电路较简单，但冲突率很高
全相联映像：电路难于设计和实现，只适用于小容量的Cache，冲突率较低
组相联映像：直接相联与全相联的折中
注意：主存与Cache之间的地址映射由硬件直接自动完成
| 冲突率（高、中、低） | 电路复杂度（复杂、简单、折中） | |
|---|---|---|
| 直接相联映像 | 高 | 简单 |
| 全相联映像 | 低 | 复杂 |
| 组相联映像 | 中 | 折中 |
主存与Cache的地址映射方式中，（全相联）方式可以实现主存任意一块装入Cache中任意位置，只有装满才需要替换
3主存编址计算
存储单元（默认1字节/8bit）：每个分组（每行位数）bit
总容量：存储单元个数*编址内容bit
存储单元个数：最大地址-最小地址+1
编址内容
按字编址：存储体的存储单元是字存储单元，即最小寻址单位是一个字（1bit）
按字节编址：存储体的存储单元是字节存储单元，即最小寻址单位是一个字节（8bit）
根据存储器所要求的容量和选定的存储芯片的容量，可计算出所需芯片的总数：总片数=总容量/每片的容量
输入/输出技术(I/O)
CPU控制内存与外设之间的交互（内存较快，外设较慢）
数据传输控制方式：
-
程序控制（查询）方式：分为无条件传送和程序查询方式两种。方法简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率
-
CPU需要频繁的查询IO的状态；无条件是系统默认 -
程序中断方式（鼠标、键盘）：与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度，CPU与数据传输并行
-
DMA（直接内存存取）方式：DMA方式是为了在主存与外设之间实现高速、批量数据交换而设置的。DMA方式比程序控制方式与中断方式都高效（不需要CPU参与数据传输过程）
CPU是在一个总线周期结束时响应DMA请求的
（DMAC向总线裁决逻辑提出总线请求；CPU执行完当前总线周期即可释放总线控制权。此时DMA响应，通过DMAC通知I/O接口开始DMA传输）
通道方式
I/O处理机
中断处理过程：
CPU无需等待也不必查询I/O状态
当I/O系统准备好以后，发出中断请求信号通知CPU
CPU接到中断请求后，保存正在执行程序的现场（保存现场）（通过栈），打断的程序当前位置即为断点
（通过中断向量表）转入I/O中的服务程序的执行，完成I/O系统的数据交换
返回被打断的程序继续执行（恢复现场）
总线系统
特点：分时双工（一条总线同一时刻仅允许一个设备发送，但允许多个设备接收）（性能低）
总线的分类：
- 数据总线：在CPU与RAM之间来回传送需要处理或是需要存储的数据
- 地址总线：用来指定在RAM之中储存的数据的地址
- 控制总线：将微处理控制单元的信号，传送到周边设备
并行总线适合近距离高速数据传输，串行总线适合长距离数据传输
可靠性
可靠性指标：
串联系统与并联系统：
N模混合系统：
性能指标
字长(计算机一次能够读取的数据长度)和数据通路宽度
主存容量和存取速度
运算速度
吞吐量与吞吐率（单位时间内完成的任务量）
响应时间（RT）与完成时间（TAT）
兼容性（向下兼容）
主频与CPU时钟周期(主频倒数)
CPI（每条指令所占据的时钟周期）与IPC（每个时钟周期能够完成的指令条数）
MIPS与MFLOPS
MIPS=指令条数/(执行时间10^6)=主频/CPI=主频IPC
MFLOPS=浮点数操作次数/(执行时间*10^6)
计算机组成与体系结构总结
操作系统相关概念
1操作系统的作用
- 管理系统的硬件、软件、数据资源
- 控制程序运行
- 人机之间的接口
- 应用软件与硬件之间的接口
操作系统任务：
进程管理、存储管理、文件管理、作业管理、设备管理
计算机系统的层次结构：计算机硬件->操作系统->系统软件->应用软件
2特殊的操作系统
进程的概念
1线程的概念
进程：程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCB）和数据块三部分组成
进程控制块（PCB）：PCB时进程存在的唯一标志。内容包含进程标识符、状态、位置信息、控制信息、队列指针（链接同一状态的进程）、优先级、现场保护区等
进程与程序的区别：
进程是程序的一次执行过程，没有程序就没有进程
程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是
进程的2个基本属性：
可拥有资源的独立单位；可独立调度和分配资源的基本单位
2进程的状态
运行状态：当一个进程在CPU上运行时（单处理机处于运行状态的进程只有一个）
就绪状态：一个进程获得了除CPU外的一切所需资源，一旦得到处理机即可运行
等待状态/阻塞状态/睡眠状态：一个进程正在等待某一事件发生（例如请求I/O等待I/O完成等）而暂时停止运行，此时即使把CPU分配给进程也无法运行，故称进程处于阻塞状态
挂起原因：
（1）进程过多，主存资源不足，此时必须将某些进程挂起，放到磁盘对换区，暂时不参与调度，以平衡系统负载
（2）系统出现故障，或者是用户调试程序，也可能需要将进程挂起检查问题
/*
考查线程之间哪些共享哪些不共享
考查线程之间状态的变迁
运行结束了只能说时间片到了，不能确定是否已完成了
*/
进程调度
1PV操作的概念
临界资源：诸进程间需要互斥方式对其进行共享的资源（进程中访问临界资源的那段代码称为临界区）
进程的互斥：当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态（互斥的进程相互之间是间接制约关系）
//厕所坑位、车票数量
进程的同步：为完成某种任务而建立的两个或多个线程，这个线程需要在某些位置上协调他们的工作次序而等待、传递信息所产生的制约关系（速度有差异，在一定情况停下等待）直接制约关系
//生产者-->市场-->消费者
PV操作（加锁解锁过程）（可能发生死锁）（降低资源利用率）（成对使用）：
信号量（S）：是一种特殊的变量（全局变量）
信号量可以表示资源数量
信号量为负数时还可以表示排队进程数
P操作（申请过程）：申请/锁定资源->检查资源是否足够
V操作（释放过程）：释放/解锁资源->检查是否有进程排队
（先全部执行完P操作再执行V操作或者两者同时执行）
P(S)：S <—— S - 1
如果S >= 0，进程继续执行
如果S < 0，进程被阻塞后，放入信号量等待队列中，然后转进程调度
V(S)：S <—— S + 1
如果S > 0，进程继续执行（没有申请了，就空闲继续执行进程即可）
如果S <= 0，从该信号的等待队列中释放一个等待进程，然后再返回原进程继续执行或转进程调度（唤醒等待队列中的一个）
/*考PV操作对信号量的值的影响*/
2信号量与PV操作
PV操作与互斥模型（互斥信号量S的初值为1）
PV操作与同步模型（资源信号量其初值为资源的个数。信号量初值为0；信号量小于0，线程等待；信号量大于0，表示可用资源个数）
关键点：
- 消费者和生产者必须互斥的使用缓冲区
- 缓冲区空时，消费者不能读取数据
- 缓冲区满时，生产者不能添加数据
- 消费者和生产者是一种同步关系，即：在生产者生产时，消费者不能消费；消费者消费时，生产者不能生产；只有生产者生产之后，消费者才能消费
- 缓冲区互斥访问，我们可以用互斥锁，信号量来控制这两个线程对临界区的访问，因为只有1块临界资源，所以初始值为1。
- 缓冲区所有格子放满了时，生产者不能生产。我们可以记录当前缓冲区没放数据的格子数，即空格子数，那么每次生产者往缓冲区放数据时，空格子数量-1，消费者取数据时，数量+1。当空格子数==0时， 生产者-1会阻塞。故我们可以用信号量来表示缓冲区为空状态的控制，初始值为N，还没有往里面放数据，生产P(-1)，消费(V+1)，当P(-1)操作阻塞，表示缓冲区的所有格子都放满了。
- 缓冲区中没有数据时，消费者不能消费，同理也用信号量来控制，我们记录当前放数据的格子的个数，初始值为0， 表示此时没有数据，生产者生产+1，消费者消费-1，当==0时，消费者阻塞。
互斥与同步模型结合（缓冲区一次只能允许一个人用）
/*有先有后是同步，访问相同是互斥，PV成双成对*/
3前驱图与PV操作
前驱：箭头流出的地方；后继：前驱流入的地方
每一个箭头流入的地方都有一个P操作（检查前驱是否完成）
每一个箭头流出的地方都有一个V操作（通知后继进程）
死锁资源数计算
死锁：是指两个以上的进程互相都要求对方已经占有的资源导致无法继续运行下去的现象
死锁四大条件：互斥，保持和等待，不剥夺，环路等待
预防死锁：有序资源分配法，静态资源分配
避免死锁：银行家算法
死锁的检测与解除
鸵鸟策略（不予理睬）
进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果进程在等待一件不可能的事，则进程就死锁了。而如果多个进程产生死锁，就会造成系统死锁。
系统不可能发生死锁的最小资源数：(w-1)*m+1<=n
w：每个进程需要的系统资源数； m：进程数
例：系统有5个进程：A、B、C、D、E。这5个进程都需要4个系统资源。如果系统至少有多少个资源则不可能发生死锁。
n<4:一定死锁; n>=4&&n<=15:可能避免死锁,可能死锁; n>=15+1:不可能死锁
进程资源图
(非)死锁：化简到最后(无)还有进程未完成
可化简：有进程可以执行完成，从而释放资源
(非)阻塞节点：(无)有资源支持进程完成
存储管理
1页式存储
页式存储：将程序与内存均化分为同样大小的块，以页为单位将程序调入内存
页表：页号+块号（物理块号/页帧号）
用户程序：逻辑页（逻辑地址=页号+页内地址）
内存：物理页（物理地址=页帧号+页内地址）
优点：利用率高，碎片小，分配及管理简单
缺点：增加了系统开销；可能产生抖动现象（给程序增加了资源，但并没有提高效率/某个页面经常性的调用内存，然后淘汰）
页面淘汰依据：
1.淘汰访问位为0页面
2.多个访问位为0，淘汰修改位为0页面
页面置换算法：
最优（Optimal，OPT）算法（理想性）
随机（RAND）算法
先进先出（FIFO）算法：有可能产生“抖动”。例如，432143543215序列，用3个页面，比4个缺页要少
最近最少使用（LRU）算法：不会“抖动”，LRU的理论依据是“局部性原理”
2段式存储
段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样
逻辑地址（段号，段内偏移量（不能超过段长））
优点：多道程序共享内存，各段程序修改互不影响
缺点：内存利用率低，内存碎片浪费大
3段页式存储
磁盘管理
磁盘存取时间=寻道时间+等待时间，寻道时间是指磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间
读取磁盘数据的时间应包括以下三个部分：（1)找磁道的时间 （2）找块（扇区）的时间，即旋转延迟时间 （3）传输时间
磁盘移臂调度算法：先来先服务（FCFS），最短寻道时间优先（SSTF），扫描算法（双向)(SCAN），循环扫描（CSCAN）算法（单向）
I/O管理软件
I/O请求：用户进程->设备无关程序->设备驱动程序->中断处理程序->硬件
I/O应答：硬件->中断处理程序->设备驱动程序->设备无关程序->用户进程
硬件：完成具体的I/O操作
中断处理程序：I/O完成后唤醒设备驱动程序
设备驱动程序：设置寄存器，检查设备状态
设备无关I/O层：设备名解析、阻塞进程、分配缓冲区
用户级I/O层：发出I/O调用
文件管理
1文件相关概念
文件：具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合
逻辑结构：有结构的记录式文件、无结构的流式文件
物理结构：连续结构、链接结构、索引结构、多个物理块的索引表
文件目录：
- 文件目录项/文件的说明/文件控制块FCB
基本信息类：文件名、文件的物理地址、文件长度和文件块数等
存储控制信息类：文件的存储权限：读写、执行权限等
（文件属性：只执行、隐含、只读、读/写、共享、系统）
使用信息类：文件建立日期、最后一次修改/访问日期、当前使用的信息、打开文件的进程数以及在文件上的等待队列等
- 目录结构
一级目录结构：线性结构，查找速度慢，不允许重名和实现文件共享等
二级目录结构：主文件目录（MFD）+用户目录（UFD）
三级目录结构：树型目录结构（多级目录结构）
若系统在将（目录）文件修改的结果写回磁盘时发生崩溃，则对系统的影响相对（空闲块/用户程序/用户数据）较大
2树形目录结构（绝对路径与相对路径）
多级目录结构允许不同用户的文件可以具有相同的文件名
绝对路径：是从盘符（根目录，CDEF盘）开始的路径，磁盘访问次数1
相对路径：是从当前目录开始的路径，磁盘访问次数1
全文件名：绝对路径+文件名
3位示图
考点
-
给一个总量问需要的（字）个数
求得团体数/人数，再根据每个人只占一个bit来换算 -
给磁盘编号问所处的位置
求i，j。根据编号求得商和余数后易解
4索引文件
索引相当于地址相当于物理块号
索引表在Unix系统中默认13个结点
直接索引（10个索引结点对应10个物理盘块对应连续的10个逻辑页，范围：10*每个逻辑页大小，访问一次磁盘）
一级间接索引（每个索引占据3B大小，范围：10-350逻辑页，341个索引结点，访问两次磁盘）
二级间接索引（341^2个索引结点）
三级间接索引（341^3个索引结点）
文件在逻辑上是连续的，但索引文件的存储（物理块）是可以分散的
考点
需要能够理解物理块号是否连续；直接索引存的是物理块地址，占用的内存也是物理块大小；间接索引就只存储一个索引表，将内存配给每一个索引，这个索引可以指向下一级的索引表也可以指向一个物理块
作业管理
作业调度算法：先来先服务法（先申请先执行），时间片轮转法，短作业优先法（优先响应作业时间短的作业），最高优先权优先法（标注优先权），高响应比优先法（优先响应响应比高的作业）
响应比：（作业等待时间+作业执行时间）/作业执行时间
操作系统章节概述总结
数据库的基本概念
1数据库体系结构
集中式数据库系统（单机系统）：
- 数据是集中的
- 数据管理是集中的
- 数据库系统的素有功能（从形式的用户接口到DBMS核心）都集中在DBMS所在的计算机
C/S结构（应用程序的客户端居多）： （B/S结构：浏览器客户端）
- 客户端负责数据表示服务
- 服务器主要负责数据库服务
- 数据库系统分别为前端和后端
- ODBC、JDBC
分布式数据库：
- 物理上分布、逻辑上集中
- 物理上分布、逻辑上分布
- 特点：
数据独立性（除了数据的逻辑独立性外，还有数据分布独立性（分布透明性）
集中与自治共享结合的控制结构（各局部的DBMS可以独立地管理局部数据库，具有自治的功能。同时，系统又设有集中控制机制，协调各局部DBMS的工作，执行全局应用）
适当增加数据冗余度（在不同的场地存储同一数据的多个副本，可以提高系统的可靠性和可用性，同时也能提高系统性能）
（提高系统的可用性，即当系统中某个节点发生故障时，因为数据有其他副本在非故障场地上，对其他所有场地来说，数据仍然是可用的，从而保证数据的完备性）
全局的一致性、可串行性和可恢复性
- 透明性：
分片透明：是指用户不必关心数据是如何分片/分块的，它们对数据的操作在全局关系上进行，即如何分片对用户是透明的
复制透明：用户不用关心数据库在网络中各个节点的复制情况，被复制的数据的更新都由系统自动完成
位置透明：是指用户不必知道所操作的数据放在何处，即数据分配到哪些站点存储对用户是透明的（物理位置）
局部映像透明性（逻辑透明）：是最低层次的透明性，该透明性提供数据到局部数据库的映像，即用户不必关心局部DBMS支持哪种数据模型、使用哪种数据操纵语言，数据模型和操纵语言的转换是由系统完成的。因此，局部映像透明性对异构型和同构异质的分布式数据库系统是非常重要的。
并行数据库：
- 共享内存式
- 无共享内存式
2三级模式结构
三级模式和两级映像
三级模式：外模式/用户模式（视图级），概念模式/模式（表级），内模式/存储模式（文件级）
外模式-概念模式映像：逻辑独立性：数据的逻辑结构发生变化后，用户程序也可以不修改。但是为了保证应用程序能够正确执行，需要修改外模式和概念模式之间的映像
概念模式-内模式映像：物理独立性：当数据的物理结构发生变化时，应用程序不用改变。但是为了能够保证应用程序能够给正确执行，需要修改概念模式和内模式之间的映像
3数据仓库
数据仓库特点：
- 面向主题：数据按主题组织
- 集成的：消除了原数据中的不一致性，提供整个企业的一致性全局信息
- 相对稳定的（非易失的）：主要进行查询操作，只有少量的修改和删除操作（或是不删除）
- 反映历史变化（随着时间变化）：记录了企业从过去某一时刻到当前各个阶段的信息可对发展历程和未来趋势做定量分析和预测
数据库设计过程
需求分析（数据流图OFD，数据字典OD，需求说明书）->概念结构设计（ER模型）->逻辑结构设计（关系模式）（转换规则、规范化理论）->物理设计（聚簇索引）
概念设计阶段
1概念设计过程
E-R模型
需求分析->（抽象数据->设计局部ER模型->合并局部模型消除冲突（集成）->重构优化消除冗余）概念结构设计->逻辑设计
集成的方法：
- 多个局部E-R图一次集成
- 逐步集成，用累加的方式一次集成两个局部E-R
集成产生的冲突及解决办法：（针对同一对象）
- 属性冲突：包括属性域冲突和属性取值冲突
- 命名冲突：包括同名异义和异名同义
- 结构冲突：包括同一对象在不同应用中具有不同的抽象，以及同一实体在不同局部E-R图中所包含的属性个数和属性排列次序不完全相同
2E-R图
实体：现实世界中可以区别于其他对象的事件或事物 (实体集-实体的集合)
属性：实体某方面的特性
- 简单属性：原子的，不可再分的
- 复合属性：可以细分为更小的部分（即划分为别的属性）
- 单值属性：定义的属性对于一个特定的实体都只有单独的一个值
- 多值属性：在某些特定情况下，一个属性可能对应一组值
- NULL属性：表示无意义或不知道
- 派生属性：可以从其他属性得来
联系：实体的联系分为实体内部的联系和实体与实体间的联系。实体间联系类型：1:1，1:*， :
-
两个不同实体集之间联系
-
两个以上不同实体集之间的联系（三元联系）多重度的确定
-
同一个实体集内的二元联系
弱实体：在现实世界中有一种特殊的依赖联系，该联系是指某实体是否存在对于另一些实体具有很强的依赖关系，即一个实体的存在必须以另一个实体为前提而将这类实体称为弱实体，如家属与职工的联系，附件与邮件
特殊化：在现实世界中，某些实体一方面具有一些共性，另一方面还具有各自的特性，一个实体集可以按照某些特征区分为几个子实体
聚集：一个联系作为另一个联系的一端
逻辑结构设计
1关系模式相关概念
数据模型（层次模型，网状模型，关系模型，面向对象模型）
三要素：数据结构、数据操作、数据的约束条件
关系模型相关概念
- 目或度：关系模式中属性的个数
- 候选码（候选键）：唯一标识元组，且无冗余。属性集合，可以有一个，可以多个，可以单属性，可以多属性。任选一个作为主键
- 主码（主键）
- 主属性与非主属性：组成候选码的属性就是主属性，其他的就是非主属性
- 外码（外键）：其它关系的主键
- 全码（ALL-Key）：关系模式的所有属性组是这个关系的候选码
关系的3种类型
- 基本关系表
- 查询表
- 视图表
完整性约束
- 实体完整性约束（主键：唯一，非空）
- 参照完整性约束（外键：其他关系主键/空）
- 用户自定义完整性约束
触发器：完成一些复杂的完整性约束条件的设定，对单条元组或属性相应的变化添加监听，一旦发生变化，随之触发或更新新的内容
2E-R图转关系模式
一个实体型必须转换为一个关系模式
联系转关系模式：
（1）一对一联系的转换有两种方式（合并实体）（独立关系）
独立的关系模式：并入两端主键及联系自身属性（主键：任一端主键）
归并（并入任意一端）：并入另一端主键及联系自身属性（主键：保持不变）
（2）一对多联系的转换有两种方式（合并实体）（独立关系）
独立的关系模式：并入两端主键及联系自身属性（主键：多端主键）
归并（并入多端）：并入另一端主键及联系自身属性（主键：保持不变）
（3）多对多联系的转换只有一种方式（独立关系）
独立的关系模式：并入两端主键及联系自身属性（主键：两端主键的组合键）
关系代数
属性列，元组行
并，交，差，笛卡尔积（列数二者之和，行数二者乘积），投影，选择，自然连接（列二者之和减去重复列数，行同名属性列取值相等/对笛卡尔积先做选择，再做投影）
规范化理论
1规范化理论基本概念
函数依赖：设R(U)是属性U上的一个关系模式，X和Y是U的子集，r为R的任一关系，如果对于r中的任意两个元组u，v，只要有u[Y]=v[Y]，则称X函数决定Y，或称Y函数依赖于X，记为X->Y，X：决定因素，Y:被决定因素
关系模式：R（A，B，C）
部分函数依赖：{AB->C,A->C}
传递函数依赖：{A->B,B->C}（冗余依赖）
Amstrong公理体系
关系模式R<U，F>来说有以下的推理规则：
A1.自反律：若Y包含于X包含于U，则X->Y成立
A2.增广律：若Z包含于U且X->Y，则XZ->YZ成立
A3.传递律：若X->Y且Y->Z，则X->Z成立
根据以上三条推理规则可得下面三条推理规则
合并规则：由X->Y，X->Z，有X->YZ。（A2，A3）
伪传递规则：由X->Y，WY->Z，有XW->Z。（A2，A3）
分解规则：由X->Y及Z包含于Y，有X->Z。（A1，A3）
候选键
图示法求候选键
1、将关系的函数依赖关系，用“有向图”的方式表示。
2、找出入度为0的属性，并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有结点，则该属性集即为关系模式的候选键
3、若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将一些中间结点（既有入度，也有出度的结点）并入入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键
主属性与非主属性：组成候选码的属性就是主属性，其他的就是非主属性
2范式判断
规范化理论
规范化问题：数据冗余，修改异常，插入异常，删除异常（未达到3NF，默认问题都存在）
范式
无非主属性，至少满足3NF
第一范式（1NF）：在关系模式R中，当且仅当所有域只包含原子值，即每个属性都是不可再分的数据项，则称关系模式R是第一范式
派生属性：能够求和的属性
第二范式（2NF）：当且仅当关系模式R是第一范式（1NF），且每一个非主属性完全依赖候选键（没有不完全依赖）时，则称关系模式R是第二范式
第三范式（3NF）：当且仅当关系模式R是第二范式（2NF），且R中没有非主属性传递依赖于候选键时，则称关系模式R是第三范式
BC范式（BCNF）：设R是一个关系模式，F是它的依赖集，R属于BCNF当且仅当其F中每个依赖的决定因素必定包含R的某个候选码
3模式分解
- 保持函数依赖分解
设数据库模式ρ={R1，R2，...，Rk}是关系模式R的一个分解，F是R上的函数依赖集，ρ中每个模式Ri上的FD集是Fi。如果{F1，F2，...，Fk}与F是等价的（即相互逻辑蕴涵），（冗余函数依赖不需要保留）那么称分解ρ保持FD。
例：设关系模式R（U,F）,其中U={A,B,C,D,E},F={A->BC,C->D,BC->E,E->A},（1）则分解ρ={R1（ABCE）,R2（CD）}是否保持函数依赖？（2）而分解ρ={R1（ABE）,R2（CD）}是否保持函数依赖？
(1)F1={A->BC,BC->E,E->A},F2={c->D},保持函数依赖
(2)F1={E->A},F2={C->D},不保持函数依赖
例：设关系模式R(U,F),其中U={A,B,C},F={A->B,B->C,A->C},则分解ρ={R1(AB),R2(BC)}是否保持函数依赖？
F1={A->B},F2={B->C}
设F3={(A->B,B->C)=>A->C},所以冗余的函数依赖不需要被保留，可推导得出的也是保持函数依赖
- 无损分解
有损：不能还原；无损：可以还原
无损连接分解：指将一个关系模式分解成若干个关系模式后，通过自然连接等运算仍能还原到原来的关系模式
存在同名属性列，以该属性列为左侧决定因素的函数依赖有保留->还原与之对应的被决定因素
例：设关系模式R(U,F)，其中：U={A,B,C,D,E}，F={A->B,DE->B,CB->E,E->A,B->D}。分解ρ={R1(ABC),R2(ED),R3(ACE)}是无损连接
| A | B | C | D | E | |
|---|---|---|---|---|---|
| R1(ABC) | √ | √ | √ | ×(√) | ×(√) |
| R2(ED) | ×(√) | ×(√) | × | √ | √ |
| R3(ACE) | √ | ×(√) | √ | ×(√) | √ |
SQL语言
1普通查询
select
2分组查询
group by () having ()
3权限控制
并发控制
1事物的特性
- 原子性：事务是原子的，要么做，要么都不做
- 一致性：事务执行的结果必须保证数据库从一个一致性状态变到另一个一致性状态
- 隔离性：事务相互隔离。当多个事务并发执行时，任一事务的更新操作直到其成功提交的整个过程，对其他事务都是不可见的
- 持久性：一旦事务成功提交，即使数据库崩溃，其对数据库的更新操作也永久有效
2并发问题
丢失更新/修改（由于多个事务的并发执行。多次写回，第一次写回被覆盖）
不可重复读（不可多次读取。验算前，对其他事务进行了修改）
读“脏”数据（被回滚，无效的数据）
3封锁协议
并发产生的问题的解决方案：封锁协议->可能会形成死锁
S封锁：共享锁/S锁/读锁：若事务T对数据对象A加上S锁，其他事务只能对A再加S锁，不能再对A添加X锁
X封锁：排他锁/独占锁/X锁/写锁：若事务T对数据对象A加上X锁，其他事务不能再对A添加任意锁
两段锁协议
数据库系统章节概述总结
