ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
****************
CÁC THUẬT TOÁN ĐIỀU KHIỂN TƯƠNG TRANH VÀ
LẬP LỊCH TRONG CƠ SỞ DỮ LIỆU THỜI GIAN THỰC
GIẢNG VIÊN HƯỚNG DẪN: PGS.TS. NGUYỄN HÀ NAM
NHÓM THỰC HIỆN:
(Nhóm 17)
LƯU MINH ĐỨC
CHU THỊ THẮM
HÀ NỘI – 03/2012
MỤC LỤC
MỞ ĐẦU 3
CHƯƠNG 1: CÁC HỆ THỐNG CSDL THỜI GIAN THỰC 4
1.1 Định nghĩa CSDL thời gian thực 4
1.2 Khái niệm về giao dịch và tính khả tuần tự 5
1.3. Mô hình CSDL thời gian thực 6
1.4. Lập lịch các giao dịch CSDL thời gian thực 7
1.5. Quản lý bộ nhớ 11
1.6 Lập lịch đọc/ghi (I/O) 13
CHƯƠNG 2: MỘT SỐ VẤN ĐỀ CHÍNH
TRONG CÁC HỆ THỐNG CSDL THỜI GIAN THỰC 17
2.1 Điều khiển đồng thời 15
2.2 Điều khiển tiếp nhận (Admission Control) 27
2.3 Quản lý bộ nhớ (Buffer management) 28
2.4 Lập lịch đĩa (Disk Scheduling) 31
KẾT LUẬN 32
TÀI LIỆU THAM KHẢO 33
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
MỞ ĐẦU
Trong những năm gần đây, các hệ thống cơ sở dữ liệu (CSDL) thời gian thực

đã và đang ngày càng được nghiên cứu và ứng dụng rộng rãi trong thực tế. Hệ thống
CSDL thời gian thực là sự kết hợp các hệ thống thời gian thực và hệ thống CSDL,
trong đó ngoài việc đóng vai trò tương tự như các hệ quản trị CSDL truyền thống gồm
lưu trữ, cung cấp các chức năng truy vấn và xử lý dữ liệu, hệ thống CSDL thời gian
thực còn phải đáp ứng các yêu cầu về mặt thời gian đối với dữ liệu được quản lý, các
ràng buộc thời gian của giao dịch, và các mục tiêu xác định về mặt hiệu năng.
Các lĩnh vực ứng dụng CSDL thời gian thực bao gồm cơ sở hạ tầng mạng, viễn
thông, thị trường tài chính, hàng không với các ứng dụng điển hình như hệ thống điều
khiển không lưu, giao dịch cổ phiếu chứng khoán, đặt chỗ máy bay, du lịch, tính cước
trả trước viễn thông Với sự phát triển nhanh chóng của mạng internet, viễn thông và
các dịch vụ toàn cầu hóa, đòi hỏi phải có những hệ thống CSDL thời gian thực để đáp
ứng được các yêu cầu của người dùng.
Trong lĩnh vực viễn thông, đang có sự phát triển vượt bậc của các thuê bao di
động với tỷ lệ các thuê bao trả trước chiếm tới hơn 80%. Do đó, bài toán tính cước
cho thuê bao điện thoại di động là hết sức quan trọng. Với xu hướng người dùng
chuyển sang sử dụng thuê bao di động mà dịch vụ trả trước là phần lớn, và trong
tương lai mạng viễn thông được nâng cấp lên thế hệ 4G với rất nhiều dịch vụ phong
phú, đa dạng thì các yêu cầu đặt ra cho bài toán tính cước trả trước là hết sức thiết
thực, cấp bách. Đó là làm sao phải tính toán được nhanh chóng, chính xác, kịp thời mà
vẫn phải đảm bảo được hoạt động của mạng lưới.
Như vậy, với thực tại và định hướng phát triển nêu trên, việc nghiên cứu các
vấn đề trong CSDL thời gian thực đặc biệt là yếu tố giải quyết tương tranh và lập lịch
là một trong những việc làm rất cấp bách.
Trang- 3
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
CHƯƠNG 1: CÁC HỆ THỐNG CSDL THỜI GIAN THỰC
Nội dung chính của chương này trình bày đầy đủ toàn bộ những lĩnh vực liên quan
của các Hệ thống CSDL thời gian thực và phân tích một số chủ đề đáng chú ý. Mở
đầu chương là phần giới thiệu các khái niệm về giao dịch và tính khả tuần tự
(serializability) thể hiện tính đúng đắn của các hệ CSDL truyền thống. Phần tiếp theo

trình bày định sự khác biệt giữa các hệ thống cấp thiết theo thời gian và các hệ CSDL
phi thời gian thực, và trình bày một mô hình của một Hệ CSDL thời gian thực để phác
họa sự pha trộn của các tài nguyên liên quan và biểu diễn các thành phần quan trọng
cần xem xét.
1.1 Định nghĩa CSDL thời gian thực
CSDL thời gian thực là một hệ thống tích hợp những đặc điểm chung của hệ thống
thời gian thực và CSDL. Nghĩa là, hệ thống CSDL thời gian thực có nhiệm vụ xử lý
các giao dịch CSDL và đáp ứng các yêu cầu ràng buộc xác định về mặt thời gian của
hệ thống.
Trên thực tế, việc thiết kế tổng thể một hệ thống CSDL thời gian thực bao hàm các
vấn đề có liên quan như sau:
1. Các mô hình hệ thống CSDL thời gian thực
2. Lập lịch các giao dịch CSDL thời gian thực.
a. Điều khiển đồng thời
b. Giải quyết tương tranh
c. Tắc nghẽn
3. Khả năng chịu lỗi và khắc phục sự cố
4. Điều khiển tiếp nhận (Admission Control)
5. Quản lý bộ nhớ
6. Lập lịch vào/ra và ghi đĩa
7. Tính toán không chính xác
8. Các hệ thống CSDL bộ nhớ chính (Main Memory Database Systems)
Trang- 4
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
9. Giảm thiểu hỗ trợ giao dịch, nghĩa là nới lỏng tính khả tuần tự (Relaxing
Serializability)
10.Tính bất biến truy nhập (Access Invariance)
11.Khả năng dự báo trước (Predictability)
Do sự pha trộn của nhiều vấn đề, các giới hạn, và mục đích nghiên cứu, nên ở đây chỉ
chú ý đến một số vấn đề trọng tâm. Các vấn đề khác sẽ được nghiên cứu sau.

1.2 Khái niệm về giao dịch và tính khả tuần tự
Trạng thái của một giao dịch bao gồm các bản ghi, sự xác nhận về các giá trị
của những bản ghi này, và một tập những chuyển đổi được phép có thể áp dụng cho
các giá trị của những bản ghi đó. Những sự xác nhận này được gọi là những ràng
buộc nhất quán.
Một điều có lẽ cần thiết để tạm thời vi phạm tính nhất quán của trạng thái hệ
thống trong khi sửa nó. Vì vậy, để chuyển đổi một trạng thái hệ thống nhất quán sang
một trạng thái nhất quán khác, hệ thống cung cấp các tập hành động theo dạng các
hoạt động đọc và ghi. Một giao dịch là một tập của những hành động như vậy, trong
khi bao gồm một sự chuyển đổi nhất quán của trạng thái hệ thống. Mỗi giao dịch, khi
được thực thi một mình, sẽ chuyển đổi một trạng thái nhất quán thành một trạng thái
nhất quán mới; nghĩa là, các giao dịch bảo trì tính nhất quán của thông tin CSDL thời
gian thực.
Các hệ thống quản lý CSDL truyền thống (DBMS) cấm những sự không nhất
quán bằng cách thỏa mãn bốn tính chất được kết hợp với các giao dịch, được gọi là
các tính chất ACID, đó là:
- A (Atomicity) Tính nguyên tử.
- C (Consistency) Tính nhất quán
- I (Isolation) Tính cô lập.
- D (Durability) Tính bền.
Trong khi mỗi giao dịch duy trì tính nhất quán của CSDL tại các giới hạn của
nó, các giao thức phục hồi được sử dụng để đảm bảo các tính chất nguyên tử và tính
bền. Cuối cùng, tính cô lập có thể được bảo đảm bởi các giá trị điều khiển đồng thời.
Trang- 5
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
Một sự thực thi được nói là có tính khả tuần tự nếu nó sinh ra cùng kết quả và
có cùng ảnh hưởng đến CSDL như một số sự thực hiện tuần tự của cùng các giao dịch.
Do các thực thi tuần tự là đúng đắn, và do mỗi thực thi tuần tự hóa có cùng ảnh hưởng
giống như một thực thi tuần tự, nên tính khả tuần tự trở thành khái niệm của tính đúng
đắn trong bất kỳ hệ quản trị CSDL thời gian thực nào.

