Luận văn: Ước lượng tài nguyên chương trình theo thời gian thực - ĐH Công nghệ, ĐHQGHN

Luận văn thạc sĩ: Nghiên cứu tiếp cận thời gian thực để tính toán, ước lượng tài nguyên chương trình 01. Giải pháp tối ưu hiệu năng, quản lý tài nguyên hiệu quả.

• Tác giả: Nguyễn Trọng Khánh
• Người hướng dẫn: TS. Phạm Ngọc Hùng
• Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
• Chuyên ngành: Khoa học máy tính
• Đề tài: Hướng tiếp cận thời gian thực cho việc tính toán và ước lượng tài nguyên sử dụng của chương trình
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH VẼ
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU
• 2. CHƯƠNG 2: TỔNG QUAN VỀ PHÂN TÍCH CHƯƠNG TRÌNH
• 2.1. Tổng quan kĩ thuật kiểm thử hộp trắng dòng điều khiển
• 2.2. Quy trình chung của kiểm thử hộp trắng dòng điều khiển theo hướng động
• 2.3. Quy trình chung của kiểm thử hộp trắng dòng điều khiển theo hướng tĩnh
• 2.4. Các tiêu chí phủ kiểm thử
• 2.5. Đồ thị dòng điều khiển
• 2.6. Đường kiểm thử
• 2.7. So sánh kĩ thuật kiểm thử hộp trắng dòng điều khiển theo hướng tĩnh và động
• 2.8. Tầm quan trọng của tự động hóa quy trình kiểm thử hộp trắng dòng điều khiển
• 3. PHƯƠNG PHÁP TIẾP CẬN THỜI GIAN THỰC CHO VIỆC ƯỚC LƯỢNG TÀI NGUYÊN SỬ DỤNG CỦA CHƯƠNG TRÌNH
• 3.1. Các nghiên cứu liên quan
• 3.2. Công cụ đo đạc và tập dữ liệu đầu vào của chương trình
• 3.2.1. Công cụ đo đạc
• 3.2.2. Tập dữ liệu đầu vào
• 3.3. Thành phần xây dựng mô hình
• 3.3.1. Phương pháp hồi qui
• 3.3.2. Đánh giá mô hình toán học
• 4. CÔNG CỤ QUAN SÁT VÀ ĐO ĐẠC TÀI NGUYÊN SỬ DỤNG CHƯƠNG TRÌNH
• 4.1. Công cụ cài đặt
• 4.2. Mục đích chương trình
• 4.3. Kiến trúc chương trình
• 4.4. Cài đặt chương trình
• 4.5. Hướng dẫn sử dụng chương trình
• 4.6. Thí nghiệm với các thuật toán thông thường
• 4.7. Thử nghiệm về nguồn mở
• 4.8. Các hạn chế mô hình
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Ước Lượng Tài Nguyên Chương Trình Giới Thiệu và Tổng Quan

Trong kỷ nguyên bùng nổ thông tin, dữ liệu tăng trưởng với tốc độ chóng mặt, đòi hỏi phần mềm phải có khả năng mở rộng để đáp ứng nhu cầu xử lý ngày càng lớn. Các chức năng cơ bản như tìm kiếm, sắp xếp, so sánh phải làm việc với cơ sở dữ liệu khổng lồ. Điều này làm tăng độ phức tạp và thời gian xử lý. Nghiên cứu và đo đạc khả năng mở rộng của chương trình trở nên vô cùng quan trọng để đảm bảo tính ổn định và thời gian chạy hợp lý.

Hiện nay, có ba phương pháp tiếp cận phổ biến để phân tích và đo đạc khả năng mở rộng của chương trình: phân tích tĩnh, tiếp cận amortised và tiếp cận thời gian thực. Phân tích tĩnh dựa trên tính toán độ phức tạp của chương trình thông qua việc xây dựng mô hình trạng thái. Mặc dù chính xác, phương pháp này chỉ phù hợp với chương trình nhỏ do độ phức tạp tính toán và đo đạc quá lớn. Tiếp cận amortised đánh giá lượng tài nguyên sử dụng trong trường hợp xấu nhất bằng cách phân tích mọi trạng thái và hành động của chương trình. Tương tự, phương pháp này cũng chỉ khả thi với chương trình nhỏ. Tiếp cận thời gian thực đo đạc chi phí tính toán trung bình của chương trình khi chạy. Các nghiên cứu sử dụng phương pháp này cho thấy kết quả chi phí tính toán tương đồng với mô hình toán học như đa thức hoặc lũy thừa. Tuy nhiên, chúng có giới hạn về số lượng mô hình toán học được hỗ trợ hoặc thời gian chạy quá lâu.

