CPS323 Lecture: ConcurrencyMaterials:1. Coroutine Projectables2. Handout for Ada Concurrency + Executable form (simple_tasking.adb, producer_and_consumer.adb)I. Introduction- ------------ A. Most of our attention throughout the CS curricum has been focussed on _sequential_ programming, in which a program does exactly one thing at a time, following a predictable order of steps. In particular, we expect a given program will always follow the exact same sequence of steps when run on a given set of data. B. An alternative is to think in terms of _concurrent_ programming, in which a "program" (at least in principle) does multiple things at the same time, following an order of steps that is not predictable and may differ between runs even if the same program is run on exactly the same data. C. Concurrency has long been an interest in CS, but has become of particular interest as we move into a situation in which raw hardware speeds have basically plateaued and multicore processors are coming to dominate the hardware scene. There are at least three reasons why this topic is of great interest. 1. Achieving maximum performance using technologies such as multicore ! processors. 2. Systems that inherently require multiple processors working together cooperatively on a single task - e.g. distributed or embedded systems. 3. Some problems are more naturally addressed by thinking in terms of ! multiple concurrrent components, rather than a single monolithic ! program. D. There are two broad approaches that might be taken to concurrency: 1. Make use of system libraries, without directly supporting parallelism in the language. (The approach taken by most languages - e.g. the use of the pthreads or PVM or MPI with a language like C++). 2. Incorporate facilities for specifying parallel computation in the language itself (e.g Java, C#, Ada). E. This leads us to ask what features are or might be present in a ! programming language to support concurrency? Of course, there are a ! multitude of possible answers to this question. ! ! 1. We have already looked at once sort of answer: multi-threading as ! found in languages like Java.! ! With concurrent threads, in principle more than one computation may be ! happening at the same time, but in practice this might not actually be ! the case. Even so, since switches between threads can occur at any ! time, careful attention must be paid to synchronizing threads so they ! don't interfere with one another. ! ! 2. We will look at two more representative models today. One is a fairly ! old idea; the other a facility found in Ada and other languages used ! for embedded systems. ! II. Coroutines-- ---------- A. Ordinarily, when we think of segmenting a program into procedures, we think HIERARCHICALLY. _____ 1. Example: If A calls B, we have | A | |___| | __|__ | B | |___| a. A's execution pauses to let B begin. b. B's local data is created from scratch. c. B runs to completion. d. B's local data is destroyed. e. A resumes where it left off. 2. If A calls B again, the whole process is repeated. a. The first execution of B has no effect on the second (except possibly through global data). b. B always starts execution from the very beginning, and runs through to the end. There is no way for B to "pause in mid-stream" and return control to A, picking up later where it left off. B. This hierarchical pattern is just what we want for most applications. However, there are some problems for which it doesn't work well, because it is just not possible to establish a clear-cut hierarchy. A good example of this sort of problem is the classic problem of the producer and the consumer. 1. In one version of this problem, a data copying program is to be written that reads data from punched cards and writes it to a disk file, subject to the following formatting requirements. (Of course, the use of punched cards for input is from the early days of computing; but the problem issues remain valid and this example has become traditional.) a. Each punched card contains exactly 80 characters. b. A CR/LF sequence is to be appended to the data from each card before writing it to the disk.c. Data is to be written to disk in blocks of 512 characters. The last block may need to be padded with null characters if it is not completely filled by data from the cards. 2. We can formulate this problem in terms of two subtasks, called the producer and the consumer, where the consumer "produces" characters by reading them from cards or manufacturing them, and the consumer "consumes" characters by writing them to the disk. a. The producer executes the following algorithm: PROJECT do read a card into card_buffer[80]; for (int = 0; i < 80; i ++) send card_buffer[i] to the consumer; send CR to the consumer; send LF to the consumer while (! out of cards); b. The consumer executes the following algorithm: do for (int j = 0; j< 512; j ++) if there is another character available then accept a character from producer into disk_buffer[j] else disk_buffer[j] = NULL; write disk_buffer[] to disk while (more characters are available) 3. While each of the above is nice and modular, we run into serious problems when we try to put these two algorithms together in a standard hierarchical way. a. We could make producer call consumer each time it produces a character. i. In this case, producer would call consumer from 3 different places