Đồ án Lý thuyết hàng đợi và hiệu năng mạng máy tính

ộ khách hàng đến hệ thông tức số khách hàng đến trong một đơn vị thời gian. Tính chất của quá trình Poisson: + Tính chất phân tích ngẫu nhiên: các quá trình phân tách ngẫu nhiên từ một quá trình Poisson có tốc độ l cũng là một quá trình Poisson có tốc độ lpi, pi là các phân nhánh sao cho =1. +Tính chất liên hợp : quá trình kết hợp các quá trình Poisson độc lập khác là một quá trình Poisson nhân với tốc độ l= Xác suất của quá trình Poisson: Pn(t) là xác suất để số khách hàng đén hệ thống thời điểm t là n thì ta có thể tính được Pn(t)=. Kỳ vọng của quá trình Poisson: giả sử là số khách hàng đến trung bình trong khoảng thời gian t. =lt. Phương sai của quá trình Poisson =lt. Qui tắc Little Phát biểu : Độ dài trung bình của hàng đợi tích của tốc độ khách hàng đến và thời gian thường trú của khách hàng trong hàng đợi. Q: số khách hàng trung bình trong hệ thống xếp hàng l: tốc độ đến của các khách hàng đến R: thời gian thường trú của khách hàng trong hệ thống. Công thức Little là một công thức đơn giản được áp dụng rất rộng rãi trong các bài toán tính toán với mô hình hàng đợi. Nó thường được sử dụng để kiểm tra độ nhất quán của dữ liệu đo. Mặt khác, trong thực tế, khi phân tích hiệu năng, ta thường biết 2 trong số 3 đại lượng của qui tắc này (thường là số lượng yêu cầu trung bình của hệ thống và thông lượng của hệ thống đó) và mong muốn biết giá trị thứ ba (thời gian lưu trú trung bình trong hệ thống). Vì vậy, qui tắc được sử dụng làm trung tâm cho nhiều thuật toán ước lượng mô hình hàng đợi, mà ta sẽ giới thiệu trong các phần sau. Chứng minh Có rất nhiều phương pháp để chứng minh công thức Little. Sau đây ta sẽ xem xét một phương pháp chứng minh đơn giản được sử dụng rộng rãi , mang tính trực quan dựa trên lược đồ mà không cần nhiều các kiến thức về các quá trình ngẫu nhiên. Thời gian Số các khách hàng S(t) 8 7 7 6 5 4 3 2 1 0 N(t) A(t) D(t) Hình I-14: Lược đồ mô phỏng cách chứng minh công thức Little Xét hàng đợi có chiều dài là Q, tốc độ khách hàng đến là l. Xét hệ thống trong khoảng thời gian từ [0..T]. Ta có lược đồ như hình vẽ trên. Trong đó: A(t) là số khách hàng đến trong khoảng thời gian [0..t] D(t) là số khách hàng rời khỏi hệ thống trong khoảng thời gian đó. Q(t) là số khách hàng trong hệ thống tại thời điểm t. S(t) là diện tích hình giới hạn bởi A(t) và D(t): diện tích này chính là tổng thời gian sử dụng hệ thống trung bình cho tất cả khách hàng đến thời điểm t. Ta có : Q(t)= A(t)- N(t). Tốc độ khách hàng đến hệ thống tính trung bình trong khoảng thời gian [0..t] là : Thời gian thường trú trung bình của mỗi khách hàng Số khách hàng trung bình trong hệ thống tại thời điểm t là : Khi thì . Do đó Q=lR Ta thấy là chứng minh trên không đòi hỏi tới một giả thiết nào cả đối với phân phối của quá trình đến, phân phối dịch vụ của khách hàng, số các server thậm chí cả trật tự phục vụ khách hàng. Do vậy nó có thể áp dụng cho hàng đợi tổng quát G/G/m. Từ qui tắc Little ta có thể suy ra một số qui tắc như sau Qui tắc tận dụng: U=XS. Mức độ tận dụng tài nguyên của hệ thống được tính bằng tích của thông lượng tương ứng với tài nguyên đó và thời gian phục vụ trung bình của tài nguyên. Qui tắc thời gian đáp ứng trong đó Z là thời gian suy nghĩ của hệ thống. Nếu trong khoảng thời gian theo dõi, ta không chỉ đếm được các yêu cầu đã hoàn thành cho toàn bộ hệ thống, mà còn đếm được số yêu cầu hoàn thành ở mỗi tài nguyên. Ta gọi số khách thăm một nguồn tài nguyên là tỉ số giữa số lượng hoàn thành ở một server tài nguyên so với tổng số hoàn thành của toàn bộ hệ thống, hoặc trực quan hơn là số khách thăm trung bình có yêu cầu mức hệ thống về tài nguyên đó. Ta gọi biến chỉ số k là tương ứng cho tài nguyên thứ k, và ta có công thức và định nghĩa được thông lượng ứng với tài nguyên thứ k là: Xk=Vk.X Gọi Dk: yêu cầu dịch vụ của tài nguyên thứ k. Dk=Vk.Sk .Ta cần phân biệt: Sk là thời gian phục vụ trung bình cho một khách ở tài nguyên k và Dk là yêu cầu phục vụ tổng hợp của tài nguyên này. D là yêu cầu phục vụ của một công việc với toàn bộ hệ thống, tính bằng tổng các yêu cầu ở các nút. Qui tắc thời gian thường trú trong hệ thống: , do đó, ta có Q=XR. Một số hàng đợi cơ bản Dựa trên lí thuyết xếp hàng ta sẽ áp dụng các quy tắc đã nêu vào các hàng đợi sau : M/M/1: hàng đợi Markov đơn giản nhất. M/M/m: các hàng đợi nhiều trạm dịch vụ M/M/m/N/N: các hàng đợi có dân số hạn chế. M/G/1: hàng đợi không Markov hàng đợi Markov M/M/1. Hình 2.2.Hàng đợi đơn giản Hàng đợi đơn giản là hàng đợi chỉ có 1 server, với thời gian phục vụ cho mỗi khách hàng là như nhau, do đó, thời gian phục vụ trung bình S cố định. Chiến lược của hàng đợi này là chiến lược FIFS. Hàng đợi M/M/1 có hai đặc trưng chủ yếu là : - Tiến trình đến là tiến trình Poisson - Hệ thống phục vụ ( Server) có thời gian dịch vụ cho mỗi khách hàng là biến ngẫu nhiên có phân bố mũ. Sau đây ta sẽ khảo sát hai đặc trưng trên của hàng đợi này Quá trình đến của khách hàng là một tiến trình Poisson - Xác suất để 1 khách hàng đến hệ thống trong khoảng thời gian [t, t+t] là - Xác suất để không có khách hàng nào đến hệ thống trong khoảng thời gian [t, t+t] là (1-) là tốc độ khách hàng đến . Sử dụng lí thuyết quá trình Poisson ta có : - Xác suất để có n khách hàng đến hệ thống trong khoảng thời gian t s là : Pn(t)= - Số khách hàng trung bình đến hệ thống trong t(s) là : Thời gian phục vụ mỗi khách hàng là biến ngẫu nhiên tuân theo phân bố mũ Trong hệ thống xếp hàng M/M/1 thì thời gian phục vụ là các biến ngẫu nhiên tuân theo phân bố mũ nghĩa là : - Xác suất để một dịch vụ được hoàn thành trong khoảng thời gian [t, t+t] là - Xác suất để không có một dịch vụ nào được hoàn thành trong khoảng thời gian [t, t+t] là 1- Trong đó là tốc độ dịch vụ trung bình của server va 1/ lf thời gian dịch vụ trung bình cho mỗi khách hàng của server. Hệ thống serve phục vụ như vậy là hệ thống không nhớ. Tính toán các tham số cho hàng đợi M/M/1 : - Xác suất trạng thái : như đã định nghĩa ta có trạng thái của hàng đợi tại một thời điểm là số khách hàng có mặt trong hàng đợi tại thời điểm đó. Trong bối cảnh của việc đánh giá hiệu năng của mạng máy tính bằng mô hình hàng đợi thì trạng thaí hệ thống chính là số gói tin lưu thông trong hệ thống. Việc tính toán xác suất trạng thái cho hàng đợi là rất quan trọng vì các độ đo hiệu năng đều phụ thuộc vào xác suất này. Gọi Pn(t) là xác suất để có số khách hàng trong hàng đợi tại thời điểm t là n thì tính toán theo phân bố mũ số khách hàng đến hệ thống và thời gian dịch vụ ta có Khi hệ thống xếp hàng đã hoạt động trong một khoảng thời gian tương đối dài thì hệ sẽ đi vào trạng thái cân bằng , khi đó tức là Pn(t) không đổi theo thời gian, Pn(t) à pn Như vậy ta có phương trình cân bằng toàn cục đối với mỗi trạng thái như sau : Tương ứng với mỗi trạng thái của hàng đợi ta có một phương trình cân bằng toàn cụ. Dựa vào phương trình này ta có thế tính được các xác suất trạng thái như sau : - Lập hệ Nphương trình cân bằng toàn cục cho N trạng thái - Giải hệ phương trình vứa lập thu được nghiệm là các xác suất trạng thái cần tìm Trên thực tế để tính toán xác xuất theo thuật toán vừa nêu là rất khó vì mỗi hàng đợi đều có không gian trạng thái rất lớn do đó hệ phương trình nhận được là rất lớn, rất phức tạp đối với việc tính toán đại số. Để giải bài toán này ta đi đến lớp các hàng đợi đơn giản hơn thoã mãn điều kiện cân bầng cụ thể, tức là cân bằng giữa luồng khách hàng đến hàng đợi và luồng khách hàng được phục vụ. Khi đó ta có phương trình cân bằng cục bộ là : hay với mọi i = Từ đó suy ra và p0= Đặt thì ta có và Hay . Dựa vào xác suất trạng thái được tính như trên ta có thể tính được các tham số của hàng đợi khác như sau Đối với hàng đợi M/M/1 thì độ hiệu dụng của hệ thống chính là xác suất để hệ thống không rỗng, do đó ta có độ hiệu dụng của hệ thống là U= 1-p0=. Như vậy chính là độ hiệu dụng của hệ thống Đối với khách hàng thứ k, thời gian lưu trú trong hệ thống được tính bằng: R=R+SQ. Trong đó, Q là độ dài của hàng đợi tại thời điểm khách hàng đó đứng ở ngoài hàng đợi (không kể bản thân khách hàng đó). Áp dụng luật Little vào, ta có kết quả là: R=S+S(XR) Suy ra Các hàng đợi nhiều trạm dịch vụ: M/M/m. Trước hết, ta xét hàng đợi chỉ có 2 server (hình 2.4). Hình 2.4. Hàng đợi có 2 server. Với hàng đợi này, ta có thể làm giảm thời gian lưu trú của khách hàng trong hệ thống. Ta có: Công thức này xây dựng được vì khi có 2 server cùng xử lý một hàng đợi, thời gian phục vụ của mỗi server giảm đi còn một nửa. Mặt khác, không phải lúc nào 2 server cũng bận, do đó có thể chưa cần phục vụ xong khách hàng thứ nhất (ví dụ ở server 1) ta đã có thể phục vụ tiếp khách hàng thứ 2 (ở server 2) nên thời gian phục vụ thực tế phụ thuộc vào xác suất bận của server, tức là phụ thuộc vào mức độ tận dụng hệ thống tại một server. Từ đây, ta có: . Suy ra: hay Công thức này cũng được sử dụng cho hệ thống đa server, tuy nhiên, dạng của nó như sau: và , với m là số server của hệ. Thời gian đáp ứng chính xác của các hệ thống đa server có thể được tính bằng công thức sau: , trong đó là xác suất mọi server đều bận và yêu cầu gửi đến sẽ được đặt vào hàng xếp. Thông thường, hàm này được định nghĩa: và được gọi là hàm Erlang C. Hàm Erlang B được định nghĩa cho hệ thống không có hàng đợi, tức là nếu khách hàng đến yêu cầu dịch vụ khi tất cả các server đều bận thì yêu cầu của họ sẽ bị huỷ. Hàm này có dạng như sau: Các hàm này có khả năng tính toán khá dễ. Do đó, nó cũng thường được sử dụng trong việc tính thời gian đáp ứng chính xác của hệ phân tán. Các hàng đợi có số khách hàng hạn chế M/M/m/N/N(hàng đợi đóng) Hàng đợi đóng có đặc điểm là nó chỉ phục vụ được một lượng khách hàng hạn chế. Gọi N là số khách hàng của hệ thống. N là một tham số của mô hình. Mỗi khách hàng trong hệ thống ở một trong các trạng thái: hoặc là đi vào hàng đợi (thời gian chuẩn bị để đi vào hàng đợi được gọi là thời gian nghĩ của hệ thống Z) hoặc đã ở trong hàng đợi và chờ được phục vụ. Trong hệ này, ta có: Biến đổi phương trình trên như sau: Khi thời gian suy nghĩ ngắn nhất và bằng 0, ta có R lớn nhất và bằng Hàng đợi M/G/1. Ký pháp biểu diễn một hàng đợi không có phân phối xác suất hàm mũ được cho trên hình 2.6. Hình 2.6. Mô hình hàng đợi M/G/1 Trong mô hình này, các khách hàng sẽ đi dần ra khỏi hệ thống khi đang được phục vụ, đến khi nó được phục vụ xong thì hoàn toàn rời khỏi hệ thống. Thời gian lưu trú tổng thể sẽ giảm đi một lượng (1-k), với k là phần còn lại trong hệ thống của khách hàng. Thay vào công thức, ta có: R=S+SQ-(1-k)rS. Tính toán, ta có: Với tính chất của phân phối tổng thể, ta có: , với Cs là giá trị hiệp biến của dãy thời gian đến. Vì thế, ta có: Các hệ thống có phản hồi. Hình 2.5 Hệ thống có phản hồi. Có một số khách hàng sau khi được phục vụ lại tiếp tục yêu cầu loại tài nguyên đó. Điều này thể hiển ở dòng quay lại hệ thống trên hình. Gọi p là xác suất quay lui. Thế thì, ta có tốc độ yêu cầu tới hàng đợi là: . Sử dụng các định nghĩa về lượng khách thăm đã nói đến ở phần trên, ta tính được lượng khách đến thăm server là: và yêu cầu dịch vụ là D=VS. Thế thì, . Mạng các hàng đợi . Các hàng đợi xét ở trên là các hệ rất đơn giản. Thông thường, để mô hình hoá một hệ thống, ta phải dùng phối hợp các loại hàng đợi nói trên. Cụ thể là, cần phân tích hệ thống thành nhiều hệ thống con, mô hình mỗi hệ thống con bằng một loại mạch cụ thể, sau đó ghép chúng lại với nhau. Một hệ thống được mô tả gồm các thành phần sau đây: một đầu vào, một đầu ra, và tiến trình thực hiện một số hành động đối với đầu vào, có thể có phản hồi hoặc không. Căn cứ vào cấu trúc mạng ta có thể chia mạng thành các hàng đợi thành hai loại : Mạng đóng và mạng mở. Mạng đóng không kết nối với thế giới bên ngoài trong khoảng thời gian khảo sát, do đó số khách hàng trong hệ thống là cố định. Mạng mở thì nhận và gửi khách hàng ra bên ngoài trong thời gian khảo sát, do vậy số khách hàng trong hệ thống luôn biến đổi theo thời gian. Mục đích cuối cùng của việc xây dựng và phân tích các mô hình là đưa ra các kết quả đo hiệu năng cho hệ thống được mô hình . Các kết quả đưa ra cóthể ở dạng các bảng số liệu thống kê hoặc tập các đường cong hiệu năng, có rát nhiều phương pháp để xác định các độ đo hiệu năng tuy nhiên mỗi phương pháp sẽ phải có chi phi cụ thể về thời gian tính toán cũng như không gian bộ nhớ. Các kỹ thuật phân tích mô hình đối với mô hình mạng các hàng đợi khá phức tạp. Nói chung các thuật toán tính toán các độ đo hiệu năng cho mạng N khách hàng dựa trên kết quả với N-1 khách hàng trước đó. Cơ sở lí thuyết của các thuật toán này chính là định lí đến do Sevcik và Mitriani đưa ra vào năm 1981 mà ta sẽ giơi thiệu phía sau. ở đây ta giới thiệu hai thuật toán chính được sử dụng để giải các bài toán hàng đợi là thuật toán nhân chập và thuật toán phân tích giá trị trung bình . Các thuật toán này thường sử dụng cho các hệ thống đóng, vì trong các hệ thống này, các kết quả của mỗi hệ thống con có liên quan chặt chẽ đến nhau, vì vậy, tính toán hiệu năng riêng rẽ trong các hệ thống con làm giảm độ chính xác của bài toán. Định lý đến. [ Sevcik và Mitriani 1981] Đối với một hệ thống hàng đợi đóng có N công việc, thời gian lưu trú trung bình trong mỗi hàng đợi là R=S+SQ(N-1). trong đó Q(N-1) là độ dài trung bình hàng đợi này khi có N-1 công việc trong mạch. Xác suất trạng thái của mạng các hàng đợi- khái niệm nghiệm dạng tích PFS Giả sử ta có một mạng xếp hàng gồm M hàng đợi với một số lượng hữu hạn - N khách hàng trong mạng. Với hàng thứ i có phân phối dịch vụ là phần phối mũ với tốc độ dịch vụ là . Đường đi trong mạng là ngẫu nhiên với rij là xác suất chuyển một khách hàng từ hàng đợi i vào hàng đợi j. Khi đó trạng thái của mạng được mô tả bằng véc tơ =(n1,n2,…nM ) trong đó ni là số khách hàng có mặt trong hàng đợi thứ i. Đặt =(0, 0, ….1, 0, …0) (1 ở vị trí thứ i). Trạng thái khi hệ thống có thêm một khách hàng vào hàng đợi i là +, trạng thái hệ thống có một khách hàng ở hàng đợi i rời khỏi hệ thống là -. Cân bằng dòng khách hàng vào và ra khỏi hệ thống ta có phương trình cân bằng toàn cục tại trạng thái là : Gọi thông lượng khách hàng trung bình qua hàng đợi thứ i là thì ở trạng thái cân bằng ta có: thông lượng chuyển qua hàng i là tổng thông lượng của tất cả các dòng khách hàng chuyển từ các hàng j tới hàng i. Ta có phương trình : i=1, 2, ….M. Kết hợp phương trình toàn cục và phương trình thông lượng ta tính toán được xác suất trạng thái cân bằng như sau : Như vậy xác suất trạng thái của mạng được biểu diễn thành tích đơn giản của các hàm tương ứng với các hàng đợi riêng lẻ của mạng. Người ta gọi đây là nghiệm dạng tích PFS . Đối với mạng đóng thì không có trạng thái rỗng nhưng trạng thái 0 ở đây được hiểu là trạng thái mà tất cả các khách hàng tập trung tại một hàng i và đang chuyển tới các hàng rỗng còn lại. Dùng phương trình chuẩn hoá để xác định p(0) ta có : 1= Trong đó G(N)=là một hằng số chuẩn hoá .Do tổng G(N) không phải là tổng vô hạn như đối với mạng xếp hàng mở cho nên ta không thể phân tích thành tích của các . Do đó ta có PFS của mạng xếp hạng như sau Để xác định xác suất trạng thái của mạng hàng đợi ta cần phải xác định hằng số G(N).Tuy nhiên việc tính toán trực tiếp nó lại rất khó do không gian trạng thái của hệ thống quá lớn, do đó cần có các thuật toán tính toán , một trong những thuật toán đó là thuật toán nhân chập Thuật toán nhân chập Tính hằng số chuẩn hoá Như trên ta có với các mạng xếp hàng thì xác suất trạng thái được tính theo công thức sau với G(N)=là hằng số chuẩn hoá đặt ta có G(N)= Gọi g(n,m) là hằng số chuẩn hoá cho n khách hàng đến m hàng đầu tiên của mạng M hàng . Ta có G(N)=g(N,M) và dễ dàng chứng minh được công thức đệ qui như sau: g(m,n)= g(n,1)=f1(n) g(0,m)=1 Dựa vào công thức đệ qui trên ta có thể tính được G(N) Độ phức tạp của thuật toán trên là 2MN vì cần phải thực hiện MN phép cộng và MN phép nhân. Xác định các độ đo hiệu năng từ các hằng số chuẩn Các độ đo hiệu năng có thể tính toán thông qua xác suất trạng thái , tuy nhiên có một cách tính ngấn gọn hơn là tính toán trực tiếp chúng thông qua hằng số chuẩn mà ta có thể sử dụng thuật toán đã trình bày ở trên để tính - Số khách hàng trung bình trong mỗi hàng đợi : - Thông lượng trung bình của mỗi hàng đợi : - Độ hiệu dụng của mỗi hàng đợi Thuật toán phân tích giá trị trung bình Thuật toán phân tích giá trị trung bình được M.Reiser đưa ra. Thuật toán sử dụng một số quan hệ xếp hàng cơ bản để xác định các giá trị trung bình của các thông số hiệu năng mà không sử dụng xác suất trạng thái và hằng số chuẩn. Đây chính là thuật toán được sử dụng trong thư viện PDQ mà ta sẽ giới thiệu ở phần sau. Giả sử mạng đóng với M hàng đợi và N khách hàng lưu thông trong mạng và hàng thứ i có tốc độ phục vụ là .Thời gian lưu trú trung bình của khách hàng tại hàng đợi thứ i chính là thời gian trung bình mà khách hàng phải đợi để được phục vụ xong tại hàng đợi thứ i, nó gồm hai phần là : thời gian được phục vụ tại server và thời gian chờ tất cả khách hàng đứng trước được phục vụ , do đó ta có : trong đó =S là thời gian phục vụ trung bình cho mỗi khách hàng và q là số khách hàng trung bình lúc đến. Theo định lí đến thì ta có trong đó (N) là số khách hàng trung bình trong hàng thứ i khi có N khách hàng trong mạng. áp dụng công thức little cho toàn bộ mạng các hàng đợi : =N áp dụng công thức Little cho hàng đợi i ta có Trên cơ sở trên ta có hai thuật toán tính giá trị trung bình như sau Thuật toán chính xác: Tính thời gian lưu trú trung bình tại mỗi trung tâm dịch vụ đối với một công việc được thêm vào hệ thống tính theo số lượng công việc hiện có trong mỗi hàng đợi ở bước lặp trước đó. Tính toán thông lượng trung bình của toàn bộ hệ thống bằng cách sử dụng qui tắc Little. Tính số lượng công việc trung bình tại mỗi hàng xếp bằng cách áp dụng qui tắc Little vào thông lượng trung bình và thời gian lưu trú trung bình trong mỗi hàng đợi. Thuật toán xấp xỉ. Thuật toán chính xác thực hiện N vòng lặp. Điều này làm cho việc tính toán khá chậm. Vì vậy, khi không cần độ chính xác cao lắm, có thể áp dụng thuật toán xấp xỉ như sau. Công thức này được xấp xỉ nhờ giả thiết rằng độ dài của các hàng đợi trong hệ thống có N công việc là tỉ lệ với N. Cài đặt cụ thể của các thuật toán này có trong bộ công cụ PDQ. Nhận xét về kĩ thuật phân tích giá trị trung bình Đối với kỹ thuật phân tích giá trị trung bình, có các đặc điểm sau đây: Chỉ phân tích hệ thống ở trạng thái tĩnh, không phải là hệ thống thay đổi theo thời gian. Nhân tố duy nhất có ảnh hưởng đến kết quả đầu ra của mô hình là tải trọng tại các hàng đợi. Chiến lược xử lý hàng đợi do thuật toán tự xác. Người sử dụng không có khả năng can thiệp vào điều này. Do đó, không phải mô hình nào cũng có thể phân tích được bằng MVA. Các hệ thống xếp hàng thời gian rời rạc Trong các hệ thống xếp hàng đã đề cập ở trên chúng ta đều giả sử là chúng có thời gian liên tục . Tức là các tiến trình đến và đi có thể xảy ra tại thời điểm bất kì. Tuy nhiên trên thực tế thì các hê thống hoạt động theo một kiểu khác liên quan đến thời gian rời rạc, trong đó các sự kiện chỉ có thể được xuất hiện tại các điểm thời gian tuần hoàn bằng nhau. Để mô hình hoá các hệ thống này ta đi đến mô hình các hàng đợi thời gian rời rạc. Trong mô hình này thời gian được chia thành các khoảng có độ dài cố định gọi là các khe thời gian (slot). Các sự kiện được ép thực hiện trong các khe thời gian.. Ví dụ một hàng đợi thời gian rời rạc nhận vào nhiều nhất một gói tin trong suốt một slot và dịch vụ nhiều nhất một gói tin trong một khe thời gian. Sau đây ta sẽ đi vào khảo sát sơ bộ hệ thống hàng đợi thời gian rời rạc này. Trạng thái của hệ thống và phương trình cân bằng cục bộ Trạng thái của hệ thống như đã định nghĩa trước vẫn là véc tơ biểu diễn số khác hàng trong mõi hàng đợi của hệ thống.Việc chuyển trạng thái hệ thống do xác suất xuất hiện các trạng thái trong mỗi khe thời gian quyết định. Có thể nói rằng trong một khe thời gian thì hệ thống có thể ở một số trạng thái nào đó. Tại cuối mỗi khe thì hệ thống phải trải qua một trong các chuyển tiếp rời khỏi trạng thái sao cho nó có thể tới một trạng thái khác trong khe sau. Một số các chuyển tiếp có thể được chọn và tổng của các xác suất của tất cả các chuyển tiếp phải bằng 1. Trong khi một hệ thống xếp hàng thời gian liên tục Markov phân phối thời gian trải qua một trạng thái bất kì là một biến ngẫu nhiên phân phối mũ thì đối với hệ thống xếp hàng thời gian rời rạc phân phối này là biến ngẫu nhiên rời rạc có phân phối hình học. Gọi pij là xác suất chuyển từ trạng thái i sang trạng thái j của hệ thống, và là xác suất cân bằng của trạng thái j . Khi đó ta có phương trình cân bằng trạng thái cục bộ như sau : và , Ta có thể tính toán được các độ đo hiệu năng theo các xác suất trạng thái đã được tính toán theo phương trình cân bằng. Một số tiến trình đối với thời gian rời rạc Quá trình Bernoull Quá trình đến cơ bản nhất trong hệ thống thời gian liên tục là quá trình Poisson thì quá trình đêns cơ bản nhất của các hệ thống thời gian rời rạc là quá trình Bernoull. Một quá trình đến được mô hình như là quá trình Bernull là quá trình thoã mãn tính chất sau: - Xác suất khách hàng đến mọi khe thời gian là như nhau và là p - Xác suất để không có khách hàng nào đến trong một khe thời gian là 1-p - Xác suất để có lớn hơn 1 khách hàng đến trong một khe thời gian là 0 Qúa trình Bernoull có chung một số đặc tính với quá trình Poisson là : - Là quá trình không nhớ : xác suất khách hàng đến hoặc không đến một khe thời gian là độc lập không phụ thuộc vào các khe trước đó - Có tính chất liên hợp : N quá trình Bernoull hợp lại với nhau cũng là một quá trình Bernoull. Kì vọng của quá trình Bernoull cho ta số khách hàng trung bình trong một khe : phân phối hình học Phân phối hình học là một phân phối thời gian rời rạc tương tự như phân phối mũ trong thời gian liên tục. Giống như phân phối mũ phân phối hình học có tính chất không nhớ - Kì vọng tức số khách hàng trung bình đến hệ thống Đánh giá Mô hình mạng xếp hàng đã trở thành một công cụ quan trọng trong việc thiết kế và phân tích hệ thống phân tán. Điều này là do trên thực tế, trong nhiều ứng dụng, mô hình mạng xếp hàng đã đạt được tính cân bằng giữa độ chính xác và hiệu quả. Về mặt chính xác, kinh nghiệm cho thấy mô hình mạng xếp hàng chỉ có sai số khoảng 5-10% về độ tận dụng và thông lượng và 10-30% về thời gian đáp ứng. Mức chính xác này ổn định và phù hợp với các yêu cầu của nhiều ứng dụng thiết kế và phân tích. Hơn thế, nó nhất quán với độ chính xác của các thành phần khác trong tiến trình phân tích hệ thống máy tính, như là đặc trưng hoá tải trọng… Về mặt hiệu quả, ta thấy rằng mạng xếp hàng có thể được định nghĩa, tham số hoá và đánh giá với chi phí rất thấp. Định nghĩa mạng xếp hàng rất dễ dàng do tính chất tương đương giữa các thành phần của hệ thống với các thuộc tính của hệ máy tính. Tham số hoá dễ dàng bởi chỉ có ít tham số bậc cao có liên quan. Đánh giá dễ dàng vì có nhiều thuật toán đã được phát triển. Tóm lại, mô hình mạng xếp hàng đạt được tính chính xác cao và chi phí thấp. Tuy nhiên, nó không phù hợp để mô hình các hệ thống phức tạp như hệ thống có vùng đệm hữu hạn, trong đó các yêu cầu đến hàng đợi sẽ bị từ chối và bị mất khi vùng đệm của hàng đợi đã đầy, các hệ thống xử lý các khối hoặc lô yêu cầu đồng thời; các hệ có các điểm rẽ nhánh hay điểm hội tụ của các tiến trình; các hệ thống có cân bằng tải, và các hệ thống phải chia sẻ tài nguyên hữu hạn… THƯ VIỆN LẬP TRÌNH GIẢI BÀI TOÁN HÀNG ĐỢI Thư viện PDQ PDQ là gì ? PDQ ( Pretty Damn Quick) là một phần mềm mở , nó được cung cấp dưới dạng mã nguồn viết bằng C, đây không phải là một ứng dụng đóng gói mà chỉ là một thư viện các hàm cho phép giải các bài toán hiệu năng được mô hình hoá bằng mô hình hàng đợi. PDQ sử dụng dụng phương pháp phân tích để giải các mô hình hàng đợi.Với phương pháp này các mô hình được biểu diễn dưới dạng các công thức toán học hoặc các thuật toan được mã hoá, sau đó sẽ xây dựng chương trình sử dụng các hàm thư viện có sẵn để giải mô hình. Trong mô hình PDQ biểu diễn hệ thống máy tính các tài nguyên về phần cứng, phần mềm được biểu diễn bằng các trung tâm dịch vụ của hàng đợi. Các yêu cầu tài nguyên được biều diễn bằng các khách hàng trong hàng đợi có trung tâm dịch vụ tương ứng với tài nguyên được yêu cầu. Các hàng đợi trong mô hình sẽ được xây dựng nhờ các hàm thư viện, như hàm tạo trung tâm dịch vụ, hàm tạo hàng đợi, hàm đặc trưng xây dựng tải... Để giải các bài toán về hiệu năng theo mô hình PDQ trước hết ta xây dựng mô hình bài toán theo mô hình hàng đợi PDQ, sau đó sử dụng hàm PDQ_Solve để giải quyết bài toán, kết quả sẽ trả về các giá trị độ đo hiệu năng của hệ thống như thông lượng, thời gian đáp ứng.... Môi trường lập trình sử dụng PDQ PDQ không phải là một ứng dụng đóng gói buộc phải chạy trên một hệ thống cụ thể nào , nó làm một thư viện mở viết bằng ngôn ngữ C. Các hàm trong PDQ viết bằng C nên tất cả các chương trình sử dụng PDQ đểu dựa