Midterm Flashcards
POSIX
Portable Operating system Interface
BSD
Berkeley Software Distribution
GNU
GNU not Unix
deadlock
A set of two or more threads is deadlocked if each thread in the set is waiting (blocked) for an event that only another thread in the set can cause.
livelock
A livelock is a deadlock caused by busy waiting rather than being asleep (blocked).
starvation (p463-464) -
when a process must wait an excessive length of time for a resource
zombie state
A child that is terminated but the parent is no longer there to accept the exit message from the child.
What four conditions are necessary for a deadlock to occur?
- Mutual exclusion condition
A resource is assigned to exactly 1 thread or it is available - Hold and wait condition
a thread may hold resources while requesting additional resources - No preemption condition.
previously granted resources cannot forcibly be taken away - Circular wait condition.
must be a circular chain of 2 or more threads.
each is waiting for resource held by next member of the chain
who showed the deadlock conditions
Coffman
List four strategies that could be used to deal with deadlocks
- Just ignore the problem
general purpose computing because it’s cheap- Detection and recovery
- Dynamic avoidance
Possibility of deadlock exists, but system is monitored so it can be avoided - Prevention
Level the “cliff”
What does a “resource graph” look like?
Circles are processes, squares are resources, arrows from resources indicate ownership, and arrows from processes indicate requests (waits)
How can one be used to detect a deadlock?
A depth-first search of a linked list model of a resource graph will detect cycles, indicated by revisiting a previously visited node.
How could we detect deadlocks when there are multiple resources of each type
Using a current allocation matrix and a request matrix to roll down the requests from the allocations.
A = E - C, where: E = total of each resource C = how many of each resource is currently allocated A = total of each resource still available
Assuming that a deadlock could be detected, what 3 techniques are mentioned in the textbook
that could be used to recover from a deadlock?
- Recover through preemption
take a resource from some other process
depends on nature of the resource - Recovery through rollback
checkpoint a process periodically
use this saved state
restart the process if it is found deadlocked - Recovery through killing process
crudest but simplest way to break a deadlock
kill one of the processes in the deadlock cycle
the other processes get its resources
choose process that can be rerun from the beginning
What are “safe” and “unsafe” states?
Unsafe
Inside a box, but not yet at a corner, because a deadlock is inevitable unless the other process is terminated or releases a resource before making additional requests..
Safe
In any arbitrary box, or on the line of the “Danger Zone”box (box below and left of the double lined box).
Is an unsafe state the same thing as a deadlock?
No. An unsafe state indicates the future deadlock that can only be avoided by external forces or by one of the processes changing its mind about needing a resource.
Review Dijkstra’s Banker’s algorithm. You should be able to use the banker’s algorithm to
determine whether or not a given state is safe or unsafe.
Take A’s value, and see there are enough resources for a process to complete. After it completes, recount P and subtract to find new value of A. Wash, rinse, repeat.
List four techniques could theoretically be used to prevent deadlocks. Given a scenario that
describes a potential deadlock, you should be able to describe how each of these 4 techniques
would be used to prevent a deadlock.
- Avoid Mutual Exclusion
- Avoid Hold and Wait
if there is a deadlock, all processes give up their resources, then request all the resources they need to complete. - Avoid No Preemption condition
- Avoid Circular Wait
a process must be allowed all resources before it begins execution; used in databases
Cars, train, barge illustration - point is to request destination resource ahead of time, AKA numerical order, but not sequential.
Who was instrumental in the original development of UNIX?
Ken Thompson
Who designed the C programming language? For what company did they work?
Dennis Ritchie, Bell Labs
What were (are) some of the goals for the development of UNIX?
Consistent
Servant, not a nanny.
Non-redundant
What university was instrumental in the further development of UNIX?
UC Berkeley
What are some of the enhancements that this university implemented in their version of UNIX?
virtual memory, networking TCP/IP, long filenames
What is the primary purpose behind POSIX?
standards, trying to make UNIX the same in all implementations
Who wrote MINIX, a small UNIX-like operating system that was intended for instructional use?
Andrew Tanenbaum
Who expanded MINIX to make LINUX?
Linus Torvalds
