Blocking Queue in iOS

Blocking queues are essential to implementing producer-consumer pattern in concurrency programming. The pattern is simple. A queue of work items is maintained. For example, the queue can be a list of image URLs that need to be downloaded. A producer adds work items to the queue. A consumer removes work items from the queue. Producers and consumers work independently from different threads. If the queue is empty, the consumer blocks while it tries to get an item from the queue. As soon as the producer posts an item, the consumer ends the wait and retrieves the item.

The work queue is normally FIFO – an item that is queued earlier gets consumed earlier. Although, more complex implementation can build in a notion of priority.

There are two types of producer-consumer problem – bounded and unbounded.

  1. Unbounded – The work queue size is unlimited. A producer can post as many work items as it wants.
  2. Bounded – The work queue size is limited. If a producer produces at a more rapid rate than the consumer can consume then the queue will get filled up. When a queue is full, the producer will block as it tries to put a new item in the queue. As soon as the consumer takes an item from the queue, the producer will succeed in adding the item.

In the bounded situation both producer and consumer may block, depending on the rate they complete their work. In the unbounded situation only the consumer can block.

The good thing about the bounded situation is that the producer can be throttled if the consumer is unable to catch up with the work load. This prevents unnecessary production and wastage of CPU. Let’s say that a slideshow program has 500 images in the master list. Every image is displayed for 5 seconds. Here, the consumption rate is very slow – one image per 5 seconds. It doesn’t make a lot of sense to download all 500 images in rapid succession. We can limit the queue size to say 10 images. That way, the producer will only download an image if the work queue has room in it. This saves network communication and CPU usage.

In iOS, we generally recommend using Grand Central Dispatch (GCD) for producer consumer. With GCD, you don’t queue data, like URLs in our example. Instead, you queue code blocks:

dispatch_async(queue, ^{
   //Show an image
   //...
});

The queue is unbounded and the producer is not throttled. Instead, GCD throttles the consumer. It will dispatch the work to a thread only if it thinks that the device is sufficiently idle.

While GCD’s implementation is simple, I do not like the fact that the producer is not throttled. In some situations, a bounded queue is preferred.

Over the next few articles, I will show how to implement blocking queues – both bounded and unbounded. Consider using them only if GCD is not an option. Generally speaking, for unbounded queue, GCD works just fine. But, I will show an implementation in any case.

Unbounded Blocking Queue

In this article, I will show how to impalement unbounded blocking queue. Once again, GCD has a good alternative solution for you. Consider using it first. I am posting this solution for a couple of reasons:

  1. From an academic point of view, this example will help you understand pthread mutex and condition locking better.
  2. The implementation closely mimics Java’s LinkedBlockingQueue. If you are porting an app from Android, this will come handy.
  3. To set a stage for the bounded blocking queue, where, GCD doesn’t do that good a job. We will get to that in a follow up article.

Without any further ado, let’s get started.

Firstly, for an unlimited FIFO list, we will need a linked list. Regular array will be too slow. Unfortunately, Objective-C collection classes do not include a linked list. We will need to implement the functionality ourselves. I will keep things simple and let the blocking queue class manage the linked list. But, we will need a Node class that represents an work item.

Node.h

#import 

@interface Node : NSObject
@property (nonatomic, strong) id data;
@property (nonatomic, strong) Node* next;
@end

Node.m

#import "Node.h"

@implementation Node 

@synthesize data;
@synthesize next;

@end

Now, we will see the UnboundedBlockingQueue class. This is equivalent to LinkedBlockingQueue of Java.

UnboundedBlockingQueue.h

#import 
#import 
#import "Node.h"

@interface UnboundedBlockingQueue : NSObject{
@private
    pthread_mutex_t lock;
    pthread_cond_t notEmpty;
    Node *first, *last;
}

- (UnboundedBlockingQueue*) init;
- (void) put: (id) data;
- (id) take: (int) timeout; //timeout is in seconds

@end

UnboundedBlockingQueue.m

#import "UnboundedBlockingQueue.h"

@implementation UnboundedBlockingQueue

- (UnboundedBlockingQueue*) init {
    if ((self = [super init])) {
        last = nil;
        first = nil;
        pthread_mutex_init(&lock, NULL);
        pthread_cond_init(& notEmpty, NULL);   
    }
    return self;
}

