开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 网络协议 -> 北航计算机学院考研知识点总结(961) -> 正文阅读

[网络协议]北航计算机学院考研知识点总结(961)

961复习要点

文章目录

961复习要点

计组

总线与输入输出控制方式

总线分类

片内总线

CPU内部的总线。是CPU内部各寄存器之间、寄存器

与ALU之间传递信息的公共通道
系统总线
1. 数据总线
2. 地址总线
3. 控制总线
通信总线

用于计算机系统间或计算机系统与其他系统的通信

总线特性

机械特性
电气特性
功能特性
过程特性

总线仲裁(控制)方式

分布式控制方式
集中式控制方式(总线控制逻辑集中于一处)
1. 链式查询方式
  - 总线控制器收到总线申请BR，BG逐个往下传
  - 遇到某接口有总线申请，BG停止往下传
  - 该接口获得总线控制权，并建立总线忙信号BS
  优点：线少，易扩充
  
  缺点：故障敏感，优先级固定
2. 计数器定时查询方式（公平）
  - 总线控制器收到总线申请BR，计数器开始计数
  - 当某个有总线申请的设备地址与计数器一致，便获得总线使用权，并建立总线忙信号BS
  优点：优先级灵活
  
  缺点：每个设备都需与新增的设备地址线相连，线多
3. 独立请求方式（公平）
  - 每个设备有独立的请求信号线与总线同意信号
  - 总线控制器根据设备的优先级决定将总线控制权交给哪个设备
  优点：响应快，优先级灵活，请求可屏蔽
  
  缺点：每个设备都有单独的总线请求信号线与总线同意信号线，线多

总线传输的五个阶段

请求总线
总线仲裁
寻址
地址传送
状态返回

总线的通信控制方式

同步通信控制方式——数据传输在统一的时钟同步信号的控制下进行
异步通信控制方式
1. 不互锁
2. 半互锁
3. 全互锁

I/O设备

I/O设备的分类

按传送数据格式：串行接口、并行接口
按信息交换单位：
1. 字符设备：用于数据输入输出；无结构类型——交互式终端机、打印机；不可寻址，在输入输出时常采用中断驱动方式
2. 块设备：由于信息存取；有结构设备——磁盘；可寻址，以数据块为单位
按I/O方式：程序查询接口、中断接口、DMA接口、通道控制接口
按时序控制方式：同步接口、异步接口

I/O设备的编址方式

统一编址：存储器地址与I/O地址统一考虑，地址空间的一部分是存储器，另一部分是I/O，支持存储器操作的指令都可用于I/O操作——MIPS
独立编址：存储器地址与I/O地址分开，CPU具有专用的I/O指令，系统总线中具有区别存储器读写和I/O操作的控制信号，并以此区别地址总线上的地址是存储器地址还是I/O地址

I/O与主机信息交换的控制方式

程序查询方式
- I/O操作由CPU直接完成（通过执行I/O指令完成）
- 外设与CPU完全串行工作
程序中断方式
- 中断
  1. 主程序：被中断的程序
  2. 中断源：引起中断的因素
    1. 人为设置：自愿中断，可重复
    2. 程序性事故：溢出、除零
    3. 硬件故障：电池掉电、磁盘损坏
    4. I/O操作：I/O设备准备就绪、请求操作
    5. 外部事件：键盘操作
  3. 中断服务子程序：处理中断事物的程序
  4. 中断向量：中断服务子程序的入口地址
  5. 中断向量表：保存所有中断向量的内存区域，一般固定
- 中断I/O方式
  1. I/O操作仍然由CPU通过I/O指令完成
  2. 在外设准备阶段，CPU可以执行其他程序，仅在外设准备就绪后，CPU才中断正在执行的程序，处理I/O事务
  3. 在外设准备阶段，CPU与外设的工作可以认为是并行的
  4. 中断I/O方式是目前最主要的I/O方式
直接内存访问方式(DMA)
1. CPU对总线的控制被临时禁止。DMA控制器接管总线控制权，
  控制数据直接在存储器与外设之间高速交换
2. CPU不再介入具体的I/O操作，由DMA控制器来负责提供存储器地址信号、读写控制信号等
3. CPU与I/O设备在更大的程度上并行工作，效率更高
4. 数据传送结束后，通过中断方式告知CPU进行善后处理
5. CPU仅在开始DMA操作之前和完成DMA操作之后参与
  I/O处理，在DMA过程中，CPU可以运行原来的程序
6. DMA方式适合高速批量的数据传输，如视频显示刷新、磁盘存储系统的读写，存储器到存储器的传输等
- DMA工作过程
- CPU工作：初始化DMA控制块$\rightarrow $D M A 请求$ \rightarrow $D M A 响应$ \rightarrow$ DMA操作**(周期窃取)**
- CPU方式：周期窃取方式——单字传送方式；停止CPU访问内存——成组访问方式
- 周期窃取：?DMA控制器接到DMA应答信号后，通过控制逻辑向系统总线发送存储器地址信号、存储器读写控制信号、
  I/O接口读写控制信号等，完成一次数据传送。这些操作完全由硬件控制，一般仅需要一个总线周期，所以这种方式称为周期窃用（cycle-stealing)方式
通道方式
- 分类
  1. 字节多路通道：不仅允许多个设备同时操作，且允许它们同时进行传输型操作；
    
    通道的数据传输率＝各外设的数据传输率之和
  2. 选择通道：一旦选择了一个外设，即使该外设没有准备好，也只能等待；
    
    通道数据传输率＝一台设备的数据传输率
  3. 数组多路通道：允许多个设备同时工作，但只允许一个设备进行传输型操作，其他设备进行控制型操作；通道数据传输率＝各设备数据传输率之和
- 通道是一种专业控制器，具有自己的指令系统
  （基本上都是I/O指令）
- 通道执行通道程序来实现和管理I/O，CPU基本
  上不需要管理I/O，CPU的效率得到更大的提高
- 通道程序由OS根据I/O任务的需求自动生成，
  存放在存储器中，通道程序由OS管理，用户程序执行和访问通道程序

在常用的I/O控制方式中，要求主存与I/O设备之间有直接数据通路的方式是DMA方式

常见的几种总线仲裁方式中，对电路最为敏感的方式是链式查询方式

将网卡缓存器中的2000字节高效快速地传输到该计算机内存中，最合适的数据传输方式是DMA方式

在计数器定时查询总线仲裁方式下，若每次计数从上次计数的终止点开始，，则每个设备使用总线的机会相等

周期挪用常用于直接存储器存储方式的输入输出(DMA方式)

在独立请求总线仲裁方式下，若要支持N个设备，则应有N个总线请求信号和N个总线响应信号

若DMA采用周期窃取方式传送数据，则每传送一个字需占用一个总线周期的时间

中断向量是中断服务子程序的入口地址

I/O控制的四种方式：程序查询方式、访问中断方式、DMA方式、通道方式

按照信息交换的单位划分，I/O设备可以分为：字符设备和块设备

虚拟存储系统

辅助存储器(外存)

磁表面存储器：磁介质+磁头

硬磁盘存储器——数据结构与格式

盘面(磁头)Head
磁道(每个磁道包含的扇区数相同)Cylinder
扇区(最小访问单元)Sector

扇区地址：

存储容量：盘面数(磁头数) X 每盘面的磁道数 X 每磁道的扇区数 X 扇区容量

寻址时间：

数据传输率 Dr：单位时间内传输的数据位数（b/s）

廉价磁盘冗余阵列RAID(redundant array of inexpensive disks)

通过把数据分成多个数据块（Block）并行写入/读出多个磁盘以提高访问磁盘的速度
不同模式的RAID

RAID0 RAID1 RAID2
RAID3 RAID4 RAID5

虚拟存储器(虚存)

虚存空间与物理空间

用户编程空间：用户编制程序时使用的地址称为虚地址或逻辑地址，其对应的存储空间称为虚存空间或逻辑地址空间。虚存空间的用户程序按照虚地址编程并存放在辅存中

物理内存空间：计算机物理内存的访问地址称为实地址或物理地址，其对应的存储空间称为物理空间或主存空间

虚拟存储器的调度方式

页式调度
段式调度
段页式调度

页式虚拟存储器

虚存空间和主存空间按固定大小分成若干页，虚存页称为虚页，
主存页称为实页。辅存中的程序按页调入内存
虚地址格式(逻辑地址)；虚页号+页内地址——虚拟内存最大容量由计算机地址结构决定
实地址格式(物理地址)：实页号+页内地址——物理内存大小决定实地址长度
页表：记录虚页与实页的映射关系，实现虚实地址的转换；建立在内存中；页表用虚页号作为索引，页表项包括虚页对应的实页号和有效位
页表寄存器：保存页表在内存中的首地址
页内地址(页内偏移量)：页大小决定
页表大小(假设所有虚页都在使用中)：虚页数*页表项位数——虚页号是页表的索引
多级页表机制：将页表分页，当前使用的页的页表项所在页在内存，
其余在外存，页表也采用按页交换机制
当虚页不在内存时(装入位为0)，
页表提供保存该虚页的磁盘地址，
以便进行磁盘读取；有些系统采用双表结构：页表只提供虚页到实页的映射；由外页表提
供虚页到磁盘地址的映射
访存次数问题
快表TLB(translation lookaside buffer):使用Cache存储部分活跃的页表项，称为TLB（快表），它包含了最近使用的那些页表项
1. 内容：虚页号(标记TAG)、对应实页号(数据)、有效位、修改位
2. 一般采用全相联模式——等价于组数为1的n路组相联
3. TLB可以看作是主存中页表的副本，因此TLB有，页表中一定有；CACHE之后会讲
4. 使用组相联时：虚页号由**组地址+tag**构成
5. 存储管理单元MMU：将虚地址转化为实地址

某机器字长为64位，内存容量为256MB，若按字编址，则其寻址空间为0～32M-1——按字编址，256MB/64bit=32M

进程可以使用的最大地址空间受限于地址位数

虚拟地址空间可以大于物理地址空间，也可以小于物理地址空间

假设：某磁盘的可用盘面数为10，每个盘面的磁道数为100，磁盘分为8个扇区，每扇区存储512个字节，磁盘转速为6000RPM。主存与磁盘之间的数据传送采用DMA单字传送方式，单字长为32位。一条指令的最长执行时间是20微秒。

请问：

该磁盘的容量是多少？ $10\times100\times8\times512bytes=4000kbytes$

该磁盘的数据传输率是多少？ $(6000/60)\times8\times512bytes=400kbytes/s$

是否可采用一条指令执行结束时响应DMA请求的方案，为什么？

不能；

传输单字： $(32/8)/400kbytes/s=0.01\times10^{-3}s=10\mu s$ ；

即约每隔 $10\mu s$ 就会有一次DMA传送请求，采取此方案会造成数据丢失。

假设一个内存管理系统有47位的虚拟空间，每页大小为16KB，并且页表项占用8位。在每级页表大小不超过1页的情况下，需要几级页表来完成虚拟地址的映射？给出虚拟地址的结构划分，并详细解释：

每页最多可包含： $16KB/8bit=16K=2^{14}$ 个页表项，又页表以虚页号作为索引，故虚页号最大为14位;

页内偏移量： $16KB=2^{14}\rightarrow 14$ 故虚拟地址中页内偏移量为14位;

可供页目录使用的地址空间最多有： $47 ? 14 = 33$ ;

要求每级页表不超过一页—— $33 / 14 = 3 (向上取整)$ 至少需要3级页表

(这里其实不太明白，但是感觉各级目录相等比较顺眼QAQ)

$33 / 3 = 11$ 故每一级页目录均为11位；

虚拟地址的结构划分：

一级页目录二级页目录三级页目录页内偏移量
11位 11位 11位 14位

虚拟地址地址空间的大小仅取决于地址结构

页面越大，页面内部的内存碎片会越多；内碎片——分配给作业的存储空间中未被利用的部分

页面的大小会影响进程切换的速度

页面越大，运行程序所需的页面越少

现有一个容量为4GB的磁盘分区，磁盘空间以簇为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空间，即用一位(bit)标识一个簇是否被分配，则存放该位图所需簇的个数为：

需要 $4GB/4KB=2^{20}$ 个簇

