CSCE4600 Final Flashcards
How many milliseconds in 1 second
1000 (10^-3)
How many microseconds in 1 second
1000000 (10^-6)
How many nanoseconds in 1 second
(10^-9)
What are the 3 different types of approaches for the deadlock problem
Detection and Recovery
Prevention
Avoidance
What are reusable resources
permanent objects with two properties
What are consumable resources
produced and consumed dynamically
What are the two properties of reusable resources
1) # of units is constant
2) each unit is available or allocated to
exactly one process
What are the three properties of consumable resources
1) # of units will vary over time;
2) system can create new units
3) process may request, acquire,
and consume resource units
T/F: With single unit resources, cycle -> deadlock
True
What are the 4 points of cycles and knots
deadlock -> cycle
cycle !-> deadlock
expedient & knot -> deadlock
deadlock !-> knot
What is a blocked state
no action by process Pi will result in a state change,
does not mean deadlock
What is a secure state
S is not a deadlock state and any state T reachable by S is not a deadlock state
What is total deadlock
If all processes Pi are deadlocked in state S
What is a deadlock state
If Pi is deadlocked in state S
T/F: does a cycle always mean dependency
False
What are the four conditions for deadlock
1) Mutual Exclusion
2) Nonpreemption
3) Resource waiting
4) Partial Allocating
What is mutual exclusion
Processes hold resources exclusively, hence making them unavailable to other processes
What is non preemption
Resources cannot be taken away from a process that is holding them. Only the process can release the resources they hold
What is resource waiting (Circular Wait)
Processes that request unavailable resources (or units) will block until they become available.
What is Partial allocation
Processes may hold some resources when they request additional units of the same resource or other resources. (Hold and Wait)
What is a sink
A node with no outgoing edges
What is an isolated node
A node with no outgoing and no inbound edges
What is a path
a sequence (a,b,c ..y,z) of at least two nodes for which (a, b) ε E
What is a cycle
a path with the same first and last vertex
What is a reachable set
reachable(z) = {b | there is a path from z to b}
What is a knot
All nodes are reachable from any other node
What is compile time
The compiler translates symbolic addresses to absolute addresses
What is load time
Generates relocatable code if memory location is not known at compile time
What is execution time
binding is delayed until runtime of the process can be moved during its execution from one segment to another
What is a logical address
generated by the CPU; also referred to as virtual address
What is a physical address
address seen by the memory unit
Which address space tends to be larger?
Logical
how many frames is physical memory
2^25
how many frames is logical memory
2^32
what is a relocation register
is added to every address generated by a user process at the time it is sent to memory
What does a relocation register contain
value of smallest physical address
what is a limit register
contains range of logical addresses
logical address must be…
less than the limit register
what is a hole
block of available memory
what is external fragmentation
when we have sufficient space in memory but the space is not contiguous
pros and cons for best fit
pro: better speed and storage utilization, leaves very large holes and very small holes
cons: very small holes may be useless, must search entire list
pros and cons for first fit
pros: better speed and storage utilization, leaves “average” size hoes
cons: may end up clustering towards top
pros and cons for worst fit
pros: allocates the largest holes
cons: must search entire list, worst in terms of storage utilization
what is internal fragmentation
the wasted memory space when the requested memory is slightly smaller than the allocated memory
what is compaction
move allocated blocks such that a single region of free memory is maintained
all internal addresses may have to be relocated and not always possible
pros and cons for fixed partition
pro: easy to implement, fast context switches
cons: suffers from internal fragmentation, one size does not fit all (example: large processes)
pros and cons for variable partition
pro: no internal fragmentation, allocates just enough for process
con: large overhead to keep track of free memory
variable partitioning requires…
coalescing, or combining neighboring small holes into contiguous memory
what is buddy system
splits block into two equal buddies, continuous until smallest block greater than or equal to s is generated
are frames physical memory or logical memory
physical
are pages physical memory or logical memory
logical
used as an index into a page table which contains base address for each page
page number
combined with base address to define the physical memory address
page offset
What are the 4 steps to a basic page replacement
1) find the location of desired page on disk
2) find a free frame (if no free frame use page replacement algo to select victim)
3) read the desired page into new free frame and update page and frame tables
4) resume the process
what does a 1 valid-invalid bit mean
in-memory
what does a 0 valid-invalid bit mean
not in memory
if valid-invalid bit is 0…
page fault
What are the 5 steps to the page fault process
1) look at another table to decide if invalid reference, abort, or just not in memory
2) get empty frame
3) Swap page into frame
4) reset tables, validation bit = 1
5) restart instructions
what is locality
code that is executed frequently and executes a few fragments at one time
what does belady’s optimal algorithm do
replace page that will not be used for the longest period of time
free to select a victim from any page in memory
global policies
defines a working set that belongs to the same processes or group of processes and selects a victim from them
local policies
what is thrashing
when a process is busy swapping pages in and out
Compiler: If you know at compile time where the process will reside in memory
then absolute code can be generated (Static)
Loader: If it is not known at compile time where the process will reside in memory
then the compiler must generate relocatable code
how many bytes are in a megabyte
1000000 (10^6)
how many bytes are in a kilobyte
1000 (10^3)
