Thảo luận Bài 8

- Trên RAG, lúc đầu tất cả nhu cầu về tài nguyên của tiến trình phải được khai báo trước bằng các Cung Nhu cầu (Claim edge) Pi • • •> Rj chỉ báo rằng Pi có thể sẽ yêu cầu Rj
- Cung Nhu cầu Pi • • •> Rj được chuyển thành Cung Yêu cầu (Request edge) Pi • • •> Rj khi Pi thực sự bắt đầu cần đến Rj .
- Nếu yêu cầu Pi • • •> Rj được HĐH đáp ứng, cung Pi • • •> Rj chuyển thành Cung Ấn định (Assignment edge) Pi <• • • Rj nối phiên bản duy nhất của Rj với Pi .
- Khi HĐH xét yêu cầu Pi • • •>Rj. Hệ chỉ cấp phát Rj cho Pi nếu Cung Ấn định Pi <• • • Rj không tạo ra vòng tròn đồng hướng trong RAG (xét cả các Cung Nhu cầu).
- Thuật giải có độ phức tạp o(n²) với n là số tiến trình trong hệ.

Ví dụ trách deadlock dùng RAG:
Đầu tiên khai báo tất cả các nhu cầu của P1 và P2:P1 và P2 có thể sử dụng R1,R2.

TranQuocLoc(I22A) đã viết: Để tìm ít nhất một chuỗi an toàn bằng thuật toán Nhà băng, chúng ta phải chọn P(i) sao cho Work >= Need(i). Vậy chọn P(i) như thế nào là thích hợp?
Ta có tập Work được khởi tạo bằng tập Available và duy trì bằng cách cộng dồn từng phiên bản của tài nguyên với tập Allcation(i). Vậy chúng ta có thể chọn P(i) là P(i) có “Allocation(i) lớn nhất trong tập Allocation”!
Allocation(i) lớn nhất phải thỏa mãn 2 điều kiện:
- Need(i) <= Work
- Tổng phiên bản của tài nguyên trong Allocation lớn nhất.
Tóm lại, ta có thuật toán tìm P(i) như sau:
Bước 1: Tạo tập Temp = {P(i) | Need(i) <= Work}
Bước 2: Chọn P(i) trong tập Temp có Allocation(i) lớn nhất (tổng các phiên bản là lớn nhất)
Ví dụ: Lấy lại bài tập trong Slide bài 8:
Thời điểm T0:
Available(3,3,2)

Process	Allocation	Max	Need
	A B C	A B C	A B C
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

Áp dụng công nghệ giải bài tập, ta có:

Work	Need(i)	P(i)	Allocation(i)
A B C	A B C		A B C
3 2 2	0 1 1	P3	2 1 1
5 3 3	1 2 2	P1	2 0 0
7 3 3	6 0 0	P2	3 0 2
10 3 5	4 3 1	P4	0 0 2
10 3 7	7 4 3	P0	0 1 0

- Với Work(3,2,2), ta có tập Temp = {P1(1,2,2), P3(0,1,1)}
sum(Allocation(1)) = 2+0+0 = 2
sum(Allocation(3)) = 2+1+1 = 4 -> Max Allocation
Vậy ta chọn P3.

- Với Work(5,3,3), ta có tập Temp = {P1(1,2,2), P4(4,3,1)}
sum(Allocation(1)) = 2+0+0 = 2
sum(Allocation(4)) = 0+0+2 = 2
Trường hợp có nhiều Max ta có thể chọn tùy ý -> Chọn P1

- Với Work(7,3,3), ta có tập Temp = {P2(6,0,0), P4(4,3,1)}
sum(Allocation(2)) = 3+0+2 = 5 -> Max Allocation
sum(Allocation(4)) = 0+0+2 = 2
Chọn P2.

- Với Work(10,3,5), ta có tập Temp = {P0(7,4,3), P4(4,3,1)}
sum(Allocation(0)) = 0+1+0 = 1
sum(Allocation(4)) = 0+0+2 = 2 -> Max Allocation
Chọn P4.

- Với Work(10,3,5), ta có tập Temp = {P0(7,4,3)}
sum(Allocation(0)) = 0+1+0 = 1 -> Max Allocation
Chọn P0.
Ta có chuỗi an toàn: {P3,P1,P2,P4,P0}

