Giáo trình Hệ điều hành - Chương 4: Quản lý tệp tin

CHƯƠNG 4: QUẢN LÝ TỆP TIN

4.0. Quan niệm về quản lý tệp tin (Files Manager)

Ở việc bẻ gãy một tiến trình hay sau khi hoàn thành một tiến trình, một câu hỏi

được đặt ra là: Bạn lưu trữ dữ liệu của bạn như thế nào, để sau này, bạn có thể làm

việc trở lại với cái bạn đã có? Tính chất này của dữ liệu gọi là cố định dữ liệu,

người ta đạt được khi dữ liệu được viết vào bộ nhớ quảng đại trước khi kết thúc

chương trình. Tuy nhiên, chúng ta vẫn còn một vấn đề: Ở phần lớn bộ nhớ quảng

đại, danh sách các tệp tin quá dài, ấy nhưng người ta muốn thời gian truy cập phải

ngắn. Do đó, trường hợp này chỉ có thể dẫn tới một cách thức tổ chức tệp tin để

quản lý các tệp dữ liệu trong hệ thống máy tính.

4.1. Hệ thống tệp tin (Files- System)

Để phục vụ việc quản lý tệp tin, đầu tiên, chúng ta viết tất cả các tệp tin vào

trong một danh sách và cần lưu ý: chúng ta cần phải biết một cái gì đó về tệp tin,

thí dụ ngày tháng năm tạo lập, dung lượng, vị trí của bộ nhớ quảng đại, luật truy

cập…

Một bảng như thế thì không khác mấy một ngân hàng dữ liệu. Nếu chúng ta

dẫn tới mỗi thuộc tính dữ liệu và kể cả các tác vụ (như các thủ tục, các phương

pháp tiến hành…), mà nó được xử lý, do đó, chúng ta nhận được một ngân hàng

dữ liệu hướng đối tượng. Ngoài ra, nếu chúng ta có các đối tượng âm thanh và

hình ảnh, mà chúng được một chương trình sinh ra hay được sử dụng, lúc đó,

chúng ta cần dùng một ngân hàng dữ liệu đa phương dụng (multimedia-

databank), trong đó, thông tin được chứa đựng để làm đồng bộ hai phương dụng.

Một cách khái quát, khi không có đối tượng nào thì việc điều hành khi lưu trữ dữ

liệu cố định được phát triển; còn đối với các ngân hàng dữ liệu lớn thì hệ thống

điều hành cơ sở dữ liệu hướng đối tượng được phát triển.

Chúng ta có thể sử dụng tất cả các cơ cấu có trên danh mục các tệp tin của bộ

nhớ quảng đại, các cơ chế này được tìm thấy để tổ chức một cách hiệu quả các

ngân hang dữ liệu hình cây; với cấu trúc này, người ta có thể tìm kiếm rất nhanh

các tệp tin với một dấu hiệu xác định (ngày tháng tạo lập tệp tin, tên tác giả…).

Tuy nhiên, chúng ta phải quan tâm tới vấn đề, mà chúng liên quan đến ngân

hàng dữ liệu. Một vấn đề cơ bản là sự cố định dữ liệu: Nếu chúng ta tạo lập, loại

bỏ hay thay đổi các dữ liệu của một tệp tin trên bộ nhớ quảng đại, do đó, điều đó

phải được giải thích ở trong bảng danh mục các dữ liệu. Nếu tác vụ này bị bẽ gãy,

thí dụ vì một lý do nào đó, tiến trình viết bị bẻ gãy (thí dụ khi mất nguồn điện), do

đó, dữ liệu ở trong bảng danh mục thì không còn thích hợp nữa. Ở các tác vụ tiếp

theo, người ta đã làm quen một cơ cấu quan trọng ở trong mục 2.3.2, đó là việc kết

hợp nhiều tác vụ thành một hoạt động nhân tử. Để phát hiện những sai sót của hệ

thống tệp tin, tất cả các tác vụ ở trên danh mục tệp tin phải được thực thi với tư

cách là những hoạt động nhân tử.

Việc ký hiệu tên tệp tin với một cái tên có ghép thêm những chữ số là một sự

trợ giúp quan trọng đối với người sử dụng. Trong bảng danh mục các tệp tin ở

hình 4.1 có thể tồn tại 2 tệp tin với các tên giống nhau Teptin1.dat và Teptin2. dat;

chúng chỉ khác nhau bởi một chữ số, do đó, đối với việc quản lý tệp tin, chúng

khác nhau rõ ràng. Hình 4.2 chỉ ra sơ đồ tổ chức quản lý tệp tin. Ở đây, mỗi tệp tin

có thể đứng độc lập (Tệp tin X), hoặc có thể thuộc một nhóm các tệp tin (Tệp tin

1, Tệp tin m…)

Hình 4.2---------------------

Các nhóm nhỏ có thể gộp lại thành nhóm lớn hơn tuỳ thuộc vào người sử dụng,

sao cho nó trở thành cấu trúc cây để sử dụng. Kiểu tổ chức tệp tin này thì rất phổ

biến. Các đại diện nhóm được biểu thì là một thư mục.

Một kiểu tổ chức quản lý các tệp tin như thế được dùng để tổ chức ngân hàng

dữ liệu, mà trong đó, tất cả các tệp tin được mô tả với các tính chất và các hiển

thị nội dung. Sự lưu ý về các tệp tin thì tồn tại ở trong một thư mục dữ liệu. Trong

hầu hết các hệ điều hành, những hệ thống tệp tin có sơ đồ đơn giản được dùng.

Hình 4.3-----------------------

Một kiểu sơ đồ khác cũng thường được dùng, đó là kiểu sơ đồ tổ chức tệp tin

kiểu mạng, hãy xem một thí dụ trong hình 4.3 trên đây. Ở đó chỉ ra 2 thư mục Ban

a và Ban b có thể nối ngang với tệp tin Thongbao. dot của công ty, vì tệp tin này luôn

luôn tồn tại.

4.2. Tên tệp tin (Filesname)

Dữ liệu của các tiến trình không chỉ phải được bảo vệ bền vững ở trên bộ nhớ

quảng đại, mà đặc biệt phải tạo khả năng truy cập qua các tiến trình khác nhau, do

đó, mỗi tệp tin được biểu thị một từ khoá rõ ràng. Vì cách tổ chức hệ thống quản

lý tệp tin hầu hết do con người thực hiện, cũng giống như việc lập trình các tiến

trình để truy cập các tệp tin, tên của tệp tin có thể giống nhau, chỉ khác, mỗi tệp tin

có thêm một con số, coi như biểu thị một khoá tượng trưng…, thí dụ

Vanban1.doc, Vanban2.doc…Cách làm này có lợi cho việc quản lý nội bộ các tệp

tin (vị trí, dung lượng) một cách dễ dàng. Tệp tin có thể được thi hành hay được

đặt tại một chỗ nào đó ở tron bộ nhớ mà tệp tin vẫn không bị thay đổi.

4.2.1 Kiểu tệp tin và tạo tên tệp tin

Một cách truyền thống, nói chung tên tệp tin gồm hai phần, chúng được ngăn

cách nhau bằng một dấu chấm: phía trái dấu chấm là tên riêng, còn bên phải là

phần mở rộng (extension). Phần mở rộng này cho thấy một sự trợ giúp về mục

đích sử dụng của tệp tin. Thí dụ tên một tệp tin Vanban.txt, ý nói: tệp tin Vanban

có kiểu mở rộng txt là một loại tệp tin text được cấu thành bởi các ký tự theo

chuẩn ASCII. Có những quy ước khác nhau cho phần mở rộng, thí dụ như sau:

.dat

.doc

.pas

.c

.h

.ps

cho dữ liệu hoặc việc tạo kiểu dạng phụ thuộc vào chương trình tạo lập;

cho các văn bản text hoặc việc tạo dạng theo kiểu soạn thảo text;

cho mã nguồn của chương trình viết bằng ngôn ngữ PASCAL;

cho mã nguồn của chương trình viết bằng ngôn ngữ C;

các tệp tin khai báo cho các chương trình viết bằng ngôn ngữ C;

các tệp tin ngôn ngữ lệnh đồ hoạ cho máy in Laser;

.tar

.html

một hệ thống tệp tin lưu trữ trong một tệp tin;

tệp tin văn bản ASCII cho hệ thống text đặc biệt của trang WEB;

.Z ; .zip; .gz

cho các tập tin nén lại;

.jog; .gi; .ti; .bmp cho các tệp tin về ảnh.

Người ta ghi nhớ rằng, phần mở rộng của tệp tin chứa đựng chỉ một ít hoặc chỉ

thỉnh thoảng những ký tự cổ xưa. Điều đó được lý giải rằng, đối với một hệ thống

tệp tin thông thường cho phép vài ký tự làm phần mở rộng và mặc khác, nó thuận

tiện cho người sử dụng không phải viết quá nhiều.

Có rất nhiều kiểu phần mở rộng, mà chúng được tạo bởi hệ thống người sử

dụng và chúng cũng phục vụ cho việc phân nhóm các tệp tin. Vì tên tệp tin nói

chung là tuỳ ý và có thể được sử dụng thay đổi, do đó, những người lập trình đều

