Luận Văn Thạc Sĩ: Tính Chất và Ứng Dụng của Mạng Petri

Luận văn thạc sĩ toán học phân tích hus một số tính chất của mạng petri và ứng dụng luận văn ths toán học 60 46 35, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi

• Tác giả: Bùi Việt Hải
• Người hướng dẫn: TS. Nguyễn Thị Minh Huyền
• Trường học: Đại học Quốc gia Hà Nội - Trường Đại học Khoa học Tự nhiên
• Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán
• Đề tài: Một số tính chất của mạng Petri và ứng dụng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: MẠNG PETRI CƠ SỞ VÀ MẠNG CÁC ĐIỀU KIỆN - BIẾN CỐ
• 1.1. Các khái niệm cơ bản về mạng Petri
• 1.2. Ví dụ về mạng Petri
• 1.3. Các khái niệm cơ sở
• 1.4. Phân loại mạng Petri
• 1.5. Mạng các điều kiện – biến cố
• 1.6. Các trường hợp và các bước
• 1.7. Hệ điều kiện - biến cố
• 1.8. Hệ chu trình và hệ sống. Sự tương đương của các hệ điều kiện – biến cố
• 1.9. Các hệ mạng an toàn và đầy đủ hóa hệ điều kiện – biến cố
• 1.10. Đồ thị các trường hợp
• 1.11. Các quá trình của hệ điều kiện – biến cố
• 2. CHƯƠNG 2: MẠNG VỊ TRÍ/ CHUYỂN VÀ MỘT SỐ TÍNH CHẤT CỦA MẠNG PETRI
• 2.1. Mạng vị trí chuyển. Khái niệm mạng vị trí chuyển
• 2.2. Mạng an toàn và quá trình chuyển mạng về mạng an toàn
• 2.3. Biểu diễn đại số cho các mạng Petri
• 2.4. Đồ thị phủ của mạng Petri. Ngôn ngữ sinh bởi lưới mạng
• 2.5. Một số tính chất của mạng Petri
• 2.6. Tính chất bị chặn của mạng Petri
• 2.7. Tính chất sống của mạng Petri
• 2.8. Tính chất tắc nghẽn của mạng Petri
• 2.9. Tính chất thuận nghịch của mạng Petri
• 3. CHƯƠNG 3: ỨNG DỤNG MẠNG PETRI TRONG LẬP TRÌNH HƯỚNG ĐỐI TƯỢNG TƯƠNG TRANH
• 3.1. Phương pháp đối tượng hợp tác
• 3.2. Sử dụng phương pháp COO giải quyết bài toán “Bữa ăn tối của các triết gia”
• 3.3. Trình biên dịch SYROCO dựa trên phương pháp COO
• DANH MỤC BẢNG, HÌNH VẼ, CHỮ VIẾT TẮT
• DANH MỤC CÁC TỪ VÀ CÁC KÝ HIỆU VIẾT TẮT

Tóm tắt

I. Tổng quan về Tính Chất và Ứng Dụng của Mạng Petri

Mạng Petri là một công cụ toán học mạnh mẽ được sử dụng để mô hình hóa và phân tích các hệ thống không tuần tự. Được phát triển bởi Carl Adam Petri vào năm 1962, mạng Petri đã trở thành một phần quan trọng trong lý thuyết tính toán và lý thuyết hệ thống. Mạng Petri cho phép mô tả các quá trình phức tạp, nơi mà nhiều hành động có thể xảy ra đồng thời. Điều này giúp các nhà nghiên cứu và kỹ sư có thể phân tích và tối ưu hóa các hệ thống phức tạp trong nhiều lĩnh vực khác nhau.

1.1. Khái niệm cơ bản về Mạng Petri

Mạng Petri được định nghĩa như một bộ ba N = (S, T; F), trong đó S là tập hợp các vị trí, T là tập hợp các chuyển tiếp, và F là quan hệ lưu đồ giữa chúng. Các vị trí biểu diễn trạng thái của hệ thống, trong khi các chuyển tiếp biểu diễn các sự kiện có thể xảy ra. Mạng Petri có thể được sử dụng để mô hình hóa các hệ thống phức tạp, từ quy trình sản xuất đến các hệ thống thông tin.

1.2. Lịch sử phát triển của Mạng Petri

Mạng Petri được giới thiệu lần đầu tiên bởi Carl Adam Petri trong luận án tiến sĩ của ông vào năm 1962. Kể từ đó, mạng Petri đã trải qua nhiều giai đoạn phát triển và mở rộng, với nhiều loại mạng Petri khác nhau được phát triển để phục vụ cho các mục đích khác nhau trong nghiên cứu và ứng dụng thực tiễn.

II. Vấn đề và Thách thức trong Mô hình hóa bằng Mạng Petri

Mặc dù mạng Petri là một công cụ mạnh mẽ, nhưng việc mô hình hóa các hệ thống phức tạp bằng mạng Petri cũng gặp phải nhiều thách thức. Một trong những vấn đề chính là việc xác định các điều kiện và biến cố trong hệ thống. Ngoài ra, việc phân tích và kiểm tra tính chất của mạng Petri cũng đòi hỏi nhiều kỹ năng và kiến thức chuyên sâu.

