25届国网计算机考试知识难点及习题整理（持续更新）

国网报名链接https://zhaopin.sgcc.com.cn/sgcchr/static/home.html

恭祝报名的同学全部上岸！！！

同时需要原文件的在评论区私信我哦，我无偿发个每一个小朋友.

算法、数据结构

1、堆排序

时间复杂度：O(nlogn)

空间复杂度：O(1)

堆排序：完全二叉树，但不是排序二叉树

第一个非叶子结点：n/2-1

最大堆：父≥子

最小堆：父≤子

算法(升序)

• 建堆：将无序数组调整为最大堆
• 排序：每次将堆顶元素与末尾元素交换，将堆的规模减一，调整剩余元素为最大堆。重复该过程直到只剩一个元素

原地排序算法

2、树的表示方法

树的表示法包括直观表示法、凹入表示法、嵌套集合表示法、广义表表示法。

• 直观表示法

  • 形式：图形化，节点用圈或方块，边连节点体现父子关系，根在上，子在下分层排列。
  • 理解：层次结构清晰，易看出分支与节点关系，如家族树展示辈分。
  • 场景：教学、文档说明。

• 凹入表示法

  • 形式：文本缩进体现层次，根顶格，子节点按层右缩。
  • 理解：看缩进量判层次与父子关系，同缩进为同层。如文件目录展示。
  • 场景：文本描述，如文件结构、代码说明。

• 嵌套集合表示法

  • 形式：节点对应集合，根集合含子集合，体现嵌套包含关系。
  • 理解：嵌套深度即树层次，内集对应节点是外集的子节点，如生物分类。
  • 场景：理论分析、数学建模。

• 广义表表示法

  • 形式：用括号逗号描述，根在前，括号括子树，逗号分子树。
  • 理解：括号嵌套反映层次，逗号分同层子节点，如 A(B(D, E), C)。
  • 场景：程序设计、数据结构处理。

3、广义表

例题：

注意：深度为1的广义表是线性表

4、数组指针和指针数组的区别

1. 定义和概念

• 数组指针：它本质上是一个指针，这个指针指向一个数组。也就是说，数组指针保存的是数组的首地址，通过这个指针可以访问整个数组。定义时，通常使用括号来明确指针和数组的关系，例如 int (*p)[n]，其中 p 是一个指向包含 n 个 int 类型元素的数组的指针。
• 指针数组：它本质上是一个数组，数组中的每个元素都是一个指针。这些指针可以指向不同的内存地址，例如 int *p[n]，这里 p 是一个包含 n 个 int 类型指针的数组。

2. 内存布局

• 数组指针：指针本身占用一定的内存空间（通常是 4 字节或 8 字节，取决于系统是 32 位还是 64 位），它指向一个连续的数组内存块。
• 指针数组：数组本身占用 n 个指针大小的内存空间，数组中的每个指针可以指向不同的内存位置，这些位置可能是分散的。

3. 使用场景

• 数组指针：常用于二维数组的传参，方便对二维数组进行操作。
• 指针数组：常用于处理多个字符串或需要动态管理多个指针的场景。

代码示例

#include <stdio.h>// 数组指针示例
void array_pointer_example() {int arr[3] = {1, 2, 3};// 定义一个数组指针，指向包含 3 个 int 类型元素的数组int (*p)[3] = &arr;// 通过数组指针访问数组元素for (int i = 0; i < 3; i++) {printf("array_pointer_example: arr[%d] = %d\n", i, (*p)[i]);}
}// 指针数组示例
void pointer_array_example() {int a = 10, b = 20, c = 30;// 定义一个指针数组，包含 3 个 int 类型的指针int *p[3] = {&a, &b, &c};// 通过指针数组访问元素for (int i = 0; i < 3; i++) {printf("pointer_array_example: p[%d] = %d\n", i, *p[i]);}
}// 二维数组和数组指针结合示例
void two_dimensional_array_example() {int arr[2][3] = {{1, 2, 3}, {4, 5, 6}};// 定义一个数组指针，指向包含 3 个 int 类型元素的数组int (*p)[3] = arr;// 通过数组指针访问二维数组元素for (int i = 0; i < 2; i++) {for (int j = 0; j < 3; j++) {printf("two_dimensional_array_example: arr[%d][%d] = %d\n", i, j, *(*(p + i) + j));}}
}int main() {array_pointer_example();printf("\n");pointer_array_example();printf("\n");two_dimensional_array_example();return 0;
}

代码解释

• array_pointer_example 函数：定义了一个包含 3 个元素的数组 arr，然后定义了一个数组指针 p 指向这个数组。通过 (*p)[i] 访问数组元素。
• pointer_array_example 函数：定义了 3 个整型变量 a、b、c，然后定义了一个指针数组 p，数组中的每个元素分别指向这 3 个变量。通过 *p[i] 访问指针所指向的元素。
• two_dimensional_array_example 函数：定义了一个二维数组 arr，然后定义了一个数组指针 p 指向二维数组的第一行。通过 *(*(p + i) + j) 访问二维数组的元素。

输出结果

array_pointer_example: arr[0] = 1
array_pointer_example: arr[1] = 2
array_pointer_example: arr[2] = 3pointer_array_example: p[0] = 10
pointer_array_example: p[1] = 20
pointer_array_example: p[2] = 30two_dimensional_array_example: arr[0][0] = 1
two_dimensional_array_example: arr[0][1] = 2
two_dimensional_array_example: arr[0][2] = 3
two_dimensional_array_example: arr[1][0] = 4
two_dimensional_array_example: arr[1][1] = 5
two_dimensional_array_example: arr[1][2] = 6

例题：

5、常见递归算法的时间复杂度

线性递归：计算n的阶乘

def factorial(n):if n == 0 or n == 1:return 1else:return n * factorial(n - 1)

• 复杂度分析：该递归函数每次递归调用将问题规模减小 1，总共需要进行n次递归调用，每次递归调用的时间复杂度为O(1)，因此总的时间复杂度为 O(n)。

二分递归：斐波那契数列

def fibonacci(n):if n == 0 or n == 1:return nelse:return fibonacci(n - 1) + fibonacci(n - 2)

• 复杂度分析：可以使用递归树法分析。该递归函数的递归树是一棵二叉树，树的高度为n，每个节点的时间开销为O(1)。递归树中节点的总数近似为2的n次方，因此时间复杂度为 O(2的n次方)。

分治递归：归并排序

def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return result

• 复杂度分析：归并排序将问题规模为n的数组分成两个规模为n/2的子数组，所以时间复杂度为 O(nlogn)。

计算机原理

1、IEEE802

• IEEE802.1：可以被认为是一个总的协议概论，它定义了一系列的标准和协议，涵盖了局域网和广域网中的网络管理和控制方面的功能，包括网络拓扑、网络互联、桥接、虚拟局域网（VLAN）等方面的规范，为其他 802 系列协议提供了总体的框架和基础。
• IEEE802.2：即逻辑链路控制层（LLC）协议，用于在局域网通信中提供逻辑链路控制，负责在数据链路层中实现可靠的数据传输、流量控制和差错控制等功能，确保数据在发送方和接收方之间的可靠性和有序性，将网络层的协议数据单元封装成数据帧，并进行相应的处理，以便在物理层和介质访问控制层上进行传输。
• IEEE802.3：定义了有线以太网的物理层和数据链路层的介质访问控制（MAC），是构建有线局域网的基础，应用范围广泛。该协议规定了以太网的传输介质、信号编码方式、数据传输速率、帧格式等内容，还定义了使用载波监听多路访问 / 冲突检测（CSMA/CD）的 LAN 访问方法，使得多个设备能够共享同一物理介质进行数据传输，并解决数据传输过程中的冲突问题。
• IEEE802.4：是令牌总线（Token Bus）协议，是一种较早的局域网技术。在这种协议中，网络中的计算机通过捕获令牌来在共享总线上发送数据，只有拥有令牌的节点才能发送数据，从而避免了数据冲突，确保了网络中数据传输的有序性。令牌沿着逻辑总线依次传递，每个节点都有平等的机会获得令牌并发送数据，适用于一些对数据传输的确定性和实时性要求较高的场景。

EEE802标准定义了网卡如何访问传输介质(如光缆、双绞线、无线等)，以及如何在传输介质上传输数据的方法，还定义了传输信息的网络设备之间连接建立，维护和拆除的途径。遵循IEEE802标准的产品包括网卡、桥接器、路由器以及其他一些用来建立局域网络的组件IEEE802.3中包括CSMA/CD，IEEE802.4中包括令牌总线网，IEEE802.5中包括令牌环网。

例题：

2、直接映像

在计算机领域，“直接映像”（Direct Mapping）通常指的是在高速缓存（Cache）中的一种地址映射方式，用于建立主存地址和高速缓存地址之间的对应关系。

例：

直接映象的地址转换速度快，但块的冲突概率较高。在大容量高速Cache系统中使用直接映象方式，即可以发挥Cache的高速度，又可以减少块的冲突概率。

3、CRC校验

CRC（Cyclic Redundancy Check）即循环冗余校验，是一种数据传输检错技术，用于在数字通信中识别数据传输过程中是否出现错误，通过在数据发送端生成一个循环冗余校验码，附加在原始数据后面一起发送，接收端通过对收到的数据进行同样的计算，来判断数据是否正确。

