Giải pháp kỹ thuật trên cơ sở loại trừ tương hỗ hệ thống máy chủ ảo

Nội dung text: Giải pháp kỹ thuật trên cơ sở loại trừ tương hỗ hệ thống máy chủ ảo

1. Tạp chí Khoa học và Công nghệ, Số 38, 2019 GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ HỆ THỐNG MÁY CHỦ ẢO ĐOÀN VĂN THẮNG1, NGUYỄN HÀ HUY CƢỜNG2, VÕ QUANG HOÀNG KHANG1 1 Đại học Công nghiệp TP Hồ chí minh;; 2 Trường Đại học Quảng Nam Trường; vanthangdn@gmail.com - nguyenhahuycuong@gmail.com Tóm tắt. Hệ thống máy chủ ảo đƣợc xây dựng trên nền của hệ thống các máy chủ vật lý phân tán trên bình diện toàn cầu và kết nối với nhau thông qua hệ thống vi n thông c vai tr ngày càng quan trọng trong việc vận hành, cung c p và khai thác tài nguyên ảo h a Đ đảm bảo việc cung c p tài nguyên này m t cách chính xác, k p thời, tránh tình trạng chồng ch o, xung đ t, bế tắc và thiếu thốn vô hạn cho các tiến trình c nhu cầu tài nguyên, đặc biệt tài nguyên ở xa, nh t thiết, phải nghiên cứu và đề xu t các giải pháp đủ mạnh, tin cậy làm nền tảng cơ sở cho hệ điều khi n bên trong các đám mây Trong bài báo này, chúng tôi nghiên cứu thuật toán loại trừ lẫn nhau theo hƣớng tiếp cận Token nhằm tìm ra những giải pháp cung c p tài nguyên phân tán hữu hiệu trong đ nh n mạnh các giải pháp loại trừ lẫn nhau và đề ra các biện pháp tránh đƣợc các v n đề thiếu thốn tài nguyên. Từ khóa. Máy chủ ảo; cung c p tài nguyên. A NEW TECHNICAL ON BASIS MUTUAL EXCLUSION FOR VIRTUALIZATION SYSTEMS Abstract. The virtualization server system is built on the basis of a distributed physical machine system on a global scale and interconnected through a telecommunication system that plays an increasingly important role in the operation and provisioning and exploits virtualization resources. To ensure the timely and accurate resource allocation of this resource, avoid overlapping, conflicting, deadlock and infinite depletion of processes that require resources, particularly remote resources, Necessarily, it is important to research and propose robust, reliable solutions that underpin the control system within the cloud. In this paper, we study the mutually exclusive algorithm in the Token approach to finding effective distributed resource allocation solutions that emphasize mutually exclusive solutions and measures. Avoid the problem of not enough resource hardware from a physical machine. Keywords. Virtualization Server; Mutual Exclusion, Physical Machine, Resource Allocation. 1 MỞ ĐẦU Điện toán Đám mây (ĐTĐM) ngày nay dựa trên sự thay đổi từ mô hình máy tính lớn đến mô hình máy khách chủ Các chi tiết về cơ sở hạ tầng đƣợc trừu tƣợng h a từ phía ngƣời sử dụng, họ không cần biết về hạ tầng công nghệ và nguồn tài nguyên đƣợc truy cập m t cách d dàng trong các đám mây Hầu hết các cơ sở hạ tầng ĐTĐM bao gồm d ch vụ cung c p thông qua trung tâm dữ liệu và xây dựng trên các máy chủ ảo Với sự xu t hiện của nền công nghiệp 4 0 nhu cầu sử dụng nguồn tài nguyên ảo h a này dự báo sẽ tăng lên trong thời gian tới đây V n đề là nguồn tài nguyên ĐTĐM thƣờng xu t hiện nhƣ là đi m truy cập duy nh t của t t cả các máy chủ ĐTĐM Thế nhƣng, ở thời đi m hiện tại mạng vẫn giữ đƣợc vai tr truyền thống của n nhƣ là m t phƣơng tiện trao đổi thông tin và đồng thời, n cũng đƣợc cảm nhận nhƣ là m t phƣơng tiện chia sẻ tài nguyên Xu hƣớng hiện nay cho th y cần phải xây dựng đƣợc các hạ tầng cung c p d ch vụ phải c tính năng vƣợt tr i linh hoạt ở khả năng mở r ng, khả năng phục hồi an ninh và tắc nghẽn mạng, cùng với đ là khả năng về tƣơng tranh xung đ t tài nguyên hữu hạn Công nghệ ảo h a cung c p sự trừu tƣợng và cô lập các chức năng c p th p hơn, cho ph p khả năng di đ ng cao hơn và tập © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh
2. GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ 77 HỆ THỐNG MÁY CHỦ ẢO hợp đƣợc các nguồn tài nguyên vật lý [2] Trong m t môi trƣờng nhƣ ĐTĐM các nguồn tài nguyên phục vụ cho các nhu cầu của khách hàng ngày m t tăng Hiện tại các khách hàng đang chia sẻ các nguồn tài nguyên hữu hạn, chẳng hạn các hệ đa server lồng vào nhau, hệ điều hành và các loại client khác, mỗi phần c cách thức hoạt đ ng cụ th , xác đ nh thứ tự mà trong đ các nguồn tài nguyên đƣợc giao cho tƣng phần Tuy nhiên, tiến trình hoạt đ ng phức tạp trong môi trƣờng phân tán hỗn tạp khách hàng phải cạnh tranh cho m t tập hợp hữu hạn của nguồn tài nguyên Từ những v n đề này đã thúc đẩy các nhà nghiên cứu, các chuyên gia trong lĩnh vực khoa học máy tính luôn nghiên cứu tìm t i các giải pháp nhằm đáp ứng tốt hơn khả năng yêu cầu sử dụng d ch vụ công nghệ thông tin của nhân loại ngày nay Trong n i dung bài báo, chúng tôi trình bày giải pháp với mô hình máy chủ ảo đáp ứng nhu cầu cung c p tài nguyên thông tin, ngăn chặn đƣợc những v n đề tranh ch p trong cung c p tài nguyên V n đề tranhch p trong cung c p tài nguyên trên nền tảng phân tán luôn đƣợc sự quan tâm giải quyết của các nhà nghiên cứu đi trƣớc Tuy nhiên, vẫn c n nhiều v n đề nghiên cứu giải quyết cho thích hợp xu thế tƣơng lai. Trong n i dung nghiên cứu này, chúng tôi cung c p giải pháp kỹ thuật mới trong cung c p tài nguyên cho hệ thống máy chủ ảo dựa trên máy chủ vật lý Giải pháp dựa trên kỹ thuật loại trừ tƣơng hỗ của tác giả Ricart – Agrawala. Chúng tôi phát tri n từ ý tƣởng thuật toán của tác giả, từ đ y đề xu t thuật toán mới gồm ba pha riêng biệt Bố cục bài báo gồm các phần nhƣ sau: phần 2: Trình bày m t số thuật toán học nữa sát và phân cụm dữ liệu; Phần 3: Ứng dụng m t số thuật toán phân loại đối tƣợng vay tín ch p, cuối cùng là kết luận và hƣớng phát tri n 2 CƠ SỞ LÝ THUYẾT 2.1 Petri Nets Petri lƣới (PN) đã đƣợc giới thiệu vào năm 1962 bởi các luận án tiến sĩ của Carl Adams Petri [16], tại Đại học Kỹ thuật Darmstandt, Đức Lý thuyết ban đầu đƣợc phát tri n nhƣ m t cách tiếp cận đ mô hình và phân tích hệ thống thông tin liên lạc Petri Nets (PNs) [14] là m t công cụ mô hình đồ họa và toán học c th đƣợc áp dụng trong m t số loại hệ thống và cho ph p các mô hình song song, đồng thời, không đồng b và hệ thống không xác đ nh K từ khi mô hình này ra đời, nhiều nh m chuyên môn nghiên cứu và đã tiếp tục cải tiến phần mở r ng đƣợc đề xu t cho ph p giới thiệu ngắn gọn hơn và đ trình bày cho các hệ thống tính toán lớn Nhƣ vậy, mạng Petri đơn giản sau đ đã đƣợc áp dụng và mở r ng các hƣớng khác nhau, stochastic, high-level, object-oriented and coloured nets là m t vài ví dụ về các phần mở r ng đƣợc đề xu t. 2.2 Place-transition nets Pertri Net c n đƣợc gọi là Place/Transition Networks (mạng v trí /chuy n tiếp) đƣợc hi n th bằng đ th c hƣớng gồm 2 node Node Transition (node chuy n tiếp) c dạng hình chữ nhật hoặc hình vuông đƣợc dùng đ bi u di n các sự kiện rời rạc c th xảy ra Node Place (node v trí) c dạng hình tr n dùng đ bi u di n trạng thái các điều kiện Pertri là m t trong những lớp nổi bật và nghiên cứu tốt nh t của Petri lƣới, và đôi khi n đƣợc gọi là mạng Petri (PN) Place/Transition mạng Petri là m t đồ th c hƣớng, thƣờng đƣợc đ nh nghĩa nhƣ sau: Định nghĩa 1 Petri net [14] là m t 5-tuple: PN = (P,T,F,W,M0) Trong đ : 1. P = {p1, p2 pm} là tập hữu hạn các place 2. T = {t1,t2, tn} là tập hữu hạn của transition 3 F: (P x T) đƣờng nối từ các input place tới các transition, trong đ N là m t tập hợp các số nguyên (là 0 hoặc 1) Trong trƣờng hợp tổng quát n là các số nguyên không âm N là hàm xác đ nh hƣớng đƣờng nối từ các transition tới các output place 4. W: (P x T) © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh
3. 78 GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ HỆ THỐNG MÁY CHỦ ẢO N trạng thái (marking) ban đầu 5. M0: P Mạng Pertri đƣợc nghiên cứu m t cách r ng rãi trên toàn thế giới, hiện nay c hơn 15 loại Pertri Net khác nhau thƣờng đƣợc phân loại vào m t trong ba nh m sau : - Nh m thứ nh t : là mạng Pertri mô tả bởi các v trí c khả năng bi u di n đúng sai, mỗi v trí đƣợc đánh d u bởi m t thẻ không c c u trúc - Nh m thứ hai : là mạng Pertri mô tả bởi các v trí c khả năng bi u di n giá tr là m t số nguyên - Nh m thứ ba : là mạng Pertri c khả năng bi u di n giá tr ở mức đ cao, chúng đƣợc đánh d u bởi các thẻ d u c c u trúc Các mạng này c th k đến nhƣ Mạng Pertri cao c p với các dữ liệu trừu tƣợng Mạng Pertri suy r ng Trong mạng Pertri suy r ng bao gồm c các mạng : Mạng Pertri tô màu. Mạng Pertri c thời gian. Mạng Pertri c gán nhãn 2.3 Mạng Pertri tô màu Coloured Pertri Net (CPN) Trƣớc khi đ nh nghĩa cho mạng CP – net, chúng ta cần chú thích m t số ký hiệu và thuật ngữ cho (net expressions) bi u thức mạng Các ký hiệu và thuật ngữ đƣợc dùng trong bi u thức nhƣ là tập màu colour, ban đầu marking (đánh d u), bi u thức arc, và guards. - Type(expr) ký hiệu của ki u m t expr cho bi u thức - Var(expr) ký hiệu của tập các biến trong bi u thức expr - Type(v) ký hiệu ki u của biến v - Type(vars),vars là tập của biến, ký hiệu tập của ki u {Type(v)| v vars}. - SSM ký hiệu của tập con của m t tập S - Bool ký hiệu tập boolean, Bool={true,false} Định nghĩa 2 M t Coloured Petri net [14] là m t 9-tuple : CPN = (  , P,T,A,N,C,G,E,I) 1. là tập hữu hạn các ki u không rỗng gọi là Colour Set. 2. P là tập hữu hạn của places 3. T là tập hữu hạn của transitions 4. A là tập hữu hạn của arcs (đƣờng nối) : P  T =P  A=T  A=  . 5. N là chức năng của node N đƣợc đ nh nghĩa từ A P T  T P. 6. C là chức năng của colour N đƣợc đ nh nghĩa từ P và  7. G là chức năng của guard N đƣợc đ nh nghĩa từ T công thức nhƣ sau: t T:[ Type (G(t)) Bool  Type ( V ar( G ( t )))  ]  8. E là chức năng của arc function N đƣợc đ nh nghĩa từ A tới bi u thức nhƣ sau : a A:[ Type (()) E a C (()) p a  Type (ar(())) V E a  ] MS  nơi p(a) là v trí của N(a) 9. I là chức năng của initialisation N đƣợc đ nh nghĩa từ P với bi u thức sau đây: (Vp P :[ Type ( I ( p )) C ( p ) ] MS 2.4 Loại trừ tương hỗ Hệ thống phân tán r ng lớn [6,10] sử dụng công nghệ ảo h a đ cho ph p việc tạo ra các phạm vi năng đ ng hơn, với nguồn tài nguyên ảo c th tính toán đáp ứng đƣợc nhu cầu của ngƣời dùng với các ứng dụng cụ th Tuy nhiên, với số lƣợng ngƣời sử dụng ngày càng tăng lên thì v n đề tranh ch p cùng m t tài nguyên găng không th không xảy ra Ví dụ trong vấn đề tranh chấp lẫn nhau: Các đầu vào là Ti và Ei (0 ≤i≤n–1) © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh
4. GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ 79 HỆ THỐNG MÁY CHỦ ẢO Ti là b xử lý thứ i muốn vào đoạn găng Ei là b xử lý thứ i muốn thoát khỏi đoạn găng Các đầu ra là Ci và Ri (0≤i≤n–1) Ci là b xử lý thứ i c th vào đoạn găng Ri là b xử lý thứ i c th vào đoạn c n lại Điều kiện cho chuỗi sự kiện α các đầu vào và đầu ra: - ∀i (0 ≤i≤n–1) : α|i quay vòng qua Ti, Ci, Ei, Ri theo đúng thứ tự (điều kiện 1 - ràng bu c trên các đầu vào đảm bảo yếu tố tuần tự). - ∀i,j (0 ≤i≠j≤n–1): đầu vào hay đầu ra của j (Cj) ngay trƣớc Ci trong α (điều kiện 2 – đảm bảo chỉ c 1 b xử lý trong 1 thời đi m) Hình 1 Tiến trình cung c p tài nguyên cho ph p loại trừ lẫn nhau Việc chia sẻ tài nguyên và / hoặc dữ liệu đƣợc phổ biến trong nhiều ứng dụng hệ thống, trong đ hầu hết các nguồn tài nguyên và dữ liệu nên đƣợc truy cập m t cách đ c quyền lẫn nhau Nguồn (hoặc biến dữ liệu) c th đƣợc mô hình h a bởi m t nơi với thẻ đại diện cho số lƣợng tài nguyên Nơi đây đƣợc xem là điều kiện trƣớc cho t t cả các quá trình chuy n đổi cần nguồn đ Sau khi sử dụng m t nguồn tài nguyên, n phải đƣợc phát hành Hình 2 mô tả m t ví dụ về m t hệ thống chia sẻ tài nguyên đƣợc truy cập m t cách đ c quyền lẫn nhau. Hình 2 Tiến trình cung c p tài nguyên xung đ t bằng Pertri net 3 GIẢI PHÁP LOẠI TRỪ TƢƠNG HỖ TRONG CUNG CẤP TÀI NGUYÊN CHO HỆ THỐNG MÁY CHỦ ẢO 3.1 Mô hình hệ thống Hệ thống bao gồm N trạm với N = { S1, S2, , Sn} Không m t tính tổng quát, chúng tôi giả đ nh rằng m t tiến trình duy nh t đang chạy trên mỗi trạm Tiến trình tại trạm Si đƣợc ký hiệu là pi T t cả các tiến trình giao tiếp không đồng b trên m t mạng truyền thông M t tiến trình c nhu cầu xâm nhập vào miền găng CS yêu cầu t t cả hoặc m t tập các tiến trình con bằng cách gửi thông điệp Request, và chờ đợi trả lời thích hợp trƣớc khi vào CS Trong khi chờ đợi các tiến trình khác không đƣợc ph p thực hiện các yêu cầu tiếp tục nhập vào miền găng CS M t trạm c th ở m t trong ba trạng thái sau đây: yêu cầu CS, thực thi trong miền găng CS, hoặc không yêu cầu và cũng không thực thi trong CS (tức là, nhàn rỗi) Trong trạng thái yêu cầu, các trạm b chặn và không th thực hiện yêu cầu thêm vào trong CS Trong trạng thái © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh
5. 80 GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ HỆ THỐNG MÁY CHỦ ẢO nhàn rỗi "idle", các trạm đƣợc thực thi bên ngoài CS Trong các thuật toán theo hƣớng Token m t trạm cũng c th c thong tin về trạng thái của trạm giữ thông báo thực hiện bên ngoài CS Tại b t k thời đi m nào, m t trạm cũng c th c m t vài yêu cầu c p phát CS M t trạm khi yêu cầu đƣợc sắp xếp từng tự và chờ phục vụ Chúng tôi đề xu t giải pháp trên cơ sở của thuật toán Ricart–Agrawala. Thuật toán sử dụng hai loại thông điệp REQUEST và REPLY M t tiến trình gửi thông điệp REQUEST cho t t cả các tiến trình khác đ yêu cầu cho ph p đƣợc quyền xâm nhập vào miền găng M t tiến trình gửi thông điệp REPLY đến m t tiến trình đ cho ph p tiến trình đ Tiến trình sử dụng đồng hồ logic Lamport đ gắng nhãn thời gian đ yêu cầu tới miền găng (CS) Nhãn thời gian dùng đ quyết đ nh ƣu tiên các yêu cầu trong trƣờng hợp c xung đ t nếu m t tiến trình pi đang chời thực thi trong miền găng nhận m t thông điệp REQUEST yêu cầu từ tiến trình pj, sau đ nếu thứ tự ƣu tiên của pj’s là sau, thì pi trì hoãn gửi REPLY và gửi thông điệp REPY tới pj chỉ sau khi thực hiện CS cho yêu cầu c p phát Ngƣợc lại, pi gửi thông điệp REPLY cho pj ngay khi n không thực thi trong CS, yêu cầu trƣớc thành công trong việc nhận thông điệp REPLY và đƣợc thực hiện trong CS Mỗi tiến trình pi duy trì m t dãy yêu cầu trì hoãn RDi, kích cỡ của dãy này tƣơng đƣơng với số tiến trình trong hệ thống Bắt đầu,ij: RDi[j]=0. Khi mà tiến trình pi trì hoãn gửi yêu cầu tới pj, n xác lập RDi[j]=1 và sau đ n gửi thông báo REPLY tới pj, n xác lập RDi[j]=0 3.2 Giới thiệu về thuật toán loại trừ tƣơng hỗ Loại trừ tƣơng hỗ c th đƣợc điều khi n trên m t trạm trung tâm c nhiệm vụ nhận t t cả các thông điệp và khuyến ngh giải ph ng Trạm này duy trì m t hàng đợi, sắp xếp các yêu cầu theo trật tự đến và phục vụ cho từng thông điệp m t trong trật tự Phân tán giải thuật này k o theo việc phân tán các chức năng cung c p mà cần phải điều khi n hàng đợi trên trạm Do vậy, m t trạm chuyên cho việc tiếp nhận các yêu cầu và các khuyến ngh giải ph ng từ t t cả các trạm c n lại M t trật tự giống trên các trạm chỉ đạt đƣợc, nếu ta áp dụng d u trong các thông điệp bởi các đồng hồ logic truyền và đánh số các trạm Quan hệ trật tự toàn b đƣợc đ nh nghĩa Thêm vào đ , đ cho m t trạm c th ra quyết đ nh bằng việc tham chiếu duy nh t vào hàng đợi của mình n c n cần phải đƣợc nhận m t thông điệp của từng trạm khẳng đ nh rằng không c thông điệp nào trƣớc các thông điệp khác mà c n đang quá cảnh trên đƣờng Thuật toán loại trừ tƣơng hỗ Ricart – Agrawala c th mô tả nhƣ sau Thuật toán Ricart – Agrawala Giai đoạn: Yêu cầu trong miền găng Bƣớc 1 Khi m t trạm Si muốn vào trong đoạn găng CS, n gửi gửi quảng bá m t thông điệp REQUEST c gán nhãn thời gian tới t t cả các trạm khác Thông điệp c điệp c dạng (T,Hi,i), trong đ Hi là d u của thông điệp c nghĩa là đồng hồ logic của n và T c th nhận m t trong ba giá tr là REQ, REL, ACQ. Bƣớc 2 Khi trạm Sj nhận m t thông điệp REQUEST từ trạm Si, n gửi m t thông điệp REPLY tới trạm Si nếu trạm Sj không yêu cầu hoặc không thực thi trong miền găng CS, hoặc nếu trạm Sj là đang yêu cầu và Si’s yêu cầu với nhãn thời gian là nhỏ hơn trạm Sj’s Nếu không, trả lời trì hoãn và Sj xác lập RDj[i]=1. Giai đoạn: Thực thi trong miền găng Bƣớc 3 Trạm Si vào trong miền găng sau khi n nhận đƣợc thông điệp REPLY từ trạm mà n gửi thông điệp REQUEST Giai đoạn: Khôi phục trong miền găng Bƣớc 4 Khi trạm Si thoát khỏi miền găng CS, n gửi t t cả thông điệp REPLY: j nếu RDi[j] =1, thì n gửi thông điệp REPLY tới Sj và xác lập RDi[j]:=0. Ý tƣởng giải thuật Start 1. ; 2. ; 3. If then © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh
6. GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ 81 HỆ THỐNG MÁY CHỦ ẢO 4. ; 5. await 6. goto start; 7. Fi; 8. ; 9. If then 10. ; 11. For j:=1 to N 12. Do wait od 13. If then 14. Await ; 15. Goto start; 16. Fi; 17. Fi; 18. Critical section; 19. ; 20. ; 3.3 Kiểm nghiệm giải thuật Các yêu cầu vào đoạn găng đƣợc xử lý theo trật tự FIFO và theo quan hệ Đ chứng minh cho điều đ ta lƣu ý rằng khi trạm Si quyết đ nh vào đoạn găng, n không th đƣa và trong mạng yêu cầu REQUEST nào trƣớc trong bối cảnh sau Thực tế, khi trạm Si vào đoạn găng c nghĩa là n đã nhận thông điệp từ t t cả các trạm khác và t t cả các thông điệp đều sau REQUEST của riêng n Ta ki m tra các đặc tính sau đây: o Trạm Si đang ở trong đoạn găng là trạm duynhaats nằm trong đoạn găng y Thực tế cho th y thông điệp REQUEST đƣợc phát bởi Si vẫn tiếp tục tồn tại trong t t cả các hàng đợi cho đến khi n đƣợc thay thế bởi thông điệp REL o Trạm nào đã yêu cầu vào đoạn găng phải đảm bảo thời hạn và phải ra khỏi đoạn găng sau m t khoản thời gian xác đ nh Ví dụ 1: Chúng ta x t m t mạng bao gồm 3 trạm, trong đ c hai trạm 1 và 2 yêu cầu vào đoạn găng tại thời đi m 2 của đồng hồ logic của chúng Tập hợp các thông điệp đƣợc mô tả nhƣ hình sau: Hình 3 Loại trừ tƣơng hỗ nhờ d u © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh
7. 82 GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ HỆ THỐNG MÁY CHỦ ẢO 4 MÔ PHỎNG VÀ ĐÁNH GIÁ KẾT QUẢ Chúng tôi sử dụng phần mềm mô phỏng Coloured Petri net 4 0 0 Đƣợc cài đặt trên máy Laptop Lenovo; Chipset Intel coreTMi5 M t số kết quả mô phỏng với mô hình CPN cho thuật toán loại trừ lẫn nhau với thuật Ricart – Agrawala. Hình 4 Mô hình mô phỏng với thuật toán Ricart – Agrawala Hình 5 M t số yêu cầu mô phỏng Coloured Pertri Net Trên hình 5 chúng tôi sử dụng 15 v trí Place với công cụ Pertri Net chúng tôi c đƣợc kết quả yêu cầu mô phỏng nhƣ trên với tỷ lệ trung bình của các tokens tại các v trí giao đ ng từ 0,0396 tới 0,14851 Và đ tin cậy tại các v trí (Place) từ 0,01452 tới 0,04493 Hình 6 Trạng thái của hệ thống phân tích Yêu cầu phân tích về không gian trạng thái của mạng Pertri net nhƣ trên hình 6 © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh
8. GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ 83 HỆ THỐNG MÁY CHỦ ẢO Hình 8 Phân bổ trạng thái của hệ thổng phân tích Phân bố trạng thái của hệ thống đƣợc đánh d u từ M0 tới M15 Với dữ liệu M0 là 0 16667 và M15 là 0.10427. Hình 8 Xác xu t của Token tại các v trí Trên hình 8 mật đ xác xu t của các Token tại các v trí (Place) với =0 các v t P0,P1 c giá tr th p nh t là 0 83333 mật đ xác xu t cao nh t tại P15, P12 c giá tr là 0,97917 Khi giá tr =1 mật đ xác xu t tại v trí P5,P6 là th p nh t c giá tr là 0 0625 c n giá tr cao nh t tại v trí P8,P13 là 0 10417 © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh
9. 84 GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ HỆ THỐNG MÁY CHỦ ẢO 5 KẾT LUẬN Qua kết quả kết quả mô phỏng và phân tích đánh giá ƣu nhƣợc đi m của thuật toán đề xu t này chúng ta nhận th y rằng thuật toán vừa nêu c những ƣu đi m hơn so với thuật toán đã đề xu t Lamport trƣớc đây Với thuật toán Lamport và thuật toán Ricart – Agrawala với yêu cầu (N-1) thông điệp REQUEST và RELASE và đ tr của thuật toán là T Tuy nhiên đối với thuật toán Ricart – Agrawala là 2(N-1) thông điệp cho mỗi CS gọi còn Lamport là 3(N-1). Nhƣ vậy, quá trình mô hình h a hệ thống phân tán máy chủ ảo giải ứng dụng thuật toán giải quyết v n đề loại trừ tƣơng hỗ với bằng Petri Net chúng tôi nhận th y kết quả mô phỏng phù hợp với yêu cầu đề ra Dựa trên kết quả này chúng ta ccos th mở r ng cho các hệ thống phức tạp hơn Và giải quyết đƣợc các v n đề trong cung c p tài nguyên phân tán Hiện nay c nhiều công cụ đ chuy n mô hình hệ thống Petri Net sang chƣơng trình với các ngôn ngữ lập trình thông dụng nhƣ Java điều này giúp ta d dàng phát tri n hệ thống sau khi mô hình h a với Petri Net TÀI LIỆU THAM KHẢO [1] D P Mitchell and M J Merritt, “A distributed algorithm for deadlock detection and resolution,” in Proc.ACM Symposium on Principles of Distributed Computing, 1984, pp. 282–284. [2] E.Knapp. (1987), Deadlock Detection in Distributed Database Systems, ACM Computing Surveys, Vol.19, No. 4 pp.303-327. [3] M,Singhal.(1989), Deadlock detection in distributed systems. IEEE Computer, Vol.22, pp. 37–48. [4] A.D.Kshemkalyani, and M.Singhal. (1999), A One-Phase Algorithm to Detect Distributed Deadlocks in Replicated Databases, IEEE Trans. Knowledge and Data Eng., vol. 11, No. 6, pp. 880-895. [5] W Voorsluys, S Garg, and R Buyya, “Provisioning spot market cloud resources to create cost-effective virtual clusters,” in Proceedings of the 11th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP). Los Alamitos, CA, USA: IEEE Comput. Soc., 2011. [6] R Buyya, R Ranjan, and R Calheiros, “Modeling and simulation of scalable cloud computing environments and the cloudsim toolkit: Challenges and opportunities,” inProceeding of the 7th International Conference on High Performance Computing & Simulation (HPCS). Los Alamitos, CA, USA: IEEE Comput. Soc., 2009, pp. 1–11. [7] D Feitelson, “Parallel workloads archive,” cs huji ac il/labs/parallel/workload [8] D Tsafrir, Y Etsion, and D G Feitelson, “Modeling User Runtime Estimates,” in In Processing of the 11th Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP) . Springer-Verlag, 2005, pp.1–35. [9] Binildas CA, Malhar Barai, Vincenzo Caselli, Service Oriented Architecture with Java (Using SOA and Web Services to build powefull Java applications), PACKT Publishing, 2008. [10] Ian Foster, Yong Zhao, Ioan Raicu, Shiyong Lu, Cloud Computing and Grid Computing 360-Degree Compared, Grid Computing Environments Workshop, 2008. [11] Rajkumar Buyya, Chee Shin Yeo, and Srikumar Venugopal, Market-Oriented Cloud Computing: Vision, Hype, and Reality for Delivering IT Services as Computing Utilities, International Conference on High Performance Computing, 2008. [12] M Andreolini, S Casolari, M Colajani, and M Messori, “Dynamic load management of virtual machines in a cloud architectures,” in CLOUDCOMP, 2009 [13] D. Prangchumpol, S. Sanguansintukul, and P Tantasanaw, “Analyzing User Behavior from Server Logs for Improved Virtualization Management”,2009 © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh
10. GIẢI PHÁP KỸ THUẬT TRÊN CƠ SỞ LOẠI TRỪ TƢƠNG HỖ 85 HỆ THỐNG MÁY CHỦ ẢO [14] M Stillwell, D Schanzenbach, F Vivien, and H Casanova, “Resource allocation algorithms for virtualized service hosting platforms,”, JPDC, vol 70, no 9, pp 962-974, 2010. [15] A Kshemkalyani, M Singhak, “Deadlock Detection in Distributed systems”, in Distributed Algorithms, 2010 – 2011. Ngày nhận bài:24/10/2018 Ngày chấp nhận đăng:10/02/2019 © 2019 Trƣờng Đại học Công nghiệp thành phố Hồ Chí Minh