每个簇用一位标识—— $2^{20}$ 位

每个簇可以存放 $2^{12}\times2^{3}=2^{15}$ 位

需要 $2^{20}/2^{15}=32$ 个簇存放

假设只考虑页内碎片和页表引起的额外内存。如进程本身占用内存的平均大小是1MB，每个页表项的大小是8B，为减少额外的内存开销，页面大小应设置为：

页内碎片：页大小决定==>取平均值(页内不产生碎片～整页分配后未使用)

页表大小：页面数量决定(存放页面所需的内存大小)

不妨设页面大小为 $2^{m}B$ ；

则进程所需的页面数量为 $2^{20}/2^{m}=2^{20-m}$ 个；

存放这些页面消耗的内存大小： $2^{20-m}\times 2^{3}=2^{23-m}$

页内碎片平均值= $(1/2)\times 2^{m}=2^{m-1}$

要使 $2^{m-1}+2^{23-m}$ 达到最小：m=12；

主存储器

存储器分类

按存储介质分
1. 半导体存储器(易失性)
2. 磁介质存储器(非易失性)
3. 光盘存储器(非易失性)
按访问方式分
1. 随机访问存储器RAM
  1. SRAM：静态存储器，集成度低，不必刷新，用作CACHE存储器，对电器干扰相对不敏感
    - 工作原理：六晶体管，触发器
  2. DRAM：动态存储器，集成度高，需要定时刷新，用作主存储器，对电器干扰相对敏感
    - 工作原理：单晶体管，电容充放电
2. 顺序访问存储器
3. 直接访问存储器
4. 只读存储器ROM
按功能分
1. 高速缓冲存储器(CACHE)
2. 主存储器
3. 辅助存储器
4. 控制存储器
存储器的层次结构

二级存储系统高速缓冲存储器主存储器
三级存储系统高速缓冲存储器主存储器辅助存储器

存储单元电路

可存储1bit二进制代码
存储位元---->存储芯片---->存储器

存储器芯片结构

基本描述：字单元数 $\times$ 字单元位数( $2^{n}\times m$ )
一维地址结构
1. 地址线n条——单向——经过译码变为 $2^{n}$ 根地址选择线
2. $2^{n}$ 选择线
3. 数据线m位——双向
二维地址结构
1. 行列相等时最佳
2. 行地址线=列地址线= $2^{n/2}$
3. $2\times2^{n/2}$ 地址选择线(行列复用则不需要乘2)
4. 数据线m条——双向—— $log_{2}m$ 位

存储器扩展

位扩展
1. 拼接数据空间
2. 地址总线不变，数据总线按扩展位数增加
3. 片选信号位数不变
字扩展
1. 拼接地址空间
2. 地址总线按扩展位数增加，数据总线不变
3. 片选信号按扩展后芯片数确定
混合扩展
1. 混合扩展同时扩展了数据空间与地址空间
2. 片选信号取决于字扩展，与位扩展无关

DRAM的刷新

刷新操作：读操作

刷新特点

按行刷新，所有芯片同时进行
刷新操作与CPU访问内存分开进行
刷新周期
刷新地址与刷新地址计数器

刷新方式

集中刷新(有 $2^{n}$ 行；设刷新周期为2ms；读写周期为 $0.5\mu s$ )

在一个时间段内，刷新存储器所有行，此时CPU停止访问内存；另一个时间段内，CPU可以访问内存，刷新电路不工作
- 集中刷新时间相当于 $2^{n}$ 个读写周期被用于刷新，CPU不工作
- 一个刷新周期中有 $2ms/0.5\mu s = 4000$ 个读写周期，其中$2^{n}\times0.5\mu s $个读写周期用于刷新，剩余读写周期用于读/写或维持信息
- 存在不能进行读写操作的死区时间
分散式刷新(有 $2^{n}$ 行；设刷新周期为2ms；存取周期为 $0.5\mu s$ )
- CPU与刷新电路交替访问内存，一个存储周期刷新1行，下一个存储周期刷新另一行，直至最后1行后，又开始刷新第1行
- 将存储周期分为用于读写与用于刷新两部分，不存在死时间，但变相增加了存取周期
- 分散刷新间隔 = 刷新行数 X 存储周期 <= 刷新周期
分布式刷新
- 保证在一个刷新周期内将存储芯片内的所有行刷新一遍，
  可能等时间间距，也可能不等
- 刷新时间间隔=刷新周期 $\times$ 行数
- 可以减少死时间，同时保证性能

动态RAM依据电容充放电原理存储信息；静态RAM依据触发器原理存储信息。

构造 $32k\times32bit$ 的存储器共需64片 $2k\times8bit$ 的SRAM存储芯片

容量 $1M\times16bit$ 的DRAM存储芯片，如采用二维地址结构，且行地址和列地址的位数相同，则行译码器输出的行选择线有1024根，该芯片的刷新地址计数器是10位

用多个容量 $1k\times4bit$ 的存储芯片，组成容量为 $64k\times8bit$ 的存储器。若将这些芯片分装在几块内存板上，每块内存板容量为 $16k\times8bit$ ，则该存储器的地址线中，必须有2根地址线用于选内存板，4根地址线用于选芯片

容量为 $32k\times16bit$ 的存储器芯片，其地址线数量和数据线数量的总和为31

p.s：地址线是地址信号线，用于传送地址信息；地址选择线用于定位存储位元

某计算机的数据总线为8位，地址总线为20位，主存按字节编址，其中地址最低的256KB主存空间为只读系统程序区，其余为用户程序区，现有若干容量为 $64k\times8bit$ 的ROM芯片和容量为 $256k\times8bit$ 的DRAM芯片：

上述规格的DRAM芯片，若行地址和列地址共享同一组芯片管脚，则所需地址管脚多少根？芯片的刷新地址计数器是多少位？

$256k=2^{18}---->行地址管脚=列地址管脚=2^{9}=512根，刷新地址计数器的位数=总行数位数=9位$

若DRAM芯片采用分布式刷新方式，且存储单元刷新间隔最长为4ms，则刷新周期是多少？

==？？？==分布式刷新方式 $? ? ? ? >$ 刷新周期= $4 m s / 512$

查阅资料得*：对于每行以4ms为刷新周期足够了，刷新循环到它需要512刷新次操作， 4ms ÷ 512 作为每次刷新的周期，（注意每次刷新周期与特定行的刷新周期的不同：每次刷新间隔指对于内存来说它隔多长时间就进行一次刷新操作，轮着刷新时，刷新的行是上一次刷新的行的下一行——是不同的两行，但对于全局内存来说确实是两次刷新操作间隔。特定哪一行的刷新周期：下一次对它进行刷新的间隔，期间要经过64次内存刷新周期才又轮得到它。）

该计算机所允许的最大主存容量是多少？

地址总线为20位，数据总线为8位，按字节编址
$2^{20}\times(8bit/8)=1MB$

构建该计算机所允许的最大容量的主存，需用上述规格的ROM芯片和DRAM芯片各多少片？

只读系统程序区 $256 K B ? ? ? ? > R O M$ ， $256 / 64 = 4$ 块

DRAM芯片 $768 K B ? ? ? ? > D R A M$ ， $768 / 256 = 3$ 块

请给出每个ROM芯片和DRAM芯片在上述主存中的地址空间范围。

$2^{20}=16^{5}---->5$ 位16进制地址码

芯片起止
ROM#1 0x00000H 0x0FFFFH
ROM#2 0x10000H 0x1FFFFH
ROM#3 0x20000H 0x2FFFFH
ROM#4 0x30000H 0x3FFFFH
DRAM#1 0x40000H 0x7FFFFH
DRAM#2 0x80000H 0xBFFFFH
DRAM#3 0xC0000H 0xFFFFFH

用于译码产生DRAM芯片片选信号的主存地址需多少位？

3块DRAM芯片，需要2位主存地址确定

https://wenku.baidu.com/view/f34bca962ec58bd63186bceb19e8b8f67c1cef27.html

指令系统与MIPS汇编

机器指令的要素

操作码
源操作数地址
目的操作数地址
下条指令的地址：只有少数指令需要指明下一条指令的地址

指令类型

数据传输指令：寄存器与存储器之间、寄存器之间传递数据
算数/逻辑运算指令：寄存器中整型数或逻辑型数据的运算操作，以及处理浮点数运算的浮点运算指令
程序控制指令：控制程序执行顺序，条件转移或跳转，子程序调用或返回
其他指令：多用户多任务系统中的特权指令；复位/暂停/空操作等指令

操作数类型

数值：无符号、定点、浮点
逻辑型数、字符
地址：操作数地址，指令地址

操作数的位置

存储器(存储器地址)
寄存器(寄存器地址)
输入输出端口(输入输出端口地址)

操作数存储方式

大端存储：最高有效字节存储在地址最小位置
小端存储：最低有效字节存储在地址最小位置

机器指令

计算机硬件可以执行的表示一种基本操作的二进制代码
1. 指令格式：操作码+操作数(操作数地址)
2. 操作码：指明指令的操作性质
3. 操作数(地址)：指明操作数的位置(或操作数本身)
操作数地址的数目
1. 三地址：
  
  OP DES Add SUR1 Add Sur2 Add
2. 双地址
  
  OP Des Add Sur Add
3. 单地址：累加器作为其中一个操作数的双操作数型，或单操作数型
  
  OP Add
4. 零地址：隐含操作数型，或无操作数型
  
  OP

指令长度

定长指令系统：MIPS
变长指令系统：一般为字节的整数倍，如80X86系统

寻址方式

形式地址：指令中直接给出的操作数的地址编码
有效地址：操作数在内存中的地址，可由形式地址和寻址方式计算得到
寻址方式：根据形式地址，计算出操作数有效地址的方法

常用寻址方式

立即寻址：操作数直接在指令代码中给出(立即寻址只能作为双操作数指令的源操作数)；操作数存放在指令中
寄存器直接寻址：操作数在寄存器中，指令地址字段给出寄存器的地址
寄存器间接寻址：操作数在存储器中，指令地址字段中给出的寄存器的内容是操作数在存储器中的地址
基址寻址/变址寻址：
- 基址寄存器+形式地址，操作数的内存地址是基址寄存器的内容与形式地址之和
- 变址寄存器+形式地址：操作数的内存地址是变址寄存器的内容与形式地址之和
相对寻址：基址寻址的特例，程序计数器PC作为基址寄存器；指令中给出的形式地址作为位移量
堆栈寻址：操作数存放在存储器中，出栈、入栈

MIPS指令格式

MIPS只有三种指令格式，32位固定长度指令格式
- R(register)类型：寄存器操作数计算，结果送寄存器
- I(Immediate)类型：使用一个16位立即数作操作数
- J(jump)类型：跳转指令，26位跳转地址
最多三地址指令： add $t0,$s1,$s2
对于Load、Store指令，单一寻址模式：Base+displacement
没有间接寻址
16位立即数——最大可表示
简单转移条件：beq、beqz等
无条件码

MIPS汇编中的算数、逻辑和移位运算

溢出检测
- 可以检测溢出异常：add、addi、sub
- 不能检测溢出异常：addu、addiu、subu
MIPS算术指令只能操作寄存器，不能指令操作内存
数据存取指令在内存和寄存器之间传输数据
分支指令中：要和PC相加(或相减)的指令数，是从分支语句的下一条指令算起的
字对齐：无论是lw还是sw，基址寄存器的值与偏移量的和始终应该是4的倍数——alignment：对象的起始地址一定要是字长的整数倍
- 16-bit立即数使用补码表示，在需要分支的时候与PC相加
- 因此可以分支到 $PC\pm2^{15}$ 字节的地方
- 改进：根据“字对齐”，其实可以分支到 $PC\pm2^{15}$ 指令字即 $PC\pm2^{17}$ 字节
- $P C = (P C + 4) + (i m m e d i a t e ? 4)$
- J-Format指令中，目标地址为26-bit立即数，利用字对齐，可以表示出32-bit地址的低28bits，剩下的最高四位根据定义，直接从PC取得

MIPS指令大全

##待补充

MIPS处理器设计

处理器设计概述

处理器的功能与组成

