CSMA/CD协议、二进制指数退避、自旋锁SpinLock

使用广播信道的数据链路层

• 总线的特点：采取的通信方式是“广播通信”[当一台计算机发送数据时，总线上的所有计算机都能检测到这个数据]。
• 为了在总线上实现一对一的通信，可以使每一台计算机的适配器拥有一个与其它适配器都不同的地址。[也就是我们常说的MAC地址]在发送数据帧时，在帧的首部写明接收站的地址。
• 仅当数据帧中的目的地与适配器ROM中存放的硬件地址一致时，该适配器才能接收这个数据帧。适配器会丢弃不是发送给自己的数据帧。
• 这样，具有广播特性的总线上就实现了一对一的通信。

---

为了通信的方便，以太网采取了以下两种措施：

---

采用较为灵活的无连接的工作方式

• 发送数据之前不需要建立连接。
• 适配器对发送的数据帧不进行编号，也不要求对方发确认帧。这样做可以使以太网工作起来非常简单，而局域网信道的质量很好，因通信质量不好产生的差错的概率是很小的。
• 因此以太网提供的服务是尽最大努力交付的，即不可靠的交付。当目的站收到有差错的数据帧时[例如利用CRC循环冗余检测进行差错检测时检测出错误]，就把帧丢弃，其它什么也不做。
• 由上层保证可靠性。对有差错帧是否需要重传则由高层决定。例如如果高层使用TCP协议，那么TCP就会发现丢失一些数据。于是经过一定时间之后，TCP就把这些数据重传给以太网进行重传。但以太网并不知道是重传帧，而是当作新的数据帧来发送。
• 总线上只要有一台计算机在发送数据，总线的传输资源就会被占用。同一时间只能允许一台计算机发送数据，否则各计算机之间就会相互干扰，使得所发送数据被破坏。因此，如何协调总线上各个计算机的工作就是以太网解决的一个重要问题。使用的协议就是"CSMA/CD"协议，意思是"载波监听多点接入/碰撞检测"[Carrier Sense Multiple Access with Collision Detection].

以太网发送的数据都使用曼彻斯特编码的信号。

• 二进制基带数字信号通常就是高低电压交替出现的信号。使用这种信号的最大问题就是当出现一长串的连1或者连0时，接收端就无法从收到的比特流中提取位同步[即比特同步信号]。
• 曼彻斯特编码的编码方法就是把每一个码元再分成两个相等的间隔。码元1是前一个间隔为低电压，后一个间隔为高电压。码元0则正好相反，从高电压到低电压[也可以采用相反的约定，1前高后低，0前低后高]。这样就保证每一个码元的正中间出现一次转换，接收端就是利用这种电压的转换把位同步信号提取出来。但是所占的频带宽度比原始基带信号增加了。
• [差分曼特斯特编码:遇0立即跳变，遇1延迟跳变]
  

CSMA/CD协议

CSMA/CD[Carrier Sense Multiple Access with Collision Detection]：载波监听多点接入碰撞检测
协议要点

• 多点接入。说明这是总线型网络，许多计算机以多点接入的方式连接在一条线上。协议的本质是"载波监听"和"碰撞检测"。
• 载波监听。发前先监听。就是用电子技术检测总线上有没有其他计算机也在发送。[其实总线上并没有什么"载波",这里只不过借用一下"载波"这个名词而已。]载波监听就是检测信道，这是个很重要的措施。不管在发送前，还是发送中，每个站都必须不停的检测信道。在发送前检测信道，是为了获得发送权。如果检测出已经有其他站在发送，则自己就暂时不允许发送数据，必须要等到信道变为空闲才能发送。在发送中检测信道是为了及时发现有没有其他站的发送和本站的发送的碰撞，称之为碰撞检测。
• 碰撞检测。边发边监听，即适配器边发送数据边检测信道上的信号电压的变化情况，以便判断自己在发送数据时其他站是否也在发送数据。当几个站同时在总线上发送数据时，总线上的信号电压变化幅度将会增大(互相叠加)。当适配器检测到的信号电压变化幅度超过一定的门限值，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞。所谓“碰撞”就是发生了冲突。因此碰撞检测也称为冲突检测。因此，任何一个正在发送数据的站，一旦发现总线上出现了碰撞，其适配器就要立即停止发送，免得继续进行无效的发送，白白浪费网络资源，然后等待一段随机时间后再次发送

