Wednesday, November 24, 2010

CTGenR8 now available!

CTGenR8 is now available on the Android market.

It's my only and worst application, with a very limited purpose. I use this to generate integers and characters to test the solutions to the algorithms we study in class.

I learned a lot about Android, and a fair bit more about the publishing side than I wanted to. In the end it's all very rewarding to be able to post a QR code for my application on the Android market!



Enjoy, happy generating. Please send me your bugs!

Thursday, October 28, 2010

Threads in Java can be simpler

Apologies, I've been waiting for my project presentation for class before posting this.

In a previous post I complained about the Java Concurrency example. It showed how unimpressive and needlessly complicated threading can be in Java. What bothers me most isn't the concept of wait() and notify(). It is the decision to explain wait() and notify() before simpler methods of synchronization.

It happens that Java has quite a few helper classes to make synchronization much simpler. The Semaphore is one of those classes. I have constructed a simpler version of the Drop class using two Semaphores.

public class Drop {
    private static final int MAX_MESSAGE = 10;
    private String[] messages = new String[MAX_MESSAGE];
    private int next_available;
    private Semaphore taking = new Semaphore(0, true);
    private Semaphore putting = 
        new Semaphore(MAX_MESSAGE, true);
    
    public void put(String message) {
        try {
            putting.acquire();
        } catch (InterruptedException e) { }
        synchronized (messages) {
            messages[next_available] = message;
            next_available++;
        }
        taking.release();                                        
    }

    public String take() {
        String message;
        try {
            taking.acquire();
        } catch (InterruptedException e) { }
        synchronized (this) {
            next_available--;
            message = messages[next_available];
        }
        putting.release();
        return message;
    }
}

There are three conceptual pieces to that make this new Drop work. The first and second are two Semaphores, putting and taking.  The third piece is the synchronized code block

  1. The putting Semaphore protects against concurrent additions, and overflow.
  2. The taking Semaphore protects against concurrent removals, and underflow.
  3. The synchronized code block it utilizes the intrinsic lock on Drop creating an atomic section. Thereby protecting against concurrent manipulations of the messages array and next_available index into it.

These three pieces are much easier to understand than a broadcast system. Although we understand (or guess) that the underlying Semphore is implemented with the broadcasting wait() and notify() system.

Utilizing the provided utilities the example has become far simpler. There's no need to check the state of the Drop when the thread has resumed. There are no concerns of cascading execution of tasks.

Synchronization in Java could be presented as a simple use of the available utilities.

Monday, September 27, 2010

Learning about bounce

There's little opportunity to handle hardware interrupts in my day to day. Thankfully COSC 625 and Arduino present the opportunity for hardware interrupts and I to get acquainted.

Arduino has a nice online reference. The documentation for attachInterrupt includes a short example for creating a circuit that toggles an LED on or off.

There are two interrupts on the Duemilanove, pin 2 and 3. Pin 2 is interrupt 0, pin 3 is interrupt 1. The example uses pin 2. When pin 2 transitions from high to low, or low to high the interrupt service routine is called. The example has the LED turn on when the button is pressed, and off when released.

/* The pin the LED is attached to. */
#define LED_PIN 13

/* The initial state of the LED */
volatile int state = LOW;

void setup()
{
  pinMode(LED_PIN, OUTPUT);
  attachInterrupt(0, blink, CHANGE);
}

void loop()
{
  digitalWrite(LED_PIN, state);
}

void blink()
{
  state = !state;
}


But that's not what happened! After pressing the button several times the LED would be on when the button was released.


Insert video here

After double checking the wiring, and the project source several times I went looking for other interrupt examples. When I stumbled across my problem, which is the well known problem of bouncing. It turns out that physical switches give dirty signals. A switch will turn on and off very quickly many times for even a single action. Something an electrical engineer is well aware of, something I had no idea about.

So well known that Arduino even has a debouncing library.

I had some difficulties with getting the library to work; it's more my fault than anything else. Instead the interrupt service routine debounces.

#define BOUNCE_MIN 250

