Đọc truyện Mô phỏng mạng_ Lý thuyết chung - Mô phỏng mạng

Mô phỏng mạng_ Lý thuyết chung

Trước Sau

Màu nền

Font chữ

Font size

Chiều cao dòng

2.1 Các lỗi thường gặp trong mô phỏng

1. Mức độ chi tiết không hợp lý: Mô phỏngcho phép nghiên cứu một hệ thống chi tiết hơn mô hình phân tích.. Việc phân tích đòi hỏi nhiều đơn giản hóa và giả thiết. Hay nói cách khác, mô hình phân tích là kém chi tiết hơn. Trong mô hình mô phỏng, mức độ chi tiết chỉ bị hạn chế bởi thời gian giành cho việc phát triển mô phỏng. Mô phỏng càng chi tiết yêu cầu càng nhiều thời gian để phát triển. Khả năng có lỗi sẽ tăng cao và sẽ khó khăn hơn để phát hiện ra các lỗi này. Thời gian gỡ rối của các lỗi này cũng sẽ tăng. Mô phỏng chi tiết hơn cũng đòi hỏi máy tínhcần nhiều thời gian hơn để thực hiện. Điều này đặc biệt quan trọng đối với các công việc mô phỏng lớn, ở đó thời gian thực hiện có thể mất nhiều giờ hoặc nhiều ngày.

Về tổng quát có thể cho rằng một mô hình càng chi tiết thì càng tốt, vì nó chỉ cần ít giả thiết hơn. Tuy nhiên điều này không phải lúc nào cũng đúng. Một mô hình chi tiết yêu cầu các kiến thức chi tiết của thông số đầu vào, và nếu không có các kiến thức chi tiết đó có thể sẽ làm cho các mô hình không chính xác. Ví dụ, trong quá trình mô phỏng hệ thống phân chia thời gian, giả sử rằng cần phải mô phỏng thời gian đáp ứng yêu cầu của đĩa . Một cách là tạo ra nó bằng cách sử dụng một hàn phân bố hàm mũ. Một cách chi tiết hơn là mô phỏng sự chuyển động của đầu đọc và sự quay của đĩa Nếu lựa chọn thứ 2 được chọn thì kết quả sẽ chỉ chính xác hơn khi các thông tin cần tham chiếu của sector và track là đã biết . Trong thực tế, người phân tích sẽ chọn lựa chọn 2. Tuy nhiên, khi thông tin tham khảo về sector không có sẵn để đưa vào mô hình thì người phân tích sẽ quyết định tạo ra các con số sector ngẫu nhiên theo phân bố hàm mũ. Kết quả là thời gian phục vụ là theo phân bố hàm mũ, một kết quả mà có thể sẽ ít tốn kém hơn nếu lựa chọn theo cách đầu tiên

Một vấn đề khác nữa trong các mô hình chi tiết là chúng tốn nhiều thời gian để phát triển. Tốt hơn hết là hãy bắt đầu với một mô hình ít chi tiết hơn, thu được một số kết quả, xem xét các tác động, sau đó đưa thêm chi tiết trong những yếu tố có ảnh hưởng lớn nhất đến kết quả.

2. Ngôn ngữ không thích hợp: Việc lựa chọn ngôn ngữ lập trình có ảnh hưởng khá quan trọng đối với giai đoạn đầu phát triền của mô hình. Các ngôn ngữ mô phỏng với mục đích đặc biệt cho phép rút ngắn thời gian phát triển mô hình và dễ dàng hơn trong các nhiệm vụ thường phải thực hiện như việc xác nhận (sử dụng các vết) và các phân tích thống kê. Mặt khác, các ngôn ngữ có mục đích tổng quan có tính khả chuyển cao hơn và cho phép điều khiển nhiều hơn về mức độ hiệu quả và thời gian thực hiện của mô phỏng.

3. Các mô hình chưa được kiểm tra . Các mô hình mô phỏng thường là các chương trình máy tính lớn và trừ khi được đề phòng đặc biệt, nó có khả năng sẽ có nhiều lỗi chương trình hoặc lỗi về lập trình, dẫn đến việc cho ra các kết quá không có ý nghĩa.

4.Các mô hình không hợp lệ. Ngay cả khi chương trình mô phỏng không có lỗi,nó vẫn có thể biểu diễn hệ thống không chính xác bởi vì các giả thiết không chính xác về hành vi của hệ thống. Do đó các mô hình cần phải được kiểm tra để đảm bảo rằng kết quả có được là giống với kết quả có được từ hệ thống thật Kết quả của tất cả các mô hình mô phỏng này đều có thể sai, nó chỉ đúng sau khi đã được xác nhận bằng các mô hình phân tích, các phép đó, hoặc bằng trực giác.

5. Điều kiện xử lý ban đầu không thích hợp. Phần đầu tiên của mô phỏng thường không miêu tả các hoạt động của hệ thống trong trạng thái ổn định. Bởi vậy phần ban đầu của mô phỏng thường được loại bỏ.

6. Sự mô phỏng quá ngắn. Người phân tích thường cố gắng tiết kiệm thời gian của mình và thời gian của máy tính bằng cách thực hiện các chương trình mô phỏng trong thời gian ngắn. Kết quả trong các trường hợp này bị phụ thuộc rất nhiều vào các điều kiện ban đầu và không thể hiện được hệ thống thực. Thời gian giành cho mô phỏng phụ thuộc vào mức độ chính xác mong muốn (độ rộng của khoảng cách tin cậy) và sự thay đổi của các đại lượng quan sát.

Các tính toán đơn giản cho sự thay đổi từcác giá trị của một biến ngẫu nhiên không đem lại một ước lượng chính xác về các thay đổi trong mô hình mô phỏng bởi vì có sự tương quan giữa các giá trị.

7. Hàm sinh số ngẫu nhiên quá kém. Mô hình mô phỏng đòi hỏi các số ngẫu nhiên, thủ tục tạo ra các số ngẫu nhiên được gọi là các hàm sinh số ngẫu nhiên. Sẽ an toàn hơn nếu sử dụng các hàm sinh nổi tiếng đã được phân tích kỹ lưỡng hơn là phát triển các hàm sinh riêng của mình Thậm chí các hàm sinh nổi tiếng này cũng đã có lỗi.

