by Johannes Frey, Hannes Buchwald, Stephan Soller, Walter Kriha, Benjamin Binder<\/p>\n
While trying to understand Hoares famous paper Communicating sequential processes<\/a> we stumbled upon some interesting problems and concepts referring to parallel programming. In this post we want to share some of the insights we gained by discussing the matter.<\/p>\n <\/p>\n Humans are not really made for multitasking. We are able to do more than one task at the same time, if all the different tasks have the same goal and can be performed without paying much attention to them. An example would be driving a car. But it\u2019s getting harder if the tasks are similar to each other and demand the same amount of attention, like calculating different sums.<\/p>\n Take for example this simple calculation:<\/p>\n (2+6) \u00d7 (7-3)<\/p>\n One person can only focus on calculating one of the two sums at a time. So real parallelism isn’t a natural way of thinking for us humans. Two persons however can each calculate one sum and then multiply their results. Real parallelism only works with more than one person.<\/p>\n If we want to implement this example we could copy the principle of having two people. Each sum is calculated in a different thread. After the threads have finished we can then multiply the results.<\/p>\n In this easy example it\u2019s not a problem to understand what is happening. But in a more complex scenario it\u2019s getting harder to understand who interacts with whom at what time.<\/p>\n As a quick reminder<\/a>: Concurrency revolves around the concept of dealing with several tasks at the same time, while parallelism revolves around actually executing multiple tasks at the same time. A program build in a concurrent way can execute in parallel but doesn’t have to. It will run just fine sequentially on a single CPU core, too.<\/p><\/blockquote>\n In a concurrent program multiple things can happen at the same time. This is easy to visualize as a few boxes connected by arrows:<\/p>\n But when written as text it’s more difficult to understand the flow of events and the dependencies between the different processes:<\/p>\n This stems from the basic structure of text and in extension programming languages: They are structured one line after<\/em> another, one statement after<\/em> the other. Text and programming languages express things as one linear stream of things. This is a restriction of the text medium itself.<\/p>\n Text as a medium is extremely useful in programming. Starting at a young age we’re trained to use language to read and write and even express our thoughts. Programming languages tap into that training and we can express complex thoughts in a compact way.<\/p>\n But to represent the parallel structure of a program, which is basically a graph, text might not be the best choice. Maybe a simple “box and arrows” visualization better serves this purpose. There are already some examples of visual programming like Blueprints in UE4<\/a> or LabVIEW<\/a>. This is something traditional editors and IDEs might want to pick up. Albeit in a more coarse way like one box per thread.<\/p>\n Concepts like futures and event-loops are approaches to cope with the same problem: Mapping a graph into linear text. For some situations they work while for others they don’t. But more on that later.<\/p>\n The two concepts we will take a closer look at are event-loops<\/a> and futures<\/a>. They can be found in programming languages like Clojure<\/a>, or in frameworks like Node.js<\/a>. Even though both concepts share the same ground (concurrent programming), they vastly differ in their approach, their style and the restrictions they enforce.<\/p>\n In essence both approaches allow us to break up the rather atomic chain of definition, execution and immediate result.<\/p>\n Futures allow us to fire up a specific task on another thread, while the main program keeps running. If, at some point in the future<\/em> ;-), we are interested in the actual value, we have to explicitly ask the future reference for its value. As long as the value is “ready” when we ask for it, we are good. Using futures blends perfectly with writing linear programming. Because you don’t have to deal with callbacks, the program stays very clean and readable.<\/p>\n The Event-Loop approach also gives away control but with the help of callbacks. In its center is one single-threaded loop that runs “forever”. This is called the event loop.<\/p>\n If an event is fired that is interesting to someone, a message is pushed into a queue together with a callback associated with the event. Whenever there is computing time left (aka the call stack is empty), messages get pulled from the queue and are processed. The processing of the messages is never interrupted, so there is no pre-emption and you can always be sure your code finished correctly.<\/p>\n In the realms of CPUs, a single-core processor deals with concurrency by interleaving tasks onto the processor with the help of the scheduler. By doing so, the CPU provides each program with the illusion of exclusive processor possession, which makes multitasking possible. A multi-core processor however deals with concurrency by actually executing tasks on multiple cores and thereby yielding “true” parallelism.<\/p>\n So why do we have to wrap our head around this low-level concept?<\/p>\n Because we have to deal with either blocking or non-blocking operations. Ideally we want our two concepts to deal with the problem. However this doesn’t always work and we still have to keep some things in mind.<\/p>\n When dereferencing a result from a future, we possibly run into a problem. As long as the value is “ready” when we ask for it, we are good. But if the value has to be calculated first, the dereference results in blocking the callers execution.<\/p>\n Because programs using an event-loop are highly decoupled, the impact of using blocking function calls doesn’t seem that big from the perspective of the program.<\/p>\nParallelism is difficult<\/h2>\n
Expressing concurrency<\/h2>\n
+-----+\n| GUI |-------+-------------+\n+-----+ \u2193 \u2193\n \u2191 +----------+ +----------+\n | | read | | download |\n | | metadata | | content |\n | +----------+ +----------+\n | \u2193 |\n | +-----------+ |\n +-----| create |\u2190-----+\n | thumbnail |\n +-----------+\n<\/pre>\n
gui_thread:\n on click:\n disk_thread.send read_file, ...\n net_thread.send download_file, ...\n on work_done:\n # show result to user\n\ndisk_thread:\n on read_file:\n # read requested file from disk\n compute_thread.send process_loaded_file. ...\n\nnet_thread:\n on download_file:\n # download requested file from server\n compute_thread.send process_downloaded_file, ...\n\ncompute_thread:\n on process_loaded_file and process_downloaded_file:\n # do time consuming processing of files\n gui_thread.send work_done, ...<\/pre>\n
Helping the programmer with concepts<\/h2>\n
Futures<\/h3>\n
Event-Loops<\/h3>\n
Blocking and non-blocking calls<\/h2>\n
Futures and blocking function calls<\/h3>\n
Event-loops and blocking function calls<\/h3>\n