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

pdf

235 trang phuongnguyen 7360

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ điều hành - Chương 5: Đồng bộ hóa tiến trình", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_he_dieu_hanh_chuong_5_dong_bo_hoa_tien_trinh.pdf

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

Chương 5 Đồng bộ hoá tiến trình 11/10/2007 Trần Hạnh Nhi 1
Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 11/10/2007 Trần Hạnh Nhi 2
Nhiều tiến trình “chung sống hoà bình” trong hệ thống ? ĐỪNG HY VỌNG An toàn khi các tiến trình hoàn toàn độc lập Làm sao có được ?? Thực tế Các tiến trình chia sẻ tài nguyên chung ( file system, CPU ) Concurrent access => bugs. Ví dụ : Dê con qua cầu Xử lý đồng hành = nhức đầu 11/10/2007 Trần Hạnh Nhi 3
Các vấn đề Tranh chấp Nhiều tiến trình truy xuất đồng thời một tài nguyên mang bản chất không chia sẻ được Xảy ra vấn đề tranh đoạt điều khiển (Race Condition) Kết quả ? Khó biết , thường là sai Luôn luôn nguy hiểm ? Không, nhưng đủ để cân nhắc kỹ càng Phối hợp Các tiến trình không biết tương quan xử lý của nhau để điều chỉnh hoạt động nhịp nhàng Cần phối hợp xử lý (Rendez-vous) Kết quả : khó biết, không bảo đảm ăn khớp 11/10/2007 Trần Hạnh Nhi 4
Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 11/10/2007 Trần Hạnh Nhi 5
Tranh đoạt điều khiển (Race condition) - Ví dụ Đếm số người vào Altavista : dùng 2 threads cập nhật biến đếm hits=> P1 và P2 chia sẻ biến hits hits = 0 P1 P2 hits = hits +1; hits = hits + 1; Kết quả cuối cùng là bao nhiêu ? 11/10/2007 Trần Hạnh Nhi 6
Tranh đoạt điều khiển (Race condition) - Ví dụ hits = 0 P2 time P1 (1) read hits (0) (2)read hits (0) (3) hits = 0 + 1 (4)hits = 0 + 1 hits = 1 11/10/2007 Trần Hạnh Nhi 7
Tranh đoạt điều khiển (Race condition) - Ví dụ hits = 0 P2 time P1 (1) read hits (0) (2) hits = 0 + 1 (3) read hits (1) hits = 2 (4) hits = 1 + 1 11/10/2007 Trần Hạnh Nhi 8
Tranh đoạt điều khiển (Race condition) - Ví dụ (tt) i=0; Thread a: Thread b: while(i -10) i = i +1; i = i - 1; print “A won!”; print “B won!”; Ai thắng ? Có bảo đảm rằng sẽ có người thắng ? Nếu mỗi tiến trình xử lý trên 1 CPU thì sao ? 11/10/2007 Trần Hạnh Nhi 9
Tranh đoạt điều khiển (Race condition)-Nhận xét Kết quả thực hiện tiến trình phụ thuộc vào kết quả điều phối Cùng input, không chắc cùng output Khó debug lỗi sai trong xử lý đồng hành Xử lý Làm lơ Dễ , nhưng có phải là giải pháp Không chia sẻ tài nguyên chung : dùng 2 biến hits1,hits2; xây cầu 2 lane Nên dùng khi có thể, nhưng không bao giờ có thể đảm bảo đủ tài nguyên, và cũng không là giải pháp đúng cho mọi trường hợp Giải pháp tổng quát : có hay không ? Lý do xảy ra Race condition ? Bad interleavings : một tiến trình “xen vào” quá trình truy xuất tài nguyên của một tiến trình khác Giải pháp : bảo đảm tính atomicity cho phép tiến trình hoàn tất trọn vẹn quá trình truy xuất tài nguyên chung trước khi có tiến trình khác can thiệp 11/10/2007 Trần Hạnh Nhi 10
Atomicity : loại bỏ Race Condition hits = 0 P2 time P1 read hits (0) hits = 0 + 1 read hits(1) hits = 1 + 1 hits = 2 11/10/2007 Trần Hạnh Nhi 11
Miền găng (Critical Section) & Khả năng độc quyền (Mutual Exclusion) Miền găng (CS) là đoạn chương trình có khả năng gây ra hiện tượng race condition P1 P2 printf(“Welcome”); printf(“Welcome”); CS hits = hits + 1 hits = hits + 1 CS printf(“Bye”); printf(“Bye”); (Hỗ trợ Atomicity : Cần bảo đảm tính “độc quyền truy xuất” (Mutual Exclusion) cho miền găng (CS) 11/10/2007 Trần Hạnh Nhi 12
Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 11/10/2007 Trần Hạnh Nhi 13
Phối hợp hoạt động P2 P1 (2) Send(“yêu”); (1) Send(“Anh”); P3 P4 (3) Send(“em”); (4) Send(“Không”); 11/10/2007 Trần Hạnh Nhi 14
Chuyện gì đã xảy ra ? P1 P3 (1) Send(“Anh”); (3) Send(“em”); P2 P4 (2) Send(“yêu”); (4) Send(“Không”); P3 P2 (3) printf(“em”); (2) Send(“yêu”); P4 P1 (4) Send(“Không”); (1)Send(“Anh”);
Phối hợp xử lý P1 P2 Job1; Job2; Làm thế nào bảo đảm trình tự thực hiện Job1 - Job2 ? P1 và P2 thực hiện “hẹn hò” (Rendez-vous) với nhau Hỗ trợ Rendez-vous : Bảo đảm các tiến trình phối hợp với nhau theo 1 trình tự xử lý định trước. 11/10/2007 Trần Hạnh Nhi 16
Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 11/10/2007 Trần Hạnh Nhi 17
Bài toán đồng bộ hoá (Synchronization) Nhiều tiến trình chia sẻ tài nguyên chung đồng thời : Tranh chấp Race Condition Nhu cầu “độc quyền truy xuất” (Mutual Exclusion) Các tiến trình phối hợp hoạt động : Tương quan diễn tiến xử lý ? Nhucầu“hòhẹn”(Rendez-vous) Thực hiện đồng bộ hoá : Lập trình viên đề xuất chiến lược Các tiến trình liên quan trong bài toán phải tôn trọng các luậtđồng bộ Giải pháp sử dụng các cơ chế đồng bộ : Do lập trình viên /phần cứng / HĐH / NNLT cung cấp 11/10/2007 Trần Hạnh Nhi 18
Mô hình đảm bảo Mutual Exclusion Nhiệm vụ của lập trình viên: Thêm các đoạn code đồng bộ hóa vào chương trình gốc Thêm thế nào : xem mô hình sau Kiểm tra và dành quyền vào CS CS; Từ bỏ quyền sử dụng CS 11/10/2007 Trần Hạnh Nhi 19
Mô hình tổ chức phối hợp giữa hai tiến trình Nhiệm vụ của lập trình viên: Thêm các đoạn code đồng bộ hóa vào 2 chương trình gốc Thêm thế nào : xem mô hình sau P1 P2 Job1; Chờ ; Báo hiệu ; Job2; Nhiều tiến trình hơn thì sao ? Không có mô hình tổng quát Tùy thuộc bạn muốn hẹn hò ra sao ☺ 11/10/2007 Trần Hạnh Nhi 20
Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy wating Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 11/10/2007 Trần Hạnh Nhi 21
Giải pháp đồng bộ hoá Một phương pháp giải quyết tốt bài toán đồng bộ hoá cần thoả mản 4 điều kiện sau: Mutual Exclusion : Không có hai tiến trình cùng ở trong miền găng cùng lúc. Progess : Một tiến trình tạm dừng bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng Bounded Waiting : Không có tiến trình nào phải chờ vô hạn để được vào miền găng. Không có giả thiết nào đặt ra cho sự liên hệ về tốc độ của các tiến trình, cũng như về số lượng bộ xử lý trong hệ thống. 11/10/2007 Trần Hạnh Nhi 22
Các giải pháp đồng bộ hoá Nhóm giải pháp Busy Waiting Phần mềm Sử dụng các biến cờ hiệu Sử dụng việc kiểm tra luân phiên Giải pháp của Peterson Phần cứng Cấm ngắt Chỉ thị TSL Nhóm giải pháp Sleep & Wakeup Semaphore Monitor Message 11/10/2007 Trần Hạnh Nhi 23
Các giải pháp “Busy waiting” While (chưa có quyền) donothing() ; CS; Từ bỏ quyền sử dụng CS Tiếp tục tiêu thụ CPU trong khi chờ đợi vào miền găng Không đòi hỏi sự trợ giúp của Hệ điều hành 11/10/2007 Trần Hạnh Nhi 24
Nhóm giải pháp Busy-Waiting Các giải pháp Busy Waiting Các giải pháp phần mềm Giải pháp biến cờ hiệu Giải pháp kiểm tra luân phiên Giải pháp Peterson Phần cứng Cấm ngắt Chỉ thị TSL 11/10/2007 Trần Hạnh Nhi 25
Giải pháp phần mềm 1: Sử dụng biến cờ hiệu int lock = 0 P0 P1 NonCS; NonCS; while (lock == 1); // wait while (lock == 1); // wait lock = 1; lock = 1; CS; CS; lock = 0; lock = 0; NonCS; NonCS; 11/10/2007 Trần Hạnh Nhi 26
Giải pháp phần mềm 1: Tình huống int lock = 0 P0 P1 NonCS; NonCS; while (lock == 1); // wait while (lock == 1); // wait lock = 1; lock = 1; CS; CS; lock = 0; lock = 0; NonCS; NonCS; 11/10/2007 Trần Hạnh Nhi 27
Nhận xét Giải pháp phần mềm 1: Biến cờ hiệu Có thể mở rộng cho N tiến trình Không bảo đảm Mutual Exclusion Nguyên nhân ? while ( lock == 1); // wait CS ! Bị ngắt xử lý lock = 1; Tài nguyên dùng chung Bản thân đoạn code kiểm tra và dành quyền cũng là CS ! 11/10/2007 Trần Hạnh Nhi 28
Giải pháp phần mềm 2 : Kiểm tra luân phiên int turn = 1 P0 P1 NonCS; NonCS; while (turn !=0); // wait while (turn != 1); // wait CS; CS; turn = 1; turn = 0; NonCS; NonCS; 11/10/2007 Trần Hạnh Nhi 29
Giải pháp phần mềm 2 : Tình huống int turn = 1 P0 P1 turn ==1 CS; Wait turn = 0; CS; NonCS turn = 1 NonCS; CS ? (turn ==1) P0 không vào được CS lần 2 khi P1 dừng trong NonCS ! 11/10/2007 Trần Hạnh Nhi 30
Nhận xét Giải pháp 2: Kiểm tra luân phiên Chỉ dành cho 2 tiến trình Bảo đảm Mutual Exclusion Chỉ có 1 biến turn, tại 1 thời điểm chỉ cho 1 tiến trình turn vào CS Không bảo đảm Progress Nguyên nhân ? “Mờ của” cho người = “Đóng cửa” chính mình ! 11/10/2007 Trần Hạnh Nhi 31
Giải pháp phần mềm 3 : Peterson’s Solution Kết hợp ý tưởng của 1 & 2, các tiến trình chia sẻ: int turn; //đến phiên ai int interest[2] = FALSE; //interest[i] = T : Pi muốn vào CS Pi NonCS; j = 1 – i; interest[i] = TRUE; turn = j; while (turn==j && interest[j]==TRUE); CS; interest[i] = FALSE; NonCS; 11/10/2007 Trần Hạnh Nhi 32
Giải pháp phần mềm 3 : Peterson Pj NonCS; i = 1 – j; interest[j] = TRUE; turn = i; while (turn==i && interest[i]==TRUE); CS; interest[j] = FALSE; NonCS; 11/10/2007 Trần Hạnh Nhi 33
Nhận xét giải pháp phần mềm 3: Peterson Là giải pháp phần mềm đáp ứng được cả 3 điều kiện Mutual Exclusion : Pi chỉ có thể vào CS khi: interest[j] == F hay turn == i Nếu cả 2 muốn về thì do turn chỉ có thể nhận giá trị 0 hay 1 nên chỉ có 1 tiến trình vào CS Progress Sử dụng 2 biến interest[i] riêng biệt => trạng thái đối phương không khoá mình được Bounded Wait : interest[i] và turn đều có thay đổi giá trị Không thể mở rộng cho N tiến trình 11/10/2007 Trần Hạnh Nhi 34
Nhận xét chung về các giải pháp phần mềm trong nhóm Busy-Waiting Không cần sự hỗ trợ của hệ thống Dễ sai, Khó mở rộng Giải pháp 1 nếu có thể được hỗ trợ atomicity thì sẽ tốt Nhờ đến phần cứng ? 11/10/2007 Trần Hạnh Nhi 35
Nhóm Busy-Waiting - Các giải pháp phần cứng Các giải pháp Busy Waiting Các giải pháp phần mềm Giải pháp biến cờ hiệu Giải pháp kiểm tra luân phiên Giải pháp Peterson Các giải pháp phần cứng Cấm ngắt Test&Set lock Instruction 11/10/2007 Trần Hạnh Nhi 36
Nhóm Busy-Waiting - Giải pháp phần cứng 1: Cấm ngắt NonCS; Disable Interrupt; CS; Enable Interrupt; NonCS; Disable Interrupt : Cấm mọi ngắt, kể cả ngắt đồng hồ Enable Interrupt : Cho phép ngắt 11/10/2007 Trần Hạnh Nhi 37
Giải pháp phần cứng 1: Cấm ngắt Thiếu thận trọng Nếu tiến trình bị khoá trong CS ? System Halt Cho phép tiến trình sử dụng một lệnh đặc quyền Quá liều ! Máy có N CPUs ? Không bảo đảm được Mutual Exclusion 11/10/2007 Trần Hạnh Nhi 38
Nhóm Busy-Waiting - Giải pháp phần cứng 2: chỉ thị TSL() CPU hỗtrợprimitive Test and Set Lock Trả về giá trị hiện hành của 1 biến, và đặt lại giá trị True cho biến Thực hiện một cách không thể phân chia TSL (boolean &target) { TSL = target; target = TRUE; } 11/10/2007 Trần Hạnh Nhi 39
Aùp dụng TSL int lock = 0 Pi NonCS; while (TSL(lock)); // wait CS; lock = 0; NonCS; 11/10/2007 Trần Hạnh Nhi 40
Nhận xét chung các giải pháp phần cứng trong nhóm Busy- Waiting Cần được sự hỗ trợ của cơ chế phần cứng Không dễ, nhất là trên các máy có nhiều bộ xử lý Dễ mở rộng cho N tiến trình 11/10/2007 Trần Hạnh Nhi 41
Nhận xét chung cho các giải pháp trong nhóm Busy Waiting Sử dụng CPU không hiệu quả Liên tục kiểm tra điều kiện khi chờ vào CS Khắc phục KhoácáctiếntrìnhchưađủđiềukiệnvàoCS, nhường CPU cho tiến trình khác Phải nhờ đến Scheduler Wait and See 11/10/2007 Trần Hạnh Nhi 42
Các giải pháp đồng bộ hoá Nhóm giải pháp Busy Waiting Phần mềm Sử dụng các biến cờ hiệu Sử dụng việc kiểm tra luân phiên Giải pháp của Peterson Phần cứng Cấm ngắt Chỉ thị TSL Nhóm giải pháp Sleep & Wakeup Semaphore Monitor Message 11/10/2007 Trần Hạnh Nhi 43
Các giải pháp “Sleep & Wake up” if (chưa có quyền) Sleep() ; CS; Wakeup( somebody); Từ bỏ CPU khi chưa được vào CS Khi CS trống, sẽ được đánh thức để vào CS Cần được Hệ điều hành hỗ trợ Vì phải thay đổi trạng thái tiến trình 11/10/2007 Trần Hạnh Nhi 44
Ý tưởng Hệ Điều hành hỗ trợ 2 primitive : Sleep() : Tiến trình gọi sẽ nhận trạng thái Blocked WakeUp(P): Tiến trình P nhận trạng thái Ready Áp dụng Sau khi kiểm tra điều kiện sẽ vào CS hay gọi Sleep() tùy vào kết quả kiểm tra Tiến trình vừa sử dụng xong CS sẽ đánh thức các tiến trình bị Blocked trước đó 11/10/2007 Trần Hạnh Nhi 45
Áp dụng Sleep() and Wakeup() int busy; // busy ==0 : CS trống int blocked; // đếm số tiến trình bị Blocked chờ vào CS if (busy) { blocked = blocked + 1; Sleep(); } else busy = 1; CS; busy = 0; if(blocked) { WakeUp(P); blocked = blocked - 1; } 11/10/2007 Trần Hạnh Nhi 46
Vấn đề với Sleep & WakeUp P1 blocked P1 P2 vĩnh viễn if (busy) { if (busy) { blocked = blocked + 1; blocked = blocked + 1; Sleep(); Sleep(); } } else busy = 1; else busy = 1; WakeUp CS; bị “lạc” CS; busy = 0; busy = 0; if(blocked) { if(blocked) { WakeUp(P); WakeUp(P); blocked = blocked - 1; blocked = blocked - 1; } } Nguyên nhân : Việc kiểm tra điều kiện và động tác từ bỏ CPU có thể bị ngắt quãng Bản thân các biến cờ hiệu không được bảo vệ 11/10/2007 Trần Hạnh Nhi 47
Cài đặt các giải pháp Sleep & WakeUp ? Hệ điều hành cần hỗ trợ các cơ chế cao hơn Dựa trên Sleep&WakeUp Kết hợp các yếu tố kiểm tra Thi hành không thể phân chia Nhóm giải pháp Sleep & Wakeup Semaphore Monitor Message 11/10/2007 Trần Hạnh Nhi 48
Giải pháp Sleep & Wakeup 1: Semaphore Được đề nghị bởi Dijkstra năm 1965 Các đặc tính : Semaphore s; Có 1 giá trị Semaphore s; // s >=0 Chỉ được thao tác bởi 2 primitives : Down(s) Up(s) Các primitive Down và Up được thực hiện không thể phân chia 11/10/2007 Trần Hạnh Nhi 49
Cài đặt Semaphore (Sleep & Wakeup) Giá trị bên trong của semaphore typedef struct { int value; struct process* L; Danh sách các tiến trình đang } Semaphore ; bị block đợi semaphore nhận giá trị dương Semaphore được xem như là một resource Các tiến trình “yêu cầu” semaphore : gọi Down(s) Nếu không hoàn tất được Down(s) : chưa được cấp resource Blocked, được đưa vào s.L Cần có sự hỗ trợ của HĐH Sleep() & Wakeup() 11/10/2007 Trần Hạnh Nhi 50
Cài đặt Semaphore (Sleep & Wakeup) Down (S) Up(S) { { S.value ; S.value ++; if S.value < 0 if S.value ≤ 0 { { Add(P,S.L); Remove(P,S.L); Sleep(); Wakeup(P); } } } } 11/10/2007 Trần Hạnh Nhi 51
Sử dụng Semaphore Tổ chức “độc quyền truy xuất” Pi Down (s) Semaphore s = ?1 CS; Up(s) Tổ chức “hò hẹn” P1 : P2: Semaphore s = ?0 Job1; Down (s); Up(s) Job2; 11/10/2007 Trần Hạnh Nhi 52
Nhận xét Semaphores Là một cơ chế tốt để thực hiện đồng bộ Dễ dùng cho N tiến trình Nhưng ý nghĩa sử dụng không rõ ràng MutualExclusion : Down & Up Rendez-vous : Down & Up Chỉ phân biệt qua mô hình Khó sử dụng đúng Nhầm lẫn 11/10/2007 Trần Hạnh Nhi 53
Giải pháp Sleep & Wakeup 2: Monitor Đề xuất bởi Hoare(1974) & Brinch (1975) Là cơ chế đồng bộ hoá do NNLT cung cấp Hỗ trợ cùng các chức năng như Semaphore Dễ sử dụng và kiểm soát hơn Semaphore Bảo đảm Mutual Exclusion một cách tự động Sử dụng biến điều kiện để thực hiện Synchronization 11/10/2007 Trần Hạnh Nhi 54
Monitor : Ngữ nghĩa và tính chất(1) Monitor M Share variable: i,j; Là một module chương trình định nghĩa Các CTDL, đối tượng dùng chung Các phương thức xử lý các đối tượng này Bảo đảm tính encapsulation Các tiến trình muốn truy xuất dữ liệu MethodA bên trong monitor phải dùng các phương MethodB thức của monitor : MethodC i=0 P1 : M.C() // i=5 prinf(j)i=5 P2: M.B() // printf(j) 11/10/2007 Trần Hạnh Nhi 55
Monitor : Ngữ nghĩa và tính chất(2) Entry queue P6 P7 P8 Share variable: i,j; Tự động bảo đảm Mutual Exclusion Tại 1 thời điểm chỉ có 1 tiến trình được thực hiện các phương thức của Monitor Các tiến trình không thể vào Monitor sẽ được đưa vào Entry queue của Monitor MethodA Ví dụ MethodB P1 : M.A(); i = 0 MethodC P6 : M.B(); printf(i) P7 : M.A(); i=5 P8 : M.C(); P1 11/10/2007 Trần Hạnh Nhi 56
Monitor : Ngữ nghĩa và tính chất(3) Entry queue P6 P7 P8 Share variable: i,j; Hỗ trợ Synchronization với các condition Condition variable: variables C1: P2 P4 P1 Wait(c) : Tiến trình gọi hàm sẽ bị blocked C2: P3 P5 Signal(c): Giải phóng 1 tiến trình đang bị blocked trên biến điều kiện c MethodA C.queue : danhsáchcáctiếntrìnhblocked MethodB trên c i=0; signal(c1)MethodC Trạng thái tiến trình sau khi gọi Signal? P1 Blocked. Nhường quyền vào monitor cho tiến wait(C1); trình được đánh thức i=5 signal(C2 ); Tiếp tục xử lý hết chu kỳ, rồi blocked 11/10/2007 Trần Hạnh Nhi 57
Sử dụng Monitor Tổ chức “độc quyền truy xuất” Monitor M Pi RC; M.AccessMutual(); //CS Function AccessMutual CS; // access RC Tổ chức “hò hẹn” Monitor M Condition c; Function F1 Job1; P1 : P2: Signal(c); M.F1(); M.F2(); Function F2 Wait(c); Job2; 11/10/2007 Trần Hạnh Nhi 58
Giải pháp Sleep & Wakeup 3: Message Được hỗ trợ bởi HĐH Đồng bộ hóa trên môi trường phân tán 2 primitive Send & Receive Cài đặt theo mode blocking 1. Send Request 3. Send Finish Server P 2. Receive Accept 11/10/2007 Trần Hạnh Nhi 59
Nội dung bài giảng Xử lý đồng hành và các vấn đề: Vấn đề tranh đoạt điều khiển (Race Condition) Vấn đề phối hợp xử lý Bài toán đồng bộ hóa Yêu cầu độc quyền truy xuất (Mutual Exclusion) Yêu cầu phối hợp xử lý (Synchronization) Các giải pháp đồng bộ hoá Busy waiting Sleep & Wakeup Các bài toán đồng bộ hoá kinh điển Producer – Consumer Readers – Writers Dinning Philosophers 11/10/2007 Trần Hạnh Nhi 60
Bàitoánđồngbộkinhđiển1: Producer - Consumer (Bounded-Buffer Problem) Mô tả : 2 tiến trình P và C hoạt động đồng hành P sản xuất hàng và đặt vào Buffer C lấy hàng từ Buffer đi tiêu thụ Buffer có kích thước giới hạn P Tình huống BufferBuffer (N)(N) C P và C đồng thời truy cập Buffer ? P thêm hàng vào Buffer đầy ? C lấy hàng từ Buffer trống ? P không được ghi dữ liệu vào buffer đã đầy (Rendez-vous) C không được đọc dữ liệu từ buffer đang trống (Rendez-vous) P và C không được thao tác trên buffer cùng lúc (Mutual Exclusion) 11/10/2007 Trần Hạnh Nhi 61
Producer – Consummer : Giải pháp Semaphore Các biến dùng chung giữa P và C BufferSize = N; // số chỗ trong bộ đệm semaphore mutex = 1 ; // kiểm soát truy xuất độc quyền semaphore empty = BufferSize; // số chỗ trống semaphore full = 0; // số chỗ đầy int Buffer[BufferSize]; // bộ đệm dùng chung 11/10/2007 Trần Hạnh Nhi 62
Producer – Consummer : Giải pháp Semaphore Producer() Consumer() { { int item; int item; while (TRUE) while (TRUE) { { produce_item(&item); down(&full); down(&empty); down(&mutex); down(&mutex) remove_item(&item,Buffer); enter_item(item,Buffer); up(&mutex); up(&mutex); up(&empty); up(&full); consume_item(item); } } } } 11/10/2007 Trần Hạnh Nhi 63
P&C - Giải pháp Semaphore: Thinking Producer() Consumer() { { int item; int item; while (TRUE) while (TRUE) { { produce_item(&item); down(&mutex); down(&mutex) down(&full); down(&empty); remove_item(&item,Buffer); enter_item(item,Buffer); up(&mutex); up(&mutex); up(&empty); up(&full); consume_item(item); } } } } 11/10/2007 Trần Hạnh Nhi 64
Producer – Consummer : Giải pháp Monitor monitor ProducerConsumer procedure remove(); condition full, empty; { int Buffer[N], count; if (count == 0) procedure enter(); wait(empty) { remove_item(&item,Buffer); if (count == N) count ; wait(full); if (count == N-1) enter_item(item,Buffer); signal(full); count ++; } if (count == 1) count = 0; signal(empty); end monitor; } 11/10/2007 Trần Hạnh Nhi 65
Producer – Consummer : Giải pháp Monitor Producer() Consumer(); { { int item; int item; while (TRUE) while (TRUE) { { produce_item(&item); ProducerConsumer.remove; ProducerConsumer.enter; consume_item(item); } } } } 11/10/2007 Trần Hạnh Nhi 66
Producer – Consummer : Giải pháp Message Producer() Consumer(); { { int item; int item; message m; Coi chừng message m; Deadlock for(0 to N) send(producer, Request); while (TRUE) while (TRUE) { { produce_item(&item); receive(producer, &m); receive(consumer, Request); remove_item(&m,&item); create_message(&m, item); send(producer, Request); send(consumer,&m); consumer_item(item); } } } } 11/10/2007 Trần Hạnh Nhi 67
Bài toán đồng bộ hoá kinh điển 2: Readers & Writers R2 Mô tả : N tiến trình Ws và Rs hoạt động đồng hành R3 Rs và Ws chia sẻ CSDL R1 W cập nhật nội dung CSDL W1 W2 Rs truy cập nội dung CSDL Tình huống Các Rs cùng truy cập CSDL ? Database W đang cập nhật CSDL thì các Rs truy cập CSDL ? Các Rs đang truy cập CSDL thì W muốn cập nhật CSDL ? W không được cập nhật dữ liệu khi có ít nhất một R đang truy xuất CSDL (ME) Rs không được truy cập CSDL khi một W đang cập nhật nội dung CSDL (ME) Tại một thời điểm , chỉ cho phép một W được sửa đổi nội dung CSDL (ME) 11/10/2007 Trần Hạnh Nhi 68
Readers-Writers với “active readers” 11/10/2007 Trần Hạnh Nhi 69
Readers-writers với một “active writer” 11/10/2007 Trần Hạnh Nhi 70
Ưu tiên ai hơn đây ? 11/10/2007 Trần Hạnh Nhi 71
Readers & Writers W độc quyền truy xuất CSDL W hiện tại kết thúc cập nhật CSDL : ai vào ? Cho W khác vào, các Rs phải đợi Ưu tiên Writer, Reader có thể starvation Cho các Rs vào, Ws khác phải đợi Ưu tiên Reader, Writer có thể starvation 11/10/2007 Trần Hạnh Nhi 72
Readers & Writers : Giải pháp Semaphore Các biến dùng chung giữa Rs và Ws semaphore db = 1; // Kiểm tra truy xuất CSDL 11/10/2007 Trần Hạnh Nhi 73
R&W : Giải pháp Semaphore (1) Reader() Writer() { { down(&db); down(&db); read-db(Database); write-db(Database); up(&db); up(&db); } } Chuyện gì xảy ra ? Chỉ có 1 Reader được đọc CSDL tại 1 thời điểm ! 11/10/2007 Trần Hạnh Nhi 74
R&W : Giải pháp Semaphore (2) Reader() Writer() { { rc = rc +1; down(&db); if (rc ==1) write-db(Database); down(&db); up(&db); read-db(Database); } rc = rc – 1; Đúng chưa ? if (rc == 0) up(&db); rc là biến dùng chung giữa các Reader } CS đó 11/10/2007 Trần Hạnh Nhi 75
Readers & Writers : Giải pháp Semaphore Các biến dùng chung giữa Rs và Ws semaphore db = 1; // Kiểm tra truy xuất CSDL Các biến dùng chung giữa Rs int rc; // Số lượng tiến trình Reader semaphore mutex = 1; // Kiểm tra truy xuất rc 11/10/2007 Trần Hạnh Nhi 76
R&W : Giải pháp Semaphore (3) Reader() Writer() { { down(&mutex); down(&db); rc = rc +1; write-db(Database); if (rc ==1) up(&db); down(&db); } up(mutex); read-db(Database); down(mutex); Ai được ưu tiên ? rc = rc – 1; if (rc == 0) up(&db); up(mutex); } 11/10/2007 Trần Hạnh Nhi 77
R&W : Giải pháp Semaphore (Thinking ) Reader() Writer() { { down(&mutex); down(&db); rc = rc +1; write-db(Database); up(mutex); up(&db); if (rc ==1) } down(&db); read-db(Database); down(mutex); ??? hê, hê, hê ☺ rc = rc – 1; up(mutex); if (rc == 0) up(&db); } 11/10/2007 Trần Hạnh Nhi 78
R&W: Giải pháp Monitor monitor ReaderWriter procedure W1(); ? Database; { procedure R1(); } { procedure W (); } { procedure R (); } { } 11/10/2007 Trần Hạnh Nhi 79
monitor ReaderWriter procedure BeginWrite() { condition OKWrite, OKRead; if (busy || rc != 0) int rc = 0; wait(OKWrite); Boolean busy = false; busy = true; } procedure BeginRead() { procedure FinishWrite() if (busy) { wait(OKRead); busy = false; rc++; if (OKRead.Queue) signal(OKRead); signal(OKRead); } else procedure FinishRead() signal(OKWrite); { } rc ; end monitor; if (rc == 0) signal(OKWrite); }
Reader&Writer : Giải pháp Monitor Reader() Writer(); { { RW.BeginRead(); RW.BeginWrite(); Read-db(Database); Write-db(Database); RW.FinishRead(); RW.FinishWrite(); } } 11/10/2007 Trần Hạnh Nhi 81
Bài toán đồng bộ hoá kinh điển 3: Bửa ăn của các Triết gia (Dining Philosophers) Năm triết gia ngồi chung quanh bàn ăn món spaghetti (yum yum) Trên bàn có 5 cái nĩa được đặt giữa 5 cái đĩa (xem hình) Để ăn món spaghetti mỗi người cần có 2 cái nĩa Triết gia thứ i: Thinking Eating Chuyện gì có thể xảy ra ? 11/10/2007 Trần Hạnh Nhi 82
Dining Philosophers : Tình huống nguy hiểm 2 triết gia “giành giật” cùng 1 cái nĩa Tranh chấp Cần đồng bộ hoá hoạt động của các triết gia 11/10/2007 Trần Hạnh Nhi 83
Dining Philosophers : Giải pháp đồng bộ semaphore fork[5] = 1; Philosopher (i) { while(true) { down(fork[i]); down(fork[i+1 mod 5]) eat; up(fork[i]); up(fork[i+1 mod 5]); think; Deadlock } 11/10/2007 Trần Hạnh Nhi 84
Dining Philosophers : Thách thức Cần đồng bộ sao cho: Không có deadlock Không có starvation 11/10/2007 Trần Hạnh Nhi 85
Bài giảng 6 : Quản lý bộ nhớ Tổng quan Nhu cầu bộ nhớ của tiến trình Các vấn đề về bộ nhớ Chuyển đổi địa chỉ Các công đoạn Các mô hình chuyển đổi địa chỉ Vai trò Quản lý bộ nhớ của HĐH Các yêu cầu Các mô hình tổ chức bộ nhớ Mô hình Liên tục Mô hình Không liên tục 4/6/2008 Trần Hạnh Nhi 1
Tổng quan : Nhu cầu về bộ nhớ của tiến trình Chương trình cần được nạp vào Bộ nhớ chính để thi hành CPU chỉ có thể truy xuất trực tiếp Main Memory Chương trình khi được nạp vaò BNC sẽ được tổ chức theo cấu trúc của tiến trình tương ứng Ai cấp phát BNC cho tiến trình ? Chương trình nguồn sử dụng địa chỉ symbolic Tiến trình thực thi truy cập điạ chỉ thực trong BNC Ai chuyển đổi địa chỉ ? HĐH Bộ phận Quản lý Bộ nhớ Mô hình tổ chức ? Cơ chế hỗ trợ Chiến lược thực hiện 4/6/2008 Trần Hạnh Nhi 2
Tổng quan : Các vấn đề về Bộ nhớ Cấp phát Bộ nhớ : Uniprogramming : Không khó Multiprogramming : BNC giới hạn, N tiến trình ? Bảovệ? Chiasẻ? Tiến trình thay đổi kích thước ? Tiến trình lớn hơn BNC ? Chuyển đổi địa chỉ tiến trình Thời điểm chuyển đổi địa chỉ ? Công thức chuyển đổi ? Phụ thuộc vào Mô hình tổ chức BNC ? Cần sự hỗ trợ của phần cứng ? Tiến trình thay đổi vị trí trong BNC ? 4/6/2008 Trần Hạnh Nhi 3
Ví dụ 0x9000 OS 0x7000 Môi trường đa nhiệm gcc 0x4000 nachos 0x3000 emacs 0x0000 Nếu nachos cần thêm không gian ? Nếu nachos có lỗi và thực hiện thao tác ghi vào địa chỉ 0x7100? Khi nào gcc biết rằng nó thường trú tại 0x4000? Nếu emacs cần nhiều bộ nhớ hơn dung lượng vật lý hiện có? 4/6/2008 Trần Hạnh Nhi 4
Các bước chuyển đổi chương trình C program: test.c Compiler Object:test.o Linker lib.o Executable: test.exe Loader Memory 4/6/2008 Trần Hạnh Nhi 5
Các bước chuyển đổi source program -> .exe
A.C B.C int x; F() OS int y; { x = 12; printf(“Hi”); y = 5; } F(); A.O B.O ? // F() 0 // x 0 -2 // F() ? // x 2 // y ? // y 4 // [0] = 12; ? // [?] = 12; ? // [?] = 5; 5 // [2] = 5; 0 // F() ? // jmp ? 6 // jmp F 3 // x //external // object 5 // y 7 // [3] = 12; 8 // [5] = 5; 9 // jmp 0 Test.exe
Thuật ngữ Địa chỉ logic – còn gọi là địa chỉ ảo , là tất cả các địa chỉ do bộxửlýtạo ra Địa chỉ physic - là địa chỉ thực tế mà trình quản lý bộ nhớ nhìn thấy và thao tác Không gian địa chỉ – là tập hợp tất cả các địa chỉ ảo phát sinh bởi một chương trình Không gian vật lý – là tập hợp tất cả các địa chỉ vật lý tương ứng với các địa chỉ ảo 4/6/2008 Trần Hạnh Nhi 8
Nhu cầu bộ nhớ của tiến trình low address system data segment (PCB) Tiếntrìnhgồmcĩ: code segment 8048314 : 8048314: push %ebp read from program file by exec code segment 8048315: mov %esp,%ebp usually read-only 8048317: mov 0xc(%ebp),%eax can be shared 804831a: add 0x8(%ebp),%eax initialized variables 804831d: pop %ebp data segment 804831e: ret initialized global variables (0 / NULL)804831f : uninitialized variables uninitialized global variables 804831f: push %ebp data segment heap 8048320: mov %esp,%ebp process A 8048322: sub $0x18,%esp dynamic memory 8048325: and $0xfffffff0,%esp heap segment data e.g., allocated using malloc 8048328: mov $0x0,%eax grows against higher addresses 804832d: sub %eax,%esp 804832f: movl $0x0,0xfffffffc(%ebp) stack segment 8048336: movl $0x2,0x4(%esp,1) variables in a function 804833e: movl $0x4,(%esp,1) y or stored register states (e.g. calling function8048345: call 8048314 em EIP) 804834a: mov %eax,0xfffffffc(%ebp) m d” grows against lower addresses 804834d: leave e us 804834e: ret n “u system data segment (PCB)804834f: nop segment pointers pid program and stack pointers Stack cho các thread possiblestack stacks for more threads high address 4/6/2008 Trần Hạnh Nhi 9
Logical and Physical Address Spaces 4/6/2008 Trần Hạnh Nhi 10
Truy xuất bộ nhớ Địa chỉ của Instruction và data trong program source code là symbolic: goto errjmp; X = A + B; Những địa chỉ symbolic này cần được liên kết (bound) với các địa chỉ thực trong bộ nhớ vật lý trước khi thi hành code Address binding: ánh xạ địa chỉ từ không gian địa chỉ (KGĐC) này vào KGĐC khác Thời điểm thực hiện address binding ? compile time load time execution time. 4/6/2008 Trần Hạnh Nhi 11
Thời điểm kết buộc địa chỉ ? Có thể thực hiện việc kết buộc địa chỉ tại 1 trong 3 thời điểm : Compile-time: Phát sinh địa chỉ tuyệt đối Phải biết trước vị trí nạp chương trình Phải biên dịch lại chương trình khi vị trí nạp thay đổi Load-time: Khi biên dịch chỉ phát sinh địa chỉ tương đối Khi nạp, biết vị trí bắt đầu sẽ tính lại địa chỉ tuyệt đối Phải tái nạp khi vị trí bắt đầu thay đổi Execution-time: Khi biên dịch,nạp chỉ phát sinh địa chỉ tuong đối Trì hoãn thời điểm kêt buộc địa chỉ tuyệt đối đến khi thi hành Khi đó ai tính toán địa chỉ tuyệt đối ? Phần cứng : MMU 4/6/2008 Trần Hạnh Nhi 12
Chuyển đổi địa chỉ MMU gcc Translation box Physical Load Store address Physical virtual legal addr? address Illegal? memory CPU error data 4/6/2008 Trần Hạnh Nhi 13
CPU, MMU and Memory 4/6/2008 Trần Hạnh Nhi 14
Yêu cầu quản lý bộ nhớ Tăng hiệu suất sử dụng CPU Cần hỗ trợ Multiprogramming Lưu trữ cùng lúc nhiều tiến trình trong BNC ? Các yêu cầu khi tổ chức lưu trữ tiến trình: 1. Relocation 2. Protection 3. Sharing 4. Logical Organization 5. Physical Organization 4/6/2008 Trần Hạnh Nhi 15
Tái định vị (Relocation) Không biết trước chương trình sẽ được nạp vào BN ở vị trí nào để xử lý. Một tiến trình có thể được di dời trong bộ nhớ sau khi đã nạp C Tiến trình tăng trưởng ? HĐH sắp xếp lại các tiến trình để có thể sử dụng BNC hiệu qủa hơn. 4/6/2008 Trần Hạnh Nhi 16
Bảo vệ (Protection) Không cho phép tiến trình truy cập đến các vị trí nhớ đã cấp cho tiến trình khác (khi chưa có phép). Không thể thực hiện việc kiểm tra hợp lệ tại thời điểm biên dịch hay nạp, vì chương trình có thể được tái định vị. Thực hiện kiểm tra tại thời điểm thi hành Cần sự hỗ trợ của phần cứng. 4/6/2008 Trần Hạnh Nhi 17
Chia sẻ (Sharing) Cần cho phép nhiều tiến trình tham chiếu đến cùng một vùng nhớ mà không tổn hại đến tính an toàn hệ thống : Tiết kiệm chổ lưu trữ cho các module dùng chung. Cho phép các tiến trình cộng tác có khả năng chia sẻ dữ liệu. 4/6/2008 Trần Hạnh Nhi 18
Tổ chức logic (Logical Organization) Người dùng viết chương trình gồm nhiều module, với các yêu cầu bảo vệ cho từng module có thể khác nhau: instruction modules : execute-only. data modules : read-only hay read/write. một số module là private, số khác có thể là public. OS cần hỗ trợ các cơ chế có thể phản ánh mô hình logic của chuơng trình 4/6/2008 Trần Hạnh Nhi 19
Tổ chức vật lý (Physical Organization) Cấp phát vùng nhớ vật lý sao cho hiệu quả Và dễ dàng chuyển đổi chương trình qua lại giữa BNC và BNP 4/6/2008 Trần Hạnh Nhi 20
Các mô hình tổ chức bộ nhớ Cấp phát Liên tục (Contigous Allocation) Linker – Loader Base & Bound Cấp phát Không liên tục (Non Contigous Allocation) Segmentation Paging 4/6/2008 Trần Hạnh Nhi 21
Cấp phát Liên tục (Contigous Allocation) Nguyên tắc : Chương trình được nạp toàn thể vào BNC để thi hành Cần một vùng nhớ liên tục, đủ lớn để chứa Chương trình Không gian địa chỉ : liên tục Không gian vật lý : có thể tổ chức Fixed partition Variable partition 2 mô hình đơn giản Linker – Loader Base & Bound 4/6/2008 Trần Hạnh Nhi 22
Fixed Partitioning Phân chia KGVL thành các partitions Có 2 cách phân chia partitions : kích thước bằng nhau kích thước khác nhau Mỗi tiến trình sẽ được nạp vào một partition để thi hành Chiến lược cấp phát partition ? 4/6/2008 Trần Hạnh Nhi 23
Chiến lược cấp phát partitions cho tiến trình Kích thước partition bằng nhau không có gì phải suy nghĩ ! Kích thước partition không bằng nhau : Sử dụng nhiều hàng đợi Cấp cho tiến trình partition với kích thước bé nhất (đủ lớn để chứa tiên trình) Khuyết điểm : phân bố các tiến trình vào các partition không đều, một số tiến trình phải đợi trong khi có partition khác trống 4/6/2008 Trần Hạnh Nhi 24
Chiến lược cấp phát partitions cho tiến trình Kích thước partition không bằng nhau : Sử dụng 1 hàng đợi Cấp cho tiến trình partition tự do với kích thước bé nhất (đủ lớn để chứa tiên trình) Cần dùng một CTDL để theo dõi các partition tự do 4/6/2008 Trần Hạnh Nhi 25
Nhận xét Fixed Partitioning Sử dụng BN không hiệu quả internal fragmentation : kích thước chương trình không đúng bằng kích thước partition Mức độ đa chương của hệ thống (Số tiến trình được nạp) bị giới hạn bởi số partitions P1 (2M) 3M internal frag P2 (4M) 8M internal frag 4/6/2008 Trần Hạnh Nhi 26
Dynamic Partitioning BNC không được phân chia trước P1 (2M) Các partition có kích thước tùy ý, P2 (4M) sẽ hình thành trong quá trình nạp các tiến trình vào hệ thống Mỗi tiến trình sẽ được cấp phát đúng theo kích thước yêu cầu không còn internal fragmentation 4/6/2008 Trần Hạnh Nhi 27
Dynamic Partitioning: tình huống P1 (2M) external P2 (4M) fragmentation P4 (1.5M) P3 (8M) 2M Chọn lựa partition để cấp phát cho tiến trình ? Đồng thời có nhiều partition tự do đủ lớn để chứa tiến trình Dynamic Allocation problem Tiến trình vào sau không lấp đầy chỗ trống tiến trình trước để lại external fragmentation
Ví dụ Dynamic Partitioning 4/6/2008 Trần Hạnh Nhi 29
Ví dụ Dynamic Partitioning 4/6/2008 Trần Hạnh Nhi 30
Giải quyết vấn đề Dynamic Allocation Các chiến lược thông dụng để chọn partition: First-fit: chọn partition tự do đầu tiên Best-fit: chọn partition tự do nhỏ nhất đủ chứa tiến trình Worst-fit: chọn partition tự do lớn nhất đủ chứa tiến trình 2M First Fit P1 P3 (1M) 8M Worst Fit P2 1.5M Best Fit 4/6/2008 Trần Hạnh Nhi 31
Memory Compaction (Garbage Collection) Giải quyết vấn đề External Fragmentation : Dồn các vùng bị phân mảnh lại với nhau để tạo thành partition liên tục đủ lớn để sử dụng Chi phí thực hiện cao 2M External P1 fragmentations 1M P2 1.5M 4/6/2008 Trần Hạnh Nhi 32
Các mô hình chuyển đổi địa chỉ Fixed/Dynamic partition là mô hình tổ chức nạp tiến trình vào KGVL Cần có mô hình để chuyển đổi địa chỉ từ KGĐC vào KGVL Linker Loader Base & Bound 4/6/2008 Trần Hạnh Nhi 33
Mô hình Linker-Loader OS test.exe 0x4000 0x7000 test.exe jump 0x5000 jump 0x2000 0x3000 0x0000 (base) Tại thời điểm Link, giữ lại các địa chỉ logic Vị trí base của tiến trình trong bộ nhớ xác định được vào thời điểm nạp : địa chỉ physic = địa chỉ logic + base 4/6/2008 Trần Hạnh Nhi 34
Nhận xét mô hình Linker-Loader Không cần sự hỗ trợ phần cứng để chuyển đổi địa chỉ Loader thực hiện Bảo vệ ? Không hỗ trợ Dời chuyển sau khi nạp ? Không hỗ trợ tái định vị Phải nạp lại ! 4/6/2008 Trần Hạnh Nhi 35
Mô hình Base & Bound OS Test.exe Bound 0x4000 Test.exe 0x7000 jump 0x2000 jump 0x2000 Base 0x0000 0x3000 Tại thời điểm Link, giữ lại các địa chỉ logic Vị trí base , bound được ghi nhận vào 2 thanh ghi: Kết buộc địa chỉ vào thời điểm thi hành => tái định vị được : địa chỉ physic = địa chỉ logic + base register Bảo vệ : địa chỉ hợp lệ ⊆ [base, bound] 4/6/2008 Trần Hạnh Nhi 36
Nhận xét mô hình Base & Bound Kết buộc địa chỉ tại thời điểm thi hành => cần hỗ trợ của phần cứng physical logical addrs addrs MMU memory CPU + base reg Hỗ trợ Bảo vệ Tái định vị 4/6/2008 Trần Hạnh Nhi 37
Khuyết điểm của cấp phát liên tục Không có vùng nhớ liên tục đủ lớn để nạp tiến trình ? Bó tay Sử dụng BNC không hiệu qua”! 1M P1 P3 (9M) 8M P2 1M 4/6/2008 Trần Hạnh Nhi 38
Các mô hình tổ chức bộ nhớ Cấp phát Liên tục (Contigous Allocation) Linker – Loader Base & Bound Cấp phát Không liên tục (Non Contigous Allocation) Segmentation Paging 4/6/2008 Trần Hạnh Nhi 39
Các mô hình cấp phát không liên tục Cho phép nạp tiến trình vào BNC ở nhiều vùng nhớ không liên tục Không gian địa chỉ : phân chia thành nhiều partition Segmentation Paging Không gian vật lý : có thể tổ chức Fixed partition : Paging Variable partition : Segmentation 4/6/2008 Trần Hạnh Nhi 40
Segmentation Lập trình viên : chương trình là một tập các segments Một segment là một đơn vị chương trình gồm các đối tượng có cùng nhóm ngữ nghĩa Ví dụ : main program, procedure, function, local variables, global variables,common block,stack, symbol table, arrays Các segment có thể có kích thước khác nhau Mô hình Segmentation : KGĐC : phân chia thành các segment KGVL : tổ chức thành dynamic partitions Nạp tiến trình : Mỗi segment cần được nạp vào một partition liên tục, tự do, đủ lớn cho segment partition nào ? Dynamic Allocation ! Các segment của cùng 1 chương trình có thể được nạp vào những partition không liên tục 4/6/2008 Trần Hạnh Nhi 41
Mô hình Segmentation int m; heap main () { F1(m); stack } data F1(int x) (m) { x = 9; code } (main,F1) Quản lýKGDC địa chỉ ? KGVL 4/6/2008 Trần Hạnh Nhi 42
Tổ chức Segmentation Điạ chỉ logic : Địa chỉ physic : Chuyển đổi địa chỉ : Chuyển đổi địa chỉ vào thời điểm thi hành MMU thi hành Sử dụng Segment Table (bảng phân đoạn) để lưu thông tin cấp phát BNC, làm cơ sở thực hiện ánh xạ địa chỉ Mỗi tiến trình có một Segment Table Sâegment Table: Số phần tử của Segment Table = Số Segment của chương trình Mỗi phần tử của Segment Table mô tả cho 1 segment, và có cấu trúc : base: địa chỉ vật lý trong BNC của partition chứa segment limit : kích thước segment Lưu trữ Segment Table ? Cache : nếu đủ nhỏ BNC : Segment-table base register (STBR), Segment-table length register (STLR) 4/6/2008 Trần Hạnh Nhi 43
Chuyển đổi địa chỉ trong mô hình Segmentation fault Logical Addr no mem yes 3 128 ? + 0x1000 Seg# offset Seg table 128 seg base limit 0 1 2 3 0x1000 512 4/6/2008 Trần Hạnh Nhi 44
Logical-to-Physical Address Translation in segmentation 4/6/2008 Trần Hạnh Nhi 45
Nhận xét Mô hình Segmentation Cấp phát không liên tục => tận dụng bộ nhớ hiệu quả Hỗ trợ tái định vị Từng Segment Hỗ trợ Bảo vệ và Chia sẻ được ở mức module Ý nghĩa của “mức module” ? Chuyển đổi địa chỉ phức tạp ☺ Đã có MMU Sử dụng dynamic partition : chịu đựng Dynamic Allocation : chọn vùng nhớ để cấp cho một segment ☺ First fit, Best fit, Worst fit External Fragmentation : Memory Compaction : chi phí cao 4/6/2008 Trần Hạnh Nhi 46
Sharing of Segments: Text Editor 4/6/2008 Trần Hạnh Nhi 47
Paging Hỗ trợ HĐH khắc phục bài toán cấp phát bộ nhớ động, và loại bỏ external fragmentation Mô hình Paging : KGĐC : phân chia chương trình thành các page có kích thước bằng nhau Không quan tâm đến ngữ nghĩa của các đối tượng nằm trong page KGVL : tổ chức thành các fixed partitions có kích thước bằng nhau gọi là frame page size = frame size Nạp tiến trình : Mỗi page cần được nạp vào một frame tự do Các pages của cùng 1 chương trình có thể được nạp vào những frames không kế cận nhau. Tiến trình kích thước N pages -> cần N frame tự do để nạp 4/6/2008 Trần Hạnh Nhi 48
Mô hình Paging int m; int m; main () main () { F1(int x) F1(m); } stack F1(int x) { x = 9; heap } KGDC Quản lý địa chỉ ? KGVL 4/6/2008 Trần Hạnh Nhi 49
Tổ chức Paging Điạ chỉ logic : Địa chỉ physic : Chuyển đổi địa chỉ : Chuyển đổi địa chỉ vào thời điểm thi hành MMU thi hành Sử dụng Page Table để lưu thông tin cấp phát BNC, làm cơ sở thực hiện ánh xạ địa chỉ Mỗi tiến trình có một Page Table Page Table Số phần tử của Page Table = Số Page trong KGĐC của chương trình Mỗi phần tử của bảng Page Table mô tả cho 1 page, và có cấu trúc : frame: số hiệu frame trong BNC chứa page Lưu trữ Page Table ? Cache : không đủ BNC : Page-table base register (PTBR), Page-table length register (PTLR) 4/6/2008 Trần Hạnh Nhi 50
Chuyển đổi địa chỉ trong mô hình Paging Logical Physical addr addr CPU p d f d KGVL f Page table 4/6/2008 Trần Hạnh Nhi 51
Logical-to-Physical Address Translation in Paging 4/6/2008 Trần Hạnh Nhi 52
Nhận xét Mô hình Paging Loại bỏ Dynamic Allocation External Fragmentation “Trong suốt” với LTV Hỗ trợ Bảo vệ và Chia sẻ ở mức page Internal Fragmentation Lưu trữ Page Table trong bộ nhớ Tốn chỗ Tăng thời gian chuyển đổi địa chỉ 4/6/2008 Trần Hạnh Nhi 53
Lưu trữ Page Table Giả sử hệ thống sử dụng m bit địa chỉ Size of KGĐC = 2m Kích thước page Trên nguyên tắc tùy ý, thực tế chọn pagesize = 2n Tại sao ? Số trang trong KGĐC: #pages = 2m / 2n = 2m-n Ví dụ : 32-bits địa chỉ, pagesize = 4K KGĐC = 232 -> #pages= 232-212 = 220 = 1.000.000 pages ! #pages = #entry trong PT Điạ chỉ logic : p d Page Table (m-n) n Mỗi tiến trình lưu 1 Page Table Số lượng phần tử quá lớn -> Lưu BNC Mỗi truy xuất địa chỉ sẽ tốn 2 lần truy xuất BNC 4/6/2008 Trần Hạnh Nhi 54
Lưu trữ Page Table : Tiết kiệm không gian Sử dụng bảng trang đa cấp Chia bảng trang thành các phần nhỏ, bản thân bảng trang cũng sẽ được phân trang Chỉ lưu thường trực bảng trang cấp 1, sau đó khi cần sẽ nạp bảng trang cấp nhỏ hơn thích hợp Có thể loại bỏ những bảng trang chứa thông tin về miền địa chỉ không sử dụng Sử dụng Bảng trang nghịch đảo Mô tả KGVL thay vì mô tả KGĐC -> 1 IPT cho toàn bộ hệ thống 4/6/2008 Trần Hạnh Nhi 55
Bảng trang đa cấp p d 0 5 1 16 2 Bảng trang tuyến tính 3 Sử dụng page-number làm chỉ mục đến Page Table p f Phải lưu tất cả các phần tử mô tả tất cả các trang trong 7 KGĐC 8 2 Những page không sử dụng : 9 lãng phí 10 Nạp toàn bộ PT vào BNC : tốn 11 chỗ 12 13 14 15 9 4/6/2008 Trần Hạnh Nhi 56
Bảng trang đa cấp 0 0 1 1 0 2 2 1 Page Table cấp 2 3 3 2 4 3 4 5 4 5 6 5 6 7 0 6 7 Page Table cấp 2 8 1 7 9 2 8 8 10 3 9 9 11 10 10 12 Page Table cấp 1 11 Page Table cấp 2 11 13 12 12 12 13 13 13 14 14 Page Table cấp 2 14 15 15 15
Mô hình bảng trang 2 cấp 4/6/2008 Trần Hạnh Nhi 58
Ví dụ mô hình bảng trang 2 cấp Một máy tính sử dụng địa chỉ 32bít với kích thước trang 4Kb. Địa chỉ logic được chia thành 2 phần: Số hiệu trang : 20 bits. Offset tính từ đầu mỗi trang :12 bits. Vì bảng trang lại được phân trang nên số hiệu trang lại được chia làm 2 phần: Số hiệu trang cấp 1. Số hiệu trang cấp 2. 4/6/2008 Trần Hạnh Nhi 59
Ví dụ mô hình bảng trang 2 cấp Vì thế, địa chỉ logic sẽ có dạng như sau: page number page offset pi p2 d 10 10 12 4/6/2008 Trần Hạnh Nhi 60
Bảng trang đa cấp 0 0 1 1 1 2 100 2 2 3 Page Table cấp 2 3 4 0 5 1 6 2 0 7 3 Page Table cấp 2 8 1 9 2 0 10 3 1 11 2 12 Page Table cấp 1 3 Page Table cấp 2 13 0 14 1 15 2 Page Table cấp 2 16 3 17
Bảng trang nghịch đảo (Inverted Page Table) Sử dụng duy nhất một bảng trang nghịch đảo cho tất cả các tiến trình Mỗi phần tử trong bảng trang nghịch đảo mô tả một frame, có cấu trúc : số hiệu page mà frame đang chứa đựng : id của tiến trình đang được sỡ hữu trang Mỗi địa chỉ ảo khi đó là một bộ ba Khi một tham khảo đến bộ nhớ được phát sinh, một phần địa chỉ ảo là được đưa đến cho trình quản lý bộ nhớ để tìm phần tử tương ứng trong bảng trang nghịch đảo, nếu tìm thấy, địa chỉ vật lý sẽ được phát sinh 4/6/2008 Trần Hạnh Nhi 62
Kiến trúc bảng trang nghịch đảo 4/6/2008 Trần Hạnh Nhi 63
Lưu trữ Page table : Tiết kiệm thời gian Mỗi truy cập BNC cần truy xuất BNC 2 lần : Tra cứu Page Table để chuyển đổi địa chỉ Tra cưu bản thân data Làm gì để cải thiện : Tìm cách lưu PT trong cache Cho phép tìm kiếm nhanh PT lớn, cache nhỏ : làm sao lưu đủ ? Lưu 1 phần PT Phần nào ? Các số hiệu trang mới truy cập gần đây nhất 4/6/2008 Trần Hạnh Nhi 64
Translation Lookaside Buffer (TLB) Vùng nhớ Cache trong CPU được sử dụng để lưu tạm thời một phần của PT được gọi là Translation Lookaside Buffer (TLB) Cho phép tìm kiếm tốc độ cao Kích thước giới hạn (thường không quá 64 phần tử) Mỗi entry trong TLB chứa một số hiệu page và frame tương ứng đang chứa page Khi chuyển đổi địa chỉ, truy xuất TLB trước, nếu không tìm thấy số hiệu page cần thiết, mới truy xuất vào PT để lấy thông tin frame. 4/6/2008 Trần Hạnh Nhi 65
Translation Lookaside Buffer 4/6/2008 Trần Hạnh Nhi 66
Chuyển đổi địa chỉ với Paging virtual address CPU pd f physical address d fd TLB p f f Memory f PT 4/6/2008 Trần Hạnh Nhi 67
Sử dụng TBL 4/6/2008 Trần Hạnh Nhi 68
Bảo vệ và chia sẻ trong Segmentation và Paging Bảo vệ Segmentation : mỗi phần tử trong ST được gắn thêm các bit bảo vệ Mỗi segment có thể được bảo vệ tùy theo ngữ nghĩa của các đối tượng bên trong segment Paging : mỗi phần tử trong PT được gắn thêm các bit bảo vệ Mỗi page không nhận thức được ngữ nghĩa của các đối tượng bên trong page, nên bảo vệ chỉ áp dụng cho toàn bộ trang, không phân biệt. Chia sẻ: Cho nhiều phần tự trong KGĐC cùng trỏ đến 1 vị trí trong KGVL Segmentation : chia sẻ mức module chương trình Paging : chia sẻ các trang 4/6/2008 Trần Hạnh Nhi 69
Sharing Pages: A Text Editor
Sharing Pages: A Text Editor ed 3 + data 1 ed 3 + data 2 ed 3 + data 3 Chia sẻ Page 2 = Chia sẻ cả code và data !
Đánh giá các mô hình chuyển đổi địa chỉ Giả sử có: tm : thời gian truy xuất BNC tc : thời gian truy xuất cache hit-ration : tỉ lệ tìm thấy một số hiệu trang p trong TLB Công thức tính thời gian truy cập thực tế (Time Effective Acess) đến một đối tượng trong BNC bao gồm thời gian chuyển đổi địa chỉ và thời gian truy xuất dữ liệu TEA = (time biding add + time acces memory) 4/6/2008 Trần Hạnh Nhi 72
Linker-Loader TEA = tm (data) Base + Bound TEA = (tc + tc) + tm (Base & Bound) (data) Segmentation TEA = tc + tm (ST trong cache) (data) Paging Không sử dụng TLB : TEA = tm + tm (PT trong mem) (data) Có sử dụng TLB : TEA = hit-ratio ( tc + tm ) + (1- hit-ratio)( tc + tm + tm ) (TLB) (data) (TLB) (PT) (data)
Bài giảng 7 : Bộ nhớ Ảo VaÁn đề với Real Memory Ý tưởng Virtual Memory Thực hiện Virtual Memory Các chiến lược của Virtual Memory Chiến lược nạp Chiến lược thay thế trang Chiến lược cấp phát khung trang Hiện tượng thrashing Nguyên nhân Giải pháp 12/16/2007 Trần Hạnh Nhi 1
Các cấp bộ nhớ Cho đến nay : Nạp toàn bộ tiến trình vào bộ nhớ rồi thực hiện nó Nếu kích thước tiến trình lớn hơn dung lương bộ nhớ chính ? Memory Cache Registers 12/16/2007 Trần Hạnh Nhi 2
Giải pháp Tại một thời điểm chỉ có 1 chỉ thị được thi hành Tại sao phải nạp tất cả tiến trình vào BNC cùng 1 lúc ? Ý tưởng Cho phép nạp và thi hành từng phần tiến trình Ai điều khiển việc thay đổi các phần được nạp và thi hành ? Tại một thời điểm chỉ giữ trong BNC các chỉ thị và dữ liệu cần thiết tại thời điểm đó Các phần khác của tiến trình nằm ở đâu ? Giải pháp Bộ nhớ ảo (virtual memory) 12/16/2007 Trần Hạnh Nhi 3
Virtual Memory Nếu có một Virtual Memory với dung lượng rất rất lớn cho LTV làm việc Hoan hô ! Virtual Memory Memory Cache Registers 12/16/2007 Trần Hạnh Nhi 4
Ý tưởng Tách biệt KGĐC và KGVL LTV : mỗi tiến trình làm việc với KGĐC 2m của mình (địa chỉ từ 0 – (2m -1)) HĐH : chịu trách nhiệm nạp các KGĐC vào một KGVL chung Giải pháp của HĐH : Nạp từng phần tiến trình Phân chia KGĐC thành các phần ? Paging/Segmentation Mở rộng BNC để lưu trữ các phần của tiến trình chưa được nạp Dùng BNP(disk) để mở rộng BNC Nhận biết phần nào của KGĐC chưa được nạp ? Bổ sung bit cờ hiệu để nhận dạng tình trạng của một page/segment là đã được nạp vào BNC hay chưa Cơ chế chuyển đổi qua lại các phần của tiến trình giữa BNC và BNP Swapping 12/16/2007 Trần Hạnh Nhi 5
Virtual Memory với cơ chế phân trang (Paging) Phân chia KGĐC thành các page Dùng BNP(disk) để mở rộng BNC, lưu trữ các phần của tiến trình chưa được nạp Bổ sung bit cờ hiệu trong Page Table để nhận dạng tình trạng một page đã được nạp vào BNC hay chưa . Cấu trúc một phần tử trong Page Tables 12/16/2007 Trần Hạnh Nhi 6
Lưu trữ KGĐC ở đâu ? Sử dụng bộ nhớ phụ để lưu trữ tạm thời các trang chưa sử dụng DISK P RAM 12/16/2007 Trần Hạnh Nhi 7
Virtual Memory virtual address space 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 physical memory 7 1 5 4 13 2 183 3 12/16/2007 Trần Hạnh Nhi 8
Memory Lookup present Outgoing physical address bit Page table 15 000 0 1 1 0 14 000 0 13 000 0 (0x6004, 24580) 12 000 0 11 111 1 10 000 0 9 101 1 8 000 0 7 000 0 6 000 0 5 011 1 4 100 1 3 000 1 2 110 1 1 001 1 4-bit index 0 010 1 into page table virtual page = 0x0010 = 2 12-bit offset Incoming virtual address 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 (0x2004, 8196) 12/16/2007 Trần Hạnh Nhi 9
Memory Lookup present Outgoing physical address bit Page table 15 000 0 14 000 0 13 000 0 12 000 0 11 111 1 10 000 0 9 101 1 8 000 0 7 000 0 6 000 0 5 011 1 PAGE FAULT 4 100 1 3 000 1 2 110 0 1 001 1 4-bit index 0 010 1 into page table virtual page = 0x0010 = 2 12-bit offset Incoming virtual address 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 (0x2004, 8196) 12/16/2007 Trần Hạnh Nhi 10
Demand Paging int i,j; i main () emacs { j i = 5; ji j = 2; i=5 } j=2 gcc KGDC code Khi nạp một tiến trình mới, chỉ nạp vào BNC page chứa entry code Khi truy xuất đến một chỉ thị hay dữ liệu, KGVL page tương ứng mới được nạp vào BNC 12/16/2007 Trần Hạnh Nhi 11
Swapping 12/16/2007 Trần Hạnh Nhi 12
Demand Paging + Swapping int i,j; main () { i i = 5; j = 2; emacs j } ji i=5 j=2 gcc KGDC code 12/16/2007 Trần Hạnh Nhi KGVL 13
Bộ nhớ ảo = “True lie“ Người dùng : sở hữu bộ nhớ “vô hạn”, “riêng biệt” Hệ điều hành : “thầm lặng” thực hiện quá trình swapping # ofreferences 10% RAM + 90% DISK Memory address DISK RAM 12/16/2007 Trần Hạnh Nhi 14
Thực hiện Bộ nhớ ảo Bảng trang : thêm 1 bit valid/invalid để nhận diện trang đã hay chưa được nạp vào RAM Frame valid/invalid 17 1 Disk 4183 0 177 1 5721 0 Mem Truy xuất đến một trang chưa được nạp vào bộ nhớ : lỗi trang (page fault) 12/16/2007 Trần Hạnh Nhi 15
Page Tables
Xử lý lỗi trang 3 xác định vị trí lưu trang trên đĩa OS lỗi trang 2 3’ truy xuất M swap out 1 trang nạn nhân nạp M i 6 Page Table tái kích hoạt frame trống tiến trình mang trang Bộ nhớ ảo 5 4 cập nhật cần truy xuất bảng trang vào bộ nhớ Bộ nhớ vật lý 12/16/2007 Trần Hạnh Nhi 17
Các bước xử lý lỗi trang 1. Kiểm tra truy xuất đến bộ nhớ là hợp lệ hay bất hợp lệ 2. Nếu truy xuất bất hợp lệ : kết thúc tiến trình Ngược lại : đến bước 3 3. Tìm vị trí chứa trang muốn truy xuất trên đĩa. 4. Tìm một khung trang trống trong bộ nhớ chính : a. Nếu tìm thấy : đến bước 5 b. Nếu không còn khung trang trống, chọn một khung trang nạn nhân để swap out, cập nhật bảng trang tương ứng rồi đến bước 5 5. Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ chính : nạp trang cần truy xuất vào khung trang trống đã chọn (hay vừa mới làm trống ) ; cập nhật nội dung bảng trang, bảng khung trang tương ứng. 6. Tái kích hoạt tiến trình người sử dụng. 12/16/2007 Trần Hạnh Nhi 18
Các câu hỏi 1. Chọn trang nào để nạp ? => Chiến lược nạp Demand Paging / Prepageing 2. Chọn trang nạn nhân ? => Chiến lược thay thế trang FIFO / OPTIMAL/LRU 3. Cấp phát khung trang => Chiến lược cấp phát khung trang Công bằng/ Tỷ lệ 12/16/2007 Trần Hạnh Nhi 19
Chiến lược nạp Quyết định thời điểm nạp một/nhiều page vào BNC Nạp trước : làm sao biết ? =>prepaging Nạp sau : tần suất lỗi trang cao ? => pure demand paging Prepaging : Nạp sẵn một số trang cần thiết vào BNC trước khi truy xuất chúng Demand paging : Chỉ nạp trang khi được yêu cầu truy xuất đến trang đó ld page ld init pages ld page ld page init pages = ? 12/16/2007 Trần Hạnh Nhi 20
Chiến lược thay thế trang (Page Replacement) Mục tiêu : thay thế trang sao cho tần suất xảy ra lỗi trang thấp nhất Đánh giá Sử dụng số frame cụ thể Giả sử có một chuỗi truy xuất cụ thể adresse : 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0611 # page : 1, 4, 1, 6, 1, 1, 1, 6, Thực hiện một thuật toán thay thế trang trên chuỗi truy xuất này Đếm số lỗi trang phát sinh Chuỗi truy xuất 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 3 frames 12/16/2007 Trần Hạnh Nhi 21
Chiến lượt thay thế trang FIFO Optimal LRU (Least Recently Used) 12/16/2007 Trần Hạnh Nhi 22
Chiến lược thay thế trang FIFO Nguyên tắc : Nạn nhân là trang “già” nhất victim add Được nạp vào lâu nhất trong hệ thống Thực hiện Lưu thời điểm nạp, so sánh để tìm min Chi phí cao Tổ chức FIFO các trang theo thứ tự nạp Trang đầu danh sác là nạn nhân Nhận xét Đơn giản Công bằng ? Không xét đến tính sử dụng ! Trang được nạp vào lâu nhất có thể là trang cần sử dụng thường xuyên ! 12/16/2007 Trần Hạnh Nhi 23
Ví dụ : FIFO 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 7 7 7 72 2 2 2 42 4 4 40 0 0 0 0 0 0 0 0 0 03 3 3 32 2 2 2 2 21 1 1 1 1 1 1 10 0 0 03 3 3 3 3 23 2 * * * * * * * * * * * * 12/16/2007 Trần Hạnh Nhi 24
FIFO và hiệu ứng Belady Sử dụng càng nhiều frame càng có nhiều lỗi trang ! 12/16/2007 Trần Hạnh Nhi 25
Chiến lược thay thế trang : Optimal Nguyên tắc : Nạn nhân là trang lâu sử victim dụng đến nhất trong tương lai Làm sao biết ? AGBDCABCABCGABC Nhận xét Cur page Bảo đảm tần suất lỗi trang thấp nhất Không khả thi ! 12/16/2007 Trần Hạnh Nhi 26
Ví dụ : Optimal 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 7 7 7 72 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 04 4 4 04 0 0 0 0 1 1 1 1 31 3 3 3 3 3 3 3 13 1 2 * * * * * * * * 12/16/2007 Trần Hạnh Nhi 27
Chiến lược thay thế trang : LRU Nguyên tắc : Nạn nhân là trang lâu nhất chưa sử dụng đến trong quá khứ Nhìn lui : đủ thông tin Nhận xét victim Xấp xỉ Optimal AGBDCABCABCGABC Thực hiện ? Cur page 12/16/2007 Trần Hạnh Nhi 28
Ví dụ : LRU 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 7 7 7 72 2 2 2 24 4 4 04 0 0 01 1 1 0 0 0 0 0 0 0 0 30 3 3 3 3 3 30 1 1 1 31 3 3 32 2 2 2 2 2 2 2 * * * * * * * * * * * 12/16/2007 Trần Hạnh Nhi 29
Thực hiện LRU Sử dụng bộ đếm: Thêm trường reference time cho mỗi phần tử trong bảng trang Thêm vào cấu trúc của CPU một bộ đếm counter. mỗi lần có sự truy xuất đến một trang trong bộ nhớ giá trị của counter tăng lên 1. giá trị của counter được ghi nhận vào reference time của trang tương ứng. thay thế trang có reference time là min . Sử dụng stack: tổ chức một stack lưu trữ các số hiệu trang mỗi khi thực hiện một truy xuất đến một trang, số hiệu của trang sẽ được xóa khỏi vị trí hiện hành trong stack và đưa lên đầu stack. trang ở đỉnh stack là trang được truy xuất gần nhất, và trang ở đáy stack là trang lâu nhất chưa được sử dụng 12/16/2007 Trần Hạnh Nhi 30
Thực hiện LRU với stack 12/16/2007 Trần Hạnh Nhi 31
Thực hiện LRU : thực tế Hệ thống được hỗ trợ phần cứng hoàn chỉnh để cài đặt LRU ? Đừng có mơ ! Hệ thống chỉ được trang bị thêm một bit reference : gắn với một phần tử trong bảng trang. được khởi gán là 0 được phần cứng đặt giá trị 1 mỗi lần trang tương ứng được truy cập được phần cứng gán trở về 0 sau từng chu kỳ qui định trước. Bit reference chỉ giúp xác định những trang có truy cập, không xác định thứ tự truy cập Không cài đặt được LRU Xấp xỉ LRU reference modify frame protect 12/16/2007 Trần Hạnh Nhi 32
4-53 Xấp xỉ LRU : Sử dụng các bits History thời gian 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 bit reference các bits history sử dụng thêm N bit history phụ trợ Sau từng chu kỳ, bit reference sẽ được chép lại vào một bit history trước khi bi reset N bit history sẽ lưu trữ tình hình truy xuất đến trang trong N chu kỳ cuối cùng. 12/16/2007 Trần Hạnh Nhi 33
Thời gian 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0
Thời gian 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0
Thời gian 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0
Thời gian 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0
Xấp xỉ LRU : Cơ hội thứ 2 (Clock algorithme) Sử dụng một bit reference duy nhất. Chọn được trang nạn nhân theo FIFO Kiểm tra bit reference của trang đó : Nếu reference = 0, đúng là nạn nhân rồi ☺ Nếu reference = 1, cho trang này một cơ hội thứ hai reference = 0 thời điểm vào Ready List được cập nhật lại là thời điểm hiện tại. Chọn trang FIFO tiếp theo Nhận xét : Một trang đã được cho cơ hội thứ hai sẽ không bị thay thế trước khi hệ thống đã thay thế hết những trang khác. Nếu trang thường xuyên được sử dụng, bit reference của nó sẽ duy trì được giá trị 1, và trang hầu như không bao giờ bị thay thế. 12/16/2007 Trần Hạnh Nhi 38
4-55 Xấp xỉ LRU : Cơ hội thức 2 (Clock algorithme) 0 page# 0 page# Trang FIFO 10 page# Trang FIFO 1101 page# Nạn nhân 00 page# 101 page# 101 page# 12/16/2007 Trần Hạnh Nhi 39
Xấp xỉ LRU : NRU Sử dụng 2 bit Reference và Modify Priority R M Với hai bit này, có thể có 4 tổ hợp tạo thành 4 lớp sau : 4 0 0 (0,0) không truy xuất, không sửa đổi 3 0 1 (0,1) không truy xuất gần đây, nhưng đã bị sửa đổi 2 1 0 (1,0) được truy xuất gần đây, nhưng không bị sửa đổi 1 1 1 (1,1) được truy xuất gần đây, và bị sửa đổi Chọn trang nạn nhân là trang có độ ưu tiên cao nhất khi kết hợp bit R và bit M 12/16/2007 Trần Hạnh Nhi 40
Chiến lược cấp phát frame Số frame cần cấp phát cho mỗi tiến trình ? Giải sử có m frame và n process Cấp phát công bằng: #frame(Pi) = m/n Công bằng ??? Cấp phát theo tỷ lệ: #frame(pi) = (si / (Σ si ))* m si = kích thước của bộ nhớ ảo cho tiến trình pi Lỗi trang xảy ra tiếp theo, cấp phát thêm frame cho tiến trình như thế nào ? Tùy thuộc chiến lược thay thế trang Cục bộ : chỉ chọn trang nạn nhân trong tập các trang của tiến trình phát sinh lỗi trang -> số frame không tăng Toàn cục: được chọn bất kỳ trang nạn nhân nào (dù của tiến trình khác) - > số frame có thể tăng, lỗi trang lan truyền 12/16/2007 Trần Hạnh Nhi 41
Thay thế trang toàn cục và kết cục bi thảm ! Running CPU IO P1, error P1 P1, swap out P2, error P2P1 P2, swap out P1 P3, error P3 Tất cả các tiến trình bận rộn thay thế trang ! 12/16/2007 Trần Hạnh Nhi 42
Thrashing Tất cả tiến trình đầu bận rộn xử lý lỗi trang ! IO hoạt động 100 %, CPU rảnh ! Hệ thống ngừng trệ P1 P2 P3 Real mem Virtual Memory = Tha hồ xài bộ nhớ Thrashing = ảo tưởng sụp đổ ! Các tiến trình trong hệ thống yêu cầu bộ nhớ nhiều hơn khả năng cung cấp của hệ thống ! 12/16/2007 Trần Hạnh Nhi 43
Thrashing Diagram Why does paging work? Locality model Process migrates from one locality (working set) to another Why does thrashing occur? Σ size of working sets > total memory size 12/16/2007 Trần Hạnh Nhi 44
Nguyên nhân Thrashing 1. Tiến trình không tái sử dụng bộ nhớ (quá khứ != tương lai) 2. Tiến trình tái sử dụng bộ nhớ, nhưng với kích thươc lớn hơn 3. Quá nhiều tiến trình trong hệ thống Chỉ có thể kiểm soát thrashing do nguyên nhân 3. 12/16/2007 Trần Hạnh Nhi 45
Working set (1968, Denning) Working set: Working set = tập hợp các trang tiến trình đang truy xuất tại 1 thời điểm Các pages được truy xuất trong Δ lần cuối cùng sẽ nằm trong working set của tiến trình Δ : working set parameter Kích thước của WS thay đổi theo thời gian tùy vaò locality của tiến trình 12/16/2007 Trần Hạnh Nhi 46
Working-Set Model Δ≡working-set window ≡ số lần truy cập VD: 10,000 instruction 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 4 3 4 4 4 1 3 2 3 Δ=10 WS(t1) = {1,2,5,6,7}, WS(t2) = {3,4} WSSi (working set of Process Pi) = tổng số trang được truy cập trong Δ lần gần đây nhất D = Σ WSSi ≡ Tổng các frame cần cho N tiến trình trong hệ thống if D > m ⇒ Thrashing if D > m, chọn mộ/một số tiến trình để đình chỉ tạm thời. 12/16/2007 Trần Hạnh Nhi 47
Giải quyết thrasing với mô hình Working set Sử dụng Working set Cache partitioning: Cấp cho mỗi tiến trình số frame đủ chứa WS của nó Page replacement: ưu tiên swap out các non-WS pages. Scheduling: chỉ thi hành tiến trình khi đủ chỗ để nạp WS của nó 12/16/2007 Trần Hạnh Nhi 48
BÀI GIẢNG 8 : LIÊN LẠC GIỮA CÁC TIẾN TRÌNH CƠCƠ CHECHẾÁ ?? TRAOTRAO ĐĐOỔIÅI THÔNGTHÔNGVAVẤNÁN TINTIN ĐĐEE GIGIÀÀ ??ƯỮÃA CACÁCÙC TIETIẾÁNN TRÌNHTRÌNH GGỈỈAIAI PHAPHÁPÙP ?? 12/16/2007 Trần Hạnh Nhi 1
NhuCầuLiênLạc Q Chia sẻ thông tin L P R Phối hợp xử lý JOB P R1 L Q R2 12/16/2007 Trần Hạnh Nhi 2
Các cơ chế liên lạc Chia sẻ tài nguyên chung Signal Pipe Shared Memory Trao đổi thông điệp Message Socket 12/16/2007 Trần Hạnh Nhi 3
IPC theo nguyên tắc chia sẻ tài nguyên chung User Process User Process shared resources OS - Kernel Các tiến trình chia sẻ Memory File System Space Communication Facilities, Common communication protocol 12/16/2007 Trần Hạnh Nhi 4
Signal Signal Meaning Handler Định nghĩa trước khi thực hiện liên lạc OS SIGINT, SIGSTOP SIGUSR1, SIGUSER2 Signal Hỗ trợ liên lạc Kernel với User Process Signal handler Process Error Timer Child Process kết thúc Signal Action User process vơí nhau Terminate Process Process Suspend, Resume 12/16/2007 Trần Hạnh Nhi 5
Name Value Function SIGHUP 1 Terminal hangup SIGINT 2 Interrupt by user: generated by SIGQUIT 3 Quit by user: generated by SIGFPE 8 Floating point error such as divide by zero SIGKILL 9 Kill the process SIGUSR1 10 User defined signal 1 SIGSEGV 11 Segment violation: process has tried to access memory not assigned to it SIGUSR2 12 User defined signal 2 SIGALRM 14 Timer set with alarm() function has timed out SIGTERM 15 Termination request SIGCHLD 17 Child process termination signal SIGCONT 18 Continue after a SIGSTOP or SIGSTP signal SIGSTOP 19 Stop the process SIGTSTP 20 Terminal stop: generated by SIGWINCH 28 Change of window size
Nhận xét Signals Liên lạc không đồng bộ L Không biết trước thời điểm SH Thiếu tin cậy Quiz : OK Q Sig A B Không cho phép trao đổi dữ liệu L Q Result 12/16/2007? Trần Hạnh Nhi 7
Pipes AB AB Q B .A L WritePipe() ReadPipe() Pipe Kernel buffer (File) có kích thước giới hạn (4K, 8K ) HĐH cung cấp hàm WritePipe & ReadPipe WritePipe khi Pipe đầy ? ReadPipe khi Pipe rỗng ? Phảiù xét đến các khả năng đồng bộ Hỗ trợ liên lạc (UNIX original ) Giữa 2 tiến trình Cha - Con Một chiều Không cấu trúc (byte transfer) 12/16/2007 Trần Hạnh Nhi 8
Nhận xét Pipe Ưu điểm : Cho phép trao đổi dữ liệu không cấu trúc Khuyết điểm Chi phí thực hiện cao (system call) Liên lạc giữa 2 tiến trình Liên lạc một chiều Pipe trong các HĐH hiện đại : Anomynous Pipe : This Named Pipe : Unix , Windows NT Truyền dữ liệu có cấu trúc Liên lạc 2 chiều 12/16/2007 Trần Hạnh Nhi 9
Shared Memory Shared Memory: Là một phần không gian nhớ không thuộc sở hữu của tiến trình nào Được HĐH tạo ra Các tiến trình có thể ánh xạ địa chỉ vào không gian chia sẻ này để truy xuất dữ liệu (như đối với không gian nội bộ) Không giới hạn số lượng tiến trình, chiều trao đổi, và thứ tự truy cập Mâu thuẫn truy xuất - > nhu cầu đồng bộ 12/16/2007 Trần Hạnh Nhi 10
IPC theo nguyên tắc trao đổi thông điệp User Process User Process OS-Kernel OS-Kernel Network Không có bộ nhớ chung Cần có đường kết nối giữa các máy tính 12/16/2007 Trần Hạnh Nhi 11
Message Message Dữ liệu có cấu trúùc Cấu trúc và thông dịch msg được thỏa thuận giữa 2 tiến trình liên lạc HĐH cung cấp 2 primitive chính send(destination, message) receive(source, message) Các vấn đề quan tâm : Direct or indirect addressing Blocking or non-blocking communication Reliable or unreliable communication Buffered or un-buffered communication 12/16/2007 Trần Hạnh Nhi 12
Định dạng Message 12/16/2007 Trần Hạnh Nhi 13
Nhận xét message Là cơ chế IPC tổng quát Hỗ trợ liên lạc giữa các tiến trính trên cùng máy Hỗ trợ liện lạc giữa các tiến trính trong hệ thống phân tán Liên lạc giữa các hệ thống không đồng nhất ? 12/16/2007 Trần Hạnh Nhi 14
Liên lạc giữa các hệ thống không đồng nhất Máy A Send( ) //UNIX P1 Receive( ) //WIN (UNIX) Máy B P2 (Windows) 12/16/2007 Trần Hạnh Nhi 15
Socket Endpoint của một kết nối 2 chiều Tương đương với một network interface (hardware) Cho phép các ứng dụng “plug in” vào mạng một cách ẩn dụ Là một giao diện lập trình mạng Cho phép các tiến trình liên lạc 2 chiều với nhau Thiết lập liên lạc : tạo 2 socket, kết nối chúng với nhau Socket description Sử dụng một transport protocol Cần đặc tả IPaddress và port kết nối Được hỗ trợ đầu tiên trong Berkeley socket Là sự mở rộng của nhập xuất file trừu tượng Hiện nay được hỗ trợ trong hầu hết HĐH hiện đại 12/16/2007 Trần Hạnh Nhi 16
12/16/2007 Trần Hạnh Nhi 17
Socket Communication 12/16/2007 Trần Hạnh Nhi 18
Liên lạc giữa các hệ thống không đồng nhất Máy A P1 Socket Send( ) (UNIX) Máy B Receive( ) Socket P2 12/16/2007 Trần Hạnh Nhi(Windows) 19
Liên lạc thông qua Socket Hỗ trợ 2 phương thức liên lạc Connection-oriented (TCP/IP) Stream Reliable Bi-directional communication Connectionless (UDP/IP) Datagram Unreliable Bi-directional communication Cho phép liên lạc giữa các tiến trình trên các mạng không đồng nhất 12/16/2007 Trần Hạnh Nhi 20
Phương thức Connection-Oriented Thực hiện trên TCP (Transmission Control Protocol.) Phải thực hiện kết nối giữa 2 tiến trình trước khi trao đổi dữ liệu Tương tự hệ thống điện thoại Dữ liệu được phân phối in sequence. guaranteed. Kết nối kết thúc khi liên lạc chấm dứt 2 modes: Iterative (synchronous) Concurrent (asynchronous) 12/16/2007 Trần Hạnh Nhi 21
Phương thức Connectionless Thực hiện trên UDP (User Datagram Protocol) Không yêu cầu kết nối tồn tại trước khi truyền dữ liệu Tương tự hệ thống thư tín Dữ liệu truyền có thể bị mất mát hay không đúng trật tự 2 modes: Iterative (synchronous) Concurrent (asynchronous) 12/16/2007 Trần Hạnh Nhi 22
Cấu trúc địa chỉ Socket Generic socket address structure: struct sockaddr { sa_family_t sa_family; /* address family */ char sa_data[14]; /* socket address */ }; A popular BSD-derived implementation: struct sockaddr_in { sa_family_t sin_family; /* address family */ in_port_t sin_port; /* protocol port number */ struct in_addr sin_addr; /* IP addr in NW byte order */ char sin_zero[8]; /* unused, set to zero */ }; 12/16/2007 Trần Hạnh Nhi 23
Port Numbers Port là 1 khái niệm trừu tượng được TCP/UDP sử dụng để phân biệt các ứng dụng trên một máy chủ Một port được xác định bằng 1 số nguyên 16 bit là port number. 3 miền giá trị đươc dành cho Well-known ports (0-1023) Registered ports (1024-49151) Dynamic ports (49512 – 65535) 12/16/2007 Trần Hạnh Nhi 24
Some Well-Known Ports 12/16/2007 Trần Hạnh Nhi 25
Socket Types Socket types: SOCK_STREAM Stream socket (TCP) SOCK_DGRAM Datagram socket (UDP) SOCK_RAW Raw socket (talk to IP directly) 12/16/2007 Trần Hạnh Nhi 26
Socket Primitives Primitive Ý nghĩa Socket Tạo 1 communication endpoint Bind Kết buộc một local address với 1 socket Listen Thông báo sẵn sàng “lắng nghe” (tiếp nhận kết nối) Accept Khoá caller đến khi có 1 yêu cầu kết nối Connect Chủ động thực hiện kết nối Send Gởi dữ liệu qua kết nối đã thiết lập Receive Nhận dữ liệu qua kết nối đã thiết lập Close Kết thúc kết nối 12/16/2007 Trần Hạnh Nhi 27
TCP System Calls Server socket() bind() listen() Client accept() socket() blocks until connection from client connect() write() read() process request write() read() close() close() 12/16/2007 Trần Hạnh Nhi 28
UDP System Calls Server socket() bind() recvfrom() Client socket() blocks until data received from a client sendto() data(request) process request data(reply) sendto() recvfrom() close() 12/16/2007 Trần Hạnh Nhi 29