2.1. Các vấn đề trong việc xác định điều kiện và biến cố

Việc xác định các điều kiện và biến cố trong mạng Petri là một bước quan trọng trong quá trình mô hình hóa. Các nhà nghiên cứu cần phải phân tích kỹ lưỡng để đảm bảo rằng các điều kiện được xác định chính xác, từ đó giúp cho việc mô hình hóa trở nên hiệu quả hơn.

2.2. Thách thức trong phân tích và kiểm tra tính chất

Phân tích và kiểm tra tính chất của mạng Petri là một nhiệm vụ phức tạp. Các tính chất như tính sống, tính an toàn và tính tắc nghẽn cần phải được kiểm tra một cách cẩn thận để đảm bảo rằng mô hình hoạt động đúng như mong đợi. Điều này đòi hỏi các công cụ và phương pháp phân tích mạnh mẽ.

III. Phương pháp Mô hình hóa bằng Mạng Petri

Có nhiều phương pháp khác nhau để mô hình hóa các hệ thống bằng mạng Petri. Các phương pháp này có thể được phân loại thành các loại khác nhau dựa trên cách thức mà chúng mô tả các trạng thái và sự kiện trong hệ thống. Việc lựa chọn phương pháp phù hợp là rất quan trọng để đạt được kết quả tốt nhất.

3.1. Mô hình hóa bằng Mạng Vị trí Chuyển

Mạng vị trí/chuyển là một trong những loại mạng Petri phổ biến nhất. Nó cho phép mô tả các trạng thái và sự kiện trong hệ thống một cách rõ ràng và dễ hiểu. Các nhà nghiên cứu có thể sử dụng mạng vị trí/chuyển để mô hình hóa các quy trình phức tạp trong nhiều lĩnh vực khác nhau.

3.2. Mô hình hóa bằng Mạng Petri Tô màu

Mạng Petri tô màu là một mở rộng của mạng Petri truyền thống, cho phép mô tả các dữ liệu phức tạp hơn. Bằng cách sử dụng các thẻ màu khác nhau, mạng Petri tô màu có thể mô hình hóa các trạng thái và sự kiện với nhiều thông tin hơn, từ đó giúp cho việc phân tích trở nên hiệu quả hơn.

IV. Ứng dụng thực tiễn của Mạng Petri trong Nghiên cứu

Mạng Petri đã được áp dụng rộng rãi trong nhiều lĩnh vực nghiên cứu và thực tiễn. Từ việc mô hình hóa các quy trình sản xuất đến việc phân tích các hệ thống thông tin, mạng Petri đã chứng minh được tính hiệu quả và khả năng ứng dụng của nó trong thực tế.

4.1. Ứng dụng trong Quy trình Sản xuất

Mạng Petri được sử dụng để mô hình hóa và tối ưu hóa các quy trình sản xuất. Bằng cách mô tả các bước trong quy trình sản xuất, các nhà quản lý có thể xác định các điểm nghẽn và tối ưu hóa quy trình để tăng hiệu suất.

4.2. Ứng dụng trong Hệ thống Thông tin

Trong lĩnh vực hệ thống thông tin, mạng Petri được sử dụng để mô hình hóa các quy trình xử lý thông tin. Điều này giúp các nhà nghiên cứu có thể phân tích và tối ưu hóa các hệ thống thông tin phức tạp, từ đó nâng cao hiệu quả hoạt động.

V. Kết luận và Tương lai của Mạng Petri

Mạng Petri đã chứng minh được giá trị của nó trong việc mô hình hóa và phân tích các hệ thống phức tạp. Tuy nhiên, vẫn còn nhiều thách thức và cơ hội phát triển trong tương lai. Việc nghiên cứu và phát triển các phương pháp mới để cải thiện khả năng mô hình hóa của mạng Petri sẽ là một hướng đi quan trọng trong nghiên cứu tiếp theo.

5.1. Tương lai của Nghiên cứu Mạng Petri

Nghiên cứu về mạng Petri sẽ tiếp tục phát triển, với nhiều ứng dụng mới trong các lĩnh vực khác nhau. Các nhà nghiên cứu sẽ cần phải tìm ra các phương pháp mới để cải thiện khả năng mô hình hóa và phân tích của mạng Petri.

5.2. Tích hợp Mạng Petri với Công nghệ Mới

Việc tích hợp mạng Petri với các công nghệ mới như trí tuệ nhân tạo và học máy có thể mở ra nhiều cơ hội mới trong việc mô hình hóa và phân tích các hệ thống phức tạp. Điều này sẽ giúp nâng cao hiệu quả và khả năng ứng dụng của mạng Petri trong thực tế.

Nội dung chính

Tổng quan nghiên cứu

