Thảo luận Bài 8

doanhongdao030(I11C) đã viết:

Duongthithanhhuynh (I11C) đã viết:Bài tập: hệ thống có 12 ổ băng và 3 tiến trình
dùng thuật giải nhà băng chứng minh trạng thái này an toàn

tiến trình		Được cấp(ổ đĩa)		tối đa cần(ổ đĩa)
P1		5		10
P2		2		4
P3		2		9

-Available=12-9=3
-Need=Max-Allocation
P1=10-5=5
P2=4-2=2
P3=9-2=7

work	≥	Need	Pi		Allocation(i)
3		2	P2		2
5		5	P1		5
10		7	P3		2

-Tồn tại chuỗi an toàn T0={P2,P1,P3}
Vậy trạng thái tại thời điểm T0 là an toàn.

mình ko hiểu lắm.có ai làm rõ hơn ko

Chào doanhongdao030(I11C)
Bạn xem thử bài mình làm xem có dễ hiểu hơn không ha!


a. Chứng minh trạng thái này an toàn:
Available=12-(5+2+2)=3
Need[i]=Max[i] - Allocation[i]


=> Tồn tại chuỗi an toàn {P2,P1,P3}. Vậy hệ thống tại thời điểm Ti ở trạng thái an toàn.

Câu b thì mình chưa biết làm. Bạn nào biết thì làm cho mình tham khảo với ha

Duongthithanhhuynh (I11C) đã viết:Bài tập: hệ thống có 12 ổ băng và 3 tiến trình
dùng thuật giải nhà băng chứng minh trạng thái này an toàn

tiến trình		Được cấp(ổ đĩa)		tối đa cần(ổ đĩa)
P1		5		10
P2		2		4
P3		2		9

-Available=12-9=3
-Need=Max-Allocation
P1=10-5=5
P2=4-2=2
P3=9-2=7

work	≥	Need	Pi		Allocation(i)
3		2	P2		2
5		5	P1		5
10		7	P3		2

-Tồn tại chuỗi an toàn T0={P2,P1,P3}
Vậy trạng thái tại thời điểm T0 là an toàn.

Có thể trình bày luôn câu b không bạn???

nguyen huynh nhu (102C) đã viết:Một hệ thống có 3 máy quét hình và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên tại thời điểm Ti thể hiện bằng các vector Allocation= (0,2,1), và Max(2,2,2). Dùng thuật giải nhà băng để:
a. Chứng minh trạng thái này an toàn.
b. Xác định có đáp ứng được hay không yêu cầu thêm 1 máy nữa của P2.
Giải:

a) Allocation= (0,2,1) và Max= (2,2,2)
Available= 3-(0+2+1)=0
Tiến trình Đang giữ Max Hệ có
P1 0 2 0
P2 2 2
P3 1 2

=> Need= (2,2,2) - (0,2,1)= (2,0,1)
Tiến trình Need
P1 2
P2 0
P3 1

Work >= Need(i) P(i) Allocation(i)
0 0 P2 2
2 1 P3 1
3 2 P1 0

Tồn tại chuỗi an toàn= {P2,P3,P1}. Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

b) Request(2)= 1
Need(2)= 0
=> Request(2)> Need(2) (1> 0)
Vậy không thể đáp ứng được yêu cầu thêm 1 máy nữa của P2.

Mình không hiểu rõ câu b lắm??? Có ai giải thích dùm không??

HuynhPhuong (I11C) đã viết:

nguyen huynh nhu (102C) đã viết:Một hệ thống có 3 máy quét hình và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên tại thời điểm Ti thể hiện bằng các vector Allocation= (0,2,1), và Max(2,2,2). Dùng thuật giải nhà băng để:
a. Chứng minh trạng thái này an toàn.
b. Xác định có đáp ứng được hay không yêu cầu thêm 1 máy nữa của P2.
Giải:

a) Allocation= (0,2,1) và Max= (2,2,2)
Available= 3-(0 2 1)=0
Tiến trình Đang giữ Max Hệ có
P1 0 2 0
P2 2 2
P3 1 2

=> Need= (2,2,2) - (0,2,1)= (2,0,1)
Tiến trình Need
P1 2
P2 0
P3 1

Work >= Need(i) P(i) Allocation(i)
0 0 P2 2
2 1 P3 1
3 2 P1 0

Tồn tại chuỗi an toàn= {P2,P3,P1}. Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

b) Request(2)= 1
Need(2)= 0
=> Request(2)> Need(2) (1> 0)
Vậy không thể đáp ứng được yêu cầu thêm 1 máy nữa của P2.

Mình không hiểu rõ câu b lắm??? Có ai giải thích dùm không??

