Thảo luận Bài 8

Trang 2 trong tổng số 9 trang Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Re: Thảo luận Bài 8

Bài gửi  AnhDao(I22B) on 9/4/2013, 01:12

Huynh Xuan Dat(I22A) đã viết:Để ngăn chặn Deadlock ta phải làm sao?
vd1 :2 con dê đi qua cầu, dê trắng và dê đen đều mún mình qua cầu chẳng ai chịu nhường ai cả, và cả 2 đều mắc kẹt mãi trên cầu....(có thể tranh chấp dẫn đến xảy ra đến cả 2 con đều rơi xuống cầu) tham khảo khóa trước Very Happy Very Happy
vd2:Giả sử tổng đài 1080 có tất cả 50 điện thoại viên. Cùng 1 lúc có 50 khách gọi đến nhờ phục vụ . Lúc này người thứ 51 gọi vào 1080 phải chờ . Xãy ra hiện tượng deadlock
tham khảo khóa trước Very Happy Very Happy
nhưng vd2 minh chưa thực sự hiểu bản chất lắm máy bạn giải thích giúp confused

Cho phép mình dc bổ sung nhé. Như vd 2 bạn vừa nêu , theo mình ngĩ vẫn chưa hợp lí lắm
Vì khj xảy ra hiện tượng Deadlock , nó sẽ kẹt mãi mãi cho đến khi có sự cứu trợ , nó mới hoạt động dc

Vậy, như ví dụ tổng đài, 50 điện thoại viên phục vụ 50 khách trong 1 thời gian có thể ngắn , hoặc có thể dài . Nhưng có đến 50 điện thoại viên,1 trong những khách ngưng kết nối , khách thứ 51 sẽ nhận được trả lời ngay ( không phải chờ lâu).
Trừ trường hợp , họ làm việc theo 1 quy định chung, có ngĩa là cuộc hội thoại giữa khách và điện thoại viên bắt buộc là 60 phút. khi đó , khách 51 mới phải chờ mãi mãi ... Deadlock xuất hiện ngay. (ko thực tế cho lắm)
Mình ngĩ là vậy thôi , nhưng ko biết có chính xác lắm ko? các bạn cho thêm ý kiến nhé Razz

AnhDao(I22B)

Tổng số bài gửi : 52
Join date : 09/03/2013
Age : 26
Đến từ : HoChiMinh

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  VoMinhThang(I22B) on 9/4/2013, 08:02

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

VoMinhThang(I22B)

Tổng số bài gửi : 41
Join date : 11/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  VoMinhThang(I22B) on 9/4/2013, 08:03

Điều kiện xuất hiện tắc nghẽn :
1 . Có sử dụng tài nguyên không thể chia sẻ .
2. Sự chiếm giữ và yêu cầu tài nguyên thêm .
3. Không thu hồi tài nguyên từ tiến trình đã sử dụng ,
4. Tồn tại 1 chu kỳ trong đồ thị cấp phát tài nguyên .
5. Có 2 tiến trình chờ đợi lẫn nhau : tiến trình này đang chờ được cấp phá tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại .
=> Khi có 4 điều kiện này thì tắc nghẽn xảy ra . Nếu thiếu 1 trong 4 điều kiện trên thì không có tắc nghẽn.

vd : 5 nhà triết học cùng ngồi vào bàn ăn để thưởng hức món mì ý . Để dùng bữa thì mỗi người cần dùng 2 cái nĩa mà trên bàn thì chỉ có 5 nĩa xếp xen kẽ 5 đĩa mì , Vậy nếu 5 người cùng ăn 1 lúc thì sẽ xảy ra hiện tượng tranh chấp gây ra hiện tượng .==> Hiên tượng Deadlock

VoMinhThang(I22B)

Tổng số bài gửi : 41
Join date : 11/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  VoMinhThang(I22B) on 9/4/2013, 08:05

Trạng thái deadlock xảy ra khi hai hay nhiều quá trình đang chờ không xác định
một sự kiện mà có thể được gây ra chỉ bởi một trong những quá trình đang chờ. Về
nguyên tắc, có ba phương pháp giải quyết deadlock:
• Sử dụng một số giao thức để ngăn chặn hay tránh deadlock, đảm bảo rằng
hệ thống sẽ không bao giờ đi vào trạng thái deadlock.
• Cho phép hệ thống đi vào trạng thái deadlock, phát hiện và sau đó phục hồi.
• Bỏ qua vấn đề deadlock và giả vờ deadlock chưa bao giờ xảy ra trong hệ
thống. Giải pháp này là một giải pháp được dùng bởi hầu hết các hệ điều
hành bao gồm UNIX.
Trường hợp deadlock có thể xảy ra nếu và chỉ nếu bốn điều kiện cần xảy ra
cùng một lúc trong hệ thống: loại trừ hỗ tương, giữ và chờ cấp thêm tài nguyên,
không đòi lại tài nguyên, và tồn tại chu trình trong đồ thị cấp phát tài nguyên. Để ngăn
chặn deadlock, chúng ta đảm bảo rằng ít nhất một điều kiện cần không bao giờ xảy ra.