---

每一个站在发送数据之前已经监听到信道为空闲，那么为什么还会出现碰撞呢？
因为电磁波在总线上总是以有限的速率传播。[也就是说电磁波的传播是有时延的]

• 电磁波在1km电缆的传播时延约为5us。
• 因此A向B发出的数据，在约5us后才能传送到B。换言之，B若在A发送的数据到达B之前发送自己的帧[因为这时B的载波监听检测不到A所发送的消息]，则必然在某个时间和A发送的帧发生碰撞。碰撞的结果是两个帧都变得无用。
• 在局域网的分析中，常把总线上的单程端到端传播时延记为t。A发送数据之后，最多要经过两倍的总线端到端的传播时延(2t)，或总线端到端往返传播时延就能检测出是否发生碰撞。
• 由于局域网上任意两个站之间的传播时延有长有短，因此局域网必须按照最坏情况设计，即取总线两端的两个站之间的传播时延[这两个站的距离最大]为端到端的传播时延。

• 在T=0时，A发送数据。B检测到信道为空闲
• 在T=t-m时(这里0<m<t)，A发送的数据还没有到达B时，由于B检测到信道是空闲的，因此B发送数据。
• 经过时间m/2后，即在T=t-m/2时，A发送的数据和B发送的数据发生了碰撞。但这时A和B都不知道发生了碰撞
• 在T=t时，B检测到发生了碰撞，停止发送数据
• 在T=2t-m时，A也检测到发生了碰撞，因而也停止发送数据。

A和B发送数据均失败，它们都要推迟一段时间再重新发送。每一个站在发送数据之后的一小段时间内，存在着遭遇碰撞的可能性。这一小段时间是不确定的，它取决于另一个发送数据的站到本站的距离。因此，以太网不能保证某一时间之内一定能够把自己的数据帧成功发送出去。以太网的这一特点称为发送的不确定性。如果希望在以太网上发生碰撞的机会很小，必须使整个以太网的平均通信量小于以太网的最高数据率。

从图中可以看出，最先发生数据帧的A站，在发送数据帧后至多经过时间2t就可以知道所发送的数据帧是否遭受了碰撞。这就是m->0的情况，因此以太网的端到端往返时间2t称为争用期，又称为碰撞窗口。

一个站在发送完数据后，只有通过争用期的"考验"，即经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

截断二进制指数退避

以太网使用截断二进制指数退避算法来确定碰撞后重传的时机。这种算法让发生碰撞的站在停止发送数据后，不是等待信道变为空闲后就立即再发送数据[这里的意思是说发生停止发送数据之后，不是立即检测信道是否空闲，而是等待一段随机时间之后再检测信道]，而是推迟(这就做退避)一个随机的时间。

如果几个发生碰撞的站都在监听信道，那么都会同时发现信道变成了空闲。如果大家都同时再重新发送，肯定又会发生碰撞。为了使各站进行重传时再次发生冲突的概率减小，具体退避算法如下：

