Mục đích của khóa luận là nghiên cứu và tìm hiểu các khái niệm liên quan đến
thành phần phần mềm, hệ thống dựa trên thành phần và hệ thống dựa trên thành phần
thời gian thực. Đầu tiên tôi sẽ trình bày tổng quan về việc xây dựng hệ thống dựa trên
thành phần và các lợi ích của nó trong việc phân tích, thiết kế các hệ thống thông tin.
Tôi sẽ trình bày việc mô hình hóa hình thức hệ thống dựa trên thành phần dựa trên nền
tảng của UTP (Unifying Theory of Programming). Tôi sẽ trình bày về các khái niệm
trong mô hình hệ thống dựa trên thành phần như: giao diện, hợp đồng, thành phần, kết
hợp thành phần. Các định nghĩa này sẽ đóng vai trò nền tảng cho việc phát triển các
khuôn mẫu cho thành phần. Một hợp đồng được định nghĩa sẽ bao hàm đặc tả của các
phương thức, một thành phần được định nghĩa là một cài đặt của một hợp đồng. Cài
đặt này có thể yêu cầu các dịch vụ từ các thành phần khác với một vài giả thiết về lập
lịch cho việc giải quyết xung đột các phương thức dùng chung và sử dụng các tài
nguyên hiện có trong xử lí song song. Trong khóa luận tôi sẽ trình bày sâu hơn về mô
hình thành phần thời gian thực dựa trên các khái niệm, các định nghĩa đã được nêu ra
trước đó. Với phần này, tôi đưa ra một mô hình giao diện thành phần cho hệ thống dựa
trên thành phần thời gian thực. Cùng với đó, đặc tả phương thức sẽ được mở rộng với
một ràng buộc về thời gian là một quan hệ giữa tài nguyên có sẵn và lượng thời gian
tiêu tốn để thực thi phương thức. Với mô hình đó, nó hỗ trợ sự phân tách giữa yêu cầu
chức năng, yêu cầu phi chức năng và kiểm chứng hợp phần hình thức của hệ thống
dựa trên thành phần thời gian thực. Cuối cùng tôi cho một ví dụ minh họa cho mô hình
được nghiên cứu trong luận văn này.
LỜI MỞ ĐẦU 1
1. TỔNG QUAN VỀ HỆ THỐNG DỰA TRÊN CÁC THÀNH PHẦN .3
1.1. Hệ thống dựa trên thành phần là gì? 3
1.1.1. Thành phần phần mềm. .3
1.1.2. Hệ thống dựa trên thành phần 4
1.2. Hệ thống thời gian thực là gì? .6
2. KIẾN TRÚC HỆ THỐNG DỰA TRÊN THÀNH PHẦN 7
3. TÌM HIỂU MÔ HÌNH THÀNH PHẦN 8
3.1 Thiết kế dưới dạng công thức logic 8
3.2 Giao diện và hợp đồng 9
3.3. Kết hợp hợp đồng. 11
4. MÔ HÌNH THÀNH PHẦN THỜI GIAN THỰC .18
4.1. Các thiết kế có nhãn ràng buộc về thời gian sử dụng như dịch vụ 18
4.2. Sử dụng các ngôn ngữ hình thức có nhãn ràng buộc về thời gian để đặc các
giao thức tương tác thời gian thực và đặc tả tiến trình. 22
4.3. Các hợp đồng thời gian thực. 23
4.4. Thành phần bị động .25
4.5. Thành phần chủ động 28
5. ỨNG DỤNG MÔ HÌNH THÀNH PHẦN TRONG HỆ THỐNG NHÚNG .30
KẾT LUẬN 33
41 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 2502 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Mô hình hóa các hệ thống dựa trên các thành phần, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
t ngôn ngữ lập trình. Nhưng với sự ra
đời của phương pháp phát triển hệ thống dựa trên thành phần, các thành
phần có thể được viết bằng các ngôn ngữ khác nhau. Bởi vì các thành
phần tương tác với nhau bằng giao diện và hợp đồng. Vấn đề này sẽ được
đề cập rõ hơn trong các phần sau.
1.2. Hệ thống thời gian thực là gì?
Hệ thống thời gian thực là hệ thống mà các dịch vụ của các thành phần phải thỏa
mãn ràng buộc về thời gian.
Ví dụ Hệ hướng dẫn lái xe.
Hệ thống này sẽ được làm rõ hơn trong phần 5 của khóa luận
7
2. KIẾN TRÚC HỆ THỐNG DỰA TRÊN THÀNH PHẦN
Với định nghĩa của một hệ thống hướng thành phần như trên, kiến trúc của hệ
thống dựa trên thành phần bao gồm các thành phần độc lập và giao tiếp với nhau qua
các giao diện giao tiếp. Sự kết hợp đó sẽ tạo thành một hệ thống lớn. Hệ thống dựa
trên thành phần được chia làm 2 phần: phần bị động và phần chủ động.
Phần bị động: là một tổ hợp các thành phần liên kết với nhau.
Phần chủ động: là một tập hợp các tiến trình phản ứng lại các tác động được gây
ra từ các sự kiện bên ngoài. Chúng sử dụng các dịch vụ từ thành phần bị động để đáp
ứng lại yêu cầu từ các tác nhân bên ngoài hệ thống thông qua giao diện thành phần.
Kiến trúc của hệ thống được mô tả trong hình dưới.
Hình 4: Kiến trúc hệ thống dựa trên thành phần.
Đối với kiến trúc này, ta có thể lấy một ví dụ đối với các chương trình đa luồng
(như chương trình Java). Ở đây, mỗi một tiến trình tương ứng với một luồng trong
Java với thiết lập đa luồng được chập nhận. Điều đó có nghĩa là nhiều luồng được truy
cập đến một dịch vụ của một thành phần con trong phần bị động một cách trực tiếp
hoặc thông qua các dịch vụ khác.
Làm thế nào để xử lý các trường hợp này để tăng hiệu suất và đặc biệt là tránh bế
tắc từ các truy cập đồng thời tới các tài nguyên dùng chung là một vấn đề lớn. Nếu
điều này xảy ra thì ngay cả tiền điều kiện của một dịch vụ được thỏa mãn thì dịch vụ
cũng không thể ngắt vì dịch vụ đã rơi vào trạng thái bế tắc. Vì thế, không phải tất cả
các hành vi truy cập dịch vụ liên tiếp đều được chấp nhận. Ngoài đặc tả với tiền điều
kiện và hậu điều kiện của một dịch vụ ra, một hợp đồng cũng phải được bao gồm trong
8
đặc tả của việc cho phép truy cập dịch vụ liên tục. Đặc tả này cũng đóng vai trò như là
một giả thiết rằng thành phần tạo nên môi trường cho chính nó,được ghi nhận bởi một
giao thức gọi là giao thức tương tác.
3. TÌM HIỂU MÔ HÌNH THÀNH PHẦN
3.1 Thiết kế dưới dạng công thức logic
Như đã nói ở phần trước, một thành phần cung cấp các dịch vụ cho các khách
hàng. Các dịch vụ có thể dữ liệu hoặc các phương thức. Để xác định các chức năng
cho các phương thức, ta sử dụng các kí hiệu UTP (Unified Theories of Programming)
cơ bản, trong đó một phương thức được xác định như là có quan hệ với nhau với các
dấu hiệu của dạng thức ( , )op in out với in và out là tập hợp các biến.
Định nghĩa 1
Một thiết kế là một tập hợp hữu hạn , FPα với α là biểu thị cho tập hợp các
biến chương trình được sử dụng bới phương thức, FP biểu thị cho đặc tả chức năng
của phương thức trong bảng kí hiệu của UTP.
• FP là một vị từ của dạng thức:
Nếu điều khiển chuyển đến chương trình (ok là true) và tiền điều kiện p được
thỏa mãn thì chương trình sẽ kết thúc tương ứng với ok’ là true và giá trị của biến
chương trình tại thời điển kết thúc và thời điểm khởi hành thỏa mãn quan hệ R.
Với p là tiền điều kiện của phương thức là giả thiết trên giá trị ban đầu của các
biến trong tập hợp \ outα mà các phương thức có thể dựa vào khi kích hoạt và R là
hậu điều kiện R bài liên quan đến quan sát ban đầu đến quan sát cuối cùng(được đại
diện bởi những biến đầu tiên trong tập hợp { | \ ( )}x x in outα′ ∈ ∪ và các biến in out).
Biến logic ok là biến đặc biệt biểu thị sự kết thúc của phương thức, ví dụ ok có giá
trị true nếu và chỉ nếu phương thức bắt đầu chạy và ok′ có giá trị true nếu và chỉ nếu
phương thức ngắt.
Làm mịn thiết kế.
Ta gọi lại định nghĩa làm mịn quan hệ cho thiết kế được trình bày trong UTP.
Một thiết kế 1 1,D FPα= là được làm mịn từ thiết kế 2 2,D FPα= (có nghĩa là
1 2D D⊑ ) nếu và chỉ nếu
9
2 1( , , , )ok ok v v FP FP′ ′∀ • ⇒
với ,v v′ là các vectơ của các biến chương trình.
Dãy thành phần
Lấy 1 1,D FPα= và 2 2,D FPα= là các thiết kế sau đó 1 2; ,D D FPα≙
Với 1 2( ) ( )FP m FP m FP m∃ • ∧≙ với giả sử là 1 1( )FP FP v= và 2 2( )FP FP v= .
Từ đây về sau, tôi sử dụng 1[ \ ]F x x để biểu diễn biểu thức kết quả từ việc thay thế x
bởi x1 trong biểu thức F.
3.2 Giao diện và hợp đồng
Chữ kí cho thành phần là giao diện của nó mà chỉ rõ những dịch vụ nào nó cung
cấp và dịch vụ nào nó yêu cầu từ môi trường. Hợp đồng là đặc tả của giao diện. Từ
thảo luận không chính thức trong phần trước, ta đưa ra định nghĩa chính thức của hai
khái niệm trong lập trình dựa trên thành phần sau đây.
Định nghĩa 2:
Một giao diện là một cặp ( , )p rI I I= với ,p p pI Fd Md= và
,
r r r
I Fd Md= . Ip được gọi là cung cấp giao diện của I và Ir được gọi là yêu cầu
giao diện của I.
Định nghĩa 3:
Một hợp đồng là một tập hợp hữu hạn , , , , ,Prp rI Init MSpec Inv Inv o với
• ( , )p rI I I= là một giao diện. Lấy ,r p r pMd Md Md Fd Fd Fd= ∪ = ∪
• Init là một khởi tạo mà kết hợp với mỗi biến trong Fd và mỗi biến cục bộ
với một giá trị của cùng kiểu.
• MSpec là đặc tả phương thức kết hợp với mỗi phương thức ( , )op in out
trong
r pMd Md Md= ∪ với một thiết kế , FPα với
( \ ( )) pin out Mdα ∪ ⊆
• Invp và Invr là vị từ trong cung cấp tính năng và yêu cầu tính năng tương
ứng trong hợp đồng (được gọi là hợp đồng bất biến). Invp đại diện cho
một thuộc tính của giá trị biến trong khai báo đặc tính FDp mà có thể dựa
10
vào trong bất kì thời điểm nào mà nó có khả năng truy cập từ các thành
phần khác. Do vậy, Invp được thỏa mãn nhất là bởi Init. Invr đại diện cho
thuộc tính mà yêu cầu giá trị của biến trong FDr mà được cung cấp.
• Pro là một giao thức, là tập con của dạng thức
{ ?, !| }* { ?, !| }*p rm m m Fd m m m Fd∈ ∪ ∈ . Chỉ có hành vi của các
phép chiếu trên { ?, !| }*pm m m Fd∈ và { ?, !| }*rm m m Fd∈ thuộc về
Pro là được chấp nhận.
Hợp đồng của một thành phần biểu diễn cái mà thành phần mong đợi từ môi
trường và cái nó cung cấp cho môi trường.
Các biến trong Fd là chỉ đọc đối với các hợp đồng khác. Invp trong một hợp đồng
biểu diễn một thuộc tính của các biến trong hợp đồng mà nó cung cấp cho môi trường,
và do vậy phải được đảm bảo bởi bất kì phương thức nào của hợp đồng.
Có lẽ nó kém rõ ràng hơn một giao thức, và cách nó quan hệ với đặc tả của các
dịch vụ. Ta cũng làm rõ khái niệm này như là một phần của nghiên cứu. Đối với
phương thức m, kí hiệu ?m và !m như là sự dẫn ra (gán giá trị cho tham số) và kết thúc
(lấy kết quả dịch vụ) của m. Ở đây sử dụng CSP (truyền thông liên tiến trình -
Communicating Sequential Processes1). Sau đó nó yêu cầu mỗi ?m phải tương ứng
với chính xác một !m theo sau, và ngược lại mỗi !m phải tương ứng đúng với một yêu
cầu hành động !m. Đối với một phương thức m, nó có thể chấp nhận một vài luồng để
sử dụng m tại cùng một thời điểm (ví dụ như vài bản sao của m). Trong trường hợp
này, đối với một ?m và và tương ứng với !m có thể có vài xuất hiện của ?m giữa
chúng. Số tối đa của các yêu cầu ?m không kết thúc tương ứng tại một thời điểm là độ
đồng thời mà m có thể cung cấp và được chỉ rõ trong giao thức. Bình thường, bất kì
phương thức m chỉ có thể được sử dụng lẫn nhau không bao gồm chính nó và các
phương thức khác trong thành phần. Trong trường hợp này, giao thức có thể được chỉ
ra như là một biểu thức chính quy {? ! | }*m m m Md∈ . Khi tất cả các phương thức m
có thể được sử dụng lẫn nhau không bao gồm chính nó và song song với các phương
thức khác, giao thức có thể được chỉ ra như là một biểu thức chính quy
{? ! }*m Md m m∈ với biểu diễn sự chèn vào song song toán tử hợp.
Định nghĩa 4:
1
Wikipedia,
11
Hợp đồng 1 1 1 1 1 1 1 1( , ), , , , ,p r p rCtr I I MSpec Init Inv Inv Pro= được làm mịn của
đồng 2 2 2 2 2 2 2 2( , ), , , , ,p r p rCtr I I MSpec Init Inv Inv Pro= được biểu diễn là
1 2Ctr Ctr⊑ nếu và chỉ nếu:
• 1 2p pFd Fd⊆ , 1 2r rFd Fd⊆ , và 2 1 1 1p pInit Fd Init Fd= với hàm f và một
tập hợp A, f A biểu diễn cho sự thu hẹp (hạn chế) của f trên A.
• 1 2p pMD Md⊆ và 1 2r rMD Md⊆ .
• Đối với tất cả phương thức op được khai báo trong 1pMd thì
1 2( ) ( )MSpec op MSpec op⊑ và 2 1p pInv Inv⇒ .
• Đối với tất cả phương thức op được khai báo trong 2rMd thì
2 1( ) ( )MSpec op MSpec op⊑ và 1 2r rInv Inv⇒ .
• 1 1 2 1{ ?, !| } { ?, !| }p pPro m m m Fd Pro m m m Fd∈ ⊆ ∈ và
2 2 1 2{ ?, !| } { ?, !| }r rPro m m m Fd Pro m m m Fd∈ ⊆ ∈ .
Ta chứng tỏ định nghĩa này như sau. Ctr2 cung cấp tất cả các dịch vụ mà Ctr1
cung cấp, thậm chí còn tốt hơn và có thể cung cấp nhiều hơn, Ctr2 nên cần ít các dịch
vụ hơn Ctr1. Điều kiện 1 2r rInv Inv⇒ nói lên rằng thuộc tính của các biến đảm bảo
bởi Ctr2 cũng chắc chắn như bởi Ctr1. Trong phần tóm tắt, hợp đồng Ctr2 cung cấp
nhiều hơn, các dịch vụ tốt hơn và cần ít hơn các dịch vụ từ môi trường so với Ctr1. Do
vậy, ta dùng Ctr2 để thay thế Ctr1 mà không mất bất kì dịch vụ nào.
3.3. Kết hợp hợp đồng.
Các hợp đồng cáo thể được kết hợp lại theo nhiều cách để hình thành một hợp
đồng mới. Một cách khó khăn hơn cho việc tính toán một hợp đồng đa hợp là tính toán
về giao thức của nó. Điều này đã được loại bỏ trong lí thuyết hợp đồng. Cách đơn giản
nhất để kết hợp hai hợp đồng là đặt chúng cạnh nhau nếu chúng có các tập hợp đặc
tính và các phương thức rời nhau.
Định nghĩa 5
12
Lấy ( , ), , , , , , 1,2i pi ri i i pi ri iCtr I I MSpec Init Inv Inv Pro i= = , là 2 hợp đồng có
những tập hợp (yêu cầu và cung cấp) thuộc tính, phương thức riêng biệt. Phép kết hợp
của Ctr1 và Ctr2 là hợp đồng
1 2 1 2 1 2 1 2 1
1 2
2 1 2
( , ), , ,
, , ( )
p p r r p
p r r 1 2 1 2
I I I I MSpec MSpec Init Init Inv
Ctr Ctr
Inv Inv Inv Pro Pro Pro Pro
∪ ∪ ∪ ∪ ∪
∪ =
∪ ∪ ∪
Chỉ một điều cần thiết để giải thích trong định nghĩa trên là làm thế nào để giao
thức cho hợp các hợp đồng được định nghĩa. Khi đặt các hợp đồng cạnh nhau, bởi vì
chúng được giả định là độc lập, tất cả các phương thức và đặc tính của chúng có thể
được sử dụng song song. Thành phần song song 1 2Pro Pro đã xác định chính xác vấn
đề. Tuy nhiên, hợp đồng ghép cũng phải cho phép các phương thức trong một thành
phần độc lập được sử dụng theo cách nguyên bản.
Có một cách khác để kết hợp hợp đồng là kết nối các phương thức được yêu cầu
của một hợp đồng đến với các phương thức cung cấp của hợp đồng khác. Lấy
( , ), , , , , , 1,2i pi ri i i pi ri iCtr I I MSpec Init Inv Inv Pro i= = là các hợp đồng có các tập
hợp đặc tính và phương thức cung cấp phù hợp, các đặc tính và phương thức yêu cầu
phù hợp, ví dụ như 1 2( )p pf Fd Fd∈ ∩ suy ra 1 2( ) ( )Init f Init f= và
1 2 1 2( ) ( )p p r rop Md Md Md Md∈ ∩ ∪ ∩ suy ra 1 2( ) ( )MSpec op MSpec op⇔ . Giả
định rằng 1 2r pI I⊆ , 2 1p rInv Inv⇒ , 1 2( ) ( )MSpec op MSpec op⊑ đối với tất cả
1rop Md∈ .
Cắm đầy đủ của 1Ctr tới 2Ctr được biểu diễn là 1 2Ctr Ctr>> được định nghĩa là:
1 2 2 2
1 2
1 1 2 1 2 2,
( , ), ,
, ,
p p r
r p p r
I I I MSpec
Ctr Ctr
Init Fd Init Inv Inv Inv Pro
∪
>> =
∧⊎
Ở đây, ta nhận thấy tập các yêu cầu không phải là 1 2r rI I∪ mà chỉ là 2rI bởi vì
do 2Ctr được làm mịn từ 1Ctr nên 2Ctr có đầy đủ tập các yêu cầu của 1Ctr . Và vì thế,
1Ctr cắm đầy đủ vào 2Ctr .
Với 1 2( )( )Init Init x⊎ được định nghĩa là
13
1 2 1 2
1 1 2
2 2 1
( ) ( ) nê'u ( ) ( )
( ) nê'u ( ) \ ( )
( ) nê'u ( ) \ ( )
Init x Init x x dom Init dom Init
Init x x dom Init dom Init
Init x x dom Init dom Init
= ∈ ∩
∈
∈
Ta thảo luận ở đây cách mà giao thức Pro được tính toán từ , 1,2iPro i = với
hợp đồng 1 2Ctr Ctr>> .
• Thứ nhất, hợp đồng ghép 1 2Ctr Ctr>> cũng phải cho phép các phương thức
của một thành phần riêng biệt được sử dụng chúng theo cách nguyên bản.
Vậy 1 2Pro Pro∪ phải bao gồm Pro .
• Các phương thức m từ 2Ctr thì không được yêu cầu bởi 1Ctr có thể được sử
dụng song song với các phương thức trong 1Ctr . Vậy Pro phải bao gồm
2 1( {! ,? | \ }*)2 p rPro Pro m m m Md Md∩ ∈ .
• Câu hỏi ở đây là làm thế nào mà một phương thức m trong 2 1p rMd Md∩ lại
được sử dụng với một phương thức trong 1pMd . Câu trả lời phụ thuộc vào độ
song song của m. Việc tính toán cho trường hợp này rất phức tạp và được để
mở tại đây. Để an toàn, ta không cho phép chúng chạy song song (mặc dù
như vậy thì hiệu quả kém hơn).
Vậy ta định nghĩa Pro như sau:
2 2 1(Pr {! ,? | \ }*)1 2 1 p rPro Pro Pro Pro o m m m Md Md= ∪ ∪ ∩ ∈
Khi 1 2Ctr Ctr>> được định nghĩa, ta nói rằng 1Ctr có khả năng kết nối với 2Ctr .
Chú ý rằng khi kết hợp hai hợp đồng theo cách này thì thành phần kết quả có thể
không được sử dụng để thay thế 1Ctr . Lí do là nó có thể yêu cầu cái gì đó từ môi
trường mà 1Ctr không cung cấp.
Định lí 1
Lấy 1Ctr là khả kết nối với 2Ctr . Nếu 2Ctr là đóng (có nghĩa là 2rI = ∅ ) thì
1 1 2( )Ctr Ctr Ctr>>⊑ .
Chứng minh:
14
Bằng việc kiểm tra trực tiếp từ định nghĩa của toán tử cắm(plug operator) và định
nghĩa của làm mịn thiết kế. Định nghĩa có thể được chỉnh sửa trong trường hợp phổ
biến là 1 2r pI I và lí thuyết vẫn đúng. Bây giờ hãy hình thức hóa khái niệm của thành
phần. Bằng trực giác, một thành phần bị động là một cài đặt của một giao diện sử dụng
dịch vụ từ các thành phần bị động khác thông qua các hợp đồng của chúng. Với một
trình bày đơn giản, ta sử dụng một kiểu kiến trúc đơn giản với khởi tạo chủ/khách và
truyền thông đồng bộ.
Định nghĩa 6
Một thành phần bị động là một tập hợp hữu hạn ,Comp Ctr Mcode= với
Comp được xác định với tên của thành phần gồm có:
• Một hợp đồng ( , ), , , , ,p r p rCtr I I MSpec Init Inv Inv Pro=
• Mcode gán mỗi phương thức op trong pMd một thiết kế xây dựng từ các
toán tử cơ bản và phương thức trong
r
I như là ánh xạ của các vết trong thiết
kế này mà bấy kì
r
op Md∈ được thay thể bởi ? !op op từ bắt đầu và kết thúc
hành động, {? ! | }
r
m m m Md∈ được bao gồm trong Pro . Điều kiện sau đây
phải được thỏa mãn bởi Mcode : ( ( ) ( ))MSpec op Mcode op⊑ và pInv được
giữ bởi bất kì phép toán nào trong Mcode .
• Cài đặt của tất cả phương thức m phải tương thích với độ song song của
chúng được mô tả trong Pro , nghĩa là hoặc một phương thức m không phải
là một phương thức đặc biệt dùng chung hoặc một số bản sao thích hợp của m
tồn tại.
Thành phần bị động Comp được nói là cài đặt bởi Ctr .
Vậy một thành phần phải được kiểm chứng bởi thiết kế của nó. Ví dụ như cài đặt
của các phương thức phải được kiểm chứng thông qua các đặc tả của chúng. Tính
đúng đắn của nó có thể được kiểm chứng riêng biệt từ môi trường.
Lấy , , 1,2i i iComp Ctr Mcode i= = là các thành phần, với 1 2Ctr Ctr>> được
định nghĩa. Lấy được Mcode′ từ 1Mcode bằng việc thay thế mỗi lần xuất hiện của
1 2( )r pop Md Md∈ ∩ bằng 2( )Mcode op trong dãy của 1Mcode . Thật dễ dàng để
15
kiểm tra toàn bộ toán tử cắm định nghĩa trong các hợp đồng được mang theo trên các
thành phần.
Định lí 2:
1 2 1 2 2 1, \Ctr Ctr Mcode Mcode Md Md′>> ∪ là một thành phần.
Ví dụ: Lấy _double quadr là một thành phần với một dịch vụ
( : , , ; : 1)dquadr in real a b c out real x mà đưa ra là một đáp án x1 của phương trình
bậc 2 theo x2: 4 2 0ax bx c+ + = . Thành phần _double quadr yêu cầu dịch vụ
( : , , ; : 1)dquadr in real a b c out real x từ thành phần khác mà khi được gọi với các
tham số a, b, c thích hợp thì sẽ trả lại đáp án của phương trình 2 0ax bx c+ + = .
Thành phần _double quadr được mô tả bằng đoạn mã bên dưới.
Phần chủ động gồm có vài tiến trình và một giao diện yêu cầu, mà có thể được
gắn và phần bị động. Một tiến trình được mô tả bởi một chương trình sử dụng các dịch
vụ từ phần bị động để phản ứng lại các sự kiện từ môi trường của hệ thống. Các sự
kiện không được điều khiển bởi hệ thống. Vậy các sự kiện thú vị từ môi trường và dịch
vụ hệ thống đi cùng nhau với các đặc tả của nó và giao thức tương tác hình thành hợp
đồng giữa hệ thống và môi trường của nó.
Thực tế, đây là một mô hình thành phần dùng để giải bài toán phương trình bậc 4
dạng đặc biệt. Nếu ta đặt X = x2 thì phương trình sẽ trở thành dạng bậc 2.
component double_quadr {
provide method {
name { dquadr(in : real a, b, c; out : real x1) },
specification{ ac ≤ 0 • ax14 + bx12 + c = 0}
}
required method{
name{ quadr(in : real a, b, c; out : real x1)},
specification{ ac ≤ 0 • ax12+bx1+c = 0∧x1 ≥ 0}
}
protocol{ (?dquadr!dquadr)∗ ⊕ (?quadr!quadr)∗}
16
implementation{
name{ dquadr(real in : a, b, c, real out : x1)},
code{quadr(in : a, b, c; out : x1); x1 := sqrt(x1)}
}
}
Định nghĩa 7
Một giao diện hệ thống là một cặp ( , , )pSI E Fd SMd= với pSMd là một tập
hợp hữu hạn các phương thức, Fd là một tập hợp hữu hạn các đặc tính, và E là tập
hợp hữu hạn các sự kiện.
Định nghĩa 8
Một hợp đồng hệ thống là một tập hợp hữu hạn
ys , , ,S Ctr SI SMSpec Inv Behav=
với
• ( , , )pSI E Fd SMd= là một giao diện hệ thống được định nghĩa ở trên.
• MSpec là một đặc tả phương thức kết hợp với mỗi phương thức
( , )op in out trong pSMd với một thiết kế , FPα với
( \ ( )) din out Fα ∪ ⊆ .
• Behav là một mô tả hành bi bên ngoài. Nó là một tập con hữu hạn của
{ , | và }*pe m e E m SMd∈ ∈ . Mỗi yếu tố của Behav được gọi là một đặc
tả tiến trình.
Một nghĩa không chính thức của dãy α trong Behav là nếu môi trường hệ
thống cung cấp dãy các sự kiện như là biến cố trong α do vậy hệ thống cung cấp dãy
các dịch vụ (phương thức) chỉ rõ bởi α theo thức tự. Các phần tử của Behav được mô
tả bởi các luồng chương trình đang chạy song song. Một iểu hiện ngữ nghĩa của
Behav có thể được định nghĩa trong logic thời gian phù hợp cho miền ứng dụng đang
nghiên cứu.
Định nghĩa 9
Một thành phần chủ động , ,ActComp Ctr SysCtr Mcode= bao gồm
17
• Một hợp đồng ( , ), , , , ,p r p rCtr I I MSpec Init Inv Inv Pro= với giao diện
cung cấp rỗng, ( , )pI = ∅ ∅ .
• Một hợp đồng hệ thống ys , , ,S Ctr SI SMSpec Inv Behav= .
• Một cài đặt tiến trình Mcode gán mỗi một phương thức op trong pSMd
một thiết kế xây dựng từ các toán tử cơ bản và phương thức trong
r
I như
là phép chiếu vết của thiết kế này trong bất kì phương thức
r
op Md∈
được thay thế bởi ? !op op (tự bắt đầu và kết thúc hành động), trên
{? ,! | }
r
m m m Md∈ được bao gồm trong Pro . Điều kiện sau đây phải
được thỏa mãn bởi : ( ( ) ( ))Mcode SMspec op Mcode op⊑ cho tất cả
pop SMd∈
Một hệ thống trong mô hình thành phần này là một thành phần chủ động được
gắn vào một thành phần bị động đóng.
Định nghĩa 10
Một hệ thống là một cặp của một thành phần chủ động
, ,ActComp Ctr SysCtr Mcode=
và một thành phần bị động đóng ,Comp Ctr Mcode′ ′= với Ctr Ctr′>> đã
được định nghĩa.
Vậy một hệ thống thành phần là một hệ thống đóng không yêu cầu bất kì dịch vụ
nào từ môi trường và cung cấp dịch vụ của nó cho môi trường như là phản ứng của nó
đáp sự kiện kích thích từ môi trường. Đặc tả của một hệ thống là hợp đồng hệ thống
ysS Ctr . Hai hệ thống là tương đương nhau nếu và chỉ nếu chúng có cùng đặc tả,
nghĩa là chúng có giao diện hệ thống tương đương. Định lí sau đây cho thấy đặc trưng
quan trọng nhất của lập trình dựa trên thành phần.
Định lí 3
Lấy ( , )S ActComp Comp′= là một hệ thống làm thành từ thành phần chủ động
, ,ActComp Ctr SysCtr Mcode= và thành phần bị động ,Comp Ctr Mcode′ ′ ′= .
18
Lấy ,Comp Ctr Mcode′′ ′′ ′′= là một thành phần bị động, Ctr Ctr′ ′′⊑ . Nên
( , )ActComp Comp′′ cũng là một hệ thống tương đương với S.
4. MÔ HÌNH THÀNH PHẦN THỜI GIAN THỰC
Các mô hình được trình bày trong phần trước có thể được mở rộng với một số
đặc tính về thời gian để trở thành mô hình thành phần cho hệ thống thời gian thực.
Trong phần này, ta thảo luận về cách thức thực hiện. Phần quan trọng của việc mở
rộng nằm ở các dịch vụ thời gian thực, các giao thức tương tác thời gian thực và các
hợp đồng thời gian thực. Các đặc tả của phương thức phải có thêm ràng buộc về thời
gian.
4.1. Các thiết kế có nhãn ràng buộc về thời gian sử dụng như dịch vụ.
Các hệ thống thời gian thực có một số ràng buộc về mặt thời gian trên các dịch
vụ như là thời gian đáp ứng và ràng buộc về tài nguyên như là yêu cầu bộ nhớ, băng
thông và tiêu thụ điện năng. Sử dụng lí thuyết lập trình thống nhất để xác định các dịch
vụ như thiết kế giúp ta dễ dàng mở rộng nên gọi là “thiết kế có nhãn ràng buộc về thời
gian” mà cũng có thể xác định các yêu cầu tài nguyên và các trường hợp thời gian thực
hiện xấu nhất cho một dịch vụ như là một mối quan hệ giữa tiền và hậu điều kiện cho
các thành phần chức năng của dịch vụ. Tiền điều kiện cho một phương thức là một vị
từ trên các biến chương trình cũng như các biến tài nguyên, và hậu điều kiện cho một
phương thức là một mối quan hệ trên các biến chương trình và các trường hợp thời
gian thực hiện dur xấu nhất và các biến tài nguyên. So với cách tiếp cận otomat thì
thiết kế có nhãn ràng buộc về thời gian thể hiện tốt hơn.
Ta có thiết kế có nhãn ràng buộc về thời gian , ,D FP FRα= với α là tập các
biến chương trình được sử dụng bởi phương thức, FP biểu diễn đặc tả chức năng và
FR biểu diễn đặc tả phi chức năng. Trong thiết kế trên, FP đã được chỉ ra ở phần
trước. FR là một vị từ của dạng thức q• n S q S⇒≙ với q là tài nguyên tiền điều kiện
cho phương thức trong giao diện được đề cập là giả định trên các tài nguyên được sử
dụng bởi phương thức và được đại diện như là vị từ trên các biến trong RES
( 1 nRES = {res ,...,res } là tập cố định các biến số nguyên). S là hậu điều kiện có ràng
buộc về thời gian cho phương thức mà quan hệ với mỗi lượng thời gian l tiêu tốn cho
việc thực thi phương thức và tài nguyên được sử dụng cho phương thức. S được đại
diện cho một vị từ trên các biến trong RES, α và l. Ta lấy một ví dụ mô tả cho ý nghĩa
của FR. Lấy , 0{x,y} FP xα ≥≙ ≙ • f 2y x= và 133 266 1FR P P+ =≙ • r
19
(( 133 1 0.001) ( 133 0 0.0005))P l P l= ⇒ ≤ ∧ = ⇒ ≤ . Khi ấy , ,FP FRα đại diện
cho thiết kế có nhãn ràng buộc về thời gian để tính toán y x= cho một số x không
âm với thời gian không quá 0.001 đơn vị thời gian khi thực hiện bằng bộ xử lí 133
MHz và không quá 0.0005 đơn vị thời gian khi thực hiện với bộ xử lí 266MHz.
Làm mịn thiết kế có nhãn ràng buộc về thời gian
Cũng giống với thiết kế trong mô hình thành phần, thiết kế có nhãn ràng buộc về
thời gian cũng có khái niệm làm mịn. Nó chỉ mở rộng thêm một phần nhỏ so với khái
niệm làm mịn thiết kế được nêu ra ở phần trước.
Một thiết kế 2 2 2, ,D FP FRα= được gọi là làm mịn từ 1 1 1, ,D FP FRα=
(biểu diễn là 1 2D D⊑ ) nếu và chỉ nếu
2 1 2 1( , , , ) ( , )ok ok v v FP FP r l FR FR′ ′∀ • ⇒ ∧ ∀ • ⇒
Với v, v’ là các véc tơ của biến chương trình, r biểu thị một véc tơ của biến tài
nguyên, 1 nr = (res ,...,res ). Phần đầu của phép toán VÀ ( ∧ ) là muốn nói lên thành
phần chức năng D2 là bản làm mịn của phần chức năng D1. Phần tiếp theo của phép
toán VÀ nói rằng nếu yêu cầu phi chức năng của D2 được thỏa mãn thì yêu cầu phi
chức năng của D1 cũng được thỏa mãn. Vậy D2 có thể cài đặt D1.
Thành phần tuần tự.
Lấy 1 1 1 1, ,D FP FRα= và 2 2 2 2, ,D FP FRα= là hai thiết kế có nhãn phụ
thuộc thời gian. Vậy, 1 2; , ,D D Fp FRα≙ với
• 1 1( )FP FP v′= và 2 2( )FP FP v=
• 1 2 1 2 2 1 2, ( [ ] [ ] )1FR l l FR l / l FR l / l l l l∃ • ∧ ∧ = +≙
Từ đây về sau, ta sẽ sử dụng 1[ ]F x / x để biểu diễn biểu thức kết quả của việc
thay thế x bằng x1 trong biểu thức F. Từ đó tài nguyên được sử dụng cho D1 có thể
được sử dụng lại cho D2 khi mà D1 kết thúc.
Phân tách thành phần song song.
Lấy 1 1 1 1, ,D FP FRα= và 2 2 2 2, ,D FP FRα= là các thiết kế có nhãn phụ
thuộc thời gian. Giả thiết rằng 1 2α α∩ = ∅ . Vậy 1 2|| , ,D D FP FRα≙ khi
20
• 1 2α α α∪≙ và 1 2FP FP FP∧≙
•
1 2 1 2 1 1
2 2 2 1 2 1 2
, , , ( , /
[ / , . ] max{ , }
1FR l l r r FR [l / l r r]
FR l l r r l l l r r r )
∃ • ∧
∧ = ∧ = +
≙
với r1 và r2 là các véc tơ
của biến tài nguyên và r1+r2 đã được định nghĩa.
Điều kiện 1 2r r r= + biểu thị số lượng các biến tài nguyên đủ để thực thi 1D và
2D song song một cách độc lập. Lệnh composed được hoàn thành khi cả hai lệnh
thành phần được hoành thành. Để lí giải hai định nghĩa này, ta có thể sử dụng ngữ
nghĩa mang tính hoạt động cho chương trình được định nghĩa như là một hệ thống
chuyển tiếp có nhãn ( , , )S C→ với mỗi trạng thái s S∈ là một tập hợp hữu hạn.
( , , )v r t . Trong đó v là một véc tơ các giá trị của biến chương trình, r là một véc tơ các
giá trị của biến tài nguyên và t là một số thực để chỉ thời gian thực. C là một tập lệnh.
Lấy ngữ nghĩa của c C∈ là thiết kế , ,FP FRα với fFP p R= ⊢ và r nFR p S= ⊢ .
Vậy có một phép chuyển ( , , ) ( , , )cv r t v r t′ ′ ′→ nếu và chỉ nếu
( ) ( , ) ( ) ( , , , )
r
p v R v v r r p r l t t S l r v v′ ′ ′ ′∧ ∧ = ∧ ∧ = − ∧ thông qua sự thông dịch của
các thiết kế. Việc định nghĩa phân tách thành phần song song và thành phần tuần tự
hiển nhiên trong hệ thống chuyển tiếp nhãn trùng với định nghĩa đã cho ở trên.
Đối với hợp đồng trong hệ thống dựa trên thành phần thời gian thực có sự khác
biệt so với hệ thống dựa trên thành phần đơn thuần. Ta có định nghĩa về hợp đồng có
nhãn ràng buộc về thời gian.
Định nghĩa
Một hợp đồng có nhãn ràng buộc về thời gian là một tập hợp hữu hạn
, , , ,I Rd MSpec Init Inv với
• ,I Fd Md= là một giao diện.
• Rd là một khai báo tài nguyên, nó là một tập con của RES.
• Init là một khởi tạo, kết hợp với mỗi biến trong Fd và mỗi biến cục bộ với
cùng một kiểu giá trị. Biến trong Rd với kiểu số nguyên.
21
• MSpec là đặc tả phương thức kết hợp với mỗi phương thức ( , )op in out
trong Md với một thiết kế có nhãn ràng buộc về thời gian , ,FP FRα ,
trong đó ( \ ( ))in out Fdα ∪ ⊆ .
• Inv là một vị từ trên các đặc tính trong hợp đồng (được gọi là bất biến hợp
đồng). Inv đại diện cho một thuộc tính bất biến của giá trị biến trong khai
báo đặc tính Fd mà có thể tin cậy tại bất kì thời điểm nào mà mó có thể
truy cập từ bên ngoài. Từ đây, Inv được thỏa mãn một cách đặc biệt bởi
Init.
Ta nhấn mạnh ở đây là các biến tài nguyên được khai báo trong Rd là biến nội
trong một hợp đồng (biến cục bộ). Inv trong một hợp đồng biểu diễn một thuộc tính
của các biến trong hợp đồng mà nó cung cấp cho môi trường. Trong trường hợp hợp
đồng không đảm bảo bất kì một thuộc tính bất biến nào của các giá trị của nó thì Inv là
đúng.
Các hợp đồng này cũng cần được làm mịn. Từ thực tiễn nghiên cứu vấn đề, ta có
định nghĩa về làm mịn hợp đồng như sau:
Hợp đồng có ràng buộc về thời gian
2 2 2 2 2 2 2, , , , ,Ctr Fd Md Rd MSpec Init Inv=
là được làm mịn bằng hợp đồng
1 1 1 1 1 1 1, , , , ,Ctr Fd Md Rd MSpec Init Inv= ,
(được biểu diễn là 1 2Ctr Ctr⊑ ) nếu và chỉ nếu:
• 1 2Fd Fd⊆ , 1 2Rd Rd⊆ và 2 1 1 1 2 1 1 1| | , | |Init Fd Init Fd Init Rd Init Rd= ≤
đối với các hàm 1 2, ,f f f và tập A. |f A biểu thị hạn chế của f trên A và
1 2f f≤ biểu thị rằng f1 và f2 có cùng miền và 1 2( ) ( )f x f x≤ với mọi x
trong miền của chúng.
• 1 2Md Md⊆ .
• Với mọi phương thức op được khai báo trong 1Md thì
1 2( ) ( )Mspec op Mspec op⊑ và 2 1Inv Inv⇒ .
22
Ta lý giải định nghĩa này như sau. 2Ctr cung cấp tất cả các dịch vụ mà 1Ctr cung
cấp và có thể cung cấp nhiều hơn nữa. 2Ctr phải có ít nhất cùng tài nguyên như là 1Ctr
có. Điều kiện 2 1Inv Inv⇒ nói lên rằng thuộc tính của các biến được đảm bảo bởi 1Ctr
thì cũng chắc chắn được đảm bảo bởi 2Ctr . Vật có thể thay thế 1Ctr bằng 2Ctr mà
không bị mất bất kì một dịch vụ nào.
Đặt , , , , , 1,2i i i i i iCtr Fd Md Rd Mspec Init i= = là các hợp đồng có ràng buộc
về thời gian tương thích với tập hợp các đặc tính và phương thức. Có nghĩa là
1 2f Fd Fd∈ ∩ bao hàm cả 1 2( ) ( )Init f Init f= và 1 2op Md Md∈ ∩ bao hàm cả
1 2( ) ( )MSpec op MSpec op⇔ . Kết hợp hợp đồng 1 2Ctr Ctr∪ được định nghĩa như
sau:
1 2 1 2 1 2
1 2
1 2 1 2 1 2
( , ), ,
, ,
Fd Fd Md Md Rd Rd
Ctr Ctr
MSpec MSpec Init Init Inv Inv
∩ ∩ ∪
∪ =
∪ ∧⊎
với 1 2( )( )Init Init x⊎ được định nghĩa là
1 2
1
2
{ ( ), ( )} nê'u
( ) nê'u
( ) nê'u
1 2
1 2
2 1
max Init x Init x x dom(Init ) dom(Init )
Init x x dom(Init )\ dom(Init )
Init x x dom(Init )\ dom(Init )
∈ ∩
∈
∈
Khi 1 2Ctr Ctr∪ được định nghĩa thì ta có thể nói 1Ctr và 2Ctr có thể rút gọn.
Chú ý rằng khi kết hợp 2 hợp đồng, lượng tài nguyên có sẵn để kết hợp được định
nghĩa như là với thành phần hợp đồng lớn nhất. Định nghĩa này phản ánh cái nhìn một
phương thức trong kết hợp hợp đồng phải có ít nhất cùng thời gian thực hiện như là nó
có trong các hợp đồng thành phần, được cung cấp đúng mẫu. Đúng mẫu có nghĩa là
thực thi phụ thuộc thời gian tốt hơn nếu có nhiều tài nguyên được cung cấp và được
hình thức hóa. Một thiết kế có ràng buộc về thời gian , ,FP FRα được gọi là đúng
mẫu nếu và chỉ nếu FR thỏa mãn 1 1 1, ( ( [ / ] [ / ]))r r r r FR r RES FR r RES∀ • ≥ ⇒ ⇒ .
Với r và r1 là các véc tơ giá trị của các biến tài nguyên.
4.2. Sử dụng các ngôn ngữ hình thức có nhãn ràng buộc về thời gian để đặc
các giao thức tương tác thời gian thực và đặc tả tiến trình.
Giao thức tương tác cho các thành phần thời gian thực phải mang theo không chỉ
các thông tin theo thứ tự thời gian của hành động giao tiếp mà còn cả ràng buộc thời
gian của chúng. Như trong lí thuyết otomat có nhãn ràng buộc về thời gian, ta có thể
gán nhãn cho một biến cố của một hành động giao tiếp với thời gian xảy ra. Một chuỗi
23
các hoạt động truyền thông được gán nhãn theo các này được gọi là “từ thời gian” (từ
có nhãn ràng buộc về thời gian). Nó biểu diễn hành vi của hệ thời gian thực là một dãy
tiến hành trong đó mỗi biến cố đều có nhãn thời gian chỉ biểu diễn khoảng thời gian
trôi qua kể từ biến cố liền trước. Một tập hợp của chuỗi có nhãn thời gian của các hành
động có thể giao tiếp có thể biểu thị một giả thiết bằng một thành phần về hành vi thời
gian thực trong môi trường của nó. Ngôn ngữ có nhãn ràng buộc về thời gian được
nghiên cứu kĩ và hiểu rõ, từ đây có thể sử dụng chúng cho các đặc tả của các giao thức
tương tác, các tiến trình có nhãn ràng buộc thời gian thực thuận lợi hơn.
Đối với hiệu quả trong việc kiểm chứng một phương thức thời gian thực trong
các thành phần, các giao thức trong ràng buộc phải không có bất kỳ thông tin về thời
gian, và thông tin thời gian cho một giao thức được bắt nguồn từ những đặc tả của
phương thức thời gian thực từ các giao thức.
4.3. Các hợp đồng thời gian thực.
Các hợp đồng thời gian thực được định nghĩa theo cùng một cách như đối với
các hợp đồng trong phần trước. Các định nghĩa của giao diện được mở rộng bằng cách
cho phép của các khai báo của tài nguyên được nhóm lại vào trong tài nguyên có thể
tiêu thụ được và tài nguyên không thể tiêu thụ được. Những bất biến hợp đồng giao
diện phải mở rộng để mô tả những những sự ràng buộc trên tài nguyên. Trong các thiết
kế có nhãn ràng buộc về thời gian của hợp đồng thời gian thực được sử dụng thay vì
các thiết kế. Một thành phần thời gian thực là một cài đặt của một hợp đồng thời gian
thực. Ta đưa ra đây một ví dụ về hệ thống thành phần thời gian thực dựa trên mô hình
đã được nghiên cứu ở trên.
Ta có ví dụ minh họa sau đây.
Ở đây, ngưỡng tài nguyên đặc tính chỉ rõ bộ nhớ thiết lập cho thành phần, và
s.event chỉ rõ tín hiệu từ lập lịch định kì gửi đến tiến trình. Ta sử dụng biểu thức chính
quy có nhãn rang buộc về thời gian để biểu diễn hành vi có ràng buộc về thời gian của
tiến trình. Mô hình hệ thống thành phần này là một bộ điều khiển định kì thu thập tín
hiệu điều khiển thông qua tác tử dựa trên dữ liệu chúng cảm nhận được. Thời gian
định kì của vòng điều khiển là 100ms.
component Actuator1{
provided feature int p1;
inv p1 > 0;
24
resource int threshold = 20;
provided method{
name getdata(),
specification true • p10 = portvalue ∧ p10 > 0 ∧ dur = 0
};
provided method{
name execute(),
specification p1 = valid ˫(actionresult ∧ dur = 30)
};
};
component Actuator2{
provided feature int p1;
inv p1 > 0;
resource int threshold = 30;
provided method{
name getdata(),
specification true ˫p10 = portvalue ∧ p10 > 0 ∧ dur = 0
};
provided method{
name execute(),
specification p1 = valid ˫(actionresult ∧ dur = 30)
};
};
active component Composition{
process{
25
name main,
specification
((s.event; actuator1.execute()||actuator2.execute();
actuator1.getdata; actuator2.getdata; ), dur ≤ 100)∗
}
4.4. Thành phần bị động
Định nghĩa
Một thành phần bị động thời gian thực là một tập hợp hữu hạn
, , , ,Comp Ctr Dep SDep Mcode SInv= với Comp được xác định với tên của
thành phần, nó bao gồm:
• Một hợp đồng , , , , ,Ctr Fd Md Rd MSpec Init Inv= .
• Tập hợp Dep của tên các thành phần, mỗi phần tử của Dep là một tên của
thành phần mà Comp phụ thuộc vào.
• SDep là tập hợp các biến trong ∏ (đại diện cho sự tương tác với bộ lập
lịch).
• SInv là một vị từ trên các biến v SDep∈ (để biểu diễn giả thiết thông tin mà
bộ lập lịch có thể tin cậy khi một phương thức trong Comp được gọi).
• Mcode gán mỗi phương thức op trong Md một thiết kế được xây dựng từ
các toán tử cơ bản và các lời gọi phương thức từ dạng thức
1( , , )call Comp C op , với 1op là một phương thức trong thành phần C trong
Dep . Chú ý rằng các tên phương thức, biến tài nguyên và biến cục bộ được
sử dụng trong đặc tả và cài đặt của phương thức 1( , )op in out trong thành
phần bị động C là cục bộ trong C và có tiền tố là “Ci ” để chống lại sự lẫn lộn
với các biến được sử dụng trong các thành phần bị động khác. Lấy Env biểu
thị vị từ ( ( ( )) ( ))U Dep Inv Ctr U SInv U∈ ∧∧ (từ đây trở đi, ta sử dụng ( )Ctr U
để biểu thị hợp đồng của thành phần U, ( ( ))Inv Ctr U để biểu thị bất biến của
hợp đồng thành phần U, ( )Dep U biểu thị tập hợp tên thành phần mà U phụ
26
thuộc và ( )SInv U biểu thị bất biến lập lịch hệ thống của thành phần U). Điều
kiện sau đây phải được thỏa mãn bởi Mcode :
Env ( ( ) ( ))MSpec op Mcode op⊑ và Inv được chiếm giữ bởi bất kì phép
toán nào được sử dụng trong Mcode. Lấy C Dep∈ và op C∈ . Do vậy
( , , )call Comp C op được định nghĩa như ( , ) ||Schedule Comp C C opi , với
( , )Schedule Comp C là một thiết kế sử dụng các biến trong ( )SDep C (giá trị
các biến này đạt diện cho những lời gọi hiện tại đến một phương thức trong
C. Ta mong đợi tiền điều kiện của ( , )Schedule Comp C được bao hàm bởi
( )SInv C ). Từ luật phân tách song song, ( , ) ||Schedule Comp C C opi bao
hàm đặc tả chức năng của C opi nhưng không cần thêm thời gian để thực
hiện.
Thành phần Comp nói lên rằng nó được cài đặt bởi hợp đồng Ctr .
Trong định nghĩa của thành phần Comp , nó yêu cầu ( ) ( )MSpec op Mcode op⊑
cho tất cả các phương thức op trong hợp đồng của Comp theo giả định
( ( ( )) ( ))U Dep Inv Ctr U SInv U∈ ∧∧ . Điều này có nghĩa là được cung cấp tất cả các
thành phần mà Comp phụ thuộc vào phải đảm những bất biến của chúng, bất kì
phương thức nào của thành phần Comp được cài đặt đúng đắn. Cũng như vậy, ta yêu
cầu bất kì phép toán nào trong Comp phải đảm bảo bất biến của Comp . Bởi vậy op
có thể được sử dụng như là một dịch vụ thích hợp với đặc tả ( )MSpec op . Có một câu
hỏi được đặt ra là làm thế nào để chắc chấn rằng ( ( ( )) ( ))U Dep Inv Ctr U SInv U∈ ∧∧
được đảm bảo? Cài đặt của op tin cậy vào các phương thức trong thành phần với tên
trong Dep. Nhưng cài đặt của các phương thức cuối cùng lại tin cậy vào op. Tình
huống này đã đưa đến lí luận vòng quanh và nó có thể là nguyên nhân làm cho op
được cài đặt không chính xác. Tình huống này sẽ không xảy ra nếu cài đặt tốt cho
phương thức được định nghĩa.
Định nghĩa về cài đặt tốt.
Các phương thức được cài đạt tốt được định nghĩa đệ quy như sau:
• Nếu op là một phương thức trong một thành phần với mã lệnh ( )Mcode op
được biên soạn từ các lệnh cơ bản thì op là được cài đặt tốt.
27
• Nếu op là một phương thức trong một thành phần với mã lệnh ( )Mcode op
được biên soạn từ các lệnh cơ bản và các lời gọi phương thức cho một
phương thức được cài đặt tốt thì op là được cài đặt tốt.
Vậy phương thức được cài đặt tốt không chứa các lời gọi phương thức đệ quy,
mặc dù các phương thức chứa các lời gọi phương thức đệ quy có thể kết thúc và có
ngữ nghĩa được định nghĩa tốt.
Từ các kết quả trên, ta đưa ra giải quyết vấn để kết hợp thành phần. Lấy
, , , , , 1,2i i i i i iC Ctr Dep SDep Mcode Inv i= = là các thành phận bị động có các hợp
đồng có thể tổ hợp và thỏa mãn 1 2( ) ( )Mcode op Mcode op≡ đối với tất cả
1 2op Md Md∈ ∩ . Tổ hợp 1 2C C∪ được định nghĩa là:
1 2 1 2 1 2 1 2 1 2, , , ,Ctr Ctr Dep Dep SDep SDep Mcode Mcode SInv SInv∪ ∪ ∪ ∪ ∪
Cần lưu ý một vài điểm sau:
• Các phương thức trong các thành phần được định nghĩa như các thiết kế với
tiền điều kiện, hậu điều kiện và các quan hệ trên lượng thời gian để thực thi
các phương thức, tài nguyên sẵn có. Điều này phù hợp cho việc chỉ rõ các hệ
thống ngừng hoạt động. nhưng nó không đủ mạnh để biểu diễn hoạt động của
các chương trình không dừng hoặc hệ thống tương tác.
• Định nghĩa của một thành phần Comp yêu cầu ( ) ( )Mspec op Mcode op⊑
với giả định ( ( ( )) ( ))
U Dep
Inv Ctr U SInv U
∈
∧∧ . Điều kiện ( ( ))Inv Ctr U trên
các biến được sử dụng để cài đặt đặc tả chức năng cho phương thức op, được
đảm bảo bởi tất cả các thành phần U. Điều kiện ( )SInv U trên các biến
( )SDep U chỉ được sử dụng bởi bộ lập lịch và được sử dụng để cài đặt đặc tả
phi chức năng của phương thức. Bởi vậy, nếu ( )SInv U được kiểm chứng như
là một bất biến toàn cục cho hệ thống đáp ứng không ràng buộc về thời gian
thì nó cũng phải là một bất biến của hệ thống có ràng buộc thời gian nữa.
Kiểm chứng của bất biến ( )SInv U cho hệ thống đáp ứng không ràng buộc về
thời gian được thực hiện với các kĩ thuyệt truyền thống. Ví dụ như khi không
cần thiết phải lập lịch (tức là sử dụng song song của các dịch vụ được chấp
nhận hoặc các dịch vụ chỉ đực gọi bởi duy nhất một thành phần tại một thời
điểm, ( )SDep U = ∅ với tất cả U) và sau đó ta có thể có
28
( , ) , , 0Schedule Comp C skip l= ∅ = (sau khi ta giả định rằng các tính toán
luôn luôn cần thời gian và từ đây về sau, đặc tả thời gian cho bộ lập lịch trong
trường hợp này phải được thay đổi thành 0l l d> ∧ ≤ với d là lương thời
gian nhỏ nhất cần để thực hiện lệnh với giả thiết về các tài nguyên trong hệ
thống). Tiền điều kiện cho ( , )Schedule Comp C là đúng và ( )SInv C có thể
đúng là bất biến tầm thường. Thêm một ví dụ khác, giả định rằng bộ lập lịch
sử dụng chính sách “đến trước phục vụ trước” (FIFO) và lượng thời gian lớn
nhất mà mỗi lần một thành phần sử dụng một dịch vụ của thành phần Comp
là a, và có khoảng n thành phần khác có thể sử dụng các dịch vụ của Comp .
Vậy ta có ( ) ( ), , x Schedule Com SDep U FP l n a= ≤ . Liệu có phải có các
lời gọi đồng thời tới một thành phần hoặc không phụ thuộc vào nếu có các
phương thức chủ động đồng thời trong hệu thống. Nếu nghôn ngữ cho phép
một phương thức được cài đặt với các lệnh song song hoặc nếu có nhiều hơn
một luồng đang chạy song song trong hệ thống.
Từ phần đã nói ở trên ta có lí do để định nghĩa một thành phần Comp2 được làm
mịn bởi Comp1 nếu và chỉ nếu Comp2 tốt hơn Comp1 theo nghĩa Comp2 cung cấp nhiều
hơn các dịch vụ của Comp1 nhưng cần ít dịch vụ hơn Comp1 và điều kiện lập lịch trong
Comp2 kém hơn trong Comp1 (có nghĩa là Comp2 có bất biến mạnh hơn cho bộ lập
lịch, cũng đồng nghĩa bộ lập lịch hoạt động với Comp1 thì cũng hoạt động với Comp2).
Vậy ta có định nghĩa cho làm mịn thành phần như sau: (định nghĩa 11)
Lấy , , , , , 1,2i i i i i iComp Ctr Dep SDep Mcode SInv i= = là các thành phần bị
động. Comp1 được gọi là làm mịn bởi Comp2 (được biểu thị là 1 2Comp Comp⊑ ) nếu
và chỉ nếu:
• 1 2Ctr Ctr⊑ (tức là Comp2 cung cấp nhiều dịch vụ hơn Comp1).
• 2 1Dep Dep⊆ , 2 1SDep SDep⊆ và 1 2SInv SInv⇒ (tức là Comp2 không
cần nhiều dịch vụ từ hệ thống như Comp1 và cần giả thiết yếu hơn về lập
lịch hệ thống).
4.5. Thành phần chủ động
Thành phần chủ động được định nghĩa theo cách giống như thành phận bị động
được định nghĩa ngoại trừ rằng thành phần chủ động phải có khai báo luồng song và
các khái báo biến cố. Thành phần chủ động được điều khiển bởi cả các biến cố từ môi
29
trường và đồng hồ bên trong nó. Một luồng T được định nghĩa always follows D e
với e là một biến cố dạng biểu thức nhị phân và D là một phương thức. Ý nghĩa của
biểu diễn “ follows D e ” là e ok D⇒ ∧ . Nói chung thì luồng T đang lắng nghe các
biến cố của cự kiện e. Bất kì khi nào mà biến cố e xảy ra, phương thức D sẽ được gọi.
Định nghĩa 12
Một hệ thống dựa trên thành phần là một tập S của các thành phần sao cho bất kì
thành phần chủ động U S∈ nào, bất kì V sao cho VU Dep* mà V S∈ chiếm giữ.
Trong một hệ thống dựa trên thành phần, ta có thể thay thế một thành phần bị
động bằng một thành phần tốt hơn mà không vi phạm các yêu cầu. thật vậy, ta có định
lí sau.
Định lí 4
Lấy S là một hệ thống dựa trên thành phần. 1Comp và 2Comp là các thành phần
bị động sao cho 1 2Comp Comp⊑ và 1Comp S∈ . S1 có được bằng việc thay thế
1Comp bằng 2Comp và đồng thời thay thế mỗi biến cố của 1Comp trong hệ thống S
bằng một biến cố của 2Comp . Do vậy, S1 cũng là một hệ thống dựa trên thành phần và
cung cấp nhiều dịch vụ hơn S.
Ta sẽ chứng minh định lí này như sau:
Điều duy nhất cần để chứng minh là sau khi thay thế các biến cố của 1Comp
bằng các biến cố của 2Comp thì kết quả vẫn là một tập hợp các thành phần của hệ
thống. Có nghĩa là ta phải thể hiện điều đó cho bất kì phương thức op nào trong hợp
đồng của một thành phần kết quả C, ( ) ( )Mspec op Mcode op⊑ theo giả thiết
( )
( ( ( )) ( ))
U Dep C
Inv Ctr U SInv U
∈
∧∧ . Từ định nghĩa 11 ở trên về làm mịn thành phần, nó
kéo theo
1 1 2 2( , ) || ( , ) ||Schedule Comp Comp Comp op Schedule Comp Comp Comp opi i⊑
cho bất kì phương thức op nào trong 1Comp . Từ sự đơn điệu của các phép toán trong
việc sử dụng ngôn ngữ lập trình theo quan hệ làm mịn, và từ thực tế là
2 1( ) ( )SInv Comp SInv Comp⇒ , ta có ( ) ( )Mspec op Mcode op⊑ giữ với giả thiết
( )
( ( ( )) ( ))
U Dep C
Inv Ctr U SInv U
∈
∧∧ .
30
5. ỨNG DỤNG MÔ HÌNH THÀNH PHẦN TRONG HỆ THỐNG NHÚNG
Từ quá trình nghiên cứu về mô hình hệ thống dựa trên thành phần và mô hình
thời gian thực ta có thể xây dựng một mô hình thành phần trên hệ thống nhúng. Hiện
nay, hầu hết các công việc của con người đã được áp dụng công nghệ, tự động hóa
nhằm mục đích nâng cao hiệu quả công việc, đảm bảo an toàn cho con người. Cùng
với mục đích đó, hệ thống hướng dẫn xe (Car Navigation System – viết tắt là CNS)
được xây dựng nhằm dẫn đường cho các lái xe đi qua một khu vực. Để tương tác với
lái xe, hệ thống phải có một thiết bị hiển thị để thể hiện bản đồ của khu vực xung
quanh xe, một bàn phím để thực hiện các lệnh cơ bản như hiển thị bản đồ, phóng
to/thu nhỏ và tìm đường đi tới đích.
Một thành phần đặt cơ sở thiết kế cho CNS mà được thể hiện trong hình 6, gồm
có những thành phần chính sau đây, trong đó quan hệ Dep giữa những thành phần
được đại diện cho bởi những mũi tên trong hình.
Hình 6: Sơ đồ thành phần cho Hệ thống hướng dẫn xe
• Thành phần GPS:
Thành phần này có một phương thức get_pos(out : src) với đặc tả
f{src}, true src = current_position,0 < l 1′ ≤⊢ . Mặc dù mã chương trình không
được trình bày ở đây nhưng ta giả định rằng mã chương trình không chứa bất kì lời gọi
nào đến một phương thức của thành phần khác. Thành phần khác duy nhất có thể sử
dụng thành phần này là Controller . Ở đây không chỉ rõ tài nguyên cụ thể được sử
dụng nhưng giả định rằng tiền điều kiện tài nguyên cho phương thức
get_pos(out : src) là true.
• Thành phần RouteDB:
Khai báo tài nguyên của thành phần này bao gồm bộ nhớ các biến tài nguyên
(khởi tạo 4 MB) và bộ xử lí 75 MHz (khởi tạo là 1). Thành phần có 2 phương thức:
_ ( : , , : )get map in src in : dstn out map với đặc tả là
31
{ , , }, _ _ _ ,0 1fsrc dstn map true map map for the area l′ = < ≤⊢
và _ ( : , : , : )find route in src in dstn out route với đặc tả là
{ , , },
_ _ ,
75 es 1 4
src dstn route true route
route to the_destination
MHz proc or memory n,0 l 11
′ =
= ∧ = < ≤
⊢
⊢
.
Thành phần khác duy nhất có thể sử dụng thành phần này là Controller . Đoạn
mã chương trình cho _ ( : , : , : )find route in src in dstn out route là
get_map(src,dstn,map);
compute(src,dstn,map,route);
Giả định rằng compute(src,dstn,map,route) cần 10 giây để một bộ xử
lí 75MHz sử dụng 4MB để thực hiện. Do đó đoạn mã này là một bản làm mịn đặc tả
của _ ( : , : , : )find route in src in dstn out route .
• Thành phần chủ động Controller :
Thành phần này có một biến cố _ _ _find route command arrival và một
phương thức _ _find route handle . Tài nguyên được khai báo của thành phần này là
biến 75 _MHz processor được khởi tạo là 1. Đoạn mã của phương thức này như sau:
: _ ;
( ( , ) || . _ os( ));
( ( , ) ||
. _ ( , , ));
_ ( );
dstn read dstn
Schedule Controller GPS GPS get p src
Schedule Controller RouteDB
RouteDB find route src dstn route
display route dstn
=
Đặc tả thời gian của phương thức này là 0 14l< ≤ . Giả định rằng mỗi một
: _dstn read dstn= và _ ( )display route dstn có thời gian tiêu dùng nhỏ hơn 1 với
dùng một bộ xử lí 75 MHz. Ta giả định rằng lệnh ( , )Schedule Controller RouteDB
và ( , )Schedule Controller RouteDB không tốn thời gian, nghĩa là l d= (ta không
thể giả định l = 0 vì giả định trước đó) là hậu điều kiện của chúng cho đặc tả có ràng
buộc thời gian (tiền điều kiện của chúng được đưa ra sau đó như là nất biến cho cả ba
thành phần). Với d là thời gian nhỏ nhất để thực hiện một lệnh. Nó được suy ra trực
tiếp từ luật thành phần liên tiếp và song song mà mã lệnh của phương thức này là bản
32
làm mịn của đặc tả của nó. Một luồng của thành phần này là
always _ _
after _ _ _
find route handle
find route command arrival .
Vậy trong mô hình này của hệ thống dựa trên thành phần ta có thể sử dụng UTP
và các luật bổ sung cho đặc tả thời gian thực cho các thiết kế để kiểm chứng nếu một
phương thức được cài đặt đúng hay không. Tuy nhiên, để mô hình này hỗ trợ chứng
thực thuộc tính phụ thuộc thời gian và theo thời gian thực. Ta phải đưa ra một nghĩa
hình thức cho các luồng và một đặc tả hình thức cho các thuộc tính thời gian thực.
33
KẾT LUẬN
Sau khi nghiên cứu các khái niệm về hệ thống dựa trên thành phần, mô hình
thành phần, các khái niệm về hệ thống dựa trên thành phần thời gian thực, tôi đã nắm
rõ được các khái niệm. Tôi đã trình bày về mô hình thành phần, kiến trúc của mô hình
thành phần. Với mô hình được trình bày ở trên thì nó có thể được mở rộng một cách dễ
dàng điều khiển các thuộc tính phi chức năng của thành phần như chất lượng dịch vụ.
Đặc tính chính của mô hình thành phần được trình bày ở trên nằm ở ngữ nghĩa hình
thức của nó trong UTP. Nó đóng vai rò như là một nền tẳng xho việc phát triển mẫu
ngôn nhữ cho lập trình dựa trên thành phần. Mẫu ngôn ngữ này được áp cho các ngôn
ngữ lập trình khác để thiết kế, lập trình dựa trên thành phẫn dễ dàng hơn. Cũng trong
mô hình đó, các thành phần được xác định tính đúng đắn bằng thiết kế. điều đó cũng
có nghĩa là cài đặt dịch vụ thỏa mãn các yêu cầu của nó. Điều đó được đẳm bảo chắc
chắn bằng cả kiểm chứng mô hình hoặc chứng minh định lý. Ngoài ra, tôi cũng trình
bày về mô hình thành phần thời gian thực. Mô hình này hỗ trợ đặ tả, làm mịn thành
phần và kiểm chứng một vài thuộc tính thời gian thực, điều mà mô hình trước không
có. Mô hình cũng hỗ trợ sự tách biệt giữa đặc tả chức năng từ đặc tả phi chức năng của
các thành phần, mà có thể đơn giản hóa kiểm chứng yêu cầu chức năng, và trong nhiều
rường hợp có thể đơn giản hóa cả các kiểm chứng yêu cầu phi chức năng nữa. Dựa
trên các kiến thức thu được tôi đã phân tích và trình bày một ví dụ về áp dụng mô hình
dựa trên thành phần. Việc nghiên cứu cá khái niệm, định nghĩa trong mô hình thành
phần và hệ thống dựa trên thành phần giúp cho thiết kế, phân tích và bảo trì các hệ
thống lớn một cách dễ dàng hơn.
TÀI LIỆU THAM KHẢO
[1] R. Alur and D.L. Dill. A Theory of Timed Automata. Theoretical Computer
Science, pages 183–235, 1994.
[2] E. Asarin, P. Caspi, and O. Maler. A Kleene Theorem for Timed Automata.
LICS’97, pages 160–171. IEEE computer Society Press, 1997.
[3] C.A.R. Hoare and He Jifeng. Unifying Theories of Programming. Prentice
Hall, 1998.
[4] Dang Van Hung. Toward a formal model for component interfaces for real-
time systems. In FMICS ’05,pages 106–114, New York, 2005. ACM Press.
[5] Dang Van Hung. Toward a Formal Model for Component Interfaces for Real-
time Systems. FMICS’05, September 5–6, 2005, Lisbon, Portugal.
[6] Pham Hong Thai, Dang Van Hung, Towards a Template Language for
Component-based Programming. WORLDCOMP’07 Conference, June 25-28, 2007,
USA.
[7] Hung Le Dang, Dang Van Hung. Timing and Concurrency Specification in
Component-based Real-Time Embedded Systems development. Proceedings of
TASE’07, June 6-8, 2007, Shanghai, China.
[8] Kurt Wallnau, Scott Hissam, and Robert Seacord, Component-Based
Software Engineering (series), 2000
[9] Ananda Basu, Marius Bozga, and Joseph Sifakis. Modeling Heterogeneous
Real-time Components in BIP. Proceedings of SEFM’06, pages 3–12, September
2006. IEEE Computer Society.
[10] He Jifeng, Zhiming Liu, and Xiaoshan Li. A Theories of Contracts.
Electronic Notes of Theoretical Computer Science, Volume 160 , pp. 173-195, 2006.
[11] Barbora Zimmerová, Component-Based Systems (CBSs) (slide bài giảng),
2005
Các file đính kèm theo tài liệu này:
- Nguyen Van Nghiep_K50CNPM_khoa luan tot nghiep dai hoc.pdf