1.3. Mô hình CSDL thời gian thực
Các giao dịch trong một hệ thống CSDL thời gian thực đi qua các thành phần khác
nhau cho đến khi kết thúc. Trong phần này đã xét một mô hình hệ thống CSDL thời
gian thực, như thể hiện trong hình 2.1 dưới đây, và mô tả các thành phần khác nhau
của nó. Phần còn lại sẽ xét hệ thống CSDL thời gian thực sẽ thừa nhận các giao dịch
là đơn vị có thể lập lịch ngược với các tác vụ trong các hệ điều hành thời gian thực
truyền thống. Nên, không như một số mô hình trong đó tải của hệ thống bao gồm chỉ
các tác vụ, và mỗi tác vụ có thể chứa một số các giao dịch trong đó, mô hình này bao
gồm có các giao dịch như các đơn vị lập lịch bộ đếm cho các tác vụ. Trong mô hình
này các tác vụ là đơn vị có thể lập lịch chính. Một mô hình phải xét các vấn đề sau:
- Kiểu của thời hạn cuối được kết hợp với một tác vụ, nghĩa là, soft, hard hay
firm.
- Kiểu của thời hạn cuối được kết hợp với các giao dịch trong một tác vụ;
nghĩa là soft, firm, hay hard
- Suy diễn một thời hạn cuối cho mỗi giao dịch trong một tác vụ cũng như tất
cả các tác vụ còn lại là phải khả thi lúc đầu,
- Các giao dịch trong một tác vụ là hợp tác hoặc độc lập,
- Sự thực thi của các giao dịch trong một tác vụ là tuần tự hoặc đồng thời,
- Nếu một thời hạn cuối của giao dịch là soft, thì những gì xảy ra nếu một
giao dịch nhỡ thời hạn cuối của nó? Đó là, nếu một giao dịch được phép
thực hiện đã qua thời hạn cuối của nó, thì một hành vi như vậy có thể hủy
hoại sự thực thi của các giao dịch khác trong tác vụ không?
- Nếu sự cố của giao dịch báo hiệu sự cố của tác vụ, thì sự cố của một giao
dịch đã làm hỏng thực thi của các giao dịch còn lại trong hệ thống.
Trang- 6
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
Hình 1.1 Mô hình CSDL thời gian thực
Mô hình trên được đề xuất với những hiểu biết tốt nhất đến thời điểm này, tuy
nhiên, một sự xem xét mô hình kỹ lưỡng vẫn là một lĩnh vực nghiên cứu mở. Mô hình
trên, nói cách khác, chỉ gồm các giao dịch, trong đó mỗi giao dịch có các thuộc tính

giống như các tác vụ trong các hệ điều hành thời gian thực truyền thống; ví dụ, các
thời hạn cuối, tính định kỳ, tính cấp thiết, mức ưu tiên, vv. Hơn nữa, CSDL tự nó
được xét với sự lập lịch các truy cập đến CSDL, mà là một vấn đề riêng biệt với lập
lịch CPU. Không những thế, lập lịch CPU được thừa nhận tồn tại ở một mức thấp hơn
mức CSDL.
Các mức ưu tiên có thể được gán cho các giao dịch thời gian thực theo nhiều
chiến lược giống nhau được dùng để gán mức ưu tiên cho các tác vụ thời gian thực.
1.4. Lập lịch các giao dịch CSDL thời gian thực
Yếu tố quyết định hiệu năng cơ bản trong một hệ thống CSDL thời gian thực là
chính sách được sử dụng để lập lịch các giao dịch. Một chính sách lập lịch xác định
khi nào dịch vụ được cấp cho giao dịch, do đó trực tiếp ảnh hưởng đến việc giao dịch
có đáp ứng được thời hạn cuối của nó hay không. Một điểm đặc biệt của các hệ thống
CSDL thời gian thực, ngoài các tài nguyên vật lý chuẩn, là các đối tượng dữ liệu được
Trang- 7
Điều khiển tiếp
nhận
Gán ưu tiên
Tính toán
Điều khiển đồng thời
Khởi tạo lại Truy nhập bộ đệm
Giao dịch
Yêu cầu/giải phóng
một đối tượng dữ liệu
Chặn
Đĩa
Nhỡ
Đạt
Ngắt
Gửi
Gửi lại

Hủy
Xác nhận
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
lưu trong CSDL, và các giao dịch truy nhập dữ liệu này phải được lập lịch theo các
mục tiêu hiệu năng thời gian thực.
Quy trình lập lịch của các giao dịch trong một hệ thống CSDL thời gian thực bao gồm
điều khiển đồng thời (concurrency control) và giải quyết tương tranh (conflict
resolution) và gián tiếp bao hàm phục hồi. Trong chương này sẽ thảo luận ngắn gọn
hai vấn đề trên, phần chi tiết sẽ được trình bày trong chương sau.
1.4.1 Điều khiển đồng thời
Một giao dịch CSDL điển hình là một chuỗi các thao tác được thực hiện trên
một CSDL. Các hệ CSDL thông thường được tập trung vào các tính chất ACID –
atomicity – nguyên tử, consistency – nhất quán, isolation – cô lập, và durability – tính
bền. Hệ quản trị CSDL phải bảo đảm những tính chất này trong khi cung cấp tối đa sự
đồng thời để tăng thông lượng, và duy trì tính đúng đắn của CSDL. Dữ liệu là tài
nguyên duy nhất, và vì thế yêu cầu một hình thức lập lịch riêng biệt so với các tài
nguyên phần cứng khác được xét. Tính khả tuần tự là khái niệm được thiết lập tốt về
tính đúng đắn cho việc lập lịch xen kẽ các hành động giao dịch. Các chính sách lập
lịch truy nhập dữ liệu được sử dụng trong một hệ CSDL nói chung được tham chiếu
đến như các giao thức điều khiển đồng thời. Các giao thức điều khiển đồng thời bảo
toàn tính toàn vẹn CSDL bằng cách giải quyết các thực thi đồng thời không tuần tự
theo một cách mà bao gồm một trật tự tuần tự hóa trong số các giao dịch tranh chấp.
Nghĩa là, điều khiển đồng thời là một cơ chế để đảm bảo sự không giao thoa của thực
thi giao dịch; đó là, tính cô lập của các giao dịch đang thực hiện đồng thời.
1.4.2 Giải quyết tương tranh
Các tranh chấp thường là kết quả của các thực thi đồng thời của các giao dịch
thực hiện các hành động không tương thích; nghĩa là, đọc và ghi trên cùng mục dữ
liệu tại cùng thời điểm. Các bộ lập lịch bất đồng khi phát hiện các tranh chấp tài
nguyên trong số các giao dịch và cách thức trong đó các tranh chấp được giải quyết
một khi chúng được tìm ra. Với các tài nguyên CSDL dùng chung, giao dịch bị đoạt

