›
›

Bài giảng Cấp hệ điều hành

pdf 29 trang phuongnguyen 50
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấp hệ điều hà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:

  • pdfbai_giang_cap_he_dieu_hanh.pdf

Nội dung text: Bài giảng Cấp hệ điều hành

  1. Cấp hệ điều hành Mục tiêu: - Tìm hiểu kỹ thuật bộ nhớ ảo (Virtual Memory) - Các chỉ thị I/O ảo - Kỹ thuật xử lý tiến trình song song
  2. Cấp hệ điều hành Cấu trúc chƣơng trình Cấu trúc Overlay Trong cấu trúc Overlay, các module chƣơng trình sau khi biên dịch đƣợc chia thành các mức: Mức 0: mức chứa module gốc dùng để nạp chƣơng trình Mức 1: chứa các module đƣợc gọi bởi mức 0 Mức 2: chứa các module đƣợc gọi bởi mức 1 . Mức i: chứa các module đƣợc gọi bởi mức i-1 Bộ nhớ dành cho chƣơng trình cũng đƣợc chia thành các mức tƣơng ứng với các mức chƣơng trình. Kích thƣớc mỗi mức trong bộ nhớ bằng kích thƣớc module lớn nhất của mức chƣơng trình tƣơng ứng. CPU M0 Mức 0: 80Kb (80Kb) M M Mức 1: 90Kb 1 2 (50Kb) (90Kb) Mức 2: 100Kb M3 M4 M5 (50Kb) (100Kb) (70Kb)
  3. Cấp hệ điều hành Cấu trúc chƣơng trình Cấu trúc Overlay * Ƣu điểm: - Cấu trúc Overlay cĩ tính chất định vị động cho phép sử dụng bộ nhớ nhiều hơn phần bộ nhớ mà hệ thống dành cho chƣơng trình. Cấu trúc chƣơng trình mang tính chất tĩnh, khơng thay đổi trong tất cả các lần thực hiện chƣơng trình. - So với cấu trúc động, cấu trúc Overlay địi hỏi cung cấp thơng tin đơn giản, khơng gắn cấu trúc vào chƣơng trình nguồn - Với sơ đồ Overlay tốt và các module độ dài khơng quá lớn thì hiệu quả khơng kém so với cấu trúc động * Nhƣợc điểm: hiệu qủa tiết kiệm bộ nhớ phụ thuộc cách tổ chức, bố trí các module chƣơng trình
  4. Cấp hệ điều hành Bộ nhớ ảo Khó khăn: - Bộ nhớ có dung lượng nhỏ và giá thành rất cao - Lập trình viên phải mất nhiều thời gian để xử lý kích thước chương trình - Khó sử dụng các giải thuật tốt đòi hỏi không gian bộ nhớ lớn Giải pháp truyền thống: - Chia chương trình thành các mảng nhỏ (overlay) có thể đặt vừa bộ nhớ - Chương trình thực thi lần lượt các overlay Nhược điểm: Người lập trình tự thao tác bằng tay các công việc: - Tách chương trình - Quyết định vị trí cất overlay trong bộ nhớ phụ - Sắp xếp chuyển đổi overlay giữa bộ nhớ chính và phụ Khắc phục: Phương pháp tự động hóa toàn bộ quá trình overlay  Phương pháp bộ nhớ ảo
  5. Cấp hệ điều hành Bộ nhớ ảo * Kỹ thuật phân trang - Tách riêng không gian địa chỉ và các vị trí ô nhớ - Ví dụ: máy tính với trường địa chỉ 16 bit trong các chỉ thị và 4096 từ nhớ Chương trình máy tính địa chỉ hóa 216 = 65536 từ nhớ 2. Các từ nhớ được đặt từ 4096 đến 1. Nội dung bộ nhớ chính được cất vào 8191 64K bộ nhớ phụ không gian địa chỉ 4K Địa chỉ 0 bộ nhớ chính 4096 0 8191 4095 12287 3. Các từ nhớ từ 4096 đến 8191 nạp vào bộ nhớ chính 4. Aùnh xạ địa chỉ từ 4096 đến Aùnh xạ địa chỉ từ không gian 8191 lên các vị trí nhớ từ 0 đến địa chỉ lên bộ nhớ chính 4095 65535
  6. Cấp hệ điều hành Bộ nhớ ảo * Kỹ thuật phân trang - Yêu cầu: Bộ nhớ phụ có thể chứa được toàn bộ chương trình - Khái niệm: + Bản sao chương trình trong bộ nhớ phụ là bản gốc + Các mảng chương trình mang vào bộ nhớ chính ỡ những thời điểm khác nhau là bản sao - Thiết kế: + Không gian địa chỉ ảo tách thành nhiều trang kích thước bằng nhau và luôn là lũy thừa của 2 + Không gian địa chỉ vật lý cũng tách thành từng mảng có kích thước bằng kích thước các trang và cất vào khung trang
  7. Cấp hệ điều hành Bộ nhớ ảo * Kỹ thuật phân trang 64K 32K Ví dụ: không gian không gian địa chỉ ảo vật lý 0 0 Page 0 0-4095 4K Page 0 0-4095 4K 4096 4096 Page 1 4096-8191 Page 1 4096-8191 8192 8192 Page 2 8192-12287 Page 2 8192-12287 12288 12288 Page 3 12288-16383 Page 3 12288-16383 16384 16384 Page 4 Page 4 20480 20480 Page 5 Page 5 24576 24576 Page 6 Page 6 24576-28671 28672 28672 Page 7 Page 7 28672-32767 32768 Page 8 36864 Page 9 40960 Page 10 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 45056 Page 11 49152 Page 12 12 bit 53248 4 bit Page 13 Sô trang Địa chỉ chọn trên 57344 ảo = 3 trang ảo = 22 Page 14 57344-61139 (12310) 61140 Page 15 61140-65536
  8. Cấp hệ điều hành Bộ nhớ ảo * Kỹ thuật phân đoạn + Kỹ thuật phân trang: Nếu kích thước chương trình/dữ liệu không bằng đúng một trang Khoảng trống không dùng đến Hiện tượng phân mảnh Hao phí bộ nhớ + Kỹ thuật phân đoạn: - Thiết kế: * Tạo các không gian địa chỉ độc lập (gọi là segment) * Mỗi segment có chiều dài khác nhau và có thể thay đổi theo thời gian thực * Để xác định địa chỉ trong bộ nhớ phân đoạn, chương trình cung cấp địa chỉ có 2 phần: số segment và địa chỉ trong segment - Ưu điểm: * Đơn giản hóa việc quản lý cấu trúc dữ liệu * Dễ dàng dùng chung dữ liệu cho các chương trình * Tiết kiệm bộ nhớ
  9. Cấp hệ điều hành Bộ nhớ ảo * Kỹ thuật phân đoạn Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 1 (8K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K) (3K) (3K) (3K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 3 (8K) Segment 3 (8K) Segment 3 (8K) Segment 6 (4K) (4K) Segment 4 (7K) Segment 4 (7K) Segment 5 (4K) Segment 5 (4K) (3K) (3K) - Nhược điểm: Bộ nhớ được chia, một số chứa segment và một số chứa lỗ trống Hiện tượng bàn cờ lãng phí bộ nhớ
  10. Cấp hệ điều hành Bộ nhớ ảo * Kỹ thuật phân đoạn: khắc phục hiện tượng bàn cờ Phương pháp 1: Mỗi lần xuất hiện lỗ trống, di chuyển segment về vị trí 0 của bộ nhớ Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 1 (8K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K) (3K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 3 (8K) Segment 6 (4K) Segment 6 (4K) Segment 3 (8K) Segment 3 (8K) (4K) Segment 4 (7K) Segment 4 (7K) Segment 4 (7K) Segment 4 (7K) Segment 4 (7K) (7K) (3K) (3K) Tốn nhiều thời gian để di chuyển
  11. Cấp hệ điều hành Bộ nhớ ảo * Kỹ thuật phân đoạn: khắc phục hiện tượng bàn cờ Phương pháp 2 (Best Fit): Chọn phần trống vừa khít nhất với segment cần đưa vào Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 1 (8K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K) (3K) (3K) 3K Segment 8 (3K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 8 (3K) Segment 3 (8K) Segment 3 (8K) Segment 6 (4K) Segment 6 (4K) (4K) 4K (4K) Segment 4 (7K) Segment 4 (7K) Segment 4 (7K) Segment 4 (7K)
  12. Cấp hệ điều hành Bộ nhớ ảo * Kỹ thuật phân đoạn: khắc phục hiện tượng bàn cờ Phương pháp 3 (First Fit): Quét vòng tròn danh sách các phần trống và chọn phần trống đầu tiên đủ lớn vừa với segment cần đưa vào Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 0 (4K) Segment 1 (8K) Segment 7 (5K) Segment 7 (5K) Segment 7 (5K) (3K) (3K) 1 Segment 8 (3K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 2 (5K) Segment 8 (3K) Segment 3 (8K) Segment 3 (8K) Segment 6 (5K) Segment 6 (4K) (4K) (3K) 2 Segment 4 (7K) Segment 4 (7K) Segment 4 (7K) Segment 4 (7K)
  13. Cấp hệ điều hành Bộ nhớ ảo SƠ ĐỒ KẾT HỢP PHÂN TRANG VÀ PHÂN ĐOẠN * Vì sao cần kết hợp?: Sơ đồ phân trang đảm bảo hiệu quả sử dụng bộ nhớ mà khơng phụ thuộc vào cấu trúc chƣơng trình của ngƣời sử dụng, điều khiển trang thuận tiện, đơn giản. Tuy nhiên khi chƣơng trình cĩ kích thƣớc lớn thì kích thƣớc bảng PCB cũng lớn theo lãng phí bộ nhớ. Nếu kích thƣớc trang quá nhỏ kích thƣớc PCb lớn tăng khả năng nạp đi nạp lại trang giảm hiệu quả sử dụng bộ nhớ. Sơ đồ phân đoạn linh hoạt hơn về độ dài các đoạn nhƣng vì độ dài các đoạn khác nhau phức tạp trong vấn đề thực hiện và cấp phát bộ nhớ Để phát huy ƣu điểm và hạn chế nhƣợc điểm của các sơ đồ trên, ngƣời ta thƣờng sử dụng sơ đồ kết hợp phân trang và phân đoạn
  14. Cấp hệ điều hành Bộ nhớ ảo SƠ ĐỒ KẾT HỢP PHÂN TRANG VÀ PHÂN ĐOẠN Trong sơ đồ này, chƣơng trình đƣợc biên dịch theo sơ đồ phân đoạn và cĩ một bảng quản lý SCB. Mỗi đoạn chƣơng trình lại đƣợc biên tập theo sơ đồ phân trang và tạo ra từng bảng PCB riêng cho mỗi đoạn. Khi chƣơng trình đƣợc nạp vào hệ thống, hệ điều hành sẽ cấp phát cho chƣơng trình các trang cần thiết để chứa đủ các đoạn chƣơng trình
  15. Cấp hệ điều hành Bộ nhớ ảo SƠ ĐỒ KẾT HỢP PHÂN TRANG VÀ PHÂN ĐOẠN Gọi trƣờng địa chỉ A của phần tử thứ I trong SCB với SCB là nơi chứa bảng quản lý trang thứ I (PCBi) cĩ trƣờng độ dài L chứa độ dài của PCBi Khi thực hiện, bảng PCB đƣợc nạp vào bộ nhớ và địa chỉ đầu của nĩ đƣợc ghi vào thanh ghi quản lý đoạn Rs. Địa chỉ truy nhập dữ liệu đƣợc biểu diễn bởi bộ ba (s,p,d), trong đĩ: - s: số hiệu đoạn cần truy nhập trong SCB - p: số hiệu trang cần truy nhập trong PCB - d: địa chỉ tƣơng đối tính từ đầu trang
  16. Cấp hệ điều hành Bộ nhớ ảo SƠ ĐỒ KẾT HỢP PHÂN TRANG VÀ PHÂN ĐOẠN Để truy nhập tới dữ liệu, hệ thống trải qua 3 bƣớc: * Bƣớc 1: Lấy nội dung thanh ghi Rs cộng với s và truy nhập tới phần tử thứ s trong SCB * Bƣớc 2: Nếu D=0 thì thực hiện thủ tục nạp PCB tƣơng ứng vào bộ nhớ và cập nhật nội dung trƣờng A. Khi nạp xong PCB, hệ thống cộng nội dung trƣờng A với p để truy nhập tới phần tử thứ p trong PCB * Bƣớc 3: Khi tìm thấy phần tử p trong PCB, hệ thống sẽ ghép nội dung của Ap (tƣơng ứng phần tử thứ p) với d để tìm ra địa chỉ đọc/ghi dữ liệu
  17. Cấp hệ điều hành Các chỉ thị I/O ảo - Phương pháp tổ chức I/O ảo: là tưởng tượng dữ liệu đọc/ghi là một chuỗi các bản ghi logic - Một bản ghi logic là một đơn vị thông tin - Một chuỗi các bản ghi logic được gọi là tập tin - Các bản ghi trong tập tin không cần có độ dài bằng nhau - Các loại tập tin tuần tự: lưu trữ trên băng từ, đĩa từ mềm, CD, - Các loại chỉ thị I/O ảo: * Chỉ thị nhập ảo (đọc tập tin) * Chỉ thị xuất ảo (ghi tập tin) * Chỉ thị mở tập tin
  18. Cấp hệ điều hành Các chỉ thị I/O ảo Hướng di Các tập tin truy xuất tuần tự chuyển của 2. Chỉ thị READ tuần tập tin tự lấy bản ghi logic Chỉ thị nhập ảo cơ bản: 1 liên tiếp và ghi lên 2 vùng đệm Số các Chỉ thị phải xác định bản ghi 3 logic được thông tin: 4 - Tập tin được đọc Bộ nhớ chính - Địa chỉ bộ nhớ chính 5 lưu giữ bản ghi 6 Bản ghi 1. Cung cấp chỉ thị Vùng đệm 7 logic OPEN để mở tập trước khi sử dụng 8 9 10 11 12
  19. Cấp hệ điều hành Các chỉ thị I/O ảo Các tập tin truy xuất tuần tự Hướng di chuyển của tập tin Chỉ thị xuất ảo cơ bản: 1 2. Chỉ thị REWIND xác 2 Số các định vị trí bản ghi logic bản ghi 3 sẽ được ghi đầu tiên logic 4 Bộ nhớ chính 1. Cung cấp chỉ thị OPEN để mở tập 5 trước khi sử dụng 6 Bản ghi Vùng đệm 7 logic Xác định vị trí bản ghi 3. Chỉ thị WRITE tuần logic kế tiếp được ghi tự liên tiếp tạo các bản ghi liên tiếp lên tập tin Mất nhiều thời gian để đọc tuần tự từ đầu
  20. Cấp hệ điều hành Các chỉ thị I/O ảo Các tập tin truy xuất ngẫu nhiên Hướng di chuyển của tập tin Chỉ thị xuất ảo cơ bản: 1 Số các bản ghi 2 Chỉ thị phải xác định logic được thông tin: 3 4 - Tập tin được đọc 1. Cung cấp chỉ thị Bộ nhớ chính - Địa chỉ bộ nhớ chính OPEN để mở tập 5 lưu giữ bản ghi trước khi sử dụng 6 Bản ghi - Vị trí bản ghi logic Vùng đệm 7 logic trong tập tin 2. Chỉ thị ảo đọc bản ghi logic n 3. Chỉ thị WRITE ghi bản ghi lên tập tin
  21. Cấp hệ điều hành Tổ chức các chỉ thị I/O ảo Tập tin được cấp phát liên tiếp Đơn vị cấp phát là SECTOR: 1 sector dành cho tập tin và các sector khác trên cùng Hệ điều hành cần biết: track dành cho các tập tin - Vị trí bắt đầu của tập tin khác - Kích thước các bản ghi vật lý Tính toán vị trí các bản ghi logic Đơn vị cấp phát là TRACK: toàn bộ track dành cho tập tin, các track khác trên cùng cylinder dành cho các tập tin khác Đơn vị cấp phát là Track 0 CYLINDER: toàn bộ cylinder dành cho 1 tập tin Track 4 Hướng đọc đĩa
  22. Cấp hệ điều hành Tổ chức các chỉ thị I/O ảo Tập tin không được cấp phát liên tiếp Để định vị bản ghi: - Phương pháp 1: Sử dụng bảng chỉ số tập tin cho biết địa chỉ trên đĩa từng bản ghi 11 - Phương pháp 2: Tổ chức tập tin như một danh sách liên kết:Đơn vị cấp phát chứa địa chỉ đơn vị kế tiếp Track 0 Track 4 Hướng đọc đĩa
  23. Cấp hệ điều hành Tổ chức các chỉ thị I/O ảo Cấp phát không gian cho tập tin - Phương pháp 1: Sử dụng danh sách trống Số Track Sector sector trống 0 0 12 1 0 10 2 3 2 2 7 1 2 10 2 3 0 3 3 4 7 4 1 9 4 11 1 - Ưu điểm: dễ quản lý - Nhược điểm: Khó khăn khi có sự biến động
  24. Cấp hệ điều hành Tổ chức các chỉ thị I/O ảo Cấp phát không gian cho tập tin - Phương pháp 2: Sử dụng bản đồ Bit Sector Track 0 1 2 3 4 5 6 7 8 9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 2 1 1 1 0 0 1 1 0 1 1 0 0 3 0 0 0 1 0 0 0 0 0 0 1 0 4 1 0 0 0 0 0 0 0 0 0 1 0 - Ưu điểm: dễ quản lý, khi có biến động chỉ đơn giản là thay đổi 1 bit - Nhược điểm: Tìm một khối có kích thước cho trước sẽ khó khăn
  25. Cấp hệ điều hành Xử lý song song Tiến trình 3 đang chờ Tiến trình 3 CPU 3 Tiến trình 2 CPU 2 Tiến trình 1 CPU 1 CPU Time Time Tiến trình 1 đang chạy Xử lý song song với Xử lý song song với nhiều CPU một CPU
  26. Cấp hệ điều hành Xử lý song song Phƣơng pháp khĩa trong THUẬT TỐN DEKKER: Dùng thêm một biến khĩa TT để xác định độ ƣu tiên của các tiến trình khi cả hai tiến trình cùng muốn vào đoạn tới hạn (TT=1 hoặc TT=2) Tiến trình 1 Tiến trình 2 Repeat Repeat K1:=1; K2:=1; While K2=1 do While K1=1 do if TT=2 then if TT=1 then Begin Begin K1:=0; K2:=0; While TT=2 do Skip; While TT=1 do Skip; K1:=1; K2:=1; End; End; {Tiến trình 1 vào đoạn tới hạn} {Tiến trình 2 vào đoạn tới hạn} K1:=0;TT=2; K2:=0;TT=1; {Phần cịn lại của tiến trình 1} {Phần cịn lại của tiến trình 2} Until False; Until False;
  27. Cấp hệ điều hành Xử lý song song Phƣơng pháp khĩa trong Nhận xét: Thuật tốn Dekker giải quyết bài tốn đoạn tới hạn hợp lý trong mọi trƣờng hợp cho dù tốc độ thực hiện của các tiến trình khác nhau. Ƣu điểm: Phƣơng pháp khĩa trong khơng địi hỏi cơng cụ đặc biệt, do đĩ cĩ thể tổ chức bằng một ngơn ngữ bất kỳ và thực hiện trên mọi hệ thống. Nhƣợc điểm: - Độ phức tạp của thuật tốn sẽ tăng khi số tiến trình nhiều hoặc số lƣợng đoạn tới hạn trong các tiến trình lớn. - Các tiến trình phải chờ đợi trong trạng thái tích cực
  28. Cấp hệ điều hành Xử lý song song Phƣơng pháp đèn hiệu 1. Nguyên tắc chung: Đèn hiệu S là một biến nguyên mà chỉ cĩ hai phép xử lý WAIT và SIGNAL mới thay đổi đƣợc giá trị của nĩ. Định nghĩa phép WAIT(S): S:=S-1 Nếu S>=0 tiếp tục thực hiện tiến trình Nếu S<0 đƣa tiến trình vào hàng đợi Định nghĩa phép SIGNAL(S): S:=S+1 Nếu S<=0 đƣa tiến trình trong hàng đợi vào đoạn tới hạn Chú ý: + Phép WAIT và SIGNAL khơng bị phân chia trong tiến trình thực hiện. + Nếu ban đầu S=1 và cả hai tiến trình đều đƣa ra phép WAIT(S) thì chỉ cĩ một tiến trình đƣợc phép vào đoạn tới hạn, tiến trình cịn lại sẽ đƣợc đƣa vào hàng đợi.
  29. Cấp hệ điều hành Xử lý song song Phƣơng pháp đèn hiệu Trình bày thuật tốn (Bài tốn 2 tiến trình) Tiến trình 1 Tiến trình 2 Repeat Repeat WAIT(S); WAIT(S); {Tiến trình 1 vào đoạn tới hạn} {Tiến trình 2 vào đoạn tới hạn} SIGNAL(S); SIGNAL(S); {Phần cịn lại của tiến trình 1} {Phần cịn lại của tiến trình 2} Until False; Until False; * Ƣu điểm: Mỗi tiến trình chỉ cần kiểm tra quyền 1 lần * Nhƣợc điểm: Phép WAIT và SIGNAL phải tổ chức hàng đợi