Starveless Priority Queue in Python

The python priority queue describes messages in absolute terms.  The most important element will always be popped.  The least important element may never be popped.

Sometimes when a message based data path is serialized to something (like a serial port based piece of hardware), all messages have some importance.  Unlike the priority queue, we would rather not use such absolute terms.  We would rather say that most of the time, the important messages are sent.  However, we guarantee that some of the time, the less important messages are sent.

The language is more gray and the queue needs to be a bit more…  “cooperative”.  (We could say “round robin”.)

Let’s implement our own.  But first, a quick back story.  I have some knowledge of Motorola’s (at the time) Time Processor Unit (TPU) on some of their embedded processors.  The TPU had an event driven model where certain sections of microcode would execute based on priority but lower priority microcode would still operated periodically.  Let’s base our design on this philosophy.  (See section 3 for more information on the TPU scheduler.)

Python has a pretty good queue framework that you derive your queue from and implement several methods.  If you ever look at the priority queue code in python, it is pretty simplistic as it relies on the heapq.  There is much work done in the Queue class including thread synchronization.

Here is our proposed round robin priority queue.

#! /usr/bin/python

import Queue

class RRPriorityQueue(Queue.Queue):
  '''Variant of Queue that retrieves open entries in priority order (lowest first)
  but allows highest priorities to be skipped.


  def _init(self, priorityOrder):
    if priorityOrder is None:
      raise TypeError

    self._queue = []

    self._priorityOrder = priorityOrder
    self._orderIdx = len(self._priorityOrder) + 1

  def _qsize(self, len=len):
    return len(self._queue)

  def _put(self, item):

  def _get(self):
    if (len(self._queue) == 0):
      raise IndexError

    retVal = None

    # change the order index for the priority order list
    self._orderIdx = self._orderIdx + 1
    if self._orderIdx >= len(self._priorityOrder):
      self._orderIdx = 0

    # the priority we are interested in and the highest value
    # in case we don't find one at our priority
    filterPriority = self._priorityOrder[self._orderIdx]
    highest = self._queue[0]

    # look for one of our priority but saving highest priority (lowest number)
    for item in self._queue:
      priority = item.priority
      if priority == filterPriority:
        # we found our item
        retVal = item
      if highest.priority > item.priority:
        highest = item

    # if we didn't find our item, the return the highest
    if retVal is None:
      retVal = highest

    return retVal

The _qsize and _put methods are basic.  The _init method requires a priority order.  This specifies the priority guaranteed to pop from the queue for the corresponding _get call.  The _orderIdx is used to know which step of the priority order the algorithm is on.  It increments or resets on every _get call.

The _get call is where the magic happens.  The first step is to increment or reset the _orderIdx value.  Then we are going to get our filterPriority from the _priorityOrder list based on the _orderIdx.  Then we iterate through the queue.  If we find an entity that matches our priority, return it.

However, what happens if we don’t find a message with our priority?  That is ok, we simply return the highest priority item first found in the queue.  The highest variable is a reference to the first item in the queue with the highest priority and is returned if we don’t find a match.

The only thing we require from the entities in the queue is that they implement a priority member (or method) that returns the priority number.  This deviates from the priority queue in that the queue wasn’t concerned about the priority number, just that an entity in the queue could compare to others.  In our case, we need to know the priority to filter the entities the way we want to.

Like the priority queue, the lower the priority number, the more important it is.

We can create our round robin queue like this:

self.q = RRPriorityQueue([1,2,1,3,1,2,1])

In this case, priority 1 messages are guaranteed to pop 4 out of 7 times.  Priority 2 message are guaranteed 2 out of 7.  Priority 3 – 1 out of 7.

You can make whatever pattern with whatever priorities you want.  Just understand that if a priority of an entity is not in the priority order, it can be starved.  It will be popped if it is the most important message when a message of the current filter order isn’t found.


Two Important SQLite and Python Lessons

When using SQLite3 and Python (2.x), there are two important lessons that are not obvious (at least not to me).

1. Dictionaries and TimeStamps

Ideally, I would like to do two things.  First, access data from a dictionary and not a list.  It is far more intuitive to access by column name (or query name substitution) than by list index.  Second, the datetime values should be correctly coerced even though SQLite has no implicit timestamp type.  I believe these two simple requirements are expected by most people, especially those family with Microsoft SQL and ADO.NET.

Good news, Python supports this!  However, there are some switches to set so to speak.

After importing sqlite3, the following connect statement will suffice for both needs:

conn = sqlite3.connect(dbname, detect_types=sqlite3.PARSE_DECLTYPES|sqlite3.PARSE_COLNAMES)

The PARSE_COLNAMES returns a dictionary for each row fetched instead of a list.

The PARSE_DECLTYPES empowers python to do a bit more type conversion based on the queries provided.  For example, if you do this:

cur.execute('select mytime from sometable')

You will get mytime as a string.  However, if you do this:

cur.execute('select mytime as "[timestamp]" from sometable')

You will get mytime as a datetime type in python.  This is very useful.

One step further; let’s say you want a timestamp but substitute the column name in the query.  Do this:

cur.execute('select mytime as "mytime [timestamp]" from sometable')

Not only with the data be returned as a datetime object, the dictionary will contain column name substitution provided in the query.  Beware, if you don’t do this on aggregate functions, the python sqlite library will attempt to add to the dictionary with an empty string key.  (Not sure why this is but beware.)

The adapters and converters live in the file in your python library installation directory for sqlite3.

Refer to the documentation here.

2. Execute and Tuples

This is really a lesson on declaring implicit tuples.

The execute method on a cursor is great because it will safely convert strings for use in the database (reducing the possibility of SQL injection).  It takes a query string and a substitution tuple.

However, I got caught again on the example below as will many who follow me.

This works:

cur.execute('insert into mytable values(?, ?, ?, ?)', (1, 2, 3, 4))

This doesn’t work and throws an exception:

cur.execute('insert into mytable values(?)', (1))

This works:

cur.execute('insert into mytable values(?)', (1,))

The comma after the one declares a tuple of one element.  Argh!!!

I hope this helps.


Beaglebone Black and Kiosk

So I wanted a super cheap but effective Kiosk.  The Beaglebone Black (BBB) was  a great choice with a 7″ screen from 4D Systems.  It is a ARM Linux machine with 4GB of internal storage.  I have a Rev C board that I got from Element 14.

For my project, I wanted a web server (sitting in front of a physical system I was controller) and a dedicated browser on the front panel.

Some Initial Steps

When I got the BBB Rev C, I plugged in the USB.  No connection.  Then I watched my router while I plugged in the network connection to see what IP address was served.  Nothing.  Then I found on the forums  that the BBB may not have shipped with the intended OS installed.  That was my case.

This guy’s site is pretty goodat describing the procedure even though he was using Ubuntu.  You can get the latest debian image here.  Install the OS and everything mentioned in the prior paragraph will magically be fixed.

Swapping In Lighttpd and PHP

The first step was to stop apache and bonescript so that we could install lighttpd and php.

Get a root shell on the BBB.  This can be done using PuTTY on Windows or a Linux box.  I used both because I am that sort of guy.

Start by disabling stuff that doesn’t matter.

systemctl disable bonescript.service
systemctl disable bonescript.socket
systemctl disable bonescript-autorun.service
systemctl disable cloud9.socket
systemctl disable mpd.service

You may want to keep cloud9 or mpd but the bonescript must go to install lighttpd.

The uninstall apache and udhcpd (which is provides a DHCP server).

update-rc.d apache2 disable
systemctl disable apache2.service
apt-get remove apache2
systemctl disable udhcpd
update-rc.d udhcpd disable
apt-get remove udhcpd

Then install lighttpd and php-cgi.  I used sqlite too.

apt-get install lighttpd
apt-get install php5-cgi
apt-get install php5-sqlite
lighty-enable-mod fastcgi 
lighty-enable-mod fastcgi-php

Modify your php and lighttpd configs as needed. (/etc/php5/cgi/php.ini and /etc/lighttpd/lighttpd.conf)

Put your pages in /var/www or wherever you prefer (as changed in lighttpd.conf).  You can manually restart lighttpd but I just reboot because I am that kind of guy and the BBB boots in 10 seconds.

Front Panel

As mentioned before,  our front panel was a 7″ display from 4D systems.

You can choose to remove X from running by disabling lightdm (associated server and sockets) using systemctl.  I would rather keep the front panel and have a kiosk that is a web browser.

Side note:  I tried to swap nodm for lightdm but ended up getting some error message that I don’t remember and got verify frustrated as X wouldn’t start except from command line.  I suspect it had something to do with the order systemctl started certain services.  I gave up because it wasn’t important to me to figure it out and reflashed the OS.  I wanted to see of nodm and matchbox were better (i.e. smaller and faster) than lightdm and LXDE but oh well.

So, in this case, we will continue to use lightdm, have it auto logon to the debian account and start the kiosk.

This was really simple.  There are two steps.

First, have chromium start when LXDE starts.  Edit /etc/xdg/lxsession/LXDE/autostart.  Comment out the lines beginning with @lxpanel and @pcmanfm.  You don’t need the desktop panels and file manager.  Add the following to the file:  @chromium –disk-cache-dir=/dev/null –app=”http://localhost”.  Of course, substitute your path if different.  The disk-cache-dir set to /dev/null prohibits chromium from caching pages.  This is critical if update your pages periodically.

If you have reviewed any chromium documentation, there is also a –kiosk flag.  However, two very undesirable aspects arise.  First, chromium balks about not having Google API keys installed.  I don’t care but chromium is relentless.  Second, if the browser is stopped hard, on the next startup, chromium asks if you want to restore your session.  Again, I don’t care but chromium is relentless.  Using the “app” flag guarantees these relentless messages do not appear.  Also, you will not see any navigation bar, etc.

Second, the screen isn’t full and you get window decorations.  Both need to go.  Edit the /home/debian/.config/openbox/lxde-rc.xml file.  Under the <applications> tag.


After the next reboot, you have a kiosk.

Future Considerations

There were several things to be considered on the front panel.

First, the scroll bars are way too small for a finger.  I didn’t get around to changing this.   Scroll bars should be avoided.  We will elaborate more.

Second, I have been in several companies now where they think that a browser on a PC will look the same as a browser on a 7″ display.  Nope.  Two problems.  Real estate and the size of a finger versus the control of a mouse.  Buttons have to be big and pages must minimize scrolling.

Third, in this day and age, we want to scroll by sliding our finger like a cell phone.  Unfortunately, this is not the way this works in this case.  Your finger is really a mouse and the screen is not a “real” touch device like a phone or tablet.

I want to play with Android for BBB but that will be a future article.