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

 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 
 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 
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 
 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 
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 
 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 
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 
 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