Hệ Điều Hành

Posted Nov 29, 2024 Updated Dec 25, 2024

By Bui Quang Dat

61 min read

Hệ Điều Hành

Hệ điều hành (Operating System - OS) là phần mềm hệ thống quản lý phần cứng và tài nguyên của máy tính, đồng thời cung cấp môi trường cho các phần mềm ứng dụng hoạt động. Nó đóng vai trò trung gian giữa người dùng và phần cứng, thực hiện các chức năng như quản lý bộ nhớ, xử lý, lưu trữ, thiết bị ngoại vi và cung cấp giao diện người dùng. Ví dụ về hệ điều hành bao gồm Windows, macOS, Linux, và Android.

Chương 1: Giới thiệu chung

I. Các thành phần của hệ thống máy tính

Một hệ thống máy tính nói chung được phân chia thành phần cứng và phần mềm.

Phần cứng: Cung cấp các tài nguyên cần thiết cho việc tính toán, xử lý dữ liệu.

Phần mềm: Các chương trình cụ thể (phần mềm hệ thống và phần mềm ứng dụng).

Hệ điều hành: Phần mềm đóng vai trò trung gian giữa phần cứng và người sử dụng chương trình ứng dụng, làm cho việc sử dụng hệ thống máy tính được tiện lợi và hiệu quả.

II. Khái niệm hệ điều hành

Hệ Điều Hành được định nghĩa thông qua mục đích, vai trò, và chức năng trong hệ thống máy tính

Hệ Điều Hành là hệ thống phần mềm đóng vai trò trung gian giữa người sử dụng và phần cứng của máy tính nhằm thực hiện 2 chức năng cơ bản:

Quản lý tài nguyên.
Quản lý việc thực hiện các chương trình.

Quản lý tài nguyên

Hệ điều hành đảm bảo cho tài nguyên hệ thống được sử dụng một cách có ích và hiệu quả.

Các tài nguyên: bộ xử lý (CPU), bộ nhớ chính, bộ nhớ ngoài (các đĩa), các thiết bị vào ra.

Phân phối tài nguyên cho các ứng dụng hiệu quả:

Yêu cầu tài nguyên được HDH thu nhận và đáp ứng bằng cách cấp cho chương trình các tài nguyên tương ứng.
HDH cần lưu trữ tình trạng tài nguyên.

Đảm bảo không xâm phạm tài nguyên cấp cho chương trình khác.

Ví dụ: Lưu trữ thông tin trên đĩa => HDH cần biết những vùng nào trên đĩa chưa được sử dụng để ghi thông tin lên những vùng này. Việc ghi thông tin cũng cần tính toán sao cho quá trình truy cập khi cần có thể thực hiện nhanh nhất.

Quản lý việc thực hiện các chương trình

Nhiệm vụ quan trọng nhất của máy tính là thực hiện các chương trình, 1 chương trình đang trong quá trình chạy gọi là tiến trình (process).

Chương trình cần được quản lý để thực hiện thuận lợi, tránh lỗi, đồng thời đảm bảo môi trường để việc xây dựng và thực hiện chương trình được thuận lợi.

Để chạy chương trình cần thực hiện một số thao tác nhất định => HĐH giúp việc chạy chương trình dễ dàng hơn, người dùng không cần phải thực hiện thao tác.

Để tạo môi trường thuận lợi cho chương trình, HĐH tạo ra các máy ảo:

Là máy logic với các tài nguyên ảo
Tài nguyên ảo mô phỏng tài nguyên thực được thực hiện bằng phần mềm
Cung cấp các dịch vụ cơ bản như tài nguyên thực
Dễ sử dụng hơn, số lượng tài nguyên ảo có thể lớn hơn số lượng tài nguyên thực.

Một số máy ảo tốt nhất hiện nay: VirtualBox (Windows/Mac/Linux); Parallels (Windows/Mac/Linux); VMware(Windows/Linux, Basic); QEMU (Linux); Boot Camp (Windows/macOS); Windows Virtual PC (Windows).

Câu hỏi ôn tập

Trình bày về các thành phần của hệ thống máy tính và vai trò của hệ điều hành trong đó.

Xem đáp án

💻 Đáp án:
Các thành phần của hệ thống máy tính và vai trò của hệ điều hành:

Phần cứng: Đây là các tài nguyên vật lý cần thiết cho việc tính toán và xử lý dữ liệu, bao gồm CPU, bộ nhớ, và các thiết bị ngoại vi.
Phần mềm: Bao gồm các chương trình cụ thể, được chia thành phần mềm hệ thống và phần mềm ứng dụng.
Hệ điều hành: Đóng vai trò trung gian giữa phần cứng và người sử dụng chương trình ứng dụng. Nó giúp việc sử dụng hệ thống máy tính trở nên tiện lợi và hiệu quả hơn. Hệ điều hành quản lý tài nguyên và cung cấp môi trường cho các phần mềm ứng dụng hoạt động.

Trình bày khái niệm hệ điều hành. Phân tích rõ hai chức năng cơ bản của hệ điều hành.

Xem đáp án

💻 Đáp án:
Khái niệm hệ điều hành và hai chức năng cơ bản:

Khái niệm: Hệ điều hành là hệ thống phần mềm đóng vai trò trung gian giữa người sử dụng và phần cứng của máy tính. Nó thực hiện hai chức năng cơ bản là quản lý tài nguyên và quản lý việc thực hiện các chương trình.
Quản lý tài nguyên: Hệ điều hành đảm bảo rằng các tài nguyên hệ thống như CPU, bộ nhớ chính, bộ nhớ ngoài, và các thiết bị vào ra được sử dụng một cách hiệu quả. Nó phân phối tài nguyên cho các ứng dụng, lưu trữ tình trạng tài nguyên, và đảm bảo không có sự xâm phạm tài nguyên giữa các chương trình.
Quản lý việc thực hiện các chương trình: Hệ điều hành giúp quản lý các chương trình đang chạy (tiến trình) để đảm bảo chúng hoạt động thuận lợi và tránh lỗi. Nó tạo ra các máy ảo để cung cấp môi trường thuận lợi cho việc xây dựng và thực hiện chương trình, giúp người dùng không cần thực hiện các thao tác phức tạp khi chạy chương trình. Máy ảo cung cấp các tài nguyên ảo mô phỏng tài nguyên thực, dễ sử dụng và có thể có số lượng lớn hơn tài nguyên thực.

III. Các dịch vụ do hệ điều hành cung cấp

Một trong những nhiệm vụ chủ yếu của HDH là tạo ra môi trường thuận lợi cho các chương trình khác thực hiện và giúp người sử dụng hệ thống dễ dàng.

Các dịch vụ có thể thay đổi theo từng HDH. Một số HDH có thể cung cấp nhiều dịch vụ khi hệ điều hành khác có thể cung cấp ít dịch vụ hơn.

Ví dụ như MS-DOS không cung cấp dịch vụ về bảo mật trong khi Windows NT lại rất chú trọng tới dịch vụ này.

Một số dịch vụ thường gặp của hệ điều hành:

Tải và chạy chương trình:
- Để thực hiện, chương trình được tải từ đĩa vào bộ nhớ, sau đó được trao quyền thực hiện các lệnh. Khi thực hiện xong, cần giải phóng bộ nhớ và các tài nguyên
- Toàn bộ quá trình này tương đối phức tạp song lại diễn ra thường xuyên.
=> HDH sẽ thực hiện công việc phức tạp và lặp đi lặp lại này
- Do HDH là chương trình đầu tiên được thực hiện khi khởi động hệ thống nên HDH tự tải mình vào bộ nhớ
- Nhờ có HĐH, lập trình viên, người sử dụng không cần quan tâm chi tiết đến việc tải và chạy chương trình.
Giao diện với người dùng (cho phép giao tiếp giữa HDH và người dùng):
- Dưới dạng dòng lệnh (command-line): cho phép người dùng chỉ thị cho HĐH bằng cách gõ lệnh dưới dạng văn bản. Ví dụ: chtr cmd.exe của Windows.
- Giao diện đồ họa (Graphic User Interface-GUI): sử dựng hệ thống cửa sổ, thực đơn và thiết bị trỏ chuột, kết hợp với bàn phím để giao tiếp với hệ thống.
Thực hiện các thao tác vào/ ra dữ liệu:
- Người dùng và chương trình trong khi thực hiện có thể có nhu cầu I/O dữ liệu với các đĩa và thiết bị ngoại vi. Để tránh cho chương trình không phải làm việc với phần cứng, yêu cầu I/O sẽ được giao cho hệ điều hành thực hiện.
Làm việc với hệ thống file:
- Nhu cầu đọc, ghi, tạo, xóa, chép file hoặc làm việc với thư mục; quản lý quyền truy cập, sao lưu.
Phát hiện và xử lý lỗi:
- Phát hiện và xử lý kịp thời các lỗi xuất hiện trong phần cứng cũng như phần mềm => Đảm bảo cho hệ thống hoạt động ổn định, an toàn
- Ví dụ: các lỗi phần cứng như hết bộ nhớ, mất điện, máy in hết mực, hết giấy,..
Truyền thông:
- Cung cấp dịch vụ cho phép thiết lập liên lạc và truyền thông tin dưới dạng thông điệp hoặc qua BN dùng chung.
Cấp phát tài nguyên:
- Trong các hệ thống cho phép nhiều chương trình thực hiện đồng thời cần có cơ chế cấp phát và phân phối tài nguyên hợp lý => nhờ có HĐH, người dùng và trình ứng dụng không phải tự thực hiện việc cấp phát tài nguyên mà vẫn đảm bảo cấp phát công bằng và hiệu quả.
Dịch vụ an ninh và bảo mật:
- Đối với hệ thống nhiều người dùng thường xuất hiện yêu cầu bảo mật thông tin, tức là người dùng này không tiếp cận được thông tin của người khác nếu không được cho phép.
- Cần đảm bảo để tiến trình không truy cập trái phép tài nguyên (như vùng nhớ, file mở) của tiến trình khác hay chính HDH sẽ thực hiện bằng cách kiểm soát truy cấp tới tài nguyên