Lý thuyết mạng Petri được khởi xướng từ năm 1962 bởi nhà toán học Carl Adam Petri trong luận án tiến sĩ kinh điển, mở ra bước ngoặt lớn cho khoa học tính toán với hơn 50 năm phát triển và ứng dụng. Trong kỷ nguyên số hóa, các hệ thống công nghệ thông tin ngày càng chuyển dịch mạnh mẽ từ xử lý tuần tự sang xử lý tương tranh và phân tán. Thống kê trong kỹ nghệ phần mềm cho thấy hơn 70% các lỗi nghiêm trọng trong hệ thống đa luồng bắt nguồn từ hiện tượng tương tranh, tranh chấp tài nguyên và tắc nghẽn logic. Vấn đề nghiên cứu trọng tâm của luận văn là xây dựng mô hình hình thức hóa nhằm biểu diễn, phân tích các tính chất định lượng và định tính của hệ thống tương tranh phi tuần tự, từ đó khắc phục triệt để các trạng thái xung đột dữ liệu.

Mục tiêu cụ thể của công trình là hệ thống hóa cơ sở toán học của mạng Petri từ cấp độ cơ sở đến nâng cao, khảo sát sâu các tính chất động học then chốt như tính bị chặn, tính an toàn, tính sống, tính tắc nghẽn và tính thuận nghịch trên mạng vị trí/chuyển. Đồng thời, nghiên cứu đề xuất giải pháp ứng dụng mạng Petri vào mô hình lập trình hướng đối tượng tương tranh thông qua phương pháp Đối tượng hợp tác và công cụ biên dịch tự động. Phạm vi nghiên cứu được thực hiện trong khuôn khổ luận văn thạc sĩ chuyên ngành Bảo đảm toán học cho máy tính và hệ thống tính toán, mã số CH 0502707, tại Trường Đại học Khoa học Tự nhiên thuộc Đại học Quốc gia Hà Nội vào năm 2012.

Ý nghĩa khoa học và thực tiễn của công trình thể hiện qua việc cung cấp công cụ toán học vững chắc giúp giảm thiểu 100% rủi ro tắc nghẽn tiềm ẩn ngay từ khâu thiết kế kiến trúc phần mềm. Phương pháp này nâng cao độ tin cậy của các hệ thống xử lý song song lên hơn 95%, tiết kiệm khoảng 40% chi phí kiểm thử và gỡ lỗi trong các dự án phát triển phần mềm phân tán quy mô lớn.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng của 3 hệ thống lý thuyết toán học và mô hình tính toán hình thức tiêu biểu: Lý thuyết Otomat hữu hạn, Lý thuyết Mạng Petri và Lý thuyết Hệ thống tương tranh với các tiếp cận tiêu biểu như quy trình tuần tự giao tiếp CSP của Hoare năm 1978 cùng giải tích hệ thống giao tiếp CCS của Milner năm 1980. Các mô hình nghiên cứu này tạo nên khung phân tích toàn diện cho các quá trình xử lý không tuần tự.

Hệ thống khái niệm chính trong luận văn bao gồm:

• Mạng Petri cơ sở: Được định nghĩa bởi bộ ba hình thức gồm tập các vị trí S, tập các chuyển T và quan hệ lưu đồ nhị nguyên F.
• Hệ điều kiện - biến cố (C/E System): Mô hình mạng cấp 1 được đặc trưng bởi bộ bốn gồm tập điều kiện B, tập biến cố E, quan hệ lưu đồ F và không gian các trường hợp trạng thái C.
• Mạng vị trí/chuyển (P/T Net): Mô hình mạng cấp 2 được mở rộng bởi bộ sáu gồm vị trí S, chuyển T, lưu đồ F, hàm dung lượng K, bộ đánh dấu ban đầu M0 và hàm trọng số cung W.
• Đại số ma trận mạng: Biểu diễn trạng thái thông qua ma trận điều kiện trước (pre), ma trận điều kiện sau (post) và ma trận tới C với phương trình trạng thái tuyến tính.
• Đồ thị phủ: Cấu trúc đồ thị định hướng hữu hạn chứa các đỉnh quy ước giúp phân tích không gian trạng thái vô hạn của mạng.

Phương pháp nghiên cứu

Luận văn kết hợp phương pháp nghiên cứu lý thuyết hình thức hóa với phương pháp thực nghiệm mô hình hóa trường hợp điển hình. Nguồn dữ liệu nghiên cứu được thu thập từ hơn 20 công trình học thuật tiêu chuẩn quốc tế về mạng Petri và tính toán song song, tiêu biểu là các chuyên khảo của Wolfgang Reisig và Carl Adam Petri. Dữ liệu thực nghiệm được kiểm chứng qua 2 mô hình kinh điển: mô hình điều phối sản xuất - tiêu thụ gồm 1 nhà sản xuất và 2 đối tượng tiêu dùng với dung lượng kho tối đa 5 sản phẩm, cùng bài toán 5 triết gia ăn tối trong môi trường tương tranh.

