Midterm

Question 1

POSIX

Answer 1

Portable Operating system Interface

Question 2

BSD

Answer 2

Berkeley Software Distribution

Question 3

GNU

Answer 3

GNU not Unix

Question 4

deadlock

Answer 4

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.

Question 5

livelock

Answer 5

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

Question 6

zombie state

Answer 6

A child that is terminated but the parent is no longer there to accept the exit message from the child.

Question 7

What four conditions are necessary for a deadlock to occur?

Answer 7

1. Mutual exclusion condition
   A resource is assigned to exactly 1 thread or it is available
2. Hold and wait condition
   a thread may hold resources while requesting additional resources
3. No preemption condition.
   previously granted resources cannot forcibly be taken away
4. 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

Question 8

who showed the deadlock conditions

Answer 8

Coffman

Question 9

List four strategies that could be used to deal with deadlocks

Answer 9

1. Just ignore the problem
   general purpose computing because it’s cheap
   
   2. Detection and recovery
   3. Dynamic avoidance
      Possibility of deadlock exists, but system is monitored so it can be avoided
   4. Prevention
      Level the “cliff”

Question 10

What does a “resource graph” look like?

Answer 10

Circles are processes, squares are resources, arrows from resources indicate ownership, and arrows from processes indicate requests (waits)

Question 11

How can one be used to detect a deadlock?

Answer 11

A depth-first search of a linked list model of a resource graph will detect cycles, indicated by revisiting a previously visited node.

Question 12

How could we detect deadlocks when there are multiple resources of each type

Answer 12

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

Question 13

Assuming that a deadlock could be detected, what 3 techniques are mentioned in the textbook
that could be used to recover from a deadlock?

Answer 13

1. Recover through preemption
   take a resource from some other process
   depends on nature of the resource
2. Recovery through rollback
   checkpoint a process periodically
   use this saved state
   restart the process if it is found deadlocked
3. 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

Question 14

What are “safe” and “unsafe” states?

Answer 14

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).

Question 15

Is an unsafe state the same thing as a deadlock?

Answer 15

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.

Question 16

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.

Answer 16

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.

Question 17

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.

Answer 17

1. Avoid Mutual Exclusion
2. Avoid Hold and Wait
   if there is a deadlock, all processes give up their resources, then request all the resources they need to complete.
3. Avoid No Preemption condition
4. 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.

Question 18

Who was instrumental in the original development of UNIX?

Answer 18

Ken Thompson

Question 19

Who designed the C programming language? For what company did they work?

Answer 19

Dennis Ritchie, Bell Labs

Question 20

What were (are) some of the goals for the development of UNIX?

Answer 20

Consistent
Servant, not a nanny.
Non-redundant

Question 21

What university was instrumental in the further development of UNIX?

Answer 21

UC Berkeley

Question 22

What are some of the enhancements that this university implemented in their version of UNIX?

Answer 22

virtual memory, networking TCP/IP, long filenames

Question 23

What is the primary purpose behind POSIX?

Answer 23

standards, trying to make UNIX the same in all implementations

Question 24

Who wrote MINIX, a small UNIX-like operating system that was intended for instructional use?

Answer 24

Andrew Tanenbaum

Question 25

Who expanded MINIX to make LINUX?

Answer 25

Linus Torvalds