Luận Văn Thạc Sĩ Về Phương Pháp Tính Cận Tài Nguyên Trong Featherweight Java

Luận văn thạc sĩ nghiên cứu vnu uet phương pháp dựa trên hệ thống kiểu để tính cận trên tài nguyên của các chương trình, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải

• Chuyên ngành: Công nghệ thông tin
• Đề tài: Phương Pháp Dựa Trên Hệ Thống Kiểu Để Tính Cận Trên Tài Nguyên Của Các Chương Trình Featherweight Java Có Giao Tác
• Loại tài liệu: luận văn

Mục lục chi tiết

• LỜI CAM ĐOAN
• DANH MỤC CÁC KÝ HIỆU, THUẬT NGỮ, CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ
• PHẦN MỞ ĐẦU
• 0.1. Tính cấp thiết của đề tài
• 0.2. Mục tiêu của luận văn
• 0.3. Công cụ phần mềm
• 0.4. Phương pháp nghiên cứu
• 0.5. Bố cục của luận văn
• 1. CHƯƠNG 1: MỘT SỐ KIẾN THỨC CƠ SỞ
• 1.1. Các lý thuyết nền tảng về hệ thống kiểu
• 1.2. Khái niệm hệ thống kiểu
• 1.3. Vai trò của hệ thống kiểu
• 1.3.1. Phát hiện lỗi
• 1.3.2. Trừu tượng hóa
• 1.3.3. Tài liệu
• 1.3.4. Tăng hiệu quả
• 2. CHƯƠNG 2
• 3. CHƯƠNG 3
• 4. CHƯƠNG 4
• 5. CHƯƠNG 5
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phương Pháp Tính Cận Tài Nguyên Trong Featherweight Java

Phương pháp tính cận tài nguyên trong Featherweight Java (TFJ) là một lĩnh vực nghiên cứu quan trọng trong lập trình song song. Với sự phát triển của các bộ xử lý đa nhân, việc tối ưu hóa tài nguyên trở nên cần thiết hơn bao giờ hết. Featherweight Java cung cấp một nền tảng lý tưởng để nghiên cứu các tính chất của Java trong môi trường giao tác. Bài viết này sẽ đi sâu vào các khía cạnh của phương pháp này, từ lý thuyết đến ứng dụng thực tiễn.

1.1. Khái Niệm Về Featherweight Java Và Tài Nguyên

Featherweight Java là một ngôn ngữ lập trình tối giản, được thiết kế để nghiên cứu các tính chất của Java. Tài nguyên trong ngữ cảnh này bao gồm bộ nhớ, thời gian xử lý và các yếu tố khác ảnh hưởng đến hiệu suất của chương trình. Việc hiểu rõ về tài nguyên là rất quan trọng để tối ưu hóa hiệu suất của các chương trình viết bằng TFJ.

1.2. Tính Cấp Thiết Của Phương Pháp Tính Cận Tài Nguyên

Với sự gia tăng của các ứng dụng đa luồng, việc tính toán tài nguyên tiêu tốn trở nên cấp thiết. Phương pháp tính cận tài nguyên giúp xác định chính xác lượng tài nguyên cần thiết cho một chương trình, từ đó giảm thiểu rủi ro và tối ưu hóa hiệu suất. Điều này đặc biệt quan trọng trong các ứng dụng yêu cầu tính toán song song.

II. Vấn Đề Và Thách Thức Trong Tính Cận Tài Nguyên

Mặc dù phương pháp tính cận tài nguyên trong TFJ mang lại nhiều lợi ích, nhưng cũng tồn tại nhiều thách thức. Các vấn đề như deadlock, hiệu suất thấp và khó khăn trong việc xác định tài nguyên tiêu tốn là những thách thức lớn. Bài viết này sẽ phân tích các vấn đề này và đề xuất giải pháp.

2.1. Các Vấn Đề Liên Quan Đến Deadlock

Deadlock là một trong những vấn đề nghiêm trọng trong lập trình song song. Khi các giao tác không thể hoàn thành do chờ đợi tài nguyên, hiệu suất của chương trình sẽ giảm sút. Việc áp dụng phương pháp tính cận tài nguyên có thể giúp phát hiện và ngăn chặn deadlock trước khi nó xảy ra.

2.2. Khó Khăn Trong Việc Xác Định Tài Nguyên Tiêu Tốn

