Chương 13 - File System và Database

13.1 Mở đầu

File – là tập hợp dữ liệu, thường được lưu trữ trong các thiết bị lưu trữ ngoại vi như đĩa từ, bằng từ,... Với file, ta có thể thực hiện các thao tác như với một đơn vị

open – chuẩn bị file cho truy cập

close – kết thúc truy cập file

create – tạo file mới

copy – tạo bản sao

destroy (delete) – xoá file

rename - đổi tên file

Đối với các đơn vị thông tin trong file, thường sử dụng các lệnh

read – đọc dữ liệu từ file

write – ghi các thông tin vào file

insert – chèn thêm thông tin

delete – xoá các đơn vị thông tin

-File system (FS) là một cấu thành của HĐH, có nhiệm vụ điều khiển thao tác với các file trên bộ nhớ ngoài. Nó còn đảm bảo khả năng chia sẻ và an toàn thông tin giữa nhiều người dùng.

13.2 Chức năng của FS

-FS phải đảm bảo nhiều chức năng khác nhau liên quan đến điều khiển truy cập, trong đó có:

Người dùng phải có khả năng tạo, thay đổi, xoá file

Cung cấp khả năng chia sẻ file dưới sự điều khiển chặt chẽ

Cơ chế chia sẻ file phải xem xét hình thức truy cập cần kiểm soát, ví dụ thao tác đọc , ghi, thay đổi, ..

Người dùng phải có khả năng thao tác dễ dàng với cấu trúc file, độc lập với phần cứng.

Đảm bảo sự troa đổi thông tin giữa các file

Cần có các công cụ khắc phục, khôi phục lại thông tin khi có sự cố

Với các thông tin quan trọng, cần có các cơ chế kiểm soát truy cập chặt chẽ, tránh các truy cập bất hợp pháp, khả năng mã hoá dữ liệu

Hệ thống cần cung cấp giao diện thân thiện với người dùng, cho phép người dùng làm việc với các cấu trúc dữ liệu logic của mình, không cần quan tâm đến các chi tiết vật lý, cụ thể

13.3 Cấu trúc dữ liệu

Tất cả các dữ liệu máy tính có thể xử lý đều tạo thành từ các bit có giá trị 0 hoặc 1. Khi kết hợp các bit thành tổ hợp, ta có thể lưu trữ, thể hiện mọi thông tin phong phú.

Mức cao hơn, ta có đơn vị byte là tổ hợp 8 bit. Như thế có thể có 256 giá trị khác nhau của 1 byte, trong số đó có các ký tự (a-z, A-Z), chữ số (0-9), các ký tự đặc biệt,..Phân bố tổ hợp các bit theo ký tự được gọi là bảng mã. Hiện nay có một số bảng mã phổ biến: EBCDIC (extend bit code decimal for interchange) thường được sử dụng để biểu diễn thông tin bên trong máy, hệ ASCII (americal standard code for interchange information) thông dụng trong các hệ thống truyền thông, ngày nay trong xu thế toàn cầu hoá, mã unicode đang được chấp nhận ngày càng rộng rãi với ưu thế có thể lưu trữ và thể hiện hầu hết các ngôn ngữ trên thế giới.

ở mức cao hơn, nhóm các ký tự liên quan đến nhau gọi là trường – field, ví dụ trường họ tên sinh viên,.. các trường liên quan tạo thành bản ghi ví fụ bản ghi thông tin sinh viên có các trường họ tên, lớp..

Nhóm các bản ghi tạo thành file và tập hợp thông tin cao nhất được gọi là cơ sở dữ liệu.

13.5 Tổ chức file

Tổ chức file là cách phân bố bản ghi của file trong bộ nhớ ngoài. Có thể chia thành các dạng tổ chức sau

+ Nối tiếp: các bản ghi phan bố theo thứ tự vật lý, bản ghi logic tiếp theo nằm nối tiếp về vật lý. Tổ chức file theo kiểu nối tiếp thường áp dụng trong băng từ.

+ Dãy chỉ số:

các bản ghi nối tiếp về logic không nhất thiết liên tiếp về vật lý. Trong hệ thống sử dụng các chỉ mục riêng trỏ đến vị trí vật lý của bản ghi. Tổ chức này thường áp dụng trong đĩa từ.