Câu hỏi ôn tập

Dựa trên định nghĩa hệ điều hành, hãy cho biết trình duyệt Web có thể là một thành phần của hệ điều hành không ?

Xem đáp án

💻 Đáp án:

Dựa trên định nghĩa của hệ điều hành, trình duyệt web không phải là một thành phần của hệ điều hành. Hệ điều hành là phần mềm hệ thống quản lý phần cứng và tài nguyên của máy tính, đồng thời cung cấp môi trường cho các phần mềm ứng dụng hoạt động. Nó thực hiện các chức năng như quản lý bộ nhớ, xử lý, lưu trữ, thiết bị ngoại vi và cung cấp giao diện người dùng.

Trình duyệt web, ngược lại, là một phần mềm ứng dụng chạy trên hệ điều hành. Nó cho phép người dùng truy cập và tương tác với nội dung trên internet. Mặc dù trình duyệt web có thể được tích hợp sâu vào hệ điều hành (như Internet Explorer trong các phiên bản Windows trước đây), nó vẫn không thực hiện các chức năng quản lý tài nguyên hệ thống như một hệ điều hành thực thụ. Thay vào đó, nó phụ thuộc vào hệ điều hành để truy cập tài nguyên phần cứng và thực hiện các tác vụ cơ bản.

Có phải bất kỳ hệ thống máy tính nào cũng có hệ điều hành không ? Tại sao ? Ở đây, hệ thống máy tính được hiểu rộng là bất cứ hệ thống nào có vi xử lý và bộ nhớ

Xem đáp án

💻 Đáp án:

Không phải bất kỳ hệ thống máy tính nào cũng có hệ điều hành. Hệ điều hành là phần mềm hệ thống được thiết kế để quản lý phần cứng và tài nguyên của máy tính, đồng thời cung cấp môi trường cho các phần mềm ứng dụng hoạt động. Tuy nhiên, có những hệ thống máy tính đơn giản hoặc chuyên dụng không cần đến hệ điều hành.

Ví dụ, các thiết bị nhúng như lò vi sóng, máy giặt, hoặc các thiết bị IoT (Internet of Things) thường có vi xử lý và bộ nhớ nhưng không sử dụng hệ điều hành phức tạp như máy tính cá nhân. Thay vào đó, chúng chạy các chương trình đơn giản được thiết kế đặc biệt cho nhiệm vụ của chúng.

Trong những trường hợp này, phần mềm được viết trực tiếp để điều khiển phần cứng mà không cần một lớp trung gian như hệ điều hành. Điều này giúp giảm chi phí và tăng hiệu suất cho các thiết bị có tài nguyên hạn chế.

IV. Giao diện lập trình của HDH

Để các chương trình có thể sử dụng được những dịch vụ, HDH cung cấp giao diện lập trình.

Giao diện này bao gồm các lời gọi hệ thống (system call) mà chương trình sử dụng yêu cầu một dịch vụ nào đó từ phía HDH.

Lời gọi hệ thống: các lệnh đặc biệt mà CTUD gọi khi cần yêu cầu HDH thực hiện một việc gì đó

Lời gọi hệ thống được thực hiện qua những thư viện hàm gọi là thư viện hệ thống. Các hàm này sẽ giúp người lập trình gọi lời gọi hệ thống tương ứng của hệ điều hành

V. Quá trình phát triển

Các hệ thống đơn giản (những năm 40-50 của thế kỷ trước): tốc độ xử lý của máy tính rất thấp, việc vào/ra được thực hiện thủ công và khó khăn.

Việc nạp chương trình được thực hiện nhờ công tắc, mạch hàn sẵn, bìa đục lỗ. Trong thời kỳ này, lập trình viên tương tác trực tiếp với phần cứng.

=> Máy tính thời kỳ này chưa có HDH.

Xử lý theo mẻ:

Chương trình được phân thành các mẻ: gồm những chương trình có yêu cầu giống nhau
Toàn bộ mẻ được nạp vào băng từ và được tải vào máy để thực hiện lần lượt

Chương trình giám sát (monitor): mỗi khi một chương trình của mẻ kết thúc, chương trình giám sát tự động nạp chương trình tiếp theo vào máy và cho phép nó chạy => Giảm đáng kể thời gian chuyển đổi giữa hai chương trình trong cùng một mẻ.

Trình giám sát là dạng đơn giản nhất của HDH

Ưu điểm: tăng và tận dụng hết công suất máy, giảm thời gian chờ đợi càng nhiều càng tốt.

Đa chương trình (đa nhiệm):

Hệ thống chứa đồng thời nhiều chương trình trong bộ nhớ.
Khi một chương trình phải dừng lại để thực hiện vào ra, HDH sẽ chuyển CPU sang thực hiện một chương trình khác.

=> Giảm thời gian chạy không tải của CPU.

Đa chương trình

Thời gian chờ đợi của CPU trong chế độ đa chương trình giảm đáng kể so với trong trường hợp đơn chương trình.
HDH phức tạp hơn rất nhiều so với HDH đơn chương trình.
Đòi hỏi hỗ trợ từ phần cứng, đặc biệt khả năng vào/ra bằng ngắt và cơ chế DMA.

Đa chương trình (Hạn chế)

Mặc dù đa chương trình cho phép sử dụng hiệu quả CPU và các tài nguyên khác của hệ thống song kỹ thuật này không cho người dùng tương tác với hệ thống.
Các máy tính thế hệ sau cho phép máy tính và người dùng làm việc trực tiếp thông quan màn hình và bàn phím.
Đối với các hệ thống này thì thời gian từ khi người dùng gõ lệnh cho tới khi máy tính phản xạ lại tương đối nhỏ.
Kỹ thuật đa chương trình không đảm bảo được thời gian đáp ứng ngắn như vậy.

Chia sẻ thời gian

Chia sẻ thời gian có thể coi như đa chương trình cải tiến
CPU lần lượt thực hiện các công việc khác nhau trong những khoảng thời gian ngắn gọi là lượng tử thời gian
Chuyển đổi giữa các công việc diễn ra với tần số cao và tốc độ CPU lớn
=> Tất cả người dùng đều có cảm giác máy tính chỉ thực hiện chương trình của mình.

=> CPU được chia sẻ giữa những người dùng khác nhau tương tác trực tiếp với hệ thống.

VI.Cấu trúc HDH

Các thành phần

Quản lý tiến trình:

Một chương trình đang trong quá trình thực hiện được gọi là tiến trình.
Tạo và xoá tiến trình (bao gồm cả tiến trình người dùng và tiến trình hệ thống).
Tạm treo và khôi phục các tiến trình bị treo.
Đồng bộ hoá các tiến trình (lập lịch cho các tiến trình.v.v.).
Tạo cơ chế liên lạc giữa các tiến trình.
Giải quyết các bế tắc, ví dụ như khi có xung đột về tài nguyên.
Bế tắc: là chương trình đang cần tài nguyên những nó chờ đợi mà không được cung cấp.

Quản lý bộ nhớ:

Quản lý, cung cấp và giải phóng.
Cung cấp và giải phóng bộ nhớ theo yêu cầu của các tiến trình.
Quản lý không gian nhớ đã được cấp và không gian còn trống.
Quản lý việc phân phối bộ nhớ giữa các tiến trình => đảm bảo việc chạy song song giữa nhiều chương trình.
Tạo ra bộ nhớ ảo và ánh xạ địa chỉ bộ nhớ ảo vào bộ nhớ thực.

Quản lý hệ thống vào ra:

