Week 3 - Mutual Exclusion

Question 1

Critical Sections

Answer 1

Set of steps algorithim that must be executed to update a shared data strucuture

repeat
«critical section»
«do other work»
forever;

Question 2

Race condition

Answer 2

outcome of two or more threads competing to modify shared data, where interference between threads results in erroneous results or a corrupted data structure.

Question 3

Mutual exclusion

Answer 3

methods to ensure only one thread does a particular activity, such as executing their critical section, at a time. i.e., all other threads are excluded from doing that activity.

Question 4

Atomicity

Answer 4

Mutual exclusion used to ensure that critical sections excute atomically.

An concurrent programming, code fragment is a piece of code that executes as a whole without interruption. Where no other code in other threads can interfere with execution.

Question 5

Race Conditions are Evil

Answer 5

Noxious kind of programming error.

They occur non-deterministically, causing intermittent faults.

• Program could be tested and never exhibit race condition.
• When program does crash randomly, and nobody knows why.

Question 6

Avoiding a Race Condtion

Answer 6

repeat
… do something to begin mutual exclusion…
«critical section»
… do something to end mutual exclusion…
«do normal work»
forever;

Question 7

Attempt at Mutal Exclusion (LOCK)

Answer 7

New shared boolean, lock, initialized to false, specifies whether thread is in its critical section.

Question 8

lock idea

Answer 8

when first thread is ready to enter critical section, its wait loop terminates immediately, lock is set to true, and critical section starts to execute.

if second thread wants critical section it will see lock is true, and wait loop iterates until the first thread leaves its critical section and sets lock back to false.

Question 9

Attempt at turn

Answer 9

a new shared variable called turn specifies whose turn it is to enter cirital section next.

Question 10

turn idea

Answer 10

turn is initalised to 0.

thread 0 is allowed to execute first cirital section.

• if thread 1 tries to enter its own critical section before thread 0 has finished, it waits in loop doing nothing.

when thread 0 leaves critical sction, turn is set to 1.

• if thread 1 was waiting in a loop, it then ends.

roles are now swapped, thread 0 cannot reenter the critical region until thread 1 has had its turn.

Question 11

problem with turn idea

Answer 11

Thread 1 may be blocked forever.

Guarantees safety but not progress.

Question 12

Algorthim interested

Answer 12

Two shared variables, interested [0] and interested [1]

they are boolean variables, either true or false.

when true interested[i] wants to enter critical section

Question 13

interested idea

Answer 13

both interested[0] and interested[1] set to false intialization.

thread sets to interested variable when wants enter into ciritcal region.
- if other interested it has to wait in loop until thread is finished crirtical section.

leave crirtical section, unset interested variavle, so other thread can have acess.

Question 14

interested problem

Answer 14

Doesnt establish mutual exlusion.

both threads now loop block forever.

guarntees safety, not progress.

Question 15

Petersons Algorithim

Answer 15

Discovered until 1981.

Late for such a fundamental and simple looking algorithm.

Question 16

Petersons Mutual Exclusion

Answer 16

Not useful in practise.

No easy generalization of more than two threads.

Relies on busy waiting, wasteful of CPU cycles.

Question 17

Petersons Mutual Exclusion solutions

Answer 17

Realistic solutions:
Parallel systems specialised atomic instructions.

Multitasking systems:
Support for synchronization into thread or process scheduling algorithims.

Question 18

Hardware Support: Test and Set

Answer 18

atomic instruction sometimes provided by hardware: Test and Set Lock (TSL).

Test and modify the content of a word atomically

Question 19

Mutual Exclusion With TSL

Answer 19

Using TSL, can do critical sections with the following approach.
Shared data: Boolean lock = false ; // initially

Question 20

Programming Abstractions

Answer 20

Parallel computers can use TSL and similar instructions to implement mutual exclusion and other kinds of synchronization.

Depends on busy waiting, and not appropriate in multi-tasking environments (because it wastes computer cycles).

Need higher-level abstractions for synchronization, that can be implemented either by low-level instructions like TSL, or OS scheduling algorithms.

Question 21

OS Support: Semaphores

Answer 21

semaphore S is an integer variable that may be accessed only using two operations P and V, with pseudocode essentially like atomic:

P(S) : S = S - 1; //decrease S

V(S) : S = S + 1;
// increase S

semaphore value must never go under 0.

Question 22

Evaluation of Semaphores

Answer 22

Semaphores provided one of the first high-level synchronization abstractions.

• Can be implemented efficiently on multiprocessors or in multi-tasking operating systems.

Question 23

Java Synchronized Methods

Answer 23

Java and several other modern programming languages use a version of the monitor idea.

methods in a Java class can be declared to be synchronized

If two threads try to call synchronized methods on the same object at the same time, one blocks until the other has completed.

static methods: if two threads try to call synchronized methods in the same class, one blocks.

Question 24

How Python implement synchronization?

Answer 24

you can use Join() method

threading module provides a Lock class to deal with the race conditions. Lock is implemented using a Semaphore object provided by the Operating System.

Python’s threading module offers: RLocks (Reentrant Locks), Semaphores and Barriers.