
 !"#$%#&'(!$
1
NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
…………………………………………………………………………………………………………………………………………………
………………………………………………………………………………

Mục Lục
TỔNG QUAN VỀ ĐỀ TÀI

1. Bối cảnh và lý do chọn đề tài
$)*+,-./01234516*6
56478$)*93:3);<+=>
?312647@A6B6+=C+=>?
3D)2?E6BF8
#6+=G>0+,@*.-+HG>0I=J
+93)>?KLM8B.-45145@;45
N9-.-3O=8!;454P<Q<O
=-.-9RP9;SET8
J3U6B)JU@I6*.-@+,-I@
*45-/.4;DD6B3A*A.E3
.8J/.4;+H1V63<;23*0
4;$)*$3/5.W9@G>0
@XRYR6E!450$)*$8
2. Mục tiêu của đề tài
Z$6-)J3*
Z$Y6
Z$+,./0
Z$Y
Z$
Z$)
Z$?I[
 !"#$%#&'(!$
2

3. Yêu cầu của đề tài
• "U)
• #-4\
• ]^4D+,-3;./6
• _;6`\B66O3#4*

• "Y35+U`@6X45135+U`3
;BX=
• !<a3;+,-K@Kbb@_Kbb
 !"#$%#&'(!$
3

Chương 1. CƠ SỞ LÝ THUYẾT
1. Giới thiệu về Deadlock
1.1 Tiến trình
1.1.1 Định nghĩa
- #;-STO2=6B+,-O45
6478!9I6BU1;O4+,-SPc
;-T3/6)OBG>0;-D
+,-8
- +HG6,3P63))*8
- '6BDB@3U+,-6BPB8
1.1.2 Phân loại
K9O;-d
- #;-)*8
- #;-+=>?8
1.1.3 Các thành phần của tiến trình
- O6e)8
- O<)8
- OG;38
- KOB)O+H).;6)S(LT3B
STBG>08
1.1.4 Vòng đời của tiến trình
 !"#$%#&'(!$
4


1.1.5 Vấn đề lập lịch tiến trình
- fJ+H451>?/*,J+H459SKLMT
- 9@1P^J=>?KLM;-
+=>?3)J8
1.2 Deadlock
1.2.1 Giới thiệu
- #.-P;-@.-=;-9
=4OQO3-45X451P<Q<
;-=8#+=H4+HES9;T8
1.2.2 Mô hình hệ thống
- B)J2J45<O+H^g<*.-
O8K454+H^*O@6hO2
6BJ)GP8iBU@jKLM3;P
kGAS+64@l[T<7?3*O458!;)J
9KLM@-O45KLM9)8#+,D@O45
64996)8
- !;6B.-4516B)O45-3)AA
2)O454R/6e4518!;99-
)GP3UO45R+HP
lH08#7?@6B)J99648$O6449
+HPlaUO45;9.-
.^664<)8#45@;6B64Q1m364
Q1)-+=aQ1mG664+,D
3U455n1+HPl6h648
- B.-/4516B45+U>?9@3//
9>?98B.-9451*45+9
+H451D)3?+H98KX0@J45+H45
13+H.J+HgB45o9)J8!9
@6B.-45164;)Jc98
- +U;B*+=@6B.-9>?6B

45c2Dd
 !"#$%#&'(!$
5

- p51d;451+H2-S7?@45+H
aQ.-T-.-451/=U99
+H458
- f>?d.-9*45S7?@;4564@
.-964T
- "/9d.-/9458
- p513/945=E)J8#7?+4513
/9;P@6Q39@A3/9BU8p51
3/9459O+H.=q3
)89@6h+=H>?@)*6
/6/r.->?4513+HA458B/
)J6h.-/94+HA458!;
6B.-451456459)+HA6B
.-@99+H563H=4548
- BH.-O6h.-H
4=D)69+HOcQ.-H8
!<D)6X.^64;Q^43/9
458K4594530S7?@64@l[@
BU3jKLMT4450S7?@@6@
6T8#45@OD)9`;8
- 6OO@XGC)J3Ugl[8"/>
6h.-<6Bgl[48\^4=@;6h.-4516Bg
l[-.-RQO8h.-
=6BD)sgl[+H/9t69+H^4cQ6B
<.-=8#7?46O5.;
aO458

- u5.*O458#7?@GC6B)
J3U6B6436Bgl[8"/>@.-L<gl[3
.-L<648!;L451643L451gl[-
G/48
 !"#$%#&'(!$
6

- B+=-<2?I/.^6Y
)U3A*4dK+,-I2>353A*
3-*I9O545+Hn8
1.2.3 Đặc điểm của Deadlock
#6B@.-=3)D3
45)JPBY@Y.-V18
#+UX/+,/.4;3A*
@XR6/Y666/8
vNhững điều kiện cần thiết gây ra deadlock:
o #+=H9;J*)G/4a6B
X)Jd
(1) Loại trừ hỗ tương: 7A6B45/+H<;B
nWl@c6B.-Oa6B=69>?
458!;6B.-451459@.-451/
O6[;45+H/98
(2) Giữ và chờ cấp thêm tài nguyên: .-/<7A6B
453=45566)+H<Q.
-8
(3) Không đòi lại tài nguyên từ quá trình đang giữ chúng: K45
P:OWl@459+H/9cD0Q.
-<9@.-93?8
(4) Tồn tại chu trình trong đồ thị cấp phát tài nguyên: 6BH.
-wLx@Ly@z@L{=69Lx=6B45+H<

QLy@Ly=45<QL|@z@Lvy=45
+H<Q.-Lx8
vKXA6OrA/J*)/a
G/48*)=H+,-+;*)<v3v=3-
;J*)B8
1.3 Các phương pháp xử lý Deadlock
K9}/.4;,/@9d
- KX9>?6B2Y4@/6
/r)JR=3O
 !"#$%#&'(!$
