Bài Giảng

Xử Lý Song Song
Nguyễn Lê Anh
Phạm Thế Long


Hà Nội 2005

2


Tài liệu này được viết ra là để tỏ lòng biết ơn tới
tất cả các thầy giáo và thủ trưởng đại đội 186.

3


Lời nói đầu
Tài liệu được biên soạn dựa trên bài giảng cho sinh viên trường đại học Dân-Lập ĐôngĐô, học viện Kỹ Thuật Quân-Sự, trường đại học Sư Phạm Hà Nội.
Tác giả xin chân thành cảm ơn sự giúp đỡ rất cảm động của tập thể học viên lớp cao học
K16 Học Viện Kỹ Thuật Quân Sự, K15 trường đại học Sư Phạm. Có nhiều trình ví dụ
trong bài giảng này là do học viên của lớp viết ra. Tác giả xin bày tỏ sự cảm ơn tới anh
Trần Bộ, học viên K16 HVKTQS, đã kiểm tra và tu chỉnh lại nhiều chương trình trong
bài giảng này.
Chẳng thể tránh được sai sót, tác giả rất biết ơn mọi sự chỉ giáo của độc giả.
Mục tiêu. Bài giảng nhằm vào việc giúp cho độc giả hiểu được những nét chính sau:
- Nhận thấy sự khác biệt giữa thuật toán song song với tuần tự. Các bước cần thiết
để xây dựng một thuật toán song song giải một bài toán kỹ thuật.
- Khả năng lập trình và những điều có thể xảy ra khi chạy trình song song.
- Cung cấp một số trình minh họa giúp cho độc giả hiểu được đúng hơn cách dùng

các lệnh và nên dùng chúng trong những tình huống nào.
Đối tượng môn học. Triển khai công việc lập trình trên một mạng máy tính, trong đó
mỗi máy tính có thể có nhiều vi-xử-lý hoạt động song song.
Yêu cầu. Người học cần phải biết ngôn ngữ lập trình C, Java, và cấu trúc lôgích của một
máy tính nói riêng cũng như mạng máy tính nói chung.


Mục Lục
I. Kiến thức chuẩn bị
I.1 Sơ lược về ngôn ngữ lập trình C & C++

15
15

I.1.1. Lịch sử

15

I.1.2. Ngôn ngữ máy.

16

I.1.2-A

Cache và quá trình đọc-ghi dữ liệu.

16

I.1.2-B


Process & Thread

17

I.1.3. Trình dịch “Complier” & trình liên kết “Link”

21

I.1.3-A

Hai cách đặt tên.

21

I.1.3-B

Khối Lệnh và Hàm

21

I.1.3-C

Truyền tham số cho hàm

23

I.1.4. Vùng nhớ và Định Dạng.

26


I.1.4-A

Dạng là gì

26

I.1.4-B

Các dạng dữ liệu cơ bản.

31

I.1.4-C

dạng “extern”

32

I.1.4-D

Dạng hằng “constant”

34

I.1.4-E

Dạng “global”

34


I.1.4-F

Dạng “static”

35

I.1.5. Các tình huống hữu dụng.

37

I.1.5-A

Nhận biết thời gian & Tạo lập ngẫu nhiên

37

I.1.5-B

Nhận dữ liệu từ bàn phím & in ra màn hình.

37

I.1.5-C

Đọc và ghi dữ liệu ra file.

38

I.1.5-D


Kỹ thuật thao tác với con trỏ.

40

I.1.5-E

Xin cấp bộ nhớ ( cho C & cho C++)

44

I.1.5-F

Kỹ thuật khai báo mảng tĩnh.

45

I.1.5-G

Kỹ thuật khai báo mảng động.

46

I.1.5-H

Kỹ thuật thao tác với xâu ký tự, String.

48


I.2 Cấu trúc máy tính


50

I.2.1. Mô hình bộ nhớ phân tán.
I.2.1-A

50

Tiến trình (process)

50

I.2.2. Mô hình bộ nhớ tập trung.

51

I.2.2-A

Thread

52

I.2.3. Cấu trúc siêu máy tính.

53

I.3 Từ điển

55


II. Tính toán song-song

57

II.1

Tính trên nhiều máy.

57

II.2

Thuật toán song song.

64

II.2.1. Lựa chọn thuật toán để song song hóa.

64

II.2.2. Song song hóa một thuật toán tuần tự.

66

II.3

II.4

Vai trò thiết bị tính.


68

II.3.1-A

Thiết bị PRAM

68

II.3.1-B

Thiết bị CRCW

69

Giảm thiểu sự phụ thuộc tính toán.

70

II.4.1. Khái niệm về bước tính và số phép tính.

70

II.4.2. Phân rã phụ thuộc.

72

II.4.2-A
II.5

Khử phụ thuộc dạng a n  n a n  1   n .


Giải phương trình vi phân
II.5.1-A

Định lý tồn tại và duy nhất nghiệm

74
75
75

II.5.2. Thuật toán Runge-Kutta cổ điển (1895).

76

II.5.3. Thuật toán Runge-Kutta song song.

81

II.5.4. Thuật toán Runge-Kutta tổng quát.

86

II.5.4-A

Định lý hội tụ Henrici.

88

II.5.4-B


Cấp hội tụ địa phương

90

II.5.4-C

Cấp hội tụ toàn cục.

93


II.5.4-D

Một số sơ đồ Runge-Kutta thường dùng

