深夜食堂

计算机网络中进行通信的真正实体是位于通信两端主机中的进程，如何为运行在不同主机上的应用进程提供直接的通信服务是运输层的任务（端到端）。 - 因特网的运输层为应用层提供了面向连接的TCP和无连接的UDP两种不同的运输协议； ## 一、端口号、复用和分用 端口号：TCP/IP体系的运输层使用端口号来区分应用层的不同应用进程。 - 端口号用16比特表示，分为熟知端口号、登记端口号、短暂端口号； - 端口号只具有本地意义； 复用和分用： - 发送方：UDP复用/TCP复用、IP复用； - 接收方：IP分用、UDP分用/TCP分用； ## 二、UDP和TCP的对比 ## 三、TCP的流量控制和拥塞控制 #### 流量控制 如果发送方数据发送速度过快，接收方可能来不及接收，造成数据丢失，这时需要采用流量控制。 利用滑动窗口机制可以很方便地在TCP连接上实现对发送方的流量控制： - TCP接收方利用自己接收窗口的大小来限制发送方发送窗口的大小； - TCP发送方收到接收方的零窗口通知后，启动持续计时器，持续计时器超时后发送零窗口探测报文。 #### 拥塞控制 某段时间内，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络性能就要变差，称为拥塞。 TCP采用了四种拥塞控制算法：慢开始、拥塞避免、快重传、快恢复。 - 发送方维护拥塞窗口cwnd变量：其值取决于网络的拥塞程度（当发生超时重传，则视为发生网络拥塞），并动态变化，发送方将拥塞窗口作为发送窗口swnd； - 维护一个慢开始门限ssthresh：cwnd<ssthresh使用慢开始算法，cwnd>ssthresh时改用拥塞避免算法； - 慢开始：cwnd初始值为1，发送方每收到一个确认报文段，将cwnd加1，cwnd呈指数增长； - 拥塞避免：每个传输轮次结束后，cwnd加1，cwnd呈线性增长； - 当遇到拥塞（超时重传），则ssthresh重置为当前cwnd的一半，cwnd减少为1，重新开始执行慢开始算法； - 快重传：超时重传不一定由网络拥塞导致，错误启动慢开始算法，降低传输效率。快重传要求接收方收到数据立刻发送确认（包括失序报文段），发送方一旦收到3个连续的重复确认就将相应报文段立即重传，而不用等超时重传计时器超时。 - 快恢复：发送方收到3个重复确认，不启动慢开始算法，而是将ssthresh和cwnd调整为当前cwnd的一半，并开始执行拥塞避免算法； ## 四、TCP超时重传时间的选择 超时重传时间RTO的选择是TCP最复杂的问题之一。 加权平均往返时间RTTs： - RTTs1 = RTT1； - 新的RTTs = (1-α) × 旧的RTTs + α × 新的RTT样本（指数平滑法） - 已成为建议标准的α取值为0.125； 超时重传时间RTO： - 应略大于加权平均往返时间RTTs； - RFC6298建议使用的RTO = RTTs + 4 × RTTd，RTTd1 = RTT1 ÷ 2，新的RTTd = (1-β) x 旧的RTTd + β × |RTTs - 新的RTT样本|，β建议值为0.25； - 只要报文段重传了，就不采用其往返时间RTT样本，并把RTO增大一些（如×2）； ## 五、TCP可靠传输的实现 TCP基于以字节为单位的滑动窗口来实现可靠传输。 - 确认报文段包含接收窗口大小和希望接收到的起始字段，发送方据此构建发送窗口； - 发送方在未收到接收方的确认时，可将发送窗口内还未发送的数据全部发送出去； - 接收方只接收序号落入发送窗口内的数据； - TCP通常将不按序到达的数据先临时存放在接收窗口中，等字节流缺少的字节收到后，再按序交付用户进程； - TCP要求接收方必须有累积确认和捎带确认机制，不应过分推迟发送确认； - TCP通信是全双工通信； ## 六、TCP的运输连接管理 TCP运输连接有三个阶段： - “三报文握手”建立TCP连接； - “四报文挥手”释放TCP连接； #### TCP的连接建立 TCP连接建立要解决以下三个问题： - 使TCP双方能够确知对方的存在； - 使TCP双方能够协商一些参数（如窗口最大值）； - 使TCP双方能够对运输实体资源（如缓存大小、连接表中的项目等）进行分配； “三报文握手”过程： - TCP服务器进程创建传输控制块，进入监听状态； - TCP客户进程创建传输控制块，向TCP服务进程发送TCP连接请求报文段（SYN=1，seq=x，不能携带数据且需要消耗掉一个序号），进入同步已发送状态；（一握手） - TCP服务器进程发送TCP连接请求确认报文段（SYN=1，ACK=1，seq=y，ack=x+1，不能携带数据且需要消耗掉一个序号），进入同步已接收状态；（二握手） - TCP客户进程发送一个普通的TCP确认报文段（ACK=1，seq=x+1，ack=y+1，可携带数据，若未携带数据则不消耗序号），进入连接已建立状态；（三握手） - TCP服务器进程进入连接已建立状态； - 若改为两挥手，则可能因TCP连接请求超时重传导致错误； #### TCP的连接释放 “四报文挥手”过程： - TCP客户进程发送TCP连接释放报文段（FIN=1，ACK=1，seq=u，ack=v，不携带数据也要消耗掉一个序号），并进入终止等待1状态； - TCP服务器进程发送一个普通的TCP确认报文段（ACK=1，seq=v，ack=u+1），并进入关闭等待状态（未传输完的数据会继续传输，持续一段时间）； - TCP客户进程收到后进入终止等待2状态； - TCP服务器进程数据发送完后，发送TCP释放报文段（FIN=1，ACK=1，seq=w，ack=u+1），并进入最后确认状态； - TCP用户进程发送普通的TCP确认报文段（ACK=1,seq=u+1，ack=w+1），并进入时间等待状态; - TCP服务器进程进入关闭状态； - TCP客户进程在2MSL（MSL为最长报文段寿命，建议值为2min，一般更小）的时间后进入关闭状态； 保活计时器：TCP服务器进程每收到一次数据，就重新设置并启动保活计时器（2小时），保活计时器到时后，TCP服务器进程发送一个探测报文段，并每隔75秒发送一次。若连续10个探测报文段未被响应，则TCP服务器进程关闭连接。 ## 七、TCP报文段的首部格式 序号：指出本TCP报文段数据载荷的第一个字节的序号（循环）。 确认号：指出期望收到对方下一个TCP报文段的数据载荷的第一个字节的序号，同时也是对之前收到的所有数据的确认，只有ACK=1才有效； 数据偏移：即首部长度，指出TCP报文段的数据载荷部分的起始处距离TCP报文段起始处有多远，取值为首部字节数/4； 保留：保留今后使用，置为0； SYN：在TCP连接建立时用来同步序号； FIN：用来释放TCP连接； RST：用来复位TCP连接，RST=1时表明连接出现异常，需要释放并重新建立连接； PSH：PSH=1时，接收方会将该报文段尽快上交应用进程； 窗口：本报文段发送方的接收窗口； 校验和：检查TCP报文段（首部+数据载荷）是否出现误码； 紧急指针：URG=1时才有效，用来指明紧急数据的长度，紧急数据可插队到发送缓存的最前面； 选项：用来增加TCP功能： - 最大报文段长度MSS选项：数据载荷部分最大长度； - 窗口扩大选项：为了扩大窗口（提高吞吐率）； - 时间戳选项：用来计算RTT；用于处理序号超范围的情况，又称防止序号绕回PAWS； - 选择确认选项：实现选择确认功能；

