Zhang XiJun

作业一

1

题目：

在某个计算机系统中有一台输入机和一台打印机，现有两道程序投入运行，且程序A先运行，程序B后开始运行。

• 程序A的运行轨迹为：
  计算50ms，打印100ms，再计算50ms，打印100ms。

• 程序B的运行轨迹为：
  计算50ms，输入80ms，再计算100ms，结束。

问题：

1. 两道程序运行时，CPU是否空闲等待？_（有空闲等待 / 无空闲等待）
   若有，在哪段时间内等待？ms - ___ms（两个空，第一个填起始时间，第二个填结束时间，仅数字）

2. 程序A，B是否有等待CPU的情况？
   A：（有等待 / 无等待）
   B：（有等待 / 无等待）
   若有，指出发生等待的时刻（若无等待，空格填0）
   （若有两段以上等待时间，用“/”标表示不同等待时间，如0/30和20/40表示0ms-20ms是第一段空闲；30ms-40ms是第二段空闲）
   A：ms - ms
   B：ms - ms

2

题目：

在单CPU和两台I/O设备（I1和I2）的多道程序设计环境下，同时投入三个作业运行，其执行轨迹如下：

• Job1：I2（30ms），CPU（10ms），I1（30ms），CPU（10ms）
• Job2：I1（20ms），CPU（20ms），I2（40ms）
• Job3：CPU（30ms），I1（20ms）

已知条件：

• CPU、I1、I2可以并行工作；
• 优先级从高到低依次为：Job1、Job2、Job3；
• 优先级高的作业可以抢占优先级低的作业（抢占式调度）；
• 所有作业同时投入运行。

问题：

1. 每个作业从投入到完成分别所需的时间。

   • Job1：__ ms
   • Job2：__ ms
   • Job3：__ ms

2. 从作业投入到完成，CPU的利用率是：

   • / = __%（保留小数点后两位）

3. I/O设备利用率：

   • I1 利用率： / = __%（保留小数点后两位）
   • I2 利用率： / = __%（保留小数点后两位）

3

题目：

在单机系统中，有同时到达的两个程序A、B，若每个程序单独运行，则使用CPU，DEV1（设备1）、DEV2（设备2）的顺序和时间如下表所示。

给定条件：

1. DEV1和DEV2是不同的I/O设备，它们能够同时工作。
2. 程序B优先级高于程序A，非抢占式。当程序A占用CPU时，即使程序B需要使用CPU，也不能打断程序A的执行，而应等待。
3. 当使用CPU之后控制转向I/O设备，或者使用I/O设备之后控制转向CPU，由控制程序执行中断处理，但这段处理时间可以忽略不计。

问题：

1. 哪个程序先结束？（A / B）
2. 程序全部执行结束需要多少时间？（__ ms）
3. 程序全部执行完毕时，CPU利用率是多少？（__%）
4. A程序等待CPU的累积时间是多少？（__ ms）
5. B程序等待CPU的累积时间是多少？（__ ms）

作业二

1

2

3.

3

作业三

1

有一个盒子里混装了数量相等的黑白围棋子，现在利用自动分拣系统把黑子、白子分开，设分拣系统有两个进程P1和P2，其中进程P1拣白子，进程P2拣黑子。规定每个进程每次拣一子；当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试写出进程P1和P2能够正确并发执行的程序。

2

请用信号量和PV操作解决以下问题：桌上有一只盘子，最多可以容纳两个水果，每次仅能放入或取出一个水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放橘子(orange)，两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子里的苹果。写出爸爸（father）、妈妈（mother）、儿子（son）和女儿（daughter）进程及所需定义的变量和信号量。用PV操作实现爸爸、妈妈、儿子、女儿间的同步与互斥关系。

3

设当前的系统状态如下，此时Available=(1,1,2)

作业四

1

数组int A[100][100]；元素按行存储，在虚拟系统中，采用LRU淘汰算法，一个进程有3页内存空间，每页可以存放200个整数，其中第1页存放程序，假定程序已在内容中，问：

A程序缺页次数为：__次；

B程序缺页次数为：__次。

程序A：

for(int i=0; i<100; i++)
   for(int j=0; j<100; j++)
        A[i,j]=0;

程序B：

for(int j=0;j<100;j++)
   for(int i=0;i<100;i++)   
           A[i,j]=0;

程序 A 分析

代码逻辑：

1
2
3

for(int i=0; i<100; i++)    // 外层循环：行
   for(int j=0; j<100; j++) // 内层循环：列
      A[i][j]=0;

访问顺序：A[0][0], A[0][1], …, A[0][99], A[1][0], …

这是按行访问，与数组的按行存储顺序一致。

缺页计算过程：

1. 访问第0、1行：都在虚拟页0中。
   • 第一次访问 A[0][0] 时，内存为空，发生 1次缺页，调入页0。
   • 后续访问第0行和第1行的剩余199个元素时，都在页0中，直接命中（不缺页）。
2. 访问第2、3行：都在虚拟页1中。
   • 访问 A[2][0] 时，页1不在内存，发生 1次缺页，调入页1。
   • 后续元素全部命中。
3. 以此类推：
   • 程序按照顺序访问：页0 $\to$ 页1 $\to$ 页2 … $\to$ 页49。
   • 由于我们有2个物理块，LRU算法会淘汰最久未使用的旧页面，但因为访问是单向顺序向前的，每一页只需要调入一次。

结果：共有50个页面，每页调入一次。

Total = 50 次缺页。

程序 B 分析

代码逻辑：

1
2
3

for(int j=0; j<100; j++)    // 外层循环：列
   for(int i=0; i<100; i++) // 内层循环：行
      A[i][j]=0;

访问顺序：A[0][0], A[1][0], A[2][0], …

这是按列访问，即“跳跃式”访问。

缺页计算过程：

1. 分析内层循环（i 从 0 到 99，处理第 j 列）：
   • i=0, 1: 访问第0、1行 $\to$ 需要 虚拟页0。
   • i=2, 3: 访问第2、3行 $\to$ 需要 虚拟页1。
   • …
   • i=98, 99: 访问第98、99行 $\to$ 需要 虚拟页49。
   • 一轮内循环（i=0~99）会依次访问：页0, 页1, 页2, …, 页49。
2. 内存状态与置换：
   • 我们只有 2个 物理块用于数据。
   • 当访问页0、页1时，填满内存。
   • 当需要页2时，根据LRU，淘汰页0。
   • 当需要页3时，根据LRU，淘汰页1。
   • …
   • 因为循环访问的页面数量（50页）远大于物理内存（2页），导致内存中的页面不断被替换（颠簸/Thrashing现象）。
   • 结论：在处理每一列（内层循环）时，需要访问所有50个页面。因为内存存不下，这 50个页面每一次都需要重新从磁盘调入。
   • 单列（一次外层循环）产生的缺页次数 = 50次。
3. 结合外层循环：
   • 外层循环 j 从 0 到 99，共执行 100次。
   • 每次外层循环都要重新把这50个页面遍历一遍。由于上一轮留下的页面（最后访问的页48、49）对下一轮开头需要的页（页0）没有帮助。
   • 总缺页次数 = 每列缺页数 $\times$ 列数
   • Total = $50 \times 100 = 5000$。

结果：5000 次缺页。

2

在一个请求分页虚存管理系统中，一个程序运行的页面走向是：1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6

分别用FIFO、OPT、和LRU算法，对于分配给程序3个页框的情况，求出缺页异常次数和缺页中断率：

（1）FIFO：缺页异常次数：_次, 缺页中断率：__%.

（2）OPT：缺页异常次数：_次, 缺页中断率：__%.

（3）LRU：缺页异常次数：_次, 缺页中断率：__%.

3

一个页式虚拟存储管理系统中的用户空间为1024KB，页面大小为4KB，内存空间为512KB。已知用户的10、11、12、13号虚页分得的内存页框号为62、78、25、36，试将逻辑地址0BEBCH转换为对应的物理地址: _H。

作业五

前言

本文讲解matlab与opencv对图像处理的基础操作，代码会有matlab与python两版，可对比学习。

读写

读入图像

matlab

1

I = imread('cameraman.jpg');

python

1

I = cv2.imread('cameraman.jpg', cv2.IMREAD_COLOR)

cv2.IMREAD_COLOR = 强制读成 3 通道 BGR 彩色图。

存入图像

matlab

1

imwrite(J,'cameramanC.jpg');

python

1

cv2.imwrite('cameramanC.jpg', J)

读图并转 double

matlab

1

Image1 = im2double(imread('lotus.jpg'));

• imread 把图像读成 0-255 的 uint8。
• im2double 把像素值线性缩放到 0–1 浮点，方便后续计算。

为什么要转成double

如果像素是 0–255，你在代码里写 0.299*r 就永远只用到 0.299×255≈76 灰度级，结果会整体偏暗甚至直接截断。

几级灰度的含义是什么

几级灰度”这句话里的“级”就是“台阶”的意思：
把黑→白这段连续亮度等间隔切成多少份，就有多少个离散台阶，叫多少灰度级。

• 2 级灰度 → 纯黑 + 纯白，一共 2 个台阶（1 bit）
• 8 级灰度 → 0, 36, 73, 109, 146, 182, 219, 255（3 bit）
• 256 级灰度 → 0–255，共 256 个台阶（8 bit）

uint8 是“Unsigned Integer, 8 bit”的缩写，含义一句话：

无符号、8 位、整型数字，只能放 0–255 的整数。

图像操作

反色

1

J=255-I;

提取通道

matlab

1
2
3

r = Image1(:,:,1);
g = Image1(:,:,2);
b = Image1(:,:,3);

分别提取rgb三个通道

opencv

1
2

matlab:g = Image1(1,1,2)提取G通道的第一个像素点
opencv:g = image[0,0,1]

opencv是从下标0开始

合并通道

NTSC 标准

1

Y = 0.299*r + 0.587*g + 0.114*b;

0.299、0.587、0.114 是 NTSC 在 1953 年定下的“亮度加权系数”，源于人眼三种视锥细胞对 R、G、B 光谱的灵敏度——绿最亮、红次之、蓝最暗

二值化（阈值 0.3）

1
2

BW = zeros(size(Y));   % 先全黑
BW(Y > 0.3) = 1;       % 亮度>0.3 的像素置 1（白）

从RGB颜色空间转换成HSI颜色空间

matlab

1

hsi = rgb2hsv(img);

HSI 颜色空间是把一幅彩色图像的每个像素拆成 3 个独立、且更符合人眼感知习惯的物理量：

1. H（Hue，色调）
   用 0°–360° 的“角度”表示“到底是什么颜色”。
   例：0°≈红，120°≈绿，240°≈蓝，绕一圈回到红。
2. S（Saturation，饱和度）
   0–1（或 0–100%）表示“颜色有多鲜艳”。
   0 → 灰，1 → 最纯、最艳。
3. I（Intensity，亮度/强度）
   0–1（或 0–255）表示“有多亮”，与颜色本身无关，只反映明暗。

• RGB 是“机器友好”的立方体坐标，但人眼很难从 (R,G,B) 直接说出“颜色、多艳、多亮”。

matlab基本操作

获取图像行列和通道数

1

[N,M,~]=size(r);

把二维矩阵 r 的“行数”赋给 N，“列数”赋给 M。

截取图像

1

newimage=img(H/4:H*3/4,W/4:W*3/4,:);

人脸肤色检测

YCrCb 阈值法

1. Y
   “Luma”——亮度（Luminance）。
   对应人眼最敏感的黑↔白信息，决定了你看到的“明暗”。
   计算公式近似：

   1	Y = 0.299·R + 0.587·G + 0.114·B

2. Cr
   “Chroma-red”——红色色度。
   表示 红色与亮度的差值：Cr = R – Y

3. Cb
   “Chroma-blue”——蓝色色度。
   表示 蓝色与亮度的差值：Cb = B – Y

人眼对 绿色最敏感，对 红、蓝最迟钝。
把“绿色”信息扔掉，只保留 R-Y 和 B-Y 两个差值，就能 最小化数据量，同时 还能把颜色还原回来。

• 人类肤色在 YCrCb 颜色空间呈明显的“聚类”特性：无论人种如何，Cb、Cr 两个色度分量都落在狭长带状区域。
• 选取经验区间（Cr ∈ [133,173]，Cb ∈ [77,127]）直接做 2D 门限，亮度 Y 不参与判断，因此对光照强度变化不敏感，但对色偏敏感。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def skin_YCrCb(img):
    #把一张 BGR 彩色图像从“蓝-绿-红”颜色空间转换到“亮度-红度-蓝度”颜色空间（YCrCb）
    ycrcb = cv2.cvtColor(img, cv2.COLOR_BGR2YCrCb)
    min_YCrCb = np.array([0, 133, 77])
    max_YCrCb = np.array([255, 173, 127])
    '''
把落在 [min_YCrCb, max_YCrCb] 立方体内的像素标为 255（白），其余标为 0（黑），返回一张单通道掩膜图。
执行过程（逐像素）：
取 ycrcb 的一个像素 (y, cr, cb)
检查是否同时满足
min_Y ≤ y ≤ max_Y
min_Cr ≤ cr ≤ max_Cr
min_Cb ≤ cb ≤ max_Cb
满足 → 输出 255；任一通道不满足 → 输出 0
    '''
    skin = cv2.inRange(ycrcb, min_YCrCb, max_YCrCb)
    return skin

HSV 阈值法

肤色聚类现象
大量统计表明：

• 不同人种、不同光照 的肤色在 RGB 空间里沿对角线“灰度轴”散开 → 亮度影响大。
• 转到 HSV 后，Hue 坐标紧紧挤在 0-20° 之间（红-橙-黄），S 中等偏高，V 中等偏亮

1
2
3
4
5
6

def skin_HSV(img):
    hsv = cv2.cvtColor(img, cv2.COLOR_BGR2HSV)
    low  = np.array([0,  30,  60])
    high = np.array([20, 150, 255])
    skin = cv2.inRange(hsv, low, high)
    return skin

椭圆模型法

原理：将RGB图像转换到YCRCB空间，肤色像素点会聚集到一个椭圆区域。先定义一个椭圆模型，然后将每个RGB像素点转换到YCRCB空间比对是否再椭圆区域，是的话判断为皮肤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# ---------------- 3. 椭圆模型法 ----------------
def skin_ellipse(img):
    ycrcb = cv2.cvtColor(img, cv2.COLOR_BGR2YCrCb)
    # 如果本地没有模型图，现场画一张 256×256 查找表
    ellipse_model = cv2.imread('ellipse_skin_model.png', 0)
    if ellipse_model is None:
        ellipse_model = np.zeros((256, 256), dtype=np.uint8)
        cv2.ellipse(ellipse_model, (113, 155), (23, 15),
                    43, 0, 360, 255, -1)
    cr = ycrcb[:, :, 1].astype(np.uint16)  # 防止溢出
    cb = ycrcb[:, :, 2].astype(np.uint16)
    indices = cr * 256 + cb
    skin = np.take(ellipse_model, indices)
    return skin

将彩色图像 Image1 的 R、B 通道互换

1

img_swap = img(:,:,[3 1 2]);

在 MATLAB 中，读取彩色图像（如用 imread）默认是 RGB 顺序：

• 第1通道：Red（红）
• 第2通道：Green（绿）
• 第3通道：Blue（蓝）

但在 OpenCV（Python/C++） 中，图像默认是 BGR 顺序：

• 第1通道：Blue
• 第2通道：Green
• 第3通道：Red

使用或操作，进行图像的嵌入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

clear; clc; close all;  % 清空所有变量
% 读取两张图片
background = imread('图片2.png');   
butterfly = imread('图片1.png');  

% 设置缩放比例
scale = 0.5;
small_butterfly = imresize(butterfly, scale, 'bilinear');

% 获取尺寸
[ih, iw, ~] = size(small_butterfly);
x = 200; y = 400;

% 提取背景中对应区域
bg_patch = background(x:x+ih-1, y:y+iw-1, :);

is_black = any(small_butterfly~=0,3);   % 蝴蝶主体区域

%只把背景中“蝴蝶主体对应位置”设为 0
% 获取尺寸
[ih, iw, ~] = size(bg_patch);

% 双重循环遍历每个像素
for i = 1:ih
    for j = 1:iw
        if is_black(i, j)   % 如果该位置是蝴蝶主体（非黑）
            bg_patch(i, j, 1) = 0;  % R 通道设为 0
            bg_patch(i, j, 2) = 0;  % G 通道设为 0
            bg_patch(i, j, 3) = 0;  % B 通道设为 0
        end
    end
end

%现在做 bitor：0 | butterfly = butterfly，背景黑区 | 0 = 背景
patch_bitor = bitor(bg_patch, small_butterfly);

% 写回背景
background(x:x+ih-1, y:y+iw-1, :) = patch_bitor;

% 显示结果
figure;
subplot(1,3,1), imshow(small_butterfly), title(['缩小后的蝴蝶 (', num2str(scale*100), '%)']);
subplot(1,3,2), imshow(bg_patch), title('处理后的背景块（蝴蝶位置清黑）');
subplot(1,3,3), imshow(background), title('最终合成图（bitor）');

利用单尺度和多尺度 Retinex 增强方法实现图像增强

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

I = imread('gugong1.jpg');

if ndims(I) == 3
    I_gray = rgb2gray(I);
else
    I_gray = I;
end

I_double = double(I_gray) + eps;

% SSR
sigma = 15;
L_ssr = log(conv2(I_double, fspecial('gaussian', [31, 31], sigma), 'same'));
R_ssr = log(I_double) - L_ssr;
ssr_img = mat2gray(R_ssr);

% MSR
sigmas = [15, 80, 250];
weights = [0.33, 0.34, 0.33];
R_msr = zeros(size(I_double));
for k = 1:length(sigmas)
    sigma = sigmas(k);
    kernel_size = round(6 * sigma) + 1;
    if mod(kernel_size, 2) == 0
        kernel_size = kernel_size + 1;
    end
    L = log(conv2(I_double, fspecial('gaussian', [kernel_size, kernel_size], sigma), 'same'));
    R_msr = R_msr + weights(k) * (log(I_double) - L);
end
msr_img = mat2gray(R_msr);

figure;
subplot(1,3,1); imshow(I); title('Original');
subplot(1,3,2); imshow(ssr_img); title('SSR');
subplot(1,3,3); imshow(msr_img); title('MSR');

直方图均衡化计算

5.4代码

opencv

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import numpy as np
import matplotlib.pyplot as plt

# --- Step 1: 构造原始图像 ---
gray_levels = np.array([0, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1])  # 原始灰度值 (0~1)
pixel_counts = np.array([560, 920, 1046, 705, 356, 267, 170, 72])
total_pixels = 64 * 64  # 4096

# 将灰度值映射到整数 0~7 用于图像存储
int_gray_levels = np.round(gray_levels * 7).astype(int)  # [0,1,2,3,4,5,6,7]

# 创建图像数组
img = np.zeros(total_pixels, dtype=np.uint8)

start_idx = 0
for i, count in enumerate(pixel_counts):
    img[start_idx:start_idx + count] = int_gray_levels[i]
    start_idx += count

img = img.reshape((64, 64))  # 重塑为 64x64 图像

# --- Step 2: 直方图均衡化 ---
hist, _ = np.histogram(img, bins=8, range=(0, 8))
cdf = np.cumsum(hist) / total_pixels
mapping = np.round(cdf * 7).astype(int)
equalized_img = mapping[img]