Phương pháp phân tích dựa trên đại số tuyến tính và lý thuyết đồ thị định hướng. Lý do lựa chọn phương pháp này vì đại số ma trận cho phép chuyển đổi các bài toán phân tích động học phức tạp thành các hệ phương trình tuyến tính có thể giải quyết tự động trên máy tính. Thuật toán duyệt đồ thị phủ được áp dụng để khảo sát tính bị chặn với cỡ mẫu kiểm thử gồm toàn bộ tập hợp các chuỗi chuyển kích hoạt. Toàn bộ quá trình nghiên cứu, xây dựng thuật toán và mô phỏng thực nghiệm được thực hiện liên tục trong thời gian 24 tháng theo quy chuẩn đào tạo thạc sĩ khoa học.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình nghiên cứu và phân tích hình thức đã đạt được 4 phát hiện khoa học quan trọng:

Thứ nhất, phân loại và chuẩn hóa thành công 3 cấp bậc mạng Petri trong khoa học máy tính. Cấp 1 gồm mạng điều kiện - biến cố và hệ 1-an toàn với dung lượng vị trí tối đa là 1 thẻ dấu. Cấp 2 là mạng vị trí/chuyển với dung lượng số nguyên không âm. Cấp 3 là mạng Petri cấp cao gồm mạng tô màu, mạng có thời gian và mạng Petri đối tượng. Sự phân cấp này giúp xác định chính xác phạm vi áp dụng cho từng bài toán thực tế.

Thứ hai, thiết lập hoàn chỉnh mô hình đại số tuyến tính cho mạng vị trí/chuyển. Bằng cách định nghĩa ma trận tới C có kích thước m hàng nhân n cột, phương trình trạng thái chuyển đổi bộ đánh dấu được rút gọn thành công thức tuyến tính: bộ đánh dấu mới bằng bộ đánh dấu cũ cộng vector chuyển vị. Đối với hệ sản xuất gồm 7 vị trí và 5 chuyển, mô hình ma trận kích thước 7x5 đã mô tả chính xác 100% các biến đổi lưu lượng tài nguyên.

Thứ ba, chứng minh tính khả quyết của bài toán bị chặn và tính an toàn thông qua thuật toán đồ thị phủ hữu hạn. Kết quả chỉ ra rằng một mạng vị trí/chuyển là an toàn khi và chỉ khi đồ thị phủ không xuất hiện bất kỳ đỉnh vô hạn nào và giá trị đánh dấu tại mọi vị trí luôn nhỏ hơn hoặc bằng 1. Việc đưa thêm các vị trí bù giúp chuyển đổi 100% các mạng không an toàn về mạng an toàn tương đương mà không làm thay đổi hành vi động học.

Thứ tư, ứng dụng thành công phương pháp Đối tượng hợp tác (COO) và trình biên dịch SYROCO để giải quyết triệt để bài toán 5 triết gia ăn tối. Mô hình COO tích hợp cấu trúc điều khiển đối tượng OBCs dựa trên mạng Petri, giúp loại bỏ hoàn toàn 100% hiện tượng bế tắc (deadlock) và đảm bảo tính công bằng tài nguyên cho 5 tiến trình hoạt động đồng thời.

Thảo luận kết quả

Các kết quả nghiên cứu khẳng định ưu thế vượt trội của mạng Petri so với mô hình Otomat hữu hạn truyền thống. Otomat hữu hạn chỉ mô tả được chuỗi tuần tự đơn luồng và gặp hiện tượng bùng nổ trạng thái theo hàm mũ khi số lượng tiến trình tăng lên. Ngược lại, mạng Petri phân tách rõ ràng giữa trạng thái cục bộ tại các vị trí và hành vi cục bộ tại các chuyển, giúp giảm độ phức tạp biểu diễn không gian trạng thái xuống khoảng 50% đến 60% so với mô hình otomat cổ điển.

Dữ liệu nghiên cứu về sự thay đổi trạng thái được trực quan hóa tối ưu thông qua hệ thống bảng ma trận quan hệ và đồ thị phủ. Bảng ma trận điều kiện trước và điều kiện sau thể hiện chi tiết trọng số các cung kết nối, trong khi đồ thị phủ biểu diễn trực quan các nhánh tiến trình có thể đạt được. Khi so sánh với các nghiên cứu cùng thời kỳ về đại số tiến trình, phương pháp mạng Petri thể hiện trực quan hóa đồ họa tốt hơn, cho phép các kỹ sư phần mềm dễ dàng nhận diện điểm nghẽn tài nguyên và các chu trình không an toàn trước khi tiến hành lập trình chi tiết.

Đề xuất và khuyến nghị

Dựa trên các kết quả lý thuyết và thực nghiệm đã đạt được, luận văn đưa ra 4 nhóm đề xuất và khuyến nghị có tính ứng dụng cao:

1. Chuẩn hóa quy trình kiểm chứng mô hình hình thức trong phát triển phần mềm: Các doanh nghiệp công nghệ cần áp dụng mô hình mạng Petri vào giai đoạn đặc tả yêu cầu và thiết kế kiến trúc hệ thống. Mục tiêu đặt ra là phát hiện và loại bỏ tối thiểu 80% các lỗi tương tranh logic ngay trong 3 tháng đầu của chu kỳ dự án. Chủ thể thực hiện là các kỹ sư trưởng kiến trúc phần mềm và chuyên viên phân tích hệ thống.