IPv4地址：给因特网上的每一台主机或路由器的每一个接口分配一个在全世界范围内唯一的32比特标识符。 - 点分十进制表示方法：XXX.XXX.XXX.XXX； ## 一、历史发展 #### 1. 分类编制的IPv4地址 分类： - A类：0开头，8位网络号+24位主机号 - B类：10开头，16位网络号+16位主机号 - C类：110开头，24位网络号+8位主机号 - D类：1110开头，多播地址 - E类：1111开头，保留 注意事项： - 只有A； - 主机号为“全0”的地址是网络地址，主机号为“全1”的地址是广播地址， 不能分配给主机或路由器的各接口； - A类网络号0和127不可分配给主机或路由器的各接口； #### 2. 划分子网的IPv4地址 为新增网络申请新的网络号会浪费大量IP地址，借用主机号的一定位数来作为子网号，区分不同子网，以减少IP地址的浪费。 - 子网掩码：使用连续的比特1来对应网络号和子网号，连续的比特0来对应主机号。 - 将划分子网的IPv4地址与其相应的子网掩码进行逻辑与运算就可得到IPv4地址所在子网的网络地址； - 可划分的子网数量由子网号位数决定，每个子网可分配的IP地址数量由主机号位数决定； #### 3. 无分类编制的IPv4地址 无分类域间路由选择CIDR：消除了传统A/B/C类地址以及划分子网的概念。 - 使用“斜线记法”，即在IPv4地址后面加上斜线“/”，在斜线后面写上网络前缀所占的比特数量； 路由聚合（构造超网）：找共同前缀 - 网络前缀越长，地址块越小，路由越具体； - 最长前缀匹配：若路由器查表转发分组时发现有多条路可选，则选择网络前缀最长的那条； ## 二、IPv4地址的应用 #### 1. IPv4地址的应用规划 定长的子网掩码FLSM：使用同一个子网掩码来划分子网，所有子网的网络前缀长度一致，会造成IP地址的浪费。 变长的子网掩码VLSM：使用不同的子网掩码来划分子网，每个子网所分配的IP地址数量可以不同，更加灵活。 #### 2. IP数据报的发送和转发过程 主机发送IP数据报： - 首先判断目的主机是否与自己在同一个网络（子网掩码）； - 若在同一个网络，则直接交付，否则通过所在网络的默认网关（路由器）转发； 路由器转发IP数据报： - 首先检查IP数据报首部是否出错； - 根据IP数据报的目的地址在路由表中查找匹配的条目并通过相应接口转发； - 路由表：记录各接口网络地址及子网掩码，若子网掩码和目的地址相与等于对应网络地址，则通过相应接口转发； #### 3. 静态路由配置与路由环路问题 静态路由配置：用户或网络管理员使用路由i去相关指令给路由器人工配置路由表。一般用于小规模网络。 - 静态路由配置：目的网络+下一跳+类型（记录要到达目的网络下一跳需要转发到哪里）； - 默认路由：因特网中网络众多，可以添加目的网络地址0.0.0.0（视为网络前缀长度为0的网络地址），没有记录的网络地址都将从这里转发； - 特定主机路由：将特定主机的IP地址设为目的网络（视为网络前缀为32的网络地址）； - 转发时优先选择网络前缀最长的； 静态路由配置可能导致路由环路问题： - 配置错误：会导致死循环，可以设置生存时间TTL字段； - 聚合了不存在的网络：目的网络中实际IP地址数量小于最大IP地址数量，有部分IP地址不存在但会错误转发，可以添加黑洞路由解决； - 网络故障：可以将故障的IP地址设为黑洞路由； ## 三、路由选择协议 动态路由选择：路由器通过路由选择协议自动获取路由信息。 - 复杂开销大，能适应不同的网络状态，适用于大规模网络； - 特点：自适应、分布式、分层次。 分层次：内部网关协议IGP（IRP）和外部网关协议EGP（ERP）； 路由器的基本结构: - 路由表：收到路由报文后，会将信息记录到路由表中； - 根据路由表得到易于查找的转发表； - 收到数据分组后，则根据转发表查表转发； - 路由选择处理机存储路由表，还会周期性地给其他路由器发送自己所知道的路由信息； - 缓存区：输入/输出缓冲区用来暂存分组； #### 1. RIP RIP要求自治系统AS内的每一个路由器都要维护从它自己到AS内其他每一个网络的距离记录。 - 基于距离向量，使用“跳数”来衡量距离，距离等于16相当于不可达，因此只适用于小型互联网； - RIP认为好的路由就是“距离短”的路由，即通过路由器数量最少的路由（不考虑传输速率）。 - 当到达同一目的网络有多条距离相等的路由时，可以进行等价负载均衡； RIP基本工作过程： - 刚开始工作时，进知道自己到直连网络的距离为1； - 每个路由器仅和相邻路由器周期性地交换并更新路由信息； - 若干次交换更新后，每个路由器都知道到达本AS内各网络的最短距离和下一跳地址，称为“收敛”； RIP存在“坏消息传播得慢”的问题，可能导致路由环路。可以采用以下方法缓解： - 限制最大路径距离为15； - 触发更新：当路由表发生变化就立即发送更新报文； - 水平分割：让路由器记录收到某特定路由信息的接口，而不让同一路由信息再通过此接口反方向传送； #### 2.开放最短路径优先OSPF OSPF基于链路状态（即本路由器都和哪些路由器相邻以及相应链路的“代价”），使用了Dijkstra提出的最短路径算法SPF。 - “代价”用来表示费用、距离、时延、带宽等； - 每个使用OSPF的路由器都会产生链路状态通告LSA，包含直连网络的状态信息和邻居路由器的状态信息，并有一个“链路状态数据库LSDB”用于存储LSA； - LSA被封装在链路状态更新分组LSU中，采用洪泛法发送； - 各路由器的LSDB最终将达到一致； - 各路由器基于LSDB进行最短路径优先SPF计算，构建各自的路由表； OSPF有以下五种分组类型： - 问候分组：用来发现和维护邻居路由器的可达性； - 数据库描述分组：发送给邻居路由器； - 链路状态请求分组：发现链路状态缺失时向邻居路由器发送； - 链路状态更新分组：洪泛发送； - 链路状态确认分组：对链路状态更新分组的确认； OSPF在多点接入网络中路由器邻居关系的建立： - 选举指定路由器DR和备用的指定路由器BDR； - 所有的非DR/BDR只与DR/BDR建立邻居关系，非DR/BDR之间通过DR/BDR交换信息； 为了使OSPF能够用于规模很大的网络，OSPF把一个自治系统再划分为若干个更小的范围，叫做区域。 - 减少了整个网络上的通信量； #### 3. 边界网关协议BGP 用于自治系统之间的路由选择，工作原理如下： - 再配置BGP时，每个自治系统的管理员选择至少一个路由器作为该自治系统的“BGP发言人”； - 不同自治系统的发言人通过建立TCP连接交换路由信息，使用TCP连接交换路由信息的两个BGP发言人称为对方的邻站或对等站； - BGP发言人交换网络可达性的信息，并根据所采用的策略从收到的路由信息中找出到达各自治系统较好的路由，即构造不存在贿赂的自治系统连通图（树形结构）； BGP-4有以下四种报文： - OPEN报文：用来与相邻的另一个BGP发言人建立关系； - UPDATE报文：用来发送通过某一路由的信息，以及列出要撤销的多条路由； - KEEPALIVE报文：周期性地证实邻站的连通性； - NOTIFICATION报文：发送检测到的错误； ## 四、IPv4数据报的首部格式 版本字段：表示IP协议版本，如IPv4； 首部长度：取值为首部长度字节数/4； 区分服务字段：根据不同取值获得不一样的服务质量，一般不用； 总长度：IP数据报的字节数（包含首部）； 标识：属于同一个数据报的各分片数据报具有相同标识（按计数器）； 标志：3个比特，DF位表示允许分片，MF位表示后面是否还有分片，保留位为0； 片偏移：分片数据报的数据载荷部分从原数据报的第几个字节开始（字节位置除以8，第一个分片为0）； 生存时间TTL：每一跳-1，归零后丢弃，防止死循环； 协议：表明数据部分是何种协议数据单元（如TCP、UDP、ISPF、IPv6）； 首部检验和：用来检测首部在传输过程是否出现差错； 可选字段：用来支持排错、测量及安全等措施，很少使用； ## 五、网际控制报文协议 为了更有效地转发IP数据报和提高交付成功的机会，在网际层使用了网际控制报文协议ICMP。 - 主机或路由器使用ICMP来发送差错报告报文和询问报文； - ICMP报文被封装在IP数据报中发送； ICMP差错报告报文共有五种： - 终点不可达：当路由器或主机不能交付数据报时，就像源点发送终点不可达报文； - 源点抑制：当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文； - 时间超过：生存时间TTL字段减到0时发送； - 参数问题：通过首部检验和字段发现首部字段出现误码时发送； - 改变路由（重定向）：路由器把改变路由报文发送给主机，让主机知道下次应将数据报发给另外的路由器； ICMP询问报文有以下两种： - 回送请求和回答：用来测试目的站是否可达及了解有关状态； - 时间戳请求和回答：请某个主机或路由器回答当前的日期和时间，用来进行时钟同步和测量时间； ICMP应用举例 - 分组网间探测PING：用来测试主机或路由器之间的连通性； - 跟踪路由：用来测试IP数据报从源主机到达目的主机要经过哪些路由； ## 六、虚拟专用网VPN和网络地址转换NAT 虚拟专用网VPN：利用因特网作为本机构各专用网之间的通信载体。 - 各主机地址使用私有地址（只能作为本地地址）； - 加密并通过路由器发送； - 同一机构不同部门的内部网络构成的虚拟专用网称为内联网VPN，有时某些外部机构参加进来，称为外联网VPN； 网络地址转换NAT：使用NAT路由器将私有地址转换成全球IP地址，缓解IPv4地址空间即将耗尽的问题。 - 使用私有地址的主机发送IP数据报； - NAT路由器修改IP数据报的IP地址为全球IP地址； - 记录私有地址和全球IP地址的对应关系，并转发IP数据报； - 一个NAT路由器可连接多台主机； - NAT路由器接收外部发来的数据报，并根据转换表转发给主机； - 可以利用运输层的端口号和IP地址一起进行转换，这样一个全球IP地址就可以使多个拥有本地地址的主机同时和因特网上的主机进行通信，称为网络地址与端口号转换NAPT；

