Assigning Task Priorities with RMA

Embedded gurus Michael Barr and David Stewart have written a couple of great articles about assigning task priorities with RMA (the Rate Monotonic Algorithm):

  1. Introduction to Rate Monotonic Scheduling, by David Stewart and Michael Barr
  2. 3 Things Every Programmer Should Know About RMA, by Michael Barr

The first article lays out the basics: RMA is an algorithm that assigns static priorities to periodic tasks in order to maximize “schedulability.”  That’s a mouthful: 16 words, 37 syllables.  And one of the words isn’t real: “schedulability,” which means “able to be scheduled so that all tasks complete before their deadline every time.”

Let’s try again: RMA helps tasks get done in time.  That’s better: 7 words, 9 syllables.

The second article expands on the basics of RMA, giving some additional guidelines for when it should be used, especially as it applies to interrupts (which it does!).

I want to talk a bit more about the basics of RMA.  RMA is easy to describe: a task’s priority is based on how often it runs.  The task that runs the most often gets the highest priority, the task that runs the second most often gets the next highest priority, and so on.  Or, to quote the first article, “Assign the priority of each task according to its period, so that the shorter the period the higher the priority.”

RMA does not guarantee that your tasks will all complete in time; RMA does guarantee to find the optimal static prioritization assignment if one exists.  If RMA doesn’t produce a “schedulable” task set then no “schedulable” static priority scheme exists.

RMA’s greedy nature makes intuitive sense: starting at time zero, assume all tasks are ready to run.  Then run the task with the shortest period.  Since this task runs more often than any other task, it “feels” right to run it first to give it the best chance of finishing before it has to run again.  Next run the task with the next shortest period, and so on, until all tasks have been run.

Fortunately the intuition and “feel” that RMA works is backed by the fact that it does!

I’ve given a very basic overview of RMA here.  Please check out Stewart and Barr’s articles for more about RMA.

“Shaping Things” by Bruce Sterling

I just finished “Shaping Things,” by Bruce Sterling.  It’s a very broad look at the way technology, people, and society have changed – and changed each other – over time.  And since it’s by Bruce Sterling, it’s mostly focused on the possibilities of tomorrow.

My favorite quote:

“Tomorrow composts today.”

Very cool – both the quote, and the book.

Sterling looks at five classes of technosocial relationships:

  • Artifacts / Hunters and Farmers
  • Machines / Customers
  • Products / Consumers
  • Gizmos / End-Users
  • Spimes / Wranglers

Definitely worth a read.

I got it from the library, and I’m going to hang on to it for a little while longer and read it again.  It’s short, but conceptually dense.

Definitely worth a re-read.

I love embedded, and so does Woz!

I love working in the embedded world.  Hardware + software = a great time and a great career.

I came across this fantastic quote by Steve Wozniak in “Making it Big in Software,” by Sam Lightstone.  Woz is talking about designing the Apple II:

“And I did every piece of software from the ground up, through applications that you can’t pin down for any one of them.  The hardware was so interrelated that I can’t really divide it into software and hardware alone.  Those days were that way.  Today, if you work on embedded processors, you put a little microprocessor into a small product.  That’s the job in the world that I would love to this day! That’s what I did back then; it mixed both hardware and software.”

Sounds like Woz wants my job.  🙂

Hacks and Hack-Nots

The world is divided into two kinds of people: Hacks and Hack-Nots.

Hacks people hack.  They want hardware and software (aka “technology” or “tech”) they can change, optimize, use as they please, modify, destroy, etc. – in short, they want to hack.

Hack-Nots people do not hack. They don’t want to know what “hacking” means. They want their hardware and software to Just Work.  They don’t want to be aware of technology at all, they just don’t care.  They want to email, work, check Facebook, etc. – in short, they want to do something other than use the tech.  Technology is a means to an end, nothing more.

Hacks check email, Facebook, blogs, etc. just like Hack-Nots, but for Hacks the journey is more important than the destination.  The experience of checking email is more important than the email itself.  Configurability is key.  Even if it Just Works out of the box, Hacks will optimize it to their liking.  Technology is an end in itself.

