Mô hình biểu diễn tương tranh

Chia sẻ: Nguyen Van Cuong | Ngày: | Loại File: PDF | Số trang:124

Thêm vào BST

Báo xấu

161
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu tài liệu giúp người học nắm bắt được các khái niệm mới, kỹ thuật cơ bản và ứng dụng chúng vào các vấn đề thực tiễn như: hệ thống thông tin, cơ sở dữ liệu, thiết kế mạch lôgic,kiến trúc máy tính,lập trình song song, công nghệ phần mềm, điều khiển hệ thống... Cũng tham khảo để nắm bắt nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mô hình biểu diễn tương tranh

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN HOÀNG CHÍ THÀNH CÁC MÔ HÌNH TƯƠNG TRANH Hà Nội
MỞ ĐẦU Mô tả, thiết kế và điều khiển hệ thống là các vấn đề chính cần đặt ra khi chúng ta xây dựng một hệ thống nào đó và sử dụng nó trong thực tiễn. Lý thuyết mạng là lý thuyết tổ chức hệ thống được C.A. Petri khởi xướng vào đầu thập niên sáu mươi của thế kỷ trước trong Luận án Tiến sĩ của ông. Từ đó đến nay các nhà tin học trên thế giới đã nghiên cứu phát triển nhiều mô hình mạng khác nhau và ứng dụng chúng vào nhiều lĩnh vực khoa học khác nhau. Ưu điểm chính của lý thuyết mạng là khả năng nhận biết và biểu diễn sự tương tranh, an toàn, xung đột, sống, tắc nghẽn ..., cung cấp kỹ thuật phân tích và thiết kế hệ thống và cảnh báo sự hữu hạn của các tài nguyên của hệ thống. Bên cạnh lý thuyết mạng nhiều mô hình biểu diễn tương tranh khác đã ra đời. Một số mô hình dựa trên ngôn ngữ hình thức như: ngôn ngữ vết của A. Mazurkiewicz, ngôn ngữ CSP của C.A.R. Hoare, ngôn ngữ CCS của R. Milner, ngôn ngữ COSY của P. Lauer, ngôn ngữ nửa vết của H.C. Thành ... Công cụ đại số cũng được sử dụng để biểu diễn tương tranh. Từ đó ra đời: đại số các quá trình của V.E. Kotov và của J.A. Bergstra, cấu trúc biến cố của G. Winskel ... Do khuôn khổ của chuyên đề, chúng tôi chỉ chọn lựa một số mô hình tiêu biểu nhất để đưa vào các bài giảng với mục tiêu giúp người học nắm bắt được các khái niệm mới, kỹ thuật cơ bản và ứng dụng chúng vào các vấn đề thực tiễn như: hệ thống thông tin, cơ sở dữ liệu, thiết kế mạch lôgic, kiến trúc máy tính, lập trình song song, công nghệ phần mềm, điều khiển hệ thống... Cuốn sách là nội dung chuyên đề dành cho học viên cao học và nghiên cứu sinh chuyên ngành Tin học, Công nghệ Thông tin, Đảm bảo Toán học cho Máy tính và Các hệ thống tính toán... mà tác giả đã giảng dạy nhiều năm tại ĐHQG Hà Nội và một số trường đại học khác. Nhiều thảo luận lý thú giữa tác giả với đồng nghiệp và học viên đã góp phần phát triển nội dung và nâng cao chất lượng của cuốn sách. Chúng tôi hy vọng rằng cuốn sách nhỏ này sẽ thật sự cần thiết cho những ai muốn nghiên cứu, khám phá những vấn đề kỳ diệu và hóc búa trong các hệ thống tương tranh. Tác giả 2
Chương 1 HỆ TƯƠNG TRANH VÀ CÁC MÔ HÌNH BIỂU DIỄN 1.1 Khái niệm về tương tranh Trong đời sống hàng ngày, chúng ta thường thấy các sự kiện mà các hành động trong nó xảy ra một cách tuần tự hoặc không tuần tự. Tương ứng với các sự kiện trên ta có các quá trình và chúng cũng được phân thành hai loại: các quá trình tuần tự và các quá trình không tuần tự. Một số quá trình được kết hợp lại với nhau tạo thành một hệ thống. Hệ thống tuần tự được tạo bởi các quá trình tuần tự. Các quá trình không tuần tự tạo nên hệ thống không tuần tự. Trong một hệ thống tuần tự tại mỗi thời điểm chỉ có một hành động xuất hiện (được thực hiện). Hành động sau xảy ra khi hành động trước đó đã kết thúc. Chúng chỉ có thể kế thừa kết quả của nhau. Chẳng hạn: - Khách xếp hàng mua hàng khi chỉ có một nhân viên bán hàng - Các thuật toán tính toán tuần tự - Các otomat hữu hạn… Còn trong hệ thống không tuần tự, tại một thời điểm có thể xảy ra đồng thời nhiều hành động. Các hành động này có thể cạnh tranh lẫn nhau trong việc sử dụng tài nguyên. Trước khi đưa ra định nghĩa hệ tương tranh chúng ta xét một số ví dụ cụ thể sau đây. Ví dụ 1.1: Quá trình sản xuất công nghiệp Giả sử một thiết bị nào đó được tạo ra từ việc chế tạo và lắp ráp ba chi tiết. Việc chế tạo từng chi tiết không phụ thuộc vào nhau. Việc lắp ráp thì thực hiện tuần tự: trước tiên lắp ráp hai chi tiết đầu sau đó lắp thêm chi tiết thứ ba. Hình 1.1. Quy trình tổ chức chế tạo và lắp ráp song song một thiết bị 3
Ta có thể đưa quá trình sản xuất thiết bị trên về một hệ thống tương tranh như sau: chế tạo đồng thời hai chi tiết 1 và 2, việc lắp ráp hai chi tiết 1 và 2 đồng thời với việc chế tạo chi tiết thứ ba, cuối cùng lắp ráp thêm chi tiết 3. Như vậy, trong hệ thống sản xuất này việc chế tạo chi tiết 1 và việc chế tạo chi tiết 2 là tương tranh với nhau. Chúng chỉ có thể được thực hiện đồng thời nếu không tranh chấp các máy móc... Quá trình sản xuất một sản phẩm có thể biểu diễn ngắn gọn bằng sơ đồ sau: 1⁪2;3⁪4;5 Với việc tổ chức sản xuất như trên, ta thấy ngay các lợi ích sau đây: 1) Các chi tiết kỹ thuật được chế tạo trên các máy khác nhau, việc chế tạo đồng thời có thể xoá bỏ thời gian chết của các máy. 2) Giảm thời gian chế tạo ra một sản phẩm. Ví dụ 1.2: Tính giá trị của một biểu thức toán học Giả sử ta cần phải tính giá trị của biểu thức sau đây: A * B - (C + D) / (E - F) Hình 1.2. Tổ chức tính toán song song một biểu thức Sơ đồ tính toán giá trị biểu thức như trên giống như sơ đồ quá trình sản xuất trong Ví dụ 1.1. Nếu máy tính có ít nhất hai bộ xử lý thì quá trình tính giá trị biểu thức sẽ nhanh hơn nhiều. Ví dụ 1.3: Chu trình xử lý Xét chu trình tính toán được viết trên ngôn ngữ lập trình Pascal sau đây: for i := 1 to 100 do if A[i] > 0 then A[i] := A[i] + 1 else A[i] := 0 ; 4
100 lệnh if trên có thể được thực hiện đồng thời nếu máy tính có trên 100 bộ xử lý. Tuy nhiên, không phải chu trình nào cũng có thể thực hiện đồng thời được. Chẳng hạn, xét chu trình sau đây: S := 0 ; for i := 1 to 100 do S := S + A[i] ; Đây là các lệnh lặp phụ thuộc. Trong trường hợp này có nhiều cách giải quyết. Chẳng hạn, ta tính toán đồng thời theo sơ đồ sau đây: Hình 1.3. Một sơ đồ tính toán song song Ví dụ 1.4: Tương tranh trong máy tính Tương tranh trong máy tính được thể hiện ở các máy tính có nhiều bộ xử lý (multi-processor). Đó là các máy tính có thể xử lý đồng thời nhiều quá trình tại cùng một thời điểm. Hình 1.4. Sơ đồ máy tính song song Với kỹ thuật này nảy sinh các vấn đề sau đây mà ta cần phải giải quyết: 5
- Sự chung sống của các bộ xử lý thuộc nhiều chủng loại khác nhau - Số lượng tối đa của các bộ xử lý trong một máy tính - Phần mềm để tự động hoá các quá trình tương tranh trên máy tính nhiều bộ xử lý… 1.2 Định nghĩa hệ tương tranh Một hệ thống được gọi là hệ tương tranh (concurrent system) nếu nó được hợp thành từ một số hệ con (tuần tự) và có các biến cố được xảy ra một cách đồng thời. Hệ tương tranh là đồng bộ nếu các hệ con của nó có chung một số biến cố và trong quá trình hoạt động của hệ chúng xuất hiện trùng hợp trong tất cả các hệ con có chung các biến cố này. Điều này chỉ ra rằng, mỗi biến cố chung xuất hiện ở bước nào đó thì nó phải có khả năng xuất hiện ở bước đó trong tất cả các hệ con có chung biến cố này. Số lần xuất hiện và thứ tự xuất hiện của biến cố chung trong các hệ con phải giống nhau. 1.3 Sơ lược về các mô hình biểu diễn tương tranh 1) Mô hình đầu tiên để biểu diễn hệ tương tranh được đề xuất bởi C.A. Petri (Đức) vào năm 1962 trong Luận án Tiến sĩ của ông. Đó là mạng Petri. Nếu otomat hữu hạn chỉ mô tả được các hệ thống tuần tự thì mạng Petri, 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, mô tả được các hệ thống không tuần tự mà trong đó có các hệ thống tương tranh. Hiện nay mạng Petri vẫn được nghiên cứu phát triển mạnh mẽ cả về lý thuyết lẫn ứng dụng [5,7,10,11]. Đã có hơn mười loại mạng khác nhau và được áp dụng vào rất nhiều lĩnh vực. 2. Ngôn ngữ vết (trace language) do A. Mazurkiewicz (Ba Lan) đưa ra vào năm 1977. Đây là một ngôn ngữ được phát triển từ ngôn ngữ hình thức để mô tả hành vi của các hệ tương tranh [1]. 3. CSP (Communicating Sequential Processes) là một ngôn ngữ để biểu diễn các hệ tương tranh [3] do C.A.R. Hoare (Anh) đưa ra vào năm 1978. 4. CCS (Calculus of Communicating Systems) được R. Milner (Anh) xây dựng vào năm 1980 như một công cụ toán học rõ ràng và tổng quát về tương tranh và được thể hiện như một ngôn ngữ lập trình [4]. Ngoài những mô hình kể trên, các hệ tương tranh còn được mô tả bằng các mô hình sau đây: - Đại số các quá trình (Algebra of Processes) của J.A. Bergstra (Hà Lan) 6
- COSY (COncurent SYstem) do P. Lauer (Canada) đề xuất - Cấu trúc biến cố (Event Structure) của G. Winskel (Đức), và nhiều mô hình khác. Một số nhóm nghiên cứu các hệ tương tranh trên thế giới: Hệ tương tranh được nhiều nhà khoa học trên thế giới nghiên cứu và phát triển tại các trường đại học và các viện nghiên cứu. - Tại Đại học Bonn (Đức), nơi ra đời của mạng Petri, có một nhóm các nhà khoa học có tên tuổi như: C.A. Petri, E. Best, W. Reisig, W. Brauer, U. Goltz… phát triển nhiều mô hình khác nhau của mạng Petri. - Đại học Aarhus (Đan Mạch) xây dựng các mô hình mạng Petri màu và ứng dụng trong thiết kế. - Đại học Amsterdam (Hà Lan) với tên tuổi của G. Rozenberg và J.W. de Baker chủ trì dự án REX (Research and Education in Concurrent Systems) - Đại học Oxfort (Anh) là nơi C.A.R. Hoare và R. Milner xây dựng trường phái mô hình các hệ tương tranh bằng ngôn ngữ trừu tượng. - Trường phái dùng monoid của đại số để phát triển lý thuyết tương tranh được nghiên cứu tại Đại học Milan (Italia) với tên tuổi các nhà khoa học như: U. Montarari, F. de Cindio, C. Simone… - A. Mazurkiewicz và J. Winkowski chủ trì nhóm nghiên cứu tương tranh tại Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học Ba Lan. - Đại học Tổng hợp Novosibierk (Nga) có một nhóm các nhà khoa học trẻ nghiên cứu về tương tranh bằng các công cụ đại số như: V.E. Kotov, L. Cherkasova… - P.S. Thiagarajan đã xây dựng một nhóm nghiên cứu mạnh về tương tranh tại Viện Toán học Chennai (Ấn độ). - Dự án châu Âu ESPRIT có trụ sở tại Đại học Newcastle (Anh) dưới sự điều hành của R.P. Hopkin với 44 nhà khoa học tham gia trực tiếp trong 10 nhóm làm việc (WG) sau đây: 1. WG.1: Các lớp modul mạng 2. WG.2: Mô phỏng tương đương 3. WG.3: Các kỹ thuật chứng minh 4. WG.4-5: Các mô hình trừu tượng 5. WG.6: Các nghiên cứu thời sự 6. WG.7: Đặc tả 7
7. WG.8: Lập trình 8. WG.9-10: Công bố kết quả Hội thảo khoa học hàng năm toàn thế giới về tương tranh (CONCUR) được tổ chức tại nhiều trung tâm nghiên cứu trên khắp các châu lục đã thu hút sự chú ý của nhiều người về Lý thuyết Tương tranh. Nhiều kết quả nghiên cứu lý thuyết và ứng dụng của hệ tương tranh đã được trình bày tại hội thảo này. 8
Chương 2 MẠNG PETRI 2.1 Ví dụ về mạng Petri Chúng ta nghiên cứu việc tổ chức cho mượn sách và nhận trả lại sách ở một thư viện. Hình 2.1. Cấu trúc đơn giản của một thư viện Đây là cấu trúc đơn giản của một thư viện. 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. a) 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) 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á. Làm mịn sơ đồ thư viện trên bằng cách thêm vào 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ơ đồ mới chi tiết hơn của một thư viện như dưới đây: Hình 2.2. Sơ đồ tổ chức đầy đủ của một thư viện 9
Đây là một ví dụ về mạng Petri. 2.2 Các khái niệm cơ sở 2.2.1 Mạng Petri Định nghĩa 2.1: Bộ ba N = (S, T; F) được gọi là một mạng Petri nếu: 1) 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òn các phần tử của tập T được gọi là T-phần tử. 2) 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. Mỗi cung của quan hệ lưu đồ F chỉ nối hai đỉnh khác loại. Do vậy, đồ thị biểu diễn một mạng Petri là một đồ thị định hướng hai phần. 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 phần tử 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. với mỗi tập con X  N thì:  X =  x và X =  x x X x X Chú ý rằng, với cặp phần tử x, y  N ta có: x  y  y  x ii) Cặp (s, t)  S  T được gọi là một nút (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 nút 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) nếu và chỉ 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. 10
Ví dụ 2.2: Xét mạng Petri được cho dưới dạng đồ thị dưới đây. Hình 2.3. Biểu diễn đồ thị của một mạng Petri Mạng ở ví dụ trên là đơn giản, không tinh khiết và không có phần tử cô lập. 2.2.2 Các mạng Petri đẳ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 và chỉ nếu: s  SN  (s)  SN’ và (x, y)  FN  ((x), (y))  FN’ Điều này cũng suy ra rằng: t  TN  (t)  TN’. 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 đó. Hiển nhiên, 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”. 11
Chương 3 HỆ MẠNG ĐIỀU KIỆN - BIẾN CỐ 3.1 Các trường hợp và các bước Chúng ta xét 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ở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ử của một mạng Petri. Ta biết rằng, các điều kiện hoặc là thoả mãn hoặc là không 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ệ, 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 và chỉ nếu các điều kiện vào của e thoả mãn trong 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. Vì các 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ố nên ta ký hiệu mạng Petri là (B, E; F) thay cho (S, T; F). Định nghĩa 3.1: Giả sử N = (B, E; F) là một mạng Petri. 1) Tập con c  B được gọi là một trường hợp hay một trạng thái. 2) 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 và chỉ nếu e  c và e  c = . 3) Giả sử e  E , c  B và e là kích hoạt được trong c. Khi đó, c' = (c \ e)  e được gọi là trường hợp kế tiếp của c (c’ là kết quả của sự xuất hiện của biến cố e trong trường hợp c). Và ta viết: c [ e > 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 (tập vào) của biến cố đó và khi ấy các điều kiện sau (tập ra) 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ó thể kích hoạt các biến cố khác. Không gian các trạng thái của hệ thống 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 biến cố e, nghĩa là e  c nhưng e  c ≠  thì ta gọi hiện tượng này là tình trạng không an toàn.  Tập con các biến cố G  E 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 được (detached). Các biến cố trong 12
một tập tách được 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. Định nghĩa 3.2: Giả sử N = (B, E; F) là một mạng Petri. 1) Tập con các biến cố G  E được gọi là tách được nếu: e1, e2  G : e1 ≠ e2  e1  e2 = e1  e2 = e1  e2 = e1  e2 = . 2) Giả sử c và c' là các trường hợp của mạng N và tập con các biến cố G là tách được. G được gọi là một bước từ c tới c' nếu và chỉ nếu mỗi biến cố e trong G là c-kích hoạt và c' = (c \ G)  G. Khi đó, ta cũng ký hiệu là: c [ G > c'. Bước G đã dẫn từ trường hợp c tới trường hợp c'. Hiển nhiên, nếu G chỉ chứa một biến cố e thì: c [ G > c'  c [ e > c'. Bổ đề 3.1: Giả sử N = (B, E; F) là một mạng Petri, tập con các biến cố G  E là tách được và c, c' là các trường hợp của N. Khi đó thì: c [ G > c'  c \ c' = G  c' \ c = G. Chứng minh: 1) Nếu c [ G > c' thì mọi e  G là c-kích hoạt và c' = (c \ G)  G. Từ đó suy ra: G  c và G  c' = . Hơn nữa: c \ c' = c \ ((c \ G)  G) = (c \ (c \ G))  (c \ G) – theo lý thuyết tập hợp = (c  G)  (c \ G) = c  G vì c \ G = c = G vì G  c. c' \ c = ((c \ G)  G) \ c = ((c \ G) \ c)  (G \ c) =   (G \ c) = G vì G  c = . 2) Ngược lại, nếu c \ c' = G thì G  c. Đồng thời, nếu c' \ c = G thì G  c = . Vậy mỗi biến cố e trong G là c-kích hoạt. Hơn nữa: (c \ G)  G = (c \ (c \ c'))  (c' \ c) = (c  c')  (c' \ c) = c'. Vậy thì: c [ G > c'. Bổ đề được chứng minh. 13
Nói chung có một số khả năng để ghép các biến cố thành một bước. Ví dụ 3.3: Xét hệ mạng Petri được cho như đồ thị dưới đây. Chọn trường hợp đầu tiên c0 = {b1}. Hình 3.1. Các bước trên mạng Không chỉ {e1,e2} mà {e2,e3} cũng tạo nên một bước. Khi thay thế các trường hợp, bước tiếp theo bước sinh ra các quá trình. Nếu bước hữu hạn thì nó có thể được thể hiện bởi sự xuất hiện của các biến cố của nó theo thứ tự tuỳ ý. Do vậy, các biến cố trong một bước hữu hạn có thể thực hiện đồng thời với nhau. Bổ đề 3.2: Giả sử N = (B, E; F) là một mạng Petri, c1, c2 là các trường hợp của mạng N và G là một bước hữu hạn dẫn c tới c'. Giả sử G = {e1, e2, … , ek} và < e1, e2, … , ek> là một dãy nào đó của các biến cố trong G. Vậy thì có các trường hợp c0, c1, … , ck mà c = c0, c' = ck và ci-1[ ei > ci với i = 1, 2, …, k. Chứng minh: Giả sử ei, ej là hai biến cố nào đó trong G và c là trường hợp kích hoạt được hai biến cố này. Thế thì: ei  ej = ei  ej = ei  ej = ei  ej = . Khi đó nếu c [ ei > c' thì ej  c'. Tương tự có thể chỉ ra rằng ej  c' = . Điều này có nghĩa là ej kích hoat được trong c'. Với i = 1, 2, …, k ta có ei vẫn bảo toàn tính kích hoạt được khi xuất hiện lần lượt của e1, e2, … , ei-1 và dẫn ci-1 tới ci. Có thể xảy ra trường hợp là hai biến cố đều được một trường hợp kích hoạt nhưng chỉ có thể xuất hiện trong các bước đơn thôi. Đó là trường hợp mà hai biến cố này có chung điều kiện vào hoặc điều kiện ra. Khi đó sự xuất hiện của chúng loại trừ lẫn nhau. Tình trạng như thế được gọi là xung đột lẫn nhau (conflict). Không phải lúc nào cũng có thể nhận biết một cách rõ ràng rằng xung đột có xảy ra hay không. 14
Ví dụ 3.4: Xét mạng Petri sau đây. Hình 3.2. Tình trạng xung đột Trong mạng trên với trường hợp được chỉ ra (các điều kiện tô màu) nếu e1 xuất hiện trước e2 thì không có xung đột giữa e1 và e3, còn nếu e2 xuất hiện trước e1 thì xảy ra xung đột. Do không có thứ tự xác định trước giữa e1 và e2 nên tình trạng này được gọi là mập mờ. 3.2 Hệ mạng điều kiện - biến cố Một mạng Petri bao gồm các điều kiện và các biến cố chưa đủ để mô tả hệ thống. Vì vậy ngoài mạng ta phải thêm vào các trường hợp mà ta muốn xét. Tập các trường hợp C này phải thoả các tính chất sau đây: 1. Nếu tập G  E là một bước được kích hoạt bởi trường hợp c  C thì G dẫn tới một trường hợp khác cũng thuộc C. Như vậy, các bước không được dẫn ra ngoài C. 2. Ngược lại, nếu trường hợp c  C là kết quả của bước G  E thì tình huống mà ta đi từ đó cũng phải là một trường hợp thuộc C. Hay nói một cách khác, nếu ta quay trở lại tìm trường hợp trước thì ta chỉ cần tìm trong C. 3. Mỗi trường hợp trong C đều có thể biến đổi (tiến hoặc lùi sau một số lần) thành các trường hợp còn lại trong C. 4. C phải đủ rộng để mà: - Mỗi điều kiện b  B phải thuộc vào ít nhất một trường hợp trong C nhưng không thuộc vào mọi trường hợp trong C. Điều này giúp loại trừ điều kiện cô lập và chu trình hẹp. - Mỗi biến cố e  E phải có ít nhất một trường hợp trong C kích hoạt được nó. Ta cũng loại trừ các biến cố cô lập vì sự xuất hiện của các biến cố phải quan sát được. Hơn nữa, ta cũng không cho phép hai điều kiện hay hai biến cố khác nhau có chung tập vào và tập ra vì không phân biệt được chúng. 15
Định nghĩa 3.5: Bộ bốn  = (B, E; F, c0) được gọi là một hệ mạng điều kiện - biến cố (C/E-system) nếu: 1) Bộ ba (B, E; F) là một mạng Petri đơn giản, không có phần tử cô lập và B  E ≠ . 2) c0  B, là trường hợp đầu tiên của hệ mạng . Tập C = [c0]R là một lớp tương đương của quan hệ đạt được R = (r  r-1)*, trong đó quan hệ r  P(B)  P(B) được định nghĩa như sau: (c1, c2)  r  G  E : c1 [ G > c2. C được gọi là không gian các trường hợp của hệ . 3) e  E , c  C để e kích hoạt được trong c. Ví dụ 3.6: Cho mạng Petri: Hình 3.3. Cấu trúc tĩnh của một hệ mạng điều kiện - biến cố Lấy c0 = {b1}. Khi đó không gian C = {{b1}, {b2, b3}, {b3, b4}, {b4}, {b5}} và ta có một hệ mạng điều kiện - biến cố. Định lý 3.3: Giả sử  là một hệ mạng điều kiện - biến cố. Thế thì: 1) B ≠   E ≠   F ≠ . 2) Với c  C , c'  B và G  E : - c [ G > c'  c'  C - c' [ G > c  c  C 3) b  B , c, c'  C mà b  c  b  c'. 4) Hệ  là tinh khiết. Chứng minh: 1) Vì B  E ≠  và các phần tử cô lập đã bị loại trừ nên phải có các phần tử x, y của  sao cho (x, y)  F. 2) Suy từ định nghĩa của hệ mạng điều kiện - biến cố. 16
3) Vì b không cô lập nên có biến cố e trong b  b và theo định nghiã thì phải có c, c'  C mà c [ e > c' và vì b  c  c'. 4) Biến cố trong chu trình hẹp không bao giờ được kích hoạt. Ví dụ 3.7: Bài toán sắp đặt lại các tập hợp. Cho hai tập không rỗng, hữu hạn, rời nhau A và B. Sắp đặt lại các phần tử trong tập A  B thành hai tập A' và B' sao cho |A'| = |A|, |B'| = |B| và max (A) < min (B). Chương trình tương tranh giải bài toán trên được biểu diễn bởi hệ mạng điều kiện - biến cố sau đây: Hình 3.4. Chương trình tương tranh cho bài toán sắp đặt lại các tập hợp Định lý 3.4: Giả sử  là một hệ mạng điều kiện - biến cố. Giả sử quan hệ r  P(B)  P(B) được định nghĩa như sau: (c1, c2)  r  e  E : c1 [ e > c2. Nếu tập các biến cố E hữu hạn thì R = ( r  r -1)*. Chứng minh: Vì R = ( r  r -1)* nên hiển nhiên ta có: R  R . Tập E hữu hạn nên mỗi bước trong E cũng hữu hạn. Do vậy, ta có r  r * và r-1  ( r -1)*. Từ đây suy ra: R  R . 17
Giả sử  = (B, E; F, c0) là một hệ mạng điều kiện - biến cố. Các trường hợp trong không gian các trường hợp kích hoạt liên tiếp các biến cố cho ta một dãy hành động xảy ra trên hệ. Chẳng hạn, c1 [e1 > c2 [e2 > c3 [e3 > c4 ... ci [ei > ci+1 ... cn [en > cn+1 , với c1, c2, ... cn+1  C và e1, e2, ... en  E. Khi đó,  = e1e2 ... en được gọi là từ sinh bởi hệ mạng . Ngôn ngữ sinh bởi hệ mạng điều kiện - biến cố , ký hiệu bởi L(), là tập tất cả các từ sinh bởi hệ mạng này. L() = { = e1e2 ... en |  c1, c2, ... cn+1  C ,  e1, e2, ... en  E : c1 [e1 > c2 [e2 > c3 [e3 > c4 ... ci [ei > ci+1 ... cn [en > cn+1}. Ngôn ngữ này thể hiện hành vi tuần tự của hệ mạng. Nó chỉ cho ta tất cả các dãy các hành động có thể xảy ra tuần tự trên hệ. 3.3 Hệ chu trình và hệ sống Những yêu cầu đặt ra cho không gian các trường hợp C của hệ mạng điều kiện - biến cố  sẽ rõ ràng hơn bằng cách thể hiện được rằng C là tập tất cả các trường hợp kế tiếp của một trường hợp ban đầu nào đó. Nếu mọi trường hợp của  đều được tái sản xuất thì mỗi một không gian các trường hợp như thế sẽ trùng với tập C. Định nghĩa 3.8: Hệ mạng điều kiện - biến cố  được gọi là chu trình nếu và chỉ nếu: c1, c2  C : (c1, c2)  r*. Định lý 3.5: Giả sử  là một hệ mạng điều kiện - biến cố chu trình và c là một trường hợp nào đó trong không gian C. Thế thì: C = {c'  (c, c')  r*} . Chứng minh: Vì hệ  là chu trình nên r-1  r . Suy ra R  r*. Trong một hệ chu trình mỗi một biến cố luôn luôn được xuất hiện trở lại. Định nghĩa 3.9: Hệ mạng điều kiện - biến cố  được gọi là sống nếu và chỉ nếu: c  C , e  E : c'  C để cho (c, c')  r* và e là c'-kích hoạt. 18
Định lý 3.6: Mọi hệ mạng điều kiện - biến cố chu trình là sống. Chứng minh: Giả sử c  C và e  E. Theo định nghĩa của hệ mạng điều kiện - biến cố phải có trường hợp c' trong C để nó kích hoạt được e. Theo tính chu trình thì (c, c')  r*. Điều ngược lại thì không phải khi nào cũng đúng. Ta hãy xét phản ví dụ sau đây. Ví dụ 3.10: Hệ mạng điều kiện - biến cố sống nhưng không là chu trình. Hình 3.5. Hệ sống nhưng không là chu trình 3.4 Các hệ mạng điều kện - biến cố tương đương Ta nói rằng hai hệ mạng điều kiện - biến cố đã cho là tương đương nếu các trường hợp và các bước của chúng tương ứng với nhau theo cách sau đây. Định nghĩa 3.11: Giả sử  và ' là hai hệ mạng điều kiện - biến cố. 1) Giả sử có hai song ánh  : C  C’ và  : E  E’ . - Hai hệ  và ' được gọi là (,)-tương đương nếu và chỉ nếu: c1, c2  C , G  E : c1 [ G > c2  (c1) [ (G) > (c2). - Hai hệ  và ' được gọi là tương đương nếu và chỉ nếu chúng là (,)- tương đương đối với cặp song ánh (,) nào đó và ta ký hiệu:   '. 2) Hai hệ  và ' được gọi là đẳng cấu nếu và chỉ nếu hai mạng (B , E , F) và (B', E' , F’) là -đẳng cấu với song ánh  nào đó và: c  C  {(b)  b  c}  C’ . Định lý 3.7: Sự đẳng cấu mạnh hơn sự tương đương. Quan hệ  là một quan hệ tương đương. 19
Định lý 3.8: Các hệ mạng điều kiện - biến cố tương đương có số các trường hợp, số các biến cố và số các bước như nhau nhưng số các điều kiện của chúng có thể khác nhau. Ví dụ 3.12: Hai hệ mạng điều kiện - biến cố tương đương biểu diễn các mùa trong năm. Hình 3.6. Hai hệ mạng điều kiện - biến cố tương đương Tập các điều kiện B' : s1 – xuân hoặc hạ s2 – xuân hoặc thu s3 – hạ hoặc thu. Tập các trường hợp C' : {s1, s2} = xuân , {s1, s3} = hạ , {s2, s3} = thu ,  = đông. Định lý 3.9: Giả sử  và ' là hai hệ mạng điều kiện - biến cố tương đương. 1. Hệ  là chu trình  hệ ' là chu trình. 2. Hệ  là sống  hệ ' là sống. Hệ mạng điều kiện - biến cố tuần tự với các trường hợp bao gồm chỉ một điều kiện tương ứng với các otomat hữu hạn. Với hai hệ như thế sự tương đương trùng với sự đẳng cấu. Bổ đề 3.10: Giả sử  và ' là hai hệ mạng điều kiện - biến cố mà: c  C  C’, |c| = 1. Khi đó thì:   ' khi và chỉ khi chúng là đẳng cấu. Chứng minh: Giả sử  là (,)-tương đương với '. Vì mỗi trường hợp của chúng chỉ chứa đúng một điều kiện nên mỗi điều kiện b tạo nên trường hợp {b}. Song ánh  : C  C’ sinh ra song ánh ' : B  B’ như sau: 20