首页 计算机

# 编译原理理论

参考教材：清华大学《编译原理》第三版。
另参考：本人的编译原理老师的授课内容。
如有错误，欢迎指正。

目的：梳理编译原理课程的核心知识，另一方面为了更好地备考期末。
形式：目录罗列知识结构、问答题强化知识、信息栏回忆知识。
每次我将这些知识总结、整理到博客上时，内心都很满足和愉悦。

# 概论

# 编译过程

词法分析是编译过程第一个阶段。这个阶段的任务是从左到右一个字符一个字符地输入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。

语法分析是编译过程的第二个阶段。语法分析在词法分析的基础上将单词序列分解成各类语法短语，得到抽象语法树。语法分析依据的是语言的语法规则，通过语法分析确定整个输入串是否构成一个语法上正确的程序。

语义分析审查源程序有无语义错误，为代码生成阶段收集类型信息。

中间代码生成将源程序变成一种内部表示形式，即中间代码，这是一种结构简单、含义明确的记号系统。

代码优化是对前一阶段产生的中间代码进行变换或改造，目的是使得生成的目标代码更加高效，节省时间与空间。

目标代码生成把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码，与硬件系统结构和指令含义有关。

  1. 编译过程主要有哪几个阶段？ 词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。

    考察编译原理的基本认识。

  2. 词法分析的输入是什么？输出是什么？ 输入是字符，输出是单词（token）序列

    考察词法分析的输入和输出。

  3. 语法分析的输入是什么？输出是什么？ 输入是词法分析输出的 token 序列，输出一般是抽象语法树

    考察语法分析的输入和输出。

  4. 语义分析的输入是什么？输出是什么？ 输入输出均为标识符。具体来说，输入是 token ($id, 标识符名表地址)，输出是新的 token ($id, 符号表地址)

  5. 中间代码的一种常见形式是近似 “三地址指令” 的四元式，请问四元式形式是 。

    • (运算符，运算对象 1，运算对象 2，结果)
    • (运算对象 1，运算符，运算对象 2，结果)
    • (结果，运算符，运算对象 1，运算对象 2)
    • (运算符，运算对象 1，运算对象 2)

# 编译程序的结构、编译阶段的组合

编译阶段的前端：主要依赖于源语言而与目标机无关。
编译阶段的后端：依赖于目标机而一般不依赖于源语言，只与中间代码有关的那些阶段的工作。

一个编译过程可由一遍、两遍或多遍完成，一遍完成的编译过程称为单遍扫描，两遍或多遍完成的编译过程称为多遍扫描。

  1. 上述编译过程的 6 个阶段的任务可以分别由 6 个模块完成，分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序。此外，一个完整的编译程序还必须包括 表格管理程序和出错处理程序。

    考察对编译程序的全面认识。

  2. 编译阶段的前端有哪些阶段？

    • 词法分析
    • 语法分析
    • 语义分析
    • 中间代码生成

    考察编译阶段的前端。
    某些代码优化工作也可在前端做，还包括与前端每个阶段相关的出错处理工作和符号表管理工作。

  3. 编译阶段的后端主要有哪些工作？

    • 词法分析
    • 目标代码生成阶段
    • 出错处理工作
    • 符号表管理工作

    考察编译阶段的后端。

  4. 占内存空间少，但时间消耗大的扫描方式是？

    • 多遍扫描
    • 单遍扫描
    • 两者都是
    • 不知道

    单遍扫描时间消耗小，但是占内存空间大，需要一次性存储所有信息。

# 解释程序与存储组织

  1. 解释程序一个个的获取、分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员以 交互方式 工作的情况。

    程序的解释是非常慢的。

  2. 在编译阶段，存储区主要为 源程序 (中间形式) 和目标代码 开辟空间，要存放编译需要的各种 表格。在运行阶段，存储区主要是 目标代码 和 数据

  3. 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。
    (1) else 没有匹配的 if。 语法分析
    (2) 数组下标越界。语义分析
    (3) 使用的函数没有定义。语法分析
    (4) 在数中出现非数字字符。 词法分析

    语法分析通常解决匹配问题。如，使用的函数没有定义，说明没有声明部分与之匹配。又如第一题的 else 没有与 if 匹配。
    跟字符有关的通常是词法分析

# 文法和语言

# 形式定义

  1. 文法 G 定义为四元组（V,Q,P,S）。其中，V 是 非终结符集；Q 是 终结符集；P 是 一组产生式；S 是 文法初始符。

  2. 终结符通常用什么表示？小写字母 非终结符通常用什么表示？大写字母

  3. ABsa 是句子？（）

    所有字符为终结符才是句子。

  4. B->dAaui，则 dAaui 是句型？（）

    句型是推导得到的符号串，可由终结符和非终结符组成。

  5. 文法描述的语言是该文法一切 句子 的集合。

# 文法类型

  1. 如果一个文法的每个产生式左部至少含一个非终结符，则这种文法是 0 型文法

    0 型文法又称为短语文法。

  2. 如果一个文法的每个产生式左部只有一个非终结符，则这种文法是 2 型文法

    2 型文法又称为上下文无关文法，是当前语言使用最多的文法。

  3. 如果一个文法的每个产生式的形式都是 A->aB 或 A->a，则这种文法是 正规文法

    正规文法即为 3 型文法。

  4. 如果一种文法的每个产生式右部的符号个数不少于左部符号的个数，则这种文法是 1 型文法

    1 型文法又称为上下文有关文法。

# 语法树

  1. 给定一个文法，其语法树唯一。（）

    对于一个文法，语法树不一定唯一。

  2. 语法树结构中，根节点一定是文法开始符。（）

  3. 语法树结构中，叶结点一定是终结符。（）

    叶结点可以是终结符也可以是空串。

  4. 最右推导是规范推导。（）

    最右推导得到的句型称为右句型。最左推导得到的句型称为左句型。

  5. 每个句子都有最左推导和最右推导，但是每个句型不一定有最左推导和最右推导。（）

  6. 当某个文法中存在某个句子有两个不同的最左（最右）推导，则这个文法是二义的。（）

# 语法分析初步

  1. 文法的短语是文法初始符经过多步推导得到的所有子串。（）

  2. 短语中经过一步推导得到的子串称为直接短语。（）

    直接短语又称为简单短语。

  3. 该文法的句柄是该文法最后一步推导得到的直接短语。（）

  4. 句柄只适用于左句型。（）

    句柄只适用于右句型，因此通常用最右推导求句柄。

  5. 自顶向下语法分析方法的关键是什么？ 寻找候选式

  6. 自底向上语法分析方法的关键是什么？ 寻找句柄

  7. 规范推导的逆过程是规范规约。（）

    错！规范推导的逆过程是规范归约。“归”。

  8. 闭包比正闭包多了空串。（）

值得一提的是，你需要掌握根据给定文法，使用最右推导和语法树，求某个给定句型或句子的短语、直接短语、句柄。

你需要了解的文法描述能力对比图：

image

很明显，从中能够看到几个特点：
（1）LL (k) 文法仅仅只能表现 LR (k) 文法的一部分。
（2）（k）一定比（k-1）的描述能力更强，毕竟较后者多一个展望符。

# 词法分析