Bằng cách này chúng ta có thể tìm ra chuỗi an toàn nhanh nhất mà không mất thời gian bởi việc chọn nhầm Pi.

thanks bạn, nhưng kẻ bảng giống thầy nhìn dể hình dung hơn, dể hiu hơn

LeVanVan (I22B) đã viết:1/ Đặc điểm: Trong một deadlock, các quá trình không bao giờ hoàn thành việc thực thi và các tài nguyên hệ thống bị buộc chặt, ngăn chặn các quá trình khác bắt đầu.
...

Mình nghe thầy thường nói là xử trí Deadlock (xử trí và xử lý 1 cái chỉ phạm vi lớn ( xử trí) 1 cái chỉ phạm vi nhỏ ( xử lý))

TranQuocLoc(I22A) đã viết: Để tìm ít nhất một chuỗi an toàn bằng thuật toán Nhà băng, chúng ta phải chọn P(i) sao cho Work >= Need(i). Vậy chọn P(i) như thế nào là thích hợp?
Ta có tập Work được khởi tạo bằng tập Available và duy trì bằng cách cộng dồn từng phiên bản của tài nguyên với tập Allcation(i). Vậy chúng ta có thể chọn P(i) là P(i) có “Allocation(i) lớn nhất trong tập Allocation”!
Allocation(i) lớn nhất phải thỏa mãn 2 điều kiện:
- Need(i) <= Work
- Tổng phiên bản của tài nguyên trong Allocation lớn nhất.
Tóm lại, ta có thuật toán tìm P(i) như sau:
Bước 1: Tạo tập Temp = {P(i) | Need(i) <= Work}
Bước 2: Chọn P(i) trong tập Temp có Allocation(i) lớn nhất (tổng các phiên bản là lớn nhất)
Ví dụ: Lấy lại bài tập trong Slide bài 8:
Thời điểm T0:
Available(3,3,2)

Process	Allocation	Max	Need
	A B C	A B C	A B C
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

Áp dụng công nghệ giải bài tập, ta có:

Work	Need(i)	P(i)	Allocation(i)
A B C	A B C		A B C
3 2 2	0 1 1	P3	2 1 1
5 3 3	1 2 2	P1	2 0 0
7 3 3	6 0 0	P2	3 0 2
10 3 5	4 3 1	P4	0 0 2
10 3 7	7 4 3	P0	0 1 0

- Với Work(3,2,2), ta có tập Temp = {P1(1,2,2), P3(0,1,1)}
sum(Allocation(1)) = 2+0+0 = 2
sum(Allocation(3)) = 2+1+1 = 4 -> Max Allocation
Vậy ta chọn P3.

- Với Work(5,3,3), ta có tập Temp = {P1(1,2,2), P4(4,3,1)}
sum(Allocation(1)) = 2+0+0 = 2
sum(Allocation(4)) = 0+0+2 = 2
Trường hợp có nhiều Max ta có thể chọn tùy ý -> Chọn P1

- Với Work(7,3,3), ta có tập Temp = {P2(6,0,0), P4(4,3,1)}
sum(Allocation(2)) = 3+0+2 = 5 -> Max Allocation
sum(Allocation(4)) = 0+0+2 = 2
Chọn P2.

- Với Work(10,3,5), ta có tập Temp = {P0(7,4,3), P4(4,3,1)}
sum(Allocation(0)) = 0+1+0 = 1
sum(Allocation(4)) = 0+0+2 = 2 -> Max Allocation
Chọn P4.

- Với Work(10,3,5), ta có tập Temp = {P0(7,4,3)}
sum(Allocation(0)) = 0+1+0 = 1 -> Max Allocation
Chọn P0.
Ta có chuỗi an toàn: {P3,P1,P2,P4,P0}

Bằng cách này chúng ta có thể tìm ra chuỗi an toàn nhanh nhất mà không mất thời gian bởi việc chọn nhầm Pi.

Thanks, Bạn giải thích từng bước rõ thiệt

Ưu nhược điểm của ngăn chặn deathlock

+ Ưu điểm: ngăn chặn bế tắc (deadlock
prevention) là phương pháp tránh được bế
tắc bằng cách làm cho điều kiện cần không
được thỏa mãn
+ Nhược điểm:
- Giảm khả năng tận dụng tài nguyên và giảm
thông lượng của hệ thống
- Không mềm dẻo