Luận văn này đề xuất một hướng tiếp cận thời gian thực mới để giải quyết những hạn chế này. Phương pháp này tính toán tài nguyên sử dụng trung bình của chương trình dựa trên dữ liệu đầu vào thay vì dự đoán thời gian chạy một cách thiếu chọn lọc. So với các phương pháp tiếp cận thời gian thực khác, phương pháp này hỗ trợ nhiều mô hình toán học hơn và có thời gian thực thi nhanh hơn. Nghiên cứu này tập trung vào đo đạc và ước lượng tài nguyên tính toán và độ sâu sử dụng của bộ nhớ stack, hai thước đo chính để đánh giá tài nguyên của chương trình. Hướng tiếp cận này có thể mở rộng để áp dụng với các độ đo tài nguyên khác. Bằng cách so sánh kết quả với lý thuyết, chúng ta có thể đánh giá khả năng mở rộng và lỗi tiềm ẩn của chương trình. Luận văn cũng xây dựng một công cụ mô phỏng phương pháp này bằng Java và sử dụng nó để đo đạc các thuật toán chuẩn và chương trình mã nguồn mở để minh chứng tính hiệu quả.

1.1. Các Phương pháp Phân Tích Khả Năng Mở Rộng Chương Trình

Có ba cách tiếp cận phổ biến cho việc phân tích và đo đạc khả năng mở rộng của chương trình dựa trên độ phức tạp tính toán và lượng tài nguyên sử dụng của chương trình đó. Cách tiếp cận đầu tiên đó là phân tích tĩnh. Việc phân tích này dựa trên tính toán độ phức tạp của chương trình bằng cách xây dựng mô hình của chương trình dựa trên các trạng thái của chúng. Hướng tiếp cận rất chính xác nhưng chỉ phù hợp với những chương trình nhỏ do độ phức tạp trong tính toán và đo đạc là rất lớn. Hướng tiếp cận thứ hai là hướng tiếp cận amortised. Hướng tiếp cận này đánh giá lượng tài nguyên sử dụng trong những trường hợp xấu nhất của chương trình bằng cách quan sát và phân tích tất cả những trạng thái cũng như hành động của chương trình đó. Tương tự như hướng tiếp cận đầu tiên, hướng tiếp cận này cũng chỉ khả thi đối với những chương trình nhỏ. Hướng tiếp cận thứ ba là hướng tiếp cận thời gian thực. Hướng tiếp cận này đo đạc chi phí tính toán trung bình của chương trình khi chạy. Kết quả chi phí tính toan trong những nghiên cứu [5, 6, 13] là tương đồng với những mô hình toán học như là đa thức hay lũy thừa.

1.2. Mục Tiêu và Đóng Góp Của Nghiên Cứu Về Ước Lượng

Luận văn này đề xuất một hướng tiếp cận thời gian thực mới nhằm giải quyết những giới hạn của hướng tiếp cận thời gian thực như đã mô tả ở trên. Hướng tiếp cận của đề xuất tính toán tài nguyên sử dụng trung bình của chương trình dựa trên dữ liệu đầu vào thay vì dự đoán thời gian chạy thực của chương trình một cách thiếu chọn lọc. So sánh với những hướng tiếp cận thời gian thực khác, hướng tiếp cận này có thể hỗ trợ nhiều mô hình toán học và có thời gian thực thi nhanh hơn. Cụ thể hơn, hướng tiếp cận của nghiên cứu này gồm hai thành phần chính. Thành phần đầu tiên là những công cụ đo đạc (monitor instrumentation) và thành phần thứ hai là để xây dựng mô hình toán học tương đương (model construction).

II. Kiểm Thử Hộp Trắng Phân Tích Chương Trình Chi Tiết

Chương này trình bày tổng quan về phân tích chương trình, tập trung vào kỹ thuật kiểm thử hộp trắng dòng điều khiển. Kỹ thuật này bao gồm kiểm thử hướng tĩnh và hướng động, đồng thời so sánh ưu nhược điểm của từng kỹ thuật. Mục tiêu của kiểm thử hộp trắng dòng điều khiển là tìm tập ca kiểm thử tối thiểu nhưng đạt độ phủ tối đa. Kiểm thử hộp trắng dòng điều khiển chia ra gồm kiểm thử hướng tĩnh và kiểm thử hướng động. Đầu vào của hai kĩ thuật này đều là mã nguồn và tiêu chí phủ kiểm thử. Sau một loạt quá trình phân tích, đầu ra tương ứng là tập ca kiểm thử. Mỗi một kĩ thuật đều có những ưu điểm và hạn chế riêng. Mục tiêu của kiểm thử hộp trắng dòng điều khiển là tìm tập ca kiểm thử tối thiểu nhưng đạt được độ phủ tối đa.

2.1. Kiểm Thử Hướng Tĩnh Ưu Điểm và Nhược Điểm Chi Tiết

