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

int rc = 0; Boolean busy = false; procedure BeginRead() { if (busy) wait(OKRead); rc++; signal(OKRead); } procedure FinishRead() { rc--; if (rc == 0) signal(OKWrite); } procedure BeginWrite() { if (busy || rc != 0) wait(OKWrite); busy = true; } procedure FinishWrite() { busy = false; if (OKRead.Queue) signal(OKRead); else signal(OKWrite); } end monitor; 11/10/2007 Trần Hạnh Nhi 81 Reader&Writer : Giải pháp Monitor Reader() { RW.BeginRead(); Read-db(Database); RW.FinishRead(); } Writer(); { RW.BeginWrite(); Write-db(Database); RW.FinishWrite(); } 11/10/2007 Trần Hạnh Nhi 82 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 83 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 84 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 85 Dining Philosophers : Thách thức „ Cần đồng bộ sao cho: „ Không có deadlock „ Không có starvation 4/6/2008 Trần Hạnh Nhi 1 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 2 „ 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ỉ ? Tổng quan : Nhu cầu về bộ nhớ của tiến trình 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 3 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ảo vệ ? Chia sẻ ? „ 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 4 Ví dụ „ 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ó? OS nachos gcc emacs 0x0000 0x4000 0x3000 0x7000 0x9000 Môi trường đa nhiệm 4/6/2008 Trần Hạnh Nhi 5 C program: test.c Executable: test.exe Compiler Linker Loader Memory Object:test.o lib.o Các bước chuyển đổi chương trình Các bước chuyển đổi source program -> .exe int x; int y; x = 12; y = 5; F(); A.C F() { printf(“Hi”); } B.C 0 // x 2 // y 4 // [0] = 12; 5 // [2] = 5; 6 // jmp F //external // object A.O B.O 0 -2 // F() 0 // F() 3 // x 5 // y 7 // [3] = 12; 8 // [5] = 5; 9 // jmp 0 ? // F() ? // x ? // y ? // [?] = 12; ? // [?] = 5; ? // jmp ? OS Test.exe 4/6/2008 Trần Hạnh Nhi 8 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 9 Nhu cầu bộ nhớ của tiến trình „ Tiến trình gồm cĩ: „ code segment „ read from program file by exec „ usually read-only „ can be shared „ data segment „ initialized global variables (0 / NULL) „ uninitialized global variables „ heap „ dynamic memory „ e.g., allocated using malloc „ grows against higher addresses „ stack segment „ variables in a function „ stored register states (e.g. calling function EIP) „ grows against lower addresses „ system data segment (PCB) „ segment pointers „ pid „ program and stack pointers „ „ Stack cho các thread process A low address high address ... 8048314 : 8048314: push %ebp 8048315: mov %esp,%ebp 8048317: mov 0xc(%ebp),%eax 804831a: add 0x8(%ebp),%eax 804831d: pop %ebp 804831e: ret 804831f : 804831f: push %ebp 8048320: mov %esp,%ebp 8048322: sub $0x18,%esp 8048325: and $0xfffffff0,%esp 8048328: mov $0x0,%eax 804832d: sub %eax,%esp 804832f: movl $0x0,0xfffffffc(%ebp) 8048336: movl $0x2,0x4(%esp,1) 804833e: movl $0x4,(%esp,1) 8048345: call 8048314 804834a: mov %eax,0xfffffffc(%ebp) 804834d: leave 804834e: ret 804834f: nop code segment system data segment (PCB) data segment initialized variables uninitialized variables d a t a s e g m e n t heap stack “ u n u s e d ” m e m o r y possible stacks for more threads 4/6/2008 Trần Hạnh Nhi 10 Logical and Physical Address Spaces 4/6/2008 Trần Hạnh Nhi 11 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 12 „ 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 Thời điểm kết buộc địa chỉ ? 4/6/2008 Trần Hạnh Nhi 13 Chuyển đổi địa chỉ gcc virtual address Load Store error data Translation box CPU legal addr? Illegal? Physical memory Physical address MMU 4/6/2008 Trần Hạnh Nhi 14 CPU, MMU and Memory 4/6/2008 Trần Hạnh Nhi 15 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 16 „ 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. Tái định vị (Relocation) 4/6/2008 Trần Hạnh Nhi 17 „ 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. Bảo vệ (Protection) 4/6/2008 Trần Hạnh Nhi 18 „ 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. Chia sẻ (Sharing) 4/6/2008 Trần Hạnh Nhi 19 „ 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 Tổ chức logic (Logical Organization) 4/6/2008 Trần Hạnh Nhi 20 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 21 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 22 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 23 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 24 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 25 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 26 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 3M 8M P1 (2M) P2 (4M) internal frag internal frag 4/6/2008 Trần Hạnh Nhi 27 Dynamic Partitioning „ BNC không được phân chia trước „ Các partition có kích thước tùy ý, 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 P1 (2M) P2 (4M) Dynamic Partitioning: tình huống „ 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 P1 (2M) P2 (4M) P3 (8M) 2M P4 (1.5M) external fragmentation 4/6/2008 Trần Hạnh Nhi 29 Ví dụ Dynamic Partitioning 4/6/2008 Trần Hạnh Nhi 30 Ví dụ Dynamic Partitioning 4/6/2008 Trần Hạnh Nhi 31 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 P1 8M P3 (1M) P2 1.5M Worst Fit First Fit Best Fit 4/6/2008 Trần Hạnh Nhi 32 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 P1 1M External fragmentations P2 1.5M 4/6/2008 Trần Hạnh Nhi 33 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 34 Mô hình Linker-Loader „ 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 0x0000 test.exe 0x4000 0x3000 test.exe jump 0x2000 jump 0x5000 0x7000 OS (base) 4/6/2008 Trần Hạnh Nhi 35 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 36 Mô hình Base & Bound 0x0000 Test.exe 0x4000 Base 0x3000 OS Test.exe jump 0x2000 jump 0x2000 Bound 0x7000 „ 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 37 Nhận xét mô hình Base & Bound „ Hỗ trợ ƒ Bảo vệ ƒ Tái định vị MMU + base reg logical addrs memory physical addrs CPU „ 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 4/6/2008 Trần Hạnh Nhi 38 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 8M P3 (9M) P2 1M 4/6/2008 Trần Hạnh Nhi 39 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 40 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 41 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 42 Mô hình Segmentation KGVL int m; main () { F1(m); } F1(int x) { x = 9; } code (main,F1) data (m) stack heap KGDCQuản lý địa chỉ ? 4/6/2008 Trần Hạnh Nhi 43 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 44 Chuyển đổi địa chỉ trong mô hình Segmentation Logical Addr Seg# offset 3 128 Seg table base limit 3 0x1000 512 mem seg 128 + 0x1000? yes no fault 0 1 2 4/6/2008 Trần Hạnh Nhi 45 Logical-to-Physical Address Translation in segmentation 4/6/2008 Trần Hạnh Nhi 46 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 47 Sharing of Segments: Text Editor 4/6/2008 Trần Hạnh Nhi 48 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 49 Mô hình Paging KGVL int m; main () { F1(m); } F1(int x) { x = 9; } KGDC Quản lý địa chỉ ? int m; main () F1(int x) stack heap 4/6/2008 Trần Hạnh Nhi 50 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 51 Chuyển đổi địa chỉ trong mô hình Paging CPU KGVL Physical addr Logical addr p d f d f Page table 4/6/2008 Trần Hạnh Nhi 52 Logical-to-Physical Address Translation in Paging 4/6/2008 Trần Hạnh Nhi 53 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 54 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 : „ Page Table / 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 p d (m-n) n 4/6/2008 Trần Hạnh Nhi 55 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 56 Bảng trang đa cấp „ Bảng trang tuyến tính „ Sử dụng page-number làm chỉ mục đến Page Table „ Phải lưu tất cả các phần tử mô tả tất cả các trang trong KGĐC „ Những page không sử dụng : lãng phí „ Nạp toàn bộ PT vào BNC : tốn chỗ p d 0 1 2 3 ... p ... 7 8 9 10 11 12 13 14 15 f 5 16 2 9 Bảng trang đa cấp 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 13 0 1 2 3 4 5 6 7 8 9 10 11 12 12 13 14 15 Page Table cấp 1 Page Table cấp 2 Page Table cấp 2 Page Table cấp 2 Page Table cấp 2 4/6/2008 Trần Hạnh Nhi 58 Mô hình bảng trang 2 cấp 4/6/2008 Trần Hạnh Nhi 59 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 60 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 Bảng trang đa cấp 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 13 0 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 Page Table cấp 1 Page Table cấp 2 Page Table cấp 2 Page Table cấp 2 Page Table cấp 2 1 2 100 4/6/2008 Trần Hạnh Nhi 62 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 63 Kiến trúc bảng trang nghịch đảo 4/6/2008 Trần Hạnh Nhi 64 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 65 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 66 Translation Lookaside Buffer 4/6/2008 Trần Hạnh Nhi 67 Chuyển đổi địa chỉ với Paging CPU p d f d f d TLB Memory virtual address physical address p f f PT f 4/6/2008 Trần Hạnh Nhi 68 Sử dụng TBL 4/6/2008 Trần Hạnh Nhi 69 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 Sharing Pages: A Text Editor Sharing Pages: A Text Editor ed 3 + data 1 ed 3 + data 3 ed 3 + data 2 Chia sẻ Page 2 = Chia sẻ cả code và data ! 4/6/2008 Trần Hạnh Nhi 72 Đá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) „ 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) 12/16/2007 Trần Hạnh Nhi 1 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 2 Các cấp bộ nhớ Registers Cache Memory „ 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 ? 12/16/2007 Trần Hạnh Nhi 3 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 4 Registers Cache Memory Virtual Memory 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ô ! 12/16/2007 Trần Hạnh Nhi 5 Ý 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 6 Cấu trúc một phần tử trong Page Tables 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 . 12/16/2007 Trần Hạnh Nhi 7 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 P RAM DISK 12/16/2007 Trần Hạnh Nhi 8 Virtual Memory 1 virtual address space 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 7 1 5 4 13 2 18 physical memory 3 3 12/16/2007 Trần Hạnh Nhi 9 0 0 1 0 Memory Lookup 0 0 0 0 0 0 0 0 0 1 0 0 12-bit offset Outgoing physical address 4-bit index into page table virtual page = 0x0010 = 2 Incoming virtual address (0x2004, 8196) 0 010 1 1 001 1 2 110 1 3 000 1 4 100 1 5 011 1 6 000 0 7 000 0 8 000 0 9 101 1 10 000 0 11 111 1 12 000 0 13 000 0 14 000 0 15 000 0Page table present bit (0x6004, 24580) 1 1 0 12/16/2007 Trần Hạnh Nhi 10 0 0 1 0 Memory Lookup 0 0 0 0 0 0 0 0 0 1 0 0 12-bit offset Outgoing physical address 4-bit index into page table virtual page = 0x0010 = 2 Incoming virtual address (0x2004, 8196) 0 010 1 1 001 1 2 110 0 3 000 1 4 100 1 5 011 1 6 000 0 7 000 0 8 000 0 9 101 1 10 000 0 11 111 1 12 000 0 13 000 0 14 000 0 15 000 0Page table present bit PAGE FAULT 12/16/2007 Trần Hạnh Nhi 11 Demand Paging KGVL i int i,j; main () { i = 5; j = 2; } emacs codeKGDC i j i=5 j=2 gcc j ƒ 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, page tương ứng mới được nạp vào BNC 12/16/2007 Trần Hạnh Nhi 12 Swapping 12/16/2007 Trần Hạnh Nhi 13 Demand Paging + Swapping KGVL i int i,j; main () { i = 5; j = 2; } emacs codeKGDC i j i=5 j=2 gcc j 12/16/2007 Trần Hạnh Nhi 14 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 RAM DISK # of references Memory address 10% RAM + 90% DISK 12/16/2007 Trần Hạnh Nhi 15 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 ƒ Truy xuất đến một trang chưa được nạp vào bộ nhớ : ƒ lỗi trang (page fault) 17 1 4183 0 177 1 5721 0 Disk Mem Frame valid/invalid Page Tables 12/16/2007 Trần Hạnh Nhi 17 Xử lý lỗi trang Bộ nhớ vật lý M Bộ nhớ ảo nạp M OS Page Table truy xuất 1 2 lỗi trang 3 xác định vị trí lưu trang trên đĩa 3’ swap out trang nạn nhân 4 mang trang cần truy xuất vào bộ nhớ 5 cập nhật bảng trang 6 tái kích hoạt tiến trình frame trống i 12/16/2007 Trần Hạnh Nhi 18 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 19 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 20 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 init pages ld page ld page ld page ... init pages = ? 12/16/2007 Trần Hạnh Nhi 21 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 22 Chiến lượt thay thế trang „ FIFO „ Optimal „ LRU (Least Recently Used) 12/16/2007 Trần Hạnh Nhi 23 Chiến lược thay thế trang FIFO „ Nguyên tắc : Nạn nhân là trang “già” nhất „ Đượ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 ! addvictim 12/16/2007 Trần Hạnh Nhi 24 Ví dụ : FIFO 7 0 1 00 32 4 2 0 3 2 1 2 0 ... 7 7 7 22 27 2 4 4 0 0 0 0 0 0 0 30 00 3 3 2 2 2 2 1 1 1 11 11 0 0 3 3 3 3 3 2 * * * *** * * * * * 2 3 0 4 2 3 4 0 * 2 3 0 1 2 12/16/2007 Trần Hạnh Nhi 25 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 26 Chiến lược thay thế trang : Optimal AGBDCABCABCGABC victim Cur page „ Nguyên tắc : Nạn nhân là trang lâu sử dụng đến nhất trong tương lai „ Làm sao biết ? „ Nhận xét „ 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 27 Ví dụ : Optimal 7 0 1 00 32 4 2 0 3 2 1 2 0 ... 7 7 7 22 27 0 2 4 2 2 2 2 0 0 0 00 1 0 2 4 2 0 0 3 0 1 1 31 0 1 3 3 3 3 3 0 1 2 * * * ** * * * 2 3 4 3 2 3 4 0 1 12/16/2007 Trần Hạnh Nhi 28 Chiến lược thay thế trang : LRU AGBDCABCABCGABC victim Cur page „ 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 „ Xấp xỉ Optimal „ Thực hiện ? 12/16/2007 Trần Hạnh Nhi 29 Ví dụ : LRU 7 0 1 00 32 4 2 0 3 2 1 2 0 ... 7 7 7 22 27 2 4 2 0 0 0 1 1 0 0 00 1 0 3 0 4 3 3 2 3 3 1 31 0 1 0 3 3 2 2 3 2 2 * * * ** * * * 2 3 4 3 4 2 0 0 1 3 * * 0 * 2 12/16/2007 Trần Hạnh Nhi 30 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 31 Thực hiện LRU với stack 12/16/2007 Trần Hạnh Nhi 32 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... frame protectmodifyreference 12/16/2007 Trần Hạnh Nhi 33 4-53 bit reference các bits history thời gian 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 0 Xấp xỉ LRU : Sử dụng 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. Thời gian 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 Thời gian 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 Thời gian 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 Thời gian 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 0 12/16/2007 Trần Hạnh Nhi 38 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 39 4-55 page#0 page#0 page#1 page#1 page#0 page#1 page#1 Trang FIFO Nạn nhân 0 0 0 0 Trang FIFO Xấp xỉ LRU : Cơ hội thức 2 (Clock algorithme) 12/16/2007 Trần Hạnh Nhi 40 Xấp xỉ LRU : NRU „ Sử dụng 2 bit Reference và Modify „ Với hai bit này, có thể có 4 tổ hợp tạo thành 4 lớp sau : „ (0,0) không truy xuất, không sửa đổi „ (0,1) không truy xuất gần đây, nhưng đã bị sửa đổi „ (1,0) được truy xuất gần đây, nhưng không bị sửa đổi „ (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 111 012 103 004 MRPriority 12/16/2007 Trần Hạnh Nhi 41 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 42 Thay thế trang toàn cục và...kết cục bi thảm ! „ Tất cả các tiến trình bận rộn thay thế trang ! Running CPU IO P1 P2 P1 P3 P1, error 1 P1, swap out P2, error P2, swap out P3, error 12/16/2007 Trần Hạnh Nhi 43 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ệ Real mem P1 P2 P3 ƒ 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 44 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 45 Nguyên nhân Thrashing Chỉ có thể kiểm soát thrashing do nguyên nhân 3. 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 12/16/2007 Trần Hạnh Nhi 46 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 47 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 48 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 1 BÀI GIẢNG 8 : LIÊN LẠC GIỮA CÁC TIẾN TRÌNH CƠ CHẾÁ ? VẤÁN ĐỀÀ ?TRAO ĐỔÅI THÔNG TIN GI ỮA Cà ÙÙC TIẾÁN TRÌNH GỈAI PHÁÙP ? 12/16/2007 Trần Hạnh Nhi 2 Nhu Cầu Liên Lạc Q LP ƒChia sẻ thông tin R ƒPhối hợp xử lý P JOB R1 R2 L Q 12/16/2007 Trần Hạnh Nhi 3 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 4 IPC theo nguyên tắc chia sẻ tài nguyên chung User Process User Process OS - Kernel shared resources „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 5 Signal „ Signal „ Meaning „ Handler „ Định nghĩa trước khi thực hiện liên lạc „ SIGINT, SIGSTOP „ SIGUSR1, SIGUSER2 „ Hỗ trợ liên lạc „ Kernel với User Process „ Process Error „ Timer „ Child Process kết thúc „ User process vơí nhau „ Terminate Process „ Suspend, Resume OS Process Signal handler Signal Action Signal 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 12/16/2007 Trần Hạnh Nhi 7 Nhận xét Signals „ Liên lạc không đồng bộ „ Không biết trước thời điểm „ Thiếu tin cậy ƒ Không cho phép trao đổi dữ liệu Sig Result L Q SH L Q Quiz : OK ? A B 12/16/2007 Trần Hạnh Nhi 8 Pipes ƒ 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) WritePipe() ReadPipe() LQ B.AAB AB 12/16/2007 Trần Hạnh Nhi 9 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 10 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 11 IPC theo nguyên tắc trao đổi thông điệp User Process OS-Kernel User Process 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 12 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 13 Định dạng Message 12/16/2007 Trần Hạnh Nhi 14 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 15 Máy A (UNIX) Máy B (Windows) Liên lạc giữa các hệ thống không đồng nhất P1 P2 Send( ) //UNIX Receive( ) //WIN 12/16/2007 Trần Hạnh Nhi 16 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 17 12/16/2007 Trần Hạnh Nhi 18 Socket Communication 12/16/2007 Trần Hạnh Nhi 19 Máy A (UNIX) Máy B (Windows) Liên lạc giữa các hệ thống không đồng nhất P1 P2 Send( ) Receive( ) Socket Socket 12/16/2007 Trần Hạnh Nhi 20 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 21 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 22 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 23 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 24 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 25 Some Well-Known Ports 12/16/2007 Trần Hạnh Nhi 26 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 27 Socket Primitives Kết thúc kết nốiClose Nhận dữ liệu qua kết nối đã thiết lậpReceive Gởi dữ liệu qua kết nối đã thiết lậpSend Chủ động thực hiện kết nốiConnect Khoá caller đến khi có 1 yêu cầu kết nốiAccept Thông báo sẵn sàng “lắng nghe” (tiếp nhận kết nối)Listen Kết buộc một local address với 1 socketBind Tạo 1 communication endpointSocket Ý nghĩaPrimitive 12/16/2007 Trần Hạnh Nhi 28 TCP System Calls bind() listen() socket() socket() accept() read() write() connect() write() read() blocks until connection from client process request Server Client close() close() 12/16/2007 Trần Hạnh Nhi 29 UDP System Calls socket() bind() recvfrom() sendto() socket() recvfrom() sendto() blocks until data received from a client process request data(request) data(reply) Server Client close()