In: Computer Science
Apply a “stepwise refi nement approach” to develop three different levels of procedural abstractions for one or more of the following programs: (1) Develop a check writer that, given a numeric dollar amount, will print the amount in words normally required on a check. (2) Iteratively solve for the roots of a transcendental equation.
(3) Develop a simple task-scheduling algorithm for an operating system.
i need 3rd part solution because 1st 2 parts are already answerd.
We are going to use min-max algorithm to make task scheduling algorithm,
Min-Max makes good use of time for greedy strategy, small tasks and big tasks are put together for scheduling. The main idea is as follows.
1) Calculate the minimum completion time for each task which is assigned to the related resources.
2) Choose a minimum value and a maximum value from the minimum completion time to make up a pair of tasks
3) Finish the pair of tasks scheduling and update related variables.
4) Repeat above steps until all tasks are assigned.
ALGORITHM :-
1 for each task Ti in task collection T
2 for j=1, 2, …, n
3 initialize RT(j)=0
4 calculate prediction finish time of task Ti which is assigned to
resource Mj, CT(i, j)=ETC(i, j)+RT(j)
5 end for
6 end for
7 while T is not null do
8 for each task Ti in task collection T
9 calculate MCT(i) and record host number host _MCT (i)
10 end for
11 choose a minimum value Ta and a maximum value Tb from the MCT(T)
12 assign Ta and Tb to host_MCT (Ta +Tb)
13 delete Ta and Tb from the task collection T
14 update RT(host_MCT (Ta +Tb))=MCT(Ta)+ MCT(Tb)
15 update CT matrix
16 end while
EXPLANATION OF TERMS USED ABOVE:-
RT(j): It refers to prepare time of resource Mj.
ETC(i, j): It represents prediction execute time of task Ti
which is assigned to resource Mj.
CT(i, j) : It represents prediction finish time of task Ti
which is assigned to resource Mj, satisfying CT(i, j)= ETC(i,
j) + RT(j).
MCT(i): It refers to the minimum finish time of task Ti.
host _MCT (i): It means that Task Ti is assigned to re-
source host _MCT (i).