以下是其具体方法和解题示例：

1. CRC 校验的基本方法
   • 确定生成多项式：生成多项式是一个二进制数，用表示，它决定了 CRC 校验的规则。例如，常见的生成多项式，其对应的二进制数为（最高次幂的系数为，其余幂次的系数根据多项式确定，这里的系数为） 。
   • 扩展原始数据：假设原始数据为，在原始数据后面添加个，为生成多项式的最高次幂。例如，原始数据，生成多项式（），则扩展后的数据为。
   • 进行模除法：用扩展后的原始数据除以生成多项式对应的二进制数，进行模除法运算（不借位的二进制除法）。得到的余数就是 CRC 校验码，其位数为。例如，对除以进行模除法，得到余数，这就是 CRC 校验码。
   • 发送数据：将原始数据后面附上计算得到的 CRC 校验码，形成最终发送的数据。上述例子中，最终发送的数据就是。
   • 接收端校验：接收端收到数据后，用同样的生成多项式对其进行模除法。如果余数为，则认为数据在传输过程中没有出错；如果余数不为，则表示数据可能出现了错误。
2. 解题方法

例题：

根据CRC校验的计算方法，本题中生成多项式为4次多项式，因此在信息串1101011011后面补4个0得到11010110110000，然后用11010110110000除以生成多项式表示的除数10011（也可以使用模二除法：相同为0，相异为1），可得余数为1110。发送端发送信息串时，会在信息串后加上余数1110以进行差错检测，因此CRC校验码为1110。

4、固件

同一项功能，既可以用硬件实现，处理速度和实现成本可能高一些；也可以用软件实现，会降低硬件成本但运行速度可能要慢一些。通常人们把原来用软件实现的一项功能改为用硬件来实现，则称这一硬件为固件。

例题：

5、寄存器

例题：

CPU中保存当前正在执行的指令的寄存器为指令寄存器IR，保存下一条指令地址的寄存器为程序计数器PC，用于存放存储器中数据和指令地址的寄存器是地址寄存器，存数据和指令的寄存器是数据寄存器。

6、计算机中的CPI是什么？

每条指令执行的时钟周期数（Clock cycle Per Instruction）

• 定义
  • CPI 表示执行一条指令所需的平均时钟周期数。时钟周期是计算机中最基本的时间单位，计算机的各种操作都在时钟信号的控制下按顺序进行。CPI 是衡量计算机 CPU 性能的一个重要指标，它反映了 CPU 执行指令的效率。
• 计算方式
  • CPI 的计算公式为：CPI = 执行程序所花费的时钟周期数 / 程序中的指令数。例如，一个程序执行时总共花费了 1000 个时钟周期，程序中包含 200 条指令，那么该程序执行过程中的 CPI = 1000 / 200 = 5，即平均每条指令需要 5 个时钟周期来执行。
• 影响因素
  • 指令类型：不同类型的指令复杂度不同，执行所需的时钟周期数也不同。例如，简单的算术逻辑指令（如加法、减法）可能只需要 1 - 2 个时钟周期，而复杂的浮点运算指令、内存访问指令可能需要多个时钟周期。
  • CPU 架构：先进的 CPU 架构通常会采用流水线技术、超标量技术等，这些技术可以提高指令的并行执行程度，从而降低 CPI。例如，流水线技术可以将一条指令的执行过程分解为多个阶段，不同指令的不同阶段可以同时进行，使得在理想情况下每个时钟周期都能完成一条指令的执行，从而使 CPI 接近 1。

例题：

7、CPU中各个部件的作用

部件名称	作用简述
运算器	执行算术运算（如加、减、乘、除）和逻辑运算（如与、或、非），处理数据
控制器	指挥和协调计算机各部件工作，控制指令的执行顺序
寄存器	暂时存放参与运算的数据和中间结果，加快 CPU 的运算速度
高速缓冲存储器（Cache）	存储 CPU 近期可能会频繁访问的数据和指令，减少 CPU 等待数据从内存传输的时间

8、冯・诺伊曼体系结构

冯・诺伊曼体系结构（Von Neumann architecture）也被称为普林斯顿结构，是现代计算机的基础架构，由美籍匈牙利数学家冯・诺伊曼在 1945 年提出。以下从设计理念、基本组成、工作原理、优缺点几个方面详细介绍：

设计理念

• 存储程序：将程序和数据以二进制形式存储在计算机的存储器中。这意味着程序可以像数据一样被处理和修改，使得计算机可以根据不同的程序完成各种不同的任务，极大地提高了计算机的通用性和灵活性。
• 程序控制：计算机按照程序中指令的顺序依次执行，自动完成数据的处理。CPU 从存储器中取出指令，分析指令的功能，然后根据指令的要求对数据进行相应的操作。

基本组成

• 运算器：负责对数据进行算术运算（如加、减、乘、除）和逻辑运算（如与、或、非）。它是计算机进行数据处理的核心部件，能够快速地完成各种复杂的计算任务。
• 控制器：指挥和协调计算机各部件的工作，控制指令的执行顺序。它从存储器中取出指令，对指令进行译码，然后根据指令的要求向运算器、存储器、输入输出设备等发出控制信号，使它们协同工作。
• 存储器：用于存储程序和数据。它可以分为主存储器（如内存）和辅助存储器（如硬盘、光盘等）。主存储器速度快，但容量相对较小；辅助存储器容量大，但速度较慢。
• 输入设备：将外部的数据和程序输入到计算机中，如键盘、鼠标、扫描仪等。输入设备把各种形式的信息转换为计算机能够识别的二进制代码，以便计算机进行处理。
• 输出设备：将计算机处理的结果以人们能够理解的形式输出，如显示器、打印机、音箱等。输出设备把计算机内部的二进制代码转换为各种形式的信息，如文字、图像、声音等。

工作原理

1. 取指令：控制器从存储器中取出一条指令，并将其存放到指令寄存器中。
2. 分析指令：控制器对指令寄存器中的指令进行译码，确定指令的操作类型和操作对象。
3. 执行指令：根据指令的要求，控制器向运算器、存储器、输入输出设备等发出控制信号，完成指令规定的操作。例如，如果是一条加法指令，运算器会从存储器或寄存器中取出操作数，进行加法运算，并将结果存回存储器或寄存器。
4. 重复上述步骤：控制器不断地重复取指令、分析指令、执行指令的过程，直到程序执行完毕。

优点

• 通用性强：由于程序和数据都存储在存储器中，计算机可以通过改变程序来完成不同的任务，适用于各种领域的应用。
• 结构简单：采用集中控制的方式，各个部件之间的关系清晰，便于设计、制造和维护。
• 易于扩展：可以通过增加存储器容量、提高运算器速度、添加输入输出设备等方式来扩展计算机的性能。

缺点

• 冯・诺伊曼瓶颈：由于程序和数据都存储在同一存储器中，并且通过同一总线进行传输，导致 CPU 与存储器之间的数据传输成为系统性能的瓶颈。当 CPU 处理速度较快时，存储器的数据传输速度可能无法满足 CPU 的需求，从而影响计算机的整体性能。
• 安全性问题：程序和数据存储在一起，容易受到病毒、恶意软件等的攻击，导致程序和数据的安全性受到威胁。

计算机网络

1、计算机输出的信号

数字信号指自变量是离散的、因变量也是离散的信号，这种信号的自变量用整数表示，因变量用有限数字中的一个数字来表示。

在计算机中，数字信号的大小常用有限位的二进制数表示，所以计算机输出的信号是二进制数据信号。

2、以太网

以太网帧是以太网中数据传输的基本单元，其标准帧结构包含多个字段，不同字段有着不同的作用，下面为你详细介绍：

1. 前导码（Preamble）： 由 7 个字节的 10101010（共 56 位）组成，它的作用是使接收端的物理层能够与发送端的信号同步。通过识别前导码的特定模式，接收端可以调整其内部的时钟，准确地采样接收到的信号，为后续正确接收数据帧做好准备。
2. 帧开始定界符（SFD，Start Frame Delimiter）： 长度为 1 个字节，其值固定为 10101011。它紧跟在前导码之后，标志着一个以太网帧的真正开始，用于区分前导码和实际的数据帧内容。
3. 目的 MAC 地址（Destination MAC Address）： 长度为 6 个字节，用于标识帧的接收方设备的物理地址。网络中的每个设备都有一个唯一的 MAC 地址，发送方在发送数据帧时，会将接收方的 MAC 地址填入该字段，以便数据帧能够准确地送达目标设备。
4. 源 MAC 地址（Source MAC Address）： 同样为 6 个字节，记录了发送该帧的设备的物理地址。接收方可以通过这个字段知道数据帧的来源，以便进行响应或记录等操作。
5. 类型 / 长度字段（Type/Length Field）： 长度为 2 个字节。当该字段的值大于等于 1536（十六进制为 0x0600）时，它表示上层协议的类型，例如 0x0800 表示 IP 协议，0x0806 表示地址解析协议（ARP）等，用于告诉接收方应该将帧中的数据部分交给哪个上层协议进行处理；当该字段的值小于 1500（十六进制为 0x05DC）时，它表示帧的数据字段的长度。
6. 数据字段（Data Field）： 长度在 46 到 1500 字节之间。它承载了要传输的实际数据，这些数据通常是由上层协议（如 IP、ARP 等）封装好的内容。如果上层数据长度小于 46 字节，以太网会自动填充一些字节，以保证帧的最小长度要求，确保数据在传输过程中的可靠性。
7. 帧校验序列（FCS，Frame Check Sequence）： 长度为 4 个字节，通常使用循环冗余校验（CRC）算法计算得出。它基于帧中的其他字段（除前导码和帧开始定界符外）生成一个校验值，接收方在接收到帧后，会对除前导码和帧开始定界符外的字段重新计算 CRC 值，并与接收到的 FCS 字段进行比较。如果两者相等，则认为帧在传输过程中没有发生错误；否则，认为帧出现了错误，将其丢弃。