đã chú ý tới cái đó, nhằm làm cho tệp tin chỉ rõ công dụng của chúng. Ở đầu tệp

tin, một hay nhiều kiểu chữ số ảo (magic number) được viết, mà chúng cho phép

một đặc tính chính xác của nội dung tệp tin.

Thí dụ về tên tệp tin ở trong Unix:

Tên tệp tin ở trong hệ điều hành Unix, có thể có tới 255 ký tự. Với Unix

version V, số ký tự của tên tệp tin có ít hơn 14 ký tự cho phần chính và 10 ký tự

cho phần mở rộng. Các tệp tin thực thi ở trong Unix có cấu trúc như sau:

TYPE File Header = RECORD

a_magic:

LONG CARDINAL

CARDINAL

{số ảo}

{độ lớn của Codesegment}

a_txt:

a_data:

a_bss:

a_syms:

a_entry:

…

CARDINAL

{độ lớn Segment của các dữ liệu khởi xướng}

CARDINAL{độ lớn Segment của các dữ liệu không khởi xướng}

CARDINAL {độ lớn bảng biểu trưng Symboltable}

CARDINAL {sự bắt đầu của chương trình}

END

Tuy nhiên, một số ảo đứng đầu tên tệp tin; chúng không chỉ dẫn tới sự giải

thích về điều đó (cho thấy tệp tin có thể thực thi), mà còn, bằng phương pháp nào

tệp tin được thực hiện:

a_magic= 407B {tạo dạng tất cả: mã không được bảo vệ cũng không được sử dụng cho 1 tiến

trình khác}

a_magic= 410B {Text-Segment được bảo vệ Data- Segment được đặt ở giới hạn trang cuối

cùng (4kB) ở trong bộ nhớ}

a_magic= 413B {Text- Segment bắt đầu ở giới hạn 4kB của tệp tin; Text và Data-Segment

là bội số của 4kB}

Để phân biệt các loại tệp tin khác nhau, đó là sự đánh giá về khả năng có thể

thực thi khi khởi động tệp tin. Loại phân biệt này thì rất đặc biệt. Sau đây chúng ta

khảo sát vài thí dụ về kiểu phân biệt tệp tin này.

Thí dụ về kiểu và tên tệp tin:

Trong Unix hay trong Windows NT, kiểu cách một tệp tin được biểu thị nhờ

một cái tên. Thí dụ tên tệp tin Script.ps.gz có ý nghĩa: đó là một tệp tin nguyên bản

(Script), mà ấn bản của nó đã được nén lại ở dạng tái bút (postscript) với chương

trình nén zip. Để đọc được tệp tin này, đầu tiên, người ta phải gọi chương trình

gunzip, và sau đó, tệp tin chuyển tới cho máy in Postscript. Kết quả chỉ dẫn là sự

cải biên: nó không chỉ chứa đựng trong tệp tin, mà còn chứa đựng ở trong kiểu tệp

tin được nén. Đối với tệp tin này, nếu kiểu tệp tin được chỉ dẫn trong thư mục, do

đó, người ta có thể thực hiện tác vụ thứ hai. Việc tạo kiểu tệp tin phải được cắt

nghĩa ở trong tệp tin hay nó phải là kiểu bởi sự xếp nhiều lần của các kiểu. Điều

đó chỉ có thể nói gọn là: phải giải thích kiểu mới lập rõ ràng và phải đưa vào

những hoạt động thích hợp cho các kiểu đó.

Thí dụ về kiểu tệp tin và các hoạt động chương trình ở trong Unix:

Ở trong hệ điều hành Unix có một giao diện đồ hoạ người sử dụng, một sự

quản lý tệp tin bao hàm trong giao diện này. Điều đó cho thấy, các tệp tin chuyên

dụng ứng với mỗi phần mở rộng sẽ dẫn tới những tác động khác nhau của chương

trình, điều đó được chỉ ra như là một Menu (thực đơn) khi kích chuột phải. Khi

kích đôi chuột trái ở tại tên tệp tin, thì hoạt động được dẫn ra trong Menu sẽ bắt

đầu khởi động.

Thí dụ về kiểu tệp tin và hoạt động chương trình ở Windows NT:

Dưới Windows NT có trình soạn thảo Editor, trình này quản lý một ngân hàng

dữ liệu riêng của tất cả các ứng dụng, bộ kích tạo hệ điều hành và các cấu hình hệ

thống…Tất cả các chương trình ở trong hệ thống cũng như các phần mở rộng đều

được khai báo ở đó. Khi kích đôi chuột trái tại trên một tệp tin ở trong trình quản

lý tệp tin thì một chương trình được gọi.

Người ta lưu ý rằng, trong hai thí dụ vừa nêu, thông tin về kiểu tệp tin thường

không được hệ điều hành quản lý, mà nó tồn tại trong các tệp tin đặc biệt hay được

chứa đựng và được quản lý với các chương trình đặc biệt. Điều đó thì không có

vấn đề gì. Kiểu tốt nhất cho việc quản lý các tệp tin là tổ chức tất cả tệp tin thành

một ngân hàng dữ liệu tổng thể; trong đó, các tính chất bổ sung của các tệp tin

được thực hiện nhờ các đặc tính bổ sung

Một vấn đề khác là việc làm sáng tỏ sự tham chiếu tệp tin, nếu các tệp tin ở

trong hệ thống quản lý files thì cho phép tên tệp tin dài; nhưng khi ứng dụng (khi

thực thi), tệp tin chỉ có thể được phép ngắn lại. Thí dụ có hai tên tệp tin

MethodeForUser.txt và MethodeForEvery.txt cùng tồn tại ở trong hệ thống tệp tin.

Khi hai tệp tin muốn thực thi, thì 8 ký tự đầu tiên được lưu ý. Trong trường hợp

này, 8 ký tự đầu tiên của hai tệp tin giống nhau. Do vậy, ở đây, một phương pháp

được tìm thấy cho phép sắp xếp các tệp tin được rõ ràng hơn.

Thí dụ về sự chuyển đổi tên tệp tin trong Windows NT:

Vì hệ điều hành Windows NT có thể quản lý cả các hệ thống tệp tin DOS bên

cạnh hệ thống tệp tin NTFS (windows NT File System). Cho nên, ở đây vấn đề đặt

ra là phải chuyển đổi các tệp tin có tên dài trong hệ thống NTFS thành tên tệp tin

rõ ràng trong hệ thống MS-DOS. Điều này đạt được bằng các giải thuật sau đây:

(1) Tất cả các ký tự của tên tệp tin không hợp lý ở trong MS-DOS được chuyển

đổi thành tên tệp tin trong hệ thống NTFS bằng cách cắt bỏ: các ký tự trống, 16 ký

tự của 16 Bit- Unicode, các điểm ở đầu, ở cuối và trong khoảng tên tệp tin.

(2) Tất cả 6 ký tự đầu tiên của chuỗi ký tự đứng trước dấu chấm phân đoạn

phần mở rộng được cắt bỏ; và sau đó, ký hiệu ~1 được thay vào trước điểm phân

đoạn phần mở rộng. Chuỗi ký tự sau điểm phân đoạn phần mở rộng chỉ để lại 3 ký

tự, các ký tự ở cuối phần này cắt bỏ và chuỗi ký tự còn lại chuyển thành chuỗi các

chữ cái lớn.

(3) Nếu có một tệp tin, mà nó chỉ ra sự giống nhau với tệp tin khác, do đó,

thay vì ký hiệu ~1, ký hiệu ~2 được thay vào chỗ đó. Nếu tệp tin này đã tồn tại, thì

thay bằng ký hiệu ~3 hay ~4.. cho đến khi không tồn tại sự giống nhau.

4.2.2. Tên đường dẫn

Qua sơ đồ sắp xếp các tệp tin, việc biểu diễn tên tệp tin rõ ràng tạo ra khả năng

để sắp xếp các nút có dạng hình cây, nhờ vậy, một đường dẫn đi tới một tệp tin

được thực hiện thuận tiện. Tên đường dẫn của một tệp tin được tạo lập từ một

chuỗi các tên nút và chứa đựng ký tự tách chia giữa các tên nút. Đó là một dấu

hiệu đặc biệt, nó là biểu tường tiêu biểu cho mỗi hệ điều hành. Thí dụ ở trong hình

4.3, tên tệp tin Vanban1.txt có đường dẫn trong hệ điều hành Unix:

Institut5/Rudi/Vanban1.txt

còn ở trong hệ điểu hành Windows NT có dạng:

Institut5/Rudi/Vanban1.txt

Về điều đó, do có sự kết nối ngang, nên có nhiều tên đường dẫn cho một tệp

tin, thí dụ đối với tệp tin Briefvorlage.dot có các đường dẫn:

Institut5/Rudi/briefvorlage.dot và Congty/Dieuhanh/briefvorlage.dot.

Những nút ở trên của hệ thống cây thư mục tệp tin được gọi là gốc, nó được

biểu thị bởi một biểu trưng đặc biệt: dấu xiên trái(/) ở trong Unix, dấu xiên phải (\)

ở trong Windows NT. Khi thông dịch tên tệp tin, nó được thực hiện từng bước từ

dưới lên trên theo hướng gốc cây thư mục tệp tin. Thí dụ trong hình 4.3, tệp tin