8. Sự lựa chọn khởi đầu không hợp lệ. Hàm sinh số ngẫu nhiên là các thủ tục máy tính, nó tạo ra một con số ngẫu nhiên từ một con số ngẫu nhiên khác cho trước. Số ngẫu nhiên đầu tiên trong dải số đó được gọi là hạt giống và được đưa ra bởi các nhà phân tích. Con số ngẫu nhiên đầu tiên cho các chuỗi số ngẫu nhiên cần phải được lựa chọn một cách cẩn thận để đảm bảo tính độc lập giữa các chuỗi số ngẫu nhiên. Thông thường, các nhà phân tích dùng chung một chuỗi số cho các quá trình xử lý khác nhau hoặc sử dụng cùng một giá trị ban đầu giống nhau cho tất cả các chuỗi (thường thường người ta khởi tạo bằng 0). Nó tạo ra sự tương quan giữa các quá trình khác nhau trong hệ thống và dẫn đến các kết quả có thể sẽ không thể hiện được hệ thống thực.

2.2 Các lý do khác khiến mô phỏng bị sai

1. Sự ước lượng thời gian không hợp lý: Nguyên nhân chính và trước tiên khiến cho các mô hình mô phỏng thất bại là các nhà phát triển đánh giá không đúng thời gian và nỗ lực cần thiết để pháp triển một mô hình mô phỏng. Thời gian giành cho các dự án mô phỏng thường được bắt đầu là các dự án 1 tuần, 1 tháng và sau đó thì kéo dài đến một vài năm. Nếu một mô phỏng thành công và cung cấp nhiều thông tin hữu ích, các người dùng sẽ muốn thêm vào nhiều tính năng, nhiềuthông số và chi tiết hơn. Mặt khác thì, nếu một chương trình mô phỏng không cung cấp thông tin hữu ích thì nó thường được mong muốn rằng nếu bổ xung thêm nhiều tính năng, nhiều thông số và chi tiết hơn có thể làm chương trình có ích hơn. Trong bất kỳ tình huống nào kể trên thì các dự án thường kéo dài hơn so với kế hoạch ban đầu.

Trong 3 kỹ thuật phân tích hiệu năng : mô hình hóa phân tích, đo đạc và mô phỏng thì việc thực hiện mô phỏng là cần nhiều thời gian nhất, nhất là đối với các mô hình hoàn toàn mới thì quá trình phát triển phải bắt đầu từ con số không. Ngoài ra cũng cần có thời gian để xác thực lại mô hình. Những người phân tích mới đối với lĩnh vực này thường không đánh giá đúng về độ phức tạp khi triển khai mô phỏng. Đối với các dự án mô phỏng trong thời gian dài, cần phải chuẩn bị trước cho những thay đổi trong hệ thống, điều khó có thể tránh khỏi đối với các dự án mô phỏng trong thời gian dài.

2. Mục tiêu không thể thực hiện được. Mô phỏng là một kế hoạch khá phức tạp, cũng giống như các kế hoạch khác,cần phải xác định rất rõ ràng các mục tiêu với các đặc tính như cụ thể, đo lường được, có thể thực hiện được, có thể lặp lại được và toàn diện. Mục tiêu cần được viết ra rõ ràng và có sự thống nhất giữa người phân tích và người sử dụng về kết quả trước khi phát triển mô hình

Một ví dụ phổ biến của mục tiêu đo lường được là “ mô hình X”. Có thể mô hình các đặc tính khác nhau của X với các mức độ chi tiết khác nhau.được cấu thành từ một vài mô hình có mức độ chi tiết khác nhau. Nếu không có quy định đúng, không thể nói rằng mục tiêu đã đạt được hay chưa. Kế hoạch mà không có mục tiêu sẽ kéo dài mãi và cuối cùng sẽ kết thúc khi tài trợ đã hết.

3. Thiếu các kỹ năng cần thiết. Một dự án mô phỏng cần ít nhất bốn kỹ năng sau

(a) Kỹ năng về lãnh đạo dự án. Có khả năng tạo ra động lực, lãnh đạo và quản lý các thành viên trong nhóm mô phỏng.

(b) Kỹ năng về mô hình hóa và thống kê thông tin. Có khả năng chỉ ra các đặc trưng chủ chốt của hệ thống và mô hìnhchúng ở mức độ chi tiết cần thiết.

(c) Kỹ năng về lập trình. Là khả năng viết ra một chương trình máy tính có thể đọc được, kiểm tra được để thực hiện mô hình chính xác.

(d) Am hiểu về hệ thống được mô hình mô hình hệ thống. Là khả năng hiểu về hệ thống, giải thích được cho nhóm mô phỏng về hệ thống, iễn giải các kết quả mô phỏng dưới dạng ảnh hưởng của chúng lên thiết kế hệ thống

Một nhóm mô phỏng nên bao gồm các thành viên có các kỹ năng trên, và người đứng đầu lý tưởng nhất là người có đủ 4 kỹ năng trên

4. Mức độ tham gia của người dùng chưa hợp l‎í : Nhóm mô phỏng và các tổ chức của người dùng cần phải được gặp mặt định kỳ và thảo luận về tiến độ, các vấn đề, các sự thay đổi nếu có trong hệ thống. Hầu hết các hệ thống tiến triển hoặc thay đổi theo thời gianvà một mô hình được phát triển mà không có sự tham gia của người sử dụng thì hiếm khi thành công. Các cuộc gặp mặt định kỳ sẽ giúp tìm ra các lỗi trong mô hình từ giai đoạn đầu và cho phép mô hình được thống nhất với các thay đổi của hệ thống.

5. Các tài liệu hướng dẫn đã lỗi thời hoặc không có thực. Hầu hết các mô hình mô phỏng đều tiến triển trong một thời gian rất dài và liên tục được thay đổi khi hệ thống bị thay đổi hoặc đã được tìm hiểu ở mức tốt hơn . Các tài liệu về các mô hình này thường là cũ quá so với sự phát triển, trừ khi nó được quan tâm đặc biệt không thì sẽ bị lỗi thời. Chiến lược tốt nhất bao gồm cả tài liệu bản thân trong chương trình và sử dụng ngôn ngữ máy tính có thể đọc một cách dễ dàng hơn.

6. Không đủ khả năng để quản lý một chương trình máy tính có độ phức tạp lớn. Một số công cụ kỹ thuật phần mềm sẵn có cho quản lí các dự án phần mềm lớn. Các công cụ này giúp ta giữ đúng định hướng của việc thiết kế các đối tượng, các yêu cầu về chức năng, cấu trúc dữ liệu và sự ước lượng về tiến độ công việc. Ngoài ra còn một số nguyên tắc thiết kế như nguyên tắc về thiết kế từ trên xuống và nguyên tắc về lập trình cấu trúc đã được phát triển để giúp đỡ sự phát triển của các chương trình máy tính lớn theo thứ tự. Nếu không sử dụng các công cụ và kỹ thuật này thì sẽ không thể có sự thành công cho việc phát triển một mô hình mô phỏng lớn.

