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

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.
Nội dung trích xuất từ tài liệu:
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ÀNHCÁC MÔ HÌNHTƯƠ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 khichú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ếtmạng là lý thuyết tổ chức hệ thống được C.A. Petri khởi xướng vào đầu thậpniên sáu mươi của thế kỷ trước trong Luận án Tiến sĩ của ông. Từ đó đến naycá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ácnhau và ứng dụng chúng vào nhiều lĩnh vực khoa học khác nhau. Ưu điểm chínhcủ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ụ đạisố 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êubiể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 đượccá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ễnnhư: 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êncứu sinh chuyên ngành Tin học, Công nghệ Thông tin, Đảm bảo Toán học choMá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ácgiả với đồng nghiệp và học viên đã góp phần phát triển nội dung và nâng caochấ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ữngai 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ỄN1.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ácsự 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ạonê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 độngtrướ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 đồngthời nhiều hành động. Các hành động này có thể cạnh tranh lẫn nhau trong việcsử 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 chitiế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ựchiệ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ị 3Ta 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ờivớ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ờinế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: 12;34;5Vớ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: ...