Homework 1 Solutions

The following problems will be due in class.

  1. A robotic vacuum cleaner has a motor control task that computes control laws for its drive motor, a contact task that detects when the robot's contact sensor is triggered by running into something, a battery status task that monitors the voltage on the battery and how much current is being taken from it, a planning task that determines the path the robot should follow, and a communication task that allows the user to set the time of day and dowload times of the day during which the robot should work. Classify each task as periodic, sporadic, or aperiodic and identify the relevant task parameters (e.g., a periodic task has a period, worst-case execution time, and relative deadline.) More than one answer may be correct, so you must justify your choices to get full credit.

    The control laws need to run at a frequency of 500 Hz. The load on the battery can change with every control law update. The robot should never travel outside the range it has planned. The planning task needs to run fast enough that the robot does not go more than 1 m between jobs in the planning task. Assume the top speed of the robot is 0.5 m/s. Be sure to describe any other assumptions you make.

    Several of the tasks had multiple acceptable answers. As long as you can give a good enough reason I will accept almost anything.
    Task Type Period Reason
    T1 Control Laws periodic 2 ms Needs to be updated with a frequency of 500 Hz
    T2 Contact sporadic N/A Run the task whenever the robot runs into something. There is no limit on how often the robot can run into things.
    periodic ≤ 2 ms The robot can only respond to running into things by changing the control laws, so there is no need to check for collisions more often than every 2 ms. The robot probably needs to run the planning task to figure out what to do, so it may make sense to wait for the planning task.
    T3 Battery status periodic 2 ms Power consumption could change based on the control laws, but probably not more frequently than that.
    T4 Planning periodic ≤ 2 s The robot takes at least 2 s to go 1 m at top speed. A 2 s period guarantees the planning task runs at least once per meter travelled. A shorter period may be useful to deal with moving obstacles like people or pets (or unexepected collisions.)
    aperiodic N/A It may be acceptable to have the robot pause if it cannot compute a new plan. If that is the case an aperiodic job may be an acceptable alternative.
    T5 Communication aperiodic N/A Nothing in the communication task depends on meeting a deadline.

  2. Do problem 3.1 in the book.

    Because sporadic jobs may have varying release times and execution times, the periodic task model may be too inaccurate and can lead to undue underutilization of the processor even when the interrelease times of jobs are bounded from below and their executions are bounded from above. As an example, suppose we have a stream of sporadic jobs whose interrelease times are uniformly distributed from 9 to 11. Their execution times are uniformly distributed from 1 to 3.

    1. What are the parameters of the periodic task if we were to use such a stask to model the stream?

      For the periodic task model we model a task using the lower bound on its period and the upper bound on its execution time (the worst case). In this case, the period, p = 9, and the exeuction time, e = 3.

    2. Compare the utilization of the periodic task in part (a) with the average utilization of the sporadic job stream.

      The utilization of a periodic task is its execution time divided by its period. In this case:

      Uperiodic = eperiodic/pperiodic = 3/9 = 0.3333

      Modeling the job as a stream of periodic jobs, the execution time is a random variable E uniformly distributed from 1 to 3 time units, and the period is a random variable P uniformly distributed from 9 to 11. Utilization is a random variable that is a function of E and P. In particular, Usporadic = E/P. In general we can find the average value of U, E[U], we need to integrate u ⋅ fu(u), the probability density function of U from -infinity to infinity.

      You can use the rules of probability to determine fu(u) from fe(e) and fp(p). In this case, after a bit more math than I anticipated we find:

      0, u < 1/11
      121/8 - 1/(8u2), 1/11 ≤ u < 1/9
      fu(u) = 5, 1/9 ≤ u < 3/11
      9/(8u2) - 81/8, 3/11 ≤ u < 1/3
      0, 1/3 ≤ u

      After integrating we find Usporadic = E[U] ≈ 0.20.

      The utilization with the periodic task model is about 13 % more than if we use the average utilization.

  3. You want to set up a lemonade stand. In no particular order, you need to:
    1. mix lemon juice and water,
    2. buy lemons and sugar (at the grocery store),
    3. buy a table (at another store),
    4. mix the lemon juice, sugar, and water,
    5. set up the table and a sign,
    6. make a sign, and
    7. pour the lemonade into cups

    Show a precedence graph that for all these activities.

    You may have drawn an edge from e to g if you assumed the table was required to pour lemonade into the cups.

  4. Do problem 4.1 from the book
    1. Find the effective release times and deadlines of the jobs in the precendence graph in Figure 4P-1.

      Precedence Graph with Effective Release Times for 4.1a

    2. Find an EDF schedule of the jobs.

      EDF schedule of jobs in above figure

    3. A job is said to be at level i if the length of the longest path from the job to jobs that have no successors is i... Find a priority-drive schedule of the jobs in Figure 4P-1 according to this priority assignment.

      Highest level first schedule

      Notes:

      1. J1 is the only job released at t=0, so it goes first.
      2. At t=1, J2, J4, and J7 have been released. J4 has a level of 3, so it goes first.
      3. At t=2, J4is done. J7 has the next highest level (2), so it goes next.
      4. At t=3, J7 is done. J3, J5, J8, and J9 are released. J5 has the next highest level (2), so it runs.
      5. At t=4, J5 is done. Either J2 or J8 could run because both have a level of 1 and both have had their precedence contraints met. At this point J2 has already missed its deadline...
      6. At t=5, either J2 or J8, whichever was run at t=4, is done. The one that was not previously run gets to run. There are no more level 1 jobs.
      7. At t=6, J3, J6, and J9 are all eligible to run and are all at level 0. They can run in any order occording to this scheduling algorithm.

      J2 and J3 miss their deadlines. This is not an optimal scheduling algorithm.

  5. Do problem 4.5 from the book

    A system contains nine nen-preemtable jobs named Ji, for i = 1, 2, ..., 9. Their execution times are 3, 2, 2, 2, 2, 4, 4, 4, 4, and 9, respectively, their release times are equal to 0, and their deadlines are 12. J1 is the immediate predecessor of J9, and J4 is the immmediate predecessor of J5, J6, J7, and J8. There are no other precedence constraints. For all the jobs, Ji has a higher priority than Jk if i < k.

    1. Draw the precedence graph of the jobs

    2. Can the jobs meet their deadlines if they are scheduled on three processors? Explain your answer.

      Yes, here is the schedule:

    3. Can the jobs meet their deadlines if we make them preemptable and schedule them preemptively? Explain your answer.

      No, J9 misses its deadline.

    4. Can the jobs meet their deadlines if they are scheduled nonpreemptively on four processors? Explain your answer.
      No, J9 misses its deadline.

    5. Suppose that due to an improvement of the three processors, the execution time of every job is reduced by 1. Can the jobs meet their deadlines? Explain your answer.

      No, J9 misses its deadline.