Câu b, để thỏa yêu cầu mới thì phải thỏa:
1. Request(i) <=Need(i)
2. Request(i) <=Available
sau khi xét 2 điều kiện này thì mới xét tiếp xem có tồn tại chuỗi an toàn khi có yêu cầu mới từ tiến trình hay không.
ở câu trên vì Request(2) > Need(2), nên không thể đáp ứng cho P2
Ở điều kiện 2 mình thấy slide của thầy ghi do không đủ tài nguyên. Còn điều kiện 1 cũng vậy phải không các bạn.

nguyenvulinh_i11c đã viết:- 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.

Trời, đọc không được gì hết bạn ơi.

vothihonggam đã viết:Tình huống kẹt của 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 (event) có thể chỉ được gây ra bởi một tiến trình khác.

ví dụ: 2 xe đi cùng chiều qua một cây cầu hẹp, mà cầu chỉ có một làn xe, nên khi 2 xe vào đến giữa cầu thì không thể tiếp tục tiến tới nữa, xãy ra kẹt xe (deadlock) vì không xe nào chịu nhường.

Deadlock là trạng thái xảy ra trong môi trường đa nhiệm khi 2 hoặc nhiều tiến trình đi vào vòng lặp chờ tài nguyên mãi mãi.

Định nghĩa Deadlock
- Trong hệ thống đa chương, nhiều quá trình có thể
cạnh tranh một số giới hạn tài nguyên.
- Một quá trình yêu cầu tài nguyên, nếu tài nguyên
không sẵn dùng tại thời điểm đó, quá trình đi vào
trạng thái chờ.
-Quá trình chờ có thể không bao giờ chuyển trạng thái
trở lại vì tài nguyên chúng yêu cầu bị giữ bởi những
quá trình khác
=>Trường hợp này gọi là deadlock(khóa chết).

Điều kiện cần để xảy ra deadlock :
Bốn điều kiện cần (necessary condition) để xảy ra
deadlock
1. Loại trừ tương hổ (Mutual exclusion): ít nhất một
tài nguyển được giữ trong chế độ không chia sẻ
2. Giữ và chờ cấp thêm tài nguyên (Hold and wait):
một process đang giữ ít nhất một tài nguyên và
đợi thêm tài nguyên do quá trình khác đang giữ
3. Không có ưu tiên (No preemption): tài nguyên không thể bị lấy lại,mà chỉ có thể được trả lại từ process đang giử tài nguyên đó khi nó muốn.
4. Chu trình (Circular wait): tồn tại một chu trình của các yêu cầu tài nguyên và tài nguyên đã được cấp phát.

Các giải pháp xử lý Deadlock:
a.Không giải quyết - Giải thuật đà điểu:
• Coi như không có vấn đề deadlock.
• Dựa trên cơ sở:
Deadlock rất ít xảy ra.
Chi phí giải quyết rất cao.
• Được dùng trên các hệ điều hành: Unix, Windows.
b.Phát hiện và phục hồi từ deadlock:
• Phát hiện deadlock:
Dùng các giải thuật phát hiện vòng chờ các process.
Do người quản trị hệ thống.
• Phục hồi từ deadlock:
Kết thúc các process bị deadlock.
Kết thúc tất cả các process bị deadlock.
Lần lượt kết thúc các process bị deadlock cho đến khi hết deadlock.
Thông số chọn process để kết thúc:
Độ ưu tiên.
Thời gian đã thực thi.
Thời gian còn lại.
Số tài nguyên đã cấp phát.
Số tài nguyên đang chờ.
Lấy lại tài nguyên từ process.
Lần lượt lấy lại các tài nguyên đã cấp phát cho các process cho đến khi hết deadlock.
Phụ thuộc bản chất của tài nguyên.
Sử dụng công cụ của hệ điều hành.
Phục hồi các điểm kiểm tra.
Định kỳ tạo các điểm kiểm tra (checkpoint).
Lưu trạng thái hệ thống tại điểm kiểm tra.
Thực hiện lại (rollback) các process bị deadlock tại các điểm kiểm tra.
Lần lượt thực hiện lại các process bị deadlock tại các điểm kiểm tra cho đến khi hết deadlock.
c.Ngăn chặn deadlock:
Loại bỏ các điều kiện dẫn đến deadlock.
Các điều kiện xem như không thể loại bỏ:
Loại trừ tương hỗ.
Không lấy lại tài nguyên từ process.
• Loại bỏ điều kiện loại trừ tương hỗ:
Giảm số tài nguyên tranh chấp.
Tăng số lượng tài nguyên.
Cấp phát tài nguyên dạng spool.
Vd: chỉ 1 printer daemon dùng máy in.
Các process gởi yêu cầu cho printer daemon.
• Loại bỏ điều kiện giữ và chờ tài nguyên:
Nguyên tắc: process không được giữ tài nguyên khi yêu cầu tài nguyên mới.
Process khai báo tài nguyên và được cấp phát 1 lần.
Nếu process yêu cầu tài nguyên và không được cấp phát thì phải trả các tài nguyên đang giữ.
• Loại bỏ điều kiện không lấy lại tài nguyên:
Lấy lại tài nguyên từ process.
Không thể với tài nguyên như máy in.
• Loại bỏ vòng chờ các process:
Có thể quy định số thứ tự tài nguyên.
Process chỉ được yêu cầu tài nguyên theo thứ tự tăng.
Giả sử có deadlock:
P1 giữ Ri, chờ Rj -> i < j.
P2 giữ Rj, chờ Rj -> j < i.
d.Tránh deadlock:
• Chấp nhận các điều kiện tạo deadlock.
• Theo dõi và tránh dẫn đến deadlock.
• Hai hướng giải quyết.
• Không tạo process mới nếu có thể dẫn đến deadlock.:
Process cần khai báo số lượng tài nguyên cần sử dụng.
Không tạo process mới nếu số lượng tài nguyên hệ thống không đủ, có thể dẫn đến deadlock.
• Không cấp phát thêm tài nguyên cho process:
Liên quan đến việc sử dụng tài nguyên trong tương lai của các process.
Định nghĩa trạng thái hệ thống với:
Vector E: tổng số các loại tài nguyên.
Vector A: số tài nguyên mỗi loại chưa dùng.
Ma trận C: số tài nguyên đã cấp phát cho các process.
Ma trận R: số lượng tài nguyên các process sẽ tiếp tục yêu cầu.

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 (trong phần VI.4.1) 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.