使用点对点信道的数据链路层： - 封装成帧、差错检测、可靠传输 使用广播信道的数据链路层： - 共享式以太网的媒体接入控制协议CSMA/CD； - 802.11局域网的媒体接入控制协议CSMA/CA； 数据链路层的互连设备 - 网桥和交换机的工作原理 - 集线器（物理层互连设备）与交换机的区别； ## 一、封装成帧 数据链路层给上层交付的协议数据单元添加帧头和帧尾使之成为帧。 - 帧头和帧尾包含有重要的控制信息； - 帧头和帧尾的作用之一就是帧定界； 透明传输：数据链路层对上层交付的传输数据没有任何限制。 - 面向字节的物理链路使用字节填充（或称字符填充）的方法实现透明传输（在与帧尾相同的数据段前插入转义字符）； - 面向比特的物理链路使用比特填充的方法实现透明传输（插入比特）； 最大传送单元MTU - 为了提高帧的传输效率，应该使帧的数据部分尽可能大一些； - 考虑到差错控制等多种因素，每一种数据链路层协议都规定了帧的数据部分的长度上限； ## 二、差错检测 比特差错：比特在传输过程中可能会产生差错，1可能会变成0，0也可能会变成1。 - 误码率BER：在一段时间内，传输错误的比特占总数的比例； - 可以使用差错检测码来检测数据传输过程中是否产生比特差错； #### 1. 奇偶校验 在待发送的数据后面添加一位奇偶校验位，表示数据中“1”个数的奇偶； - 偶数个位发生误码时无法检测出，效果不好； #### 2. 循环冗余校验CEC 收发双方约定好一个生成多项式G(x)，发送方基于待发送的数据和生成多项式计算出冗余码，将其添加到数据后面一起传输；接收方通过生成多项式来计算接受到的数据是否产生了误码。 收发双方具体处理如下： CRC有很好的检错能力，虽然计算复杂但非常易于用硬件实现，因此被广泛用于数据链路层。

检错码只能检测出错误，但不能定位并纠正错误。使用纠错码可以进行前向纠错，但开销较大，计算机网络中较少使用。 ## 三、可靠传输 数据链路层向上层提供的服务类型： - 不可靠传输：仅仅丢弃有误码的帧； - 可靠传输：想办法发送端发送什么，接收端就收到什么（无线链路误码率较高，需要可靠传输服务）； - 可靠传输服务不仅局限于数据链路层，其他各层均可选择实现；