7. Kết quả khó hiểu: Phần lớn các kết quả mô phỏng khó hiểu là do có lỗi trong chương trình mô phỏng,các giả thiết về mô hình không hợp lý hoặc không có các kiến thức về hệ thống thực tế. Bởi vậy người phát triển mô hình cần phải kiểm tra lại mô hình và nếu vẫn còn các kết quả khó hiểu thì hãy thông báo cho người sử dụng chú ý. Nó có thể cung cấp những cái nhìn thấu đáo hơn các hoạt động của hệ thống hoặc các đặc tính của hệ thống cần được chi tiết hóa hơn nữa.

Danh sách dưới gồm 3 danh sách con tương ứng với các giai đoạn lập kế hoạch, phát triển, sử dụng của một dự án mô phỏng.

Bảng 2.1 Danh sách cần KIỂM TRA về các MÔ PHỎNG

1.Các việc cần kiểm tra trước khi phát triển mô phỏng.

(a) Mục tiêu của mô phỏng trên lý thuyết đã được xác định hợp lý ?

(b) Mức độ chi tiết trong mô hình thích hợpvới mục đích hay không ?

(c) Nhóm mô phỏng có bao gồm đầy đủ các thành viên với các vị trí: lãnh đạo, mô hình hóa, lập trình và am hiểu về hệ thống máy tính hay không ?

(d) Có đủ thời gian cho kế hoạch của dự án hay không ?

2.Kiểm tra trong quá trình phát triển.

(a) Tính độc lập và tính đơn trị của bộ sinh số ngẫu nhiên được sử dụng trong mô phỏng đã được kiểm tra hay chưa ?

(b) Mô hình có được xem xét thường xuyên bởi người sử dụng hay không?

3.Kiểm tra sau khi thực hiện mô phỏng.

(a) Độ dài của mô phỏng có thích hợp hay không ?

( b) Quá trình chuyển tiếp của giai đoạn đầu đã đượclooại bỏ trước khi tính toán hay chưa

(d) Mô hình đã được xác nhận là hợp lý trước khi sử dụng kết quả của nó hay chưa ?

(e) Nếu có kết quả đáng ngạc nhiên, xem chúng đã được kiểm duyệt hay chưa ?

(f) Các bộ số đầu tiên (hạt giống)của các dải số ngẫu nhiên có bị trùng lặp hay không ?

2.3 Ccác thuật ngữ

Dưới đây là một số thuật ngữ thường được sử dụng trong mô hình hóa. Để định nghĩa chúng, một ví dụ mô phỏng về việc lập lịch của CPU sẽ được sử dụng trong phần này. Vấn đề đặt ra là nghiên cứu các kỹ thuật lập lịch khác nhau cho CPU với những đặc điểm về yêu cầu công việc khác nhau. Các thành phần khác của hệ thống như phương tiện ghi nhớ, thiết bị đầu cuối sẽ bị bỏ qua trong phần này.

Biến trạng thái: Các biến mà giá trị của nó để xác định các trạng thái của hệ thống gọi là biến trạng thái. Nếu một chương trìnhh mô phỏng bị dừng lại ở giữa chừng, nó có thể được khởi động lại nếu chỉ khi các giá trị của biến trạng thái đã được biết trước Trong một chương trình mô phỏng lập lịch cho CPU biến trạng thái là độ dài hàng đợi các công việc.

Hình 2.1 Mô hình thời gian rời rạc và thơi gian liên tục

Sự kiện: Một thay đổi trong trạng thái của hệ thống gọi là sự kiện. Trong việc mô phỏng lập lịch cho CPU có 3 sự kiện như sau: sự kiện tới của một công việc, bắt đầu thực hiện một chương trình và đích đến của công việc.

Mô hình thời gian liên tục và thời gian rời rạc Một mô hình mà trạng thái hệ thống được xác định trong mọi thời điểm gọi là mô hình thời gian liên tục. Ví dụ mô hình lập lịch của CPU là một mô hình liên tục. Nếu trạng thái một hệ thống được định nghĩa chỉ tại một thời điểm cụ thể thì mô hình đó gọi là mô hình rời rạc. Ví dụ như một lớp học thường gặp mặt vào các chiều thứ 6. Giả sử trong mô hình, trạng thái của lớp được quy định là số sinh viên tham dự lớp. Chú ý rằng sĩ số lớp chỉ được xácc định vào các thứ 6. Trong tất cả các ngày khác, trạng thái của lớp là không xách định. Đây là một ví dụ về mô hình thời gian rời rạc. Hình 2.4 thể hiện 2 kiểu mô hình trên.

Mô hình trạng thái liên tục và trạng thái rời rạc: Một mô hình được gọi là mô hình có trạng thái liên tục hoặc trạng thái rời rạc phụ thuộc vào các biến trạng thái là liên tục hay rời rạc. Nhắc lại phần 10.1, biến liên tục có thể lấy các giá trị vô hạn không thể đếm được. Ví dụ, trong một mô hình về lớp học hàng tuần, trạng thái được xác định bằng thời gian sinh viên tham dự một môn học,là mô hình trạng thái liên tục. Mặt khác, nếu trạng thái được xác định bởi số sinh viên thì nó là mô hình trạng thái rời rạc. Trong mô hình lập lịch cho CPU, biến trạng thái – chiều dài hàng đợi- có thể chỉ được gán giá trị nguyên. Bởi vậy mô hình trạng thái rời rạc ở hình 24.2a cũng có thể gọi là mô hình sự kiện rời rạc. Tương tự như vậy mô hình trạng thái liên tục cũng có thể gọi là mô hình sự kiện liên tục.

Hình 2.2 Continuous-state versus discrete-state models

Hình 2.3 Deterministic versus probabilistic models

Chú ý rằng tính liên tục của thời gian không bao hàm tính liên tục của trạng thái và ngược lại. Vì vậy đối với các ví dụ có thể tìm thấy nhiều ví dụ cho 4 kết hợpcó thể xảy ra đó là: trạng thái rời rạc/thời gian rời rạc, trạng thái rời rạc /thời gian liên tục, trạng thái liên tục/ thời gian rời rạc và trạng thái liên tục/ thời gian liên tục.

Mô hình tất định và mô hình xác xuất: Nếu đầu ra (kết quả) của mô hình có thể dự đoán một cách chắc chắn thì đó là một mô hình tất định. Mặt khác, một mô hình là mô hình xác xuất nếu với lặp lại cùng một bộ thông số đầu vào nhưng cho các kết quả khác nhau . Điều này thể hiện trong hình 24.3. Hình 24.3b là kết quả của mô hình xác xuất. Các điểm trên đường thẳng đứng bi ểudiễn các kết quả của đầu ra khác nhau cho một giá trị đầu vào. Trong hình 24.3a, với đầu vào giống nhau thì cho đầu ra giống nhau, do vậy trên trục tung chỉ có một điểm.