• 协议规定了基本退避时间为争用期2t，具体的争用期时间为51.2us。对于10Mbit/s以太网，在争用期内可以发送512bit，即64字节。也可以说争用期是512比特时间。[1比特时间就是发送1比特所需的时间。所以这种时间单位与数据率密切相关。为了方便，也可以直接使用比特作为争用期的单位，争用期是512bit，即争用期是发送512bit所需的时间]
• 从离散的整数集合[0,1,…,($2^k$-1)]中随机取出一个数，记为r。重新检测信道是否空闲推后的时间就是r倍的争用期。其中k=Min[重传次数,10]
• 重传达16次仍不能成功(这表明同时打算发送数据的站太多，一致连续发生冲突)，则丢弃该帧，并向高层报告。
• 若连续多次发生冲突，就表明可能有较多的站参与征用信道。使用上述退避算法可以使重传需要推迟的平均时间随重传次数而增大[动态退避]，从而减小发生碰撞的概率，有利于整个系统的稳定。[增大重传时间，减小冲突概率，利于系统稳定性]
• 适配器每发送一个新的帧，就要执行一次CSMA/CD算法。适配器对过去的发生过的碰撞并无记忆功能。因此，当好几个适配器执行指数退避算法时，很可能有某一个适配器发送的新帧能够碰巧立即成功地插入信道中，得到了发送权，而已经推迟好几次发送的站，很可能不巧，还要继续执行退避算法，继续等待。

最短帧长

• 现在考虑一种情况。某个站发送了一个很短的帧，但在发送完毕之前并没有检测出碰撞。假定这个帧在继续向前传播到达目的站之前和别的站发送的帧发送了碰撞，因而目的站将收到有差错的帧[会将其丢弃]。可是发送站却不知道这个帧发生了碰撞，因而不会重传这个帧。
• 为了避免上述情况的发生，以太网规定了一个最短帧长64字节，即512bit。如果要发送的数据非常少，必须加入一些填充字节，使帧长不小于64字节。对于10Mbit/s以太网，发送512bit的时间需要51.2us，也就是争用期。
• 以太网在发送数据时，如果在争用期没有发生碰撞，那么后续发送的数据一定不会发生冲突。如果发生碰撞，一定是在发送的前64字节之内。
• 由于一检测到冲突就立即中止发送，这时已经发送出去的数据一定小于64字节，凡长度小于64字节的帧都是由于冲突而异常中止的无效帧，只要收到了这种无效帧，就应当立即丢弃。

强化碰撞

• 当发送数据的站一旦发现发生了碰撞，除了立即停止发送数据外，还要再继续发送32比特或48比特的人为干扰信号，以便让所有用户都知道现在已经发生了碰撞。[强化碰撞]
• 以太网规定了帧间最小间隔为9.6us，相当于96比特时间。这样做是为了使刚刚收到数据帧的站的接收缓存来得及清理，做好接收下一帧的准备

CSMA/CD协议要点

• 准备发送:适配器从网络层获得一个分组，加上以太网的首部和尾部，组成以太网帧，放入适配器的缓存中。但在发送之前，必须先检测信道。
• 检测信道:若检测到信道忙，则应不停的检测，一直等待信道转为空闲。若检测到信道空闲，并在96比特时间内信道保持空闲[保证帧最小间隔],就发送帧。
• 在发送过程中仍不停地检测信道，即网络适配器要边发送边监听。一下有两种情况:
• 1.发送成功:在争用期内一直未检测到碰撞。这个帧肯定能发送成功。发送完毕后，什么也不做，回到第一步
• 2.发送失败:在争用期内检测到碰撞。立即停止发送数据，按规定发送人为干扰信号。适配器接着执行指数退避算法，等待r倍争用期后，回到第二步，继续检测信道。若重传16次仍不能成功，停止重传向上报告错误。

发送流程总结为:
发前先听，边发边听，冲突停发，随即等待一段时间重发

PS:以太网每发送完一帧，会保留该帧地副本，以便在争用期检测出碰撞之后，重传该帧。

传播时延和传输时延

易混淆的两个概念是传播时延和传输时延。

• 传输时延是指一个站点从开始发送数据帧到数据帧发送完毕所需要的全部时间[发送时延]
• 传播时延是指发送端开始发送数据到接收端收到数据所需要的全部时间。
• 传输时延和发送数据帧大小有关，而传播时延和传输距离相关。