Xác định chính xác tài nguyên tiêu tốn trong các chương trình TFJ là một thách thức lớn. Các yếu tố như cấu trúc dữ liệu, thuật toán và cách thức giao tác đều ảnh hưởng đến tài nguyên. Việc phát triển một hệ thống kiểu chính xác có thể giúp cải thiện khả năng ước lượng tài nguyên.

III. Phương Pháp Tính Toán Tài Nguyên Trong Featherweight Java

Để tính toán tài nguyên trong TFJ, cần áp dụng các phương pháp và thuật toán cụ thể. Bài viết này sẽ trình bày các phương pháp chính, bao gồm việc sử dụng hệ thống kiểu và các thuật toán tính toán tài nguyên.

3.1. Hệ Thống Kiểu Trong Featherweight Java

Hệ thống kiểu là một phần quan trọng trong việc tính toán tài nguyên. Nó giúp xác định các quy tắc kiểu và đảm bảo rằng các chương trình được viết đúng cách. Việc áp dụng hệ thống kiểu trong TFJ giúp giảm thiểu lỗi và tối ưu hóa tài nguyên.

3.2. Thuật Toán Tính Tài Nguyên

Các thuật toán tính tài nguyên trong TFJ được thiết kế để ước lượng chính xác lượng tài nguyên cần thiết cho một chương trình. Những thuật toán này dựa trên các quy tắc kiểu và các phép toán tính toán tài nguyên, giúp cải thiện hiệu suất của chương trình.

IV. Ứng Dụng Thực Tiễn Của Phương Pháp Tính Cận Tài Nguyên

Phương pháp tính cận tài nguyên trong TFJ không chỉ có giá trị lý thuyết mà còn có nhiều ứng dụng thực tiễn. Bài viết này sẽ trình bày một số ứng dụng tiêu biểu và kết quả nghiên cứu liên quan.

4.1. Ứng Dụng Trong Lập Trình Song Song

Phương pháp tính cận tài nguyên có thể được áp dụng trong lập trình song song để tối ưu hóa hiệu suất. Việc xác định chính xác tài nguyên cần thiết giúp các lập trình viên thiết kế các ứng dụng hiệu quả hơn.

4.2. Kết Quả Nghiên Cứu Về Tài Nguyên

Nghiên cứu về tài nguyên trong TFJ đã chỉ ra rằng việc áp dụng phương pháp tính cận tài nguyên giúp giảm thiểu tài nguyên tiêu tốn và cải thiện hiệu suất. Các kết quả này có thể được áp dụng trong thực tiễn để tối ưu hóa các ứng dụng.

V. Kết Luận Và Tương Lai Của Phương Pháp Tính Cận Tài Nguyên

Phương pháp tính cận tài nguyên trong Featherweight Java đã chứng minh được giá trị của nó trong việc tối ưu hóa tài nguyên. Bài viết này sẽ tóm tắt các kết quả đạt được và đề xuất hướng phát triển trong tương lai.

5.1. Tóm Tắt Kết Quả Đạt Được

Các kết quả nghiên cứu cho thấy phương pháp tính cận tài nguyên giúp cải thiện hiệu suất và giảm thiểu tài nguyên tiêu tốn. Điều này mở ra nhiều cơ hội cho việc phát triển các ứng dụng hiệu quả hơn.

5.2. Hướng Phát Triển Trong Tương Lai

Trong tương lai, việc phát triển các phương pháp tính toán tài nguyên chính xác hơn sẽ là một thách thức lớn. Cần nghiên cứu thêm về các thuật toán và hệ thống kiểu để cải thiện khả năng ước lượng tài nguyên trong các chương trình TFJ.

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

3 MỤC LỤC LỜI CAM ĐOAN .3 DANH MỤC CÁC KÝ HIỆU , THUẬT NGỮ, CHỮ VIẾT TẮT .5 DANH MỤC CÁC BẢNG .7 DANH MỤC CÁC HÌNH VẼ .8 Tính cấp thiết của đề tài .8 Mục tiêu của luận văn .9 Công cụ phần mềm.9 Phƣơng pháp nghiên cƣ́u .9 Bố cục của luận văn. MỘT SỐ KIẾN THỨC CƠ SỞ. Các lý thuyết nền tảng về hệ thống kiểu. Khái niệm hệ thống kiểu.

