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

h : 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 trên mã nguồn C. Do đó PDQ có thể sử dụng trong bất kì môi trường làm việc nào từ máy microcomputer đến các mainframe. Yêu cầu đối với hệ thống chỉ là có trình dịch C (C compiler). Trình dịch này có thể có sẵn trên môi trường Unix. Hiện này có rất nhiều trình dịch C được viết cho các hệ điều hành khác nhau trên máy tính cá nhân như DOS, Linux, Window, MacOS, Như vậy PDQ có thể ứng dụng được rất rộng rãi trên các môi trường làm việc khác nhau. Giao diện lập trình PDQ .Kiểu dữ liệu: Nodes CEN: trung tâm dịch vụ với số server hữu hạn. Dùng với hàm PDQ_CreateNode() DLY: trung tâm hàng đợi với. Dùng với hàm PDQ_CreateNode() Các quy luật phục vụ FCFS : Đến trước phục vụ trước. Dùng với hàm PDQ_CreateNode() ISRV : Phục vụ vô thời hạn. Dùng với hàm PDQ_CreateNode() LCFS : Đến sau phục vụ trước. Dùng với hàm PDQ_CreateNode() PSHR : Chia sẻ bộ xử lí. Dùng với hàm PDQ_CreateNode() Các tiến trình tải BATCH tải batch-class. Lấy giá trị bằng 1 nếu thời gian nghĩ bằng 0. Được sử dụng trogn mạng hàng đợi đóng. TERM tải terminal-class, lấy giá trị là 1 nếu thời gian nghĩ khác 0. Được áp dụng cho mạng hàng đợi kín. TRANS tải transport-class, được xác định bằng tốc độ đến của khách hàng tới hệ thống. Phương pháp giải APPROX Sử dụng kĩ thuật giải MVA xấp xỉ. Áp dụng cho mạng các hàng đợi đóng. CANON Sử dụng kĩ thuật giải kinh điển. Áp dụng cho mạng các hàng đợi đóng. EXACT Sử dụng kĩ thuật giải MVA chính xác. Áp dụng cho mạng các hàng đợi đóng. Biến toàn cục: Các biến toàn cục sau là bắt buộc cho mỗi mô hình PDQ int nodes Biến đếm số hàng đợi trong mạng hàng đợi. Giá trị xác định nhờ hàm PDQ_CreateNode(). int screams Biến đếm số tiến trình trong hệ thống. Giá trị xác định bởi hàm hàm PDQ_CreateClosed() và hàm PDQ_CreateOpen(). Các biến toàn cục sau có thể sử dụng được trong các mô hình PDQ. int DEBUG Cờ để đảo điều kiện gỡ lỗi PDQ. Mặc định là FALSE. Là tham số cho hàm PDQ_SetDebug(). Char model (MAXBUF) Mảng kí tự gồm tên mẫu. Khởi tạo giá trị bằng hàm PDQ_Int ().MAXBUF =50 Double tolerance Biến điều khiển số lần lặp lại sử dụng trong phương pháp giải xấp xỉ MVA Hơn nữa ,các kiểu sau (các cấu trúc C) biểu diễn các đặc điểm của hàng đợi và các tiến trình. batch_type ,*bt Chứa tên và số lượng tải batch-class job_type,*job Mô tả loại tải : batch, terminal, transaction và loại hàng đợi : đóng, mở node_type,*node Biểu diễn thuộc tính của hàng đợi như độ dài, thời gian thường trú systat_type,*sys Miêu tả thuộc tính hệ thống, ví dụ thời gian đáp ứng terminal_type,*tm Chứa tên và số lượng tải terminal-class transaction_type,*tx Chứa tên và số lượng tải transaction-class. Các hàm thủ tục Tất cả hàm thư viện PDQ đều có tiếp ngữ đầu là PDQ_ . Thư viện “PDQ.lib” bao gồm các hàm sau: PQD_Init( ) khởi tạo các biến trong của mô hình PDQ, hàm này phải được gọi trước một khi sử dụng một hàm PDQ bất kì PDQ_CreateOpen( ) Định nghĩa các đặc trưng của một tải trong mô hình mạng hàng đợi mở PDQ_Create Closed( ) Định nghĩa các đặc trưng của tải trong mô hình mạng hàng đợi đóng PDQ_CreateNode( ) Định nghĩa các các đặc trưng của một hàng đợi trong mạng các hàng đợi đóng hoặc mở PDQ_SetDemand( ) Định nghĩa yêu cầu dịch vụ ở một tải xác định tại một hàng đợi nào đó PDQ_SetVisits () Định nghĩa thời gian phục vụ và số lần đến thăm trung tâm dịch vụ của một tải PDQ_SetWUnit( ) Thay đổi tên đơn vị tải xuất hiện trong báo cáo PDQ PDQ_SetTUnit( ) Thay đổi tên đơn vị thời gian xuất hiện trong báo cáo PDQ PDQ_SetGraph( ) Khởi tạo biến vẽ hình PDQ_PrintXLS( ) Tạo ra 3 file lưu trữ thông lượng, thời gian đáp ưng, dung lượng theo khuôn dạng file dữ liệu XLS PDQ_SetDebug( ) Kiểm tra các biến dữ liệu bên trong của mô hình PDQ PDQ_Solve( ) Giải mô hình PDQ với các tham số cho trước. PDQ_GetResponse( ) Trả về thời gian đáp ứng của hệ thống đối với tải xác định PDQ_GetThruput( ) Trả về thông lượng của hệ thống đối với một tải xác định PDQ_GetUtilization( ) Trả về độ hiệu dụng của một hàng đợi với một tải xác định PDQ_Report() Tạo ra báo cáo chứa kết quả về các thông số hiệu năng của hệ thống. Sau đây ta sẽ lần lượt xem xét các hàm nói trên một cách cụ thể về tham số, cú pháp, chức năng. PDQ_CreateClosed Cú pháp int PDQ_CreateClosed(char *name,int class,float pop,float think); Chức năng PDQ_CreateClosed dùng để định nghĩa đặc tính của tải trong mô hình mạng hàng đợi kín. Hàm này phải được gọi cho từng tải của hệ thống một cách độc lập Biến số: Name Tên được dùng để nhận ra khối lượng công việc class Loại tải có thể là batch hoặc term pop Số lượng yêu cầu hay số khách hàng hoạt động trong mạng hàng đợi đóng think Độ trễ hay thời gian nghĩ , trước khi yêu cầu quay lại mạch hàng đợi Giá trị trả về của hàm PDQ_CreateClosed() trả về số tiến trình tải được tạo ra trong mô hình ở thời điểm hiện tại Sử dụng main() { PDQ_CreateClosed("DB_workers",TERM,57. 4. 31.6); PDQ_CreateClosed("fax_tasks",BATCH, 10.0); } PDQ_CreateNode Cú pháp int PDQ_CreateNode(char *name,int device,int sched); Chức năng PDQ_CreateNode dùng để định nghĩa các đặc trưng cho một hàng đợi trong mô hình mạng các hàng đợi đóng hoặc mở Tham số name Tên hàng đợi device Loại trung tâm dịch vụ, có thể là CEN hoặc DLY. Thông thường là CEN sched Quy luật hàng đợi. Phổ biến nhất là quy luật FCFS Giá trị trả về PDQ_CreateNode trả về số hàng đợi đã được tạo ra trong mô hình Sử dụng main() { PDQ_CreateNode("cpu",CEN,FCFS); PDQ_CreateNode("bus",CEN,ISRV); PDQ_CreateNode("disk",CEN,FCFS) } PDQ_CreateOpen Cú pháp int PDQ_CreateOpen(char *name,float lambda); Chức năng PDQ_CreateOpen ( ) dùng để định nghĩa đặc tính của một tải trong mô hình mạng các hàng đợi mở. Hàm này phải được gọi một cách độc lập cho các tải khác nhau Biến số name Tên của tải lambda Tốc độ đến hàng đợi Trả về PDQ_CreateOpen() trả về số các tiến trình tải trong mô hình Sử dụng main() { PDQ_CreateOpen("IO_Cmds",10.0) } PDQ_GetResponse: Cú pháp float PDQ_GetResponse (int class ,char *wname); Chức năng PDQ_GetResponse () dùng để xác định thời gian đáp ứng của hệ thống đối với một tải xác định Biến số class Loại tải trans,term,batch wname Tên tải Giá trị trả về PDQ_GetResponse () trả về thời gian đáp ứng hệ thống đối với tải xác định Sử dụng main() { float rt; - rt= float PDQ_GetResponse (TRANS,"IO_Cmds"); printf("R(%s),% 3.4 f\n","IO_Cmds",rt); } PDQ_GetThruput Cú pháp float PDQ_GetThruput(int class,char *wname); Chức năng PDQ_GetThruput() dùng để xác định thông lượng của hệ thống đối với một tải xác định Biến số class Loại tải : trans, term hay batch wname Tên tải Giá trị trả về PDQ_GetThruput() trả về thông lượng của hệ với tải xác định Sử dụng main() { float tp; tp= float PDQ_GetThruput(TRANS,"IO_Cmds"); printf ("R(%s):%3.4 f\n","IO_Cmds",tp); } PDQ_GetUtilization Cú pháp float PDQ_GetUtilization (char *device,char *work ); Chức năng PDQ_GetUtilization() dùng để xác định độ hiệu dụng của mỗi hàng đợi với tải cho trước. Hàm này chỉ nên gọi sau khi mô hình PDQ đã được giải. Biến số device tên của hàng đợi work tên của tải Giá trị trả về Độ hiệu dụng với giá trị thập phân nằm trong khoảng (0.1 .. 1.0) Sử dụng main() { float ut; PDQ_solve(); ut= PDQ_GetUtilization("Disk","IO_Cmds"); printf ("R(%s):%3.4f\n","IO_Cmds",ut); } PDQ_Init Cú pháp void PDQ_Init(char *name); Chức năng PDQ_Init khởi tạo toàn bộ các biến trong PDQ. Hàm này phải gọi trước khi gọi một hàm bất kì trong PDQ. Khi hàm này được gọi tất cả các biến trong PDQ được khởi tạo lại, có thể gọi lại hàm nhiều lần trong một mô hình PDQ. Biến số name Tên của mô hình sẽ xuất hiện trong báo cáo kết quả, tên này phải không vượt quá 24 kí tự Giá trị trả về Hàm này không có giá trị trả về. Sử dụng main() { PDQ_Init("File Server"); PDQ_Solve(); PDQ_Report(); PDQ_Init("Client Workstation"); PDQ_Solve(); PDQ_Report(); } PDQ_Report Cú pháp void PDQ_Report(); Chức năng PDQ_Report() tạo ra báo cáo với khuôn dạng xác định, trong đó chứa kết quả của việc giải mô hình bao gồm số lượng hàng đợi, số tiến trình trong hệ thống, các độ đo hiệu năng mức hệ thống, độ đo hiệu năng của các hàng đợi. Có thể có một trường chú thích thích hợp để kiểm tra sự biến đổi thông số đầu vào khi chạy trong mô hình. Để thêm chú thích vào báo cáo, chỉ cần tạo hoặc thay đổi file comments.pdq Giá trị trả về Hàm này không có giá trị trả về. Sử dụng main() { PDQ_Init("Super Dooper Server"); PDQ_Solve(); PDQ_Report(); } PDQ_SetDebug Cú pháp void PDQ_SetDebug(int flag); Chức năng PDQ_SetDebug() dùng để cho phép chuẩn đoán đầu ra của các biến trong mô hình hoặc trong các thủ tục sử dụng trong lời giải của mô hình Biến số flag Đặt là True hay False để đảo điều kiện gỡ lỗi Giá trị trả về Không có giá trị trả về, đầu ra được ghi vào file debug.log Sử dụng main() { void PDQ_SetDebug(TRUE); nodes =PDQ_CreateNode("Server",CEN,FCFS); stream=PDQ_CreateOpen ("work",3.5); PDQ_SetDemand ("Server","work",2.2); PDQ_SetDebug(FALSE); } /*main*/ Thủ tục sau cho đầu ra trong file debug.log DEBUG:PDQ_CreateNode Entering Node(0):CEN FCFS "server" Exiting Stream(0):TRANS "work",Lamda:0.5 DEBUG:PDQ_SetDemand() Entering DEBUG:getnode_index() Entering node:”server” index: 0 Exting DEBUG:getjob_index() Entering stream:”work” index:0 Exting DEBUG:PDQ_SetDemand() Exiting PDQ_SetDemand Cú pháp Void PDQ_SetDemand(char*nodename,char*work_name,float time); Chức năng PDQ_SetDemand dùng để định nghĩa yêu cầu phục vụ cho một tải đã chỉ ra. Tên của hàng đợi và tải phải tồn tại trong hệ thống từ trước. Hàm này phải được gọi cho mỗi tiến trình trước khi nhập vào hàng đợi Biến số nodename Tên hàng đợi workname Tên tải time Yêu cầu dịch vụ (trong các đơn vị thời gian) do tải yêu cầu tại hàng đợi Giá trị trả về Hàm này không có giá trị trả về. Sử dụng main() { PDQ_CreateClosed("DB_workers",TERM,57.4, 31.6); PDQ_CreateClosed("fax_tasks",BATCH, 10.0) PDQ_CreateNode("cpu",CEN,FCFS); PDQ_SetDemand("cpu","DB_Worker",0.130); PDQ_SetDemand("cpu","fax_Report",3.122); } PDQ_SetUnit Cú pháp void PDQ_SetUnit(char *unitname); Chức năng PDQ_SetUnit() thay đổi tên của đơn vị thời gian xuất hiện trong báo cáo PDQ. Đơn vị mặc định “s” (giây) Biến số unitname Tên của đơn vị Sử dụng main() { PDQ_SetUnit ("Minutes”) } PDQ_SetVisits Cú pháp Void PDQ_SetVisits(char*nodename,char*work_name,float visits,float service) Chức năng PDQ_SetVisits dùng để định nghĩa yêu cầu phục vụ của một tải về thời gian phục vụ và só lần tới trung tâm dịch vụ của tải. Tên của tải và hàng đợi phải tồn tại trong hệ thống. Hàm này phải được gọi cho mỗi tiến trình trước khi đi và một hàng đợi Biến số nodename Tên của hàng đợi workname Tên của tải visits Số lần tới hàng đợi của tiến trình tải. Số này là không có thứ nguyên service Thời gian phục vụ tiến trình yêu cầu tại hàng đợi Giá trị trả về Hàm này không có giá trị trả về Sử dụng main() { PDQ_CreateClosed("DB_workers",TERM,57.4 , 31.6); PDQ_CreateNode("cpu",CEN,FCFS); PDQ_SetVisits("cpu","DB_Worker”,10.0,0.013); } PDQ_SetWUnit Cú pháp void PDQ_SetWUnit(char *unitname); Chức năng PDQ_SetWUnit() thay đổi tên của công việc xuất hiện trong PDQ _Report Biến số unitname Tên của đơn vị Giá trị trả về Hàm này không có giá trị trả về. Sử dụng main() { PDQ_SetWUnit("I/O_Regs") } PDQ_Solve Cú pháp int PDQ_Solve (int method); Chức năng PDQ_Solve() được gọi sau khi mô hình PDQ được tạo. Hàm này sẽ giải mô hình theo giải thuật theo tham số được đưa ra Giá trị trả về Hàm này không có giá trị trả về. Sử dụng main() { PDQ_Solve(APPROX); PDQ_Report(); } Mẫu của một chương trình dựa theo mô hình PDQ - Khai báo các header file. #include #include #include - Khai báo các biến tổng thể bắt buộc node, stream. Các biến nàycho phép các thủ tục PDQ bên trong giữ trạng thái toàn cục của mạng các hàng đợi đã tạo trong PDQ extern int nodes,stream - Khai báo các biến xác định các tham số của mô hình. float inter_arriv_time=0.5; float service_time =1.0; - Khởi tạo mô hình PDQ với tên mô hình và các đơn vị đo sẽ xuất hiện trong báo cáo kết quả PDQ_Init("Minimal Model"); PDQ_SetWUnit("Compltns"); PDQ_SetUnit("time"); - Định nghĩa các hàng đợi trong mạng hàng đợi và các tiến trình sẽ yêu cầu dịch vụ tại các hàng đợi đó nodes=PDQ_CreateNode("server", CEN,FCFS); - Tạo hệ thống hàng đợi và đưa ra các tham số cho mạng đó. stream= PDQ_CreateNode("work",inter_arriv_time); - Định nghĩa các yêu cầu dịch vụ của các tiến trình đối với các hàng đợi PDQ_SetDemand(“server",”work”,service_time); - Giải mô hình PDQ_Solve(CANON); - Hiển thị kết quả PDQ_Report(); Báo cáo kết quả của một chương trình (PDQ_Report) - Thông tin về mô hình : tên, ngày cập nhật, version. *** ******* Pretty Damn Quick REPORT ******** ******* *** of : Sat Oct 20 14:52:25 2001 *** **** ******* *** for: M/M/1 *** **** ******* *** Rel: PDQ Analyzer v2.5 082401 ******* *************************************************** ** *************************************************** ** ****** Comments ********* - Tóm tắt tất cả các tham số đầu vào của mô hình ****** ******* ******* PDQ Model INPUTS ******************************* Node Sched Resource Workload Class Demand ---- ----- -------- -------- ----- ------ CEN FCFS Server Customers TRANS 1.0000 Queueing Circuit Totals: Generators: 0.00 Streams : 1 Nodes : 1 WORKLOAD Parameters Srcs per Sec Demand -------- ------- ------ Customers 0.5000 1.0000 - Kết quả đầu ra. *************************************** ****** PDQ Model OUTPUTS ******** *************************************** Solution Method: CANON ****** SYSTEM Performance ******* Metric Value Unit --------------- ---- ---- Workload: "Customers" Mean Throughput 0.5000 Customer/Minute Response Time 2.0000 Minute Bounds Analysis: Max Throughput 1.0000 Customer/Minute ****** RESOURCE Performance ******* Metric Resource Work Value Unit --------- ------ ---- ----- ---- Throughput Server Customers 0.5000 Customer/Minute Utilization Server Customers 50.0000 Percent Queue Length Server Customers 1.0000 Customer Residence Time Server Customers 2.0000 Minute Ví dụ cho hàng đợi M/M/1 Trên đây ta vừa xem xét các bước để tiến hành xây dụng một chương trình theo mô hình PDQ, sau đây ta sẽ áp dụng nó cho một trường hợp cụ thể, xây dựng mô hình cho hàng đợi M/M/1. Input Tốc độ đến hàng đợi l= 0.5 khach/giay Thời gian phục vụ S=0.1 (s). Output Thời gian thường trú của mỗi khách hàng trong hệ thống R==2(s) Độ hiệu dụng của server U=lS=0.5=50% Độ dài hàng đợi Q=lR=1 (khachang) Thời gian chờ phục vụ của khách hàng trong hàng đợi W=R-U=1.5(s) Mô hình PDQ viết bằng C #include #include #include #include "../lib/PDQ_Lib.h" main() { // PDQ global variables extern int nodes; extern int streams; // Model specific variables double arrival_rate = 0.5; double service_time = 1.0; // Initialize PDQ and the model a name PDQ_Init("M/M/1"); // Change metric labels PDQ_SetWUnit("Customer"); PDQ_SetTUnit("Minute"); // Create the M/M/1 queue nodes = PDQ_CreateNode("Server", CEN, FCFS); // Define the workload and circuit type streams=PDQ_CreateOpen("Customers",arrival_rate); // Define service demand due to workload on the queueing center PDQ_SetDemand("Server","Customers",service_time); // Solve the model PDQ_Solve(CANON); // Generate a standard report PDQ_Report(); } Phát triển thêm các thủ tục vào thư viện PDQ. Trong phần này em sẽ xây dựng thêm các thủ tục để giải một số mô hình hàng đợi cơ bản như sau: PDQ_Simark( ) hàng đợi Markov đơn giản M/M/1. PDQ_Pmark( ) Các hàng đợi song song q(M/M/1) PDQ_Multser( ) Các hàng đợi nhiều trạm dịch vụ M/M/m PDQ_Infcus( ) Các hàng đợi có dân số hạn chế. Thủ tục giải mô hình hàng đợi Markov đơn giản Input Tốc độ đến hàng đợi l Thời gian phục vụ S Output Thời gian thường trú của mỗi khách hàng trong hệ thống R= Độ hiệu dụng của server U=lS Độ dài hàng đợi Q=lR Thời gian chờ phục vụ của khách hàng trong hàng đợi W=R-U. Thủ tục giải mô hình các hàng đợi Markov đơn giản song song Input Thời gian phục vụ S Tốc độ đến hàng đợi l Số các server phục vụ q Output Độ hiệu dụng của server U=lS Độ hiệu dụng của từng server r= U/q Thời gian thường trú của mỗi khách hàng trong hệ thống R= Thời gian chờ phục vụ của khách hàng trong hàng đợi W=R-S Thủ tục giải hàng đợi nhiều serve song song PDQ_Mutilser() Input Thời gian phục vụ S Tốc độ đến hàng đợi l Số các server phục vụ m Output Độ hiệu dụng của server U=lS Độ hiệu dụng của từng server r= U/m Thời gian thường trú của mỗi khách hàng trong hệ thống R= Thời gian chờ phục vụ của khách hàng trong hàng đợi W=R-S Độ dài hàng đợi Đánh giá về thư viện lập trình PDQ PDQ là một thư viện các hàm có thể sử dụng để giải bài toán hiệu năng dựa trên mô hình hàng đợi. PDQ được cung cấp dưới mã nguồn viết trên ngôn ngữ C. Đây là thư viện có thể áp dụng một cách rộng rãi trên các hệ thống. Việc sử dụng các hàm trong thư viện này khá đơn giản. Mặt khác PDQ là một thư viện mở, người lập trình có thể thêm vào thư viện này các hàm cần thiết để thuận lợi hơn cho mục đích giải mô hình hàng đợi. Để khai thác thư viện PDQ áp dụng cho bài toán tính toán hiệu năng của WebServer trên đây em đã xây dựng thêm một số thủ tục thêm vào thư viện Tuy nhiên trước khi áp dụng các hàm này yêu cầu người lập trình phải thiết lập được mô hình hàng đợi thích hợp. Để chương trình có thể giao tiếp trực quan hơn với người dùng thì cần yêu cầu xây dựng giao diện người dùng cho báo cáo kết quả. ĐÁNH GIÁ HIỆU NĂNG CỦA WEBSERVER Tổng quan chung về WebServer Word Wide Web là gì? World Wide Web ( Web ) là một dịch vụ hay còn gọi là một công cụ trên Internet ra đời gần đây nhất nhưng phát triển nhanh nhất hiện nay. Nó cung cấp một giao diện thân thiện với người dùng, dễ sử dụng, thuận lợi và đơn giản để tìm kiếm thông tin. Thực chất Web không phải là một hệ thống cụ thể với tên gọi như trên mà là một tập hợp các công cụ tiện ích và siêu giao diện ( meta-Interace) giúp người sử dụng có thể tự tạo ra các " siêu văn bản " và cung cấp cho những người dùng khác trên Internet. Nguyên tắc hoạt động của Web Nguyên tắc : Web dựa trên một kỹ thuật biểu diễn thông tin Siêu văn bản (hypertext), trong đó các từ được chọn trong văn bản có thể được ''mở rộng" bất kỳ lúc nào. Sự mở rộng ở đây có thể được hiểu là chúng có các liên kết (links) tới các tài liệu khác (có thể là văn bản, hình ảnh, âm thanh hoặc hỗn hợp ). Siêu văn bản là một loại văn bản thông thường nhưng lại chứa một hay nhiều tham chiếu tới các văn bản khác. Như đã nói ở trên, Web không phải là một hệ thống cụ thể mà là một tập hợp các công cụ tiện ích và siêu giao diện ( meta-Interace) giúp người sử dụng có thể tự tạo ra các " siêu văn bản " và cung cấp cho ngững người dùng khác trên Internet và người ta gọi đó là Công nghệ Web. Công nghệ Web cho phép xử lí các trang dữ liệu đa phương tiện và truy nhập trên các mạng diện rộng. Thực chất Web là hội tụ của Internet, siêu văn bản và thông tin đa phương tiện. URL (Union Resource Locator ) : Để thực hiện việc truy nhập, liên kết các tài nguyên khác nhau theo kỹ thuật Siêu văn bản, Web sử dụng khái niệm URL. Đây chính là một dạng tên để định danh duy nhất cho một tài liệu hoặc một dịch vụ trong Web. Cấu trúc của một URL : Protocol://host.domain/derictory/filename Ví dụ : Protocol có thể là : + Ftp file ở trong một Fpt Server. Ví dụ : Ftp://ftp.microsoft.com/file.doc + Mailto Địa chỉ E-mail cá nhân. Ví dụ : someone@microsoft.com + File Truyền file + HTTP (Hypertext Transfer Protocol) URL được sử dụng trong tất cả các dịch vụ thông tin của Internet và đặc biệt là trong Web. Mỗi trang Web có một URL duy nhất để xác định nó, thông qua URL có thể truy cập tới bất kì tài nguyên của bất kì dịch vụ nào trên Internet. Hoạt động của Web: INTERNET Server(2) Client(1) Web browser Web server Server(3) 1. Bộ duyệt trên PC (web browser) gửi địa chỉ URL đến máy chủ nội bộ 2. Nếu trang Web có địa chỉ máy chủ là chính máy chủ nội bộ đó thì trang Web đó được máy chủ nội bộ gửi đến cho PC đó. 3. Nếu trang Web có địa chỉ máy chủ là một máy chủ ở xa thì yêu cầu sẽ được chuyển tới máy chủ ở xa. Trang Web cần thiết sẽ được máy chủ ở xa gửi lại cho máy chủ nội bộ, rồi gửi cho máy PC yêu cầu. Giao thức http Web browser và Web Server giao tiếp với nhau thông qua giao thức HTTP (HyperText Transfer Protocol) Giao thức này hỗ trợ truyền và trao đổi nhiều thông tin khác nhau như văn bản, hình ảnh, âm thanh, …theo các chuẩn MIME sao cho thông tin khi truyền đi sẽ được nhận một cách đúng đắn. Khái niệm về WebServer Web Server là máy chủ trong đó chứa thông tin dưới dạng trang Web. Các Web Server được nối với nhau trên Internet, mỗi Server có địa chỉ riêng và bắt đầu bằng Thành phần chủ chốt của Web Server là phần mềm. Phần mềm WebServer là một phần mềm phục vụ. Khi được thi hành nó nạp vào bộ nhớ và đợi các yêu cầu từ nơi khác đến. Các yêu cầu đó có thể đến từ một người sử dụng phần mềm Web browser hoặc cũng có thể từ một WebServer khác. Các đối tượng đưa ra yêu cầu được gọi là Client, các yêu cầu đối với một WebServer thường là đòi hỏi về dữ liệu hay thông tin nào đó. Khi nhận yêu cầu WebServer phân tích yêu cầu để xác định xem tư liệu mà khách hàng muốn là gì. Sau đó nó tìm lấy tư liệu và gửi lại cho Client. WebServer cũng như các máy phục vụ thông tin trên Internet khác được nối với nhau, điều này đòi hỏi các máy tính phải có phần mềm giao tiếp với mạng và phần cứng thích hợp. Hầu hết các giao thức đều chạy trên họ giao thức TCP/IP và sử dụng giao thức truyền thông TCP. Hoạt động của WebServer WebServer thực chất là phần mềm phục vụ các yêu cầu trang Web. Khi được thực hiện, đầu tiên WebServer thực hiện phân tích tham số dòng lệnh để xác định cổng truyền thông, nơi đặt các tệp lệnh cấu hình. Nếu tham số dòng lệnh không có thì, thì WebServer sẽ dùng cổng ngầm định là cổng được khai báo trong tệp cấu hình httppd.conf và coi các tệp cấu hình nằm trong thư mục ngầm định. Sau đó nó tiến hành đọc tệp cấu hình và phân tích các tệp này để xác định các thông số cho quá trình hoạt động. Các thông số này là số hiệu cổng truyền, định danh người dùng, thư mục gốc của WebServer … Sau khi phân tích các thông số cấu hình, WebServer sẽ chờ yêu cầu từ phía Client tại cổng đã xác định. Khi có yêu cầu gửi tới cổng, WebServer nhận yêu cầu, phân tích yêu cầu để xác định tư liệu mà khách hàng đòi hỏi . Khi xác định được nội dung yêu cầu, nó sẽ tìm tư liệu được yêu cầu và một mặt gửi cho Web browser , thông qua giao thức HTTP, mặt khác tài liệu đó được lưu trữ vào trong cache WebServer nhận tư liệu hiển thị nó lên màn hình và cắt kết nối với WebServer. Các tư liệu trước khi gửi tới Client đựoc lưu trữ vào Cache. Khi nhận được yêu cầu về tư liệu nào đó WebServer đầu tiên luôn tìm trong cache. Hiệu năng của các WebServer Các tiêu chuẩn đánh giá Web Server Web Server là trung tâm hệ thống intranet , việc chọn giải pháp cho Web Serverlà rất cần thiết và có ảnh hưởng lớn tới việc phát triển các ứng dụng nghiệp vụ. Do đó nhận thức rõ được vấn đề này có tác dụng lớn đến hiệu quả đầu tư và chi phí cho công nghệ Intranet. Để đánh giá một Web Server ta thường có một số tiêu chuẩn chính như sau: Hiệu năng Bảo mật : Thông qua địa chỉ IP, tên máy chủ của mạng con, thư mục ... Web Oracle cung cấp phương án bảo mật thông tin theo tên người sử dụng và khoá mã được mã hoá hoàn toàn trong quá trình truyền thông trên mạng. Truy nhập và tích hợp CSDL : Hầu hết các Web Server đều sử dụng giao diện CGI, một số khác thì dùng giao diện lập trình ứng dụng (API) hoặc ngôn ngữ hỏi đáp có cấu trúc SQL. Quản lí và quản trị Web Server : Đặc tính quan trọng của tiêu chuẩn này là khả năng quản trị từ xa, giao diện đồ họa và điều khiển cấu hình của máy chủ Đánh giá hiệu năng của WebServer về mặt thời gian đáp ứng. Một phiên truyền tin theo giao thức HTTP thực hiện các bước sau: Bước Client Server 1 Yêu cầu kết nối 2 Trả lời chấp nhận kết nối 3 Báo nhận+ yêu cầu dữ liệu1 Yêu cầu dữ liệu 2 Báo nhận(1) Yêu cầu dữ liệu 3 4 Báo nhận(2,3) + dữ liệu 1 Dữ liệu 2 Báo nhận dữ liệu dữ liệu 3 dữ liệu 4 + tín hiệu cắt kết nối Báo nhận dữ liệu 5 Tín hiệu cắt kết nối B¸o nhËn c¾t kÕt nèi. B­íc 1 trong giao thøc HTTP lµ thñ tôc b¾t tay gi÷a client vµ server x¸c ®Þnh c¸c tham sè ®Ó ®Ó truyÒn tin. D÷ liÖu ®­îc truyÒn trªn ®­êng truyÒn theo giao thøc TCP, theo giao thøc nµy th× d÷ liÖu truyÒn ®­îc ph©n ®o¹n thµnh c¸c gãi tin cã kÝch th­íc nhÊt ®Þnh, kÝch th­íc lín nhÊt cña gãi tin gäi lµ MSS. Giao thøc truyªn lµ giao thøc kh«ng ®ång bé, ng­êi göi ng­êi göi sÏ göi c¸c gãi tin tíi mét bufer ë bªn nhËn vµ bªn nhËn sÏ lÊy c¸c gãi tin tõ bufer ®Ó xö lÝ. KÝch th­íc cña buffer gäi lµ kÝch th­íc cöa sæ (Window size). KÝch th­íc cöa sè sÏ ¶nh h­ëng ®Õn tèc ®é truyÒn c¸c gãi tin dùa vµo kÝch th­íc cöa sè ta tÝnh to¸n tèc ®é truyÒn gãi tin sao cho kh«ng xÈy ra t¾c nghÏn. Tèc ®é truyÒn tèi ­u lµ tèc ®é mµ sè gãi tin mµ bªn nhËn nhËn ®­îc b»ng sè gãi tin mµ bªn göi göi ®i, TCP ®­a ra tèc ®é truyÒn tèi ­u kÝ hiÖu lµ Slow Start. Khi tèc ®é truyÒn nhá h¬n gi¸ trÞ Slow Start bªn nhËn sÏ tÝnh ®­îc kÝch th­íc cöa sæ kh¸c chøa c¸c gãi tin ch­a ®­îc b¸o nhËn gäi lµ Congestion Window. Khi mét kÕt nèi ®­îc thµnh lËp, ng­êi göi ®­îc phÐp göi thªm mét gãi tin khi ch­a cã b¸o nhËn, khi mét gãi tin ®­îc b¸o nhËn th× Congestion Window t¨ng 1. Ng­îc l¹i nÕu gãi tin bÞ mÊt hoÆc time out th× cña sæ nµy gi¶m 1 Thêi gian tån t¹i cña kÕt nèi th­êng lín h¬n thêi gian yªu cÇu trao ®æi ,tuy nhiªn thêi gian kÕt nèi cña HTTP lµ rÊt ng¾n do ®ã gi¸ trÞ Slow Start cã ¶nh h­ëng rÊt lín tíi hiÖu n¨ng cña client vµ server. V× c¸c header cña HTTP th­êng lín h¬n MSS nªn client ph¶i ph©n ®o¹n nã thµnh hai gãi tin, ë b­íc 2, cöa sè Congestion Window ®­îc khëi t¹o lµ 1.Nh­ vËy tån t¹i thêi gian trÔ ®Ó gãi tin tr­íc ®­îc b¸o nhËn tr­íc khi gãi tin tiÕp theo ®­îc göi ®i. Thêi gian trÔ nµy ®­îc kÝ hiÖu lµ RTD (Ruond-Trip-Delay) Do kÝch th­íc cña mét trang Web th­êng l¬n h¬n gi¸ trÞ MSS nªn lu«n tån t¹i gi¸ trÞ RTD do d÷ liÖu ph¶i ph©n ®o¹n ®Ó cã thÓ truyÒn theo giao thøc TCP. Ta cã thÓ tÝnh to¸n ®­îc thêi gian ®¸p øng cña server bao gåm Thêi gian göi yªu cÇu Thêi gian trÔ RTD Thêi gian xö lÝ cña server Thêi gan ®Ó göi ®¸p øng Thêi gian ®¸p øng chung b»ng tæng tÊt c¶ c¸c thêi gian trªn. §¸nh gi¸ hiÖu n¨ng cña WebServer vÒ mÆt dung l­îng. Mét vÊn ®Ò lín ®Æt ra ®èi víi viÖc qu¶n lÝ c¸c Web lµ cÊu h×nh cña WebServer. C¸c yÕu tè vÒ cÊu h×nh nh­ : hÖ thèng file, bé nhí, dung l­îng l­u tr÷, cache… cÇn ph¶i thay ®æi liªn tôc sao cho cã thÓ ®¸p øng ®­îc yÒu cÇu cña client, víi sè l­îng client ngµy cµng t¨ng. MÆt kh¸c sù më réng vÒ cÊu h×nh nµy ph¶i tÝnh to¸n dùa trªn gi¸ c¶ phÇn cøng vµ yªu cÇu hiÖu n¨ng. C¸c yÕu chÝnh ®Ó ®¸nh gi¸ dung l­îng cña c¸c WebServer bao gåm : Ph­¬ng ph¸p cÊt d÷ file (caching file) Ho¹t ®éng cña hÖ thèng file (file system activity) Ph©n chia c¸c tiÕn tr×nh phô (forking slaves) Sö dông bé nhí (Memory consumption) Ho¹t ®éng cña c¸c tiÕn tr×nh (Process activity) Ho¹t ®éng cña m¹ng (network activity) Thêi gian ®¸p øng (response-time characteristics) TÝnh co d·n cña server-host Th«ng l­îng CÊu h×nh cña Server Dung l­îng cña Proxy/gateway. §Ó ­íc tÝnh ®­îc dung l­îng phï hîp cho WebServer th× ta cã thÓ dùa trªn sè liÖu trong c¸c logs file cÊu h×nh cña WebServer. XÂY DỰNG CHƯƠNG TRÌNH ĐÁNH GIÁ THỜI GIAN ĐÁP ỨNG CỦA WEBSERVER SỬ DỤNG MÔ HÌNH HÀNG ĐỢI VÀ THƯ VIỆN PDQ Mô hình hàng đợi PDQ để giải bài toán tính thời gian đáp ứng và thông lượng của WebServer. client Master m Slaves Các yêu cầu của Client được đưa vào hàng đợi chính, sau khi xử lí để xác định địa chỉ của WebServer được yêu cầu thông qua URL, các yêu cầu được gửi tới các hàng đợi của các WebServer đó. Sau khi sử lí yêu cầu các Slave sẽ gửi thông tin được yêu cầu về các Client. Ta mô hình hoá hệ thống bằng mạng hàng đợi đóng với số khách hàng (Clients) cố định N. Mạng bao gồm một hàng đợi đơn M/M/1 biểu diễn tiến trình chính và m hàng đợi đơn M/M/1 diễn song song biểu diễn m tiến trình phụ như hình vẽ. Từ mô hình hàng đợi đã nêu ta sẽ xây dựng chương trình sử dụng các hàm của thư viện PDQ để xây dựng mạng hàng đợi và xác định các thông số cho hàng đợi - Khởi tạo mô hình PDQ_Init("HTTPd_Server") - Định nghĩa đặc trưng tải cho hệ thống streams = PDQ_CreateClosed("homepage", TERM, 1.0 * pop, 0.0) Các tải tạo ra thuộc lớp terminal, thời gian nghĩ là 0 (s), pop là số client trong hệ thống - Tạo hàng đợi cho tiên trình chính nodes = PDQ_CreateNode("master", CEN, FCFS); - Tạo các hàng đợi cho tiến trình phụ : for (s = 0; s < servers; s++) { nodes = PDQ_CreateNode(slave[s], CEN, FCFS); } - Định nghĩa yêu cầu dịch vụ cho sever của hàng đợi chính PDQ_SetDemand("master", work[w], Smaster); Thời gian dịch vụ yêu cầu là Smaster. - Định nghĩa yêu cầu dịch vụ ở cho các server của hàng đợi phụ : for (s = 0; s < servers; s++) { PDQ_SetDemand(slave[s], work[w], time[w] / servers) } - Giải mô hình theo kĩ thuật phân tích giá trị trung bình chính xác PDQ_Solve(EXACT); - Lấy thông lượng của hệ thống : PDQ_GetThruput(TERM, "homepage") -Lấy thời gian đáp ứng của hệ thống : PDQ_GetResponse(TERM, "homepage") Lập chương trình trên ngôn ngữ Visual C. Mã nguồn chương trình của thư viện PDQ được viết bằng ngôn ngữ C chuẩn, vì vậy để tiện trong việc sử dụng thư viện này ta chọn ngôn ngữ Visual C để cài đặt chương trình minh hoạ. Để sử dụng thư viện PDQ các file mã nguồn của thư viện PDQ được sử dụng thư viện tĩnh . Kết quả của việc tạo thư viện tĩnh này ta được file thư viện PDQ_Lib.lib. Trong các ứng dụng trên VC ta để truy cập các hàm, biến… của thư viện PDQ ta chỉ cần sử dụng file thư viện PDQ_Lib.lib và file tiêu đề PDQ_Lib. h . Dao diện chính của chương trình như sau : Tham số đầu vào của chương trình do người dùng nhập vào (INPUT DATA) bao gồm : - Số server : chỉ định số số serve slave được dùng ( chính là số hàng đợi song song) - Thời gian dịch vụ Smaster : Thời gian dịch vụ yêu cầu ở server chính - Thời gian dịch vụ Slave : Thời gian dịch vụ cho mỗi client ở serve slave Dữ liệu ra của chương trình là thông lượng và thời gian đáp ứng của hệ thống tương ứng với các tham số đầu với số client khác nhau. Dữ liệu ra được lưu trong file "PDQ.dat" để có thể lưu lại khi cấn sử dụng và được hiển thị trên màn hình. Mã nguồn chương trình như sau : extern int nodes, streams; extern job_type *job; extern double getjob_pop(int c); extern int getjob_index(char *wname); extern double PDQ_GetResponse(int should_be_class, char *wname); extern double PDQ_GetThruput(int should_be_class, char *wname); extern double PDQ_GetUtilization(char *device, char *work, int should_be_class); int pop, servers ; int s, w; FILE *fp; static char *slave[] = { "slave0", "slave1", "slave2", "slave3", "slave4", "slave5", "slave6", "slave7", "slave8", "slave9", "slave10", "slave11", "slave12", "slave13", "slave14", "slave15" }; w = HOMEPG; fp=fopen("PQD.dat","a"); #ifdef PREFORK fprintf(fp,"Pre_fork model \"%s\" Load (m = %d)\n", w == STRESS ? work[STRESS] : work[HOMEPG], servers); #else fprintf(fp,"Forking Model under \"%s\" Load \n",w == STRESS ? work[STRESS] : work[HOMEPG]); #endif fprintf(fp,"N\tX\tR\n"); fclose(fp); for (pop = 1; pop <= 10; pop++) { PDQ_Init("HTTPd_Server"); streams = PDQ_CreateClose(work[w], TERM, 1.0 * pop, 0.0); nodes = PDQ_CreateNode("master", CEN, FCFS); #ifdef PREFORK for (s = 0; s < servers; s++) { nodes = PDQ_CreateNode(slave[s], CEN, FCFS); } PDQ_SetDemand("master", work[w], 0.0109); for (s = 0; s < servers; s++) { PDQ_SetDemand(slave[s], work[w], time[w] / servers); } #else /* FORKING */ nodes = PDQ_CreateNode("forks", CEN, ISRV); PDQ_SetDemand("master", work[w], 0.0165); PDQ_SetDemand("forks", work[w], time[w]); #endif PDQ_Solve(EXACT); fp=fopen("PDQ.dat","a"); fprintf(fp,"%3.2f\t%3.4f\t%3.4f\n", getjob_pop(getjob_index(work[w])), PDQ_GetThruput(TERM, work[w]), PDQ_GetResponse(TERM, work[w])); fclose(fp); } char ch; m_xau=""; if ((fp=fopen("PDQ.dat","rb"))==NULL) { MessageBox("Khong mo duoc file?"); return ; } while (!feof(fp)) { ch=getc(fp); m_xau.Insert(m_xau.GetLength(),ch); } m_edit.SetWindowText(m_xau); fclose(fp); } Phân tích kết quả thử nghiệm. Trong mô hình đã nêu ta có một tiến trình chính (tương ứng với hàng đợi đơn) và m tiến trình phụ (tương ứng với m hàng đợi song song) trong ứng dụng thử nghiệm ta chỉ qui định số server slave lớn nhất là 16. Thời gian dịch vụ ở tiến trình chính là Smaster, thời gian dịch vụ Sslave do người dùng nhập vào. Nếu thời gian dịch vụ ở tiến trình chính lớn hơn tiến trình phụ Smaster>Sslave thì xảy ra tắc nghẽn ở tiến trình chính và tiến trình phụ sẽ không có hiệu quả. Do đó ta giả sử thời gian dịch vụ ở tiến trình chính bé hơn ở tiến trình phụ Smaster <Sslave. Với số server slave là m=2, Smaster=0,0109 (s), Sslave=0,0044(s). Ta có kết quả thời gian đáp ứng và thông lượng của hệ thống với số client khác nhau như sau : N X R 1.00 24.4499 0.0409 2.00 44.1775 0.0453 3.00 59.6092 0.0503 4.00 71.1625 0.0562 5.00 79.3343 0.0630 6.00 84.7335 0.0708 7.00 88.0403 0.0795 8.00 89.9120 0.0890 9.00 90.8925 0.0990 10.00 91.3700 0.1094 N là số client, X là thông lượng hệ thống, R là thời gian đáp ứng. Cho tăng số server slave lên ta có kết quả như sau - Thông lượng Số client M=1 M=1 M=4 M=8 M=16 1 24.5 24.5 24.5 24.5 24.5 2 30.39 36.49 40.56 42.96 44.27 3 32.30 43.58 51.90 56.99 59.80 4 32.96 48.21 60.24 67.54 71.42 5 33.20 51.44 66.58 75.33 79.61 6 33.28 53.80 71.50 80.95 84.89 7 33.32 55.58 75.39 84.87 88.23 8 33.33 56.98 78.50 87.52 90.04 9 33. 33 58.09 81.02 89.23 90.97 10 33.33 58.99 83.06 90.30 91.41 - Thời gian đáp ứng Client M=1 M=2 M=4 M=8 M=16 1 0.0409 0.0409 0.0409 0.0409 0.0409 2 0.0658 0.0548 0.0493 0.0466 0.0452 3 0.0929 0.0668 0.0578 0.0526 0.0502 4 0.1214 0.0830 0.0664 0.0592 0.0560 5 0.1506 0.0972 0.0751 0.0664 0.0628 6 0.1803 0.1115 0.0839 0.0741 0.0706 7 0.2101 0.1259 0.0928 0.0825 0.0793 8 0.2400 0.1404 0.1019 0.0914 0.0889 9 0.2700 0.1549 0.1111 0.1009 0.0989 10 0.3000 0.1695 0.1204 0.1107 0.1094 Từ bảng kết quả ta thấy để hiệu năng của hệ thống (tăng thông lượng, giảm thời gian đáp ứng ) ta cần giảm tải ở tiến trình chính bằng cách tăng số tiến trình phụ Kết luận Trong phần này ta đã giới thiệu một số khái niệm về WWW và WebServer đây chỉ là những khái niệm hết sức cơ bản. Sau đó ta đưa ra một số thông số để đánh giá hiệu năng của WebServer. Do sự thay đổi nhanh chóng về công nghệ Web đang diễn ra nên các thông số được đưa ra ở đây chỉ mang tính minh hoạ để nhằm mục đích chính là xây dựng mô hình hàng đợi PDQ theo lí thuyết đã trình bày. KẾT LUẬN Hiện nay các hệ thống thống truyền thông trong đó có mạng máy tính không ngừng được phát triển dưạ trên sự phát triển nhanh chóng của công nghệ điện tử. Tuy nhiên việc xây dựng và thiết kế các hệ thống này không chỉ dựa trên nền tảng vật lí mà còn phụ thuộc vào việc phân tích đánh giá các thông số hiệu năng của hệ thồng từ đó có phương án tối ưu cho việc xây dựng và phát triển hệ thống nhằm đáp ứng được yêu cầu xử lí thông tin nhanh chóng với dung lượng lớn và độ tin cậy cao. Trên thực tế để đánh giá hiệu năng của một mạng máy tính người ta hay dùng phương pháp mô hình hoá, trong đó mạng máy tính được mô hình hoá bằng các mô hình toán học. Các thuộc tính được thể hiện trong mô hình là các thuộc tính có ảnh hưởng đến hiệu năng của hệ thống, đầu ra của mô hình là kết quả ước lượng của hiệu năng, với một sai số chấp nhận được. Các mô hình toán học được sử dụng thường là mạng hàng đợi, mạng Petri, đồ thị, và các mô hình lai ghép, trong đó mạng các hàng đợi tỏ ra là mô hình đơn giản nhưng có hiệu quả nhất. Chính vì vậy đồ án của em đã tập trung vào nghiên cứu lí thuyết xếp hàng và thư viện cung cấp một số thủ tục để giải các bài toán hàng đợi. Đồ án của em đã giới thiệu cụ thẻ một số khái niệm chung về mạng hàng đợi, khảo sát chi tiết một số hàng đợi đơn như M/M/1, M/M/n, M/G/1. Trong mô hình mạng các hàng đợi thì các tiến trình thường được mô phỏng là tiến trình Poisson, vì thể em đã đi sâu vào tìm hiểu quá trình này từ đó rút ra được các kết quả tính toán để áp dụng cho các mô hình hàng đợi. Sau khi khảo sát chi tiết các hàng đợi đơn, em đi vào tìm hiểu mạng các hàng đợi , đây là mô hình tổng quát chung để mô hình hoá mạng. Tuy nhiên việc tính toán trên mô hình này khá phức tạp đòi hỏi khối lượng tính toán rất lớn, để giảm khối lượng tính toán cần có các thuật toán để giải mô hình . Trong phần này em đã tìm hiểu hai thuật toán giải mô hình là thuật toán nhân chập và thuật toán phân tích giá trị trung bình. Thuật toán nhân chập sẽ lập công thức tính xác suất trạng thái của hệ thống dưới dạng tích đơn giản của hằng số chuẩn và các hàm xác suất trạng thái của các hàng đợi riêng lẻ trong mạng, sau đó tính hằng số chuẩn của mạng thông qua công thức truy hồi, trong khi đó thuật toán phân tích giá trị trung bình lại không đi tính hằng số chuẩn mà dựa trên một số quan hệ xếp hàng cơ bản để tính giá trị trung bình của các tham số hiệu năng của mạng. Sau khi tìm hiểu chung về lí thuyết xếp hàng, đồ án của em đi vào tìm hiểu và giới thiệu thư viện PDQ là một bộ công cụ cung cấp các hàm để giải mô hình hàng đợi, nó được cung cấp kèm theo cuốn sách “The Practical Performance Analyst Performance-by-design Techniques for Distributed Systems” của Neil Gunther. Dựa trên lí thuyết xếp hàng và thư viện PDQ được trình bày đồ án của em đã xây dựng một ứng dụng minh hoạ tính thời gian đáp ứng và thông lượng của WebServer. Do sự phát triển nhanh chóng về công nghệ Web và hạn chế về tiếp cận đối tượng nên ứng dụng này chỉ mang tính minh hoạ cho lí thuyết xếp hàng và phương pháp áp dụng thư viện PDQ mà em đã trình bày. Nội dung chính trong đồ án của em là lí thuyết xếp hàng cơ bản nó là cơ sở để xây dựng mô hình để đánh giá hiệu năng của mạng máy tính . Do hạn chế về thời gian, trình độ và điều kiện tiếp cận đối nên đồ án của em chưa phân tích, khảo sát chi tiết một số hệ thống hàng đợi như hệ thống xếp hàng thời gian thực và chương trình xây dựng chỉ mang tính minh hoạ, chưa xây dựng được phần mềm đóng gói đầy đủ có thể đánh giá được các thông số hiệu năng trên một mạng cụ thể. TÀI LIỆU THAM KHẢO. Neil J. Gunther, “The Practical Performance Analyst Performance-by-design Techniques for Distributed Systems”, McGraw-Hill, 1998 Leonard Kleinrock, “Queueing System – VolumeII : Computer application”, John Wiley & Sons,1976 Robert Lloyd-Evans, “ Wide Area Network Performance and Optimization Practical Strategise for Success”, Addison-Wesley, 1994. Paul J.Pery, “World Wide Web Secrets” Lê Ngọc Anh, “ Luận văn tốt nghiệp cao học : Phân tích hiệu năng của mạng máy tính sử dụng lí thuyết xếp hàng”, Đại học Bách Khoa Hà Nội, 2001. Tô Phương Dung“ Luận văn tốt nghiệp cao học :Nghiên cứu phương pháp trợ giúp WebServer khai thác cơ sở dữ liệu”, Đại học Bách Khoa Hà Nội, 1997.