[机器学习西瓜书] 第02章 模型评估与选择 笔记

[机器学习西瓜书] 第02章 模型评估与选择 笔记

人工智能AI|计算机 ComputerScience


@ZYX 写于2020年07月30日

第02章 模型评估与选择

2.1 经验误差与过拟合

  • 错误率
    分类错误的样本数占样本总数的比例称为”错误率”(error rate)

    • 如果在$m$个样本中有$a$个样本分类错误,则错误率$E=a/m$;
    • 精度
      $1-a/m$ 称为”精度”(accuracy)
      即”精度=1一错误率”
  • 误差
    学习器的实际预测输出与样本的真实输出之间的差异称为”误差” (error)

    • 训练误差||经验误差
      学习器在训练集上的误差称为”训练误差”(training error)或”经验误差”(empirical error)

      • 由于无法做到泛化误差最小号,实际能做的是努力使经验误差最小化
    • 泛化误差
      新样本上的误差称为”泛化误差”(generalization error).

      • 显然,我们希望得到泛化误差小的学习器
  • 过拟合
    训练样本自身的一些特点当作了所有潜在样本都会具有的一般性质,称为”过拟合” (overfitting).

    • 这样就会导致泛化性能下降
    • 是机器学习面临的关键障碍
    • 无法彻底避免的,能做的只是”缓解”
      • 机器学习面临的问题通常是NP难甚至更难
    • 欠拟合
      “欠拟合” (underfitting) 是指对训练样本的一般性质尚未学好.

      • 通常是由于学习能力低下
      • 欠拟合较容易克服
  • 模型选择问题
    该选用哪一个学习算法、使用哪一种参数配置? 这是”模型选择”(model selection)问题

    • 解决
      1. 评估候选模型的泛化误差
      2. 选择泛化误差最小的那个模型

2.2 评估方法

  • 需使用一个测试集(testing set)来测试学习器对新样本的判别能力
    • 以测试集上的测试误差(testing error)作为泛化误差的近似
    • 假设测试样本也是从样本真实分布中独立同分布采样而得
    • 应尽可能与训练集互斥
    • 数学表达
      • 包含$m$个样例的数据集$D=\{(x_{1},y_{1}),(x_{2},y_{2}), \cdots, (x_{m},y_{m})\}$
      • 通过对$D$进行适当的处理,从中产生出
        1. 训练集$S$
        2. 测试集$T$

2.2.1 留出法

  • 直接将数据集D划分为两个互斥的集合:其中一个集合作为训练集S,另一个作为测试集T,
    即$D=S∪T, S∩T=\empty$
  • 训练/测试集的划分要尽可能保持数据分布的一致性,避免因数据划分过程引入额外的偏差而对最终结果产生影响,
    • 例:在分类任务中,至少要保持样本的类别比例相似.
      • 分层采样
        保留类别比例的采样方式通常称为”分层采样” (stratified sampling).
  • 一般要采用若干次随机划分、重复进行实验评估后取平均值作为留出法的评估结果
    • 单次使用留出法得到的估计结果不够稳定可靠
  • 窘境
    • 若令训练集S包含绝大多数样本
      • 则训练出的模型可能更接近于用D训练出的模型
      • 但由于T比较小评估结果可能不够稳定准确
    • 若令测试集T多包含一些样本, 则训练集SD差别更大了,被评估的模型与用D训练出的模型相比可能有较大差别,从而降低了评估结果的保真性(fidelity)
    • 常见做法是将大约2/3~4/5的样本用于训练,剩余样本用于测试.

2.2.2 交叉验证法

  • 步骤
    1. 数据集D划分为$k$个大小相似的互斥子集(也就是partition)
      • 每个子集$D_{i}$都尽可能保持数据分布的一致性, 即从D中通过分层采样得到.
    2. 每次用$k-1$个子集的并集作为训练集,剩余的那个子集作为测试集;
      • 可获得k组训练/测试集
    3. 进行$k$ 次训练和测试
    4. 返回这$k$ 个测试结果的均值
  • 评估结果的稳定性和保真性在很大程度上取决于k的取值
    • 通常称为”k折交叉验证” (k-fold cross validation)
    • k最常用的取值是10
  • 为减小因样本划分不同而引入的差别,k折交叉验证通常要
    1. 随机使用不同的划分重复$p$ 次
    2. 最终的评估结果是这$p$ 次k折交叉验证结果的均值
    • 常见的有”10次10折交叉验证”
  • 特例:留一法(Leave-One-Out,简称LOO)
    令$k=m$

    • 留一法不受随机样本划分方式的影响(每个只有1个样本)
    • 缺点
      • 在数据集比较大时,训练$m$ 个模型的计算开销可能是难以忍受的
      • 估计结果也未必永远比其他评估方法准确
        • 没有免费的午餐定理对实验评估方法同样适用.

2.2.3 自助法

  • 步骤
    1. 对它进行采样产生数据集$D’$
      1. 每次随机从D中挑选一个样本,将其拷贝放入D’
      2. 将该样本放回D中,使得该样本在下次采样时仍可被采到
      3. 重复执行$m$ 次
      • 得到包含$m$ 个样本的数据集$D’$,
      • 样本在m次采样中始终不被采到的概率是$(1-1/m)^{m}$ ——取极限得$\lim_{m \rightarrow \infty}\left(1-\frac{1}{m}\right)^{m} \mapsto \frac{1}{e} \approx 0.368$
        • 即D中约有36.8%的样本未出现在D’中
    2. 将D’用作训练集, D\D'(D-D’)用作测试集
  • 包外估计
    约1/3数据没在训练集中出现的样本用于测试.这样的测试结果,亦称”包外估计”(out-of-bag estimate)
  • 优点
    • 在数据集较小、难以有效划分训练/测试集时很有用
    • 能从初始数据集中产生多个不同的训练集,这对集成学习等方法有很大的好处.
  • 缺点
    • 改变了初始数据集的分布,这会引入估计偏差

2.2.4 调参与最终模型

  • 大多数学习算法都有些参数(parameter)需要设定
    • 参数配置不同,学得模型的性能往往有显著差别
  • 调参
    对算法参数进行设定,这就是通常所说的”参数调节”或简称”调参”(parameter tuning).
  • 学习算法的很多参数是在实数范围内取值
    • 对每种参数配置都训练出模型来是不可行的
    • 所以对每个参数选定一个范围变化步长
      • 选定的参数值往往不是”最佳”值
      • 是在计算开销性能估计之间进行折中的结果
        • 通过这个折中,学习过程才变得可行
  • 验证集
    模型评估与选择中用于评估测试的数据集,称为”验证集”(validation set).

2.3 性能度量

  • 衡量模型泛化能力的评价标准,这就是性能度量(performance measure)
  • 性能度量反映了任务需求
    • 这意味着模型的”好坏”是相对的
  • 数学表达
    • 样例集$D=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots ,(x_{m},y_{m})\}$
      • $y_{i}$ 是示例$x_{i}$ 的真实标记
      • $f(x)$ 学习器预测结果
  • 均方误差”
    • 回归任务最常用的性能度量是”均方误差” (mean squared error)
      $E(f;D)=\frac{1}{m} \sum_{i=1}^{m}(f(x_{i})-y_{i})^{2}$
    • 一般化
      • 对于数据分布 $\mathcal{D}$概率密度函数 $p(\cdot)$
        $E(f ; \mathcal{D})=\int_{\boldsymbol{x} \sim \mathcal{D}}(f(\boldsymbol{x})-y)^{2} p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x}$

2.3.1 错误率与精度

  • 错误率是分类错误的样本数占样本总数的比例
    • 定义:
      $E(f ; D)=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right) \neq y_{i}\right)$
    • 一般化
      $E(f ; \mathcal{D})=\int_{\boldsymbol{x} \sim \mathcal{D}} \mathbb{I}(f(\boldsymbol{x}) \neq y) p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x}$
  • 精度则是分类正确的样本数占样本总数的比例
    • 定义
      $\begin{aligned} \operatorname{acc}(f ; D) &=\frac{1}{m} \sum_{i=1}^{m} \mathbb{I}\left(f\left(\boldsymbol{x}_{i}\right)=y_{i}\right) \\ &=1-E(f ; D) \end{aligned}$
    • 一般化
      $\begin{aligned} \operatorname{acc}(f ; \mathcal{D}) &=\int_{\boldsymbol{x} \sim \mathcal{D}} \mathbb{I}(f(\boldsymbol{x})=y) p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x} \\&=1-E(f ; \mathcal{D}) \end{aligned}$

2.3.2 查准率、查全率与Fl

  • 对于二分类问题,可将样例根据其真实类别与学习器预测类别的组合划分为
    1. 真正例(true positive) $TP$
    2. 假正例(false positive) $FP$
    3. 真反倒(true negative) $TN$
    4. 假反例(false negative) $FN$
    • TP+FP+TN+FN=样例总数
  • 分类结果的混淆矩阵(confusion matrix)
    | 真实情况 | 预测结果 | 预测结果 |
    | :————: | :————: | :————: |
    | \ | 正例 | 反例 |
    | 正例 | TP(真正例) | FN (假反例) |
    | 反例 | FP(假正例) | TN (真反例) |
  • 公式
    • 查准率 $P=\frac{TP}{TP+FP}$
    • 查全率 $R=\frac{TP}{TP+FN}$
    • 查准率和查全率是一对矛盾的度量,往往成反比
P-R图

图2.3 P-R曲线与平衡点示意图
– 可根据学习器的预测结果对样例进行排序
– 前面是被认为”最可能”是正例的样本
– 最后是被认为”最不可能”是正例的样本
P-R曲线
– 按排序逐个把样本作为正例进行预测,则每次可以计算出:
纵轴:查准率
横轴:查全率
– 就得到查准率-查全率曲线,简称”P-R曲线”
包住: 若一个的P-R曲线被另一个的完全”包住”,则可断言后者的性能优于前者
交叉: 如果两个学习器的P-R曲线发生了交叉,这时比较P-R曲线节面积的大小
平衡点
“平衡点” (Break-Event Point,简称BEP)是查准率==查全率时的取值
– BEP在外的更好
F1度量:
$F1=\frac{2\times P\times R}{P+R}=\frac{2\times TP}{|D|+TP-TN}$
– Fl 是基于查准率与查全率的调和平均(harinonicmean)定义的:
$\frac{1}{F 1}=\frac{1}{2} \cdot\left(\frac{1}{P}+\frac{1}{R}\right)$
– F1度量的一般形式——$F_{\beta}$
$F_{\beta}=\frac{\left(1+\beta^{2}\right) \times P \times R}{\left(\beta^{2} \times P\right)+R}$
– $\beta >0$ 度量了查全率对查准率的相对重要性
– $\beta =1$: 就是F1
– $\beta >1$: 查全率R更重要
– $\beta <1$: 查准率P更重要
– $n$ 个二分类混淆矩阵上综合考察查准率和查全率
– 第一种:在各混淆矩阵上分别计算出查准率和查全率
– 记为$\left(P_{1}, R_{1}\right),\left(P_{2}, R_{2}\right), \ldots,\left(P_{n}, R_{n}\right)$
宏查准率: $macro-P=\frac{1}{n}\sum_{i=1}^{n}P_{i}$
宏查全率: $macro-R=\frac{1}{n}\sum_{i=1}^{n}R_{i}$
宏F1: $macro-F1=\frac{2\times macroP\times macroR}{macroP+macroR}$
– 第二种:将各泪淆矩阵的对应元素进行平均
– 得到 $\overline{T P}, \overline{F P}, \overline{T N}, \overline{F N}$
微查准率:$microP=\frac{\overline{TP}}{\overline{TP}+\overline{FP}}$
徽查全率: $microR=\frac{\overline{TP}}{\overline{TP}+\overline{FN}}$
微F1: $micro-F1=\frac{2\times microP\times microR}{microP+microR}$

2.3.3 ROC与AUC

  • 很多学习器是
    1. 为测试样本产生一个实值或概率预测
    2. 然后将这个预测值与一个分类阔值(threshold)进行比较
      • 若大于阈值则分为正类
      • 否则为反类
  • 过程就相当于在这个排序中以某个”截断点” (cut point)将样本分为两部分
    • 前一部分判作正例,后一部分则判作反例.
    • 在不同的应用任务中,我们可根据任务需求来采用不同的截断点
      • 排序本身的质量,体现了综合考虑学习器在不同任务下的”期望泛化性能
