Tóm tắt Luận văn Tính cận trên bộ nhớ log của chương trình sử dụng giao dịch
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN PHAN TÌNH
TÍNH CẬN TRÊN BỘ NHỚ LOG CỦA CHƢƠNG
TRÌNH SỬ DỤNG GIAO DỊCH
Ngành:
Chuyên ngành: Kỹ thuật Phần Mềm
Mã số: 60480103
Công Nghệ Thông Tin
TÓM TẮT LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN
Hà Nội - 2016
MỤC LỤC
MỞ ĐẦU ................................................................................................................3
Tính cấp thiết của đề tài......................................................................................3
Mục tiêu nghiên cứu ...........................................................................................3
Phƣơng pháp nghiên cứu ....................................................................................4
Cấu trúc của luận văn .........................................................................................4
1.1. Giới thiệu .....................................................................................................5
1.2. Hƣớng tiếp cận.............................................................................................6
1.3. Ví dụ minh họa ............................................................................................6
2.1. Hệ thống kiểu...............................................................................................7
2.1.1. Giới thiệu về hệ thống kiểu...................................................................7
2.2.1. Giao dịch (Transaction) ........................................................................8
3.1. Cú pháp của TM [1].....................................................................................9
3.2. Các ngữ nghĩa động.....................................................................................9
3.2.1. Ngữ nghĩa cục bộ..................................................................................9
3.2.2. Ngữ nghĩa toàn cục...............................................................................9
4.1. Các kiểu .....................................................................................................11
5.2.2. Thuật toán Cộng (Joint)......................................................................16
5.2.3. Thuật toán gộp (Merge)......................................................................17
5.2.4. Thuật toán JoinCommit ......................................................................17
KẾT LUẬN...........................................................................................................18
TÀI LIỆU THAM KHẢO ....................................................................................19
2
MỞ ĐẦU
Tính cấp thiết của đề tài
Cùng với sự phát triển nhƣ vũ bão của khoa học công nghệ, các vi xử lý hiện đại
ngày càng thể hiện sức mạnh qua nhiều nhân (core) với tốc độ xử lý ngày càng cao. Có
đƣợc nhƣ vậy là do bên trong các vi xử lý này đƣợc thiết kế các luồng (thread) có khả
năng chạy và xử lý song song. Trƣớc đây để lập trình đa luồng, ngƣời ta sử dụng cơ
chế đồng bộ (synchronization) dựa trên khóa (lock) để áp đặt giới hạn về quyền truy
cập tài nguyên trong một môi trƣờng khi có nhiều luồng thực thi.Tuy nhiên, khi áp
dụng phƣơng pháp này thƣờng nảy sinh các vấn đề nhƣ khóa chết (deadlock) hoặc các
lỗi tiềm tàng…
Software Transactional Memory (STM- bộ nhớ giao dịch phần mềm) [8] là một
giải pháp đơn giản hơn, nhƣng vô cùng mạnh mẽ mà có thể giải quyết đƣợc hầu hết
các vấn đề trên. Nó đã thay thế hoàn toàn giải pháp cũ trong việc truy cập bộ nhớ dùng
chung. STM giao tiếp với bộ nhớ thông qua các giao dịch. Các giao dịch này cho phép
tự do đọc, ghi để chia sẻ các biến và một vùng nhớ gọi là log sẽ đƣợc sử dụng để ghi
lại các hoạt động này cho tới khi kết thúc giao dịch.
Một trong những mô hình giao dịch phức tạp sử dụng STM là mô hình giao dịch
lồng và đa luồng (nested and multi-threaded transaction) [5]. Trong quá trình thực thi
của các chƣơng trình giao dịch lồng và đa luồng, khi các luồng mới đƣợc sinh ra hoặc
một giao dịch đƣợc bắt đầu, các vùng bộ nhớ gọi là log sẽ đƣợc cấp phát. Các log này
dùng để lƣu lại bản sao của các biến dùng chung, nhờ vậy mà các luồng trên có thể sử
dụng các biến này một cách độc lập.
Vấn đề đặt ra ở đây là tại thời điểm chƣơng trình chạy liệu lƣợng bộ nhớ cần cấp
phát cho các log có vƣợt quá tài nguyên bộ nhớ của máy, hay chƣơng trình có thể chạy
một cách trơn tru mà không gặp phải bất kỳ lỗi nào nhƣ hết bộ nhớ. Chính vì vậy, việc
xác định cận trên của bộ nhớ ở thời điểm chạy chƣơng trìnhcủa chƣơng trình giao dịch
là một vấn đề then chốt, có ý nghĩa hết sức quan trọng.
Chính vì lí do đó, trong luận văn thực hiện ở đây, một nghiên cứu sử dụng
phƣơng pháp phân tích tĩnh để giải quyết bài toán tính cận trên bộ nhớ log của chƣơng
trình có giao dịch sẽ đƣợc trình bày, dựa trên bài báo đã đƣợc các tác giả công bố
trong [1].
Mục tiêu nghiên cứu
Luận văn đƣợc thực hiện dựa trên nghiên cứu trong bài báo [1]. Do vậy để có thể
hiểu đƣợc giải pháp các tác giả đã đề xuất trong [1], trong luận văn này tập trung
nghiên cứu các lý thuyết về hệ thống kiểu; Các khái niệm cơ bản cũng nhƣ tính chất
của giao dịch; Nghiên cứu cú pháp và ngữ nghĩa của ngôn ngữ TM (Transactional
Memory) – Một ngôn ngữ để viết các chƣơng trình giao dịch. Từ việc nắm đƣợc giải
pháp xây dựng hệ thống kiểu đề cập trong bài báo, một công cụ sẽ đƣợc cài đặt dựa
trên ngôn ngữ C#.
3
Phƣơng pháp nghiên cứu
Để thực hiện đƣợc mục tiêu đã đề ra trong luận văn, các phƣơng pháp nghiên cứu
sau đây đã đƣợc kết hợp:
- Phƣơng pháp nghiên cứu lý thuyết: bao gồm phân tích, tổng hợp các tài liệu, bài
báo có liên quan về lý thuyết hệ thống kiểu đặc biệt là hệ thống kiểu cho các chƣơng
trình TM, tài liệu về các thuật toán dựa trên hệ thống kiểu..
- Phƣơng pháp thực nghiệm: Cài đặt thuật toán đã đề xuất, chạy thử để kiểm tra
tính đúng đắn của chƣơng trình.
Cấu trúc của luận văn
Luận văn đƣợc trình bày trong các phần, với nội dung chính của mỗi phần nhƣ
sau:
Mở đầu: Nêu ra tính cấp thiết của đề tài, nêu ra các mục tiêu cần nghiên cứu, các
phƣơng pháp đƣợc sử dụng khi nghiên cứu và cấu trúc các phần của luận văn.
Chƣơng 1: Giới thiệu bài toán
Trình bày nội dung cụ thể của bài toán tính cận trên bộ nhớ log của chƣơng trình
có sử dụng giao dịch, các vấn đề cần giải quyết trong bài toán này và hƣớng tiếp cận
để giải quyết bài toán. Trong phần này, các điểm cải tiến của phƣơng pháp giải quyết
bài toán ở đây so với các phƣơng pháp trƣớc kia cũng đƣợc nêu ra. Ví dụ đƣợc trình
bày trong mục 1.3 sẽ minh họa rõ ràng cho bài toán và hƣớng tiếp cận đã đƣa ra.
Chƣơng 2: Một số kiến thức cơ sở
Trình bày các lý thuyết cơ bản đƣợc sử dụng làm cơ sở để giải quyết bài toán,
bao gồm: Lý thuyết về hệ thống kiểu nhƣ khái niệm, các thuộc tính hay ứng dụng của
hệ thống kiểu trong thực tế; Lý thuyết về giao dịch, bộ nhớ giao dịch phần mềm gồm
các khái niệm, tính chất, ứng dụng…
Chƣơng 3: Ngôn ngữ giao dịch
Giới thiệu ngôn ngữ giao dịch TM (Transactional memory)- Một ngôn ngữ đƣợc
dùng để viết các chƣơng trình giao dịch. Trong chƣơng này, cú pháp và ngữ nghĩa của
ngôn ngữ TM sẽ đƣợc trình bày cụ thể.
Chƣơng 4: Hệ thống kiểu cho chƣơng trình giao dịch
Nghiên cứu hệ thống kiểu để giải quyết bài toán tính cận trên bộ nhớ log cho
chƣơng trình có giao dịch đã đƣợc trình bày trong bài báo [1]. Lý thuyết hệ thống kiểu
đƣợc phát triển ở đây bao gồm các kiểu và các quy tắc kiểu.
Chƣơng 5: Xây dựng công cụ và thực nghiệm
Cài đặt các thuật toán kiểu dựa trên hệ thống kiểu đã đƣợc trình bày ở chƣơng 4.
Từ các thuật toán đó, xây dựng công cụ để giải quyết bài toán tính cận trên bộ nhớ log
và thực nghiệm để kiểm tra tính đúng đắn của công cụ.
Kết luận:
Đánh giá các kết quả đã đạt đƣợc, nêu ra tồn tại và hƣớng phát triển.
4
CHƢƠNG 1. GIỚI THIỆU BÀI TOÁN
1.1. Giới thiệu
Nhƣ chúng ta đã đề cập ở phần mở đầu, STM là giải pháp đƣợc sử dụng trong
việc chia sẻ bộ nhớ dùng chung và một trong những mô hình giao dịch phức tạp sử
dụng STM là mô hình giao dịch lồng và đa luồng (nested and multi-threaded
transaction)
Ở đây, một giao dịch đƣợc gọi là lồng khi nó chứa một số giao dịch khác. Chúng
ta gọi giao dịch cũ là giao dịch cha và gọi các giao dịch mà sinh ra trong giao dịch cha
là giao dịch con. Các giao dịch con này phải đƣợc đóng trƣớc giao dịch cha. Hơn nữa,
giao dịch đƣợc gọi là đa luồng (multi-threaded) khi các luồng con sinh ra đƣợc chạy
bên trong giao dịch đồng thời chạy song song với luồng cha đang thực thi giao dịch.
Khi một giao dịch đƣợc bắt đầu một vùng bộ nhớ gọi là log đƣợc cấp phát dùng để lƣu
lại bản sao của các biến dùng chung. Một luồng mới hay luồng con, khi đƣợc sinh ra
cũng sẽ tạo một bản sao các log giao dịch của luồng cha. Khi luồng cha thực hiện đóng
(commit) giao dịch, tất cả các luồng con đƣợc tạo bên trong luồng cha phải cùng đóng
với luồng cha. Chúng ta gọi kiểu đóng này là join commit, và thời điểm khi những
commit này xảy ra đƣợc gọi là thời điểm joint commit. Ở thời điểm join commit bộ
nhớ đƣợc cấp phát cho các log cũng đƣợc giải phóng. Join commit đóng vai trò nhƣ sự
đồng bộ ngầm của các luồng song song. Chính vì hình thức đồng bộ này mà các luồng
song song bên trong một giao dịch không hoàn toàn chạy độc lập.
Và vấn đề cần trả lời ở đây là liệu ở thời điểm chạy chƣơng trình, liệu lƣợng bộ
nhớ cần cấp phát cho các log có vƣợt quá tài nguyên bộ nhớ của máy, hay chƣơng
trình có thể chạy một cách trơn tru mà không gặp phải bất kỳ lỗi nào nhƣ hết bộ nhớ.
Để trả lời cho câu hỏi này, chúng ta cần phải xác định đƣợc biên bộ nhớ của chƣơng
trình giao dịch hay chính là cận trên bộ nhớ đƣợc cấp phát cho các log ở thời điểm
biên dịch.
Ở các nghiên cứu trƣớc đây [2, 11], một hệ thống kiểu đƣợc phát triển để đếm số
lƣợng log lớn nhất mà cùng tồn tại ở một thời điểm khi chƣơng trình đang chạy. Con
số này chỉ cho thông tin thô về bộ nhớ đƣợc sử dụng bởi các log giao dịch. Để quyết
định thêm chính xác lƣợng bộ nhớ lớn nhất mà các log giao dịch có thể sử dụng, trong
nghiên cứu [1] các tác giả đã đề xuất phƣơng pháp giải quyết vấn đề với việc tính đến
kích thƣớc của mỗi log. Đây cũng là điểm cải tiến của hƣớng tiếp cận mới này so với
các hƣớng tiếp cận trƣớc đó.
Nhƣ vậy, bài toán cần giải quyết ở đây có thể phát biểu nhƣ sau: Tính toán lƣợng
bộ nhớ yêu cầu lớn nhất cho toàn bộ chƣơng trình giao dịch khi biết kích thƣớc của
các log.
5
1.2. Hƣớng tiếp cận
Để giải quyết bài toán đặt ra, trƣớc hết chúng ta sẽ viết các chƣơng trình giao
dịch bằng một ngôn ngữ dành riêng cho nó, cụ thể là ngôn ngữ TM sẽ đƣợc trình bày
trong chƣơng 3.
Để thêm thông tin về kích thƣớc của mỗi log, chúng ta sẽ mở rộng lệnh bắt đầu
giao dịch trong các nghiên cứu trƣớc để chứa thông tin này. Sau đó chúng ta phát triển
một hệ thống kiểu để đánh giá tài nguyên bộ nhớ log mà các giao dịch có thể yêu cầu.
So với các nghiên cứu trƣớc [2,11] thì ý tƣởng về các cấu trúc kiểu trong nghiên
cứu [1] không có gì thay đổi. Tuy nhiên, các ngữ nghĩa kiểu và các quy tắc kiểu là mới
và khác so với các nghiên cứu trƣớc đây.
1.3. Ví dụ minh họa
6
CHƢƠNG 2. MỘT SỐ KIẾN THỨC CƠ SỞ
2.1. Hệ thống kiểu
2.1.1. Giới thiệu về hệ thống kiểu
Về định nghĩa hệ thống kiểu, có rất nhiều quan điểm đƣợc đƣa ra. Trong các
ngôn ngữ lập trình, hệ thống kiểu đƣợc định nghĩa là tập các quy tắc để gán thuộc tính
đƣợc gọi là kiểu cho các cấu trúc của một chƣơng trình máy tính bao gồm các biến,
biểu thức, các hàm, hoặc module...Theo lý thuyết ngôn ngữ, một hệ thống kiểu là một
tập các quy tắc quy định cấu trúc và lập luận cho ngôn ngữ. Trong lập trình, hệ thống
kiểu đƣợc định nghĩa là một cơ chế cú pháp ràng buộc cấu trúc của chƣơng trình bằng
việc kết hợp các thông tin ngữ nghĩa với các thành phần trong chƣơng trình và giới hạn
phạm vi của các thành phần đó.
Mục đích cơ bản của hệ thống kiểu là ngăn chặn các sự cố do các lỗi thực thi
trong quá trình chƣơng trình chạy [3, 6]. Nó đƣợc thực hiện bằng cách định nghĩa các
giao diện giữa các phần khác nhau của một chƣơng trình máy tính, và sau đó kiểm tra
xem các thành phần đã đƣợc ghép nối nhất quán hay chƣa. Việc kiểm tra này có thể
xảy ra tĩnh (tại thời gian biên dịch), hoặc động (tại thời gian chạy), hoặc kết hợp cả
kiểm tra tĩnh và động. Ngoài ra hệ thống kiểu còn đƣợc sử dụng với nhiều mục đích
khác, chẳng hạn nhƣ cho phép tối ƣu hóa trình biên dịch nhất định, cung cấp một hình
thức tài liệu…
2.1.2. Các thuộc tính của hệ thống kiểu
Một hệ thống kiểu có một số thuộc tính sau:
Khả năng kiểm chứng: Hệ thống kiểu phải có thuật toán kiểm tra kiểu để phân
loại các chƣơng trình. Một hệ thống kiểu phải chủ động nắm bắt lỗi thực thi trƣớc khi
chúng xảy ra.
Tƣờng minh: Các lập trình viên có thể dự đoán nếu một chƣơng trình vƣợt qua
bộ kiểm tra kiểu. Nếu nó lỗi khi kiểm tra, nên tìm đƣợc lí do một cách dễ dàng.
Khả năng thực thi: Các biến, biểu thức nên đƣợc kiểm tra tĩnh càng nhiều càng
tốt. Mặt khác, chúng cũng cần đƣợc kiểm tra động. Sự nhất quán cần đƣợc kiểm chứng
một cách thƣờng xuyên.
2.1.3. Các ứng dụng của hệ thống kiểu
Hệ thống kiểu đóng vai trò quan trọng trong công nghệ phần mềm và trong lĩnh
vực bảo mật mạng.
Đối với công nghệ phần mềm, nó đƣợc sử dụng trong trình biên dịch của các
ngôn ngữ lập trình, tối ƣu hóa, trong cơ sở dữ liệu và thậm chí là mô hình các ngôn
ngữ tự nhiên… Trong ngôn ngữ lập trình, hệ thống kiểu có các chức năng chính sau :
a. Phát hiện i
b. Tr u tƣ ng h a
c. Làm tài iệu
7
d. Tăng hiệu quả
2.2. Giao dịch và bộ nhớ giao dịch phần mềm ( Software Transactional Memory-
STM)
2.2.1. Giao dịch (Transaction)
Một giao dịch là một luồng điều khiển mà áp dụng một chuỗi hữu hạn các thao
tác nguyên thủy (primitive) vào bộ nhớ [8]. Hay nói cách khác một giao dịch là một
thực thi của một chƣơng trình ngƣời dùng.
2.2.2. Bộ nhớ giao dịch phần mềm (Software Transactional Memory- STM)
Từ năm 1986, ý tƣởng cung cấp hỗ trợ phần cứng cho các giao dịch đã ra đời.
Cho đến 1995 Nir Shavit và Dan Touitou đã mở rộng ý tƣởng này cho bộ nhớ giao
dịch phần mềm. Kể từ đó, nó đã trở thành trọng tâm của các các lý thuyết nghiên cứu
chuyên sâu và các ứng dụng thực tế.
Trong khoa học máy tính, bộ nhớ phần mềm giao dịch (STM) là một cơ chế
kiểm soát đồng thời tƣơng tự nhƣ các giao dịch cơ sở dữ liệu cho việc kiểm soát quyền
truy cập vào bộ nhớ dùng chung trong tính toán song song. Đây là một phƣơng pháp
thay thế cho cơ chế đồng bộ dựa trên khóa. STM là một chiến lƣợc thực hiện trong
phần mềm, chứ không phải là một thành phần phần cứng.
8
CHƢƠNG 3. NGÔN NGỮ GIAO DỊCH
Trong chƣơng này chúng ta sẽ nghiên cứu về cú pháp và ngữ nghĩa của một ngôn
ngữ giao dịch đƣợc gọi là TM (Transactional Memory).
Một chƣơng trình TM bắt đầu bằng lệnh onacid(n) (với n biểu diễn kích thƣớc bộ
nhớ đƣợc cấp phát cho log khi mở một giao dịch mới )và kết thúc bằng lệnh commit.
Dƣới đây, chúng ta sẽ tìm hiểu cú pháp và ngữ nghĩa của TM. Trong đó, cú
pháp nhằm mô tả các thành phần của một ngôn ngữ. Và các công thức thể hiện hoạt
động của chƣơng trình ở các mức cục bộ (bên trong một luồng), ở mức toàn cục (trong
các luồng song song). Ngữ nghĩa thể hiện cách thức một chƣơng trình đƣợc thực hiện
nhƣ thế nào.
3.1. Cú pháp của TM [1]
Bảng 3.1 Bảng cú pháp của TM
3.2. Các ngữ nghĩa động
Ngữ nghĩa của TM đƣợc đƣa ra bởi 2 mức tập hợp của các quy tắc hoạt động,
tƣơng ứng với các ngữ nghĩa cục bộ và toàn cục.
Môi trƣờng thực thi (toàn cục) đƣợc cấu trúc nhƣ là một tập của các môi trƣờng
cục bộ. Mỗi môi trƣờng cục bộ là một chuỗi các log cùng với kích thƣớc của nó.
Môi trƣờng cục bộ và môi trƣờng toàn cục đƣợc định nghĩa nhƣ sau:
3.2.1. Ngữ nghĩa cục bộ
Các ngữ nghĩa cục bộ liên quan tới việc đánh giá một luồng đơn và các giao dịch
cục bộ ở dạng . và ở đây là các môi trƣờng cục bộ, trong khi và
là các biểu thức sẽ đƣợc thực thi bởi luồng, có nghĩa là một biểu thức đƣợc đánh giá
trong môi trƣờng cục bộ E thì nó sẽ đƣợc chuyển thành một biểu thức , tƣơng ứng
với nó môi trƣờng cục bộ E sẽ chuyển thành môi trƣờng cục bộ .
Định nghĩa 1(Local environment – Môi trường cục bộ) Một môi trường cục bộ
là một chuỗi tuần tự của các log và kích thước của nó: l1:n1;…lk:nk. Môi trường
không có phần tử nào được gọi là môi trường rỗng và ký hiêu bởi
3.2.2. Ngữ nghĩa toàn cục
[1].
Ở mức toàn cục, ngữ nghĩa sẽ có dạng: hoặc trong
đó: là môi trƣờng toàn cục và là tập các tiến trình có dạng . Môi trƣờng toàn
cục là một tập các môi trƣờng cục bộ mà không rỗng.
Định nghĩa 2 (Global environment – Môi trường toàn cục)
9
Một môi trường toàn cục là một tập các luồng và môi trường cục bộ của nó,
được viết là: , với là tên luồng và là môi trường cục bộ
của luồng [1].
Bảng 3.2. Bảng ngữ nghĩa động của TM
10
CHƢƠNG 4. HỆ THỐNG KIỂU CHO CHƢƠNG TRÌNH GIAO DỊCH
Mục đích chính của hệ thống kiểu là để xác định lƣợng bộ nhớ lớn nhất mà một
chƣơng trình TFJ có thể yêu cầu.
Kiểu của một thành phần (term) trong hệ thống đƣợc tính toán từ chuỗi các số có
dấu, là một biểu diễn trừu tƣợng của thành phần hành vi giao dịch liên quan tới bộ nhớ
log.
4.1. Các kiểu
Theo [1], các kiểu của chúng ta là các chuỗi giới hạn trên tập đƣợc gọi là chuỗi
số có dấu. Một số có dấu là một cặp của các dấu và các số tự nhiên không âm N+.
Chúng ta sử dụng 4 dấu {+, −, ¬, #} cho việc ký hiệu tƣơng ứng mở, đóng, joint
commit, và bộ nhớ tích lũy lớn nhất mà các log sử dụng.
Tập tất cả các chuỗi số có dấu đƣợc ký hiệu là TN.
Do đó TN= {+n, –n,¬n, #n}
Ý nghĩa của những số có dấu này đƣợc mô tả nhƣ sau :
Số có dấu +n chỉ ra rằng mở giao dịch có kích thƣớc của log là n đơn vị bộ
nhớ. Lƣu ý là ngữ nghĩa này khác so với các nghiên cứu [5,6], ở đó nó ký
hiệu cho n lệnh mở giao dịch onacid liên tiếp.
Số có dấu –n có nghĩa là có n lệnh commit liên tiếp.
¬
Số có dấu n có nghĩa là n luồng yêu cầu sự đồng bộ ở thời điểm Join
commit.
#
Số có dấu n chỉ ra số đơn vị bộ nhớ lớn nhất hiện tại mà thành phần sử
dụng là n.
Định nghĩa 5 (Chuỗi chuẩn tắc): Một chuỗi gọi là chuẩn tắc nếu tag(S) không
|
|
chứa „−−‟, „##‟, „+ −‟, „+ ¬‟, „+ #¬‟ hoặc „+# −‟ và >0 với mọi i [1].
Định nghĩa 6 (Rút gọn):
Hàm rút gọn seq được định nghĩa đệ quy như sau:
seq(S) = S khi S là chuẩn tắc
seq( S #m #n S‟) = seq( S # max(m,n)S‟)
seq( S −m −n S‟) = seq( S − (m+n)S‟)
seq( S +k #l −n S‟) = seq( S #(l+k) – (n-1) S‟) [1]
Định nghĩa 7 (Cộng):
Cho S= s1...sk là một chuỗi chuẩn tắc mà + không nằm trong {S } và giả sử
i=first(S, −) . Thì hàm cộng join(S) định nghĩa đệ quy thay thế − trong S bởi ¬ như
sau:
join (S)= S
nếu i=0;
¬
−
| |
join(S) = s1...si-1 1 join ( ( – 1) si+1 …sk ) ngược lại [1]
Định nghĩa 8 (Gộp):
11
Cho S1 và S2 là các chuỗi cộng mà số các thành phần ¬ trong S1 và S2 là như
nhau (có thể là 0). Hàm merge được định nghĩa đệ quy như sau :
Merge (# m1, # m2)= # (m1 + m2 )
#
¬
#
¬
#
¬
Merge ( m1 n1 , m2 n2 )= (m1 + m2 ) (n1 + n2 )merge( ) [1]
Định nghĩa 9 (Chọn) :
Cho S1 và S2 là 2 chuỗi mà nếu chúng ta loại bỏ thành phần # từ chúng, thì hai
chuỗi còn lại là giống hệt nhau. Hàm alt được định nghĩa đệ quy như sau :
alt ( #m1 , #m2 )= #max( m1,m2)
#
*
#
*
#
*
alt ( m1 n1 , m2 n2 )= max(m1, m2 ) n alt ( ) [1]
4.2. Các quy tắc kiểu
Bảng 4.1 Các quy tắc kiểu
Trong bảng trên, quy tắc T-ONACID cho phép chuyển onacid(n) thành +n.
Quy tắc T- COMMIT cho phép chuyển commit thành -1;
Quy tắc T- SPAWN chuyển S từ chuỗi cộng và đánh dấu các kiểu mới bởi do đó
chúng ta có thể gộp nó với chuỗi của luồng cha trong hàm T- MERGE.
Quy tắc T- PREP cho phép chúng ta tìm kiểu phù hợp cho e trong T- MERGE.
Quy tắc T-JC giải quyết join commit giữa các luồng chạy song song và sử dụng tời
công thức jc trình bày ở định nghĩa 10. Trong đó, phần tử + cuối cùng trong S1, gọi là
12
+n sẽ đƣợc kết hợp với phần tử ¬ đầu tiên trong S2, gọi là ¬l (Hình 4.1). Nhƣng sau +n,
# ’
có thể có thành phần #, gọi là n , do vậy cận của các đơn vị bộ nhớ cục bộ đƣợc sử
dụng bởi thành phần có kiểu +n#n’ là n+ n’. Trƣớc ¬l có thể có #l‟, vì vậy khi thực hiện
join commit các thành phần có kiểu ¬l với giao dịch bắt đầu của nó có kiểu +n, kiểu
của các phân đoạn sẽ là l‟+l*n. Sau khi kết hợp +n từ S1 với ¬l từ S2 chúng ta có thể rút
gọn các chuỗi mới và lặp lại các join commit của jc. Do đó hàm jc đƣợc xác định nhƣ
sau :
Định nghĩa 10 (Join commit):
Hàm jc được xác định đệ quy như sau :
# ‟ # ‟¬
#
‟
#
‟
#
‟
jc( +n n , l l ) =jc(seq( (n+ n ), seq( (n+n ),seq( ( l + l*n) )) nếu l>0
#
# ‟
#
‟
‟
jc( n, l )= seq( max(n , l ) )
ngược lại [1]
Hình 4.1 Các luồng song song Joincommit
Định nghĩa 11 (Chƣơng trình well- typed): Một thành phần e được gọi là
well- typed nếu tồn tại một dẫn xuất cho e mà 0 e : # n với một số n [1].
Do các kiểu phản ánh hành vi của một thành phần, vì vậy kiểu của một chƣơng
trình định kiểu tốt (well- typed) chứa chỉ một chuỗi #n ở đó n là số đơn vị bộ nhớ lớn
nhất đƣợc sử dụng khi thực hiện chƣơng trình.
Dƣới đây chúng ta sẽ sử dụng các lý thuyết ở trên để giải bài toán tính cận trên cho
chƣơng trình trong hình 1.3.
Để thuận lợi cho việc tính toán, trƣớc hết ta chia nhỏ chƣơng trình thành các biểu thức
e1 = onacid (1); onacid (2);
e2 = spawn (onacid (4); commit; commit; commit; commit)
e3 =onacid (3);
e4 = spawn (onacid (5); commit; commit; commit; commit)
e5 = commit;onacid (6);commit;commit;onacid (7);commit;commit;
Trƣớc hết ta tính kiểu cho e4;
Sử dụng các quy tắc T-ONACID, T-COMMIT và T-SEQ ta có kiểu của
Onacid (5);commit;commit;commit;commit : #5¬1¬1¬1
Áp dụ ng T-SPAWN, ta đƣợc
6 e4 :(#5¬1¬1¬1)p
Tiếp theo ta tính e5 ; cũng áp dụng các hàm T-ONACID, T-COMMIT và T-SEQ ta có
13
6 e5 : −1#6−1#7−1
Sử dụng T-PREP, chúng ta có kiểu phù hợp với S4 , tiếp tục áp dụng hàm T- MERGE
ta đƣợc
6 e45 : (#5¬2#6¬2#7¬2)p
Với -3 e3 :+3, chúng ta áp dụng T-JC ta đƣợc
3 e345: #11¬2#7¬2
vì jc(+3, #5¬2#6¬2#7¬2) = jc( seq(#3), seq(# (5+3*2) #6¬2#7¬2))
=jc(#3, #11¬2#7¬2)= #11¬2#7¬2;
Tƣơng tự ta tính đƣợc kiểu của e2 : 3 e3 : (#4¬1¬1)p. Kiểu của e3 phù hợp với e345 , do
vậy ta lại sử dụng hàm T-MERGE và đƣợc kiểu của e2345
3 e 2345 : #15¬3#7¬3
Áp dụng T-JC cho e1 và e2 ta đƣơc
0 e12345 : #24
#
# ¬
#
vì jc(+1+2, 15¬3#7¬3)= jc(seq(+1#2),seq(#21, 7 3)= jc(+1#2, 21¬3)= jc(seq(#3),
seq(#24)) = #24
Vậy chƣơng trình này là well-typed và lƣợng bộ nhớ lớn nhất mà chƣơng trình cần là
24 đơn vị bộ nhớ.
14
CHƢƠNG 5. XÂY DỰNG CÔNG CỤ VÀ THỰC NGHIỆM
5.1. Giới thiệu ngôn ngữ lập trình/ nền tảng
Ngôn ngữ lập trình đƣợc sử dụng để xây dựng công cụ trong luận văn này là
ngôn ngữ C#, trên nền .NET. Đây một ngôn ngữ lập trình ứng dụng, ngôn ngữ biên
dịch, ngôn ngữ đa năng đƣợc phát triển bởi Microsoft. Ngôn ngữ C# là một ngôn ngữ
đƣợc phát triển từ C, C++ và Java, nhƣng nó đƣợc tạo từ nền tảng phát triển hơn. C#
đƣợc thêm vào những đặc tính mới để giúp cho nó uyển chuyển và dễ sử dụng hơn.
Nhiều đặc tính trong ngôn ngữ C# khá giống với ngôn ngữ Java. Cụ thể, C# có những
đặc tính cơ bản sau :
Đơn giản, dễ học : Chỉ có khoảng hơn 80 từ khóa và mƣời mấy kiểu dữ
liệu đƣợc dựng sẵn
Gần gũi với các ngôn ngữ lập trình thông dụng nhƣ C, C++, Java
Xây dựng dựa trên nền tảng của những ngôn ngữ lập trình mạnh nên thừa
hƣởng đƣợc các ƣu điểm của các ngôn ngữ đó.
Hƣớng đối tƣợng
Mạnh mẽ và mềm dẻo
Cung cấp những đặc tính hƣớng thành phần nhƣ property, event…
C# có bộ Garbage Collector sẽ tự động thu gom vùng nhớ khi không sử
dụng nữa.
Hỗ trợ khái niệm giao diện
Song hành với ngôn ngữ C# là nền tảng .NET Framework. Đây là một nền tảng
lập trình và cũng là một nền tảng thực thi ứng dụng chủ yếu trên hệ điều Windows. Nó
cũng đƣợc phát triển bởi Microsoft và bao gồm 2 thành phần chính:
CLR: Các chƣơng trình đƣợc viết trên nền.NET sẽ đƣợc triển khai trong
môi trƣờng đƣợc gọi là CLR (Common Language Runtime). Môi trƣờng
phần mềm này đóng vai trò là một máy ảo cung cấp các dịch vụ nhƣ bảo
mật, quản lý ngoại lệ hay bộ nhớ.
Thƣ viện các lớp: .NET framework gồm nhiều lớp thƣ viện, những thƣ
viện này sẽ hỗ trợ các lập trình viên trong việc xây dựng giao diện, kết nối
cơ sở dữ liệu, giao tiếp mạng…
5.2. Xây dựng công cụ và thực nghiệm
Trong phần này của luận văn, dựa vào các quy tắc kiểu đã đƣợc đề cập ở chƣơng
4, tôi sẽ xây dựng thuật toán tính kiểu đề giải quyết bài toán đã nêu trong chƣơng 2.
Bƣớc tiếp theo, dựa trên thuật toán có đƣợc viết một chƣơng trình bằng ngôn ngữ C#
để tính toán cận trên tài nguyên cho một chƣơng trình giao dịch
Trƣớc tiên để xây dựng thuật toán ta quy ƣớc một số ký hiệu đƣợc sử dụng để biểu
diễn một chuỗi số có dấu khi lập trình nhƣ sau:
{+n, −n, #n,! n } ( trong đó n là số tự nhiên) tƣơng ứng với các thành phần dạng
15
{ n, n, n, n } đã đề cập trong phần 4.1
Chúng ta sẽ chuyển đổi mã của chƣơng trình giao dịch thành một chuỗi gồm các
dấu, các số và các dấu đóng mở ngoặc tƣơng ứng với các lệnh sinh một luồng mới và
đóng luồng. Cụ thể:
onacid (n): Tƣơng ứng với chuỗi “+n”;
commit: Tƣơng ứng với “-1”;
spawn: Tƣơng ứng với “( )” – Khởi tạo một luồng
Qua bƣớc chuyển đổi các thành phần trên, ta sẽ kết xuất đƣợc một xâu là đầu vào để
thực hiện tính toán.
Chƣơng trình đƣợc xây dựng bao gồm các phƣơng thức cơ bản sau:
CalculResourses (string Input): Phƣơng thức thực hiện việc tính cận trên bộ nhớ
log của chƣơng trình sử dụng giao dịch. Phƣơng thức này sẽ gọi tới các phƣơng
thức Seq, Joint, Merge, JointCommit đƣợc trình bày ở bên dƣới.
Seq (string InputString): Phƣơng thức rút gọn một chuỗi gồm dấu và số.
Joint (string InputString): Phƣơng thức chuyển các dấu “─ ” trong chuỗi đã
đƣợc rút gọn (sau khi thực hiện hàm Seq ở trên) về dấu “⌐”.
Merge (string s1, string s2): Phƣơng thức gộp 2 chuỗi chuẩn tắc.
JoinCommit(string s1, string s2): Phƣơng thức jointcommit 2 chuỗi chuẩn tắc
Sau đây chúng ta sẽ đi xây dựng thuật toán cụ thể cho các phƣơng thức đã nêu ở
trên:
5.2.1. Thuật toán rút gọn (chính tắc h a) một chu i
5.2.1.1. Mô tả thuật toán:
Thuật toán dựa trên các quy tắc đƣợc trinh bày trong định nghĩa 6, mục 4.1.
Đầu vào: Một chuỗi số có dấu chƣa đƣợc chính tắc, cho trƣớc các quy tắc rút gọn nhƣ
sau:
seq(S) = S khi S là một chuỗi chính tắc;
seq(S#m#nS') = seq(S#max(m,n)S')
seq(S-m-nS') = seq(S-(m+n)S')
seq(S+m#l−nS') = seq(S # (m+ 1) − (n - 1)S')
Đầu ra: Chuỗi S đã đƣợc rút gọn hay chính tắc
5.2.2. Thuật toán Cộng (Joint)
5.2.2.1. Mô tả thuật toán
Thuật toán dựa trên các quy tắc đƣợc trinh bày trong định nghĩa 7, mục 4.1
Đầu vào: Chuỗi có dấu chính tắc S không chứa dấu +, và i là vị trí chứa dấu – đầu
tiên trong chuỗi S, i # 0. Hàm join(S) đƣợc định nghĩa đệ quy nhƣ sau:
join(S) = S nếu i=0;
join(S) = s1…si-1 ¬1 join (−(|si| - 1) si+1…sk) nếu i≠0;
Đầu ra: Chuỗi S chỉ chứa dấu # và ⌐ ( trong lập trình dùng ký hiệu “!” thay cho ⌐)
16
5.2.3. Thuật toán gộp (Merge)
5.2.3.1. Mô tả thuật toán
Thuật toán dựa trên các quy tắc đƣợc trinh bày trong định nghĩa 8, mục 4.1
Đầu vào: S1, S2 là 2 chuỗi có dấu đã chính tắc, với số phần tử chứa dấu “¬” bằng
nhau (có thể bằng 0). Hàm merge định nghĩa đệ quy nhƣ sau:
Merge (S1, S2) = #(m1+m2) khi Si = #mi , i =1, 2
#
¬
#
¬
#
¬
Merge ( m1 n1 , m2 n2 )= (m1 + m2 ) (n1 + n2 ) Merge( )
Đầu ra: Chuỗi mới đƣợc gộp từ 2 chuỗi có dấu chính tắc ban đầu (chỉ chứa # và ⌐).
Để kiểm tra tính đúng đắn của thuật toán, ta kiểm tra với các đầu vào khác nhau
và đƣợc kết quả cho ở bảng sau:
Bảng 5.3 Bảng kết quả kiểm thử hàm gộp
Lƣợt
Chuỗi 1
!1
Chuỗi 2
!1
Kết quả
!2
1
2
3
4
5
!1
#1 !1
!1
#1!2
#2!2
#3
#2!3
#3
#6
#3!1#2!2
#1!1!1
#4!2#2#2!3
5.2.4. Thuật toán JoinCommit
5.2.4.1.Mô tả thuật toán:
Thuật toán dựa trên các quy tắc đƣợc trinh bày trong định nghĩa 10, mục 4.1
Đầu vào: S1, S2 là 2 chuỗi chính tắc.
Hàm joint commit đƣợc định nghĩa nhƣ sau:
Jc (#n1, #l1) = #max (n1, l1)
#
⌐
Jc (S‟1+n1 n2, #l1 l2 S'2) = jc (Sequence (S‟1 #(n1+n2)), Sequence( #(l1+12*n) S'2)
Đầu ra: Giá trị cận trên tài nguyên hoặc thông báo chƣơng trình thành lập không hợp
lệ
5.2.5. Thuật toán tính cận trên tài nguyên của chƣơng trình giao dịch
5.2.5.1. Mô tả thuật toán
Đầu vào: Chuỗi kết xuất đƣợc từ chƣơng trình Featherweight Java có sử dụng giao
dịch
Đầu ra: Giá trị cận trên tài nguyên bộ nhớ log của chƣơng trình hoặc thông báo
chƣơng trình thành lập không hợp lệ
17
KẾT LUẬN
Qua thời gian nghiên cứu và tìm hiểu đề tài, luận văn đã đƣợc hoàn thành và đạt
đƣợc những nội dung đề ra với mục tiêu chính là giải quyết bài toán tính cận trên bộ
nhớ log cho các chƣơng trình sử dụng giao dịch.
Về lý thuyết, luận văn đã trình bày đƣợc các kiến thức cơ sở về hệ thống kiểu
nói chung bao gồm định nghĩa hệ thống kiểu, các thuộc tính cơ bản của hệ thống kiểu
và ứng dụng của hệ thống kiểu trong thực tế. Ngoài ra, luận văn còn trình bày các khái
niệm cơ bản về giao dịch và bộ nhớ giao dịch phần mềm. Tiếp theo, cú pháp và ngữ
nghĩa của ngôn ngữ giao dịch TM cũng đƣợc giới thiệu trong luận văn. Từ cú pháp và
ngữ nghĩa của ngôn ngữ TM, luận văn đã trình bày phƣơng pháp xây dựng hệ thống
kiểu để xác định cận trên bộ nhớ log của chƣơng trình sử dụng giao dịch, dựa trên
nghiên cứu đƣợc các tác giả thực hiện trong bài báo [1]. Một chƣơng trình có giao dịch
đƣợc cấu thành từ các thành phần cơ bản, mỗi thành phần thể hiện hành vi giao dịch và
đƣợc định kiểu thông qua một dạng chuỗi số đặc biệt, chuỗi số có dấu. Hệ thống kiểu
đƣợc trình bày ở đây bao gồm các kiểu, các quy tắc kiểu trong đó chứa định nghĩa các
phép toán đƣợc sử dụng để định kiểu cho từng thành phần trong chƣơng trình sử dụng
giao dịch.
Về thực nghiệm, một công cụ đƣợc viết bằng ngôn ngữ C# đã đƣợc cài đặt để
tính cận trên bộ nhớ log của chƣơng trình sử dụng giao dịch. Chƣơng trình bao gồm
các phƣơng thức đƣợc xây dựng để thực hiện các phép toán nhƣ rút gọn một chuỗi số
có dấu, gộp 2 chuỗi số có dấu, Joincommit…Và đặc biệt là phƣơng thức để tính cận
trên bộ nhớ log. Chƣơng trình đã đƣợc thực nghiệm với nhiều chuỗi đƣợc kết xuất từ
các chƣơng trình giao dịch khác nhau và cho kết quả tƣơng đối chính xác.
Tuy nhiên, do thời gian có hạn và tài liệu nghiên cứu liên quan chƣa nhiều. Hơn
nữa, đây là một đề tài khó, đòi hỏi sự đầu tƣ nhiều về thời gian và công sức nên trong
luận văn này không tránh khỏi những hạn chế. Trong quá trình nghiên cứu về đề tài,
chúng tôi cũng nhận thấy các kết quả nghiên cứu mới chỉ dừng ở mức độ thực hiện và
kiểm chứng về mặt lý thuyết mà chƣa hề đƣợc kiểm chứng ở thực tế. Do vậy trong
tƣơng lai, hi vọng đề tài có thể đƣợc nghiên cứu và kiểm chứng ở thực tế. Nếu thành
công, các kết quả đạt đƣợc này sẽ đóng góp đáng kể vào việc tối ƣu các chƣơng trình
phần mềm và làm tăng hiệu quả sử dụng tài nguyên bộ nhớ.
18
TÀI LIỆU THAM KHẢO
Tiếng Anh
[1] Anh-Hoang Truong, Ngoc-Khai Nguyen, Dang Van Hung, and Dang Duc Hanh
(2016), “Calculate statically maximum log memory used by multi-threaded
transactional programs”, Theoretical Aspects of Computing – ICTAC 2016, pp. 82-99
[2] Anh-Hoang Truong, Dang Van Hung, Duc-Hanh Dang, and Xuan-Tung Vu, “A
type system for counting logs of multi-threaded nested transactional programs”, In
Nikolaj Bjørner, Sanjiva Prasad, and Laxmi Parida, editors, Distributed Computing
and Internet Technology - 12th International Conference, ICDCIT 2016, Proceedings,
volume 9581 of LNCS, pp. 157-168
[3] Hoang Truong (2006), Type Systems for Guaranteeing Resource Bounds of
Component Software, Dissertation for the degree Philosophiae Doctor (PhD)
University of Bergen, Norway
[4] Igarashi, Atsushi, Pierce Benjamin C, Wadler, Philip (2001), “Featherweight Java:
a minimal core calculus for Java and GJ”, Journal ACM Transactions on
Programming Languages and Systems, Volume 23, pp. 396- 450
[5] Jiang Hui,Lin Dong, Zhang Xingyuan, Xie Xiren(2001), “Type System in
Programming Languages”, Journal of Computer Science and Technology, Volume
16, pp. 286-292
[6] Luca Cardelli (1996), “Type system”, ACM Computing Surveys (CSUR),Volume
28 Issuse1, pp. 263-264
[7] Martin Steffen and Thi Mai Thuong Tran (2009), “Safe commits for Transactional
Featherweight Java”, Integrated Formal Methods, pp. 290-304
[8] N.Shavit, and D.Touitou (1995), “Software Transational Memory”, Proceeding
PODC '95 Proceedings of the fourteenth annual ACM symposium on Principles
distributed computing, pp 204-213
[9] Thi Mai Thuong Tran, O.Owe, and Martin Steffen (2010), “Safe typing for
transactional vs. lock-based concurrency in multi-threaded Java”, KSE '10
Proceedings of the 2010 Second International Conference on Knowledge and
Systems Engineering, pp.188-193
[10] Thi Mai Thuong Tran, Martin Steffen, and Hoang Truong (2011), “Estimating
Resource Bounds for Software Transactions”, SEFM 2013 Proceedings of the 11th
International Conference on Software Engineering and Formal Methods, Volume
8137, pp. 212-228
[11] Xuan-Tung Vu, Thi Mai Thuong Tran, Anh-Hoang Truong, and Martin Steffen.
“A type system for finding upper resource bounds of multi-threaded programs with
nested transactions”, In Symposium on Information and Communication Technologys
2012, SoICT ‟12, Halong City, Quang Ninh, Viet Nam, August 23-24, 2012, pp. 21-30
19
20 trang
19500
Free
Bạn đang xem tài liệu "Tóm tắt Luận văn Tính cận trên bộ nhớ log của chương trình sử dụng giao dịch", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- tom_tat_luan_van_tinh_can_tren_bo_nho_log_cua_chuong_trinh_s.pdf
