›

Giáo trình Nguyễn Lý Hệ điều hành - Chương 3: Quản lý lưu trữ

pdf 171 trang huongle 6010
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Nguyễn Lý Hệ điều hành - Chương 3: Quản lý lưu trữ", để 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:

  • pdfgiao_trinh_nguyen_ly_he_dieu_hanh_chuong_3_quan_ly_luu_tru.pdf

Nội dung text: Giáo trình Nguyễn Lý Hệ điều hành - Chương 3: Quản lý lưu trữ

  1. Nội dung chương 3 1. Quảnlýbộ nhớ 2. B ộ nhớảo 3. Giao di ệnhệ thống file 4. Cài đặth ệ thống file 2008-05-01 Nguyên lý Hệ điềuhành 2
  2. 1. Quảnlýbộ nhớ 1. Cơ sở 2. Swapping 3. Phân phốibộ nhớ liên tục 4. Phân trang (paging) 5. Phân đo ạn (segmentation) 6. Phân đo ạnkế thợpvới phân trang (Segmentation với Paging) 2008-05-01 Nguyên lý Hệ điềuhành 3
  3. 1.1. Cơ sở „ Chương trình muốnthựcthicầnphải đượctảivào bộ nhớ và đặt trong mộttiếntrình „ Hàng đợi vào (Input Queue) ‰ Tậpcáctiến trình trên đĩa, đang đợitảivàobộ nhớđểthực hiện „ Các chương trình ngườidùngmuốn đượcthựcthi cầnphải qua mộtsố bước trong đócóbướcgánđịa chỉ cho các câu lệnh/dữ liệu. 2008-05-01 Nguyên lý Hệ điềuhành 4
  4. Gán bộ nhớ cho các câu lệnh và dữ liệu „ Việcgánđịachỉ cho các câu lệnh và dữ liệu đượcthựcthitại các thời điểm ‰ Biên dịch –nếuvị trí trong bộ nhớđã đượcbiếttrước–sinhra mã tuyệt đối (absolute code); cầnphải đượcbiêndịch lạinếuvị trí bắt đầubị thay đổi ‰ Lúc tải (loading time) –phảisinhramãcóthểđịnh vị lại (relocatable code) – nếuvị trí trong bộ nhớ không đượcbiết trước „ Mã có thểđịnh vị lại “14 bytes kể từđầu module” ‰ Lúc thựcthi–Gánđịachỉđược trì hoãn cho đếnkhithựcthi nếutiếntrìnhcóthể thay đổi, từđoạnbộ nhớ này đến đoạnbộ nhớ khác trong khi thựcthi. „ Yêu cầuphầncứng hỗ trợ cho các ánh xạđịachỉ (thanh ghi cơ sở, thanh ghi giớihạn) 2008-05-01 Nguyên lý Hệ điềuhành 5
  5. Các bướcxử lý củatiến trình người dùng 2008-05-01 Nguyên lý Hệ điềuhành 6
  6. Không gian địachỉ vật lý và không gian địac hỉ logic „ Khái niệ m không gian địachỉ logic gắnvới không gian địachỉ vậtlýlà trung tâm củacáckĩ thuậtquản lý bộ nhớ ‰ Các địachỉ logic – đượcsinhrabởiCPU; cònđượcgọilà địachỉảo ‰ Địachỉ vậtlý–địachỉ thật trong bộ nhớ, thấy đượcbởi đơnvị quảnlýbộ nhớ „ Như nhau trong lược đồ gán địachỉ lúc biên dịch, tải „ Khác nhau trong lược đồ gán địachỉ lúc thựcthi 2008-05-01 Nguyên lý Hệ điềuhành 7
  7. Đơnvị quảnlýbộ nhớ (MMU) „ Thiếtbị phầncứng thựchiệnviệcánhxạđịachỉảo đến địachỉ vậtlý „ Ví dụ về 1 lược đồ MMU đơngiản ‰ Giá trị thanh ghi relocation đượccộng vào cho mỗi địachỉ đượcsinhrabởitiến trình người dùng tạithời điểmnótải vào bộ nhớ. „ Chương trình người dùng làm việcvớicácđịachỉ logic; nó không bao giờ thấy địachỉ vậtlý 2008-05-01 Nguyên lý Hệ điềuhành 8
  8. Gán địachỉđộng với thanh ghi relocation 2008-05-01 Nguyên lý Hệ điềuhành 9
  9. Tải động vào bộ nhớ „ Các phương thức không đượctảivàobộ nhớ khi nó đượcgọi „ Tậndụng không gian bộ nhớ tốthơn ‰ Phương thức không đượcsử dụng sẽ không bao giờđượctải „ Hữu ích khi cầnlượng mã lớn để xử lý các trường hợp không thường xuyên „ Không cầnphảicósự hỗ trợđặcbiệtcủahệ điều hành trong thiếtkế chương trình 2008-05-01 Nguyên lý Hệ điềuhành 10
  10. Liên kết động „ Việc liên kếtsẽ bị trì hoãn đếnthờigianthựcthi „ Các đoạnmãnhỏ, gọilàstub, đượcsử dụng để xác định thủ tục thư viện trong vùng bộ nhớ thích hợp. „ Stub đượcthaythế bởi địachỉ vậtlýcủa routine và thựcthi routine „ Hệđiều hành cầnphảikiểmtraxemliệuphương thứccónằm trong địachỉ bộ nhớ củatiếntrình „ Liên kết động rấthữuhiệu cho các thư viện 2008-05-01 Nguyên lý Hệ điềuhành 11
  11. Overlays „ Chỉ giữ trong bộ nhớ những câu lệnh và dữ liệucần trong bấtcứ thời điểmnào „ Cầnkhitiếntrìnhlớnhơnkíchcỡ bộ nhớđượcgán cho nó „ Đượcthựcthibởingười dùng, không cầnsự hỗ trợ đặcbiệttừ hệđiều hành, thiếtkế lậptrìnhcủacấu trúc overlay tương đốiphứctạp 2008-05-01 Nguyên lý Hệ điềuhành 12
  12. Overlays 2008-05-01 Nguyên lý Hệ điềuhành 13
  13. 1.2. Swapping „ Mộttiếntrìnhcóthể bị swapped tạmrabộ lưutrữ nền , sau đó được mang trở lạibộ nhớđểthựcthitiếp „ Bộ lưutrữ nền–đĩatốc độ nhanh, đủ lớn để lưutrữ phiên bảncủatất cảảnh bộ nhớ cho tấtcả người dùng; phải cung cấpkhả năng truy cập trựctiệp đếncácảnh bộ nhớ này. „ Roll out, roll in –biếnthể swapping đượcsử dụng trong thuật toán lấp lịpcóưutiến; tiếntrìnhcóđộ ưutiênthấpnhấtbị swap ra cho phép tiếntrìnhcóđộ ưutiêncaonhất đượctảivàovàthựcthi. „ Một trong những giai đoạn quan trọng trong thời gian swap là thờigian chuyển đổingữ cảnh ‰ Tổng thờigianchuyểngiaotỉ lệ vớitổng dung lượng bộ nhớ bị swap. „ Ta có thể thấynhiều phiên bảnbiếnthể củatrênrất nhiềuhệ thống, i.e., UNIX, Linux, and Windows. 2008-05-01 Nguyên lý Hệ điềuhành 14
  14. Lược đồ Swapping 2008-05-01 Nguyên lý Hệ điềuhành 15
  15. 1.3. Phân phốibộ nhớ liên tục „ Bộ nhớ chính thường được chia thành hai phần ‰ Phầnlưutrúhệđiều hành, thường đượctổ chức trong vùng bộ nhớ thấp(địachỉ thấp) vớivector ngắt. ‰ Các tiến trình người dùng, thường đượctổ chức trong vùng bộ nhớ cao. „ Bảovệ ‰ Lược đồ thanh ghi relocation cho việcbảovệ các tiếntrình người dùng. ‰ Thay ghi relocation chứagiátrị của địachỉavậtlýnhỏ nhất; thanh ghi giớihạnchứa các giá trị từ miền địachỉ logic – các địachỉ logic phảicógiátrị nhỏ hơngiátrị của thanh ghi giớihạn. 2008-05-01 Nguyên lý Hệ điềuhành 16
  16. Hỗ trợ phầncứng cho các thanh ghi relocation và thanh ghi limit 2008-05-01 Nguyên lý Hệ điềuhành 17
  17. Phân phối liên tục (Cont.) „ Phân phối đa phân đoạn ‰ Lỗ hổng–khốibộ nhớ rỗi; các lỗ hổng vớinhững kích cỡ khác nhau nằm rải rác trong bộ nhớ. ‰ Khi mộttiếntrìnhcầntảivàobộ nhớ, nó được phân phối vùng bộ nhớ từ lỗ hổng đủ lớnchứanó. ‰ Hệđiều hành quản lý thông tin về: a) các phân đoạn đã được phân phốib) Cácphânđoạnrỗi(lỗ hổng) OS OS OS OS process 5 process 5 process 5 process 5 process 9 process 9 process 8 process 10 process 2 process 2 process 2 process 2 2008-05-01 Nguyên lý Hệ điềuhành 18
  18. Bài toán phân phốibộ nhớđộng „ Làm thế nào để phân phốitiến trình có kích cỡ n vào một danh sách các lỗ hổng còn rỗi ‰ First-fit: tìm lỗ hổng đầutiênđủ lớn ‰ Best-fit: tìm lỗ hổng bé nhất, đủ lớn „ Tìm kiếm trên toàn bộ danh sách các lỗ hổng (trừ phi các lỗ hổng đượcsắpxếp theo kích cỡ) „ Sinh ra phầnthừanhỏ nhất ‰ Worst-fit: tìm lỗ hổng lớnnhất „ Cũng phảitìmkiếm „ Sinh ra phầnthừalớnnhất „ First-fit và best-fit tốthơnchiếnlược worst-fit trên quan điểmtốc độ và sự tậndụng bộ nhớ 2008-05-01 Nguyên lý Hệ điềuhành 19
  19. Sự phân mảnh „ Phân mảnh ngoài –tổngkhônggianbộ nhớ có thể đáp ứng yêu cầu, nhưng không liên tục „ Phân mảnh trong –bộ nhớđược phân phốicóthể lớnhơnmột chút so vớiyêucầu; sự khác biệtvề kích cỡ này là nộitrongmột phân đoạn, và ko được sử dụng „ Làm giảm phân mảnh ngoài bằng kếtkhối ‰ Xáo các nội dung bộ nhớđểđặttấtcả vùng bộ nhớ rỗi cạnh nhau tạo thành mộtkhốilớn ‰ Kếtkhốichỉ thích hợpkhiviệc phân đoạnlạilàđộng và đượcthựchiệntạilúcthựcthi 2008-05-01 Nguyên lý Hệ điềuhành 20
  20. 1.4. Phân trang (paging) „ Không gian địachỉ logic củamộttiếntrìnhcóthể không liên tục; „ Chia bộ nhớ vật lý thành các khốicókíchcỡ cốđịnh gọilà frames (kích cỡ là lũythừacủa 2, khoảng từ 512 bytes đến 8192 bytes). „ Chia bộ nhớ logic thành các khốicũng kích cỡ, gọilàtrang (pages). „ Lưulạitấtcả các frames rỗi. „ Để thựcthimộtchương trình có n pages, cầntìmn frames rỗivà tảichương trình vào. „ Thiếtlậpmộtbảng page để chuyển đổi địachỉ logic thành địachỉ vậtlý. „ Có sự phân mảnh trong. 2008-05-01 Nguyên lý Hệ điềuhành 21
  21. Lược đồ dịch địachỉ „ Địachỉ sinh bởiCPU được chia thành hai phần ‰ Page number (p) – đượcsử dụng như là mộtchỉ số trong bảng page, chứa địachỉ cơ sở củamỗi page trong bộ nhớ vậtlý ‰ Page offset (d) – đượckếthợpvới địachỉ cơ sở để xác định địachỉ vậtlýđượcgửichođơnvị bộ nhớ. 2008-05-01 Nguyên lý Hệ điềuhành 22
  22. Kiếntrúcdịch địachỉ 2008-05-01 Nguyên lý Hệ điềuhành 23
  23. Ví dụ về phân trang 2008-05-01 Nguyên lý Hệ điềuhành 24
  24. Ví dụ phân trang 2008-05-01 Nguyên lý Hệ điềuhành 25
  25. Các frame rỗi Trước khi phân phối Sau khi phân phối 2008-05-01 Nguyên lý Hệ điềuhành 26
  26. Thực thi bảng page „ Bảng page đượclưutrữ trong bộ nhớ trong. „ Thanh ghi cơ sở bảng-trang (PTBR) trỏđếnbảng trang. „ Thanh ghi độ dài bảng trang (PRLR) chỉ kích cỡ của bảng trang. „ Trong lược đồ này, mọitruycập đếndữ liệuvàcâu lệnh đòi hỏi hai lầntruycậpbộ nhớ. ‰ Mộtlầnchobảng trang và mộtlầnchodữ liệu/ câu lệnh. „ Hai vấn đề truy cậpbộ nhớ này có thểđượcgiải quyếtbằng cách sử dụng một cache phầncứng tra cứu nhanh gọilàbộ nhớ kếthợp hay bộđệmdịch (TLBs) 2008-05-01 Nguyên lý Hệ điềuhành 27
  27. Bộ nhớ kếthợp „ Bộ nhớ kếthợp – tìm kiếm song song Page # Frame # Dịch địachỉ (A’, A’’) ‰ NếuA’làthanhghik ếthợp, lấy frame# ra ‰ Nếu không, lấy frame# từ bảng trang trong bộ nhớ 2008-05-01 Nguyên lý Hệ điềuhành 28
  28. Phầncứng cho phân trang, TLB 2008-05-01 Nguyên lý Hệ điềuhành 29
  29. Thờigiantruycậphiệuquả „ Tra cứukếthợp= ε thờigianđơnvị „ Giả sử thờigianchukỳ bộ nhớ là 1 micro giây „ Tỉ lệ hit – phầntrămthờigianmàmột page number được tìm thấy trong các thanh ghi kếthợp; khẩu phần liên quan đếnsố các thanh ghi kếthợp. „ Hit ratio = α „ Thờigiantruycậphiệuquả(EAT) EAT = (1 + ε) α + (2 + ε)(1 – α) = 2 + ε – α 2008-05-01 Nguyên lý Hệ điềuhành 30
  30. Bảovệ bộ nhớ „ Bảovệ bộ nhớ bằng cách kếthợp các bit bảo vệ mớimỗiframe. „ Bit valid-invalid gắnvớimỗiphầntử của bảng trang: ‰ “valid” chỉ rằng trang liên kếttrongmột không gian địachỉ logic, và là mộttranghợplệ. ‰ “invalid” chỉ rằng trang không ở trong một không gian địachỉ logic. 2008-05-01 Nguyên lý Hệ điềuhành 31
  31. Bit valid và invalid trong bảng trang 2008-05-01 Nguyên lý Hệ điềuhành 32
  32. Các trang chia sẻ „ Mã chia sẻ ‰ Một phiên bảnmãchỉđọc đượcchiasẻ giữa nhiềutiến trình(i.e., text editors, compilers, window systems). ‰ Mã chia sẻ phảixuấthiệntại cùng mộtvị trí trong không gian địachỉ logic củatấtcả các tiếntrình. „ Mã và dữ liệuriêng ‰ Mỗitiếntrìnhlưutrữ một phiên bảnriêngcủamãvàdữ liệu. ‰ Các trang cho mã riêng và dữ liệu riêng có thể xuấthiện mọinơi trong không gian địachỉ logc. 2008-05-01 Nguyên lý Hệ điềuhành 33
  33. Ví dụ về các trang chia sẻ 2008-05-01 Nguyên lý Hệ điềuhành 34
  34. 1.5. Cấutrúcbảng trang „ Phân trang phân cấp „ Các bảng trang băm „ Các bảng trang đánh chỉ số ngược 2008-05-01 Nguyên lý Hệ điềuhành 35
  35. Các bảng trang phân cấp „ Chia không gian địachỉ vật lý thành nhiều bảng trang. „ Mộtkĩ thuật đơngiảnlàsử dụng bảng trang hai mức. 2008-05-01 Nguyên lý Hệ điềuhành 36
  36. Ví dụ về bảng trang hai mức „ Một địachỉ logic (trên máy 32 bit vớikíchcỡ trang 4K) được chia thành: ‰ Page number gồm20 bits ‰ Page offset gồm 12 bits „ Khi bảng trang được phân trang, page number đượcchiatiếp thành: ‰ Một page number 10 bits. ‰ Một page offset 10 bit. „ Như vậy, không gian địachỉ logic sẽ như sau: page number page offset pi p2 d 10 10 12 ởđây pi là mộtchỉ số củabảng page ngoài và p2 là độ dịch chuyển trong trang củabảng trang ngoài. 2008-05-01 Nguyên lý Hệ điềuhành 37
  37. Lược đồ bảng trang hai mức 2008-05-01 Nguyên lý Hệ điềuhành 38
  38. Lược đồ dịch địachỉ „ Lược đồ dịch địachỉ cho kiến trúc phân trang 32-bit hai tầng. 2008-05-01 Nguyên lý Hệ điềuhành 39
  39. Các bảng trang băm „ Thông thường các không gian địachỉ > 32 bits. „ Chỉ số trang ảo đượcbămvàomộtbảng trang. Bảng trang này chứamộtchuỗicácphầntửđược bămvàocùngmộtvị trí. „ Các chỉ số trang ảo được tìm kiếmtrongchuỗinày. Nếutìmthấy, frame vậtlýtương ứng đượclấyra. 2008-05-01 Nguyên lý Hệ điềuhành 40
  40. Bảng trang băm 2008-05-01 Nguyên lý Hệ điềuhành 41
  41. Bảng trang ngược „ Mỗiphầntừ tương ứng vớimột trang thật trong bộ nhớ. „ Mỗiphầnthử gồm địachỉảocủa trang đượclưu trong phầnbộ nhớ thật, với thông tin về tiếntrình chứa trang đó. „ Giảmbộ nhớ cầnthiết để lưutrữ mỗibảng trang, nhưng tăng thờigiancầnthiết để tìm kiếmbảng khi mộtyêucầutruycậptrangxuấthiện. „ Sử dụng trang băm để giớihạntìmkiếm đếnmột, hoặcmộtvàiphầntử củabảng trang. 2008-05-01 Nguyên lý Hệ điềuhành 42
  42. Kiếntrúcbảng trang ngược 2008-05-01 Nguyên lý Hệ điềuhành 43
  43. 1.6. Phân đoạn „ Lược đồ quảnlýbộ nhỡ hỗ trợ quan điểmcủangười dùng về bộ nhớ. „ Mộtchương trình là mộttậpcácđoạn. Một đoạnlàmột đơnvị logic gồmcó: main program, procedure, function, method, object, local variables, global variables, common block, stack, symbol table, arrays 2008-05-01 Nguyên lý Hệ điềuhành 44
  44. Quan điểmngười dùng củamột chương trình 2008-05-01 Nguyên lý Hệ điềuhành 45
  45. Quan điểm logic của segmentation 1 4 1 2 3 2 4 3 user space physical memory space 2008-05-01 Nguyên lý Hệ điềuhành 46
  46. Kiến trúc phân đoạn „ Địachỉ logic gồm hai phần: , „ Bảng Segment– ánh xạ các địachỉ vật lý hai chiều; mỗiphầntử củabảng có: ‰ Base –chứa địachỉ vậtlýbắt đầunơi mà các segment lưutrú trong bộ nhớ. ‰ Limit –xácđịnh kích cỡ của segment. „ Segment-table base register (STBR) trỏđếnbảng segment trong bộ nhớ. „ Segment-table length register (STLR) thế hiệnsố các segments đượcsử dụng bởimộtchương trình; segment number s là hợplệ nếu s < STLR. 2008-05-01 Nguyên lý Hệ điềuhành 47
  47. Kiến trúc segmentation (cont.) „ Xác định vị trí lại. ‰ Động ‰ Dùng bảng segment „ Chia sẻ. ‰ Các đoạn đượcchiasẻ. ‰ Cùng segment number „ Phân phối. ‰ first fit/best fit ‰ Phân mảnh ngoài 2008-05-01 Nguyên lý Hệ điềuhành 48
  48. Kiến trúc phân đoạn „ Bảovệ. Mộtphầntừ trong bảng segment liên kết với: ‰ Bit hợplệ = 0 ⇒ segment không hợplệ ‰ Ưu tiên read/write/execute „ Các bits bảovệ kếthợpvới các segments; chia sẻ mã ở mức segment. „ Khi các segment thay đổikíchcỡ, phân phốibộ nhớ là phân phối động. „ Mộtvídụ segmentation được cho trong hình vẽ sau 2008-05-01 Nguyên lý Hệ điềuhành 49
  49. Phầncứng phân đoạn 2008-05-01 Nguyên lý Hệ điềuhành 50
  50. Ví dụ về phân đoạn 2008-05-01 Nguyên lý Hệ điềuhành 51
  51. Chia sẻ các đoạn 2008-05-01 Nguyên lý Hệ điềuhành 52
  52. Phân đoạnkếthợpvới phân trang „ Hệ thống MULTICS giảiquyết bài toán phân mảnh ngoài bằng cách phân trang các segments. „ Giải pháp khác với segmentation thuầntúylà phầntừ bảng segment không chứa địachỉ cơ sở củasegment màđịachỉ cơ sở của bảng trang cho segment này. 2008-05-01 Nguyên lý Hệ điềuhành 53
  53. Lược đồ dịch địachỉ MULTICS 2008-05-01 Nguyên lý Hệ điềuhành 54
  54. Phân đoạnkếthợpvới phân trang – Intel 386 „ Như tronghìnhvẽ sau, Intel 386 sử dụng segmentation với paging cho việcquảnlýbộ nhớ vớilược đồ hai tầng phân trang. 2008-05-01 Nguyên lý Hệ điềuhành 55
  55. Dịch địachỉ Intel 30386 2008-05-01 Nguyên lý Hệ điềuhành 56
  56. 2. Bộ nhớảo 1. Cơ sở 2. Phân trang theo yêu cầu 3. Hi ệunăng của phân trang theo yêu cầu 4. Thay thế trang 5. Các thu ậttoánthayth ế trang 6. C ấp phát frames 7. Thrashing 8. Các vấn đề khác 2008-05-01 Nguyên lý Hệ điềuhành 57
  57. 2.1. Cơ sở „ Câu lệnh/ dữ liệucần trong BNTđể thựchiện „ Không cầnthường xuyên lưu toàn bộ chương trình người dùng vào trong BNT „ Bộ nhớảo –táchbiệtbộ nhớ logic mứcngười dùng và bộ nhớ vậtlý ‰ Chỉ mộtphầnchương trình cần trong bộ nhớđểthựcthi ‰ Không gian địachỉ logic có thể lớnhơn nhiều không gian địachỉ vậtlý ‰ Cho phép chia sẻ các không gian địachỉ bởimộtsố tiến trình. ‰ Cho phép tạo nhiềutiếntrìnhmộtcáchhiệuquả. „ Bộ nhớảocóthểđượcthực thi thông qua: ‰ Phân trang theo yêu cầu ‰ Phân đoạn theo yêu cầu 2008-05-01 Nguyên lý Hệ điềuhành 58
  58. Bộ nhớảolớnhơnbộ nhớ vậtlý 2008-05-01 Nguyên lý Hệ điềuhành 59
  59. Không gian địachỉảo 2008-05-01 Nguyên lý Hệ điềuhành 60
  60. Thư việnchiasẻ dùng bộ nhớảo 2008-05-01 Nguyên lý Hệ điềuhành 61
  61. 2.2. Phân trang theo yêu cầu „ Chỉ tảimột trang vào bộ nhớ khi cầnthiết ‰ Cầnvào/raít ‰ Cầnbộ nhớ ít ‰ Phản ứng nhanh hơn ‰ Cho phép nhiềungười dùng hơn „ Cầnmộttrang⇒ tham chiếu đếnnó ‰ Tham chiếu không hợplệ ⇒ bỏ qua ‰ Không trong bộ nhớ ⇒ tảivàobộ nhớ 2008-05-01 Nguyên lý Hệ điềuhành 62
  62. Chuyểnbộ nhớđược phân trang vào không gian đĩ aliêntục 2008-05-01 Nguyên lý Hệ điềuhành 63
  63. Bit valid/invalid „ Liên kếtmỗiphầntử củabảng trang vớimột bit valid/invalid (1 ⇒ in-memory, 0 ⇒ not-in-memory) „ Bit valid–invalid đượckhởitạobằng 0 vớimọiphầntử củabảng trang. „ Ví dụ về mộtbảng trang. Frame # valid-invalid bit 1 1 1 1 0 M 0 0 page table „ Trong quá trình dịch địachỉ, nếu bit valid-invalid trong phầntử bảng trang là 0 ⇒ lỗi trang. 2008-05-01 Nguyên lý Hệ điềuhành 64
  64. Bảng trang khi một vài trang không trong bộ nhớ chính 2008-05-01 Nguyên lý Hệ điềuhành 65
  65. Lỗitrang „ Tham chiếu đếnmột trang không có trong bộ nhớ, trước tiên tham chiếusinhramột trap cho hệđiều hành ⇒ lỗi trang „ Hệđiều hành kiểmtrabảng khác để xác định ‰ Tham chiếu không hợplệ ⇒ bỏ qua. ‰ Trang không có trong bộ nhớ. „ Lấyramột frame rỗng „ Tráo đổi trang vào frame „ Thiếtlậplạicácbảng, bit valid = 1 „ Khởitạolạilệnh: ‰ Chuyểnkhối 2008-05-01 Nguyên lý Hệ điềuhành 66
  66. Các bướcxử lý lỗitrang 2008-05-01 Nguyên lý Hệ điềuhành 67
  67. Trường hợp không còn frame rỗi „ Thay thế trang ‰ Tìm mộttrangnàođóhiệntrongbộ nhớ, nhưng đang không đượcsử dụng, swap nó ra. ‰ Thuật toán thay trang ‰ Hiệunăng – cầnmộtthuậntoántrả lạivớiítlỗi trang nhấtcóthể. „ Trangcóthểđượctảivàobộ nhớ mộtvài lần. 2008-05-01 Nguyên lý Hệ điềuhành 68
  68. 2.3. Hiệunăng của phân trang theo yêu cầu „ Tỉ lệ lỗ i trang 0 ≤ p ≤ 1.0 ‰ Nếu p = 0, không có lỗitrang ‰ Nếu p = 1, mọi tham chiếu đềulỗi „ Thờigiantruycậphiệuquả (EAT) EAT = (1 – p) x thời gian truy cậpbộ nhớ + p (phụ trội do lỗ i trang + [swap trang ra ] + swap trang vào + phụ trộido khở i động lại) 2008-05-01 Nguyên lý Hệ điềuhành 69
  69. Ví dụ về phân trang theo yêu cầu „ Thờigiantruycậpbộ nhớ = 1 microsecond „ 50% trang bị thay thế cầnphảicậpnhậtlại (do đã có sửa đổi) Æ 50% trang cầnphải đượcswap ra „ Thời gian Swap trang = 10 msec = 10,000 microsec EAT = (1 – p) x 1 + p (15000) 1 + 15000P (in microsec) 2008-05-01 Nguyên lý Hệ điềuhành 70
  70. 2.4. Thay thế trang „ Tránhtìnhtrạng phân phốibộ nhớ quá tải ‰ Dịch vụ lỗi trang bao gồmviệc thay trang. „ Sử dụng bít sửa đổi (dirty) ‰ Giảmthờigianphụ trộicủaviệcchuyển trang – chỉ có các trang bị sửa đổimớiphải ghi lạilênđĩa. „ Thay trang làm tăng sự tách biệt giữabộ nhớ logic và bộ nhớ vậtlý 2008-05-01 Nguyên lý Hệ điềuhành 71
  71. Yêu cầu thay trang 2008-05-01 Nguyên lý Hệ điềuhành 72
  72. Kĩ thuật thay trang cơ bản 1. Tìm vị trí củatrangyêucầutrênđĩa. 2. Tìm mộtframe rỗi: -Nếucómộtframe rỗi, tậndụng frame đó. -Nếu không có frame rỗi, áp dụng thu ậttoán thay trang để lựach ọ nmộtframe n ạn nhân . 3. Đọctrangyêucầu vào frame mớirỗi. Cậpnhật trang và bảng frame 4. Khởi động lạitiến trình. 2008-05-01 Nguyên lý Hệ điềuhành 73
  73. Thay trang 2008-05-01 Nguyên lý Hệ điềuhành 74
  74. 2.5. Các thuật toán thay thế trang „ Mục đích: tỉ lệ lỗi trang thấpnhất. „ Đánh giá thuật toán ‰ Áp dụng thuậttoántrênmộtchuỗi các tham chiếu bộ nhớ ‰ Tính toán số lỗi trang trên chuỗi đó. „ Trong tấtcả các ví dụ sau, ta sử dụng chuỗi tham chiếusau 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. 2008-05-01 Nguyên lý Hệ điềuhành 75
  75. Đồ thị mô tả số lỗitrangtheosố Frames 2008-05-01 Nguyên lý Hệ điềuhành 76
  76. Thuậttoánvàotrướcratrước(FIFO) „ Chuỗi tham chiếu: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 „ 3 frames (mỗitiếntrìnhchỉ có 3 trang cùng ở trong bộ nhớ tại cùng mộtthời điểm) 1 1 4 5 2 2 1 3 9 page faults 3 3 2 4 „ 4 frames 1 1 5 4 2 2 1 5 10 page faults 3 3 2 4 4 3 „ Thay thế FIFO – Belady’s Anomaly ‰ Nhiềuframes ⇒ ít lỗi trang 2008-05-01 Nguyên lý Hệ điềuhành 77
  77. Thay trang theo thuật toán FIFO 2008-05-01 Nguyên lý Hệ điềuhành 78
  78. Thuậttoántối ưu „ Thay trang sẽ không đượcsử dụng trong thờigian dài „ Ví dụ 4 frames: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1 4 2 6 page faults 3 4 5 „ Làm thế nào biết được điềunày? „ Đượcsử dụng để đánh giá hiệusuấtthuậttoánsử dụng 2008-05-01 Nguyên lý Hệ điềuhành 79
  79. Thuật toán thay trang tối ưu 2008-05-01 Nguyên lý Hệ điềuhành 80
  80. Thuật toán LRU (least recently used) „ Chuỗi tham chiếu: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 1 5 2 3 5 4 4 3 „ Thực thi counter ‰ Mọiphầntử trang có một counter; mỗilầntrangđược tham chiếu đến Æ cậpnhật counter bằng thời điểmthamchiếumới. ‰ Khi một trang cần thay đổi, xem xét các counter để xác định trang nạn nhân. 2008-05-01 Nguyên lý Hệ điềuhành 81
  81. ThuậttoánLRU 2008-05-01 Nguyên lý Hệ điềuhành 82
  82. ThuậttoánLRU „ Cài đặtbằng ngănxếp ‰ Lưugiữ số hiệu trang trong mộtngănxếp „ Cài đặtmột danh sách liên kếtkép ‰ Tham chiếu trang: „ Chuyểnlênđầungănxếp „ Cần thay đổitổng cộng 6 con trỏ ‰ Không đòi hỏitìmkiếm khi thay trang 2008-05-01 Nguyên lý Hệ điềuhành 83
  83. Sử dụng mộtngănxếp để lưutrữ hầuhết các tham chi ếumới 2008-05-01 Nguyên lý Hệ điềuhành 84
  84. Các thuậttoánxấpxỉ LRU „ Bit tham chiếu ‰ Mỗi trang liên kếtvớimột bit, bit này đượckhởitạobằng 0 ‰ Khi một trang được tham chiếu đến, bit đượcthiếtlậpbằng 1 ‰ Thay thế bit 0 (nếu có). Tuy nhiên ta không biếtthứ tự thay thế. „ Cơ hộithứ hai ‰ Cần bit tham chiếu. ‰ Thay thếđồng hồ. ‰ Nếu trang chuẩnbịđược thay thế (theo thứ tựđồng hồ) có bit tham chiếu= 1. „ Thiếtlậpbit thamchiếubằng 0. „ Để lại trang đótrongbộ nhớ. „ Thay thế trang kế tiếp (theo thứ tựđồng hồ), theo cùng mộtsố luật. 2008-05-01 Nguyên lý Hệ điềuhành 85
  85. ThuậttoánCơ hộithứ hai 2008-05-01 Nguyên lý Hệ điềuhành 86
  86. 2.6. Cấp phát frames „ Mỗitiếntrìnhcầnmộtsố lượng ít nhấtcác trang cần dùng „ Ví dụ: IBM 370 – cần 6 trang để thựchiện lệnh SS MOVE: ‰ Lệnh 6 bytes, lưu trong 2 trang ‰ 2 trang để xử lý from ‰ 2 trang để xử lý to „ Hai lược đồ phân phốicơ bản ‰ Phân phốicốđịnh ‰ Phân phối ưutiên 2008-05-01 Nguyên lý Hệ điềuhành 87
  87. Cấp phát cốđịnh „ Cấp phát đều–Vídụ: Nếu có 100 frames và 5 tiến trình, cấpcho mỗitiến trình 20 frames. „ Cấp phát tỉ lệ –Cấp phát theo kích cỡ củatiếntrình sizesi = of processpi S= ∑ i s total m = number of frames s a allocation= p= i for ×m i i S m = 64 si = 10 s2 = 127 10 a= ×64 ≈ 5 1 137 127 a=64 × ≈ 59 2 137 2008-05-01 Nguyên lý Hệ điềuhành 88
  88. Cấp phát ưu tiên „ Lược đồ cấp phát tỉ lệ theo độ ưutiên(thayvì theo kích cỡ) „ NếutiếntrìnhPi phát sinh mộtlỗi trang ‰ Chọn để thay thế một trong các frame củanó ‰ Chọn để thay thế mộtframe từ mộttiếntrìnhvới độ ưutiênthấphơn 2008-05-01 Nguyên lý Hệ điềuhành 89
  89. Cấp phát cụcbộ và cấp phát toàn cục „ Cấp phát toàn cục –tiếntrìnhlựachọnmộtframe thay thế từ tậptấtcả các frame; mộttiếntrìnhcóthể lấymộtframe củatiến trình khác. „ Cấpphátcụcbộ –tiếntrìnhchỉ lựachọnframe thay thế từ tập các frame củanó 2008-05-01 Nguyên lý Hệ điềuhành 90
  90. 2.7. Thrashing „ Nếumộttiến trình không có “đủ” trang, tỉ lệ lỗitrang có thể rấtcao. ‰ Tính tậndụng CPU thấp „ Hệđiềuhànhmuốntăng độ đachương trình ‰ Tiếntrìnhmới được thêm vào hệ thống „ Thrashing ≡ mộttiến trình dùng nhiềuthờigiancho việc thay trang 2008-05-01 Nguyên lý Hệ điềuhành 91
  91. Thrashing (tiếp) 2008-05-01 Nguyên lý Hệ điềuhành 92
  92. Phân trang theo yêu cầu và thrashing „ Mô hình cụcbộ ‰ Các tiếntrìnhditrútừ miềncụcbộ này sang miềncụcbộ khác ‰ Các miềncụcbộ có thể bị chồng chéo. „ Vì sao lạixuấthiện thrashing? Σ kích cỡ các miềncụcbộ > dung lượng bộ nhớ 2008-05-01 Nguyên lý Hệ điềuhành 93
  93. Mô hình “tậplàmviệc” „ Δ≡cửasổ tậplàmviệc ‰ Mộttậpcốđịnh các tham chiếu trang ‰ Ví dụ: 10,000 lệnh „ WSSi (tậplàmviệccủatiếntrìnhPi) ‰ Tổng số trang được tham chiếu trong cửasổ làm việcmớinhất Δ (thay đổi theo thời gian) ‰ Δ quá nhỏ sẽ không chứa được toàn bộ mộtmiềncụcbộ ‰ Δ quá lớnsẽ chứa đồng thờimộtsố miềncụcbộ ‰ Δ = ∞⇒chứa toàn bộ chương trình „ D = Σ WSSi ≡ tổng các frames yêu cầu „ Nếu D > m ⇒ Thrashing „ Chiếnlược: Nếu D > m, thựchiện phong tỏamột trong số các tiếntrình 2008-05-01 Nguyên lý Hệ điềuhành 94
  94. Mô hình tậplàmviệc 2008-05-01 Nguyên lý Hệ điềuhành 95
  95. Lược đồ tầnsuấtlỗitrang „ Thiếtlậpmộttỉ lệ lỗi trang chấpnhận được ‰ Nếutỉ lệ lỗithựctế thấp, tiến trình giải phóng frames ‰ Nếutỉ lệ lỗithựctế cao, tiếntrìnhlấy thêm frames 2008-05-01 Nguyên lý Hệ điềuhành 96
  96. 2.8. Các vấn đề khác „ Thựcthi“tiền phân trang” ‰ Giảmmộtsố lượng lớnlỗi trang xuấthiệnvào thời điểmbắt đầutiếntrình ‰ Phân trướcmộtsố trang mà tiếntrìnhcóthể cần tới ‰ Thựchiện“tiền phân trang” có thể làm lãng phí thiếtbị vào ra hoặcbộ nhớ „ Nếuthờigiantiếtkiệm được do lỗitranglớnhơnthời gian lãng phí Æ nên dùng tiềnphântrang 2008-05-01 Nguyên lý Hệ điềuhành 97
  97. Kích cỡ trang „ Xem xét các yếutốđểquyết định kích cỡ trang: ‰ Phân mảnh ‰ Kích cỡ bảng ‰ Phụ trội do vào ra ‰ Tham chiếucụcbộ 2008-05-01 Nguyên lý Hệ điềuhành 98
  98. Cấutrúcchương trình „ Cấutrúcchương trình ‰ Int[128,128] data; ‰ Mỗi hàng đượclưu trong 1 trang ‰ Chương trình 1 for (j = 0; j <128; j++) for (i = 0; i < 128; i++) data[i,j] = 0; 128 x 128 = 16,384 lỗi trang ‰ Chương trình 2 for (i = 0; i < 128; i++) for (j = 0; j < 128; j++) data[i,j] = 0; 128 lỗi trang 2008-05-01 Nguyên lý Hệ điềuhành 99
  99. 3. Giao diệnhệ thống file 1. Khái niệm file 2. Các phươ ng pháp truy nhập file 3. Chia sẻ file 4. G ắnhệ thố ng file 5. B ảovệ 2008-05-01 Nguyên lý Hệ điềuhành 100
  100. Hệ thống file „ Hệ thống file cung cấpkholưutrữ lâu dài cho chương trình và dữ liệu. ‰ Để đảmbảoviệclưutrữ lâu dài, các file đượclưu trữ trên đĩa ‰ Để có thể sử dụng nội dung file, CPU đọcfile vào bộ nhớ trong „ Hệ thồng file bao gồm ‰ Mộttậpcácfile ‰ Mộtcấutrúcthư mục 2008-05-01 Nguyên lý Hệ điềuhành 101
  101. 3.1. Khái niệm file „ Mộttậpdữ liệu đượclưutrữ trong thiếtbị lưutrữ thứ cấp. „ Thông thường, một file lưutrữ chương trình hoặc dữ liệu ‰ Mộtchuỗi các bit, bytes, dòng hoặcbảnghi ‰ Ý nghĩacủacácbản ghi này được định nghĩabởingười tạo „ Hệđiềuhànhtrừutượng hóa chi tiếtcủamỗithiếtbị lưutrữ ‰ Người dùng thấymộtmảng tuyến tính các bản ghi ‰ Hệđiềuhànhánhxạ file logic lên thiếtbị lưutrữ 2008-05-01 Nguyên lý Hệ điềuhành 102
  102. Cấu trúc file „ Không có cấutrúc–chuỗicáctừ (words), bytes „ Cấutrúcbản ghi đơngiản ‰ Các dòng ‰ Kích cỡ cốđịnh ‰ Kích cỡ thay đổi „ Các cấutrúcphứctạp ‰ Tài liệu được định dạng ‰ File có thểđịnh vị lại được „ Có thể cài đặtcấutrúcphứctạpbằng cách thêm mộtsố kí tựđiềukhiển vào file. 2008-05-01 Nguyên lý Hệ điềuhành 103
  103. Những thông tin về file mà HĐH quảnlý „ File có các thuộc tính: ‰ Tên (name) ‰ Sốđịnh danh (identifier) ‰ Kiểu (type) ‰ Vị trí (location) ‰ Kích thước(size) ‰ Bảovệ (protection) : thông tin điềukhiểntruycập ‰ OwnerID ‰ Thời gian: tạo, sửa đổilầncuối, truy cậplầncuối 2008-05-01 Nguyên lý Hệ điềuhành 104
  104. Ví dụ về khối điềukhiển file trong Linux 2008-05-01 Nguyên lý Hệ điềuhành 105
  105. Các thao tác trên file „ File là mộtkiểudữ liệutrừutượng „ Thông thường, có các thao tác trên file sau ‰ create(): tìm không gian trong hệ thống cho một file và sau đó thêm nó vào thư mục ‰ write(): thêm dữ liệuvàofile tạivị trí hiệntại ‰ read(): đọcdữ liệutừ file bắt đầutừ vị trí hiệntại ‰ seek(): thay đổivị trí con trỏđọchoặc ghi đếnmột ví trí xác định trong file ‰ delete(): xóa mộtfile khỏihệ thống file 2008-05-01 Nguyên lý Hệ điềuhành 106
  106. Các file mở „ Các thông tin để quản lý các file đang mở: ‰ Con trỏ file: trỏđếnvị trí đọc/ghi cuối „ Thông tin đơntiếntrình ‰ Số lầnmở file – Khi các tiếntrìnhmở file thoát Æ xóa phầntử tương ứng với file trong bảng file mở „ Thông tin hệ thống ‰ Vị trí đĩa: Lưulại thông tin truy nhậpdữ liệu ‰ Các quyềntruynhập: mode truy nhập đốivớimỗi tiếntrình 2008-05-01 Nguyên lý Hệ điềuhành 107
  107. Khóa các file mở „ Mộtsố HDH và hệ thống file hỗ trợ khóa các file mở „ Sắpxếpviệctruynhập file „ Bắtbuộc/Tư vấn: ‰ Bắtbuộc –truyvấnbị từ chốitùythuộckhóavà yêu cầu ‰ Tư vấn –cáctiếntrìnhkiểmtratrạng thái của khóa và xác định. 2008-05-01 Nguyên lý Hệ điềuhành 108
  108. Ví dụ khóa file trong Java import java.io.*; import java.nio.channels.*; public class LockingExample { public static final boolean EXCLUSIVE = false; public static final boolean SHARED = true; public static void main(String arsg[]) throws IOException { FileLock sharedLock = null; FileLock exclusiveLock = null; try { RandomAccessFile raf = new RandomAccessFile("file.txt", "rw"); // get the channel for the file FileChannel ch = raf.getChannel(); // this locks the first half of the file - exclusive exclusiveLock = ch.lock(0, raf.length()/2, EXCLUSIVE); / Now modify the data . . . */ // release the lock exclusiveLock.release(); 2008-05-01 Nguyên lý Hệ điềuhành 109
  109. Ví dụ khóa file trong Java // this locks the second half of the file - shared sharedLock = ch.lock(raf.length()/2+1, raf.length(), SHARED); / Now read the data . . . */ // release the lock exclusiveLock.release(); } catch (java.io.IOException ioe) { System.err.println(ioe); }finally { if (exclusiveLock != null) exclusiveLock.release(); if (sharedLock != null) sharedLock.release(); } } } 2008-05-01 Nguyên lý Hệ điềuhành 110
  110. Các kiểu file – tên, phầnmở rộng 2008-05-01 Nguyên lý Hệ điềuhành 111
  111. 3.2. Các phương pháp truy cập „ Truy cậptuầntự read next write next reset no read after last write (rewrite) „ Truy cậptrựctiếp read n write n position to n read next write next rewrite n n = số hiệutương đốicủakhối 2008-05-01 Nguyên lý Hệ điềuhành 112
  112. File truy nhậptuầntự 2008-05-01 Nguyên lý Hệ điềuhành 113
  113. Mô phỏng truy cậptuầntự trên mộtfile truy nh ậptrự ctiếp 2008-05-01 Nguyên lý Hệ điềuhành 114
  114. Ví dụ về chỉ số và các file tương đối 2008-05-01 Nguyên lý Hệ điềuhành 115
  115. 3.3.Cấu trúc thư mục „ Các đĩathường đượctổ chức thành các phân vùng. „ Các thư mụcthuthậpvàtổ chức các file trên một phân vùng Directory Files F 2 F 4 F 1 F 3 F n 2008-05-01 Nguyên lý Hệ điềuhành 116
  116. Cách thứctổ chứcmộthệ thống file điển hình 2008-05-01 Nguyên lý Hệ điềuhành 117
  117. Các thao tác trên thư mục „ search: tìm một file hoặctập các file khớpvới điềukiệntìmkiếm „ create: tạomột file trên mộtthư mục „ delete: xóa một file khỏimộtthư mục „ list: xem nội dung thư mục „ rename: thay đổitêncủamột file „ traverse 2008-05-01 Nguyên lý Hệ điềuhành 118
  118. Tổ chứcthư mục(mức logic) „ Hiệuquả ‰ Xác định vị trí các file một cách nhanh chóng „ Đặttên–thuậntiện cho người dùng ‰ Hai người dùng có thể dùng cùng 1 tên cho hai file khác nhau ‰ File giống nhau có thể có các tên khác nhau „ Gộp nhóm – gộp các file có cùng đặctrưng lại thành các nhóm (e.g., các file chương trình java, tấtcả trò chơi, ) 2008-05-01 Nguyên lý Hệ điềuhành 119
  119. Cấutrúcđơnmức „ Mộtthư mục đơnchotấtcả người dùng „ Vấn đề ‰ Đặttên ‰ Gộp nhóm 2008-05-01 Nguyên lý Hệ điềuhành 120
  120. Cấutrúchaimức „ Mỗingười dùng có mộtthư mục „ Đường dẫn „ Cho phép hai người dùng khác nhau đặt cùng mộttênfile „ Tìm kiếmhiệuquả „ Chưacótínhnăng gộp nhóm 2008-05-01 Nguyên lý Hệ điềuhành 121
  121. Cấu trúc cây 2008-05-01 Nguyên lý Hệ điềuhành 122
  122. Cấu trúc cây „ Tìm kiếmhiệuquả „ Tính năng gộp nhóm „ Thư mụchiệnthời(thư mục làm việc) ‰ cd /spell/mail/prog ‰ type list 2008-05-01 Nguyên lý Hệ điềuhành 123
  123. Cấutrúcđồ thị không có chu trình 2008-05-01 Nguyên lý Hệ điềuhành 124
  124. Cấutrúcđồ thị không có chu trình „ Làm sao đảmbảo không có chu trình? ‰ Chỉ chophéptạoliênkết đến file mà không cho tạoliênkết đếncácthư mụccon ‰ Thu rác (garbage collection) ‰ Mỗikhimộtliênkếtmới được thêm, sử dụng một thuật toán xác định chu trình để kiểmtraxemcó thêm được không 2008-05-01 Nguyên lý Hệ điềuhành 125
  125. 3.4.Gắn hệ thống file „ Mộthệ thống file cần được gắn trướckhicóthể truy cập 2008-05-01 Nguyên lý Hệ điềuhành 126
  126. ĐiểmgắnHệ thống file 2008-05-01 Nguyên lý Hệ điềuhành 127
  127. 3.5.Chia sẻ file „ Nhu cầuchiasẻ file trong hệ thống đangười dùng „ Thựchiệnchiasẻ file thông qua lược đồ bảovệ „ Trên các hệ thống phân tán, các file có thểđược chia sẻ qua mạng „ Hệ thống file mạng (NFS) là phương pháp chia sẻ file phổ biến 2008-05-01 Nguyên lý Hệ điềuhành 128
  128. Chia sẻ file – đangười dùng „ User IDs nhậndiệnngười dùng, cho phép cấpquyềnvàbảovệ file cấpngười dùng. „ Group IDs xác định nhóm người dùng, cấp quyềntruynhập theo nhóm. 2008-05-01 Nguyên lý Hệ điềuhành 129
  129. Chia sẻ file – Các hệ thống file từ xa „ Thông qua mạng để truy cậphệ thống file giữacáchệ thống ‰ Truy cậpthủ công thông qua các chương trình như FTP ‰ Truy nhậptựđộng thông qua hệ thống file chia sẻ ‰ Truy nhập bán tựđộng thông qua world wide web „ Mô hình client-server cho phép khách gắncáchệ thống file củaservers ‰ Server có thể phụcvụ nhiều clients ‰ Việcnhậndạng người dùng trên máy client thường không bảomậthoặc phứctạp ‰ NFS là giao thứcchiasẻ file client-server chuẩncủa UNIX ‰ CIFS là giao thứcchuẩncủa Windows. ‰ Các lờigọi file chuẩncủahệđiều hành đượcchuyển thành các lờigọifile từ xa. „ Các hệ thống thông tin phân tán (các dịch vụđịnh dạng phân tán) như LDAP, DNS, NIS, Active Directory thiếtlậptruycậphợpnhất đến thông tin chia sẻ từ xa. 2008-05-01 Nguyên lý Hệ điềuhành 130
  130. Chia sẻ file – Các mode thấtbại „ Các hệ thống file từ xa có thêm các mode thấtbại, do mạng, do server „ Khôi phụctừ thấtbạicần thông tin trạng thái của mỗiyêucầutừ xa. „ Các giao thức không hướng kếtnốinhư NFS trong mỗiyêucầu cho phép khôi phụcdễ dàng hơn nhưng ít bảomậthơn. 2008-05-01 Nguyên lý Hệ điềuhành 131
  131. Chia sẻ file – Tính thống nhấtvề mặtngữ nghĩa „ Tính nhấtquánvề ngữ nghĩa xác định cách thức cho phép nhiềungười dùng truy cập vào file cùng lúc. ‰ Tương tự cách đồng bộ tiếntrìnhcộng tác „ Hệ thống file Andrew (AFS) triểnkhaingữ cảnh chia sẻ file từ xa ‰ Hệ thống file Unix (UFS) thiếtlập: „ Việcghilênmột file mở có thể thấybởinhững người dùng khác ngay lậptức „ Con trỏđến file chia sẻ cho phép nhiềungười dùng truy cập đến file đồng thời. ‰ AFS có các ngữ cảnh sessions „ Việccậpnhật lên file chỉ thấy được trong những sessions sau khi file đã đóng 2008-05-01 Nguyên lý Hệ điềuhành 132
  132. 3.6. Bảovệ „ Ngườitạo/sở hữuphảicókhả năng điềukhiển ‰ Xác định ai có thể làm gì trên file „ Các kiểutruynhập ‰ Read ‰ Write ‰ Execute ‰ Append ‰ Delete ‰ List 2008-05-01 Nguyên lý Hệ điềuhành 133
  133. Nhóm và quyềntruynhập „ Các mode truy nhập: read, write, execute „ Ba lớpngười dùng RWX a) owner access 7 ⇒ 1 1 1 RWX b) group access 6 ⇒ 1 1 0 RWX c) public access 1 ⇒ 0 0 1 „ Tạomột nhóm G (tên duy nhất), và thêm người dùng vào nhóm đó. „ Vớimột file (vd: game) hay thư mục con, định ngh ĩamột quyềntruynhập xác định owner group public chmod 761 game 2008-05-01 Nguyên lý Hệ điềuhành 134
  134. Quản lý quyềntruynhập trong XP 2008-05-01 Nguyên lý Hệ điềuhành 135
  135. Liệtkêthư mục trong Unix 2008-05-01 Nguyên lý Hệ điềuhành 136
  136. 4. Cài đặthệ thống file 1. Cấutrúcvàcàiđặthệ thống file 2. Cài đặtthư mục 3. Các ph ương pháp phân phối 4. Qu ản lý không gian rỗ i 5. Hi ệuquả , hi ệusu ất 6. Khôi phục 2008-05-01 Nguyên lý Hệ điềuhành 137
  137. 4.1. Cấutrúcvàcàiđặthệ thống file „ Cấu trúc file ‰ Đơnvị lưutrữ mứclogic ‰ Tập các thông tin có liên quan đếnnhau „ Hệ thống file đượclưutrênthiếtbị lưutrữ thứ cấp (các đĩatừ) „ Hệ thống file đượctổ chứcthànhcáctầng „ Khối điềukhiển file –cấutrúclưutrữ chứa thông tin về một file 2008-05-01 Nguyên lý Hệ điềuhành 138
  138. Hệ thống file phân tầng 2008-05-01 Nguyên lý Hệ điềuhành 139
  139. Mộtkhối điều khiển file điểnhình 2008-05-01 Nguyên lý Hệ điềuhành 140
  140. Các cấutrúchệ thống file trong bộ nhớ „ Các cấu trúc file hệ thống cầnthiếtvàđược cung cấpbởihầuhếtcáchệđiều hành. „ Hình 12-3(a) mô tả quá trình mở một file. „ Hình 12-3(b) mô tả quá trình đọcmột file 2008-05-01 Nguyên lý Hệ điềuhành 141
  141. Các cấutrúchệ thống file trong bộ nhớ 2008-05-01 Nguyên lý Hệ điềuhành 142
  142. Các hệ thống file ảo „ Các hệ thống file ảo(VFS) cungcấpmộtcáchthức hướng đốitwongjđể cài đặthệ thống file „ VFS cho phép thiếtlậpgiaodiệnlờigọihệ thống (API) chung cho các loạihệ thống file khác nhau „ API là giao diện VFS thay vì giao diệncủabấtkì mộthệ thống file cụ thể nào 2008-05-01 Nguyên lý Hệ điềuhành 143
  143. Hệ thống file ảo 2008-05-01 Nguyên lý Hệ điềuhành 144
  144. 4.2. Cài đặtthư mục „ Danh sách liên kết chứa tên file và con trỏđến các file ‰ Đơngiản ‰ Tốnkémthờigian „ Bảng băm. ‰ Giảmthời gian tìm kiếmthư mục ‰ Va chạm – tình huống xảy ra khi hai tên file được ánh xạ vào cùng một địa điểm ‰ Kích cỡ cốđịnh 2008-05-01 Nguyên lý Hệ điềuhành 145
  145. 4.3. Các phương pháp phân phối „ Cách thức phân phốicáckhối đĩa cho các file: ‰ Phân phối liên tục ‰ Phân phối liên kết ‰ Phân phốichỉ số 2008-05-01 Nguyên lý Hệ điềuhành 146
  146. Phân phối liên tục „ Mỗifile lưutrongmộttậpcáckhốiliêntụctrênđĩa „ Đơngiản–chỉ cần điểmbắt đầu (block #) và kích cỡ (số các blocks) „ Truy nhậpngẫunhiên „ Không tậndụng không gian tối ưu „ Các file không thể thay đổikíchcỡ 2008-05-01 Nguyên lý Hệ điềuhành 147
  147. Phân phối liên tục (tt) „ Ánh xạ từ không gian logic sang không gian vậtlý Q LA/512 R Khốicầntruycập= Q + địachỉ bắt đầu Gia số trong khối= R 2008-05-01 Nguyên lý Hệ điềuhành 148
  148. Phân phối không gian đĩaliêntục 2008-05-01 Nguyên lý Hệ điềuhành 149
  149. Các hệ mở rộng dựa trên phân phối liên tụ c „ Nhiềuh ệ thống file mới (ví dụ: Veritas File System) sử dụng mộtlược đồ phân phốiliêntụccósửa đổi „ Các hệ thống file mở rộng phân phốikhối đĩa trong các extents „ Một extent là mộttậpcáckhối đĩa liên tục ‰ Extents được phân phốichomột file ‰ Mộtfile cóthể chứamột hay nhiều extent. 2008-05-01 Nguyên lý Hệ điềuhành 150
  150. Phân phối liên kết „ Một file có thể là một danh sách khối đĩa: các khối đĩacóthể nằmrảirác. Khối= Con trỏ 2008-05-01 Nguyên lý Hệ điềuhành 151
  151. Phân phối liên kết (tt) „ Đơngiản–chỉ cần địachỉ bắt đầu „ Hệ thống quản lý không gian rỗi– Không lãng phí tài nguyên „ Không truy nhậpngẫu nhiên Q „ Ánh xạ LA/511 R Khốisắp đượctruynhậptạivị tri thứ Qth trong danh sách liên kết các blocks biểudiễn file. Gia số trong blocks= R + 1 Bảng phân phối file ( bảng FAT) – phân phối không gian đĩa trong MS-DOS và OS-2 2008-05-01 Nguyên lý Hệ điềuhành 152
  152. Phân phối liên kết 2008-05-01 Nguyên lý Hệ điềuhành 153
  153. Bảng phân phối file 2008-05-01 Nguyên lý Hệ điềuhành 154
  154. Phân phốichỉ số „ Khối index: chứa toàn bộ con trỏđến các khối đĩa . Bảng chỉ số 2008-05-01 Nguyên lý Hệ điềuhành 155
  155. Ví dụ về phân phốichỉ số 2008-05-01 Nguyên lý Hệ điềuhành 156
  156. Phân phốichỉ số (tt) „ Cầnbảng chỉ „ Truy cậpngẫu nhiên „ Phân phối động mà không sinh ra phân mảnh ngoài (chỉ tốn không gian cho bảng index) „ Ánh xạ từ không gian logic sang không gian vật lý trong một file kích cỡ tối đa là 256K từ và kích cỡ khối là 512 từ chúng ta chỉ cầnmộtkhốicho bảng index Q Q = chỉ số trong bảng index LA/512 R = chỉ số trong khối R 2008-05-01 Nguyên lý Hệ điềuhành 157
  157. Phân phối đánh chỉ số – Ánh xạ (tt) „ Ánh xạ từ không gian logic sang không gian vậtlý trong mộtfile độ dài không giớihạn (kích cỡ khốilà 512 từ). „ Lược đồ liên kết–Liênkếtcáckhối trong bảng chỉ số (không giớihạnkíchcỡ). Q1 LA / (512 x 511) R1 Q1 = khốicủabảng chỉ số R1 đượcsử dụng như sau: Q2 R1 / 512 R2 Q2 = gia số trong khốichứabả ng chỉ số R2 gia số trong khối file: 2008-05-01 Nguyên lý Hệ điềuhành 158
  158. Phân phối đánh chỉ số - Ánh xạ (tt) „ Hai mứcchỉ số (kích cỡ file tối đalà 5123) Q1 LA / (512 x 512) R1 Q1 = Gia số trong bảng file mức ngoài R1 đượcsử dụng như sau: Q2 R1 / 512 R2 Q2 = gia số trong khốicủabảng chỉ số mức trong R2 gia số trong khối file: 2008-05-01 Nguyên lý Hệ điềuhành 159
  159. Phân phối file chỉ số – Ánh xạ (tt) M outer-index index table file 2008-05-01 Nguyên lý Hệ điềuhành 160
  160. Lược đồ kếthợp: UNIX (4K bytes mỗikhối) 2008-05-01 Nguyên lý Hệ điềuhành 161
  161. 4.4. Quản lý không gian rỗi „ Vector bit (n khối 0 1 2 n-1 0 ⇒ block[i] free bit[i] = 1 ⇒ block[i] occupied 678 Tính toán số khối (s ố lượng bit mỗitừ) * (số lượng từ nhậngiátrị 0) + Gia số bit 1 đầ utiên 2008-05-01 Nguyên lý Hệ điềuhành 162
  162. Quản lý không gian rỗi (tt) „ Ánh xạ bit cần thêm không gian ‰ Ví dụ: kích cỡ khối= 212 bytes kích cỡđĩ a= 230 bytes (1 gigabyte) n = 230/2 12 = 218 bits (or 32K bytes) „ Dễ dàng truy nhập đế n file liên tục „ Danh sách liên kết (danh sách liên kếtrỗi) ‰ Khó có được không gian liên tục ‰ Không lãng phí không gian 2008-05-01 Nguyên lý Hệ điềuhành 163
  163. Quản lý không gian rỗi (tt) „ Cầnphảibảovệ: ‰ Con trỏđếndanhsáchrỗi ‰ Ánh xạ bit „ Phải đượcgiữ trên đĩa „ Bảnsaotrongđĩavàtrongbộ nhớ có thể khác nhau „ Không cho phép khối[i] ở trong trạng thái mà bit[i] = 1 trong bộ nhớ và bit[i] = 0 trên đĩa ‰ Giải pháp: „ Thiếtlậpbit[i] = 1 trong đĩa „ Phân phốikhối[i] „ Thiếtlậpbit[i] = 1 trong bộ nhớ 2008-05-01 Nguyên lý Hệ điềuhành 164
  164. Danh sách liên kết không gian rỗi trên đĩa 2008-05-01 Nguyên lý Hệ điềuhành 165
  165. Hiệunăng „ Hiệuquả phụ thuộc vào: ‰ Các thuật toán phân phối đĩavàthư mục ‰ Các kiểudữ liệu đượcgiữ trong đầuvàothư mục chứa file „ Năng suất ‰ Cache đĩa–lưulạimộtphần đĩathường xuyên được truy nhập ‰ Giải phóng sau- đọctrước–kĩ thuậttối ưutruynhập tuầntự ‰ Tăng năng suấtlàmviệcchoPC 2008-05-01 Nguyên lý Hệ điềuhành 166
  166. Cache trang „ Một cache trang lưulại các trang thay vì các khối đĩasửadụng bởicáckĩ thuậtbộ nhớ „ Ánh xạ bộ nhớ I/O sửadụng cache trang „ Các thao tác vào ra vớihệ thống file sử dụng page(disk) cache 2008-05-01 Nguyên lý Hệ điềuhành 167
  167. I/O mà không có mộttổ chức cache hợpnhất 2008-05-01 Nguyên lý Hệ điềuhành 168
  168. Sửadụng cache bộđệmhợpnhất „ Mộtcache bộđệmhợpnhất: sử dụng không gian cache page để ‰ cache cả các trang ánh xạ bộ nhớ ‰ vào/ra các hệ thống file thông thường 2008-05-01 Nguyên lý Hệ điềuhành 169
  169. I/O sử dụng cache bộđệmhợpnhất 2008-05-01 Nguyên lý Hệ điềuhành 170
  170. Khôi phục „ Kiểm tra tính nhất quán – so sánh dữ liệu trong cấutrúc thư mục và so sánh vớikhối đĩa, cố gắng giảiquyếttính không nhất quán „ Sử dụng các chương trình hệ thống để back up dữ liệu từđĩa sang các thiếtbị lưutrữ khác (floppy disk, magnetic tape, other magnetic disk, optical) „ Khôi phụcfile hay thư mụcbị mấtbằng cách khôi phục lại backup 2008-05-01 Nguyên lý Hệ điềuhành 171