Đề Tài :Mô phỏng hàng đợi bằng GPSS

Chia sẻ: Nguyen Quang Ha | Ngày: | Loại File: DOC | Số trang:63

Thêm vào BST

Báo xấu

122
lượt xem 33
download

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

Hiện nay, hàng đợi được ứng dụng khá rộng rãi trong thực tế. Một bài toán trong thực tế đặt ra là phải tính, hay dự đoán được khả năng đáp ứng của một hệ thống với một hàng đợi cụ thể được áp dụng. Về mặt lý thuyết, đã có nhiều nghiên cứu về các mô hình hàng đợi này, cũng như các công thức để tính toán. Song một nhược điểm mà cách tính toán theo lý thuyết mắc phải là phức tạp và gặp rất nhiều khó khăn trong việc áp dụng tính toán vào thực tế. Các mô hình lý thuyết mới...

Chủ đề:

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

Lưu

Nội dung Text: Đề Tài :Mô phỏng hàng đợi bằng GPSS

BỘ GIAO DUC VÀ ĐAO TAO ́ ̣ ̀ ̣ TRƯỜNG ĐẠI HỌC KHOA HỌC KHOA CÔNG NGHỆ THÔNG TIN  BÀI BÁO CÁO THỰC TẬP CHUYÊN NGÀNH CUỐI KHÓA Đề Tài :Mô phỏng hàng đợi bằng GPSS (General Purpose Simulation System) Giảng viên hướng dẫn : Đặng Thanh Chương Sinh viên thực hiện : Nguyễn Quang Hà
MỤC LỤC CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI..................................................................................4 I. Đặt vấn đề...................................................................................................................4 II. Mục tiêu đề tài............................................................................................................4 III. Giới hạn đề tài..........................................................................................................4 CHƯƠNG 2: LÝ THUYẾT CHUNG VỀ HÀNG ĐỢI.....................................................6 II. Các khái niệm cơ bản................................................................................................ 6 1. Định nghĩa về hàng đợi:..........................................................................................6 2. Các tham số đặc trưng của hàng đợi. ....................................................................7 3. Mô tả trạng thái cho hệ thống hàng đợi:............................................................... 7 4. Các thông số hiệu năng thường dùng trong mô hình mạng hàng đợi:..................8 III. Một số hàng đợi cơ bản........................................................................................... 8 1. Hàng đợi Markov M/M/1........................................................................................ 8 2. Hàng đợi Markov M/M/n...................................................................................... 10 3. Hàng đợi có Markov M/M/n/n.............................................................................. 11 I. Giới thiệu GPSS........................................................................................................ 16 II. Các thực thể GPSS ( GPSS Entities ).......................................................................17 1. Thực thể Transaction............................................................................................ 18 2. Các thực thể Block ( Block Entities )................................................................... 20 3. Các thực thể Facility ( Facility Entities )..............................................................21 4. Thực thể Function ( Function Entities )................................................................22 5. Các thực thể Logicswitch ( Logicswitch Entities )...............................................23 6. Các thực thể Matrix ( Matrix Entities )................................................................23 7. Các thực thể Queue ( Queue Entities )..................................................................23 8. Các thực thể Storage ( Storage Entities )..............................................................24 9. Các thực thể Savevalue ( Savevalue Entities )......................................................25 10. Các thực thể Table ( Table Entities ).................................................................. 25 11. Các thực thể Userchain ( Userchain Entities )....................................................25 12. Các thực thể Variable ( Variable Entities ).........................................................25 III. Các câu lệnh GPSS..................................................................................................25 1. Câu lệnh START ..................................................................................................27 2. Câu lệnh STORAGE ............................................................................................28 IV. Các câu lệnh Block ( Block Statements )...............................................................29 1. Block GENERATE................................................................................................32 2. Block ADVANCE................................................................................................. 33 3. Block QUEUE ...................................................................................................... 34 4. Block DEPART..................................................................................................... 35 5. Block ENTER........................................................................................................ 35 6. Block LEAVE........................................................................................................36 7. Block SEIZE ......................................................................................................... 37 8. Block RELEASE .................................................................................................. 38 9. Block TERMINATE .............................................................................................39 10. Block TEST ........................................................................................................ 40 V. Câu lệnh sử dụng phân bố xác suất........................................................................ 41 - - 2
VI. Báo cáo tiêu chuẩn.................................................................................................. 42 1. Quản lý báo cáo ( Report Management ).............................................................. 42 2. Báo cáo mẫu..........................................................................................................43 Mô hình chung........................................................................................................... 43 Báo cáo.......................................................................................................................43 CHƯƠNG 4: MÔ PHỎNG HÀNG ĐỢI......................................................................... 50 1. Hàng đợi M/M/1 theo lý thuyết............................................................................ 50 2. Mô phỏng hàng đợi M/M/1...................................................................................50 II. Mô phỏng hàng đợi M/M/n...................................................................................... 54 2. Mô phỏng hàng đợi M/M/4 ..................................................................................54 III. Mô phỏng hàng đợi M/M/n/n .................................................................................57 1.Lý thuyết hàng đợi M/M/n/n .................................................................................57 2. Mô phỏng hàng đợi M/M/4/4 ..............................................................................58 Kết luận............................................................................................................................ 62 Tài liệu tham khảo............................................................................................................63 - - 3
CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI I. Đặt vấn đề. Hiện nay, hàng đ ợi đ ược ứng d ụng khá r ộng rãi trong th ực t ế. M ột bài toán trong th ực tế đặt ra là ph ải tính, hay d ự đoán đ ược kh ả năng đáp ứng c ủa m ột h ệ thống với một hàng đợi c ụ th ể đ ược áp d ụng. V ề m ặt lý thuy ết, đã có nhi ều nghiên c ứu về các mô hình hàng đ ợi này, cũng nh ư các công th ức đ ể tính toán. Song m ột nhược đi ểm mà cách tính toán theo lý thuy ết m ắc ph ải là ph ức t ạp và gặp rất nhiều khó khăn trong vi ệc áp d ụng tính toán vào th ực t ế. Các mô hình lý thuyết m ới ch ỉ đáp ứng đ ược các mô hình hàng đ ợi ở d ạng đ ơn gi ản, trong khi các hàng đợi trên th ực t ế ho ạt đ ộng khá ph ức t ạp. Do có, m ột nhu c ầu phát sinh là phải có m ột công c ụ ph ục v ụ cho vi ệc mô ph ỏng cũng nh ư tính toán trên các mô hình hàng đợi. Từ đó, đ ề tài đ ược th ực hi ện nh ằm cung c ấp m ột cung công cụ giúp gi ải quyết bài toán trên cũng nh ư ph ục v ụ cho m ục đích nghiên c ứu h ọc tập về các mô hình hàng đ ợi. II. Mục tiêu đề tài. Mục tiêu của đề tài là nghiên cứu các mô hình hàng đợi. Đồng thời, bước đầu xây dựng mô phỏng về các mô hình hàng đợi đơn giản. Trong đó, các mô phỏng phải giải quyết được vấn đề cốt yếu là có khả năng mô phỏng các trường hợp trong hệ thống hàng đợi mà nếu tính toán lý thuyết là quá phức tạp. Hệ thống hàng đợi được nghiên cứu chỉ dừng lại ở mô hình M/M/n/n. Để thực hiện mục tiêu đề ra, đề tài đã thực hiện thông qua hai bước, bước một là nghiên cứu lý thuyết hàng đ ợ i và ch ươ ng trình mô ph ỏ ng GPSS, bước hai là áp dụng các lý thuyết đó để xây dựng mô phỏng. Tương ứng, bản báo cáo cũng được trình bày theo trình tự trên với: • Chương 1 trình bày sơ bộ về dề tài. • Chương 2 trình bày về các lý thuyết mô hình hàng đợi • Chương 3 trình bày về chương trình mô phỏng GPSS • Chương 4 trình bày về quá trình mô phỏng và các kết quả đạt được III. Giới hạn đề tài. Nội dung nghiên cứu chỉ dừng lại ở mô hình hàng đợi kinh điển, gặp nhiều trong thực tế là M/M system (M/M/n/N/K) – Markov-Markov system. Trong đó: • Quá trình đến là quá trình Poisson (xét theo Xi ~ P(λ)), có nghĩa là khoảng thời gian đến được phân phối theo hàm mũ với mật độ λ. • Thời gian phục vụ (holding time, service time): tuân theo phân phối hàm số mũ với mật độ μ. • Quá trình đến là độc lập với các quá trình phục vụ và ngược lại. • n: số server phục vụ. • K : dung lượng của hệ thống hay tổng khả năng phục vụ của hệ thống. Bao gồm số Server và số buffer. K ≥ n. • N: số khách hàng. - - 4
• Các khách hàng luôn “kiên nhẫn”, không có hiện tượng hủy yêu cầu từ phía khách hàng khi chưa được phục vụ xong. • Không xãy ra quá trình “cố gắng thử lại” hay “yêu cầu lại” của các khách hàng. • Trong M/M system, buffer (hay queue) được thực hiện ở dạng FIFO (First in fisrt out). Tuy nhiên, hoàn toàn có thể thay thế bằng một dạng khác. Do vấn đề này không thuộc phạm vi đề tài, nên chỉ có một dạng được áp dụng chung cho tất cả các mô phỏng là FIFO. Mô phỏng được xây dựng bằng GPSS World Student (phiên bản 5.2.2) trên hệ đi ề u hành Window. Các mô phỏng chỉ mới dừng lại ở việc mô phỏng một mô hình đơn, chưa hình thành việc liên kết các hệ thống với nhau. - - 5
CHƯƠNG 2: LÝ THUYẾT CHUNG VỀ HÀNG ĐỢI I. Giới thiệu Lý thuyết hàng đợi (Queueing theory) là một chuyên ngành của xác suất. Những bài báo đầu tiên viết về nó cách đây khoản vài chục năm nhưng ứng dụng của nó mang lại là rất lớn trong công nghệ thông tin, kinh tế… Lý thuyết hàng đợi, nghiên cứu quá trình phục vụ. Nó nghiên cứu những đặc trưng và xác định các tính chất của hệ thống được thiết lập bởi các yêu cầu của khách hàng. Những yêu cầu, thời gian phục vụ là những đại lượng ngẫu nhiên. Những hệ như vậy thường là những mô hình của các hệ thống thực tế, ví dụ: mạng điện thoại, mạng máy tính, hệ thống tính toán,… Thành phận quan trọng của một hệ thống phục vụ: + Luồng các yêu cầu vào. + Máy phục vụ. + Phương pháp phục vụ. + Hàng đợi. + Luồng các yêu cầu ra. II. Các khái niệm cơ bản. 1. Định nghĩa về hàng đợi: • Hàng đợi là hệ thống bao gồm các thành phần : khách hàng vào/ra hệ thống (input/output), hệ thống phục vụ (server), hàng đợi(queue). • Khách hàng vào hệ thống được đưa vào hàng đợi, đến lượt thì được phục vụ ở server, sau khi được phục vụ xong thì ra khỏi hệ thống. Khi dùng hàng đợi ta hiểu là toàn bộ hệ thống xếp hàng bao gồm các yêu cầu đợi phục vụ và các yêu cầu đang được phục vụ . Ví dụ: Các hệ thống điện thoại: khi số lượng lớn khách hàng quay số để kết nối đến một trong những đường ra hữu hạn của tổng đài. Trong mạng máy tính: khi mà gói tin được chuyển từ nguồn tới đích và đi qua một số lượng các nút trung gian. Hệ thống hàng đợi xuất hiện tại mỗi nút ở quá trình lưu tạm thông tin tại bộ đệm. Hệ thống máy tính: khi các công việc tính toán và tuyến làm việc của hệ thống yêu cầu dịch vụ từ bộ xử lý trung tâm và từ các nguồn khác. Những tình huống này được diễn tả bằng hình vẽ sau: - - 6
Hàng đợi Sự ki ện đến Server Sự kiện đi Hình 2- 1: Mô hình chung của hệ thống hàng đợi 2. Các tham số đặc trưng của hàng đợi. - Tính chất của dòng khách hàng đến hàng đợi hay phân bố xác suất khoảng thời gian giữa các yêu cầu hàng đợi. - Phân bố xác suất khoảng thời gian dịch vụ cho mỗi yêu cầu trong hàng đợi. - Số các server tại hàng đợi. - Dung lượng bộ đệm hay dung lượng lưu trữ tại hàng đợi. - Tổng số các yêu cầu hiện đang có mặt tại hàng đợi. - Các kiểu dịch vụ. Theo kí pháp của Kendall một hệ thống hàng đợi được phân loại qua các kí hiệu của bộ mô tả kendall tổng quát có dạng A/B/m/K/n/D • A: phân bố xác suất của khoảng thời gian yêu cầu để phục vụ các khách hàng trong hệ thống hàng đợi. • B: phân phối xác suất trong khoảng thời gian yêu cầu để phục vụ các khách hàng trong hệ thống hàng đợi. • m: số lượng server • K: kích thước bộ đệm hoặc dung lượng lưu trữ tại hệ thống xếp hàng. • n : số lượng khách hàng được phép chuyển qua hệ thống. • D: phương thức phục vụ. 3. Mô tả trạng thái cho hệ thống hàng đợi: • Trạng thái của một hệ thống hàng đợi là một véc tơ biểu diễn số khách hàng trong mỗi hàng đợi của hệ thống tại mỗi thời điểm cụ thể. Trạng thái hệ thống hàng đợi cho phép mô tả hàng đợi một cách đầy đủ ở thời điểm bất kì mà không cần biết thêm các đại lượng khác như thời gian phục vụ, thời gian giữa hai lần đến liên tiếp • Đối với hệ thống xếp hàng ta thường dùng mô hình thống kê Markov để tính toán , để mô tả trạng thái hệ thống ta tính Pn(t) là xác suất để hệ thống có véc tơ trạng thái n tại thời điểm t. - - 7
4. Các thông số hiệu năng thường dùng trong mô hình mạng hàng đợi: Một Server µ Sự đi S ự đến với tốc Số vị trí trong hàng đ ợi độ trung bình λ là vô hạn Hình 2- 2: Hệ thống hàng đợi đơn giản Đối với một hệ thống hàng đợi, cần tìm cách để đánh giá được các chỉ số sau: - Tốc độ lưu lượng đến (Arrival rate): tốc độ luồng lưu lượng đến hay số khách hàng đến trung bình trong một khoảng thời gian, ký hiệu λ. - Tốc độ phục vụ (Service rate): tốc độ phục vụ hay số khách hàng trung bình được phục vụ trên một đơn vị thời gian, ký hiệu µ. - Số lượng trung bình của khách hàng trong hệ thống E[N] . - Số lượng trung bình của khách hàng trong hàng đợi E[N Q ] . - Thời gian trung bình trong hệ thống E[W] : bao gồm 2 khoảng thời gian: thời gian đợi và thời gian phục vụ. Tính toán các tham số hiệu năng này đòi hỏi những giả thiết thêm dựa trên đặc tính của hệ thống hàng đợi, như: quy tắc phục vụ khách hang (giả sử là FCFS), phân bố trạng thái ổn định Pk , k = 0,1,... (cũng giống như phân bố xác suất của số lượng khách hàng trong hệ thống). - Thời gian trung bình trong hàng đợi (thời gian đợi để được phục vụ) E[WQ ] : bằng thời gian trung bình hệ thống trừ đi thời gian phục vụ. - Xác suất tắc nghẽn PB: Xác suất hệ thống bận hay còn gọi là hệ số sử dụng của toàn hệ thống (Utilization factor). Lưu ý: Các cách tiếp cận đã trình bày được sử dụng để phân tích bất kỳ một hệ thống hàng đợi đều phải có các giả thiết sau: Quá trình đến là quá trình Poisson, có nghĩa là khoảng thời gian đến được phân bố theo hàm mũ. - Quá trình đến với tốc độ đến thay đổi. - Hệ thống có một hoặc nhiều server. - Thời gian phục vụ có dạng phân bố hàm mũ. - Quá trình đến là độc lập với các quá trình phục vụ và ngược lại. - Có hữu hạn (hoặc vô hạn) các vị trí đợi hữu hạn trong hệ thống. Tất cả các giả thiết tạo thành lớp đơn giản nhất của hệ thống hàng đợi. III. Một số hàng đợi cơ bản 1. Hàng đợi Markov M/M/1. Là hàng đợi có quá trình đến Poisson với tốc độ λ , thời gian phục vụ có phân phối mũ tốc độ phục vụ µ với 1 server phục vụ và trạng thái hệ thống (kích thước bộ - - 8
đệm) không giới hạn. Hình 2-3: Mô hình hàng đợi M/M/1 Lược đồ trạng thái λ λ λ λ λ λ 0 1 2 ... i-1 i i+1 µ µ µ µ µ µ Hình 2-4: Chuỗi Markov của hàng đợi M/M/1 Các công thức sau đây đã được chứng minh bằng phương pháp giải tích. • Số lượng trung bình khách hàng trong hệ thống: ρ λ E[N ] = với ρ = 1− ρ µ • Số lượng trung bình khách hàng đợi, có nghĩa là chiều dài hàng đợi trung bình: ρ ρ2 E[ N Q ] = −ρ = 1− ρ 1− ρ • Thời gian đợi trung bình trong hệ thống là: 1 E[W ] = µ (1 − ρ ) • Thời gian đợi trung bình trong hàng đợi là: 1 ρ E[WQ ] = E[W ] − = µ µ (1 − ρ ) • Số lượng server được sử dụng (Server utilization): λ U s = 1 − P0 = = ρ µ - - 9
2. Hàng đợi Markov M/M/n. Là hàng đợi có quá trình đến Poisson với tốc độ λ , thời gian phục vụ có phân phối mũ tốc độ phục vụ µ với n server và trạng thái hệ thống (kích thước bộ đệm) không giới hạn. Hình 2-5: Mô hình hàng đợi M/M/n Lược đồ chuyển trạng thái và hệ phương trình trạng thái cân bằng: Hình 2-6: Chuỗi Markov của hàng đợi M/M/n Trong mô hình trên, hệ thống ở trạng thái i khi có i khách hàng được phục vụ đồng thời. Tốc độ đến và tốc độ phục vụ của chùm trong trạng thái i được xác định là λ và iµ Khi một khách hàng đến tại trạng thái i sẽ được chuyển sang trạng thái i+1; ngược lại, khi một khách hàng hoàn thành phục vụ của nó và rời khỏi hệ thống, trạng thái i sẽ được chuyển về trạng thái i-1. Đặt P = (P0,P1,...,Pn) là xác suất trạng thái cân bằng của hệ thống, với Pi là xác suất trạng thái ổn định (steady-state) của trạng thái i (0 ≤ i ≤ n) . Theo lược đồ trạng thái như hình 2-6, ta có hệ phương trình trạng thái cân bằng sau:  λ P = µ P0 1 µP = λP0  P = λ P 1 2 2 µP + λP = ( λ + µ ) P  2 0 1  2 2µ 2 0   3µP3 + λP = ( λ + 2 µ ) P2 1  λ3  P3 = 3!µ 3 P0   nµPn+1 + λPn−1 = (λ + nµ ) Pn  ... P = λ P n  n n!µ n 0  - - 10
∞ Với ràng buộc: ∑ P =1 i =0 i i λ 1 Nếu i < n, Pi = P0   .  µ  i!   i λ 1 Nếu i ≥ n, P = P   0  n! n i −n µ i −1  n−1 ρ i ∞ ρ i  Suy ra P0 = 1 + ∑ + ∑  i −n    i =0 i! i =n n! n  Xác suất của một yêu cầu phải đợi được tính theo công thức Erlang’s C hoặc được goi là Erlang’s delay: pnn ∞ ρi n!(n − ρ ) P ( waiting ) = C (n, ρ ) = ∑ P0 = n−1 i n! n i −n ρ pnn i =n ∑ i! n!(n − ρ ) i =0 + Các công thức sau đây đã được chứng minh bằng phương pháp giải tích. • Số lượng trung bình khách hàng trong hệ thống: ρ E[ N ] = ρ + C (n, ρ ) n−ρ • Số lượng trung bình khách hàng đợi, có nghĩa là chiều dài hàng đợi trung bình: ρ E[ N Q ] = C (n, ρ ) n−ρ • Số yêu cầu được phục vụ trung bình: λ E[ N s ] = =ρ µ 3. Hàng đợi có Markov M/M/n/n Là hàng đợi có quá trình đến Poisson với tốc độ λ , thời gian phục vụ có phân phối mũ tốc độ phục vụ µ với n server và trạng thái hệ thống (kích thước bộ đệm) bị giới hạn bởi số lượng n. - - 11
Hình 2-7: Mô hình hàng đợi M/M/n/n a. Lưu lượng xảy đến (Offered Traffic), lưu lượng được mang (Carried Traffic) và lưu lượng tràn (Overflow Traffic). λ Lưu lượng xảy đến (offered traffic): ρ = . µ Lưu lượng được mang (carried traffic): bằng ρ .(1 − PB) , trong đó PB là xác suất tắc nghẽn của hệ thống. Lưu lượng tràn (overflow traffic): còn được gọi là lưu lượng mất (lost traffic), có thể được tính như sau: Lưu lượng tràn = Lưu lượng xảy đến – lưu lượng được mang Do đó, đối với mô hình M/M/n/n, lưu lượng tràn bằng: ρ tr = ρ − ρ .(1 − PB) = ρ ⋅ PB Lược đồ chuyển trạng thái và hệ phương trình trạng thái cân bằng: Hình 2-8: Chuỗi Markov của hàng đợi M/M/n/n Trong mô hình trên, hệ thống ở trạng thái i khi có i khách hàng được phục vụ đồng thời. Tốc độ đến và tốc độ phục vụ của chùm trong trạng thái i được xác định là λi và iµ Khi một khách hàng đến tại trạng thái i sẽ được chuyển sang trạng thái i+1; ngược lại, khi một khách hàng hoàn thành phục vụ của nó và rời khỏi hệ thống, trạng thái i sẽ được chuyển về trạng thái i-1. - - 12
Đặ t P = ( P0 , P1 ,..., Pn ) là xác suất trạng thái cân bằng của hệ thống, với Pi là xác suất trạng thái ổn định (steady-state) của trạng thái i ( 0 ≤ i ≤ n ) . Theo lược đồ trạng thái như hình 2-8, ta có hệ phương trình trạng thái cân bằng sau:  λ0 P1 = µ P0 µP1 = λ0 P0  2µP + λ P = (λ + µ ) P P2 = λ0 λ1 P0 (1)   2 0 0 1 1   2µ 2 3µP3 + λ1 P1 = (λ2 + 2 µ ) P2  λ λλ ...  P3 = 0 1 3 2 P0 3!µ   λn−1 Pn −1 = nµPn  ... Pn = λ0 λ1λ2  λn−1 P0   n!µ n ∑ n Với ràng buộc: i =0 Pi = 1(2) Kết hợp (1) và (2), ta có công thức tổng quát sau: λ0 λ1λ2  λi −1 Pi = P0 i = 1,2,3,…,n i! µ i Trong đó P0 được tính như sau: −1  λ λλ λ λ λ λ  P0 = 1 + 0 + 0 21 +  + 0 1 2 n n −1   µ 2µ n! µ  Khi xem các tốc độ đến là như nhau, bằng λ , ta có các giá trị: −1 ρi  n ρi  Pi = P0 ,i = 1,2,3,…,n với P0 = ∑  i!  i =0 i!  Khi đó, xác suất tắc nghẽn được tính theo công thức Erlang-B như sau: ρ n / n! PB = E ( n, ρ ) = P = n ,i = 1,2,3,…,n ∑i=0 ρ i / i! n Các công thức sau đây đã được chứng minh bằng phương pháp giải tích. - - 13
• Số lượng trung bình khách hàng trong hệ thống, số lượng trung bình server bận. n n ρj n−1 ρi E[ N ] = n = ∑ jPj = ∑ j P0 = ρ ∑ P0 = ρ (1 − Pn ) j =0 j =0 j! j =0 i! ρ do đó số lượng trung bình của các yêu cầu cho một máy chủ đã cho là: (1 − Pn ) n • Số server sử dụng (Utilization of a server) : n i n ρ Như ta đã thấy U s = ∑ Pi = = (1 − Pn ) i =1 n n n • Thời gian chờ trung bình của một server nhất định: Bằng cách áp dụng các mối quan hệ nổi tiếng 1/ µ P ( the server is idle) = e + 1/ µ trong đó là thời gian rỗi trung bình của server. Như vậy ρ 1/ µ (1 − Pn ) = n e + 1/ µ Do đó : n 1 e= − λ (1 − Pn ) µ • Thời gian bận trung bình của hệ thống: Rõ ràng - - 14
Eδ r U r = 1 − P0 = 1 + Eδ r λ n ρi 1 − P0 ∑ i! Trong đó Eδ r = = i =0 λP0  n ρi  λ 1 + ∑     i =0 i!  - - 15
CHƯƠNG 3: PHẦN MỀM MÔ PHỎNG GPSS I. Giới thiệu GPSS. General Purpose Simulation System (GPSS) là một ngôn ngữ được thiết kế để mô hình hóa các sự kiện rời rạc. Loại ngôn ngữ như nó tồn tại được đến ngày hôm nay là kết quả của hơn hai mươi năm phát triển. GPSS có gốc rễ trong những ngày đầu phát triển của các máy tính lớn, những ý tưởng cơ bản của nó đã được chứng minh là phù hợp với các ứng dụng dựa trên các vấn đề của ngày nay bằng cách sử dụng môi trường máy tính hiện đại. Sự phổ biến của GPSS là do một phần khả năng mà nó thể hiện. Nói dễ hiểu, mô hình GPSS sẽ yêu cầu nhiều trang của C++ để hoàn thành mã hóa một mục tiêu tương tự. Người sử dụng GPSS là tựu do tập trung vào các vấn đề quan trọng trong mô hình được phát triển từ ngôn ngữ riêng của mình thu thập số liệu thống kê, xuất kết quả, lập bảng đánh giá và thực hiện một loạt các công việc nhàm chán. GPSS cung cấp một bộ các thành phần trừu tượng của các kiểu khác nhau và một bộ các toán tử được gọi là các Block nhằm thực hiện một số hành động trên các thành phần riêng lẻ. Transaction là thành phần di chuyển thông qua một chuỗi các Block đã được thiết kế để mô phỏng hệ thống đang được nghiên cứu. Tình trạng các thành phần của mô phỏng sẽ xác định các chi tiết của một Block tại một loại nhất định sẽ hoạt động như thế nào. Một số loại khác nhau của các thành phần thiết bị sẵn có trong GPSS. Thiết bị (Facility) là một thực thể hoặc là có sẵn để sử dụng hoặc sử dụng nhiều nhất một transaction tại một thời điểm. Lưu trữ (Storage) là tương tự nhưng có khả năng có thể được chỉ định để phù hợp với nhu cầu của những người xây dựng mô hình. Cuối cùng, một bộ chuyển đổi logic (Logicswitch) là một bộ các yếu tố đơn giản ON / OFF có thể được thiết lập và thử nghiệm để sửa đổi các đường đi của một Transaction thông qua các Block của mô phỏng. Các Transaction di chuyển thông qua các Block hoạt động trên các thực thể Facility, GPSS thu thập các Facility đang được sử dụng và thống kê hành vi transaction chẳng hạn như nội dung trung bình, thời gian trung bình, nội dung tối đa và tương tự thế, để đưa vào các báo cáo tự động tạo ra khi chạy mô hình hoàn thành. Thêm vào đó là khả năng đo lường và báo cáo được cung cấp bởi các hàng đợi và các thực thể bảng (Table). Khối QUEUE và DEPART được đặt xung quanh một Block hoặc một nhóm của các Block nơi Transaction chờ đợi để có thể thu thập. Hàng đợi sẽ thu thập và báo cáo số liệu thống kê như chiều dài hàng đợi tối đa và trung bình, độ trễ trung bình, tỷ lệ phần trăm của các transaction đã bị làm trễ. Thời gian trong GPSS cũng là một khái niệm trừu tượng. Nó đo thời gian trong mô phỏng bằng các đơn vị thời gian. Một đơn vị thời gian được giải thích một cách thích hợp do người thiết kế mô hình. - - 16
II. Các thực thể GPSS ( GPSS Entities ). GPSS được xây dựng xung quanh một số khái niệm trừu tượng cơ bản được gọi là các thực thể. Để có thể tạo ra mô phỏng phức tạp, phải có được một sự hiểu biết về các thực thể và các quy tắc để có thể thao tác được với thực thể đó. Các thực thể GPSS là những đối tượng trừu tượng tồn tại trong một mô phỏng. Nếu thích một khái niệm cụ thể hơn, ta có thể nghĩ về một thực thể GPSS như là một tập hợp các con số trong bộ nhớ của máy tính. Việc tập trung lại của tất cả các thực thể được gọi là các mô phỏng. Các loại thực thể nổi bật nhất là các Transactions và Block, bởi vì mô phỏng, ở một mức độ lớn, là bao gồm nhiều Transactions di chuyển từ một Block đi vào Block khác. Transactions là các loại thực thể duy nhất có thể bị xóa ra khỏi mô phỏng. Để có hiệu quả trong việc tạo ra các mô phỏng, ta phải hiểu các thuộc tính của các thực thể GPSS và làm thế nào để sử dụng các Block GPSS để gây ra sự tương tác giữa các thực thể. Các thực thể GPSS được đánh số. Khi bạn sử dụng một tên để chỉ một thực thể, giá trị số nguyên liên kết với tên được sử dụng để tìm ra các thực thể. Tuy nhiên bình thường ta không gán các giá trị số nguyên vào tên, mặc dù câu lệnh EQU cho phép ta làm như vậy. GPSS World bình thường gán một giá trị duy nhất lớn hơn hoặc bằng đến 10.000. Hầu hết các đơn vị GPSS được tạo ra tự động khi cần thiết. Ví dụ, một tham chiếu đến một thực thể Facility sử dụng các tên Barber sẽ khiến một Facility được tạo ra nếu không tồn tại trước. Sự tiện lợi này đôi khi có thể khiến cho mô phỏng sử dụng rất nhiều bộ nhớ ảo do một lỗi trong mô hình GPSS. Mô phỏng của ta có thể cực kỳ lớn. Việc sử dụng bộ nhớ ảo cung cấp cho mô phỏng chiếm một nửa gigabyte (512 MB). Một số thực thể phải được khai báo cụ thể trước khi chúng có thể được sử dụng. Nói chung có một thuộc tính, chẳng hạn như kích thước, mà phải được thực hiện được biết đến với các đối tượng mô phỏng. Tên trong trường nhãn, được gọi là một thực thể Label được sử dụng để chỉ các thực thể. Các đối tượng sau đây phải được khai báo trước khi chúng có thể được sử dụng: • Các thực thể Storage phải được khai báo trong câu lệnh STORAGE. • Các biến số học phải được khai báo trong câu lệnh VARIABLE. • Biến "Floating point" phải được khai báo trong câu lệnh FVARIABLE. • Các biến Boolean phải được khai báo trong câu lệnh BVARIABLE. • Ma trận phải được khai báo trong câu lệnh MATRIX, hoặc khai báo tạm thời Matrix PLUS. - - 17
• Tables phải được khai báo trong câu lệnh TABLE. • Qtables phải được khai báo trong câu lệnh QTABLE. • Các hàm phải được khai báo trong câu lệnh FUNCTION và Follower Function. • Tham số Transaction phải được khai báo trong các Block ASSIGN, MARK, READ, SELECT, SPLIT, COUNT hoặc TRANSFER SUB trước khi chúng được tham chiếu. Một số loại thực thể phải chịu một hoặc nhiều mối quan hệ đặc biệt đến Transactions. Các thực thể Storage và Facility có thể được sở hữu một phần hoặc toàn bộ bởi các Transactions. Sau đó, các Transactions khác có thể đến phần còn lại trong mô hình trong khi chúng chờ đợi việc cấp quyền sở hữu. Điều đó tùy thuộc vào chúng ta để đảm bảo quyền sở hữu đó là cuối cùng sẽ được cấp phát bởi các chủ sở hữu ban đầu, bằng cách làm cho họ nhập Blocks RELEASE, RETURN, hoặc LEAVE. Nếu không, các mô phỏng có thể không hoàn toàn thành công. Một số khối như PREEMPT và FUNAVAIL có các tùy chọn chuyển hướng các đường đi của các Transaction sở hữu. 1. Thực thể Transaction Transactions chuyển từ các Block đến Block khác trong một mô phỏng theo một cách đại diện cho các hệ thống thế giới thực mà ta là người mẫu. Khi một Transaction bắt đầu di chuyển trong mô phỏng, nó liên tục đi vào các Blocks miễn là nó có thể. Trong quá trình mô phỏng, các Transaction cố gắng đi từ các Block đến Block khác được gọi là đăng nhập Transaction ( Active Transaction ). Nếu một Transaction không tìm thấy điều kiện thuận lợi khi nó cố gắng đi vào một Block, nó có thể đến để nơi nghỉ ngơi ( it may come to rest ). Sau đó, Transaction khác được chọn để bắt đầu để việc di chuyển qua mô phỏng ( move through simulation ) cho đến khi nó được nghỉ ngơi. Transaction được đánh số liên tục trong suốt một phiên làm việc bắt đầu với giá trị là 1. Câu lệnh CLEAR có thể khiến Transactions bắt đầu với giá trị là 1 thêm lần nữa. Các hành vi của Transaction được xác định phần nào bởi một số biến trạng thái được gọi là thuộc tính Transaction (Transaction Attributes ). Các thuộc tính quan trọng của Transactions là: • Tham số ( Parameters )- Các tham số Transaction là một tập hợp các giá trị liên quan đến một Transaction. Mỗi Transaction có thể có bất kỳ số lượng các tham số. Ứng với mỗi Thông số có một số hiệu thông số ( Parameter Number ) mà nó được tham chiếu và có giá trị. Số hiệu tham số là số nguyên dương. Để hiệu quả, bạn có thể cho phép GPSS World để truy cập trực tiếp các thông số bằng cách sử dụng các Block Parameter trong mô phỏng. Block Parameter là một mảng của Tham số liền kề nhau như là một phân đoạn duy nhất của bộ nhớ được cấp phát - - 18
và giải phóng. Khi bạn tạo các Parameter đầu tiên, mà số hiệu tham số thuộc phạm vi đó, tất cả các tham số khác trong phân đoạn đó đều được coi là đúng. Khi sử dụng một Parameter trong Block Parameter, các đối tượng mô phỏng có thể đi trực tiếp đến nó, chứ không phải kiểm tra từng Parameter riêng biệt. Điều này có thể tiết kiệm rất nhiều thời gian. Tất cả những gì ta phải làm để sử dụng Blocks Parameter là khai báo chúng trong Simulate Page Model Settings Notebook. Tham số Transaction phải được tạo ra và gán giá trị trước khi chúng có thể được tham chiếu. Các Block ASSIGN, MARK, và TRANSFER SUB, SELECT, SPLIT và COUNT có thể tạo ra một tham số Transaction nếu chúng không tồn tại. • Sự ưu tiên ( Priority ) – Sự ưu tiên của một Transaction được xác định bằng cách nhận được khi nó và các Transactions khác đang chờ đợi cùng một tài nguyên. Transaction với giá trị ưu tiên cao hơn sẽ nhận được sự ưu tiên. Các hàng đợi ưu tiên quan trọng nhất trong mô phỏng là Current Events Chain, Facility Delay Chains, và các Storage Delay Chain. Future Events Chain không phải là một chuỗi ưu tiên. Hiệu quả của việc ưu tiên là một Transaction sẽ được chọn trước Transactions ưu tiên thấp hơn khi mới vừa đăng nhập Transaction, hoặc Facility hoặc Storage được chọn. Transaction được ưu tiên thường được lên kế hoạch đến và phục vụ đầu tiên. • Đánh dấu Thời gian ( Mark Time ) - đồng hồ thời gian tuyệt đối mà các Transaction đầu tiên đi vào mô phỏng hoặc đi vào Block MARK mà không có toán hạng A. • Assembly Set - Một số nguyên dương được giữ bên trong mỗi Transaction. Assembly Set được sử dụng để đồng bộ hóa Transaction trong các Block ASSEMBLE, GATHER, and MATCH. Khi Transaction được tạo ra bởi Block GENERATE, bản thân Assembly Set được thiết lập bằng số hiệu Transaction của nó. Khi Transaction được tạo ra bởi một Block SPLIT, Assembly Set được đặt bằng các Transaction bố mẹ. Một Transaction có thể sửa đổi Assembly Set của mình bằng cách sử dụng Block ADOPT. • Chỉ số trễ ( Delay Indicator ) - Một cờ được giữ trong mỗi Transaction được thiết lập bằng cách từ chối đi Block ( Block entry refusal ), và thiết lập lại bằng cách đi vào vào Block TRANSFER SIM. Nó được sử dụng bởi các Block TRANSFER SIM để chuyển hướng Transaction. • Chỉ số vết ( Trace indicator ) - Một cờ được giữ trong mỗi Transaction tạo ra các tin nhắn vết ứng với mỗi lần Transaction đi vào một Block. Chỉ số vết được thiết lập bởi một Block TRACE và thiết lập lại bởi một Block UNTRACE. • Current Block – Số thực thể của Block có chứa Transaction. • Next Block - Số thực thể của Block mà Transaction sẽ cố gắng đi trong lần tiếp theo. - - 19
• Chains - Trạng thái của một Transaction được xác định ở một mức độ nào đó bằng các chuỗi mà nó chứa. Một Transaction được cho là chính xác nhất trong một số trạng thái: • ACTIVE – Là Transaction có độ ưu tiên cao nhất trên các Current Events Chain. • SUSPENDED – Là Transaction đang chờ đợi Future Events Chain hoặc Current Events Chain để trở thành Active Transaction. • PASSIVE – Là Transaction đã đến nơi nghỉ ngơi trong các mô phỏng trên User Chain, Delay Chain, hoặc Pending Chain. • TERMINATED – Là Transaction đã bị hủy và không còn tồn tại trong các mô phỏng. Ngoài ra, còn có một trạng thái mà không phải là loại trừ lẫn nhau với những thứ khác: • PREEMPTED – Là Transaction đã được hình thành trước mỗi Facility và trên một hoặc nhiều Chain bị gián đoạn. 2. Các thực thể Block ( Block Entities ) Thực thể Block trong GPSS là các yếu tố cấu trúc cơ bản của mô phỏng. Nó rất hữu ích để diễn dãi ra bằng các mô hình GPSS thông qua sơ đồ khối. Đây là mạng lưới các kết nối sự kiện với các biểu tượng Block tương ứng với các vị trí của các Block trong mô phỏng. Mỗi Transaction trong mô hình được chứa trong Block một cách chính xác, nhưng hầu hết các Block có thể chứa nhiều Transaction. Trình tự của Block gặp phải bởi các Transaction khác nhau xác định bản chất và phần lớn kết quả của mô phỏng. Mỗi Transaction đi vào một Block sau đó đi tiếp, cho đến khi nó được gọi bằng TERMINATED hoặc mô phỏng kết thúc. Transactions đôi khi phải chờ đợi trong một Block cho đến khi phù hợp với điều kiện cho đi vào Block tiếp theo. Các Block vĩnh viễn trong một mô phỏng được tạo ra trong quá trình dịch mô hình ban đầu từ Block Statement trong mô hình. Trình tự của các Block trong mô phỏng đã được biên dịch là giống như thứ tự của câu lệnh Block bởi trình biên dịch. Số thứ tự dòng được bỏ qua trong GPSS World. Các GPSS Block Statement có thể được tạo ra trong Object Model bằng cách sử dụng các trình soạn thảo văn bản toàn màn hình hoặc thông qua một hoặc nhiều hộp thoại tạo Block cho chương trình cung cấp thông qua các lệnh trình đơn Edit / Insert Block. Các Block Statement gửi đến mô phỏng hiện hành tạo ra một Block tạm thời trong một chế độ gọi là " Manual Simulation ". Các Statement tương tác tạo ra các Active - - 20