ROC
  • 全称是”受试者工作特征”(Receiver Operating Characteristic)曲线
  • 纵轴:真正例率 (True Positive Rate,简称TPR)
  • 横轴:假正例率 (False Positive Rate,简称FPR)
  • TPR与FPR
    • $TPR=\frac{TP}{TP+FN}$
    • $FPR=\frac{FP}{TN+FP}$
  • ROC图
    • 显示ROC曲线的图称为”ROC 图”
      图2.4 ROC 曲线与AUC 示意图
    • 无法产生光滑ROC 曲线,只能绘制近似ROC曲线()
    • 步骤
      • 给定 $m^{+}$ 个正例和 $m^{-}$ 个反例,
      1. 根据学习器预测结果对样例进行排序
      2. 把分类阔值设为最大,即把所有样例均预测为反例
        • 此时真正例率和假正例率均为0,
        • 在坐标(0,0)处标记一个点
      3. 然后,将分类阐值依次设为每个样例的预测值,即依次将每个样例划分为正例
        • 设前一个标记点坐标为(x,y)
          • 当前若为真正例,则对应标记点的坐标为 $(x,y+\frac{1}{m^{+}})$;
          • $(x\frac{1}{m^{-}},y)$
    • 包住:若一个的ROC曲线被另一个的曲线完全”包住”,则后者的性能优
    • 若两个学习器的ROC曲线发生交叉:
      • 比较ROC曲线下的面积,即AUC(Area Under ROC Curve)
        • 可估算为 $AUC=\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1}-x_{i})\cdot (y_{i}+y_{i+1})$
        • AUC考虑的是样本预测的排序质量
          • 因此它与排序误差有紧密联系
        • 排序损失(loss)
          $\mathfrak{l}_{rank}=\frac{1}{m^{+}m^{-}}\sum_{x^{+}\in D^{+}}\sum_{x^{-}\in D^{-}}(\mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)<f\left(\boldsymbol{x}^{-}\right)\right)+\frac{1}{2} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)=f\left(\boldsymbol{x}^{-}\right)\right))$

          • 每一对正、反例:
            • 若正例的预测值<反例,则记一个”罚分”
            • 若相等,则记0.5 个”罚分”
          • $\mathfrak{l}_{rank}$ 对应的是ROC曲线之上的面积
            $AUC=1-\mathfrak{l}_{rank}$

2.3.4 代价敏感错误率与代价曲线

  • 非均等代价
    • 为权衡不同类型错误所造成的不同损失,可为错误赋予”非均等代价” (unequal cost)
    • 数学表达
      • $cost_{ij}$表示将第i类样本预测为第j类样本的代价.
        • 一般来说 $cost_{ii}=0$
        • $cost_{01}>cost_{10}$ : 将第0类判别为第1类所造成的损失更大
        • 损失程度相差越大, $cost_{01}$ 与 $cost_{10}$ 值的差别越大.
      • 代价矩阵(cost matrix)
        | 真实类别 | 预测类别 | 预测类别 |
        | ———— | ———— | ———— |
        | \ | 第0类 | 第1类 |
        | 第0类 | 0 | $cost_{01}$ |
        | 第1类 | $cost_{10}$ | 0 |
  • 总体代价
    • 在非均等代价下,希望最小化”总体代价” (total cost).
    • “代价敏感” (cost-sensitive)错误率
      令$D^{+}, D^{-}$ 代表 正例子集反例子集
      $E(f;D;cost)=\frac{1}{m}(\sum_{x_{i}\in D^{+}}\mathbb{I}(f(x_{i}\not =y_{i})\times cost_{01}+\sum_{x_{i}\in D^{-}}\mathbb{I}(f_{x_{i}\not =y_{i}})\times cost_{10})$
  • 代价曲线(cost curve)
    • 横轴:取值为[0,1]的正例概率代价
      $P(+)cost=\frac{p\times cost_{01}}{p \times cost_{01}+(1-p)\times cost_{10}}$

      • p:样例是正例的概率
    • 纵轴:取值为[0,1] 的归一化代价
      $cost_{norm}=\frac{FNR\times p \times cost_{01}+FPR\times (1-p)\times cost_{10}}{p \times cost_{01}+(1-p)\times cost_{10}}$

      • FPR 是假正例率
      • FNR = 1 – TPR 是假反例率
    • 绘制
      1. ROC曲线上每一点对应了代价平面上的一条线段
        • 设ROC曲线上点的坐标为(TPR, FPR) ,则可相应计算出FNR
      2. 然后绘制一条从(0,FPR)到(1,FNR)的线段
        图2.5 代价曲线与期望总体代价

2.4 比较检验

  • 我们希望比较的是泛化性能,然而通过实验评估方法,我们获得的是测试集上的性能,两者的对比结果可能未必相同
  • 测试集上的性能与测试集本身的选择有很大关系
  • 很多机器学习算法本身有一定的随机性
  • 统计假设检验(hypothesis test)
  • 以错误率为性能度量,用$\epsilon$ 表示.

2.4.1 假设检验

  • 设检验中的”假设”是对学习器泛化错误率分布的某种判断或猜想
    例如$\epsilon =\epsilon_{0} $.

    • 现实任务中,只能获知其测试错误率 $\hat{\epsilon}$
      • 可根据测试错误率估推出泛化错误率的分布
  • 二项检验
    • 二项(binomial)分布
      • 泛化错误率为$\epsilon$ 的学习器在一个样本上犯错的概率是$\epsilon$
      • 测试错误率$\hat{\epsilon}$ 意味着在$m$ 个测试样本中恰有$\hat{\epsilon}\times m$ 个被误分类
      • 泛化错误率为$\epsilon$ 的学习器被测得测试错误率为$\hat{\epsilon}$ 的概率:
        $P(\tilde{\epsilon};\epsilon)=\left(\begin{array}{c}m \\ \hat{\epsilon} \times m\end{array}\right) \epsilon^{\hat{\epsilon} \times m}(1-\epsilon)^{m-\hat{\epsilon} \times m}$

        • 假定测试样本是从样本总体分布中独立采样而得
          • 泛化错误率为$\epsilon$ 的学习器将其中m’个样本误分类,其余样本全部分类正确的概率是$\epsilon\^{m’}(1-\epsilon)^{m-m’}$
      • 这符合二项(binomial)分布
    • 步骤
      • 设 假设为$\epsilon \le \epsilon_{0}$
      • $1-\alpha $为置信度 confidence
      • 在$1-\alpha$ 的概率内所能观测到的最大错误率
        $\bar{\epsilon}=\max \epsilon \quad \text { s.t. } \quad \sum_{i=\epsilon_{0} \times m+1}^{m}\left(\begin{array}{c}m \\ i\end{array}\right) \epsilon^{i}(1-\epsilon)^{m-i}<\alpha$

        • 若测试错误率$\hat{\epsilon}$小于临界值$\bar{\epsilon}$
          • 在$\alpha $显著度下,不能拒绝假设
        • 否则,假设可被拒绝
  • t检验
    • 多次重复留出法或是交叉验证法等进行多次训练/测试,会得到多个测试错误率,可使用”t 检验” (t-test)
    • 令假设为$\mu=\epsilon_{0}$;显著度为$\alpha$
    • 数值
      • 平均测试错误率$\mu$
        $\mu=\frac{1}{k}\sum_{i=1}^{k}\hat{\epsilon_{i}}$
      • 方差$\sigma^{2}$
        $\sigma^{2}=\frac{1}{k-1}\sum_{i=1}^{k}(\hat{\epsilon}-\mu)^{2}$
      • 考虑到这k个测试错误率可看作泛化错误率$\epsilon_{0}$的独立采样,则变量
        $\tau_{t}=\frac{\sqrt{k}(\mu-\epsilon{0})}{\sigma}$

        • 自由度为k-1的t分布
    • 考虑双边(two-tailed)假设
      得临界值为$t_{-\alpha/2}, t_{\alpha/2}$

      • 若$|\mu-\epsilon_{0}|\in [t_{-\alpha/2}, t_{\alpha/2}]$
        则不能拒绝假设
      • 否则可拒绝假设

2.4.2 交叉验证t检验

  • 对两个学习器A和B,若我们使用k折交叉验证法得到的测试错误率分别为$\epsilon_{1}^{A}, \epsilon_{2}^{A}, \ldots, \epsilon_{k}^{A}$ 和 $\epsilon_{1}^{B}, \epsilon_{2}^{B}, \ldots, \epsilon_{k}^{B}$
    • $\epsilon_{i}^{A}$和$\epsilon_{i}^{B}$是在相同的第i折训练/测试集上得到的结果
    • 可用k折交叉验证”成对t检验” (paired t-tests)
  • 基本思想
    若两个学习器的性能相同,则它们使用相同的训练/测试集得到的测试错误率应相同
  • 步骤
    1. 对每对结果求差,$\Delta_{i}=\epsilon_{i}^{A}-\epsilon_{i}^{B}$
      • 若两性能相同,则差值均值班为零
    2. 令假设为”学习器A与B性能相同“,计算$\mu$和$\sigma^{2}$
    3. 在显著度α下,计算变量
      $\tau_{t}=\left|\frac{\sqrt{k}\mu}{\sigma}\right|$

      • 小于临界值$t_{\alpha/2,k-1}$,则假设不能被拒绝
        • $t_{\alpha/2,k-1}$ 是自由度为k-1的t分布上尾部累积分布为α/2的临界值
      • 否则,认为两学习器性能有显著差别
  • 一个重要前提是测试错误率均为泛化错误率的独立采样
  • 5 x 2 交叉验证
    • 通常情况下由于样本有限,不同轮次的训练集会有一定程度的重叠。为缓解这一问题,可采用”5 x 2 交叉验证”
    • 5×2 交叉验证是做5 次2 折交叉验证,在每次2 折交叉验证之前随机将数据打乱,使得5 次支又验证中的数据划分不重复.
    • 步骤
      1. 第i次二折交叉验证将产生2对测试错误率
      2. 分别求差
        • 第1折上差值为 $\Delta_{i}^{1}$
        • 第2折上差值为 $\Delta_{i}^{2}$
      3. 计算
        • 均值 $\mu=0.5(\Delta_{i}^{1}+\Delta_{i}^{2})$
        • 方差$\sigma_{i}^{2}=\left(\Delta_{i}^{1}-\frac{\Delta_{i}^{1}+\Delta_{i}^{2}}{2}\right)^{2}+\left(\Delta_{i}^{2}-\frac{\Delta_{i}^{1}+\Delta_{i}^{2}}{2}\right)^{2}$
      4. 得到变量
        $\tau_{t}=\frac{\mu}{\sqrt{0.2 \sum_{i=1}^{5} \sigma_{i}^{2}}}$

        • 服从自由度为5的t分布
        • 双边检验的临界值$t_{\alpha / 2,5}$

2.4.3 McNemar 检验

  • 对二分类问题, 可获得两学习器分类结果的差别
    即两者都正确都错误一个正确另一个错误的样本数

    • 列联表 (contingency table)
      | B | A | A |
      | ———— | ———— | ———— |
      | \ | 正确 | 错误 |
      | 正确 | $e_{00}$ | $e_{01}$ |
      | 错误 | $e_{10}$ | $e_{11}$ |
  • 假设是两学习器性能相同, 则 $e_{01}=e_{10}$
    • 变量$|e_{01}-e_{10}|$ 应服从正态分布
      • $mu=1$
      • $\sigma^{2}=e_{01}+e_{10}$
    • 卡方分布
      $\tau_{\chi^{2}}=\frac{\left(\left|e_{01}-e_{10}\right|-1\right)^{2}}{e_{01}+e_{10}}$

      • 服从自由度为1 的$\mathcal{X}^{2}$分布
        • 即标准正态分布变量的平方
      • 给定显著度α
        • 当以上变量恒小于临界值$\mathcal{X}^{2}$时,不能拒绝假设
        • 否则,可认为有显著差异

2.4.4 Friedman检验与Nemenyi后续检验

  • 在一组数据集上对多个算法进行比较
  • 例子
    • D1、 D2 、D3 和D4 四个数据集
    • 对算法A 、B 、C 进行比较
    1. 使用留出法或交叉验证法得到每个算法在每个数据集上的测试结果
    2. 然后,在每个数据集上根据测试性能由好到坏排序,并赋予序值1,2, …,
      • 若算法的测试性能相同,则平分序值.
        • 第二和第三名并列(2+3)/2=2.5
    3. Friedman检验来判断这些算法是否性能都相同
      • 若相同,则它们的平均序值应当相同
      • 若”所有算法的性能相同”这个假设被拒绝
        • 这时需进行后续检验(post-hoc test)来进一步区分各算法
          • 比如Nemenyi后续检验
  • 原始Friedman检验
    • N 个数据集上比较k 个算法
    • $r_{i}$ 表示第i个算法的平均序值
    • 此时$r_{i}$ 服从正态分布
      • $\mu=(k+1)/2$
      • $(k^{2}-1)/12$
    • 变量
      $\begin{aligned} \tau_{\chi^{2}} &=\frac{k-1}{k} \cdot \frac{12 N}{k^{2}-1} \sum_{i=1}^{k}\left(r_{i}-\frac{k+1}{2}\right)^{2} \\ &=\frac{12 N}{k(k+1)}\left(\sum_{i=1}^{k} r_{i}^{2}-\frac{k(k+1)^{2}}{4}\right) \end{aligned}$

      • 在k 和N 都较大时,服从自由度为k-1 的$\mathcal{X}^{2}$ 分布.
  • 现在通用的Friedman检验
    $\tau_{F}=\frac{(N-1) \tau_{\chi^{2}}}{N(k-1)-\tau_{\chi^{2}}}$

    • $\tau_{\mathcal{X}^{2}}$ 和原始一样
    • 服从自由度为k-1 和(k – l)(N – 1) 的F 分布,
  • Nemenyi检验
    • Nemenyi检验计算出平均序值差别的临界值域
      $C D=q_{\alpha} \sqrt{\frac{k(k+1)}{6 N}}$

      • 若两个算法的平均序值之差超出临界值域CD,则拒绝”两个算法性能相同”
    • 可以直观地用Friedman 检验图显示
      • 若两个算法的横线段有交叠,则说明这两个算法没有显著差别,否则即说明有显著差别
        图2.8 Friedman 检验图

2.5 偏差与方差

  • 偏差方差分解(bias-variance decomposition)是解释why学习算法泛化性能的一种重要工具
  • 对学习算法的期望泛化错误率进行拆解
    • 测试样本x
    • 令$y_{D}$ 为x在数据集中的标记, y为现实标记
    • $f(x;D)$为预测输出
  • 例子:回归任务
    • 学习算法的期望预测为
      $\bar{f}(\boldsymbol{x})=\mathbb{E}_{D}[f(\boldsymbol{x} ; D)]$
    • 使用样本数相同的不同训练集产生的方差为
      $\operatorname{var}(\boldsymbol{x})=\mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]$

      • 度量了同样大小的训练集的变动所导致的学习性能的变化
      • 即刻画了数据扰动所造成的影响
    • 噪声为
      $\varepsilon^{2}=\mathbb{E}_{D}\left[\left(y_{D}-y\right)^{2}\right]$

      • 假定噪声期望为0,即$E_{D}\left[y_{D}-y\right]=0$
      • 表达了在当前任务上任何学习算法所能达到的期望泛化误差的下界
      • 即刻画了学习问题的难度
    • 期望输出与真实标记的差别称为偏差(bias)
      $\operatorname{bias}^{2}(\boldsymbol{x})=(\bar{f}(\boldsymbol{x})-y)^{2}$

      • 偏差度量了学习算法的期望预测与真实结果的偏离程度
      • 刻画了学习算法本身的拟合能力
  • 得到 $E(f ; D)=\operatorname{bias}^{2}(x)+\operatorname{var}(x)+\varepsilon^{2}$
    • 也就是说:
      • 泛化误差可分解为偏差、方差与噪声之和.
      • 泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度所共同决定的
  • 推导
    $\begin{aligned} E(f ; D)=& \mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ; D)-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})+\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right] \\ &+\mathbb{E}_{D}\left[2(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))\left(\tilde{f}(\boldsymbol{x})-y_{D}\right)\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y+y-y_{D}\right)^{2}\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[(\bar{f}(\boldsymbol{x})-y)^{2}\right]+\mathbb{E}_{D}\left[\left(y-y_{D}\right)^{2}\right] \\ &+2 \mathbb{E}_{D}\left[(\bar{f}(\boldsymbol{x})-y)\left(y-y_{D}\right)\right] \\=& \mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+(\bar{f}(\boldsymbol{x})-y)^{2}+\mathbb{E}_{D}\left[\left(y_{D}-y\right)^{2}\right] \end{aligned}$
  • 一般来说?偏差与方差是有冲突的,这称为偏差一方差窘境(bias-variance dilemma)
    • 在训练不足时
      • 学习器的拟合能力不够强
      • 训练数据的扰动不足以便学习器产生显著变化
      • 此时偏差主导了泛化错误率
    • 随着训练程度的加深
      • 学习器的拟合能力逐渐增强
      • 训练数据发生的扰动渐渐能被学习器学到
      • 方差逐渐主导了泛化错误率
        图2.9 泛化误差与偏差、方差的关系示意图