功能：控制指令执行
指令执行过程：取指-取数-执行
指令周期：取指周期-取数周期-执行周期
功能部件
- 指令地址部件
- 指令寄存部件
- 译码部件
- 控制信号逻辑部件
- 执行部件：ALU、寄存器等
CPU组成
- 控制单元(Controller)
- 执行单元(数据通路)

其余部分不作重点讲解

计算机性能评价

响应时间与吞吐量

响应时间：从提交作业到作业完成所花费的时间
吞吐量：一定时间间隔内完成的作业数
CPU执行时间：

$程序的CPU时钟周期数\times时钟周期长度$

$\frac{程序的CPU时钟周期数}{时钟频率}$
程序的CPU时钟周期数： $程序指令数\times每条指令的平均时钟周期数$
$C P I ：指令平均执行时钟周期数$
- 不同指令集的CPI比较没有意义
- $CPU的时钟周期数=\sum{CPI_i\times I_i}$
- $平均时钟周期数 C P I = C P U 时钟周期数 / I C (指令的条数)$
- $CPU时间=CPU时钟周期数\times时钟周期长=CPU时钟周期数/频率=(IC\times CPI)/f$
MIPS：百万指令每秒
- 不同指令集的MIPS比较没有意义
- 同一台机器，不同的测试程序测出来的MIPS值也可能不一样
- $MIPS=\frac{IC}{执行时间\times 10^{6}}=\frac{IC}{(IC\times CPI)\times10^{6}/f}=\frac{f}{CPI\times10^{6}}$
- MFLOP：百万浮点操作数每秒

计网

应用层

应用层概述

所有网络协议均为了某种应用服务
应用层的许多协议大部分是基于client/server方式
1. QQ、Weixin等使用私有协议
2. HTTP、SSH等使用开放协议
3. 均基于基于TCP、UDP、IP等底层协议
应用层协议运行在用户态，由应用程序负责管理；TCP/IP等协议运行在内核态，由操作系统负责管理；
应用程序使用网络时，需要调用操作系统提供的接口，即应用Socket API

Socket(套接字)

面向连接并发服务器——e.g TCP
无连接循环服务器——e.g UDP

辨析：面向连接即连接已建立，则不需要说明交给谁——直接send()、recv()；无连接则需要说明交给谁、接收谁发的——sendto()、recvfrom()
Telnet：使用TCP连接到特定服务器，并将输入发送给服务端，将从服务器接收的信息显示在屏幕上

WWW(万维网)

分布式超媒体 (hypermedia) 系统，是超文本 (hypertext) 系统的扩充
1. 一个超文本由多个信息源链接成，超文本是万维网的基础
2. 超媒体与超文本的区别是文档内容不同
HTTP——HyperText Transfer Protocol
1. 无连接
2. 基于TCP，可靠交换文件的重要基础
3. 熟知端口号：80
5. ① 怎样标识分布在Internet上的万维网文档？ ------URL
  
  ② 用什么协议实现万维网上各种超链的链接？------HTTP
  
  ③ 如何存储和表示万维网文档？------HTML
6. HTTP/1.0每传送一个文件都需要建立一次TCP连接；HTTP/1.1进行了改进；
网站地址：统一资源定位符 URL
1. 由以冒号隔开的两大部分组成，并且在 URL 中的字符对大写或小写没有要求
2. 缺省：
  1. 文件的<路径>项——缺省经常是index.html， default.html etc.
  2. 文件的<端口>项——采用协议默认端口时一般可以省略
4. Cookie 是网站服务器为用户产生一个唯一的识别码
HTTP报文类型：
1. 请求报文
2. 响应报文
3. HTTP是面向正文的(text-oriented)，报文中的字段都是
  ASCII 码串，因而每个字段的长度都是不确定的
安全的HTTP协议：HTTPS
1. 建立在SSL基础上
2. 熟知端口号为443
3. 加密的数据传输

文件传输协议FTP(File Transfer protocol)

FTP 提供交互式的访问，允许客户指明文件的类型与格式，并允许文件具有存取权限
FTP 屏蔽了各计算机系统的细节，因而适合于在异构网络中任意计算机之间传送文件
端口号：
1. control：21；
2. data：20
面向连接：FTP客户与服务器传递FTP命令时，使用的是建立在TCP之上的控制连接

电子邮件

发邮件
1. SMTP()
  1. ① 连接建立：连接在发送主机的SMTP客户和接收主机的SMTP
    服务器之间建立，不使用中间邮件服务器
    
    ② 邮件传送
    
    ③ 连接释放：邮件发送完毕后，SMTP释放TCP 连接
  2. SMTP支持在邮件服务器间、用户代理及邮件服务器间发送邮件(双向均可)
收邮件
1. POP3——Post Office Protocol：收方邮件服务器到收方主机(单向)
2. IMAP——Internet Message Access Protocol：功能更强大、丰富

域名服务

提供域名到IP地址转换的服务叫域名服务
域名：…… . <三级域名>.<二级域名>.<顶级域名>——需要转换为IP地址才可以访问
域名服务器程序在专设的结点上运行，运行该程序的机器称为域名服务器
互联网采用了层次树状结构的命名方法
权限域名服务器：
根域名服务器：不管是哪一个本地域名服务器，若要对互联网上任何一个域名进行解析，只要自己无法解析，就首先求助于根域名服务器
1. 根域名服务器并不直接把域名直接转换成 IP 地址。
2. 在使用迭代查询时，根域名服务器把下一步应当找的顶级域名服务器的 IP 地址告诉本地域名服务器。
顶级域名服务器
1. 负责管理在该顶级域名服务器注册的所有二级域名
2. 当收到 DNS 查询请求时，就给出相应的回答（可能是最后的结果，也可能是下一步应当找的域名服务器的IP地址）
权限域名服务器
1. 保存该区中所有主机的域名到IP地址的映射
2. 当一个权限域名服务器还不能给出最后的查询回答时，就会告诉发出查询请求的DNS客户，下一步应当找哪一个权限域名服务器
本地域名服务器
1. 当一个主机发出DNS查询请求时，这个查询请求报文就发送给本地域名服务器
主机向本地域名服务器的查询一般都是采用递归查询
本地域名服务器向根域名服务器的查询通常是采用迭代查询
每个域名服务器都维护一个高速缓存，存放最近用过的名字以及从何处获得名字映射信息的记录
1. 可大大减轻根域名服务器的负荷
2. 为保持高速缓存中的内容正确，域名服务器应为每项内容设置计时器，并处理超过合理时间的项
3. 当权限域名服务器回答一个查询请求时，在响应中都指明绑定有效存在的时间值。增加此时间值可减少网络开销，而减少此时间值可提高域名转换的准确性

简单网络管理协议SNMP

网络管理包括对硬件、软件和人力的使用、综合与协调，以便对网络资源进行监视、测试、配置、分析、评价和控制，这样就能以合理的价格满足网络的一些需求，如实时运行性能，服务质量等。
网络管理并不是指对网络进行行政上的管理

如果本地域名服务器无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为一条、一条

在“HTTP协议缺省使用端口80”这句话中，端口80为Web服务器的传输层端口号

HTTP协议的英文全称是Hypertext Transfer Protocol

TCP/IP协议向应用层提供的编程接口是Socket

域名解析DNS使用的传输层协议是UDP，如果一个C语言编写的应用程序基于该传输层协议实现网络通信，则该程序可调用套接字(Socket)编程接口函数sendto向外发送数据

建立TCP连接后，报文段中搭载的HTTP协议报文头部中用于获取文件的命令是GET

运行在不同主机间的两个应用进程AP1和AP2之间能建立多个TCP连接

传输层

传输层协议概述

传输层又叫运输层
向应用层提供服务
功能：连接管理、流量控制、差错控制、拥塞控制、建立无连接和面向连接的通信等
通信逻辑：进程(??用进程标识符来标志)间通信，端到端；可以复用和分用；可靠/不可靠通信服务
网络环境中一个完整的进程通信标识需要一个五元组来表示：

协议本地地址本地端口号
远程地址远程端口号
主要协议
1. UDP协议：无连接，用户数据报协议
2. TCP协议：面向连接，传输控制协议
  
  UDP和TCP都使用IP协议，即他们的协议数据单元都作为IP数据报的数据
是自下而上第一个提供端到端服务的层次
端口：为了使运行不同操作系统的计算机的应用进程能够互相通信，就必须用统一的方法对TCP/IP体系的应用进程进行标志
常用端口号

端口号协议主要功能
20 FTP(数据)
21 FTP(control)
23 TELNET
25 SMTP
53 DNS
69 TFTP
80 HTTP
161 SNMP(agent)
162 SNMP(management)
179 BGP
5060 SIP over TCP or UDP
5061 SIP using TLS over TCP ; SIPS over TCP

用户数据报协议UDP

不可靠、无连接；效率更高，但可能会出现丢包、乱序、数据错等问题
基于UDP的典型协议：RIP、DNS
面向报文，没有拥塞控制功能，但首部开销小(8个字节)
数据报格式

首部数据报
首部格式(不包含伪首部——4个字段、8个字节)

–伪首部– 源端口目的端口长度校验和
12字节：仅在计算校验和时使用，不实际传输 2字节 2字节 2字节：UDP数据报的长度 2字节：整个UDP数据报的校验和
伪首部格式

源IP地址目的IP地址 0 17 UDP长度
UDP的协议类型

传输控制协议TCP

可靠、有连接；处理开销较大，传送数据前要先建立连接；建立的连接只能有两个端点，每一条TCP连接只能是点对点的。
提供全双工通信
基于TCP的典型协议：HTTP、FTP
TCP把整个报文看成是一个个字节组成的数据流，每一个字节对应于一个序号
TCP每个报文段首部中的序号字段值表示该报文段数据部分的第一个字节的序号
TCP确认是对接收到数据最高序号表示确认。即表示期望下次收到的数据中第一个数据字节的序号

TCP报文段的首部格式

校验和：整个IP报文的校验和

TCP可靠传输的实现

复位RST	当该字段为1时，表明TCP连接出现严重差错，需释放连接后重新建立连接
同步SYN	该字段为1时，表示这是一个连接请求或连接接收报文
终止FIN	该字段为1时，表示要求释放TCP连接
窗口大小	2字节，用来让对方设置发送窗口的依据，单位为字节

超时重传时间的选择

TCP的可靠传输通过校验和+超时重传实现

TCP每发送一个报文段，就对这个报文段设置一个计时器
如果计时器设置的重传时间到，但还没有收到确认，就要重传该报文段
1. 加权平均往返时间 $RTT_s$ ( $R T T$ ：往返时间)
  
  $newRTT_s=(1-\alpha)*oldRTT_s+\alpha*newRTT_{sample}$
  
  其中 $\alpha$ 越小， $R T T$ 值更新得越慢
2. 超时重传时间 $R T O$
  
  $RTO=RTT_s+4\times RTT_D$
  
  其中 $RTT_D$ 是 $R T T$ 的加权平均值
  
  RFC2988建议这样计算 $RTT_D$
  1. 第一次测量时， $RTT_D$ 值取为测量到的 $R T T$ 样本值的一半
  2. 以后的测量中，使用下式计算加权平均的 $RTT_D$
    
    $newRTT_D=(1-\beta)\times oldRTT_D+\beta \times |RTT_s-newRTT_{sample}|$

TCP的流量控制

滑动窗口——实现可靠传输和流量控制

TCP基于滑动窗口协议实现可靠传输和流量控制，滑动窗口以字节为单位
acknowledge number：在此序号之前的数据已被正确接收
接收方根据ack与对方发来的窗口大小确定发送窗口的大小
TCP报头中都携带有窗口大小字段，告知对方自己接收窗口的剩余大小(即可接收的字节数，注意不要忽略仍在传输中的数据)
发送方的发送窗口应不大于对方的接收窗口
如何避免相互等待？

持续计数器——TCP为每一个连接设有一个持续计数器
如何保证传输效率(控制TCP报文的发送时机)：
1. 缓存数据达到一定量就发送
2. 应用进程控制
3. 定时发送

TCP的拥塞控制

拥塞概念：

在某段时间内，若对网络中某资源的需求超过了该资源所能提供的可用部分，网络性能就要变坏，从而产生拥塞

拥塞产生的条件 $\sum source-needed > source-available$

注意??：网络拥塞是多种原因引起的，通过简单地增加某种资源数量往往不能消除拥塞

拥塞常常会趋于恶化：TCP重传机制

e.g 一个路由器由于缓存不足丢弃了部分报文，发送端主机将超时重发，导致网络中被注入了更多的报文，从而加剧拥塞。

拥塞控制

防止过多的数据被注入到网络中，使网络中的路由器或链路不致过载。

是全局性的过程

流量控制

点对点通信量的控制——端到端的问题

RFC2581定义的4种拥塞控制方法

慢启动，又称为慢开始

开始发送时，如果立即把大量报文注入网络，则可能导致拥塞——不清楚网络的负荷状况——试探性地增加发送窗口

拥塞窗口 $c w n d$ ：
- 由发送方维持，是一个状态变量
- 取决于网络的拥塞程度，并在动态地变化
- 发送方让自己的发送窗口等于拥塞窗口，如再考虑到接收方的接受能力，则发送窗口还可能小于拥塞窗口
慢启动的工作过程
1. 开始发送报文段时，设置 $c w n d$ 为1，即设置为一个最大报文段 $M S S$ 的数值
2. 每收到一个对新的报文段的确认后，将拥塞窗口加一，即增加一个 $M S S$ 的数值
3. 传输轮次：使用慢启动时，每经过一个传输轮次，拥塞窗口 $c w n d$ 就加倍；一个传输轮次所经历的时间其实就是往返时间 $R T T$ ——把拥塞窗口 $c w n d$ 所允许的报文段都发送出去并收到了对已发送的最后一个字节的确认
4. 慢启动门限 $s s t h r e s h$ ——使用慢启动算法与拥塞避免算法的分界线
拥塞避免

思路：每经过一个往返时间 $R T T$ 就将发送方的拥塞窗口 $c w n d$ 加1，而不是加倍——拥塞窗口按线性规律缓慢增长——加法增大
- 拥塞发生时的处理：
  
  无论在慢启动阶段还是拥塞避免阶段，只要发送方判断网络出现拥塞，就要把慢启动门限 $s s t h r e s h$ 改为出现拥塞时的发送方窗口值的一半(但不能小于2)——乘法减小
  
  接着把拥塞窗口重新设置为1，执行慢启动法
快重传

思路：如果发送方在超时时间内未收到确认报文，说明网络中发生拥塞，此时发送方应尽早地减小窗口宽度
- 如果接收方收到一个失序的报文段，就发出重复确认，以便使发送方尽早知道有报文段没有到达接收方
- 发送方只要接收到三个重复确认就应当立即重传对方尚未收到的报文段
快恢复

思路：当发送方收到连续三个重复的确认时，就进行“乘法减小”，即将慢启动门限 $s s t h r e s h$ 减为当前的拥塞窗口宽度的一半
- 接下来不执行慢启动算法，而是设置为慢启动门限 $s s t h r e s h$ 减半后的数值，然后开始执行拥塞避免算法——“加法增大”
- 发送方认为当前网络可能没有发生拥塞(仅有拥塞征兆)
发送窗口的上限值—— $\min[rwnd,cwnd]$

TCP的连接管理

三个阶段——“C/S方式”

连接建立
数据传送
连接释放

连接建立——三次握手

客户机请求连接—— $S Y N = 1 ， A C K = 0$ ，选择 $s e q = x$ 表明传送数据时第一个数据字节的序号
服务器确认连接请求—— $S Y N = 1 ， A C K = 1$ ，确认号 $a c k = x + 1$ ，自己选择序号 $s e q = y$
客户机收到后，给出确认—— $S Y N = 0, A C K = 1$ ，确认号 $a c k = y + 1$

为什么是三次握手？

防止“失效的连接请求”占用服务器端资源

三次握手带来的安全问题及解决办法？

TCP-SYN flooding——不停发出连接请求，但不对SYN、ACK报文做出响应，占用服务器内部数据缓存

连接释放——可由任意方发起

A主动关闭连接—— $F I N = 1, s e q = u$
B接收后发出确认—— $A C K = 1, a c k = u + 1, s e q = v$
A—>B方向的连接被释放，连接半关闭，但B若发送数据，A仍要接收
B发送完毕—— $F I N = 1, A C K = 1, s e q = w, a c k = u + 1$
A接收后发出确认—— $A C K = 1, a c k = w + 1, s e q = u + 1$

关于MSL：Maximum Segment Lifetime——报文段最大存活时间
关闭连接前等待2MSL时间

主机甲向主机乙发送一个（SYN=1，seq=11220）的TCP段，期望与主机乙建立TCP连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确TCP段可能是中SYN=1，ACK=1，ack=11221，seq=任意值

一个TCP连接总是以1KB的最大段发送 TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT（往返时间）时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是9KB

Internet中某主机A上的浏览器使用HTTP协议从Web服务器B下载一个长度为10MB的文件。题图以表格形式给出了A与B之间从通信开始后传输的TCP报文段信息，表格中每一行对应一个报文段，报文段按传输时间先后顺序编号为 $S_1-S_{14}$ ，数据长度栏目表示报文段所搭载的应用数据长度。表格中的数值均为10进制，标注为’X’的表示该字段值未知，已知A、B间建立TCP连接的过程中通过选项字段协商确定最大报文段长度MSS=1000字节，双方均按照慢启动(开始)和拥塞避免机制进行传输，慢启动门限 $s s t h r e s h = 4$ ，单位：MSS，传输过程中没有报文段超时

编号传输方向序号确认号 ACK SYN 窗口
$S_1$ $A\rightarrow B$ 0 0 X X 6500
$S_2$ $B\rightarrow A$ 0 1 X X 16384
$S_3$ $A\rightarrow B$ 1 1 X X 6500
$S_4$ $A\rightarrow B$ 1 1 1 0 6500
$S_5$ $B\rightarrow A$ 1 382 1 0 16384
$S_6$ $A\rightarrow B$ 382 1001 1 0 5500
$S_7$ $B\rightarrow A$ 1001 382 1 0 16384
$S_8$ $B\rightarrow A$ 2001 382 1 0 16384
$S_9$ $A\rightarrow B$ 382 3001 1 0 3500
$S_{10}$ $B\rightarrow A$ 3001 382 1 0 16384
$S_{11}$ $B\rightarrow A$ 4001 382 1 0 16384
$S_{12}$ $B\rightarrow A$ 5001 382 1 0 16384
$S_{13}$ $B\rightarrow A$ 6001 382 1 0 16384
$S_{14}$ $A\rightarrow B$ 382 X 1 0 6000

已知报文段 $S_1,S_2,S_3$ 是A、B间建立TCP连接的报文段，请分别给出这三个报文段中SYN和ACK两个字段的值
报文段 $S_4$ 中搭载的HTTP协议报文头部中的方法或命令是什么？
请给出报文段 $S_8$ 和 $S_{13}$ 中搭载的数据长度和报文段 $S_{14}$ 中搭载的确认号字段
假设B在收到 $S_{14}$ 后，直到收到A的下一个确认之前，最多可向A发送n个字节的应用数据。如果B在报文段 $S_{14}$ 之后仍然采用慢启动机制，n的值是多少？如果B在报文段 $S_{14}$ 之后改用拥塞避免机制，n的值是多少？

解析：

序号 SYN ACK
$S_1$ 1 0
$S_2$ 1 1
$S_3$ 0 1
原因：SYN字段值表示正在请求建立连接/同意建立连接请求，ACK字段在连接建立后直到连接断开之前恒为1

$S_4$ 开始向Web服务器请求发送文件，方法：GET

根据确认号推知， $S_8$ 搭载的数据长度为1000字节，在 $S_{13}$ 所处的发送轮次中，由于A给出了接收窗口的最大值为3500字节，故而B在未收到A的确认信息之前，最多能向A传送3500字节—— $S_{13}$ 搭载的数据长度为500，传输过程中没有报文段超时，因此A在 $S_{14}$ 给出的确认号为A接下来可以接受的最小序号值，即6001+500=6501

分析：

最初B的发送窗口值为1(慢启动机制)，第一轮次结束后(收到 $S_6$ 确认报文) $c w n d$ 加倍，此时的 $r w n d$ 为5.5，发送窗口值为min[ $c w n d, r w n d$ ]为2，接着开始第二轮传输，第二轮次结束后(收到 $S_9$ 确认报文) $c w n d$ 加倍，为4，但此时的 $r w n d$ 为3.5，发送窗口值为min[ $c w n d, r w n d$ ]为3.5
注意，这里只是改变了发送窗口搭载的最大数据长度，并没有改变 $c w n d = 4 = s s t h r e s h$
接下来接收到的确认报文 $r w n d = 6$
若继续使用慢启动机制，则 $c w n d = 2 ? 4 = 8$ ，能发送的最大数据长度为 $M S S ? m i n [c w n d, r w n d] = 6000$ ；
若改用拥塞避免机制，则 $c w n d = 4 + 1 = 5$ ，能发送的最大数据长度为 $M S S ? m i n [c w n d, r w n d] = 5000$

网络层

网络层模型

网络层是通信子网的最高层，对上层用户屏蔽了子网通信的细节，如子网类型、拓扑结构、子网数目，对上层提供一致的服务、统一的地址
- 实现端到端的网络连接，屏蔽不同子网技术的差异，向上层提供一致的服务
- 主要功能：
  1. 路由选择和转发
  2. 分组交换
  3. 屏蔽子网的差异，实现统一的网络编地址
- 主要采用无连接方式、分组交换方式(IP传输方式)
网络层提供的两种服务
- 电信虚电路：面向连接的服务——通信双方之间的所有分组传输都是通过同一条虚电路传送
- Internet数据报：无连接的服务——通信双方的多次通信可以沿着相同/不同的路径传输
- TCP/IP采用数据报服务

网际协议IP

网际协议IP是TCP/IP体系中两个最主要的协议之一
- 与IP协议配套使用的四个协议
  1. 地址解析协议ARP
  2. 逆地址解析协议RARP
  3. 网际控制报文协议ICMP
  4. 网际组管理报文协议IGMP
分类的IP地址
- IP地址：由ICNN分配给主机或路由器的标识符——IPv4为32位IP地址
- 编址方法：
  1. 分类的IP地址
  2. 子网划分
  3. 构成超网
- $IP\ address::=={<net-id>,<host-id>}$
- IP地址的表示方法：点分十进制记法
- 全0、全1的IP地址有特殊含义
  - 全0表示本网络或本主机
  - 全1表示广播地址
- IP地址与硬件地址
  - IP地址：网络层及以上各层使用的地址，是一种逻辑地址，存放在IP包头部
  - 物理地址：数据链路层以及物理层使用的地址，存放在数据链路层的帧中(帧中也有IP地址，不过在帧的数据部)
  - [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mzb83Num-1637284592611)(/Users/cleopatra/Library/Application Support/typora-user-images/image-20211109194442371.png)]
ARP与RARP协议
- ARP将IP地址转化为物理地址——解决同一局域网中的主机或路由器的IP地址和硬件地址的映射
  - 主机设有一个ARP高速缓存，存有本地局域网上各主机和路由器的IP地址与硬件地址映射表
  - 当主机欲向本局域网内上的主机发送IP包时，
    
    先查看高速缓存===>如有，则查出其对应的硬件地址，再将此硬件地址写入MAC帧===>如无，则发送ARP请求：
  1. 主机A广播发送ARP请求分组
  2. 目标主机收到ARP请求帧后以单播形式发送ARP响应分组
  - 如果目标主机不在本局域网内，IP包需经由路由器转发
    
    —此时在局域网内要完成的是路由器IP与物理地址的映射
- RARP协议将物理地址转换为IP地址

IP数据报格式

组成：头部+数据

头部：20字节的固定字段+0到多个可选字段
重要字段：
- Version：4bit，版本
- IHL：4bit，IP包头长度，单位为word(32bit)
- Type of service：1 byte，服务类型
- Total length：2 bytes，IP包总长度，单位为字节——IP包的最大长度为65535字节
- Identification：2 bytes，标识
- DF：1bit，Don’t Fragment
- MF：1bit，More Fragment
- Fragment offset：13 bit，片偏移，以8字节为单位
Time to Live (TTL)：1byte，生存时间，IP包在网络中可通过路由器个数的最大值——Hop(每经过一个路由器俗称为1跳)

