Thảo luận Bài 8

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

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


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

_ 5 lớp học điều cần máy chiếu . Trong khi đó phòng thiết bị chỉ có 1 máy chiếu .điều này dẫn tới ranh chấp chữa các lớp dùng máy chiếu .

_ 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

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

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

Điều kiện xuất hiện tắc nghẽn :
- Mutual exclusion: với mỗi tài nguyên, chỉ có một process sử dụng tại một thời điểm.
- Hold and wait: một process vẫn sở hữu tài nguyên đã được cấp phát trong khi yêu cầu một tài nguyên khác.
- No Preemption: một tài nguyên không thể bị đoạt lại từ chính process đang sở hữu tài nguyên đó.
- Circular wait: tồn tại một chu kỳ khép kín các yêu cầu tài nguyên.

Có 2 tiến trình chờ đợi lẫn nhau : tiến trình này đang chờ được cấp phá tài nguyên đang bị tiến trình kia chiếm giữ và ngược lại .

=> Khi có 4 điều kiện này thì tắc nghẽn xảy ra . Nếu thiếu 1 trong 4 điều kiện trên thì không có tắc nghẽn.

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

Định nghĩa: Tình huống bị kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện(event) có thể chỉ được gây ra bởi một tiến trình khác.
vd1: Hiện tượng deadlock xảy ra tại một ngã 4, đèn xanh đèn đỏ bị hỏng. 4 làn xe đều chạy liên tục ( tại điểm cắt ngã 4 sẽ xảy ra hiện tượng kẹt xe). => Xuất hiện deadlock (Trên thực tế chẳng có ai chịu nhường đường cả.)
vd2: 2 con dê đi qua cầu, dê trắng và dê đen đều mún mình qua cầu chẳng ai chịu nhường ai cả, và cả 2 đều mắc kẹt mãi trên cầu....(có thể tranh chấp dẫn đến xảy ra đến cả 2 con đều rơi xuống cầu) ví dụ này đơn giản dể hiểu và dể nhớ

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

LuongGiaDuc(I12A) đã viết:+Trên RAG, lúc đầu tất cả nhu cầu về tài nguyên của tiến trình phải được khai báo trước bằng các Cung Nhu cầu (Claim edge) Pi · · ·> Rj chỉ báo rằng Pi có thể sẽ yêu cầu Rj
+Cung Nhu cầu Pi · · ·> Rj được chuyển thành Cung Yêu cầu (Request edge) Pi Rj khi Pi thực sự bắt đầu cần đến Rj .
+Nếu yêu cầu Pi Rj được HĐH đáp ứng, cung Pi Rj chuyển thành Cung Ấn định (Assignment edge) Pi Rj nối phiên bản duy nhất của Rj với Pi .
+Khi HĐH xét yêu cầu Pi Rj . Hệ chỉ cấp phát Rj cho Pi nếu Cung Ấn định Pi Rj không tạo ra vòng tròn đồng hướng trong RAG (xét cả các Cung Nhu cầu).
+Thuật giải có độ phức tạp O(n²) với n là số tiến trình trong hệ.

Mình bổ sung thêm ảnh minh họa :

Thuật giải Nhà Băng Là thuật giải cho trường hợp mỗi loại tài nguyên có N phiên bản.
VD:
-5 tiến trình {P0, P1 , ... , P4}
-3 loại tài nguyên: A (10 phiên bản), B (5 phiên bản), C (7 phiên bản).
-Thời điểm T0 :
Đang giữ Max Hệ có
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
Hệ có: Available = (10, 5, 7) - (7, 2, 5) = (3, 3, 2)
Ma trận Need = Max - Allocation: Need
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
Hệ thống trong trạng thái an toàn vì tồn tại chuỗi an toàn < P1, P3, P4, P2, P0 >
Giả sử P1 bây giờ nêu yêu cầu mới là (1, 0, 2)
Yêu cầu này thoả các điều kiện:
1. Request1 Need1 vì (1, 0, 2) ? (1, 2, 2)
2. Request1 Available vì (1, 0, 2) ? (3, 3, 2)
Trạng thái mới:
Đang giữ Need Hệ có
A B C A B C A B C
P0 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
Tồn tại chuỗi an toàn:

