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

1Chươ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
2Nộ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)
3Giớ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
4Giớ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)
5Giớ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 tốn song song
2. Máy tính hỗ trợ tương tranh vật lý (multi-core 
processors) rất phổ biến
6Kiến trúc máy tính multi-core
Single instruction 
multiple data (SIMD)
Multiple Instruction 
multiple data (MIMD)
7Tươ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 hỗ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
8Tươ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
9Tươ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
10
Tương tranh ở mức CT con (tt)

 Các kiểu đồng bộ hĩa :
1. Hợp tác (Cooperation)
 Task A phải đợi cho đến khi task B hồn thành một vài 
tác vụ nhất định nào đĩ trước khi task A cĩ thể thực hiện 
tiếp tục → mơ hình producer-consumer
2. Cạnh tranh (competition)
 Khi hai hoặc nhiều tasks cùng dùng chung một tài nguyên 
(resource) nhưng tài nguyên này khơng thể dùng đồng 
thời được
 Sự canh tranh thường được cung cấp bởi quyền truy cập 
loại trừ lẫn nhau
11
Sự cần thiết của đơng bộ hĩa 
trong cạnh tranh
12
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ị 
hỗ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ĩ
13
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
14
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
15
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?
16
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)
17
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
18
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ụ DEPOSIT và
FETCH như là hai cách thức để truy nhập buffer
 Sử dụng hai semaphores cho sự hợp tác:
emptyspots và fullspots
 Counter của hai semaphore dùng để lưu trữ số empty
spots và full spots trong buffer
19
Semaphores

 Trước tiên DEPOSIT phải kiểm tra 
emptyspots xem 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
20
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 
fullspots bị 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 FETCH và DEPOSIT trên các 
semaphore thành cơng thơng qua hai thao tác wait
và release
21
Semaphores
wait(aSemaphore)
if aSemaphore’s counter > 0 then
Decrement aSemaphore’s counter
else
Put the caller in aSemaphore’s queue
Attempt to transfer control to some
ready task 
(If the task ready queue is empty, 
deadlock occurs) 
end
22
Semaphores
release(aSemaphore)
if aSemaphore’s queue is empty {no one waiting}
then
Increment aSemaphore’s counter
else
Put the calling task in the task ready 
queue
Transfer control to a task from
aSemaphore’s queue
end
23
Producer Consumer Code
semaphore fullspots, emptyspots;
fullspots.count = 0;
emptyspots.count = BUFLEN;
task producer;
loop
-- produce VALUE –-
wait (emptyspots); {wait for space}
DEPOSIT(VALUE);
release(fullspots); {increase 
filled}
end loop;
end producer;
24
Producer Consumer Code
task consumer;
loop
wait (fullspots);{to make sure it is not empty}
FETCH(VALUE);
release(emptyspots); {increase empty space}
-- consume VALUE –-
end loop;
end consumer;
25
Semaphores

 ðồng bộ hĩa cạnh tranh với semaphores
 Semaphore thứ ba, cĩ tên là access, dùng để kiểm 
sốt truy cập (đồng bộ hĩa cạnh tranh)

 Counter của access sẽ chỉ cĩ hai giá trị 0 và 1

 Tương đương như là một semaphore nhị phân (binary
semaphore)

 Giá trị khởi tạo của access phải là 1, đồng nghĩa là 
tài nguyên đang ở trạng thái sẵn sàng. 0 nghĩa là bận
26
Code của Producer-Consumer 
semaphore access, fullspots, emptyspots;
access.count = 1;
fullstops.count = 0;
emptyspots.count = BUFLEN;
task producer;
loop
-- produce VALUE –-
wait(emptyspots); {wait for space}
wait(access); {wait for access)
DEPOSIT(VALUE);
release(access); {relinquish access}
release(fullspots); {increase filled space}
end loop;
end producer;
27
Code của Producer-Consumer
task consumer;
loop
wait(fullspots);{make sure it is not empty}
wait(access); {wait for access}
FETCH(VALUE);
release(access); {relinquish access}
release(emptyspots); {increase empty space}
-- consume VALUE –-
end loop;
end consumer;
28
Semaphores : nhận xét

 Mơi trường lập trình khơng an tồn (Unsafe)
 Sử dụng sai các semaphores cĩ thể là nguyên nhân thất 
