Definitions

Question 1

synchronization

Answer 1

the coordination of two or more tasks to get the desired results

Question 2

Control synchronization

Answer 2

When, for example, one task depends on the end of another task, the second task can’t start before the first has finished

Question 3

Data access synchronization

Answer 3

When two or more tasks have access to a shared variable and only one of the tasks can access the variable at any given time

Question 4

granularity

Answer 4

the number of tasks, which can be performed independently without intercommunication in your parallel algorithm

Question 5

coarse-grained granularity

Answer 5

(big tasks with low intercommunication), the overhead due to synchronization will be low. However, maybe you won’t benefit all the cores of your system

Question 6

fine-grained granularity

Answer 6

(small tasks with high intercommunication), the overhead due to synchronization will be high and maybe the throughput of your algorithm won’t be good.

Question 7

Semaphore

Answer 7

A semaphore is a mechanism that can be used to control the access to one or more units of a resource. It has a variable that stores the number of resources that can be used and two atomic operations to manage the value of the variable

Question 8

mutex

Answer 8

A mutex (short for mutual exclusion) is a special kind of semaphore that can take only two values (resource is free and resource is busy), and only the process that sets the mutex to busy can release it.

Question 9

Monitor

Answer 9

A monitor is a mechanism to get mutual exclusion over a shared resource. It has a mutex, a condition variable, and two operations to wait for the condition and to signal the condition. Once you signal the condition, only one of the tasks that are waiting for it continues with its execution.

Question 10

Mutual exclusion

Answer 10

A concept closely related to synchronization is critical section. A critical section is a piece of code that can be only executed by a task at any given time because of its access to a shared resource. Mutual exclusion is the mechanism used to guarantee this requirement and can be implemented by different ways.

Question 11

thread safety

Answer 11

A piece of code (or a method or an object) is thread-safe if all the users of shared data are protected by synchronization mechanisms, a nonblocking compare-and-swap (CAS) primitive or data is immutable, so you can use that code in a concurrent application without any problem.

Question 12

atomic operation

Answer 12

a kind of operation that appears to occur instantaneously to the rest of the tasks of the program

Question 13

atomic variable

Answer 13

a kind of variable with atomic operations to set and get its value. You can implement an atomic variable using a synchronization mechanism or in a lock-free manner using CAS, which doesn’t need any synchronization.

Question 14

shared memory

Answer 14

normally it is used when the tasks are running in the same computer. The tasks use the same memory area where they write and read values. To avoid problems, the access to this shared memory has to be in a critical section protected by a synchronization mechanism.

Question 15

message passing

Answer 15

normally is used when the tasks are running in different computers. When a task needs to communicate with another, it sends a message that follows a predefined protocol. This communication can be synchronous if the sender is blocked waiting for a response or asynchronous if the sender continues with their execution after sending the message.

Question 16

data race (also named race condition)

Answer 16

when you have two or more tasks writing a shared variable outside a critical section—that’s to say, without using any synchronization mechanisms. Under these circumstances, the final result of your application may depend on the order of execution of the tasks.

Question 17

deadlock

Answer 17

when there are two or more tasks waiting for a shared resource that must be free from the other, so none of them will get the resources they need and will be blocked indefinitely

Question 18

livelock

Answer 18

occurs when you have two tasks in your systems that are always changing their states due to the actions of the other. Consequently, they are in a loop of state changes and unable to continue.

For example, you have two tasks—Task 1 and Task 2—and both need two resources: Resource 1 and Resource 2. Suppose that Task 1 has a lock on Resource 1, and Task 2 has a lock on Resource 2. As they are unable to gain access to the resource they need, they free their resources and begin the cycle again. This situation can continue indefinitely, so the tasks will never end their execution.