95

II.5.5. Phương pháp song song giải hệ phương trình vi phân.
II.5.5-A

Thuật toán.

102

II.5.5-B

Quá trình phân chia công việc cho các vi xử lý.

104


III. Tính toán trên mạng.
III.1

102

Môi trường gửi-nhận MPI.

105
105

III.1.1. Khái niệm SPMD -- độc trình dùng bộ nhớ phân tán.

105

III.1.2. Khái niệm mạng ảo.

106

III.1.3. Cấu trúc một trình MPI.

106

III.1.4. Tuần tự hóa song song.

109

III.2

Nhu cầu đồng bộ


112

III.2.1. Đồng bộ ngầm định.

112

III.2.2. Đồng bộ cưỡng bức & Lỗi mất đồng bộ.

112

III.2.3. Mất đồng bộ khi dùng chung thiết bị không đồng bộ.

113

III.3

Các phương pháp gửi-nhận cơ bản.

115

III.3.1. Bản chất của việc truyền dữ liệu giữa 2 máy tính.

115

III.3.2. Mục tiêu của việc cải tiến quá trình gửi-nhận.

119

III.4


Các lệnh gửi-nhận dữ liệu cơ bản

III.4.1. Lệnh MPI_Send và MPI_Recv

122
122

III.4.1-A

Lệnh MPI_Send.

122

III.4.1-B

Lệnh MPI_Recv

125

III.4.2. Lệnh MPI_Ssend

126

III.4.3. Lệnh MPI_Bsend

131

III.4.4. Lệnh MPI_Rsend

135


III.5

Các lệnh Non-blocking

136

III.5.1. Lệnh MPI_Isend

137

III.5.2. Lệnh MPI_Irecv

145

7


III.5.3. Hiệu ứng chậm khi dùng lệnh non-blocking

152

III.6

Các lệnh Persistent

154

III.7


Lỗi do gửi nhận không đúng địa chỉ

156

III.8

Cơ chế gửi nhận cạnh tranh.

159

IV. Chiến lược phân việc cho các máy tính.

165

IV.1

Nhận việc theo “kế hoạch”

165

IV.2

Nhận việc thông qua “xếp-hàng”.

167

IV.2.1. Thuật toán.

167


IV.2.1-A

Sơ đồ lệnh thuật toán “xếp-hàng”

168

IV.2.1-B

Sơ đồ khối vòng lặp chính

169

IV.2.2. Ví dụ

169

IV.2.2-A

Phân tích thiết kế.

169

IV.2.2-B

Chuẩn bị dữ liệu.

171

IV.2.2-C


Thuật toán giao việc & nhận kết quả.

171

IV.2.2-D

Chương trình.

175

V. Deadlock

178

V.1

Khái niệm deadlock

178

V.2

Deadlock do “giao thoa” các đoạn lệnh gửi-nhận.

180

V.3

Deadlock do vùng đệm hệ thống quá nhỏ.


184

V.4

Deadlock xảy ra do xuất hiện “vòng lặp”

185

V.4.1. Vòng Send-Recv

186

V.4.2. Vòng Recv-Send.

186

V.5

Deadlock xảy ra do mất đồng bộ

188

V.5.1. Khái niệm đồng bộ và đường đồng mức.

188

V.5.2. Deadlock xảy ra do đường đồng mức bị xoắn.

189


8


V.5.2-A

Trường hợp Barrier-Bcast

190

V.5.2-B

Trường hợp Barrier-Reduce

191

V.5.2-C

Trường hợp Bcast-Reduce

192

V.5.3. Deadlock xảy ra do đường đồng mức bị cắt.

193

V.6

Deadlock xảy ra với các lệnh Non-Blocking.

197


V.7

Tránh Deadlock

201

V.7.1. Tránh Deadlock bằng cách dùng vùng đệm phụ.

201

V.7.2. Tránh Deadlock bằng tuần tự hóa.

201

V.7.3. Sử dụng lệnh non-blocking để tránh Deadlock.

204

V.7.4. Tránh deadlock bằng chế độ gửi nhận đồng thời.

206

V.7.5. Tránh Deadlock bằng thuật toán “đen-trắng”

208

VI. Mô hình tương-tác.

210


VI.1

Mô phỏng các hiện tượng tự nhiên bằng máy tính.

210

VI.2

Các kết nối cơ bản.

210

VI.2.1. Kết nối nhóm “Group”

212

VI.2.2. Mô hình “hướng tâm”.

213

VI.2.3. Mô hình đường ống thẳng và vòng

214

VI.2.4. Cấu trúc lưới hai chiều

217

VI.3


Mô hình kết nối qua các ví dụ.

219

b

VI.3.1. Tính tích phân f (x )dx .

219

a

VI.3.2. Phương trình Laplace

 2u
2x

0 .

221

VI.3.2-A

Lược đồ sai phân.

221

VI.3.2-B


Thiết kế thuật giải song song

222

VI.3.2-C

Sử dụng kết nối ảo.

224

VI.3.2-D

Phương án sử dụng lệnh MPI_Sendrecv.

225
9


VI.3.3. Phương trình dao động

 2u
t 2

 2

 2u
2x

.


227

VI.3.3-A

Lược đồ sai phân.

227

VI.3.3-B

Trình tuần tự

229

VI.3.3-C

Thiết kế thuật giải song song

230

VI.3.3-D

Chương trình và kết quả chạy trình

233

 2u

2 
 2

2  u  u 



VI.3.4. Giải phương trình dao động 2
 x 2 y 2  .
t



236

VI.3.4-A

Lược đồ sai phân.

236

VI.3.4-B

Thiết kế thuật giải song song.

238

VI.3.4-C

Chương trình.

240


VI.3.5. Giải phương trình truyền nhiệt

  2u  2u 
u



 2 x 2 y  .
t



243

VI.3.5-A

Lược đồ sai phân.

243

VI.3.5-B

Trình tuần tự.

247

VI.3.5-C

Thiết kế giải thuật song song.


248

VI.3.5-D

Trình Song-Song.

252

VII. Nguyên lý các trình song song dùng chung bộ nhớ.
VII.1

Khái niệm Kernel, Process & Thread.

254
254

VII.1.1. Process

254

VII.1.2. Thread

255

VII.1.3. Lệnh Atomic.

257

VII.2


Tạo lập thread.

257

VII.2.1. Thiết lập Thuộc tính cho thread.

257

VII.2.2. Tạo lập, Giao nhiệm vụ & Truyền tham số cho thread.

258

VII.2.2-A

Các bước cơ bản.

258

VII.2.2-B

Ví dụ về tạo lập & truyền dữ liệu cho thread.

259

VII.2.2-C

Tạo mảng thread

266
10



VII.2.3. Sự khác nhau giữa thread và trình con.

267

VII.2.3-A

Thread là trình con được kích hoạt để chạy song song.

267

VII.2.3-B

Thread, Trình con, và Màn hình.

269

VII.3

Hiệu ứng rượt đuổi & khái niệm vùng lệnh tuần tự.

271

VII.3.1. Nghịch lý “Bán-Vé”.

271

VII.3.1-A


Bài toán và trình mô phỏng.

271

VII.3.1-B

Phân tích nghịch lý.

272

VII.3.1-C

Hiệu ứng rượt đuổi “race”.

272

VII.3.1-D

Khái niệm vùng lệnh tuần tự CS (critical secsion).

272

VII.3.2. Mutex.

276

VII.3.2-A

Định nghĩa Mutex.


276

VII.3.2-B

Tạo lập Mutex

277

VII.3.2-C

Lời giải cho bài toán “Bán Vé”

277

VII.3.2-D

Ví dụ.

279

VIII. Điều phối hoạt động của các threads.
VIII.1

283

Chiến lược phân việc

283

VIII.1.1. Thuật toán cân bằng.


283

VIII.1.2. Thuật toán “cạnh tranh”

286

VIII.2

Thuật toán Mutex.

289

VIII.2.1. Sơ lược lịch sử Mutex.

289

VIII.2.2. Thuật toán Test & Set.

290

VIII.2.2-A Điều phối hoạt động của 2 thread.
VIII.2.3. Thuật toán Bakery.

290
293

VIII.2.3-A Mô tả thuật toán

293


VIII.2.3-B Trình mô phỏng

295

VIII.2.4. Thuật toán Eisenberg-McGuire (1972).

297

VIII.2.4-A Mô tả thuật toán

297

VIII.2.4-B Trình mô phỏng.

298
11


VIII.2.5. Thuật toán Edsger Dijkstra's.
VIII.2.5-A Mô tả thuật toán.
VIII.3

Thread Deadlock.

VIII.3.1. Khái niệm Deadlock và Stavation.

300
300
302

302

VIII.3.1-A Deadlock do dùng chung thiết bị tuần tự.

302

VIII.3.2. Bữa ăn tối của 5 triết gia (Dining Philosophers).

306

VIII.4

Biến điều kiện & Qui trình đồng bộ hóa thread.

311

VIII.4.1. Qui trình thiết lập đồng bộ giữa các thread.

312

VIII.4.2. Deadlock do bị mất tín hiệu đồng bộ.

316

VIII.4.3. Biện pháp tránh mất tín hiệu đồng bộ.

317

VIII.4.4. Deadlock do vi phạm lôgích thời gian.


320

VIII.5

Đèn hiệu – Semaphore.

323

VIII.5.1. Khái niệm về đèn hiệu Semaphore.

323

VIII.5.2. Lĩnh vực sử dụng đèn hiệu Semaphore.

323

VIII.5.3. Sơ đồ khối và trình mô phỏng Semaphore

324

VIII.5.4. Một vài ví dụ kinh điển về sử dụng Semaphore

326

VIII.5.4-A Bài toán “ô-tô qua cầu”

327

VIII.5.4-B Bài toán “Khuyến mại thuốc lá”.


328

VIII.5.5. Khả năng deadlock khi dùng Semaphore.

330

VIII.6

Một số bài toán điều phối kinh điển

VIII.6.1. Bài toán sản-xuất & tiêu-thụ (Producer & Consumer )

332
332

VIII.6.1-A Phân tích sự kiện

332

VIII.6.1-B Sơ đồ khối

333

VIII.6.1-C Trình mô phỏng.

335

VIII.6.2. Bài toán Đọc & Ghi (Readers & Writers)

337


VIII.6.2-A Phân tích sự kiện

337

VIII.6.2-B Trình mô phỏng

338

12


IX. OpenMP.

343

IX.1

Khái niệm về vùng song song & thread.

344

IX.2

Các sơ đồ song song cơ bản.

348

IX.2.1. Giao nhiệm vụ cho từng thread “parallel section”.


