Giáo trình Xử lý song song và phân tán

à là xử lý tuần tự. Vấn đề là khả năng các tiến trình được tạo lập nhìn thấy dữ liệu của nhau như thế nào? Một mặt một tiến trình có thể muốn giữ một phần dữ liệu cục bộ cho riêng mình, không cho những tiến trình khác nhìn thấy/truy cập tới những dữ liệu đó. Mặt khác, nó cũng muốn trao đổi thông tin với các tiến trình khác. Xử lý vấn đề che giấu hay chia sẻ thông tin như thế nào còn tuỳ thuộc vào mô hình mà chúng ta áp dụng, dựa vào tiến trình hay luồng. Các tiến trình trong UNIX được sử dụng như các đơn vị tính toán độc lập, theo mặc định, việc tính toán và cập nhật bộ nhớ của một tiến trình không là không nhìn thấy được bởi các tiến trình khác. Đối với các luồng, tất cả các thông tin, theo mặc định, là nhìn thấy được. Do vậy, trong mô hình này cần phải cố gắng rất nhiều để che giấu thông tin. Bây giờ chúng ta xét một số hàm điều phối vấn đề chia sẻ bộ nhớ. Khi muốn sử dụng bộ nhớ chung, ta cần phải xin cấp phát bộ nhớ và sau khi sử dụng xong phải giải phóng chúng. Người lập trình phải có trách nhiệm giải phóng bộ nhớ chia sẻ một cách tường minh khi chúng không còn cần thiết sử dụng. Có hai hàm cơ sở: shared(m, &id): giống như malloc(), nhưng cấp phát m byte bộ nhớ chia sẻ cho tiến trình id. free_shm(): giải phóng bộ nhớ đã được cấp. Ví dụ: Bài toán loại trừ nhau. Trước tiên chúng ta xét đoạn chương trình sau: main(){ int id, sid, *i, j; i = (int*)shared(sizeof(int), &sid); *i = 100; j = 100; printf(“Before fork: %d, %d\n”, *i, j); id = create_process(2); *i = id; j = id * 2; // (1) printf(“After fork: &d, %d\n”, *i, j);// (2) join_process(3, id); printf(“After join: &d, %d\n”, *i, j); free_shm(sid); } Chúng ta hãy dự đoán xem các kết quả của hai lệnh printf(“After ”) cho kết quả như thế nào? Lứu ý rằng, i là biến chia sẻ, id là duy nhất (số hiệu) đối với mỗi tiến trình. Giả sử câu lệnh (1) thực hiện với id = 2, liệu dòng (2) có in ra là “After fork: 2, 4” hay không? Câu trả lời là không nhất thiết. Các giá trị của *i, j in ra có thể là 2, 4; 4, 4; 6, 4; bởi vì khi tiến trình thứ i thực hiện xong câu lệnh (1), trước khi nó thực hiện (2) thì có thể các tiến trình khác đã cập nhật lại giá trị của i. Đây là bài học quan trọng của lập trình chia sẻ bộ nhớ. Vấn đề truy cập vào bộ nhớ chia sẻ là phải có sự hợp tác chặt chẽ giữa các tiến trình. Nếu có một tiến trình truy cập vào một vùng nhớ với ý định cập nhật thì nó phải được đảm bảo rằng không một tiến trình nào khác đọc dữ liệu ở vùng đó cho đến khi việc cập nhật đó kết thúc. Muốn giải quyết được vấn đề trên thì phải có cơ chế đảm bảo rằng, các khối lệnh của chương trình được thực thi chỉ bởi một tiến trình tại mỗi thời điểm. Nếu có một tiến trình bắt đầu vào thực hiện một khối lệnh thì những tiến trình khác không được vào khối lệnh đó. Những cơ chế như thế gọi là gài khoá (lock). Khi vào một vùng lệnh thì dùng chìa để khoá nó lại, sau đó mở khoá (unlock) khi ra khỏi vùng đó và trao chìa cho tiến trình khác có nhu cầu. Để thực hiện các yêu cầu đó chúng ta sử dụng: init_lock(Id): Khởi động bộ khoá vùng nhớ chia sẻ, trong đó Id là tên của vùng nhớ sử dụng chung. lock(Id): khoá lại vùng nhớ Id. Nếu một tiến trình đã dùng chìa để khoá lại một vùng nhớ chung thì những tiến trình khác muốn truy cập vào đó sẽ phải chờ. Giả thiết rằng chỉ có một chìa khoá, do vậy chỉ khi chiếc khoá đã được một tiến trình nào đó mở ra thì chìa của nó mới được giao cho tiến trình khác sử dụng. unlock(Id): mở khoá vùng đã bị khoá và trả lại chìa cho tiến trình khác. Sử dụng cơ chế gài khoá để viết lại chương trình trên cho đúng là như sau: main(){ int *lock1,id, sid1, sid2, *i, j; lock1 = (int*)shared(sizeof(int), &sid1); init_lock(lock1); i = (int*)shared(sizeof(int), &sid2); *i = 100; j = 100; printf(“Before fork: %d, %d\n”, *i, j); id = create_process(2); lock(lock1); *i = id; j = id * 2; // (1) printf(“After fork: &d, %d\n”, *i, j);// (2) unlock(lock1); join_process(3, id); printf(“After join: &d, %d\n”, *i, j); free_shm(sid1); free_shm(sid2); } Chúng ta nhận thấy cơ chế gài khoá giải quyết được bài toán loại trừ lẫn nhau, nghĩa là nó chỉ cho phép một tiến trình được vào thực hiện một vùng mã lệnh tại mỗi thời điểm. Ví dụ: Cho trước một đoạn chương trình tính tổng của hai vector: for(i = 0; i < N; i++){ // (1) C[i] = A[i] + B[i]; } Thực hiện song song hoá đoạn chương trình này như thế nào? Tương tự như ví dụ nêu trên, giả sử ta có M tiến trình. Chúng ta có thể chia N phần tử thành M phần (thường ta giả thiết N chia hết cho M, nghĩa là N/M là số nguyên) và gán từng phần đó cho mỗi tiến trình. Chu trình trên có thể viết thành: for(j = id * N/M; j < (id+1)*N/M; j++){ C[j] = A[j] + B[j]; } Trong đó, id là số hiệu của tiến trình, chạy từ 0 đến M-1. Tiến trình thứ i xử lý N/M phần tử liên tiếp kể từ i*N/M+1, ví dụ hình 4-1 (a). Hoặc ta có thể cho phép các tiến trình truy cập xen kẽ vào các phần tử của mảng như sau: Tiến trình Pi bắt đầu từ phần tử thứ i, sau đó bỏ qua M phần tử để xử lý phần từ tiếp theo, nghĩa là nó truy cập đến i, i+M, i+2M, v.v., ví dụ hình 4-1 (b). Chu trình (1) khi đó được viết như sau: for(j = id; j < N; j+=M){ C[j] = A[j] + B[j]; } Ví dụ: Khi N = 15 và M = 5 thì việc gán các phần tử của vector cho các tiến trình sẽ được thực hiện theo cách trên như sau: P1 P2 P3 P4 P5 1 4 7 10 13 2 5 8 11 14 3 6 9 12 15 P1 P2 P3 P4 P5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (a) (b) Hình 4-1 Các cách phân chia chu trình của một mảng tuần tự 4.1.2 Lập trình chia sẻ bộ nhớ dựa vào luồng Nhiều hệ điều hành hiện nay đều hỗ trợ đa luồng, ví dụ Window, OS/2, và UNIX. Trong hệ thống SMP, những luồng khác nhau có thể được hệ điều hành lập lịch tự động cho những CPU khác nhau. Một số ngôn ngữ lập trình, ví dụ Java cũng hỗ trợ lập trình đa luồng. Một tiến trình là bức tranh về sự hoạt động của một chương trình. Mỗi tiến trình được kết hợp với một hoặc nhiều luồng. Các luồng có thể xem như các tập con của một tiến trình [6]. Các luồng của một tiến trình có thể chia sẻ với nhau về không gian địa chỉ chương trình, các đoạn dữ liệu và môi trường xử lý, đồng thời cũng có vùng dữ liệu riêng để thao tác. Để dễ hiểu hơn về mô hình này, chúng ta có thể hình dung tiến trình như một xí nghiệp và các luồng như là các công nhân làm việc trong xí nghiệp đó. Các công nhân của xí nghiệp cùng chia sẻ nhau diện tích mặt bằng và các tài nguyên của cả xí nghiệp. Song, mỗi công nhân lại có chỗ làm việc được xem như là chỗ riêng của họ và những người khác không truy cập được. Việc tạo ra một công nhân (tuyển dụng lao động) dễ hơn nhiều việc tạo lập ra một xí nghiệp, vì một muốn có một xí nghiệp thì phải có ít nhất một công nhân nào đó theo qui định. Tương tự chúng ta có thể quan sát mối quan hệ giữa tiến trình và luồng về phương diện thông tin. Các công nhân trong xí nghiệp, theo mặc định, được quyền biết về mọi sự thay đổi, mọi việc xảy ra trong xí nghiệp. Nhưng nói chung, những biến động của xí nghiệp thì bình thường những xí nghiệp khác không biết được, trừ khi nó được thông báo trực tiếp cho những xí nghiệp đó. Các tiến trình và các luồng trong hệ thống song song cần phải được đồng bộ, song việc đồng bộ các luồng được thực hiện hiệu quả hơn đổi với các tiến trình. Đồng bộ các tiến trình đòi hỏi tốn thời gian hoạt động của hệ thống, trong khi đối với các luồng thì việc đồng bộ chủ yếu tập trung vào sự truy cập các biến chung của chương trình. Nhiều hệ điều hành hiện nay hỗ trợ đa luồng như: SUN Solaris, Window NT, OS/2, v.v. Bên trong những hệ điều hành này, những đặc tính hỗ trợ cho NSD khai thác được các luồng trong chương trình của mình thường khác nhau. Rất may hiện nay đã có một chuẩn, đó là Pthread của IEEE Portable Operating System Interface, POSIX. Thực hiện các luồng của Pthread Trong Pthread, chương trình chính cũng chính là một luồng. Một luồng có thể được tạo lập và kết thúc bằng những chương trình con sau: Pthread_t aThread; // Khai báo một luồng pthread_create(&aThread,&status,(void*)proc1,(void*)arg); pthread_join(athread, void *status); Hoạt động của các chương trình con trên được mô tả như trong hình 4-2. Một luồng mới được tạo ra và hoạt động ở proc1 và được truyền danh sách các đối số là &arg. Luồng sẽ bị huỷ bỏ sau khi kết thúc hoạt động và giải phóng các tài nguyên. Trang thái kết thúc công việc được trả lại trong pthrread_join(). Chương trình chính . . athread . proc1(&arg) pthread_create(&aThread,&status,(void*)proc1,(void*)arg); { . . . . pthread_join(athread, void *status); . . return(*status); . . } Hình 4-2 Hoạt động của luồng trong Pthread Có thể tạo lập và kết thúc một dãy các luồng. for(int i=0; i <n; i++) pthread_create(&aThread[i],&status,(void*)proc1,(void*)arg); . . . for(int i=0; i <n; i++) pthread_join(aThread[i],NULL); Ví dụ: Xét một chương trình đơn giản sử dụng các luồng. Chương trình gồm hai chương trình con reader() và processor(). Reader() đọc dãy dữ liệu từ luồng vào và processor() xử lý trên các dữ liệu đọc vào. #include #include int counter = 0; int item[100]; void *reader(); void *processor(); main(){ pthread-t id; /* Tạo ra hai luồng để đọc và xử lý */ if(0==pthread_create(&id, NULL,reader,NULL)) printf(“Reader done\n”); if(0==pthread_create(&id,NULL,processor,NULL)) printf(“Processor done\n”); /* Kết thúc tất cả các luồng */ pthread_exit(NULL); } /* reader()đọc dữ liệu vào mảng item */ void *reader(){ int num; printf(“Reader starting\n”); while(1){ printf(“Num please: \n”); scanf(“%d”, &num); if(num==0){counter = -1; break;} /* Kết thúc khi đọc vào số 0 */ item[counter++] = num; } } /* procesor() xử lý dữ liệu từ mảng item */ void *processor(){ int i, mycount = 0; int array[100]; printf(“processor starting\n”); for(i=0; i<100;i++) arra[i] = 0; while(1){ if(counter <0) break; if(mycount < counter){ for(i=0; i < 100; i++) array[i] += item[mycount]; printf(“%d %d %d\n”,mycount,counter,item[mycount]); mycount++; } } } Ngay khi một giá trị được đọc và lưu trữ vào bộ nhớ, đơn vị reader lại sẵn sàng để đọc số tiếp theo. Cùng thời điểm này, đơn vị procesor đã có thể lấy dữ liệu ra từ nơi lưu trữ để xử lý. Các lệnh printf() trong chương trình trên giúp chúng ta theo dõi được vết thực hiện của các luồng. Vấn đề thực hiện loại trừ nhau giữa các luồng Vấn đề thực hiện loại trừ nhau giữa các luồng cũng tương tự như đối với các tiến trình. Chúng ta có bốn hàm nguyên thuỷ: pthread_mutex_init(mutex, NULL) pthread_mutex_lock(mutex) pthread_mutex_unlockinit(mutex) pthread_mutex_destroy(mutex) Ví dụ: Chương trình đọc vào một mảng a[] các số nguyên và thực hiện cộng song song (theo nhiều luồng) các phần tử của mảng với một hằng số k. #include #include int a[100], N = 50; int ok, k, next, nProc = 3; pthread_mutex_t lock; void *work(); main(){ thread_t id; int i, status; /* Đọc vào một mảng gồm N số */ for(i=0; i < N; i++) scanf(“%d”, a+i); scanf(“%d”, a+i); next = N – 1; thread_mutex_init(&lock, NULL); ok = 0; for(i = 0; i < nProc; i++){ if(0==pthread_create(&id,NULL,work,NULL)) continue; else printf(Không tạo được luồng!\n”); } ok = 1; pthread_exit(&status); } /* Chương trình xử lý vấn loại trừ nhau giữa các luồng để thực hiện song song */ void *work(){ int i, ctr, j; ctr = 0; while(ok==0); /* Chờ cho đến khi tất cả các luồng được tạo lập*/ do{ pthread_mutex_lock(&lock); i = next--; pthread_mutex_unlock(&lock); ctr++; if(i >= 0) a[i] += k; if(i%pthread_self() == 0) sleep(1); /*Chậm lại một nhịp */ }while(i >= 0); printf(“Thread %d đã thực hiện %d vòng lặp\n”,pthread_self(), ctr); } Thành phần cơ bản của work() là chu trình do-while. Biến next là toàn cục và được gán giá trị ở chương trình chính là N-1. Mỗi luồng trong hệ thống sẽ nhìn vào giá trị của next để biết xem còn công việc để thực hiện tiếp hay không. next được giảm đi để chỉ ra rằng có một luồng đang xử lý a[next]. Vì tất cả các luông đều sử dụng được biến next nên cần phải đảm bảo rằng việc giảm giá trị của next không gây ra sự ảnh hưởng tới luồng khác, nghĩa là phải đưa nó vào vùng khoá (lock). Tại sao giá trị sau khi giảm lại phải đặt vào i? Như trên đã nêu, next là biến chia sẻ cho tất cả các luồng. Do vậy, không thể đảm bảo được rằng, giá trị của next sau khi được giảm vẫn được giữ nguyên sau khi mở khoá. 4.1.3 Xử lý luồng trong Java Java là ngôn ngữ lập trình hướng đối tượng hỗ trợ đa luồng, tiện lợi cho các ứng dụng web trên mạng. Trong mô hình hướng đối tượng, tiến trình và thủ tục là thứ yếu, mọi chức năng của chương trình được xác định thông qua các đối tượng. Khái niệm luồng trong Java giống như trong các hệ điều hành được tích hợp vào ngôn ngữ. Cũng giống như trên, các luồng được tạo lập, sau đó thực hiện một số công việc và kết thúc hoạt động khi không còn vai trò sử dụng. Tạo lập các luồng Trong Java có một lớp được xây dựng sẵn là Thread, làm lớp cơ sở để xây dựng những lớp kết thừa mới. class MyClass extends Thread{ . . . } Các tiến trình trong hệ thống bắt đầu thực hiện ở một địa chỉ đặc biệt được xác định bởi phương mức có tên là main() của một lớp chính. Tương tự khi một luồng của lớp MyClass được tạo ra thì nó gọi phương thức run() để thực hiện. Phương thức này được viết đè để thực thi những công việc yêu cầu trong mỗi luồng được tạo ra. class MyClass extends Thread{ // Một số thuộc tính public void run(){ // Các lệnh cần thực hiện theo luồng } // Một số phương thức khác được viết đè hay bổ sung } Khi chương trình chạy nó sẽ gọi một phương thức đặc biệt đã được khai báo trong Thread đó là start() để bắt đầu một luồng đã được tạo ra. Java không hỗ trợ đa kế thừa. Do vậy, nếu người lập trình muốn tạo ra một lớp kế thừa từ một lớp cơ sở và để thực hiện được theo luồng thì nó cũng đồng thời phải kế thừa từ lớp Thread. Điều này không thực hiện được. Java giải quyết hạn chế trên bằng cách xây dựng khái niệm Interface. Giao diện hỗ trợ thực hiện theo luồng là Runnable. Người lập trình thiết kế các lớp thực hiện theo luồng bằng cách cài đặt theo giao diện Runnable. class MyClass implemnets Runnable{ . . . } Các trạng thái của Thread Một luồng có thể ở một trong các trạng thái sau: new: khi một luồng mới được tạo ra với toán tử new(). runnable: khi chúng ta gọi phương thức start() để bắt đầu của một luồng. blocked: từ trạng thái runnable chuyển sang trạng thái “bị chặn” khi gọi một trong các phương thức: sleep(), suspend(), wait(), hay bị chặn lại ở Input/output. dead: luồng chuyển sang trạng thái “chết” khi nó kết thúc hoạt động bình thường, hoặc gặp phải ngoại lệ không thực hiện tiếp được. Hình 4-3 mô tả sơ đồ chuyển trạng của các luồng trong hệ thống. dead new blocked start stop sleep resume Đánh thức notify wait chặn lại bởi I/O Kết thúc I/O suspend runnable Hình 4-3 Sơ đồ trạng thái của Thread Ví dụ: Chương trình sau sử dụng Thread để tính tổng các phần tử của một mảng. public class Adder{ public int[] array; private int sum = 0; private int i