pppeck313/323-da-algorithms-6-dependency-graph

323 6-Dependency-Graph

CSC 323-32: Project 6 (C++)

Preston Peck

Due date: Dec. 6, 2016

**** Algorithm steps for Dependency Job Scheduling:

Step 0: open input-1 (argv[1]) and input-2 (argv[2]) and output (argv[4])
0.1: numJobs <-- get from input1.
0.2: numProcessor <-- get from argv[3]
0.3: if numProcessor > numJobs
numProcessor <-- numJobs
0.4: Time <-- 1

Step 1: graphHashTable <-- dynamically allocated and initialized of all fields

Step 2: <ni, nj> <-- read from input-1
2.1: job <-- ni & child <-- nj
2.2: newNode <-- create a graphNode for
2.3: push newNode on the top of graphHashTable[index].stackTop
2.4: graphHashTable[job].childCount ++
2.5: graphHashTable[child].fatherCount ++

Step 3: repeat step 2 until input-1 is end of file

Step 4: totalJobTime <-- 0

Step 5: <job, jobTime> <-- read from input-2
5.1: graphHashTable[job].jobTime <-- jobTime
5.2: totalJobTime += jobTime

Step 6: repeat step 5 until input-2 is end of file

Step 7: processorSchedule <-- dynamically allocated and initialized

Step 8: job <-- 1

Step 9: if graphHashTable[job].fatherCount == 0
9.1: orphan <-- job
9.2: newNode <-- create a graphNode for
9.3: insert(OPEN, newNode)
9.4: graphHashTable[orphen].fatherCount --

Step 10: job++

Step 11: repeat step 9 - step 10 while job <= numJobs

Step 12: processor <-- 1

Step 13: if OPEN is not empty and processorSchedule[processor][0] <= 0
13.1: availProc <-- processor
13.2: processorSchedule[availProc][0]++
13.3: job <-- remove from Open
13.4: jobTime <-- graphHashTable[job].jobTime

Step 14: slot <-- Time

Step 15: processorSchedule[availProc][slot] <-- job

Step 16: slot ++

Step 17: repeat step 15 to step 16 while slot <= Time + jobTime

Step 18: processor ++

Step 19: repeat step 13 - step 18 while OPEN is NOT empty and (processor <= numProcessor)

Step 20: Time++

Step 21: processor <-- 1

Step 22: if (processorSchedule[processor][0] > 0) and (processorSchedule[processor][Time] <= 0)
doneJob <-- processorSchedule[processor][Time - 1]
22.1: graphHashTable[doneJob].fatherCount--
22.2: processorSchedule[processor][0] <-- 0

Step 23: processor ++

Step 24: repeat step 22 to 23 while processor <= numProcessor

Step 25: repeat which steps 8 to 24 while Time < totalJobTime

INPUT

Dependencies
15
1 2
1 3
7 3
9 3
4 2
4 6
4 5
2 6
3 6
3 10
3 8
5 13
8 15
8 11
6 11
6 12
6 13
5 14
12 14

13
1 2
7 3
9 3
4 2
4 6
4 5
2 6
3 10
3 8
5 13
8 11
6 11
6 12
6 13

Times
15
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1

13
1 4
2 1
3 3
4 3
5 2
6 2
7 1
8 2
9 2
10 3
11 2
12 4
13 2

Processors
2
5
40

OUTPUT

	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	T11	T12	T13	T14	T15
P1	4	5	9	3	6	12	14	11	0	0	0	0	0	0	0
P2	1	2	7	0	8	15	13	10	0	0	0	0	0	0	0

	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	T11	T12	T13	T14	T15
P1	4	3	6	12	14	0	0	0	0	0	0	0	0	0	0
P2	1	5	8	15	0	0	0	0	0	0	0	0	0	0	0
P3	9	2	10	13	0	0	0	0	0	0	0	0	0	0	0
P4	7	0	0	11	0	0	0	0	0	0	0	0	0	0	0
P5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	T11	T12	T13	T14	T15
P1	4	3	6	12	14	0	0	0	0	0	0	0	0	0	0
P2	1	5	8	15	0	0	0	0	0	0	0	0	0	0	0
P3	9	2	10	13	0	0	0	0	0	0	0	0	0	0	0
P4	7	0	0	11	0	0	0	0	0	0	0	0	0	0	0
P5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P6	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P7	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P8	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P9	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P10	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P11	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	T11	T12	T13	T14	T15	T16	T17	T18	T19	T20	T21	T22	T23	T24	T25	T26	T27	T28	T29	T30	T31
P1	1	1	1	1	9	9	6	6	12	12	12	12	8	8	11	11	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P2	4	4	4	5	5	2	7	3	3	3	10	10	10	13	13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	T11	T12	T13	T14	T15	T16	T17	T18	T19	T20	T21	T22	T23	T24	T25	T26	T27	T28	T29	T30	T31
P1	1	1	1	1	2	10	10	10	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P2	4	4	4	5	5	6	6	12	12	12	12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P3	9	9	3	3	3	8	8	13	13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P4	7	0	0	0	0	0	0	11	11	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10	T11	T12	T13	T14	T15	T16	T17	T18	T19	T20	T21	T22	T23	T24	T25	T26	T27	T28	T29	T30	T31
P1	1	1	1	1	2	10	10	10	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P2	4	4	4	5	5	6	6	12	12	12	12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P3	9	9	3	3	3	8	8	13	13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P4	7	0	0	0	0	0	0	11	11	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P5	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P6	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P7	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P8	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P9	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P10	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P11	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
P13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0