Chương 1. Giới thiệu 9 một chương trình giao dịch cơ bản hoạt động theo cơ chế STM và sử dụng hệ thống kiểu để xác định biên bộ nhớ giao dịch cho các chương trình này. - Chương 6 luận án tổng kết lại những vấn đề luận án đã giải quyết được, những vấn đề còn tồn tại cần tiếp tục nghiên cứu để có thể áp dụng kết quả vào thực tế. Ngoài ra, trong chương này, luận án cũng trình bày về những hướng nghiên cứu dự kiến trong tương lai, nhằm phát triển tốt hơn nữa sản phẩm của luận án để đóng góp cho cộng đồng nghiên cứu cũng như những người làm lập trình để xây dựng những phần mềm hoạt động hiệu quả, tiết kiệm tài nguyên.
9 Chương 2 KIẾN THỨC NỀN TẢNG VÀ NGHIÊN CỨU LIÊN QUAN Trong chương này, luận án trình bày những khái niệm, nguyên tắc cơ bản của lập trình tương tranh, cơ chế STM và hệ thống kiểu. Đây là những khối kiến thức cơ bản liên quan trực tiếp đến bài toán đặt ra và phương pháp giải quyết bài toán của luận án. Những kiến thức này là nền tảng để xây dựng các ngôn ngữ và các hệ thống kiểu trong các chương tiếp theo. Phần cuối chương, luận án trình bày về những hướng nghiên cứu trong và ngoài nước liên quan tới bài toán xác định biên tài nguyên tiêu thụ của các chương trình và những nghiên cứu về cơ chế STM trong các chương trình tương tranh.
Giới thiệu Mặc dù các chương trình tương tranh là một giải pháp hứa hẹn nhằm nâng cao hiệu suất của các hệ thống phần mềm. Tuy nhiên, việc viết các chương trình cho các hệ thống tương tranh là một nhiệm vụ khó khăn. Trong đó điểm mấu chốt là việc đồng bộ dữ liệu giữa các luồng, các tiến trình. Điều này đã thu hút nhiều nhà nghiên cứu với nhiều giải pháp được đề xuất trong các ngữ cảnh khác nhau.
Trong những năm gần đây, các hệ thống cơ sở dữ liệu đang hoạt động rất thành công trên các kiến trúc tương tranh. Các cơ chế kiểm soát tương tranh trong các hệ thống cơ sở dữ liệu được xử lý ngầm bởi các hệ quản trị cơ sở dữ liệu. Cốt lõi của các hệ thống này là các giao dịch, trong đó một giao dịch được hiểu là một chuỗi các lệnh để hoàn thành trọn vẹn một công việc và được sử dụng để truy cập và thao tác trên các đối tượng đang hoạt động một cách đồng thời. Một giao dịch có thể thành công khi nó thay đổi một số trạng thái trong cơ sở dữ liệu và không thành công hoặc bị hủy bỏ khi không có thay đổi về trạng thái của cơ sở dữ liệu.
Các giao dịch được thực hiện thông qua hệ thống cơ sở dữ liệu hoặc bằng các giao diện của các hàm, ẩn các chi tiết phức tạp khỏi người dùng và cung cấp giao diện đơn giản để giao tiếp [44]. Xuất phát từ sự thành công của các hệ thống cơ sở dữ liệu hoạt động theo kiến trúc tương tranh, những nhà nghiên cứu đã đưa ra ý tưởng về bộ nhớ giao 10 Chương 2. Kiến thức nền tảng và nghiên cứu liên quan 11 dịch trên cấp độ chương trình. Ý tưởng cơ bản của cơ chế bộ nhớ giao dịch ở cấp độ chương trình được phát triển từ cơ chế giao dịch trong các hệ thống cơ sở dữ liệu, mặc dù chúng cũng có những điểm khác nhau ở một số khía cạnh.
Một giao dịch trong các hệ thống cơ sở dữ liệu bao gồm một tập hợp các hướng dẫn không thể chia nhỏ và phải cùng thực thi tức thời cùng nhau. Các giao dịch trong cơ sở dữ liệu có bốn thuộc tính cơ bản là tính nguyên tố, tính nhất quán, tính độc lập và tính bền vững được gọi chung là ACID. Trong cơ chế bộ nhớ giao dịch phần mềm, một giao dịch cũng có các thuộc tính này. Luận án sẽ trình bày cụ thể hơn trong phần tiếp theo.
Việc điều khiển tương tranh thông thường được thực hiện bởi cơ chế dựa trên khóa. Ý tưởng chính của cơ chế này đó là, trong khi một giao dịch thực hiện trên một dữ liệu nào đó thì dữ liệu đó sẽ bị khóa lại không cho các giao dịch khác thao tác lên chúng. Khi giao dịch hoàn thành, các dữ liệu này mới được mở khóa cho các giao dịch khác sử dụng. Giải pháp dựa trên khóa là một giải pháp quen thuộc.
Tuy nhiên chúng tồn tại nhiều hạn chế, gây khó khăn cho người lập trình. Vì vậy, cơ chế bộ nhớ giao dịch ra đời, nhằm khắc phục những nhược điểm của cơ chế dựa trên khóa. Ý tưởng chính của cơ chế bộ nhớ giao dịch đó là, khi một luồng hoặc một giao dịch cần thao tác trên một dữ liệu dùng chung của chương trình, chúng sẽ sao chép các dữ liệu đó thành một bản sao để chúng sử dụng một cách độc lập. Sau khi hoàn thành giao dịch, chúng sẽ so sánh giá trị các bản sao với giá trị gốc để đồng bộ dữ liệu.
Nếu không xảy ra xung đột, giao dịch sẽ được hoàn thành, ngược lại giao dịch sẽ phải thực hiện lại, hoặc bị hủy bỏ. Như vậy, với cơ chế bộ nhớ giao dịch, người lập trình sẽ viết chương trình đơn giản hơn. Tuy nhiên, do việc tạo ra các bản sao của các dữ liệu dùng chung làm cho các chương trình tiêu tốn nhiều tài nguyên hơn. Thêm nữa, nếu các giao dịch phải hủy bỏ hoặc thực hiện lại nhiều lần sẽ dẫn đến giảm hiệu suất của chương trình.
Mục tiêu chính của luận án đó là đưa ra phương pháp để người lập trình có thể ước lượng tài nguyên tiêu thụ tối đa mà chương trình bộ nhớ giao dịch cần sử dụng, từ đó tối ưu chương trình nhằm nâng cao hiệu quả của việc sử dụng tài nguyên cũng như hiệu suất của chương trình. Do đặc điểm của chương trình giao dịch có các luồng và các giao dịch đan xen lồng nhau phức tạp, các luồng chạy song song nhưng không độc lập mà có các điểm đồng kết thúc nên việc phân tích, xác định tài nguyên chúng sử dụng sát với thực tế là một bài toán không tầm thường. Kiến thức nền tảng và nghiên cứu liên quan 12 Để hiểu rõ hơn bài toán đặt ra, phần tiếp theo luận án trình bày một số khái niệm, nguyên tắc cơ bản về cơ chế điều khiển tương tranh dựa trên khóa. Điều khiển tương tranh dựa trên khóa Trong lập trình tương tranh, cơ chế đồng bộ dựa trên khóa có ưu điểm đó là chúng được dùng phổ biến từ lâu và được hỗ trợ bởi nhiều ngôn ngữ lập trình.
Tuy nhiên, chúng có những hạn chế và gây ra những khó khăn cho người lập trình. Để hiểu rõ hơn về cơ chế này, trong phần này chúng ta xem xét một số khái niệm và đặc điểm của cơ chế đồng bộ dựa trên khóa. Khái niệm khóa Khóa là một đặc quyền truy xuất lên các đơn vị dữ liệu của các giao dịch mà bộ quản lý khóa có thể trao cho hay thu hồi lại từ các giao dịch. Khi một giao dịch đã khóa trên một đơn vị dữ liệu nào đó thì các giao dịch khác không được phép truy cập đến đơn vị dữ liệu đó cho đến khi nó nhả khóa.
Khi một giao dịch T thực hiện việc khóa đơn vị dữ liệu A, ta nói T đang giữ khóa A. Thông thường tại mỗi thời điểm, chỉ có một tập con các đơn vị dữ liệu bị khóa, vì vậy bộ quản lý khóa có thể lưu các khóa hiện hành trong một bảng (gọi là lock table) với các mẩu tin có dạng (A, L, T) (có ý nghĩa là giao dịch T có một khóa kiểu L trên đơn vị dữ liệu A). Có hai kỹ thuật khóa phổ biến đó là kỹ thuật khóa đơn giản và kỹ thuật khóa đọc/ghi. Kỹ thuật khóa đơn giản Một giao dịch khi có yêu cầu truy xuất đến đơn vị dữ liệu thì phải phát ra yêu cầu xin khóa (lock) trên đơn vị dữ liệu đó.
Nếu yêu cầu này được chấp nhận thì được quyền thao tác. Khi đó các giao dịch khác sẽ không được phép truy cập đến đơn vị dữ liệu đó cho đến khi giao dịch giữ khóa được giải phóng khóa (unlock). Ví dụ: Giả sử có hai giao dịch T1 và T2, mỗi giao dịch đều truy xuất đến một đơn vị dữ liệu A (mang giá trị một số nguyên), sau đó cộng thêm 1 vào A. Hai giao dịch này có thể được mô tả bởi chương trình P sau đây: P: Lock(A); Read(A); A=A+1; Write(A); Unlock(A); Nếu T1 bắt đầu trước, nó yêu cầu khóa trên A.
Giả sử rằng không có giao dịch nào đang khóa A, bộ quản lý khóa sẽ cho nó khóa này. Như vậy bây giờ chỉ có T1 mới có thể truy xuất A. Nếu T2 bắt đầu trước khi T1 kết thúc thì T2 phải đợi. Chỉ khi T1 thực hiện lệnh Unlock(A), hệ thống mới cho phép T2 tiến 12 Chương 2.
Kiến thức nền tảng và nghiên cứu liên quan 13 hành. Kết quả là T1 hoặc T2 sẽ hoàn tất trước khi giao dịch kia bắt đầu, và tác dụng là A được tăng thêm 2. Qua ví dụ trên ta thấy, nếu không phân biệt khóa cho thao tác đọc hay ghi thì rõ ràng sẽ có nhiều giao dịch phải chờ để được quyền khóa trên một đơn vị dữ liệu. Thực tế nhiều khi một giao dịch chỉ cần lấy giá trị của một đơn vị dữ liệu nhưng không thay đổi giá trị đó.
Vì vậy để giảm bớt tình huống phải chờ khi các giao dịch cùng đọc dữ liệu, người ta đề xuất tách yêu cầu khóa thành hai loại yêu cầu khóa riêng biệt đó là khóa đọc và khóa ghi. Kỹ thuật khóa đọc, ghi Khóa để đọc (còn gọi là shared lock): Khi một giao dịch T chỉ muốn đọc một đơn vị dữ liệu A, chúng sẽ thực hiện lệnh RLOCK(A), ngăn không cho bất kỳ giao dịch nào khác ghi giá trị mới vào A trong khi T đang khóa A. Tuy nhiên các giao tác khác vẫn có thể giữ một khóa đọc trên A cùng lúc với T. Một khóa như vậy gọi là khóa để đọc.
Khi một giao dịch đang giữ khóa ghi trên một đơn vị dữ liệu, các giao dịch khác không thể lấy được khóa đọc hoặc khóa ghi trên A cùng lúc với T. Điều kiện để xin khóa đọc/ghi: Một yêu cầu xin khóa RLOCK(A) chỉ được chấp nhận nếu A chưa bị khóa bởi một lệnh WLOCK trước đó. Một yêu cầu xin khóa WLOCK(A) chỉ được chấp thuận nếu A đang được tự do.