quyền thường phải được hoàn tác nếu các cập nhật không đúng chỗ được sử dụng [3],
[5].
Trang- 8
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
Khi một giao dịch yêu cầu một khóa trên mục dữ liệu trong khi khóa đã bị giữ,
trong chế độ tranh chấp, bởi một giao dịch khác, cả hai giao dịch đều có các ràng buộc
thời gian, thì chỉ một giao dịch có thể giữ khóa. Tranh chấp nên được giải quyết theo
các đặc điểm của các giao dịch tương tranh.
Giải quyết tương tranh Wound-Wait dựa trên mức ưu tiên
Kỹ thuật Wound-Wait ban đầu được đề xuất bởi Rosenkrantz để tránh tắc
nghẽn. Lược đồ ban đầu được thiết kế có sử dụng các nhãn thời gian. Tuy nhiên, hai
tác giả Abbott và Garcia-Molina đã sửa bản lược đồ để cho chúng sử dụng các mức ưu
tiên thay vì các nhãn thời gian và được áp dụng cho phiên bản được sửa để giải quyết
tương tranh trong các hệ CSDL thời gian thực. Phiên bản được sửa mới gọi là High-
Priority (HP) – Ưu tiên mức cao và như Priority-Abort (PA) – Hủy bỏ theo mức ưu
tiên [2], [3]. Phác họa thuật toán chung là như sau:
Gọi P(T
i
) là ưu tiên của giao dịch T
i
T
r
yêu cầu một khóa trên mục dữ liệu D
If (không tranh chấp) then T
r
truy nhập D
else - T
h
đang giữ mục dữ liệu được yêu cầu, giải quyết tương tranh như sau
if (P(T

r
) > P(T
h
)) then T
h
bị hủy bỏ
else T
r
đợi khóa, nghĩa là, chặn.
Trong lược đồ HP, nếu hai giao dịch tham gia vào một tranh chấp, thì giao dịch
có mức ưu tiên thấp hơn sẽ bị hủy nhằm giải phóng tài nguyên theo yêu cầu cho giao
dịch có mức ưu tiên cao hơn. Để bảo trì tính khả tuần tự, giao dịch có mức ưu tiên
thấp hơn bị đoạt quyền sẽ được hoàn tác, và khi được khởi động lại nó phải thực hiện
từ đầu. Tuy nhiên, một giao dịch ưu tiên thấp hơn trong phương pháp HP được phép
đợi giao dịch có mức ưu tiên cao hơn. Nên, tất cả các tranh chấp được giải quyết để
ưu tiên cho các giao dịch ưu tiên cao hơn. Phụ thuộc vào cách thức các mức ưu tiên
của các giao dịch được sinh ra, các giao thức giải quyết tương tranh khác nhau có thể
được tạo.
Trang- 9
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
1.4.3 Tắc nghẽn
Sự sử dụng các lược đồ khóa có thể gây ra một sự tắc nghẽn, do đó yêu cầu
phát hiện tắc nghẽn xảy ra, ngăn tắc nghẽn, hay tránh tắc nghẽn. Trong phần này sẽ
chỉ thảo luận sự phát hiện tắc nghẽn do nó là phương pháp được sử dụng nhiều nhất
trong các hệ quản trị CSDL thông thường. Một lược đồ phát hiện tắc nghẽn được gọi
khi một giao dịch ở trong hàng đợi một mục dữ liệu bị khóa. Bất cứ khi nào một tập
các giao dịch tham gia vào một vòng đợi thì một tắc nghẽn sẽ xảy ra. Nếu chu trình
tắc nghẽn được phát hiện, một trong số các giao dịch liên quan trong chu trình phải bị
hủy bỏ nhằm phá vỡ chu trình đó. Trong những trường hợp như vậy, một giao dịch
tham gia trong chu trình được chọn để hủy nhằm phá vỡ sự tắc nghẽn. Trong một hệ

CSDL thời gian thực, giao dịch bị hủy bỏ nên được chọn sao cho đảm bảo số lượng
lớn nhất các giao dịch còn lại có thể đáp ứng được thời hạn cuối của chúng. Các giao
dịch trong bất kỳ hệ thống cấp thiết thời gian nào bị hủy bỏ sẽ được xét các yêu cầu
thời gian của chúng ngoài việc hệ thống phải chịu một giá tối thiểu. Năm chính sách
giải quyết tắc nghẽn mà đưa các tính chất thời gian vào của các giao dịch và cái giá
của các hành động bị hủy như sau:
Chính sách 1: Luôn luôn hủy giao dịch gọi phát hiện tắc nghẽn.
Chính sách 2: Lưu vết chu trình tắc nghẽn, và hủy giao dịch chậm đầu tiên gặp phải
trong một chu trình tắc nghẽn. Nếu không có giao dịch chậm nào tìm thấy, thì hủy
giao dịch với thời hạn cuối lâu nhất.
Chính sách 3: Lưu vết chu trình tắc nghẽn, và hủy giao dịch chậm đầu tiên gặp phải
trong một chu trình tắc nghẽn. Nếu không có giao dịch chậm nào tìm thấy, thì hủy
giao dịch với thời hạn cuối sớm nhất.
Chính sách 4: Lưu vết chu trình tắc nghẽn, và hủy giao dịch chậm đầu tiên gặp phải
trong một chu trình tắc nghẽn. Nếu không có giao dịch chậm nào tìm thấy, thì hủy
giao dịch ít cấp thiết nhất.
Chính sách 5: Hủy giao dịch không khả thi với tính cấp thiết thấp nhất. Nếu tất cả các
giao dịch là khả thi, thì hủy một giao dịch khả thi với tính cấp thiết thấp nhất. Chính
sách này là nhạy cảm với độ chính xác của thời gian tính toán vì nó yêu cầu thông tin
Trang- 10
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
về thời gian thực thi còn lại; nên, tổng các yêu cầu thời gian thực thi tại thời điểm bắt
đầu mỗi giao dịch phải được biết.
1.5. Quản lý bộ nhớ
Khả năng sẵn sàng của bộ nhớ ảnh hướng đến thời gian đáp ứng giao dịch theo
hai cách.
Thứ nhất, trước khi một giao dịch bắt đầu thực hiện, bộ đệm (các trang nhớ)
phải được cấp phát cho giao dịch. Những bộ đệm này được sử dụng để lưu mã thực
thi, sao chép các tệp và dữ liệu được phân trang từ đĩa cứng, và bất cứ đối tượng tạm
thời nào được tạo ra. Phụ thuộc vào giao dịch, một số lượng bộ đệm nhất định phải