Brief.doc ở thư mục Rudi mà cả ở thư mục Hans, tên đường dẫn của nó được biểu

diễn mỗi dấu đại diện cho một thư mục nào đó:

../../Rudi/Brief1.doc

Tên đường dẫn tương đối bắt đầu từ một vị trí nào đó của cây tới tệp tin. Tên

đường dẫn tuyệt đối được biểu thị từ gốc đến ngọn là tên tệp tin. Thí dụ ở trong

hình 4.4 chỉ ra một đường dẫn tương đối ../Daten/Dat1.a với tệp tin Dat1.a của

chương trình Prog.

Hình 4.4 -----------------

4.2.3. Thí dụ về cây thư mục ở Unix

Trong Unix, sơ đồ một hệ thống tệp tin thông dụng được chỉ ra trong hình 4.2,

nhờ đó không gian tên tệp tin được tạo lập. Ngoài ra ở cấu trúc cây này người ta

có thể nối ngang qua giữa các tệp tin bởi lênh “ln”.

Đối với đặc điểm của sơ đồ tên, người ta phải phân biệt, các thư mục đã được

thu xếp với các tên tệp tin trên ổ đĩa hay chưa (?). Nếu chúng đã được thu xếp, do

đó, một sự nối ngang trực tiếp là có thể. Trường hợp này gọi là kết nối vật lý hay

kết nối cứng. Nếu ngược lại, chúng được thu xếp khác nhau trên ổ đĩa, do đó,

người ta có thể thiết đặt một sự nối ngang logic và dẫn ra tên đường dẫn của

chúng. Trường hợp này gọi là kết nối tượng trưng (symbol-link).

Sự khác nhau ở các kết nối ngang nói ở trên là ở chỗ, việc xoá bỏ tên tệp tin

hay thư mục khi có nhiều tiến trình hay nhiều người sử dụng truy cập chúng. Nếu

chúng ta lưu ý tới hệ thống cây thư mục ở trong hình 4.5, chúng ta thấy rằng

không có sự phân biệt giữa tên tệp tin và tên thư mục.

Hình 4.5-----------------

Nếu các thư mục Gruppe1 và Gruppe2 được ghép ở các ổ đĩa khác nhau, do

đó, các nối ngang Rudi/Datei2 và Hans/Datei2 thì khác biệt với các nối ngang

Gruppe1/Hans/Datei3 và Gruppe2/Datei3: ở đây cặp thứ nhất là nối vật lý, còn cặp

thứ hai là nối logic.

Nếu bây giờ ở Unix một tệp tin được xoá bỏ, do đó, nó sẽ tồn tại tối thiểu cho

đến khi có một sự kết nối vật lý tồn tại. Ở trong thí dụ đã nêu, nếu tệp tin có đường

dẫn Rudi/Datei2 được xoá bỏ, do đó, tệp tin chỉ còn lại dưới cái tên có đường dẫn

Hans/Datei2 và có thể sử dụng được. Ngược lại nếu tệp tin có đường dẫn

Hans/Datei3 xoá bỏ; do đó, tệp tin tương ứng cũng bị xoá bỏ; sự tham chiếu tên

(sysbol-link) ở trong thư mục Gruppe2 vẫn còn tồn tại, nhưng khi truy cập tệp tin

thì ngay lập tức xuất hiện lỗi khi tham chiếu tên tệp tin này, tức là một tệp tin với

cái tên này không còn nữa.

Điều quyết định trong hệ điều hành Unix là để một tệp tin được xoá hoàn toàn,

thì phụ thuộc vào bộ đếm để đếm số tham chiếu kết nối vật lý. Tuy nhiên, cơ chế

này của hệ điều hành Unix là một phương tiện đơn giản ở trong phạm vi đa tiến

trình, nhưng cũng có thể dẫn tới lỗi. Chúng ta nhận thấy rằng, chúng ta đang ở tại

thư mục Rudi của hình 4.5 và thực hiện kết nối vật lý trên thư mục Gruppe1. Vì

việc xóa bỏ một thư mục chưa trống thì cấm (để tránh lỗi), do đó, chúng ta không

thể xoá được thư mục Gruppe2. Ngược lại, ở tại thư mục Gruppe1: ở đây có một

kết nối thứ hai của thư mục Rudi, cho nên cho phép xoá bỏ tên tệp tin được. Điều

đó dẫn tới tình huống, rằng bây giờ thư mục Gruppe1 với thư mục con và các tệp

tin ở phía dưới còn tồn tại, tuy nhiên những thứ đó không còn dùng được nữa, vì

chúng là những thư mục trống, và do đó cũng không thể xoá bỏ được. Điều đó thì

cũng khong thể tránh được: tuy kết nối ngang là có thể, nhưng việc kiểm tra các

vòng nối và việc tách chia các sơ đồ tệp tin tại mỗi tác vụ xoá là không nên làm.

Từ lý do này, ở ấn bản mới của Unix về cây thư mục thì chỉ còn được dùng kiểu

kết nối logic.

Đối với việc tạo lập hay xoá bỏ tệp tin, ở trong Unix có một có chế thông

dụng: Nếu một tiến trình tạo lập một tệp tin và sau đó, nhiều tiến trình mở tệp tin

này, do đó, tệp tin không bị biến mất khi xoá, nhờ người tạo lập. Và nó sẽ tồn tại

cho tới khi tiến trình cuối cùng gọi thủ tục close() và như vậy, bộ đếm sự tham

chiếu trở về 0.

Hệ thống tệp tin hình cây tổng quát được phân chia thành các sơ đồ nhánh khác

nhau, mà các tệp tin của chúng tồn tại trên các ổ đĩa khác nhau. Khi khởi động hệ

thống (bootstrap), hệ thống tệp tin của các ổ đĩa khác nhau vào một nút gốc (root)

bằng một hàm gọi hệ thống mount(), mà ở đó, nút gốc của mỗi hệ thống tệp tin

còn được phản ảnh bởi tên của một thư mục (mount point direction). Hình 4.6 chỉ

ra một cây thư mục tệp tin như vậy.

Hình 4.6---------------------------

4.2.4. Cây thư mục ở Windows NT

Cây thư mục ở trong hệ điều hành Windows NT mô tả toàn bộ các đối tượng

toàn cục; một cách độc lập với cái đó, khi chúng là các tệp tin thuần tuý hay những

đối tượng khác như các kênh trao đổi thông tin (communication-canal hay named

pips), các bộ nhớ chia xẻ (shared memory), các cờ hiệu (semaphore), các biến cố

hay các tiến trình. Các đối tượng với tên gọi toàn cục được trao cho các cơ chế bảo

vệ tương ứng khi truy cập.

Hệ thống cây thư mục bắt đầu với nút gốc bởi dấu xiên phải (\), ở đó tồn tại các

đối tượng tệp tin hay các đối tượng thư mục. Các thư mục đối tượng là các đối

tượng chứa đựng tên của đối tượng với những thuộc tính (biến số, hằng số…), với

các phương pháp (tạo lập, mở hay đọc lướt các thư mục). Hệ thống này không chỉ

bao gồm trạng thái nhân, mà cả trạng thái người sử dụng, nghĩa là các thư mục

không chỉ có thể đặt vào nhân hệ điều hành Windows NT, mà còn có thể đặt vào

cả các hệ thống khác như OS/2, POSIX…Đối với mỗi loại đối tượng (tệp tin, tiến

trình…) có những ấn bản chuyên dụng cho 3 phương pháp sử dụng các đơn thể

nhân khác nhau (điều hành I/O, điều hành tiến trình…).

Tuy nhiên, để tạo lập thư mục toàn cục từ các thư mục đối tượng hay việc thiết

đặt các đường dẫn kết nối ngang (như trong Unix) đều có thể thực hiện một cách

thuận lợi ở trong Windows NT.

Ở cây thư mục của việc điều hành đối tượng thì tồn tại nhiều đối tượng khác

nhau (xem hình 4.7). Chẳng hạn đối tượng “A:” là một kết nối ngang logic với đối

tượng hệ thống tệp tin “Floppy”. Với mỗi đối tượng thì một phương pháp dò tìm

được chuyên môn hoá. Nếu trình soạn thảo Editor muốn mở tệp tin có đường dẫn

A:\Texte\bs_files.doc, do đó, tại cửa sổ điều hành đối tượng, nó hỏi đối tượng này.

Bằng phương pháp dò tìm, trình điều hành đối tượng tìm kiếm cây thư mục của

nó: đối tượng cần tới ở chỗ nào (?). Nếu nó đi tới đối tượng “A:”, thì khi đó,

phương pháp kết nối logic được áp dụng.

Hình 4.7---------------------

Chuỗi ký tự “A:” được thay thế bởi chuỗi ký tự “\Device\Floppy0” và sau đó,

được chuyển cho trình điều hành đối tượng. Trình này sẽ xử lý đường dẫn cho tới

khi gặp đối tượng tệp tin “Floppy0”. Phương pháp dò tìm này làm việc trên cây

thư mục của trình điều hành hệ thống các tệp tin, nó dò tìm đường dẫn với các thủ

tục đặc biệt, cho tới khi một đối tượng tệp tin với bs_files.doc có thể được đưa trở