Mô hình tĩnh và mô hình động: Một mô hình mà trong đó thời gian không là biến số thì được gọi là mô hình tĩnh, còn nếu trạng thái của hệ thống thay đổi theo thời gian thì gọi là mô hình động. Ví dụ, mô hình lập lịch cho CPU là mộ mô hình động. Một ví dụ về mô hình tĩnh là mô hình cho thể hiện công thức tính năng lượng: E=mc2 .

Mô hình tuyến tính và mô hình phi tuyến: Nếu mô hình có thông số đầu ra là một hàm tuyến tính của các thông số đầu vào thì đó là mô hình tuyến tính, nếu không thì đó là mô hình phi tuyến, hãy xem hình 24.4 dưới đây.

Hình 2.4 Mô hình tuyến tính và mô hình phi tuyến

Mô hình mở và mô hình đóng: Nếu tham số đầu vào là ở bên ngoài so với mô hình và độc lập với mô hình thì đó là mô hình mở. Mô hình đóng là mô hình có đầu vào ở bên trong nó. Hình 24.5 thể hiện hai mô hình hàng đợi của một hệ thống máy tính.Trong Hình 24.5b các công việc giống nhau được luân chuyển trong mô hình. Một công việc đi ra khỏi hàng đợi thứ 2 tiếp tục đi vào hàng đợi thứ nhất.. Đây chính là mô hình đóng. Còn hình 24.5a thể hiện một mô hình mở, trong đó các công việc mới được đưa vào mô hình.

Hình 2.5 Mô hình mở và mô hình đóng

Mô hình ổn định và không ổn định: Nếu các hoạt động động của mô hình ở mức trạng thái ổn định, đó là độc lập về mặt thời gian, thì nó được gọi là ổn định. Còn nếu một mô hình có các hoạt động liên tục thay đổi thì nó gọi là không ổn định. Những điều này được minh họa ở hình 24.6

Hình 2.6 Mô hình ổn định và không ổn định

Các mô hình hệ thống máy tính thường là các mô hình: thời gian liên tục, trạng thái rời rạc, xác suất, động và phi tuyến. Có một vài mô hình mở và một vài mô hình đóng. Ngoài ra các mô hình ổn định và không ổn định cũng được sử dụng.

2.4 Lựa chọn ngôn ngữ mô phỏng

Lựa chọn ngôn ngữ là bước quan trọng nhất trong tiến trình phát triển của một mô hình mô phỏng. Một quyết định sai trong bước này có thể làm cho thời gian thực hiện mô phỏng lâu, không hoàn thành được việc nghiên cứu và không khả thi

Có bốn lựa chọn: một ngôn ngữ mô phỏng, một ngôn ngữ lập trình đa dụng, ngôn ngữ lập trình đa dụng mở rộng, và gói mô phỏng (như là một bộ giải quyết mạng). Mỗi lựa chọn có ưu nhược điểm riêng.

Các ngôn ngữ mô phỏng tiết kiệm được cho người phân tích đáng kể thời gian khi phát triển mô hình. Những ngôn ngữ này có sẵn các chức năng để cải thiện về thời gian, lập lịch sự kiện, biến đổi các thực thể, tạo các biến ngẫu nhiên , thu thập dữ liệu thống kê, và tạo các báo cáo. Chúng cho phép các nhà phân tích danh nhiều thời gian vào các kết quả cụ thể của hệ thông được mô hình mà không cần phải quan tâm nhiều đến các vấn đề chung chung đối với các mô phỏng. Các ngôn ngữ này cũng cho phép một mã module rất dễ đọc, có thể phát hiện lỗi rất tốt.….

Ngôn ngữ lập trình đa dụng như Pascal hoặc FORTRAN được chọn chủ yếu bởi vì các nhà phân tích đã quen với ngôn ngữ này. Hầu hết các nhà thiết kế mạng máy tính và các nhà phân tích mới không quen với những loại ngôn ngữ mô phỏng. Bên cạnh đó các yêu cầu về thời hạn cũng không cho phép họ học một loại ngôn ngữ mô phỏng nào. Hơn nữa, các ngôn ngữ mô phỏng thường không có sẵn trên hệ thống máy tính của họ. Đó là lý do tại sao hầu hết mọi người viết mô phỏng đầu tiên của mình bằng ngôn ngữ lập trình đa dụng

Ngay cả đối với những người mới, thời gian chọn lựa giữa ngôn ngữ mô phỏng và ngôn ngữ lập trình đa dụng cũng không xảy ra. Nếu họ chọn ngôn ngữ mô phỏng, họ phải bỏ thời gian để học ngôn ngữ này. Trong một số trường hợp, họ thậm chí còn phải cài đặt nó vào trong hệ thống máy tính của họ và chú ý để không bỏ sót một file nhỏ nào trong quá trình cài đặt. Nếu họ chọn ngôn ngữ lập trình đa dụng, họ có thể bắt đầu ngay lập tức . Nhưng họ phải mất thời gian để thực hiện các thường trình để xử lý sự kiện, tạo số ngẫu nhiên và những thứ tương tự như thế. Có thể phải mất một khoảng thời gian đáng kể để tìm hiểu các vấn đề này và khám phá lại những vấn đề đã biết.

Điều đó không có ý là các nhà phân tích lúc nào cũng phải sử dụng các ngôn ngữ mô phỏng. Có những điều phải quan tâm khác, như hiệu xuất, tính linh động và tính cơ động, những yếu tố này có thể làm cho ngôn ngữ lập trình đa dụng trở thành một sự lựa chọn tốt nhất. Một mô hình được phát triển bằng ngôn ngữ lập trình đa dụng thì hiệu xuất hợn và chiếm ít thời gian của CPU. Ngôn ngữ lập trình đa dụng mang đến cho các nhà phân tích khả năng mềm dẻo hơn vì nó cho phép họ sử dụng những đường tắt bị cấm trong ngôn ngữ mô phỏng. Hơn nưa, một mô hình được phát triển bằng ngôn ngữ lập trình đa dụng có thể chuyển đổi để thực hiện ở những hệ thống máy tính khác nhau một cách dễ dàng

Để có được một lựa chọn khách quan giữa ngôn ngữ mô phỏng và ngôn ngữ lập trình đa dụng, các nhà phân tích được khuyên cáo nên học ít nhất một ngôn ngữ mô phỏng để các yếu tố khác cùng với kiến thức sẽ giúp ích trong việc lựa chọn một ngôn ngữ thích hợp

Một mở rộng của ngôn ngữ lập trình đa dụng như GASP (đối với FORTRAN) là một ngôn ngữ thay thế. Các mở rộng này bao gồm một tập các thường trình để xử lý các nhiệm vụ thường được yêu cầu trong các mô phỏng. Mục đích của chúng là đem đến một thỏa hiệp dưới dạng hiệu xuất, tính linh động và tính cơ động.