Trong kiểm thử tĩnh, mã nguồn không được thực thi trong môi trường chạy để sinh ca kiểm thử. Trong kiểm thử tĩnh, quá trình chạy ca kiểm thử chỉ thực hiện duy nhất một lần với từng ca kiểm thử để tính toán giá trị trả về và đảm bảo ca kiểm thử thực thi không có vấn đề. Đầu tiên, đồ thị dòng điều khiển được xây dựng dựa trên mã nguồn và tiêu chí phủ kiểm thử. Bước tiếp theo, từ đồ thị dòng điều khiển chúng tôi xây dựng được tập đường kiểm thử. Mỗi một đường kiểm thử trong tập đường kiểm thử mô tả hành vi chương trình với một miền bộ đầu vào nào đó. Sau đó, pha tìm ca kiểm thử thỏa mãn đường kiểm thử được tiến hành. Cuối cùng, ca kiểm thử được thực thi trong môi trường chạy.

2.2. Kiểm Thử Hướng Động Quy Trình và Ứng Dụng Thực Tế

Theo kĩ thuật này, mã nguồn sẽ được thêm các đoạn chương trình con trước khi thực thi trong môi trường chạy. Hình trình bày quy trình chung của kiểm thử động. Nhìn chung, kĩ thuật này gồm 6 bước cơ bản được diễn giải theo thứ tự dưới đây:

• Bước 1. Chèn thêm các đoạn mã nguồn mới vào mã nguồn cần kiểm thử.
• Bước 2. Chọn ngẫu nhiên một tập giá trị đầu vào hợp lệ làm ca kiểm thử đầu tiên. Thực thi chương trình với bộ giá trị vừa tìm được. Nếu không thực thi được, quay lại bước 2 để sinh bộ giá trị khác.
• Bước 3. Tìm tập các câu lệnh đã được đi qua với bộ giá trị ở bước 3 để xây dựng được hệ ràng buộc tương ứng.
• Bước 4. Phủ định hệ ràng buộc thu được ở bước 4 để sinh các hệ ràng buộc mới có tác dụng sinh các ca kiểm thử kế tiếp. Nếu không thể sinh hệ phủ định nào khác, thuật toán kết thúc.
• Bước 5. Giải hệ ràng buộc thu được ở bước 5 để sinh ca kiểm thử kế tiếp. Nếu không có ca kiểm thử nào thỏa mãn, quay về bước 5 để tìm hệ ràng buộc phủ định mới sao cho khác hệ ràng buộc hiện tại. Ngược lại, quay lại bước 3 để sinh ca kiểm thử kế tiếp.

2.3. So Sánh Chi Tiết Kiểm Thử Tĩnh vs. Kiểm Thử Động

Mỗi một kĩ thuật kiểm thử đều có những ưu điểm và hạn chế riêng. Để có cái nhìn tổng quan về hai kĩ thuật, chúng tôi đưa ra sự so sánh về số ca kiểm thử, thời gian sinh ca kiểm thử, khả năng kiểm thử vòng lặp, ảnh hưởng bởi phức tạp mã nguồn đối với hai kĩ thuật.

• Về số ca kiểm thử.
• Về thời gian sinh ca kiểm thử.
• Về khả năng kiểm thử vòng lặp.
• Tính phức tạp mã nguồn.

III. Tiếp Cận Thời Gian Thực Ước Lượng Tài Nguyên Hiệu Quả

Hướng tiếp cận này dựa trên việc quan sát và đo đạc tài nguyên sử dụng của chương trình (F(n)) thông qua tập dữ liệu đầu vào. Sau đó, áp dụng mô hình hồi qui để sinh ra hàm RF(n) - xấp xỉ của F(n): F(n) → RF(n). Ba thách thức chính bao gồm: (1) Cần mô hình toán học để so sánh và dự đoán tài nguyên (ví dụ, tuyến tính, logarit tuyến tính, mũ, lũy thừa). (2) Giảm thiểu thời gian chạy và theo dõi. (3) Tối ưu công cụ đo đạc thời gian thực để đo chính xác tài nguyên sử dụng, phụ thuộc vào cách thức chạy của chương trình và dữ liệu đầu vào. Để giải quyết, phương pháp này bao gồm công cụ đo đạc và xây dựng mô hình tài nguyên sử dụng. Đầu vào là chương trình và tập dữ liệu, công cụ đo đạc theo dõi và đo đạc tài nguyên, và phần xây dựng mô hình đánh giá và xây dựng mô hình tương ứng. Đầu ra cuối cùng là mô hình toán học tương ứng.

3.1. Thách Thức và Giải Pháp trong Ước Lượng Thời Gian Thực