Quản lý thông qua các chương trình điều khiển
Đơn giản hoá và tăng hiệu quả quá trình trao đổi thông tin giữa các tiến trình với thiết bị vào ra

Quản lý file và thư mục:

Tạo, xóa file và thư mục
Đọc ghi file
Ánh xạ file và thư mục sang bộ nhớ ngoài

Hỗ trợ mạng và xử lý phân tán:

Quản lý thiết bị mạng
Hỗ trợ các giao thức truyền thông
Quản lý truyền thông, cân bằng tải => Thông qua các thành phần điều khiển, giao tiếp mạng.

Giao diện với người dùng:

Đó là hệ thống thông dịch lệnh
Giúp cho máy tính hiểu và xử lý được các chỉ thị, các lệnh của người dùng.
Ví dụ: bash của Linux, command của window

Các chương trình tiện ích và ứng dụng.

Nhân của HDH

HDH gồm rất nhiều thành phần, tuy nhiên độ quan trọng của các thành phần khác nhau, có những thành phần không thể thiếu là cơ sở cho toàn hệ thống hoạt động, một số thành phần của HDH cung cấp chức năng kém quan trọng hơn.

=> chỉ tải những thành phần quan trọng không thể thiếu được vào bộ nhớ gọi là nhân.

Nhân (kernel) là phần cốt lõi, thực hiện các chức năng cơbản nhất, quan trọng nhất của HDH và thường xuyên được giữ trong bộ nhớ

Kernel có nhiệm vụ quản lý tài nguyên hệ thống (liên lạc giữa các thành phần phần cứng và phần mềm)

Máy tính hiện đại thường được thiết kế với hai chế độ thực hiện chương trình.

Nhân chạy trong chế độ đặc quyền – chế độ nhân: là chế độ mà chương trình thực hiện trong đó có đầy đủ quyền truy cập và điều khiển phần cứng máy tính.
Chế độ người dùng: chương trình thực hiện trong chế độ người dùng bị hạn chế rất nhiều quyền truy cập và sử dụng phần cứng.

Việc phân biệt chế độ nhân và chế độ người dùng nhằm mục đích ngăn không cho CTUD vô tình hoặc cố ý thực hiện những thao tác làm ảnh hưởng tới hệ thống.

Một số cấu trúc HDH.

Cấu trúc nguyên khối:

Toàn bộ chương trình và dữ liệu của HĐH có chung 1 không gian nhớ. Do vậy, có thể coi là một khối duy nhất.
HĐH trở thành một tập hợp các thủ tục hay các chương trình con
Ưu điểm: Nhanh, không mất thời gian giữa các không gian nhớ
Nhược điểm: Không an toàn, khi bất kỳ thành phần nào có sự cố thì toàn bộ hệ thống sẽ không hoạt động đc; Ko mềm dẻo và khó sửa đổi, thêm bớt thành phần nào sẽ ảnh hưởng tới toàn bộ hệ thống, khi có lỗi khó xác định lỗi do thành phần nào gây ra.

Cấu trúc phân lớp:

Các thành phần được chia thành các lớp nằm chồng lên nhau
Mỗi lớp chỉ có thể liên lạc với lớp nằm kề bên trên và kề bên dưới
Mỗi lớp chỉ có thể sử dụng dịch vụ do lớp nằm ngay bên dưới cung cấp
Ưu điểm: chia nhỏ chức năng, dễ sử dụng, dễ sửa lỗi
Nhược điểm: khó thiết kế (xác định số lớp, phân chia thành phần các chức năng của mỗi lớp), tốc độ chậm hơn cấu trúc nguyên khối

Cấu trúc vi nhân (micro kernel):

Nhân có kích thước nhỏ, chỉ chứa các chức năng quan trọng nhất
Các chức năng còn lại được đặt vào các modul riêng: chạy trong chế độ đặc quyền hoặc người dùng. Khi có yêu cầu từ ứng dụng, nhân sẽ chuyển cho module tương ứng để xử lý và nhận lại kết quả, nhân chủ yếu đóng vai trò trung gian liên lạc.
Ưu điểm: mềm dẻo, an toàn
Nhược điểm: tốc độ chậm hơn so với cấu trúc nguyên khối

VII. Một số HDH cụ thể

UNIX

Là một hệ điều hành đa nhiệm, được phát triển đầu tiên bởi Ken Thompson, Dennis Ritchie và Douglas Mcllroy tại AT & T Bell.
UNIX được nghiên cứu tại các phòng thí nghiệm năm 1969 và dần cải tiến, phát triển và trở nên phổ biến. Unix lần đầu tiên được lập trình lại bởi Ken Thompson bằng ngôn ngữ C vào năm 1973.
Tạo ra ngôn ngữ cấp cao trong các hệ điều hành
Tạo ra hệ thống tập tin phân cấp
Unix shell đã truyền cảm hứng cho nhiều trình thông dịch dòng lệnh phát triển sau đó.
Giúp ngôn ngữ lập trình C trở nên phổ biến hơn
Góp phần vào sự ra mắt của phong trào phần mềm miễn phí

MINIX (Từ mini-Unix)

Là một hệ điều hành máy tính tựa Unix dựa trên kiến trúc micro-kernel.
Phiên bản đầu của MINIX được tạo ra bởi Andrew S.Tanenbaum cho mục đích giáo dục như minh họa, phục vụ đào tạo, có thể sử dụng miễn phí.
MINIX bây giờ phát triển như là phần mềm nguồn mở.

LINUX

Vào năm 1991 trong khi đang học tại Helsinki - Phần Lan, Linus Torvalds bắt đầu có ý tưởng về một hệ điều hành.
Do ông cũng nhận thấy hạn chế trong giấy phép của Minix chỉ cho phép việc sử dụng Minix trong giáo dục mà thôi. Ông bắt đầu viết nên hệ điều hành LINUX phát triển từ MINIX.

MS-DOS

Là sản phẩm của hãng Microsoft và được trang bị cho các máy PC đầu tiên của IBM
Để có thể chạy trên PC với tài nguyên hạn chế, MS-DOS được xây dựng đơn giản và ít chức năng hơn
Nhiều giải pháp kỹ thuật trong MS-DOS có nguồn gốc từ UNIS như giao iện lập trình (lời gọi hệ thống), cấu trúc phân cấp của thư mục, bộ dịch lệnh
Không có các chức năng như bảo mật, hỗ trợ mạng, hỗ trợ nhiều tiến trình

Windows NT

Windows NT (NT-new technology) là một thành viên của họ điều hành thế hệ mới như Windows 2000, XP, Vista,7.

Phiên bản đầu tiên được phát hành vào năm 1993
Đây là hđh sử dụng nhiều kỹ thuật tiên tiến trong lĩnh vực hđh đã được phát triển cho đến thời điểm này gồm các giải pháp lấy từ UNIX
Là một hệ điều hành đa nhiệm, hỗ trợ mạng, có các chức năng bảo mật, có giao diện đồ họa dưới dạng cửa sổ và được dùng cho cả máy PC yêu cầu độ ổn định cao.

Chương 2: Hệ thống File

Hệ thống máy tính phải có khả năng lưu lại được các thông tin, dữ liệu. Hệ thống lưu trữ của các loại máy tính cao cấp thuờng có kích thươc rất lớn nên sẽ chứa rất nhiều dữ liệu. Khi lượng dữ liệu lưu trữ quá lớn, nếu không khéo trong việc quản lý truy cập sẽ khó khăn và hao tốn thời gian. Cần có các hình thức tổ chức, sắp xếp dữ liệu một cách hợp lý và xây dựng các thuật toán tối ưu để có thể truy cập nhanh chóng, hiệu quả.

I. Các khái niệm.

File được định nghĩa như tập hợp các thông tin liên quan đến nhau được đặt tên và được lưu trữ trên bộ nhớ ngoài.

Thuộc tính của file: để quản lý file ngoài nội dung, HĐH còn định nghĩa các thuộc tính, tính chất. File có các thuộc tính như sau:

Tên file
Kiểu file
Kích thước file
Người tạo file, người sở hữu
Quyền truy cập file
Thời gian tạo file, sửa file, truy cập lần cuối
Vị trí file

Đặt tên cho file:

Cho phép xác định file.
Là thông tin người dùng thường sử dụng nhất khi làm việc với file.

Quy tắc đặt tên cho file của một số HDH:

Cấu trúc file:

Các thông tin trong file có thể rất khác nhau
Có những file chứa nhiều thông tin không có cấu trúc: file văn bản. File có cấu trúc như: file CSDL, file excel. => Cấu trúc của file cũng rất khác nhau và phụ thuộc vào thông tin chứa trong file Hỗ trợ cấu trúc file ở mức HDH:
Ưu điểm:
- Các thao tác với file sẽ dễ dàng hơn đối với người lập trình ứng dụng
- HDH có thể kiểm soát được các thao tác với file
Nhược điểm:
- Tăng kích thước hệ thống
- Tính mềm dẻo của HDH bị giảm Thực tế các HDH chỉ coi file là tập hợp các byte không cấu trúc.

