Problem Statement
Deadlocks are the culprit in many computer lock-ups. Deadlocks can occur when there are resources that can only be accessed by 1 process at a time. When a process, p1, tries to access a resource that is already in use (locked) by another process, p2, then p1 has to wait until p2 is done with the resource (unlocks it) before it can gain access. A deadlock occurs when each running process is waiting to lock a resource that another process already has locked. For example, the following is the simplest possible deadlock:
p1 has locked resource A, and is waiting for resource B.
p2 has locked resource B, and is waiting for resource A.
In this case, neither process can make any progress because they are both waiting for each other.
In this problem you are to write a method which analyzes a small segment of code for a few processes and determines if a deadlock could occur. You should assume that you have no knowledge about the scheduler, so you must consider all possible schedules (see below for an example of this). You will be given a String[], processes, each of whose elements represents a single process. Each of these elements will consist of a sequence of upper and lowercase letters. An uppercase letter indicates that a process is attempting to lock a resource, while a lowercase letter indicates that a process is trying to unlock a resource.
For example, if processes = {"ABba","BAab"} then there are two processes. The first process is attempting to lock resource A, then lock resource B, then unlock resource B, then unlock resource A. The second process is doing the same, except with B and A switched. If the scheduler allows the first process to lock both A and B, or the second process to lock both B and A, then no deadlocks will occur, because one of the processes will finish executing (reach the end of the string), unlocking all of the resources it locked. However, if the scheduler allows the first process to lock A, and the second process to then lock B, then the deadlock described above will occur. Since we don't know anything about the scheduler, we must assume that it can execute the processes interleaved in any possible way, so in this example a deadlock could occur.
Your method should return a int[] representing how the processes might deadlock. The return should have one element for each process, representing the index of the character on which the corresponding process is stuck waiting (indexed from 0), or -1 if that process finishes despite the deadlock. If no deadlocks can occur, you should return an empty int[], {}. If there is more than one way for the processes to deadlock, you should return the one with the smallest int in the first position. If there is still a tie, you should return the one with the smallest int in the second position, and so on. For example, {-1,1,1} would be preferred over {1,1,1} and {-1,2,2}.
p1 has locked resource A, and is waiting for resource B.
p2 has locked resource B, and is waiting for resource A.
In this case, neither process can make any progress because they are both waiting for each other.
In this problem you are to write a method which analyzes a small segment of code for a few processes and determines if a deadlock could occur. You should assume that you have no knowledge about the scheduler, so you must consider all possible schedules (see below for an example of this). You will be given a String[], processes, each of whose elements represents a single process. Each of these elements will consist of a sequence of upper and lowercase letters. An uppercase letter indicates that a process is attempting to lock a resource, while a lowercase letter indicates that a process is trying to unlock a resource.
For example, if processes = {"ABba","BAab"} then there are two processes. The first process is attempting to lock resource A, then lock resource B, then unlock resource B, then unlock resource A. The second process is doing the same, except with B and A switched. If the scheduler allows the first process to lock both A and B, or the second process to lock both B and A, then no deadlocks will occur, because one of the processes will finish executing (reach the end of the string), unlocking all of the resources it locked. However, if the scheduler allows the first process to lock A, and the second process to then lock B, then the deadlock described above will occur. Since we don't know anything about the scheduler, we must assume that it can execute the processes interleaved in any possible way, so in this example a deadlock could occur.
Your method should return a int[] representing how the processes might deadlock. The return should have one element for each process, representing the index of the character on which the corresponding process is stuck waiting (indexed from 0), or -1 if that process finishes despite the deadlock. If no deadlocks can occur, you should return an empty int[], {}. If there is more than one way for the processes to deadlock, you should return the one with the smallest int in the first position. If there is still a tie, you should return the one with the smallest int in the second position, and so on. For example, {-1,1,1} would be preferred over {1,1,1} and {-1,2,2}.
Definition
- Class:
- Deadlocks
- Method:
- checkCode
- Parameters:
- String[]
- Returns:
- int[]
- Method signature:
- int[] checkCode(String[] processes)
- (be sure your method is public)
Notes
- You may assume that, initially, no resources are locked by any processes.
Constraints
- processes will contain between 2 and 5 elements, inclusive.
- Each element of processes will contain between 0 and 30 characters, inclusive.
- Each character of each element of processes will be an uppercase or lowercase letter ('A'-'Z' or 'a'-'z').
- No process will attempt to unlock a resource it does not have locked, and every process will unlock all its locked resources before it terminates (at the end of the String)
- No process will attempt to lock a resource it already has locked.
Examples
{"ABba","BAab"}Returns: { 1, 1 }The example in the problem statement.{"CABbac","CDBAabcd"}Returns: { }This is safe because both of the processes start by locking C. They can't get into the situation where one process has A locked, and the other has B locked.{"ABbaCc","CDBAabcd"}Returns: { 1, 3 }{"ABCabc","BCAabc","CABabc",""}Returns: { -1, 1, 2, -1 }If the scheduler allows the first process to lock A, B, and C, then the first process will finish. If it then allows the second process to lock B, and the third process to lock A and C, then the second process is waiting for the third process and vice-versa. The last process doesn't lock anything, so it is guaranteed to finish. Note that this is only one of many potential deadlock scenarios and that we picked this one based on the tie breaking rules in the problem statement.{"ABCDEabcde","ABCDEabcde","ABCDEabcde","ABCDEabcde","ABCDEabcde"}Returns: { }
Back to all problems