[机器学习西瓜书] 第01章 绪论 笔记

[机器学习西瓜书] 第01章 绪论 笔记

人工智能AI


@ZYX 写于2020年07月27日

第01章 绪论

1.1 引言

  • 机器学习
    • 目的
      1. 研究如何通过计算的手段
      2. 利用经验来改善系统自身的性能
        • “经验” 通常以 “数据” 形式存在
    • 主要内容
      • 学习算法” (learning algorithm)
        关于在计算机上从数据中产生“模型” (model) 的算法

1.2 基本术语

  • “数据”
    • 表现方式:tuple
      例如 (色泽=青绿;根蒂=蜷缩;敲声=浊响)

      • 每对括号内是一条记录
      • “=”意思是”取值为”
  • “数据集” (data set)
    • 一组记录的集合
    • 示例 || 样本
      每条记录是关于一个事件或对象的描述,称为一个”示例” (instance)或”样本”(sample).

      • 通常假设样本空间中全体样本服从一个未知”分布”(distribution)$\mathcal{D}$
        • 每个样本都是独立地从分布上获得的,即”独立同分布” (independent and identicallydistributed,简称i.i.d.).
      • 特征向量
        属性空间中的每个点对应一个坐标向量,因此我们也把…个示例称为一个”特征向量” (feature vector).
    • 属性 || 特征
      反映事件或对象在某方面的表现或性质的事项,称为”属性” (attribute) 或”特征” (feature)

      • 属性值(attribute value)
        属性上的取值
      • 属性空间
        属性张成的空间称为”属性空间” (attribute space) 、”样本空间” (sample space)或”输入空间”
  • 规范数学表达
    1. 令$D=\{x_{1},x_{2},\cdots,x_{m}\}$表示包含$m$个示例数据集
    2. 每个示例由$d$个属性描述
    • 每个示例$x_{i}=(x_{i1};x_{i2};\cdots;x_{id})$
      • $d$维样本空间$\chi$ 中的一个向量
      • $x_{i}\in\chi$
        • $x_{ij}$ 是$x_{i}$在第$j$个属性上的取值
        • 维数
          $d$ 称为样本 $x_{i}$ 的”维数” (dimensionality)
  • 学习 || 训练
    从数据中学得模型的过程,称为”学习”(learning)或”训练”(training)

    • 工具
      通过执行某个学习算法来完成
    • 原料
      • 训练数据
        使用的数据称为”训练数据” (training data) ,

        • 训练样本
          每个样本称为一个”训练样本”(training sample)
        • 训练集
          训练样本组成的集合称为”训练集” (training set)
    • 目标
      为了找出或逼近真相

      • 假设
        学得模型对应了关于数据某种潜在规律,因此亦称”假设” (hypothesis)

        • 真相 || 真实
          潜在规律自身,则称为”真相”或”真实” (ground-truth)
      • 学习器
        有时将模型称为”学习器” (learner)
        可看作学习算法在给定数据和参数空间上的实例化.
    • 结果
      • 要建立关于”预测” (prediction) 的模型,需获得对于训练样本“判断结果”信息
      • 标记
        关于示例结果的信息,例如”好瓜”,称为”标记” (label)
      • 样例
        拥有了标记信息的示例,则称为”样例” (example)

        • 用$(x_{i},y_{i})$表示第$i$个样例
          • $x_{i}$是一个示例
          • $y_{i}\in\gamma$是示例$x_{i}$的标记
            • 标记空间
              $\gamma$是所有标记的集合,亦称”标记空间”(label space)或”输出空间”
  • 监督学习 (supervised learning)
    使用的训练样本通常拥有标记信息

    • 数学定义
      通过对训练集$\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{m},y_{m}))\}$进行学习
      建立一个从输入空间$\chi$到输出空间$\gamma$的映射$f:\chi\to\gamma$.
    • 种类
      1. 分类
        若欲预测的是离散值,例如”好/坏”,此类学习任务称为”分类” (classification);

        • 二分类
          只涉及两个类别的,称为”二分类” (binary classification)任务
          通常,设置$\gamma=\{-1,+1\} or \{0,1\}$

          • 通常称其中一个类为”正类” (positive class);另一个类为”反类” (negative class);
        • 多分类
          涉及多个类别时,称为”多分类” (multi-class classification)任务.
          $|\gamma|>2$
      2. 回归
        若欲预测的是连续值,例如西瓜成熟度0.95,此类学习任务称为”回归” (regression).
        $\gamma=\R$
    • 测试
      学得模型后,使用其进行预测的过程称为”测试” (testing)

      • 测试样本
        被预测的样本,称为”测试样本” (testing sample).
  • 无监督学习 (unsupervised learning)
    使用的训练样本通常不拥有标记信息

    • “聚类” (clustering)
      将训练集中的西瓜分成若干


      • 称为一个”簇” (cluster);

        • 这些自动形成的簇可能对应一些潜在的概念划分
  • 泛化
    学得模型适用于新样本的能力,称为”泛化” (generalization) 能力

1.3 假设空间

  • 归纳学习
    • 广义: 从样例中学习
    • 狭义: 要求从训练数据中学得概念(concept)
      • 此亦称为”概念学习”或”概念形成”
      • 布尔概念学习
        最基本的概念学习,即对”是/否”这样的可表示为0/1布尔值的目标概念的学习
        例如 好瓜 ↔ (色泽=?)∧(根蒂=?)∧(敲声=?)
        ?表示尚未确定取值,通过学习,确定下来
    • 把学习过程看作一个在所有假设组成的空间中进行搜索的过程
      • 目标
        找到与训练集”匹配”(fit)的假设,即能够将训练集中的瓜判断正确的假设
      • 成果
        获得与训练集一致(即对所有训练样本能够进行正确判断)的假设

        • 版本空间
          可能有多个假设与训练集一致,即存在着一个与训练集一致的”假设集合”,称为”版本空间” (version space).

1.4 归纳偏好

机器学习算法在学习过程中对某种类型假设的偏好,称为”归纳偏好” (inductive bias),简称为”偏好”

  • 任何一个有效的机器学习算法必有其归纳偏好
    • 否则将被假设空间中看似在训练集上”等效”的假设所迷惑,而无法产生确定的学习结果.
  • 原则
    • 奥卡姆剃刀(Occam’s razor)
      若有多个假设与观察一致,则选最简单的那个
    • 奥卡姆剃刀并非唯一可行的原则
  • 在具体的现实问题中,归纳偏好是否与问题本身匹配,大多数时候决定了算法的性能.

没有免费的午餐(NFL)定理

对于任意两个学习算法$\mathfrak{L}_{a}$和$\mathfrak{L}_{b}$,我们都有$\sum_{f}E_{ote}(\pounds|X,f)=\sum_{f}E_{ote}(\pounds_{b}|X,f)$

  • 前提
    • 所有问题出现的机会相同、或所有问题同等重要
    • 假设$f$均匀分布
  • 完整证明
    1. 假设样本空间$\mathcal{X}$和假设空间$\mathcal{H}$组都是离散的
    2. 令 $P\left(h \mid X, \mathfrak{L}_{a}\right)$ 代表算法 $\mathfrak{L}_{a}$ 基于训练数据 $X$ 产生假设 $h$ 的概率
    3. 令 $f$ 代表我们希望学习的真实目标函数.

    • $E_{\text {ote}}\left(\mathfrak{L}_{a} \mid X, f\right)=\sum_{h} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x})) P\left(h \mid X, \mathfrak{L}_{a}\right)$

      • $\mathbb{I}(\cdot)$ 是指示函数,若·为真则取值1 ,否则取值0

$$\begin{aligned} \sum_{f} E_{\text {ote}}\left(\mathfrak{L}_{a} \mid X, f\right) &=\sum_{f} \sum_{h} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x})) P\left(h \mid X, \mathfrak{L}_{a}\right) \\ &=\sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P\left(h \mid X, \mathfrak{L}_{a}\right) \sum_{f} \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x})) \\ &=\sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P\left(h \mid X, \mathfrak{L}_{a}\right) \frac{1}{2} 2^{|\mathcal{X}|} \\ &=\frac{1}{2} 2^{|\mathcal{X}|} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P\left(h \mid X, \mathfrak{L}_{a}\right) \\ &=2^{|x|-1} \sum_{x \in \mathcal{X}-X} P(x) \cdot 1 \end{aligned}$$

  • 结论
    无论学习算法$\mathfrak{L}_{a}$多聪明、学习算法$\mathfrak{L}_{b}$多笨拙,它们的期望性能相同
  • 意义
    • 脱离具体问题,空泛地谈论”什么学习算法更好”毫无意义,