được cấp phát nhằm ngăn chặn giao dịch bị thất bại (ở đây khái niệm thất bại là hiện
tượng trong đó một giao dịch tiêu tốn hầu hết thời gian cho việc tráo đổi dữ liệu với
đĩa cứng). Khi bộ nhớ còn ít, một giao dịch có thể bị chặn không cho thực hiện. Tổgn
bộ nhớ sẵn sàng cho hệ thống vì thế giới hạn số lượng giao dịch thực thi đồng thời.
Thứ hai, một số ứng dụng, như xử lý ảnh, có yêu cầu bộ nhớ cao. Những sự
thực thi này sẽ chậm đáng kể nếu bộ nhớ ít và sự tráo đổi bộ nhớ được thực hiện
thường xuyên
Nhiệm vụ của một trình quản lý bộ đệm là cấp phát các bộ đệm nhớ cho các
giao dịch một cách thông minh sao cho các giao dịch có mức ưu tiên cao được hưởng
thời gian đáp ứng ngắn hơn. Một trình quản lý bộ đệm thường được xác định bằng
những chính sách tiếp nhận và thay thế bộ đệm. Các chính sách se được giải thích
ngắn gọn lần lượt dưới đây. Bên cạnh đó sẽ là các ví dụ cụ thể minh họa cách thức mà
các mức ưu tiên giao dịch được sử dụng để cải thiện hành vi thời gian thực của trình
quản lý. Khi một giao dịch T được đưa ra, trình quản lý bộ đệm sẽ quyết định có chấp
nhận thực hiện hay không. Quyết định này được gọi là chính sách tiếp nhận giao dịch.
Giả sử rằng các giao dịch là có thể cung cấp cho trình quản lý bộ đệm với số lượng bộ
nhớ nó cần để thực hiện thích hợp. Nếu có đủ không gian trống, giao dịch T được tiếp
nhận. Mặt khác, T bị chặn hay khác nữa là một số các giao dịch đang thực hiện có thể
bị treo và các bộ đệm của chúng được cấp phát lại cho giao dịch T. Trong trường hợp
thứ hai, sự quyết định các giao dịch nào sẽ bị treo có thể được xác định bằng mức ưu
Trang- 11
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
tiên của chúng. Một giải pháp đơn giản đưa ra để treo các giao dịch với mức ưu tiên
thấp nhất cho đến khi:
1. Đủ số bộ đệm đã được giải phóng cho T thực hiện, hay
2. Không có thêm các giao dịch không bị treo với mức ưu tiên nhỏ hơn T.
Trong trường hợp đầu, các bộ đệm được giải phóng được cấp phát cho T và T được
tiếp nhận. Với trường hợp thứ hai, T bị chặn do thiếu bộ nhớ.
Các chính sách thay thế truyền thống bao gồm LRU(Least Recently Used – được sử
dụng gần ít nhất), LFU (Least Frequently Used – được sử dụng thường xuyên ít

nhất), Hãy xét ví dụ một chính sách mang tên Priority-LRU, được đề xuất với việc
xem xét mức ưu tiên giao dịch là sự sử dụng bộ đệm mới xảy ra. Thuật toán này nhóm
các giao dịch thành m lớp ưu tiên. Tất cả các bộ đệm mà được sử dụng bằng một số
giao dịch trong lớp thứ i được đưa vào một danh sách L
i
và được nói rằng có mức ưu
tiên i. Vùng chứa bộ đệm vì vậy được tổ chức thành m danh sách: L
1
, L
2
, …, L
m
theo
mức ưu tiên của bộ đệm. Thuật toán Priority-LRU có thể được mô tả ngắn gọn bằng
các mã giả sau.
Priority-LRU(W
R
):
S :=
φ
;
(* Đưa bộ đệm ít được sử dụng gần đây nhất của mỗi danh sách vào S*)
FOR i := 1 TO m DO
x := bộ đệm ít được sử dụng gần đây nhất trong L
i
;
S := S ∪ {x};
END FOR
(* Lấy bộ đệm có mức ưu tiên thấp nhất trong S mà không là một trong các bộ
đệm được sử dụng gần đây nhiều nhất W

R
*)
WHILE S ≠
φ
DO
x := bộ đệm có mức ưu tiên thấp nhất trong S;
Trang- 12
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
(*Kiểm tra nếu x vừa mới được tham chiếu*)
IF x là một trong số các bộ đệm được truy nhập gần đây nhiều nhất W
R
THEN
S := S – {x};
ELSE
RETURN(x);
ENDIF;
END WHILE
RETURN (không có trang nào phù hợp);
Thuật toán Priority-LRU lấy một tham số, W
R
, để điều khiển tầm quan trọng tương đối
của tính chất mới xảy ra và mức ưu tiên. Ví dụ, khi W
R
được thiếp lập về 0, bộ đệm
được sử dụng gần đây nhất trong nhóm có mức ưu tiên thấp nhất được chọn. Một bộ
đệm có mức ưu tiên thấp luôn được chọn có lợi cho các bộ đệm có mức ưu tiên cao
hơn. Ngược lại, nếu W
R
được thiếp lập cao, thì các bộ đệm có mức ưu tiên thấp sẽ bị
ngắt nếu chúng mới được tham khảo gần đây.

1.6 Lập lịch đọc/ghi (I/O)
Với lập lịch CPU, các thuật toán lập lịch đĩa mà đưa vào các ràng buộc thời gian có
thể cải thiện đáng kể hiệu năng thời gian thực. Các thuật toán lập lịch CPU, như là
Earliest Deadline First và Highest Priority First, là những thuật toán đáng được xem
xét nhưng chúng phải được chỉnh sửa lại trước khi có thể áp dụng vào lập lịch
đọc/ghi. Lý do chính là thời gian tìm kiếm trên đĩa, phụ thuộc vào sự di chuyển đầu
đọc đĩa. Thứ tự trong đó các yêu cầu đọc/ghi được phục vụ, vì thế, có một ảnh hưởng
rộng lớn lên thời gian đáp ứng và thông lượng của phân hệ đọc/ghi [4]. Để minh họa,
hãy xét ví dụ sau như trong hình vẽ:
Trang- 13
Vị trí đầu đọc di chuyển
hiện tại theo hướng này
Yêu cầu A C D
B
đọc/ghi
Rãnh #: 0 1 2 3 4 5 6 7
8
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
Hình 2.2 Ví dụ lập lịch đĩa
Giả sử rằng có 4 yêu cầu A, B, C và D trong hàng đợi đọc/ghi với các mức ưu tiên của
chúng theo thứ tự sau:
Pr(A) > Pr(B) > Pr(C) > Pr(D)
Vị trí của dữ liệu cần thiết bởi mỗi yêu cầu được thể hiện ở hình vẽ trên. Nếu sử dụng
thuật toán Highest Priority First (HPF), thì thứ tự phục vụ sẽ là:
HPF: A, B, C, D.
Ta chú ý rằng trong trường hợp này, đầu đọc quét đĩa ngược và tiến bốn lần, hay 32
rãnh. Để ý rằng các yêu cầu có thể được thỏa mãn trong chỉ 11 dịch chuyển rãnh
(trong thứ tự D, B, C, A), rõ ràng HPF không phải là một cách thông minh để lập lịch
đầu đọc đĩa nếu thời gian đáp ứng hay thông lượng là một điều cần quan tâm.
Các thuật toán làm giảm sự dịch chuyển đầu đọc đĩa đã được nghĩ ra. Các thuật toán

này tập trung vào cách tối ưu sự dịch chuyển của đầu đọc dựa trên các yêu cầu đọc ghi
với các mức ưu tiên của chúng. Chi tiết một số thuật toán sẽ được đề cập ở chương
sau.
Trang- 14
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
CHƯƠNG 2: MỘT SỐ VẤN ĐỀ CHÍNH TRONG CÁC HỆ
THỐNG CSDL THỜI GIAN THỰC
Nội dung chương này sẽ trình bày chi tiết một số vấn đề quan trọng đã được quan tâm
nghiên cứu nhiều trong CSDL thời gian thực. Đó là các vấn đề điều khiển đồng thời,
quản lý bộ nhớ và lập lịch ghi đĩa.
2.1 Điều khiển đồng thời
2.1.1 Điều khiển đồng thời theo khóa (Locking Concurrency Control)
Việc khóa các mục dữ liệu là một kỹ thuật nhằm ngăn chặn nhiều giao dịch truy nhập
cùng các mục dữ liệu đồng thời trong các chế độ tương tranh (các hoạt động đọc và
ghi). Nên, các khóa đồng bộ truy nhập đến các đối tượng CSDL. Một khóa là một biến
được kết hợp với một đối tượng dữ liệu trong CSDL, và nó mô tả kiểu của các hoạt
động mà được thực hiện trên đối tượng dữ liệu tương ứng. Trình quản lý khóa của một
hệ quản trị CSDL quản lý tất cả các khóa. Việc sử dụng các khóa không có sự điều
khiển tại các thời điểm mà các hoạt động khóa và mở khóa được thực hiện không đảm
bảo tính khả tuần tự. Vì thế, một cơ chế mà điều khiển sự sử dụng các khóa được yêu
cầu nhằm duy trì tính nhất quán CSDL. Để thỏa mãn tính nhất quán logic, các kỹ thuật
điều khiển đồng thời như Khóa hai pha đã được sử dụng.
Khóa hai pha (Two Phase Locking 2PL)
Giao thức 2PL cơ bản, là một kỹ thuật khóa bi quan, nó đảm bảo tính khả tuần tự của
một sự thực thi bằng cách điều khiển các thể hiện tại đó các hoạt động khóa và mở
khóa được thực hiện. Nó chia một sự thực thi của giao dịch ra làm hai pha. Trong pha
đầu, hay còn gọi là pha tăng trưởng, một giao dịch có thể đạt được tất cả các khóa của
nó động theo nhu cầu phát sinh, nhưng nó có thể không giải phóng bất kỳ khóa nào
mà nó đang giữ. Tuy nhiên, trong pha thứ hai, hay còn gọi là pha co lại (shrinking-
phase), giao dịch bắt đầu giải phóng động các khóa nó giữ, và không thể nhận được