- (void) dealloc {
    pthread_mutex_destroy(&lock);
    pthread_cond_destroy(& notEmpty);
}

- (void) put: (id) data {
    pthread_mutex_lock(&lock);

    Node *n = [[Node alloc] init];
    
    n.data = data;

    if (last != nil) {
        last.next = n;
    }
    if (first == nil) {
        first = n;
    }
    
    last = n;

    pthread_cond_signal(& notEmpty);
    pthread_mutex_unlock(&lock);
}

- (id) take: (int) timeout {
    id data = nil;
    struct timespec ts;
    struct timeval now;
    
    pthread_mutex_lock(&lock);
    
    gettimeofday(&now, NULL);
    
    ts.tv_sec = now.tv_sec + timeout; 
    ts.tv_nsec = 0; 
    
    while (first == nil) {
        if (pthread_cond_timedwait(& notEmpty, &lock, &ts) == ETIMEDOUT) {
            pthread_mutex_unlock(&lock);
            return nil;
        }
    }
    data = first.data;
    first = first.next;
    if (first == nil) {
        last = nil; //Empty queue
    }
    
    pthread_mutex_unlock(&lock);
    
    return data;
}

@end

If you are new to pthreads, focus on the pthread_cond_timedwait call. It does three things:

  1. Releases the lock on the mutex.
  2. Starts to wait for notification (signal) on the condition.
  3. Once the signal arrives, waits to reacquire the lock on the mutex.

For all practical purposes, all of the take: and put: methods run within an exclusive lock of the mutex. However, while pthread_cond_timedwait() is waiting, the lock is relinquished. It is essential that it does so. This allows the producer to call the put: method and put an item in the queue.

Finally, we should only call pthread_cond_timedwait() if there is a reason to do so – that is the queue is empty. This process is tricky due to spurious wake. In short, in multiprocessor nvironments, pthread_cond_timedwait/pthread_cond_wait can return even when no thread has signaled the condition. To deal with that, we employ this logic:

  • If pthread_cond_timedwait times out, we return nil. This will only happen if the queue is still empty.
  • If pthread_cond_timedwait returns for any other reason, we go back and check if the queue is empty (first == nil). In case of spurious wake, the queue can be still empty. This is why, the wait calls are wrapped in a while block and not an if block.

Finally, we see example uses of the class.

- (void) startProcess {
    //Start producer thread
    [NSThread detachNewThreadSelector:@selector(doPut) toTarget:self withObject:nil];
    //Start consumer thread
    [NSThread detachNewThreadSelector:@selector(doGet) toTarget:self withObject:nil];
}
//Producer
- (void) doPut {
    int i;
    for (i = 0; i < 5; ++i) {
            @autoreleasepool {
            NSString *str = [NSString stringWithFormat: @"Data %d", i];
            NSLog(@"Putting %@", str);
            [queue put: str];
        }
    }
}
//Consumer
- (void) doGet {
    while (TRUE) {
        @autoreleasepool {
            NSString *str = [queue take: 10];
            if (str == nil) {
                NSLog(@"Queue is empty");
            } else {
                [NSThread sleepForTimeInterval: 1];
                NSLog(@"Got %@", str);
            }
        }
    }  
}

Advertisements

A Documentation Model for a RESTful API

In this article, I propose a documentation structure for RESTful Web Services.

RESTful Web Services lack any standard for modeling. By that I mean, the URI syntax, HTTP method, response code etc. are all left up to the API designer. Without a clear documentation, developers can be left guessing about exactly how to invoke a service. There is a reason good documentation is considered a key best practice in a RESTful API design.

I have seen pretty messy documentation, some from fairly well known companies. Don’t let that happen to you.

What Needs to be Documented?

There are some factors that are common to all entry points or operations of the service. They need to be documented in one place:

  1. The base URL consisting of the protocol and host name only.
  2. Any details about the authentication scheme.

For each entry point (or operation) supported by the API, document these items.

General:

  1. What does the operation do?
  2. What are the security requirements? Is SSL or authentication required?

For the request:

  1. The HTTP method.
  2. URI syntax. This may contain the base URL for ease of use.
  3. URL parameters if any.
  4. Request body parameters if any.
  5. Supported MIME types (Content-type request header).

For the response:

  1. Meaning of various HTTP reply codes.
  2. Schema of the response body in success situation.
  3. Schema of the response body in error situations.

The URI Syntax