Đa số HDH không hỗ trợ và quản lý kiểu cấu trúc file

Cấu trúc file do chương trình ứng dụng và người dùng tự quản lý

Trong HDH UNIX, DOS, WINDOWS, file đươc xem như tập hợp các byte.

Các chương trình ứng dụng khác nhau sẽ tự tạo ra và quản lý cấu trúc file riêng mình.

Ví dụ: chương trình đồ họa lưu file dưới dạng mã nhị phân đã được giải nén, chương trình hệ thống quản lý dữ liệu sẽ tạo ra file bao gồm các bản ghi.

II. Các phương pháp truy cập file

Để đọc/ghi file hệ điều hành phải quy định cách thức truy cập tới nội dung file. Mỗi HDH có thể hỗ trợ một hoặc nhiều cách truy cập khác nhau.

Truy cập tuần tự:

Thông tin được đọc, ghi theo từng byte/ bản ghi lần lượt từ đầu file
Sử dụng 1 con trỏ để định vị vị trí hiện thời trong file
Kiểu truy cập này phù hợp với một số thiết bị và một số thiết bị nhớ và một số ứng dụng

Truy cập trực tiếp:

File được xem như các khối/ bản ghi được đánh số
Các khối có thể truy cập theo thứ tự bất kỳ
Chẳng hạn ta có thể đọc khối 50 sau đó đọc khổi 13 rồi khối 101.
Việc truy cập trực tiếp dựa trên đặc điểm của đĩa cho phép truy cập các khối bất kỳ
File được chứa trong các khối khác nhau của đĩa do vậy cũng cho phép truy cập không tuần theo thứ tự

Truy cập dựa trên chỉ số:

Cho phép truy cập tới bản ghi trong file, không theo số thứ tự hoặc vị trí của bản ghi trong file mà theo khóa ứng với bản ghi đó.
File chứa 1 chỉ số riêng: gồm các khóa và con trỏ chỉ tới các bản ghi trong file
Truy cập: tìm khóa tương ứng trong chỉ mục, sau đó theo con trỏ xác định bản ghi và truy cập trực tiếp tới nó

III. Các thao tác với file

Tạo file:

Tạo file trống chưa có data; được dành 1 chỗ trong thư mục kèm theo một số thuộc tính như thời gian tạo file, tên file, người tạo file,… Xóa file:
Giải phóng không gian mà dữ liệu của file chiếm trên đĩa
Giải phóng chỗ của file trong thư mục
Việc giải phóng không gian có thể đơn thuần là đánh dấu không gian như không gian tự do.

Mở file:

Thực hiện trước khi ghi và đọc file
Đọc các thuộc tính của file trên đĩa vào bộ nhớ để tăng tốc độ cho thao tác đọc ghi tiếp theo.

Đóng file:

Xóa các thông tin về file ra khỏi bảng trong bộ nhớ để nhường chỗ cho các file sắp mở.
Rất nhiều hệ điều hành hạn chế số lượng file được mở cùng một lúc nên việc đóng các file đã truy cập xong là rất quan trọng.

Ghi vào file

Đọc file

IV. Thư mục

Khái niệm

Số lượng file lưu trữ trên đĩa rất lớn => phải tổ chức để dễ dàng quản lý, truy cập files

Không gian trên đĩa được chia thành các phần (partition/volume) gọi là đĩa logic

Ví dụ: trên máy tính PC có 1 ổ cứng và có thể chia thành các ổ C,D,E => đĩa logic

Để quản lý file trên các đĩa logic, thông tin về file được lưu trong thư mục của đĩa

Thư mục = ∑ các khoản mục ~ files

Khoản mục chứa các thông tin về file: tên, kích thước, vị trí, kiểu file,… hoặc con trỏ tới nơi lưu trữ thông tin này

Coi thư mục như 1 bảng, mỗi dòng là khoản mục ứng với 1

Các cách lưu thông tin về file trong thư mục:

Toàn bộ thuộc tính của file được lưu trong thư mục, file chỉ chứa data => kích thước khoản mục, thư mục lớn
Một phần thuộc tính được lưu trữ luôn cùng với dữ liệu của file.

Thư mục chỉ lưu thông tin tối thiểu cần thiết cho việc tìm kiếm vị trí file trên đĩa => kích thước giảm

Các thao tác với thư mục

Mở file:

HDH tìm trong thư mục khoản mục ứng với tên file cần mở
Đọc các thuộc tính và vị trí dữ liệu của file vào bảng chứa thông tin về các file đang mở
Nếu khoản mục trỏ tới CTDL khác chứa thuộc tính file, cấu trúc này sẽ được đọc vào bảng

Tìm kiếm file: Cấu trúc thư mục phải cho phép tìm kiếm file theo tên file

Tạo file: Tạo khoản mục mới và thêm vào thư mục

Xóa file: Thông tin về file và khoản mục tương ứng bị xóa khỏi thư mục

Duyệt thư mục: liệt kê các file trong thư mục và thông tin chứa trong khoản mục của file

Đổi tên file: chỉ cần thực hiện với thư mục chứ không liên quan đến dữ liệu của file

Cấu trúc hệ thống thư mục

Thư mục 1 mức:

Đơn giản nhất
Chỉ có 1 thư mục duy nhất và tất cả các file được giữ trong thư mục này
Khó chọn tên cho file
Tìm kiếm file khó

Thư mục 2 mức:

Phân cho mỗi người dùng 1 thư mục riêng (UFD: User File Directory), chứa các file của mình
Khi người dùng truy cập file, file sẽ được tìm kiếm trong thư mục ứng với tên người đó => các người dùng khác nhau có thể đặt tên file trùng nhau
Cô lập người dùng
Các file mà nhiều người dùng truy cập tới => chép vào từng thư mục của từng người dùng => lãng phí

Thư mục cấu trúc cây:

Thư mục con có thể chứa các thư mục con khác và các files
Hệ thống thư mục được biểu diễn phân cấp như 1 cây: cành là thư mục, lá là file

Thư mục cấu trúc cây (tt):

Phân biệt khoản mục file và khoản mục của thư mục con: thêm bit đặc biệt trong khoản mục
- 1: khoản mục của thư mục mức dưới
- 0: khoản mục của file
Tại mỗi thời điểm, người dùng làm việc với thư mục hiện thời (current directory)
Tổ chức cây thư mục cho từng đĩa:
- Trong hệ thống file như FAT của DOS, cây thư mục được xây cho từng đĩa. Hệ thống thư mục được coi là rừng, mỗi cây trên 1 đĩa
- Linux: toàn hệ thống chỉ gồm 1 cây thư mục

Thư mục cấu trúc đồ thị không tuần hoàn (acyclic graph ):

Chia sẻ files và thư mục để có thể xuất hiện ở nhiều thư mục riêng khác nhau
Mở rộng của cấu trúc
Cây: lá và cành có thể đồng thời thuộc về những cành khác nhau
Triển khai:
- Sử dụng liên kết: con trỏ tới thư mục hoặc file khác
- Tạo bản sao của file và thư mục cần chia sẻ và chứa vào các thư mục khác nhau => phải đảm bảo tính đồng bộ và nhất quán
Mềm dẻo nhưng phức tạp

Đường dẫn

Mô tả vị trí của file trong thư mục

Đường dẫn tuyệt đối:

Đường dẫn từ gốc của cây thư mục, đi qua các thư mục trung gian, dẫn tới file
C:\bc\bin\bc.exe Đường dẫn tương đối:
Tính từ thư mục hiện thời
Thêm 2 khoản mục đặc biệt trong thư mục: “.”, “..”

Tổ chức bên trong của thư mục

Danh sách:

Tổ chức thư mục dưới dạng danh sách các khoản mục
Tìm kiếm khoản mục được thực hiện bằng cách duyệt lần lượt danh sách
Thêm file mới vào thư mục:
- Duyệt cả thư mục để kiểm tra xem khoản mục với tên file như vậy đã có chưa
- Khoản mục mới được thêm vào cuối danh sách hoặc 1 ô trong bảng
Mở file, xóa file
Tìm kiếm trong danh sách chậm
Lưu trữ thư mục trong bộ nhớ

Cây nhị phân:

Tăng tốc độ tìm kiếm nhờ CTDL có hỗ trợ sắp xếp
Hệ thống file NTFS của WinNT Bảng băm (hash table):
Dùng hàm băm để tính vị trí của khoản mục trong thư mục theo tên file
Thời gian tìm kiếm nhanh
Hàm băm phụ thuộc vào kích thước của bảng băm => kích thước bảng cố định

Tổ chức thư mục của DOS:

Mỗi đĩa logic có cây thư mục riêng, bắt đầu từ thư mục gốc ROOT
Thư mục gốc được đặt ở phần đầu của đĩa, ngay sau sector khởi động BOOT và bảng FAT
Thư mục gốc chứa files và các thư mục con
Thư mục con có thể chứa files và các thư mục cấp dưới nữa
Được tổ chức dưới dạng bảng: mỗi khoản mục chiếm 1 dòng trong bảng và có kích thước cố định 32 bytes.

Tổ chức thư mục của Linux:

Thư mục hệ thống file Ext2 của Linux có cách tổ chức đơn giản
Khoản mục chứa tên file và địa chỉ I-node
Thông tin còn lại về các thuộc tính file và vị trí các khối dữ liệu được lưu trên I-node chứ không phải thư mục
Kích thước khoản mục phụ thuộc vào độ dài tên file
Phần đầu của khoản mục có trường cho biết kích thước khoản mục

V. Cấp phát không gian cho file

Nhiệm vụ quan trọng của HDH trong việc quản lý hệ thống file là cấp phát không gian trên đĩa và các hiết bị nhớ ngoài khác để lưu trữ file và thư mục. Đồng thời, ghi lại vị trí các khối nhớ đã cấp phát để có thể tiến hành truy cập về sau.

Sector hay Cung là đơn vị nhỏ nhất do chương trình điều khiển đĩa cho phép đọc hoặc ghi (khối vật lý), 1 sector = 512 byte

Cluster hay đơn vị cấp phát gồm một số khối vật lý, là đơn vị thông tin nhỏ nhất mà hệ điệu hành cấp phát cho file (khối logic) 2KB - 32 KB.

Mục đích cấp phát không gian cho file:

Tăng hiệu năng truy cập tuần tự
Dễ dàng truy cập ngẫu nhiên đến file
Dễ dàng quản lý file

Các phương pháp cấp phát không gian cho file

Cấp phát khối liên tiếp
Sử dụng danh sách kết nối
Sử dụng danh sách kết nối trên bảng chỉ số
Sử dụng khối chỉ số

Cấp phát các khối liên tiếp

Nguyên tắc: File được cấp phát các khối liên tiếp trên đĩa.
HĐH chọn 1 vùng trống có đủ số lượng khối cho file.
Bảng cấp phát xác định vị trí file gồm 1 khoản mực cho 1 file, khối bắt đầu, và số khối (độ dài) của file
HĐH cấp phát trước và biết kích thước file khi tạo file.

ưu điểm:
- Cho phép truy cập trực tiếp và tuần tự
- Đơn giản, tốc độ cao
Nhược điểm:
- Phải biết trước kích thước file khi tạo
- Khó tìm chỗ cho file
- Gây phân mảnh ngoài: đó là hiện tượng vùng trống còn lại trên đĩa có kích thước quá nhỏ do vậy không thể cấp phát cho file có kích thước lơn hơn.

Sử dụng danh sách kết nối

Nguyên tắc: File được phân phối các khối nhớ kết nối với nhau thành danh sách kết nối, đầu khối chứa con trỏ trỏ tới khối tiếp theo.
File được cấp thêm khối mới, khối đó thêm vào cuối danh sách.
Bảng cấp phát chứa con trỏ tới khối đầu tiên của file, HĐH đọc lần lượt từng khối và sử dụng con trở để xác định khối tiếp theo.

ưu điểm:
- Không bị phân mảnh ngoài
- Không yêu cầu biết trước kích thước file lúc tạo
- Dễ tìm vị trí cho file, khoản mục đơn giản
Nhược điểm:
- Không hỗ trợ truy cập trực tiếp
- Tốc độ truy cập không cao
- Giảm độ tin cậy và tính toàn vẹn của hệ thống file

Sử dụng danh sách kết nối trên bảng chỉ số

Bảng chỉ số: Mỗi ô của bảng ứng với 1 khối (sector) của đĩa
Con trỏ tới khối tiếp theo của file được chứa trong ô tương ứng của bảng
Mỗi đĩa logic có 1 bảng chỉ số được lưu ở vị trí xác định
Kích thước mỗi ô trên bảng phụ thuộc vào số lượng khối trên đĩa

Cho phép tiến hành truy cập file trực tiếp: đi theo chuỗi con trỏ chứa trong bảng chỉ mục
Bảng FAT (File Allocation Table): được lưu ở đầu mỗi đĩa logic sau sector khởi động
FAT12, FAT16, FAT32: mỗi ô của bảng có kích thước 12, 16, 32 bit cho phép quản lý $2^{12}, 2^{16}, 2^{32}$ ô nhớ.

Sử dụng khối chỉ mục (index block/ node)

Nguyên tắc: Mỗi file có một khối chỉ mục chính (index block) chứa danh sách các khối dữ liệu của file.
Tất cả con trỏ tới các khối thuộc về 1 file được tập trung 1 chỗ, trong một khối gọi là khối chỉ mục (I-node)
Mảng chứa thuộc tính của file và vị trí các khối của file trên đĩa
Ô thứ i của mảng chứa con trỏe tới khối thứ i của file

Chọn kích thước I-node:
- Nhỏ: Tiết kiệm không gian nhưng không đủ con trỏ tới các khối nếu file lớn.
- Lớn: Với file nhỏ chỉ chiếm 1 vài ô thì lãng phí.
Giải pháp:
- Thay đổi kích thước i-node = sử dụng danh sách kết nối
- Sử dụng I-node có cấu trúc nhiều mức

I-node cấu trúc nhiều mức: không trỏ trực tiếp tới ô chứa dữ liệu mà trỏ tới các ô khối chỉ mục sau đó cái ô này mới chứa địa chỉ.

ưu điểm:
- Cho phép truy cập trực tiếp
- Các khối thuộc 1 file không cần nằm liên tiếp nhau
Nhược điểm:
- Tốc độ truy cập file chậm

VI. Quản lý không gian trống trên đĩa

Kích thước khối (cluster):
- Kích thước khối lớn:
  - Giảm kích thước bảng chỉ mục, tăng tốc độ đọc file;
  - Bị phân mảnh trong
- Kích thước khối nhỏ:
  - Mỗi file chiếm nhiều khối nhớ, nằm rải rác trên đĩa
  - Thời gian đọc file lâu
- Chọn kích thước khối tùy thuộc:
  - Kích thước đĩa: đĩa lớn, chọn kích thước khối lớn => thời gian truy cập nhanh, đơn giản hóa việc quản lý
  - Kích thước file: hệ thống sử dụng nhiều file lớn, kích thước tăng và ngược
- Kích thước khối thường là lũy thừa 2 của sector và nằm trong khoảng từ 512B tới 32 KB

Bảng bit

Vector bit là mảng 1 chiều
Mỗi ô có kích thước 1 bit tương ứng với một khối trên đĩa
Khối được cấp phát có bít tương ứng là 0, khối trống: 1 hoặc ngược lại
Dễ tìm 1 hoặc nhóm các khối trống liên tiếp
Với đĩa có kích thước lớn, đọc toàn bộ vector bit vào MEM có thể đòi hỏi khá nhiều không gian nhớ

Danh sách kết nối

Các khối trống được liên kết với nhau thành danh sách
Mỗi khối trống chứa con trỏ chỉ tới khối trống tiếp theo
Địa chỉ khối trống đầu tiên được lưu ở vị trí đặc biệt trên đĩa và được HDH giữ trong MEM khi cần làm việc với các file
Đòi hỏi truy cập lần lượt khi cần duyệt danh sách này
HDH có thể cấp phát ngay các khối ở đầu danh sách

Danh sách vùng trống

Các khối nằm liền nhau thường được cấp phát và giải phóng đồng thời
Lưu vị trí khối trống đầu tiên của vùng các khối trống liên tiếp và số lượng các khối trống nằm liền sau đó
Thông tin trên được lưu vào danh sách riêng

VII. Độ tin cậy của hệ thống file

Phát hiện và loại trừ các khối hỏng

Phát hiện và loại trừ khối hỏng
- Phương pháp 1:
  - Một sector trên đĩa được dành riêng chứa danh sách các khối hỏng
  - Một số khối không hỏng được dành riêng để dự trữ
  - Các khối hỏng sẽ được thay thế bởi các khối dự trữ bằng cách thay thế địa chỉ
  - Truy cập tới khối hỏng thành truy cập tới khối dự trữ
- Phương pháp 2:
  - Tập trung tất cả các khối hỏng thành 1 file => được coi như đã cấp phát và không được sử dụng nữa

Sao dự phòng

Tạo ra một bản sao của đĩa trên một vật mang khác
Sao lưu toàn bộ (full backup):
- Ghi toàn bộ thông tin trên đĩa ra vật mang tin khác
- Chắc chắn nhưng tốn nhiều thời gian
Sao lưu tăng dần (incremental backup):
- Được sử dụng sau khi đã tiến hành full backup ít nhất 1 lần
- Chỉ ghi lại các file đã bị thay đổi sau lần sao lưu cuối cùng
- Hệ thống lưu trữ thông tin về các lần lưu trữ file
- DOS: file thay đổi, archive bit =1
Kết hợp:
- Full backup: hàng tuần/ tháng
- Incremental backup: hàng ngày

Kiểm tra tính toàn vẹn của hệ thống

Hệ thống file chứa nhiều CTDL có mối liên kết => thông tin về liên kết bị hư hại, tính toàn vẹn của hệ thống bị phá vỡ
Các khối không có mặt trong danh sách các khối trống, đồng thời cũng không có mặt trong một file nào
Một khối có thể vừa thuộc về một file nào đó vừa có mặt trong danh sách khối trống
HDH có các chương trình kiểm tra tính toàn vẹn của hệ thống file, được chạy khi hệ thống khởi động, đặc biệt là sau sự cố

Kiểm tra tính toàn vẹn của hệ thống file

Ví dụ trong hệ UNIX:
- Tạo hai số đếm cho mỗi khối:
  - Số đếm thứ nhất: số lần khối đó xuất hiện trong danh sách khối trống.
  - Số đếm thứ hai: số lần khối xuất hiện trong file
- Tất cả số đếm được khởi tạo bằng 0
- Duyệt danh sách khối trống và toàn bộ i-node của các file
  - Một khối xuất hiện trong danh sách khối trống, số đếm tương ứng thứ nhất được tăng một đơn vị
  - Nếu khối xuất hiện trong i-node của file, số đếm tương ứng thứ hai được tăng một đơn vị
- Tổng 2 số đếm = 1

Đảm bảo tính toàn vẹn bằng cách sử dụng giao

Giao tác (transaction) là một tập hợp các thao tác cần phải được thực hiện trọn vẹn cùng với nhau
Với hệ thống file: mỗi giao tác sẽ bao gồm những thao tác thay đổi liên kết cần thực hiện cùng nhau
Toàn bộ trạng thái hệ thống file được ghi lại trong file log
Nếu giao tác không được thực hiện trọn vẹn, HDH sử dụng thông tin từ log để khôi phục hệ thống file về trạng thái không lỗi trước khi thực hiện giao tác

VIII. Bảo mật cho hệ thống file

Ngăn cản việc truy cập trái phép các thông tin lưu trữ trong file và thư mục
Hạn chế các thao tác truy cập tới file hoặc thư mục
Dùng mật khẩu:
- Người dùng phải nhớ nhiều mật khẩu
- Mỗi khi thao tác với tài nguyên lại gõ mật khẩu
Sử dụng danh sách quản lý truy cập ACL (Access Control List)
- Mỗi file được gán danh sách đi kèm, chứa thông tin định danh người dùng và các quyền người đó được thực hiện với file
- ACL thường được lưu trữ như thuộc tính của file/ thư mục
- Thường được sử dụng cùng với cơ chế đăng nhập
- Các quyền truy cập cơ bản:
  - Quyền đọc (r)
  - Quyền ghi, thay đổi (w)
  - Quyền xóa
  - Quyền thay đổi chủ file (change owner)

IX. Hệ thống file FAT

3 phiên bản: FAT12, FAT16, FAT32
Chữ số chỉ kích thước ô bảng FAT tương ứng 12, 16 và 32 bit

Đĩa Logic

Đơn vị cấp phát không gian trên đĩa (khối logic) là cluster (lũy thừa 2 của số lượng sector)

Boot sector:
- Sector đầu tiên của đĩa logic
- Chứa thông tin mô tả cấu trúc đĩa logic: kích thước sector, cluster, kích thước bảng FAT
- Chứa mã chương trình mồi để tải HĐH nếu đĩa logic là đĩa khởi động
FAT: bảng chỉ số quản lý cấp phát khối cho file
Thư mục gốc ROOT
Vùng dữ liệu: chứa các file và thư mục của đĩa logic

BOOT SECTOR

32 Byte đầu tiên

Các byte tiếp theo với FAT12/16

Các byte tiếp theo với FAT32

Bảng FAT

Quản lý các cluster trên đĩa và các file theo nguyên tắc:
- Các khối thuộc cùng 1 file được liên kết thành 1 danh sách
- Con trỏ được chứa trong ô tương ứng của bảng FAT
Mỗi ô trong bảng FAT tương ứng với một cluster trên đĩa, chứa 1 trong các thông tin:
- STT cluster tiếp theo trong danh sách các khối của file
- Dấu hiệu kết thúc nếu ô tương ứng với cluster cuối cùng của file
- Dấu hiệu đánh dấu cluster hỏng, không được sử dụng
- Dấu hiệu đánh dấu cluster dự phòng
- Bằng 0 nếu cluster trống, chưa cấp phát cho file nào
Cluster đầu tiên của vùng dữ liệu được đánh STT là 2
Hai ô đầu tiên của bảng FAT không dùng để quản lý cluster

Thư mục gốc (ROOT)

Mỗi thư mục được lưu trong bảng thư mục, thực chất là 1 file đặc biệt chứa các khoản mục của thư mục
Mỗi khoản mục chứa thông tin về một file hoặc thư mục con của thư mục đang xét
Với FAT12/16, thư mục trên cùng của đĩa được chứa trong 1 vùng đặc biệt gọi là thư mục gốc
Các thư mục mức thấp hơn/ thư mục gốc của FAT32 được chứa trong vùng dữ liệu trên đĩa cùng với các file
Mỗi thư mục gồm các khoản mục 32 byte xếp liền nhau

Hàm đọc đĩa

int absread(int drive, int nsects, long lsect, void *buffer)
- drive: ổ đĩa cần đọc, A: 0, B:1, C:2
- nsects: số sector cần đọc
- lsect: vị trí sector bắt đầu đọc
- buffer: vùng nhớ lưu nội dung thông tin cần đọc

Đọc FAT

Vị trí sector bắt đầu: reserved sector (byte 14, 15 trong bootsector)
Tổng số sector cần đọc: sectors per FAT (byte 22, 23)

Đọc ROOT

Vị trí sector bắt đầu: reserved sector + NoOfFATs * sectors per FAT
Tổng số sector cần đọc: NoOfRootEntries * 32 /BytesPerSector

Bài tập thực hành

Bài tập: Trình bày các bước cần thiết để đọc thư mục gốc root từ thẻ nhớ USB (FAT16)

  
int absread(int drive, int nsects, long lsects, void *buffer)
// drive: o dia can doc A: 0, B: 1, C: 2
// nsects(num sector): so sector can doc
// lsects(first sector): vi tri sector bat dau doc
// buffer: vung nho luu noi dung thong tin can doc

B1: Xây dựng cấu trúc của BOOT và ROOT → khai báo cấu trúc dữ liệu

  
struct BOOT {
};
int *root

B2: Đọc Boot Sector bằng hàm absread(4 (hoac 5), 1, 0, &boot)
B3: đọc Root → sử dụng absread
Số lượng sector cần đọc:

  
nsects = BOOT.root_size * 32 / BOOT.bytes_per_sector
// BOOT.root_size * 32 : tong so luong byte cua boot

Vị trí sector đầu tiên:

lsectors = BOOT.reserved + BOOT.FAT_size * BOOT.FAT_cnt
// BOOT.reserved: so luong sector cac khoi du phong
// BOOT.FAT_size: kich thuoc 1 bang FAT
// BOOT.FAT_cnt: so luong bang FAT

Hàm đọc ROOT:

absread(4, (hoac 5), nsects, lsects, root)

Bài tập: Giả sử bảng FAT đã được đọc (đã đọc boot sector) vào bộ nhớ địa chỉ <void *FAT> Viết chương trình C/C++ liệt kê Cluster trống trong N cluster đầu tiên.

  
for(int i = 0; i < N; i++)
	if(fat[i] == 0) printf(" %d", i);

Bài tập: Giả sử bảng FAT đã được đọc(đã đọc boot sector) vào bộ nhớ địa chỉ và 1 file nằm ở thư mục gốc bắt đầu từ cluster n. Viết đoạn chương trình in ra tên file

  
int *root = new int[BOOT.Root_size * 32 / sizeof(int)]
absread(Drive, nsects, lsect, root)
for(int i = 0; i < BOOT.Root_size, i++) {
	if(root[i].first_cluster == n) {
		// in file name
		for(int j = 0; j < 8; j++) { // Tên file, thêm bằng dấu trắng ở cuối nếu ngắn hơn 8 byte
			if(root[i].filename[j] != ' ') {
				printf("%c", root[i].filename[j])
				}
			}
		}
	}

Bài tập: Giả sử bảng FAT đã được đọc(đã đọc boot sector) vào bộ nhớ địa chỉ và 1 file nằm ở thư mục gốc bắt đầu từ cluster n. Viết đoạn chương trình in ra các cluster thuộc file đó

  
int cur = n;
printf("%u -> ", cur);
while(n < 0xFFF8){
	cur = FAT[cur]
	printf("%u -> ", cur);
}

Chương 3: Quản lý bộ nhớ

I. Phân chương bộ nhớ

Để thực hiện tiến trình, HĐH cần cấp phát cho tiến trình không gian nhớ cần thiết.
Việc cấp phát và quản lý vùng nhớ là chức năng quan trọng của HĐH
Một kỹ thuật cấp phát đơn giản nhất là mỗi tiến trình được cấp một vùng bộ nhớ liên tục
HĐH tiến hành chia bộ nhớ thành các phần liên tục là chương (partition), mỗi tiến trình sẽ được cung cấp một chương để chứa lệnh và dữ liệu của mình.
Quá trình phân chia bộ nhớ thành chương như vậy gọi là phân chương bộ nhớ.
Tùy thuộc việc lựa chọn vị trí và kích thước của chương, có thể phân biệt phân chương cố định và phân chương động
Các chiến lược quản lý bộ nhớ:
- Phân chương cố định
- Phân chương động
- Phân trang
- Phân đoạn
- Kết hợp phân đoạn - phân trang

Phân chương cố định

Nguyên tắc:
- Bộ nhớ được chia làm n phần.
- Mỗi phần được gọi là một chương (partition)
- Chương được sử dụng như một vùng nhớ độc lập.
- Mỗi chương chúa được đúng một tiến trình
- Khi được tải vào, tiến trình được cấp phát một chương. Sau khi tiến trình kết thúc, HĐH giải phóng chương và chương có thể được cấp phát cho tiến trình mới.
- Chương có thể có kích thước bằng nhau hoặc khác nhau.
Ví dụ: Xét hệ thống dưới đây bộ nhó được tổ chức theo phân chương cố định, tính thời gian HĐH thực hiện xong các tiến trình sau:

Kích thước các chương bằng nhau:
- Ưu điểm: Đơn giản
- Nhược điểm: Kích thước chương trình > kích thước chương dẫn đến không thể cấp phát.
- Gây phân mảnh trong
Kích thước các chương khác nhau:
- Có hai cách lựa chọn chương nhớ để cấp cho tiến trình đang chờ đợi bằng cách chọn chương có kích thước nhỏ nhất:
  - Mỗi chương có một hàng đợi riêng
  - Một hàng đợi chung cho tất cả các chương
Mỗi chương có một hàng đợi riêng: tiến trình có kích thước phù hợp với chương nào sẽ nằm trong hàng đợi của chương đó.

Ưu điểm: Tiết kiệm bộ nhớ, giảm phân mảnh trong.
Nhược điểm: Hệ thống không tối ưu, có thời điểm hàng đợi chương lớn thì rỗng, hàng đợi chương nhỏ hơn chứa nhiều tiến trình.
Một hàng đợi chung cho tất cả các chương: Mỗi khi có một chương trống tiến trình nằm gần đầu hàng đợi nhất và có kích thước phù hợp với chương nhất sẽ được tải và thực hiện

Ưu điểm: Tiết kiệm bộ nhớ, giảm phân mảnh trong và tối ưu hệ thống.
Nhận xét về phân chương cố định:
- Ưu điểm:
  - Đơn giản và ít xử lý
  - Giảm thời gian tìm kiếm
- Nhược điểm:
  - Hệ số song song không thể vượt quá số lượng chương của bộ nhớ
  - Bị phân đoạn bộ nhớ
  - Kích thước chương trình lớn hơn kích thước chương lớn nhất
  - Tổng bộ nhớ tự do còn lớn, nhưng không dùng để nạp các chương trình khác

Chương trình động

Nguyên tắc
Kích thước, số lượng và vị trí chương đều có thể thay đổi
Các vùng trống bộ nhớ cũng có thể được liên kết thành một danh sách kết nối
Khi một tiến trình yêu cầu bộ nhớ:
- HĐH cấp cho tiến trình 1 chương có kích thước đúng bằng tiến trình đó đang cần
- Nếu tìm thấy vùng nhớ tương ứng
- Vùng trống được chia thành 2 phần
- Một phần cung cấp theo yêu cầu
- Một phần trả lại danh sách vùng trống tự do
Nếu không tìm thấy:
- Phải chờ tới khi có được một vùng trống thỏa mãn
- Cho phép tiến trình khác trong hàng đợi thực hiện (nếu độ ưu tiên đảm bảo)
Khi tiến trình kết thúc sẽ tạo vùng trống trong Bộ nhớ và các vùng trống nằm cạnh nhau được nhập lại thành vùng lớn hơn

Ví dụ: Xét hệ thống dưới đây bộ nhó được tổ chức theo phân chương động, tính thời gian HĐH thực hiện xong các tiến trình sau:

Phân chương động tránh việc phân mảnh trong
Gây phân mảnh ngoài: dồn những vùng trống nhỏ thành lớn (nén)
Các chiến lược cấp chương chọn vùng chống:
- First Fit: Chọn vùng thích hợp đầu tiên
- Best Fit: Vùng thích hợp nhất
- Worst Fit: Vùng trống thích hợp nhất - vùng kích thước lớn nhất

Phương pháp kề cận - Buddy system

Nguyên tắc: Chia đôi liên tiếp vùng trống tự do cho tới khi thu được vùng trống nhỏ nhất thỏa mãn
Các chương và khối trống có kích thước là $2^k (L \leq k \leq H)$
$2^L$: Kích thước nhỏ nhất của chương
$2^H$: Kích thước của toàn bộ không gian nhớ
Yêu cầu cấp vùng nhớ $S$:
- $2^{H-1} < S \leq 2^H $: Cấp cả $2^{H}$
- $S \leq 2^{H-1}$: Chia vùng trống tìm được thành 2 khối bằng nhau (gọi là buddies) $2^{H-1}$
  - Nếu $2^{H-2} < S \leq 2^{H-1}$: Cấp cả $2^{H-1}$
  - Tiếp túc chi đôi tới khi tìm được vùng thỏa mãn.
Ví dụ: Vùng trống 16K Bytes, yêu cầu cấp phát một chương có kích thước 735 Bytes

Phương pháp kề cận cung cấp bộ nhớ nhanh: với bộ nhớ kích thước $n$,cần duyệt $log_2{n}$ danh sách

Thu hồi vùng nhớ: Có thể kết hợp 2 vùng kề nhau có cùng kích thước, tiếp tục kết hợp liên tiếp cho tới khi tạo ra vùng trống lớn nhất có thể.

Ánh xạ địa chỉ và chống truy cập trái phép

Khi tiến trình được tải vào bộ nhớ, CPU dành 2 thanh ghi:
- Thanh ghi cơ sở: chứa địa chỉ bắt đầu của tiến trình
- Thanh ghi giới hạn: chứa độ dài chương

Địa chỉ logic được so sánh với nội dung của thanh ghi giới hạn
- Nếu lớn hơn: lỗi truy cập
- Nhỏ hơn: đưa tới bộ cộng với thanh ghi cơ sở thành địa chỉ vật lý
Nếu chương bị di chuyển thì nội dung của thanh ghi cơ sở bị thay đổi chứa địa chỉ mới

Trao đổi giữa bộ nhớ và đĩa (swapping)

Phương pháp tráo đổi (swapping):
Các tiến trình đang thực hiện có thể bị tạm thời tải ra đĩa nhường chỗ để tải các tiến trình khác vào.
Sau đó lại được tải vào (nếu chưa kết thúc) để thực hiện tiếp
- Một tiến trình đã hết khoảng thời gian sử dụng CPU của mình
- Nhường chỗ cho một tiến trình khác có thứ tự ưu tiên cao hơn
Thời gian tải phụ thuộc vào tốc độ truy cập đĩa, tốc độ truy cập bộ nhớ và kích thước tiến trình
Khi được tải vào lại, tiến trình có thể được chứa vào chương ở vị trí cũ hoặc được cấp cho một chương địa chỉ hoàn toàn mới
Các tiến trình bị trao đổi phải ở trạng thái nghỉ, đặc biệt không thực hiện các thao tác vào ra

II. Phân trang bộ nhớ

Trong kỹ thuật phân chương, mỗi tiến trình chiếm một chương tức là một vùng liên tục trong bộ nhớ dẫn đến phân mảnh và không tận dụng hết được bộ nhớ.
Kỹ thuật phân trang (paging) để hạn chế nhược điểm của kỹ thuật phân chương:

Khái niệm phân trang

Bộ nhớ vật lý được chia thành từng khối có kích thước bằng nhau: khung trang vật lý (page frame):
- Khung trang vật lý được đánh số 0,1,2,… : địa chỉ vật lý của khung trang
- Khung trang được dùng làm đơn vị phân phối nhớ
Không gian địa chỉ logic của tiến trình hay bộ nhớ logic (chương trình) được chia thành những khối gọi là trang (page) có kích thước bằng khung trang.