Các gói mô phỏng như QNET và RESQ cho phép người dùng định nghĩa một mô hình sử dụng đối thoại. Các gói này có một thư viện cac cấu trúc dữ liệu, các thường trình và các giải thuật. Ưu điểm lớn nhất của chúng là tiết kiệm thời gian. Vì dụ, sử dụng gói mô phỏng, một người có thể phát triển mô hình, giải quyết và có được kết quả trong vòng một ngày. Mặt khác, phát triển một mô phỏng sử dụng một ngôn ngữ có thể mất một vài ngày (nếu không muốn nói là vài tháng), tùy thuộc vào độ phức tạp của hệ thống.

Vấn đề chính của các gói mô phỏng là tính cứng nhắc. Chúng chỉ cung cấp các tính chất mềm dẻo đã được thấy trước bởi những người thiết kế ra chúng. Trong hầu hết trường hợp trong thực tế, các nhà phân tích gặp phải một số vấn đề này khác không thể mô hình được bằng gói mô phỏng. Điều này bắt buộc các nhà phân tích phải làm đơn giản hóa các quá trình. Tuy nhiên, đối với các hệ thống không thể mô hình theo phương pháp phân tích, sẽ tiết kiệm thời gian hơn rất nhiều nếu nhà phân tích xem xét khả năng sử dụng một gói mô phỏng trước khi bắt đầu phát triển một mô hình mô phỏng mới

Các ngôn ngữ mô phỏng có thể được phân loại vào 2 danh sách chính, những ngôn ngữ mô phỏng liên tục và những ngôn ngữ mô phỏng sự kiện rời rạc, phụ thuộc vào loại sự kiện mà chúng mô phỏng. Các ngôn ngữ mô phỏng liên tục được thiết kế để xử lý những mô hình sự kiện liên tục thường được diễn tả bằng các phương trình vi phân. Ví dụ về loại này là cáci ngôn ngữ CSMP và DYNAMO. Những ngôn ngữ này thường phổ biến trong các mô hình hệ thống hóa học. Mặt khác, các ngôn ngữ mô phỏng sự kiện rời rạc được thiết kế để xử lý những thay đổi sự kiện dời rạc. Hai ví dụ của loại ngôn ngữ này là SIMULA và GPSS. Một số ngôn ngữ như SIMSCRIPT và GASP cho phép các mô phỏngrời rạc, liên tục, và kết hợp. Bốn ngôn ngữ sau là các loại ngôn ngữ được các nhà phân tích hiệu suất hệ thông máy tính sử dụng.

2.5 Cácloại mô phỏng

Trong các loại mô phỏng khác nhau được để cập đến trong các tài liệu, những loại như mô phỏng Monte Carlo, mô phỏng Trace-Driven và mô phỏng sự kiện dời dạc là những loại mô phỏng thu hút được nhiều hứng thú nhất của các nhà khoa học máy tính

Mô phỏng sử dụng phần cứng hoặc phần sụn gọi là sự giả lập. Ví dụ, một bộ giả lập đầu cuối mô phỏng một loại đầu cuối trên một đầu cuối khác. Giả lập bộ xử lý giả lập một tập lệnh của một bộ xử lý trên một bộ khác. Mặc dù giả lập là một loại của mô phỏng, các vấn đề thiết kế cho giả lập hầu hết là các vấn đề về thiết kế phần cứng. Do đó, giả lập sẽ không được để cập đến trong tài liệu này nữa.

Ba loại mô phỏng khác được miêu tả ở đoạn sau.

2.5.1 Phương pháp mô phỏng Monte Carlo

Phương pháp mô phỏng tĩnh hay một phương pháp mô phỏng nào đó không có trục thời gian thì được gọi là phương pháp mô phỏng Monte Carlo. Những phương pháp thường được dùng để mô hình những hiện tượng xác suất , những hiện tượng không thay đổi đặc tính theo thời gian. Giống như một phương pháp mô phỏng động, các phương pháp mô phỏng tĩnh cũng cần phải có một bộ tạo các số giả ngẫu nhiên. Phương pháp mô phỏng Monte Carlo cũng được sử dụng để tính toán các biểu thức không theo sắc xuất bằng cách sử dụng các phương pháp theo sắc xuất.

Ví dụ. 2.5.1 Tính toán phép tích phân sau

Một cách để tính phép tích phân trên là tạo ra các số ngẫu nhiên được phân bố đều x và đối với từng số tính toán được một hàm y như sau:

Giá trị y mong muốn là:

Do đó, tích phân trên có thể được tính bằng cách tạo ra các số ngẫu nhiên được phân bố đều xi, tính toán yi, và sau đó tính trung bình cộng như sau:

2.5.2 Phương pháp mô phỏng Trace - Driven

Mô phỏng sử dụng trace làm đầu vào là phương pháp mô phỏng trace-driven. Trace là một bản ghi các sự kiện được sắp xếp theo thời gian của một hệ thống thật. Các phương pháp mô phỏng trace-driven này khá thông dụng trong các phân tích hệ thống máy tính. Chúng thường được sử dụng để phân tích và điều chỉnh các giải thuật quản lý tài nguyên. Giải thuật paging, phân tích bộ nhớ cache, các giải thuật lập lịch CPU, các giải thuật ngăn chặn nghẽn và các giải thuật để phân chia động bộ nhớ là các ví dụ về các trường hợp đã áp dụng thành công phương pháp mô phỏng Trace-driven và được để cập đến trong các tài liệu Trong những nghiên cứu đó, Trace của tài nguyên yêu cầu được dùng làm đầu vào để thực hiện mô phỏng để mô hình những giải thuật khác nhau. Ví dụ, để thực hiện so sánh các lưu đồ quản lý bộ nhớ khác nhau, một trace các mẫu tham chiếu trang nhớ của các chương trình quan trọng sẽ được lấy trên hệ thống. Sau đó có thể sử dụng các trace này để tìm ra tập các tham số tối ưu đối với một giải thuật quản lý bộ nhớ cho trước hoặc để so sánh những giải thuật khác nhau.

Cần phải chú ý rằng các trace phải là độc lập với hệ thống đang nghiên cứu. Ví dụ, một trace của các trang nhớ được lấy ra từ một đĩa phụ thuộc vào qui mô công việc và các chính sách thay thế trang nhớ được sử dụng. Trace này không thể dùng để nghiên cứu các chính sách thay thế trang nhớ khác. Do đó, một nhà phân tích có thể cần một trace của các trang nhớ được tham chiếu. Tương tự như vậy, một trace lệnh được lấy từ một hệ điều hành không thể dùng để phân tích một hệ điều hành khác.

Những ưu điểm của phương pháp mô phỏng trace –driven như sau:

1. Tính tin cậy: Rất dễ dàng chuyển kết quả của phương pháp mô phỏng trace-driven cho các thành viên khác trong đội thiết kế. Ví dụ, một trace các tham chiếu trang nhớ có độ tin cậy cao hơn so với các tham chiếu được tạo ngẫu nhiên sử dụng một phân bố giả định.

2. Dễ dàng kiểm tra: Bước đầu tiên của phương pháp mô phỏng trace - driven là thực hiện giám sát hệ thông thực để thu các trace. Trong suốt quá trình giám sát này, nhà phân tích cũng có thể đo kiểm các đặc tính hiệu suất của hệ thống. Bằng việc so sánh hiệu suất đã đó được với hiệu suất có được khi mô phỏng, nhà phân tích có thể kiểm tra mô hình trace – driven một cách dễ dàng

3. Khối lượng công việc chính xác: Một trace duy trì các tác dụng tương quan và đan xen trong khối lượng công việc (tải). Việc đơn giản hoá như khi bắt đầu một mô hình phân tích về tải là không cần thiết.

4. Cân bằng về mức độ chi tiết: Do mức độ chi tiết trong tải là cao, có thể nghiên cứu ảnh hưởng của từng thay đổi nhỏ trong mô hình hoăc các giải thuật

5. Ít ngẫu nhiên: Trace là một đầu vào xác định. Nếu lặp lại mô phỏng, đầu vào trace là không đổi nhưng đầu ra có thể khác nhau do tính ngẫu nhiên ở những phần khác của mô hình. Nói chung, đầu ra của mô hỉnh trace- driven ít thay đổi hơn, điều đó có nghĩa là mô hình không cần phải lập lại nhiều lần một mô phỏng để có được kết quả tin cậy thống kê mong muốn. Nếu các phần khác của hệ thống cũng không ngẫu nhiên, thì có thể thu được kết quả chính xác trong một lần thực hiện mô phỏng của mô hình

6. So sánh công bằng: Trace cho phép những khả năng khác nhau được so sánh với cùng một luồng đầu vào. Đây là một phép so sánh công bằng hơn những mô hình mô phỏng có đầu vào được tạo ra từ luồng ngẫu nhiên và khó mô phỏng các khả năng khác nhau.

7. Tương tự như triển khai thực sự: Một mô hình trace-driven nhìn chung là rất giống với hệ thống thực tế mà nó mô hình hoá. Do đó, khi thực hiện nó, nhà phân tích có thể cảm thấy rất thoải mái về độ phực tạp trong việc thực hiệngiải thuật đề xuất

Những nhược điểm của phương pháp mô phỏng trace-driven như sau:

1. Phức tạp: Mộ mô hình trace – driven yêu cầu mô phỏng chi tiết hơn về hệ thống. Đôi lúc độ phực tạp của mô hình làm lu mờ giải thuật đang được mô hình hoá

2. Tính điển hình: Các Traces được thưc hiện trong một hệ thống có thể không đại diện cho tải trong một hệ thông khác. Thậm chí trong một hệ thống tải có thể thay đổi theo thời gian, và vì vậy các trace trở nên vô dụng nhanh hơn những loại mô hình tải có thể hiệu chỉnh theo thời gian

3. Tính hữu hạn: Trace là một chuỗi dài. trace chi tiết về hoạt động trên một hệ thống trong vài phút có thể đủ để làm đầy một phần đĩa. Kết quả dựa trên những phút ít ỏi đấy không ứng dụng được cho các hoạt động trong khoảng thời gian còn lại của cả ngày

Tính hợp lý ở từng điểm

: Trong khi sử dụng các trace để kiểm tra tính hợp lý, phải hết sức cần thận vì các trace chỉ cung cấp một điểm kiểm tra đơn lẻ.

Một giải thuật là tốt nhất cho một trace có thể không hề tốt cho các trace khác. Nhà phân tích cần dùng nhiều trace khác nhau để kiểm tra các kết quả .

5. Chi tiết: Vấn đề chính của phương pháp mô phỏng trace-driven là độ chi tiết cao. Nhìn chung các trace là những chuỗi dài cần phải được đọc ra từ đĩa và sau đó cần phải hoàn thành việc tính toán cho từng phần tử của trace

6. Cân bằng: Đối với các trace, rất khó thay đổi các đặc tính tải. Bản thân một trace cũng không tự thay đổi nó được. Do đó để kết luận về sự ảnh hưởng của những thay đổi trong tải, thì cần phải có một trace cho tải bị thay đổi. Tương tự như vậy, nếu một trace chứa các đặc tính yêu cầu tài nguyên của một số công việc thì rất khó để nghiên cứu các ảnh hưởng tới từng công việc đơn lẻ.

2.5.3 Các mô phỏng sự kiện rời rạc

Một mô phỏng sử dụng mô hình trạng thái rời rạc của hệ thống được gọi là phương pháp mô phỏng sự kiện rời rạc. Phương pháp này ngược với các phương pháp mô phỏng sự kiện liên tục ở chỗ trong mô phỏng sự kiện liên tục trạng thái của hệ thống lấy các giá trị liên tục. Các mô hình trạng thái liên tục được sử dụng trong các mô phỏng hóa học do trạng thái của hệ thống được mô tả bởi sự tập trung của một chất hóa học. Trong các hệ thống máy tính, các mô hình sự kiện rời rạc được sử dụng bởi vì trạng thái của hệ thống được mô tả bởi số lượng công việc ở những thiết bị khác nhau. Lưu ý rằng thuật ngữ “rời rạc” không dùng để chỉ giá chị thời gian được sử dụng trong mô phỏng. Phương pháp mô phỏng sự kiện rời rạc có thể sử dụng các giá trị thời gian liên tục hay rởi rạc.

Tất cả phương pháp mô phỏng sự kiện rời rạc đều có chung một cấu trúc. Bất kể hệ thống được mô hình là gì, thì phương pháp mô phỏng cũng sẽ có một số thành phần như sau: Nếu sử dụng ngôn ngữ lập trình đa dụng, thì các nhà phân tích phải tự phát triển tất cả các thành phần. Nguôn ngữ lập trình mô phỏng thì có thể cung cấp một vài thành phần còn lại các nhà phân tích phải tự phát triển. Các thành phần đó như sau

1. Bộ lập lịch sự kiện (Event Scheduler): Lưu trữ một danh sách liên kết các sự kiện xắp xẩy ra. Bộ lập lịch này cho phép tính toán các sự kiện theo nhiều cách khác nhau. Một số phép tính toàn như sau:

(a) Lập lịch sự kiện X tại thởi điểm T

(b) Giữ sự kiện X trong khoảng thời gian dt

(d) Giữ sự kiện X vô hạn định (Cho đến khi nó được một sự kiện khác lập lịch)

