title: PAT
date: 2020-01-06 07:26:48
tags:

• 2020
  top_img: https://cdn.jsdelivr.net/gh/RangerWang/butterfly_cdn@v0.5/top_img/wallpaper11.jpg
  cover: https://cdn.jsdelivr.net/gh/RangerWang/butterfly_cdn@v0.5/top_img/wallpaper11.jpg
  toc: true
  toc_number: true
  mathjax: true
  categories:
• history
• 2020
• 408
  comments: true
  password: 333
  message: ‘抱歉, 此乃南墙, 请回头…’

Morning Reading

• 数据结构（45）
• 计算机组成原理（45）
• 计算机网络（25）
• 计算机操作系统（35）

Data Structure

大纲

[考查目标]

1。掌握数据结构的基本概念、基本原理和基本方法。
2。掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复
杂度与空间复杂度的分析。
3。能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用 C 或 C++语言
设计与实现算法的能力。

一、线性表

（一）线性表的定义和基本操作
（二）线性表的实现
1。顺序存储
2。链式存储
3。线性表的应用

二、栈、队列和数组

（一）栈和队列的基本概念
（二）栈和队列的顺序存储结构
（三）栈和队列的链式存储结构
（四）栈和队列的应用
（五）特殊矩阵的压缩存储

三、树与二叉树

（一）树的基本概念
（二）二叉树
1。二叉树的定义及其主要特征
2。二叉树的顺序存储结构和链式存储结构
3。二叉树的遍历
4。线索二叉树的基本概念和构造
（三）树、森林
1。树的存储结构
2。森林与二叉树的转换
3。树和森林的遍历
（四）树与二叉树的应用
1。二叉排序树
2。平衡二叉树
3。哈夫曼（Huffman）树和哈夫曼编码

四、图

（一）图的基本概念
（二）图的存储及基本操作
1。邻接矩阵法
2。邻接表法
3。邻接多重表、十字链表
（三）图的遍历
1。深度优先搜索
2。广度优先搜索
（四）图的基本应用
1。最小（代价）生成树
2。最短路径
3。拓扑排序
4。关键路径

五、查找

（一）查找的基本概念
（二）顺序查找法
（三）分块查找法
（四）折半查找法
（五）B 树及其基本操作、B+树的基本概念
（六）散列（Hash）表
（七）字符串模式匹配
（八）查找算法的分析及应用

六、排序

（一）排序的基本概念
（二）插入排序
1。直接插入排序
2。折半插入排序
（三）气泡排序（bubble sort）
（四）简单选择排序
（五）希尔排序（shell sort）
（六）快速排序
（七）堆排序
（八）二路归并排序（merge sort）
（九）基数排序
（十）外部排序
（十一）各种内部排序算法的比较
（十二）排序算法的应用

Introduction

graph LR
    A(绪论) --- B(数据结构)

    B --- B1(逻辑结构)
    B --- B2("存储结构(物理结构)")
    B --- B3(数据的运算)
    B1 --- B11("线性结构: 线性表, 栈, 队列")
    B1 --- B12("非线性结构: 树, 图, 集合")

    A --- C(五个特征)
    C --- C1(算法定义)
    C --- C2("五个特性: 有穷, 确定, 可行, 输出, 输出")
    C --- C3(效率的度量)
    C3 --- C11(时间复杂度)
    C3 --- C12(空间复杂度)

基本概念和术语

数据, 数据元素, 数据对象, 数据类型, 抽象数据类型, 数据结构

抽象数据类型(ADT): 指一个数据模型及定义在该模型上的一组操作; 其定义仅取决于它的一组逻辑特性; 常用(数据对象, 数据关系, 基本操作集)表示

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。包含三方面内容(逻辑结构, 存储结构和数据运算)

• 数据的逻辑结构

    graph LR    
        A(数据的逻辑结构) --- B(线性结构)
        B --- B1(一般线性表)
        B --- B2(受限线性表)
        B2 --- B21(栈和队列)
        B2 --- B22(串)
        B --- B3(线性表推广)
        B3 --- B31(数组)
        B3 --- B32(广义表)
        A --- C(非线性结构)
        C --- C1(集合)
        C --- C2(树形结构)
        C2 --- C21(一般树)
        C2 --- C22(二叉树)
        C --- C3(图状结构)
        C3 --- C31(有向图)
        C3 --- C32(无向图)
  

• 存储结构

  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储(Hash存储)

算法和算法评价

• 时间复杂度

  算法中所有语句的频度之和记为 T(n), 时间复杂度主要分析 T(n)的数量级。
  常用算法中基本运算的频度 f(n)来分析算法的时间复杂度. 记为 T(n) = O(f(n))
  常见的渐近时间复杂度为:

  O(1) < O($log{2}n$) < O(n) < O($nlog{2}n$) < O($n^2$) < O($n^3$) < O($2^n$) < O($n!$) < O($n^n$)

• 空间复杂度

Linear List

graph LR
    A(线性表) --- B(顺序存储)
    B --- B1(顺序表)
    A(线性表) --- C(链式存储)
    C --- C1(单链表)
    C1 --- C5(指针实现)
    C --- C2(双链表)
    C2 --- C5
    C --- C3(循环链表)
    C3 --- C5(指针实现)
    C --- C4("静态链表(借助数组实现)")

顺序存储

• 定义

  #define InitSize 100
  typedef struct {
      ElemType *data;
      int MaxSize, length;
  }
  

• 线性表中的位序从1开始，数组中的元素的下标是从0开始的
• 主要特点: 随机访问，即通过首地址和元素序号可在时间O(1)内找到指定元素。
• 存储密度高，每个节点只存储输出元素
• O(n) 插入，删除，顺序查找

链式存储

链表，无论单链表，双链表还是循环链表，一定要保证不断链。

单链表

• 定义

    typedef struct LNode{
    ElemType data;
        struct LNode *next;
          }LNode, *LinkList
  

  ```

• 不管带不带头结点，头指针始终指向链表的第一个结点

• 头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。(加入头结点，空表和非空表的处理得到统一)

• O(n)

  • 头插法建立单链表
  • 尾插发建立单链表
  • 按序号查找结点值
  • 按值查找表结点
  • 插入结点操作
  • 删除结点操作
  • 求表长操作

双链表

• 定义

  typedef struct DNode{
      ElemType data;
      struct DNode *prior,*next;
  } DNode, *DLinklist;
  

循环单链表

• 循环单链表
• 循环双链表

静态链表

借助数组来描述线性表的链式存储结构，这里的指针是结点的相对地址(数组下标)，又称游标。

如何选取存储结构

• 基于存储考虑

  难以估计线性表的长度或存储规模时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储结构的存储密度是小于1的。

• 基于运算考虑

  • 若经常做的运算时按序号访问数据元素，则显然顺序表优于链表。
  • 在顺序表中进行插入、删除操作时，平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的。
  • 在链表中进行插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。

• 基于环境的考虑

  • 顺序表容易实现，任何高级语言中都有数组类型；链表的操作时基于指针的，相对来讲，前者实现较为简单
  • 通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表宜选择链式存储。

Stack and Queue

复习提示

• 本章通常以选择题的形式考查，题目不算难，但命题形式灵活，也容易出现在算法设计题中。
• 其中栈(出入栈的过程、出栈序列的合法性) 和 队列的操作及其特征是重点。
• 此外，栈和队列的顺序存储结构、链式存储结构及其特点、双端队列的特点、栈和队列的常见应用，以及数组和特殊矩阵的压缩存储都是读者必须掌握的内容。

graph LR
    A(线性表)-- 操作受限 ---B1(栈)
    B1 --- B11(顺序栈)
    B1 --- B12(链栈)
    B1 --- B13(共享栈)
    A(线性表)-- 操作受限 ---B2(队列)
    B2 --- B21(循环队列)
    B2 --- B22(链式队列)
    B2 --- B23(双端队列)
    A-- 推广 ---C(数组)
    C --- C1(一维数组)
    C --- C2("多维数组: 压缩存储, 稀疏矩阵")

栈

栈(Stack) 只允许在一端进行插入或删除操作的线性表。

• 顺序栈

  #define MaxSize 50
  typedef struct{
      Elemtype data[MaxSize];
      int top;
  } SqStack;
  

  • 栈顶指针: S.top, 初始时设置S.top=-1; 栈顶元素: S.data[S.top]
  • 进栈操作: 栈不满时，栈顶指针先加1，再送值到栈顶元素。
  • 出栈操作: 栈非空时，先取栈顶元素值，再将栈顶指针减1。
  • 栈空条件: S.top == -1;栈满条件: S.top == MaxSize-1; 栈长: S.top+1

• 共享栈

  两个顺序栈共享一个一维数组空间
  - top0=-1时，0号栈为空， top1=MaxSize时1号栈为空
  - 栈满，仅当两个栈顶指针相邻(top1 - top0)=1 时，判断为栈满。
  

• 链栈

  typedef struct Linknode{
      ElemType data;
      struct Linknode *next;
  } *LiStack;
  

  • 多个栈共享存储空间
  • 不存在栈满上溢,通常采用单链表实现
  • 规定所有操作都在表头进行

队列

队列(Queue) 只允许在表的一端进行插入，而在表的另一端进行删除

队列的顺序存储

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front, rear;
} SqQueue;

存在 假溢出 的现象

循环队列

初始时: Q.font=Q.rear=0
队首指针进1: Q.front=(Q.front+1)%MaxSize
队尾指针进1: Q.rear=(Q.rear+1)%MaxSize
队列长度: (Q.rear+MaxSize-Q.front)%MaxSize

区分队满还是队空，三种处理方式:

1. (普遍)牺牲一个存储单元来区分队空和队满，即队头指针在队尾指针的下一位置作为队满的标志

   队满条件: (Q.rear+1)%MaxSize==Q.front
   队空条件: Q.front==Q.rear
   

2. 类型中增设表示元素个数的数据成员

   队空条件: Q.size==0
   队满条件: Q.size==MaxSize
   队满队空都有Q.front==Q.rear
   

3. 类型中增设tag数据成员，以区分是队满还是队空。

   1. tag等于0时，若因删除导致Q.front==Q.rear，则为队空。
   2. tag等于1时，若因插入导致Q.front==Q.rear, 则为队满。

队列的链式存储

typedef struct{
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct{
    LinkNode *front, *rear;
} LinkQueue;

• 当Q.front==NULL 且Q.rear==NULL时, 链式队列为空
• 用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。

双端队列

输出受限的双端队列，输入受限的双端队列

• 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。4132
• 能由输出受限的双端队列得到，但不能有输入受限的双端队列得到的输出序列。4213
• 既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。4231

栈和队列的应用

• 栈在括号匹配中的应用
• 栈在表达式求值中的应用
• 栈在递归中的应用
• 队列在层次遍历中的应用
• 队列在计算机系统中的应用

特殊矩阵的压缩存储

即最小空间存储矩阵，矩阵在计算机图形学，工程计算中占有举足轻重的地位。数据结构考虑的是如何用最小的内存空间来存储同样一组数据，并能方便地提取矩阵中的元素。

数组一旦被定义，其维数和维界就不再改变。

• 数组的存储结构
  • 一个数组的所有元素在内存中占用一段连续的存储空间。
• 矩阵的压缩存储
• 稀疏矩阵

总结

在考研真题中，链式栈出现的概率要比顺序栈低得多。

Tree and Binary Tree

复习提示

• 本章多以选择题的形式考查，但也会涉及树遍历相关的算法题
• 树和二叉树的性质、遍历操作、转换、存储结构和操作特性等
• 满二叉树、完全二叉树，线索二叉树、哈夫曼树的定义和性质
• 二叉排序树和二叉平衡树的性质和操作等，都是选择题必然会涉及的内容

graph LR
    A(树形结构) --- B(二叉树)
    B --- B1("概念: 定义, 存储结构")
    B --- B2("操作")
    B --- B3("应用")
    B2 --- B21("三种遍历")
    B2 --- B22("线索二叉树")
    B3 --- B31("排序二叉树 ---- 平衡二叉树")
    B3 --- B32(哈夫曼树)
    A(树形结构) --- C(树和森林)
    C --- C1("概念: 定义, 存储结构")
    C --- C2(操作)
    C2 --- C21(与二叉树的转换)
    C2 --- C22(遍历)
    C --- C3("应用: 并查集")

树具有如下最基本的性质:

1. 树种的结点树等于所有结点的度数加 1。
2. 度为 m 的树种第 i 层上至多有 $m^{i-1}$ 个结点。(i $\ge$ 1)
3. 高度为 h 的 m 叉树至多有 $(m^h-1)/(m-1)$ 个结点
4. 具有 n 个结点的 m 叉树的最小高度为 $\lceil log_m{(n(m-1)+1)} \rceil$

树结点与度之间的关系有:

1. 总结点数 = $n_0+n_1+n_2+…+n_m$
2. 总分支数 = $1n_1+2n_2+…+mn_m$
3. 总结点数 = 总分支数 + 1

二叉树

• 几个特殊的二叉树

  • 满二叉树
  • 完全二叉树
  • 二叉排序树
  • 平衡二叉树

• 二叉树的性质

  • $n_0=n_2+1$
  • 非空二叉树上第 K 层上至多有 $2^{K-1}$个结点 $(k\ge1)$
  • 高度为 h 的二叉树至多有 $2^h-1$ 个结点
  • 具有 n 个 (n > 0) 结点的完全二叉树的高度为 $\lceil log_2(n+1)\rceil 或 \lceil log_2n\rceil+1$

• 顺序存储结构

• 链式存储结构

  typedef struct BiTNode{
      ElemType data;
      struct BiTNode *lchild, *rchild;
  } BiTNode, *BiTree;
  

  • 在含有 n 个结点的二叉链表中，含有 n + 1个空链域
  • 非空指针树 = 总分支数 = n - 1
  • 空指针树 = n + 1

二叉树的遍历

按照某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

• common

• 由遍历序列构造二叉树, 先中，后中，层中

• 常见有: 先序(PreOrder)、中序(InOrder) 和后序(PostOrder)。

  • 时间复杂度都是O(n).
  • 递归遍历中，递归工作栈的栈深恰好为树的深度。

• 递归算法和非递归算法的转换

  • 借助栈

    void InOrder2(BiTree T){
        InitStack(S);
        BiTree p=T;
        while(p||!IsEmpty(s)) {
            if(p) {
                Push(S, p);
                p = p->lchild;
            } else {
                Pop(S, p);
                visit(p);
                p = p->rchild;
            }
        }
    }
    

• 层次遍历

  • 借助队列

    void LevelOrder(BiTree T) {
        InitQueue(Q);
        BiTree p;
        EnQueue(Q,T);
        while(!IsEmpty(Q)) {
            DeQueue(Q,p);
            visit(p);
            if (p->lchild != NULL)
                EnQueue(Q, p->lchild);
            if (p->rchild != NULL)
                EnQueue(Q, p->rchild);
        }
    }
    

线索二叉树

• 线索，指向前驱或后继的指针。

    typedef struct ThreadNode {
    ElemType data; 
        struct ThreadNode *lchild, *rchild; // 左右孩子指针
        int ltag, rtag;
    } ThreadNode, *ThreadTree;
  

• 线索二叉树的构造

  

  void InThread(ThreadTree &p, ThreadTree &pre) {
      // 中序遍历对二叉树线索化的递归算法
      if (p != NULL) {
          InThread(p->lchild, pre);
          if (p->lchild == NULL) {
              p->lchild = pre;
              p->ltag = 1;
          }
          if (pre != NULL && pre->rchild==NULL) {
              pre->rchild = p;
              pre->rtag = 1;
          }
          pre = p;
          InThread(p->rchild, pre);
      }
  }
  
  void CreateInThread(ThreadTree T) {
      ThreadTree pre=NULL;
      if (T != NULL) {
          InThread(T, pre);
          pre->rchild=NULL;
          pre->rtag=1;
      }
  }
  

  树,森林

  • 存储结构

    • 双亲表示法

      #define MAX_TREE_SIZE 100
      typedef struct {
          ElemType data;
          int parent;
      } PTNode;
      typedef struct {
          PTNode nodes[MAX_TREE_SIZE];
          int n;
      }PTree;
      

    • 孩子表示法

    • 孩子兄弟表示法, 又称二叉树表示法

      typedef struct CSNode {
          ElemType data;
          struct CSNode *firstchild, *nextsibling;
      } CSNode, *CSTree
      

      • 最大的优点是可以方便地实现树转换为二叉树的操作。

  • 树，森林和二叉树的转换

  • 树和森林的遍历

    • 先根遍历
    • 后根遍历

  • 树的应用 —— 并查集

树和二叉树的应用

• 二叉排序树 (BST)

  • 二叉排序树的非递归查找

    BSTNode *BST_Search(BiTree T, ElemType key, BSTNode *&p) {
        p=NULL;
        while (T!=NULL && key!=T->data) {
            p=T;
            if (key < T->data) T=T->lchild;
            else T=T->rchild;
        }
        return T;
    }
    

  • 二叉排序树的插入

    int BST_Insert(BiTree &T, KeyType k){
        if (T == NULL) {
            T = (BiTree)malloc(sizeof(BSTNode));
            T->key=k;
            T->lchild=T->rchild=NULL;
            return 1;
        } else if (k == T->key){
            return 0;
        } else if (k < T->key)
            return BST_Insert(T->lchild, k);
    }
    

  • 二叉排序树的构造

    void Create_BST(BiTree &T, KeyType str[], int n) {
        T=NULL;
        int i=0;
        while(i<n){
            BST_Insert(T,str[i]);
            i++;
        }
    }
    

• 平衡二叉树

  任意结点的左右子树高度差的绝对值不超过1，将这样的二叉树成为平衡二叉树，简称平衡树(AVL)。定义高度差为平衡因子，可能取值为-1,0,1。

  • 调整规律

    • LL平衡旋转(右单旋转)
    • RR平衡旋转(左单旋转)
    • LR平衡旋转(先左后右双旋转)
    • RL平衡旋转(先右后左双旋转)

  • 平衡二叉树的查找

    含有 n 个结点的平衡二叉树的最大深度为O($log_2{n}$)，因此平衡二叉树的平均查找长度为$O(log_2{n})$。

• 哈夫曼树和哈夫曼编码

  • common

    • 从树的根结点到任意结点的路径长度 (经过的边数)与该结点上权值的乘积，称为该结点的带权路径长度。

    • 树种所有叶节点的带权路径长度之和称为该树的带权路径长度，记为$WPL=\sum{i=1}^{n}w{i}l_{i}$。

      $w_i是第i个叶节点所带的权值，l_i是该叶节点到根结点的路径长度$

    • 在含有n个带权叶子结点的二叉树中，其中带权路径长度(WPL) 最小的二叉树称为哈夫曼树，也称最优二叉树。

  • 哈夫曼树的构造

    • 每个初始结点最终都成为叶节点，且权值越小的结点到跟结点的路径长度越大。
    • 构建过程中共新建了$n-1$个结点，因此哈夫曼树种的结点总数为$2n-1$。

  • 哈夫曼编码

总结

• 本章的内容较多，其中二叉树是极其重要的考点。
• 遍历是二叉树的各种操作的基础，统考时会考察遍历过程中对结点的各种其他操作，而且容易结合递归算法和利用栈或队列的非递归算法。
• 读者需重点掌握各种遍历方法的代码书写，并学会在遍历的基础上，进行一些其他的相关操作。
• 其中递归算法短小精悍，出现的概率较大，请读者不要掉以轻心，要做到对几种遍历方式的程序模板烂熟于心，并结合一定数量的习题，才可以在考试中快速地写出漂亮的代码。

Graph

图$G$由顶点集$V$和边集$E$组成，记为$G=(V，E)$。有向图$: v为弧尾，w为弧头$。无向图$(v, w)$

复习提示

• 图算法的难度较大，因此主要掌握深度优先搜索与广度优先搜索，其他内容以算法题形式出现的概率不高。
• 应掌握
  • 图的基本概念及基本性质、
  • 图的存储结构（邻接矩阵、邻接表、邻接多重表和十字链表）及其特性
  • 存储结构之间的转化
  • 基于存储结构上的遍历操作和各种应用(拓扑排序、最小生成树、最短路径和关键路径)
• 图的相关算法较多、易混，但通常只要求掌握其基本思想和实现步骤(能手动模拟)，而算法的具体实现则不是重点

graph LR
    A(图) --- B(图的定义)
    A(图) --- C(图结构的存储)
    C --- C1("邻接矩阵法, 邻接表法")
    C --- C2("邻接多重表法, 十字链表")
    A(图) --- D(图的遍历)
    D --- D1(深度优先遍历)
    D --- D2(广度优先遍历)
    A(图) --- E(图的相关应用)
    E --- E1("最小生成树: Prim算法, Kruskal算法")
    E --- E2("最短路径: Dijkstr算法, Floyd算法")
    E --- E3("拓扑排序: AOV网")
    E --- E4("关键路径: AOE网")

定义

• 有向图，无向图，简单图，多重图，完全图(简单完全图)，子图，

• 连通，连通图和连通分量

  • 无向图中，顶点 $v$ 到顶点 $w$ 有路径存在，则称 $v$ 和 $w$ 是连通的。
  • 无向图中，若图$G$中任意两个顶点都是连通额，则称图$G$为连通图。
  • 无向图中的极大连通子图称为连通分量。极大即要求该连通子图包含其所有的边，极小连通子图 是既要保持图连通又要使得边数最少的子图。

• 强连通图、强连通分量

  • 有向图中，$v 到 w ，w 到 v$ 都有路径，则称两个顶点是强连通的。
  • 有向图中，图中任意一对顶点都是强连通的，则称此图为强连通图。
  • 有向图中的极大强连通子图称为有向图的强连通分量

• 生成树、生成森林

  • 连通图的生成树包含图中全部顶点的一个极小连通子图，若顶点数为 $n$，则它的生成树含有 $n-1$ 条边。

  • 在非连通图中，连通分量的生成树构成了非连通图的生成森林。

• [顶点的度、入度和出度]

• 边的权和网、[稠密图、稀疏图]、[路径、路径长度和回路]、[简单路径、简单回路]、距离、有向树

图的存储及基本操作

• 临接矩阵法，指用一个一维数组存储图中顶点信息，用一个二维数组存储图中边的信息(即各顶点之间的临接关系)，存储顶点之间临接关系的二维数组称为邻接矩阵。

  #define MaxVertexNum 100                        // 图顶点数目的最大值
  typedef char VertexType;                        // 顶点的数据类型
  typedef int EdgeType;                            // 带权图中边上权值的数据类型
  typedef struct {
      VertexType Vex[MaxVertexNum];                // 顶点表
      EdgeType Edge[MaxVertexNum][MaxVertexNum];    // 邻接矩阵，边表
      int vexnum, arcnum;                            // 图的当前顶点数和弧数
  } MGraph;
  

  • 邻接矩阵表示法的空间复杂度为$O(n^2)$，其中 n 为图的顶点数$\vert V \vert$
  • 1 为存在边，0 为不存在边

• 邻接表法，是对图$G$中的每个顶点$v_i$建立一个单链表，这个单链表称为边表。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）。

  

  #define MaxVertexNum 100        // 图中顶点数目的最大值
  typedef struct ArcNode {        // 边表结点
      int adjvex;                    // 该弧所指向的顶点的位置
      struct ArcNode *next;        // 指向下一条弧的指针
      // InfoType info;            // 网的边权值
  }ArcNode;
  typedef struct VNode {            // 顶点表结点
      VertexType data;            // 顶点信息
      ArcNode *first;                // 指向第一条依附该顶点的弧的指针
  }VNode, AdjList[MaxVertexNum];
  typedef struct {
      AdjList vertices;            // 邻接表
      int vexnum, arcnum;            // 图的顶点数和弧数
  } ALGraph;                        // ALGraph是以邻接表存储的图类型
  

  • 顶点表结点 [ 顶点域(data)，边表头指针(firstarc) ]，边表结点 [ 邻接点域(adjvex)，指针域(nextarc)]

• 十字链表，是有向图的一种链式存储结构

  

  #define MaxVertexNum 100            // 图中顶点数目的最大值
  typedef struct ArcNode {            // 边表结点
      int tailvex, headvex;            // 该弧的头尾结点
    struct AcrNode *hlink, *tlink;    // 分别指向弧头相同和弧尾相同的结点
      // InfoType info;                // 相关信息指针
  } ArcNode;
  typedef struct VNode {                // 顶点表结点
      VertexType data;                // 顶点信息
      ArcNode *firstin, *firstout;    // 指向第一条入弧和出弧
  } VNode;
  typedef struct {
      VNode xlist[MaxVertexNum];        // 邻接表
      int vexnum, arcnum;                // 图的顶点数和弧数
  } GLGraph;                            // GLGraph 是以十字邻接存储的图类型
  

  • 顶点结点 [data，firstin，firstout]
  • 弧结点 [tailvex，headvex，hlink，tlink，info]

• 邻接多重表，是无向图的另一种链式存储结构。

  

  #define MaxVertexNum 100            // 图中顶点数目的最大值
  typedef struct ArcNode {            // 边结点
      bool mark;                        // 访问标记
      int ivex, jvex;                    // 分别指向该弧的两个结点
      struct ArcNode *ilink, *jlink;    // 分别指向两个顶点的下一条边
      // InfoType info;                // 相关信息指针
  } ArcNode;        
  typedef struct VNode {
      VertexType data;                // 顶点表结点
      ArcNode *firstedge;
  } VNode;
  typedef struct {
      VNode adjmulist[MaxVertexNum];
      int vexnum, arcnum;
  } AMLGraph;
  

  • 顶点结点 [data，firstedge]
  • 边结点 [mark，ivex，ilink，jvex，jlink，info]

• 图的基本操作

  • Adjacent(G, x, y)
  • Neighbors(G, x)
  • InsertVertex(G, x)
  • DeleteVertex(G, x)
  • AddEdge(G, x, y)
  • RemoveEdge(G, x, y)
  • FirstNeighbor(G, x): 存在，返回顶点号，不存在，返回 -1.
  • NextNeighbor(G, x, y): 存在，返回顶点号，不存在，返回 -1.
  • Get_edge_value(G, x, y)
  • Set_edge_value(G, x, y, v)

图的遍历

• Intro
  • 图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。
  • 树是一种特殊的图。
  • 几乎所有图的搜索算法，都可以抽象为优先级搜索或最佳优先搜索。

• 对于同样一个图，基于邻接矩阵存储的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS和BFS序列是不唯一的。

• 广度优先搜索，(Breadth-First-Search, BFS)

  • info

    • 会优先考虑最早被发现的顶点，也就是离起点越近的顶点其优先级越高。
    • 类似于二叉树的层序遍历算法，借助队列。
    • Dijkstra 单源最短路径算法和 Prim最小生成树算法也应用了类似的思想。
    • 图的广度优先遍历还可用于求一些问题的最优解，但初试方面很难涉及。
    • 邻接表存储$O(\vert V \vert+\vert E \vert)$；邻接矩阵存储$O(\vert V \vert^2)$。
    • 在广度遍历的过程中，我们可以得到一颗遍历树，称为广度优先生成树。

  • 广度优先所有算法的伪代码如下：

    bool visited[MAX_VERTEX_NUM];
    void BFSTraverse(Graph G) {
        // 对图G进行广度优先遍历，设访问函数为visit()
        for (i=0; i<G.vexnum; ++i)        
            visited[i] = false;                // 访问标记数组初始化
        InitQueue(Q);                        // 初始化辅助队列Q
        for (i=0; i<G.vexnum; ++i)            // 从 0 号顶点开始遍历
            if (!visited[i])                // 对每个连通分量调用一次BFS
                BFS(G, i);                    // Vi未访问过，从Vi开始BFS
    }
    void BFS(Graph G, int v) {
        visit(v);                            // 访问初始顶点v
        visited[v] = true;                    // 对v做已访问标记
        Enqueue(Q, v);                        // 顶点 v 入队列
        while(!isEmpty(Q)) {
            DeQueue(Q, v);                    // 顶点 v 出队列
            for (w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G, v, w)
                                             // 检测 v 所有邻接点
                 if (!visited[w]) {            // w 为 v 的尚未访问的邻接顶点
                     visit(w);                // 访问顶点 w
                     visited[w] = true;        // 对w做已访问标记
                     EnQueue(Q, w);
                 } //if
        } // while
    }
    

  • BFS算法求解单源最短路径问题(最少边数，非带权)

    void BFS_MIN_Distance(Graph G, int u) {
        //d[i]表示从 u 到 i 结点的最短路径
        for (i=0; i<G.vexnum; ++i)
            d[i] = ∞;                        // 初始化路径长度
        visited[u] = true; d[u] = 0;
        EnQueue(Q, u);
        while(!isEmpty(Q)) {                // BFS算法主过程
            DeQueue(Q, u);                    // 队头元素出队
            for (w=FirstNeighbor(G, u); w>=0; w=NextNeighbor(G, u, w))
                if (!visited[w]) {            // w为u的尚未访问的邻接顶点
                    visited[w] = true;        // 设已访问标记
                    d[w] = d[u] + 1;        // 路径长度加1
                    EnQueue(Q, w);            // 顶点w入队
                } // if
        } //while
    }
    

• 深度优先搜索 (Depth-First-Search, DFS)

  • info

    • 会优先考虑最后被发现的顶点，广泛应用于人工智能方面。
    • 类似于树的先序遍历(借助递归工作栈)，所遵循的策略是尽可能”深”地搜索一个图。
    • 邻接矩阵 $O(\vert V \vert^2)$；邻接表 $\vert V \vert+\vert E \vert$ 。
    • 对连通图调用DFS才能产生深度优先生成树，否则产生的将是深度优先生成森林。

  • 算法过程如下

    bool visited[MAX_VERTEX_NUM];            // 访问标记数组
    void DFSTraverse(Graph G) {
        // 对图G进行深度优先遍历，访问函数为visit()
        for (v=0; v<G.vexnum; ++v)
            visited[v] = false;
           for (v=0; v<G.vexnum; ++v)
            if (!visited[v])
                DFS(G, V);
    }
    void DFS(Graph G, int v) {
        // 从顶点 v 出发, 采用递归思想，深度优先遍历图G
        visit(v);                            // 访问顶点
        visited[v] = true;                    // 设已访问标记
        for (w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G, v, w))
            if (!visited[w]) {                // w 为 u 的尚未访问的邻接顶点
                DFS(G, w);
                // if 
            }
    }
    

图的应用

本节是历年考查重点。图的应用主要包括: 最小生成(代价)树，最短路径，拓扑排序和关键路径。一般，直接以算法设计题形式考查的可能性很小，而更多的是结合图的实例来考查算法的具体执行过程，读者必须学会手工模拟给定图的各个算法的执行过程。此外，还需掌握对给定模型建立相应的图去解决问题的方法。

• 最小生成树

  • 性质：不唯一；边的权值之和唯一；边数为顶点数减1
  • 算法：Prim(普里姆)，适于求解边稠密的图的最小生成树。
  • 算法：Kruskal(克鲁斯卡尔)，是一种按权值的递增次序选择合适的边来构成最小生成树的方法，适于边稀疏而顶点多的图。

• 最短路径，带权路径长度最短的那条路径称为最短路径。

  • Dijkstra。
    • 常用于求解带权有向图中某个源点到其余各顶点的最短路径。
    • 基于贪心算法
  • Floyd-Warshall。

• 拓扑排序

  • Info

    • 有向无环图，简称DAG图。
    • AOV网，DAG图中，顶点表示活动，有向边表示活动的先后关系。
    • 拓扑排序是对有向无环图的顶点的一种排序。
    • 对一般图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

  • 算法实现

    bool TopologicalSort(Graph G) {
        // 若G存在拓扑序列，返回true; 否则返回false,这时 G 中存在环
        InitStack(S);                            // 初始化栈，存储入度为0的顶点
        for (int i=0; i<G.vexnum; i++)
            if (indegree[i]==0)
                Push(S, i);                        // 将所有入度为 0 的顶点进栈
        int count = 0;                            // 计数，记录当前已经输出的顶点数
        while(!IsEmpty(S)) {                    // 栈不空，则存在入度为 0 的顶点
            Pop(S, i);                            // 栈顶元素出栈
            print[count++]=i;                    // 输出顶点 i.
            for (p=G.vertices[i].firstarc; p ; p=p->nextarc) {
                // 将所有 i 指向的顶点的入度间1，并且将入度减为0的顶点压入栈 S
                v = p->adjvex;
                if (!(--indegree[v]))
                    Push(S, v);                    // 入度为0， 则入栈
            } // for
        } // while
        if (count<G.vexnum)
            return false;                        // 排序失败，有向图中有回路
        else
            return true;                        // 拓扑排序成功
    }
    

• 关键路径

  • Info

    • 在带权有向图中，顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销(如完成活动所需的时间)，则称这种有向图为用边表示活动的网络，简称AOE网。
    • 性质
      • 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
      • 只有在进入某一顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
    • AOE网中，仅有一个入度为0的顶点(开始顶点，源点)，也仅有一个出度为0的顶点(结束顶点，汇点)
    • AOE网中具有最大路径长度的路径称为关键路径，关键路径上的活动称为关键活动。
    • AOE网中的路径并不唯一，关键路径上的活动都是关键活动，决定整个过程的关键因素。

  • 寻找关键活动时所用到的几个参量的定义。

    1. 事件$v_k$的最早发生事件$v_e(k)$

       $v_e(源点)=0$

       $v_e(k)=Max{v_e(j)+Weight(v_j, v_k)}, Weight(v_j, v_k)表示上的权值$

    2. 事件$v_j$的最迟发生事件$v_l(j)$

       $v_l(汇点)=v_e(汇点)$

       $v_l(j)=Min{v_l(k)-Weight(v_j, v_k)}, Weight(v_j, v_k)表示上的权值$

    3. 活动$a_i$的最早开始事件$e(i)$

       该时间是指该活动的起点所表示的事件最早发生的时间。

       若边$$表示活动$a_i$，则有$e(i)=v_e(k)$

    4. 活动$a_i$的最迟开始事件$l(i)$

       该时间是指该活动的终点所表示的事件最迟发生时间与该活动所需时间之差。

       若边$$表示活动$ai$，则有$l(i)=v_l(j)-Weight(v_k,v_j)$

    5. 一个活动$a_i$的最迟开始时间$l(i)$和其最早开始时间$e(i)$的差额$d(i)=l(i)-e(i)$

       它是指该活动的时间余量，即活动$a_i$可拖延的时间。

       称$l(i)-e(i)=0$即$l(i)=e(i)$的活动$a_i$是关键活动。

Searching

复习提示

本章是考研命题的终点

• 对应散列查找，应掌握散列表的构造、冲突处理方法(各种方法的处理过程)、查找成功和查找失败的平均查找长度、散列查找的特征和性能分析。
• 对于折半查找，应掌握折半查找的过程、构造判定树、分析查找成功和查找失败的平均查找长度等
• B树和B+ 树是本章的难点，对于B树，考纲要求掌握插入、删除和查找的操作过程，不要求掌握算法；对于B+ 树，仅要求了解其基本概念和性质。
• 串部分需要重点掌握next数组的构造方法。

graph LR
    A(查找) --- B("基本概念: 静态查找, 动态查找")
    A --- C(线性结构)
    C --- C1(顺序查找)
    C --- C2(折半查找)
    C --- C3(分块查找)
    A --- D(树形结构)
    D --- D1(二叉排序树)
    D --- D2(二叉平衡树)
    D --- D3(B树, B+树)
    A --- E("散列结构 ---- 散列表")
    E --- E1(性能分析)
    E --- E2(冲突处理)
    A --- F("效率指标 --- 平均查找长度")
    F --- F1(查找成功)
    F --- F2(查找失败)

基本概念

• 查找，查找表，
• 静态查找：顺序查找，折半查找，散列查找等
• 动态查找：二叉排序树的查找，散列查找。（二叉平衡树和B树都是二叉排序树的改进）
• 关键字，平均查找长度(ASL，衡量查找算法效率的最主要的指标)

顺序查找

又称线性查找，主要用于在线性表中进行查找。

• 一般线性表的顺序查找

  typedef struct {
      ElemType *elem;        // 元素存储空间基址，建表时按实际长度分配，0号单元留空
      Int TableLen;
  }SSTable;
  int Search_Seq(SSTable ST, ElemType key) {
      ST.elem[0] = key;
      for (i=ST.TableLen;ST.elem[i]!=key;--i);
      return i;
  }
  

  • ST.elem[0] = key 称为 “哨兵”，可以避免很多不必要的判断语句，从而提高程序效率。
  • $ASL{成功}=\frac{n+1}{2}\qquad ASL{不成功}=n+1$
  • 缺点: 当 n 较大时，平均查找长度较大，效率低。
  • 优点: 对数据元素的存储没有要求，顺序存储或链式存储皆可。
  • 注意：对线性链表只能进行顺序查找。

• 有序表的顺序查找

  • $ASL{成功}=\frac{n+1}{2}; ASL{不成功}=\frac{n}{2}+\frac{n}{n+1}$
  • 比一般的顺序查找算法好一些
  • 注意：有序表的顺序查找和后面的折半查找的思想是不一样的，且有序表的顺序查找中的线性表可以是链式存储结构。

折半查找

又称二分查找，仅适用于有序的顺序表。

• 算法

  int Binary_Search(SeqList L, ElemType key) {
      int low=0, high=L.Tablelen-1, mid;
      while (low<=high) {
          mid=(low+high)/2;
          if (L.elem[mid] == key)
              return mid;
          else if (L.elem[mid] > key)
              high=mid-1;
          else
              low=mid+1;
      }
      return -1;
  }
  

  • $ASL\approx log_2(n+1)-1$，判定树种的树高$h=\lceil log_2(n+1) \rceil$
  • 即$O(log_2n)$，平均情况下比顺序表查找的效率高。
  • 折半查找仅适用于线性表的顺序存储结构，不适合与链式存储结构，且要求元素按关键字有序排列。

分块查找

• 又称索引顺序查找，结合顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。

• 块内无序，块间有序

• 分为两步
  1. 在索引表中确定待查记录所在的块，可以顺序或折半查找索引表。
  2. 在块内顺序查找。

B树

B+树

散列表

串

Sorting

复习提示

• 堆排序（建堆、插入和调整）、快速排序（划分、过程特征）、归并排序（归并路数、归并过程）是重点。
• 读者应深入掌握各种排序算法的思想、排序过程(能动手模拟) 和特征（初态的影响、时空复杂度、稳定性、适用性等）
• 常以选择题的形式考查不同算法之间的对比
• 对于一些常用排序算法的关键代码，要达到熟练编写的程度；
• 看到某特定序列，读者应具有选择最优排序算法（根据排序算法特征）的能力。

graph LR
    A(排序) --- B(基本概念)
    B --- B1(稳定性)
    B --- B2("衡量标准: 时,空复杂度")
    A --- C(内部排序)
    C --- C1(插入排序)
    C1 --- C11(直接插入排序)
    C1 --- C12(折半插入排序)
    C1 --- C13(希尔排序)
    C --- C2(交换排序)
    C2 --- C21(冒泡排序)
    C2 --- C22(快速排序)
    C --- C3(选择排序)
    C3 --- C31(简单选择排序)
    C3 --- C32(堆排序)
    C --- C4(归并排序)
    C --- C5(基数排序)
    A --- D("外部排序----多路归并排序")

插入排序

• 直接插入排序

  void InsertSort(ElemType A[], int n) {
      int i,j;
      for (i=2; i<=n; i++) {                // 依次将A[2] ~ A[n]插入到前面已排序序列
          if (A[i].key < A[i-1].key) 
              A[0]=A[i];
              for (j=i-1; A[0].key < A[j].key; --j)
                  A[j+1]=A[j];            // 向后挪位
              A[j+1]=A[0];
          }
  }
  

• 折半插入排序

  void InsertSort(ElemType A[], int n) {
      int i,j,low,high,mid;
      for (i=2; i<=n; i++) {                // 依次将A[2] ~ A[n]插入到前面已排序序列
          A[0]=A[i];
          low=1; high=i-1;
          while (low <= high) {
              mid=(low+high)/2;
              if (A[mid].key > A[0].key) high=mid-1;
              else low=mid+1;
          }
          for (j=i-1; j>=high+1; --j)
              A[j+1]=A[j];
          A[high+1]=A[0];
      }
  }
  

• 希尔排序

  void ShellSort(ElemType A[], int n) {
      for (dk=n/2; dk>=1; dk=dk/2)
          for (i=dk+1; i<=n; ++1) 
              if(A[i].key < A[i-dk].key) {
                   A[0]=A[i];
                  for (j=i-dk; j>0&&A[0].key < A[j].key; j-=dk)
                      A[j+dk]=A[j];
                  A[j+dk]=A[0];
              }//if
  }
  

交换排序

• 冒泡排序

  void BubbleSort(ElemType A[], int n) {
      for (i=0; i<n-1; i++) {
          flag=false;
          for(j=n-1; j>i; j--)
              if (A[j-1].key > A[j].key) {
                  swap(A[j-1], A[j]);
                  flag=true;
              }
          if (flag==false)
              return;
      }
  }
  

• 快速排序

  void QuickSort(ElemType A[], int low, int high) {
      if (low<high) {
          int pivotpos=Partition(A, low, high);
          QuickSort(A, low, pivotpos-1);
          QuickSort(A, pivotpos+1, high);
      }
  }
  int partition(ElemType A[], int low, int high) {
      ElemType pivot=A[low];
      while(low<high) {
          while(low<high&&A[high] >= pivot) --high;
          A[low]=A[high];
          while(low<high&&A[low] <= pivot) ++low;
          A[high]=A[low];
      }
      A[low]=pivot;
      return low;
  }
  

选择排序

• 简单选择排序

  void SelectSort(Ele;mType A[], int n) {
      for (i=0; i<n-1; i++) {
          min = 1;
          for(j=i+1; j<n; j++)
              if(A[j] < A[min]) min=j;
          if(min!=i) swap(A[i], A[min])
      }
  }
  

• 堆排序

  • 建立大根堆算法

    void BuildMaxHeap(ElemType A[], int len) {
        for (int i=len/2; i>0; i--)
            AdjustDown(A, i, len);
    }
    void AdjustDown(ElemType A[], int k, int len) {
        A[0]=A[k];
        for (i=2*k; i<=len; i*=2) {
            if (i<len && A[i]<A[i+1])
                i++;
            if (A[0]>=A[i]) break;
            else {
                A[k]=A[i];
                k=i;
            }
        } // forj
        A[k]=A[0];
    }
    

  • 堆排序算法

    void HeapSort(ElemType A[], int len) {
        BuildMaxHeap(A, len);
        for(i=len; i>1; i--) {
            Swap(A[i], A[1]);
            AjustDown(A, 1, i-1);
        }//for
    }
    

  • 下面是向上调整堆的算法

    void AjustUp(ElemType A[], int k) {
        A[0]=A[k];
        int i=k/2;
        while(i>0&&A[i]<A[0]) {
            A[k]=A[i];
            k=i;
            i=k/2;
        }//while
        A[k]=A[0];
    }
    

归并排序

基数排序

各种内部排序算法的比较和应用

外部排序

小结

Principles of Computer Composition

大纲

[考查目标]

1。理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，
具有完整的计算机系统的整机概念。
2。理解计算机系统层次化结构概念，熟悉硬件与软件之间的界面，掌握指令集体系结
构的基本知识和基本实现方法。
3。能够综合运用计算机组成的基本原理和基本方法，对有关计算机硬件系统中的理论
和实际问题进行计算、分析，对一些基本部件进行简单设计；并能对高级程序设计语言（如
C 语言）中的相关问题进行分析。

一、计算机系统概述

（一）计算机发展历程
（二）计算机系统层次结构

1. 计算机系统的基本组成

2. 计算机硬件的基本组成

3. 计算机软件和硬件的关系

4. 计算机的工作过程

（三）计算机性能指标
吞吐量、响应时间；CPU 时钟周期、主频、CPI、CPU 执行时间；MIPS、MFLOPS 、GFLOPS、
TFLOPS、PFLOPS。

二、数据的表示和运算

（一）数制与编码
1。进位计数制及其相互转换
2。真值和机器数
3.BCD 码

1. 字符与字符串
   5。校验码
   （二）定点数的表示和运算
   1。定点数的表示
   无符号数的表示；有符号整数的表示。
   2。定点数的运算
   定点数的位移运算；原码定点数的加减运算；补码定点数的加/减运算；定点数的乘/
   除运算；溢出概念和判别方法。
   （三）浮点数的表示和运算
   1。浮点数的表示
   IEEE 754 标准
   2。浮点数的加/减运算
   （四）算术逻辑单元 ALU
   1。串行加法器和并行加法器
   2。算术逻辑单元 ALU 的功能和结构

三、存储器层次结构

（一）存储器的分类
（二）存储器的层次化结构
（三）半导体随机存取存储器
1.SRAM 存储器
2.DRAM 存储器
3。只读存储器
4.Flash 存储器
（四）主存储器与 CPU 的连接
（五）双口 RAM 和多模块存储器
（六）高速缓冲存储器（Cache）
1.Cache 的基本工作原理
2.Cache 和主存之间的映射方式
3.Cache 中主存块的替换算法
4.Cache 写策略
（七）虚拟存储器
1。虚拟存储器的基本概念
2。页式虚拟存储器
3。段式虚拟存储器
4。段页式虚拟存储器
5.TLB（快表）

四、指令系统

（一）指令格式
1。指令的基本格式
2。定长操作码指令格式
3。扩展操作码指令格式
（二）指令的寻址方式
1。有效地址的概念
2。数据寻址和指令寻址
3。常见寻址方式
（三）CISC 和 RISC 的基本概念

五、中央处理器（CPU）

（一）CPU 的功能和基本结构
（二）指令执行过程
（三）数据通路的功能和基本结构
（四）控制器的功能和工作原理
1、硬布线控制器
2、微程序控制器
微程序、微指令和微命令；微指令的编码方式；微地址的形式方式。
（五）指令流水线
1、指令流水线的基本概念
2、指令流水线的基本实现
3、超标量和动态流水线的基本概念

六、总线

（一）总线概述
1、总线的基本概念
2、总线的分类
3、总线的组成及性能指标
（二）总线仲裁
1、集中仲裁方式
2、分布仲裁方式
（三）总线操作和定时
1、同步定时方式
2、异步定时方式
（四）总线标准

七、输入输出（I/O）系统

（一）I/O 系统基本概念
（二）外部设备
1、输入设备：键盘、鼠标
2、输出设备：显示器、打印机
3、外存储器：硬盘存储器、磁盘阵列、光盘存储器
（三）I/O 接口（I/O 控制器）
1、I/O 接口的功能和基本结构
2、I/O 端口及其编址
（四）I/O 方式
1、程序查询方式
2、程序中断方式
中断的基本概念；中断响应过程；中断处理过程；多重中断和中断屏蔽的概念。
3、DMA 方式
DMA 控制器的组成，DMA 传送过程。

一、计算机系统概述

复习提示

重点掌握各个性能指标的计算和基本概念。

概念

小记

• 机器语言是计算机唯一可以直接执行的语言。

英文缩写

• 存储器

  • MAR - 地址寄存器，多少个存储单元，即为内存
  • MDR - 数据寄存器，64k x 32位，即为存储容量

• 运算器

  • ALU - 算术逻辑单元
  • ACC - 累加器
  • MQ - 乘商寄存器
  • X - 操作数寄存器
  • IX - 变址寄存器
  • BR - 基址寄存器
  • PSW - 程序状态寄存器
• 控制器
  • PC - 程序计数器
  • IR - 指令寄存器，OP-操作码，Ad - 地址码
  • CU - 控制单元

性能指标

• 机器字长，计算机能直接处理的二进制数据的位数，一般等于内部寄存器的大小，决定计算机的运算精度。

• 数据通路带宽，数据总线一次所能并行传送信息的位数。（外部）

• 主存容量，指主存储器所能存储信息的最大容量，MAR的位数反映存储单元的个数。

• 运算速度

  • 吞吐量，指系统在单位时间内处理请求的数量。主要取决于主存的存取周期

  • 响应时间，

  • CPU时钟周期，常为节拍脉冲或T周期，即主频的倒数，是CPU中最小的时间单位，每个动作至少需要1个时钟周期。

  • 主频（CPU时钟频率），衡量机器速度的重要参数，主频越高，速度越快。1Hz表示每秒1次。

  • CPI（Clock cycle Per Instruction），指执行一条指令所需的时钟周期数。

  • CPU执行时间，指运行一个程序所花费的时间

    CPU执行时间=CPU时钟周期数 / 主频=（指令条数 x CPI）/ 主频

  • MIPS、MFLOPS(百万)、GFLOPS(十亿)、TFLOPS(万亿)

Others

• 计算机的功能部件

• 三种语言

  机器语言，汇编语言(汇编程序)，高级语言(编译-汇编 | 翻译)

• 计算机的工作过程

  取指令：(PC) -> MAR -> M -> MDR -> IR
  分析指令: OP(IR) -> CU
  执行指令: Ad(IP) -> MAR -> M -> MDR -> ACC
        : (PC)+1 -> PC
  

• 计算机系统的多层次结构

  微程序机器层 - 传统机器语言层 - 操作系统层 - 汇编语言层 - 高级语言层.

  “裸机” - 没有配备软件的纯硬件系统，3-5层称为虚拟机

• 计算机体系结构和计算机组成的区别和联系

二、数据的表示和运算

复习提示

纵观近几年真题，不难发现unsigned, short, int, long, float, double, 等在C语言中的表示，运算，溢出判断，隐式类型转换, 强制类型转换, IEEE 754浮点数的表示, 以及浮点数的运算，都是考验的重点，需要牢固掌握。

数制与编码

• Base

  • 十进制（Decimal）,二进制（Binary）,十六进制（Hexadecimal）,八进制（Octal）
  • 基数，位权，数码
  • int, long, unsigned, unsigned long, float : 32位，4字节
  • short, unsigned short: 16位, 2字节
  • char: 8位，1字节
  • double: 64位，8字节

• 进制转换

  • 二转八或十六，
    • 一串二进制数分为3位（八进制）或4位（十六进制）
    • 整数，小数点向左；小数，小数点向右
  • 任意转十，数码与权值相乘，乘积叠加
  • 十转任意，基数乘除法
    • 整数部分采用除基取余法
    • 小数部分采用乘基取整法，ps: 不是每个十进制小数都可以准确地用二进制表示，比如0.3

• 真值，机器数：真值是带符号“+” 和 “-”的数, 机器数是将符号数字化的数，如 0为正，1为负。

• BCD码，二进制编码的十进制数（Binary-Coded Decimal, BCD），常采用4位二进制数表示一位十进制的数码。有8421码，余3码，2421码

  • 余3码，在8421码的基础上加(0011)
  • 2421码，特点是大于5的4位二进制数中的最高位为1。如: 5 —> 1011

• 字符与字符串

  • 字符编码ASCII码，占7位，表示128个字符。
  • 汉字的表示和编码，占两个字节。

• 校验码

  • tips

    • 码距不小于2，开始具有检错能力，
    • 码距越大，检错，纠错能力就越强，
    • 检错能力永远大于等于纠错能力

  • 奇偶校验码，具有局限性，奇偶校验只能发现数据代码中奇数位的出错情况，但不能纠正错误，常用于对存储器数据的检查或传输数据的检查。

    • 只能发现数据代码中奇数位的出错情况，不能纠错，常用于对存储器数据的检查或传输数据的检查。

  • 海明（汉明）校验码 *

    • 纠错理论 L - 1 = D + C 且 D >= C

    • Steps

      1. 确定海明码的位数，$n+k\le2^k-1$,若要检测两位错，则需再增加1位校验位，即$2^{k-1}\ge n+k$

      2. 确定校验位的分布，规定校验位 $P_i$在海明位号为$2^{i-1}$的位置上，其余各位为信息位。

      3. 分组以形成校验关系，被校验数据位的海明位号等于校验该数据位的各校验位海明位号之和。

      4. 校验位取值，校验位$P_i$的值为第$i$组(由校验位校验的数据位)所有位求异或

      5. 海明码的校验原理

         每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，若全为 0,则说明无错，否则说明出错，且这个数就是错误位的位号，直接将该位取反就达到了纠错的目的。

  • 循环冗余校验（CRC）码 *

    • 生成多项式$G(x)$是接收端和发送端的一个约定，最高幂次为 R, R+K = N（CRC码的位数）
    • 模2除法，加法和减法的结果相同，都是做异或运算，不借位。
    • Steps
      • 移位
      • 相除
      • 检错和纠错，将处错位取反即可

定点数的表示与运算

• 表示

  • 无符号数，

  • 有符号数 | 原码，补码，反码，移码 | 区别真值

    

    0为正，1为负，设字长为n+1.

    • 原码，

      • 纯小数表示范围$-(1-2^{-n})\le x\le1-2^{-n}$
      • 整数表示范围$-(2^{n}-1)\le x \le 2^{n}-1$
      • 真值零的原码表示有正零和负零两种形式，00000 = 10000

    • 补码，

      • 纯小数表示范围$-1\le x\le 1-2^{-n}$，（比原码多表示 $-{1}$）

      • 整数表示范围$-2^n \le x \le 2^n-1$, (比原码多表示$-2^n$)

      • 真值零的补码表示是唯一的，00000

      • 对于正数，补码与原码的表示相同

      • 对于负数， $[x]原 \rarr [x]补 或 [x]补\rarr[x]原$

        符号为不变，数值部分按位取反，末位加1

    • 反码

      • 纯小数表示范围$-(1-2^{-n})\le x\le1-2^{-n}$
      • 纯整数表示范围$-(2^{n}-1)\le x \le 2^{n}-1$
      • 真值零的反码表示不唯一，0.0000 = 1.1111

    • 移码

      • 常用来表示浮点数的阶码，它只能表示整数。
      • 真值零的移码表示唯一，100…..0（n 个 0）
      • $[x]补的符号位取反即得[x]移$
      • 移码全 0 时，对应真值的最小值$-{2^n}$，移码全 1 时，对应真实的最大值 $2^n-1$
      • 移码保持了数据原有的大小顺序，移码大真值就大，移码小真值就小

  • 定点表示

    定点小数($1-2^{-n}$)，定点整数($2^n - 1$)

  • 补码的算术移位

• 运算

  1. 移位

     • 算术移位 (有符号数), 移位过程中，符号位保持不变

       

     • 逻辑移位，操作对象是逻辑代码，可视为无符号数

     • 循环移位

       • 带进位标志位CF的循环移位（大循环）,不带进位标志位的循环移位（小循环）

       • 特点：移出的数位又被移入数据

       • 适合将数据的低字节数据和高字节数据互换

         

  2. 原码定点数的加减法运算

  3. 补码定点数的加减法运算

     计算机系统中普遍采用补码加减运算

  4. 符号扩展

     • 整数，所有附加位都用 0进行填充
     • 负数-补码，所有附加位用 1(整数) 或 0(小数)进行填充
     • 负数-反码，所有附加位用 1进行填充

  5. 溢出概念和判别方法

     • 大于机器所能表示的最大正数为 上溢

     • 小于机器所能表示的最小负数为 下溢

     • 补码溢出判断

       1. 采用一位符号位 $$V=A_sB_S\overline{S_s}+\overline{A_SB_S}S_s$$

      V=0，表示无溢出；V=1，表示有溢出

   2. 采用双符号位，也称模 4 补码

      $S_{s1}S_{s2}$相同，表示未溢出，不同，表示溢出，此时最高位符号位代表真正的符号

   3. 采用一位符号位根据数据位的进位情况判断溢出

      若符号位的进位$C_s$与最高数位的进位相同，说明没有溢出，否则表示发生溢出

1. 定点数的乘法运算

   乘法运算由累加和右移操作实现

   • 原码一位乘法

     符号位与数值位分开求，符号位求异或，数值位求两绝对值的乘积（过程中的移位操作均为逻辑移位），操作中引入双符号位

     

   • 补码一位乘法（Booth算法）

     一种有符号数的乘法，采用相加或相减操作计算补码数据的乘积，（移位操作为补码右移），引入双符号位，（共进行 n+1 次累加和 n 次右移）.

     

   • 乘法运算总结

     

2. 定点数的除法运算

   除法运算可转换成 “累加-左移”（逻辑左移）

   • 原码除法，主要采用原码不恢复余数法，也称原码加减交替除法

     特点：商符合商值分开进行，商符求异或.

     1. 先用被除数减去除数，
        1. 当余数为正时，商上 1，余数和商左移一位，再减去除数。
        2. 当余数为负时，商上0，余数和商左移一位，再加上除数。
        3. 当第 n + 1 步余数为负时，需加上 |Y| 得到 第 n + 1 步正确的余数

   

• 补码除法，(加减交替法)

  1. 被除数与除数同号，则被除数减去除数；异号，被除数加上除数
  2. 余数与除数同号，则商上 1，余数左移一位减去除数；异号，则商上 0，余数左移一位加上除数
  3. 若对商的精度没有特殊要求，则一般采用 “末位恒置 1” 法
  4. Tips
     • 异号相除是看够不够减，然后上商，够减商0，不够减商1.

  

• 除法运算总结

  

• 强制类型转换

  • 强制类型转换的结果保持位值不变，仅改变了解释这些位的方式。

• 数据的存储和排列，

  • 大端方式和小端方式
  • 边界对齐方式相对边界不对齐方式是一种空间换时间的思想。

浮点数的表示与运算

• 表示

  • tips

    • 将比例因子表示在数据中，让小数点的位置根据需要而浮动，这样在位数有限的情况下，既扩大了数的表示范围，又保持了数的有效精度。
    • 长度相同，格式相同的两种浮点数，基数越大
      • 范围越大，但精度变低（数变稀疏）
      • 运算速度更高

  • 表示格式

    

  • 规格化浮点数

    • 规定尾数的最高数位必须是一个有效值
    • 左规，算术左移一位、阶码减1
    • 右规，算术右移一位、阶码加1
    • 规格化浮点数的尾数 M 的绝对值应满足条件 $1/r\le |M|\le1$
    • 原码
      • 正数尾数的表示范围 $1/2\le M\le(1-2^{-n})$
      • 负数尾数的表示范围$-(1-2^{-n})\le M\le-1/2$
    • 补码
      • 正数尾数的表示范围$1/2\le M\le(1-2^{-n})$
      • 负数尾数的表示范围$-1\le M \le-(1/2+2^{-n})$
    • 基数 r 不同，浮点数的规格化形式也不同

  • IEEE754标准

    IEEE754标准的浮点数（除临时浮点数外），是尾数用采取隐藏位策略的原码表示，且阶码用移码表示的浮点数。

    

    

    

    • 尾数采用隐藏位策略的原码表示，阶码用移码表示
    • 隐藏尾数最高位

  • 定点, 浮点表示的区别

    浮点表示相比较而言，表示范围远远扩大、精度有所下降、运算较复杂、（非规格化）不一定会溢出

    • 精度，是指一个数所含有效数值位的位数
    • 浮点运算中，只有规格化后阶码超出所能表示的范围时，才发生溢出

• 浮点数的加减运算

  • 特点：阶码运算和尾数运算分开进行，一律采用补码.

  • 分为以下几步：

    • 对阶 ，小阶向大阶看齐

    • 尾数求和

    • 规格化

      • 当尾数的最高数值位与符号位不同时，即为规格化形式。
      • 当基数为 4 时，原码规格化形式的尾数最高两位不全为 0
      • 当基数为 8 时，原码规格化形式的尾数最高 3 位不全为 0

    • 舍入

      • 0 舍 1 入法；最高数值位为0，舍去；为1，尾数末位加 1.
      • 恒置 1 法

    • 溢出判断

      • 浮点数的溢出与否是由阶码的符号决定的
        • 01，即阶码大于最大阶码，表示上溢，进入中断处理
        • 10，即阶码小于最小阶码，表示下溢，按机器零处理
          • 运算结果的绝对值小于机器所能表示的最小绝对值，分正下溢 和 负下溢

    • 强制类型转换

      常见有 char - int - long -double 和 float - double

算术逻辑单元（ALU）

• 加法器

  一位全加器 |

  • 串行加法器，
    • 加法分 n 次进行
    • 器件少，成本低；运算速度慢，多用于某些低俗的专用运算器
  • 并行加法器
    • 位数与机器的字长相同
    • 并行加法器的最长运算时间主要由进位信号的产生和传递时间决定
    • 串行进位，又称行波进位，位数越多延迟时间就越长；最长运算时间取决于进位信号的传递时间；
    • 并行进位，又称先行进位、同时进位；
    • 分组并行进位方式，常用，组内并行，组间串行
    • 并行快速进位方式
      • 单级先行进位方式，又称组内并行，组间串行进位方式
      • 多级先行进位方式，又称组内并行，组间并行进位方式

• 算术逻辑单元的功能和结构

  • 74181

三、存储系统

1. 存储器的层次结构

• 分类

  • 作用

    主存储器（主存，内存）、辅助存储器（外存）、高速缓冲存储器（Cache）

  • 介质

    磁表面存储器（磁盘，磁带）、磁心存储器半导体存储器（MOS行存储器，双极行存储器）和光存储器（光盘）

  • 存取方式

    随机存储器（RAM）、只读存储器（ROM）、串行访问存储器

  • 可保存性

    易失存储器，非易失存储器

• 性能指标

  存储容量 | 单位成本 |

  • 存储速度

    数据传输率 = 数据的宽度 / 存储周期

    存取时间$T_a$，存取周期$T_m$，主存带宽$B_m$(又称数据传输率)

    

2. 存储器的层次化结构

（磁带，光盘）—> 磁盘—> 主存—> Cache—> 寄存器

3. 半导体随机存储器

• 半导体存储芯片

  • 基本结构：存储矩阵，译码驱动，读写电路，读/写控制线，片选线，地址线，数据线

    

  • 74138译码器

  • tips

    • 地址线和数据线共同反应存储芯片容量大小，如地址线10根，数据线8根，则芯片容量=$2^{10}*8$

• SRAM和DRAM

  • SRAM工作原理

  • DRAM工作原理

    DRAM电容上的电荷只能维持1~2 ms

    • 集中刷新，

      读写操作时，不受刷新影响，因此系统的存取速度较高；缺点是在集中刷新期间（死区）不能访问存储器。

    • 分散刷新

      优点是没有死区；缺点是加长了系统的存取周期，降低了整机的速度

    • 异步刷新

      前两种的结合。避免是CPU连续等待过长的时间，而且减少了刷新次数，从根本上提高了整机的工作效率

  • RAM的读 写周期

    • 写周期不明确

      

      

  • SRAM 和 DRAM 的比较.

    

  • tips

    • 地址码相同的多个存储元构成一个存储单元

• 只读存储器

  • ROM的特点，

    • 结构简单，所以位密度比可读写存储器的高
    • 具有非易失性，可靠性高

  • 类型

    掩膜式只读存储器MROM，一次可编程只读存储器PROM，可擦除可编程只读存储器EPROM(编程次数有限)，闪速存储器Flash Memory，固态硬盘Solid State Drivers.

4. 主存储器与CPU的连接

• 连接原理

  数据总线，地址总线，控制总线

  

• 主存容量的扩展

  • 位扩展法

    • 连接方式，是将多个存储芯片的地址端、片选端和读写控制端相应并联，数据短分别引出。

    • 仅采用位扩展时，各芯片连接地址线的方式相同，但连接数据线的方式不同，在某一时刻选中所有的芯片，所以片选信号$\overline{CS}$要连接到所有芯片

    • 

  • 字扩展法

    • 字扩展将芯片的地址线、数据线、读写控制线相应并联，而由片选信号来区分给芯片的地址范围。
    • 仅采用字扩展时，各芯片连接地址线的方式相同，连接数据线的方式也相同，但在某一时刻只需选中部门芯片，所以通过片选信号$\overline{CS}$或采用译码器设计连接到相应的芯片
    • 

  • 字位同时扩展法

    • 采用字位同时扩展时，各芯片连接地址线的方式相同，但连接数据线的方式不同，而且需要通过片选信号$\overline{CS}$或采用译码器设计连接到相应的芯片。
    • 

• 存储芯片的地址分配和片选

  CPU对存储单元进行访问，首先要选择存储芯片（片选），然后为选中的芯片依地址码选择相应的存储单元，以进行数据的存取（字选）。片内的字选通常是由CPU送出的 N 条低位地址线完成的，地址线直接接到所有存储芯片的地址输入端（N由片内存储容量$2^N$决定）

  • 线选法

    优：不需要地址译码器，线路简单；缺：地址空间不连续，选片的地址线必须分时为低电平（否则不能工作），不能充分利用系统的存储器空间，造成地址资源的浪费

  • 译码片选法

    用除片内寻址外的高位地址线通过地址译码器芯片产生片选信号。

• 存储器与CPU的连接

  • 合理选择存储芯片

  • 地址线的连接

    • CPU的地址线数往往比存储芯片的地址线数要多
    • 通常将CPU地址线的低位与存储芯片的地址线相连，以选择芯片中的某一单元（字选），这部分的译码是由芯片的片内逻辑完成的。
    • 而CPU地址线的高位则在扩充存储芯片时使用，用来选择存储芯片（片选），这部分译码由外接译码器逻辑完成

  • 数据线的连接

    CPU的数据线数与存储芯片的数据线数不一定相等，在相等时可直接相连；在不相等时必须对存储芯片扩位，使两者相等

  • 读/写命令线的连接

  • 片选线的连接

    片选线的连接是CPU与存储芯片连接的关键。存储器有许多存储芯片叠加而成，哪一片被选中完全取决于该存储芯片的片选控制端$\overline{CS}$是否能接收到来自CPU的片选有效信号。

    片选信号与CPU的访存控制信号$\overline{MREQ}$(低电平有效)有关

5. 双端口RAM和多模块存储器

为了提高CPU访存速度，可采用双端口存储器、多模块存储器等技术，它们同属并行技术，前者为空间并行，后者为时间并行。

• 双端口RAM

  

• 多模块存储器

  • 单体多字存储器

    • 优：增大了存储器的宽度，提高了单体存储器的工作速度
    • 缺：指令和数据在主存内必须是连续存放的，一旦遇到转移指令，或操作数不能连续存放，这种方法的效果就不明显
    • 

  • 多体并行存储器

    • 高位交叉编址（顺序方式），高位地址表示体号，低位地址为体内地址

    • 低位交叉编址（交叉方式），低位地址为体号，高位地址为体内地址

    • 

      

6. 高速缓冲存储器

因为单纯依靠并行主存系统提高主存系统的频宽是有限的，所以 Cache 闪亮登场.

• 程序访问的局部性原理，包括时间局部性和空间局部性

  高速缓冲技术就是利用程序访问的局部性原理。

• Cache的基本工作原理，cache常由SRAM构成

  

  • CPU与Cache之间的数据交换以字位单位，而Cache与主存之间的数据交换以Cache块进行。
  • Cache写策略处理，全写法和写回法
  • Cache的命中率，$H=N_c / (N_c+N_m)$
  • Cache-主存系统的平均访问时间 $T_a=Ht_c + (1-H)t_m$

• Cache和主存的映射方式

  在Cache中，地址映射是指把主存地址空间映射到Cache地址空间，即把存放在主存中的程序按照某种规则装入Cache。

  地址映射不同于地址变换，地址变换是指CPU在访存时，将主存地址按映射规则换算成Cache地址的过程。

  • 直接映射，实现简单，但不够灵活，块冲突概率最高，空间利用率最低

    

  • 全相联映射，比较灵活，Cache块的冲突概率低，空间利用率高，命中率也高；缺点：地址变换速度慢，实现成本高，通常采用昂贵的按内容寻址的相连存储器进行地址映射。

    

  • 组相联映射

    组间采取直接映射，组内采取全相连映射

    

• Cache中主存块的替换算法

  • 随机算法（RAND）

    实现比较简单，但未依据程序访问的局部性原理，故可能命中率较低.

  • 先进先出算法（FIFO）

    容易实现，但也未依据程序访问的局部性原理，可能会把常用的程序块作为最早进入Cache的块替换掉。

  • 近期最少使用算法（LRU）

    依据程序访问的局部性原理选择近期内长久未访问过的存储行作为替换的行，平均命中率要比FIFO的高，是堆栈类算法。

    LRU对每行设置一个计数器，Cache每命中一次，命中行计数清 0，其它行计数器均加 1。计数值最大的行换出。

  • 最不经常使用算法（LFU）

    将一段时间内被访问次数最少的存储行换出，每行也设置一个计数器，新行初始为0，每访问一次，被访问行计数器加 1，计数值最小的行换出

• Cache写策略，对于Cache写命中 （write hit）

  • 全写法（写直通法，write-through）

    实现简单，随时保持主存数据的正确性。缺点：增加了访存次数，降低了Cache的效率。

    写缓冲（Write Buffer）:减少全写法直接写入主存的时间消耗，是一个FIFO队列

    

  • 写回法（write-back）

    当CPU对Cache写命中时，只修改Cache的内容，而不立即写入主存，只有当此块被换出时才写回主存。

    减少了访存次数，但存在不一致的隐患，

    每个Cache行必须设置一个标志位（脏位），以反映此块是否被CPU修改过。

  写不命中

  • 写分配法（write-allocate）

    加载主存中的块到Cache中，然后更新这个Cache块，它试图利用程序的空间局部性，但缺点是每次不命中都需要从主存中读取一块

  • 非写分配法（not-write-allocate）

    只写入主存，不进行调块

  • 多级Cache

    通常为 3 级，离CPU越远，访问速度越慢，容量越大。指令Cache与数据Cache分离一般在L1级，此时通常为写分配法与写回法合用。

    

7. 虚拟存储器

虚拟存储器具有主存的速度和辅存的容量，提高了存储系统的性价比。

• 基本概念

  • 用于编程允许设计的地址称为 虚地址或逻辑地址，虚地址对应的存储空间或程序空间；实际的主存单元地址称为实地址或物理地址，实地址对应的是主存地址空间，也成实地址空间。虚地址要比实地址大很多。程序进行虚地址到实地址转换的过程称为程序的再定位。

    

    

    

• 页式虚拟存储器

  • 虚地址分为两个字段：虚页号 和 页内地址

  • 页表，虚页号和实页号的对照表；页表项：虚页号，实页号，装入位

  • 优： 页面长度固定，页表简单，调入方便。缺：处理，保护和共享都不及段式虚拟存储器方便。

    

• 段式虚拟存储器

  • 虚拟地址分为两部分：段号和段内地址

  • 段表，是程序逻辑段和在主存中存放位置的对照表；段表行：段号，装入位，段起点和段长

  • 优：易于编译，管理，修改和保护，也便于多道程序的共享；缺：容易在段间留下碎片，造成浪费。

    

• 段页式虚拟存储器

  • 徐地址分为段号，段内页号，页内地址三部分。

• 块表（TLB）

  • 存储在高速缓冲器的页表项，相应地存放在主存中的页表为慢表（Page）,是块表的超集。

• 虚拟存储器与Cache的比较

  

8. tips

• 相联存储器既可以按地址寻址，又可以按内容寻址，又称按内容寻址的存储器。

• 软件和硬件的逻辑上是等效的，不是等价的

• 什么是存储程序原理？按此原理，计算机应具有哪几大功能？

  • 存储程序是指将指令以代码的形式事先输入计算机主存储器，然后按其在存储器中的首地址执行程序的第一条指令，以后就按该程序的规定顺序执行其他指令，直至程序执行结束。
  • 计算机按照此原理应该具有 5 大功能：数据传送功能、数据存储功能、数据处理功能、操作控制功能、操作判断功能

四、指令系统

1. 指令格式

指令，又称机器指令，是计算机运行的最小功能单位。指令系统是计算机的主要属性，位于硬件和软件的交界层面上。

• 基本格式

  • 一条指令就是机器语言的一个语句，它是一组有意义的二进制代码，包括 操作码字段 和 地址码字段。

  • 指令长度：单字长指令，半字长指令，双字长指令

  • 定长指令字结构和变长指令字结构

  • 根据指令中操作数地址码的 数目 的不同，可分为

    • 零地址指令

      • 不需要操作数的指令，如空操作指令，停机指令，关中断指令等
      • 零地址的运算类指令仅用在堆栈计算机中

    • 一地址指令

      • 只有目的操作数的但操作数指令

        $OP(A_1)\rarr A_1$ ,如加1，减1，求反，求补

      • 隐含约定目的地址的双操作数指令，如ACC(累加器)

        $(ACC)OP(A_1)\rarr ACC$

    • 二地址指令

      $(A_1)OP(A_2)\rarr A_1$

    • 三地址指令

      $(A_1)OP(A_2)\rarr A_3$

    • 四地址指令

      $(A_1)OP(A_2)\rarr A_3,\ A_4 = 下一条将要执行指令的地址$，

• 定长操作码指令格式

  一般 n 位操作码字段的指令系统最大能够表示 $2^n$ 条指令.

• 扩展操作码指令格式

  

  • 设计操作码指令格式时，需注意：

    • 不允许短码是长码的前缀，即短操作码不能与长操作码的前面部分的代码相同

    • 各指令的操作码一定不能重复

      一般地，使用频率较高的指令分配较短的操作码，使用频率低的指令分配较长的操作码，以减少指令译码和分析的时间。

2. 指令寻址方式

寻址方式是指寻找指令或操作数有效地址的方式，即确定本条指令的数据地址及下一条待执行指令的地址的方法。形式地址（A）+ 寻址方式 = 有效地址（EA）.

• 指令寻址

  • 顺序寻址方式，（PC）+ 1（1个指令字长）
  • 跳跃寻址方式，通过转移类指令实现。

• 数据寻址

  数据寻址是指如何在指令中表示一个操作数的地址，如何用这种表示得到操作数或怎样计算出操作数的地址。

  

• 常见的数据寻址方式

  

  1. 隐含寻址

     累加器（ACC）对单地址指令格式来说是隐含地址。

     优：利于缩短指令字长；缺：需增加存储操作数或隐含地址的硬件

  2. 立即（数）寻址

     优：指令在执行阶段不访问主存，指令执行时间最短；缺：A的位数限制了立即数的范围。

  3. 直接寻址,EA = A

     指令字中的形式地址 A 是操作数的真实地址 EA.

     优：简单，指令在执行阶段仅访问一次主存，不需要专门计算操作数的地址。

     缺：A的位数决定了该指令操作数的寻址范围，操作数的地址不易修改

  4. 间接寻址，EA = (A)

     即操作数地址的地址，一次间接寻址或多次间接寻址.

     优：可扩大寻址范围，便于编制程序；

     缺：指令在执行阶段要多次访存，优于访问速度过慢，所以不常用，一般问道扩大寻址范围时，通常指的是寄存器间接寻址。

  5. 寄存器寻址，EA = $R_i$

     指在指令字中直接给出操作数所在的寄存器编号,其操作数在有 $R_i$所指的寄存器内。

     优：指令在执行阶段不访问主存，只访问寄存器，因寄存器数量少，对应地址码长度较小，使得指令字短且因不用访存，所以执行速度快，支持向量/矩阵运算

     缺：寄存器价格昂贵，计算机中的寄存器个数有限。

  6. 寄存器间接寻址，EA = $(R_i)$

     指在寄存器$R_i$中给出的不是一个操作数，而是操作数所在主存单元的地址。

     特点：比一般简介寻址速度更快，但指令的执行阶段需要访问主存。

  7. 相对寻址，EA = （PC）+ A

     把程序计数器（PC）的内容加上指令格式中的形式地址 A 而形成操作数的有效地址。其中 A 是相对于当前指令地址的位移量，可正可负，补码表示。

     优：操作数地址不固定，随 PC 值得变化而变化，且与指令地址之间总是相差一个固定值，因此便于程序浮动，相对寻址广泛应用于转移指令。

  8. 基址寻址, EA = (BR) + A

     CPU中基址寄存器（BR）的内容加上指令格式中的形式地址 A 而形成操作数的有效地址. 其中基址寄存器即可采用专用寄存器，又可采用通用寄存器。基址寄存器面向操作系统，其内容由操作系统或管理程序确定，主要用于解决程序逻辑空间与存储器物理空间的无关性。

     优：可扩大寻址范围，用户不必考虑自己的程序存于主存的哪个空间区域，故有利于多道程序设计，并可用于编制浮动程序，但偏移量（形式地址 A）的位数较短。

  9. 变址寻址，EA = (IX) + A

     指有效地址 EA 等于指令字中的形式地址 A 与 变址寄存器 IX 的内容之和。变址寄存器是面向用户的，在程序执行过程中，变址寄存器的内容可由用户改变（作为偏移量），形式地址 A 不变（作为基地址）。

     变址寻址与基址寻址的有效地址形成过程极为相似，但本质上讲，两者有较大区别：

     • 基址寻址面向系统，主要用于为多道程序或数据分配存储空间，故基址寄存器的内容通常由操作系统或管理程序确定，在程序的执行过程中其值不可变，而指令字中的 A 是可变的。
     • 变址寻址立足于用户，主要用于处理数组问题，在变址寻址中，变址寄存器的内容由用户设定，在程序执行过程中其值可变，而指令字中的 A 是不可变的。

  10. 堆栈寻址

      该存储区中被读/写单元的地址是用一个特定的寄存器给出的，该寄存器称为堆栈指针（SP）.

      • 寄存器堆栈又称硬堆栈，成本较高，不适合做大容量堆栈，
      • 从主存中划出来一段区域来做堆栈是最合算且最常用的方法，称为软堆栈。

3. CISC和RISC的基本概念

• 复杂指令系统计算机(CISC)

• 精简指令系统计算机(RISC)

• 两者的比较

  

五、中央处理器

1. CPU的功能和基本结构

• 功能

  • 控制器的功能是负责协调并控制计算机各部件执行程序的指令序列，包括取指令、分析指令和执行指令。
  • 运算器的功能是对数据进行加工。
  • CPU的功能包括：1. 指令控制；2.操作控制；3.时间控制；4.数据加工；5.中断处理

• 基本结构

  • 运算器

    • 1.算术逻辑单元（ALU），进行逻辑/算术运算
    • 2.暂存寄存器 ，暂存从主存读来的数据，对应用程序员透明

    • 3.累加寄存器（ACC），通用寄存器，暂存ALU运算的结果信息，可以作为加法运算的一个输入端

    • 4.通用寄存器组

      如AX, BX, CX, DX, SP等，用于存放操作数（源操作数，目的操作数及中间结果）和各种地址信息。SP是堆栈指针，用于指示栈顶的地址。

    • 5.程序状态字寄存器（PSW）

      溢出标志（OF）,符号标志（SF），零标志（CF），进位标志（CF）等。PSW中的这些位参与并决定微操作的形成。

    • 6.移位器 ，对操作数和运算结果进行移位运算

    • 7.计数器（CT），控制乘除运算的操作步数。

  • 控制器

    基本功能是执行指令，每条指令的执行是由控制器发出的一组微操作实现的。控制器分 硬布线控制器和微程序控制器两种类型。

    1. 程序计数器（PC）
    2. 指令寄存器（IR），保存当前正在执行的指令
    3. 指令译码器，仅对操作码字段进行译码，向控制器提供特定的操作信号。
    4. 存储器地址寄存器，用于存放所要访问的主存单元的地址
    5. 存储器数据寄存器，用于存放向主存写入的信息或从主存中读出的信息
    6. 时序系统，用于产生各种时序信号，它们都由统一视同（CLOCK）分频得到
    7. 微操作信号发生器，根据IR的内容，PSW的内容及 时序信号，产生控制整个计算机系统所需的各种控制信号，其结构有组合逻辑型和存储逻辑型两种。
    8. 控制器的工作原理：根据指令操作码、指令的执行步骤（微命令序列）和条件信号来形成当前计算机各部件要用到的控制信号。计算机整机各硬件系统在这些控制信号的控制下协同运行，产生预期的执行结果.

    寄存器

    • 用户可见，通用寄存器组，程序状态字寄存器
    • 用户不可见，存储器地址寄存器，存储器数据寄存器，指令寄存器

2. 指令执行过程

• 指令周期

  • CPU从主存中每取出并执行一条指令所需的全部时间称为指令周期。
  • 取指周期：取指令；间址周期：取有效地址；执行周期：取操作数；中断周期：保存程序断点。
  • 4个标志触发器FE、IND、EX 和 INT，分别对应上述四个周期，1 状态表示有效
  • 中断周期中的进栈操作是减 1，因为计算机的堆栈中都是向低地址增加。

• 指令周期的数据流

  数据流是根据指令要求依次访问的数据序列。

  • 取指周期

    

  • 间址周期

    

  • 执行周期

    不同指令的执行周期操作不同，因此没有同意的数据流向

  • 中断周期

    

• 指令执行方案

  • 单指令周期

    对所有指令都选用相同的执行时间来完成，此时每条指令 都在固定的时钟周期内完成。会降低整个系统的运行速度。

  • 多指令周期

    选用不同个数的时钟周期来完成不同的指令的执行过程

  • 流水线方案

    指令之间并行执行。追求目标是力争在每个时钟脉冲周期完成一条指令的执行过程（理想状态）。

3. 数据通路的功能和基本结构

• 功能

  数据在功能部件之间传送的路径称为数据通路。功能是实现CPU内部的运算器与寄存器及寄存器之间的数据交换。建立数据通路的任务是由 “操作控制部件” 来完成的。

• 数据通路的基本结构

  • CPU内部单总线方式，多冲突，性能低

  • CPU内部三总线方式，效率较高

  • 专用数据通路方式，性能较高，但硬件量大。

  • Attention

    内部总线是指同一部件，如CPU内部链接各寄存器及运算部件之间的总线；系统总线是指同一台计算机系统的各部件，如CPU, 内存， 通道和各类 I/O 接口间互相连接的总线。

• Others

  • 寄存器之间的数据传送

  • 主存与CPU之间的数据传送

  • 执行算术或逻辑运算

    

4. 控制器的功能和工作原理

• 结构和功能

  

  • 根据控制器产生微操作控制信号的方式的不同，控制器可分为以下两种

• 硬布线控制器

  • 硬布线控制单元图

    

  • 硬布线控制器的时序系统及微操作

    • 时钟周期

    • 机器周期

    • 指令周期

    • 微操作命令分析

      

  • CPU的控制方式

    • 同步控制方式，优点：控制电路简单，缺点：运行速度慢
    • 异步控制方式，优点：运行速度快，缺点：控制电路复杂
    • 联合控制方式，对各种不同的指令的微操作实行大部分采用同步控制，小部分采用异步控制的办法。

  • 硬布线控制单元设计步骤，复杂，详见书本

    • 列出微操作命令的操作时间表
    • 进行微操作信号综合
    • 画出微操作命令的逻辑图

• 微程序控制器

  微程序控制器采用存储逻辑实现，也就是把微操作信号代码化，使每条机器指令转化成为一段微程序并存入一个专门的存储器（控制存储器）中，微操作控制信号由微指令产生。

  • 基本概念

    • 微命令与微操作
      • 微操作是计算机中最基本的、不可再分解的操作。微命令是构成控制序列的最小单位。微命令和微操作是一一对应的。微命令是微操作的控制信号，微操作是微命令的执行过程。
      • 微命令有相容性和互斥性之分。
    • 微指令与微周期
      • 微指令是若干微命令的集合；存放微指令的控制存储器的单元地址称为微地址。一条微指令包含两大部分：1. 操作控制字段，又称微操作码字段；2. 顺序控制字段，又称微地址码字段。
      • 微周期常指从控制器中读取一条微指令并执行相应的微操作所需的时间。
    • 主存储器与控制存储器
      • 主存储器用于存放程序和数据，在CPU外部，用 RAM 实现
      • 控制存储器（CM）用于存放微程序，在CPU内部，用ROM实现。
    • 程序与微程序
      • 程序，是指令的有序集合，用于完成特定的功能
      • 微程序，是微指令的有序集合，一条指令的功能由一段微程序来实现。实际上是机器指令的实时解释器。对用户透明。
    • 区分一下寄存器
      • 地址寄存器（MAR）
      • 微地址寄存器（CMAR）
      • 指令寄存器（IR）
      • 微指令寄存器（CMDR 或 $\mu$IR）

  • 组成和工作过程

    • 基本组成

      

      • 控制存储器，存放各指令对应的微程序
      • 微指令寄存器，
      • 微地址形成部件
      • 微地址寄存器

    • 工作过程，复杂，见课本

  • 微指令的编码方式

    又称微指令的控制方式，是指如何对微指令的控制字段进行编码，以形成控制信号。编码的目标是在保证速度的情况下，尽量缩短微指令字长。

    • 直接编码（直接控制）方式

      优点是简单、直观，执行速度快，操作并行性好；缺点是微指令字长过长，n 个微指令就要求微指令的操作字段有 n 位，造成控制存储器容量极大。

      

    • 字段直接编码方式

      • 可以缩短微指令字长，但因为要通过译码电路后再发出微命令，因此比直接编码方式慢。
      • 微命令字段分段的原则：见书。

    • 字段间接编码方式

      又称隐式编码，可进一步缩短微指令字长，但因削弱了微指令的并行控制能力，因此通常作为字段直接编码方式的一种辅助手段。

  • 微指令的地址形成方式

    • 直接由微指令的下地址字段指出，又称断定方式
    • 根据机器指令的操作码形成

  • 微指令的格式

    • 水平型微指令

      优点是微程序短，执行速度快；缺点是微指令长，编写微程序较麻烦

    • 垂直型微指令

      优点是微指令短，简单，规整，便于编写微程序；缺点是微程序长，执行速度慢，工作效率低。

    • 混合型微指令

      微指令较短，仍便于编写；微程序也不长，执行速度加快

    • 水平型微指令和垂直型微指令

      

  • 微程序控制单元的设计步骤

    1. 写出对应机器指令的微操作命令及节拍安排
    2. 确定微指令格式
    3. 编写微指令码点

  • 动态微程序设计和毫微程序设计

    1. 动态微程序设计
    2. 毫微程序设计

  • 硬布线和微程序控制器的特点

    

5. 指令流水线

• 基本概念

  计算机的流水线把一个重复的过程分解为若干子过程，每个子过程与其他子过程并行执行。是一种普遍使用的并行处理技术。

  • 指令流水的定义

    多条指令在处理器中执行时：

    • 顺序执行方式，T = 3nt

      传统冯.诺依曼机采用顺序执行方式，又称串行执行方式。优点是控制简单，硬件代价小；缺点是执行指令的速度较慢。

    • 一次重叠执行方式，T = (1+2n)t

      优点：程序的执行时间缩短了 1/3, 各功能部件的利用率明显提高，但硬件上有较大开销，控制过程也较复杂。

    • 二次重叠执行，（2+n）t

      时间缩短 2/3，这是一种理想的指令执行方式。

  ![image-20200422172613136](pat\cc0057.png)

• 流水线的表示方法，时空图

  

• 流水线方式的特点，见书。

  

• 流水线的分类

  • 部件功能级，处理机级和处理机间级流水线
  • 单功能流水线和多功能流水线
  • 动态流水线和静态流水线
  • 线性流水线和非线性流水线

• 影响流水线的因素

  • 结构相关（资源冲突）
  • 数据相关（数据冲突）
  • 控制相关（控制冲突）

• 流水线的性能指标

  • 流水线的吞吐率
  • 流水线的加速比
  • 流水线的效率

• 超标量流水线的基本概念

  • 超标量流水线技术
  • 超流水线技术
  • 超长指令字

六、总线

1. 总线概述

为了更好地解决 I/O 设备和主机之间连接的灵活性问题，计算机的结构从分散连接发展为总线连接，为了进一步简化设计，又提出了各类总线标准。

• 基本概念

  • 定义

    总线是一组能为多个部件分时、共享的公共信息传送线路。在某一时刻只允许有一个部件向总线发送信息，但多个部件可同时从总线上接受相同的信息。

  • 总线设备：主设备和从设备

• 总线特性：是指机械特性（尺寸，形状）、电器特性（传输方向和有效的电平范围）、功能特性（每根传输线的功能）和时间特性（信号和时序的关系）。

• 总线的猝发传输方式，在一个总线周期内传输存储地址连续的多个数据字的总线传输方式，称为猝发传送。

• 分类

  按功能划分为以下 3 类：

  • 片内总线，是CPU芯片内部寄存器与寄存器之间、寄存器与ALU之间的公共连接线。

  • 系统总线，是计算机系统内各功能部件（CPU,主存，I/O连接）之间相互连接的总线。

    数据通路是数据流经的路径，数据总线是承载的媒介。

    按传送信息内容的不同，又可分为 3 类：

    • 数据总线，用来传输数据信息，是双向传输总线，其位数与机器字长、存储字长相关
    • 地址总线，用来指出数据总线上的源数据或目的数据所在的主存单元或 I/O 端口的地址，是单向传输总线，地址总线的位数与主存地址空间的大小有关。
    • 控制总线，用来传输控制信息，包括CPU送出的控制命令和主存（或外设）返回CPU的反馈信号。

  • 通信总线，也称为外部总线

    通信总线是在计算机系统之间或计算机系统与其他系统（如远程通信设备、测试设备）之间传送信息的总线

• 结构

  • 单总线结构，主存总线

  • 双总线结构，主存总线 和 I/O 总线

  • 三总线结构，主存总线，I/O总线，直接内存访问（DMA）总线

• 性能指标

  1.总线的传输周期，2.总线时钟周期，3.总线的工作频率， 4.总线的时钟频率， 5.总线宽度，6.总线带宽，7.总线复用，8.信号线数

2. 总线仲裁

• 集中仲裁方式

  • 链式查询方式
  • 计数器定时查询方式
  • 独立请求方式

  

• 分布仲裁方式

3. 总线操作和定时

总线定时是指总线在双方交换数据的过程中国需要时间上配合关系的控制，这种控制称为总线定时，其实质是一种协议或规则，主要有同步和异步两种基本定时方式。

• 总线传输的4个阶段

  申请分配阶段，寻址阶段，传输阶段，结束阶段

• 同步定时方式

  适用于总线长度较短及总线所接部件的存取时间比较接近的系统。

• 异步定时方式

  根据 “请求” 和 “回答” 信号的撤销是否互锁，又可分为以下 3 种类型：

  • 不互锁方式
  • 半互锁方式
  • 全互锁方式

4. 总线标准

七、输入/输出系统

1. I/O系统基本概念

• 输入/输出系统

  • 1.外部设备 2.接口 3.输入设备 4.输出设备 5.外存设备
  • I/O软件，I/O硬件

• I/O控制方式

  1）2）主要用于数据传输率较低的外部设备，3）4）主要用于数据传输率较高的设备

  1. 程序查询方式，由CPU通过程序不断查询 I/O 设备是否已做好准备，从而控制 I/O设备与主机交换信息

  2. 程序中断方式，有在 I/O 设备准备就绪并向 CPU 发出中断请求时才予以响应

  3. DMA方式，主存和 I/O 设备之间有一条直接数据通路，当主存和 I/O 设备交换信息时，无需调用中断服务程序。

  4. 通道方式，在系统中设有通道控制部件，每个通道都挂接若干外设，主机在执行 I/O 命令时，只需启动有关通道，通道将执行通道程序，从而完成 I/O 操作。

2. 外部设备

• 输入设备

  键盘，鼠标(机械式，光电式)

• 输出设备

  • 显示器

    主要参数有：屏幕大小，分表率，灰度级，刷新，刷新频率，显示存储器

    • 阴极射线管（CRT）显示器

      字符显示器 和 图形显示器

    • 液晶显示器（LCD）

    • LED（发光二极管）显示器

  • 打印机

    • 针式打印机
    • 喷墨式打印机
    • 激光打印机

• 外存储器

  磁盘存储器，磁盘阵列，光盘存储器，固态硬盘

3. I/O接口

• 功能

  1. 实现主机和外设的通信联络控制
  2. 进行地质译码和设备选择
  3. 实现数据缓冲
  4. 信号格式的转换
  5. 传送控制命令和状态信息

• 基本结构

  

• 类型

  1. 按数据传送方式可分为并行接口（一个字节或一个字的所有位同时传送）和串行接口（一位一位地传送），接口要完成数据格式的转换
  2. 按主机访问 I/O 设备的控制方式可分为程序查询接口，终端接口和 DMA接口等
  3. 按功能选择的灵活性可分为可编程接口和不可编程接口

• 端口及其编址

  对 I/O 端口的编址方式：

  • 统一编址，又称存储器映射方式
  • 独立编址，又称 I/O 映射方式

4. I/O方式

• 程序查询方式
• 程序中断方式
  • 中断的基本概念
  • 程序中断方式工作流程
  • 多重中断和中断屏蔽技术
• DMA方式
  • DMA方式的特点
  • DMA控制器的组成
  • DMA的传送方式
  • DMA的传送过程
  • DMA方式和中断方式的区别

疑难杂症

• 指导书
  • 浮点运算对阶
    • P71 T28

Computer Operating System

大纲

[考查目标]

1。掌握操作系统的基本概念、基本原理和基本功能，理解操作系统的整体运行过程。
2。掌握操作系统进程、内存、文件和 I/O 管理的策略、算法、机制以及相互关系。
3。能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用 C 语言
描述相关算法。

一、操作系统概述

（一）操作系统的概念、特征、功能和提供的服务
（二）操作系统的发展与分类
（三）操作系统的运行环境
1。内核态与用户态
2。中断、异常
3。系统调用
（四）操作系统体系结构

二、进程管理

（一）进程与线程
1。进程概念
2。进程的状态与转换
3。进程控制
4。进程组织
5。进程通信
共享存储系统；消息传递系统；管道通信。
6。线程概念与多线程模型
（二）处理机调度
1。调度的基本概念
2。调度时机、切换与过程
3。调度的基本准则
4。调度方式
5。典型调度算法
先来先服务调度算法；短作业（短进程、短线程）优先调度算法；时间片轮转调度算法；
优先级调度算法；高响应比优先调度算法；多级反馈队列调度算法。
（三）同步与互斥
1。进程同步的基本概念
2。实现临界区互斥的基本方法
软件实现方法；硬件实现方法。
3。信号量
4。管程
5。经典同步问题
生产者-消费者问题；读者-写者问题；哲学家进餐问题。
（四）死锁
1。死锁的概念
2。死锁处理策略
3。死锁预防
4。死锁避免
系统安全状态，银行家算法。
5。死锁检测和解除

三、内存管理

（一）内存管理基础
1。内存管理概念
程序装入与链接；逻辑地址与物理地址空间；内存保护。
2。交换与覆盖
3。连续分配管理方式
4。非连续分配管理方式
分页管理方式；分段管理方式；段页式管理方式。
（二）虚拟内存管理
1。虚拟内存基本概念
2。请求分页管理方式
3。页面置换算法
最佳置换算法（OPT）；先进先出置换算法（FIFO）；最近最少使用置换算法（LRU）；
时钟置换算法（CLOCK）。
4。页面分配策略
5。工作集
6。抖动

四、文件管理

（一）文件系统基础
1。文件概念
2。文件的逻辑结构
顺序文件；索引文件；索引顺序文件。
3。目录结构
文件控制块和索引节点；单级目录结构和两级目录结构；树形目录结构；图形目录结构。
4。文件共享
5。文件保护
访问类型；访问控制。
（二）文件系统实现
1。文件系统层次结构
2。目录实现
3。文件实现
（三）磁盘组织与管理
1。磁盘的结构
2。磁盘调度算法
3。磁盘的管理

五、输入输出（I/O）管理

（一）I/O 管理概述
1.I/O 控制方式
2。 I/O 软件层次结构
（二）I/O 核心子系统
1.I/O 调度概念
2。高速缓存与缓冲区
3。设备分配与回收
4。假脱机技术（SPOOLing）

一、概述

Intro

• 操作系统（Operating System, OS）是指控制和管理整个计算机系统的硬件和软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。

• 特征

  • 并发（Concurrence）

    • 并发
      • 并发是指两个或多个事件在同一时间间隔内发生
      • 操作系统中，引入进程的目的是使程序能并发执行，通过分时得以实现
      • 操作系统具有处理和调度多个程序同时执行的能力
    • 并行
      • 并行性指系统具有同时进行运算或操作的特定
      • 需要有相关硬件的支持，如多流水线或多处理机硬件环境

  • 共享（Sharing）

    • 两种方式
      1. 互斥共享方式
         • 一段时间内只允许一个进程访问该资源，如打印机
         • 临界资源或独占资源
      2. 同时访问方式
         • “同时” 指宏观上的，微观上，可能是对资源的 “分时共享”，如磁盘设备
    • 共享和并发是操作系统两个最基本的特征，两者之间互为存在的条件

  • 虚拟（Virtual）

    • 虚拟是指把一个物理上的实体变为若干个逻辑上的对应物
    • 操作系统利用多种虚拟技术来实现虚拟处理器、虚拟内存和虚拟外部设备等。
    • 虚拟技术可归纳为：时分复用技术 和 空分复用技术

  • 异步（Asynchronism）

    多道程序环境允许多个程序并发执行，但由于资源有限，进程的执行并不是一贯到底的，而是走走停停的，它以不可预知的速度向前推进，这就是进程的异步性。

• 操作系统的目标和功能

  操作系统类似于 工人 于 雇主和机器的关系

  1. 操作系统作为计算机系统资源的管理者

     • 处理机管理（进程管理）

       包括进程控制、进程同步、进程通信、死锁处理、处理机调度等

     • 存储器管理

       包括内存分配、地址映射、内存保护与共享、内存扩充

     • 文件管理

       包括文件存储空间的管理、目录管理、文件读写管理和保护

     • 设备管理

       包括缓冲管理、设备分配、设备处理、虚拟设备

  2. 操作系统作为用户与计算机硬件系统之间的接口

     • 命令接口
       • 用户利用这些操作命令来组织和控制作业的执行
       • 按作业控制方式不同分两种
         1. 联机命令接口，又称交互式命令接口，适用于分时或实时系统的接口
         2. 脱机命令接口，又称批处理命令接口，适用于批处理系统。
     • 程序接口
       • 编程人员可以使用它们来请求操作系统服务
       • 程序接口由一组系统调用命令（简称系统调用，也称广义指令）组成

  3. 操作系统用作扩充机器

     • 没有任何软件支持的计算机称为 裸机
     • 通常把覆盖了软件的机器称为扩充机器或虚拟机。

• 操作系统发展与分类

  

• 操作系统的运行环境

  • 操作系统的运行机制

    • CPU 通常执行两种不同性质的程序

      1. 操作系统内核程序
      2. 用户自编程序（应用程序）

    • 特权指令，是指计算机中不允许用户直接使用的指令，如 I/O指令、置终端指令等

    • CPU状态，用户态（目态）和 核心态（管态、内核态）

    • 现代操作系统几乎都是层次的结构，各项功能分别设置在不同的层次上。

    • 大多数操作系统内核包括四方面内容：

      1. 时钟管理

      2. 中断机制

         中断机制中，只有一小部分功能属于内核，它们负责保护和恢复中断现场的信息，转移控制权到相关的处理程序

      3. 原语（Atomic Operation）

         • 处于操作系统的最低层，是最接近硬件的部分
         • 具有原子性
         • 运行时间短，且调用频繁

      4. 系统控制的数据结构及处理

         系统中用来登记状态信息的数据结构很多。

  • 中断和异常的概念

    

    • 操作系统内核工作在核心态，用户程序工作在用户态
    • CPU运行上层程序时唯一能进入这些 “门”（从用户态进入核心态）的途径就是通过中断或异常。
    • 为了提高利用率，需要把程序未使用的资源占有权释放，而这一行为就需要通过中断实现。
    • 中断（Interruption），外中断，指来自 CPU 执行指令以外的事件的发生，这类中断与当前处理机运行的程序无关。
    • 异常（Exception）,内中断、例外或陷入（trap）,指源自 CPU 执行指令内部的事件，对异常的处理一般要依赖于当前程序的运行现场，而且异常不能被屏蔽，应立即处理。

  • 系统调用

    • 是指用户在程序中调用 操作系统所提供的一些子功能。

    • 按功能分

      设备管理 | 文件管理 | 进程管理 | 进程通信 | 内存管理

    • 用户程序可以执行陷入指令（又称访管指令或 trap 指令）来发起系统调用，请求操作系统提供服务。相当于底层操作对用户透明，用户只需调用已定义的方法或操作即可。期间，CPU 在用户态和核心态间切换

    • 访管指令是在用户态使用的，不是特权指令

      

• 操作系统的体系结构

  • 大内核
  • 微内核
  • 库操作系统

二、进程管理

进程与线程

• Intro

  • 进程（Process）,是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
  • 更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性.
  • 进程控制块（Process Control Block, PCB）,描述进程的基本情况和运行态
  • 进程映像 （进程实体）由程序段、相关数据段 和 PCB三部分构成
    • PCB是进程存在的唯一标志
    • 所谓创建/撤销进程，实质是创建进程映像中的 PCB
    • 进程映像是静态的，进程是动态的
  • 特征
    • 动态性，有着 创建、活动、暂停、终止等过程
    • 并发性，多个进程实体同时存在于内存中，能在一段时间内同时运行
    • 独立性，指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位，凡未建立 PCB 的程序，都不能作为一个独立的单位参与运行
    • 异步性，操作系统必须配置相应的进程同步机制
    • 结构性，由 PCB 对其进行描述

• 进程的状态与转换

  

  • 5 种状态
    1. 运行态
    2. 就绪态，已获得除处理机外的一切所需资源，一旦得到处理机即可运行
    3. 阻塞态，等待态，除处理机外，还需其它资源或等待某一事件
    4. 创建态
    5. 结束态
  • 状态转换
    • 运行态 - 阻塞态是主动行为，阻塞态 - 就绪态 是被动行为

• 进程控制

  一般把进程控制用的程序段称为原语.

  1. 进程的创建

     

  2. 进程的终止

     

  3. 进程的阻塞（Block）和唤醒（Wakeup）

     

  4. 进程切换

     • 注意区别 进程切换 与 处理机模式切换
     • 注意区别 调度 与 切换

     

• 进程的组织

  进程是一个独立的运行单位，也是操作系统进行，资源分配和调度的基本单位。一般由三部分组成

  1. 进程控制块，即现场

     • 是进程存在的唯一标志
     • 操作系统通过 PCB 表来管理和控制进程
     • 常用的组织方式
       1. 链接方式，将同一状态的 PCB 链接成一个队列
       2. 索引方式，将同一状态的进程组织在一个索引表中
     • 

  2. 程序段

     程序段就是能被进程调度程序调度到 CPU 执行的程序代码段。注意，多个进程可以运行同一个程序。

  3. 数据段

     一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。

• 进程的通信

  高级通信方式是指以较高的效率传输大量数据的通信方式，主要有以下三类：

  1. 共享存储
     • 通信进程间存在一块可直接访问的共享空间
     • 又分两种：低级方式的共享是基于数据结构的共享；高级方式的共享是基于存储区的共享。
     • 操作系统只负责提供存储空间和同步互斥工具（如 P V 操作）
     • 进程内的线程是自然共享进程空间的
  2. 消息传递
     • 直接通信方式，直接把消息发送给接受进程的消息缓冲队列上，
     • 间接通信方式，发送消息到某个中间实体（信箱，又称信箱通信方式），广泛应用于计算机网络，相应的通信系统称为电子邮件系统
  3. 管道通信
     • 所谓管道，是指用于连接一个读进程和一个写进程以实现它们之间的通信的一个共享文件，又名 pipe 文件。如 linux 管道
     • 管道机制提供 互斥、同步、确定对方的存在 三方面的协调能力
     • 管道也是一种文件，是一个固定大小的缓冲区
     • 半双工通信

• 线程概念和多线程模型

  1. 线程的基本概念
     • 引入进程的目的是为了更好地使用多道程序并发执行，提高资源利用率和系统吞吐量，增加并发程度
     • 引入线程的目的则是为了减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能
     • 线程是一个基本的 CPU 执行单元，也是程序执行留的最小单元
     • 由线程 ID、程序计数器、寄存器集合和堆栈组成
     • 线程是进程中的一个实体，是被系统独立调度和分配的基本单位
     • 线程也有就绪、阻塞和运行三种基本状态
     • 进程只作为除 CPU 外的系统资源的分配单元，线程则作为处理机的分配单元
  2. 线程与进程的比较
     • 调度，线程是独立调度的基本单位，进程是拥有资源的基本单位。
     • 拥有资源，进程一直都是拥有资源的基本单位，线程可访问其隶属进程的系统资源
     • 并发性，不仅进程，而且线程都可以并发执行，提高了系统的吞吐量
     • 系统开销，线程切换的开销远小于进程切换
     • 地址空间和其他资源，进程的地址空间之间相互独立
     • 通信方面，线程间可以直接读/写进程数据段来进行通信
  3. 线程的属性
  4. 线程的实现方式
     • 用户级线程（User-Level Thread, ULT）
     • 内核级线程（kernel-Level Thread, KLT），又称内核支持的线程
  5. 多线程模型
     • 多对一模型
     • 一对一模型
     • 多对多模型

处理机调度

• Intro

  • 调度

    从就绪队列中按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

  • 调度的层次

    一个作业从提交开始直到完成，往往要经历以下三级调度，

    1. 作业调度，又称高级调度，是内存与辅存之间的调度，频率低，几分钟一次，大多多道批处理系统中有，其它系统则不需要

    2. 中级调度，又称内存调度，

       • 作用是提高内存利用率和系统吞吐量
       • 挂起态，就绪态

    3. 进程调度，又称低级调度，频率很高，一般几十毫秒一次，最基本的，不可或缺

       

  • 三级调度的联系

• 调度的时机、切换和过程

  进程调度和切换程序是操作系统内核程序

  • 不能马上进行进程调度与切换的情况，应置系统的请求调度标志，直到以下过程结束
    1. 在处理中断的过程中
    2. 进程在操作系统内核程序临界区中
    3. 其他需要完全屏蔽中断的原子操作过程中
  • 应马上进行进程调度与切换的情况如下：
    1. 发生引起调度条件且当前进程无法继续运行下去时
    2. 中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。

• 进程调度方式

  1. 非剥夺调度方式，非抢占方式

     适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统

  2. 剥夺调度方式，抢占方式

     该方式对提高系统吞吐率和响应效率都有明显的好处，但 “剥夺” 不是一种任意性行为，必须遵循一定的原则，主要有优先权、短进程优先和时间片原则等。

• 调度的基本准则

  1. CPU 利用率，尽可能使 CPU 保持 “忙” 状态，使这一资源利用率最高
  2. 系统吞吐量，表示单位时间内 CPU 完成作业的数量
  3. 周转时间
     • 是指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行及进行输入/输出操作所花费时间的总和。
     • 周转时间 = 作业完成时间 - 作业提交时间
     • $带权周转时间 = \frac{作业周转时间}{作业实际运行时间}$
     • 平均周转时间，平均带权周转时间
  4. 等待时间，
     • 指进程处于等处理机状态的时间之和。
     • 处理机调度算法只影响作业在就绪队列中等待所花的时间
     • 该指标可以衡量一个调度算法的优劣
  5. 响应时间
     • 在交互式系统中是重要的标准之一

• 典型的调度算法

  1. 先来先服务（FCFS）调度算法

  2. 短作业优先（SJF）调度算法

     • “饥饿现象”，长作业长期不被调度

  3. 优先级调度算法

     • 剥夺式 / 非剥夺式优先级算法

     • 静态 / 动态 优先级，动态调整的主要依据有占有 CPU 时间的长短、就绪进程等待 CPU 时间的长短

     • 优先级设置参考准则

       • 系统进程 > 用户进程
       • 交互型进程 > 非交互型进程（或前台进程 > 后台进程）
       • I/O 型进程 > 计算型进程

  4. 高响应比优先调度算法

     • 主要用于作业调度，是对 FCFS 和 SJF 的一种综合平衡

     • 克服饥饿状态，兼顾了长作业

       $$R_p = \frac{等待时间+要求服务时间}{要求服务时间}$$

1. 时间片轮转调度算法

   • 主要适用于分时系统
   • 时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力

2. 多级反馈队列调度算法（融合了前几种算法的优点）

   • 是时间片轮转调度算法 和 优先级调度算法的综合与发展，可以兼顾多方面的系统指标
   • 实现思想
     1. 多个就绪队列，第 1 级优先级最高
     2. 不同队列，每个进程的运行时间片越小
     3. 仅当第 1 - (i-1) 级队列均为空时，才会调度第 i 级队列，如有新进程进入高优先级队列，则被抢占

进程同步

• Intro

  • 临界资源

    • 访问临界资源的那段代码称为临界区
    • 临界资源的访问过程：
      1. 进入区
      2. 临界区，又称临界段
      3. 退出区
      4. 剩余区

  • 同步

    也称直接制约关系，指两个或多个进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系，该关系源于它们之间的相互合作

  • 互斥

    也称间接制约关系，需遵循以下准则：

    1. 空闲让进
    2. 忙则等待
    3. 有限等待
    4. 让权等待

• 实现临界区互斥的基本方法

  • 软件实现方法

    进入区设置标志，退出区修改标志

    1. 单标志法，（违背 空闲让进）要求两个进程必须交替进入临界区
    2. 双标志法先检查，（违背 忙则等待）
    3. 双标志法后检查，可能导致 “饥饿” 现象
    4. Peterson’s Algorithm，是算法一和算法三的结合

  • 硬件实现方法

    通过硬件支持实现临界段问题的方法称为低级方法，或元方法

    1. 中断屏蔽方法，限制了处理机交替执行程序的能力，因此执行的效率会明显降低。
    2. 硬件指令方法，

• 信号量

  • Intro

    • 可以用来解决互斥与同步问题，信号量只能被两个标准的原语 wait(S) | P 和 signal(S) | V 访问，也可记为 “P 操作” 和 “V 操作”
    • 原语是指完成某种功能且不被分割、不被中断执行的操作序列，通常可有硬件实现。

  • Intro

    1. 整型信号量

       • wait(S) {
           while(S <= 0);
           S = S - 1;
         }
         signal(S) {
           S = S + 1;
         }
         

       • 被定义为一个用于表示资源数目的整型量 S.

       • 未遵循 “让权等待” 的准则，而是使进程处于 “忙等” 的状态

    2. 记录性信号量

       • typedef struct {
           int value;
           struct process *L;
         } semaphore;
         
         void wait(semaphore S) {  // 相当于申请资源
           S.value--;
           if(S.value < 0) {
             add this process to S.L;
             block(S.L);
           }
         }
         
         void signal(semaphore S) {  // 相当于释放资源
           S.value++;
           if(S.value <= 0){
             remove a process P from S.L;
             wakeup(P);
           }
         }
         

       • S.value < 0, 表示该类资源已分配完，因此进程调用 block 原语，进行自我阻塞，放弃处理机，并插入该类资源的等待队列 S.L. 遵循 “让权等待” 准则

       • 若 S.value 加 1,后，仍然 <= 0, 表示 S.L 中仍有等待该资源的进程被阻塞，故还应调用 wakeup 原语，将 S.L 中的第一个等待进程唤醒。

    3. 利用信号量实现同步

       S 初始值为 0，$P_2$ 等待 $P_1$ 的结果， $P_2$ 先执行 P(S) , S 为 0，执行 P 操作会把进程 $P_2$ 阻塞，并放入阻塞队列；当进程 $P_1$ 得出结果，执行 V 操作，把 $P_2$ 从 阻塞队列中放回就绪队列，当 $P_2$ 得到处理机时，就得以继续执行。

    4. 利用信号量实现进程互斥

       S 初始值为 1，临界区无进程，进程执行 P 操作，把 S 减为 0，然后进入临界区；临界区有进程，S 为 0，再有进程执行 P 操作将会被阻塞。

       • 在同步问题中，若某个行为要用到某种资源，则在这个行为前面 P 这种资源一下；若某个行为会提供某种资源，则在这个行为后面 V 这种资源一下。
       • 在互斥问题中，P 、V 操作要紧夹使用互斥资源的那个行为，中间不能有其他冗余代码。

    5. 利用信号量实现前驱关系

       • 信号量也可用来描述程序之间或语句之间的前驱关系

    6. 分析进程同步和互斥问题的方法步骤

       1. 关系分析
       2. 整理思路
       3. 设置信号量

• 管程

  • 管程是由一组数据及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。
  • 组成，类似面向对象中的一个抽象类
    1. 局部于管程的共享数据结构数据说明
    2. 对该数据结构进行操作的一组过程
    3. 对局部与管程的共享数据设置初始值的语句
  • 基本特性
    1. 局部于管程的数据只能被局部于过程内的过程所访问
    2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
    3. 每次仅允许一个进程在管程内执行某个内部过程

死锁

三、内存管理

概念

虚拟内存管理

四、文件管理

Intro

文件系统实现

磁盘组织与管理

五、输入/输出（I/O）管理

Intro

I/O 核心子系统

Computer Network

大纲

[考查目标]

1。掌握计算机网络的基本概念、基本原理和基本方法。
2。掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组成和特点，理
解典型网络设备的工作原理。
3。能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计
和应用。

一、计算机网络体系结构

（一）计算机网络概述
1。计算机网络的概念、组成与功能
2。计算机网络的分类
3。计算机网络的标准化工作及相关组织
（二）计算机网络体系结构与参考模型
1。计算机网络分层结构
2。计算机网络协议、接口、服务等概念
3.ISO/OSI 参考模型和 TCP/IP 模型

二、物理层

（一）通信基础
1。信道、信号、宽带、码元、波特、速率、信源与信宿等基本概念
2。奈奎斯特定理与香农定理
3。编码与调制
4。电路交换、报文交换与分组交换
5。数据报与虚电路
（二）传输介质
1。双绞线、同轴电缆、光纤与无线传输介质
2。物理层接口的特性
（三）物理层设备
1。中继器
2。集线器

三、数据链路层

（一）数据链路层的功能
（二）组帧
（三）差错控制
1。检错编码
2。纠错编码
（四）流量控制与可靠传输机制
1。流量控制、可靠传输与滑轮窗口机制
2。停止-等待协议
3。后退 N 帧协议（GBN）
4。选择重传协议（SR）
（五）介质访问控制
1。信道划分
频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理。
2。随即访问
ALOHA 协议；CSMA 协议；CSMA/CD 协议；CSMA/CA 协议。
3。轮询访问
令牌传递协议
（六）局域网
1。局域网的基本概念与体系结构
2。以太网与 IEEE 802.3
3.IEEE 802.11
4。令牌环网的基本原理
（七）广域网
1。广域网的基本概念
2.PPP 协议
3.HDLC 协议
（八）数据链路层设备
1。网桥的概念和基本原理
2。局域网交换机及其工作原理。

四、网络层

（一）网络层的功能
1。异构网络互联
2。路由与转发
3。拥塞控制
（二）路由算法
1。静态路由与动态路由
2。距离-向量路由算法
3。链路状态路由算法
4。层次路由
（三）IPv4
1.IPv4 分组
2.IPv4 地址与 NAT
3。子网划分与子网掩码、CIDR
4.ARP 协议、DHCP 协议与 ICMP 协议
（四）IPv6
1.IPv6 的主要特点
2.IPv6 地址
（五）路由协议
1。自治系统
2。域内路由与域间路由
3.RIP 路由协议
4.OSPF 路由协议
5.BGP 路由协议
（六）IP 组播
1。组播的概念
2.IP 组播地址
（七）移动 IP
1。移动 IP 的概念
2。移动 IP 的通信过程
（八）网络层设备
1。路由器的组成和功能
2。路由表与路由转发

五、传输层

（一）传输层提供的服务
1。传输层的功能
2。传输层寻址与端口
3。无连接服务与面向连接服务
（二）UDP 协议
1.UDP 数据报
2.UDP 校验
（三）TCP 协议
1.TCP 段
2.TCP 连接管理
3.TCP 可靠传输
4.TCP 流量控制与拥塞控制

六、应用层

（一）网络应用模型
1。客户/服务器模型
2.P2P 模型
（二）DNS 系统
1。层次域名空间
2。域名服务器
3。域名解析过程
（三）FTP
1.FTP 协议的工作原理
2。控制连接与数据连接
（四）电子邮件
1。电子邮件系统的组成结构
2。电子邮件格式与 MIME
3.SMTP 协议与 POP3 协议
（五）WWW
1.WWW 的概念与组成结构
2.HTTP 协议

一、计算机网络体系结构

概述

计算机网络是一些互联的、自治的计算机系统的集合.

• 功能：数据通信，资源共享，分布式处理，提高可靠性，负载均衡等。

• 分类

  • 按分布范围

    1. 广域网（WAN），使用交换技术
    2. 城域网（MAN），多采用以太网技术，因此也常并入局域网的范围进行讨论
    3. 局域网（LAN）,使用广播技术
    4. 个人区域网（PAN）,也称无线个人区域网（WPAN）

  • 按传输技术

    是否采用分组存储转发与路由选择机制是点对点式网络与广播式网络的重要区别，广域网基本属于点对点网络。

    • 广播式网络
    • 点对点网络

  • 按拓扑结构

    1. 星形网络

       每个终端或计算机都以单独的线路与中央设备相连，现在中央设备一般是交换机或路由器。

       便于集中控制和管理，缺点是成本高，中心结点对故障敏感。

    2. 总线形网络

       建网容易，增减结点方便，节省线路。缺点是重负载时通信效率不高，总线任意一处对故障敏感

    3. 环形网络

       如令牌环局域网

    4. 网状型网络

       多仔广域网中，可靠性高，缺点是控制复杂，线路成本高。

  • 按使用者

    • 公用网，public
    • 专用网，private

  • 按交换技术

    • 电路交换网络

      如传统电话网络， 包括建立连接、传输数据和断开连接 三个阶段

    • 报文交换网络，也称存储-转发网络

      用户数据加上源地址、目的地址、校验码等辅助信息，然后封装成报文。

    • 分组交换网络，也称包交换网络

      基于报文交换网络，并且其缓冲易于管理，平均时延小，平均占用缓冲区更少，易于标准化。目前流行。

  • 按传输介质，有线，无线。

• 计算机网络的标准化工作及相关组织

  RFC（Request For Comments）; 4个阶段。

  组织：ISO, ITU, IEEE

• 性能指标

  • 带宽，Bandwidth，本来表示通信线路允许通过的信号频带范围，单位是Hz。计算机网络中，带宽表示网络的通信线路所能传送数据的能力，单位是比特 b/s.

  • 时延，Delay，包括发送时延，传播时延，处理时延和排队时延。

    • 发送时延 = 分组长度 / 信道宽度

      高速链路只是减少了发送时延

    • 传播时延 = 信道长度 / 电磁波在信道上的传播速率

  • 时延带宽积 = 传播时延 x 信道带宽

  • 往返时延，RTT

  • 吞吐量，Throughput，指单位时间内通过某个网络（或信道，接口）的数据量，受网络带宽或网络额定速率的限制。

  • 速率，speed，单位 b/s. kb, Mb, Gb

• 体系结构，层次和各层的协议及层间接口的集合。

  

  • 协议

    • 即网络协议，两个（或多个）水平实体间通信的规则的集合；
    • 由三部分组成：1. 语法，规定传输数据格式 2. 语义，规定所要完成的功能 3. 同步，规定了执行各种操作的条件、时序关系等。

  • 接口，是同一结点内相邻两层间交换信息的连接点，是一个系统的内部规定。SAP（Service Aceess Point）

  • 服务，是垂直的，供上层调用。服务原语有 4 类：1. 请求 2. 指示 3. 响应 4. 证实

    1. 面向连接服务与无连接服务

       如 TCP vs IP、UDP

    2. 可靠服务和不可靠服务

       只有被高一层实体 “看得见” 的功能才能称为服务

    3. 有应答服务和无应答服务

       如，文件传输服务 vs WWW服务

• OSI参考模型

  

  • 物理层，
    • 传输单位：比特，任务是透明地传输比特流
    • 功能：在物理媒体上为数据端设备透明地传输原始比特流
    • 接口标准：EIA-232C、EIA/TIA RS-449、CCITT的X.21等
    • 研究内容
      • 一些物理媒体，不在物理层协议之内
  • 数据链路层
    • 传输单位：帧，任务是将网络层传来的 IP 数据包组装成帧
    • 功能：组帧、差错控制、流量控制和传输管理等。
    • 特殊子层——介质访问子层，处理广播式网络中 如何控制对共享信道的访问 问题。
    • 协议：SDLC、HDLC、PPP、STP和 帧中继等
  • 网络层
    • 传输单位：数据报，它关心的是通信子网的运行控制，主要任务是把网络层的协议数据单元（分组）从源端传送到目的端，为分组交换网上的不同主机提供通信服务。
    • 功能：对分组进行路由选择，并实现流量控制、拥塞控制、差错控制和网际互联等功能。
      • 因特网是由大量易购网络通过 路由器，Router相互连接起来的。因此，因特网的网络层也称网际层或IP层。
    • 协议：IP、IPX、ICMP、IGMP、ARP、RARP 和 OSPF等
  • 传输层
    • 传输单位：报文段（TPC）或用户数据报（UDP），负责主机中两个进程之间的通信
    • 功能：为端到端连接提供可靠的传输服务，为端到端连接提供流量控制、差错控制、服务质量、数据传输管理等服务。
    • 特点
      • 数据链路层提供的是点对点的通信，一个点指一个硬件地址或IP地址
      • 传输层提供的是端对端的通信，端指的是一个点的一个端口，一个进程
      • 传输层具有复用和分用的功能。
    • 协议：TPC、UDP
  • 会话层
    • 允许不同主机上的各个进程之间进行会话
    • 可以使用校验点使会话在通信失效时从校验点继续恢复通信，实现数据同步
  • 表示层
  • 应用层

• TCP / IP 模型

  • 网络接口层
    • 只是指出主机必须使用某种协议与网络连接，以便在其上传递 IP 分组。
    • 功能：从主机或结点接收 IP 分组，并把它们发送到指定的物理网络上。
  • 网际层（主机-主机）
    • TPC/IP模型的关键部分，将分组发往任何网络
    • 协议：IPv4, IPv6
  • 传输层（应用-应用或进程-进程）
    • 功能：使得发送端和目的端主机上的对等实体进行会话
    • 协议：TPC, UDP
  • 应用层（用户-用户）
    • 协议：Telnet、FTP、DNS、SMTP、HTTP

• 两种模型的比对

  • OSI参考模型在网络层支持无连接和面向连接的通信，传输层仅有面向连接

  • TCP/IP模型认可可靠性是端到端的问题，因此它在网际层仅有一种无连接的通信模式，但传输层支持无连接和面向连接两种模式。

  • 学习模型

    数据部分SDU - 加上控制信息PCI - PDU

    

二、物理层

通信基础

• 基本概念

  • 数据：传送信息的实体

  • 信号：数据的电器或电磁表现，是数据在传输过程中的存在形式，有模拟信号和数字信号两种形式，传输方式有串行传输和并行传输两种方式。

  • 码元，用一个固定时长的信号波形（数字脉冲）表示一位 k 进制数字，是数字通信中数字信号的计量单位。

  • 一个数据通信系统主要划分为信源、信道和信宿三部分。

    • 信道有基带信道和宽带信道 及 无线信道和有线信道之分
    • 交互方式：单工、半双攻、全双工
    • 信道的极限容量是指信道的最高码元传输速率或信道的极限信息传输速率

  • 速率，单位时间内传输的数据量

    • 码元传输速率，码元速率，波形速率

      单位是波特（Baud），码元速率与进制无关

    • 信息传输速率，信息速率，比特率

      单位是比特/秒 ， b/s

• 奈奎斯特 (Nyquist) 定理

  • 理想低通信道下的极限数据传输率 = $2Wlog_2V$，单位 b/s.
    • W 为理想低通信道的带宽，单位为 Hz
    • V 为每个码元离散电平的数目。如16种码元需要 4 位二进制位。
  • 结论：
    • 任何信道，码元传输的速率是有上限的。
    • 信道的频带越宽，就可用更高的速率进行码元的有效传输
    • 给出了码元传输速率的限制，但没有给出信息传输速率的限制

• 香农定理

  • 信号的极限数据传输率 = $Wlog_2(1+S/N)$，单位 b/s.
    • W 为信道的带宽
    • S 为信道所传输信号的平均功率
    • N 为信道内部的高斯噪声功率。 S/N 为信噪比, 信噪比 = $10log_{10}(S/N)$，单位 dB。如S/N=10 时，信噪比为 10 dB， S/N = 1000时，信噪比为 30dB.
  • 结论
    1. 信道的带宽或信道的信噪比越大，信息的极限传输速率越高。
    2. 对一定的传输带宽和一定的信噪比，信息传输速率的上限是确定的。
    3. 只要信息的传输速率低于信道的极限传输速率，就能找到某种方法来实现无差错的传输。
    4. 实际信道能达到的传输速率要低很多
    5. 表明，一个码元对应的二进制位数是有限的。

编码与调制

调制指把数据变换为模拟信号的过程；编码指把数据变换为数字信号的过程。

1. 数字数据编码为数字信号，数字发送器

   用于基带传输，

   

   • 非归零编码
   • 曼彻斯特编码，Manchester Encoding
     • 每个码元中间出现电平跳变
     • 所占频带宽度是原始基带宽度的两倍
     • 用于以太网
   • 差分曼彻斯特编码
     • 常用于局域网传输
     • 可实现自同步，且抗干扰性较好
   • 4B/5B编码

2. 数字数据调制为模拟信号，调制器

   调制方法有：

   • 幅移键控（ASK），振幅

   • 频移键控（FSK）, 频率

   • 相移键控（PSK），相位

   • 正交振幅调制（QAM）,ASK 与 PSK的结合

     

1. 模拟数据编码为数字信号，PCM编码器

   常用于对音频信号进行编码的脉码调制（PCM）。包括三个步骤：采样、量化和编码。

   采样定理：

   • $f_{采样}$必须大于等于最大频率$f$的两倍
   • 又称奈奎斯特定理

2. 模拟数据调制为模拟信号，放大器调制器

电路交换、报文交换与分组交换

1. 电路交换

   • 三个阶段：连接建立，数据传输，连接释放
   • 优点：通信时延小，有序传输，没有冲突，使用范围广，实时性强，控制简单
   • 缺点：建立连接时间长，线路独占，灵活性差，难以规格化
   • 适于数据量很大且传送时间远大于呼叫时间

2. 报文交换

   • 优点：无需建立连接，动态分配线路，提高线路可靠性，提高线路利用率，提高多目标服务
   • 缺点：存在转发延迟，要求网络节点有较大缓存空间

3. 分组交换

   较先进，解决大报文传输的问题

   • 优点：无建立时延，线路利用率高，简化了存储管理，加速传输，减少了出错率和重发数据量
   • 缺点：存在传输时延，需要传输额外的信息量，需对分组按编号进行排序（若采用虚电路，但有呼叫建立，数据传输和虚电路释放三个过程）
   • 适于计算机之间的突发式数据通信

数据报与虚电路

面向连接的虚电路方式 和 无连接的数据报方式是分组交换的两种方式，都由网络层提供。

• 数据报，存储转发

• 虚电路

  • 将数据报方式与电路交换方式结合起来，充分发挥两种方法的优点。
  • 三个阶段：呼叫建立，数据传输和虚电路释放
  • 连接一旦建立，就固定了虚电路所对应的物理路径
  • 电路并不是 专用的，

• 比较

  

传输介质

• 双绞线

  • 减少相邻导线的电磁干扰
    • 绞合
    • 外面加上一个金属丝编织成的屏蔽网，屏蔽双绞线（STP）,非屏蔽双绞线（UTP）
  • 通信距离 几千米到数十千米，太远时，模拟传输，用放大器放大衰减的信号；数字传输，用中继器将失真信的信号整形。
  • 带宽取决于铜线的粗细和传输的距离

• 同轴电缆

  • 组成：内导体、绝缘层、网状编织屏蔽层和塑料外层

  • $50\Omega$ ,传送基带数字信号，局域网和$70\Omega$传送宽带信号，有线电视系统。

  • 抗干扰，广泛用于传输较高传输速率的数据，其传输距离更远，但价格较双绞线贵。

• 光纤

  • 利用光导纤维传递光脉冲来进行通信，带宽范围极大
  • 组成：线心和包层
  • 多模光纤，从不同角度入射的多束光线可在一条光纤中传输，
    • 光源：发光二极管
    • 会逐渐展宽，造成失真，只适合近距离传输
  • 单模光纤，光纤直径减小到仅一个光波长度时，不会产生多次反射。
    • 直径只有几微米，成本高
    • 光源：定向性很好的激光二极管
    • 衰减小，适合远距离传输

• 无线传输介质

  • 无线电波，传输距离长，向所有方向传播
  • 微波、红外线和激光
    • 高带宽无线通信，
    • 直线传播，又称视线介质，传输距离有限，需借助中继站来接力，如卫星。
    • 卫星通信，通信容量大，距离远，覆盖广，缺点是端到端传播时延长。

• 物理层的接口特性

  • 机械特性，规定物理连接时所采用的规格、引线的数目、引脚的数量和排列情况等
  • 电气特性，规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制等。
  • 功能特性，某一电压表示意义，接口部件的信号线（数据线，定时线）的用途
  • 规程特性，定义个物理线路的工作规程和时序关系。

物理层设备

• 中继器，又称转发器
  • 将信号整形并放大再转发出去
  • 使用中继器连接的几个网段仍然是一个局域网，
  • 工作在物理层，不能连接两个具有不同速率的局域网，没有存储转发功能，两端网段必须使用同一个协议。
  • 放大器放大模拟信号（将信号放大），中继器放大数字信号（信号整形再生）
• 集线器 Hub
  • 多端口中继器，工作在物理层
  • 扩大网络传输范围，
  • 主要使用双绞线组建共享网络
  • 只能工作在半双工状态

三、数据链路层

本章是历年考察重点，研究的是 “点到点” 之间的通信。

功能

主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。

1. 为网络层提供服务

   • 无确认的无连接服务，适用于实时通信 或 误码率较低的通信信道，如以太网
   • 有确认的无连接服务，适用于误码率较高的通信信道，如无线通信
   • 有确认的面向连接服务，适用于通信要求（可靠性、实时性）较高的场合。有连接就一定有确认。

2. 链路管理

3. 帧定界、帧同步与透明传输，HDLC通信中，用标识位 F（01111110）来标识帧的开始和结束。
4. 流量控制，限制发送方的数据流量，使其发送速率不超过接收方的接收能力。
5. 差错控制
   • 位错，CRC检错，ARQ重传出错帧
   • 帧错，引入定时器和编号机制

组帧

组帧主要解决帧定界、帧同步、透明传输等问题。网络信息传输的最小单位是 帧。

1. 字符计数法，帧头设置计数字段。
2. 字符填充的首尾定界符法，使用特殊字符：开始（DLE STX）结束（DLE ETX）.
3. 比特填充的首尾标志法，使用 01111110标志开始和结束。容易由硬件实现，性能优于字符填充.常用。
4. 违规编码法，借用违规编码序列定始终。如局域网IEEE 802。只适用于采用冗余编码的特殊编码环境，常用。

差错控制

1. 检错编码
   • 奇偶校验码
   • 循环冗余码
2. 纠错编码
   • 海明码

流量控制与可靠传输机制

1. 流量控制、可靠传输 与 滑动窗口机制

   流量控制的基本方法是由接收方控制发送方发送数据的速率，常见方式有：停止-等待协议和滑动窗口协议。

   • 停止-等待流量控制基本原理，每次只发送一帧，然后等待反馈。

   • 滑动窗口流量控制基本原理，

     • 发送窗口$W_T$代表在还未收到对方确认信息的情况下发送方最多还可以发送多个数据帧。

     • 接受窗口，控制可以 接收/抛弃 哪些数据帧，

     • 接收窗口大小为 1 时，可保证帧的有序接受

     • 窗口的大小在传输过程中是固定的，与 传输层的滑动窗口协议的区别

       停止-等待协议：$W_T=1,W_R=1$

       后退 N 帧协议：$W_T>1,W_R=1$

       选择重传协议：$W_T>1,W_R>1$

   • 可靠重传机制

     数据链路层的可靠性传输通常使用确认和超时重传两种机制来完成。

     • 确认，捎带确认

     • 超时重传，发送方设置计时器

     • 自动重传请求（ARQ），接收方请求出错帧。传统自动重传请求分三种：

       • Stop-and-Wait ARQ
       • Go-Back_N ARQ
       • 选择性重传ARQ

       数据链路层中流量控制和可靠传输是交织在一起的。

2. 单帧滑动窗口 与 停止-等待协议

   • 用 1 bit 对帧编号
   • 每发送一个数据帧就停止并等待。

   

3. 多帧滑动窗口 与 后退 N 帧协议（GBN）

   • 接收方只允许按顺序接收帧；

   • 接收端可以在连续收到好几个正确的数据帧后，才对最后一个数据帧发确认信息。

   • 若采用 n 比特对帧编号，发送窗口大小应满足 $1\le W_T\le 2^n-1$。

   • 会有 在重传时 必须把原来已经传送正确的数据帧进行重传 的现象。
   • 累计确认

   

4. 多帧滑动窗口 与选择重传协议（SR）

   • 只重传出现差错的数据帧或计时器超时的数据帧

   • 更有效的差错处理策略，一旦接收方怀疑帧出错，就会发送一个否定帧 NAK给发送方，重传。

   • 窗口需满足: $W_R+W_T\le 2^n \quad,W_R\le 2^{n-1}\le W_T$

   • 接受窗口为最大值时，$W{Tmax}=W{Rmax}=2^{n-1}\quad,一般地 W_T = W_R$

     

• 信道效率，也称信道利用率，从时间角度的定义：信道效率是对发送方而言的，是指发送方在一个发送周期的时间内，有效地发送数据所需要的时间占整个发送周期的比率。
• 信道吞吐率 = 信道利用率 x 发送方的发送速率。

介质访问控制，

MAC子层，任务是为使用介质的每个结点 隔离 来自同一信道上其它结点所传送的信号，决定广播信道中信道分配。

1. 信道划分介质访问控制

   信道划分实质就是通过分时，分频，分码等方法把原来的一条广播信道，逻辑上分为几条用于两个结点之间通信的互不干扰的子信道，实际上就是把广播信道转变为点对点信道。

   

   • 频分多路复用（FDM）,静态
     • 相邻信道之家需加入“保护频带”，防止信道间相互干扰
     • 充分利用传输介质的带宽，系统效率较高；技术成熟，容易实现
     • 共享时间，而不共享空间
   • 时分多路复用（TDM），静态
     • 一条物理信道按时间片 轮流地分配给多个信号使用。
     • 统计时分多路复用（STDM，又称异步时分多路复用）是TDM的一种改进，采用STDM帧，不固定分配时隙，而按需动态地分配时隙。可相对提高线路的利用率。
     • 共享空间，而不共享时间
   • 波分多路复用（WDM），动态
     • 即光的频分多路复用，波长分解复用器
     • 即共享空间，又共享时间。黄豆与绿豆在同一辆车运送，到达 C 站后再分开。
   • 码分多路复用（CDM），动态
     • 采用不同编码。即共享信道的频率，又共享时间。
     • 合波器，分波器
     • 码分多址（CDMA）,一种方式。码片（Chip）
     • 频谱利用率高、抗干扰能力强、语音质量好等优点，还可以减少投资和降低运行成本，主要用于无线通信系统，特别是移动通信系统。

2. 随机访问介质访问控制

   • info

     • 解决随机接入发生的碰撞，每个用户需要按照一定的规则反复地重传它的帧，直到无碰撞地通过。
     • 常用协议核心思想都是：胜利者通过争用获得信道，从而获得信息的发送权，因此，随机访问介质控制协议又称 争用协议。
     • 是一种将广播信道转化为点到点信道的行为。

   • ALOHA协议， Additive Link On-line HAwaii system.

     • 纯ALOHA协议
       • 重传策略，让各站等待一段随机的时间，直到重传成功。
       • 吞吐量 $S=Ge^{-2G},\quad G为网络负载$
     • 时隙ALOHA协议
       • 规定只能在每个时隙开始时才能发送一个帧
       • $S=Ge^{-G}$，比纯ALOHA网络的吞吐量大了 1 倍。

   • CSMA协议，载波侦听多路访问（Carrier Sense Multiple Access, CSMA）

     

     1. 1-坚持 CSMA

        侦听到信道忙后，继续坚持侦听信道；侦听到信道空闲后，发送帧的概率为 1。

     2. 非坚持CSMA

        如果信道忙，那么放弃侦听，等待一个随机的时间再继续侦听，若空闲，立即发送。

     3. p-坚持CSMA

        • 用于时分信道
        • 若忙，等待下一个时隙再侦听；若空闲，以概率 p 发送数据，以概率 1-p 推迟到下一个时隙

   • CSMA/CD 协议，载波侦听多路访问/碰撞检测（CSMA with Collision Detection）

     • 适用于总线形网络或半双工网络环境
     • 碰撞检测，就是边发送边侦听
     • 工作流程可简单概括为：先听后发，边听边发，冲突停发，随机重发。
       • 传输拥塞信号后，适配器采用 截断二进制指数退避算法 等待一段随机事件
         • 重传所需的退避时间就是 r 倍的基本退避时间。
     • 总线的传播时延对 CSMA/CD的影响很大，采用CSMA/CD协议的以太网不可能进行全双工通信，只能进行半双工通信。
       • 设$\tau$为单程传播时延，以太网端到端往返时间$2\tau$为争用期，（又称冲突窗口或碰撞窗口）
       • 最小帧长 = 总线传播时延 x 数据传输率 x 2

   • CSMA/CA 协议，载波侦听多路访问/碰撞避免（CSMA with Collision Avoidance）

     • CSMA/CD协议已成功应用于使用有线连接的局域网，CSMA/CA应用于无线网
     • 采用二进制指数退避算法，当且仅当检测到信道空闲且这个数据帧是要发送的第一个数据帧时，才不使用退避算法
     • 三种机制来实现碰撞避免
       • 预约信道
       • ACK帧
       • RTS/CTS 帧，可选，主要用于解决无线网中的 “隐蔽站” 问题

3. 轮询访问介质访问控制

   • 典型协议是 令牌传递协议，主要用在令牌环局域网。

   • 令牌是由一组特殊的比特组合而成的帧，只有拿到令牌的计算机才可以发送数据帧

   • 适合负载很高的广播信道，即指多个结点在同一时刻发送数据概率很大的信道。

局域网

要熟悉局域网的各种协议.

• 基本概念和体系结构

  • 特点

    1. 为一个单位所拥有，且地理范围和站点数目均有限
    2. 所有站点共享较高的总带宽（即较高的数据传输率）
    3. 较低的时延和较低的误码率
    4. 各站为平等关系而非主从关系
    5. 能进行广播和组播

  • 局域网的特性主要由三个要素决定

    • 拓扑结构

      星形、环形、总线形，星形和总线形结合的复合型

    • 传输介质

      双绞线（主流）、铜缆和光纤等

    • 介质访问控制方式，最重要，决定技术特性

      CSMA/CD、令牌总线和令牌网，前两种主用于总线形网络，令牌环主要用于环形局域网

  • 三种特殊的局域网拓扑实现

    • 以太网（使用范围最广），逻辑拓扑是总线形结构，物理拓扑是星形或拓展星形结构
    • 令牌环（Token Ring,IEEE 802.5）,逻辑拓扑是环形结构，物理拓扑是星形结构
    • FDDI（光纤分布数字接口，IEEE 802.8）,逻辑拓扑是环形结构，物理拓扑是双环结构

  • IEEE 802

    • 局域网参考模型只对应与OSI的数据链路层和物理层
    • 由于以太网的垄断地位，几乎成为局域网的代名词，802 LLC子层作用已经不大，现在许多网卡仅装有 MAC 协议而没有 LLC 协议。
    • 逻辑链路控制（LLC）子层
      • 向网路层提供无确认无连接、带确认无连接、面向连接、高速传送服务
    • 媒体介入控制（MAC）子层
      • 功能：组帧和拆卸帧、比特传输差错检测、透明传输

    

• 以太网 与 IEEE 802.3

  • Intro

    • IEEE 802.3标准是一种基带总线形的局域网标准，描述物理层和数据链路层的MAC子层的实现方法。
    • 以太网逻辑上总线形拓扑，所有计算机共享一条总线，信息以广播方式发送，使用CSMA/CD方式对总线进行访问控制，符合DIX Ethernet V2标准，（与IEEE 802.3差别很小，故802.3 局域网常简称为以太网）
    • 以太网简化通信，采用无连接的工作方式，不发送数据帧编号，不要求接收方发送确认，最大努力交付数据，提供不可靠服务，差错的纠正由高层完成。

  • 以太网的传输介质与网卡

    • 使用集线器的以太网仍是一个总线网，属于一个冲突域。
    • 网卡，网络适配器（Adapter）或网络接口卡（NIC）
      • 是局域网中连接计算机和传输介质的接口，不仅能实现与局域网传输介质之间的物理连接和电信号匹配，还涉及帧的发送与接收、帧的封装与拆封、介质访问控制、数据的编码与解码及数据缓存功能等。
      • 每个网卡有一个唯一代码，称为 介质访问控制（MAC）地址。该地址用于控制主机在网络上的数据通信。
      • 工作在物理层，只关注比特。

    

  • 以太网的MAC帧

    • MAC地址，又称物理地址，长 6 字节。高24位为厂商代码。

    • 两种标准：DIX Ethernet V2 和 IEEE 802.3

      • 有CSMA/CD算法可知以太网帧的最短帧长为 64B，MAC帧的首尾部长度为18B. 所以数据最短为 46B，最大 1500B是规定，没有为什么。

      

  • 高速以太网

    速率达到或超过 100Mb/s的以太网称为高速以外网

    • 100BASE-T 以太网
    • 吉比特以太网
    • 10 吉比特以太网

• IEEE 802.11

  • 是无线局域网的一系列协议标准
  • 采用CAMA/CA协议
  • 有固定基础设施无线局域网
    • 基本服务及（Basic Service Set, BSS）,一个基站（接入点Access Point, AP，作用和网桥类似），若干移动站。
    • 主干分配系统（Distribution System, DS）
    • 扩展的服务集（Extended Service Set, ESS）,可通过门桥（Portal，作用相当于网桥）为无线用户提高到非 802.11 无线局域网的接入
    • 
  • 无固定基础设施无线局域网自组织网络
    • 没有接入点（AP）
    • 与移动IP并不相同
    • 具有自己特定的路由选择协议，可以不和因特网相连
    • 

• 令牌环网的基本原理

  

  • 物理上采用星形拓扑结构，逻辑上仍是环形拓扑结构，其标准由IEEE 802.5 定义。

广域网

• 基本概念

  • 广域网是因特网的核心部分，任务是长距离运送主机所发送的数据。

  • 

  • 广域网由一些结点交换机及连接这些交换机的链路组成。

    • 结点交换机在单个网络中转发分组，结点之间都是点到点相连。
    • 路由器在多个网络构成的互联网中转发分组
    • 路由选择（形成路由表和转发表），分组转发
    • 
  • PPP协议 和 HDLC协议是常用的两种广域网数据链路层控制协议

• PPP协议，（Point-to-Point Protocol）

  • 面向字节

  • 设计目的主要是用来通过拨号或专线方式建立点对点连接发送数据，使其成为各主机、网桥和路由器之间简单连接的一种共同的解决方案。

  • 三部分

    1. 链路控制协议（LCP）
    2. 网络控制协议（NCP）
    3. 一个将 IP 数据报封装到串行链路的方法。信息部分长度受MTU限制。

  • PPP 帧的格式

    

  • PPP 是点对点，不是总线，无须采用CSMA/CD协议，没有最短帧一说，所以信息段占0-1500B

• HDLC协议，高级数据链路控制（High-level Data Link Control, HDLC）

  • 面向比特

  • 基于两种配置，非平衡配置和平衡配置

  • 3 种站类型：主站（命令帧）、从站（响应帧）和复合站（命令帧和复合帧）。

  • 3 中数据操作方式：正常响应方式，异步平衡方式，异步响应方式

  • HDLC帧

    

    

数据链路层设备

• 网桥的概念及其基本原理

  • Intro
    • 网桥工作在链路层的 MAC 子层，可以使以太网各网段成为隔离开的碰撞域
    • 网桥处理数据的对象是帧，中继器、放大器处理数据的对象是信号，所以它们是工作在物理层 的设备。
    • 网桥的基本特点，见书。
    • 网桥的优缺点，见书。
  1. 透明网桥（选择的不是最佳路由）
  2. 源路由网桥（选择的是最佳路由）
  3. 两种网桥的比较

• 局域网交换机及其工作原理

  1. 局域网交换机
     • 工作在数据链路层
     • 虚拟局域网（Virtual LAN，VLAN）不仅可以隔离冲突域，而且可以隔离广播域
  2. 原理
  3. 特点，见书
  4. 两种交换模式
     • 直通式
     • 存储转发式

四、网络层

功能

1. 异构网络互联
   • 网络互联通常是指用路由器进行网络互联和路由选择
   • 虚拟互联网络也就是逻辑互联网络，可简称为 IP网络
   • 中间设备，中间系统，中继系统
     1. 物理层：中继器，集线器（Hub）
     2. 数据链路层中继系统：网桥或交换机
     3. 网络层：路由器
     4. 网络层以上：网关
2. 路由与转发
   • 路由选择，路由选择协议，生成路由表
   • 分组转发，转发表由路由表得出。
3. 拥塞控制
   • 随着网络负载的增加，网络吞吐量可能进入的状态：轻度拥塞，拥塞，死锁
   • 作用是确保子网能够承载所达到的流量，这是一个全局性的过程，涉及网络中所有主机、路由器及导致网络传输能力下降的所有因素。
   • 方法
     • 开环控制，静态预防方法，在做决定时不考虑当前网络的状态
     • 闭环控制，动态方法，基于反馈环路的概念

路由算法

1. 静态路由与动态路由

   常见的动态路由算法分两类：距离-向量路由算法 和 链路状态路由算法

2. 距离-向量路由算法

   • 常见算法是 RIP算法，它采用 “条数” 作为距离的度量
   • 最短（最小代价）通路

3. 链路状态路由算法

   • 典型算法是 OSPF算法
   • Dijsktra最短路径算法计算路由

4. 层次路由

IPv4

1. IPv4分组

   • IPv4分组的格式

     • 固定部分为 20 B.
     • 首部长度，总长度，片偏移的单位分别为 4B, 1B, 8B
     • fields
       • 首部长度，16位，指首部和数据之和的长度，单位字节，最大长度 65535B.以太网帧的最大传输单元（MTU）为1500B.
       • 标识，16位，计数器，每产生一个数据报就加 1，分片的多个数据报标识相同。
       • 标志，3位，最低位 MF: 1 表示还有分片 0 表示最后一个分片。中间位 DF：为 0 时才允许分片。
       • 片偏移，13位，分片后，某片在原分组中的相对位置。单位 8 B，即分片长度为 8B（64位）的整数倍
       • 生存时间（TTL），8位，数据报在网络中可通过的路由器数的最大值。
       • 协议，6为TCP，17为UDP

     

   • IP数据报分片

     • 目的主机使用 IP 首部中的标识、标志和片偏移字段来完成对片的重组。

   • 网络层转发分组的流程

     

     • 将 IP 地址转换成 MAC 地址，将其放到 MAC 帧首部中，然后根据这个 MAC 地址找到下一条路由器。
     • 不同网络中传送时，MAC帧中的源地址和目的地址要发生变化
     • 网桥在转发帧时，不改变帧的源地址。

2. IPv4地址与NAT

   • IPv4地址

     • IP 地址::= {<网络号>, <主机号>}

     

     • 主机号全为 0 表示本网络本身

     • 主机号全为 1 表示本网络的广播地址，又称直接广播地址

     • 127.0.0.0 保留为环路自检地址，表示任意主机本身

     • 32位全为0， 0.0.0.0 表示本网络上的本主机

     • 32位全为1， 255.255.255.255 表示整个 TCP/IP网络的广播地址，又称受限广播地址。由于路由器对广播域的隔离，其等效为本网络的广播地址。

       

     • A 减2，全 0 为保留地址，网络号为 127 的 IP 地址是环回测试地址

     • B 减1,128.0 网络号不可指派 / 65534

     • C 减1,192.0.0的网络不可指派 / 254

   • IP地址的特点

     • 路由器至少具有两个IP地址，也至少有多个硬件地址

   • 网络地址转换（NAT）

     指通过将专用网络地址（如Intranet）转换为公用地址（Internet）,对外隐藏内部管理的IP地址。

     • 路由器对目的地址是私有地址的数据报一律不进行转发

     • 专用互联网或本地互联网，私有IP地址也称为可重用地址

     • NAT 转换表 完成 本地地址 与 全球地址的相互转换，

     • 通过{本地IP地址 : 端口} - {全球IP地址: 端口}

     • 普通路由器（仅在网络层）在转发 IP 数据报时，不改变其源 IP 地址和目的地址。而NAT路由器在转发 IP 数据报时，一定要更换其IP地址。

       

3. 子网划分与子网掩码、CIDR

   • 子网划分

     • 子网划分纯属一个单位内部的事情，单位对外仍然表现为没有划分子网的网络
     • IP 地址 = {<网络号>, <子网号>, <主机号>}
     • 划分子网只是把 IP 地址的主机号这部分进行再划分。
     • 全0 或 全1的子网号 是否可用取决于路由器所用的路由选择软件是否支持全0 或全1
     • 子网中主机号全0的地址为子网的网络号，主机号全1的地址为子网的广播地址，不能被指派。

   • 子网掩码

     • 使用子网掩码来表达对原网络中主机号的借位。IP 地址与子网掩码逐位 “与”，便可得出相应子网的网络地址。
     • 默认子网掩码，
     • 路由表中信息内容，目的网络地址、子网掩码、下一跳地址

   • 无分类域间路由选择（CIDR）

     无域间路由选择是在变长子网掩码的基础上提出的一种消除传统A、B、C类网络划分，并且可以在软件的支持下实现超网构造的一种 IP 地址的划分方法。

     • IP 地址的无分类两级编址 IP::={<网络前缀>,<主机号>}
     • CIDR还是用 “斜线记法” 或称（CIDR记法），即 IP 地址/网络前缀所占比特数
     • CIDR不使用子网，但仍然使用 “掩码” 一词。
     • CIDR地址块，路由聚合，或称构成超网，有利于减少路由器之间的路由选择信息的交换，从而提高网络性能。
     • 使用CIDR时，路由表每项由 “网络前缀” 和 “下一条地址” 组成，选择路由时 使用最长前缀匹配（最佳匹配），更精确。
     • CIDR查找路由的方法，自上而下层次查找，无分类编址的路由表，二叉线索数据结构

4. ARP、DHCP与ICMP

   • IP地址与硬件地址

     • IP分组在每个网络中都被路由器解封装和重新封装，其数据链路层封装所使用的MAC地址是不断改变的，这也决定了无法使用MAC地址跨网络通信。

   • 地址解析协议（Address Resolution Protocol, ARP）

     • 完成 IP 地址到 MAC 地址的映射
     • 每台主机都设有一个 ARP 高速缓冲，用来存放本局域网上各主机和路由器的 IP 地址和 MAC 地址的映射表，称 ARP 映射表，使用 ARP 来动态维护。
     • ARP “看到了” IP地址 工作在网络层，NAT路由器 “看到了” 端口 工作在传输层。
     • 使用目的MAC地址为 FF-FF-FF-FF-FF-FF的帧广播

   • 动态主机配置协议（Dynamic Host Configuration Protocol, DHCP）

     • 常用于给主机动态地分配 IP 地址，
     • 应用层协议，基于 UDP
     • 工作原理
       • 客户/服务器方式
       • DHCP服务器的回答报文称为提供报文
       • DHCP发现消息 - DHCP提供消息 - DHCP请求消息 - DHCP确认消息
     • 租用期

   • 网际控制报文协议（Internet Control Message Protocol, ICMP）

     让主机或路由器报告差错和异常情况

     • IP 层协议

     • A. ICMP差错报告报文

       1.终点不可达 2.源点抑制 3.时间超过 4.参数问题 5.改变路由（重定向）

     • B. ICMP询问报文

       • 1.回送请求和回答报文 2.时间戳请求和回答报文 3.掩码地址请求和回答报文 4.路由器询问和通告报文。前两类常用。
       • 常见应用粉组网间探测PING（应用层，B1） 和 Traceroute（网络层 A3）.

• IPv6

  1. IPv6的主要特点
     • 16B, 128位，首部长度时 8B 的整数倍
  2. IPv6地址
     • 每 4 位用一个十六进制数表示，并用冒号分隔每 16 位

• 路由协议

  1. 自治系统（Autonomous System, AS）

     • 单一技术管理下的一组路由器

  2. 域内路由与域间路由

     • 内部网关协议（Interior Gateway Protocol, IGP）
       • 使用最多，如 RIP 和 OSPF
     • 外部网关协议（External Gateway Protocol, EGP）
       • 使用最多的是 BGP-4

  3. 路由信息协议（Routing Information Protocol, RIP）

     RIP 是一种分布式的基于距离向量的路由选择协议，最大优点就是简单。

     • RIP规定
       1. 距离向量，跳数
       2. 距离等 16，表示网络不可达，因而 RIP 只适合小型互联网
     • RIP的特点（注意与OSPF的特点比较）
       1. 仅和相邻路由器交换信息
       2. RIP 收敛
       3. RIP是应用层协议，使用UDP传送数据（端口520）。
     • 距离向量算法
       • 每个路由表项: <目的网络 N, 距离 d, 下一跳路由器 X>
       • RIP 默认超时时间为 180 s.
       • 步骤见书 P178

  4. 开发最短路径优先（OSPF）协议

     使用分布式链路状态路由算法.

     • OSPF协议的基本特点
       • 洪泛法
       • “链路状态” 说明本路由器和哪些路由器相邻及该链路的 “度量”（或代价）
       • 只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。
       • OSPF是网络层协议，直接使用 IP 数据报传送（其 IP 数据报首部的协议字段为 89）
       • 根据 IP 分组的不同服务类型（TOS）而设置成不同的代价。
       • 多路径间的负载平衡
       • 每个链路状态都有一个 32 的序号，序号越大，状态就越新。
     • OSPF的基本工作原理
       • 链路状态数据库，即全网的拓扑结构图，在全网内是一致的。
       • 每个路径根据该全网拓扑结构图，使用 Dijkstra 最短路径算法计算最优路径以构造路由表。路由表只存储 “下一跳”
       • 区域，将利用洪泛法交换链路状态信息的范围局限于每个区域而非整个自治系统，减少了这个网络上的通信量。主干区域。
     • OSPF的五种分组类型
       1. 问候分组
       2. 数据库描述分组
       3. 链路状态请求分组
       4. 链路状态更新分组
       5. 链路状态确认分组

  5. 边界网关协议（Border Gateway Protocol, BGP）

     • Intro
       • BGP 是不同自治系统的路由器之间交换路由信息的协议，是一种外部网关协议。
       • 常用于互联网的网关之间
       • 路由表包含，1）已知路由器的列表 2）路由器能达到的地址及到达每个路由器的路径的跳数
       • BGP 只能力求寻找一条能够到达目的网络且比较好的路由，而非寻找一条最佳路由。
       • 采用路径向量路由选择协议，应用层协议，基于 TCP
     • 工作原理
       • BGP 所交换的网络可达性信息就是要到达某个网络所要经过的一系列 AS.
       • BGP 支持 CIDR, 路由表项包括目前的网络前缀、下一跳路由器，以及到达该目的网络所要经过的各个自治系统序列
       • BGP-4使用 4 中报文
         1. 打开（Open）报文
         2. 更新（Update）报文
         3. 保活（Keepalive）报文
         4. 通知（Notification）报文

     

• IP组播

  1. 组播的概念
     • 组播机制是为了能够支持像视频点播和视频会议这样的多媒体应用
     • 仅应用于 UDP
     • 组播地址表示一组地址，在 D 类地址空间空分配。
     • 主机使用一个称为 IGMP（因特网组管理协议）的协议加入组播组。
     • 组播需要路由器的支持才能实现，组播路由器。
  2. IP组播地址
     • D 类地址范围是 224.0.0.0 - 239.255.255.255，一个 D 类 IP 地址标志一个组播组。
     • 组播数据报，首部中协议字段值是 2. 表明使用 IGMP.
     • IP 组播分为两种
       1. 只在本局域网上进行硬件组播
       2. 在因特网的范围内进行组播
     • 组播 IP 地址与以太网硬件地址的映射关系不是唯一的。
  3. IGMP与组播路由算法
     • 因特网组管理协议（Internet Group Management Protocol, IGMP），使路由器知道组播成员的信息
     • 组播路由选择协议
       • 组播路由选择实际上就是要找出以源主机为根节点的组播转发树，
     • IGMP 让连接到本地局域网上的组播路由器知道本局域网上是否有主机参加或退出了某个组播组。

• 移动IP

  1. 移动 IP 的概念
     • 移动 IP，支持移动性的因特网体系结构与协议；
     • 区别与移动自网络
     • 区别与动态 IP
  2. 移动 IP 通信过程
     • 本地地址，转交地址，移动绑定

• 网络层设备

  1. 路由器的组成和功能
     • 任务是连接异构网络并完成路由转发
     • 路由器隔离了广播域
     • 结构：路由选择和分组转发；模型：路由器是网络层设备，实现下三层
     • 存储转发设备
       • 网桥实现了物理层和数据链路层，那么网桥可以互联两个物理层和数据链路层不同的网络
       • 但中继器是直通式设备，实现物理层后，却不能互联两个物理层不同的网段。
     • 路由选择处理机
     • 分组转发：交换结构，一组输入端口，一组输出端口
       • 交换方法：存储器，总线，互联网络
  2. 路由表与路由转发
     • 路由表项：目的网络 IP 地址、子网掩码、下一跳 IP 地址、接口

五、传输层

传输层提供的服务

• 传输层的功能

  • 通信部分的最高层，用户功能的最低层
  • 只有主机的协议栈才有传输层和应用层，而路由器只用到下三层
  • 提供应用进程之间的逻辑通信（即端到端的通信），网络层提供的是主机间的逻辑通信
  • 复用和分用，注意区别与网络层的 复用，分用
  • 对收到的报文进行差错检测（首部和数据部分），网络层只检查 IP 数据报首部，不检查数据部分。
  • 提供两种不同的传输协议， TCP（面向连接，虚电路） 和 UDP（无连接，数据报）

• 传输层的寻址与端口

  • 端口是传输层的服务访问点（TSAP）,标识主机应用进程，类似于 IP 和 MAC地址

  • 是软件端口，区别与路由器或交换机上的硬件端口

  • 端口号，长16 bite, 标识 65536个不同端口号

    • 服务端使用的端口号

      1. 熟知端口号，0 - 1023，IANA（互联网地址指派机构）指派给 TCP/IP 最重要的应用程序

         

      2. 登记端口，1024 - 49151，使用这类端口必须在 IANA登记，以防止重复

    • 客户端使用的端口号，49152 - 65535，又称短暂端口号（临时端口号）

  • 套接字

    • 套接字 = （主机 IP 地址， 端口号），唯一标识网络中一台主机和其上的一个应用（进程）
    • 在网络中采用发送方和接收方的套接字（Socket）组合来识别端点

• 无连接服务和面向连接服务

  • TCP 不提供广播和组播服务；增加了开销（确认、流量控制、计时器及连接管理）；主适用于可靠性更高德场合，如文件传输协议（FTP）,超文本传输协议（HTTP），远程登录（TELNET）

  • UDP

    • UDP 在 IP 之上仅提供两个附加服务：多路复用 和 对数据的错误检查

    • 简单，执行速度快，实时性好

    • 小文件传送协议（TFTP）、DNS、SNMP和实时传输协议（RTP）

UDP 协议

• UDP 数据报

  • 概述
    • 常用于一次性传输较少数据的网络应用
    • 常用于多媒体应用（IP 电话、实时视频会议、流媒体等）
    • 可靠数据传输相对实时性来说不重要
    • 维护可靠性的工作需要用户在应用层完成
    • UPD面向报文，一次交付一个完整的报文，报文不可分割，是 UDP 数据报处理的最小单位。
  • 首部格式
    • 两部分：UDP 首部（8B） 和用户数据
    • 首部包含 4 个字段
      1. 源端口，不需要时可用全 0
      2. 目的端口
      3. 长度，最小是 8，仅有首部
      4. 校验和，可选，不需要，设全 0
    • 接收方发现目的端口号不正确，丢弃报文，并由 ICMP 发送 “端口不可达” 差错报文给发送方

• UDP 校验

  

  • 12B的伪首部仅为了计算校验和，即检查了UPD 数据报，又对 IP 数据报的源 IP 地址和目的 IP 地址进行了检验。
  • UDP 校验和计算方法，二进制反码运算求和再取反。
    • 若 UDP 数据报部分的长度不是偶数个字节，则需填入一个全 0 字节，该字节和伪首部一样，是不发送的。
    • 检错能力并不强，却简单、处理速度快

TCP 协议

• 特点

  • 主要解决传输的可靠、有序、无丢失和不重复问题
  • 提供全双工通信，发送缓存和接受缓存
  • 面向字节流，

• TCP报文段

  

  • TCP传送的数据单元称为报文段，分首部和数据两部分，首部最短 20 B，后面有 4N 字节是根据需要而增加选项，通常长度为 4B 的整数倍。
  • TCP 报文段既可以用来运载数据，又可以用来建立连接、释放连接和应答
    1. 序号，4B，TCP是面向字节流一的（即 TCP 传送时是逐个字节传送的），所以 TCP 连接传送的数据流中的每个字节都编上一个序号。序号字段的值指的是本报文段所发送的数据的第一个字节的序号。
    2. 确认号，4B，是期望收到对方的下一个报文段的数据的第一个字节的序号
    3. 数据偏移，即首部长度，4位，单位是32位（4B）,当该字段值为 15 时，达到 TCP 首部的最大长度 60B
    4. 保留字段，应置为 0
    5. 紧急位 1 URG，为 1，表示紧急指针字段有效，相当于高优先级的数据，需要和紧急指针配套使用，即数据从第一个自己到紧急指针所指字节就是紧急数据
    6. 确认位 2 ACK，为 1，表示确认号字段有效，为 0，则无效。TCP规定，在连接建立后所有传送的报文段都必须把 ACK 置 1.
    7. 推送位 3 PSH（Push），为 1，接受 TCP 尽快交付给接受应用进程，而不再等整个缓存都填满后再向上交付
    8. 复位位 4 RST（Reset），为 1，表明 TCP 连接出现严重差错，必须释放链接，然后再重新建立运输连接
    9. 同步位 5 SYN，为 1，表示这是一个连接请求（SYN=1; ACK=0）或连接接收报文（SYN=1; ACK=1）
    10. 终止位 6 FIN （Finish），为 1，表示数据发送完毕，并要求释放传输连接
    11. 窗口，2B，单位字节，指出现在允许对方发送的数据量
    12. 校验和，2B, 检验首部和数据，也要加上伪首部，只需将 UDP 伪首部的第 4 个字段，即协议字段的17 改成 6，其他和 UDP 一样。
    13. 紧急指针，16 位，指出本报文段中紧急数据公有多少字节
    14. 选项，长度可变，（Maximum Segment Size, MSS）,MSS 是 TCP 报文段中数据字段的最大长度。
    15. 填充字段，使整个首部长度是 4B的整数倍。

• TCP 连接管理

  • tips

    • 每条 TCP 连接有两个端点，连接的端口称为 套接字（socket）或插口，唯一地被两个端点（即套接字）确定
    • 连接的建立采用 客户/ 服务器 方式。
    • 连接的三个阶段：连接的建立、数据传送和连接释放

  • TCP 连接的建立，3 次握手

    

    • 服务器端的资源是在完成第二次握手时分配的，客户端的资源是在完成第三次握手时分配的，这就使得服务器易于收到 SYN 洪泛攻击

  • TCP 连接的释放，4 次握手

    

    

• TCP 可靠传输

  1. 序号
  2. 确认，默认使用累计确认
  3. 重传，导致重传：
     • 超时
       • TCP 采用一种自适应算法计算超时计时器的重传时间
       • $新RTT_S=(1-\alpha)\times(旧RTT_S)+\alpha\times(新RTT样本)$（Round-Trip Time, RTT）
         • $0\le\alpha\lt1$，接近 0，表示新旧变化不大，RTT 值更新较慢；接近 1，旧的受新的影响较大，RTT值更新较快。
         • 推荐值 0.125
       • 超时重传时间（Retransmission Time-Out, RTO）
         • $RTO = RTT_S+4\times RTT_D$
         • $RTT_D$ 是 RTT的偏差的加权平均值，它与 $RTT_S$ 和新 RTT 样本之差有关。
           • 第一次测量时， $RTT_D$取为测量到的 RTT 样本值得一半
           • 之后，$新 RTT_D=(1-\beta)\times(旧RTT_D)+\beta\times|RTT_S - 新RTT样本|$
           • 其中，$\beta$ 是个小于 1 的系数，推荐 0.25
     • 冗余 ACK
       • 超时触发重传存在的一个问题是超时周期旺旺太长
       • 快速重传，冗余 ACK 就是再次确认某个报文段的 ACK，而发送方先前已经收到过该报文段的确认。
  4. 校验机制 ，与 UDP 校验一样

• TCP 流量控制

  • 基于滑动窗口协议
  • 接受窗口，rwnd, 接收方通过调整 TCP 报文段首部中的 “窗口” 字段值来限制发送方发送速率
  • 拥塞窗口，cwnd, 发送方根据其对当前网络拥塞程度的估计而确定的窗口值，其大小与网络的带宽和时延密切相关
  • 发送方的发送窗口的实际大小取 rwnd 和 cwnd 中的最小值
  • 传输层和数据链路层的流量控制的区别
    • 传输层定义端到端用户之间的流量控制，数据链路层定义两个中间的相邻节点的流量控制
    • 数据链路层的滑动窗口协议的窗口大小不能动态变化，传输层的则可以动态变化

• TCP 拥塞控制

  • 与流量控制的异同

    • 相似之处，两者都通过控制发送数据的速率来达到控制效果
    • 不同，拥塞控制是一个全局性的过程，涉及所有的主机、路由器 以及与降低网络传输性能有关的所有因素；流量控制往往是指点对点的通信量的控制，即接受端控制发送端

  • 4 种算法：

    • 慢开始和拥塞避免

      1. 慢开始算法

         cwnd初始为1个MSS, 每经过一个 RTT ，拥塞窗口 cwnd 就会加倍，增大道一个规定的慢开始门限 ssthresh (阈值)，然后改用拥塞避免算法

      2. 拥塞避免算法

         每经过一个 RTT，拥塞窗口 cwnd 就会增加 一个 MSS，不再是加倍，线性增长，当出现一次超时（网络拥塞），令慢开始门限 ssthresh 等于当前 cwnd 的一般

         根据 cwnd 的大小 执行不同的算法

         • cwnd < ssthresh, 使用慢开始算法
         • cwnd > ssthresh, 使用拥塞避免算法
         • cwnd = ssthresh, 皆可

      3. 网络拥塞的处理

         • 只要发送方检测到 超时时间的发生， ssthresh 就设置为出现拥塞时 cwnd 值得一半，cwnd 重新设置为 1，执行慢开始算法。

         • 若 2cwnd > ssthresh, 则下一个 RTT 的 cwnd 等于 ssthresh。即慢开始阶段 cwnd 不能超过 ssthresh值

         • 不能完全避免拥塞

         • “乘法减小” 和 ‘“加法增大’

           

    • 快重传和快恢复，是对上面方法的改进

      1. 传重传

         • 快重传并不是取消重传计时器，而是在某些情况下可更早地重传丢失的报文段
         • 当发送方连续收到 三个重复的 ACK 报文时，直接重传对方尚未收到的报文段，而不必等待那个报文段设置的重传计时器超时。

      2. 快恢复

         原理：发送端收到连续三个冗余 ACK（即重复确认）时，执行 “乘法减小”算法，把慢开始门限 ssthresh 设置为出现拥塞时发送方 cwnd 的一半，与慢开始不同，它把 cwnd 设置为慢开始门限 ssthrsh 改变后的数值而不是 1（因此成为快恢复）.然后执行拥塞避免算法（“加法增大”）

         

    • 当发送方检测到超时的时候，就采用慢开始和拥塞避免，当发送方接受到冗余 ACK 时，就采用快重传和快恢复。

六、应用层

Intro

1. 客户/服务器模型

   常见应用包括Web、文件传输协议（FTP）、远程登录和电子邮件

2. P2P模型

   • 任意一对计算机——称为对等方（Peer）,流行的应用有PPlive、Bittorrent 和电驴等。

域名系统（DNS）

• Intro

  • 域名系统（Domain Name System, DNS），用来将便于记忆的主机名转换为便于机器处理的 IP 地址。
  • 采用 C/S 模型，其协议运行在 UDP 之上，使用 53 号端口

• 层次域名空间

  • 采用层次树结构的命名方法，

  • 任何一个连接到因特网的主机或路由器，都有一个唯一的层次结构名称，即域名（Domain Name）,其中域是名字空间中一个可被管理的划分，每个域名都有标号序列组成，标号之间用点 “.” 隔开。

  • 每个域由不同的组织进行管理，每个组织都可以将它的域再分成一定数目的子域，并将这些子域委托给其他组织去管理

  • tips

    1. 标号中的英文不区分大小写
    2. 标号中除连字符（_）外不能使用其他的标点符号
    3. 每个标号不能超过 63 个字符，完整域名不超过 255个字符
    4. 低级域名在左边，顶级域名在最右边

  • 顶级域名（Top Level Domain, TLD）

    1. 国家顶级域名（nTLD）

    2. 通用顶级域名（gTLD）

       .com-公司；.net-网络服务机构；.org-非营利性组织；.gov-美国政府部门

    3. 基础结构域名，仅一个，即arpa, 用于反向域名解析，又称反向域名

       

• 域名服务器

  • Intro

    • 因特网的域名系统被设计成一个联机分布式的数据库系统，

  • 4 种类型的域名服务器

    1. 根域名服务器

       • 最高层次的域名服务器，知道所有的顶级域名服务器的 IP 地址
       • 有 13 个根域名服务器（冗余服务器的集群），
       • 用来管管辖顶级域，通常并不直接把待查询的域名直接转换成 IP 地址，而是告诉本地域名服务器下一步应当找哪个顶级域名服务器进行查询

    2. 顶级域名服务器

       • 负责管理在该顶级域名服务器注册的所有二级域名
       • 应答可能是最后结果，也可能是下一步应当查找的域名服务器的 IP 地址

    3. 授权域名服务器（权限域名服务器）

       • 每台主机都必须在授权域名服务器处登记
       • 许多域名服务器都同时充当本地域名服务器和授权域名服务器
       • 授权域名服务器总能将其管辖的主机名转换为该主机的 IP 地址

    4. 本地域名服务器

       • 本地域名服务器对域名系统非常重要
       • Windows配置本地连接时，就需要填写DNS地址，即本地DNS

       

• 域名解析过程

  • Intro

    • 正向解析，把域名映射称为 IP 地址
    • 反向解析，把 IP 地址映射称为域名
    • 为了提高 DNS 查询效率，在域名服务器中广泛地使用了高速缓存。

  • 两种方式

    • 递归查询，会造成根域名服务器负载过大，几乎不用

    • 递归和迭代相结合的查询

      

文件传输协议（FTP）

• FTP 的工作原理

  • 文件传输协议（File Transfer Protocol, FTP）
  • C/S 工作方式， TCP
  • 端口 21

• 控制连接（端口 21）与数据连接（端口 20）

电子邮件

• 电子邮件系统的组成结构

  • 三个最主要的构建：用户代理（User Agent）、邮件服务器、电子邮件使用的协议（SMTP、POP3或 IMAP）

    

    

  • 邮件服务器

    • 同时充当客户和服务器

• 电子邮件格式与MIME

  • 电子邮件格式
    • 一个电子邮件分为信封和内容两大部分，邮件内容又分为首部和主体，主体由用户自由撰写。
    • 邮件系统会自动地将信封所需的信息提取出来并写在信封上。
  • 多用途网际邮件扩充（Multipurpose Internet Mail Extensions, MIME）
    • 增加邮件主体的结构，并定义了传送非 ASCII码的编码规则
    • 

• SMTP 和 POP3

  • 简单邮件传输协议（Simple Mail Transfer Protocol, SMTP）
    • C/S | TCP 连接 | 端口 25
    • 1.连接建立 2.邮件传送 3.连接释放
  • 邮局协议（Post Office Protocol，POP3）
    • C/S | TCP 连接 | 端口 110
    • 两种规则方式
      • 下载并保留
      • 下载并删除
  • 网际报文存取协议（IMAP）

万维网（WWW）

• WWW的概念与组成结构

  • 万维网（World Wide Web, WWW）是一个资料空间

  • 超文本标记语言（HyperText Markup Language, HTML）

  • 万维网的内核部分是由三个标准构成的

    1. 统一资源定位符（URL）

       • 负责标识万维网上的各种文档

       • 一般形式 <协议>://<主机>:<端口>/<路径>

       • 常见协议有 http, ftp等

    2. HTTP，应用层协议，TCP

    3. HTML，一种文档结构的标记语言

  • 万维网是无数个网络站点和网页的集合

• 超文本传输协议（HTTP）

  • Intro

    • HTTP定义了浏览器怎样向万维网服务器请求万维网文档，以及服务器怎样把文档传送给浏览器
    • 是面向事务（Transaction-oriented）的协议，规定了浏览器和服务器之间的请求和响应的格式与规则，是万维网能够可靠交换文件的重要基础

  • HTTP 的操作过程

    

  • HTTP 的特点

    • 无状态
    • cookie是一个存储在用户主机的文本文件，用于web服务识别用户

    • HTTP使用的 TCP是面向连接的，但 HTTP本身是无连接的

    • 持久连接，（HTTP/1.1 支持）

      • 非流水线，HTTP/1.1默认。
      • 流水线

    

  • HTTP的报文结构

    • HTTP是面向文本的（Text-Oriented）,因此报文中的每个字段都是一些 ASCII码串。
    • 请求报文
    • 相应报文
    • 

855

• Reference

  • 南京大学计算机科学与技术845考研资料

  • book

    • 南瓜书

  • 经验贴

    https://github.com/nju-kaoyan/nju_ai_20/wiki

  • 参考book

  

Examination Syllabus

• 基础级

  中文题目只涉及初级编程分5个段位

  青铜

  理解并掌握简单数据类型及表达式、程序的顺序执行结构和简单分支结构。具备使用一门编程语言进行简单的计算、基本的格式化输入输出以及解决简单分支问题的能力。

  白银

  在达到青铜段位要求的基础上，理解并掌握程序的循环结构。具备编程解决复杂嵌套分支和嵌套循环问题的能力。

  黄金

  在达到白银段位要求的基础上， 理解并掌握数组（包括高维数组和字符串）和结构体等概念，具备编程解决相关问题的能力。

  白金

  在达到黄金段位要求的基础上，理解并掌握函数和递归的概念，具备使用函数和递归解决较为复杂的综合性问题的能力，并掌握一定的调试技巧。

  钻石

  在达到白金段位要求的基础上，掌握简单排序、二分查找算法，具备解决较为复杂的综合性问题的能力，能够编写并调试代码量超过50行的程序。

• 乙级

  中文题目只涉及基础编程最难到排序算法

  考生应具备以下基本能力：

    1. 基本的C/C++的代码设计能力，以及相关开发环境的基本调试技巧；   
    2. 理解并掌握最基本的数据存储结构，即：数组、链表；   
    3. 理解并熟练编程实现与基本数据结构相关的基础算法，包括递归、排序、查找等；   
    4. 能够分析算法的时间复杂度、空间复杂度和算法稳定性；   
    5. 具备问题抽象和建模的初步能力，并能够用所学方法解决实际问题。     
  

• 甲级

  英文题目涉及基础数据结构

  在达到乙级要求的基础上，还要求：

    1. 具有充分的英文阅读理解能力；   
    2. 理解并掌握基础数据结构，包括：线性表、树、图；   
    3. 理解并熟练编程实现经典高级算法，包括哈希映射、并查集、最短路径、拓扑排序、关键路径、贪心、深度优先搜索、广度优先搜索、回溯剪枝等；   
    4. 具备较强的问题抽象和建模能力，能实现对复杂实际问题的模拟求解。   
  

• 顶级

  国际竞赛水平相当涉及高级数据结构与经典算法的应用

  在达到甲级要求的基础上，还要求：

    1. 对高级、复杂数据结构掌握其用法并能够熟练使用，如后缀数组、树状数组、线段树、Treap、静态KDTree等；   
    2. 能够利用经典算法思想解决较难的算法问题，如动态规划、计算几何、图论高级应用（包括最大流/最小割，强连通分支、最近公共祖先、最小生成树、欧拉序列）等，并灵活运用；   
    3. 能够解决复杂的模拟问题，编写并调试代码量较大的程序；   
    4. 具有缜密的科学思维，考虑问题周全，能够正确应对复杂问题的边界情况。   
  

PAT

• PAT准备，希望甲级高分，该如何高效地准备？如何算是真正有效地刷题？

• 《算法导论》

• 学会C++

• 数据结构我大概学了这几块：

  线性结构：数组，栈，队列看一下就过了；链表自己实现了一遍；常见排序理解并会写。
  树：二叉搜索树熟练（尤其是各种遍历）；AVL树和红黑树尽力理解了一下，我是真的记不住……
  图：BFS, DFS, 最短路（dijkstra, spfa, floyd）。这里的题目最常见，要能写得很灵活。
  其它：堆，背包问题（良心教程https://github.com/tianyicui/pack/blob/master/V2.pdf），贪心问题， KMP（还没遇到过题目）。
  

Reference

• 大纲