CSMA/CD与CSMA/CA

Carrier Sense Multiple Access with Collision Avoidance[载波监听多点接入/碰撞避免]
在802.11?线局域?协议中，冲突的检测存在?定的问题，这个问题称为"Near/Far"现象，这是由于要检测冲突，设备必须能够?边接受数据信号?边传送数据信号，?这在?线系统中是?法办到的。鉴于这个差异，在802.11中对CSMA/CD进?了?些调整，采?了新的协议CSMA/CA。

CSMA/CA利?ACK信号来避免冲突的发?，也就是说，只有当客户端收到?络上返回的ACK信号后才确认送出的数据已经正确到达?的。
CSMA/CA协议的?作流程分为两个分别是:

• 发送数据前，先监听媒体状态，媒体空闲且维持?段时间后，发送数据。
• 送出数据前，先送?段??的请求传送报?(RTS : Request to Send)给?标端，等待?标端回应 CTS:Clear to Send 报?后，才开始传送。利?RTS-CTS握?(handshake)程序，确保接下来传送资料时，不会被碰撞。同时由于RTS-CTS封包都很?，让传送的?效开销变?。
  　　　　
  RTS/CTS 通信访问方式是可选的。在这种方式下，发送站在正式发送数据前需要对信道进行预约，预约成功后才能发送数据。这种方式又被称为“四次握手”机制，主要用于解决 CSMA/CA 协议基本访问方式中存在的隐蔽站问题和暴露站问题。

CSMA/CA与CSMA/CD的区别

• 两者的传输介质不同,CSMA/CD?于总线式以太?,?CSMA/CA则?于?线局域?802.11a/b/g/n等等
• 载波检测?式：因传输介质不同，CSMA/CD与CSMA/CA的检测?式也不同。CSMA/CD通过电缆中电压的变化来检测，当数据发?碰撞时，电缆中的电压就会随着发?变化；?CSMA/CA采?能量检测（ED）、载波检测（CS）和能量载波混合检测三种检测信道空闲的?式。
• 信道利?率?较：CSMA/CA协议信道利?率低于CSMA/CD协议信道利?率。但是由于?线传输的特性，在?线局域?不能采?有线局域?的CSMA/CD协议。信道利?率受传输距离和空旷程度的影响，当距离远或者有障碍物影响时会存在隐藏终端问题，降低信道利?率。

具体最?的信道利?率与传输速率有关。在IEEE802.11b?线局域?中，在1Mb/s速率时最?信道利?率可到90%，?在11Mb/s时最?信道利?率只有65%左右。

练习题

1.数据链路(逻辑链路)与链路(物理链路)有何区别?电路接通了与数据链路接通了的区别何在?[3-01]

• 数据链路与链路的区别在于数据链路除链路外，还必须有一些必要的规程来控制数据的传输，因此，数据链路比链路多了实现通信规程所需要的硬件和软件。“电路接通了"表示链路两端的节点交换机已经开机了，物理连接已经能够传送比特流了，但是，数据传输并不可靠，在物理连接基础上，再建立数据链路连接，才是"数据链路接通了”，此后，由于数据链路连接具有检测，确认和重传功能，才使不太可靠的物理链路变成可靠的数据链路，进行可靠的数据传输；当数据链路断开连接时，物理电路连接不一定跟着断开连接

2.网络适配器的作用是什么?网络适配器工作在哪一层?[3-03]

• 适配器(即网卡)来实现数据链路层和物理层这两层的协议的硬件和软件网络适配器工作在TCP/IP协议中的网络接口层(OSI中的数据链路层和物理层)

3.假定1km长的CSMA/CD网络的数据率为1Gbit/s。设信号在网络上传播速率为200 000km/s。求能够使用此协议的最短帧长。[3-20]

