Bài giảng Hệ điều hành (Operating Systems): Chương 5, 6, 7, 8 - TS. Vũ Đức Lung

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

Thêm vào BST

Báo xấu

80
lượt xem 10
download

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

Bài giảng Hệ điều hành (Operating Systems) - Chương 5, 6, 7, 8 gồm có những nội dung chính như: Đồng bộ và giải quyết tranh chấp (Process Synchronization), tắc nghẽn(Deadlock), quản lý bộ nhớ, bộ nhớ ảo. Mời các bạn cùng tham khảo.

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 (Operating Systems): Chương 5, 6, 7, 8 - TS. Vũ Đức Lung

Chương V-I: Liên lạc giữa các Tiến Trình Nhu Cầu Liên Lạc Q Chia sẻ thông tin p L CƠ CHẾ ? R Phối hợp tăng tốc độ xử lý TRAO ĐỔI THÔNG VẤNTIN ĐỀGIỮA CÁC TIẾN TRÌNH GIẢI JOB ? PHÁP ? p L Q Khoa KTMT Vũ Đức Lung 1 Khoa KTMT Vũ Đức Lung 2 Các Cơ Chế Liên Lạc Các Cơ Chế Liên Lạc Signal : Không truyền được dữ liệu Pipe Tín hiệu Mô tả SIGINT Người dùng nhấn phím DEL để ngắt xử lý tiến Truyền dữ liệu không cấu trúc trình SIGQUIT Yêu cầu thoát xử lý SIGILL Tiến trình xử lý một chỉ thị bất hợp lệ SIGKILL Yêu cầu kết thúc một tiến trình SIGFPT Lỗi floating – point xảy ra ( chia cho 0) SIGPIPE Tiến trình ghi dữ liệu vào pipe mà không có reader SIGSEGV Tiến trình truy xuất đến một địa chỉ bất hợp lệ SIGCLD Tiến trình con kết thúc SIGUSR1 Tín hiệu 1 do người dùng định nghĩa SIGUSR2 Tín hiệu 2 do người dùng định nghĩa Các tín hiệu được gửi đi bởi?khi nhận thì xử lý ra sao? Khoa KTMT Vũ Đức Lung 3 Khoa KTMT Vũ Đức Lung 4 Các Cơ Chế Liên Lạc Các Cơ Chế Liên Lạc Shared Memory Message Mâu thuẫn truy xuất => nhu cầu đồng bộ hoá Liên lạc trên môi trường phân tán Liên kết tiềm ẩn Send(message) : gởi một thông điệp Receive(message) : nhận một thông điệp Liên kết tường minh Send(destination, message) : gởi một thông điệp đến destination Receive(source,message) : nhận một thông điệp từ source Khoa KTMT Vũ Đức Lung 5 Khoa KTMT Vũ Đức Lung 6 1
Các Cơ Chế Liên Lạc Các Cơ Chế Liên Lạc Socket: là một thiết bị truyền thông hai chiều như tập tin Để thực hiện liên lạc bằng socket, cần tiến hành các thao tác :: Mỗi Socket là một thành phần trong một mối nối giữa các máy Tạo lập hay mở một socket trong mạng Gắn kết một socket với một địa chỉ Liên lạc : có hai kiểu liên lạc tùy thuộc vào chế độ nối kết: Các thuộc tính của socket: Liên lạc trong chế độ không liên kết Domaine: định nghĩa dạng thức địa chỉ và các nghi thức sử dụng. Có Liên lạc trong chế độ nối kết nhiều domaines, ví dụ UNIX, INTERNET, XEROX_NS, ... Hủy một socket Type: định nghĩa các đặc điểm liên lạc a) độ tin cậy b) độ bảo toàn thứ tự dữ liệu VD: Giao tiếp trong TCP c) Lặp lại dữ liệu d) Chế độ nối kết e) Bảo toàn giới hạn thông điệp f) Khả năng gởi thông điệp khẩn Khoa KTMT Vũ Đức Lung 7 Khoa KTMT Vũ Đức Lung 8 Race condition Vùng tranh chấp (Miền găng - critical section) P11 và P22 chia sẻ biến chung hits P2 P1 hits = 0 P1 P2 read hits time CS read hits read hits hits = hits + 1 CS read hits hits = hits + 1 hits =hits + 1 hits = hits + 1 hits = 1, 2 ? CS là đoạn chương trình có khả năng gây ra hiện tượng race condition Kết quả cuối cùng không dự đoán được ! Khoa KTMT Vũ Đức Lung 9 Khoa KTMT Vũ Đức Lung 10 Giải pháp tổng quát Mô hình đảm bảo độc quyền truy xuất hits = 0 P1 P2 time Kiểm tra và dành quyền vào CS hits = hits + 1 CS; hits = hits + 1 Từ bỏ quyền sử dụng CS hits = 2 Bảo đảm tính “độc quyền truy xuất” miền găng tại một thời điểm Khoa KTMT Vũ Đức Lung 11 Khoa KTMT Vũ Đức Lung 12 2
Hẹn hò Giải pháp P1 P2 P1 P2 Job1; Job2; Job1; Job2; Làm thế nào bảo đảm trình tự thực hiện Job11 - Job22 ? Hai tiến trình cần trao đổi thông tin về diễn tiến xử lý Khoa KTMT Vũ Đức Lung 13 Khoa KTMT Vũ Đức Lung 14 Mô hình tổ chức phối hợp hoạt động giữa hai tiến trình P1 P2 Job1; Chờ ; Báo hiệu ; Job2; Khoa KTMT Vũ Đức Lung 15 3
Noäi dung Chöông V - Phaàn II Ñaët vaán ñeà (taïi sao phaûi ñoàng boä vaø giaûi quyeát tranh chaáp ?) Ñ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 (Process Synchronization) – 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 1 Khoa KTMT 2 Ñaët vaán ñeà Baøi toaùn Producer-Consumer • Khaûo saùt caùc process/thread thöïc thi ñoàng thôøi vaø chia Producer--Consumer seû döõ lieäu (qua shared memory, file). P không được ghi dữ liệu vào buffer đã đầy Neáu khoâng coù söï kieåm soaùt khi truy caäp caùc döõ lieäu chia C không được đọc dữ liệu từ buffer đang trống seû thì coù theå ñöa ñeán ra tröôøng hôïp khoâng nhaát quaùn döõ P và C không được thao tác trên buffer cùng lúc 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ûm söï thöïc thi coù traät töï cuûa caùc process ñoàng thôøi. Giôùi haïn, khoâng giôùi haïn ??? Q P Buffer Buffer (N) (N) C p L R Khoa KTMT 3 Khoa KTMT 4 Ñaët vaán ñeà Bounded buffer (tt) Xeùt baøi toaùn Producer-Consumer vôùi bounded buffer Quaù trình Producer Bounded buffer, theâm bieán ñeám count item nextProduced; while(1) { #define BUFFER_SIZE 10 /* 10 buffers */ while (count == BUFFER_SIZE); /* do nothing */ buffer[in] = nextProduced; typedef struct { count++; ... bieán count ñöôïc chia seû in = (in + 1) % BUFFER_SIZE; giöõa producer vaø consumer } item; } item buffer[BUFFER_SIZE]; Quaù trình Consumer item nextConsumed; int in = 0, out = 0, count = 0; while(1) { while (count == 0); /* do nothing */ nextConsumed = buffer[out] ; count--; out = (out + 1) % BUFFER_SIZE; } Khoa KTMT 5 Khoa KTMT 6 1
Bounded buffer (tt) Bounded buffer (tt) Caùc leänh taêng, giaûm bieán count töông ñöông trong ngoân • Maõ maùy cuûa caùc leänh taêng vaø giaûm bieán count coù theå bò thöïc thi xen ngöõ maùy laø: keõ Giaû söû count ñang baèng 5. Chuoãi thöïc thi sau coù theå xaûy ra: • (Producer) count++: • • register1 = count 0: producer register1 := count {register1 = 5} • register1 = register1 + 1 1: producer register1 := register1 + 1 {register1 = 6} • count = register1 2: consumer register2 := count {register2 = 5} 3: consumer register2 := register2 - 1 {register2 = 4} • (Consumer) count--: 4: producer count := register1 {count = 6} • register2 = count 5: consumer count := register2 {count = 4} • register2 = register2 - 1 • count = register2 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 Trong ñoù, caùc registeri laø caùc thanh ghi cuûa CPU. bò ngaét nöûa chöøng. Khoa KTMT 7 Khoa KTMT 8 Bounded buffer (tt) Vaán ñeà Critical Section Race condition: nhieàu process truy xuaát vaø thao taùc Giaû söû coù n process cuøng truy xuaát ñoàng thôøi döõ lieäu ñoàng thôøi leân döõ lieäu chia seû (nhö bieán count) 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 Caáu truùc cuûa moãi process Pi- Moãi process coù ñoaïn thöù töï thöïc thi cuûa caùc leänh thao taùc döõ lieäu. code nhö sau : Do { Ñeå döõ lieäu chia seû ñöôïc nhaát quaùn, caàn baûo ñaûm entry section /* vaøo critical section */ critical section /* truy xuaát döõ lieäu chia xeû */ sao cho taïi moãi thôøi ñieåm chæ coù moät process ñöôïc exit section /* rôøi critical section */ thao taùc leân döõ lieäu chia seû. Do ñoù, caàn coù cô cheá remainder section /* laøm nhöõng vieäc khaùc */ ñoàng boä hoaït ñoäng cuûa caùc process naøy. } 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 9 Khoa KTMT 10 Vaán ñeà Critical Section Yeâu caàu cuûa lôøi giaûi cho Critical Section Problem Vaán ñeà Critical Section: phaûi baûo ñaûm söï loaïi tröø • Lôøi giaûi phaûi thoûa boán tính chaát: (1) Ñoäc quyeàn truy xuaát (Mutual exclusion): Khi moät process P ñang töông hoã (MUTual EXclusion, mutex), töùc laø khi moät thöïc thi trong vuøng tranh chaáp (CS) cuûa noù thì khoâng coù process Q process ñang thöïc thi trong vuøng tranh chaáp, khoâng naøo khaùc ñang thöïc thi trong CS cuûa Q. coù process naøo khaùc ñoàng thôøi thöïc thi caùc leänh trong vuøng tranh chaáp. (2) Progress: Moät tieán trình taïm döøng beân ngoaøi mieàn gaêng khoâng ñöôïc ngaên caûn caùc tieán trình khaùc vaøo mieàn gaêng vaø vieäc löïa choïn P naøo vaøo CS phaûi coù haïn ñònh • (3) Chôø ñôïi giôùi haïn (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). (4)Khoâng coù giaû thieát naøo ñaët ra cho söï lieân heä veà toác ñoä cuûa caùc tieán trình, cuõng nhö veà soá löôïng boä xöû lyù trong heä thoáng Khoa KTMT 11 Khoa KTMT 12 2
Phaân loaïi giaûi phaùp Caùc giaûi phaùp “Busy waiting” Nhóm giải pháp Busy Waiting – Sử dụng các biến cờ hiệu While (chưa có quyền)) do nothing() () ; – Sử dụng việc kiểm tra luân phiên – Giải pháp của Peterson CS; – Cấm ngắt – Chỉ thị TSL Từ bỏ quyền sử dụng CS Nhóm giải pháp Sleep & Wakeup – Semaphore Tiếp tục tiêu thụ CPU trong khi chờ đợi vào miền găng – Monitor Không đòi hỏi sự trợ giúp của Hệ điều hành – Message Khoa KTMT 13 Khoa KTMT 14 Caùc giaûi phaùp “Sleep & Wake up” Caù Caùc giaû giaûi phaù phaùp “Busy waiting” waiting” Giaû Giaûi thuaä thuaät 1 if (chưa có quyền)) Sleep()() ; 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 CS; Process Pi Wakeup(( somebody);); do { while (turn != i); critical section Từ bỏ CPU khi chưa được vào miền găng turn = j; remainder section Cần được Hệ điều hành hỗ trợ } 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 15 Khoa KTMT 16 Giaûi thuaät 1 (tt) Giaûi thuaät 2 Bieán chia seû Process P0: Process P1: • boolean flag[ 2 ]; /* khôûi ñaàu flag[ 0 ] = flag[ 1 ] = false */ do do • Neáu flag[ i ] = true thì Pi “saün saøng” vaøo critical section. while (turn != 0); while (turn != 1); Process Pi critical section critical section do { turn := 1; turn := 0; flag[ i ] = true; /* Pi “saün saøng” vaøo CS */ remainder section remainder section while ( flag[ j ] ); /* Pi “nhöôøng” Pj */ while (1); while (1); critical section flag[ i ] = false; Ví duï: remainder section P0 coù RS (remainder section) raát lôùn coøn P1 coù RS nhoû??? } while (1); Baûo ñaûm ñöôïc mutual exclusion. Chöùng minh? Khoâng thoûa maõn progress. Vì sao? Khoa KTMT 17 Khoa KTMT 18 3
Giaûi thuaät 3 (Peterson) Giaûi thuaät Peterson-2 process Bieán chia seû: keát hôïp caû giaûi thuaät 1 vaø 2 Process P1 Process Pi , vôùi i = 0 hay 1 Process P0 do { do { do { /* 1 wants in */ /* 0 wants in */ flag[ i ] = true; /* Process i saün saøng */ flag[0] = true; flag[1] = true; turn = j; /* Nhöôøng process j */ /* 0 gives a chance to 1 */ /* 1 gives a chance to 0 */ while (flag[ j ] and turn == j); turn = 1; turn = 0; critical section while (flag[1] && turn == 1); while (flag[0] && turn == 0); flag[ i ] = false; critical section; critical section; /* 0 no longer wants in */ /* 1 no longer wants in */ remainder section flag[0] = false; flag[1] = false; } while (1); remainder section; remainder section; } while(1); } 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 Khoa KTMT 20 Giaûi thuaät 3: Tính ñuùng ñaén Giaûi thuaät 3: Tính ñuùng ñaén (tt) • Giaûi thuaät 3 thoûa mutual exclusion, progress, vaø – Neáu Pj ñaõ baät flag[ j ] = true vaø ñang chôø taïi while() thì bounded waiting coù chæ hai tröôøng hôïp laø turn = i hoaëc turn = j Mutual exclusion ñöôïc baûo ñaûm bôûi vì – Neáu turn = i thì Pi vaøo CS. Neáu turn = j thì Pj vaøo CS • P0 vaø P1 ñeàu ôû trong CS neáu vaø chæ neáu flag[0] = nhöng seõ baät flag[ j ] = false khi thoaùt ra ⇒ cho pheùp flag[1] = true vaø turn = i cho moãi Pi (khoâng theå xaûy ra) Pi vaøo CS Chöùng minh thoûa yeâu caàu veà progress vaø – Nhöng neáu Pj coù ñuû thôøi gian baät flag[ j ] = true thì Pj bounded waiting cuõng phaûi gaùn turn = i – Pi khoâng theå vaøo CS neáu vaø chæ neáu bò keït taïi voøng – Vì Pi khoâng thay ñoåi trò cuûa bieán turn khi ñang keït laëp while() vôùi ñieàu kieän flag[ j ] = true vaø turn = j . trong voøng laëp while(), Pi seõ chôø ñeå vaøo CS nhieàu – Neáu Pj khoâng muoán vaøo CS thì flag[ j ] = false vaø do nhaát laø sau moät laàn Pj vaøo CS (bounded waiting) ñoù Pi coù theå vaøo CS. Khoa KTMT 21 Khoa KTMT 22 Giaûi thuaät bakery: n process Giaûi thuaät bakery: n process (tt) Tröôùc khi vaøo CS, process Pi nhaän moät con soá. /* shared variable */ boolean choosing[ n ]; /* initially, choosing[ i ] = false */ Process naøo giöõ con soá nhoû nhaát thì ñöôïc vaøo CS int num[ n ]; /* initially, num[ i ] = 0 */ Tröôøng hôïp Pi vaø Pj cuøng nhaän ñöôïc moät chæ soá: do { – Neáu i < j thì Pi ñöôïc vaøo tröôùc. (Ñoái xöùng) choosing[ i ] = true; Khi ra khoûi CS, Pi ñaët laïi soá cuûa mình baèng 0 num[ i ] = max(num[0], num[1],…, num[n − 1]) + 1; choosing[ i ] = false; Cô cheá caáp soá cho caùc process thöôøng taïo caùc soá for (j = 0; j < n; j++) theo cô cheá taêng daàn, ví duï 1, 2, 3, 3, 3, 3, 4, 5,… { while (choosing[ j ]); while ((num[ j ] != 0) && (num[ j ], j) < (num[ i ], i)); Kí hieäu } critical section • (a,b) < (c,d) neáu a < c hoaëc if a = c vaø b < d num[ i ] = 0; • max(a0,…,ak) laø con soá b sao cho b ≥ ai vôùi moïi i = 0,…, k remainder section } while (1); Khoa KTMT 23 Khoa KTMT 24 4
Töø software ñeán hardware Caám ngaét Khuyeát ñieåm cuûa caùc giaûi phaùp software Trong heä thoáng uniprocessor: – Caùc process khi yeâu caàu ñöôïc vaøo vuøng tranh chaáp mutual exclusion ñöôïc baûo Process Pi: ñaûm. ñeàu phaûi lieân tuïc kieåm tra ñieàu kieän (busy waiting), do { – Nhöng neáu system clock toán nhieàu thôøi gian xöû lyù cuûa CPU disable_interrupts(); ñöôïc caäp nhaät do interrupt – Neáu thôøi gian xöû lyù trong vuøng tranh chaáp lôùn, moät thì sao? critical section giaûi phaùp hieäu quaû neân coù cô cheá block caùc process Treân heä thoáng multiprocessor: caàn ñôïi. enable_interrupts(); mutual exclusion khoâng ñöôïc ñaûm baûo remainder section – Chæ caám ngaét taïi CPU thöïc } while (1); Caùc giaûi phaùp phaàn cöùng (hardware) thi leänh disable_interrupts – Caám ngaét (disable interrupts) – Caùc CPU khaùc vaãn coù theå truy caäp boä nhôù chia seû – Duøng caùc leänh ñaëc bieät Khoa KTMT 25 Khoa KTMT 26 Leänh TestAndSet Leänh TestAndSet (tt) Ñoïc vaø ghi moät bieán trong moät Mutual exclusion ñöôïc baûo ñaûm: neáu Pi vaøo CS, caùc thao taùc atomic (khoâng chia caét ñöôïc). process Pj khaùc ñeàu ñang busy waiting boolean TestAndSet(boolean &target) I Shared data: Khi Pi ra khoûi CS, quaù trình choïn löïa process Pj vaøo CS { boolean lock = false; keá tieáp laø tuøy yù ⇒ khoâng baûo ñaûm ñieàu kieän bounded boolean rv = target; I Process Pi : waiting. Do ñoù coù theå xaûy ra starvation (bò boû ñoùi) target = true; return rv; } do { Caùc processor (ví duï Pentium) thoâng thöôøng cung caáp while (TestAndSet(lock)); moät leänh ñôn laø Swap(a, b) coù taùc duïng hoaùn chuyeån noäi critical section dung cuûa a vaø b. lock = false; • Swap(a, b) cuõng coù öu nhöôïc ñieåm nhö TestAndSet remainder section } while (1); Khoa KTMT 27 Khoa KTMT 28 Swap vaø mutual exclusion Giaûi thuaät duøng TestAndSet thoaû maõn 3 yeâu caàu (1) Bieán chia seû lock ñöôïc khôûi Bieán chia seû (khôûi taïo laø false) Caáu truùc döõ lieäu duøng chung (khôûi taïo laø false) taïo giaù trò false bool lock; bool waiting[ n ]; Moãi process Pi coù bieán cuïc boä bool key; key bool lock; Process Pi naøo thaáy giaù trò Process Pi Mutual exclusion: Pi chæ coù theå vaøo CS neáu vaø chæ neáu lock = false thì ñöôïc vaøo CS. hoaëc waiting[ i ] = false, hoaëc key = false – Process Pi seõ loaïi tröø caùc do { process Pj khaùc khi thieát laäp key = true; • key = false chæ khi TestAndSet (hay Swap) ñöôïc thöïc thi lock = true while (key == true) Process ñaàu tieân thöïc thi TestAndSet môùi coù key == false; void Swap(boolean &a, Swap(lock, key); caùc process khaùc ñeàu phaûi ñôïi boolean &b) { critical section • waiting[ i ] = false chæ khi process khaùc rôøi khoûi CS boolean temp = a; lock = false; Chæ coù moät waiting[ i ] coù giaù trò false remainder section a = b; } while (1) Progress: chöùng minh töông töï nhö mutual exclusion b = temp; Bounded waiting: waiting in the cyclic order } Khoâng thoûa maõn bounded waiting Khoa KTMT 29 Khoa KTMT 30 5
Giaûi thuaät duøng TestAndSet thoaû maõn 3 yeâu caàu (2) Caùc giaûi phaùp “Sleep & Wake up” do { int busy; // =1 neáu CS ñang bò chieám waiting[i i]]==true; waiting[ true; Int blocked; // soá P ñang bò khoùa key==true; true; do key while(waiting[ (waiting[i i]]&&&&key) key) { while if (busy==1){ key==TestAndSet(lock); key TestAndSet(lock); blocked = blocked +1; waiting[i i]]==false; waiting[ false; sleep(); Tröôøng hôïp: critical section } -A vaøo CS else busy =1; -B kích hoaït vaø taêng blocked j j==(i(i++1) 1)%%n; n; -A kích hoaït laïi while(((j(j!= !=i)i) && && !waiting[ !waiting[j j]])) CS; while busy = 0; -B kích hoaït laïi j j==(j(j++1) 1)% %n;n; -????? if(blocked !=0){ ifif(j(j====i)i) wakeup(process); lock==false; lock false; blocked = blocked -1; else else } waiting[j j]]==false; waiting[ false; RS; remainder section } while(1); } while (1) Khoa KTMT 31 Khoa KTMT 32 Semaphore Semaphore • Laø coâng cuï ñoàng boä cung caáp bôûi OS maø khoâng ñoøi hoûi P(S) hay wait(S) söû duïng ñeå giaønh taøi nguyeân vaø giaûm busy waiting bieán ñeám S=S-1 Semaphore S laø moät bieán soá nguyeân. V(S) hay signal(S) seõ giaûi phoùng taøi nguyeân vaø taêng bieán Ngoaøi thao taùc khôûi ñoäng bieán thì chæ coù theå ñöôïc truy ñeám S= S+1 xuaát qua hai taùc vuï coù tính ñôn nguyeân (atomic) vaø loaïi Neáu P ñöôïc thöïc hieän treân bieán ñeám
Hieän thöïc semaphore (tt) Ví duï söû duïng semaphore 1 : Hieän thöïc mutex vôùi semaphore Khi moät process phaûi chôø treân semaphore S, noù Duøng cho n process Shared data: seõ bò blocked vaø ñöôïc ñaët trong haøng ñôïi semaphore mutex; semaphore Khôûi taïo S.value = 1 /* initially mutex.value = 1 */ – Haøng ñôïi naøy laø danh saùch lieân keát caùc PCB • Chæ duy nhaát moät process ñöôïc vaøo CS Taùc vuï signal() thöôøng söû duïng cô cheá FIFO khi (mutual exclusion) Process Pi: choïn moät process töø haøng ñôïi vaø ñöa vaøo haøng ñôïi ready do { Ñeå cho pheùp k process wait(mutex); block() vaø wakeup() thay ñoåi traïng thaùi cuûa vaøo CS, khôûi taïo critical section process S.value = k signal(mutex); • block: chuyeån töø running sang waiting remainder section • wakeup: chuyeån töø waiting sang ready } while (1); Khoa KTMT 37 Khoa KTMT 38 Ví duï söû duïng semaphore 2 :Ñoàng boä process baèng semaphore Nhaän xeùt Hai process: P1 vaø P2 Ñeå ñoàng boä hoaït ñoäng Khi S.value ≥ 0: soá process coù theå thöïc thi wait(S) maø theo yeâu caàu, P1 phaûi khoâng bò blocked = S.value Yeâu caàu: leänh S1 trong ñònh nghóa nhö sau: S1; P1 caàn ñöôïc thöïc thi Khi S.value < 0: soá process ñang ñôïi treân S laø S.value signal(synch); tröôùc leänh S2 trong P2 Atomic vaø mutual exclusion: khoâng ñöôïc xaûy ra tröôøng Ñònh nghóa semaphore Vaø P2 ñònh nghóa nhö sau: hôïp 2 process cuøng ñang ôû trong thaân leänh wait(S) vaø wait(synch); synch ñeå ñoàng boä signal(S) (cuøng semaphore S) taïi moät thôøi ñieåm (ngay caû S2; vôùi heä thoáng multiprocessor) Khôûi ñoäng semaphore: ⇒ do ñoù, ñoaïn maõ ñònh nghóa caùc leänh wait(S) vaø synch.value = 0 signal(S) cuõng chính laø vuøng tranh chaáp Khoa KTMT 39 Khoa KTMT 40 Nhaän xeùt (tt) Deadlock vaø starvation Vuøng tranh chaáp cuûa caùc taùc vuï wait(S) vaø signal(S) 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 thoâng thöôøng raát nhoû: khoaûng 10 leänh. ñang ñôïi taïo ra). Goïi S vaø Q laø hai bieán semaphore ñöôïc khôûi taïo = 1 Giaûi phaùp cho vuøng tranh chaáp wait(S) vaø signal(S) P0 P1 – Uniprocessor: coù theå duøng cô cheá caám ngaét (disable interrupt). Nhöng phöông phaùp naøy khoâng laøm vieäc treân heä wait(S); wait(Q); thoáng multiprocessor. wait(Q); wait(S); M M – Multiprocessor: coù theå duøng caùc giaûi phaùp software (nhö signal(S); signal(Q); giaûi thuaät Dekker, Peterson) hoaëc giaûi phaùp hardware signal(Q); signal(S); (TestAndSet, Swap). P0 thöïc thi wait(S), roài P1 thöïc thi wait(Q), roài P0 thöïc thi wait(Q) bò • Vì CS raát nhoû neân chi phí cho busy waiting seõ raát thaáp. blocked, P1 thöïc thi wait(S) bò blocked. Starvation (indefinite blocking) Moät tieán trình coù theå khoâng bao giôø ñöôïc laáy ra khoûi haøng ñôïi maø noù bò treo trong haøng ñôïi ñoù. Khoa KTMT 41 Khoa KTMT 42 7
Caùc loaïi semaphore Caùc baøi toaùn ñoàng boä (kinh ñieån) Counting semaphore: moät soá nguyeân coù giaù trò Bounded Buffer Problem khoâng haïn cheá. Readers and Writers Problem Dining-Philosophers Problem Binary semaphore: coù trò laø 0 hay 1. Binary semaphore raát deã hieän thöïc. Coù theå hieän thöïc counting semaphore baèng binary semaphore. Khoa KTMT 43 Khoa KTMT 44 Caùc baøi toaùn ñoàng boä Bounded buffer Baøi toaùn bounded buffer producer consumer – Döõ lieäu chia seû: do { do { 9 wait(full) semaphore full, empty, mutex; nextp = new_item(); wait(mutex); – Khôûi taïo: 9 9 wait(empty); nextc = get_buffer_item(out); • full = 0; /* soá buffers ñaày */ wait(mutex); 9 • empty = n; /* soá buffers troáng */ 9 signal(mutex); insert_to_buffer(nextp); signal(empty); • mutex = 1; 9 9 signal(mutex); consume_item(nextc); signal(full); 9 n buffers } while (1); } while (1); out Khoa KTMT 45 Khoa KTMT 46 Baøi toaùn “Dining Philosophers” (1) Baøi toaùn “Dining Philosophers” (2) 5 trieát gia ngoài aên vaø suy Trieát gia thöù i: nghó 3 2 do { 3 wait(chopstick [ i ]) Moãi ngöôøi caàn 2 chieác 4 2 wait(chopstick [ (i + 1) % 5 ]) ñuõa (chopstick) ñeå aên … Treân baøn chæ coù 5 ñuõa eat 4 0 1 1 … Baøi toaùn naøy minh hoïa söï signal(chopstick [ i ]); 0 khoù khaên trong vieäc phaân signal(chopstick [ (i + 1) % 5 ]); phoái taøi nguyeân giöõa caùc … Döõ lieäu chia seû: think process sao cho khoâng semaphore chopstick[5]; xaûy ra deadlock vaø … starvation } while (1); Khôûi ñaàu caùc bieán ñeàu laø 1 Khoa KTMT 47 Khoa KTMT 48 8
Baøi toaùn “Dining Philosophers” (3) Baøi toaùn Readers-Writers (1) Giaûi phaùp treân coù theå gaây ra deadlock Readers - Writers – Khi taát caû trieát gia ñoùi buïng cuøng luùc vaø ñoàng thôøi caàm chieác ñuõa beân tay traùi ⇒ deadlock W không được cập nhật dữ liệu khi có một R đang truy xuất CSDL . Moät soá giaûi phaùp khaùc giaûi quyeát ñöôïc deadlock Tại một thời điểm , chỉ cho phép một W được – Cho pheùp nhieàu nhaát 4 trieát gia ngoài vaøo cuøng moät luùc sửa đổi nội dung CSDL. – Cho pheùp trieát gia caàm caùc ñuõa chæ khi caû hai chieác ñuõa ñeàu saün saøng (nghóa laø taùc vuï caàm caùc ñuõa phaûi R2 xaûy ra trong CS) R3 R1 – Trieát gia ngoài ôû vò trí leû caàm ñuõa beân traùi tröôùc, sau ñoù môùi ñeán ñuõa beân phaûi, trong khi ñoù trieát gia ôû vò trí W1 W2 chaün caàm ñuõa beân phaûi tröôùc, sau ñoù môùi ñeán ñuõa beân traùi Database Starvation? Khoa KTMT 49 Khoa KTMT 50 Baøi toaùn Readers-Writers (2) Baøi toaùn Readers-Writers (3) Boä ñoïc tröôùc boä ghi (first Reader Process mutex: “baûo veä” bieán readcount reader-writer) Döõ lieäu chia seû wait(mutex); wrt semaphore mutex = 1; readcount++; – Baûo ñaûm mutual exclusion ñoái vôùi caùc writer semaphore wrt = 1; if (readcount == 1) – Ñöôïc söû duïng bôûi reader ñaàu tieân hoaëc cuoái cuøng int readcount = 0; wait(wrt); vaøo hay ra khoûi vuøng tranh chaáp. signal(mutex); Neáu moät writer ñang ôû trong CS vaø coù n reader Writer process ... reading is performed ñang ñôïi thì moät reader ñöôïc xeáp trong haøng wait(wrt); ... ñôïi cuûa wrt vaø n − 1 reader kia trong haøng ñôïi ... wait(mutex); cuûa mutex writing is performed readcount--; Khi writer thöïc thi signal(wrt), heä thoáng coù theå ... if (readcount == 0) signal(wrt); phuïc hoài thöïc thi cuûa moät trong caùc reader ñang signal(wrt); signal(mutex); ñôïi hoaëc writer ñang ñôïi. Khoa KTMT 51 Khoa KTMT 52 Caùc vaán ñeà vôùi semaphore Critical Region (CR) Semaphore cung caáp moät coâng cuï maïnh meõ ñeå baûo Laø moät caáu truùc ngoân ngöõ caáp cao (high-level language construct, ñöôïc dòch sang maõ maùy bôûi moät compiler), thuaän tieän hôn cho ngöôøi ñaûm mutual exclusion vaø phoái hôïp ñoàng boä caùc process laäp trình. Tuy nhieân, neáu caùc taùc vuï wait(S) vaø signal(S) naèm raûi Moät bieán chia seû v kieåu döõ lieäu T, khai baùo nhö sau raùc ôû raát nhieàu processes ⇒ khoù naém baét ñöôïc hieäu öùng v: shared T; 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. Bieán chia seû v chæ coù theå ñöôïc truy xuaát qua phaùt bieåu sau region v when B do S; /* B laø moät bieåu thöùc Boolean */ Moät process bò “die” coù theå keùo theo caùc process khaùc cuøng söû duïng bieán semaphore. • YÙ nghóa: trong khi S ñöôïc thöïc thi, khoâng coù quaù trình khaùc coù theå signal(mutex) wait(mutex) signal(mutex) truy xuaát bieán v. signal(mutex) wait(mutex) signal(mutex) 99 99 99 criticalsection critical section criticalsection critical section criticalsection critical section 99 99 99 wait(mutex) wait(mutex) wait(mutex) wait(mutex) signal(mutex) signal(mutex) Khoa KTMT 53 Khoa KTMT 54 9
CR vaø baøi toaùn bounded buffer Monitor (1) Döõ lieäu chia seû: Producer Cuõng laø moät caáu truùc ngoân ngöõ caáp cao töông töï CR, coù region buffer buffer when when (count (count > 0){ 0){ } nextc == pool[out]; nextc pool[out]; out == (out out (out ++1) 1)%% n; n; count--; count--; }} Khoa KTMT 55 Khoa KTMT 56 Monitor (2) Caáu truùc cuûa monitor Laø moät module phaàn Ñaëc tính cuûa monitor monitor monitor-name meàm, bao goàm – Local variable chæ coù theå { – Moät hoaëc nhieàu thuû tuïc truy xuaát bôûi caùc thuû tuïc shared variable declarations (procedure) cuûa monitor procedure body P1 (9) { – Process “vaøo monitor” baèng ... – Moät ñoaïn code khôûi taïo (initialization code) caùch goïi moät trong caùc thuû } tuïc ñoù procedure body P2 (9) { – Caùc bieán döõ lieäu cuïc boä (local data variable) – Chæ coù moät process coù theå ... vaøo monitor taïi moät thôøi } ñieåm ⇒ mutual exclusion procedure body Pn (9) { shared data ñöôïc baûo ñaûm ... } … entry queue { operations initialization code initialization Moâ hình cuûa moät monitor } code ñôn giaûn } Khoa KTMT 57 Khoa KTMT 58 Condition variable Monitor coù condition variable Nhaèm cho pheùp moät process ñôïi “trong monitor”, phaûi khai baùo bieán ñieàu kieän (condition variable) shared data entry queue condition a, b; a Caùc process coù theå ñôïi ôû entry Caùc bieán ñieàu kieän ñeàu cuïc boä vaø chæ ñöôïc truy caäp beân b queue hoaëc ñôïi ôû caùc condition trong monitor. queue (a, b,…) Chæ coù theå thao taùc leân bieán ñieàu kieän baèng hai thuû tuïc: Khi thöïc hieän leänh a.wait, ... process seõ ñöôïc chuyeån vaøo – a.wait: process goïi taùc vuï naøy seõ bò “block treân bieán ñieàu kieän” a condition queue a process naøy chæ coù theå tieáp tuïc thöïc thi khi coù process khaùc Leänh a.signal chuyeån moät thöïc hieän taùc vuï a.signal operations process töø condition queue a – a.signal: phuïc hoài quaù trình thöïc thi cuûa process bò block treân vaøo monitor bieán ñieàu kieän a. • Khi ñoù, ñeå baûo ñaûm mutual Neáu coù nhieàu process: chæ choïn moät initialization exclusion, process goïi a.signal Neáu khoâng coù process: khoâng coù taùc duïng code seõ bò blocked vaø ñöôïc ñöa vaøo urgent queue Khoa KTMT 59 Khoa KTMT 60 10
Monitor coù condition variable (tt) Monitor vaø dining philosophers entry queue monitor waiting area entrance 3 2 MONITOR local data condition c1 condition variables c1.wait procedure 1 4 1 ... 0 ... condition cn monitor dp cn.wait procedure k { enum {thinking, hungry, eating} state[5]; urgent queue initialization code condition self[5]; cx.signal exit Khoa KTMT 61 Khoa KTMT 62 Dining philosophers (tt) Dining philosophers (tt) void pickup(int i) { void test(int i) { state[ i ] = hungry; if ( (state[(i + 4) % 5] != eating) && test[ i ]; (state[ i ] == hungry) && if (state[ i ] != eating) (state[(i + 1) % 5] != eating) ) { self[ i ].wait(); state[ i ] = eating; } self[ i ].signal(); void putdown(int i) { } state[ i ] = thinking; void init() { // test left and right neighbors for (int i = 0; i < 5; i++) test((i + 4) % 5); // left neighbor state[ i ] = thinking; test((i + 1) % 5); // right … } } } Khoa KTMT 63 Khoa KTMT 64 Dining philosophers (tt) 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); aên dp.putdown(i); Giaûi thuaät khoâng deadlock nhöng coù theå gaây starvation. Khoa KTMT 65 11
Chöông 6 : Taéc ngheõn(Deadlock) Vaán ñeà deadlock trong heä thoáng Moâ hình heä thoáng Tình huoáng: moät taäp caùc process bò blocked, moãi process giöõ taøi nguyeân vaø ñang chôø taøi nguyeân maø process khaùc trong taäp ñang giöõ. Ñònh nghóa Ví duï 1 Ñieàu kieän caàn cuûa deadlock – Giaû söû heä thoáng coù 2 file treân ñóa. Resource Allocation Graph (RAG) – P1 vaø P2 moãi process ñang môû moät file vaø yeâu caàu môû file kia. Phöông phaùp giaûi quyeát deadlock Ví duï 2 Deadlock prevention – Semaphore A vaø B, khôûi taïo baèng 1 P0 P1 Deadlock avoidance wait(A); wait(B); Deadlock detection wait(B); wait(A); Deadlock recovery Phöông phaùp keát hôïp ñeå giaûi quyeát Deadlock Khoa KTMT 1 Khoa KTMT 2 Moâ hình hoùa heä thoáng Ñònh nghóa Heä thoáng goàm caùc loaïi taøi nguyeân, kí hieäu R1, R2,…, Rm , bao goàm: Moät tieán trình goïi laø deadlocked neáu noù ñang ñôïi moät – CPU cycle, khoâng gian boä nhôù, thieát bò I/O, file, semaphore,… söï kieän maø seõ khoâng bao giôø saûy ra. • Moãi loaïi taøi nguyeân Ri coù Wi thöïc theå (instance). Thoâng thöôøng, coù nhieàu hôn moät tieán trình bò lieân quan trong moät deadlock. Giaû söû taøi nguyeân taùi söû duïng theo kyø (Serially Reusable Resources) Moät tieán trình goïi laø trì hoaõn voâ haïn ñònh (indefinitely – Yeâu caàu (request): process phaûi chôø neáu yeâu caàu khoâng ñöôïc ñaùp öùng postponed) neáu noù bò trì hoaõn moät khoaûng thôøi gian daøi ngay – Söû duïng (use): process söû duïng taøi nguyeân laëp ñi laëp laïi trong khi heä thoáng ñaùp öùng cho nhöõng tieán – Hoaøn traû (release): process hoaøn traû taøi nguyeân trình khaùc . i.e. Moät tieán trình saün saøng ñeå xöû lyù nhöng noù khoâng bao giôø Caùc taùc vuï yeâu caàu (request) vaø hoaøn traû (release) ñeàu laø system nhaän ñöôïc CPU. call. Ví duï – request/release device – open/close file – allocate/free memory – wait/signal Khoa KTMT 3 Khoa KTMT 4 Ñieàu kieän caàn ñeå xaûy ra deadlock Ñieàu kieän caàn ñeå xaûy ra deadlock (tt) Boán ñieàu kieän caàn (necessary condition) ñeå xaûy ra 3. Khoâng tröng duïng (No preemption): (= no resource deadlock preemption) taøi nguyeân khoâng theå bò laáy laïi, maø chæ coù theå ñöôïc traû laïi töø process ñang giöõ taøi nguyeân ñoù khi 1. Loaïi tröø hoã töông (Mutual exclusion): ít nhaát moät taøi noù muoán. nguyeân ñöôïc giöõ theo nonsharable mode (ví duï: printer; ví duï sharable resource: read-only files). 4. Chu trình ñôïi (Circular wait): toàn taïi moät taäp {P0,…,Pn} caùc quaù trình ñang ñôïi sao cho P0 ñôïi moät taøi nguyeân maø P1 ñang giöõ 2. Giöõ vaø chôø caáp theâm taøi nguyeân (Hold and wait): moät P1 ñôïi moät taøi nguyeân maø P2 ñang giöõ process ñang giöõ ít nhaát moät taøi nguyeân vaø ñôïi theâm taøi … nguyeân do quaù trình khaùc ñang giöõ. Pn ñôïi moät taøi nguyeân maø P0 ñang giöõ Khoa KTMT 5 Khoa KTMT 6 1
Ñoà thò caáp phaùt taøi nguyeân Resource Allocation Graph (tt) Resource Allocation Graph Resource allocation graph (RAG) laø ñoà thò coù höôùng, vôùi Kyù hieäu taäp ñænh V vaø taäp caïnh E Process: Pi Rj – Taäp ñænh V goàm 2 loaïi: Loaïi taøi nguyeân vôùi 4 thöïc theå: P = {P1, P2,…, Pn } (Taát caû process trong heä thoáng) R = {R1, R2,…, Rm } (Taát caû caùc loaïi taøi nguyeân trong heä thoáng) Rj – Taäp caïnh E goàm 2 loaïi: Pi yeâu caàu moät thöïc theå cuûa Rj : Pi Caïnh yeâu caàu (Request edge): ø Pi Rj Rj Caïnh caáp phaùt (Assignment edge): Rj Pi Pi ñang giöõ moät thöïc theå cuûa Rj : Pi Khoa KTMT 7 Khoa KTMT 8 Ví duï veà RAG Ví duï veà RAG (tt) R1 R3 R1 R3 P1 P2 P3 P1 P2 P3 Deadlock xaûy ra! R2 R4 R2 R4 Khoa KTMT 9 Khoa KTMT 10 RAG vaø deadlock RAG vaø deadlock (tt) Ví duï moät RAG chöùa chu trình nhöng khoâng xaûy ra RAG khoâng chöùa chu trình (cycle) ⇒ khoâng coù deadlock deadlock: P4 coù theå traû laïi instance cuûa R2. RAG chöùa moät (hay nhieàu) chu trình – Neáu moãi loaïi taøi nguyeân chæ coù moät thöïc theå ⇒ deadlock R1 P2 – Neáu moãi loaïi taøi nguyeân coù nhieàu thöïc theå ⇒ coù theå xaûy ra deadlock P1 R2 P3 P4 Khoa KTMT 11 Khoa KTMT 12 2
Caùc phöông phaùp giaûi quyeát deadlock (1) Caùc phöông phaùp giaûi quyeát deadlock (2) • Ba phöông phaùp • 2) Cho pheùp heä thoáng vaøo traïng thaùi deadlock, • 1) Baûo ñaûm raèng heä thoáng khoâng rôi vaøo tình traïng nhöng sau ñoù phaùt hieän deadlock vaø phuïc hoài heä deadlock baèng caùch ngaên (preventing) hoaëc traùnh thoáng. (avoiding) deadlock. • Khaùc bieät • 3) Boû qua moïi vaán ñeà, xem nhö deadlock khoâng – Ngaên deadlock: khoâng cho pheùp (ít nhaát) moät trong 4 ñieàu bao giôø xaûy ra trong heä thoáng. kieän caàn cho deadlock ☺Khaù nhieàu heä ñieàu haønh söû duïng phöông phaùp naøy. – Traùnh deadlock: caùc quaù trình caàn cung caáp thoâng tin veà – Deadlock khoâng ñöôïc phaùt hieän, daãn ñeán vieäc giaûm taøi nguyeân noù caàn ñeå heä thoáng caáp phaùt taøi nguyeân moät hieäu suaát cuûa heä thoáng. Cuoái cuøng, heä thoáng coù theå caùch thích hôïp ngöng hoaït ñoäng vaø phaûi ñöôïc khôûi ñoäng laïi. Khoa KTMT 13 Khoa KTMT 14 1. Ngaên deadlock (deadlock prevention) Ngaên deadlock (tt) Ngaên deadlock baèng caùch ngaên moät trong 4 ñieàu kieän 2. Ngaên Hold and Wait caàn cuûa deadlock – Caùch 1: moãi process yeâu caàu toaøn boä taøi nguyeân caàn thieát moät laàn. Neáu coù ñuû taøi nguyeân thì heä thoáng seõ caáp phaùt, neáu khoâng 1. Ngaên mutual exclusion ñuû taøi nguyeân thì process phaûi bò blocked. – ñoái vôùi nonsharable resource (vd: printer): khoâng laøm ñöôïc – ñoái vôùi sharable resource (vd: read-only file): khoâng caàn thieát – Caùch 2: khi yeâu caàu taøi nguyeân, process khoâng ñöôïc giöõ baát kyø taøi nguyeân naøo. Neáu ñang coù thì phaûi traû laïi tröôùc khi yeâu caàu. – Ví duï ñeå so saùnh hai caùch treân: moät quaù trình copy döõ lieäu töø tape drive sang disk file, saép xeáp disk file, roài in keát quaû ra printer. – Khuyeát ñieåm cuûa caùc caùch treân: Hieäu suaát söû duïng taøi nguyeân (resource utilization) thaáp Quaù trình coù theå bò starvation Khoa KTMT 15 Khoa KTMT 16 Ngaên deadlock (tt) Ngaên deadlock (tt) 3. Ngaên No Preemption: neáu process A coù giöõ taøi nguyeân vaø ñang 4. Ngaên Circular Wait: gaùn moät thöù töï cho taát caû caùc taøi nguyeân trong yeâu caàu taøi nguyeân khaùc nhöng taøi nguyeân naøy chöa caáp phaùt ngay heä thoáng. ñöôïc thì – Taäp hôïp loaïi taøi nguyeân: R={R1, R2,…,Rm } Haøm aùnh xaï: F: R->N – Caùch 1: Heä thoáng laáy laïi moïi taøi nguyeân maø A ñang giöõ – Ví duï: F(tape drive) = 1, F(disk drive) = 5, F(printer) = 12 A chæ baét ñaàu laïi ñöôïc khi coù ñöôïc caùc taøi nguyeân ñaõ bò laáy F laø haøm ñònh nghóa thöù töï treân taäp caùc loaïi taøi nguyeân. laïi cuøng vôùi taøi nguyeân ñang yeâu caàu – Caùch 2: Heä thoáng seõ xem taøi nguyeân maø A yeâu caàu Neáu taøi nguyeân ñöôïc giöõ bôûi moät process khaùc ñang ñôïi theâm taøi nguyeân, taøi nguyeân naøy ñöôïc heä thoáng laáy laïi vaø caáp phaùt cho A. Neáu taøi nguyeân ñöôïc giöõ bôûi process khoâng ñôïi taøi nguyeân, A phaûi ñôïi vaø taøi nguyeân cuûa A bò laáy laïi. Tuy nhieân heä thoáng chæ laáy laïi caùc taøi nguyeân maø process khaùc yeâu caàu Khoa KTMT 17 Khoa KTMT 18 3
2. Traùnh taéc ngheõn Ngaên deadlock (tt) Deadlock avoidance 4. Ngaên Circular Wait (tt) Deadlock prevention söû duïng taøi nguyeân khoâng hieäu quaû. – Moãi process chæ coù theå yeâu caàu thöïc theå cuûa moät loaïi taøi nguyeân theo thöù töï taêng daàn (ñònh nghóa bôûi haøm F) cuûa loaïi taøi nguyeân. Ví duï Deadlock avoidance vaãn ñaûm baûo hieäu suaát söû duïng taøi nguyeân toái Chuoãi yeâu caàu thöïc theå hôïp leä: tape drive → disk drive → printer ña ñeán möùc coù theå. Chuoãi yeâu caàu thöïc theå khoâng hôïp leä: disk drive → tape drive Yeâu caàu moãi process khai baùo soá löôïng taøi nguyeân toái ña caàn ñeå – Khi moät process yeâu caàu moät thöïc theå cuûa loaïi taøi nguyeân Rj thì noù phaûi thöïc hieän coâng vieäc traû laïi caùc taøi nguyeân Ri vôùi F(Ri) > F(Rj). R1 Giaûi thuaät deadlock-avoidance seõ kieåm tra traïng thaùi caáp phaùt taøi – “Chöùng minh” giaû söû toàn taïi moät chu trình deadlock P1 P2 nguyeân (resource-allocation state) ñeå baûo ñaûm heä thoáng khoâng rôi F(R4) < F(R1) vaøo deadlock. F(R1) < F(R2) • Traïng thaùi caáp phaùt taøi nguyeân ñöôïc ñònh nghóa döïa treân soá taøi F(R2) < F(R3) R4 R2 nguyeân coøn laïi, soá taøi nguyeân ñaõ ñöôïc caáp phaùt vaø yeâu caàu toái ña F(R3) < F(R4) cuûa caùc process. • Vaäy F(R4) < F(R4), maâu thuaãn! R3 P4 P3 Khoa KTMT 19 Khoa KTMT 20 Traïng thaùi safe vaø unsafe Chuoãi an toaøn (tt) Moät traïng thaùi cuûa heä thoáng ñöôïc goïi laø an toaøn (safe) Ví duï: Heä thoáng coù 12 tape drives vaø 3 quaù trình P0, P1, P2 neáu toàn taïi moät chuoãi (thöù tö)ï an toaøn (safe sequence). Taïi thôøi ñieåm t0 Moät chuoãi quaù trình laø moät chuoãi an toaøn Maximum Current neáu needs needs – Vôùi moïi i = 1,…,n, yeâu caàu toái ña veà taøi nguyeân cuûa Pi coù theå P0 10 5 ñöôïc thoûa bôûi P1 4 2 taøi nguyeân maø heä thoáng ñang coù saün saøng (available) cuøng vôùi taøi nguyeân maø taát caû Pj , j < i, ñang giöõ. P2 9 2 Moät traïng thaùi cuûa heä thoáng ñöôïc goïi laø khoâng an toaøn – Coøn 3 tape drive saün saøng. (unsafe) neáu khoâng toàn taïi moät chuoãi an toaøn. – Chuoãi laø chuoãi an toaøn ⇒ heä thoáng laø an toaøn Khoa KTMT 21 Khoa KTMT 22 Chuoãi an toaøn (tt) Traïng thaùi safe/unsafe vaø deadlock Giaû söû taïi thôøi ñieåm t1, P2 yeâu caàu vaø ñöôïc caáp phaùt 1 Neáu heä thoáng ñang ôû traïng thaùi safe ⇒ khoâng deadlock. tape drive Neáu heä thoáng ñang ôû traïng thaùi unsafe ⇒ coù theå daãn ñeán deadlock. – coøn 2 tape drive saün saøng Traùnh deadlock baèng caùch baûo ñaûm heä thoáng khoâng ñi ñeán traïng thaùi unsafe. caàn toái ña ñang giöõ P0 10 5 P1 4 2 deadlock unsafe P2 9 3 Heä thoáng coøn an toaøn khoâng? safe Khoa KTMT 23 Khoa KTMT 24 4
Giaûi thuaät ñoà thò caáp phaùt taøi nguyeân Giaûi thuaät banker Khaùi nieäm caïnh thænh caàu AÙp duïng cho heä thoáng caáp phaùt taøi nguyeân trong ñoù moãi loaïi taøi nguyeân coù theå coù nhieàu instance. R1 R1 Baét chöôùc nghieäp vuï ngaân haøng (banking) Ñieàu kieän P1 P1 P2 P2 – Moãi process phaûi khai baùo soá löôïng thöïc theå (instance) toái ña cuûa moãi loaïi taøi nguyeân maø noù caàn – Khi process yeâu caàu taøi nguyeân thì coù theå phaûi ñôïi maëc duø taøi R2 R2 nguyeân ñöôïc yeâu caàu ñang coù saün – Khi process ñaõ coù ñöôïc ñaày ñuû taøi nguyeân thì phaûi hoaøn traû trong moät khoaûng thôøi gian höõu haïn naøo ñoù. Khoa KTMT 25 Khoa KTMT 26 Giaûi thuaät banker (tt) Giaûi thuaät banker (tt) 1.Giaûi thuaät an toaøn n: soá process, m: soá loaïi taøi nguyeân Tìm moät chuoãi an toaøn Caùc caáu truùc döõ lieäu Available: vector ñoä daøi m 1. Goïi Work vaø Finish laø hai vector ñoä daøi laø m vaø n. Khôûi taïo Available[ j ] = k ⇔ loaïi taøi nguyeân Rj coù k instance saün saøng Work := Available Max: ma traän n × m Finish[ i ] := false, i = 1,…, n Max[ i, j ] = k ⇔ quaù trình Pi yeâu caàu toái ña k instance cuûa loaïi 2. Tìm i thoûa taøi nguyeân Rj (a) Finish[ i ] = false Allocation: ma traän n × m (b) Needi ≤ Work (haøng thöù i cuûa Need) Allocation[i, j] = k ⇔ Pi ñaõ ñöôïc caáp phaùt k instance cuûa Rj Neáu khoâng toàn taïi i nhö vaäy, ñeán böôùc 4. Need: ma traän n × m 3. Work := Work + Allocationi Need[i, j] = k ⇔ Pi caàn theâm k instance cuûa Rj Finish[ i ] := true Nhaän xeùt: Need[i, j] = Max[i, j] – Allocation[i, j] quay veà böôùc 2. 4. Neáu Finish[ i ] = true, i = 1,…, n, thì heä thoáng ñang ôû traïng thaùi safe Kyù hieäu Y ≤ X ⇔ Y[i] ≤ X[i], ví duï (0, 3, 2, 1) ≤ (1, 7, 3, 2) Thôøi gian chaïy cuûa giaûi thuaät laø O(m·n2) Khoa KTMT 27 Khoa KTMT 28 Giaûi thuaät banker (tt) Giaûi thuaät banker (tt) 2. Giaûi thuaät yeâu caàu (caáp phaùt) taøi nguyeân 2.Giaûi thuaät yeâu caàu taøi nguyeân Goïi Requesti laø request vector cuûa process Pi . AÙp duïng giaûi thuaät kieåm tra traïng thaùi an toaøn leân traïng thaùi treân Requesti [ j ] = k ⇔ Pi caàn k instance cuûa taøi nguyeân Rj . Neáu traïng thaùi laø safe thì taøi nguyeân ñöôïc caáp thöïc söï cho Pi . Neáu traïng thaùi laø unsafe thì Pi phaûi ñôïi, vaø 1. Neáu Requesti ≤ Needi thì ñeán böôùc 2. Neáu khoâng, baùo • phuïc hoài traïng thaùi: loãi vì process ñaõ vöôït yeâu caàu toái ña. Available := Available + Requesti 2. Neáu Requesti ≤ Available thì qua böôùc 3. Neáu khoâng, Pi Allocationi := Allocationi – Requesti phaûi chôø vì taøi nguyeân khoâng coøn ñuû ñeå caáp phaùt. Needi := Needi + Requesti 3. Giaû ñònh caáp phaùt taøi nguyeân ñaùp öùng yeâu caàu cuûa Pi baèng caùch caäp nhaät traïng thaùi heä thoáng nhö sau: Available := Available – Requesti Allocationi := Allocationi + Requesti Needi := Needi – Requesti Khoa KTMT 29 Khoa KTMT 30 5
Giaûi thuaät kieåm tra traïng thaùi an toaøn – Ví duï GT (kieåm tra traïng thaùi)an toaøn – Vd (tt) Coù 5 process P0 ,…, P4 Coù 3 loaïi taøi nguyeân: A (coù 10 instance), B (5 instance) vaø C (7 Chuoãi an toaøn instance). Sô ñoà caáp phaùt trong heä thoáng taïi thôøi ñieåm T0 Allocation Need Work ABC ABC A B C Allocation Max Available Need P0 010 743 3 3 2 A B C A B C A B C A B C P1 200 122 P0 0 1 0 7 5 3 3 3 2 7 4 3 5 3 2 P2 302 600 P1 2 0 0 3 2 2 1 2 2 7 4 3 P2 3 0 2 9 0 2 6 0 0 P3 211 011 P3 2 1 1 2 2 2 0 1 1 P4 002 431 7 4 5 P4 0 0 2 4 3 3 4 3 1 10 4 7 10 5 7 Khoa KTMT 31 Khoa KTMT 32 GT caáp phaùt taøi nguyeân – Ví duï 3. Phaùt hieän deadlock (Deadlock detection) Yeâu caàu (1, 0, 2) cuûa P1 coù thoûa ñöôïc khoâng? Chaáp nhaän xaûy ra deadlock trong heä thoáng, kieåm tra – Kieåm tra ñieàu kieän Request1 ≤ Available: traïng thaùi heä thoáng baèng giaûi thuaät phaùt hieän deadlock. (1, 0, 2) ≤ (3, 3, 2) laø ñuùng – Giaû ñònh thoûa yeâu caàu, kieåm tra traïng thaùi môùi coù phaûi laø safe hay khoâng. Neáu coù deadlock thì tieán haønh phuïc hoài heä thoáng Allocation Need Available A B C A B C A B C Caùc giaûi thuaät phaùt hieän deadlock thöôøng söû duïng moâ hình RAG. P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 Heä thoáng caáp phaùt taøi nguyeân ñöôïc khaûo saùt trong moãi P4 (3, 3, 0) ? tröôøng hôïp sau P0 (0, 2, 0) ? P3 2 1 1 0 1 1 1. Moãi loaïi taøi nguyeân chæ coù moät thöïc theå (instance) P3 (0, 2, 1)? P4 0 0 2 4 3 1 2. Moãi loaïi taøi nguyeân coù theå coù nhieàu thöïc theå – Traïng thaùi môùi laø safe (chuoãi an toaøn laø ), vaäy coù theå caáp phaùt taøi nguyeân cho P1. Khoa KTMT 33 Khoa KTMT 34 Moãi loaïi taøi nguyeân chæ coù moät thöïc theå Moãi loaïi taøi nguyeân coù nhieàu thöïc theå Söû duïng wait-for graph Phöông phaùp duøng wait-for graph khoâng aùp duïng ñöôïc cho tröôøng – Wait-for graph ñöôïc daãn xuaát töø RAG baèng caùch boû caùc node bieåu dieãn hôïp moãi loaïi taøi nguyeân coù nhieàu instance. taøi nguyeân vaø gheùp caùc caïnh töông öùng. Coù caïnh töø Pi ñeán Pj ⇔ Pi ñang chôø taøi nguyeân töø Pj Caùc caáu truùc döõ lieäu duøng trong giaûi thuaät phaùt hieän deadlock Available: vector ñoä daøi m P5 • soá instance saün saøng cuûa moãi loaïi taøi nguyeân P5 • Allocation: ma traän n × m R1 R3 R4 • soá instance cuûa moãi loaïi taøi nguyeân ñaõ caáp phaùt cho moãi process P1 P2 P3 P1 P2 P3 • Request: ma traän n × m • yeâu caàu hieän taïi cuûa moãi process. R2 P4 R5 P4 • Request [i, j ] = k ⇔ Pi ñang yeâu caàu theâm k instance cuûa Rj Moät giaûi thuaät kieåm tra coù toàn taïi chu trình trong wait-for graph hay khoâng seõ ñöôïc goïi ñònh kyø. Giaûi thuaät phaùt hieän chu trình coù thôøi gian chaïy laø O(n 2), vôùi n laø soá ñænh cuûa graph. Khoa KTMT 35 Khoa KTMT 36 6