Без темы
<<  Private Banking Customized Financial Planning PROJECT ACHIEVEMENTS: UKRAINIAN EXPERIENCE – LESSONS LEARNED  >>
Programming with Shared Memory Threads Accessing shared data Critical
Programming with Shared Memory Threads Accessing shared data Critical
Shared memory multiprocessor system
Shared memory multiprocessor system
Programming a Shared Memory System Generally, more convenient and
Programming a Shared Memory System Generally, more convenient and
Methods for Programming Shared Memory Multiprocessors Using
Methods for Programming Shared Memory Multiprocessors Using
Using Heavyweight Processes Operating systems often based upon notion
Using Heavyweight Processes Operating systems often based upon notion
(UNIX) FORK-JOIN construct
(UNIX) FORK-JOIN construct
UNIX System Calls
UNIX System Calls
Differences between a process and threads
Differences between a process and threads
Pthreads IEEE Portable Operating System Interface, POSIX standard
Pthreads IEEE Portable Operating System Interface, POSIX standard
Detached Threads It may be that thread are not bothered when a thread
Detached Threads It may be that thread are not bothered when a thread
Pthreads Detached Threads
Pthreads Detached Threads
Issues in writing shared memory programs
Issues in writing shared memory programs
Interleaved Statements Instructions of processes/threads interleaved
Interleaved Statements Instructions of processes/threads interleaved
Thread-Safe Routines Thread safe if routine can be called from
Thread-Safe Routines Thread safe if routine can be called from
2. Re-ordering code Static re-ordering - Compilers may re-order code
2. Re-ordering code Static re-ordering - Compilers may re-order code
Compiler/Processor Optimizations Compiler and processor reorder
Compiler/Processor Optimizations Compiler and processor reorder
3. Accessing Shared Data Accessing shared data needs careful control
3. Accessing Shared Data Accessing shared data needs careful control
Instruction Process/thread 1 Process/thread 2 x = x + 1; read x
Instruction Process/thread 1 Process/thread 2 x = x + 1; read x
Critical Section A mechanism for ensuring that only one process
Critical Section A mechanism for ensuring that only one process
Locks Simplest mechanism for ensuring mutual exclusion of critical
Locks Simplest mechanism for ensuring mutual exclusion of critical
Control of critical sections through busy waiting
Control of critical sections through busy waiting
Pthreads Lock routines Locks implemented in Pthreads with mutually
Pthreads Lock routines Locks implemented in Pthreads with mutually
Condition Variables Often, a critical section is to be executed if a
Condition Variables Often, a critical section is to be executed if a
Pthread Condition Variables Pthreads arrangement for signal and wait:
Pthread Condition Variables Pthreads arrangement for signal and wait:
Critical Sections Serializing Code High performance programs should
Critical Sections Serializing Code High performance programs should
Illustration
Illustration
Deadlock Can occur with two processes when one requires a resource
Deadlock Can occur with two processes when one requires a resource
Deadlock Deadlock can also occur in a circular fashion with several
Deadlock Deadlock can also occur in a circular fashion with several
Pthreads pthtrylock routine Offers one routine that can test whether a
Pthreads pthtrylock routine Offers one routine that can test whether a
Semaphores A positive integer (including zero) operated upon by two
Semaphores A positive integer (including zero) operated upon by two
P and V operations are performed indivisibly
P and V operations are performed indivisibly
Mutual exclusion of critical sections can be achieved with one
Mutual exclusion of critical sections can be achieved with one
General semaphore (or counting semaphore) Can take on positive values
General semaphore (or counting semaphore) Can take on positive values
Monitor Suite of procedures that provides only way to access shared
Monitor Suite of procedures that provides only way to access shared
Program example To sum the elements of an array, a[1000]: int sum,
Program example To sum the elements of an array, a[1000]: int sum,
Pthreads program example
Pthreads program example
37
37
38
38
Questions
Questions

Презентация: «Programming with Shared Memory Threads Accessing shared data Critical sections». Автор: Barry Wilkinson. Файл: «Programming with Shared Memory Threads Accessing shared data Critical sections.ppt». Размер zip-архива: 333 КБ.

Programming with Shared Memory Threads Accessing shared data Critical sections

содержание презентации «Programming with Shared Memory Threads Accessing shared data Critical sections.ppt»
СлайдТекст
1 Programming with Shared Memory Threads Accessing shared data Critical

Programming with Shared Memory Threads Accessing shared data Critical

sections

8a-1

ITCS4145/5145, Parallel Programming B. Wilkinson Jan 4, 2013 slides8a.ppt

2 Shared memory multiprocessor system

Shared memory multiprocessor system

Processors cores and processors

Single address space exists – each memory location given unique address within single range of addresses. Any memory location can be accessible by any of the processors. Multicore processors are of this type. Also multiprocessor servers such as coit-grid05.uncc.edu, which have both multicore processors and multiple such processors

Address 0 1 2 3

Memory locations

2

3 Programming a Shared Memory System Generally, more convenient and

Programming a Shared Memory System Generally, more convenient and

efficient than message passing. Can take advantage of shared memory for holding data rather than explicit message passing to share data. However access to shared data by different processors needs to be carefully controlled usually explicitly by programmer. Shared memory systems have been around for a long time but with the advent of multi-core systems, it has become very important to able to program for them

3

4 Methods for Programming Shared Memory Multiprocessors Using

Methods for Programming Shared Memory Multiprocessors Using

heavyweight processes. Using threads explicitly - e.g. Pthreads, Java threads Using a sequential programming language such as C supplemented with compiler directives and libraries for specifying parallelism. e.g. OpenMP. Underlying mechanism on OpenMP is thread-based. Using a “parallel programming” language, e.g. Ada, UPC - not popular. We will look mostly at thread API’s and OpenMP

4

5 Using Heavyweight Processes Operating systems often based upon notion

Using Heavyweight Processes Operating systems often based upon notion

of a process. Processor time shares between processes, switching from one process to another. Might occur at regular intervals or when an active process becomes delayed. Offers opportunity to de-schedule processes blocked from proceeding for some reason, e.g. waiting for an I/O operation to complete. Concept could be used for parallel programming. Not much used because of overhead but fork/join concepts used elsewhere.

5

6 (UNIX) FORK-JOIN construct

(UNIX) FORK-JOIN construct

Fork here creates a complete copy of the main program and starts it at the same place as the Fork. Both programs continue together.

6

7 UNIX System Calls

UNIX System Calls