划分子网和构造超网

划分子网
- 分类IP地址的缺点：
  - IP地址空间的利用率有时很低
  - 给每一个物理网络分配一个网络号会使路由遍变得太大而使网络性能变坏
  - 两级的IP地址不够灵活
——增加子网字段，形成三级ip地址：从主机号借用若干位作为子网号

$IP \ address ::={<net-id>,<subnet-id>,<host-id>}$
- 子网掩码对目的IP地址和子网掩码执行“按位与”操作，即得到子网(网络)地址
- 子网掩码是一个网络或一个子网的重要属性
构造超网
- 无分类编址CIDR
  - 消除传统分类IP地址以及划分子网的概念
  - 使用各种长度的网络前缀来代替分类地址中的网络号和子网号
  - IP地址从三级编址又回到了两级编址
  - $IP \ address::={<prefix>,<host-id>}$
  - 斜线记法，又称为CIDR记法——IP地址后加一个斜线“/”后面跟网络前缀所占的位数
  - 网络前缀都相同的连续IP地址组成“CIDR地址块”
  - CIDR带来的好处
    1. 路由聚合==构成超网
    2. 减少路由表项
  - 最长前缀匹配——网络前缀越长，其地址块就越小，因而路由就越具体(more specific)
- 在计算子网内能分配的最大地址个数时，要注意主机号全0与全1的特殊性

网际控制报文协议ICMP

Internet Control Message Protocol
报文共有9种，分为差错报告报文和询问报文两类
- 差错报文
  - Destination unreachable(终点不可达)——packet cannot be delivered路由器或主机无法传输报文时
  - Time exceeded(超时)——TTL hits 0
  - Parameter problem——Invalid header field
  - Source quench(源点抑制)——Choke packet路由器或主机由于拥塞丢弃报文时，向源主机发送此报文
  - Redirect(重定向)——teach a router about geography路由改变
- 询问报文
  - Echo request——Ask a machine if it is alive
  - Echo reply——Yes,I’m alive
  - Timestamp request——Same as Echo request,but with timestamp
  - Timestamp request——Same as Echo reply,but with timestamp
应用举例
- Ping——用于测试主机之间的连通性
  - ICMP Echo request/reply
- Traceroute/Trancert——用于测试到另一台主机所经过的路由信息
  - ICMP 超时报告报文——TTL字段分别设置为1，2，3，…，直到到达目的主机(UDP报文)

路由算法及协议

路由算法用于生成路由信息(路由表)
静态路由与动态路由
- 静态路由选择策略：非自适应路由选择；简单、开销小，不能及时适应网络状态的变化；适用于小规模变化较少的网络，由人工设置路由。
- 动态路由选择策略：自适应路由选择；能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大；适用于较大规模，频繁变化的网络，通过专门的算法和协议进行路由计算。
自制系统AS(Autonomous Systom):在单一的技术管理下的一组路由器，而这些路由器使用一种AS内部的路由选择协议和共同的度量以确定分组在该AS内的路由，同时还使用一种AS之间的路由选择协议用以确定分组在AS之间的路由
- 外部网关协议：自制系统之间的路由选择——EGP
  - e.g BGP
    1. BGP难以找到最佳路由，只能寻找一条能够到达目的网络且比较好的路由(不能兜圈子)
    2. BGP发言人：
      1. 两个BGP发言人通过一个共享网络连接在一起
      2. 一般是AS的边界路由器，也可以不是
      3. BGP发言人与其他AS中的BGP发言人交换路由信息
      4. 路由信息的交换通过TCP协议进行，两个发言人在TCP连接上交换BGP报文以建立BGP会话
      5. 发言人除了运行BGP协议外，还要运行AS内部网关路由协议
    3. BGP-4使用的四种报文：
      1. OPEN报文：建立关系
      2. UPDATE报文：发送某一路由信息；列出要撤销的多条路由
      3. KEEPALIVE报文：周期性证实邻站关系
      4. NOTIFICATION报文：用于发送检测到的差错
- 内部网关协议：自治系统内部的路由选择——IGP
  - e.g RIP；OSPF
典型的动态路由算法
- 距离向量路由算法
  - RIP协议：
    
    -每个路由器维护一张表，表中给出了到每个目的地的已知最佳距离和线路，并通过与相邻路由器交换距离信息来更新表
    
    -路由器周期性地向所有相邻路由器发送他的距离表，同时他也接收每个邻居节点发来的距离表
    
    -根据不同的邻居发来的信息，计算到目标路由器的最小距离，更新本路由的路由表
  - 算法缺陷：对好消息反应迅速，对坏消息反应迟钝
    1. 网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器
    2. 支持的网络规模有限
    3. 路由器间交换的路由信息是路由器中的完整路由表，随网络规模的扩大，开销随之增大
  - 距离定义：路由器跳数 hop count
  - 最长距离——15跳，跳数为16表示不可达
  - 要点
    1. 仅和相邻路由器交换信息
    2. 交换的信息是当前路由器所知道的全部信息
    3. 按固定的时间间隔交换路由信息
- 链路状态路由算法——构造全网拓扑结构图
  - 基本思想
    1. 发现邻居结点，学习其网络地址
    2. 测量到各邻居结点的延迟或开销
    3. 构造一个分组，其中包含所有它刚刚知道的信息
    4. 将这个分组发送给其他所有路由器
    5. 计算出到每一个其他路由器的最短路径
  - OSPF协议
    
    -收敛速度快：链路状态发生变化时，结点会以洪泛方式告知网络中所有其他结点
    
    -适用于大规模网络：仅在链路状态发生变化时发送洪泛信息，不会产生很大通信量
    
    **OSPF直接用IP数据报传送
    
    OSPF的5种分组
    1. Hello分组
    2. Database Description分组
    3. Link State Request分组
    4. Link State Update分组：使用洪泛法对全网更新链路状态
    5. Link State Acknowledge分组

路由器

组成
1. 路由选择：按照路由选择协议工作，构建路由表
2. 分组转发：交换结构
功能
1. 运行路由协议，设置路由表
2. 检测到拥塞时，合理丢弃IP分组
3. 根据收到的IP分组的目的IP地址，将其转发到合适的输出线路上

IP组播

又称为多播，用于实现一点对多点的数据传输
组播的典型应用实例：网络视频服务
主机通过IGMP协议与组播路由器通信，加入/退出某个组播组

虚拟专用网VPN和网络地址转换NAT

网络地址转换NAT
- 专用地址
  1. 10.0.0.0～10.255.255.255
  2. 172.16.0.0～172.31.255.255
  3. 192.168.0.0～192.168.255.255
- 当内部网络使用专用地址时，与Internet的通信需要通过NAT(Network Address Translation)
- NAT路由器内部使用TCP/UDP端口号实现外网数据包向内网地址的转换
虚拟专用网VPN——virtual private network
- 多个企业/机构内部网络之间互连的实现方法：
  - 租用专用线路
  - 基于公用网络
- VPN涉及的技术
  - 隧道
  - 加密
  - 身份认证
- 基于Internet建立VPN的两种情形
  - 内部网络通过Internet互连
  - 远程用户访问内部网
- 典型VPN实现技术
  - IPsec：ESP隧道模式
  - SSL：WEB浏览器内置SSL支持

某网络的IP地址空间为192.168.5.0/24，采用长子网划分，子网掩码为255.255.255.248，则该网络的最大子网个数为32，每个子网内的最大可分配地址个数为6

在子网192.168.4.0/30中，能接受目的地址为192.168.4.3的IP分组的最大主机数是2，ip地址分别是：192.168.4.1/30；192.168.4.2/30(CIDR记法)

若路由器R因为拥塞丢弃IP分组，则此时R可向发出该IP分组的源主机发送的ICMP报文的类型是源点抑制报文

某自治系统采用RIP协议，若该自治系统内的路由器 $R_{1}$ 收到其邻居路由器 $R_{2}$ 的距离矢量中包含的信息 $< n e t 1, 16 >$ ，则可能得出的结论是 $R_{1}$ 不能经过 $R_{2}$ 到达 $n e t 1$

数据链路层

概述

物理层实现了比特流的传输，数据链路层在其基础上实现帧的传输——数据链路层传输的协议数据单元(PDU)是帧
数据链路层使用的信道类型：
- 点对点信道
- 广播信道：必须采用专门的共享信道协议来协调数据发送
数据链路层涉及的问题
1. 成帧：帧边界的可识别性
  - 字符计数法
  - 字符填充的首尾定界法
  - 比特填充的首尾定界法
  - 物理编码违例法
2. 差错控制
  - 错误检测和纠正
  - 检错编码： $误码率=\frac{出错的比特数}{传送的总比特数}$
  - 处理方法
    1. 使用可检测并纠正错误的编码：纠错码
    2. 使用可检测错误的编码+重传：检错码
  - 检错编码：奇偶校验、简单累加和、循环冗余校验CRC
  - 纠错编码：海明码
  通过检错码/纠错码可以做到帧的无差错接收，但并不意味着可靠传输，其他的错误包括帧丢失、帧重复、帧先序
3. 流量控制及可靠传输
4. 广播信道中的介质访问控制
基本数据链路协议
- 无限制的单工协议
  1. 单向传输
  2. 理想信道
  3. 发送方总有数据发送
  4. 接收方总能及时处理所收到的数据
- 单工停-等协议(比无限制的单工协议增加了流量控制机制)
  1. 接收方每收到一帧，都向发送方返回一个应答帧
  2. 发送方每发送一帧，都等待来自接收方的应答帧，之后才发送下一帧
- 有噪声信道的单工协议
  1. 解决方案——ARQ协议
    - 校验和：检测帧是否出错
    - 确认帧
    - 超时重发
    - 帧序号：保证接收方不会重复接收帧
  2. 考虑的情形
    - 帧被正确接收
    - 数据帧出错或丢失
    - 确认帧出错或丢失
- 滑动窗口协议
  - 允许发送方连续发送多个帧
  - 通过滑动窗口实现流量控制
  - 发送方：发送窗口内的序号代表允许它发送的帧
  - 接收方：接收窗口内的序号代表它可以接收的帧
  连续发送的多个帧中，某一个帧出错或丢失，但后续帧已被正确接收，如何处理？——数据链路层需按顺序向网络层上交帧
  - 后退N帧的滑动窗口协议
    1. 某帧出错，则该帧之后的帧全部丢弃，从出错帧开始重新发送
  - 选择性重传的滑动窗口协议
    1. 某帧出错，选择性地重发该帧，该帧之后发送的帧由接收方数据链路层缓冲，收到重发的帧后上交网络层
  - 注意??： $ACK_n表示n及n以前的帧均已被正确接收$
点对点协议PPP
- 应用：拨号上网、光纤传输
- 组成
  1. 将IP数据报封装到串行链路的方法
  2. 链路控制协议LCP(Link Control Protocol)
  3. 网络控制协议NCP(Network Control protocol)
- 帧格式：面向字节，所有PPP帧的长度都是整数字节
- 透明传输问题
  - 同步传输
    - 零比特填充：发送端只要发现5个连续1，则立即填入一个0；接收端对帧中的比特流进行扫描，每当发现5个连续1时就把这5个连续1后面的1个0删除
  - 异步传输：字符填充
- 身份认证协议
  - PAP——Password
  - CHAP——Challenge-Handshake
介质访问控制
1. 静态划分信道
  - 频分复用
  - 时分复用
  - 波分复用
  - 码分复用
2. 动态介质访问控制(多点控制)
  - 随机访问：可能产生碰撞、冲突
    
    -典型协议：ALOHA、CSMA、CSMA/CD、CSMA/CA
  - 受控访问：
    
    -多点线路探询(polling)、轮询(局域网中使用较少)
