Tuesday, September 07, 2010

Lock-Ordering Deadlock

The code snippet below shows an example of a lock-ordering deadlock.
/**
 * Swaps the balances of two accounts.
 * Deadlock-prone!
 *
 * @param a
 * @param b
 */
public void swap(Account a, Account b) {
 synchronized (a) {
  synchronized (b) {
   double aBal = a.getBalance();
   double bBal = b.getBalance();
   a.setBalance(bBal);
   b.setBalance(aBal);
  }
 }
}
It acquires locks on both Account objects and then swaps their balances. It may look harmless at first, but if you look closely you will see that a deadlock can occur if two threads call swap at the same time, for the same accounts, but in the opposite order:

Thread_1: swap(a,b)
Thread_2: swap(b,a)

It is possible that Thread_1 will acquire the lock on account a and wait for the lock on account b, while Thread_2 is holding the lock on b and waiting for the lock on a.

In order to fix this, we need to make sure that the locks are always acquired in the same order. Here are a few different approaches that can be taken to resolve this:

1. Synchronizing the method
Remove the nested lock acquisitions and synchronize the method instead.


/**
 * Swaps the balances of two accounts.
 *
 * @param a
 * @param b
 */
public synchronized void swap(Account a, Account b) {
 double aBal = a.getBalance();
 double bBal = b.getBalance();
 a.setBalance(bBal);
 b.setBalance(aBal);
}
2. Inducing a lock ordering
To induce a lock ordering, you can compare the two accounts based on a unique, immutable key such as an account number. If your accounts are not Comparable, you can use System.identityHashCode instead. In case, for some reason, the two accounts being passed in are the same, you need to aquire a tie-breaking lock before aquiring the account locks.
private static final Object tieBreaker = new Object();

public void swap(Account a, Account b) {
 final int c = a.compareTo(b);
 if (c > 0) {
  synchronized (a) {
   synchronized (b) {
    double aBal = a.getBalance();
    double bBal = b.getBalance();
    a.setBalance(bBal);
    b.setBalance(aBal);
   }
  }
 } else if (c < 0) {
  synchronized (b) {
   synchronized (a) {
    double aBal = a.getBalance();
    double bBal = b.getBalance();
    a.setBalance(bBal);
    b.setBalance(aBal);
   }
  }
 } else {
  synchronized (tieBreaker) {
   synchronized (a) {
    synchronized (b) {
     double aBal = a.getBalance();
     double bBal = b.getBalance();
     a.setBalance(bBal);
     b.setBalance(aBal);
    }
   }
  }
 }
}
3. Using tryLock
Use tryLock to acquire both locks, but backoff and retry if they cannot both be acquired.
public void swap(Account a, Account b)
                        throws InterruptedException {
 Random random = new Random();
 while(true){
  if(a.getLock().tryLock()){
   try{
    if(b.getLock().tryLock()){
     try{
      double aBal = a.getBalance();
      double bBal = b.getBalance();
      a.setBalance(bBal);
      b.setBalance(aBal);
      return;
     }
     finally{
      b.getLock().unlock();
     }
    }
   }
   finally{
    a.getLock().unlock();
   }
  }
  Thread.sleep(random.nextInt(1000));
 }
}

Dell Studio - Restoring the Function Keys

I really like my new Dell Studio 17 laptop. But it does come with one really annoying feature. The function keys F1, F2 etc don't work as they should. They have been overlayed with "multimedia" keys which are enabled by default, so pressing F3, for example, brings up the battery dialog, F5, pops up the brightness control and F9 increases volume. In order to use the original F5 behaviour (e.g. to reload a webpage) you would have to combine it with the Function key (Fn) i.e. press Fn+F5. This is a big design defect, in my opinion. I would rather have my original F1, F2 keys back and combine them with the Fn key for multimedia, which I do not use as often.

There is a way to reconfigure the function keys. It involves changing a setting in the BIOS. You need to perform the following steps:

  1. When the laptop starts up (and you see the Dell Studio logo), quickly press F2 to enter the Setup Utility.
  2. Go to the "Advanced" tab.
  3. Move down to "Function Key Behaviour" and use the + key to change it from "Multimedia" to "Function".
  4. Press F10 to Save and Exit.

Monday, September 06, 2010

Java Bit Twiddling

