Process Synchronization

Question 1

What is the initial value of the counter in the motivating scenario?

Answer 1

5

Question 2

What are the possible outcomes for the value of the counter after concurrent execution?

Answer 2

4, 5, or 6

Question 3

Define race conditions.

Answer 3

A situation where several processes access and manipulate the same data (critical section) and the outcome depends on the order of access.

Question 4

How can race conditions be prevented?

Answer 4

By synchronization, ensuring only one process manipulates the critical data at a time.

Question 5

What is the critical section problem?

Answer 5

To design a protocol that ensures when one process is in its critical section, no other may be in its critical section.

Question 6

What are the three main conditions to solve the critical section problem?

Answer 6

• Mutual Exclusion
• Progress
• Bounded Waiting

Question 7

What does mutual exclusion ensure?

Answer 7

If process P_i is executing in its critical section, no other processes can be executing in their critical sections.

Question 8

What does progress mean in the context of the critical section problem?

Answer 8

If no process is executing in its critical section and some processes wish to enter, the selection of the next process cannot be postponed indefinitely.

Question 9

What is bounded waiting?

Answer 9

A bound must exist on the number of times other processes can enter their critical sections after a request is made.

Question 10

What does Dekker’s algorithm use to indicate if a process is ready to enter the critical section?

Answer 10

The turn variable.

Question 11

What is the purpose of the flag array in Peterson’s solution?

Answer 11

To indicate if a process is ready to enter the critical section.

Question 12

What does the test_and_set instruction do?

Answer 12

Writes to a memory location and returns its old value.

Question 13

What is an atomic operation?

Answer 13

An operation that is performed without the possibility of interruption.

Question 14

What is the role of hardware support in synchronization?

Answer 14

To implement critical section code efficiently using atomic hardware instructions.

Question 15

True or False: The usage of interrupts is suitable for multicore systems.

Answer 15

False

Question 16

What is the function of the compare_and_swap instruction?

Answer 16

It sets a variable to a new value only if it equals an expected value, executed atomically.

Question 17

How does the compare_and_swap instruction guarantee mutual exclusion?

Answer 17

It ensures that only one process can change the value of a shared variable at a time.

Question 18

Fill in the blank: The critical section must be executed by _______.

Answer 18

only one process at a time

Question 19

What does the term ‘critical section’ refer to?

Answer 19

A segment of code where a process accesses shared resources.

Question 20

What happens if multiple processes enter their critical sections simultaneously?

Answer 20

It can lead to data inconsistency.

Question 21

What is the significance of disabling interrupts in uniprocessor systems?

Answer 21

It allows currently running code to execute without preemption.

Question 22

What is the main drawback of disabling interrupts in multiprocessor systems?

Answer 22

It is generally too inefficient.

Question 23

What is the expected behavior of a process that has made a request to enter its critical section?

Answer 23

It should not be indefinitely postponed from entering.

Question 24

How does hardware support improve synchronization mechanisms?

Answer 24

By providing atomic operations that prevent race conditions.

Question 25

What is the main goal of mutual exclusion?

Answer 25

To prevent multiple processes from entering a critical section simultaneously.

Question 26

Is bounded waiting guaranteed in the discussed mutual exclusion solution?

Answer 26

No, bounded waiting is not guaranteed.

Question 27

What are the advantages of the mutual exclusion solution?

Answer 27

* Applicable to any number of processes * Simple and easy to verify * Can support multiple critical sections

Question 28

What does the 'test_and_set' operation do in mutual exclusion?

Answer 28

It tests a variable and sets it to true atomically, ensuring only one process can acquire the lock.

Question 29

What is a mutex lock?

Answer 29

A synchronization tool that protects a critical section by requiring processes to acquire and release a lock.

Question 30

What is a spinlock?

Answer 30

A type of mutex lock that uses busy waiting to acquire the lock.

Question 31

Define the semaphore.

Answer 31

A synchronization tool that provides more sophisticated ways for processes to synchronize their activities.

Question 32

What are the two atomic operations associated with semaphores?

Answer 32

* wait() * signal()

Question 33

What is a binary semaphore?

Answer 33

A semaphore that can only take values 0 or 1, often used to implement mutual exclusion.

Question 34

What is the difference between a counting semaphore and a binary semaphore?

Answer 34

A counting semaphore can have a value in an unrestricted domain, while a binary semaphore is limited to 0 or 1.

Question 35

What is deadlock?

Answer 35

A situation where two or more processes are waiting indefinitely for an event that can only be caused by one of the waiting processes.

Question 36

What is starvation in the context of process synchronization?

Answer 36

Indefinite blocking where a process may never be removed from the semaphore queue.

Question 37

What is priority inversion?

Answer 37

A scheduling problem where a lower-priority process holds a lock needed by a higher-priority process.

