Bài giảng Hệ điều hành: Chương 3 - Thoại Nam, Lê Ngọc Minh

pdf
Số trang Bài giảng Hệ điều hành: Chương 3 - Thoại Nam, Lê Ngọc Minh 30 Cỡ tệp Bài giảng Hệ điều hành: Chương 3 - Thoại Nam, Lê Ngọc Minh 380 KB Lượt tải Bài giảng Hệ điều hành: Chương 3 - Thoại Nam, Lê Ngọc Minh 1 Lượt đọc Bài giảng Hệ điều hành: Chương 3 - Thoại Nam, Lê Ngọc Minh 17
Đánh giá Bài giảng Hệ điều hành: Chương 3 - Thoại Nam, Lê Ngọc Minh
5 ( 22 lượt)
Nhấn vào bên dưới để tải tài liệu
Đang xem trước 10 trên tổng 30 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

Chöông 3 Ñoàng boä vaø giaûi quyeát tranh chaáp (Process Synchronization) -1- Noäi dung Khaùi nieäm cô baûn ‰ Baøi toaùn “Critical-Section” ‰ Caùc giaûi phaùp phaàn meàm ‰ – Peterson, Bakery Ñoàng boä baèng hardware ‰ Semaphore ‰ Caùc baøi toaùn ñoàng boä ‰ Critical Region ‰ Monitor ‰ Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt -2- 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt -4- 2 Race Condition ‰ Race condition: nhieàu process truy xuaát vaø thao taùc ñoàng thôøi treân döõ lieäu chia seû. – 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. ‰ Chuùng ta caàn baûo ñaûm sao cho taïi moãi thôøi ñieåm coù moät vaø chæ moät process ñöôïc truy xuaát, thao taùc treâ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. ‰ ‰ Caùc leänh taêng, giaûm bieán töông ñöông trong ngoân ngöõ maùy laø: (P) count ++; – register1 := count – register1 := register1 +1 – count := register1 ‰ (C) count --; – register2 := count – register2 := register2 -1 – count := register2 ‰ Trong ñoù, registeri laø caùc thanh ghi cuûa CPU. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -5- Ví duï veà Race Condition ‰ Quaù trình thöïc hieän xen keõ cuûa leänh taêng/giaûm bieán count ‰ Hieän taïi: count = 5 0: producer register1 := count 1: producer register1 := register1+1 2: consumer register2 := count 3: consumer register2 := register2-1 4: producer count := register1 5: consumer count := register2 0 {register1 = 5} {register1 = 6} {register2 = 5} {register2 = 4} {count = 6} {count = 4} Caû hai process thao taùc ñoàng thôøi treân bieán chung count. Keát quaû cuûa bieán chung naøy khoâng nhaát quaùn döôùi caùc thao taùc cuûa hai process ⇒ leänh count++, count-- phaûi laø atomic, nghóa laø thöïc hieän nhö moät leänh ñôn, khoâng bò ngaét nöûa chöøng. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt -6- 3 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 enterC S B :enter(critical_section) Process B B blocked B :leave(critical_section) Tim e t1 t2 t3 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt -8- 4 Caáu truùc toång quaùt Giaû söû moãi process thöïc thi bình Moät soá giaû ñònh: thöôøng (i.e, nonzero speed) vaø ‰ Coù theå coù nhieàu CPU nhöng khoâng cho pheùp coù nhieàu taùc khoâng coù söï töông quan giöõa toác vuï truy caäp moät vò trí trong boä ñoä thöïc thi cuûa caùc process nhôù cuøng luùc (simultaneous) ‰ Caáu truùc toång quaùt cuûa moät ‰ Khoâng raøng buoäc veà thöù töï process: thöïc thi cuûa caùc process ‰ Caùc process coù theå chia seû DO { moät soá bieán chung nhaèm muïc entry section ñích ñoàng boä hoaït ñoäng cuûa chuùng. critical section ‰ Giaûi phaùp cuûa chuùng ta caàn exit section phaûi ñaëc taû ñöôïc caùc phaàn remainder section entry section vaø exit section. ‰ } WHILE (1); Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -9- Raøng buoäc cuûa baøi toaùn tranh chaáp ‰ Mutual Exclusion – Taïi moãi thôøi ñieåm, chæ coù moät process ñöôïc pheùp thöïc thi trong vuøng tranh chaáp (CS) ‰ 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 phaûi ñang thöïc thi trong vuøng khoâng tranh chaáp môùi ñöôïc laø öùng cöû vieân cho vieäc choïn process naøo ñöôïc vaøo vuøng tranh chaáp keá tieáp. – Quaù trình choïn löïa naøy khoâng ñöôïc trì hoaõn voâ haïn (postponed indefinitely) ‰ Bounded Waiting – Moãi process chæ phaûi chôø trong ñeå ñöôïc vaøo vuøng tranh chaáp trong moät khoaûng thôøi gian naøo ñoù. Khoâng ñeå xaûy ra tình traïng “ñoùi taøi nguyeân” (starvation) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt -10- 5 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt -12- 6 Giaûi thuaät 1 ‰ Bieán chia seû – int turn; /* khôûi ñaàu turn = 0 */ – neáu turn = i ⇒ Pi ñöôïc pheùp vaøo critical section ‰ Process Pi do { while (turn != i) ; Critical_Section(); turn = j; Remainder_Section(); } while (1); ‰ ‰ Thoaû maõn mutual exclusion (1) Khoâng thoaû maõn yeâu caàu progress (2) vaø boundedwaiting (3) vì tính chaát strict alternation. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -13- Giaûi thuaät 1 (t.t) Process P0: do while(turn !=0 ); Critical_Section(); turn:=1; Remainder_Section(); Process P1: do while(turn!=1); Critical_Section(); turn:=0; Remainder_Section(); while (1); while (1); Ví duï: P0 coù RS raát lôùn vaø P1 coù RS nhoû. Neáu turn=0, P0 ñöôïc vaøo CS vaø sau ñoù thöïc thi vuøng RS (turn=1). Ñeán P1 vaøo CS vaø sau ñoù thöïc thi RS (turn=0) vaø tìm caùch vaøo CS moät laàn nöõa nhöng yeâu caàu bò töø choái !!! P1 phaûi chôø P0 !!!. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt -14- 7 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 ⇒ 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt -16- 8 Giaûi thuaät Peterson-2 process PROCESS P0 DO { flag[0]:=true; /* 0 wants in */ PROCESS P1 DO { flag[1]:=true; /* 1 wants in */ turn:= 1; turn:=0; /* 0 gives a chance to 1 */ /* 1 gives a chance to 0 */ WHILE ( flag[1] && turn=1 ); CRITICAL_SECTION; flag[0]:=false; WHILE ( flag[0] && turn=0 ); CRITICAL_SECTION; flag[1]:=false; /* 0 no longer wants in */ /* 1 no longer wants in */ REMAINDER_SECTION; WHILE (1); REMAINDER_SECTION; WHILE (1); Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -17- Giaûi thuaät 3: Tính ñuùng ñaén ‰ Mutual exclusion ñöôïc baûo ñaûm bôûi vì – P0 vaø P1 ñeàu ôû trong CS neáu vaø chæ neáu flag[0] = flag[1] = true vaø chæ neáu turn = i vôùi moãi Pi (khoâng theå xaûy ra) ‰ Chöùng minh thoaû yeâu caàu veà progress vaø bounded waiting – Pi khoâng theå vaøo CS neáu vaø chæ neáu bò keït taïi voøng laëp while() vôùi ñieàu kieän flag[j] = true vaø turn = j. – Neáu Pj khoâng muoán vaøo CS thì flag[j] = false vaø do ñoù Pi coù theå vaøo CS. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt -18- 9 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ì Pj vaøo CS 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt -20- 10
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.