Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
i
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
VÀ TRUYỀN THÔNG VÕ QUANG HUY XỬ LÝ SONG SONG
ÁP DỤNG ĐỐI VỚI MỘT SỐ BÀI TOÁN
TRONG LÝ THUYẾT ĐỒ THỊ
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01
TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
tới tập thể các thầy, cô giáo trong Trường Đại học Công nghệ thông tin và Truyền
thông; Viện công nghệ thông tin thuộc Viện khoa học và Công nghệ Việt Nam.
Đặc biệt Tôi xin gửi lời cảm ơn sâu sắc tới thầy giáo TS V Vinh Quang đã định
hướng và tận tình hướng dẫn tôi hoàn thành nội dung bản luận văn này.
Tôi xin cảm ơn các bạn đồng nghiệp và người thân đã động viên, giúp đỡ tôi
trong quá trình nghiên cứu và thực hiện luận văn.
Trong một khoảng thời gian ngắn, với kiến thức của bản thân còn hạn chế nên
luận văn không tránh khỏi những thiếu sót về mặt khoa học, tôi rất mong nhận được
những đóng góp ý kiến của các Thầy cô giáo cùng bạn bè để bản luận văn được
hoàn chỉnh hơn.
Xin trân trọng cảm ơn!
Thái Nguyên, ngày tháng năm 2013
Học viên V Quang Huy Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
iii
MỤC LỤC
LỜI CẢM ƠN i
MỤC LỤC iii
DANH MỤC CÁC HÌNH VẼ v
LỜI NÓI ĐẦU 1
Chƣơng 1: MỘT SỐ KIẾN THỨC CƠ BẢN VỀ XỬ LÝ SONG SONG 2
1.1 Khái niệm cơ bản về xử lý song song 2
3.1.1 Thuật toán sắp xếp đánh số 47
3.1.2 Thuật toán sắp xếp so sánh và đổi chỗ 48
3.1.3 Thuật toán sắp xếp MergeSort 51
3.2. Song song hóa một số thuật toán tối ưu trên đồ thị 54
3.2.1 Song song hóa thuật toán Kruskal 54
3.2.2 Song song hóa thuật toán Prim 56
3.2.3. Song song hóa thuật toán Floyd 59
3.2.4 Song song hóa thuật toán tô màu đồ thị 61
PHẦN KẾT LUẬN 63
TÀI LIỆU THAM KHẢO 64
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
v
DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Mô tả kiến trúc Von Neumann 2
Hình 1.2. Mô hình của kiến trúc SISD 6
Hình 1.3. Mô hình của kiến trúc SIMD 6
những bài toán nổi bật là các bài toán tối ưu trên mô hình lý thuyết đồ thị.
Với mục đích nghiên cứu vấn đề thiết kế các thuật toán song song dựa trên các
thuật toán tuần tự, luận văn đặt vấn đề nghiên cứu về lý thuyết xử lý song song và
ứng dụng trên một số bài toán trong mô hình đồ thị.
Cấu trúc của luận văn gồm phần mở đầu và 3 chương nội dung như sau
Phần mở đầu giới thiệu về hướng nghiên cứu và các mục đích nghiên cứu
Chương 1: luận văn trình bày các khái niệm về vấn đề xử lý song song, mô
hình máy tính song song, thuật toán song song cùng một số ngôn ngữ song song.
Đây là các khái niệm quan trọng làm cơ sở cho các vấn đề được đưa ra trong các
chương tiếp sau.
Chương 2: luận văn đưa ra các khái niệm cơ bản về lý thuyết đồ thị, mô hình
các bài toán tối ưu và mô tả các thuật toán tuần tự kinh điển giải các bài toán tương
ứng, đánh giá độ phức tạp của các thuật toán tuần tự.
Chương 3: Trên cơ sở các thuật toán đã trình bày trong chương 2 kết hợp với
lý thuyết xử lý song song, luận văn đưa ra một số hướng thiết kế các thuật toán song
song giải các bài toán tối ưu trên mô hình đồ thị, đánh giá độ phức tạp của các thuật
toán tương ứng.
Kèm theo luận văn là các phần mềm thử nghiệm các thuật toán tuần tự được
viết bằng ngôn ngữ C++.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
Chƣơng 1
MỘT SỐ KIẾN THỨC CƠ BẢN VỀ XỬ LÝ SONG SONG
1.1 Khái niệm cơ bản về xử lý song song
Trong những thập niên 60, nền tảng để thiết kế máy tính đều dựa trên mô hình
của John Von Neumann (Xem 0), với một đơn vị xử lý được nối với một vùng lưu
trữ làm bộ nhớ và tại một thời điểm chỉ có một lệnh được thực thi.
Mặc dù tốc độ xử lý của các BXL tăng nhiều trong những năm qua, nhưng do
giới hạn về vật lý nên khả năng tính toán của chúng không thể tăng mãi được. Điều
này dẫn tới là muốn tăng được khả năng tính toán của các hệ thống máy tính thì
đích cuối cùng là phải khai thác được khả năng xử lý song song của chúng.
Xét về mặt công nghệ, việc xây dựng, quản trị và ứng dụng một hệ thống xử lý
song song cũng không phải dễ dàng. Thông thường, chi phí phải trả cho việc quản
trị một hệ thống xử lý song song trong 1 năm còn cao hơn nhiều so với chi phí bỏ ra
để mua cả hệ thống. Ví dụ, một cluster có tốc độ tính toán 1 TeraFlops có chi phí
vào khoảng 100 nghìn USD, gần bằng chi phí phải trả cho một người quản trị hệ
thống trong một năm.
Nghiên cứu về xử lý song song vì vậy không chỉ mang ý nghĩa khoa học, mà
còn có ý nghĩa thực tiễn rất lớn. Việc nghiên cứu về xử lý song song, từ lý thuyết
cho đến ứng dụng, không chỉ giúp chúng ta nắm được nền tảng công nghệ, mà còn
giúp chúng ta nhìn thấy tiềm năng to lớn của xử lý song song trong công nghệ nói
riêng và các lĩnh vực kinh tế quốc dân nói chung.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
Định nghĩa: Xử lý song song là quá trình xử lý gồm nhiều tiến trình được
kích hoạt đồng thời và cùng tham gia giải quyết một vấn đề, nói chung là thực hiện
trên những hệ thống đa bộ xử lý.
Sự khác nhau giữa song song với tuần tự:
+ Trong tính toán tuần tự với một BXL thì mỗi thời điểm chỉ thực hiện được
một phép toán.
+ Trong tính toán song song thì một số BXL cùng kết hợp với nhau để giải
quyết cùng một vấn đề cho nên giảm được thời gian xử lý vì mỗi thời điểm có thể
có nhiều phép toán được thực hiện đồng thời.
Ba yếu tố chính dẫn đến việc xử lý song song:
1. Hiện nay giá thành của phần cứng (CPU) giảm mạnh, tạo điều kiện để xây
đơn dòng dữ liệu). Đây thực chất chính là kiến trúc Von Neumann.
2. SIMD (Single Instruction, Multiple Data Stream - Đơn dòng lệnh, đa dòng
dữ liệu). Kiến trúc này bao gồm các bộ xử lý kiểu vectơ cũng như các bộ xử lý song
song cực lớn (MPP).
3. Mô hình MISD (Multiple Instruction, Single Data Stream - Đa dòng lệnh,
đơn dòng dữ liệu).
4. Mô hình MIMD (Multiple Instruction, Multiple Data Stream - Đa dòng
lệnh, đa dòng dữ liệu). Kiến trúc này bao gồm các hệ đa vi xử lý truyền thống cũng
như các mạng máy trạm.
Sau đây chúng ta nghiên cứu chi tiết các mô hình trên:
1.2.1. Mô hình SISD: Đơn luồng lệnh, đơn luồng dữ liệu
Máy tính loại SISD chỉ có một CPU, ở mỗi thời điểm thực hiện một chỉ lệnh và chỉ
đọc, ghi một mục dữ liệu. Tất cả các máy tính SISD chỉ có một thanh ghi register được
gọi là bộ đếm chương trình (program counter) được sử dụng để nạp địa chỉ của lệnh tiếp
theo khi xử lý tuần tự và kết quả là thực hiện theo một thứ tự xác định của các câu lệnh.
Hình 1.2 mô tả hoạt động của máy tính theo mô hình SISD.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
Hình 1.2. Mô hình của kiến trúc SISD
Mô hình SISD còn được gọi là SPSD, đơn chương trình và đơn luồng dữ liệu.
Đây chính là mô hình máy tính truyền thống kiểu von Neumann.
1.2.2. Mô hình SIMD: Đơn luồng lệnh, đa luồng dữ liệu
điều khiển
Đơn vị điều khiển (CU)
Phần tử
xử lý 1
Tín hiệu
điều khiển
Phần tử
xử lý n
Phần tử
xử lý 2
. . .
Tín hiệu
điều khiển
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
1.2.3. Mô hình MISD: Đa luồng lệnh, đơn luồng dữ liệu
Máy tính loại MISD là ngược lại với SIMD. Máy tính MISD có thể thực hiện
nhiều chương trình (nhiều lệnh) trên cùng một mục dữ liệu, nên còn được gọi là
MPSD (đa chương trình, đơn luồng dữ liệu). Kiến trúc kiểu này có thể chia thành
hai nhóm:
Lớp các máy tính yêu cầu những đơn vị xử lý (PU) khác nhau có thể nhận
được những chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. Đây là kiến
trúc khó và hiện nay chưa có loại máy tính nào được sản xuất theo loại này.
Lớp các máy tính có các luồng dữ liệu được chuyển tuần tự theo dãy các
CPU liên tiếp. Đây là loại kiến trúc hình ống thực hiện xử lý theo vector thông qua
một dãy các bước, trong đó mỗi bước thực hiện một chức năng và sau đó chuyển
kết quả cho PU thực hiện bước tiếp theo. Hoạt động của máy tính theo kiến trúc loại
này giống như hệ tuần hoàn nên còn được gọi là hệ tâm thu.
.
.
.
Luồng lệnh
2
Luồng lệnh n
Luồng
dữ liệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8
thống. Đây là kiến trúc phức tạp nhất, nhưng nó là mô hình hỗ trợ xử lý song song
cao nhất và đã có nhiều máy tính được sản xuất theo kiến trúc này, ví dụ: BBN
Butterfly, Alliant FX, iSPC của Intel, v.v.
Mô hình của kiến trúc MIMD được mô tả như hình 1.5.
Hình 1.5. Mô hình của kiến trúc MIMD
Theo sự phân loại của Flynn thì có hai họ kiến trúc quan trọng cho các máy
tính song song đó là SIMD và MIMD. Những kiến trúc khác có thể xếp theo hai
mẫu đó. Mẫu hình các kiến trúc xử lý song song có thể phân chia như hình 1.6.
liệu 1
Luồng dữ
liệu 2
Luồng dữ
liệu n
MIMD
SIMD
Hybrid
MISD
Multiprocessor
Multicomputer
Data Flow Machine
Array Processor
Pipelined Vector Processor
Pipelined Vector Processor
Systolic Array
SIMD-MIMD
MIMD-SIMD
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9
Những kiến trúc khác nhau có thể tạo ra những khả năng khác nhau cho việc
xử lý song song. Ngay trong kiến trúc tuần tự chúng ta cũng có thể tận dụng đốc độ
cực nhanh của các BXL để thực hiện xử lý song song theo nguyên lý chia sẻ thời
gian và chia sẻ tài nguyên. Tất nhiên đối với những kiến trúc máy tính song song thì
mục đích chính là khai thác triệt để khả năng của kiến trúc song song để viết các
chương trình song song.
1.3 Khái niệm về thuật toán song song
Một trong các mục đích chính của xử lý song song là nghiên cứu và xây dựng
một dãy các thao tác
{ }
12
, , ,
n
T T T
, trong đó
1i
T
+
thực hiện sau khi
i
T
kết thúc.
3. Nguyên lý chia để trị: Chia bài toán thành những phần nhỏ hơn tương đối
độc lập với nhau và giải quyết chúng một cách song song.
1.3.2 Các cách tiếp cận trong thiết kế
Có ba cách tiếp cận để thiết kế thuật toán song song:
1. Thực hiện song song hoá những thuật toán tuần tự, biến đổi những cấu trúc
tuần tự để tận dụng được những khả năng song song tự nhiên của tất cả các thành
phần trong hệ thống xử lý.
2. Thiết kế những thuật toán song song mới phù hợp với kiến trúc song song.
3. Xây dựng những thuật toán song song từ những thuật toán song song đã
được xây dựng cho phù hợp với cấu hình tôpô và môi trường song song thực tế.
Như vậy, cách làm thông dụng là biến đổi các thuật toán tuần tự về song song,
hay chuyển từ một dạng song song về dạng song song phù hợp hơn sao vẫn bảo
toàn được tính tương đương trong tính toán. Do đó, khi biến đổi chúng ta cần trả lời
hai câu hỏi:
1. Kiến trúc nào phù hợp cho bài toán?
2. Những bài toán loại nào sẽ xử lý hiệu quả trong kiến trúc song song cho trước?
- thời gian truyền thông dữ liệu.
Thời gian tính toán
comp
t
được xác định giống như thuật toán tuần tự. Khi có
nhiều tiến trình tiến trình thực hiện đồng thời thì tính thời gian thực hiện của tiến
trình phức tạp nhất (thực hiện lâu nhất). Trong phân tích độ phức tạp tính toán,
chúng ta luôn giả thiết rằng, tất cả các bộ xử lý là giống nhau và thao tác cùng một
tốc độ như nhau. Đối với những cụm máy tính không thuần nhất thì điều này không
đảm bảo do vậy, việc đánh giá thời gian tính toán của những hệ như thế là rất phức tạp.
Thời gian truyền thông
comm
t
lại phụ thuộc vào kích cỡ của các thông điệp, vào
cấu hình kết nối mạng đường truyền và cả cách thức truyền tải thông điệp, v.v.
Công thức ước lượng thời gian truyền thông được xác định như sau:
atacomm startup d
t t n t= + *
Trong đó
+
startup
t
là thời gian cần thiết để gửi những thông điệp không phải là dữ liệu.
Nó bao gồm cả thời gian để đóng gói thông điệp ở nơi gửi và thời gian mở gói ở nơi
nhận. Để đơn giản chúng ta giả thiết thời gian này là hằng số.
+
atad
t
là thời gian cần thiết để chuyển một từ dữ liệu (một mục dữ liệu) từ nơi
2
n
+ 1
Thời gian truyền thông (ở bước 1 và 3):
ata ata
( ) ( )
2
comm startup d starup d
n
t t t t t= + * + +ata
2 ( 1)
2
startup d
n
tt= * + + *
Độ phức tạp tính toán là
()On
và độ phức tạp truyền thông cũng là
()On
,
do vậy độ phức tạp nói chung của thuật toán trên cũng là
()On
.
1.5. Phân tích và đánh giá thuật toán song song
Đánh giá thuật toán tuần tự có thể căn cứ chủ yếu vào thời gian thực hiện được
tính theo hàm của kích cỡ dữ liệu vào (input). Hàm này được gọi là độ phức tạp tính
cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số
lượng các bộ xử lý được phép sử dụng trong hệ thống.
Độ phức tạp thời gian là thước đo quan trọng nhất đánh giá mức độ hiệu quả
của thuật toán song song. Chúng ta giả thiết rằng mô hình tính toán có p bộ xử lý.
Nghĩa là mức độ song song là có giới hạn. Ngược lại, mức độ song song không bị
giới hạn khi số các bộ xử lý là không bị chặn.
Độ phức tạp thời gian của thuật toán song song sử dụng p bộ xử lý để giải một
bài toán có kích cỡ n là hàm f(n,p) xác định thời gian cực đại trôi qua giữa thời điểm
bắt đầu thực hiện thuật toán bởi một bộ xử lý và thời điểm kết thúc của các bộ xử lý
đối với bộ dữ liệu vào bất kỳ. Có hai loại thao tác khác nhau trong các thuật toán
song song:
1. Các phép toán cơ sở như +, -, *, /, AND, OR, v.v.
2. Các phép toán truyền dữ liệu trên các kênh truyền.
Độ phức tạp thời gian của thuật toán song song được xác định bởi số các phép
toán cơ sở và số các bước truyền tải dữ liệu giữa các bộ xử lý với nhau. Từ đó suy
ra, độ phức tạp thời gian của thuật toán song song không chỉ phụ thuộc vào mô hình
tính toán mà còn phụ thuộc vào số bộ xử lý được sử dụng.
Nói chung, chương trình tính toán song song thường bắt đầu bằng việc nhập
dữ liệu vào bộ nhớ và kích hoạt một phần tử xử lý. Mỗi bước tính toán, phần tử xử
lý này có thể đọc một số dữ liệu từ bộ nhớ, thực hiện một số phép toán cơ sở và ghi
kết quả vào bộ nhớ riêng hoặc bộ nhớ chung. Đồng thời mỗi bước tính toán, một
phần tử xử lý có thể kích hoạt một hay một số phần tử xử lý khác. Thực tế thì các
máy tính đều có số bộ xử lý là hữu hạn, nên những thuật toán song song không bị
giới hạn chỉ có nghĩa sử dụng khi chúng có thể chuyển đổi về thuật toán song song
bị giới hạn.
Có ba cách định nghĩa khái niệm liên quan đến độ phức tạp của thuật toán
song song:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
éù
êú
êú
êú
,
1 pp££
bộ xử lý thì sẽ có độ phức tạp thời gian là
( * )O p T
.
Định nghĩa 2 chỉ ra rằng khi số bộ xử lý được sử dụng giảm xuống trong một
phạm vi nhất định thì thuật toán tiếp tục làm việc nhưng thời gian thực hiện sẽ tăng lên.
Định nghĩa 3 khẳng định rằng có cách để cài đặt thuật toán song song khi số
các bộ xử lý được sử dụng bị giảm xuống.
Mức độ hiệu quả của thuật toán được thể hiện ở mức độ song song của thuật toán.
Mức độ song song của thuật toán là số lượng cực đại các phép toán độc lập có
thể thực hiện đồng thời ở mỗi thời điểm thực hiện của thuật toán.
Ký hiệu P(W) là độ song song của thuật toán, thì thuật toán hiệu quả giải để
giải bài toán có cỡ W là những thuật toán chỉ cần sử dụng nhiều nhất P(W) bộ xử lý.
Ngoài ra, để đánh giá được thuật toán song song chúng ta còn phải xét tới hệ
số gia tốc của nó.
Hệ số gia tốc của thuật toán song song sử dụng p bộ xử lý được xác định như sau:
/
p S p
S T T=
Trong đó
+
s
T
là thời gian thực hiện tính toán trên một bộ xử lý.
công việc và lập lịch được thực hiện ở giai đoạn dịch chương trình. Do vậy,
chương trình dịch loại này đòi hỏi phải rất hoàn hảo. Nhưng điều này khá
khó, bởi vì rất khó đánh giá được thời gian thực hiện chương trình, đặc biệt
là vấn đề lập lịch trước sẽ không thể thực hiện tối ưu được.
Nói chung, cho đến hiện nay khá nhiều chương trình dịch cho các máy tính
song song được xây dựng là cho ngôn ngữ lập trình Fortran.
Ví dụ chương trình dịch Paraphrase (do Kuck viết năm 1984) cho máy tính
Cedar Multiprocessor được phát triển ở Đại học Illinois, sử dụng đồ thị độc lập dữ
liệu để biến đổi chương trình Fortran từ dạng tuần tự sang dạng thích hợp để thực
hiện song song. Chương trình dịch này thực hiện theo hai giai đoạn:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
1. Giai đoạn 1: thực hiện biến đổi độc lập với máy tính, chuyển chƣơng
trình sang dạng trung gian thể hiện đƣợc dạng song song của mã
chƣơng trình.
2. Giai đoạn 2: thực hiện ánh xạ để chuyển từ dạng trung gian sang kiến
trúc song song của máy tính.
Chương trình dịch Paraphrase được sử dụng khá thành công trên máy tính
máy tính các bộ xử lý vector như Cray X/MP, khai thác tốt các khả năng song song
của chương trình Fortran.
Một ví dụ khác là chương trình dịch song song Fortran D (Fox xây dựng năm
1991, Hiranandani cải tiến 1992, 1993). Fortran D mở rộng của Fortran, trong đó
cho phép người lập trình xác định được sự phân rã dữ liệu của chương trình song
song. Hai vấn đề: ánh xạ sử dụng phương pháp gán mảng và ánh xạ sử dụng phân
rã, phân tán dữ liệu đã được giải quyết hiệu quả trong Fortran D.
Hệ điều hành là một chương trình làm nhiệm vụ phối hợp các hoạt động của
máy tính. Hệ điều hành thực hiện các chức chính sau:
Khởi động hệ thống
1.7. Một số ngôn ngữ lập trình song song
1.7.1. Lập trình song song với OCCAM
Occam là ngôn ngữ lập trình song song được Inmos Company phát triển năm
1988, mục đích chính là để thiết kế và cài đặt các chip được gọi là transputer.
Transputer là một máy tính một chip đơn với một bộ xử lý, bộ nhớ riêng và
bốn kênh vào/ra. Transputer có hai loại 16 bit hoặc 32 bit với tốc độ 10 triệu phép
tính /giây và mỗi kênh có khả năng truyền tải 10 megabit/giây.
Chương trình Occam thường nhiều tiến trình và chúng có thể được ánh xạ
sang một số các transputer bất kỳ để thực hiện song song và trao đổi dữ liệu với
nhau thông qua các kênh vào/ra. Nói chung số lượng các transputer trong mạng có
thể tăng, hoặc giảm và chương trình có thể thực hiện mà không cần có sự thay đổi
nào cả.
Occam là ngôn ngữ lập trình bậc cao, được sử dụng để lập trình cho những
hệ thống gồm nhiều máy tính kết nối với nhau, hoặc các hệ phân tán. Tuy nhiên, so
với các ngôn ngữ lập trình bậc cao khác thì Occam còn thiếu một số đặc tính như hỗ
trợ cơ chế đệ qui, định nghĩa kiểu dữ liệu hay con trỏ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
18
Trong Occam, một hành động có thể thực hiện song song được gọi là một
tiến trình và mỗi câu lệnh cần phải khai báo như một tiến trình. Khi lập trình chúng
ta phải chỉ rõ là các tiến trình sẽ kết hợp với nhau một cách tuần tự hay song song.
Các tiến trình cơ bản trong Occam
Có ba tiến trình nguyên thuỷ trong Occam:
Tiến trình gán: thay đổi giá trị của các biến
Tiến trình Input: nhận dữ liệu vào từ các kênh vào (cổng vào)
Tiến trình Output: gửi dữ liệu ra các kênh ra.
Ví dụ: Giả sử hai tiến trình A và B nhận các dữ liệu vào, tính bình phương của
chúng và gửi cho tiến trình C.
CHAN In1, In2:
CHAN Out1, Out2:
VAR Sum1, Sum2:
SEQ
Sum1:= 0
Sum2:= 0
PAR
Tiến trình thứ nhất
While TRUE
VAR Item1:
SEQ
In1 ? Item1
Sum1:= Sum1 + Item1
Out1 ! Sum1
Tiến trình thứ hai
While TRUE
VAR Item1:
SEQ
In2 ? Item2
Sum2:= Sum2 + Item2
Out2 ! Sum2
Sự trao đổi giữa các tiến trình
Trong ví dụ trên, các tiến trình không cần trao đổi với nhau vì mỗi tiến trình
đều sử dụng các biến cục bộ của riêng mình. Khi có nhiều tiến trình muốn trao đổi
dữ liệu với nhau thì phải trao đổi với nhau trên cùng một kênh truyền dữ liệu. Một
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
20
tiến trình gửi dữ liệu ra một kênh truyền và tiến trình kia nhận dữ liệu từ kênh đó.
Copyright: Tài liệu đại học ©