Hướng tiếp cận đề xuất phải đối mặt với ba thách thức chính như sau. Thứ nhất đó là hướng tiếp cận này cần đến sự hỗ trợ của các mô hình toán học để có thể so sánh và dự đoán được lượng tài nguyên sử dụng của chương trình. Ví dụ, như trong nghiên cứu này chúng tôi sử dụng mô hình toán học phổ biến như tuyến tính, logarit tuyến tính, mũ, lũy thừa. Thách thức thứ hai chính là việc phải giảm thiểu thời gian chạy và theo dõi của chương trình. Thời gian chạy chương trình của hướng tiếp cận này phụ thuộc chủ yếu vào tập dữ liệu đầu vào. Thách thức thứ ba chính là sự cần thiết cho việc tối ưu công cụ đo đạc thời gian thực để có thể đo chính xác được tài nguyên sử dụng.

3.2. Công Cụ Đo Đạc và Vai Trò Trong Ước Lượng Tài Nguyên

Trong nghiên cứu này, phương pháp đề xuất tiến hành quan sát lượng tài nguyên được sử dụng của chương trình. Vì thế, phương pháp này sử dụng một biến đếm đơn cho mỗi độ đo tài nguyên sử dụng. Hiện tại, nghiên cứu tập trung vào hai thước đo cơ bản và phổ biến đó là chi phí tính toán và độ sâu của bộ nhớ stack. Trong tương lai, nghiên cứu này có thể mở rộng ra với nhiều độ đo khác nữa. Với công cụ đo chi phí tính toán của chương trình, phương pháp đề xuất đo tổng số lượng vòng lặp được chạy của một chương trình. Với công cụ đo độ sâu của bộ nhớ stack sử dụng, chúng tôi tiến hành đo đạc số lượng lần đệ qui hoặc gọi lại và độ sâu lớn nhất của bộ nhớ stack mà chương trình cần để sử dụng.

3.3. Tập Dữ Liệu Đầu Vào Lựa Chọn và Tầm Quan Trọng

Như đã đề cập ở trên, tập dữ liệu đầu vào có ảnh hưởng trực tiếp đến độ chính xác của kết quả cuối cùng. Bên cạnh đó, nếu tập dữ liệu quá lớn và dư thừa thì cũng ảnh hưởng đến thời gian thực thi của chương trình. Chính vì vậy, việc lựa chọn tập dữ liệu đầu vào phù hợp đóng vai trò rất quan trọng. Về mặt lý thuyết, tập dữ liệu này phải bao phủ được hết các trường hợp có thể xảy ra của chương trình, đặc biệt là những trường hợp tốt nhất và xấu nhất. Trong nghiên cứu này, chúng tôi có xử dụng phân tích tĩnh để qua đó lựa chọn được tập dữ liệu phù hợp nhất có thể.

IV. Xây Dựng Mô Hình Toán Học Phương Pháp Hồi Quy

Thành phần xây dựng mô hình khởi tạo một mô hình toán học mô tả tài nguyên sử dụng dựa trên dữ liệu đầu vào là kết quả của bộ quan sát và đo đạc ở phần đầu. Hướng tiếp cận của chúng tôi chọn ra những phương pháp hồi qui tham số như là bộ xấp xỉ thay vì sử dụng những bộ xấp xỉ đã có khác, ví dụ mạng Nơ-ron, SVR [11]. Lý do cho việc này đó là phương pháp hồi qui tham số có thể đánh giá được những tham số cụ thể của mô hình kết quả trong khi mô hình mạng Nơ-ron không tham số không thể làm được. Bằng cách sử dụng một mô hình kết quả cụ thể, chúng tôi có thể dễ dàng đánh giá khả năng mở rộng của chương trình.

4.1. Phương Pháp Hồi Quy Cơ Sở Lý Thuyết và Ứng Dụng

Khái niệm của phương pháp hồi qui được định nghĩa như sau. Phương pháp hồi qui là một phương pháp thống kê mà giá trị kì vọng của một hay nhiều biến ngẫu nhiên được dự đoán dựa vào điều kiện của các biến ngẫu nhiên khác. Phân tích hồi qui không chỉ là trùng khớp đường cong (lựa chọn một đường cong mà vừa khớp nhất với một tập điểm dữ liệu) mà nó còn phải trùng khớp với một mô hình các thành phần ngẫu nhiên và xác định. Thành phần xác định được gọi là bộ dự đoán và thành phần ngẫu nhiên được gọi là phần sai số. Ví dụ, cho một tập điểm (xi, yi), phương pháp hồi qui khởi tạo một mô hình để tính xấp xỉ y bởi yx.

4.2. Các Mô Hình Hồi Quy Lựa Chọn và Ưu Điểm Tương Đối

Có năm mô hình hồi qui được lựa chọn để khởi tạo và xây dựng mô hình của các chương trình cần ước lượng. Chúng được chọn bởi vì chúng là những mô hình toán học phức tạp phổ biến.

