04-计算机类专业知识笔试篇（常考、易错）
快速换算
2^10=K，2^20=M，2^30=G（计组、操作系统）
G=10^9，M=10^6，K=10^3（计网）
ms=10^-3,us=10^-6,ns=10^-9
八进制、十六进制转10进制都要先换算成二进制
牢记：8421，牢记2^n
目录
4. 调度机制（先来先服务、最短作业优先、优先级调度、高响应比调度、时间片轮转、多级反馈队列）
一、数据结构与算法
1. 时间复杂度计算
通常情况下：内层代码执行次数的级别（幂数）
等差数列求和：
等比数列求和：
2. 链表插入删除
插入：先管插入元素的next
删除：先定位要删的元素
双向链表插入，可画图示意，处理好所有指针即可
3. 栈和队列
栈：数值转换、括号匹配、行编辑程序（输入法）
链式队列：入队时在队尾插入，出队时在队头删除
4. 数据与特殊矩阵！三元组
1.二维数组a[m,n]，行存储，Loc(a[i,j])=Loc(a[0,0])+(i*n+j)*l（l为每个单元占几个单位）
2.行存储，上三角矩阵a[i,j]存到一维数组B中的下标：（2n-i-1)*(i/2)+j
3.行存储，下三角矩阵：（i+1)*(i/2)+j
4.行存储，三对角矩阵：2i+j
5.如果采用三元组表存储稀疏矩阵 M，除了三元组表外，还需要保存的是该稀疏矩阵 M 的行数（rows）和列数（cols），因为三元组表只存储了稀疏矩阵中非零元素的值及其所在的行列下标，而没有存储稀疏矩阵的整体尺寸。因此，需要额外保存稀疏矩阵 M 的行数和列数信息，以便在对其进行各种运算时能正确地按照矩阵的规模进行操作。
5. 树和二叉树
1. 二叉树，满二叉树、完全二叉树：满二叉树还没满的状态
二叉树第i层至多有2^（i-1）个节点
深度为k的二叉树至少有k个节点，至多有2^k-1个节点
2. 二叉树顺序访问：
先序遍历：根结点、先序遍历左子树、先序遍历右子树
中序遍历：中序遍历左子树、根结点、中序遍历右子树
后序遍历：后序遍历左子树、后序遍历右子树、根结点
先(根)序遍历（根左右）：A B D H E I C F J K G
中(根)序遍历（左根右） : D H B E I A J F K C G
后(根)序遍历（左右根） : H D I E B J K F G C A
3. 线索二叉树：
结构：lchild,ltag,data,rtag,rchild
ltag=0,表示lchild为左子女指针，ltag=1,表明lchild为前趋线索。rtag同理。
所以当ltag=rtag=1时，该节点为叶子结点。
先找顺序，再找每个节点的前趋和后继指向，如果没有树的分叉能到，那就画虚线
4. 树的存储表示
双亲表示法（data，parent（父亲节点编号，编号按层序遍历，从0编辑）），一组连续的单元（线性表顺序存储，相当于数组）
子女链表表示法（data，first），这个是线性表，first为链表，子节点编号、从左到右
子女-兄弟链表表示法：全链表，左指向最左的孩子，右指向兄弟
5.树、森林、二叉树的转换
树转二叉树：现将同一层的兄弟节点连接起来，只留下每个节点最左侧的一个，其余剪掉，旋转后即可得到二叉树（旋转规则：左孩子为孩子，右孩子为兄弟）
森林转二叉树：先将森林中所有的树转成二叉树，再按照（左子树、根结点）、（右子树根节点+右子树的左子树）、右子树的右子树进行拼接
二叉树转森林、树：先用逆方法剪枝，再用逆方法转换成树（左孩子为孩子，右孩子为兄弟）
注意：二叉树转的森林和树是唯一的
5.树、森林的遍历
树、森林的遍历分为深度优先和广度优先
树的深度优先分为：先序遍历和后序遍历，对应其二叉树的先序遍历和中序遍历
森林的深度优先分为：先序遍历和中序遍历，对应其二叉树的先序遍历和中序遍历
树的广度优先：层序遍历，自左向右，逐层访问
森林的广度优先：层序遍历（不是逐一访问子树，而是森林中的同一层访问）
6. 赫夫曼树（最优二叉树）
带权路径长度：（（外结点值）x（该节点到根节点的路径））求和
赫夫曼树（最优二叉树）：带权路径长度最短
构建过程：逐次选两个根节点权值最小的作为左右子树，新的根节点权值为左右两节点权值之和。（如果有未参与的节点和树根相同，优先选择未参与的节点）
平均加权长度=带权路径长度/外节点值之和
7.赫尔曼编码（长度最短的前缀编码）
先构建赫尔曼数，再根据左0右1的方式构建编码
（编码：从根节点到叶节点（自上向下），读编码（左0右1））
8.定长编码
定长编码的结点肯定在同一层，这样才能编码长度一致（从根节点到结点的路径长度一致）
9. 树的节点：
注意第i层的n叉树，节点有n^(i-1)个，总节点要层层累加
10. B树关键字删除。注意此处的[m/2]均为上取整，2.5的上取整为3
情况 1：要删除的关键字在叶子节点中。
- 直接删除该关键字。
情况 2：要删除的关键字在非叶子节点中。
- 找到该关键字的前驱（最大关键字）或后继（最小关键字）。
- 将前驱或后继替换到要删除的关键字位置，然后递归地删除前驱或后继关键字。
情况 3：要删除的关键字在一个子节点中，并且该子节点的关键字数少于 [m/2]-1（m为树的阶数，题目里有或者看数最多有几个分支）
- 需要通过借用或合并来调整
- 借用（如果有一侧能借就借）：
- 如果左兄弟或右兄弟的关键字数大于[m/2]-1，可以从兄弟节点借用一个关键字，并将原父节点的关键字下移到。
- 合并（两侧都不能借才合并）：
- 如果兄弟节点的关键字数也少于[m/2]-1，则可以将当前节点与一个兄弟节点合并。
- 将父节点中的分隔关键字下移到合并后的节点中，然后删除父节点中的该关键字。
反向思维解题：
按照关键字大小前后分子节点关键字，查看分出来的子关键字是不是满足大于[m/2]-1即可
平衡二叉树：
定义：树的左右高度差不超过1
平衡二叉树的关键字插入：按照从上到下、左小右大的原则将关键字插入树中。调整：找到失去平衡的最小子树，换成稳定的三角结构（左小右大根中）。将其余节点尽可能保存不变地进行相应地调整（例如，原来是谁的左节点就还是谁的左节点），将要插入的关键字按照插树规则，继续插入。
树的节点个数=树的总度数之和+1
6. 图
无向完全图的总边数：n(n-1)/2
有向完全图总边数：n(n-1)
带权图被称为网络，是否为稀疏矩阵的判断标准：nlog2n
连通图：每个i到j都有路可以走，那么是连通的；若图中任意两个顶点都是连通的，那么是该图为连通图。（特指无向图）
无向图G=（V，E），其中V是顶点，E是边数，E>=V-1，才有可能是连通的
连通分量：非连通图的极大连通子图为连通分量（特指无向图）
强连通图：有向图中，如果顶点i到j之间存在路径，j到i之间也存在路径，就是强连通图（特指有向图）
邻接矩阵：1为邻接，0为不邻接。无指向自己的路则本元素为0。
无向图的邻接矩阵对称，第i行第i列之和为i的度
有向图的邻接矩阵不一定对称，第i行之和为出度，第i列之和入度。
有向图邻接表中有n个表头和m个表节点，表明该图中有n个顶点和m个有向边
一个表的邻接矩阵表示是唯一的，邻接表表示不唯一
图的深度优先遍历：类似树的先序遍历，递归，不唯一
图的广度优先遍历：类似树的层序遍历，不递归，不唯一
最小生成树：连通图的生成树最少含有n个节点和n-1条边，方法：普里姆算法和克鲁斯卡尔算法，两种都为贪心策略
普里姆算法：每次选择权值最小的边，直到所有的顶点都被连接到树中
克鲁斯卡尔算法：先构建顶点图，逐次选取最小的边，如果边的两边顶点来自不同的连通图（连通、不连通），则把边加入，直到所有的顶点连接到同一个连通图为止。
AOV（有向无环图）：顶点表示活动，AOE（带权有向图）：用边表示活动
关键路径：AOE网络中，从源点到汇点具有最大长度的路径称为关键路径
AOV拓扑排序：选择只出不进的点，删除对应的点和边，直到全部删完，删除顶点的顺序，即为AOV拓扑排序顺序。
AOE关键路径和时间余量最大的活动：
求解步骤：
1. 求解每个事件(节点)的最早发生时间。ve(i) 【正向、事件、顶点】Max
2. 求解每个事件(节点)的最迟发生时间。vl(i) 【逆向、事件、顶点】Min
3. 求解每个活动(边)的最早发生时间。e(i) 【正向、活动、有向边】求所有活动的最早开始时间e[i]，若边<vi,vj>表示活动i，则有e[j]=ve[i]。
4. 求解每个活动(边)的最迟发生时间。l(i) 【逆向、活动、有向边】若边<vi,vj>表示活动i，则有l[i]=vl[j]-weight(vi,vj)。
5. 计算每个活动的时间余量，余量为0的活动就是关键活动。d(i)【 l(i) - e(i) 】
1 2 3 4 5 6 ve(i) 0 2 5 8 9 12 vl(i) 0 4 5 8 11 12
a b c d e f g h i j e(i) 0 0 2 2 5 5 5 8 8 9 l(i) 2 0 4 5 5 7 11 10 8 11 d(i) 2 0 2 3 0 2 6 2 0 2 总结：关键路径b,e,i；余量最大的活动g。
寻找最短路径：狄杰斯特拉算法和费洛伊德算法
狄杰斯特拉算法（贪心）：两个集合，一个存放已到达节点，一个存放未到达节点，每次找从已到达节点到未到达节点的最短路径，把包括进来的未到达节点放到第一个集合中，直到所有的节点都放进了第一个集合中。
弗洛伊德算法（动态规划）：写邻接矩阵，逐次更新经过各个节点的路径（该定点所在的行和列均不用更新），如果大于初始值就不更新，小于的话就更新。他可以求出任何节点到任何节点的最短路径
7. 查找
2.散列的ASL（成功）：关键码比较次数之和/关键码个数。ASL（失败）：和Hash函数有关，MOD13的情况下，地址为0～12，（地址0开始找到一个空的地址的比较次数之和）/地址数，注意如果最后不为空要继续循环去找。hash散列的开放寻址法（线性探测，二次探测等）删除关键字空间仍被占，不能直接置空。
8. 排序
原地排序：空间复杂度O（1）
稳定性：相同的R，排序前后相对位置不变
内部排序和外部排序：元素全部放在内存中的排序，需要内存外存之间来回换的排序
内部排序：
类型 名称 描述 时间复杂度 空间复杂度 稳定性 插入排序 直接插入排序 按数据表顺序取数，插入到已排序的队列中
(n-1)次排序
O(n^2) O(1) 稳定 折半插入排序 直接插入排序为基础，折半查找插入的位置，最好0，最坏移动n(n-1)/2 O(n^2) O(1) 稳定 希尔排序 希尔排序 设置gap，开始数的后一个开始查gap个和开始数组成一组进行排序，逐步减小gap(一般为/2），知道gap=1。 O(n)~O(n^2) O(1) 不稳定 选择排序 简单选择排序 从数据表中选择最小的，和未排序的第一个位置交换
（n-1次排序）
O(n^2) O(1) 不稳定 锦标赛排序 树形选择，左右两两比较，逐层选择出最小的 O(nlog2n) O(n) 不稳定 交换排序 冒泡排序 从后向前，依次和前面的比较，每次可选出最小的一个，置于首位；最坏要比较
n(n-1)/2次。
O(n^2) O(1) 稳定 快速排序 取第一个为基准，low和high两个指针，从high开始，找比基准小的数和基准换位置，找到后启动low指针找比基准大的，和high指针指的位置换位置，依次交替，将基准落到low和high重叠的位置，此刻基准左侧的都小于基准，右侧的都大于基准。之后，对左右两子序列执行相同的操作，直到划分出来的子序列最多只有一个元素为止 O(nlog2n) O(log2n)~O(n) 不稳定 归并排序 归并排序 两两合并的思路：两两排序、合并，直到全部合成一个 O(nlog2n) O(n) 稳定 基数排序 基数排序 MSD、LSD两种：最高位优先和最低位优先。LSD：先个位、再排十位、最后排百位（和位置有关） O(d(n+radix)),d位数，r基数（待排序的数字的进制数） O(n) 稳定 堆排序 堆排序 分大根堆、小根堆。
建堆：1.普通建堆：先层序插入并从0标号。从第一个非叶子节点为【n/2】-1（【n/2】向下取整），调整，之后指针-1，依次调整，注意每调整一次都要看调整后是否需要再调整。时间复杂度O(n) 2.依次插入建堆：每次插入后就做调整，直到插完。时间复杂度为 O(nlogn)
插入：按照层序插入的位置插入，把包含插入节点到根上的一路节点选中，进行冒泡排序
删除：用最后一个节点替换删除的值，之后再调整为大根堆或小根堆。
（最坏要比较O(nlog2n)次）
O(n)/O(nlog2n) O(1) 不稳定
二叉排序树：左小右大依次插入！！
总结：
O(n^2)：直接插入、折半插入、简单选择、冒泡排序
O（nlog2n）：锦标赛、快排、归并
非原地：锦标赛、快排、归并、基数（既然时间复杂度下，那就要在空间上多付出一点）
不稳定的：希尔排序、简单选择、锦标赛、快排、堆排序
插入排序和选择排序，不受存储类型的约束
希尔排序和堆排序，利用随机访问特性，所以顺序存储效率>链式存储效率
外部排序：
访问外存系统慢：着重考虑如何使外存的访问次数达到最小
外存信息读取：磁带、磁盘
外部排序的过程：将外存分为n个子文件，将子文件读入内存，内部排序进行排序，排序后的有序子文件写入外存。然后这些段进行有序归并，归并段由小变大，知道行程整个有序文件
总时间=内部排序时间+外存读/写所需时间+内部归并所需时间
减少归并次数：多路平衡归并，常见锦标赛选最小记录，构成严格的k叉归并树时，不够可以补虚段
二、数据库系统
1. 基本概念
数据库的三级模式结构：内模式、模式、外模式（DDL来定义模式）
模式：逻辑模式，数据库中全体数据的逻辑结构和特征描述，是所有用户的公共数据视图
外模式：保证数据库安全性的重要举措，用户只能看到外模式的数据，对于其他数据是不可见的
内模式：数据的物理结构和存储方式的描述，设计影响数据库性能
数据库的二级映像功能：
外模式/模式映像：多个，逻辑独立性
模式/内模式映像：唯一，物理独立性
视图：虚表，提供给用户以多角度观察数据库中的数据的重要机制
数据库系统包含：数据库、数据库管理系统、数据库管理员、应用系统、用户，不包含操作系统
建立：
从Student表中取出所在系为02的数据，组成一个师徒，视图名为Student_VIEW
CREATE VIEW Student_VIEW
AS SELECT * FROM Student WHERE StudentDept='02';
删除：
DROP VIEW Student_VIEW
更新：UPDATE Student_VIEW SET StudentAddress="北京" WHERE StudentName="小红"
缺点：视图在更新时要转换成对基本表的更新
2. 数据模型
数据库中的模型分为两种：概念模型、数据模型
概念模型：用于信息世界的建模，是用户到数据库设计者之间的交流语言
概念模型的基本术语：实体、属性、域、码、联系（1:1，1:n，n:n），E- R模型
数据模型：信息世界数据化为机器世界
（1）层次模型：只能表示1:1、1:n的关系
（2）网状模型：可以表示n:n的关系
（3）关系模型：用表来表示关系
层次模型和网状模型是格式化模型
3. 关系数据库基本理论（交并补除差）
候选码：关系属性中某个属性的值能够唯一标识一个元组，且又不包含多个属性，则该属性称为该关系的候选码
主码：多个候选码，选择其中一个作为主码
主属性：候选码的诸属性被称为主属性
非主属性：不包含在任何候选码中的属性
关系的完整性约束：
（1）实体完整性：指关系数据库中所有的表都必须有主键
（2）参照完整性：定义外键与被参照的主键之间的引用规则，不允许参照不完整的元组
（3）用户定义完整性：指明关系中属性的取值范围，防止属性的值与应用语义矛盾
关系代数：
（1）传统：并、差（R-S,找R中S没有的行）、交、广义笛卡尔积
（2）专门：选择（选择出一些行）、投影（选择出一些列）、连接（等值连接、自然连接）、除运算
除运算：R除S，如果R某属性的象集包含R与S相同属性的象集，那么结果为该属性。
4. 关系数据库标准语言SQL（增删改查）
SQL：Structured Query Language，关系代数和关系演算之间的一种语言
SQL特点：综合统一、高度非过程化、面向集合操作、一种语法多种使用方式、简单易学
SQL包括：数据定义语言（DDL）、数据操纵语言（DML）、数据库控制语言（DCL）
SQL的功能：数据查询、数据定义、数据操纵、数据控制
（1）数据定义：CREATE、ALTER、DROP；注意：视图和索引不支持修改定义，但一些产品Mysql、Orcale允许修改定义
示例：建立一个学生表Student，其中包括学号（Sno），姓名（Sname），性别（Ssex），年龄（Sage），入学时间（Sdate）5个属性。其中学号为主键，姓名唯一，入学时间不能为空。
CREATE TABLE Student
(Sno CHAR(6) PRIMARY KEY,
Sname CHAR(10) UNIQUE,
Ssex CHAR(2) CHECK(Ssex IN (’男’,’女’)),
Sage SMALLINT,
Sdate DATE NOT NULL);
示例：加入电话列
ALTER TABLE Student ADD SPhone CHAR(11);
示例：删除数据表
DROP TABLE Student;
示例：创建索引，索引名为Index_Student 按照学生姓名升序排列，若学生的姓名相同，则按照ID进行降序排列：
CREATE UNIQUE INDEX Index_Student ON Student(Sname,Sno DESC);
示例：删除索引
DROP INDEX Index_Student;
（2）数据查询：SELECT
GROUP BY：按一列的值、多列的值分组，列值相等的元组为一组
HAVING：与GROUP BY 配合使用，只有满足特定条件的组会被展示出来
ORDER BY：列值排序，升序ASC，降序DESC
计算值：COUNT(*):计算元组个数，COUNT(<列名>）：计算该列值的个数
MAX(<列名>)、MIN(<列名>)、SUM(<列名>)、AVG(<列名>)
示例：查询学生表Student的学生的人数
SELECT COUNT(Sno) AS 总人数 FROM Student;
总人数 8
查询满足制定条件的元组：WHERE语句
示例：SELECT * FROM Student WHERE Sname LIKE '____'
查找全名为两个汉字的学生信息，ASCII编码两个_代表一个汉字，GBK一个_代表一个汉字
示例：根据 order_date 列的值将 orders 表中的记录分组，并计算每个日期的总销售额。
SELECT order_date, SUM(amount)
FROM orders
GROUP BY order_date;
示例：Course表是学生选择课程的记录，查找每位学生所选的课程数
SELECT Sno,Count(Sno) AS 所选课程数
FROM Course
GROUP BY Sno;
连接查询：等值/非等值查询，外连接查询（左外、右外、全外），自身连接查询
等值/非等值查询：
SELECT S.Sname,S.Ssex,S.Sdept,D.Dname
FROM Student S,Dept D
WHERE S.Sdept=D.Dno;
内连接：select * from a_table a inner join b_table b on a.a_id = b.b_id;
左外：select * from a_table a left join b_table b on a.a_id = b.b_id;
右外：select * from a_table a right outer join b_table b on a.a_id = b.b_id;
嵌套查询：允许多层嵌套，但子查询中不能适用ORDER BY
示例：查询使用软件工程系、计算机系的学生学号、姓名、性别
SELECT Sno,Sname,Ssex
FROM Student
WHERE Sdept IN (SELECT Dno FROM DEPT WHERE Dname="软件工程" AND Dname ="计算机");
注意：EXISTS 只返回TRUE、FALSE，一般SELECT *，给出列名也没有意义
（3）数据更新
插入：INSERT INTO Student VALUES (‘20160702’，‘小红’，‘女’，‘24’);
修改：UPDATE Student SET Sage ='18' WHERE Sname = '小红';
删除：DELETE FROM Student WHERE Ssex = '女';
ORDER、COUNT、FROM 不是标准SQL语言
WHERE后不能用COUNT、SUM等函数
5. 查询处理和查询优化
查询处理步骤：
（1）查询分析：判断查询语句是否符合SQL语法规则
（2）查询检查：语义检查、完整性检查
（3）查询优化：选择一个高效执行的查询处理策略，两种类型：代数优化和物理优化
（4）查询执行：执行代码、回送查询结果
实现查询的算法：
（1）选择操作：扫描算法：全表扫描、索引扫描
（2）连接操作：最耗时、等值连接算法：嵌套循环、排序合并、索引链接、Hash Join
查询优化：关系数据库的关键技术、关系数据库系统的优点所在
代数优化：通过关系代数表达式的等价变换来提高查询效率
物理优化：基于规则（不能在任何情况下使用、大多数情况下可用）、基于代价估算、两者结合
6. 数据库安全性
目的：防止非法用户使用数据库
1. 用户的标识和识别
口令鉴别（静态、动态）、生物特征鉴别、智能卡鉴别
2. 存取控制
自主存取控制：赋予权限
示例：为ZHANG用户赋予Student表的INSERT权限
GRANT INSERT ON TABLE Student TO ZHANG；
示例：拿回ZHANG的INSERT权限
REVOKE INSERT ON TABLE Student FROM ZHANG；
强制存取控制：采取强制的检查手段
当用户的许可级别大于等于数据密级才能读；小于等于才能写
3. 视图（保护数据的独立性）+ 授权机制
4. 安全审计：用户对数据库的所有操作都记录下来，放入审计日志中，供审计员审核
5. 数据加密：加密解密占用大量系统资源，因此为可选项，由用户选择对高机密数据进行加密
7. 数据库的完整性检查（三种）
目的：防止合法用户在使用数据时向数据中加入不合语义的数据（保证数据的完整性和相容性）
完整性约束的作用对象，包含列级、元组级、关系级三级
完整性约束包括三大类型：实体完整性约束、参照完整性约束、用户定义完整性
（1）实体完整性：通过主码来实现，主码的属性不能为空，且主码值必须唯一
检查：不唯一拒绝，主码的属性为空拒绝
（2）参照完整性：不允许参照不存在的实体
（3）用户定义的完整性：NOT NULL，UNIQUE、CHECK
（4）触发器：对基本表进行插入、修改、删除时自动执行的特殊存储过程。一般用在比CHECK约束更复杂的约束中，由AFTER，BEFORE两种触发器，一般在特定语句执行前/后自动触发
create trigger tri_insert_student after insert
on student for each row
update class set count=count+1 where class.id=new.class_id;
8. 数据库恢复（事务）
1.事务：用户定义的一个数据库操作序列，要么全做要么全不做，是一个不可分割的单位。是关系数据库的一种特殊手段，SQL定义事务有以下三条：BEGIN TRANSACTION、COMMIT、ROLLBACK
2.事务的四个特征：ACID
原子性（Atomicity）：事务时一个原子操作，是数据库的逻辑工作单位
一致性（Consistency）：事务必须从一个一致性状态变成另一个一致性状态
隔离性（Isolation）：同一时间可能有许多事务处理同一个数据，一个事务的执行不被另一个事务的执行干扰。
持久性（Durablity）：一个事务一旦提交，它对数据库中数据的改变是永久性的
3.故障类型：事务故障、系统故障、介质故障（外存故障）、计算机病毒
4.故障恢复：与先备份正确的数据库映像，故障时根据预先备份重新建立数据库
方法1：数据传储：静态、动态、海量、增量
方法2：日志文件：记录事务对数据库的更新操作。原则1:先写日志再写数据库 原则2:必须严格按照并发事务执行的时间次序
9. 并发控制（封锁）
1. 事务并发执行可能存在问题：丢失修改、不可重复读、读脏数据
丢失修改：T1、T2同时修改一条数据，T2的提交结果破坏了T1的提交结果，导致T1丢失修改
不可重复读：T1读取数据，T2修改数据，T1再读和之前读的不一样。修改、插入、删除，后两种条数改变的也被称为幻读
读脏数据：T1修改数据，T2读取数据，T1撤回事务，T2读的和数据库里的不一致，错误的数据，称为脏数据
2.控制并发的一种方式：封锁
1）排他锁、写锁、X锁：事务T对数据对象A加上X锁，事务T可以读A也可以修改A，其他事务不能再对A加任何锁，直到T释放A上的锁，这保证了其他事务在T释放A上的锁之前不能在读取和修改A。
2）共享锁、读锁、S锁：如果事务T对数据对象A加上S锁，则可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁。这保证了其他事务可以读取A，但在事务T释放对象A上的S锁之前不能对A做任何修改。
3.活锁
T1封锁R，T2请求R，T3请求R....，T1释放后给T3，T3释放后给T4，T2永远等待
解决方法：先来先服务，事务按次序获得锁
4.死锁
T1封锁R1，T2封锁R2；T1申请R2，T2申请R1
解决：一次封锁：事务一次性对所有要用到的对象加锁
顺序封锁：预先确定对象的封锁顺序，事务对对象封锁时，按照顺序进行；不能先封锁后面的对象
诊断：超时、等待图存在回路
解除：选择代价最小的事务进行撤销，释放此事务所有的锁
5. 并发调度的可串行化
并发执行与按照某一次序串行执行的事务结果相同，这种并发执行调度策略被称为可串行化
保证并发调度的可串行化：两段锁协议
第一段是获得封锁，也称扩展阶段：事务可以获得任何数据项上任何类型的锁，但是不能释放锁
第二段是释放封锁，也称收缩阶段：事务可以释放任何数据项上任何类型的锁，但是不能获得锁
注意：充分不必要条件，可串行调度中不一定所有的事务都符合两段锁协议
10. 规范化（范式）
不规范可能带来的问题：数据冗余、更新异常、插入异常、删除异常
X->Y，Y被包含于X，则称X->Y是平凡函数依赖，否则称为非平凡函数依赖
X->Y，若X的任一真子集X'都无法退出Y，则称Y完全函数依赖于X，否则为部分依赖
X->Y，Y->Z，Y不被包含在X，Z不被包含在Y，且X推不出Z，则Z传递函数依赖于X
候选码求解：
只出现在左侧的一定，只出现的右边的一定不，两边都没出现的一定，之后把一定的和两边都出现的进行组合，计算闭包，如果闭包包含所有属性，那么则为候选码
规范：
1NF：每个属性都不能再分
2NF：1NF的基础上，消除非主属性的部分函数依赖
3NF：2NF的基础上，消除非主属性的传递依赖
BCNF：消除主属性的部分依赖和传递依赖（若X->Y,Y不被包含于X，X必含有码）
4NF：消除多值依赖
注意：规范化程度越高，数据冗余越小，检索效率越慢
11.候选键、主键、超键、外键
学生信息（学号 身份证号 性别 年龄 身高 体重 宿舍号）和 宿舍信息（宿舍号 楼号）
候选键：见上述候选码的求解方法，学号、身份证号
主键：要么学号、要么身份证号
超键：只要含有“学号”或者“身份证号”两个属性的集合就叫超键，例如R1（学号 性别）、R2（身份证号 身高）、R3（学号 身份证号）等等都可以称为超键！
外键：宿舍号
12.有损连接和无损连接
无损连接：将关系模式 R 分解后，通过自然连接操作能够完全恢复出原始关系 R 中的所有数据，且既不会增加多余信息也不会丢失任何原有信息。
有损连接：分解后的子关系模式通过自然连接后，无法恢复出原始关系 R，要么丢失了某些元组，要么产生了原本不存在的虚假元组。
（1）Chase（追赶）法 / 表格法，适用于全部场景
步骤：
构造初始表格：
建立一个表格，行代表每个分解后的子模式 Ri，列代表关系模式 R 中的所有属性。
在表格中填符号：如果该子模式 Ri 包含某个属性 Aj，则在 (i, j) 位置填
a_j；否则填b_i_j。根据函数依赖进行“追赶”：
查看给定的函数依赖集 F。
对于每一个函数依赖
X -> Y，在表格中寻找X列上值相等的行。如果找到，则将这些行在Y列上的符号修改为一致。修改规则是：
如果其中一行是
a_j，则将其他行的值也改为a_j。如果没有
a_j，则改为下标最小的那个b_i_j。判断结果：
在修改过程中，如果发现某一行全部变成了
a1, a2, ..., an（即变成了一个完全是a的行），那么可以立即断定该分解是无损连接的。如果直到无法再根据任何函数依赖修改表格后，仍然没有出现这样的行，则该分解是有损连接的。
例子：
关系模式 R：
R(A, B, C, D)函数依赖集 F：
{A->B, A->C, C->D}分解方案：
ρ = {R1(A, B, C), R2(C, D)}步骤1：构造初始表
步骤2：根据函数依赖进行追赶
A B C D R1 a1 a2 a3 b14 R2 b21 b22 a3 a4
1. A->B,A列不相等，无变化
2. A->C,A列不相等，无变化
3.C->D，C列有相等，需要让对应的D也相等（有a以a为准，无a以最小的b为准）
修改后的表格：发现存在R1包含了a类的全部类型，所以是无损连接，否则是有损链接
A B C D R1 a1 a2 a3 a4 R2 b21 b22 a3 a4
（2）快速判断发，适用于分解成两个关系的场景
分解 ρ = {R1, R2} 是无损连接的，当且仅当以下两个条件之一成立：
R1 ∩ R2 -> R1 - R2或者
R1 ∩ R2 -> R2 - R1
例子：
关系模式 R：
R(A, B, C, D)函数依赖集 F：
{A->B, A->C, C->D}分解方案：
ρ = {R1(A, B, C), R2(C, D)}R1^R2=C；
R1-R2=A,B；
R2-R1=D；
存在R1^R2=C -> R2-R1（C->D），因此为无损连接
三、计算机网络
1.基本概念（OSI、TCP/IP）
组成：
物理组成：硬件、软件、协议
功能组成：通信子网（网络协议组成，提供数据传输、数据交换等功能，负责连网计算机之间通信）、资源子网（主机、终端组成，负责全网数据处理，提供网络服务）
计算机网络资源包括：数据资源、硬件资源、软件资源
网络协议：属于计算机网络软件系统、由语法、语义、载体三要素构成
工作方式：边缘部分（所以连在网上的主机组成，用户可直接使用）、核心部分（网络及路由器，为边缘部分提供服务）
分类：
按照范围分：广域网（WAN）、城域网（MAN）、局域网（LAN）、个人局域网（PAN）
按照拓扑结构：星形、树形、总线型、环形、网状
按使用范围：公网、私网
按逻辑功能：通信子网、资源子网
按通信方式：点对点（星形，环形）、广播式（总线型）
性能指标：速、带宽、时延、吞吐量、时延带宽积、利用率（并非越高越好，利用率过高会产生非常大的时延）、往返时间（RTT）
OSI七层模型、TCP/IP四层模型、五层模型：
| OSI | 数据类型 | 基本功能 | 设备 | 常见协议 |
| 应用层 | 报文 | 提供网络服务接口 | 计算机或终端设备 |
HTTP、FTP、TELNET ------------------ ASCII、JPEG ------------------ RPC ------------------ TCP（面向连接）、UDP（面向报文） |
| 表示层 | 数据加密、解密、压缩、格式转换 | |||
| 会话层 | 建立、管理、终止进程间的通话 | |||
| 运输层 | TCP、UDP报文 | 第一个端到端传输的层次，提供应用进程间的逻辑通信，差错检测、拥塞控制 | ||
| 网络层 |
数据报 （数据报分组交换是失序的） |
对子网间数据报进行路由选择和IP寻址，不提供校验、允许乱序 | 路由器、防火墙 | IP、ARP、ICMP报文(ping)、RIP、OSPF、BGP |
| 数据链路层 |
数据帧 （以太网中帧的最小长度为64） |
在不可靠的介质中提供可靠传输，流量控制、差错控制、帧同步 | 网桥、交换机 |
MAC、PPP（两个均在数据链路层） PPP：五个1后补0 |
| 物理层 | 比特 | 对数据传输线路信道进行定义 | 中继器、集线器 |
基于TCP的应用层协议有：HTTP、FTP、SMTP（基于ASCII）、TELNET、SSH、POP
基于UDP的应用层协议：DNS、TFTP（简单文件传输协议）、SNMP：简单网络管理协议
路由协议：
1.RIP：基于距离向量、一条路径只能包含15个路由器、基于UDP
2.OSPF：使用了地杰斯特拉提出的最短路径算法、直接使用IP数据报传送
3.BGP：基于TCP
数据报，如果有错，会将其丢弃，都是不可靠的，包括IP数据报
2. 时延计算
时延带宽积=单向传播时延x带宽
发送时延=数据包大小（bit）/带宽（b/s）
着重考虑最后一次发送
答：分组发送1000次，单项传播时延=1000b/100Mb/s=0.01ms，单次发送时延=1000x8/100Mb/s=0.08ms。从0ms开始，H1开始向H2发送，最后0.08x1000=80ms，H1完成发送；最后一组发送后经过0.01ms传播时延到达路由器。路由器校验（时间不计），再通过0.08ms发送，0.01ms传播到达H2。因此总时延为：80+0.01+0.08+0.01=80.10ms
3. 信道传输
（1）奈奎斯特定理：无噪声信道下，最大数据传输的次数=2W（W带宽）
最大传输速率=
,W带宽，M信号状态数（4个幅值的ASK调制，M=4）
（2）香农定理：
信噪比=10log10（S/N）
极限传输速率C=Wlog2（1+S/N），W为带宽
（2）信道利用率
停等协议的信道利用率=Td/（Td+RTT+Ta）
GBN和SR协议的利用率为(wXTd)/（Td+RTT+Ta） ,w为窗口大小，大于等于1
GBN和SR的信道利用率和w相关。w大小和协议帧序号位数相关。GBN最大为为2^n-1，WB最大为2^（n-1）
GBN（后退N帧）协议：
- 允许发送方在未收到确认的情况下，连续发送多个数据帧（窗口大小 N），但接收方只会按顺序接收数据帧。
- 如果接收方发现某个帧丢失或错误，会丢弃该帧及其之后的所有帧，并要求发送方重新发送这些帧。
SR（选择重传）协议：
- 同样允许发送方在未收到确认的情况下连续发送多个数据帧（窗口大小 N），但接收方可以接收乱序帧并缓存它们。
- 只有那些丢失或错误的帧会被重新请求，接收方只重传特定的帧。
发送０～７帧，只收到0，2，3的帧确认，GBN重发：4～7帧，SR重发：1，４～７帧
4. QAM调优、ASK调制
每次需要传输的比特数量=最大的数据传输速率/最大数据传输的次数
n = 2^（每次需要传输的比特数量）
选择：QAM-n方式
5. 二进制指数避退算法
每次发生冲突，网卡会随机选择一个等待时间，在0～2^k-1个时间片之间等待。k为冲突次数。
6. CRC冗余校验码
（1）看多项式的次数，就在后面补几个0
（2）与G作异或除（相同为0，不同为1）
（3）如果余数不为0就是发生了错误
VS 奇偶校验码：比奇偶可靠，奇偶只能检测奇数位数的错误，不能检测偶数位数的错误（无法定位）
VS 海明码：海明码不仅可以检测，还可以纠错
7. IPv4
IPv4格式：
32位，划分4个字节，每8位一点
A类：A类IP地址：一个A类IP地址由1字节的网络地址和3字节主机地址组成，网络地址的最高位必须是“0”， 地址范围从1.0.0.0 到126.0.0.0。可用的A类网络有126个，每个网络能容纳1亿多个主机。
0 000 0000 - 0 111 1111: 0-127
网络数： 2^7(1~126)（0：用于表示未知地址，127表示回环地址，两个都不能用）
每个网络中的主机数： 2^24-2
注意：主机位全0，表示网络ID，防止发生混淆；
注意：主机位全1表示本网段内的广播地址。所以每个网段中的第一个与最后一个都不能使用。
默认子网掩码： 255.0.0.0
私网地址：10.0.0.0
B类：B类IP地址：一个B类IP地址由2个字节的网络地址和2个字节的主机地址组成，网络地址的最高位必须是“10”，地址范围从128.0.0.0到191.255.255.255。可用的B类网络有16382个，每个网络能容纳6万多个主机 。
10 00 0000 - 10 11 1111： 128-191
网络数： 2^14（128~191）
每个网络中的主机数： 2^16-2
默认子网掩码： 255.255.0.0
私网地址： 172.16.0.0-172.31.0.0
C类：C类IP地址：一个C类IP地址由3字节的网络地址和1字节的主机地址组成，网络地址的最高位必须是“110”。范围从192.0.0.0到223.255.255.255。C类网络可达209万余个，每个网络能容纳254个主机。
110 0 0000 - 110 1 1111: 192-223
网络数： 2^21（192~223）
每个网络中的主机数： 2^8-2
默认子网掩码： 255.255.255.0
私网地址： 192.168.0.0-192.168.255.0
D类：D类地址用于多点广播（Multicast）：D类IP地址第一个字节以“1110”开始，它是一个专门保留的地址。它并不指向特定的网络，目前这一类地址被用在多点广播（Multicast）中。多点广播地址用来一次寻址一组计算机，它标识共享同一协议的一组计算机。224.0.0.0到239.255.255.255用于多点广播 。
1110 0000 - 1110 1111: 224-239
E类：240-255：ping十进制的ip地址也可以ping通。
特殊地址：（0.0.0.0）、（255.255.255.255）、（127.*.*.*）、（169.254.*.*）（DHCP）
私有地址：
A类地址：10.0.0.0～10.255.255.255
B类地址：172.16.0.0～172.31.255.255 （16个B类）
C类地址：192.168.0.0～192.168.255.255
广播地址：对于一个给定的IP地址和子网掩码，广播地址可以通过将IP地址的主机部分全设为1来计算。
主机地址：主机部分全为0。
主机号不能全部为0，也不能全部为1，所以要-2，主机号就是除了子网掩码部分，后面部分的十进制数。
子网划分：IP：202.168.10.0，子网掩码：255.255.255.192
IP看是C类，默认掩码为24位，掩码最后:11000000，借了2位，所以子网数2^2=4(:00,:01,:10,:11)，剩余主机数2^6-2=62。共4个子网，每个子网可分配主机数62。
注意：！！子网号一定是连续的
查看可分配IP：
上述例子中，IP的前26位固定不变，后面全为0为主机地址，全为1位广播地址，其余为可分配地址。
IPv4 vs IPv6:
（1）v4，32位，v6，128位
（2）v4首部长度可变，v6基本首部长度不可变
（3）v4转v6的过程中，应并行使用，可以采用双协议栈和隧道技术
（4）v4首部包含TTL表示最大跳数，v6首部的Hop Limit也表示最大跳数。两者等价
8. 网络主机 网关、子网掩码
主机->交换机->若干个路由器->Internet。默认网关：最靠近主机路由器端口地址。主机的子网掩码和默认网关的子网掩码相同
9. SDN网络体系结构
北向接口：对上层开发者提供的编程接口
南向接口：负责控制平面和数据平面的通信
10. 拥塞控制（TCP）
注意！！！没说快速恢复就是慢开始
最大段长（MSS）：慢开始初始为1MSS，紧接着指数2倍增长，2MSS，4MSS直到之前拥塞窗口的一半，开始加法增长，每次＋1MSS。
RTT：每一传输伦次即为1RTT，例如慢开始阶段1MSS->2MSS为1RTT，2MSS->4MSS也为RTT
慢开始：
快恢复：
11. 3次握手，4次挥手
注意：（1）一个来回为一个RTT
（2）挥手中，如果不说明/要求至少，则挥手时服务器发送的ACK和FIN重合，即服务器断开连接最少需要1.5个RTT
（3）挥手中，客户端需要在收到服务器端的FIN指令后，等待2MSL
（4）建立连接后开始传输内容，HTTP先传输文本再传输图片等，窗口大小和拥塞控制中有关。先是1个MSS，之后指数增长（拥塞控制前期窗口的增长规律）。且例如先传输1MSS的文本，在传输3MSS的图片。1个RTT可传输文本，第二个RTT能够传输２个MSS，需要第三个RTT再传输1个MSS才能把图片发送过来。
12. 曼切斯特编码、差分曼切斯特编码
曼切斯特编码：由负到正为1，由正到负0
差分：虚线处无跳变为１，有跳变为０，只能求得中间的编码，开头结尾缺信息
13. IP数据报
数据帧=数据帧首部+数据部分+数据帧尾部（数据部分最大长度单元：MTU）
IP数据报：数据报首部+数据报数据部分=》传到数据帧的数据部分
标志位：DF=1，不可分片；MF=1，后续还有分片
口诀：1总8片首4（描述总长用1个字节一个单位，分片8个字节一个单位，首部4个字节一个单位）
分片总长度=数据报首部长度+分片后传输数据的长度
14. UDP数据报、TCP段
作用：传输应用层数据
格式：UDP=8B头部+应用层数据；TCP=20B固定头部+可变头部+应用层数据
有效载荷（应用层数据）传输效率=应用层数据长度/总长度=应用层数据长度/（头部长度+应用层数据长度）
四、操作系统
1. 基本概念
系统配置操作系统的原因：方便性、有效性、可扩充性、开放性
并行：同时进行；并发：交替执行
三种基本的操作系统：
（1）多批道处理系统：用户提交的作业先放在外存上，并排成一个后备队列，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。
（2）分时系统：允许多个用户同时通过的终端，以交互方式使用主机，共享主机中的资源。
（4）实时系统：在规定时间内完成对该事件的处理，控制所有实时任务协调一致地进行。
操作系统的基本特征：
（1）并发性：并发和并行的区别？并发：多个事件在同一时间间隔发生；并行：多个事件在同一时刻发生
（2）共享性：资源可供内存中多个并行执行的进程共同使用。互斥共享方式：打印机；同时访问方式：磁盘等
（3）虚拟性：将物理实体变为若干个逻辑上的对应物。两种方式：时分复用（提高资源利用率）和空分复用（提高存储空间的利用率）。
（4）异步性：多道程序环境下，每个进程何时执行、何时暂停未知，并以不可预知的速度向前推进。
主要功能：
（1）处理机管理功能：对进程进行管理，创建和撤销进程，进程协调等
（2）存储器管理功能：为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储的利用率
（3）设备管理功能：完成用户进程提出的I/O请求
（4）文件管理功能：对用户文件和系统文件进行管理
（4）接口：提供用户和操作系统的借口
2. 微内核、宏内核
（1）微内核：各个服务之间相互独立；宏内核：各个服务混在一起
（2）安全性：微内核>宏内核
（3）可靠性、可扩展性、可移植性：微内核>宏内核
（4）效率：微内核<宏内核
（5）微内核提供了对分布式系统的支持，融入了面向对象技术
中断向量表是一种用于存储中断处理程序入口地址的数据结构，以中断号为索引，将中断号映射到相应的中断处理程序入口地址。需要能够随机访问，因此最好采用数组。中断向量表是操作系统初始化时就创建的。
3. 进程管理（状态转换）
（1）进程：系统进行资源分配和调度的独立单位，目的：多个程序能并发执行
（2）线程：一个进程包含一个或多个相对独立的线程。进程只是拥有资源的基本单位，线程是能够用独立运行的基本单位，也是独立调度和分派的基本单位。线程中只拥有一点必不可少的，保证其独立运行的资源。
（3）进程状态：就绪态：进程已得到所有必要资源，只要再获得处理机，便可立即执行。执行状态：正在执行，运行状态，单处理机系统只能有一个进程处于执行状态，多处理机系统可以有多个进程处于执行状态。阻塞状态：正在执行的进程由于发生某事件暂时无法执行时，便放弃处理机且处于暂停状态。
进程自己决定：执行->阻塞
sleep 和wait的区别：
- 所属对象不同，sleep是Thread 上的方法，而wait是Object上的方法
- sleep方法不会释放锁，而wait会释放锁
- sleep不依赖于synchronized，而wait必须在synchronized包住的代码块中执行，如果不是，则会报错
- sleep不需要被唤醒，休眠之后会从阻塞状态转为就绪状态，而wait在某些情况下会仍然处于阻塞状态，需要手动唤醒
4. 调度机制（先来先服务、最短作业优先、优先级调度、高响应比调度、时间片轮转、多级反馈队列）
高级调度：作业调度、长程调度，决定外存后备队列中哪些作业调入内存
低级调度：进程调度、短程调度，决定就绪队列中的哪个进程获得处理机
中级调度：内存调度，将暂时不能运行的进程调至外存，此时进程处于挂起状态。目的是为了提高内存利用和系统吞吐量。
作业：包括程序、数据和作业说明书三部分，系统根据说明书对程序的运行进行控制。在批处理系统中，是以作业为单位，从外存调入内存的。
调度算法：先来先服务、短作业优先、优先级调度、高响应比优先、基于时间片轮转的调度、多级反馈队列调度
（1）先来先服务：FCFS，最简单，按照到达时间排序即可
（2）短作业/进程优先：SJF/SPJ，作业进程调度的区别不再赘述，每次选择的是已进入系统的，要求服务时间最短的作业，调度顺序：A C E D B
| 作业 | 到达时间 | 服务时间 | 开始时间 | 结束时间（服务时间+开始时间） | 周转时间（结束时间-到达时间） | 带权周转时间（周转时间/服务时间） |
| A | 0 | 3 | 0 | 3 | 3 | 1 |
| B | 1 | 6 | 14 | 20 | 19 | 3.17 |
| C | 2 | 4 | 3 | 7 | 5 | 1.25 |
| D | 3 | 5 | 9 | 14 | 11 | 2.2 |
| E | 4 | 2 | 7 | 9 | 5 | 2.5 |
缺点：对长作业不利，完全忽视作业的等待时间
（3）优先级响应：静态优先级、动态优先级
（4）高响应比优先：每次有作业运行完，都要计算各个已经到达且未执行作业的优先级。优先级=（作业到达到上一作业服务完成的等待时间+服务时间）/服务时间。上述例子中，A运行完成，Rb=(2+6)/6=1.33；Rc=(1+4)/4=1.25；Rd=(0+5)/5=1,因此A执行完执行B
（5）基于时间片轮转：和时间片的大小有关。假设时间片大小为1，那么时间片每执行1个单位，那么就轮转（换个作业执行），注意只在未执行完成的作业中轮转
| 作业 | 到达时间 | 服务时间 | 开始时间 | 结束时间 |
| A | 0 | 3 | 0 | 11 |
| B | 1 | 6 | 1 | 20 |
| C | 2 | 4 | 2 | 16 |
| D | 3 | 5 | 3 | 19 |
| E | 4 | 2 | 4 | 10 |
（6）多级反馈队列调度：设置多个队列，越往前队列的优先级越高，为每个进程规定的运行时间片就越小。每个队列都采取先来先服务，一个新进程进来后在第一队列的末尾，如果能在时间片内完成则撤离，完不成则放在第二队列的队尾，以此类推。仅当第一队列为空时，才会执行第二队列。当处理第i个队列时，有新进程进入较高队列，则抢占处理机，同时将正在执行的进程调到第i队队尾。
实时调度算法：（1）最早截止时间（2）最低松弛度：松弛度=必须完成时间-任务本身运行时间-当前时间
考点：1.牢记先来先服务、短作业优先、响应级优先、高响应比优先（（到达时间-上一服务结束时间）/服务时间）、时间片轮转的原理
2.看清！！抢占式还是非抢占式。
3.牢记周转时间=结束时间-到达时间；带权周转时间=周转时间/服务时间；平均可求平均值
5. 内存管理
将用户源程序转变为可执行的程序，通常要经过编译、链接、装入三个步骤。
链接方式：静态链接（运行之前链接）、装入时动态链接（装入内存时边装入边链接）、运行时动态链接（程序执行时，发现某模块未装入内存，立即寻找、装入内存并链接）
装入：绝对装入（逻辑地址和物理地址一致）、可重定位装入、动态装入（程序执行时才将逻辑地址转为物理地址）
连续分配存储管理方式：单一连续分配、固定大小连续分配、动态分区分配（根据进程实际需要，动态分配空间，常用数据结构：空闲分区表和空闲分区链）、动态可重定位分区分配（将内存中的所有作业移动为相邻，将闲散小空闲分区拼凑成大空闲分区）
动态分区算法：
（1）首次适应法：空闲分区按地址从小到大排序（地址递增），每次分配内存时总是顺序查找空闲分区，直到找到一个能满足作业大小要求的空闲分区为止，从中划出一块与请求大小相等的内存空间分配给请求作业。缺点：低地址使用频繁，存在很多难以利用的小的空闲分区（碎片），查找开销大。
（2）循环首次适应：先从上次找到的空闲内存的下一空闲分区开始查找。缺点：可能会缺乏大的空闲分区
（3）最佳适应法：每次分配内存时，找能够满足作业的最小空闲分区。要求空闲分区按照容量从小到大分区（容量递增）。缺点：每次分配后所分割下来的剩余部分是最小的，因此存在很多碎片
（4）最坏适应法：按容量从大到小排序，先检查第一个空闲分区大小，如果不能满足则分配失败，满足则分配相应的内存给作业。优点：减少碎片，查找效率高。缺点：使内存缺少大的空闲分区
（1）（2）（3）（4）是基于顺序搜索的动态分区分配算法，不适用于太大的系统
（5）快速适应算法：按容量大小分类，每类维护一个表/链，同时设置管理索引表，记录类型和表头指针。根据进程大小，从索引表中找出能容纳它内存的最小空间分区，从链表中取下第一块进行分配
动态分区垃圾回收：根据回收区的首址，从空闲分区表中找到相应的插入点。总之：以自最前已知地址为首址，修改相应的大小即可
离散分配---允许将进程直接分散地装入许多不相邻的空闲分区中。
离散分配的单位为页，即为分页式存储管理方式；离散分配的单位为段，那么为分段式存储管理方式。
分页存储（一维）：将进程的逻辑地址空间分为若干个大小相等的区域，称为页，从0开始编号。相应的内存物理地址被分成若干个块，称为物理块或页框，同样从0开始编号。若干页可以被装入多个不相邻的物理块中。同时，系统为每个进程维护一个页表，记录页号和页框的映射。
分段存储（二维）：将作业的地址空间划分为若干段，从0开始编号，使用一段连续的地址空间。段的长度由逻辑信息组的长度决定，因此每个段的长度不等。
6. 用户态内核态切换
所谓内核态，即操作系统的管理程序运行时的状态。所谓用户态，即用户程序运行时的状态
（1）用户态（目态）只能执行非特权指令，内核态（管态）什么都可以执行
（2）常见的特权指令：对I/O设备的操作的指令、访问程序状态的指令、存取特殊寄存器的指令等
（3）类似于trap指令、数据传送指令、设置断点指令都可以在用户态执行，只是需要从用户态切换到内核态
且运行完成后，又会由内核态切为用户态。
7. 虚拟内存管理
虚拟内存管理是操作系统的一项重要功能，它允许程序使用比实际物理内存更多的内存空间。这一机制通过将内存划分为多个页（或段）来实现，具体包括以下几个关键概念和特点：
C语言中malloc()等请求分配空间的函数，分配的是虚拟内存
1. 虚拟地址空间
每个进程都有自己独立的虚拟地址空间，这使得进程之间的内存空间相互隔离，提高了安全性和稳定性。
2. 页和页表
页（Page）：虚拟内存被划分为固定大小的块，称为页。
页表（Page Table）：操作系统为每个进程维护一个页表，用于映射虚拟页到物理页。页表记录了虚拟页和物理页之间的对应关系。
3. 物理内存
物理内存被划分为同样大小的块，称为页框。通过页表，虚拟页可以映射到任何物理页。
4. 页替换算法
缺页：访问时，页面不在，就是缺页了
缺页率=缺页次数/页面总数
当物理内存不足以满足所有活跃进程的需求时，操作系统需要决定哪些页可以被换出。这涉及到页替换算法，如：
最久未使用（LRU）：替换最近最少使用的页。
先进先出（FIFO）：替换最早加载到内存的页。
影响缺页率：1.替换算法：LRU通常比FIFO缺页率高。2.工作集大小：工作集越大物理块越大，缺页率少3.进程数量越多，缺页率越高
- 改进的Clock置换方法：访问位、修改位；访问位优先级大于修改位；（0，1）（1，0）应淘汰（0，1）
5. 页面错误（Page Fault）
当程序访问一个不在物理内存中的虚拟页时，会发生页面错误。操作系统会捕获这个错误，加载相应的页面到内存中，然后更新页表。
6. 懒惰加载
虚拟内存允许“懒惰加载”，即程序在需要时才加载数据到内存，而不是在启动时一次性加载所有数据。
7. 共享内存
虚拟内存还可以实现多个进程之间的内存共享，多个进程可以映射同一个物理内存页，从而共享数据。（data在进程R和进程S中的页框一定相同，但是页号/页不一定相同（因为每个进程都有自己的独立页表））
8. 安全性和隔离
虚拟内存提供了进程间的隔离，防止一个进程访问另一个进程的内存空间，增强了系统的安全性。
9. 关于大小
主存和硬盘容量影响实际可用的物理内存，虚拟内存大小由虚拟内存管理机制和操作系统定义决定，与主存和硬盘的容量无关。
分页虚拟存储管理--虚表实表换算：
主存（物理地址）=实页号+页大小（内容）
虚拟地址 （逻辑地址）=虚页号+页大小（内容）
页大小（内容）相同=页大小占的位数
注意！！！关于进制一定要注意
例子：2022.15
注意：页大小4KB，按字节编址，占12位；虚地址4GB=32位；因此实地址=12位实页号+12位页大小；虚地址=20位虚页号+12位页大小。虚地址16进制，图中虚页号10进制。
请求分页存储管理方式：
逻辑地址/页面大小：商为页号，余数为页内地址
物理地址=块号x页号+页内地址
多级页表中，页表基址寄存器存放顶级页表的起始物理地址
8. 文件系统
- 操作系统初始化：创建中断向量表
- 硬盘被逻辑格式化：创建硬盘分区表
- 分区完成后初始化文件系统：创建文件系统的根目录
- 如果是Unix系统，初始化文件系统时，还需要创建索引结点表
- 索引节点是文件系统的一种数据结构，每个索引节点保存文件系统的一个文件系统对象的元信息数据，但不包括数据内容或文件名。文件被打开时，需要将磁盘索引节点复制到内存索引节点中。关闭时，要释放索引节点空间。
- 目录：目的-实现按名存取，级数越多，文件查找的时间越少
9. 死锁
（1）四个必要条件
互斥条件：资源是独占的
不可剥夺条件：不被其他进程强行剥夺
请求和保持条件：在申请新的资源时，继续占用已分配资源
循环等待条件：进程等待队列形成环路
死锁预防：
破坏其中一个
（不可剥夺条件）不能获得所需要的全部资源时便处于等待状态，等待期间可以被剥夺
（请求与保持条件）每个进程在开始执行时就申请他所需要的全部资源
（循环等待）将紧缺的，稀少的采用较大的编号，在申请资源时必须按照编号的顺序进行
死锁避免：系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源。
银行家算法！！安全序列：按照何种方式分配资源可以使进程执行完成不死锁
银行家算法：避免死锁
撤销进程法：解除死锁
资源静态分配法：避免死锁
资源分配图简化法：检测死锁
10.系统调用
系统调用：由用户进程发起的，请求操作系统的服务。
操作系统完成：页置换、进程调度等
系统调用：创建新进程
11.磁盘调度算法
请求队列：98、183、37、122、14、124、65、67，当前磁头在53
（1）先来先服务：98、183、37、122、14、124、65、67
（2）最短寻道时间优先：65、67、37、14、98、122、124、183
（3）扫描算法：需要知道磁头的方向，假设磁头向0，37、14、65、67、98、122、183
12.信号量控制
进程同步的一种工具，通过信号量S和P、V操作来实现进程的同步和互斥。
S>0，表示当前可用资源、S<0，表示等待使用该资源的进程数
P操作：S=S-1，占用资源，若S<0，则进程进入阻塞队列
V操作：S=S+1，释放资源，若S<=0，则释放阻塞队列中第一个等待信号量的进程
两个并发进程，若S=0，则表示一个进程进入临界区（访问临界资源的一段代码），另一个进程等待
注意：P、V不能防止死锁
五、计算机组成原理
1. 基本概念
（1）主频：1s有多少个时钟周期
（2）CPI，即执行一条指令所需要的时钟周期数
（3）IPS，即1s执行多少条指令
（4）CPU执行时间：运行一个程序所花费的时间 (s)
（5）同时注意单位换算：G=10^9，M=10^6，K=10^3
（6）CPU包括：运算器和控制器（通常由ROM构成）
数据总线：双向传输；
地址总线：单向传输；
对任一控制线而言，传输是单向的，对控制总线总体来说，传输是双向的
微指令（存放在CPU的控制器中，直接执行微指令的是硬件）->机器语言->操作系统语言->汇编语言->高级语言->应用语言
每一条机器指令由一段用微指令编成的微程序来解释执行
2. 机器数（进制转换，原码，补码，反码，移码）
进制转换（整数部分）：
二进制：1100B、八进制：123O、十六进制：1AF6H
二进制：
1024，512，256，128，64，32，16，8，4，2，1
八进制和十六进制就除法吧，取余直到除数为0，记得最后倒着写
进制转换（小数部分）：
0.小数部分x2/x8/x16，取整，每次取0.尾数，直到小数点后面部分为0，记得正着写
二转八、十六进制转换：就是以小数点为中间向前向后分，3/4为一个，不够补0，分别进行进制转换
八、十六转二：一个一个转二进制然后拼接起来即可
原码：0正号，1负号
反码：正数，反码和原码一样；负数，除符号位外取反
补码：正数，补码和原码一样；负数，补码=反码+1=原码除符号位外取反+1
移码：补码的符号位取反
C语言中：数值在计算机中是以补码的方式存储的
机器数：一个数在计算机中的二进制表示形式， 叫做这个数的机器数。机器数一般可以用十六进制表示。
char=8位，short=16位，double=64，float=32，其他的跟系统位数有关系，比如int=16/32
例题：short类型的变量x=-8190的机器数是（）
首先：short类型是16位，计算机机器数是补码，找-8190的补码，位数不够在前面补0，直到连同符号位一起占16位，1 1100000 00000010
3. IEEE754标准
注意！！！：正反都要会
前提，先换算成1.Mx2^e的形式，再计算E和M（二进制，注意小数的二进制转换方法）
组成：1位符号位（S）+8位阶码（E）+23位尾数（M）
对应真值：（-1）^S x （1.M）x 2^e，其中e=E的十进制表示-127
E的十进制表示的范围：1～254
特殊：
1. 当阶码全为 0 ，尾数不全为 0，表示 非规格化小数 ，用来表示比最小绝对值还要小的数，即
尾数码 隐含的最高位不是 1，而是 0；
阶码真值 固定为 -126，而非 -127；
2. 当阶码全为1，尾数全为0，表示无穷大
3. 当阶码全为1，尾数不全为0，表示非数值NaN
4. OF、CF计算
CF是无符号数溢出标志，OF是有符号数溢出标志。相应地将数值看成有符号数和无符号数
1、CF的判断
①加法
十进制角度，如果两无符号数相加，结果大于2^n-1（n为位数），则CF=1，否则CF=0；
二进制角度，如果两无符号数相加，最高位向前有进位，则CF=1，否则CF=0。
②减法
十进制角度，如果两无符号数相减，减数大于被减数（也即结果不在0—2^n-1内），则CF=1，否则CF=0；
二进制角度，如果两无符号数相减，最高位向前游借位，则CF=1，否则CF=0。
2、OF的判断
①加法
十进制角度，如果两有符号数相加，结果不在-2^(n-1)~2^(n-1)-1内，则OF=1，否则OF=0；
二进制角度，如果两有符号数同号，而相加结果与之异号，则OF=1，否则OF=0。
②减法
十进制角度，如果有符号数相减结果不在-2^(n-1)~2^(n-1)-1内，则OF=1，否则OF=0；
二进制角度，如果两个数异号，而相减结果与被减数符号相反，则OF=1，否则OF=0；
总结：判断OF：十进制数如果够减够加（不超出范围）则OF=0，否则为1；判断CF：将符号数转为无符号数（符号位看作本身位），如果够减、够加（不进位），CF=0，否则为1。
溢出位的作用：计算机并不知道计算是否溢出，例如int32位，即使溢出，计算机只会存32位，所以要用溢出位来判断存的数是否正确。
5. 寻址
寄存器中存操作数还是操作数的地址主要与寻址方式有关。
指令寻址：顺序寻址、跳跃寻址（转移的有效地址）
数据寻址：
1.立即寻址：操作数就在指令中，紧跟在操作码后面，作为指令一部分存放在内存的代码段中，该操作数为立即数，以补码的形式存放
2.直接寻址：存储单元的有效地址EA（即：操作数的有效地址）直接由指令给出。
3.间接寻址：给出的不是操作数的地址，而是存放操作数地址的主存单元地址，再访问一次地址才能找到操作数
4.寄存器寻址：指令给出一通用寄存器编号，指定的寄存器中存放着操作数（从寄存器读取数据比主存快得多）
5.寄存器间接寻址：指令给一通用寄存器编号，寄存器中存放操作数的有效地址，操作数在主存中
6.变址（便于处理数组）/基址/相对寻址：指令给出的地址A+变址/基址寄存器/程序计数器PC的地址=操作数的有效地址
6. 数据通路组成
数据通路由组合逻辑元件（操作元件）和时序逻辑元件（状态元件）组成。
操作元件：任何时刻的输出只和当前时刻有关系。常见的操作元件：多路选择器、编码器、译码器、移位器、比较器、算术逻辑部件。
状态元件：任何时刻的输出不仅和当前时刻有关，还和之前的时刻有关。常见状态元件：程序计数器、通用寄存器、触发器等。
7. 总线传输
单机系统中，三总线结构的计算机的总线系统一般由：内存总线、I/O总线、DMA总线组成
总线标准：ISA（系统总线，其他局部）、EISA、PCI、PCI-Express、USB（串行）
总线宽度：指数据总线的根数，用位来表示
总线时钟周期：1/总线时钟频率（1GHZ的时钟频率对应1ns的时钟周期）
带宽：单位时间内，总线上最多可传输数据的位数
带宽是评价总线性能的重要指标，带宽=工作频率x（宽度/8）（因为宽度通常用b）
注意！！！b和B的区别，b是bit的缩写，意思是比特位；B是Byte的缩写，意思是字节；换算：8b=1B
总线传输：支持突发传送和不支持突发传送
区别：支持突发传送只需要首次传输地址、之后只需要传输数据和准备数据就可以了
不支持突发传送需要每次都传输地址、传输数据、准备数据
注意！！一般读取主存块涉及多次总线传输
概念题：
总线是两个或多个部件之间进行数据交换的传输介质
同步总线：通信双方采用同一个时钟信号，但是总线事务不一定在一个时钟周期内完成，即工作频率
异步总线：通过握手的方式进行通信，每握一次进行一次通信
8. 指令执行
已知：
1. 流水线：取指：IF，译码：ID，执行：EX，访存：MEM，写回：WB
2. MEM vs WB：访存是指 CPU 与内存之间进行数据的读取或写入操作。主要用于从内存中获取数据，或将计算结果存储到内存中。写回是指将 CPU 内部寄存器中的计算结果写回到目标寄存器或内存中。将执行结果保存，以供后续指令使用，确保数据的一致性。
3. 数据冒险：数据冒险是指在流水线处理过程中，由于指令之间存在数据依赖关系，导致某一指令在执行时需要的数据尚未准备好，从而影响到程序的正确性。
4. 控制冒险是指由于控制流改变（如条件跳转或分支指令）而导致的流水线执行不确定性，影响指令的正确执行。
5. 旁路转发避免数据冒险：原需要在上一阶段MEM后，现在ID后直接可以转个下一阶段
6. 硬件阻塞（插入气泡）：在分支指令之后，处理器会插入一个或多个空操作周期（气泡）。这些周期不会执行任何有效的指令，只是让流水线暂停，直到处理器能够确定下一条指令。
例题：2023.19
阻塞防止冒险（I2～I4阻塞）：
| I4 | IF | ID | EX | MEM | WB | |||||||||||
| I3 | IF | ID | EX（写pc） | MEM | WB | |||||||||||
| I2 | IF | ID | EX | MEM | WB | |||||||||||
| I1 | IF | ID | EX | MEM | WB | |||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
旁路转发（上一阶段EX后直接将结果转发给下一阶段EX，不用等WB）+硬件阻塞：
| I4 | IF | ID | EX | MEM | WB | ||||||
| I3 | IF | ID | EX | MEM | WB | ||||||
| I2 | IF | ID | EX | MEM | WB | ||||||
| I1 | IF | ID | EX | MEM | WB | ||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
9. 中断
中断事件由硬件发现，软件处理
（1）内部中断，异常：指令执行错误或中断指令产生的内部中断，在指令执行的过程中被检测。异常分为故障、自陷、终止。故障（Fault）：指令执行引起的异常，例如缺页（注意！！缺页中断后，需要回到原指令重新执行）、除0、溢出等。自陷（Trap）：事先安排的异常事件，用于在用户态下调用操作系统内核程序。终止（Abort）：CPU出现了无法继续执行的硬件故障，如控制器出错等。异常不能被屏蔽。
（2）外部中断，硬件中断：指令执行完成后，CPU会检查中断请求信号，如果有中断请求发生，则进行中断响应，暂停当前的任务，保存现场并处理中断。分为可屏蔽中断和不可屏蔽中断。可屏蔽中断指通过INTR线发出的中断请求，通过改变屏蔽字可以实现多重中断。不可屏蔽中断是指通过NMI线发出的中断请求，通常是紧急硬件故障，如电源掉电等。
（3）故障异常、自陷异常是软中断、终止异常和外部中断为硬件中断。
大多数的中断处理流程：
1）关中断。CPU响应中断后，在保护现场的过程中不允许响应更高级的中断请求。
2）保存断点。保存原来程序的断点（程序计数器PC）。
3）引出中断服务程序。把中断服务程序的入口给到程序计数器。
4）保护现场和屏蔽字。
5）开中断。允许更高级的中断请求
6）执行中断服务程序。
7）关中断。保证在恢复的现场时不被打断
8）恢复现场和屏蔽字。
9）开中断、中断返回。返回到原来程序的断点处。
（1）外设通过中断控制器向CPU发送中断请求信号，CPU无需向外设发送中断终止信号
（2）外设准备数据的时间应大于中断处理时间，因为一般会设置缓冲区，如果准备数据时间太快，可能会导致缓冲区数据被覆盖
10. I/O控制方式
基本控制方式有4种：
（1）程序查询方式：由CPU通过程序不断查询I/O设备是否已做好准备，从而控制设备与主机交换信息。（CPU执行查询程序）
（2）程序中断方式：只在I/O设备准备完毕并向CPU发送中断请求时才予以响应。（CPU执行中断服务程序）
（3）DMA方式：主存和I/O设备之间有一条直接数据通路，当主存和I/O设备交换信息时，不需要调用中断服务程序。（不需要CPU参与，不需要保护中断现场，以数据块为单位）
（4）通道方式：在系统中设有通道控制部件，每个通道都挂接若干设备，主机在执行I/O命令时，只需启动有关通道，通道将执行通道程序，从而完成I/O操作。（CPU主要负责初始化和启动通道，而在通道执行I/O任务时，可以继续处理其他任务。）
（1）（2）主要由程序实现，用于数据传输速率比较低的外部设备，（3）（4）主要由硬件实现，用于传输速率比较高的设备。
11. Cache缓存器
主存=比较器位数（Tag）+组号（块号占的位数）+块内地址（与主存块大小相等）
（1）m路组相连映射方式：每行m个标记位，每次要和m比较，选择一个存入，因此需要m个比较器；比较器位数=Tag占的位数
（2）直接映射方式：组号位数=物理地址中组号的位数，Cache行位数=Tag+块内地址
（3）回写：+1脏位+1有效位
12. DRAM芯片
内存条：8x8192x8192的单位是bit
地址引脚：内存大小占多少位
行缓冲区：一行的大小
DRAM存储容量512Kx8位；512K代表字线，连接地址，2^19=512K，所以需要19条地址线；
8位是位线，连接数据，所以需要8条数据线。
DRAM的刷新方式：集中刷新、异步刷新、分散刷新
13. 指令集体系结构
指令集体系结构（ISA）主要规定了计算机系统的指令集、数据类型、寄存器架构、寻址模式以及输入输出操作等内容。
零地址、一地址、二地址
14. 汇编（特殊寄存器）
源文件转变为可执行目标文件：预处理-》编译-》汇编-》链接四个阶段
汇编语言程序员可见：基址寄存器、状态/标志寄存器、程序计数器PC、通用寄存器组。
另：指令寄存器（MAR、MDR、IR）是CPU内部寄存器，微指令寄存器是硬件的。
存储器：ROM、RAM，内存按工作原理分为ROM、RAM
专用寄存器：
（1）程序计数器PC：用于存放现行指令地址，具有计数功能，决定指令的执行顺序
（2）指令寄存器IR：用于存放当前准备执行的指令
（3）存储器数据寄存器MDR：用于存放准备存入存储器的数据，或者最近从存储器取出的数据
（4）存储器地址寄存器MAR：用于存放将被访问的存储单元地址
（5）状态标志寄存器PSW：保留由算数指令和逻辑指令运算或测试结果建立的各种条件代码
某机字长32位，存储容量64MB，若按字遍址，则MAR和MDR的位数分别为多少？
注：字为bit,B为字节，8bit=1B
MDR的位数为32
MAR的位数为64MB/32bit=2^24，故其位数为24
二地址指令中，操作数的物理地址可以在：内存、寄存器、指令中
15. 并行处理技术
MMID：多计算机系统、多处理器系统
向量处理器是SIMD的变体
硬件多线程技术：在一个核里处理多个线程，用于单核处理器
共享内存处理器（SMP)：共享单一物理地址空间，所有核都可以通过存取指令来访问同一片主存地址空间
六、信息新技术
1. 分布式数据处理
（1）区块链
区块链是分布式数据存储的新模式。
特征：去中心化（每个节点高度自治，都有可能成为中心）、开放性、不可篡改、可追溯性、匿名行
（2）Hadoop
Hadoop是对海量数据进行分布式处理的软件框架，成本低，任何人都能使用
特点：高可靠、高扩展、高效性、高容错性
2. 物联网
1999年提出物联网的概念
物联网四层模型：感知识别层、网络构建层、管理服务层、综合应用层
物联网应用的关键技术：传感器技术、RFID技术、嵌入式系统技术
3. 大数据基础
大数据四大特征：数据规模大（基本属性）、数据类型多、数据处理速度快、数据价值密度低
大数据结构：结构化（二维表）、半结构化（XML、JSON）、非结构化（文档、图片）
数据预处理：数据清理、数据集成、数据变换、数据归约
数据挖掘常用算法：分类、聚类、关联规则、时间序列预测
4. 神经网络
神经网络特点：大规模并行处理、自适应自组织自学习能力、分布式存储、弹性拓扑、高度冗余、
非线性运算
根据神经元连接方式不同：前馈型（BP）、反馈型（Hopfield）
按工作方式分：同步和异步
研究内容：生物原型、建立模型、算法
5. 机器学习
研究内容：学习机理、学习方法、学习系统
按学习方式分：机械式学习、指导式学习、示例学习、类比学习、解释学习
按学习能力：监督、非监督、强化
按推理方式：基于演绎、基于归纳
6. 硬件技术
ARM微处理器，32位设计；ARM（32位）和Thumb（16位）两种状态；
操作数寄存器为0，换ARM；在Thumb出现异常，换为ARM；
操作数寄存器为1，换Thumb；在Thumb出现异常，异常处理完之后，换Thumb
总结：只有在寄存器状态为0和Thumb状态下出现异常才会是ARM状态
FPGA：现场可编程逻辑门阵列，由RAM、逻辑单元、乘法器等硬件组成；只能进行定点运算；采用CMOS工艺，功耗低；所有功能都依靠硬件实现，无法实现分支条件跳转等操作。
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
13
0- 0
已为社区贡献2条内容
所有评论(0)