Concurrency: An Introduction

1 26 Concurrency: An IntroductionThus far, we have seen the development of the basic abstractionsthat theOS performs. We have seen how to take a single physical CPU and turnit into multiplevirtual CPUs, thus enabling the illusion of multiple pro-grams running at the same time. We have also seen how to create theillusion of a large, privatevirtual memoryfor each process; this abstrac-tion of theaddress spaceenables each program to behave as if it has itsown memory when indeed the OS is secretly multiplexing addressspacesacross physical memory (and sometimes, disk).In this note, we introduce a new abstraction for a single running pro-cess: that of athread. Instead of our classic view of a single point ofexecution within a program ( , a single PC where instructions are be-ing fetched from and executed), amulti-threadedprogram has more thanone point of execution ( , multiple PCs, each of which is being fetchedand executed from).

2 Perhaps another way to think of this is that eachthread is very much like a separate process, except for one difference:theysharethe same address space and thus can access the same state of a single thread is thus very similar to that of a has a program counter (PC) that tracks where the program is fetch-ing instructions from. Each thread has its own private set of registers ituses for computation; thus, if there are two threads that are running ona single processor, when switching from running one (T1) to running theother (T2), acontext switchmust take place. The context switch betweenthreads is quite similar to the context switch between processes, as theregister state of T1 must be saved and the register state of T2 restoredbefore running T2. With processes, we saved state to aprocess controlblock (PCB); now, we ll need one or morethread control blocks (TCBs)to store the state of each thread of a process.

3 There is one major difference,though, in the context switch we perform between threads as comparedto processes: the address space remains the same ( , thereis no need toswitch which page table we are using).One other major difference between threads and processes concernsthe stack. In our simple model of the address space of a classic process12 CONCURRENCY: ANINTRODUCTION16KB15KB2KB1KB0 KBStack(free)HeapProgram Codethe code segment:where instructions livethe heap segment:contains malloc d datadynamic data structures(it grows positively)(it grows negatively)the stack segment:contains local variablesarguments to routines, return values, (1)Stack (2)(free)(free)HeapProgram CodeFigure :Single-Threaded And Multi-Threaded Address Spaces(which we can now call asingle-threadedprocess), there is a single stack,usually residing at the bottom of the address space (Figure , left).

4 However, in a multi-threaded process, each thread runs independentlyand of course may call into various routines to do whatever work it is do-ing. Instead of a single stack in the address space, there willbe one perthread. Let s say we have a multi-threaded process that has twothreadsin it; the resulting address space looks different (Figure , right).In this figure, you can see two stacks spread throughout the addressspace of the process. Thus, any stack-allocated variables, parameters, re-turn values, and other things that we put on the stack will be placed inwhat is sometimes calledthread-localstorage, , the stack of the rele-vant might also notice how this ruins our beautiful address space lay-out. Before, the stack and heap could grow independently and troubleonly arose when you ran out of room in the address space. Here, weno longer have such a nice situation.

5 Fortunately, this is usually OK, asstacks do not generally have to be very large (the exception being in pro-grams that make heavy use of recursion). Why Use Threads?Before getting into the details of threads and some of the problemsyoumight have in writing multi-threaded programs, let s first answer a moresimple question. Why should you use threads at all?OPERATINGSYSTEMS[ ] : ANINTRODUCTION3As it turns out, there are at least two major reasons you should usethreads. The first is simple:parallelism. Imagine you are writing a pro-gram that performs operations on very large arrays, for example, addingtwo large arrays together, or incrementing the value of each element inthe array by some amount. If you are running on just a single proces-sor, the task is straightforward: just perform each operation andbe , if you are executing the program on a system with multipleprocessors, you have the potential of speeding up this process consider-ably by using the processors to each perform a portion of the work.

6 Thetask of transforming your standardsingle-threadedprogram into a pro-gram that does this sort of work on multiple CPUs is calledparalleliza-tion, and using a thread per CPU to do this work is a natural and typicalway to make programs run faster on modern second reason is a bit more subtle: to avoid blocking programprogress due to slow I/O. Imagine that you are writing a program thatperforms different types of I/O: either waiting to send or receive a mes-sage, for an explicit disk I/O to complete, or even (implicitly)for a pagefault to finish. Instead of waiting, your program may wish to do some-thing else, including utilizing the CPU to perform computation, or evenissuing further I/O requests. Using threads is a natural wayto avoidgetting stuck; while one thread in your program waits ( , is blockedwaiting for I/O), the CPU scheduler can switch to other threads, whichare ready to run and do something useful.