[深入理解计算机系统] 02 信息的表示和处理 笔记

[深入理解计算机系统] 02 信息的表示和处理 笔记

计算机 ComputerScience|计算机原理 ComputerSystem


@ZYX 写于2020年07月12日

第二章 信息的表示和处理

前言

  • 我们研究三种最重要的数字表示
    1. 无符号(unsigned)编码基于传统的二进制表示法,表示大于或者等于零的数字
    2. 补码(two’s-complement)编码是表示有符号整数的最常见的方式,有符号整数就是可以为正或者为负的数字
    3. 浮点数(floating-point)编码是表示实数的科学记数法的以二为基数的版本
  • 计算机的表示法是用有限数量的位来对一个数字编码,因此,当结果太大以至不能表示时, 某些运算就会溢出(overflow)
  • 浮点运算有完全不同的数学属性。
    • 虽然溢出会产生特殊的值但是一组正数的乘积总是正的
    • 由于表示的精度有限,浮点运算是不可结合的
      (3.14+1e20)-1e20==0.0
      3.14+(1e20-1e20)==3.14
  • 整数运算浮点数运算会有不同的数学属性是因为它们处理数字表示有限性的方式不同:
    • 整数的表示只能编码一个较小的数值范围,但是这种表示是精确的
    • 浮点数可以编码一个较大的数值范围,但是这种表示只是近似的
  • Java语言创造了一套新的数字表示和运算标准。C标准的设计允许多种实现方式,而Java标准在数据的格式和编码上是非常精确具体的

2.1 信息存储

  • 大多数计算机使用8位的块,或者字节(byte) ,作为最小的可寻址的存储器单位 , 而不是在存储器中访问单独的
    • 虚拟存储器(virtual memory)
      机器级程序将存储器视为一个非常大的字节数组,称为虚拟存储器
    • 地址(address)
      存储器的每个字节都由一个唯一的数字来标识,称为它的地址
    • 虚拟地址空间(virtual address space)
      所有可能地址的集合称为虚拟地址空间

      • 这个虚拟地址空间是一个展现给机器级程序概念性映像
        • 实际实现是将随机访问存储器(RAM)磁盘存储器特殊硬件操作系统软件结合起来,为程序提供一个看上去统一的字节数组
      • 接下来的几章,我们将讲述编译器运行时系统是如何将存储器空间划分为更可管理的单元,以存放不同的程序对象(program object)
        • 程序对象:程序数据、指令和控制信息。
        • 这种管理完全是在虚拟地址空间里完成的

2.1.1 十六进制表示法

  • 在C语言中,以Ox或0X开头的数字常量被认为是十六进制的值。
    • 字符‘A’〜‘F’既可以是大写,也可以是小写,甚至是大小写混合

2.1.2 字与数据大小

  • 每台计算机都有一个字长(word size) ,指明指针数据标称大小(nominal size)
    • 对于一个字长为ω位的机器而言 :
      1. 虚拟地址的范围为0〜$2^{\omega}-1$
      2. 程序最多访问$2^\omega$个字节。
    • 32位和64位
      • 向后兼容:大多数64位机器都能兼容32位机器编译的程序
        基本C 数据类型的典型大小(以字节为单位)。 分配的字节数受程序是如何编译的影响而变化。 本图给出的是32 位和64 位程序的典型值
  • ISO C99引入了大小固定的数据类型:
    比如int32_t固定为4字节 in64_t固定为8字节

    • 数据大小固定,不随编译器和机器变化
  • 程序员应该力图使他们的程序在不同的机器和编译器上是可移植的
    • 可移植性的一个方面就是使程序对不同数据类型的确切大小不敏感
    • C语言标准对不同数据类型的数字范围设置了下界,但是却没有上界

2.1.4 寻址和字节顺序

  • 对于跨越多字节的程序对象,我们必须建立两个规则:
    1. 这个对象的地址是什么,
    2. 存储器中如何排列这些字节
    • 在几乎所有的机器上,多字节对象都被存储为连续的字节序列,对象的地址为所使用字节中最小的地址
  • 排列字节的规则:
    • 大端法(big endian)
      最高有效字节在最前面的方式,称为大端法(big endian)

      • 大多数IBM和Sun Microsystems的机器都采用这种规则
    • 小端法(little endian)
      最低有效字节在最前面的方式,称为小端法(little endian)

      • 大多数Intel兼容机都釆用这种规则
    • 双端法(bi-endian)
      许多比较新的微处理器使用双端法(bi-endian),也就是说可以把它们配置成作为大端或者小端的机器运行

      • 一旦选择了特定的操作系统, 字节顺序就固定了
        • 比如ARM架构处理器使用双端法,但是跑了安卓和iOS后就是小端法
    • 对于大多数应用程序员来说,他们机器所使用的字节顺序是完全不可见的,无论为哪种类型的机器编译的程序都会得到同样的结果
      • 不过有时候,字节顺序会成为问题:
        1. 网络传输
          此时应用程序的代码编写必须遵守已建立的关于字节顺序的规则,以确保:

          1. 发送方机器将它的内部表示转换成网络标准,
          2. 接收方机器则将网络标准转换为它的内部表示
        2. 当阅读表示整数数据的字节序列时
          • 通常在检查机器级程序时会出现这种情况
            8G483bd:      01      05      64      94      04      08      add      %eax,      0x8049464
          • 这一行是由反汇编器(disassembler)生成的,
            • 反汇编器是一种确定可执行程序文件所表示的指令序列的工具
        3. 当编写规避正常的类型系统的程序时
          • 强制类型转换(cast)与union
  • show_bytes函数:
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, int len) {
    int i;
    for(i = 0; i < len; i++)
        printf("%.2x", start[i]);
    printf("\n");
}

2.1.4 表示字符串

  • C语言中字符串被编码为一个以null (其值为0)字符结尾的字符数组
    • 字符都由某个标准编码来表示,最常见的是ASCII字符码
  • 文本数据比二进制数据具有更强的平台独立性
    • 在使用ASCII码作为字符码的任何系统上都将得到相同的结果与字节顺序和字大小规则无关

2.1.5 表示代码

  • 不同的机器类型使用不同的且不兼容的指令和编码方式
  • 二进制代码是不兼容的
  • 从机器的角度来看,程序仅仅只是字节序列

2.1.6 布尔代数简介

2.1.7 C语言中的位级运算

|就是OR (或),&就是AND (与),〜就是NOT (取反),而^就是EXCLUSIVE-OR (异或)

2.1.8 C语言中的逻辑运算

  • C语言还提供了一组逻辑运算符||、&&和!,分别对应于命题逻辑中的OR、AND和NOT 运算。
  • 逻辑运算很容易和位级运算相混淆,但是它们的功能是完全不同
    真值 返回值
    所有非零的参数 TRUE 1
    参数0 FALSE 0

2.1.9 C语言中的移位运算

  • C语言还提供了一组移位运算,以便向左或者向右移动位模式
  • 左移:
    • 对于一个位表示为$[x_{\omega-1}, x_{\omega-2}, …, x_0]$的操作数x,C表达式x«k会生成一个值,其位表示为$[x_{\omega-k-1}, x_{\omega-k-2}, …, x_0, 0, …, 0]$
      1. x向左移动k位
      2. 丢弃最高的k位
      3. 并在右端补k个0
    • 移位量应该是一个0〜ω-1之间的值
    • 移位运算是从左至右可结合的
      x«j«k==(x«j)«k
  • 右移
    • 一般而言,机器支持两种形式的右移:逻辑右移算术右移
      • 逻辑右移在左端补k个0,得到的结果是$[0, …, 0, x_{\omega-1}, x_{\omega-2}, …, x_k]$
      • 算术右移是在左端补k个最髙有效位的值,得到的结果是$[x_{\omega-1}, …, x_{\omega-1}, x_{\omega-1}, x_{\omega-2}, …, x_k]$
        • 它对有符号整数运算非常有用。
    • C语言标准并没有明确定义应该使用哪种类型的右移
      • 对于unsigned数据,右移必须是逻辑的
      • 对于有符号数据,算术/逻辑右移都可以
      • 实际上,几乎所有的编译器/机器组合都对有符号数据使用算术右移,且许多程序员也都假设这样。
    • 另一方面,Java对于如何进行右移有明确的定义
      • x>>k会将x算术右移k个位置
      • x>>>k会对x做逻辑右移

2.2 整数表示

编码整数的两种不同方式:一种只能表示非负数,而另一种能够表示负数、零和正数
– 术语表
图2-8 整数的数据与算术操作术语。下标w表示数据表示中的位数

2.2.1 整型数据类型

图2-9 32 位程序上C 语言整型数据类型的典型取值范围
图2-10 64 位程序上C 语言整型数据类型的典型取值范围
– 一个值得注意的特点是取值运围不是对称的——负数的范围比整数的范围大1。
– C语言标准定义了每种数据类型必须能够表示的最小的取值范围
图2-11 C 语言的整型数据类型的保证的取值范围。C 语言标准要求
这些数据类型必须至少具有这样的取值范围

2.2.2 无符号数的编码

  • 假设一个整数数据类型有ω位。我们可以将位向量写成 $\vec \omega$ 表示整个向量,或者写成$[x_{\omega-1}, x_{\omega-2}, …, x_0]$来表示向量中的每一位
  • 原理: unsigned数编码的定义
    对向量$\vec x=[x_{\omega-1}, x_{\omega-2}, …, x_0]$:
    $B2U_\omega(\vec x)=\sum_{i=0}^{\omega-1}x_i·2^i$
  • 函数$B2U_\omega$能够被定义为一个映射 ${0,1}^{\omega}$→{${0, …, 2^\omega-1}$}
  • 原理: unsigned编码的唯一性
    • 函数$B2U_\omega$是双射(bijection)

2.2.3 补码编码

  • 最常见的有符号数的计算机表示方式就是补码(two’s-complement) 形式
    • 将字的最高有效位解释为负权(negative weight).
  • 原理:补码编码的定义
    对向量$\vec x=[x_{\omega-1}, x_{\omega-2}, …, x_0]$:
    $B2T_\omega(\vec x)=-x_{\omega -1}2^{\omega-1}+\sum_{i=0}^{\omega-2}x_{i}2^{i}$

    • 最高有效位$x_{\omega-1}$也称为符号位,它的“权重”为一2^{\omega-1}
      • 置1,表负,置0,非负。
  • 原理:补码编码的唯一性
    函数$B2T_{\omega}$是一个双射。

    • 对于每个数$x$
      • 满足$TMin_{\omega}\le x\le TMax_{\omega}$ 则$T2B_{\omega}(x)$是x的(唯一的)ω位模式
        图2-14 重要的数字。图中给出了数值和十六进制表示
  • C语言标准并没有要求要用补码形式来表示有符号整数,但是几乎所有的机器都是这么做的
    • C 库中的文件<limits.h>定义了一组常量,来限定编译器运行的这台机器的不同整型数据类型的取值范围。比如,它定义了常量INT_MAX, INT_MIN, 和UINT_MAX它们描述了有符号和无符号整数的范围
  • Java 标准是非常明确的。它要求采用补码表示。在Java 中,单字节数据类型称为byte而不是char

2.2.4 有符号数和无符号数之间的转换

  • C 语言允许在各种不同的数字数据类型之间做强制类型转换。
  • 对于大多数C 语言的实现,处理同样字长的有符号数和无符号数之间相互转换的一般规则是:数值可能会改变,但是位模式不变
  • 原理:补码转换为无符号数
    对满足$TMin_{\omega}\le x\le TMax_{\omega}$的$x$有:
    $T2U_{\omega}(x)= \begin{cases}a &\text{, }x<0\\ c &\text{, } x \ge 0 \end{cases}$
  • 推导:补码转换为无符号数
    $B2U_{\omega}(T2B_{\omega}(x))=T2U_{\omega}(x)=x+x_{\omega-1}2^{\omega}$
  • 原理:无符号数转换为补码
    对满足$0\le u \le UMax_{\omega}$的$u$有:
    $U2T_{\omega}(u)=\begin{cases} u &\text{, }u \le TMax_{\omega}\\u-2^{\omega} &\text{, } u>TMax_{\omega} \end{cases}$
  • 推导:无符号数转换为补码
    $U2T_{\omega}(u)=-u_{\omega -1}2^{\omega}+u$

2.2.5 C 语言中的有符号数与无符号数

  • 通常,大多数数字都默认为是有符号的
  • 当执行一个运算时,如果它的一个运算数是有符号的而另一个是无符号的,那么C语言会隐式地将有符号参数强制类型转换为无符号数,并假设这两个数都是非负的,来执行这个运算。
    • 对于像<和>这样的关系运算符来说,它会导致非直观的结果
      图2-19 C 语言的升级规则的效果

