Bài giảng Hệ điều hành - Chương 4: Đồng bộ hóa tiến trình

Chia sẻ: Hkmghnjm Hkmghnjm | Ngày: | Loại File: PDF | Số trang:85

Thêm vào BST

Báo xấu

424
lượt xem 79
download

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

Nội dung bài giảng trong chương 4 Đồng bộ hóa tiến trình thuộc bài giảng Hệ điều hành nêu các nội dung chính xử lý đồng hành các vấn đề: vấn đề tranh đoạt điều khiển, vấn đề phối hợp xử lý; bài toán đồng bộ hóa; các giải pháp đồng bộ hóa; các bài toán đồng bộ hóa kinh điển.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Hệ điều hành - Chương 4: Đồng bộ hóa tiến trình

Baøi giaûng 4 Ñoàng boä hoaù tieán trình 10/28/2005 Trần Hạnh Nhi 1
Noäi dung baøi giaûng Xöû lyù ñoàng haønh vaø caùc vaán ñeà: Vaán ñeà tranh ñoaït ñieàu khieån (Race Condition) Vaán ñeà phoái hôïp xöû lyù Baøi toaùn ñoàng boä hoùa Yeâu caàu ñoäc quyeàn truy xuaát (Mutual Exclusion) Yeâu caàu phoái hôïp xöû lyù (Synchronization) Caùc giaûi phaùp ñoàng boä hoaù Busy waiting Sleep & Wakeup Caùc baøi toaùn ñoàng boä hoaù kinh ñieån Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 2
Nhieàu tieán trình “chung soáng hoaø bình” trong heä thoáng ? ÑÖØNG HY VOÏNG An toaøn khi caùc tieán trình hoaøn toaøn ñoäc laäp Laøm sao coù ñöôïc ?? Thöïc teá Caùc tieán trình chia seû taøi nguyeân chung ( file system, CPU...) Concurrent access => bugs. Ví duï : Deâ con qua caàu Xöû lyù ñoàng haønh = ...nhöùc ñaàu 10/28/2005 Trần Hạnh Nhi 3
Caùc vaán ñeà Tranh chaáp Nhieàu tieán trình truy xuaát ñoàng thôøi moät taøi nguyeân mang baûn chaát khoâng chia seû ñöôïc Xaûy ra vaán ñeà tranh ñoaït ñieàu khieån (Race Condition) Keát quaû ? Khoù bieát , thöôøng laø ...sai Luoân luoân nguy hieåm ? ...Khoâng, nhöng ñuû ñeå caân nhaéc kyõ caøng Phoái hôïp Caùc tieán trình khoâng bieát töông quan xöû lyù cuûa nhau ñeå ñieàu chænh hoaït ñoäng nhòp nhaøng Caàn phoái hôïp xöû lyù (Rendez-vous) Keát quaû : khoù bieát, khoâng baûo ñaûm aên khôùp 10/28/2005 Trần Hạnh Nhi 4
Noäi dung baøi giaûng Xöû lyù ñoàng haønh vaø caùc vaán ñeà: Vaán ñeà tranh ñoaït ñieàu khieån (Race Condition) Vaán ñeà phoái hôïp xöû lyù Baøi toaùn ñoàng boä hoùa Yeâu caàu ñoäc quyeàn truy xuaát (Mutual Exclusion) Yeâu caàu phoái hôïp xöû lyù (Synchronization) Caùc giaûi phaùp ñoàng boä hoaù Busy waiting Sleep & Wakeup Caùc baøi toaùn ñoàng boä hoaù kinh ñieån Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 5
Tranh ñoaït ñieàu khieån (Race condition) - Ví duï Ñeám soá ngöôøi vaøo Altavista : duøng 2 threads caäp nhaät bieán ñeám hits=> P1 vaø P2 chia seû bieán hits hits = 0 P1 P2 hits = hits +1; hits = hits + 1; Keát quaû cuoái cuøng laø bao nhieâu ? 10/28/2005 Trần Hạnh Nhi 6
Tranh ñoaït ñieàu khieån (Race condition) - Ví duï hits = 0 P1 P2 time (1) read hits (0) (2)read hits (0) (3) hits = 0 + 1 (4)hits = 0 + 1 hits = 1 10/28/2005 Trần Hạnh Nhi 7
Tranh ñoaït ñieàu khieån (Race condition) - Ví duï hits = 0 P1 P2 time (1) read hits (0) (2) hits = 0 + 1 (3) read hits (1) hits = 2 (4) hits = 1 + 1 10/28/2005 Trần Hạnh Nhi 8
Tranh ñoaït ñieàu khieån (Race condition) - Ví duï (tt) i=0; Thread a: Thread b: while(i < 10) while(i > -10) i = i +1; i = i - 1; print “A won!”; print “B won!”; Ai thaéng ? Coù baûo ñaûm raèng seõ coù ngöôøi thaéng ? Neáu moãi tieán trình xöû lyù treân 1 CPU thì sao ? 10/28/2005 Trần Hạnh Nhi 9
Tranh ñoaït ñieàu khieån (Race condition)-Nhaän xeùt Keát quaû thöïc hieän tieán trình phuï thuoäc vaøo keát quaû ñieàu phoái Cuøng input, khoâng chaéc cuøng output Khoù debug loãi sai trong xöû lyù ñoàng haønh Xöû lyù Laøm lô Deã , nhöng coù phaûi laø giaûi phaùp Khoâng chia seû taøi nguyeân chung : duøng 2 bieán hits1,hits2; xaây caàu 2 lane... Neân duøng khi coù theå, nhöng khoâng bao giôø coù theå ñaûm baûo ñuû taøi nguyeân, vaø cuõng khoâng laø giaûi phaùp ñuùng cho moïi tröôøng hôïp Giaûi phaùp toång quaùt : coù hay khoâng ? Lyù do xaûy ra Race condition ? Bad interleavings : moät tieán trình “xen vaøo” quaù trình truy xuaát taøi nguyeân cuûa moät tieán trình khaùc Giaûi phaùp : baûo ñaûm tính atomicity cho pheùp tieán trình hoaøn taát troïn veïn quaù trình truy xuaát taøi nguyeân chung tröôùc khi coù tieán trình khaùc can thieäp 10/28/2005 Trần Hạnh Nhi 10
Atomicity : loaïi boû Race Condition hits = 0 P1 P2 time read hits (0) hits = 0 + 1 read hits(1) hits = 1 + 1 hits = 2 10/28/2005 Trần Hạnh Nhi 11
Mieàn gaêng (Critical Section) & Khaû naêng ñoäc quyeàn (Mutual Exclusion) Mieàn gaêng (CS) laø ñoaïn chöông trình coù khaû naêng gaây ra hieän töôïng race condition P1 P2 printf(“Welcome”); printf(“Welcome”); CS hits = hits + 1 hits = hits + 1 CS printf(“Bye”); printf(“Bye”); Hoã trôï Atomicity : Caàn baûo ñaûm tính “ñoäc quyeàn truy xuaát” (Mutual Exclusion) cho mieàn gaêng (CS) 10/28/2005 Trần Hạnh Nhi 12
Noäi dung baøi giaûng Xöû lyù ñoàng haønh vaø caùc vaán ñeà: Vaán ñeà tranh ñoaït ñieàu khieån (Race Condition) Vaán ñeà phoái hôïp xöû lyù Baøi toaùn ñoàng boä hoùa Yeâu caàu ñoäc quyeàn truy xuaát (Mutual Exclusion) Yeâu caàu phoái hôïp xöû lyù (Synchronization) Caùc giaûi phaùp ñoàng boä hoaù Busy waiting Sleep & Wakeup Caùc baøi toaùn ñoàng boä hoaù kinh ñieån Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 13
Phoái hôïp hoaït ñoäng P2 P1 (2) Send(“yeâu”); (1) Send(“Anh”); P3 P4 (3) Send(“em”); (4) Send(“Khoâng”); 10/28/2005 Trần Hạnh Nhi 14
Chuyeän gì ñaõ xaûy ra ? P1 P3 (1) Send(“Anh”); (3) Send(“em”); P2 P4 (2) Send(“yeâu”); (4) Send(“Khoâng”); P3 P2 (3) printf(“em”); (2) Send(“yeâu”); P4 P1 (4) Send(“Khoâng”); (1)Send(“Anh”);
Phoái hôïp xöû lyù P1 P2 Job1; Job2; Laøm theá naøo baûo ñaûm trình töï thöïc hieän Job1 - Job2 ? P1 vaø P2 thöïc hieän “heïn hoø” (Rendez-vous) vôùi nhau Hoã trôï Rendez-vous : Baûo ñaûm caùc tieán trình phoái hôïp vôùi nhau theo 1 trình töï xöû lyù ñònh tröôùc. 10/28/2005 Trần Hạnh Nhi 16
Noäi dung baøi giaûng Xöû lyù ñoàng haønh vaø caùc vaán ñeà: Vaán ñeà tranh ñoaït ñieàu khieån (Race Condition) Vaán ñeà phoái hôïp xöû lyù Baøi toaùn ñoàng boä hoùa Yeâu caàu ñoäc quyeàn truy xuaát (Mutual Exclusion) Yeâu caàu phoái hôïp xöû lyù (Synchronization) Caùc giaûi phaùp ñoàng boä hoaù Busy waiting Sleep & Wakeup Caùc baøi toaùn ñoàng boä hoaù kinh ñieån Producer – Consumer Readers – Writers Dinning Philosophers 10/28/2005 Trần Hạnh Nhi 17
Baøi toaùn ñoàng boä hoaù (Synchronization) Nhieàu tieán trình chia seû taøi nguyeân chung ñoàng thôøi : Tranh chaáp Race Condition Nhu caàu “ñoäc quyeàn truy xuaát” (Mutual Exclusion) Caùc tieán trình phoái hôïp hoaït ñoäng : Töông quan dieãn tieán xöû lyù ? Nhu caàu “hoø heïn” (Rendez-vous) Thöïc hieän ñoàng boä hoaù : Laäp trình vieân ñeà xuaát chieán löôïc Caùc tieán trình lieân quan trong baøi toaùn phaûi toân troïng caùc luaätñoàng boä Giaûi phaùp söû duïng caùc cô cheá ñoàng boä : Do laäp trình vieân /phaàn cöùng / HÑH / NNLT cung caáp 10/28/2005 Trần Hạnh Nhi 18
Moâ hình ñaûm baûo Mutual Exclusion Nhieäm vuï cuûa laäp trình vieân: Theâm caùc ñoaïn code ñoàng boä hoùa vaøo chöông trình goác Theâm theá naøo : xem moâ hình sau ... Kieåm tra vaø daønh quyeàn vaøo CS CS; Töø boû quyeàn söû duïng CS 10/28/2005 Trần Hạnh Nhi 19
Moâ hình toå chöùc phoái hôïp giöõa hai tieán trình Nhieäm vuï cuûa laäp trình vieân: Theâm caùc ñoaïn code ñoàng boä hoùa vaøo 2 chöông trình goác Theâm theá naøo : xem moâ hình sau ... P1 P2 Job1; Chôø ; Baùo hieäu ; Job2; Nhieàu tieán trình hôn thì sao ? Khoâng coù moâ hình toång quaùt Tuøy thuoäc baïn muoán heïn hoø ra sao ☺ 10/28/2005 Trần Hạnh Nhi 20