TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VINH  KHOA CÔNG NGHỆ THÔNG TIN
BÀI TẬP LỚN
MÔN HỆ PHÂN TÁN
TÌM HIỂU PHÁT TRÀN KHÔNG ĐỒNG BỘ
Danh sách nhóm Và công việc của từng người như sau:
ooo000ooo
1.Lê Thị Lương : Tìm hiểu Lý thuyết-Cài đặt chương trình
2.Trần Thị Thanh Liên : Tìm hiểu Lý thuyết-Cài đặt chương trình
3.Hoàng Anh Tuấn : Lý thuyết-Báo cáo-cài đặt
4.Nguyễn Thị Ngọc Gái : Tìm hiểu nội dung công việc
5.Trần Thị Châu : Tìm hiểu nội dung công việc
6.Nguyễn Thị Hoài : Tìm hiểu nội dung công việc
7.Nguyễn Thị Diễn : Tìm hiểu nội dung công việc
8.Lê Thị Lam : Tìm hiểu nội dung công việc
9.Nguyễn Ngọc Dũng : Tìm hiểu nội dung công việc
10.Hoàng Trọng Cường : Tìm hiểu nội dung công việc
11.Nguyễn Thị Hương : Tìm hiểu nội dung công việc
Giảng viên hướng dẫn : Ths Trần Thị Gia - - Sinh viên thực hiên : Nhóm 2
1
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VINH  KHOA CÔNG NGHỆ THÔNG TIN
NỘI DUNG BÁO CÁO

A.Chuẩn bị nội dung làm bài tập lớn
1.Tư tưởng
2.Tài liệu tham khảo
3.Giới thiệu ngôn ngữ lập trình C++ áp dụng cài đặt
B.Giới thiệu chung về hệ phân tán
1.Tổng quan về hệ phân tán
2.Phân loại hệ phân tán
3.Vai trò của hệ phân tán
4.Đặc trưng của hệ phân tán

2.Tài liệu tham khảo
* Hệ phân tán
+ Giáo trình :Hệ phân tán – GV- Ths Trần Thị Gia – Khoa CNTT – ĐHSPKT VInh
+ Giáo trình :Tập bài giảng chuẩn hóa của Bộ môn Mạng và HTTT, Khoa CNTT,-Đại học
SPKT Vinh
+ Nguyễn Thúc Hải, mạng máy tính và các hệ thống mở, NXBGD, 1999
+ giáo trình : tập bài giảng chuẩn hoá của Bộ môn Truyền thông và Mạng máy tính, Khoa
Công nghệ Thông tin, Đại học Bách khoa Hà nội
* Lập trình C++
+ Giáo trình :Lập trình hướng đối tượng– GV- Ths Lưu Hương Giang – Khoa CNTT –
ĐHSPKT VInh
+ Nguyễn Thanh Thuỷ, Lập trình hướng đối tượng với C++,NXB Khoa học và kỹ thuật,1999
+ Nguyễn Thanh Thuỷ - Nguyễn Quang Huy, Bài tập lập trình ngôn ngữ C,NXB Khoa học và
Kỹ thuật,2003
3.Giới thiệu ngôn ngữ lập trình áp dụng cài đặt
C++ là ngôn ngữ lập trình hướng đối tượng và là sự mở rộng của ngôn ngữ C.Nó là ngôn
ngữ lập trình rát quan trọng, là tiền đề để phát triển của mọi ngôn ngữ lập trình và cũng là
tiền đề để phát triển ngôn ngữ lập trình Java, Chương trình C++ của chúng em chạy dựa
trên phần mềm c free v5.0 hoặc DEV-C.
B.Giới thiệu chung về hệ phân tán
1.Tổng quan về hệ phân tán
Các khái niệm hệ phân tán
• Định nghĩa 1: Hệ phân tán là tập hợp các máy tính tự trị được kết nối với nhau bởi
một mạng máy tính và được cài đặt phần mềm hệ phân tán.
• Định nghĩa 2: Hệ phân tán là một hệ thống có chức năng và dữ liệu phân tán trên các
trạm (máy tính) được kết nối với nhau bởi một mạng máy tính.
• Định nghĩa 3: Hệ phân tán là một tập các máy tính độc lập giao tiếp với người dùng
như một hệ thống thống nhất, toàn vẹn.
=> Như vậy có thể nói : HPT = MMT+ Phần mềm hệ phân tán
- Ví dụ: bộ đa xử lý, mạng cục bộ, Internet,ngân hàng tự động,hệ thống thương mại điện tử

