Two thread updating a variable without a lock

  • 1

    Two thread updating a variable (initial value of 0) without a lock, each thread uses a loop of 50 to increment a global variable. What is the minimum and maximum possible value you can get?

  • 1

    Min: 50
    Max: 100
    First, let me explain how cpu, which here mains arithmetic unit works.
    cpu have it's own cache, say cache1, cache2, cache3.
    For a c++ code like:
    Say i is stored in memory location Mem1, then
    1 Load data from Mem1 to cache1
    2 Load 1 to cache2
    3 calculate cache1+cache2, and assign result to cache3
    4 Put back cache3 data to Mem1

    For two threads T and S, we use T1_1,T1_2,T1_3,T1_4 and S1_1,S1_2,S1_3,S1_4 representing steps for each thread, then the sequences can be:
    which is 50.

  • 3

    The max should be 100 which is easy to understand. The min could be 50, which needs more explanation:

    First of all, each thread may copy the variable to a CPU cache while working on it, for performance purpose, then there are no guarantees that the value will be written back to memory before a thread is done with the increment operations. It is possible that both threads read 0 from the memory initially, then increment the value to 50 in different CPU caches, then write to memory one after another.

    Even though, each increment will be written back to memory, the min will still be 50 because of race condition. Similar reason, let's see an example:

    1. Originally the var is 0.
    2. Thread 1 reads the var, increments it to 1, but hasn't written it back to memory.
    3. Thread 2 reads the var, still 0, increments it to 1.
    4. Thread 1 writes back to memory, var is 1 now.
    5. Thread 2 writes back to memory, var is overwritten, but still 1.

    It is unlikely to happen every time, but it is possible that one thread overwrites the value the other thread just writes back, so min could be 50.

  • 2

    If the variable is marked volatile to force fresh reads before each increment, you can get a number significantly less than 50, since the reads and writes can happen out of order across threads. For example, imagine this sequence:

    [1] Thread 1: Read 0
    [2] Thread 2: Read 0
    [3] Thread 1: inc, write 1, read 1, inc, write 2
    [4] Thread 2: inc, write 1, read 1
    [5] Thread 1: read 1
    [6] Thread 2: inc, write 1, read 1, inc, write 2, inc, write 3
    [7] Thread 1: inc, write 2

    Thread 1 has done 3 increments, thread 2 has done 4 increments, and yet our observed value is only 2.

    In the most degenerate case, assuming reads & writes are atomic (no state tearing), the theoretical minimum is 2. In the example above, just imagine thread 1 ran to near completion in step [3], then thread 2 ran to completion, then thread 1 stomped the value at the very end with its last increment in step [7]

  • 0
    This post is deleted!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.