Giáo trình Hệ thống nhúng (Phần 2)

43 trang phuongnguyen 4310

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Hệ thống nhúng (Phần 2)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_he_thong_nhung_phan_2.pdf

Nội dung text: Giáo trình Hệ thống nhúng (Phần 2)

Cơ bản về lập trình nhúng Biểu diễn số và dữ liệu • Đơn vị cơ bản nhất trong biểu diễn thông tin của hệ thống số được gọi là bit, chính là ký hiệu viết tắt của thuật ngữ binary digit. • Năm 1964, IBM đã thiết kế và chế tạo máy tính số sử dụng một nhóm 8 bit để đánh địa chỉ bộ nhớ và định nghĩa ra thuật ngữ 8 bit = 1 byte. • Ngày nay sử dụng rộng rãi thuật ngữ word là một từ dữ liệu dùng để biểu diễn kích thước dữ liệu mà được xử lý một cách hiệu quả nhất đối với mỗi loại kiến trúc xử lý số cụ thể. Chính vì vậy một từ có thể là 16 bits, 32 bits, hoặc 64 bits • Mỗi một byte có thể được chia ra thành hai nửa 4 bit và được gọi là các nibble. Nibble chứa các bit trọng số lớn được gọi là nibble bậc cao, và nibble chứa các bit trọng số nhỏ được gọi là nibble bậc thấp. Các hệ thống cơ số Trong các hệ thống biểu diễn số hiện nay đều được biểu diễn ở dạng tổng quát là tổng luỹ thừa theo cơ số, và được phân loại theo giá trị cơ số. Một cách tổng quát một hệ biểu diễn số cơ số b và a được biểu diễn như sau: n A=anbn+ an-1bn-1+ + a0 = ∑i = 0 ai∗bi Ví dụ: như cơ số binary (nhị phân), cơ số decimal (thập phân, cơ số 8 Octal (bát phân). Ví dụ về biểu diễn các giá trị trong các hệ cơ số khác nhau: • 243.5110 = 2 x 102 + 4 x 101 + 3 x 100 + 5 x 10-1 + 1 x 10-2 • 2123 = 2 x 32 + 1 x 31 + 2 x 30 • 101102 = 1 x 24 + 0 x 23 + 1 x 22 + 1 x 21 + 0 x 20 = 2210 Hai loại cơ số biểu diễn thông dụng nhất hiện nay cho các hệ thống xử lý số là cơ số nhị phân và cơ số mười sáu. Số nguyên Trong biểu diễn số có dấu để phân biệt số dương và số âm người ta sử dụng bit trọng số lớn nhất qui ước làm bit dấu và các bit còn lại được sử dụng để biểu diễn giá trị độ lớn của số. Ví dụ một từ 8 bit được sử dụng để biểu diễn giá trị -1 sẽ có dạng nhị phân là 10000001, và giá trị +1 sẽ có dạng 00000001. Như vậy với một từ 8 bit có thể biểu diễn 57/99
được các số trong phạm vi từ -127 đến +127. Một cách tổng quát một từ N bit sẽ biểu diễn được -2(N-1)-1 đến +2(N-1)-1. Chú ý khi thực hiện cộng hai số có dấu: • Nếu hai số cùng dấu thì thực hiện phép cộng phần biểu diễn giá trị và sử dụng bit dấu cùng dấu với hai số đó. • Nếu hai số khác dấu thì kết quả sẽ nhận dấu của toán tử lớn hơn, và thực hiện phép trừ giữa toán tử có giá trị lớn hơn với toán tử bé hơn. Ví dụ 1: Cộng hai số có dấu 010011112 và 001000112. 1 1 1 1 ⇐ carries (Số nhớ) 0 1 0 0 1 1 1 1 (79) 0 + 0 1 0 0 0 1 1 + (35) 0 1 1 1 0 0 1 0 (114) Ví dụ 2: Trừ hai số có dấu 010011112 và 011000112. 0 1 1 2 ⇐ borrows (số vay) 0 1 1 0 0 0 1 1 (99) 0 - 1 0 0 1 1 1 1 - (79) 0 0 0 1 0 1 0 0 (20) • Thuật toán thực hiện phép tính có dấu: • (1) Khai báo và xóa các biến lưu giá trị và dấu để chuẩn bị thực hiện phép tính. • (2) Kiểm tra dấu của toán tử thứ nhất để xem có phải số âm không. Nếu là số âm thì thực hiện bù dấu và bù toán tử. Nếu không thì chuyển qua thực hiện bước 3. • (3) Kiểm tra dấu của toán tử thứ hai để xem có phải số âm không. Nếu là số âm thì thực hiện bù dấu và bù toán tử. Nếu không thì chuyển sang thực hiện bước 4. • (4) Thực hiện phép nhân hoặc chia với các toán tử vừa xử lý. • (5) Kiểm tra dấu. Nếu zero thì coi như đã kết thúc. Nếu bằng -1 (0ffh) thì thực hiện phép tính bù hai với kết quả thu được và kết thúc. Hiện nay người ta sử dụng hai qui ước biểu diễn số nguyên phân biệt theo thứ tự của byte trọng số trong một từ được biểu diễn: 58/99
• Litte edian: byte trọng số nhỏ nhất đứng trước thuận lợi cho phép cộng hoặc trừ. • Big endian: byte trọng số lớn nhất đứng trước thuận lợi cho phép nhân hoặc chia. Ví dụ: xét một số nhị phân 4byte Byte 3 Byte 2 Byte 1 Byte 0 Theo qui ước biểu diễn litte edian thì thứ tự địa chỉ lưu trong bộ nhớ sẽ là: Địa chỉ cở sở + 0 = Byte 0 Địa chỉ cơ sở + 1 = Byte 1 Địa chỉ cơ sở + 2 = Byte 2 Địa chỉ cơ sở + 3 = Byte 3 Và theo qui ước biểu diễn số big edian sẽ là: Địa chỉ cở sở + 0 = Byte 3 Địa chỉ cơ sở + 1 = Byte 2 Địa chỉ cơ sở + 2 = Byte 1 Địa chỉ cơ sở + 3 = Byte 0 Số dấu phẩy tĩnh Chúng ta có thể sử dụng một ký hiệu dấu chấm ảo để biểu diễn một số thực. Dấu chấm ảo được sử dụng trong từ dữ liệu dùng để phân biệt và ngăn cách giữa phần biểu diễn giá trị nguyên của dữ liệu và một phần lẻ thập phân. Ví dụ về một từ 8bit biểu diễn số dấu phảy động được chỉ ra như trong Hình 6.1. Với cách biểu diễn này, giá trị thực của số được tính như sau: N = a4 24 + a3 23 + a2 22 + a1 21 + a0 20 + a−1 2−1 + a−2 2−2 + a−3 2−3 = 0.24+1.23+0.22+1.21+0.20+1.2-1+0.2-2+1.2-3 = 8+2+1+1/2+1/8 = 11.625 59/99
Định dạng biểu diễn số dấu phảy tĩnh 8 bit Nhược điểm của phương pháp biểu diễn số dấu phảy tĩnh là vùng biểu diễn số nguyên bị hạn chế bởi dấu phảy tĩnh được gán cố định. Điều này dễ xảy ra hiện tượng tràn số khi thực hiện các phép nhân hai số lớn. Số dấu phẩy động Phương pháp biểu diễn số chính xác và linh hoạt được sử dụng rộng rãi hiện nay là hệ thống biểu diễn số dấu phảy động. Đây cũng là một phương pháp biểu diễn số khoa học bao gồm 2 phần: phần biểu diễn lưu trữ số mantissa và một phần lưu trữ biểu diễn số exponent. Ví dụ trong hệ cơ số thập phân, một số nguyên bằng 5 có thể được biểu diễn hoặc là 0.5*101 , 50 * 10−1 , hoặc 0.05*102 Trong máy tính số hoặc hệ thống số nói chung, các số dấu phảy động nhị phân thường được biểu diễn dạng: N = M * 2E Trong đó: • M là phần giá trị số mantissa, • E là phần lũy thừa của số N. M thường là các giá trị lẻ mà phần thập phân của nó thường nằm trong khoảng 0.5 ≤ M ≤ 1. Hình 6.2 mô tả biểu diễn một số dấu phảy động của từ 8 bit gồm 5 bit biểu diễn phần số có nghĩa mantissa, và 3 bit biểu diễn phần lũy thừa. Vì các phần mantissa và lũy thừa đều có thể nhận các giá trị âm vì vậy các bit đầu tiên của các phần giá trị đó đều có thể được sử dụng để biểu diễn dấu khi cần thiết. Biểu diễn dấu phảy động 8bit 60/99
Trong một số VXL, VĐK do độ rộng từ nhị phân nhỏ nên có thể sử dụng 2 từ để biểu diễn một số dấu phảy động. Một từ sẽ dùng để biểu diễn giá trị mantissa, và một phần biểu diễn giá trị exponent. Nếu phần mantissa được chuẩn hóa thành một số lẻ có giá trị trong khoảng 0.5 ≤ M ≤ 1 thì bit đầu tiên sau bit dấu thường là một và sẽ có một dấu phảy nhị phân ẩn ngay sau bit dấu. Phần biểu diễn exponent E sẽ quyết định vị trí của dấu phảy động sẽ dịch sang trái (E>0) hay sang phải (E<0) bao nhiêu vị trí. Ví dụ biểu diễn một số thập phân 6.5 bằng một từ 8 bit dấu phảy động như sau: N = .1101 * 2 11(2) = (1/2+1/4+1/16)*2 3 = 6.5 Trong trường hợp này phần mantissa gồm 4 bit và phần exponent gồm 3 bit. Nếu ta dịch dấu phảy sang phải 3 vị trí bit thì chúng ta sẽ có một số nhị phân dấu phảy động biểu diễn được sẽ là 110.1. Tổng quát hóa trong trường hợp một số nhị phân dấu phảy động n bit gồm m bit biểu diễn phần mantissa và e bit biểu diễn phần exponent thì giá trị của số lớn nhất có thể biểu diễn được sẽ là: − m + 1 (2e − 1 − 1) Nmax = (1 − 2 )2 Và số dương nhỏ nhất có thể biểu diễn là: − (2e − 1 − 1) Nmin = 0.5 ∗ 2 Theo tiêu chuẩn IEEE 754 và 854 có 2 định dạng chính cho số dấu phảy động là số thực dài (long) và số thực ngắn (short) chúng khác nhau về dải biểu diễn và độ lớn lưu trữ yêu cầu. Theo chuẩn này, số thực dài được định dạng 8 byte bao gồm 1 bit dấu, 11 bit exponent và 53 bit lưu giá trị số có nghĩa. Một số thực ngắn được định dạng 4 byte bao gồm 1 bit dấu, 8 bit lũy thừa và 24 bit lưu giá trị số có nghĩa. Một số thực ngắn có thể biểu diễn và xử lý được số có giá trị nằm trong dải 1038 to 10-38 và số thực dài có thể biểu diễn và xử lý được số có giá trị thuộc dải 10308 to 10-308 . Để biểu diễn một giá trị tương đương như vậy bằng số dấu phảy tĩnh thì cần tới 256 bit hay 32 byte dữ liệu. Ngôn ngữ lập trình Một trong những ngôn ngữ lập trình có lẽ phổ cập rộng rãi nhất hiện nay là ngôn ngữ C. So với bất kỳ ngôn ngữ lập trình nào khác đang tồn tại C thực sự phù hợp và trở thành một ngôn ngữ phát triển của hệ nhúng. Điều này không phải là cố hữu và sẽ tồn tại mãi, nhưng tại thời điểm này thì C có lẽ là một ngôn ngữ gần gũi nhất để trở thành một chuẩn 61/99
ngôn ngữ trong thế giới hệ nhúng. Trong phần này chúng ta sẽ cùng tìm hiểu tại sao C lại trở thành một ngôn ngữ phổ biến đến vậy và tại sao chúng ta lựa chọn nó như một ngôn ngữ minh họa cho việc lập trình hệ nhúng. Sự thành công về phát triển phần mềm thường là nhờ vào sự lựa chọn ngôn ngữ phù hợp nhất cho một dự án đặt ra. Cần phải tìm một ngôn ngữ để có thể đáp ứng được yêu cầu lập trình cho các bộ xử lý từ 8bit đến 64bit, trong các hệ thống chỉ có hữu hạn về bộ nhớ vài Kbyte hoặc Mbyte. Cho tới nay, điều này chỉ có C là thực sự có thể thỏa mãn và phù hợp nhất. Rõ ràng C có một số ưu điểm nổi bật tiêu biểu như khá nhỏ và dễ dàng cho việc học, các chương trình biên dịch thường khá sẵn cho hầu hết các bộ xử lý đang sử dụng hiện nay, và có rất nhiều người đã biết và làm chủ được ngôn ngữ này rồi, hay nói cách khác cũng đã được phổ cập từ lâu. Hơn nữa C có lợi thế là không phụ thuộc vào bộ xử lý thực thi mã nguồn. Người lập trình chỉ phải tập trung chủ yếu vào việc xây dựng thuật toán, ứng dụng và thể hiện bằng ngôn ngữ thân thiện thay vì phải tìm hiểu sâu về kiến thức phần cứng, cũng như rất nhiều các ưu điểm nổi bật khác của ngôn ngữ bậc cao nói chung. Có lẽ một thế mạnh lớn nhất của C là một ngôn ngữ bậc cao mức thấp nhất. Tức là với ngôn ngữ C chúng ta vẫn có thể điều khiển và truy nhập trực tiếp phần cứng khá thuận tiện mà không hề phải hy sinh hay đánh đổi bất kỳ một thế mạnh nào của ngôn ngữ bậc cao. Thực chất đây cũng là một trong những tiêu chí xây dựng của những người sáng lập ra ngôn ngữ C muốn hướng tới. Thực tế điều này đã được đề cập đến khi hai nhà sáng lập ra ngôn ngữ C, KernighanvàRitchie đã đưa vào trong phần giới thiệu của cuốn sách của họ “The C Programming Language” như sau: “C is a relatively “low level” language. This characterization is not pejorative; it simply means that C deals with the same sort of objects that most computers do. These may be combined and moved about with the arithmetic and logical operators implemented by real machines ” Tất nhiên là C không phải là ngôn ngữ duy nhất cho các nhà lập trình nhúng. Ít nhất hiện nay người ta cũng có thể biết tới ngoài ngôn ngữ C là Assembly, C++, và Ada. Trong những buổi đầu phát triển hệ nhúng thì ngôn ngữ Assembly chủ yếu được sử dụng cho các vi xử lý đích. Với ngôn ngữ này cho phép người lập trình điều khiển và kiểm soát hoàn toàn vi xử lý cũng như phần cứng hệ thống trong việc thực thi chương trình. Tuy nhiên ngôn ngữ Assembly có nhiều nhược điểm mà cũng chính là lý do tại sao hiện nay nó ít được phổ cập và sử dụng. Đó là, việc học và sử dụng ngôn ngữ Assembly rất khó khăn và đặc biệt khó khăn trong việc phát triển các chương trình ứng dụng lớn phức tạp. Hiện nay nó chỉ được sử dụng chủ yếu như điểm nối giữa ngôn ngữ bậc cao và bậc thấp và được sử dụng khi có yêu cầu đặc biệt về hiệu suất thực hiện và tối ưu về tốc độ mà không thể đạt được bằng ngôn ngữ khác. Ngôn ngữ Assembly chỉ thực sự phù hợp cho những người có kinh nghiệm và hiểu biết tốt về cấu trúc phần cứng đích cũng như nguyên lý thực hiện của bộ lệnh và chíp xử lý. 62/99
C++ là một ngôn ngữ kế thừa từ C để nhằm vào các lớp ứng dụng và tư duy lập trình hướng đối tượng và cũng bắt đầu chiếm được số lượng lớn quan tâm trong việc ứng dụng cho phát triển hệ nhúng. Tất cả các đặc điểm cốt lõi của C vẫn được kế thừa hoàn toàn trong ngôn ngữ C++ và ngoài ra còn hỗ trợ khả năng mới về trừu tượng hóa dữ liệu và phù hợp với tư duy lập trình hiện đại; hướng đối tượng. Tuy nhiên điều này bị đánh đổi bởi hiệu suất và thời gian thực thi do đó chỉ phù hợp với các dự án phát triển chương trình lớn và không chịu sức ép lớn về thời gian thực thi. Ada cũng là một ngôn ngữ hướng đối tượng mặc dù nó không được phổ cập rộng rãi như C++. Ada được xây dựng bởi cơ quan quốc phòng Mỹ để phục vụ phát triển các phần mềm quân sự chuyên dụng đặc biệt. Mặc dù cũng đã được chuẩn hóa quốc tế (Ada83 và Ada95) nhưng nó vẫn không được phổ cập rộng rãi ngoài việc ứng dụng chủ yếu trong các lĩnh vực quân sự và hàng không vũ trụ. Và nó cũng dần dần bị mất ưu thế và sự phổ cập trong thời gian gần đây, đây cũng là một điều đáng tiếc vì bản thân Ada cũng là một ngôn ngữ có nhiều đặc điểm phù hợp cho việc phát triển phần mềm hệ nhúng thay vì phải sử dụng C++. Các kiến trúc phần mềm nhúng thông dụng Hiện nay tồn tại một số loại kiến trúc phần mềm thông dụng trong các hệ thống nhúng như sau: Vòng lặp kiểm soát đơn giản Theo thiết kế này, phần mềm được tổ chức thành một vòng lặp đơn giản. Vòng lặp gọi đến các chương trình con, mỗi chương trình con quản lý một phần của hệ thống phần cứng hoặc phần mềm. Hệ thống ngắt điều khiển Các hệ thống nhúng thường được điểu khiển bằng các ngắt. Có nghĩa là các tác vụ của hệ thống nhúng được kích hoạt bởi các loại sự kiện khác nhau. Ví dụ, một ngắt có thể được sinh ra bởi một bộ định thời sau một chu kỳ được định nghĩa trước, hoặc bởi sự kiện khi cổng nối tiếp nhận được một byte nào đó. Loại kiến trúc này thường được sử dụng trong các hệ thống có bộ quản lý sự kiện đơn giản, ngắn gọn và cần độ trễ thấp. Hệ thống này thường thực hiện một tác vụ đơn giản trong một vòng lặp chính. Đôi khi, các tác vụ phức tạp hơn sẽ được thêm vào một cấu trúc hàng đợi trong bộ quản lý ngắt để được vòng lặp xử lý sau đó. Lúc này, hệ thống gần giống với kiểu nhân đa nhiệm với các tiến trình rời rạc. 63/99
Đa nhiệm tương tác Một hệ thống đa nhiệm không ưu tiên cũng gần giống với kỹ thuật vòng lặp kiểm soát đơn giản ngoại trừ việc vòng lặp này được ẩn giấu thông qua một giao diện lập trình API. Các nhà lập trình định nghĩa một loạt các nhiệm vụ, mỗi nhiệm vụ chạy trong một môi trường riêng của nó. Khi không cần thực hiện nhiệm vụ đó thì nó gọi đến các tiến trình con tạm nghỉ (bằng cách gọi “pause”, “wait”, “yeild” ). Ưu điểm và nhược điểm của loại kiến trúc này cũng giống với kiểm vòng lặp kiểm soát đơn giản. Tuy nhiên, việc thêm một phần mềm mới được thực hiện dễ dàng hơn bằng cách lập trình một tác vụ mới hoặc thêm vào hàng đợi thông dịch (queue-interpreter). Đa nhiệm ưu tiên Ở loại kiến trúc này, hệ thống thường có một đoạn mã ở mức thấp thực hiện việc chuyển đổi giữa các tác vụ khác nhau thông qua một bộ định thời. Đoạn mã này thường nằm ở mức mà hệ thống được coi là có một hệ điều hành và vì thế cũng gặp phải tất cả những phức tạp trong việc quản lý đa nhiệm. Bất kỳ tác vụ nào có thể phá hủy dữ liệu của một tác vụ khác đều cần phải được tách biệt một cách chính xác. Việc truy cập tới các dữ liệu chia sẻ có thể được quản lý bằng một số kỹ thuật đồng bộ hóa như hàng đợi thông điệp (message queues), semaphores Vì những phức tạp nói trên nên một giải pháp thường được đưa ra đó là sử dụng một hệ điều hành thời gian thực. Lúc đó, các nhà lập trình có thể tập trung vào việc phát triển các chức năng của thiết bị chứ không cần quan tâm đến các dịch vụ của hệ điều hành nữa. Vi nhân (Microkernel) và nhân ngoại (Exokernel) Khái niệm vi nhân (microkernel) là một bước tiếp cận gần hơn tới khái niệm hệ điều hành thời gian thực. Lúc này, nhân hệ điều hành thực hiện việc cấp phát bộ nhớ và chuyển CPU cho các luồng thực thi. Còn các tiến trình người dùng sử dụng các chức năng chính như hệ thống file, giao diện mạng lưới, Nói chung, kiến trúc này thường được áp dụng trong các hệ thống mà việc chuyển đổi và giao tiếp giữa các tác vụ là nhanh. Còn nhân ngoại (exokernel) tiến hành giao tiếp hiệu quả bằng cách sử dụng các lời gọi chương trình con thông thường. Phần cứng và toàn bộ phần mềm trong hệ thống luôn đáp ứng và có thể được mở rộng bởi các ứng dụng. 64/99
Nhân khối (monolithic kernels) Trong kiến trúc này, một nhân đầy đủ với các khả năng phức tạp được chuyển đổi để phù hợp với môi trường nhúng. Điều này giúp các nhà lập trình có được một môi trường giống với hệ điều hành trong các máy để bàn như Linux hay Microsoft Windows và vì thế rất thuận lợi cho việc phát triển. Tuy nhiên, nó lại đòi hỏi đáng kể các tài nguyên phần cứng làm tăng chi phí của hệ thống. Một số loại nhân khối thông dụng là Embedded Linux và Windows CE. Mặc dù chi phí phần cứng tăng lên nhưng loại hệ thống nhúng này đang tăng trưởng rất mạnh, đặc biệt là trong các thiết bị nhúng mạnh như Wireless router hoặc hệ thống định vị GPS. Lý do của điều này là: • Hệ thống này có cổng để kết nối đến các chip nhúng thông dụng. • Hệ thống cho phép sử dụng lại các đoạn mã sẵn có phổ biến như các trình điều khiển thiết bị, Web Servers, Firewalls, • Việc phát triển hệ thống có thể được tiến hành với một tập nhiều loại đặc tính, chức năng còn sau đó lúc phân phối sản phẩm, hệ thống có thể được cấu hình để loại bỏ một số chức năng không cần thiết. Điều này giúp tiết kiệm được những vùng nhớ mà các chức năng đó chiếm giữ. • Hệ thống có chế độ người dùng để dễ dàng chạy các ứng dụng và gỡ rối. Nhờ đó, qui trình phát triển được thực hiện dễ dàng hơn và việc lập trình có tính linh động hơn. • Có nhiều hệ thống nhúng thiếu các yêu cầu chặt chẽ về tính thời gian thực của hệ thống quản lý. Còn một hệ thống như Embedded Linux có tốc độ đủ nhanh để trả lời cho nhiều ứng dụng. Các chức năng cần đến sự phản ứng nhanh cũng có thể được đặt vào phần cứng. Tập lệnh Cấu trúc tập lệnh CISC và RISC Hầu hết các vi điều khiển và VXL nhúng có cấu trúc được phát triển dựa theo kiến trúc máy tính tập lệnh phức hợp CISC (Complex Instruction Set Computer). CISC là một cấu trúc xử lý các lệnh phức hợp, tức là một lệnh phức hợp sẽ bao gồm một vài lệnh đơn. Theo nguyên lý này có thể giảm bớt được thời gian dùng để truy nhập và đọc mã chương trình từ bộ nhớ. Điều này rất có ý nghĩa với các kiến trúc thiết kế xử lý tính toán theo kiểu tuần tự. Lý do cho sự ra đời của tập lệnh phức hợp nhằm giảm thiểu dung lượng bộ nhớ cần thiết để lưu giữ chương trình thực hiện, và sẽ giảm được giá thành về bộ nhớ cần cung cấp cho CPU. Các lệnh càng gọn và phức hợp thì sẽ cần càng ít không gian bộ nhớ chương trình. Kiến trúc tập lệnh phức hợp sử dụng các lệnh với độ dài biến đổi tuỳ thuộc vào độ phức hợp của các lệnh từ đơn giản đến phức tạp. Trong đó sẽ có một số lượng lớn các lệnh có thể truy nhập trực tiếp bộ nhớ. Vì vậy với kiến trúc tập lệnh phức hợp chúng ta sẽ có được một tập lệnh đa dạng phức hợp, gọn, với độ dài lệnh thay đổi và dẫn đến chu kỳ thực hiện lệnh cũng thay đổi tuỳ theo độ phức hợp trong từng lệnh. 65/99
Một vài lệnh phức hợp, đặc biệt là các lệnh truy nhập bộ nhớ cần tới vài chục chu kỳ để thực hiện. Trong một số trường hợp các nhà thiết kế VXL thấy rằng cần phải giảm chu kỳ nhịp lệnh để có đủ thời gian cho các lệnh hoàn thành điều này cũng dẫn đến thời gian thực hiện bị kéo dài hơn. Một số VĐK được phát triển theo kiến trúc máy tính tập lệnh rút gọn RISC (Reduced Instruction Set Computer). RISC phù hợp với các thiết kế kiến trúc xử lý các lệnh đơn. Thuật ngữ “rút gọn” (reduced) đôi khi bị hiểu không thật chính xác theo nghĩa đen của nó thực chất ý tưởng gốc xuất phát từ khả năng cung cấp một tập lệnh tối thiểu để thực hiện tất cả các hoạt động chính như: chuyển dữ liệu, các hoạt động ALU và rẽ nhánh điều khiển chương trình. Chỉ có các lệnh nạp (load), lữu trữ (store) là được phép truy nhập trực tiếp bộ nhớ. So sánh đặc điểm của CISC và RISC Các kiểu truyền địa chỉ toán tử lệnh Các kiểu đánh/truyền địa chỉ cho phép chúng ta chỉ ra/truyền toán tử tham gia trong các lệnh thực thi. Kiểu địa chỉ có thể chỉ ra là một hằng số, một thanh ghi hoặc một khu vực cụ thể trong bộ nhớ. Một số kiểu đánh địa chỉ cho phép sử dụng địa chỉ ngắn và một số loại thì cho phép chúng ta xác định khu vực chứa toán tử lệnh, và thường được gọi là địa chỉ hiệu dụng của toán tử và thường là động. Chúng ta sẽ xét một số loại hình đánh địa chỉ cơ bản hiện đang được sử dụng rộng rãi trong cơ chế thực hiện lệnh. • Đánh địa chỉ tức thì (Immediate Addressing): Phương pháp này cho phép truyền giá trị toán tử lệnh một cách tức thì như một phần của câu lệnh được thực thi. Ví dụ nếu sử dụng kiểu đánh địa chỉ tức thời cho câu lệnh Load 0x0008 thì giá trị 0x0008 sẽ được nạp ngay vào AC. Trường bit thường dùng để chứa toán tử lệnh sẽ chứa giá trị thực của toán tử chứ không phải địa chỉ của toán tử cần truyền cho lệnh thực thi. Kiểu địa chỉ tức thời cho phép thực thi 66/99
lệnh rất nhanh vì không phải thực hiện truy xuất bộ nhớ để nạp giá trị toán tử mà giá trị toán tử đã được gộp như một phần trong câu lệnh và có thể thực thi ngay. Vì toán tử tham gia như một phần cố định của chương trình vì vậy kiểu đánh địa chỉ này chỉ phù hợp với các toán tử hằng và biết trước tại thời điểm thực hiện chương trình, hay đã xác định tại thời điểm biên dịch chương trình. • Đánh địa chỉ trực tiếp (Direct Addressing):Phương pháp này cho phép truyền toán tử lệnh thông qua địa chỉ trực tiếp chứa toán tử đó trong bộ nhớ. Ví dụ nếu sử dụng cơ chế đánh địa chỉ toán tử trực tiếp thì trong câu lệnh Load 0x0008 sẽ được hiểu là dữ liệu hay toán tử được nạp trong câu lệnh này nằm trong bộ nhớ tại địa chỉ 0x0008. Cơ chế đánh địa chỉ trực tiếp cũng thuộc loại hình khá nhanh mặc dù không nhanh được như cơ chế truyền địa chỉ tức thời nhưng độ mềm dẻo cao hơn vì địa chỉ của toán tử không nằm trong phần mã lệnh và giá trị có thể thay đổi trong quá trình thực thi chương trình. • Đánh địa chỉ thanh ghi (Register Addressing): Trong cách đánh địa chỉ và truyền toán tử này thì toán tử không nằm trong bộ nhớ như trường hợp đánh địa chỉ trực tiếp mà nằm tại chính trong thanh ghi. Khi toán tử đã được nạp vào thanh ghi thì việc thực hiện có thể rất nhanh vì tốc độ truy xuất thanh ghi nhanh hơn so với bộ nhớ. Nhưng số lượng thanh ghi chỉ có hạn và phải được chia sẻ trong quá trình thực hiện chương trình vì vậy các toán tử phải được nạp vào thanh ghi trước khi nó được thực thi. • Đánh địa chỉ gián tiếp (Indirect Addressing): Trong phương pháp truyền toán tử này, trường toán tử trong câu lệnh được sử dụng để tham chiếu tới một con trỏ nằm trong bộ nhớ để trỏ tới địa chỉ hiệu dụng của toán tử. Cơ chế truyền này có thể nói là mềm dẻo nhất so với các cơ chế truyền địa chỉ khác trong quá trình thực thi chương trình. Ví dụ nếu áp dụng cơ chế truyền địa chỉ gián tiếp trong câu lệnh Load 0x0008 thì sẽ được hiểu là giá trị dữ liệu có địa chỉ tại 0x0008 thực chất là chứa địa chỉ hiệu dụng của toán tử cần truyền cho câu lệnh. Giả thiết tại vị trí ô nhớ 0x0008 đang chứa giá trị 0x02A0 thì 0x02A0 chính là giá trị thực của toán tử sẽ được nạp vào AC. Một biến thể khác cũng có thể thực hiện theo cơ chế này là truyền tham chiếu tới con trỏ nằm trong khu vực thanh ghi. Cơ chế này còn được biết tới với tên gọi là đánh địa chỉ gián tiếp thanh ghi. Ví dụ một câu lệnh Load R1 sử dụng cơ chế truyền địa chỉ gián tiếp thanh ghi thì chúng ta có thể dễ dàng thông dịch được toán tử truyền trong câu lệnh này có địa chỉ hiệu dụng nằm trong thanh ghi R1. • Cách đánh địa chỉ cơ sở và chỉ số (Indexed and Based Addressing): Trong cơ chế này người ta sử dụng một thanh ghi để chứa offset (độ chênh lệch tương đối) mà sẽ được cộng với toán tử để tạo ra một địa chỉ hiệu dụng. Ví dụ, nếu toán tử X của lệnh Load X được đánh địa chỉ theo cơ chế địa chỉ chỉ số và thanh ghi R1 là thanh ghi chứa chỉ số và có giá trị là 1 thì địa chỉ hiệu dụng của toán tử thực chất sẽ là X+1. Cơ chế đánh địa chỉ cơ sở cũng giống như vậy ngoại trừ một điều là thay vì sử dụng thanh ghi địa chỉ offset thì ở đây sử dụng thanh ghi địa chỉ cơ sở. Về mặt lý thuyết sự khác nhau giữa hai cơ chế tham chiếu địa chỉ này là chúng được sử dụng thế nào chứ không phải các toán tử 67/99
được tính toán thể nào. Một thanh ghi chỉ số sẽ lưu chỉ số mà sẽ được sử dụng như một offset so với địa chỉ được đưa ra trong trường địa chỉ của lệnh thực thi. Thanh ghi cơ sở lưu một địa chỉ cơ sở và trường địa chỉ trong câu lệnh thực thi sẽ lưu giá trị dịch chuyển từ địa chỉ này. Hai cơ chế tham chiếu địa chỉ này rất hữu ích trong việc truy xuất với các phần tử kiểu mảng. Tuỳ thuộc vào thiết kế tập lệnh các thanh ghi mục đích chung thường hay được sử dụng trong cơ chế đánh địa chỉ này. • Đánh địa chỉ ngăn xếp (Stack Addressing): Trong cơ chế truyền địa chỉ này thì toán tử nhận được từ đỉnh ngăn xếp. Thay vì sử dụng thanh ghi mục đích chung hay ô nhớ kiến trúc dựa trên ngăn xếp lưu các toán tử trên đỉnh của ngăn xếp, và có thể truy xuất với CPU. Kiến trúc này không chỉ hiệu quả trong việc lưu giữ các giá trị trung gian trong các phép tính phức tạp mà còn cung cấp một phương pháp hiệu quả trong việc truyền các tham số trong các lời gọi hàm cũng như để lưu cất các cấu trúc dữ liệu cục bộ và định nghĩa ra phạm vi tồn tại của các biến và các hàm con. Trong các cấu trúc lệnh truyền toán tử dựa trên ngăn xếp, hầu hết các lệnh chỉ bao gồm phần mã, tuy nhiên cũng có một số lệnh đặc biệt chỉ có một toán tử ví dụ như lệnh cất vào (push) hoặc lấy ra (pop) từ ngăn xếp. Chỉ có một số lệnh yêu cầu hai toán tử thì hai giá trị chứa trong 2 ô nhớ trên đỉnh ngăn xếp sẽ được sử dụng. Ví dụ như lệnh Add, CPU lấy ra khỏi ngăn xếp hai phần tử nằm trên đỉnh rồi thực hiện phép cộng và sau đó lưu kết quả trở lại đỉnh ngăn xếp. • Các cách đánh địa chỉ khác: Có rất nhiều biến có thể tạo bởi các cơ chế đánh địa chỉ giới thiệu ở trên. Đó là sự tổ hợp trong việc tạo ra hoặc xác định địa chỉ hiệu dụng của toán tử truyền cho lệnh thực thi. Ví dụ như cơ chế đánh địa chỉ chỉ số gián tiếp sử dụng đồng thời cả hai cơ chế đánh địa chỉ đồng thời, tương tự như vậy cũng có cơ chế đánh địa chỉ cơ sở/offset Cũng có một số cơ chế tự động tăng hoặc giảm thanh ghi sử dụng trong lệnh đang thực thi nhờ vậy mà có thể giảm được độ lớn của mã chương trình đặc biệt phù hợp cho các ứng dụng Nhúng. 68/99
Tác vụ và truyền thông giữa các tác vụ Các tác vụ (Task) Một hệ thống thời gian thực được gọi là “điều khiển sự kiện” có nghĩa là hệ thống đó phải có chức năng chính là phản ứng lại các sự kiện xảy ra trong môi trường của hệ thống. Vậy thì hệ thống phản ứng lại các sự kiện như thế nào? Một giải pháp đưa ra có tên Đa nhiệm. Giải pháp này đã được chứng minh là một mô hình chuẩn cho các hệ thống điều khiển sự kiện và hệ thống sử dụng ngắt. Ý tưởng cơ bản của giải pháp này là chúng ta có thể phân chia một vấn đề lớn thành các nhánh nhỏ và đơn giản hơn để giải quyết. Mỗi một vấn đề con (sub-problem) trở thành một tác vụ - task. Mỗi một tác vụ chỉ làm một việc đơn giản. Sau đó, chúng ta giả thiết rằng các tác vụ này chạy song song với nhau. Trên thực tế, các tác vụ không bao giờ chạy song song nếu chúng ta không có một hệ thống đa vi xử lý. Trong trường hợp đang xét, các tác vụ sẽ chia sẻ một bộ vi xử lý. Cũng giống như các chương trình khác, một tác vụ bao gồm mã lệnh để thực hiện các chức năng tác vụ phải thực hiện (do người lập trình đã thiết kế). Mã lệnh được chứa trong một hàm tương tự như hàm main() trong ngôn ngữ lập trình C. Điều làm nên sự khác biệt của tác vụ chính là ngữ cảnh (context) chứa trong ngăn xếp (stack) của nó. Task là gì? Mỗi một tác vụ bao gồm : • Mã nguồn chứa các chức năng của tác vụ. • Một ngăn xếp để chứa ngữ cảnh của tác vụ. • Một hộp thư (mail box) (tùy chọn) để phục vụ cho việc truyền thông với các tác vụ khác. Chú ý rằng, đôi khi (nhiều khi khá hữu dụng) ta có thể tạo ra nhiều tác vụ từ một hàm chung. Như đã nói, điều làm cho một tác vụ có thể tách biệt và khác biệt với các tác vụ 69/99
khác chính là ngăn xếp của nó. Thực tế đây chính là lập trình hướng đối tượng kiểu cổ điển. Ta có thể nghĩ rằng hàm tác vụ chính là việc định nghĩa một class. Và một tác vụ tạo ra từ hàm đó chính là một ví dụ về class. Mặc dù có thể thấy các tác vụ là khá độc lập, nhưng về cơ bản thì chúng cũng cần phải hợp tác với nhau để thực hiện một mục đích chung đã được thiết kế sẵn cho hệ thống. Vì vậy, mỗi một tác vụ cần phải có một cơ chế truyền thông mà thông qua đó, chúng có thể kết nối, đồng bộ với các tác vụ khác. Trong trường hợp này, ta gọi cơ chế đó là Hộp thư – mail box. Hình 7.2 miêu tả cấu trúc mã nguồn của một tác vụ. Đối số data dùng để tham số hóa một tác vụ. Vai trò của nó cũng giống với các đối số argv và argc trong hàm main() với ngôn ngữ C. Đối số này thực sự quan trọng trong trường hợp nhiều tác vụ cùng được tạo ra từ một hàm. Sự duy nhất của tác vụ được thể hiện bởi giá trị của đối số này. Cấu trúc thông thường của một tác vụ Một tác vụ có thể được khởi động với một vài khởi tạo (có thể bao gồm khởi tạo đối số data). Sau đó, thông thường, tác vụ sẽ đi vào một vòng lặp không giới hạn. Tại một vài điểm trong vòng lặp, nó sẽ đợi "Một sự kiện nào đó xảy ra", có thể, sự kiện đó là một bản tin được gửi tới mail box, hoặc đơn giản là tràn bộ định thời. Trong khi chờ sự kiện, tác vụ sẽ không làm gì cả và không sử dụng bộ vi xử lý. Một vài tác vụ khác nếu đã sẵn sàng hoạt động hoặc đang hoạt động sẽ xử dụng bộ vi xử lý. Khi sự kiện mà tác vụ đang chờ xảy ra, tác vụ sẽ "thức dậy" và: nhận lấy bản tin, giải mã bản tin và hoạt động theo các yêu cầu đặt sẵn dựa trên một hệ thống các yêu cầu được phân định bởi câu lệnh switch(). Sau khi thực hiện xong yêu cầu, tác vụ lại quay trở lại trạng thái chờ sự kiện. Có thể thấy rằng, tất cả các tá vụ đều giành phần lớn thời gian cho việc chờ một sự kiện nào đó xảy ra. Đây cũng chính là lí do để đa nhiệm hoạt động. 70/99
Truyền thông và đồng bộ giữa các tác vụ Mặc dù các tác vu ̣ được xem như độc lập với nhau nhưng nhiệm vu ̣ tổng quát của hệ thống yêu cầu các tác vu ̣phải có sự liên hê ̣ với nhau, hợp tác với nhau. Do đó, thành phần cốt yếu của bất cứ hệ điều hành thời gian thực là tập hợp các dịch vụ truyền thông và đồng bộ. Có một vài cơ chế đồng bộ và truyền thông hay được sử dụng, bao gồm: • Semaphore: Sử dụng cho việc đồng bộ hóa tín hiệu và khả năng tận dụng tài nguyên. • Monitor: Điều khiển việc truy cập vào vùng dữ liệu chia sẻ trong hoạt động của hệ thống. Semaphore Hãy xét 2 tác vụ, mỗi tác vu ̣ có nhiệm vụ in một bản tin có nội dung “I am task n” (n là số thứ tự của tác vụ) bằng một máy in chia sẻ như trong hình dưới. Nếu chúng ta không sử dụng bấ t cứ một cơ chế đồng bộ nào, kết quả có được từ máy in sẽ có thể là “II a amm tatasskk 12”. chia sẻ tài nguyên Điều cần thiết ở đây là phải có một cơ chế nào đó để với cơ chế này, máy in chỉ có thể được sử dụng bởi 1 tác vụ tại một thời điểm xác định. Semaphore hoạt động giống như một chiếc chìa khóa cho việc truy cập tới tài nguyên. Chỉ có tác vụ có chìa khóa này mới có quyền sử dụng tài nguyên. Để có thể sử dụng tài nguyên (là chiếc máy in trong trường hợp này), tác vu ̣ cần yêu cầu (acquire) chìa khóa (semaphore) bằng cách gọi tới một dịch vụ thích hợp như trong hình 7.4. Nếu chìa khóa ở trạng thái sẵn sàng, tức̀ là tài nguyên (máy in) hiện tại không được sử dụng bởi bất kỳ một tác vụ nào, tác vụ đó có thể được cho phép sử dụng tài nguyên. Sau khi sử dụng xong, tác vụ đó phải trả lại (release) semaphore cho các tác vụ khác có thể sử dụng. 71/99
Chia sẻ tài nguyên với Semaphone Tuy nhiên, nếu máy in đang được sử dụng, tác vụ đó sẽ bị khóa cho tới khi tác vụ đang sử dụng máy in trả lại semaphore. Cùng một lúc có thể có nhiều tác vụ yêu cầu semaphore trong khi máy in đang hoạt động. Tất cả các tác vụ đó đều sẽ bị khóa. Các tác vụ bị khóa sẽ được xếp hàng theo kiểu hàng đợi theo thứ tự về mặt ưu tiên hoặc theo thứ tự thời gian mà chúng yêu cầu semaphore theo lệnh acquireSem. Cách thức sắp xếp thứ tự hàng đợi cho các tác vụ có thể được xây dựng trong kernel hoặc cũng có thể được cấu hình khi mà semaphore được tạo ra Lệnh acquireSem hoạt động như sau: • Giảm giá trị của semaphore. • Nếu kết quả giá trị lớn hơn hay bằng 0, tức là tài nguyên là sẵn sàng, tác vụ có thể sử dụng tài nguyên ngay lập tức. Ngược lai kết quả nhỏ hơn 0, tác vị sẽ bị khóa và chờ đến khi tác vị đang sử dụng tài nguyên sử dụng lệnh releaseSem. Lệnh releaseSem tăng giá trị của semaphore, Nếu kết quả trả về bé hơn hoặc bằng 0, điều đó có nghĩa là có ít nhất một tác vụ đang đợi semaphore, do đó tác vụ sẽ được chuyển vào trạng thái sẵn sàng. Trong trường hợp máy in này, semaphore sẽ được gán mặc định ban đầu là 1 trong trường hợp hệ thống chỉ có một máy in được quản lý. Trường hợp này thông thường được gọi là semaphore nhị phân (binary semaphore) để phân biệt với các trường hợp tổng quát hơn (counting semaphore), trong đó semaphore được mặc định là một số bất kỳ nguyên và không âm. Xét một bộ định địa chỉ bộ nhớ động để quản lý bộ nhớ đệm cố định như trên hình 7.5. Ở đây chúng ta khởi tạo cho semaphore một số lượng bộ nhớ đệm đang còn trống tại thời điểm ban đầu. Khi câu lệnh bufReq được gọi đến, nó trước tiên dành lấy semaphore, sau đó định địa chỉ cho bộ nhớ đệm. Trong 10 lần gọi lệnh bufReq đầu tiên, semaphore vẫn còn không âm, điều này làm cho các tác vụ yêu cầu semaphore vẫn có thể hoạt động 72/99
được. Đến lần thực thi lệnh bufReq lần thứ 11, tác vụ yêu cầu sẽ bị khóa và chờ đến khi có một tác vụ khác gọi lệnh bufReq để giải phóng semaphore. Chia sẻ hệ thống đa tài nguyên Một số kenel sử dụng cả hai loại binary semaphore và couting semaphore vì trong một một số trường hợp, binary semaphore có hiệu quả hơn. Binary semaphone đôi khi còn được gọi là mutex có nghĩa là loại trừ lẫn nhau (mutual exclusion) . Một semaphore đôi khi cũng có thể được sử dụng để tạo tín hiệu cho sự xuất hiện của một sự kiện như trong hình 7.6. Lấy vụ dụ làm thế nào mà hệ thống có thể nhận biết được sự xuất hiện của một ngắt? tác vụ cần thông tin về sự xuất hiện của ngắt sẽ treo (pend) semaphore lên. Chương trình con dịch vụ ngắt (Internet sevice Routine) sẽ phục vụ ngắt và sau đó gửi (post) semaphore lại. (chú ý rằng: thuật ngữ “pend” và “post” được sử dụng thường xuyên hơn các thuật ngữ “acquire” và “release”. Tạo tín hiệu cho sự kiện thông qua semaphore Ở các ví dụ trên, semaphore được khởi tạo bởi một giá trị khác 0 bởi vì tài nguyên là sẵn sàng để sử dụng. Ở đây, semaphore được khởi tạo là 0. Vì vậy khi tác vụ đầu tiên treo 73/99
(pend) semaphore, nó ngay lập tức bị khóa lại - sự kiện chưa được sảy ra. Khi một ISR gửi (post) lại semaphore, tác vụ đó tiếp tục được đánh thức và tiếp tục được thực hiện . Khi semaphore được sử dụng như một khóa tài nguyên, nhiều tác vụ có thể post hoặc pend nó. Tuy nhiên trong trường hợp tạo tín hiệu hoặc đồng bộ hóa, semaphore thường được sử dụng bởi chỉ một ISR và một 1 tác vụ. Cơ chế tương tự như trên cũng có thể được sử dụng khi một tác vụ muốn tạo tín hiệu của một sự kiện tới một tác vụ khác. Monitor Monitor là một ngôn ngữ lập trình được xây dựng để điều khiển việc truy nhập vào vùng dữ liệu chia sẻ trong hoạt động của hệ thống. Mã chương trình đồng bộ được bổ sung vào trong bộ biên dịch và thực thi khi chạy chương trình. • Monitor là một modul đóng gói • Các cấu trúc dữ liệu được chia sẻ. • Các thủ tục hoạt động thao tác trên các cấu trúc dữ liệu chia sẻ. • Đồng bộ các luồng thực thi đồng thời mà có thể kích hoạt các thủ tục trong hoạt động hệ thống. • Monitor có thể bảo vệ dữ liệu khỏi sự truy nhập không có cấu trúc. Nó đảm bảo rằng các luồng truy nhập vào dữ liệu thông qua các thủ tục tương tác theo những cách hợp pháp và có kiểm soát. • Monitor đảm bảo loại trừ xung đột • Chỉ có một luồng có thể thực thi bất kỳ thủ tục nào tại mỗi một thời điểm (luồng trong monitor) • Nếu có một luồng đang thực thi bên trong một monitor nó sẽ khoá các luồng khác muốn vào, do đó monitor cũng phải có một hàng đợi. Minh họa về Monitor 74/99
Kĩ thuật lập lịch và xử lý ngắt trong thời gian thực Các khái niệm Các tác vụ (task) hoạt động dưới sự giám sát của kernel thời gian thực. Chúng bao gồm: • Một tập hợp các dịch vụ thực hiện các công việc như đồng bộ hoá và giao tiếp truyền thông giữa các tác vụ. • Một bộ lập lịch (scheduler) với chức năng khẳng định rằng chỉ có duy nhất tác vụ với mức ưu tiên cao nhất đang được thực thi. Bộ lập lịch xét các tác vụ như những cái máy trạng thái (state machine). Tất cả các kernel đều có mô hình trạng thái của nó, tuy nhiên, thông thường thì các mô hình trạng thái nảy rất phức tạp. Hình 9.1 chỉ ra cho các bạn thấy một mô hình trạng thái mang tính khái niệm của tác vụ. Trong hình, ta thấy có các trạng thái: • Đang thực thi (Running): chỉ có duy nhất một tác vụ là được nằm trong trạng thái này. Một tác vụ có thể tự động chuyển từ trạng thái Đang thực thi sang trạng thái Khoá (Blocked) bằng việc chờ đợi một sự kiện xảy ra. Trong một hệ thống có sự chiếm quyền thực thi (chúng ta sẽ đề cập đến nó sau), bộ lập lịch có thể bắt một tác vụ đang ở trạng thái Đang thực thi xuống trạng thái Sẵn sàng (Ready) nếu có một tác vụ với mức ưu tiên cao hơn chuyển đến trạng thái Sẵn sàng. Chúng ta gọi nó là sựchiếm quyền thực thi (preemption). • Sẵn sàng (Ready): nếu một tác vụ đã sẵn sàng để hoạt động nhưng lại có mức ưu tiên thấp hơn tác vụ đang thực thi, tác vụ đó sẽ được chuyển đến trạng thái này và chờ. Tác vụ này sẽ được chuyển đến trạng thái Đang thực thi nếu nó trở thành tác vụ có mức ưu tiên cao nhất. • Khoá (Blocked): một tác vụ bị khoá là tác vụ đang đợi một sự kiện nào đó xảy ra, ví dụ như một bản tin, tin nhắn được gửi đến hộp thư của tác vụ đó, hay thời gian chờ của tác vụ kết thúc . 75/99
Mô hình trạng thái của tác vụ Các phương pháp lập lịch phổ biến Lập lịch có chu kỳ Có rất nhiều tác vụ mà công việc của nó chỉ là thức dậy theo chu kỳ, làm một vài công việc nào đó và quay trở lại ngủ tiếp. Có một vài phương pháp để thực hiện các tác vụ kiểu này như trên hình 8.2. Trong tất cả các hệ điều hành, chúng ta đều có thể tìm thấy một lệnh gọi là hàm trễ Delay(), hoặc là một vài hàm có chức năng tương tự. Hàm này làm cho tác vụ bị khoá trong một thời gian xác định cho trước, thông thường thời gian này được biểu diễn bằng xung đồng hồ (clock tick). Hình 8.2a cho ta thấy việc thực hiện một tác vụ khi ta sử dụng lệnh Delay() đối với tác vụ có tính chu kỳ đó. Trong trường hợp này, khoảng thời gian trễ là 3 clock tick. Hoạt động của hệ thống phụ thuộc vào thời gian thực thi của tác vụ. Nếu thời gian thực hiện nhỏ hơn 1 tick thì tác vụ sẽ thức dậy sau mỗi 3 tick như mong muốn. Tuy nhiên, nếu tác vụ hoạt động quá 1 tick, khi đó, sau khi tác vụ gọi lệnh Delay(), nó vẫn sẽ bị khoá trong 3 clock tick. Thế nhưng, trong ví dụ này, tác vụ thực tế là sẽ thức dậy sau mỗi 4 xung clock tick. Đó không phải là điều chúng ta mong muốn. Một phương án khác, không phải hệ thống nào cũng có, được trình bày ở hình 8.2b. Trong trường hợp này, bộ lập lịch sẽ đánh thức tác vụ vào đúng thời điểm thích hợp mà không quan tâm đến thời gian thực hiện tác vụ. Do đó, thay vì dùng hàm Delay(), một tác vụ có tính chu kỳ sẽ gọi hàm WaitTilNext(). Hàm này sẽ khóa tác vụ cho tới phiên thực hiện kế tiếp. 76/99
Các tác vụ có tính chu kì Lập lịch không theo chu kỳ Một số tác vụ phải phản ứng lại các sự kiện xảy ra ngẫu nhiên tại các thời điểm khác nhau. Một sự kiện có thể là việc một gói dữ liệu từ trên mạng được gửi đến nơi, việc một cái công tắc đóng lại để chỉ ra là bể nước đã đầy hoặc cũng có thể là sự kết thúc việc convert một tín hiệu tương tự sang số của bộ ADC và đang cần được đọc. Thông thường, các sự kiện không đồng bộ này được giao tiếp với máy tính thông qua các ngắt. Chương trình con dịch vụ ngắt phải có cách nào đó để kết nối sự xuất hiện của ngắt với tác vụ chịu trách nhiệm xử lý sự kiện. Lập lịch theo kiểu chiếm quyền thực thi và lập lịch không có chiếm quyền thực thi Có 2 phương thức cơ bản cho việc lập lịch một tác vụ: chiếm quyền thực thi và không chiếm quyền thực thi. Xét 2 tác vụ: tác vụ 1 có mức ưu tiên thấp hơn đang thực hiện và tác vụ 2 có mức ưu tiên cao hơn đang bị khoá để chờ một sự kiện xảy ra, sự kiện này được thông báo bởi một tín hiệu ngắt. Hình 8.3a cho thấy những gì xảy ra trong hệ thống không có tính chiếm quyền ưu tiên. Chương trình con dịch vụ ngắt ISR làm cho tác vụ 2 với mức ưu tiên cao hơn chuyển từ trạng thái Khoá sang trạng thái Sẵn sàng. Tuy nhiên, đến khi ISR được thực hiện xong thì tác vụ 1 với mức ưu tiên thấp hơn vẫn sẽ được tiếp tục thực thi tại điểm nó bị ngắt. Sau đó, khi tác vụ 1 bị khoá để chờ sự kiện thì tác vụ 2 mới được chuyển sang trạng thái thực thi. Hình 8.3 b ứng với trường hợp của hệ thống có tính chiếm quyền ưu tiên. Điểm khác biệt ở đây là bộ lập lịch được gọi đến ở cuối chương trình con dịch vụ ngắt. Bộ lập lịch xác định tác vụ có mức ưu tiên cao đang ở trạng thái Sẵn sàng và chuyển nó lên trạng 77/99
thái thực thi. Do đó, tác vụ với mức ưu tiên thấp đã bị chiếm quyền thực thi. Một hệ thống không có tính chiếm quyền thực thi muốn rằng tất cả các tác vụ phải là “những công dân tốt” bằng cách tự nguyện trao trả bộ xử lý cho các tác vụ khác để chắc chắn một điều: các tác vụ đều có cơ hội để sử dụng bộ xử lý. Các thế hệ Windows trước kia đều là dạng này. Linux thì khác, nó là một hệ điều hành có tính chiếm quyền thực thi mặc dù các bản Linux chuẩn không quan tâm đến vấn đề thời gian thực bởi trong một thời gian dài, vấn đề chiếm quyền thực thi không được đề cập. Các hệ thống có tính chiếm quyền thực thi cung cấp cho ta nhiều hơn thời gian phản ứng có thể dự đoán được bởi vì tác vụ có mức ưu tiên cao sẽ được xử lý ngay lập tức. Đây chính là điểm cốt lõi của thời gian thưc: khả năng đảm bảo một thời gian lớn nhất để phản ứng lại một sự kiện. Trong hệ thống không chiếm quyền thực thi, chẳng có gì để đảm bảo thời gian một tác vụ nhường lại bộ xử lý cho các tác vụ khác. Mặt khác, trong một hệ thống có chiếm quyền ưu tiên, vấn đề tranh chấp tài nguyên hệ thống cũng đáng được quan tâm cẩn thận. Lập lịch: Có và không có chiếm quyền thực thi Hai phương án khác được tận dụng để xử lý các tác vụ có cùng mức ưu tiên. Trong phương thức lập lịch kiểu vòng lặp robin, một tác vụ sẽ được thực thi đến khi nào nó bị khoá (block) để chờ một sự kiện xuất hiện hoặc cũng có khi nó tình nguyện nhường (yield) bộ xử lý lại. Sự khác biệt giữa khoá và nhường là ở chỗ: trong trường hợp thứ 2, tác vụ sẽ quay trở lại trạng thái Sẵn sàng (ready). Xét trường hợp trong danh sách Sẵn sàng có 3 tác vụ thứ tự lần lượt là A, B, C. Các tác vụ này có cùng mức ưu tiên như nhau. Tác vụ A đứng đầu danh sách và được chuyển đến trạng thái Thực thi. Khi tác vụ A nhường (yield) bộ xử lý, tác vụ B trở thành trạng thái thực thi và danh sách Sẵn sàng sẽ như sau: 78/99
B C A Khi B nhường, C sẽ chuyển trạng thái và danh sách sẽ chuyển thành: B C A Như vậy, tất cả các tác vụ sẽ hoạt động thành một vòng tròn, chúng hoạt động theo kiểu nhường nhau. Các tác vụ có mức ưu tiên thấp hơn trong trạng thái Sẵn sàng sẽ không bao giờ được thực hiện cho đến khi tất cả các tác vụ trên bị khoá. Nhát cắt thời gian là một biến thể của vòng lặp robin. Trong đó, nó quy định mỗi tác vụ sẽ nhận được một lượng thời gian nhất định hay còn gọi là nhát cắt thời gian. Việc làm này bảo vệ các tác vụ khỏi trường hợp chiếm dụng bộ xử lý quá lâu. Do đó, một tác vụ sẽ chạy cho đến khi nó bị khoá, nó tình nguyện nhường hay quá hạn về thời gian cho phép. Tùy thuộc vào hoàn cảnh và yêu cầu, các tác vụ sẽ có lượng thời gian cho phép bằng nhau hoặc khác nhau. Xét trên khía cạnh nào đó, vòng lặp robin chỉ là một dạng khác của vòng lặp polling. Kỹ thuật lập lịch • FCFS Trong cơ chế lập lịch đến trước được phụ vụ trước thì các quá tình được xử lý theo thứ tự mà nó xuất hiện yêu cầu và cho đến khi hoàn thành. Cơ chế lập lịch này thuộc loại không ngắt được và có ưu điểm là dễ dàng thực thi. Tuy nhiên, nó không phù hợp cho các hệ thống mà hỗ trợ nhiều người sử dụng vì có một sự biến đổi lớn về thời gian trung bình mà một quá trình hay tác vụ phải chờ đợi để được xử lý. Hơn nữa do việc xử lý không ngắt được nên có hiện tượng chiếm hữu độc quyền bộ xử lý trong thời gian dài và có thể gây ra sự trễ bất thường trong quá trình thực hiện của các tác vụ phải chờ đợi khác. • Shortest Job First - SJF Trong cơ chế lập lịch này tác vụ có thời gian thực thi ngắn nhất sẽ có quyền ưu tiên cao nhất và sẽ được phục vụ trước. Vấn đề chính gặp phải trong cơ chế lập lịch này là không biết trước được thời gian thực thi của các tác vụ tham gia trong chương trình và thông thường phải áp dụng cơ chế tiên đoán và đánh giá dựa vào kinh nghiệm về các tác vụ thực thi trong hệ thống. Điều này chắc chắn rất khó để luôn đảm bảo được độ chính xác. Cơ chế lập lịch này có thể áp dụng cho cả loại ngắt được và không ngắt được. • Rate monotonic (RM): 79/99
Phương pháp lập lịch RM có lẽ hiện này là thuật toán được biết tới nhiều nhất áp dụng cho các tác vụ hay quá trình độc lập. Phương pháp này dựa trên một số giả thiết sau: (1) Tất cả các tác vụ tham gia hệ thống phải có deadline kiểu chu kỳ (2) Tất cả các tác vụ độc lập với nhau (3) Thời gian thực hiện của các tác vụ biết trước và không đổi (4) Thời gian chuyển đổi ngữ cảnh thực hiện là rất nhỏ và có thể bỏ qua Thuật toán RM được thực thi theo nguyên lý gán mức ưu tiên cho các tác vụ dựa trên chu kỳ của chúng. Tác vụ nào có chu kỳ nhỏ thì sẽ có được gán mức ưu tiên cao. Theo nguyên lý này với các tác vụ chu kỳ không thay đổi thì RM sẽ là phương pháp lập lịch cho phép ngắt và mức ưu tiên cố định. Tuy nhiên RM hỗ trợ yêu cầu hệ thống không tốt. • Earliest deadline first (EDF) Như đúng tên gọi của phương pháp, thuật toán lập lich theo phương pháp này sử dụng deadline của tác vụ hay như điều kiện ưu tiên để xử lý điều phối hoạt động. Tác vụ có deadline gần nhất sẽ có mức ưu tiên cao nhất và các tác vụ có deadline xa nhất sẽ nhận mức ưu tiên thấp nhất. Ưu điểm nổi bật của phương pháp này là giới hạn có thể lập lịch đáp ứng được 100% cho tất cả các tập tác vụ. Hơn nữa mức ưu tiên gán cho mỗi tác vụ trong quá trình hoạt động là động vì vậy chu kỳ của tác vụ có thể thay đổi bất kỳ lúc nào theo thời gian. EDF có thể được áp dụng cho các tập tác vụ chu kỳ và cũng có thể mở rộng để đáp ứng cho các trường hợp các deadline thay đổi khác nhau theo chu kỳ. Vấn đề chính của thuật toán lập lich EDF là không thể đảm bảo được tác vụ nào trong hệ thống có thể không được thực thi trong tình huống quá độ hệ thống bị quá tải. Trong nhiều trường hợp mặc dù mức độ sử dụng trung bình nhỏ hơn 100% những vẫn có thể trong một tình huống nào đó vẫn vượt qua khả năng đáp ứng của hệ thống tức là sẽ có tác vụ không được đảm bảo thực thi đúng. Trong những trường hợp như vậy cần phải điều khiển để biết tác vụ nào bị lỗi không thực hiện thành công hoặc tác vụ nào được thực hiện thành công trong quá trình quá độ. • Minimum Laxity first (MLF) Cơ chế lập lịch này sẽ ưu tiên tác vụ nào còn ít thời gian còn lại để thực hiện nhất trước khi nó phải kết thúc để đảm bảo yêu cầu thực thi đúng. Đây được xem là cơ chế lập lịch gán quyền ưu tiên động và dễ đạt được sự tối ưu về hiệu suất thực hiện và sự công bằng trong hệ thống. • Round Robin 80/99
Đây là một cơ chế lập lịch phân bổ đều đặn, ngắt được và đơn giản. Mỗi một tác vụ được xử lý/phục vụ trong một khoảng thời gian nhất định và lặp lại theo một chu trình xuyên suốt toàn bộ các tác vụ tham gia trong hệ thống. Khoảng thời gian phục vụ cho mỗi tác vụ trong quá trình là một sự thoả hiệp giữa thời gian thực hiện của các tác vụ và thời gian thực hiện một chu trình. Có thể chọn khoảng thời gian đó rất nhỏ và đôi lúc chúng ta không nhận được ra rằng đang có sự phân bổ thực hiện trong hệ thống. Tuy nhiên nếu thời gian đó quá nhỏ có thể làm mất tính hiệu quả thực hiện toàn hệ thống vì cần nhiều thời gian trong việc chuyển đổi ngữ cảnh cho mỗi tác vụ sau mỗi chu trình thực hiện. Xử lý ngắt Một hệ thống thời gian thực được gọi là “điều khiển sự kiện” có nghĩa là hệ thống đó phải có chức năng chính là phản ứng lại các sự kiện xảy ra trong môi trường của hệ thống. Vậy thì hệ thống phản ứng lại các sự kiện như thế nào?. Hiện nay có hai phương pháp tiếp cận vấn đề này. Phương pháp đầu tiên là Polling hay Vòng lặp Polling và phương pháp thứ 2 là xử lý ngắt (Interrup). Polling Vòng lặp Polling Hãy xem đoạn code trong hình 8.4. Chương trình được bắt đầu bằng một vài cài đặt ban đầu cho hệ thống rồi truy cập vào trong một vòng lặp vô hạn, trong đó, các sự kiện mà hệ thống có thể phản ứng lại được kiểm tra. Khi có một sự kiện xảy ra, dịch vụ phản ứng lại sự kiện đó được kích hoạt. Tiến trình thực hiện của vòng lặp trên tỏ ra khá đơn giản và thích hợp với những hệ thống nhỏ không đòi hỏi quá gắt gao về mặt thời gian. Tuy nhiên, cũng có một số vấn đề cần bàn đến: • Thời gian phản ứng lại sự kiện phụ thuộc rất lớn vào vị trí mà chương trình đang thực hiện trong vòng lặp. Lấy ví dụ: Nếu sự kiện event_1 xảy ra ngay 81/99
trước câu lệnh if(event_1) thì thời gian phản ứng là rất ngắn. Nhưng nếu sự kiện event_1 xảy ra ngay sau khi câu lệnh kiểm tra đó, chương trình lúc này phải quét toàn bộ vòng lặp và quay trở về điểm đầu và thực hiện dịch vụ của sự kiện event_1. • Và cũng là một hệ quả tất yếu, thời gian phản ứng cũng là một hàm của số lượng sự kiện được kích hoạt tại một thời điểm và sau đó là thời gian thực hiện các dịch vụ trong một lần quét vòng lặp của chương trình. • Tất cả các sự kiện được chương trình đối xử một cách bình đẳng và không có sự ưu tiên nào cả. • Khi có một đặc tính mới, do đó là dịch vụ mới, được thêm vào chương trình, thời gian phản ứng lại dài thêm ra. Interrupt (ngắt) Phương pháp tiếp cận thứ 2 là ngắt (Interrupt). Rất hữu dụng và cũng gây không ít khó khăn cho người lập trình. Ý tưởng của ngắt: sự xuất hiện của một sự kiện có thể “ngắt” tiến trình thực hiện của chương trình, “nhồi” thêm và thực hiện một tiến trình khác vào như hình 8.5. Khi tiến trình nhồi thêm được thực hiện xong, chương trình chính lại được thực hiện tiếp từ thời điểm bị ngắt. Tiến trình của sự kiện ngắt được thực hiện ngay lập tức mà không phải quan tâm đến chương trình chính. Những tiến trình như thế người ta gọi là “chương trình con dịch vụ ngắt” (Interrupt Service Routine) viết tắt ISR. Các thế hệ vi xử lý hiện nay thường thực hiện 3 loại ngắt khác nhau: • Câu lệnh INT, hay nhiều khi còn được nhắc đến với cái tên là TRAP (bẫy). Nó như một câu lệnh để gọi một chương trình con đặc biệt. Chúng ta sẽ đề cập đến nó sau. • Các trường hợp đặc biệt của bộ xử lý. Các điều kiện lỗi như lỗi chia 0, lỗi truy cập bất hợp pháp vào bộ nhớ có thể được điều khiển thông qua cơ chế ngắt. Ngắt Hai loại ngắt kể trên đồng bộ với việc thực hiện lệnh. Trong đó: INT chính là một câu lệnh và các lỗi đặc biệt của bộ xử lý chính là kết quả trực tiếp của việc thực hiện lệnh. 82/99
Loại ngắt thứ 3 được tạo ra bởi sự kiện xảy ra bên ngoài bộ xử lý. Loại ngắt này được tạo ra bởi các I/O phần cứng và xảy ra không đồng bộ với việc thực hiện lệnh. Các ngắt ngoài không đồng bộ: • Làm tối đa hoá hiệu suất và thông lượng của hệ thống máy tính • Gây ra phần lớn các lỗi và rắc rối cho người lập trình Hầu hết các bộ xử lý đều sử dụng lược đồ ngắt giống nhau. Hình 8.6 chỉ ra kiến trúc ngắt của Intel x86. 1kilo byte (KB) đầu tiên của bộ nhớ được giành cho bảng véctơ ngắt (Interrupt Vector Table). Mỗi một véctơ có 4 byte thể hiện địa chỉ (segment và offset) của chương trình con dịch vụ ngắt. Các véctơ này mang những ý nghĩa, chức năng khác nhau và được định nghĩa bởi kiến trúc của bộ xử lý. Ví dụ: véctơ 0 là lỗi chia 0, véctơ 3 là breakpoint (lệnh ngắt INT 1byte). Ngắt- Bảng véctơ ngắt Một số véctơ được dành cho các ngắt ngoài. Trong PC, các véctơ 8 đến 15 và 0x70 đến 0x77 được dành cho phần cứng. Tất cả các véctơ được truy cập thông qua lệnh ngắt INT 2byte, trong đó, byte thứ 2 chỉ ra số thứ tự của véctơ (ngắt). Phần mềm hệ thống thường thiết lập các quy ước liên quan đến nhiều véctơ này. Ví dụ: PC BIOS sử dụng một số ngắt cho các dịch vụ phần cứng và LINUX sử dụng ngắt INT 0x80 để gọi dịch vụ của kernel. Sau đây là một ví dụ về việc sử dụng ngắt INT 0x80 của Linux: • Bộ xử lý lưu lại giá trị hiện thời của thanh ghi bộ đếm chương trình Program Counter (PC) và Code Segment (CS) vào ngăn xếp stack cùng với từ điều khiển trạng thái bộ xử lý Proccesor Status Word (PSW). 83/99
• Byte thứ 2 trong câu lệnh INT là một chỉ số trong bảng véctơ ngắt để từ đó tìm được địa chỉ của chương trình con dịch vụ ngắt (ISR). Bộ xử lý nạp địa chỉ này vào thanh ghi PC và CS và việc thực hiện chương trình con được thực hiện từ điểm này. Ngắt và hoạt động của ngắt • Kết thúc của ISR là câu lệnh IRET (Interrupt Return). Nó giải phóng PC và CS để nạp lại giá trị của chương trình chính và thực hiện tiếp lệnh tiếp theo sau lệnh INT. Lệnh INT cũng tương tự như lệnh gọi chương trình con CALL nhưng có đôi chút khác biệt: trong khi địa chỉ đích của lệnh CALL được nhúng vào trong câu lệnh đó thì với INT, ta không cần quan tâm đến địa chỉ của ISR. Địa chỉ của nó nầm trong bảng véctơ ngắt. Đây là một điểm thuận lợi cho việc truyền thông giữa chương trình được biên dịch và chương trình được tải, ví dụ như chương trình ứng dụng và hệ điều hành. Các ngắt ngoài có cách thức thực hiện như thể hiện trong hình 8.8. Một thiết bị bên ngoài đưa ra một “yêu cầu ngắt” Interrupt Request (IRQ). Khi bộ xử lý phản ứng lại bằng một xác nhận “chấp nhận ngắt” Interrupt Acknowledge (IAK), thiết bị đó sẽ gửi số thứ tự của véctơ ngắt lên bus dữ liệu. Bộ xử lý sau đó sẽ thiết lập một lệnh ngắt INT với chỉ số véctơ ngắt đã được cung cấp. Ngắt cứng 84/99
Hình 8.8: Ngắt cứng Ngắt có thể được kích hoạt hoặc bị vô hiệu hoá. Ở cấp độ của bộ xử lý, ngắt có thể được kích hoạt hoặc vô hiệu hoá thông qua câu lệnh STI và CLI. Các ngắt có thể được kích hoạt hoặc vô hiệu một cách có chọn lọc ở cả bộ điều khiển ngắt 8259 hay ở chính thiết bị đó. Trên thực tế, việc kích hoạt và vô hiệu ngắt chính làđiểm mấu chốtđể thiết kế và thực thi một phần mềm thời gian thực Cũng không có gì đáng ngạc nhiên khi nói rằng ngắt không đồng bộ có những vấn đề đáng bàn của nó. Để ý một ứng dụng thu thập dữ liệu dựa trên bộ A/D đa kênh như trên hình 8.9. Cứ mỗi khi bộ chuyển đổi A/D thu thập một tập hợp dữ liệu trên các kênh, nó ngắt bộ xử lý. Chương trình con dịch vụ ngắt đọc dữ liệu và cất vào bộ nhớ đệm, nơi mà chương trình khác (còn gọi là chương trình nền) sẽ tiếp tục xử lý. Ví dụ về ngắt Hoạt động điều khiển ngắt cho phép chúng ta phản ứng lại A/D một cách nhanh chóng trong khi bộ nhớ đệm tách chương trình nền khỏi nguồn dữ liệu, ví dụ: chương trình nền không cần quan tâm đến dữ liệu được từ đâu mà có được. Bây giờ hãy xem đến đoạn mã lệnh được ghi trong hình 8.9. Giả thiết chỉ là thí nghiệm, chúng ta cung cấp một tín hiệu biến đổi liên tục vào cả kênh 5 và 6. Đồng thời, giả thiết rằng chương trình sẽ không bị “fail” khi đang thực hiện đo tín hiệu đồng nhất. Trong thực tế, chương trình như đã viết chắc chắn sẽ bị “fail” bởi vì một ngắt có thể xảy ra trong khi cập nhật biến Cur_temp và cập nhật biến Set_temp với kết quả là giá trị của biến Cur_temp được cập nhật từ tập hợp dữ liệu cũ trước đó, còn giá trị của biến Set_temp được cập nhật từ tập hợp dữ liệu hiện thời. Như vậy, khi tín hiệu đầu vào thay đổi theo thời gian và các tập hợp dữ liệu được tách rời nhau ở các thời gian xác định, giá trị các biến sẽ khác nhau và do đó, chương trình sẽ “fail”. Đây chính là bản chất của vấn đề lập trình thời gian thực. Cần phải quản lý các ngắt khôngđồng bộđể chúng không xảy ra vào những thờiđiểm không thích hợp. 85/99
Có một giải pháp, dù không hay cho lắm, để giải quyết vấn đề này. Ta có thể dùng một lệnh vô hiệu hoá ngắt (CLI) trước khi cập nhật biến Cur_temp và kích hoạt ngắt bằng lệnh STI sau khi cập nhật biến Set_temp. Việc làm này giúp các ngắt tránh khỏi phiền phức của việc cập nhật liên tục như đã đề cập. Có vẻ như chúng ta đã sáng suốt khi sử dụng các lệnh CLI và STI như một chìa khoá cho một giải pháp đúng đắn, nhưng nếu chỉ đơn giản là rải các lệnh CLI và STI trong code của chương trình thì cũng chẳng khác gì việc sử dụng các lệnh “go to” và các biến toàn cục. 86/99
Thiết kế Hệ thống nhúng Quy trình phát triển của một hệ thống nhúng Quá trình phát triển của một hệ thống nhúng được thực hiện theo chu trình sau: • (1) Problem specification • (2) Tool/chip selection • (3) Software plan • (4) Device plan • (5) Code/debug • (6) Test • (7) Integrate Mô hình hóa sự kiện và tác vụ Phương pháp mô hình Petrinet Năm 1962 Carl Adam Petri đã công bố phương pháp mô hình hình hoạ tác vụ hay quá trình theo sự phụ thuộc nhân quả đã được phổ cập rộng rãi và được biết tới như ngày này với tên gọi là mạng Petri. Mạng Petri được sử dụng phổ biến để biểu diễn mô hình và phân tích các hệ thống có sự cạnh tranh trong quá trình hoạt động. Một hệ thống có thể hiểu là một tổ hợp của nhiều thành phần và mỗi thành phần thì đều có các thuộc tính. Các thuộc tính đó có thể thay đổi và được đặc trưng bởi các biến trạng thái. Một chuỗi các trạng thái sẽ mô tả quá trình động của một hệ thống. Mạng Petri thực sự là một giải pháp mô tả hệ thống động với các sự kiện rời rạc tác động làm thay đổi trạng thái của các đối tượng trong hệ thống theo từng điều kiện cụ thể trạng thái của hệ thống. Mạng Petri được thiết lập dựa trên 3 thành phần chính: (1) Các điều kiện, (2) các sự kiện, và (3) quan hệ luồng. Các điều kiện có thể là thoả mãn hoặc không thoả mãn. Các sự kiện là có thể xảy ra hoặc không. Và quan hệ luồng mô tả điều kiện của hệ trước khi sự kiện xảy ra. Các điều kiện đòi hỏi phải thoả mãn để một sự kiện xảy ra hoặc chuyển trạng thái thực hiện thì được gọi là điều kiện trước (precondition). Các điều kiện mà được thoả mãn khi một sự kiện nào đó xảy ra thì được gọi là điều kiện sau (postcondition). 87/99
Quy ước biểu diễn mô hình Petrinet Ví dụ về mô hình mạng Petri Trong qui ước biểu diễn hình hoạ thì mạng Petri sử dụng các vòng tròn để biểu diễn các điều kiện, các hộp để biểu diễn các sự kiện, và mũi tên biểu diễn quan hệ luồng. Một ví dụ minh hoạ về mạng Petri được mô tả trong Hình 13.1, trong đó: • P = {p1 , p2 , , pnp } là tập gồm np vị trí được biểu diễn trong mô hình (được mô tả bởi các vòng tròn). • T = {t1 , t2 , , tnt } là tập gồm nt chuyển đổi trong tập chuyển đổi biểu diễn trong mô hình (được mô tả bởi các hình chữ nhật). • I biểu diễn quan hệ đi vào chuyển đổi và được ký hiệu bởi đường mũi tên theo hướng từ các vị trí tới các chuyển đổi. • O biểu diễn quan hệ đi ra khỏi chuyển đổi và được ký hiệu bởi các đường mũi tên theo hướng từ các chuyển đổi tới các vị trí. • M = {m1 , m2 , mnp } là dấu trạng thái của các chuyển đổi trong hệ thống. Các giá trị mi là số các thẻ bài (được ký hiệu như các chấm tròn đen) chứa bên trong các vị trí pi trong tập dấu M . Hệ thống động có thể được mô tả bởi mạng Petri nhờ sự chuyển dịch các thẻ bài trong các vị trí của hệ thống mô hình và tuân thủ theo luật sau: • Một chuyển đổi được phép thực thi nếu tất cả các vị trí đi vào chuyển đổi đó chứa ít nhất một thẻ bài. • Khi một chuyển đổi đã được thực thi xong (hoàn thành) thì một thẻ bài sẽ bị loại ra khỏi vị trí đi vào chuyển đổi đó đồng thời bổ sung thêm một thẻ bài vào các vị trí đầu ra tương ứng của chuyển đổi đó. 88/99
Các trạng thái động của hệ thống được mô tả bởi tập R(M) đánh dấu bởi các dấu trong tập M. Trong ví dụ trên có 5 phần tử dấu trong tập R lần lượt là M 1 , M 2 , M 3 , M 4 , M 5. Tương ứng lần lượt như sau: • M 1 = (1, 0, 0, 0, 0) • M 2 = (0,1,1, 0, 0) • M 3 = (0,1, 0, 0,1) • M 4 = (0, 0, 0,1,1) • M 5 = (0, 0,1,1, 0) Mô tả các tình huống hoạt động cơ bản với Petrinet • Song song và đồng bộ: Trong mô hình PN mô tả như trong Hình 9.2 (a), các chuyển đổi t1 và t2 được phép thực hiện đồng thời; hoạt động của chúng không ảnh hưởng đến nhau. Các hoạt động được mô hình bởi hai chuyển đổi thực hiện song song. Trong hệ thống dự phòng với độ tin cậy cao, mô hình này được sử dụng để biểu diễn hai thành phần C1 và C2 song song để đảm bảo hoạt động dự phòng; trong trường hợp này các vị trí p1 và p3 biểu diễn điều kiện làm việc, các vị trí p2 và p4 biểu diễn điều kiện lỗi, t1 và t2 là các sự kiện lỗi trong các tác vụ C1 và C2 một cách tương ứng. Mô hình Petrinet 2 hoạt động song song: Độc lập (a) và đồng bộ (b) Trong hoạt động song song, các tác vụ hoàn toàn độc lập, tuy nhiên nếu các sự kiện đó cần phải kết thúc và là điều kiện để cho một chuyển đổi khác thì hoạt động đồng bộ có thể được thực hiện nhờ bổ sung một chuyển đổi t3 như mô tả trong Hình 9.2 (b). Khi đó chuyển đổi t3 cần thẻ bài đồng thời của cả p2 và p4. • Chia sẻ đồng bộ: Một yếu tố đặc trưng trong hoạt động của hệ thống phân tán là thường phải chia sẻ một số tài nguyên hữu hạn. Sự thiếu thốn về tài nguyên làm hạn chế hoạt động của hệ thống trong quá trình xử lý thậm chí làm tắc nghẽn hệ thống. Việc mô hình và phân tích các 89/99
hệ thống có hiện tượng tắc nghẽn là một tác vụ khó khăn trong hầu hết các quá trình mô hình có thể gặp phải. Hoạt động của bộ đệm với dung lượng hữu hạn Để minh hoạ tình huống này, biểu diễn hoạt động của bộ đệm với dung lượng hữu hạn được mô tả bởi PN trong Hình 9.3. Vị trí p3 mô hình số các vị trí bộ đệm còn trống và vị trí p2 mô hình số vị trí đã được điền đầy; chú ý rằng tổng các thẻ bài chứa trong các vị trí p2 và p3 luôn là hằng số (trong ví dụ này là 3). Chuyển đổi t2 mô hình quá trình điền đầy một vị trí bộ đệm và hoàn thành nếu có ít nhất một vị trí bộ đệm còn trống cùng với thẻ bài chứa trong vị trí p1 và p3. Chuyển đổi t3 được phép thực hiện nếu có ít nhất một vị trí bộ đệm đã được điền đầy. Khi hoàn thành chuyển đổi t3, một thẻ bài sẽ được chuyển từ vị trí p2 sang vị trí p3. • Tuần tự: Hoạt động tuần tự sẽ được mô tả và minh hoạ bởi hoạt động của bộ tạo và bộ sử dụng thông qua một bộ đệm. Bộ tạo sẽ sinh ra các đối tượng để đưa vào trong một bộ đệm và sẽ được lấy ra bởi bộ sử dụng. Quá trình sử dụng sẽ phải được thực hiện một cách tuần tự theo quá trình tạo ra đối tượng. Mô hình cho hoạt động này được diễn tả bởi PN như trong Hình 9.4 (a). Thẻ bài chứa trong vị trí p1 có nghĩa là bộ tạo đã sẵn sàng thực hiện. Khi các chuyển đổi t1 và t2 hoàn thành thì một đối tượng được tạo ra (một thẻ bài tương ứng cũng sẽ được chuyển vào trong bộ đệm mô hình bởi vị trí p5) và bộ tạo lại sẵn sàng trở lại. Nếu bộ sử dụng có nhu cầu tiêu thụ (được mô hình bởi thẻ bài chứa trong vị trí p3 ) và đang có ít nhất một đối tượng trong bộ đệm thì một thẻ bài chứa trong vị trí p5 sẽ được lấy đi và chuyển đổi t3 sẽ hoàn thành. 90/99
Hoạt động tạo và sử dụng với bộ đệmvô hạn (a) và hữu hạn(b) Trong cách mô tả trong Hình 9.4 (a) thì việc tạo và sử dụng được thực hiện thông qua một bộ đệm với giả thiết là có dung lượng vô hạn. Trong thực tế thì các bộ đệm là hữu hạn, để mô tả hoạt động với bộ đệm loại này Hình 9.4 (b) được sử dụng. Vị trí p6 mô hình các vị trí bộ đệm còn trống và vị trí p5 mô hình các vị trí bộ đệm đã được điền đầy. Tổng số lượng các thẻ bài chứa trong các vị trí p5 và p6 phải luôn là hằng số. Nếu một thẻ bài được gán cho vị trí p5 trong dấu khởi tạo thì bộ tạo sẽ không thể tạo thêm đối tượng chừng nào bộ sử dụng vẫn chưa tiêu thụ đối tượng trong bộ đệm. Loại trừ xung đột Hoạt động loại trừ của hai tác vụ song song chia sẻ tài nguyên Hai tác vụ C1 và C2 được phép làm việc song song và cùng chia sẻ tài nguyên CS, nhưng không được truy nhập vào tài nguyên đồng thời. Giản đồ PN cho hoạt động này được mô tả như trong Hình 10.5. Các vị trí p1 và p5 biểu diễn các tác vụ C1 và C2 làm việc độc lập; vị trí p2 và p6 biểu diễn các yêu cầu của các tác vụ C1 và C2 một cách tương ứng khi muốn truy nhập vào tài nguyên chia sẻ CS; p3 và p7 biểu diễn CS đang bị chiếm dụng bởi các tác vụ C1 và C2 một cách tương ứng. Vị trí p4 mô tả quyết định xem tác vụ nào có thể truy nhập tài nguyên Cs và tránh các vị trí p3 và p7 bị đánh dấu đồng thời. Thực tế khi p2 và p6 được đánh dấu thì các chuyển đổi t2 và t5 xung đột. Việc hoàn thành một trong hai tác vụ sẽ khoá/cấm lẫn nhau. Việc hoàn thành chuyển đổi 91/99
t3 hoặc t6 sẽ mô hình việc giải phóng nguồn tài nguyên chung (chuyển thẻ bài trở lại vị trí p4) và trở về điều kiện làm việc bình thường. Ngôn ngữ mô tả phần cứng (VHDL) VHDL (Very High Speed Integrated Circuit Hardware Description Lanuage) là một ngôn ngữ chung để mô tả các thiết kế phần cứng ở mức phần tử logic cơ bản cấu thành nên hệ thống và đã được phát triển bởi tổ chức quốc phòng Mỹ. Mục đích chính là để thuận tiện cho việc trao đổi dữ liệu thiết kế phần cứng theo một định dạng chuẩn mà mọi người có thể hiểu và thông dịch, tạo điều kiện thuận lợi trong việc phối hợp hay hợp tác trong các dự án thiết kế. Đặc biệt nó rất thuận tiện trong việc chuyển đổi hay tổng hợp biên dịch thành một dạng ngôn ngữ thực thi phần cứng thực. Điều này rất khó thực hiện bằng các ngôn ngữ bậc cao như C nhưng với VHDL điều này chính là ưu điểm nổi bật và là thế mạnh trong việc mô hình hoá hệ thống, mô tả một cách chi tiết các phần tử cứng cấu thành tham gia trong hệ thống. VHDL là một chuẩn IEEE (Std - 1076) đã được sự hỗ trợ bởi rất nhiều nhà cung cấp phát triển phần cứng. Ứng dụng một cách chuyên nghiệp ngôn ngữ này là phục vụ cho việc mô tả các mạch ASICs phức hợp, chế tạo thực thi các mạch FPGA Ngôn ngữ VHDL có thể đọc hiểu khá dễ dàng với cấu trúc cú pháp rõ ràng gần giống như ngôn ngữ Visual Basic và Pascal. Nó có thể phát huy được thế mạnh về cú pháp để định nghĩa xây dựng kiểu dữ liệu mới và hỗ trợ cho việc lập trình theo nhóm. Với xu thế hiện nay các nhóm phát triển có thể thực thi với điều kiện cách xa nhau về khoảng cách địa lý, vì vậy việc phối hợp và thiết kế theo nhóm là rất cần thiết. 92/99
Thiết kế các phần mềm điều khiển Thiết kế phần mềm điều khiển Hệ thống điều khiển số Để thực thi một bộ điều khiển số trên thiết bị vật lý thực phải đòi hỏi xét xem bộ điều khiển với mô hình hàm truyền đã cho có thể hiện thực hóa được không. Điều kiện phải xét thực ra là để đảm bảo rằng không có đầu ra nào của hệ thống lại xuất hiện trước khi có tín hiệu vào. Hay nói cách khác hệ thống xây dựng phải tuân thủ tính nhân quả. Nếu khai triển hàm truyền của bộ điều khiển số được mô tả ở dạng tổng quát: thành chuỗi lũy thừa theo z thì nó phải không được phép chứa bất kỳ phần tử nào chứa lũy thừa dương của z. Hay nói cách khác là bộ điều khiển được mô tả như trên phải có bậc ≤ 0 tức là bậc của tử số phải nhỏ hơn hoặc bằng bậc của mẫu số (n ≥ m). Sau khi đã thiết kế được bộ điều khiển số thì việc còn lại là lập trình và nạp vào các bộ điều khiển vật lý khả trình. Thực chất quá trình này là thực thi hàm truyền của bộ điều khiển số bằng lập trình số trên các bộ điều khiển vật lý đã có. Ở đây chúng ta sẽ chủ yếu quan tâm đến việc triển khai để chuẩn bị cho bước lập trình các hàm truyền của bộ điều khiển số. Xuất phát từ mô tả hàm truyền dạng tổng quát của bộ điều khiển số: trong đó, a0 ≠ 0 nếu b0 ≠ 0 ; m và n là các số nguyên dương. Có thể triển khai để thực thi một hàm truyền của bộ điều khiển số theo 3 cách như sau: Triển khai lập trình số trực tiếp 93/99
Để triển khai lập theo phương pháp lập trình trực tiếp thì hàm truyền bộ điều khiển đã cho biểu diễn trong miền z phải được chuyển đổi về dạng hàm truyền rời rạc: Từ đẳng thức trên dễ dàng tính ra được giá trị của đầu ra u * (t ) của bộ điều khiển số đã cho theo các giá trị hiện tại và quá khứ của đầu vào e* (t ) cũng như các giá trị quá khứ của chính nó Để thực hiện bộ điều khiển này yêu cầu phải lưu trữ các giá trị quá khứ của đầu vào và đầu ra của bộ điều khiển. Với bộ điều khiển đã cho yêu cầu phải có n + m giá trị cần phải lưu trữ hay nói cách khác cần phải có n + m phần tử lưu trữ. Một phương pháp khác để triển khai lập trình trực tiếp là sử dụng cơ chế tách trực tiếp đầu vào và đầu ra của bộ điều khiển theo một biến trung gian X(z). Không mất tính tổng quát nếu chúng ta nhân cả tử và mẫu của hàm truyền bộ điều khiển số đã cho với một biến X(z). Từ đó rút ra được hàm truyền của đầu vào E(z) theo X(z) và hàm truyền của đầu ra U(z) theo X(z). Phương pháp này thực hiện như sau: Theo phương pháp này yêu cầu số phần tử lưu trữ chính bằng giá trị n, bằng bậc của đa thức mẫu số trong hàm truyền bộ điều khiển số đã cho. Từ 2 đẳng thức trên ta cũng dễ dàng xây dựng được giản đồ trạng thái mô tả hàm truyền của bộ điều khiển số (giả thiết m = n = 3 ). Giản đồ trạng thái của hệ thống số • Triển khai lập trình số ghép tầng 94/99
Cách triển khai này yêu cầu chuyển đổi bộ điều khiển về dạng tích của các hàm truyền đơn giản để có thể dễ dàng thực hiện bằng các chương trình đơn giản. Hay nói cách khác bộ điều khiển số đã cho là kết quả ghép tầng của nhiều bộ điều khiển nhỏ. • Triển khai lập trình số song song Bộ điều khiển đã cho sẽ được tách ra thành tổng của các bộ điều khiển đơn giản và có thể thực hiện lập trình song song cho các bộ điều khiển đó. Một số phương pháp phát triển phần mềm nhúng Trong quá trình phát triển, phần mềm cần phải được thử nghiệm với đối tượng điều khiển. Tuỳ thuộc vào từng môi trường phát triển chúng ta có thể tiến hành theo một số các phương pháp sau. • Mô hình Offline Trong hệ thống phát triển này nền phần cứng nhúng đích được mô phỏng bằng mô hình chạy trên PC và đối tượng điều khiển cũng là mô hình mô phỏng chạy trên PC. Vì vậy quá trình phát triển thực chất là quá trình chạy mô phỏng hệ thống được thực hiện hoàn toàn trên PC. Với hệ thống này không thể thử nghiệm cho các sự kiện đáp ứng thời gian thực vì thời gian của mô phỏng khác với thời gian diễn biến thực của hệ thống. • Hệ thống phát triển (Software in the loop) 95/99
Hệ thống này mô phỏng nền phần cứng thực trên PC cho đáp ứng hành vi giống như với vi mạch cứng thực và mô hình đối tượng được mô hình thực thi trên PC. Loại hệ thống này cũng tương tự như hệ thống mô phỏng offline tuy nhiên có ưu điểm hơn vì khả năng mô phỏng hành vi và đáp ứng của vi mạch nhúng chính xác hơn và trung thực hơn. Và cũng có một nhược điểm là không thử nghiệm được bài toán thời gian thực. • Mô phỏng thời gian thực Hệ thống này sử dụng nền phần cứng nhúng đích thực nhưng đối tượng thì chỉ là mô hình thời gian thực không phải đối tượng thực. Ưu điểm là khá mềm dẻo và thay đổi cấu hình đơn giản trong quá trình phát triển để thử nghiệm với các hành vi khác nhau của đối tượng. Rút ngắt và đơn giản hóa công việc xây dựng đối tượng. • Mô hình phát triển thực Hệ thống này sử dụng nền phần cứng nhúng đích thực với đối tượng thực. Tuy nhiên có sự hỗ trợ của công cụ phát triển để có thể cài đặt và thử nghiệm trực tiếp trên nền phần cứng thực. Đây là một dạng mô hình cho kết quả trung thực và chính xác nhất trong các dạng hệ thống phát triển nêu trên. Tuy nhiên các nền phần cứng này thường được phát triển và hỗ trợ bởi các nhà cung cấp để có thể tương thích với công cụ phần mềm kèm theo. 96/99
Tham gia đóng góp Tài liệu: Giáo trình hệ thống nhúng Biên tập bởi: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: Module: Mở đầu hệ thống nhúng Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: Module: Tổng quan hệ thống nhúng Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: Module: Các thành phần cơ bản trong kiến trúc phần cứng Hệ thống nhúng Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: Module: Một số nền phần cứng và Cơ sở kỹ thuật của phần mềm nhúng Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: Module: Hệ điều hành cho các hệ thống nhúng (HĐH thời gian thực) Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: Module: Cơ bản về lập trình nhúng Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: 97/99
Giấy phép: Module: Tác vụ và truyền thông giữa các tác vụ Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: Module: Kĩ thuật lập lịch và xử lý ngắt trong thời gian thực Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: Module: Thiết kế Hệ thống nhúng Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: Module: Thiết kế các phần mềm điều khiển Các tác giả: Khoa CNTT ĐHSP KT Hưng Yên URL: Giấy phép: 98/99
Chương trình Thư viện Học liệu Mở Việt Nam Chương trình Thư viện Học liệu Mở Việt Nam (Vietnam Open Educational Resources – VOER) được hỗ trợ bởi Quỹ Việt Nam. Mục tiêu của chương trình là xây dựng kho Tài nguyên giáo dục Mở miễn phí của người Việt và cho người Việt, có nội dung phong phú. Các nội dung đểu tuân thủ Giấy phép Creative Commons Attribution (CC-by) 4.0 do đó các nội dung đều có thể được sử dụng, tái sử dụng và truy nhập miễn phí trước hết trong trong môi trường giảng dạy, học tập và nghiên cứu sau đó cho toàn xã hội. Với sự hỗ trợ của Quỹ Việt Nam, Thư viện Học liệu Mở Việt Nam (VOER) đã trở thành một cổng thông tin chính cho các sinh viên và giảng viên trong và ngoài Việt Nam. Mỗi ngày có hàng chục nghìn lượt truy cập VOER (www.voer.edu.vn) để nghiên cứu, học tập và tải tài liệu giảng dạy về. Với hàng chục nghìn module kiến thức từ hàng nghìn tác giả khác nhau đóng góp, Thư Viện Học liệu Mở Việt Nam là một kho tàng tài liệu khổng lồ, nội dung phong phú phục vụ cho tất cả các nhu cầu học tập, nghiên cứu của độc giả. Nguồn tài liệu mở phong phú có trên VOER có được là do sự chia sẻ tự nguyện của các tác giả trong và ngoài nước. Quá trình chia sẻ tài liệu trên VOER trở lên dễ dàng như đếm 1, 2, 3 nhờ vào sức mạnh của nền tảng Hanoi Spring. Hanoi Spring là một nền tảng công nghệ tiên tiến được thiết kế cho phép công chúng dễ dàng chia sẻ tài liệu giảng dạy, học tập cũng như chủ động phát triển chương trình giảng dạy dựa trên khái niệm về học liệu mở (OCW) và tài nguyên giáo dục mở (OER) . Khái niệm chia sẻ tri thức có tính cách mạng đã được khởi xướng và phát triển tiên phong bởi Đại học MIT và Đại học Rice Hoa Kỳ trong vòng một thập kỷ qua. Kể từ đó, phong trào Tài nguyên Giáo dục Mở đã phát triển nhanh chóng, được UNESCO hỗ trợ và được chấp nhận như một chương trình chính thức ở nhiều nước trên thế giới. 99/99