PROBLEM STATEMENT
The company you work for is developing a new operating system to handle loads
that take a great deal of time to compute. You are asked to write a routine
that will evaluate the efficiency of the scheduling algorithm. You should
simulate the running a number of processes and compute the efficiency of each
one. In addition, you should compute the overall efficiency of the operating
system when all the processes are run on it. Efficiency is calculated by
taking the total running time of a process or processes and dividing it by the
allocated time for the process or processes and multiplying by 100. (All
fractional parts are dropped.) You should return an int[] with a value for
each of the processes representing the efficiency of each process. The values
should be sorted by the names of the processes to which they correspond. The
overall efficiency of the operating system should be the last element of the
returned int[].
Each process will run in a one or more "time slots." A time slot is a
contiguous segment of time during which only one process may run. Each process
has a time slot length associated with it, which starts at one, and increases
if the program requires more time. For example, a process whose running time
is 10 will first run in a time slot of length 1. Since it can not finish in
this time slot, the next time the process is run, it will have a time slot of
length 2, then 4, and then 8. Thus, though the the process has a running time
of only 10, it actually uses 1+2+4+8=15 units of time.
Scheduling algorithm:
Time starts at zero, and the input queue is empty. The algorithm is as follows:
1) Any processes that are initiated at this time are appended to the end of the
queue in the order they appear in the input parameter, and there time slot
length is initialized to 1.
2) If a process ends and there is time left over for its slot, the time is
wasted in idle processes.
3) If the time slot for a process ends and the process is not finished, the
time slot length for that process is doubled. The process is then placed at
the end of the queue and the process on the front of the queue (if there is
one) is allocated a time slot and runs.
4) If there are still processes running, still processes which aren't finished
(including those not started) go to 1.
DEFINITION
Class: Scheduler
Method: efficiency
Parameters: String[]
Returns: int[]
Method signature (be sure your method is public): int[] efficiency(String[]
processes);
NOTES
- Slot times are integer powers of 2 greater than or equal to 1. i.e. 1, 2, 4,
8, 16, ...
- Only one process runs in any time slot. If a process completes in a time
slot and there is time left over, no other process run in that time slot.
- The scheduling algorithm continues until all processes have completed and the
final time slot ends.
- Assume the time used for computing the scheduling algorithm is negligible.
- Process names are case sensitive.
- Any uppercase letters sort before any lowercase letter. ('Z' sorts before 'a')
- Overall efficiency is calculated by dividing the total time that all of the
processes run by the total elapsed time, and multiplying by 100. (fractional
parts are dropped)
TopCoder will ensure the validity of all inputs. Inputs are valid if:
- processes has between 1 and 50 elements, inclusive.
- Elements of processes will be formatted as: "<processname>:<running
time>:<start time>" (quotes and angle brackets for clarity only)
- <processname> will be composed only of the characters 'a'-'z' and 'A'-'Z'.
- A colon will follow processname, followed by a number, followed by a colon,
followed by a number. (Numbers will not have extra leading zeroes)
- Running time will be between 1 and 100000, inclusive.
- Start time will be between 0 and 100000, inclusive.
- Process names will be between 1 and 30 characters.
- Process names will not be repeated.
EXAMPLES
1)
processes:
{"printerdeamon:65:0"}
At time zero the slot length is 1. Processes time left is 65
At time 1 the slot length is increased to 2. Process time left is 64
At time 3 the slot length is increased to 4. Process time left is 62
At time 7 the slot length is increased to 8. Process time left is 58
At time 15 the slot length is increased to 16. Process time left is 50
At time 31 the slot length is increased to 32. Process time left is 34
At time 63 the slot length is increased to 64. Process time left is 2
At time 65 the process ends but there is still time in the queue
At time 127 the process and slot have ended and the queue is empty.
Total time spend in printerdeamon = 127
Total processor time = 127
Printerdeamon efficiency = (65/127)*100 = 51
Processor efficiency = (65/127)*100 = 51
returns {51, 51}
2)
processes:
{"graphicsdraw:30:1",
"deamonstarter:13:0"}
At time 0 deamonstarter is loaded and run for one time slot.
At time 1 graphicsdraw is appended to the queue and deamonstarter ends, so
graphicsdraw starts up.
At time 2 graphicsdraw ends and deamonstarter begins
At time 4 then switch.
At time 6 they switch
At time 10 they switch
At time 14 they switch
At time 15 deamonstarter ends but the slot is not done until 22
At time 22 graphicsdraw is started for a 8 time unit slot
At time 30 graphicsdraw ends with the 8 unit slot but since nothing is in the
queue it starts again.
At time 45 the graphicsdraw is done and at 46 the slot is finished.
Graphicsdraw = 1+2+4+8+16=31 time units so 30/31*100 = 96
Deamonstarter = 1+2+4+8 = 15 time units so 13/15*100 = 86
Scheduler efficiency = (30+13)/46 = 93.478
returns {86, 96, 93}
3)
processes:
{"printer:65:5"}
there are 5 extra unit slots at the beginning because the processor waits
(65/127)*100 = 51 for printer
(65/132)*100 = 49 overall
returns {51,49}
4)
processes:
{"init:1:60",
"about:1:0"}
returns {100,100,3}
5)
processes:
{"nothing:100000:100000",
"something:100000:100000",
"aout:100000:100000"}
returns {76, 76, 76, 60}