Bài giảng Cấu trúc máy tính - Bài 5: Bộ nhớ ngoài

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í dụ 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. 
 Block và Record 
 Bản ghi vật lý hay khối là đơn vị thông tin thực sự được trao đổi với thiết bị lưu trữ. 
 Còn bản ghi logic là tập hợp thông tin được coi là đơn vị toàn vẹn nhìn từ phía người 
 dùng, ví dụ bản ghi sinh viên. 
 Với hai khái niệm trên, ta có các quan hệ sau về độ dài tương đối giữa chúng: 
 Một khối = một bản ghi. 
 Một khối = nhiều bản ghi. 
 Một bản ghi = nhiều khối. 
 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 phân 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 (Directory): 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. 
120 IT101_Bai 5_v1.0010110225 
 Bài 5: Bộ nhớ ngoài
 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ệ điều hành, hệ thống file thường cung cấp các 
 công cụ: 
 Các phương pháp truy cập: xác định, 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 hệ thống file 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. Hệ thống file 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. 
 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 của 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 hệ thống file, theo đó thường 
 khi truy cập thông tin thường scan các khối 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ế hệ thống file. 
 Trong các hệ thống dùng tổ chức bộ nhớ theo trang, khối 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 khối 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. 
5.2.2. Phân bố liên tục, không liên tục 
 Có hai hình thức phân bố: liên tục và không liên tục. 
 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. 
IT101_Bai 5_v1.0010110225 121 
 Bài 5: Bộ nhớ ngoài
 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. 
 Tuy 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ả. 
 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 khối 
 Hình thức phân bố theo khối 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, hệ thống file cố gắng cấp phát khối trống gần nhất. Khi truy cập 
 dữ liệu, hệ thống file xác định số blokc và sau đó số Sector trong khối. Có 3 hình thức 
 phân bố theo khối: chuỗi block/block chaining, chuỗi block chỉ số/index block và 
 bảng ánh xạ block. 
5.2.3. Các sơ đồ tổ chức hệ thống file theo khối 
 Chuỗi các block dữ liệu 
 Trong sơ đồ này, bản ghi trong directory trỏ đến khối đầu tiên của file. Mỗi khối (có 
 độ dài cố định) gồm hai phần: phần header chứa con trỏ đến khối tiếp theo (khối cuối 
 cùng - con trỏ đặc biệt để báo hiệu) và phần dữ liệu. Đơn vị cấp phát nhỏ nhất là khối. 
 Để đọc bản ghi, đầu tiên cần tìm đến khối sau đó đến Sector trong khối chứa bản ghi. 
 Quá trình tìm kiếm phải bắt đầu duyệt từ khối đầu tiên, theo các con trỏ đến khối cần 
 tìm. Như thế nếu khối 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 khối 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 khối liên kết 2 chiều, mỗi khối có 2 con trỏ, 1 trỏ tới khối 
 tiếp theo và 1 trỏ tới khối trước. 
122 IT101_Bai 5_v1.0010110225 
 Bài 5: Bộ nhớ ngoài
 Directory
 File A
 Header Header Header
 Data Data Data
 Data Block 0 Data Block 1 Data Block n 
 Hình 5.2.3-1: Chuỗi các block 
 Sơ đồ chuỗi block chỉ mục 
 Trong sơ đồ này, các chỉ mục (Index) được chứa trong các khối chỉ số. Mỗi khối chỉ 
 số chứa số lượng cố định các phần tử, mỗi phần tử chứa con trỏ đến khối dữ liệu. Nếu 
 một index block không đủ, hệ thống dùng chuỗi các chỉ số 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 khối 
 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 khối dữ liệu. Để tăng tốc độ, có thể bố trí các chỉ số block nằm trên 
 vùng liên tục trong bộ nhớ ngoài. Khi tìm thấy vị trí khối dữ liệu thì chỉ cần nạp khối 
 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 đá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 chỉ số. 
 Directory
 Index Block 0 Index Block n
 File A
 Header Header
 Pointer Pointer
 Pointer ...
 ... ...
 Data Data Data
 Hình 5.2.3-2: Sơ đồ chuỗi index block 
 Sơ đồ 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ố khối có thể dễ dàng tính toán được vị trí khối trên bộ nhớ ngoài. Sơ 
 đồ này sử dụng bảng ánh xạ khối, mỗi dòng chứa thông tin ánh xạ cho 1 khối. 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 khối dữ 
IT101_Bai 5_v1.0010110225 123 
 Bài 5: Bộ nhớ ngoài
 liệu đầu tiên của file. Mỗi dòng của bảng ánh xạ chứa số của khối 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 khối 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 khối nào tiếp theo – nó là khối cuối cùng. 
 Các dòng ánh xạ của khối trống chứa giá trị đặc biệt khác thể hiện rằng đó là khối 
 trống, có thể cấp phát. Hệ thống có thể tra cứu bảng ánh xạ để tìm các khối trống, 
 hoặc lưu thông tin khối 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 khối trống và vị trí tương đối của chúng so với các 
 khối khác, từ đó khi cần cấp phát có thể chọn các khối gần với khối thuộc cùng 1 file 
 một cách dễ dàng, nâng cao tốc độ truy cập. 
 Hình 5.2.3-3: Bảng ánh xạ khối 