-Giả sử tiếp theo P4 nêu yêu cầu (3, 3, 0)
Không đủ tài nguyên vì Request4 > Available
-Giả sử tiếp theo P0 nêu yêu cầu (0, 2, 0)
Đủ để cấp vì Request0 Available nhưng nếu đáp ứng, hệ sẽ chuyển sang trạng thái không an toàn do không tồn tại chuỗi an toàn.

Một hệ thống có 3 loại tài nguyên và 3 tiến trình với trạng thái cấp phát như sau:

Hãy thể hiện trạng thái này bằng Đồ thị cấp phát tài nguyên.

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

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

Code:

#include<stdio.h>
#include<stdlib.h>

int main()
    {
    int num_p,num_re;
    int all[10] [10],re[10],av[10],cl[10][ 10],used[ 10];
    int more[10];
    int i=0;
    int ap,ar;
    int cp,cr;
    int j=0;
    int pi,ci;
    printf("\nNhap so tien trinh : ");
    scanf("%d",&num_p) ;
    printf("\nNhap so tai nguyen : ");
    scanf("%d",&num_re);
    printf("\nNhap gia tri toi da cua moi tai nguyen : \n\n");
    for(i=0;i<num_re;i++)
        {
        printf("R[%d] = ",i+1);
        scanf("%d",&re[i]) ;
        }

    //Allocation
    printf("\n");
    for(ap=0;ap<num_p;ap++)
        {
        printf("Nhap so tai nguyen da cap phat cho tien trinh %d : ",ap+1);
        for(ar=0;ar<num_re;ar++)
        scanf("%d",&all[ar][ap]);
        }

    //claim matrix
    printf("\n");
    for(cp=0;cp<num_p;cp++)
        {
        printf("Nhap so tai nguyen yeu cau cua tien trinh %d : ",cp+1);
        for(cr=0;cr<num_re;cr++)
        scanf("%d",&cl[cr][cp] );
        }

    //Used & Available
    for(i=0;i<num_re;i++)
        {
        used[i]=0;
        for(j=0;j<num_p;j++)
        used[i]=used[i]+all[i] [j];
        av[i]=re[i]-used[ i];
        }

    //check deadlock
    for(pi=0;pi<num_p;pi++)
        {
        int check=0;
        for(ci=0;ci<num_re;ci++)
            {
            more[ci]=cl[ci][pi]- all[ci][pi];
            if(more[ci] <= av[ci])
            check++;
            }
        if(check==num_re)
        goto l1;
        }
    printf("\n\t\t!! XAY RA DEADLOCK !!\n\n");
    getch();
    return 0;

    l1:
    printf("\n\t\t!! SAFE !!\n\n");
    getch();
    return 0;
    }

Đoạn code này có nghĩa là : nếu tất cả tiến trình (cl) đều yêu cầu tài nguyên nhiều hơn giới hạn thì nghĩa là đã xảy ra deadlock. theo mỉnh hiểu là như vậy không biết có đúng không mong thầy và các bạn góp ý thêm.thanks rất nhiều!!!!

• Điều kiện xảy ra Deadlock :

- Điều kiện Mutual-Exclusion:các quá trình thực hiện loại trừ tương hỗ trên vùng tranh chấp

- Điều kiện Hold & Wait:quá trình đang giữ tài nguyên có thể yêu cầu thêm tài nguyên khác.

- Điều kiện No-Preemption:tài nguyên chỉ được giải phóng khi quá trình dùng xong.

- Điều kiện Circular-Wait:các quá trình giữ và đợi tài nguyên tạo thành một vòng đợi luẩn quẩn.

• Giải quyết Deadlock:

- Ngăn ngừa Deadlock:qui định cấp dùng tài nguyên nghiêm ngặt, không cho các điều kiện Deadlock xảy ra.

- Tránh Deadlock: Vẫn cho các điều kiện Deadlock tồn tại, quản lý việc cấp phát tài nguyên hợp lý an toàn.

- Phát hiện Deadlock

- Phục hồi 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ó)