lại.

Với cơ chế này, ở trong Windows NT có thể tích hợp một cách thống nhất các

hệ thống tệp tin khác nhau như hệ thống FAT (file allocation table) của MS-DOS,

hệ thống tệp tin hiệu suất cao của OS/2 và hệ thống tệp tin NT của Windows.

Đối với việc xoá một tệp tin cũng như xoá một đối tượng được nhiều tiến trình

sử dụng, thì các cơ chế được dẫn tới tương tự như trong Unix. Vì lý do thực thi, có

hai bộ đếm tham chiếu được dẫn tới: một bộ để đếm số lượng các chức danh đối

tượng, khi đó chúng được đón nhận ở các tiến trình người sử dụng; và một bộ nữa

để đếm số lượng que chỉ thị, khi đó chúng được đưa vào hệ điều hành (đáng lẽ

chúng được trao cho bởi các đối tượng khi truy cập nhanh). Nếu bộ đếm tham

chiếu của người sử dụng mà tham chiếu tới tên tệp tin bị giảm xuống tới 0, thì do

đó, đối tượng sẽ bị xóa ở trong cây thư mục; và cũng vì thế, không có một tiến

trình nào có thể truy cập được. Tuy nhiên, nó vẫn còn ở lại trong bộ nhớ cho tới

khi bộ đếm các tham chiếu của hệ điều hành giảm xuống 0. Sau đó bộ nhớ được

giải phóng và được sự dụng trở lại. Với cơ chế này đã tránh được: một đối tượng

được nhiều tiến trình xử lý bị xoá một cách nhầm lẫn trước khi các tiến trình khác

thực thi xong.

Một bộ đếm tham chiếu đôi cũng tránh được: thí dụ một đối tượng tiến trình

được sinh ra bởi một tiến trình và sau đó, với sự kết thúc của tiến trình này, nó đi

tới kết thúc; tuy nhiên, vẫn còn một tiến trình có quan hệ với đối tượng. Sự tham

chiếu của hệ điều hành tới tiến trình thứ hai đảm bảo sự tồn tại của đối tượng tệp

tin cho tới khi quan hệ nói trên không còn nữa.

4.3. Thuộc tính tệp tin và cơ chế bảo vệ

Trong một thư mục có chứa tên một tệp tin, thì hầu hết các thông tin về tệp tin

được bảo vệ. Bên cạnh độ lớn tệp tin (tính bằng Byte hay bằng các khối trang),

ngày tháng tạo lập và ngày tháng điều chỉnh, còn có các thuộc tính khác (còn gọi

là các cờ hiệu khác) như ẩn khuất (Hidden), hệ thống.

Một dạng đặc biệt của các thông tin trạng thái là các thông tin bảo vệ như luật

truy cập của con người và của các chương trình đối với tệp tin. Tương tự như đối

với các cơ chế bảo vệ bộ nhớ, người ta đã xem xét để loại bỏ các chức năng lỗi của

chương trình như các lỗi khi truy xuất chương trình của người sử dụng nhờ những

biện pháp có mục đích: Những biện pháp do Uỷ ban POSI-6 đề nghị có nội dùng

như sau:

+ Phải đảm bảo nguyên tắc thu gọn đặc quyền ít nhất (least privilege) đối với

việc thực hiện một nhiệm vụ.

+ Phải bổ sung việc điều khiển khi truy cập qua các thông báo rời rạc

(discretionary access control). Việc truy xuất cưỡng bức thì độc lập với người tạo

lập. Việc truy xuất đối tượng chỉ xảy ra bởi các tiến trình với các đặc quyền lớn

hơn.

+ Phải lưu ý các ghi chép về trạng thái của đối tượng nhằm có thể phát hiện các

nguyên nhân và các người làm việc trong hệ thống khi sử dụng sai trái.

Ngược lại, hệ điều hành chỉ thực thi rất giới hạn các yêu cầu kể trên.

4.3.1. Các đặc quyền truy cập ở Unix

Ở hệ điều hành Unix có các biến trạng thái (còn gọi là các cờ) khác nhau: đọc

(ký hiệu r), viết (w), thực thi (x). Tất cả các tệp tin và các thư mục đều có một

trạng thái như nhau.

Các ký hiệu vừa nói có ý nghĩa như sau:

r cho phép đọc danh sách tệp tin;

w cho phép thay đổi vị trí tệp tin trong danh sách;

x cho phép thực thi hay tìm kiếm tệp tin trong danh sách.

Về quyền truy cập, hệ điều hành Unix phân biệt 3 hạng: chủ nhân hệ thống

(owner), thành viên một nhóm (user group member) và mọi người khác (other).

Chỉ dẫn về các quyền truy cập

Lệnh ls là để xem các tệp tin và các quyền truy cập chúng. Lệnh ls-al để xem

các tệp tin của một thư mục, thí dụ với lệnh này, ta nhận được đoạn thông báo:

drwxr-xr-x

- rw- r--r –

brause 512

obene 512

brause 44181 Ap23 15:56 data1.txt

Ap23 15:55

May17 17:53

.

..

Ở cột đầu tiên là các quyền truy cập của các tệp tin. Trong đó: d là thư mục

(directory), còn 9 ký tự tiếp theo được phân làm 3 cho các người sử dụng owner

(chủ nhân), grouper (nhóm trưởng), other (người khác) với r: đọc, w: viết, x: tìm

kiếm và dấu gạch ngang (-) để chỉ một quyền truy cập không được chọn. Những

cột còn lại của bảng thông báo này là tên người sử dụng, dung lượng (Byte), ngày

tháng tạo lập, thời gian tạo lập và cuối cùng là tên tệp tin. Ở dòng đầu tiên của cột

tên tệp tin, có một dấu chấm (.) để chỉ tên tệp tin ở một thư mục hiện hành của

người sử dụng brause có dung lượng 512Byte, được tạo lập ngày 23 tháng 4 lúc

15giờ 55 phút. Ở dòng thứ 2 của cột này có dấu hai chấm (..) cũng giải thích tương

tự.

Ở hệ điều hành Unix, để thực hiện một chương trình, có thể kết nối các quyền

truy cập của riêng mình trong chương trình với hàm userId cho người thực hiện và

groupId cho người quản lý nhóm. Do đó, các chức năng của chương trình hệ thống

có thể được mọi người sử dụng thực hiện, nếu thiết đặt các trạng thái userId và set

groupId. Còn nếu tại một thư mục, trạng thái sticky bit được thiết đặt, do đó, một

người sử dụng bình thường không thể xoá hay gọi các tệp tin của người sử dụng

khác trong thư mục này.

Chỉ những ấn bản đặc biệt của hệ điều hành Unix mới có các danh sách điều

khiển truy xuất với nhiều cơ chế khác nhau. Cũng với lý do này, sự hoạt động

mạnh mẽ của nhóm O/Open đã thống nhất và tạo ra được nhiều tiêu chuẩn bảo vệ

hệ thống Unix.

4.3.2. Quyền truy cập ở trong Windows NT

Hệ thống tệp tin ở trong hệ điều hành Windows NT được quản lý bởi một cơ

chế định hướng đối tượng. Quyền truy cập có giá trị đối với mỗi đối tượng trong

cây thư mục của Windows NT (như các tiến trình, các cờ hiệu, khoảng nhớ…).

Độc lập với các quyền truy cập này còn có những tính chất đặc biệt đối với các đối

tượng tệp tin:

Các thuộc tính:

+ Tên tệp tin

+ Kiểu thiết bị mà trên đó tệp tin tồn tại,

+ Byte offset: là tình trạng hiện hành của tệp tin,

+ Shared mode: là trạng thái (đọc/viết/xoá) của tệp tin trong khi sử dùng,

+ Open mode: là kiểu và phương pháp tác vụ của tệp tin (đồng bộ/ không đồng

bộ, có / không có bộ đệm Cache, truy cập tuần tự/ bất kỳ…)

+ file disposition: biểu thị tệp tin bền vững hay tuỳ ý.

Các phương pháp:

Các hàm CreateFile(), OpenFile(), ReadFile(), WriteFile(), CloseFile(), dùng

để đọc chọn hay thay thế các thông tin tệp tin, các thuộc tính mở rộng, các độ lớn

tệp tin (Byte), các thông tin về thiết bị hay để đọc chọn một thư mục…

Mỗi đối tượng tệp tin là một bản sao của thông tin điều khiển của một tệp tin;

nó cũng có thể dẫn tới nhiều đối tượng, mà chúng tham chiếu chính tệp tin này.

Do đó, có những thông tin toàn cục được lưu trữ trong tệp tin (không phải ở trong

đối tượng tệp tin) và cũng có thể được thay đổi ở đó.

Mỗi tệp tin chứa đựng những thuộc tính tệp tin khác nhau; khi thực hiện chúng

là những dòng dữ liệu biến thiên theo độ lớn tệp tin. Trước hết, chúng bao gồm

những thông tin sau đây:

Các thông tin chuẩn:

+ Ngày tháng và thời gian tạo lập, ngày tháng và thời gian truy xuất gần đây và

lần thay thế cuối cùng;

+ Dung lượng tệp tin hiện hành;