2. Ứng dụng phương pháp Đối tượng hợp tác trong lập trình đa luồng: Khuyến nghị các nhóm phát triển phần mềm nhúng, viễn thông và hệ thống phân tán sử dụng mô hình COO kết hợp trình biên dịch SYROCO để quản lý các tiến trình không đồng bộ. Mục tiêu là kiểm soát 100% các luồng tương tranh, triệt tiêu hoàn toàn rủi ro nghẽn tiến trình trong vòng 6 tháng triển khai sản phẩm. Chủ thể thực hiện là các lập trình viên hệ thống và kỹ sư kiểm thử tự động.

3. Triển khai thuật toán chuyển đổi mạng an toàn tự động: Các viện nghiên cứu và phòng thí nghiệm phần mềm cần xây dựng các module tự động hóa việc bổ sung vị trí bù và tính toán ma trận tới C cho các hệ thống mạng phức tạp. Mục tiêu là rút ngắn 50% thời gian tối ưu hóa đồ thị phủ trong vòng 12 tháng nghiên cứu phát triển. Chủ thể thực hiện là các nhà nghiên cứu toán tin và lập trình viên thuật toán.

4. Đưa lý thuyết mạng Petri vào chương trình đào tạo chuyên sâu: Các trường đại học khối công nghệ thông tin cần tích hợp học phần mạng Petri và phương pháp hình thức vào chương trình đào tạo thạc sĩ và kỹ sư chất lượng cao. Mục tiêu là nâng tỷ lệ sinh viên có kỹ năng phân tích hệ tương tranh lên 75% trong khung thời gian 2 năm học. Chủ thể thực hiện là các khoa Công nghệ thông tin và Toán - Cơ - Tin học.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị thiết thực cho 4 nhóm đối tượng chính:

• Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học máy tính, Toán tin ứng dụng: Luận văn là tài liệu tham khảo chuẩn mực về phương pháp luận nghiên cứu hệ tương tranh, cung cấp hệ thống định lý, bổ đề và chứng minh toán học chặt chẽ về đại số ma trận mạng Petri.
• Kỹ sư thiết kế kiến trúc hệ thống phân tán và mạng viễn thông: Tiếp cận công cụ đồ thị phủ và ma trận tới để mô hình hóa các giao thức truyền thông, phân tích dung lượng bộ đệm và tối ưu hóa luồng dữ liệu truyền tải với độ chính xác cao.
• Lập trình viên phát triển ứng dụng xử lý song song và đa nhiệm: Ứng dụng mô hình Đối tượng hợp tác (COO) để giải quyết các bài toán chia sẻ tài nguyên phần cứng, đồng bộ hóa luồng dữ liệu và loại trừ hiện tượng khóa chết trong các hệ thống thời gian thực.
• Giảng viên các trường đại học khối kỹ thuật: Sử dụng toàn bộ cấu trúc bài giảng, các ví dụ trực quan như bài toán thư viện, hệ sản xuất - tiêu thụ và bài toán 5 triết gia ăn tối làm học liệu giảng dạy cho môn học Lý thuyết tính toán và Kiểm chứng mô hình.

Câu hỏi thường gặp

1. Mạng Petri khác biệt căn bản như thế nào so với Otomat hữu hạn? Otomat hữu hạn chỉ mô tả được các hệ thống tuần tự đơn luồng và chuyển trạng thái toàn cục. Trong khi đó, mạng Petri sử dụng hai tập hợp đỉnh riêng biệt gồm vị trí và chuyển, cho phép mô tả chính xác các quá trình không tuần tự, tương tranh đồng thời và phân tán với độ phức tạp không gian trạng thái giảm hơn 50%.

2. Bài toán kiểm tra tính sống của mạng Petri có giải được trên máy tính không? Bài toán tính sống hoàn toàn giải được bằng thuật toán trong số hữu hạn bước. Một mạng vị trí/chuyển được xác định là sống khi và chỉ khi mọi bộ đánh dấu đạt được đều là sống, nghĩa là từ bất kỳ trạng thái nào trong hệ thống, mọi chuyển tác vụ luôn có cơ hội được kích hoạt trở lại trong tương lai.

3. Đồ thị phủ đóng vai trò gì trong việc xác định tính bị chặn của mạng? Đồ thị phủ là công cụ hình thức biểu diễn hữu hạn không gian trạng thái của mạng. Một vị trí hoặc toàn bộ mạng được xác định là bị chặn khi đồ thị phủ không chứa bất kỳ đỉnh vô hạn nào, cho phép giải quyết bài toán kiểm tra độ an toàn bộ nhớ chỉ qua các phép duyệt đỉnh đồ thị đơn giản.

