Concurrency and Deadlocks in Java: A Brief Introduction

In attempting to understand how concurrency works with java it is important to lay the foundation by discussing process management in operating systems before moving on to specific concurrency issues in java.

Process Management in Operating Systems

A process is an instance of a computer program that performs some action. A process can have multiple threads and can be controlled by a user, other programs or by the operating system that its running on. The operating system will execute processes sequentially and can be running multiple processes at any one time, this is called concurrency.

To further explain, a single computer processor runs instructions one at a time, so that a user can run several programs at once, time-sharing is performed. Time-sharing allows for programs to be in either “executed” or “waiting to be executed” state, this gives the illusion to the user that multiple processes are running at the same time but in reality the operating system is switching between them rapidly. An operating system run on a computer with multiple processors can execute instructions simultaneously for different processes.

Mutexes and Threads

A mutex or mutual exclusion is used in parallel programming to “lock” a shared resources so that only one thread can access it at a time whilst at the same time giving waiting tasks a place to wait for their turn. A popular way to remember this is to think of an airplane bathroom. Only one person can access the bathroom at one time, in this case the lock is the mutex so when the door is locked the bathroom is unavailable to the people waiting in queue.

In java every object has one monitor and mutex associated with it. A monitor is a piece of code which is guarded by a mutex. Whenever a thread accesses a synchronized method, the mutex is locked, conversely when the method is finished, the mutex is unlocked. This ensures that only one synchronized method is called at a time on a given object.

Deadlocks and Prevention

A deadlock occurs when two or more threads are waiting for each other to finish and so therefore cannot.

Lock Ordering

One way to prevent a deadlock is to assign an order to the locks and require that they are accessed in that order. This can only work if you know about all locks ahed of time so is not always practical.

Lock Timeout

You can also prevent deadlocks by having a timeout function on lock attempts. This means a thread will only try for so long to acquire the necessary locks before quitting (backing up), thus freeing all locks taken. It will then try again after a random amount of time during which other threads can try to access the necessary threads.

One of the drawbacks if you have lots of threads trying to acquire the same lock they might end up waiting the same amount of time and therefore trying to obtain a lock at the same time over and over.

Deadlock Detected

What do you do if you have a deadlock? You can release all the locks and wait a random amount of time before retrying. But this is can have the same problems as described by a lock timeout above. A better way to do this would be to assigned a priority to the threads so that only the highest priority thread/s backup.

References

Processes:

Mutexes:

Deadlocks:

Advertisements

An Intro to Big Oh Notation with Java

Big Oh notation is used in computer science to decribe the complexity of an algorithm in terms of time and space (memory). Big Oh notation describes the worst case scenario of what happens when an algorithm is run with N values and is really only useful when talking about large sets of data.

constant logarithmic linear quadratic cubic
n O(1) O(log N) O(N) O(N log N) O(N2) O(N3)
1 1 1 1 1 1 1
2 1 1 2 2 4 8
4 1 2 4 8 16 64
8 1 3 8 24 64 512
16 1 4 16 64 256 4,096
1,024 1 10 1,024 10,240 1,048,576 1,073,741,824
1,048,576 1 20 1,048,576 20,971,520 1012 1016

Big Oh Complexity Over Time

Source: table source here also big thanks to Dean who made the graph for me 🙂

Explanation

O(1) = irrespective of changing the size of the input, time stays the same

O(N) = as you increase the size of input, the time taken to complete operations scales linearly with that size

O(log N) = growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase

O(N2) = growth will double with each additional element in the input

Java Example for O(1):

    public static boolean isArrayOver100(String[] args) {
        if (args.length > 100)
            return true;
        return false;
    }

Java Example for O(N):

    public static boolean contains(String[] args, String value) {
        for (int i = 0; i < args.length; i++) {
            if (args[i] == value)
                return true;
        }
        return false;
    }

Java Example for O(log N):

public static int binarySearch(int[] toSearch, int key) {
    int fromIndex = 0;
    int toIndex = toSearch.length - 1;

    while (fromIndex < toIndex) {
        int midIndex = (toIndex - fromIndex / 2) + fromIndex;
        int midValue = toSearch[midIndex];

        if (key > midValue) {
            fromIndex = midIndex++;
        } else if (key < midValue) {
            toIndex = midIndex - 1;
        } else {
            return midIndex;
        }
    }
    return -1;
}

See my other post on binary search here.

Java Exmaple O(N2)

public static boolean containsDuplicates(String[] args) {
        for (int i = 0; i < args.length; i++) {
            for (int j = 0; j < args.length; j++) {
                if (i == j)
                    break;
                if (args[i] == args[j])
                    return true;
            }
        }
        return false;
    }