voidstatic unsigned long int last;
  unsigned long int now;

  now = millis();
  if ((now - last) <= BOUNCE_MIN) {
    /* do nothing */
    return;
  }

  last = now;
  state = !state;
}

Which limits the frequency of state changes to 250ms.



It works!

Sunday, September 19, 2010

My first integrated circuit

It's really hard to put down a toy. The arduino is no exception, and the projects from oomlout are so easy to do. Put those two together and you've got the start of an addiction.

The CIRC05 project is the first to use an integrated circuit. It works by throwing a latch to tell the integrated circuit to receive data, then sending the data, finally releasing the latch at which point the data is displayed. The data being sent is an 8 bit number, each bit of the number corresponds to a pin. When a bit is set the pin is high (the LED is on), when a bit is clear the pin is low (the LED is off.)

I'm still learning about basic electricity and electronics, so I followed the wiring layout (pdf link) without any variation. I did want to continue playing around with the layout. To do that the source needed some modifications, allowing subsequent projects with the same layout to require minimal work.

First the original in action:


This is the modified version of the oomlout source, subsequent projects will provide unique get_pin_value() and get_delay_ms() functions. By modifying these two functions the LED behavior is easily varied.
#define PIN_DATA 2
#define PIN_CLOCK 3
#define PIN_LATCH 4

#define DELAY_MS 150

void setup() {
    pinMode(PIN_DATA, OUTPUT);
    pinMode(PIN_CLOCK, OUTPUT);
    pinMode(PIN_LATCH, OUTPUT);
}

void loop() {
    static int pin_value = 0;
    static int delay_ms;

    pin_value = get_pin_value(pin_value);
    delay_ms = get_delay_ms(pin_value);

    updateLEDs(pin_value);
    delay(delay_ms);
}

void updateLEDs(int value) {
    /* Pull the chip latch low */
    digitalWrite(PIN_LATCH, LOW);
    /* Puts the bits into the shift register */
    shiftOut(PIN_DATA, PIN_CLOCK, MSBFIRST, value);
    /* Pulls the latch high, displaying the data */
    digitalWrite(PIN_LATCH, HIGH);
}

int get_pin_value(int i) {
    if (i == 255) {
 return (0);
    }
    return (++i);
}

int get_delay_ms(int i) {
    return (DELAY_MS);
}

The first modification was to make the LEDs light up sequentially.



The get_pin_value() and get_delay_ms() functions follow
int get_pin_value(int i) {
  if (i == 0 || i > 128) {
    return 1;
  }

  return (i*2);
}

int get_delay_ms(int i) {
    return (150);
}

The second modification was to light the LEDs sequentially keeping the previously lit LEDs on.



The get_pin_value() function is only marginally more complex, get_delay_ms() is unchanged
int get_pin_value(int i) {
    if (i == 0 || i > 255) {
        return 1;
    }

    return (i * 2 + 1);
}

int get_delay_ms(int i) {
    return (DELAY_MS);
}

The third modification was to light LEDs randomly, and delay randomly between displaying the values. This is my favorite.



The get_pin_value() and get_delay_ms() functions are simplistic.

int get_pin_value(int i) {
    /* In setup randomSeed(analogRead(0)); */
    return random(0, 256);
}

int get_delay_ms(int i) {
    return random(50, 200);
}

I am having a hard time putting this toy away, luckily I'm getting tired. Maybe I'll play with inputs tomorrow...

Saturday, September 18, 2010

8 LED Arduino

With a little free time this weekend, I invested it in my Arduino. I selected a project from ardx.orgCIRC02. The board layout (pdf link) involves 8 LEDs controlled by 8 output pins 2 through 9.

The initial project blinks the LEDs in ascending order, and then repeats. Wiring the board took longer than building the project




The original project source
int ledPins[] = {2, 3, 4, 5, 6, 7, 8, 9};

void setup() {
  for (int i = 0; i < 8; i++) {
      pinMode(ledPins[i], OUTPUT);
  }
}

void loop() {
  oneAfterAnotherNoLoop();
}

void oneAfterAnotherNoLoop() {
    int delayTime = 75;
    
    for (int i = 0; i < 8; i++) {
        digitalWrite(ledPins[i], HIGH);
        delay(delayTime);
        digitalWrite(ledPins[i], LOW);
        delay(delayTime);
    }
}

