hệ điều hành 1 - Chương 5: Đồng Bộ và Giải Quyết Tranh Chấp

Khảo sát các process/thread thực thi đồng thời và chia sẻ dữ liệu (qua shared memory, file).Nếu không có sự kiểm soát khi truy cập các dữ liệu chia sẻ thì có thể đưa đến ra trường hợp không nhất quán dữ liệu (data inconsistency).Để duy trì sự nhất quán dữ liệu, hệ thống cần có cơ chế bảo đảm sự thực thi có trật tự của các process đồng thời.
Nội dung trích xuất từ tài liệu:
hệ điều hành 1 - Chương 5: Đồng Bộ và Giải Quyết Tranh Chấp Chöông5 ÑoàngBoävaøGiaûiQuyeátTranhChaáp(ProcessSynchronization) -4.1- Noäidung Ñ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 Monitor Khoa KTMT 2 Ñaëtvaá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ûmsöï thöïc thi coù traät töï cuûa caùc process ñoàng thôøi. Q p L R Khoa 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 P Buffe Buffe r(N) r(N) C Khoa KTMT 4 Ñaëtvaá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 Boundedbuffer(tt) Quaù trình Producer item nextProduced; while(1) { while (count == BUFFER_SIZE); /* do nothing */ buffer[in] = nextProduced; count++; in = (in + 1) % BUFFER_SIZE; } bieán count ñöôïc chia seû Quaù trình Consumer giöõa producer vaø consumer item nextConsumed; while(1) { while (count == 0); /* do nothing */ nextConsumed = buffer[out] ; count--; out = (out + 1) % BUFFER_SIZE; } Khoa KTMT 6 Boundedbuffer(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 Boundedbuffer(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:=register21 {register2 = 4} 4: producer count:=register1 {count = 6} Caû 5: hai process thao consumer count:=register taùc ñoàng thôøi2 leân bieán chung {count = 4} count. Trò cuûa bieán chung naøy khoâng nhaát quaùn döôùi caùc thao taùc cuûa hai process. Giaûi phaùp: 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 Khoa bò ngaét KTMT nöûa chöøng. 8 Boundedbuffer(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àCriticalSection 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 proc ...