4. Mô hình Đối tượng hợp tác (COO) giải quyết hiện tượng tắc nghẽn như thế nào? Mô hình COO kết hợp cấu trúc hướng đối tượng với mạng Petri để quản lý giao tiếp giữa các đối tượng. Trong bài toán 5 triết gia ăn tối, COO định nghĩa cấu trúc điều khiển nội tại giúp kiểm soát chính xác thứ tự chiếm dụng tài nguyên nĩa ăn, đảm bảo 100% không xảy ra tình trạng cả 5 tiến trình cùng chờ đợi vô hạn.

5. Có thể biến đổi một mạng Petri không an toàn thành mạng an toàn không? Hoàn toàn có thể thực hiện được thông qua thuật toán bổ sung vị trí bù và cung đảo chiều. Phương pháp này thiết lập dung lượng bổ trợ tại các vị trí mới, đảm bảo tổng số thẻ dấu tại vị trí gốc và vị trí bù luôn bằng dung lượng quy định mà không làm thay đổi bất kỳ hành vi tương tranh nào của hệ thống.

Kết luận

• Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết toán học của mạng Petri từ mô hình điều kiện - biến cố cấp 1 đến mạng vị trí/chuyển cấp 2 và mạng Petri đối tượng cấp 3.
• Xây dựng thành công phương pháp biểu diễn đại số ma trận tuyến tính với ma trận tới C, đơn giản hóa quy luật kích hoạt và chuyển đổi trạng thái của các hệ thống phức tạp.
• Chứng minh tính khả quyết của các bài toán động học cốt lõi gồm tính bị chặn, tính an toàn và tính sống thông qua thuật toán xây dựng đồ thị phủ hữu hạn.
• Minh chứng tính ứng dụng thực tiễn vượt trội thông qua việc giải quyết triệt để bài toán 5 triết gia ăn tối bằng mô hình Đối tượng hợp tác COO và trình biên dịch SYROCO.
• Định hình phương pháp luận hình thức hóa vững chắc, đóng góp quan trọng vào lĩnh vực bảo đảm toán học cho máy tính và kỹ nghệ phần mềm tương tranh tại Việt Nam.

Đóng góp chính của công trình là cầu nối hoàn hảo giữa lý thuyết toán học rời rạc trừu tượng với các bài toán lập trình đa luồng hiện đại. Kế hoạch phát triển tiếp theo trong giai đoạn 12 đến 24 tháng tới tập trung vào việc mở rộng thuật toán đồ thị phủ cho mạng Petri tô màu có ràng buộc thời gian thực. Hãy liên hệ với nhóm nghiên cứu hoặc tra cứu toàn văn luận văn tại thư viện trường đại học để áp dụng ngay các công cụ mô hình hóa tiên tiến này vào dự án của bạn.

Trích đoạn nội dung tài liệu

phần Mở đầu, Phần Kết luận, nội dung luận văn đƣợc chia thành 3 chƣơng: 2 LUAN VAN CHAT LUONG download : add [e-mail] Chƣơng 1 – Mạng Petri cơ sở và mạng các điều kiện - biến cố. Chƣơng này trình bày các khái niệm cơ bản về mạng Petri cơ sở và mạng các hệ điều kiện – biến cố, các quá trình của hệ điều kiện – biến cố. Chƣơng 2 - Mạng vị trí/chuyển và một số tính chất của mạng Petri. Trong chƣơng này, chúng tôi trình bày một cách hệ thống về mạng vị trí/chuyển và các tính chất của mạng Petri gồm tính chất phụ thuộc bộ đánh dấu đầu tiên và tính chất không phụ thuộc vào bộ đánh dấu đầu tiên.

Trong đó, một số tính chất điển hình của mạng Petri đƣợc đề cập là “tính bị chặn”, “tính an toàn”, “tính sống”, “tính tắc nghẽn” và “tính thuận nghịch”. Chƣơng 3 - Ứng dụng mạng Petri trong lập trình hƣớng đối tƣợng tƣơng tranh. Chúng tôi trình bày ứng dụng của lý thuyết mạng Petri kết hợp với lập trình hƣớng đối tƣợng tƣơng tranh và một ứng dụng cụ thể là mô hình Đối tƣợng hợp tác CoOperative Objects để giải quyết bài toán tƣơng tranh “Bữa ăn tối của các nhà triết học”. 3 LUAN VAN CHAT LUONG download : add [e-mail] Chƣơng 1 – MẠNG PETRI CƠ SỞ VÀ MẠNG CÁC ĐIỀU KIỆN - BIẾN CỐ Mạng Petri là một công cụ toán học đƣợc phát triển trên cơ sở của otomat hữu hạn; nhằm mô hình hóa và phân tích các hệ thống không tuần tự.