Vai trò của hệ thống kiểu. Các thuộc tính cơ bản của hệ thống kiểu. Các ứng dụng và ý nghĩa kinh tế của hệ thống kiểu. Hệ thống kiểu trong việc chính thức hóa ngôn ngữ kiểu.

Bộ nhớ giao tác phần mềm. Khái niệm và các thuộc tính cơ bản của giao tác. Bộ nhớ giao tác phần mềm. FEATHERWEIGHT JAVA CÓ GIAO TÁC.

Ngữ nghĩa cục bộ. Ngữ nghĩa toàn cục. HỆ THỐNG KIỂU CHO TFJ. Các qui tắc kiểu.

Qui tắc cục bộ. Qui tắc toàn cục. THUẬT TOÁN KIỂU VÀ CÔNG CỤ. Xây dựng bộ cú pháp cho TFJ với ANTLR.

Cơ sở lý thuyết về cú pháp đƣợc hỗ trợ bởi ANTLR. Bộ đặc tả cú pháp cho TFJ với ANTLR V3 .45 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Xây dựng thuật toán tính kiểu. Rút gọn một chuỗi số có dấu bất kỳ về chuỗi số chính tắc.

Mô tả phép toán cộng ⊕ của 2 chuỗi số có dấu chính tắc. Mô tả phép toán gộp ⊗ của 2 chuỗi số có dấu chính tắc. Mô tả phép toán điều kiện , phép toán chọn ⊙, của 2 chuỗi số có dấu chính tắc. Tính toán giá trị mức giới hạn trên tổng chi phí tài nguyên cho một chƣơng trình TFJ .63 TÀI LIỆU THAM KHẢO.

CÁC CÔNG CỤ HỖ TRỢ CÀI ĐẶT THỰC NGHIỆM. BẢNG MÔ TẢ CHI TIẾT ĐẶC TẢ CÚ PHÁP TFJ TRÊN ANTLR V3. BẢNG MÔ TẢ CÁC PHƢƠNG THỨC TRONG CHƢƠNG TRÌNH.85 LUAN VAN CHAT LUONG download : add [e-mail] 5 DANH MỤC CÁC KÝ HIỆU , THUẬT NGỮ, CHỮ VIẾT TẮT CHỮ VIẾT TẮT, THUẬT STT GIẢI NGHĨA NGỮ, KÝ HIỆU CHỮ VIẾT TẮT FJ –Featherweigh Java Một ngôn ngữ Java tối giản để nghiên cứu các 1 tính chất của Java. STM - Software Bộ nhớ giao tác phần mềm, một giải pháp viết 2 Transactional Memory các chƣơng trình tƣơng tranh, thay cho cơ chế đồng bộ dựa trên khóa.

TFJ – Transactional Là một ngôn ngữ mở rộng của FJ tích hợp mô 3 Featherweight Java hình bộ nhớ giao tác phần mềm. THUẬT NGỮ 1 Type System Hệ thống kiểu 2 Transaction Giao tác 3 Thread Luồng 4 Excution errors Lỗi thực thi 5 Syntactic mechanism Cơ chế cú pháp 6 Type checker Bộ kiểm tra kiểu 7 Well-behaved Tính chất hành xử đúng của chƣơng trình. 8 Well-formed Tính chất thiết lập đúng của chƣơng trình. 9 Ill-behaved Tính chất hành xử yếu của chƣơng trình.

10 Execution error Lỗi thực thi Well-typed Một chƣơng trình khi đƣợc thông qua bởi bộ 11 kiểm tra kiểu đƣợc gọi là kiểu tốt. Ill-typed Một chƣơ ng trì nh không đƣợc thông qua bởi bộ 12 kiểm tra kiểu đƣợc gọi là kiểu yếu. 13 ADT-Abstract Data Type Kiểu dữ liệu trừu tƣợng 14 Efficiency Hiệu suất chƣơng trình 15 Compositionality Tính thành phần 16 Guarantee Tính đảm bảo Static phase Pha tĩnh, đặc tả bởi tập các qui tắc đánh giá kiểu 17 một biểu thƣ́c nói riêng và một chƣơng trình nói chung có là well-formed. Dynamic phase Pha động, là một mô tả chƣơng trình đƣợc thực 18 hiện nhƣ thế nào.