例题：

解答一：以太网要求帧的最小长度是64字节，源地址、目标地址、类型和校验及域占用了18个字节，那么一个有20字节数据的以太网帧的长度就是18+20=38字节，还需要填充64-38=26字节。

解答二：

3、Telnet 协议

Telnet 协议是 TCP/IP 协议族中的一员，它允许用户通过本地计算机（客户端）登录到远程计算机（服务器）上，像直接操作远程计算机一样执行命令、管理系统等，实现远程控制和管理。

例题：

PSH位表示带有PUSH标志的数据，接收方在收到数据后应该立即请求将数据递交给应用程序，而不是将它缓存起来。

选项 A：SYN

• SYN（Synchronize Sequence Numbers）是 TCP 建立连接时使用的标志位。当客户端要与服务器建立连接时，会发送一个带有 SYN 标志位的 TCP 包给服务器，用于同步双方的初始序列号，它主要用于 TCP 连接的三次握手过程，和使服务器尽快响应命令并无直接关系。

选项 B：URG

• URG（Urgent Pointer field significant）表示紧急指针有效。当 URG 标志位置 1 时，表明紧急指针字段有效，意味着该数据包中包含紧急数据。紧急数据需要尽快处理，但它并不是用于让服务器尽快响应普通用户命令的机制。

选项 C：PSH

• PSH（Push function）是 “推送” 标志位。当发送方将 PSH 标志位置 1 时，它会通知 TCP 协议栈立即将缓冲区中的数据发送出去，而不需要等到缓冲区满。在 Telnet 协议这种交互式应用场景中，用户发送的命令需要及时被服务器处理，设置 PSH 标志位可以使客户端尽快将命令数据发送到服务器，让服务器尽快响应命令。所以该选项正确。

选项 D：RST

• RST（Reset the connection）用于重置连接。当接收方收到一个带有 RST 标志位的 TCP 包时，会立即中断当前的 TCP 连接，它通常用于异常情况的处理，如检测到非法的数据包或要强制关闭连接等，和使服务器尽快响应命令没有关联。

4、ISO 的 OSI/RM 模型

ISO 的 OSI/RM 模型将网络通信分七层：

1. 物理层：处理物理介质上比特流传输，规定接口、信号等特性，设备有集线器、中继器。
2. 数据链路层：把比特流封装成帧，差错检测，负责介质访问，含 LLC 与 MAC 子层，设备有交换机、网桥。
3. 网络层：实现数据帧源到目的传输，处理路由、拥塞和互联，用 IP 地址，设备是路由器。
4. 传输层（端到端）：提供端到端可靠通信，处理分段、重组等，协议有 TCP、UDP。
5. 会话层：建立、管理和终止应用会话，有同步和恢复机制。
6. 表示层：处理数据表示和转换，如加密、压缩，定义数据表示标准。
7. 应用层（端到端）：为用户应用程序提供服务，包含 HTTP、SMTP 等协议。

5、TCP/IP协议四层模型

网络接口层（Network Interface Layer）

• 功能：该层也被称为数据链路层与物理层的结合。它负责将 IP 数据包封装成适合在物理网络上传输的帧，并通过物理介质（如网线、光纤、无线信号等）发送出去；同时，接收来自物理网络的帧，并将其解封装为 IP 数据包。这一层处理了与各种物理网络技术的接口细节，包括不同网络类型（如以太网、Wi-Fi、令牌环网等）的特性和要求。
• 协议与技术：包含了多种协议和技术，如以太网协议（Ethernet），它定义了局域网中数据传输的帧格式、介质访问控制方法等；Wi-Fi 协议（如 802.11 系列标准），用于无线局域网的数据传输；还有 PPP（Point-to-Point Protocol）协议，常用于广域网中拨号连接和点对点链路的数据传输。

网际层（Internet Layer）

• 功能：核心功能是实现不同网络之间的互联和数据包的路由。它负责将数据包从源主机通过网络传输到目标主机，无论这些主机位于何种类型的网络中。网际层处理 IP 地址的分配、路由选择、数据包的分片与重组等任务，确保数据包能够跨越多个网络到达正确的目的地。
• 主要协议
  • IP（Internet Protocol）：是网际层的基础协议，定义了 IP 数据包的格式和传输规则。IPv4 是目前广泛使用的版本，但由于地址空间有限，IPv6 正在逐步推广。
  • ICMP（Internet Control Message Protocol）：用于在 IP 主机、路由器之间传递控制消息和错误报告，例如 Ping 命令就是基于 ICMP 协议实现的，用于测试网络连通性。
  • ARP（Address Resolution Protocol）：用于将 IP 地址解析为对应的物理地址（MAC 地址），使得数据包能够在局域网中正确传输。
  • RARP（Reverse Address Resolution Protocol）：与 ARP 相反，它将物理地址解析为 IP 地址，常用于无盘工作站获取自己的 IP 地址。

传输层（Transport Layer）

• 功能：为应用程序提供端到端的通信服务，确保数据在源端和目标端之间的可靠传输或高效传输。它负责处理数据的分段、重组、流量控制、差错检测和恢复等问题，使得应用程序可以忽略底层网络的复杂性，专注于自身的业务逻辑。
• 主要协议
  • TCP（Transmission Control Protocol）：是一种面向连接的、可靠的传输协议。它通过三次握手建立连接，在传输过程中提供可靠的数据传输，使用确认机制、重传机制和滑动窗口协议来保证数据的完整性和顺序性。TCP 适用于对数据准确性要求较高的应用，如文件传输（FTP）、电子邮件（SMTP）、网页浏览（HTTP）等。
  • UDP（User Datagram Protocol）：是一种无连接的、不可靠的传输协议。它不建立连接，也不保证数据的可靠传输，但具有较低的开销和较高的传输效率。UDP 适用于对实时性要求较高、对少量数据丢失不太敏感的应用，如实时音视频流、在线游戏等。

应用层（Application Layer）

• 功能：直接为用户的应用程序提供网络服务，是用户与网络交互的接口。应用层协议定义了应用程序之间通信的规则和格式，使得不同的应用程序可以在网络上进行数据交换和协同工作。
• 常见协议
  • HTTP（Hypertext Transfer Protocol）：用于在 Web 浏览器和 Web 服务器之间传输超文本（如 HTML 页面），是互联网上应用最为广泛的协议之一。
  • FTP（File Transfer Protocol）：用于在不同主机之间进行文件的上传和下载，提供了可靠的文件传输服务。
  • SMTP（Simple Mail Transfer Protocol）：用于发送电子邮件，将邮件从发件人的邮件客户端传输到收件人的邮件服务器。
  • POP3（Post Office Protocol 3）和 IMAP（Internet Message Access Protocol）：用于接收电子邮件，POP3 将邮件从邮件服务器下载到本地客户端，IMAP 则允许客户端在服务器上管理邮件。
  • DNS（Domain Name System）：用于将域名解析为对应的 IP 地址，使得用户可以使用易于记忆的域名来访问网络资源

6、计算机网络发展的四个阶段

第一阶段：面向终端的计算机网络（20 世纪 50 年代末 - 60 年代中期）

• 基本概念：这是计算机网络的雏形，以一台大型计算机为中心，通过通信线路连接多个远程终端。终端本身不具备数据处理能力，主要用于输入数据和显示计算结果，所有的数据处理任务都由中心计算机完成。
• 典型应用：在商业、科学研究等领域，用户通过终端设备远程访问大型计算机上的资源，进行数据处理和计算。例如，航空公司的订票系统，多个售票终端通过通信线路连接到中心计算机，实现机票的预订和查询功能。
• 技术特点：采用电路交换技术，通信线路是专用的，在通信过程中需要建立一条物理连接，通信结束后再拆除连接。这种方式适合于实时性要求较高的通信，但线路利用率较低。

第二阶段：计算机 - 计算机网络（20 世纪 60 年代中期 - 70 年代末）

• 基本概念：将多台计算机通过通信线路连接起来，实现计算机之间的直接通信和资源共享。此时的网络不再以单个计算机为中心，而是多个计算机平等地连接在一起，形成了分布式的网络结构。
• 典型代表：ARPANET（阿帕网）是这一阶段的典型代表，它是美国国防部高级研究计划局资助开发的一个计算机网络，最初用于军事和科研目的。ARPANET 采用分组交换技术，将数据分成多个小的数据包进行传输，大大提高了网络的可靠性和线路利用率。
• 技术特点：分组交换技术成为主流，它将数据分成若干个分组，每个分组独立地在网络中传输，通过路由选择算法选择最佳路径到达目的地。这种方式可以动态地分配网络资源，提高了网络的效率和灵活性。同时，网络中开始出现网络协议，用于规范计算机之间的通信规则。