接下来介绍三种可靠传输实现机制： #### 1. 停止-等待协议SW 原理： - 接收方接收到数据分组后，若检测无误发送则给发送方发送ACK分组，发送方收到后发送下一个数据分组；若发送方没有及时收到ACK分组则会超时重传； - 接收端检测到数据分组有误码时，将其丢弃并等待超时重传。但对于误码率较高的点对点链路，可以给发送方发送NKA分组； - 超时重传后，接收方可能会收到重复的数据分组，为了让接收方能够判断接收到的数据分组是否重复，需要给数据分组编号（1个比特）。 - 为了让发送方能够判断所受到的ACK分组是否是重复的，需要给ACK分组编号。数据链路层一般不会出现ACK分组迟到，所以该层可以不用给ACK分组编号。 - 数据链路层重传时间可以选为略大于平均往返时间； 信道利用率： #### 2. 回退N帧协议GBN 原理： - 使用n个比特给分组编序号，即序号0至2^n-1; - 发送窗口尺寸Wt取值：1<Wt<2^n-1，数据落在发送窗口外的分组不允许发送；接收串口的尺寸Wr = 1，数据落在接收窗口外的分组不允许接收，接收方只能按序接收正确到达的数据分组； - 累积确认：接收方不一定要对所有数据分组逐个发送确认，可通过发送ACKn表示需要n及以前的所有数据分组都已正确接收； - 当数据分组出现了差错，接收方会丢弃分组并发送当前接收成功的累积确认（比如序号5出现差错则会丢弃567并重复发送ACK4），发送方接收到重复的确认，就可以不等超时计时器超时就立刻重传567； #### 3. 选择重传协议SR 回退N帧协议GBN需丢弃误码数据分组及之后的所有分组，为了进一步提高性能，可设法只重传出现误码的数据分组。接收窗口尺寸Wr大于1，可以使接收方先收下失序到达但无误码的数据分组，等所缺分组收齐后再一并交送上层。 - 1<Wt<=2^{(n-1)，1<Wr<=Wt，若Wt>2}(n-1)会出现接收方无法分辨新旧数据分组的问题； - 无法使用累计确认； ## 四、点对点协议PPP 点对点协议PPP是目前使用最广泛的点对点数据链路层协议。 PPP协议为在点对点链路传输各种协议数据报提供了一个标准方法，主要由以下三部分构成： - 对各种协议数据报的封装方法（封装成帧） - 链路控制协议LCP，用于建立、配置以及测试数据链路的链接； - 一套网络控制协议NCPs，其中的每一个协议支持不同的网络层协议； 帧格式 实现透明传输的方法 - 面向字节的异步链路：字节填充法（插入转义字符）； - 面向比特的同步链路：比特填充法（插入比特0）； 差错检测 - CRC-CCITT = X^16+X12+X^5+1; - 使用PPP的链路层向上不提供可靠服务； ## 五、媒体接入控制 共享信道要注重考虑如何协调多个发送和接受站点对一个共享传输媒体的占有，即媒体接入控制MAC； - 静态划分信道：频分多址、时分多址、码分多址（不灵活，多用于物理层）； - 动态接入控制：受控接入(集中控制&分散控制，已淘汰)、随机接入； - 在有线领域，共享式局域网已被取代；但由于无线信道的广播天性，无线局域网仍然使用共享媒体技术； #### 1. 静态划分信道 信道复用：通过一条物理线路同时传输多路用户的信号。 频分复用FDM：所有用户同时占用不同的频带资源并行通信； 时分复用TDM：所有用户在不同的时间占用相同的频带宽度； 波分复用WDM：光的频分复用； 码分复用CDM - CDMA中，每一个比特时间再划分成m个短的间隔，成为码片； - 每个站被指派一个唯一的m bit码片序列，如果要发送1，则发送自己的m bit码片序列；如果要发送0，则发送m bit码片序列的二进制反码； - 码片序列挑选原则：①每个站码片必须各不相同；②每个站码片必须相互正交； #### 2. 随机接入CSMA/CD CSMA/CD：载波监听多址接入/碰撞检测，总线局域网使用。 - 多址接入MA：多个站连接在一条总线上，竞争使用总线； - 载波监听CS：每个站在发送帧之前先要检测一下总线上是否有其他站点在发送帧（“先听后说”）——在总线空闲96比特时间时发送； - 碰撞检测CD：每一个正在发送帧的站边发送边检测碰撞，一旦发现总线上出现碰撞，则立即停止发送，退避一段随机时间后再次发送； 争用期 最小帧长 - 当帧长太小时，争用期过短，已发送的帧可能在发送完毕后遭遇碰撞，而无法被检测出； - 因此以太网规定最小帧长为64字节，即512bit，如果发送的数据非常少则需要填充至64字节（包含帧头帧尾）； 最大帧长：最大长度1500字节（不包含帧头帧尾）； 退避时间计算方法：截断二进制指数退避算法 信道利用率：Smax = 1/(1+a)，a=τ/T0 - 要使帧长度尽量大，参数a尽量小，以提高信道利用率； 帧发送流程： 帧接收流程 #### 3. 随机接入CSMA/CA 载波监听多址接入/碰撞避免 CSMA/CA，802.11无线局域网使用。 - 无线网卡上实现碰撞检测对硬件要求非常高，且由于隐蔽站问题，碰撞检测意义不大； - 由于不可能避免所有碰撞，且无线信道误码率高，802.11标准使用了数据链路层确认机制（停止-等待协议）； - 802.11的MAC层标准定义了两种不同的媒体接入控制方式：分布式协调功能DCF（默认）和点协调功能PCF（较少使用）； 帧间间隔IFS：802.11标准规定，所有的站点必须在持续检测到信道空闲一段指定时间后才能发送帧。 - 高优先级帧需要等待的时间较短，低优先级帧需要等待的时间较长； - 短帧间间隔SIFS（28μs），是最短的帧间间隔，用来分隔一次对话的各帧； - DCF帧间间隔DIFS（128μs），在DCF方式中用来发送数据帧和管理帧； 工作原理： - 源站在检测到信道空闲后，经过DIFS间隔发送第一帧，目的站在接收到帧后，经过SIFS间隔反馈ACK； - 从源站发出第一帧到接收到ACK这段时间里，信道为忙；其他站在检测到信道空闲后，经过DIFS间隔并退避一段随机时间（以防止多个站点同时发送数据而产生碰撞）后，发送下一帧。 - 站点检测到信道为空，且所发送的数据帧不是成功发送完上一个数据帧之后立即连续发出的数据帧时，不用退避； 退避算法 - 站点为退避计时器设置一个随机退避时间，当退避计时器时间为0时，开始发送数据； - 当退避计时器还未减小到0信道又转为忙状态，则冻结计时器数值，等信道空闲，再经过DIFS后，继续启动计时器； - 在进行第i次退避时，在时隙编号{0,1,...,2^(i+2)-1}中随机选择一个（i达到6 时不再增加），乘以基本退避时间（一个时隙的长度）得到退避时间； 信道预约：为了尽可能减少碰撞的概率和降低碰撞影响，802.11标准允许对信道进行预约。 - 源站在发送数据帧前先发送一个短的控制帧，即请求发送RTS； - 目的站收到RTS，且媒体空闲，就发送一个响应控制帧，即允许发生CTS； - 源站收到CTS后，等待SIFS间隔即可发送数据帧； - 目的站正确收到数据帧并等待SIFS后，向源站发出ACK； - 其他各站收到CTS后就推迟接入无线局域网； - 如RTS帧发生碰撞，需执行算法重传RTS帧； - 一般数据帧发送时延往往大于传播时延，碰撞概率大；而RTS、CTS很短，碰撞的概率和开销很小； 虚拟载波监听：除RTS和CTS会携带通信需要持续时间，数据帧也能携带通信需要持续时间。 - 因此，站点只要监听到RTS帧、CTS帧或数据帧的任何一个，就能知道信道被占用的持续时间； - 虚拟载波监听机制能减少隐蔽站带来的碰撞问题； ## 六、MAC地址、IP地址和ARP协议 #### 1. MAC地址 当多个主机连接在同一个广播信道上，要想实现两个主机之间的通信，则每个主机都必须有一个数据链路层地址。 每个主机发送的帧必须携带标识发送主机和接收主机的地址，由于这类地址用于媒体介入控制（MAC），因此被称为MAC地址。 - MAC地址一般被固化在网卡（网络适配器）上，因此也被称为硬件地址和物理地址； - 一般情况下用户主机会有有线局域网适配器和无线局域网适配器，每个适配器都会有唯一的MAC地址，交换机和路由器拥有更多网络接口，所以一台设备会有多个MAC地址； IEEE 802局域网的MAC地址格式：xx-xx-xx-xx-xx-xx，每个x表示一个16进制数。 - OUI：前三个字节，分配给厂商； - 第一个字节的b0位表示单播0/多播1，b1位表示全球管理0/本地管理1； - 广播地址：FF-FF-FF-FF-FF-FF； - 单播：帧会发给广播域所有主机，只有MAC地址匹配才会接收，否则会丢弃； #### 2. IP地址 IP地址是因特网上的主机和路由器所使用的地址，用于标识两部分信息： - 网络编号：表示因特网上数以百万计的网络； - 主机编号：标识同一个网络上的不同主机或路由器接口； MAC地址不具备区分不同网络的功能，而IP地址具备。 数据包转发过程中IP地址和MAC地址的变化情况： - IP地址因填写源主机和目标主机； MAC地址因填写上一个发送接口的MAC地址和下一跳的地址； #### 3. ARP协议 地址解析协议ARP：通过IP地址找到MAC地址（不能跨网络使用）。 主机中存放ARP高速缓存表，记录各主机IP地址和MAC地址的对应关系。 - 若查找不到，则向广播地址发布ARP请求报文； - IP地址匹配的主机反馈ARP响应报文（单播）； - 将收到的响应报文记录到ARP高速缓存表中（动态，2分钟后会自动删除），下次可直接使用； ## 七、交换机 #### 1. 集线器HUB - 早期以太网的互连设备； - 工作在OSI体系结构的物理层； - 对接受到的信号进行放大、转发； - 使用集线器作为互联设备的以太网属于共享总线式以太网，集线器互连起来的所有主机共享总线宽带，属于同一个碰撞域和广播域； #### 2. 交换机SWITCH - 目前以太网中使用最广泛的互连设备； - 工作在OSI体系结构的数据链路层（也包括物理层）； - 根据MAC地址对帧进行转发（存储帧交换表，即接口号和MAC地址的对应表），因此单播帧只会发给目标主机； - 使用交换机作为互连设备的以太网是交换式以太网，交换机可以隔离碰撞域但不隔离广播域； #### 3. 交换机自学习和转发帧的流程 交换机根据帧交换表中查找到的MAC地址对帧进行转发，以太网交换机通过自学习算法逐渐建立帧交换表。 - 若帧交换表中没有源主机，则记录源主机MAC地址及对应接口； - 若帧交换表中没有目标主机，则向所有接口转发该帧（盲目泛洪），只有MAC地址对应的主机会接受该帧； - 若帧交换表有目标主机，则会直接将帧转发到对应接口； #### 4. 生成树协议STP 为了提高以太网可靠性，可以添加冗余链路。但冗余电路会形成网络环路，导致： - 广播风暴（广播帧在各交换机间反复转发）； - 主机收到重复广播帧； - 交换机的帧交换表震荡； 以太网交换机使用生成树协议STP，可以避免网络环路带来的各种问题： - 无论交换机之间采用怎样的连接，都使用生成树算法构建一个逻辑上没有环路的网络； - 交换机或网络物理拓扑发生变化时，进行生成树的重新计算； ## 八、虚拟局域网VLAN 随着交换式以太网规模扩大，广播域也会响应扩大，带来许多弊端： - 广播风暴（如一个ARP请求会传遍整个广播域）； - 难以管理和维护； - 潜在的安全问题； 使用路由器可以隔离广播域，但路由器成本较高，可以使用虚拟局域网VLAN达到类似的效果。 虚拟局域网是一种将局域网内的设备划分成与物理位置无关的逻辑组的技术，这些逻辑组具有某些共同的需求。 #### 实现方式 IEEE 802.1Q帧对以太网帧格式进行了扩展，插入4字节的VLAN标记。 - VLAN标记的最后12比特称为VLAN标识符VID，唯一地标志了以太网帧属于哪一个VLAN； - VID有效取值为1-4094； - 交换机收到普通的以太网帧时，会插入4字节的VLAN标记（打标签），转发802.1Q帧时，可能会删除VLAN标记（去标签）； 交换机端口类型： Access： - 一般用于连接用户计算机，只能属于一个VLAN； - 接收处理：一般只接收普通以太网MAC帧，根据端口PVID给帧打标签； - 发送处理：若帧中的VID与端口的PVID相等则“去标签转发”； Trunk： - 一般用于交换机之间或交换机与路由器之间，可以属于多个VLAN； - 接收处理：接收未打标签的帧，根据端口PVID打标签； - 发送处理：对VID等于PVID的帧去标签再转发，对于不等的帧直接转发； Hybird： - 既可连接用户计算机，也可以交换机之间或交换机和路由器互连，可以属于多个VLAN； - 发送处理方法：查看帧的VID是否在端口的“去标签”列表中，若存在则去标签再转发，否则直接转发（直接转发给用户计算机会因无法识别而被丢弃）； - 接收处理方法：同Trunk；

物理层考虑怎样才能在连接各计算机的传输媒体上传输数据比特流。 传输媒体： - 导引型传输媒体：双绞线、同轴电缆、光纤 - 非导引型传输媒体：微波通信 物理层协议主要任务： - 机械特性、电气特性、功能特性、过程特性 ## 一、传输媒体 分类： - 导引型传输媒体：双绞线、同轴电缆、光纤、电力线； - 非导引型传输媒体：无线电波、微波红外线、可见光； #### 导引型传输媒体 同轴电缆 - 基带同轴电缆和宽带同轴电缆 - 价格贵且布线不够灵活和方便。 双绞线 - 无屏蔽双绞线电缆和屏蔽双绞线电缆 - 绞合作用：①抵御部分来自外界的电磁波干扰；②减少相邻导线的电磁波干扰； 光纤 - 优点：①通信容量大；②传输损耗小，适合远距离传输；③抗雷电和电磁干扰性能好；④无串音干扰，保密性好；⑤体积小，重量轻； - 缺点：①割接需要专用设备；②光电接口价格较贵； 电力线 #### 非导引型传输媒体 无线电波 微波 - 直线传播； - 地面微波接力通信和卫星通信； 红外线 - 点对点无线传输，直线传输，传输速率低； 可见光 - 如LIFI通信，处于实验研究阶段； ## 二、传输方式 串行传输和并行传输 同步传输和异步传输 单向通信和双向通信 ## 三、编码和调制 基带信号（消息→数据→信号→基带信号） - 数字基带信号和模拟基带信号 - 数字信道和模拟信道 - 编码和调制 码元：在使用时间域的波形表示数字信号时，代表不同离散数值的基本波形； #### 常用编码 不归零编码与归零编码 - 不归零编码存在同步问题，不采用； - 归零编码每个码元传输结束后都要归零，编码效率低； 曼彻斯特编码 - 每个码元中间时刻发生跳变，跳变的方向表示0和1； 差分曼彻斯特编码 - 码元中间时刻的跳变表示时钟，码元开始处电平是否变化表示数据0和1； #### 调制方法 基本调制方法：调幅、调频、调相 混合调制：正交振幅调制QAM - 基本调制方法一个码元只能表示一个bit信息；可以采用混合调制方法，相位和振幅一起调制； - 如QAM-16，有12种相位，可以调制出16种码元，每种码元对应4个bit（2^4=16）； ## 信道的极限容量 信号通过信道会产生失真，产生失真的原因主要有： - 码元传输速率、信号传输距离、噪声干扰、传输媒体质量等； 奈式准则：在假定的理想条件下，为了避免码间串扰，码元传输速率是有上限的。 - 理想低通信道的最高码元传输速率 = 2W Baud = 2W码元/秒； - 理想带通信道的最高码元传输速率 = W Baud = W码元/秒； - W：信道带宽（单位：HZ）；Baud：波特，即码元/秒； - 码元传输速率又称波特率、调制速率、波形速率或符号速率，当1码元携带n比特信息量时，n*波特率=比特率； - 要想提高比特率，就必须设法使每一个码元能携带更多比特信息，需要采用多元制； - 实际信道所能传输的最高码元速率明显低于奈式准则的上限数值； 香农公式：带宽受限且有高斯白噪声干扰的信道的极限信息传输速率c： - c = W × log2(1+S/N) - W：信道带宽，s：信道内所传信号的平均功率，N：信道内的高斯噪声功率，S/N：信噪比（单位分贝）； - 要努力提高信道中的信噪比； - 实际所能达到的比公式的极限功率低不少；

Linux命令格式：command [-options] [parameter] command：命令本身 - -options：命令选项，可通过选项控制命令的行为细节； - parameter：命令参数，多数用于命令的指向目标等； ## 命令 #### ls命令 作用：列出目录下的内容 语法细节： ls [-a -l -h] [Linux路径] - [Linux路径]默认为HOME目录，即：/home/用户名； - -a表示all，即列出全部文件（包括隐藏的文件/文件夹）； - -l表示以列表（竖向排列）的形式展示内容，并展示更多信息； - -h以更加人性化的方式显示文件的大小单位（使用-h必须使用-l）； #### cd-pw命令 cd：切换工作目录 - 语法：cd [Linux路径]； - 无选项，默认参数为HOME； pwd：展示当前工作目录路径 - 无选项且无参数； #### mkdir命令 作用：创建新的目录（文件夹）。 语法：mkdir [-p] Linux路径 - 参数必填，即要创建的文件夹路径； - -p可选，表示自动创建不存在的父目录，适用于创建连续多层级的目录； - 创建文件夹需要修改权限，否则只能在HOME内操作； #### touch、cat、more命令 touch：创建文件 - 语法 touch Linux路径 - touch命令无选项，参数必填，表示要创建的文件路径 cat：查看文件内容 - 语法：cat Linux路径 more ：查看文件内容 - 语法：more Linux路径； - cat直接将内容全部显示出来，more支持翻页（空格翻页）； - 翻页界面按q退出； #### cp、mv、rm命令 cp：复制文件、文件夹 - 语法：cp [-r] 参数1 参数2； - -r可选，用于复制文件夹； - 参数1表示被复制的文件，参数2表示复制去的地方； mv：移动文件、文件夹 - 语法：mv 参数1 参数2； - 参数1表示被移动的文件，参数2表示移动去的地方； - mv test2.txt test3.txt可起到改名作用； rm：删除文件、文件夹 - 语法：rm [-r -f] 参数1 参数2 ...... 参数N； - -r用于删除文件夹； - -f表示强制删除（不会弹出提示）； - 参数1 参数2 ...... 参数N表示要删除的文件； - rm支持通配符“”; #### grep、wc命令 grep：从文件中通过关键字过滤文件行 - 语法：grep [-n] 关键字 文件路径 - 选项-n可选，表示在结果中显示匹配的行的行号； - 关键字表示过滤的关键字，带空格时需用双引号包围； - 文件路径可使用管道符获取； wc：统计文件的行数、单词数量等； - 语法：wc [-c -m -l -w] 文件路径 - -c表示统计bytes数量，-m表示统计字符数量，-l表示统计行数，-w表示统计单词数； - 文件路径可使用管道符获取 #### which、find命令 which：查看命令的程序文件存放位置 - 语法：which 要查找的命令，如which cd； find：搜索指定文件 - 语法一：find 起始路径 -name "被查找文件名"； - 语法二：find 起始路径 -size -10k查找小于10KB的文件，+10k可以查找大于10KB的； - 文件名支持通配符模糊匹配； #### echo、tail命令 echo：在命令行输出指定内容 - 语法：echo 输出的内容，如echo "hello world!"； tail：可以查看文件尾部内容，追踪文件的最新更改 - 语法：tail [-f -num] Linux路径； - -f表示持续追踪； - -num表示查看尾部多少行，默认为10； ## 特殊符号 特殊路径符 - “.”表示当前目录，如cd ./Desktop； - “..”表示上一级目录，如cd ../..表示切换到上二级目录； - “~”表示HOME目录，比如cd ~表示切换到HOME目录； 通配符 - “”表示通配符，即匹配任意内容（包括空）； - 如test表示匹配所有以test开头的内容，test*表示匹配所有包含test的内容； 管道符 -“|”表示将左边命令的结果作为右边的输入（参数）； - 可以嵌套； 重定向符 - “>”将左侧命令的结果覆盖写入到符号右侧文件中； - “>>”将左侧命令的结果追加写入到符号右侧文件中； - 如ls >> test.txt，可以将ls的输出结果追加写入test.txt中；

