Tìm hiểu thuật toán lomet trong cung cấp tài nguyên dùng chung phục vụ hệ thống máy chủ ảo của điện toán đám mây.

- 1 -

LỜI CAM ĐOAN

Tôi xin cam đoan :

1. Những nội dung trong luận văn này là do tôi thực hiện dưới sự

hướng dẫn trực tiếp của PGS.TS Lê Văn Sơn.

2. Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng tên

tác giả, tên công trình, thời gian, địa điểm công bố.

3. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá,

tôi xin chịu hoàn toàn trách nhiệm.

Sinh viên

Nguyễn Trọng Tiệp

- 2 -

LỜI CẢM ƠN

Để hoàn thành khóa luận tốt nghiệp này, tôi đã nhận đƣợc sự hƣớng dẫn

tận tình ngay từ những ý tƣởng cơ bản ban đầu của thầy giáo PGS.TS Lê Văn

Sơn; cùng với sự giúp đỡ, động viên của các thầy cô giáo trong khoa Tin học

trƣờng Đại học Sƣ Phạm – Đại học Đà Nẵng, những ngƣời đã tận tình dạy dỗ,

truyền lại cho chúng tôi kiến thức và những bài học kinh nghiệm quý giá. Bên

cạnh đó tôi cũng nhận đƣợc sự giúp đỡ từ các thầy cô trong khoa Tin học, và

các anh, chị, bạn bè giúp đỡ tôi trong khóa luận tốt nghiệp này.

Tôi xin chân thành cảm ơn thầy giáo PGS.TS Lê Văn Sơn là ngƣời trực

tiếp hƣớng dẫn tôi trong khóa luận này – thầy đã hƣớng dẫn rất tận tình, thầy

đã góp ý ngay cả những việc nhỏ nhất.

Tôi cũng xin chân thành cảm ơn tới thầy Đặng Hùng Vỹ đã giúp đỡ tôi

trong quá trình xây dựng ý tƣởng về chƣơng trình ứng dụng cho đề tài.

Và cuối cùng tôi xin chân thành cảm ơn tới các thầy cô giáo trong khoa

Tin học trƣờng Đại học Sƣ Phạm – Đại học Đà Nẵng cùng các anh, chị và các

bạn trong lớp cũng nhƣ ngoài lớp đã nhiệt tình giúp đỡ tôi hoàn thành tốt

khóa luận này.

- 3 -

MỤC LỤC

LỜI CAM ĐOAN....................................................................................................1

LỜI CẢM ƠN .........................................................................................................2

MỤC LỤC ..............................................................................................................3

DANH MỤC CÁC HÌNH VẼ .................................................................................5

MỞ ĐẦU ................................................................................................................7

Chƣơng 1: BẾ TẮC VÀ CÁC CHIẾN LƢỢC CUNG CẤP TÀI NGUYÊN TRONG

HỆ PHÂN TÁN ....................................................................................................11

1.1. MỘT SỐ KHÁI NIỆM.............................................................................11

1.2. BẾ TẮC (DEADLOCK) TRONG VIỆC CUNG CẤP TÀI NGUYÊN

DÙNG CHUNG. ...............................................................................................13

1.3. CHIẾN LƢỢC CUNG CẤP TÀI NGUYÊN. ...........................................15

1.3.1. Cung cấp tài nguyên duy nhất.........................................................15

1.3.2. Cung cấp một tập hợp các tài nguyên. Vấn đề bế tắc ......................18

Chƣơng 2: TỔNG QUAN VỀ THUẬT TOÁN LOMET .......................................22

2.1. CÁC PHƢƠNG PHÁP CUNG CẤP SỬ DỤNG TRẠNG THÁI TỔNG

QUÁT ...............................................................................................................22

2.2. THUẬT TOÁN LOMET..........................................................................25

2.2.1. Vị trí của vấn đề. ............................................................................25

2.2.2. Nguyên lý và thuyết minh phƣơng pháp .........................................27

2.2.3. Thuật toán ......................................................................................28

Chƣơng 3: XÂY DỰNG ỨNG DỤNG BÀI TOÁN BÃI ĐỔ XE....................30

3.1. GIỚI THIỆU BÀI TOÁN.........................................................................30

3.2. GIẢI PHÁP TRONG BÀI TOÁN ............................................................32

3.3. PHÂN TÍCH ỨNG DỤNG.......................................................................33

3.3.1. Mô hình use-case (Hình 3.3)...........................................................33

3.3.2. Đặc tả chức năng của client ............................................................33

3.3.3. Đặc tả chức năng của các server .....................................................37

3.4. XÂY DỰNG ỨNG DỤNG ......................................................................44

3.4.1. Xây dựng client ..............................................................................44

3.4.2. Xây dựng server .............................................................................45

- 4 -

3.5. CÀI ĐẶT ỨNG DỤNG............................................................................47

3.5.1. Client..............................................................................................47

3.5.2. Server.............................................................................................51

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN..............................................................57

DANH MỤC TÀI LIỆU THAM KHẢO ...............................................................58

- 5 -

DANH MỤC CÁC HÌNH VẼ

Số hiệu

hình vẽ

Tên hình vẽ Trang

Hình 1.1 Bế tắc giao thông tại ngã tƣ 13

Hình 1.2 Đồ thị cung cấp tài nguyên bị bế tắc 14

Hình 1.3 Đồ thị truy cập vào tài nguyên bằng server duy nhất 16

Hình 1.4

Đồ thị truy cập vào tài nguyên bằng một chƣơng trình trực

duy nhất

17

Hình 1.5 Truy cập trực tiếp vào các server 17

Hình 2.1 Vòng khép kín trên đồ thị 25

Hình 2.2 Đồ thị G1 trên trạm S1 26

Hình 2.3 Đồ thị G2 trên trạm S2 26

Hình 2.4 Đồ thị G3 trên trạm S3 26

Hình 2.5 Phát sinh bế tắc 26

Hình 2.6 Trạng thái cung cấp tài nguyên trên 3 trạm 28

Hình 3.1 Mô phỏng bãi đậu xe 30

Hình 3.2 Mô phỏng bãi đậu xe trong mạng máy tính 31

Hình 3.3 Minh họa mô hình use-case của ứng dụng 33

Hình 3.4 Biểu đồ hoạt động chức năng đăng kí 34

Hình 3.5

Biểu đồ hoạt động chức năng yêu cầu ra khỏi bãi đậu

xe

35

Hình 3.6

Biểu đồ hoạt động chức năng yêu cầu xem thông tin

trong bãi

37

Hình 3.7 Biểu đồ hoạt động chức năng của các server 37

Hình 3.8 Mô hình vòng tròn ảo 38

Hình 3.9 Cấu trúc thông điệp 39