CSCI 3120 - Final Remaining Stuff Prep
Exam Questions With Solved Solutions
Graded A+.
What are the two deadlock avoidance algorithms? - Answer Resource Allocation Graph
Algorithm
Banker's Algorithm
What must be true of our system in order to use the wait-for deadlock detection algorithm? -
Answer The system must only have one instance for each resource type.
What are the different types of edges that can be present in the resource allocation graph
algorithm? - Answer Request edge - a process requests a resource
Assignment edge - a resource is assigned to a process
Claim edge - shows that a process is allowed to request a resource
Describe the Resource Allocation Graph Algorithm - Answer Resource requests can only be
granted if doing so does not result in the creation of a cycle (we check using cycle detection
algorithm)
What is a wait-for graph used for? - Answer Deadlock detection
How does a wait-for graph work? - Answer Is derived from our original resource allocation
graph, but removes all resource nodes.
Instead we only have process nodes, and directed edges connect processes that are requesting
resources to the processes using the resources they need.
ie. it shows the processes and which ones are "waiting-for" others to finish.
,Periodically invoke a cycle detection algorithm
When do systems typically invoke cycle detection algorithms? - Answer Depends on how often
deadlocks are likely to occur and how many processes will be affected by a deadlock.
How do systems handle deadlocks when they occur? - Answer Either abort one or more
processes, or preempt some resources from one or more of the deadlocked processes (reassign
their resources)
What are the two possible methods used to eliminate deadlocks by aborting processes? -
Answer Abort all deadlock processes (this is bad. Processes are ABORTED, no context
switching takes place so information is lost)
Abort one process at a time (less risk of losing data, but deadlock detection algorithm must be
called every time we abort a process)
If we choose to eliminate deadlocks by aborting processes, and choose one at a time, how do
we choose? - Answer We choose the one with minimum cost. Cost is determined by:
- Priority of process
- How long the process has been running
- How much more time it needs
- How many resources it is using
- How many more resources are needed to complete
If we choose to eliminate deadlocks by preempting resources, what issues need to be
addressed? - Answer Which resources / processes should be preempted?
What do we do with a process if we preempt its resources? Typically abort and restart
How do we prevent starvation (ie. how do we avoid preempting the same process over and
over)?
, How quickly can the CPU access data from a register? Memory? - Answer Registers can be
accessed within one cycle of the CPU clock.
Memory can take many cycles.
What what must happen if data or instructions for the CPU is not in memory or in a register? -
Answer It must be retrieved and placed in memory for the CPU to access it
In what capacity do we allow user processes to interact with the operating system? - Answer
In a limited / protected capacity.
How do we protect the operating system from access by user processes? - Answer Ensure that
each process has its own memory space. This also helps protect user processes from one
another.
How do we specify legal addresses in practice? - Answer Using a base register (specifies the
smallest legal memory address) and limit register (specifies the size of the range allotted to a
process)
What happens if a process tries to access memory that it isn't allowed to (ie. memory used by
OS or other processes)? - Answer Trap occurs in OS; illegal addressing error
When a program is not being run, where is it typically kept? - Answer On disk as a binary
executable file
When a process is being loaded into main memory, how may its address be represented? -
Answer In the program, appear symbolically as variables
Compiler links symbolic addresses to relocatable addresses (ie. not specific; "14 bytes from the
beginning of module")
Linker or loader binds the relocatable addresses to specific (absolute) addresses
What is a logical / virtual address? - Answer Run from 0 to MAX. Memory addresses from the
perspective of a user program. Logical addresses are mapped to physical addresses
Exam Questions With Solved Solutions
Graded A+.
What are the two deadlock avoidance algorithms? - Answer Resource Allocation Graph
Algorithm
Banker's Algorithm
What must be true of our system in order to use the wait-for deadlock detection algorithm? -
Answer The system must only have one instance for each resource type.
What are the different types of edges that can be present in the resource allocation graph
algorithm? - Answer Request edge - a process requests a resource
Assignment edge - a resource is assigned to a process
Claim edge - shows that a process is allowed to request a resource
Describe the Resource Allocation Graph Algorithm - Answer Resource requests can only be
granted if doing so does not result in the creation of a cycle (we check using cycle detection
algorithm)
What is a wait-for graph used for? - Answer Deadlock detection
How does a wait-for graph work? - Answer Is derived from our original resource allocation
graph, but removes all resource nodes.
Instead we only have process nodes, and directed edges connect processes that are requesting
resources to the processes using the resources they need.
ie. it shows the processes and which ones are "waiting-for" others to finish.
,Periodically invoke a cycle detection algorithm
When do systems typically invoke cycle detection algorithms? - Answer Depends on how often
deadlocks are likely to occur and how many processes will be affected by a deadlock.
How do systems handle deadlocks when they occur? - Answer Either abort one or more
processes, or preempt some resources from one or more of the deadlocked processes (reassign
their resources)
What are the two possible methods used to eliminate deadlocks by aborting processes? -
Answer Abort all deadlock processes (this is bad. Processes are ABORTED, no context
switching takes place so information is lost)
Abort one process at a time (less risk of losing data, but deadlock detection algorithm must be
called every time we abort a process)
If we choose to eliminate deadlocks by aborting processes, and choose one at a time, how do
we choose? - Answer We choose the one with minimum cost. Cost is determined by:
- Priority of process
- How long the process has been running
- How much more time it needs
- How many resources it is using
- How many more resources are needed to complete
If we choose to eliminate deadlocks by preempting resources, what issues need to be
addressed? - Answer Which resources / processes should be preempted?
What do we do with a process if we preempt its resources? Typically abort and restart
How do we prevent starvation (ie. how do we avoid preempting the same process over and
over)?
, How quickly can the CPU access data from a register? Memory? - Answer Registers can be
accessed within one cycle of the CPU clock.
Memory can take many cycles.
What what must happen if data or instructions for the CPU is not in memory or in a register? -
Answer It must be retrieved and placed in memory for the CPU to access it
In what capacity do we allow user processes to interact with the operating system? - Answer
In a limited / protected capacity.
How do we protect the operating system from access by user processes? - Answer Ensure that
each process has its own memory space. This also helps protect user processes from one
another.
How do we specify legal addresses in practice? - Answer Using a base register (specifies the
smallest legal memory address) and limit register (specifies the size of the range allotted to a
process)
What happens if a process tries to access memory that it isn't allowed to (ie. memory used by
OS or other processes)? - Answer Trap occurs in OS; illegal addressing error
When a program is not being run, where is it typically kept? - Answer On disk as a binary
executable file
When a process is being loaded into main memory, how may its address be represented? -
Answer In the program, appear symbolically as variables
Compiler links symbolic addresses to relocatable addresses (ie. not specific; "14 bytes from the
beginning of module")
Linker or loader binds the relocatable addresses to specific (absolute) addresses
What is a logical / virtual address? - Answer Run from 0 to MAX. Memory addresses from the
perspective of a user program. Logical addresses are mapped to physical addresses
