PROBLEM STATEMENT
One of the more complicated tasks a memory manager may face is managing shared
memory between multiple processes. The basic rule is: don't let one process
modify memory that is actively referenced by another process. Multiple
processes may open the same memory read-only, but if one process wants to open
the memory to write, then it must lock all other processes out or wait until no
other process has a lock on that memory.
The system you are working on is a handheld that runs 4 processes at a time,
executing one block from each at the same time. By setting the processes at
different "run levels", it may be possible to improve the running time of the
system. The run level allows a more important process to pull memory locks
away from a less important process. When this happens (unless the less
important process was already giving up the lock), the less important process
must rollback to its last stable state (last state that was not affected by the
memory locks it lost). If a low priority process loses its write (exclusive)
lock to a more important process that just requests a read lock, the low
priority process may retain a read lock on that variable.
No process can have the same run level as another process and run levels cannot
be changed during execution. This guarantees the system will always finish
execution. All memory locks are released when the process finishes its final
step (note: this means doing a free on the final step is redundant, but it's
still legal). Find the fastest possible execution time for the given system
(execution time measured by the number of execution periods it takes to finish
the slowest of the 4 programs) by assigning optimal run levels to the different
processes.
DEFINITION
Class name: Shared
Method name: fastest
Parameters: String[], String[], String[], String[]
Returns: int
The method signature is (make sure it is declared public):
int fastest(String[] p1, String[] p2, String[] p3, String[] p4);
Each String[] (p1, p2, p3, and p4) represents a set of instructions for a
process.
Each process is documented as a view of the system from the perspective of the
memory manager. The instructions the memory manager recognizes are:
"R(x)" - attempt to obtain a read only lock on memory location x
"W(x)" - attempt to obtain a read/write (exclusive) lock on x
"NOOP" - wait for a time unit (indicates processing that doesn't concern the
memory manager)
"F(x)" - free all locks held on memory location x by the executing process
NOTE
If a process is freeing the requested lock at the same time as it is requested
by another process, the lock will be released and the other process will have
the chance to acquire the lock as if it had not been held. In this case, the
releasing process does not need to be rolled back (includes freeing by
finishing the final instruction). The final instruction of a program will
never be a read or write lock. Example: the current instruction from p1 is
F(12) and the current instruction from p2 is W(12). If no other processes have
locks on 12, p2 acquires exclusive lock, and p1 executes F(12) and continues
regardless of their relative run levels.
A process may take multiple locks on the same memory without freeing in
between. In this case, the more exclusive is always maintained. Example (...
does not contain a F(100)): R(100) ... R(100), the second R(100) can be
considered a NOOP. R(100) ... W(100) is an upgrade, which would roll back to
W(100) if only the write lock is lost, or all the way to R(100) if another
process preempts with exclusive control. W(100) ... R(100), the second R(100)
can be considered a NOOP. W(100) ... W(100), the second W(100) can be
considered a NOOP.
TopCoder will ensure:
1) all instructions will be in the above format, i.e.: "NOOP" or "op(x)" with
no spaces where op is F, R, or W (uppercase only) and x is a number (the number
can be padded with zeros).
2) all values of x will be numbers between 1 and 10000 inclusive. 001 should be
treated the same as 1.
3) each process, p1-p4 will contain between 1 and 50 instructions, inclusive
4) each instruction will contain between 4 and 50 characters, inclusive
5) the final instruction of each process will not be a request for a read or
write lock.
6) No set of instructions which leads to a cascading rollback is allowed (ie a
case where rolling back gives the process a lock on memory that someone else
has locked.)
EXAMPLES
Example 1
p1 = { R(100),NOOP,NOOP,NOOP }
p2 = { W(100),F(100),NOOP }
p3 = { NOOP }
p4 = { R(50),W(50),F(50) }
In this case, there are really only 2 processes to be concerned with. p3 is
done in 1 cycle no matter what, and p4 will execute in 3 cycles without being
affected by the others because there are no overlapping memory locations.
However, p1 and p2 are trying to access the same shared memory and p2 wants
exclusive control, we have 2 possibilities: either we have given p1 a higher
run level priority, which works as follows:
1) p1 acquires read lock on 100, p2 cannot get lock and must wait.
2) p1 does nothing (1st NOOP), p2 cannot get lock and must wait
3) p1 does nothing (2nd NOOP), p2 cannot get lock and must wait
4) p1 does nothing (3rd NOOP) and finishes, p2 gets the lock because p1 is
freeing the memory (due to finished execution) this cycle
5) p2 frees 100
6) p2 does nothing and finishes
The second possibility is that p2 has a higher run level priority then p1 and
acquires the lock first, in this case
1) p2 acquires write (exclusive) lock on 100, p1 cannot get lock and must wait
2) p2 frees lock on 100, p1 acquires lock
3) p2 does nothing and finishes, p1 does nothing (1st NOOP)
4) p1 does nothing (2nd NOOP)
5) p1 does nothing and finishs (3rd NOOP)
Clearly the system is the best when p2 has a higher run level then p1, and the
execution time of the system in this case will be 5, so we return 5.
Example 2
p1 = { F(5964),W(6044),R(6044),NOOP,F(5964),W(6044),W(5964),NOOP }
p2 = { NOOP,NOOP,W(6044),W(5337),R(6044),R(5964),R(6044),NOOP }
p3 = { NOOP }
p4 = { W(5964),NOOP }
return 13
Example 3
p1 = { W(0032),W(032),NOOP,NOOP }
p2 = { F(0004892),F(4892),NOOP,F(4849) }
p3 = { R(004849),W(4892),F(04849),F(032) }
p4 = { W(4892),W(04892),NOOP,NOOP }
return 6