Order of execution problems

The critical section problem is an abstraction of synchronization problems that occur when several processes compete for the same resource. Synchronization problems are also common when processes must coordinate the order of execution of operations of different processes. For example, consider the problem of the concurrent execution of one step of the mergesort algorithm, where an array is divided into two halves, the two halves are sorted concurrently and the results are merged together. Thus, to mergesort the array \([5, 1, 10, 7, 4, 3, 12, 8]\), we divide it into two halves \([5, 1, 10, 7]\) and \([4, 3, 12, 8]\), sort them obtaining \([1, 5, 7, 10]\) and \([3, 4, 8, 12]\), respectively, and then merge the two sorted arrays to obtain \([1, 3, 4, 5, 7, 8, 10, 12]\).

To perform this algorithm concurrently, we will use three processes, two for sorting and one for merging. Clearly, the two sort processes work on totally independent data and need no synchronization, while the merge process must not execute its statements until the two other have completed. Here is a solution using two binary semaphores:

The integer components of the semaphores are initialized to zero, so process merge is initially blocked on $1. Suppose that process sort1 completes before process sort2; then sort1 signals $1 enabling merge to proceed, but it is then blocked on semaphore $2. Only when sort2 completes will merge be unblocked and begin executing its algorithm. If sort2 completes before sort1, it will execute signal(S2), but merge will still be blocked on S1 until sort1 completes.