This post explains some of the less commonly used operators in Java, namely the bitwise and bit shift operators and how they can be cleverly used to multiply or divide integers, test for evenness etc. The operators are shown in the table below:
Name Description
~a (NOT) Negates each bit. 0s becomes 1s and vice versa. ~a=(-a)-1
a & b (AND) In each pair of corresponding bits, the result is 1 if the first bit is 1 AND the second bit is 1, 0 otherwise.
a | b (OR) In each pair of corresponding bits, the result is 1 if the first bit is 1 OR the second bit is 1 OR both bits are 1, and otherwise the result is 0
a ^ b (XOR) In each pair of corresponding bits, the result in each position is 1 if the two bits are different, and 0 if they are the same.
a << n (LEFT-SHIFT) Shifts bit pattern to the left by n positions and places 0s on the right.
a >> n (RIGHT-SHIFT) Shifts bit pattern to the right by n positions and places the sign-bit on the left, thus preserving the sign of the operand.
a >>> n (UNSIGNED-RIGHT-SHIFT) Shifts bit pattern to the right by n positions and places 0s on the left.
Examples of bitwise and bit shift operators in action:
a = 3 (11)
b = 6 (110)

~a = -4 (11111111111111111111111111111100)
a & b = 2 (10)
a | b = 7 (111)
a ^ b = 5 (101)
a << 2 = 12 (1100)
b >> 1 = 3 (11)
b >>> 1 = 3 (11)
The code used to generate this is shown below:
final int a = 3; // 011
final int b = 6; // 110

System.out.printf("a = %s\t(%s)\n", a,
                 Integer.toBinaryString(a));
System.out.printf("b = %s\t(%s)\n", b,
                 Integer.toBinaryString(b));

/**
 * NOT
 */
int not = ~a;
System.out.printf("~a = %s\t(%s)\n", not,
                 Integer.toBinaryString(not));

/**
 * AND
 */
int and = a & b;
// 011
// 110
//----&
// 010
System.out.printf("a & b = %s\t(%s)\n", and,
                 Integer.toBinaryString(and));

/**
 * OR
 */
int or = a | b ;
// 011
// 110
//----|
// 111
System.out.printf("a | b = %s\t(%s)\n", or,
                 Integer.toBinaryString(or));

/**
 * XOR
 */
int xor = a ^ b ;
// 011
// 110
//----^
// 101
System.out.printf("a ^ b = %s\t(%s)\n", xor,
                 Integer.toBinaryString(xor));

/**
 * LEFT-SHIFT
 */
int lshift = a << 2;
// 00011
// ----- <<2
// 01100
System.out.printf("a << 2 = %s\t(%s)\n", lshift,
                 Integer.toBinaryString(lshift));

/**
 * RIGHT-SHIFT
 */
int rshift = b >> 1;
// 110
// ----- >>1
// 011
System.out.printf("b >> 1 = %s\t(%s)\n", rshift,
                 Integer.toBinaryString(rshift));

/**
 * UNSIGNED-RIGHT-SHIFT
 */
int urshift = b >>> 1;
// 110
// ----- >>1
// 011
System.out.printf("b >>> 1 = %s\t(%s)\n", urshift,
                 Integer.toBinaryString(urshift));

Usage of bit manipulation:
So, where do you use this? In the olden days, they were used for efficiency but most modern compilers today perform optimisations for you, so you don't have to worry about it. The bitwise and bit shift operators are not used very frequently in day-to-day programming, but here are a few scenarios where they can be used - mainly to impress you colleagues :)

1. Checking if an integer is even or odd
If an integer is odd, its rightmost bit will always be 1 and if it is even, it will always be 0. For example, 4 is 100 and 5 is 101.

public boolean isEven(int a){
    return a & 1 == 0;
}
2. Multiplying/Dividing by powers of two
Shifting to the left is just like multiplying by a power of two. For example 3 << 2 is 12. In general, a << n is a*(2^n). Keep in mind that a left shift can result in "overflow" which occurs when you exceed the limits of the range of the data type you are using and can cause unexpected behaviour.

A right shift is an integer division by a power of 2. Shifting right 1 position is the same as dividing by two. This approach is used in the Collections Framework, such as the Arrays class to find the middle element of an array. In general, a >> n is a/(2^n). Be careful, when right shifting negative integers. For example, 5 >> 1 gives 2, but -5 >> 1, gives -3.

3. Is an integer positive or negative?
Shift the integer right 31 places. The value of the far left bit is copied to the other bits. The far left bit is 1 when the value is negative and 0 otherwise.

public boolean isNegative(int a){
    return (a >> 31) != 0;
}
4. Negating an integer
You can use the NOT operator to determine the negative of any integer as shown in the snippet below. The basic idea is you invert all the bits and then add 1.
int num = 4;
int neg = ~num + 1; //-4
Note that you can also do the reverse and determine the positive of a negative integer by subtracting 1 and then inverting the bits.

5. Check if the nth bit is set
This is a more generalised version of the even/odd check. We move the 1 bit n places to the left and then apply the AND operation. If the nth bit was not set, this would result in 0.