7 Threading enablesoverlapofI/O with other activitieswithina single program, much likemultipro-grammingdid for processesacrossprograms; as a result, many modernserver-based applications (web servers, database management systems,and the like) make use of threads in their course, in either of the cases mentioned above, you could use multi-pleprocessesinstead of threads. However, threads share an address spaceand thus make it easy to share data, and hence are a natural choice whenconstructing these types of programs. Processes are a more sound choicefor logically separate tasks where little sharing of data structures in mem-ory is An Example: Thread CreationLet s get into some of the details. Say we wanted to run a programthat creates two threads, each of which does some independent work, inthis case printing A or B . The code is shown in Figure (page 4).

8 The main program creates two threads, each of which will run thefunctionmythread(), though with different arguments (the stringAorB). Once a thread is created, it may start running right away (dependingon the whims of the scheduler); alternately, it may be put in a ready butnot running state and thus not run yet. Of course, on a multiprocessor,the threads could even be running at the same time, but let s not worryabout this possibility quite 2008 21, ARPACI-DUSSEAUTHREEEASYPIECES4 CONCURRENCY: ANINTRODUCTION1#include < >2#include < >3#include < >4#include " "5#include " "67void*mythread(void*arg) {8printf("%s\n", (char*) arg);9return NULL;10}1112int13main(int argc, char*argv[]) {14pthread_t p1, p2;15int rc;16printf("main: begin\n");17 Pthread_create(&p1, NULL, mythread, "A");18 Pthread_create(&p2, NULL, mythread, "B");19// join waits for the threads to finish20 Pthread_join(p1, NULL);21 Pthread_join(p2, NULL);22printf("main: end\n");23return 0;24}Figure :Simple Thread Creation Code( )After creating the two threads (let s call them T1 and T2), themainthread callspthreadjoin(), which waits for a particular thread tocomplete.

9 It does so twice, thus ensuring T1 and T2 will run and com-plete before finally allowing the main thread to run again; whenit does,it will print main: end and exit. Overall, three threads were employedduring this run: the main thread, T1, and us examine the possible execution ordering of this little the execution diagram (Figure , page 5), time increases in the down-wards direction, and each column shows when a different thread (themain one, or Thread 1, or Thread 2) is , however, that this ordering is not the only possible , given a sequence of instructions, there are quite a few, depending onwhich thread the scheduler decides to run at a given point. For example,once a thread is created, it may run immediately, which would lead to theexecution shown in Figure (page 5).We also could even see B printed before A , if, say, the schedulerdecided to run Thread 2 first even though Thread 1 was created earlier;there is no reason to assume that a thread that is created first will run (page 6) shows this final execution ordering, with Thread 2getting to strut its stuff before Thread you might be able to see, one way to think about thread creationOPERATINGSYSTEMS[ ] : ANINTRODUCTION5mainThread 1 Thread2starts runningprints main: begin creates Thread 1creates Thread 2waits for T1runsprints A returnswaits for T2runsprints B returnsprints main: end Figure :Thread Trace (1)mainThread 1 Thread2starts runningprints main: begin creates Thread 1runsprints A returnscreates Thread 2runsprints B returnswaits for T1returns immediately; T1 is donewaits for T2returns immediately.

10 T2 is doneprints main: end Figure :Thread Trace (2)is that it is a bit like making a function call; however, insteadof first ex-ecuting the function and then returning to the caller, the system insteadcreates a new thread of execution for the routine that is being called, andit runs independently of the caller, perhaps before returningfrom the cre-ate, but perhaps much later. What runs next is determined by the OSscheduler, and although the scheduler likely implements some sensiblealgorithm, it is hard to know what will run at any given moment in you also might be able to tell from this example, threads makelifecomplicated: it is already hard to tell what will run when! Computers arehard enough to understand without concurrency. Unfortunately,withconcurrency, it simply gets worse. Much 2008 21, ARPACI-DUSSEAUTHREEEASYPIECES6 CONCURRENCY: ANINTRODUCTION mainThread 1 Thread2starts runningprints main: begin creates Thread 1creates Thread 2runsprints B returnswaits for T1runsprints A returnswaits for T2returns immediately; T2 is doneprints main: end Figure :Thread Trace (3) Why It Gets Worse: Shared DataThe simple thread example we showed above was useful in showinghow threads are created and how they can run in different orders depend-ing on how the scheduler decides to run them.