7

- KX9C)J3O@)93
?I8
- KX9.3A*43/3==
G/4)J8"/4+Ha*)*@/
M!(]8
- ~*4Rc93*3;3*
8
2. Thuật toán nhà băng của Dijsktra
2.1 Giới thiệu
- '6BA453+HQ
8
- •?)J9*O45
- #6Or63)A
+HJ9A/O45+HGP+U@9
6OG6*)G/4A/;-
451459G/48f9D3O
4.4;P3)A458
2.2 Cấu trúc dữ liệu

- !*AX<)/+H4-Y/\8!<A
X<)46eO)JA458"EJ
.-)J36JO45)J8KX1
AX<)d
• Availabled6B39*PJ+H45o
a6hO8!;€3•‚ƒ@9)O45
„

oa8
• Maxd6B6GPlJ+HJ4516h.
-8!;G•@‚ƒ@-.-L

9451*A
)O45„

8
• Allocationd6B6GPlJ+H456h
O)+HAU6h.-8!;€•@‚ƒ@-.
-L

)+HA)O45„

8
 !"#$%#&'(!$
8

• Needd6B6GP45145:O6h.
-8!;!•@‚ƒ@-.-L

9156)

O45„

3?98KX0r@!•@‚ƒ
G•@‚…€•@‚8
- KAX<)4;g=3*7+U3P8,/
3)-4/\@X;30)8"E]3p
39*8KX9r]†p;3c;]•‚†p•‚
A/ƒy@|@z@8#7?@;]ƒSy@‡@}@|T3pƒSx@}@|@yT-p†]@pˆ
];p†]3p‰]8
- KX9G6GC6h:6€3!+
<336;UX+€
 
3!
 
+,28
_€

GP45)+HAU.-L

W3
!

GP45g6.-L