No join routine – use exit() to exit from process and wait() to wait for slave to complete: … pid = fork(); if (pid == 0) { // code to be executed by child } else { //code to be executed by parent } if (pid == 0) exit(0); else wait (0); …

8a-7

8 Differences between a process and threads

Differences between a process and threads

8

9 Pthreads IEEE Portable Operating System Interface, POSIX standard

Pthreads IEEE Portable Operating System Interface, POSIX standard

9

10 Detached Threads It may be that thread are not bothered when a thread

Detached Threads It may be that thread are not bothered when a thread

it creates terminates and then a join not needed. Threads not joined are called detached threads. When detached threads terminate, they are destroyed and their resource released.

10

11 Pthreads Detached Threads

Pthreads Detached Threads

11

12 Issues in writing shared memory programs

Issues in writing shared memory programs

8a-12

13 Interleaved Statements Instructions of processes/threads interleaved

Interleaved Statements Instructions of processes/threads interleaved

in time. Example Process/Thread 1 Process/Thread 2 Instruction 1.1 Instruction 2.1 Instruction 1.2 Instruction 2.2 Instruction 1.3 Instruction 2.3 Many possible orderings, e.g.: Instruction 1.1 Instruction 1.2 Instruction 2.1 Instruction 1.3 Instruction 2.2 Instruction 2.3 assuming instructions cannot be divided into smaller steps.

Each process/thread must achieve the desired results irrespective of the interleaving order

13

14 Thread-Safe Routines Thread safe if routine can be called from

Thread-Safe Routines Thread safe if routine can be called from

multiple threads simultaneously and always produce correct results. Standard I/O thread safe (prints messages without interleaving the characters). System routines that return time may not be thread safe. Routines that access shared data may require special care to be made thread safe.

14

15 2. Re-ordering code Static re-ordering - Compilers may re-order code

2. Re-ordering code Static re-ordering - Compilers may re-order code

during compilation and prior to execution of code Dynamic re-ordering - Processors may re-order code during execution. In both cases, objective is to best utilize available computer resources and minimize execution time.

8a-15

16 Compiler/Processor Optimizations Compiler and processor reorder

Compiler/Processor Optimizations Compiler and processor reorder

instructions to improve performance. Example Suppose one had the code: a = b + 5; x = y * 4; p = x + 9; and processor can perform, as is usual, multiple arithmetic operations at the same time. Can reorder to: x = y * 4; a = b + 5; p = x + 9; and still be logically correct. This gives multiply operation longer time to complete before result (x) is needed in last statement. Very common for processors to execute machines instructions “out of program order” for increased speed.

16

17 3. Accessing Shared Data Accessing shared data needs careful control

3. Accessing Shared Data Accessing shared data needs careful control

Consider two processes each of which is to add one to a shared data item, x. Location x is read, x + 1 computed, and the result written back to the location:

17

18 Instruction Process/thread 1 Process/thread 2 x = x + 1; read x

Instruction Process/thread 1 Process/thread 2 x = x + 1; read x

compute x + 1 write to x read x compute x + 1 write to x

Get x = x + 2 finally.

Instruction Process/thread 1 Process/thread 2 x = x + 1; read x read x compute x + 1 compute x + 1 write to x write to x

Get x = x + 1 finally.

8a-18

19 Critical Section A mechanism for ensuring that only one process

Critical Section A mechanism for ensuring that only one process

accesses a particular resource at a time. critical section – a section of code for accessing resource Arrange that only one such critical section is executed at a time. This mechanism is known as mutual exclusion. Concept also appears in an operating systems.

19

20 Locks Simplest mechanism for ensuring mutual exclusion of critical

Locks Simplest mechanism for ensuring mutual exclusion of critical

sections. A lock - a 1-bit variable that is a 1 to indicate that a process has entered the critical section and a 0 to indicate that no process is in the critical section. Operates much like that of a door lock: A process coming to the “door” of a critical section and finding it open may enter the critical section, locking the door behind it to prevent other processes from entering. Once the process has finished the critical section, it unlocks the door and leaves.

20

21 Control of critical sections through busy waiting

Control of critical sections through busy waiting

21

22 Pthreads Lock routines Locks implemented in Pthreads with mutually

Pthreads Lock routines Locks implemented in Pthreads with mutually

exclusive lock variables, or “mutex” variables: … pthread_mutex_lock(&mutex1); critical section pthread_mutex_unlock(&mutex1); … If a thread reaches mutex lock and finds it locked, it will wait for lock to open. If more than one thread waiting for lock to open, when it does open, system selects one thread to be allowed to proceed. Only thread that locks a mutex can unlock it.

Same mutex variable

22

23 Condition Variables Often, a critical section is to be executed if a

Condition Variables Often, a critical section is to be executed if a

specific global condition exists; for example, if a certain value of a variable has been reached. With locks, the global variable would need to be examined at frequent intervals (“polled”) within a critical section. Very time-consuming and unproductive exercise. Can be overcome by introducing so-called condition variables.

23

24 Pthread Condition Variables Pthreads arrangement for signal and wait:

Pthread Condition Variables Pthreads arrangement for signal and wait:

Notes: Signals not remembered - threads must already be waiting for a signal to receive it. Pthread_cond_wait() unlocks mutex1 so that it can be used other thread and relocks it after woken up. Value of c checked in both threads

24

25 Critical Sections Serializing Code High performance programs should

Critical Sections Serializing Code High performance programs should

have as few as possible critical sections as their use can serialize the code. Suppose, all processes happen to come to their critical section together. They will execute their critical sections one after the other. In that situation, the execution time becomes almost that of a single processor.

25

26 Illustration

Illustration

26

27 Deadlock Can occur with two processes when one requires a resource

Deadlock Can occur with two processes when one requires a resource

held by the other, and this process requires a resource held by the first process.

27

28 Deadlock Deadlock can also occur in a circular fashion with several

Deadlock Deadlock can also occur in a circular fashion with several

processes having a resource wanted by another.

28

29 Pthreads pthtrylock routine Offers one routine that can test whether a

Pthreads pthtrylock routine Offers one routine that can test whether a

lock is actually closed without blocking the thread: pthread_mutex_trylock() Will lock an unlocked mutex and return 0 or will return with EBUSY if the mutex is already locked – might find a use in overcoming deadlock.

29

30 Semaphores A positive integer (including zero) operated upon by two

Semaphores A positive integer (including zero) operated upon by two

operations: P operation on semaphore s Waits until s is greater than zero and then decrements s by one and allows the process to continue. V operation on semaphore s Increments s by one and releases one of the waiting processes (if any).

30

31 P and V operations are performed indivisibly

P and V operations are performed indivisibly

Mechanism for activating waiting processes implicit in P and V operations. Though exact algorithm not specified, algorithm expected to be fair. Processes delayed by P(s) are kept in abeyance until released by a V(s) on the same semaphore. Devised by Dijkstra in 1968. Letter P from Dutch word passeren, meaning “to pass” Letter V from Dutch word vrijgeven, meaning “to release”

31

32 Mutual exclusion of critical sections can be achieved with one

Mutual exclusion of critical sections can be achieved with one

semaphore having the value 0 or 1 (a binary semaphore), which acts as a lock variable, but P and V operations include a process scheduling mechanism: Process 1 Process 2 Process 3 Noncritical section Noncritical section Noncritical section … ... … P(s) P(s) P(s) Critical section Critical section Critical section V(s) V(s) V(s) … … … Noncritical section Noncritical section Noncritical section

32

33 General semaphore (or counting semaphore) Can take on positive values

General semaphore (or counting semaphore) Can take on positive values

other than zero and one. Provide, for example, a means of recording number of “resource units” available or used. Can solve producer/ consumer problems - more on that in operating system courses. Semaphore routines exist for UNIX processes. Does not exist in Pthreads as such, though they can be written. Do exist in real-time extension to Pthreads.

33

34 Monitor Suite of procedures that provides only way to access shared

Monitor Suite of procedures that provides only way to access shared

resource. Only one process can use a monitor procedure at any instant. Could be implemented using a semaphore or lock to protect entry, i.e.: monitor_proc1() { lock(x); monitor body unlock(x); return; }

A version of a monitor exists in Java threads, see later

34

35 Program example To sum the elements of an array, a[1000]: int sum,

Program example To sum the elements of an array, a[1000]: int sum,

a[1000]; sum = 0; for (i = 0; i < 1000; i++) sum = sum + a[i];

35

36 Pthreads program example

Pthreads program example

n threads created, each taking numbers from list to add to their local partial sums. When all numbers taken, threads can add their partial sums to a shared location sum. Shared location global_index used by each thread to select next element of a[]. After global_index read, it is incremented in preparation for next element to be read.

Modified within critical sections

36

37 37

37

38 38

38

39 Questions

Questions

8a-39

«Programming with Shared Memory Threads Accessing shared data Critical sections»
http://900igr.net/prezentacija/anglijskij-jazyk/programming-with-shared-memory-threads-accessing-shared-data-critical-sections-108798.html
cсылка на страницу
Урок

Английский язык

29 тем
Слайды
900igr.net > Презентации по английскому языку > Без темы > Programming with Shared Memory Threads Accessing shared data Critical sections