1

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Phạm Đình Luật VẤN ĐỀ CẤP PHÁT VÀ CẬP NHẬT CÁC MẢNH
TRONG HỆ PHÂN TÁN
Chuyên ngành: Truyền dữ liệu và Mạng máy tính
Mã số: 60.48.15

Người hướng dẫn khoa học: PGS. TS Lê Huy Thập TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2012
2

thời nhiều máy tính để bộ xử lý tính toán song song nhằm
nâng cao hiệu năng tính toán, tiết kiệm thời gian, giảm chi
phí, giải quyết được các vấn đề lớn hơn, phức tạp hơn và
tăng khả năng xử lý đồng thời cao hơn.
Lĩnh vực CNTT ở Việt nam tuy còn non trẻ nhưng nó
phát triển nhanh chóng và góp phần không nhỏ trong công
cuộc xây dựng, phát triển đất nước. Nhiệm vụ của những
cán bộ làm công tác trong lĩnh vực CNTT là phải đi trước,
đón đầu những tiến bộ của khoa học kỹ thuật và xu hướng
phát triển của thời đại nhất là trong lĩnh vực CNTT. Chính
vì vậy, tôi đã lựa chọn đề tài:
“Cấp phát và cập nhật các mảnh trong hệ thống phân
tán” để nghiên cứu thực hiện. 4

CHƯƠNG I. HỆ ĐA XỬ LÝ
1.1 Tổng quan hệ đa xử lý
1.1.1 Sơ đồ cấu trúc tổng quát của vi xử lý
Tùy thuộc vào các thế hệ khác nhau, các bộ vi xử
lý có thể có cấu trúc bên trong khác đi nhưng vẫn có một
số nguyên tắc hoạt động cơ bản nhất.
Vi xử lý là một mạch số có thể thực hiện nhiều
chức năng số khác nhau. Nó sẽ thực hiện một bài toán,
một công việc khi được cung cấp một chương trình. Một
chương trình là một chuỗi các tín hiệu nhị phân nối tiếp

phép toán theo dạng song song không đồng bộ, các nút
hoạt động hợp tác chặt chẽ nhưng thực hiện độc lập. Ví dụ
trong hệ thống phục vụ đặt chỗ máy bay, việc đặt chỗ xảy
ra thường xuyên, liên tục và đồng thời, mỗi cuộc đặt chỗ
cần một chương trình để thực hiện, các chương trình này
6

không bắt đầu song song từng lệnh một, do đó chúng ta có
nhiều dòng chảy lệnh và nhiều dòng chảy dữ liệu.
1.2 Ứng dụng đa xử lý dữ liệu
 Database server: Database server là dịch vụ kết nối
trực tiếp đến máy chủ chứa cơ sở dữ liệu. Server là một
máy chủ mà trên đó có cài đặt phần HQTCSDL như: SQL
Server, MySQL, Oracle… dịch vụ Database server hoàn
toàn đạt hiệu quả nếu hệ thống được thiết kê có bộ nhớ
được chia sẻ kiểu kiến trúc MIMD UMA.
 Web server: Web server là dịch vụ mà một máy
tính (máy chủ) trên đó cài đặt phần mềm phục vụ Web hay
còn gọi là Web Server. Dịch vụ Web Server sử dụng hệ
thống bộ nhớ không chia sẻ MIMD NUMA.
 Multimedia: Là kỹ thuật tích hợp trên một nền
thống nhất các dạng dữ liệu khác nhau với sự hỗ trợ của
máy tính.
 CAD/CAM:
CAD là các phần mềm thiết kế và các phần mềm vẽ
có sự trợ giúp của máy tính.
CAM là một hoạt động cụ thể trong công nghệ chế
tạo cơ khí. Kết quả của CAM là cụ thể, đó là chi tiết cơ
khí.
7