- Định nghĩa Deadlock (Kẹt khoá): Tình huống bị kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện (event) có thể chỉ được gây ra bởi một tiến trình khác.
- Deadlock là tình huống xuất hiện khi hai hay nhiều “hành động” phải chờ một hoặc nhiều hành động khác để kết thúc, nhưng không bao giờ thực hiện được Máy tính: Bế tắc là tình huống xuất hiện khi hai tiến trình phải chờ đợi nhau giải phóng tài nguyên hoặc nhiều tiến trình chờ sử dụng các tài nguyên theo một “vòng tròn.
+ Yêu cầu tài nguyên.
+ Sử dụng tài nguyên.
+ Trả lại tài nguyên.
vd1: Hiện tượng deadlock xảy ra trên 1 ngõ hẹp ( tại 1 thời điểm chỉ duy nhất 1 xe đi qua ). Khi các xe di chuyển tại 1 thời điểm cả 2 đều đi ngang đoạn ngõ hẹp và cả 2 xe đều kẹt ở ngõ => Xuất hiện deadlock (Trên thực tế chẳng có ai chịu nhường đường cả.)

Ưu điểm: ngăn chặn bế tắc (deadlock
prevention) là phương pháp tránh được bế
tắc bằng cách làm cho điều kiện cần không
được thỏa mãn



Nhược điểm:

• _Giảm khả năng tận dụng tài nguyên và giảm
  thông lượng của hệ thống
  _Không mềm dẻo

- Mutual exclusion: với mỗi tài nguyên chỉ có một process sử dụng tại một thời điểm.
- Hold and wait: một process vẫn sở hữu tài nguyên đã được cấp phát trong khi yêu cầu một tài nguyên khác.
- No preemption: một tài nguyên không thể bị đoạt lại từ chính process đang sở hữu tài nguyên đó.
- Circular wait: tồn tại một chu trình khép kín các yêu cầu tài nguyên.

Đ/n: Tình huống bị kẹt của một nhóm tiến trình do mỗi tiến trình trong nhóm đều chờ một sự kiện(event) có thể chỉ được gây ra bởi một tiến trình khác.
ví dụ:
Có hai xe đi ngược chiều cùng qua 1 cây cầu hẹp, mà cầu thì chỉ có một làm xe nên khi hai xe vào đến giữa cầu thì không thể tiếp tục tiến đi được nữa xảy ra kẹt xe(deadlock) vì không người nào chịu nhường đường.

- là tình huống hay trạng thái của hệ thống bị kẹt của 1 nhóm tiến trình hay các tiến trình
vidu: 2 xe qua cầu hẹp ko xe nào nhường xe nào và 2 xe bị kẹt nay cầu
vidu: 2 người bị chết đuối ôm nhau 2 người rơi vào tình huống kẹt
vidu: 4 xe cùng đi vào một ngã 4(deadlock tiềm tàng có khả năng nguy hiểm dễ sãy ra deadlock nhưng ko phải là deadlock)

Để ngăn chặn Deadlock ta phải làm sao cho ít nhất 1 trong 4 điều kiện dẫn đến Deadlock không xảy ra. Cụ thể:

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

- Với Hold and Wait:

1- Khi TT yêu cầu TN, nó không được giữ 1 TN nào khác.

2- TT phải yêu cầu và được cấp tất cả các TN mà nó cần ngay đầu công việc.

- Với No Preemption:

1- Khi TT giữ TN mà xin thêm nhưng không được, các TN mà nó giữ phải bị tiếm quyền sử dụng và trả lại HĐH.

2- Khi TT xin thêm TN, nếu TN này đang được giữ bởi TT khác đang ở trạng thái chờ, TN của TT khác này bị tiếm quyền sử dụng để cấp cho TT đang xin.

- Với Circular Wait: Cấp TN theo một thứ tự nào đấy.

+ Điều kiện loại trừ lẫn nhau: Một tài nguyên không thể sử dụng bởi nhiều hơn một tiến trình tại một thời điểm

+ Điều kiện giữ và chờ: Các tiến trình giữ tài nguyên và chờ tài nguyên mới

+ Điều kiện không thể chiếm: Các tài nguyên không thể bị đòi lại, chúng chỉ có thể được giải phóng bởi chính tiến trình chiếm giử chúng

+ Điều kiện chu trình chờ: Các tiến trình giử tài nguyên và chờ các tài nguyên bị giử bởi tiến trình khác, tạo thành một chu trình. Ví dụ: Tiến trình 1, chiếm A1, chờ A2. Tiến trình 2 chiếm A2, chờ A3,... Tiến trình N chiếm An, chờ A1.