Trạng thái an toàn
Một trạng thái là an toàn nếu hệ thống có thể cấp phát các tài nguyên tới mỗi
quá trình trong một vài thứ tự và vẫn tránh deadlock. Hay nói cách khác, một hệ thống
ở trong trạng thái an toàn chỉ nếu ở đó tồn tại một thứ tự an toàn. Thứ tự của các quá
trình <P1, P2, …, Pn> là một thứ tự an toàn cho trạng thái cấp phát hiện hành nếu đối với mỗi thứ tự Pi, các tài nguyên mà Pi yêu cầu vẫn có thể được thoả mãn bởi tài
nguyên hiện có cộng với các tài nguyên được giữ bởi tất cả Pj, với j<i. Trong trường
hợp này, nếu những tài nguyên mà quá trình Pi yêu cầu không sẳn dùng tức thì thì Pi
có thể chờ cho đến khi tất cả Pj hoàn thành. Khi chúng hoàn thành, Pi có thể đạt được
tất cả những tài nguyên nó cần, hoàn thành các tác vụ được gán, trả về những tài
nguyên được cấp phát cho nó và kết thúc. Khi Pi kết thúc, Pi+1 có thể đạt được các tài
nguyên nó cần,... Nếu không có thứ tự như thế tồn tại thì trạng thái hệ thống là không
an toàn.
Một trạng thái an toàn không là trạng thái deadlock. Do đó, trạng thái
deadlock là trạng thái không an toàn. Tuy nhiên, không phải tất cả trạng thái không an
toàn là deadlock (hình VI-4). Một trạng thái không an toàn có thể dẫn đến deadlock.
Với điều kiện trạng thái là an toàn, hệ điều hành có thể tránh trạng thái không an toàn
(và deadlock). Trong một trạng thái không an toàn, hệ điều hành có thể ngăn chặn các
quá trình từ những tài nguyên đang yêu cầu mà deadlock xảy ra: hành vi của các quá
trình này điều khiển các trạng thái không an toàn.
Để minh hoạ, chúng ta xét một hệ thống với 12 ổ băng từ và 3 quá trình: P0,
P1, P2. Quá trình P0 yêu cầu 10 ổ băng từ, quá trình P1 có thể cần 4 và quá trình P2 có
thể cần tới 9 ổ băng từ. Giả sử rằng tại thời điểm t0, quá trình P0 giữ 5 ổ băng từ, quá
trình P1 giữ 2 và quá trình P2 giữ 2 ổ băng từ. (Do đó, có 3 ổ băng từ còn rảnh).
Nhu cầu tối đa Nhu cầu hiện tại
P0 10 5
P1 4 2
P2 9 2
Tại thời điểm t0, hệ thống ở trạng thái an toàn. Thứ tự <P1,P0, P2> thoả điều kiện
an toàn vì quá trình P1 có thể được cấp phát tức thì tất cả các ổ đĩa từ và sau đó trả lại
chúng (sau đó hệ thống có 5 ổ băng từ sẳn dùng ), sau đó quá trình P0 có thể nhận tất
cả ổ băng từ và trả lại chúng (sau đó hệ thống sẽ có 10 ổ băng từ sẳn dùng), và cuối
cùng quá trình P2 có thể nhận tất cả ổ băng từ của nó và trả lại chúng (sau đó hệ thống
sẽ có tất cả 12 ổ băng từ sẳn dùng).
Một hệ thống có thể đi từ trạng thái an toàn tới một trạng thái không an toàn.
Giả sử rằng tại thời điểm t1, quá trình P2 yêu cầu và được cấp 1 ổ băng từ nữa. Hệ
thống không còn trong trạng thái an toàn. Tại điểm này, chỉ quá trình P1 có thể được
cấp tất cả ổ băng từ của nó. Khi nó trả lại chúng, chỉ quá trình P1 có thể được cấp phát
tất cả ổ băng từ. Khi nó trả lại chúng, hệ thống chỉ còn 4 ổ băng từ sẳn có. Vì quá trình P0 được cấp phát 5 ổ băng từ, nhưng có tối đa 10, quá trình P0 phải chờ. Tương
tự, quá trình P2 có thể yêu cầu thêm 6 ổ băng từ và phải chờ dẫn đến deadlock.
Lỗi của chúng ta là gán yêu cầu từ quá trình P2 cho 1 ổ băng từ nữa. Nếu chúng
ta làm cho P2 phải chờ cho đến khi các quá trình khác kết thúc và giải phóng tài
nguyên của nó thì chúng ta có thể tránh deadlock.
Với khái niệm trạng thái an toàn được cho, chúng ta có thể định nghĩa các giải
thuật tránh deadlock. Ý tưởng đơn giản là đảm bảo hệ thống sẽ luôn còn trong trạng
thái an toàn. Khởi đầu, hệ thống ở trong trạng thái an toàn. Bất cứ khi nào một quá
trình yêu cầu một tài nguyên hiện có, hệ thống phải quyết định tài nguyên có thể được
cấp phát tức thì hoặc quá trình phải chờ. Yêu cầu được gán chỉ nếu việc cấp phát để
hệ thống trong trạng thái an toàn.
Trong mô hình này, nếu quá trình yêu cầu tài nguyên đang có, nó có thể vẫn
phải chờ. Do đó, việc sử dụng tài nguyên có thể chậm hơn mà không có giải thuật
tránh deadlock.
[img][/img]

