Start Concurrent: A Gentle Introduction to Concurrent Programming

The processor, or central processing unit (CPU), is the “brain” of a computer. It fetches instructions, decodes them, and executes them. It may send data to or from memory or I/O devices. The CPU on virtually all modern computers is a microprocessor, meaning that all the computation is done by an integrated circuit fabricated out of silicon. What are the important features of CPUs? How do we measure their speed and power?

Memory is where all the programs and data on a computer are stored. The memory in a computer is usually not a single piece of hardware. Instead, the storage requirements of a computer are met by many different technologies.

At the top of the pyramid of memory is primary storage, memory that the CPU can access and control directly. On desktop and laptop computers, primary storage usually takes the form of random access memory (RAM). It is called random access memory because it takes the same amount of time to access any part of RAM. Traditional RAM is volatile, meaning that its contents are lost when it’s unpowered. All programs and data must be loaded into RAM to be used by the CPU.

After primary storage comes secondary storage. The realm of secondary storage is dominated by hard drives that store data on spinning magnetic platters though flash technology is beginning to replace them. Optical drives (such as CD, DVD, and Blu-ray) and the now virtually obsolete floppy drives also fall into the category of secondary storage. Secondary storage is slower than primary storage, but it is non-volatile. Some forms of secondary storage such as CD-ROM and DVD-ROM are read only, but most are capable of reading and writing.

Before we can compare these kinds of storage effectively, we need to have a system for measuring how much they store. In modern digital computers, all data is stored as a sequence of 0s and 1s. In memory, the space that can hold either a single 0 or a single 1 is called a bit, which is short for “binary digit.”

A bit is a tiny amount of information. For organizational purposes, we call a sequence of eight bits a byte. The word size of a CPU is two or more bytes, but memory capacity is usually listed in bytes not words.

Both primary and secondary storage capacities have become so large that it is inconvenient to describe them in bytes. Computer scientists have borrowed prefixes from physical scientists to create suitable units.

Common units for measuring memory are bytes, kilobytes, megabytes, gigabytes, and terabytes. Each unit is 1,024 times the size of the previous unit. You may have noticed that 2¹⁰ (1,024) is almost the same as 10³ (1,000). Sometimes it’s not clear which value is meant. Disk drive manufacturers always use powers of 10 when they quote the size of their disks. Thus, a 1 TB hard disk might hold 10¹² (1,000,000,000,000) bytes, not 2⁴⁰ (1,099,511,627,776) bytes. Standards organizations have advocated that the terms kibibyte (KiB), mebibyte (MiB), gibibyte (GiB), and tebibyte (TiB) be used to refer to the units based on powers of 2 while the traditional names be used to refer only to the units based on powers of 10, but the new terms have not yet become popular.

We called memory a pyramid earlier in this section. At the top there’s a small but very fast amount of memory. As we work down the pyramid, the storage capacity grows, but the speed slows down. Of course, the pyramid for every computer is different. Below is a table that shows many kinds of memory moving from the fastest and smallest to the slowest and largest. Effective speed is hard to measure (and is changing as technology progresses), but note that each layer in the pyramid tends to be 10-100 times slower than the previous layer.

I/O devices have much more variety than CPUs or memory. Some I/O devices, such as USB ports, are permanently connected by a printed circuit board to the CPU. Other devices called peripherals are connected to a computer as needed. Their types and features are many and varied, and this book does not go deeply into how to interact with I/O devices.

Common input devices include mice, keyboards, touch pads, microphones, game pads, and drawing tablets. Common output devices include monitors, speakers, and printers. Some devices perform both input and output, such as network cards.

Remember that our view of computer hardware as CPU, memory, and I/O devices is only a model. A PCI Express socket can be considered an I/O device, but the graphics card that fits into the socket can be considered one as well. And the monitor that connects to the graphics card is yet another one. Although the graphics card is an I/O device, it has its own processor and memory, too. It’s pointless to get bogged down in details unless they are relevant to the problem you’re trying to solve. One of the most important skills in computer science is finding the right level of detail and abstraction to view a given problem.

