Thảo luận Bài 8

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

Thủ thuật phát hiện deadlock và phục hồi deadlock.

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

1. Thủ thuật phát hiện deadlock:
- Khi nào chúng ta cần giải thuật phát hiện deadlock?
- Câu trả lời phụ thuộc vào hai yếu tố:
+ Deadlock có khả năng xảy ra như thế nào?
+ Có bao nhiêu tiến trình sẽ bị ảnh hưởng bởi deadlock khi nó xảy ra ?
- Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện deadlock sẽ được thực hiện thường xuyên. Tài nguyên được cấp phát cho deadlock sẽ được rảnh rỗi cho đến khi deadlock bị phá vỡ. Ngoài ra, số lượng tiến trình tham gia vào trong chu trình deadlock có thể tăng lên.

- Deadlock xảy ra khi một tiến trình thực hiện yêu cầu mà không được cấp phát tài nguyên tức thì. Yêu cầu này có thể là yêu cầu cuối cùng hoàn thành một chuỗi các tiến trình chờ. Trong trường hợp này chúng ta có thể gọi giải thuật phát hiện deadlock mỗi khi yêu cầu cấp phát không được cấp phát tức thì. Chúng ta không chỉ biết được tập hợp các tiến trình bị deadlock mà còn xác định tiến trình đã gây ra deadlock (Trong thực tế, mỗi tiến 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 tạo ra một chu trình trong đồ thị tài nguyên, mỗi chu trình hoàn thành bởi các yêu cầu gần đây nhất và “gây ra” bởi một tiến trình có thể xác định.

- Tất nhiên, nếu thuật toán phát hiện deadlock được gọi cho mọi yêu cầu tài nguyên điều này có thể gây ra chi phí lớn trong thời gian tính toán. Một phương pháp để giảm chi phí là ta gọi giải thuật trong thời điểm ít thường xuyên hơn - ví dụ mỗi giờ hoặc bất cứ khi nào CPU sử dụng dưới 40%. Nếu giải thuật phát hiện deadlock được gọi vào thời điểm bất kỳ, có thể có nhiều chu trình trong đồ thị tài nguyên. Chúng ta không thể xác định được tiến trình nào “gây ra” deadlock.
2. Phục hồi deadlock:
- Khi giải thuật phát hiện deadlock xác định tồn tại một deadlock, có 2 cách để giải quyết:
+ Một là thông báo cho người điều hành biết deadlock xảy ra và để cho người điều hành khắc phục bằng tay.
+ Hai là để cho hệ thống phục hồi tự động. Có hai tùy chọn để phá vỡ deadlock. Một giải pháp đơn giản là hủy một hay nhiều tiến trình để phá vỡ tồn tại chu trình trong đồ thị cấp phát tài nguyên. Lựa chọn thứ hai là lấy lại một hay nhiều tài nguyên từ tiến trình 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

Các giải pháp xử lý Deadlock

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

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

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

Câu 2: Phân tích 4 điều kiện cần dẫn đến Deadlocks? Phủ định 4 điều kiện thì có tác dụng ngăn chặn deadlock ko xảy ra?

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

* 4 điều kiện cần dẫn đến Deadlocks:
- Loại trừ lẫn nhau (Mutual Exclusion): Ít nhất có 1 tài nguyen có tính không chia sẽ (non-sharable), nghĩa là : Một thời điểm chỉ có 1 tiến trình được sử dụng nó.
VD: Xe qua cầu hẹp. Mỗi thời điểm chỉ có xe ô tô được đi qua cầu thôi. vì cầu hẹp nên không thể dùng chung được.
- Giữ và chờ ( Hold and Wait ) : Có một tiến trình đang giữ 1 tài nguyên và xin thêm tài nguyên đang độc chiếm tiến trình khác.
VD: Xe qua cầu hẹp . 2 xe đang đứng giữa cầu. Mỗi xe đang giữ nửa mặt cầu và muốn "xin" thêm nửa mặt cầu còn lại.
- 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ử dung xong.
VD:Xe qua cầu hẹp .Phải để 2 xe A hoặc B tự nguyện trả lại mặt đường (tức là một trong 2 xe phải lùi lại). Còn có tiếm quyền (Preemption) nghĩa là cầu được lắp chiếc "cẩu" để khi cần thiết "nhấc" 1 ô tô lên khoảng 2 m (tiếm quyền sử dụng mặt cầu của nó) để chiếc kia qua được !
- 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 bời giữ P2, tiến trình P2 chờ TN giữ bởi P3,...,Pn chờ P1.

* Phủ định 4 điều kiện:
- Loại trừ lẫn nhau: để ngăn tình trạng này xảy ra thì ta có thể tạo nhiều tài nguyên dùng chung để các tiến trình sử dụng 1 cách hiệu quả.
- Giữ và chờ: để ngăn tình trạng này ta sẽ cho các tiến trình giữ và chờ trong một khoảng thời gian nhất định nào đó. Như thế, sẽ giải phóng được tài nguyên và các tiến trình khác tiếp tục sử dụng TN đó.
- Không có tiếm quyền: để ngăn tình trạng này thì ta phải làm cho hệ điều hành lấy lại tài nguyên mà tiến trình đó đang giữ (có tiếm quyền).
- Chờ xoay vòng: cách giải quyết cũng giống (Loại trừ lẫn nhau) là phải tạo nhiều TN dùng chung.

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

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

Bài gửi  NguyenThiNgocPhuoc(122A) on 16/4/2013, 00:26

- 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à tại 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 1 tài nguyên đang bị độc chiếm bởi 1 tiến trình khác.

- Không có tiếm quyền (No Preemption): Tài nguyên đang bị giữ bởi 1 tiến trình không thể bị tiếm quyền mà phải đợi tiến trình này tự nguyện trả lại cho hệ thống sau khi đã sử dụng xong.

- Chờ xoay (Circular Wait): Giả sử các tiến trình đang chờ tài nguyên {P1, P2,..., Pn}. Khi đó P1 đang chờ tài nguyên được giữ bởi P2, P2 đang chờ tài nguyên được giữ bởi P3,..., Pn đang chờ tài nguyên được giữ bởi P1.

NguyenThiNgocPhuoc(122A)

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

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

Về Đầu Trang Go down

4 cách ngăn chặn Deadlock

Bài gửi  NguyenThiNgocPhuoc(122A) on 16/4/2013, 00:49

Để 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ể là:

- Với Mutual Exclusion: Đảm bảo tài nguyên nào cũng được dùng chung cùng 1 lúc bởi nhiều tiến trình.

- Với Hold and Wait:
+ Khi tiến trình yêu cầu tài nguyên thì tiến trình đó không được giữ 1 tài nguyên nào khác.
+ Tiến trình phải yêu cầu và được cấp tất cả các tài nguyên mà nó cần ngay đầu công việc.

- Với No Preemption:
+ Khi tiến trình giữ tài nguyên nhưng muốn xin thêm tài nguyên khác thì tài nguyên mà nó đang giữ phải bị tiếm quyền sử dụng và trả lại cho hệ điều hành.
+ KHi tiến trình yêu cầu tài nguyên nhưng tài nguyên đó đang được tiền trình khác giữ (ở trạng thái chờ) thì tài nguyên đó bị tiếm quyền sử dụng và được cấp cho tiến trình đang xin.
- Với Circular Wait: Tài nguyên được cấp theo 1 thứ tự nào đấy.

NguyenThiNgocPhuoc(122A)

Tổng số bài gửi : 15
Join date : 21/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  NguyenThiNgocPhuoc(122A) on 16/4/2013, 01:03

- Một trạng thái được gọi là an toàn (safe) nếu tồn tại ít nhất 1 cách mà trong 1 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ả các tiến trình thực thi hoàn tất.

- Khi đó hệ thống tồn tại 1 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 cả các Pj (j
- Nếu các tài nguyên yêu cầu không đủ, Pi phải chờ cho đến khi tất cả các Pj trả lại các tài nguyên mà chúng chiếm giữ.

- Khi Pi nhận đủ tài nguyên cần thiết, nó sử dụng và trả lại hệ điều hành để P(i+1) có thể vận hành và cứ như thế cho đến Pn.

- Khi 1 tiến trình yêu cầu 1 tài nguyên 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 không an toàn thì tài nguyên đó được cấp phát ngay.

NguyenThiNgocPhuoc(122A)

Tổng số bài gửi : 15
Join date : 21/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  MaiXuanSon (I22B) on 16/4/2013, 09:24

phungvanduong24(I12A) đã viết:

Theo mình bài này bạn giải theo các bước thì đúng nhưng mình sửa lại chổ Ma Trận sau:
P[i] --> Không có i --> Proccess
Allocation[i]--> Không có i --> Allocatin
Max[i] --> Không có i --> Max
Còn các bạn nghỉ sao về bài giải của bạn này?

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  BuiThucTuan(I22B) on 16/4/2013, 09:31

MaiXuanSon (I22B) đã viết:
phungvanduong24(I12A) đã viết:

Theo mình bài này bạn giải theo các bước thì đúng nhưng mình sửa lại chổ Ma Trận sau:
P[i] --> Không có i --> Proccess
Allocation[i]--> Không có i --> Allocatin
Max[i] --> Không có i --> Max
Còn các bạn nghỉ sao về bài giải của bạn này?
Đúng rồi đó. Bảng trạng thái thì không cần có i vi đó la biểu diển các vecto. còn trợ giúp tìm chuổi an toàn thì phải có i

BuiThucTuan(I22B)

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

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

Về Đầu Trang Go down

Trình bày 4 cách ngăn chặn Deadlock.

Bài gửi  LeThiKimNgan67(I11C) on 16/4/2013, 10:11

Để 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 tài 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 tiến trình yêu cầu tài nguyên, nó không được giữ 1 tài nguyên nào khác.
2- tiến trình phải yêu cầu và được cấp tất cả các tài nguyên mà nó cần ngay đầu công việc.
- Với No Preemption:
1- Khi tiến trình giữ tài nguyên mà xin thêm nhưng không được, các tài nguyên mà nó giữ phải bị tiếm quyền sử dụng và trả lại hệ điều hành.
2- Khi tiến trình xin thêm tài nguyên, nếu tài nguyên này đang được giữ bởi tiến trình khác đang ở trạng thái chờ, tài nguyên của tiến trình khác này bị tiếm quyền sử dụng để cấp cho tiến trình đang xin.
- Với Circular Wait: Cấp tài nguyên theo một thứ tự nào đấy.

LeThiKimNgan67(I11C)

Tổng số bài gửi : 23
Join date : 26/02/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  LeThiKimNgan67(I11C) on 16/4/2013, 10:16

- 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 tài nguyên 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 tài nguyên mà chúng chiếm giữ.
- Khi Pi nhận được đủ tài nguyên 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

LeThiKimNgan67(I11C)

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

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

Về Đầu Trang Go down

Trình bày thứ tự sử dụng tài nguyên của tiến trình

Bài gửi  LeThiKimNgan67(I11C) on 16/4/2013, 10:20

Thứ tự sử dụng tài nguyên của tiến trình:
1. Yêu cầu (Request): Nếu không được đáp ứng do bị tiến trình khác giữ => tiến trình phải chờ.
2. Sử dụng (Use): Sau khi được cấp phát, tiến trình thao tác với tài nguyên (thực hiện I/O, in ra giấy, ...).
3. Trả lại (Release): Trả tài nguyên cho HĐH quản lý

LeThiKimNgan67(I11C)

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

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

Về Đầu Trang Go down

Bai 8: Deadlock

Bài gửi  TranAnhTam(I22B) on 16/4/2013, 17:32

Phát hiện Deadlock
Nếu một hệ thống không thực hiện giải thuật ngăn chặn deadlock 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 phải cung cấp:
- Giải thuật xem xét trạng thái của hệ thống để quyết định deadlock có xảy ra hay không.
-Giải thuật phục hồi từ deadlock
Trong thảo luận dưới đây, chúng ta thảo luận chi tiết về hai yêu cầu khi chúng liên quan đến những hệ thống với chỉ một thể hiện của mỗi loại tài nguyên cũng như đối với hệ thống có nhiều thể hiện cho mỗi loại tài nguyên. Tuy nhiên, tại thời điểm này chúng ta chú ý lược đồ phát hiện và phục hồi yêu cầu chi phí bao gồm không chỉ chi phí tại thời điểm thực thi cho việc duy trì thông tin cần thiết và thực thi giải thuật phát hiện mà còn các lãng phí có thể phát sinh trong việc phát hiện từ deadlock.

TranAnhTam(I22B)

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

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

Về Đầu Trang Go down

Giải câu 4 đề thi I11C

Bài gửi  LuGiaLam(I22A) on 16/4/2013, 21:32





bài viết của mình làm trên Word nhưng do khó up nên mình chuyển thành ảnh
Nếu có gì sai sót.
Mong thầy và các bạn chỉ dẫn thêm
Bên dưới mình có kèm file Word gốc
Thank mọi người đã đọc!
Attachments
Câu 4.docx You don't have permission to download attachments.(22 Kb) Downloaded 2 times

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  VoMinhThang(I22B) on 17/4/2013, 13:01

LeThiKimNgan67(I11C) đã viết:Thứ tự sử dụng tài nguyên của tiến trình:
1. Yêu cầu (Request): Nếu không được đáp ứng do bị tiến trình khác giữ => tiến trình phải chờ.
2. Sử dụng (Use): Sau khi được cấp phát, tiến trình thao tác với tài nguyên (thực hiện I/O, in ra giấy, ...).
3. Trả lại (Release): Trả tài nguyên cho HĐH quản lý

Bạn có thể giải thích rõ hơn + ví dụ minh họa được 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

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

Bài gửi  vivanbieu(I22B) on 17/4/2013, 13:09

* 4 điều kiện dẫn đến deadlock:
-loại trừ lẫn nhau(mutual exclusion): có ít nhất một tài nguyên không chia sẽ(không dùng chung được)
vidu: 2 xe qua cầu hẹp tại 1 thời điểm chỉ có 1 xe qua cầu không thể có 2 xe qua cầu được , cầu ko dùng chung được tại 1 thời điểm.
- giữ và chờ (hold and wait): có 1 tiến trình đang giữ 1 tài nguyên và xin thêm 1 tài nguyên khác
vidu: 2 xe qua cầu hẹp và 2 xe bị kẹt mỗi xe giữ một nữa mặt cầu, và chờ thêm nữa mặt cầu còn lại để được qua cầu
- không có tiếm quyền( no preemption): không có chuyện bắt các tiến trình trả lại tài nguyên
vidu: 2 xe qua cầu hẹp , để cho 1 trong 2 xe trả lại mặt cầu còn lại phải có 1 cần cẫu, cẫu 1 trong 2 xe lên cao khoãng 2 m nhường cho xe còn lại.(no preemption không có cái cần cẫu giải quyết việc đó)
- chờ xoay vòng(circular wait): p1 chờ tài nguyên của p2, p2 chờ tài nguyên của p3,p3 chờ tài nguyên của p4,...,p(n-1) chờ tài nguyên cua p(n), p(n) chờ tài nguyên của p1
vidu: 4 xe bị kẹt ở ngã 4 đường xe 1 chờ xe 2 , xe 2 chờ xe 3, xe 3 chờ xe 4, xe 4 chờ xe 1

Trình bày 4 cách ngăn chặn Deadlock.
1. 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.
2. Cho phép hệ thống đi vào trạng thái deadlock, phát hiện nó và phục hồi.
3. 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.
4. 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.
- 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ó thể 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ăg và cần được khởi động lại bằng thủ công.

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

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

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

- Một trạng thái được gọi là an toàn nếu tồn tại 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ảo 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- 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

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

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

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

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

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

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

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

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

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

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

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

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

Very Happy Rất hay. Mình hiểu hơn chúc rồi đó. Nhưng giá trị work ban đầu là (3,3,2) nha bạn.

NguyenHuuMinh80(I22B)

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

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

Về Đầu Trang Go down

RE:4 Điều Kiện Dẫn Đến Deadlock

Bài gửi  VoMinhDien(I22B) on 17/4/2013, 17:18

NguyenThiNgocPhuoc(122A) đã viết:- 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à tại 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 1 tài nguyên đang bị độc chiếm bởi 1 tiến trình khác.

- Không có tiếm quyền (No Preemption): Tài nguyên đang bị giữ bởi 1 tiến trình không thể bị tiếm quyền mà phải đợi tiến trình này tự nguyện trả lại cho hệ thống sau khi đã sử dụng xong.

- Chờ xoay (Circular Wait): Giả sử các tiến trình đang chờ tài nguyên {P1, P2,..., Pn}. Khi đó P1 đang chờ tài nguyên được giữ bởi P2, P2 đang chờ tài nguyên được giữ bởi P3,..., Pn đang chờ tài nguyên được giữ bởi P1.

Hiện giờ có nhiều thuật giải chặn, tránh deadlock xãy ra. Nhưng theo thầy dạy deadlock không thể nào chặn được vì nó luôn tiềm tàng trong máy tính chỉ có cách tránh deadlock mà điềhu này thì thuật giải nhà băng mình đã học giải quyết rất tốt. Thuật giải nhà băng hạn chế tối đa các điều kiện xãy ra deadlock thậm chí không bao giờ cho phép nó 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  LêAnhNgữ(I22A) on 17/4/2013, 20:02

NguyenCaoDuong(I22B) đã viết:






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


Xin lỗi bạn NguyenCaoDuong có nhằm không vậy???
- Thứ 1: trên hình vẽ có ghi Có Deadlock khi tài nguyên trên chu trình chỉ có 1 phiên bản.
- Thứ 2: Thầy có kêu ghi lại ghi chú Thầy nhấn mạnh "Loại tài nguyên ít nhất 1 dấu chấm trở lên"
Vậy thì khó mà chấp nhận đc kết quả đưa ra của bạ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

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

Bài gửi  NguyenCaoDuong(I22B) on 17/4/2013, 21:22

LêAnhNgữ(I22A) đã viết:
NguyenCaoDuong(I22B) đã viết:






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


Xin lỗi bạn NguyenCaoDuong có nhằm không vậy???
- Thứ 1: trên hình vẽ có ghi Có Deadlock khi tài nguyên trên chu trình chỉ có 1 phiên bản.
- Thứ 2: Thầy có kêu ghi lại ghi chú Thầy nhấn mạnh "Loại tài nguyên ít nhất 1 dấu chấm trở lên"
Vậy thì khó mà chấp nhận đc kết quả đưa ra của bạn Shocked

Không sao đâu bạn, chắc mình không nhầm.
- Thứ nhất: Đúng là nếu khi tài nguyên trên chu trình chỉ có 1 phiên bản thì có Deadlock
- Thứ hai: Tại vì theo như câu hỏi của bạn BuiThucTuan(I22B) thì khi tài nguyên R2 chỉ có một phiên bản thì có xảy ra Deadlock không?
Thì theo mình thì sẽ không có Deadlock. Theo như trong Slide của Thầy thì “Có thể không có Deadlock khi 1 tài nguyên thuộc chu trình có nhiều phiên bản”. Loại tài nguyên R1 có 2 phiên bản: 1 phiên bản thuộc một chu trình, còn phiên bản kia được cấp tới tiến trình P2.

Còn đây là theo cách hiểu của mình:
Mình giả sử như loại tài nguyên R2 chỉ có 1 phiên bản. Khi đó bạn sẽ nhìn ra có một chu trình từ P1->R1->P3->R2->P1. Nhưng vì tiến trình P2 có thể trả lại phiên bản của loại tài nguyên R1 và tài nguyên đó có thể được cấp cho tiến trình P1 đang có nhu cầu thì khi đó sẽ không còn chu trình nữa dẫn tới không có Deadlock.
Vậy thì theo bạn thì Có Deadlock hay không có Deadlock? Bạn cứ nói đi để có gì mình hoc hỏi thêm.



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

NguyenCaoDuong(I22B) đã viết:





Không sao đâu bạn, chắc mình không nhầm.
- Thứ nhất: Đúng là nếu khi tài nguyên trên chu trình chỉ có 1 phiên bản thì có Deadlock
- Thứ hai: Tại vì theo như câu hỏi của bạn BuiThucTuan(I22B) thì khi tài nguyên R2 chỉ có một phiên bản thì có xảy ra Deadlock không?
Thì theo mình thì sẽ không có Deadlock. Theo như trong Slide của Thầy thì “Có thể không có Deadlock khi 1 tài nguyên thuộc chu trình có nhiều phiên bản”. Loại tài nguyên R1 có 2 phiên bản: 1 phiên bản thuộc một chu trình, còn phiên bản kia được cấp tới tiến trình P2.

Còn đây là theo cách hiểu của mình:
Mình giả sử như loại tài nguyên R2 chỉ có 1 phiên bản. Khi đó bạn sẽ nhìn ra có một chu trình từ P1->R1->P3->R2->P1. Nhưng vì tiến trình P2 có thể trả lại phiên bản của loại tài nguyên R1 và tài nguyên đó có thể được cấp cho tiến trình P1 đang có nhu cầu thì khi đó sẽ không còn chu trình nữa dẫn tới không có Deadlock.
Vậy thì theo bạn thì Có Deadlock hay không có Deadlock? Bạn cứ nói đi để có gì mình hoc hỏi thêm.


Smile Chào bạn !!!!

(Dựa theo hình phía trên)
- Nếu giả sử của bạn bỏ 1 phiên bản R2. Chu trình P1->R1->P3->R2->P1 thì mình vẫn thấy đc chu trình của nó đấy, nhưng sẽ bị Deadlock bởi vì ngay vị trí R1 có P4 yêu cầu và P1 yêu cầu cùng 1 lúc thì làm sao mà 1 phiên bản phục vụ được cho 2 tiến trình đó????. Nếu như thế thì làm sao mà thực hiện tiếp tục trên R1,P1,P2 như bạn nói được????
- Trường hợp không bỏ phiên bản ở R2 để tiếp tục với giả sử của bạn trên R1,P1,P2: Lên tới R1 như bạn nói, bạn muốn bỏ đi cung yêu cầu của P2, rồi ấn định phiên bản P2 vừa sử dụng cho P1 yêu cầu => không có Deadlock, mình chấp nhận, nhưng thời điểm nào là thích hợp và làm sao để biết P2 trả lại phiên bản cho R1????, khi đó thì không đi vào trọng tâm của vấn đề cần hỏi là "Nếu R2 chỉ có 1 phiên bản thì có xảy ra DeadLock ko???" confused

Thật sự cần câu trả lời !!!! Cảm ơn trước nhé...

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

Bai 8: Deadlock

Bài gửi  TranAnhTam(I22B) on 20/4/2013, 20:13

Tóm tắt nội dung bài học


Tiến trình là một chương trình đang xử lý, mỗi tiến trình có một không gian địa chỉ, một con trỏ
lệnh, một tập các thanh ghi và stack riêng. Các tiến trình chỉ có thể liên lạc với nhau thông qua các
cơ chế do hệ điều hành cung cấp.
+ Mục đích cho nhiều tiến trình hoạt đồng thời là để tăng hiệu suất sử dụng CPU, tăng mức
đô đa nhiêm, tăng tốc độ xử lý.
+ Một tiến trình có thể tạo nhiều tiến trình, mỗi tiến trình thực hiện một chức năng nào đó và thực
thi đồng thời cũng bằng cách chia sẻ CPU. Các tiểu trình trong cùng một tiến trình dùng chung
không gian địa chỉ tiến trình nhưng có con trỏ lệnh, tập các thanh ghi và stack riêng. Các tiểu trình
liên lạc với nhau thông qua các biến toàn cục của tiến trình.
+ Các trạng thái của tiến trình : New, Ready, Running, Blocked, End
+ Tập lệnh của CPU được phân thành tập lệnh đặc quyền (các lệnh nếu sử dụng không chính xác,
có thể ảnh hưởng xấu đến hệ thống) và tập lệnh không đặc quyền (không ảnh hưởng tới hệ thống).
Phần cứng chỉ cho phép các lệnh đặc quyền được thực hiện trong chế độ đặc quyền. Hệ điều hành
hoạt động trong chế độ đặc quyền, các tiến trình của người dùng sẽ hoạt động trong chế độ không
đặc quyền
+ Hệ điều hành quản lý các tiến trình thông qua bảng tiến trình, mỗi mục trong bảng gọi là khối
quản lý tiến trình lưu thông tin về một tiến trình gồm có: định danh của tiến trình , trạng thái tiến
trình, ngữ cảnh của tiến trình, thông tin giao tiếp, thông tin thống kê.
+ Các thao tác trên tiến trình: tạo tiến trình, kết thúc tiến trình, tạm dừng tiến trình, tái kích hoạt
tiến trình, thay đổi độ ưu tiên tiến trình.
+ Mỗi tài nguyên được quản lý bằng một cấu trúc gọi là khối quản lý tài nguyên chứa các thông
tin sau : định danh tài nguyên, trạng thái tài nguyên, hàng đợi trên một tài nguyên, bộ cấp phát.
+ Một số đặc tính của tiến trình: tính hướng nhập/xuất, tính hướng xử lý, tiến trình tương tác hay
xử lý theo lô, độ ưu tiên của tiến trình, thời gian đã sử dụng CPU của tiến trình, thời gian còn lại
tiến trình cần để hoàn tất.
+ Tiến trình được điều phối thông qua bộ điều phối và bộ phân phối. Bộ điều phôi sử dụng một
giải thuật thích hợp để lựa chọn tiến trình được xử lý tiếp theo. Bộ phân phối chịu trách nhiệm cập
nhật ngữ cảnh của tiến trình bị tạm ngưng và trao CPU cho tiến trình được chọn bởi bộ điều phối
để tiến trình thực thi.
+ Mục tiêu của bộ điều phối: sự công bằng, tính hiệu quả, thờii gian đáp ứng hợp lý, thái gian lưu
lại trong hệ thống, thông lượng tối đa. Các nguyên lý điều phối: điÅu phối độc quyÅn, điều phối
không độc quyền.
+ Thái điểm thực hiện điều phối: tiến trình chuyển từ trạng thái running sang trạng thái blocked,
hoặc tiến trình chuyển từ trạng thái running sang trạng thái ready, hoặc tiến trình chuyển từ trạng
thái blocked sang trạng thái ready, hoặc tiến trình kết thúc, hoặc tiến trình có độ ưu tiên cao hơn
xuất hiện.
+ Để thực hiện điều phối, hệ điều hành sử dụng ba loại danh sách là: danh sách tác vụ , danh sách
sẵn sàng, danh sách chờ đợi. Các thuật toán điều phối: FIFO, Round Robin, độ ưu tiên, SJFS, nhiều
mức độ mu tiên,điều phối xổ số.
+ Cơ chế liên lạc giữa các tiến trình: liên lạc bằng tín hiệu, liên lạc bằng đường ống, liên lạc qua
vùng nhớ chia sẻ, liên lạc bằng thông điệp, liên lạc qua socket.
+ Đồng bộ các tiến trình, miền găng. Các giải pháp đồng bộ: semaphore, monitor, trao đổi thông
điệp.
+ Tình trạng tắc nghẽn, điều kiện xuất hiện tắc nghẽn, các phương pháp xử lý tắc nghẽn. Giải
thuật cấp phát tài nguyên

TranAnhTam(I22B)

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

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

Về Đầu Trang Go down

Re: Thảo luận Bài 8: Thuật giải Nhà băng

Bài gửi  nguyenhoanglam_I22B on 21/4/2013, 23:24

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

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


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

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

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


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

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

nguyenhoanglam_I22B

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

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

Về Đầu Trang Go down

Đặc điểm deadlock

Bài gửi  Ng0HaiQuan(i22B) on 21/4/2013, 23:48

Trong một deadlock, các quá trình không bao giờ hoàn thành việc thực thi và
các tài nguyên hệ thống bị buộc chặt, ngăn chặn các quá trình khác bắt đầu.
Mục đích Sau khi học xong chương này, người học nắm được những kiến thức sau:
Hiểu mô hình hệ thống về deadlock
• Hiểu các đặc điểm của deadlock
• Hiểu các phương pháp quản lý deadlock
• Hiểu cách ngăn chặn deadlock
• Hiểu cách tránh deadlock
• Hiểu cách phát hiện deadlock
• Hiểu cách phục hồi từ deadlock

Ng0HaiQuan(i22B)

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

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

Về Đầu Trang Go down

Bai 8: Deadlock

Bài gửi  TranAnhTam(I22B) on 23/4/2013, 17:47

http://www.youtube.com/watch?v=oIXj9FfSyxY

TranAnhTam(I22B)

Tổng số bài gửi : 19
Join date : 28/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:48


Sponsored content


Về Đầu Trang Go down

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