behattieu_xiteen
New Member
Download miễn phí Báo cáo Tìm hiểu phát tràn không đồng bộ
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
5.Mục tiêu hệ phân tán
6.Lý thuyết hệ phân tán
7.Các lĩnh vực ứng dụng
C.Phát tràn không đồng bộ
1.Nêu Khái niệm
2.Nguyên tắc hoạt động
3.Mô hình truyền thông báo
4.Trạng thái
5.Cấu hình
6.Thực hiện và tính thỏa đáng
7.Thực hiện không đồng bộ
8.Giải thuật phát tràn không đồng bộ
9.Độ phức tạp giải thuật phát tràn
10.Tính thoả đáng
11.Độ phức tạp
D.Áp dụng giải thuật phát tràn không đồng bộ
1.Ví dụ minh họa
2.Cài đặt giải thuật
3.Chạy chương trình
.Tư tưởng mục tiêu môn học
• Hiểu được các đặc trưng và mục tiêu thiết kế hệ phân tán – Các vấn đề kỹ thuật cơ bản của hệ phân tán.
• Nắm vững các kiến thức hệ thống về phương pháp luận và công cụ để xây dựng và phát triển các hệ phân tán.
• Thông qua Bài tập lớn môn học sinh viên có thể bước đầu tập dượt nghiên cứu và triển khai ứng dụng tiếp cận với các công nghệ liên quan đến 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 hay 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ử
• Hệ phân tán vs. hệ song song :
- Hệ song song phối hợp nhiều bộ xử lý nhằm giải quyết một vấn đề cho trước một cách nhanh nhất .
- Trong hệ phân tán, mỗi bộ xử lý nói chung có chýõng trình làm việc riêng bán độc lập, vì lợi ích chung nên cần phối hợp hành động với nhau.
• Mục đích môn học là nghiên cứu các công cụ và kỹ thuật xây dựng phần mềm phân tán
– Tập trung vào khía cạnh giải thuật
2.Phân loại hệ phân tán
• Trước đây, HPT dược chia thành 3 loại: hệ điều hành hệ phân tán, cơ sở dữ liệu hệ phân tán và các hệ thống tính toán hệ phân tán
• Ngày nay, HPT được phân chia như sau:
- HPT mang tính hệ thống: hệ điều hành phân tán
- HPT mang tính ứng dụng: các hệ thống truyền tin phân tán
3.Vai trò của hệ phân tán
• Trao đổi tin cậy: Tiền đề để phát triển các mạng máy tinh.
• Chia sẻ tài nguyên: Giúp giảm chi phí hệ thống.
• Nâng cao độ tin cậy thông qua sao lăp: Hệ thống vẫn hoạt động khi một bộ phận gặp sự cố.
• Nâng cao hiệu suất thông qua song song hóa: Thực hiện công việc chung hay chia sẻ công việc.
• Đơn giản thiết kế thông qua chuyên dụng hóa: Phân tích hệ thống thành các tiến trình tác hợp với nhau
4.Đặc trưng của hệ phân tán
• Kết nối người sử dụng và tài nguyên.
• Tính trong suốt.
• Tính mở.
• 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 đề
• 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.
• Mạng máy tính: Thiết kế các dịch vụ điều khiển mạng.
• Kiến trúc đa xử lý: Các bộ xử lý kết nối với nhau cần phối hợp thực hiện.
C.Phát tràn không đồng bộ
1.Khái niệm mô hình không đồng bộ
• Hệ thống gọi là không đồng bộ nếu không có cận trên cố định với thời gian.
– Từ lúc thông báo được gửi đi cho đến lúc giao.
– hay giữa các bước thực hiện của bộ xử lý.
• Ví dụ: Internet.
• Trên thực tế cận trên là lớn và không cố định có thể coi là hệ thống không đồng bộ.
2.Nguyên tắc hoạt động
• Nguyên tắc cơ bản của hệ phân tán là sự đồng bộ và đa tiến trình, trong trường hợp này, các tiến trình truy cập cùng một lúc và nhiều tài nguyên, để tránh điều này của giải pháp pháp chúng ta thực hiện truy cập loại trừ lẫn nhau, hay thực hiện một cách không đồng bộ bộ nhằm mục đích:
– Tránh xung đột đường truyền
– Tham gia sự ưu tiên trong đối tượng hệ thống máy .
• Giải thuật này chia thành 2 giải pháp cơ bản:
– Thứ nhất: đưa ra một thông điệp đặc biệt giữa các tiến trình, được gọi là biểu tượng token…
• Phụ thuộc vào tổ chức của tiến trình
• Tiến trình phải đợi tiến trình khác để xử lý(deadlock)
– Thứ hai: Một tiến trình muốn truy cập vào tài nguyên khác thì phải được sự cho phép của tiến trình khác.
• Tập trung dữ liệu.
• Phân tán dữ liệu.
3.Mô hình truyền thông báo
• Các nút của đồ thị = các bộ xử lý p0, p1,..., pn-1
• 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 pi có 2r thành phần đặc biệt outbufi[l] và inbufi[l], với l = 1..r
• outbufi[l] chứa các thông báo pi gửi cho nút bên cạnh trên kênh l nhưng chưa đến nơi
• inbufi[l] chứa các thông báo pi nhận được trên kênh l nhưng chưa xử lý
– Tập trạng thái Qi 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 inbufi[l] phải rỗng
– Hàm chuyển của pi có đầu vào (trạng thái khả truy nhập) không bao gồm các outbufi[l] và đầu ra là một trạng thái có các inbufi[l] rỗng
5.Cấu hình
• Cấu hình là một vectơ C = (q0,..., qn-1) trong đó qi là một trạng thái của pi
– Trạng thái của các biến outbuf của cấu hình thể hiện các thông báo đang di chuyển trên các kênh truyền
– Cấu hình ban đầu là một vectơ (q0,..., qn-1) thỏa mãn mỗi qi là một trạng thái ban đầu của pi
• Nói cách khác ở cấu hình ban đầu tất cả các bộ xử lý đều ở trạng thái ban đầu tương ứng
• Có thể coi cấu hình là trạng thái tổng thể của toàn bộ hệ thống
6.Thực hiện và tính thỏa đáng
• 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)
• Đ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
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
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
5.Mục tiêu hệ phân tán
6.Lý thuyết hệ phân tán
7.Các lĩnh vực ứng dụng
C.Phát tràn không đồng bộ
1.Nêu Khái niệm
2.Nguyên tắc hoạt động
3.Mô hình truyền thông báo
4.Trạng thái
5.Cấu hình
6.Thực hiện và tính thỏa đáng
7.Thực hiện không đồng bộ
8.Giải thuật phát tràn không đồng bộ
9.Độ phức tạp giải thuật phát tràn
10.Tính thoả đáng
11.Độ phức tạp
D.Áp dụng giải thuật phát tràn không đồng bộ
1.Ví dụ minh họa
2.Cài đặt giải thuật
3.Chạy chương trình
.Tư tưởng mục tiêu môn học
• Hiểu được các đặc trưng và mục tiêu thiết kế hệ phân tán – Các vấn đề kỹ thuật cơ bản của hệ phân tán.
• Nắm vững các kiến thức hệ thống về phương pháp luận và công cụ để xây dựng và phát triển các hệ phân tán.
• Thông qua Bài tập lớn môn học sinh viên có thể bước đầu tập dượt nghiên cứu và triển khai ứng dụng tiếp cận với các công nghệ liên quan đến 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 hay 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ử
• Hệ phân tán vs. hệ song song :
- Hệ song song phối hợp nhiều bộ xử lý nhằm giải quyết một vấn đề cho trước một cách nhanh nhất .
- Trong hệ phân tán, mỗi bộ xử lý nói chung có chýõng trình làm việc riêng bán độc lập, vì lợi ích chung nên cần phối hợp hành động với nhau.
• Mục đích môn học là nghiên cứu các công cụ và kỹ thuật xây dựng phần mềm phân tán
– Tập trung vào khía cạnh giải thuật
2.Phân loại hệ phân tán
• Trước đây, HPT dược chia thành 3 loại: hệ điều hành hệ phân tán, cơ sở dữ liệu hệ phân tán và các hệ thống tính toán hệ phân tán
• Ngày nay, HPT được phân chia như sau:
- HPT mang tính hệ thống: hệ điều hành phân tán
- HPT mang tính ứng dụng: các hệ thống truyền tin phân tán
3.Vai trò của hệ phân tán
• Trao đổi tin cậy: Tiền đề để phát triển các mạng máy tinh.
• Chia sẻ tài nguyên: Giúp giảm chi phí hệ thống.
• Nâng cao độ tin cậy thông qua sao lăp: Hệ thống vẫn hoạt động khi một bộ phận gặp sự cố.
• Nâng cao hiệu suất thông qua song song hóa: Thực hiện công việc chung hay chia sẻ công việc.
• Đơn giản thiết kế thông qua chuyên dụng hóa: Phân tích hệ thống thành các tiến trình tác hợp với nhau
4.Đặc trưng của hệ phân tán
• Kết nối người sử dụng và tài nguyên.
• Tính trong suốt.
• Tính mở.
• 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 đề
• 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.
• Mạng máy tính: Thiết kế các dịch vụ điều khiển mạng.
• Kiến trúc đa xử lý: Các bộ xử lý kết nối với nhau cần phối hợp thực hiện.
C.Phát tràn không đồng bộ
1.Khái niệm mô hình không đồng bộ
• Hệ thống gọi là không đồng bộ nếu không có cận trên cố định với thời gian.
– Từ lúc thông báo được gửi đi cho đến lúc giao.
– hay giữa các bước thực hiện của bộ xử lý.
• Ví dụ: Internet.
• Trên thực tế cận trên là lớn và không cố định có thể coi là hệ thống không đồng bộ.
2.Nguyên tắc hoạt động
• Nguyên tắc cơ bản của hệ phân tán là sự đồng bộ và đa tiến trình, trong trường hợp này, các tiến trình truy cập cùng một lúc và nhiều tài nguyên, để tránh điều này của giải pháp pháp chúng ta thực hiện truy cập loại trừ lẫn nhau, hay thực hiện một cách không đồng bộ bộ nhằm mục đích:
– Tránh xung đột đường truyền
– Tham gia sự ưu tiên trong đối tượng hệ thống máy .
• Giải thuật này chia thành 2 giải pháp cơ bản:
– Thứ nhất: đưa ra một thông điệp đặc biệt giữa các tiến trình, được gọi là biểu tượng token…
• Phụ thuộc vào tổ chức của tiến trình
• Tiến trình phải đợi tiến trình khác để xử lý(deadlock)
– Thứ hai: Một tiến trình muốn truy cập vào tài nguyên khác thì phải được sự cho phép của tiến trình khác.
• Tập trung dữ liệu.
• Phân tán dữ liệu.
3.Mô hình truyền thông báo
• Các nút của đồ thị = các bộ xử lý p0, p1,..., pn-1
• 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 pi có 2r thành phần đặc biệt outbufi[l] và inbufi[l], với l = 1..r
• outbufi[l] chứa các thông báo pi gửi cho nút bên cạnh trên kênh l nhưng chưa đến nơi
• inbufi[l] chứa các thông báo pi nhận được trên kênh l nhưng chưa xử lý
– Tập trạng thái Qi 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 inbufi[l] phải rỗng
– Hàm chuyển của pi có đầu vào (trạng thái khả truy nhập) không bao gồm các outbufi[l] và đầu ra là một trạng thái có các inbufi[l] rỗng
5.Cấu hình
• Cấu hình là một vectơ C = (q0,..., qn-1) trong đó qi là một trạng thái của pi
– Trạng thái của các biến outbuf của cấu hình thể hiện các thông báo đang di chuyển trên các kênh truyền
– Cấu hình ban đầu là một vectơ (q0,..., qn-1) thỏa mãn mỗi qi là một trạng thái ban đầu của pi
• Nói cách khác ở cấu hình ban đầu tất cả các bộ xử lý đều ở trạng thái ban đầu tương ứng
• Có thể coi cấu hình là trạng thái tổng thể của toàn bộ hệ thống
6.Thực hiện và tính thỏa đáng
• 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)
• Đ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
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links