Thảo luận Bài 8

Trang 1 trong tổng số 3 trang 1, 2, 3  Next

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

Thảo luận Bài 8

Bài gửi  Admin on 27/4/2014, 07:40

Thảo luận những vấn đề liên quan đến Bài 8.

Admin
Admin

Tổng số bài gửi : 291
Join date : 18/02/2009

Xem lý lịch thành viên http://hedieuhanh.forumvi.net

Về Đầu Trang Go down

Hướng giải bài toán khác theo giải thuật nhà băng

Bài gửi  VanPhuAnhTuan95(HLT3) on 27/4/2014, 22:48

Đề bài như sau (theo slide bài giảng của thầy):




Bài làm:


Mong thầy và các bạn cùng tham khảo và cho nhận xét về bài làm. Cảm ơn thầy và các bạn.

VanPhuAnhTuan95(HLT3)

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

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  VanPhuAnhTuan95(HLT3) on 27/4/2014, 23:43

Chào mọi người,
Trong câu b của bài tập cuối Slide (Slide 8.29) của thầy có nói là P3 xin thêm 1 ổ băng nữa, điều đó có nghĩa là phần Need của P3 cộng thêm 1 ổ đĩa hay phần Allocation được cộng lên 1 vậy mọi người? Mình gặp vướng mắc ở chỗ đó khi làm bài, mong nhận được sự giúp đỡ từ mọi người.

VanPhuAnhTuan95(HLT3)

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

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

Về Đầu Trang Go down

Trình bày 4 điều kiện cần dẫn đến DEADLOCK

Bài gửi  NguyenChiKien(HLT3) on 28/4/2014, 17:19

- 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 {P1, P2, ..., Pn}, khi đó P1 chờ TN giữ bởi P2, P2 chờ TN giữ bởi P3 , ... , Pn chờ P1.
avatar
NguyenChiKien(HLT3)

Tổng số bài gửi : 44
Join date : 23/03/2014
Age : 34

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  NguyenChiKien(HLT3) on 28/4/2014, 17:24

VanPhuAnhTuan95(HLT3) đã viết:Chào mọi người,
Trong câu b của bài tập cuối Slide (Slide 8.29) của thầy có nói là P3 xin thêm 1 ổ băng nữa, điều đó có nghĩa là phần Need của P3 cộng thêm 1 ổ đĩa hay phần Allocation được cộng lên 1 vậy mọi người? Mình gặp vướng mắc ở chỗ đó khi làm bài, mong nhận được sự giúp đỡ từ mọi người.
Allocation đó bạn!!!!
avatar
NguyenChiKien(HLT3)

Tổng số bài gửi : 44
Join date : 23/03/2014
Age : 34

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

Về Đầu Trang Go down

Ngăn chặn DEADLOCK

Bài gửi  NguyenChiKien(HLT3) on 28/4/2014, 17:29

Để 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.
avatar
NguyenChiKien(HLT3)

Tổng số bài gửi : 44
Join date : 23/03/2014
Age : 34

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

Về Đầu Trang Go down

