Flashcards in Midterm Deck (62):
What are the 4 conditions for deadlock?
1. mutual exclusion
2. hold and wait
3. no pre-emption
4. circular wait
what condition is it when only one process may use a resource at a time?
what is the hold and wait deadlock condition?
a process may hold allocated resources while awaiting the assignment of others
what is "no pre-emption?
when no resource can be forcibly removed from a process holding it
what is "circular wait?"
a closed chain of processes where each process holds at least one resource needed by another process in the chain
what are the 3 approaches to dealing with deadlock?
prevent, avoid, detect
how do you prevent circular wait?
by defining a linear ordering of resource types
what are the two approaches to deadlock avoidance?
resource allocation denial, process initiation denial
list 2 advantages of deadlock avoidance over other deadlock avoidance strategies
- not necessary to preempt and rollback process like in deadlock detection
- less restrictive than deadlock prevention
what are the restrictions on deadlock avoidance?
- maximum resource requirement for all processes must be stated in advance
- processes being considered must be independent with no synchronization requirements
- a fixed number of resources must be allocated
- no process can exit holding resources
what does "unsafe status" signal in deadlock avoidance?
that deadlock is a possibility
list the advantages and disadvantages of deadlock detection algorithms
advantages: leads to early detection, simple algorithms
disadvantages: frequent checks consume processor time
how can a system recover from a deadlock?
- abort all deadlocked processes
- abort deadlock processes one by one until deadlock is gone
- back up deadlocked processes to a previous checkpoint and restart all processes
- preempt resources until deadlock is gone
what are GPU's?
graphical processing units that provide computations on arras of data
what are DSP's?
digital signal processors for streaming signals
what are the two steps to instruction execution?
1. process fetches instructions from memory
2. processor executes each instruction
what are interrupts?
interrupts, interrupt the normal sequencing of the processor
what is the purpose of interrupts?
to improve process utilization
what are the interrupt classes and how are they generated?
Program: generated by a condition
Timer: generated by a timer
I/O: generated by I/O controller
Hardware failure: generated by failure
what does an os do?
what is batch processing?
set of programs are executed in a linear sequential order, no manual intervention, data is collected in batches of files
what is the uniprogramming (single batch) approach?
processor spends some amount of time executing until it hits an I/O instructions, must wait for I/O instruction to finish before continuing
what is the multi programming batch approach?
when one job is waiting on I/O, processor can switch to another job
what are the 3 components of a process?
1. an executable program
2. the associated data
3. executable context (process state) of the program
what is in the "trace" of a process
sequence of instructions that get executed for that process
what does the dispatcher do
switches processor from on process to another
what are the 2 characteristics of a process?
- resource ownership
what are the contents of a thread?
- execution state
- thread context
- execution stack
- static storage for local variables
- access to memory and resources of its process (all threads of a process share this stuff)
what benefits are provided by using threads?
- threads can be created faster than processes
- threads can be killed faster than processes
- switching between threads is faster than switching between processes
- threads enhance communication efficiency between programs
what happens to the threads of a process when that process is terminated?
they are all terminated as well
if a process is suspended what happens to its threads?
they are also suspended
what manages user level threads?
what are the advantages of ULT's? (User level threads)
- don't need kernel mode privileges to switch threads
- scheduling can be app specific
- ULT's run on any OS
what are the disadvantages of ULTs?
- when ULTs execute system calls not only is the thread normally blocked but so are all other threads associated with the process
how do you overcome the system call blocking that occurs in ULT?
Jacketing: coverts blocking sys calls to non-blocking sys calls, this is done by writing an app as multiple processes instead of multiple threads`
what are the advantages of KLT? (kernel level threading)
- kernels can schedule multiple threads from the same process on multiple processors at the same time
- if a thread is blocked the kernel can schedule another thread in the same process
- kernel allows multi threading
what are the disadvantages of KLTs
- transferring control between threads in the same process requires a mode switch to the kernel
when does the logical address (LA) change?
when does the physical address (PA) change?
when a swap occurs, i.e when the process location changes
how is the PA computed?
PA = LA + Base
what is the "BASE" in memory relocation
a cpu registered maintained by the OS that is updated after a context switch
what are the shortcomings of simple swapping?
- memory limits
- one size fits all (need to fragment)
- zero protection
what is a paging scheme?
memory is divided into equal chunks (pages) and processes can have as many pages as they require
what does simple paging allow? what does it manage to avoid?
for processes to be of different sizes, it avoids fragmentation
what is the key insight of virtual memory?
why swap all of a process? why not just swap in only the pages we need?
how is it that the memory space of each process can be bigger than the amount of physical memory in a computer?
because with virtual memory every process thinks it has access to the entire memory space
what is a page fault?
when a program tires to access objects not currently in memory
how does the OS respond to a page fault?
it performs a context switch pausing active process to bring needed page out from memory
what are the differences between paging and segmentation?
- pages are all the same length, segments can vary in size
- paging is invisible, segments are explicitly managed by the program
what are the drawbacks of fixed blocks for dynamic memory management?
- no flexibility
- lots of waste (oh you need 10 bytes?
here's a whole fackin block mate)
- fragmentation is possible if a larger block is needed then what the list is made up of
why can't the relative speed of execution of processes be predicted?
- activities of other processes can impact a process
- OS handle interrupts differently
- OS have different scheduling policies
what is the "race condition"?
when multiple processes or threads read and write data items and the final result depends on the order of execution ("loser" of the race is the process that updates last)
what must an OS do to deal with concurrency
- keep track of various processes
- allocate and de-allocate resources
- protect data and physical resources from interference from other processes
- ensure process outputs are independent of the speed of execution
what 3 control problems must be faced when dealing with competing processes?
- need for mutual exclusion
what are the requirements for mutual exclusion?
- needs to be enforced no matter what
- a process must not interfere with other processes when it halts
- a process needs to be able to access a critical section if no other process is using it
- relative process speeds or number of processes are irrelevant
- a process remains in its critical section for a finite time only
what are the disadvantages of interrupt disabling for mutual exclusion?
- efficiency of execution goes down
- will not work on multiprocessor architecture`
what are the advantages of special machine instruction for mutual exclusion?
- applicable to any number of processes on single or multiprocessors sharing memory
- simple and easy to verify
- can support multiple critical sections (each defined by its own variable)
what are the disadvantages of special machine instructions for mutual exclusion?
- while processes wait for access to critical section it consumes processor time
- starvation is possible when process leaves critical section and several processes are waiting
- deadlock is also possible
how can you know whether a semiphore will block or not?
you can't know before a process decrements
if two processes are running currently how can a semiphore indicated which process will continue immediately on a uni processor
it can't help
can you know using a semiphore how many processes are waiting?