ECEN 5623

Assignment #1 -- RM/DM Scheduling Feasibility Tests

Submission Format: Plain text, Rich text, PDF, or MS Word

Code Format: Turn in all code in a tar or zip file!

Upon Completion upload to culearn.colorado.edu, "Lab Assignments, Lab 1".

(If there is a problem with culearn, then E-mail to siewerts@colorado.edu with subject line "LAB SUBMISSION 1" (subject line must be all caps exactly as it appears between quotes) and CC the TA.)

Be sure to include all source code with your submission.

All Group Design Assignments should be uploaded to culearn.colorado.edu, ECEN5623, "Lab Assignments, Project 1".

(If there is a problem with culearn, then E-mail to siewerts@colorado.edu with subject "GROUP SUBMISSION 1")

Project submission should be in an MS Word or text document with all group members clearly identified on a cover page! Only ONE submission needs to be made for all in the group.

LAB ASSIGNMENT (Individual Problem)

Lab learning objectives are: familiarization with Rate Monotonic and Deadline Monotonic policy and feasibility tests, understanding of sufficient vs. necessary and sufficient feasibility, and basic methods for developing, cross-compiling, downloading, and debugging Beagle xM target ARM code cross-compilation and cross-debugging tools. Alternatively you can use native compile and debug tools running directly on your target, so choose one, and for extra credit compare both methods in terms of efficiency and ease of use.

Please read Deadline Monotonic Scheduling by Neil Audsley and the Real-Time Embedded Components and Systems text, Chapter 2, Processing section.

For each feasibility test, allocate sufficient memory to allow up to 20 tasks to be tested by your code. Give me evidence that you have tested each one of your feasibility tests by writing a driver to call the tests with examples from one of the papers, or your own example. The code may be automatically tested for grading, so it must conform to the naming and parameter specification given here and must be in the files requested -- Thanks!

  1. [5 pts] Read Audsley Deadline Monotonic Theory paper and provide a single paragraph summary on why this mathematical formulation is easier OR harder to understand than the LUB derivation.

  2. [10 pts] Code the sufficient RM scheduling feasibility test (Liu and Layland paper p.9, Theorem 5) for following ANSI C function prototype:

    int RM_sufficient(

    int Ntasks,

    int *tid,

    unsigned long int *T,

    unsigned long int *C,

    unsigned long int *D);

    Where Ntasks is the number of tasks in the task set, tid is an array of unique task Ids, T is an array of the release periods, C is an array of the computation times, D is an array of the deadlines (T must equal D for each tid in RM). Finally, the function should simply return 1 if the system can be scheduled, and 0 if it can’t.

     

  3. [10 pts] Code the sufficient DM scheduling feasibility test (Audsley-1990, eq. 8) for following ANSI C function prototype:

    int DM_sufficient(

    int Ntasks,

    int *tid,

    unsigned long int *T,

    unsigned long int *C,

    unsigned long int *D,

    double *S);

    Where parameters are defined again as in #2 and S is an array the code populates with the scheduling feasibility of each task (i.e. the demand this task places on the CPU plus all interference with this task by tasks of higher priority).

     

  4. [10 pts] Code the Completion Time Test (chap. 2 of RTECS text, Processing section) for the following ANSI C function prototype:

    int Sched_completion(

    int Ntasks,

    int *tid,

    unsigned long int *T,

    unsigned long int *C,

    unsigned long int *D);

    Where parameters are defined again as in #2. Assume that T must equal D in all cases.

  5. [15 pts] Provide test cases and show output results for runs of #2, #3, and #4 both on your native Ubuntu Linux system AND on your Beagle xM target.

  6. [10 pts] Describe in your own words what the difference is between a "sufficient" and a "necessary and sufficient" scheduling feasibility test. Also explain how the RM Least-Upper-Bound is just sufficient and scheduling point is necessary and sufficient. Be very complete and mathematically and algorithmically accurate in your description.

  7. [10 pts] Why is the sufficient RM least upper bound so pessimistic? (Please give three specific reasons), but also explain why it still may be very useful.

  8. [10 pts] If EDF can be shown to meet deadlines and potentially has 100% CPU resource utilization, then why is it not typically the hard real-time policy of choice? I.e. what are drawbacks to using EDF compared to RM/DM? (Give at least two reasons) In an overload situation, how will EDF fail?

  9. [20 pts] Provide screen-dumps to prove that you have been able to 1) install Eclipse with the CodeSourcery tool-chain for ARM, 2) build C code projects, 3) download them for exeuction, 4) and single step cross-debug them on the target. Alterntaively, you can complete this exercise on the Beagle xM running graphics and a native compiler and debugger if you prefer providing capture of your session with screen dumps or the "script" command on your Beagle xM. For 5 points of extra credit, please compare the two methods in terms of ease of use and efficiency.

     

    DESIGN ASSIGNMENT - High-Level Design (Group Problem) -- Turn in either a Block Diagram or DFD (Data Flow Diagram) showing both hardware and software elements in your group project (one copy per group). Separately, turn in a paragraph describing your role in this high-level design.

    Please turn individual paragraph in by uploading to culearn Project 1.