Giải thích thuật giải Nhà băng
Dữ liệu : – có 5 tiến trình : P0,……,P4 (Ví dụ là : 5 công ty khác nhau cần vay )
- 3 loại tài nguyên : A(10 phiên bản), B(5 phiên bản), C(7 phiên bản)
=>Đây là các loại tiền mà nhà băng có.
- Tại thời điểm To:
Allocation Max Available
A B C A B C A B C
Po 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
Tổng loại tiền mà các công ty có (Cộng theo cột từ trên xuống của Allocation)
Tổng :7 2 5
Chú ý :
- Allocation tổng số các loại tiền mà các công ty đang có
- Max : Tổng các loại tiền (tối đa ) mà các công ty có thể có
- Hệ có : Available = ( 10 ,5 ,7 ) – ( 7, 2 ,5 ) = ( 3 ,3 ,2 )
Ta có : Need = Max – Allocation
=>Số loại tiền tối đa mà các công ty có thể vay thêm.
Ta có ma trận sau : Need
A B C
P0 7 4 3 (7,5,3) – (0,1,0)
P1 1 2 2 (3,2,2) – (2,0,0)
P2 6 0 0 (9,0,2) - (3,0,2)
P3 0 1 1 (2,2,2) - (2,1,1)
P4 4 3 1 (4,3,3) – (0,0,2)
Giả sử tại thời điểm To công ty : Ta phải kiểm tra tổng số các loại tiền mà công ty cần : Need <= Work : hệ số các loại tiền có trong nhà băng. Trong thời điểm này thì chỉ có P1,P3 là thỏa điều kiện được vay trước.
Giả sử P1 vay trước : Ta có bảng sau đảm bảo số tiền vay không vượt qua số tiền nhà băng cần có.
Work Need(i) P(i) Allocation
A B C A B C A B C
3 2 2 1 2 2 P1 2 0 0
Số tiền ít nhất nhà băng cần có cho P1 vay là (3,2,2)
Vậy hệ số tiền mà nhà băng có ít nhẩt cho công ty tiếp theo vay là:
Work = (3,2,2)+(2,0,0) = (5,3,2)
Ta xét hệ số các loại tiền Need <=Work. Trong trường hợp này thì P1 và P4 có thể vay.Giả sử P3 vay.Và làm các bước tương tự cho các công ty còn lại ta có bảng sau
Work Need(i) P(i) Allocation
A B C A B C A B C
3 2 2 1 2 2 P1 2 0 0
5 3 2 0 1 1 P3 2 1 1
7 4 3 4 3 1 P4 0 0 2
7 4 5 6 0 0 P2 3 0 2
10 4 7 7 4 3 P0 0 1 0
Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu
Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 >
P1 muốn tăng tiền vay (1,0,2) thì phải thỏa điều kiện:
1 – Request (yêu cầu) <= Need vì (1,0,2) <= (1,2,2) // Thỏa điều kiện
2- Request (yêu cầu) <= Available vì (1,0,2) <= (3,3,2) // Thỏa điều kiện
Ta lại làm lại từ đầu và xét trạng thái mới
Ta có:
Bảng Max sẽ được thay bằng bảng Need (Vì Need đã là giá trị lớn nhất để có thể tồn tại chuổi an toàn).
Allocation của P1 sẽ đổi do cộng đồn giá trị Allocation ban đầu với giá trị Allocation mới:
(2,0,0) + (1,0,2) = (3,0,2)
Need của P1 cũng thay đổi do điều kiện xét ta có:
Need (P1)[mới] = Need(P1)[cũ] – Request = (1,2,2) – (1,0,2) = (0,2,0)
Available cũng thay đổi do:
Available (mới) = Available (củ) – Request = (3,3,2,) – (1,0,2) = (2,3,0)
Allocation Need Available
A B C A B C A B C
Po 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
Work Need(i) P(i) Allocation
A B C A B C A B C
2 3 0 0 2 0 P1 3 0 2
5 3 2 0 1 1 P3 2 1 1
7 4 3 4 3 1 P4 0 0 2
7 4 5 6 0 0 P2 3 0 2
104 7 7 4 3 P0 0 1 0
Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu
Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 >

Nếu chúng ta có một hệ thống cấp phát tài nguyên với một thể hiện của mỗi loại, một biến dạng của đồ thị cấp phát tài nguyên được định nghĩa trong phần VI.4.2 có thể được dùng để tránh deadlock.

Ngoài các cạnh yêu cầu và gán, chúng ta giới thiệu một loại cạnh mới được gọi là cạnh thỉnh cầu (claim edge). Một cạnh thỉnh cầu Pi  Rj hiển thị quá trình Pi có thể yêu cầu tài nguyên Rj vào một thời điểm trong tương lai. Cạnh này tương tự cạnh yêu cầu về phương hướng nhưng được hiện diện bởi dấu đứt khoảng. Khi quá trình Pi yêu cầu tài nguyên Rj, cạnh thỉnh cầu Pi  Rj chuyển tới cạnh yêu cầu. Tương tự, khi một tài nguyên Rj được giải phóng bởi Pi, cạnh gán Rj  Pi được chuyển trở lại thành cạnh thỉnh cầu Pi  Rj. Chúng ta chú ý rằng các tài nguyên phải được yêu cầu trước trong hệ thống. Nghĩa là, trước khi Pi bắt đầu thực thi, tất cả các cạnh thỉnh cầu của nó phải xuất hiện trong đồ thị cấp phát tài nguyên. Chúng ta có thể giảm nhẹ điều kiện này bằng cách cho phép một cạnh Pi  Rj để được thêm tới đồ thị chỉ nếu tất cả các cạnh gắn liền với quá trình Pi là các cạnh thỉnh cầu.

Giả sử rằng Pi yêu cầu tài nguyên Rj. Yêu cầu có thể được gán chỉ nếu chuyển cạnh yêu cầu Pi  Rj tới cạnh gán RjPi không dẫn đến việc hình thành chu trình trong đồ thị cấp phát tài nguyên. Chú ý rằng chúng ta kiểm tra tính an toàn bằng cách dùng giải thuật phát hiện chu trình. Một giải thuật để phát hiện một chu trình trong đồ thị này yêu cầu một thứ tự của n2 thao tác, ở đây n là số quá trình trong hệ thống.
Nếu không có chu trình tồn tại, thì việc cấp phát tài nguyên sẽ để lại hệ thống trong trạng thái an toàn. Nếu chu trình được tìm thấy thì việc cấp phát sẽ đặt hệ thống trong trạng thái không an toàn. Do đó, quá trình P­i sẽ phải chờ yêu cầu của nó được thoả.

Để minh hoạ giải thuật này, chúng ta xét đồ thị cấp phát tài nguyên của hình VI-5. Giả sử rằng P2 yêu cầu R2. Mặc dù R2 hiện rảnh nhưng chúng ta không thể cấp phát nó tới P2 vì hoạt động này sẽ tạo ra chu trình trong đồ thị .Một chu trình hiển thị rằng hệ thống ở trong trạng thái không an toàn. Nếu P1 yêu cầu R2 và P2 yêu cầu R1 thì deadlock sẽ xảy ra.

Các phương pháp xử lý deadlock

 chúng ta có thể sử dụng một giao thức để ngăn chặn hay tránhddeadlocks,đảm bảo răng hệ thống sẽ không bao giờ đi vào trạng thái deadlocks
 chúng ta có thể cho phép hệ thống đi vào trạng thái deadlock,phát hiện no 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ờ sảy ra trong hê thống.giải pháp này được dùng nhiều trong hệ điều hành, kể cả UNIX.