5.2.4. Điều khiể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 file
 f1 f2 ...
 truy cập, một trong các sơ đồ đơn giản nhất user
 là sử dụng ma trận điều khiển quyền truy cập u1 R=0 R=1
 (hình 5.2.4). Trong đó một chiều là các ID u2 R=1 R=1
 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 Hình 5.2.4 
 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. 
 Mô tả file – File Descriptor 
 File Descriptor là bản ghi lưu đầy đủ các thông tin về file mà hệ điều hành 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: 
124 IT101_Bai 5_v1.0010110225 
 Bài 5: Bộ nhớ ngoài
 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. 
IT101_Bai 5_v1.0010110225 125 
 Bài 5: Bộ nhớ ngoài
TÓM LƯỢC CUỐI BÀI 
Các bạn đã được học về Bộ nhớ ngoài. 
Chúng ta cần ghi nhớ các vấn đề sau: 
 Hiểu được về đĩa từ: 
 o Cấu tạo của đĩa từ. 
 o Tối ưu theo thời gian định vị Track. 
 o Tối ưu theo thời gian trễ. 
 Hiểu được về hệ thống file: 
 o Phân bố liên tục và không liên tục. 
 o Các sơ đồ tổ chức hệ thống file. 
 o Điều khiển truy cập. 
 Làm được các bài tập về hệ thống file. 
126 IT101_Bai 5_v1.0010110225 
 Bài 5: Bộ nhớ ngoài
CÂU HỎI TỰ LUẬN 
Câu 1. Giả sử một hệ thống có 3 loại thiết bị là Máy in, Ổ Đĩa cứng và Ổ CD–ROM. Có 1 yêu 
cầu in tập tin DanhSach.doc, 1 yêu cầu đọc F1.txt từ đĩa cứng, 1 yêu cầu ghi ra F2.txt trên đĩa 
cứng. Hãy thể hiện bằng hình vẽ Bảng trạng thái thiết bị với 3 yêu cầu Cập/Xuất kể trên. 
Câu 2. Trong hai loại bộ nhớ là Bộ nhớ chính và Đĩa từ, loại nào là bộ nhớ sơ cấp, loại nào là bộ 
nhớ thứ cấp? Phân loại như vậy để làm gì? 
Câu 3. Trình bày thuật giải điều phối FCFS. 
Câu 4. Giả sử một Partition trên đĩa cứng được cài hệ tập tin FAT. Hãy thể hiện cấu trúc của 
Partition đó bằng hình vẽ. 
Câu 5. Trong một hệ tập tin FAT16, tập tin Vanban.doc có nội dung trải trên các liên cung 
(Cluster) 5, 3, 2. Hãy minh hoạ cấu trúc Đầu mục (Directory Entry) của tập tin này cùng nội 
dung bảng FAT. 
BÀI TẬP TRẮC NGHIỆM 
1. Máy tính PC sử dụng hệ thống cơ số nào để lưu trữ dữ liệu trên đĩa cứng? 
a) Hệ thập lục phân. b) Hệ thập phân. 
c) Hệ bát phân. d) Hệ nhị phân. 
2. Hệ điều hành thường được lưu trữ trong: 
a) ROM. b) RAM. 
c) Bộ nhớ ngoài. d) Bộ xử lí trung tâm (CPU). 
3. Khi khởi động máy tính, hệ điều hành được nạp vào: 
a) Bộ nhớ RAM. b) Bộ nhớ ROM. 
c) Bộ nhớ ngoài. d) Bộ xử lý trung tâm. 
4. Hệ điều hành đảm nhiệm việc nào trong những việc dưới đây? 
a) Soạn thảo văn bản. 
b) Giao tiếp với ổ đĩa cứng, quản lí bộ nhớ trong. 
c) Chơi trò chơi điện tử. 
d) Giải các bài toán trên máy tính. 
5. Tệp tin thường được lưu trữ tại: 
a) RAM. b) ROM. 
c) Bộ xử lí trung tâm. d) Bộ nhớ ngoài. 
IT101_Bai 5_v1.0010110225 127 
 Bài 5: Bộ nhớ ngoài
6. Trong các câu sau câu nào không phải nhiệm vụ của hệ quản lý tệp? 
a) Tổ chức thông tin trên bộ nhớ ngoài. 
b) Cung cấp các dịch vụ để đọc/ ghi thông tin trên bộ nhớ ngoài dễ dàng. 
c) Đảm bảo cho các chương trình đang hoạt động trong hệ thống có thể đồng thời truy cập tới 
các tệp. 
d) Quản lí các thiết bị vật lý kết nối đến máy tính. 
7. Các tài nguyên điển hình thuộc phần cứng bao gồm: 
a) Thiết bị xử lý trung tâm (CPU). 
b) Bộ nhớ trong, hệ thống vào/ra (kênh, thiết bị điều khiển thiết bị vào/ra và thiết bị vào/ra). 
c) Bộ nhớ ngoài. 
d) Cả 3 đáp án trên đều đúng. 
128 IT101_Bai 5_v1.0010110225