+ Truy cập trực tiếp

Truy cập bản ghi trực tiếp theo địa chỉ vật lý. Tổ chức hệ thống đơn giản nhưng gánh nặng chuyển sang người lập trình, họ phải biết rõ cấu trúc vật lý của thiết bị. Vì thế hình thức này ít áp dụng.

+ Thư mục

Thư mục là kiến trúc cao hơn file, bao gồm tập hợp các file. Về thực chất thì thư mục cũng là file, chỉ có điều dữ liệu trong đó là thông tin về các file nằm trong thư mục.

13.7 Hệ thống file (File System)

Ta có thể đưa ra các đặc điểm sau của file

+ tần số thay đổi: static và dynamic

+ kích thước file

File System là cấu thành quan trọng của HĐH, FS thường cung cấp các công cụ

Các phương pháp truy cập: xác định, tổt chức truy cập dữ liệu

Các cơ chế điều khiển file: điều khiển truy cập, chia sẻ file cho nhiều người dùng, bảo vệ dữ liệu

Công cụ điều khiển bộ nhớ ngoài: quản lý việc phân bố, cấp phát bộ nhớ ngoài

Công cụ đảm bảo tính toàn vẹn dữ liệu

Chức năng quan trọng của FS là cấp phát bộ nhớ ngoài, điều khiển truy cập. Trong các hệ đa người dùng, đa nhiệm, cùng một lúc có thể có nhiều yêu cầu truy cập đồng thời. FS phải đảm bảo phục vụ các yêu cầu nhanh nhất, vẫn đảm bảo an toàn dữ liệu.

13.8 Cấp phát và giải phòng không gian đĩa

-Vấn đề cấp phát và giải phóng không gian đĩa, ở mức độ nào đó có nhiều điểm chung với phân bố bộ nhớ trong các hệ đa nhiệm. Nếu như ban đầu file được ghi trong một vùng nhớ liên tục thì theo thời gian, các file liên tục thay đổi và không gian đĩa trở nên bị chia nhỏ (fragmentation).

-Một trong những biện pháp giải quyết tình trạng đó là theo chu kỳ thực hiện việc dồn đĩa. Các file được tổ chức lại để chúng chiếm vùng đĩa liên tục. Việc này thường được thực hiện vào thời gian rỗi của hệ thống. Một số hệ thống còn có thể dọn dẹp đĩa ngay cả khi đang phục vụ người dùng.

-Trong một số tình huống, khi mà số yêu cầu đọc/ghi dữ liệu rất nhiều thì việc dồn đĩa có thể không mang lại lợi ích. Ví dụ các yêu cầu có thể yêu cầu dữ liệu trên các file trên vùng đĩa cách xa nhau ngay cả khi các file nằm trên vùng đĩa liên tục.

Khái niệm locality trong bộ nhớ ảo cũng có mặt trong FS, theo đó thường khi truy cập thông tin thường scan các block dữ liệu. Do đó việc sắp xếp để các file chiếm vùng đĩa liên tục thực sự có hiệu quả.

-Việc xác định thói quen của người dùng: các ứng dụng, các dữ liệu thường xuyên được dùng cũng có thể cần để ý trong thiết kế FS.

-Trong các hệ thống dùng tổ chức bộ nhớ theo trang, block trao đổi bộ nhớ với bộ nhớ ngoài là bội của trang, khi đó việc tổ chức bộ nhớ ngoài theo các block có kích thước tương đương cũng có ý nghĩa. Với tính locality, việc truy xuất các trang bộ nhớ liền nhau dẫn đến việc cần phân bố dữ liệu trong bộ nhớ ngoài cũng cần liền nhau.

13.9 Phân bố

Có hai hình thức phân bố: liên tục và không liên tục.

-13.9.1 Phân bố liên tục

Trong hình thức này, mỗi file được cấp phát một vùng liên tục. Nếu không có được vùng trống liên tục đủ lưu file thì file sẽ không thể được lưu.

Một trong các ưu điểm của phân bố liên tục là các bản ghi liên tiếp về logic cũng được lưu liên tục về mặt vật lý, điều đó cho phép cải thiện tốc độ truy cập.

Việc tổ chức lưu trữ cũng tương đối đơn giản.

