"a bit of everything" Kobe Flashcards
What is meant by a task being blocked?
That it is waiting on a blocking synchronisation action
When is a set of tasks D considered deadlocked? Three conditions:
- All tasks in D are blocked or terminated
- There is at least one non-terminated task in D
- For each non-terminated task t in D, any task that might block t is also in D
What are four program conditions that may lead to deadlock?
- Mutual exclusion
- Greediness (holding and waiting)
- Absence of preemption mechanisms
- Circular waiting
What two types of resources have their access associated with deadlocks?
- Consumable resources that are taken away upon use.
- Reusable resources that are given back after use.
What are a great model for the analysis of deadlocks? What are two types of these models?
Graphs
Wait-for graphs and dependency graphs
What two things do wait-for graphs model best? How about dependency graphs?
Consumable resources and condition synchronisations
Reusable resources and action synchronisations
What do the nodes in wait-for graphs represent?
How about edges?
What does an edge p1->p3 represent?
What are the edges labelled with?
What does the wait-for graph capture?
Tasks, i.e., activities, threads/processes
Wait-for (blocked-on) relationships.
p3 is blocked on p1
Corresponding blocking conditions
A possible dynamic situation (reachable system state), whose existance must be proven.
When is a deadlock possible in a wait-for graph?
Only if there is a CYCLE in the wait-for graph and NO TASK OUTSIDE any cycle can UNBLOCK a task in the cycle.
How can one use a wait-for graph to prove the abscence of deadlocks?
Through a proof by contradiction.
Assume one task T in the graph is blocked on a certain action. Add T to a new graph
Add each task T’ that can unblock T to the new graph, creating an edge from T’ to T labeled with the blocking condition it may unblock.
Check whether each task T’ can possible be blocked on an action. If yes, repeat from 1 with T’.
Once the whole graph is built, check if we are in a deadlock state. If no, we reached a contradiction. If yes, we are in a potential deadlock and we should build a trace showing how we reached that state.
What type of graph are resource dependency graphs? What do the nodes represent? How about the edges?
Bipartite graphs
Two classes of nodes, one for tasks and one for resources
Three types of edges, depending on type of outgoing and incoming nodes
Let p be a task and R a resource. What does the edge p->R represent in a dependency graph? How about R->p? How about p–>R
p->R represents that task p is requesting resource R and now waiting for it
R->p represents that task p holds resource R
p–>R represents that task p MAY request resource R
What does a resource dependency graph represent? What are three types of events that may change the state?
A particular state of the system
A request by a task, An acquisition of a resource by a task, A release of a resource by a task
When is a task in a resource dependency graph blocked?
When it has an outgoing edge that is not directly removable, i.e., for which the requested resource is not free
When is there a deadlock in a resource dependency graph?
When after removing non-blocked tasks and all their incoming connections, there rem,ains a set of tasks.
What are three active approaches to dealing with deadlocks?
Prevention at design time by programmer
Avoidance on system side by dynamically checking to avoid entering risky state
Detection and Recovery by checking only whether we are in a deadlock state, and trying to recover from it
What is prevention?
How can dependency graphs be used?
Wait-for graphs?
What are some synchronisation tricks that can be used?
How does preemption play a role?
analysing your system using reduced dependency graphs and wait-for graphs at design time to provide a proof that there can never be any deadlock
Make their reductions be empty.
Prevent cycles in the graphs
No circular wait, ensuring termination of critical sections, locking resources in a fixed order, acquiring all resources at once
Preemption of resources must be allowed when needed
How does avoidance work?
Upon executing each potentially blocking action:
check if an open execution path exists (i.e., that will avoid deadlocks)
if one does not, deny or postpone the action
the check can be carried out with a reduction of the max claim graph
What is a maximum claim graph?
Dependency graph extended to capture potential future resource claims
What is Banker’s algorithm?
What does c[j] represent?
How about max[i,j]?
What is its aim?
An avoidance algorithm
Number of resources of type j
Maximum number of resources of type j that may be needed by task i
Synchronising requests such that each taskc an always acquire resources until its specified maximum
What does avail[j] represent in the Banker’s algorithm?
How about alloc[i,j]?
How about claim[i,j]?
What are the initial states of all these?
What are the invariants related to these?
Number of resources of type j still available?
Number of resources of type j allocated to task i
Maximum number of resources of type j that may still be claimed by task i
Avail[j] = c[j], Alloc[i,j] = 0, claim[i,j] = max[i,j]
Avail[j] = c[j] - Sum of Alloc[i,j] for all i
claim[i,j] = max[i,j] - alloc[i,j]
When is a state called open for a task i? How would you specify this mathematically?
When all the resources it may claim can be directly given to it
Claim[i,j] is less than or equal to Avail[j]
When is a state called safe for a task?
When this task can eventually be given its maximum number of resources
When is a state called safe?
When it is safe for all tasks
Assume a safe state, and a new request on resource j by task i. If this request were fulfilled, is it enough to check whether the resulting state is safe for task i to determine whether the resulting state is safe overall? Why or why not?
How could state safety be checked?
Yes, because if it is safe for task i, then all resources owned by task i will eventually be returned, reaching a state at least as safe as the current one.
Repeat the following:
1. Find an open task
2. Remove it, and all its claims (graph reduction)
3. Until task i is found to be open
What does the NextOpen function do?
What happens if no task can proceed in the NextOpen function?
In the NextOpen function, what does Alloc[i] != 0 check?
What does Claim[i] <= Avail ensure in the NextOpen function?
It finds the index of the first open task that can proceed based on the available resources and claimed resources.
The function returns N, indicating no open task is available.
It checks if the task i is active (has allocated resources).
It ensures the remaining resource claim of task i can be satisfied with the current available resources.
What is the precondition for calling the Safe function?
Avail >= req must hold, meaning the available resources can cover the requested resources.
What does the line Avail = Avail - req in the Safe function simulate?
How does the Safe function check if the system remains safe after allocation?
What does Avail = Avail + Alloc[k] in the Safe function do?
Why is the Claim[k] reset to Max[k] when task k completes?
What does the Safe function return?
What happens inside the while loop in the Safe function?
It reduces available resources by the amount requested by task i.
It simulates completing tasks using the NextOpen function and checks if resources can satisfy all remaining claims.
It simulates releasing all resources held by task k back to the available pool.
To indicate that task k has finished and no longer needs resources.
true if the system is in a safe state after allocation, otherwise false.
The function iterates through open tasks, simulating their completion, until the system is safe or no open tasks remain.
What is the purpose of the Safe function in the Banker’s Algorithm?
To ensure that allocating resources to a task will not lead the system into an unsafe state.
What is the Banker’s Algorithm, and how does it work in detail?
The Banker’s Algorithm is a deadlock avoidance method that ensures safe resource allocation by simulating whether a system can remain in a safe state after granting resource requests. It works by checking if resource allocation to processes is possible without causing a system-wide deadlock. It concerns one particular request, and simulates whether granting that request would lead to a safe state or not?
What does the detection algorithm do during execution?
What is required for deadlock detection during execution?
What is a major drawback of repeated monitoring and recovery from deadlock?
Where can the recovery algorithm be executed?
What are the two approaches for killing tasks in a deadlock set?
What does rolling back to a safe state require?
What does preempting resources in a deadlock involve?
It is invoked periodically to check if deadlock occurs.
An algorithm to examine the state upon execution of a blocking action, and an algorithm to recover from a deadlock.
It causes large overheads.
Locally, inside the task that last blocked or globally, through a recovery policy.
Kill all tasks, and kill some tasks based on specific criteria.
An alternative execution path must exist, and the state must be recorded at checkpoints (sufficient history information to roll back).
Deallocating resources from tasks in the deadlock state.
What are the different schemes for the prevention approach?
Requesting all resources at once.
Preemption.
Resource ordering.
What are the major advantages of the prevention approach?
Works well for processes that perform a single burst of activity.
No preemption necessary.
What are the major disadvantages of the prevention approach?
Inefficient.
Delays process initiation.
Future resource requirements must be known by processes.
What are the major advantages of the avoidance approach?
What are the major disadvantages of the avoidance approach?
No preemption necessary.
Future resource requirements must be known by the OS.
Processes can be blocked for long periods.
What are the major advantages of the detection approach?
What are the major disadvantages of the detection approach?
Never delays process initiation.
Facilitates online handling.
Inherent preemption losses.
What are the resource allocation policies for the three approaches (Prevention, Avoidance, and Detection)?
Prevention: Conservative; undercommits resources to ensure that deadlocks cannot occur. It enforces strict rules to avoid unsafe states by limiting resource allocation.
Avoidance: Balances between prevention and detection by cautiously allocating resources to maintain at least one safe path. The system dynamically analyzes the current state and future requests to avoid potential deadlocks.
Detection: Very liberal; resources are granted whenever possible without regard to potential deadlocks. This approach focuses on detecting and resolving deadlocks after they occur.
What is a resource in the context of processes?
Anything needed for a process to run, such as main memory, space on a disk, or the CPU
How does an OS abstract resources? What represents disk space? How about memory use? How about CPU use?
By creating simplified representations of hardware:
Files represent disk space
Processes represent memory use
Threads represent CPU use
How does an OS manage resource sharing? Three ways
Space sharing (allocates different resources to different programs simultaneously)
Time sharing (allows programs to share resources over time by switching between them)
OS Isolation Mechanisms (protect resources and programs, ensuring they do not interfere with each other or compromise system stability)
What are the four main components of the OS kernel in logical OS organization?
Process and thread manager.
File manager.
Memory manager.
Device manager.
What does the process and thread manager interact with?
Memory manager for virtual memory management.
Processor(s) for scheduling and task execution.
What does the file manager interact with?
Memory manager for performance improvement (e.g., caching data).
Device manager for accessing storage devices.
What is the role of the memory manager in logical OS organization?
Coordinates with the process manager for virtual memory (e.g., scheduling and memory allocation).
Interacts with the file manager for performance improvement (e.g., data caching).
Manages access to main memory.
How do modules in the OS kernel coordinate their activities?
All modules (process manager, file manager, memory manager, device manager) interact to ensure efficient resource allocation and system performance.
What are the two requirements for process execution?
A running program must be brought from disk to main memory
Each process must have a distinct address space for protection
What are the six characteristics of a good memory from the user/program perspective?
Non-volatile.
Private for a program (protected).
Infinite capacity.
Zero access time.
Simple to use.
Cheap.
What are the characteristics of CPU registers in the memory hierarchy?
They have the fastest access speed (1 clock cycle)
They are limited in size
They store the most frequently accessed data