VoMinhThang(I22B)

Tổng số bài gửi : 41
Join date : 11/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  VoMinhThang(I22B) on 9/4/2013, 08:05

Khi nào thì chúng ta nên nạp giải thuật phát hiện deadlock? Câu trả lời phụ thuộc
vào hai yếu tố:
1) Deadlock có khả năng xảy ra thường xuyên như thế nào?
2) Bao nhiêu quá trình sẽ bị ảnh hưởng bởi deadlock khi nó sẽ ra?

Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện nên được nạp lên
thường xuyên. Những tài nguyên được cấp phát để các quá trình bị deadlock sẽ rảnh
cho đến khi deadlock có thể bị phá vỡ. Ngoài ra, số lượng quá trình liên quan trong
chu trình deadlock có thể tăng lên.

Deadlock xảy ra chỉ khi một số quá trình thực hiện yêu cầu mà không được cấp tài
nguyên tức thì. Yêu cầu này có thể là yêu cầu cuối hoàn thành một chuỗi các quá trình
đang yêu cầu. Ngoài ra, chúng ta có thể nạp giải thuật phát hiện mọi khi một yêu cầu
cho việc cấp phát không thể được cấp tức thì. Trong trường hợp này, chúng ta không
chỉ định nghĩa tập hợp các quá trình bị deadlock, mà còn xác định quá trình đã gây ra
deadlock. (Trong thực tế, mỗi quá trình trong suốt quá trình bị deadlock là một liên
kết trong chu trình của đồ thị tài nguyên, vì thế tất cả chúng gây ra deadlock). Nếu có
nhiều loại tài nguyên khác nhau, một yêu cầu có thể gây chu trình trong đồ thị tài
nguyên, mỗi chu trình hoàn thành bởi yêu cầu mới nhất và “được gây ra” bởi một quá
trình có thể xác định.

Dĩ nhiên, nạp giải thuật phát hiện deadlock cho mỗi yêu cầu có thể gây ra một
chi phí có thể xem xét trong thời gian tính toán. Một thay đổi ít đắt hơn là nạp giải
thuật tại thời điểm ít thường xuyên hơn- ví dụ, một lần một giờ hay bất cứ khi nào
việc sử dụng CPU rơi xuống thấp hơn 40%. Nếu giải thuật phát hiện deadlock được
nạp trong những thời điểm bất kỳ, thì có nhiều chu trình trong đồ thị tài nguyên.
Chúng ta không thể nói quá trình nào của nhiều quá trình bị deadlock gây ra deadlock

VoMinhThang(I22B)

Tổng số bài gửi : 41
Join date : 11/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Phát hiện deadlock

Bài gửi  VoMinhThang(I22B) on 9/4/2013, 08:06

Là xác định sự kiện xuất hiện trạng thái deadlock, xác định các quá trình và tài nguyên nằm trong tình trạng deadlock. Các thuật toán xác định deadlock thường được áp dụng trong các hệ thống có xuất hiện 3 điều kiện đầu tiên trong số các điều kiện làm xuất hiện deadlock. Và sau đó mới xác định xem có tồn tại trạng thái "chờ vòng" hay không.

Tất nhiên sử dụng các thuật toán phát hiện deadlock cũng phải trả giá, đó là chi phí về thời gian máy. Và chúng ta lại gặp vấn đề phải xác định giải pháp trung hòa: các chi phí thực hiện thuật toán phát hiện deadlock có tiệt kiệm hơn hẳn so với khi dùng các biện pháp cô lập, loại bỏ deadlock hay không.

VoMinhThang(I22B)

Tổng số bài gửi : 41
Join date : 11/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Trình bày định nghĩa Deadlocks ? ví dụ minh hoạ

Bài gửi  VoMinhThang(I22B) on 9/4/2013, 08:08

Trong môi truờ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 đang chờ
khác. Trường hợp này được gọi là deadlock (khoá chết).
Hầu hết các hệ điều hành không cung cấp
phương tiện ngăn chặn deadlock nhưng những đặc điểm này sẽ được thêm vào sau đó.
Vấn đề deadlock chỉ có thể trở thành vấn đề phổ biến, xu hướng hiện hành gồm số
lượng lớn quá trình, chương trình đa luồng, nhiều tài nguyên trong hệ thống và đặc
biệt các tập tin có đời sống dài và những máy phục vụ cơ sở dữ liệu hơn là các hệ
thống bó.