一、常见的计算机网络体系结构

OSI体系结构（法律上的国际标准） - 应用层、表示层、会话层、运输层、网络层、数据链路层、物理层 TCP/IP体系结构（事实上的国际标准） - 应用层：HTTP、SMTP、DNS、RTP - 运输层：TCP、UDP - 网际层：IP - 网络接口层 原理体系结构 - 应用层、运输层、网络层、数据链路层、物理层； - 适用于教学； ## 二、计算机网络体系结构分层 物理层：解决使用何种信号来传输比特的问题。 - 传输媒体 - 物理接口 - 信号 数据链路层：解决分组在一个网络（或一段链路）上传输的问题。 - 主机编址问题（如何标识网络中的各主机），如MAC地址 - 如何从信号所表示的一连串比特流中区分出地址和数据 - 协调各主机争用总线 网络层：解决分组在多个网络上传输（路由）的问题。 - 如何标识各网络以及网络中的各主机（网络和主机共同编址问题，如IP地址） - 路由器如何转发分组，如何进行路由选择 运输层：解决进程之间基于网络的通信问题。 - 如何解决进程之间基于网络的通信问题 - 出现传输错误时如何处理 应用层：解决通过应用进程的交互来实现特定网络应用的问题。 - 通过应用进程间的交互来完成特定网络的应用 ## 三、专用术语 #### 实体 任何可发送或接受信息的硬件或软件进程。 - 对等实体：接受双方相同层次中的实体 #### 协议 控制两个对等实体进行逻辑通信的规则的集合。 协议三要素：语法、语义、同步 - 语法：定义所交换信息的格式； - 语义：定义收发双方所要完成的操作； - 同步：定义收发双方的时序关系； #### 服务 服务：在协议控制下，两个对等实体间的逻辑通信使得本层能够向上一层提高服务。 - 协议是水平的，服务是垂直的； 服务访问点：在同一系统中相邻两层的实体交换信息的逻辑接口，用于区分不同的服务类型。 - 数据链路层：帧的“类型”字段； - 网络层：IP数据报首部中的“协议字段”； - 运输层：端口号 服务原语：上层使用下层所提供的服务是时必须与下层交换的命令。 协议数据单元PDU：对等层次之间传送的数据包 - 应用层：报文 - 运输层：TCP报文段或UDP用户数据报 - 网络层：IP数据报或分组 - 链路层：帧 - 物理层：比特流 服务数据单元SDU：同一系统内，层与层之间交换的数据包。 - 多个SDU可以合成为一个PDU；

一、速率

连接在计算机网络上的主机在数字信道上传送比特的速率。 - 又称比特率、数据率，单位b/s（bit/s，bps）； - 1kb/s = 10^3 b/s； #### 二、带宽 计算机网络中，带宽用来表示网络的通信线路所能传送数据的能力。 - 网络带宽表示在单位时间内从网络某一点到另一点所能通过的最高数据率。 - 单位：b/s #### 三、吞吐量 在单位时间内通过某个网络（或信道、接口）的数据量； - 受网络带宽或额定速率的限制； #### 四、时延 发送时延：源主机将分组发往传输线路； - 分组长度(b)/发送速率(b/s) - 发送速率 = min(网卡发送速率, 信道带宽, 接口速率) 传播时延：分组在链路上传输 - 信道长度(m)/电磁波传播速率(m/s) - 电磁波传播速率：自由空间3x10^{8m/s，铜线2.3X10}8m/s，光纤2.0X10^8m/s； 处理时延：路由器对分组进行存储转发； - 不方便计算； #### 五、时延带宽积 时延带宽积 = 传播时延X带宽 - 发送端连续发送数据时，发送的第一个比特到达终点时发送端已发送的比特数。 - 链路的时延带宽积又称以比特为单位的链路长度； #### 六、往返时间（RTT） 在很多情况下，因特网上的信息不仅仅是单方向传输，而是双向传输。 #### 七、利用率 信道利用率：信道有百分之几是被利用的（有数据通过）。 网络利用率：全网络的信道利用率加权平均。 - 信道利用率增大时，时延会增加； #### 八、丢包率 在一定时间范围内，传输过程中丢失的分组数量与总分组数量的比率，即分组丢失率。 - 可分为接口丢包率、结点丢包率、链路丢包率、路径丢包率、网络丢包率等； - 分组误码和网络拥塞会导致分组丢失； - 丢包率反映了网络的拥塞情况；

交换：按照某种方式动态地分配传输线路的资源 ## 电路交换 通过电话交换机接通电话线，使得不需要所有电话两两连接电话线。 - 建立连接（分配通信资源） - 通话（一直占用通信资源） - 释放连接（归还通信资源） 当使用电路交换来传送计算机数据时，其线路的传输效率往往很低。 ## 分组交换

报文交换