349

IX.2.2. Command-Sharing “chia xẻ thuật toán”.

352

IX.2.3. Work-sharing “chia xẻ công việc”.

355

IX.3

Song song lồng nhau.

360

IX.4

Lựa chọn phương án song song hóa (chưa xong)

366

IX.5

Hiệu ứng Race & Deadlock trong OpenMP.

372

IX.5.1. Nghịch lý bán vé


373

IX.5.2. Bữa ăn tối của 5 triết gia

374

IX.5.3. Tán tỉnh

376

IX.6

Tránh hiệu ứng Race.

377

IX.7

Giải phương trình vi phân.

382

IX.7.1. Thuật toán song song Hammer-Hollingsworth.
IX.7.2. Giải phương trình

 2u
t 2




2

 2u
2x

382

.

384

IX.7.3. Chỉ thị đồng bộ “#pragma omp barrier”.
IX.8

385

Ví dụ.

X. Công nghệ tổ hợp

388
390

X.1

MPI & Thread.

390

X.2


MPI & OpenMP.

395

XI. Phụ lục.

396

XI.1

Process & Thread trong Microsoft Windows.

396

XI.2

Tạo lập thread.

396
13


XI.3

Vùng CS (Critical Secsion).

399

XI.4


Đồng bộ hóa hoạt động của các thread.

401

XI.4.1. Bài toán mô phỏng chất khí lý tưởng

401

XI.4.2. Bài toán sản-xuất & tiêu-thụ (Producer & Consumer )

404

XI.5

Java thread.

406

XI.5.1. Hiện tượng Race.

406

XI.5.1-A

Nghịch lý “Bán Vé”.

406

XI.5.1-B


Hiện tượng Race khi không có đồng bộ.

407

XI.5.2. Đồng bộ hóa thread.
XI.5.2-A

408

Lời giải cho nghịch lý “Bán Vé”.

410

XI.5.3. Hiện tượng deadlock.

XI.6

411

XI.5.3-A

“Tán Tỉnh”.

411

XI.5.3-B

Deadlock khi đồng bộ trình con.


413

Gửi nhận dữ liệu trên mạng Internet

415

XII. Tài liệu tham khảo

419

XIII. Câu hỏi thi

421

14


I. Kiến thức chuẩn bị
I.1 Sơ lược1 về ngôn ngữ lập trình C & C++
I.1.1. Lịch sử
Ngôn ngữ lập trình C do Kernighan và Ritchie (phòng thí nghiệm Bell Lab) tạo ra vào
đầu những năm 1970, với tên gọi là K&R. C được tạo ra là để phục vụ cho việc lập trình
trên hệ điều hành UNIX, về sau được mở rộng ra cho các hệ điều hành khác. ANSI C là
phiên bản C do viện chuẩn quốc gia Hoa Kỳ (American National Standards Institute) tạo
ra.
Ngôn ngữ C++ do Bjarne Stroustrup (phòng thí nghiệm Bell Lab) tạo ra vào đầu những
năm 80. Nó được tạo ra để kết hợp các đặc tính tốt của C (như khả năng can thiệp được
vào các thiết bị phần cứng của máy tính) với Simula-67 (khả năng hướng đối tượng) và
Algol-68 (khả năng chạy trình từng phần).
C và C++ được tạo ra để phục vụ cho các mục đích khác nhau. Ngôn ngữ C thích hợp

cho kiểu tư duy lập trình “dưới-lên-trên”. Đó là kiểu lập trình: tạo ra các trình con trước
rồi sử dụng nó để tạo ra các chương trình phức tạp hơn. Ngôn ngữ lập trình C++ thì
thích hợp cho kiểu tư duy lập trình “trên-xuống-dưới”. Quá trình lập trình bắt đầu từ
việc phân tích bài toán thành các nhiệm vụ và sử dụng chúng để giải quyết bài toán đặt
ra. Các nhiệm vụ lại được phân rã tiếp thành các nhiệm vụ nhỏ hơn...
Sau đây là tóm lược (chỉ để phục vụ cho bài giảng) về C & C++. Việc làm này là không
dễ, bởi các khái niệm cơ bản thường đan xen vào với nhau khó có thể phân định rạch ròi
cái nào cần phải được định nghĩa trước và cái nào sau; việc làm này là cũng không dễ,
bởi mỗi trình dịch lại sử dụng các thư viện khác nhau.
Để cho đơn giản, các trình ví dụ có trong bài giảng này được viết bằng Visual C 6.0 của
Microsoft (có sử dụng thêm một số thư viện cần thiết để dịch và chạy trình).
Để thuận lợi cho công việc, đề nghị độc giả dịch và chạy chương trình đơn giản nhất,
trình “Hello World” sau đây.
#include <iostream.h>
int main()
{ cout << "Hello World";
return 0;
}
1

Những gì được trình bày ở đây chỉ nhằm giúp độc giả nhớ lại ngôn ngữ C phục vụ cho việc đọc bài giảng.


Ý nghĩa của việc chạy thành công trình “Hello World” không chỉ ở chỗ nó cho thấy hệ
thống trình dịch C++ (của độc giả) đã được cài đặt đúng, mà quan trọng hơn, nó – bằng
cách chèn vào chỗ cần thiết trong chương trình dòng lệnh cout << “Hello World”; – chỉ
cho chúng ta một cách để biết được trình đang chạy qua lệnh nào!?
I.1.2. Ngôn ngữ máy.
I.1.2.A


