problem
PLEASE ANSWER IN JAVA THANK YOU - This is a scheduling
problem
PLEASE ANSWER IN JAVA THANK YOU - This is a scheduling
problem
- Please Answer In Java Thank You This Is A Scheduling Problem Please Answer In Java Thank You This Is A Scheduling Pr 1 (73.56 KiB) Viewed 47 times
- (int) jobTime - (node) next Method: - constructor (...) - A schedule class - (int) numNodes // the total number of nodes in the input graph. - (int) numProcs // the number of processors can be used. - (int) procUsed // number of processors und so far; initialized to 0. - (int) current Time // initialize to 0. - (int) totalJobTimes // the sum of all job times of nodes in the graph. - (int[jobTimeAry // an ID array to store the job time of each node in the graph; // to be dynamically allocated, size of numNodes +1; initialized to 0. - (int [10) Matrix // a 2-D integer array, size numNodes+1 by numNodes+1, // to represent the dependency graph; to be dynamically allocated, initialized to zero. // We use this matrix for the followings: // Matrix [0][0] to store number of nodes remain in the graph; initialize to numNodes; 1/ decreases by 1, when a node is deleted; So, to check if the graph is empty, 1/ just check if Matrix[0][0]==0. // Matrix 6] >= 1, means node i is a parent of nodej (i.e., node jis a dependent of node i). // Matrix [0]G), we use row 0 to store the parent counts of node j. 1/The parent counts of nodej is the total count of none zero rows in i-th column. // So if we want to know the parent counts of nodej, we check Matrix(OG). // Matrix [0], we use column 0 to store the dependent counts of node i. 1/The dependent counts of node i is the total count of none zero columns in i-th row. // So if we want to know the dependent counts of node i, we check Matrix [i[0). // Matrix , the diagonal, to indicate the status of the node, where i = 1 ... numNodes // Matrix [0][0]==0 means node i is not in the graph. (i.e., done and deleted.) // Matrix [0]) 1 means node i is in the graph and not marked yet. // Matrix i]=2 means node i is marked. - int (0) Table // a 2-D integer array, size of (numProcs +1) by (totalJobTimes +1) for scheduling; // to be dynamically allocated, and initialized to 0. // Index of Table row represent processor's id, and index of Table column represent time slot. // Table [T]>0 means the processor i is processing a job, (TableT]), at time slot T. // Table [T] =0 means the processor i is idled (available) at time slot T. // where i = 1 to numProcs and T =0 to totalJobTimes. - (node) OPEN // OPEN acts as the list head of a linked list with a dummy node. // Nodes in OPEN are sorted in ascending order by jobTime. Methods: - constructor (...) // take care all member allocations, initialization, etc. - load Matrix (inFile) // read an edge <n, n>from inFileland load. - (int) loadJobTimeAry (inFile2) // read each pair jobID, time from inFile2 and load to jobTime Ary; // set jobTimeAry[jobID] + time; this method needs to keep track of total job times; // it returns totalJobTimes - setMatrix (...) // Compute parent counts and store in Matrix[0]). // computes dependent counts and store in Matrix[i][0], 3
1/set diagonal entries Matrix[i][i] to 1; set Matrix [0][0] to numNodes. // If you like, you may let the constructor do these. - printMatrix (outFile2)// Print the entire content of Matrix with row and column indices in readable format. - (int) findOrphan (...) // Check Matrix [0]G] to find the next un-marked orphan node, j, i.e., Matrix [0G]=0&& //Matrix [1]6)=1. If found, mark the orphan, i..., set Matrix[16] + 2, then returns j; // if no such j, returns -1. - OpenInsert (node) // inserts node into OPEN in ascending order with respect to the node's jobTime. // Re-use codes similar to your earlier projects. On your own. - printOPEN (outFile2) // Prints to outFile2, nodes in OPEN linked list. // Re-use codes similar to the printList method in your earlier projects. - (int) getNextProc (current Time) // on your own // check Table [i][currentT'ime] to find the first i where Table [i][currentTime] =0 // if found returns i, else returns -1, means no available processor. - fillOPEN (...) // populate OPEN from orphan nodes in the graph; see algorithm below. - fillTable (...) // populate the table from jobs in OPEN; see algorithm below. - putJobOnTable (availProc, current Time, jobID, jobTime) // see algorithm below. - printTable (outFilel, current Time) // print the schedule Table up to the current Time slot to outFilel, // On your own, see the format description given in the above. - (bool) checkCycle (...) // on your own. Check the followings: (1) OPEN is empty. (2) Graph is not empty. // you should know where to check. (3) all processors are available. Il you should know where to check if all 3 conditions in the above are true, returns true, else returns false. - (Luul) isGiaplıEmply (...) // ou you ww. if Matrix [0][0] =0 returns true, else returns false. When you printMatrix, pay attention to // the content of Matrix [0][0). -deleteDoneJobs (...) // delete all done jobs from the graph; see algorithm steps below. - delete Job (jobID) // see algorithm steps below. // When a job is done, we delete the job and its outgoing edges from the graph, as follows. // 1) To delete a job in the graph is to set Matrix [jobID] jobID] to 0 and decrease the number of nodes in graph by 1, i.e., Matrix [0][0) -- // 2) To delete a job's outgoing edges is to decrease the parent counts all its dependents by 1. Note: the job's dependents are those none zero adjMatrix [jobID]6) >0, on jobID row For example, if Matrix [jobID]]] > 0, then decrease Matrix [0]G] by 1; i.e., Matrix [016)-- ***** ********* IV. main(..) // If you like, Step 1 to Step 4 can be done in the class constructor. Step 1: inFilel, inFile2, outFilel, outFile2 open numNodes fread from inFilel. numProcs get from argy [3] if (numProcs <=0) exit with error message"need 1 or more processors". else if (numProcs > numNodes) numProcs numNodes // means unlimited processors. Step 2: Matrix € dynamically allocate, size of numNodes+1 by numNodes+1, initialize to zero 4
load Matrix (inFile1) setMatrix (...) printMatrix (outFile2) // check for your self to make sure the matrix is correctly set. Step 3: OPEN get a dummy node for OPEN to point to currentTime 0 // at the beginning of scheduling procUsed 0 // no processor is used at the beginning Step 4: totalJobTimes loadJobTimeAry (inFile2) Table dynamically allocate, size of numProcs by totalJobTimes, initialize to zero printTable (outFilel, current Time) Step 5: fillOPEN(...) printOPEN (outFile2) Step 6: fillTable (...) print Table (outFilel, current Time) Step 7. Current Time ++ Step 8: deleteDone Jobs (...) Step 9: if checkCycle (...) is true output error message to outFilel: "there is cycle in the graph!!!" and exit the program step 10: repeat step 3 to step 7 until isGraphEmpty (...) step 11: printTable (outFile1) // The final schedule table. step 12: close all files ******* 考 ****************** V.fillOPEN (...) Step 1: jobID findOrphan (...) Step 2: if jobID>0 new Node € get a node with (jobID, jobTimeAry[jobID], null) OpenInsert (newNode) printOPEN(outFile2) // debug print Step 3: repeat step 1 to step 2 until no more unmarked orphan VI, fill Table (...) Step 1: availProc € getNextProc (current Time) if availProc >= 0 // means there is a processor available { newJob remove the front node of OPEN after dummy node // newJob is a node! putJobOnTable (availProc, currentTime, newJob.jobID, newJob.jobTime) if availProc> procUsed procUsed ++ step 2: repeat step 1 while availProc >= 0 && OPEN is not empty && procUsed <numProes **** ********** V. putJobOnTable (availProc, current Time, jobld, jobTime) Step 0: Time + current Time EndTime Time +jobTime Step 1: Table[avail Proc][Time] jobID Step 2: Time ++ Step 3: repeat step 1 to step 2 while Time < EndTime ************** ******************* ************* VII. deleteDoneJobs (...) 5
***** ************ Step 1: proct 0 Step 2: if Table[proc)( current Time] <= 0 && Table[proc) current Time - 1]> 0 1/ meaning, the processor, proc, just finished a job in the previous time cycle. jobID Table[proc) currentTime - 1] deleteJob(jobID) // see algorithm steps below. } Step 3: printMatrix (outFile2) step 4: proc++ step 5: repeat step 2 to step 4 while proc <procUsed *************** VI. delete Job (jobID) // When a job is done, we delete the job and its outgoing edges. ******* ********************** Step 1: Matrix [jobID][jobID] €0 // delete jobID from the graph Matrix [0][0) -- // one less node in the graph Step 2:j1 Step 3: if Matrix [jobID][] >0 // meansj is a dependent of jobID Matrix [016] -- // decrease j's parent count by 1 Step 4: j++ Step 5: repeat Step 3 to Step 4 while jnumNodes *********