LUAN VAN CHAT LUONG download : add [e-mail] 6 19 Atomicity Tính nguyên tử 20 Consistency Tính nhất quán 21 Isolation Tính độc lập 22 Durability Tính bền vững 23 Onacid Trạng thái mở một giao tác 24 Commit Trạng thái kết thúc một giao tác 25 Lock-based synchronization Đồng bộ hóa dựa trên khóa 26 Nested transactions Các giao tác lồng 27 Multi-threaded Đa luồng 28 Spawn Sinh luồng Joint commits Các commit của các luồng song song đồng thời 29 thực hiện kết thúc một giao tác chung. 30 Local semantics Ngữ nghĩa cục bộ 31 Global semantics Ngữ nghĩa toàn cục 32 Local enviroments Môi trƣờng cục bộ 33 Global enviroments Môi trƣờng toàn cục 34 Syntax Cú pháp 35 Term Các thành phần trong biểu thức cú pháp. KÝ HIỆU + m Mô tả thành phần + trong hệ thống kiểu dựa trên 1 chuỗi số có dấu, m thao tác onacid liên tiếp. - m Mô tả thành phần – trong hệ thống kiểu dựa trên 2 chuỗi số có dấu, m thao tác commit liên tiếp.

# m Mô tả thành phần # trong hệ thống kiểu dựa trên 3 chuỗi số có dấu, m các giao tác lồng nhau. ¬ m Mô tả thành phần ¬ thể hiện số lƣợng joint 4 commit trong hệ thống kiểu dựa trên chuỗi số có dấu. LUAN VAN CHAT LUONG download : add [e-mail] 7 DANH MỤC CÁC BẢNG Bảng 2.2 Ngữ nghĩa cục bộ [17] .3 Ngữ nghĩa toàn cục [17].1 Hệ thống kiểu mức cục bộ[17] .2 Hệ thống kiểu mức toàn cục[17] .1 Tổng quát hóa các rule của EBNF [18] .2 Bảng kết quả kiểm thử phép toán chính tắc chuỗi số có dấu .3 Bảng kết quả kiểm thử phép toán cộng 2 chuỗi số có dấu chính tắc .4 Bảng kết quả kiểm thử phép toán gộp 2 chuỗi số có dấu chính tắc .5 Bảng kết quả kiểm thử phép toán chọn 2 chuỗi số có dấu chính tắc. 51 Bảng PL-0 1 Chú giải chi tiết các rule trong cú pháp của ngôn ngữ TFJ.

69 Bảng PL-0 2 Mô tả các phƣơng thức dùng để tính toán giới hạn trên chi phí tài nguyên. 85 DANH MỤC CÁC HÌNH VẼ Hình 1.1 Hệ thống kiểu trong trình biên dịch[10] .2 Sơ đồ các trạng thái của giao tác .3 Ví dụ giả mã cho mô hình giao tác lồng và đa luồng .4 Ví dụ mô hình giao tác lồng, đa luồng và joint .5 Ví dụ mô hình giao tác thể hiện tính phụ thuộc các luồng song song .1 Mô tả hai thành phần # liền kề .2 Minh họa ý nghĩa thành phần ¬ .3 Mô hình mô tả spawn ở thời điểm cuối của biểu thức .1 Mô tả các bƣớc lấy đƣợc chuỗi StringTFJPrimitive .2 Mô tả các giai đoạn để tính giá trị giới hạn trên tài nguyên .3 Mô hình chƣơng trình TFJ cho Ví dụ 4.4 Minh họa ví dụ các giai đoạn để tính giới hạn trên tổng chi phí tài nguyên .1 Mô hình giao tác Thực nghiệm 1 .2 Chạy mã Thực nghiệm 1 trên công cụ.3 Mô hình giao tác cho Thực nghiệm 2 .4 Chạy mã Thực nghiệm 2 trên công cụ tính kiểu tự động. 62 Hình PL-0 1 Tạo mới một Project. 66 Hình PL-0 2 Tạo một tệp ngữ pháp trong ANTLR.

68 LUAN VAN CHAT LUONG download : add [e-mail] 8 PHẦN MỞ ĐẦU Tính cấp thiết của đề tài Gần đây các máy tính và điện thoại đƣợc trang bị nhiều bộ xử lý hay các bộ xử lý có nhiều nhân (core). Để khai thác hết khả năng chạy song song của các bộ xử lý này cần có các tiến trình hoặc luồng (process, thread) có khả năng tính toán song song. Các ngôn ngữ lập trình truyền thống sử dụng cơ chế khóa và đồng bộ (lock, synchronization) để các tiến trình cùng hoạt động và truy cập đến các biến dùng chung. Tuy nhiên, phƣơng pháp này dễ gây ra các khóa chết (deadlock) hoặc các lỗi tiềm ẩn rất khó phát hiện và sửa chữa.