With the board wired up, the blinking LEDs didn't satisfy me. I created a few other projects that used the same wiring. Adding few utility functions, and an amplification array. With this basic set up, each project need only to implement an in_order() function
/**
 * Finds the number of elements in an array.
 */
#define NELE(array) (sizeof(array) / sizeof(array[0]))

/**
 * The amount to decay each pin by
 */
#define DECAY_AMOUNT 75

/**
 * The number of miliseconds to delay by
 */
#define DELAY_MS 80

int ledPins[] = {2, 3, 4, 5, 6, 7, 8, 9};
int ledAmp[NELE(ledPins)];

/**
 * setup
 *
 * Invoked by the arduino infrastructure to initialize state.
 */
void setup() {
  for (int i = 0; i < NELE(ledPins); i++) {
    pinMode(ledPins[i], OUTPUT);
    ledAmp[i] = 0;
  }
}

/**
 * Neverending loop
 */
void loop() {
  in_order();
}

/**
 * Decays all the pin outs that are in use
 *
 * @param[in] amount the amount to decay the pins by
 */
void decay_pins(int amount) {
  for (int i = 0; i < NELE(ledPins); i++) {
    ledAmp[i] -= amount;
    if (ledAmp[i] < 0) {
      ledAmp[i] = 0;
    }
  }
}

/**
 * Writes all the new pin values
 */
void write_pins() {
  for (int i = 0; i < NELE(ledPins); i++) {
    analogWrite(ledPins[i], ledAmp[i]);
  }
}
The high-top fade, the LEDs are faded left to right




Source to in_order
void in_order() {
  for (int i = 0; i < NELE(ledPins); i++) {
    ledAmp[i] = 255; /* Set the pin high */
    write_pins(); /* Write all pin values */
    delay(DELAY_MS);

    decay_pins(DECAY_AMOUNT); /* Decay all pins */
    write_pins();
    delay(DELAY_MS);
  }
}


The Battle Star Galactica, where the LEDs are fade left to right, then right to left.






Source to in_order
void in_order() {
  for (int i = 0; i < NELE(ledPins) - 1; i++) {
    ledAmp[i + 1] = 255; /* Set the pin high */
    ledAmp[i] = 255; /* Set the pin high */

    write_pins(); /* Write all pin values */
    delay(DELAY_MS);

    decay_pins(DECAY_AMOUNT); /* Decay all pins */
    write_pins();
    delay(DELAY_MS);
  }

  for (int i = NELE(ledPins); i > 0 ; i--) {
    ledAmp[i] = 255; /* Set the pin high */
    ledAmp[i - 1] = 255; /* Set the pin high */

    write_pins(); /* Write all pin values */
    delay(DELAY_MS);

    decay_pins(DECAY_AMOUNT); /* Decay all pins */
    write_pins();
    delay(DELAY_MS);
  }
}

The explosion, the center LED is lit up then fades away towards the edges





Source to in_order
void in_order() {
  int center = NELE(ledPins) / 2;
  for (int i = 0; i < NELE(ledPins) / 2; i++) {
    ledAmp[center - i] = 255; /* Set the pin high */
    ledAmp[center + i] = 255; /* Set the pin high */

    write_pins(); /* Write all pin values */
    delay(DELAY_MS);

    decay_pins(DECAY_AMOUNT); /* Decay all pins */
    write_pins();
    delay(DELAY_MS);
  }
  if (NELE(ledPins) % 2 == 0) {
    /* NELE(ledPins) is even */
    ledAmp[0] = 255;
  }
}

Monday, September 13, 2010

Threads in Java are not simple

To prepare for an upcoming project in real-time processing I needed an education in Java threads. I wanted to build a simple producer and consumer project with each producer and consumer given their own thread. There would be multiple producers and consumers, and possibly multiple items in the work queue.

This was supposed to be easy, as Java was designed with threading in mind. This is my experience, followed by an explanation of the costly scheduling that the sanctioned examples produces. The length of this post is a testament to the simplicity of implementing synchronized threads in Java.

