Most Likely Flashcards
Deadlock occurs when
every process in a set is waiting for an event that can only be caused by another process in the set
Deadlock can occur only when the following four conditions are satisfied:
Mutual exclusion
Hold and wait
No preemption
Circular wait
Mutual exclusion
only one process at a time can use a resource
Hold and wait
a process holding at least one resource is waiting to acquire additional resources held by other processes
No preemption
a resource can be released only voluntarily by the process holding it, after that process has completed its task
Circular wait
here 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.
A directed edge from a process to a resource is
called a request edge in system resource-allocation graph
The assignment edge is
a directed edge from a resource to a process.
A cycle in a resource-allocation graph is
not a sufficient condition for deadlock in the case that each resource has more than one instance.
A cycle in a resource-allocation graph is sufficient and necessary only
if each resource has only one instance.
Most OS pretend that deadlock
will never happen and leave it up to the responsibility of application programmer.
An unsafe state may lead to a
deadlocked state, but not necessary must lead to.
contiguous memory allocation
each process is contained in a single section of memory that is contiguous to the section containing the next process
With contiguous memory allocation, all portions of a process must be loaded into sequential physical memory partitions.
First fit
Allocate program to the first partition big enough to hold it
Best-fit
The allocator places a process in the smallest block of unallocated memory in which it will fit.
has the least wasted space and the smallest partition fitting the requirements.
worst-fit
Allocate program to the largest partition big enough to hold it
Allocate the largest hole. Again, we must search the entire list, unless it is sorted by size.
External fragmentation
is the phenomenon that results in unused blocks of memory outside of existing partitions.
All processes in a computer system share a
single inverted page table.
Each entry in the inverted page table contains
a process id and page number
Pure paging has
fixed page size, has internal fragmentation (so wasted memory is from internal fragmentation)
effective memory-access time
Average time required to access memory based on the TLB Hit Ratio.
translation look-aside buffer
Hardware cache of recently used page table entries. Smaller page size increases page count, resulting in larger page tables and smaller ____ hit ratio.
A small but fast-lookup hardware cache which stores page and frame numbers for memory access.
The optimal page replacement policy is
impossible to implement because it would require the OS to have perfect knowledge of future events.
A dead-lock free solution may still
have the problem of starvation.
Global replacement for page replacement which can select the replacement page from any other process has the problem that
a certain process cannot control it page-fault rate.
Local replacement only allows the system to
choose a replacement page from the pages belonging to the same process. Global replacement algorithm is more frequently used due to its efficiency in utilizing memory resources.
Copy-on-Write allows
the parent and child processes to initially share the same pages, but when either process modifies a page, a copy of the shared page is created
Thrashing occurs when
a process spends more time paging than executing.