bại trong đồng bộ hĩa hợp tác, e.g., buffer sẽ bị tràn 
(overflow) nếu khơng cĩ dịng code 
wait(emptyspots) trong producer task. Hoặc 
buffer sẽ bị underflow nếu khơng cĩ dịng code 
wait(fullspots)
 Trình biên dịch khơng thể kiểm tra việc dùng sai

 Sự tin cậy
 Sử dụng sai cĩ thể là nguyên nhân thất bại của đồng bộ 
hĩa cạnh tranh, e.g., chương trình sẽ bị deadlock nếu 
loại bỏ dịng code release(access)
29
Chương trình giám sát (Monitors)

 NNLT : concurrent Pascal, Modula, Mesa, tiếp 
theo là C#, Ada and Java

 Ý tưởng: bao đống dữ liệu chia sẽ và giới hạn các 
thao tác truy nhập

 CT giám sát là một trù tường hĩa dữ liệu cho 
những dữ liệu chia sẽ
30
Monitor Buffer Operation
31
ðồng bộ hĩa cạnh tranh

 Dữ liệu chia sẽ được đặt bên trong CT giám sát
(tốt hơn là đặt trong các client)

 Tất cả các truy nhập đều diễn ra ở trong CT giám 
sát
 Việc cài đặt CT giám sát phải bảo đảm các truy cập 
được đồng bộ bằng cách chỉ cĩ một truy cập tại một 
thời điểm nhất định
 Nếu CT giám sát bận vào thời điểm gọi, thì các lời gọi 
sẽ được đặt vào trong hàng đợi
32
ðồng bộ hĩa hợp tác

 Sự hợp tác giữa các tiến trình (processes) vẫn là 
một tác vụ trong lập trình
 Lập trình viên phải bảo đảm là khơng xảy ra underflow
và overflow trong một buffer chia sẽ
33
Chương Trình giám sát: nhận xét

 Hỗ trợ tốt cho sự đồng bộ hĩa cạnh tranh

 ðối với đồng bộ hĩa hợp tác thì tương tự như 
semaphore nên → sẽ gặp các vấn đề như 
semaphore
34
Truyền thơng điệp

 ðược đưa ra bởi Hansen & Hoare vào 1978

 Vấn đề: làm thế nào giải quyết vấn đề khi cĩ nhiều 
yêu cầu giao tiếp từ nhiều task với một task cho trước
 Vài dạng của cơ chế khơng quyết định cho sự cơng bằng
 Guarded commands của Dijkstra: kiểm sốt truyền thơng 
điệp

 Ý tưởng chính: giao tiếp giữa các task giống như đến 
phịng mạch
 Phần lớn thời gian BS đợi bệnh nhân 
 Hoặc bệnh nhân đợi BS, BS sẽ khám bệnh cho bệnh nhân 
nếu cả hai đều rãnh
 Hoặc lấy cái hẹn
35
Truyền thơng điệp (tt)

 Truyền thơng điệp là mơ hình tương tranh
 Cĩ thể là mơ hình của cả semaphore và CT giám sát
 Khơng chỉ cho đồng bộ hĩa cạnh tranh
 Truyền thơng điệp đồng bộ, khi bận các task khơng 
muốn bị gián đoạn
36
Truyền thơng điệp

 Trong phạm vi tasks, chúng ta cần:
a. Một cơ chế để cho phép một task biểu thị khi nào nĩ 
sẵn sàng nhận các thơng điệp
b. Các tasks cần cách ghi nhớ các task khác đang đợi nĩ 
nhận message và cĩ sự lựa chọn các message tiếp theo

 ðN: Khi message của một task được nhận bởi 
một task nào đĩ, thì sự truyền message được gọi 
là rendezvous
37
VD về Rendezvous
38
Tương tranh trong Java: Java thread 

 Khi chương trình Java thực thi hàm main() tức là 
tạo ra một luồng chính (main thread)

 Trong luồng main
 Cĩ thể tạo các luồng con
 Khi luồng main ngừng thực thi, chương trình sẽ kết 
thúc 

 Luồng cĩ thể được tạo ra bằng 2 cách:
 Tạo lớp dẫn xuất từ lớp Thread
 Tạo lớp hiện thực giao tiếp Runnable