2.2.6 扩展一个数字的位表示

  • 零扩展(zero extension): 将一个无符号数转换为一个更大的数据类型,我们只要简单地在表示的开头添加0:
    原理:无符号数的零扩展
    定义宽度为ω的位向量$\vec u = [u_{\omega-1}, u_{\omega}, …, u_{0}]$和宽度为 $\omega’$的位向量$\vec u’=[0, …, 0, u_{\omega-1}, u_{\omega}, …, u_{0}]$ 其中ω’>ω。则$B2U_{\omega}(\vec u)=B2U_{\omega ‘}(\vec u’)$
  • 符号扩展(sign extension) : 要将一个补码数字转换为一个更大的数据类型,可以在表示中添加最高有效位的值
    原理:补码数的符号扩展
    定义宽度为ω的位向量$\vec{x}=[x_{u-1}, x_{w-2}, \cdots, x_{0}]$和宽度为ω的位向量$\vec{x}^{\prime}=[x_{w-1}, \cdots, x_{w-1}, x_{w-1}, x_{w-2}, \cdots, x_{0}]$, 其中ω’>ω, 则$B 2 T_{w}(\bar{x})=B 2 T_{w^{\prime}}\left(x^{\prime}\right)$

2.2.7 截断数字

  • 原理:截断无符号数
      1. $\vec x=[x_{\omega-1}, x_{\omega-2}, …, x_0]$
      2. $\vec x’$是将其截断为k位的结果:$\vec x’=[x_{k-1}, x_{k-2}, …, x_{0}]$
      3. $x=B2U_{w}(\vec x)$
      4. $x’=B2U_{k}(\vec x’)$
    • 则 $x’=x \mod 2^{k}$
  • 原理:截断补码数值
      1. $\vec x=[x_{\omega-1}, x_{\omega-2}, …, x_0]$
      2. $\vec x’$是将其截断为k位的结果:$\vec x’=[x_{k-1}, x_{k-2}, …, x_{0}]$
      3. $x=B2U_{w}(\vec x)$
      4. $x’=B2T_{k}(\vec x’)$
    • 则 $x’=U2T_{k}(x \mod 2^{k})$
  • 推导:截断补码数值
    $B2U_{w}([x_{\omega-1}, x_{\omega-2}, …, x_0]) \mod 2^{k}=B2U_{k}[x_{k-1}, x_{k-2}, …, x_{0}]$

2.2.8 关于有符号数与无符号数的建议

unsigned对unsigned,不要混用有符号和无符号

2.3 整数运算

2.3.1 无符号加法

  • 原理:无符号数加法 $+_{w}^{u}$
    对$0 \le x, y<2^{w}$的x和y有:
    $x+_{w}^{u}=\begin{cases} x+y &\text{, } x+y<2^{w} \\x+y-2^{w} &\text{, }2^{w} \le x+y < 2^{w+1} \end{cases}$
  • 运算溢出,是指完整的整数结果不能放到数据类型的字长限制中去
  • 原理:检测无符号数加法中的溢出
    对:在范围$0 \le x,y \le UMax_{w}$中的x和y
    令:$s=x+^{u}_{w}y$
    则:对计算s,当且仅当s<x(或者等价地s<y)时,发生了溢出
  • 推导:检测无符号数加法中的溢出
    1. 如果s 没有溢出,我们能够肯定s≥x
    2. 如果s 确实溢出了,我们就有$s=x+y-2^{w}<x$
  • 原理:无符号数求反
    对:满足$0 \le x < 2^{w}$的任意x
    其w位的无符号逆元$-^{u}_{w}x=\begin{cases} x &\text{, } x=0 \\2^{w}-x &\text{, } x>0\end{cases}$

2.3.2 补码加法

  • 原理:补码加法
    对:满足$-2^{w-1}\le x,y \le 2^{w-1}-1$的整数x和y
    有$x+^{t}_{w}=\begin{cases} x+y-2^{w} &\text{, } 2^{w-1}\le x+y 正溢出 \\x+y &\text{, } -2^{w-1}\le x+y \le 2^{w-1} 正常 \\x+y+2^{w} &\text{, } x+y<-2^{w-1} 负溢出\end{cases}$
  • 推导:补码加法
    $x+^{t}_{w}y=U2T_{w}(T2U_{w}(x) +^{u}_{w} T2U_{w}(y))$
  • 原理:检测补码加法中的溢出
    对满足$TMin_{w} \leqslant x, \quad y \leqslant TMax_{w}$的x和y
    令$s=x+^{t}_{w}y$

    • 正溢出 当且仅当x>0, y>0(或$x+y<TMax_{w}$), s≤0
    • 负溢出 当且仅当x<0, y<0, s≥0

2.3.3 补码的非

  • 原理:补码的非
    对满足$TMin_{w} \le x \le TMax_{w}$的x
    其补码非$-^{t}_{w}x=\begin{cases} TMin_{w} &\text{, } x=TMin_{w} \\-x &\text{, } x>TMin_{w} \end{cases}$

2.3.4 无符号乘法

  • 原理:无符号数乘法
    对满足$0 \le x,y \le UMax_{w}$的x和y
    有$x*^{u}_{w}y=(x·y)\mod 2^{w}$

2.3.5 补码乘法

  • 原理:补码乘法
    对满足$TMin_{w} \le x,y \le TMax_{w}$的x和y
    有$x*^{t}_{w}y=U2T_{w}((x·y)\mod 2^{w})$
  • 原理:无符号和补码乘法的位级等价性
    给定长度为w的位向量$\vec x, \vec y$
    用补码形式的位向量表示来定义整数x和y: $x=B2T_{w}(\vec x), y=B2T_{w}(\vec y)$
    用无符号形式的位向量表示来定义非负整数x’和y’: $x’=B2U_{w}(\vec x), y’=B2U_{w}(\vec y)$
    则$T2B_{w}(x*^{t}_{w}y)=U2B_{w}(x’*^{u}_{w}y’)$

2.3.6 乘以常数

  • 以往,在大多数机器上,整数乘法指令相当慢,需要10个或者更多的时钟周期,然而其他整数运算(例如加法、减法、位级运算和移位)只需要1个时钟周期。因此,编译器使用了一项重要的优化,试着用左移和加法运算的组合来代替乘以常数因子的乘法。
  • 原理:与2的幂相乘的无符号乘法
    C 变量x和k有无符号数值x和k,
    且$0 \le k<w$
    则C 表达式x<<k产生数值:$x*^{u}_{w}2^{k}$

    • 固定大小的补码算术运算的位级操作与其无符号运算等价
      • 产生$x*^{t}_{w}2^{k}$
  • 这样就可以通过快速展开乘数,把乘法变成多次移位
    • x * 14=> (x<<3)+(x<<2)+(x<<1) 因为$14=2^{3}+2^{2}+2^{1}$
    • 甚至可以变成 (x<<4)-(x<<1) 因为$14=2^{4}-2^{1}$