đáp ứng yêu cầu từ các tiến trình Client khác.
1.3.2.4 Khả năng mở rộng
Khả năng mở rộng được đặc trưng bởi tính không
thay đổi phần mềm hệ thống và phần mềm ứng dụng khi
hệ thống được mở rộng.
1.3.2.5 Khả năng thứ lỗi
+ Dùng khả năng thay thế để đảm bảo sự hoạt động liên
tục và hiệu quả.
+ Dùng các chương trình hồi phục khi gặp sự cố.
1.3.2.6 Tính trong suốt
Được hiểu như là sự che khuất đi các thành phần
riêng biệt của hệ đối với người sử dụng và những người
lập trình ứng dụng: +Tính trong suốt về vị trí;+ Tính trong
suốt trong việc sử dụng;+ Tính trong suốt của việc phân
chia;+ Tính trong suốt trong sự trùng lặp.
9

1.3.2.7 Đảm bảo tính tin cậy và nhất quán
Sự bí mật của dữ liệu phải được bảo vệ, các chức
năng khôi phục hư hỏng phải được đảm bảo, ngoài ra yêu
cầu nhất quán của dữ liệu cũng rất quan trọng trong thể
hiện (Khi các thuộc tính dữ liệu là khác nhau thì các thao
tác phải nhất quán).
1.3.3 Mục đích của việc sử dụng dữ liệu phân tán
- Đáp ứng nhu cầu nhanh nhất, hiệu quả nhất trong
việc cập nhật và chia sẻ thông tin, cũng như các yêu cầu
làm việc trong môi trường mạng Internet, tintranet phát
triển rực rỡ như hiện tại, rất phù hợp cho các Công ty và
các Tập đoàn mở rộng và phát triển trong xu thế toàn cầu
hóa và hội nhập hóa.

đó có cơ sở dữ liệu phân tán đáp ứng được việc hội nhập
kinh tế toàn cầu, đáp ứng được việc phát triển mở rộng
của các tổ chức kinh tế toàn cầu khi có các văn phòng, chi
11

nhánh khác nhau về địa lý nên việc lưu trữ thông tin trên
cơ sở dữ liệu phân tán là hiệu quả hơn cả. Cơ sở dữ liệu
phân tán là giải pháp tự nhiên khi tổ chức đã có sẵn cơ sở
dữ liệu và cần mở rộng cho các phổ dụng phổ quát hơn và
giảm các chi phí truyền thông so với dữ liệu tập trung,
đồng thời đáp ứng được việc truy nhập cơ sở dữ liệu của
người sử dụng (được phép) đối với các vị trí khác. Do vậy
việc quản trị cơ sở dữ liệu có thể được thực hiện tự quản
tại mỗi vị trí khác nhau.
CHƯƠNG II. CƠ SỞ DỮ LIỆU – DỮ LIỆU
PHÂN TÁN
2.1 CSDL phân tán và Hệ quản trị cơ sở dữ liệu
phân tán
2.1.1 Hệ quản trị cở sở dữ liệu
Hệ quản trị cơ sở dữ liệu bao gồm một tập các phần mềm
(chương trình) sau:
+ Các chương trình quản lý dữ liệu phân tán.
+ Chứa các chương trình để quản trị việc truyền thông dữ
liệu.
+ Các chương trình để quản trị cơ sở dữ liệu địa phương.
+ Các chương trình quản trị từ điển dữ liệu.

12

2.1.2 Kiến trúc hệ cơ sở dữ liệu phân tán

 Mức độ chia sẻ (level of sharing): Có ba khả năng
là : 1- không chia sẻ, 2-chia sẻ dữ liệu, và 3- chia sẻ
dữ liệu lẫn chương trình.
 Kiểu mẫu truy xuất (behavior of access pattern): Có
hai chọn lựa là kiểu truy xuất tĩnh và kiểu truy xuất
động.
 Mức độ hiểu biết về kiểu mẫu truy xuất: Đòi hỏi