39
Tương tranh trong Java (tt)

 VD
public class Mythread extends Thread{
private String data
public Mythread(String data){
this.data = data;
}
public void run(){
System.out.println(‘‘I am a thread!’’);
System.out.println(‘‘The data is:’’,data);
}
}
40
Tương tranh trong Java (tt)

 Tạo ra một thể hiện của lớp Thread (hoặc dẫn xuất của nĩ) 
và gọi phương thức start()

 Khi gọi myThread.start() một luồng mới tạo ra và chạy 
phương thức run() của myThread.
41
Tương tranh trong Java: Runnable

 Giao tiếp Runnable
 Ngồi tạo luồng bằng cách thừa kế từ lớp Thread, cũng 
cĩ một cách khác để tạo luồng trong Java
 Luồng cĩ thể tạo bằng cách tạo lớp mới hiện thực giao 
tiếp Runnable và định nghĩa phương thức: 
public abstract void run()
 ðiều này đặc biệt hữu ích nếu muốn để tạo ra một đối 
tượng Thread nhưng muốn sử dụng một lớp cơ sở khác 
Thread
42
Tương tranh trong Java: Runnable

 VD
43
Tương tranh trong Java: Runnable

 ðể tạo ra một luồng mới từ một đối tượng hiện thực giao 
tiếp Runnable, cần phải khởi tạo một đối tượng Thread
mới với đối tượng Runnable như đích của nĩ

 Khi gọi start() trên đối tượng luồng sẽ tạo ra một luồng 
mới và phương thức run() của đối tượng Runnable sẽ 
được thực hiện
44
Tương tranh trong Java: điều khiển
45
Tương tranh trong Java: điều khiển

 Khi một luồng giành quyền sử dụng CPU, nĩ sẽ thực hiện 
cho đến khi một sự kiện sau xuất hiện:
 Phương thức run() kết thúc
 Một luồng quyền ưu tiên cao hơn 
 Nĩ gọi phương thức sleep() hay yield() – nhượng bộ

 Khi gọi yield(), luồng đưa cho các luồng khác với cùng 
quyền ưu tiên cơ hội sử dụng CPU. Nếu khơng cĩ luồng 
nào khác cùng quyền ưu tiên tồn tại, luồng tiếp tục thực 
hiện

 Khi gọi sleep(), luồng ngủ trong một số mili-giây xác 
định, trong thời gian đĩ bất kỳ luồng nào khác cĩ thể sử 
dụng CPU
46
Tương tranh trong Java: điều khiển

 Phương thức join()
 Khi một luồng (A) gọi phương thức join() của một 
luồng nào đĩ (B), luồng hiện hành (A) sẽ bị khĩa chờ 
(blocked) cho đến khi luồng đĩ kết thúc (B).
47
ðồng bộ hĩa cạnh tranh với java

 Dùng từ khĩa synchronized trước tên các hàm khi 
định nghĩa để cấm các lớp khác thực thi các hàm 
này khi nĩ đang thực thi
class ManageBuf{
private int [100] buf;
public synchonized void deposit(int item){}
public synchonized void fetch(int item){}
}
48
ðồng bộ hĩa hợp tác với java

 Các phương thức wait(), notify() và notifyAll() 
được sử dụng để thĩa khĩa trên một đối tượng và 
thơng báo các luồng đang đợi chúng cĩ thể cĩ lại 
điều khiển

 wait() được gọi trong vịng lập

 notify() thơng báo cho thread đang chờ đợi là sự 
kiện đang đợi đã xãy ra

 notifyall() đánh thức các thread đang đợi là cĩ thể 
thực thi sau lệnh wait() 
49
ðồng bộ hĩa hợp tác với java: VD
50
ðồng bộ hĩa hợp tác với java: VD
51
SimpleThread
class SimpleThread extends Thread {
public SimpleThread(String str) {
super(str);
}
public void run() {
for (int i = 0; i < 10; i++) {
System.out.println(i + " " + getName());
try {
sleep((int)(Math.random() * 1000));
} catch (InterruptedException e) {}
}
System.out.println("DONE! " + getName());
}
}
52
TwoThreads
class TwoThreadsTest {
public static void main (String[] args) {
new SimpleThread("Jamaica").start();
new SimpleThread("Fiji").start();
}
}