1) Base of hexadecimal number system? Answer : 16 2) Universal gate in digital logic? Answer : NAND 3) Memory type that is non-volatile? Answer : ROM 4) Basic building block of digital circuits? Answer : Gate 5) Device used for data storage in sequential circuits? Answer : Flip-flop 6) Architecture with shared memory for instructions and data? Answer : von Neumann 7) The smallest unit of data in computing? Answer : Bit 8) Unit that performs arithmetic operations in a CPU? Answer : ALU 9) Memory faster than main memory but smaller in size? Answer : Cache 10) System cycle that includes fetch, decode, and execute? Answer : Instruction 11) Type of circuit where output depends on present input only? Answer : Combinational 12) The binary equivalent of decimal 10? Answer : 1010 13) Memory used for high-speed temporary storage in a CPU? Answer : Register 14) Method of representing negative numbers in binary? Answer : Two's complement 15) Gate that inverts its input signal? Answer : NOT 16)...
Deadlock Detection
i. If deadlocks are not avoided, then another method is to detect when they have occurred and recover
somehow.
ii. In addition to the performance hit of frequently checking for deadlocks, a policy / algorithm must be in place for recovering from deadlocks, and there is potential for lost work when processes must be deleted or have their resources prevented.
Single Instance of Each Resource Type
i. If each resource category has a single instance, then we can use a variation of the resource-allocation
graph known as a wait-for graph.
ii. A wait-for graph can be built from a resource-allocation graph by eliminating the resources and collapsing the associated edges, as shown in the figure below.
iii) An arc from Pi to Pj in a wait-for graph implies that process Pi is waiting for a resource that process Pj is currently holding.
As before, cycles in the wait-for graph imply deadlocks.
This algorithm must maintain the wait-for graph, and constantly search it for cycles.
Several Instances of a Resource Type Available:
A vector of length m implies the number of available resources of each type.
Allocation: An n x m matrix defines the number of resources of each type presently assigned to each process.
Request: An n x m matrix implies the current request of each process. If Request [ij] = k, then process
Pi is requesting k more occurence of resource type. Rj .
Detection Algorithm
1. Let Work and Finish be vectors of length m and n, accordingly Initialize:
(a) Work = Available(b) For i = 1,2, …, n,
if Allocationi != 0, then
Finish[i] = false;
otherwise,
Finish[i] = true
2. Find an index i similar that both:
(a) Finish[i] == false
(b) Requesti <=Work
If no such i exists, go to step 4
3. 3. Work = Work + Allocationi
Finish[i] = true go to step 2
4. If Finish[i] == false, for some i, 1 <= i <=n, then the system is in deadlock state.
Moreover, if Finish[i] == false, then Pi is deadlocked
Algorithm requires an order of O(m x n2) operations to detect whether the system is in deadlocked
state.
Example of Detection Algorithm
Five processes P0 through P4; three resource types A (7 instances), B (2instances), and C (6 instances) Snapshot at time T0:
Now suppose that process P2 makes a request for an additional instance of type C, yielding the state shown below. Is the system now deadlocked?
Detection-Algorithm Usage
i. When should the deadlock detection be done? Frequently, or infrequently?
The answer may depend on how frequently deadlocks are expected to occur, as well as the possible consequences of not catching them immediately.(If deadlocks are not removed immediately when they occur, then more and more processes can "back up" behind the deadlock, making the eventual task of
unblocking the system more difficult and possibly damaging to more processes. )
ii. There are two obvious approaches, each with trade-offs:
1) Do deadlock detection after every resource allocation which cannot be immediately granted. This has the advantage of detecting the deadlock right away, while the minimum number of processes are involved in the deadlock (One might consider that the process whose request triggered the deadlock condition is the "cause" of the deadlock, but realistically all of the processes in the cycle are equally responsible for the resulting deadlock. ) The down side of this approach is the extensive overhead and performance hit caused by checking for deadlocks so frequently.
2) Do deadlock detection only when there is some clue that a deadlock may have occurred, such as when CPU utilization reduces to 40% or some other magic number. The advantage is that deadlock detection is done much less frequently, but the down side is that it becomes impossible to detect the processes involved in the original deadlock, and so deadlock recovery can be more complicated and damaging to more processes.
3) ( As I write this, a third alternative comes to mind: Keep a historical log of resource allocations, since that last known time of no deadlocks. Do deadlock checks periodically ( once an hour or when CPU usage is low?), and then use the historical log to trace through and determine when the deadlock occurred and what processes caused the initial deadlock. Unfortunately I'm not certain that breaking the original deadlock would then free up the resulting log jam. )