2.3.7 除以2的幂

  • 在大多数机器上,整数除法要比整数乘法更慢——需要30个或者更多的时钟周期。
  • 除以2的幂也可以用右移运算来实现
    • 无符号用逻辑移位
    • 补码数用算术移位
  • 整数除法总是舍入到零
  • 原理:除以2 的幂的无符号除法
    C 变量x 和k 有无符号数值$x$和$k$
    且$0 \le k<w$
    x>>k产生数值$\lfloor x/2^{k} \rfloor$
  • 原理:除以2 的幂的补码除法,向下舍入
    C变量x 和k 分别有补码值x 和无符号数值k
    且$0 \le k<w$
    则当执行算术移位时,C表达式x>>k产生数值$\lfloor x/2^{k} \rfloor$

    • 对于x>0, 变量x 的最高有效位为0, 所以效果与逻辑右移是一样的。
      • 对于非负数来说,算术右移k位与除以$2^{k}$是一样的
  • 原理:除以2 的幂的补码除法,向上舍入
    C 变量x 和k 分别有补码值x和无符号数值k,
    且$0 \le k<w$
    则当执行算术移位时,C 表达式(x+(1<<k)-1)>>k=>$\lfloor x/2^{k} \rfloor$。

    • 也就是说,通过给x增加一个偏量y-1
      然后再将除法向下舍人
      当y整除x时,我们得到q,否则,就得到q+1
  • 算术右移的代码
    (x<0 ? x+(1<>k

2.3.8 关于整数运算的最后思考

  • 计算机执行的“整数”运算实际上是一种模运算形式

2.4 浮点数

  • 浮点表示对形如$V=x \times 2^{y}$的有理数进行编码
  • IEEE读作 eye-triple-ee

2.4.1 二进制小数

  • 形如$b_{m}b_{m-1}\dots b_{1}b_{0}.b_{-1}b{-2}\dots b_{-n+1}b_{-n}$
    $b=\sum^{m}_{i=-n}2^{i}\times b_{i}$

    • 我们只能近似地表示它
    • 增加二进制表示的长度可以提高表示的精度

2.4.2 IEEE浮点表示

  • IEEE 浮点标准用$V=(-1)^{s}\times M \times 2^{E}$E的形式来表示一个数:
    • 符号(sign) $s$决定这数是负数($s=1$)还是正数($s=0$)
      • 而对于数值0的符号位解释作为特殊情况处理。
    • 尾数(significand) $M$是一个二进制小数,它的范围是$[1, 2-\varepsilon]$或者是$[0, 1-\varepsilon ]$
    • 阶码(exponent) $E$的作用是对浮点数加权,这个权重是2的$E$次幂(可能是负数)。
  • 将浮点数的位表示划分为三个字段,分别对这些值进行编码:
    • 一个单独的符号位$s$直接编码符号$s$
    • $k$位的阶码字段exp=$e_{k-1}\cdots e_{1}e_{0}$编码阶码$E$
    • $n$位小数字段frac=$f_{n-1}\cdots f_{1}f_{0}$编码尾数$M$
      • 但是编码出来的值也依赖于阶码字段的值是否等于0。
        图2-32 标准浮点格式(浮点数由3 个字段表示。两种最常见的格式是它们
被封装到32 位(单精度)和64 位(双精度)的字中)
  • 给定位表示,根据exp 的值,被编码的值可以分成三种不同的情况(最后一种情况有两个变种)
    图2-33 单精度浮点数值的分类(阶码的值决定了这个数是规格化的、非规格化的或特殊值)
情况1: 规格化的值
  • 这是最普遍的情况。当exp的位模式既不全为0(数值0),也不全为1(单精度数值为255, 双精度数值为2047)时,都属于这类情况。
  • 阶码字段被解释为以偏置(biased) 形式表示的有符号整数
    • e.g $E=e-Bias$
    • 其中e 是无符号数,其位表示为$e_{k-1}\cdots e_{1}e_{0}$
    • Bias为一个$2^{k-1}-1$(单精度是127, 双精度是1023)的偏置值。
  • 小数字段frac被解释为描述小数值$f$,其中$0\le f<1$
    • 其二进制表示为$0.f_{n-1}\cdots f_{1}f_{0}$
  • 尾数定义为$M=1+f$
    • 这种方式也叫做隐含的以1开头的(implied leading 1)表示
      • 因为可以把$M$看成一个二进制表达式为$1.f_{n-1}\cdots f_{1}f_{0}$的数字。
情况2: 非规格化的值
  • 当阶码域为全0时,所表示的数是非规格化形式。
  • 阶码值是$E=1-Bias$
  • 尾数的值是$M=f$,也就是小数字段的值,不包含隐含的开头的1。
  • 非规格化数有两个用途
    1. 它们提供了一种表示数值0的方法
      • 符号位为0 => +0.0
      • 符号位为1 => -0.0
      • 根据IEEE的浮点格式,值+0.0 和-0.0 在某些方面被认为是不同的,而在其他方面是相同的
    2. 非规格化数的另外一个功能是表示那些非常接近于0的数
      • 它们提供了一种属性,称为逐渐溢出(gradual underflow) ,其中,可能的数值分布均勻地接近于0.0
情况3: 特殊值
  • 当指阶码全为1 的时候出现的
    • 当小数域全为0时,得到的值表示无穷
      • 当$s=0$时是$+\infty$
      • 当$s=1$时是$-\infty$
    • 当我们把两个非常大的数相乘,或者除以零时,无穷能够表示溢出的结果
  • 当小数域为非零时,结果值被称为“NaN”
    • 一些运算的结果不能是实数或无穷, 比如$\sqrt{-1}$或$\infty – \infty$
    • 在某些应用中,表示未初始化的数据时,它们也很有用处

2.4.3 数字示例

图 2-35 8 位浮点格式的非负值示例a=4 的阶码位的和 n 3 的小数位。偏置量是 7)
– 最大非规格化数$\frac{7}{512}$和最小规格化数$\frac{8}{512}$之间的平滑转变
– 这种平滑性归功于我们对非规格化数的$E$的定义。
– 通过将$E$定义为$1-Bias$而不是$-Bias$, 我们可以补偿非规格化数的尾数没有隐含的开头的1。

2.4.4 舍入

  • 舍入(rounding)运算的任务
    • 对于值x,我们一般想用一种系统的方法,能够找到“最接近的”匹配值x’,它可以用期望的浮点形式表示出来。
  • IEEE浮点格式定义了四种不同的舍入方式默认的方法是找到最接近的匹配,而其他三种可用于计算上界和下界。
    1. 向偶数舍入(round-to-even)
      • 也被称为向最接近的值舍入(round-to-nearest), 是默认的方式
      • 它将数字向上或者向下舍人,使得结果的最低有效数字是偶数
      • 在大多数现实情况中避免了统计偏差
        • 在50%的时间里,它将向上舍入,而在50%的时间里,它将向下舍入
    2. 向零舍入方式把正数向下舍入,把负数向上舍入
    3. 向下舍入方式把正数和负数都向下舍人
    4. 向上舍入方式把正数和负数都向上舍人
  • 我们将最低有效位的值0认为是偶数,值1认为是奇数。

2.4.5 浮点运算

  • IEEE 标准指定了一个简单的规则,来确定诸如加法和乘法这样的算术运算的结果:
    把浮点值x和y看成实数,
    而某个运算$\odot$定义在实数上
    计算将产生$Round(x\odot y)$

    • 这是对实际运算的精确结果进行舍入后的结果。
  • IEEE还制定一些规则规定含有特殊值的运算
    • 比如1/-0.0和1/+0.0
  • 对于浮点数加法$x+^{f}y$
    • 对于所有x和y的值,这个运算是可交换的
    • 这个运算是不可结合的
      • 比如(3.14+1e10)-1e10求值得到0.0——因为舍入,值3.14会丢失。
      • 3.14+(1e10-1e10)得出值3.14。
    • 另一方面,浮点加法满足了单调性属性
      • 若a≥b,那么对于任何a,b以及x的值,除了NaN,都有x+a≥x+b
  • 对于浮点数乘法$x*^{f}y$ – 定义为$Round(x\times y)$
    • 这个运算在乘法中是封闭的(虽然可能产生无穷大或NaN)
    • 可交换的
    • 乘法单位元为1.0
    • 不具有可结合性
      • 由于可能发生溢出,或者由于舍人而失去精度
    • 在加法上不具备分配性
    • 浮点乘法满足下列单调性:
      a≥b 且 c≥0 => $a*^{f}c \ge a*^{f}b$
      a≤b 且 c≤0 => $a*^{f}c \le a*^{f}b$
    • 还可以保证,只要a≠NaN,就有$a*^{f}a \ge 0$

2.4.6 C 语言中的浮点数

  • 当程序文件中出现下列句子时,编译器GCC会定义程序常数INFINITY(表示$+\infin$)和NAN(表示NaN):
    #define _GNU_SOURCE 1
    #include <math.h>
    
  • 当在int、 float 和double 格式之间进行强制类型转换时,程序改变数值和位模式的原则如下(假设int 是32 位的):
    • 从int转换成float 数字不会溢出,但是可能被舍入。
    • 从int或float转换成double能够保留精确的数值。
    • 从double 转换成floatÿ 因为范围要小一些,所以值可能溢出成$+\infin$或$-\infin$另外,由于精确度较小,它还可能被舍人。
    • 从float 或者double 转换成intÿ 值将会向零舍入
[深入理解计算机系统] 01 计算机系统漫游 笔记

[深入理解计算机系统] 01 计算机系统漫游 笔记

计算机 ComputerScience|计算机原理 ComputerSystem


@ZYX 写于2020年07月08日

第一章 计算机系统漫游

前言

  • 计算机系统是由硬件和系统软件组成的,它们共同工作来运行应用程序。

1.1 信息就是位+上下文

  • hello程序的生命周期是从一个源程序(或者说源文件)开始的 , 即程序员利用编辑器创 建并保存的文本文件
  • 源程序实际上就是一个由值0和1组成的位(bit) 序列
    • 8个位被组织成一组,称为字节
    • 每个字节表示程序中某个文本字符
      • 大部分系统都使用ASCII来记录字符
      • 这种方式实际上就是用一个单字节大小的整数值来表示每个字符
      • 文本文件:只由ASCII字符构成的文件
        • 二进制文件: 所有其他文件

1.2 程序被其他程序翻译成不同的格式

  • hello程序的生命周期
    1. 从一个高级C语言程序开始,这种形式能够被人读懂
    2. 为了在系统上运行hello.c,每条C语句都被转化为低级机器语言指令
    3. 这些指令按照称为可执行目标程序的格式打包,并以二进制磁盘文件的形式存放起来
      • 目标程序也称为可执行目标文件
  • 编译系统: 四个阶段的程序(预处理器编译器汇编器链接器

    1. 预处理阶段
      • 预处理器(cpp) 根据以字符#开头的命令,修改原始的C程序。
      • 结果就得到了另一个C程序,通常是以.1作为文件扩展名
    2. 编译阶段
      • 编译器(cel) 将文本文件hello.i翻译成文本文件hello.S,它包含一个汇编语言程序。
        • 汇编语言非常有用,因为它为不同高级语言的不同编译器提供了通用的输出语言
    3. 汇编阶段
      1. 汇编器(as) 将hello.s翻译成机器语言指令
      2. 把这些指令打包成一种叫 可重定位目标程序(relocatable object program) 的格式
      3. 并将结果保存在目标文件hello.o中。
    4. 链接阶段
      • 链接器(Id) 就负责处理这种合并。
      • 结果就得到hello文件,它是一个可执行目标文件(或者简称为可执行文件)
        • 可以被加载到内存中,由系统执行。

1.3 了解编译系统如何工作是大有益处的

  • 有一些重要的原因促使程序员必须知道编译系统是如何工作的,其原因如下:
    1. 优化程序性能
      为了在C程序中做出好的编码选择,需要了解机器代码以及编译器将不同的C语句转化为机器代码的方式
    2. 理解链接时出现的错误
    3. 避免安全漏洞
      e.x 缓冲区溢出错误是造成大多数网络和服务器上安全漏洞的主要原因

1.4 处理器读并解释存储在存储器中的指令

  • 要想在Unix系统上运行可执行文件,我们将它的文件名输入到称为外壳(shell) 的应用程序中
unix> ./hello
hello, world
unix>
  • shell是一个命令行解释器
    1. 它输出一个提示符
    2. 等待你输入一个命令行
    3. 然后执行这个命令
    • 如果该命令行的第一个单词不是shell命令,外壳就会假设是可执行文件的名字,它将加载并运行这个文件

1.4.1 系统的硬件组成

  1. 总线
    • 贯穿整个系统的是一组电子管道,称做总线
    • 它携带信息字节并负责在各个部件间传递
    • 通常总线被设计成传送定长的字节块,也就是字(word)
      • 字中的字节数(即字长)是一个基本的系统参数
        • 有的是4个字节(32位),有 的是8个字节(64位)
  2. I/O设备
    • 输入/输出(I/O)设备是系统与外部世界的联系通道
    • 我们的示例系统包括4个I/O设备:
      1. 键盘:用户输入
      2. 鼠标:用户输入
      3. 显示器:用户输出
      4. 磁盘驱动器(简单地说就是磁盘): 长期存储数据程序
    • 每个I/O设备都通过一个控制器适配器与I/O总线相连
      • 控制器和适配器之间的区别主要在于封装方式:
        1. 控制器是置于I/O设备本身或者系统的主印制电路板(通常称为主板)上的芯片组
        2. 适配器是一块插在主板插槽上的
  3. 主存
    • 是一个临时存储设备
    • 在处理器执行程序时,存放:
      1.程序和程序处理的数据
    • 由一组动态随机存取存储器(DRAM)芯片组成的
      • 从逻辑上来说,存储器是一个线性字节数组
        • 每个字节都有其唯一的地址(即数组索引),这些地址是从零开始的
        • 一般来说,组成程序的每条机器指令都由不同数量的字节构成
        • 与C程序变量相对应的数据项大小是根据类型变化的
  4. 处理器
    • 中央处理单元(CPU),简称处理器,是解释(或执行)存储在主存中指令的引擎。
    • 核心是一个字长的存储设备(或寄存器),称为程序计数器(PC)。
      • 在任何时刻,PC都指向主存中的某条机器语言指令(即含有该条指令的地址)
    • 从系统通电,到断电,处理器一直在
      1. 执行PC指向的指令,
      2. 再更新程序计数器,使其指向下一条指令。
    • 类似按照一个非常简单的指令执行模型来操作的
      • 这个模型是由指令集结构决定的
      • 指令按照严格的顺序执行,这里“执行”包含执行一系列步骤:
        1. 读取:处理器从PC指向的存储器处读取指令
        2. 解释:解释指令中的位
        3. 执行:执行指令指示的简单操作
        4. 更新:更新PC,使其指向下一条指令
          • 这条指令并不一定与存储器中刚刚执行的指令相邻。
            • 比如 if else之类的工作流
      • 操作是围绕着主存寄存器文件(register file)和算术/逻辑单元(ALU)进行的
        • 寄存器文件是一个小的存储设备
          • 由一些1字长的寄存器组成,每个寄存器都有唯一的名字
        • ALU计算新的数据地址值
    • 但是实际上现代处理器使用了非常复杂的机制来加速程序的执行
      • 因此可以这样区分处理器的指令集结构微体系结构
        • 指令集结构描述的是每条机器代码指令的效果
        • 微体系结构描述的是处理器实际上是如何实现的

1.4.2 运行hello程序

  • 运行hello程序时发生了什么:
    1. shell程序执行它的指令: 等待我们输入一个命令
    2. 输入 “./hello”并回车
    3. shell程序将字符逐一读入寄存器
    4. 最后把寄存器中的字符存放到存储器
      图片

1.5 高速缓存至关重要

  • 复制数据就是开销,减缓了程序“真正的”工作。因此,设计者的一个主要目标就是使这些复制操作尽可能快地完成
  • 根据机械原理,较大的存储设备要比较小的存储设备运行得慢,而快速设备的造价远高于同类的低速设备
    • 一个典型的寄存器文件只存储几百字节的信息,而主存里可存放几十亿字节。
    • 处理器从寄存器文件中读数据的速度比从主存中读取几乎要快100倍
  • 针对这种处理器与主存之间的差异,系统设计者釆用了更小、更快的存储设备,即高速缓存存储器(简称高速缓存)
    • 作为暂时的集结区域,用来存放处理器近期可能会需要的信息
    • L1和L2:
      容量 速度
      L1 数万字节 几乎和访问寄存器文件一样快
      L2 数十万到数百万字节 比访问L1的时间长5倍,比访问主存的时间快5〜10倍
      • L1和L2高速缓存是用一种叫做静态随机访问存储器(SRAM) 的硬件技术实现的
      • 比较新的、处理能力更强大的系统甚至有L3高速缓存
    • 系统可以获得一个很大的存储器,同时访问速度也很快,
      • 原因是利用了高速缓存的局部性原理,即程序具有访问局部区域里的数据和代码的趋势
      • 大部分的存储器操作都能在快速的高速缓存中完成。

1.6 存储设备形成层次结构

  • 在处理器和一个又大又慢的设备(例如主存)之间插入一个更小更快的存储设备(例如高速 缓存)的想法已经成为了一个普遍的观念
  • 每个计算机系统中的存储设备都被组织成了一个存储器层次结构
  • 从上至下,设备变得访问速度越来越慢、容量越来越大,并且每字节的造价也越来越便宜
    Figure 1.9 An example of a memory hierarchy.
  • 存储器层次结构的主要思想是一层上的存储器作为低一层存储器的高速缓存
  • 程序员同样可以利用对整个存储器层次结构的理解来提高程序性能

1.7 操作系统管理硬件

  • shell和hello程序都依靠操作系统提供的服务来访问键盘、显示器、磁盘或者主存
  • 操作系统是应用程序硬件之间插入的一层软件
    • 所有应用程序对硬件的操作尝试都必须通过操作系统。
  • 操作系统有两个基本功能:
    1. 防止硬件被失控的应用程序滥用
    2. 向应用程序提供简单一致的机制来控制复杂而又通常大相径庭的低级硬件设备
      Figure 1.10 Layered view of a computer system.
  • 操作系统通过几个基本的抽象概念进程、虚拟存储器和文件)来实现这两个功能
    • 文件是对I/O设备的抽象表示
    • 虚拟存储器是对主存磁盘I/O设备的抽象表示
    • 程则是对处理器主存I/O设备的抽象表示
      Figure 1.11 Abstractions provided by an operating system.

1.7.1 进程

  • 进程是操作系统对一个正在运行的程序的一种抽象。
  • 在一个系统上可以同时运行多个进程,而每个进程都好像在独占地使用硬件
  • 并发运行,则是说一个进程的指令和另一个进程的指令是交错执行的
  • 一个CPU看上去都像是在并发地执行多个进程
    • 这是通过处理器在进程间切换来实现的。
    • 操作系统实现这种交错执行的机制称为上下文切换
  • 上下文
    • 定义:操作系统保持跟踪进程运行所需的所有状态信息
    • 上下文切换:
      • 当操作系统决定要把控制权从当前进程转移到某个新进程时,就会进行上下文切换,即:
        1. 保存当前进程的上下文
        2. 恢复新进程的上下文
        3. 然后将控制权传递到新进程。
  • 从一个进程到另一个进程的转换是由操作系统的内核kernel管理的
    • 内核是操作系统代码常驻主存的部分
    • 当应用程序需要操作系统的某些操作时,他就执行系统调用system call指令,将控制权传递给内核。然后内核执行被请求的操作返回应用程秀
      Figure 1.12 Process context switching.

1.7.2 线程

  • 在现代系统中,一个进程实际上可以由多个称为线程执行单元组成
    • 每个线程都运行在进程的上下文中,并共享同样的代码和全局数据

1.7.3 虚拟内存

  • 虚拟内存为每个进程提供了一个假象,即每个进程都在独占地使用主存
  • 每个进程看到的是一致的存储器,称为虚拟地址空间
    Figure 1.13 Process virtual address space.
    请注意,图中的地址是从下往上增大的

  • 在Linux中,地址空间
    • 最上面的区域是为操作系统中的代码和数据保留的,这对所有进程来说都是一样的。
    • 底部区域存放用户进程定义的代码和数据
  • 每个进程看到的虚拟地址空间由大量准确定义的构成,每个区都有专门的功能。
    1. 程序代码和数据:
      • 代码是从同一固定地址开始,紧接着的是和C全局变量相对应的数据位置
      • 代码和数据区是直接按照可执行目标文件的内容初始化的
    2. 堆:
      • 当调用如malloc和free这样的C标准库函数时,可以在运行时动态地扩展和收缩
    3. 共享库:
      • 大约在地址空间的中间部分是一块用来存放像C标准库和数学库这样共享库的代码和数据的区域
    4. 栈:runtime stack
      • 编译器用它来实现函数调用
      • 用户栈在程序执行期间可以动态地扩展和收缩
    5. 内核虚拟存储器:
      • 内核总是驻留在内存中,是操作系统的一部分。地址空间顶部的区域是为内核保留的,
      • 不允许应用程序读写这个区域的内容或者直接调用内核代码定义的函数。
      • 基本思想是把一个进程虚拟存储器的内容存储在磁盘上,然后用主存作为磁盘的高速缓存

1.7.4 文件

  • 文件就是字节序列,仅此而已
  • 系统中的所有输入输出都是逋过使用一小组称为Unix-I/O的系统函数调用读写文件来实现的

1.8 系统之间利用网络通信

  • 实际上,现代系统经常通过网络和其他系统连接到一起。
  • 从一个单独的系统来看,网络可视为一个I/O设备

  • 随着Internet出现,将一台主机的信息复制到另外一台主机已经成为计算机系统最重要的用途之一

  • telnet

1.9 重要主题

总结一下我们旋风式的系统漫游: 系统是硬件和系统软件互相交织的集合体,它们必须共同协作以达到运行应用程序的最终目的

1.9.1 Amdahl 定律

  • 主要思想:
    • 当我们对系统的某个部分加速时,其对系统整体性能的影响取决于-该部分的重要性+加速程度
    • 参数:
      1. $T_{old}$ : 系统执行某应用程序的时间
      2. α : 该程序可提升部分所需时间的占比
      3. k :该部分可提升的比例
    • 可以推出:
      1. $alpha T_{old}$ :可提升部分所需时间
      2. $(alpha T_{old})/k$ :提升后,该部分所需时间
    • 提升后的整个程序所需时间:
      $T_{new} = (1-alpha)T_{old} + (alpha T_{old})/k = T_{old}[(1-alpha)+alpha /k]$
    • 加速比:
      $S=frac{1}{(1-alpha)+alpha/k}$
    • 推论
      • 要想显著加速整个系统,必须提升系统中相当大的部分的’速度

1.9.2 并发和并行

  • 有两个需求是驱动进步的持续动力:
    1. 一个是我们想要计算机做得更多,
    2. 另一个是我们想要计算机运行得更快
  • 并发(concurrency)是一个通用的概念,指一个同时具有多个活动的系统
  • 并行(parallelism)指的是用并发使一个系统运行得更快
    • 可以在系统的多个抽象层次上运用。(这里强调三个层次)
  1. 线程级并发
    • 构建在进程这个抽象之上,我们能够设计出同时执行多个程序的系统,这就导致了并发。
    • 单处理器系统
      • 即使处理器必须在多个任务间切换,大多数实际的计算也都是由一个处理器来完成的系统不
    • 多处理器系统
      • 一个由单操作系统内核控制的多处理器组成的系统
      • 随着多核处理器和超线程(hyperthreading)的出现,这种系统才变得常见。
      • 多核处理器是将多个CPU(称为“核”)集成到一个集成电路芯片上
        • 每个核都有自己的L1和L2高速缓存
        • 但是它们共享更高层次的高速缓存,以及到主存的接口。
      • 超线程有时称为同时多线程(simultaneous multi-threading)
        • 是一项允许一个CPU执行多个控制流的技术
        • 它涉及CPU某些硬件有多个备份:比如 PC和寄存器文件
        • 而其他的硬件部分只有一份,比如执行浮点算术运算的单元。
        • 超线程的处理器可以在单个周期的基础上决定要执行哪一个线程
          • 这使得CPU能够更好地利用它的处理资源
      • 多处理器的使用可以从两个方面提高系统性能:
        1. 它减少了在执行多个任务时模拟并发的需要
        2. 它可以使应用程序运行得更快
  2. 指令级并行
    • 在较低的抽象层次上,现代处理器可以同时执行多条指令的属性称为指令级并行
    • 其实每条指令从开始到结束需要长得多的时间,大约20个或者更多的周期,但是是处理器使用了非常多的聪明技巧来同时处理多达100条的指令。
    • 如果处理器可以达到比一个周期一条指令更快的执行速率,就称之为超标量 (superscalar) 处理器
  3. 单指令、多数据并行
    • 允许一条指令产生多个可以并行执行的操作,这种方式称为单指令、多数据,即SIMD并行。
    • 提供这些SIMD指令多是为了提高处理影像、声音和视频数据应用的执行速度

1.9.3 计算机系统中抽象的重要性

  • 抽象的使用是计算机科学中最为重要的概念之一
[CCNA学习指南] 第一章 网络互联 Internetworking

[CCNA学习指南] 第一章 网络互联 Internetworking

网络 Network


@ZYX 写于2020年07月01日

第一章 网络互联 Internetworking

摘要

CCNA考点

  • Describe how a network works>
  • Describe the purpose and functions of various network devices
  • Select the components required to meet a network specification
  • Use the OSI and TCP/IP models and their associated protocols to explain how data flows in a network
  • Describe common networked applications including web applications
  • Describe the purpose and basic operation of the protocols in the OSI and TCP models
  • Describe the impact of applications (Voice over IP and Video over IP) on a network
  • Interpret network diagrams
  • Describe the components required for network and Internet communications
  • Identify and correct common network problems at layers 1, 2, 3, and 7 using a layered model approach
  • Differentiate between LAN/WAN operation and features
  • Configure, verify, and troubleshoot a switch with VLANs and interswitch communications
  • Explain network segmentation and basic traffic management concepts
  • Implement an IP addressing scheme and IP Services to meet network requirements in a medium-size Enterprise branch office network
  • Explain the operation and benefits of using DHCP and DNS
  • Configure, verify, and troubleshoot basic router operation and routing on Cisco devices

章节顺序

  1. Internetworking basics
  2. Network segmentation
  3. How bridges, switches, and routers are used to physically and logically segment a network
  4. How routers are employed to create an internetwork

1.1 网络互联基础 Internetworking Basics

  1. 模拟一个交流场景 Bob -=- HUB -=- Sally
    1. This network is actually one collision domain and one broadcast domain
    2. they’re both on the same LAN connected with a multiport repeater (a hub).
    3. Bob is actually going to use Sally’s MAC address to get ahold of her.
    4. How to get MAC?
      1. Bob is going to start with name resolution (hostname to IP address resolution), using Domain Name Service (DNS).
        • if these two are on the same LAN, Bob can just broadcast to Sally asking her for the information (no DNS needed)
        • since the two hosts are on a local LAN, Bob will just broadcast to resolve the name Sally (192.168.0.255 is a broadcast address)
          Source|Destination|Protocol|Info
          192.168.0.2|192.168.0.255|NBNS|Name query NB SALLY<00>
          EthernetII,Src:192.168.0.2(00:14:22:be:18:3b),Dst:Broadcast(ff:ff:-ff:ff:ff:ff)
        • shows that Bob knows his own MAC address and source IP address
        • but not Sally’s IP address or MAC address
        • so Bob sends a broadcast address of
          • all fs for the MAC address (a Data Link layer broadcast)
          • and an IP LAN broadcast of 192.168.0.255
    5. Next, check out Sally’s response:
      Source Destination Protocol Info
      192.168.0.3 192.168.0.2 ARP 192.168.0.3 is at 00:0b:db:99:d3:5e
      192.168.0.3 192.168.0.2 NBNS Name query response NB 192.168.0.3
  2. break up one large network into a bunch of smaller ones
    • because user response will have dwindled to a slow crawl as the network grew and grew
    • The answer breaking up a big network into a number of smaller ones—network segmentation
      • using devices like routers, switches, and bridges
  3. some causes of LAN traffic congestion:
    • Too many hosts in a broadcast or collision domain
    • Broadcast storms
    • Too much multicast traffic
    • Low bandwidth
    • Adding hubs for connectivity to the network
  4. hubs don’t segment a network; they just connect network segments together.
    1. an inexpensive way to connect a couple of PCs together, which is great for home use and troubleshooting
  5. routers
    1. are used to
      1. connect networks together
      2. and route packets of data from one network to another
    2. break up a broadcast domain
      1. broadcast domain: the set of all devices on a network segment that hear all the broadcasts sent on that segment
      2. Breaking up a broadcast domain is important
        1. because when a host or server sends a network broadcast, every device on the network must read and process that broadcast unless you’ve got a router
    3. when the router’s interface receives this broadcast, it can discard the broadcast without forwarding it on to other networks
    4. break up collision domains as well.
    5. Advantage of using router
      1. They don’t forward broadcasts by default.
      2. They can filter the network based on layer 3 (Network layer) information (e.g., IP address).
    6. function summary:
      1. Packet switching
      2. Packet filtering
      3. Internetwork communication
      4. Path selection
    7. routers are really switches: they’re actually what we call layer 3 switches
      1. router vs "switch"
        1. layer 2 switches, which forward or filter frames,
          1. they’re employed to add functionality to a network LAN
            1. The main purpose of a switch: to optimize its performance—providing morebandwidth for the LAN’s users
          2. switches only “switch” frames from one port to another within the switched network
          3. switches break up collision domains:
            • collision domains: a network scenario wherein one particular device sends a packet on a network segment, forcing every other device on that same segment to pay attention to it
            • If at the same time a different device tries to transmit, leading to a collision, both devices must retransmit, one at a time.
            • This situation is typically found in a hub environment
            • each and every port on a switch represents its own collision domain
        2. Every Switch port creates only 1 single broadcast domain
        3. routers (or layer 3 switches):
          1. use logical addressing
          2. and provide what is called packet switching.
          3. Routers can also provide packet filtering by using access lists,
    8. internetwork:
      1. when routers connect two or more networks together and use logical addressing (IP or IPv6), this is called an internetwork.
  6. bridging:
    1. bridges and switches basically do the same thing
      • break up collision domains on a LAN
    2. LAN switches use bridging technologies, so Cisco still refers to them as multiport bridges
    3. use a bridge in a network to
      1. reduce collisions within broadcast domains
      2. and to increase the number of collision domains in your network
        • Doing this provides more bandwidth for users

1.2 网络互联模型 Internetworking Models

  • The OSI model was meant to create interoperable network devices and software
    • in the form of protocols
    • so that different vendor networks could work with each other
      1. binding: at a particular layer, the communication processes that are related to each other are bound
      2. The OSI model:
      3. is hierarchical
      4. Advantage:
      5. divides the process into smaller and simpler components
        1. aiding component development, design, and troubleshooting
      6. allows multiple-vendor development through standardization of network components
      7. encourages industry standardization by defining what functions occur at each layer of the model
      8. allows various types of network hardware and software to communicate.
      9. prevents changes in one layer from affecting other layers
      10. One of the greatest functions is to assist in data transfer between disparate hosts
      11. The OSI has 7 different layers, divided into 2 groups:
      12. The top three layers define how the applications within the end stations will communicate with each other and with users:
      13. Application 应用层
        • Provides a user interface
          • File, print, message, database, and application services
      14. Presentation 表示层
        • Presents data
        • handles processing such as encryption
          • Data encryption, compression, and translation services
      15. Session 会话层
        • Keeps different applications’ data seperate
          • Dialog control
        • none of the upper layers knows anything about networking or network
          addresses
      16. the four bottom layers define 1 how data is transferred through a physical wire or through switches and routers 2 how to rebuild a data stream from a transmitting host to a destination host’s application
      17. Transport 传输层:
        1. Provides reliable or unreliable delivery
        2. Perofrms error correction before retransmit
          • End-to-end connection
      18. Network 网络层:
        1. Provides logical addressing which routers use for path determination
          • Routing
      19. Data Link 数据链路层
        1. Combines packets -> bytes -> frames
        2. Provides access to media using MAC
        3. Performs error detection (not correction)
          • Framing
      20. Physical 物理层
        1. Moves bits between devices
        2. Specifies volage, wire speed, and pin-out of cables(电缆针脚)
          • Physical topology
      21. The following network devices operate at all seven layers of the OSI model:
      22. Network Management Stations (NMSs)
      23. Web and application servers
      24. Gateways (not default gateways)
      25. Network hosts

1.3.1 Application Layer 应用层

  1. marks the spot where users actually communicate to the computer
  2. This layer acts only when access to the network is going to be needed
    • 若不涉及网络应用,不会用到应用层。比如浏览本地网页
  3. Application layer is acting as an interface between the actual application program and the next layer down
    • by providing ways to send information down through the protocol stack
    • this means that Microsoft Word, for example, does not reside at the Application layer but instead interfaces with the Application layer protocols
  4. is also responsible for identifying and establishing the availability of the intended communication partner and determining whether sufficient resources for the intended communication exist.
  5. often unites communicating components from more than one network application

1.3.2 Presentation Layer 表示层

  1. presents data to the Application layer
  2. is responsible for
    1. data translation
    2. code formatting.
      • essentially a translator and provides coding and conversion functions
  3. ensures that data transferred from the Application layer of one system can be read by the Application layer of another one.
  4. Tasks like data compression, decompression, encryption, decryption, and some multimedia operations are associated

1.3.3 Session Layer 会话层

  1. is responsible for setting up, managing, and then tearing down sessions between Presentation layer entities
  2. provides dialog control between devices, or nodes
  3. coordinates communication between systems and serves to organize their communication by:
    1. simplex 单工
    2. half duplex 半双工
    3. and full duplex 全双工
      • keeps different applications’ data separate

1.3.4 Transport Layer 传输层

  1. segments data from upper-layer applications and unite it into the same data stream.
  2. provide end-to-end data transport services
  3. establish a logical connection between the sending host and destination host on an internetwork.
  4. TCP UDP
    • is responsible for:
      1. providing mechanisms for multiplexing upper-layer applications
      2. establishing sessions
      3. tearing downvirtual circuits
      4. hides details of any network-dependent information from the higher layers by providing transparent data transfer
    • reliable networking:
      acknowledgments, sequencing, and flow control will be used.
  5. The Transport layer can be connectionless or connection oriented
  6. Flow Control
    • Data integrity is ensured at the Transport layer by maintaining flow control
      1. prevents a sending host from overflowing the buffers in the receiving host
      2. Reliable data transport employs a connection-oriented communications session, and the protocols involved ensure that the following will be achieved:
      3. The segments delivered are acknowledged back to the sender upon their reception.
      4. Any segments not acknowledged are retransmitted.
      5. Segments are sequenced back into their proper order upon arrival at their destination.
      6. A manageable data flow is maintained in order to avoid congestion, overloading, and data loss.
  7. Connection-Oriented Communication 面向连接的通信
    1. In reliable transport operation, a device that wants to transmit sets up a connection-oriented communication session with a remote device by creating a session:
      1. first establishes a session with its peer system, which is called a call setup or a three-way handshake
      2. Data is then transferred
      3. Finally a call termination takes place to tear down the virtual circuit
    2. While the information is being transferred, the two machines periodically check in with each other to ensure that the data is being received properly
    3. summary of the steps in the connection-oriented session—the three-way handshake:
      1. The first “connection agreement” segment is a request for synchronization.
      2. The next segments acknowledge the request and establish connection parameters. These segments request that the receiver’s sequencing is synchronized here as well so that a bidirectional connection is formed.
      3. The final segment is also an acknowledgment. It notifies the destination host that the connection agreement has been accepted and that the actual connection has been established. Data transfer can now begin.
    4. Buffer: when a machine receives a flood of datagrams too quickly for it to process, it stores them in a memory section called a buffer:
      • 如果缓存已满,之后的数据将被丢弃
    5. Instead of dumping data and allowing data to be lost, the transport can issue a “not ready” indicator to the sender.
    6. In connection-oriented data transfer, datagrams are delivered to the receiving host in the same sequence they’re transmitted:
      • the transmission fails if:
        1. this order is breached
        2. any data segments are lost, duplicated, or damaged along the wa
      • solved by having the receiving host acknowledge that it has received each and every data segment.
    7. A service is considered connection oriented if it has the following characteristics:
      1. A virtual circuit is set up (e.g., a three-way handshake).
      2. It uses sequencing.
      3. It uses acknowledgments.
      4. It uses flow control.
        • The types of flow control are buffering, windowing, and congestion avoidance
  8. Windowing 窗口技术
    • the sender uses the break as an opportunity to transmit more data
      • because there’s time available before it finishes processing acknowledgments from the receiving machine,
    • The quantity of data segments (measured in bytes) that the transmitting machine is allowed to send without receiving an acknowledgment is called a window.
      1. Windows are used to control the amount of outstanding, unacknowledged data segments.
        • So the size of the window controls how much information is transferred
    • If a receiving host fails to receive all data, the host can decrease the window size.
  9. Acknowledgments 确认
    • through something called positive acknowledgment with retransmission
      • Reliable data delivery guarantees that the data won’t be duplicated or lost
        1. requires a receiving machine send an acknowledgment message back to the sender when it receives data
        2. When sending a segment, the transmitting machine starts a timer and retransmits if it expires before an acknowledgment is returned

1.3.5 Network Layer 网络层

  1. manages device addressing
  2. tracks the location of devices on the network
  3. and determines the best way to move data
    • must transport traffic between devices that aren’t locally attached (Router)
  4. 步骤:
    1. when a packet is received on a router interface, the destination IP address is checked
    2. 2 Conditions:
      1. If the packet isn’t destined for that particular router
        1. it will look up the destination network address in the routing table
        2. nce the router chooses an exit interface, the packet will be sent to that interface to be framed and sent out on the local network
      2. If the router can’t find an entry for the packet’s destination network in the routingtable
        • the router drops the packet
  5. Two types of packets are used at the Network layer: data and route updates:
    1. Data packets: Used to transport user data through the internetwork
      • Protocols used to support data traffic are called routed protocols
        • IPv4 IPv6
    2. Route update packets: Used to update neighboring routers about the networks connected to all routers within the internetwork.
      • Protocols that send route update packets are called routing protocols
        • RIP EIGRP OSPF
  6. The routing table includes the following information:
    1. Network addresses 网络地址: Protocol-specific network addresses
      • must maintain a routing table for individual routed protocol
        • because each routed protocol keeps a network with a different addressing scheme
    2. Interface 接口: The exit interface a packet will take when destined
    3. Metric 度量值: The distance to the remote network
  7. Because each interface in a router represents a separate network, it must be assigned unique network identification numbers, and each host on the network connected to that router must use the same network number.
    • Here are some points about routers that you should really commit to memory:
      1. Routers, by default, will not forward any broadcast or multicast packets.
      2. Routers use the logical address in a Network layer header to determine the next hop router to forward the packet to.
      3. Routers can use access lists, created by an administrator, to control security on the types of packets that are allowed to enter or exit an interface.
      4. Routers can provide layer 2 bridging functions if needed and can simultaneously route through the same interface.
      5. Layer 3 devices (routers in this case) provide connections between virtual LANs (VLANs).
      6. Routers can provide quality of service (QoS) for specific types of network traffic.

1.3.6 Data Link Layer 数据链路层

  1. provides the physical transmission of the data
  2. handles error notification, network topology, and flow control
    • This means that the Data Link layer will
      1. ensure that messages are delivered to the proper device on a LAN using hardware addresses
      2. will translate messages from the Network layer into bits for the Physical layer to transmit
  3. Data Frame:
    • The Data Link layer formats the message into pieces, each called a data frame,
    • and adds a customized header containing the hardware destination and source address
  4. For a host to send packets to hosts on a local network as well as transmit packets between routers, the Data Link layer uses hardware addressing.
  5. Each time a packet is sent between routers,
    1. it’s framed with control information at the Data Link layer,
    2. but that information is stripped off at the receiving router and only the original packet is left.
      • This framing of the packet continues for each hop until the packet is finally delivered to the correct receiving host.
      • the packet itself is never altered along the route;
      • only encapsulated with the type of control information.
  6. The IEEE Ethernet Data Link layer has two sublayers:
    1. Media Access Control (MAC) 802.3 Layer:
      • Defines how packets are placed on the media
      • Contention media access is “first come/first served” access where everyone shares the same bandwidth
        1. Physical addressing, logical topologies is defined:
          • logical topology: the signal path through a physical topology
        2. Line discipline, error notification (not correction), ordered delivery of frames, and optional flow control can also be used at this sublayer
    2. Logical Link Control (LLC) 802.2 Layer:
      • Responsible for identifying Network layer protocols and then encapsulating them
      • LLC header tells the Data Link layer what to do with a packet once a frame is received
        • A host look in the header to find out where the packet is destined, 比如网络层的IP协议
      • The LLC can also provide flow control and sequencing of control bits.
  7. switches and bridges both work at the Data Link layer and filter the network using hardware (MAC) addresses:
    1. Layer 2 switching is considered hardware-based bridging because it uses specialized hardware called an application-specific integrated circuit (ASIC).
      • can run up to gigabit speeds with very low latency rates
        • Latency is the time measured from when a frame enters a port to when it exits a port.
    2. Bridges and switches read each frame as it passes through the network.
    3. The layer 2 device then puts the source hardware address in a filter table and keeps track of which port the frame was received on
      • to determine the location of the specific sending device
    4. LOCATION is important
    5. After a filter table is built, it will forward frames only to the segment where the destination hardware address is located:
      1. If the destination device is on the same segment as the frame, the layer 2 device will block the frame from going to any other segments
      2. If the destination is on a different segment, the frame can be transmitted only to that segment. This is called transparent bridging.
    6. When a switch interface receives a frame with a destination hardware address that isn’t in the filter table, it will forward the frame to all connected segments:
      1. If the unknown device replies to this forwarding action, the switch updates its filter table
        • But in the event the destination address of the transmitting frame is a broadcast address, the switch will forward all broadcasts to every connected segment by default
        • All devices that the broadcast is forwarded to are considered to be in the same broadcast domain. This can be a problem: layer 2 broadcast storms

1.3.7 Physical Layer 物理层

  1. It sends bits and receives bits
  2. The Physical layer communicates directly with the various types of actual communication media(介质)
    • Different kinds of media represent these bit values in different ways
  3. specifies the electrical, mechanical, procedural, and functional requirements for activating, maintaining, and deactivating a physical link between end systems
  4. This layer is also where you identify the interface between the data terminal equipment (DTE) and the data communication equipment (DCE)
    • The DCE is usually located at the service provider, while the DTE is the attached device
  5. Hubs at the Physical Layer
    1. a hub is really a multiple-port repeater:
      • receives a digital signal
      • reamplifies or regenerates that signal
      • and then forwards the digital signal out all active ports
    2. This means all devices plugged into a hub are in the same collision domain as well as in the same broadcast domain
    3. Every device connected to the hub, or hubs, must listen if a device transmits
已到首页—已到末页