Thuật giải tránh deadlock dùng RAG (áp dụng cho trường hợp các 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:

Bài gửi  LamQuocVu(HLT3) on 28/4/2014, 22:36

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


LamQuocVu(HLT3)

Tổng số bài gửi : 31
Join date : 17/03/2014

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

Về Đầu Trang Go down

Xin lỗi mình gửi thiếu dữ liệu

Bài gửi  LamQuocVu(HLT3) on 28/4/2014, 22:39




LamQuocVu(HLT3)

Tổng số bài gửi : 31
Join date : 17/03/2014

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

Về Đầu Trang Go down

Định nghĩa, điều kiện xuất hiện deadlock

Bài gửi  VoMinhQuang (HLT3) on 29/4/2014, 18:40

Định nghĩa:

Một tập hợp các tiến trình được định nghĩa ở trong tình trạng deadlock (kẹt khoá) khi mỗi tiến trình trong tập hợp đều chờ đợi một sự kiện mà chỉ có một tiến trình khác trong tập hợp mới có thể phát sinh được.

Nói cách khác, mỗi tiến trình trong tập hợp đều chờ được cấp phát một tài nguyên hiện đang bị một tiến trình khác cũng ở trạng thái blocked chiếm giữ. Như vậy 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ụ: kẹt xe trên đường, kẹt mạng khi có quá nhiều người truy cập vào website cùng một lúc,...

Vấn đề "Bữa ăn tối của các nhà hiền triết": 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 deadlock.

Bữa ăn tối của các nhà hiền triết

Điều kiện xảy ra deadlock:
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, một tài nguyên không thể chia sẻ được hệ thống cấp phát chỉ cho một tiến trình , khi tiến trình sử dụng xong tài nguyên này, hệ thống mới thu hồi và cấp phát tài nguyên cho tiến trình khác.


  • 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, nghĩa là: Có ít nhất hai tiến trình chờ đợi lẫn nhau: tiến trình này chờ được cấp phát tài nguyên đang bị tiến trình 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 một trong 4 điều kiện trên thì không có tắc nghẽn.

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.

VoMinhQuang (HLT3)

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

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

Về Đầu Trang Go down

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

Bài gửi  VoMinhQuang (HLT3) on 29/4/2014, 18:54

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

VoMinhQuang (HLT3)

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

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

Về Đầu Trang Go down

Chấm dứt tiến trình deadlock

Bài gửi  VoMinhQuang (HLT3) on 29/4/2014, 18:57

- Hệ thống thu hồi tài nguyên của các tiến trình bị DeadLock :Phá vỡ toàn bộ chu trình bị Deadlock nhưng phí tổn khá lớn vì nhiều tiến trình có thể đã thực thi trong thời gian dài và một phần kết quả thực thi bị loại bỏ sau đó có thể phải thực hiện lại.

- Lần lượt chấm dứt từng tiến trình cho tới khi phá vỡ chu trình bế tắc (deadlock). Cứ sau khi kết thúc một tiến trình,hệ thống kiểm tra xem bế tắc còn hay không?

- Việc chấm dứt tiến trình có thể không đơn giản. Nếu chấm dứt một tiến trình đang trong quá trình cập nhật file có thể bị lỗi file .

Nếu sử dụng phương pháp thứ 2 nêu trên thì hệ thống phải xác định thứ tự chấm dứt tiến trình hoặc nhóm tiến trình để phá vỡ bế tắc. Quyết định này phụ thuộc vào chính sách của hệ thống,tương tự như vấn đề điều phối CPU

Như vậy các vấn đề cần phải tính đến là:
- Độ ưu tiên của tiến trình.
- Tiến trình thực thi được bao lâu và cần bao lâu để kết thúc.
- Tiến trình sử dụng bao nhiêu tài nguyên và bao gồm những tài nguyên nào?
- Tiến trình cần thêm bao nhiêu tài nguyên để hoàn thành.
- Có bao nhiêu tiến trình cần bị chấm dứt.
- Tiến trình có tương tác với người dùng hay không ?

VoMinhQuang (HLT3)

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

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  VanPhuAnhTuan95(HLT3) on 30/4/2014, 15:50

VanPhuAnhTuan95(HLT3) đã viết:Đề bài như sau (theo slide bài giảng của thầy):




Bài làm:


Mong thầy và các bạn cùng tham khảo và cho nhận xét về bài làm. Cảm ơn thầy và các bạn.
bài giải này có ổn không mọi người?

VanPhuAnhTuan95(HLT3)

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

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  VanPhuAnhTuan95(HLT3) on 30/4/2014, 15:51

NguyenChiKien(HLT3) đã viết:
VanPhuAnhTuan95(HLT3) đã viết:Chào mọi người,
Trong câu b của bài tập cuối Slide (Slide 8.29) của thầy có nói là P3 xin thêm 1 ổ băng nữa, điều đó có nghĩa là phần Need của P3 cộng thêm 1 ổ đĩa hay phần Allocation được cộng lên 1 vậy mọi người? Mình gặp vướng mắc ở chỗ đó khi làm bài, mong nhận được sự giúp đỡ từ mọi người.
Allocation đó bạn!!!!
ok, thks bạn, mình sẽ làm thử

VanPhuAnhTuan95(HLT3)

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

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

Về Đầu Trang Go down

BÀI TẬP SLIDE 8.29

Bài gửi  VanPhuAnhTuan95(HLT3) on 1/5/2014, 14:00

Mọi người xem bài giải như thế đúng chưa?



VanPhuAnhTuan95(HLT3)

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

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

Về Đầu Trang Go down

Bài gửi  NguyenLamGiang28 on 2/5/2014, 09:53

- Câu a cùng đáp án.
- Câu b:
+ Sau khi cấp cho P3 1 ổ đĩa nữa thì mình không tìm ra được chuỗi an toàn => KHÔNG nên đáp ứng yêu cầu của P3.
**Ra cùng 1 đáp án nhưng cách làm khác nhau và mình cũng cũng không biết nên làm theo cách nào. Có ai có câu trả lời chính xác không?

NguyenLamGiang28

Tổng số bài gửi : 12
Join date : 28/04/2014

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

Về Đầu Trang Go down

Những điều kiện cần thiết gây ra deadlock

Bài gửi  LeThanhQuan (TH10A2) on 3/5/2014, 13:21

Trường hợp deadlock có thể phát sinh nếu bốn điều kiện sau xảy ra cùng một
lúc trong hệ thống:
1) Loại trừ hỗ tương: ít nhất một tài nguyên phải được giữ trong chế độ
không chia sẻ; nghĩa là, chỉ một quá trình tại cùng một thời điểm có thể sử
dụng tài nguyên. Nếu một quá trình khác yêu cầu tài nguyên đó, quá trình
yêu cầu phải tạm dừng cho đến khi tài nguyên được giải phóng.
2) Giữ và chờ cấp thêm tài nguyên: quá trình phải đang giữ ít nhất một tài
nguyên và đang chờ để nhận tài nguyên thêm mà hiện đang được giữ bởi
quá trình khác.
3) Không đòi lại tài nguyên từ quá trình đang giữ chúng: Các tài nguyên
không thể bị đòi lại; nghĩa là, tài nguyên có thể được giải phóng chỉ tự ý
bởi quá trình đang giữ nó, sau khi quá trình đó hoàn thành tác vụ.
4) Tồn tại chu trình trong đồ thị cấp phát tài nguyên: một tập hợp các quá
trình {P0, P1,…,Pn} đang chờ mà trong đó P0 đang chờ một tài nguyên được giữ bởi P1, P1 đang chờ tài nguyên đang giữ bởi P2,…,Pn-1 đang chờ tài nguyên đang được giữ bởi quá trình P0.
Chúng ta nhấn mạnh rằng tất cả bốn điều kiện phải cùng phát sinh để deadlock
xảy ra. Điều kiện chờ đợi ch trình đưa đến điều kiện giữ-và-chờ vì thế bốn điều kiện
không hoàn toàn độc lập.

