Bài giảng Hệ điều hành: Chương 5 - ThS. Hà Lê Hoài Thương

Mục tiêu trình bày trong chương 5 Đồng bộ và giải quyết tranh chấp thuộc bài giảng hệ điều hành nhằm trình bày về các kiến thức: tại sao phải đồng bộ và giải quyết tranh chấp, vấn đề Critical section, các giải pháp phần mềm, đồng bộ bằng Critical region, đồng bộ bằng hardware, các bài toán đồng bộ.
Nội dung trích xuất từ tài liệu:
Bài giảng Hệ điều hành: Chương 5 - ThS. Hà Lê Hoài Thương Chöông V - Phaàn IIÑoàng Boä vaø Giaûi Quyeát Tranh Chaáp (Process Synchronization) 1 Noäi dung Ñaët vaán ñeà (taïi sao phaûi ñoàng boä vaø giaûi quyeát tranh chaáp ?) Vaán ñeà Critical section Caùc giaûi phaùp phaàn meàm ‟ Giaûi thuaät Peterson, vaø giaûi thuaät bakery Ñoàng boä baèng hardware Semaphore Caùc baøi toaùn ñoàng boä Critical region MonitorKhoa KTMT 2 Ñaët vaán ñeà„ Khaûo saùt caùc process/thread thöïc thi ñoàng thôøi vaø chia seû döõ lieäu (qua shared memory, file). Neáu khoâng coù söï kieåm soaùt khi truy caäp caùc döõ lieäu chia seû thì coù theå ñöa ñeán ra tröôøng hôïp khoâng nhaát quaùn döõ lieäu (data inconsistency). Ñeå duy trì söï nhaát quaùn döõ lieäu, heä thoáng caàn coù cô cheá baûo ñaûm söï thöïc thi coù traät töï cuûa caùc process ñoàng thôøi. Q p L RKhoa KTMT 3 Baøi toaùn Producer-Consumer Producer-Consumer P không được ghi dữ liệu vào buffer đã đầy C không được đọc dữ liệu từ buffer đang trống P và C không được thao tác trên buffer cùng lúc Giôùi haïn, khoâng giôùi haïn ??? P Buffer (N) CKhoa KTMT 4 Ñaët vaán ñeà Xeùt baøi toaùn Producer-Consumer vôùi bounded buffer Bounded buffer, theâm bieán ñeám count #define BUFFER_SIZE 10 /* 10 buffers */ typedef struct { ... } item; item buffer[BUFFER_SIZE]; int in = 0, out = 0, count = 0;Khoa KTMT 5 Bounded buffer (tt) Quaù trình Producer item nextProduced; while(1) { while (count == BUFFER_SIZE); /* do nothing */ buffer[in] = nextProduced; count++; bieán count ñöôïc chia seû in = (in + 1) % BUFFER_SIZE; giöõa producer vaø consumer } Quaù trình Consumer item nextConsumed; while(1) { while (count == 0); /* do nothing */ nextConsumed = buffer[out] ; count--; out = (out + 1) % BUFFER_SIZE; }Khoa KTMT 6 Bounded buffer (tt) Caùc leänh taêng, giaûm bieán count töông ñöông trong ngoân ngöõ maùy laø:„ (Producer) count++: „ register1 = count „ register1 = register1 + 1 „ count = register1„ (Consumer) count--: „ register2 = count „ register2 = register2 - 1 „ count = register2 Trong ñoù, caùc registeri laø caùc thanh ghi cuûa CPU.Khoa KTMT 7 Bounded buffer (tt)„ Maõ maùy cuûa caùc leänh taêng vaø giaûm bieán count coù theå bò thöïc thi xen keõ Giaû söû count ñang baèng 5. Chuoãi thöïc thi sau coù theå xaûy ra:„ 0: producer register1 := count {register1 = 5} 1: producer register1 := register1 + 1 {register1 = 6} 2: consumer register2 := count {register2 = 5} 3: consumer register2 := register2 - 1 {register2 = 4} 4: producer count := register1 {count = 6} 5: consumer count := register2 {count = 4} Caùc leänh count++, count-- phaûi laø ñôn nguyeân (atomic), nghóa laø thöïc hieän nhö moät leänh ñôn, khoâng bò ngaét nöûa chöøng. Khoa KTMT 8 Bounded buffer (tt) Race condition: nhieàu process truy xuaát vaø thao taùc ñoàng thôøi leân döõ lieäu chia seû (nhö bieán count) ‟ Keát quaû cuoái cuøng cuûa vieäc truy xuaát ñoàng thôøi naøy phuï thuoäc thöù töï thöïc thi cuûa caùc leänh thao taùc döõ lieäu. Ñeå döõ lieäu chia seû ñöôïc nhaát quaùn, caàn baûo ñaûm sao cho taïi moãi thôøi ñieåm chæ coù moät process ñöôïc thao taùc leân döõ lieäu chia seû. Do ñoù, caàn coù cô cheá ñoàng boä hoaït ñoäng cuûa caùc process naøy.Khoa KTMT 9 Vaán ñeà Critical Section Giaû söû coù n process cuøng truy xuaát ñoàng thôøi döõ lieäu chia seû Caáu truùc cuûa moãi process Pi - Moãi process coù ñoaï ...