Swipe-card readers

The swipe-card reader driver is a fairly simple program—it waits for a card to be swiped through the hardware, and then collects the card ID. While the driver itself is reasonably simple, there's a major design point we need to consider that's different than what we've seen so far with the door lock driver. Recall that the door-lock driver acted as a data sink—the control process sent it commands, telling it to perform certain actions. With the swipe-card reader, we don't want it to be a data sink. We don't want to ask the swipe card reader if it has data yet; we want it to tell us when someone swipes their access card. We need the swipe-card reader to be a data source—it should provide data to another application when the data is available.

To understand this, let's think about what happens in the control program. The control program needs to know which user has swiped their card. If the control program kept asking the swipe card reader if anything had happened yet, we'd run into at a scalability problem (via polling), and possibly a blocking problem.

The scalability problem stems from the fact that the control program is constantly inquiring about the status of the swipe card reader. This is analogous to being on a road trip with kids who keep asking “Are we there yet?” It would be more efficient (but far more unlikely) for them to ask (once!) “Tell us when we get there.”

If the control program is continually polling, we're wasting CPU cycles—it costs us to ask, and it costs us to get an answer. Not only are we wasting CPU, but we could also be wasting network bandwidth in a network-distributed system. If we only have one or two swipe-card readers, and we poll them once per second, this isn't a big deal. However, once we have a large number of readers, and if our polling happens faster, we'll run into problems.

Ideally, we'll want to have the reader send us any data that it has as soon as it's available. This is also the intuitive solution; you expect something to happen as soon as you swipe your card.

The blocking problem could happen if the control program sent a message to the reader driver asking for data. If the reader driver didn't have any data, it could block—that is, it wouldn't reply to the client (who is asking for the data) until data became available. While this might seem like a good strategy, the control program might need to ask multiple reader drivers for data. Unless you add threads to the control program (which could become a scalability problem), you'd have a problem—the control program would be stuck waiting for a response from one swipe-card reader. If this request was made on a Friday night, and no one swiped in through that particular card reader until Monday morning, the control program would be sitting there all weekend, waiting for an answer.

Meanwhile, someone could be trying to swipe in on Saturday morning through a different reader. Gratuitously adding threads to the control program (so there's one thread per swipe card reader) isn't necessarily an ideal solution either. It doesn't scale well. While threads are reasonably inexpensive, they still have a definite cost—thread-local memory, some internal kernel data structures, and context-switch overhead. It's the memory footprint that'll have the most impact (the kernel data structures used are relatively small, and the context-switch times are very fast). Once you add these threads to the control program, you'll need to synchronize them so they don't contend for resources (such as the database). The only thing that these threads buy you is the ability to have multiple blocking agents within your control program.

At this point, it seems that the solution is simple. Why not have the swipe-card reader send a message to the control program, indicating that data is available? This way, the control program doesn't have to poll, and it doesn't need a pool of threads. This means that the swipe-card reader is a “data source,” as we suggested above.

There's one subtle but critical point here. If the reader sends a message to the control program, and the control program sends a message to the reader at the same time, we'll run into a problem. Both programs sent messages to each other, and are now deadlocked, waiting for the other program to respond to their messages. While this might be something that only happens every so often, it'll fail during a demo rather than in the lab, or worse, it'll fail in the field.

Why would the control program want to send a message to the swipe-card reader in the first place? Well, some readers have an LED that can be used to indicate if access was allowed or not—the control program needs to set this LED to the correct color. (Obviously, in this example, there are many ways of working around this; however, in a general design, you should never design a system that even has a hint of allowing a deadlock!)

The easiest way around this deadlock is to ensure that it never happens. This is done with something called a send hierarchy. You structure your programs so those at one level always send messages to those at a lower level, but that those at lower levels never send messages to those at higher (or the same) levels. In this way, two programs will never send each other messages at the same time.

Unfortunately, this seems to break the simple solution that we had earlier: letting the swipe-card reader driver send a message to the control program. The standard solution to this is to use a non-blocking message (a QNX Neutrino-specific “pulse”). This message can be sent up the hierarchy, and doesn't violate our rules because it doesn't block the sender. Even if a higher level used a regular message to send data to a lower level at the same time the lower level used the pulse to send data to the higher level, the lower level would receive and process the message from the higher level, because the lower level wouldn't be blocked.

Let's put that into the context of our swipe-card reader. The control program would “prime” the reader by sending it a regular message, telling it to send a pulse back up whenever it has data. Then the control program goes about its business. Some time later, when a card is swiped through the reader, the driver sends a pulse to the control program. This tells the control program that it can now safely go and ask the driver for the data, knowing that data is available, and that the control program won't block. Since the driver has indicated that it has data, the control program can safely send a message to the driver, knowing that it'll get a response back almost instantly.

In the following diagram, there are a number of interactions:

  1. The control program primes the swipe-card reader.
  2. The reader replies with an OK.
  3. When the reader has data, it sends a pulse up to the control program.
  4. The control program sends a message asking for the data.
  5. The reader replies with the data.
Figure 1. A well-defined message-passing hierarchy prevents deadlocks.

Using this send hierarchy strategy, we have the swipe-card driver at the bottom, with the control program above it. This means that the control program can send to the driver, but the driver needs to use pulses to transfer indications “up” to the control program. We could certainly have this reversed: have the driver at the top, sending data down to the control program. The control program would use pulses to control the LED status on the swipe-card hardware to indicate access granted or denied.

Why would we prefer one organization over the other? What are the impacts and trade-offs?

Let's look at the situation step-by-step to see what happens in both cases.