93`451
3?98
2.3 Thuật toán kiểm tra an toàn
- "/GP)JQO49+H6/
+d
Bước 1: "EŠ3‹39*63+,28iQ

OŠdƒ€33‹•‚dƒŒƒy@|@z@8
Bước 2: #-6d
T‹•‚ƒŒ
T!†Š8!;9@4U+U•
Bước 3: ŠdƒŠb€‹•‚dƒ43*+U|8
Bước 4: !;‹•‚ƒA/@-)JQO8
"/49451B2O6G|.4;PO
48
2.4 Thuật toán yêu câu tài nguyên
- K„.3451.-L8!;„.•‚ƒ@-.-
L6J)O45„8i6B45145+HD
)Q.-L@-OB+HD)d
Bước 1: !;„.†!@4U+U|8!+HO@6B
*)h3-.-3+H.451J98
Bước 2: !;„.†€3@4U+U}8!+HO@L/=
3-45o98
 !"#$%#&'(!$
9

Bước 3: "/>)JA45+H451U.-L
r4gOd
€3dƒ€3…„.W
€dƒ€b„.W
!dƒ!…„.W
!;;./OA45@-P+H
3.-L+HA4598#45@;O
6U@-L/=„.3OA45u
+H?I8
 !"#$%#&'(!$
10


Chương 2. THIẾT KẾ VÀ XÂY DỰNG CHƯƠNG TRÌNH
1. Phân tích yêu cầu
\Y8
(dE[Œ8G6^G•@‚@€•@‚36/#•‚8
- \1d€•@‚ƒx8
- #;45145;;-A
Ždi6O;-45145@;
-A453;?451;;-A8
dfJ;-
dfJ45
 !"#$%#&'(!$
11

2. Xây dựng chương trình
2.1 Cấu trúc hoạt động của chương trình
 !"#$%#&'(!$
12

2.2 Các biến, hàm sử dụng trong chương trình
STT Tên hàm, biến Chức năng
y €•‚•‚ /€245eA
| G•‚•‚ /G245J6;-
451
} !•‚•‚ /!2456;-1

• €3•‚ /€3245N9
• #•‚ /#+gJ459N
• #6y•‚@6|•‚@
6}•‚

}6/+O6=}6/€3@
€@!
‡ „.•‚ /245451
‘ #6•‚•‚ /+45=A9
45
m K6•‚ /+;-/S6ƒ
yT
yx „ fJ45
yy ’ fJ;-
y| (ST $6A4<)[Œ8G
y} €3ST $6-66/3•‚•‚
y• !ST $6-66/•‚•‚
y• (fŒST $66@/3*y;@x;

y• “„.ST $645145
y‡ „.”‹S•@T $645145
y‘ \ST $6+<)
ym „ST $6?<)
|x ST $6P3)16
|y €S•@•@T $6B6/
|| Ž”yS•@T $6GA6/y*
|} Ž”|S•@T $6GA6/|*
|• KLS•.@T $6A45
|• ŠST $663A45;
-=
|• „34”„ST $6I45;-A
|‡ KST $66;-A
 !"#$%#&'(!$
13


3. Kết quả thử nghiệm.
3.1 Dữ liệu từ file input.txt
 !"#$%#&'(!$
14

3.2 Demo.
 !"#$%#&'(!$
15

 !"#$%#&'(!$
16

 !"#$%#&'(!$
17

 !"#$%#&'(!$
18

 !"#$%#&'(!$
19

Chương 3. ĐÁNH GIÁ KẾT QUẢ
1. Đánh giá
$O;
• Thuật toán banker xuất phát từ giả thiết số tài nguyên là cố định. Nhưng bởi vì
các tài nguyên không thể làm việc mãi (ví dụ dừng lại để bảo dưỡng) do đó
chúng ta không thể cho rằng số lượng tài nguyên là cố định.
• Thuật toán đòi hỏi rằng số người dùng là không đổi. Yêu cầu đó cũng không
thực tế, vì trong các hệ đa chương trình, số lượng người dùng luôn thay đổi
• Thuật toán đòi hỏi bộ phận phân phối tài nguyên phải đảm bảo thoả mãn tất

cả các yêu cầu sau khoảng thời gian hữu hạn nào đó. Tuy nhiên trong thực tế
người ta cần những con số cụ thể hơn nhiều.
• Cũng như thế, thuật toán đòi hỏi người dùng phải trả lại các tài nguyên được
cấp, sau một khoảng thời gian nào đó- và trong thực tế cũng cần các chỉ số cụ
thể.
• Thuật toán yêu cầu người dùng phải báo trước số lượng lớn nhất tài nguyên
anh ta cần. Nhưng sự phân phối tài nguyên ngày càng phải linh động, và do
đó càng khó đánh giá yêu cầu lớn nhất. Vì máy tính ngày càng thân thiện với
người dùng nên sẽ ngày càng nhiều người dùng không có hình dung chính xác
về số tài nguyên lớn nhất mà anh ta sẽ cần, thay vào đó khi nào cần tài nguyên
người dùng mới yêu cầu.
8 #+)*6\@
–,6)*./71234516*65
647@.9eXXYR,3*6E!45'7$)
*$8
2. Những hạn chế
K+,-63`:+D.3B3`:5;
B@1/O56)+,-D.3B
,
 !"#$%#&'(!$
20

PHỤ LỤC
Mã lệnh chương trình
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
// khai bao bien toan cuc
int alloc[10][10];
int max[10][10];

int need[10][10];
int avail[10];
int total[10];
int temp1[10],temp2[10][10],temp3[10][10],task[10];
int request[10],tam[10][10],complete[10];
int r,p; // r: so tai nguyen, p: so tien trinh
// nguyen mau ham
void Input();// lay du lieu tu txt
void Available();// tim mang avail[][]
void Need(); // tim mang need[][]
int IsSefe(); // ham kiem tra an toan
void EnterRequest();// ham nhap cac yeu cau tai nguyen
void Request_F(int *b, int n); // ham yeu cau tai nguyen
void Backup();// ham sao luu du lieu
void Resore();// ham khoi phuc du lieu
void Menu();// hien thi danh sach viec can lam
void Add(int *a,int*b,int n); // cong hai mang
void Out_1(int *a,int n);// xuat mang mot chieu
void Out_2(int *a,int n, int m);// xuat mang 2 chieu
void CapPhat(int *request, int a);// cap phat tai nguyen
cho tien trinh a
void waiting();// kiem tra va cap phat tai nguyen cho cac
tien trinh dang cho
void Recovery_R(int a);// thu hoi tai nguyen
void Check();//kiem tra cac tien trinh hoan tat de cap
phat tai nguyen cho cac tien trinh dang cho
//
void Input()
{
int i,j;

FILE* fp=fopen("input.txt","rt");
if(fp==NULL)
{
 !"#$%#&'(!$
21

printf("/nLoi mo file!!!\nNhan phim bat ki de mo
lai file\n");
getch();
Input();
}
else
{
fscanf(fp,"%d",&r);// lay so luong tai nguyen
for(i=0;i<r;i++) fscanf(fp,"%d",&total[i]);
fscanf(fp,"%d",&p);// lay so luong tien trinh
// lay bang Allocation
for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
fscanf(fp,"%d",&alloc[i][j]);
}
// lay bang Max
for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
{
fscanf(fp,"%d",&max[i][j]);
}
}

fclose(fp);
}
}
//
void Available()
{
int i,j,k=0;
for(i=0;i<r;i++)
{
for(j=0;j<p;j++)
{
avail[k]+=alloc[j][i];
}
avail[k] = total[i]- avail[k];
k++;
}
}
//
void Need()
 !"#$%#&'(!$
22

{
int i,j;
for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
{
need[i][j] = max[i][j] - alloc[i][j];
}

}
}
//
void Output_1(int *a,int n)
{
int i;
for(i=0;i<n;i++)
printf("r[%d]=%3d\t",i,a[i]);
}
//
void Output_2(int a[10][10],int n,int m)
{
int i,j;
for(i=0;i<n;i++)
{
printf("P[%d] ",i);
for(j=0;j<m;j++)
{
printf("%3d",a[i][j]);
}
printf("\n");
}
}
//
void Backup()
{
for (int i=0;i<r;i++) temp1[i]=avail[i];
for (int i=0;i<p;i++)
for(int j=0;j<r;j++)
{

temp2[i][j]=alloc[i][j];
temp3[i][j]=need[i][j];
}
}
//
 !"#$%#&'(!$
23

void Restore()
{
for (int i=0;i<r;i++) avail[i]=temp1[i];
for (int i=0;i<p;i++)
for(int j=0;j<r;j++)
{
alloc[i][j]=temp2[i][j];
need[i][j]=temp3[i][j];
}
}
//
void Add(int*a,int*b,int n)
{
for (int i=0;i<n;i++)
a[i]+=b[i];
}
//
void CapPhat(int *request,int a)
{
int i;
for(i=0;i<r;i++)
{

alloc[a][i] += request[i];
avail[i] -= request[i];
need[a][i] -= request[i];
}
}
//
void Recovery_R(int a)
{
int i;
for(i=0;i<r;i++)
{
avail[i]+=alloc[a][i];
alloc[a][i]=0;
}
printf("\n So luong tai nguyen san dung.
(Available) \n");
Output_1(avail,r);
}
//
void Menu()
{
 !"#$%#&'(!$
24

printf("\n==============================");
printf("\n1: tiep tuc yeu cau tai nguyen");
printf("\n2: exit");
printf("\nMoi Chon: ");
printf("\n=> ");
}

//
void waiting()
{
int i,j,s,a[10],s1,s2;
for(i=0;i<p;i++)
{
s=0;
for(j=0;j<r;j++)
{
s+=tam[i][j];
}
if(s)
{
for(j=0;j<r;j++)
{
a[j]=tam[i][j];
}
if(complete[i]==0)
{
printf("\n
");
printf("\n => cap phat tai nguyen cho tien
trinh P[%d] dang cho",i);
printf("\n Tai nguyen ma P[%d] yeu
cau.\n",i);
Output_1(a,r);// in tai nguyen dang cho
luu o mang a
//
s1=0;
for(j=0;j<r;j++)

{
if(a[j] > need[i][j])
s1=1;
}
if(s1)
{
 !"#$%#&'(!$
25