4.假定在使用CSMA/CD协议的10Mbit/s以太网中某个站在发送数据时检测到碰撞，执行退避算法时选择了随机数r=100。试问这个站需要等待多长时间才能再次发送数据?如果是100Mbit/s的以太网呢?[3-22]

5.假设站点A和B在同一个10Mbit/s以太网网段上。这两个站点之间的传播时延为225比特时间。先假定A开始发送一帧，并且在A发送结束之前B也发送一帧。如果A发送的是以太网容许的最短的帧，那么A在检测到和B发生碰撞之前能否把自己的数据发送完毕?换言之，如果A在发送完毕之前没有检测到碰撞，那么能否肯定A所发送的帧不会和B发送的帧发生碰撞?(提示:在计算时应当考虑到一个以太网帧在发送到信道上时，在MAC帧前面还要增加若干字节的前同步码和帧定界符)[3-24]

6.在上题中的站点A和B在t=0时同时发送了数据帧。当t=225比特时间，A和B同时检测到发生了碰撞，并且在t=225+48=273比特时间完成了干扰信号的传输。A和B在CSMA/CD算法中选择不同的r值退避。假定A和B选择的随机数分别是r_A=0和r_B=1。试问A和B各在什么时间开始重传其数据帧?A重传的数据帧在什么时间到达B?A重传的数据会不会和B重传的数据再次发生碰撞?B会不会在预定的重传时间停止发送数据?[3-25]

7.以太网上只有两个站，它们同时发送数据，产生了碰撞。于是按照截断二进制指数退避算法进行重传。重传次数记为i，i=1,2,3,…。试计算第1次重传失败的概率、第2次重传失败的概率、第3次重传失败的概率，以及一个站成功发送数据之前的平均重传次数I。[3-26]

自旋锁

利用"指数退避算法"用go语言模拟出一把"spin lock"
首先简单介绍一下什么是自旋锁:自旋锁是一种乐观锁，用CAS(Compare And Swap)操作实现；自旋锁是为保护共享资源而提出的一种锁机制。任何时候只能有一个请求者占有资源，如果资源已经被占用，其余请求者就一直循环在那里看该自旋锁的保持者是否已经释放了锁，虽不会产生上下文的切换但是会一直占用CPU资源。

对于Go语言的GMP调度模型，调度时机分为:“主动调度”、“被动调度”、“抢占调度”;

• 主动调度就是主动让出自己的调度权，通过"runtime包下的Gosched方法实现"
• 被动调度就是由于IO操作或者系统调用而被阻塞，被迫让出调度权
• 抢占调度就是协程执行的时间或者系统调用时间过长而被另外的协程抢占调度权

介绍完一些前置知识，接下来详细解释一下"spin lock"的实现，[下图中贴出来的代码图是截取github上一个协程池项目ants中实现的spin lock，使用的是改编版本的指数退避算法]。

• spin lock是通过CAS操作实现的，spin lock的本质是一个uint32类型的数值，当其值为0时代表未上锁，其值为1时代表已上锁。
• 对于Unlock操作就是通过原子操作将spinlock对应的数值存储为0
• 对于Lock操作就是通过CAS操作在spinlock对应数值为0的前提下变为1[也就是一个未被上锁的锁才有资格被上锁]。通过runtime.Gosched()进行退避[等待一段时间才重新获取锁]，具体的退避流程如下:
  1.首先规定退避的最大上限是16次，每次退避完后以2倍的速度增长退避次数
  2.第一次获取锁失败，进入for循环通过runtime.Gosched()主动退避backoff次，如果backoff没有达到上限就将backoff左移一位也就是变为原先的2倍，为下次退避做准备。
  3.本质就是通过不断让出调度权加长锁等待的时间，减小锁冲突的概率，提高整体性能

参考博客

1.计算机网络第七版课后题答案
2.github项目协程池ants
3.计算机网络谢希仁第七版