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