CMSC 330: Organization of Programming Languages Multithreading CMSC 330 - Spring 2011 1CMSC 330 - Spring 2011 Multiprocessors ! Description • Multiple processing units (multiprocessor) • From single microprocessor to large compute clusters • Can perform multiple tasks in parallel simultaneously 106K processor IBM BlueGene/L 32 processor Pentium Xeon Intel Core 2 Quad 6600 2CMSC 330 - Spring 2011 Concurrency ! Important & pervasive topic in CS ! Currently covered in • CMSC 132 – object-oriented programming II Java threads, data races, synchronization • CMSC 216 – low level programming / computer systems C pthreads • CMSC 411/430 – architectures / compilers Instruction level parallelism • CMSC 412 – operating systems Concurrent processes • CMSC 424 – database design Concurrent transactions • CMSC 433 – programming language technologies Advanced synchronization • CMSC 451 – algorithms Parallel algorithms 3CMSC 330 - Spring 2011 Computation Abstractions CPU 1 CPU 2 p3 p1 p2 p4 t1 t2 t1 t2 t3 t1 t4 t5 AcomputerProcesses(e.g.,JVMʼs)Threads4CMSC 330 - Spring 2011 Processes vs. Threads int x; foo() { …x… } int x; foo() { …x… } int x; foo() { …x… } foo() { …x… } ProcessesdonotsharedataThreadssharedatawithinaprocess5CMSC 330 - Spring 2011 So, What Is a Thread? ! Conceptually • Parallel computation occurring within a process ! Implementation view • A program counter and a stack • Heap and static area are shared among all threads ! All programs have at least one thread (main) 6CMSC 330 - Spring 2011 Implementation View ! Per-thread stack and instruction pointer • Saved in memory when thread suspended • Put in hardware esp/eip when thread resumes eip eip eip esp esp esp esp eip stack pointer program counter 7CMSC 330 - Spring 2011 Programming Threads ! Thread creation is inexpensive ! Threads reside on same physical processor ! Threads share memory, resources • Except for thread local variables ! Shared-memory programming paradigm • Threads communicate via shared data • Synchronization used to avoid data races ! Limited scalability (10ʼs of threads) • This is a traditional point of view, based on threads running on a single processor • With the advent of multicore architectures, it is much less applicable 8CMSC 330 - Spring 2011 Programming Processes ! Process creation is expensive • Must allocate, copy memory ! Processes may reside on separate processors ! Processes do not share memory ! Message-passing programming paradigm • Messages using I/O streams, sockets, network, files ! Processes must cooperate to communicate • Actions performed to send and receive data ! Highly scalable (1000ʼs of processors) 9CMSC 330 - Spring 2011 Programming Languages & Threads ! Threads are available in many languages • C, C++, Java, Ruby, OCaml… ! In older languages (e.g., C and C++), threads are a platform specific add-on • Not part of the language specification • Implemented as code libraries (e.g., pthreads) ! In newer languages (e.g., Java, Ruby), threads are part of the language specification • Not dependent on operating system • Can utilize special keywords, syntax 10What Is the Big Deal about Threads? ! Conventional wisdom: threads are hard ! Main reason: nondeterminism • Different threads execute at different speeds • This leads to unpredictable results • When you program with threads, you have to be ready for unexpected results CMSC 330 - Spring 2011 11Example ! Suppose x = 0 initially, and following threads executed ! What is the value of x afterward • Could be 2 • Could also be 1! CMSC 330 - Spring 2011 12 T1 y = x; T2 z = x; x = y+1; x = z+1; T1 y = x; T2 x = y+1; z = x; x = z+1; T1 y = x; T2 z = x; x = y+1; x = z+1;Data Races ! The previous example is an illustration of a data race • Threads are “racing” to read, write x • If one thread completes its write before other reads: value of x is 2 • If both threads read x before either writes it: value of x is 1 ! Languages rarely specify who wins data races, so programs must handle any outcome CMSC 330 - Spring 2011 13Our Study of Threads ! We will develop a simple toy language to highlight issues in multithreading • Language will be given an operational semantics • Possibilities for nondeterminism will be highlighted ! We will add concurrency-control constructs that are intended to control nondeterminism • Impact on semantics will be shown • Possibilities for other adverse behavior will emerge: deadlock ! Morals • Concurrency (i.e. multithreading) is fraught with perils! • If you are aware of them, you can cope CMSC 330 - Spring 2011 14Toy Language (TL): Expression Syntax E ::= x | n | E op E (op ∈{+,-,/,*, etc.}) ! x ∈Id is an identifier ! n is an integer ! op ∈{+,-,/,*, ...} is a set of integer operations CMSC 330 - Spring 2011 15TL: Expression Semantics ! Similar to before • Let Z (integers) be the set of results • Let A be an environment (i.e. element of Id → Z) • Then meaning of expressions given via A;E ⇒ v If E is an expression Then A;E ⇒ v means e evaluates to v in context of A • Following rules define ⇒ CMSC 330 - Spring 2011 16 – A;x ⇒A(x) – A;n ⇒n E1 ⇒v1E2 ⇒v2 E1 op E2 ⇒v1opv2TL: Sequential Commands Syntax ! Programs in TL built from expressions and commands • Commands modify environment, implement control flow • Later they will also create threads, etc. ! Syntax of sequential (i.e. no threads) commands • Let x be an Id, E an expression, l an Id (“label”) • Then a command has following form C := skip | halt | x = E | goto l | if E != 0 then goto l • Let Cmd be the set of all commands CMSC 330 - Spring 2011 17TL: Sequential Programs Syntax ! Programs will be sequences of (possibly labeled) commands ! Example sum = 0 top: sum = sum + B B = B-1 if B != 0 goto top halt ! What program does: • If B > 1 then when
View Full Document