9/28/10 1 Advanced(Locking(Techniques(• Coarse‐grained(Synchroniza9on(• Fine‐grained(Synchroniza9on(• Op9mis9c(Synchroniza9on(• Lazy(Synchroniza9on(List‐based(Set(head( pred( curr( tail(a(b(c(head(pred( curr(tail(a(b(c(class node { T item; int key; Node next; }9/28/10 2 Coarse‐grained(Synchroniza9on(• Take(a(sequen9al(implementa9on,(add(a(lock(field,(and(ensure(that(each(method(call(acquires(and(releases(this(lock(• Simple,(and(works(well(when(levels(of(concurrency(is(low(• When(too(many(threads(try(to(access(the(object(at(the(same(9me,(the(object(becomes(a(sequen9al(boGleneck(Coarse‐grained(Locking(public(class(CoarseList<T>({((private(Node(head;((private(Lock(lock(=(new(ReentrantLock(();((public(CoarseList(()({(( (head(=(new(Node((Integer.MIN_VALUE);(( (head.next(=(new(Node((Integer.MAX_VALUE);((}((public(boolean(add((T(item)({(( (Node(pred,(curr;(( (int(key(=(item.hashCode(();(( (lock.lock(();(( (try({(( ( (pred(=(head;(( ( (curr(=(pred.next;(( ( (while((curr.key(<(key)({(( ( ( (pred(=(curr;(curr(=(curr.next;(( ( (}(( ( (if((key(==(curr.key)({(( ( ( (return(false;(( ( (}(else({(( ( ( (Node(node(=(new(Node((item);(( ( ( (node.next(=(curr;(pred.next(=(node;(( ( ( (return(true;(( ( (}(( ( (finally({(( ( ( (lock.unlock(();(( ( (}(( (}((}((public(boolean(remove((T(item)({(( (Node(pred,(curr;(( (int(key(=(item.hashCode(();(( (lock.lock(();(( (try({(( ( (pred(=(head;(( ( (curr(=(pred.next;(( ( (while((curr.key(<(key)({(( ( ( (pred(=(curr;(curr(=(curr.next;(( ( (}(( ( (if((key(=(curr.key)({(( ( ( (pred.next(=(curr.next;(( ( ( (return(true;(( ( (}(else({(( ( ( (return(false;(( ( (}(( (}(finally({(( ( (lock.unlock(();(( (}((}(9/28/10 3 Fine‐grained(Synchroniza9on(• Improve(concurrency(by(locking(individual(nodes,(instead(of(locking(the(en9re(list(• Opera9ons(interfere(only(when(trying(to(access(the(same(node(at(the(same(9me(• Higher(concurrency,(but(requires(a(lock(to(be(added(for(each(node(Fine‐grained(Locking(public(class(CoarseList<T>({((private(Node(head;((public(CoarseList(()({(( (head(=(new(Node((Integer.MIN_VALUE);(( (head.next(=(new(Node((Integer.MAX_VALUE);((}((public(boolean(add((T(item)({(( (int(key(=(item.hashCode(();(( (head.lock(();(( (Node(pred(=(head;(( (try({(( ( (Node(curr(=(pred.next;(( ( (curr.lock(();(( ( (try({(( ( ( (while((curr.key(<(key)({(( ( ( ( (pred.unlock();((( ( ( ( (pred(=(curr;(curr(=(curr.next;(( ( ( ( (curr.lock(();(( ( ( (}(( ( ( (if((key(==(curr.key)({(( ( ( ( (return(false;(( ( ( (}((( ( ( (Node(newNode(=(new(Node((item);(( ( ( (newNode.next(=(curr;(( ( ( (pred.next(=(newNode;(( ( ( (return(true;(( ( (}(finally({(( ( ( (curr.unlock(();(( ( (}(( (}(finally({(( ( (pred.unlock(();(( (} (((}((public(boolean(remove((T(item)({(( (Node(pred(=(null,(curr(=(null;(( (int(key(=(item.hashCode(();(( (head.lock(();(( (try({(( ( (pred(=(head;(( ( (curr(=(pred.next;(( ( (curr.lock();(( ( (try({(( ( ( (while((curr.key(<(key)({(( ( ( ( (pred.unlock(();(( ( ( ( (pred(=(curr;(curr(=(curr.next;(( ( ( ( (curr.lock(();(( ( ( (}(( ( ( (if((key(=(curr.key)({(( ( ( ( (pred.next(=(curr.next;(( ( ( ( (return(true;(( ( ( (}(( ( ( (return(false;(( ( (}(finally({(( ( ( (curr.unlock(();(( ( (}(( (}(finally({(( ( (pred.unlock(();(( (}((}(}(9/28/10 4 Why(Two(Locks?(head(pred( curr(tail(a(b(c(Thread(A( Thread(B(Hand‐Over‐Hand(Locking(head(pred( curr(tail(a(b(c(Thread(A(Thread(B(Except(for(the(ini9al(head(node,(acquire(the(lock(for(curr(only((while(holding(the(lock(for(pred(9/28/10 5 Op9mis9c(Synchroniza9on(• Search(a(component(without(acquiring(any(locks(• When(a(node(is(found,(it(locks(the(component,(and(then(checks(whether(the(component(has(been(changed(• Op9mis9c(about(the(possibility(of(conflic9ng(Op9mis9c(Locking((1)((public(boolean(add((T(item)({(( (int(key(=(item.hashCode(();(( (while((true)({(( ( (Node(pred(=(head;(( ( (Node(curr(=(pred.next;(( ( (while((curr.key(<=(key)({(( ( ( (pred(=(curr;(curr(=(curr.next;(( ( (}(( ( (pred.lock();(curr.lock(();(( ( (try({(( ( ( (if((validate(pred,(curr))({(( ( ( ( (if((curr.key(==(key)({(( ( ( ( ( (return(false;(( ( ( ( (}(else({(( ( ( ( ( (Node(node(=(new(Node((item);(( ( ( ( ( (node.next(=(curr;(pred.next(=(node;(( ( ( ( ( (return(true;(( ( ( ( (}(( ( ( (}(( ( (}(finally({(( ( ( (pred.unlock(();(curr.unlock();(( ( (}(( (}((}((public(boolean(remove((T(item)({(( (int(key(=(item.hashCode(();(( (while((true)({(( ( (Node(pred(=(head;(( ( (Node(curr(=(pred.next;(( ( (while((curr.key(<(key)({(( ( ( (pred(=(curr;(curr(=(curr.next;(( ( (}(( ( (pred.lock();(curr.lock(();(( ( (try({(( ( ( (if((validate(pred,(curr))({(( ( ( ( (if((curr.key(==(key)({(( ( ( ( ( (pred.next(=(curr.next;(( ( ( ( ( (return(true;(( ( ( ( (}(else({(( ( ( ( ( (return(flase;(( ( ( ( (}(( ( ( (}(( ( (}(finally({(( ( ( (pred.unlock(();(curr.unlock();(( ( (}(( (}((}(9/28/10 6 Op9mis9c(Locking((2)((public(boolean(contains((T(item)({(( (int(key(=(item.hashCode(();(( (while((true)({(( ( (Node(pred(=(head;(( ( (Node(curr(=(pred.next;(( ( (while((curr.key(<(key)({(( ( ( (pred(=(curr;(curr(=(curr.next;(( ( (}(( ( (try({(( ( ( (pred.lock();(curr.lock(();(( ( ( (if((validate(pred,(curr))({(( ( ( ( ( return((curr.key(=(key);(( ( ( (}(( ( (}(finally({(( ( ( (pred.unlock(();(curr.unlock();(( ( (}(( (}((}((public(boolean(validate((Node(pred,(Node(curr)({(( (Node(node(=(head;(( (while((node.key(<=(pred.key)({(( ( (if((node(==(pred)((( ( ( (return(pred.next(=(curr;(( ( (node(=(node.next;(( (}(( (return(false;((}(Why(valida9on?(head( pred(curr(tail(9/28/10 7 Lazy(Synchroniza9on(• Postpone(significant(changes,(e.g.,(physically(removing(a(node(from(a(linked(list(• Allow(a(list(to(be(traversed(only(once(without(locking,(and(contains()(is(wait‐free.(• Require(a(new(field(marked(to(be(added(into(each(node((Lazy(Locking((1)((public(boolean(add((T(item)({(( (int(key(=(item.hashCode(();(( (while((true)({(( ( (Node(pred(=(head;(( ( (Node(curr(=(pred.next;(( ( (while((curr.key(<(key)({(( ( ( (pred(=(curr;(curr(=(curr.next;(( ( (}(( ( (pred.lock();(( ( (try({(( ( ( (curr.lock();(( ( ( (try({(( ( ( ( (if((validate(pred,(curr))({(( ( ( ( ( (if((curr.key(==(key)({(( ( ( ( ( ((return(false;(( ( ( ( ( (}(else({(( ( ( ( ( ( (Node(node(=(new(Node((item);(( ( ( ( ( ( (node.next(=(curr;((( ( ( ( ( ( (pred.next(=(node;(( ( ( ( ( ( (return(true;(( ( ( ( ( (}(( ( ( ( (}(( ( ( (}(finally({(( ( ( ( (curr.unlock();(( ( ( (}(( ( (}(finally({(( ( ( (pred.unlock(();((( ( (}((