(e) Lập lịch cho một sự kiện đang bị giữ vô hạn định

Bộ lập lịch sự kiện là một trong những thành phần hoạt động thường xuyên nhất khi tiến hành mô phỏng.Nó được thực thi trước các sự kiện, và có thể được gọi nhiều lần trong một sư kiện để lập lich các sự kiện mớikhác. Do lập lịch sự kiện có ảnh hưởng đáng kế tới hiệu xuất tính toán của một phương pháp mô phỏng, nên chủ đề này sẽ được đề cập nhiều hơn trong phần 24.6

2. Cơ chế SimulationClockandaTime-advancing: Mỗi mô phỏng đều có một biến toàn cục đại diện cho thời gian được mô phỏng. Bộ lập lịch có trách nghiệm thực hiện trước thời gian này. Có 2 cách để thực hiện. Cách đầu tiên là phương pháp thời gian đơn vị (unit time), gia tăng thời gian bằng một gia tăng nhỏ và sau đo kiểm ra để tìm xem có sự kiện nào xuất hiện hay không. . Phương pháp thứ 2, được gọi là phương pháp event-driven, thời gian tự động tăng đến thời điểm có sự kiện tiếp theo gần nhất xẩy ra. Phương pháp thời gian đơn vị thường không được dùng trong các mô phỏng máy tính.

3. Các biến trạng thái hệ thống (SystemStateVariables): Là các biến toàn cục mô tả trạng thái của hệ thống. Ví dụ trong mô phỏng lập lịch CPU, biến trạng thái hệ thống là số lượng công việc có trong hang đợi. biến toàn cục này khác với các biến cục bộ như thời gian CPU cần để xử lý một công việc, là biến được lưu trong cấu trúc dữ liệu đại diện cho công việc đó.

4. Các thường trình của sự kiện (EventRoutines): Từng sự kiện được mô phỏng bằng thường trình của chính nó. Các thường trình này cập nhật các biến trạng thái hệ thống và lập lịch những sự kiện khác. Ví dụ, trong khi mô phỏng cơ chế lập lịch CPU, có thể cần đến các thường trình để xử lý 3 sự kiện là việc mới xuất hiển, lập lịch công việc, hoàn thành công việc

5. Các thường trình đầu vào (InputRoutines): Các thường chình này chứa các tham số mô hình, như yêu cầu về CPU trung bình từ người sử dụng trên một công việc. Vì cần nhiều thời gian để hoàn thành mô phỏng, sẽ tốt hơn nếu yêu cầu tất cả đầu vào ngay từ lúc đầu và sau đó thì giải phỏng người sử dụng. Các thường trình đầu vào thông thường cho phép các tham số thay đổi theo một cách cụ thể. Ví dụ mô phỏng có thể được thực hiện với yêu cầu CPU trung bình thay đổi từ 1 đến 9 ms trong các bước 2ms. Mỗi tập các giá trị đầu vào xác định một phép lặp có thể được lặp lại nhiều lần với những khởi đầu khác nhau. Do đó, một lần thực hiện mô phỏng có nhiều vòng lặp và mỗi vòng lặp lại bao gồm nhiều lần lặp lại.

6. Bộ tạo báo cáo (ReportGenerator): Chúng là các thường trình đầu ra được thực hiện vào giai đoạn cuối của mô phỏng. Chúng tính toàn kết quả cuối cùng và in ra theo một định dạng cụ thể.

7. Các thường trình khởi tạo (InitializationRoutines): Chúng thiết lập trạng thái khởi tạo cho các biến trạng thái hệ thống và khởi tạo những luổng tạo số ngẫu nhiên khác nhau. Các thường trình này nên là các thường trình riêng biệt để khởi tạo trạng thái vào lúc bắt đầu mô phỏng, lúc bắt đầu một vòng lặp lại và lúc bắt đầu lặp.

8. Các thường trình bám vết (TraceRoutines): Chúng in ra các tham số trung gian trong quá trình thực hiện mô phỏng bắt đầu. Chúng giúp sửa lỗi chương trình mô phỏng. Các thường trình này nên có tính năng on/ off để có thể tắt chúng đi trong lần các lần chạy sản phẩm cuối cùng của mô hình. Một mô hình thậm chí còn có khả năng ngắt hoạt động từ bàn phím và bật/ tắt các thường trình bám vết.

9. Quản lý bộ nhớ động (DynamicMemoryManagement): Số thực thể trong mô phỏng thay đổi liên lục khi các thực thể mới được tạo ra và các thực thể cũ bị phá hủy, do đó cần phải dọn rác thường xuyên. Hầu hết ngôn ngữ mô phỏng và các ngôn ngữ lập trình đa dụng có chức năng dọn rác tự động. Trong các trường hợp khác, người lập trình phải tự viết code để quản lý bộ nhớ động

10. Chương trình chinh (MainProgram): Tập hợp tất các thường trình lại với nhau. Nó gọi các thường trình đầu vào, khởi tạo mô phỏng, thực hiện những lập lại khác nhau, và cuối cùng gọi các thường trình đầu ra

2.4.6 Các giải thuật thiết lập sự kiện

Trong các mô phỏng sự kiện rời rạc, phải đảm bảo rằng các sự kiện xuất hiện trong một trình tự và thời gian thích hợp. Hầu hết ngôn ngữ lập trình đều có chức năng tự động xắp sếp sự kiện này tuy nhiên đối với nhưng mô phỏng được viết bằng ngôn ngữ đa dụng, người lập trình phải thực hiện chức năng này. Đôi khi, đối với những mô phỏng sử dụng ngôn ngữ mô phỏng, nhà phân tích cũng thích sử dụng giải thuật xắp sếp của riêng họ. Ví dụ, trong một số trường hợp, hiệu quả hoạt động của những giải thuật này tiếp kiệm được khoảng 30% tổng tời gian của bộ xử lý

Lập lịch sự kiện thường được thực hiện bằng việc giữ các thông báo sự kiện theo một danh sách liên kết có thứ tự. Mỗi thông bao chứa thời gian xẩy ra sự kiện và một con trỏ tới mã có thể phải thi hành tại thời điểm đó. Có hai thao tác cần phải thực hiện thường xuyên trên tập này: Thứ nhất là chèn các sự kiện mới và thứ 2 là tìm sự kiện tiếp theo (xuất hiện sớm nhất) và xoá nó ra khỏi tập. Lựa chọn câu trúc dữ liệu để duy trì tập này ảnh hưởng đến thời gian xử lý cần thiết cho 2 hoạt động này. Một số cấu trúc dữ liệu cần ít thời gian để chèn nhưng yêu cầu xử lý đáng kể để tìm sự kiện tiếp theo. Các cấu trúc dữ liệu khác thực hiện tất cả những công việc tại thời điểm chèn để việc tìm sự kiện tiếp theo không hề phức tạp. Bởi vậy lựa chọn cấu trúc dữ liệu phụ thuộc vào tần suất chèn vào, xoá đi và vào số lượng trung bình của các sự kiện trong tập sự kiện tương lai. Một số cấu trúc dữ liệu đã được đề xuất như sau :