người thiết kế hiểu càng rõ về thông tin truy xuất
càng tốt, có hai trường hợp là: Biết một phần thông
tin và biết thông tin một cách đầy đủ.
Có hai chiến lược chính được xác định trong việc
thiết kế các CSDL phân tán là tiếp cận từ trên xuống (top-
down approach) và tiếp cận từ dưới lên (bottom-up
approach).
14

a) Quán trình tiếp cận từ trên xuống
b) Quá trình thiết kế từ dưới lên
c) Các xu hướng hiện đại của hệ cơ sở dữ liệu phân
tán
2.2 Cách phân mảnh và tái cấu trúc cơ sở dữ liệu
phân tán
Để thuận lợi cho việc nghiên cứu, chúng ta xét cơ
sở dữ liệu quan hệ của công ty điện toán như sau:
Quan hệ EMP(ENO,ENAME,TITLE):
Trong đó EMP là Employee, ENO là Employee Number (
Mã số nhân viên), ENAME là Employee Name (tên nhân
viên), TITLE(Chức vụ) và dữ liệu định nghĩa như sau:
ENO ENAME TITLE
E1

PNO PNAME BUDGET

LOC
P1
P2
P3
P4
Intrumentation
Database
Develop
CAD/CAM
Maintenance
150000
135000
250000
310000
Montreal
NewYork
NewYork
Paris
Bảng 2.2b: Quan hệ PROJ
- Quan hệ PAY(TITLE,SAL):
Trong đó SAL – salary (Tiền lương). Và dữ liệu giả
định như sau:
TITLE SAL
Elect.Eng
Syst.Anal
Mech.Eng
Programmer
40000

P3
P3
Manager
Analyst
Analyst
Consultant
Engineer
Progammer
Manager
Manager
Enginner
Manager
12
24
6
10
48
18
24
48
36
40
Bảng 2.2d: Quan hệ ASG.
2.2.1 Tại sao cần phải phân mảnh
Trước tiên, khi tạo khung nhìn của các ứng dụng
thường chỉ là tập con của mối quan hệ, đơn vị truy xuất
không phải là toàn bộ quan hệ. Vì vậy đưa tập con của
quan hệ ra khung nhìn là tốt nhất cho lên phân mảnh các
quan hệ và phân tán đến nơi sử dụng khung nhìn sẽ là điều
thích hợp nhất.

2.2.3 Phân mảnh cơ sở dữ liệu phân tán thực hiện
đến mức độ nào?
Phân mảnh dữ liệu thực hiện đến mức nào là một
quyết định rất quan trọng, có ảnh hưởng tới hiệu năng vấn
tin. Mức độ phân mảnh có thể là thái cực không phân
mảnh thành từng bộ phận (trường hợp phân mảnh ngang)
hoặc thành từng thuộc tính ( trường hợp phân mảnh dọc).
2.2.4 Phương pháp phân mảnh cơ sở dữ liệu phân
tán
2.2.4.1 Phân mảnh ngang và phân mảnh ngang dẫn
xuất
a) Phân mảnh ngang nguyên thủy
b) Phân mảnh dọc
2.3 Bài toán qui hoạch toán học
2.3.1 Bài toán tối ưu tổng quát
Bài toán tối ưu tổng quát có dạng:
19

f(x) max (min) (2.3.1)
Với các điều kiện:
g
i
(x) = (, , , ) b
i
, i = 1, 2, , m (2.3.2)
x  X  R
n
(2.3.3)
Bài toán (2.3.1) (2.3.3) được gọi là bài toán quy hoạch
toán học, f(x) được gọi là hàm mục tiêu, các hàm g

2.4.1 Bài toán cấp phát
Giả sử rằng có một tập các mảnh F= {F
1
,F
2
,…,F
n
}
và một mạng bao gồm các vị trí S= {S
1
,S
2
,…,S
m
} trên đó
có các tập ứng dụng Q = {q
1
,q
2
,…,q
n
} đang chạy. Bài toán
cấp phát là tìm ra đầu mối “tối ưu” của F cho S. Một trong
các điểm quan trọng cần được được thảo luận là định
nghĩa tính tối ưu.
1. Chi phí nhỏ nhất: Hàm chi phí gồm có chi phí lưu
mảnh F
i
tại vị trí S
j ,