Working my way through the Java tutorials I found this example. The heart of the example is the Drop class, it is the resource that will be accessed by multiple threads. Through an instance of the Drop class, the Producers will convey messages to the Consumers.

The Drop class with the commentary removed:

Drop.java
    public class Drop {
        private String message;
        private boolean empty = true;

        public synchronized String take() {
            while (empty) {
                try {
                    wait();
                } catch (InterruptedException e) {}
            }
            empty = true;
            notifyAll();
            return message;
        }

        public synchronized void put(String message) {
            while (!empty) {
                try { 
                    wait();
                } catch (InterruptedException e) {}
            }
            empty = false;
            this.message = message;
            notifyAll();
        }
    }

The purpose of the Drop class is to prevent concurrent access to the message member. This is achieved by using the Object's intrinsic lock (also called the monitor lock, or the monitor).


A thread obtains the lock by calling and entering a synchronized method. Any other thread that calls a synchronized method will be blocked until the lock is released. In this example the lock can be released in two ways; the synchronized call returns, or the thread wait()'s.


To understand the process, we need to understand wait() and notifyAll(). When a thread wait()'s it blocks, awaiting an InterruptionException, notifyAll() delivers such an exception.

It's important to understand that each thread will block on two levels, when in the context of a synchronized method without the intrinsic lock, and while wait()'ing.


In the Drop class when modifying or retrieving the message, the procedure is:

  1. Check if the message is empty
  2. If the message is incorrectly empty then wait()
    • When notified go to 1.
  3. Modify or retrieve message
  4. Modify empty
  5. Notify all threads

My Producer and Consumer classes are different from those in the example. They run forever and identify the Producer and Consumer by their thread name. Producers infinitely produce messages, and Consumers read those messages forever spitting them to System.out.

Producer.java
    import java.util.Random;

    public class Producer implements Runnable {
        private Drop drop;

        public Producer(Drop drop) {
            this.drop = drop;
        }

        public void run() {
            Random random = new Random();
            String pre = Thread.currentThread().getName()
                       + " widget #: ";
            int i = 1;

            while (true) {
                drop.put(pre + " " + i++);
                try {
                    Thread.sleep(random.nextInt(5000));
                } catch (InterruptedException e) { }
            }
        }
    }
Consumer.java
    import java.util.Random;

    public class Consumer implements Runnable {
        private Drop drop;

        public Consumer(Drop drop) {
            this.drop = drop;
        }

        public void run() {
            Random random = new Random();
            while (true) {
                message = drop.take();
                System.out.println(
                    Thread.currentThread().getName() + 
                    " MESSAGE RECEIVED: " + message);
                try {
                    Thread.sleep(random.nextInt(5000));
                } catch (InterruptedException e) {}
            }
        }
    }

Lastly a driver is needed to start the producers and consumers. To ease the scheduling explanation there will be one Producer and four Consumers.

ProducerConsumerExample.java
    public class ProducerConsumerExample {
        public static void main(String[] args) {
            Drop drop = new Drop();
            (new Thread(new Producer(drop))).start();
            (new Thread(new Consumer(drop))).start();
            (new Thread(new Consumer(drop))).start();
            (new Thread(new Consumer(drop))).start();
            (new Thread(new Consumer(drop))).start();
        }
    }

That's a lot of code, and a long introduction. Now we're ready to look at how threads are scheduled. To increase the simplicity of this situation I'm going to ignore the Producer for the moment.

I'm going to name the Consumer threads A, through D. When the program starts, it's non-deterministic which Consumer will start first, second, or third. However, I'm going to order those threads by their start time, and then name them. This means A starts first, B second, C third, and D last.

Assuming there is no message in the Drop instance (it's empty) the following happens. A, B, C, and D all call drop.take(). Since A started first, A is rewarded with the lock. B, C, and D are now all blocked on the intrinsic lock of the Drop object.

From A's perspective this happens
  1. drop.take() determines the message is empty
  2. A wait()s; which releases the lock
Now the lock is released. We'll assume the thread scheduling is fair (it doesn't have to be) and B obtains the lock. Which then...
  1. drop.take() determines the message is empty
  2. B wait()s; which releases the lock
