Chương 5: Đồng bộ hóa tiến trình

Chia sẻ: Lê Trinh | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

183
lượt xem 24
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'chương 5: đồng bộ hóa tiến trình', công nghệ thông tin, hệ điều hành phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 5: Đồng bộ hóa tiến trình

Chương 5: Đồng bộ hóa tiến trình Tình trạng đua tranh Cơ sở Tình trạng đua tranh: là tình trạng mà vài tiến trình cùng truy cập và Bài toán miền tương trục thay đổi lên dữ liệu được chia sẻ. Giá trị cuối cùng của dữ liệu chia sẻ Đồng bộ hóa bằng phần cứng phụ thuộc vào tiến trình nào hoàn thành cuối cùng. Semaphores Để ngăn chặn tình trạng đua tranh, các tiến trình đua tranh phải được Các bài toán cổ điển về đồng bộ hóa đồng bộ hóa. Monitors Đồng bộ hóa trong Solaris và Windows 2000 Hệ điều hành 5.1 Phạm Thế Phi ©2004 Hệ điều hành 5.3 Phạm Thế Phi ©2004 Cơ sở Vấn đề miền tương trục Truy cập cạnh tranh lên dữ liệu được chia sẻ có thể gây nên tình Tất cả n tiến trình đang cạnh tranh để sử dụng dữ liệu chia sẻ. trạng không nhất quán dữ liệu. Mỗi tiến trình có một đoạn mã lệnh, gọi là miền tương trục, mà Việc duy trì sự nhất quán dữ liệu yêu cầu các cơ chế để đảm bảo trong đó có hành động truy cập dữ liệu được chia sẻ. sự thực thi một cách có thứ tự của các tiến trình có hợp tác với Vấn đề – đảm bảo rằng khi một tiến trình đang chạy trong nhau. miền tương trục, không có một tiến trình nào khác được cho Ví dụ? phép chạy trong miền tương trục của mình. Hệ điều hành 5.2 Phạm Thế Phi ©2004 Hệ điều hành 5.4 Phạm Thế Phi ©2004
Giải pháp cho vấn đề miền tương trục Giải thuật 1 1. Loại trừ hỗ tương. Nếu tiến trình Pi đang thực thi trong miền tương trục, thì không có tiến trình nào khác có thể thực thi Các biến chung: trong miền tương trục của mình. ) int turn; 2. Tiến triển. Nếu không có tiến trình nào đang thực thi trong khởi đầu turn = 0 miền tương trục của nó và có tồn tại vài tiến trình đang mong ) turn = i ⇒ Pi có thể bước vào miền tương trục của nó muốn được thực thi trong miền tương trục của chúng, thì việc Tiến trình Pi lựa chọn cho một tiến trình bước vào miền tương trục của nó do { không thể bị trì hoãn mãi được. while (turn != i) ; 3. Chờ đợi hữu hạn. Không có tiến trình nào phải chờ đợi vĩnh critical section viễn để có thể bước vào miền tương trục của nó turn = j; reminder section } while (1); Giải pháp này thõa mãn yêu cầu về loại trừ hỗ tương nhưng không tiến triển được. Hệ điều hành 5.5 Phạm Thế Phi ©2004 Hệ điều hành 5.7 Phạm Thế Phi ©2004 Những cố gắng đầu tiên để giải quyết bài Giải thuật 2 toán miền tương trục Chỉ có 2 tiến trình, P0 và P1 Các biến chia sẻ Cấu trúc tổng quát của tiến trình Pi (tiến trình kia là P1-j) ) boolean flag[2]; khởi đầu flag [0] = flag [1] = false. do { ) flag [i] = true ⇒ Pi sẵn sàng bước vào miền tương trục của nó entry section Tiến trình Pi critical section do { exit section flag[i] := true; reminder section while (flag[j]) ; critical section } while (1); flag [i] = false; Các tiến trình có thể chia sẻ một số biến chung để đồng bộ hóa hành remainder section động của chúng. } while (1); Thõa mãn yêu cầu loại trừ hỗ tương, nhưng không tiến triển Hệ điều hành 5.6 Phạm Thế Phi ©2004 Hệ điều hành 5.8 Phạm Thế Phi ©2004
Giải thuật 3 Giải thuật Bakery Kết hợp các biến chia sẻ được sử dụng trong các giải thuật 1 Chú thích < dùng để so sánh các cặp (ticket #, process id #) và 2. ) (a,b) < c,d) if a < c or if a = c and b < d Tiến trình Pi ) max (a0,…, an-1) là số k, sao cho k ≥ ai for i = 0, do { …, n – 1 flag [i]:= true; Dữ liệu chia sẻ turn = j; while (flag [j] and turn = j) ; boolean choosing[n]; critical section int number[n]; flag [i] = false; Các dữ liệu trên được khởi tạo tương ứng là false và 0 remainder section } while (1); Thõa mãn cả 3 điều kiện Hệ điều hành 5.9 Phạm Thế Phi ©2004 Hệ điều hành 5.11 Phạm Thế Phi ©2004 Giải thuật Bakery Giải thuật Bakery do { Miền tương trục cho n tiến trình choosing[i] = true; Trước khi bước vào miền tương trục của mình, tiến trình nhận number[i] = max(number[0], number[1], …, number [n – 1])+1; được một con số. Tiến trình nào nhận được con số nhỏ nhất choosing[i] = false; sẽ có quyền bước vào miền tương trục. for (j = 0; j < n; j++) { If tiến trình Pi và Pj nhận được cùng một số, và nếu i
Đồng bộ hóa với sự trợ giúp của phần cứng Loại trừ tương hỗ với sự trợ giúp của phần cứng Đọc và sửa đổi nội dung của một word một cách tự động Tự động swap hai biến boolean TestAndSet(boolean &target) { boolean rv = target; void Swap(boolean &a, boolean &b) { target = true; boolean temp = a; a = b; return rv; b = temp; } } Hệ điều hành 5.13 Phạm Thế Phi ©2004 Hệ điều hành 5.15 Phạm Thế Phi ©2004 Loại trừ tương hỗ với Test-and-Set Loại trừ tương hỗ với Swap Dữ liệu được chia sẻ: Dữ liệu chia sẻ (khởi tạo là false): boolean lock = false; boolean lock; boolean waiting[n]; Tiến trình Pi Tiến trình Pi do { do { while (TestAndSet(lock)) ; key = true; while (key == true) critical section Swap(lock,key); lock = false; critical section remainder section lock = false; } remainder section } Hệ điều hành 5.14 Phạm Thế Phi ©2004 Hệ điều hành 5.16 Phạm Thế Phi ©2004
Semaphores Cài đặt Semaphore Công cụ dùng để đồng bộ hóa không gây ra tình trạng chờ đợi bận. Định nghĩa một semaphore như là một record Semaphore S – biến integer typedef struct { Chỉ có thể được truy cập thông qua hai thao tác nguyên tử (không thể int value; chia nhỏ được nữa): struct process *L; wait (S): } semaphore; while S≤ 0 do no-op; S--; Giả sử ta đã có hai thao tác: ) block – ngưng tạm thời tiến trình gọi thao tác này. signal (S): ) wakeup(P) khởi động lại tiến trình đã bị blocked P. S++; Hệ điều hành 5.17 Phạm Thế Phi ©2004 Hệ điều hành 5.19 Phạm Thế Phi ©2004 Miền tương trục của n tiến trình Cài đặt Dữ liệu chia sẻ: Các thao tác trên Semaphore bây giờ được định nghĩa như sau: semaphore mutex; //khởi đầu mutex = 1 wait(S): S.value--; Tiến trình Pi: if (S.value < 0) { add this process to S.L; do { block; wait(mutex); } critical section signal(mutex); signal(S): remainder section S.value++; } while (1); if (S.value
Semaphore như là công cụ đồng bộ hóa tổng quát Có hai kiểu semaphore Thực thi B trong Pj chỉ sau khi A đã được thực thi trong Pi Semaphore tăng dần– giá trị integer có thể trải qua nhiều miền Sử dụng semaphore flag khởi tạo với giá trị 0 giá trị. Code: Semaphore nhị phân – giá trị integer chỉ nhận một trong hai giá trị Pi Pj 0 và 1; có thể cài đặt đơn giản hơn. Có thể coi semephore nhị phân là trường hợp đặc biệt của M M semaphore tăng dần. A wait(flag) signal(flag) B Hệ điều hành 5.21 Phạm Thế Phi ©2004 Hệ điều hành 5.23 Phạm Thế Phi ©2004 Deadlock và chết đói Các bài toán đồng bộ hóa cổ điển Deadlock – hai hoặc nhiều tiến trình đang chờ đợi vô hạn một sự Bài toán người sản xuất-người tiêu dùng (Bounded-Buffer hay kiện nào đó, mà sự kiện đó chỉ có thể được tạo ra bởi một trong các Producer-Customer) tiến trình đang chờ đợi kia. Xem S và Q là 2 semaphores được khởi tạo là 1 Bài toán Readers and Writers P0 P1 wait(S); wait(Q); Bài toán “5 nhà triết gia ăn tối” (Dining-Philosophers) wait(Q); wait(S); M M signal(S); signal(Q); signal(Q) signal(S); Sự chết đói – bị nghẽn (block) không hạn định. Một tiến trình có thể không bao giờ được xóa khỏi hàng đợi trong semaphore. Hệ điều hành 5.22 Phạm Thế Phi ©2004 Hệ điều hành 5.24 Phạm Thế Phi ©2004
Bounded-Buffer Bounded-Buffer – Tiến trình Consumer Dữ liệu chia sẻ do { semaphore full, empty, mutex; wait(full) wait(mutex); Khởi tạo: … remove an item from buffer to nextc … full = 0, empty = n, mutex = 1 signal(mutex); signal(empty); … consume the item in nextc … } while (1); Hệ điều hành 5.25 Phạm Thế Phi ©2004 Hệ điều hành 5.27 Phạm Thế Phi ©2004 Bounded-Buffer – tiến trình Producer Bài toán Readers-Writers Dữ liệu chia sẻ do { … semaphore mutex, wrt; produce an item in nextp … Khởi tạo wait(empty); wait(mutex); mutex = 1, wrt = 1, readcount = 0 … add nextp to buffer … signal(mutex); signal(full); } while (1); Hệ điều hành 5.26 Phạm Thế Phi ©2004 Hệ điều hành 5.28 Phạm Thế Phi ©2004
Readers-Writers – Tiến trình Writer Bài toán năm nhà triết gia ăn tối wait(wrt); … writing is performed … signal(wrt); Dữ liệu chia sẻ semaphore chopstick[5]; Khởi đầu, các giá trị là 1 Hệ điều hành 5.29 Phạm Thế Phi ©2004 Hệ điều hành 5.31 Phạm Thế Phi ©2004 Readers-Writers – Tiến trình Reader Bài toán năm nhà triết gia ăn tối Philosopher i: wait(mutex); do { readcount++; wait(chopstick[i]) if (readcount == 1) wait(chopstick[(i+1) % 5]) wait(wrt); … signal(mutex); eat … … reading is performed signal(chopstick[i]); … signal(chopstick[(i+1) % 5]); wait(mutex); … readcount--; think if (readcount == 0) … signal(wrt); } while (1); signal(mutex): Hệ điều hành 5.30 Phạm Thế Phi ©2004 Hệ điều hành 5.32 Phạm Thế Phi ©2004
Monitors Cái nhìn một cách có sơ đồ về Monitor Cấu trúc dùng để đồng bộ hóa được cài đặt ở ngôn ngữ cấp cao, nó cho phép chia sẻ an toàn một kiểu dữ liệu trừu tượng nào đó giữa nhiều tiến trình cạnh tranh. monitor monitor-name { shared variable declarations procedure body P1 (…) { ... } procedure body P2 (…) { ... } procedure body Pn (…) { ... } { initialization code } } Hệ điều hành 5.33 Phạm Thế Phi ©2004 Hệ điều hành 5.35 Phạm Thế Phi ©2004 Monitors Monitor với các biến điều kiện Để cho phép một tiến trình chờ đợi trong monitor, một biến điều kiện phải được khai báo như sau: condition x, y; Biến điều kiện chỉ có thể được sử dụng với hai thao tác wait và signal. ) Thao tác x.wait(); có nghĩa là tiến trình đang gọi thao tác này đang ngủ cho đến khi một tiến trình khác gọi x.signal(); ) Thao tác x.signal khởi động lại chính xác một tiến trình đang ngủ để chờ đợi trên biến x. Nếu không có tiến trình nào đang ngủ trên x, thì thao tác signal không gây ảnh hưởng gì cả. Hệ điều hành 5.34 Phạm Thế Phi ©2004 Hệ điều hành 5.36 Phạm Thế Phi ©2004
Ví dụ về cài đặt bài toán 5 nhà triết gia ăn 5 nhà triết gia ăn tối tối trên monitor monitor dp void test(int i) { { if ( (state[(i + 4) % 5] != eating) && enum {thinking, hungry, eating} state[5]; (state[i] == hungry) && condition self[5]; (state[(i + 1) % 5] != eating)) { void pickup(int i) // các slide kế tiếp state[i] = eating; void putdown(int i) // các slide kế tiếp self[i].signal(); void test(int i) // các slide kế tiếp } void init() { for (int i = 0; i < 5; i++) } state[i] = thinking; } } Hệ điều hành 5.37 Phạm Thế Phi ©2004 Hệ điều hành 5.39 Phạm Thế Phi ©2004 Các nhà triết gia ăn tối void pickup(int i) { state[i] = hungry; test[i]; if (state[i] != eating) self[i].wait(); } void putdown(int i) { state[i] = thinking; // test left and right neighbors test((i+4) % 5); test((i+1) % 5); } Hệ điều hành 5.38 Phạm Thế Phi ©2004