Honors Discrete 8 - wsfcs.k12.nc.us
Hon Discrete 8.3 Priority List Worksheet Name: _____ANSWER KEY_____
Use a separate sheet of paper as needed.
1) Schedule the project for the given priority list, project digraph, and 2 processors.
[pic]
a. For the priority list A(10), B(7), C(5), D(3), E(2) [pic]
b. For the priority list E(2), D(3), C(5), B(7), A(10) [pic]
c. Which priority list provides a better schedule?
ANSWER A is better because 14 < 20
2) Schedule the project for the given priority list, project digraph, and 2 processors. [pic]
a. For the priority list A(6), B(3), C(7), D(4), E(1), F(8), G(9), H(2).
[pic]
b. For the priority list H(2), G(9), F(8), E(1), D(4), C(7), B(3), A(6).
[pic]
c. Which priority list provides a better schedule?
SCHEDULE B IS BETTER BECAUSE 21 < 23
3) Draw the project digraphs for the following: Don’t forget Start and End
|Task |Time |Precedence Relations |
|A |6 | |
|B |7 | |
|C |10 | |
|D |11 |F→D |
|E |3 |G→ E |
|F |4 |B→F, C→F |
|G |9 |A→G, B→G |
|Task |Time |Precedence Relations |
|A |11 | |
|B |50 |H→B |
|C |25 |A→ C |
|D |37 |C→ D, E→ D |
|E |18 |A→ E, H→ E |
|F |29 |A→ F, D→ F |
|G |44 |D→ G |
|H |33 | |
Textbook p. 304 #23 – 26: Refer to a project of 11 tasks (A though K) with the following processing times (in hours): A(10), B(7), C(11), D(8), E(9), F(5), G(3), H(6), I(4), J(7), K(5).
23. (a) A schedule with N = 3 processors produces a finishing time FIN = 31 hours. What is the total idle time for all the processors?
TOTAL PROCESSING TIME = 75; IDLE = 3*31 – 75 = 18 hours
(b) Explain why a schedule with N = 3 processors must have a finishing time FIN ≥ 25 hours.
75/ 3 = 25; assumes each of the 3 processors works non-stop with no idle time or waiting
24. (a) A schedule with N = 5 processors produces a finishing time FIN = 19 hours. What is the total idle time for all the processors?
IDLE = 5*19 – 75 = 20 HOURS
(b) Explain why a schedule with N = 5 processors must have a finishing time FIN ≥ 15 hours.
75/5 = 15; assumes each of the 5 processors works non-stop with no one idling or waiting
25. Explain why a schedule with N = 6 processors must have a finishing time FIN ≥ 13 hours.
75/ 6 = 12.5; since all tasks are whole hours we round up to 13 hours to say some workers could work non-stop for 12 straight hours with 1 hour of idle or work 13 straight hours to make up the 0.5 hour difference
26. (a) Explain why a schedule with N = 10 processors must have a finishing time FIN ≥ 11 hours
75/10 = 7.5, but the largest individual processing time is C at 11 hours so at least one processor will be busy for 11 straight hours
(b) Explain why it doesn’t make sense to put more than 10 processors on this project.
More than 11 processors doesn’t make sense because there are only 11 tasks and more than 11 processors would mean some processors would NEVER do a task and only idle. Exactly 11 processors don’t make sense because one processor will still always never do a job because of idling for a precedence relation to be met, or one processor could do two tasks in the time it takes to do the longest task at 11 and the 11th worker would be useless.
Based on the previous textbook problems:
a. How is the total processing time of all tasks, total idle time, and FIN time related?
(N Processors) * FIN = Total Processing Time + Total Idle Time
b. How is the FIN time related to the total processing time of all tasks and number of processors related?
FIN > Total Processing Time/( N Processors)
c. Why should a project never have more processors than tasks? Explain.
Processors will always IDLE and some will never actually complete a task
(You would be paying someone to do nothing in a job situation)
d. Can the FIN time ever be smaller than the longest task’s individual processing time? Why?
NO; The finishing time is based on when all processors are done and the last remaining task is completed. The finishing time can’t be shorter than the longest individual task.
-----------------------
START(0)
A
B
C
END(0)
D
E
E(2)
D(3)
C(5)
B(7)
A(10)
2
0
4
6
8
12
10
14
16
18
20
P1:
P2:
Idle (3)
Idle (10)
D(3)
A(10)
B(7)
E(2)
C(5)
2
0
4
6
8
12
10
14
16
18
20
P1:
P2:
START(0)
A
B
C
END(0)
D
E
F
G
H
Idle
H(2)
C(7)
E
G(9)
Idle (3)
D(4)
B(3)
A(6)
F(8)
2
0
4
6
8
12
10
14
16
18
22
20
24
26
28
Time:
P1:
P2:
Idle
C(7)
H(2)
G(9)
E
B(3)
F(8)
D(4)
A(6)
2
0
4
6
8
12
10
14
16
18
22
20
24
26
28
Time:
P1:
P2:
A
D
F
C
E
G
START(0)
B
END(0)
START(0)
END(0)
D
A
E
G
B
H
F
C
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.