Tiểu luận: Đồng bộ hóa nguyên thủy

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) 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
Nội dung trích xuất từ tài liệu:
Tiểu luận: Đồng bộ hóa nguyên thủy 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 NỘI DUNG TRÌNH BÀY3.1 Giới thiệu3.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 Monitors3.4 Nguy hiểm của sự tắc nghẽn (DANGERS OF DEADLOCKS)3.5 Problems3.6 Bibliographic Remarks M12CQCT01- M12CQCT01-B GROUP 1 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) bận) Đồng bộ hóa nguyên thuỷ được sử dụng để loại trừ lẫnnhau để cung cấp trật tự giữa các hoạt động khác nhau theocác chuỗi khác nhau. nhau. Có rất nhiều cách xây dựng đồng bộ hóa trong các ngônngữ lập trình khác nhau, hai trong số đó phổ biến nhất là: nhau, là:Semaphores và Monitors Bùi Hồng Đại – M12CQCT01-B M12CQCT01- 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 đúngBùi Hồng Đại – M12CQCT01-B M12CQCT01- 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 M12CQCT01- GROUP 1 Semaphores  Loại trừ lẫn nhau là đơn giản để thực hiện: BinarySernaphore mutex = new BinarySemaphore(true1; mutex.P(); criticalSection0; 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 M12CQCT01- 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 M12CQCT01- GROUP 1Bài toánNhà sản Semaphores Bài toán xuất – các triết Người gia ăn tốitiêu thụ . Bài toán Bộ đọc – Bộ ghiBùi Hồng Đại – M12CQCT01-B M12CQCT01- GROUP 1 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úngBùi Hồng Đại – M12CQCT01-B M12CQCT01- 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 M12CQCT01- 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 M12CQCT01- 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 ...