# --- Step 3: 可视化对比 ---
plt.figure(figsize=(8, 4))

plt.subplot(1, 2, 1)
plt.imshow(img, cmap='gray', vmin=0, vmax=7)
plt.title('Original')
plt.axis('off')

plt.subplot(1, 2, 2)
plt.imshow(equalized_img, cmap='gray', vmin=0, vmax=7)
plt.title('Equalized')
plt.axis('off')

plt.tight_layout()
plt.show()

landingpage的组成

1.开始界面，大概说明产品的定位和作用，让用户可以快速注册后进入

Grammarly: Free AI Writing Assistance

2.展示产品的特点功能和使用范例：1.特点功能这块可以像manus把使用过程中比较有特点的功能截屏，做成下面这样；2.范例部分结构可以参考manus或者lovart垂直滑动的效果，效果可以参考genspackGenspark - AI 幻灯片

专为演示文稿打造的 Gamma | 利用 AI 立即构建演示文稿 | Gamma

3.用户的声音，价格。用户声音我觉得参考lovart就可以，声音这边也可以使用一个滚动的效果

TRAE - Collaborate with Intelligence

我感觉我们的风格应该还是要简约大气

PPtYoda技术调用

这个项目的核心就是基于python-pptx的这个包，其实跟我们不是很符合。

他们ppt生成的逻辑核心是模板，一定要有pptx模板，并带有每个部分的备注，上传后解析，把ppt的各个结构转化成json存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

file = models.FileField(
        upload_to=get_template_path,
        storage=ppt_storage,
    )
    created_at = models.DateTimeField(auto_now_add=True)

    cover_template = models.JSONField(null=True, blank=True, default=dict)
    toc_template = models.JSONField(null=True, blank=True, default=dict)
    chapter_L1_template = models.JSONField(null=True, blank=True, default=dict)
    chapter_L2_template = models.JSONField(null=True, blank=True, default=dict)
    blank_template = models.JSONField(null=True, blank=True, default=dict)

    slide_templates = models.JSONField(null=True, blank=True, default=list)
    components = models.JSONField(null=True, blank=True, default=list)
    sections = models.JSONField(null=True, blank=True, default=dict)

生成ppt时，也是让大模型生成符合这种规范的json，然后通过python-pptx填入。

这样好处确实是解决了使用python-pptx时，生成的ppt结构混乱的问题，但是这样生成的ppt完全依赖于你输入的模板，灵活性上有所缺陷。

后续任务

1.导出speaknotes-pdf后端

2.生成完整presentation

docker部署

1
2
3
4
5
6
7
8
9

docker pull postgres

docker run -d --name pgsql \
  -p 5432:5432 \
  -e POSTGRES_PASSWORD=123456 \
  -v D:\database\postgresql:/var/lib/postgresql/data \
  postgres
  
  docker run -d --name pgsql -p 5432:5432 -e POSTGRES_PASSWORD=123456 -v D:\database\postgresql:/var/lib/postgresql/data postgres

docker 运行postgresql 极限简洁教程 - 刘老六 - 博客园

恢复数据库

使用pg_restore

1
2
3
4
5
6
7

# 1. 删除现有数据库
psql -U postgres -c "DROP DATABASE dvdrental;"

# 2. 重建空数据库
psql -U postgres -c "CREATE DATABASE dvdrental;"

pg_restore --dbname=postgresql://postgres:123456@localhost:5432/dvdrental --no-owner /workspace/dvdrental

以下是数据库导入的原理

1. toc.dat（目录文件）

作用 ：Table of Contents，包含备份的元数据信息

内容 ：数据库结构、表定义、索引、约束、函数等的描述

格式 ：二进制格式，记录了所有数据库对象的信息

1. 数据文件（3038.dat, 3040.dat, …）

作用 ：存储实际的表数据

命名规则 ：数字对应数据库对象的 OID（Object Identifier）

1. restore.sql（可选的SQL脚本）

作用 ：包含恢复数据库的 SQL 命令

内容 ：CREATE TABLE、INSERT、索引创建等语句

pg_restore 工作流程

1. 读取 toc.dat
2. 创建数据库结构
3. 创建约束和索引

SQLAlchemy ORM

范例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

---
config:
  layout: elk