Ví dụ 1: Giả sử có hai tiến trình P1 và P2 hoạt động đồng thời trong hệ thống. Tiến trình P1 đang giữ tài nguyên R1 và xin được cấp R2 để tiếp tục hoạt động, trong khi đó tiến trình P2 đang giữ tài nguyên R2 và xin được cấp R1 để tiếp tục hoạt động. Trong trường hợp này cả P1 và P2 sẽ không tiếp tục hoạt động được. Như vậy P1 và P2 rơi vào trạng thái tắc nghẽn. Ví dụ này có thể được minh hoạ bởi sơ đồ ở hình 2.

Tắc nghẽn thường xảy ra do xung đột về tài nguyên thuộc loại không phân chia được, một số ít trường hợp xảy ra với tài nguyên phân chia được. Ví dụ sau đây là trường hợp tắc nghẽn do xung đột về tài nguyên bộ nhớ, là tài nguyên thuộc loại phân chia được.

Ví dụ 2: Trong các ứng dụng cơ sở dữ liệu, một chương trình có thể khoá một vài record mà nó sử dụng, để dành quyền điều khiển về cho nó. Nếu tiến trình P1 khoá record R1, tiến trình P2 khoá record R2, và rồi sau đó mỗi tiến trình lại cố gắng khoá record của một tiến trình khác. Tắc nghẽn sẽ xảy ra.

Như vậy tắc nghẽn là hiện tượng: Trong hệ thống xuất hiện một tập các tiến trình, mà mỗi tiến trình trong tập này đều chờ được cấp tài nguyên, mà tài nguyên đó đang được một tiến trình trong tập này chiếm giữ. Và sự đợi này có thể kéo dài vô hạn nếu không có sự tác động từ bên ngoài.

Trong trường hợp của ví dụ 1 ở trên: hai tiến trình P1 và P2 sẽ rơi vào trạng thái tắc nghẽn, nếu không có sự can thiệp của hệ điều hành. Để phá bỏ tắc nghẽn này hệ điều hành có thể cho tạm dừng tiến trình P1 để thu hồi lại tài nguyên R1, lấy R1 cấp cho tiến trình P2 để P2 hoạt động và kết thúc, sau đó thu hồi cả R1 và R2 từ tiến trình P2 để cấp cho P1 và tái kích hoạt P1 để P1 hoạt động trở lại. Như vậy sau một khoảng thời gian cả P1 và P2 đều ra khỏi tình trạng tắc nghẽn.

Khi hệ thống xảy ra tắc nghẽn nếu hệ điều hành không kịp thời phá bỏ tắc nghẽn thì hệ thống có thể rơi vào tình trạng treo toàn bộ hệ thống. Như trong trường hợp tắc nghẽn ở ví dụ 1, nếu sau đó có tiến trình P3, đang giữ tài nguyên R3, cần R2 để tiếp tục thì P3 cũng sẽ rơi vào tập tiến trình bị tắc nghẽn, rồi sau đó nếu có tiến trình P4 cần tài nguyên R1 và R3 để tiếp tục thì P4 cũng rơi vào tập các tiến trình bị tắc nghẽn như P3, … cứ thế dần dần có thể dẫn đến một thời điểm tất cả các tiến trình trong hệ thống đều rơi vào tập tiến trình tắc nghẽn. Và như vậy hệ thống sẽ bị treo hoàn toàn

VoMinhThang(I22B)

Tổng số bài gửi : 41
Join date : 11/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  vivanbieu(I22B) on 9/4/2013, 08:41

- Định nghĩa Deadlock (Kẹt khoá): Là Tình huống bị 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 (event) có thể chỉ được gây ra bởi một tiến trình khác.
- Deadlock là tình huống xuất hiện khi hai hay nhiều “hành động” phải chờ một hoặc nhiều hành động khác để kết thúc, nhưng không bao giờ thực hiện được Máy tính: Bế tắc là tình huống xuất hiện khi hai tiến trình phải chờ đợi nhau giải phóng tài nguyên hoặc nhiều tiến trình chờ sử dụng các tài nguyên theo một “vòng tròn.
-Sử dụng tài nguyên.
vd:
2 con dê đi qua cầu, dê trắng và dê đen đều múốn mình qua cầu chẳng ai chịu nhường ai cả, và cả 2 đều mắc kẹt mãi trên cầu....(có thể tranh chấp dẫn đến xảy ra đến cả 2 con đều rơi xuống cầu)
vd:
có 5 phòng trọ trong cùng 1 dãy.nhưng chỉ có 1 wc,phòng nào cũng giành đi trước không ai chịu nhường,xảy ra (deadlock).Rất thực tế hehe

vivanbieu(I22B)

Tổng số bài gửi : 27
Join date : 09/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Mô hình hệ thống(System Model)

Bài gửi  NguyenNhatHuy64(I22B) on 9/4/2013, 09:27

