V is partitioned into two types:
P={
Thursday, August 27, 2009
Thursday, August 20, 2009
deadlock
1.Deadlock Characterization
necessary conditions:
1) Mutual exclusion:
• at least one shared resource is held
2) Hold and wait:
• a process must be holding at least one resource andwaiting for another
3) No preemption:
• cannot steal a resource away from a process
4) Circular wait:
• E.g., A is waiting for B who is waiting for C who iswaiting for A.
necessary conditions:
1) Mutual exclusion:
• at least one shared resource is held
2) Hold and wait:
• a process must be holding at least one resource andwaiting for another
3) No preemption:
• cannot steal a resource away from a process
4) Circular wait:
• E.g., A is waiting for B who is waiting for C who iswaiting for A.
3.deadlock prevention
*negate one of the necessary conditionsNegating Mutual Exclusion :
example:shared use of a printer
»give exclusive use of the printer to each user in turn wanting to print?
»deadlock possibility if exclusive access to another resource also allowed
»better to have a spooler process to which print jobs are sent
-complete output file must be generated first
example: file system actions
»give a process exclusive access rights to a file directory
example: moving a file from one directory to another
-possible deadlock if allowed exclusive access to two directories simultaneously
-should write code so as only to need to access one directory at a time
*negate one of the necessary conditionsNegating Mutual Exclusion :
example:shared use of a printer
»give exclusive use of the printer to each user in turn wanting to print?
»deadlock possibility if exclusive access to another resource also allowed
»better to have a spooler process to which print jobs are sent
-complete output file must be generated first
example: file system actions
»give a process exclusive access rights to a file directory
example: moving a file from one directory to another
-possible deadlock if allowed exclusive access to two directories simultaneously
-should write code so as only to need to access one directory at a time
deadlock
4.deadlock detection
• Allow system to enter deadlock state
• Detection algorithm
•Recovery scheme
• Allow system to enter deadlock state
• Detection algorithm
•Recovery scheme
5.deadlock recovery
•Pre-emption–take resources from a process and give to others
–how to select a victim?
»order of precedence for pre-empting
»number of resources already held
»how many more will it need to complete?
»amount of CPU time already used–swapping process out of memory may be sufficient
»but may still hold resources involved in deadlock
–may need to roll pre-empted process back
»back to some safe restart point or go back to beginning
»may need to checkpoint processes
»not convenient for user interaction!
–need to avoid starvation of a low priority process always being pre-empted
»include number of previous pre-emptions as a choice factor
•Pre-emption–take resources from a process and give to others
–how to select a victim?
»order of precedence for pre-empting
»number of resources already held
»how many more will it need to complete?
»amount of CPU time already used–swapping process out of memory may be sufficient
»but may still hold resources involved in deadlock
–may need to roll pre-empted process back
»back to some safe restart point or go back to beginning
»may need to checkpoint processes
»not convenient for user interaction!
–need to avoid starvation of a low priority process always being pre-empted
»include number of previous pre-emptions as a choice factor
Sunday, August 16, 2009
real-time scheduler
The real-time scheduler (Scheduler/RealTime../ns-2/scheduler.cc) attempts to synchronize the execution of events with real-time. It is currently implemented as a subclass of the list scheduler. The real-time capability in ns is still under development, but is used to introduce an ns simulated network into a real-world topology to experiment with easily-configured network topologies, cross-traffic, etc. This only works for relatively slow network traffic data rates, as the simulator must be able to keep pace with the real-world packet arrival rate, and this synchronization is not presently enforced.
The real-time scheduler (Scheduler/RealTime../ns-2/scheduler.cc) attempts to synchronize the execution of events with real-time. It is currently implemented as a subclass of the list scheduler. The real-time capability in ns is still under development, but is used to introduce an ns simulated network into a real-world topology to experiment with easily-configured network topologies, cross-traffic, etc. This only works for relatively slow network traffic data rates, as the simulator must be able to keep pace with the real-world packet arrival rate, and this synchronization is not presently enforced.
Subscribe to:
Posts (Atom)