Question 38

List the classical problems of synchronization.

Answer 38

* Bounded-Buffer Problem * Readers and Writers Problem * Dining-Philosophers Problem

Question 39

What is the Bounded-Buffer Problem?

Answer 39

A problem involving N buffers, each capable of holding one item, where the producer and consumer must synchronize access.

Question 40

What are the roles of the producer and consumer in the Bounded-Buffer Problem?

Answer 40

* Producer: produces items and adds them to the buffer * Consumer: removes items from the buffer and consumes them

Question 41

In the Readers-Writers Problem, what is a reader?

Answer 41

A process that only reads shared data and does not modify it.

Question 42

In the Readers-Writers Problem, what is a writer?

Answer 42

A process that can both read and write shared data.

Question 43

What is the main problem in the Readers-Writers Problem?

Answer 43

To allow multiple readers to read concurrently while ensuring exclusive access for writers.

Question 44

What is the Dining-Philosophers Problem?

Answer 44

A classical synchronization problem that illustrates the difficulty of allocating resources among processes without deadlock and starvation.

Question 45

How many forks are available in the Dining-Philosophers Problem?

Answer 45

Five forks.

Question 46

What is a potential solution to avoid deadlock in the Dining-Philosophers Problem?

Answer 46

Allow a philosopher to pick up their chopsticks only if both are available.

Question 47

What is the role of semaphores in the Dining-Philosophers Problem?

Answer 47

One semaphore per fork to manage access to the forks.

Question 48

What happens if each philosopher starts by picking their left fork?

Answer 48

It can lead to deadlock.

Question 49

What is the purpose of the wait() operation in synchronization?

Answer 49

To decrement the semaphore value and potentially block the process if the value is less than or equal to zero.

Question 50

What does the signal() operation do in synchronization?

Answer 50

It increments the semaphore value and may wake up a blocked process.

Question 51

What is a semaphore value of -ve indicative of?

Answer 51

The number of processes waiting to acquire that semaphore.

Question 52

What is the solution to starvation in semaphore queues?

Answer 52

Implementing a priority-inheritance protocol or ensuring fair access to resources.

Question 53

What is the condition for a philosopher to pick up chopsticks?

Answer 53

Both chopsticks must be available

Question 54

How does an odd philosopher pick up chopsticks?

Answer 54

First the left chopstick, then the right chopstick

Question 55

How does an even philosopher pick up chopsticks?

Answer 55

First the right chopstick, then the left chopstick

Question 56

What is a proposed solution to the dining philosophers problem?

Answer 56

Allow at most four philosophers to be sitting simultaneously at the table

Question 57

Define monitors in concurrent programming.

Answer 57

High-level language constructs providing functionality equivalent to semaphores but easier to control

Question 58

List the programming languages where monitors can be found.

Answer 58

* Concurrent Pascal * Java

Question 59

What does a monitor contain?

Answer 59

* One or more procedures * An initialization sequence * Local data variables

Question 60

What ensures mutual exclusion in a monitor?

Answer 60

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

Question 61

What locks shared data in a monitor?

Answer 61

The monitor locks the shared data on process entry

Question 62

What must be declared to allow a process to wait within a monitor?

Answer 62

A condition variable

Question 63

What happens to a process when it invokes x.wait()?

Answer 63

The process is suspended until another process invokes x.signal()

Question 64

What is the effect of the x.signal operation?

Answer 64

It resumes exactly one suspended process that invoked x.wait()

Question 65

What is the solution function to the dining philosophers problem?

Answer 65

DP.pickup(i)

Question 66

What synchronization method was used in Linux prior to kernel version 2.6?

Answer 66

Disables interrupts to implement short critical sections

Question 67

What does Linux version 2.6 and later provide for synchronization?

Answer 67

* Semaphores * Atomic integers * Spinlocks

Question 68

What is the pthreads API?

Answer 68

An OS-independent API that provides synchronization tools

Question 69

List the synchronization tools provided by pthreads.

Answer 69

* Mutex locks * Condition variables

Question 70

What is the syntax to create and initialize a mutex in pthreads?

Answer 70

#include pthread_mutex_t mutex; pthread_mutex_init(&mutex, NULL);

Question 71

What is the function to acquire a mutex lock in pthreads?

Answer 71

pthread_mutex_lock(&mutex)

Question 72

What is the function to release a mutex lock in pthreads?

Answer 72

pthread_mutex_unlock(&mutex)

Question 73

What is the syntax to create and initialize a semaphore?

Answer 73

#include sem_t sem; sem_init(&sem, is_shared(0/1), 1);

Question 74

What is the function to acquire a semaphore?

Answer 74

sem_wait(&sem)

Question 75

What is the function to release a semaphore?

Answer 75

sem_post(&sem)