Cache và quá trình đọc-ghi dữ liệu.

Máy tính được tạo ra từ 2 phần cơ bản:
CPU – bộ xử lý trung tâm: nó có khả năng truy cập vào tất cả các “ngóch ngách” của
máy tính để gửi và nhận dữ liệu, nó có một bộ phận hỗ trợ thực hiện các phép toán đơn
giản như + - * / ... b)
RAM – bộ nhớ: nơi đây người ta lưu qui trình tính toán cùng với dữ liệu cần cho nó.
Bộ nhớ, RAM, gồm các byte nhớ – còn được gọi là ô nhớ 2 – kết hợp lại với nhau. Để
phân biệt, chúng được đánh số liên tiếp tăng dần từ 0.
Muốn đọc hoặc ghi dữ liệu ra các ô nhớ này, thì địa chỉ của chúng phải được tải vào các
thanh ghi; nếu thanh ghi 16 bit thì ta có thể qui chiếu tới 216 ô nhớ khác nhau, và nếu nó
là 32 bit thì 2 32 ô nhớ khác nhau3. Địa chỉ của một ô nhớ gồm 2 phần, phần thứ nhất gọi
là “segment” và phần thứ hai gọi là “offset”. “segment” lưu địa chỉ đầu tiên của vùng
nhớ cần qui chiếu đến, và “offset” là địa chỉ tương đối kể từ “segment”. Tùy theo cấu
trúc của hệ thống qui chiếu địa chỉ, mà địa chỉ vật lý của ô nhớ được qui về “segment”
và “offset”. Nếu địa chỉ vật lý có dạng 2  seg  offset và các thanh ghi seg, offset đều
là 2n bit thì dung lượng bộ nhớ mà CPU có thể quản lý được là 2n (2   1) .
Quá trình ghi và đọc dữ liệu không hề đơn giản, và thời gian tiêu tốn do tín hiệu xung
điện mang các dữ liệu ấy phải chạy một đoạn đường xa từ CPU ra đến RAM là chủ yếu
– cho dù dòng điện chạy với tốc độ ánh sáng, là tốc độ nhanh nhất có thể. Để vi xử lý
không phải chờ dữ liệu đi lại, người ta thiết kế ra một vùng nhớ phụ ở ngay trong CPU,
và gọi nó là “cache”. “Cache” lưu giữ cả địa chỉ ô nhớ và dữ liệu có trong ô nhớ ấy. Một
khi CPU cần dữ liệu thì “cache” sẽ đọc/ghi chúng từ RAM vào để cung cấp cho CPU.
Như vậy, CPU chỉ cần tiếp xúc với “cache” mà không cần phải truy cập vào RAM. Quá
trình “cache” đọc dữ liệu có thể xảy ra trước khi CPU cần đến chúng, do “cache” có thể
phát hiện được các lệnh truy cập bộ nhớ sớm hơn CPU, và quá trình cache ghi dữ liệu ra
RAM có thể là sau, cho dù CPU đã thực hiện xong lệnh ghi dữ liệu, và đang đi thực hiện
các lệnh tiếp theo. Với cơ chế này hiệu quả tính toán chung tăng lên rất nhiều. Hiệu quả
2


mỗi ô có thể nhớ được 256 trạng thái, đánh số từ 0..255.
một phần của chúng được để ở đĩa cứng. Khi cần các dữ liệu ở đĩa cứng này, chúng sẽ được chuyển vào
RAM.
3

16


tính toán còn được tăng lên do việc các ô nhớ thường được dùng đi dùng lại, và như vậy
thì giao tiếp của CPU với bộ nhớ trên thực tế chỉ là giao tiếp với “cache”. Ngoài ra chiến
lược “caching”, tức là chiến lược lưu giữ tạm thời dữ liệu cũng được người ta nghiên
cứu để tăng khả năng mà “cache” có thể cung cấp được dữ liệu cho CPU. Ví dụ như mỗi
lần “cache” đọc/ghi dữ liệu, nó đọc/ghi cả một vùng liên tiếp của RAM, mà dữ liệu tính
toán thì thường là các mảng và được lưu dưới dạng các byte liên tiếp!.
Quá trình CPU giao tiếp với “cache” và “cache” giao tiếp với RAM là các quá trình vận
hành tương đối độc lập. Điều này, một mặt làm cho hiệu quả tính toán tăng lên, một mặt
khác có thể gây ra sự phiền toái. Sự phiền toái xảy ra do RAM là vùng nhớ dùng chung
và có thể có nhiều thiết bị cùng một lúc truy cập vào. Vậy một khi CPU ghi dữ liệu ra
RAM mà dữ liệu lại không ra ngay, thì các thiết bị khác đọc được dữ liệu nhưng lại là dữ
liệu cũ không phải là thứ cần thiết. Để cấm không cho các thiết bị khác truy cập vào một
ô nhớ khi lệnh đọc/ghi dữ liệu của CPU đang được thực hiện, thì “cache” phải chuyển
tải dữ liệu ngay ra RAM và máy tính phải ở vào trạng thái đặc biệt và trạng thái này
được gọi là “lock”, khóa ô nhớ.
Đối với máy tính có nhiều vi xử lý cùng dùng chung một vùng nhớ RAM, lập trình viên
phải lưu tâm đến, không chỉ cơ chế giao tiếp gián tiếp qua “cache” của CPU và RAM,
mà cả nguy cơ các vi xử lý cùng lúc truy cập vào một ô nhớ khi nó đang ghi dữ liệu.
I.1.2.B

Process & Thread


Vào thời kỳ đầu những năm 70, bộ lệnh (assembly) cho máy tính rất đơn giản. Nó thậm
chí chẳng có cả lệnh “nhảy” jump, hay lệnh gọi trình con. Vi-xử-lý chỉ làm theo các lệnh
được hiện ra ở thanh ghi mã lệnh IP. Mà các con số hiện ra trên IP thì cứ tuần tự tăng
dần, mỗi lần 1 đơn vị. Muốn lệnh tiếp theo phải thực hiện là một lệnh nào đó ở vị trí
khác, không phải nằm ngay sau lệnh vừa thực hiện, thì lập trình viên phải đánh lừa vi xử
lý. Cụ thể là họ phải xác định được vị trí của lệnh này, sau đấy “nhét” nó vào thanh IP và
“chờ” cho vi-xử-lý bị mắc lỡm4. Lệnh gọi một trình con thì phức tạp hơn một tí, bởi vì
sau khi kết thúc hoạt động của trình con thì lệnh tiếp theo phải là lệnh tiếp theo lệnh đã
gọi nó.
Ngày nay bộ lệnh (assembly) cho máy tính đã thay đổi nhiều. Quá trình tích lũy kinh
nghiệm tin học trong 50 năm đã đúc kết lại và hình thành ra các nguyên lý về cấu trúc
máy tính và lập trình, các nguyên lý này được “thể hiện” ra ở các lệnh assembly. Các thủ
tục như chuyển điều khiển và gọi trình con đã và chỉ còn là các lệnh đơn giản. Cấu trúc
của một chương trình cũng có thay đổi. Dữ liệu được phân ra làm nhiều loại như:
1. Dữ liệu tĩnh (gọi đơn giản là dữ liệu) là vùng nhớ cố định nơi lưu giữ các biến
(global) dùng cho toàn bộ chương trình và các trình con.
4

Những kiến thức này do các thày giáo Nguyễn Xuân My, Nguyễn Vy (dạy đại đội 186) dạy..

17


2. Stack là vùng nhớ có thể dùng đi dùng lại nhiều lần.
3. Heap là vùng nhớ chỉ gồm các byte không có định dạng.
Mã lệnh của chương trình được lưu vào một vùng, gồm các byte liên tiếp, được gọi là
segment mã lệnh (cseg segment). Dữ liệu được để vào một segment (dseg segment) nằm
liền sát với segment mã lệnh. Các biến (tức vùng nhớ có độ dài nhất định nhưng nội
dung thì có thể thay đổi) được lưu vào vùng nhớ có tên là stack. Đó là một vùng nhớ mà
cứ mỗi khi có một biến được khai báo thì stack lại tăng thêm một “ngăn” cho nó.

Ví dụ về trình assembly
assume
ss:sseg
cseg
start:
mov
mov
mov
mov
int
mov
int
cseg

Địa chỉ vật lý

cs:cseg, ds:dseg,
segment
ax, dseg
ds, ax
dx, offset msg
ah, 09h
21h
ax, 4C00h
21h
ends

dseg
segment
byte

msg
db
'Hello!',0Dh,0Ah,'$'
dseg
ends
sseg
db
sseg

segment
stack
100h dup(?)
ends

end start

Ngay sau vùng dữ liệu là một khoảng trống được gọi là heap. Người ta thường dùng
chúng để nhớ một “lô” nào đó các byte, còn địa chỉ (nơi để “lô” byte ấy) thì được để vào
một biến nào đó (trong stack).
Như vậy, mỗi một chương trình được phân ra làm các phần chính như vùng mã lệnh,
vùng dữ liệu, vùng stack, vùng heap, và còn một vùng nữa để giao tiếp với hệ điều hành

18


(ví dụ như để đọc và ghi dữ liệu ra file). Các yếu tố này lập thành một thể thống nhất và
được gọi là tiến trình (process).
Chương trình, kể cả khi nó đã được dịch ra lệnh máy, cũng chỉ là phần mã lệnh (được để
vào vùng mã lệnh), trong khi tiến trình, tức process, thì bao gồm mã lệnh và các yếu tố
phục vụ cho nó hoạt động (như nói ở phần trước).

Một trình con chỉ là một đoạn mã lệnh của trình chính (nhưng được dùng nhiều lần), vì
vậy mã lệnh của nó cũng được để ngay ở vùng segment mã lệnh. Trước khi gọi, các giá
trị cần truyền cho trình con được nhét vào stack – trình con sẽ vào stack để lấy chúng ra.
Mỗi trình con có thể có biến riêng, vì thế chúng cũng có stack và stack của nó là stack
của trình chính – trình con chỉ dùng nhờ (vì đây là một quá trình tuần tự, khi trình con
chạy thì trình chính ngừng hoạt động). Phần stack mà trình con dùng “nhờ” sẽ bị mất đi
khi trình con kết thúc hoạt động.
Việc phân bổ chi tiết các vùng nhớ được trình dịch thực hiện. Lập trình viên chỉ việc
khai báo các segment với các nội dung cần thiết.
Đối với trường hợp các trình con có thể được kích hoạt để hoạt động song song với nhau
(và song song với cả trình chính), thì trình dịch phải bố trí cho chúng vùng stack hoàn
toàn riêng biệt (không thể sử dụng “nhờ” được nữa!).