LeThanhQuan (TH10A2)

Tổng số bài gửi : 6
Join date : 05/04/2014

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  NguyenVanNgoc (HLT3) on 3/5/2014, 15:31

NguyenChiKien(HLT3) đã viết:Để 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.

NguyenVanNgoc (HLT3)

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

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

Về Đầu Trang Go down

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

Bài gửi  truongphamhuytruong.i11c on 3/5/2014, 17:22

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

+ Ngăn ngừa hoặc tránh xa, đả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 rồi khôi phục lại.

+ Bỏ qua dead lock , coi như ko có dead trong hệ thống

Ngăn chặn deadlock : là đảm bảo ít nhất một trong bốn điều kiện không thể xuất hiện
a.Ngăn cản lẫn nhau – đảm bảo là hệ thống không có các file không thể chia sẻ.
Một tiến trình không bao giờ phải chờ tài nguyên có thể chia sẻ
Ví dụ: read-only files(vì file read only thì nhiều tiến trình truy xuất nó cũng không ảnh hưởng gì-nội dung file không thay đổi)
Một số tài nguyên là không thể chia sẻ
Ví dụ: chế độ toàn màn hình


b.Giữ và đợi cấp thêm tài nguyên – phải đảm bảo rằng mỗi khi một tiến trình yêu cầu một tài nguyên, nó không giữ bất kỳ tài nguyên nào khác.
Đòi hỏi tiến trình yêu cầu và được phân phối tất cả các tài nguyên của nó trước khi nó bắt đầu thực hiện, hoặc chỉ cho phép tiến trình yêu cầu các tài nguyên khi không có tài nguyên nào cả.


c.Không có ưu tiên: không đòi lại tài nguyên từ tiến trình đang giữ chúng_
Nếu một tiến 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 thể được phân phối ngay cho nó thì tất cả các tài nguyên nó đang giữ được giải phóng.
Các tài nguyên ưu tiên được thêm vào danh sách tài nguyên dành cho tiến trình đang chờ đợi.
Tiến trình sẽ được khởi động lại chỉ khi nó có thể lấy lại các 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.


d.Chờ đợi vòng tròn – áp dụng một thứ tự tuyệt đối cho tất cả các loại tài nguyên: mỗi loại được gắn một số nguyên
Mỗi tiến trình yêu cầu các tài nguyên theo thứ tự tăng dần: chỉ có thể nhận được tài nguyên có trọng số cao hơn của bất kỳ tài nguyên nào nó đang giữ
Muốn có tài nguyên j, tiến trình phải giải phóng tất cả các tài nguyên có trọng số i > j (nếu có)

Tài liệu này mình kiếm được trên mạng, các bạn đọc rồi cho ý kiến nha
.

truongphamhuytruong.i11c

Tổng số bài gửi : 50
Join date : 26/08/2011

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  truongphamhuytruong.i11c on 3/5/2014, 17:25

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.

truongphamhuytruong.i11c

Tổng số bài gửi : 50
Join date : 26/08/2011

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

Về Đầu Trang Go down

Thêm ví dụ về Deadlock

Bài gửi  truongphamhuytruong.i11c on 3/5/2014, 17:28

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

truongphamhuytruong.i11c

Tổng số bài gửi : 50
Join date : 26/08/2011

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

