CS4315 - Final Review || with Complete Solutions.
(T/F) Deadlock can arise if some of the conditions hold simultaneously. correct answers False
(T/F) All safe states are deadlock free, but not all unsafe states lead to deadlocks correct answers
True
Mutual Exclusion correct answers only one process at a time can use a resource
Hold and Wait correct answers a process holding at least one resource is waiting to acquire
additional resources held by other processes
No preemption correct answers A resource can be released only voluntarily by the process
holding it, after that process has completed its task
Circular Wait correct answers there exists a set {P0 , P1 , ..., Pn } of waiting processes such that
P0 is waiting for a resource that is held by P1 , P1 is waiting for a resource that is held by P2 , ...,
Pn-1 is waiting for a resource that is held by Pn , and Pn is waiting for a resource that is held by
P0 .
Prevent deadlock-mutual exclusion correct answers This condition cannot be denied, unless for
sharable resources, e.g., a real-only file
Prevent deadlock-hold and wait correct answers Method 1:
Each process requests and is allocated all its resources before execution (no waiting)
Method 2:
If a process needs to acquire a new resource, it must first release all resources it holds, then
reacquire all it needs (no holding)
Prevent deadlock-no preemption correct answers A protocol: A waiting process will implicitly
release its current resources
If a process requests some resources
- Resources are free: allocate them
- Resources are held by a waiting process: preempt the resources and allocate them to this
process
- Otherwise: the requesting process must wait (since the resources are being used by other
running processes)
Deadlock prevention-Cyclic wait correct answers One way to ensure that this condition may not
hold
- Imposing a total ordering of all resource types
- Requiring that each process requests resources in an increasing order of enumeration
- Release resources in a decreasing order
,What is deadlock avoidance? correct answers Ensuring that a system will never enter an unsafe
state.
What does Deadlock Avoidance require to work? correct answers Requires each process to
declare the maximum number of resources of each type that it may need
What does it mean for a system to be in a safe state? correct answers System is in safe state if
there exists a sequence of ALL the processes in the systems such that for each Pi , the resources
that Pi can still request can be satisfied by currently available resources + resources held by all
the Pj , with j < i
What is the banker's algorithm? correct answers The Banker's algorithm is a resource allocation
and deadlock avoidance algorithm used in operating systems. It tests for safety by simulating the
allocation of predetermined maximum possible amounts of all resources, then makes an "s-state"
check to test for possible deadlock conditions for all other pending activities, before deciding
whether allocation should be allowed to continue
What is the process for recovering from deadlock? correct answers 1. Choose a blocked process
2. Preempt it
3. Run the detection algorithm
4. Iterate it until the state is not a deadlock state
Recovery from deadlock: Selecting a victim. correct answers minimize cost
Recovery from deadlock: Rollback correct answers return to some safe state, restart process for
that state
Recovery from deadlock: Starvation correct answers same process may always be picked as
victim, include number of rollback in cost factor
What is a base register? correct answers holds the smallest legal physical memory address
What is a limit register? correct answers contains the size of the range of legal physical memory
addresses
What will happen if a memory access is attempted outside the valid range? correct answers If a
memory access is attempted outside the valid range, then hardware will generate a fatal error.
What is address binding? correct answers It is the process of mapping a program's logical
addresses to corresponding physical addresses.
Address Binding: Compile Time correct answers -knows exactly where value should be stored
-address is fixed
-not flexible
, Address Binding: Load Time correct answers Must generate relocatable code if memory location
is not known at compile time
Address Binding: Execution Time correct answers Binding delayed until run time if the process
can be moved during its execution from one memory segment to another.
- Used by most general-purpose operating systems
What is a logical address? correct answers the address generated by the CPU, also referred to as
virtual address
What is a physical address? correct answers the address seen by the memory unit (loaded into
Memory Address Register)
Execution/run-time mapping from virtual to physical address is done using _____ correct
answers Memory-management unit (MMU)
Why need mapping logical address to physical address? correct answers it allows the operating
system to manage memory more efficiently by using techniques such as paging and
segmentation. Logical addresses provide a layer of abstraction that allows processes to access
memory without knowing the physical memory location. This abstraction makes it easier to
manage memory and allows the operating system to allocate memory to processes more
efficiently.
What is the Memory-management unit (MMU) used for? correct answers The MMU translates
logical addresses into physical addresses using the page table. This translation is transparent to
the process and is performed by hardware.
What is static linking? correct answers library modules get fully included in executable modules,
wasting both disk space and main memory usage (because every program that included a certain
routine from the library would have to have their own copy of that routine linked into their
executable code).
What is a stub? correct answers a small piece of code indicating how to locate the appropriate
library routine
What is dynamic linking? correct answers Only a stub is linked into the executable module,
containing references to the actual library module linked in at run time. Only one copy of the
library routine is loaded.
What is swapping? correct answers If there is not enough memory available to keep all running
processes in memory at the same time, then some processes who are not currently using the CPU
may have their memory swapped out to a fast local disk called the backing store.
It is important to swap processes out of memory only when there are no pending I/O operations.
Why? correct answers It is important to swap processes out of memory only when there are no
(T/F) Deadlock can arise if some of the conditions hold simultaneously. correct answers False
(T/F) All safe states are deadlock free, but not all unsafe states lead to deadlocks correct answers
True
Mutual Exclusion correct answers only one process at a time can use a resource
Hold and Wait correct answers a process holding at least one resource is waiting to acquire
additional resources held by other processes
No preemption correct answers A resource can be released only voluntarily by the process
holding it, after that process has completed its task
Circular Wait correct answers there exists a set {P0 , P1 , ..., Pn } of waiting processes such that
P0 is waiting for a resource that is held by P1 , P1 is waiting for a resource that is held by P2 , ...,
Pn-1 is waiting for a resource that is held by Pn , and Pn is waiting for a resource that is held by
P0 .
Prevent deadlock-mutual exclusion correct answers This condition cannot be denied, unless for
sharable resources, e.g., a real-only file
Prevent deadlock-hold and wait correct answers Method 1:
Each process requests and is allocated all its resources before execution (no waiting)
Method 2:
If a process needs to acquire a new resource, it must first release all resources it holds, then
reacquire all it needs (no holding)
Prevent deadlock-no preemption correct answers A protocol: A waiting process will implicitly
release its current resources
If a process requests some resources
- Resources are free: allocate them
- Resources are held by a waiting process: preempt the resources and allocate them to this
process
- Otherwise: the requesting process must wait (since the resources are being used by other
running processes)
Deadlock prevention-Cyclic wait correct answers One way to ensure that this condition may not
hold
- Imposing a total ordering of all resource types
- Requiring that each process requests resources in an increasing order of enumeration
- Release resources in a decreasing order
,What is deadlock avoidance? correct answers Ensuring that a system will never enter an unsafe
state.
What does Deadlock Avoidance require to work? correct answers Requires each process to
declare the maximum number of resources of each type that it may need
What does it mean for a system to be in a safe state? correct answers System is in safe state if
there exists a sequence of ALL the processes in the systems such that for each Pi , the resources
that Pi can still request can be satisfied by currently available resources + resources held by all
the Pj , with j < i
What is the banker's algorithm? correct answers The Banker's algorithm is a resource allocation
and deadlock avoidance algorithm used in operating systems. It tests for safety by simulating the
allocation of predetermined maximum possible amounts of all resources, then makes an "s-state"
check to test for possible deadlock conditions for all other pending activities, before deciding
whether allocation should be allowed to continue
What is the process for recovering from deadlock? correct answers 1. Choose a blocked process
2. Preempt it
3. Run the detection algorithm
4. Iterate it until the state is not a deadlock state
Recovery from deadlock: Selecting a victim. correct answers minimize cost
Recovery from deadlock: Rollback correct answers return to some safe state, restart process for
that state
Recovery from deadlock: Starvation correct answers same process may always be picked as
victim, include number of rollback in cost factor
What is a base register? correct answers holds the smallest legal physical memory address
What is a limit register? correct answers contains the size of the range of legal physical memory
addresses
What will happen if a memory access is attempted outside the valid range? correct answers If a
memory access is attempted outside the valid range, then hardware will generate a fatal error.
What is address binding? correct answers It is the process of mapping a program's logical
addresses to corresponding physical addresses.
Address Binding: Compile Time correct answers -knows exactly where value should be stored
-address is fixed
-not flexible
, Address Binding: Load Time correct answers Must generate relocatable code if memory location
is not known at compile time
Address Binding: Execution Time correct answers Binding delayed until run time if the process
can be moved during its execution from one memory segment to another.
- Used by most general-purpose operating systems
What is a logical address? correct answers the address generated by the CPU, also referred to as
virtual address
What is a physical address? correct answers the address seen by the memory unit (loaded into
Memory Address Register)
Execution/run-time mapping from virtual to physical address is done using _____ correct
answers Memory-management unit (MMU)
Why need mapping logical address to physical address? correct answers it allows the operating
system to manage memory more efficiently by using techniques such as paging and
segmentation. Logical addresses provide a layer of abstraction that allows processes to access
memory without knowing the physical memory location. This abstraction makes it easier to
manage memory and allows the operating system to allocate memory to processes more
efficiently.
What is the Memory-management unit (MMU) used for? correct answers The MMU translates
logical addresses into physical addresses using the page table. This translation is transparent to
the process and is performed by hardware.
What is static linking? correct answers library modules get fully included in executable modules,
wasting both disk space and main memory usage (because every program that included a certain
routine from the library would have to have their own copy of that routine linked into their
executable code).
What is a stub? correct answers a small piece of code indicating how to locate the appropriate
library routine
What is dynamic linking? correct answers Only a stub is linked into the executable module,
containing references to the actual library module linked in at run time. Only one copy of the
library routine is loaded.
What is swapping? correct answers If there is not enough memory available to keep all running
processes in memory at the same time, then some processes who are not currently using the CPU
may have their memory swapped out to a fast local disk called the backing store.
It is important to swap processes out of memory only when there are no pending I/O operations.
Why? correct answers It is important to swap processes out of memory only when there are no
