18-348 Lab #9

Spring 2014

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.

Note: DIP switch lettering on the CPU module has confused students in the past because the switches are active low and have weird markings. The switch being down on the side with the arrow head means the switch is OFF (GetSwitches() returns 0), and the switch being down on the side with the numbers (where it says "Off") means the switch is ON (GetSwitches() returns 1)


Important Notes:

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 (note that you only need one, so only one partner needs to have one). If neither partner has a working multi-tasker after the prelab due date be sure to come to office hours and get help completing it so you can do the lab.

"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.  The performance of the tasker can be improved by implementing the generic concept of a "sleep" function (also called "yield"), 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 SWI-based sleep function for the preemptive multi-tasker, and call that sleep function in taskTerminate. By 'SWI-based' we mean that yielding back to the scheduler shall be done by executing the SWI instruction. 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 prelab_9_bonus_andrewID.c.

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:
Final projects can NOT involve any of the following:

Note about RTOS projects:An example of an RTOS project would be to implement a mutex with priority ceiling protocol and use the counter/timer to initiate periodic tasks. Note that all other requirements for the project still hold (correct watchdog usage, interrupt, etc). An example of an interrupt includes: using SWI to implement yield. There are other possibilities (such as serial) but we point these out because to show that they are OK to count

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 + 10 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. 

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 by 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, the TAs will help you get the tasker working. If this happens be sure to get help as early as possible

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: Ensure your prelab bonus yield function works in the prioritized preemptive tasker (update it if needed).

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.

  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) Optional. Include your code listing as lab_9_bonus_gXX.c. Your sleep call must use an SWI and 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.


Change notes for 2014: