Thảo luận Bài 8

Trang 7 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  NguyenVanQuoc (I22B) on 13/4/2013, 23:09

NguyenVanLanh (I22A) đã viết:
LeThanhQuang (I22B) đã viết:

Để giải quyết trường hợp tắt nghẽn xe ở cầu hẹp:
Cách 1: ta có thể đặt một cần cẩu ở giữa cầu nếu có trường hợp bị nghẽn, cần cẩu sẽ nhất 1 trong hai chiếc lên để giải phóng cho xe còn lại.
Cách 2: Để không bao giờ bị kẹt nữa ta có thể xây dựng thêm một cây cầu tương tự như vậy. Ta cho cây cầu kia di chuyển 1 hướng và cầu còn lại thì duy chuyển hướng còn lại.

Cach 2 của bạn ko đúng rồi. cách này biến thành đường 1 chiều rồi... Mà trong trường hợp này là đường 2 chiều mà...

Thế thì nên sữa lại thành, mở rộng cầu thành mặt đường cầu hai chiều. Chứ không phải xây thêm cầu. Có vẻ chuẩn hơn.


Được sửa bởi NguyenVanQuoc (I22B) ngày 13/4/2013, 23:41; sửa lần 1.

NguyenVanQuoc (I22B)

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

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

Về Đầu Trang Go down

Những câu hỏi của bài 8

Bài gửi  LeSonCa(I22B) on 13/4/2013, 23:26

Câu 1:Trình bày khái niệm Deadlock và nêu ví dụ từ đời thường.
Câu 2: Trình bày 4 điều kiện cần dẫn đến Deadlock và biện pháp ngăn chặn Deadlock.
Câu 3: Biết vẽ và giải thích, cũng như đánh giá trạng thái của đồ thị cấp phát tài nguyên.
Câu 4: Giải bài tập tránh Deadlock bằng thuật giải nhà băng.
Ghi chú: Câu 4 Ngoài trình bày lời giải, cần trình bày về trạng thái an toàn và tránh Deadlock. (Tại sao phải tìm được ít nhất 01 chuỗi an toàn và chuỗi đó có tính chất gì?)

LeSonCa(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

re:Để giải quyết trường hợp tắt nghẽn xe ở cầu hẹp:

Bài gửi  NguyenXuanThi(I22A) on 14/4/2013, 00:03

NguyenVanQuoc (I22B) đã viết:
NguyenVanLanh (I22A) đã viết:
LeThanhQuang (I22B) đã viết:

Để giải quyết trường hợp tắt nghẽn xe ở cầu hẹp:
Cách 1: ta có thể đặt một cần cẩu ở giữa cầu nếu có trường hợp bị nghẽn, cần cẩu sẽ nhất 1 trong hai chiếc lên để giải phóng cho xe còn lại.
Cách 2: Để không bao giờ bị kẹt nữa ta có thể xây dựng thêm một cây cầu tương tự như vậy. Ta cho cây cầu kia di chuyển 1 hướng và cầu còn lại thì duy chuyển hướng còn lại.

Cach 2 của bạn ko đúng rồi. cách này biến thành đường 1 chiều rồi... Mà trong trường hợp này là đường 2 chiều mà...

Thế thì nên sữa lại thành, mở rộng cầu thành mặt đường cầu hai chiều. Chứ không phải xây thêm cầu. Có vẻ chuẩn hơn.
mình đồng ý với ý kiến này

NguyenXuanThi(I22A)

Tổng số bài gửi : 23
Join date : 21/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  NguyenXuanThi(I22A) on 14/4/2013, 00:11

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

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.
mấy ví dụ trên thì mình nghĩ đó không phải là deadlock mà là chỉ chờ bận thôi, deadlock nghĩ là chờ mãi mãi không dứt ra được

NguyenXuanThi(I22A)

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

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

Về Đầu Trang Go down

re: Bài tập giải thuật nhà băng các bạn thao khảo.

Bài gửi  NguyenXuanThi(I22A) on 14/4/2013, 00:14

lekhanhhoa(I22B) đã viết:Bài 1: 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.


Bai 2:

Một hệ thống có 3 máy quét hình và 2 tiến trình P1,P2 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(1,1) và Max(2,2). Dùng thuật giải nhà băng để:

a) Chứng minh trạng thái 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 nữa P2 ./.



Giải:
a) Allocation=(1,1), Max=(2,2);
Available=3-(1+1)=1;
Ta có: Need(i)=Max(i)-Allocation(i)
=> p1=(2-1)=1; p2=(2-1)=1;
Work >= Need(i) P(i ) Allocation
1 1 p1 1
2 1 p2 1
. Tồn tại chuỗi an toàn=.
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.
b)
Request(2)<=Need(2) vì 1<=1
Request(2)<=Available vì 1<=1
Trạng thái mới:
Allocation(1,1+1)(vì thêm 1 máy nữa nên cộng thêm 1)
Available=3-(1+1+1)=0
Need(i):
p1 1
p2 0
Work >= Need(i) P(i) Allocation
0 0 p2 2
2 1 p1 1
Tồn tại trạng thái an toàn=
Vậy trạng thái hệ thống ở thời điểm Ti là an toàn.
thanks bạn, nếu có thể bạn vẻ thêm khung giống thầy cho dễ hơn hihi Very Happy

NguyenXuanThi(I22A)

Tổng số bài gửi : 23
Join date : 21/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  HuynhDucQuang(I22B) on 14/4/2013, 00:19

PhamPhuKhanh52(I22B) đã viết:1. Loại trừ tương hỗ: Nếu một tiến trình đang sử dụng tài nguyên dùng chung thì tiến trình khác phải chờ.Biện pháp tránh loại trừ tương hỗ: Cho nhiều tiến trình cùng sử dụng tài nguyên đồng thời.
2. Giữ và chờ: Khi một tiến trình đã giữ một tài nguyên rồi và nó cần thêm những tài nguyên khác nữa.
=> Biện pháp tránh Giữ và chờ: Không cho tiến trình yêu cầu thêm tài nguyên cho đến khi tài nguyên đang chiếm giữ được giải phóng.
3. Không tiếm quyền: Tiến trình dùng xong tài nguyên rồi tự trả lại, không có sự can thiệp của Hệ Điều Hành.
=> Biện pháp tránh Không tiếm quyền: Cần phải tiếm quyền.
4. Chờ xoay vòng: Khi các tiến trình chờ tài nguyên đang được cấp cho một tiến trình khác và tạo thành một vòng khép kín.

Bài viết này trông quen ghê nhỉ?

HuynhDucQuang(I22B)

Tổng số bài gửi : 38
Join date : 08/03/2013
Đến từ : 11H1010104

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  LêAnhNgữ(I22A) on 14/4/2013, 09:06

BuiThucTuan(I22B) đã viết:


cho mình hỏi là ở hình thứ 3 đó: nếu R2 chỉ có 1 phiên bản thui, tức là chỉ có 1 dấu chấm thui thì có xảy ra deadlock ko? nhờ thầy và các bạn giải thích dùm. [/quote]

- Có Deadlock khi tài nguyên trên chu trình chỉ có 1 phiên bản. Loại tài nguyên ít nhất 1 dấu chấm trở lên Shocked



LêAnhNgữ(I22A)

Tổng số bài gửi : 15
Join date : 23/03/2013
Age : 25
Đến từ : Tây Ninh

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

Về Đầu Trang Go down

Bài 5 trong đề thi của lớp I13A

Bài gửi  TruongMinhTriet(I22B) on 14/4/2013, 13:38

a)

  • Tại thời điểm Ti ta có bảng sau:



  • Hệ có Available=5 - 4 = 1


  • Ma trận Need= Max - Allocation



  • Tìm chuỗi an toàn:


Vậy chuỗi an toàn tìm đươc = {P2, P1, P3}
Vậy trạng thái hệ thống ở tại thời điểm Ti là an toàn
b)
P3 xin cấp thêm 1 máy, yêu cầu này thỏa điều kiện:

  • request <= Need vì 1<2


  • request <= Available vì 1=1


Trạng thái mới t có

Tìm chuỗi an toàn:

Vậy ta tìm được chuỗi an toàn = {P2, P3, P1}
Vậy trạng thái hệ thống ở thời điểm mới là an toàn
p/s: đây là bài giải của mình không bít là đúng hay sai mong mọi người và thầy đóng góp ý kiến

Admin
Sai Câu b !

TruongMinhTriet(I22B)

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

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

Về Đầu Trang Go down

Một chút ý kiến về 1 vd

Bài gửi  LeQuangLong (I22B) on 14/4/2013, 16:27

Em chào thầy! Hôm thứ 6 ngày 12/04 trong bài Deadlock thầy có nói nhanh về 1 số ví dụ mà các bạn đã đưa ra trên forum là những ví dụ không có Deadlock. Có thể giải quyết bằng cách chờ. Nhưng trong đó lại có 1 ví dụ 5 thầy giáo của 5 môn khác nhau cần máy chiếu, nhưng chỉ có 1 máy chiếu.

Theo em ví dụ này thầy cần nói rõ hơn 1 tí về điều kiện. Vì nếu như cả 5 thầy cùng dạy tiết 1 mà cần máy chiếu thì chắc chắn là sẽ bị kẹt ngay. Theo đó chỉ cần có ít nhất 2 thầy cùng dạy 1 tiết (có thể tiết 2, 3 chứ không nhất thiết phải là tiêt 1) là trường hợp này cũng đều dẫn đến Deadlock.
Nên => Điều kiện duy nhất để tiến trình này không bị deadlock là cả 5 thầy phải dạy ở 5 tiết khác nhau từ 1->5 theo đó, các tiết trước phải nhường cho các tiết sau 1 cách tuần tự Smile

LeQuangLong (I22B)

Tổng số bài gửi : 2
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  TruongMinhTriet(I22B) on 14/4/2013, 16:40

TruongMinhTriet(I22B) đã viết:a)

  • Tại thời điểm Ti ta có bảng sau:



  • Hệ có Available=5 - 4 = 1


  • Ma trận Need= Max - Allocation



  • Tìm chuỗi an toàn:


Vậy chuỗi an toàn tìm đươc = {P2, P1, P3}
Vậy trạng thái hệ thống ở tại thời điểm Ti là an toàn
b)
P3 xin cấp thêm 1 máy, yêu cầu này thỏa điều kiện:

  • request <= Need vì 1<2


  • request <= Available vì 1=1


Trạng thái mới t có

Tìm chuỗi an toàn:

Vậy ta tìm được chuỗi an toàn = {P2, P3, P1}
Vậy trạng thái hệ thống ở thời điểm mới là an toàn
p/s: đây là bài giải của mình không bít là đúng hay sai mong mọi người và thầy đóng góp ý kiến

Admin
Sai Câu b !
ah, vậy là e quên xét điều kiện work >= Need, nên kết quả của câu b này của e là sai, kết quả của câu này phải là: trạng thái mới là không an toàn vì không tìm được dãy an toàn. Cảm ơn thầy đã nhắt nhở.

TruongMinhTriet(I22B)

Tổng số bài gửi : 13
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  NguyenCaoDuong(I22B) on 14/4/2013, 18:38

BuiThucTuan(I22B) đã viết:
NguyenVanQuoc (I22B) đã viết:




cho mình hỏi là ở hình thứ 3 đó: nếu R2 chỉ có 1 phiên bản thui, tức là chỉ có 1 dấu chấm thui thì có xảy ra deadlock ko? nhờ thầy và các bạn giải thích dùm.

Nếu R2 chỉ có một phiên bản thì vẫn không có Deadlock. Vì tới một lúc nào đó tiến trình P2 có thể trả lại phiên bản của loại tài nguyên R1. Tài nguyên đó có thể được cấp phát tới P1 sau đó thì chu trình sẽ không còn nữa ===> Không có Deadlock




NguyenCaoDuong(I22B)

Tổng số bài gửi : 27
Join date : 10/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  LeThanhQuang (I22B) on 14/4/2013, 18:42

PhamPhuKhanh52(I22B) đã 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ụ:
Trường ĐH Mở cho phép sinh viên đăng ký môn học trực tuyến. hệ thống đăng ký môn học trực tuyến là tài nguyên hệ thống. Do tài nguyên chỉ cho phép 1 số lượng sinh viên nhất định vào đăng ký mà lượng sinh viên đăng nhập lại rất lớn dẫn đến tình trạng nghẽn mạch không thể vào trong để đăng ký được

Ví dụ của bạn trong trường hợp này là có một số bạn chưa thể vào đăng ký thì trường hợp này chỉ là chờ chứ không phải là chờ mãi mãi nên ví dụ này không phải là Deadlocks

LeThanhQuang (I22B)

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

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

Về Đầu Trang Go down

Câu 3: Vẽ và giải thích, đánh giá trạng thái của đồ thị cấp phát tài nguyên

Bài gửi  LuGiaLam(I22A) on 15/4/2013, 00:10





Khi tiến trình Pi yêu cầu đối tượng tài nguyên Rj,hệ thống bổ sung một cung yêu cầu vào đồ thị phân phối tài nguyên. Khi có thể đáp ứng yêu cầu thành cung phân phối . Cung phân phối bị xóa bỏ khi tiến trình giải phóng tài nguyên.

Đồ thị phân phối tài nguyên mô tả như sau:
P= {P1,P2,P3}
R={R1,R2,R3,R4}
E={P1 -> R1 , P2 -> R3 , R1 -> P2 , R2 ->P2 , R2 -> R1 , R3 -> P3}

Số đối tượng của mỗi tài nguyên:
+ R1 có 1 đối tượng.
+ R2 có 2 đối tượng.
+ R3 có 1 đối tượng.
+ R4 có 3 đối tượng.
Trạng thái các tiến trình:
+ P1 đang giữ 1 đối tượng R2 và đang đợi 1 đối tượng R1
+ P2 đang giữ 1 đối tượng R1 và đang đợi 1 đối tượng R3
+ P3 đang giữ 1 đối tượng R3.

Xét đồ thị hình (B)
Nếu P3 yêu cầu một đối tượng R2 . Do hệ thống không còn đối tượng tài nguyên R2 rồi nên cung yêu cầu P3 -> R2 được thêm vào đồ thị . Lúc này , xuất hiện 2 chu trình;
Chu trình 1: P1 -> R1 -> P2 -> R3 -> P3 -> R2 -> P1
Chu trình 2: P2 -> R3 -> P3 -> R2 -> P2

Ba tiến trình P1,P2,P3 bế tắc (deadlock):
+ P2 chờ R3 ( bị chiếm dụng bởi P3)
+ P3 chờ P1 và P2 giải phóng R2
+ P1 chờ P2 giải phóng R1

Xét đồ thị hình (C)
Chu trình : P1->R1->P3->R2->P1
>>>Không có bế tắc (deadlock) do P4 có thể giải phóng 1 đối tượng R2.

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

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

Bài gửi  NguyenHoangMinh_I22B on 15/4/2013, 07:51

Huynh Xuan Dat(I22A) đã viết:
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

VD của bạn chưa đúng vì vị khách thứ 51 tuy phải chờ nhưng không phải chờ "mãi mãi". Khi 1 trong 50 khách hàng đang được tiếp xong việc sẽ có chỗ trống cho vị khách thứ 51. Vậy điều này không phải Deadlock vì không dẫn đến tình trạng vị khách thứ 51 chờ "mãi mãi".
Lưu ý các bạn cho ví dụ nếu không xác định được "tài nguyên dùng chung", "thời gian tranh chấp" thì tốt nhất nên dùng ngay ví dụ của thầy và các ví dụ được thầy thông qua. Tránh lấy ví dụ chưa được thầy chấp nhận để làm bài thi.Good luck What a Face

NguyenHoangMinh_I22B

Tổng số bài gửi : 3
Join date : 28/03/2013
Age : 28
Đến từ : GO VAP - HO CHI MINH -VIET NAM

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  TruongTranThanhTu(I22B) on 15/4/2013, 08:01

LeThanhQuang (I22B) đã viết:

Để giải quyết trường hợp tắt nghẽn xe ở cầu hẹp:
Cách 1: ta có thể đặt một cần cẩu ở giữa cầu nếu có trường hợp bị nghẽn, cần cẩu sẽ nhất 1 trong hai chiếc lên để giải phóng cho xe còn lại.
Cách 2: Để không bao giờ bị kẹt nữa ta có thể xây dựng thêm một cây cầu tương tự như vậy. Ta cho cây cầu kia di chuyển 1 hướng và cầu còn lại thì duy chuyển hướng còn lại.

nếu sử dụng cách 2 thì theo mình nghĩ là xây cầu vượt như ớ nước ta hiện nay, xe từ bên trái qua thì chạy lên cầu, xe từ bên phải qua thì chay đường dưới cầu

TruongTranThanhTu(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

Khái niệm Deadlock và ví dụ

Bài gửi  TruongTranThanhTu(I22B) on 15/4/2013, 08:23

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

TruongTranThanhTu(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

Câu 2 : trình bày 4 điều kiện cần dẫn đến Deadlock và biện pháp ngăn chặn ?

Bài gửi  phungvanduong24(I12A) on 15/4/2013, 10:21

* 4 điều kiện :
-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 .
* Biện pháp ngăn chặn :
Để 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.

-Loại trừ hỗ tương
Điều kiện loại trừ hỗ tương phải giữ cho tài nguyên không chia sẻ. Thí dụ, một máy in không thể được chia sẻ cùng lúc bởi nhiều quá trình. Ngược lại, các tài nguyên có thể chia sẻ không đòi hỏi truy xuất loại trừ hỗ tương và do đó không thể liên quan đến deadlock. Những tập tin chỉ đọc là một thí dụ tốt cho tài nguyên có thể chia sẻ. Nếu nhiều quá trình cố gắng mở một tập tin chỉ đọc tại cùng một thời điểm thì chúng có thể được gán truy xuất cùng lúc tập tin. Một quá trình không bao giờ yêu cầu chờ tài nguyên có thể chia sẻ. Tuy nhiên, thường chúng ta không thể ngăn chặn deadlock bằng cách từ chối điều kiện loại trừ hỗ tương: một số tài nguyên về thực chất không thể chia sẻ.

-Giữ và chờ cấp thêm tài nguyên
Để đảm bảo điều kiện giữ-và-chờ cấp thêm tài nguyên không bao giờ xảy ra trong hệ thống, chúng ta phải đảm bảo rằng bất cứ khi nào một quá trình yêu cầu tài nguyên, nó không giữ bất cứ tài nguyên nào khác. Một giao thức có thể được dùng là đòi hỏi mỗi quá trình yêu cầu và được cấp phát tất cả tài nguyên trước khi nó bắt đầu thực thi. Chúng ta có thể cài đặt sự cung cấp này bằng cách yêu cầu các lời gọi hệ thống yêu cầu tài nguyên cho một quá trình trước tất cả các lời gọi hệ thống khác.
Một giao thức khác cho phép một quá trình yêu cầu tài nguyên chỉ khi quá trình này không có tài nguyên nào. Một quá trình có thể yêu cầu một số tài nguyên và dùng chúng. Tuy nhiên, trước khi nó có thể yêu cầu bất kỳ tài nguyên bổ sung nào, nó phải giải phóng tất cả tài nguyên mà nó hiện đang được cấp phát.

Để hiển thị sự khác nhau giữa hai giao thức, chúng ta xét một quá trình chép dữ liệu từ băng từ tới tập tin đĩa, sắp xếp tập tin đĩa và sau đó in kết quả ra máy in. Nếu tất cả tài nguyên phải được yêu cầu cùng một lúc thì khởi đầu quá trình phải yêu cầu băng từ, tập tin đĩa và máy in. Nó sẽ giữ máy in trong toàn thời gian thực thi của nó mặc dù nó cần máy in chỉ ở giai đoạn cuối.

Phương pháp thứ hai cho phép quá trình yêu cầu ban đầu chỉ băng từ và tập tin đĩa. Nó chép dữ liệu từ băng từ tới đĩa, rồi giải phóng cả hai băng từ và đĩa. Sau đó, quá trình phải yêu cầu lại tập tin đĩa và máy in. Sau đó, chép tập tin đĩa tới máy in, nó giải phóng hai tài nguyên này và kết thúc.

Hai giao thức này có hai nhược điểm chủ yếu. Thứ nhất, việc sử dụng tài nguyên có thể chậm vì nhiều tài nguyên có thể được cấp nhưng không được sử dụng trong thời gian dài. Trong thí dụ được cho, chúng ta có thể giải phóng băng từ và tập tin đĩa, sau đó yêu cầu lại tập tin đĩa và máy in chỉ nếu chúng ta đảm bảo rằng dữ liệu của chúng ta sẽ vẫn còn trên tập tin đĩa. Nếu chúng ta không thể đảm bảo rằng dữ liệu vẫn còn tập tin đĩa thì chúng ta phải yêu cầu tất cả tài nguyên tại thời điểm bắt đầu cho cả hai giao thức. Thứ hai, đói tài nguyên là có thể. Một quá trình cần nhiều tài nguyên phổ biến có thể phải đợi vô hạn định vì một tài nguyên mà nó cần luôn được cấp phát cho quá trình khác.

- Không đòi lại tài nguyên từ quá trình đang giữ chúng
Điều kiện cần thứ ba là không đòi lại những tài nguyên đã được cấp phát rồi. Để đảm bảo điều kiện này không xảy ra, chúng ta có thể dùng giao thức sau. Nếu một quá trình đang giữ một số tài nguyên và yêu cầu tài nguyên khác mà không được cấp phát tức thì tới nó (nghĩa là, quá trình phải chờ) thì tất cả tài nguyên hiện đang giữ được đòi lại. Nói cách khác, những tài nguyên này được giải phóng hoàn toàn. Những tài nguyên bị đòi lại được thêm tới danh sách các tài nguyên mà quá trình đang chờ. Quá trình sẽ được khởi động lại chỉ khi nó có thể nhận lại tài nguyên cũ của nó cũng như các tài nguyên mới mà nó đang yêu cầu.

Có một sự chọn lựa khác, nếu một quá trình yêu cầu một số tài nguyên, đầu tiên chúng ta kiểm tra chúng có sẳn không. Nếu tài nguyên có sẳn, chúng ta cấp phát chúng. Nếu tài nguyên không có sẳn, chúng ta kiểm tra chúng có được cấp phát tới một số quá trình khác đang chờ tài nguyên bổ sung. Nếu đúng như thế, chúng ta lấy lại tài nguyên mong muốn đó từ quá trình đang đợi và cấp chúng cho quá trình đang yêu cầu. Nếu tài nguyên không sẳn có hay được giữ bởi một quá trình đang đợi, quá trình đang yêu cầu phải chờ. Trong khi nó đang chờ, một số tài nguyên của nó có thể được đòi lại chỉ nếu quá trình khác yêu cầu chúng. Một quá trình có thể được khởi động lại chỉ khi nó được cấp các tài nguyên mới mà nó đang yêu cầu và phục hồi bất cứ tài nguyên nào đã bị lấy lại trong khi nó đang chờ.

Giao thức này thường được áp dụng tới tài nguyên mà trạng thái của nó có thể được lưu lại dễ dàng và phục hồi lại sau đó, như các thanh ghi CPU và không gian bộ nhớ. Nó thường không thể được áp dụng cho các tài nguyên như máy in và băng từ.

- Tồn tại chu trình trong đồ thị cấp phát tài nguyên
Điều kiện thứ tư và cũng là điều kiện cuối cùng cho deadlock là điều kiện tồn tại chu trình trong đồ thị cấp phát tài nguyên. Một cách để đảm bảo rằng điều kiện này không bao giờ xảy ra là áp đặt toàn bộ thứ tự của tất cả loại tài nguyên và đòi hỏi mỗi quá trình trong thứ tự tăng của số lượng.

Gọi R = {R1, R2, …, Rm} là tập hợp loại tài nguyên. Chúng ta gán mỗi loại tài nguyên một số nguyên duy nhất, cho phép chúng ta so sánh hai tài nguyên và xác định tài nguyên này có đứng trước tài nguyên khác hay không trong thứ tự của chúng ta. Thông thường, chúng ta định nghĩa hàm ánh xạ một-một F: R  N, ở đây N là tập hợp các số tự nhiên. Thí dụ, nếu tập hợp các loại tài nguyên R gồm các ổ băng từ, ổ đĩa và máy in thì hàm F có thể được định nghĩa như sau:

F(ổ băng từ) = 1,

F(đĩa từ) = 5,

F(máy in) = 12.

Bây giờ chúng ta xem giao thức sau để ngăn chặn deadlock: mỗi quá trình có thể yêu cầu tài nguyên chỉ trong thứ tự tăng của số lượng. Nghĩa là, một quá trình ban đầu có thể yêu cầu bất cứ số lượng thể hiện của một loại tài nguyên Ri. Sau đó, một quá trình có thể yêu cầu các thể hiện của loại tài nguyên Rj nếu và chỉ nếu F(Rj) > F(Ri). Nếu một số thể hiện của cùng loại tài nguyên được yêu cầu, thì một yêu cầu cho tất cả thể hiện phải được cấp phát. Thí dụ, sử dụng hàm được định nghĩa trước đó, một quá trình muốn dùng ổ băng từ và máy in tại cùng một lúc trước tiên phải yêu cầu ổ băng từ và sau đó yêu cầu máy in.

Nói một cách khác, chúng ta yêu cầu rằng, bất cứ khi nào một quá trình yêu cầu một thể hiện của loại tài nguyên Rj, nó giải phóng bất cứ tài nguyên Ri sao cho F(Ri)  F(Rj).

Nếu có hai giao thức được dùng thì điều kiện tồn tại chu trình không thể xảy ra. Chúng ta có thể giải thích điều này bằng cách cho rằng tồn tại chu trình trong đồ thị cấp phát tài nguyên tồn tại. Gọi tập hợp các quá trình chứa tồn tại chu trình trong đồ thị cấp phát tài nguyên là {P0, P1, … , Pn}, ở đây Pi đang chờ một tài nguyên Ri, mà Ri được giữ bởi quá trình Pi+1. Vì sau đó quá trình Pi+1 đang giữ tài nguyên Ri trong khi yêu cầu tài nguyên Ri+1, nên chúng ta có F(Ri) < F(Ri+1) cho tất cả i. Nhưng điều kiện này có nghĩa là F(R0) < F(R1) < …< F(Rn) < F(R0). Bằng qui tắc bắt cầu F(R0) < F(R0), điều này là không thể. Do đó, không thể có chờ chu trình.

Chú ý rằng hàm F nên được định nghĩa dựa theo thứ tự tự nhiên của việc sử dụng tài nguyên trong hệ thống. Thí dụ, vì ổ băng từ thường được yêu cầu trước máy in nên có thể hợp lý để định nghĩa F( ổ băng từ) < F(máy in).

phungvanduong24(I12A)

Tổng số bài gửi : 61
Join date : 20/02/2012

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

Về Đầu Trang Go down

Câu 3 : Biết vẽ và giải thích cũng như đánh giá trạng thái của đồ thị cấp phát tài nguyên

Bài gửi  phungvanduong24(I12A) on 15/4/2013, 14:07

- Đồ thị cấp phát tài nguyên (Resource allocation graph-RAG) là đồ thị có hướng với tập nút V và tập cung E.

+ Tập nút V gồm 2 loại:
P ={P1, P2, ..., Pn} tập hợp các tiến trình đang vận hành trong hệ thống.
R ={R1, R2, ..., Rm} tất cả các tài nguyên trong hệ thống. Mỗi loại Rj có từ 1 đến nhiều
phiên bản. VD: máy in có 3 phiên bản, ...

+Tập cung E bao gồm:
Cung yêu cầu (Request edge): có hướng từ Pi -> Rj, P1 yêu cầu 1 phiên bản tài nguyên Rj.
Cung ấn định (Assignment edge): có hướng từ Rj->Pi, 1 phiên bản tài nguyên Rj được cấp
phát cho Pi.

Đồ thị cấp phát tài nguyên gồm có: chu trình và không có chu trình.
o Không có chu trình: không tồn tại Deadlock
o Có chu trình: có hoặc không có Deadlock
.Có Deadlock khi mỗi tài nguyên trên chu trình chỉ có duy nhất 1 phiên bản.
.Có thể không có Deadlock khi tài nguyên thuộc chu trình có nhiều phiên bản.




- Cách vẽ:
Hiển thị mỗi tiến trình Pi là một hình tròn, và mỗi loại tài nguyên Rj là hình chữ nhật. Vì loại tài nguyên Rj có thể có nhiều hơn một phiên bản, chúng ta hiển thị mỗi phiên bản là một chấm nằm trong hình vuông. Chú ý rằng một cung yêu cầu trỏ tới chỉ một hình vuông Rj (tới đường viền), trái lại một cung ấn định cũng phải trỏ tới một trong các dấu chấm trong hình vuông(vào trong viền).


- Giải thích:
Hình 1:
Các tập P, R, và E:
P = {P1, P2, P3}
R = {R1, R2, R3, R4}
E = {P1→R1, P2 →R3, R1 →P2, R2→P2, R3→P3}

Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1 và 1 phiên bản của R2 và yêu cầu được được tài nguyên R3 cấp cho 1 phiên bản của nó. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R3. Còn lại tài nguyên R4 với các phiên bản của nó vẫn chưa có tiến trình nào xin được cấp phát. Từ hình vẽ Đồ thị cấp phát tài nguyên cho thấy không tồn tại chu trình cũng như Deadlock.

Hình 2:
Các tập P, R tương tự hình 1, tập E = {P1 → R1, R1 → P2, P2 → R3, R3 → P3, P3 → R2, R2 → P1, R2→P2}
Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1 và 1 phiên bản của R2 và yêu cầu được được tài nguyên R3 cấp cho 1 phiên bản của nó. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R3 và yêu cầu cấp phát 1 phiên bản của tài nguyên R2. Trong trường hợp này, một chu trình trong đồ thị là điều kiện cần nhưng chưa đủ để tồn tại deadlock, do nhìn hình lại chúng ta thấy có 2 chu trình: P1 → R1 → P2 → R3 → P3 → R2 → P1 và P2 → R3 → P3 → R2 → P2. Nghĩa là tiến trình P3 đang chờ tiến trình P1 hay P2 trả lại tài nguyên R2. Ngoài ra, tiến trình P1 đang chờ tiến trình P2 trả lại phiên bản tài nguyên R1 cho nên tiến trình P1, P2, P3 đã bị Deadlock vì không có phiên bản tài nguyên yêu cầu hiện có (vi phạm điều kiện deadlock).

Hình 3:
Các tập P, R, và E:
P = {P1, P2, P3, P4}
R = {R1, R2}
E = {P1 → R1, R1 → P2 , R1 → P3, P3 → R2, R2 → P1, R2→P4}
Tiến trình P1 đang giữ một phiên bản của loại tài nguyên R2 và yêu cầu được cấp phát 1 phiên bản của loại tài nguyên R1. Tiến trình P2 đang giữ 1 phiên bản của loại tài nguyên R1. Tiến trình P3 đang giữ 1 phiên bản của tài nguyên R1 và yêu cầu cấp phát 1 phiên bản của tài nguyên R2. Tiến trình P4 đang giữ 1 phiên bản của tài nguyên R2. Từ hình chúng ta thấy xảy ra 1 chu trình P1 → R1 → P3 → R2 → P1 nhưng không có deadlock vì tiến trình P4 có thể trả lại phiên bản của loại tài nguyên R2. Tài nguyên đó có thể được cấp phát tới P3 sau đó, chu trình sẽ không còn.

phungvanduong24(I12A)

Tổng số bài gửi : 61
Join date : 20/02/2012

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

Về Đầu Trang Go down

Các điều kiện dẫn đến Deadlock

Bài gửi  PhamThiThao (I22B) on 15/4/2013, 21:35

Deadlock xảy ra khi có 4 điều kiện cần sau:

+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 này 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ờ tài nguyên 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 .

Chú ý: Bốn điều kiện này không hoàn toàn độc lập với nhau: ví dụ, Điều kiện 4 kéo theo Điều kiện 2.

PhamThiThao (I22B)

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

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

Về Đầu Trang Go down

Phân tích khái niệm tài nguyên hệ thống

Bài gửi  PhamThiThao (I22B) on 15/4/2013, 21:36

-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(Instances). Các tài nguyên hệ thống này cấp phát cho các tiến trình theo yêu cầu.
- Tài nguyên cùng loại: Giả sử máy có 3 ổ băng từ và có 3 tiến trình đang chạy. Mỗi tiến trìnhđang giữ 1 ổ băng.
- Tài nguyên khác loại: Giả sử có 1 máy in, 1 ổ băng từ. Tiến trình P1 đang giữ ổ băng, P2 giữ máy in.

PhamThiThao (I22B)

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

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

Về Đầu Trang Go down

Thuật giải tránh deadlock RAG

Bài gửi  PhamThiThao (I22B) on 15/4/2013, 21:38

Thuật giải tránh deadlock RAG (áp dụng cho trường hợp loại tài nguyên chỉ có 1 phiên bản) nếu có nhiều phiên bản thuật giải này không dùng được:
- 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.

PhamThiThao (I22B)

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

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

Về Đầu Trang Go down

Giải pháp ngăn Deadlock

Bài gửi  PhamThiThao (I22B) on 15/4/2013, 21:50

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.

PhamThiThao (I22B)

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

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

Về Đầu Trang Go down

Tránh Deadlock bằng Banker’s Algorithm.

Bài gửi  PhamThiThao (I22B) on 15/4/2013, 21:51

Banker’s Algorithm.
Là thuật giải tránh Deadlock cho trường hợp mỗi loại tài nguyên có n phiên bản.
- Áp dụng cho hệ thống cấp phát tài nguyên trong đó mỗi loại tài nguyên có thể có nhiều phiên bản.
- Mô phỏng nghiệp vụ ngân hàng (banking)
- Một số giả thiết:

Mỗi tiến trình (process) phải khai báo số lượng tối đa tài nguyên mỗi loại mà process đó cần để hoàn tất công việc.
Khi tiến trình yêu cầu một tài nguyên thì có thể phải đợi mặc dù tài nguyên được yêu cầu đang có sẵn
Khi tiến trình đã có được đầy đủ tài nguyên thì phải hoàn trả trong một khoản thời gian hữu hạn nào đó.

PhamThiThao (I22B)

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

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

Về Đầu Trang Go down

Thế nào là trạng thái an toàn của hệ thống

Bài gửi  PhamThiThao (I22B) on 15/4/2013, 21:53

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

PhamThiThao (I22B)

Tổng số bài gửi : 54
Join date : 19/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  Sponsored content Today at 14:50


Sponsored content


Về Đầu Trang Go down

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