Giáo trình Nguyên lý hệ điều hành - Chương 3: Điều khiển bộ nhớ

65 trang Gia Huy 16/05/2022 2590

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: Điều khiển bộ 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:

giao_trinh_nguyen_ly_he_dieu_hanh_chuong_3_dieu_khien_bo_nho.pdf

Nội dung text: Giáo trình Nguyên lý hệ điều hành - Chương 3: Điều khiển bộ nhớ

Nguyên lý hệ điều hành CHƯƠNG 3 : ĐIỀU KHIỂN BỘ NHỚ Bộ nhớ chính là thiết bị lưu trữ duy nhất thông qua đó CPU có thể trao đổi thông tin với môi trường ngoài, do vậy nhu cầu tổ chức, quản lý bộ nhớ là một trong những nhiệm vụ trọng tâm hàng đầu của hệ điều hành . Bộ nhớ chính được tổ chức như một mảng một chiều các từ nhớ (word), mỗi từ nhớ có một địa chỉ . Việc trao đổi thông tin với môi trường ngoài được thực hiện thông qua các thao tác đọc hoặc ghi dữ liệu vào một địa chỉ cụ thể nào đó trong bộ nhớ. Hầu hết các hệ điều hành hiện đại đều cho phép chế độ đa nhiệm nhằm nâng cao hiệu suất sử dụng CPU. Tuy nhiên kỹ thuật này lại làm nảy sinh nhu cầu chia sẻ bộ nhớ giữa các tiến trình khác nhau . Vấn đề nằm ở chỗ : « bộ nhớ thì hữu hạn và các yêu cầu bộ nhớ thì vô hạn ». 3.1 Tổ chức vùng nhớ Dung Tốc lượng độ nhỏ nhanh Regist er Cache SRAM 1 Cache 2 Main memory DRAM Dung Tốc Hình 3.1 lượng Disk độ lớn 3.2 Mục tiêu của việc quản lý vùng nhớ chậm Cấp phát vùng nhớ cho các tiến trình có yêu cầu và thu hồi vùng nhớ khi tiến trình thực hiện xong. Quản lý được vùng nhớ rỗi, vùng nhớ bận. - Tại một thời điểm có thể lưu giữ được nhiều tiến trình đồng thời. - Chuyển đổi giữa địa chỉ logic và địa chỉ vật lý (physic) - Chia sẻ thông tin: làm thế nào để cho phép hai tiến trình có thể chia sẻ thông tin trong bộ nhớ? - Ngăn chặn các tiến trình xâm phạm đến vùng nhớ được cấp phát cho tiến trình khác 3.3 Không gian địa chỉ và không gian vật lý 67
Nguyên lý hệ điều hành Một trong những hướng tiếp cận trung tâm nhằm tổ chức quản lý bộ nhớ một cách hiệu qủa là đưa ra khái niệm không gian địa chỉ được xây dựng trên không gian nhớ vật lý, việc tách rời hai không gian này giúp hệ điều hành dễ dàng xây dựng các cơ chế và chiến lược quản lý bộ nhớ hữu hiệu : Địa chỉ logic – còn gọi là địa chỉ ảo , là địa chỉ do bộ xử lý tạo ra. Địa chỉ vật lý - 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. Địa chỉ ảo và địa chỉ vật lý là như nhau trong phương thức kết buộc địa chỉ vào thời điểm biên dịch cũng như vào thời điểm nạp. Nhưng có sự khác biệt giữa địa chỉ ảo và địa chỉ vật lý trong phương thức kết buộc vào thời điểm xử lý. MMU (memory-management unit) là một cơ chế phần cứng được sử dụng để thực hiện chuyển đổi địa chỉ ảo thành địa chỉ vật lý vào thời điểm xử lý. Chương trình của người sử dụng chỉ thao tác trên các địa chỉ ảo, không bao giờ nhìn thấy các địa chỉ vật lý . Địa chỉ thật sự ứng với vị trí của dữ liệu trong bô nhớ chỉ được xác định khi thực hiện truy xuất đến dữ liệu. 3.4. Cấp phát liên tục Tiến trình được nạp vào một vùng nhớ liên tục đủ lớn để chứa toàn bộ tiến trình. Không cho phép chương trình khác sử dụng vùng nhớ dành cho chương trình 3.4.1 Hệ đơn chương Trong phương pháp này bộ nhớ được chia sẻ cho hệ điều hành và một tiến trình duy nhất của người sử dụng. Tại một thời điểm, một phần của bộ nhớ sẽ do hệ điều hành chiếm giữ, phần còn lại thuộc về tiến trình người dùng duy nhất trong hệ thống. Tiến trình này được toàn quyền sử dụng bộ nhớ dành cho nó. 68
Nguyên lý hệ điều hành Hình 3.2 Tổ chức bộ nhớ trong hệ thống đơn chương Để bảo vệ hệ điều hành khỏi sự xâm phạm tác động của chương trình người dung, sử dụng một thanh ghi giới hạn lưu địa chỉ cao nhất của vùng nhớ được cấp cho hệ điều hành. Tất cả các địa chỉ được tiến trình người dung truy xuất sẽ được so sánh với nội dung thanh ghi giới hạn, nếu địa chỉ này lớn hơn giới hạn cho phép thì là hợp lệ, ngược lại một ngắt sẽ được phát sinh để báo cho hệ thống về một truy xuất bất hợp lệ. Khi bộ nhớ được tổ chức theo cách thức này, chỉ có thể xử lý một tiến trình tại một thời điểm. Quan sát hoạt động của các tiến trình, có thể nhận thấy rất nhiều tiến trình trải qua phần lớn thời gian để chờ các thao tác nhập/xuất hoàn thành. Trong suốt thời gian này, CPU ở trạng thái rỗi. Trong trường hợp như thế, hệ thống đơn chương không cho phép sử dụng hiệu quả CPU. Ngoài ra, sự đơn chương không cho phép nhiều người sử dụng làm việc đồng thời theo cơ chế tương tác. Để nâng cao hiệu suất sử dụng CPU, cần cho phép chế độ đa chương mà trong đó các tiến trình chia sẻ CPU với nhau để hoạt động đồng hành. 3.4.2 Hệ thống đa chương với phân vùng cố định Một trong những phương pháp đơn giản nhất để cấp phát bộ nhớ là chia bộ nhớ thành những phân vùng có kích thước cố định. Các phân vùng khác nhau có thể có kích thước khác nhau hay bằng nhau. Mỗi phân vùng chỉ có thể chứa một tiến trình. Do đó, cấp độ đa chương được giới hạn bởi số lượng phân vùng. Trong phương pháp đa phân vùng, khi một phân vùng rảnh, một tiến trình được chọn từ hàng đợi nhập và được nạp vào phân vùng trống. Khi tiến trình kết thúc, phân vùng trở nên sẳn dùng cho một tiến trình khác. Có hai tiếp cận để tổ chức hàng đợi: • Sử dụng nhiều hàng đợi: mỗi phân vùng sẽ có một hàng đợi tương ứng. Khi một tiến trình mới được tạo lập sẽ được đưa vào hàng đợi của phân vùng có kích thước nhỏ nhất đủ lớn để chứa tiến trình. 69
Nguyên lý hệ điều hành Cách tổ chức này có khuyết điểm trong trường hợp các hàng đợi của một số phân vùng lớn thì trống trong khi các hàng đợi của các phân vùng nhỏ lại đầy, buộc các tiến trình trong những hàng đợi này phải chờ được cấp phát bộ nhớ, do vậy sử dụng không hiệu quả bộ nhớ. • Sử dụng một hàng đợi: tất cả các tiến trình được đặt trong hàng đợi duy nhất. Khi có một phân vùng trống, tiến trình đầu tiên trong hàng đợi có kích thước phù hợp sẽ được đặt vào phân vùng và cho xử lý. Hình 3.3 Cấp phát đa vùng với phân vùng cố định Trong trường hợp tiến trình đầu tiên có kích thước nhỏ trong khi phân vùng tự do là lớn sẽ dẫn tới lãng phí bộ nhớ. Giải pháp: Khi có một phân vùng rỗi thì tìm trên toàn bộ hàng đợi này tiến trình lớn nhất đặt vừa rong phân vùng này, nạp tiến trình vào bộ nhớ chính. Xuất hiện hiện tượng phân mảnh nội vi (internal fragmentation): do kích thước tiến trình được nạp nhỏ hơn kích thước của phân vùng chứa tiến trình, phần bộ nhớ không được sử dụng đến trong phân vùng này gọi là phân mảnh nội vi. Nhận xét: -Mức độ đa chương của hệ thống bị giới hạn bởi số lượng phân vùng. - Sử dụng bộ nhớ không hiệu quả: Tổng bộ nhớ nhỏ tự do, rời rạc còn lớn nhưng không thể sử dụng để nạp tiến trình khác. 70
Nguyên lý hệ điều hành Tiến trình có kích thước lớn hơn phân vùng lớn nhất sẽ không bao giờ được thực hiện. - Ưu điểm: đơn giản, dễ tổ chức bảo vệ, giảm thời gian tìm kiếm. 3.4.3 Hệ thống đa chương với phân vùng động Hệ điều hành giữ một bảng hiển thị những phần nào của bộ nhớ là rỗi và phần nào đang bận. Ban đầu, tất cả bộ nhớ là sẵn dùng cho tiến trình người dùng, và được xem như một khối lớn bộ nhớ sẵn dùng. Khi một tiến trình đến và cần bộ nhớ, hệ điều hành tìm kiếm một vùng trống đủ lớn cho tiến trình này. Nếu tìm thấy, hệ điều hành sẽ cấp phát cho tiến trình phần bộ nhớvừa đúng với kích thước của tiến trình, phần bộ nhớ còn lại dành cho các tiến trình khác. Hình 3.4 Cấp phát đa vùng với phân vùng động Thông thường, một tập hợp các vùng trống có kích thước khác nhau được phân tán khắp bộ nhớ tại bất cứ thời điểm được cho. Khi một tiến trình đến và yêu cầu bộ nhớ, hệ thống tìm tập hợp này một vùng trống đủ lớn cho tiến trình này. Nếu vùng trống quá lớn, nó được chia làm hai: một phần được cấp cho tiến trình đến; phần còn lại được trả về tập hợp các vùng trống. Nếu vùng trống mới nằm kề với các vùng trống khác, các vùng trống nằm kề này được gom lại để tạo thành một vùng trống lớn hơn. Xuất hiện hiện tượng phân mảnh ngoại vi( external fragmentation ) : khi các tiến trình lần lượt vào và ra khỏi hệ thống, dần dần xuất hiện các khe hở giữa các tiến trình. Đây là các khe hở được tạo ra do kích thước của tiến trình mới được nạp nhỏ hơn kích thước vùng nhớ mới được giải phóng bởi một tiến trình đã kết thúc và ra khỏi hệ thống. , không gian bộ nhớ trống bị phân rã thành những mảnh nhớ nhỏ. Hiện tượng này có thể dẫn đến tình huống tổng vùng nhớ trống đủ để thoả mãn yêu cầu, nhưng các vùng nhớ này lại không liên tục ! Người ta có thể áp dụng kỹ thuật « dồn bộ nhớ » (memory compaction ) để kết hợp các mảnh bộ nhớ nhỏ rời rạc thành 71
Nguyên lý hệ điều hành một vùng nhớ lớn liên tục. Tuy nhiên, kỹ thuật này đòi hỏi nhiều thời gian xử lý, ngoài ra, sự kết buộc địa chỉ phải thực hiện vào thời điểm xử lý, vì các tiến trình có thể bị di chuyển trong quá trình dồn bộ nhớ. Thuật toán đơn giản là dịch chuyển các tiến trình về phía đầu của bộ nhớ. Ví dụ: 0 0 0 0 300K HDH 300K HDH 300K HDH 300K HDH 500K P1 500K P1 500K P1 500K P1 P2 P2 P2 P2 600K P2 600K P2 600K P2 600K P2 P3 P4 800 1000K 1000K P3 K P4P3 P3 P3 P3 1200K P3 1200K 1200K 1500K P4 P4 P4 1500K P4 P4 P4 1900K 1900K 1900K 2100K 2100K 2100K 2100K P3 Hình 3.5 Cấp phát gốc Dịch chuyển 600K Dịch chuyển 400K Dịch chuyển 200K Vấn đề cấp phát động Lựa chọn vùng nhớ tự do trong danh sách các vùng nhớ tự do để cấp phát cho tiến trình. Có 3 chiến lược phổ biến nhất được dùng: • First-fit: cấp phát vùng nhớ tự do đầu tiên đủ lớn. Tìm kiếm có thể bắt đầu tại đầu từ danh sách tập hợp các vùng trống hay tại điểm kết thúc của tìm kiếm first-fit trước đó. Chúng ta dừng tìm kiếm ngay khi chúng ta tìm thấy một vùng trống đủ lớn. • Best-fit: cấp phát vùng nhớ tự do nhỏ nhất đủ lớn. Chúng ta phải tìm toàn bộ danh sách, trừ khi danh sách được xếp thứ tự theo kích thước. Worst-fit: cấp phát vùng nhớ tự do lớn nhất đủ lớn để chứa tiến trình. Chúng ta phải tìm toàn bộ danh sách trừ khi nó được xếp theo thứ tự kích thước. Quản lý các khối rỗi bận - Quản lý bằng bản đồ bit: Bộ nhớ được chia thành các đơn vị cấp phát, mỗi đơn vị được ánh xạ tới một bit trong bản đồ bit. Giá trị bit này xác định trạng thái của đơn vị bộ nhớ đó: 0 đang tự do, 1 đã được cấp phát. Khi cần nạp một tiến trình có kích thước k đơn vị, hệ thống sẽ tìm trong bản đồ bit một dãy k bit có giá trị 0. Kích thước của đơn vị cấp phát là vấn đề lớn trong thiết kế. Nếu kích thước đơn vị cấp phát nhỏ sẽ làm tăng kích thước của bản đồ bit. Ngược lại, nếu kích thước đơn vị 72
Nguyên lý hệ điều hành cấp phát lớn có thể gây hao phí cho đơn vị cấp phát sau cùng. Đây là giải pháp đơn giản nhưng thực hiện chậm nên ít được dùng. Hình 3.6 Quản lý bộ nhớ bằng bản đồ bit - Quản lý bằng danh sách liên kết: Dùng một danh sách liên kết để quản lý các phân đoạn bộ nhớ đã cấp phát và phân đoạn tự do.Danh sách liên kết gồm nhiều nút liên tiếp. Mỗi nút gồm 1 bit đầu để xác định phân đoạn đó là vùng trống (H) hay một tiến trình (P), sau đó là 3 từ để chỉ địa chỉ bắt đầu, chiều dài và chỉ điểm tới mục kế tiếp. Việc sắp xếp các phân đoạn theo địa chỉ hay theo kích thước tuỳ thuộc vào giải thuật quản lý bộ nhớ. Hình 3.7 Quản lý bộ nhớ bằng danh sách liên kết 3.5. Cấp phát không liên tục Cấp phát không liên tục là một chương trình có thể được phân chia thành mộ số đoạn, các đoạn này nằm ở các vùng nhớ rời rạc nhau, giữa các vùng nhớ này có thể có các vùng nhớ được phân phối cho chương trình khác. 3.5.1 Phân trang ( Paging) Ý tưởng: 73
Nguyên lý hệ điều hành Hình 3.8 Mô hình bộ nhớ phân trang Phân bộ nhớ vật lý thành các khối (block) có kích thước cố định và bằng nhau, gọi là khung trang (page frame). Không gian địa chỉ cũng được chia thành các khối có cùng kích thước với khung trang, và được gọi là trang (page). Khi cần nạp một tiến trình để xử lý, các trang của tiến trìnhsẽ được nạp vào những khung trang còn trống. Một tiến trình kích thước N trang sẽ yêu cầu N khung trang tự do. Cơ chế MMU trong kỹ thuật phân trang: Hình 3.9 Cơ chế phần cứng hỗ trợ phân trang Cơ chế phần cứng hỗ trợ thực hiện chuyển đổi địa chỉ trong cơ chế phân trang là bảng trang (pages table): Mỗi tiến trình có một bảng trang. Số phần tử của bảng trang=số trang trong không gian địa chỉ của tiến trình. 74
Nguyên lý hệ điều hành Mỗi phần tử trong bảng trang mô tả một trang cho biết địa chỉ bắt đầu của vị trí lưu trữ trang tương ứng trong bộ nhớ vật lý ( số hiệu khung trang trong bộ nhớ vật lý đang chứa trang ). Hình 3.10 Chuyển đổi địa chỉ: Địa chỉ logic Địa chỉ vật lý số hiệu trang (p): sử dụng như chỉ mục đến phần tử tương ứng trong bảng trang. địa chỉ tương đối trong trang (d): kết hợp với địa chỉ bắt đầu của trang để tạo ra địa chỉ vật lý mà trình quản lý bộ nhớ sử dụng. Số hiệu khung trang (f):địa chỉ bắt đầu của khung trang trong bộ nhớ vật lý. Kích thước của trang do phần cứng qui định. Để dễ phân tích địa chỉ ảo thành số hiệu trang và địa chỉ tương đối, kích thước của một trang thông thường là một lũy thừa của 2 (biến đổi trong phạm vi 512 bytes và 8192 bytes). Nếu kích thước của không gian địa chỉ là 2m và kích thước trang là 2 n, thì m-n bits cao của địa chỉ ảo sẽ biễu diễn số hiệu trang, và n bits thấp cho biết địa chỉ tương đối trong trang. Cài đặt bảng trang: - Với các bảng trang có kích thước nhỏ, trong trường hợp đơn giản nhất, bảng trang được cài đặt trongmột tập các thanh ghi 75
Nguyên lý hệ điều hành - Nếu bảng trang có kích thước lớn, nó phải được lưu trữ trong bộ nhớ chính, và sử dụng một thanh ghi để lưu địa chỉ bắt đầu lưu trữ bảng trang (PTBR). Theo cách tổ chức này, mỗi truy xuất đến dữ liệu hay chỉ thị đều đòi hỏi hai lần truy xuất bộ nhớ : một cho truy xuất đến bảng trang và một cho bản thân dữ liệu, do vậy truy cập chậm. Hình 3.11 Sử dụng thanh ghi nền trỏ đến bảng trang - Để nâng cao tốc độ truy xuất, sử dụng thêm một vùng nhớ đặc biệt , với tốc độ truy xuất nhanh và cho phép tìm kiếm song song, vùng nhớ cache nhỏ này thường được gọi là bộ nhớ kết hợp (translation look-aside buffer TLBs). Mỗi thanh ghi trong bộ nhớ kết hợp chứa số hiệu trang và số hiệu khung trang tương ứng, khi CPU phát sinh một địa chỉ logic, số hiệu trang của địa chỉ sẽ được so sánh cùng lúc với các số hiệu trang trong bộ nhớ kết hợp để tìm ra phần tử tương ứng. Nếu có trang tương ứng trong bộ nhớ kết hợp thì sẽ xác định ngay số hiệu khung trang tương ứng, nếu không mới cần thực hiện thao tác tìm kiếm trong bảng trang.Nhờ đặc tính này mà việc tìm kiếm trên bộ nhớ kết hợp được thực hiện rất nhanh, nhưng chi phí phần cứng lại cao. Trong kỹ thuật phân trang, TLBs được sử dụng để lưu trữ các trang bộ nhớ được truy cập gần hiện tại nhất. 76
Nguyên lý hệ điều hành Hình 3.12 Bảng trang với TLBs Tổ chức bảng trang: Hình 3.13 Bảng trang 2 cấp Mỗi hệ điều hành có một phương pháp riêng để tổ chức lưu trữ bảng trang. Đa số các hệ điều hành cấp cho mỗi tiến trình một bảng trang. Tuy nhiên phương pháp này không thể chấp nhận được nếu hệ điều hành cho phép quản lý một không gian địa chỉ có dung lượng quá (232, 264): trong các hệ thống như thế, bản thân bảng trang đòi hỏi một vùng nhớ qúa lớn! Thí dụ, xét một hệ thống với không gian địa chỉ luận lý 32 bit. Nếu kích thước 32 12 trang 4KB thì bảng trang có thể chứa tới 1 triệu mục từ (2 /2 ). Giả sử rằng mỗi mục từ chứa 4 bytes, mỗi tiến trình có thể cần tới 4MB không gian địa chỉ vật lý cho một bảng trang. Rõ ràng, chúng ta sẽ không muốn cấp phát bảng trang liên tiếp nhau. Một giải pháp đơn giản cho vấn đề này là chia bảng trang thành những phần nhỏ hơn. 77
Nguyên lý hệ điều hành Phân trang đa cấp: phân 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 Ví dụ trong bảng trang 2 cấp cho máy 32 bit với kích thước trang 4KB. Địa chỉ logic được chia thành số trang chứa 20 bit và độ dời trang chứa 12 bit. Vì chúng ta phân trang bảng trang, số trang được chia thành số trang 10 bit và độ dời trang 10-bit. Do đó, một địa chỉ logic như sau: Hình 3.14 Phân trang 3 cấp Không gian địa chỉ 64 bit, kích thước trang 4KB 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 phản ánh một khung trang trong bộ nhớ bao gồm địa chỉ logic của một trang đang được lưu trữ trong bộ nhớ vật lý tại khung trang này, cùng với thông tin về tiến trình đang được sỡ hữu trang. Mỗi địa chỉ ảo khi đó là một bộ ba Trong đó : pid là định danh của tiến trình p là số hiệu trang d là địa chỉ tương đối trong trang 78
Nguyên lý hệ điều hành Hình 3.15 Mỗi phần tử trong bảng trang nghịch đảo là một cặp . 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. Trong các trường hợp khác, xem như tham khảo bộ nhớ đã truy xuất một địa chỉ bất hợp lệ. Bảo vệ: Cơ chế bảo vệ trong hệ thống phân trang được thực hiện với các bit bảo vệ được gắn với mỗi khung trang. Thông thường, các bit này được lưu trong bảng trang , vì mỗi truy xuất đến bộ nhớ đều phải tham khảo đến bảng trang để phát sinh địa chỉ vật lý, khi đó, hệ thống có thể kiểm tra các thao tác truy xuất trên khung trang tương ứng có hợp lệ với thuộc tính bảo vệ của nó không. Ngoài ra, một bit phụ trội được thêm vào trong cấu trúc một phần tử của bảng trang : bit hợp lệ-bất hợp lệ (valid-invalid). Hợp lệ : trang tương ứng thuộc về không gian địa chỉ của tiến trình. Bất hợp lệ: trang tương ứng không nằm trong không gian địa chỉ của tiến trình, điều này có nghĩa tiến trình đã truy xuất đến một địa chỉ không được phép. Hình 3.16 Cấu trúc một phần tử trong bảng trang 79
Nguyên lý hệ điều hành Chia sẻ bộ nhớ trong cơ chế phân trang: Hình 3.17 Chia sẻ các trang trong hệ phân trang Một ưu điểm của cơ chế phân trang là cho phép chia sẻ các trang giữa các tiến trình.Trong trường hợp này, sự chia sẻ được thực hiện bằng cách ánh xạ nhiều địa chỉ logic vào một địa chỉ vật lý duy nhất. Có thể áp dụng kỹ thuật này để cho phép các tiến trình chia sẻ một vùng code chung: nếu có nhiều tiến trình của cùng một chương trình, chỉ cần lưu trữ một đoạn code của chương trình này trong bộ nhớ, các tiến trình sẽ có thể cùng truy xuất đến các trang chứa code chung này. Lưu ý để có thể chia sẻ một đoạn code, đoạn code này phải có thuộc tính cố định và không thay đổi trong quá trình xử lý. 80
Nguyên lý hệ điều hành Nhận xét Kỹ thuật phân trang loại bỏ được hiện tượng phân mảnh ngoại vi : mỗi khung trang đều có thể được cấp phát cho một tiến trình nào đó có yêu cầu. Tuy nhiên hiện tượng phân mảnh nội vi vẫn có thể xảy ra khi kích thước của tiến trình không đúng bằng bội số của kích thước một trang, khi đó, trang cuối cùng sẽ không được sử dụng hết. Một khiá cạnh tích cực rất quan trọng khác của kỹ thuật phân trang là sự phân biệt rạch ròi góc nhìn của người dùng và của bộ phận quản lý bộ nhớ vật lý: Góc nhìn của người sử dụng: một tiến trình của người dùng nhìn thấy bộ nhớ như là một không gian liên tục, đồng nhất và chỉ chứa duy nhất bản thân tiến trình này. Góc nhìn của bộ nhớ vật lý: một tiến trình của người sử dụng được lưu trữ phân tán khắp bộ nhớ vật lý, trong bộ nhớ vật lý đồng thời cũng chứa những tiến trình khác. Phần cứng đảm nhiệm việc chuyển đổi địa chỉ logic thành địa chỉ vật lý . Sự chuyển đổi này là trong suốt đối với người sử dụng. 3.5.2. Phân đoạn (Segmentation) Lưu ý rằng sự phân trang không phản ánh đúng cách thức người sử dụng cảm nhận về bộ nhớ. Người sử dụng nhìn thấy bộ nhớ như một tập các đối tượng của chương trình (segments, các thư viện ) và một tập các đối tượng dữ liệu (biến toàn cục, stack, vùng nhớ chia sẻ ). Vấn đề đặt ra là cần tìm một cách thức biễu diễn bộ nhớ sao cho có thể cung cấp cho người dùng một cách nhìn gần với quan điểm logic của họ hơn và đó là kỹ thuật phân đoạn Ý tưởng: quan niệm không gian địa chỉ là một tập các phân đoạn (segments) – các phân đoạn là những phần bộ nhớ kích thước khác nhau và có liên hệ logic với nhau. Mỗi phân đoạn có một tên gọi (số hiệu phân đoạn) và một độ dài. Người dùng sẽ thiết lập mỗi địa chỉ với hai giá trị : . 81
Nguyên lý hệ điều hành Hình 3.18 Mô hình phân đoạn bộ nhớ Cơ chế MMU trong kỹ thuật phân đoạn: Hình 3.19 Cơ chế phần cứng hổ trợ kĩ thuật phân đoạn Cần phải xây dựng một ánh xạ để chuyển đổi các địa chỉ 2 chiều được người dùng định nghĩa thành địa chỉ vật lý một chiều. Sự chuyển đổi này được thực hiện qua một bảng phân đoạn. Mỗi thành phần trong bảng phân đoạn bao gồm một thanh ghi nền và một thanh ghi giới hạn. Thanh ghi nền lưu trữ địa chỉ vật lý nơi bắt đầu phân đoạn trong bộ nhớ, trong khi thanh ghi giới hạn đặc tả chiều dài của phân đoạn. Chuyển đổi địa chỉ: Mỗi địa chỉ ảo là một bộ : số hiệu phân đoạn s : được sử dụng như chỉ mục đến bảng phân đoạn 82
Nguyên lý hệ điều hành địa chỉ tương đối d : có giá trị trong khoảng từ 0 đến giới hạn chiều dài của phân đoạn. Nếu địa chỉ tương đối hợp lệ, nó sẽ được cộng với giá trị chứa trong thanh ghi nền để phát sinh địa chỉ vật lý tương ứng. Cài đặt bảng phân đoạn: Hình 3.20 Hệ thống phân đoạn Có thể sử dụng các thanh ghi để lưu trữ bảng phân đoạn nếu số lượng phân đoạn nhỏ. Trong trường hợp chương trình bao gồm quá nhiều phân đoạn, bảng phân đoạn phải được lưu trong bộ nhớ chính. Một thanh ghi nền bảng phân đoạn (STBR) chỉ đến địa chỉ bắt đầu của bảng phân đoạn. Vì số lượng phân đoạn sử dụng trong một chương trình biến động, cần sử dụng thêm một thanh ghi đặc tả kích thước bảng phân đoạn (STLR). Với một địa chỉ logic , trước tiên số hiệu phân đoạn s được kiểm tra tính hợp lệ (s <STLR). Kế tiếp, cộng giá trị s với STBR để có được địa chỉ địa chỉ của phần tử thứ s trong bảng phân đoạn (STBR+s). Điạ chỉ vật lý cuối cùng là (STBR+s + d) Hình 3.21 Sử dụng STBR, STLR và bảng phân đoạn 83
Nguyên lý hệ điều hành Bảo vệ: Một ưu điểm đặc biệt của cơ chế phân đoạn là khả năng đặc tả thuộc tính bảo vệ cho mỗi phân đoạn. Vì mỗi phân đoạn biễu diễn cho một phần của chương trình với ngữ nghĩa được người dùng xác định, người sử dụng có thể biết được một phân đoạn chứa đựng những gì bên trong, do vậy họ có thể đặc tả các thuộc tính bảo vệ thích hợp cho từng phân đoạn. Cơ chế phần cứng phụ trách chuyển đổi địa chỉ bộ nhớ sẽ kiểm tra các bit bảo vệ được gán với mỗi phần tử trong bảng phân đoạn để ngăn chặn các thao tác truy xuất bất hợp lệ đến phân đoạn tương ứng. Chia sẻ phân đoạn: Hình 3.22 Chia sẻ code trong hệ phân đoạn Một ưu điểm khác của kỹ thuật phân đoạn là khả năng chia sẻ ở mức độ phân đoạn. Nhờ khả năng này, các tiến trình có thể chia sẻ với nhau từng phần chương trình ( ví dụ các thủ tục, hàm), không nhất thiết phải chia sẻ toàn bộ chương trình như trường hợp phân trang. Mỗi tiến trình có một bảng phân đoạn riêng, một phân đoạn được chia sẻ khi các phần tử trong bảng phân đoạn của hai tiến trình khác nhau cùng chỉ đến một vị trí vật lý duy nhất. Kỹ thuật phân đoạn thõa mãn được nhu cầu thể hiện cấu trúc logic của chương trình nhưng nó dẫn đến tình huống phải cấp phát các khối nhớ có kích thước khác nhau cho các phân đoạn trong bộ nhớ vật lý. Điều này làm rắc rối vấn đề hơn rất nhiều so với việc cấp phát các trang có kích thước tĩnh.Một giải pháp dung hoà là kết hợp cả hai kỹ thuật phân trang và phân đoạn : chúng ta tiến hành phân đoạn kết hợp phân trang 3.5.3. Phân đoạn kết hợp phân trang (Paged segmentation) 84
Nguyên lý hệ điều hành Ý tưởng: Không gian địa chỉ là một tập các phân đoạn, mỗi phân đoạn được chia thành nhiều trang. Khi một tiến trình được đưa vào hệ thống, hệ điều hành sẽ cấp phát cho tiến trình các khung trang cần thiết để chứa đủ các phân đoạn của tiến trình. Cơ chế MMU trong kỹ thuật phân đoạn kết hợp phân trang: Để hỗ trợ kỹ thuật phân đoạn, cần có một bảng phân đoạn, nhưng giờ đây mỗi phân đoạn cần có một bảng trang phân biệt. Chuyển đổi địa chỉ: Mỗi địa chỉ logic là một bộ ba: số hiệu phân đoạn (s): sử dụng như chỉ mục đến phần tử tương ứng trong bảng phân đoạn. Hình 3.23 Mô hình phân đoạn kế hợp phân trang số hiệu trang (p): sử dụng như chỉ mục đến phần tử tương ứng trong bảng trang của phân đoạn. địa chỉ tương đối trong trang (d): kết hợp với địa chỉ bắt đầu của trang để tạo ra địa chỉ vật lý mà trình quản lý bộ nhớ sử dụng. 85
Nguyên lý hệ điều hành Hình 3.24 Cơ chế phần cứng của sự phân đoạn kết hợp phân trang Tất cả các mô hình tổ chức bộ nhớ trên đây đều có khuynh hướng cấp phát cho tiến trình toàn bộ các trang yêu cầu trước khi thật sự xử lý. Vì bộ nhớ vật lý có kích thước rất giới hạn, điều này dẫn đến hai điểm bất tiện sau : Kích thước tiến trình bị giới hạn bởi kích thước của bộ nhớ vật lý. Khó có thể bảo trì nhiều tiến trình cùng lúc trong bộ nhớ, và như vậy khó nâng cao mức độ đa chương của hệ thống. 3.6 Bộ nhớ ảo (Virtual Memory) Bộ nhớ ảo là một kỹ thuật hiện đại giúp cho người dùng được giải phóng hoàn toàn khỏi mối bận tâm về giới hạn bộ nhớ. Ý tưởng, ưu điểm và những vấn đề liên quan đến việc tổ chức bộ nhớ ảo sẽ được trình bày trong bài học này. Nếu đặt toàn thể không gian địa chỉ vào bộ nhớ vật lý, thì kích thước của chương trình bị giới hạn bởi kích thước bộ nhớ vật lý. Thực tế, trong nhiều trường hợp, chúng ta không cần phải nạp toàn bộ chương trình vào bộ nhớ vật lý cùng một lúc, vì tại một thời điểm chỉ có một chỉ thị của tiến trình được xử lý. Ví dụ, các chương trình đều có một đoạn code xử lý lỗi, nhưng đoạn code này hầu như rất ít khi được sử dụng vì hiếm khi xảy ra lỗi, trong trường hợp này, không cần thiết phải nạp đoạn code xử lý lỗi từ đầu. Từ nhận xét trên, một giải pháp được đề xuất là cho phép thực hiện một chương trình chỉ được nạp từng phần vào bộ nhớ vật lý. Ý tưởng chính của giải pháp này là tại mỗi thời điểm chỉ lưu trữ trong bộ nhớ vật lý các chỉ thị và dữ liệu của chương trình cần thiết cho việc thi hành tại thời điểm đó. Khi cần đến các chỉ thị khác, những chỉ thị mới 86
Nguyên lý hệ điều hành sẽ được nạp vào bộ nhớ, tại vị trí trước đó bị chiếm giữ bởi các chỉ thị nay không còn cần đến nữa. Với giải pháp này, một chương trình có thể lớn hơn kích thước của vùng nhớ cấp phát cho nó. Một cách để thực hiện ý tưởng của giải pháp trên đây là sử dụng kỹ thuật overlay. Kỹ thuật overlay không đòi hỏi bất kỳ sự trợ giúp đặc biệt nào của hệ điều hành , nhưng trái lại, lập trình viên phải biết cách lập trình theo cấu trúc overlay, và điều này đòi hỏi khá nhiều công sức. Để giải phóng lập trình viên khỏi các suy tư về giới hạn của bộ nhớ, mà cũng không tăng thêm khó khăn cho công việc lập trình của họ, người ta nghĩ đến các kỹ thuật tự động, cho phép xử lý một chương trình có kích thước lớn chỉ với một vùng nhớ có kích thước nhỏ . Giải pháp được tìm thấy với khái niệm bộ nhớ ảo (virtual memory). 3.6.1. Định nghĩa Bộ nhớ ảo là một kỹ thuật cho phép xử lý một tiến trình không được nạp toàn bộ vào bộ nhớ vật lý. Bộ nhớ ảo mô hình hoá bộ nhớ như một bảng lưu trữ rất lớn và đồng nhất, tách biệt hẳn khái niệm không gian địa chỉ và không gian vật lý. Người sử dụng chỉ nhìn thấy và làm việc trong không gian địa chỉ ảo, việc chuyển đổi sang không gian vật lý do hệ điều hành thực hiện với sự trợ giúp của các cơ chế phần cứng cụ thể. Thảo luận: Cần kết hợp kỹ thuật swapping đển chuyển các phần của chương trình vào-ra giữa bộ nhớ chính và bộ nhớ phụ khi cần thiết. Nhờ việc tách biệt bộ nhớ ảo và bộ nhớ vật lý, có thể tổ chức một bộ nhớ ảo có kích thước lớn hơn bộ nhớ vật lý. Bộ nhớ ảo cho phép giảm nhẹ công việc của lập trình viên vì họ không cần bận tâm đến giới hạn của vùng nhớ vật lý, cũng như không cần tổ chức chương trình theo cấu trúc overlays. 87
Nguyên lý hệ điều hành Hình 3.25 Bộ nhớ ảo 3.6.2. Cài đặt bộ nhớ ảo Bộ nhớ ảo thường được thực hiện với kỹ thuật phân trang theo yêu cầu (demand paging). Cũng có thể sử dụng kỹ thuật phân đoạn theo yêu cầu ( demand segmentation) để cài đặt bộ nhớ ảo, tuy nhiên việc cấp phát và thay thế các phân đoạn phức tạp hơn thao tác trên trang, vì kích thước không bằng nhau của các đoạn. Phân trang theo yêu cầu ( demand paging) Một hệ thống phân trang theo yêu cầu là hệ thống sử dụng kỹ thuật phân trang kết hợp với kỹ thuật swapping. Một tiến trình được xem như một tập các trang, thường trú trên bộ nhớ phụ ( thường là đĩa). Khi cần xử lý, tiến trình sẽ được nạp vào bộ nhớ chính. Nhưng thay vì nạp toàn bộ chương trình, chỉ những trang cần thiết trong thời điểm hiện tại mới được nạp vào bộ nhớ. Như vậy một trang chỉ được nạp vào bộ nhớ chính khi có yêu cầu. Với mô hình này, cần cung cấp một cơ chế phần cứng giúp phân biệt các trang đang ở trong bộ nhớ chính và các trang trên đĩa. Có thể sử dụng lại bit valid-invalid nhưng với ngữ nghĩa mới: valid : trang tương ứng là hợp lệ và đang ở trong bộ nhớ chính . invalid : hoặc trang bất hợp lệ (không thuộc về không gian địa chỉ của tiến trình) hoặc trang hợp lệ nhưng đang được lưu trên bộ nhớ phụ. Một phần tử trong bảng trang mộ tả cho một trang không nằm trong bộ nhớ chính, sẽ được đánh dấu invalid và chứa địa chỉ của trang trên bộ nhớ phụ. Cơ chế phần cứng : 88
Nguyên lý hệ điều hành Cơ chế phần cứng hỗ trợ kỹ thuật phân trang theo yêu cầu là sự kết hợp của cơ chế hỗ trợ kỹ thuật phân trang và kỹ thuật swapping: Hình 3.26 Bảng trang với một số trang trên bộ nhớ phụ Bảng trang: Cấu trúc bảng trang phải cho phép phản ánh tình trạng của một trang là đang nằm trong bộ nhớ chính hay bộ nhớ phụ. Bộ nhớ phụ: Bộ nhớ phụ lưu trữ những trang không được nạp vào bộ nhớ chính. Bộ nhớ phụ thường được sử dụng là đĩa, và vùng không gian đĩa dùng để lưu trữ tạm các trang trong kỹ thuật swapping được gọi là không gian swapping. Lỗi trang Truy xuất đến một trang được đánh dấu bất hợp lệ sẽ làm phát sinh một lỗi trang (page fault). Khi dò tìm trong bảng trang để lấy các thông tin cần thiết cho việc chuyển đổi địa chỉ, nếu nhận thấy trang đang được yêu cầu truy xuất là bất hợp lệ, cơ chế phần cứng sẽ phát sinh một ngắt để báo cho hệ điều hành. Hệ điều hành sẽ xử lý lỗi trang như sau : Kiểm tra truy xuất đến bộ nhớ là hợp lệ hay bất hợp lệ 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 Tìm vị trí chứa trang muốn truy xuất trên đĩa. Tìm một khung trang trống trong bộ nhớ chính : 89
Nguyên lý hệ điều hành Nếu tìm thấy : đến bước 5 Nếu không còn khung trang trống, chọn một khung trang « nạn nhân » và chuyển trang « nạn nhân » ra bộ nhớ phụ (lưu nội dung của trang đang chiếm giữ khung trang này lên đĩa), cập nhật bảng trang tương ứng rồi đến bước 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. Tái kích hoạt tiến trình người sử dụng. Hình 3.27 Các giai đoạn xử lý lỗi trang 3.6.3.Các thuật toán thay thế trang Khi xảy ra một lỗi trang, cần phải mang trang vắng mặt vào bộ nhớ . Nếu không có một khung trang nào trống, hệ điều hành cần thực hiện công việc thay thế trang – chọn một trang đang nằm trong bộ nhớ mà không được sử dụng tại thời điểm hiện tại và chuyển nó ra không gian swapping trên đĩa để giải phóng một khung trang dành chỗ nạp trang cần truy xuất vào bộ nhớ. Như vậy nếu không có khung trang trống, thì mỗi khi xảy ra lỗi trang cần phải thực hiện hai thao tác chuyển trang : chuyển một trang ra bộ nhớ phụ và nạp một trang khác vào bộ nhớ chính. Có thể giảm bớt số lần chuyển trang bằng cách sử dụng thêm một bit cập nhật (dirty bit). Bit này được gắn với mỗi trang để phản ánh tình trạng trang có bị cập nhật hay không : giá trị của bit được cơ chế phần cứng đặt là 1 mỗi lần có một từ được ghi vào trang, để ghi nhận nội dung trang có bị sửa đổi. Khi cần thay thế một trang, nếu bit cập nhật có giá trị là 1 thì trang cần được lưu lại trên đĩa, ngược lại, nếu bit cập nhật là 0, nghĩa là trang không bị thay đổi, thì không cần lưu trữ trang trở lại đĩa. 90
Nguyên lý hệ điều hành số hiệu bit valid-invalid dirty trang bit Hình 3.28 Cấu trúc một phần tử trong bảng trang Sự thay thế trang là cần thiết cho kỹ thuật phân trang theo yêu cầu. Nhờ cơ chế này, hệ thống có thể hoàn toàn tách rời bộ nhớ ảo và bộ nhớ vật lý, cung cấp cho lập trình viên một bộ nhớ ảo rất lớn trên một bộ nhớ vật lý có thể bé hơn rất nhiều lần. Sự thi hành phân trang theo yêu cầu Việc áp dụng kỹ thuật phân trang theo yêu cầu có thể ảnh hưởng mạnh đến tình hình hoạt động của hệ thống. Gỉa sử p p = 0 : không có lỗi trang nào p = 1 : mỗi truy xuất sẽ phát sinh một lỗi trang Thời gian thật sự cần để thực hiện một truy xuất bộ nhớ (TEA) là: TEA = (1-p)ma + p (tdp) [+ swap out ] + swap in + tái kích hoạt Trong công thức này, ma là thời gian truy xuất bộ nhớ, tdp thời gian xử lý lỗi trang. Có thể thấy rằng, để duy trì ở một mức độ chấp nhận được sự chậm trễ trong hoạt động của hệ thống do phân trang, cần phải duy trì tỷ lệ phát sinh lỗi trang thấp. Hơn nữa, để cài đặt kỹ thuật phân trang theo yêu cầu, cần phải giải quyết hai vấn đề chính yếu : xây dựng một thuật toán cấp phát khung trang, và thuật toán thay thế trang. Các thuật toán thay thế trang Vấn đề chính khi thay thế trang là chọn lựa một trang « nạn nhân » để chuyển ra bộ nhớ phụ. Có nhiều thuật toán thay thế trang khác nhau, nhưng tất cả cùng chung một mục tiêu : chọn trang « nạn nhân » là trang mà sau khi thay thế sẽ gây ra ít lỗi trang nhất. Có thể đánh giá hiệu qủa của một thuật toán bằng cách xử lý trên một chuỗi các địa chỉ cần truy xuất và tính toán số lượng lỗi trang phát sinh. Ví dụ: Giả sữ theo vết xử lý của một tiến trình và nhận thấy tiến trình thực hiện truy xuất các địa chỉ theo thứ tự sau : 0100, 0432, 0101, 0162, 0102, 0103, 0104, 0101, 0611, 0102, 0103,0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105 91
Nguyên lý hệ điều hành Nếu có kích thước của một trang là 100 bytes, có thể viết lại chuỗi truy xuất trên giản lược hơn như sau : 1, 4, 1, 6, 1, 6, 1, 6, 1 Để xác định số các lỗi trang xảy ra khi sử dụng một thuật toán thay thế trang nào đó trên một chuỗi truy xuất cụ thể, còn cần phải biết số lượng khung trang sử dụng trong hệ thống. Để minh hoạ các thuật toán thay thế trang sẽ trình bày, chuỗi truy xuất được sử dụng là : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 a) Thuật toán FIFO Tiếp cận: Ghi nhận thời điểm một trang được mang vào bộ nhớ chính. Khi cần thay thế trang, trang ở trong bộ nhớ lâu nhất sẽ được chọn Ví dụ : sử dụng 3 khung trang , ban đầu cả 3 đều trống : 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 * * * * * * * * * * * * * * * Ghi chú : * : có lỗi trang Thảo luận: Để áp dụng thuật toán FIFO, thực tế không nhất thiết phải ghi nhận thời điểm mỗi trang được nạp vào bộ nhớ, mà chỉ cần tổ chức quản lý các trang trong bộ nhớ trong một danh sách FIFO, khi đó trang đầu danh sách sẽ được chọn để thay thế. Thuật toán they thế trang FIFO dễ hiểu, dễ cài đặt. Tuy nhiên khi thực hiện không phải lúc nào cũng có kết qủa tốt : trang được chọn để thay thế có thể là trang chức nhiều dữ liệu cần thiết, thường xuyên được sử dụng nên được nạp sớm, do vậy khi bị chuyển ra bộ nhớ phụ sẽ nhanh chóng gây ra lỗi trang. Số lượng lỗi trang xảy ra sẽ tăng lên khi số lượng khung trang sử dụng tăng. Hiện tượng này gọi là nghịch lý Belady. Ví dụ: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Sử dụng 3 khung trang , sẽ có 9 lỗi trang phát sinh 1 2 3 4 1 2 5 1 2 3 4 5 92
Nguyên lý hệ điều hành 1 1 1 4 4 4 5 5 5 5 5 5 2 2 2 1 1 1 1 1 3 3 3 3 3 3 2 2 2 2 2 4 4 * * * * * * * * * Sử dụng 4 khung trang , sẽ có 10 lỗi trang phát sinh 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 1 1 1 5 5 5 5 4 4 2 2 2 2 2 2 1 1 1 1 5 3 3 3 3 3 3 2 2 2 2 4 4 4 4 4 4 3 3 3 * * * * * * * * * * b). Thuật toán tối ưu Tiếp cận: Thay thế trang sẽ lâu được sử dụng nhất trong tương lai. Ví dụ : sử dụng 3 khung trang, khởi đầu đều trống: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 * * * * * * * * * Thảo luận: Thuật toán này bảo đảm số lượng lỗi trang phát sinh là thấp nhất , nó cũng không gánh chịu nghịch lý Belady, tuy nhiên, đây là một thuật toán không khả thi trong thực tế, vì không thể biết trước chuỗi truy xuất của tiến trình! c) Thuật toán « Lâu nhất chưa sử dụng » ( Least-recently-used LRU) Tiếp cận: Với mỗi trang, ghi nhận thời điểm cuối cùng trang được truy cập, trang được chọn để thay thế sẽ là trang lâu nhất chưa được truy xuất. Ví dụ: sử dụng 3 khung trang, khởi đầu đều trống: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 * * * * * * * * * * * * Thảo luận: 93
Nguyên lý hệ điều hành Thuật toán FIFO sử dụng thời điểm nạp để chọn trang thay thế, thuật toán tối ưu lại dùng thời điểm trang sẽ được sử dụng, vì thời điểm này không thể xác định trước nên thuật toán LRU phải dùng thời điểm cuối cùng trang được truy xuất – dùng quá khứ gần để dự đoán tương lai. Thuật toán này đòi hỏi phải được cơ chế phần cứng hỗ trợ để xác định một thứ tự cho các trang theo thời điểm truy xuất cuối cùng. Có thể cài đặt theo một trong hai cách 94
Nguyên lý hệ điều hành Chương 4 QUẢN LÝ VÙNG NHỚ PHỤ Máy tính phải sử dụng thiết bị có khả năng lưu trữ trong thời gian dài (long-time) vì: Phải chứa những lượng thông tin rất lớn (giữ vé máy bay, ngân hàng ). Thông tin phải được lưu trữ một thời gian dài trước khi xử lý. Nhiều tiến trình có thể truy cập thông tin cùng lúc. Giải pháp là sử dụng các thiết bị lưu trữ bên ngoài gọi là bộ nhớ ngoài. Bao gồm: ổ cứng đĩa mềm Đĩa CD Flash disk 4.1 Cấu trúc đĩa cứng Lưu trữ dữ liệu trên bề mặt các đĩa phủ vật liệu từ tính. Là loại bộ nhớ không thay đổi (Non-Volatile) Có vai trò quan trọng trong hệ thống. Dung lượng ngày càng được nâng lên và kích thước nhỏ đi. - Cấu tạo và nguyên lý hoạt động. Hình 4.1 95
Nguyên lý hệ điều hành - Cấu tạo: Vỏ đĩa cứng, đĩa từ, trục quay, đầu đọc ghi, mạch điều khiển, cổng kết nối.  Hình 4.2 Vỏ đĩa cứng: Là bảng gắn linh kiện có chức năng bảo vệ. Đĩa từ: Cấu tạo nhôm hay thủy tinh, gốm, Bề mặt phủ lớp từ tính. Xếp chồng nhau và dữ liệu ở cả 2 mặt. Hình 4.3 96
Nguyên lý hệ điều hành Trục quay (Động cơ quay): Truyền chuyển động quay. Cấu tạo nhẹ, chính xác Đầu đọc ghi: Cấu tạo gồm lõi ferit và cuộn dây. Cấu tạo nhỏ, đọc dữ liệu từ hóa trên mặt đĩa. Hình 4.4 Mạch điều khiển: Điều khiển động cơ đồng trục và cần đọc ghi. Bộ nhớ đệm. Đầu kết nối giao tiếp. Cổng kết nối: Kết nối với mainboard.Các chuẩn ATA, SATA, SATAII, Hình 4.5 97
Nguyên lý hệ điều hành - Cấu trúc bề mặt đĩa Track: Trên một bề mặt đĩa được chia ra nhiều vòng đồng tâm gọi là track. Trên track được chia ra các phần nhỏ bằng các đoạn hướng tâm gọi là Sector (512Byte) Được định dạng ở cấp thấp (Low format) Cylinder: Tập hợp các track cùng bán kính (ở các mặt đĩa khác nhau) Trên một ổ cứng có nhiều cylinder Hình 4.6 Nguyên lý hoạt động Truy cập ngẫu nhiên dữ liệu trên đĩa cứng. Thông qua đầu đọc/ghi để truy xuất hay ghi dữ liệu. Dữ liệu được ghi khi đầu đọc đưa dòng điện vào và lấy ra khi đọc. Dữ liệu trên đĩa được lưu dưới dạng các bit 0, Thông số và đặc tính của ổ cứng Dung lượng 98
Nguyên lý hệ điều hành Dung lượng ổ cứng được tính bằng: (số byte/sector) × (số sector/track) × (số cylinder) × (số đầu đọc/ghi). Theo nhà SX: 1GG = 1000 MB Tốc độ quay Số vòng/phút (revolutions per minute) Tốc độ quay tỉ lệ thuận với thời gian truy xuất dữ liệu 3.600 > 15.000 Bộ nhớ đệm Có nhiệm vụ như RAM, lưu dữ liệu tạm thời suốt thời gian làm việc của ổ cứng. Bộ nhớ đệm càng cao càng tốt (phụ thuộc hiệu suất hoạt động của ổ cứng) Chuẩn giao tiếp - Các chuẩn phổ biến ATA, SATA, SCSI, Fibre Channel (máy chủ máy trạm) tốc độ cao - Chuẩn SATA II đã xuất hiện với băng thông 300MB/s (hay 3Gb/s), gấp đôi so với SATA(150MB/s). Hình 4.7 Tốc độ truyền dữ liệu 99
Nguyên lý hệ điều hành - Tốc độ thực không thể đạt tốc độ chuẩn giao tiếp. - Các thông số ảnh hưởng đến tốc độ truyền dữ liệu: - Tốc độ quay Số lượng đĩa từ Công nghệ chế tạo Dung lượng bộ nhớ đệm Thiết đặt các Chế độ làm việc của ổ cứng. Thiết đặt phần cứng -Thiết đặt kênh Chuẩn giao tiếp ATA, trên cùng một cáp truyền Jumper (cầu đấu) M = Master SL = Slave CS = Cable Select -Thiết đặt chuẩn giao tiếp Hình 4.8 : Minh họa thiết đặt kênh Thiết đặt phần mềm 100
Nguyên lý hệ điều hành -Phân vùng (Partition) Phân vùng (partition): là tập hợp các vùng ghi nhớ dữ liệu trên các cylinder gần nhau với dung lượng theo thiết đặt của người sử dụng để sử dụng cho các mục đích sử dụng khác nhau. Có thể cài nhiều hệ điều hành Hỗ trợ quản lí dữ liệu hiệu quả hơn - Định dạng phân vùng FAT (File Allocation Table) Chuẩn hỗ trợ DOS và các hệ điều hành họ Windows 9X/Me. FAT32 (File Allocation Table, 32-bit) được hỗ trợ bắt đầu từ hệ điều hành Windows 95 OSR2 NTFS (Windows NT File System) Được hỗ trợ bắt đầu từ các hệ điều hành họ NT/2000/XP/Vista. - Format Format cấp thấp (low format) định dạng lại các track, sector, cylinder Format thông thường: định dạng mức cao (high-level format) Format nhanh (xóa các kí tự lưu trữ đầu tiên của hdh hay phần mềm) Format thường (Xóa dữ liệu và kiểm tra khối hư hỏng (bad block)) Ổ cứng và các lỗi liên quan.  Không nhận ổ đĩa khi cắm mới  Không tìm thấy hệ điều hành  Thường xuyên bị treo, truy cập ứng dụng chậm Khắc phục.  Kiểm tra từng phần để loại bỏ từ từ  Kiểm tra bằng phần mềm SCANDISK  Phân vùng lại nếu cần Đĩa mềm Mặt Rãnh Sector ý nghĩa 0 0 1 Bootsector 0 0 2,3 FAT1(File Allocation Table) 101
Nguyên lý hệ điều hành 0 0 4, 5 FAT2(dành trường hợp FAT1 hỏng) 0 0 6,7,8,9 Root directory 1 0 1,2,3 Root directory Đĩa cứng Mặt Rãnh Sector ý nghĩa 0 0 1 Bootsector 1 0 1 Cung khởi động Bảng các phân khu được tạo offset Nội dung Kích thước 1BEh Partition1 entry 16 byte 1CEh Partition1 entry 16 byte 1DEh Partition1 entry 16 byte 1EEh Partition1 entry 16 byte Nội dung 16 byte địa chỉ Kích thước Nội dung 00 1 byte địa chỉ khởi động 01 3 byte địa chỉ đầu phân khu 05 3 byte địa chỉ cuối phân khu 08 4 byte Số cung trước phân khu 0C 4 byte Số cung trong phân khu 04 1 byte Chỉ thị hệ thống 4.2 Hệ thống bảng Fat 3 byte BPB 512 byte lệnh nhẩy Chương trình mồi Hình 4.9 kết thúc FAT là vùng chứa thông tin định vị các vùng55A chớa nội dungsector các file trên đĩa a) Bootsector Bao gồm bảng tham số vật lý của đĩa và chương trình khởi động của HĐH (nếu có) 102
Nguyên lý hệ điều hành BPB (BIOS Parameters block) offset size ý nghĩa 0 3 byte lệnh nhẩy 3 8 byte chứa phiên bản của DOS 11 2 byte Kích thước 1 sector 13 1 byte Số sector cho một đơn vị cấp phát 14 2 byte Dự trữ 16 1 byte Số bảng FAT 17 2 byte Số phần tử tối đa có thể có trong thư mục gốc 19 2 byte Chỉ tổng số sector trên đĩa 32M 36 1 byte Số driver vật lý(đĩa mềm:0, đĩa cứng: 80) 37 1 byte Byte dự trữ 38 1 byte chữ ký của Bootsector 39 4 byte Số volume của đĩa 43 11 byte Nhãn đĩa 54 8byte Chứa một đoạn text miêu tả 62 byte bắt đầu chương trình mồi VD Bootsector đĩa cứng EB 3C 90 4D 53 57 49 4E 34 2E 31 M S W I N 4 1 0 0 0 2 b) FAT FAT 12 dùng 12 bit biểu diễn 1 FAT entry FAT 16 dùng 16 bit biểu diễn 1 FAT entry FAT 32 dùng 32 bit biểu diễn 1 FAT entry 212=(0 4096 FAT entry) 216=(0 65535 FAT entry) FAT entry FAT 12 FAT 16 Ý nghĩa 0 0FD 00FD Đĩa mềm 1 FFE FFFE Vùng đĩa không sử dụng 2 3 3 Vùng lưu giữ tiếp theo 3 FF7 FFF7 Vùng đĩa hỏng 6 FFF FFFF kết thúc File 7 000 0000 Vùng đĩa trống 103
Nguyên lý hệ điều hành Lưu giữ File theo FAT Các phần tử trong bảng FAT tạo thành danh sách móc nối và phần tử cuối cùng của danh sách có giá trị FFF(FFFF). Vì các phần tử tạo thành danh sách móc nối nên chúng không nhất thiết phải nằm cạnh nhau. Ví dụ : Tệp f1.txt có giá trị Starting cluster=6 0 FF0 1 FFF 2 3 4 4 8 5 FFF 6 9 7 5 8 7 9 3 Tệp được lưu ở các cluster sau: 6→9→3→4→8→7→5 c) Root Directory (DIR) Từ thư mục gốc cho phép định vị dưộctàn bộ cấu trúc logic của đĩa logic. Lối vào thư mục 32 byte 0-7 Tên file 8-10 Phần mở rộng 11 Thuộc tính của File 7 6 5 4 3 2 1 0 Dự trữ Dự trữ Archive Directory volum system hiden readonly 12-21 Dự trữ của DOS 22-23 Ngày tháng tạo File 24-25 Giờ phút tạo File 26-27 Chỉ ra nơi đầu tiên lưu trữ file 28-31 Chỉ độ lớn của File. d) Data area 104
Nguyên lý hệ điều hành Vùng data chính là nơi trên đĩa logic chứa nội dung các file có trên đĩa. Vùng này đưcợ chia thành các cluster (khối) và một file chứa nguyên vẹn một số cluster. 4.3 Hệ thống NTFS (New Technology File System) Bảng Partition (mặt 0, rãnh 0, cung 1) Boot sector (mặt 1, rãnh 0, cung 1) Win2000 NTFS nhìn thấy FAT32 FAT32 không nhìn thấy NTFS Bootsector Byte 0x00-0x0A: lệnh nhẩy và các thông tin khác Byte 0x0B-0x53: Các thông số BPB và BPB mở rộng Byte phần còn lại Đoạn mã khởi động MFT(Master File Table) chiếm 12% dung lượng đĩa Tương tự FAT (MFT1, MFT2) MFT chứa thông tin: cso 16 điểm vào đầu tiên(16 bản ghi) Bản ghi 1: MFT1 Bản ghi 2: MFT2 $logFile: chỉ ra sự thay đổi của danh mục $bitmap: $badcluster: danh sách khối hỏng $secure: thông tin bảo vệ $dùng cho file nhỏ 16 bản ghi System file File name MFT record Ý nghĩa MFT $MFT 0 Chứa một file cơ sở ghi nhớ mã file và thư mục trên NTFS MFT $MFT mirr 1 Bản sao LogFile $log File 2 Danh sách các thao tác khôi phục khi xoá Volumn $volumn 3 Chứa thông tin về ổ đĩa 105
Nguyên lý hệ điều hành Attribute $Att Def 4 Bảng tên số lượng va mô tả thuộc tính Rootfile name $RF 5 Thư mục gốc index Cluster bitmap $bitmap 6 Chỉ các cluster đã sử dụng Bootsector $Boot 7 Chứa PDB Bad cluster $badclus 8 Chứa cluster hỏng Secure File $sercure 9 chứa các danh sách an toàn Upcase Table $Upcase 10 Chuyển đổi ký tự NTFS $Extend 11 Mở rộng extension 12-15 Dự trữ 4.4 Các thông số và thuật toán truy nhập đĩa 4.4.1Các thông số Thời gian truy xuất dữ liệu=thời gian tìm kiếm+thời gian dịch chuyển + thời gian quay trễ Tốc độ đĩa bao gồm ba phần. Để truy xuất các khối trên đĩa, trước tiên phải di chuyển đầu đọc đến track hay cylinder thích hợp, thao tác này gọi là seek và thời gian để hoàn tất gọi là seek time(thời gian tìm kiếm). Một khi đã đến đúng track, còn phải chờ cho đến khi khối cần thiết đến dưới đầu đọc. Thời gian chờ này gọi là latency time(thời gian quay trễ). Cuối cùng là vận chuyển dữ liệu giữa đĩa và bộ nhớ chính gọi là transfer time(thời gian dịch chuyển). Tổng thời gian cho dịch vụ đĩa chính là tổng của ba khoảng thời gian trên. Trong đó seek time và latency time là mất nhiều thời gian nhất, do đó để giảm thiểu thời gian truy xuất hệ điều hành đưa ra các thuật toán lập lịch truy xuất. Hệ số đan xen Hệ số đan xen của các sector nhằm làm khớp tốc độ quay nhanh của đĩa với tốc độ mà đầu từ có thể xử lý dữ liệu chậm khi chúng đi qua hết một sector. Nếu dữ liệu của một tệp được ghi trên nhiều cung liên tiếp của một rãnh đầu từ phải đợi vòng quay tới để đọc cung tiếp theo do vậy làm tăng thời gian truy nhập. Để tối ưu hoá quá trình này, cung có thể được định địa chỉ xen kẽ khiến nhiều cung được đọc cùng một lúc trong một vòng quay của đĩa. 106
Nguyên lý hệ điều hành 0 0 7 5 6 1 2 3 2 6 5 7 4 3 4 1 0 0 Xen kẽ với hệ số đan xen là 3 Không đan xen Hình 4.10 4.4.2 Các thuật toán đọc đĩa Tất cả mọi công việc đều phụ thuộc vào việc nạp chương trình và nhập xuất tập tin, do đó điều quan trọng là dịch vụ đĩa phải càng nhanh càng tốt. Hệ điều hành có thể tổ chức dịch vụ truy xuất đĩa tốt hơn bằng cách lập lịch yêu cầu truy xuất đĩa. a) Lập lịch FCFS : Phương pháp lập lịch đơn giản nhất là FCFS(first-come,first-served). Thuật toán này rất dể lập trình nhưng không cung cấp được một dịch vụ tốt. Ví dụ : cần phải đọc các khối theo thứ tự như sau : 98, 183, 37, 122, 14, 124, 65, và 67 Giả sử hiện tại đầu đọc đang ở vị trí 53. Như vậy đầu đọc lần lượt đi qua các khối 53, 98, 183, 37, 122, 14, 124, 65, và 67 như hình sau : Hình 4.11 Phương pháp FCFS b)Lập lịch SSTF (shortest-seek-time-first) Thuật toán này sẽ di chuyển đầu đọc đến các khối cần thiết theo vị trí lần lượt gần với vị trí hiện hành của đầu đọc nhất. Ví dụ : cần đọc các khối như sau : 98, 183, 37, 122, 14, 124, 65, và 67 107
Nguyên lý hệ điều hành Giả sử hiện tại đầu đọc đang ở vị trí 53. Như vậy đầu đọc lần lượt đi qua các khối 53, 65, 67, 37, 14, 98, 122, 124 và 183 như hình sau : Hình 4.12 Phương pháp SSTF Với ví dụ này, thuật toán SSTF làm giảm số khối mà đầu đọc phải di chuyển là 208 khối. c)Lập lịch SCAN Theo thuật toán này, đầu đọc sẽ di chuyển về một phía của đĩa và từ đó di chuyển qua phía kia. Ví dụ : cần đọc các khối như sau : 98, 183, 37, 122, 14, 124, 65, và 67 Giả sử hiện tại đầu đọc đang ở vị trí 53. Như vậy đầu đọc lần lượt đi qua các khối 53, 37, 14, 0 , 65, 67, 98, 122, 124 và 183 như hình sau : Thuật toán này còn được gọi là thuật toán thang máy. Hình ảnh thuật toán giống như hình ảnh của một người quét tuyết, hay quét lá. d)Lập lịch C-SCAN Thuật toán này tương tự như thuật toán SCAN, chỉ khác là khi nó di chuyển đến một đầu nào đó của đĩa, nó sẽ lập tức trở về đầu bắt đầu của đĩa. Lấy lại ví dụ trên, khi đó thứ tự truy xuất các khối sẽ là : 53, 65, 67, 98, 122, 124, 183, 199, 0, 14, 37 như hình sau : 108
Nguyên lý hệ điều hành Hình 4.13 Phương pháp C-SCAN e)Lập lịch LOOK: Nhận xét rằng cả hai thuật toán lập lịch SCAN và C-SCAN luôn luôn chuyển đầu đọc của đĩa từ đầu này sang đầu kia. Nhưng thông thường thì đầu đọc chỉ chuyển đến khối xa nhất ở mỗi hướng chứ không đến cuối. Do đó SCAN và C-SCAN được chỉnh theo thực tế và gọi là lập lịch LOOK. Như hình sau : Hình 4.14 Phương pháp LOOK Lựa chọn thuật toán lập lịch : Với những thuật toán lập lịch, vấn đề là phải lựa chọn thuật toán nào cho hệ thống. Thuật toán SSTF thì rất thông thường. Thuật toán SCAN và C-SCAN thích hợp cho những hệ thống phải truy xuất dữ liệu khối lượng lớn. Với bất kỳ thuật toán lập lịch nào, điều quan trọng là khối lượng về số và kiểu khối cần truy xuất. Ví dụ , nếu số khối cần truy xuất là liên tục thì FCFS là thuật toán tốt. Quản lý lỗi Đĩa là đối tượng mà khi truy xuất có thể gây nhiều lỗi. Một trong số các lỗi thường gặp là Lỗi lập trình : yêu cầu đọc các sector không tồn tại. Lỗi lập trình xảy ra khi yêu cầu bộ điều khiển tìm kiếm cylinder không tồn tại, đọc sector không tồn tại, dùng đầu đọc không tồn tại, hoặc vận chuyển vào và ra bộ nhớ không tồn tại. Hầu hết các bộ điều khiển kiểm tra các tham số và sẽ báo lỗi nếu không thích hợp. Lỗi checksum tạm thời : gây ra bởi bụi trên đầu đọc. Bụi tồn tại giữa đầu đọc và bề mặt đĩa sẽ gây ra lỗi đọc. Nếu lỗi tồn tại, khối có thể bị đánh dấu hỏng bởi phần mềm. Lỗi checksum thường trực : đĩa bị hư vật lý trên các khối. Lỗi tìm kiếm : ví dụ đầu đọc đến cylinder 7 trong khi đó phải đọc 6. 109
Nguyên lý hệ điều hành Lỗi điều khiển : bộ điều khiển từ chối thi hành lệnh. 110
Nguyên lý hệ điều hành Chương 5 QUẢN LÝ VÀO RA Một trong những chức năng chính của hệ điều hành là quản lý tất cả những thiết bị nhập/xuất của máy tính. Hệ điều hành phải ra các chỉ thị điều khiển thiết bị, kiểm soát các ngắt và lỗi. Hệ điều hành phải cung cấp một cách giao tiếp đơn giản và tiện dụng giữa các thiết bị và phần còn lại của hệ thống và giao tiếp này phải độc lập với thiết bị. 5.1 Khái niệm về hệ thống quản lý vào/ ra Hệ thống quản lý nhập/xuất được tổ chức theo từng lớp, mỗi lớp có một chức năng nhất định và các lớp có giao tiếp với nhau như sơ đồ sau : CÁC LỚP CHỨC NĂNG VÀO/RA Xử lý của người dùng Tạo lời gọi nhập/xuất, định dạng nhập/xuất Phần mềm độc lập thiết Đặt tên, bảo vệ, tổ chức khối, bộ đệm, định vị bị Điều khiển thiết bị Thiết lập thanh ghi thiết bị, kiểm tra trạng thái Kiểm soát ngắt Báo cho driver khi nhập/xuất hoàn tất Phần cứng Thực hiện thao tác nhập/xuất Ví dụ: Trong một chương trình ứng dụng, người dùng muốn đọc một khối từ một tập tin, hệ điều hành được kích hoạt để thực hiện yêu cầu này. Phần mềm độc lập thiết bị tìm kiếm trong cache, nếu khối cần đọc không có sẵn, nó sẽ gọi chương trình điều khiển thiết bị gửi yêu cầu đến phần cứng. Tiến trình bị ngưng lại cho đến khi thao tác đĩa hoàn tất. Khi thao tác này hoàn tất, phần cứng phát sinh một ngắt. Bộ phận kiểm soát ngắt kiểm tra biến cố này, ghi nhận trạng thái của thiết bị và đánh thức tiến trình bị ngưng để chấm dứt yêu cầu I/O và cho tiến trình của người sử dụng tiếp tục thực hiện. 5.2 Phần cứng vào/ra 5.2.1 Các thiết bị vào/ra Các thiết bị nhập xuầt có thể chia tương đối thành hai loại là thiết bị khối (block device)và thiết bị tuần tự(character device). - Thiết bị khối là thiết bị mà thông tin được lưu trữ trong những khối có kích thước cố định và được định vị bởi địa chỉ. Kích thước thông thường của một khối là khoảng từ 128 bytes đến 1024 bytes. Đặc điểm của thiết bị khối là chúng có thể được truy xuất (đọc hoặc ghi) từng khối riêng biệt, và chương trình có thể truy xuất một khối bất kỳ nào đó. Đĩa là một ví dụ cho loại thiết bị khối. - Một dạng thiết bị thứ hai là thiết bị tuần tự. Ở dạng thiết bị này, việc gửi và nhận thông tin dựa trên là chuỗi các bits, không có xác định địa chỉ và không thể thực 111
Nguyên lý hệ điều hành hiện thao tác seek được. Màn hình, bàn phím, máy in, card mạng, chuột, và các loại thiết bị khác không phải dạng đĩa là thiết bị tuần tự. Việc phân chia các lớp như trên không hoàn toàn tối ưu, một số các thiết bị không phù hợp với hai lớp trên, ví dụ : đồng hồ, bộ nhớ màn hình v.v không thực hiện theo cơ chế tuần tự các bits. Ngoài ra, người ta còn phân loại các thiết bị I/O dưới một tiêu chuẩn khác : - Thiết bị tương tác được với con người : dùng để giao tiếp giữa người và máy. Ví dụ : màn hình, bàn phím, chuột, máy in - Thiết bị tương tác trong hệ thống máy tính là các thiết bị giao tiếp với nhau. Ví dụ : đĩa, băng từ, card giao tiếp - Thiết bị truyền thồng : như modem Những điểm khác nhau giữa các thiết bị I/O gồm : Tốc độ truyền dữ liệu , ví dụ bàn phím : 0.01 KB/s, chuột 0.02 KB/s Công dụng. Đơn vị truyền dữ liệu (khối hoặc ký tự). Biểu diễn dữ liệu, điều này tùy thuộc vào từng thiết bị cụ thể. Tình trạng lỗi : nguyên nhân gây ra lỗi, cách mà chúng báo về Một thiết bị giao tiếp với một hệ thống máy tính bằng cách gửi các tín hiệu qua dây cáp hay thậm chi qua không khí. Các thiết bị giao tiếp với máy tính bằng một điểm nối kết(cổng-port) như cổng tuần tự. Nếu một hay nhiều thiết bị dung một tập hợp dây dẫn, nối kết được gọi là bus. Một bus là một tập hợp dây dẫn và giao thức được định nghĩa chặt chẽ để xác định tập hợp thông điệp có thể được gửi qua dây. Trong thuật ngữ điện tử, các thông điệp được truyền bởi các mẫu điện thế điện tử được áp dụng tới các dây dẫn với thời gian được xác định. Khi thiết bị A có một cáp gán vào thiết bị B, thiết bị B có một cáp gán vào thiết bị C và thiết bị C gán vào một cổng máy tính, sự sắp xếp này được gọi là chuỗi nối tiếp. Một chuỗi nối tiếp thường điều hành như một bus. 5.2.2 Tổ chức của chức năng I/O Có ba cách để thực hiện I/O : Một là, bộ xử lý phát sinh một lệnh I/O đến các đơn vị I/O, sau đó, nó chờ trong trạng thái "busy" cho đến khi thao tác này hoàn tất trước khi tiếp tục xử lý. 112
Nguyên lý hệ điều hành Hai là, bộ xử lý phát sinh một lệnh I/O đến các đơn vị I/O, sau đó, nó tiếp tục việc xử lý cho tới khi nhận được một ngắt từ đơn vị I/O báo là đã hoàn tất, nó tạm ngưng việc xử lý hiện tại để chuyển qua xử lý ngắt. Ba là, sử dụng cơ chế DMA (như được đề cập ở sau) Các bước tiến hóa của chức năng I/O : Bộ xử lý kiểm soát trực tiếp các thiết bị ngoại vi. Hệ thống có thêm bộ điều khiển thiết bị. Bộ xử lý sử dụng cách thực hiện nhập xuất thứ nhất. Theo cách này bộ xử lý được tách rời khỏi các mô tả chi tiết của các thiết bị ngoại vi. Bộ xử lý sử dụng thêm cơ chế ngắt. Sử dụng cơ chế DMA, bộ xử lý truy xuất những dữ liệu I/O trực tiếp trong bộ nhớ chính. 5.2.3 Bộ điều khiển thiết bị Một đơn vị bị nhập xuất thường được chia làm hai thành phần chính là thành phần cơ và thành phần điện tử. Thành phần điện tử được gọi là bộ phận điều khiển thiết bị hay bộ tương thích, trong các máy vi tính thường được gọi là card giao tiếp. Thành phần cơ chính là bản thân thiết bị. Một bộ phận điều khiển thường có bộ phận kết nối trên chúng để có thể gắn thiết bị lên đó. Một bộ phận điều khiển có thể quản lý được hai, bốn hay thậm chí tám thiết bị khác nhau. Nếu giao tiếp giữa thiết bị và bộ phận điều khiển là các chuẩn như ANSI, IEEE hay ISO thì nhà sản xuất thiết bị và bộ điều khiển phải tuân theo chuẩn đó, ví dụ : bộ điều khiển đĩa được theo chuẩn giao tiếp của IBM. Giao tiếp giữa bộ điều khiển và thiết bị là giao tiếp ở mức thấp. Hình 5.1 Sự kết nối giữa CPU, bộ nhớ, bộ điều khiển và các thiết bị nhập xuất 113
Nguyên lý hệ điều hành Chức năng của bộ điều khiển là giao tiếp với hệ điều hành vì hệ điều hành không thể truy xuất trực tiếp với thiết bị. Việc thông tin thông qua hệ thống đường truyền gọi là bus. Công việc của bộ điều khiển là chuyển đổi dãy các bit tuần tự trong một khối các byte và thực hiện sửa chửa nếu cần thiết. Thông thường khối các byte được tổ chức thành từng bit và đặt trong buffer của bộ điều khiển. Sau khi thực hiện checksum nội dung của buffer sẽ được chuyển vào bộ nhớ chính. Ví dụ : bộ điều khiển cho màn hình đọc các byte của ký tự để hiển thị trong bộ nhớ và tổ chức các tín hiệu để điều khiển các tia của CRT để xuất trên màn ảnh bằng cách quét các tia dọc và ngang. Nếu không có bộ điều khiển, lập trình viên hệ điều hành phải tạo thêm chương trình điều khiển tín hiệu analog cho đèn hình. Với bộ điều khiển , hệ điều hành chỉ cần khởi động chúng với một số tham số như số ký tự trên một dòng, số dòng trên màn hình và bộ điều khiển sẽ thực hiện điều khiển các tia. Mỗi bộ điều khiển có một số thanh ghi để liên lạc với CPU. Trên một số máy tính, các thanh ghi này là một phần của bộ nhớ chính tại một địa chỉ xác định gọi là ánh xạ bộ nhớ nhập xuất. Hệ máy PC dành ra một vùng địa chỉ đặc biệt gọi là địa chỉ nhập xuất và trong đó được chia làm nhiều đoạn, mỗi đoạn cho một loại thiết bị như sau : Bộ điều khiển Địa chỉ nhập/xuất Vectơ ngắt nhập/xuất Đồng hồ 040 - 043 8 Bàn phím 060 - 063 9 RS232 phụ 2F8 - 2FF 11 Đĩa cứng 320 - 32F 13 Máy in 378 - 37F 15 Màn hình mono 380 - 3BF - Màn hình màu 3D0 - 3DF - Đĩa mềm 3F0 - 3F7 14 RS232 chính 3F8 - 3FF 12 Hệ điều hành thực hiện nhập xuất bằng cách ghi lệnh lên các thanh ghi của bộ điều khiển. Ví dụ : bộ điều khiển đĩa mềm của IBMPC chấp nhận 15 lệnh khác nhau như : READ, WRITE, SEEK, FORMAT, RECALIBRATE, một số lệnh có tham số và các tham số cũng được nạp vào thanh ghi. Khi một lệnh đã được chấp nhận, CPU sẽ rời bộ điều khiển để thực hiện công việc khác. Sau khi thực hiện xong, bộ điều khiển phát sinh một ngắt để báo hiệu cho CPU biết và đến lấy kết quả được lưu giữ trong các thanh ghi. 5.2.4 Truy nhập bộ nhớ trực tiếp DMA (Direct Memory Access) 114
Nguyên lý hệ điều hành Đa số các loại thiết bị, đặc biệt là các thiết bị dạng khối, hỗ trợ cơ chế DMA (direct memory access). Để hiểu về cơ chế này, trước hết phải xem xét quá trình đọc đĩa mà không có DMA. Trước tiên, bộ điều khiển đọc tuần tự các khối trên đĩa, từng bit từng bit cho tới khi toàn bộ khối được đưa vào buffer của bộ điều khiển. Sau đó máy tính thực hiện checksum để đảm bảo không có lỗi xảy ra. Tiếp theo bộ điều khiển tạo ra một ngắt để báo cho CPU biết. CPU đến lấy dữ liệu trong buffer chuyển về bộ nhớ chính bằng cách tạo một vòng lặp đọc lần lượt từng byte. Thao tác này làm lãng phí thời gian của CPU. Do đó để tối ưu, người ta đưa ra cơ chế DMA. Cơ chế DMA giúp cho CPU không bị lãng phí thời gian. Khi sử dụng, CPU gửi cho bộ điều khiển một số các thông số như địa chỉ trên đĩa của khối, địa chỉ trong bộ nhớ nơi định vị khối, số lượng byte dữ liệu để chuyển. Sau khi bộ điều khiển đã đọc toàn bộ dữ liệu từ thiết bị vào buffer của nó và kiểm tra checksum. Bộ điều khiển chuyển byte đầu tiên vào bộ nhớ chính tại địa chỉ được mô tả bởi địa chỉ bộ nhớ DMA. Sau đó nó tăng địa chỉ DMA và giảm số bytes phải chuyển. Quá trình này lập cho tới khi số bytes phải chuyển bằng 0, và bộ điều khiển tạo một ngắt. Như vậy không cần phải copy khối vào trong bộ nhớ, nó đã hiện hữu trong bộ nhớ. 5.3 Phần mềm vào/ra Mục tiêu chung của thiết bị logic là dể biểu diễn. Thiết bị logic được tổ chức thành nhiều lớp. Lớp dưới cùng giao tiếp với phần cứng, lớp trên cùng giao tiếp tốt, thân thiện với người sử dụng. Khái niệm then chốt của thiết bị logic là độc lập thiết bị, ví dụ : có thể viết chương trình truy xuất file trên đĩa mềm hay đĩa cứng mà không cần phải mô tả lại chương trình cho từng loại thiết bị. Ngoài ra, thiết bị logic phải có khả năng kiểm soát lỗi. Thiết bị logic được tổ chức thành bốn lớp : Kiểm soát lỗi, điều khiển thiết bị, phần mềm hệ điều hành độc lập thiết bị, phần mềm mức người sử dụng. 5.3.1 Kiểm soát ngắt Ngắt là một hiện tượng phức tạp. Nó phải cần được che dấu sâu trong hệ điều hành, và một phần ít của hệ thống biết về chúng. Cách tốt nhất để che dấu chúng là hệ điều hành có mọi tiến trình thực hiện thao tác nhập xuất cho tới khi hoàn tất mới tạo ra một ngắt. Tiến trình có thể tự khóa lại bằng cách thực hiện lệnh WAIT theo một biến điều kiện hoặc RECEIVE theo một thông điệp. Khi một ngắt xảy ra, hàm xử lý ngắt khởi tạo một tiến trình mới để xử lý ngắt. Nó sẽ thực hiện một tín hiệu trên biến điều kiện và gửi những thông điệp đến cho các tiến trình bị khóa. Tổng quát, chức năng của ngắt là làm cho một tiến trình đang bị khóa được thi hành trở lại. 115
Nguyên lý hệ điều hành 5.3.2 Điều khiển thiết bị (device drivers) Tất cả các đoạn mã độc lập thiết bị đều được chuyển đến device drivers. Mỗi device drivers kiểm soát mỗi loại thiết bị, nhưng cũng có khi là một tập hợp các thiết bị liên quan mật thiết với nhau. Device drivers phát ra các chỉ thị và kiểm tra xem chỉ thị đó có được thực hiện chính xác không. Ví dụ, driver của đĩa là phần duy nhất của hệ điều hành kiểm soát bộ điều khiển đĩa. Nó quản lý sectors, tracks, cylinders, head, chuyển động, interleave, và các thành phần khác giúp cho các thao tác đĩa được thực hiện tốt. Chức năng của device drivers là nhận những yêu cầu trừu tượng từ phần mềm nhập/xuất độc lập thiết bị ở lớp trên, và giám sát yêu cầu này thực hiện. Nếu driver đang rảnh, nó sẽ thực hiện ngay yêu cầu, ngược lại, yêu cầu đó sẽ được đưa vào hàng đợi. Ví dụ, bước đầu tiên của yêu cầu nhập/xuất đĩa là chuyển từ trừu tượng thành cụ thể. Driver của đĩa phải biết khối nào cần đọc, kiểm tra sự hoạt động của motor đĩa, xác định vị trí của đầu đọc đã đúng chưa v.v Nghĩa là device drivers phải xác định được những thao tác nào của bộ điều khiển phải thi hành và theo trình tự nào. Một khi đã xác định được chỉ thị cho bộ điều khiển, nó bắt đầu thực hiện bằng cách chuyển lệnh vào thanh ghi của bộ điều khiển thiết bị. Bộ điều khiển có thể nhận một hay nhiều chỉ thị liên tiếp và sau đó tự nó thực hiện không cần sự trợ giúp của hệ điều hành. Trong khi lệnh thực hiện. Có hai trường hợp xảy ra : Một là device drivers phải chờ cho tới khi bộ điều khiển thực hiện xong bằng cách tự khóa lại cho tới khi một ngắt phát sinh mở khóa cho nó. Hai là, hệ điều hành chấm dứt mà không chờ, vì vậy driver không cần thiết phải khóa. Sau khi hệ điều hành hoàn tất việc kiểm tra lỗi và nếu mọi thứ đều ổn driver sẽ chuyển dữ liệu cho phần mềm độc lập thiết bị. Cuối cùng nó sẽ trả về thông tin về trạng thái hay lỗi cho nơi gọi và nếu có một yêu cầu khác ở hàng đợi, nó sẽ thực hiện tiếp, nếu không nó sẽ khóa lại chờ đến yêu cầu tiếp theo. 5.3.3 Phần mềm nhập/xuất độc lập thiết bị Mặc dù một số phần mềm nhập/xuất mô tả thiết bị nhưng phần lớn chúng là độc lập với thiết bị. Ranh giới chính xác giữa drivers và phần mềm độc lập thiết bị là độc lập về mặt hệ thống, bởi vì một số hàm mà được thi hành theo kiểu độc lập thiết bị có thể được thi hành trên drivers vì lý do hiệu quả hay những lý dó khác nào đó. Giao tiếp đồng nhất cho device drivers Đặt tên thiết bị Bảo vệ thiết bị 116
Nguyên lý hệ điều hành Cung cấp khối độc lập thiết bị Tổ chức buffer Định vị lưu trữ trên thiết bị khối Cấp phát và giải phóng thiết bị tận hiến Báo lỗi Chức năng cơ bản của phần mềm nhập/xuất độc lập thiết bị là những chức năng chung cho tất cả các thiết bị và cung cấp một giao tiếp đồng nhất cho phần mềm phạm vi người sử dụng. Trước tiên nó phải có chức năng tạo một ánh xạ giữa thiết bị và một tên hình thức. Ví dụ đối với UNIX, tên /dev/tty0 dành riêng để mô tả I-node cho một file đặc biệt, và I-node này chứa chứa số thiết bị chính, được dùng để xác định driver thích hợp và số thiết bị phụ, được dùng để xác định các tham số cho driver để cho biết là đọc hay ghi. Thứ hai là bảo vệ thiết bị, là cho phép hay không cho phép người sử dụng truy xuất thiết bị. Các hệ điều hành có thể có hay không có chức năng này. Thứ ba là cung cấp khối dữ liệu độc lập thiết bị vì ví dụ những đĩa khác nhau sẽ có kích thước sector khác nhau và điều này sẽ gây khó khăn cho các phần mềm người sử dụng ở lớp trên. Chức năng này cung cấp các khối dữ liệu logic độc lập với kích thước sector vật lý. Thứ tư là cung cấp buffer để hỗ trợ cho đồng bộ hóa quá trình hoạt động của hệ thống. Ví dụ buffer cho bàn phím. Thứ năm là định vị lưu trữ trên các thiết bị khối. Thứ sáu là cấp phát và giải phóng các thiết bị tận hiến. Cuối cùng là thông báo lỗi cho lớp bên trên từ các lỗi do device driver báo về. 5.3.4 Phần mềm vào/ra phạm vi người sử dụng Hầu hết các phần mềm nhập/xuất đều ở bên trong của hệ điều hành và một phần nhỏ của chúng chứa các thư viện liên kết với chương trình của người sử dụng ngay cả những chương trình thi hành bên ngoài hạt nhân. Lời gọi hệ thống, bao gồm lời gọi hệ thống nhập/xuất thường được thực hiện bởi các hàm thư viện. Ví dụ khi trong chương trình C có lệnh count = write(fd, buffer, nbytes) ; 117
Nguyên lý hệ điều hành Hàm thư viện write được địch và liên kết dưới dạng nhị phân và nằm trong bộ nhớ khi thi hành. Tập hợp tất cả những hàm thư viện này rõ ràng là một phần của hệ thống nhập/xuất. Không phải tất cả các phần mềm nhập/xuất đều chứa hàm thư viện, có một loại quan trọng khác gọi là hệ thống spooling dùng để khai thác tối đa thiết bị nhập/xuất trong hệ thống đa chương. Các hàm thư viện chuyển các tham số thích hợp cho lời gọi hệ thống và hàm thư viện thực hiện việc định dạng cho nhập và xuất như lệnh printf trong C. Thư viện nhập/xuất chuẩn chứa một số hàm có chức năng nhập/xuất và tất cả chạy như chương trình người dùng. Chức năng của spooling là tránh trường hợp một tiến trình đang truy xuất thiết bị, chiếm giữ thiết bị nhưng sau đó không làm gì cả trong một khoảng thời gian và như vậy các tiến trình khác bị ảnh hưởng vì không thể truy xuất thiết bị đó. Một ví dụ của spooling device là line printer. Spooling còn được sử dụng trong hệ thống mạng như hệ thống e-mail chẳng hạn. 118
Nguyên lý hệ điều hành Chương 6: HỆ THỐNG QUẢN LÝ FILE Trong hầu hết các ứng dụng, tập tin là thành phần chủ yếu. Cho dù mục tiêu của ứng dụng là gì nó cũng phải bao gồm phát sinh và sử dụng thông tin. Thông thường đầu vào của các ứng dụng là tập tin và đầu ra cũng là tập tin cho việc truy xuất của người sử dụng và các chương trình khác sau này. 6.1 File và các khái niệm liên quan Tập tin Máy tính có thể lưu giữ thông tin trên các thiết bị lưu trữ khác nhau như đĩa từ, băng từ, đĩa quang Để cho máy tính trở nên thuận tiện và dễ sử dụng, HĐH cung cấp một cách lưu giữ thông tin logic như nhau trên các thiết bị lưu giữ đó là file (tập tin) Tập tin là đơn vị lưu trữ thông tin của bộ nhớ ngoài. Các tiến trình có thể đọc hay tạo mới tập tin nếu cần thiết. Thông tin trên tập tin là vững bền không bị ảnh hưởng bởi các xử lý tạo hay kết thúc các tiến trình, chỉ mất đi khi user thật sự muốn xóa. Tập tin được quản lý bởi hệ điều hành. Các thuộc tính file - Tên tập tin : Tập tin là một cơ chế trừu tượng và để quản lý mỗi đối tượng phải có một tên. Khi tiến trình tạo một tập tin, nó sẽ đặt một tên, khi tiến trình kết thúc tập tin vẫn tồn tại và có thể được truy xuất bởi các tiến trình khác với tên tập tin đó. Cách đặt tên tập tin của mỗi hệ điều hành là khác nhau, đa số các hệ điều hành cho phép sử dụng 8 chữ cái để đặt tên tập tin như ctdl, caycb, tamhghau v.v , thường thường thì các ký tự số và ký tự đặc biệt cũng được sử dụng như baitap2 , Hệ thống tập tin có thể có hay không phân biệt chữ thường và chữ hoa. Ví dụ : UNIX phân biệt chữ thường và hoa còn MS-DOS thì không phân biệt. Nhiều hệ thống tập tin hỗ trợ tên tập tin gồm 2 phần được phân cách bởi dấu ‘.’ mà phần sau được gọi là phần mở rộng. Ví dụ : vidu.txt. Trong MS-DOS tên tập tin có từ 1 đến 8 ký tư, phần mở rộng có từ 1 đến 3 ký tự. Trong UNIX có thể có nhiều phân cách như prog.c.Z. Một số kiểu mở rộng thông thường là : .bak, .bas, .bin, .c, .dat, .doc, .ftn, .hlp, .lib, .obj, .pas, .tex, .txt. Trên thực tế phần mở rộng có hữu ích trong một số trường hợp, ví dụ như có những trình dịch C chỉ nhận biết các tập tin có phần mở rộng là .C Loại File: được thể hiện ở phần mở rộng và cách thực hiện trên file 119
Nguyên lý hệ điều hành Loại File Phần mở Chức năng rộng Excutable Exe, com, bin sẵn sàng để chạy ngôn ngữ máy Object Obj,o dịch ngôn ngữ máy, không liên kết Source code C, pas, asm Mã nguồn Batch Bat, sh xử lý theo lô Text Txt, doc đocữ liệu văn bản, tài liệu Library Lib,a Thư viện Print or Ps, pdf, gif In ấn và hiển thị view Archive Arc, zip, tar Nhóm các file trong một file, lưu giữ. Ngoài tên và dữ liệu, hệ điều hành cung cấp thêm một số thông tin cho tập tin gọi là thuộc tính. Các thuộc tính thông dụng trong một số hệ thống tập tin : Tên thuộc tính Ý nghĩa Bảo vệ Ai có thể truy xuất được và bằng cách nào Mật khẩu Mật khẩu cần thiết để truy xuất tập tin Người tạo Id của người tạo tập tin Người sở hữu Người sở hữu hiện tại Chỉ đọc 0 là đọc ghi, 1 là chỉ đọc ẩn 0 là bình thường, 1 là không hiển thị khi liệt kê Hệ thống 0 là bình thường, 1 là tập tin hệ thống Lưu trữ 0 đã đuợc backup, 1 cần backup ASCII/binary 0 là tập tin văn bản, 1 là tập tin nhị phân Truy xuất ngẫu nhiên 0 truy xuất tuần tự, 1 là truy xuất ngẫu nhiên Temp 0 là bình thường, 1 là bị xóa khi tiến trình kết thúc Khóa 0 là không khóa, khác 0 là khóa Độ dài của record Số byte trong một record Vị trí khóa Offset của khóa trong mỗi record Giờ tạo Ngày và giờ tạo tập tin Thời gian truy cập Ngày và giờ truy xuất tập tin gần nhất cuối cùng Thời gian thay đổi Ngày và giờ thay đổi tập tin gần nhất cuối cùng Kích thước hiện thời Số byte của tập tin Kích thước tối đa. Số byte tối đa của tập tin Hình 8.3 Một số thuộc tính thông dụng của tập tin 6.2 Thư mục: khái niệm, hệ thống thư mục, tổ chức bên trong 120
Nguyên lý hệ điều hành Thư mục Thư mục là nơi để lưu giữ tập các file Để lưu trữ dãy các tập tin, hệ thống quản lý tập tin cung cấp thư mục, mà trong nhiều hệ thống có thể coi như là tập tin. Hệ thống thư mục theo cấp bậc Một thư mục thường thường chứa một số entry, mỗi entry cho một tập tin. Mỗi entry chứa tên tập tin, thuộc tính và địa chỉ trên đĩa lưu dữ liệu hoặc một entry chỉ chứa tên tập tin và một con trỏ, trỏ tới một cấu trúc, trên đó có thuộc tính và vị trí lưu trữ của tập tin. Khi một tập tin được mở, hệ điều hành tìm trên thư mục của nó cho tới khi tìm thấy tên của tập tin được mở. Sau đó nó sẽ xác định thuộc tính cũng như địa chỉ lưu trữ trên đĩa và đưa vào một bảng trong bộ nhớ. Những truy xuất sau đó thực hiện trong bộ nhớ chính. Số lượng thư mục trên mỗi hệ thống là khác nhau. Thiết kế đơn giản nhất là hệ thống chỉ có thư mục đơn(còn gọi là thư mục một cấp), chứa tất cả các tập tin của tất cả người dùng, cách này dễ tổ chức và khai thác nhưng cũng dễ gây ra khó khăn khi có nhiều người sử dụng vì sẽ có nhiều tập tin trùng tên. Ngay cả trong trường hợp chỉ có một người sử dụng, nếu có nhiều tập tin thì việc đặt tên cho một tập tin mới không trùng lắp là một vấn đề khó. Cách thứ hai là có một thư mục gốc và trong đó có nhiều thư mục con, trong mỗi thư mục con chứa tập tin của người sử dụng (còn gọi là thư mục hai cấp), cách này tránh được trường hợp xung đột tên nhưng cũng còn khó khăn với người dùng có nhiều tập tin. Người sử dụng luôn muốn nhóm các ứng dụng lại một cách logic. Từ đó, hệ thống thư mục theo cấp bậc (còn gọi là cây thư mục) được hình thành với mô hình một thư mục có thể chứa tập tin hoặc một thư mục con và cứ tiếp tục như vậy hình thành cây thư mục như trong các hệ điều hành DOS, Windows, v. v Ngoài ra, trong một số hệ điều hành nhiều người dùng, hệ thống còn xây dựng các hình thức khác của cấu trúc thư mục như cấu trúc thư mục theo đồ thị có chu trình và cấu trúc thư mục theo đồ thị tổng quát. Các cấu trúc này cho phép các người dùng trong hệ thống có thể liên kết với nhau thông qua các thư mục chia sẻ. 121
Nguyên lý hệ điều hành Hình 6.1 Hình 6.2 Hệ thống thư mục theo cấp bậc Đường dẫn : Khi một hệ thống tập tin được tổ chức thành một cây thư mục, có hai cách để xác định một tên tập tin. Cách thứ nhất là đường dẫn tuyệt đối, mỗi tập tin được gán một đường dẫn từ thư mục gốc đến tập tin. Ví dụ : /usr/ast/mailbox. Dạng thứ hai là đường dẫn tương đối, dạng này có liên quan đến một khái niệm là thư mục hiện hành hay thư mục làm việc. Người sử dụng có thể quy định một thư mục là thư mục hiện hành. Khi đó đường dẫn không bắt đầu từ thư mục gốc mà liên 122
Nguyên lý hệ điều hành quan đến thư mục hiện hành. Ví dụ, nếu thư mục hiện hành là /usr/ast thì tập tin với đường dẫn tuyệt đối /usr/ast/mailbox có thể được dùng đơn giản là mailbox. Trong phần lớn hệ thống, mỗi tiến trình có một thư mục hiện hành riêng, khi một tiến trình thay đổi thư mục làm việc và kết thúc, không có sự thay đổi để lại trên hệ thống tập tin. Nhưng nếu một hàm thư viện thay đổi đường dẫn và sau đó không đổi lại thì sẽ có ảnh hưởng đến tiến trình. Hầu hết các hệ điều hành đều hỗ trợ hệ thống thư mục theo cấp bậc với hai entry đặc biệt cho mỗi thư mục là "." và " ". "." chỉ thư mục hiện hành, " " chỉ thư mục cha. Các thao tác trên thư mục : Tạo : một thư mục được tạo, nó rỗng, ngoại trừ "." và " " được đặt tự động bởi hệ thống. Xóa :xoá một thư mục, chỉ có thư mục rỗng mới bị xóa, tư mục chứa "." và " " coi như là thư mục rỗng. Mở thư mục :thư mục có thể được đọc. Ví dụ để liệt kê tất cả tập tin trong một thư mục, chương trình liệt kê mở thư mục và đọc ra tên của tất cả tập tin chứa trong đó. Trước khi thư mục được đọc, nó phải được mở ra trước. Đóng thư mục :khi một thư mục đã được đọc xong, phải đóng thư mục để giải phóng vùng nhớ. Đọc thư mục :Lệnh này trả về entry tiếp theo trong thư mục đã mở. Thông thường có thể đọc thư mục bằng lời gọi hệ thống READ, lệnh đọc thư mục luôn luôn trả về một entry dưới dạng chuẩn . Đổi tên :cũng như tập tin, thư mục cũng có thể được đổi tên. Liên kết :kỹ thuật này cho phép một tập tin có thể xuất hiện trong nhiều thư mục khác nhau. Khi có yêu cầu, một liên kết sẽ được tạo giữa tập tin và một đường dẫn được cung cấp. Bỏ liên kết :Nếu tập tin chỉ còn liên kết với một thư mục, nó sẽ bị loại bỏ hoàn toàn khỏi hệ thống, nếu nhiều thì nó bị giảm chỉ số liên kết. 6.3 Các phương pháp lưu giữ file Định vị liên tiếp : Lưu trữ tập tin trên dãy các khối liên tiếp. Phương pháp này có 2 ưu điểm : thứ nhất, dể dàng cài đặt. Thứ hai, dể dàng thao tác vì toàn bộ tập tin được đọc từ đĩa bằng thao tác đơn giản không cần định vị lại. 123
Nguyên lý hệ điều hành Phương pháp này cũng có 2 khuyết điểm : không linh động trừ khi biết trước kích thước tối đa của tập tin. Sự phân mảnh trên đĩa, gây lãng phí lớn. Định vị bằng danh sách liên kết : Hình 6.3 Định vị bằng danh sách liên kết Mọi khối đều được cấp phát, không bị lãng phí trong trường hợp phân mảnh và directory entry chỉ cần chứa địa chỉ của khối đầu tiên. Tuy nhiên khối dữ liệu bị thu hẹp lại và truy xuất ngẫu nhiên sẽ chậm. Danh sách liên kết sử dụng index : Tương tự như hai nhưng thay vì dùng con trỏ thì dùng một bảng index. Khi đó toàn bộ khối chỉ chứa dữ liệu. Truy xuất ngẫu nhiên sẽ dễ dàng hơn. Kích thước tập tin được mở rộng hơn. Hạn chế là bản này bị giới hạn bởi kích thước bộ nhớ . 124
Nguyên lý hệ điều hành Hình 6.4 Bảng chỉ mục của danh sách liên kết I-nodes : Một I-node bao gồm hai phần. Phần thứ nhất là thuộc tính của tập tin. Phần này lưu trữ các thông tin liên quan đến tập tin như kiểu, người sở hữu, kích thước, v.v Phần thứ hai chứa địa chỉ của khối dữ liệu. Phần này chia làm hai phần nhỏ. Phần nhỏ thứ nhất bao gồm 10 phần tử, mỗi phần tử chứa địa chỉ khối dữ liệu của tập tin. Phần tử thứ 11 chứa địa chỉ gián tiếp cấp 1 (single indirect), chứa địa chỉ của một khối, trong khối đó chứa một bảng có thể từ 210 đến 232 phần tử mà mỗi phần tử mới chứa địa chỉ của khối dữ liệu. Phần tử thứ 12 chứa địa chỉ gián tiếp cấp 2 (double indirect), chứa địa chỉ của bảng các khối single indirect. Phần tử thứ 13 chứa địa chỉ gián tiếp cấp 3 (double indirect), chứa địa chỉ của bảng các khối double indirect. Cách tổ chức này tương đối linh động. Phương pháp này hiệu quả trong trường hợp sử dụng để quán lý những hệ thống tập tin lớn. Hệ điều hành sử dụng phương pháp này là Unix (Ví dụ : BSD Unix) 125
Nguyên lý hệ điều hành Hình 6.5 Cấu trúc của I-node 6.4 Các yêu cầu quản lý file. - Người sử dụng có thể dễ dàng tạo, sửa, thêm, bớt, xoá file. - Người sử dụng có thể chia sẻ file cho người sử dụng khác - Người sử dụng có thể truyền thông tin giữa các file lẫn nhau. - Người sử dụng có thể lấy lại, lưu giữ file một cách dễ dàng. - Người sử dụng có thể ngăn chặn các hành vi xâm phạm đến file và thực hiện được chế độ bảo vệ file. - Có giao diện sử dụng file dễ dàng. 6.5 Các thao tác file Tạo : một tập tin được tạo chưa có dữ liệu. Mục tiêu của chức năng này là thông báo cho biết rằng tập tin đã tồn tại và thiết lập một số thuộc tính. Xóa :khi một tập tin không còn cần thiết nữa, nó được xóa để tăng dung lượng đĩa. Một số hệ điều hành tự động xoá tập tin sau một khoảng thời gian n ngày. 126
Nguyên lý hệ điều hành Mở : trước khi sử dụng một tập tin, tiến trình phải mở nó. Mục tiêu của mở là cho phép hệ thống thiết lập một số thuộc tính và địa chỉ đĩa trong bộ nhớ để tăng tốc độ truy xuất. Đóng : khi chấm dứt truy xuất, thuộc tính và địa chỉ trên đĩa không cần dùng nữa, tập tin được đóng lại để giải phóng vùng nhớ. Một số hệ thống hạn chế tối đa số tập tin mở trong một tiến trình. Đọc : đọc dữ liệu từ tập tin tại vị trí hiện thời của đầu đọc, nơi gọi sẽ cho biết cần bao nhiêu dữ liệu và vị trí của buffer lưu trữ nó. Ghi : ghi dữ liệu lên tập tin từ vị trí hiện thời của đầu đọc. Nếu là cuối tập tin,kích thước tập tin sẽ tăng lên, nếu đang ở giữa tập tin, dữ liệu sẽ bị ghi chồng lên. Thêm : gần giống như WRITE nhưng dữ liệu luôn được ghi vào cuối tập tin. Tìm :dùng để truy xuất tập tin ngẫu nhiên. Khi xuất hiện lời gọi hệ thống, vị trí con trỏ đang ở vị trí hiện hành được di chuyển tới vị trí cần thiết. Sau đó dữ liệu sẽ được đọc ghi tại vị trí này. Lấy thuộc tính :lấy thuộc tính của tập tin cho tiến trình Thiết lập thuộc tính :thay đổi thuộc tính của tập tin sau một thời gian sử dụng. Đổi tên :thay đổi tên của tập tin đã tồn tại. 6.6 Tổ chức file, truy nhập file Cấu trúc của tập tin : Gồm 3 loại : Dãy tuần tự các byte không cấu trúc : hệ điều hành không biết nội dung của tập tin:MS-DOS và UNIX sử dụng loại này. Dãy các record có chiều dài cố định. Cấu trúc cây : gồm cây của những record, không cần thiết có cùng độ dài, mỗi record có một trường khóa giúp cho việc tìm kiếm nhanh hơn. Tập tin lưu trữ các thông tin. Khi tập tin được sử dụng, các thông tin này được đưa vào bộ nhớ của máy tính. Có nhiều cách để truy xuất chúng. Một số hệ thống cung cấp chỉ một phương pháp truy xuất, một số hệ thống khác, như IBM chẳng hạn cho phép nhiều cách truy xuất. Kiểu truy xuất tập tin đơn giản nhất là truy xuất tuần tự . Tiến trình đọc tất cả các byte trong tập tin theo thứ tự từ đầu. Các trình soạn thảo hay trình biên dịch cũng truy xuất tập tin theo cách này. Hai thao tác chủ yếu trên tập tin là đọc và ghi. Thao tác đọc 127
Nguyên lý hệ điều hành sẽ đọc một mẫu tin tiếp theo trên tập tin và tự động tăng con trỏ tập tin. Thao tác ghi cũng tương tự như vậy. Tập tin có thể tự khởi động lại từ vị trí đầu tiên và trong một số hệ thống tập tin cho phép di chuyển con trỏ tập tin đi tới hoặc đi lui n mẫu tin. Truy xuất kiểu này thuận lợi cho các loại băng từ và cũng là cách truy xuất khá thông dụng. Truy xuất tuần tự cần thiết cho nhiều ứng dụng. Có hai cách truy xuất. Cách truy xuất thứ nhất thao tác đọc bắt đầu ở vị trí đầu tập tin, cách thứ hai có một thao tác đặc biệt gọi là SEEK cung cấp vị trí hiện thời làm vị trí bắt đầu. Sau đó tập tin được đọc tuần tự từ vị trí bắt đầu. Hình 6.6 Truy xuất tuần tự trên tập tin Một kiểu truy xuất khác là truy xuất trực tiếp. Một tập tin có cấu trúc là các mẫu tin logic có kích thước bằng nhau, nó cho phép chương trình đọc hoặc ghi nhanh chóng mà không cần theo thứ tự. Kiểu truy xuất này dựa trên mô hình của đĩa. Đĩa cho phép truy xuất ngẫu nhiên bất kỳ khối dữ liệu nào của tập tin. Truy xuất trực tiếp được sử dụng trong trường hợp phải truy xuất một khối lượng thông tin lớn như trong cơ sở dữ liệu chẳng hạn. Ngoài ra còn có một số cách truy xuất khác dự trên kiểu truy xuất này như truy xuất theo chỉ mục 6.7 Độ an toàn của hệ thống file Một hệ thống tập tin bị hỏng còn nguy hiểm hơn máy tính bị hỏng vì những hư hỏng trên thiết bị sẽ ít chi phí hơn là hệ thống tập tin vì nó ảnh hưởng đến các phần mềm trên đó. Hơn nữa hệ thống tập tin không thể chống lại được như hư hòng do phần cứng gây ra, vì vậy chúng phải cài đặt một số chức năng để bảo vệ. Quản lý khối bị hỏng Đĩa thường có những khối bị hỏng trong quá trình sử dụng đặc biệt đối với đĩa cứng vì khó kiểm tra được hết tất cả. Có hai giải pháp : phần mềm và phần cứng. Phần cứng là dùng một sector trên đĩa để lưu giữ danh sách các khối bị hỏng. Khi bộ kiểm soát tực hiện lần đầu tiên, nó đọc những khối bị hỏng và dùng một khối thừa để lưu giữ. Từ đó không cho truy cập những khối hỏng nữa. 128
Nguyên lý hệ điều hành Phần mềm là hệ thống tập tin xây dựng một tập tin chứa các khối hỏng. Kỹ thuật này loại trừ chúng ra khỏi danh sách các khối trống, do đó nó sẽ không được cấp phát cho tập tin. Backup Mặc dù có các chiến lưọc quản lý các khối hỏng, nhưng một công việc hết sức quan trọng là phải backup tập tin thường xuyên. Tập tin trên đĩa mềm được backup bằng cách chép lại toàn bộ qua một đĩa khác. Dữ liệu trên đĩa cứng nhỏ thì được backup trên các băng từ. Đối với các đĩa cứng lớn, việc backup thường được tiến hành ngay trên nó. Một chiến lược dể cài đặt nhưng lãng phí một nữa đĩa là chia đĩa cứng làm hai phần một phần dữ liệu và một phần là backup. Mỗi tối, dữ liệu từ phần dữ liệu sẽ được chép sang phần backup. Hình 6.7 Backup Tính không đổi của hệ thống tập tin Một vấn đề nữa về độ an toàn là tính không đổi. Khi truy xuất một tập tin, trong quá trình thực hiện, nếu có xảy ra những sự cố làm hệ thống ngừng hoạt động đột ngột, lúc đó hàng loạt thông tin chưa được cập nhật lên đĩa. Vì vậy mỗi lân khởi động ,hệ thống sẽ thực hiện việc kiểm tra trên hai phần khối và tập tin. Việc kiểm tra thực hiện , khi phát hiện ra lỗi sẽ tiến hành sữa chữa cho các trường hợp cụ thể: 129
Nguyên lý hệ điều hành Hình 6.8 Trạng thái của hệ thống tập tin 130
Nguyên lý hệ điều hành Tài liệu tham khảo: [1] “Tập slide bài giảng”. [2] “Operating System Concepts”. A. Silberschatz, P. B. Galvin, G. Gagne, Wiley & Sons, 2002. [3] “Operating Systems”, H. M. Deitel, P. J. Deitel and D. R. Choffnes, Pearson Education International, 2004. [4] “Modern Operating Systems”. Andrew S. Tanenbaum, Prentice-Hall International, 2001. [5] “Operating Systems – Internals and Design Principles”. William Stallings, Pearson Education International, 2005. 131