3. 以太网的核心——CSMA/CD
  - 载波监听多点访问/碰撞检测
  - 随机访问协议
  核心概念：
  1. 载波监听
    
    结点在发送之前先检测总线上是否有其他结点正在发送数据
  2. 碰撞检测
    
    结点边发送数据边检测信道上是否发生了碰撞
    
    由于线路的传播时延，单纯的载波监听并不难完全避免碰撞
    
    发生碰撞时，两个或更多的信号在总线上相互叠加，导致无法识别
  3. 碰撞强化
    
    发送方检测到碰撞后，立即停止发送，并发送32或48bit的人为干扰信号，以便让所有用户知道发生了碰撞
  4. 碰撞退避
    - 碰撞后，结点等待一段时间，重新开始载波检测和发送操作
    - 为避免退避后再次碰撞，冲突各方的等待时间应各不相同
    - 以太网采用截断二进制指数退避算法
      1. 退避时间： $T=2\tau\times倍数$
      2. 倍数：在0，1，……， $2^{k}-1$ 中取随机数， $k=min\{重传次数，10\}$
      3. 重传次数超过16后，丢弃该帧，并向上层报告
  5. 争用期：
    - 一个站点开始发送数据后，最多经过 $2\tau$ 就可知道是否发生了碰撞
    - 以太网的端到端往返时延 $2\tau$ 称为争用期，或碰撞窗口
    - 如果经过争用期还没有检测到碰撞，就可以肯定这次发送不会发生碰撞
  优缺点讨论
  - 网络负载较轻时效率高
  - 硬软件实现简单、灵活
  - 网络负载较重时，碰撞发生概率增大，网络效率较低
  - 由于存在多次冲突的可能，数据从发送方到达接收方的时间没有保证——无法在发送时确定数据传输时间
4. 局域网技术标准
  - IEEE802标准将局域网的数据链路层分为两个子层
    1. LLC(Logic Link Control)逻辑链路控制子层
    2. MAC(Media Access Control)介质访问控制子层
  - IEEE802.2:逻辑链路控制子层LLC
  - IEEE802.3:CSMA/CD介质访问控制与物理层技术规范
  - IEEE802.11:无线局域网介质访问控制与物理层技术规范
5. 以太网的MAC层
  - 以太网采用CSMA/CD介质访问控制协议
    1. 结点发送数据时，以太网总线结构，总线上的所有结点都能收到帧
    2. 按照IEEE803.2标准，给每个站点分配唯一的MAC地址
    3. MAC地址为48bit，高24bit为厂商识别符，低24位由厂商自行分配，需保证每个网络接口具有全球唯一的MAC地址
  - 适配器每收到一个帧就检查帧中的目的MAC地址，如果是发往本站的帧则进行处理，否则丢弃
    1. 单播
    2. 组播/多播
    3. 广播
  - 以太网的帧格式
  - 以太网采用曼彻斯特编码，每个比特均有电平跳变，无电平跳变则意味着总线空闲
  - 高速以太网若工作在全双工模式下则不使用CSMA/CD协议——不存在争用
  - 特殊字符表示
    
    10BASE- T 10：10Mbps，BASE：基带传输，T：双绞线
    
    100BASE- TX 2对UTP5类线或屏蔽双绞线
    FX 一对光纤
    T4 4对UTP三类线或五类线
    1000BASE- X 基于光纤
    SX 短波长
    LX 长波长
    CX 铜线
    T 4对五类双绞线UTP
    万兆以太网 – 只使用光纤

局域网互连

在物理层扩展局域网

使用中继器或集线器可以实现局域网在物理层的互联
集线器与中继器都不分割碰撞域
- 优点：实现网络扩展较方便，成本低
- 缺点碰撞域增大，碰撞发生概率增大，可能影响网络性能

在数据链路层扩展局域网

使用网桥可以实现局域网在数据链路层的互联——网桥工作在数据链路层
- 基本工作原理
  - 根据MAC帧的目的地址对收到的帧进行转发
  - 具有过滤帧的功能，当收到一个帧时，确定该帧的目的MAC地址，确定将该帧转发到哪个接口——并不向所有接口转发帧
- 网桥的优点
  - 过滤通信量，增加吞吐量——各网段是独立的碰撞域
  - 扩大了物理范围
  - 提高了可靠性
  - 可互联不同物理层、不同MAC子层和不同速率的局域网（这可是桥诶！不同物理层怎么了，物理层的质对于网桥是透明的，不在桥的考虑范围内）
- 网桥的局限性
  - 存储转发增加了时延
  - 在MAC子层并没有流量控制功能
  - 只适合用户数不太多(不超过几百个)和通信量不大的局域网
    - 广播风暴：某些站点频繁发送广播帧产生网络拥塞
改进网桥？——多接口网桥，交换机
- 交换机工作在数据链路层，每个接口为一个网段(碰撞域)，可以大幅提高网络性能
- 集线器由所有接口共享传输介质的带宽，而交换机为每个接口独享带宽
- 交换机按照自学习算法建立转发表——根据接收到帧的源MAC地址以及收到帧的接口建立转发表
- 透明网桥还使用生成树算法：避免帧无休止转发
虚拟局域网VLAN
- 在现有局域网基础上，通过将网络站点分组，构成若干逻辑上独立的虚拟局域网
- 用途
  - 便于管理
  - 控制广播风暴
  - 安全性
- 帧不会在两个VLAN之间自动转发，包括广播帧
- IEEE802.1Q在以太网帧中扩展VLAN标记(tag)，供交换机识别和转发

数据链路层采用后退N帧(GBN)协议，发送方已经发送了编号0-1的帧，当计时器超时时，若发送方只收到0，2，3号帧的确认，则发送方需要重发的帧数是4： $ACK_{n}$ 代表n号帧及n号帧之前的帧都已被正确接收

某局域网采用CSMA/CD协议实现介质访问控制，数据传输率为 $100 M b / s$ ，主机甲与主机乙的距离为 $2 k m$ ，信号传播速度是 $200000 k m / s$ 请回答以下问题，并给出计算过程：

(1) 若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻为止，最短经过多长时间？最长经过多长时间？(假设主机甲和主机已发送数据时，其它主机不发送数据)

解析：

甲乙间单向传输时延 $\tau=2/200000=10\mu s$

最短：同时发送，中点处发生冲突，继而开始传送冲突信号——10 $\mu s$

最长：甲发送的帧已经走过整段距离后，乙开始发送数据，此时冲突信号需传输整段到甲—— $2*10\mu s$

在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传播速率为 $1 G b p s$ ，电缆中的信号传播速度是 $200000 k m / s$ 。若最小数据帧长度减少 $800 b i t$ ，则最远的两个站点之间的距离至少需要

传输时延>2 $\tau$ ,保证了在远端站点发送完数据之前能够检测到冲突
传输时延=数据包的大小/数据包的发送速率
传播时延= $\tau=L/v$

设 $C S M A / C D$ 局域网的数据传输速率为 $1 G p s$ ,信号传播速度为 $200000 k m / s$ ，最小帧长度为 $25000 b i t$ ，则该局域网中两站之间的最远距离为？

操作系统

PV操作

同步与互斥问题

进程同步
- 间接相互制约——资源共享
- 直接相互制约——进程合作
- 进程同步：指多个相关进程在执行次序上的协调，用于保证这种关系的相应机制称为同步机制
互斥：在同一个时刻，只允许一个进程访问临界资源
临界资源：一次只允许一个进程使用的资源。
1. e.g 打印机、共享变量
2. 假脱机打印(spooling)——把独占的临界资源共享访问
临界区：对临界资源进行访问的程序片段
同步机制应遵循的准则：
1. 空闲让进
2. 忙则等待
3. 有限等待
4. 让权等待

基于忙等待的互斥方法

信号量机制(Semaphore)——安全地避免忙等
1. $0\leq S$ 表示当前可用的资源数目
  1. $S = 1$ 实现互斥：二元信号量
  2. $S > 2$ 实现同步：通用信号量
2. $P (), S ()$ 操作原语：原子操作不会被打断var $S : S a m e p h o r e$
  1. $P ()$ 操作分配资源： $S = S ? 1$ 若 $S < 0$ 则置进程为阻塞状态，并将该进程加入阻塞队列；否则继续执行。
  2. $V ()$ 操作释放资源： $S = S + 1$ ，若 $S\leq0$ 则从阻塞队列；
3. P、V操作的定义：
```
procedure p(var s:samephore);
　　{
　　s.value=s.value-1;
　　if (s.value<0) asleep(s.queue);
　　}
　　
procedure v(var s:samephore);
　　{
　　s.value=s.value+1;
　　if (s.value<=0) wakeup(s.queue);
　　}
```
4. 信号量的使用
  1. 必须置一次且只能置一次初值——资源个数
  2. 只能通过 $P, V$ 操作改变

基于信号量的方法

互斥量(Mutex)：信号量值设置为1就是互斥量——用于实现对共享资源和代码的互斥访问；
1. 0——解锁状态
2. 1——加锁状态

基于管程的同步与互斥

管程(Monitor)
1. 管程是一种高级同步原语
2. 一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能够同步进程和改变管程中的数据
管程的实现：
1. 同步机制使用：
  1. wait
  2. signal

经典同步与互斥问题#待补充

生产者消费者问题

/*设有一个可以装A、B两种物品的仓库,其容量无限大,但
要求仓库中A、B两种物品的数量满足下述不等式:
? -M≤A物品数量-B物品数量≤N 
? 其中M和N为正整数. 
§ 试用信号量和PV操作描述A、B两种物品的入库过程.*/

/*分析：A入库——必然导致B最大值增加，但A能够入库的要求为当前库中A数量小于(B数量+N)；B入库同理*/

Semaphore mutex = 1,sa = N,sb = M;
procedure A：
  while(1)
    begin
    P(sa)
		P(mutex)
		A get stored
    V(mutex)
		V(sb)
procedure B：
  while(1)
    begin
    P(sb)
		P(mutex)
    B get stored
    V(mutex)
    V(sa)

/*三个进程P1、P2、P3 互斥使用一个包含N（N>0）个单元的缓冲区。P1 每次用produce()生成一个正整数并用put()送入缓冲区某一个空单元中；P2 每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3 每次用 geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。*/

Semaphore mutex = 0,empty = N,odd = 0,even = 0
int number = 0
P1:
cobegin:
while(True)
number = produce()
P(empty)
P(mutex)
put()
v(mutex)
if(number%2==0):
	V(even)
else:
	V(odd)

P2:
cobegin:
while(True)
P(odd)
P(mutex)
getodd()
countodd()
V(mutex)
V(empty)

P3:
cobegin:
while(True)
P(even)
P(mutex)
geteven()
counteven()
V(mutex)
V(empty)

读者-写者问题

//灯开关模式
int readers = 0
Semaphore mutex = 1
Semaphore roomEmpty = 1

writer:

P(roomEmpty);
write//critical region
V(roomEmpty);

reader:
P(mutex);
	readers=readers+1
	if readers == 1:
		P(roomEmpty)
V(mutex);

read//critical region

P(mutex);
	readers=readers-1;
	if readers == 0:
		V(roomEmpty);
V(mutex)

//闸机模式
int readers = 1
  Semaphore mutex = 1
  Semaphore roomEmpty = 1
  Semaphore turnstile = 1
  
writer:

P(turnstile);//writer在闸机前排队，等待roomEmpty
	P(roomEmpty);
	wirte//critical region
	V(turnsitile);
V(roomEmpty);

Reader:

P(turnstile);
V(turnstile);
P(mutex);
	readers = readers+1
	if readers==1:
		P(roomEmpty)
V(mutex);
	read//critical rigion
P(mutex);
	readers = readers-1
	if readers==0:
		V(roomEmpty);
V(mutex)

哲学家进餐问题
理发师问题

死锁

死锁发生的四个必要条件
1. 互斥条件
2. 保持和请求条件
3. 不剥夺条件
4. 环路等待条件
死锁发生的原因
1. 竞争资源
2. 并发执行的顺序不当
处理死锁的方法
1. 死锁预防：破坏死锁产生的四个条件之一
2. 死锁避免：在资源分配之前判断是否安全，仅当安全才进行分配——e.g 银行家算法
3. 死锁检测
4. 死锁解除
资源分配图——不可简化的资源分配图====>死锁(简化后还存在边)，其中的有边进程为死锁进程
安全状态：程序存在一个序列 $p_1,p_2,…,p_n>$ 能够顺利执行
银行家算法：
- 可利用资源向量Available
- 最大需求矩阵Max
- 分配矩阵Allocation
- 需求矩阵Need