• Tính co giản.
• Tính chịu lỗi.
• Tính an toàn an ninh.
5.Mục tiêu hệ phân tán
• A. Kết nối người sử dụng và tài nguyên: giải quyết bài toán chia sẻ tài nguyên trong hệ
thống (resource sharing)
• B. Tính trong suốt: Ẩn giấu sự rời rạc và những nhược điểm nếu có của hệ phân tán
đối với người sử dụng và những nhà lập trình ứng dụng ( Theo tiêu chuẩn ISO cho
HPT ISO/IS/10746 tên là “ open distributed processing reference model” 1995 đã cụ
thể hóa 8 dạng trong suốt:….)
• C. Tính mở (openness): HPT gọi là mở nếu nó cung cấp các dịch vụ theo các quy tắc
chuẩn mô tả cú pháp và ngữ nghĩa của dịch vụ đó.
• D. tính co giãn (Scalability): thich nghi với sự thay đổi quy mô của hệ thống
6.Lý thuyết hệ phân tán
• Phát hiện và khái quát hóa các vấn đề cơ bản
• Phát biểu các vấn đề một cách chính xác
• Thiết kế các giải thuật để giải quyết các vấn đề
Giảng viên hướng dẫn : Ths Trần Thị Gia - - Sinh viên thực hiên : Nhóm 2
4
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VINH  KHOA CÔNG NGHỆ THÔNG TIN
• Chứng minh tính đúng đắn của các giải thuật
• Phân tích độ phức tạp của các giải thuật
– Dựa trên các tiêu chí như thời gian thực hiện, lượng bộ nhớ sử dụng, số thông
báo trao đổi
• Chứng minh các kết quả về tính không thể và các kết quả cận dưới
– Phụ thuộc nhiều vào giả thiết
7.Các lĩnh vực ứng dụng
• Hệ điều hành: Các tiến trình cần giao tiếp với nhau.
• Cơ sở dữ liệu phân tán: Các server CSDL cần được phối hợp đồng bộ.
• Khắc phục lỗi phần mềm: Cho chạy nhiều chýõng trình để nâng cao độ tin cậy.

• Các cạnh không định hýớng của đồ thị = các kênh hai chiều nối từng cặp nút
• Mỗi bộ xử lý pi gắn nhãn cho các kênh kề nó 1, 2, 3, r (r là bậc của Pi).
4.Trạng thái
• Mỗi bộ xử lý là một máy trạng thái
– Mỗi trạng thái của p
i
có 2r thành phần đặc biệt outbuf
i
[l] và inbuf
i
[l], với l = 1 r
• outbuf
i
[l] chứa các thông báo p
i
gửi cho nút bên cạnh trên kênh l nhưng
chưa đến nơi
• inbuf
i
[l] chứa các thông báo p
i
nhận được trên kênh l nhưng chưa xử lý
– Tập trạng thái Q
i
chứa một tập con gồm các trạng thái ban đầu
• Ở trạng thái ban đầu các inbuf
i
[l] phải rỗng
– Hàm chuyển của p
i

• Các điều kiện đối với chuỗi các cấu hình xen kẽ sự kiện mô tả hoạt động của hệ thống
– Điều kiện an toàn : điều kiện phải đúng với mọi tiền tố hữu hạn của chuỗi mô tả
• Chưa có điều gì xấu xảy ra
– Điều kiện sống động : điều kiện phải đúng một số lần nhất định (có thể vô hạn
lần)
Giảng viên hướng dẫn : Ths Trần Thị Gia - - Sinh viên thực hiên : Nhóm 2
6
p
0
p
1
p
3
p
2
1
2
3
1
1
1
2
2
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VINH  KHOA CÔNG NGHỆ THÔNG TIN
• Điều tốt sẽ đến
• Thực hiện là một chuỗi mô tả thỏa mãn mọi điều kiện an toàn đặt ra
• Thực hiện thỏa mãn mọi điều kiện sống động đặt ra được gọi là thực hiện thỏa đáng
7.Thực hiện không đồng bộ
• Hệ thống gọi là không đồng bộ nếu không có cận trên đối với thời gian
– từ lúc thông báo được gửi đi cho đến lúc giao

