370 #5 - Concurrency, Interprocess Communication and Deadlock

Sharing resources - some resources can only be safely used by one thread at a time.

Any situation where the order of execution of threads can cause different results. Programmers have no control.

Only one.

Ensuring only one thread is active in a critical section.

• Deadlock
• Indefinite postponement - priority too low or just unlucky

Waste of time - no work is actually being executed but the processor is being used and the process's time slice is being used up.

1. It's a spin-lock/busy wait
2. No control over who gets the lock when it is freed - no queue or priority
3. It doesn't work! Thread knows that locked is now false and so is about to set locked to true but it's time slice ends before it can do so (time between while loop and setting locked value), which it will do as soon as it starts running again. While that process is waiting, another thread comes along and sees locked is false and sets it to be true. Thus two threads can set locked to be true, resulting in it no longer being a critical section.

• Only works on shared memory multiprocessors if instruction reordering can be turned off, otherwise need hardware help with memory barriers
• Two writes don't get interleaved at some minimum write size, the hardware allows only one processor access at a time.
• Only for two threads where flag and turn are shared between the two threads (i and j)

Aside from all of the restrictions and that it only works with two threads, there is still a busy wait.

Each thread is given a number indicating when it requests the lock i.e. scheduling number. These are not unique because they can be accessed concurrently, so we append the pid to it to make it unique. This number orders the access for the resource.

• Raise the interrupt priority level to stop any other process from running while the lock is being tested/checked
• Doesn't allow preemption of processor - thread is not swapped out while running the code testing the lock
• Not used anymore due to disadvantages

1. Heavy-handed: not all processes at the current interrupt priority level need to be stopped
2. Doesn't work efficiently on multiprocessors
3. A message requesting the IPL change must be sent to all processors, in some circumstances all other processors must wait

• Atomic/indivisible instructions used that appear interruptable - if this instruction is doing something, this entire instruction will execute without it's state being altered or being accessed by an outside thread
• testAndSet(lockVariable) - returns the value of that variable as it currently is and simultaneously sets the variable to be true
• Works for multiprocessors
• Still results in a busy wait

• Each thread can be made to wait while another thread gets access to the resource more than once
• Threads do not get access before any threads that request it later
• Indefinite postponement is possible
• A queue would help

• Should threads with higher priorities get prior access to resources?
• Makes the priority mechanism more effective
• Increases the chance of indefinite postponement