# 词法分析与语法分析的接口方式

  1. 词法分析与语法分析的协同工作关系决定了两者之间存在接口方式的规定，最容易想到的方式是词法分析工作是独立的一遍，把字符流的源程序变为 单词序列（token），输出到一个中间文件，以供语法分析使用。

    考察词法分析的输出。词法分析的输出是单词序列（token）
    词法分析的接口方式还有两种，一种是词法分析程序作为语法分析程序的子程序，当语法分析程序需要一个单词时，就调用词法分析程序。还有一种是协同程序方式，词法分析程序与语法分析程序以生产者消费者的方式同步进行。

  2. 你能想到的词法分析任务有哪些？如下

    （1）组织源程序的输入。（2）删除注释，无用空格。（3）查填标识符名表。（4）检查词法错误。（5）记录遇到的换行符个数，以便提供词法报错信息。（6）识别单词，转换成机内表示形式，即 token 的二元式表示。

# 标识符名表

  1. token 的机内表示方式采用二元式表示：（单词种别，单词自身值），如常数 5 的二元式是（2,'5'），其中，2 这个编码代表种类是常数，'5' 代表值。（）

  2. 所有 token 的二元式形成的表格称为标识符名表。（）

  3. token 中，关键字、界限符、运算符的单词类别编码足以表示其完整信息，因此对于这些 token，它们二元组的单词属性值常为空。（）

  4. 标识符的 token 的二元式表示为：（标识符的类别编码，指向该标识符所在符号表中位置的指针）（）

  5. 标识符名表就是符号表。（）

    标识符名表常用于词法分析，而符号表常用于语义分析。

# 正规文法和正规式

  1. 正规式又称为正则表达式，也可以认为是字符串的形式规则，这种规则能表示的所有字符串的集合称为正规集。（）

  2. 空串不是正规式。（）

  3. 一个字符也能是正规式。（）

  4. 如果 a,b 是正规式，那么 (a)、a|b、a・b、a * 也是正规式（* 表示闭包）。（）

  5. (a|b)* 等价于 (a|b)(a|b)...(a|b)。(a*|b*) 等价于 (a|b)*。（）

  6. 如果 d 表示 0-9 中的数字，那么 dd * 可以表示空串。（）

    dd * 表示至少一个数字。

  7. 若两个正规式 a 和 b 所表示的 正规集 相同，则说 a 和 b 等价。

交代一些正规式的代数规律：
（1）r|s = s|r “或” 满足交换律
（2）r|(s|t)=(r|s)|t "或" 的可结合律
（3）(rs) t=r (st) "连接" 的可结合律（“连接” 可以理解为 “与”）
（4）r (s|t)=rs|rt, (s|t) r=sr|tr 分配律
（5）ϵ\epsilonr=r, rϵ\epsilon=r ϵ\epsilon 是 “连接” 的恒等元素
（6）r|r=r “或” 的抽取律
（7）r**=r 幂等性
（8）r*=(r|ϵ\epsilon)* 闭包一定包含空串

# 有穷自动机

有穷自动机 FA 作为一种识别装置，能准确地识别正规集。
有穷自动机分为两类：确定地有穷自动机 DFA 和不确定地有穷自动机 NFA。

  1. 一个确定的有穷自动机 DFA 可以用五元组 M 表示：M=(K,∑\sum,ff,S,Z)。K 是 状态集。∑\sum 是 输入符号表。ff 是 转换函数。S 是 初始状态。Z 是 终态集。

    考察 DFA 的五要素。

  2. DFA 只能有一个初始状态，但是可以有多个终态。（）

  3. DFA 可以表示成一个状态图。其中，初态状态冠以 =>，终态用双圈表示。（）

    考察 DFA 状态图。

  4. DFA 状态图的弧上允许有空串。（）

    DFA 不允许空串转换。

  5. DFA 还可以表示成一个状态表，行表示状态，列表示输入符号，矩阵元素表示相应状态经过输入符号转换的新状态。（）

    考察 DFA 状态转换表

  6. 一个符号串，能被自动机识别，在于从初始状态到终止状态存在一条道路。（）

  7. DFA 的状态图中，从一个状态结点出发的弧的数量是无限制的。（）

    DFA 的每个状态结点，只能伸出 n 条弧，这个 n 是输入符号表的长度，即状态转换表中有效列的个数。

  8. 一个不确定的有穷自动机 NFA 能被一个五元组表示：M=(K,∑\sum,ff,S,Z)，其中 K 是状态集、∑\sum 是输入符号表、ff 是转换函数、S 是 非空状态集、Z 是终态集。

    NFA 的初态可以不止一个。

  9. NFA 的状态图的弧上允许有空串。（）

  10. NFA 的状态图中，每个状态结点伸出的弧的数量没有限制。（）

值得一提的是，你需要掌握将 NFA 转换为 DFA，使用子集构造法对 DFA 最小化，并判断给定的符号串能否被最小化 DFA 识别。

# 自顶向下语法分析

# 自顶向下思想

自顶向下分析方法从文法的开始符号出发企图推导出与输入的单词符号串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。

  1. LL (1) 分析方法有递归下降分析方法和表驱动的 LL (1) 分析方法。（）

  2. 自顶向下分析方法的四个动作是 推导 -> 匹配 -> 成功 -> 报错

  3. 自顶向下分析方法分为确定的自顶向下分析方法和不确定的自顶向下分析方法。（）

  4. 递归下降方法和 LL (k) 分析方法都属于不确定的自顶向下分析方法。（）

    都属于确定的自顶向下分析方法。

  5. 确定的自顶向下分析方法要尽可能地消除 回溯

  6. 确定的自顶向下分析方法的 “确定” 含义在于，对于一个非终结符，通过给定的一个输入字符，推导得到的符号串是唯一的。（）

    换言之，一个非终结符，通过给定的输入符号，选择的候选式是唯一的，而不确定的自顶向下分析方法选择的候选式是不唯一的。

# LL（1）分析方法

  1. FIRST 集允许有空串。（）

  2. 尾符（$、#）可含于 FOLLOW 集中，而空串不能。（）

  3. 文法初始符的 FOLLOW 集一定不包含尾符。（）

    FOLLOW 集由于文法初始符一定包含尾符，故 FOLLOW 集可以包含尾符。同时，FOLLOW 集还不允许包含空串。

  4. 给定上下文无关文法的产生式 A->aBc，若 B 导空，则 A 导空。（）

    导空条件是右部的所有文法符号均导空，不能只导空一个。换言之，只要出现一个终结符，这个产生式左部对应的非终结符一定不导空。

  5. 给定上下文无关文法的产生式 A->a，如果 a 不导空，则该产生式的 SELECT 集为 FIRST (a)。（）

  6. 给定上下文无关文法的产生式 A->a，如果 a 导空，则该产生式的 SELECT 集为 FIRST (a)∪\cupFOLLOW(A)。（）

    (FIRST(a) - ϵ\epsilon) ∪\cup FOLLOW(A)

  7. 一个上下文无关文法是 LL (1) 文法的充分必要条件是，对每个非终结符 A 的所有不同产生式，以两个为例，A->a, A->b，满足 SELECT (A->a) ∩\cap SELECT (A->b) 等于空集。

  8. LL (1) 的第一个 L 含义是使用最左推导，第二个 L 的含义是自左向右扫描输入串。（）

    1 表明只需向右看一个符号便可决定如何推导。

  9. 如果 A 和 B 均为非终结符，则 FIRST (AB) = FIRST (A)。（）

    FIRST (AB) = FIRST (A) 和 FIRST (B) 的并集。

  10. 如果产生式 X->aB，则 FIRST (X)={a}。（）

  11. 如果产生式 X->ϵ\epsilon，则 FIRST (X)={ϵ\epsilon}。（）

  12. 如果产生式 X->Ab，A 不可导空，则 FIRST (X)=FIRST (A)。（）

  13. 如果产生式 X->ABCD，A,B,C 均导空，D 不可导空，则 FIRST (X)=FIRST (A) ∪\cup FIRST(B) ∪\cup FIRST(C) ∪\cup FIRST(D)。（）

    正确的公式应该是：FIRST (X)=(FIRST (A)-ϵ\epsilon) ∪\cup (FIRST(B)-ϵ\epsilon) ∪\cup (FIRST(C)-ϵ\epsilon) ∪\cup FIRST(D)。

  14. 如果产生式 X->ABCD，A,B,C,D 均导空，则 FIRST (X)=FIRST (A) ∪\cup FIRST(B) ∪\cup FIRST(C) ∪\cup FIRST(D)。（）

    正确的公式应该是：FIRST (X)=FIRST (A) ∪\cup FIRST(B) ∪\cup FIRST(C) ∪\cup FIRST(D) ∪{ϵ}\cup \{\epsilon\}。

  15. 如果有上下文无关文法的产生式 A->aBC，C 是非终结符 B 后面的文法符号串，则 FOLLOW (B) 一定包含 FIRST (C)。（）

  16. 在第 80 题的基础上，如果 C 导空（如 C 实际上是多个非终结符 DEF，D,E,F 均导空），则 FOLLOW (B) 还包含 FOLLOW (A)。（）

  17. 求文法的所有非终结符的 FOLLOW 时，当每个非终结符的 FOLLOW 集不再增大时停止。（）

  18. 一个 LL (1) 文法一定不存在左递归和左公因子。（）

  19. 递归下降分析方法也需要每个非终结符的所有产生式满足 SELECT 集的交集为空。（）

  20. 使用表驱动的 LL (1) 分析方法对输入符号串进行一栈一流分析时，当且仅当栈顶为 [尾符 ($ 或 #)]，而且输入流指针指向 [尾符 ($ 或 #)]，两者匹配才表示该输入字符串符合文法。

  21. 表驱动的 LL (1) 分析方法在对输入符号串进行一栈一流分析时，栈中的非终结符选择候选式进行推导展开时，输入流不变。（）

    对，输入流顶部字符被抵消，当且仅当栈顶元素与输入流顶部字符匹配。

  22. 如果栈的顶部是非终结符 A，则要选择与当前输入符相匹配的 A 的产生式，并用该产生式的右部替换栈顶的非终结符。（）

  23. 一栈一流分析的分析栈从文法初始符开始。（）

  24. LL (1) 预测分析表的行只有非终结符，列只有输入符和空串。（）

    列不含空串，而且不只含输入符，还包含尾符。

  25. 递归下降分析方法内存要求高，适用于小规模文法。（）

预测分析表每个矩阵元素的内容是一条关于某个非终结符 A 的产生式，表明当用非终结符 A 向下推导时，面临输入符 a 时所应采取的候选产生式。

# 自底向上语法分析

# 基本思想

自底向上是对输入符号串自左向右扫描，并将输入符号逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或其他可归约串时就进行归约。归约的结果是将句柄或其他可归约串从栈顶部分弹出，而将相应的非终结符压入栈中。重复这个过程直到归约到栈中只剩文法初始符时则为分析成功，也就确认了输入串是文法的句子。

  1. 自底向上分析方法的四个动作是什么？

    • 移入、归约、成功、报错。
    • 推导、匹配、成功、报错。
    • 移入、匹配、成功、报错。
    • 推导、归约、成功、报错。

  2. 自底向上四个动作中移入是将输入符号从输入流中移入到 。

    • 状态栈。
    • 符号分析栈。
    • ACTION 表。
    • GOTO 表。

  3. 符号分析栈从尾符开始。（）

# LR (0) 分析方法

LR 分析基本思想是：（1）历史信息：记住已经移入和归约的整个符号串。（2）预测信息：根据所用的产生式推测未来可能遇到的符号。

  1. LR (k) 中的 L 的含义是 自左向右扫描输入流；R 的含义是 构造最右推导的逆；k 的含义是 分析动作向前所看的输入流符号个数。

  2. LR (k) 分析方法相较 LL (k) 分析方法和自底向上优先分析方法的优点是 分析速度快，准确，对文法限制少，能指出出错位置，相应的缺点是 对一个实用语言文法的分析器的构造工作量相当大

你可能需要掌握消除一个文法中的空产生式的算法。

  1. 为了防止文法初始符出现在文法产生式右部，在原文法 G [S] 中增加产生式 S'->S，S 为原文法 G 的开始符号，所得的新文法 G' 称为原文法 G 的 拓广文法。

  2. 在文法 G 中每个产生式的右部适当位置添加一个圆点构成 项目。

  3. 一个产生式 S->aAcBe 对应有 6 个项目：[0] S->.aAcBe,[1] S->a.AcBe, [2] S->aA.cBe,[3] S->aAc.Be,[4] S->aAcB.e,[5] S->aAcBe.。归约项目是圆点在产生式最右端的 LR (0) 项目，如 [5]。接受项目是对文法初始符的归约项目，即 [[5]]。待约项目是圆点后第一个符号为非终结符的 LR (0) 项目，如 [1] 和 [3]。移入项目是圆点后第一个符号为终结符的 LR (0) 项目，如 [0]、[2] 和 [4]。

  4. 若句型αβ\alpha \beta 中，β\beta 是终结符串或空串，（说明α\alpha 是非终结符串），则α\alpha 是 前缀

  5. 若作为前缀的α\alpha 不含句柄或含一个句柄且具有形式α=α′π\alpha=\alpha'\pi（π\pi 是句柄），则称前缀α\alpha 是 活前缀。

  6. 若α\alpha 是含句柄的活前缀，即有α=α′π\alpha=\alpha'\pi，且π\pi 是句柄，则α\alpha 是 归约活前缀。

  7. 若有项目集 IS={.abd [1], .abc [2], .bc [3], .de [4], de.c [5]}，则项目集 IS 对 a 做投影 IS (a)={a.bd[1],a.bc[2]{.gap}}。

> 以此类推，IS(b)={b\.c[3]}, IS(c)={dec\.[5]}。
  1. 例如有如下文法 G [E']：
(1) E'->E
(2) E->T
(3) T->F
(4) F->id
(5) E->E+T
(6) T->T*F
(7) F->(E)

则产生式 E'->E 关于项目 I={E'->.E} 闭包 CLOSURE ([E'->.E]) 为？{.quiz .multi}
- E'->.E {.correct}
- E->.T {.correct}
- E->.E+T {.correct}
- E->E+.T
- T->F.
- T->.F {.correct}
- T->.T*F {.correct}
- F->.id {.correct}
- F->.(E) {.correct}
- F->id.

  1. LR (0) 项目集规范族又称为 LRSM、LR 自动机、DFSA。

  2. 如下项目集：
    A->α\alpha.αβ\alpha\beta
    B->\gama.
    存在 移入 - 归约冲突。

  3. 如下项目集：
    A->β\beta.
    B->\gama.
    存在 归约 - 归约冲突。

  4. 对一个文法的 LR (0) 项目集规范族不存在 移入 - 归约冲突或 归约 - 归约冲突时，称这个文法是 LR (0) 文法。

> LR(0)文法的项目集规范族的任何状态都不允许存在移入-归约冲突和归约-归约冲突。

  1. LR (0) 分析表由 ACTION 表和 GOTO 表组成。

  2. LR (0) 分析表中的 ACTION 表的列标是终结符和尾符。（）

  3. LR (0) 分析表中的 GOTO 表的列标是非终结符。（）

  4. ACTION [k,a] 为 S_j 的含义是，在状态 k，遇到终结符 a，将终结符 a 移入符号栈，将状态 j 压入状态栈。（）

  5. ACTION [k,a] 为 r_j 的含义是，在状态 k 使用第 j 个产生式（记为 S）对符号栈中的句柄进行归约，弹出符号栈中与 S 同长的符号，弹出状态栈中与 S 同长的状态，同时将 S 的左部非终结符（记为 M）压入栈顶，根据项目集规范族，查看状态栈栈顶非终结符遇到 M 能够 GOTO 到哪个状态（记为 k'），将 k' 压入状态栈栈顶。（）

  6. LR (0) 分析表的行号的含义是状态，从 0 开始。（）

  7. 找到包含能够归约到文法初始符的接受项目 I，在 LR (0) 分析表中，置 ACTION [I, 尾符]=acc，表示接受。（）

# SLR (1) 分析方法

  1. 如果 LR (0) 项目集规范族存在归约 - 归约冲突或移入 - 归约冲突，则这个文法不是 LR (0) 文法。例如，此时出现归约 - 归约冲突的状态涉及的产生式为：A->\gama.,B->θ\theta.。对所有涉及归约 - 归约冲突状态的产生式的左部非终结符求 FOLLOW 集。如果它们的 FOLLOW 集彼此互不相交，则这个文法是 SLR (1) 文法。（）

  2. 在第 116 题的基础上，对于出现移入 - 归约冲突状态涉及的产生式为：X->α\alpha.bβ\beta,A->\gama。移入项目的展望符为 b，如果满足归约项目的左部非终结符的 FOLLOW 集与展望符交集为空，那么这个文法依然是 SLR (1) 文法。（）

  3. 对于 SLR (1) 文法，在冲突状态中，如果输入符号 a 等于移入项目的展望符 b，则选择移入。如果输入符号 a 是某个非终结符的 FOLLOW 集的一个元素，那么则使用这个终结符的产生式进行归约。（）

# 数据库理论

# 绪论

# 数据库系统概述

  1. 描述事物的 符号记录 称为数据。

  2. 数据的 含义 称为数据的语义，数据与其语义是不可分的。

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

  4. 数据库中的数据具有较小的 数据冗余、较高的 数据独立性和 可扩展性，并可为各种用户 共享

  5. 数据库管理系统与操作系统都是软件，但数据库管理系统是操作系统和用户的接口，操作系统是软件和硬件的接口。

  6. 数据库管理系统的英文缩写是 DBMS。

  7. 数据库管理系统是位于 用户 和 操作系统 之间的数据管理软件。它和操作系统一样是计算机的基础软件。

  8. 数据库管理系统的主要功能有 {.quiz .multi}
    - 数据定义功能。 {.correct}
    - 数据组织、存储和管理功能。 {.correct}
    - 数据操纵功能。 {.correct}
    - 数据库的事务管理和运行管理功能。 {.correct}
    - 数据库的建立和维护功能。

  9. 数据定义语言的英文缩写是 DML，数据操纵语言的英文缩写是 DDL。

> 定义是DDL（Data Definition Language）。操纵是DML（Data Manipulation Language）。

  1. 数据库系统的英文缩写是 DBS。

  2. 数据库系统是指引入 数据库 的计算机系统，一般是指由 数据库、数据库管理系统、应用系统和数据库管理员组成的存储、管理、处理和维护数据的系统。

  3. 数据管理 是指对数据进行分类、组织、编码、存储、检索和维护，它是数据处理的中心问题。

  4. 数据库管理技术经历了 人工管理、文件系统和数据库系统 三个阶段。

  5. 人工管理阶段的数据有哪些特点？ {.quiz .multi}
    - 数据不保存。 {.correct}
    - 应用程序管理数据。 {.correct}
    - 数据不共享。 {.correct}
    - 数据不具有独立性。

  6. 文件系统阶段的数据有哪些特点？ {.quiz .multi}
    - 数据可以长期保存。 {.correct}
    - 数据由专门的软件进行管理。 {.correct}
    - 数据共享性弱，冗余度高。 {.correct}
    - 数据独立性弱。

  7. 数据库系统阶段的数据有哪些特点？ {.quiz .multi}
    - 整体数据结构化。 {.correct}
    - 数据的共享性强、冗余度低且易于扩充。 {.correct}
    - 数据的独立性强。 {.correct}
    - 数据由数据库管理系统统一管理和控制。

  8. 数据库管理系统除了提供第八题所述的主要功能外，还需要提供哪些功能？ {.quiz .multi}
    - 数据的安全性保护。 {.correct}
    - 数据的完整性检查。 {.correct}
    - 数据的并发性控制。 {.correct}
    - 数据库的恢复。

# 数据模型

  1. 数据模型也是一种模型，它是对现实世界 数据特征 的抽象。

  2. 什么是数据库系统的核心和基础？ {.quiz}
    - 概念模型。
    - E-R 图。
    - 数据模型。 {.correct}
    - 数据结构。

  3. 把现实世界中的具体事物抽象、组织为某一数据库管理系统所支持的数据模型，这个过程称为 数据建模

  4. 数据建模主要有两步，分别为 建立概念模型和 将概念模型转换为数据模型。

  5. 概念模型是按 用户 的观点来对数据建模，主要用于 数据库设计。

  6. 数据模型是按 计算机系统 的观点对数据建模，是数据库管理系统支持的，用于 数据库管理系统 的实现。

  7. 客观存在并可相互区别的事物称为 实体

  8. 实体所具有的某一特性称为 属性

  9. 唯一标识实体的属性集称为 码

  10. 同一类型实体的集合称为 实体集

  11. 实体内部的联系通常是指组成实体的 各属性 之间的联系，实体之间的联系通常是指 不同实体集 之间的联系。

  12. 实体之间的联系有一对一、一对多、多对多、多对一等多种类型。

> 实体之间的联系没有多对一的类型。
  1. 通常用 E-R 图 来描述现实世界的概念模型。
> 这种方式构建了一个E-R模型。

  1. 实体用 矩形 来表示。属性用 椭圆 来表示。联系用 菱形 来表示。

  2. 所有表都是实体。

> 并非所有的表都是实体，表是实体集的呈现方式与存储方式，表既可以是实体也可以是联系。
  1. 数据模型的三要素是 数据结构、数据操纵和完整性约束。
> 数据模型的三要素实际上就是数据模型的组成部分。

  1. 数据结构描述数据库的 组成对象 以及 对象之间 之间的联系。

  2. 数据操纵是指对数据库中各种对象（型）和实例（值）允许执行的 操作 的集合。

> 数据操纵包括数据操作以及有关的操作规则。

  1. 完整性规则是给定的数据模型中的数据及其联系所具有的 制约和依存规则，用以限定符合数据模型的数据库状态以及状态的变化，以保证数据的正确、有效和相容。

  2. 关系模型由一组关系组成，每个关系的数据结构是一张 规范化的二维表

  3. 关系表中的一行即为一个 元组

> 元组又称为记录。
  1. 关系表中的一列即为一个 属性
> 每列的名称即为属性名。

  1. 码 是关系表中的属性集，能唯一标识一条记录。

  2. 域 表示某一属性的取值范围，通常是一组具有相同数据类型的值的集合。

  3. 分量 是元组中一个属性值。

> 特指在元组内。
  1. 关系模式要求关系必须是 规范化 的。
> 规范条件中最基本的一条就是：关系的每个分量必须是一个不可分的数据项，即行不可分，不允许表中还有表。这就是1NF。

  1. 数据操纵是 集合 操作，操作对象和操作结果都是 关系。

  2. 关系模型有哪些优点？ {.quiz .multi}
    - 关系模型建立在严格的数学概念基础上。 {.correct}
    - 关系模型的概念单一。 {.correct}
    - 关系模型的存取路径对用户隐蔽。 {.correct}
    - 降低了开发关系数据库管理系统的难度。

> 关系模型的缺点是：查询效率较低；增加了开发关系数据库管理系统的难度。

# 数据库系统的三级模式结构

  1. 型是指对某一类数据的结构和属性的说明，值是型的一个具体赋值。

  2. 模式是数据库中全体数据的 逻辑结构 和 特征 的描述。

  3. 模式的一个具体值称为模式的一个 实例。

> 同一个模式可以有很多实例。

  1. 模式反映的是数据的结构及其联系，而实例反映的是数据库某一时刻的状态。

  2. 模式是所有用户的 公共数据 视图。

  3. 三级模式结构是指数据库系统是由 模式、外模式 和 内模式三级构成。

> 一个数据库对应一个模式。
  1. 外模式是数据库用户能够看见和使用的 局部 数据的 逻辑结构 和 特征 的描述。
> 外模式是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。
  1. 一个数据库只能有一个外模式。
> 一个数据库可以有多个外模式。

  1. 同一外模式也可以为某一用户的多个应用系统所使用，但一个应用程序只能使用一个外模式。

  2. 内模式是对数据 物理结构 和 存储方式 的描述，是数据在数据库内部的组织方式。

  3. 一个数据库只能有一个内模式。

  4. 两级映像实现了模式、内模式和外模式这三个抽象层次的联系和转换。两级映像包括 外模式 // 模式映像 和 模式 // 内模式映像

  5. 两级映像的存在，保证了数据库系统中的数据能够具有较强的逻辑独立性和物理独立性。

  6. 当模式改变时，数据库管理员对外模式 // 模式映像进行改变，可以使得 外模式 保持不变，因而应用程序不必修改，保证了数据与程序的逻辑独立性，简称 数据的逻辑独立性

  7. 一个数据库不只有一个外模式 // 模式映像。

  8. 当数据库的存储结构改变时，数据库管理员对模式 // 内模式映像进行改变，可以使 模式 保持不变，因而应用程序也不必改变，保证了数据与程序的物理独立性，简称 数据的物理独立性

  9. 数据库系统的组成包括硬件平台、软件平台、人员，其中人员包括 {.quiz .multi}
    - 数据库管理员。{.correct}
    - 系统分析员。 {.correct}
    - 数据库设计员。 {.correct}
    - 应用程序员。 {.correct}
    - 最终用户。

# 关系模型

# 关系模型的数据结构和形式化定义

  1. 笛卡尔积不允许域相同。

  2. 笛卡尔积是域上的一种集合运算。

  3. 一个域允许的不同取值个数称为这个域的 基数

  4. 笛卡尔积的基数由组成它的所有域的基数累乘而来。

  5. 笛卡尔积没有实际语义，只有它的某个真子集才有实际含义。

  6. 某组域上的笛卡尔积的子集称为这组域上的 关系

  7. 笛卡尔积的域的个数称为在这组域上关系的目（或度）。

> 目常被认为是属性列的个数。

  1. 关系有哪三种类型？ {.quiz .multi}
    - 基本关系（通常又称为基本表）。 {.correct}
    - 查询结果。 {.correct}
    - 视图。 {.correct}
    - 触发器。

  2. 基本关系有哪 6 条性质？ {.quiz .multi}
    - 列是同质的，每个列中的分量来自同一个域。 {.correct}
    - 不同的列可出自同一个域。 {.correct}
    - 列的顺序无所谓。 {.correct}
    - 行的顺序无所谓。 {.correct}
    - 每个分量必须是不可分的数据项。 {.correct}
    - 任意两个元组的码不能取相同的值。

  3. 在关系模型中，关系是元组的集合，关系是值；关系模型是对关系的描述，关系模式是型。

  4. 关系模式可以形式化地表示为：R (U,D,DOM,F)。其中，R 是关系名，U 是组成该关系的 属性的属性名 的集合，D 是 U 中属性所来自的 域，DOM 为属性向域的 映像集合，F 是属性间 数据依赖关系 的集合。

> 关系模式可以简写为：R(U)或R(A_1,A_2,...,A_n)，A_i是属性名。
  1. 若关系模式中某一个属性或一组属性的值能唯一地标识一个元组，而它的真子集不能唯一地标识一个元组，则称该属性或属性组为 候选码
> 若一个关系有多个候选码，则选定其中一个为主码。
> 候选码是能唯一标识一条记录的最小属性集。

  1. 候选码的诸属性称为 主属性。不包含在任何候选码中的属性称为 非主属性

  2. 关系模式的所有属性是这个关系模式的候选码，称为 全码。

  3. 关系模式是静态的、稳定的，而关系是动态的、随时间不断变化的。

  4. 关系数据库模式是关系数据库中 所有关系模式 的集合，是对关系数据库的描述。关系数据库是这些关系模式在某一时刻对应的 关系 的集合。

# 关系操作

  1. 哪些是 5 个基本关系操作？ {.quiz .multi}
    - 笛卡尔积。 {.correct}
    - 交。
    - 并。 {.correct}
    - 投影。 {.correct}
    - 连接。
    - F. 选择。 {.correct}
    - G. 差。 {.correct}
    - H. 补。
    - I. 除。

  2. 一个关系数据语言能够表示关系代数可以表示的查询，则称其具有完备的表达能力，简称 关系完备性

> 关系数据语言是用于操纵关系数据的语言。
  1. 关系数据语言类型有哪些？ {.quiz .multi}
    - 关系代数。 {.correct}
    - SQL 语言。 {.correct}
    - C 语言。
    - 关系演算。

# 关系的完整性

  1. 关系模型中有三类完整性约束：实体完整性、参照完整性和用户定义的完整性。

  2. 关系的两个不变性是指关系模型必须满足实体完整性和用户定义的完整性。

> 关系模式必须满足的两个完整性是实体完整性和参照完整性。

  1. 实体完整性约束的关键是 “主码非空且唯一”。

  2. 参照完整性约束的关键是 “外码为空或与被参照表主码相等”。

  3. 参照完整性约束中，外码在参照表中，外码与被参照表中的主码值相等。

  4. 参照完整性约束中，参照表和被参照表可以是同一张表。

# 数据库安全与触发器

# 存取控制

存取控制机制确保了只授权给有资格的用户访问数据库的权限，同时令所有未被授权的人员无法接近数据。存取控制机制主要包括定义用户权限和合法权限检查两部分。

  1. 存取控制方法分为 自主存取控制方法 和 强制存取控制方法。

  2. 自主存取控制方法中，同一用户对于不同的数据库对象有不同的存取权限。

  3. 自主存取控制方法中，不同用户对于同一数据库对象的权限相同。

> 不同用户对同一数据库对象的存取权限也不同。

  1. 自主存取控制方法中，用户可以将拥有的存取权限转授给其他用户。

  2. 强制存取控制方法中，每一个数据库对象都被标以一定的密级。

  3. 强制存取控制方法中，每一个用户会被授予某一个级别的许可证。

  4. 强制存取控制方法中，对于任意一个数据库对象，任何用户都能存取。

> 在强制存取控制方法中，只有具有合法许可证的用户才能存取当前的数据库对象。

# 触发器

触发器又叫做事件 - 条件 - 动作规则。当特定的系统事件（如对一个表的更新操作，事务的结束等）发生时，对规则的条件进行检查，如果条件成立则执行规则中的动作，否则不执行该动作。

  1. 触发器是用户定义在 关系表 上的一类由 事件 驱动的 特殊过程。
> 触发器类似约束，但是比约束更加灵活，可以实施更为复杂的检查和违约操作。
  1. 如下关于创建触发器的 SQL 语句，请判断是否正确： CREATE TRIGGER 后面要加触发器名。（）
CREATE TRIGGER SC_T
AFTER UPDATE ON SC
REFERENCING
OLD AS OldTuple
NEW AS NewTuple
FOR EACH ROW
WHEN(NewTuple.Grade >= 1.1 * OldTuple.Grade)
BEGIN
INSERT INTO SC_U(Sno, Cno, OldGrade, NewGrade)
VALUES(OldTuple.Sno, OldTuple.Cno, OldTuple.Grade, 			NewTuple.Grade)
END
  1. 在第 96 题的背景下， AFTER UPDATE ON SC 的含义是在 SC 表更新后激活触发器。于是对应有 BEFORE UPDATE ON SC ，表示触发器激活的时间是在执行除法事件前。（）
> 格式为：`AFTER` | `BEFORE` 触发事件 `ON` 表名。触发事件可以是`INSERT`、`DELETE`、`UPDATE`，也可以是`INSERT OR DELETE`、`DELETE AND INSERT`。

  1. 在第 96 题的背景下，REFERENCING 指出引用的变量，如果触发事件是 UPDATE 操作，并且有 FOR EACH ROW 子句，则可以引用的变量有 OLD 和 NEW ，分别表示修改之前的元组和修改之后的元组。若没有 FOR EACH ROW 子句，则可以引用的变量有 OLD TABLE 和 NEW TABLE ，分别表示表中原来的内容和表中变化后的部分。（）

  2. 在第 96 题的背景下， BEGIN 和 END 之间的内容是动作体。

  3. 在 96 题的背景下， FOR EACH ROW 定义了触发器的类型，指明动作体执行的频率。该语句的含义是对于 UPDATE 执行了多少行，则触发器执行多少次。（）

FOR EACH STATEMENT 是语句级触发器。 FOR EACH ROW 是行级触发器。语句级触发器是执行了触发事件的语句后执行一次动作体。行级触发器则是触发事件执行影响了多少行，则执行多少次动作体。

  1. 在第 96 题的背景下， WHEN () 的内容是触发条件，当触发条件为真时，动作体才执行，否则动作体不执行。如果省略 WHEN 触发条件，则在触发事件引发的触发器激活后就立即执行动作体。

  2. 删除触发器的 SQL 语句格式是： DROP TRIGGER 触发器名 ON 表名 。

# 关系代数

  1. 关系代数的运算对象是关系，运算结果不是关系。
> 关系代数的运算结果还是关系。
  1. 关系代数分为传统的集合运算和专门的关系运算，则专门的关系运算有哪些？ {.quiz .multi}
    - 选择。 {.correct}
    - 笛卡尔积。
    - 连接。 {.correct}
    - 除。 {.correct}
    - 投影。
> 传统的集合运算有并，差，交，笛卡尔积。
  1. 关系的差运算，对于两个关系 R 和 S，R-S 和 S-R 一定是等价的。
> 关系的差运算有顺序，R-S与S-R一般不等价。
  1. 关系代数中，表示不等于的运算符是！=。
> 表示不等于的运算符只能是\<>。
  1. 用关系代数查询信息安全专业的全体学生。
> $$\sigma_{Smajor='信息安全'}(Student)$$
> 常见的在选择运算的条件表达式的运算符有>(大于),>=(大于等于),<(小于),<=(小于等于),=(等于),\<>(不等于),$\lnot$(非),$\land$(与),$\lor$(或)。
  1. 查询 2001 年后（包含 2001 年）出生的学生。 
> $$\sigma_{Sbirthdate>=2001-1-1}(Student)$$
  1. 查询学生的学号和主修专业。 
> $$\pi_{Sno,Smajor}(Student)$$
  1. 检索选修课程号为 C1 的学生学号与成绩。 
> $$\pi_{Sno,Grade}(\sigma_{Cno='C1'}(SC))$$
  1. 检索选修课程名为 ' 数据库原理 ' 的学生学号与姓名。 
> $$\pi_{Sno,Sname}(\sigma_{Cname='数据库原理'}(SC \bowtie Student \bowtie Course))$$
  1. 检索所学课程包含 ZHANG 老师所讲授的所有课程的学生学号。 
> $$\pi_{Cno,Sno}(SC) \div \pi_{Cno}(\sigma_{Teacher='ZHANG'}(Course))$$
  1. 检索至少选修了两门课程的学生学号。 
> $$\pi_{Sno}(\sigma_{1=4 \wedge 2!=5}(SC \bowtie SC))$$
> 这里的数字代表列号。1=4表示同一个学生，2=5表示同一门课程，2!=5表示与当前课程不同的课程。已知2=5的元组一定成立，如果2!=5成立，那么选修的课程数就至少有2个了。
  1. 检索学号为 S3 的学生选修的课程号与成绩。 
> $$\pi_{Cno,Grade}(\sigma_{Sno='S3'}(SC))$$
  1. 检索选修课程号为 C2 或 C4 的学生姓名与专业。 
> $$\pi_{Sname,Smajor}(\sigma_{Cno='C2' \vee Cno='C4'}(Student \bowtie SC))$$
  1. 检索学号为 S1 的学生所学课程的课程名与任课教师名。 
> $$\pi_{Cname,Teacher}(\sigma_{Sno='S1'}(SC \bowtie Course))$$
  1. 检索选修了全部课程的学生学号。 
> $$\pi_{Sno,Cno}(SC) \div \pi_{Cno}(Course)$$

# SQL 语言

本博文涉及的表有学生表 Student、课程表 Course、学生选课表 SC。
Student(Sno‾\underline{Sno},Sname,Ssex,Sbirthdate,Smajor)
学生 (学号‾\underline{学号}, 姓名，性别，出生日期，专业)

Course(Cno‾\underline{Cno},Cname,Ccredit,Teacher)
课程 (课程号‾,课程名,学分,授课老师\underline{课程号},课程名,学分,授课老师)

SC(Sno‾\underline{Sno},Cno,Grade,Semester)
学生选课 (学号‾\underline{学号}, 课程号，成绩，选修学期)

  1. 查询学号为 20180003 的学生的详细情况。 
SELECT * FROM Student 
WHERE Sno='20180003';
  1. 查询所有姓刘的学生的姓名、学号和性别。 
SELECT Sname, Sno, Ssex FROM Student 
WHERE Sname LIKE '刘%';
  1. 如果课程号长度为 5 个字符，查询课程号为 81 开头，最后一位是 6 的课程名称和课程号。 
SELECT Cname, Cno FROM Course 
WHERE Cno LIKE '81__6';
  1. 查询所有不姓刘的学生的姓名、学号和性别。 
SELECT Sname, Sno, Ssex FROM Student
WHERE Sname NOT LIKE '刘%';
  1. 查询 DB_Design 课程的课程号和学分。 
SELECT Cno, Ccredit FROM Course
WHERE Cname = 'DB\_Design' ESCAPE'\';
  1. 将学生 20180001 的出生日期改成 2001 年 3 月 18 日。 
UPDATE Student
SET Sbirthdate='2001-03-18'
WHERE Sno='20180001';
  1. 将 2020 年第 1 学期选修 81002 课程的所有学生的成绩减少 5 分。 
UPDATE Student
SET Grade=Grade-5
WHERE Semester='20201' AND Cno='81002';
  1. 将计算机科学与技术专业学生的成绩置零。 
UPDATE SC
SET Grade=0
WHERE Sno IN (
SELECT Sno From Student
WHERE Smajor='计算机科学与技术'
);
  1. 建立信息管理与信息系统专业学生的视图，并要求进行插入、修改和删除操作时，仍需保证该视图只有信息管理与信息系统专业的学生。 
CREATE VIEW xinxiguanli
AS
SELECT * FROM Student
WHERE Smajor='信息管理与信息系统'
WITH CHECK OPTION;
  1. 按照前文信息要求，创建 SC 表，说明 Sno, Cno, Grade 属性不允许取空值。 
CREATE TABLE SC
(
	Sno CHAR(8) NOT NULL,
	Cno CHAR(5) NOT NULL,
	Grade SMALLINT NOT NULL,
	Semester CHAR(5),
	PRIMARY KEY(Sno, Cno)
)
  1. 建立学院表 School，要求学院名称 SHname 列取值唯一，且要求为变长的字符，长度最大为 40，学院编号 SHno 列为主码，要求为 8 个字符长度，另外还有属性 SHfounddate 表示建立日期。 
CREATE TABLE School
(
	SHno CHAR(8) PRIMARY KEY,
	SHname VARCHAR(40) UNIQUE,
	SHfounddate DATE
)
  1. 按照前文信息要求，创建 Student 表，且要求性别属性为 6 字符长度且只允许取 ' 男' 或 ' 女'，学号属性为 8 个字符长度且为主码，姓名属性为 20 个字符长度且不为空，专业属性为变长的字符串，最长为 20。 
CREATE TABLE Student
(
	Sno CHAR(8) PRIMARY KEY,
	Sname CHAR(20) NOT NULL,
	Ssex CHAR(6) CHECK(Ssex In('男','女')),
	Sbirthdate DATE,
	Smajor VARCHAR(20)
)
  1. 检索学生 S1 所选修全部课程的课程号与成绩，并按照成绩逆序排序。 
SELECT Cno, Grade FROM SC
WHERE Sno = (
	SELECT Sno FROM Student
	WHERE Sname='S1'
)
ORDER BY Grade DESC。
  1. 检索同时选修了至少两门课程的学生学号与姓名。 
SELECT Sno, Sname FROM Student
WHERE Sno IN (
	SELECT Sno FROM SC 
 	GROUP BY SNO
   	HAVING COUNT(*)>=2
);
  1. 检索至少选修 LIU 老师所授课程中一门课程的女学生姓名、课程名及成绩。 
SELECT a.Sname, c.Cname, b.Grade FROM Student a, SC b, Course c
WHERE a.Sno=b.Sno AND b.Cno=c.Cno AND a.Ssex='女' AND b.Teacher LIKE 'LIU%';
  1. 检索 ZHANG 老师所授课程的每门课程的平均成绩。 
SELECT AVG(SC.Grade) FROM SC, Course
WHERE SC.Cno=Course.Cno AND Course.Teacher LIKE 'ZHANG%'
GROUP BY SC.Cno;
  1. 检索所有女学生的学号和姓名，并按学号逆序排序。 
SELECT Sno, Sname FROM Student
WHERE Ssex='女'
ORDER BY Sno DESC;
  1. 检索同时选修了至少三门课程的学生学号与姓名。 
SELECT Student.Sno, Student.Sname FROM Student, SC
WHERE Student.Sno=SC.Sno
GROUP BY Student.Sno
HAVING COUNT(SC.Cno)>=3;

# 数据库设计

  1. 数据库设计的基本步骤有 需求分析阶段、概念结构设计阶段、逻辑结构设计阶段、物理结构设计阶段、数据库实施阶段、数据库运行和维护阶段。

  2. 数据字典是进行详细的 数据收集 和 数据分析 之后所获得的主要成果。它是关于数据库中对数据的 描述，即元数据，而不是数据本身。

  3. 数据字典在需求分析阶段被建立，在数据库设计过程中不断修改、充实和完善。

  4. 数据字典通常包括哪些部分？ {.quiz .multi}
    - 数据项。 {.correct}
    - 数据结构。 {.correct}
    - 数据流。 {.correct}
    - 数据存储。 {.correct}
    - 处理过程。

  5. 数据项是数据的最小组成单位，若干个数据项能组成一个数据结构。

# 操作系统理论

# 概述

  1. 什么是操作系统？（答案如下）
> 1. 操作系统管理计算机资源，主要对处理机、存储器、文件、作业、设备进行管理。
> 2. 操作系统为用户提供了使用计算机硬件资源的接口。常见的接口提供方式有图形接口、命令行接口、程序接口。
> 3. 操作系统被用作扩充机器。裸机是没有软件的计算机，而操作系统可以将裸机改造为功能更强、更方便的机器。

  1. 操作系统有核心态（管态）和用户态（目态）两种运行状态，对应将程序划分为内核程序和应用程序

  2. 操作系统需要通过内核的时钟管理，向用户提供标准的系统时间。其次，通过时钟中断的管理，可以实现进程的切换。

内核是计算机上配置的底层软件。主要包括时钟管理、中断机制、一系列原语、系统控制的数据结构以及如何管理这些数据结构。
原语是操作系统底层的一些可被调用的公用小程序，用于完成一个规定的操作。

  1. 原语位于操作系统底层，最接近硬件。

  2. 原语可以被中断。

> 原语程序的运行具有原子性，操作只能一气呵成。
  1. 原语调用频繁，运行时间短。

中断是 CPU 对系统发生的事件做出的一个反应，使 CPU 暂停正在执行的程序，保留现场，并执行相应的处理程序。
中断机制的引入，初衷是为了提升多道程序运行环境中 CPU 的利用率，后面发展为操作系统各项操作的基础。
中断具有优先级。

  1. 低级中断不能被高级中断打断。

  2. 外中断通常与 CPU 执行的指令无关。异常又被称为内中断，主要是由 CPU 执行的指令产生的事件，比如地址越界，算术溢出等，是 CPU 执行指令本身时出现的问题。

  3. 异常是一种特殊的中断。

  4. 对中断的处理方式有顺序处理和嵌套处理。

> 嵌套处理主要是由于中断优先级的存在，高级的中断打断低级中断。

常见中断处理流程是：关中断（CPU 相应中断，从此刻开始不会响应更高级的中断的请求）→\rightarrow 保存断点（将原来程序的断点，即程序计数器 PC 保存起来）→\rightarrow 引入中断服务程序 →\rightarrow 保护现场（保存相关寄存器的内容）→\rightarrow 开中断（允许响应更高级的中断）→\rightarrow 执行中断服务程序 →\rightarrow 关中断（准备恢复现场，此刻开始不再响应更高级中断的请求）→\rightarrow 恢复现场 →\rightarrow 开中断、中断返回。

  1. 操作系统的内核类型有大内核（强内核、单内核）和微内核。

  2. 微内核操作系统因为需要频繁在用户态和核心态之间切换，所以有一定的性能损失。

大内核将操作系统的功能作为一个紧密结合的整体放到内核中。
微内核则是将操作系统分为多个小的、定义良好的功能模块。基本的功能保留到内核，即微内核，而其他的功能模块运行在用户态。

# 计算机网络理论

# 计算机网络体系结构

互联网相较互连网，范围更大。互连网是多个互连网互连而来的。
互联网由核心部分与边缘部分组成，边缘部分主要是大部分的主机构成，核心部分主要是大部分的路由器组成。
ISP 又称互联网服务提供者，比如中国电信，中国移动，中国联通。

  1. 互联网两个重要特点是连通性和共享

  2. 计算机之间的通信，本质上是进程和进程之间的通信。

  3. 主机与主机之间的通信方式有两种，分别是客户 - 服务器方式（C/S）和对等方式（P2P）

  4. 电路交换，表现在链路上的一个重要特点是通话全部时间内链路始终被两端用户占用

分组转发采用的是存储转发技术。
1GB = 1024MB = 2102^{10}MB = 2202^{20}KB = 2302^{30} B。（存储 - 字节视角）
1Gb = 10310^3 Mb = 10610^6 Kb = 10910^9 b。（网络 - 比特视角）

  1. 分组转发有哪四大优点？{.quiz .multi}
    - 方便
    - 高效 {.correct}
    - 迅速 {.correct}
    - 可靠 {.correct}
    - 灵活

  2. 计算机网络有哪些性能指标？ {.quiz .multi}
    - 速率 {.correct}
    - 带宽 {.correct}
    - 吞吐量 {.correct}
    - 时延 {.correct}
    - 往返时间 RTT

> 还有利用率、时延带宽积这两个指标。
> 时延又有分为发送时延、传播时延、排队时延、处理时延。
> 带宽是某个信道，单位时间内最大通过数据量，和速率一样单位是bit/s。吞吐量是指单位时间内通过某个网络的实际数据量，更强调实际，单位是bit。
> 时延带宽积正如其名，是传播时延与带宽的乘积，反映的是某条链路最大的比特容量。往返时间RTT是指发送方发送信息开始，到收到对方确认信息所花的时间。

OSI 和 TCP/IP 模型主要有五层：应用层、传输层、网络层、数据链路层、物理层。当然还有一些辅助的层：表示层、会话层。这两个暂时不是学习重点。

  1. 应用层为应用程序提供数据传输服务，数据单位是报文。

  2. 传输层为进程提供端到端的数据传输服务，数据单位是报文段。

  3. 网络层主要为主机提供数据传输服务，数据单位是数据包（packet—— 分组交换的数据单元）。

  4. 数据链路层为同一链路的主机提供数据传输服务，数据单位是帧。

物理层主要负责在物理介质上传输数据比特流。

  1. 为什么计算机网络要分层？（答案如下）
> 1. 各层可以相互独立，上下层只需要知道对方的接口即可，无需知道内部实现。
> 2. 灵活性好，某层要修改内部实现时，无需更改接口。
> 3. 易于实现和维护，整个系统被划分为多个独立的子系统。
> 4. 方便标准化，各层可以通过协议说明各自的功能和服务。
> 5. 分层使得更具扩展性。
  1. 如果数据帧长度为 1Kb，发送速率是 200bit/s，求发送时延。（答案如下）
> 发送时延 = 数据帧长度（bit） / 发送速率（bit / s）。因此答案为5s。
  1. 传播时延随着信道的长度增大而增大。
> 传播时延 = 信道长度（m） / 光速（m/s）。
  1. 信道利用率增加，则该信道的时延降低。
> 时延应该更高，公式反映为：当前时延D = 空闲时延D0 / （1-利用率U）。空闲时延D0一般是不变的。

# 计算机系统组成理论

# 概论

  1. 冯诺依曼体系结构三大思想为？{.quiz .multi}
    - 计算机硬件系统由运算器、存储器、控制器、输入设备、输出设备 5 大部件组成。{.correct}
    - “存储程序”：指令和数据以同等地位存储在存储器中。{.correct}
    - 指令和数据均用二进制表示。{.correct}
    - 以输入设备和输出设备为中心。

“存储程序” 的概念是指将指令事先输入计算机的主存，然后取程序在主存的首地址来执行程序的第一条指令，按程序规定的顺序执行其他指令，直到程序结束。

这揭示了计算机的工作过程：1）把程序和数据存入主存。2）把主存的源程序转换为可执行文件。3）从可执行文件的首地址开始逐条执行指令。

计算机系统结构层次从高到低分为：应用软件级、高级语言级、汇编语言级、操作系统级、机器语言级、硬件逻辑级。

  1. 编译是将源程序翻译为可执行的目标程序，也就是汇编语言文件。
> 目标程序文件是二进制的机器语言文件。
> 编译包含了汇编过程。
  1. 回顾一下，java 虚拟机 jvm 的作用是什么？
答案

java 程序并不一步到位编译为目标程序，而是先编译成中间文件字节码，即.class 文件，然后再用解释的方式一条一条执行。而 JVM 的作用就是作为一个中介将字节码逐条解释为目标代码，然后执行。

  1. 描述一下指令的执行过程和程序的执行过程。
答案

指令的执行过程：
取指：到 PC 取指令的地址，然后在主存中取出指令内容，最终送入指令寄存器 IR。
分析指令：控制器根据 IR 译码后送出控制信号。
执行指令：控制器根据控制信号在主存取出操作数，在运算器完成指令。

程序的执行过程：
程序的第一条指令在 PC 中被取出，经过分析和执行后，通过第一条指令的地址计算出下一条指令的地址，用新得到的指令地址继续读出第二条指令并执行，直到程序结束。

计算机主要四大性能指标：机器字长、数据通路带宽、主存容量、运算速度。运算速度有吞吐量、响应时间、时钟周期、主频、CPI 等指标。

  1. 数据通路带宽是指数据总线一次所能串行传送信息的位数。
> 带宽是衡量并行传送信息的能力指标。
  1. 主存容量可以用字数×\times 字长（如 512K ×\times 16 位）来表示。

吞吐量是指系统单位时间内处理请求或指令的数量。
相应时间是指用户向系统发送一个请求，到计算机对该请求做出相应并获得结果的时间。

  1. CPU 最小的时间单位是时钟周期，又称为节拍脉冲。

  2. 什么是 CPI？

答案

英文全名叫 Clock cycle Per Instruction，即执行一条指令所需的时钟周期数。

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

RunfarAI 微信支付

微信支付

RunfarAI alipay

alipay

RunfarAI paypal

paypal