-uy nhiên phân bố liên tục có những hạn chế, khi các file bị xoá, thay đổi, tạo ra tình trạng phân mảnh. Hơn nữa, khi cần ghi thêm dữ liệu vào file không phải luôn có vùng trống ngay cuối file để lưu.

-Để tránh tình trạng phân mảnh có thể thực hiện dồn file, tuy nhiên việc đó không phải luôn mang lại hiệu quả.

-13.9.1 Phân bố không liên tục

Bởi vì thường xuyên các file bị thay đổi, do đó hình thưc phân bố liên tục đ• nhanh chóng bị thay thế bởi hình thức phân bố không liên tục, mặc dù tổ chức phức tạp hơn nhưng nó cho phép xây dựng hệ thống mềm dẻo hơn. Có một số hình thức phân bố không liên tục

-1. Sử dụng danh sách sector

Trong sơ đồ này, đĩa được xem như tập hợp các sector riêng rẽ. File có thể bao gồm các sector nằm trên các vị trí rải rác. Các sector thuộc cùng một file có các con trỏ đến nhau, tạo thành chuỗi/danh sách các sector. Không gian trống được chỉ ra trong một danh sách các sector trống.

-Khi cần cấp phát thêm bộ nhớ, chỉ cần cấp sector từ danh sách sector trống. Còn khi file giảm kích thước thì sector được đánh dấu trống và đưa vào danh sách. Việc dồn đĩa không phải đặt ra.

-Tuy nhiên nó cũng có những nhược điểm. Bởi vì các sector có thể nằm rải rác trên đĩa, việc truy cập dữ liệu liên tiếp trong file có thể kéo theo thời gian tìm kiếm sector khá lâu. Việc đọc dữ liệu kéo theo phải duyệt qua chuỗi các sector, xử lý con trỏ kết nối.

-2. Phân bố theo block

Hình thức phân bố theo block là kết hợp giữa hình thức phân bố liên tục và không liên tục, trong đó bộ nhớ ngoài được chia thành các khối/block gồm nhiều sector liên tục. Khi cấp phát thêm, FS cố gắng cấp phát block trống gần nhất. Khi truy cập dữ liệu, FS xác định số blokc và sau đó số sector trong block. Có 3 hình thức phan bố theo block: chuỗi block/block chaining, cuỗi block chỉ số/index block và bảng ánh xạ block

+ Chuỗi các block dữ liệu

Trong sơ đồ này, bản ghi trong directory trỏ đến block đầu tiên của file. Mỗi block (có độ dài cố định) gồm hai phần: phần header chứa con trỏ đến block tiếp theo, và phần dữ liệu. Block cuối cùng Đơn vị cấp phát nhỏ nhất là block. Để đọc bản ghi, đầu tiên cần tìm đến block sau đó đến sector trong block chứa bản ghi.

Quá trình tìm kiếm phải bắt đầu duyệt từ block đầu tiên, theo các con trỏ đến block cần tìm. Như thế mếu block phân bố rải rác thì thời gian truy cập lâu hơn đáng kể. Việc cấp phát thêm block hay xoá bớt khá dễ dàng thông qua định hướng lại con trỏ. Trong một số hệ thống, tổ chức chuỗi block liên kết 2 chiều, mỗi block có 2 con trỏ, 1 trỏ tới block tiếp theo và 1 trỏ tới block trước.

hình 13.4: Chuỗi các block

+ Sơ đồ chuỗi block chỉ số/ index block

Trong sơ đồ này, các chỉ mục (index) được chứa trong các block chỉ số. Mỗi block chỉ số chứa số lượng cố định các phần tử, mỗi phần tử chứa con trỏ đến block dữ liệu. Nếu một index block không đủ, hệ thống dùng chuỗi các index block để chứa thông tin của file, mỗi index block có con trỏ đến index block tiếp theo trong chuỗi.

So với sơ đồ dùng chuỗi các block, sơ đồ này có một số ưu điểm. Khi tìm kiếm block dữ liệu nào đó, chỉ cần tìm (duyệt) trong số lượng ít các index block thay vì duyệt qua số lượng lớn các block dữ liệu. Để tăng tốc độ, có thể bố trí các index block nằm trên vùng liên tục trong bộ nhớ ngoài. Khi tìm thấy vị trí block dữ liệu thì chỉ cần nạp block dữ liệu đó vào bộ nhớ.