Phần lớn, chúng ta có thể giải quyết vấn đề deadlock theo một trong ba cách:
• Chúng ta có thể sử dụng một giao thức để ngăn chặn hay tránh deadlocks, đảm bảo rằng hệ thống sẽ không bao giờ đi vào trạng thái deadlock
• Chúng ta có thể cho phép hệ thống đi vào trạng thái deadlock, phát hiện nó và phục hồi.
• Chúng ta có thể bỏ qua hoàn toàn vấn đề này và giả vờ deadlock không bao giờ xảy ra trong hệ thống. Giải pháp này được dùng trong nhiều hệ điều hành, kể cả UNIX.
• Chúng ta sẽ tìm hiểu vắn tắt mỗi phương pháp. Sau đó, chúng ta sẽ trình bày các giải thuật một cách chi tiết trong các phần sau đây.
Để đảm bảo deadlock không bao giờ xảy ra, hệ thống có thể dùng kế hoạch ngăn chặn hay tránh deadlock. Ngăn chặn deadlock là một tập hợp các phương pháp để đảm bảo rằng ít nhất một điều kiện cần không thể xảy ra. Các phương pháp này ngăn chặn deadlocks bằng cách ràng buộc yêu cầu về tài nguyên được thực hiện như thế nào. Chúng ta thảo luận phương pháp này trong phần sau.
Ngược lại, tránh deadlock yêu cầu hệ điều hành cung cấp những thông tin bổ sung tập trung vào loại tài nguyên nào một quá trình sẽ yêu cầu và sử dụng trong thời gian sống của nó. Với những kiến thức bổ sung này, chúng ta có thể quyết định đối với mỗi yêu cầu quá trình nên chờ hay không. Để quyết định yêu cầu hiện tại có thể được thoả mãn hay phải bị trì hoãn, hệ thống phải xem xét tài nguyên hiện có, tài nguyên hiện cấp phát cho mỗi quá trình, và các yêu cầu và giải phóng tương lai của mỗi quá trình.
Nếu một hệ thống không dùng giải thuật ngăn chặn hay tránh deadlock thì trường hợp deadlock có thể xảy ra. Trong môi trường này, hệ thống có thể cung cấp một giải thuật để xem xét trạng thái của hệ thống để xác định deadlock có xảy ra hay không và giải thuật phục hồi từ deadlock.
Nếu hệ thống không đảm bảo rằng deadlock sẽ không bao giờ xảy ra và cũng không cung cấp một cơ chế để phát hiện và phục hồi deadlock thì có thể dẫn đến trường hợp hệ thống ở trong trạng thái deadlock. Trong trường hợp này, deadlock không được phát hiện sẽ làm giảm năng lực hệ thống vì tài nguyên đang được giữ bởi những quá trình mà chúng không thể thực thi, đi vào trạng thái deadlock. Cuối cùng, hệ thống sẽ dừng các chức năng và cần được khởi động lại bằng thủ công.
Mặc dù phương pháp này dường như không là tiếp cận khả thi đối với vấn đề deadlock nhưng nó được dùng trong một số hệ điều hành. Trong nhiều hệ thống, deadlock xảy ra không thường xuyên; do đó phương pháp này là rẻ hơn chi phí cho phương pháp ngăn chặn deadlock, tránh deadlock, hay phát hiện và phục hồi deadlock mà chúng phải được sử dụng liên tục. Trong một số trường hợp, hệ thống ở trong trạng thái cô đặc nhưng không ở trạng thái deadlock. Như thí dụ, xem xét một quá trình thời thực chạy tại độ ưu tiên cao nhất (hay bất cứ quá trình đang chạy trên bộ định thời biểu không trưng dụng) và không bao giờ trả về điều khiển đối với hệ điều hành. Do đó, hệ thống phải có phương pháp phục hồi bằng thủ công cho các điều kiện không deadlock và có thể đơn giản sử dụng các kỹ thuật đó cho việc phục hồi deadlock.

- Một trạng thái được gọi là an toàn “safe” nếu tồn tại ít nhất một cách mà trong một khoảng thời gian hữu hạn nào đó, hệ thống có thể cấp phát tài nguyên thỏa mãn cho tất cả process thực thi hoàn tất .

- Khi đó hệ thống tồn tại một Chuỗi an toàn {P1, P2, … , Pn } bao gồm tất cả các tiến trình sao cho với mỗi Pi, các tài nguyên mà nó yêu cầu có thể được đáp ứng bởi số lượng hiện có cộng thêm của tất cả các Pj mà j < i.

- Nếu các TN yêu cầu không có đủ, Pi phải chờ cho đến khi tất cả các Pj trả lại các TN mà chúng chiếm giữ.

- Khi Pi nhận được đủ TN cần thiết, nó sử dụng và trả lại HĐH để Pi+1 có thể vận hành, cứ như thế cho đến Pn

- Khi một process yêu cầu một tài nguyên đang sẵn có, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay.

ngongocdiep06 (113A)

Tổng số bài gửi: 23
Join date: 16/07/2012

Ng0HaiQuan(i22B) đã viết:

TranQuocLoc(I22A) đã viết: Để tìm ít nhất một chuỗi an toàn bằng thuật toán Nhà băng, chúng ta phải chọn P(i) sao cho Work >= Need(i). Vậy chọn P(i) như thế nào là thích hợp?
Ta có tập Work được khởi tạo bằng tập Available và duy trì bằng cách cộng dồn từng phiên bản của tài nguyên với tập Allcation(i). Vậy chúng ta có thể chọn P(i) là P(i) có “Allocation(i) lớn nhất trong tập Allocation”!
Allocation(i) lớn nhất phải thỏa mãn 2 điều kiện:
- Need(i) <= Work
- Tổng phiên bản của tài nguyên trong Allocation lớn nhất.
Tóm lại, ta có thuật toán tìm P(i) như sau:
Bước 1: Tạo tập Temp = {P(i) | Need(i) <= Work}
Bước 2: Chọn P(i) trong tập Temp có Allocation(i) lớn nhất (tổng các phiên bản là lớn nhất)
Ví dụ: Lấy lại bài tập trong Slide bài 8:
Thời điểm T0:
Available(3,3,2)

Process	Allocation	Max	Need
	A B C	A B C	A B C
P0	0 1 0	7 5 3	7 4 3
P1	2 0 0	3 2 2	1 2 2
P2	3 0 2	9 0 2	6 0 0
P3	2 1 1	2 2 2	0 1 1
P4	0 0 2	4 3 3	4 3 1

Áp dụng công nghệ giải bài tập, ta có:

Work	Need(i)	P(i)	Allocation(i)
A B C	A B C		A B C
3 2 2	0 1 1	P3	2 1 1
5 3 3	1 2 2	P1	2 0 0
7 3 3	6 0 0	P2	3 0 2
10 3 5	4 3 1	P4	0 0 2
10 3 7	7 4 3	P0	0 1 0

- Với Work(3,2,2), ta có tập Temp = {P1(1,2,2), P3(0,1,1)}
sum(Allocation(1)) = 2+0+0 = 2
sum(Allocation(3)) = 2+1+1 = 4 -> Max Allocation
Vậy ta chọn P3.

- Với Work(5,3,3), ta có tập Temp = {P1(1,2,2), P4(4,3,1)}
sum(Allocation(1)) = 2+0+0 = 2
sum(Allocation(4)) = 0+0+2 = 2
Trường hợp có nhiều Max ta có thể chọn tùy ý -> Chọn P1

- Với Work(7,3,3), ta có tập Temp = {P2(6,0,0), P4(4,3,1)}
sum(Allocation(2)) = 3+0+2 = 5 -> Max Allocation
sum(Allocation(4)) = 0+0+2 = 2
Chọn P2.

- Với Work(10,3,5), ta có tập Temp = {P0(7,4,3), P4(4,3,1)}
sum(Allocation(0)) = 0+1+0 = 1
sum(Allocation(4)) = 0+0+2 = 2 -> Max Allocation
Chọn P4.

- Với Work(10,3,5), ta có tập Temp = {P0(7,4,3)}
sum(Allocation(0)) = 0+1+0 = 1 -> Max Allocation
Chọn P0.
Ta có chuỗi an toàn: {P3,P1,P2,P4,P0}

Bằng cách này chúng ta có thể tìm ra chuỗi an toàn nhanh nhất mà không mất thời gian bởi việc chọn nhầm Pi.

