Bài giảng Hệ điều hành - Chương 3: Đồng bộ và giải quyết tranh chấp - Thoại Nam

Nội dung text: Bài giảng Hệ điều hành - Chương 3: Đồng bộ và giải quyết tranh chấp - Thoại Nam

1. Khaùi nieäm cô baûn ‰ Caùc process/thread thöïc thi ñoàng thôøi chia seû code, chia seû döõ lieäu (qua shared memory, file). ‰ Neáu khoâng coù söï ñieàu khieån khi truy caäp caùc döõ lieäu chia seû thì coù theå xaûy ra tröôøng hôïp khoâng nhaát quaùn döõ lieäu (data inconsistent). ‰ Ñ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ù thöù töï cuûa caùc process ñoàng thôøi. ‰ Ví duï Bounded-Buffer (ch.4) theâm bieán ñeám count #define BUFFER_SIZE 10 # typedef struct { } item; item buffer[BUFFER_SIZE]; int in = 0, out = 0, count = 0; Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -3- Bounded Buffer (t.t) ‰ Producer item nextProduced; while (1){ while ( count == BUFFER_SIZE ); /* do nothing */ buffer[in] = nextProduced; count++; in = (in + 1) % BUFFER_SIZE; } ‰ Consumer item nextConsumed; while (1){ while ( count == 0 ); /* do nothing */ buffer[in] = nextConsumed; count ; out = (out + 1) % BUFFER_SIZE; } Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -4- 2
2. Critical Section ‰ Giaû söû coù n process cuøng truy xuaát ñoàng thôøi döõ lieäu chia seû ‰ Khoâng phaûi taát caû caùc ñoaïn code ñeàu phaûi ñöôïc quan taâm giaûi quyeát vaán ñeà race condition maø chæ nhöõng ñoaïn code coù chöùa caùc thao taùc treân döõ lieäu chia seû. Ñoaïn code naøy ñöôïc goïi laø vuøng tranh chaáp - critical section (CS). ‰ Vaán ñeà ñaët ra: phaûi baûo ñaûm raèng khi moät process ñang thöïc thi trong vuøng tranh chaáp, khoâng coù moät process naøo khaùc ñöôïc pheùp thöïc thi caùc leänh trong vuøng tranh chaáp ⇒ mutual exclusion (mutex): söï loaïi tröø töông hoã. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -7- Critical Section vaø Mutual Exclusion A: enter(critical_section) A: leave(critical_section) Process A B attem ps to enter CS B: enter(critical_section) Process B B blocked B: leave(critical_section) Time t1 t2 t3 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8- 4
3. 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 » Interrupt disable, Test-and-Set Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -11- Giaûi phaùp phaàn meàm ‰ Tröôøng hôïp 2 process ñoàng thôøi – Giaûi thuaät 1 vaø 2 – Giaûi thuaät 3 (Peterson’s algorithm) ‰ Giaûi thuaät toång quaùt cho n process – Bakery algorithm Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -12- 6
4. Giaûi thuaät 2 ‰ Bieán chia seû – boolean flag[2]; /* khôûi ñaàu flag [0] = flag [1] = false. */ –Neáuflag [i] = true ⇒ Pi saün saøng vaøo critical section ‰ Process Pi do { flag[i] := true; while (flag[j]) ; Critical_Section(); flag [i] = false; Remainder_Section(); } while (1); ‰ Baûo ñaûm ñöôïc mutual exclusion. Chöùng minh? ‰ Khoâng thoaû maõn progress. Vì sao? Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -15- Giaûi thuaät 3 (Peterson) ‰ Bieán chia seû: keát hôïp caû giaûi thuaät 1 vaø 2. ‰ Process Pi do { flag [i]:= true; turn = 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 Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -16- 8
5. Giaûi thuaät 3: Tính ñuùng ñaén (t.t) – Neáu Pj ñaõ baät flag[j]=true vaø ñang chôø taïi while() thì coù chæ hai tröôøng hôïp laø turn=i hoaëc turn=j – Neáu turn=i thì Pi vaøo CS. Neáu turn=j thìPjvaøoCS nhöng seõ baät flag[ j]=false khi thoaùt ra ⇒ cho pheùp Pi vaøo CS – Nhöng neáu Pj coù ñuû thôøi gian baät flag[ j]=true thì Pj cuõng phaûi gaùn turn=i – Vì Pi khoâng thay ñoåi trò cuûa bieán turn khi ñang keït trong voøng laëp while(), Pi seõ chôø ñeå vaøo CS nhieàu nhaát laø sau moät laàn Pj vaøo CS (bounded waiting) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -19- Tröôøng hôïp process bò “cheát” ‰ Neáu thoûa ñoàng thôøi 3 yeâu caàu (mutex, progress, bounded waiting) thì giaûi phaùp giaûi quyeát tranh chaáp coù khaû naêng phaùt hieän moät process bò “cheát” taïi nhöõng vuøng khoâng coù tranh chaáp (remainder section) – Khi ñoù, process bò “cheát” taïi caùc vuøng khoâng tranh chaáp cuõng coù nghóa laø coù moät remainder section daøi voâ haïn. ‰ Khoâng coù giaûi phaùp naøo coù theå cung caáp cô cheá ñuû maïnh ñeå giaûi quyeát tröôøng hôïp process bò “cheát” beân trong critical section (CS) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -20- 10
6. Töø software ñeán hardware ‰ Khuyeát ñieåm cuûa caùc giaûi phaùp software – Caùc process khi yeâu caàu ñöôïc vaøo vuøng tranh chaáp ñeàu phaûi lieân tuïc kieåm tra ñieàu kieän (busy waiting), tieâu toán laõng phí nhieàu thôøi gian xöû lyù cuûa CPU – Neáu thôøi gian xöû lyù trong vuøng tranh chaáp lôùn, moät giaûi phaùp hieäu quaû neân coù cô cheá block caùc process ñang ñôïi. ‰ Caùc giaûi phaùp phaàn cöùng (hardware) – Caám ngaét (disable interrupts) – Duøng caùc leänh ñaëc bieät Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -23- Caám ngaét ‰ Trong heä thoáng uniprocessor: mutual exclusion ñöôïc baûo Process Pi: ñaûm tuy nhieân hieäu suaát thöïc thibògiaûmsuùtvìkhicoù repeat process trong CS, chuùng ta disable_interrupts(); khoâng theå thöïc hieän caùch Critical_Section(); thöïc thi xen keõ ñoái vôùi caùc enable_interrupts(); process ñang ôû vuøng khoâng coù tranh chaáp (non-CS). Remainder_Section() ‰ Treân heä thoáng multiprocessor: forever mutual exclusion khoâng ñöôïc ñaûm baûo – CS coù tính atomic nhöng khoâng mutual exclusive Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -24- 12
7. Leänh test-and-set (t.t) ‰ Mutual exclusion ñöôïc baûo ñaûm: neáu Pi vaøo CS, caùc process Pj khaùc ñeàu ñang busy waiting ‰ Khi Pi ra khoûi CS, quaù trình choïn löïa process Pj vaøo CS keá tieáp laø tuyø yù ⇒ khoâng baûo ñaûm ñieàu kieän bounded waiting. Do ñoù coù theå xaûy ra starvation (bò boû ñoùi) ‰ Caùc processor (ví duï Pentium) thoâng thöôøng cung caáp moät leänh ñôn laø swap(a,b) coù taùc duïng hoaùn chuyeån noäi dung cuûa a vaø b. – swap(a,b) cuõng coù öu nhöôïc ñieåm nhö test-and-set Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -27- Swap vaø Mutual Exclusion ‰ Bieán chia seû lock ñöôïc khôûi ‰ Bieán chia seû (khôûi taïo laø false) taïo giaù trò false bool lock; ‰ Moãi process Pi coù bieán cuïc boä bool waiting[n]; key ‰ Process P ‰ Process Pi naøo thaáy giaù trò i lock=false thì ñöôïc vaøo CS. do { – Process Pi seõ loaïi tröø caùc process Pj khaùc khi thieát laäp key = true; lock=true while (key == true) void Sw ap(boola, boolb) Swap(lock,key); { critical section boolean tem p = a; lock = false; remainder section a = b; } b = tem p; } Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -28- 14
8. Semaphore ‰ Laø coâng cuï ñoàng boä cung caáp bôûi OS maø khoâng ñoøi hoûi busy waiting ‰ Semaphore S laø moät bieán soá nguyeân, ngoaøi thao taùc khôûi ñoäng bieán thì chæ coù theå ñöôïc truy xuaát qua hai taùc vuï coù tính ñôn nguyeân (atomic) vaø loaïi tröø (mutual exclusive) – wait(S) hay coøn goïi laø P(S): giaûm giaù trò semaphore. Neáu giaù trò naøy aâm thì process thöïc hieän leänh wait() bò blocked. – signal(S) hay coøn goïi laø V(S): taêng giaù trò semaphore. Neáu giaù trò naøy aâm, moät process ñang blocked bôûi moät leänh wait() seõ ñöôïc hoài phuïc ñeå thöïc thi. ‰ Traùnh busy waiting: khi phaûi ñôïi thì process seõ ñöôïc ñaët vaøo moät blocked queue, trong ñoù chöùa caùc process ñang chôø ñôïi cuøng moät söï kieän. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -31- Hieän thöïc Semaphore ‰ Ñònh nghóa semaphore nhö moät record typedefstru c t { intvalue; structprocess *L ; /* process queue */ } sem aphore; ‰ Giaû söû coù hai taùc vuï ñôn: – block: taïm treo process naøo thöïc thi leänh naøy. – wakeup(P): hoài phuïc quaù trình thöïc thi cuûa moät process P ñang blocked . Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -32- 16
9. Hieän thöïc Mutex vôùi Semaphore ‰ Duøng cho n process ‰ Shared data: semaphore mutex; ‰ Khôûi taïo S.value = 1 /*initially mutex.value = 1*/ ‰ Chæ duy nhaát moät 1 ‰ Process Pi: process ñöôïc vaøo CS (mutual exclusion) do { wait(mutex); ‰ Ñeå cho pheùp k process critical section vaøo CS, khôûi taïo S.value = k signal(mutex); remainder section } while (1); Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -35- Ñoàng boä process baèng semaphore ‰ Hai process: P1 vaø P2 ‰ Ñeå ñoàng boä hoaït ñoäng theo yeâu caàu, P1 phaûi ñònh nghóa nhö sau: ‰ Yeâu caàu: leänh S1 trong P1 caàn ñöôïc thöïc thi S1; tröôùc leänh S2 trong P2 signal(synch); ‰ Vaø P2 ñònh nghóa nhö sau: ‰ Ñònh nghóa semaphore “synch” duøng ñoàng boä wait(synch); S2; ‰ Khôûi ñoäng semaphore: synch.value= 0 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -36- 18
10. Deadlock vaø Starvation ‰ Deadlock – hai hay nhieàu process ñang chôø ñôïi voâ haïn ñònh moät söï kieän khoâng bao giôø xaûy ra (vd: söï kieän do moät trong caùc process ñang ñôïi taïo ra). ‰ Goïi S vaø Q laø hai bieán semaphore ñöôïc khôûi taïo = 1 P0 P1 P(S); P(Q); P(Q); P(S); MM V(S); V(Q); V(Q) V(S); ‰ Starvation (indefinite blocking) coù theå xaûy ra khi chuùng ta boû process vaøo haøng ñôïi vaø laáy ra theo cô cheá LIFO. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -39- Caùc loaïi semaphore ‰ Counting semaphore: moät soá nguyeân coù giaù trò khoâng haïn cheá. ‰ Binary semaphore: moät soá nguyeân coù giaù trò naèm trong khoaûng [0,1]. Binary semaphore raát deã hieän thöïc. ‰ Chuùng ta coù theå hieän thöïc counting semaphore S baèng binary semaphore. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -40- 20
11. Baøi toaùn “Dining Philosopher” ‰ 5 trieát gia ngoài aên vaø suy nghó ‰ Moãi ngöôøi caàn 2 chieác ñuõa ñeå aên ‰ Treân baøn chæ coù 5 ñuõa ‰ Baøi toaùn naøy minh hoaï söï khoù khaên trong vieäc phaân phoái taøi nguyeân giöõa caùc ‰Döõ lieäu chia seû: process sao cho khoâng semaphore chopstick[5]; xaûy ra deadlock vaø starvation ‰Khôûi ñaàu caùc bieán ñeàu laø 1 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -43- Baøi toaùn “Dining Philosopher” Trieát gia thöù i: do { wait(chopstick[i]) wait(chopstick[ (i+1) % 5 ] ) eat signal(chopstick[i]); signal(chopstick[ (i+1) % 5] ); think } while (1); Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -44- 22
12. Baøi toaùn Readers-Writers (t.t) ‰ mutex: baûo veä bieán readcount ‰ wrt – Baûo ñaûm mutual exclusion ñoái vôùi caùc writer – Ñöôïc söû duïng bôûi reader ñaàu tieân hoaëc cuoái cuøng vaøo hay ra khoûi vuøng tranh chaáp. ‰ Neáu moät writer ñang ôû trong CS vaø coù n reader ñang ñôïi thì moät reader ñöôïc xeáp trong haøng ñôïi cuûa wrt vaø n-1 reader kia trong haøng ñôïi cuûa mutex ‰ Khi writer thöïc thi signal(wrt), chuùng ta coù theå phuïc hoài thöïc thi cuûa moät trong caùc reader ñang ñôïi hoaëc writer ñang ñôïi ⇒ döïa vaøo scheduler Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -47- Caùc vaán ñeà vôùi semaphore ‰ Semaphore cung caáp moät coâng cuï maïnh meõ ñeå baûo ñaûm mutual exclusion vaø phoái hôïp ñoàng boä caùc process ‰ Tuy nhieân, caùc taùc vuï wait(S) vaø signal(S) naèm raûi raùc ôû raát nhieàu processes ⇒ khoù naém baét ñöôïc hieäu öùng cuûa caùc taùc vuï naøy. Neáu khoâng söû duïng ñuùng ⇒ coù theå xaûy ra tình traïng deadlock hoaëc starvation. ‰ Moät process bò “die” coù theå keùo theo caùc process khaùc cuøng söû duïng bieán semaphore. signal(mutex) wait(mutex) signal(mutex) critical section critical section critical section wait(mutex) wait(mutex) signal(mutex) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -48- 24
13. Monitor ‰ Cuõng laø moät caáu truùc ngoân ngöõ caáp cao (high-level language construct) töông töï CR, coù chöùc naêng nhö semaphore nhöng deã ñieàu khieån hôn ‰ Xuaát hieän trong nhieàu ngoân ngöõ laäp trình ñoàng thôøi nhö – Concurrent Pascal, Modula-3, uC++, Java ‰ Coù theå hieän thöïc baèng semaphore (!!!) shared data Entry queue operations initialization code Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -51- Monitor ‰ Laø moät module phaàn meàm trong ñoù bao goàm – Moät hoaëc nhieàu thuû tuïc/haøm (procedure) – Moät ñoaïn code khôûi taïo (initialization code) – Caùc bieán döõ lieäu cuïc boä (local data variable) ‰ Ñaëc tính cuûa monitor: – Local variable chæ coù theå truy xuaát bôûi caùc thuû tuïc cuûa monitor – Process vaøo monitor baèng caùch goïi moät trong caùc thuû tuïc ñoù – Chæ coù moät process coù theå vaøo monitor taïi moät thôøi ñieåm ⇒ Mutual Exclusion ñöôïc baûo ñaûm ‰ Hieän thöïc monitor (tham khaûo taøi lieäu) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -52- 26
14. Monitor coù condition variable shared data entrance queue a b ª Caùc process coù theå ñôïi ôû entrance queue hoaëc ñôïi ôû caùc condition queue (a, b, ) ª Khi thöïc hieän leänh cwait(a), process seõ ñöôïc chuyeån vaøo condition queue a operations ª Leänh csignal(a) chuyeån moät process trong condition queue a vaøo monitor initialization ª Do ñoù, process goïi csignal(cn) code seõ bò blocked vaø ñöôïc ñöa vaøo urgent queue Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -55- Monitor coù condition variable entrance queue m onitor waiting area entrance MONITOR local data condition c1 conditional variable cw ait(c1) Procedure 1 condition cn cw ait(cn) Procedure k urgent queue initialization code csignal exit Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -56- 28
15. Dining Philosopher (t.t) void pickup(int i) { state[i] = hungry; test[i]; if (state[i] != eating) self[i].wait(); } void putdown(int i) { state[i] = thinking; // test left and right neighbors test((i+4) % 5); test((i+1) % 5); } Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -59- Dining Philosopher (t.t) void test(int i) { if ( (state[(I + 4) % 5] != eating) && (state[i] == hungry) && (state[(i + 1) % 5] != eating)) { state[i] = eating; self[i].signal(); } } ‰ Tröôùc khi aên, moãi trieát gia phaûi goïi haøm pickup(), aên xong roài thì phaûi goïi haøm putdown() dp.pickup(i); /* yum yum yum */ dp.putdown(i); Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -60- 30