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

Chia sẻ: Lê Trinh Vàng | Ngày: | Loại File: PPT | Số trang:65

Thêm vào BST

Báo xấu

60
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Chöông 5 Ñoàng Boä vaø Giaûi Quyeát Tranh Chaáp (Process Synchronization) -4.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  Monitor Khoa 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û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ë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++; 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
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}  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
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ïn code nhö sau : Do { entry section /* vaøo critical section */ critical section /* truy xuaát döõ lieäu chia seû */ exit section /* rôøi critical section */ remainder section /* laøm nhöõng vieäc khaùc */ } While (1)  Trong moãi process coù nhöõng ñoaïn code coù chöùa caùc thao taùc leân döõ lieäu chia seû. Ñoaïn code naøy ñöôïc goïi laø vuøng tranh chaáp (critical section, CS). Khoa KTMT 10
Vaán ñeà Critical Section  Vaán ñeà Critical Section: phaûi baûo ñaûm söï loaïi tröø töông hoã (mutual exclusion, mutex), töùc laø khi moät process ñang thöïc thi trong vuøng tranh chaáp, khoâng coù process naøo khaùc ñoàng thôøi thöïc thi caùc leänh trong vuøng tranh chaáp. Khoa KTMT 11
Yeâu caàu cuûa lôøi giaûi cho Critical Section Problem • Lôøi giaûi phaûi thoûa ba tính chaát  (1) Mutual exclusion: Khi moät process P ñang thöïc thi trong vuøng tranh chaáp (CS) cuûa noù thì khoâng coù process Q naøo khaùc ñang thöïc thi trong CS cuûa Q.  (2) Progress: neáu khoâng coù process naøo ñang thöïc thi trong vuøng tranh chaáp vaø ñang coù moät soá process chôø ñôïi vaøo vuøng tranh chaáp thì: – Chæ nhöõng process khoâng ñang thöïc thi trong remainder section môùi ñöôïc laø öùng cöû vieân cho vieäc ñöôïc choïn vaøo vuøng tranh chaáp. – Quaù trình choïn löïa naøy khoâng ñöôïc trì hoaõn voâ haïn (postponed indefinitely). • (3) Bounded waiting: Moãi process chæ phaûi chôø ñeå ñöôïc vaøo vuøng tranh chaáp trong moät khoaûng thôøi gian coù haïn ñònh naøo ñoù. Khoâng xaûy ra tình traïng ñoùi taøi nguyeân (starvation). Khoa KTMT 12
Yeâu caàu cuûa lôøi giaûi cho Critical Section Problem - Giaû söû taát caû tieán trình thöïc thi ôû toác ñoä khaùc 0 (nonzero) - Khoâng coù giaû ñònh naøo lieân quan ñeán toác ñoä töông ñoái cuûa n tieán trình Khoa KTMT 13
Phaân loaïi giaûi phaùp  Giaûi phaùp phaàn meàm (software solutions) – user/programmer töï thöïc hieän (thoâng thöôøng seõ coù söï hoã trôï cuûa caùc thö vieän laäp trình) – OS cung caáp moät soá coâng cuï (caùc haøm vaø caáu truùc döõ lieäu) hoã trôï cho programmer qua system calls.  Giaûi phaùp phaàn cöùng (hardware solutions) – Döïa treân moät soá leänh maùy ñaëc bieät Khoa KTMT 14
Giaûi phaùp phaàn meàm  Tröôøng hôïp 2 process ñoàng thôøi: P0 vaø P1 – Giaûi thuaät 1 vaø 2 – Giaûi thuaät 3 (Peterson’s algorithm)  Giaûi thuaät cho n process – Bakery algorithm Khoa KTMT 15
Giaûi thuaät 1  Bieán chia seû • int turn; /* khôûi ñaàu turn = 0 */ • neáu turn = i thì Pi ñöôïc pheùp vaøo critical section, vôùi i = 0 hay 1  Process Pi do { while (turn != i); critical section turn = j; remainder section } while (1);  Thoaû maõn mutual exclusion (1)  Nhöng khoâng thoaû maõn yeâu caàu veà progress (2) vaø bounded waiting (3) vì tính chaát strict alternation cuûa giaûi thuaät Khoa KTMT 16
Giaûi thuaät 1 (tt) Process P0: Process P1: do do while (turn != 0); while (turn != 1); critical section critical section turn := 1; turn := 0; remainder section remainder section while (1); while (1); Ví duï: P0 coù RS (remainder section) raát lôùn coøn P1 coù RS nhoû. Neáu turn = 0, P0 ñöôïc vaøo CS vaø sau ñoù thöïc thi turn = 1 vaø vaøo vuøng RS. Luùc ñoù P1 vaøo CS vaø sau ñoù thöïc thi turn = 0, keá ñoù P1 vaøo vaø xong RS, vaø ñôïi vaøo CS moät laàn nöõa, nhöng vì turn = 0 neân P1 phaûi chôø P0. Khoa KTMT 17
Giaûi thuaät 2  Bieán chia seû • boolean flag[ 2 ]; /* khôûi ñaàu flag[ 0 ] = flag[ 1 ] = false */ • Neáu flag[ i ] = true thì Pi “saün saøng” vaøo critical section.  Process Pi do { flag[ i ] = true; /* Pi “saün saøng” vaøo CS */ while ( flag[ j ] ); /* Pi “nhöôøng” Pj */ critical section flag[ i ] = false; remainder section } while (1);  Baûo ñaûm ñöôïc mutual exclusion. Chöùng minh?  Khoâng thoûa maõn progress. Vì sao? Tröôøng hôïp sau coù theå xaûy ra: • P0 gaùn flag[ 0 ] = true • P1 gaùn flag[ 1 ] = true • P0 vaø P1 loop maõi maõi trong Khoa KTMTvoøng laëp while 18
Giaûi thuaät 3 (Peterson)  Bieán chia seû: keát hôïp caû giaûi thuaät 1 vaø 2  Process Pi , vôùi i = 0 hay 1 do { flag[ i ] = true; /* Process i saün saøng */ turn = j; /* Nhöôøng process j */ while (flag[ j ] and turn == j); critical section flag[ i ] = false; remainder section } while (1);  Thoaû maõn ñöôïc caû 3 yeâu caàu (chöùng minh?) ⇒ giaûi quyeát baøi toaùn critical section cho 2 process. Khoa KTMT 19
Giaûi thuaät Peterson2 process Process P0 Process P1 do { do { /* 0 wants in */ /* 1 wants in */ flag[0] = true; flag[1] = true; /* 0 gives a chance to 1 */ /* 1 gives a chance to 0 */ turn = 1; while (flag[1] && turn = 0; turn == 1); while (flag[0] && critical section turn == 0); /* 0 no longer wants in */ critical section flag[0] = false; /* 1 no longer wants in */ remainder section flag[1] = false; } while(1); remainder section } while(1); Khoa KTMT 20