• Mô hình logarit
• Mô hình logarit tuyến tính
• Mô hình đa thức
• Mô hình mũ
• Mô hình lũy thừa

4.3. Đánh Giá Mô Hình R2 MRE và Biểu Đồ Phân Tán

Sau khi khởi tại những mô hình trên, chúng tôi sử dụng một số công cụ đánh giá bao gồm công cụ đo hệ số xác định R2 (Coefficient of Determination R2) và Công cụ tính sai số lỗi (Mean of relative Errors MRE) [2] để đánh giá các mô hình toán học trên. Những công cụ này sẽ đánh giá độ chính xác của mô hình, quyết định khi nào thì việc dự đoán có thể dừng lại và mô hình nào là mô hình có độ chính xác cao nhất. Sau đó mô hình có độ chính xác cao nhất sẽ được lựa chọn làm mô hình để đánh giá tài nguyên sử dụng của chương trình.

V. Công Cụ Quan Sát Cài Đặt Sử Dụng và Thử Nghiệm

Chương trình được thiết kế để đo tài nguyên sử dụng của các chương trình khác nhau, bao gồm độ phức tạp tính toán, số lượng khung stack (đối với chương trình đệ quy) và độ sâu lớn nhất của bộ nhớ stack. Kiến trúc chương trình bao gồm thư mục counter (chứa lớp định nghĩa bộ đếm), thư mục regression (chứa lớp tính toán mô hình và các mô hình toán học) và thư mục test (chứa cài đặt thuật toán để thực nghiệm).

5.1. Kiến Trúc Chương Trình Các Thành Phần Chính và Chức Năng

Cấu trúc chương trình của bao gồm ba thành phần chính:

• Thư mục counter chứa lớp mà chúng tôi cài đặt để định nghĩa ra các bộ đếm sử dụng để quan sát và đo đạc tài nguyên
• Thư mục regression chứa các lớp mà chúng tôi sử dụng để tính toán mô hình cùng với cài đặt của năm mô hình toán học cơ bản cho phương pháp hồi qui mà nghiên cứu của chúng tôi hỗ trợ để xây dựng mô hình tương đương của tài nguyên chương trình
• Cuối cùng thư mục test chứa các cài đặt thuật toán của các phép toán mà chương trình chúng tôi sử dụng để thực nghiệm.

5.2. Hướng Dẫn Sử Dụng Lệnh Tùy Chọn và Ví Dụ Cụ Thể

Sau khi vào thư mục executable nằm trong thư mục regression được giải nén của mã nguồn. Mở cửa sổ dòng lênh (command line) và chạy tệp regression.jar bằng câu lệnh dưới đây:

java –jar regression.jar [OPTION] [CLASS]

• OPTION: tùy chọn hàm để mô hình tài nguyên sử dụng.

  • -p --polynomial [OPTIONAL NUMBER] Sử dụng hàm polynomial để mô hình tài nguyên sử dụng. Hàm mặc định là hàm polynomial bậc 2. [OPTIONAL NUMBER] để chọn bậc của hàm polynomial.
  • -e --exponential Sử dụng hàm exponential để mô hình tài nguyên sử dụng.
  • -po --power Sử dụng hàm power để mô hình tài nguyên sử dụng.
  • -l --logarithmic Sử dụng hàm logarithmic để mô hình tài nguyên sử dụng.
  • -ll --linearlog Sử dụng hàm linear log để mô hình tài nguyên sử dụng.

• CLASS: tùy chọn class cần được đo tài nguyên sử dụng. Với phiên bản hiện tại, chương trình chỉ hỗ sợ hữu hạn số lượng đầu vào

5.3. Thử Nghiệm Thuật Toán Thông Thường và Nguồn Mở

Chúng tôi xây dựng một công cụ phần mềm để mô phỏng hướng nghiên cứu này bằng ngôn ngữ Java. Công cụ này có hai chức năng chính: giám sát thiết bị đo đạc và xây dựng mô hình. Chức năng giám sát sẽ tự động chèn bộ đếm vào một chương trình và quan sát việc sử dụng tài nguyên bằng cách thực hiện chương trình với các đầu vào khác nhau. Chúng tôi mô hình hóa việc sử dụng tài nguyên bằng phương pháp hồi quy.

VI. Kết Luận Đánh Giá và Hướng Phát Triển Trong Tương Lai

Với sự phát triển bùng nổ của ngành công nghệ thông tin, việc đánh giá khả năng mở rộng của chương trình trở thành một mảng rất quan trọng trong lĩnh vực kiểm chứng và kiểm thử chương trình. Chúng tôi đề xuất một hướng tiếp cận thời gian thực cho việc ước lượng tài nguyên sử dụng của chương trình với hai mục đích: Mục đích thứ nhất là đánh giá khả năng mở rộng của chương trình và mục đích thứ hai là tìm ra những lỗi tiềm ẩn của chương trình. Với mỗi chương trình, hướng tiếp cận của chúng tôi quan sát tài nguyên sử dụng dựa trên tập dữ liệu đầu vào. Sau đó dữ liệu quan sát được sẽ được fit với một mô hình toán học mà nó mô tả mối quan hệ giữa tập dữ liệu đầu vào và tài nguyên sử dụng của chương trình.

6.1. Tóm Tắt Kết Quả Nghiên Cứu và Đóng Góp Thực Tiễn

Trong phạm vi của nghiên cứu này, chúng tôi tạm thời tập trung vào hai phép đo đạc chính là phép đo chi phí tính toán và phép đo khung stack được sử dụng. Để kiểm chứng hướng tiếp cận này, chúng tôi có xây dựng một công cụ bằng ngôn ngữ Java và thực hiện các thí nghiệm trên cả những chương trình thuật toán chuẩn và các chương trình mã nguồn mở. Kết quả của thí nghiệm cho thấy khả năng dự đoán chính xác và hiệu năng tốt hơn so với các hướng tiếp cận thời gian thực khác.

6.2. Hạn Chế và Hướng Nghiên Cứu Mở Rộng Trong Tương Lai

Trong tương lai, chúng tôi sẽ cải thiện và mở rộng thêm nghiên cứu này. Đầu tiên, hướng tiếp cận này bị giới hạn bởi những chương trình có đặc điểm đơn giản vì vậy chúng tôi muốn mở rộng nghiên cứu với những chương trình phức tạp hơn. Thứ hai, nghiên cứu của chúng tôi dựa trên hướng tiếp cận thời gian thực, bởi vậy tập dữ liệu đầu vào càng đầy đủ thì độ chính xác của kết quả càng cao.

Trích đoạn nội dung tài liệu

CHƯƠNG 1. GIỚI THIỆU Trong thời đại bùng nổ thông tin, khi mà tất cả các lĩnh vực trong ngành công nghệ thông tin đều phát triển rất mạnh mẽ, điều này dẫn đến việc tăng rất nhanh về lượng dữ liệu lưu trữ và sử dụng. Trong hầu hết các tổ chức cũng như doanh nghiệp, lượng dữ liệu lưu trữ và sử dụng tăng trung bình từ 30% đến 50% mỗi năm. Lượng thông tin mà các tổ chức cũng như doanh nghiệp xử lý mỗi ngày lên tới hơn 60 terabyte - tăng hơn 1000 lần so với thập niên trước [1].

Bởi vậy, việc phần mềm ngày nay phải có khả năng mở rộng để xử lý với lượng dữ liệu ngày càng lớn là điều hiển nhiên. Ví dụ, những chức năng rất cơ bản của một phần mềm như tìm kiếu, sắp xếp hay so sánh, v. sẽ phải làm việc với những cơ sở dữ liệu lớn hơn rất nhiều so với quá khứ. Việc này không những làm tăng độ phức tạp của chương trình mà còn làm tăng rất nhiều thời gian xử lý của chương trình.

Bởi vậy, việc nghiên cứu và đo đạc khả năng mở rộng của chương trình [14] để đảm bảo được tính ổn định cũng như thời gian chạy hợp lý với người dùng trở thành một mảng rất quan trọng trong quá trình phát triển phần mềm. Ở thời điểm hiện tại, có ba cách tiếp cận phổ biến cho việc phân tích và đo đạc khả năng mở rộng của chương trình dựa trên độ phức tạp tính toán và lượng tài nguyên sử dụng của chương trình đó. Cách tiếp cận đầu tiên đó là phân tích tĩnh [8, 17], việc phân tích này dự trên tính toán độ phức tạp của chương trình bằng cách xây dựng mô hình của chương trình dựa trên các trạng thái của chúng. Hướng tiếp cận rất chính xác nhưng chỉ phù hợp với những chương trình nhỏ do độ phức tạp trong tính toán và đo đạc là rất lớn.

Hướng tiếp cận thứ hai là hướng tiếp cận amortised được mô tả trong [9,10,12]. Hướng tiếp cận này đánh giá lượng tài nguyên sử dụng trong những trường hợp xấu nhất của chương trình bằng cách quan sát và phân tích tất cả những trạng thái cũng như hành động của chương trình đó. Tương tự như hướng tiếp cận đầu tiên, hướng tiếp cận này cũng chỉ khả thi đối với những chương trình nhỏ. Hướng tiếp cận 6 TIEU LUAN MOI download : [e-mail] thứ ba là hướng tiếp cận thời gian thực được mô tả trong các nghiên cứu tại [5, 6, 13].

Hướng tiếp cận này đo đạc chi phí tính toán trung bình của chương trình khi chạy. Kết quả chi phí tính toan trong những nghiên cứu [5, 6, 13] là tương đồng với những mô hình toán học như là đa thức hay lũy thừa. Tuy nhiên, những nghiên cứu này đề có những giới hạn liên quan đến số lượng mô hình toán học mà họ hỗ trợ hay là thời gian chạy quá lâu. Luận văn này đề xuất một hướng tiếp cận thời gian thực mới nhằm giải quyết những giới hạn của hướng tiếp cận thời gian thực như đã mô tả ở trên.

Hướng tiếp cận của đề xuất tính toán tài nguyên sử dụng trung bình của chương trình dựa trên dữ liệu đầu vào thay vì dự đoán thời gian chạy thực của chương trình một cách thiếu chọn lọc. So sánh với những hướng tiếp cận thời gian thực khác, hướng tiếp cận này có thể hỗ trợ nhiều mô hình toán học và có thời gian thực thi nhanh hơn. Cụ thể hơn, hướng tiếp cận của nghiên cứu này gồm hai thành phần chính. Thành phần đầu tiên là những công cụ đo đạc (monitor instrumentation) và thành phần thứ hai là để xây dựng mô hình toán học tương đương (model construction).

Đầu tiên, những công cụ đo đạc sẽ theo dõi và đo đạc lượng tài nguyên sử dụng của chương trình dựa trên những tập dữ liệu đầu vào tương ứng. Sau đó, thành phần xây dựng mô hình toán học sẽ tiến hành xây dựng để phù hợp những dữ liệu và kết quả quan sát được với những mô hình toán học mà chúng tôi hỗ trợ. Hiện tại, nghiên cứu trong luận văn này đã có thể hỗ trợ được năm mô hình toán học phổ biến. Nghiên cứu này cũng tập trung vào việc đo đạc và ước lượng tài nguyên tính toán và độ sâu sử dụng của bộ nhớ stack mà chương trình cần như là hai thước đo chính để đánh giá tài nguyên của chương trình.

Hướng tiếp cận này cũng có thể được mở rộng để áp dụng với những độ đo tài nguyên khác. Tuy nhiên, trong khuôn khổ nghiên cứu của luận văn này, nghiên cứu chỉ tập trung vào hai thước đo như đã nêu trên. Bằng cách so sánh kết quả của hướng tiếp cận này với những kết quả dựa trên lý thuyết chúng tôi có thể đánh giá được khả năng mở rộng cũng như lỗi tiềm ẩn của chương trình. Luận văn cũng xây dựng một công cụ để mô phỏng hướng tiếp cận 7 TIEU LUAN MOI download : [e-mail] này bằng ngôn ngữ lập trình Java và sử dụng công cụ này để đo đạc những thuật toán chuẩn và một số chương trình mã nguồn mở nhằm minh chứng cho tính hiệu quả của phương pháp đề xuất.

Phần còn lại của luận văn được cấu trúc như sau. Hướng tiếp cận đề xuất nhằm tính toán và ước lượng tài nguyên sử dụng của các chương trình sẽ được mô tả chi tiết trong Chương 2. Chương 3 giới thiệu về công cụ cài đặt hỗ trợ phương pháp đề xuất cũng như mô tả chi tiết về quá trình thực nghiệm nhằm minh chứng cho tính hiệu quả của phương pháp đề xuất. Cuối cùng, kết luận và định hướng phát triển trong tương lai của luận văn sẽ được trình bày trong Chương 4.

8 TIEU LUAN MOI download : [e-mail] CHƯƠNG 2. TỔNG QUAN VỀ PHÂN TÍCH CHƯƠNG TRÌNH Ở phần này, khóa luận trình bày các kiến thức tổng quan về phân tích chương trình. Kĩ thuật chính mà chúng tôi hướng tới ở đây là kiểm thử hộp trắng dòng điều khiển gồm hai kĩ thuật kiểm thử hướng tĩnh và hướng động, đồng thời đưa ra sự so sánh về ưu điểm và nhược điểm của từng kĩ thuật. Tổng quan kĩ thuật kiểm thử hộp trắng dòng điều khiển Kiểm thử hộp trắng dòng điều khiển chia ra gồm kiểm thử hướng tĩnh và kiểm thử hướng động.

Đầu vào của hai kĩ thuật này đều là mã nguồn và tiêu chí phủ kiểm thử. Sau một loạt quá trình phân tích, đầu ra tương ứng là tập ca kiểm thử. Mỗi một kĩ thuật đều có những ưu điểm và hạn chế riêng. Mục tiêu của kiểm thử hộp trắng dòng điều khiển là tìm tập ca kiểm thử tối thiểu nhưng đạt được độ phủ tối đa.

