CS4315 > Chapter 7 Pt.1 > Flashcards

Chapter 7 Pt.1 Flashcards

(60 cards)

Study These Flashcards
1
Q

What is a deadlock?

A

A state where a set of processes is blocked forever; each holds some resources and waits for others held by peers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

List the three phases of resource use in the system model

A

request; use; release

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are resource types and instances?

A

Resource types are categories like CPU or printer; each type Ri has Wi instances that can be allocated

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Give two examples of operating system resources

A

CPU cycles; memory space; I/O devices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Can deadlock involve same or different resource types?

A

Either; deadlock can involve same type or multiple different resource types

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Define mutual exclusion in deadlock characterization

A

Only one process at a time can use a nonsharable resource

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Define hold and wait

A

A process holds at least one resource while waiting to acquire additional resources held by others

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Define no preemption

A

Resources cannot be forcibly taken; they are released only voluntarily after use

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Define circular wait

A

When a group of processes are all waiting on each other in a loop, so nobody can move

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

When can deadlock arise according to the four conditions?

A

When mutual exclusion; hold and wait; no preemption; and circular wait all hold simultaneously

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a resource allocation graph RAG?

A

A directed graph with process vertices and resource type vertices showing requests and assignments

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a request edge in RAG notation?

A

A directed edge from process Pi to resource Rj meaning Pi is requesting an instance of Rj

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is an assignment edge in RAG notation?

A

A directed edge from resource Rj to process Pi meaning an instance of Rj is allocated to Pi

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How is a resource with multiple instances shown in RAG?

A

A resource node Rj annotated with multiple dots or boxes representing instances

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

State the basic fact about cycles and deadlock with single instance per type

A

If the RAG contains a cycle and each type has one instance; the system is deadlocked

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

State the basic fact about cycles with several instances per type

A

If the RAG contains a cycle with several instances; deadlock is possible but not guaranteed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

If the RAG has no cycles; what can we conclude?

A

No deadlock is present

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Name the four broad methods for handling deadlocks

A

Prevention; avoidance; detection and recovery; ignoring deadlock

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Which strategy is used by most mainstream OSes?

A

Ignoring deadlock; assume it never occurs; programmer handles rare cases

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Why might ignoring deadlock be acceptable in practice?

A

Deadlocks are rare; prevention or avoidance can be costly; detection may not be worth overhead

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Deadlock prevention aims to do what?

A

Ensure at least one of the necessary conditions never holds

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Can we deny mutual exclusion to prevent deadlock?

A

Only sharable resources like read-only files avoid the need for mutual exclusion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Prevention for hold and wait: describe Method 1

A

Require each process to hog all the resources before execution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Downside of Method 1 for hold and wait prevention

A

Wastes resources; Longer waiting at the beginningt; may over-allocate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Prevention for hold and wait: describe Method 2
If a process needs a new resource, it must drop everything it currently has, then request all the resources it needs again, including the new one.
26
Downside of Method 2
Can cause starvation; repeated release and reacquire; thrashing of resources
27
Prevention for no preemption: describe the protocol
If requested resources are held by a waiting process; preempt them for the requester; otherwise requester waits; waiting processes implicitly release resources
28
Downside of no preemption prevention protocol
Starvation risk for processes that are repeatedly preempted
29
Prevention for circular wait: what is the key idea?
We force all processes to request resources in a specific order. If everyone follows the same order, a circle wait can never form, so no deadlock.
30
Why does total ordering prevent cycles?
Edges always point from lower to higher ordered resources; a cycle would violate the ordering
31
Explain the lock ordering idea for transactions
Define a consistent global order on locks; always acquire in that order to avoid circular wait
32
Describe the classic two-account transfer deadlock scenario
Tx1 locks Account A then B; Tx2 locks B then A; each waits for the other; causing circular wait
33
What is deadlock avoidance in contrast to prevention?
Lets processes request resources freely, but the system checks each request first and only grants it if it keeps the system in a safe state.
34
What prior info does avoidance require from each process?
Each process must declare the maximum number of resources of each type it may need
35
Define a safe state
A safe state is a situation where the system can finish all processes in some order without getting stuck.
36
Relationship between safe states and deadlock
If in a safe state; no deadlock will occur; unsafe states may lead to deadlock but not always
37
What does avoidance try to ensure regarding unsafe states?
The system never enters an unsafe state through any allocation decision
38
Magnetic tape example: total tapes and processes
System has 12 magnetic tapes and three processes P0; P1; P2
39
In the tape example; what is the meaning of Still needs column
Maximum minus currently holding for each process; number of additional units required to complete
40
Why is sequence P1; P0; P2 safe in the example?
Freed tapes after P1 then P0 allow P2 to obtain its remaining needs; all can finish
41
RAG analysis: what must you check to prove no deadlock with multi-instance resources?
Look for cycles and confirm whether at least one process can still finish to break the cycle; if so deadlock may be avoided
42
Given a cycle in RAG with multi-instance resources; is deadlock certain?
No; termination of one process holding an instance may release resources and break the cycle
43
Why does hold and wait increase deadlock risk in practice?
It couples resource retention with new requests; forming wait chains that enable cycles
44
How does enforcing request in increasing resource order affect programmer effort?
Requires foreknowledge of resource needs and consistent coding discipline across the system
45
When might no preemption be impractical?
For resources that are not easily preemptable like printer output or regions with side effects
46
Why can prevention lead to low utilization?
Processes hoard resources early or release and reacquire frequently; leaving resources idle
47
Explain why safe state does not equal minimal resource use
Safe simply means a completion order exists; it does not optimize utilization or throughput
48
Give a simple method to test safety for a single resource type case
Simulate granting to processes whose remaining need is less than or equal to available; free on finish; repeat
49
In practice; what makes avoidance algorithms hard to use widely?
Need accurate maximum demand declarations; dynamic workloads change; overhead of checks
50
How can lock ordering be applied in large codebases?
Establish a global lock ranking document; static analysis or assertions enforce acquire order
51
Why does acquiring two mutexes in inconsistent order cause deadlock?
Thread A holds mutex 1 and waits for mutex 2; Thread B holds mutex 2 and waits for mutex 1; forms a circular wait
52
What lesson does the bank transfer example illustrate beyond ordering?
Design APIs that acquire all needed locks in one place; avoid layered calls that acquire locks inconsistently
53
What are the pros of ignoring deadlock in OS design?
Simplicity; lower overhead; programmer can design around rare cases or restart components
54
What are the cons of ignoring deadlock?
Latent failures; rare but catastrophic stalls; requires careful application-level recovery
55
How does detection and recovery differ from avoidance?
Detection allows unsafe states and finds deadlocks later; then kills processes or preempts resources to recover
56
Why is starvation a possible side effect in some prevention methods?
Repeated preemption or requeueing can delay a victim process indefinitely
57
What types of resources are generally sharable vs nonsharable?
Sharable: read-only files; caches; Nonsharable: printers; mutexes; memory pages in use
58
What simple rule prevents circular wait when using two locks?
Always acquire the lower ordered lock before the higher; release in reverse
59
How does a safe sequence relate to available resources at each step?
At each step a process can obtain its remaining need using available plus resources freed by earlier completions
60
Explain why unsafe does not imply immediate deadlock
There may still exist a path to completion; unsafe only means some future sequence of requests could cause deadlock
CS4315
flashcards
Decks in class (15)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions