P R E L I M I N A R Y S P E C I F I C A T I O N Due 2:00 am, Friday, 12 February 2016 CPSC 223b Homework #2 The Processor Scheduling Problem REMINDER: Do not under any circumstances copy another student's code or give a copy of your code to another student. After discussing the assignment with another student, you may not take any written or electronic record away. Moreover, you must engage in a full hour of mind-numbing activity before you work on it again. Such discussions must be noted in your log file. (40) Suppose that you are given a set of independent tasks (with specified run-times) and a set of identical processors. For any assignment of tasks to processors, the workload of each processor is the sum of the run-times of the tasks assigned to it. The goal in processor scheduling is to find an assignment that minimizes the largest workload among the processors. Write a program Psched nProc [taskRuntime]* [-opt | -lw | -lwd | -bw | -bwd]* that performs various assignments of tasks to processors and prints their maximum workloads. Here nProc is the number of processors (which must be a positive integer). The processors are numbered P(0), P(1), ..., P(nProc-1). [taskRuntime]* is a sequence of zero or more run-times (which must be nonnegative integers). [-opt | -lw | -lwd | -bw | -bwd]* is a sequence of zero or more flags (each either -opt or -lw or -lwd or -bw or -bwd) that specify which assignments to perform. The flags have the following meanings: -opt Use backtracking to find an assignment that minimizes the largest workload among the processors. -lw Use the least-workload heuristic: assign the tasks (i.e., the run- times) in the order they appear on the command line; assign each to a processor that has the least workload at the time of the assignment. -lwd Use the least-workload heuristic, but first sort the tasks (i.e., the run-times) in decreasing order of run-time and then assign them in that order. -bw Use the best-workload heuristic: assign the tasks in the order that their run-times appear on the command line; assign each to a processor that has the least current workload, unless this assignment would NOT increase the maximum current workload, in which case assign that task to the busiest processor with this property. -bwd Use the best-workload heuristic, but first sort the tasks (i.e., the run-times) in decreasing order of run-time and then assign them in that order. Psched prints the maximum workload using a statement like printf ("-FFF %d\n", maxWorkLoad); where FFF is the current flag (blank-padded to three characters). When more than one flag is specified, it prints the corresponding maximum workloads on separate lines in the order specified on the command line. Flags may be specified more than once. Note that the task run-times must all PRECEDE the first function flag. Examples: % Psched 3 7 6 4 8 5 4 7 -lw -lwd -lw 18 -lwd 16 % Psched 3 7 6 4 8 5 4 7 -bw -bwd -bw 17 -bwd 15 % Psched 3 7 6 4 8 5 4 7 -opt -opt 14 Use the submit command to turn in the source file(s) for Psched, a Makefile, and your log file (see Homework #1). YOU MUST SUBMIT YOUR FILES (INCLUDING THE LOG FILE) AT THE END OF ANY SESSION WHERE YOU SPEND AT LEAST ONE-HALF HOUR WRITING OR DEBUGGING CODE, AND AT LEAST ONCE EVERY HOUR DURING LONGER SESSIONS. (All submissions are retained.) Notes ~~~~~ 1. Psched should not make any additional assumptions (beyond those above) about the number of processors, the number of tasks, the task-times, or the number of flags. However, it should fail gracefully if any of these assumptions are violated. Hint: With the right code, the value returned by atoi() can always be used, even if the argument specifying the number of processors or a run-time is not a nonnegative integer. 2. There are two basic ideas in the best-workload heuristic: A. Keep the maximum current workload as small as possible. (This is what makes best-workload a greedy algorithm.) B. Given the choice of assigning the run-time R to one of two processors A and B in a situation where neither assignment would increase the maximum current workload, assign it to the busier of A and B. (The other will be able to handle larger workloads in the future.) For example, suppose that there are three processors with workloads A: 13 B: 14 C: 20 and a task with run-time 5 to assign. Assigning that run-time to A or B will not increase the maximum current workload (= 20). In least-workload we would choose A. But since B is busier than A, in best-workload we choose B. 3. The general form of backtracking for this problem is something like: int ps (...) { if all tasks have been assigned to processors return the maximum workload for this assignment or for the best assignment seen so far, whichever is smaller for each processor in the order P(0), ..., P(nProc-1) assign the next unassigned task to that processor call ps() recursively to find the smallest maximum workload given that the tasks already assigned can not be reassigned deassign the task just assigned return the smallest maximum workload found } The initial call to ps() must specify a value for the workload of the best assignment seen so far. While this could be an arbitrary upper bound (which might not correspond to a complete assignment), Psched uses the workload for the -lwd assignment. To reduce the amount of backtracking required Psched should also implement the following heuristics: A. Always pick an unassigned task with the longest run-time to assign next; or, equivalently, sort the tasks in decreasing order of run-time and then assign them in sequence. B. Compute a lower bound on the maximum workload (by adding the run-times of the individual tasks, dividing by the number of processors, and rounding up to the nearest integer) and stop searching if a complete assignment with that workload is ever found. C. Keep track of the smallest maximum workload found previously (initially this is the workload for the -lwd assignment as noted above) and ignore any partial assignment that makes the workload for some processor at least this large. D. Not assign a task to a processor with the same (current) workload as a lower-numbered processor. E. Not assign succeeding tasks with the same run-time to processors with lower numbers. 4. When available, the public grading script will be /c/cs223/Hwk2/test.Psched and my solution will be /c/cs223/Hwk2/Psched. The instrumented version /c/cs223/Hwk2/PschedI prints the number of backtracks required and also accepts flags of the form -opt[A|B|C|D|E|T]* that disable the specified heuristics [A, B, C, D, or E] and/or turn on tracing mode [T]. Example: % PschedI 3 5 5 4 4 3 3 3 -optT Add TIME(0) = 5 to P(0) Lower = 9; Upper = 11; Loads: L(0) = 5, L(1) = 0, L(2) = 0, Add TIME(1) = 5 to P(0) Lower = 9; Upper = 11; Loads: L(0) = 10, L(1) = 0, L(2) = 0, Add TIME(2) = 4 to P(1) Lower = 9; Upper = 11; Loads: L(0) = 10, L(1) = 4, L(2) = 0, Add TIME(3) = 4 to P(1) Lower = 9; Upper = 11; Loads: L(0) = 10, L(1) = 8, L(2) = 0, Add TIME(4) = 3 to P(2) Lower = 9; Upper = 11; Loads: L(0) = 10, L(1) = 8, L(2) = 3, Add TIME(5) = 3 to P(2) Lower = 9; Upper = 11; Loads: L(0) = 10, L(1) = 8, L(2) = 6, Add TIME(6) = 3 to P(2) Lower = 9; Upper = 11; Loads: L(0) = 10, L(1) = 8, L(2) = 9, Remove TIME(6) = 3 from P(2) Remove TIME(5) = 3 from P(2) Remove TIME(4) = 3 from P(2) Remove TIME(3) = 4 from P(1) Remove TIME(2) = 4 from P(1) Remove TIME(1) = 5 from P(0) Add TIME(1) = 5 to P(1) Lower = 9; Upper = 10; Loads: L(0) = 5, L(1) = 5, L(2) = 0, Add TIME(2) = 4 to P(0) Lower = 9; Upper = 10; Loads: L(0) = 9, L(1) = 5, L(2) = 0, Add TIME(3) = 4 to P(1) Lower = 9; Upper = 10; Loads: L(0) = 9, L(1) = 9, L(2) = 0, Add TIME(4) = 3 to P(2) Lower = 9; Upper = 10; Loads: L(0) = 9, L(1) = 9, L(2) = 3, Add TIME(5) = 3 to P(2) Lower = 9; Upper = 10; Loads: L(0) = 9, L(1) = 9, L(2) = 6, Add TIME(6) = 3 to P(2) Lower = 9; Upper = 10; Loads: L(0) = 9, L(1) = 9, L(2) = 9, Remove TIME(6) = 3 from P(2) Remove TIME(5) = 3 from P(2) Remove TIME(4) = 3 from P(2) Remove TIME(3) = 4 from P(1) Remove TIME(2) = 4 from P(0) Remove TIME(1) = 5 from P(1) Remove TIME(0) = 5 from P(0) #backtracks(-optT) = 13 5. You may implement the sorting algorithm of your choice (efficiency is not important for the small numbers of run times that will be tested), but you must start from scratch and your algorithm must be able to sort N items in time proportional to N^2. In the unlikely event that you do not know ANY algorithms, you may read about them in a book. However, the Gilligan's Island Rule then applies. 6. The only new C constructs needed for this assignment are * command-line arguments * strcmp() (for identifying command-line arguments), * atoi() (for converting strings to integers) * arrays (for holding assignments and workloads) * recursion (for implementing backtracking). 7. Psched does NOT need pointers or pointer notation and may not use them, other than when declaring the argv parameter to main() (or another function to which you pass it). 8. Features of C99 (but not ANSI C) that may be useful: * Variable declarations (and initializations) may appear in for loops. * The length of an array may be an expression whose value is not known until run-time; no longer must the length of any dimension of an array be known at compile-time. For example, // Reverse the elements in the array X with N elements void reverse (int n, int x[]) { int y[n]; for (int i = 0; i < n; i++) y[n-i] = x[i]; for (int i = 0; i < n; i++) x[i] = y[i]; } 9. If your code for backtracking runs too slowly (e.g., it passes a test when you run it manually, but times out when the script runs it), the most likely cause is an incorrect implementation of one or more of the heuristics in Note 3 or one where the backtracking function (ignoring the recursive call) does not run in time that is bounded by a constant times the square of the number of processors. Warning: The test scripts will circumvent any attempt to enable compiler optimization (e.g., the -O3 flag to gcc) A. Backtracking will be worth at most 24 points. B. Hints: * Using ceil() to compute the lower bound is more trouble than it's worth. * You need not keep track of the task numbers. C. Point to Ponder: How large can the ratio of N(lw)/N(opt) be? N(lwd)/N(opt)? N(bw)/N(opt)? N(bwd)/N(opt)? N(lw)/N(bw)? ... D. Reading: K&R: Appendix B2 (character class tests) K&R: Chapter 2 (types, operators, and expressions) Summit: https://www.eskimo.com/~scs/cclass/krnotes/sx5.html (K&R 2) K&R: Chapter 3 (control flow) Summit: https://www.eskimo.com/~scs/cclass/krnotes/sx6.html (K&R 3) K&R: Chapter 4 (functions and program structure) Summit: https://www.eskimo.com/~scs/cclass/krnotes/sx7.html (K&R 4) M&S: pp. 14-16 (help), 109-119 , 138-144 (argv)> CS-223-01/27/16