+ Thuộc tính logic của tệp tin biểu thị bởi giá trị Yes/No. Thí dụ: tệp tin hệ

thống, tệp tin ẩn, tệp tin lưu trữ, tệp tin điều khiển, tệp tin chỉ đọc, tệp tin nén…

Tên tệp tin:

Trong cây thư mục với kết nối vật lý, tên tệp tin có thể dài; ở các kết nối khác

của MS-DOS, tệp tin có tên ngắn.

Các dữ liệu bảo vệ:

Chúng đựơc chứa đựng trong danh sách điều khiển việc truy xuất đối với mọi

chủ nhân của tệp tin.

Nội dung tệp tin:

Thuộc tính này chứa đựng các dữ liệu riêng lẻ; tại các thư mục, một cấu trúc

chỉ số được lưu trữ cùng với các tệp tin.

Điều được quan tâm là các dữ liệu thực chất được chứa đựng một trong các

thuộc tính nêu ở trên. Vì người sử dụng có thể tạo ra các thuộc tính, cho nên các

dòng dữ liệu cũng được bổ sung liên tục. Khác với tên tệp tin chính, thí dụ

MyFile.dat, các dữ liệu phụ của người lập trình được tham chiếu với một cái tên

bổ sung; tên này được tách làm hai phần ngăn cách nhau bởi dấu hai chấm, thí dụ

MyFile.dat:MyCommentar. Điều đó đã tạo nên nhiều thông tin bổ sung để treo

vào một tệp tin (chẳng hạn tên của một chương trình xử lý hay ngữ cảnh khi xử lý

lần cuối…) mà không hề thay đổi các dữ liệu chính. Do vậy, đối với mỗi dòng dữ

liệu, một thông tin trạng thái được dẫn tới, ví như độ lớn hiện hành lớn nhất được

cấp phát, các cờ hiệu đối với các phần của tệp tin…

Khi thay thế hay dẫn trở lại, các thuộc tính logic được trợ giúp nhờ phương

pháp kết hợp. Thí dụ một tệp tin được nén lại một cách tự động, tức là tệp tin nhận

được thuộc tính nén lại. Điều đó cũng có giá trị đối với toàn bộ cây thư mục.

Các cơ chế bảo vệ trong hệ điều hành Windows NT được tách chia một cách

mạnh mẽ hơn trong Unix. Đối với mỗi tệp tin có một danh sách truy cập được chi

tiết hoá; trong đó, các quyền truy cập của người sử dụng được thực hiện. Việc bổ

sung thêm tên tiêu chuẩn như Adminitrator (quản lý), System, Creator (tạo lập),

Quest (Khách), EveryOne (mọi người)…, người ta có thể chuyên môn hoá những

người sử dụng tiếp theo và các quyền của họ; nghĩa là họ được phép hay không

được phép về một quyền truy cập nào đó.

Hệ thống bảo vệ này thì không giới hạn trên các tệp tin, nó được áp dụng một

cách tổng hợp ở tất cả các đối tượng toàn cục ở đây thư mục trong Windows NT

và được chỉ huy một cách thống nhất. Tiếp đó, một sự kiểm tra đối với việc truy

cập tới tệp tin hay thư mục được trợ giúp.

4.4. Các chức năng tệp tin

Có rất nhiều kiểu tác vụ xảy ra trên các tệp tin. Trong mục này, chúng ta khảo

sát vài kiểu đặc trưng cho tệp tin trên bộ nhớ quảng đại (các loại ổ đĩa cứng, ổ đĩa

mềm, băng nhựa camara…).

4.4.1. Các chức năng chuẩn

Trong hầu hết các hệ điều hành đều có vài chức năng cơ bản, mà với chúng,

các tệp tin có thể được đọc và viết. Sau đây là các chức năng cơ bản đó.

• Tạo lập tệp tin (Create File):

Để thiết đặt một tệp tin, các thông số bao gồm một chuỗi các ký tự để chuyên

môn hoá các kiểu truy cập (viết/ đọc, tuần tự/ tự chọn). Khi gọi một chức năng,

người ta nhận được một sự tham chiếu tệp tin, mà với sự tham chiếu này, người ta

có thể truy cập tới tất cả các chức năng tiếp theo của tệp tin. Một sự tham chiếu

như thế (phân đoạn tệp tin, chức danh tệp tin) có thể là một con số (chỉ số của một

trường nội bộ của việc điền vào tệp tin) hay một bộ chỉ thị ở một cấu trúc bên

trong tệp tin.

• Mở một tệp tin (OpenFiele):

Khi mở một tệp tin đang tồn tại, các cấu trúc dữ liệu khác nhau được khởi

xướng, do đó, việc truy cập tiếp theo diễn ra nhanh hơn. Thuộc cái đó có việc

kiểm tra các quyền truy cập cũng như cơ chế các bộ đệm, cơ chế các cấu trúc truy

cập.

• Đóng tệp tin (Close File):

Để đóng một tệp tin, cần phải mô tả các thông tin quản lý tệp tin tại bộ nhớ

quảng đại và được phép nối tiếp việc sử dụng không gian các cấu trúc dữ liệu của

việc quản lý tệp tin ở bộ nhớ chính.

Tương tự như vậy, khi trao đổi thông tin giữa các tiến trình ở mục 2.4.1, người

ta có thể thay thế đôi lệnh OpenFile() và CloseFile(). Thay vì nối cứng vật lý sự

trao đổi thông tin, người ta được phép có một sự trao đổi thông tin không cần kết

nối vật lý: Tất cả mọi sự truy cập được thực hiện theo dãy tuần tự của chúng mà

không cần dùng lệnh OpenFile(). Tuy nhiên, điều đó thì không thật chính thức đối

với một cách tổ chức dữ liệu cục bộ: Thay vì truy cập tệp tin, người ta chỉ xếp đặt

một lần (thí dụ việc kiểm tra quyền truy cập, việc xem xét các khối tệp tin…)

người ta phải thực hiện điều đó mỗi lần truy cập, do đó dẫn tới chi phí quản lý

giảm thiểu đáng kể.

• Đọc và viết tệp tin (Read File/ Write File):

Gọi hệ thống như là một tham số nhận được sự tham chiếu tệp tin và một dung

lượng của bộ đệm để đọc hay viết. Nếu có một tệp tin mặc định và phù hợp với

dung lượng bộ đệm, do đó, tệp tin được thực hiện.

• Tìm kiếm tệp tin (Seek File):

Một tệp tin được tổ chức một cách tuần tự đơn giản và chiếm một vị trí, mà tại

đó, người ta có thể viết hay đọc. Vị trí tệp tin này không chỉ được mô phỏng như

những thông tin quản lý, mà còn có thể được thay thế bởi một chương trình ở

trong các hệ thống các tệp tin như vậy. Bằng việt xử lý tuần tự còn gọi là truy cập

tuần tự (sequential access), thí dụ khoảng từ tính của ổ đĩa mềm, người ta dẫn tới

việc truy cập tuỳ chọn còn gọi là truy cập ngẫu nhiên (random access). Điều đó thì

tiện lợi khi làm việc với ổ đĩa CD ROM.

Theo quan điểm hệ điều hành, các dịch vụ hệ thống nhận được sự trợ giúp một

cách khác nhau. Điều đó được bao hàm trong câu hỏi, liệu việc đọc/ viết có được

lưu trữ, hay liệu chương trình người sử dụng phải tự làm điều đó, khi phản ứng

của hệ thống đặt lên một trạng thái không bình thường (?). Nếu không có dữ liệu

nào có thể được đọc hay được viết, vì tại hàm Read() không có dữ liệu nào được

sử dụng, hay tại hàm Write() không có ổ đĩa nào sẵn sàng làm việc. Gần như hàm

Read() ở trong trường hợp này thì ngăn hãm tiến trình người sử dụng, còn hàm

Write() thì không. Vì lý do này, các dữ liệu được lưu trữ; khi bộ đệm tràn hay ổ

đĩa có khiếm khuyết, một thông báo lỗi được đưa trở lại. Một cách thuận lợi, khi

đó có nhiều chức nằng được bổ sung như: DeleteFile(), RemameFile(),

CopyFile(), AppendFile(), FlushBuffer(),…Tất cả đều phụ thuộc vào hệ điều hành

một cách mạnh mẽ.

4.4.2. Các chức năng truy cập ở trong Unix

Ở trong hệ điều hành Unix, các gọi hệ thống có dạng fd=creat(name, mode) và

fd=open(name, mode) đã cung cấp cho ta một số bộ mô tả tệp tin (fd: file

discriptor). Nó chính là sự tham chiếu đối với tất cả sự truy cập khác nhau, như:

+ read (fd, buffer, nbytes)

+ write (fd, buffer, nbytes) viết n Bytes từ một bộ đệm;

+ close (fd) viết một tệp tin.

đọc n Bytes ở trong bộ đệm;

Bộ mô tả tệp tin này là chỉ số (Index) ở trong một trường của bảng mô tả tệp tin

(file descript table). Số lượng các tệp tin và số lượng của sự điền vào (tức số lượng

lớn nhất đối với fd) là cố định, nó được thông báo khi có sự dịch đổi của hệ điều

hành; đồng thời, nó xác định độ lớn của cấu trúc quản lý đối với các tệp tin được