Các trình con loại này được gọi là thread. Giống với trình con, các thread có thể truy cập
(để đọc và ghi) các biến dữ liệu chung ở vùng (data segment); và khác với các trình con
là chúng có thể tranh nhau ghi và đọc vào các ô nhớ chung này.
Bảng liệt kê sự khác nhau giữa thread và process
19


thread

process

thread không có data segment & heap

có code segment, data segment, stack
segment, heap & một số phần I/O nữa

thread tồn tại trong process


mỗi process có ít nhất một thread

có thể có nhiều thread trong một thread trong cùng một process dùng
process, và main() là một trong số đó
chung nhau code/data/heap và I/O; nhưng
chúng có stack segment, registers riêng.
tạo ra một thread mất ít thời gian

tạo ra một process mất nhiều thời gian

chuyển đổi nhanh

chuyển đổi chậm

khi thread kết thúc hoạt động vùng bộ khi process kết thúc hoạt động, tất cả các
nhớ stack của nó được giải phóng
thread kết thúc theo.
Hình vẽ sau mô tả vị trí stack của các thread trong cùng một process. Các stack đều nằm
trong vùng stack của process (trình chính), nhưng nằm ở những vị trí khác nhau. Vì vậy
mỗi thread phải nhớ lấy địa chỉ vùng stack của mình.

20


I.1.3. Trình dịch “Complier” & trình liên kết “Link”
I.1.3.A

Hai cách đặt tên.


Có thể dùng một số byte liên tiếp – “vùng nhớ” – để nhớ một lượng thông in nào đó; và
để tìm lại được nó với mục đích đọc/sửa thông tin ấy (truy cập hay qui chiếu), chúng ta
cần phải biết là ta đã dùng bao nhiêu byte vào việc này – dung lượng, và địa chỉ vùng
nhớ nơi đã lưu chúng (địa chỉ vật lý của byte đầu tiên).
Việc làm phức tạp này có thể được thực hiện đơn giản bằng một trong 2 cách sau:
Đặt cho “vùng nhớ” ấy một cái tên – tên này vừa phải cho biết địa chỉ vật lý, vừa phải
cho biết dung lượng, và vừa phải cho biết dạng của “vùng nhớ”.
Chứa địa chỉ của byte đầu tiên của “vùng nhớ” vào một nơi và đặt tên cho chỗ ấy – con
trỏ (pointer – luôn chiếm 4 byte). Mỗi khi cần truy cập đến vùng nhớ ta sử dụng tên con
trỏ để tìm thấy địa chỉ của “vùng nhớ”. Con trỏ vừa phải cho biết địa chỉ vật lý của vùng
nhớ, vừa phải cho biết độ lớn của nó, và vừa phải cho biết nó thuộc dạng nào.
Cách thứ nhất, về bản chất, đi kèm với mỗi tên là một con trỏ (ký hiệu là &tên) – trỏ
vào địa chỉ byte đầu tiên của vùng nhớ. Cách thứ hai, những gì chứa trong pointer có thể
thay đổi. Chính vì vậy, bằng cách thay đổi giá trị con trỏ ta có thể quy chiếu nó đến một
vùng nhớ khác.
Trình dịch “Compiler” và trình liên kết “Link” quản lý việc tương ứng các tên tới các
vùng nhớ cụ thể. Việc của chúng ta là khai báo5.
Định nghĩa
Mảng là tên một số “vùng nhớ” liên tiếp được đánh theo chỉ số. Ví dụ như a 0 , a 1 ,.., a 19
-- là mảng a , hay b 0,0 ,b 0,1 ,.., b19,49 -- là mảng b ... Các “vùng nhớ” trong cùng một
mảng đều phải thuộc cùng một định dạng.
Ví dụ khai báo “int a[20];” hàm ý: với mỗi chỉ số k trong khoảng từ “0..19” thì “a[k]” là
một số nguyên. Cũng vậy, khai báo “float b[20][50];” hàm ý: với mỗi chỉ số 0k19 và
với mỗi chỉ số 0h49 thì “b[k,h]” là một số thực.

I.1.3.B

Khối Lệnh và Hàm

Mỗi lệnh của C & C++ đều được tạo ra từ ngôn ngữ máy; và chúng có tên để gọi. Ngoặc

{...} được dùng để tạo ra khối (gồm nhiều lệnh ở trong) – được coi như một lệnh. Một
5

Ví dụ “int x = 210;” là báo cho Compiler biết về nhu cầu sử dụng 4 byte liên tiếp để ghi vào đấy số nguyên 210.

21


khối lệnh được dùng nhiều lần thì người ta đặt tên cho nó và gọi nó là hàm.
Tên hàm khác với tên biến ở chỗ tên hàm đi kèm với ngoặc (...). Như vậy, A thì là biến,
mà A(...) thì là hàm. Mỗi khi gặp tên hàm này, CPU lần ngược trở lại để tìm khúc lệnh
tương ứng và thực hiện. Mỗi hàm được coi là một lệnh.
Một hàm và một khối lệnh còn khác nhau ở chỗ, hàm được mô tả một cách hình thức từ
trước với các biến hình thức. Các biến hình thức là các ô nhớ có tên nhưng chưa có giá
trị, giá trị của nó sẽ tùy thuộc vào nhu cầu cụ thể và được gán sau.
Các biến hình thức được khai báo trong (...) của hàm khi mô tả hàm, và nó sẽ được gán
giá trị trực tiếp, hay nhận giá trị từ một biến nào đó.
Ví dụ như trình sau
double power(double X, unsigned n)
{
double Y = 1.0;
for(unsigned i = 0; i < n; i++) Y *= X;
return(Y);
}