Sơ đồ này có nhược điểm chủ yếu là khi có thay đổi dữ liêu, ví dụ khi cần thêm các bản ghi dữ liệu mới có thể dẫn đến phải cấu trúc lại nhiều index block. Trong một số hệ thống, để khắc phục người ta dánh sẵn các vùng trống dự trữ cho các index block có thể có trong tương lai. Tuy nhiên khi vùng trống đó đầy thì cũng dẫn đến phải cấu trúc lại index.

Hình 13.5 Sơ đồ chuỗi index block.

+ Sơ đồ bảng ánh xạ block

Hình 13.6 bảng ánh xạ block

Trong sơ đồ này để xác định vị trí block, không cần phải có con trỏ mà dùng số của block, bởi vì từ số block có thể dễ dàng tính toán được vị trí block trên bộ nhớ ngoài. Sơ đồ này sử dụng bảng ánh xạ block, mỗi dòng chứa thông tin ánh xạ cho 1 block. Dòng trong bảng thư mục sẽ trỏ đến một dòng trong bảng ánh xạ - tương ứng với block dữ liệu đầu tiên của file. Mỗi dòng của bảng ánh xạ chứa số của block tiếp theo của file. Như thế từ bảng ánh xạ có thể đọc được tất cả thông tin vị trí các block dữ liệu của file.

-Với dòng ánh xạ tương ứng với block cuối của file, thường chứa giá trị đặc biệt (ví dụ null) thể hiện rằng không còn block nào tiếp theo-nó là block cuối cùng.

Các dòng ánh xạ của block trống chứa giá trị đặc biệt khác thể hiện rằng đó là block trống, có thể cấp phát. Hệ thống có thể tra cứu bảng ánh xạ để tìm các block trống, hoặc lưu thông tin block trống trong một danh sách riêng.

Bảng ánh xạ có thể được thay đổi để lưu cả các thông tin khác, phục vụ cho mục đích tìm kiếm.

-Một trong các ưu điểm lớn nhất của sơ đồ này là chỉ cần tra cứu thông tin trong bảng ánh xạ file là có thể xác định các block trống và vị trí tương đối của chúng so với các block khác, từ đó khi cần cấp phát có thể chọn các block gần với block thuộc cùng 1 file một cách dễ dàng, nâng cao tốc độ truy cập.

13.10 Mô tả file - File Descriptor

File Descriptor là bản ghi lưu đầy đủ các thông tin về file mà HĐH cần quan tâm, quản lý. Các thông tin lưu trong File Descriptor sẽ phụ thuộc vào từng hệ thống, nhưng nói chung chúng đều có các thông tin sau:

Tên file

Kích thước file

Kiểu file

Ngày tháng tạo, cập nhật ,..

Thông tin thuộc tính

File Descriptor nằm trên bộ nhớ ngoài và chúng được nạp vào bộ nhớ khi mở (open) file. Nói chung thì File Descriptor được xử lý bởi File system, người dùng không có quyền truy cập trực tiếp.

13.11 Ma trận điều khiển quyền truy cập

Tại sao cần quản lý quyền truy cập đến file. Trong hệ thống nhiều người dùng, mỗi người đều lưu thông tin riêng của mình trên các file và các người dùng khác nói chung không được truy cập đến chúng, do đó hệ thống cần có các thông tin về quyền truy cập để điều khiển truy cập.

Có nhiều cơ chế khác nhau để quản lý quyền truy cập, một trong các sơ đồ đơn giản nhất là sử dụng ma trận điều khiển quyền truy cập (hình 13.7). Trong đó một chiều là các ID người dùng (hàng Ri), một chiều là ID file (cột Ci). Vị trí ô RiCj chứa giá trị quyền truy cập của người dùng Ui đối với file Fj. Nếu kích thước ô là 1 bit, ta có thể xác định 2 quyền, ví dụ giá trị 0 là không được đọc, 1 là có quyền đọc,.. Tất nhiên để quản lý nhiều quyền hơn thì ta cần lưu được tổ hợp nhiều quyền hơn.

Hình 13.7