thêm bất kỳ khóa nào nữa. Nghĩa là, một khi một giao dịch giải phóng một khóa, nó sẽ
không nhận thêm khóa nữa. Ngoài ra, một giao dịch được phép nâng cấp từ một khóa
đọc lên một khóa ghi chỉ trong pha đầu. Với 2PL, khi một giao dịch yêu cầu một khóa
mà đang được giữ bởi một giao dịch khác, giao dịch yêu cầu đợi cho đến khi giải
phóng khóa. Các giao dịch bị chặn được xếp hàng trong trình quản lý khóa. Kỹ thuật
Trang- 15
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
được dùng trong tổ chức hàng đợi này là điều quan tâm lớn trong các hệ thống cấp
thiết thời gian. Nếu mọi giao dịch trong một lịch tuân theo giao thức 2PL, lịch sẽ được
bảo đảm là khả tuần tự và không cần được xác minh.
Đồng bộ hóa các giao dịch CSDL thời gian thực trong các giao thức dựa trên
khóa
Đảo ưu tiên là một điều rất không mong muốn trong các hệ thống CSDL thời gian
thực do thực tế là kể từ lúc giao dịch có mức ưu tiên thấp hơn bị phân biệt trong sử
dụng tài nguyên hệ thống, nên giao dịch bị chặn có mức ưu tiên cao hơn về bản chất
đang chạy ở một mức ưu tiên hiệu quả bằng với những giao dịch có mức ưu tiên thấp
hơn. Với một hệ thống CSDL thời gian thực đối phó với sự suy giảm này, khóa 2PL
cần được tăng cường với lược đồ điều khiển theo mức ưu tiên để đảm bảo rằng các
giao dịch có mức ưu tiên cao hơn không bị trễ bởi các giao dịch có mức ưu tiên thấp
hơn. Các lược đồ khác nhau như Kế thừa ưu tiên, hủy ưu tiên, Mức trần ưu tiên, và kế
thừa ưu tiên có điều kiện đã được đề xuất như là các cơ chế cơ bản để tổng hợp các
mức ưu tiên trong các giao thức dựa trên khóa, tất cả các giao thức trên sẽ được mô tả
trong phần tiếp.
Thuật toán 2PL Wait Promote (2PL-WP)
Thuật toán 2PL Wait-Promote (2PL-WP) là lược đồ ngược của sự kế thừa ưu tiên
trong các hệ thống thời gian thực truyền thống. Nó tương tự như giao thức 2PL cơ bản
về cách giải quyết các tranh chấp, đó là, các giao dịch luôn luôn chặn bất cứ khi nào
một yêu cầu khóa bị từ chối. Sự khác biệt nằm ở chỗ nó bao gồm một cơ chế kế thừa
ưu tiên. Với cơ chế này, bất cứ khi nào một yêu cầu bị chặn đằng sau một giao dịch
giữ khóa có mức ưu tiên thấp hơn, ưu tiên của giao dịch giữ khóa được đẩy đến giao

dịch yêu cầu đó. Nói cách khác, giao dịch giữ khóa có mức ưu tiên thấp hơn kế thừa
mức ưu tiên cao hơn của giao dịch giữ khóa, và giao dịch giữ khóa giữ lại mức ưu tiên
cao hơn đã được đánh giá này cho đến khi kết thúc. Chú ý rằng không như một sự kế
thừa ưu tiên thuần túy, nếu giao dịch ưu tiên cao hơn bị hủy trong khi nó bị khóa, giao
dịch ưu tiên được đánh giá sẽ giữ mức ưu tiên đã đánh giá cho đến khi kết thúc.
Thuật toán 2PL High-Priority (2PL-HP)
Trang- 16
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
Thuật toán Khóa hai pha mức ưu tiên cao (2PL High-Priority 2PL-HP) được trình bày
đã được trình bày trong chương trước gọi là “priority-based Wound-Wait” theo cách
giải quyết tương tranh. Lược đồ sửa đổi giao thức 2PL cơ bản bằng cách kết hợp mức
ưu tiên của một giao dịch trong khi giải quyết một tranh chấp, mà vẫn đảm bảo các
giao dịch có mức ưu tiên cao không bị trễ, bởi các giao dịch có mức ưu tiên thấp.
Lược đồ 2PL-HP giải quyết tất cả các tranh chấp dữ liệu trực tiếp theo cách ưu tiên
cho các giao dịch có mức ưu tiên cao. Đặc biệt, khi một giao dịch yêu cầu một khóa
trên đối tượng dữ liệu đang được giữ bởi giao dịch có mức ưu tiên thấp hơn trong một
chế độ tương tranh, giao dịch đang giữ khóa bị hủy/khởi tạo lại và giao dịch yêu cầu
được gán khóa. Nếu giao dịch yêu cầu có một mức ưu tiên thấp hơn giao dịch đang
giữ, nó sẽ đợi đối tượng dữ liệu được yêu cầu được giải phóng. Ngoài ra, một giao
dịch đọc mới có thể nhập vào một nhóm các giao dịch đọc chỉ nếu mức ưu tiên của nó
là cao hơn tất cả các giao dịch ghi khác đang đợi khóa. Một lợi ích thứ hai của lược đồ
2PL-HP ngoài việc không bị đảo ưu tiên là nó không bị nghẽn.
Một trở ngại của thuật toán 2PL-HP là một giao dịch có thể bị khởi tạo lại bởi một
giao dịch có mức ưu tiên cao hơn mà sau đó nhỡ hạn cuối và bị loại bỏ. Điều này có
nghĩa rằng sự khởi tạo lại không dẫn đến việc giao dịch có mức ưu tiên cao hơn đáp
ứng hạn cuối của nó, một phần do mất mát tài nguyên hệ thống do khởi tạo lại. Nên,
những việc khởi tạo lại lãng phí đó có thể dẫn đến giáng bậc hiệu năng. Hơn nữa,
2PL-HP mất một số yếu tố chặn có ích 2PL-HP cơ bản do bản chất dựa trên sự khởi
tạo lại cục bộ của lược đồ Mức ưu tiên cao (High-Priority).
Các kết quả thí nghiệm đã cho thấy các thuật toán điều khiển đồng thời thời gian thực