I/O系统

I/O设备

按传输速度：高速、中速、低速
按信息交换单位：字符设备、块设备
按共享属性：独占设备、共享设备、虚拟设备

设备与控制器间接口

数据信号
控制信号
状态信号

I/O控制技术

程序控制I/O
1. I/O请求由程序发起，并等待操作完成
2. 数据的读写通过CPU
3. 在外设处理数据时，CPU只能等待
中断驱动方式
1. I/O操作由程序发起，在操作完成时由外设向CPU发出中断，并通知该程序
2. 数据的读写通过CPU
3. 虽然CPU可以在外设处理数据时继续执行当前程序或其他程序，但CPU传输效率低，只适用于数据传输率较低的设备
直接存储访问方式DMA
1. 由程序设置DMA控制器中的寄存器值后，发起I/O操作，由DMA控制器完成内存与外设的成批数据交换，在操作完成时由DMA控制器向CPU发起中断请求。
2. CPU只干预I/O操作的开始和结束，DMA是l/O设备与主存之间由硬件组成的直接数据通路
3. 适用于高速设备成批读取数据
I/O通道控制设备
1. 通道指令——
2. 由操作系统构造通道指令并存放在内存中
3. 执行一个通道程序可以完成N组I/O操作

缓冲技术

缓冲技术可以提高外设的利用率
1. 匹配CPU与不同外设的处理速度
2. 减少对CPU的中断次数
3. 提高CPU与外设间的并行性
缓冲池(buffer pool)
单缓冲(一个缓冲区)
1. 只传送以完整形式存在于缓冲区中的数据(填满后传)
2. 只向空缓冲区注入新的数据
3. CPU只处理以完整形式存在于缓冲区内的数据(传完后处理)
双缓冲
1. 两个缓冲区，CPU与外设都可以连续处理而无需等待对方
2. 要求CPU与外设速度相近

假脱机技术SPOOLing

把独享设备转变成具有共享特征的虚拟设备
提高设备利用率
在多道程序系统中，专门利用一道程序(SPOOLing程序)来完成对设备的I/O操作，无需使用外围I/O处理机

磁盘

组成：扇面、磁道(柱面)、扇区、磁头
磁盘与操作系统启动：
1. MBR(主引导扇区)
2. DPT分区表(DPT)
3. 分区引导扇区(DBR)
磁盘调度算法

常见算法
1. 先来先服务
2. 最短寻道时间
考虑磁道距离+磁头移动方向
1. 扫描算法
2. 循环扫描算法
- 先来先服务：按照给出的访问顺序直接访问
- 最短寻道时间：每次寻道均寻找从当前磁道移动至目标磁道所需移动道数最短的磁道
- 扫描(SCAN)算法：在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象，与电梯运行方式类似
  
  SCAN算法对最近扫描过的区域不公平，因此，它在访问局部性方面不如前两种好
- 循环扫描算法：循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描
提高I/O速度的主要途径
- 选择性能好的磁盘
- 并行化
- 采用适当的调度算法
- 设置磁盘高速缓冲区

廉价冗余磁盘阵列

利用冗余技术提高可靠性
利用并行提高性能

普通磁盘驱动器只能通过CRC(循环冗余校验)码提供简单的容错，RAID建立在每个磁盘驱动器的硬件容错功能之上，可提供更高的安全性

RIAD0	RAID1	RAID2
无冗余校验功能，并行交叉存取提高I/O速度	镜像磁盘冗余阵列，读性能好，对应镜像盘同时读取；写性能由写速度最慢的盘决定，故写性能不一定好；有效容量仅50%	采用海明码检错、纠错，数据位交叉写入磁盘，“按位条带化”
RAID3	RAID4	RAID5
采用奇偶校验冗余的磁盘阵列，数据位交叉写入磁盘。将磁盘分组，采用字节级别的条带，读写要访问组中所有盘，每组中有一个盘作为校验盘。	数据块交叉，用一个校验盘，将数据按块交叉存储在多个磁盘上；使用较少的盘参与操作，以使磁盘阵列可以并行进行多个数据的磁盘操作	数据块交叉和分布的冗余校验，将数据和校验都分布在各个磁盘中，没有专门的奇偶校验去东区。

最少磁盘数量：

RAID0 2
RAID1 2
0+1(组内条带化，组间镜像) 2
1+0(组内镜像，组间条带化) 2
2 7*
3 3
4 3
5 3
6 4
补充：

码距<=>海明距离，码距越大，纠错能力越强，但数据冗余也越大，编码效率低。

文件系统

文件系统的基本概念

文件系统模型的三个层次

文件系统接口
1. 命令行接口——用户和文件系统的交互接口
2. 程序接口——用户程序和文件系统的接口；用户程序可以通过系统调用的形式来取得文件系统的服务
对象操作管理的软件集合：
1. 对文件存储空间的管理
2. 对文件目录的管理
3. 用户将文件的逻辑地址转换为物理地址的机制
4. 对文件读和写的管理；
5. 对文件的共享和保护的功能
对象及其属性
- 文件系统管理的对象
  1. 文件——直接对象
  2. 目录——文件系统必须包括目录，每个目录项中必须包括文件名以及文件所在的物理地址(或指针)
  3. 磁盘存储空间——文件和目录必定占用存储空间

文件名

文件名.扩展名

文件类型

性质和用途：系统文件、库文件、用户文件
数据形式：源文件、目标文件、可执行文件
保护级别：只读文件、读写文件、执行文件、不保护文件
逻辑结构：有结构文件、无结构文件
物理结构：顺序文件、链接文件、索引文件

文件的逻辑结构

提高检索效率、便于修改、降低文件存储代价

流式结构——单位是字节
记录式文件结构——单位是记录
树形结构

文件物理结构

在存储介质上的存放方式，表示了一个文件在文件存储介质上的位置、链接和编目方法

连续结构——容易出现磁盘碎片，适合变化不大的文件；方便顺序存取和随机存取(有序)
索引结构
- 一个文件的信息存放在若干个不连续物理块中；
- 系统为每个文件建立一个专用数据结构——索引表；
- 索引表就是磁盘块地址数组，其中第i个条目指向文件的第i块
- 每个文件的索引表长度是不一样的，故不能存放在FCB中，FCB只记录索引表的地址
1. 索引文件：为每个文件建立逻辑块号与物理块号的对照表，称为文件的索引表；文件由数据文件和索引表构成。这种文件称为索引文件；
2. 索引文件的操作：
  1. 在存储区中，索引文件占两个区——索引区+数据区
  2. 访问索引文件：先读取文件索引区，由逻辑块号查得物理块号；再访问物理块号获得所需信息
  3. [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DyZHiBer-1637284592613)(/Users/cleopatra/Library/Application Support/typora-user-images/image-20211104154433234.png)]
  4. 本身带来了系统开销：内外存空间+存取时间
串联结构
- 按顺序由串联的块组成；即文件的信息按存储介质的物理特性存于若干块中
- 对于记录式文件，一块可以包含一个逻辑记录或多个逻辑记录，也可以若干物理块包含一个逻辑记录
空间利用率高，顺序存取效率高；

随机存取效率低，可靠性不强(指针出错)；链接指针占用一定空间

文件存取方式及存储介质

顺序存取、随机存取(提供读写位置)
存储介质：磁盘、磁带、光盘；
物理块(块block、簇cluster)：数据存储、传输和分配的单位，存储设备通常划分为大小相等的物理块，统一编号

文件系统的实现方法

由文件说明索引组成的用于文件检索的特殊文件
文件目录的主要内容：文件访问和控制信息(不包括文件内容)
文件属性信息，部分为用户可获取
基本信息：文件名；别名的数量
文件类型
地址信息(存放位置、文件长度)
访问控制信息：文件所有者、访问权限
使用信息：创建时间；最后一次读访问的时间+用户；最后一次写访问的时间+用户

目录分级

单级目录

二级目录

在根目录下，每个用户对应一个目录，在用户目录下是该用户的文件，而不再有下级目录。(适用于多用户系统)

多级目录

在较高的目录级，其目录表目为下一级目录名以及一个指向其目录的指针，在最后一级目录，这个指针指向文件的物理地址

特点：

层次清楚
可解决文件重名问题
查找速度快
目录级别太多会增加路径检索时间

目录的实现：

直接法：文件名+文件控制块
间接法：文件名+文件控制块的地址(索引号)

文件目录的查询：

顺序查询
Hash方法——“杂凑法”

便于共享的目录组织

文件的共享要求系统能提供一种方法：使存储空间内保存一份副本，而所有要共享该文件的用户可用相同的或不同的文件名来访问它
共享目录实例练习：

用户A有两个w文件 $F_{1},F_{2}，用户B有三个文件$ $F_{1},F_{3},F_{5}$ 其中用户A的文件 $F_{1}$ 与用户B的文件 $F_{1}$ 不是同一个文件，用户B的文件 $F_{3}$ 和用户A的文件 $F_{2}$ 是同一个文件。

请针对以上需求，给出一种目录组织方案。画图辅助说明。

【分析】：

$A----F_{1}$ 与 $B----F_{1}$ 不是同一个文件，故各处于各自的文件目录下，映射向不同的文件物理地址即可；

是同一个文件的不同目录下的文件需通过同一个索引节点映射向同一个文件，针对进一步需求——A删除文件，仅删除自己目录下的文件/同时删去所有与A删除的文件相同的文件设置的计数器情况不同；

全局同步：count=1，任何目录下操作删去文件则count-1，系统负责删去文件，各目录下文件对应项删去

异步删去：count=共享该文件的目录数，任何目录下删去该文件，count-1，仅删去该目录下该文件对应项以及映射关系即可；当count=0时，系统负责删去文件

文件控制块

基本信息：文件名；物理位置；文件逻辑结构；文件物理结构
访问控制信息：文件所有者、访问权限
使用信息：创建时间、上一次修改时间、当前使用信息

文件描述符

一般为一个非负整数，唯一标识一个打开的文件

文件系统实例分析

在采用索引的文件系统中，已知索引节点可设置为10个直接索引，1个一次间接索引，1个2次间接索引。文件块大小为s字节，文件块号为t字节。这个文件系统支持的最大文件是多大？

10个间接索引能索引10块数据

1个一次间接索引能够索引的数据块的数量为 $s / t$

一个二次间接索引能够索引的数据块数量为 $s/t)^{2}$

故，文件最大为 $10+s/t+(s+t)^{2})*s$

进程与线程

进程的概念

顺序执行

特征：顺序性、封闭性、可再现性
并发：设有两个活动a1和a2，如果在某一指定的时间t，无论a1和a2是在同一处理机上还是在不同的处理机上执行，只要a1和a2都处在各自的起点和终点之间的某一处，则称a1和a2是并发执行的——强调时间段

特征：
1. 间断性：执行——暂停——执行
2. 非封闭性：多个程序共享系统中的资源，程序间相互影响
3. 不可再现性：在初始条件相同的情况下，程序的额执行结果依赖于执行的次序
  
  并发程序的无关性是进程与时间无关的一个充分条件——Bernstein条件：
  
  可并发当且仅当：
  1. 进制间读集与写集交集为空集
  2. 写集间交集为空集
并行：强调时间点——两个程序，在同一时间度量下同时运行在不同的处理机上，则称这两个程序是并行执行的
并发可能是伪并行，也可能是真并行

进程的引入

进程是程序的一次执行，是程序及其数据，是在处理机上顺序执行时发生的活动
进程时系统进行资源分配和调度的一个独立单位
特征：动态性；并发性；独立性；异步性
进程的结构特征：
- 程序段、数据段、进程控制块PCB
- 一个进程应该包括：程序的代码；程序的数据；PC中的值，用来指示下一条将运行的指令
- 一组通用的寄存器的当前值，堆、栈
- 一组系统资源(打开的文件)
利弊：提高效率；空间开销、时间开销

进程的状态与控制

进程控制的主要任务：创建、撤销进程、实现进程的状态转换——内核实现
进程控制的实现：原语*