sử dụng hai biến hình thức X, n để tính Y=Xn.
Khi lập trình (viết ra các dòng lệnh trên) các biến X và n đều chưa có giá trị. Chúng
được dùng trong khối lệnh trên chỉ thể hiện thuật toán tính ra Y=Xn mà thôi.
Để biết được giá trị 210 chúng ta đưa ra lời gọi power (2,10);
Kết hợp lại ta có

#include <iostream.h>
double power(double X, unsigned n)
{
double Y = 1.0;
for(unsigned i = 0; i < n; i++) Y *= X;
return(Y);
}
void main()
{ cout << power (2,10) <<"\n";
}

Quá trình chạy trình được bắt đầu từ dòng lệnh main(); và tất nhiên trong một trình C thì
có và chỉ có một dòng lệnh main(); mà thôi.
Nhiều khi hàm chỉ đơn thuần là một số thao tác trên các dữ liệu, kết quả tính là sự thay
đổi nội dung của các ô dữ liệu này.
Trong trình sau đây, hàm power() chỉ làm một số thao tác trên các ô chứa dữ liệu Y, X, n.
Kết quả của việc làm này là tính Y=Xn.

22


#include <iostream.h>
double Y =1.0, X=2; unsigned n=10;
void power()
{
for(unsigned i = 0; i < n; i++) Y *= X;
}
void main()
{
power ();

cout << Y <<"\n";
}

Hàm có thể tự gọi lại nó. Trong trình ví dụ như trình sau đây
#include <iostream.h>
int fib(int num)
/* Fibonacci value of a number */
{
switch(num) {
case 0:
return(0);
break;
case 1:
return(1);
break;
default:
/* Including recursive calls */
return(fib(num - 1) + fib(num - 2));
break;
}
}
void main()
{
cout << fib(10) <<"\n";
}

giá trị fib(n) = fib(n - 1) + fib(n- 2) với fib(0) = 0, và fib(1) = 1;

I.1.3.C


Truyền tham số cho hàm

Có hai cách truyền thông số cho hàm: cách thứ nhất là truyền trực tiếp giá trị, và cách
thứ hai là truyền địa chỉ nơi lưu giữ giá trị cần truyền. Chúng ta cùng theo dõi hai trình
sau đây để thấy sự khác nhau của chúng.
Trình này thực hiện sai ý định

Trình này thực hiện đúng ý định

23


#include <iostream.h>
void sw(int x, int y)
{
int z;
z=x; x=y; y=z;
}
void main()
{
int x=7, y=5;
cout << "x="<sw(x,y);
cout << "x="<}

#include <iostream.h>
void sw(int *x, int* y)
{
int z;

z=*x; *x=*y; *y=z;
}
void main()
{
int x=7, y=5;
cout <<"x="<< x <<" y="<< y <<"\n";
sw(&x,&y);
cout <<"x="<< x <<" y="<< y <<"\n";
}

x=7 y=5

x=7 y=5

x=7 y=5

x=5 y=7

Các hàm sw() được viết ra với mục đích thực hiện việc trao đổi giá trị của 2 biến x, y
cho nhau. Tuy nhiên kết quả thực hiện của chúng lại là khác nhau. Nguyên nhân của sự
khác nhau này không phải là do thuật toán sai, mà là ở cách chúng ta truyền tham số cho
chúng.
Trong trình thứ nhất, với khai báo
void sw(int x, int y)

thì hai biến mới (với tên gọi là x và y) kiểu số nguyên sẽ được hàm tạo ra, chúng được
nạp giá trị (truyền trực tiếp giá trị).
Thuật toán
void sw(int x, int y)
{

int z;
z=x; x=y; y=z;
}

chỉ trao đổi giá trị của hai biến này mà thôi -- và như vậy thì hai biến “cũ” (vẫn với tên
gọi là x và y) sẽ chẳng bị ảnh hưởng bởi các biến đổi nói trên.
Trong trình thứ hai, với khai báo
void sw(int *x, int* y)

thì chúng ta đã truyền6 cho hàm địa chỉ (&x là địa chỉ của x, &y là địa chỉ của y) của các
ô nhớ x và y; và chính vì vậy, các biến đổi sẽ trực tiếp ảnh hưởng tới giá trị của các biến
x và y.
6

Thực tế là hai ô nhớ địa chỉ, với tên gọi là x và y, đã được tạo ra và các địa chỉ được truyền vào các ô nhớ vừa
được tạo ra này.

24


Trong C người ta thường sử dụng cách truyền địa chỉ.
Hai trình con sau đây là tương đương với nhau; chức năng của chúng là tính tổng hai số.
#include <iostream.h>
int sw(int x, int y)
{
return y+x;
}
void main()
{
cout << sw(7,5) <<"\n";

}

#include <iostream.h>
int sw(int* x, int* y)
{
return *y+*x;
}
void main()
{int x=7, y=5;
cout << sw(&x,&y) <<"\n";
}

12

12

25