dựa trên Mức ưu tiên cao thực hiện tốt hơn đáng kể so với thuật toán Kế thừa mức ưu
tiên (Priority-Inheritance). Hơn nữa, một điều đã được chứng minh rằng 2PL-HP thực
hiện tốt hơn lược đồ 2PL-WP trong bối cảnh của một môi trường RTDB, và kết luận là
thuật toán Kế thừa mức ưu tiên là không thích hợp cho giải quyết tương tranh trong
khóa hai pha 2PL.
Giao thức mức trần ưu tiên (Priority Ceiling Protocol)
Một kỹ thuật khác được đề xuất để giải quyết vấn đề đảo ưu tiên trong các giao thức
dựa trên khóa là Giao thức mức trần ưu tiên (PCP). Giao thức PCP là như sau:
Trang- 17
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
1. Khi một giao dịch mức ưu tiên thấp hơn, TL, chặn sự thực thi của một giao dịch
mức ưu tiên cao hơn, TH, TL kế thừa mức ưu tiên của TH và thực hiện ở mức ưu tiên
được đánh giá đó cho đến khi hoàn thành. Nếu có nhiều hơn một giao dịch mức ưu
tiên cao hơn bị chặn trên cùng đối tượng dữ liệu, thì giao dịch có mức ưu tiên thấp
nhất sẽ kế thừa và thực hiện ở mức ưu tiên cao nhất trong số tất cả các giao dịch bị
chặn.
2. Một trật tự ưu tiên tổng thể phải được thiết lập trong số tất cả các giao dịch đang
hoạt động, mà có thể đạt được bằng cách định nghĩa ba tham số cho mỗi đối tượng dữ
liệu trong CSDL: mức trần ưu tiên ghi, mức trần ưu tiên tuyệt đối, và mức trần ưu
tiên đọc-ghi.
- Mức trần ghi của một đối tượng dữ liệu là mức ưu tiên cao nhất mà có thể
ghi đối tượng.
- Mức trần tuyệt đối của một đối tượng dữ liệu là mức ưu tiên cao nhất mà có
thể đọc hay ghi đối tượng.
- Mức trần đọc-ghi của một đối tượng dữ liệu được thiết lập động lúc thời
gian chạy. Khi một giao dịch ghi một đối tượng dữ liệu, mức trần đọc ghi
được thiết lập tương đương với mức trần tuyệt đối. Tuy nhiên, mức trần
đọc-ghi được thiết lập bằng với mức trần ghi cho các thao tác đọc.
Một giao dịch không thể nhận được khóa đọc hay ghi trên một đối tượng dữ liệu trừ
phi luật giới hạn trên được thỏa mãn, điều này có nghĩa là mức ưu tiên của giao dịch

yêu cầu phải là cao hơn mức trần đọc ghi của tất cả đối tượng dữ liệu. Giao thức được
thể hiện là không bị nghẽn và chặn đơn. Chú ý rằng chặn đơn có nghĩa rằng một khi
một giao dịch bắt đầu thực thi sau khi bị chặn, nó có thể không chặn lại nữa.
Một trong những tính chất của giao thức này là các giao dịch với các mức ưu tiên mà
thấp hơn hay bằng với mức trần ưu tiên ghi hiện thời không được phép đọc đối tượng
dữ liệu. nên, các giao dịch có mức ưu tiên thấp hơn có thể không truy nhập đến cùng
đối tượng dữ liệu thận chí trong những chế độ tương thích. Một phép đo bi quan như
vậy được thực hiện để đảm bảo rằng một giao dịch có mức ưu tiên cao tương lai sẽ
không chặn trên nhiều giao dịch đọc nếu nó muốn thực hiện một hoạt động ghi.
Kế thừa ưu tiên có điều kiện (Conditional Priority-Inheritance CPI)
Trang- 18
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
Huang đã đề xuất một lược đồ kết hợp sự kế thừa ưu tiên và hủy ưu tiên, được gọi là
Conditional Priority Inheritance (CPI). Ý tưởng cơ bản đằng sau nó như sau: khi sự
đảo ưu tiên được phát hiện, nếu giao dịch có mức ưu tiên thấp hơn là gấn hoàn thành,
thì nó kế thừa mức ưu tiên cao hơn tham gia trong tranh chấp; mặt khác, giao dịch có
mức ưu tiên thấp hơn bị hủy. Kết quả là, lược đồ làm giảm tổng số tài nguyên lãng phí
bằng cách tránh hủy các giao dịch có mức ưu tiên thấp hơn mà sắp được hoàn thành,
và tránh trễ chặn kéo dài trải qua bởi các giao dịch có mức ưu tiên cao
Để sự kế thừa ưu tiên có điều kiện làm việc, một điều phải biết chính xác những gì mà
được gọi là sự gần hoàn thành. Huang đã sử dụng độ dài của giao dịch – được định
nghĩa như là số bước, đã được biết trước. Vì vậy, Huang định nghĩa một giá trị
ngưỡng để đo số bước còn lại được thực hiện bởi giao dịch có mức ưu tiên thấp hơn
tham gia tranh chấp. Dựa trên giá trị ngưỡng, để có thể quyết định có đánh giá mức ưu
tiên thấp hơn hay hủy giao dịch tương ứng.
Huang đã định nghĩa ngưỡng dựa trên số bước còn lại được thực thi bởi giao dịch có
mức ưu tiên thấp hơn tham gia vào tranh chấp. Tuy nhiên, Huang đã không xét đến
các ngữ nghĩa của các bước còn lại này. Đó là, do các hoạt động khác yêu cầu số
lượng thời gian khác nhau, nên có thể có một bước đơn yêu cầu nhiều thời gian hơn
nhiều bước khác vì ví dụ như trật tự của sự khác biệt độ lớn giữa tốc độ của CPU và

hệ thống con vào/ra. Một trễ như vậy không chỉ là do các hoạt động vào/ra, nhưng
cũng có thể là kết quả của các vòng lặp, các câu lệnh theo điều kiện, và các kênh
truyền thông và các hỏng hóc kết hợp của chúng. Hơn nữa, khong có gì bảo đảm rằng
một số ít bước còn lại, mà thỏa mãn được mức ngưỡng, sẽ không tránh khỏi tắc nghẽn
và/hay chặn thao chuỗi.
Vấn đề của giao thức CPI là nó không tương thích với các giao dịch CSDL thời gian
thực. Các giao dịch trong các hệ thống CSDL thời gian thực là phải phụ thuộc vào hạn
cuối, mà được đo bởi xung đồng hồ. Nói cách khác, giao thức CPI là không nhận biết
hạn cuối. Nó sử dụng số bước còn lại để thực hiện, mà không tương thích và không
nhạy cảm với hạn cuối. Nên, một giao dịch ưu tiên mức cao có thể nhỡ hạn cuối của
nó mặc dù kiểm tra mức ngưỡng đã được thỏa mãn. Nếu một giao dịch muốn sử dụng
lược đồ CPI, thì nó phải xác định số lượng thời gian còn lại để thực hiện, và ngưỡng
không nên tĩnh. Đúng hơn, mức ngưỡng nên là một phép đo mà phản ánh chính xác
Trang- 19
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
hạn cuối của giao dịch ưu tiên mức cao tham gia vào tranh chấp. Chỉ khi đó, một giao
dịch mới tin tưởng cho phép một giao dịch có mức ưu tiên thấp hơn đang tranh chấp
tiếp tục thực hiện mà không làm hỏng giao dịch ưu tiên mức cao hơn và tuân theo lịch
biểu giao dịch được điều khiển theo mức ưu tiên thời gian thực.
2.1.2 Điều khiển đồng thời lạc quan (Optimistic Concurrency Control)
Điều khiển đồng thời lạc quan (OCC) xét lại khái niệm xác nhận hợp lệ (validation),
hay được gọi là sự chứng nhận (certification), của các hoạt động của giao dịch tại thời
điểm cuối thực thi. OCC không yêu cầu bất kỳ kiểm tra nào được thực hiện trong quá
trình thực thi của một giao dịch. Ý tưởng đằng sau OCC là làm tất cả các kiểm tra cần
thiết cùng lúc (tại thời điểm cuối), sao cho thực thi giao dịch tiếp tục với một mào đầu
tối thiểu và không có trễ chặn. Nếi có ít tranh chấp và xen chéo giữa các giao dịch,
hầu hết các giao dịch sẽ được chứng nhận và xác nhận thành công. Tuy nhiên, nếu
càng có nhiều xen chéo giữa các giao dịch, thì càng có nhiều giao dịch sẽ bỉ hủy bỏ và
khởi tạo lại; nên, làm giảm sự tận dụng tài nguyên hệ thống. Trong giao thức OCC cổ
điển, các giao dịch đọc và cập nhật các mục dữ liệu tự do, lưu các cập nhật của chúng

