Synchronization cont. #

Weakness of the semaphore #

In class exercises #

• 2 semaphores, 1 mutex semaphore allowing access to laoding zone, and 1 counting semaphore checking if there is a car waiting
• mutex initialized to 1 (unlocked)
• car counting semaphore initialized to \( n \)

• 2 binary semaphores, with ping’s semaphore being set to 1 initially, and pong’s being set to 0.
• Since we want A to start, it’s initial semaphore is set to 1
• Since we want pong to be after, we set its initial semaphore value to 0

while(1)
    wait(A)
    print "ping"
    signal(B)

while(1)
    wait(B)
    print "pong"
    signal(A)

Deadlocks #

A situation where process sync becomes locked (like when all diners try to grab left chopstick in the philosopher’s problem). A system with limited resources may experience deadlock (if there were enough chopsticks then there wouldn’t be deadlock).

• if thread 1 runs first, it grabs the first mutex
• if there is a context switch, and thread 2 tries to gain mutex, it grab the second mutex
• when thread 1 tries to get second mutex, it will be blocked and have to wait
• both threads are now locked, waiting for each other
• eventually both threads will starve

This really happens because both threads are attempting to gain both mutexs in opposite order. If we visually graph this, you can see it forms a cycle:

Characterization #

When trying to avoid deadlock, we just need to make 1 of these above conditions false.

Resource allocation graph #

The above graph of the thread 1/2 deadlock was a resource allocation graph.

• requests edges can be approved or denied
• an assignment edge represents something that has already happened

• request edges point to the entire resource
• assignment (allocation) edges point to the particular instant of the resource