lưu trữ ở trong cấu trúc người sử dụng của một tiến trình.

Bộ mô tả tệp tin này đóng vai trò quan trọng trong hệ điều hành Unix. Theo

tiêu chuẩn, trước khi khởi xướng một tiến trình (chẳng hạn một chương trình), bộ

mô tả tệp tin được ghi nhớ: fd =0 cho việc nhập số liệu (stdin), fd =1 cho việc xuất

số liệu (stdout) và fd=2 cho việc xuất số liệu khi có lỗi (stderr). Ở trong Unix,

người ta lợi dụng điều này để kết nối các chương trình với nhau, nhằm dẫn tới một

chức năng nào đó. Ở mục 2.4, chúng ta đã làm quan với cấu trúc trao đổi thông tin

pipe, thí dụ:

Programm1 | Programm2 | … | ProgrammN

Để thực hiện dòng lệnh này, tiến trình cha thiết đặt nhiều tiến trình con và tạo

ra đối với mỗi một sự kết nối trao đổi thông tin một pipe. Sau đó, tiến trình cha

khởi xướng các bộ mô tả tệp tin (file descriptors) cho mỗi tiến trình; khi đó, chúng

sẽ dẫn tới: pipe vào với fd =1 ở tiến trình gởi đi, pipe ra với fd =0 ở tiến trình

nhận. Hình 4.8 mô tả một hệ thống pipe ở trong Unix.

Hình 4.8-----------------

Việc sắp xếp các bộ mô tả tệp tin chỉ là sự quy ước; mỗi tiến trình có thể đạt

được các sự sắp xếp các bộ mô tả tệp tin khác nhau qua việc đóng và mở có mục

đích các tệp tin: Khi mở, bộ mô tả tệp tin trống với con số hệ thống nhỏ nhất được

sử dụng đầu tiên.

4.4.3. Các chức năng truy cập tệp tin ở Windows NT

Các chức năng cơ bản đối với việc truy cập tệp tin được tóm lược như là những

phương pháp về thiết laap các thuộc tính tệp tin. Các phương pháp hiệu nghiệm kể

trên còn dẫn tới nhiều chức năng đối với các tệp tin như FlushBuffer() cũng như

các tác vụ thư mục đặc trưng (đọc, viết, tìm kiếm thư mục…). Nói chung, một bản

phác thảo được quan tâm đó là: Mọi tác vụ dù có cấu trúc như thế nào đều có thể

thay đổi trên bộ nhớ quảng đại, thì chúng cũng được thực thi như là những biến

đổi nhân tử (atomar transaction). Thuộc cái đó còn có một dịch vụ đặc biệt gọi là

dịch vụ đăng ký tệp tin (log file service: LFS); mỗi lần truy cập tệp tin, dịch vụ

này được gọi bởi nhân hệ điều hành và viết bản ghi đăng ký cho hệ thống tệp tin.

Trước khi các tệp tin riêng lẻ được thay đổi trên bộ nhớ quảng đại (nhờ một biến

cố), do đó, các bản ghi đăng ký (log records) của tất cả các tác vụ (đối với một

biến cố) được viết trên bộ nhớ quảng đại. Bản phác thảo được chỉ ra bởi trình viết

trước luc đăng ký (write ahead logging) đã tạo điều kiện để viết lại hệ thống tệp

tin một cách sạch sẽ khi hệ thống có sự cố. Nếu sự cố xảy ra trước khi viết vào bộ

đệm dùng để đăng ký (log buffer), do đó, tất cả các tác vụ bị lảng quên và vì thế

phải thực hiện mới mẽ từ đầu. Nếu sự cố xảy ra giữa khoảng kết thúc đăng ký I/O

và kết thúc tệp tin I/O, khi đó, cần phải kiểm tra khi cho máy hoạt động trở lại,

phải xem xét và hiệu chỉnh chỗ nào đã thực hiện việc ghi chép, chỗ nào chưa (?).

Sau mỗi tình huống, những tác vụ còn sai hỏng đối với mỗi biến cố được gọi tới

và được thực hiện tiếp tục.

Tuy nhiên, bản phác thảo này có một vài giả định quan trọng, chúng không

nhất thiết phải được thực hiện trong từng trường hợp. Do vậy, sự truyền đạt các số

liệu đăng ký phải hoàn toàn không có lỗi, tức là, tệp tin đăng ký nên linh động, vì

việc chuyển tải dữ liệu thường chứa đựng lỗi, do đó tệp tin sẽ không sử dụng

được. Nếu giả sử có một khiếm khuyết thụ động dẫn hệ thống tới một trạng thái an

toàn (fail save); nghĩa là một lỗi tích cực cũng chưa xoá được dữ liệu.

4.4.4. Các chức năng truy cập có cấu trúc

Những chức năng truy cập được trình bày cho tới nay là một loại đơn giản và

chúng chỉ mới có ý nghĩa tách chia các giải thuật về truy cập các tệp tin. Trong rất

nhiều hệ thống, có các tác vụ để tạo điều kiện thiết lập một sự truy cập có cấu trúc

tới tệp tin, mà việc truy cập này được hướng tới sự tổ chức logic của dữ liệu ở

trong tệp tin, sau đây sẽ lần lượt nói tới từng loại:

Các tệp tin tuần tự (sequential files):

Với các máy tính được nói ở trên, người ta đã xử lý các danh sách dữ liệu dài,

mà chúng được tổ chức như là những bản ghi được sắp xếp một cách tuần tự. Vì

những bàn ghi tồn tại ở những tệp tin rộng rãi ở trên đĩa mềm và lần lượt được xử

lý. Hình thức tổ chức này đạt được thời gian hơi lâu. Kiểu tệp tin theo ngôn ngữ

Pascal xuất phát từ các tác vụ đọc/ viết tuần tự của toàn bộ các bản ghi dữ liệu

trong khoảng hai tác vụ put() và get().

Tuy nhiên, nếu người ta muốn truy cập trên các dữ liệu ở trong dãy tuần tự

khác, do đó, điều đó xảy ra lại càng vô cùng chậm.

Các tệp tin tuỳ chọn (random access files):

Nhược điểm nêu ở trên nhằm dẫn tới việc khắc phục một cơ chế tệp tin, mà nó

cho phép một sự truy cập trên bản ghi số liệu được sắp xếp theo một dãy tuần tự

bất kỳ. Ý tưởng này có thể được thực hiện bởi sự tạo lập của hệ thống ổ đĩa cứng.

Hầu hết các hệ thống tệp tin đều tạo điều kiện cho kiểu truy cập này nhờ việc biểu

thị vị trí truy cập tệp tin.

Khi truy cập tệp tin tuỳ chọn hay tuần tự, một kiểu truy cập này được thực hiện

nhờ một kiểu khác; tuy nhiên, nó không nhằm mục đích từ bỏ một loại nào cả.

Người ta có thể thực hiện các tệp tin tuần tự trên nhiều hướng khác nhau của ổ đĩa.

Đối với các tệp tin tuỳ chọn thì điều đó không có lợi lắm.

Tuy nhiên, nếu có một cơ chế nội dung tệp tin được đưa ra, thì người ta thấy

rằng, tiến hành truy cập cả hai kiểu sẽ chậm hơn một kiểu. Tóm lại, người ta phải

tôn trọng cơ chế tệp tin và phải thực thi một cách hiệu nghiệm bằng các phương

tiện điều hành hiện có. Từ lý do này, trong các hệ thống ngân hàng dữ liệu còn có

những phương pháp truy cập hiệu nghiệm hơn.

Các tệp tin chỉ số tuần tự (index sequential files):

Loại tệp tin này được cấu thành từ các bản ghi dữ liệu (data records), chúng

được sắp xếp theo một tiêu chuẩn gọi là sắp xếp theo chìa khoá (key) và khởi đầu

của tệp tin là một chỉ số. Trong thư mục chỉ số, các kiểu “đóng/mở” bằng chìa

khoá được kiến tạo và được thực thi (thí dụ kiểu điền vào các tệp tin quản lý nhân

sự: họ tên, ngày sinh, quê quán…); người ta có thể truy cập nhanh chóng từng

phần của tệp tin; từng phần này lại được trợ cứu một khoảng giá trị thích ứng của

mỗi chìa khoá. Vì một kiểu cấu trúc như thế thì đặc trưng cho tất cả các hệ thống

tệp tin của các thư mục. Chúng ta có thể nhìn thấy điều này một cách chính xác

hơn: Hình 4.9 chỉ ra cấu trúc kiểu chỉ số với một thí dụ về tệp tin quản lý nhân sự.

Tệp tin này được sắp xếp theo một chìa khoá, thí dụ theo lứa tuổi. Các bản ghi dữ

liệu riêng lẻ được tạo lập qua mũi tên xuất phát từ bậc số 0.

Hình 4.9****************************

Chìa khoá lớn nhất (con số lớn nhất) của một tệp tin (ô hình chữ nhật như hình

4.9) bắt đầu từ chỉ số của bậc số 0 được mô tả ở chỉ số của bậc số 1; chìa khoá lớn

nhất của một đoạn tệp tin của bậc số 1được chỉ ra ở chỉ số của bậc số 2… Nếu