A number system is a way to represent numbers. It’s easy to confuse the numeral that represents the number with the number itself. You might think of the number ten as “10”, a numeral made of two symbols, but the number itself is the concept of ten-ness. You could express that quantity by holding up all your fingers, with the symbol “X”, or by knocking ten times.

Representing ten with “10” is an example of a positional number system, namely base 10. In a positional number system, the position of the digits determines the magnitude they represent. For example, the numeral 3,432 contains the digit 3 twice. The first time, it represents three groups of one thousand. The second time, it represents three groups of ten. In contrast, the Roman numeral system is an example of a number system that is not positional.

The numeral 3,432 and possibly every other normally written number you’ve seen is expressed in base 10 or the decimal system. It’s called base 10 because, as you move from the rightmost digit leftward, the value of each position goes up by a factor of 10. Also, in base 10, ten is the smallest positive integer that requires two digits for representation. Each smaller number has its own digit: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Representing ten requires two existing digits to be combined. Every base has the property that the number it’s named after takes two digits to write, namely “1” and “0.” (An exception is base 1, which does not behave like the other bases and is not a normal positional number system.)

We can extend these ideas to any base, checking our logic against the familiar base 10. Suppose that a numeral consists of n symbols s_n-1, s_n-2, …, s₁, s₀. Furthermore, suppose that this numeral belongs to the base b number system. We can expand the value of this numeral as:

The leftmost symbol in the numeral is the highest order digit and the rightmost symbol is the lowest order digit. For example, in the decimal numeral 492, 4 is the highest order digit and 2 the lowest order digit.

Fractions can be expanded in a similar manner. For example, a fraction with n symbols s₁, s₂, …, s_n-1, s_n in a number system with base b can be expanded to:

As computer scientists, we have a special interest in base 2 because that’s the base used to express numbers inside of computers. Base 2 is also called binary. The only symbols allowed to represent numbers in binary are “0” and “1”, the binary digits or bits.

In the binary numeral 10011, the leftmost 1 is the highest order bit and the rightmost 0 is the lowest order bit. By the rules of positional number systems, the highest order bit represents 1 · 2⁴ = 16.

Another useful number system is base 16, also known as hexadecimal. Hexadecimal is surprising because it requires more than the familiar 10 digits. Numerals in this system are written with 16 hexadecimal digits that include the ten digits 0 through 9 and the six letters A, B, C, D, E, and F. The six letters, starting from A, correspond to the values 10, 11, 12, 13, 14, and 15.

Hexadecimal is used as a compact representation of binary. Although binary numbers can get very long, four binary digits can be represented with only a single hexadecimal digit.

The base 8 number system is also called octal. Like hexadecimal, octal is used as a shorthand for binary. A numeral in octal uses the octal digits 0, 1, 2, 3, 4, 5, 6, and 7. Otherwise the same rules apply. For example, the octal numeral 377 can be expanded to:

You may have noticed that it is not always clear which base a numeral is written in. The digit sequence 337 is a legal numeral in octal, decimal, and hexadecimal, but it represents different numbers in each system. Mathematicians use a subscript to denote the base in which a numeral is written.

Thus, 337₈ = 255₁₀, 377₁₀ = 377₁₀, and 377₁₆ = 887₁₀. Base numbers are always written in base 10. A number without a subscript is assumed to be in base 10. In Java, there’s no way to mark subscripts, so prefixes are used. A prefix of 0 is used for octal, no prefix is used for decimal, and a prefix of 0x is used for hexadecimal. A numeral cannot be marked as binary in Java. The corresponding numerals in Java code would thus be written 0377, 377, and 0x377. Be careful not to pad numbers with zeroes in Java since they might be interpreted as base 8! Remember that the value 056 is not the same as the value 56 in Java.

The following table lists a few characteristics of the four number systems we have discussed with representations of the numbers 7 and 29.

It’s useful to know how to convert a number represented in one base to the equivalent representation in another base. Our examples have shown how to convert a numeral in any base to decimal by expanding the numeral in the sum-of-product form and then adding the different terms together. But how do you convert a decimal numeral to another base?

There are at least two different ways to convert a decimal numeral to binary. One way is to write the decimal number as a sum of powers of two as in the following conversion of the number 23.

First, find the largest power of two that’s less than or equal to the number. In this case, 16 fits the bill because 32 is too large. Subtract that value from the number, leaving 7 in this case. Then repeat the process. The last step is to collect the coefficients of the powers of two into a sequence to get the binary equivalent. We used 16, 4, 2, and 1 but skipped 8. If we write a 1 for every place we used and a 0 for every place we skipped, we get 23 = 10111₂. While this is a straightforward procedure for decimal to binary conversion, it can be cumbersome for larger numbers.

An alternate way to convert a decimal numeral to an equivalent binary numeral is to divide the given number by 2 until the quotient is 0 (keeping only the integer part of the quotient). At each step, record the remainder found when dividing by 2. Collect these remainders (which will always be either 0 or 1) to form the binary equivalent. The least significant bit is the remainder obtained after the first division, and the most significant bit is the remainder obtained after the last division. In other words, this approach finds the digits of the binary number in backward order.

A decimal number can be converted to its hexadecimal equivalent using either of the two procedures described above. Instead of writing a decimal number as a sum of powers of 2, one writes it as a sum of powers of 16. Similarly, when using the division method, instead of dividing by 2, one divides by 16. Octal conversion is similar.

We use hexadecimal because it’s straightforward to convert from it to binary or back. The following table lists binary equivalents for the 16 hexadecimal digits.

With the help of the table above, let’s convert 3FA₁₆ to binary. By simple substitution, 3FA₁₆ = 0011 1111 1010₂. Note that we’ve grouped the binary digits into clusters of 4 bits each. Of course, the leftmost zeroes in the binary equivalent are useless as they do not contribute to the value of the number.

In mathematics, binary numerals can represent arbitrarily big numbers. Inside of a computer, the size of a number is constrained by the number of bits used to represent it. For general purpose computation, 32- and 64-bit integers are commonly used. The largest integer that Java represents with 32 bits is 2,147,483,647, which is good enough for most tasks. For larger numbers, Java can represent up to 9,223,372,036,854,775,807 with 64 bits. Java also provides representations for integers using 8 and 16 bits.

These representations are easy to determine for positive numbers: Find the binary equivalent of the number and then pad the left side with zeroes to fill the remaining space. For example, 19 = 10011₂. If stored using 8 bits, 19 would be represented as 0001 0011. If stored using 16 bits, 19 would be represented as 0000 0000 0001 0011. (We separate groups of 4 bits for easier reading.)

Recall that computers deal with numbers in their binary representation, meaning that all arithmetic is done on binary numbers. Sometimes it’s useful to understand how this process works and compare it to decimal arithmetic. The table below lists rules for binary addition.

As indicated above, the addition of two 1s leads to a 0 with a carry of 1 into the next position to the left. Addition for numbers composed of more than one bit use the same rules as any addition, carrying values that are too large into the next position. In decimal addition, values over 9 must to be carried. In binary addition, values over 1 must be carried. The next example shows a sample binary addition. To simplify its presentation, we assume that the integers are represented with only 8 bits.

Subtraction in binary is also similar to subtraction in decimal. The rules are given in the following table.

When subtracting a 1 from a 0, a 1 is borrowed from the next left position. The next example illustrates binary subtraction.

Negative integers are also represented in computer memory as binary numbers, using a system called two’s complement. When looking at the binary representation of a signed integer in a computer, the leftmost (most significant) bit will be 1 if the number’s negative and 0 if it’s positive. Unfortunately, there’s more to finding the representation of a negative number than flipping this bit.

Suppose that we need to find the binary equivalent of the decimal number -12 using 8 bits in two’s complement form. The first step is to convert 12 to its 8-bit binary equivalent. Doing so we get 12 = 0000 1100. Note that the leftmost bit of the representation is a 0, indicating that the number is positive. Next, we take the two’s complement of the 8-bit representation in two steps. In the first step, we flip every bit, i.e., change every 0 to 1 and every 1 to 0. This gives us the one’s complement of the number, 1111 0011. In the second step, we add 1 to the one’s complement to get the two’s complement. The result is 1111 0011 + 1 = 1111 0100.