URI is used to uniquely identify a resource or a specific collection of resources. It should be documented using place holder parameters. Example:

/api/v2/products/{productId}

Or,

http://www.example.com/api/v2/products/productId

Name Type Description
productId Integer The ID of the product

URL Parameters

URL parameters are normally used with GET requests only. They provide filtering and sorting criteria. They should be documented using place holder parameters.

/api/v2/products/categories/{categoryId}?sortBy={sortBy}&maxSize={maxSize}

Name Type Description
sortBy String How to sort the results. Possible values: PRICE, ALPHABATIC. Optional. Default is PRICE.
maxSize Integer Maximum number of products returned. Optional. Default is 100.

Request Body Parameters

Request Body Parameters

Request body is normally used with PUT and POST requests. They are listed in a table similar to the URL parameters.

Describing the Response Body Schema

Most APIs use examples to describe the schema. This is not a bad way. For XML response, it may be useful to also attach a schema document.

Example Case Study

Get a Product

URI

http://www.example.com/api/v2/products/productId?lang=lang&currency=currency

Name Type Description
productId Integer The ID of the product

HTTP Method: GET

URL Parameters

Name Type Description
lang String The language code in which the description of the product will be returned. Possible values en, fr and es. Optional. Defaults to browser’s language setting.
currency String Currency in which prices are returned. Possible values USD, CAD and EUR. Optional. Default is USD.

MIME Types

text/xml, application/xml and application/json

HTTP Reply Codes

Code Meaning
200 Success
404 Product not found. Check the ID.
500 Invalid language or currency setting.

Response Body on Success

XML:

<product>
  <id>1001</id>
  <price>172.00<price>
  <currency>USD</currency>
  <image>http://images.example.com/small/1001.png</image&gt;
  <name>Baseball gloves</name>
  <description>…</description>
</product>

JSON:

{
  “id”: 1001,
  “price”: 172.00,
  “currency”: “USD”,
  “image”: “http://images.example.com/small/1001.png&#8221;,
  “description”:”…”
}

Proper Logging from Android Application

In this short article, we will dispel a simple confusion about logging in Android.

The android.util.Log class has various methods to perform logging at different levels. For example, v() is for verbose and i() is for information.

static String TAG = "MyApp";

Log.v(TAG, "Hello World");

The default log level is INFO. From the adb shell, you can change the log level to DEBUG, VERBOSE etc. using this command:

setprop  log.tag.MyApp  DEBUG

This looks straightforward. But, here is the catch. No matter what the log level is, every log entry always gets logged. If this is confusing to you, an example will help. In the examples above, we have set the log level to DEBUG. From the code we do a VERBOSE level log entry. You will think that logcat will not show this entry. That is not true. As I said, all log entries made from the code will always get logged.

So, why bother setting the log level. More importantly, how do you disable logging from the release version?

The answer is simple. You need to change your code and avoid logging based on the current log level setting. So, our example code will look like this.

if (Log.isLoggable(TAG, Log.VERBOSE)) {
    Log.v(TAG, "Hello World");
}

Now, this code will avoid a log entry if the level is set to something coarser like DEBUG or INFO.

This is why wrapping your log calls in isLoggable() is not just an optimization, it is absolutely essential.

You can simplify your life by creating a utility class that hides some of the details.

public class Logger {
    static String TAG = "MyApp";
	
    public static void v(String str) {
        if (Log.isLoggable(TAG, Log.VERBOSE)) {
            Log.v(TAG, str);
        }
    }
    public static void v(String str, Throwable t) {
        if (Log.isLoggable(TAG, Log.VERBOSE)) {
            Log.v(TAG, str, t);
        }
    }
}

Now, logging becomes super easy from your application:

Logger.v("Hello World");

To view verbose level log during development, run this command from adb shell.

setprop  log.tag.MyApp  VERBOSE

End users will not see the log entries since the default log level is INFO.

Saving Media from an Android Application

Some applications allow users to save photos, movies or music on the device. In this article, we will explore some of the best practices in that area.

First, you need to decide where to save the file. In most cases, you should not save into an application private folder. These folders are removed when the application is uninstalled. Best place to save media files is in a public shared folder on external SD card storage. For example, the following code gets the public Pictures folder on the SD card.

File targetDir;

targetDir = Environment.getExternalStoragePublicDirectory(
    Environment.DIRECTORY_PICTURES);
//Create the folder if necessary
if (targetDir.exists() == false) {
    targetDir.mkdir();
}
File outFile = new File(targetDir, "photo.jpg");

On most devices, this will select the /mnt/sdcard/Pictures folder. Unlike the Context.getExternalFilesDir() method, getExternalStoragePublicDirectory() does not create the folder for you. That is why we need create it using mkdir().

To write to the SD card, you must seek the android.permission.WRITE_EXTERNAL_STORAGE permission. So, add this to AndroidManifest.xml.

<manifest …>
<uses-permission android:name=”android.permission.WRITE_EXTERNAL_STORAGE”/>

</manifest>

Writing to the file itself is easy. You use the usual Java IO for that. Only thing to keep in mind is that you should always work with the file system from a separate thread so that you don’t tie up the main GUI thread.

The gallery application of some devices do not scan the Pictures folder on the SD card. If that happens, users will not be able to view the saved file from the media gallery. We need to inform the media scanner about the new file.  Add this code to do that. This will make the gallery application aware of the newly saved file.

MediaScannerConnection.scanFile(context,
    new String[] { outFile.toString() }, null,
    new MediaScannerConnection.OnScanCompletedListener() {
        public void onScanCompleted(String path, Uri uri) {
        }
});

Hardware Debugging with HTC Thunderbolt

Testing your app with the emulator is a good start. But, there is no alternative to actually running it on a device. Getting the app installed on a device is easy. All you have to do is export the APK and somehow manage to get it on the phone – download from a web server, send it as an email attachment or copy it into the SD card.

If you wish the debug the application on the device or view the LogCat entries, then you will need to resort to USB debugging. Google’s official documentation on this topic is here. But, the reality can be quite different, as we will see here.

Install USB Device Drivers

First step in the process is to install the USB drivers for your phone. Normally, you can download the drivers from the vendor’s web site. For HTC Thunderbolt, this is easier said than done. I couldn’t even find Thunderbolt mentioned in HTC web site.

My first attempt was to install the HTC Sync software which supposedly installs the drivers. But, as many have learned, Sync doesn’t install very well in Windows 7. That was a dead end.

After much Google searching, I found a site where someone was kind enough to store the 64bit drivers. Download the ZIP file and extract it somewhere.

Make sure that your device is not plugged in to the PC. Enable debugging by following these steps on the device:

  1. Open Settings.
  2. Go to Applications.
  3. Go to Development.
  4. Check USB Debugging.

Now, plug in the device to a USB slot of your PC. Windows will attempt to install the device drivers, which will fail.

Next, we will fix the device driver problem. Open Windows control panel. Click Devices and Printers. You will see the Android Phone device with an icon like this:

image

Right click it and select Properties.

image

Click Hardware tab. Click Properties button.

image

Click Change Settings.

image

Click the Driver tab. Click Update Driver.

Follow the wizard and point to the folder where the driver files from the ZIP file were downloaded. This will install the drivers correctly.

Just to be safe, unplug the device and after a few minutes, plug it back in.

Verify Connection

First, we will verify that adb can “see” the device. Open a command prompt and go to the platform-tools folder of the SDK. Then run the command:

adb  devices

image

This should show your device. If you don’t see it, something is wrong and you need to make sure that the drivers have installed correctly.

Debug from Eclipse

Now, we are ready to start debugging from Eclipse. First, make sure that no virtual emulator is running. Start Eclipse. Make the application debuggable by editing AndroidManifest.xml.

<application
    android:icon=”@drawable/icon”
    android:label=”@string/app_name” android:debuggable=”true”>

Save the XML file.

Next, run your Android project like you normally would. For example, right click the project and select Run As > Android Application. Eclipse will automatically deploy your application to the device and start it there. If your device screen is locked, just slide the slider and unlock it. You should see your application running.

You should be able to view the LogCat messages in Eclipse. The viewer in Eclipse is somewhat shaky. I find myself viewing the messages from the command line. You can do that by running this command:

adb  logcat

Happy debugging!

We are Live!

This is the first post to this blog, and I am naturally excited. I created this blog as a companion to my book Android Architecture Patterns.

I am still working on the book and hope to finish the finishing touches within a week. If all goes well, I plan on publishing an iOS counterpart to this book.

Please come back and visit my blog for high quality articles and tutorials on mobile architecture issues.