[homework 3] elimination-backoff stack (due 12/23)

[jeehoonkang]

• Implement the elimination-backoff stack.
• Skeleton: https://github.com/kaist-cp/cs492-concur/tree/master/homework/src/elim_stack

References

• https://people.csail.mit.edu/shanir/publications/Lock_Free.pdf
• https://fenix.tecnico.ulisboa.pt/downloadFile/3779576906983/ConcurrentStacks.pdf

[jeehoonkang]

Invariants

• An elimination array has many slots.
• A slot is a (possibly null) pointer to PushReq with four possible tags: 0, 1, 2, 3.
  • Tag 0: slot is empty (pointer should be null)
  • Tag 1: slot has push request
  • Tag 2: slot has pop request (pointer should be null)
  • Tag 3: slot has both push and pop requests (already collided)

Procedures

try_push()

• Try push to the underlying Treiber's stack. If it fails...
• Pick a random slot.
• If it's tag is 2, try to collide by CAS.
• If it's tag is 1/3, retry from the beginning.
• If it's tag is 0, try to install a push request in the slot by CAS.
• thread::sleep(ELIM_DELAY).
• Check if the slot is collided; if so, return. (Don't touch the slot and the push request.)
• Otherwise, clean up the slot and retry from the beginning.

try_pop()

• Try pop from the underlying Treiber's stack. If it fails...
• Pick a random slot.
• If it's tag is 1, try to collide by CAS.
• If it's tag is 2/3, retry from the beginning.
• If it's tag is 0, tag it with 2 by CAS.
• thread::sleep(ELIM_DELAY).
• Check if the slot is collided; if so, clear the slot and immediately free the push request.
• Otherwise, clean up the slot and retry from the beginning.

[hydium]

in try_push()

Check if the slot is collided; if so, return. (Don't touch the slot and the push request.)

Why not clean up the slot? A pop should've collided and returned by now, there would be no one to clean it up if the push just returns.

[hyunsukimsokcho]

@hydium A collision implies there is a pop() thread colliding against the push() thread you mentioned. Then, the pop() thread seems to be responsible for cleaning up and freeing the PushReq.

[hydium]

@hyunsukimsokcho But then, how does the push() thread know what happened after waking up? After the pop() thread cleans the slot up, it can be reused by other threads and be in an arbitrary state.

[hyunsukimsokcho]

@hydium I see your point. Maybe pop() thread only frees PushReq and push() thread CAS the tag to 0. Then, whether there is a collision can be known by checking PushReq || tag == 3. (It is not a trivial implication from the provided spec. by prof.)

[codingskynet]

I knew that the dead line is 2019-12-23 21:00:00. But, in "gg.kaist.ac.kr" the dead line is "2019-12-23 09:00:01". Is it wrong or just I know wrong information?

[cmpark0126]

I knew that the dead line is 2019-12-23 21:00:00. But, in "gg.kaist.ac.kr" the dead line is "2019-12-23 09:00:01". Is it wrong or just I know wrong information?

Don't worry, It means 21:00:01. (9:00:01 PM)

[jeehoonkang]

I uploaded the scores. Grading criteria is as follows.

• A (30pts): sequential stress test (address sanitizer on).
• B (30pts): concurrent stress test (address sanitizer on).
• C (40pts): concurrent linearizability test (address sanitizer off).

If you're stack doesn't eliminate at all, I deducted 70%. If your program leaks memory, you'll get partial credits (10pts); if your program crashes, you'll get no credits.