Thus, the 8-bit, two’s complement binary equivalent of -12 is 1111 0100. Note that the leftmost bit is a 1, indicating that this is a negative number.

Why do computers use two’s complement? First of all, they need a system that can represent both positive and negative numbers. They could have used the leftmost bit as a sign bit and represented the rest of the number as a positive binary number. Doing so would require a check on the bit and some conversion for negative numbers every time a computer wanted to perform an addition or subtraction.

Because of the way it’s designed, positive and negative integers stored in two’s complement can be added or subtracted without any special conversions. The leftmost bit is added or subtracted just like any other bit, and values that carry past the leftmost bit are ignored. Two’s complement has an advantage over one’s complement in that there is only one representation for zero. The next example shows two’s complement in action.

When performing arithmetic on numbers, an overflow is said to occur when the result of the operation is larger than the largest value that can be stored in that representation. An underflow is said to occur when the result of the operation is smaller than the smallest possible value.

Both overflows and underflows lead to wrapped-around values. For example, adding two positive numbers together can result in a negative number or adding two negative numbers together can result in a positive number.

The smallest (most negative) number that can be represented in 8-bit two’s complement is -128. A result smaller than this will result in underflow. For example, -115 - 31 = 110. Try out the conversions needed to test this result.

Although we most commonly manipulate numbers using traditional mathematical operations such as addition, subtraction, multiplication, and division, there are also operations that work directly on the binary representations of the numbers. Some of these operators have clear relationships to mathematical operations, and some don’t.

Bitwise AND, bitwise OR, and bitwise XOR take two integer representations and combine them to make a new representation. In bitwise AND, each bit in the result will be a 1 if both of the original integer representations in that position are 1 and 0 otherwise. In bitwise OR, each bit in the result will be a 1 if either of the original integer representations in that position are 1 and 0 otherwise. In bitwise XOR, each bit in the result will be a 1 if the two bits of the original integer representations in that position are different and 0 otherwise.

Bitwise complement is a unary operator like the negation operator (-). Instead of merely changing the sign of a value (which it will also do), its result changes every 1 in the original representation to 0 and every 0 to 1.

The signed left shift, signed right shift, and unsigned right shift operators all create a new binary representation by shifting the bits in the original representation a certain number of places to the left or the right. The signed left shift moves the bits to the left, padding with 0s. If you do a signed left shift by n positions, it’s equivalent to multiplying the number by 2ⁿ (until overflow occurs). The signed right shift moves the bits to the right, padding with whatever the sign bit is. If you do a signed right shift by n positions, it’s equivalent to dividing the number by 2ⁿ (with integer division). The unsigned right shift moves the bits to the right, including the sign bit, filling the left side with 0s. An unsigned right shift will always make a value positive but is otherwise similar to a signed right shift. A few examples follow.

We’ve seen how to represent positive and negative integers in computer memory, but this section shows how rational numbers, such as 12.33, -149.89, and 3.14159, can be converted into binary and represented.

Scientific notation is closely related to the way a computer represents a rational number in memory. Scientific notation is a tool for representing very large or very small numbers without writing a lot of zeroes. A decimal number in scientific notation is written a × 10^b where a is called the mantissa and b is called the exponent.

For example, the number 3.14159 can be written in scientific notation as 0.314159 × 10¹. In this case, 0.314159 is the mantissa, and 1 is the exponent. Here a few more examples of writing numbers in scientific notation.

There are many ways of writing any given number in scientific notation. A more standardized way of writing real numbers is normalized scientific notation. In this notation, the mantissa is always written as a number whose absolute value is less than 10 but greater than or equal to 1. Following are a few examples of decimal numbers in normalized scientific notation.

A shorthand for scientific notation is E notation, which is written with the mantissa followed by the letter ‘E’ followed by the exponent. For example, 39.2 in E notation can be written 3.92E1 or 0.392E2. The letter ‘E’ should be read “multiplied by 10 to the power.” It’s legal to use E notation to represent numbers in scientific notation in Java.