I/O设备：将数据输入/输出计算机的外部设备。 - 按使用特性可分为人机交互类设备、存储设备、网络通信设备； - 按传输速率可分为低速设备、中速设备、高速设备； - 按信息交换的单位可分为块设备、字符设备； I/O分为软件层和硬件层，软件层次从上至下可分为用户层软件、设备独立性软件、设备驱动软件、中断处理程序，每层会利用下层提供的服务，实现某些功能，并屏蔽实现的具体细节，向高层提供服务（封装）。 ## 一、IO控制器 I/O设备的电子部分，用于实现对I/O设备的控制。 #### 1. 主要功能 - 接受和识别CPU发出的指令（控制寄存器）； - 向CPU报告设备的状态（状态寄存器）； - 数据交换，暂存输入/输出的数据（数据寄存器）； - 地址识别（由I/O逻辑实现）； #### 2. 组成 - CPU和控制器之间的接口（实现控制器和CPU之间的通信）； - I/O逻辑（负责识别CPU发出的命令，并向设备发出命令）； - 控制器和设备之间的接口（实现控制器和设备之间的通信）； #### 3. 寄存器编址方式 内存映射I/O： - 控制器中的寄存器和内存统一编址； - 可以采用对内存进行操作的指令来对控制器进行操作； 寄存器独立编址： - 控制器中的寄存器独立编址； - 需要设置专门的指令来操作控制器； ## 二、I/O控制方式 用什么方式来控制I/O设备的数据读/写。 #### 1. 程序直接控制方式 - CPU干预频率高（等待IO完成过程需要不断轮询检查）； - 每次数据传送单位为一个字； - 实现简单，但CPU利用率低； #### 2. 中断驱动方式 - CPU发出I/O命令后可以做其他事，本次I/O完成后设备控制器发出中断信号； - CPU干预频率较低； - 每次数据传送单位为一个字； - CPU利用率明显 提升，但频繁中断会消耗大量CPU时间； #### 3. DMA方式 直接存储器存取，主要用于块设备的I/O控制。 - 数据传送单位是“块”； - 仅在传送一个或多个连续数据块的开始和结束时，才需要CPU干预； - I/O设备和内存间的数据传输不需要经过CPU； #### 4. 通道控制方式 CPU发出I/O命令后可以做其他事，通道会执行通道程序以完成I/O，完成后通道向CPU发出中断信号。 - CPU干预频率极低； - 每次读写一组数据块； - 实现复杂，需要专门的硬件； ## 三、假脱机技术 用户层软件：实现与用户交互的接口，向上提供方便易用的库函数。 假脱机技术又称SPOOLing技术，在用户层软件实现，是用软件的方式模拟脱机技术，达成脱离主机控制进行输入/输出的目的。 - 输入井和输出井：在磁盘中申请的临时存放输入/输出数据的空间； - 输入进程和输出进程：设备数据与输入/输出井的数据交互进程； - 输入缓冲区和输出缓冲区：内存中的缓冲区，输入/输出时的中转站； ## 四、设备的分配与回收 设备独立性软件：负责I/O调度、设备保护、设备分配与回收、缓冲区管理等； #### 1. 设备分配时应考虑的因素 设备的固有属性 - 独占设备、共享设备、虚拟设备； 设备分配算法 - 先来先服务、优先级高者优先、短任务有限等等； 设备分配中的安全性 - 安全分配方式：为进程分配一个I/O设备后就将进程阻塞； - 不安全分配方式； #### 2. 静态分配和动态分配 静态分配：进程运行前为其分配全部所需资源，运行接收后归还； 动态分配：进程运行过程中动态申请资源； #### 3.设备分配管理中的数据结构 设备控制表（DCT）：系统为每个设备配置一张DCT，用于记录设备情况； - 设备类型（打印机/扫描仪/键盘...）； - 设备标识符（物理设备名）； - 设备状态（空闲/忙碌/故障...）； - 指向设备控制器的指针（每个设备由一个控制器控制）； - 重复执行次数或时间（多次操作不成功后认为本次I/O失败）； - 设备队列的队首指针（指向正在等待该设备的进程队列，队列由进程PCB组成）； 控制器控制表（COCT）：每个设备控制器对应一张COCT，操作系统根据COCT的信息对控制器进行操作和管理； - 控制器标识符、控制器状态、指向通道表的指针、控制器队列队首/尾指针； 通道控制板（CHCT）：每个通道对应一张CHCT，操作系统根据CHCT的信息对通道进行操作和管理； - 标识符、状态、与通道连接的控制器表首址、通道队列队首/队尾指针； 系统设备表（SDT）：记录了系统中全部设备情况，每个设备对应一个表目； #### 4. 设备分配的步骤 - 根据进程请求的物理设备名查找SDT； - 根据SAT找到DCT，若忙碌则将进程PCB挂到设备等待队列； - 根据DCT找到COCT，若控制器忙碌则挂到控制器等待队列； - 根据COCT找到CHCT，若通道忙碌则搞到通道等等队列； - 可以建立逻辑设备名和物理设备名的映射机制，用户编程时只需提高逻辑设备名。

五、缓冲区管理

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区（常用）。 作用： - 缓和CPU与I/O设备速度不匹配的矛盾； - 减少对CPU的中断频率，放宽对CPU中断响应时间的限制； - 解决数据粒度不匹配的问题； - 提高CPU与I/O设备之间的并行性； #### 1. 单缓冲 在主存中为用户进程分配一个缓冲区（一个块）。 - 缓冲区数据非空时不能冲入数据，缓冲区为空时，需要充满才能把数据传出； #### 2. 双缓冲 在主存中为用户进程分配两个缓冲区。 #### 3. 循环缓冲 多个缓冲区链接成循环队列，in指针指向第一个缓冲区，out指针指向第一个满缓冲区； #### 4. 缓冲池 由系统中共用的缓冲区组成。 - 按使用状况分为空缓存队列、装满输入数据的缓冲队列、装满输出数据的缓冲队列； - 按实际功能不同设置四种工作缓冲区：用于收容输入数据的工作缓冲区（hin）、用于收容输出数据的工作缓冲区（hout）、用于提取输入数据的工作缓冲（cin）、用于提取输出数据的工作缓冲区（cout）

磁盘的表面由一些磁性物质组成，可以记录二进制数据。磁盘的表面被划分成一个个磁道，一个磁道又被分成一个个扇区，每个扇区就是一个磁盘块。 - 地址形式：可以用（柱面号、盘面号、扇区号）来定位一个磁盘块。在读取地址连续的磁盘块时，（柱面号，盘面号，扇区号）的写法能减少磁头移动； - 根据磁头是否可移动可分为固定头磁盘和移动头磁盘； - 根据盘片是否可换可分为固定盘磁盘和可换盘磁盘； ## 一、磁盘调度算法 一次磁盘读/写操作时间分为三部分： - 寻找时间：启动磁臂、移动磁头所花的时间； - 延迟时间：将目标扇区转到磁头下面所花的时间； - 传输时间：读/写数据花费的时间；

磁盘调度算法通过减少寻找时间来提高效率。 #### 1. 先来先服务（FCFS） - 按访问请求到达的先后顺序进行处理； #### 2. 最短寻找时间优先（SSTF） - 每次都优先响应距离磁头最近的磁道访问请求； - 贪心思想，无法保证整体最优； - 可能导致饥饿； #### 3. 扫描算法（SCAN） - 只有磁头移到最边缘磁道才会改变方向； - 对各个位置磁道响应频率不均匀； #### 4. 循环扫描算法（C-SCAN） - 磁头只在朝一个方向移动时才会响应请求； #### 5.LOOK和C-LOOK - LOOK算法是SCAN的改进，只要磁头移动方向上不再有请求就改变方向； - C-LOOK算法是C-SCAN的改进； ## 二、减少延迟时间的方法 交替编号：让编号相邻的扇区物理上不相邻； - 物理相邻的两个扇区无法连续读取； 错位命名：让相邻盘面的扇区编号错位；