What is the Shared Data Problem?

sharing

Table of Contents

Before we discuss the shared data problem when building embedded systems, it is important to understand what interrupts are.


What are Interrupts?

The most basic embedded software has a main program that runs uninterrupted…that is, it runs until either it stops on its own or something else causes it to stop.

For example, if you unplug your refrigerator, all programs that were running will immediately stop, and the refrigerator will shutdown. Otherwise, while the refrigerator is plugged in, programs will continue to run uninterrupted. This is called embedded software without interrupts.

You also have software where the main program executes normally but stops either periodically or due to some code (that is not part of the main method) that must get executed immediately. The main program stops, some other code is executed…(i.e. code that is not part of the main program). We call this an interrupt service routine. When this interrupt service routine is finished, control is shifted back to the main program, and the main program gets back to doing what is was doing prior to being interrupted.

Here is an image that shows what I just explained:

interrupt_service_routine

You likely trigger interrupt service routines all of the time without even knowing. For example, normally your desktop computer runs various background programs when you are not on your computer. Let’s call this the main() program. As soon as you click your mouse or type on your keyboard, you trigger an interrupt service routine. The computer handles this interrupt service routine by exiting the main() program temporarily, reading what you just did and doing what you commanded it to do (i.e. servicing the interrupt).

After that, the computer exits the interrupt service routine, goes back to doing what it was doing before you interrupted it (i.e. control shifts back to the main() program). That is a lot like how interrupts work in embedded systems, and you will find them in many if not most embedded programs in some form or fashion.

Return to Table of Contents

The Shared Data Problem

A big problem in embedded systems occurs in embedded software when an interrupt service routine and the main program share the same data. What happens if the main program is in the middle of doing some important calculations using some piece of data…an interrupt occurs that alters that piece of data…and then the main program finishes its calculation? Oops! The calculation performed by the main program might be corrupted because it is based off the wrong/different data value. This is known as the shared data problem.

Real-World Analogy: Running a Bakery

Imagine you own a bakery. You are trying to calculate how much money you made in 2018. You have just entered the revenue for each month listed in a Google spreadsheet. It looks like this:

Addison’s Bakery 2018 Revenue By Month

  • January: $10,000
  • February: $10,000
  • March: $10,000
  • April: $10,000
  • May: $10,000
  • June: $10,000
  • July: $10,000
  • August: $10,000
  • September: $10,000
  • October: $10,000
  • November: $10,000
  • December: $10,000

You get out your handy calculator.

calculator
“calculator” by stockcatalog is licensed under CC BY 2.0 

Starting with January through March, you add the first three months of revenue into your calculator “10000 + 10000 + 10000 +” and then all of a sudden, your assistant (whose job it is to keep revenue updated periodically), interrupts you and asks if he can update something in the spreadsheet. You say, “Sure.”

You get up from your chair and go to the break room.

In the meantime, your assistant (i.e. the “interrupt service routine”) then gets on your computer.

While you are in the break room, your assistant changes the revenue on your spreadsheet in January 2018, increasing it from $10,000 to $15,000. He then leaves the room.

You then return from the break room. You get back in your chair and continue entering in the numbers in your calculator for the other nine months, for April through December. You conclude that the revenue for 2018 was $10000 per month for 12 months (i.e. $120,000). You record that number so that you can use it for your tax filings. Oops! See the mistake?

The main program (i.e. you) was unaware that the interrupt service routine (i.e. your assistant) made a change to the January 2018 revenue data, so the value of $120,000 is not consistent with the updated data. It should be $125,000 not $120,000.

This in a nutshell is the shared data problem. We need to make sure that you, the main() program, are NEVER interrupted while you are in the middle of making important calculations on your calculator. You and your assistant both share responsibility for making sure revenue is accurate, but we need to make sure you both aren’t working on the revenue at the same time.

In the real world, this would take the form of you posting a “DO NOT DISTURB” sign on your door to keep your assistant out when you are making critical calculations. In software engineering, we call this “disabling interrupts.” While interrupts are disabled, nothing can interrupt the main program.

Disabling interrupts is like the main program putting up a big DO NOT DISTURB sign. Source: Wikimedia Commons

Real-World Example: Designing an Automatic Doggy Door

doggy_door

Let’s look at a real-world example to further show you the shared data problem.

Problem

Imagine you are a software engineer working at a company. Your team is responsible for designing an automatic dog entry door. This embedded device can be wirelessly updated with RFID tags for dogs or other pets to be allowed entry.

The door needs to automatically unlock for dogs that are in the vicinity of the door. A pet must be allowed to enter even when the table of RFID tags is being updated. The RFID tag IDs are shared data since the interrupt service routine that must update the tag IDs and the main() program that is responsible for automatically unlocking the door when dogs are in the vicinity both share and use this data. A problem will occur when the doggy door is in the middle of an RFID tag ID update when a dog needs to get through the door. We wouldn’t want to let the poor dog wait outside in the freezing cold while the device is in the middle of an RFID tag update!

How do we create a solution that solves the shared data problem? The RFID tags need to be updated regularly but that same data is needed regularly by the main() program to let dogs enter when they need to. Let’s solve this now.

System Requirements

rfid_tags
Dogs wearing RFID tags/cards need to be able to enter the door (i.e. gate) when they get close to the doggy door.
  • This embedded device can be wirelessly updated with RFID tags.
  • Dogs or other pets must be allowed entry when they are in the vicinity of the door.
  • Dog must be allowed to enter even when the table of RFID tags is being updated.
  • RFID tag IDs are shared data which must be managed.

In the shared data problem for the doggy door controller, we need to make sure the dog can enter at all times while the RFID tags are being updated. Because this is a dog, it is unacceptable for the door to remain locked and keep a dog waiting.

Implementation

To solve this problem, I would design the following loop for the main program in pseudocode:

While (True)

  // Begin Critical Section of Code - Can't Be Interrupted
  Disable_interrupts()
  
    Scan to see if dogs are in the area (i.e. RFID scan)
      If a valid dog is in the area, unlock the door
      Else, do nothing
 
  // End Critical Section of Code That Can't Be Interrupted
  Re-enable_interrupts()

  Update RFID table (interrupt service routine)
  // In the meantime, dog is walking through the door
  
  Check if the door is unlocked
    If the door is unlocked, delay 30 seconds to give 
    the dog sufficient time to enter

  Make sure the doggy door is locked
  
  Go back to the beginning of this loop

The above architecture satisfies the requirements and enables a dog to enter even when the table of RFID tags is in the middle of an update.

Return to Table of Contents