Danh sách liên kết theo thứ tự (OrderedLinkedList) : Phương pháp phổ biến nhất được sử dụng trong các ngôn ngữ mô phỏng như SIMULA, GPSS, và GASP IV là những phương pháp có danh sách kiên kết theo thứ tự lớn gấp đôi. Đầu vào đầu tiên trong danh sách là sự kiện tiếp theo gần nhất. Đo đó, việc xoá bỏ tương đối dễ dàng Để chèn them sự kiện mới, danh sách được tìm kiếm để tìm ra vị trí thích hợp nhất cho một đầu vào mới. Một số phương pháp tìm kiếm khác đã được đề xuất. Phương pháp phổ biến nhất là tìm kiếm ngược từ giá trị thời gian cao nhất. Lần lượt, danh sách sẽ được tìm kiếm từ đầu vào đầu tiên trở đi. Một số phương pháp khác còn dữ con trỏ ở giữa danh sách, trược hết là xác định nửa danh sách chứa vị trí thích hợp, rồi sau đó tìm quyết định tìm xuôi hay tìm ngược để tìm vị trí đúng

Fig. 2.xyz1 Danh sách liên kết theo thứ tự

Danh sách chỉ mục tuyến tính (IndexedLinearList): Trong phương pháp này, tập các sự kiện tương lai được chia thành những tập nhỏ. Mỗi tập có độ dài cố định trong khoảng thời gian t và được duy trì như là một danh sách con. Một ma trận các chỉ mục được giữ theo qui tắc là đầu vào của chỉ số thứ i trỏ tới danh sách con thứ i chưa các sự kiện đã được lập lịch trong khoảng [(i- 1)”t, i”t),nghĩa là, tại hoặc sau thời điểm (i- 1)”t nhưng trược thời điểm I ”t. Ở đây, khoảng thời gian t được người sử dụng đặt. Do đó, Khi có một sự kiện mới cần được chèn vào, danh sách con yêu cầu có thể được xác định mà không cần tìm kiếm. Sau đó một danh sách con thích hợp được tìm ngược lại để tìm ra vị trí thích hợp của đầu vào mới.

(Fig. 2.xyz2 Danh sách chỉ mục tuyến tính

Một số thay đổi đã được đề xuất cho phương pháp này dựa trên lý luận rằng việc khoảng thời gian giữ sự kiện (thời gian từ khi lặp lịch một sự kiện và thời điểm xuất hiện của nó) được phân bố không đồng đều. Trong một thay đổi, đã có một đề xuất là để cho tất cả các danh sách có cùng một chiều dài bằng khoảng cách giữa mỗi đầu vào của danh sách; điều đó nghĩa là, t là biến đổi. Phép tìm kiếm nhị phân được sử dụng để tìm đầu vào danh sách thích hợp. Trong một đề xuất thay đổi khác, chỉ có danh sách con đầu tiên mới được sắp xếp; những danh sách còn lại không được sắp xếp. Một danh sách con chỉ được sắp xếp khi nó thành danh sách thứ nhất, do đó giảm được chi phí cho việc sắp xếp

Một đề xuất thay đổi đáng quan tâm của phương pháp này được gọi là các hàng lịch. Nó dựa trên loại lịch để bàn mà con người hay dùng để lập lịch sự kiện. Một cuốn lịch để bàn thông thường có 365 trang – mỗi trang là một ngày trong năm. Tất cả các sự kiện trong một ngày được ghi vào trang ứng với ngày đó. Các sự kiện của cùng một ngày nhưng của năm tiếp theo cũng có thể được ghi vào trang đó Đặc điểm này sẽ không gây nhầm lẫn gì nếu năm xảy ra sự kiện cũng được ghi cùng với sự kiện và các sự kiện được xóa đi sau khi được thực hiện. Ý tưởng này có thể được thực hiện một cách dễ dàng bằng cách sử dụng danh sách tuyến tính được chỉ mục. Khoảng t ứng với một ngày, và kích thước của chỉ mục ứng với số ngày trong năm,Cả hai tham số này cần phải được lựa chọn cẩn thận để cho số lượng sự kiện trên một trang là nhỏ (gần với 0 hoặc 1).

3. Cấu trúc cây: Các cấu trúc dữ liệu hình cây cũng được sử dụng trong phương pháp mô phỏng các tập sự kiện. Thường là các cây nhị phân do đó thời gian tìm kiếm n sự kiện là log2n.

Trường hợp đặc biệt của cây nhị phân là heap, trong đó mỗi sự kiện được lưu lại như là một node của cây nhị phân. Mỗi node có thể có tới 2 nhánh con, và thời gian cho mỗi sự kiện ở mỗi node nhỏ hơn thời gian ở mỗi nhánh con của nó. Điều đó nghĩa là sự kiện ở gốc có thới gian sớm nhất. Ưu điểm của các heap là cây có thể được lưu trong một ma trận (ngược với danh sách liên kết) bằng việc đặt gốc tại vị trí 1 của ma trận và các nhánh con tại vị trí 2 và 3. Các node sự kiện tiếp theo nằm ở vị trí 4, 5, 6, 7 của mà trận, và cứ thế, như ở

hình 2.

xyz3

. Điểm giao nhau của heap rất đơn gian vì rất dễ để tìm ra node cha và noed con của một node bất kỳ. Hai nhánh con của node nằm ở vị trí i là 2i và 2i + 1. Node cha của node nằm ở vị trí i là ở vị trí [i/2]. Ở đây, [.] nghĩa là bỏ bớt tới số nguyên nhỏ hơn tiếp theo.

Ma trận có thể được sắp xếp lại một phần khi có thêm hoặc loại bỏ một phần tử

FIGURE

.xyzz3

Cây nhị phân

Việc lựa chọn cấu trúc dữ liệu thích hợp phụ thuộc vào phân bố thời gian giữ sự kiện và số lượng sự kiện trong tập sự kiện tương lai.

Nó cũng phụ thuộc vào mức độ rằng buộc mà cấu trúc dữ liệu có thể được thực hiện trong một ngôn ngữ lập trình cho trước. Danh sách được liên kết đơn giản được coi là một thay thế có hiệu quả trong trường hợp số lượng sự kiện ít (ít hơn 20 sự kiện). Đối với các tập có kích cỡ 20 đến 120, danh sách tuyến tính chỉ mục là lựa chọn phù nhất, đối với những tập lớn hơn heap được coi là có hiệu quả nhất.