DOC PREVIEW
UMD CMSC 330 - Multithreading

This preview shows page 1-2-3-4-5-6-39-40-41-42-43-80-81-82-83-84-85 out of 85 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 85 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 AcomputerProcesses(e.g.,JVMʼs)Threads4CMSC 330 - Spring 2011 Processes vs. Threads int x; foo() { …x… } int x; foo() { …x… } int x; foo() { …x… } foo() { …x… } ProcessesdonotsharedataThreadssharedatawithinaprocess5CMSC 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 ⇒v1E2 ⇒v2 E1 op E2 ⇒v1opv2TL: 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

UMD CMSC 330 - Multithreading

Documents in this Course
Exam #1

Exam #1

6 pages

Quiz #1

Quiz #1

2 pages

Midterm 2

Midterm 2

12 pages

Exam #2

Exam #2

7 pages

Ocaml

Ocaml

7 pages

Parsing

Parsing

38 pages

Threads

Threads

12 pages

Ruby

Ruby

7 pages

Quiz #3

Quiz #3

2 pages

Threads

Threads

7 pages

Quiz #4

Quiz #4

2 pages

Exam #2

Exam #2

6 pages

Exam #1

Exam #1

6 pages

Threads

Threads

34 pages

Quiz #4

Quiz #4

2 pages

Threads

Threads

26 pages

Exam #2

Exam #2

9 pages

Exam #2

Exam #2

6 pages

Load more
Download Multithreading
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Multithreading and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Multithreading 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?