18-348 Lab #9

Fall 2009

This lab is based on Lecture 15 - Cooperative and Preemptive Context Switching and Lecture 16 - Concurrency.

Links to all files referenced in the lab and prelab can be found in the Files section at the end of this document.

Important Notes:

This lab is entirely new for 2009:  That means it probably has a few bugs, although we have worked hard to keep them to a minimum.  If you see something that looks like a problem please report it via e-mail to the course staff, make a reasonable assumption, and attempt to proceed. We will reply and (if necessary) fix problems as soon as we can.  One of the things we have done is created a complete solution to the non-bonus portions before assigning the lab, so we know for sure that the solution can be done the way we suggest you do it.  But, there are many possible solutions, and any solution that meets the requirements is OK.

Purpose:  Several employers have told us the one thing students don't do enough of as undergrads is look at someone else's code and fix it.  As it turns out, engineers in industry spend more time maintaining existing code than in writing new code.  So, this lab is designed to both (a) help you understand how multi-taskers work, and (b) give you some experience understanding and modifying existing code representative of what you might see in a reasonably good code base out in industry.

Lab depends on correct pre-lab: You need a working multi-tasker to complete the main lab.  We VERY STRONGLY suggest you do the following if you have problems with the prelab.  If you can't get your multi-tasker to work by end of recitation (1:30 PM) on the Friday that the prelab is due, you can ask for a solution sheet from a TA that shows you how to implement the missing pieces of the preemptive tasker (not other parts of the prelab; just that part).  Getting this hint will cost you all the points for that section (preemptive tasker section) of the prelab.  But, without knowing that information, you will have a lot of trouble getting the lab to work, and you'd lose the points anyway.  If you receive the hint you are NOT allowed to show it to anyone else, ever.  The hints are only available at scheduled office hours, and the TA must mark you off as having received it.  Both team members must agree to accept the hint (which will affect both of their prelab scores; but if one team member knows how to do it, you don't need the hint for the lab portion).  If both team members are not present in person, e-mail from the missing team member to the course staff suffices as permission for the other team member to pick up the hint.  One person must be physically present to receive the hint; it will not be provided via e-mail.  We hope nobody needs the hint, but it is there if you need it.

"Spreadsheet math": When we say "spreadsheet math" we mean math based on calculations that can be reported via a spreadsheet-format part of your Acrobat file writeup. We specifically intend this to mean you don't have to show us a generalized mathematical formula; you just need to show your work in justifying a particular numerical answer.  ONLY the acrobat file will be considered in determining your grade.

Code: The code has several different variants all in the same file.  This technique helps ensure that bugs found in one variant are fixed in other variants, which is easy to get wrong if each variant is a different copy of the code.  We'll admit that usually there are fewer variants, but this approach does have its place.  If you are confused by all the #ifdefs it is OK to simply delete all the ignored chunks of code for a variant when trying to understand it.  But the answers you turn in must have all variants in a single .c file as this one does.

You may find it easier to check your answers visually by slowing down tasks so you can see the light patterns more easily (e.g., by increasing compute time for every task and also increasing the period of every task correspondingly). But, be sure to restore periods and task lengths before handing in your results.

Pre-Lab:

Goal:

Discussion:

In this pre-lab, you will work individually to understand and implement various types of multi-taskers.  Refer to the appropriate lecture for more details about cooperative and preemptive multi-tasking and concurrency. 

The point of the pre-lab questions is to get you to closely study the provided code and understand it.  Most questions request you make a change to the source code and sometimes answer a question based on doing that. Changes to the source code should be handed in as part of your single program hand-in except where noted.  Do NOT make changes to the code EXCEPT where you are told to do so.  In some cases you will merely need to copy existing code from a different compilation case in the provided code and perhaps change it a little.  That's OK -- the point is for you to understand similarities and differences between approaches.  Note that this is a pre-lab and you should NOT be exchanging solution information with anyone else, including your lab partner until after you have both turned in your pre-labs.

Procedure:

Create a new C project in Code Warrior.  Download the lab_9_skeleton.c, rename it to prelab_9_andrewID.c and replace the default main.c.  Make sure you include the modclock library in your project.

This program runs on the stand-alone course module and does not require the project board at all.  When compiling and running your code on the module, make sure you select the TBDML option and plug the USB cable directly into the module.  Also, double check that your module jumpers are set to enable both BDM jumpers and power the module via the TBMDL port.

Part 1: UNTIMED_CYCLIC_EXEC
  1. Enable #define UNTIMED_CYCLIC_EXEC
  2. Comment out all other #defines
  3. This should produce code that runs an untimed round-robin ordering of all enabled tasks
  4. Compile and run this version. Play with the DIP switches to see what they do individually and in combination.
Q1. Set all switches ON (all tasks enabled).  Tell us the pattern of LED displayed for the first two cycles (which order, and any pauses you observe).

Q2. Use a spreadsheet approach to predict timing for the first 2 seconds of running.  Just list start time and which task is running in msec (or "idle" if no task is running). For example:

TIME (msec)   Task starts
   0           3
 227           4
 ...          ...

Download this example spreadsheet if you like (blue boxes are calculated automatically; we've filled in a few boxes for you so you can see how the spreadsheet works).  If the program doesn't match your spreadsheet prediction, think about why that might be.

To use the simulator, Enable #define SIMSWITCHES, which always returns all switches true for simulation purposes

Use the simulator to find when each task executes and correct your spreadsheet (accuracy to the nearest 1 or 2 msec is fine).  Hint:  use a breakpoint at the start of each task.  You'll need to use the simulator to figure out when the first task starts executing for your predictions. Make sure you set the simulator clock frequency to display msec instead of clock ticks!

Hand in the final, corrected spreadsheet as part of your PDF.


Part 2:  CYCLIC_EXEC
  1. Enable #define CYCLIC_EXEC
  2. Comment out all other #defines
  3. This should run an untimed round-robin ordering of all enabled tasks, BUT that has a fixed period for running that loop
Q3. For Task0 (the scheduler), fill in missing code for the CYCLIC_EXEC case.

Q4. For the main loop, fill in the missing code for the CYCLIC_EXEC case.

Q5. Compile and run this version. Play with the DIP switches to see what they do.  Set all switches ON (all tasks enabled).  Tell us the pattern of LED displayed for the first fifteen seconds (which order, and any pauses you observe).  Use this order and rough timing to decide if you implemented things correctly.

Q6.  Why is there a long pause before LEDs start to light up?


Part 3: MULTI_RATE_COOPERATIVE
  1. Enable #define MULTI_RATE_COOPERATIVE
  2. Comment out all other #defines
  3. This code should run as-is.  You do not have to add code for this to work.
  4. This should produce code that runs an multi-rate cooperative tasker. The execution order will be round-robin of all active tasks.  Each active task will be run at its defined period.  Each tasks' period starts whenever it is activated, but flipping the switches quickly will not cause tasks to re-run any sooner than their defined periods.
  5. Compile and run this version. Play with the DIP switches to see what they do individually and in combination. 

Q7. Turn on ONLY Dip Switches #1 and #4.  How many times does LED #1 blink compared to #4.  Explain why this makes sense.  (Hint, consider how long LED #1 stays illuminated for each blink carefully.)

Q8. Use a spreadsheet approach and the simulator, record the timing of the first FIVE executions of EACH task.  For each of those five executions, state whether it met its periodic deadline.  A tab on the example spreadsheet may help you with this.  The information we are looking for is, for example:

Task #2
Period start      Actual Start     Deadline Met?
  60.3              60.4             OK
 560.3             1954.0           MISSED!
   ...

Please note we do not want you to report more than the first FIVE of EACH task (30 times in all).  


Part 4: PRIORITIZED_COOPERATIVE
  1. Enable #define PRIORITIZED_COOPERATIVE
  2. Comment out all other #defines
  3. This should produce code that runs a prioritized cooperative multi-tasker
Q9.  For Task0 (the scheduler), fill in missing code for the PRIORITIZED_COOPERATIVE case.

Q10. For the main loop, fill in the missing code for the PRIORITIZED_COOPERATIVE case.

Q11. Record the following for Task 2 using the simulator and report them in spreadsheet format:  Period start, actual starting time, whether deadline was met.  Record from from 0 to 13000 msec.  There is a template spreadsheet tab to help you if you wish to use it.  Explain why Task 2 is missing deadlines where it is, and why it doesn't miss them as many times in a row as you saw with the MULTI_RATE_COOPERATIVE case.


Part 5: PREEMPTIVE
  1. Enable #define PREEMPTIVE
  2. Comment out all other #defines
  3. This runs a round-robin preemptive multitasker, which means that every active task gets an equal amount of time if it is active.
  4. The compiler will generate a couple warnings about the inline assembly making the debugger's life hard; it is OK to ignore those warning (but not others!)
Q12. For the function SetLED, re-enable interrupts at the correct location.  Why did they need to be disabled?

Q13. Fix the bug in TimeNow (missing code -- the statement that is there is correct as far as it goes).  Why is that change necessary?

Q14. For the function CreateLaunchStack, fill in the missing lines of code to set up data on the stack that will enable an RTI to run a suspended task. 

The purpose of this question is to encourage you to look through the code and understand what is going on as an example of a preemptive multitasker.  It will take some thought to understand all this; leave time to absorb and reflect on what is going on here.

Q15. The round-robin PREEMPTIVE scheduler should be working now.  Run it on the hardware. Play with the switches and convince yourself that it is working in a reasonable way.  What simple visual observation tells you that it is preemptive?  What simple visual observation tells you that the CPU is loaded less than 100%?

Q16. After you get the PREEMPTIVE version working, try this experiment. Comment out the infinite loop ("for(;;){}") in the definition of the procedure TaskTerminate. What happens?  In 25 words or fewer, why do we need this loop for things to work properly?

BONUS Q17. (Optional) This code is brand new this semester. If you find a bug in our code, please report it.  We'll bestow bonus points in proportion to the severity of the bug, with points going to the first student who reports it via e-mail.  Style bugs will get a few points; functionality bugs will get more points.  We've run the code and think it is reasonably solid, but there are no doubt some subtle things lurking there (which is why you really don't want to write your own RTOS for a real product!)  If you find bugs after you hand in your pre-lab report, it is OK to report them later and we'll figure out a reasonable reward strategy.  In keeping with bonuses in previous labs, the maximum bonus awarded to any one person will total no more than 10% of the pre-lab grade.

Lab 11 Brain Storming

This part of the pre-lab should be performed with your partner (both partners must include the lab 11 idea in their pre-lab).  You and your partner should come up with an idea for the final project. We're looking for simple projects that encompasses approximately two weeks worth of lab work.  Feel free to ask the instructor or TA's for suggestions or feedback on ideas.

This is not a full design proposal, we just want a brief idea of your project.

The final project must incorporate three or more of the following items in List 1:

List 1:
Your design must also incorporate:
•
Remember:  Killer complexity is not required for this project.  Clever is nice.  Cool is nice.  On time is more important than any of the above.  Above all else, your project must work by the demonstration deadline and must be well documented.

Hand-in Checklist: (170 + 17 points)

All non-code submissions shall be in a single PDF document.

  1. (160 points - 10 points per question) Complete questions Q1 - Q16 and include your answers in the following two files. 
  2. (Bonus: Up to 17 points) Include any bugs you find as question Q17 or a fix for the example bug in your prelab write-up file.  For the example bug, also submit a C file with obvious comments indicating your solution.
  3. (4 points) Include a brief description of your idea for lab 11 (50 words or less) in your prelab_9_andrewID.pdf.  You will receive full credit for any idea that fits the above criteria. 
    NOTE:  We will ONLY look at the first 50 words.  Keep it short.
  4. (2 points) Include at least three items from List 1 you expect to include in your lab 11.
  5. (2 points) List at least two interrupts that would be useful for your project for lab 11.
  6. (2 points) State whether your idea would require additional components not found in lab.  If so, mention these extra components in your brief project description.  Remember, any additional components must be approved by staff.

Refer to the LAB FAQ for more information on lab handin procedures and file type requirements.  You MUST follow these procedures or we will not accept your submissions.

Lab:

Goal:

Discussion:

The pre-lab skeleton you were given has a working multi-tasker (after you fill in the missing pieces). The primary design criterion for the multi-tasker was to be something you could understand as an extension of the cooperative tasking ideas.  That is why it uses the same data structures and a reasonably similar design approach.  But, this design approach is also the source of some fundamental limitations.  Some of these limitations can be fixed be redesigning it, and a redesign of that nature is the main focus of this lab assignment.

Reminder:  If neither partner was able to successfully complete the Part 5 Preemptive Multi-tasker, you can ask for a solution sheet from a TA that shows you how to implement the missing pieces of the preemptive tasker (at the cost of the points for that pre-lab section).

Procedure:

For the lab assignment, start by deleting all code that is ignored when the PREEEMPTIVE compilation profile is used (this is just to clean up the clutter).

Additionally, change the #define entries for periods so that PERIOD0 is 50 and PERIOD1 is 250 (instead of 5 and 20 as they were previously). (If you are curious, you can leave them at 5 and 20 and ask yourself why the lights never go on for Q2 below even though things worked fine for the pre-lab schedulers, but that is not a required part of this lab.)

Part 1:

Change the timer tick ISR so that the PREEMPTIVE scheduler implements a prioritized preemptive scheduler rather than a round-robin preemptive scheduler.  This means that on every timer tick, the task with the highest priority runs for the next time slice.  We suggest that you define any temporary variables such as loop variables as being static to avoid problems with stack usage in task switching.  You should NOT have to add any assembly language.

Q1. Hand in your code for the prioritized preemptive multi-tasker.  Save this version of your code as lab_9_q1_gXX.c (where XX is your group number).

Q2. Run the prioritized preemptive multi-tasker on the CPU module. How can you tell from the lights that it is prioritized rather than round-robin?

Q3. The multi-tasker in the skeleton runs the scheduler (Task 0) as a task.  This makes it simpler to understand the code compared to the cooperative multi-tasking examples we've shown you, but it is a source of performance problems, because Task #0 wastes a whole clock tick each time it runs as a task.  Rewrite the prioritized preemptive tasker so that Task #0 is called directly from the ISR rather than executed as a task.  Make sure that interrupts stay disabled until the end of the timer ISR.  Save this version of your code as lab_9_q3_gXX.c (where XX is your group number).

Q4. What is blocking time for the system you have created as a result of Q3?  Let's assume it is caused by the timer ISR.  Measure it using the simulator with breakpoints.  Take at least 10 measurements and report the longest blocking time you observe.  Why does the blocking time vary?

BONUS Q5. Optional.  The performance of the tasker can be improved by implementing the generic concept of a "sleep" function (also called "yeild"), which returns control to the tasker so that the remainder of the current time slice can be used by another task. In our use of the word "sleep" we do NOT mean sleep for a specified amount of time. Rather, we mean simply give up unused time in the time slice and let the tasker use it for another task instead. This is handy when a task terminates, and when a task is waiting for a mutex value.  Implement a sleep function for the prioritized preemptive multi-tasker, and call that sleep function in TaskTerminate. In your writeup, explain in 100 words or fewer the approach you took.  Use #ifdefs so that your code can be run with and without this change for the demo.  Save this version of your code as lab_9_bonus_gXX.c.

Demo Checklist: (50 + 5 points)

  1. (25 points) Demonstrate your lab_9_q1_gXX.c to the TA.  Show why it is prioritized now rather than round-robin.
  2. (25 points) Demonstrate your lab_9_q3_gXX.c to the TA.  Show how you measured your blocking time and what the results were.
  3. (Bonus 5 points) Optional.  Demonstrate your lab_9_bonus_gXX.c works and explain your implementation.

Hand-in Checklist: (105 + 10 points)

All non-code submissions shall be in a single PDF document. Each graph must have a title, your names, and correct, appropriate labels (describe the axis and give units, if any) to receive full credit.

  1. (5 points) List any problems you encountered in the lab and pre-lab, and suggestions for future improvement of this lab. If none, then state so to get these points.
  2. (40 points) Submit your code listing for Q1 as lab_9_q1_gXX.c.  You must follow the Coding style sheet to receive full credit.
  3. (10 points) Answer Q2 in your lab write-up.
  4. (30 points) Submit your code listing for Q3 as lab_9_q3_gXX.c.  You must follow the Coding style sheet to receive full credit.
  5. (20 points) Answer Q4 in your lab write-up.
  6. (Bonus: 10 points) Answer Q5 in your lab write-up and include your code listing as lab_9_bonus_gXX.c. You must follow the Coding style sheet to receive full credit.

Refer to the LAB FAQ for more information on lab handin procedures and file type requirements.  You MUST follow these procedures or we will not accept your submissions. 

Hints and Suggestions:

FILES for this lab:

Relevant reading:

Also, see the course materials repository page.