ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
VŨ XUÂN MẠNH XÂY DỰNG HỆ THỜI GIAN THỰC VÀ ỨNG
DỤNG CHO BÀI TOÁN QUẢN LÝ NHÀ
HÀNG DỊCH VỤ
LUẬN VĂN THẠC SĨ
Chuyên ngành: Công nghệ Phần mềm
Mã số: 60.48.10 Hướng dẫn khoa học: PGS.TS Nguyễn Văn Vỵ Hà Nội 2011
Trang 3
MỤC LỤC
LỜI CAM ĐOAN 1
LỜI CẢM ƠN 2
MỤC LỤC 3
BẢNG KÝ HIỆU CÁC TỪ VIẾT TẮT 5
BẢNG GIẢI THÍCH CÁC THUẬT NGỮ 6
DANH MỤC CÁC HÌNH VẼ 7
DANH MỤC CÁC BẢNG 9
Xử lý thời gian thực 17
1.5.1
Xử lý ngắt 20
1.5.2
Quản lý tiến trình 22
CHƢƠNG 2: PHÁT TRIỂN HỆ THỐNG THÔNG TIN THỜI GIAN THỰC CHO
QUẢN LÝ DỊCH VỤ NHÀ HÀNG 24
2.1.
Khảo sát, phân tích mô hình quản lý dịch vụ nhà hàng và đề xuất bài toán 24
2.1.1.
Khảo sát hoạt động quản lý dịch vụ nhà hàng 24
2.1.2.
Những vấn đề từ mô hình hoạt động dịch vụ nhà hàng truyền thống 26
2.1.3.
Đề xuất giải pháp 27
2.2.
2.3.3.
Biểu đồ lớp 41
2.4.
Thiết kế 47
2.4.1.
Biểu đồ tƣơng tác 47
2.4.2.
Biểu đồ hoạt động 50
2.4.3.
Biểu đồ thành phần và biểu đồ triển khai hệ thống 55
2.4.4.
Thiết kế thiết bị xử lý trung tâm 56
2.4.5.
Thiết kế thiết bị chọn món 59
2.5.
PHỤ LỤC 76
PLI. Tính năng của vi điều khiển ATmega8 và ATmega48 76
1.
ATmega8 76
2.
ATmega48 77
PLII. Chức năng các khối trong vi điều khiển AVR [3] 78
1.
Bộ nhớ chƣơng trình (Program memory) 78
2.
Bộ nhớ dữ liệu (Data memory) 78
3.
Khối tính toán logic (Arithmetic Logic Unit) 81
4.
Khối ngăn xếp 82
Down
Phím cuộn xuống
Clr
Phím xóa
OK
Phím xác nhận
Mnu
Danh sách lựa chọn lệnh trên thiết bị chọn món
NV
Nhân viên
K.Vực
Khu vực
Max-Tbl
Số lượng bàn lớn nhất có thể
Max-SoLuong
Số lượng đơn vị món ăn lớn nhất có thể
Max-MaNV
Số lượng nhân viên lớn nhất có thể
Max-KV
Số lượng khu vực lớn nhất có thể
NSX
Nhà sản xuất
VĐK
Vi điều khiển, chíp
AP
Access point - điểm truy cập
CSDL
Cơ sở dữ liệu
DL
Dữ liệu
Tên hình
Trang
1.
Hình 1.1: Các mức đáp ứng sự kiện về mặt thời gian
12
2.
Hình 1.2: Đồ thị mô tả đặc trưng hai loại hệ thời gian thực
14
3.
Hình 1.3: Các thành phần của hoạt động thời gian thực
16
4.
Hình 1.4: Các kiểu tác vụ theo chuẩn IEC 61131-3
18
5.
Hình 1.5: Mô hình chung của hệ thời gian thực
19
6.
Hình 1.6: Mô hình xử lý ngắt
20
7.
Hình 1.7: Ưu tiên ngắt
21
8.
Hình 1.8: Hành động thực thi thời gian thực yêu cầu bắt đầu một
tiến trình
22
9.
Hình 2.1: Sơ đồ tiến trình phân tích hoạt động nghiệp vụ
29
20.
Hình 2.12: Biểu đồ tuần tự cho use case khai báo khu vực
47
21.
Hình 2.13: Biểu đồ tuần tự cho use case chọn món, hủy món
48
22.
Hình 2.14: Biểu đồ tuần tự cho use case lập phiếu chế biến
49
23.
Hình 2.15: Biểu đồ hoạt động của chức năng gọi món/hủy món của
thiết bị
50
24.
Hình 2.16: Biểu đồ hoạt động chức năng chuyển bàn/ ghép bàn
51
25.
Hình 2.17: Biểu đồ hoạt động chức năng Thanh toán/ gọi nhân viên
52
26.
Hình 2.18: Biểu đồ hoạt động chức năng Thanh toán/ gọi nhân viên
53
27.
Hình 2.19: Biểu đồ hoạt động thiết bị xử lý trung tâm
54
28.
Hình 2.20: Biểu đồ thành phần
55
29.
Hình 2.21: Biểu đồ triển khai hệ thống
67
39.
Hình 2.31: Lưu đồ thuật toán trên bộ xử lý chung
69
40.
Hình 2.32: Lưu đồ thuật toán trên bộ xử lý riêng
70
41.
Hình PLII.1: Bản đồ bộ nhớ dữ liệu
79
42.
Hình PLII.2: Thanh ghi trong bộ nhớ dữ liệu
79
43.
Hình PLII.3: Mô tả ngăn xếp
82 Trang 9
DANH MỤC CÁC BẢNG
Số
Tên bảng
Trang
1.
Bảng 2.1: Giải pháp cho các vấn đề đặt ra
30
2.
Bảng 2.2 : Các tác nhân nghiệp vụ và vai trò
37
3.
Bảng 2.13: Gói dữ liệu ghép bàn / chuyển bàn
72
14.
Bảng 2.14: Gói dữ liệu thanh toán/ gọi nhân viên
72
15.
Bảng PLII.3: Mô tả các thanh ghi của VĐK AVR
80 Trang 10
MỞ ĐẦU
Hiện nay, các hệ thống nhúng đang được ứng dụng rộng rãi trong hầu hết
các thiết bị điện tử chuyên dụng, từ đồ điện tử trong gia đình như Ti vi, máy
giặt, lò vi sóng đến những hệ thống lớn như máy bay, tên lửa, vệ tinh nhân tạo…
Nghiên cứu công nghệ nhúng đang là một hướng nghiên cứu mang nhiều tính
ứng dụng công nghệ mới ở Việt Nam.
Mặc dù một số trường đại học trong nước đã đưa vào giảng dạy một số
môn học như Lập trình hệ thống, Hệ vi xử lý, Công nghệ phần mềm nhúng…
Nhưng việc ứng dụng kiến thức của lĩnh vực này để phát triển các ứng dụng cụ
thể gặp nhiều khó khăn. Lý do đơn giản là việc xây dựng các hệ thống này ngoài
yêu cầu về các linh kiện điện tử, phòng thí nghiệm, công cụ làm việc như Osillo,
đồng hồ vạn năng… người xây dựng còn phải có kiến thức về hệ thống, về điện
tử, về phát triển phần mềm và kinh nghiệm nhất định. Trong khi đó có rất nhiều
ứng dụng chỉ có thể giải quyết bằng thiết bị nhúng
Từ yêu cầu thực tiễn, và cũng để nâng cao kỹ năng thực hành và củng cố lý
thuyết, đề tài “Xây dựng Hệ hệ thời gian thực và ứng dụng cho bài toán quản lý
nhà hàng dịch vụ” được chọn làm đề tài luận văn của tôi. Hiện nay các nhà hàng
dịch vụ lớn phát triển mạnh. Việc quản lý và vận hành chủ yếu dùng sức người
làm cho chất lượng dịch vụ kém, hạn chế kết quả kinh doanh. Việc đưa các ứng
gian thực [8] hoạt động hiệu quả không chỉ phụ thuộc vào sự chính xác của kết
quả tạo ra mà còn phụ thuộc vào thời điểm đưa ra kết quả. Hệ thống sẽ là thất
bại mỗi khi các yêu cầu về thời gian hay mức độ đáp ứng không được thoả mãn.
Hình 1.1 [4] mô tả mức độ đáp ứng kịp thời của hệ thống theo bốn yêu cầu khác
nhau.
Hình 1.1: Các mức đáp ứng sự kiện về mặt thời gian
Trên hình 1.1 (a) sự kiện xảy ra tại thời điểm t
s
hệ thống mất khoảng thời
gian T để nhận biết có sự kiện kích ứng và xử lý tức thời ngay sau đó tại thời
điểm t
p
.
Thời gian
Sự kiện
Phản ứng
T
t
s
p
a) Chính xác tại t = t
pThời gian
Sự kiện
Phản ứng
T
t
s
t
p-1
t
p-2b) Trong khoảng t
p-1
≤ t ≤ t
p-2
Trang 13
Trên hình 1.1 (b) sự kiện xảy ra tại thời điểm t
s
gian này được xác định từ thời điểm bắt đầu và thời điểm hoàn tất công việc.
Trong thực tế, nhiều yếu tố kích thích xảy ra trong khoảng thời gian rất ngắn, ví
dụ vào khoảng vài mili giây, và khi đó thời gian mà hệ thống cần đáp ứng lại các
yếu tố kích thích thường vào khoảng dưới 1 giây mới đảm bảo được yêu cầu
mong muốn. Khoảng thời gian này bao gồm: thời gian tiếp nhận kích thích, thời
gian xử lý thông tin và thời gian đáp ứng kích thích [8].
1.2 Phân loại hệ thời gian thực
Hệ thời gian thực được chia thành hai loại, hệ thời gian thực cứng
(Hardware real time system) và hệ thời gian thực mềm (Sofware real time
system). Hình 1.2 [2] dưới đây minh họa cho sự khác biệt giữa hai loại hệ thống
đó. Với đồ thị có nét đậm biểu thị cho hệ thời gian thực mềm nên kết quả trả về
và thời điểm đáp ứng có dung sai lớn hơn đồ thị thể hiện hệ thời gian thực cứng.
Trang 14
đồ thị hệ mềm
đồ thị hệ cứng
+
- Trang 15
Một hệ thời gian thực mềm là một hệ thống mà trong đó các hoạt động của
nó được phép hoàn thành trong một sai số cho phép mà không gây hậu quả
nghiêm trọng [8], tức là sự đáp ứng của hệ thống có thể vượt ra ngoài một giới
hạn cho phép mà vẫn có thể chấp nhận được. Ví dụ về hệ thống này bao gồm
những hệ thống thực hiện tương tác trực tuyến, những bộ chuyển mạch điện
thoại, hay các trò chơi điện tử.
Sự phân biệt giữa khoảng thời gian bắt buộc cứng hay mềm của hệ thời
gian thực hiện thường tùy thuộc trạng thái định lượng những giới hạn mang lại
kết quả hữu dụng. Tuy nhiên, trong thực tế, sự phân chia này nhiều khi không
cần thiết. Vì vậy, sự phân chia này chỉ có tính tương đối.
1.3 Đặc điểm của hệ thời gian thực
Một hệ thống thời gian thực có các đặc trưng tiêu biểu [2] sau:
− Tính bị động: Hệ thống thường phải phản ứng lại với các sự kiện xuất hiện
vào các thời điểm thường không biết trước.
− Tính nhanh nhạy: Hệ thống phải xử lý thông tin một cách nhanh chóng để
có thể đưa ra kết quả phản ứng một cách kịp thời. Đây là một đặc điểm tiêu
biểu. Tuy nhiên, đối với một hệ thống có tính năng thời gian thực không
nhất thiết phải đáp ứng thật nhanh mà quan trọng hơn là phải có phản ứng
kịp thời đối với các yêu cầu, tác động từ bên ngoài.
− Tính đồng thời: Hệ thống phải có khả năng phản ứng và xử lý đồng thời
nhiều sự kiện diễn ra.
− Tính tiền định: Dự đoán trước được thời gian phản ứng tiêu biểu, thời gian
phản ứng chậm nhất cũng như trình tự đưa ra các phản ứng. Phải lập lịch
Hình 1.3: Các thành phần của hoạt động thời gian thực
Thông tin
lập lịch
Đồng hồ thời
gian thực
Điều khiển ngắt
Xử lý các yêu cầu
về tài nguyên
Tài nguyên
chờ xử lý
Danh sách
sẵn sàng
Danh sách tài
nguyên có giá trị
Danh sách
xử lý
Lập lịch
Quản lý tài nguyên
Bộ điều vận
Hoạt động
xử lý
Sẵn sàng
xử lý
chậm hơn để tránh mất thông tin. Sự chỉ định tiến trình ưu tiên, thường được yêu
cầu phân tích và mô phỏng nhiều.
1.5 Xử lý thời gian thực
Xử lý thời gian thực (realtime processing) [4] là hình thức xử lý thông tin
trong một hệ thống để đảm bảo tính năng thời gian thực của nó. Như vậy, xử lý
thời gian thực cũng có các đặc điểm tiêu biểu nêu trên như tính bị động, tính
nhanh nhạy, tính đồng thời và tính tiền định. Để có thể phản ứng với nhiều sự Trang 18
kiện diễn ra cùng một lúc, một hệ thống xử lý thời gian thực cần sử dụng các
tiến trình tính toán đồng thời.
Quá trình tính toán là một tiến trình thực hiện một hoặc một phần chương
trình tuần tự do hệ điều hành quản lý trên một máy tính, có thể tồn tại đồng thời
với các quá trình khác trong thời gian thực hiện lệnh và thời gian xếp hàng chờ
thực hiện.
Có ba hình thức tổ chức các quá trình tính toán đồng thời:
− Tính toán tương tranh: Nhiều quá trình tính toán chia sẻ thời gian xử lý
thông tin trên một bộ xử lý.
− Tính toán song song: Các quá trình tính toán được phân chia thực hiện song
song trên nhiều bộ xử lý của một máy tính.
− Tính toán phân tán: Mỗi quá trình tính toán được thực hiện riêng trên một
máy tính.
Trong các hình thức trên đây, hình thức xử lý tương tranh là chủ yếu, nó
tương ứng với trường hợp phổ biến khi hệ thống chỉ có một bộ xử lý. Mặc dù hệ
thống điều khiển có thể có nhiều trạm, và mỗi trạm là một hệ đa bộ xử lý, số
lượng các quá trình tính toán cần thực hiện luôn lớn hơn số lượng các bộ vi xử
lý. Trong khi một Bộ vi xử lý không thể thực hiện song song nhiều lệnh, nó phải
phân chia thời gian để thực hiện xen kẽ nhiều nhiệm vụ khác nhau theo thứ tự
tùy theo mức ưu tiên và phương pháp lập lịch.
Mã thực thi
Sự kiện
Tác vụ sự kiện
Ví dụ:
- Điều khiển trình tự
- Xử lý sự cố
Trang 19
thành vòng điều khiển khép kín và được xử lý tuần hoàn. Kiểu cuối cùng là kiểu
tác vụ sự kiện, nghĩa là mỗi tác vụ sẽ được kích hoạt khi có sự kiện tương ứng
xảy ra.
Trong các hệ thống điều khiển, khái niệm tác vụ hay được sử dụng bên
cạnh quá trình tính toán. Có thể nói, tác vụ là một nhiệm vụ xử lý thông tin trong
hệ thống, được thực hiện theo cơ chế tuần hoàn hoặc theo sự kiện. Các dạng tác
vụ qui định trong chuẩn IEC 61131-3 (Programmable Controllers – Part3:
Programming Languages) được minh họa trên hình 1.4. Ví dụ, một tác vụ thực
hiện nhiệm vụ điều khiển cho một hoặc nhiều mạch vòng kín có chu kỳ trích
mẫu giống nhau. Hoặc, một tác vụ có thể thực hiện nhiệm vụ điều khiển logic,
điều khiển trình tự theo các sự kiện xảy ra. Tác vụ có thể thực hiện dưới dạng
một quá trình tính toán duy nhất, hoặc một dãy các quá trình tính toán khác
nhau.
Hoạt động của hệ thống thời gian thực được xác định thông qua việc xác
định danh sách các kích thích mà hệ thống nhận được, danh sách các đáp ứng,
và thời điểm các đáp ứng cần được sinh ra.
Các kích thích được chia thành hai loại:
1. Kích thích có chu kỳ: Những kích thích này xuất hiện sau mỗi khoảng thời
gian nhất định cho trước. Ví dụ hệ thống có thể kiểm tra một bộ cảm biến,
cứ mỗi lần sau 50 milli giây lại thực hiện một hoạt động (hồi đáp phụ thuộc
tác
Bộ thao
tác
Bộ thao
tác Trang 20
Kích thích có chu kỳ trong hệ thời gian thực thường được tạo ra bằng một
bộ cảm biến gắn trong hệ thống. Các kích thích này cung cấp thông tin trạng thái
về môi trường hệ thống. Chúng điều khiển các hồi đáp tác động tới một tập Bộ
thao tác có nhiệm vụ điều khiển một số đơn vị phần cứng, rồi sau đó Bộ thao tác
làm ảnh hưởng trực tiếp tới môi trường hệ thống.
Kích thích không có chu kỳ có thể sinh ra bởi các Bộ thao tác hay bởi các
bộ cảm biến. Chúng thường chỉ ra một số điều kiện ngoại lệ, như ổ cứng hỏng,
nó cần phải được hệ thống quản lý. Mô hình cảm biến - hệ thống - bộ thao tác
này trong hệ thời gian thực nhúng, được minh họa trong hình 1.5.
1.5.1 Xử lý ngắt
Một đặc trưng hay dùng để phân biệt các hệ thống thời gian thực với các
kiểu hệ thống khác là việc xử lý ngắt. Hệ thống thời gian thực phải đáp ứng với
các kích thích bên ngoài (hay thường gọi là các ngắt) trong một khuôn khổ thời
gian do thế giới bên ngoài ấn định. Bởi vì nhiều kích thích (ngắt) thường xuất
hiện nên phải thiết lập các mức ưu tiên ngắt.
Xử lý ngắt bắt buộc không chỉ lưu trữ thông tin để cho máy tính có thể
chạy lại đúng đắn nhiệm vụ đã bị ngắt trước đó mà còn phải tránh sự tắc nghẽn
và các chu trình vô hạn.
ngắt. Khi hoàn thành xong nhiệm vụ ngắt thì trạng thái của máy lại được khôi
phục và luồng xử lý dở dang (thông thường) lại được tiếp tục.
Trong nhiều tình huống, bản thân dịch vụ ngắt cho một sự kiện có thể lại bị
ngắt bởi một sự kiện khác, có mức ưu tiên cao hơn. Mức ưu tiên ngắt (hình 1.7)
có thể được thiết lập. Nếu một tiến trình có mức ưu tiên thấp ngẫu nhiên được
phép ngắt bởi một tiến trình có mức ưu tiên cao thì có thể khó chạy lại các tiến
trình theo đúng trật tự và có thể làm phát sinh chu trình vô hạn.
Hình 1.7: Ưu tiên ngắt
Ở hình 1.7, các ngắt mức ưu tiên cao hơn được xen vào luồng xử lý của các
ngắt có độ ưu tiên thấp hơn nên các ngắt mức cao được hoàn thành trước và sau
khi hoàn thành nó tiếp tục quay trở lại để thực hiện công việc còn dang dở trước
khi bị ngắt.
Để xử lý ngắt mà vẫn đáp ứng cho các ràng buộc thời gian hệ thống, nhiều
hệ điều hành thời gian thực tiến hành tính toán động để xác định xem mục tiêu
hệ thống đã đạt chưa. Những tính toán động này đều dựa trên tần số trung bình
số lần xuất hiện của sự kiện, khối lượng thời gian cần để phục vụ nó (nếu chúng
có thể được phục vụ), và chương trình có thể ngắt tạm thời ngăn cản chúng phục
vụ.
Nếu các tính toán động chỉ ra rằng, không thể xử lý được các sự kiện xuất
hiện trong hệ thống mà vẫn đáp ứng các ràng buộc thời gian thì hệ thống phải
quyết định theo sơ đồ hành động. Một sơ đồ có thể bao gồm việc đặt dữ liệu vào
bộ đệm để nó có thể được xử lý nhanh chóng khi hệ thống sẵn sàng.
Mức ưu tiên ngắt Thời gian
Dịch vụ ngắt mức 3
Dịch vụ ngắt mức 3
hoàn thành
Luồng xử lý thông
Hình 1.8: Hành động thực thi thời gian thực yêu cầu bắt đầu một tiến trình
Hoạt động quản lý tiến trình định kỳ được chỉ ra ở hình 1.8. Danh sách các
tiến trình định kỳ được Bộ lập lịch kiểm tra và lựa chọn một tiến trình để thực
hiện. Sự lựa chọn này phụ thuộc vào tiến trình ưu tiên, tiến trình định kỳ, thời
gian thực thi mong muốn và giới hạn kết thúc của các tiến trình đã sẵn sàng. Đôi
khi, có hai tiến trình với hai giới hạn khác nhau cần được thực hiện tại cùng một
thời điểm. Trong tình huống này, một tiến trình sẽ được gán một khoảng thời
gian trễ trong giới hạn thời gian của nó.
Nguyên nhân gây ra ngắt của máy tính là điều khiển truyền tới một vị trí
xác định trên bộ nhớ, nó bao gồm một lệnh nhảy tới một dich vụ ngắt thông
thường. Dịch vụ ngắt thường cần đơn giản, ngắn và có số lần thực hiện ít. Khi
một ngắt được phục vụ, những ngắt khác sẽ không thể thực hiện được và sẽ bị
Bộ lập lịch
Chọn tiến trình
để thực hiện
Quản lý tài nguyên
Phân chia bộ nhớ
và bộ xử lý
Bộ điều vận
Bắt đầu thực hiện
trên một bộ xử lý có
giá trị Trang 24
CHƯƠNG 2: PHÁT TRIỂN HỆ THỐNG THÔNG TIN THỜI
GIAN THỰC CHO QUẢN LÝ DỊCH VỤ NHÀ HÀNG
2.1. Khảo sát, phân tích mô hình quản lý dịch vụ nhà hàng và
đề xuất bài toán
2.1.1. Khảo sát hoạt động quản lý dịch vụ nhà hàng
Theo khảo sát trên địa bàn Hà Nội, hầu hết các nhà hàng dịch vụ hiện nay
vẫn sử dụng những quy trình nghiệp vụ thủ công (sử dụng nhân công là chính)
để thực hiện hoạt động kinh doanh của mình. Quy trình nghiệp vụ của các nhà
hàng truyền thống có thể được mô tả tóm tắt qua các giai đoạn chính như sau:
1. Tiếp nhận yêu cầu
2. Chế biến
3. Phục vụ khách
4. Thanh toán
2.1.1.1.
Đây là giai đoạn đầu tiên của hoạt động dịch vụ nhà hàng. Nó bắt đầu khi
khách đến để dùng dịch vụ. Lúc này thường cần nhiều nhân công là các phục vụ
bàn để đáp ứng yêu cầu của khách hàng. Trình tự thực hiện của giai đoạn này
trải qua các bước sau:
(1) Phục vụ bàn chào và đón khách
(2) Phục vụ bàn dẫn khách vào bàn hoặc để khách tự chọn bàn
(3) Phục vụ bàn giới thiệu thực đơn đồ uống và đồ ăn với khách
(4) Phục vụ bàn ghi lại thông tin đặt món vào phiếu yêu cầu.
Thông tin của phiếu yêu cầu thường gồm các khoản mục:
Tên người phục vụ bàn
Số bàn và số lượng khách của bàn đó
Tên mỗi loại đồ ăn/uống và số lượng
Các yêu cầu khác (nếu có)
2.1.1.4. n thanh toán
Khi khách hàng có yêu cầu thanh toán thì phục vụ bàn và thu ngân phải
thực hiện các bước sau:
Copyright: Tài liệu đại học ©