Banker's algorithm
E79782
Banker's algorithm is a classic deadlock-avoidance algorithm in operating systems that safely allocates resources to processes by simulating and verifying that the system will remain in a safe state.
Observed surface forms (2)
| Surface form | Occurrences |
|---|---|
| Resource Allocation in Multiprocess Computer Systems | 1 |
| banker's algorithm | 1 |
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
deadlock avoidance algorithm
ⓘ
operating system algorithm ⓘ resource allocation algorithm ⓘ |
| appliesTo | multiple instances of each resource type ⓘ |
| assumes |
fixed number of processes
ⓘ
fixed number of resource types ⓘ maximum resource demand known in advance ⓘ processes eventually release resources ⓘ |
| basedOn | safe state concept ⓘ |
| category | deadlock handling technique ⓘ |
| checks | safety of resource allocation ⓘ |
| complexity | polynomial time in number of processes and resources ⓘ |
| contrastedWith |
deadlock detection
ⓘ
deadlock prevention ⓘ |
| deniesRequestIf | resulting state is unsafe ⓘ |
| developedBy | Edsger W. Dijkstra ⓘ |
| ensures |
each process can complete eventually in a safe state
ⓘ
system remains in a safe state ⓘ |
| exampleUsedIn | resource allocation problems in textbooks ⓘ |
| formalizedIn | matrices and vectors ⓘ |
| goal | find safe sequence of process execution ⓘ |
| grantsRequestIf | resulting state is safe ⓘ |
| inspired | later research in deadlock avoidance ⓘ |
| introducedIn | 1960s ⓘ |
| involves |
resource request algorithm
ⓘ
safety algorithm ⓘ |
| limitation |
assumes resources are reusable
ⓘ
high runtime overhead for large systems ⓘ not suitable when maximum demands are unknown ⓘ |
| models | banker-customer relationship ⓘ |
| nameOrigin | analogy with a banker granting loans ⓘ |
| notApplicableTo | single-instance resource deadlock avoidance ⓘ |
| prevents |
circular wait
ⓘ
deadlock ⓘ |
| property | conservative in resource allocation ⓘ |
| relatedTo |
deadlock state
ⓘ
safe state ⓘ unsafe state ⓘ |
| requires |
allocation matrix
ⓘ
available resources vector ⓘ maximum demand matrix ⓘ need matrix ⓘ preemption not allowed for allocated resources ⓘ processes declare maximum resource needs ⓘ |
| simulates | future resource allocation sequences ⓘ |
| taughtIn | operating systems courses ⓘ |
| usedFor |
deadlock avoidance
ⓘ
safe resource allocation ⓘ |
| usedIn | operating systems ⓘ |
Referenced by (3)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
banker's algorithm
this entity surface form:
Resource Allocation in Multiprocess Computer Systems