数据的表示

考点1：进制转换

考点2：码制（原码/反码/补码/移码）

考点3：浮点数的表示

考点4：逻辑运算

进制转换

进制数码基数位权十进制(D)0,1,2,3,4,5,6,7,8,91010的k次二进制(B)0,122的k次十六进制(H)0~9,A,B,C,D,E,F1616的k次

按权展开法

R进制转十进制使用按权展开法，其具体操作方式为：将R进制数的每一位数值用R的k次方表示，即幂的底数是R，指数为k，k与该位和小数点之间的距离有关。当该位位于小数点左边，k值是该位和小数点之间数码的个数，而当该位位于小数点右边，k值是负值，其绝对值是该位和小数点之间数码的个数加1。

!image-20240913153924070

短除法

十进制转R进制使用短除法(除基取余法)。

例如将94转换为二进制，不断的除R取余，直到为0，最后从下往上记录得到对应的R进制

!image-20240913154252267

减法

十进制转二进制通过减法

!image-20240913155326411

二进制转八进制和十六进制

二进制转八进制，对二进制分组，每3位二进制作为一组，不够的在前面补0

二进制转十六进制，对二进制分组，每4位二进制作为一组，不够的在前面补0

例如：

10 001 110 转八进制可以是：2 1 6，相当于0010、0001、0110

码制

原码：最高位是符号位，其余低位表示数值的绝对值

反码：正数的反码与原码相同，负数的反码是其绝对值按位取反(符号位不变)

补码：正数的补码与原码相同，负数的补码是其反码末位加1（符号位不变）

移码：

数值1数值-1(码制相加)1-1 原码0000 00011000 00011000 0010 反码0000 00011111 11101111 1111 补码0000 00011111 11110000 0000 移码1000 00010111 11111000 0000

数值范围和数值个数

!image-20240913163443428

浮点数的表示

N = 尾数 * 基数的指数次幂

尾数是一个定点小数，基数通常是2，指数也叫做阶码(阶码一般出现的时候是定点整数)

移码通常用在浮点数的阶码表示，补码通常用在浮点数的尾数表示

阶码可以影响数值表示的范围，阶码的位数越多，表示的范围就越大

尾数可以表示数值的有效精度，长度越大，精度越高

浮点数运算

运算过程：对阶>尾数计算>结果格式化

需要先进行阶码的对阶，让阶码保持一致

一般对接时，是小数向大数看齐

特点：

1、一般尾数用补码，阶码用移码

2、阶码的位数决定数的表示范围，位数越多范围越大

3、尾数的位数决定数的有效精度，位数越多精度越高

4、对阶时，小数向大数看齐

5、对阶是通过较小数的尾数右移实现的

例如：1.25×10的6次幂，对阶10次幂的话，就需要让尾数右移4位，变为0.000125×10的10次幂

阶符：阶码的符号位，当阶符为正号时，阶码是整数；当阶符为负数时，阶码是小数。

数符：尾数部分的符号位

逻辑运算

逻辑变量之间的运算称为逻辑运算。二进制1和0在逻辑上可以代表“真”与假。

!image-20240914142140368

优先次序：

!(非) > &&(与) > ||(或)

逻辑运算符中的&&和||低于关系运算符，!高于算术运算符

因此运算符的优先顺序为：！ > 算术运算符 > 关系运算符 > && > || > 赋值运算符

关系运算符

关系运算符及其优先次序

优先级相同(高)：<(小于)、<=(小于或等于)、>(大于)、>=(大于或等于)

优先级相同(低)：==(等于)、!=(不等于)

说明：

关系运算符的优先级低于算术运算符

关系运算符的优先级高于赋值运算符

短路原则

在逻辑表达式的求解中，并不是所有的逻辑运算符都要被执行。

a&&b&&c 只有a为真时，才需要判断b的值，只有a和b都为真时，才需要判断c的值

abc 只要a为真，就不必判断b和c的值，只有a为假，才判断b。a和b都为假才判断c

校验码

考点1：奇偶校验码

考点2：CRC循环冗余校验码

考点3：海明校验码

奇偶校验码

码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。

例如，用4位二进制表示16种状态，则有16个不同的码字，此时码距为1,。如0000与0001。

奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码。

奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。

偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数。

奇偶校验，可检查1位（奇数位）的错误，不可纠错。

CRC循环冗余校验码

CRC校验，可检错，不可纠错。

CRC的编码方法是：在k位信息码之后拼接r位校验码。应用CRC码的关键是如何从k位信息位简便地得到r位校验位（编码），以及如何从k+r位信息码判断是否出错。

把接收到的CRC码用约定的生成多项式G(X)去除（模二除法），如果正确，则余数为0；如果某一位出错，则余数不为0。不同的位数出错其余数不同，余数和出错位序号之间有唯一的对应关系。

海明校验码

海明校验码的原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀的拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。

海明校验码即可检错，也可纠错。

海明校验位的求取公式：2的r次方 >= m + r +1 或者 2的r次方 - 1 >= m + r

r是最小值，m是信息位的个数

校验码位数校验码位置检错纠错校验方式奇偶校验1一般拼接在头部可检奇数位错不可纠错奇校验：最终1的个数是奇数个；
偶校验：最终1的个数是偶数个； CRC循环冗余校验生成多项式是最高次幂决定拼接在信息位尾部可检错不可纠错模二除法求余数，拼接作为校验位海明校验2的r次方 >= m + r + 1插入在信息位中间可检错可纠错分组奇偶校验

CPU的组成(运算器与控制器)

计算机结构

外设

辅助存储器（辅存/外存）

输入设备

输出设备

主机

主存储器（主存/内存）

CPU

运算器

控制器

存储器：主存储器、辅助存储器

!image-20240918151156349

CPU结构

CPU

运算器

算术逻辑单元ALU

累加寄存器

数据缓冲寄存器

状态条件寄存器

控制器

程序计数器PC

指令寄存器IR

指令译码器

时序部件

运算器

1. 算术逻辑单元ALU：数据的算术运算和逻辑运算

2. 累加寄存器AC：通用寄存器，为ALU提供一个工作区，用在暂存数据

3. 数据缓冲寄存器DR：写内存时，暂存指令或数据

4. 状态条件寄存器PSW：存状态标志和控制标志（有争议，也有将其归为控制器的）

控制器

1. 程序计数器PC：存储下一条要执行指令的地址

2. 指令寄存器IR：存储即将执行的指令

3. 指令译码器ID：对指令中的操作码字段进行分析解释

4. 时序部件：提供时序控制信号

寻址方式

指令的基本概念

一个指令就是机器语言的一个语句，它是一组有意义的二进制代码，指令的基本格式如下：

操作码字段地址码字段 OP(操作码字段)A1(地址码字段)A2(地址码字段)

地址码是可以不存在的，所以也就有以下分类

零地址指令

单地址指令

二地址指令......

立即寻址方式

特点：操作数直接在指令中（放置的是操作数本身），速度快，灵活性差

直接寻址方式

特点：指令中存放的是操作数的地址

间接寻址方式

特点：指令中存放了一个地址，这个地址对应的内容是操作数的地址。

寄存器寻址方式

特点：寄存器存放操作数

寄存器间接寻址方式

特点：寄存器内存放的是操作数的地址

CISC与RISC

指令系统类型指令寻址方式实现方式其他 CISC(复杂)数量多，使用频率差别大，可变长格式支持多种微程序控制技术(微码)研制周期长 RISC(精简)数量少，使用频率接近，定长格式，大部分为单周期指令，操作寄存器，只有Load/Store操作内存支持方式少增加了通用寄存器；硬布线逻辑控制为主；适合采用流水线优化编译，有效支持高级语言

CISC与RISC比较，分哪些维度？

指令数量、指令使用频率、寻址方式、寄存器、流水线支持、高级语言支持

CISC：复杂，指令数量多，频率差别大，多寻址

RISC：精简，指令数量少，操作寄存器，单周期，少寻址，多通用寄存器，流水线

流水线技术

相关参数计算：流水线执行时间计算、流水线吞吐率、流水线加速比、流水线效率

流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度

!image-20240918164451317

流水线计算

实践公式：（k+n-1）*△t 其中 k 为一条指令所包含部分的数量，n 为指令的条数，Δt 为流水线周期

例题：若指令流水线一条指令分为取指、分析、执行三个阶段，并且这三个阶段的时间分别为取指1ns，分析2ns，执行1ns，则流水线的周期为多少？100条指令全部执行完毕需要执行的时间是多少？

　　分析：上面已经说过，流水线的周期为花费时间最长的阶段所花费的时间，所以流水线的周期就是2ns。

　　　　根据理论公式，T=（1+2+1）+（100-1）2=4+992=202ns

　　　　　根据实践公式，T=（3+100-1）*2=204ns

流水线吞吐率计算

存储系统

考点1：层次化存储体系

考点2：Cache

考点3：主存编址计算

层次化存储结构

!image-20240920134353336

局部性原理是层次化存储结构的支撑

时间局部性：刚被访问的内容，立即又被访问。

空间局部性：刚被访问的内容，临近的空间很快被访问

分类

存储器位置：内存&外存

存取方式：

按内容存取

相联存储器（如Cache）

按地址存取

随机存取存储器（如内存）

顺序存取存储器（如磁带）

直接存取存储器（如磁盘）

工作方式

1. 随机存取存储器RAM（如内存DRAM）

2. 只读存储器ROM（如BIOS）

DRAM：动态随机存取存储器

SRAM：静态随机存取存储器

Cache：高速缓存

EEPROM：电可擦可编程只读存储器

Cache

概念

在计算机的存储系统体系中，Cache是访问速度最快的层次（若有寄存器，则寄存器最快）。

使用Cache改善系统性能的依据是程序的局部性原理。

时间局部性

空间局部性

如果以h代表对Cache的访问命中率，t1表示Cache的周期时间，t2表示主存储器周期时间，以读操作为例，使用"Cache + 主存储器"的系统的平均周期为t3，则：

t3 = h × t1 + (1-h) × t2

其中，(1-h)又称失效率(未命中率)。

直接相联映像：硬件电路较简单，但冲突率很高。

全相联映像：电路难于设计和实现，只适用于小容量的cache，冲突率较低。

组相联映像：直接相联与全相联折中。

注：主存与Cache之间的地址映射由硬件直接完成。

映像

地址映像是将主存与Cache的存储空间划分为若干大小相同的页（或称为块）

例如，某机的主存容量为1GB，划分为2048页，每页512KB；Cache容量为8MB，划分为16页，每页512KB。

冲突率（高、中、低）电路复杂度（复杂、简单、折中）直接相联映像高简单全相联映像低复杂组相联映像中折中

主存编址计算

存储单元

存储单元格式：最大地址-最小地址+1

编址内容

按字编址：存储体的存储单元是字存储单元，即最小寻址单位是一个字

按字节编址：存储体的存储单元是字节存储单元，即最小寻址单元是一个字节。

总容量 = 存储单元个数 * 编址内容

根据存储器所要求的容量和选定的存储芯片的容量，就可以计算出所需芯片的总数，即：

总片数 = 总容量/每片的容量

输入输出技术

数据传输控制方式

程序控制(查询)方式：分为无条件传送和程序查询方式两种。方式简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率。

程序中断方式：与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度。

DMA方式：DMA方式是为了在主存与外设之间实现高速、批量数据交换而设置的。DMA方式比程序控制方式与中断方式都高效。

（DMAC向总线裁决逻辑提出总线请求；CPU执行完当前总线周期即可释放总线控制权。此时DMA响应，通过DMAC通知I/O接口开始DMA传输。）

通道方式

I/O处理机

中断处理过程：

CPU无需等待也不必查询I/O状态。

当I/O系统准备好以后，发出中断请求信号通知CPU；

CPU接到中断请求后，保存正在执行程序的现场（保存现场），打断的程序当前位置即为断点；

（通过中断向量表）转入I/O中的服务程序的执行，完成I/O系统的数据交换；

返回被打断的程序继续执行（恢复现场）。

总线系统

一条总线同一时刻仅允许一个设备发送，但允许多个设备接收

总线的分类

数据总线（Data Bus）：简称DB，在CPU和RAM之间来回传送需要处理或是需要储存的数据。

地址总线（Address Bus）：简称AB，用来指定在RAM（Random Access Memory）之中储存的数据的地址

控制总线（Control Bus）：将微处理器控制单元（Control Unit）的信号，传送到周边设备

可靠性

可靠性指标

!image-20240920163743753

串联系统和并联系统

下图中，第一个示例为串联系统，第二个为并联系统

下图中有对应的计算公式

!image-20240920164157566

N模混合系统

性能指标

操作系统概念

考点1：操作系统的作用

考点2：特殊的操作系统

操作系统的作用

管理系统的硬件、软件、数据资源

控制程序运行

人机之间的接口

应用软件与硬件之间的接口

进程管理

存储管理

文件管理

作业管理

设备管理

特殊的操作系统

分类特点批处理操作系统单道批：一次一个作业入内存，作业由程序、数据、作业说明书组成
多道批：一次多个作业入内存，特点：多道、宏观上并行微观上串行分时操作系统采用时间片轮转的方式为多个用户提供服务，每个用户感觉独占系统
特点：多路性、独立性、交互性和及时性 实时操作系统实时控制系统和实时信息系统
交互能力要求不高，可靠性要求高（规定时间内响应并处理）网络操作系统方便有效共享网络资源，提供服务软件和有关协议的集合
主要的网络操作系统有：Unix、Linux和Windows Server系统分布式操作系统任意两台计算机可以通过通信交换信息
是网络操作系统的更高级形式，具有透明性、可靠性、高性能等特性微机操作系统Windows：Microsoft开发的图形用户界面、多任务、多线程操作系统
Linux：免费使用和自由传播的类Unix操作系统，多用户、多任务、多线程、多CPU的操作系统嵌入式操作系统运行在智能芯片环境中
特点：微型化、可定制（针对硬件变化配置）、实时性、可靠性、易移植性（HAL和BSP支持）

进程

考点1：线程的概念

考点2：进程的状态

线程的概念

进程的概念

进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCB）和数据块三部分组成。

PCB：PCB是进程存在的唯一标志。内容包含进程标识符、状态、位置信息、控制信息、队列指针（链接同一状态的进程）、优先级、现场保护区等。

进程和程序

进程与程序的区别：进程是程序的一次执行过程，没有程序就没有进程。

程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是。

进程和线程

进程的2个基本属性：可拥有资源的独立单位；可独立调度和分配资源的基本单位。

进程可以包含多个线程

线程之间可共享的内容有

内存地址空间

代码

数据

文件等

不可共享的内容有：

程序计数器

寄存器

栈

进程的状态

运行：当一个进程在CPU上运行时。

就绪：一个进程获得了除CPU外的一切所需资源，一旦得到处理机即可运行。

阻塞：阻塞也称等待或睡眠状态，一个进程正在等待某一事件(例如请求I/O等待I/O完成等)而暂时停止运行，此时即使把CPU分配给进程也无法运行，故称进程处于阻塞状态。

五态模型

!image-20240923152740676

挂起原因：

1. 进程过多，主存资源不足，此时必须将某些进程挂起，放到磁盘对换区，暂时不参与调度，以平衡系统负载；

2. 系统出现故障，或者是用户调试程序，也可能需要将进程挂起检查问题。

进程调度

考点1：PV操作的概念

考点2：信号量与PV操作

考点3：前趋图与PV操作

PV的概念

进程的同步与互斥

临界资源：诸进程间需要互斥方式对其进行共享的资源。（进程中访问临界资源的那段代码称为临界区）

互斥：如千军万马过独木桥，是一种间接制约关系，相当于独木桥制约了所有人。

互斥的简单释义其实就是：一个服务器的情况下，只能存在一个使用者，只有当当前使用者使用完成后，其他使用者才能进入服务器使用，这就是互斥，排斥其他人

同步：速度有差异，在一定情况停下等待，是一种直接制约关系，相当于速度直接制约了不同的进程。

同步简单来说，其实就是多个进程同时出发，但有的进程速度快，有的进程速度慢，快的就需要等待慢的来同步进行

PV操作

信号量：是一种特殊的变量。

信号量可以表示资源数量。

信号量为负数时还可以表示排队进程数。

P是荷兰语的Passeren，V是荷兰语的Verhoog。

!image-20240923160714633

信号量与PV操作

互斥模型

多个进程共享一台打印机问题（互斥模型）：

当使用打印机时，就将打印机上锁，即P(S)操作；

当打印机使用完成后，进行V(S)操作，将打印机解锁

这里的S代表互斥信号量，互斥信号量S的初值为1。

同步模型

!image-20240924095031511

生产者：

生产一个产品；

P(S1);

送产品到缓冲区；

V(S2);

消费者：

P(S2);

从缓冲区取出产品

V(S1);

消费产品

同步模型所需要确定的就是，当数据被生产后，消费者需要将其消费，所以V操作的先后并不重要，重要的是P操作的检查情况，保证同步的进行

前趋图与PV操作

PV操作应用

前趋图节点表示进程，箭头表示进程间的先后关系，前趋节点完成之后，才能执行后继节点。

!image-20240924111903906

复杂一点的前趋图，会有进程间的并行关系，会体现进程之间的直接制约关系

在执行D操作的时候，必须先去验证前趋节点是否已经准备就绪，也就是说，需要P(Sa)、P(Sb)、P(Sc)操作去验证ABC三个前趋节点是否已经完成；而PV操作是成对出现的，因此有了P操作，还需要三个V操作与之对应。

A完成之后，会有V(Sa)；

B完成之后，会有V(Sb)；

C完成之后，会有V(Sc)；

也就是说，在前趋图中，所有的箭线中的箭头流出会对应一个V操作，箭头流入对应一个P操作，这也就是PV操作，只是A完成后释放当前资源的操作叫做V操作，在D操作执行前需要保证A操作执行了的操作的叫做P操作

如下图所示，对应操作执行完成后，都会释放为V操作，并对下一流节点进行P操作，通过后则如此反复

!image-20240924112256051

死锁资源计算

死锁问题

所谓死锁，是指两个以上的进程互相都要对方已经占有的资源，导致无法继续运行下去的现象。

死锁的四大条件：

互斥

保持和等待

不剥夺

环路等待

死锁处理：

死锁的预防

打破四大条件

有序资源分配法

静态资源分配

死锁的避免

银行家算法

死锁的检测与解除

鸵鸟策略（不予理睬）

进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果进程在等待一件不可能发生的事，则进程就死锁了。而如果多个进程产生死锁，就会造成系统死锁。

系统不可能发生死锁的最小资源数（w-1）* m <= n

m：代表进程数量

w：代表每个进程需要的资源数量

n：代表总资源可用数量

进程资源图

如下图所示

!image-20240924145141083

第三图具体图意：先分析资源分配情况，列出剩余可用资源：此时已分配1个R1给进程P，剩余1个R1可用。

再判断申请后进程是否能够执行：P进程申请1个R1，系统有1个R1可用，P进程可成功执行，执行后释放占用的2个R1

段页式存储

考点1：页式存储

考点2：段式存储

考点3：段页式存储

页式存储

页式存储组织

页式存储：将程序与内存均划分为同样大小的块，以页为单位将程序调入内存。

将用户程序划分为固定大小的页面，内存也划分为相同大小的页面

此时用户程序被称为逻辑页，内存被称为物理页

!image-20240924152447906

物理块号又称页帧号

逻辑地址 = 页号 + 页内地址

物理地址 = 页帧号 + 页内地址

优点：利用率高，碎片小，分配及管理简单

缺点：增加了系统开销，可能产生抖动现象

页面淘汰依据

访问位为0

多个访问位为0时，考虑修改位为0

!image-20240925100753638

页面置换算法

最优（Optimal，OPT）算法（理想型）

随机（RAND）算法

先进先出（FIFO）算法：有可能产生“抖动”。例如，432143543215序列，用3个页面，比4个缺页要少

说明一下这里的先进先出算法，具体流程是这样的：

432143543215，3个页面

432，先进入对应的页面，此时轮到1，遵从先进先出原则，将4踢出页面并放入1，接着踢出3放入4，踢出2放入3，以此推类即可。

最近最少使用（LRU）算法：不会“抖动”，LRU的理论依据是“局部性原理”。

局部性原理：

时间局部性：刚刚被访问的内容，立即又被访问。

空间局部性：刚被访问的内容，临近的空间很快被访问

段式存储

段式存储组织

段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样。

示例图

!image-20240925104346122

起始位置记录后被称为基址，依次记录相应所需的长度，称为段长

段号不超过段长时，逻辑地址可以转换为对应的物理地址。

优点：多道程序共享内存，各段程序修改互不影响

缺点：内存利用率低，内存碎片浪费大

段页式存储

段页式存储：段式和页式的综合体。先分段，再分页。1个程序有若干个段，每个段中可以有若干页，每个页的大小相同，但每个段的大小不同。

示例图

优点：空间浪费小、存储共享容易、存储保护容易、能动态连接

缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降

磁盘管理

存取时间=寻道时间+等待时间，寻道时间是指磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间。

读取磁盘数据的时间应包括以下三个部分:

1. 找磁道的时间。

2. 找块（扇区）的时间，即旋转延迟时间。

3. 传输时间。

先来先服务（FCFS）

最短寻道时间优先（SSTF）

扫描算法（SCAN）- 电梯算法(双向扫描的过程)

循环扫描（CSCAN）算法(单向扫描)

FCFS

SSTF

解题步骤

最短移臂调度算法

这题应该如何操作，首先我们要确定15号柱面，最短移臂调度算法，是找离15号最近的柱面号，那么，我们先将柱面号和请求序列对应的找出，从小到大排列

12：1、5

19：2、4

23：3

28：6

找一下柱面号中距离15号柱面最近的->12，所以15或者51开头都行，接着找->19,所以24或42往后都行，然后以此类推即可。

IO管理软件

硬件：完成具体的I/O操作。

中断处理程序：I/O完成后唤醒设备驱动程序

设备驱动程序：设置寄存器，检查设备状态

设备无关I/O层：设备名解析、阻塞进程、分配缓冲区

用户级I/O层：发出I/O调用

文件管理

考点1：文件相关概念

考点2：树形目录结构（绝对路径与相对路径）

考点3：位示图

考点4：索引文件

文件相关概念

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

逻辑结构：有结构的记录式文件、无结构的流式文件。

物理结构：连续结构、链接结构、索引结构、多个物理块的索引表。

文件目录：

文件目录项/文件的说明/文件控制块FCB

基本信息项：文件名、文件的物理地址、文件长度和文件块数等

存储控制信息类：文件的存储权限：读写、执行权限等

（文件属性：只执行、隐含、只读、读/写、共享、系统）

使用信息类：文件建立日期、最后一次修改/访问日期、当前使用的信息打开文件的进程数以及在文件上的等待队列等

目录结构

一级目录结构：线性结构，查找速度慢，不允许重名和实现文件共享等

二级目录结构：主文件目录（MFD） + 用户目录（UFD）

三级目录结构：树型目录结构（多级目录结构）

树形目录结构

多级目录结构允许不同用户的文件可以具有相同的文件名

绝对路径：从盘符开始的路径

相对路径：是从当前目录开始的路径

全文件名：绝对路径 + 文件名

位示图

空闲存储空间的管理

太难了，听懵了，写不出来

索引文件

索引文件结构

!image-20240926154639175

一般的索引文件有13个节点，从0开始，0-12,13个节点存地址，地址去存物理盘块，盘块再去存内容。

索引可以分为：

直接索引

一级间接索引

二级间接索引

三级间接索引

如果一个存储结构不使用索引，那么他的存量就是 物理块数 \* 单位大小。

如果每个物理块的单位大小为 4K，则总空间为 4*13 = 52K

如果引入了一级间接索引，索引指向了具体的物理块号

我们假设第10个节点是一级间接索引，如果一个地址占用4个字节，一个物理盘块有4KB容量（因为4KB=1024``4B），那么在第10个物理块中就可以存放1024份地址，那么10号物理块中就可以存储1024份容量，就是10244KB = 4 MB的容量。

如果引入了二级间接索引，索引指向了中间索引，中间索引在指向具体的物理块号。

如果一个地址占用 4 个字节，一个物理盘块有 4KB 容量，那么在第 11 个物理块中就可以存放 1024 份地址，每份子地址可以再存储 1024 份二级地址，那么 11 号物理块就可以存储 1024 \* 1024 份容量，就是 1024 X 1024 X 4KB = 4GB 的容量。

间接索引的容量是通过物理盘块的大小去除以地址占用的字节后，在对应的间接索引中说明，可存放的地址容量，如果每个地址容量，还存在二级间接索引，那么就在对应的基础上，再存入对应的容量，如二级间接索引的意思

!image-20240926171648810

作业管理

作业的状态

!image-20240927092652319

作业调度算法

先来先服务法：谁先申请就先执行谁

时间片轮转法：将cpu按时间划分为一些资源，按时间片段轮转执行，当时间片到了后就执行

短作业优先法：会将作业的执行时间记录下来，谁的时间短就优先执行谁

最高优先权优先法：为作业标注优先权，标注后，谁的优先权比较高，就优先执行谁，默认优先权是一样的，如果分配了优先权，则会出现高权限抢夺低权限的资源情况

高响应比优先法：会将相关作业的响应比求出，谁的响应比高就优先响应

响应比 = （作业等待时间 + 作业执行时间） / 作业执行时间

数据库的基本概念

考点1：数据库体系结构

考点2：三级模式结构

考点3：数据仓库

数据库体系结构

集中式数据库系统

数据是集中的

数据管理是集中的

数据库系统的素有功能（从形式的用户接口到DBMS核心）都集中在DBMS所在的计算机

C/S结构 or B/S结构

客户端负责数据表示服务

服务端负责数据库服务

数据库系统分为前端和后端

ODBC（Oracle）、JDBC

分布式数据库

物理上分布、逻辑上集中

物理上分布、逻辑上分布

特点

透明性

并行数据库

共享内存式

无共享式

分布式数据库特点

数据独立性。除了数据的逻辑独立性与物理独立性外，还有数据分布独立性（分布透明性）。

集中与自治共享结合的控制结构。各局部的DBMMS可以独立地管理局部数据库，具有自治的功能。同时，系统又设有集中控制机制，协调各局部DBMS（数据库管理系统）的工作，执行全局应用。

适当增加数据冗余度。在不同的场地存储同一数据的多个副本，可以提高系统的可靠性和可用性，同时也能提高系统性能。（提高系统的可用性，即当系统中某个节点发生故障时，因为数据有其他副本在非故障场地上，对其他所有场地来说，数据仍然是可用的，从而保证数据的完备性。）

全局的一致性、可串行性和可恢复性。

分布式数据库透明性

分片透明：是指用户不必关心数据是如何分片的，它们对数据的操作在全局关系上进行，即如何分片对用户是透明的。

复制透明：用户不用关心数据库在网络中各个节点的复制情况，被复制的数据的更新都由系统自动完成。

位置透明：是指用户不必知道所操作的数据放在何处，即数据分配到哪个或哪些站点存储对用户是透明的

局部映像透明性（逻辑透明）：是最低层次的透明性，该透明性提供数据到局部数据库的映像，即用户不必关心DBMS支持哪种数据模型、使用哪种数据操纵语言，数据模型和操纵语言的转换是由系统完成的。因此，局部映像透明性对异构型和同构异质的分布式数据库系统是非常重要的。

三级模式结构

三级模式和两级映像

(视图级)外模式

逻辑独立性：数据的逻辑结构发生变化后，用户程序也可以不修改。但是为了保证应用程序能够正确执行，需要修改外模式和概念模式之间的映像。

(表级)概念模式

物理独立性：当数据的物理结构发生变化后，应用程序不用改变，但是为了能够保证应用程序能够正确执行，需要修改概念模式和内模式之间的映像。

数据仓库

数据仓库特点

面向主题：数据按主题组织

集成的：消除了源数据中的不一致性，提供整个企业的一致性全局信息

相对稳定的(非易失的)：主要进行查询操作，只有少量的修改和删除操作（或是不删除）

反映历史变化（随着时间变化）：记录了企业从过去某一时刻到当前各个阶段的信息，可对发展历程和未来趋势做定量分析和预测。

!image-20240929095633612

上图所展示的4个步骤

1. 数据预处理

2. 数据仓库存储

3. 数据分析

4. 数据展现

OLAP：联机分析系统

OLTP：联机事务系统

Data Extraction：数据清理

ETL：数据抽取的过程

数据库设计过程

下面说明对应过程所得出的内容

需求分析：数据流图、数据字典、需求说明书

概念结构设计：ER模型

逻辑结构设计：关系模式(考虑规范化问题)

物理设计：聚簇索引

概念设计模式

考点1：概念设计过程

考点2：E-R图

概念设计过程

!image-20240929155801590

集成的方法：

多个局部E-R图一次集成

逐步集成，用累加的方式一次集成两个局部E-R

集成产生的冲突及解决办法：（针对同一对象）

属性冲突：包括属性域和属性取值冲突。

命名冲突：包括同名异义和异名同义

结构冲突：包括同一对象在不同应用中具有不同的抽象，以及同一实体在不同局部E-R图中所包含的属性个数和属性排列次序不完全相同。

E-R图

E-R模型

!image-20240930092316156

实体：实体是现实世界中可以区别于其他对象的事件或事物。（实体集——实体的集合）

属性：属性是实体某方面的特性

联系：实体的联系分为实体内部的联系和实体与实习之间的联系。实体间的联系类型：`1:1`、`1:`、`:*`

属性

简单属性和复合属性

简单属性是原子的，不可再分的；

复合属性可以细分为更小的部分（即划分为别的属性）。

单值属性和多值属性

定义的属性对于一个特定的实体都只有单独的一个值，称为单值属性；

在某些特定情况下，一个属性可能对应一组值，称为多值属性。

NULL属性：表示无意义或不知道

派生属性：可以从其他属性得来

联系类型判断

!image-20240930100314005

一对一（1:1）

一对多（1：`*`）

多对多（``：``）

两个以上不同实体集之间的联系（三元联系）

多重度的确定（可根据语义直接转换）

以三元关系中的一个实体作为中心，假设另两个实体都只有一个实例：

若中心实体只有一个实例能与另两个实体的一个实例进行关联，则中心实体的连通数为`一`

若中心实体有多于一个实例能与另两个实体实例进行关联，则中心实体的连通数为`多`

同一实体集内的二元联系

!image-20240930104843740

拓展的E-R模型

弱实体：在现实世界中有一种特殊的依赖联系，该联系是指某实体是否存在对于另一些实体具有很强的依赖关系，即一个实体的存在必须以另一个实体为前提，而将这类实体称为弱实体，如家属与职工的联系，附件与邮件

特殊化：在现实世界中，某些实体一方面具有一些共性，另一方面还具有各自的特性，一个实体集可以按照某些特征区分为几个子实体

聚集：一个联系作为另一个联系的一端

上述是理论，下面简单描述一下

弱实体其实就是说依赖性很强的实体，不能单独存在，不能脱离主体，像附件不能单独存在一样

特殊化可以说明一个实体是有着与其他实体相同的特性，但拥有一些拓展的能力

聚集，类似第三方，中间的媒介来联系另一端

逻辑结构设计

考点1：关系模式相关概念

考点2：E-R图转关系模式

关系模式相关概念

数据模型

层次模型

网状模型

关系模型

面向对象模式

注：数据模型三要素：数据结构、数据操作、数据的约束条件

E-R图转关系模式

一个实体型必须转换为一个关系模式

联系转关系模式：

!image-20241008094429009

1. 一对一的转换有两种方式

独立的关系模式：并入两端主键及联系自身属性。（主键：任一端主键）

归并（任意一端）：并入另一端主键及联系自身属性。（主键：保持不变）

2. 一对多联系的转换有两种方式

独立的关系模式：并入两端主键及联系自身属性。（主键：多端主键）

归并（多端）：并入另一端主键及联系自身属性。（主键：保持不变）

3. 多对多联系的转换只有一种方式

独立的关系模式：并入两端主键及联系自身属性。（主键：两端主键的组合键）

关系代数

了解关于表之间的交集、并集、差集、笛卡尔积、投影(垂直方向获取data)、选择(水平方向条件筛选data)

自然连接

自然连接的列数是由：两者的列数之和-重复列数

规范化理论

函数依赖

函数依赖，可以理解为通过x可以计算出y，而y是依赖于x所得出的结果

另类的说法，从数据库层面来说，假设有一个学号一个姓名，我们可以通过学号去查出姓名，但没办法通过姓名查出学号(因为姓名有可能重复)

这里存在其他两种函数依赖，一种是部分函数依赖，另一种是传递函数依赖

!image-20241009111155294

部分函数依赖呢，可以这么说嘛，通过二者的组合键来推出一个值，这是通过组合键中的一部分，可以确定某个属性，这个部分，就体现在了组合键中

传递函数依赖，其实就是通过A可以推出B，B可以推出C，那么A就可以推出C，因为B传递了C，当然，这是有条件的，B是不可以推出A的，因为当B推出A时，二者等价，等价就不存在传递函数依赖的关系了

价值与用途

非规范化的关系模式，可能存在的问题包括：数据冗余、更新异常、插入异常、删除异常

候选关键字

超键是用来唯一标识元组的，候选键也是用来唯一标识元组的，当超键消除多余属性后，就变为了候选键，候选键从中任选一个，就是主键

怎么说超键与候选键的区别呢，这里给出一个例子，(学号、姓名、性别)，由学号、姓名可以组成超键，它可以唯一标识元组，性别这个值，当然它不能作为候选键，因为候选键不能有多余属性，而学号和姓名，其中一个就是多余属性，因为我们可以通过学号就能确定性别，此时姓名就冗余了，多余了

主键就好比从多个候选键中选出一个候选人作为主键来使用

求候选键

1. 将关系模式的函数依赖关系用“有向图”的方式表示

2. 找入度为0的属性(没有任何一个箭头指向它)，并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有结点，则该属性集即为关系模式的候选键

3. 若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将一些中间结点(既有入度，也有出度的节点)并入入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键

好的，已知上述信息后，我们可以看一下下面这道题，给定了R(关系节点)，F(每一条指向的线段)

我们找出入度为0的点，这里看出是A1，以A1作为起点，来遍历，发现A1到了A2，可以往A4、A3方向遍历，可以完全遍历，那么A1就是R的候选键

!image-20241009140723970

第二题，先找出入度为0的点，A、B、D、C，ABC组合后，可以遍历上面的结点，C可以遍历IJ，那么ABCD组合后，才能遍历所有的结点

!image-20241009141307080

范式

数据库范式，想要达到第二范式，必须先达到第一范式，想要达到第三范式，必须先达到第二范式

主属性：主属性属于候选键的一部分

非主属性：非主属性就是不属于候选键的一部分

数据库第一范式：属性值都是不可分的原子值

数据库第二范式：消除非主属性对候选键的部分依赖

数据库第三范式：消除非主属性对候选键的传递依赖

数据库BC范式：消除主属性对候选键的传递依赖

第一范式

第一范式（1NF）：在关系模式R中，当且仅当所有域只包含原子值，即每个分量都是不可再分的数据项，则称R是第一范式。

简单说明第一范式，其实就是将，列项，分为不可再分的值，细分列项

第二范式

第二范式（2NF）：当且仅当R是1NF，且每一个非主属性完全依赖主键(不存在部分依赖)时，则称R是第二范式。

不需要为表移除后所导致的其他问题而苦恼，通过第二范式，你可以让表的独立性大大的提高

第三范式

第三范式（3NF）：当且仅当R是1NF，且E中没有非主属性传递依赖于码时，则称R是第三范式。

第三范式让冗余的字段结合起来，作为一个新的字段集合

BC范式

BC范式（BCNF）：设R是一个关系模式，F是它的依赖集，R属于BCNF当且仅当其F中每个依赖的决定因素必定包含R的某个候选码。

模式分解

听了一大堆，一句没听懂

数据库并发控制

原子性：要么一次通过，要么一次全失败

一致性：在事务执行之前，数据是一致的状态，在事务执行后，数据也是一致的状态

隔离性：事务之间是独立进行、互不影响

持续性：事务执行之后，结果是持续的

并发问题示例

封锁协议

一级封锁协议。事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。可防止丢失修改

二级封锁协议。一级封锁协议加上事务T在读取数据R之前先对其加S锁，读完后即可释放S锁。可防止丢失修改，还可防止读脏数据

三级封锁协议。一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。可防止丢失修改、防止读脏数据与防止数据重复读

两段锁协议。可串行化。可能发生死锁

S锁：读锁

X锁：写锁

读锁加入后，还可以加读锁，但不能加写锁

写锁加入后，不能加入任何锁

数据库完整性约束

实体完整性约束

参照完整性约束

用户自定义完整性约束

触发器

数据库安全

措施说明用户标识和鉴定最外层的安全保护措施，可以使用用户账户、口令及随机数检验等方式存取控制对用户进行授权，包括操作类型（如查找、插入、删除、修改等动作）和数据对象（主要是数据范围）的权限密码存储和传输对远程终端信息用密码传输视图的保护对视图进行授权审计使用一个专用文件或数据库，自动将用户对数据库的所有操作记录下来

数据备份与恢复

冷备份也称为静态备份，是将数据库正常关闭，在停止状态下，将数据库的文件全部备份(复制)下来。

热备份也称为动态备份，是利用备份软件，在数据库正常运行状态下，将数据库中的数据文件备份出来。

备份方式\优缺点优点缺点冷备份非常快速的备份方法(只需复制文件)；容易归档(简单复制即可)；容易恢复到某个时间点上(只需将文件再复制回去)；能与归档方法相结合，做数据库“最佳状态”的恢复；低度维护，高度安全单独使用时，只能提供到某一时间点的恢复；在实施备份的券过程中，数据库必须要做备份而不能做其他工作；若磁盘空间有限，只能复制到磁带等其他外部存储设备中，速度会很慢；不能按表或按用户恢复热备份可在表空间或数据库文件级备份，备份的时间短；备份时数据库仍然可使用；可达到秒级恢复(恢复到某一时间点上)；可对几乎所有数据库实体做恢复；恢复是快速的不能出错，否则后果严重；若热备份不成功，所得结果不可用于时间点的恢复；因难于维护，所以要特别小心，不允许“以失败告终”

完全备份：备份所有数据

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

增量备份：备份上一次备份之后变化的数据（仅备份变化的数据，其他数据不备份）

1. 静态海量转储：在系统中无运行事务时进行，每次转储全部数据库。

2. 静态增量转储：在系统中无运行事务时进行，每次只转储上一次转储后更新过的数据。

3. 动态海量转储：转储期间允许对数据库进行存取或修改，每次转储全部数据库。

4. 动态增量转储：转储期间允许对数据库进行存取或修改，每次只转储上一次转储后更新过的数据。

日志文件：事务日志是针对数据库改变所做的记录，它可以记录针对数据库的任何操作，并将记录结果保存在独立的文件中

数据库故障与恢复

故障关系故障原因解决方法事务本身的可预期故障本身逻辑在程序中预先设置Rollback语句事务本身的不可预期故障算术溢出、违反存储保护由DBMS的恢复子系统通过日志，撤销事务对数据库的修改，回退到事务初始状态系统故障系统停止运转通常使用检查点法介质故障外存被破坏一般使用日志重做业务

数据仓库与数据挖掘

OLAP服务器：联机分析处理服务器

数据挖掘方法分类

方法

决策树

神经网络

遗传算法

关联规则挖掘算法

分类

关联分析：挖掘出隐藏在数据间的相互关系。

序列模式分析：侧重点是分析数据间的前后关系（因果关系）。

分类分析：为每一个记录赋予一个标记再按标记分类。

聚类分析：分类分析法的逆过程。

反规范化技术

由于规范化会使表不断的拆分，从而导致数据表过多。这样虽然减少了数据冗余，提高了增、删、改的速度，但会增加查询的工作量。提高了增、删、改的速度，但会增加查询的工作量。系统需要进行多次连接，才能进行查询操作，使得系统效率大大下降

解决方法

增加派生性冗余列

增加冗余列

重新组表

分割表

计算机网络

OSI/RM七层模型

层次名称主要功能主要设备及协议 7应用层实现具体的应用功能POP3、FTP、HTTP、Telnet、SMTP、DHCP、TFTP、SNMP、DNS 6表示层数据的格式与表达、加密、压缩5、6、7这三层是一样的 5会话层建立、管理和终止会话 4传输层端到端的连接TCP、UDP 3网络层分组传输和路由选择三层交换机、路由器
ARP、RARP、IP、ICMP、IGMP 2数据链路层传送以帧为单位的信息网桥、交换机、网卡
PPTP、L2TP、SLIP、PPP 1物理层二进制传输中继器、集线器

网络技术标准与协议

TCP/IP协议：Internet，可拓展，可靠，应用最广，牺牲速度和效率

IPX/SPX协议：NOVELL,路由，大型企业网

NETBEUI：IBM，非路由，快速

应用层应用层表示层会话层传输层传输层 Internet层网络层数据链路层网络接口层物理层

TCP三次握手

DHCP协议

1. 客户机/服务器模型

2. 租约默认为8天

3. 当租约过半时，客户机需要向DHCP服务器申请续租；

4. 当租约超过87.5%时，如果仍然没有和当初提供IP的DHCP服务器联系上，则开始联系其他的DHCP服务器

5. 固定分配、动态分配和自动分配

6. 169.254.X.X和0.0.0.0

DNS协议

!image-20241012105621361

主机向本地域名服务器的查询采用递归查询。

本地域名服务器向根域名服务器的查询通常采用迭代查询。

递归查询：服务器必须回答目标IP与域名的映射关系。

迭代查询：服务器收到一次迭代查询回复一次结果，这个结果不一定是目标IP与域名的映射关系，也可以是其他DNS服务器的地址。

当一个客户端（例如你的电脑或手机）向 DNS 服务器（通常是你的本地 DNS 服务器或 ISP 的 DNS 服务器）发送请求时，如果该服务器没有所需的信息，那么它有责任自己去其他 DNS 服务器中查找这些信息。

服务器会代表客户端执行所有必要的进一步查询，直到它获得答案。然后，它将答案返回给客户端。这种查询方式称为递归查询，因为服务器必须递归地完成客户端的查询。

这种查询方式简化了客户端的工作，但为服务器增加了更多的工作。

当一个 DNS 服务器（例如本地 DNS 服务器）向其他 DNS 服务器（例如根域服务器或 TLD 服务器）发送查询时，它可能执行一个迭代查询。

在迭代查询中，被查询的服务器提供关于如何获得答案的最佳信息，但并不实际为查询者提供最终答案。例如，当本地 DNS 服务器查询根服务器以获取 example.com 的 IP 地址时，根服务器可能只告诉它去查询一个特定的 .com TLD 服务器。

之后，本地 DNS 服务器再继续查询 .com TLD 服务器，然后可能被告知去查询 example.com 的权威 DNS 服务器。这个过程一直持续，直到本地 DNS 服务器得到最终的答案。

这种查询方式意味着每一步都需要请求者（在这种情况下是本地 DNS 服务器）进行下一步的查询，而不是被查询的服务器自己去做。

相当于说，递归查询是服务器自己去帮你找这个网络地址，而迭代查询是你本地客户端去找这个网络地址，服务器告诉你去哪找或者直接提供给你

拓扑结构

按分布范围分

局域网（LAN）

城域网（MAN）

广域网（WAN）

因特网

按拓扑结构分

总线型

星型

环型

网络规划与设计

网络规划原则

实用性原则

开放性原则

先进性原则

网络设计任务

确定网络总体目标

确定总体设计原则

通信子网设计

资源子网设计

设备选型

网络操作系统与服务器资源设备

网络安全设计

网络设计原则

可用性：指网络或网络设备可用于执行预期任务时间所占总量的百分比。

可靠性：网络设备或计算机持续执行预定功能的可能性。

可恢复性：指网络从故障中恢复的难易程度和时间。

适应性：指在用户改变应用要求时网络的应变能力。

可伸缩性：指网络技术或设备随着用户需求的增长而扩充的能力。

网络实施原则

可靠性原则

安全性原则

高效性原则

可扩展性原则

网络实施步骤

工程实施计划

网络设备到货验收

设备安装

系统测试

系统试运行

用户培训

系统转换

逻辑网络设计

利用需求分析和现有网络体系分析的结果来设计逻辑网络结构，最后得到一份逻辑网络设计文档

输出内容包括以下几点：

逻辑网络设计图

IP地址方案

安全方案

具体的软硬件、广域网连接设备和基本服务

招聘和培训网络员工的具体说明

对软硬件、服务、员工和培训的费用初步估计

物理网络设计

物理网络设计是对逻辑网络设计的物理实现，通过对设备的具体物理分布、运行环境等确定，确保网络的物理连接符合逻辑连接的要求。输出如下内容：

网络物理结构图和布线方案

设备和部件的详细列表清单

软硬件和安装费用的估算

安装日程表，详细说明服务的时间以及期限

安装后的测试计划

用户的培训计划

分层设计

!image-20241012140129547

接入层：向本地网段提供用户接入

汇聚层：网络访问策略控制、数据包处理、过滤、寻址

核心层：数据交换

IP地址与子网划分

IP地址

1. 子网掩码

2. 将一个网络划分为多个子网（取部分主机号当子网号）

3. 将多个网络合并成一个大的网络（取部分网络号当主机号）

例1，将B类IP地址168.195.0.0划分成27个子网，子网掩码为多少？

首先需要将ip地址转换成二进制

1010 1000 1100 0011 0000 0000 0000 0000

如何划分对应的位数呢，我们从后续的0中借位，假设需要借的位数为k，需要划分的子网为N

那么一位0就相当于2的1 = 2，2位0是2的2 = 4，依次继续

那么我们需要满足27位，也就是N=27，借5位就是2的5次 = 32

那么，原来的网络号则是1，子网号也是1，而主机号是0

则结果是：1111 1111 1111 1111 1111 1000 0000 0000

这就是子网掩码，如果我们想将其划成60个子网，则再借一个主机号，让主机号为1即可，也就是2的6次64即可

最后将结果转为十进制即可

`1111 1111 1111 1111 1111 1000 0000 0000` = 255.255.248.0

例2，将B类IP地址168.195.0.0划分成若干子网，每个子网内有主机700台，则子网掩码为多少？

这个题应该反推，700台主机需要多少个主机号那么2的k次方 - 2 需要 >= 700

那么至少需要10个主机号才能满足700台主机,其他的就可以作为网络号了

接着将其转为10进制即是子网掩码

无分类编址(无类域间路由)

!image-20241012144349784

特殊含义IP地址

IP说明 127网段回播地址网络号全0地址当前子网中的主机全1地址本地子网的广播主机号全1地址特定子网的广播 10.0.0.0/810.0.0.1至10.255.255.254 172.16.0.0/12172.16.0.1至172.31.255.254 192.168.0.0/16192.168.0.1至192.168.255.254 169.254.0.0保留地址，用于DHCP失效(Win) 0.0.0.0保留地址，用于DHCP失效(Linux)

无线网

无线局域网（WLAN，802.11，WIFI）

无线城域网（WMAN，802.16，WiMax）

无线广域网（WWAN，3G/4G）

无线个人网（WPAN，802.15，Bluetooth）

优势：

移动性

灵活性

成本低

容易扩充

接入方式

有接入点模式

无接入点模式

网络接入技术

有线接入

公用交换电话网络（PSTN）

数字数据网（DDN）

综合业务数字网（ISDN）

非对称数字用户线路（ADSL）

同轴光纤技术（HFC）

无线接入

IEEE 802.11（WIFI）

IEEE 802.15（蓝牙Bluetooth）

红外（IrDA）

WAPI

3G/4G

WCDMA

CDMA2000

TD-SCDMA

LTE-Advanced

WirelessMAN-Advanced(802.16m)(WiMAX)

IPv6

IPv6是设计用于替代现行版本IP协议（IPv4）的下一代IP协议。

（1）IPv6地址长度为128位，地址空间增大了（2的96次方）倍

（2）灵活的IP报文头部格式。使用一系列固定格式的扩展头部取代了IPV4中可变长度的选项字段。IPv6中选项部分的出现方式也有所变化，使路由器可以简单路过选项而不做任何处理，加快了报文处理速度；

（3）IPv6简化了报文头部格式，字段只有8个，加快报文转发，提高了吞吐量；

（4）提高安全性。身份认证和隐私权是IPv6的关键特性；

（5）支持更多的服务类型；

（6）允许协议继续演变，增加新的功能，使之适应未来技术的发展；

单播地址（Unicast）：用于单个接口的标识符。

任播地址（Anycast）：泛播地址。一组接口的标识符，IPv4广播地址。

组播地址（Multicast）：IPv6中的组播在功能上与IPv4中的组播类似。

系统安全分析与设计

信息系统安全属性

安全属性

保密性：最小授权原则、防暴露、信息加密、物理保密

完整性：安全协议、校验码、密码校验、数字签名、公证

可用性：综合保障(IP过滤、业务流控制、路由选择控制、审计跟踪)

不可抵赖性：数字签名

对称加密

常见对称密钥加密算法：加密时使用的密钥和解密时是完全一致的

缺陷

加密强度不高

密钥分发困难

DES：替换+移位、56位密钥、64位数据块、速度快、密钥易产生

3DES（三重DES）：两个56位的密钥K1、K2

加密：K1加密->K2解密->K1加密

解密：K1解密->K2加密->K1解密

AES：高级加密标准Rijndael加密法，是美国联邦政府采用的一种区块加密标准。

这个标准用来替代原先的DES。对其要求是“至少与3DES一样安全”。

RC-5：RSA数据安全公司的很多产品都使用了RC-5。

IDEA算法：128位密钥、64位数据块、比DES的加密性好、对计算机功能要求相对低，PGP。

!image-20241014094927361

非对称加密

非对称加密技术：加密的密钥和解密的密钥是使用的不同密钥

缺陷：

加密速度慢

不适用于大数据量

!image-20241014095527686

常见的非对称密钥加密算法：

RSA:512位（或1024位）密钥、计算量极大、难破解

Elgamal：其基础是Diffie-Hellman密钥交换算法

ECC：椭圆曲线算法

其他非对称算法包括：背包算法、Rabin、D-H

信息摘要

单向散列函数（单向Hash函数）、固定长度的散列值

常用的消息摘要算法有MD5、SHA，市场上广泛使用的MD5，SHA算法的散列值分别为128和160位，由于SHA通常采用的密钥长度较长，因此安全性高于MD5

信息摘要其实就是从原内容通过消息摘要算法破坏性的解析特征值得出一个对应位数的值，作为信息摘要和内容一起发给其他用户，信息摘要起到了一个验证内容完整性的作用

数字签名

一般信息传输时，是这样一个流程

将信息发送给B，明文发送，并将文章产生信息摘要，用A的私钥加密后生成了数字签名，传输给B，B通过A的公钥解密(只有通过公钥和私钥一起，才能解密)，因为私钥只有A有，所以B解析出了信息摘要（B通过A的公钥解析出了A的信息摘要，说明这个信息是A的，这就是数字签名），将接收到的文章产生信息摘要进行比对，无误后说明就没问题了

数字签名是表示身份的，没有保密性，通过谁的公钥打开了这个包，那么这个包就是谁发生的

数字信封与PGP

发送方将原文用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方。

接收方收到电子信封，用自己的私钥解密信封，取出对称密钥解密得出原文。

PGP可以用于电子邮件，也可以用于文件存储。采用了杂合算法，包括IDEA、RSA、MD5、ZIP数据压缩算法。

PGP承认两种不同的证书格式：PGP证书和X.509证书

PGP证书包含PGP版本号、证书持有者的公钥、证书持有者的信息、证书拥有着的数字签名、证书的有效期、密钥首选的对称加密算法。

X.509证书包含证书版本、证书的序列号、签名算法标识、证书有效期、以下数据：证书发行商名字、证书主体名、主体公钥信息、发布者的数字签名。

各个网络层次的安全保障

网络威胁与攻击

威胁名称描述重放攻击（ARP）所截获的某次合法的通信数据拷贝，出于非法的目的而被重新发送。拒绝服务（DOS）对信息或其它资源的合法访问被无条件地阻止。窃听用各种可能的合法或非法的手段窃取系统中的信息资源和敏感信息
例如对通信线路中传输的信号进行搭线监听，或者利用通信设备在工作过程中产生的电磁泄露截取有用信息等。业务流分析通过对系统进行长期监听，利用统计分析方法对诸如通信频度、通信的信息流向、通信总量的变化等参数进行研究，从而发现有价值的信息和规律。信息泄露信息被泄露或透露给某个非授权的实体。破坏信息的完整性数据被非授权地进行增删、修改或破坏而受到损失非授权访问某一资源被某个非授权的人、或以非授权的方式使用。假冒通过欺骗通信系统（或用户）达到非法用户冒充成为合法用户，或者特权小的用户冒充成为特权大的用户的目的。黑客大多是采用假冒进行攻击。旁路控制攻击者利用系统的安全缺陷或安全性上的脆弱之处获得非授权的权利或特权。例如，攻击者通过各种攻击手段发现原本应保密，但是却又暴露出来的一些系统“特性”。利用这些“特性”，攻击者可以绕过防线守卫者侵入系统的内部。授权侵犯被授权以某一目的使用某一系统或资源的某个人，却将此权限用于其它非授权的目的，也称作“内部攻击”。特洛伊木马软件中含有一个察觉不出的或者无害的程序段，当它被执行时，会破坏用户的安全。陷阱门在某个系统或某个部件中设置了“机关”，使得当提供特定的输入数据时允许违反安全策略。抵赖这是一种来自用户的攻击，比如：否认自己曾经发布过的某条消息、伪造一份对方来信等。

防火墙

数据结构与算法基础

数组

数组类型存储地址计算一维数组a`[n]`a[i]的存储地址为：a+i*len 二维数组`a[m][n]`a`[i][j]`的存储地址（按行存储）为：a+(i``n+j)``len
a`[i][j]`的存储地址（按列存储）为：a+(j``m+i)``len

稀疏矩阵

线性表

顺序表和链表

线性表分为顺序表和链表

下图为概念图示

链表的基本操作

顺序存储和链式存储对比

队列与栈

理解示意图

后续这里的数据结构与算法讲的不是很好，后面单独有效的去学习数据结构与算法

软件开发模型

瀑布模型：送代模型/送代开发方法

演化模型：快速应用开发

增量模型：构件组装模型/基于构件的开发方法

螺旋模型：统一过程/统一开发方法

快速原型模型：敏捷开发方法

喷泉模型：模型驱动的开发方法

V模型：基于架构的开发方法

瀑布模型(SDLC)

软件计划

需求分析

软件设计

程序编码

软件测试

运行维护

其他经典模型

增量模型与螺旋模型

增量模型是逐步开发，开发一部分就放出去一部分

!image-20241015145255711

V模型、喷泉模型与RAD

!image-20241015145624482

构建组装模型(CBSD)

!image-20241016103324485

统一过程

听了没啥用，全是理论，刷题完事了

面向对象

面向对象基本概念

对象

类（实体类、边界类、控制类

抽象

封装

继承与泛化

多态

接口

消息

组件

模式和复用

设计原则

单一职责原则：设计目的单一的类

开放-封闭原则：对扩展开放，对修改封闭

李氏（Liskov）替换原则：子类可以替换父类

依赖倒置原则：要依赖于抽象，而不是具体实现；针对接口编程，不要针对实现编程

接口隔离原则：使用多个专门的接口比使用单一的总接口要好

组合重用原则：要尽量使用组合，而不是继承关系达到重用目的

迪米特（Demeter）原则（最少知识法则）：一个对象应当对其他对象有尽可能少的了解

UML

设计模式

设计模式的概念

架构模式：软件设计中的高层决策，例如C/S结构就属于架构模式，架构模式反映了开发软件系统过程中所作的基本设计决策

设计模式：主要关注软件系统的设计，与具体的实现语言无关

惯用法：是最低层的模式，关注软件系统的设计与实现，实现时通过某种特定的程序设计语言来描述构件与构件之间的关系。每种编程语言都有它自己特定的模式，即语言的惯用法。例如引I用-计数就是C++语言中的一种惯用法

设计模式的分类

创建型模型

设计模式名称简要说明 Abstract Factory
抽象工厂模式提供一个接口，可以创建一系列相关或相互依赖的对象，而无需指定它们具体的类 Builder
构建器模式将一个复杂类的表示与其构造相分离，使得相同的构建过程能够得出不
同的表示 FactoryMethod
工厂方法模式定义一个创建对象的接口，但由子类决定需要实例化哪一个类。工厂方法使得子类实例化的过程推迟 Prototype
原型模式用原型实例指定创建对象的类型，并且通过拷贝这个原型来创建新的对象 Singleton
单例模式保证一个类只有一个实例，并提供一个访问它的全局访问点

结构型模式

设计模式名称简要说明速记关键字 Adapter
适配器模式将一个类的接口转换成用户希望得到的另一种接口。它使原本不相容的接口得以协同工作转换接口转换接口 Bridge
桥接模式将类的抽象部分和它的实现部分分离开来，使它们可以独立地变化继承树拆分 Composite
组合模式将对象组合成树型结构以表示“整体-部分”的层次结构，使得用户对单个对象和组合对象的使用具有一致性树形目录结构 Decorator
装饰模式动态地给一个对象添加一些额外的职责。它提供了用子类扩展功能的一个灵活的替代，比派生一个子类更加灵活附加职责 Facade
外观模式定义一个高层接口，为子系统中的一组接口提供一个一致的外观，从而简化了该子系统的使用对外统一接口 Flyweight
享元模式提供支持大量细粒度对象共享的有效方法 Proxy
代理模式为其他对象提供一种代理以控制这个对象的访问

行为型模式

设计模式名称简要说明速记关键字 Chain of Responsibility
职责链模式通过给多个对象处理请求的机会，减少请求的发送者与接收者之间的耦合。将接收对象链接起来，在链中传递请求，直到有一个对象处理这个请求传递职责 Command
命令模式将一个请求封装为一个对象，从而可用不同的请求对客户进行参数化，将请求排队或记录请求日志，支持可撤销的操作日志记录，可撤销 Interpreter
解释器模式给定一种语言，定义它的文法表示，并定义一个解释器，该解释器用来根据文法表示来解释语言中的句子 Iterator
选代器模式提供一种方法来顺序访问一个聚合对象中的各个元素。而不需要暴露该对象的内部表示 Mediator
中介者模式用一个中介对象来封装一系列的对象交互。它使各对象不需要显式地相互调用，从而达到低耦合，还可以独立地改变对象间的交互不直接引用 Memento
备忘录模式在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，从而可以在以后将该对象恢复到原先保存的状态 Observer
观察者模式定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并自动更新 State
状态模式允许一个对象在其内部状态改变时改变它的行为状态变成类 Strategy
策略模式定义一系列算法，把它们一个个封装起来，并且使它们之间可互相替换，从而让算法可以独立于使用它的用户而变化多方案切换 TemplateMethod
模板方法模式定义一个操作中的算法骨架，而将一些步骤延迟到子类中，使得子类可以不改变一个算法的结构即可重新定义算法的某些特定步骤 Visitor
访问者模式表示一个作用于某对象结构中的各元素的操作，使得在不改变各元素的类的前提下定义作用于这些元素的新操作

数据流图(DFD)

数据流图的基本概念

数据字典

符号含义举例说明 =被定义为 +与x=a+b，表示x由a和b组成 [...,...]或[...\...]或x=[a,b],x=[a\b],表示x由a或由b组成 {...}重复x={a},表示x由0个或多个a组成 (...)可选x=(a),表示a可在x中出现，也可以不出现

数据流图平衡原则

父图与子图之间的平衡

子图内平衡

数据库设计

数据库设计过程

ER模型

转换的基本原则是：实体和联系分别转换成关系，属性则转换成相应关系的属性。

一对一联系

一对多联系

多对多联系

多元联系