I took this post as my inspiration as I found it to be a great introduction but have instead used java for the code examples.

Implementing Binary Search in Java

What is it?

Binary Search is a technique used to search sorted data sets. It works by comparing the middle element against the search value, if the search value is greater than the middle element a subset is created out of the upper half of the set. The same operation is then performed on the subset recursively until the value is either found and the index returned, or not found and -1 returned.

eg. If we start with with a set of ints: [1, 4, 6, 8, 9, 10, 11, 13, 15] and our search value = 11

  • Choose the middle element: 9
  • Is key == 9? No so we can’t break early
  • Is 9 > 11
  • No, so take the upper half and create a subset [10, 11, 13, 15]
  • Choose the middle element: 13 (4/2 =2 which is the third element in the array as arrays are zero based)
  • Is 13 > 11
  • Yes, so take the lower half and create a subset [10, 11]
  • Choose the middle element: 11
  • Is 11 == 11 yes – we have found our element

Binary Search in Java

I have created my own java binary search method:

    public static int binarySearch(int[] toSearch, int key) {
        int fromIndex = 0;
        int toIndex = toSearch.length - 1;

        while (fromIndex <= toIndex) {
            int midIndex = (toIndex - fromIndex) / 2 + fromIndex;
            int midValue = toSearch[midIndex];

            if (key > midValue) {
                fromIndex = midIndex + 1;
            } else if (key < midValue) {
                toIndex = midIndex - 1;
            } else {
                return midIndex;
            }
        }
        return -1;
    }

Take a look at Arrays.binarySearch() method to see the java source code implementation of the search. If you don’t have the java source code attached to your favourite IDE I suggest you do so, it’s a great way to learn how everything works.

Complexity

The complexity of the binary search is O(log n).

Why use Binary Search?

Binary Search is quicker than searching through every element (O(n)) as it halves the amount of elements to search each iteration. This halving means that after a strong growth curve at the beginning, it slowly flattens out as the size of the input data set increases, therefore it is good for large data sets.

More Info

There is a good introductory explanation of binary search and O notation here.

Pair Programming: a few thoughts

I recently read a great article on pair programming by a developer over at Atlassian where he really summed up my views on the topic. I have had really good experiences with pairing and some not so good ones.

What came out of some of the more positive experiences were:

  • I came up to speed on a new system quickly
  • Risks or major design questions were verbalised and dealt with sooner
  • I learnt more efficient ways of coding things
  • I learnt more cool eclipse keyboard shortcuts!
  • My TDD and general development skills rapidly increased

Some of the more difficult experiences:

  • I felt frustrated at the sometimes slow pace
  • Sometimes my pair would dominate the keyboard so it was easy to drift off into la la land
  • When joining an existing team I worried I wasn’t learning enough of the system and if they were sick that day I’d be lost

Some of the paring experiences Ive had I didn’t realise until much later how extremely valuable they really were.

I think in order for pairing to be successful you should:

  • rotate partners often
  • be open to constructive criticism on code improvements
  • voice your opinion/suggestions so you can work a team to develop a solution
  • take breaks every couple of hours to check email/facebook – refresh
  • ensure you get equal keyboard time
  • keep trying! – pairing wont come naturally to everyone but there are a lot of benefits to come out of it and its a chance to really improve as a developer

If your workplace doesn’t see the value in pairing then as stated in the article, I think the next best thing is to make sure you get an extra set of eyes on every line of code committed, whether its using a code review tool or as I did on a former project, have another developer check over your code before each commit.

Running JavaFX project on Linux thru Hudson