1.Các 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 (Instance)
2.Thứ tự sử dụng tài nguyên của tiến trình theo nguyên tắc gồm.
+ yêu cầu(request):tài nguyên nếu không được đáp ứng bởi vì tiến trình khác đang giữ nên tiến trình đang yêu cầu phải chờ cho đến khi được trả lại cho nó.ví dụ:xin sử dụng xe ô tô công ty để phục vụ công tác
+ sau đó sử dụng tài nguyên(use) :sau khi tiến trình được cấp phát,tiến trình sẽ thao tác trên tài nguyên(thực hiện công việc IO,in văn bản,...),lái xe chở những nhân sự đến nới yêu cầu
+ và cuối cùng là trả lại tài nguyên:tiến trình sử dụng xong sẽ trả cho hệ điều hành quản lý tài nguyên đó,khi hết sử dụng trả xe lại cho công ty.

NguyenNhatHuy64(I22B)

Tổng số bài gửi : 16
Join date : 09/03/2013
Age : 24

Xem lý lịch thành viên

Về Đầu Trang Go down

4 điều kiện cần dẫn đến Deadlock và 4 cách ngăn chặn Deadlock

Bài gửi  NguyenTrungTin(I22A) on 9/4/2013, 10:04

4 điều kiện cần dẫn đến Deadlock


- Loại trừ lẫn nhau (Mutual Exclusion): Ít nhất có 1 tài nguyên có tính không chia sẻ (non-sharable), nghĩa là: Mỗi thời điểm chỉ có 1 tiến trình được sử dụng nó.
- Giữ và chờ (Hold and Wait): Có 1 tiến trình đang giữ 1 tài nguyên và xin thêm tài nguyên đang độc chiếm bởi tiến trình khác.
- Không có tiếm quyền (No Preemption): Tài nguyên đang giữ bởi tiến trình không thể bị tiếm quyền mà phải được tiến trình ny tự nguyện trả lại hệ thống sau khi sử dụng xong.
- Chờ xoay vịng (Circular Wait): Giả sử cĩ n tiến trình đang chờ ti nguyn l { P1 , P2, ... , Pn }, khi đó P1 chờ TN giữ bởi P2 , tiến trình P2 chờ TN giữ bởi P3 , ... , Pn chờ P1.

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:
+ Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.
+ 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:
+ 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.
+ 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.

NguyenTrungTin(I22A)

Tổng số bài gửi : 21
Join date : 14/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Khái niệm deadlock và các ví dụ minh họa.

Bài gửi  MaiXuanSon (I22B) on 9/4/2013, 10:25

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

Ví dụ 1: Chuyện kể về 2 chú dê con tranh nhau qua cầu hẹp không con nào chịu nhường con nào và 2 hai rơi xuống vực. Tài nguyên ở đây là cây cầu hẹp.
Ví dụ 2: Hai con cua kẹp càng của nhau. Tài nguyên ở đây là Cái càng và cuối cùng 2 con bị ngư dân bắt làm thịt.
Ví dụ 3: Hai chiếc xe hơi tranh nhau qua cầu hẹp không hai chịu nhường sẽ xảy ra deadlock mãi mãi. Chỉ còn cách là thuê cần cẩu nhất xe 1 lên cho xe 2 chạy qua rồi tiếp tục bỏ xe 1 xuống chạy qua cầu, ở đây là nhờ sự trợ giúp của cần cẩu, tài nguyên là cây cầu hẹp.

MaiXuanSon (I22B)

Tổng số bài gửi : 49
Join date : 11/03/2013
Age : 30

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  MaiXuanSon (I22B) on 9/4/2013, 10:33

TruongNhuNgoc (I22A) đã viết:
TruongNhuNgoc (I22A) đã 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.
VD: Trong công ty có 1 cái máy photo và có người đang sử dụng nó trong khi đó thì có 2 người khác đến để photo tài liệu --> dẫn đến tranh chấp.

Admin
Không phải lúc nào Tranh chấp cũng dẫn đến Kẹt khoá (Deadlock) !

Dạ thưa thầy có phải vì việc chờ photo chỉ mất một khoảng thời gian ngắn không phải chờ mãi mãi nên không gọi là Deadlock.

Admin
Đúng rồi ! Deadlock là chờ mãi mãi mà không được !

Tình huống sau đây có được gọi là Deadlock không?
Một máy tính đang hoạt động bình thường, người sử dụng mở 1 lúc nhiều chương trình quá máy tính xử lý không kịp, người sử dụng cứ thế là click và click chuột liên tục làm máy tính bị đứng luôn. Chỉ còn cách reset lại máy tính thì mới sử dụng lại được.

Nhờ Thầy và các bạn giúp đỡ. Thanks

MaiXuanSon (I22B)

Tổng số bài gửi : 49
Join date : 11/03/2013
Age : 30

Xem lý lịch thành viên

Về Đầu Trang Go down

Khái niệm Deadlocks

Bài gửi  ThaiMyTu (I22B) on 9/4/2013, 12:09

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à kết quả của các tiền trình là sẽ kẹt lại mãi mãi cho đến khi có một nguồn tác động khác từ bên ngoài tác động vào (như tắt máy, thoát chương trình,...)