Software Transactional Memory (STM- bộ nhớ giao tác phần mềm) [15], là một giải pháp mới để viết các chƣơng trình song song sử dụng cơ chế giao tác (transaction) của các hệ quản trị cơ sở dữ liệu thay cho cơ chế đồng bộ dựa trên khóa đối với việc chia sẻ bộ nhớ đồng thời. STM xử lý với bộ nhớ thông qua các giao tác, mỗi giao tác cho phép tự do đọc và ghi để chia sẻ các biến khi đƣợc khởi động (onacid) và một log đƣợc sử dụng để ghi các hoạt động này cho tới thời điểm kết thúc (commit). Tuy nhiên, một vấn đề phát sinh mô hình STM này sử dụng thêm khá nhiều tài nguyên (bộ nhớ, xử lý), do các log là các bản sao của thông tin, biến, khi tính toán để thực hiện commit hoặc rollback khi tính toán bị thất bại xong. Hệ thống kiểu là một phƣơng pháp phân tích tĩnh dựa trên các qui tắc kiểu đã đặt ra để đƣa ra các khẳng định chƣơng trình có thành lập đúng hoặc an toàn hay không, từ đó, nó hạn chế các lỗi tiềm tàng có thể xảy ra.

Hệ thống kiểu cũng có thể ƣớc lƣợng an toàn thông tin về tài nguyên sử dụng của chƣơng trình mà không cần thực thi nó[5]. Việc này có ý nghĩa thực tiễn vì với một chƣơng trình đã cho ta biết đƣợc trong trƣờng hợp xấu nhất nó có thể cần bao nhiêu bộ nhớ. Một số hệ thống kiểu trƣớc kia khi giải quyết vấn đề tính toán tài nguyên tĩnh cho một chƣơng trình có giao tác thông qua thể hiện cây phân cấp [13] và tổng tài nguyên đƣợc tính theo nguyên tắc cộng dồn, khi đó giới hạn trên tổng tài nguyên đƣa ra là con số khá lớn. Luận văn nghiên cứu một hệ thống kiểu mới [17] sử dụng các chƣơng trình Featherweight Java có giao tác (Transactional Featherweight Java, gọi tắt là TFJ).

Hệ thống kiểu ƣớc lƣợng tài nguyên tiêu tốn chính xác hơn so với các nghiên cứu trƣớc đó [6, 13]. Những vấn đề nêu trên là cơ sở khoa học và thực tiễn để tôi thực hiện đề tài “Phương pháp dựa trên hệ thống kiểu để tính cận trên tài nguyên của các chương trình Featherweight Java có giao tác”. LUAN VAN CHAT LUONG download : add [e-mail] 9 Mục tiêu của luận văn Trên cơ sở nghiên cứu lý thuyết về hệ thống kiểu , để xác định tài nguyên của các chƣơng trình Featherweight Java có giao tác (TFJ) [17], đề tài đƣa ra phƣơng pháp tính tài nguyên của các chƣơng trình TFJ và cài đặt một công cụ phần mềm có khả năng tính tài nguyên sử dụng của các chƣơng trình TFJ đó. Công cụ phần mềm Sử dụng thƣ viện và công cụ hỗ trợ ANTLR để phân tích mã nguồn của chƣơng trình TFJ.

Các công cụ lập trình trên nền .NET và ngôn ngữ C # để cài đặt thuật toán chƣơng trình. Phƣơng pháp nghiên cƣ́u Để đề tài đạt đƣợc kết quả nhƣ mục tiêu đặt ra, trong luận văn tôi đã đề xuất và áp dụng các phƣơng pháp nghiên cứu nhƣ sau: - Nghiên cứu tài liệu: Nghiên cứu hệ thống kiểu nói chung và tập trung vào hệ thống kiểu cho các chƣơng trình TFJ nhƣ đã nêu trong [17]. Đây là mảng kiến thức mới, không đƣợc học ở trƣờng và đòi hỏi nhiều kiến thức nền tảng liên quan.