Quy trình chung của kiểm thử hộp trắng dòng điều khiển theo hướng động Theo kĩ thuật này, mã nguồn sẽ được thêm các đoạn chương trình con trước khi thực thi trong môi trường chạy.1 trình bày quy trình chung của kiểm thử động. Nhìn chung, kĩ thuật này gồm 6 bước cơ bản được diễn giải theo thứ tự dưới đây: Bước 1. Chèn thêm các đoạn mã nguồn mới vào mã nguồn cần kiểm thử. Chọn ngẫu nhiên một tập giá trị đầu vào hợp lệ làm ca kiểm thử đầu tiên.

Thực thi chương trình với bộ giá trị vừa tìm được. Nếu không thực thi được, quay lại bước 2 để sinh bộ giá trị khác. Tìm tập các câu lệnh đã được đi qua với bộ giá trị ở bước 3 để xây dựng được hệ ràng buộc tương ứng. Phủ định hệ ràng buộc thu được ở bước 4 để sinh các hệ ràng buộc mới có tác dụng sinh các ca kiểm thử kế tiếp.

Nếu không thể sinh hệ phủ định nào khác, thuật toán kết thúc. Giải hệ ràng buộc thu được ở bước 5 để sinh ca kiểm thử kế tiếp. Nếu không có ca kiểm thử nào thỏa mãn, quay về bước 5 để tìm hệ ràng buộc phủ định mới sao cho khác hệ ràng buộc hiện tại. Ngược lại, quay lại bước 3 để sinh ca kiểm thử kế tiếp.

9 TIEU LUAN MOI download : [e-mail] Source Pha chèn thêm khối code Tiêu chí lệnh mới phủ Tìm ca kiểm thử khởi đầu ngẫu nhiên Thực thi ca kiểm thử vừa tìm được Tái tạo đường thực thi Tạo đường thực thi mới Kết False Tìm được ca True thúc kiểm thử mới Hình 0. Quy trình chung của kiểm thử hộp trắng dòng điều khiển theo hướng động. Trong bước 1, quá trình chèn thêm khối mã nguồn mới vào mã nguồn cần kiểm thử được tiến hành một cách tự động. Công cụ DMS/SRT1 được đánh giá khá mạnh mẽ để thực hiện pha này.

Đoạn mã nguồn thêm vào có chức năng đánh dấu, thoát chương trình hoặc ghi thông tin về quá trình thực thi ra tệp, v. Để làm được điều này, chúng tôi cần xây dựng các luật chèn thêm mã nguồn mới vào mã nguồn cần kiểm thử. Với công cụ DMS/SRT, mỗi một luật bắt đầu với từ khóa rule và theo sau là tên đặt cho luật. Từ khóa rewrite to nêu cách biến đổi đoạn mã nguồn gốc về đoạn mã nguồn mới.

Kiểu dữ liệu có thể là expression (ứng với biểu thức), statement (ứng với câu lệnh gán hoặc khởi tạo), type (ứng với kiểu dữ liệu), identifier (ứng với định danh như tên biến, tên hàm), v.2 mô tả một luật chèn thêm câu lệnh đánh dấu vào khối lệnh điều khiển rẽ nhánh. Cụ thể, biến mảng visited đánh dấu vị trí câu lệnh đi qua 10 TIEU LUAN MOI download : [e-mail] được bổ sung vào mã nguồn ban đầu ngay sau mỗi khối lệnh điều khiển rẽ nhánh.3 đưa ra mã nguồn triangle sau khi áp dụng luật.2: Ví dụ một luật chèn mã nguồn trong DMS/SRT. Mã nguồn hàm triangle sau khi thêm khối mã nguồn mới. Quy trình chung của kiểm thử hộp trắng dòng điều khiển theo hướng tĩnh Trong kiểm thử tĩnh, mã nguồn không được thực thi trong môi trường chạy để sinh ca kiểm thử.

Trong kiểm thử tĩnh, quá trình chạy ca kiểm thử chỉ thực hiện duy 11 TIEU LUAN MOI download : [e-mail] nhất một lần với từng ca kiểm thử để tính toán giá trị trả về và đảm bảo ca kiểm thử thực thi không có vấn đề. Các bước tổng quát trong kĩ thuật này được trình bày ở Hình 0. Đầu tiên, đồ thị dòng điều khiển được xây dựng dựa trên mã nguồn và tiêu chí phủ kiểm thử. Bước tiếp theo, từ đồ thị dòng điều khiển chúng tôi xây dựng được tập đường kiểm thử.

Mỗi một đường kiểm thử trong tập đường kiểm thử mô tả hành vi chương trình với một miền bộ đầu vào nào đó. Sau đó, pha tìm ca kiểm thử thỏa mãn đường kiểm thử được tiến hành. Cuối cùng, ca kiểm thử được thực thi trong môi trường chạy.