Solution to RTS 97 HW 6

Note: Although simulator output detailing each action is shown, the preferred form of solutions is as a time chart, as used in class.

Problem 1

The list below shows changes in CPU state with time. (For example, {25, B} means at time 25 the CPU started running task B. {89, NoTask} means that at time 89 the CPU became idle.)

{{0, A}, {10, B}, {20, A}, {25, B}, {34, C}, {44, A}, {54, B}, 
    {64, C}, {74, A}, {79, B}, {88, C}, {89, NoTask}, {90, A}}


** Time:        0  
Task A created.
Task A changing from Ready to Run

** Time:        7  
Task B created.

** Time:       10  
Task A quantum expired.
Task A changing from Run to Ready
Task B changing from Ready to Run

** Time:       20  
Task B quantum expired.
Task B changing from Run to Ready
Task A changing from Ready to Run

** Time:       22  
Task C created.

** Time:       25  
Task A to sleep until next event at 30.

** Time:       25  
Task A to sleep until 30.
Task A changing from Run to Wait
Task B changing from Ready to Run

** Time:       30  
Resources now available for task A.
Task A changing from Wait to Ready

** Time:       34  
Task B to sleep until next event at 42.

** Time:       34  
Task B to sleep until 42.
Task B changing from Run to Wait
Task C changing from Ready to Run

** Time:       42  
Resources now available for task B.
Task B changing from Wait to Ready

** Time:       44  
Task C quantum expired.
Task C changing from Run to Ready
Task A changing from Ready to Run

** Time:       54  
Task A quantum expired.
Task A changing from Run to Ready
Task B changing from Ready to Run

** Time:       64  
Task B quantum expired.
Task B changing from Run to Ready
Task C changing from Ready to Run

** Time:       74  
Task C quantum expired.
Task C changing from Run to Ready
Task A changing from Ready to Run

** Time:       79  
Task A to sleep until next event at 90.

** Time:       79  
Task A to sleep until 90.
Task A changing from Run to Wait
Task B changing from Ready to Run

** Time:       88  
Task B to sleep until next event at 96.

** Time:       88  
Task B to sleep until 96.
Task B changing from Run to Wait
Task C changing from Ready to Run

** Time:       89  
Task C finishes normally.
Task C changing from Run to Zombie

** Time:       90  
Resources now available for task A.
Task A changing from Wait to Ready
Task A changing from Ready to Run

** Time:       96  
Resources now available for task B.
Task B changing from Wait to Ready

Problem 2

{{0, A}, {11, B}, {22, A}, {31, D}, {42, C}, {53, D}, {62, B}, 
    {71, E}, {82, C}, {91, E}, {100, NoTask}}


** Time:        0  
Task A created.
At round {TaskSched} tasks {A} chosen.
At round {TaskSched, 1} tasks {A} chosen.
At round {TaskSched, 1, 1} tasks {A} chosen.
Task A changing from Ready to Run

** Time:       10  
Task B created.

** Time:       11  
Task A quantum expired.
Task A changing from Run to Ready
At round {TaskSched} tasks {B, A} chosen.
At round {TaskSched, 1} tasks {B} chosen.
At round {TaskSched, 1, 1} tasks {B} chosen.
Task B changing from Ready to Run

** Time:       20  
Task C created.

** Time:       22  
Task B quantum expired.
Task B changing from Run to Ready
At round {TaskSched} tasks {A, C, B} chosen.
At round {TaskSched, 1} tasks {A} chosen.
At round {TaskSched, 1, 1} tasks {A} chosen.
Task A changing from Ready to Run

** Time:       30  
Task D created.

** Time:       31  
Task A finishes normally.
Task A changing from Run to Zombie
At round {TaskSched} tasks {D} chosen.
At round {TaskSched, 2} tasks {D} chosen.
At round {TaskSched, 2, 1} tasks {D} chosen.
Task D changing from Ready to Run

** Time:       40  
Task E created.

** Time:       42  
Task D quantum expired.
Task D changing from Run to Ready
At round {TaskSched} tasks {C, B} chosen.
At round {TaskSched, 1} tasks {C} chosen.
At round {TaskSched, 1, 1} tasks {C} chosen.
Task C changing from Ready to Run

** Time:       53  
Task C quantum expired.
Task C changing from Run to Ready
At round {TaskSched} tasks {E, D} chosen.
At round {TaskSched, 2} tasks {D} chosen.
At round {TaskSched, 2, 1} tasks {D} chosen.
Task D changing from Ready to Run

** Time:       62  
Task D finishes normally.
Task D changing from Run to Zombie
At round {TaskSched} tasks {B, C} chosen.
At round {TaskSched, 1} tasks {B} chosen.
At round {TaskSched, 1, 1} tasks {B} chosen.
Task B changing from Ready to Run

** Time:       71  
Task B finishes normally.
Task B changing from Run to Zombie
At round {TaskSched} tasks {E} chosen.
At round {TaskSched, 2} tasks {E} chosen.
At round {TaskSched, 2, 1} tasks {E} chosen.
Task E changing from Ready to Run

** Time:       82  
Task E quantum expired.
Task E changing from Run to Ready
At round {TaskSched} tasks {C} chosen.
At round {TaskSched, 1} tasks {C} chosen.
At round {TaskSched, 1, 1} tasks {C} chosen.
Task C changing from Ready to Run

** Time:       91  
Task C finishes normally.
Task C changing from Run to Zombie
At round {TaskSched} tasks {E} chosen.
At round {TaskSched, 2} tasks {E} chosen.
At round {TaskSched, 2, 1} tasks {E} chosen.
Task E changing from Ready to Run

** Time:      100  
Task E finishes normally.
Task E changing from Run to Zombie

Problem 3

Solution 1:

Use same scheduling as in problem 2. Move C to class 2, and assign it a deadline of infinity.

 Task   Round 1  Round 2
 A	Class 1  FCFS   
 B	Class 1  FCFS   
 C	Class 2  Deadline infinity
 D	Class 2  Deadline 60
 E	Class 2  Deadline 95

Solution 2:

Use three scheduling rounds. The first round is round-robin, as before. A and B remain in class 1, C is moved to class 2, and D and E remain in class 2.

Priority scheduling is used in the second class-2 round, C gets priority 1, D, E and any new deadline tasks are assigned priority 2.

Deadline scheduling is used for class-2, priority-2 tasks.

These are summarized in the table below:

 Task   Round 1  Round 2  Round 3
 A	Class 1  FCFS     Not Needed
 B	Class 1  FCFS     Not Needed
 C	Class 2  Pri. 1   Not Needed   
 D	Class 2  Pri. 2   Deadline 60
 E	Class 2  Pri. 2   Deadline 95