* 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


=> muốn ngặn chặn được Deadlock thì ta phủ định 4 điều kiện sãy ra deadlock thì không bao giờ có chuyện Deadlock cả

Để giải quyết deadlock chúng ta có thể thực hiện theo một trong các cách:
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.

Tài nguyên R2 có 2 phiên bản, 1 phiên bản được cấp cho tiến trình P1, một phiên bản được cấp cho tiến trình P4.
Tài nguyên R1 cũng có 2 phiên bản, 1 phiên bản được cấp cho tiến trình P2, một phiên bản được cấp cho tiến trình P3.
Tiến Trình P1 yêu cầu thêm tài nguyên R1, tiến trình P3 yêu cầu thêm tài nguyên R2.

- Giả sử tại thời điểm 16h: P4 sử dụng xong 1 phiên bản của tài nguyên R2 và trả R2 về cho HDH

- Tại thời điểm 16h10: HDH sẽ cấp 1 phiên bản của tài nguyên R2 cho P3. Lúc này P2 cũng dùng xong R1 và trả R1 lại cho HDH

- Tại thời điểm 16h15: HDH sẽ cấp 1 phiên bản của tài nguyên R1 cho P1

=> Trong trường hợp trên Deadlock sẽ không xảy ra, các tiến trình cần tài nguyên đều được cấp tài nguyên.

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

Trong môi truờng đa chương, nhiều quá trình có thể cạnh tranh một số giới hạn
tài nguyên. Một quá trình yêu cầu tài nguyên, nếu tài nguyên không sẳn dùng tại thời
điểm đó, quá trình đi vào trạng thái chờ. Quá trình chờ có thể không bao giờ chuyển
trạng thái trở lại vì tài nguyên chúng yêu cầu bị giữ bởi những quá trình đang chờ
khác. Trường hợp này được gọi là deadlock (khoá chết).
Hầu hết các hệ điều hành không cung cấp
phương tiện ngăn chặn deadlock nhưng những đặc điểm này sẽ được thêm vào sau đó.
Vấn đề deadlock chỉ có thể trở thành vấn đề phổ biến, xu hướng hiện hành gồm số
lượng lớn quá trình, chương trình đa luồng, nhiều tài nguyên trong hệ thống và đặc
biệt các tập tin có đời sống dài và những máy phục vụ cơ sở dữ liệu hơn là các hệ
thống bó.

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

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

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

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

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

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

NHƯ VÍ DỤ CỦA THẦY CẤP PHÁT TÀI NGUYÊN LÚC 16h



TẠI THỜI ĐIỂM 16h NHÌN MÔ HÌNH NÀY THÌ THẤY CÁC MŨI TÊN MÀU ĐỎ THÀNH 1 VÒNG VẬY KHẢ NĂNG DEADLOCK XẢY RA RẤT LÀ CAO.
NHƯNG THỰC CHẤT MÔ HÌNH NÀY KO XẢY RA HIỆN TƯỢNG DEADLOCK.



TẠI THỜI ĐIỂM 18h5' TIẾN TRÌNH P4 SỬ DỤNG TÀI NGUYÊN CỦA R2 SAU 1 THỜI GIAN P4 KO SỬ DỤNG TÀI NGUYÊN NỮA MÀ CHỈ LÀ XỬ LÝ ĐƠN THUẦN CỦA TIẾN TRÌNH P4, P4 SẼ TRẢ LẠI TÀI NGUYÊN CHO R2, R2 THẤY TÀI NGUYÊN TRỐNG VÀ THẤY P3 ĐANG CHỜ YÊN CẦU CẤP PHÁT THÊM TÀI NGUYÊN, R2 CẤP TÀI NGUYÊN TRỐNG ĐẤY CHO TIẾN TRÌNH P3. VẬY LÀ KHẢ NĂNG XẢY RA DEADLOCK ĐƯỢC GIẢI QUYẾT NHƯ HÌNH DƯỚI THEO MŨI TÊN MÀU XANH.



VẬY VẤN ĐỀ XẢY RA DEADLOCK ĐƯỢC GIẢI QUYẾT.

CÓ GÌ THIẾU SÓT MONG MỌI NGƯỜI GIÚP ĐỠ.