3.1 Bài toán cấp phát và vấn đề cập nhật dữ liệu
3.1.1 Cập nhật các quan hệ trung gian
3.1.2 Cập nhật các mảnh
Tác nhân chính ảnh hưởng đến hiệu qủa hoạt động của
một chiến lược thực hiện là kích thước các mảnh được tạo
ra. Khi cấp phát các mảnh đến các vị trí khác, kích thước
các quan hệ trung gian và mảnh phải được tính toán. Vì
22

các mảnh thường xuyên được cập nhật nên chúng ta luôn
luôn phải ước lượng lại kích thước của các kết quả trung
gian của các phép toán đại số và các mảnh. Việc ước
lượng này dựa trên thông tin thống kê về các quan hệ cơ
sở và các công thức để dự đoán lực lượng của các kết qủa.
Dĩ nhiên là có những được mất giữa tính chính xác của
các số liệu thống kê và chi phí quản lý chúng, số liệu càng
chính xác, chi phí càng cao.
Kích thước của một mảnh F(A) | A = {A
1
, A
2
, …, A
n
} phụ
thuộc vào các yếu tố sau:
i. Đối với mỗi thuộc tính A
l
, chiều dài theo số bytes được
ký hiệu là lengh(A
l

), lực lượng của miền
là card(dom(A
l
). Giá trị này cho biết số lượng các giá trị
duy nhất trong dom[A
l
]
iv. Số lượng bộ của mỗi mảnh F
i
được ký hiệu là card(F
i
).
Như vậy kích thước của mảnh F
i
(tính bằng byte) là:
23




n
k
kii
AlengthFCardF
1
)(*)(||

Thực ra các mảnh có thể được sinh ra từ các quan hệ trung
gian vì vậy chúng ta có thể phải ước lượng kích thước của
chúng.

cho trước mà mới chỉ đưa ra một số giả thiết đơn giản hóa
và dễ áp dụng cho một số cách cài đặt đơn giản.
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
KẾT LUẬN
Hiện nay cùng với việc phát triển vượt bậc về công
nghệ thông tin, các bộ chip xử lý liên tục phát triển đáp
ứng được việc tính toán ngày càng cao, do giới hạn về mặt
vật lý các nhà sản xuất không thể tích hợp mãi các vi
mạch vào một con chíp trên cùng một diện tích được,
chính vì vậy các nhà sản xuất đã cho ra đời các chíp đa xử
lý. Để tận dụng ưu điểm đó các nhà lập trình sẽ hướng
chia các bài toán lớn thành các bài toán nhỏ hơn, đơn giản
đi để có thể chạy song song trên một hay nhiều bộ vi xử
25

lý. Việc cấp phát và cập nhật các mảnh trong hệ thống
phân tán, chia sẻ dữ liệu và thu thập dữ liệu trong môi
trường phân tán như Internet/Intranet đòi hỏi phải tiếp tục
nghiên cứu sâu thêm các phương phán hiện hành nhằm
đáp ứng tính xác thực, hiệu quả của các hệ thống thông tin
đăng ký trên mạng như: Việc đăng ký các tua du lịch, mua
bán trong các giao dịch thương mại điện tử, đăng ký giữ
chỗ trong giao thông vận tải, đăng ký dự thi trong các hệ
thống thông tin đào tạo, đăng ký sim thẻ, các dịch vụ gia
tăng của các nhà khai thác di động
Luận văn đã nêu được khái niệm tổng quát nhất về cơ
sở dữ liệu phân tán, qua đó chúng ta nhận thấy sự khác
biệt giữa cơ sở dữ liệu phân tán và cơ sở dữ liệu tập trung,
đồng thời chỉ ra các lợi ích của việc phát triển cơ sở dữ
liệu tại mỗi công ty đặc biệt với các công ty lớn có nhiều