VD: 2 xe ở 2 đầu cùng đi về phía cây cầu hẹp, nhưng cây cầu chỉ được phép cho duy nhất 1 xe qua cầu. Trong khi cả 2 xe đi tới giữa cầu, do cả 2 xe đều không chịu nhường nhau, dẫn tới việc không xe nào được đi tiếp tới nửa cầu bên kia. Kết quả là cả cây cầu đều bị kẹt (deadlocks).

ThaiMyTu (I22B)

Tổng số bài gửi : 11
Join date : 10/03/2013
Age : 26
Đến từ : HCM city

Xem lý lịch thành viên

Về Đầu Trang Go down

Re:Thảo Luận Bài 8

Bài gửi  VoMinhDien(I22B) on 9/4/2013, 13:32

Ví dụ: Deadlock trong máy tính xảy ra khi tiến trình A đang sử dụng 1 ổ đĩa và cần sử dụng thêm 1 ổ đĩa nữa. Tiến trình B cũng vậy đang sử dụng 1 ổ đĩa và cần thêm 1 ổ đĩa nửa mà hệ điều hành chỉ có 2 ổ đĩa. Điều đó dẫn đến 2 tiến trình chờ nhau mãi mãi. Deadlock xãy ra.

VoMinhDien(I22B)

Tổng số bài gửi : 34
Join date : 11/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  NguyenThiMai(I22A) on 9/4/2013, 13:46

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.
rendeer rendeer

  • 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
afro afro

  • 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
lol! lol!

NguyenThiMai(I22A)

Tổng số bài gửi : 32
Join date : 28/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Câu 1 : Định nghĩa Deadlock và các ví dụ minh họa

Bài gửi  Dao Duy Thanh(I22B) on 9/4/2013, 14:03

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

Dao Duy Thanh(I22B)

Tổng số bài gửi : 16
Join date : 13/03/2013
Age : 26

Xem lý lịch thành viên

Về Đầu Trang Go down

Định nghĩa Deadlock và Ví dụ.

Bài gửi  BuiHuuDang(I22B) on 9/4/2013, 14:04

Định nghĩa Deadlock: 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ụ 1:tại một thời diểm, tiến trình 1 đang giữ tài nguyên R1, yêu cầu R2 và tiến trình 2 đang giữ tài nguyên R2, yêu cầu R1, như vây yêu cầu về tài nguyên không thể đáp ứng cho cả hai tiến trình. Khi đó không có tiến trình nào có thể tiếp tục xử lý, cũng như giải phóng tài nguyên cho tiến trình khác sử dụng, tất cả các tiến trình trong tập hợp đều bị khóa vĩnh viễn!

ví dụ 2: Bữa ăn tối của các triết gia. Có 5 nhà triết gia cùng ngồi ăn tối. Mỗi nhà triết gia cần dùng 2 cái đũa để có thể ăn. Nhưng trên bàn chỉ có tổng cộng 5 cái đũa, nếu cả 5 người đều cầm cái đũa bên trái cùng lúc, thì sẽ không có ai có được cái đũa bên phải để có thể bắt đầu ăn . Tình trạng này gọi là tình trạng tắc nghẽn.

-Tài nguyên có thể là tài nguyên vật lý (máy in, bộ nhớ, cpu, đĩa, …) hoặc tài nguyên logic (file, semaphore, monitor,…). Tài nguyên lại phân thành hai loại: loại tài nguyên có thể lấy lại từ một tiến trình đang chiếm giữ mà không ảnh hưởng đến tiến trình đang chiếm giữ và loại tài nguyên không thể thu hồi lại từ tiến trình đang chiếm giữ.

BuiHuuDang(I22B)

Tổng số bài gửi : 14
Join date : 13/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Ví dụ thêm về deadlock

Bài gửi  Dao Duy Thanh(I22B) on 9/4/2013, 14:06

VD: 5 nhà triết học cùng ngồi ăn tối với món spaghetti nổi tiếng. Mỗi nhà triết học cần dùng 2 cái nĩa để có thể ăn spaghetti . Nhưng trên bàn chỉ có tổng cộng 5 cái nĩa để xen kẽ với 5 cái đĩa. Mỗi nhà triết học sẽ suy ngẫm các triết lý của mình đến khi cảm thấy đói thì dự định lần lượt cầm 1 cái nĩa bên trái và 1 cái nĩa bên phải để ăn. Nếu cả 5 nhà triết học đều cầm cái nĩa bên trái cùng lúc, thì sẽ không có ai có được cái nĩa bên phải để có thể bắt đầu thưởng thức spaghetti . Đây chính là tình trạng tắc nghẽn.

Dao Duy Thanh(I22B)

Tổng số bài gửi : 16
Join date : 13/03/2013
Age : 26

