| We have run some processes concurrently on a single cpu by time sharing.
Only one process could run at a time, but the operating system often switched which
of the processes was the one that was running.
Each process, as it ran, frequently
checked what time it was and stored that time. The sequence of times that
each process observed is given to us. We want to find out how often the
context was switched from one of our processes to another. Because it is
possible that a process was allowed to execute very briefly and then the
cpu was switched to a different process before the first process checked and
stored the time, the best we can hope for is to find the minimum possible
number of switches that is consistent with the recorded times.
The biggest complication is that times on a computer are discrete. If the
time that was recorded was 3, that means that the actual time was sometime
between the third and fourth clock tick. Multiple processes could record the
same time, and one process could record the same time multiple times.
Create a class Switching that contains a method minSwitch that is given
String[] ticks, the sequence of times
recorded by each process, and that returns the smallest number of context
switches that could have occurred. The i-th element of ticks contains the
sequence of times recorded by the i-th process.
|