CSE 130 Quiz 4

AAAAAAAAAAAAAAAAAAAAAAAAAA

What are the lessons of the sleepy barber problem?

• Initialize semaphore to 0

• Semaphores coordinate two threads

  • T1: sem.down() causes T1 to wait

  • T2: sem.up() lets T1 proceed

• Use a mutex using a semaphore to protect its shared variables

  • T1: mutex.down() gets the lock

  • T2: mutex.down() must wait for T1 to release the lock with mutex.up()

• Semaphore’s up and down are atomic and you can make an atomic operation using mutexes (initialize semaphore mutex to 1)

• Up and down pairs must match

How many semaphores does each hungry philosopher use?

two (one semaphore for each chopstick)

What are the three cases with solution 1: semaphores for each chopstick in the hungry philosophers issue?

1. No contention

2. Need to wait. P0 needs to wait for P1 to put C[1] down down (P1 - C[1].up) before it can have it.

3. Deadlock. All 5 philosophers pick up one chopstick but cannot pick up the other and everyone is waiting on everyone

what is a resource?

something a process/thread uses; usually limited and thread needs exclusive access

(types of resources) can be taken away from a process with no ill effects

preemptable resource(ty

(types of resources) causes the process to fail if taken away

nonpreemptable resources

What kind of resource causes deadlock?

nonpreemptable resource

What is an infeasible region?

region to prevent t1 and t2 from accessing the same resource at the same time

what is the consequence of two infeasible regions?

unsafe regions; causes the progress of both tasks to permanently stop if thread progress enters it; deadlock— t1 has r2, wants r1, t2 has r1, wants r2

what are the four conditions of deadlock?

1. mutual exclusions- tasks claim exclusive control over resources

2. non-preemption- resource cannot be taken away

3. hold and wait- task holds a resource while waiting for another to release

4. circular wait - circular chain of 2 or more processes where each resource is held by the next member of the chain

how do you deal with deadlock?

• ignore the problem

• detect deadlock and recover from it

• prevent deadlock (avoid one of the four necessary conditions)

What is circular wait?

assign the order of resources and always acquire resources in that order

What does solution 2: grab the lower chopstick then wait for the higher numbered chopstick solve for the hungry philosophers?

deadlock

How do you do a resource graph?

• Vertex per resource

• Arrow per thread/task

• Tail for held resource

• Arrowhead for wanted resource

what is the ostrich algorithm?

Pretend there’s no problem; good if deadlocks are rare

How do you detect and recover from deadlock?

• Preemption - take resource from some other process

• Rollback - periodic checkpoints, restart a process if it is in deadlock

  • Kill one process in the deadlock cycle, choose one that can be rerun from the start

How do you prevent deadlock?

ensure that at least one of the conditions for deadlock never occurs

(Preventing Deadlock) eliminate mutual exclusion

spooling

(Preventing Deadlock) eliminate hold and wait

require processes to request resources before starting

What is livelock?

Processes still run, but don’t make progress

(Preventing Deadlock) eliminate “non-preemptive resources”

take resources away if there’s not a complete set and it won’t break the processes

Who holds and who wants? Who is deadlocked?

2, 4, 5, 7 are in deadlock

How can you see which resources are in deadlock in a resource graph?

They’re in a cycle and any process that wants a resource in the cycle is also deadlocked

(Preventing Deadlock) eliminating circular wait

order resources numerically

What is a high-level construct that implements locks/synchronization implicitly?

monitors

How do monitors work

One monitor has multiple entry points

Only one thread may be in the monitor at a time (no manual locking/unlocking)

How do you implement monitors

language/compiler, or use semaphores

How do condition variables work in monitors?

They have two operations — wait() and signal(). Only usable within monitors

What are the advantages and disadvantages of monitors?

Adv: better than locks, condition variables, and semaphores

Dis: not many programming languages support monitors

(Mutex Alternatives) Strict Alternation. What is its issue?

only two threads; take turns and use a shared variable to keep track of whose turn it is. Problem: if one of the processes no longer needed the CR, it wouldn’t access the CR to give the turn variable to the other process

(Mutex Alternatives) Dekker’s Algorithm

Threads express “interest” in the critical region, which alerts other threads; gives lock to thread only if the other thread is not interested and its the thread’s turn(Mutex Alternatives)

(Mutex Alternatives) Lamport’s Algorithm

allows multiple processes or threads to access a shared resource without conflicts. It works by assigning each process a number (ticket) when it wants to enter the critical section, and the process with the lowest number gets access first.

A pthreads condition variable is always associated with

• another condition variable

• a semaphore

• a mutex

a mutex

Which of the following is not a way to prevent deadlock?

• Avoid giving threads exclusive access to a shared resource

• Require all threads to acquire resources in the same order

• Require threads to release held resources before acquiring more

• Require threads to tolerate having their held resources taken away by the operating system

• None of the above

• None of the above

(T/F) In the dining philosopher problem, we associate one semaphore with each philosopher

false

Which if the following is not a mutual exclusion property?

• Any number of threads should be supported

• Only one thread can access a shared resource at a time

• The algorithm cannot busy wait

• Threads should not wait forever to enter a critical section

• Threads that are outside of a critical section cannot block other threads

• The algorithm cannot busy wait

A thread enters a “zombie state” when…

• it exits but has no value to return

• it exits before a call to pthread_join()

• it exits directly from the running state

• it cannot run for some reason

• it exits before a call to pthread_join()

my answers are not fully correct lol

1

S.down()

S.up()

S.down()

S.up()

my answers are not fully correct lol

N

T.down()

nothing

nothing

T.up()