Xem lý lịch thành viên

Về Đầu Trang Go down

Ngăn chặn tắc nghẽn

Bài gửi  Dao Duy Thanh(I22B) on 9/4/2013, 14:44

Để tắc nghẽn không xảy ra, cần bảo đảm tối thiểu một trong 4 điều kiện cần không xảy ra:

Tài nguyên không thể chia sẻ : nhìn chung gần như không thể tránh được điều kiện này vì bản chất tài nguyên gần như cố định. Tuy nhiên đối với một số tài nguyên về kết xuất, người ta có thể dùng các cơ chế spooling để biến đổi thành tài nguyên có thể chia sẻ.

Sự chiếm giữ và yêu cầu thêm tài nguyên: phải bảo đảm rằng mỗi khi tiến trình yêu cầu thêm một tài nguyên thì nó không chiếm giữ các tài nguyên khác. Có thể áp đặt một trong hai cơ chế truy xuất sau :

Tiến trình phải yêu cầu tất cả các tài nguyên cần thiết trước khi bắt đầu xử lý .

=> phương pháp này có khó khăn là tiến trình khó có thể ước lượng chính xác tài nguyên cần sử dụng vì có thể nhu cầu phụ thuộc vào quá trình xử lý . Ngoài ra nếu tiến trình chiếm giữ sẵn các tài nguyên chưa cần sử dụng ngay thì việc sử dụng tài nguyên sẽ kém hiệu quả.

Khi tiến trình yêu cầu một tài nguyên mới và bị từ chối, nó phải giải phóng các tài nguyên đang chiếm giữ , sau đó lại được cấp phát trở lại cùng lần với tài nguyên mới.

=> phương pháp này làm phát sinh các khó khăn trong việc bảo vệ tính toàn vẹn dữ liệu của hệ thống.

Không thu hồi tài nguyên: cho phép hệ thống được thu hồi tài nguyên từ các tiến trình bị khoá và cấp phát trở lại cho tiến trình khi nó thoát khỏi tình trạng bị khóa. Tuy nhiên với một số loại tài nguyên, việc thu hồi sẽ rất khó khăn vì vi phạm sự toàn vẹn dữ liệu .

Tồn tại một chu kỳ: tránh tạo chu kỳ trong đồ thị bằng cách cấp phát tài nguyên theo một sự phân cấp như sau :

gọi R = {R1, R2,...,Rm} là tập các loại tài nguyên.

Các loại tài nguyên được phân cấp từ 1-N.

Ví dụ : F(đĩa) = 2, F(máy in) = 12

Các tiến trình khi yêu cầu tài nguyên phải tuân thủ quy định : khi tiến trình đang chiếm giữ tài nguyên Ri thì chỉ có thể yêu cầu các tài nguyên Rj nếu F(Rj) > F(Ri).

Dao Duy Thanh(I22B)

Tổng số bài gửi : 16
Join date : 13/03/2013
Age : 26

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  AnhDao(I22B) on 9/4/2013, 14:46

MaiXuanSon (I22B) đã viết:
TruongNhuNgoc (I22A) đã viết:
TruongNhuNgoc (I22A) đã 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.
VD: Trong công ty có 1 cái máy photo và có người đang sử dụng nó trong khi đó thì có 2 người khác đến để photo tài liệu --> dẫn đến tranh chấp.

Admin
Không phải lúc nào Tranh chấp cũng dẫn đến Kẹt khoá (Deadlock) !

Dạ thưa thầy có phải vì việc chờ photo chỉ mất một khoảng thời gian ngắn không phải chờ mãi mãi nên không gọi là Deadlock.

Admin
Đúng rồi ! Deadlock là chờ mãi mãi mà không được !

Tình huống sau đây có được gọi là Deadlock không?
Một máy tính đang hoạt động bình thường, người sử dụng mở 1 lúc nhiều chương trình quá máy tính xử lý không kịp, người sử dụng cứ thế là click và click chuột liên tục làm máy tính bị đứng luôn. Chỉ còn cách reset lại máy tính thì mới sử dụng lại được.

Nhờ Thầy và các bạn giúp đỡ. Thanks

Theo mình ngĩ đây chính là Deadlock đó bạn . Razz

AnhDao(I22B)

Tổng số bài gửi : 52
Join date : 09/03/2013
Age : 26
Đến từ : HoChiMinh

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  HongGiaPhu (I22A) on 9/4/2013, 15:14

Khái niệm DeadLock (Kẹt Khoá)


Hiện tượng một tiến trình yêu cầu được cấp phát tài nguyên nhưng không được thoả mãn, dẫn đến tiến trình đó rơi vào luôn trạng thái chờ vô tận, gọi là DeadLock.

Những điều kiện xảy ra DeadLock


1/ Mutual Exclusion (Loại trừ lẫn nhau): tình huống này xảy ra khi có một tài nguyên được giữ ở chế độ không chia sẻ được (Nonshavable), nếu như có một tiến trình yêu cầu tài nguyên đó thì tiến trình đó phải chờ tới khi tài nguyên đó được giải phóng hoặc được trả lại bởi một tiến trình khác đang sử dụng tài nguyên đó.

2/ Hold And Wait (Giữ và đợi): Phải thuộc một tiến trình mà tiến trình này đang giữ ít nhất một tài nguyên và đang đợi để yêu cầu thêm một tài nguyên nữa mà tiến trình này đang được giữ bởi một tiến trình khác.

3/ No Preemption (Không tiếm quyền): Tiến trình giữ tài nguyên mãi mà không chịu trả, giải phóng cho tiến trình khác sử dụng.

4/ Circular Wait (Đợi vòng): Giả sử ta có một tập tiến trình P = {P1, P2, ..., Pn) và một tập các tài nguyên R = {R1, R2,.... Rn), trong đó do P1 yêu cầu tài nguyên R1, nhưng R1 được cấp cho P2, P2 yêu cầu R2 nhưng R2 lại được cấp cho P3, P3 yêu cầu R3 nhưng R3 lại đang được dùng bởi P1. Do đó ta có một tập E là tập chứa chu kỳ mạch vòng => E = {P1→R1→P2→R2→P3→R3→P1}.

Cách ngăn chặn DeadLock

1/ Ngăn cản Mutual Exclusion: Đảm bảo hệ thống không có các tài nguyên không thể chia sẻ được. Một tiến trình không bao giờ phải chờ tài nguyên có thể chia sẻ được.
Ví dụ: Một máy in không thể dùng chung cho nhiều tiến trình cùng lúc.

2/ Ngăn cản Hold and Wait
- Bất cứ một Process nào yêu cầu tài nguyên thì nó sẽ không được giữ bất kỳ một tài nguyên nào khác.
- Phải đảm bảo các tài nguyên mà tiến trình đó yêu cầu phải được cấp đầy đủ trước khi nó vận hành hoặc tiến trình đó chỉ được yêu cầu tài nguyên đó khi không có tiến trình nào đang sử dụng tài nguyên đó cả.

3/ Ngăn cản không Preemption
- Hệ thống phải đảm bảo các tài nguyên sử dụng tài nguyên theo đúng thứ tự.
- Không được đòi tài nguyên khi có một tiến trình khác đang sử dụng.
- Nếu như một tiến trình đang được vận hành và đang giữ một số tài nguyên mà yêu cầu tài nguyên khác nhưng hệ thống không cấp phát ngay được thì tất cả tài nguyên mà tiến trình đó đang giữ sẽ được giải phóng. Tiến trình chỉ được vận hành trở lại khi nó lấy lại được các tài nguyên cũ cũng như các tài nguyên mới mà nó yêu cầu.
- Các tài nguyên ưu tiên được thêm vào danh sách các tài nguyên dành cho tiến trình đang chờ đợi.

4/ Ngăn cản Circutar Wait
- Các tài nguyên được áp dụng theo một thứ tự tuyệt đối bằng cách một tài nguyên được gán một số nguyên để tránh hiện tượng đợi vòng không bao giờ xảy ra.
- Mỗi tiến trình yêu cầu tài nguyên theo thứ tự tăng dần, một tiến trình chỉ có thể yêu cầu tài nguyên và chỉ được nhận tài nguyên có trọng số cao hơn của bất kì tài nguyên nào mà nó đang giữ.
Ví dụ: Cho một tập R = { R1, R1,..., Rn} là tập các tài nguyên, ta gán cho mỗi tài nguyên một số nguyên duy nhất, so sánh hai tài nguyên với nhau để xác định thứ tự của chúng, mỗi Proces chỉ yêu cầu tài nguyên theo một thứ tự tăng dần, một tiến trình chỉ có thể yêu cầu tài nguyên Rj khi và chỉ khi <=>E(Rj) > F(Ri). farao

HongGiaPhu (I22A)

Tổng số bài gửi : 25
Join date : 10/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

TRÌNH BÀI KN DEADLOCK VÀ VD MINH HỌA

Bài gửi  NguyenVanLanh (I22A) on 9/4/2013, 15:23

deadlock là hiện tượng một tiến trình hay nhiều tiến trình chiếm hữu tài nguyên lâu dài dẫn đến tranh chấp tài nguyên làm cho các tiến trình có nhu cầu sử dụng tài nguyên này luôn ở trạng thái chờ.
Vdụ1: Khi users truy nhập vào trang 5giay.vn cùng lúc sẽ làm cho trang web bị quá tải do chiếm nhiều băng thông. cuối cùng dẫn đến tình trang nhiều user đăng nhập request time out hoặc chờ lâu hơn bình thuog.
Vdu2:
Một nhóm khách du lịch dinh di tham quan bằng 1 chiếc ghe . Chiếc ghe có thể chở được 5 người. khi nhóm khách xuống ghe thì ghe đầy. bỗng 1 bạn trên bờ muốn tham gia di chung bất ngờ nhảy xuống ngồi. Chiếc xuống quá tải ở mức an toàn, khiến cho nhóm khach du lịch không sao củ động được. cử động thì sẽ chìm và chết đuối ngay. Cuối cùng tình trạng deadclock xảy ra. =>fai nhờ nhân viên cứu trợ hộ.

