From 7923a597052c69cb7676fce8e7a81040b69edc4b Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Sun, 8 Feb 2015 22:21:10 -0800 Subject: [PATCH] changes --- Makefile | 3 ++- concurrent-hashmap/note.txt | 20 ++++++++------------ 2 files changed, 10 insertions(+), 13 deletions(-) diff --git a/Makefile b/Makefile index e988a49..835f7d1 100644 --- a/Makefile +++ b/Makefile @@ -1,5 +1,6 @@ DIRS := barrier mcs-lock mpmc-queue spsc-queue spsc-bugfix linuxrwlocks \ - dekker-fences chase-lev-deque ms-queue chase-lev-deque-bugfix + dekker-fences chase-lev-deque ms-queue chase-lev-deque-bugfix \ + concurrent-hashmap .PHONY: $(DIRS) diff --git a/concurrent-hashmap/note.txt b/concurrent-hashmap/note.txt index 6b0898d..0056dcd 100644 --- a/concurrent-hashmap/note.txt +++ b/concurrent-hashmap/note.txt @@ -1,14 +1,10 @@ -#Non-SC case: -If we have two threads, 1 thread has a put(K1, V1), another thread has another -put(K2, V2) followed by a get(K3), where K1 and K3 have the same hash and k1 and -k2 are hashed in the same slot, as follows. +#Non-SC: +The following case can be non-SC. Thrd1 Thrd2 -put(k1, v1); // a put(k2, v2); // b - get(k3); // c -Suppose we have a synchronized before b with the segment lock, so by SC a is -before b. Since b is sequenced before c, a should be SC before c. However, in c, -the first time it does not grab the lock, and c could read an old entry (the -head of the linked list, meaning that it gets a shorter list), and that can be -an SC violation. The solution is that we use annotations to tell the SC analysis -when we will ignore the specific actions (FIXME!!) +put(k1, v1); // a put(k2, v2); // c +get(k2); // b get(k1); // d + +When b and d both read the old head of the list (and they later grab the lock, +making it the interface SC), it's non-SC because neither reads the updated +value. -- 2.34.1