COP 4610 EXAM 2 WANG STUDY GUIDE
Monitor - Answer -A lock + condition variables
Lock - Answer -provides mutual exclusion to shared data.
a lock provides two operations
-Acquire()
-Release()
Condition Variable - Answer -provides a queue for waiting threads inside a critical
section
each conditional variable
-consists of a queue of threads
-Provides three operations
**wait()
**Signal()
**Broadcast()
Hoare vs. Mesa Monitors - Answer -Hoare Monitors (used in most textbooks)
-Signal() transfers the CPU directly to a waiting thread.
Mesa Monitors (used in most real operating systems)
-Signal() only puts a waiting thread on the scheduler's ready queue
-By the time the waken thread gets the CPU, the waiting condition may no longer be
true and needs to be retested.
Semaphores VS Monitors - Answer -We can't quite implement monitors with
semaphores.
Condition variables only work inside a lock
-using semaphores inside a lock may deadlock
Condition variables have no history, but semaphores have
-Signal() with an empty queue does nothing
**A subsequent Wait() will wait
-V() increments semaphore
**A subsequent P() will not wait
-Wait() will always wait
-P() might not wait
Deadlock - Answer -Occur when threads are waiting for resources with circular
dependencies.
, Deadlock implies starvation
Preemptable Resource - Answer -EX- CPU
can be resolved by reallocation of resources
Nonpreemptable Resource - Answer -A resource that cannot be taken away from its
current owner without causing computation to fail
Starvation - Answer -a thread waits indefinitely
Checkpointing - Answer -taking snapshots of system states from time to time
Four Conditions for Deadlocks - Answer -limited access (lock-protected resources)
no preemption (if someone has the resource, it cannot be taken away)
wait while holding (holding a resource while requesting and waiting for the next
resource)
circular chain of requests
Banker's Algorithm - Answer --A thread states its maximum resource needs in advance.
-The OS allocates resource dynamically as needed. A thread waits if granting its
request would lead to deadlocks.
-A request can be granted if some sequential ordering of threads is deadlock free.
Deadlock Recovery Techniques - Answer -* Scan the resource allocation graph
* Detect circular chains of requests
* Recover from the deadlock
Interprocess Communication - Answer -Processes communicate among address
spaces.
-Bug stream ex. pipe
-Message passing (send/receive)
-File system (read and write)
-Shared memory
Direct
-send(P1, message);
-receive(P2, message);
-One-to-one communication
Monitor - Answer -A lock + condition variables
Lock - Answer -provides mutual exclusion to shared data.
a lock provides two operations
-Acquire()
-Release()
Condition Variable - Answer -provides a queue for waiting threads inside a critical
section
each conditional variable
-consists of a queue of threads
-Provides three operations
**wait()
**Signal()
**Broadcast()
Hoare vs. Mesa Monitors - Answer -Hoare Monitors (used in most textbooks)
-Signal() transfers the CPU directly to a waiting thread.
Mesa Monitors (used in most real operating systems)
-Signal() only puts a waiting thread on the scheduler's ready queue
-By the time the waken thread gets the CPU, the waiting condition may no longer be
true and needs to be retested.
Semaphores VS Monitors - Answer -We can't quite implement monitors with
semaphores.
Condition variables only work inside a lock
-using semaphores inside a lock may deadlock
Condition variables have no history, but semaphores have
-Signal() with an empty queue does nothing
**A subsequent Wait() will wait
-V() increments semaphore
**A subsequent P() will not wait
-Wait() will always wait
-P() might not wait
Deadlock - Answer -Occur when threads are waiting for resources with circular
dependencies.
, Deadlock implies starvation
Preemptable Resource - Answer -EX- CPU
can be resolved by reallocation of resources
Nonpreemptable Resource - Answer -A resource that cannot be taken away from its
current owner without causing computation to fail
Starvation - Answer -a thread waits indefinitely
Checkpointing - Answer -taking snapshots of system states from time to time
Four Conditions for Deadlocks - Answer -limited access (lock-protected resources)
no preemption (if someone has the resource, it cannot be taken away)
wait while holding (holding a resource while requesting and waiting for the next
resource)
circular chain of requests
Banker's Algorithm - Answer --A thread states its maximum resource needs in advance.
-The OS allocates resource dynamically as needed. A thread waits if granting its
request would lead to deadlocks.
-A request can be granted if some sequential ordering of threads is deadlock free.
Deadlock Recovery Techniques - Answer -* Scan the resource allocation graph
* Detect circular chains of requests
* Recover from the deadlock
Interprocess Communication - Answer -Processes communicate among address
spaces.
-Bug stream ex. pipe
-Message passing (send/receive)
-File system (read and write)
-Shared memory
Direct
-send(P1, message);
-receive(P2, message);
-One-to-one communication