vào một không gian riêng. Những cập nhật này được làm công khai tại thời điểm xác
nhận. Trước khi một giao dịch được phép xác nhận, nó phải vượt qua được một cuộc
kiểm tra chứng nhận hợp lệ. Các kiểm tra chứng nhận kiểm xem có hay không một
tranh chấp giữa giao dịch đang chứng nhận và các giao dịch khác mà vừa được xác
nhận kể từ lúc giao dịch đang chứng nhận bắt đầu thực hiện. Giao dịch đang chứng
nhận được khởi tạo lại nếu nó không qua sự kiểm tra này. Kỹ thuật này cũng được gọi
là OCC chuyển tiếp (forward OCC).
OCC – Xác nhận quảng bá (Broadcast Commit OCC -BC)
Một dạng biến đổi khác của kỹ thuật chuyển tiếp là OCC ngược (backward OCC), nó
kết hợp với một xác nhận quảng bá (Broadcast-Commit). OCC cổ điển được thay đổi
một chút để kết hợp thêm xác nhận quảng bá nhằm để phù hợp với các môi trường hệ
thống CSDL thời gian thực. Trong thuật toán kết quả, OCC-BC, khi một giao dịch xác
nhận, nó thông báo cho các giao dịch hiện thời đang chạy khác mà tranh chấp với nó,
và những giao dịch đang tranh chấp này được trực tiếp khởi tạo lại. Chú ý rằng không
cần kiểm tra các tranh chấp với các giao dịch vừa được xác nhận, vì nếu giao dịch
Trang- 20
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
đang chứng nhận hiện thời đã trong tình trạng tranh chấp với bất cứ giao dịch đã xác
nhận nào, thì nó đã bị khởi tạo lại trước khi nó đạt đến trạng thái chứng nhận hiện
thời. Điều này ngụ ý rằng một khi một giao dịch đạt đến pha chứng nhận, nó sẽ được
bảo đảm sự xác nhận. Phương pháp xác nhận quảng bá phát hiện các tranh chấp sớm
hơn thuật tóan OCC cơ bản, kết quả là làm giao dịch khởi tạo lại sớm hơn, và làm
lãng phí tài nguyên ít hơn, nên tăng cơ hội đáp ứng các hạn cuối của giao dịch.
OCC-Hy sinh (Sacrifice)
Thuật toán OCC-Sacrifice sửa lại giao thức OCC-BC bằng cách kết hợp một cơ chế
hy sinh ưu tiên. Định nghĩa một tập-tranh chấp là tập của các giao dịch đang chạy
hiện thời mà tranh chấp với giao dịch đanh chứng nhận. Trong lược đồ OCC-
Sacrifice, một giao dịch mà đạt đến giai đoạn chứng nhận sẽ kiểm tra sự tranh chấp
với các giao dịch đang thực hiện hiện thời. Nếu tranh chấp được phát hiện và một hay
nhiều giao dịch trong tập tranh chấp có một mức ưu tiên cao hơn, thì giao dịch đang

chứng nhận sẽ được khởi tạo lại. Đó là, giao dịch đang chứng nhận bị hy sinh trong nỗ
lực giúp đỡ các giao dịch có ưu tiên cao hơn đang tranh chấp tạo ra các hạn cuối của
chúng.
OCC-Sacrifice hy sinh mục tiêu đưa ra sự đối xử ưu đãi cho các giao dịch ưu tiên cao
hơn. Tuy nhiên, nó phải chịu vấn đề tiềm tàng về sự hy sinh bị lãng phí, trong đó một
giao dịch bị hy sinh thay cho giao dịch khác mà bị loại bỏ sau này. Những hy sinh như
thế là vô ích và làm giáng bậc hiệu năng. Trở ngại này của OCC-Sacrifice là tương tự
với vấn đề wasted-restart của 2PL-HP.
OCC-Đợi (Wait)
Thuật toán OCC-Wait sửa lại giao thức OCC-BC bằng cách kết hợp một cơ chế đợi ưu
tiên. Trong thuật toán này, một giao dịch đạt đến sự chứng nhận và tìm các giao dịch
có mức ưu tiên cao hơn trong tập tranh chấp của nó sẽ bị ép phải đợi. chu kỳ đợi này
đưa cho các giao dịch có mức ưu tiên cao hơn một cơ hội để tạo ra hạn cuối đầu tiên.
Khi một giao dịch đang đợi, có thể là nó sẽ được khởi tạo lại do sự xác nhận của một
trong số các giao dịch có mức ưu tiên cao hơn đang tranh chấp.
Pessimistic và Optimistic dưới môi trường CSDL thời gian thực.
Trong các hệ thống CSDL truyền thống, một chính sách giải quyết tương tranh dựa
trên khóa bảo quản được tài nguyên, trong khi một cách tiếp cận lạc quan với chính
Trang- 21
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
sách giải quyết tương tranh dựa trên khởi tạo lại có xu hướng lãng phí tài nguyên.
Trong các hệ thống CSDL thời gian thực, những giao thức này có xu hướng đối xử
khác nhau. Đó là, 2PL-HP mất một số những ưu điểm chặn của 2PL cơ bản do sự hủy
bỏ/khởi tạo lại của các giao dịch ưu tiên thấp hơn tham gia tranh chấp. Nói cách khác,
các giao thức lạc quan với phương pháp quảng bá có xu hướng phát hiện các tương
tranh sơm hơn thuật toán OCC cơ bản, kết quả là làm các quá trình khởi tạo lại xảy ra
sớm hơn; nên, làm tài nguyên lãng phí ít hơn. Nói chung, các thuật toán dựa trên sự
chặn làm giảm mức độ cơ chế song song khi chúng xây dựng các lịch tuần tự hóa;
trong khi, các cách tiếp cận lạc quan cố gắng tăng cơ chế song song đến tối đa, sau khi
chúng cắt bớt (prune) một số giao dịch nhằm thỏa mãn tính khả tuần tự. Trễ trong việc

phát hiện các tranh chấp bằng cách tiếp cận lạc quan là thực sự tiên tiến. Trong thuật
toán 2PL-HP, một giao dịch có thể được khởi tạo lại bởi, hay đợi một giao dịch khác
mà sẽ bị hủy bỏ sau đó. Những sự khởi tạo lại như vậy và/hay sự chờ đợi là vô ích và
làm cho hiệu năng suy giảm. Tuy nhiên, trong các cách tiếp cận lạc quan khi kết hợp
lược đồ xác nhận quảng bá, chỉ các giao dịch đang xác thực có thể làm cho các giao
dịch khác khởi tạo lại. Hơn nữa, do tất cả các giao dịch đang xác thực được đảm bảo
sự xác nhận và hoàn thành, thì tất cả các khởi tạo lại được sinh ra bởi thuật toán lạc
quan đó là hữu ích.
OCC có những ưu điểm là không bị chặn và chống tắc nghẽn, là điều mong muốn của
các hệ thống thời gian thực. Nhờ có tiềm năng về mức độ song song cao, OCC được
kỳ vọng sẽ thực hiện tốt hơn 2PL khi được tích hợp với lập lịch CPU được điều khiển
theo mức ưu tiên trong các hệ thống CSDL thời gian thực. Tuy nhiên, các hiệu ứng và
ảnh hưởng tổng thể của các mào đầu tham gia vào thực hiện OCC thời gian thực đã
được kiểm chứng. Nghiên cứu được báo cáo rằng thời gian chặn dưới các giao thức
lạc quan đã được hạn chế và có tính dự báo cao hơn 2PL. Nghiên cứu cũng cho thấy
các thuật toán lạc quan thực hiện tốt hơn các giao thức khóa ở mức độ tương tranh dữ
liệu thấp. Tuy nhiên, ở mức tranh chấp dữ liệu cao, các giao thức khóa thực hiện tốt
hơn các giao thức lạc quan.
Một kết quả quan trọng là có một điểm cắt trong kích cỡ CSDL. Dưới điểm cắt, tranh
chấp dữ liệu là cao, mà có nguyên nhân là một giao thức điều khiển đồng thời dựa trên
khóa; nghĩa là, 2PL-HP, để giải thích cho ảnh hưởng tiêu cực của các cách tiếp cận
Trang- 22
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
chặn; có nghĩa là, làm lãng phí các khởi tạo lại. Tuy nhiên, bên trên điểm cắt, tranh
chấp dữ liệu được giảm do tăng kích cỡ CSDL, làm cho 2PL-HP hoạt động giống như
các hệ quản trị CSDL truyền thống, khắc phục các ràng buộc thời gian của một hệ
thống thời gian thực. Nên, trong khi một các tiếp cận lạc quan, Wait-50, thực hiện tốt
hơn 2PL-HP dưới điểm cắt, hai thuật toán sẽ hoán chuyển tính ưu việt hiệu năng của
chúng khi lên trên điểm cắt. Những kết quả này giải thích sự tương phản lẫn nhau.
Các nghiên cứu của Haritsa đã xét đến kích thước CSDL nhỏ; nghĩa là, dưới điểm cắt

đó, trong khi các nghiên cứu của Huang lại xét đến CSDL lớn ở bên trên điểm cắt.
Hình 2.1 Quan hệ giữa kích cỡ CSDL và tỉ lệ nhỡ hạn của giao dịch
Trang- 23
Đi
ể
m
gi
ao
nh
au
C
ỡ
C
S
D
L
%

N
h
ỡ
Tr
an
h
ch
ấp
ca
o
Tr
an

h
ch
ấp
th
ấp
T
ố
i
ư
u
2
P
L
-
H
P
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
2.1.4 Điều khiển đồng thời suy đoán (Speculative)
Một bất lợi lớn của OCC cổ điển khi được sử dụng trong các hệ thống CSDL
thời gian thực là các tranh chấp của giao dịch không được phát hiện cho đến pha xác
thực, tại thời điểm đó nó có thể quá muộn để khởi tạo lại. OCC-BC cố gắng giải quyết
vấn đề này bằng cách thông báo cho tất cả các giao dịch tranh chấp đang chạy đồng
thời của sự xác nhận của một giao dịch tranh chấp. OCC-BC phát hiện các tranh chấp
sớm hơn giao thức OCC cơ bản. Điểm yếu lớn của các giao thức OCC nói chung là
một giao thức OCC bỏ qua sự xảy ra của một tranh chấp giữa hai giao dịch cho đến
pha xác thực của một trong số chúng, tại thời điểm đó nó có thể là quá muộn để hiệu
chỉnh vấn đề bằng cách khởi tạo lại một trong các giao dịch.
Dựa trên quan sát này, Bestavros đã giới thiệu một lớp mới về các giao thức
điều khiển đồng thời là chủ yếu được thiết kế để phục vụ các ứng dụng CSDL thời
gian thực. Lớp các giao thức này được gọi là Điều khiển Đồng thời Suy đoán

(Speculative Concurrency Control - SCC), nó dựa trên sự sử dụng của các tính toán
dư để tạo ra các lịch tuần tự hóa tại các giai đoạn sớm, do đó có một cơ hội tốt hơn để
đáp ứng các hạn cuối đã cho.
Các giao thức SCC cho phép các giao dịch tranh chấp xử lý đồng thời trong khi
phát hiện các tranh chấp càng sớm ngay khi chúng xảy là. Nghĩa là, các giao thức
SCC kết hợp các giao thức bi quan và lạc quan để nhận được những ư điểm của chúng
trong khi tránh các nhược điểm của chúng. Trong các giao thức SCC, một phiên bản
mới (bóng) của giao dịch đang tranh chấp được khởi tạo ngay khi tranh chấp được
phát hiện và một lịch tuần tự hóa khác được xây dựgn sử dụng phiên bản được khởi
tạo mới. Phiên bản đầu tiên thực hiện khi bất kỳ giao dịch nào dưới các giao thức
OCC – bỏ qua bất kỳ tranh chấp nào mà có thể phát triển trong suốt quá trình thực
hiện. Trong khi đó, phiên bản bóng thực hiện khi bất kỳ giao dịch nào dưới các giao
thức bi quan – tùy thuộc vào khóa/chặn và các khởi tạo lại. Mục đích của phiên bản
bóng là để giữ một phiên bản sạch (một phiên bản không có tranh chấp) trong trường
hợp nó cần thiết. Khi một giao dịch đạt đến pha xác thực và ép một giao dịch khác, T,
bị hủy bỏ, T sẽ không phải khởi tạo lại từ lúc bắt đầu. Đúng hơn, phiên bản bóng được
đẩy lên để trở thành phiên bản gốc và T sẽ lấy lại sự thực hiện trên phiên bản gốc. Một
Trang- 24
Điều khiển tương tranh và lập lịch trong CSDL thời gian thực
khi phiên bản bóng trở thành phiên bản gốc, nó bắt đầu thực hiện khi có bất kỳ giao
dịch nào dưới giao thức OCC. Ngoài ra, phiên bản bóng mới sẽ được tạo ngay khi một
tranh chấp được phát hiện. Vì vậy, sau khi một giao dịch gặp một tranh chấp, sẽ có
nhiều hơn một phiên bản của giao dịch trong hệ thống, mỗi phiên bản với sự tính toán
của nó. Phiên bản mà đảm bảo tính khả tuần tự chính là phiên bản được xác nhận.
Chu kỳ giữa lúc một tranh chấp xảy ra và lúc hủy bỏ/khởi tạo lại một giao dịch
là thực chất bị mất, hay không được tận dụng, trong các giao thức OCC. Một chu kỳ
như vậy được tận dụng hay được trao quyền trong việc xây dựng các phiên bản bóng
trong các giao thức SCC. Nên, một giao dịch bị hủy bỏ/khởi tạo lại có một cơ hội đáp
ứng hạn cuối của nó tốt hơn. Chú ý rằng cho các mục tiêu hiệu năng, một phiên bản
bóng được khởi tạo mới không phải bắt đầu từ lúc mở đâu. Đúng hơn, nó có thể lấy sự

thực hiện nhất quán từ phiên bản bóng khác, nếu có một. Rõ ràng, SCC là một lớp tốt
hơn của các giao thức điều khiển đồng thời và là cân bằng hơn cho các hệ thống
CSDL thời gian thực tại đó thời gian là một trong những điều cốt yếu.
Các cập nhật được tạo bởi mỗi giao dịch được tạo trên các bản sao chép cục bộ và do
đó là không thấy được cho đến khi các giao dịch đang cập nhật được xác nhận. Các
giao thức SCC chấp nhận một sự xác thực chuyển tiếp. Nghĩa là, tập các đối tượng
được đọc bởi tất cả các giao dịch đang hoạt động được kiểm tra so với tập các đối
tượng được ghi bởi giao dịch đang xác thực. Lược đồ chung là như sau:
- Khi một giao dịch bắt đầu một thực hiện mới, một phiên bản bóng gốc được
tạo.
- Khi một tranh chấp tiềm tàng được phát hiện, một phiên bản bóng được tạo,
và một phiên bản bóng mới được tạo cho mọi tranh chấp tiềm tàng trong
một phiên bản bóng sớm hơn.
- Khi một bóng đạt đến điểm mà đã gây ra tranh chấp, mà đã khởi tạo nó, nó
sẽ chặn lại.
- Khi phiên bản gốc xác thực, tất cả các bóng kết hợp với nó bị loại bỏ cộng
thêm bất kỳ các bóng nào khác mà có tính khả tuần tự đã tranh chấp trên
những bóng bị loại bỏ cũng sẽ bị loại.
Trang- 25