Tiến trình được cấp các khung để chứa các trang của mình.
Trang có thể chứa trong các khung nằm rải rác trong bộ nhớ

Bảng trang: HĐH quản lý việc cấp phát khung cho mỗi tiến trình bằng bảng trang (Page table): mỗi ô tương ứng với 1 trang và chứa số khung cấp cho trang đó.
Mỗi tiến trình có bảng trang riêng:

Ánh xạ địa chỉ

Ánh xạ địa chỉ địa chỉ logic khi phân trang sang địa chỉ vật lý.

Ánh xạ địa chỉ gồm 2 phần:
- Số thứ tự trang (p)
- Độ dịch (địa chỉ lệch) của địa chỉ so với đầu trang (o)

Nếu kích thước trang là $2^n$. Biểu diễn địa chỉ logic dưới dạng địa chỉ có độ dài (m + n) bit
- m bit cao: biểu diễn số thứ tự trang
- n bit thấp: biểu diễn độ dịch trong trang nhớ

Cho trang nhớ có kích thước 1024Byte, độ dài địa chỉ logic là 16bit. Tính địa chỉ logic của địa chỉ vật lý 1500? Tính số trang và độ dịch trong trang?

Xem đáp án

💻 Đáp án:

Cách 1:
m+n = 16 do không gian nhớ logic là 16 bit
Số lượng khung trong một trang là 1024 Bytes = $2^{10}$ Bytes, nên cần 10 bit để biểu diễn cho khung trong trang
=> n = 10 ; m = 6
1500 = 0000010111011100
Vậy ta có p = $000001_2$ = 1; o = $0111011100_2$ = 476
Cách 2:
Phần p = 1500/1024 = 1
Phần o = 1500mod1024 = 476
Vậy ta có p = 1; o = 476

Chuyển địa chỉ logic sang địa chỉ vật lý:
- Lấy m bit cao của địa chỉ => được số thứ tự trang
- Dựa vào bảng trang, tìm được số thứ tự khung vật lý (k)
- Địa chỉ vật lý bắt đầu của khung là $k ∗ 2^n$
- Địa chỉ vật lý của byte được tham chiếu = địa chỉ bắt đầu của khung + Địa chỉ lệch (độ dịch)
Nhận xét: Chỉ cần thêm số khung vào trước dãy bit biểu diễn độ lệch
Quá trình biến đổi từ địa chỉ logic sang địa chỉ vật lý được thực hiện bằng phần cứng
Kích thước trang là lũy thừa của 2, nằm trong khoảng từ 512B đến 16MB
Việc tách phần p và o trong địa chỉ logic được thực hiện dễ dàng bằng phép dịch bit

Ưu điểm của phân trang:
- Không tồn tại hiện tượng phân đoạn ngoài: Phân mảnh trong khi phân trang có giá trị trung bình bằng nửa trang
- Hệ số song song cao và cho phép sử dụng chung trang
- Cơ chế ánh xạ địa chỉ hoàn toàn trong suốt đối với chương trình Nhược điểm của phân trang:
- Tồn tại hiện tượng phân đoạn trong
  - Luôn xuất hiện ở trang cuối cùng
  - Giảm kích thước trang cho phép tiết kiệm MEM?
    - Kích thước trang nhỏ => số lượng lớn, bảng trang to, khó quản lý
    - Không tiện cho việc trao đổi với đĩa do thực hiện theo từng khối lớn
- Đòi hỏi hỗ trợ của phần cứng cho chiến lược phân trang lớn
- Khi chương trình lớn, bảng quản lý trang nhiều phần tử

Tổ chức bảng trang

Mỗi thao tác truy cập bộ nhớ đều đòi hỏi truy cập bảng phân trang => tổ chức bảng phân trang sao cho tốc độ truy cập là cao nhất

Sử dụng tập hợp các thanh ghi làm bảng phân trang:
- Tốc độ truy cập rất cao
- Số lượng thanh ghi hạn chế => không áp dụng được
Giữ các bảng trang trong MEM:
- Vị trí mỗi bảng được trỏ bởi thanh ghi cơ sở bảng trang PTBR (Page Table Base Register)
- Thời gian để truy cập bảng => sử dụng bộ nhớ cache tốc độ cao
Bảng trang nhiều mức:
- Các hệ thống tính toán hiện đại cho phép sử dụng không gian địa chỉ logic lớn ($ 2^{32} \to 2^{64} $) => Số lượng trang cần quản lý tăng dẫn đến kích thước bảng trang tăng
- Nguyên tắc: Bảng quản lý trang được phân trang
  - Chia bảng trang thành những phần nhỏ hơn
  - Tổ chức bảng trang nhiều mức: Khoản mục của bảng mức trên chỉ tới bảng trang khác
- Ví dụ về bảng 2 mức:
  - Máy tính có không gian địa chỉ logic là 4GB ($2^{32}$B), kích thước trang nhớ là 4KB ($2^{12}$B):
    - Số thứ tự trang $2^{32} / 2^{12} = 2^{20}$ => m = 20bit
    - Độ dịch trong trang $2^{12}$ => n = 12bit
- Bảng trang được phân trang. Số hiệu trang được chia thành 2 phần:
- P1: 10 bit cho phép định vị khoản mục trong bảng mức trên
- P2: 10 bit định vị khoản mục trong bảng mức dưới
- O: 12 bit, chứa độ dịch trong trang
Địa chỉ truy nhập có dạng P1, P2, o

III. Phân đoạn bộ nhớ

Khái niệm

Chương trình thường được chia thành nhiều phần:
- Một chương trình chính (main program)
- Tập các chương trình con
- Các biến, các cấu trúc dữ liệu
Các module, đối tượng trong chương trình được xác định bằng tên:
- Hàm sqrt(), thủ tục printf()…
- x, y, counter, Buffer…
Các phần tử trong module được xác định theo độ lệch với vị trí đầu:
- Câu lệnh thứ 5 của hàm sqrt()…
- Phần tử thứ 12 của mảng Buffer…
Khi phân trang, chương trình được chia thành các trang có kích thước đều nhau, không quan tâm tới tổ chức logic và ý nghĩa của từng thành phần.
Một cách tổ chức khác, cho phép chia chương trình thành các đoạn theo cấu trúc logic
- Đoạn chương trình - Đoạn mã: chứa toàn bộ mã chương trình, một số hàm hoặc thủ tục của chương trình.
- Đoạn dữ liệu: chứa các biến toàn cục, các mảng.
- Đoạn ngăn xếp: chứa ngăn xếp của tiến trình
Mỗi đoạn chiếm một vùng liên tục
- Có vị trí bắt đầu và kích thước
- Có thể nằm tại bất cứ đâu trong bộ nhớ
Đối tượng, phần tử trong từng đoạn được xác định bởi vị trí tương đối so với đầu đoạn
Ví dụ về phân đoạn bộ nhớ:

So sánh với phân chương động:
- Giống: bộ nhớ được cấp phát theo từng vùng kích thước thay đổi
- Khác: chương trình có thể chiếm nhiều hơn 1 đoạn và không cần liên tiếp nhau trong MEM
Ưu điểm:
- Tránh hiện tượng phân mảnh trong, dễ sắp xếp bộ nhớ
- Dễ chia sẻ các đoạn giữa các tiến trình khác nhau

Kích thước mỗi đoạn có thể thay đổi không ảnh hưởng đoạn khác
Nhược điểm:
- Có phân mảnh ngoài

Ánh xạ địa chỉ

Sử dụng bảng đoạn (SCB: Segement Control Block) cho mỗi tiến trình. Mỗi phần tử của bảng tương ứng với 1 đoạn, chứa:

Dấu hiệu (Mark (0/1)): Đoạn đã tồn tại trong bộ nhớ
Địa chỉ cơ sở (Address): Vị trí bắt đầu của đoạn trong bộ nhớ
Độ dài đoạn (Length): Sử dụng để chống truy cập trái phép ngoài đoạn
Địa chỉ logic gồm 2 thành phần (s, o):
- s: số thứ tự, tên đoạn
- o: độ dịch trong đoạn
Địa chỉ truy nhập: <Tên (số stt) đoạn, Độ dịch trong đoạn>

Từ chỉ số đoạn s, vào bảng đoạn, tìm địa chỉ vật lý bắt đầu của đoạn
So sánh độ dịch o với chiều dài đoạn, nếu lớn hơn => Địa chỉ sai - Lỗi truy cập
Địa chỉ vật lý mong muốn là tổng của địa chỉ vật lý bắt đầu đoạn và địa chỉ lệch

Coming Soon….

Môn học ở PTIT

ptit

This post is licensed under CC BY 4.0 by the author.