doudao1950 2018-04-03 12:51
浏览 83

如何实现“ i ++和i> = max”? 0:i”仅在Go中使用原子

only use atomic implement the follow code:

const Max = 8
var index int
func add() int {
    index++
    if index >= Max {
        index = 0
    }
    return index
}

such as:

func add() int {
    atomic.AddUint32(&index, 1)
    // error: race condition 
    atomic.CompareAndSwapUint32(&index, Max, 0)
    return index
}

but it is wrong. there is a race condition. can be implemented that don't use lock ?

  • 写回答

2条回答 默认 最新

  • dongxunhua2054 2018-04-03 13:22
    关注

    Solving it without loops and locks

    A simple implementation may look like this:

    const Max = 8
    
    var index int64
    
    func Inc() int64 {
        value := atomic.AddInt64(&index, 1)
        if value < Max {
            return value // We're done
        }
    
        // Must normalize, optionally reset:
        value %= Max
        if value == 0 {
            atomic.AddInt64(&index, -Max) // Reset
        }
        return value
    }
    

    How does it work?

    It simply adds 1 to the counter; atomic.AddInt64() returns the new value. If it's less than Max, "we're done", we can return it.

    If it's greater than or equal to Max, then we have to normalize the value (make sure it's in the range [0..Max)) and reset the counter.

    Reset may only be done by a single caller (a single goroutine), which will be selected by the counter's value. The winner will be the one that caused the counter to reach Max.

    And the trick to avoid the need of locks is to reset it by adding -Max, not by setting it to 0. Since the counter's value is normalized, it won't cause any problems if other goroutines are calling it and incrementing it concurrently.

    Of course with many goroutines calling this Inc() concurrently it may be that the counter will be incremented more that Max times before a goroutine that ought to reset it can actually carry out the reset, which would cause the counter to reach or exceed 2 * Max or even 3 * Max (in general: n * Max). So we handle this by using a value % Max == 0 condition to decide if a reset should happen, which again will only happen at a single goroutine for each possible values of n.

    Simplification

    Note that the normalization does not change values already in the range [0..Max), so you may opt to always perform the normalization. If you want to, you may simplify it to this:

    func Inc() int64 {
        value := atomic.AddInt64(&index, 1) % Max
        if value == 0 {
            atomic.AddInt64(&index, -Max) // Reset
        }
        return value
    }
    

    Reading the counter without incrementing it

    The index variable should not be accessed directly. If there's a need to read the counter's current value without incrementing it, the following function may be used:

    func Get() int64 {
        return atomic.LoadInt64(&index) % Max
    }
    

    Extreme scenario

    Let's analyze an "extreme" scenario. In this, Inc() is called 7 times, returning the numbers 1..7. Now the next call to Inc() after the increment will see that the counter is at 8 = Max. It will then normalize the value to 0 and wants to reset the counter. Now let's say before the reset (which is to add -8) is actually executed, 8 other calls happen. They will increment the counter 8 times, and the last one will again see that the counter's value is 16 = 2 * Max. All the calls will normalize the values into the range 0..7, and the last call will again go on to perform a reset. Let's say this reset is again delayed (e.g. for scheduling reasons), and yet another 8 calls come in. For the last, the counter's value will be 24 = 3 * Max, the last call again will go on to perform a reset.

    Note that all calls will only return values in the range [0..Max). Once all reset operations are executed, the counter's value will be 0, properly, because it had a value of 24 and there were 3 "pending" reset operations. In practice there's only a slight chance for this to happen, but this solution handles it nicely and efficiently.

    评论

报告相同问题?

悬赏问题

  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥15 python天天向上类似问题,但没有清零
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?