Bài giảng Nguyên lý ngôn ngữ lập trình - Chương 9: Ngôn ngữ lập trình song song - Nguyễn Văn Hòa
Chương 9: Ngôn ngꢀ lꢁp
trình song song
Giꢀng viên: Ph.D Nguyꢁn Văn Hòa
Khoa KT-CN-MT – ðH An Giang
1
Nꢂi dung
ꢀ Giꢂi thiꢃu
ꢀ SubProprogam-level
ꢀ Semaphores
ꢀ Chương trình giám sát (monitor)
ꢀ Truyꢄn thông ñiꢃp (massage passing)
ꢀ Luꢅng (Java thread)
2
Giꢃi thiꢄu
ꢀ Sꢆ tương tranh (concurrency) có thꢇ xꢀy ra ꢈ 4
mꢉc sau:
1. Lꢃnh mã máy
2. Câu lꢃnh cꢊa NN LT cꢋp cao (lꢃnh lꢌp)
3. Chương trình con
4. Chương trình
ꢀ Vì không có mꢍt NN LT nào hꢎ trꢏ tương tranh ꢈ
mꢉc chương trình, và lꢃnh mã máy nên 2 sꢆ
tương tranh này không ñưꢏc trình bày ꢈ chương
này
3
Giꢃi thiꢄu (tt)
ꢀ ðN: Thread ñiꢄu khiꢇn trong mꢍt chương trình là
thꢉ tꢆ các ñiꢇm cꢐn ñꢑn cꢊa CT
ꢀ Phân loꢒi sꢆ tương tranh:
1. Tương tranh vꢓt lý (physical concurrency) – Multiple
processors ñꢍc lꢓp (ñiꢄu khiꢇn vꢂi multiple threads)
2. Trương tranh logic (logical concurrency) – Sꢆ tương
tranh này xuꢋt hiꢃn khi có sꢆ chia sꢔ trên cùng mꢍt
processor (Mꢍt phꢐn mꢄn có thꢇ ñưꢏc thiꢑt kꢑt vꢂi
multiple thread)
4
Giꢃi thiꢄu (tt)
ꢀ Tꢒi sao phꢀi hꢕc sꢆ tương tranh trong NN LT
1. Rꢋt hꢖu dꢗng cho viꢃc thiꢑt kꢑ chương trình hꢎ trꢏ
tính toán song song
2. Máy tính hꢎ trꢏ tương tranh vꢓt lý (multi-core
processors) rꢋt phꢘ biꢑn
5
Kiꢅn trúc máy tính multi-core
Single instruction
multiple data (SIMD)
Multiple Instruction
multiple data (MIMD)
6
Tương tranh ꢆ mꢇc chương trình con
ꢀ
ðN: Mꢍt công viꢃc (task) hoꢌc tiꢑn trình (process) là mꢍt
ñơn vꢙ chương trình ñưꢏc thꢆc hiꢃn ñꢅng thꢚi vꢂi nhꢖng
chương trình khác
ꢀ
Task khác vꢂi chương trình con như thꢑ nào?
ꢁ
Task có thꢇ ñưꢏc bꢛt ñꢐu ꢈ thꢚi ñiꢇm tưꢚng minh
ꢁ
Khi mꢍt chương trình bꢛt ñꢐu thꢆc thi mꢍt task, thông thưꢚng thì
không bꢙ ñình hoãn
ꢁ
Khi viꢃc thꢆc thi mꢍt task kꢑt thúc thì không nhꢋt thiꢑt phꢀi trꢀ
quyꢄn ñiꢄu khiꢇn cho caller
ꢀ
Các công viꢃc (tasks) có thꢇ trao ñꢘi qua lꢒi
7
Tương tranh ꢆ mꢇc CT con (tt)
ꢀ Thông thưꢚng có 2 loꢒi tasks
ꢁ Heavyweight tasks thꢆc thi vꢂi không gian ñꢙa chꢜ và
run-time stack cꢊa chính nó
ꢁ Lightweight tasks luôn luôn thꢆc thi vꢂi cùng không
gian ñꢙa chꢜ và cùng run-time stack
8
Tương tranh ꢆ mꢇc CT con (tt)
ꢀ ðN: mꢍt task riêng biꢃt (disjoint) nꢑu như nó
không giao tiꢑp hoꢌc ꢀnh hưꢚng ñꢑn sꢆ thꢆc thi
cꢊa mꢍt task nào ñó trong mꢍt chương trình bꢋt
kỳ
ꢀ Mꢍt task giao tiꢑp vꢂi mꢍt task khác thì cꢐn
thiꢑt phꢀi có sꢆ ñꢅng bꢍ hóa (synchronization)
ꢁ Sꢆ giao tiꢑp có thꢇ bꢝng:
1. Chia sꢔ các biꢑn không cꢗc bꢍ
2. Tham sꢞ
3. Truyꢄn thông ñiꢃp
9
Tương tranh ꢆ mꢇc CT con (tt)
ꢀ Các kiꢇu ñꢅng bꢍ hóa :
1. H
Task A ph
tác v nh
ti p t
2. C nh tranh (competition)
Khi hai ho c nhi u tasks cùng dùng chung m
(resource) nh ng tài nguyên này không th dùng ñꢅng
th ñưꢏ
canh tranh thưꢚng ñưꢏc cung c
i tr n nhau
ꢏ
p tác (Cooperation)
ñꢏi cho ñꢑn khi task B hoàn thành m
ñꢙnh nào ó trưꢂc khi task A có th th
mô hình producer-consumer
ꢁ
ꢀ
t
i
ꢍ
t vài
ꢗ
ꢋ
ñ
ꢇ
ꢆc hi
ꢃ
n
ꢑ
ꢒ
ꢗc →
ꢁ
ꢁ
ꢌ
ꢄ
ꢍt tài nguyên
ư
ꢇ
ꢚ
ꢆ
ꢒ
i
c
S
lo
ꢋp bꢈi quyꢄn truy cꢓp
ꢟ lꢠ
10
Sꢈ cꢉn thiꢅt cꢊa ñông bꢂ hóa
trong cꢋnh tranh
11
Tương tranh ꢆ mꢇc CT con (tt)
ꢀ Viꢃc ñꢅng bꢍ hóa ñòi hꢡi mꢍt cơ chꢑ cꢊa sꢆ trꢙ
hoãn viꢃc thꢆc thi các task
ꢀ Sꢆ ñiꢄu khiꢇn viꢃc thꢆc thi ñưꢏc ñiꢄu hành bꢈi
mꢍt chương trình, gꢕi là scheduler, có nhiꢃu vꢗ
sꢛp ñꢌt viꢃc thꢆc thi task vào nhꢖng processors
sꢢn có
12
Tương tranh ꢆ mꢇc CT con (tt)
ꢀ Các Task có thꢇ ꢈ mꢍt trong vài trꢒng thái sau
ñây:
1. New – mꢂi khꢈi tꢒo nhưng chưa ñưꢏc thꢆc hiꢃn
2. Runnable hoꢌc ready – sꢢn sàng ñꢇ chꢒy nhưng chưa
chꢒy (vì không có processor sꢢn có)
3. Running
4. Blocked – ñã chꢒy, nhưng không thꢇ tiꢑp tꢗc vì ñang
ñꢏi vài sꢆ kiꢃn nào ñó xꢀy ra)
5. Dead
13
Tương tranh ꢆ mꢇc CT con (tt)
ꢀ Liveness là ñꢌc ñiꢇm mà mꢍt chương trình có thꢇ
có hoꢌc không
ꢁ Trong code tuꢐn tꢆ, nghĩa là nꢑu mꢍt CT tiꢑp tꢗc thꢆc
thi → dꢠn ñꢑn sꢆ cꢒnh tranh
ꢁ Trong môi trưꢚng tương tranh, mꢍt task có thꢇ dꢁ dàng
mꢋt liveness cꢊa nó
ꢁ Nꢑu tꢋt cꢀ các task trong môi trưꢚng tương tranh ñꢄu
mꢋt liveness cꢊa chúng, trưꢚng hꢏp này gꢕi là
deadlock
14
Tương tranh ꢆ mꢇc CT con (tt)
ꢀ Các NN LT hꢎ trꢏ tương tranh ñꢄu có 2 cơ chꢑ:
ñꢅng bꢍ hóa cꢒnh tranh và ñꢅng bꢍ hóa hꢏp tác
ꢀ Các yꢑu tꢞ khi thiꢑt kꢑ tương tranh:
1. Sꢆ ñꢅng bꢍ hóa hꢏp tác ñưꢏc cung cꢋp như thꢑ nào?
2. Sꢆ ñꢅng bꢍ hóa tương tranh ñưꢏc cung cꢋp như thꢑ
nào?
3. Cách gì và khi nào mꢍt task bꢛt ñꢐu và kꢑt thúc thꢆc
thi?
4. Các task có ñưꢏc sinh ra mꢍt cách tĩnh hay ñꢍng?
15
Tương tranh ꢆ mꢇc CT con (tt)
ꢀ Các phương thꢉc ñꢅng bꢍ hóa:
1. Semaphores
2. Chương trình giám sát (Monitors)
3. Truyꢄn thông ñiꢃp (Message Passing)
16
Semaphores
ꢀ Dijkstra - 1965
ꢀ Mꢍt semaphore là mꢍt cꢋu trúc dꢖ liꢃu chꢉa mꢍt
counter và mꢍt hàng ñꢏi (queue) nhꢝm lưu trꢖ các
mô tꢀ cꢊa task
ꢀ Các semaphores ñưꢏc dùng ñꢇ cài ñꢌt các bꢀo vꢃ
trong code có sꢆ truy nhꢓp các cꢋu trúc dꢖ liꢃu
chia sꢔ
ꢀ Các semaphores chꢜ có 2 thao tác vꢗ, wait và
release (hay ñưꢏc gꢕi P và V bꢈi Dijkstra)
ꢀ Các semaphores có thꢇ ñưꢏc dùng trong cꢀ ñꢅng
bꢍ hóa cꢒnh tranh và hꢏp tác
17
Semaphores
ꢀ ðꢅng bꢍ hóa hꢏp tác vꢂi Semaphores
ꢁ Example: Mꢍt buffer chia sꢔ
ꢁ Buffer ñưꢏc cài ñꢌt vꢂi hai tác vꢗ DEPOSITvà
FETCHnhư là hai cách thꢉc ñꢇ truy nhꢓp buffer
ꢁ Sꢣ dꢗng hai semaphores cho sꢆ hꢏp tác:
emptyspotsvà fullspots
ꢁ Counter cꢊa hai semaphore dùng ñꢇ lưu trꢖ sꢞ empty
spots và full spots trong buffer
18
Semaphores
ꢀ Trưꢂc tiên DEPOSITphꢀi kiꢇm tra
emptyspotsxem có còn khoꢀng trꢞng trong
buffer không
ꢀ Nꢑu còn khoꢀng trꢞng thì counter cꢊa emtyspots
giꢀm ñi mꢍt và giá trꢙ ñưꢏc ñưa vào buffer
ꢀ Nꢑu không còn khoꢀng trꢞng thì chương trình gꢕi
DEPOSIT ñưꢏc ñꢌt trong hàng ñꢏi cho ñꢑn khi có
mꢍt emtyp spot rꢎng
ꢀ Khi kꢑt thúc DEPOSIT, giá trꢙ cꢊa counter cꢊa
fullspotsñưꢏc tăng lên mꢍt
19
Semaphores
ꢀ Trưꢂc tiên FETCH phꢀi kiꢇm tra fullspots
xem có còn giá trꢙ nào trong buffer không
ꢁ Nꢑu còn thì mꢍt giá trꢙ ñưꢏc lꢋy ra và counter cꢊa
fullspotsbꢙ giꢀm ñi mꢍt
ꢁ Nꢑu không còn giá trꢙ nào thì tiꢑn trình cꢊa FETCH
ñưꢏc ñꢌt trong hàng ñꢏi cho ñꢑn khi có mꢍt giá trꢙ xuꢋt
hiꢃn
ꢁ Khi kꢑt thúc FETCH, tăng counter cꢊa emptyspots
lên mꢍt
ꢀ Hai thao tác FETCHvà DEPOSITtrên các
semaphore thành công thông qua hai thao tác wait
và release
20
Tải về để xem bản đầy đủ
52 trang
23000
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nguyên lý ngôn ngữ lập trình - Chương 9: Ngôn ngữ lập trình song song - Nguyễn Văn Hòa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_nguyen_ly_ngon_ngu_lap_trinh_chuong_9_ngon_ngu_lap.pdf