第三阶段：开放式标准化网络（20 世纪 70 年代末 - 90 年代）

• 基本概念：随着计算机网络的发展，不同厂商生产的计算机和网络设备之间的兼容性问题日益突出。为了解决这个问题，国际标准化组织（ISO）制定了开放系统互连（OSI）参考模型，为网络通信提供了一个统一的标准框架。各个厂商按照这个标准来开发网络设备和软件，使得不同厂商的产品可以相互兼容和互操作。
• 典型标准：除了 OSI 参考模型外，TCP/IP 协议族也在这一阶段逐渐成为事实上的工业标准。TCP/IP 协议具有简洁、高效、实用等特点，被广泛应用于各种网络环境中，成为互联网的核心协议。
• 技术特点：网络标准化是这一阶段的主要特点，各种网络协议和标准的制定使得网络的发展更加规范化和有序化。同时，局域网技术得到了快速发展，如以太网、令牌环网等，为企业和机构内部的计算机联网提供了便利。

第四阶段：高速互联网络阶段（20 世纪 90 年代至今）

• 基本概念：随着计算机技术、通信技术和半导体技术的飞速发展，网络的传输速度和处理能力得到了极大的提高。高速宽带网络、无线网络、移动互联网等技术不断涌现，互联网的应用范围也从最初的科研和军事领域扩展到了社会生活的各个方面，如电子商务、远程教育、电子政务、社交媒体等。
• 典型技术：光纤通信技术的广泛应用使得网络的传输带宽得到了极大的提升；无线局域网（WLAN）和移动通信技术（如 3G、4G、5G）的发展使得人们可以随时随地接入网络；云计算、大数据、物联网等新兴技术与网络技术的融合，为网络的发展带来了新的机遇和挑战。
• 技术特点：高速、宽带、移动、智能是这一阶段网络的主要特点。网络的发展不仅改变了人们的生活和工作方式，也对社会经济的发展产生了深远的影响。

7、NSFNET网络特点

NSFNET（National Science Foundation Network，美国国家科学基金会网络）是美国国家科学基金会（NSF）在 20 世纪 80 年代建立的计算机网络，在互联网发展历程中扮演了重要角色，具体介绍如下：

1. 背景与目的：20 世纪 80 年代，美国的科研机构和高校对计算机网络的需求日益增长，为了促进科研和教育领域的计算机资源共享与合作，NSF 决定建立一个连接各超级计算机中心的网络，这就是 NSFNET 的起源。其主要目的是为科研人员和高校师生提供高速的网络连接，以便他们能够更方便地访问超级计算机资源和进行学术交流。
2. 网络架构：NSFNET 采用了层次化的网络架构。它以主干网为核心，连接了分布在美国各地的多个超级计算机中心。主干网的传输速率相对较高，最初的主干网速率为 56Kbps，后来逐步升级到 T1（1.544Mbps）和 T3（44.736Mbps）线路。在主干网之下，通过地区网络连接各个高校和科研机构的局域网，形成了一个庞大的网络体系。
3. 发展历程：NSFNET 于 1985 年开始建设，1986 年正式投入使用。随着网络技术的发展和用户需求的增加，NSFNET 不断进行升级和扩展。它不仅提高了网络的传输速率，还增加了网络的覆盖范围和连接的机构数量。到了 20 世纪 90 年代，NSFNET 已经成为美国乃至全球互联网的重要组成部分。
4. 对互联网的影响：NSFNET 对互联网的发展产生了深远的影响。它打破了阿帕网（ARPANET）主要服务于军事和科研的局限，将网络扩展到了更广泛的科研和教育领域，推动了互联网在学术和教育界的普及。同时，NSFNET 的成功运营和发展也为互联网的商业化奠定了基础。1995 年，NSFNET 停止运营，其主干网部分被商业化的网络服务提供商所取代，但它在互联网发展史上的地位不可磨灭，为现代互联网的形成和发展做出了重要贡献。

操作系统

1、对操作系统的管理

操作系统的管理主要涉及对计算机系统中各种资源的有效管理和协调，以提高系统的性能和效率，方便用户使用计算机。主要包括以下几个方面的管理：

管理类型	主要内容
进程管理	进程的创建与撤销；进程调度；进程同步与互斥；进程通信
内存管理	内存分配与回收；地址转换；内存保护；虚拟内存管理
设备管理	设备分配与回收；设备驱动程序管理；设备独立性；虚拟设备技术
文件管理	文件的组织与存储；文件目录管理；文件的共享与保护；文件系统的挂载与卸载
用户接口管理	命令接口；图形用户界面（GUI）；程序接口

1、 进程管理

• 进程的创建与撤销：操作系统负责创建新的进程，为其分配必要的系统资源（如内存、CPU 时间等），当进程完成任务或出现异常时，及时撤销该进程并回收其占用的资源。
• 进程调度：根据一定的调度算法，从就绪队列中选择一个进程，将 CPU 资源分配给它，使进程能够在 CPU 上执行。常见的调度算法有先来先服务（FCFS）、短作业优先（SJF）、时间片轮转（RR）等。
• 进程同步与互斥：多个进程在并发执行时，可能会竞争共享资源，为了避免出现数据不一致等问题，操作系统需要提供机制来实现进程之间的同步与互斥。例如，使用信号量、互斥锁等方法来控制对共享资源的访问。
• 进程通信：不同进程之间可能需要进行数据交换和信息传递，操作系统提供了多种进程通信机制，如管道、消息队列、共享内存、套接字等。

2、内存管理

• 内存分配与回收：操作系统要为进程分配所需的内存空间，当进程不再使用内存时，及时回收这些内存，以便分配给其他进程。常见的内存分配算法有首次适应算法、最佳适应算法、最坏适应算法等。
• 地址转换：将进程的逻辑地址转换为物理地址，使进程能够正确地访问内存中的数据。这通常通过页表、段表等机制来实现。
• 内存保护：防止不同进程之间相互干扰，确保每个进程只能访问自己被分配的内存空间。操作系统通过设置访问权限等方式来实现内存保护。
• 虚拟内存管理：当物理内存不足时，操作系统使用虚拟内存技术，将部分暂时不用的程序和数据从物理内存交换到磁盘上的交换空间（如虚拟内存文件），从而为当前需要运行的进程提供足够的内存空间。

3、设备管理

• 设备分配与回收：根据进程的请求，为其分配合适的设备，并在设备使用完毕后及时回收。操作系统会考虑设备的可用性、优先级等因素进行合理分配。
• 设备驱动程序管理：设备驱动程序是操作系统与硬件设备之间的接口，操作系统负责加载、卸载和管理设备驱动程序，确保设备能够正常工作。
• 设备独立性：使应用程序与具体的物理设备无关，应用程序只需要使用逻辑设备名来请求设备，操作系统会将逻辑设备名映射到具体的物理设备上。
• 虚拟设备技术：通过软件手段将一台物理设备虚拟成多台逻辑设备，提高设备的利用率。例如，SPOOLing 技术可以将一台打印机虚拟成多个逻辑打印机，多个进程可以同时使用该打印机。

4、文件管理

• 文件的组织与存储：操作系统需要确定文件在磁盘等存储设备上的组织方式，如采用连续分配、链接分配、索引分配等方式，以便高效地存储和访问文件。
• 文件目录管理：文件目录用于管理文件的名称、属性、存储位置等信息，操作系统提供了文件目录的创建、删除、查找等操作，方便用户对文件进行管理。
• 文件的共享与保护：允许不同用户或进程共享文件，同时要保证文件的安全性，防止文件被非法访问和修改。操作系统通过设置文件的访问权限（如读、写、执行权限）来实现文件的保护。
• 文件系统的挂载与卸载：将存储设备上的文件系统挂载到操作系统的目录树中，使用户可以访问其中的文件；当不再需要使用该文件系统时，将其卸载。

5、用户接口管理

• 命令接口：用户可以通过在命令行中输入命令来操作系统，如在 Windows 的命令提示符或 Linux 的终端中输入各种命令，操作系统会对这些命令进行解释和执行。
• 图形用户界面（GUI）：以图形化的方式为用户提供操作界面，用户可以通过鼠标点击、拖动等操作来完成各种任务，如打开文件、启动程序等。
• 程序接口：为开发人员提供了一组系统调用，开发人员可以在程序中使用这些系统调用来请求操作系统提供的服务，如创建文件、分配内存等。

2、死锁

死锁是指多个进程在执行过程中，因争夺资源而造成的一种互相等待的僵局，若无外力作用，这些进程都将无法向前推进。

1. 死锁产生的原因
   • 资源竞争：系统中的资源有限，当多个进程同时竞争这些资源时，可能会导致死锁。例如，进程 A 和进程 B 都需要使用资源 X 和资源 Y，进程 A 已经占用了资源 X，进程 B 已经占用了资源 Y，此时进程 A 等待进程 B 释放资源 Y，进程 B 等待进程 A 释放资源 X，从而形成死锁。
   • 进程推进顺序不当：进程在运行过程中，对资源的申请和释放顺序不合理，也可能导致死锁。即使系统资源充足，但如果进程的推进顺序不恰当，也会出现相互等待的情况。