NguyenVanLanh (I22A)

Tổng số bài gửi : 21
Join date : 08/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Các điều kiện dẫn đến Deadlock và ví dụ minh họa

Bài gửi  LeVanVan (I22B) on 9/4/2013, 23:04

Các điều kiện
1. Điều kiện loại trừ lẫn nhau: Một tài nguyên không thể sử dụng bởi nhiều hơn một tiến trình tại một thời điểm.
- Ví dụ : trên một đường ray (tài nguyên), không thể có nhiều hơn 1 tàu hỏa (tiến trình) đi qua, tại một thời điểm.
2. Điều kiện giữ và chờ: Các tiến trình giữ tài nguyên và chờ tài nguyên mới
3. Điều kiện không thể chiếm: Các tài nguyên không thể bị đòi lại, chúng chỉ có thể được giải phóng bởi chính tiến trình chiếm giử chúng
4. Điều kiện chu trình chờ: Các tiến trình giử tài nguyên và chờ các tài nguyên bị giử bởi tiến trình khác, tạo thành một chu trình.

LeVanVan (I22B)

Tổng số bài gửi : 12
Join date : 10/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

Tình trạng DeadLock

Bài gửi  LuGiaLam(I22A) on 9/4/2013, 23:20

Deadlock sẽ xảy ra nếu bốn điều khiện sau đồng thời xuất hiện:

Độc quyền truy xuất (Mutual Exclusion):Ít nhất một tài nguyên nắm giữ thuộc kiểu không thể dùng chung.Nghĩa là tại thời điểm đó chỉ có 1 tiến trình được quyền sử dụng tài nguyên.

Giữ và chờ ( Hold and Wait): Phải có tiến trình đang nắm giữ tài nguyên đồng thời lại chờ tài nguyên bị tiến trình khác chiếm giữ.

Không chiếm đoạt (No preemption): Hệ thống không thể cướp tài nguyên của tiến trình,trừ khi tiến trình chủ động giải phóng tài nguyên khi không cần thiết

Vòng đợi (Circular wait) :Tồn tại tập hợp các tiến trình đang trong trạng thái chời tài nguyên .

4 điều kiện trên phải đồng thời xuất hiện thì hiện tượng DeadLock mới xảy ra.

VD: 2 chiếc xe hàng chạy hướng ngược chiều nhau qua cầu. Do cầu hẹp,chỉ qua được 1 chiếc, 2 chiếc xe cùng qua cầu . Xảy ra tình trạng tắc nghẽn trên cầu.
VD:Trên bàn ăn có 1 đôi đũa, 1 dĩa thức ăn, 2 người đang cần gấp thức ăn để ăn. 2 bên không thể lấy 1 chiếc đũa vì phải có 1 đôi đũa thì mới gấp được thức ăn. Xãy ra tình trạng tranh chấp dẫn đến Deadlock.

LuGiaLam(I22A)

Tổng số bài gửi : 18
Join date : 11/03/2013
Age : 27
Đến từ : Viet Nam

Xem lý lịch thành viên

Về Đầu Trang Go down

Deadlock và ví dụ minh họa

Bài gửi  TranVuSang (I22B) on 10/4/2013, 04:00

Deadlock là hiện tượng ( tình huống ) của 1 nhóm tiến trình chờ 1 sự kiện nào đó mà sự kiện này chỉ có thể được gây ra bởi 1 tiến trình khác. Và việc chờ này không có giới hạn thời gian mà là chờ mãi mãi.

VD: Một nhóm du khách sử dụng du thuyền để đi chơi ở 1 nơi nào đó trên biển. Bổng nhiên trên đường đi họ gặp bão lớn và bị trôi dạt vào 1 đảo hoang nào đó mà trên đảo không có người, cũng không có thiết bị phát tính hiệu cấp cứu và như vậy là họ bị kẹt lại trên đảo hoang và chỉ còn biết trông chờ 1 chiếc thuyền nào khác vô tình đi qua đảo này và cứu họ.

Không biết ví dụ này có viễn tưởng quá không. Mong các bạn góp ý.

TranVuSang (I22B)

Tổng số bài gửi : 53
Join date : 09/03/2013
Age : 27

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thảo luận Bài 8

Bài gửi  Sponsored content Today at 14:50


Sponsored content


Về Đầu Trang Go down

Trang 2 trong tổng số 9 trang Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết