Đồng bộ hoá nguyên thuỷ

LOGO ĐỒNG BỘ HOÁ NGUYÊN THUỶ Giảng viên hướng dẫn: PGS.TS Trần Đình Quế Học viên thực hiện: Bùi Hồng Đại Nguyễn Thị Bích Ngọc Phạm Hữu Tình Phạm Minh Tuấn Nguyễn Tuấn M12CQCT01-B GROUP 1 NỘI DUNG TRÌNH BÀY 3.1 Giới thiệu 3.2 Semaphores 3.2.1 Bài toán Nhà sản xuất – Người tiêu thụ (The Producer-Consumer Problem) 3.2.2 Bài toán Bộ đọc – Bộ ghi (The Reader-Writer Problem) 3.2.3 Bài toán các triết gia ăn tối (The Dining Philosopher Problem) 3.3 Monitors 3.4 Nguy hiểm của sự tắc nghẽn (DANGERS OF DEADLOCKS) 3.5 Problems 3.6 Bibliographic Remarks Giới thiệu  Trong chương này giới thiệu sự đồng bộ hoá nguyên thuỷ sử dụng các giải pháp Busy Wait (Chờ đợi bận)  Đồng bộ hóa nguyên thuỷ được sử dụng để loại trừ lẫn nhau để cung cấp trật tự giữa các hoạt động khác nhau theo các chuỗi khác nhau.  Có rất nhiều cách xây dựng đồng bộ hóa trong các ngôn ngữ lập trình khác nhau, hai trong số đó phổ biến nhất là: Semaphores và Monitors Bùi Hồng Đại – M12CQCT01-B GROUP 1 Semaphores  Khái niệm Semaphores được Dijkstra đưa ra để giải quyết Busy Wait.  Một semaphore S là một biến số nguyên (integer) được truy xuất chỉ thông qua hai thao tác nguyên tử: wait và signal.  Các thao tác này được đặt tên P () (cho wait - chờ để kiểm tra) và V () (cho signal- báo hiệu để tăng).  Giá trị của Semaphore (hoặc Semaphore nhị phân) chỉ có thể là sai hoặc đúng.  Hàng đợi của các quá trình bị chặn ban đầu là trống rỗng  một quá trình có thể thêm vào hàng đợi khi nó làm cho một cuộc gọi đến P ().  Khi một quá trình gọi P () và giá trị là đúng, thì giá trị của cột trở thành sai.  Nếu giá trị của cột là sai, sau đó quá trình này bị chặn cho đến khi nó trở thành đúng Bùi Hồng Đại – M12CQCT01-B GROUP 1 Semaphores  Giả thiết là cuộc gọi này chèn quá trình người gọi vào hàng đợi của các quá trình bị chặn.  Khi giá trị trở thành đúng, quá trình có thể làm cho nó sai và trở về từ P ().  Các cuộc gọi đến V () làm cho giá trị đúng và cũng thông báo một quá trình nếu hàng đợi của các quá trình ngủ (Sleeping) trên cột đó là không rỗng. Bùi Hồng Đại – M12CQCT01-B GROUP 1 Semaphores  Loại trừ lẫn nhau là đơn giản để thực hiện: BinarySernaphore mutex = new BinarySemaphore(true1; mutex.P(); c r i t i c a l S e c t i o n 0 ; mutex.V();  Một biến thể của cột cho phép nó để có bất kỳ số nguyên giá trị của nó.  Các cột này được gọi là Semaphores đếm (Counting semupphores).  Semaphores có thể được sử dụng để giải quyết một loạt các vấn đề đồng bộ hóa. Bùi Hồng Đại – M12CQCT01-B GROUP 1 Semaphores  Chú ý:  Java không cung cấp các cột để xây dựng ngôn ngữ cơ bản, nhưng có thể dễ dàng được thực thi trong Java bằng cách sử dụng ý tưởng của các Monitor (sẽ đề cập sau). Chỉ đơn giản cho rằng Semaphores có sẵn và giải quyết vấn đề đồng bộ hóa bằng cách sử dụng chúng. Bùi Hồng Đại – M12CQCT01-B GROUP 1 Bùi Hồng Đại – M12CQCT01-B . GROUP 1 Bài toán Nhà sản xuất – Người tiêu thụ Semaphores Bài toán Bộ đọc – Bộ ghi Bài toán các triết gia ăn tối Bài toán Nhà sản xuất – Người tiêu thụ  Một bộ đệm được chia sẻ giữa hai quá trình được gọi là nhà sản xuất và người tiêu thụ.  Nhà sản xuất sản xuất các mục được gửi trong bộ đệm và người tiêu thụ lấy các mục từ bộ đệm và tiêu thụ (sử dụng) chúng  Giả sử các mặt hàng kiểu Double. Kể từ khi bộ đệm được chia sẻ, mỗi quá trình phải truy cập vào bộ đệm trong một cách loại trừ lẫn nhau.  Sử dụng một loạt các đôi kích thước như một bộ đệm của chúng Bùi Hồng Đại – M12CQCT01-B GROUP 1 Bài toán Nhà sản xuất – Người tiêu thụ  Bộ đệm có hai con trỏ, inBuf và outBuf, các chỉ số trong mảng gửi một mục và lấy một mục tương ứng  Biến đếm theo dõi số lượng các mục hiện trong bộ đệm  bên cạnh việc loại trừ lẫn nhau, có thêm hai hạn chế đồng bộ hóa mà cần phải được thỏa mãn:  Người tiêu dùng không nên lấy bất kỳ mục nào từ một bộ đệm trống.  Nhà sản xuất không nên gửi bất kỳ mục nào trong bộ đệm nếu nó là đầy đủ. Các bộ đệm có thể trở thành đầy đủ nếu nhà sản xuất là sản xuất các mặt hàng tại một tỷ lệ lớn hơn so với tỷ lệ mà tại đó các mặt hàng được tiêu thụ của người tiêu dùng. Bùi Hồng Đại – M12CQCT01-B GROUP 1 Bài toán Nhà sản xuất – Người tiêu thụ  Như vậy hình thức đồng bộ hóa được gọi là điều kiện đồng bộ hóa.  Nó đòi hỏi một quá trình chờ đợi cho một số điều kiện để trở thành hiện thực (chẳng hạn như các bộ đệm để trở thành không rỗng) trước khi tiếp tục các hoạt động của mình. Bùi Hồng Đại – M12CQCT01-B GROUP 1 Bài toán Bộ đọc – Bộ ghi  Yêu cầu thiết kế một giao thức để phối hợp truy cập vào cơ sở dữ liệu chia sẻ. Yêu cầu bao gồm:  Không xung đột đọc – ghi: Giao thức nên đảm bảo rằng người đọc và người viết không truy cập CSDL đồng thời.  Không xung đột ghi – ghi: Giao thức nên đảm bảo rằng 2 người ghi không truy cập CSDL đồng thời. Nguyễn Thị Bích Ngọc – M12CQCT01-B GROUP 1 Bài toán Bộ đọc – Bộ ghi  Có thể đồng thời nhiều người đọc truy cập vào CSDL đồng thời  giả sử rằng người đọc theo dõi giao thức bằng cách họ gọi hàm startRead trước khi đọc CSDL và gọi hàm endRead sau khi đọc xong  Người ghi theo dõi với giao thức tương tự  dụng wlock semaphores để đảm bảo rằng chỉ có người ghi đơn lẻ truy cập vào CSDL và chỉ có những người đọc truy cập vào nó. Để đếm số lượng người đọc truy cập vào CSDL, chúng ta sử dụng hàm numReaders. www.themegallery.com Company Logo Bài toán Bộ đọc – Bộ ghi  Phương thức startWrite và endWrite là khá đơn giản  Bất cứ người ghi nào khi muốn truy cập vào CSDL khóa nó bằng cách sử dụng wlock .P().  Nếu CSDL không được khóa, người ghi này có thể truy cập vào. Bây giờ, không có người đọc hoặc người ghi có thể truy cập vào CSDL cho đến khi người ghi này gỡ bỏ việc khóa sử dụng hàm endWrite(). www.themegallery.com Company Logo Bài toán Bộ đọc – Bộ ghi  Xem hàm startRead và endRead  Trong hàm startRead, người đọc đầu tiên gia tăng numReaders. Nếu đây là người đọc đầu tiên (numReaders = 1) , sau đó nó cần khóa CSDL, nếu không sẽ có những người đọc khác truy cập vào CSDL và có thể sử dụng nó.  Trong hàm endRead, giá trị của numRead giảm dần và khi người đọc cuối cùng rời khỏi CSDL thì CSDL sẽ được mở khóa và sử dụng gọi hàm wlock.V().  Giao thức này có sự bất lợi đó là người ghi có thể bị bỏ đói trong sự có mặt liên tục của người đọc. Một giải pháp starvation – free cho vẫn đề đọc – ghi vẫn còn là một bài tập. www.themegallery.com Company Logo Bài toán các triết gia ăn tối  Vấn đề này, đầu tiên đặt ra và giải quyết bằng cách Dijkstra, có ích trong việc đưa ra khỏi vấn đề liên quan với lập trình đồng thời và đối xứng  yêu cầu đưa ra 1 giao thức để phối hợp truy cập vào các tài nguyên chia sẻ. Một người có đầu óc máy tính có thể thay thế cho quy trình triết học và tập tin cho các đĩa. Nhiệm vụ ăn uống có thể xem như là phản hồi của hoạt động yêu cầu truy nhập đến file chia sẻ.  Mỗi triết gia Pi lặp lại một cách xoay vòng các trạng thái được theo dõi như sau: thinking, hungry và eating. Để ăn, triết gia cần có các tài nguyên (dĩa) do đó cần gọi hàm acquire(i). Do đó giao thức yêu cầu trừu tượng hóa một giao diện Resource www.themegallery.com Company Logo Bài toán các triết gia ăn tối  Để giải quyết vấn đề này sử dụng nhị phân semaphores cho mỗi chiếc dĩa.  Để yêu cầu các nguồn tài nguyên để ăn, một nhà triết học i sẽ túm lấy chiếc dĩa ở bên trái bằng cách sử dụng fork[i]. P() và dĩa bên phải sử dụng fork[(i+1)%n].P()  Để trả lại tài nguyên, triết gia gọi ra V() cho cả 2 chiếc dĩa  Nhu vậy sự nguy hiểm của đối xứng trong hệ thống phân phối. Giao thức này có thể dẫn đến bế tắc khi mỗi triết gia có thể lấy chiếc dĩa bên trái và chờ người hàng xóm bên phải đặt lại dĩa đó. www.themegallery.com Company Logo Bài toán các triết gia ăn tối  Có nhiều cách để mở ra hướng giải quyết đảm bảo giải phóng bế tắc. Ví dụ:  Chúng ta có thể giới thiệu đối xứng bằng cách yêu cầu một người triết gia túm lấy chiếc dĩa trong một thứ tự khác nhau ( ví dụ: dĩa bên phải cho phép bởi dĩa bên trái thay vì ngược lại).  Chúng ta có thể yêu cầu triết gia cầm cả 2 dĩa lên tại thời điểm đồng thời. Giả sử nhà triết gia có thể đứng lên trước khi cầm bất cứ dĩa nào. Cho phép nhiều nhất 4 triết gia tại bất cứ thời điểm nào.  Đây như là bài tập để người đọc thiết kế giao thức để giải phóng bế tắc. www.themegallery.com Company Logo Bài toán các triết gia ăn tối  Bài toán các triết gia dùng bữa cũng minh họa sự khác biệt giữa bế tắc tự do và bế tắc đói.  Giả sử yêu cầu triết gia cầm cả 2 dĩa tại thời điểm đồng thời. Mặc dù lúc này có thể loại bỏ bế tắc  Sẽ có vấn đề với các triết gia đang đói bởi vì hàng xóm tiếp tục luân phiên nhau ăn. Người đọc được mời đến với giải pháp là tự do bế tắc tốt hơn là bị đói. www.themegallery.com Company Logo Monitors  Monitor là một cấu trúc hướng đối tượng bậc cao để đồng bộ hóa trong lập trình đồng thời  Monitor có thể được xem như một lớp (Class) mà có thể được sử dụng trong chương trình đồng thời.  một Monitor có các biến dữ liệu (variables) và phương pháp (methods) để thao tác dữ liệu. Bởi vì nhiều luồng (threads) có thể truy cập dữ liệu được chia sẻ cùng một lúc  Monitor hỗ trợ methods để đảm bảo loại trừ lẫn nhau (mutual exclusion). www.themegallery.com Company Logo Monitors  Điều kiện là ít nhất một threads có thể được thực hiện trong bất kỳ methods nào và bất cứ lúc nào.  Cụm từ " thread t is inside the monitor " được sử dụng để biểu thị rằng thread t được thực hiện bên trong monitor  Nhiều nhất là một thread có thể được ỏ trong monitor tại một thời điển bất kỳ  Như vậy, liên quan đến tất cả các đối tượng monitor là một danh sách các thread đang chờ đợi để vào monitor.  Đối tượng monitor là một tài nguyên sử dụng chung còn các Thread như là các tiến trình chờ đợi để được sử dụng tài nguyên chung.  Tại một thời điểm bất kỳ chỉ có 1 thread có thể được sử dụng tài nguyên chung là monitor). www.themegallery.com Company Logo Monitors  Chương trình đồng thời cũng yêu cầu đồng bộ hóa có điều kiện (conditional synchronization) khi một threads phải chờ đợi một điều kiện nhất định để trở thành hiện thực  Để giải quyết đồng bộ có điều kiện, Monitor hỗ trợ xây dựng các khái niệm về biến điều kiện (condition variables). Một biến điều kiện có hai hoạt động được xác định trên nó: chờ đợi (wait) và thông báo (notify) (còn được gọi là signal).  Đối với bất kỳ điều kiện biến x:  Với mọi thread t1, mà gọi đến x.wait () thì thread t1 bị chặn và đưa vào một hàng đợi kết hợp với x.  Khi thread khác t2, gọi đến x.notify (), nếu hàng đợi kết hợp với x là rỗng, một thread được lấy ra từ hàng đợi và đưa vào hàng đợi của các thread có đủ điều kiện để chạy. www.themegallery.com Company Logo Monitors  Nhiều nhất là một thread có thể được trong monitor, điều này ngay lập tức đặt ra một vấn đề: thread đó cần tiếp tục sau khi thông báo cho hoạt động - một trong đó được gọi là phương pháp thông báo cho hay các thread đã được chờ đợi. Có hai câu trả lời có thể sảy ra: Một trong những thread đã được chờ đợi trên biến điều kiện tiếp tục thực hiện. monitor theo quy tắc này được gọi là Hoare monitor .  Các thread đó thực hiện cuộc gọi thông báo cho tiếp tục thực hiện. Khi thread này đi ra khỏi monitor, sau đó các thread khác có thể nhập vào monitor. Đây là ngữ nghĩa sau trong Java. (the semantics followed in Java) www.themegallery.com Company Logo Monitors  Một lợi thế của Hoare monitor là các thread đó đã được thông báo trên điều kiện bắt đầu thực hiện nó mà không có sự can thiệp của bất kỳ thread khác. do đó, trạng thái trong đó thread này bắt đầu thực hiện cũng giống như khi thông báo (notify), nó có thể cho rằng điều kiện là đúng. Vì vậy, bằng cách sử dụng Hoare Mointor, mã của một thread có thể là: if (!B) x.wait();  Giả sử rằng t2 thông báo chỉ khi B là đúng, chúng ta biết rằng t1 có thể giả định B thay đổi. Trong Java kiểu monitor, mặc dù t2 phát hành thông báo, t1 vẫn tiếp tục thực hiện. Vì vậy, khi t1 được được thực hiện, các điều kiện B có thể không đúng nữa. Do đó, khi sử dụng Java, các thread thường chờ đợi điều kiện này như: while(!B) x.wait(); www.themegallery.com Company Logo Monitors  Các thread t1 có thể chỉ lấy một notify() như một gợi ý rằng B có thể đúng. Do đó, rõ ràng cần phải kiểm B khi thay đổi. Nếu B thực sự là sai, nó gọi lại wait().  Trong Java, chúng ta xác định một đối tượng là một monitor bằng cách sử dụng các từ khóa đồng bộ với các phương pháp của nó. Để có được đồng bộ hóa có điều kiện, Java cung cấp: wait(): chèn các thread trong hàng đợi. Để đơn giản, chúng tôi sử dụng Util.myWait () thay vì wait () trong Java. Sự khác biệt duy nhất là myWait () bắt được ngoại lệ bị gián đoạn( InterruptedException)  notify (): đánh thức một thread trong hàng đợi.  notifyAll (): đánh thức tất cả các thread trong hàng đợi chờ. www.themegallery.com Company Logo Monitors  Java không có biến điều kiện. Như vậy, kết hợp với mỗi đối tượng có một hàng đợi duy nhất cho điều kiện.  Điều này là đủ cho hầu hết nhu cầu lập trình.  Nếu cần, nó cũng dễ dàng để mô phỏng các biến điều kiện trong Java. Một đại diện bằng hình ảnh của một Java monitor.  Có hai hàng đợi kết hợp với một đối tượng: một hàng đợi của các thread chờ khóa liên quan đến monitor và một hàng đợi của các thread chờ đợi một số điều kiện để trở thành hiện thực www.themegallery.com Company Logo Nguy hiểm của sự tắc nghẽn (Deadlock)  thread t1 gọi Khi mỗi quá trình đồng bộ đều yêu cầu một lock, có thể để xảy ra quá trình tắc nghẽn (Deadlock).  Chương trình để tránh Deadlock sẽ được thiết kế, sử dụng thường xuyên chiến lược đặt tất cả các đối tượng trong một hệ thống và thu được duy nhất một lock trong đơn tăng thêm  Một vài phương thức hữu ích trong JavaThread như sau:  Phương thức interrupt() cho phép một thread bị ngắt. Nếu t2.interrupt(), t2 sẽ get InterruptedException.  Phương thức yield() cho phép một thread nhường CPU cho thread khác. Nó không yêu cầu một ngắt nào với các thread khác và một chương trình không có yield() sẽ có chức năng tương đương với gọi yield(). Một thread có thể chọn yield() nếu nó đang đợi cho dữ liệu để sẵn sàng từ InputStream.  Phương thức holdsLock(x) trả lại giá trị true nếu thread hiện tại đang sử dụng giám sát lock của đối tượng x. www.themegallery.com Company Logo Các vấn đề  3.1 Chỉ ra nếu P() và V() thao tác của một nhị phân không được thực thi tự động, khi đó các kết thúc có thể bị vi phạm  3.2 Cho thấy các semaphore đếm có thể được thực thi bằng cách sử dụng nhị phân (Gợi ý: sử dụng các biến chia sẻ kiểu integer và semaphore hai nhị phân.  3.3 Đưa một giáp pháp miễn phí cho vấn đề đọc-ghi sử dụng semaphore.  3.4 Vấn đề sau được hiểu như là vấn đề sleeping barber. Có một thread gọi là barbe. Barber sẽ chặn lại sự đợi chờ của bất cứ customer nào. Nếu không có customer, barber sẽ ngừng làm việc. Nếu có nhiều thread customer. Một customer sẽ đợi barber nếu có bất cứ ghế bên trái trong barber room. Ngược lại, customer rời ngay lập tức. Nếu có một chair trống, customer sẽ chiếm đóng. Nếu barber đang ngủ, customer sẽ đánh thưc barber dậy. giả sử rằng có n ghế trong barber shop. Viết một lớp Java SleepingBarber swrr dụng semaphore cho phép những phương thức sau: runBarber() // gọi thread barber; chạy mãi mai; hairCut() // gọi thread customer www.themegallery.com Company Logo Các vấn đề  3.5 Đưa một giải pháp deadlock-free cho vấn đề dùng bữa tối sử dụng semaphore. Giả sử rằng một trong số các chiếc dĩa được chọn là khác nhau.  3.6 Giả sử rằng có ba threads – P, Q và R . Sử dụng semaphore để điều hành in ấn như là số của R được in ra luôn nhỏ hơn hoặc bằng tổng số của P và Q được in ra.  3.7 Viết một giám sát cho vấn đề sleeping barber  3.8 Chỉ ra cách điều khiển các biến của một giám sát có thể thực thi trong Java www.themegallery.com Company Logo Các vấn đề  3.9 Viết một lớp giám sát counter cho phép một tiến trình ngủ đến khi hàm đếm đạt đến một giá trị nào đó. Lớp counter cho phép hai thao tác: increament () và sleepUntill(int x).  3.10 Viết một lớp Java BoundedCounter với một giá trị nhỏ nhất và lớn nhất. Lớp này cung cấp hai phương thức: increment() và decrement(). Kết quả của việc giảm giá trị nhỏ nhất và tăng giá trị lớn nhất trong việc gọi thread đợi đến khi thao tác được thực hiện mà không xâm phạm vào phạm vi đếm www.themegallery.com Company Logo Bình luận thư mục  Semaphore đã được giới thiệu bởi Dijkstra [Dij65a]. Khái niệm giám sát được giới thiệu bởi Brinch Hansen [Ha11721 và Hoare- phong cách giám sát, bởi Hoare [Hoa74]. Các giải pháp cho các vấn đề đồng bộ hóa cổ điển trong Java cũng sẽ được thảo luận trong cuốn sách của Hartley [Har98]. Ví dụ của bế tắc và độ phân giải của nó dựa trên nguồn tài nguyên đặt hàng được thảo luận trong cuốn sách của Lea [Lea99]. www.themegallery.com Company Logo LOGO