Quiz 3/Ch5 Synchronization

Question 1

Deadlock, Starvation, Priority Inversion

Answer 1

Deadlock – two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
… …
signal(S); signal(Q);
signal(Q); signal(S);

Starvation – indefinite blocking (one process)

• > A process may never be removed from the semaphore queue in which it is suspended
• ->May occur if we remove processes from the list associated with a semaphore in LIFO order

Priority Inversion – Scheduling problem when lower-priority process holds a lock needed by higher-priority process
->Solved via priority-inheritance protocol

Question 2

Semaphore: busy waiting vs no busy waiting

Answer 2

Classic implementation: when count reaches zero, process will block() until resource becomes available, creating busy waiting.

• > busy waiting semaphores are also called spinlocks
• > semaphore value is never negative

No busy implementation: each semaphore has an associated waiting queue where they place processes when count = 0.

• > block() places process invoking the operation on the waiting queue
• > wakeup removes a process in the waiting queue & places it in the ready queue
• > semaphore value can be negative. Indicates how many processes are waiting on that semaphore.

Question 3

Semaphore

Answer 3

**More sophisticated than mutex locks

Semaphore S – integer variable
Can only be accessed via two indivisible (atomic) operations (wait & signal)
–>wait() decrements count of resources available
–>signal() increments count of resources available

Counting semaphore – integer value can range over an unrestricted domain
Binary semaphore – integer value can range only between 0 and 1
Same as a mutex lock

Question 4

Mutex Locks

Answer 4

Protect a critical section by first acquire() a lock then release() the lock
–>Boolean variable indicating if lock is available or not

Calls to acquire() and release() must be atomic
–>Usually implemented via hardware atomic instructions

But this solution requires busy waiting
–>This lock therefore called a spinlock

**Spinlocks are good in multiprocessor systems when the critical section is short, a process may spin on a processor waiting for the other to exit the critical section. NO context switch needed, thus it reduces the CS overhead.

Question 5

Atomic Hardware instructions/solutions

Answer 5

**All solutions are based on idea of locking

Atomic = non-interruptible (don’t want to interrupt the conversion of high-level code to assembly… high-level could have one instruction turned into 3, fetch from memory, increment in register, rewrite to memory)

1. Either test memory word and set value
2. Or swap contents of two memory words

Question 6

Preemptive vs non-preemptive

Answer 6

Preemptive – allows preemption of process when running in kernel mode
Non-preemptive – runs until exits kernel mode, blocks, or voluntarily yields CPU
Essentially free of race conditions in kernel mode

**Preemptive are more suitable for real-time systems

Question 7

Solution to Critical-Section Problem

Answer 7

1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections
2. Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely
3. Bounded Waiting - A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted
   Assume that each process executes at a nonzero speed
   No assumption concerning relative speed of the n processes

Question 8

Race Condition

Answer 8

Two or more processes accessing the same shared data at the same time and outcome depends on the order of execution.

Question 9

Readers-Writers Problem

Answer 9

A data set is shared among a number of concurrent processes

• > Readers – only read the data set; they do not perform any updates
• > Writers – can both read and write

Problem – allow multiple readers to read at the same time
->Only one single writer can access the shared data at the same time

Several variations of how readers and writers are considered – all involve some form of priorities

Shared Data

• > Data set
• > Semaphore rw_mutex initialized to 1
• > Semaphore mutex initialized to 1
• > Integer read_count initialized to 0 (shared variable, protected by the mutex)

Question 10

Readers-Writers variables

Answer 10

To ensure that these difficulties do not arise, we require that the writers have exclusive access to the shared database while writing to the database.

The “read” count variable keeps track of how many processes are currently reading the object.

The “mutex” semaphore is used to ensure mutual exclusion when the variable read count is updated.

The semaphore “rw mutex” functions as a mutual exclusion semaphore for the writers. It is also used by the first or last reader that enters or exits the critical section. It is not used by readers who enter or exit while other readers are in their critical sections.

Question 11

Readers-Writers Problem Variations

Answer 11

First variation – no reader kept waiting unless writer has permission to use shared object (writer starvation)
Second variation – once writer is ready, it performs the write ASAP (reader starvation)
Both may have starvation leading to even more variations
Problem is solved on some systems by kernel providing reader-writer locks

Question 12

Dining-Philosophers Problem
(a simple representation of the need to allocate several resources among several processes in a deadlock-free and starvation-free manner)

Answer 12

Deadlock handling
Allow at most 4 philosophers to be sitting simultaneously at the table.
Allow a philosopher to pick up the forks only if both are available (picking must be done in a critical section.
Use an asymmetric solution – an odd-numbered philosopher picks up first the left chopstick and then the right chopstick. Even-numbered philosopher picks up first the right chopstick and then the left chopstick.

**Note that deadlock-free does not guarantee starvation-free

Question 13

Problems with Semaphores

Incorrect use

Answer 13

1. Placing signal(mutex) before wait(mutex) - can violate mutual exclusion
2. Replace signal() with another wait() - deadlock will occur
3. Omitting wait() or signal() or both - can violate either of the above

Question 14

Monitors

Answer 14

A high-level abstraction that provides a convenient and effective mechanism for process synchronization

Abstract data type, internal variables only accessible by code within the procedure

Only one process may be active within the monitor at a time

But not powerful enough to model some synchronization schemes (where a process needs to wait for a condition to become true)

Question 15

Monitor Condition Variables

Answer 15

condition x, y;
Two operations are allowed on a condition variable:
-> x.wait() – a process that invokes the operation is suspended until another process invokes x.signal()
-> x.signal() – resumes one of processes (if any) that invoked x.wait()
–> If no x.wait() on the variable, then it has no effect on the variable

**x.wait() is different than semaphore wait() because x.wait() will ALWAYS block initially, semaphore will only do so if value is <=0

Question 16

Condition Variables Choices

Answer 16

If process P invokes x.signal(), and process Q is suspended in x.wait(), what should happen next?
-> Both Q and P cannot execute in parallel. If Q is resumed, then P must wait

Options include:
Signal and wait – P waits until Q either leaves the monitor or it waits for another condition
Signal and continue – Q waits until P either leaves the monitor or it waits for another condition

**A process waiting and a process signaling may be using the monitor at the same time. So either you allow the signaling to execute and then leave the monitor, or the contrary.

**To better explain the options above, see problem of philosophers. The putdown method may have to issue two signalings one after the other. After the first signal, what should we do?

Question 17

Resuming Processes within a Monitor

Answer 17

If several processes queued on condition x, and x.signal() executed, which should be resumed?

FCFS (first come first served) frequently not adequate (if processes have different priorities)
conditional-wait construct of the form x.wait(c)
-> Where c is priority number
-> Process with lowest number (highest priority) is scheduled next

Question 18

Linux Synchronization (kernel sync)

Answer 18

Linux:
Prior to kernel Version 2.6, disables interrupts to implement short critical sections
Version 2.6 and later, fully preemptive

Linux provides:
Semaphores
atomic integers
spinlocks
reader-writer versions of both

On single-cpu system, spinlocks replaced by enabling and disabling kernel preemption

**Atomic_integers allow to increase/decrease a shared variable value atomically!

Question 19

Pthreads Synchronization

Answer 19

Pthreads API is OS-independent

It provides:
mutex locks
pthread_mutex_t mutex;
pthread_mutex_init(&mutex,NULL);
/* acquire the mutex lock */
	   pthread_mutex_lock(&mutex);
		/* critical section */
	  /* release the mutex lock */
	  pthread_mutex_unlock(&mutex);

Semaphores

Question 20

Transactional Memory

Answer 20

A memory transaction is a sequence of read-write operations to memory that are performed atomically.

**The advantage of using such a mechanism rather than locks is that the transactional memory system—not the developer—is responsible for guaranteeing atomicity.

**Additionally, because no locks are involved, deadlock is not possible.

Question 21

OpenMP

#pragma omp parallel & #pragma omp critical

Answer 21

OpenMP is a set of compiler directives and API that support parallel progamming.

Any code following the compiler directive #pragma omp parallel is identified as a parallel region and is performed by a number of threads equal to the number of processing cores in the system.

OpenMP provides the compiler directive #pragma omp critical, which specifies the code region following the directive as a critical section in which only one thread may be active at a time. No race conditions.

Easier than using mutex locks. But is up to the developer identify when there could be a race condition. Also, deadlocks can still be possible (compiler still uses locks).

Question 22

Functional Programming Languages

Answer 22

The fundamental difference between imperative and functional languages is that functional languages do not maintain state.

That is, once a variable has been defined and assigned a value, its value is immutable—it cannot change.

Because functional languages disallow mutable state, they need not be concerned with issues such as race conditions and deadlocks.

Essentially, most of the problems addressed in this chapter are nonexistent in functional languages.