[l] chứa các thông báo p
i
nhận được trên kênh l nhưng chưa xử lý
Giảng viên hướng dẫn : Ths Trần Thị Gia - - Sinh viên thực hiên : Nhóm 2
7
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VINH  KHOA CÔNG NGHỆ THÔNG TIN
- Khởi tạo:
• Với p
0
, color là green và tất cả các outbuf chứa M
• Với các bộ xử lý khác, color là red và các outbuf rỗng
- Hàm chuyển
• Nếu M nằm trong inbuf và color là red thì đổi color thành green và gửi M
vào tất cả các outbuf
- Bước lặp:
• Trong các bộ xử lý kề với P
0
ta chọn một P
i
nào đó rồi thực hiện hai sự
kiện:
+ Sự kiện giao tại P
i
từ P
0
+ Sự kiện tính bởi P
i
• Sau đó tiếp tục xét một trong các bộ xử lý kề với P
i
mà chưa xét (đang ở

Các thông báo gửi
đi
+
Sự kiện tính
- Xử lý các thông báo gửi đến
- Chuyển trạng thái bộ xử lý
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VINH  KHOA CÔNG NGHỆ THÔNG TIN
• Một thông báo được gửi đi trên mỗi cạnh theo mỗi hướng
• Độ phức tạp thời gian
– Thời gian tối đa đến khi kết thúc giải thuật là D + 1, trong đó D là đường kính của
đồ thị
• Đến thời gian t, thông báo M tới được tất cả các bộ xử lý cách p
0
t cạnh
(hoặc nhỏ hơn)
10.Tính thoả đáng
• Với mô hình không đồng bộ, một thực hiện là thỏa đáng nếu
– Mọi thông báo trong các outbuf nhất định sẽ được giao
– Mọi bộ xử lý thực hiện vô hạn bước tính
11.Độ phức tạp
• Tập trung vào hiệu suất xấu nhất
• Độ phức tạp thông báo là số tối đa các thông báo gửi đi trong thực hiện thỏa đáng
• Độ phức tạp thời gian là thời gian tối đa đến khi kết thúc trong thực hiện thỏa đáng
-Với mô hình không đồng bộ đo dựa trên các giả thiết
• Thời gian xử lý một sự kiện là không đơn vị
• Thời gian truyền một thông báo (từ sự kiện gửi đến sự kiện xử lý thông
báo) tối đa là một đơn vị
– Lưu ý : Độ chính xác của giải thuật không đồng bộ cần được chứng minh độc lập
với các giả thiết thời gian
D.Áp dụng giải thuật phát tràn không đồng bộ

(p
0
p
2
)=M
- color(p
0
)=green, color(p
1
)=color(p
2
)=red, outbuf
i
()={ }
Giảng viên hướng dẫn : Ths Trần Thị Gia - - Sinh viên thực hiên : Nhóm 2
9
p
2
p
0
p
1
M
M
green
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VINH  KHOA CÔNG NGHỆ THÔNG TIN
• Bước lặp 1: Xét P
1
là nút kề với P
0

1
rồi chọn một nút bất kỳ đang ở trạng thái màu đỏ để xét tiếp.
Ở đây ta chọn P
2
là nút kề tiếp theo để xét. Tức là ta tiến hành thực hiện liên tiếp hai
sự kiện giao và tính cho nút P
2
• Tại bước lặp này mọi nút trên mạng đều được chuyển sang màu xanh và thuật toán
kết thúc
Giảng viên hướng dẫn : Ths Trần Thị Gia - - Sinh viên thực hiên : Nhóm 2
p
0
p
2
p
1
green
red red
M
M
p
0
p
2
p
1
green
red red
M
Sự kiện giao

green



=
=
redPcolo
MPPinbuf
)(
)(
1
101
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VINH  KHOA CÔNG NGHỆ THÔNG TIN
Minh hoạ tổng thể :
2.Cài đặt giải thuật
#include<iostream.h>
#include<iomanip.h>
int a[50][50],b[50],n,v;
int tim(int i, int m) //xet dinh i da chuyen thanh mau green chua?
{int j;
j=0;
while(( j<=m)&& b[j]!=i) j++;
if (j>m) return 0; // chua chuyen thanh mau green
else return 1; //da chuyen mau green
Giảng viên hướng dẫn : Ths Trần Thị Gia - - Sinh viên thực hiên : Nhóm 2
p
0
p
2
p

p
2
p
1
green
M
M
M
green
green
M
p
0
p
2
p
1
green
red red
M
M
p
0
p
2
p
1
green
red red
M

M
M
Sự kiện giao
tại p
2
từ p
1
M
11
TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT VINH  KHOA CÔNG NGHỆ THÔNG TIN
}
int main()
{int i,j;
cout<<"\n nhap so dinh cua do thi:";
cin>>n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=0;
i=0;
while(i<n)
{ do
{cout<<"\n nhap dinh ke voi dinh "<<i<<" ("<<n<<": het dinh ke) : ";
cin>>j;
if (j!=i && j>=0 && j<n)
{a[i][j]=1;

}
}while(j!=n);
i++;
}

if (i==n)
{
// neu cac dinh ke voi dinh k da chuyen mau green , ta xet cac dinh con chua chuyen
thanh green cua dinh cha cua k trong do thi
int g;
g=j-1;
while((i==n)&&(g>=0))
{i=0;
int h;
h=b[g];
while(!((a[h][i]==1)&& !tim(i,j)) && i<n )
i++;
g ;
}
// neu cac dinh con da chuyen thanh green, ta xet cac dinh con lai
if (i==n)
{i=0;
while((i<n)&& (a[i][i]!=0)) i++;
}
}
j++;
b[j]=i;
a[i][i]=2; // chuyen dinh i thanh mau green
}

cout<<"\n ket qua phat tran khong dong bo :";
for(i=0;i<n;i++) cout<<b[i]<<" ";
}
}while(v>=0 && v<n);
return 0;