Synchronization, concurrency and multitasking: why is it difficult?

Essentially, multi-processor systems are difficult to program because:

A highly concurrent application needs to make sure that each process is "in the right place at the right time" to take advantage of what resources are available at any given moment.

A typical situation is illustrated in Figure 1. The architectural details have been heavily simplified in this diagram, but it shows four processes "running" on a machine with two CPUs. Since there are only two CPUs, only two processes can actually be running simultaneously at any one time; the operating system must periodically allocate CPU time to different processes– or "swap them in and out" of the CPUs– so that over time all four make progress.

Additionally– and usually more significantly– each running process, via the CPU, may access main memory, shared between the two CPUs, and other shared peripherals such as hard disks. These "external" resources are much slower to access than registers and cached instructions "internal" to the CPU. Additionally, only one value can physically be written to a memory address at once, and only one part of a hard disk can physically be accessed at once. These factors pose two main problems:

The ideal solution to the first problem is that while one process is waiting on a slow resource, it is "swapped out" of the CPU and another process that requires the CPU runs in the meantime. Moving towards this ideal generally falls under the heading of concurrency. In the second case, what physically happens (e.g. which processor "gets in there first" when the two CPUs simultaneously want to write different values to a memory location) is determined by the hardware and can be unpredictable. So when data is being shared in this way, we need to take special steps in software to manage simultaneous access and give predictable results. This second issue is generally the realm of synchronization.

Concurrency on a single-processor machine

Concurrency is still often an issue on a single-processor machine because processes are usually swapped in and out of the available processor under interrupt. One process cannot necessarily predict when another one is going to "step in" and potentially change some data that it was in the middle of accessing. And the issue of not "wasting" the CPU still remains: if process 1 is waiting for data from the hard disk, and thus cannot usefully use the CPU, it would be useful to let process 2 use the CPU in the meantime.


On the next page, we continue our discussion by looking at issues relating to processor architecture which affect concurrent programming.