Để đảm bảo deadlock không bao giờ sả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à 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 sảy ra deadlock không thể sảy ra,các phương pháp này ngăn chặn deadlock bằng ràng buộc các yêu cầu về tài nguyên .
Ngược lại ,tránh deadlock yêu cầu hệ điều hành cung cấpnhuwng thông tin bổ sung tập trung vào loại tài nguyen nào là một quá trình sẽ yêu cầu và sử dụng trong thời gian sống của nó.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 hiện tại có thể thỏa mãn hay bị trì hoãn,hệ thống phải xem sét tài nguyên hiện có,tài nguyên hiện cấp phát cho mỗi quá trình,các yêu cầu và giải phóng tương lai của mỗi quá trình.
Nếu 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 trang 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 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 khả thi 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 ta sử dụng lien 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.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.

Hay lắm, cảm ơn các bạn nhiều.

Deadlock : Là Một số tiến trình có thể tranh nhau bởi một số tài nguyên hạn chế.
Tài nguyên hệ thống được chia thành nhiều loại, mỗi loại có 1 hoặc nhiều phiên bản(Instances).
+ Các tiến trình chờ có thể sẽ không bao giờ thay đổi lại trạng thái được vì các tài nguyên mà nó yêu cầu bị giữ bởi các tiến trình chờ khác.
+ Mỗi tiến trình sử dụng tài nguyên theo các bước sau:
• yêu cầu tài nguyên(request): Nếu yêu cầu không được giải quyết ngay( ví dụ khi tài nguyên đang được tiến trình khác sử dụng) thì tiến trình yêu cầu phải đợi cho đến khi nhận được tài nguyên.
• Sử dụng tài nguyên(use)
• Trả lại(Release): Trả tài nguyên cho HĐH quản lý.
Ví dụ1: Hiện tượng tắc nghẽn trên cầu:
+Hai(hay nhiều hơn) ô tô đối đầu nhau trên một cây cầu hẹp chỉ đủ độ rộng cho một chiếc.
+ Mỗi đoạn của cây cầu có thể xem như một tài nguyên
+ Nếu deadlock xuất hiện, nó có thể được giải quyết nếu một hay một số ô tô lùi lại nhường đường rồi tiển ra sau.
Ví dụ 2: Hiện tượng kẹt mạng tại tổng đài 1080:
+ ví dụ tổng đài 1080 gồm có 100 điện thoại viên.
+ 100 khách hàng gọi tới cùng một lúc. Khách hàng 101,102…. Gọi tới, sẽ phải chờ.
+ 1 khách hàng ứng với một điện thoại viên có thể xem như một tài nguyên.
+ nếu deadlock xuất hiện, nó có thể được giải quyết nếu 1 trong 100 khách hàng đã được điện thoại viên trả lời xong và nhường tài nguyên cho các khách hàng tiếp theo...

Để 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.
.

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 (trong phần VI.4.1) 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.

Để deadlock xảy ra, một trong bốn điều kiện cần phải xảy ra. Bằng cách đảm
bảo ít nhất một trong bốn điều kiện này không thể xảy ra, chúng ta có thể ngăn chặn
việc xảy ra của deadlock. Chúng ta tìm hiểu tỷ mỹ tiếp cận này bằng cách xem xét
mỗi điều kiện cần riêng rẻ nhau.

Chào Thầy và các bạn
-Thầy ơi cho em hỏi là: Trong thuật giải nhà băng mình đi tìm chuỗi an toàn .
Ví dụ: Có 4 tiến trình từ [ P1, P2, P3, P4 ] vậy lúc mình tìm chuỗi an toàn em vét theo thứ tự từ P1 đến P4, nếu như P1 thoả điều kiện thì em tiếp tục xét tiếp P2. Giả sử P2 không thoả điều kiện thì mình có xét tiếp P3 và P4 không Thầy hay là khi P2 không thoả thì mình kết luận liền là "Không tìm được chuỗi an toàn".
- Thầy hướng dẫn giúp em nhé!

Admin
- Em xét theo thứ tự từ đầu đến cuối là đúng. Chú ý: Tiến trình nào lấy được rồi thì bỏ qua.
- Nếu trong quá trình xét, tiến trình nào đó không thoả, thì chuyển sang tiến trình kế tiếp. Nếu thoả, hãy chọn nó.
- Xét đến cùng mà không tìm được tiến trình nào thoả, nghĩa là không tồn tại chuỗi an toàn (chỉ tìm được phần đầu của chuỗi hay thậm chí chuỗi hoàn toàn rỗng).

chauchanduong (I11C) đã viết:Chào Thầy và các bạn
-Thầy ơi cho em hỏi là: Trong thuật giải nhà băng mình đi tìm chuỗi an toàn .
Ví dụ: Có 4 tiến trình từ [ P1, P2, P3, P4 ] vậy lúc mình tìm chuỗi an toàn em vét theo thứ tự từ P1 đến P4, nếu như P1 thoả điều kiện thì em tiếp tục xét tiếp P2. Giả sử P2 không thoả điều kiện thì mình có xét tiếp P3 và P4 không Thầy hay là khi P2 không thoả thì mình kết luận liền là "Không tìm được chuỗi an toàn".
- Thầy hướng dẫn giúp em nhé!