If you want to get your FX project setup as a Job in Hudson. Simply follow the steps below and victory will be yours!

  • Download the javaFX1.2 SDK installation file for Linux
  • Copy the installation script to the desired locatio
  • Create a new environment variable $JFX_HOME and set it to the base directory of you fx sdk installation
  • Create a simple HelloWorld.fx script and test it’s compiling eg.
  • import javafx.stage.Stage;
    import javafx.scene.Scene;
    import javafx.scene.text.Text;
    import javafx.scene.text.Font;
    
    Stage {
        title: "Application title"
        width: 250
        height: 80
        scene: Scene {
            content: Text {
                font : Font {
                    size : 24
                }
                x: 10, y: 30
                content: "Application content"
            }
        }
    }
    

    Then verify it’s running by executing the javaxc command (much like javac)

  • Add a pom.xml to your project that looks like the one below
  • <build>
    		<sourceDirectory>src</sourceDirectory>
    		<plugins>
    			<plugin>
    				<groupId>org.apache.maven.plugins</groupId>
    				<artifactId>maven-compiler-plugin</artifactId>
    				<configuration>
    					<compilerId>javafxc</compilerId>
    					<include>**/*.fx</include>
    					<fork>true</fork> <!-- NOTE: only “fork” mode supported now -->
    				</configuration>
    				<dependencies>
    					<dependency>
    						<groupId>net.sf.m2-javafxc</groupId>
    						<artifactId>plexus-compiler-javafxc</artifactId>
    						<version>0.3</version> 
    					</dependency>
    				</dependencies>
    			</plugin>
    		</plugins>
    	</build>
    
  • Add a new job in Hudson for a maven2 project and kick off a build. All should be well! If you do get an exception like the one below, then verify your $JFX_HOME variable is set correctly. I had to restart Glassfish in order for Hudosn to pick up the new variable.
  • Caused by: java.lang.NullPointerException
    	at java.io.File.<init>(File.java:222)
    	at net.sf.m2javafxc.javafxc.JavafxcCompiler.compile(JavafxcCompiler.java:146)
    	at org.apache.maven.plugin.AbstractCompilerMojo.execute(AbstractCompilerMojo.java:493)
    	... 32 more
    

    Grails Pagination with Multiple Order Clauses – How To

    There is a known bug in grails where you can’t have multiple order by’s when returning a PagedResultList. When talking about the .createCriteria().list() method it seems you can only specify the order by inside the .list() method and not in the builder body itself even if only ordering by one values.

    This is very annoying as I think multiple order by’s would be a common requirement of a lot of apps. Below is my work around to this bug. I’ll investigate providing a patch to fix this in the near future.

    Let’s start by taking a look at three ways you might use to query the database:

    Our domain class looks like this:

    @Entity
    @Table(name = "tbl_book")
    public class Book {
    
    @Id
    @Column(name = "bookId")
    private int id;
    private String author;
    private String title;
    private Date releaseDate;
    
    // getters and setters
    
    1. Dynamic Methods:
      def results = Book.findAllByAuthor("Marsden", [max:10, offset:0, sort:"releaseDate", order:"desc"])

      The above method would return a PagedResultList ordered by releaseDate descending, but what if we want to order by venue as well? We can’t! Moving on…

    2. def results = Book.createCriteria()
               def results = Book.createCriteria().list(
                   max: params.max,
                   offset: params.offset) {
                   and {
                       eq('author', 'Marsden')
                       order('releaseDate', 'desc')
                       order('title', 'asc')
                   }
               }  

      The above thows a runtime sql exception, you can get it to work only by including the order in the .list() function and only if you include just one order statement, further details of the bug here. Sigh…

    3. def results = Book.withCriteria()
              def results = Book.withCriteria() {
                  maxResults(params.max?.toInteger())
                  firstResult(params.offset?.toInteger())
      
                  and {
                      eq('author', 'Marsden')
                      order('releaseDate', 'desc')
                      order('title', 'asc')
                  }
              }
      

      The above looks fine except it doesn’t return an instance of PagedResultList which means we don’t have access to the results.totalCount method which gives us the total number of results needed for pagination in the g:pagination tag in the view. Still no dice…!

    Solution

    Use query method 3, Book.withCriteria() and then create a seperate query to return the total number of results eg:

            def rowCount = Book.createCriteria().get() {
                projections {
                    rowCount()
                }
                and {
                    eq("author", params.author)
                }
            }
    

    rowCount should then be passed to your view so the pagination tag can use it:

                <div class="paginateButtons">
                    <g:paginate total="${rowCount}" />
                </div>
    

    This solution is really ugly. Im not a fan of having to execute the query twice just to get the total count. I really hope this bug is fixed soon, or someone tells me im missing something fundamental 🙂

    Nabble questions on this here and here.

    Populating a select box in Grails with values from database

    A fairly common requirement is to populate values in a select box/drop down box with values from a database. It’s quick and easy to do in Grails.

    1. Inside your Contorller, create your query in the closure associated with your view. Eg. I’m going to create a new object that contains a list of values from that database and return it to the search.gsp view:
    2. def search = {
        def authors = Book.executeQuery("SELECT distinct b.author FROM Book b")
        [authors : authors]
      }
    3. Inside your search.gsp, add a select box that displays the list of countries:
      <g:select id="authorSelection" name="author" from="${authors}" value="" noSelection="['':'Please Select...']> 
    4. When you are reading the value back out of the form in your controller, simply use:
      params.author
    5. You’re done! Easy peasy.

    EDIT: I recently found an official looking tutorial about how to do selects with grails here.