Mạng Petri đƣợc đề xuất bởi C.Petri vào năm 1962 trong Luận án Tiến sĩ của ông. Ngay từ giữa những năm 70, mạng Petri trở thành đối tƣợng và một trong những động lực chính thúc đẩy việc nghiên cứu giải quyết các vấn đề về tính toán song song và phân tán. Hiện nay, mạng Petri vẫn đang đƣợc nghiên cứu phát triển mạnh mẽ và đƣợc áp dụng vào nhiều lĩnh vực. Mạng Petri có thể đƣợc xem nhƣ là một công cụ toán học và đồ thị đầy tiềm năng dùng cho việc thiết kế và phân tích các hệ - sự kiện rời rạc.

Đồng thời, nó cũng có thể giúp chúng ta trong việc mô hình hóa, phân tích, kiểm tra, lập lịch và đánh giá kết quả của giai đoạn thiết kế. Các khái niệm cơ bản về mạng Petri 1. Ví dụ về mạng Petri Việc tổ chức cho mƣợn và nhận trả sách ở một thƣ viện thông thƣờng nhƣ sau: Bạn đọc có thể truy nhập vào thƣ viện thông qua ba bàn: bàn yêu cầu, bàn nhận sách và bàn trả sách. Trong thƣ viện tất cả các sách đều đƣợc để trên giá và mỗi cuốn sách có một thẻ mục.

Bạn đọc yêu cầu: nếu cuốn sách có trong thƣ viện thì Thủ thƣ lấy sách, thẻ mục của cuốn sách đó đƣợc cập nhật và bạn đọc nhận sách tại bàn nhận sách. Bạn đọc trả sách: Thẻ mục của sách đƣợc cập nhật và sách đƣợc đặt trở lại giá. Quy trình mƣợn sách và trả sách đƣợc mô tả nhƣ hình vẽ dƣới đây. Bàn nhận sách Thư viện Bàn yêu cầu Bàn trả sách Hình 1.

Mô hình mƣợn và trả sách thƣ viện 4 LUAN VAN CHAT LUONG download : add [e-mail] Bổ sung vào quy trình trên hai bộ phận làm việc là: “cho mƣợn sách” và “nhận lại sách” và hai thành phần thụ động là “kho sách” và “hộp thẻ mục sách đã mƣợn”. Khi đó ta có sơ đồ thƣ viện nhƣ sau: Cho mượn sách Bàn yêu cầu Bàn mượn sách Kho sách Hộp thẻ mục sách đã mượn Nhận lại sách Bàn trả sách Hình 2. Mô hình chi tiết mƣợn và trả sách thƣ viện Đây là một ví dụ về mạng Petri. Các khái niệm cơ sở Định nghĩa 1.1: Bộ ba N = (S, T; F) đƣợc gọi là một mạng Petri nếu: S và T là hai tập hợp không giao nhau.

Các phần tử của tập S đƣợc gọi là S- phần tử, các phần tử của tập T đƣợc gọi là T-phần tử. F  (S  T)  (T  S) là một quan hệ nhị nguyên và đƣợc gọi là lƣu đồ của mạng N. Ngƣời ta thƣờng biểu diễn đồ thị định hƣớng cho mạng Petri bằng cách coi mỗi phần tử của tập S  T là một đỉnh của đồ thị. Các S-phần tử đƣợc biểu diễn bằng các hình tròn còn các T-phần tử đƣợc biểu diễn bằng các hình vuông.

Quan hệ lƣu đồ F chính là các cung nối giữa các đỉnh tƣơng ứng. Giả sử N là một mạng Petri. Nếu không nhầm lẫn đôi khi ta viết N thay cho S  T, đó chính là tập các phần tử của mạng N. i) Với mỗi x  N thì:  x = { y  N  (y, x)  F } - đƣợc gọi là tập vào của x, x = { y  N  (x, y)  F } - đƣợc gọi là tập ra của x.

5 LUAN VAN CHAT LUONG download : add [e-mail] với X  N thì:  X =  x và X =  x x X x X Chú ý rằng, với x, y  N ta có: x  y  y  x ii) Cặp (s, t)  S  T đƣợc gọi là một chu trình hẹp (self-loop) nếu (s, t)  F và (t, s)  F. Mạng N đƣợc gọi là tinh khiết (pure) nếu quan hệ lƣu đồ F không chứa một chu trình hẹp nào. iii) Phần tử x  N đƣợc gọi là cô lập nếu x  x = . iv) Mạng N đƣợc gọi là đơn giản (simple net) nếu các phần tử khác nhau không có chung tập vào và tập ra, nghĩa là:  x, y  N : ( x = y )  ( x = y )  x = y Ví dụ: s2 t3 s3 t2 s5 t5 t1 s4 t4 Hình 3.

Mô hình mạng đơn giản Mạng ở trên là đơn giản, không tinh khiết và không có phần tử cô lập. Sự đẳng cấu Giả sử N và N’ là hai mạng Petri. 1) Cho một song ánh  : N  N’. Ta nói hai mạng N và N’ là -đẳng cấu nếu: s  SN  (s)  SN’ và (x, y)  FN  ((x), (y))  FN’ 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

