961复习要点
计组
总线与输入输出控制方式
总线分类
片内总线
CPU 内部的总线。是CPU 内部各寄存器之间、寄存器
与ALU之间传递信息的公共通道
系统总线
数据总线 地址总线 控制总线 通信总线
用于计算机系统间或计算机系统与其他系统的通信
总线特性
机械特性 电气特性 功能特性 过程特性
总线仲裁(控制)方式
分布式控制方式
集中式控制方式(总线控制逻辑集中于一处)
链式查询方式
优点:线少,易扩充
缺点:故障敏感,优先级固定
计数器定时查询方式(公平)
优点:优先级灵活
缺点:每个设备都需与新增的设备地址线相连,线多
独立请求方式(公平)
优点:响应快,优先级灵活,请求可屏蔽
缺点:每个设备都有单独的总线请求信号线与总线同意信号线,线多
总线传输的五个阶段
请求总线 总线仲裁 寻址 地址传送 状态返回
总线的通信控制方式
同步通信控制方式——数据传输在统一的时钟同步信号的控制下进行 异步通信控制方式
不互锁 半互锁 全互锁
I/O设备
I/O设备的分类
按传送数据格式:串行接口、并行接口 按信息交换单位:
字符设备:用于数据输入输出;无结构类型——交互式终端机、打印机;不可寻址,在输入输出时常采用中断驱动方式 块设备:由于信息存取;有结构设备——磁盘;可寻址,以数据块为单位 按I/O方式:程序查询接口、中断接口、DMA接口、通道控制接口 按时序控制方式:同步接口、异步接口
I/O设备的编址方式
统一编址:存储器地址与I/O地址统一考虑,地址空间的一部分是存储器,另一部分是I/O,支持存储器操作的指令都可用于I/O操作——MIPS 独立编址:存储器地址与I/O地址分开,CPU具有专用的I/O指令,系统总线中具有区别存储器读写和I/O操作的控制信号,并以此区别地址总线上的地址是存储器地址还是I/O地址
I/O与主机信息交换的控制方式
程序查询方式
程序中断方式
直接内存访问方式(DMA)
CPU对总线的控制被临时禁止。DMA控制器接管总线控制权 , 控制数据直接在存储器与外设之间高速交换 CPU不再介入具体的I/O操作,由DMA控制器来负责提供存储器地址信号、读写控制信号等 CPU与I/O设备在更大的程度上并行工作,效率更高 数据传送结束后,通过中断方式告知CPU进行善后处理 CPU仅在开始DMA操作之前 和完成DMA操作之后 参与 I/O处理,在DMA过程中,CPU可以运行原来的程序 DMA方式适合高速批量 的数据传输,如视频显示刷新、磁盘存储系统的读写,存储器到存储器的传输等
通道方式
在常用的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)
虚拟存储器(虚存)
虚存空间与物理空间
用户编程空间:用户编制程序时使用的地址称为虚地址或逻辑地址,其对应的存储空间称为虚存空间或逻辑地址空间。虚存空间的用户程序按照虚地址编程并存放在辅存 中
物理内存空间:计算机物理内存的访问地址称为实地址或物理地址,其对应的存储空间称为物理空间或主存 空间
虚拟存储器的调度方式
页式虚拟存储器
某机器字长为64位,内存容量为256MB,若按字编址,则其寻址空间为0~32M-1 ——按字编址,256MB/64bit=32M
进程可以使用的最大地址空间受限于地址位数
虚拟地址空间可以大于物理地址空间,也可以小于物理地址空间
假设:某磁盘的可用盘面数为10,每个盘面的磁道数为100,磁盘分为8个扇区,每扇区存储512个字节,磁盘转速为6000RPM。主存与磁盘之间的数据传送采用DMA单字传送方式,单字长为32位。一条指令的最长执行时间是20微秒。
请问:
该磁盘的容量是多少?
10
×
100
×
8
×
512
b
y
t
e
s
=
4000
k
b
y
t
e
s
10\times100\times8\times512bytes=4000kbytes
1 0 × 1 0 0 × 8 × 5 1 2 b y t e s = 4 0 0 0 k b y t e s
该磁盘的数据传输率是多少?
(
6000
/
60
)
×
8
×
512
b
y
t
e
s
=
400
k
b
y
t
e
s
/
s
(6000/60)\times8\times512bytes=400kbytes/s
( 6 0 0 0 / 6 0 ) × 8 × 5 1 2 b y t e s = 4 0 0 k b y t e s / s
是否可采用一条指令执行结束时响应DMA请求的方案,为什么?
不能;
传输单字:
(
32
/
8
)
/
400
k
b
y
t
e
s
/
s
=
0.01
×
1
0
?
3
s
=
10
μ
s
(32/8)/400kbytes/s=0.01\times10^{-3}s=10\mu s
( 3 2 / 8 ) / 4 0 0 k b y t e s / s = 0 . 0 1 × 1 0 ? 3 s = 1 0 μ s ;
即约每隔
10
μ
s
10\mu s
1 0 μ s 就会有一次DMA传送请求,采取此方案会造成数据丢失。
假设一个内存管理系统有47位的虚拟空间,每页大小为16KB,并且页表项占用8位。在每级页表大小不超过1页的情况下,需要几级页表来完成虚拟地址的映射?给出虚拟地址的结构划分,并详细解释:
每页最多可包含:
16
K
B
/
8
b
i
t
=
16
K
=
2
14
16KB/8bit=16K=2^{14}
1 6 K B / 8 b i t = 1 6 K = 2 1 4 个页表项,又页表以虚页号作为索引,故虚页号最大为14位;
页内偏移量:
16
K
B
=
2
14
→
14
16KB=2^{14}\rightarrow 14
1 6 K B = 2 1 4 → 1 4 故虚拟地址中页内偏移量为14位;
可供页目录使用的地址空间最多有:
47
?
14
=
33
47-14=33
4 7 ? 1 4 = 3 3 ;
要求每级页表不超过一页——
33
/
14
=
3
(
向
上
取
整
)
33/14=3(向上取整)
3 3 / 1 4 = 3 ( 向 上 取 整 ) 至少需要3级页表
(这里其实不太明白,但是感觉各级目录相等比较顺眼QAQ)
33
/
3
=
11
33/3=11
3 3 / 3 = 1 1 故每一级页目录均为11位;
虚拟地址的结构划分:
一级页目录 二级页目录 三级页目录 页内偏移量 11位 11位 11位 14位
虚拟地址地址空间的大小仅取决于地址结构
页面越大,页面内部的内存碎片会越多;内碎片 ——分配给作业的存储空间中未被利用的部分
页面的大小会影响进程切换的速度
页面越大,运行程序所需的页面越少
现有一个容量为4GB的磁盘分区,磁盘空间以簇为单位进行分配,簇的大小为4KB,若采用位图法管理该分区的空间,即用一位(bit)标识一个簇是否被分配,则存放该位图所需簇的个数为:
需要
4
G
B
/
4
K
B
=
2
20
4GB/4KB=2^{20}
4 G B / 4 K B = 2 2 0 个簇
每个簇用一位标识——
2
20
2^{20}
2 2 0 位
每个簇可以存放
2
12
×
2
3
=
2
15
2^{12}\times2^{3}=2^{15}
2 1 2 × 2 3 = 2 1 5 位
需要
2
20
/
2
15
=
32
2^{20}/2^{15}=32
2 2 0 / 2 1 5 = 3 2 个簇存放
假设只考虑页内碎片和页表引起的额外内存。如进程本身占用内存的平均大小是1MB,每个页表项的大小是8B,为减少额外的内存开销,页面大小应设置为:
页内碎片:页大小决定==>取平均值(页内不产生碎片~整页分配后未使用)
页表大小:页面数量决定(存放页面所需的内存大小)
不妨设页面大小为
2
m
B
2^{m}B
2 m B ;
则进程所需的页面数量为
2
20
/
2
m
=
2
20
?
m
2^{20}/2^{m}=2^{20-m}
2 2 0 / 2 m = 2 2 0 ? m 个;
存放这些页面消耗的内存大小:
2
20
?
m
×
2
3
=
2
23
?
m
2^{20-m}\times 2^{3}=2^{23-m}
2 2 0 ? m × 2 3 = 2 2 3 ? m
页内碎片平均值=
(
1
/
2
)
×
2
m
=
2
m
?
1
(1/2)\times 2^{m}=2^{m-1}
( 1 / 2 ) × 2 m = 2 m ? 1
要使
2
m
?
1
+
2
23
?
m
2^{m-1}+2^{23-m}
2 m ? 1 + 2 2 3 ? m 达到最小:m=12;
主存储器
存储器分类
存储单元电路
可存储1bit二进制代码 存储位元---->存储芯片---->存储器
存储器芯片结构
基本描述:字单元数
×
\times
× 字单元位数(
2
n
×
m
2^{n}\times m
2 n × m ) 一维地址结构
地址线n条——单向——经过译码变为
2
n
2^{n}
2 n 根地址选择线
2
n
2^{n}
2 n 选择线数据线m位——双向 二维地址结构
行列相等时最佳 行地址线=列地址线=
2
n
/
2
2^{n/2}
2 n / 2
2
×
2
n
/
2
2\times2^{n/2}
2 × 2 n / 2 地址选择线(行列复用则不需要乘2)数据线m条——双向——
log
?
2
m
\log_{2}m
log 2 ? m 位
存储器扩展
位扩展
拼接数据空间 地址总线不变,数据总线按扩展位数增加 片选信号位数不变 字扩展
拼接地址空间 地址总线按扩展位数增加,数据总线不变 片选信号按扩展后芯片数确定 混合扩展
混合扩展同时扩展了数据空间与地址空间 片选信号取决于字扩展,与位扩展无关
DRAM的刷新
刷新操作:读操作
刷新特点
按行刷新,所有芯片同时进行 刷新操作与CPU访问内存分开进行 刷新周期 刷新地址与刷新地址计数器
刷新方式
集中刷新(有
2
n
2^{n}
2 n 行;设刷新周期为2ms;读写周期为
0.5
μ
s
0.5\mu s
0 . 5 μ s )
在一个时间段内,刷新存储器所有行,此时CPU停止访问内存;另一个时间段内,CPU可以访问内存,刷新电路不工作
分散式刷新(有
2
n
2^{n}
2 n 行;设刷新周期为2ms;存取周期为
0.5
μ
s
0.5\mu s
0 . 5 μ s )
分布式刷新
动态RAM依据电容充放电 原理存储信息;静态RAM依据触发器 原理存储信息。
构造
32
k
×
32
b
i
t
32k\times32bit
3 2 k × 3 2 b i t 的存储器共需64 片
2
k
×
8
b
i
t
2k\times8bit
2 k × 8 b i t 的SRAM存储芯片
容量
1
M
×
16
b
i
t
1M\times16bit
1 M × 1 6 b i t 的DRAM存储芯片,如采用二维地址结构,且行地址和列地址的位数相同,则行译码器输出的行选择线有1024根 ,该芯片的刷新地址计数器是10位
用多个容量
1
k
×
4
b
i
t
1k\times4bit
1 k × 4 b i t 的存储芯片,组成容量为
64
k
×
8
b
i
t
64k\times8bit
6 4 k × 8 b i t 的存储器。若将这些芯片分装在几块内存板上,每块内存板容量为
16
k
×
8
b
i
t
16k\times8bit
1 6 k × 8 b i t ,则该存储器的地址线中,必须有2根地址线用于选内存板 ,4根地址线用于选芯片
容量为
32
k
×
16
b
i
t
32k\times16bit
3 2 k × 1 6 b i t 的存储器芯片,其地址线数量和数据线数量的总和为31
p.s:地址线是地址信号线,用于传送地址信息 ;地址选择线用于定位存储位元
某计算机的数据总线为8位,地址总线为20位,主存按字节编址,其中地址最低的256KB主存空间为只读系统程序区,其余为用户程序区,现有若干容量为
64
k
×
8
b
i
t
64k\times8bit
6 4 k × 8 b i t 的ROM芯片和容量为
256
k
×
8
b
i
t
256k\times8bit
2 5 6 k × 8 b i t 的DRAM芯片:
上述规格的DRAM芯片,若行地址和列地址共享同一组芯片管脚,则所需地址管脚多少根?芯片的刷新地址计数器是多少位?
256
k
=
2
18
?
?
?
?
>
行
地
址
管
脚
=
列
地
址
管
脚
=
2
9
=
512
根
,
刷
新
地
址
计
数
器
的
位
数
=
总
行
数
位
数
=
9
位
256k=2^{18}---->行地址管脚=列地址管脚=2^{9}=512根,刷新地址计数器的位数=总行数位数=9位
2 5 6 k = 2 1 8 ? ? ? ? > 行 地 址 管 脚 = 列 地 址 管 脚 = 2 9 = 5 1 2 根 , 刷 新 地 址 计 数 器 的 位 数 = 总 行 数 位 数 = 9 位
若DRAM芯片采用分布式刷新方式 ,且存储单元刷新间隔最长为4ms,则刷新周期是多少?
==???==分布式刷新方式
?
?
?
?
>
---->
? ? ? ? > 刷新周期=
4
m
s
/
512
4ms/512
4 m s / 5 1 2
查阅资料得*:对于每行以4ms为刷新周期足够了,刷新循环到它需要512刷新次操作, 4ms ÷ 512 作为每次刷新的周期 ,(注意每次刷新周期与特定行的刷新周期的不同:每次刷新间隔指对于内存来说它隔多长时间就进行一次刷新操作,轮着刷新时,刷新的行是上一次刷新的行的下一行——是不同的两行,但对于全局内存来说确实是两次刷新操作间隔。特定哪一行的刷新周期:下一次对它进行刷新的间隔,期间要经过64次内存刷新周期才又轮得到它。)
该计算机所允许的最大主存容量是多少?
地址总线为20位,数据总线为8位,按字节编址
2
20
×
(
8
b
i
t
/
8
)
=
1
M
B
2^{20}\times(8bit/8)=1MB
2 2 0 × ( 8 b i t / 8 ) = 1 M B 构建该计算机所允许的最大容量的主存,需用上述规格的ROM芯片和DRAM芯片各多少片?
只读系统程序区
256
K
B
?
?
?
?
>
R
O
M
256KB---->ROM
2 5 6 K B ? ? ? ? > R O M ,
256
/
64
=
4
256/64=4
2 5 6 / 6 4 = 4 块
DRAM芯片
768
K
B
?
?
?
?
>
D
R
A
M
768KB---->DRAM
7 6 8 K B ? ? ? ? > D R A M ,
768
/
256
=
3
768/256=3
7 6 8 / 2 5 6 = 3 块
请给出每个ROM芯片和DRAM芯片在上述主存中的地址空间范围。
2
20
=
1
6
5
?
?
?
?
>
5
2^{20}=16^{5}---->5
2 2 0 = 1 6 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汇编
机器指令的要素
操作码 源操作数地址 目的操作数地址 下条指令的地址:只有少数指令需要指明下一条指令的地址
指令类型
数据传输指令:寄存器与存储器之间、寄存器之间传递数据 算数/逻辑运算指令:寄存器中整型数或逻辑型数据的运算操作,以及处理浮点数运算的浮点运算指令 程序控制指令:控制程序执行顺序,条件转移或跳转,子程序调用或返回 其他指令:多用户多任务系统中的特权指令;复位/暂停/空操作等指令
操作数类型
数值:无符号、定点、浮点 逻辑型数、字符 地址:操作数地址,指令地址
操作数的位置
存储器(存储器地址) 寄存器(寄存器地址) 输入输出端口(输入输出端口地址)
操作数存储方式
大端存储:最高有效字节存储在地址最小位置 小端存储:最低有效字节存储在地址最小位置
机器指令
计算机硬件可以执行的表示一种基本操作的二进制代码
指令格式:操作码+操作数(操作数地址) 操作码:指明指令的操作性质 操作数(地址):指明操作数的位置(或操作数本身) 操作数地址的数目
三地址:
OP DES Add SUR1 Add Sur2 Add
双地址
单地址:累加器作为其中一个操作数的双操作数型,或单操作数型
零地址:隐含操作数型,或无操作数型
指令长度
定长指令系统: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相加 因此可以分支到
P
C
±
2
15
PC\pm2^{15}
P C ± 2 1 5 字节的地方 改进:根据“字对齐”,其实可以分支到
P
C
±
2
15
PC\pm2^{15}
P C ± 2 1 5 指令字 即
P
C
±
2
17
PC\pm2^{17}
P C ± 2 1 7 字节
P
C
=
(
P
C
+
4
)
+
(
i
m
m
e
d
i
a
t
e
?
4
)
PC=(PC+4)+(immediate*4)
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执行时间:
程
序
的
C
P
U
时
钟
周
期
数
×
时
钟
周
期
长
度
程序的CPU时钟周期数\times时钟周期长度
程 序 的 C P U 时 钟 周 期 数 × 时 钟 周 期 长 度
程
序
的
C
P
U
时
钟
周
期
数
时
钟
频
率
\frac{程序的CPU时钟周期数}{时钟频率}
时 钟 频 率 程 序 的 C P U 时 钟 周 期 数 ?
程序的CPU时钟周期数:
程
序
指
令
数
×
每
条
指
令
的
平
均
时
钟
周
期
数
程序指令数\times每条指令的平均时钟周期数
程 序 指 令 数 × 每 条 指 令 的 平 均 时 钟 周 期 数
C
P
I
:
指
令
平
均
执
行
时
钟
周
期
数
CPI:指令平均执行时钟周期数
C P I : 指 令 平 均 执 行 时 钟 周 期 数
不同指令集的CPI比较没有意义
C
P
U
的
时
钟
周
期
数
=
∑
C
P
I
i
×
I
i
CPU的时钟周期数=\sum{CPI_i\times I_i}
C P U 的 时 钟 周 期 数 = ∑ C P I i ? × I i ?
平
均
时
钟
周
期
数
C
P
I
=
C
P
U
时
钟
周
期
数
/
I
C
(
指
令
的
条
数
)
平均时钟周期数CPI=CPU时钟周期数/IC(指令的条数)
平 均 时 钟 周 期 数 C P I = C P U 时 钟 周 期 数 / I C ( 指 令 的 条 数 )
C
P
U
时
间
=
C
P
U
时
钟
周
期
数
×
时
钟
周
期
长
=
C
P
U
时
钟
周
期
数
/
频
率
=
(
I
C
×
C
P
I
)
/
f
CPU时间=CPU时钟周期数\times时钟周期长=CPU时钟周期数/频率=(IC\times CPI)/f
C P U 时 间 = C P U 时 钟 周 期 数 × 时 钟 周 期 长 = C P U 时 钟 周 期 数 / 频 率 = ( I C × C P I ) / f MIPS:百万指令每秒
不同指令集的MIPS比较没有意义 同一台机器,不同的测试程序测出来的MIPS值也可能不一样
M
I
P
S
=
I
C
执
行
时
间
×
1
0
6
=
I
C
(
I
C
×
C
P
I
)
×
1
0
6
/
f
=
f
C
P
I
×
1
0
6
MIPS=\frac{IC}{执行时间\times 10^{6}}=\frac{IC}{(IC\times CPI)\times10^{6}/f}=\frac{f}{CPI\times10^{6}}
M I P S = 执 行 时 间 × 1 0 6 I C ? = ( I C × C P I ) × 1 0 6 / f I C ? = C P I × 1 0 6 f ? MFLOP:百万浮点操作数每秒
计网
应用层
应用层概述
所有网络协议均为了某种应用服务 应用层的许多协议大部分是基于client/server方式
QQ、Weixin等使用私有协议 HTTP、SSH等使用开放协议 均基于基于TCP、UDP、IP等底层协议 应用层协议运行在用户态 ,由应用程序负责管理;TCP/IP等协议运行在内核态 ,由操作系统负责管理; 应用程序使用网络时,需要调用操作系统提供的接口,即应用Socket API
Socket(套接字)
面向连接并发服务器——e.g TCP
无连接循环服务器——e.g UDP
辨析:面向连接即连接已建立,则不需要说明交给谁——直接send()、recv() ;无连接则需要说明交给谁、接收谁发的——sendto()、recvfrom()
Telnet:使用TCP连接到特定服务器,并将输入发送给服务端, 将从服务器接收的信息显示在屏幕上
WWW(万维网)
分布式超媒体 (hypermedia) 系统,是超文本 (hypertext) 系统的扩充
一个超文本由多个信息源链接成,超文本是万维网的基础 超媒体与超文本的区别是文档内容不同 HTTP ——HyperText Transfer Protocol
无连接
基于TCP,可靠交换文件的重要基础
熟知端口号:80
① 怎样标识分布在Internet上的万维网文档? ------URL
② 用什么协议实现万维网上各种超链的链接?------HTTP
③ 如何存储和表示万维网文档?------HTML
HTTP/1.0每传送一个文件都需要建立一次TCP连接;HTTP/1.1进行了改进;
网站地址:统一资源定位符 URL
由以冒号隔开的两大部分组成,并且在 URL 中的字符对大写或小写没有要求 缺省:
文件的<路径>项——缺省经常是index.html, default.html etc. 文件的<端口>项——采用协议默认端口时一般可以省略 Cookie 是网站服务器为用户产生一个唯一的识别码 HTTP报文类型:
请求报文 响应报文 HTTP是面向正文的(text-oriented),报文中的字段都是 ASCII 码串 ,因而每个字段的长度都是不确定的 安全 的HTTP协议:HTTPS
建立在SSL基础上 熟知端口号为443 加密的数据传输
文件传输协议FTP(File Transfer protocol)
FTP 提供交互式的访问,允许客户指明文件的类型与格式,并允许文件具有存取权限 FTP 屏蔽了各计算机系统的细节 ,因而适合于在异构网络中任意计算机之间传送文件 端口号:
control:21; data:20 面向连接:FTP客户与服务器传递FTP命令时,使用的是建立在TCP 之上的控制连接
电子邮件
发邮件
SMTP()
① 连接建立:连接在发送主机的SMTP客户和接收主机的SMTP 服务器之间建立,不使用中间邮件服务器
② 邮件传送
③ 连接释放:邮件发送完毕后,SMTP释放TCP 连接
SMTP支持在邮件服务器间、用户代理及邮件服务器间发送邮件(双向均可)
收邮件
POP3——Post Office Protocol:收方邮件服务器到收方主机(单向) IMAP——Internet Message Access Protocol:功能更强大、丰富
域名服务
提供域名到IP地址转换的服务叫域名服务
域名:…… . <三级域名>.<二级域名>.<顶级域名>——需要转换为IP地址才可以访问
域名服务器程序在专设的结点上运行, 运行该程序的机器称为域名服务器
互联网采用了层次树状结构 的命名方法
权限域名服务器:
根域名服务器:不管是哪一个本地域名服务器,若要对互联网 上任何一个域名进行解析,只要自己无法解析, 就首先求助于根域名服务器
根域名服务器并不直接把域名直接转换成 IP 地址。 在使用迭代查询时,根域名服务器把下一步 应当找的顶级域名服务器的 IP 地址 告诉本地域名服务器 。 顶级域名服务器
负责管理在该顶级域名服务器注册的所有二级域名 当收到 DNS 查询请求时,就给出相应的回答(可能是最后的结果,也可能是下一步应当找的域名服务器的IP地址) 权限域名服务器
保存该区中所有主机 的域名到IP地址的映射 当一个权限域名服务器还不能给出最后的查询回答时,就会告诉发出查询请求的DNS客户,下一步应当找哪一个权限域名服务器 本地域名服务器
当一个主机发出DNS查询请求时,这个查询请求报文就发送给本地域名服务器 主机向本地域名服务器的查询一般都是采用递归查询
本地域名服务器向根域名服务器的查询通常是采用迭代查询
每个域名服务器都维护一个高速缓存,存放最近用过的名字以及从何处获得名字映射信息的记录
可大大减轻根域名服务器的负荷 为保持高速缓存中的内容正确,域名服务器应为每项内容设置计时器,并处理超过合理时间的项 当权限域名服务器回答一个查询请求时,在响应中都指明绑定有效存在的时间值。增加此时间值可减少网络开销,而减少此时间值可提高域名转换的准确性
简单网络管理协议SNMP
网络管理包括对硬件、软件和人力的使用、综合与协调,以便对网络资源进行监视、测试、配置、分析、评价和控制, 这样就能以合理的价格满足网络的一些需求,如实时运行性能,服务质量等。 网络管理并不是指对网络进行行政上的管理
如果本地域名服务器无缓存,当采用递归方法解析另一网络某主机域名时,用户主机、本地域名服务器发送的域名请求消息数分别为一条 、一条
在“HTTP协议缺省使用端口80”这句话中,端口80为Web服务器的传输层端口号
HTTP协议的英文全称是Hypertext Transfer Protocol
TCP/IP协议向应用层提供的编程接口是Socket
域名解析DNS 使用的传输层协议是UDP ,如果一个C语言编写的应用程序基于该传输层协议实现网络通信,则该程序可调用套接字(Socket)编程接口函数 sendto 向外发送数据
建立TCP连接后,报文段中搭载的HTTP协议报文头部中用于获取文件的命令是GET
运行在不同主机间的两个应用进程AP1和AP2之间能建立多个TCP连接
传输层
传输层协议概述
传输层又叫运输层
向应用层提供服务
功能:连接管理、流量控制、差错控制、拥塞控制、建立无连接和面向连接的通信等
通信逻辑:进程(??用进程标识符来标志)间通信,端到端;可以复用和分用;可靠/不可靠通信服务
网络环境中一个完整的进程通信标识需要一个五元组来表示:
主要协议
UDP协议:无连接,用户数据报协议
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的流量控制
滑动窗口——实现可靠传输和流量控制
TCP的拥塞控制
拥塞概念:
在某段时间内,若对网络中某资源的需求超过了该资源所能提供的可用部分,网络性能就要变坏,从而产生拥塞
拥塞产生的条件
∑
s
o
u
r
c
e
?
n
e
e
d
e
d
>
s
o
u
r
c
e
?
a
v
a
i
l
a
b
l
e
\sum source-needed > source-available
∑ s o u r c e ? n e e d e d > s o u r c e ? a v a i l a b l e
注意??:网络拥塞是多种原因引起的,通过简单地增加某种资源数量往往不能消除拥塞
拥塞常常会趋于恶化:TCP重传机制
e.g 一个路由器由于缓存不足丢弃了部分报文,发送端主机将超时重发,导致网络中被注入了更多的报文,从而加剧拥塞。
拥塞控制
防止过多的数据被注入到网络中,使网络中的路由器或链路不致过载。
是全局性的过程
流量控制
点对点通信量的控制——端到端的问题
RFC2581定义的4种拥塞控制方法
慢启动,又称为慢开始
开始发送时,如果立即把大量报文注入网络,则可能导致拥塞——不清楚网络的负荷状况——试探性地增加发送窗口
拥塞窗口
c
w
n
d
cwnd
c w n d :
慢启动的工作过程
开始发送报文段时,设置
c
w
n
d
cwnd
c w n d 为1,即设置为一个最大报文段
M
S
S
MSS
M S S 的数值 每收到一个对新的报文段的确认后,将拥塞窗口加一,即增加一个
M
S
S
MSS
M S S 的数值 传输轮次:使用慢启动时,每经过一个传输轮次,拥塞窗口
c
w
n
d
cwnd
c w n d 就加倍;一个传输轮次 所经历的时间其实就是往返时间
R
T
T
RTT
R T T ——把拥塞窗口
c
w
n
d
cwnd
c w n d 所允许的报文段都发送出去并收到了对已发送的最后一个字节的确认 慢启动门限
s
s
t
h
r
e
s
h
ssthresh
s s t h r e s h ——使用慢启动算法与拥塞避免算法的分界线 拥塞避免
思路:每经过一个往返时间
R
T
T
RTT
R T T 就将发送方的拥塞窗口
c
w
n
d
cwnd
c w n d 加1,而不是加倍——拥塞窗口按线性规律缓慢增长——加法增大
快重传
思路:如果发送方在超时时间内未收到确认报文,说明网络中发生拥塞,此时发送方应尽早地减小窗口宽度
如果接收方收到一个失序的报文段,就发出重复确认,以便使发送方尽早知道有报文段没有到达接收方 发送方只要接收到三个重复确认就应当立即重传 对方尚未收到的报文段 快恢复
思路:当发送方收到连续三个重复的确认 时,就进行“乘法减小”,即将慢启动门限
s
s
t
h
r
e
s
h
ssthresh
s s t h r e s h 减为当前的拥塞窗口宽度的一半
接下来不执行慢启动算法,而是设置为慢启动门限
s
s
t
h
r
e
s
h
ssthresh
s s t h r e s h 减半后的数值,然后开始执行拥塞避免算法——“加法增大” 发送方认为当前网络可能没有发生拥塞(仅有拥塞征兆) 发送窗口的上限值——
min
?
[
r
w
n
d
,
c
w
n
d
]
\min[rwnd,cwnd]
min [ r w n d , c w n d ]
TCP的连接管理
三个阶段——“C/S方式”
连接建立 数据传送 连接释放
连接建立——三次握手
客户机请求连接——
S
Y
N
=
1
,
A
C
K
=
0
SYN=1,ACK=0
S Y N = 1 , A C K = 0 ,选择
s
e
q
=
x
seq =x
s e q = x 表明传送数据时第一个数据字节的序号 服务器确认连接请求——
S
Y
N
=
1
,
A
C
K
=
1
SYN=1,ACK=1
S Y N = 1 , A C K = 1 ,确认号
a
c
k
=
x
+
1
ack=x+1
a c k = x + 1 ,自己选择序号
s
e
q
=
y
seq=y
s e q = y 客户机收到后,给出确认——
S
Y
N
=
0
,
A
C
K
=
1
SYN=0,ACK=1
S Y N = 0 , A C K = 1 ,确认号
a
c
k
=
y
+
1
ack=y+1
a c k = y + 1
为什么是三次握手?
三次握手带来的安全问题及解决办法?
TCP-SYN flooding——不停发出连接请求,但不对SYN、ACK报文做出响应,占用服务器内部数据缓存
连接释放——可由任意方发起
A主动关闭连接——
F
I
N
=
1
,
s
e
q
=
u
FIN=1,seq=u
F I N = 1 , s e q = u B接收后发出确认——
A
C
K
=
1
,
a
c
k
=
u
+
1
,
s
e
q
=
v
ACK=1,ack=u+1,seq=v
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
FIN=1,ACK=1,seq=w,ack=u+1
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
ACK=1,ack=w+1,seq=u+1
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
S_1-S_{14}
S 1 ? ? S 1 4 ? ,数据长度栏目表示报文段所搭载的应用数据长度。表格中的数值均为10进制,标注为’X’的表示该字段值未知,已知A、B间建立TCP连接的过程中通过选项字段协商确定最大报文段长度MSS=1000字节 ,双方均按照慢启动(开始)和拥塞避免机制进行传输,慢启动门限
s
s
t
h
r
e
s
h
=
4
ssthresh=4
s s t h r e s h = 4 ,单位:MSS,传输过程中没有报文段超时
编号 传输方向 序号 确认号 ACK SYN 窗口
S
1
S_1
S 1 ?
A
→
B
A\rightarrow B
A → B 0 0 X X 6500
S
2
S_2
S 2 ?
B
→
A
B\rightarrow A
B → A 0 1 X X 16384
S
3
S_3
S 3 ?
A
→
B
A\rightarrow B
A → B 1 1 X X 6500
S
4
S_4
S 4 ?
A
→
B
A\rightarrow B
A → B 1 1 1 0 6500
S
5
S_5
S 5 ?
B
→
A
B\rightarrow A
B → A 1 382 1 0 16384
S
6
S_6
S 6 ?
A
→
B
A\rightarrow B
A → B 382 1001 1 0 5500
S
7
S_7
S 7 ?
B
→
A
B\rightarrow A
B → A 1001 382 1 0 16384
S
8
S_8
S 8 ?
B
→
A
B\rightarrow A
B → A 2001 382 1 0 16384
S
9
S_9
S 9 ?
A
→
B
A\rightarrow B
A → B 382 3001 1 0 3500
S
10
S_{10}
S 1 0 ?
B
→
A
B\rightarrow A
B → A 3001 382 1 0 16384
S
11
S_{11}
S 1 1 ?
B
→
A
B\rightarrow A
B → A 4001 382 1 0 16384
S
12
S_{12}
S 1 2 ?
B
→
A
B\rightarrow A
B → A 5001 382 1 0 16384
S
13
S_{13}
S 1 3 ?
B
→
A
B\rightarrow A
B → A 6001 382 1 0 16384
S
14
S_{14}
S 1 4 ?
A
→
B
A\rightarrow B
A → B 382 X 1 0 6000
已知报文段
S
1
,
S
2
,
S
3
S_1,S_2,S_3
S 1 ? , S 2 ? , S 3 ? 是A、B间建立TCP连接的报文段,请分别给出这三个报文段中SYN和ACK两个字段的值 报文段
S
4
S_4
S 4 ? 中搭载的HTTP协议报文头部中的方法或命令是什么? 请给出报文段
S
8
S_8
S 8 ? 和
S
13
S_{13}
S 1 3 ? 中搭载的数据长度 和报文段
S
14
S_{14}
S 1 4 ? 中搭载的确认号字段 假设B在收到
S
14
S_{14}
S 1 4 ? 后,直到收到A的下一个确认之前,最多可向A发送n个字节的应用数据。如果B在报文段
S
14
S_{14}
S 1 4 ? 之后仍然采用慢启动机制,n的值是多少?如果B在报文段
S
14
S_{14}
S 1 4 ? 之后改用拥塞避免机制,n的值是多少?
解析 :
序号 SYN ACK
S
1
S_1
S 1 ? 1 0
S
2
S_2
S 2 ? 1 1
S
3
S_3
S 3 ? 0 1
原因:SYN字段值表示正在请求建立连接/同意建立连接请求,ACK字段在连接建立后直到连接断开之前恒为1
S
4
S_4
S 4 ? 开始向Web服务器请求发送文件,方法:GET
根据确认号推知,
S
8
S_8
S 8 ? 搭载的数据长度为1000字节,在
S
13
S_{13}
S 1 3 ? 所处的发送轮次中,由于A给出了接收窗口的最大值为3500字节,故而B在未收到A的确认信息之前,最多能向A传送3500字节——
S
13
S_{13}
S 1 3 ? 搭载的数据长度为500,传输过程中没有报文段超时,因此A在
S
14
S_{14}
S 1 4 ? 给出的确认号为A接下来可以接受的最小序号值,即6001+500=6501
分析 :
最初B的发送窗口值为1(慢启动机制),第一轮次结束后(收到
S
6
S_6
S 6 ? 确认报文)
c
w
n
d
cwnd
c w n d 加倍,此时的
r
w
n
d
rwnd
r w n d 为5.5,发送窗口值为min[
c
w
n
d
,
r
w
n
d
cwnd,rwnd
c w n d , r w n d ]为2,接着开始第二轮传输,第二轮次结束后(收到
S
9
S_9
S 9 ? 确认报文)
c
w
n
d
cwnd
c w n d 加倍,为4,但此时的
r
w
n
d
rwnd
r w n d 为3.5,发送窗口值为min[
c
w
n
d
,
r
w
n
d
cwnd,rwnd
c w n d , r w n d ]为3.5 注意,这里只是改变了发送窗口搭载的最大数据长度,并没有改变
c
w
n
d
=
4
=
s
s
t
h
r
e
s
h
cwnd=4=ssthresh
c w n d = 4 = s s t h r e s h 接下来接收到的确认报文
r
w
n
d
=
6
rwnd=6
r w n d = 6
若继续使用慢启动机制,则
c
w
n
d
=
2
?
4
=
8
cwnd=2*4=8
c w n d = 2 ? 4 = 8 ,能发送的最大数据长度为
M
S
S
?
m
i
n
[
c
w
n
d
,
r
w
n
d
]
=
6000
MSS*min[cwnd,rwnd]=6000
M S S ? m i n [ c w n d , r w n d ] = 6 0 0 0 ; 若改用拥塞避免机制,则
c
w
n
d
=
4
+
1
=
5
cwnd=4+1=5
c w n d = 4 + 1 = 5 ,能发送的最大数据长度为
M
S
S
?
m
i
n
[
c
w
n
d
,
r
w
n
d
]
=
5000
MSS*min[cwnd,rwnd]=5000
M S S ? m i n [ c w n d , r w n d ] = 5 0 0 0
网络层
网络层模型
网络层是通信子网的最高层,对上层用户屏蔽了子网通信的细节,如子网类型、拓扑结构、子网数目,对上层提供一致的服务、统一的地址
实现端到端的网络连接,屏蔽不同子网技术的差异,向上层提供一致的服务 主要功能:
路由选择和转发 分组交换 屏蔽子网的差异,实现统一的网络编地址 主要采用无连接方式、分组交换方式(IP传输方式) 网络层提供的两种服务
电信虚电路 :面向连接的服务——通信双方之间的所有分组传输都是通过同一条虚电路传送 Internet数据报 :无连接的服务——通信双方的多次通信可以沿着相同/不同的路径传输 TCP/IP采用数据报服务
网际协议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地址:从主机号借用若干位作为子网号
I
P
?
a
d
d
r
e
s
s
:
:
=
<
n
e
t
?
i
d
>
,
<
s
u
b
n
e
t
?
i
d
>
,
<
h
o
s
t
?
i
d
>
IP \ address ::={<net-id>,<subnet-id>,<host-id>}
I P ? a d d r e s s : : = < n e t ? i d > , < s u b n e t ? i d > , < h o s t ? i d >
子网掩码对目的IP地址和子网掩码执行“按位与”操作,即得到子网(网络)地址 子网掩码是一个网络或一个子网的重要属性 构造超网
无分类编址CIDR
消除传统分类IP地址以及划分子网的概念 使用各种长度的网络前缀来代替分类地址中的网络号和子网号 IP地址从三级编址又回到了两级编址
I
P
?
a
d
d
r
e
s
s
:
:
=
<
p
r
e
f
i
x
>
,
<
h
o
s
t
?
i
d
>
IP \ address::={<prefix>,<host-id>}
I P ? a d d r e s s : : = < p r e f i x > , < h o s t ? i d > 斜线记法,又称为CIDR记法——IP地址后加一个斜线“/”后面跟网络前缀所占的位数 网络前缀都相同的连续IP地址组成“CIDR地址块” CIDR带来的好处
路由聚合==构成超网 减少路由表项 最长前缀匹配——网络前缀越长,其地址块就越小,因而路由就越具体(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——用于测试主机之间的连通性
Traceroute/Trancert——用于测试到另一台主机所经过的路由信息
ICMP 超时报告报文——TTL字段分别设置为1,2,3,…,直到到达目的主机(UDP报文)
路由算法及协议
路由器
组成
路由选择:按照路由选择协议工作,构建路由表 分组转发:交换结构 功能
运行路由协议,设置路由表 检测到拥塞时,合理丢弃IP分组 根据收到的IP分组的目的IP地址,将其转发到合适的输出线路上
IP组播
又称为多播,用于实现一点对多点的数据传输 组播的典型应用实例:网络视频服务 主机通过IGMP协议与组播路由器通信,加入/退出某个组播组
虚拟专用网VPN和网络地址转换NAT
网络地址转换NAT
专用地址
10.0.0.0~10.255.255.255 172.16.0.0~172.31.255.255 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_{1}
R 1 ? 收到其邻居路由器
R
2
R_{2}
R 2 ? 的距离矢量中包含的信息
<
n
e
t
1
,
16
>
<net1,16>
< n e t 1 , 1 6 > ,则可能得出的结论是
R
1
R_{1}
R 1 ? 不能经过
R
2
R_{2}
R 2 ? 到达
n
e
t
1
net1
n e t 1
数据链路层
概述
局域网互连
在物理层扩展局域网
使用中继器或集线器可以实现局域网在物理层的互联 集线器与中继器都不分割碰撞域
优点:实现网络扩展较方便,成本低 缺点碰撞域增大,碰撞发生概率增大,可能影响网络性能
在数据链路层扩展局域网
使用网桥可以实现局域网在数据链路层的互联——网桥工作在数据链路层
基本工作原理
根据MAC帧的目的地址对收到的帧进行转发 具有过滤帧的功能,当收到一个帧时,确定该帧的目的MAC地址,确定将该帧转发到哪个接口——并不向所有接口转发帧 网桥的优点
过滤通信量,增加吞吐量——各网段是独立的碰撞域 扩大了物理范围 提高了可靠性 可互联不同物理层、不同MAC子层和不同速率的局域网 (这可是桥诶!不同物理层怎么了,物理层的质对于网桥是透明的,不在桥的考虑范围内) 网桥的局限性
存储转发增加了时延 在MAC子层并没有流量控制功能 只适合用户数不太多(不超过几百个)和通信量不大的局域网
改进网桥?——多接口网桥,交换机
交换机工作在数据链路层,每个接口为一个网段(碰撞域),可以大幅提高网络性能 集线器由所有接口共享传输介质的带宽,而交换机为每个接口独享 带宽 交换机按照自学习算法建立转发表——根据接收到帧的源MAC地址 以及收到帧的接口 建立转发表 透明网桥还使用生成树算法 :避免帧无休止转发 虚拟局域网VLAN
在现有局域网基础上,通过将网络站点分组,构成若干逻辑上独立的虚拟局域网 用途
帧不会在两个VLAN之间自动转发,包括广播帧 IEEE802.1Q在以太网帧中扩展VLAN标记(tag),供交换机识别和转发
数据链路层采用后退N帧(GBN)协议,发送方已经发送了编号0-1的帧,当计时器超时时,若发送方只收到0,2,3号帧的确认,则发送方需要重发的帧数是4 :
A
C
K
n
ACK_{n}
A C K n ? 代表n号帧及n号帧之前的帧都已被正确接收
某局域网采用CSMA/CD协议实现介质访问控制,数据传输率为
100
M
b
/
s
100Mb/s
1 0 0 M b / s ,主机甲与主机乙的距离为
2
k
m
2km
2 k m ,信号传播速度是
200000
k
m
/
s
200000km/s
2 0 0 0 0 0 k m / s 请回答以下问题,并给出计算过程:
(1) 若主机甲和主机乙发送数据时发生冲突,则从开始发送数据时刻起,到两台主机均检测到冲突时刻为止,最短经过多长时间?最长经过多长时间?(假设主机甲和主机已发送数据时,其它主机不发送数据)
解析 :
甲乙间单向传输时延
τ
=
2
/
200000
=
10
μ
s
\tau=2/200000=10\mu s
τ = 2 / 2 0 0 0 0 0 = 1 0 μ s
最短:同时发送,中点处发生冲突,继而开始传送冲突信号——10
μ
s
\mu s
μ s
最长:甲发送的帧已经走过整段距离后,乙开始发送数据,此时冲突信号需传输整段到甲——
2
?
10
μ
s
2*10\mu s
2 ? 1 0 μ s
在一个采用CSMA/CD协议的网络中,传输介质是一根完整的电缆,传播速率为
1
G
b
p
s
1Gbps
1 G b p s ,电缆中的信号传播速度是
200000
k
m
/
s
200000km/s
2 0 0 0 0 0 k m / s 。若最小数据帧长度减少
800
b
i
t
800bit
8 0 0 b i t ,则最远的两个站点之间的距离至少需要
传输时延>2
τ
\tau
τ ,保证了在远端站点发送完数据之前能够检测到冲突 传输时延=数据包的大小/数据包的发送速率 传播时延=
τ
=
L
/
v
\tau=L/v
τ = L / v
设
C
S
M
A
/
C
D
CSMA/CD
C S M A / C D 局域网的数据传输速率为
1
G
p
s
1Gps
1 G p s ,信号传播速度为
200000
k
m
/
s
200000km/s
2 0 0 0 0 0 k m / s ,最小帧长度为
25000
b
i
t
25000bit
2 5 0 0 0 b i t ,则该局域网中两站之间的最远距离为?
操作系统
PV操作
同步与互斥问题
进程同步
互斥:在同一个时刻,只允许一个进程访问临界资源 临界资源:一次只允许一个进程使用的资源。
e.g 打印机、共享变量 假脱机打印(spooling)——把独占的临界资源共享访问 临界区:对临界资源进行访问的程序片段 同步机制应遵循的准则 :
空闲让进 忙则等待 有限等待 让权等待
基于忙等待的互斥方法
信号量机制(Semaphore )——安全地避免忙等
0
≤
S
0\leq S
0 ≤ S 表示当前可用的资源数目
S
=
1
S=1
S = 1 实现互斥:二元信号量
S
>
2
S>2
S > 2 实现同步:通用信号量
P
(
)
,
S
(
)
P(),S()
P ( ) , S ( ) 操作原语:原子操作不会被打断var
S
:
S
a
m
e
p
h
o
r
e
S:Samephore
S : S a m e p h o r e
P
(
)
P()
P ( ) 操作分配资源:
S
=
S
?
1
S=S-1
S = S ? 1 若
S
<
0
S<0
S < 0 则置进程为阻塞状态,并将该进程加入阻塞队列;否则继续执行。
V
(
)
V()
V ( ) 操作释放资源:
S
=
S
+
1
S=S+1
S = S + 1 ,若
S
≤
0
S\leq0
S ≤ 0 则从阻塞队列; 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) ;
}
信号量的使用
必须置一次且只能置一次初值——资源个数 只能通过
P
,
V
P,V
P , V 操作改变
基于信号量的方法
互斥量(Mutex):信号量值设置为1就是互斥量——用于实现对共享资源和代码的互斥访问;
0——解锁状态 1——加锁状态
基于管程的同步与互斥
管程(Monitor)
管程是一种高级同步原语 一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作,这组操作能够同步进程和改变管程中的数据 管程的实现:
同步机制使用:
wait signal
经典同步与互斥问题 #待补充
生产者消费者问题
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)
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
V ( roomEmpty) ;
reader:
P ( mutex) ;
readers= readers+ 1
if readers == 1 :
P ( roomEmpty)
V ( mutex) ;
read
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) ;
P ( roomEmpty) ;
wirte
V ( turnsitile) ;
V ( roomEmpty) ;
Reader:
P ( turnstile) ;
V ( turnstile) ;
P ( mutex) ;
readers = readers+ 1
if readers== 1 :
P ( roomEmpty)
V ( mutex) ;
read
P ( mutex) ;
readers = readers- 1
if readers== 0 :
V ( roomEmpty) ;
V ( mutex)
哲学家进餐问题
理发师问题
死锁
死锁发生的四个必要条件
互斥条件 保持和请求条件 不剥夺条件 环路等待条件 死锁发生的原因
竞争资源 并发执行的顺序不当 处理死锁的方法
死锁预防:破坏死锁产生的四个条件之一 死锁避免:在资源分配之前判断是否安全,仅当安全才进行分配——e.g 银行家算法 死锁检测 死锁解除 资源分配图——不可简化的资源分配图====>死锁(简化后还存在边),其中的有边进程为死锁进程 安全状态:程序存在一个序列
<
p
1
,
p
2
,
…
,
p
n
>
<p_1,p_2,…,p_n>
< p 1 ? , p 2 ? , … , p n ? > 能够顺利执行 银行家算法:
I/O系统
I/O设备
设备与控制器间接口
I/O控制技术
缓冲技术
假脱机技术SPOOLing
磁盘
组成:扇面、磁道(柱面)、扇区、磁头
磁盘与操作系统启动:
MBR(主引导扇区) DPT分区表(DPT) 分区引导扇区(DBR) 磁盘调度算法
常见算法
先来先服务 最短寻道时间 考虑磁道距离+磁头移动方向
扫描算法 循环扫描算法
提高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
补充:
码距<=>海明距离,码距越大,纠错能力越强,但数据冗余也越大,编码效率低。
文件系统
文件系统的基本概念
文件系统模型的三个层次
文件系统接口
命令行接口——用户和文件系统的交互接口 程序接口——用户程序和文件系统的接口;用户程序可以通过系统调用的形式来取得文件系统的服务 对象操作管理的软件集合:
对文件存储空间的管理 对文件目录的管理 用户将文件的逻辑地址转换为物理地址的机制 对文件读和写的管理; 对文件的共享和保护的功能 对象及其属性
文件名
文件名.扩展名
文件类型
文件的逻辑结构
提高检索效率、便于修改、降低文件存储代价
流式结构——单位是字节 记录式文件结构——单位是记录 树形结构
文件物理结构
在存储介质上的存放方式,表示了一个文件在文件存储介质上的位置、链接和编目方法
连续结构——容易出现磁盘碎片,适合变化不大的文件;方便顺序存取和随机存取(有序)
索引结构
索引文件:为每个文件建立逻辑块号与物理块号的对照表,称为文件的索引表;文件由数据文件和索引表构成。这种文件称为索引文件; 索引文件的操作:
在存储区中,索引文件占两个区——索引区+数据区 访问索引文件:先读取文件索引区,由逻辑块号查得物理块号;再访问物理块号获得所需信息 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DyZHiBer-1637284592613)(/Users/cleopatra/Library/Application Support/typora-user-images/image-20211104154433234.png)] 本身带来了系统开销:内外存空间+存取时间 串联结构
空间利用率高,顺序存取效率高;
随机存取效率低,可靠性不强(指针出错);链接指针占用一定空间
文件存取方式及存储介质
顺序存取、随机存取(提供读写位置) 存储介质:磁盘、磁带、光盘; 物理块(块block、簇cluster):数据存储、传输和分配的单位,存储设备通常划分为大小相等的物理块,统一编号
文件系统的实现方法
目录
由文件说明索引组成的用于文件检索的特殊文件 文件目录的主要内容:文件访问和控制信息(不包括文件内容) 文件属性信息,部分为用户可获取 基本信息:文件名;别名的数量 文件类型 地址信息(存放位置、文件长度) 访问控制信息:文件所有者、访问权限 使用信息:创建时间;最后一次读访问的时间+用户;最后一次写访问的时间+用户
目录分级
单级目录
二级目录
在根目录下,每个用户对应一个目录,在用户目录下是该用户的文件,而不再有下级目录。(适用于多用户系统)
多级目录
在较高的目录级,其目录表目为下一级目录名以及一个指向其目录的指针,在最后一级目录,这个指针指向文件的物理地址
特点:
层次清楚 可解决文件重名问题 查找速度快 目录级别太多会增加路径检索时间
目录的实现:
直接法:文件名+文件控制块 间接法:文件名+文件控制块的地址(索引号)
文件目录的查询:
顺序查询 Hash方法——“杂凑法”
便于共享的目录组织
文件的共享要求系统能提供一种方法:使存储空间内保存一份副本,而所有要共享该文件的用户可用相同的或不同的文件名来访问它
共享目录实例练习:
用户A有两个w文件
F
1
,
F
2
,
用
户
B
有
三
个
文
件
F_{1},F_{2},用户B有三个文件
F 1 ? , F 2 ? , 用 户 B 有 三 个 文 件
F
1
,
F
3
,
F
5
F_{1},F_{3},F_{5}
F 1 ? , F 3 ? , F 5 ? 其中用户A的文件
F
1
F_{1}
F 1 ? 与用户B的文件
F
1
F_{1}
F 1 ? 不是同一个文件,用户B的文件
F
3
F_{3}
F 3 ? 和用户A的文件
F
2
F_{2}
F 2 ? 是同一个文件。
请针对以上需求,给出一种目录组织方案。画图辅助说明。
【分析】:
A
?
?
?
?
F
1
A----F_{1}
A ? ? ? ? F 1 ? 与
B
?
?
?
?
F
1
B----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
s / t
一个二次间接索引能够索引的数据块数量 为
(
s
/
t
)
2
(s/t)^{2}
( s / t ) 2
故,文件最大为
(
10
+
s
/
t
+
(
s
+
t
)
2
)
?
s
(10+s/t+(s+t)^{2})*s
( 1 0 + s / t + ( s + t ) 2 ) ? s
进程与线程
进程的概念
进程的引入
进程是程序的一次执行,是程序及其数据,是在处理机上顺序执行时发生的活动 进程时系统进行资源分配和调度的一个独立单位 特征:动态性;并发性;独立性;异步性 进程的结构特征:
利弊:提高效率;空间开销、时间开销
进程的状态与控制
进程的三种基本状态
就绪状态:进程已获得除处理机外的所需资源,等待分配处理机资源,只要分配CPU就可以执行 执行状态:占用处理机资源;处于此状态的进程数目小于等于CPU的数目。在没有其他进程可以执行时,通常会自动执行系统的idle 进程(相当于空操作)背单词啦啊喂 阻塞状态:正在执行的进程,由于发生某种事件而暂时无法执行,便放弃处理机处于暂停状态 状态转换: 进程控制块
系统为每个进程定义了一个数据结构:进程控制块PCB
作用:进程创建、撤销;进程的唯一标志 ;限制系统进程数目
内容:
进程标识符:每个进程必须有一个唯一的标识符 程序和数据地址:把PCB与其程序和数据联系起来 现行状态:方便管理 现场保护区 互斥和同步机制 进程通信机制 优先级 资源清单 链接字 家族关系 组织方式:线性表、链接方式、索引方式
进程上下文切换
通常由调度器执行 保存进程执行断点 切换内存映射(页表基址、flush TLB) 陷入内核
CPU状态改变 由中断、异常、Trap指令(系统调用)引起 需要保存执行现场(寄存器、堆栈等) 系统调用
涉及进程从用户态到内核态的切换,这个时候的切换主要是寄存器上下文的切换,和通常所说的进程上下文切换不同 进程包含了两个概念:资源拥有者 和可执行单元
线程:将资源与计算分离,提高并发效率 进程与线程
现代操作系统将资源拥有者 称为进程
可执行单元 称为线程:CPU调度和分配的单位
引入线程的目的:
区分 CPU调度 调度 控制、协调多个进程对CPU的竞争
调度的类型
高级调度——接纳作业的数量、类型 中级调度——内外存交换 低级调度——微观调度,“进程/线程调度” 进程切换 时机
用户系统调用:来自程序的显式请求(如打开文件),该进程多半会被阻塞 陷阱:最末一条指令导致出错,会引起进程移至退出状态 中断:外部因素影响当前指令的执行,控制被转移至中断处理程序 步骤
保存处理器的上下文,包括程序计数器和其他寄存器 用新状态和其他相关信息更新正在运行进程的PCB 把进程移至合适的队列 选择另一个要执行的进程 更新被选中进程的PCB 从被选中进程PCB中重新装入CPU上下文 面向用户的调度性能准则
常用调度算法
先来先服务——按作业提交的先后顺序调度 最短作业优先——按预计执行时间调度 最短剩余时间优先——按完成时间调度 最高响应比优先——响应比
R
P
=
T
w
a
i
t
e
d
+
T
n
e
e
d
e
d
T
n
e
e
d
e
d
RP=\frac{T_{waited}+T_{needed}}{T_{needed}}
R P = T n e e d e d ? T w a i t e d ? + T n e e d e d ? ? 交互式系统的调度算法
时间片轮转 多级队列 多级反馈队列 内存管理 基本概念
地址空间:一个进程所能用于访问内存的地址集合 逻辑空间:虚拟地址,程序所使用的地址 物理地址:存储器地址 碎片
内碎片:分配给作业的存储空间中未被利用的部分(无法被整理,但在作业完成后会得到释放) 外碎片:系统中无法利用的空闲小分区(动态分区管理会产生外部碎片)外碎片是造成内存系统性能下降的主要原因,外部碎片可以整理后清除 消除外部碎片的方法:紧凑技术 紧凑技术
通过移动作业,把多个分散的小分区拼凑成一个大分区的方法——消除外部碎片 实现支撑:动态重定位,作业在内存中的位置发生了变化,这就必须对其地址加以修改或改变 分区的存储保护
界限寄存器方法
上下界寄存器方法 基址、限长寄存器(BR、LR)方法 存储保护键方法
存储块保护键——加锁;作业保护键——加钥匙 作业运行时检查钥匙与锁是否匹配,不匹配则系统发出保护性中断信号,停止作业运行 扩充内存的两种方法
覆盖:把一个程序划分为一系列功能相对独立的程序段,让执行时不要求同时装入内存的程序段组成一组(称为覆盖段),共享主存的同一个区域
交换:把暂时不用的某个或某些程序及其数据的部分或全部从主存移到辅存中去,以便腾出存储空间;接着把指定程序或数据从辅存读到相应的主存中,并将控制转给它,让其在系统上运行
增加并发运行的程序数目,并给用户提供适当的响应时间,编写程序时不影响程序结构 对换入和换出的控制增加处理机开销;程序整个地址空间都进行传送,没有考虑执行过程中地址访问的统计特性 分区式内存管理
内存的碎片问题:无论固定分区,还是可变分区都普遍存在的问题;内存紧缩 程序需要装入连续的内存空间 很难满足程序对内存空间的动态要求 很难找到一个绝对有效的内存分配/回收策略 内存利用率低 页式内存管理 基本思想 把一个逻辑地址连续的程序分散存放到若干不连续的内存区域中,并保证程序的正确执行
纯分页系统 不具备页面对换的分页存储管理方式,不支持虚拟存储器功能;在调度一个作业时,必须把它所有的页一次装到主存的页框内,如果当时页框数不足,则作业必须等待,系统再调度另外作业
没有外碎片,每个内碎片不超过页大小——平均内碎片大小为页大小的1/2 程序不必连续存放 便于改变程序占用空间的大小 但程序全部装入内存;有内碎片 基本概念
页:把作业的地址空间分成一些大小相等的片,称之为页面(page)或页,各页从0开始编号 存储块:把物理内存的存储空间也分为与页面大小相同的片,这些片称为存储块,或称为页框,同样从0开始编号 页表:为了便于在内存中找到进程的每个页面所对应的页框,分页系统中为每一个进程配置一张页表,进程逻辑地址空间中的每一页,在页表中都有对应的一个页表项 数量关系
页表
存放在内存中,属于进程的现场信息 用途
访问一个数据需要访存2次——页表一次+内存一次 页表的基址和长度由页表寄存器给出 页表查找(地址变换机构)
页表内容:页号对应存储块号——页号作为页表项的索引不需要以数据形式存储 地址转换机构
页表寄存器中页表长度与页号比较——越界中断 页表始址与
页
号
×
页
表
项
长
度
页号\times页表项长度
页 号 × 页 表 项 长 度 相加 根据相加结果访问对应页表项,得到的数据即为页号对应块号 块号与页内地址拼接得到物理地址 e.g 假设虚拟地址占8位,物理地址占10,每个页面的大小是64Bytes。问:
一共有多少个虚拟页面 一共有多少个物理页面(页框) 每个页表中有多少个页表项 假定页表是一个数组
{
2
,
5
,
1
,
8
}
\left\{2,5,1,8\right\}
{ 2 , 5 , 1 , 8 } ,请问对应虚拟地址0d241的物理地址是多少 解答
64
=
2
6
64=2^{6}
6 4 = 2 6 页内偏移占6位,即页号占
8
?
6
=
2
8-6=2
8 ? 6 = 2 位,共有
2
2
=
4
2^{2}=4
2 2 = 4 个虚拟页面同1.共有
2
10
?
6
=
16
2^{10-6}=16
2 1 0 ? 6 = 1 6 个物理页面 一共有
4
4
4 个虚拟页面——一个页表中有
4
4
4 个页表项
0
d
241
=
0
b
11
?
110001
0d241 = 0b11\ 110001
0 d 2 4 1 = 0 b 1 1 ? 1 1 0 0 0 1 对应页号为3,即其对应的页框号为8(页号从0开始),物理地址为
0
b
1000
?
110001
=
0
d
561
0b1000\ 110001=0d561
0 b 1 0 0 0 ? 1 1 0 0 0 1 = 0 d 5 6 1 页表的分级 一级页表
若逻辑地址空间很大,则划分的页较多,页表就很大,占用的存储空间大(要求页表为连续存储) 解决方法——多级页表
页表分级管理 动态调入页表:只将当前需用的部分页表项调入内存,其余的需用时再调入 二级页表
将页表再进行分页 ,离散地将各个页表页面存放在不同的物理块中,同时再建立一张外部页表用以记录页表页面对应的物理块号(页表的页表)
正在运行的进程,必须把外部页表(页表的页表)调入内存,而动态调入内部页表。只将当前所需的一些内层页表装入内存,其余部分根据需要再陆续调入
逻辑地址:
e.g 对于32位地址空间,页面大小为4K,如每个页表项占4个字节,则页表需占
4
M
B
4MB
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
0x3A
0 x 3 A 对应的物理地址
解答
页内偏移量:
8
=
2
3
8=2^{3}
8 = 2 3 ,3位
物理页框号:
128
/
8
=
16
=
2
4
128/8=16=2^{4}
1 2 8 / 8 = 1 6 = 2 4 ,4位
虚拟页号:
512
/
8
=
64
=
2
6
512/8=64=2^{6}
5 1 2 / 8 = 6 4 = 2 6 ,6位,逻辑地址
512
=
2
9
512=2^{9}
5 1 2 = 2 9 ,9位
页表项1 Bytes——一个页面存储8个页表项,一个页表最多管理8个页面——需要三位表示页号
推出一级页号占3位
0
x
3
A
=
0
b
000
?
111
?
010
0x3A=0b000\ 111\ 010
0 x 3 A = 0 b 0 0 0 ? 1 1 1 ? 0 1 0 推出一级页号为0,二级页号为7,页内偏移为2
查询步骤:
查找一级页表中的第0页表项,从中找到对应的二级页表的物理地址,读出相应的物理页框; 查找对应二级页表的第7页表项,从中找到对应的物理页框号; 上一步得到的物理页框的初始地址+偏移量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
(2*100ns+20ns)*0.2+(100ns+20ns)*0.8
( 2 ? 1 0 0 n s + 2 0 n s ) ? 0 . 2 + ( 1 0 0 n s + 2 0 n s ) ? 0 . 8 过程分析:不命中的情况下,首先访问TLB未命中(20ns),再访问内存内页表(100ns),最后根据页表内容访问内存内物理页(100ns);命中的情况下,首先访问TLB命中(20ns),再根据快表页框号访问对应物理页面(100ns) 哈希页表、反置页表
哈希页表:处理超过32位地址空间的常用方法:以虚拟页号作为哈希值 反置页表:按照物理地址排序,查找依据虚拟地址