---
erDiagram
    零件（Part） ||--o{ 库存（Inventory） : "存放"
    库房（Warehouse） ||--o{ 库存（Inventory） : "包含"
    供应商（Supplier） ||--o{ 采购（Purchase） : "供应"
    零件（Part） ||--o{ 采购（Purchase） : "被采购"
    库房（Warehouse） ||--o{ 采购（Purchase） : "接收"
    库房（Warehouse） }|--|| 职工（Staff） : "组长"
    库房（Warehouse） ||--o{ 职工（Staff） : "雇佣"
    零件（Part） {
        string part_id PK "零件编号"
        string name "名称"
        decimal unit_price "单价"
        string type "类型"
    }
    供应商（Supplier） {
        string supplier_id PK "供应商编号"
        string name "名称"
        string address "地址"
        string phone "电话"
    }
    库房（Warehouse） {
        string warehouse_id PK "库房号"
        string address "地址"
    }
    职工（Staff） {
        string staff_id PK "职工号"
        string name "姓名"
        string gender "性别"
        date hire_date "进厂时间"
        string title "职称"
        string warehouse_id FK "所属库房"
    }
    库存（Inventory） {
        string warehouse_id PK,FK "库房号"
        string part_id PK,FK "零件编号"
        int stock_quantity "库存数量"
    }
    采购（Purchase） {
        string purchase_id PK "采购单号"
        string part_id FK "零件编号"
        string supplier_id FK "供应商编号"
        string warehouse_id FK "库房号"
        date purchase_date "采购日期"
        int quantity "进货数量"
        decimal actual_price "实际单价"
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

# models.py
from sqlalchemy import (
    create_engine, Column, String, Integer, DECIMAL, Date, CHAR,
    ForeignKey, CheckConstraint, UniqueConstraint
)
from sqlalchemy.ext.declarative import declarative_base
from sqlalchemy.orm import relationship

# SQLAlchemy 的基类，所有模型类都需要继承这个 Base
# declarative_base() 创建了一个基类，用于定义数据库表结构的映射
Base = declarative_base()

class Part(Base):
    __tablename__ = 'part'
    
    part_id = Column(String(20), primary_key=True)
    name = Column(String(100), nullable=False)
    unit_price = Column(DECIMAL(10, 2), nullable=False)
    type = Column(String(50), nullable=False)
    
    # 约束：单价 >= 0
    __table_args__ = (
        CheckConstraint(unit_price >= 0, name='check_unit_price_positive'),
    )

class Supplier(Base):
    __tablename__ = 'supplier'
    
    supplier_id = Column(String(20), primary_key=True)
    name = Column(String(100), nullable=False)
    address = Column(String(200))
    phone = Column(String(20))

class Warehouse(Base):
    __tablename__ = 'warehouse'
    
    warehouse_id = Column(String(20), primary_key=True)
    address = Column(String(200), nullable=False)

    # 可选：未来加组长时在此添加
    # leader_staff_id = Column(String(20), ForeignKey('staff.staff_id'), unique=True)

class Staff(Base):
    __tablename__ = 'staff'
    
    staff_id = Column(String(20), primary_key=True)
    name = Column(String(50), nullable=False)
    gender = Column(CHAR(1))
    hire_date = Column(Date, nullable=False)
    title = Column(String(50))
    warehouse_id = Column(String(20), ForeignKey('warehouse.warehouse_id'), nullable=False)
    
    # 约束：性别只能是 M/F
    __table_args__ = (
        CheckConstraint("gender IN ('M', 'F')", name='check_gender'),
    )

class Inventory(Base):
    __tablename__ = 'inventory'
    
    warehouse_id = Column(String(20), ForeignKey('warehouse.warehouse_id'), primary_key=True)
    part_id = Column(String(20), ForeignKey('part.part_id'), primary_key=True)
    stock_quantity = Column(Integer, nullable=False)
    
    # 表级约束：确保库存数量不能为负数
    # 当尝试插入或更新为负数时会触发数据库错误
    __table_args__ = (
        CheckConstraint(stock_quantity >= 0, name='check_stock_non_negative'),
    )

class Purchase(Base):
    __tablename__ = 'purchase'
    
    purchase_id = Column(String(30), primary_key=True)
    part_id = Column(String(20), ForeignKey('part.part_id'), nullable=False)
    supplier_id = Column(String(20), ForeignKey('supplier.supplier_id'), nullable=False)
    warehouse_id = Column(String(20), ForeignKey('warehouse.warehouse_id'), nullable=False)
    purchase_date = Column(Date, nullable=False)
    quantity = Column(Integer, nullable=False)
    actual_price = Column(DECIMAL(10, 2), nullable=False)
    
    # 表级约束：确保采购业务逻辑的合理性
    # - 采购数量必须为正数（不能为零或负数）
    # - 实际采购价格必须为正数（不能为零或负数）
    __table_args__ = (
        CheckConstraint(quantity > 0, name='check_quantity_positive'),
        CheckConstraint(actual_price > 0, name='check_price_positive'),
    )

建立表

1

DATABASE_URL = "postgresql://postgres:123456@localhost:5432/factory_db"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# create_tables.py
from sqlalchemy import create_engine
from models import Base
from dotenv import load_dotenv
import os

load_dotenv()

# 替换为你的 Docker PostgreSQL 地址
DATABASE_URL = os.getenv("DATABASE_URL")

# 创建数据库引擎，用于连接数据库
# create_engine 会根据 DATABASE_URL 创建对应的数据库连接池
engine = create_engine(DATABASE_URL)
Base.metadata.create_all(engine)  # 自动建表！
print("✅ 所有表已创建")

各类 RAG 增强技术

如何提高 RAG 管道的性能 | Milvus 文档

可以通过此GitHub 链接获得本文所列主要方法的简单实现。

我们可以根据 RAG 管道各阶段的作用对不同的 RAG 增强方法进行分类。

• 查询增强：修改和操作 RAG 输入的查询过程，以便更好地表达或处理查询意图。
• 增强索引：使用多分块、分步索引或多向索引等技术优化分块索引的创建。
• 检索器增强：在检索过程中应用优化技术和策略。
• 生成器增强：在为 LLM 生成提示时调整和优化提示，以提供更好的响应。
• 增强 RAG 管道：在整个 RAG 管道中动态切换流程，包括使用 Agents 或工具来优化 RAG 管道中的关键步骤。

接下来，我们将介绍每个类别下的具体方法。

查询增强

共有四种方式：假设问题、假设文档嵌入、子查询和回溯提示。接下来我将选取几个具体说明。

HyDE（假设文档嵌入）

HyDE 是假设文档嵌入的缩写。它利用 LLM 制作一个“假设文档\“或虚假\答案，以回应没有上下文信息的用户查询。然后，这个假答案会被转换成向量嵌入，并用于查询向量数据库中最相关的文档块。随后，向量数据库会检索出 Top-K 最相关的文档块，并将它们传送给 LLM 和原始用户查询，从而生成最终答案。

这种方法在解决向量搜索中的跨域不对称问题方面与假设问题技术类似。不过，它也有缺点，如增加了计算成本和生成虚假答案的不确定性。

创建子查询

当用户查询过于复杂时，我们可以使用 LLM 将其分解为更简单的子查询，然后再将其传递给向量数据库和 LLM。让我们来看一个例子。

想象一下，用户会问“Milvus 和 Zilliz Cloud 在功能上有什么不同？\“这个问题相当复杂，在我们的知识库中可能没有直接的答案。为了解决这个问题，我们可以将其拆分成两个更简单的子查询：

• 子查询 1：”Milvus 有哪些功能？”
• 子查询 2：”Zilliz Cloud 有哪些功能？”

有了这些子查询后，我们将它们全部转换成向量嵌入后发送给向量数据库。然后，向量数据库会找出与每个子查询最相关的 Top-K 文档块。最后，LLM 利用这些信息生成更好的答案。

增强索引

增强索引是提高 RAG 应用程序性能的另一种策略。让我们来探讨三种索引增强技术：自动合并文档块，构建分层索引，混合检索和重新排名

构建分层索引

在创建文档索引时，我们可以建立两级索引：一级是文档摘要索引，另一级是文档块索引。向量搜索过程包括两个阶段：首先，我们根据摘要过滤相关文档，随后，我们在这些相关文档中专门检索相应的文档块。

在涉及大量数据或数据分层的情况下，例如图书馆 Collections 中的内容检索，这种方法证明是有益的。

混合检索和重新排名

混合检索和重排技术将一种或多种辅助检索方法与向量相似性检索相结合。然后，Reranker会根据检索结果与用户查询的相关性对检索结果重新排序。

常见的补充检索算法包括基于词频的方法（如BM25）或利用稀疏嵌入的大模型（如SPLADE）。重新排序算法包括 RRF 或更复杂的模型，如Cross-Encoder（类似于 BERT 的架构）。

改进检索器

改进 RAG 系统中的检索器组件也能改进 RAG 应用。让我们来探讨一些增强检索器的有效方法：句子窗口检索，元数据过滤

生成器增强

让我们通过改进 RAG 系统中的生成器来探索更多 RAG 优化技术：压缩 LLM 提示，调整提示中的块顺序

调整提示中的块顺序

在论文Lost in the Middle“中，研究人员观察到，LLMs 在推理过程中经常会忽略给定文档中间的信息。相反，他们往往更依赖于文档开头和结尾的信息。

根据这一观察结果，我们可以调整检索知识块的顺序来提高答案质量：在检索多个知识块时，将置信度相对较低的知识块放在中间，而将置信度相对较高的知识块放在两端。

增强 RAG 管道

我们还可以通过增强整个 RAG 管道来提高 RAG 应用程序的性能。

自我反思

这种方法在人工智能 Agents 中融入了自我反思的概念。那么，这种技术是如何工作的呢？

一些最初检索到的 Top-K 文档块是模棱两可的，可能无法直接回答用户的问题。在这种情况下，我们可以进行第二轮反思，以验证这些文档块是否能真正解决查询问题。

我们可以使用高效的反思方法（如自然语言推理（NLI）模型）进行反思，也可以使用互联网搜索等其他工具进行验证。

使用代理进行查询路由选择

有时，我们不必使用 RAG 系统来回答简单的问题，因为它可能会导致更多的误解和对误导信息的推断。在这种情况下，我们可以在查询阶段使用代理作为路由器。这个 Agents 会评估查询是否需要通过 RAG 管道。如果需要，则启动后续的 RAG 管道；否则，LLM 直接处理查询。

Agents 可以有多种形式，包括 LLM、小型分类模型，甚至是一组规则。

通过根据用户意图路由查询，可以重新定向部分查询，从而显著提高响应时间，并明显减少不必要的噪音。

我们可以将查询路由技术扩展到 RAG 系统内的其他流程，例如确定何时利用网络搜索等工具、进行子查询或搜索图片。这种方法可确保 RAG 系统中的每个步骤都能根据查询的具体要求进行优化，从而提高信息检索的效率和准确性。

操作系统概论

操作系统的主要特征

并发性 (Concurrency)

🔍 核心定义

并发性是指两个或两个以上的事件或活动在同一时间间隔内发生。

• 关键点：“同一时间间隔” ≠ “同一时刻”。它强调的是“看起来同时”，而不是“真正同时”。

📌 操作系统中的体现

1. 多个 I/O 设备同时工作：

   • 你的键盘在输入，打印机在打印，网卡在收发数据。这些设备都在“同时”工作。

2. I/O 和 CPU 计算同时进行：

   • 当 CPU 在计算时，I/O 设备可能在后台传输数据。CPU 不需要等待 I/O 完成，可以去处理其他任务。

3. 内存中多个程序交替执行：

   • 这是最核心的体现。操作系统通过时间片轮转（Time-Slicing）等调度算法，让多个程序“轮流”使用 CPU，从而实现“宏观上的并发”。

🖼️ 并发 vs 并行

这是你 PPT 中提出的关键问题！

✅ 一句话总结：并行是并发的一种特例。并发是“逻辑上的同时”，并行是“物理上的同时”。

共享性 (Sharing)

🔍 核心定义

共享性指操作系统中的资源（包括硬件资源和软件资源）可被多个并发执行的进程共同使用，而不是被一个进程所独占。

• 关键点：共享不等于“无限制访问”，它必须在操作系统管理下进行，以保证安全和有序。

📌 资源共享的方式

1️⃣ 透明资源共享 / 同时共享方式

• 含义：允许多个进程在同一时间段内对资源进行访问，好像每个进程都独占资源一样。
• 特点：
  • 访问的次序对结果无影响。
  • 通常用于可重入或只读的资源。
• 例子：
  • CPU：通过时间片轮转，让多个进程“同时”使用 CPU。
  • 主存 (RAM)：多个进程的代码和数据可以同时存在于内存中。
  • 磁盘：多个进程可以同时读取磁盘上的不同文件。
  • 打印机：虽然物理上一次只能打印一个任务，但操作系统可以通过“打印队列”实现逻辑上的“同时共享”。

2️⃣ 独占资源共享 / 互斥共享方式

• 含义：在同一时间段内只允许一个进程访问资源。
• 特点：
  • 这类资源称为临界资源 (Critical Resource)。
  • 必须通过互斥机制（如锁、信号量）来保护。
• 例子：
  • 磁带机：一次只能由一个进程控制。
  • 扫描仪：一次只能扫描一份文档。
  • 数据库中的某一行记录：如果两个事务同时修改同一行，会导致数据不一致。

🛠️ 操作系统如何管理共享？

• 提供显式资源共享机制：如 fork(), semaphore, mutex, lock 等系统调用。
• 将互斥访问下放给用户决策：程序员需要自己负责加锁和解锁，操作系统提供工具。

异步性 (Asynchrony)

🔍 核心定义

异步性指在多道程序环境中，由于资源有限而进程众多，多数情况下，进程的执行不是一气呵成，而是“走走停停”。

• 关键点：进程的执行是不可预测的，它的推进速度取决于系统调度、I/O 等待、中断等多种因素。

📌 异步性的表现

1. 作业到达系统的时间和类型不确定：

   • 用户随时可能启动一个新程序。

2. 操作员发出命令或操作的时间和类型不确定：

   • 用户可能随时按下键盘或点击鼠标。

3. 程序运行发生错误或异常的类型和时刻不确定：

   • 程序可能因为除零、内存溢出等原因崩溃。

4. 中断事件发生的时刻不确定：

   • 时钟中断、I/O 中断、硬件故障中断等都是随机发生的。

1
2
3
4
5
6
7

graph TD
    A[并发性] --> B[多个任务同时执行]
    C[共享性] --> D[资源被多个任务共同使用]
    E[异步性] --> F[任务执行“走走停停”]

    B & D & F --> G[现代操作系统的核心特征]
    G --> H[实现多任务、多用户环境]

多道程序设计

核心思想

多道程序设计是指允许多个程序同时驻留在内存中，并由操作系统统一管理和调度，使它们交替（并发）地使用 CPU 和其他系统资源。

• 核心目的：掩盖 I/O 等待时间，提高 CPU 和系统资源的利用率。
• 终极目标：让昂贵的 CPU 永远不要闲着！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

gantt
    title 单道程序 vs 多道程序
    dateFormat  HH:mm:ss
    axisFormat  %Ss

    section 单道程序
    作业A-CPU     :crit, a1, 00:00:00, 2s
    作业A-I/O     :active, a2, after a1, 8s
    作业A-CPU     :crit, a3, after a2, 2s
    作业A-I/O     :active, a4, after a3, 8s

    section 多道程序
    作业A-CPU     :crit, b1, 00:00:00, 2s
    作业B-CPU     :crit, b2, after b1, 2s
    作业C-CPU     :crit, b3, after b2, 2s
    作业A-I/O     :active, b4, after b1, 8s
    作业B-I/O     :active, b5, after b2, 8s
    作业C-I/O     :active, b6, after b3, 8s

对比：在多道程序中，当作业 A 在等待 I/O 时，CPU 立刻去执行作业 B 和 C。CPU 几乎没有空闲时间，利用率接近 100%！

cpu利用率

CPU利用率 = 1 - p^n

🔍 假设条件

1. 系统中有 n 个程序 同时在内存中。
2. 每个程序平均有 p 的概率在等待 I/O 操作。
   • 例如，p = 0.8 表示一个程序有 80% 的时间在等磁盘读写、键盘输入等，只有 20% 的时间在真正使用 CPU。
3. 各个程序的等待操作是相互独立的。
   • 这是一个关键假设，意味着一个程序是否在等 I/O，不影响其他程序。

💡 公式推导

• CPU 空闲的概率：当且仅当所有 n 个程序都在等待 I/O 时，CPU 才会空闲。
• 因为每个程序等待 I/O 的概率是 p，且它们相互独立，所以所有 n 个程序都等待 I/O 的概率是 p^n。
• 因此，CPU 空闲的概率 = p^n。
• CPU 利用率 = 1 - CPU 空闲的概率 = 1 - p^n。

若进程平均花费 80% 的时间等待 I/O，则为了使得 CPU 利用率不低于 80%，应至少有多少道程序在主存中运行？

计算过程

根据公式：

CPU利用率 = 1 - p^n ≥ 0.8

移项得：

p^n ≤ 0.2

代入 p = 0.8：

0.8^n ≤ 0.2

两边取对数（以 10 为底或自然对数均可）：

n * log(0.8) ≤ log(0.2)

注意：log(0.8) 是负数，所以在除的时候要反转不等号方向：

n ≥ log(0.2) / log(0.8)

计算数值：

• log(0.2) ≈ -0.69897
• log(0.8) ≈ -0.09691
• n ≥ (-0.69897) / (-0.09691) ≈ 7.21

因为 n 必须是整数，且要满足 n ≥ 7.21，所以：

n = 8

✅ 最终答案

为了使得 CPU 利用率不低于 80%，应至少有 8 道程序在主存中运行。

是不是同时运行的程序越多越好？

不是！同时运行的程序（道数）并不是越多越好。存在一个最优的“道数”，超过这个值，系统的整体效率反而会下降。

当道数 n 超过某个临界值后，系统性能会急剧下降。主要原因有：

1️⃣ 上下文切换开销 (Context Switching Overhead)

什么是上下文切换？

• 当操作系统从一个进程切换到另一个进程时，它需要保存当前进程的状态（寄存器、内存映射、程序计数器等），并加载下一个进程的状态。

2️⃣ 内存压力 (Memory Pressure)

• 每个进程都需要内存：代码段、数据段、堆、栈、页表等。

3️⃣ 资源竞争加剧 (Resource Contention)

• 锁竞争：多个进程同时访问共享资源（如数据库连接池、文件锁），需要排队等待，增加了延迟。
• 缓存失效：多个进程的指令和数据交替进入 CPU 缓存，导致缓存命中率降低，CPU 需要更频繁地从内存读取数据。

处理器状态

为什么需要两种处理器状态？

现代计算机是一个多用户、多任务的环境。如果所有程序都能随意执行任何指令，那么一个不小心的 bug 或一个恶意程序就可能：

• 格式化硬盘。
• 修改系统时间。
• 访问其他用户的隐私数据。
• 导致系统崩溃。

为了避免这种情况，CPU 被设计成有两种工作模式：

1. 用户态 (User Mode)：普通程序运行的状态，只能执行“安全”的指令。
2. 核心态 (Kernel Mode / Supervisor Mode)：操作系统内核运行的状态，可以执行所有指令，包括“危险”的特权指令。

程序状态字 (PSW)

Program Status Word (PSW) 是一个非常重要的寄存器。

• 定义：PSW 是 CPU 内部的一个特殊寄存器，用于存储当前处理器的各种状态信息。
• 关键作用：PSW 中有一个标志位（通常是最高位或某一位），用来标识当前 CPU 处于用户态还是核心态。
  • PSW[bit] = 0 → 用户态
  • PSW[bit] = 1 → 核心态

✅ 这就是 CPU 判断当前是否可以执行特权指令的依据！

当 CPU 执行一条指令时，它会检查 PSW 中的这个标志位：

• 如果是用户态，并且指令是特权指令，则触发一个异常 (Exception)，操作系统会介入处理（通常是终止该程序）。
• 如果是核心态，则允许执行。

CPU 如何判断当前是否可以执行特权指令？

答案：CPU 通过检查 程序状态字 (PSW) 中的一个特定标志位来判断。

• 如果该标志位表示当前处于用户态，并且遇到的是特权指令，则 CPU 会触发一个异常（通常是“非法指令”或“特权指令违规”），并将控制权交给操作系统内核。
• 操作系统内核会根据情况决定是终止该程序，还是进行其他处理。

进程控制和管理

进程定义与属性

进程（Process）是程序在计算机上的一次执行实例，是操作系统进行资源分配、调度和保护的基本单位。

为什么要引入“进程”？

1️⃣ 刻画系统的动态性（Dynamic Nature）

• 问题：程序是静态的代码，无法描述“执行中”的状态。
• 解决方案：进程是一个动态实体，它有生命周期（创建 → 运行 → 阻塞 → 终止）。
• 意义：操作系统可以精确跟踪每个任务的当前状态，做出调度决策。

2️⃣ 发挥系统的并发性（Concurrency）

• 问题：CPU 和 I/O 设备速度不匹配。程序在等待 I/O（如读文件、网络请求）时，CPU 就空闲了。
• 解决方案：通过进程切换，让 CPU 在等待期间去执行其他任务。
• 意义：提高了 CPU 利用率和系统吞吐量。

3️⃣ 解决资源共享与隔离的矛盾

• 问题：多个程序可能需要共享资源（如文件、打印机），但又不能互相干扰。
• 解决方案：
  • 共享性：进程可以通过合法机制（如共享内存、消息队列）共享资源。
  • 独立性/保护性：每个进程拥有独立的地址空间，操作系统通过内存管理单元（MMU）确保 A 进程不能访问 B 进程的内存。
• 意义：既实现了协作，又保证了安全和稳定。

进程的五大核心属性

进程状态转换

五态模型

七态模型

七态模型在五态模型的基础上，显式增加了“挂起（Suspend）”的概念

挂起 = 进程被换出到外存（Swap）

• 目的：当系统内存紧张时，操作系统会将一些暂时不活跃的进程（比如长时间阻塞的进程）从内存移到硬盘上的“交换区（Swap Space）”，以腾出内存给更紧急的任务。

挂起就绪态 (Ready/Suspend)

定义：

进程具备运行条件（即它已经准备好执行），但目前在外存中。只有当它被换入内存后，才能被调度器选中运行。

挂起等待态 (Blocked/Suspend)

定义：

进程正在等待某一个事件发生（如 I/O 完成、用户输入、网络响应），并且目前在外存中。

进程描述和组成

进程映像

进程映像（Process Image）是指进程在内存中的完整内容，包括代码、数据、堆、栈以及内核数据结构（如 PCB）等所有组成部分的集合。

进程上下文

寄存器上下文 (Register Context)存储在 PCB 中
包含：通用寄存器、程序计数器、栈指针、程序状态字

这是进程“灵魂”的一部分——CPU 执行时最直接依赖的状态。

PCB（Process Control Block，进程控制块）

PCB 是操作系统为每个进程创建的一个数据结构，用来记录和刻画该进程的所有状态和相关信息。

1️⃣ 进程标识信息 (Identification Information)

🌰 你的例子：

1 2 3

import os print(f"当前进程 PID: {os.getpid()}") print(f"父进程 PID: {os.getppid()}")

这些值就是从 PCB 中读取的！

2️⃣ 处理器状态信息 (Processor State Information) —— 这就是“寄存器上下文”

这是 PCB 最关键的部分，用于上下文切换。

⚡ 关键点：每次进程切换时，操作系统都会将当前 CPU 寄存器的值“倾倒”进 PCB，再从新进程的 PCB “倒回”寄存器。这就是“上下文切换”的核心开销。

3️⃣ 进程调度信息 (Scheduling Information)

🌰 你的例子：
在 FastAPI 中，当一个请求在 await httpx.get(...) 时，其对应协程/线程的状态会被标记为“阻塞”，并被放入等待队列。这就是 PCB 中“进程状态”字段的作用。

4️⃣ 内存管理信息 (Memory Management Information)

💡 关键点：确保进程访问的是自己的内存空间，实现“内存保护”。

5️⃣ I/O 状态信息 (I/O Status Information)

🌰 你的例子：
当你在 Python 中 f = open("log.txt", "a") 时，操作系统会在 PCB 的“打开文件列表”中添加一条记录，记录这个文件句柄 f 对应的 fd。

6️⃣ 记账信息 (Accounting Information)

📊 用途：用于性能监控、计费、调试等。

进程队列

链接方式

索引方式

进程切换和处理器状态转换

模式切换 vs. 进程切换

1. 模式切换 (Mode Switch)

定义：CPU 在“用户态（User Mode）”和“核心态（Kernel Mode）”之间的切换。 触发方式：由中断（Interrupt）或系统调用（System Call） 引起。 目的：让操作系统获得控制权，执行特权指令（如访问硬件、修改内存映射）。

1. 进程切换 (Process Switch / Context Switch)

定义：操作系统暂停当前正在运行的进程，保存其状态，并加载另一个进程的状态，使其开始运行。 触发方式：通常发生在核心态下，由中断或系统调用引发。 目的：实现多任务并发，公平分配 CPU 时间。

当进程开始运行时，操作系统如何重新获得控制？

果进程一直在运行，操作系统就永远没机会调度其他进程了，系统就会卡死。

答案：中断 (Interrupt) 是关键！

• 什么是中断？ 中断就像一个“紧急电话”，它能打断 CPU 当前正在执行的程序，强制 CPU 去处理一个更高优先级的事情——通常是操作系统内核。
  • 硬件中断：由外部设备触发，比如键盘敲击、鼠标移动、网络数据包到达、定时器到期。
  • 软件中断/异常：由程序自身触发，比如除零错误、访问非法内存地址、或者程序主动发起的系统调用（如 open(), read()）。

进程需要保存哪些状态？

当操作系统获得控制权后，它必须把当前正在运行的进程（比如进程0）的“工作状态”完整地记录下来，以便将来能恢复执行。这个过程叫做“保存现场 (Save Context)”。

需要保存哪些状态？

这些状态主要存储在一个叫做 PCB (Process Control Block, 进程控制块) 的数据结构里。PCB 就像是进程的“身份证 + 工作日志 + 资源清单”。

如何选择下一个待执行的进程/线程？

当操作系统保存完当前进程的状态后，它需要决定“接下来该让谁干活”。这个决策过程叫做“进程调度 (Process Scheduling)”。

如何选择？

这取决于操作系统的调度算法 (Scheduling Algorithm)。

线程

为什么需要线程？—— 引入线程的动机

❓ 问题：进程模型有什么不足？

1. 切换开销大：进程切换需要保存/恢复整个内存空间（代码、数据、堆、栈）和 PCB，开销大。
2. 通信困难：进程间通信（IPC）需要管道、消息队列、共享内存等复杂机制，效率低。
3. 不适合细粒度并发：比如一个 Web 服务器，每个请求都创建一个进程，成本太高。

✅ 解决方案：引入线程！

线程是进程内的一个执行单元，是 CPU 调度和分派的基本单位。

• 同一个进程内的所有线程：
  • 共享：代码段、数据段、堆、打开的文件等进程资源。
  • 私有：各自的栈和寄存器上下文。

💡 核心价值：实现进程内部的并发，降低切换和通信开销。

什么是线程？—— 核心定义

线程（Thread）是进程中一个可并发执行的控制流，它拥有自己独立的栈和寄存器状态，但与其他线程共享进程的地址空间和资源。

线程如何工作？—— 线程的生命周期与切换

1. 线程的生命周期状态

和进程类似，线程也有状态：新建 → 就绪 → 运行 → 阻塞 → 终止。

1. 线程切换（Thread Switching）

• 开销远小于进程切换！因为不需要切换地址空间（页表），只需要保存/恢复寄存器上下文和栈指针。
• 切换由线程调度器（在 OS 内核或用户态库中）管理。

1. 线程的实现方式

💡 Python 的 threading 是内核级线程，但受 GIL 限制，无法真正并行执行 Python 字节码。

处理器调度

调度层次

1️⃣ 高级调度（High-Level Scheduling）—— 作业调度 / 长程调度

目标：决定哪些“作业”被允许进入系统参与 CPU 竞争。 对象：作业（Job）→ 通常是一个完整的程序或任务（如编译一个文件、运行一个脚本）。 发生频率：低（几分钟到几小时一次）。 执行者：操作系统内核。

🔍 核心功能：

• 选作业进内存：从后备队列中选择作业，将其加载到内存，创建进程。
• 控制多道程序的道数：决定同时在内存中运行多少个作业（即并发度）。太多会耗尽内存，太少会浪费 CPU。

2️⃣ 中级调度（Medium-Level Scheduling）—— 平衡调度 / 内存调度

目标：根据内存状态，决定哪些进程可以在内存中运行，哪些需要换出到外存。 对象：进程（Process）。 发生频率：中等（几秒到几分钟一次）。 执行者：操作系统内核。

🔍 核心功能：

• 选进程进出内存：当内存紧张时，将一些不活跃的进程（如长时间阻塞的进程）换出到 Swap 分区；当内存空闲时，再换回。
• 平衡系统负载：防止内存溢出，提高系统吞吐量。

3️⃣ 低级调度（Low-Level Scheduling）—— 进程调度 / CPU 调度

目标：决定哪个就绪队列中的进程/线程获得 CPU 执行权。 对象：进程或线程（内核级线程）。 发生频率：高（毫秒级，每几十到几百毫秒一次）。 执行者：操作系统内核 → 这是操作系统最核心的部分！

🔍 核心功能：

• 选进程分配 CPU：从就绪队列中选出下一个要运行的进程/线程。
• 执行上下文切换：保存当前进程上下文，恢复新进程上下文。
• 实现公平与效率：通过调度算法（如 RR、优先级、MLFQ）保证所有进程都能得到 CPU 时间。

1
2
3
4
5
6
7
8

graph LR
    A[高级调度] -->|选作业进内存| B[中级调度]
    B -->|选进程进出内存| C[低级调度]
    C -->|选进程分配 CPU| D[CPU 执行]

    style A fill:#f9d5e5,stroke:#333
    style B fill:#e3eaa7,stroke:#333
    style C fill:#b2d3c2,stroke:#333

调度算法评价指标

七种调度策略

先来先服务 (First Come First Serverd, FCFS)

短作业优先 (Shortest Job First, SJF)

最短剩余时间优先 (Shortest Remaining Time First, SRTF)

最高响应比优先 (Highest Response Ratio First, HRRF)

优先级调度 (Priority Scheduling)

轮转调度 (Round Robin Scheduling, RR)

多级反馈队列调度 (Multi-Level Feedback Queue, MLFQ)

并发：互斥与同步

进程交互

为什么需要“进程交互”？

在单进程时代，程序是“独占”的——它不需要考虑别人。但在现代操作系统中：

• 多个进程/线程同时运行。
• 它们可能共享资源（如内存、文件、数据库连接）。
• 它们可能需要协同完成一个复杂任务（如一个 Web 请求涉及多个微服务）。

这就产生了两个根本性问题：

1. 竞争（Competition）：多个进程争抢同一个资源，导致结果不可预测。
2. 协作（Cooperation）：多个进程需要按特定顺序执行，才能完成共同目标。

✅ 进程交互就是解决这两个问题的机制。

竞争关系（进程互斥）

✅ 核心定义：

进程互斥是指若干进程因相互争夺独占型资源而产生的竞争制约关系。

📌 关键词解析：

• “相互争夺”：多个进程都想使用同一个资源。
• “独占型资源”：一次只能被一个进程使用的资源，如打印机、临界区代码、全局变量、数据库连接等。
• “竞争制约关系”：一个进程的执行会制约另一个进程的执行。

🧱 两个核心控制问题：

1. 死锁问题（Deadlock）
   • 定义：多个进程互相等待对方释放资源，导致所有进程都无法继续执行。
   • 经典例子：“哲学家就餐问题”——五个哲学家围坐圆桌，每人左右各有一根筷子。他们必须拿到两根筷子才能吃饭。如果每个人都拿起左边的筷子，然后等待右边的筷子，就会陷入死锁。
   • 四个必要条件：
     • 互斥条件
     • 请求与保持条件
     • 不剥夺条件
     • 环路等待条件
2. 饥饿问题（Starvation）
   • 定义：某个进程因为优先级低或资源分配策略不当，长时间得不到所需资源，导致无法执行。
   • 例子：在一个高优先级任务永远不结束的系统中，低优先级任务可能永远得不到 CPU。

协作关系（进程同步）

✅ 核心定义：

进程同步是指为完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。

📌 关键词解析：

• “完成共同任务”：多个进程/线程需要合作才能达成目标。
• “协调活动”：它们需要按特定顺序执行。
• “排定执行先后次序”：比如 A 必须在 B 之前执行。
• “等待、传递信号或消息”：通过同步机制（如信号量、条件变量、管道）实现通信和协调。

🧱 核心思想：

• “生产者-消费者”模型：生产者生成数据，消费者消费数据，它们必须同步。
• “读者-写者”模型：读者可以同时读，但写者必须独占。
• “屏障（Barrier）”：所有进程到达某个点后才能继续执行。

临界区管理

什么是“临界区”？

✅ 核心定义：

并发进程中，与共享变量有关的程序段叫做“临界区”（Critical Section）。

📌 关键词解析：

• “并发进程”：多个进程/线程同时运行。
• “共享变量”：多个进程都能访问和修改的变量（如全局变量、数据库连接、文件句柄）。
• “程序段”：一段代码，比如 counter += 1 这样的操作。

💡 简单说：临界区 = 操作共享资源的那一小段代码。

🎯 为什么重要？

因为这段代码如果被多个进程同时执行，会导致竞态条件（Race Condition），产生不可预测的结果。

如何避免错误？—— 互斥访问临界区

如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。

这就是“进程互斥”的核心思想。

临界区调度的三个原则（经典！）

这是解决临界区问题的黄金法则，任何同步机制都必须满足这三个条件：

✅ 原则 1：一次至多一个进程能够进入临界区内执行

互斥性（Mutual Exclusion）

• 这是最基本的要求。任何时候，最多只能有一个进程在临界区内。
• 如果 A 在临界区，B 就不能进入，必须等待。

✅ 原则 2：如果已有进程在临界区，其他试图进入的进程应等待

忙则等待（Progress）

• 如果临界区空闲，想进入的进程可以立即进入。
• 如果临界区被占用，其他进程必须等待，不能“自旋”浪费 CPU（虽然有些实现会自旋，但理想情况下应该阻塞等待）。

✅ 原则 3：进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入

有限等待（Bounded Waiting）

• 防止“饥饿”。不能让某个进程永远等下去。
• 例如，使用队列来管理等待的进程，确保每个进程最终都能获得进入临界区的机会。

实现临界区管理的软件方法一Peterson方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int turn;           // turn 表示轮到谁进入
boolean flag[2];   // flag[i] 表示进程 i 想进入临界区

// 初始化
flag[0] = flag[1] = false;

Process P0() {
    flag[0] = true;
    turn = 1;       // 谦让给 P1
    while (flag[1] && turn == 1); // 等待 P1 退出或谦让
    /* critical section */
    flag[0] = false;
    /* remainder section */
}

Process P1() {
    flag[1] = true;
    turn = 0;       // 谦让给 P0
    while (flag[0] && turn == 0); // 等待 P0 退出或谦让
    /* critical section */
    flag[1] = false;
    /* remainder section */
}

✅ 1. 互斥性 (Mutual Exclusion)

定义：一次至多一个进程能进入临界区。

📌 证明思路：

• 假设 P0 和 P1 同时进入临界区。
• 那么 flag[0] = true 且 flag[1] = true。
• 根据算法，P0 在进入前设置了 turn = 1，P1 设置了 turn = 0。
• 由于 turn 只能取值 0 或 1，不可能同时为 0 和 1。
• 所以，当 P0 检查 while (flag[1] && turn == 1) 时，如果 turn == 0，它就会阻塞。
• 同理，P1 也会被阻塞。
• 结论：不可能同时进入。

✅ 2. 空闲让进 (Progress)

定义：如果临界区空闲，且有进程想进入，则该进程应该能进入。

📌 证明思路：

• 如果 P1 不想进入临界区，则 flag[1] = false。
• 此时，无论 turn 是多少，P0 的 while (flag[1] && turn == 1) 条件都会失败（因为 flag[1] 是 false），所以 P0 可以立即进入临界区。

✅ 3. 有限等待 (Bounded Waiting)

定义：一个进程最多等待另一个进程执行完临界区一次，就能获得进入的机会。

📌 证明思路：

• 假设 P0 被阻塞，说明 turn = 1 且 flag[1] = true，即 P1 在临界区。
• 当 P1 执行完临界区后，它会设置 flag[1] = false。
• 此时，如果 P0 还想进入，它的 while 条件会失败，从而进入临界区。
• 如果 P1 在 flag[1] = false 后又想进入，则它会设置 flag[1] = true 和 turn = 0。
• 此时，P0 会被阻塞，但 P1 执行完后，P0 就能进入。
• 结论：P0 最多等待 P1 执行一次临界区，就能进入。

信号量与PV操作

信号量（Semaphore）

✅ 核心定义：

信号量是一种软件资源，用于表示物理资源的实体，是一个与队列有关的整型变量。

📌 关键词解析：

• “表示物理资源”：比如打印机、数据库连接池、线程池中的可用线程数。
• “整型变量”：信号量的值代表当前可用资源的数量。
• “与队列有关”：当资源不足时，等待的进程会被放入一个等待队列。

P/V 操作：信号量的“原子操作”

✅ 定义：

P (Proberen, 尝试) 和 V (Verhogen, 增加) 是对信号量进行操作的原语。

• P 操作：尝试获取资源。如果资源可用（信号量 > 0），则减 1；否则，进程进入等待队列。
• V 操作：释放资源。增加信号量值，并唤醒一个等待的进程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// P 操作 (Wait)
void P(semaphore s) {
    s.value = s.value - 1;
    if (s.value < 0) {
        // 资源不足，将当前进程加入等待队列并阻塞
        block(current_process);
    }
}

// V 操作 (Signal)
void V(semaphore s) {
    s.value = s.value + 1;
    if (s.value <= 0) {
        // 有进程在等待，唤醒一个
        wakeup(one_waiting_process);
    }
}

⚠️ 关键点：P/V 操作必须是原子操作（Atomic Operation），即在执行过程中不能被中断。否则会导致竞态条件。

哲学家进餐问题

哲学家进餐问题：核心描述

✅ 问题设定：

• 有 5 位哲学家 围坐在一张圆桌旁。
• 每位哲学家面前有一盘意大利面。
• 桌子上有 5 把叉子，每两位哲学家之间放一把。
• 哲学家的生活只有两件事：
  • 思考（Think）：什么都不做。
  • 吃饭（Eat）：必须同时拿到左右两边的叉子才能吃。
• 吃完后，会放下叉子，继续思考。

💡 目标：设计一个算法，让所有哲学家都能吃饱，且不会发生死锁或饥饿。

为什么会出现死锁？

📌 死锁的四个必要条件：

1. 互斥条件：叉子一次只能被一个人使用。
2. 请求与保持条件：哲学家拿起一把叉子后，会继续等待另一把。
3. 不剥夺条件：不能强行从哲学家手中拿走叉子。
4. 环路等待条件：每位哲学家都在等右边的人放下叉子，形成一个循环等待链。

解决方案：打破死锁的四个条件之一

要避免死锁，只需破坏其中一个必要条件即可。以下是几种经典的解决方案：

✅ 解决方案 1：限制同时就餐的哲学家数量（破坏“环路等待”）

最多允许 4 位哲学家同时吃面。

📌 原理：

• 如果只有 4 个人尝试拿叉子，那么至少有一把叉子是空闲的。
• 这样，总会有一个人能拿到两把叉子并吃完，从而释放资源。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import threading
import time

# 5 把叉子（信号量）
forks = [threading.Semaphore(1) for _ in range(5)]
# 限制同时就餐人数为 4
dining_room = threading.Semaphore(4)

def philosopher(i):
    while True:
        think()
        dining_room.acquire()  # 进入餐厅（最多 4 人）
        
        forks[i].acquire()       # 拿起左边叉子
        forks[(i + 1) % 5].acquire()  # 拿起右边叉子
        
        eat(i)
        
        forks[i].release()       # 放下左边叉子
        forks[(i + 1) % 5].release()  # 放下右边叉子
        
        dining_room.release()    # 离开餐厅

def think():
    time.sleep(0.1)

def eat(i):
    print(f"Philosopher {i} is eating...")
    time.sleep(0.1)

# 创建 5 个哲学家线程
threads = []
for i in range(5):
    t = threading.Thread(target=philosopher, args=(i,))
    threads.append(t)
    t.start()

for t in threads:
    t.join()

✅ 解决方案 2：奇偶号哲学家取叉子顺序不同（破坏“环路等待”）

奇数号哲学家先取左边叉子，再取右边；偶数号哲学家先取右边叉子，再取左边。

📌 原理：

• 这样就不会形成环路等待。
• 例如，哲学家 0（偶数）先拿右边叉子（叉子 1），哲学家 1（奇数）先拿左边叉子（叉子 1）→ 他们争抢同一把叉子，但最终只会有一个成功，另一个等待，从而打破环路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def philosopher(i):
    while True:
        think()
        
        if i % 2 == 0:  # 偶数号哲学家
            forks[(i + 1) % 5].acquire()  # 先拿右边叉子
            forks[i].acquire()             # 再拿左边叉子
        else:  # 奇数号哲学家
            forks[i].acquire()             # 先拿左边叉子
            forks[(i + 1) % 5].acquire()  # 再拿右边叉子
        
        eat(i)
        
        forks[i].release()                 # 放下左边叉子
        forks[(i + 1) % 5].release()      # 放下右边叉子

✅ 解决方案 3：拿起两把叉子才开始吃（破坏“请求与保持”）

每位哲学家必须同时拿到两把叉子才能开始吃，否则一把也不拿。

1️⃣ 全局变量定义

1
2
3
4
5
6
7

#define THINKING 0
#define HUNGRY   1
#define EATING   2

semaphore s[5];     // 用于阻塞哲学家的信号量
semaphore mutex = 1; // 互斥锁，保护 state 和 s
int state[5];      // 哲学家的状态

• s[i] 初始值为 0，因为一开始没有人需要等待。
• state[i] 初始化为 THINKING。

2️⃣ take_fork(int i) 函数

1
2
3
4
5
6
7

void take_fork(int i) {
    P(mutex);           // 获取互斥锁
    state[i] = HUNGRY;  // 哲学家 i 变成饥饿状态
    test(i);            // 尝试让 i 吃饭
    V(mutex);           // 释放互斥锁
    P(s[i]);            // 如果 test(i) 没有让 i 吃上饭，这里会阻塞
}

📌 关键点：

• state[i] = HUNGRY: 告诉“管家”，我饿了。
• test(i): “管家”检查我是否能吃。
  • 如果能吃，test(i) 会执行 V(s[i])，唤醒我。
  • 如果不能吃，test(i) 不做任何事。
• P(s[i]): 如果我没被唤醒，我就在这里阻塞，等待邻居放叉子。

✅ 这个函数是“非阻塞”的：它只负责声明“我饿了”，然后立即返回。真正的等待发生在 P(s[i])。

3️⃣ put_fork(int i) 函数

1
2
3
4
5
6
7

void put_fork(int i) {
    P(mutex);           // 获取互斥锁
    state[i] = THINKING; // 哲学家 i 变成思考状态
    test((i + 1) % 5);  // 检查右边邻居
    test((i + 4) % 5);  // 检查左边邻居（(i+4)%5 == (i-1)%5）
    V(mutex);           // 释放互斥锁
}

📌 关键点：

• state[i] = THINKING: 我吃饱了，不再占用叉子。
• test((i+1)%5) 和 test((i+4)%5): 告诉“管家”，我的邻居们可能现在可以吃饭了。
  • 例如，哲学家 0 放下叉子后，哲学家 1 和 4 可能现在能拿到两把叉子了。
  • “管家”会检查他们是否处于 HUNGRY 状态，并且邻居都不在吃，如果是，就唤醒他们。

4️⃣ test(int i) 函数 —— 核心逻辑！

1
2
3
4
5
6
7
8

void test(int i) {
    if (state[i] == HUNGRY &&
        state[(i + 1) % 5] != EATING &&
        state[(i + 4) % 5] != EATING) {
        state[i] = EATING;  // 可以吃了！
        V(s[i]);            // 唤醒哲学家 i
    }
}

📌 关键点：

• 检查三个条件：
  1. state[i] == HUNGRY: 我确实想吃饭。
  2. state[(i+1)%5] != EATING: 我右边的邻居没在吃。
  3. state[(i+4)%5] != EATING: 我左边的邻居没在吃。
• 如果都满足：说明我现在可以拿到两把叉子！
  • 设置 state[i] = EATING。
  • 执行 V(s[i])，唤醒我自己（因为我在 take_fork 中 P(s[i]) 阻塞了）。

✅ 这个函数是“原子”的：因为它在 mutex 保护下执行，不会被其他哲学家打断。

生产者消费者问题

mutex 的作用就是：

保护对共享变量（或临界区）的访问，
只在真正操作这些共享资源的前后“加锁”和“解锁”。

（防死锁铁律）：

永远不要在持有互斥锁（mutex）的情况下，调用可能阻塞的操作（如 P(empty)、P(full)、sleep、wait 等）。

什么是生产者-消费者问题？

这是一个经典的多线程同步问题，用于模拟现实中的“生产”与“消费”场景：

• 生产者 (Producer)：负责制造数据或产品。
• 消费者 (Consumer)：负责处理或消费这些数据/产品。
• 缓冲区 (Buffer)：一个有限大小的共享空间，用来暂存生产者的产品，供消费者取用。

📌 核心挑战

1. 互斥 (Mutual Exclusion)：多个生产者/消费者不能同时操作缓冲区的同一个位置，否则数据会错乱。
2. 同步 (Synchronization)：
   • 生产者不能在缓冲区满时继续生产（要等待）。
   • 消费者不能在缓冲区空时继续消费（要等待）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

item B[n];
Semaphore empty;  /*可用的空缓冲区个数*/
Semaphore full;   /*可用的产品数*/
Semaphore mutex;  /*互斥信号量*/
empty = n; full = 0; mutex = 1;
int in = 0; out = 0;  /*in为放入缓冲区指针, out为取出缓冲区指针*/

Process producer_i( ) {
    while(true) {
        item product = produce();
        P(empty);
        P(mutex);
        B[in] = product;
        in = (in+1) % n;
        V(mutex);
        V(full);
    }
}

Process consumer_i( ) {
    while(true) {
        P(full);
        P(mutex);
        Item product = B[out];
        out = (out+1) % n;
        V(mutex);
        V(empty);
        consume(product);
    }
}

问题：如果将P操作的顺序交换，会出现什么情况？

生产者霸占着 mutex 锁，等待 empty，消费者等待 mutex 锁，导致死锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

sequenceDiagram
    participant Producer as 生产者 P1
    participant Consumer as 消费者 C1
    participant Mutex as 互斥锁 (mutex)
    participant Empty as 空闲缓冲区 (empty)

    Note over Producer,Consumer: 初始状态: empty=0 (缓冲区满), mutex=1

    Producer->>Mutex: P(mutex) // 成功获取锁，mutex=0
    Producer->>Empty: P(empty) // empty=0，阻塞！等待空位...
    Note over Producer: 生产者 P1 霸占 mutex 锁，等待 empty

    Consumer->>Full: P(full) // full=1，成功，full=0
    Consumer->>Mutex: P(mutex) // mutex=0，阻塞！等待锁...
    Note over Consumer: 消费者 C1 等待 mutex 锁

    Note over Producer,Consumer: 💥 死锁！
    Note right of Producer: 我要等 empty (需 C1 消费)
    Note left of Consumer: 我要等 mutex (需 P1 释放)

问题：当前生产者消费者共用一个互斥锁会造成竞争

1
2
3
4

Semaphore pmutex, cmutex; // 两个独立的互斥锁
...
P(pmutex); // 生产者只锁自己的写入区域
P(cmutex); // 消费者只锁自己的读取区域

优势：

• 生产者之间：仍然需要 pmutex 来互斥，因为多个生产者可能同时想写入 in 指针指向的位置。
• 消费者之间：仍然需要 cmutex 来互斥，因为多个消费者可能同时想读取 out 指针指向的位置。
• 生产者 vs 消费者：它们可以并行！ 只要生产者在写一个位置，消费者在读另一个位置，两者互不干扰，完全可以同时进行。

死锁

死锁产生

什么是死锁

在多进程/多线程系统中，死锁是指两个或多个进程因竞争资源而造成的一种互相等待的现象，若无外力作用，它们都将无法向前推进。

简单说：A 等 B，B 等 C，C 又等 A，大家谁也不让步，结果全都卡住。

死锁的4个必要条件

只要系统发生死锁，以下4个条件必然同时成立。缺一不可！

1️⃣ 互斥访问 (Mutual Exclusion)

• 定义：系统中存在临界资源，进程应互斥地使用这些资源。
• 通俗解释：资源一次只能被一个进程使用。比如，打印机、文件、数据库连接、内存中的某个变量等。
• 为什么是必要条件？如果资源可以被多个进程同时共享（如只读文件），那就不存在竞争，也就不会死锁。

2️⃣ 占有和等待 (Hold and Wait)

• 定义：进程在请求资源得不到满足而等待时，不释放已占有的资源。
• 通俗解释：一个进程已经拿着一些资源，但它还需要其他资源才能完成工作，于是它一边等着新资源，一边还紧紧攥着自己手里的旧资源，不肯放手。
• 为什么是必要条件？如果一个进程在等待新资源时能主动释放旧资源，那么它就不会阻塞别人，死锁也就不会形成。

3️⃣ 不剥夺 (No Preemption)

• 定义：已被占用的资源只能由属主进程自愿释放，而不允许被其他进程剥夺。
• 通俗解释：资源一旦被某个进程拿走，除非它自己愿意还回来，否则谁也不能强行抢走。这保证了进程的“自主性”，但也为死锁埋下了隐患。
• 为什么是必要条件？如果系统能强行剥夺资源（比如操作系统强制回收），那么就可以打破死锁链。

4️⃣ 循环等待 (Circular Wait)

• 定义：存在循环等待链，每个进程在链中等待下一个进程所持有的资源，造成这组进程处于永远等待状态。
• 通俗解释：这是一个闭环。A 等 B 的资源，B 等 C 的资源，C 又等 A 的资源，形成了一个“等待环”。
• 为什么是必要条件？如果没有循环，等待链最终会指向一个“不等待”的进程，这个进程完成后会释放资源，从而解开整个等待链。

死锁防止

死锁避免

银行家算法

死锁检测和解除

资源分配图

• 阻塞节点 (Blocked Node)：一个进程，它正在请求一个或多个资源，但这些资源当前都被其他进程占用，且没有空闲实例可用。它必须等待。
• 非阻塞节点 (Non-blocked Node)：一个进程，它要么没有请求任何资源，要么它请求的资源当前有空闲实例可以立即满足。它可以继续执行。

如何通过资源分配图判断死锁？

✅ 死锁的充分条件（当资源类型只有一个实例时）

如果资源分配图中存在一个环，则系统一定发生死锁。

• 原因：在一个环中，每个进程都在等待下一个进程所持有的资源，而下一个进程又在等待再下一个……形成一个无限等待的闭环。

⚠️ 当资源类型有多个实例时

环的存在是死锁的必要条件，但不是充分条件。

• 原因：即使图中有环，但如果环中的某个资源类型有多个实例，那么可能还有空闲实例可以满足某个进程的需求，从而打破死锁。

资源分配图的简化

死锁检测算法

与银行家算法的安全性检测类似

存储管理

内存是什么？

从物理上讲，内存通常指的是随机存取存储器（RAM - Random Access Memory）。

从操作系统的角度来看，内存是CPU（大脑）和硬盘（仓库）之间的“高速中转站”。它是计算机暂时存放数据的地方，用来存储当前正在运行的程序和正在处理的数据。

存储层次结构

计算机的存储设备像一个金字塔，越往上速度越快、价格越贵、容量越小：

1. 寄存器 (Registers): 在 CPU 内部，极快，容量极小（纳秒级）。
2. 高速缓存 (Cache): 在 CPU 旁边，非常快（L1/L2/L3）。
3. 内存 (Main Memory/RAM): 我们今天的主角，速度适中，容量适中。
4. 本地磁盘 (Local Disk): 机械硬盘或固态硬盘，慢，容量巨大（毫秒级）。

操作系统的任务： 主要是管理第3层（内存），并负责在内存和磁盘之间搬运数据。

逻辑地址和物理地址

逻辑地址 (Logical Address)

• 别名： 虚拟地址 (Virtual Address)。
• 谁生成的？ CPU（在执行程序时）。
• 是什么？ 这是程序“眼中”的地址。
  • 当程序员写代码或者编译器编译程序时，它们看到的都是逻辑地址。
  • 程序觉得：“我拥有从 0 到 Max 的一整块连续内存。”

物理地址 (Physical Address)

• 谁看到的？ 内存条（硬件）。
• 是什么？ 这是数据在内存条上真正的“门牌号”。
  • 它对应着内存芯片中某个具体的存储单元。
  • 只有操作系统和硬件知道数据真正藏在哪里。

内存复用方式

为了支持多道程序设计（让电脑同时跑微信、浏览器、游戏），内存必须被复用。复用只有两种基本手段：

1. 切大块（按照分区复用）：
   • 把内存切成几个大块（分区）。
   • 规矩： 一个程序必须完整地塞进一个分区里（连续存放）。
2. 切碎块（按照页框复用）：
   • 把内存切成无数个一样大的小格子（页框）。
   • 规矩： 一个程序可以被切碎，散落在多个页框里（离散存放）。

四大具体方法

这张图非常精彩，它展示了从“逻辑空间”（你以为的样子）到“物理空间”（实际的样子）的四种映射路径。请看着图中的 ①、②、③、④。

1. 路径 ①：单连续/分区存储管理 (The “Old School”)

• 逻辑上： 程序认为自己是一条连续的直路（单连续逻辑地址空间）。
• 物理上： 放入“分区”（Partition）。
• 解释：
  • 这是最原始的方法。程序多大，就在内存里找个多大的坑填进去。
  • 缺点： 必须连续。如果你有 100MB 内存，中间断断续续空了 50MB，但没有一块连续的 50MB，那 50MB 的程序就跑不起来。这叫“外部碎片”。

2. 路径 ②：页式存储管理 (Paging - 现代主流的基础)

• 逻辑上： 程序依然认为自己是一条连续的直路（单连续逻辑地址空间）。
• 物理上： 放入“页框”（Page Frames）。
• 变化：
  • 虽然程序觉得自己是连续的，但操作系统偷偷拿把剪刀，把程序切成标准大小的“页”，然后随便塞进内存里任意位置的“框”里。
  • 优点： 彻底解决了“必须连续”的问题。内存利用率极高。

3. 路径 ③：段式存储管理 (Segmentation - 符合人类直觉)

• 逻辑上： 程序认为自己是由不同的“功能块”组成的（多连续逻辑地址空间/段表）。
  • 比如：主程序段、数据段、栈段。
• 物理上： 放入“分区”。
• 解释：
  • 程序员喜欢这种方式。因为我们可以说：“把我的代码段设为只读，把数据段设为可写”。
  • 但是，每个段在物理内存里还是要占一块连续的地盘，所以依然会有碎片问题。

4. 路径 ④：段页式存储管理 (Segmented Paging - 集大成者)

• 逻辑上： 先分段（符合程序员视角，便于管理和保护）。
• 物理上： 再分页（符合硬件视角，便于内存利用）。
• 解释：
  • 这是最强形态。
  • 先把程序按逻辑分成“段”（比如代码段）。
  • 再把这个“段”切碎成“页”，丢进物理内存的“页框”里。
  • 结果： 既有了分段的逻辑优势（保护、共享），又有了分页的物理优势（没有碎片）。

存储管理的功能

地址转换 (Address Translation)

• 核心： 将逻辑地址映射为物理地址（又称重定位）。
• 方式： 分为静态重定位（装入时确定，不可动）和动态重定位（运行时确定，灵活）。

分配与去配 (Allocation & Deallocation)

• 核心： 掌管内存的“借”与“还”。
• 动作： 进程装入时分配空间并记录；进程撤离时回收空间并去配。

存储保护 (Storage Protection)

• 核心： 确保进程互不干扰，防止越界访问。
• 规则： 自己的随便用，共享的按权限用，别人的严禁用。

内存共享 (Sharing)

• 核心： 允许多个进程共同使用同一块内存区域（如公共代码库）。
• 目的： 提高内存利用率，支持进程协作。

内存扩充 (Expansion)

• 核心： 利用磁盘空间“欺骗”程序，实现虚拟内存。
• 技术： 对换（整进整出）与虚拟技术（部分装入，按需调页）。

一句话总结： 操作系统通过转换地址让程序能跑，通过分配回收管理空间，通过保护防止打架，通过共享节省资源，通过扩充让小内存跑大程序。

连续分配管理方式 (Continuous Allocation)

核心定义

所谓“连续”，就是一个程序在物理内存中必须占据一块连在一起的地盘。

• 就像一群人去电影院看电影，必须买连座票，中间不能断开。

连续分配主要经历了三个阶段的进化，我们重点掌握后两个：

第一阶段：单一连续分配 (Single Continuous Allocation)

• 这是什么： 整个内存只有你（操作系统）和我（用户程序）两个人。
• 情况： 内存分为系统区和用户区。用户区一次只能跑一个程序。
• 结局： 这种方式太浪费了（如果你只有 10MB 程序，却占用了 8GB 内存），现代通用操作系统已经不用了。我们直接跳过。

第二阶段：固定分区分配 (Fixed Partitioning)

为了能多道程序并行，我们开始切蛋糕。

• 做法： 系统启动时，就把内存切成若干个固定大小的区域（分区）。这些格子的大小一旦切好，就不能变了。
• 两种切法：
  1. 分区大小相等： 比如全是 10MB 的格子。
  2. 分区大小不等： 有小的（4MB）、中等的（8MB）、大的（16MB），这样更灵活。
• 问题（致命伤）：内部碎片 (Internal Fragmentation)
  • 假设有一个分区是 10MB。
  • 你的程序只有 6MB。
  • 虽然程序装进去了，但剩下的 4MB 被锁在这个分区里，别的程序进不来，你也用不了。这就叫内部碎片（在分区内部浪费的空间）。

第三阶段：动态分区分配 (Dynamic Partitioning)

为了解决“内部碎片”，操作系统决定：现吃现切。

• 做法： 初始时内存是一整块。当程序 A 来了，它需要 5MB，我就切 5MB 给它；程序 B 来了要 10MB，我紧接着切 10MB 给它。
• 优点： 没有内部碎片！因为我是按需分配的，你需要多少我给多少。
• 问题（致命伤）：外部碎片 (External Fragmentation)
  • 随着时间推移，有的程序运行完走了（释放内存），内存里会留下一个个“坑”。
  • 比如：程序 B 走了，留下了 10MB 的空坑。
  • 这时来了一个 12MB 的新程序，它塞不进这个 10MB 的坑里。虽然内存里可能总共有 100MB 的空闲空间，但因为它们不连续（都是些碎小的坑），导致大程序跑不起来。这就叫外部碎片（在分区外部浪费的空间）。

“紧凑”技术 (Compaction)

操作系统不能看着这 16M 内存白白浪费。为了让 P5 跑起来，操作系统必须进行“内存搬家”，专业术语叫紧凑或拼接。

• 做法： 操作系统让现有的进程（P2, P4, P3）全部往上挪动，挤在一起。
• 效果：
  • 所有的空闲小坑（6M, 6M, 4M）会被“挤”到内存的最底部，汇合成一个 16M 的大坑。
  • 这时候，10M 的 P5 就可以舒舒服服地住进去了！

代价： “搬家”是非常耗时的。CPU 要暂停所有工作，疯狂地搬运数据（复制内存），这会严重拖慢电脑速度。这也解释了为什么以前的 Windows 98/XP 用久了要进行“磁盘碎片整理”（虽然那是磁盘，但原理类似，都是为了合并碎片）。

可变分区内存管理-分配算法

为什么需要分配算法？

因为“紧凑”（内存搬家）的代价太高了，会让电脑变卡。所以我们尽量通过聪明的分配算法，减少碎片的产生，不到万不得已不搬家。

以下是四种算法的详细解析：

1. 最先适应算法 (First Fit)

这是最简单、最自然的策略。

• 核心思想： 不管别的，按地址从低到高挨个找，找到第一个能装下的坑，就立刻分给它。
• 数据结构： 空闲分区表是按地址递增排列的。
• 优点：
  • 保留了大空间： 因为它总是先填低地址的坑，所以高地址的大片连续空间通常会被保留下来，有利于以后装入大作业。
• 缺点：
  • 忙闲不均： 低地址部分会被切得稀碎，用得很频繁；而查找时每次都从头开始，导致查找开销大，且低地址端充满了小碎片。

2. 下次适应算法 (Next Fit)

这是对“最先适应算法”的改良。

• 核心思想： 既然每次从头找太累，那就从上次分配结束的位置开始往下找。找到队尾如果还没找到，就绕回队头接着找（循环扫描）。
• 优点：
  • 速度快： 缩短了平均查找时间。
  • 均衡： 内存里的每个坑被选中的概率差不多，空间利用更均衡。
• 缺点（致命）：
  • 因为它把内存里的“大坑”都截断用了，导致缺乏大的连续空间。如果有大作业来了，可能反而找不到足够大的地盘了。

3. 最优适应算法 (Best Fit)

听名字觉得是最好的，其实通常是最烂的。

• 核心思想： 扫描整个内存，找到能装下该进程、且大小最接近（最小）的那个坑。
  • 比如你要 5MB，有一个 6MB 的坑和一个 20MB 的坑，它会选 6MB 的那个。
• 数据结构： 为了找得快，通常把空闲分区按大小递增顺序排列。
• 优点：
  • 它确实不想浪费大空间，尽量保留了大分区给大作业用。
• 缺点：
  • 制造碎片： 每次切完后，剩下来的那点空间（比如 6MB 切走 5MB，剩 1MB）实在太小了，谁也用不了。日积月累，内存里全是这种微小的、无法利用的外部碎片。

4. 最坏适应算法 (Worst Fit)

这是“最优适应”的反面。

• 核心思想： 每次都挑最大的那个坑给进程。
  • 比如你要 5MB，它偏偏要把那个 100MB 的大坑切给你。
• 数据结构： 空闲分区按大小递减顺序排列，这样查表时只要看第一个满不满足就行了。
• 优点：
  • 减少碎片： 切完剩下的一般还比较大（100MB 切走 5MB，剩 95MB），还可以继续给别的程序用。所以它对中小型作业非常有利。
• 缺点：
  • 大作业哭了： 最大的坑很快就被消耗掉了，真来了个超级大的程序，往往就没地方放了。

分页存储管理 (Paging Storage Management)

为什么要引入分页？

• 分区的痛： 程序必须完整地塞进连续的内存里。如果有 3 个 2MB 的小坑，想装一个 5MB 的程序，装不进去。
• 分页的药： 允许程序“打散”。把 5MB 的程序切成很多小块，分别塞进那 3 个 2MB 的坑里（甚至更小的坑），只要总空间够，就能跑。

核心思想： 逻辑上连续（程序看来是完整的），物理上不连续（内存里是散落的）。

三大概念

A. 页框 (Page Frame) —— 物理内存的“格子”

• 定义： 操作系统把物理内存切成一个个大小完全固定的块。
• 大小： 通常较小且是 2 的幂，比如 4KB（4096字节）。
• 编号： 从 0 开始编号，叫页框号或物理块号。
• 类比： 就像是一个巨大的药柜，里面全是大小一样的标准小抽屉。

B. 页面 (Page) —— 程序的“切片”

• 定义： 把用户的程序（逻辑地址空间）\也切成和页框*一模一样大小*的块。
• 编号： 从 0 开始编号，叫页号。
• 类比： 你把药材（程序）切成标准的小方块，每一块刚好能塞进一个抽屉。

C. 页表 (Page Table) —— 寻宝图

• 定义：既然程序被切碎散落在内存的各个角落，CPU 怎么知道程序的“第 1 页”在哪个“抽屉”里？
• 我们需要一张映射表，这就是页表。
• 内容： 记录了 逻辑页号 -> 物理页框号 的对应关系。

分页是如何解决碎片问题的？

没有“外部碎片”：

• 因为内存被切成了标准的 4KB 格子，程序也是 4KB 的块。只要内存里有空闲的格子，程序就能塞进去，完全不用担心“坑太小”的问题。

只有微小的“内部碎片”：

• 产生原因： 程序的最后一部分可能填不满一页。
• 例子： 页面大小是 4KB。你的程序是 4.1KB。
  • 第 1 页（4KB）填满。
  • 第 2 页（0.1KB）只占了一点点，剩下的 3.9KB 就是浪费的。
• 结论： 这种浪费主要发生在程序的最后一页，平均只有半页大小，相比于固定分区的浪费，这简直可以忽略不计。

分页存储管理的地址转换

TLB（快表）

1. 核心痛点：为什么要引入快表？

请看图，它指出了一个严重的问题：

• 页表放在哪里？ 放在内存中。
• 这就导致了一个尴尬的后果： 每次 CPU 想读取一个数据，必须访问两次内存。
  1. 第一次访问： 去查内存里的页表，把逻辑地址翻译成物理地址。
  2. 第二次访问： 根据物理地址，真正去取数据。

2. 解决方案：TLB (快表)

为了解决“慢”的问题，科学家发明了 TLB (Translation Look-aside Buffer)，中文叫快表或联想寄存器。

• 它是什么？ CPU 内部的一种极其快速、但容量很小的高速缓存。
• 它存什么？ 它存放当前最常访问的那一小部分页表项（Page # 到 Frame # 的映射）。
• 原理： 利用程序的“局部性原理”。如果你刚看了第 5 页，你很可能马上又要看第 5 页。

升级后的比喻：

• 你在手边放了一张小纸条（TLB）。
• 每次找书前，先看小纸条。如果纸条上有位置信息（TLB 命中），直接去拿书，不用跑去查目录了！

3. 加入 TLB 后的工作流程

请看图 的流程图，这是现在的标准动作：

1. CPU 发出请求： 逻辑地址（页号 $p$）。
2. 先查 TLB（快）：
   • 情况 A：命中 (Hit)
     • 直接拿到物理块号。
     • 耗时： 仅需 1 次内存访问（取数据）。
   • 情况 B：未命中 (Miss)
     • 没办法，只能老老实实去访问内存里的页表（慢）。
     • 拿到块号后，顺手把这一项存进 TLB（以备下次用）。
     • 耗时： 2 次内存访问。

分页存储空间的分配与去配

安全性问题： 怎么防止进程去访问不属于它的内存？

之前学的页表，只是告诉 CPU “第 X 页在第 Y 块”。但这里有个漏洞：如果一个程序只有 5 页，但恶意（或错误）代码试图去访问“第 6 页”，会发生什么？

为了防止这种越界访问，操作系统在页表的每一行后面加了一个小尾巴，叫 “有效-无效位” (Valid-invalid bit)。

1. 机制详解

• v (valid)：有效。表示这一页是合法的，确实在物理内存里，且属于当前进程。
• i (invalid)：无效。表示这一页不属于该进程（或者该页还在磁盘上没调入内存）。
• 后果： 如果 CPU 试图访问一个标记为 i 的页面，硬件会立即触发一个异常 (Exception/Trap)，操作系统会终止该进程或进行处理。

2. 图中的数学例子（非常重要）

让我们拆解一下图中的计算题，看看它是怎么判定“第 6 页”是非法的：

• 前提条件：
  • 页大小 = 2KB ($2^{11} = 2048$ 字节)。
  • 这意味着地址的低 11 位是偏移量。
• 进程需求：
  • 进程实际使用的地址范围是 0 ~ 10468。
• 计算需要多少页：
  • $$\frac{10468}{2048} \approx 5.11$$
  • 这意味着填满了第 0, 1, 2, 3, 4 页，并且第 5 页占用了一点点（0.11的部分）。
  • 所以，总共需要 0~5 号页（共 6 个页）。
• 查看页表状态：
  • 你看右边的页表，页号 0~5 的状态位都是 v（允许访问）。
  • 页号 6, 7 的状态位是 i（禁止访问）。
  • 如果程序试图访问地址 12287（属于第 6 页），MMU 检查到是 ‘i’，直接报错拦截。

管理问题： 操作系统怎么快速知道哪些物理格子是空的？

操作系统手里握着几千几万个物理页框，当新程序来的时候，怎么快速找到哪里有空位？位图 (Bitmap) 是最常用的方法。

1. 核心思想

• 用一串二进制位 (0和1) 来代表物理内存的格局。
• 每一位 (bit) 对应一个 物理页框。
• 映射规则：
  • 第 1 个 bit 对应 第 1 个页框。
  • 第 2 个 bit 对应 第 2 个页框…以此类推。

2. 状态表示

• 1： 表示该页框被占用。

• 0： 表示该页框空闲。

  (注：有些系统可能反过来，但根据这张PPT的文字“找出为 0 的那些位”，说明这里 0 代表空闲)

3. 分配算法流程

当一个程序需要申请 3 个页框时：

1. 扫描： 操作系统扫描这个位图，寻找哪里有 “0”。
2. 计算： 比如发现第 5、6、8 位是 0。
3. 计算页框号：
   • 发现第 $i$ 位是 0，那么对应的物理页框号就是 $i$（或者基于基址计算）。
4. 修改状态： 把这几位从 0 变成 1（标记为占用）。
5. 分配： 把算出来的物理页框号填到进程的页表里。

多级页表 (Multi-level Page Table)

1. 为什么要引入多级页表？(The Problem)

让我们做一个简单的数学计算：

• 在 32 位系统下，页面大小 4KB。

• 这意味着总共有 $2^{20}$ (约 100 万) 个页面。

• 如果每个页表项占 4 字节，那么一张完整的页表需要：

  $$100\text{万} \times 4\text{B} = \mathbf{4\text{MB}}$$

痛点：

1. 必须连续： 在单级页表中，这 4MB 的空间必须在物理内存中连续存放。
2. 难找： 在内存紧张时，很难找到一块完整的、连续的 4MB 空间给页表住。
3. 浪费： 很多程序其实只用了一点点内存，但为了维持结构，你不得不把这 100 万个坑位都建好（哪怕大部分是空的）。

解决方案：

把这 4MB 的大页表，也切成小块（页），散落在内存里！既然切碎了，就需要再建立一张表来管理这些碎块——这就是二级页表（页表的页表）。

2. 逻辑地址的重新划分

请看图，为了支持二级页表，逻辑地址被切得更碎了：

• 旧模式（单级）： 20位页号 ($p$) + 12位偏移 ($d$)。
• 新模式（二级）：
  • $p_1$ (10位)：一级页号（外层页号）。用来找“目录的目录”。
  • $p_2$ (10位)：二级页号（内层页号）。用来找“具体的页表”。
  • $d$ (12位)：页内偏移。保持不变。

为什么是 10 位？

$2^{10} = 1024$。每个页表项 4 字节。

$1024 \times 4\text{B} = 4\text{KB}$。

妙处： 这样切割后，每一张二级页表的大小刚好是一个页面 (4KB)！这让页表本身也可以完美地塞进普通的内存页框里。

地址变换过程 (The Walk)

请看图，这是一个“三步跳”的过程：

1. 第一跳（查目录）：
   • CPU 拿着 $p_1$，去查一级页表。
   • 得到结果：知道“这一段地址对应的二级页表”在内存的什么位置。
2. 第二跳（查页表）：
   • CPU 拿着 $p_2$，去刚才找到的那张二级页表里查。
   • 得到结果：终于拿到了真正的物理块号 (Frame #)。
3. 第三跳（取数据）：
   • 用物理块号 + 偏移量 $d$，去访问物理内存，拿到真正的数据。

优点：

• 离散存储页表： 页表不需要 4MB 连续空间了，可以打散放在各种角落。
• 节省空间： 如果一个程序只用了很小的内存，我们只需要建立“一级页表”和“少量二级页表”即可。其他的二级页表根本不用创建（或者可以留在磁盘上）。

缺点（如图片右上角文字所示）：

• 变慢了！
  • 单级页表：访存 2 次（查表+取数）。
  • 二级页表：访存 3 次（查一级+查二级+取数）。
  • 多级页表级数越多，访问越慢。

补救措施： 这就是为什么上一节讲的 TLB (快表) 极其重要！如果有 TLB，大部分时候我们直接能拿到结果，不需要走这漫长的三步跳。

分段存储管理

1. 为什么要分段？

请看图，这解释了分段的初衷：

• 程序员眼中的程序：
  • 程序员写代码时，不会认为程序是一堆 4KB 的碎片。
  • 我们认为程序是由不同的功能块组成的：比如 主程序 (main)、子程序 (subroutine)、栈 (stack)、变量数组 (array) 等。
• 分页的尴尬： 分页像碎纸机，可能把一个完整的函数切成两半，一半在第 1 页，一半在第 20 页。这让共享和保护变得很麻烦。
• 分段的解决： 保持逻辑完整。
  • 主程序 单独一段。
  • 栈 单独一段。
  • 数据表 单独一段。
  • 特点： 每个段的大小不固定（主程序可能 50KB，栈可能 1KB）。

黄金类比：

• 分页 像是把一本书的每一页撕下来，胡乱塞进一个个一样大的信封里。
• 分段 像是把书按“章”分开。第一章放一个文件夹，第二章放一个文件夹。有的章长，有的章短。

2. 逻辑地址的变化 (2D Address)

在分段管理中，地址不再是一维的线性的，而是二维的。

请看图 的底部：

• 逻辑地址 = 段号 (Segment Number) + 段内偏移 (Offset)
• 例子： “第 1 段 的 第 500 行”。

关键区别：

• 分页： 只要给出一个物理地址，机器自动切分。
• 分段： 用户（编译器）必须显式地指定“段号”和“段内偏移”。

3. 核心机制：段表 (Segment Table)

既然段的大小不固定，操作系统怎么管理呢？请看图。

我们需要一张段表，用来记录每个“章”在内存里的位置。因为每一章长度不一样，所以段表必须包含两列核心信息：

1. 段起始地址 (Base)： 这个段在物理内存是从哪里开始的？（比如从 6300 开始）。
2. 段长度 (Limit/Length)： 这个段到底有多大？（比如只有 400 大小）。
   • 注意：页表不需要记录“长度”，因为页表默认全是 4KB。但在分段中，这个长度至关重要！

4. 地址变换与保护 (The Translation & Safety)

这是分段管理最厉害的地方：越界保护。

我们模拟一次 CPU 访问（结合图 的数据）：

• 场景： CPU 要访问 段号 1，偏移量 500 的数据。

步骤：

1. 查表： 找到段表里的第 1 项。
2. 获取信息：
   • 基址 (Base) = 6300
   • 限长 (Length) = 400
3. 越界检查 (Critical Step)：
   • CPU 会拿你的偏移量 500 和 限长 400 比较。
   • 500 > 400，说明你试图访问这一段之外的地方！
   • 结果： 硬件直接拦截，抛出 “段错误” (Segmentation Fault)。这是编程时最常见的报错之一。
4. 正常情况： 如果偏移量是 100（小于 400），则物理地址 = $6300 + 100 = 6400$。

虚拟内存 (Virtual Memory)

1. 痛点：实存管理的问题

请看图，传统的实存管理（Real Memory Management）有一个硬性规定：

• 必须全部装入： 作业（程序）如果要运行，必须把它的全部信息一次性装入内存。
• 后果：
  1. 大程序跑不了： 程序的体积受限于物理内存的大小。
  2. 浪费资源： 其实程序里很多代码是很少用到的（比如“异常处理代码”、“巨大的未填满的数组”）。把这些一辈子都不一定跑一次的代码一直放在昂贵的内存里，是极大的浪费。

2. 解决方案：虚拟内存

虚拟内存的核心思想就是“欺骗”。

• 核心动作：部分装入 (Partial Loading)。
  • 操作系统不再把整个程序塞进内存，而是只把当前立刻要用的那几页装进去，剩下的留在硬盘上。
  • 程序运行到哪里，就动态地把哪里的数据从硬盘“拉”进内存（请求调页）。
  • 如果内存满了，就把暂时不用的数据“踢”回硬盘（页面置换）。
• 效果：
  • 逻辑 > 物理： 给用户提供一个比物理主存大得多的“虚拟主存”。
  • 以小博大： 8GB 的物理内存，可以流畅运行 20GB 的游戏，甚至可以同时运行总共 100GB 的多个程序。

3. 理论基石：局部性原理

你可能会问：“这样频繁地在内存和硬盘之间倒腾数据，电脑不会卡死吗？” 答案是：通常不会。因为程序运行有一个神奇的规律，叫“局部性原理”。

请看图，它解释了为什么我们敢“只装入一部分”：

1. 时间局部性 (Temporal Locality)：
   • 现象： 如果一条指令被执行了，那么不久之后它很有可能再次被执行。
   • 原因： 程序里充满了大量的循环 (Loop)。一旦进入循环，CPU 就会盯着这几行代码反复跑，完全不需要访问其他页面的代码。
2. 空间局部性 (Spatial Locality)：
   • 现象： 如果一个存储单元被访问了，那么它附近的单元也很有可能马上被访问。
   • 原因： 指令通常是顺序执行的；数据通常是聚集成群的（比如数组、表）。

结论： 在一段较短的时间内，程序实际上只需要访问极小一部分内存就能正常工作。所以我们完全可以把剩下的 90% 扔在硬盘里睡觉，而不影响运行速度。

如何实现虚拟内存技术

要实现虚拟内存，不能使用我们最早学的“连续分配方式”（因为要频繁地把一大块程序搬进搬出，效率太低且不仅能保证连续空间）。

因此，虚拟内存必须建立在离散分配（非连续分配）的基础上。

根据课件，实现虚拟内存主要有以下三个流派和两个核心“新技能”：

1. 三种实现方式

其实就是把你之前学的“基本款”升级为“虚拟款”：

2. 两个新增的核心功能

这是“虚拟系统”和“普通系统”最本质的区别。为了实现“空手套白狼”，操作系统必须具备两项新能力：

A. 请求调页/调段功能 (Demand Paging/Segmentation)

• 动作： “缺了就拿”。
• 描述： 在程序执行过程中，当 CPU 发现要访问的数据不在内存时（缺页），操作系统负责把所需的信息从硬盘（外存）调入内存，然后让程序继续执行。

B. 页面置换/段置换功能 (Page/Segment Replacement)

• 动作： “满了就扔”。
• 描述： 当内存空间不够的时候，操作系统负责利用某种算法，把内存中暂时用不到的信息（页面或段）换出到硬盘上，腾出地方给新进来的页面用。

页式虚拟存储管理

1. 核心思想：按需调入 (Demand Paging)

• 启动时： 操作系统只把进程的第一页（或者极少量的几页）装入内存，然后就让 CPU 开始跑。
• 运行时：
  • CPU 执行着执行着，发现要访问的下一行代码在“第 5 页”。
  • 一查页表，发现第 5 页不在内存里。
  • 动作： 暂停程序，去硬盘把第 5 页抓进来，然后继续跑。
• 地位： 这是现代 OS 的主流存储管理技术。

2. 基础设施升级：扩充页表 (Expanded Page Table)

为了支持这种“有的在内存，有的在硬盘”的复杂情况，原来的页表（只记录页号->块号）已经不够用了。我们需要给页表加很多“状态栏”。

请看图，现在的页表项变得很宽，包含了以下关键信息：

1. 驻留标识 (Present/Resident bit)： 最重要的一位。
   • 1: 表示该页在内存中（可以直接访问）。
   • 0: 表示该页在磁盘上（需要触发中断去调入）。
2. 写回标志 (Dirty/Modify bit)：
   • 记录这一页在内存里有没有被修改过。
   • 作用： 当这一页要被踢出内存时，如果是“脏”的（被改过），必须写回硬盘保存；如果是“干净”的，直接扔掉就行（硬盘里有原版），省了一次磁盘 IO。
3. 引用标志 (Reference bit)：
   • 记录这一页最近有没有被访问过。
   • 作用： 给置换算法参考。最近刚被用过的，最好别踢它（LRU 算法的基础）。

3. 核心机制：缺页中断 (Page Fault)

当 CPU 想要访问一个“驻留标识为 0”（不在内存）的页面时，就会触发缺页中断。这是虚拟内存运转的“引擎”。

1. CPU 访问： 给出逻辑地址。
2. 硬件检查： 发现页表里这一项显示“不在内存”。
3. 产生中断： 硬件立刻产生缺页中断，CPU 暂停当前进程，把控制权交给操作系统。
4. OS 处理 (关键分支)：
   • 情况 A（内存有空位）：
     • 直接从磁盘找到该页，读入空闲的页框。
     • 修改页表（把驻留位置 1，填入块号）。
   • 情况 B（内存满了）：
     • 执行页面置换算法，挑一个倒霉蛋（淘汰页）踢出去。
     • 如果那个倒霉蛋被修改过，先把它写回磁盘。
     • 把腾出来的空位给新页面用。
5. 恢复执行： 操作系统更新完页表后，重新执行刚才那条导致中断的指令。这一次，CPU 就能顺利找到数据了。

虚存地址转换过程

第一阶段：启动与分流

1. 地址分解 (Step 1)

• 动作： CPU 发出指令，MMU（内存管理单元）截获逻辑地址，自动把它切成两半：页号 ($p$) 和 页内偏移 ($d$)。

2. 查快表 (Step 2)

• 动作： 以页号 $p$ 为索引，先去查 CPU 内部的 快表 (TLB)。
• 耗时： $t_1$（非常短，纳秒级）。

第二阶段：三种可能的命运

命运一：快表命中 (TLB Hit) —— 极速模式

这是图中 (3) 的路径。

• 情况： 在 TLB 里直接找到了页号对应的物理块号。
• 结果：
  • 直接取出块号。
  • 拼接： 块号 + 偏移量 = 物理地址。
  • 访问数据： 去访问主存（耗时 $t_2$）。
• 总耗时： $t_1 (\text{查TLB}) + t_2 (\text{取数据})$。

命运二：快表未命中，但页表命中 —— 普通模式

这是图中 (4) -> (5) 的路径。

• 情况： TLB 里没找到（Miss），但MMU 去查内存里的 页表 时，发现该页在内存中（驻留位为 1）。

• 动作：

  1. 从页表中读出物理块号。
  2. 关键动作：装入快表 (Load TLB)。为了下次能快点，把这一项复制到 TLB 里。
  3. 形成物理地址，访问数据。

• 总耗时： $t_1 (\text{查TLB}) + t_2 (\text{查页表}) + t_2 (\text{取数据})$。

  (比命运一多了一次访存的时间)

命运三：缺页中断 —— 龟速模式

这是图中 (6) -> (7) -> (8) 的路径（红色箭头）。

• 情况： TLB 没找到，查内存页表发现也不在内存中（驻留位为 0，失效）。
• 动作：
  1. Step (6) 缺页中断： MMU 发出信号，CPU 暂停，操作系统接管。
  2. Step (7) 调页： 操作系统去 辅助存储器 (磁盘) 里把这一页找出来，读入内存。
     • 注意：这一步耗时是 $t_3$，通常是毫秒级，比前两种慢几万倍。
  3. Step (8) 装入/改表： 数据读进内存后，操作系统更新 页表 和 快表，把状态改为“在内存”。
• 结局： 重启指令，这次就会走“命运一”或“命运二”了。

缺页中断率 (Page Fault Rate)

怎么衡量虚拟内存效率高不高？就看缺页中断率 ($f$)。

• 公式：

  $$f = \frac{F}{S + F}$$
  • $F$: 缺页次数（去磁盘拿的次数）。
  • $S$: 成功在内存找到的次数。
  • 目标： 我们希望 $f$ 无限接近于 0。

• 影响 $f$ 的四大因素：

  1. 内存页框数： 给进程分的“房间”越多，缺页率越低。
  2. 页面大小： 页面越大，缺页率通常越低（因为一次拉进来更多数据），但浪费也可能变大。
  3. 页面替换算法： 算法越聪明（踢得越准），缺页率越低。
  4. 程序特性： 这不仅是 OS 的事，也是程序员的事！

页面调度算法

最佳页面调度算法(OPT, OPTimal replacement)

先进先出页面调度算法(FIFO, First-In First-Out replacement)

Belady异常

为什么会发生这种事？

Belady 异常的根本原因在于 FIFO 算法的“无脑”。

• FIFO 的逻辑： 只看进入内存的时间，谁来得早谁滚蛋。
• 问题所在： 它完全不考虑页面的使用频率或访问模式。
  • 在上面的 4 页框例子中，4 和 3 是经常要被访问的热门页面。
  • 但是因为它们进来得早，FIFO 总是优先把它们踢出去。
  • 当页框变多时，页面的驻留时间变长了，队列的结构变了，导致原本能“巧合”命中的页面（比如在3页框时，踢出的顺序刚好避开了马上要用的页），在4页框时反而被“精准”地踢出去了。

最近最少使用页面调度算法(LRU, Least Recently Used replacement)

最不常用页面调度算法(LFU, least frequently used)

时钟页面调度算法(Clock, Clock policy replacement)

1. 核心道具 (The Setup)

要玩转这个算法，需要三个关键道具：

1. 环形队列 (Circular Queue)：
   • 把内存里的所有页面首尾相连，排成一个圆圈，就像钟面一样。
2. 表针 (Pointer)：
   • 有一个指针，指向当前要检查的那个页面（下一号淘汰候选人）。
3. 引用标志位 (Reference/Use Bit)：
   • 每个页面都有一个标志位。
   • 1 = 最近被访问过（免死金牌）。
   • 0 = 最近没被访问（可以杀）。

2. 算法规则：给一次“改过自新”的机会

Clock 算法的核心逻辑就是“二次机会” (Second Chance)。

当内存满了，需要踢人时，指针开始顺时针扫描：

• 情况 A：遇到标志位是 1 的页面
  • 动作： 操作系统心软了。它把标志位改为 0（没收免死金牌），然后指针移向下一页。
  • 潜台词： “我看你最近刚被用过，这次先不杀你，但我把你的牌子没收了。如果下次我转回来你还没被访问，那你就在劫难逃了。”
• 情况 B：遇到标志位是 0 的页面
  • 动作： 操作系统不客气了。直接淘汰这个页面！
  • 后续： 把新页面装进这个坑位，把标志位置为 1，指针移向下一页。

段式虚拟存储管理

如果有需要再学

设备管理

设备控制方式

为什么要有设备控制方式

1. 巨大的速度鸿沟 (The Speed Gap)

这是最根本的原因。

• CPU：是电子设备，运算速度以纳秒 (ns) 计，一秒钟能执行几十亿次指令。
• I/O设备：大多包含机械部件（如硬盘磁头转动、打印机喷墨），速度以毫秒 (ms) 甚至秒计。

差距有多大？ 如果把 CPU 比作一列高铁（时速 300公里），那 I/O 设备就像是一只蜗牛。 如果没有优化的“控制方式”（比如让 CPU 傻等的轮询方式），就相当于让高铁停下来等蜗牛爬过铁轨。这简直是暴殄天物，极大地浪费了昂贵的 CPU 资源。

所以，设备控制方式的演进，本质上就是为了不让高铁等蜗牛。

2. 实现“并行操作” (Parallelism)

操作系统的核心目标之一是效率。我们希望计算机能同时做多件事。

• 没有好的控制方式时：CPU 必须亲自指挥设备每一个动作。CPU 在忙 I/O 的时候，就不能做计算；做计算的时候，就不能管 I/O。这是串行的。
• 有了好的控制方式（如 DMA、通道）：
  • CPU 说：“你去把电影拷贝一下。”（发指令）
  • CPU 转头去运行游戏逻辑。（做计算）
  • 设备控制器自己在旁边慢慢拷贝电影。（做 I/O）

这就是CPU 与设备的并行。只有通过先进的设备控制方式，才能把 CPU 从繁琐的搬运工作中解放出来，让它去处理更有价值的逻辑运算。

3. 屏蔽设备的复杂性 (Abstraction)

世界上的设备千奇百怪：鼠标、键盘、显卡、网卡、打印机、VR眼镜……

• 它们的物理原理完全不同。
• 它们的数据格式完全不同。

如果让 CPU 直接去控制每一个物理细节（比如控制硬盘电机转几圈、控制打印机喷头往哪喷），CPU 的指令集会变得无比复杂，且操作系统无法通用。

设备控制方式（配合硬件控制器）起到了一层“翻译”和“管家”的作用：

• CPU 只需要下达统一的命令（读、写）。
• 具体的脏活累活（如何控制电压、如何校验数据、如何按顺序传输）交给设备控制器和控制逻辑（如 DMA 控制器）去完成。

四者之间差异在于：CPU和设备并行工作的方式和程度不同。

轮询（Polling）

流程解析：

1. 发出命令：CPU 告诉设备（控制器）“我要读数据”。
2. 读状态：CPU 紧接着去读设备的状态寄存器。
3. 检查状态（关键点）：
   • 如果设备“未就绪”（还在忙着准备数据），CPU 顺着红色箭头跳回去，再次读取状态。
   • CPU 会一直在“读状态 -> 检查 -> 未就绪 -> 读状态”这个圈里打转。
4. 读写数据：只有当设备终于显示“就绪”了，CPU 才会跳出循环，亲自把数据读进来。

核心特点：CPU 全程陪跑 (CPU 全程参与)

忙等 (Busy Waiting)：

• 这就是上面说的那个“死循环”。在设备准备数据的这段时间（对于 CPU 来说极其漫长），CPU 没有去干别的更有意义的事，而是像个复读机一样一直问“好了没？”。
• 结果：CPU 的利用率被严重拉低。

串行工作：

• PPT 文字提到：“在设备接受 I/O 命令之前处理器不能执行其他操作”。
• 这意味着 计算任务 和 I/O 任务 是完全串行的（排队做）。CPU 不能在设备忙的时候去算别的题。

中断驱动方式 (Interrupt-Driven I/O)

当设备准备好了（状态变为“就绪”），控制器会向 CPU 发送一个电信号，这个信号就叫中断。

CPU 的反应：

1. 收到信号，暂停当前正在做的工作（保存现场）。
2. 跳到 “中断处理程序”（流程图中的黄色框）。
3. 传送数据：CPU 亲自把数据从设备搬运到内存。
4. 恢复：搬运完后，CPU 回到刚才暂停的地方继续工作。

直接存储器访问（DMA, Direct Memory Access）

图展示了 DMA 模块的内部结构，这解释了它是如何独立工作的：

• 地址寄存器：记住了数据要搬到内存的哪个位置。
• 数据计数：记住了还有多少数据要搬。
• 控制逻辑：负责指挥总线进行读写。
• 关键点：CPU 一旦把这些寄存器填好，DMA 就拥有了工作的全部信息，不再需要 CPU 指导。

CPU -> DMA（下达命令）：

• CPU 告诉 DMA：“把硬盘里这 1MB 数据搬到内存地址 X。”

继续执行后续指令（红色虚线）：

• 关键时刻：CPU 下完命令直接走人，去处理其他进程。
• 与此同时，DMA 控制器接管总线，一车一车地往内存搬数据。这是真正的并行！

中断（最后一步）：

• 只有当这 1MB 数据全部搬完了，DMA 才会发一个中断信号告诉 CPU：“老板，活干完了。”

什么是“周期窃取”？

“DMA 和 CPU 同时通过总线访问内存，CPU 会把总线的占有权让给 DMA 一个/几个主存周期”。

形象理解：

• 总线 (Bus) 就像是一条独木桥。内存是桥对面的仓库。
• CPU 是一个一直在过桥搬东西的人。
• DMA 是另一个也要过桥搬东西的人。
• “周期窃取”：当 DMA 需要搬运一个数据字时，它不会把 CPU 彻底赶走，而是趁着 CPU 正在思考（译码）或者还没上桥的间隙，“偷” 用一下这个桥（总线周期），快速搬运一个字，然后立马把桥还给 CPU。

图中的方框（取指令、译码、取操作数…）代表 CPU 执行一条指令的各个微步骤。

中断断点 (最右侧)：请看最右边的箭头。中断是非常“讲礼貌”的。它必须等到 CPU 把当前这条指令完全执行完（存结果之后），才会去响应中断。

DMA 断点 (中间的箭头)：请看指向“译码”和“取操作数”之间的那个箭头。DMA 是“急脾气”。它不需要等指令执行完。只要 CPU 当前这个微操作（比如译码）不占用总线，DMA 就可以见缝插针地插入进来，偷一个周期传数据。

结论：DMA 的响应速度比中断快得多，因为它不需要等指令结束。

为什么“窃取”不会严重拖慢 CPU？

Cache 的功劳：PPT 最后一行提到“CPU 大部分情况下与 Cache 进行数据交换”。CPU 也就是在这一瞬间不能访问主存（内存），但它依然可以访问Cache（高速缓存）。只要 Cache 里有数据，CPU 就算没了总线也能继续干活，完全感觉不到 DMA 在偷东西。

不连续性：DMA 只是偶尔偷一个周期，而不是长时间霸占，所以对 CPU 的宏观影响很小。

三种方式对比

• ① 轮询方式: CPU需要主动等待设备就绪，并且全程参与内存数据的交换。
• ② 中断方式: CPU无需主动等待设备就绪。当设备准备好后，会向CPU发送一个中断信号，CPU响应中断后再参与内存数据交换。
• ③ DMA方式: CPU只在I/O操作开始前和结束后参与（例如，初始化DMA控制器），在实际的数据传输过程中，由DMA控制器直接在内存和设备间搬运数据，CPU完全不参与主存数据交换。

从轮询到中断再到DMA，CPU的效率越来越高，它能更早地从I/O等待中解放出来去执行其他任务，从而提高了系统的并行处理能力。然而，这种并行仅限于物理层面的I/O操作，即CPU和I/O设备可以同时工作，而不是指CPU内部或软件层面的并行计算。

通道控制方式 (Channel Control)

1. 核心定义：什么是“通道”？

• 别名：它又被称为 I/O 处理器 (I/O Processor)。
• 地位：它不再是一个简单的硬件控制器，而是一个“弱智版 CPU”。
• 能力：它拥有执行逻辑独立 I/O 任务的能力。这意味着它不仅仅能“搬运”，还能做简单的“决策”（比如：先读这个，再写那个，如果错了重试）。

2. 核心机制：通道程序 & 四级连接

这里有两个关键概念需要理解：

A. 通道程序 (Channel Program)

PPT 提到，处理器不再执行具体的 I/O 指令，而是“在主存中组织通道程序”。

• DMA 方式：CPU 给的是参数（源地址、目的地址、数据量）。
• 通道方式：CPU 给的是一段代码（通道程序）。
  • 比喻：
    • DMA：老板说“把这堆砖搬到后院”。
    • 通道：老板写了一张任务清单：“1. 先把砖搬到后院；2. 然后去买水泥；3. 最后把墙砌好。” 通道拿着这张清单，自己去执行一系列复杂的动作，不需要老板再插手。

B. 四级连接 (Four-level Connection)

PPT 中提到了 “处理器、通道、控制器、设备” 的四级连接。

• 这是一个层级管理结构：
  • CPU 指挥 通道。
  • 通道 指挥 设备控制器。
  • 设备控制器 控制 设备。
• 目的：一个通道可以控制多台设备，大大节省了 CPU 的接口资源。

3. 工作流程：高度并行 (High Parallelism)

详细展示了工作步骤，这里有几个考试常考的缩写：

1. CPU 启动：
   • CPU 遇到 I/O 任务。
   • OS 组织好通道程序，把这个程序的地址放在 CAW (Channel Address Word，通道地址字) 中。
   • CPU 启动通道，然后立即走人（去干别的事）。
2. 通道执行：
   • 通道从 CAW 里拿到清单（通道程序），开始指挥设备干活。
   • 此时，CPU 和 通道 真正实现了“高度并行”。
3. 结束汇报：
   • 活干完了，通道发出中断。
   • CPU 响应中断，从 CSW (Channel Status Word，通道状态字) 中读取执行情况（比如是成功了还是出错了）。

总线与I/O

什么是总线

从慢吞吞的键盘到快如闪电的显卡，它们都需要和 CPU 或内存交换数据。总线就是它们共同行走的通道。

想象计算机的主板是一个繁忙的城市。

• CPU、内存、硬盘、网卡 就是城市里的建筑物。
• 总线 就是连接这些建筑物的主干道。
• 数据 就是路上跑的车辆。

总线的三大组成部分：

1. 数据总线 (Data Bus) —— 运货车
   • 作用：用来传输实际的数据（比如你的文档内容、游戏画面）。
   • 特点：是双向的（能发能收）。路越宽（比如 32位、64位），一次能拉的货就越多。
2. 地址总线 (Address Bus) —— 导航员
   • 作用：用来告诉大家“我要去哪里”。比如 CPU 要读内存，必须先通过地址总线广播：“我要找 0x0012 号房间的数据”。
   • 特点：通常是单向的（由 CPU 发出）。
3. 控制总线 (Control Bus) —— 红绿灯/交警
   • 作用：用来指挥交通。比如发送“读”、“写”、“中断”或“请求占用总线”的信号。
   • 关联：刚才我们学的 “DMA 周期窃取”，其实就是 DMA 通过控制总线向 CPU 申请：“把路权借我用一下”。

解决 I/O 速度不匹配问题

这里的“不匹配”体现在两个维度：

• I/O 和 CPU 的不匹配：CPU 是光速运行的，而 I/O 设备相对较慢。
• 各设备之间的不匹配：这是这张图的重点。键盘和显卡虽然都是 I/O 设备，但它们的速度简直是云泥之别。

总线概念结构

单总线结构模型 (Single Bus Structure Model)

• 一条总线：中间那根橙色的双向大箭头。
• 全员接入：CPU、主存（内存） 和所有的 I/O 模块 都直接挂在这同一根线上。

这意味着什么？ 这意味着 CPU 想和内存说话，要走这条路；硬盘想把数据传给内存，也要走这条路。大家共享这一条通信通道。

优点：简单粗暴

1. 结构简单：硬件设计非常容易，成本低。
2. 易于扩充：这是最大的好处。如果你想加一台打印机，只需要把它“挂”在总线上就行，不需要改动 CPU 或内存的架构。就像在路边盖新房子一样容易。

缺点：致命的“堵车”

这种设计在早期计算机中很流行，但随着设备越来越多，它的弊端完全暴露出来：

• 共用总线导致压力大：
  • 因为只有一条路，同一时刻只能有一组对话。如果硬盘正在传电影，CPU 就不能读内存，必须干等。这就构成了瓶颈。
• 传输时延长：
  • 设备多了，大家都要申请路权，排队时间自然变长。
• 最痛的点：慢速外设占用带宽多：
  • 这是单总线最大的硬伤。
  • 比喻：想象这是一条单车道高速公路。如果前面有一辆拖拉机（慢速 I/O 设备）在慢慢开，后面性能再好的法拉利（CPU/内存）也得跟在屁股后面慢慢爬。
  • 这就导致了高速设备的性能被低速设备严重拖累。

三级总线模型 (Three-level Bus Model)

第一级：局部总线 (Local Bus) —— “VIP 专用通道”

• 位置：最上方，连接 CPU 和 Cache (高速缓存)。
• 作用：这是系统中最快的一条路。
• 意义：CPU 和 Cache 之间的交互极其频繁且速度极快。把它们单独划在这个“小圈子”里，让 CPU 能全速运行，完全不受外界打扰。

第二级：主存总线 (System Bus) —— “城市主干道”

• 位置：中间层，连接 主存 (Main Memory)、Cache 和 局部 I/O 控制器。
• 作用：负责内存数据的吞吐。
• 意义：当 Cache 没命中时，需要从主存调数据，就走这条路。它比局部总线慢一点，但依然很快。

第三级：扩展总线 (Expansion Bus) —— “社区辅路”

• 位置：最下方，连接各种 I/O 设备（如 LAN网卡、SCSI设备、打印机等）。
• 作用：专门用来挂载各种速度参差不齐的外设。
• 关键组件：扩展总线接口 (Expansion Bus Interface)。它是连接“主干道”和“辅路”的立交桥/收费站。它不仅负责传递数据，还起到缓冲的作用，防止慢速设备的信号干扰高速总线。

优点：各行其道

分流 (Isolation)：

• “主存与 I/O 之间的数据传送” 和 “处理器的内存活动” 被分离开了。
• 简单说：硬盘往内存传数据（走扩展总线 -> 主存总线）的时候，CPU 依然可以在局部总线上和 Cache 玩得很开心，互不影响。

扩展性强：

• “支持更多的 I/O 设备”。因为有了扩展总线这一层，你可以挂很多慢速设备，而不会增加主存总线的负载（电容负载）。

缺点：木桶效应

PPT 也提到了一个缺点：“不适用于 I/O 设备数据速率相差太大的情形”。

• 解读：你看最下面的“扩展总线”，上面既挂了高速的 LAN (网卡)、SCSI (高速硬盘接口)，又可能挂慢速的 字符设备 (键盘/鼠标)。
• 如果所有外设都挤在这一根扩展总线上，高速设备（如千兆网卡）可能会觉得这条路太慢，或者被慢速设备抢占时隙，导致性能发挥不出来。
• 解决思路：这就是为什么现代电脑（如你现在的 PC）其实演进到了更高级的结构（如 桥接芯片组架构，分为北桥和南桥，或者现在的 PCH），把高速 I/O (PCIe) 和低速 I/O (USB) 进一步分开。

南北桥架构” (Northbridge and Southbridge Architecture)

核心理念：快慢彻底分家

PPT 顶部的文字点出了核心思路：“通过存储总线、PCI总线、E(ISA)总线分别连接主存、高速I/O设备和低速I/O设备”。

• 为什么要分南北？
  • 有些设备太快（内存、显卡），必须贴着 CPU 跑。
  • 有些设备太慢（鼠标、键盘），离 CPU 远点没关系。
  • 于是，主板芯片组被劈成了两半：北桥负责快，南桥负责慢

北桥 (Northbridge) —— 速度担当

地位：它是离 CPU 最近的芯片（通常在主板上方，故称北桥）。

• 别名：PPT 中标注为 “主存控制器” (Memory Controller)。
• 连接对象（贵族圈）：
  1. CPU：通过“处理器总线”直接连接，带宽最高。
  2. 主存 (RAM)：通过“存储总线”连接。这是北桥最重要的任务——管理内存读写。
  3. 高速 I/O 设备：PPT 中展示了 图形设备 (显卡)、SCSI (服务器硬盘)、LAN (网卡) 挂接在 PCI 总线 上。虽然 PCI 总线在物理上通常由南桥管理或作为南北桥的桥梁，但逻辑上它们属于高速区，需要通过北桥与 CPU 高速交换数据。

南桥 (Southbridge) —— 管家担当

地位：离 CPU 较远（通常在主板下方，故称南桥）。

• 别名：PPT 中标注为 “I/O 控制器”。
• 连接对象（平民圈）：
  1. 低速 I/O 设备：PPT 下方展示的 COM 口、鼠标、键盘。
  2. 慢速总线：这些设备挂在 E(ISA) 总线 上。这是一种非常古老且缓慢的总线标准。
• 职责：南桥负责处理这些琐碎、慢速的输入输出，整理好之后，再通过“桥间接口”统一汇报给北桥。

关键接口：桥间接口 (Hub Interface)

请看图中连接北桥和南桥的那根竖线——“桥间接口”。

• 这是连接“CBD”和“郊区”的高速公路。
• 所有的鼠标点击、键盘输入，都要先汇聚到南桥，通过这个接口传给北桥，最后才能到达 CPU。

北桥：负责 CPU总线、存储总线（内存）以及 PCI总线（高速 I/O，如显卡、网卡）。

南桥：负责 E(ISA)总线（慢速 I/O，如键盘、鼠标），并通过桥间接口与北桥通信。

优点：支持不同速率 (Heterogeneity)

PPT 明确指出了这种架构的优点：“可以支持不同数据速率的 I/O 设备”。

• 各司其职：
  • CPU 想读内存，直接找北桥，路径极短，速度极快。
  • CPU 想读鼠标，指令传给南桥，南桥慢慢去读，不会占用北桥的高速通道。
• 消除瓶颈：慢速的 ISA 设备再多，也不会拖慢 CPU 访问内存的速度，因为它们在物理上被隔绝在南桥下面了。

第一梯队（最快）：北桥负责

• 不仅仅是内存：你说得对，北桥不仅连接主存，还连接了 图形设备 (显卡)。显卡是 I/O 设备中对速度要求最高的（比如打游戏时的数据吞吐量极大），所以它被提拔到了“北桥”这个 VIP 区域，直接和 CPU、内存享受高速通道。

第二梯队（较快）：PCI 总线

• LAN (网卡) 和 SCSI (硬盘) 挂在 PCI 总线 上。这是一条高速公路，专门给这些吞吐量大的设备跑。

第三梯队（慢速）：南桥负责

• 鼠标、键盘 被赶到了最下面的 E(ISA) 总线，由 南桥 统一管理。
• 南桥像一个过滤器，把这些慢速设备的琐碎请求整理好，再通过中间的接口汇报上去。

I/O 软件的层次结构

第 1 层：用户空间的 I/O 软件 (User-Space I/O Software)

“我要打印一份文件”

• 位置：最顶层，直接和用户打交道。
• 是谁：你写的 C 语言代码（printf, scanf），或者具体的应用程序（Word, 浏览器）。
• 核心功能：
  • I/O 系统调用：发起请求。
  • SPOOLing：比如你点打印时，电脑没卡死，而是把任务放到了后台队列里，这就是 SPOOLing 技术（后面会细讲）。
  • I/O 格式化：比如把你的数字 100 转换成字符 '1', '0', '0' 显示在屏幕上。
• 特点：它根本不知道硬盘是圆的还是方的，它只知道“我要读/写数据”。

第 2 层：独立于设备的 I/O 软件 (Device-Independent I/O Software)

“好的，不管你是存到 U 盘还是硬盘，逻辑都一样”

• 位置：第二层，这是操作系统的核心通逻辑。
• 核心功能：
  • 设备的命名：把物理设备映射成逻辑名（比如 /dev/sda 或 C: 盘）。
  • 设备保护：检查你有没有权限读这个文件。
  • 缓冲 (Buffering)：非常关键！为了解决速度差异，数据会先暂存在这里。
  • 设备分配与释放：决定这个打印机现在归谁用。
• 特点：这一层抹平了硬件差异。对于它来说，所有设备都是“文件”。

第 3 层：I/O 设备驱动程序 (Device Drivers)

“收到，正在指挥西部数据硬盘的磁头移动”

• 位置：第三层，这是最懂硬件的软件。
• 核心功能：
  • 翻译：把上层的“读第 5 个块”这种抽象命令，翻译成具体的硬件指令（如“设置寄存器 X 为 1，向端口 Y 发送数据”）。
  • 检查状态：看设备是不是忙，是不是出错了。
• 特点：每一类设备都有专门的驱动。显卡有显卡驱动，网卡有网卡驱动。它是操作系统和硬件之间的“翻译官”。

第 4 层：I/O 中断处理程序 (Interrupt Handlers)

“老板，活干完了！(叫醒 CPU)”

• 位置：最底层软件，紧贴硬件。
• 核心功能：
  • 处理中断：当硬件干完活（比如 DMA 搬运完了），会发个电信号触发中断，这层软件负责响应。
  • 唤醒驱动：告诉上面的驱动程序“数据到了，你可以继续往下跑了”。
• 特点：它是在硬件事件发生后被动触发的“急救员”。

总结：数据流动的全过程

想象你在 Word 里点击“保存”（写硬盘）：

1. 用户层：Word 调用系统函数 write()。
2. 独立层：OS 检查权限，分配缓存，找到文件对应的逻辑地址。
3. 驱动层：驱动程序把逻辑地址算出具体的磁道和扇区，向硬盘控制器发指令。
4. 硬件层：硬盘疯狂转动，磁头写入数据。
5. 中断层：硬盘写完，发中断。中断程序告诉驱动“搞定”，驱动告诉上层“搞定”，最后 Word 提示你“保存成功”。

I/O 缓冲区

1. 核心定义：什么是 I/O 缓冲区？

给出了明确定义：“在内存中开辟的存储区，专门用于临时存放 I/O 操作的数据”。

• 通俗理解：
  • 没有缓冲：CPU 直接伸手向硬盘要数据，硬盘没给，CPU 就手悬在半空等着。
  • 有了缓冲：在内存里放一个“快递柜”。硬盘把数据慢慢填进柜子，填满了通知 CPU 来取。CPU 取数据的时候，硬盘可以继续往下一个柜子里填。

2. 为什么要引入缓冲？（五大目的）

PPT 左侧详细列出了目的，每一条都直击痛点：

1. 解决速度不匹配：这是最核心的。CPU 是跑车，I/O 是拖拉机。缓冲让跑车不用停车等拖拉机。
2. 协调记录大小不一致：
   • 逻辑记录：你的代码可能想读一行字（10个字节）。
   • 物理记录：硬盘一次只能读一个扇区（4KB）。
   • 缓冲的作用：把 4KB 读到缓冲区，然后把其中的 10个字节 拿给你的程序。
3. 提高并行性：CPU 算它的，设备传它的，互不干扰。
4. 减少中断次数：
   • 如果没有缓冲，每来一个字符就要中断 CPU 一次。
   • 有了缓冲，填满一整个缓冲区（比如 4KB）才中断一次。CPU 舒服多了。
5. 放宽响应时间要求：数据来了先进缓冲区待着，CPU 忙完手头的事再来取，不用秒回。

3. 缓冲技术的进化史（看右边的图）

PPT 右侧的四张小图展示了缓冲技术是如何一步步变强的。

(a) 无缓冲 (No Buffering)

• 状态：CPU 和设备直接对接。
• 后果：完全串行。设备忙，CPU 就要等；CPU 忙，设备就要停。效率最低。

1. 三个关键变量 (T, M, C)

首先，你要搞清楚这三个字母代表什么，它们是一个数据块处理流程的三个步骤：

• $T$ (Time for Input)：输入时间。从磁盘把一块数据读到缓冲区。这是 I/O 设备的活。
• $M$ (Time for Move)：传送时间。系统把数据从缓冲区“搬”到用户的内存区。这是内存复制的操作。
• $C$ (Time for Computation)：计算时间。CPU 对这块数据进行处理。这是 CPU 的活。

核心逻辑：

• 没有缓冲时：这三步是串行的，总时间 = $T + C$。
• 有了单缓冲：$T$（I/O） 和 $C$（CPU计算） 可以并行了（同时进行）。

2. 两种场景分析

PPT 下方展示了两种可能的情况，取决于“谁更慢”。

情况一：T > C (I/O 慢，CPU 快)

这是左边的图。

• 场景：硬盘读得很慢 ($T$ 长)，CPU 算得很快 ($C$ 短)。
• 过程：
  • CPU 很快算完了上一块数据 ($C$)，但是下一块数据还没传完 ($T$)。
  • 结果：CPU 必须等待硬盘。
• 瓶颈：在于 $T$。
• 处理一块数据的总时间：$T + M$。
  • (注：虽然也有 C，但 C 包含在 T 的时间段里并行做完了，没有增加额外耗时，所以只算长的那段 T，加上必须要做的搬运 M。)

情况二：T < C (I/O 快，CPU 慢)

这是右边的图。

• 场景：硬盘读得飞快 ($T$ 短)，但 CPU 计算很复杂，算得很慢 ($C$ 长)。
• 过程：
  • 硬盘很快把缓冲区填满了 ($T$)，但是 CPU 还在算上一块 ($C$)，没空来取。
  • 结果：硬盘必须等待 CPU 腾出缓冲区。
• 瓶颈：在于 $C$。
• 处理一块数据的总时间：$C + M$。

(b) 单缓冲 (Single Buffer)

• 原理：操作系统在内存里建一个仓库。
  • 设备 -> 仓库：设备把数据搬进仓库（CPU 此时可以干别的）。
  • 仓库 -> 用户进程：仓库满了，CPU 把数据从仓库挪走。
• 局限：不能同时进出。当 CPU 正在从仓库取货时，设备不能往里面送货（因为只有一个门），设备必须暂停等待仓库腾空。

(c) 双缓冲 (Double Buffering) —— 也叫“乒乓缓冲”

• 原理：建两个仓库（1号和2号）。
• 玩法：
  • 设备往 1号 装货。
  • 与此同时，CPU 从 2号 取货。
  • 大家都不用停！等 1号满了、2号空了，交换一下。
• 优点：实现了极致的并行。除非 CPU 处理太慢或者设备太慢导致一方严重积压，否则数据流几乎是连续的。

答案是：Max(C + M, T)

这里的逻辑是：

• T (Input)：设备往“缓冲区1”里送货的时间。
• C + M (Compute + Move)：CPU 从“缓冲区2”取货 ($M$) 并处理 ($C$) 的时间。
• 因为有两个缓冲区，这两件事是完全并行的。谁慢（时间长），整体速度就取决于谁。

(d) 多缓冲/循环缓冲 (Circular Buffering)

• 原理：建很多个仓库，连成一个圈。
• 场景：适用于阵发性的大量数据传输（比如看高清视频，网速忽快忽慢）。
• 玩法：
  • 设备拼命往空仓库里填（生产者）。
  • CPU 拼命追着满仓库取（消费者）。
  • 只要圈里还有空位，设备就不用停；只要圈里还有满位，CPU 就不用停。这是弹性最大的方案。

独占型外围设备的分配

设备独立性 (Device Independence)

1. 核心痛点：如果把代码写死会怎样？

以前的做法 (物理设备绑定)：

• 你在写程序时，如果直接写死：“我要用编号为 001 的那台惠普打印机”。
• 后果：如果这台 001 号打印机坏了，或者被搬走了，你的程序就直接报错崩溃了，即使旁边还有一台一模一样的 002 号打印机空闲着，你也用不了。

总结：绑定具体物理设备虽然简单，但灵活性极差，一坏就瘫痪。

2. 解决方案：引入“逻辑设备”

为了解决这个问题，操作系统引入了设备独立性。

• 核心思想：
  • 用户（程序员）：只负责说“我要用一台打印机”（这就是逻辑设备）。
  • 操作系统：负责去仓库看哪台打印机是好的、空闲的（比如 003 号），然后把它分配给你（这就是物理设备）。
• PPT 定义：用户不指定物理设备，而是指定逻辑设备，使得用户作业和物理设备分离开来。

3. 实现机制：映射表 (The Mapping Table)

操作系统是怎么把你的“空头支票”（逻辑设备）兑现成“真金白银”（物理设备）的呢？

• PPT 中间红字提到：系统需要提供逻辑设备名到物理设备名的映射表。
• 类比：
  • 你打车时输入“我要去机场”（逻辑请求）。
  • 打车软件（操作系统）查一下数据库（映射表），指派了“京B·12345”这辆车（物理设备）给你。
  • 这一层映射关系，就是设备独立性的核心。

4. 三大优点 (考试必考)

代码不用改 (应用程序与具体物理设备无关)：

• 你换了个新鼠标，不需要去改你的游戏代码。因为游戏只调用“逻辑鼠标”，操作系统会自动把新鼠标映射上去。系统增减或变更设备时不需要修改源程序。

系统更可靠 (易于应对故障)：

• 如果打印机 A 坏了，操作系统自动把任务导向打印机 B。用户根本感觉不到故障的存在。

资源分配更灵活：

• 谁闲着就给谁用，实现了多道程序设计，不再出现“旱的旱死，涝的涝死”的情况。

设备分配的数据结构

共享型外围设备的驱动

1. 物理组件：搭建“多层蛋糕”

请看右上角的 3D 图：

• 盘片 (Platters)：磁盘里不只有一张盘，而是有多张盘片叠在一起，穿在中间的轴上高速旋转。
• 盘面 (Surfaces)：每个盘片就像硬币一样，有正反两面。通常每一面都可以存数据，所以 2 个盘片就有 4 个盘面。
• 磁头 (Heads)：看那个像梳子一样的移动臂，它的每一个齿尖上都有一个磁头。
  • 关键点：所有磁头是共进退的。移动臂一动，所有磁头一起动。

2. 数据划分：画圈圈

请看右下角的平面图：

• 磁道 (Track)：盘面被划分成无数个同心圆，每一个圈就是一个磁道。
  • 比喻： 就像操场上的跑道。
• 扇区 (Sector)：每个磁道又像切披萨一样，被切分成很多小块，每一块叫扇区。
  • 地位：扇区是磁盘读写的最小物理单位（通常是 512 字节或 4KB）。

3. 核心概念：柱面 (Cylinder) —— 考试必考

这是最抽象但最重要的概念。请看右上角图中标注红色的虚线圆柱体。

• 定义：所有盘面上，半径相同的那些磁道，在垂直方向上叠在一起，就构成了一个柱面。
• 为什么要有这个概念？
  • 因为所有磁头是固定在同一个移动臂上的。
  • 当你把磁头移动到最外圈（磁道 0）时，所有盘面的磁头都同时停在了磁道 0 上。
  • 性能秘诀：如果不移动机械臂，只通过电子切换磁头来读写不同盘面上的数据，速度是极快的。
  • 结论：柱面是操作系统优化读写速度的关键。把相关联的数据存在同一个柱面上，就能减少机械臂的移动。

4. 磁盘寻址：如何找到一个数据块？

PPT 左下角红字列出了物理块地址的编码方法，最经典的是 CHS 寻址法：

1. 柱面号 (Cylinder) —— 找圈

• 首先，操作系统指挥移动臂，把磁头移动到指定的半径位置（比如第 100 号柱面）。
• 动作：机械移动（最慢，叫“寻道时间”）。

2. 磁头号 (Head) —— 找面

• 磁头臂到了位置，但有 4 个盘面，我要读哪一个？通过激活具体的磁头来选择盘面。
• 动作：电子切换（极快）。

3. 扇区号 (Sector) —— 找块

• 盘面在疯狂旋转，磁头不动，等着指定的那个扇区（披萨块）转到磁头底下。
• 动作：机械旋转等待（较慢，叫“旋转延迟”）。

地址转换关系（扇区编号从0开始）

磁盘存取时间

公式左边的 $T_a$ 代表 磁盘一次存取的总时间 (Total Access Time)。它由三部分组成：

第一部分：寻道时间 ($T_s$) —— “最耗时的赶路”

• 对应变量：$T_s$ (Seek Time)。
• 含义：机械臂把磁头移动到指定柱面（磁道）所花的时间。
• 特点：
  • 这是物理机械运动。
  • 在计算题中，通常会直接给你一个平均值（比如 “平均寻道时间为 10ms”），或者让你根据移动了多少个磁道来算。
  • 它是性能杀手：通常占总时间的大头。

第二部分：旋转延迟 ($\frac{1}{2r}$) —— “平均运气”

• 对应变量：图中蓝色的 $\frac{1}{2r}$。
• 含义：平均旋转等待时间。
• 推导逻辑（非常重要）：
  • $r$：磁盘旋转速度（单位：转/秒）。比如 7200转/分 = 120转/秒。
  • $1/r$：转一整圈需要的时间。
  • 为什么是 $1/2$？：因为当你磁头到了磁道时，目标扇区可能刚过去（要等一整圈），也可能正好就在下面（不用等）。平均来看，你需要等半圈。
  • 这就是 $\frac{1}{2} \times (\text{转一圈的时间})$ 的由来。

第三部分：传输时间 ($\frac{b}{rN}$) —— “真正的读写”

• 对应变量：图中橙色的 $\frac{b}{rN}$。
• 含义：平均传输时间。也就是磁头扫过数据块并读取内容的时间。
• 变量详解：
  • $b$：你要读写的字节数 (Bytes to transfer)。
  • $N$：一个磁道上总共有多少字节 (Bytes per track)。
  • $r$：转速。
• 推导逻辑：
  • $r \times N$ = 磁盘一秒钟能扫过多少数据（数据传输率）。
  • 时间 = 总量 / 速度 = $b / (r \times N)$。
  • 或者另一种理解： $\frac{b}{N}$ 表示你要读的数据占了这一圈的百分之多少（比如占了 1/10 圈），然后乘以转一圈的时间 ($1/r$)。结果是一样的。

移臂调度及算法

先来先服务算法

最短查找时间优先算法

单向扫描算法

双向扫描算法

电梯调度算法

旋转调度

循环排序

优化分布（交替排序）

参考资料

操作系统原理 (2025 春季学期)

01 - AI 时代的操作系统课2025 南京大学操作系统原理]_哔哩哔哩_bilibili

第一章作业

1

假设同一套指令集用不同的方法设计了两种机器 M1 和 M2。机器 M1 的时钟周期为 0.8ns，机器 M2 的时钟周期为 1.2ns。某个程序 P 在机器 M1 上运行时的 CPI 为 4，在 M2 上的 CPI 为 2。对于程序 P 来说，哪台机器的执行速度更快？快多少？

2

假定编译器对某段高级语言程序编译生成两种不同的指令序列 S1 和 S2，在时钟频率为 500MHz 的机器 M 上运行，目标指令序列中用到的指令类型有 A、B、C 和 D 四类。每类指令在 M 上的 CPI 和两个指令序列所用的各类指令条数如下表所示。

3

假定机器 M 在运行程序 P 的过程中，共执行了 500×10⁶ 条浮点数指令、4000×10⁶ 条整数指令、3000×10⁶ 条访存指令、1000×10⁶ 条分支指令，这 4 种指令的 CPI 分别是 2、1、4、1。若要使程序 P 的执行时间减少一半，浮点指令的 CPI 应如何改进？若要使程序 P 的执行时间减少一半，访存指令和分支指令的 CPI 应如何改进？若浮点指令和整数指令的 CPI 减少 20%，访存指令和分支指令的 CPI 减少 40%，则程序 P 的执行时间会减少多少？

第二章作业

1

假定某计算机的总线采用奇校验，每8位数据有一位校验位，若在32位数据线上传输的信息是
8F 3C AB 96H，则对应的4个校验位应为什么？
若接收方收到的数据信息和校验位分别为87 3C AB 96H 和 0101B，则说明发生了什么情况，并给出验证过程。.0

第一部分：计算原始数据 8F 3C AB 96H 对应的 4 个校验位

前提条件：

• 使用奇校验：每个字节（8位）中，1的个数必须是奇数。
• 每8位数据配1位校验位，所以32位数据分成4个字节，对应4个校验位。
• 数据是十六进制：8F 3C AB 96H

我们需要对每一个字节单独计算其奇校验位。

第一步：把每个十六进制字节转换成二进制

• 8F H = 1000 1111
• 3C H = 0011 1100
• AB H = 1010 1011
• 96 H = 1001 0110

第二步：数每个字节中“1”的个数，然后确定校验位

奇校验规则： 如果当前字节中“1”的个数是偶数，则校验位设为 1，使总数变为奇数；如果是奇数，则校验位设为 0，保持奇数。

我们逐个来看：

1. 字节 8F = 1000 1111

   • 数“1”：位置0, 4,5,6,7 → 共 5个1 → 是奇数
   • 所以校验位 = 0

2. 字节 3C = 0011 1100

   • 数“1”：位置2,3,4,5 → 共 4个1 → 是偶数
   • 所以校验位 = 1

3. 字节 AB = 1010 1011

   • 数“1”：位置0,2,4,6,7 → 共 5个1 → 是奇数
   • 所以校验位 = 0

4. 字节 96 = 1001 0110

   • 数“1”：位置0,3,5,6 → 共 4个1 → 是偶数
   • 所以校验位 = 1

✅ 所以，对应的4个校验位是：0 1 0 1，即 0101B

第二部分：接收方收到的数据是 87 3C AB 96H 和校验位 0101B，发生了什么？验证过程

现在接收方收到：

• 数据：87 3C AB 96H
• 校验位：0101B

我们怀疑有错误，因为原始发送的是 8F，但收到的是 87 —— 很可能第一个字节出错了！

我们来逐字节验证奇校验是否成立。

第一步：将接收到的数据转为二进制

• 87 H = 1000 0111
• 3C H = 0011 1100 （没变）
• AB H = 1010 1011 （没变）
• 96 H = 1001 0110 （没变）

校验位：0101B → 对应四个字节的校验位分别是：第1字节 0，第2字节 1，第3字节 0，第4字节 1

第二步：验证每个字节 + 校验位 是否满足奇校验

注意：我们验证的是“数据位 + 校验位”一共9位中，1的个数是否为奇数。

1. 第一字节 87 + 校验位 0

   • 数据位：1000 0111 → “1”的个数：位置0, 5,6,7 → 4个1
   • 加上校验位 0 → 总共还是 4个1 → 是偶数 ❌
   • 不满足奇校验！→ 出错！

2. 第二字节 3C + 校验位 1

   • 数据位：0011 1100 → “1”的个数：4个（偶数）
   • 加上校验位 1 → 总共 4+1=5 → 奇数 ✅
   • 正确

3. 第三字节 AB + 校验位 0

   • 数据位：1010 1011 → “1”的个数：5个（奇数）
   • 加上校验位 0 → 总共 5 → 奇数 ✅
   • 正确

4. 第四字节 96 + 校验位 1

   • 数据位：1001 0110 → “1”的个数：4个（偶数）
   • 加上校验位 1 → 总共 5 → 奇数 ✅
   • 正确

✅ 结论：只有第一个字节校验失败！说明在传输过程中，第一个字节发生了错误。

进一步分析：哪里出错了？

原始发送的是 8F H = 1000 1111

接收的是 87 H = 1000 0111

对比：

1
2
3
4

原始: 1 0 0 0  1 1 1 1
接收: 1 0 0 0  0 1 1 1
             ↑
            第5位（从左数第5位，或从右数第4位）由1变成了0

所以，第5位发生了翻转错误（bit flip）。

🧠 总结

1. 原始数据 8F 3C AB 96H 的校验位是 0101B。
2. 接收方收到 87 3C AB 96H 和 0101B 后，发现第一个字节校验失败，说明该字节在传输中发生了错误（具体是第5位由1变0）。
3. 奇校验能检测单个比特错误，但不能纠正它，也不能检测偶数个比特错误。

第三章作业

已知 x = 10, y = -6，采用 6位机器数表示。请按如下要求计算并把结果还原成真值。

（1）求 [x + y]补，[x - y]补
（2）用原码一位乘法计算 [x × y]原
（3）用布斯算法计算 [x × y]补
（4）用加减交替法计算 [x / y]原 的商和余数

第七章作业

1

DRAM 的全称是 Dynamic Random Access Memory，中文叫 动态随机存取存储器。

它是计算机中最常用的主存储器（Main Memory / RAM），也就是我们平时常说的“内存条”上的核心芯片。

为什么 DRAM 单元要刷新？（物理原理）

核心原因：漏电。

你可以把 DRAM 的存储单元想象成一个底部有个小针眼的“水桶”（电容），而数据就是“水”（电荷）。

• 存入数据 “1”： 你给桶里倒满水。
• 存入数据 “0”： 你把桶倒空。
• 问题来了： 因为那个小针眼（晶体管的漏电流），满桶的水会慢慢往下漏。
  • 如果你不管它，过一会儿（比如 2ms 后），桶里的水漏干了，原本的 “1” 就变成了 “0”，数据就丢了。

这里最容易混淆的是两个时间概念，必须分清楚：

1. 最大刷新时间（题目中的 2ms）：
   • 这是死线 (Deadline)。
   • 意思是：对于每一个水桶，管理员最迟必须每隔 2ms 回来检查一次。如果超过 2ms 没管它，水就漏光了。
2. 产生刷新信号的间隔（题目要求的答案）：
   • 这是管理员处理下一行水桶的频率。
   • 关键点： 管理员不能一次性同时刷新几百万个水桶（那样电路会过载，电流太大）。他必须一批一批地（一行一行地）轮流刷新。

2

ROM 的全称是 Read-Only Memory，中文叫 只读存储器。

核心特点：

• 字面意思： “Read-Only” 意味着只能读，不能写（或者说在正常工作状态下不能随意写入）。
• 实际特性（最重要）：非易失性 (Non-Volatile)。
  • RAM (DRAM/SRAM)： 一断电，数据立马消失。
  • ROM： 断电后，数据依然保存。哪怕你把电脑关机放一年，ROM 里的数据也不会丢。

为什么 ROM 总是放在内存地址的最前面（从 0 开始）？

1. 开机第一件事： 当你按下电脑电源键时，RAM（内存条）里是空的（全是乱码或 0），CPU 无法从 RAM 里读取指令。
2. 启动引导： CPU 设计为通电后自动去地址 0000H（或其他固定地址）找第一条指令。
3. 固化程序： 我们必须在这个位置放一个断电也不丢数据的存储器（ROM），里面存着电脑的启动程序（BIOS/UEFI）。
   • 它负责检测硬件、初始化系统，然后把操作系统（Windows/Linux）从硬盘搬到 RAM 里。

当 $\overline{\text{MREQ}} = 0$（即处于低电平/有效状态）时，它的主要作用是通知系统，CPU 当前正打算对内存（RAM 或 ROM）进行访问。

$R/\overline{W}$ (Read / Write Control)

• 角色：这是 CPU 发出的控制信号（总线信号）。
• 含义：它告诉整个系统，CPU 当前想要控制数据流向的方向。
• 状态逻辑：
  • 高电平 (1) = Read (读)：CPU 准备从总线上接收数据（数据流向：内存 $\to$ CPU）。
  • 低电平 (0) = Write (写)：CPU 准备向总线上发送数据（数据流向：CPU $\to$ 内存）。

通俗理解：这是 CPU 在喊话：“大家都听好了，我现在是要‘收东西’（Read）还是要‘发东西’（Write）。”

$\overline{WE}$ (Write Enable)

• 角色：这是 RAM 芯片上的输入引脚（控制端）。
• 含义：允许写入信号。它决定了内存芯片是否允许将数据总线上的电平记录到存储单元中。
• 符号含义：顶部的横线表示低电平有效 (Active Low)。
• 状态逻辑：
  • 低电平 (0) = 允许写入：内存芯片打开“大门”，将数据总线上的数据存入当前地址指向的单元。
  • 高电平 (1) = 禁止写入：内存芯片处于读取模式（配合其他信号）或待机模式，不会修改内部存储的数据。

通俗理解：这是内存芯片身上的一个开关。只有把这个开关拉下来（变低），内存才会乖乖地把数据“记下来”。

3

4

5