Về Đầu Trang Go down

Khái niện đồ thị cấp phát tài nguyên.

Bài gửi  truongphamhuytruong.i11c on 3/5/2014, 17:32

Đồ 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.
[img][/img]

truongphamhuytruong.i11c

Tổng số bài gửi : 50
Join date : 26/08/2011

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

Về Đầu Trang Go down

Trạng thái an toàn và giải pháp tránh deadlock

Bài gửi  NguyenHaAn(I22A) on 3/5/2014, 18:53

Thế nào là trạng thái an toàn của hệ thống?
Một trạng thái được gọi là an toàn “safe” nếu tồn tại ít nhất một cách mà trong một
khoảng thời gian hữu hạn nào đó, hệ thống có thể cấp phát tài nguyên thỏa mãn cho tất cả process thực thi hoàn tất .
Khi đó hệ thống tồn tại một Chuỗi an toàn {P1, P2, … , Pn } bao gồm tất cả các tiến trình sao cho với mỗi Pi, các tài nguyên mà nó yêu cầu có thể được đáp ứng bởi số lượng hiện có cộng thêm của tất cả các Pj mà j < i.
Nếu các TN yêu cầu không có đủ, Pi phải chờ cho đến khi tất cả các Pj trả lại các TN mà chúng chiếm giữ.
Khi Pi nhận được đủ TN cần thiết, nó sử dụng và trả lại HĐH để Pi+1 có thể vận hành, cứ như thế cho đến Pn
Khi một process yêu cầu một tài nguyên đang sẵn có, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay.

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

NguyenHaAn(I22A)

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

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

Về Đầu Trang Go down

Định nghĩa Deadlock

Bài gửi  LeVanVan69 (I22B) on 3/5/2014, 21:06


            Định nghĩa: Là tình huống dừng tạm thời 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ụ: Tại ngã 4, 4 xe từ 4 hướng khác nhau cùng đến giao lộ, không xe nào chịu nhường đường cho xe nào nên tất cả đều phải chờ đến khi có đường trống để đi, kết quả là kẹt xe. Như thế tất cả 4 xe đều trong trạng thái chờ hay nói cách khác các tiến trình đang chờ tài nguyên của nhau và cứ xoay vòng và như thế tất cả tiến trình đều bị dừng (deadlock).





Được sửa bởi LeVanVan69 (I22B) ngày 3/5/2014, 21:17; sửa lần 1.

LeVanVan69 (I22B)

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

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  LeVanVan69 (I22B) on 3/5/2014, 21:13

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

1/ 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ó.
2/ 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.
3/ 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.
4/ 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 .





Được sửa bởi LeVanVan69 (I22B) ngày 3/5/2014, 21:28; sửa lần 2.

LeVanVan69 (I22B)

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

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

Về Đầu Trang Go down

Ngăn chặn Deadlock

Bài gửi  LeVanVan69 (I22B) on 3/5/2014, 21:27

1/ Ngăn cản lẫn nhau, đảm bảo là hệ thống không có các file không thể chia sẻ.
           Một tiến trình không bao giờ phải chờ tài nguyên có thể chia sẻ
Ví dụ: read-only files(vì file read only thì nhiều tiến trình truy xuất nó cũng không ảnh hưởng gì-nội dung file không thay đổi)
     2/ Giữ và đợi cấp thêm tài nguyên, phải đảm bảo rằng mỗi khi một tiến trình yêu cầu một tài nguyên, nó không giữ bất kỳ tài nguyên nào khác. Đòi hỏi tiến trình yêu cầu và được phân phối tất cả các tài nguyên của nó trước khi nó bắt đầu thực hiện, hoặc chỉ cho phép tiến trình yêu cầu các tài nguyên khi không có tài nguyên nào cả.
     3/Không có ưu tiên_không đòi lại tài nguyên từ tiến trình đang giữ chúng_
          Nếu một tiến 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 thể được phân phối ngay cho nó thì tất cả các tài nguyên nó đang giữ được giải phóng. Các tài nguyên ưu tiên được thêm vào danh sách tài nguyên dành cho tiến trình đang chờ đợi. Tiến trình sẽ được khởi động lại chỉ khi nó có thể lấy lại các 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.
      4/ Chờ đợi vòng tròn – áp dụng một thứ tự tuyệt đối cho tất cả các loại tài nguyên: mỗi loại được gắn một số nguyên, mỗi tiến trình yêu cầu các tài nguyên theo thứ tự tăng dần: chỉ có thể nhận được tài nguyên có trọng số cao hơn của bất kỳ tài nguyên nào nó đang giữ.


LeVanVan69 (I22B)

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

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


Sponsored content


Về Đầu Trang Go down

Trang 1 trong tổng số 3 trang 1, 2, 3  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