Admin
- Em xét theo thứ tự từ đầu đến cuối là đúng. Chú ý: Tiến trình nào lấy được rồi thì bỏ qua.
- Nếu trong quá trình xét, tiến trình nào đó không thoả, thì chuyển sang tiến trình kế tiếp. Nếu thoả, hãy chọn nó.
- Xét đến cùng mà không tìm được tiến trình nào thoả, nghĩa là không tồn tại chuỗi an toàn (chỉ tìm được phần đầu của chuỗi hay thậm chí chuỗi hoàn toàn rỗng).

Mình cảm ơn bạn đã đưa ra câu hỏi này nha, mình cũng đang thắc mắc cho này, giờ thì mình rõ rồi.
Em cám ơn thầy đã giải đáp

- 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 nguyê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 trình khép kín các yêu cầu tài nguyên.

doanhongdao030(I11C) đã viết:

Duongthithanhhuynh (I11C) đã viết:Bài tập: hệ thống có 12 ổ băng và 3 tiến trình
dùng thuật giải nhà băng chứng minh trạng thái này an toàn

tiến trình		Được cấp(ổ đĩa)		tối đa cần(ổ đĩa)
P1		5		10
P2		2		4
P3		2		9

-Available=12-9=3
-Need=Max-Allocation
P1=10-5=5
P2=4-2=2
P3=9-2=7

work	≥	Need	Pi		Allocation(i)
3		2	P2		2
5		5	P1		5
10		7	P3		2

-Tồn tại chuỗi an toàn T0={P2,P1,P3}
Vậy trạng thái tại thời điểm T0 là an toàn.

mình ko hiểu lắm.có ai làm rõ hơn ko

Mình xin giải theo cách hiểu của mình!
Allocation = (5,2,2)
Max = (10,4,9)
Need = Max - Allocation = (5,2,7)
Available = 12 - (5+2+2)=3

P[i]	Need	Max	Allocation	Available
P1	5	10	5	3
P2	2	4	2
P3	7	9	2

tìm chuỗi an toàn

Word >=	Need	Pi	Allocation
3	2	P2	2
5	5	P1	5
10	7	P3	2

Vậy tồn tại chuỗi an toàn là <P2,P1,P3>

BuiHuuThanhLuan(I11C) đã viết:

HuynhPhuong (I11C) đã viết:

nguyen huynh nhu (102C) đã viết:Một hệ thống có 3 máy quét hình và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên tại thời điểm Ti thể hiện bằng các vector Allocation= (0,2,1), và Max(2,2,2). Dùng thuật giải nhà băng để:
a. Chứng minh trạng thái này an toàn.
b. Xác định có đáp ứng được hay không yêu cầu thêm 1 máy nữa của P2.
Giải:

a) Allocation= (0,2,1) và Max= (2,2,2)
Available= 3-(0 2 1)=0
Tiến trình Đang giữ Max Hệ có
P1 0 2 0
P2 2 2
P3 1 2

=> Need= (2,2,2) - (0,2,1)= (2,0,1)
Tiến trình Need
P1 2
P2 0
P3 1

Work >= Need(i) P(i) Allocation(i)
0 0 P2 2
2 1 P3 1
3 2 P1 0

Tồn tại chuỗi an toàn= {P2,P3,P1}. Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.

b) Request(2)= 1
Need(2)= 0
=> Request(2)> Need(2) (1> 0)
Vậy không thể đáp ứng được yêu cầu thêm 1 máy nữa của P2.

Mình không hiểu rõ câu b lắm??? Có ai giải thích dùm không??

Câu b, để thỏa yêu cầu mới thì phải thỏa:
1. Request(i) <=Need(i)
2. Request(i) <=Available
sau khi xét 2 điều kiện này thì mới xét tiếp xem có tồn tại chuỗi an toàn khi có yêu cầu mới từ tiến trình hay không.
ở câu trên vì Request(2) > Need(2), nên không thể đáp ứng cho P2
Ở điều kiện 2 mình thấy slide của thầy ghi do không đủ tài nguyên. Còn điều kiện 1 cũng vậy phải không các bạn.

Thanks nha

chauchanduong (I11C) đã viết:Chào Thầy và các bạn
-Thầy ơi cho em hỏi là: Trong thuật giải nhà băng mình đi tìm chuỗi an toàn .
Ví dụ: Có 4 tiến trình từ [ P1, P2, P3, P4 ] vậy lúc mình tìm chuỗi an toàn em vét theo thứ tự từ P1 đến P4, nếu như P1 thoả điều kiện thì em tiếp tục xét tiếp P2. Giả sử P2 không thoả điều kiện thì mình có xét tiếp P3 và P4 không Thầy hay là khi P2 không thoả thì mình kết luận liền là "Không tìm được chuỗi an toàn".
- Thầy hướng dẫn giúp em nhé!

Admin
- Em xét theo thứ tự từ đầu đến cuối là đúng. Chú ý: Tiến trình nào lấy được rồi thì bỏ qua.
- Nếu trong quá trình xét, tiến trình nào đó không thoả, thì chuyển sang tiến trình kế tiếp. Nếu thoả, hãy chọn nó.
- Xét đến cùng mà không tìm được tiến trình nào thoả, nghĩa là không tồn tại chuỗi an toàn (chỉ tìm được phần đầu của chuỗi hay thậm chí chuỗi hoàn toàn rỗng).

Mình nghĩ nếu bạn học kỹ hiểu được cách cấp phát tài nguyên (hãy liên hệ với ví dụ quản lý tiền ngân hàng của thầy cho là bạn dễ hiểu hơn ) thì bạn sẽ biết vì sao cấp phát như thế thì sẽ ở trong trạng thái an toàn. (Mình hiểu là cấp phát theo cách này thì lỡ tiến trình yêu cầu tài nguyên mà chưa có phải chờ thì cũng không bao giờ DEADLOCK ( phải chờ mãi mãi ) nếu trạng thái đó tồn tại chuỗi an toàn và hệ thống cấp phát tài nguyên theo thuật giải nhà băng )
Làm theo phương pháp vét cạn như vậy sẽ tốn thời gian và công sức tính toán hơi nhiều khi không cần thiết đó. Để làm nhanh và chính xác bài toán này và ít nhầm lẫn mình nghĩ nên làm theo các bước sau :
1. Tính hệ có Available= (Tổng các loại tài nguyên-viết theo ma trận nếu nhiều)-(Tổng các loại tài nguyên mà các tiến trình đang giữ-viết theo ma trận nếu nhiều) . Trừ theo phương pháp ma trận nếu có nhiều loại tài nguyên nha mấy bạn.
2. Tính Need(i) của mỗi tiến trình.
3.Vẽ bảng gồm 4 cột với tên cột theo thứ tự work,need(i),P(i),Allocation(i). Nhớ chú ý cái tên loại tài nguyên ABC mà thầy nhắc trên lớp .
4.Đầu tiên viết số tài nguyên mà hệ có tính được vào dòng đầu tiên ở cột "WORK".
5.Đưa mắt nhìn nhanh tìm xem tiến trình nào chưa xét có need(i)<work đã viết ở dòng dưới cùng (chứ chẳng cần viết nháp tính từng cái 1 từ trên xuống đâu).
- Nếu không có need(i) nào thỏa điều kiện thì =>Kết luận :"Không tồn tại chuỗi an toàn nên trạng thái ở thời điểm... là không an toàn". =>kết thúc bài toán.
- Nếu có thì viết tiếp các số liệu của tiến trình P(i) vừa tìm được vào hàng đang viết như sau: Need(i),P(i) là tên tiến trình mới tìm,Allocation là số tài nguyên ban đầu tiến trình đang giữ (đề cho ban đầu) =>Loại bỏ tiến trình mới viết để lần sau không xét nữa=>qua bước 6.
6.
+Nếu vẫn còn tiến trình để xét: Tính work ở dòng dưới =work ở dòng sát trên + Allocation ở dòng sát trên và viết vào cột work =>trở về lại bước 5.
+Nếu đã hết tiến trình để xét=>Đã tìm thấy 1 chuỗi an toàn (có thể có nhiều chuỗi nha, chỉ cần tìm 1 là đủ rồi, còn nếu muốn tìm hết chuỗi an toàn thì hãy theo phương pháp vét cạn). Kết luận :"Tồn tại chuỗi an toàn bằng (liệt kê tên các tiến trình trong cột P(i) từ trên xuống dưới. Vậy trạng thái ở thời điểm ... là an toàn."

Xong cách tìm chuỗi an toàn ở dữ liệu cho trước. Và cách xác định trạng thái có an toàn hay không ở thời điểm ... bằng cách xác định chuỗi an toàn theo thuật giải nhà băng.
Mình trình bày như thế có dễ hiểu hơn không mấy bạn ?

Thưa thầy cho em hỏi một vấn đề nữa mà em chưa biết là : Chẳng hạn về trường hợp không tìm được chuỗi an toàn thì phải trình bày như thế nào ạ, có cần phải làm tới bước kẻ bảng và thực hiện tuần tự cho tới khi kết thúc ở Bước 5 rồi kết luận vào bài làm như thế không thầy ?

Admin
Với trường hợp không tồn tại chuỗi an toàn, có 2 khả năng:
1. Chỉ tìm được phần đầu của chuỗi (số tiến trình tìm được ≥ 1 và < Tổng số tiến trình).
2. Chuỗi rỗng (không tìm được tiến trình nào).
Dù thế nào, cũng phải lập bảng với các cột Work, Need_i, P_i, Allocation_i !