người ta tìm bản ghi dữ liệu của một chìa khoá xác định x, do đó, người ta phải

xác định khoảng xuất phát của chỉ số thứ 2, mà trong khoảng này tồn tại chìa khoá

cần tìm, và xuất phát từ giới hạn trên của khoảng này, nhờ bậc sắp xếp, các tệp tin

tuần tự dịch chuyển từ dưới lên cho tới khi người ta tìm thấy con số của bản ghi dữ

liệu. Sau đó, người ta có thể đọc bản ghi dữ liệu mà nó được tạo ra có mục đích từ

tệp tin.

Nếu người ta thực nghiệm để mô tả cấu trúc logic cho các đối tượng vật lý - vết

đường (track), hình trụ (cylinder), hình quạt (sector), do đó người ta có thể dễ

dàng nhận được vấn đề để tái bản các bản ghi dữ liệu và để tổ chức bản ghi một

cách mới mẽ. Thí dụ, việc tổ chức bản ghi với chìa khóa số 41 (xem hình 4.9) để

tạo nên những vấn đề tương đối đầy đủ, vì mỗi hộp chữ nhật có khả năng lớn nhất

là 3 chìa khoá và nó luôn luôn chứa đựng sẵn sàng 3 chìa khoá này. Do đó, chúng

cần tới các cấu trúc trợ giúp cho việc tổ chức các dòng dữ liệu phát sinh khi thay

đổi thường xuyên các dữ liệu và chúng đòi hỏi ngay một bản ghi mới và đầy đủ

tệp tin. Đặc biệt, điều đó xuất hiện khi tổ chức dữ liệu với rất nhiều chìa khóa và

thường hay thay đổi. Nếu chỉ số thư mục cho ta biết nội dùng thư mục của một hệ

thống các tệp tin và với các chìa khoá này, chúng chứa đựng sự tham chiếu tệp tin

(tên tệp tin, số tệp tin…) của bộ nhớ quảng đại. Đối với một hệ thống tệp tin hiệu

nghiệm, nó thì khó thích hợp để tổ chức các chìa khóa thành các chỉ số thư mục

theo sơ đồ khác nhau, mà sơ đồ này cho phép một sự tìm kiếm nhanh như là việc

bổ sung vào hay lấy đi linh hoạt các chìa khóa.

Thêm vào đó, chúng ta thực hiện 2 thay đổi. Đầu tiên chúng tag hi chép mỗi

chìa khoá vào một nút của cây thư mục chỉ một lần; điều này tiết kiệm được không

gian bộ nhớ và thời gian tìm kiếm. Sau đó, chúng ta sẽ đem lại một ý nghĩa khác

cho kiểu này: Trong hình 4.9, đầu tiên, chúng ta phải quyết định trên một bậc, chìa

khóa cần tìm để sắp xếp thì ở chỗ nào (?). Nếu chúng ta tìm thấy, thí dụ chìa khoá

số 60, do đó, chúng ta nhận biết nó thuộc chỉ số bậc số 2, tức là chìa khoá này thì

lớn hơn 48 và nhỏ hơn 99, và cho nên nó là loại được tiếp tục dẫn tới cho đến số

99. Tác vụ so sánh giữa các chìa khoá có tính nguyên tắc này được chúng ta sử

dụng để khảo sát kết quả trong khoảng giới hạn này (60 tới 99) và không nối các

cành vào khoảng giới hạn này, mà vào khoảng tự tạo. Bây giờ, cành này sẽ là một

khoảng sơ đồ cây trung gian được kết nối giữa các chìa khoá và được dẫn tới các

chìa khoá mà chúng nằm trong giá trị giữa 2 khoá nói trên. Mỗi nút chứa đựng

nhiều nhất m sự tách nhánh và với m-1 chìa khóa. Chúng ta nhận thấy các lá của

cây (hay các bản ghi dữ liệu riêng lẻ) hình như không thuộc cây lúc đầu. Hình như

4.10 là một cây như thế, với nhiều nhất 3 chìa khóa trên mỗi hộp chìa khóa, mà ở

đó sự kết nối tới các lá cây được biểu thị bởi các mũi tên.

Hình 4.10******************************

Chúng ta có thể tạo lập một cách dễ dàng một cây thư mục như thế. Chúng ta

xuất phát từ hộp chìa khóa bậc số 0 và điền đầy hộp đầu tiên này cho đến khi đầy

tràn. Chìa khóa tiếp theo (thí dụ số 37) dịch lên phía trên với chỉ số của bậc số 1.

Hộp chìa khóa tiếp theo lại được làm đầy và khi đó chìa khóa tiếp theo (thí dụ chìa

khóa số 56) lại được dịch lên phía trên. Điều đó được thực hiện cho đến cuối bản

ghi chìa khóa. Nếu chìa khóa cuối cùng là chìa khóa thứ m, do đó, nó sẽ không

dịch lên bậc số cao hơn, khi đó, chúng ta tách chia m chìa khóa thành 2 hộp chìa

khóa khác nhau, theo hướng nhìn xuống dưới. Bây giờ nếu trên mặt bằng kế cạnh

cao hơn, hộp chìa khóa đầu tiên đã đầy tràn, do đó, tương tự như ở bậc thấp hơn, ở

đây sẽ được sử trí: chìa khóa được đếm đầu tiên tới một hộp có chỉ số của bậc ở

đó.

Với cấu trúc cây mới này, chúng ta đã đạt được một ưu điểm nữa để truy cập

nhanh hơn: chúng ta có thể kết hợp một cách dễ dàng các chìa khoá bổ sung. Ở

đây, chúng xuất phát từ phía trên rồi lần lượt đi qua cây và tìm khoảng nào mà

chìa khóa tồn tại. Nếu chìa khóa chưa hề tồn tại, thì, chúng ta dừng lại một lá cây.

Sauk hi chỉ định tại một lá cây như thế, bây giờ chúng ta kết hợp với chìa khóa đã

có của mình. Nếu hộp chìa khoá đã đi theo qua, do vậy, chúng ta có thể thử

nghiệm một lần, di chuyển các chìa khoá dư ra ở trong hộp theo hướng từ trái qua

phải, mà ở đó, tất nhiên, chìa khoá ở bậc kế cạnh được dự kiến dịch chuyển tới.

Tuy nhiên, độc lập với điều đó, một giải thuật kết hợp được thiết lập như sau:

+ Người ata phân chia hộp chìa khóa có m chìa khóa thành 2 hộp với các chìa

khóa S₁,…,S_[m/2]-1, S_[m/2]+1,…,S_m.

+Người ta di chuyển chìa khoá S_[m/2]ở giữa lên trên ở bậc gần đó.

+ Trường hợp ở đó hộp chìa khóa đã chạy qua, thì người ta sẽ xử lý tại đây.

Tác vụ xoá bỏ các chìa khóa thì được phân tích ngược lại:

Bây giờ, chúng ta lưu ý rằng, chúng ta đã tạo ra được một cây mà lá cây đều ở

trên một bình diện như nhau và số lượng các nhánh bị tách ra là như nhau. Do đó,

chúng ta nhận thấy rằng, các hộp chìa khoá được điền đầy một cách thoả mãn với

tối đa m nhánh và m-1 chìa khóa thì một nữa các nhánh [m/2] thực chất được sử

dụng. Khi đó, ở gốc cây có thể xảy ra trường hợp: chỉ tồn tại 1 chìa khóa với 2

nhánh, tuy rằng con số thực chất là m nhánh.

Một loại cây cho cấu trúc dữ liệu như vậy có tên gọi là cây B (B-Tree) do

D.Comer đề xướng (1979). Xem hình 4.10 ở trên, ta nhận thấy: Về hình thức, cây

B là một cây được diễn giải như sau:

(1). Mỗi cành cũng như mỗi nút (tới gốc và lá ) được toả ra tối thiểu k = [m/2]

và tối đa k=m cành.

(2). Mỗi nút chứa đựng k-1 chìa khoá (hay chỉ số)

(3). Tất cả các lá đều ở trên một bình diện. Chúng ta lưu ý rằng, những là nào

không chứa đựng chìa khóa thì không được quan tâm.

Một cây như vậy được gọi là cây bậc m. Người ta lưu ý rằng, với tổng số chìa

khóa ở trên cây là N thì chúng ta có N+1 lá ở bậc thấp nhất. (Vì sao? sẽ được giải

thích như dưới đây). Cây B có thể đi qua một cách nhanh chóng: Gốc cây có tối

thiểu hai cành và mỗi cành trong bậc kế cạnh lại có tối thiểu [m/2] cành, do vậy, ở

bậc kế n tồn tại tối thiểu một số cành là:

2.[m/2].[m/2]…= 2.[m/2]^n-1.

(4.1)

Cho nên, đối với số lượng các bậc cần dùng (gọi là dãy tuần tự tìm kiếm) với N

chìa khoá và N+1 lá cây thì sẽ dẫn tới điều kiện sau đây:

N+1≥ [m/2]^n-1

Hay: log_[m/2](N+1)/2 ≥ n-1

(4.2)

(4.3)

Trong đó, người ta gọi N: số chìa khoá hay số lá cây; n: số bậc; m: số cành cây.

Điều đó đã đem lại một sự tiết kiệm thời gian rất nhiều, thí dụ: khi m=200 và

N=1,98.10⁶thì theo điều kiện (4.3) chúng ta cần tới:

n-1 <= log₁₀₀(0,99.10⁶) = log₁₀₀(0,99) +log₁₀₀(100³)< 3.

Hay : 3≥ n-1

Để thoả mãn bất phương trình cuối cùng, người ta nhận thấy vế trái của nó chỉ

có thể là n-1 =2; khi đó bậc tối đa của cây B cho ví dụ này là n=3. Tóm lại, với

chìa khóa đã cho và bậc tối đa của cây đã xác định, tệp tin sẽ được tìm thấy một

cách dễ dàng! Điều đó cho thấy các cây B có khuynh hướng tự làm thật thấp

xuống khi số lượng điều vào các dữ liệu gia tăng lớn lên.

Có rất nhiều hình thái khác nhau của cây B, bằng cách, người ta có thể chọn

cho mỗi bậc giá trị m khác nhau. Về nguyên tắc, điều đó không làm thay đổi thuật

toán, mà nó chỉ là vấn đề dẫn xuất cấu trúc cây. Sau đây, chúng ta muốn khảo sát

một khả năng quan trọng khác, để làm gia tăng ý nghĩa thực tiễn: nó được các hệ

điều hành và các ngân hàng dữ liệu áp dụng một cách rộng rãi.

Ý tưởng cơ bản để cải tiến cấu trúc cây được đơn giản nhờ lý thuyết cây B là ở

chỗ: không chỉ sử dụng các hộp đầy chìa khóa (còn gọi là các phân đoạn), mà còn

chia nhỏ một phân đoạn thành hai phân đoạn mới khi có các bản ghi dữ liệu bổ

sung, và còn phản ảnh các thay đổi trong chỉ số của bậc kế cạnh. Các phân đoạn

được liên kết năng động với nhau qua bộ chỉ thị. Sự điền đầy của hai hộp chìa

khóa mới có thể rất hạn hẹp. Để cải thiện điều này, người ta có thể xem xét tới các

chìa khóa có ý nghĩa ở phía trên của các nút kế cạnh đã được điều đầy hơn, do đó,

chúng ta đạt được một sự cân bằng và làm đầy hộp chìa khóa mới một cách hoàn

hảo hơn. Ý tưởng này được trình bày trong một giải thuật duy nhất như sau:

•

Người ta thâu tóm hộp chìa khóa có m-1 chìa khóa, hộp chìa khóa kế

cạnh có m chìa khoá cũng như các chìa khóa khác thuộc bậc kế cạnh cao hơn tới

một hộp duy nhất. Bấy giờ, hộp này chứa đựng các chìa khóa S₁, S₂,. ..,S_2n.

•

Người ta phân chia các chìa khóa trong 3 hộp với số các chìa khóa cho

mỗi hộp [(2m-2)/3],[(2m-1)/3] và [2m/3]. Khi đó, hai chìa khóa S_Avà S_Bvới các

chỉ số A và B đi lên phía trên với bậc có chỉ số cao hơn. A và B được biểu diễn

bởi các biểu thức:

A = [(2m-2)/3] +1

B = [(2m-1)/3] +1 + [(2m-1)/3] +1

(4.4)

(4.5)

Bấy giờ, mỗi một trong 3 phân đoạn thì không phải một nửa mà khoảng 2/3

được làm đầy bởi các chìa khóa; do đó, đối diện với cây B, người ta nhận được

một cây cải tiến hơn; cây mới này được biểu thị là cây B^*(B^*- tree). Hình 4.11 ở

dưới cho thấy kết quả của việc sử dụng chìa khóa số 41 ở trong đây được chỉ ra

trong hình 4.10 ở trên: hình 4.11 (a) là cây B, còn hình 4.11(b) là cây B^*.

Hình 4.11***********************************

Một cách hình thức, theo định nghĩa của cây B và cây B* được pahan biệt qua

điều kiện thay đổi (điều kiện 1 được nêu ở trên) như sau:

1). Mỗi nhánh cũng như mỗi nút (tới gốc và lá) được lẻ nhánh thêm tối thiểu

k= (2m-1)/3 và tối đa m cành.

2). Gốc có tối thiểu 2 và tối đa 2[(2m-1)/3]+1 sự phân nhánh. Do đó, gốc cây

có thể được phân chia thành 2 hộp chìa khóa với số chìa khóa của mỗi hộp [(2m-

2)/3] (với lưu ý cộng thêm 1 chìa cho gốc mới ).

Theo D.Comer (1979), còn có nhiều dạng khác nữa của cây B; với giáo trình

nguyên lý hệ điều hành, một sự trình bày về cây B như vậy là vừa đủ.

Tệp tin đảo ngược (inverted files) và đa danh sách (multi- liste):

Ở cơ chế tệp tin này, những thông tin về các bản ghi dữ liệu đã được sắp xếp

(một cách tuần từ) được sắp xếp lại theo các chìa khóa khác nhau. Đối với mỗi

chìa khóa, các tham chiếu tới các bản ghi dữ liệu được viết thành một chỉ số ở đầu

tệp tin; chìa khóa cũng được chứa đựng trong các bản ghi này. Hình 4.12 chỉ ra

một tệp tin với đa danh sách.

Hình 4.12*******************************

Khi việc điền vào bắt đầu, các danh sách được sắp xếp theo chỉ số của bản ghi,

xem chìa khóa 1 và 2 (hình 4.12 ở trên). Tuy nhiên, người ta cũng có thể sắp xếp

theo chỉ số các giá trị tăng hay giảm của các chìa khóa, do đó, cấu trúc phân nhánh

ở trong hình 4.12 thực ra vẫn chưa rõ ràng. Điều đó được chỉ ra với danh sách các

bản ghi đối với chìa khóa m (thí dụ trong hình 4.12 là 1, 3, 2, 6, 5, 8).

Nếu chúng ta kết hợp tất cả các bộ chỉ thị của một chìa khóa trong chỉ số bắt

đàu của tệp tin và không viết chúng vào trong các bản ghi dữ liệu, do đó, điều này

được biểu thị là tệp tin được đảo ngược: Khái niệm đảo ngược được rút ra từ viện

chứng, rằng, chúng ta không khai thác giá trị chìa khóa từ bản ghi, ngược lại, bản

ghi được khai thác từ chìa khóa.

Các tệp tin đảo ngược thích hợp đặc biệt tốt đối với việc đọc chọn có quan hệ

với một chìa khóa xác định.

Một sự thực thi hiệu nghiệm cách tổ chức tệp tin như cấu trúc vừa nêu ở trên

được thực hiện ở trong hệ điều hành các máy tính lớn. Từ lý do này, hệ điều hành

Unix với tư cách là một hệ điều hành máy tính đứng vững lâu dài đối với các áp

dụng về ngân hàng dữ liệu; vì trong các chương trình ứng dụng, người ta không

cần thiết phải tạo lập trên những tác vụ cao hơn. Các lớp trung gian giữa các tác vụ

liên hiệp (complex) và cơ chế đơn giản của các hàm tuỳ chọn ReadFile() và

WriteFile() của hệ điều hành phải được mỗi người sử dụng tự viết lấy, mà với điều

đó, sự cảnh giới của ngân hàng dữ liệu che phủ lên hệ điều hành Unix với mức độ

cao. Trong khi đó, sự tư duy kiểu này còn có vai trò đáng kể trong nhiều áp dụng

đặc biệt, vì những bộ vi xử lý với ấn bản mới có tốc độ truy cập nhanh và vì các ổ

đĩa đời mới đã làm cân bằng tổn hao của một lớp trung gian rất nhiều.

4.4.5. Các tệp tin được ảnh xạ bộ nhớ (memory mapping files)

Các tệp tin với việc truy cập tuỳ chọn thường được làm việc mạnh mẽ trên bộ

nhớ chính (RAM). Người ta có thể nghiên cứu tiếp sự phân tích như sau: Người ta

có thể xem xét các tệp tin ở trên bộ nhớ quảng đại như là một sự kế tục của bộ nhớ

chính trên bộ nhớ quảng đại. Cho nên, điều đó đặt ra, phải thực hiện bước tiếp

theo, và một cách đúng mức (trước sau như một) phải tái tạo một sự kết nối trực

tiếp một tệp tin với một khoảng của bộ nhớ chính, mà tệp tin được tách chia thành

những khoảng có chiều dài bằng một trang. Khi đó, người ta gọi là tệp tin ảnh xạ

bộ nhớ; tương tự, bộ nhớ cũng được phân chia thành các trang.

Một kiểu kết nối như thế sẽ đạt được bởi gọi hệ thống; trong đó, các trang của

một tệp tin được ảnh xạ như là một sự thay thế các trang bộ nhớ chính ở trong

không gian địa chỉ ảo của một tiến trình. Hình 4.13 minh hoạ điều này một cách

đầy đủ.

Việc thực thi một cơ chế như vậy thì tương đối đơn giản: Khi một miền mà

trên đó các trang của một tiến trình được nạp, do đó, miền của tệp tin được chỉ ra ở

trên bộ nhớ quảng đại. Điều đó, mang lại những lợi thế khác nhau như sau:

+ Độ nhanh nhạy: