Operating systems Flashcards
to study
What defines a process in deadlock ?
if every process in the set is
waiting for an event that can be caused only by another process in the set.
What is a pre-emptible resource ?
A pre-emptible resource is one that can be taken away from a process with no ill effect to the process; e.g., memory.
What is a non pre-emptible resource ?
A non-preemptible resource is one that cannot be taken away from its user since it will make the user fails; e.g., printers
What are the four necessary conditions for deadlock to occur ?
- Mutual exclusion condition. Only one process at a time can use the resource.
- Hold and wait condition. A process holding at least one resource is waiting to acquire additional resources held by other processes.
- No pre-emption condition. A resource can be released only voluntarily by the process holding it after that process has completed its task.
- Circular wait condition. 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.
Name the 3 methods for HANDLING deadlock ?
- Use a protocol to ensure that the system will never reaches
deadlock
– Using deadlock prevention and/or deadlock avoidance techniques - Allow the system to enter a deadlock state and then recover
– needs deadlock detection and deadlock recovery algorithms - Ignore the problem and pretend that deadlocks never occur in
the system
– used by most OS, including UNIX
Name the 3 deadlock prevention techniques.
- Deny mutual exclusion. ( Note this can only be used with shareable resources).
- Deny hold and wait. (Must guarantee that whenever a process requests a resource, it does not hold any
other resources). - Prevent no pre-emption (i.e., allow pre-emption)
- Deny circular wait. (All resources are ordered and each resource must request increasing order of resources.
Name some techniques for the deny hold and wait technique and state an issue with it.
- Each process is granted all resources before it starts
- Allows a process to request resources only when it has none
Problems:
- Resource utilisation is low
- Possible starvation.
Describe the no pre-emption technique and give a problem with it.
When a process holding some resources requests other resource that cannot
be immediately allocated, it must release all resources currently being held .
Problem:
Can be applied easily to resources whose state can be saved easily (e.g.,
memory), but not so easily for others (e.g., printer)
Name a problem with the deny circular wait technique.
It may be impossible to find a resource ordering
that satisfies everyone
what is the safe state ?
When a process requests an available resource, the system checks if its allocation keeps the system in safe state
The system is in safe state if there exists a safe sequence of all processes
What is deadlock avoidance and what is it used for?
Used to keep a system in a safe state.
The system must have some additional priori information
about which resources a process will request and use during its lifetime.
The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
What is the banker’s algorithm ?
Each process must have a priori claim that states the maximum number of instances of each resource type that it may need .
Name and describe the 2 types of deadlock detection ?
- For single instance of each resource type:
Maintain a wait for graph and invoke an algorithm that searches for a cycle in the graph - For several instances of a resource type:
Uses data structures.
Available: a vector of length M.
Allocation: n x m matrix. Defines the number of resources of each type currently allocated to each
process.
Request: n × m matrix. Indicates the current request of each process
What are the 2 deadlock recover techniques?
- Terminate processes
Kill (abort) all deadlocked processes
Kill one process at a time until deadlock cycle eliminated - Pre-empt a resource from a process
Name a problem with the termination of a process technique?
what if the process is in the middle of updating a file?
Aborting the process may lead to incorrect file
Nam a problem with the pre-empt a recourse from a process technique.
Starvation – same process may always be picked as victim
Define memory
Memory is a large array of words or bytes, each with its own address
What is a volatile sortrage device ?
It loses its contents in the case of system failure.
What 3 things are the OS responsible for when it comes to memory?
- Keep track of which parts of memory are being used and by whom.
- Decide which processes to load next when memory space becomes available.
- Allocate and deallocate memory.
What is binding ?
mapping from one address space to another
What are the 3 types of binding time ?
- Compile time:
- Load time: binding is delayed until code loaded into memory.
- Execution time: binding is delayed until run time
What is the difference between logical and physical address space ?
Logical address – generated by the CPU.
Physical address – address seen by the memory unit.
Logical and physical addresses are the same in compile-time and load-time address-binding schemes.
Logical and physical addresses are different in execution-time address binding scheme.
What is the MMU ?
Memory-management unit
A piece of hardware.
The run-time mapping from virtual to physical addresses is done by the MMU.
What is dynamic loading ?
Routine is not loaded until it is called.
To have a better memory-space utilization.
Useful when large amounts of code are needed to handle infrequently occurring cases.
No special support from the OS is required.
What is dynamic linking ?
Linking is delayed until execution time.
Used for system libraries
Small piece of code, Stub, is used to locate the appropriate memory-resident library routine.
OS needs to check if the routine is in process’ memory address.
What is contiguous allocation
each process is in one contiguous memory location
What is memory fragmentation ?
2 Types:
1. External :
total memory space exists to satisfy a request, but
it is not contiguous.
- Internal:
the
allocated memory may be slightly larger than requested memory.
What is compaction
Used to reduce external fragmentation
Shuffle memory contents to place all free memory together in one large block.
is possible only if relocation is dynamic, and is done at
execution time.
must determine the cost à the size of memory contents that have to be moved; the less the better.
What is paging ?
Another solution to the external fragmentation
may create internal fragmentation.
A process is allocated physical memory when it is available.
The physical memory is divided into fixed-sized blocks called frames.
The logical memory is divided into fixed-sized blocks called pages.
What is the modify bit ?
Also known as the dirty bit.
Used to to reduce overhead of page transfer
Each page is associated with a dirty bit
– When a page is modified, set its dirty bit
– Only modified pages are written back to disk
What is thrashing ?
each process is busy swapping pages in and
out
Thus, spending more time paging than executing
Thrashing results in severe performance problems
This occurs because:
If a process does not have enough frames, the page-fault
rate is very high. This leads to:
– Low CPU utilization
– OS thinks that it needs to increase the degree of
multiprogramming
Name the 2 algorithms used to reduce the effect of thrashing
- Local:
-Only replace frames belonging to this process.
-Only slows this process down dramatically
-Slows others as well, but not as much
-Stops other processes thrashing. - Priority:
- Only high priority process can steal frames from low
priority processes.
- Low priority processes can be thrashing
- Low priority processes decrease speed.
What is demand paging ?
- Processes reside on secondary memory (usually disk).
- Bring a page (not entire process) into memory only when it is needed
advantages: – Less I/O needed. – Less memory needed. – Faster response. – More users.
-Needs hardware support to distinguish between those pages that are in memory and those pages that are on disk.
