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].
32 trang |
Chia sẻ: lylyngoc | Lượt xem: 3018 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Đồng bộ hoá nguyên thuỷ, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
Các file đính kèm theo tài liệu này:
- bao_cao_nhom_1_8353.pdf