CSC512 Homework: Real-Time Analysis Part 2

Due May 4, 2003



  1. Consider two task systems:
      2.  
      Task Period Exec. Time
      task1 8 3
      task2 9 3
      task3 15 3

       
      Task Period Exec. Time
      task1 8 4
      task2 12 4
      task3 20 4
      For each task analyze its schedulability using Cheddar . Generate a Cheddar screenshot for the analysis including both Scheduling feasibility and Scheduling simulation. Generate the Cheddar xml file called prob1_yourname.xml for this problem.

  2. Consider the task system:
    3. with rate-monotonic scheduling and priority ceiling resource management.
    1. Are the tasks schedulable (Yes/No)? Explain your answer using RM analysis.  You do not need to use Cheddar for this question.

      2.  
    2. What is the blocking time of task4? Why?

     
  3. Consider the task system:
    4. The notation [X,3[Z,1]] in task3 means that task3, which has 5 total units of execution time, has resource X for 3 of those 5 units, and it has resource Z for one of the 3 units that it also is holding X. RapdiRMA will want to know the exact interval during which each resource is used, but the exact interval during which the task uses a resource does not matter in analysis, so you can use any intervals that match the specifications. For instance, for task3 you could specify that it uses X from 1 to 4 and that it uses Z from 2 to 3.

    Assume rate-monotonic scheduling and priority ceiling resource management.
     

    1. Generate a Cheddar screenshot for the analysis including both Scheduling feasibility and Scheduling simulation. Generate the Cheddar xml file called prob2a_yourname.xml for this problem.

    2. Explain the results from a using the theory from Liu's book.

      3.  
    3. Assume that priorities 1,2,3, and 4 are assigned to the tasks (using rate monotonic assignment), with priority 1 being the highest. What is the priority ceiling of each resource?

  4. For the given system of jobs and resources, demonstrate how the Basic Priority Ceiling Protocol (BPCP) and the Read/Write Priority Ceiling Protocol (R/W PCP) work.

    Resources:

    R1, R2, and R3.

    Jobs:
    J1 = (3, 4, [Lread(R1), 3])
    J2 = (1.5, 4, [Lread(R2), 3 [Lwrite(R1), 2]])   J3 = (0, 4, [Lread(R1), 3 [Lwrite(R3), 1]])

    For both the BPCP and the R/W PCP, do the following:

    1. Compute the priority ceilings for each of the resources.
      • For BPCP, the locks indicated for each job will be exclusive locks, since BPCP does not handle read and write locks.
      • For R/W PCP, compute the write priority ceiling and the absolute priority ceiling for each resource.
    2. Draw a time-line showing the execution of each of the jobs. Use shading as in book examples to indicate different resource accesses.
    3. Write a description of the time-line for every point in time at which a significant event occurs, i.e. a lock is requested, a job is preempted, etc.
      • Be sure to indicate any priority inheritance that occurs.
      • Also indicate the dynamically calculated r/w priority ceiling when appropriate.
    4. In this example, what benefit did using the R/W PCP provide the system, if any?
    5. Under what conditions would the Affected Set Priority Ceiling Protocol (ASPCP) be beneficial in this example?

      6.  

  5. For the given system of jobs and resources, determine schedulability of the system.

    In this problem, high number indicates high priority. Thus, task T4 has highest priority, and task T1 has lowest priority. The following picture illustrates the architecture of the system:

    The following table describes the system parameters:
     
    Task Period Rel. Deadline Exec. Time Node Resources
    T1 53 53 6 2 S2 [1->5]
    T3 51 51 9 1 S1 [1->4]
    T4 25 25 5 2 S1 [1->2],S2 [2->5]

    Determine the schedulability of the system of tasks.  Turn in a detailed description of the schedulability test for task T3.  You are not required to use Cheddar for this question, but you may want to use it to check your work.
     

  6. Do Liu 9.2 (b,c,d)

  7. Do Liu 9.5

  8. Do Liu 9.11 (a,b)

     
What to Hand In
     
      Hand in a printed version the homework (in person or to Dr. Fay-Wolfe's mailbox) by May 4. Also email me (wolfe@cs.uri.edu) the Cheddar files prob1_yourname.xml prob2a_yourname.xml that you generated.