For Hacks, optimization and configurability are more than just a Nice To Have, they are Moral Imperatives.  They believe it is actually morally wrong to not be able to mess with their technology.  They believe that being told they can only use C++ is slavery.  Even if C++ is their favorite programming language in the world, not having a choice is wrong.

For Hack-Nots, optimization and configurability are a distraction. Putzing around with settings is a waste of time.  They do not want to mess with technology that already works.  They do not care that software can only be written in C++.  They do not know what C++ is, and they will never care.

Until the last five or ten years most computing technology was made by, and for, Hacks.  Recently this trend has changed. Most technology is still made by Hacks, by definition.  Somewhere, however,  someone with an eye for the desires and dollars of the Hack-Nots took notice and is now telling the Hacks what to make.

Not in all cases, of course.  Most technology is still Hacks-only.

But the Hack-Nots are coming, and technology is on its way to meet them.  Hack-Nots will drive the marketplace simply because they are more numerous than the Hacks.

Book Review: “Hardware/Firmware Interface Design”

I just finished Hardware/Firmware Interface Design: Best Practices for Improving Embedded Systems Development, by Gary Stringham.  Gary sent me a review copy of the book, btw, but I get no money for reading or reviewing it.  Though if you buy the book via my Amazon link, I get a bit of cash.

Anyway – the book is very good.  Gary says, “This book is written by a firmware engineer but is directed primarily to hardware engineers.”  I’ve been a hardware engineer and a firmware engineer, and I think both groups should read this book.

Gary has been in the trenches of firmware/hardware co-design for 20+ years and this book shows it.  The book gives 300+ “Best Practices” which are actually usable and practical – a departure from many software or hardware design books.  Gary talks about low-level concepts like interrupts, register definitions, and debugging, as well as higher level concepts like planning, documentation, and block partitioning across multiple product generations.

Summary: You should read this book if you’re a hardware or firmware engineer.

This is one of the books that I’ll probably revisit a couple of times a year to refresh myself on A Right Way to do hardware/firmware co-design.

‘Nuff said.

Book Review: Accelerando

I just finished reading Accelerando by Charles Stross for the second time.

It’s a scifi novel which starts in the near-future with the first hints of computers augmenting man’s intelligence.  The Singularity draws near as man becomes more integrated with machine  – posthumans are born.  Well, not born, more like evolved.  Humans and intelligence change more rapidly than many can cope with.

The most fascinating idea from the book is that of cognitive forking (my phrase, not Stross’s): people can “fork” threads of their own consciousness to carry out tasks in parallel to their primary consciousness.  When a forked thread of consciousness is done with its task it rejoins your primary consciousness and you instantly know whatever it learned.   Want to research several things at once?  Fork a thread for each task, wait a little while, and voilà!  You’re smarter in 1/Nth the time than if you’d just had your primary consciousness.

The book also discusses what happens to people who are unwilling or unable to keep up with the ever-faster changes in technology and humanity:

“The faux-young boomers feel betrayed, forced back into the labor pool, but unable to cope with the implant-accelerated culture of the new millennium, their hard-earned experience rendered obsolete by deflationary time.”

“Capitalism doesn’t have a lot to say about workers whose skills are obsolete, other than that they should invest wisely while they’re earning and maybe retrain: but just knowing how to invest in Economics 2.0 is beyond an unaugmented human. You can’t retrain as a seagull, can you, and it’s quite as hard to retool for Economics 2.0.”

It is a GREAT book – one of the most original books I have ever read – highly recommended.

You can read the whole book online at Stross’s site.

I also recommend another book by Stross, Halting State.

Another theme change

I had to change my theme again today.

A few days ago I switched to a new theme that I really liked, “LonelyTree.” One of my favorite parts of that theme was the header graphic: a great big, beautiful, wise looking tree.

Today I got an email from Oliver Flores, an artist from Guadalajara, Mexico, saying that the image was his, and could I please take it down. His email was very polite, and he gave me this link to his original image: http://oliverflores.blogspot.com/2007/10/grow.html

A quick look told me that the LonelyTree theme seems to have ripped off Oliver’s image, so I changed my theme and sent Oliver info on where I got it.

I browsed through some of Oliver’s other art, and it’s really good! You should definitely check it out. So even though I lost a great header image (for good reason!), I have a new artist to follow.