Homework 2 Solutions

The following problems will be due in class.

  1. Do problem 5.1 parts b, d, and f from the book.

    Each of the following systems of periodic tasks is scheduled and executed according to a cyclic schedule. For each system, choose an appropriate frame size. Preemptions are allowed, but the number of preemptions should be kept small.

    1. (8, 1), (15, 3), (20, 4), and (22, 6)

      The frame size has to meet all three criteria discussed in the chapter.

      1. f ≥ max(ei), 1 ≤ i ≤ n
        f ≥ 6
      2. f divides at least one of the periods evenly:
        f ∈ {1, 2, 3, 4, 5, 8, 10, 11, 15, 20, 22}
      3. 2f - gdc(f, pi) ≤ Di, 1 ≤ i ≤ n
        f = 8
        2 × 8 - gcd(8, 8) = 16 - 8 = 8 ≤ 8
        2 × 8 - gcd(8, 15) = 16 - 1 = 15 ≤ 15
        2 × 8 - gcd(8, 20) = 16 - 4 = 12 ≤ 20
        2 × 8 - gcd(8, 22) = 16 - 2 = 14 ≤ 22
        f = 10
        2 × 10 - gcd(10, 8) = 20 - 2 = 18 > 8
        f = 11
        2 × 11 - gcd(11, 8) = 22 - 1 = 21 > 8
        f = 15
        2 × 15 - gcd(15, 8) = 30 - 1 = 29 > 8
        f = 20
        2 × 20 - gcd(20, 8) = 40 - 4 = 36 > 2
        f = 22
        2 × 22 - gcd(22, 8) = 44 - 2 = 42 > 2

      The only frame size that works for this set of tasks is f = 8.

    2. (5, 0.1), (7, 1.0), (12, 6), and (45, 9)

      The frame size has to meet all three criteria discussed in the chapter.

      1. f ≥ max(ei), 1 ≤ i ≤ n
        f ≥ 9
        The smallest period is 5, which is less than the longest execution time. We cannot have a frame size larger than the period, so at this point we know we have to split the (45, 9) task and the (12, 6) task. Splitting (45, 9) into two tasks does not leave many frame size choices. Try (45, 9) => (45, 3), (45, 3), (45, 3) and (12, 6) => (12, 3), (12, 3)
        f≥ 3
      2. f divides at least one of the periods evenly:
        f ∈ {1, 2, 3, 4, 5, 6, 7, 9, 12, 15, 45}
      3. 2f - gdc(f, pi) ≤ Di, 1 ≤ i ≤ n
        f = 3
        2 × 3 - gcd(3, 5) = 6 - 1 = 5 ≤ 5
        2 × 3 - gcd(3, 7) = 6 - 1 = 5 ≤ 7
        2 × 3 - gcd(3, 12) = 6 - 3 = 3 ≤ 12
        2 × 3 - gcd(3, 45) = 6 - 3 = 3 ≤ 45
        f = 4
        2 × 4 - gcd(4, 5) = 8 - 1 = 7 > 5
        f = 5
        2 × 5 - gcd(5, 5) = 10 - 5 = 5 ≤ 5
        2 × 5 - gcd(5, 7) = 10 - 1 = 9 > 7

      The only frame size that works for this set of tasks is f = 3 (assuming the last two tasks are split as described above.)

    3. (7, 5, 1, 5), (9, 1), (12, 3), and (0.5, 23, 7, 21)

      The frame size has to meet all three criteria discussed in the chapter.

      1. f ≥ max(ei), 1 ≤ i ≤ n
        f ≥ 7
        The smallest period is 5, which is less than the longest execution time. We cannot have a frame size larger than the period, so at this point we know we have to split the (0.5, 23, 7, 21) task. Splitting it into two tasks does not work (try it, to see). Split the long task into three (0.5, 23, 3, 21), (0.5, 23, 3, 21), and (0.5, 23, 2, 21)
        f≥ 3
      2. f divides at least one of the periods evenly:
        f ∈ {1, 2, 3, 4, 5, 6, 9, 12, 23}
      3. 2f - gdc(f, pi) ≤ Di, 1 ≤ i ≤ n
        f = 3
        2 × 3 - gcd(3, 5) = 6 - 1 = 5 ≤ 5
        2 × 3 - gcd(3, 9) = 6 - 3 = 3 ≤ 9
        2 × 3 - gcd(3, 12) = 6 - 3 = 3 ≤ 12
        2 × 3 - gcd(3, 23) = 6 - 1 = 5 ≤ 21
        f = 4
        2 × 4 - gcd(4, 5) = 8 - 1 = 7 > 5
        f = 5
        2 × 5 - gcd(5, 5) = 10 - 5 = 5 ≤ 5
        2 × 5 - gcd(5, 9) = 10 - 1 = 9 ≤ 9
        2 × 5 - gcd(5, 12) = 10 - 1 = 9 ≤ 12
        2 × 5 - gcd(5, 23) = 10 - 1 = 9 ≤ 21

      Either f = 3 or f = 5 may work, assuming the last two tasks are split as described above. We need to make a schedule to verify the tasks can be scheduled with those frame sizes.

  2. Do problem 5.2 from the book. Add part c:
    1. When will the aperiodic job mentioned in (b) complete, if the system does do slack stealing?

      When doing parts b and c use the system from previous parts. That is, if any sporadic jobs are scheduled in part a, they will be in the system in parts b and c.

    1. Suppose that a sporadic job S1 (23, 1) arrives in frame 1, sporadic jobs S2(16, 0.8) and S3(20, 0.5) arrive in frame 2. In which frame are the accepted sporadic jobs scheduled?

      S1(23, 1)
      Since S1 arrives in frame 1, scheduling decisions about it are made at the start of frame 2. Frame 2 has a slack of 0.5, as does frame 3. Frame 3 ends at t=15 which is well before S1's deadline. The scheduler accepts S1 at the start of frame 2. If no other jobs arrive it would finish at the end of frame 3.
      S2(16, 0.8)
      The scheduler examines S2 at the start of frame 3 (t=10). The deadline, 16, is in frame 4, but there is only 0.5 slack in frame 3, so there is no way S2 can finish before its deadline. The scheduler rejects S2 at the start of frame 3.
      S3(20, 0.5)
      The scheduler examines S3 at the start of frame 3 (t=10). It's deadline is 20, which is the start of frame 5. There are 1.0 units of slack between frame 3 and frame 5, so the scheduler needs to see if S3 can be scheduled without making any currently scheduled jobs miss their deadlines. S3 has an earlier deadline than S1 so if S3 were accepted, it would run for 0.5 time units at the end of frame 3 and S1 would run for 0.5 time units at the end of frame 4. Since S1 has already executed for 0.5 time units at the end of frame 2, it will meet its deadline. S3 is accepted at the start of frame 3.
    2. Suppose that an aperiodic job with exeuction time 3 arrives at time 1. When will it be completed, if the systems does not do slack stealing?

      Call the aperiodic job A. When all the periodic jobs complete at the end of frame 1, the scheduler will let A execute until the start of frame 2, 1 time unit later. Frames 2, 3, and 4 have no slack because S1 and S3, from part (a), consume all of it. The scheduler runs A in the slack at the ends of frames 5 and 6. A completes at t=30, the end of frame 6.

    3. When will the aperiodic job mentioned in (b) complete, if the system does do slack stealing?

      When the periodic jobs complete at the end of frame 1, the scheduler will let A execute until the start of frame 2, 1 time unit later. (If frame 1 has several periodic jobs, and one of them ends after t=1, A could steal the slack then, but it would still get 1 time unit of execution time in frame 1). Frames 2, 3, and 4 have no slack because S1 and S3, from part (a), consume all of it. The scheduler runs A at the start of frames 5 and 6, stealing one unit of slack from each frame. A completes at t=26, 1 time unit into frame 6.

  3. Imagine a digital audio effects processor implemented with three periodic tasks. The input task, Tin samples data at a frequency of 44.1 KHz, and takes 5 μs to execute for each sample. Likewise, the output task, Tout outputs samples at a frequency of 44.1 KHz and takes 6 μs to run. The filter task, Tfilter operates on 64 samples at a time, thus it runs at a frequency 1/64th that of the input and output tasks. The filter takes 500 μs to run.

    A fourth, aperiodic task controls the user interface. The arrival rate of user-interface jobs is 10 jobs/s. The mean execution and mean square execution time 10 ms and 125 ms, respectively.

    What is the average response time of jobs in the aperiodic task? Is the user likely feel that the user-interface is responsive?

    As always it is important to pay attention to units. The three periodic task parameters are:

    Tin
    (1/44.1 KHz, 5 μs) ≈ (22.7 μs, 5 μs)
    Tout
    (1/44.1 KHz, 6 μs) ≈ (22.7 μs, 6 μs)
    Tfilter
    (64/44.1 KHz, 500 μs) ≈ (1.45 ms, 0.5  ms)

    U = 5 μs/22.7 μs + 6 μs/22.7 μs + 0.5 ms/1.45 ms ≈ 0.830
    UA = 10 Hz × 10 ms = 0.1
    Plugging in to (5.4a) & (5.4b) on P. 95, W ≈ 111 ms

    A response time of 100 ms is generally considered the limit for a system to feel responsive. This system is pretty close to that, but a little above, so it might seem a bit sluggish, but mostly responsive.