Distributed Programming for the Cloud - Large Scale and Big Data: Processing and Management - page 8

tasks. Semaphores use two operations, post and wait. The post operation acts like
depositing a token, signaling that data has been produced. The wait operation blocks
until signaled by the post operation that it can proceed with consuming data. Locks
protect critical sections or regions that at most one task can access (typically write)
at a time. Locks involve two operations, lock and unlock for acquiring and releas-
ing a lock associated with a critical section, respectively. A lock can be held by only
one task at a time, and other tasks cannot acquire it until released. Lastly, a bar-
rier defines a point at which a task is not allowed to proceed until every other task
reaches that point. The efficiency of semaphores, locks, and barriers is a critical and
challenging goal in developing distributed/parallel programs for the shared-memory
programming model (details on the challenges that pertain to synchronization are
provided in Section 1.5.4).
Figure 1.5 shows an example that transforms a simple sequential program into a
distributed program using the shared-memory programming model. The sequential
program adds up the elements of two arrays b and c and stores the resultant elements
in array a . Afterward, if any element in a is found to be greater than 0, it is added to a
grand sum. The corresponding distributed version assumes only two tasks and splits
the work evenly across them. For every task, start and end variables are specified
to correctly index the (shared) arrays, obtain data, and apply the given algorithm.
Clearly, the grand sum is a critical section; hence, a lock is used to protect it. In addi-
tion, no task can print the grand sum before every other task has finished its part,
thus a barrier is utilized prior to the printing statement. As shown in the program,
the communication between the two tasks is implicit (via reads and writes to shared
(a)
(b)
FIGURE 1.5 (a) A sequential program that sums up elements of two arrays and computes a
grand sum on results that are greater than zero. (b) A distributed version of the program in (a)
coded using the shared-memory programming model.