进程的三种基本状态
1. 就绪状态：进程已获得除处理机外的所需资源，等待分配处理机资源，只要分配CPU就可以执行
2. 执行状态：占用处理机资源；处于此状态的进程数目小于等于CPU的数目。在没有其他进程可以执行时，通常会自动执行系统的idle进程(相当于空操作)背单词啦啊喂
3. 阻塞状态：正在执行的进程，由于发生某种事件而暂时无法执行，便放弃处理机处于暂停状态
4. 状态转换：
进程控制块

系统为每个进程定义了一个数据结构：进程控制块PCB

作用：进程创建、撤销；进程的唯一标志；限制系统进程数目

内容：
- 进程标识符：每个进程必须有一个唯一的标识符
- 程序和数据地址：把PCB与其程序和数据联系起来
- 现行状态：方便管理
- 现场保护区
- 互斥和同步机制
- 进程通信机制
- 优先级
- 资源清单
- 链接字
- 家族关系
组织方式：线性表、链接方式、索引方式
- 进程上下文切换
  - 通常由调度器执行
  - 保存进程执行断点
  - 切换内存映射(页表基址、flush TLB)
- 陷入内核
  - CPU状态改变
  - 由中断、异常、Trap指令(系统调用)引起
  - 需要保存执行现场(寄存器、堆栈等)
- 系统调用
  - 涉及进程从用户态到内核态的切换，这个时候的切换主要是寄存器上下文的切换，和通常所说的进程上下文切换不同
进程包含了两个概念：资源拥有者和可执行单元

线程：将资源与计算分离，提高并发效率

进程与线程
- 现代操作系统将资源拥有者称为进程
- 可执行单元称为线程：CPU调度和分配的单位
引入线程的目的：
- 减小进程切换的开销
- 提高进程内的并发程序
- 共享资源
区分

CPU调度

调度

控制、协调多个进程对CPU的竞争

调度的类型
1. 高级调度——接纳作业的数量、类型
2. 中级调度——内外存交换
3. 低级调度——微观调度，“进程/线程调度”
进程切换

时机
- 用户系统调用：来自程序的显式请求(如打开文件)，该进程多半会被阻塞
- 陷阱：最末一条指令导致出错，会引起进程移至退出状态
- 中断：外部因素影响当前指令的执行，控制被转移至中断处理程序
步骤
1. 保存处理器的上下文，包括程序计数器和其他寄存器
2. 用新状态和其他相关信息更新正在运行进程的PCB
3. 把进程移至合适的队列
4. 选择另一个要执行的进程
5. 更新被选中进程的PCB
6. 从被选中进程PCB中重新装入CPU上下文
面向用户的调度性能准则
- 周转时间：作业从提交到完成所经历的时间
  - 平均周转时间
  - 带权周转时间
- 响应时间：用户输入一个请求到系统给出首次响应的时间
- 截止时间：开始截止时间和完成截止时间——实时系统
- 优先级
- 公平性
- 吞吐量：单位时间内所完成的作业数
常用调度算法
- 先来先服务——按作业提交的先后顺序调度
- 最短作业优先——按预计执行时间调度
- 最短剩余时间优先——按完成时间调度
- 最高响应比优先——响应比 $RP=\frac{T_{waited}+T_{needed}}{T_{needed}}$
交互式系统的调度算法
1. 时间片轮转
2. 多级队列
3. 多级反馈队列
内存管理

基本概念
1. 地址空间：一个进程所能用于访问内存的地址集合
2. 逻辑空间：虚拟地址，程序所使用的地址
3. 物理地址：存储器地址
碎片
- 内碎片：分配给作业的存储空间中未被利用的部分(无法被整理，但在作业完成后会得到释放)
- 外碎片：系统中无法利用的空闲小分区(动态分区管理会产生外部碎片)外碎片是造成内存系统性能下降的主要原因，外部碎片可以整理后清除
- 消除外部碎片的方法：紧凑技术
紧凑技术
- 通过移动作业，把多个分散的小分区拼凑成一个大分区的方法——消除外部碎片
- 实现支撑：动态重定位，作业在内存中的位置发生了变化，这就必须对其地址加以修改或改变
分区的存储保护
1. 界限寄存器方法
  1. 上下界寄存器方法
  2. 基址、限长寄存器(BR、LR)方法
2. 存储保护键方法
  1. 存储块保护键——加锁；作业保护键——加钥匙
  2. 作业运行时检查钥匙与锁是否匹配，不匹配则系统发出保护性中断信号，停止作业运行
扩充内存的两种方法
- 覆盖：把一个程序划分为一系列功能相对独立的程序段，让执行时不要求同时装入内存的程序段组成一组(称为覆盖段)，共享主存的同一个区域
  - 对用户不透明，增加了用户负担
- 交换：把暂时不用的某个或某些程序及其数据的部分或全部从主存移到辅存中去，以便腾出存储空间；接着把指定程序或数据从辅存读到相应的主存中，并将控制转给它，让其在系统上运行
  - 增加并发运行的程序数目，并给用户提供适当的响应时间，编写程序时不影响程序结构
  - 对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性
分区式内存管理
- 内存的碎片问题：无论固定分区，还是可变分区都普遍存在的问题；内存紧缩
- 程序需要装入连续的内存空间
- 很难满足程序对内存空间的动态要求
- 很难找到一个绝对有效的内存分配/回收策略
- 内存利用率低
页式内存管理

基本思想

把一个逻辑地址连续的程序分散存放到若干不连续的内存区域中，并保证程序的正确执行

纯分页系统

不具备页面对换的分页存储管理方式，不支持虚拟存储器功能；在调度一个作业时，必须把它所有的页一次装到主存的页框内，如果当时页框数不足，则作业必须等待，系统再调度另外作业
- 没有外碎片，每个内碎片不超过页大小——平均内碎片大小为页大小的1/2
- 程序不必连续存放
- 便于改变程序占用空间的大小
- 但程序全部装入内存；有内碎片
基本概念
- 页：把作业的地址空间分成一些大小相等的片，称之为页面(page)或页，各页从0开始编号
- 存储块：把物理内存的存储空间也分为与页面大小相同的片，这些片称为存储块，或称为页框，同样从0开始编号
- 页表：为了便于在内存中找到进程的每个页面所对应的页框，分页系统中为每一个进程配置一张页表，进程逻辑地址空间中的每一页，在页表中都有对应的一个页表项
数量关系
- 页大小：与块大小一样是由硬件来决定的，通常为2 的幂
- 逻辑地址空间为 $2^{m}$ ，且页大小为 $2^{n}$ ，那么逻辑地址的高 $m ? n$ 位表示页号，低n位表示页偏移
- 地址结构
  
  地址页号/块号偏移
  逻辑地址页号p 页内偏移w
  物理地址块号b 块内偏移d
  页内偏移=块内偏移
  
  页号和块号之间的联系？地址变化——页表查找
页表
- 存放在内存中，属于进程的现场信息
- 用途
  - 记录进程的内存分配情况
  - 实现进程运行时的动态重定位
- 访问一个数据需要访存2次——页表一次+内存一次
- 页表的基址和长度由页表寄存器给出
页表查找(地址变换机构)
- 页表内容：页号对应存储块号——页号作为页表项的索引不需要以数据形式存储
- 地址转换机构
  - 页表寄存器中页表长度与页号比较——越界中断
  - 页表始址与 $页号\times页表项长度$ 相加
  - 根据相加结果访问对应页表项，得到的数据即为页号对应块号
  - 块号与页内地址拼接得到物理地址
e.g 假设虚拟地址占8位，物理地址占10，每个页面的大小是64Bytes。问：
- 一共有多少个虚拟页面
- 一共有多少个物理页面(页框)
- 每个页表中有多少个页表项
- 假定页表是一个数组 $\left\{2,5,1,8\right\}$ ，请问对应虚拟地址0d241的物理地址是多少
解答
- $64=2^{6}$ 页内偏移占6位，即页号占 $8 ? 6 = 2$ 位，共有 $2^{2}=4$ 个虚拟页面
- 同1.共有 $2^{10-6}=16$ 个物理页面
- 一共有 $4$ 个虚拟页面——一个页表中有 $4$ 个页表项
- $0b11\ 110001$ 对应页号为3，即其对应的页框号为8(页号从0开始)，物理地址为 $0b1000\ 110001=0d561$
页表的分级

一级页表
- 若逻辑地址空间很大，则划分的页较多，页表就很大，占用的存储空间大(要求页表为连续存储)
- 解决方法——多级页表
  - 页表分级管理
  - 动态调入页表：只将当前需用的部分页表项调入内存，其余的需用时再调入
二级页表
- 将页表再进行分页，离散地将各个页表页面存放在不同的物理块中，同时再建立一张外部页表用以记录页表页面对应的物理块号(页表的页表)
- 正在运行的进程，必须把外部页表(页表的页表)调入内存，而动态调入内部页表。只将当前所需的一些内层页表装入内存，其余部分根据需要再陆续调入
- 逻辑地址：
  
  页表页面号页号页内地址
  e.g 对于32位地址空间，页面大小为4K，如每个页表项占4个字节，则页表需占 $4 M B$ 空间，则页表页面号：10位，页号：10位，页内地址：12位
- 地址变换：
  - 外部页表寄存器存放外部页表始址
  - 与 $页表页面号\times页表项大小$ 相加得到外部页表中对应位置
  - 取外部页表项(存放对应的第二级页表始址)与 $页号\times页表项大小$ 得到对应第二级页表的页表项，取出数据(物理页框号)
  - 与页内地址拼接得到物理地址
    
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZJ4lTrMe-1637284592615)(/Users/cleopatra/Library/Application Support/typora-user-images/image-20211116162559370.png)]
  - e.g 页面的大小为8 Bytes，物理内存为128 Bytes，虚拟地址空间为512 Bytes。假设每个页表项占一个字节，设计一个多级页表，并回答如何查询虚拟地址 $0 x 3 A$ 对应的物理地址
  解答
  - 页内偏移量： $8=2^{3}$ ，3位
  - 物理页框号： $128/8=16=2^{4}$ ，4位
  - 虚拟页号： $512/8=64=2^{6}$ ，6位，逻辑地址 $512=2^{9}$ ，9位
  - 页表项1 Bytes——一个页面存储8个页表项，一个页表最多管理8个页面——需要三位表示页号
  - 一级页号二级页号：3位页内偏移：3位
    推出一级页号占3位
  - $0x3A=0b000\ 111\ 010$ 推出一级页号为0，二级页号为7，页内偏移为2
  - 查询步骤：
    1. 查找一级页表中的第0页表项，从中找到对应的二级页表的物理地址，读出相应的物理页框；
    2. 查找对应二级页表的第7页表项，从中找到对应的物理页框号；
    3. 上一步得到的物理页框的初始地址+偏移量010即为物理地址
- 多级页表
  - 多级页表结构中，指令所给出的地址除偏移地址外的各部分全是各级页表的页表号或页号，而各级页表中记录的全是物理页号，指向下级页表或真正的被访问页
快表(联想存储器)，TLB
- 特殊的高速缓冲存储器Cache，内容是页表中的一部分或全部内容
- CPU产生逻辑地址的页号，首先在快表中寻找，若命中就找出其中对应的物理块；若未命中，再到页表中找到其对应的物理块，并将相应的页表项复制到快表。若快表中内容满，则按某种算法淘汰某些页
- 快表一般包含
  
  valid有效位 Tag(virtual page number)虚拟页号 page frame number物理页框号
- 有效访问时间
  
  假如查找TLB需要20ns，访问内存需要100ns，TLB命中率为80%
  - 有效内存访问时间= $(2 ? 100 n s + 20 n s) ? 0.2 + (100 n s + 20 n s) ? 0.8$
  - 过程分析：不命中的情况下，首先访问TLB未命中(20ns)，再访问内存内页表(100ns)，最后根据页表内容访问内存内物理页(100ns)；命中的情况下，首先访问TLB命中(20ns)，再根据快表页框号访问对应物理页面(100ns)
- 哈希页表、反置页表
  - 哈希页表：处理超过32位地址空间的常用方法：以虚拟页号作为哈希值
  - 反置页表：按照物理地址排序，查找依据虚拟地址