A rational number can be broken into an integer part and a fractional part. In the number 3.14, 3 is the integer part, and .14 is the fractional part. We’ve already seen how to convert the integer part to binary. Now, we’ll see how to convert the fractional part into binary. We can then combine the binary equivalents of the integer and fractional parts to find the binary equivalent of a decimal real number.

A decimal fraction f is converted to its binary equivalent by successively multiplying it by 2. At the end of each multiplication step, either a 0 or a 1 is obtained as an integer part and is recorded separately. The remaining fraction is again multiplied by 2 and the resulting integer part recorded. This process continues until the fraction reduces to zero or enough binary digits for the desired precision have been found. The binary equivalent of f then consists of the bits in the order they have been recorded, as shown in the next example.

In some cases the process described above will never have a remainder of 0. Then, we can only find an approximate representation of the given fraction as demonstrated in the next example.

Now that we understand how integers as well as fractions can be converted from one number base to another, we can convert any rational number from one base to another. The next example demonstrates one such conversion.

Floating-point representation is a system used to represent rational numbers in computer memory. In this notation a number is represented as a × b^e, where a gives the significant digits (mantissa) of the number and e is the exponent. The system is very similar to scientific notation, but computers usually use base b = 2 instead of 10.

For example, we could write the binary number 1010.1₂ in floating-point representation as 10.101₂ × 2² or as 101.01₂ × 2¹. In any case, this number is equivalent to 10.5 in decimal.

In standardized floating-point representation, a is written so that only the most significant non-zero digit is to the left of the decimal point. Most computers use the IEEE 754 floating-point representation to represent rational numbers. In this notation, the memory to store the number is divided into three segments: one bit used to mark the sign of the number, m bits to represent the mantissa (also known as the significand), and e bits to represent the exponent.

In IEEE floating-point representation, numbers are commonly represented using 32 bits (known as single precision) or using 64 bits (known as double precision). In single precision, m = 23 and e = 8. In double precision, m = 52 and e = 11. To represent positive and negative exponents, the exponent has a bias added to it so that the result is never negative. This bias is 127 for single precision and 1,023 for double precision. The packing of the sign bit, the exponent, and the mantissa is shown in Figure 1.4 (a) and (b).

Fixing the number of bits used for representing a real number limits the numbers that can be represented in computer memory using the floating-point notation. The largest rational number that can be represented in single precision has an exponent of 127 (254 after bias) with a mantissa consisting of all 1s:
0 1111 1110 1111 1111 1111 1111 1111 111
This number is approximately 3.402 × 10³⁸. To represent the smallest (closest to zero) non-zero number, we need to examine one more complication in the IEEE format. An exponent of 0 implies that the number is unnormalized. In this case, we no longer assume that there is a 1 bit to the left of the mantissa. Thus, the smallest non-zero single precision number has its exponent set to 0 and its mantissa set to all zeros with a 1 in its 23^rd bit:
0 0000 0000 0000 0000 0000 0000 0000 001
Unnormalized single precision values are considered to have an exponent of -126. Thus, the value of this number is 2^-23 × 2^-126 = 2^-149 ≈ 1.4 × 10^-45. Now that we know the rules for storing both integers and floating-point numbers, we can list the largest and smallest values possible in 32- and 64-bit representations in Java in the following table. Note that largest means the largest positive number for both integers and floating-point values, but smallest means the most negative number for integers and the smallest positive non-zero value for floating-point values.

Using the same number of bits, floating-point representation can store much larger numbers than integer representation. However, floating-point numbers are not always exact, resulting in approximate results when performing arithmetic. Always use integer formats when fractional parts aren’t needed.

Several binary representations in the floating-point representation correspond to special numbers. These numbers are reserved and do not have the values that would be expected from normal multiplication of the mantissa by the power of 2 given by the exponent.

As we have seen, many rational numbers can only be approximately represented in computer memory. Thus, arithmetic done on the approximate values yields approximate answers. For example, 1.3 cannot be represented exactly using a 64-bit value. In this case, the product 1.3 * 3.0 will be 3.9000000000000004 instead of 3.9. This error will propagate as additional operations are performed on previous results. The next example illustrates this propagation of errors when a sequence of floating-point operations are performed.

While the above example may seem unrealistic, it does expose the inherent dangers of floating-point calculations. Although the error is less when using double precision representations, it still exists.

Multicore systems have impressive performance. The first multicore processors had two cores, but current designs have four, six, eight, or higher. A processor with eight cores can execute eight different programs at the same time. Or, when faced with a computationally intense problem like matrix math, code breaking, or scientific simulation, a processor with eight cores could solve the problem eight times as fast. A desktop processor with 100 cores that can solve a problem 100 times faster is not out of reach.

In fact, modern graphics cards are already blazing this trail. Consider the 1080p standard for high definition video, which has a resolution of 1,920 × 1,080 pixels. Each pixel (short for picture element) is a dot on the screen. A screen whose resolution is 1080p has 2,073,600 dots. To maintain the illusion of smooth movement, these dots should be updated around 30 times per second. Computing the color for more than 2 million dots based on 3D geometry, lighting, and physics effects 30 times a second is no easy feat. Some of the cards used to render computer games have hundreds or thousands of cores. These cores are not general purpose or completely independent. Instead, they’re specialized to do certain kinds of matrix transformations and floating-point computations.

Although chip-makers have spent a lot of money marketing multicore technology, they haven’t spent much money explaining that one of the driving forces behind the “multicore revolution” is a simple failure to make processors faster in other ways. In 1965, Gordon Moore, one of the founders of Intel, remarked that the density of silicon microprocessors had been doubling every year (though he later revised this to every two years), meaning that twice as many transistors (computational building blocks) could fit in the same physical space. This trend, often called Moore’s Law, has held up reasonably well. For years, clever designs relying on shorter communication times, pipelining, and other schemes succeeded in doubling the effective performance of processors every two years.

At some point, the tricks became less effective and exponential gains in processor clock rate could no longer be sustained. As clock frequency increases, the signal becomes more chaotic, and it becomes more difficult to tell the difference between the voltages that represent 0s and 1s. Another problem is heat. The energy that a processor uses is related to the square of the clock rate. This relationship means that increasing the clock rate of a processor by a factor of 4 will increase its energy consumption (and heat generation) by a factor of 16.

The legacy of Moore’s Law lives on. We’re still able to fit more and more transistors into tinier and tinier spaces. After decades of increasing clock rate, chip-makers began using the additional silicon density to make processors with more than one core instead. Since 2005 or so, increases in clock rate have stagnated.

Does a processor with eight cores solve problems eight times as fast as its single core equivalent? Unfortunately, the answer is, “Almost never.” Most problems are not easy to break into eight independent pieces.

For example, if you want to build eight houses and you have eight construction teams, then you probably can get pretty close to completing all eight houses in the time it would have taken for one team to build a single house. But what if you have eight teams and only one house to build? You might be able to finish the house a little early, but some steps necessarily come after others: The concrete foundation must be poured and solid before framing can begin. Framing must be finished before the roof can be put on. And so on.

Like building a house, most problems you can solve on a computer are difficult to break into concurrent tasks. A few problems are like painting a house and can be completed much faster with lots of concurrent workers. Other tasks simply cannot be done faster with more than one team on the job. Worse, some jobs can actually interfere with each other. If a team is trying to frame the walls while another team is trying to put the roof onto unfinished walls, neither will succeed, the house might be ruined, and people could get hurt.

On a desktop computer, individual cores generally have their own level 1 cache but share level 2 cache and RAM. If the programmer isn’t careful, he or she can give instructions to the cores that will make them fight with each other, overwriting memory that other cores are using and crashing the program or giving an incorrect answer. Imagine if different parts of your brain were completely independent and fought with one another. The words that came out of your mouth might be gibberish.

To recap, the first problem with concurrent programming is finding ways to break down problems so that they can be solved faster with multiple cores. The second problem is making sure that the different cores cooperate so that the answer is correct and makes sense. These are not easy problems, and many researchers are still working on finding better ways to do both.

Some educators believe that beginners will be confused by concurrency and should wait until later courses to confront these problems. We disagree: Forewarned is forearmed. Concurrency is an integral part of modern computation, and the earlier you get introduced to it, the more familiar it’ll be.