And so on, at the end of this process A, B, C, and D have all relinquished the lock on the Drop instance. But they're all waiting to be notified.

Here is where it gets ugly.


The Producer thread wakes up deciding it's time to put a message in the Drop object. It calls drop.put(). After storing the message and setting empty to false, drop.put() invokes notifyAll().


What happens next?

The naive answer is A Consumer thread consumes the message. This answer did not satisfy me. Does the consumer thread execute in the context of notifyAll()? Doesn't Exception handling trump all other contexts?

To answer these question you have to think about the intrinsic lock, as well as the blocking from wait.

Remember that notifyAll() has been called within the context of drop.put(), which means that an Exception has been generated for all threads waiting on the intrinsic lock. The Producer currently owns the lock (the method is synchronized), no other thread can begin executing until the drop.put() call returns. The call to notifyAll() does not relinquish the lock. (This portion of the answer is  in the  documentation just remember that intrinsic lock is the same as monitor.)

Each of the Consumer threads are sitting in wait(). Earlier I said this relinquished the lock, I lied. Really when a thread calls wait() it's giving up the lock to obtain it later. wait() is waiting on the lock.

I find it's easier to think of the line of code that immediately follows the wait(). The next line of code the thread is going to execute is within the synchronized method drop.take(). The lock is required to execute in the context of the synchronized method. It happens to be that the Exception handling is the next logical section of code. To be able to process the Exception the thread must obtain the lock on the Drop object. This teaches me that Exceptions are not always handled immediately in Java.

Therefor each thread is in competition for the lock. One of them will be given the lock (suppose it's C). The following occurs:
  1. Enter drop.take() context; acquiring the lock
  2. Handle the Exception
  3. Find that there is a message
  4. Read the message
  5. Clear empty
  6. return from drop.take(); relinquishing the lock.
Now the lock on the Drop object is free. One thread is given the lock, say it's A.
  1. Enter drop.take() context; acquiring the lock
  2. Handle the Exception
  3. Find that there is no message
  4. wait(); relinquishing the lock
Now the lock on the Drop object is free. One thread is given the lock, say it's D.
  1. Enter drop.take() context; acquiring the lock
  2. Handle the Exception
  3. Find that there is no message
  4. wait(); relinquishing the lock
What this looks like is a cascade of acquire and release of the lock, each thread is given the lock to handle the Exception then almost immediately wait()'s. Which will lead to another cascade.

Due to the property of notifyAll() delivering an exception to all threads waiting on the lock of the object, there is overhead of checking the objects state after the handling of any Exception.

In the situation outlined above adding second Producer makes the situation less clear. This second producer will awaken the first. After adding a message to the Drop object, the second Producer's notifyAll() will be needlessly noticed by the first.

Understanding how a producer and consumer relationship through the Java tutorial example is anything but simple. Handling the lock is managed through two competing systems synchronized methods and notifyAll(). With notifyAll() complicating methods that wait()

Friday, September 10, 2010

Blink ... Blink ... Blink ...

Setting up the Arduino SDK on my laptop was the hardest part of this project. Some of the cross compiling set up scripts on gentoo have a couple of issues. Which was just as fun as chasing down the need to use icedtea for the SDK instead of the JRE from Sun (now Oracle.)




The source for the project is extremely short.
int ledpin = 13;

void setup() {
    pinMode(ledPin, OUTPUT);
}

void loop() {
    digitalWrite(ledPin, HIGH);
    delay(1000);
    digitalWrite(ledPin, LOW);
    delay(1000);
}
 I'm really looking forward to more Arduino projects.

Thursday, September 9, 2010

Best intentions.

This September is an important month in my life. My anticipated, and extremely delayed return to Eastern Michigan University began this month. After a five year hiatus I intend to complete my masters in computer science.

A lot has changed with the school, computer science, and me. There are new buildings and professors on campus. Java has taken over in academia. I'm older and more focused, driven to complete this important educational task.

Through this blog I'll record my challenges, opinions, and successes.