zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Quản trị kinh doanh

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

Chia sẻ: Sfdsf Sdfsd | Ngày: | Loại File: PDF | Số trang:32

Báo xấu

110
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầ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

Chủ đề:

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

Lưu

Nội dung Text: 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À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 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ẫ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. 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à: 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 đúng Bù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 1
Bài toán Nhà sản Semaphores Bài toán xuất – các triết Người gia ăn tối tiêu thụ . Bài toán Bộ đọc – Bộ ghi Bù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ú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ụ  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ữ 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 M12CQCT01- 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

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí

65 tài liệu

2430 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.