CAS, Level-based API and Agile

Posted on Edited on

semaphore

Let’s take a look at an over-simplified version of Golang runtime’s semaphore lock() implementation. If you’re interested, see the original version here.

Before you start, let’s make some assumptions to ease your understanding:

  1. a mutex l is an unsigned integer;
  2. it’s unlocked by default, having value 0;
  3. it’s locked by setting its value to 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func lock(l *mutex) {
	// Speculative grab for lock.
	if atomic.Casuintptr(&l.key, 0, locked) {
		return
	}

	// On uniprocessor's, no point spinning.
	// On multiprocessors, spin for ACTIVE_SPIN attempts.
	spin := 0
	if ncpu > 1 {
		spin = active_spin
	}
Loop:
	for i := 0; ; i++ {
		v := atomic.Loaduintptr(&l.key)
		if v&locked == 0 {
			// Unlocked. Try to lock.
			if atomic.Casuintptr(&l.key, v, v|locked) {
				return
			}
			i = 0
		}
		if i < spin {
			procyield(active_spin_cnt)
		} else if i < spin+passive_spin {
			osyield()
		} else {
			if v&locked != 0 {
				// Queued. Wait.
				semasleep(-1)
				i = 0
			}
		}
	}
}

What happens in the lock function can be summarized in the following points:

  1. if it is unlocked, grab it by setting it to 1;
  2. otherwise, we do some active spinnings to wait;
  3. before we start the spinning, if it is unlocked, grab it by setting it to 1;
  4. spin if we haven’t spent too much time actively waiting;
  5. otherwise, go to sleep;
  6. once wake up, start over from step 1;

Compare and Set.

Now, let me try to write some ugly pseudo code to summarize.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
run() {
beginning:
   # Make observations
   o := observe()
   # Act based on observations and make new proposed changes
   p := act(o)
   # Post new proposals assuming my past observations still hold, if not, go back to the beginning;
   goback := false
   atomic {
	   if o == observe() {
              setp(p)
              goback = false
	   } else {
              goback = true
	   }
   }
   if goback {
      goto beginning
    }
}

Leveled API

Feels familiar? This is actually a very typical controller in high level. And it’s called level-based API in Kubernetes. By “level-based”, we mean:

  1. we make no other assumptions about the world except our last observations;
  2. we make decisions completely based on our assumptions;
  3. we try to commit our decisions if our assumptions still hold, otherwise, we update our assumptions;

Why?

Some points I can think of:

  1. optimal concurrency control, thereby -> we get “optimal”;
  2. remain as stateless as possible;
    1. scalable;
    2. better manageability;

Distinct thought pattern? Or repeating history

CAS?

This is all I know, let’s move the world forward; otherwise, allow me to refresh my knowledge and try again.

Agile?

Some items copied from Wikipedia: Agile Overview

  1. Iterative, incremental;
  2. Efficient and face-to-face communication
  3. Very short feedback loop and adaptation cycle;

Similar?

Conclusion

In multithread programming, CAS or Optimal Concurrency Control is used to:

  1. capture my moment;
  2. make my contribution based on my understanding;
  3. try really hard to catch up with the real world;

Here, data is modified all the time by our peers, and we need to stay up to date with it to make changes.

In a team, Standup or Sprint Planning is used to achieve almost the same thing:

  1. (to market or customers or PM) what do you think?
  2. here is what I propose to solve your problem, does it still make sense?
  3. what’s on your mind now? let me know!

Yeah, if human were more advanced machines, why not manage them using the same way :) Of course, don’t forget to add Happiness on top.