首页 > 编程语言 >指数退避算法

指数退避算法

时间:2024-03-24 15:44:17浏览次数:31  
标签:exponential 指数 backOff 算法 backoff 退避

指数退避算法

指数退避算法

在查看Ants的源码时, 发现了一个关于自旋锁 spinlock的一个操作, 就此引入指数退避算法以及相关的实现.
互斥锁/自旋锁

示例代码

func (sl *spinLock) Lock() {
  backoff := 1
  for !atomic.CompareAndSwapUint32((*uint32)(sl), 0, 1) {
    // Leverage the exponential backoff algorithm, see https://en.wikipedia.org/wiki/Exponential_backoff.
    for i := 0; i < backoff; i++ {
      runtime.Gosched()
    }
    if backoff < maxBackoff {
      backoff <<= 1
    }
  }
}

解释

  1. 第3行, 尝试CAS获得锁, 如果获取成功, 直接返回
  2. 如果获取失败, 尝试等待 n 个时间片
  3. backOff << 1 , 重新尝试获取

重点

需要重点关注的是backOff的值, 会指数递增, 从 1 > 2 > 4 > 8 > 16 > ...

随着尝试次数的增加, 等待时间也会增长, 这就是指数递增.

参考文档

https://cloud.google.com/memorystore/docs/redis/exponential-backoff?hl=zh-cn

标签:exponential,指数,backOff,算法,backoff,退避
From: https://www.cnblogs.com/pDJJq/p/18092514/index-refund-algorithm-qx9rb

相关文章

  • 算法思想总结:位运算
                            创作不易,感谢三连支持!!一、常见的位运算总结标题  二、位1的个数.-力扣(LeetCode) 利用第七条特性:n&(n-1)干掉最后一个1,然后每次都用count++去统计,直到变成0classSolu......
  • 【算法双周赛】蓝桥杯【小白赛】
    坤星球【算法赛】问题描述坤星球是一颗十万光年之外的星球,相比于地球的时间流逝它的时间流逝更加缓慢,坤星球1年等于地球2.5年。现在问你,2024坤年等于地球多少年?注意:答案输出阿拉伯数字,不能为浮点数。输入格式本题为填空题,无需输入即可作答。输出格式输出一个数......
  • 机器学习算法那些事 | 使用Transformer模型进行时间序列预测实战
    本文来源公众号“机器学习算法那些事”,仅用于学术分享,侵权删,干货满满。原文链接:使用Transformer模型进行时间序列预测实战时间序列预测是一个经久不衰的主题,受自然语言处理领域的成功启发,transformer模型也在时间序列预测有了很大的发展。本文可以作为学习使用Transformer模......
  • raft算法和etcd代码解析-3.网络分区问题及其它
    网络分区问题网络分区导致选举永远无法达成共识,选举不断超时,任期号将不断增加为避免这个问题,candidate会探测网络环境以免发起无意义的竞选集群变更leader收到配置变更要求,会广播配置变更日志,日志包括新结点和老节点,在收到老节点的多数派认可后,leader后提交该请求在处理配置......
  • Floyd 判圈算法
    概述  Floyd判圈算法又称作是龟兔赛跑算法,就是快慢指针的应用,主要用于判断并找到环形链表的入口。做法是设置两个指针,一个快指针(兔子),一个慢指针(乌龟),快指针一次移动两个节点,慢指针一次移动一个节点。如果有环存在,它们第一次会在环上相遇,这时快指针移动到出发点,转换成慢指针(就是......
  • 蓝桥杯2017年第八届真题-分巧克力(二分算法)
    题目描述儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有N块巧克力,其中第i块是HixWi的方格组成的长方形。为了公平起见,小明需要从这N块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:1.形状是正方形,边长是整数2.大......
  • TSP旅行商问题——SA模拟退火算法,SA+GA组合算法(代码解释)
    SA代码直接用就行,成功率极高importrandomimportnumpyasnpimportmatplotlib.pyplotasplt#randomlygeneratethemapwithconstraintof[-100,100]defgen_cities(city_num,random_state=True):ifrandom_state:cities=(np.random.uniform(0......
  • java数据结构与算法刷题-----LeetCode75. 颜色分类
    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846文章目录1.双指针两次遍历2.三指针1.双指针两次遍历解题思路:时间复杂度O(......
  • java数据结构与算法刷题-----LeetCode451. 根据字符出现频率排序
    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846文章目录1.hash统计出现次数后排序2.桶排序1.hash统计出现次数后排序解题思路:时间复杂度O(......
  • Myelsa的Python算法之旅(高铁直达)
    博客个人主页(非风V非雨):https://blog.csdn.net/ygb_1024?spm=1010.2135.3001.5421Python-VBA编程500例算法清单(持续更新中)Myelsa的Python算法之旅创作清单算法明细对应网址博客个人主页(非风V非雨)非风V非雨-CSDN博客Myelsa的Python算法之旅(高铁直达)Myelsa的Python算法......