public boolean isBitSet(int a, int n){
    return a & (1 << n) != 0;
}
6. Setting the nth bit
a | (1<<n)
7. Unsetting the nth bit
a & ~(1<<n)
8. Toggling the nth bit
a ^ (1<<n)
9. Unsetting the rightmost 1-bit
a & (a-1)
10. Checking if number is a power of 2
If the number is a power of 2, there will be only one 1-bit. If we unset this bit, we will get 0.
return (a & (a-1)) == 0;
11. Swapping values without a temporary variable
Swap two variables without a temporary variable using XOR:
x = x ^ y;
y = x ^ y;
x = x ^ y;
References:
Bit Twiddling Hacks
Java Ranch - Bit Shifting
Low Level Bit Hacks You Absolutely Must Know

Thursday, September 02, 2010

Python Cheat Sheet

I've been playing around with python over the last few days. It's really easy to use and I've written the following cheat sheet so that I don't forget how to use it:

Collections:

###################### TUPLE - immutable list
rgb = ("red", "green", "blue")

assert len(rgb) == 3
assert min(rgb) == "blue"
assert max(rgb) == "red"

#find the last element
assert rgb[len(rgb) - 1] == "blue"

assert "red" in rgb
assert "yellow" not in rgb

#slice the list [1,3)
rgb[1:3] #('green', 'blue')

#concatenate twice
rgb * 2

#iterate over list
for e in rgb:
 print e

###################### LIST - mutable list
colors = ["black", "white"]
assert len(colors) == 2

#add an element
colors.append("green")
assert len(colors) == 3
assert colors[2] == "green"

#remove an element
colors.remove("white")
assert "white" not in colors

colors.append("green")

#count occurrences of an element
assert colors.count("green") == 2

#return first index of value
assert colors.index("black") == 0

#insert element
colors.insert(1, "orange")
assert colors.index("orange") == 1

#remove the last element
e = colors.pop()
assert e == "green"

#replace a slice
colors[1:3] = ["red"];

colors.reverse()
colors.sort()

###################### SET
l = ["a", "b", "a", "c"]
assert len(set(l)) == 3

###################### DICTIONARY- mappings

dict = {"alice":22, "bob":20}
assert dict.get("alice") == 22

#add an element
dict["charlie"] = 25
assert dict.get("charlie") == 25

#get list of keys
assert len(dict.keys()) == 3

#get list of values
assert len(dict.values()) == 3

#check for key
assert dict.has_key("alice")
Loops:
for i in range(1, 10, 2):
    print i

while True:
    print 1
    break
Methods:
Printing out the factorial of a number.
def factorial(n):
    """prints factorial of n using recursion."""
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print factorial(4)
Classes:
class Person:

    def __init__(self, name, age):
        self.name = name
        self.age = age

    def equals(self, p):
        return isinstance(p, Person) and \
               self.name == p.name and \
               self.age == p.age


    def toString(self):
        return "name: %s, age: %s" % (self.name, self.age)


p = Person("Bob", 20)
q = Person("Charlie", 20)
assert p.equals(p)
assert p.equals(q)==False
print p.toString()
Read user input:
string = raw_input("Enter your name: ")
number = input("Enter a number:")
File I/O:
#write to file
filename = "C:/temp/test.txt"
f = file(filename, "w")
f.write("HELLO WORLD\nHELLO WORLD")
f.close()

#open a file in read-mode
f = file(filename, "r")

#read all lines into a list in one go
assert len(f.readlines()) == 2

#print out current position
print f.tell()

#go to beginning of file
f.seek(0)

#read file line by line with auto-cleanup
with open("C:\\temp\hello.wsdl") as f:
    for line in f:
        print line
Pickling (Serialisation):
#pickling
f = file("C:\\temp\dictionary.txt", 'w')
dict = {"alice":22, "bob":20}
import pickle
pickle.dump(dict, f)
f.close()

#unpickling
f = file("C:\\temp\dictionary.txt", 'r')
obj = pickle.load(f)
f.close()
assert obj["alice"] == 22
assert obj["bob"] == 20
Exception handling:
try:
    i = int("Hello")
except ValueError:
    i = -1
finally:
    print "finally"


#creating a custom exception class
from repr import repr

class MyException(Exception):
    def __init__(self, value):
        self.value = value
    def __str__(self):
        return repr(self.value)

try:
    raise MyException(2*2)
except MyException as e:
    print 'My exception occurred, value:', e.value
Lambdas:
def make_incrementor (n):
    return lambda x: x + n

f = make_incrementor(2)
print f(42)

print map(lambda x: x % 2, range(10))