thanks bạn, nhưng kẻ bảng giống thầy nhìn dể hình dung hơn, dể hiu hơn

Đã có bảng kết quả rùi mà bạn còn làm thêm thế không phải là dư thừa ak

nguyenvankhoa59(122B) đã viết:
Đã có bảng kết quả rùi mà bạn còn làm thêm thế không phải là dư thừa ak

Tác giả bài viết diễn giải chi tiết như vậy mà sao thừa được bạn

Một hệ thống có 10 máy quét và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng các vector Allocation (3,1,1) và Max (9,4,8 ).
Dùng thuật giả nhà băng để
a. Chứng minh trạng thái này an toàn
b. Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3?
Giải
a.
Allocation = (3,1,1)
Max = (9,4,8 )
Avaible = 10 - (3+1+1) = 5

Process Allocation Max Need Available
P1 3 9 6 5
P2 1 4 3
P3 1 8 7


Bảng trợ giúp:
Work >= Needi Pi Allocation
5 3 P2 1
6 6 P1 3
9 7 P3 1

Tìm được chuỗi an toàn P2, P1, P3
Do đó trạng thái hệ thống ở thời điểm Ti là an toàn
b.
Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3
Gọi yêu cầu là Request3. Ta cáo Request3 = 1
Request3 =< Need3 (vì 1 =<7)
Request3 =< Available (vì 1 =<5)
Trạng thái mới của hệ thống
Allocation = (3,1,2)
Max = (9,4,8 )
Avaible = 10 - (3+1+2) = 4

Process Allocation Max Need Available
P1 3 9 6 4
P2 1 4 3
P3 2 8 6


Bảng trợ giúp:
Work >= Needi Pi Allocation
4 3 P2 1
5 ? ? ?

Cả 2 tiến trình P1 và P3 điều không thỏa điều kiện Work >= Needi (vì Need2 = 6, Need3 = 6)
Vậy ta không nên đáp ứng yêu cầu Request3 vì hệ thông sẽ không còn an toàn

QuangMinhTuan(I22B) đã viết:Deadlock là trạng thái xảy ra khi một nhóm tiến trình ngưng hoạt động trong thời gian dài do do một hay nhiều tiến trình trong nhóm chờ mãi mãi một sự kiện (event) phát sinh bởi một tiến trình khác hoặc trong nhóm đó.
Ví dụ: A vào thư viện mượn sách để đọc, nhưng B đã mượn trước nên A phải ngồi chờ khi B đọc xong đã.

- Tình huống ví dụ này là A phải ngồi chờ B đọc xong, vậy là thời gian đọc của B vẫn có thể hoàn thành được cho nên A không phải là chờ mãi mãi nên đây không phải là Deadlock.
- Cùng ví dụ trên để rơi vào Deadlock nếu A và B cùng muốn mượn 1 quyển sách ở thư viện, B mượn được trước nhưng không may bị mất quyển sách đó thì lúc đấy B không thể trả được quyển sách đó và A cũng không thể mượn được thì lúc đấy Deadlock mới xảy ra.

Ví Dụ Deadlock:
-Trong câu truyện ngụ ngôn :hai chú dê trắng và dê đen cùng tranh nhau đi qua một cây cầu mà không ai chịu nhường ai. Trong tình trạng này là Deadlock, xảy ra và không giải quyết được cả hai chú dê không giải quyết được và dẫn đến viêc cả hai rơi xuống cầu và chết.

-Trong đời thường có hai người A và người B cùng ở một khu vực mà khu vực đó chỉ có một tiệm bán gạo nhưng chẳng may hai người đều cần mua gạo về ăn nhưng tiệm chỉ còn mỗi một bao gạo nên không ai chịu nhường ai nên xảy ra tình trạng deadlock.

-Trong Học tập : ví dụ trong cuộc thi olympic cả hai bạn chơi A và B đều có điểm bằng nhau cho đến cuối cùng thế là hai bạn trả lời tiếp các câu hỏi phụ . Trong Tình huống này nếu hai bạn A và B đều không trả lời được hết những câu hỏi phụ thì sẽ xảy ra tình trang Deadlock. Deadlock chỉ chấm dứt cho đến khi một trong hai trả lời đúng và hơn bạn kia và giành chiến thắng.

Có mấy khái niệm này mình chưa hiểu bạn nào biết giúp mình với.
Available=?
Work=?
Request=?
Request(i)<=Need(i) && Request(i) <= Available là gì?
Thank.u

Bạn nào có thể giải thích rõ hơn về vi du hom nay của Thầy không ! Theo cách nói và làm của Thầy

*Điều kiện xuất hiện tắc nghẽn
Hệ thống sẽ xuất hiện tắc nghẽn khi và chỉ khi có đủ 4 điều kiện sau: + Điều kiện 1: Có sử dụng tài nguyên không thể chia sẻ
Mỗi thời điểm, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình ,
khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến
trình khác.
+ Điều kiện 2: Sự chiếm giữ và yêu cầu thêm tài nguyên không thể chia sẻ
Có tiến trình chiếm giữ các tài nguyên trong khi lại chờ được cấp phát thêm tài nguyên bị chiếm giữ bởi tiến trình khác.
+ Điều kiện 3: Không thu hồi tài nguyên từ tiến trình đang giữ chúng
Tài nguyên không thể được thu hồi từ tiến trình đang chiếm giữ chúng trước khi tiến trình này sử dụng chúng xong.
+ Điều kiện 4: Tồn tại một chu trình trong đồ thị cấp phát tài nguyên
Có ít nhất hai tiến trình chờ đợi lẫn nhau: tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình khác chiếm giữ và ngược lại.

Đồ thị cấp phát tài nguyên:
hình tròn là tiến trình, hình vuông là tài nguyên. Đối với tiến trình, mũi tên đi ra là chiếm giữ tài nguyên, mũi tên vào là yêu cầu tài nguyên. Ví dụ tiến trình A đang giữ tài nguyên R, tiến trình B yêu cầu tài nguyên S. Tiến trình C giữ U, yêu cầu T, tiến trình D giữ T, yêu cầu U. Tập hợp tiến trình {C,D} gọi là ở tình trạng tắc nghẽn.

nguyenhoanglam_I22B đã viết:Một hệ thống có 10 máy quét và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng các vector Allocation (3,1,1) và Max (9,4,8 ).
Dùng thuật giả nhà băng để
a. Chứng minh trạng thái này an toàn
b. Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3?
Giải
a.
Allocation = (3,1,1)
Max = (9,4,8 )
Avaible = 10 - (3+1+1) = 5

Process Allocation Max Need Available
P1 3 9 6 5
P2 1 4 3
P3 1 8 7


Bảng trợ giúp:
Work >= Needi Pi Allocation
5 3 P2 1
6 6 P1 3
9 7 P3 1

Tìm được chuỗi an toàn P2, P1, P3
Do đó trạng thái hệ thống ở thời điểm Ti là an toàn
b.
Xác định có nên đáp ứng hay không yêu cầu cấp thêm 1 máy cho tiến trình P3
Gọi yêu cầu là Request3. Ta cáo Request3 = 1
Request3 =< Need3 (vì 1 =<7)
Request3 =< Available (vì 1 =<5)
Trạng thái mới của hệ thống
Allocation = (3,1,2)
Max = (9,4,8 )
Avaible = 10 - (3+1+2) = 4

Process Allocation Max Need Available
P1 3 9 6 4
P2 1 4 3
P3 2 8 6


Bảng trợ giúp:
Work >= Needi Pi Allocation
4 3 P2 1
5 ? ? ?

Cả 2 tiến trình P1 và P3 điều không thỏa điều kiện Work >= Needi (vì Need2 = 6, Need3 = 6)
Vậy ta không nên đáp ứng yêu cầu Request3 vì hệ thông sẽ không còn an toàn

Bạn có thể giải thích lại phần cầu b không? Phần này mình chưa hiểu vấn đề.

Ba phương pháp:
• 1) Bảo đảm rằng hệ thống không rơi vào tình trạng deadlock bằng cách ngăn (preventing) hoặc tránh (avoiding) deadlock.
• Khác biệt
Ngăn deadlock: không cho phép (ít nhất) một trong 4 điều kiện cần cho deadlock
Tránh deadlock: các quá trình cần cung cấp thông tin về tài nguyên nó cần để hệ thống cấp phát tài nguyên một cách thích hợp
• 2) Cho phép hệ thống vào trạng thái deadlock, nhưng sau đó phát hiện deadlock và phục hồi hệ thống.
• 3) Bỏ qua mọi vấn đề, xem như deadlock không bao giờ xảy ra trong hệ thống.
Khá nhiều hệ điều hành sử dụng phương pháp này.
Deadlock không được phát hiện, dẫn đến việc giảm hiệu suất của hệ thống. Cuối cùng, hệ thống có thể ngưng hoạt động và phải được khởi động lại

1. Chấm dứt quá trình

Phục hồi hệ thống khỏi deadlock bằng cách Chấm dứt tất cả process bị deadlocked, hoặc Chấm dứt lần lượt từng process cho đến khi không còn deadlock
Sử dụng giải thuật phát hiện deadlock để xác định còn deadlock hay không
Dựa trên yếu tố nào để chọn process cần được chấm dứt?
Độ ưu tiên của process
Thời gian đã thực thi của process và thời gian còn lại
Loại tài nguyên mà process đã sử dụng
Tài nguyên mà process cần thêm để hoàn tất công việc
Số lượng process cần được chấm dứt
Process là interactive process hay batch process

2. Lấy lại tài nguyên

Lần lượt lấy lại tài nguyên từ các process, cấp phát chúng cho process khác cho đến khi không còn deadlock nữa.
Các vấn đề trong chiến lược thu hồi tài nguyên:
Chọn “nạn nhân”: chọn tài nguyên và process nào (có thể dựa trên số tài nguyên sở hữu, thời gian CPU đã tiêu tốn,...)?
Rollback: rollback process bị lấy lại tài nguyên trở về trạng thái safe, rồi tiếp tục process từ trạng thái đó. Do đó hệ thống cần lưu giữ một số thông tin về trạng thái các process đang thực thi.

- Mutual exclusion: với mỗi tài nguyên, chỉ có một process sử dụng tại một thời điểm.
- Hold and wait: một process vẫn sở hữu tài nguyên đã được cấp phát trong khi yêu cầu một tài ngyên khác.
- No preemption: một tài nguyên không thể bị đoạt lại từ chính process đang sở hữu tài nguyên đó.
- Circular wait: tồn tại một chu kỳ khép kín các yêu cầu tài nguyên.

*Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
- Với Circular Wait: Cấp TN theo một thứ tự nào đấy.

• Thế nào là trạng thái an toàn của hệ thống?
Một trạng thái được gọi là an toàn “safe” nếu tồn tại ít nhất một cách mà trong một khoảng thời gian hữu hạn nào đó, hệ thống có thể cấp phát tài nguyên thỏa mãn cho tất cả process thực thi hoàn tất .
Khi đó hệ thống tồn tại một Chuỗi an toàn {P1, P2, … , Pn } bao gồm tất cả các tiến trình sao cho với mỗi Pi, các tài nguyên mà nó yêu cầu có thể được đáp ứng bởi số lượng hiện có cộng thêm của tất cả các Pj mà j < i.
Nếu các TN yêu cầu không có đủ, Pi phải chờ cho đến khi tất cả các Pj trả lại các TN mà chúng chiếm giữ.
Khi Pi nhận được đủ TN cần thiết, nó sử dụng và trả lại HĐH để Pi+1 có thể vận hành, cứ như thế cho đến Pn
Khi một process yêu cầu một tài nguyên đang sẵn có, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay.
• Trình bày 4 cách ngăn chặn Deadlock.
Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:
- Với Mutual Exclusion: Đảm bảo TN(tai nguyên) nào cũng dùng chung được cùng một lúc bởi nhiều tiến trình.
- Với Hold and Wait:
1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.
2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.
- Với Circular Wait: Cấp TN theo một thứ tự nào đấy.

NguyenThiMai(I22A) đã viết:Trình bày khái niệm Deadlocks và ví dụ minh họa Deadlocks
- Khái niệm: Deadlocks là tình huống kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện có thể chỉ được gây ra bởi một tiến trình khác.
- Ví dụ:

• có 1 cái hang mà 2 con cua giành chiếm dẫn đến chúng ghanh ghét nhau, 2 con cùng chui vào hang vì cái hang hẹp nên những cái càng của chúng bị vướng vào nhau và rồi chúng bị rơi vào tình huống kẹt.

• 2 lớp học I22A và I22B đều cần thực hành.Trong khi đó phòng máy chỉ có 1 phòng trống => deadlock

• Giả sử tổng đài viettell có 20 tổng đài viên. Cùng 1 lúc có 20 khách gọi đến hỏi về những thắc mắc.Vào lúc này người thứ 21 gọi vào phải chờ => hiện tượng deadlock

Mình thấy 3 ví dụ của bạn này không đúng lắm, không biết các bạn nghĩ sao về 3 ví dụ của bạn này.
- Ví dụ về 2 lớp học thực hành nhưng chỉ có 1 phòng.
+ Trường hợp này lớp 1 học xong thì lớp 2 vẫn tiếp tục học được => Không bị Deadlock.
- Ví dụ tổng đài Vietell.
+ Cùng lúc 20 khách gọi đến thì có 20 tổng đài viên trả lời, nếu có khách thứ 21 gọi đến thì chờ 1 lúc rồi 1 trong 20 tổng đài viên kia trả lời xong. Thì lúc này vẫn đáp ứng khách thứ 21 được.

Kiến thức mình sơ sài mong Thầy và các Bạn giúp.

NguyenMinhTam(I22B) đã viết:

NguyenVanLanh (I22A) đã viết:

NguyenMinhTam(I22B) đã viết:deadlock là hiện tượng một tiến trình chiếm hữu tài nguyên lâu dài làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn chờ mãi mãi .
Cho em hỏi vậy mình chỉ có thể ngăn chăn deadlock thôi đúng không ạ. Deadlock có thể được xử lý và giải phóng không ạ

Theo mjh thì deadlock sẽ tự giải phóng được. Nhanh hoặc chậm tùy thuộc vào số tiến trình. Ít tiến trình tranh chấp tài nguyện thì thời gian thoát ra khỏi deadlock sẽ nhanh. Ngược lại nhiều tiến trình thì thời gian thoát ra tình trang deadloack chập hoặc rất chập. Do đoán được thời gian thoát ra tình trạng đang bị deadlock quá lâu để tránh mất thời gian thì khi đó con người sẽ can thiệp hoặc có công cụ hổ trợ khác.

Uhm,mình đồng ý kiến với bạn , biết là chờ mãi mãi.nhưng đọc 1 số tài liệu lại thấy có thể giải phóng để hếtdeadlock

Nhất trí với ý kiến của 2 bạn.

MaiXuanSon (I22B) đã viết:

NguyenThiMai(I22A) đã viết:Trình bày khái niệm Deadlocks và ví dụ minh họa Deadlocks
- Khái niệm: Deadlocks là tình huống kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện có thể chỉ được gây ra bởi một tiến trình khác.
- Ví dụ:

• có 1 cái hang mà 2 con cua giành chiếm dẫn đến chúng ghanh ghét nhau, 2 con cùng chui vào hang vì cái hang hẹp nên những cái càng của chúng bị vướng vào nhau và rồi chúng bị rơi vào tình huống kẹt.

• 2 lớp học I22A và I22B đều cần thực hành.Trong khi đó phòng máy chỉ có 1 phòng trống => deadlock

• Giả sử tổng đài viettell có 20 tổng đài viên. Cùng 1 lúc có 20 khách gọi đến hỏi về những thắc mắc.Vào lúc này người thứ 21 gọi vào phải chờ => hiện tượng deadlock

Mình thấy 3 ví dụ của bạn này không đúng lắm, không biết các bạn nghĩ sao về 3 ví dụ của bạn này.
- Ví dụ về 2 lớp học thực hành nhưng chỉ có 1 phòng.
+ Trường hợp này lớp 1 học xong thì lớp 2 vẫn tiếp tục học được => Không bị Deadlock.
- Ví dụ tổng đài Vietell.
+ Cùng lúc 20 khách gọi đến thì có 20 tổng đài viên trả lời, nếu có khách thứ 21 gọi đến thì chờ 1 lúc rồi 1 trong 20 tổng đài viên kia trả lời xong. Thì lúc này vẫn đáp ứng khách thứ 21 được.

Kiến thức mình sơ sài mong Thầy và các Bạn giúp.

Những ví dụ này tương tự như ví dụ về máy photocopy, nên những trường hợp này không thể xem là deadlock được. Những trường hợp này chỉ phải chờ một chút thôi.