2. 死锁的四个必要条件
   • 互斥条件：资源在某一时刻只能被一个进程所使用，即资源具有排他性。例如，打印机在打印一份文件时，其他进程不能同时使用该打印机。
   • 请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但又对自己已获得的资源保持不放。
   • 不可剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行剥夺，只能由该进程自己释放。
   • 循环等待条件：存在一个进程资源的循环链，链中每个进程已获得的资源同时被下一个进程所请求。在这个循环链中，每个进程都在等待下一个进程释放资源，从而形成死锁。
3. 死锁的特点
   • 相互等待：死锁中的进程都处于等待状态，它们相互等待对方释放资源，导致所有进程都无法继续执行。
   • 资源独占：涉及死锁的资源被进程独占，其他进程无法使用这些资源，造成资源的浪费。
   • 永久性：如果没有外部干预，死锁状态将一直持续下去，进程无法自行解除死锁。
4. 规避死锁的方法
   • 资源预分配策略：在进程开始运行之前，为其分配所需的全部资源，这样进程在运行过程中就不会再请求其他资源，从而避免了资源竞争和死锁的发生。但这种方法可能会导致资源利用率降低，因为有些资源可能在进程运行的大部分时间内处于闲置状态。
   • 资源有序分配法：对系统中的资源进行编号，规定进程必须按照资源编号的顺序请求资源。这样可以破坏循环等待条件，从而避免死锁的发生。例如，资源编号为 1、2、3，进程在请求资源时，只能先请求资源 1，再请求资源 2，最后请求资源 3。
   • 银行家算法：这是一种避免死锁的经典算法，它通过模拟银行系统的贷款策略来管理资源的分配。系统在每次分配资源之前，先检查此次分配是否会导致系统进入不安全状态，如果会，则拒绝分配；如果不会，则进行分配。银行家算法需要记录系统中资源的总量、每个进程已分配的资源量和还需要的资源量等信息。
   • 剥夺资源法：当发现有进程可能导致死锁时，剥夺该进程已占用的部分或全部资源，分配给其他需要这些资源的进程。这种方法可以解除死锁，但可能会对被剥夺资源的进程造成影响，需要谨慎使用。

例题：

考虑一下极端情况，每个进程已经分配到了2台磁带机，那么，其中任何一个进程只要再分配到1台磁带机即可满足它的最大需求，该进程总能运行下去直到结束，然后将磁带机归还给系统再次分配给其它进程使用。所以，系统中只要满足2x+1=11这个条件即可以认为系统不会死锁，解得x=5。

3、设备管理

操作系统设备管理的功能主要有：输入输出、设备分配和缓冲管理。其中，缓冲管理是管理好各种类型的缓冲区，协调各类设备的工作速度提高系统的使用效率。它通过单缓冲区、双缓冲区或缓冲池等机制来实现。

例题1：

例题2：

下列功能中，不属于设备管理功能的是()。 A.实现虚拟存储器 B.实现文件共享 C.外围设备的启动 D.实现虚拟设备

选项A：虚拟存储器是存储管理的范畴。

选项B：文件共享主要是文件系统管理的功能。

选项C：设备管理的主要任务之一就是对各种外围设备进行管理和控制，其中包括外围设备的启动操作。

选项D：虚拟设备是设备管理的一项重要功能。

4、存储管理

例题：

单用户连续管理是把内存直接分配给一个进程连续的使用；可变分区管理是把内存划分成大小不等的区域，再把这样不同大小的区域分配给不同的进程，每一个进程只占用一个连续的区域。

5、计算机总线

计算机总线是计算机各功能部件之间进行信息传输的公共通道，就像城市中的交通干线，负责连接计算机系统的各个组成部分，实现它们之间的数据、地址和控制信息的传输。以下从总线的分类、组成、工作原理、性能指标等方面进行详细介绍：

1、总线的分类

• 按功能和传输信息的种类分类
  • 数据总线（Data Bus，DB）：用于在 CPU、内存和 I/O 设备之间传输数据。数据总线是双向的，既可以将数据从内存或输入设备传送到 CPU，也可以将 CPU 处理后的数据传送到内存或输出设备。数据总线的位数（宽度）决定了一次能传输的数据量，例如 32 位数据总线一次能传输 32 位（4 字节）的数据。
  • 地址总线（Address Bus，AB）：用于指定数据或指令在内存中的存储地址。地址总线是单向的，由 CPU 发出地址信息，用于选择要访问的内存单元或 I/O 端口。地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如 20 位地址总线可寻址的内存空间为 = 1MB。
  • 控制总线（Control Bus，CB）：用于传输控制信号和时序信号，协调计算机各部件的工作。控制总线的信号包括读写控制信号、中断请求信号、时钟信号等。控制总线的信号有的是单向的，有的是双向的。
• 按连接部件分类
  • 内部总线：指芯片内部连接各元件的总线，如 CPU 内部寄存器之间、运算器与控制器之间的总线。内部总线的速度通常非常快，以满足芯片内部高速数据传输的需求。
  • 系统总线：连接计算机主机内部各大部件的总线，如 CPU、内存、主板上的各种扩展插槽之间的总线。常见的系统总线有 PCI 总线、PCI - Express 总线等。
  • 外部总线：也称为通信总线，用于连接计算机与外部设备，如 USB 总线、串口、并口等。外部总线主要用于实现计算机与外部设备之间的数据通信。

2、总线的组成

• 导线：是总线的物理载体，用于传输电信号。导线的材质、粗细、长度等因素会影响信号的传输质量。
• 接口电路：位于总线与各个部件之间，负责信号的转换、缓冲和驱动等功能。例如，CPU 通过接口电路与总线相连，将内部的信号转换为适合在总线上传输的信号。

3、总线的工作原理

• 总线仲裁：当多个设备同时请求使用总线时，需要进行总线仲裁，以确定哪个设备可以优先使用总线。常见的总线仲裁方式有集中式仲裁和分布式仲裁。集中式仲裁由一个仲裁器统一管理总线的使用权；分布式仲裁则由各个设备共同参与仲裁过程。
• 数据传输：获得总线使用权的设备将数据、地址和控制信号发送到总线上，其他设备通过总线接收这些信号。在数据传输过程中，需要遵循一定的时序规则，以确保数据的正确传输。

4、总线的性能指标

• 总线带宽：指单位时间内总线上可传输的数据量，通常以字节 / 秒（B/s）为单位。总线带宽与总线的时钟频率和数据总线的宽度有关，计算公式为：总线带宽 = 总线时钟频率 × 数据总线宽度 / 8。
• 总线时钟频率：指总线的工作频率，单位为赫兹（Hz）。时钟频率越高，总线在单位时间内传输数据的次数就越多，传输速度也就越快。
• 总线复用：指在同一总线上分时传输不同类型的信息，如地址和数据可以复用同一组总线。总线复用可以减少总线的数量，降低成本。

例题：

在计算机总线中，地址信息、数据信息和控制信息不能同时出现。（正确）

6、单道批处理系统

单道批处理系统是一种早期的操作系统类型，它将用户提交的作业（程序、数据和作业说明书的集合）成批地送入计算机，由操作系统按照一定的策略依次执行。在这个过程中，内存中始终只保持一道作业运行，直到该作业完成后才调入下一道作业。

工作流程

1. 作业收集：用户将需要处理的作业（通常包含程序、数据和作业说明书）提交给系统操作员，操作员将这些作业汇集到一起，形成一个作业批。
2. 作业装入：操作系统将作业批中的第一个作业装入内存，并为其分配所需的系统资源，如内存空间、CPU 时间等。
3. 作业执行：CPU 开始执行内存中的作业，直到该作业完成或因某种原因（如出错、等待外部设备）暂停。
4. 作业完成处理：作业完成后，操作系统回收该作业占用的系统资源，并输出作业的处理结果。
5. 调入下一个作业：重复步骤 2 - 4，依次处理作业批中的其他作业，直到所有作业都处理完毕。

特点

• 自动性：在作业处理过程中，系统能够自动地依次处理作业批中的各个作业，无需人工干预。一旦作业批被提交，系统会按照预定的顺序逐个执行作业，大大提高了作业处理的效率。
• 顺序性：作业是按照它们进入系统的先后顺序依次执行的，前一个作业执行完毕后，才会调入下一个作业。这种顺序执行的方式使得系统的管理和调度相对简单。
• 单道性：内存中始终只存在一道作业在运行，CPU 和其他系统资源在一段时间内只为这一道作业服务。这意味着在作业执行过程中，其他作业必须等待，直到当前作业完成。

局限性

• 资源利用率低：由于内存中只有一道作业运行，当该作业进行 I/O（输入 / 输出）操作时，CPU 会处于空闲状态，因为 I/O 操作的速度通常比 CPU 的处理速度慢得多。例如，当作业需要从磁盘读取大量数据时，CPU 只能等待数据读取完成，导致 CPU 的利用率不高。
• 作业周转时间长：作业必须依次执行，即使某个作业只需要很少的 CPU 时间，但如果前面有一个耗时很长的作业在执行，它也必须等待。这使得作业的平均周转时间（从作业提交到作业完成所经历的时间）较长，用户需要等待较长的时间才能得到处理结果。
• 系统吞吐量小：系统吞吐量是指单位时间内系统处理的作业数量。由于单道批处理系统一次只能处理一道作业，且 CPU 利用率低，导致系统在单位时间内能够处理的作业数量有限，系统吞吐量较小。

7、不同类型操作系统的主要发展阶段

手工操作阶段（20 世纪 40 - 50 年代中期）

• 优点：简单直接，用户对计算机操作有完全控制权。
• 缺点：计算机利用率极低，人工操作慢，大量时间 CPU 闲置。
• 特点：无操作系统，用户直接操控硬件，效率取决于人工操作速度。

单道批处理系统阶段（20 世纪 50 - 60 年代中期）

• 优点：实现作业自动过渡，减少人工干预，提高作业处理效率。
• 缺点：内存仅一道作业运行，I/O 时 CPU 空闲，资源利用率低。
• 特点：引入监督程序，成批处理作业，但单道执行。

多道批处理系统阶段（20 世纪 60 - 70 年代中期）

• 优点：多作业并发执行，提高 CPU 利用率和系统吞吐量。
• 缺点：缺乏交互性，作业周转时间长，资源管理复杂。
• 特点：多个作业同时驻留内存，由系统调度执行。

分时系统阶段（20 世纪 60 年代末至今）

• 优点：交互性强，多个用户可同时使用，响应及时。
• 缺点：对系统性能要求高，处理实时任务能力弱。
• 特点：将 CPU 时间分片，轮流为用户服务。

实时系统阶段（20 世纪 60 年代末至今）

• 优点：能及时响应外部事件，保证任务在规定时间完成。
• 缺点：开发和维护成本高，资源利用率相对较低。
• 特点：用于对时间敏感领域，分硬、软实时系统。

个人计算机操作系统阶段（20 世纪 70 年代末至今）

• 优点：界面友好，功能丰富，适合个人用户，操作简便。
• 缺点：安全性相对较弱，资源管理可能不够精细。
• 特点：面向个人，有图形界面和大量应用程序。

网络操作系统阶段（20 世纪 80 年代至今）

• 优点：支持网络通信和资源共享，具备网络管理功能。
• 缺点：网络故障影响大，安全管理难度高。
• 特点：管理网络资源，实现用户间资源共享与通信。

分布式操作系统阶段（20 世纪 90 年代至今）

• 优点：并行性高、容错性强，可统一使用多计算机资源。
• 缺点：系统设计和管理复杂，通信开销大。
• 特点：多计算机联网形成统一计算环境。

8、重定位

在多道程序环境下，程序和数据需要装入内存才能运行。然而，程序员在编写程序时，通常使用的是逻辑地址（相对地址），即程序中指令和数据的地址是相对于程序起始点的地址。而计算机内存管理使用的是物理地址（绝对地址），是内存中实际存储单元的地址。重定位就是将程序中的逻辑地址转换为物理地址的过程。

分类

• 静态重定位
  • 原理：静态重定位是在程序装入内存时，由装配程序一次性完成逻辑地址到物理地址的转换。转换过程依据程序装入内存的起始地址，将程序中所有的逻辑地址加上这个起始地址，从而得到对应的物理地址。一旦转换完成，在程序运行期间地址不再改变。
  • 优点：不需要硬件支持，实现简单，可在没有专门的地址转换机构的计算机系统中使用。
  • 缺点：程序装入内存后不能在内存中移动，因为移动后物理地址会发生变化，但静态重定位无法动态调整地址；而且多个程序难以共享内存中的同一程序副本。
  • 示例：假设一个程序的逻辑地址空间从 0 开始，长度为 1000。当该程序被装入到内存起始地址为 5000 的位置时，静态重定位会将程序中的逻辑地址 0 转换为物理地址 5000，逻辑地址 10 转换为物理地址 5010，以此类推。
• 动态重定位
  • 原理：动态重定位是在程序运行过程中，每当 CPU 访问内存时，由硬件地址转换机构（如基址寄存器）将逻辑地址转换为物理地址。基址寄存器中存放着程序在内存中的起始地址，当 CPU 访问逻辑地址时，将逻辑地址加上基址寄存器中的值，就得到了对应的物理地址。
  • 优点：程序在内存中可以动态移动，便于内存的动态分配和回收；可以实现多个程序共享内存中的同一程序副本，提高内存利用率。
  • 缺点：需要硬件支持，增加了计算机系统的成本和复杂性。
  • 示例：同样假设程序的逻辑地址空间从 0 开始，长度为 1000。程序装入内存时，基址寄存器被设置为程序在内存中的起始地址，如 6000。当 CPU 要访问逻辑地址 20 时，硬件地址转换机构会将 20 加上基址寄存器中的 6000，得到物理地址 6020 进行内存访问。

作用

• 提高内存利用率：通过重定位，多个程序可以共享内存空间，并且可以根据内存的使用情况动态分配和回收内存，从而提高内存的利用率。
• 支持程序的动态加载和链接：动态重定位使得程序可以在运行时动态地加载和链接其他模块，增加了程序的灵活性和可扩展性。
• 实现多道程序设计：重定位是实现多道程序设计的基础，它允许多个程序同时装入内存并并发执行，每个程序使用自己的逻辑地址空间，通过重定位转换为物理地址，互不干扰。

9、为什么引入磁盘之后导致现代OS具有并发性和共享性？

并发性方面

1. 进程切换与内存管理：磁盘作为外存设备，能够存储大量的程序和数据。当内存空间有限时，操作系统可以将暂时不运行的进程及其相关数据保存到磁盘上（如进程的上下文信息等），当需要运行该进程时，再从磁盘加载到内存中。这使得多个进程可以在内存中交替执行，实现进程的并发执行。
2. I/O 操作的异步性：磁盘的引入使得 I/O 操作可以异步进行。操作系统可以在进程发起磁盘 I/O 请求后，让该进程进入等待状态，同时调度其他进程运行。当磁盘 I/O 操作完成时，通过中断机制通知操作系统，相应的进程可以被唤醒并继续执行。这种异步的 I/O 处理方式使得 CPU 和磁盘可以并行工作，多个进程的 I/O 操作也可以重叠进行，进一步提高了系统的并发性。
3. 虚拟内存技术：磁盘是实现虚拟内存的基础。虚拟内存技术允许进程使用比实际物理内存更大的地址空间，通过将一部分不常用的内存页面交换到磁盘上，当需要访问这些页面时再从磁盘调回内存。这样，更多的进程可以同时被装入到虚拟内存中，使得系统中能够同时存在多个处于运行或就绪状态的进程，从而提高了系统的并发程度。

共享性方面

1. 文件共享：磁盘用于存储文件，多个用户或进程可以通过操作系统提供的文件系统共享磁盘上的文件。不同的进程可以同时读取或写入同一个文件（在一定的访问控制规则下），实现了文件级别的共享。
2. 数据共享：除了文件之外，磁盘上还可以存储各种类型的数据，如数据库数据等。多个进程可以通过访问磁盘上的共享数据来实现数据的共享和交互。
3. 设备共享：磁盘作为一种外部存储设备，操作系统可以对其进行管理，使得多个进程可以共享使用磁盘设备。操作系统通过设备驱动程序和 I/O 调度算法来协调多个进程对磁盘的访问请求，提高磁盘设备的利用率。

10、分段存储管理为什么利于程序的动态链接？

1. 逻辑独立性与模块化：分段存储管理将程序按照逻辑功能划分为多个段，如代码段、数据段、堆栈段等。每个段都有自己独立的含义和功能，这与程序的模块化设计思想相契合。在动态链接时，不同的模块（段）可以独立地进行链接操作。例如，一个大型软件系统由多个功能模块组成，每个模块可以被编译成一个独立的段。在链接阶段，只需要将这些段按照逻辑关系进行组合即可，使得链接过程更加清晰和易于管理，也方便对特定模块进行更新和维护，而不影响其他模块的链接。
2. 地址空间分离：每个段都有自己独立的地址空间，段内地址是连续的，段与段之间的地址空间相互独立。这种地址空间的分离特性使得在动态链接时，链接器可以很容易地确定各个段在内存中的位置和边界。例如，在链接一个库函数时，链接器可以根据段的信息将库函数的代码段准确地链接到主程序的合适位置，同时保证数据段和其他段的正确映射，避免地址冲突，提高了链接的准确性和可靠性。
3. 符号解析与重定位：分段存储管理便于符号解析和重定位操作。在动态链接过程中，程序中的符号（如函数名、变量名等）需要被解析并映射到正确的内存地址。由于每个段都有明确的逻辑意义，链接器可以根据段的信息快速找到符号所在的段，并进行相应的重定位操作。例如，当一个程序调用了另一个模块中的函数时，链接器可以根据段的信息确定该函数所在的段，然后在链接时将调用指令的地址重定位到正确的函数入口地址，使得程序能够正确地调用外部函数，实现动态链接的功能。
4. 按需加载与共享：分段存储管理支持按需加载，即只有当程序需要使用某个段时，才将该段加载到内存中。这对于动态链接非常有利，因为在动态链接时，可能只需要链接部分模块或段，而不是一次性加载整个程序。例如，对于一些不常用的功能模块，可以在需要时再进行动态链接和加载，减少了内存的占用。此外，多个程序可以共享相同的段（如共享库），通过分段存储管理，操作系统可以方便地管理这些共享段，确保不同程序对共享段的正确访问，同时也提高了内存的利用率，进一步促进了动态链接的实现。
5. 易于链接修改：当程序的某个部分发生变化时，由于分段存储管理的模块化特性，只需要对相应的段进行修改和重新链接即可。例如，如果一个模块的功能发生了更新，只需要重新编译该模块对应的段，然后在链接时将更新后的段与其他段重新链接，而不需要对整个程序进行重新编译和链接，大大提高了程序维护和更新的效率，也使得动态链接更加灵活和便捷。

11、多道程序设计的特性

间断性

• 原因：在多道程序环境下，内存中同时存在多个程序。当一个程序在运行过程中，可能会因为等待某些事件（如 I/O 操作完成）而暂停执行，此时操作系统会将 CPU 资源分配给其他就绪的程序。当等待的事件发生后，该程序才会有机会继续执行。
• 示例：一个计算密集型程序在执行过程中需要从磁盘读取数据，在发出磁盘 I/O 请求后，它会进入等待状态，CPU 转而执行其他程序。当磁盘数据读取完成后，该程序才会恢复执行。

共享性

• 资源共享：多道程序设计允许多个程序共享系统中的各种资源，包括硬件资源（如 CPU、内存、磁盘、打印机等）和软件资源（如系统程序、库函数等）。通过资源共享，可以提高资源的利用率，降低系统成本。
• 示例：多个程序可以同时使用内存空间，操作系统会合理地分配内存给不同的程序；多个程序也可以共享磁盘上的文件系统，减少了存储资源的浪费。

制约性

• 程序间制约：多道程序之间存在着相互制约的关系。这种制约关系可以分为直接制约和间接制约。直接制约通常是由于程序之间存在协作关系，一个程序的执行依赖于另一个程序的结果；间接制约则是由于多个程序竞争同一资源而产生的。
• 示例：在一个生产流水线上的模拟程序中，装配程序需要等待零件加工程序完成后才能继续执行，这是直接制约；多个程序同时竞争 CPU 资源，一个程序占用 CPU 时，其他程序就需要等待，这是间接制约。

宏观上并行、微观上串行

• 宏观并行：从宏观角度来看，多道程序在同时执行。多个程序都在系统中处于活动状态，它们的执行过程是重叠的，仿佛在同时进行。这提高了系统的整体处理能力，使得系统能够同时处理多个任务。
• 微观串行：从微观角度来看，在单 CPU 系统中，同一时刻 CPU 只能执行一个程序的指令。多个程序是轮流使用 CPU 的，它们的执行是串行的。操作系统通过合理的调度算法，在不同程序之间快速切换 CPU 的使用权，使得每个程序都能得到一定的执行时间。
• 示例：在一个多道程序系统中有程序 A、程序 B 和程序 C。宏观上，这三个程序都在同时运行；但微观上，CPU 可能先执行程序 A 的一部分指令，然后切换到程序 B 执行一段时间，再切换到程序 C，如此循环。

调度性

• 资源调度：在多道程序设计中，操作系统需要对各种资源进行调度，以确保多个程序能够合理地使用资源。主要的调度包括 CPU 调度、内存调度、I/O 调度等。通过调度，可以提高系统的性能和资源利用率。
• 示例：操作系统的 CPU 调度算法（如先来先服务、短作业优先、时间片轮转等）会根据程序的特点和系统的状态，选择合适的程序执行；内存调度会决定哪些程序可以进入内存，哪些程序需要换出到磁盘。

12、操作系统的设计方法

模块化设计方法

• 原理：将操作系统按照功能划分为多个相对独立的模块，每个模块完成特定的功能，模块之间通过规定的接口进行交互。这种设计方法使得系统结构清晰，易于理解、维护和扩展。
• 优点
  • 提高了系统的可维护性，当某个模块出现问题时，只需对该模块进行修改，不会影响其他模块。
  • 增强了系统的可扩展性，可以方便地添加新的模块来实现新的功能。
  • 便于团队开发，不同的开发人员可以负责不同的模块，提高开发效率。
• 缺点：模块间的接口设计较为困难，如果接口设计不合理，可能会导致模块间的耦合度增加，影响系统的性能和稳定性。
• 示例：在一个操作系统中，可以将进程管理、内存管理、文件管理等分别设计成独立的模块。进程管理模块负责进程的创建、调度和销毁；内存管理模块负责内存的分配和回收；文件管理模块负责文件的存储和访问。

分层式设计方法

• 原理：将操作系统按照功能的层次进行划分，每一层都建立在其下层的基础之上，并且只与相邻的上下层进行交互。下层为上层提供服务，上层通过调用下层的服务来实现更高级的功能。
• 优点
  • 降低了系统的复杂度，每层只需要关注本层的功能和与相邻层的接口，便于系统的设计和实现。
  • 提高了系统的可维护性和可扩展性，当需要修改或扩展某一层的功能时，只需要对该层进行操作，不会影响其他层。
  • 增强了系统的可靠性，由于层与层之间的独立性较强，一层出现问题不会轻易影响到其他层。
• 缺点：系统的效率可能会受到一定影响，因为每层之间的交互需要进行额外的处理，增加了系统的开销。
• 示例：典型的分层式操作系统可以分为硬件层、操作系统内核层、系统服务层和应用程序层。硬件层提供计算机的基本硬件资源；操作系统内核层负责管理硬件资源和提供基本的系统服务；系统服务层为应用程序提供更高级的服务；应用程序层则是用户直接使用的各种应用程序。

微内核设计方法

• 原理：将操作系统的核心功能（如进程管理、内存管理等）尽可能地精简，只保留最基本的功能作为微内核，而将其他大部分服务（如文件系统、设备驱动等）作为用户态的进程来实现。微内核通过消息传递机制与这些用户态进程进行通信。
• 优点
  • 提高了系统的可扩展性，由于大部分服务都是用户态进程，当需要添加新的服务时，只需添加新的用户态进程即可，不会影响微内核的稳定性。
  • 增强了系统的可靠性，微内核的代码量较小，出现错误的概率也相对较低，而且当某个用户态服务进程出现问题时，不会影响整个系统的运行。
  • 便于移植，由于微内核的功能比较简单，将其移植到不同的硬件平台上相对容易。
• 缺点：消息传递机制会带来一定的开销，可能会影响系统的性能；而且微内核与用户态服务进程之间的通信比较复杂，增加了系统的设计和实现难度。
• 示例：QNX、L4 等操作系统采用了微内核设计方法。在这些操作系统中，微内核只负责进程调度、线程通信等基本功能，而文件系统、网络服务等则以独立的用户态进程形式存在。

面向对象设计方法

• 原理：将操作系统中的各种实体（如进程、文件、设备等）抽象为对象，每个对象包含数据和操作这些数据的方法。对象之间通过消息传递进行交互，并且可以通过继承、封装和多态等机制来实现代码的复用和扩展。
• 优点
  • 提高了代码的可复用性，通过继承和多态机制，可以减少代码的重复编写。
  • 增强了系统的可维护性，由于对象的封装性，每个对象的内部实现细节对外部是隐藏的，当需要修改某个对象的功能时，不会影响其他对象。
  • 便于系统的扩展，通过创建新的对象和修改现有对象的方法，可以方便地实现系统的功能扩展。
• 缺点：面向对象的设计和实现需要一定的编程技巧和经验，如果设计不当，可能会导致系统的复杂度增加。
• 示例：在一些现代操作系统中，将进程抽象为进程对象，每个进程对象包含进程的状态、优先级、资源等信息，并且提供了创建、销毁、调度等操作方法。

数据库开发与设计

1、三级模式

数据库系统三级模式由外模式、模式和内模式构成，带来数据独立与安全等优点，以下用表格呈现：

模式类型	别称	定义	作用	数量
外模式	子模式、用户模式	用户可见可用的局部数据逻辑结构描述	提供个性化界面，屏蔽复杂性，方便安全使用	多个
模式	逻辑模式、概念模式	全体数据的逻辑结构和特征描述	综合考虑用户需求，定义数据整体逻辑	一个
内模式	存储模式	数据物理结构和存储方式描述	设计管理存储结构，提升存储效率性能	一个

优点：实现逻辑与物理数据独立性，便于数据共享和保障数据安全。

2、数据库关系理论

关系数据理论，也被称为关系数据库理论。是数据库领域的重要基础理论，主要用于设计和优化关系型数据库，确保数据库中数据的完整性、一致性和减少数据冗余。

2.1、函数依赖

• 定义：设 是一个属性集 上的关系模式， 和 是 的子集。若对于 的任意一个可能的关系 ， 中不可能存在两个元组在 上的属性值相等， 而在 上的属性值不等， 则称 “ 函数确定 ” 或 “ 函数依赖于 ”，记作 。
• 示例：在学生信息表（学号，姓名，班级）中，学号可以唯一确定姓名和班级，即存在函数依赖：学号 → 姓名，学号 → 班级。

2.2、范式

范式是符合某一种级别的关系模式的集合，是衡量关系模式好坏的标准。满足不同程度要求的为不同范式，从低到高主要有第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、巴斯 - 科德范式（BCNF）等。

• 第一范式（1NF）
  • 定义：如果一个关系模式 的所有属性都是不可分的基本数据项，则 。
  • 示例：若一个学生选课表中，“课程” 属性包含多门课程，且未分开存储，就不满足 1NF；将 “课程” 拆分为多个单独的课程记录，使每个属性都是不可再分的，就满足了 1NF。
• 第二范式（2NF）
  • 定义：若关系模式 ，并且每一个非主属性都完全函数依赖于任何一个候选码，则 。
  • 示例：在订单表（订单号，产品编号，产品名称，数量）中，候选码是（订单号，产品编号），若产品名称只依赖于产品编号，而不依赖于整个候选码，那么该表不满足 2NF；将订单表拆分为订单表（订单号，产品编号，数量）和产品表（产品编号，产品名称），就满足了 2NF。
• 第三范式（3NF）
  • 定义：设关系模式 ，若 中不存在这样的码 、属性组 及非主属性 （）， 使得 ， 成立，，则称 。即每一个非主属性既不部分依赖于码也不传递依赖于码。
  • 示例：在员工信息表（员工编号，部门编号，部门名称）中，员工编号 → 部门编号，部门编号 → 部门名称，存在传递依赖，不满足 3NF；将其拆分为员工表（员工编号，部门编号）和部门表（部门编号，部门名称），就满足了 3NF。
• 巴斯 - 科德范式（BCNF）
  • 定义：设关系模式 ，若 且 时 必含有码，则 。也就是说，每一个决定因素都包含码。
  • 示例：在关系模式（仓库名，管理员，物品名，数量）中，若存在函数依赖（仓库名，物品名）→ 数量，（仓库名，管理员）→ 物品名，管理员 → 仓库名，该关系模式不满足 BCNF；进行适当的分解后可满足 BCNF。

3、数据库三级模式和二级映像

数据库的三级模式结构是指数据库系统由外模式、模式和内模式三级构成，这是数据库系统内部的体系结构，以下为你展开介绍：

1. 外模式：也称为子模式或用户模式，是数据库用户（包括应用程序员和最终用户）能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。外模式通常是模式的子集，一个数据库可以有多个外模式。不同的用户可以有不同的外模式，通过外模式可以为用户提供数据的个性化视图，同时也可以对用户的数据访问进行一定的限制，提高数据的安全性。

   例如，银行系统中，普通客户的外模式可能只能看到自己账户的余额、交易记录等信息，而银行管理员的外模式则可以看到所有客户的详细信息以及系统的管理数据。

2. 模式：也称为逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。它处于三级模式的中间层，既不涉及数据的物理存储细节和硬件环境，也与具体的应用程序、开发工具及高级程序设计语言无关。模式定义了数据的基本结构，包括数据的类型、长度、关系等，还定义了数据之间的联系以及数据的完整性和安全性约束条件等。

   例如，在一个学生管理数据库中，模式会定义学生表包含哪些字段（如学号、姓名、年龄等），以及这些字段的数据类型，同时还会定义学生表与其他表（如课程表、成绩表）之间的关系。

3. 内模式：也称为存储模式，是数据在数据库系统内部的表示，即对数据的物理结构和存储方式的描述。内模式定义了数据在存储介质上的组织方式，如数据文件的存储结构、索引的组织方式、数据的存储位置等。一个数据库只有一个内模式，它是数据库的物理存储结构，是数据库管理系统进行数据管理的基础。

   例如，数据库管理系统可能会根据数据的使用频率和访问模式，将某些经常访问的数据存储在高速存储设备上，而将不常访问的数据存储在低速存储设备上，这些存储策略的实现都体现在内模式中。

在数据库的三级模式结构中，存在二级映像，分别是**外模式 / 模式映像和模式 / 内模式映像，它们在保证数据库数据的逻辑独立性和物理独立性**方面起着关键作用，以下是详细介绍：

1. 外模式 / 模式映像： 外模式 / 模式映像是定义在外模式和模式之间的一种对应关系。对于每一个外模式，数据库系统都有一个外模式 / 模式映像，它确定了外模式与模式之间的对应关系，该映像通常包含在外模式的描述中。当模式发生改变（如**增加新的关系、新的属性、改变属性的数据类型**等）时，数据库管理员可以通过修改外模式 / 模式映像，使外模式保持不变。由于应用程序是依据外模式编写的，外模式不变，应用程序就不需要修改，这保证了数据与程序的逻辑独立性。

   例如，在一个企业的员工信息管理数据库中，模式中员工表增加了一个新的字段 “员工照片”，此时通过修改外模式 / 模式映像，让一些不需要使用 “员工照片” 字段的应用程序所对应的外模式不包含这个新字段，这些应用程序就无需修改仍可正常运行。

2. 模式 / 内模式映像：模式 / 内模式映像是定义在模式和内模式之间的对应关系，一个数据库只有一个模式 / 内模式映像，它定义了数据全局逻辑结构与存储结构之间的对应关系，该映像定义通常包含在模式描述中。当数据库的存储结构（内模式）发生改变（如**存储设备的更换、存储方式的改变、数据存储位置的调整**等）时，数据库管理员可以通过修改模式 / 内模式映像，使模式保持不变。因为应用程序是依据模式编写的，模式不变，应用程序也不需要修改，这保证了数据与程序的物理独立性。

   例如，原来数据库的数据存储在普通硬盘上，现在更换为固态硬盘以提高读写性能，此时通过修改模式 / 内模式映像，调整数据的存储路径和方式等，使得上层的模式感知不到这种物理存储的变化，应用程序也就不需要进行修改。

4、数据库操作类型

操作类型	含义	常见语句及示例
数据定义DDL	用于定义数据库的结构和对象，包括创建、修改和删除数据库对象，如数据库、表、视图、索引等	- CREATE：创建新的数据库对象，如 CREATE TABLE students (id INT, name VARCHAR(50)); - ALTER：修改已存在的数据库对象的结构，如 ALTER TABLE students ADD COLUMN age INT; - DROP：删除数据库对象，如 DROP TABLE students;
数据操纵DML	用于对数据库中的数据进行插入、更新和删除操作，以实现数据的增删改功能	- INSERT：向表中插入新的数据记录，如 INSERT INTO students (id, name, age) VALUES (1, 'Alice', 20); - UPDATE：修改表中已存在的数据记录，如 UPDATE students SET age = 21 WHERE id = 1; - DELETE：删除表中的数据记录，如 DELETE FROM students WHERE id = 1;
数据查询	用于从数据库中检索满足特定条件的数据，是数据库操作中最常用的操作之一	SELECT：如 SELECT * FROM students; 查询 students 表所有记录；SELECT name, age FROM students WHERE age > 20; 查询 students 表中 age 大于 20 的记录的 name 和 age 字段
数据控制DCL	用于控制用户对数据库的访问权限，确保数据库的安全性和完整性	- GRANT：授予用户对数据库对象的特定权限，如 GRANT SELECT, INSERT ON students TO user1; - REVOKE：撤销用户已有的权限，如 REVOKE INSERT ON students FROM user1;

注意：

数据查询（Data Query）

• 英文缩写：一般在常见语境中，没有一个特定统一被广泛认知的类似 “DDL”“DML” 的严格缩写，但有时也会简单用 “DQ” 来表示数据查询（Data Query）相关操作；不过在更专业和通用的表述里，查询操作其实常被包含在 DML 里，因为 SELECT 语句本质也是对数据的一种操作。
• 解释：主要是从数据库里检索符合特定条件的数据，核心语句是 SELECT 。

数据库管理语言分类及作用：

5、数据库不同阶段

人工管理阶段（20 世纪 50 年代中期以前）

• 数据不保存：计算机主要用于科学计算，数据随程序运行结束而消失。
• 无管理软件：程序员自行管理数据，包括存储结构、存取方法等。
• 数据不共享：数据是程序的一部分，不同程序数据不能共享，冗余度高。
• 数据独立性差：数据存储结构改变，程序需大幅修改。

文件系统阶段（20 世纪 50 年代后期 - 60 年代中期）

• 数据可长期保存：数据以文件形式存于外存，可多次使用。
• 文件管理系统：操作系统提供文件管理功能，方便数据存取。
• 数据共享性差：文件面向特定应用，数据冗余大，易不一致。
• 数据独立性低：数据逻辑结构改变，需修改应用程序。

数据库系统阶段（20 世纪 60 年代后期至今）

• 数据结构化：整体数据结构化，数据间联系紧密。
• 高共享低冗余：数据面向整个系统，多用户共享，冗余低且易扩充。
• 高独立性：包括物理和逻辑独立性，数据存储和逻辑结构改变不影响应用程序。
• 统一管理控制：DBMS 统一管理，提供安全保护、完整性检查、并发控制和恢复功能。

高级数据库阶段（当代）

• 分布式数据库：数据分布存储，节点协作，具高扩展性和可用性。
• NoSQL 数据库：突破关系模型，用于海量数据和高并发，如键值、文档、列族、图数据库。
• NewSQL 数据库：融合关系数据库和 NoSQL 优点，兼顾 ACID 特性和扩展性。

\