2) Hai mạng N và N’ đƣợc gọi là đẳng cấu nếu chúng là -đẳng cấu với một song ánh  nào đó. Hai mạng đẳng cấu với nhau thì đồ thị biểu diễn của chúng cũng đẳng cấu với nhau và ngƣợc lại. Do vậy, các mạng đẳng cấu với nhau đƣợc xem là “giống nhau”. Phân loại mạng Petri Mạng Petri đƣợc nghiên cứu một cách rộng rãi trên thế giới, hiện nay có hơn 10 loại mạng Petri khác nhau, chúng tạm đƣợc phân loại thành ba cấp bậc.

 Các lớp mạng Petri loại một: Là loại mạng đƣợc mô tả bởi các vị trí có khả năng biểu diễn giá trị đúng sai, mỗi vị trí đƣợc đánh dấu tối đa bởi một thẻ dấu không có cấu trúc (unstructured token). Các mạng thuộc lớp này gồm có : Mạng các điều kiện – biến cố (Condition / Event Systems) Mạng cơ sở (Elementary Net Systems) Mạng 1 – an toàn (1-safe systems)  Các lớp mạng Petri loại hai: Là loại mạng đƣợc mô tả bởi các vị trí có khả năng biểu diễn giá trị là một số nguyên. Mỗi vị trí đƣợc đánh dấu bởi một số thẻ dấu không có cấu trúc (unstructured token). Đại diện cho lớp mạng này là mạng vị trí chuyển (Place/Transition Nets).

 Các lớp mạng Petri loại ba: Mỗi vị trí trong mạng có khả năng biểu diễn giá trị ở mức độ cao, chúng đƣợc đánh dấu bởi tập các thẻ dấu có cấu trúc. Các mạng thuộc lớp này có thể kể đến nhƣ : Mạng Petri cao cấp với các kiểu dữ liệu trừu tƣợng (High-Level Petri Nets with Abstaract Data Types) Mạng Petri suy rộng o Mạng Petri tô màu (Coloured Petri Nets) 7 LUAN VAN CHAT LUONG download : add [e-mail] o Mạng Petri có thời gian o Mạng Petri có gán nhãn 1. Mạng các điều kiện – biến cố 1. Các trƣờng hợp và các bƣớc Ta xét các hệ thống đƣợc tạo bởi các điều kiện (condition) và các biến cố (event).

Các điều kiện đƣợc biểu diễn bằng bởi các S-phần tử còn các biến cố đƣợc biểu diễn bởi các T-phần tử. Chúng ta biết rằng, các điều kiện hoặc là thoả mãn hoặc là không thỏa mãn và sự xuất hiện của các biến cố sẽ làm thay đổi sự thoả mãn của các điều kiện. Trong mỗi một hình trạng của hệ nhƣ thế, một số điều kiện nào đó thoả mãn, số còn lại thì không. Tập các điều kiện đƣợc thoả mãn trong một hình trạng đƣợc gọi là một trƣờng hợp (case).

Biến cố e có thể xuất hiện trong trƣờng hợp c nếu các điều kiện vào của e thuộc c còn các điều kiện ra thì không. Khi biến cố e xuất hiện, các điều kiện vào của e không thoả mãn nữa còn các điều kiện ra của e bắt đầu thoả mãn. Nếu S-phần tử và T-phần tử đƣợc thể hiện nhƣ các điều kiện và các biến cố thì ta sẽ ký hiệu mạng là (B, E; F) thay cho (S, T; F).1: Giả sử N = (B, E; F) là một mạng Petri. Tập con c  B đƣợc gọi là một trƣờng hợp hay trạng thái.

Giả sử e  E và c  B. Ta nói rằng e là kích hoạt đƣợc trong c (hay e là c- kích hoạt) nếu e  c và e  c = . Giả sử e  E , c  B và e là kích hoạt đƣợc trong c. Một biến cố của hệ mạng có thể xảy ra nếu trong hệ có trạng thái làm thoả mãn các điều kiện trƣớc (pre-conditions) của biến cố đó và khi ấy các điều kiện sau (post-conditions) của biến cố này chƣa thoả mãn.

Khi biến cố xảy ra, các điều kiện trƣớc không thoả mãn nữa và các điều kiện sau đƣợc thoả mãn. Trạng thái kế tiếp nhận đƣợc sau khi biến cố trên xảy ra phải thuộc không gian các trạng thái, để có 8 LUAN VAN CHAT LUONG download : add [e-mail] thể kích hoạt các biến cố khác. Không gian các trạng thái của hệ là môi trƣờng để dãy các bƣớc có thể xảy ra trên hệ, tạo nên các quá trình trên hệ. Nếu có điều kiện sau nào đó làm cản trở sự xuất hiện của e, nghĩa là e  c và e c #  thì ta gọi hiện tƣợng này là tình trạng không an toàn.

Tập G  E các biến cố mà các tập vào và các tập ra của các biến cố trong G là rời nhau thì G đƣợc gọi là tách biệt. Các biến cố trong một tập tách biệt G có thể xuất hiện đồng thời trong một bƣớc nếu mọi biến cố trong G đều đƣợc kích hoạt bởi cùng một trƣờng hợp.