Giáo trình Nguyên lý hệ điều hành

BỘ LAO ĐỘNG – THƯƠNG BINH VÀ XÃ HỘI 
TỔNG CỤC DẠY NGHỀ 
GIÁO TRÌNH 
Môn học: Nguyên lý hệ điều hành 
NGHỀ: QUẢN TRỊ MẠNG 
TRÌNH ĐỘ: CAO ĐẲNG NGH 
(Ban hành kèm theo Quyết định số:120/QĐ-TCDN ngày 25/02/2013 
của Tổng cục trưởng Tổng cục dạy nghề) 
Hà Nội, năm 2013 
TUYÊN BỐ BẢN QUYỀN: 
 Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể 
được phép dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và 
tham khảo. 
 Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh 
doanh thiếu lành mạnh sẽ bị nghiêm cấm. 
MÃ TÀI LIỆU: MH 10 
1 
LỜI GIỚI THIỆU 
 Trong hệ thống kiến thức chuyên ngành trang bị cho sinh viên 
nghề Quản trị mạng máy tính, môn học Nguyên lý hệ điều hành góp 
phần cung cấp những nội dung liên quan đến việc mô tả các phương 
pháp giải quyết các bài toán điều khiển hoạt động của hệ thống máy tính 
 Các nội dung chính được trình bày trong tài liệu này gồm các 
chương: 
 -Giới thiệu chung về hệ điều hành 
 - Điều khiển dữ liệu 
 - Điều khiển bộ nhớ 
 - Điều khiển CPU và Tiến trình 
 - Hệ điều hành đa xử lý 
Mặc dầu có rất nhiều cố gắng, nhưng không tránh khỏi những khiếm 
khuyết, rất mong nhận được sự đóng góp ý kiến của độc giả để giáo trình 
được hoàn thiện hơn. 
 Hà Nội, ngày 25 tháng 02 năm 2013 
Tham gia biên soạn 
 1. Chủ biên Ths. Nguyễn Văn Hưng 
 2. CN Trương Văn Hiền 
2 
MC LC 
LI GII THIU....................................................................................... 1 
CHNG 1:GII THIU CHUNG V H IU HÀNH ..................... 7 
1. Khái nim v h iu hành ........................................................... 7 
1.1. Tài nguyên h thng ...................................................................... 7 
1.2. Khái nim h iu hành ............................................................ 10 
2. Phân loi h iu hành .................................................................. 11 
2.1. Các thành phn ca h iu hành ............................................. 11 
2.2. Phân loi h iu hành .............................................................. 13 
2.3. Tính cht c bn ca h iu hành ...................................... 15 
2.4. Phân lp các chng trình trong thành phn iu khin ...... 16 
2.5. Chc nng c bn ca h iu hành ................................... 17 
2.6. Nhân ca h iu hành, ti h iu hành ............................. 20 
3. S lc lch s phát trin ca HH .......................................... 22 
Mc tiêu: nm c lch s phát trin h iu hành. .................. 22 
CÂU HI VÀ BÀI TP ............................................................................... 24 
CHNG 2: IU KHIN D LIU .................................................. 25 
1. Các phng pháp t chc và truy nhp d liu ............................. 26 
1.1. Các phng pháp t chc d liu ............................................ 26 
1.2. Các phng pháp truy nhp d liu ........................................ 28 
1.3 Chc nng ca h thng iu khin d liu .................... 29 
2. Bn ghi và khi ................................................................................. 30 
2.1. Bn ghi lôgic và bn ghi vt lý .................................................. 30 
2.2. Kt khi và tách khi ................................................................. 31 
3. iu khin buffer ........................................................................... 33 
3.1. Vai trò ca buffer....................................................................... 33 
3.2. S dng buffers......................................................................... 34 
3.3. iu khin buffer (vào ra d liu) .......................................... 35 
4. Quy trình iu khin chung vào ra ................................................ 37 
4.1 Các khi iu khin d liu .................................................... 37 
4.2 Ví d v s  chung iu khin vào ra trong h iu hành
 ............................................................................................................ 37 
3 
5. T chc lu tr d liu trên b nh ngoài ................................. 38 
Mc tiêu: Nm c cách thc t chc lu tr d liu, các 
phng pháp qun lý trên b nh ngoài. .............................................. 38 
5.1. Các khái nim c bn ................................................................ 38 
5.2. Các phng pháp qun lý không gian t do ............................. 39 
5.3. Các phng pháp cp phát không gian t do ........................... 41 
5.4. Lp lch cho a ................................................................... 44 
5.5. H file ........................................................................................ 44 
CÂU HI VÀ BÀI TP ............................................................................... 45 
CHNG 3: IU KHIN B NH ................................................... 47 
1. Qun lý và bo v b nh ............................................................... 47 
1.1. Mt s khái nim liên quan n b nh ................................ 47 
1.2. Qun lý phân phi b nh. Vn  bo v b nh .......... 48 
2. iu khin b nh liên tc theo a bài toán .................................. 50 
2.1. Chin lc gii hn tnh (cn c nh) .......................... 50 
2.2 Chin lc gii hn ng (cn thay i) .......................... 51 
2.3. Cách thc Overlay và swapping .................................................. 53 
2.4. Các phng thc phân phi vùng nh (first fit, best fit, worst 
fit) ....................................................................................................... 55 
3. iu khin b nh gián on ....................................................... 56 
3.1. T chc gián on .................................................................... 56 
3.2. Phân on ................................................................................... 58 
3.3. Phân trang .................................................................................... 62 
3.4. Kt hp phân on và phân trang ............................................. 65 
CÂU HI VÀ BÀI TP ............................................................................... 67 
CHNG 4: IU KHIN CPU, IU KHIN QUÁ TRÌNH ........... 68 
1. Các khái nim c bn ........................................................................ 68 
1.1.Khái nim quá trình ...................................................................... 68 
1.2. Quan h gia các quá trình ......................................................... 69 
2. Trng thái ca quá trình .................................................................... 70 
2.1.S  không gian trng thái (SNAIL) ...................................... 70 
2.2. Mt s khi iu khin quá trình ......................................... 72 
3. iu phi quá trình ........................................................................... 73 
3.1. Nguyên tc chung ........................................................................ 73 
3.2. Các trình lp lch (long term, short term) .............................. 73 
4. Các thut toán lp lch ..................................................................... 74 
4 
4.1. First Come First Served (FCFS)............................................... 74 
4.2. Shortest Job First (SJF) ............................................................. 74 
4.3. Shortest Remain Time (SRT) ................................................... 76 
4.4. Round Robin (RR) ..................................................................... 77 
4.5. Multi Level Queue (MLQ) ........................................................ 78 
4.6. Multi Level Feedback Queues (MLFQ) ................................... 79 
5. H thng ngt ................................................................................. 80 
5.1. Khái nim ngt ........................................................................... 80 
5.2. X lý ngt ................................................................................... 81 
6. Hin tng b tc ......................................................................... 83 
6.1. Khái niệm bế tắc ......................................................................... 83 
6.2. Các biện pháp phòng tránh bế tắc ............................................. 84 
6.3. Phát hin b tc ........................................................................ 84 
6.4. X lý b tc .............................................................................. 85 
6.5. Kt lun chung v phòng tránh b tc................................... 85 
CÂU HI VÀ BÀI TP ............................................................................... 87 
CHNG 5: H IU HÀNH A X LÝ .............................................. 88 
1. H iu hành a x lý tp trung ................................................... 89 
1.1 H thng a x lý ..................................................................... 89 
1.2. H iu hành a x lý tp trung ............................................ 91 
2. H iu hành a x lý phân tán ......................................................... 93 
2.1. Gii thiu h phân tán ................................................................ 93 
2.2. c im h phân tán ............................................................... 93 
CÂU HI VÀ BÀI TP ............................................................................... 94 
TÀI LIU THAM KHO........................................................................... 96 
5 
NGUYÊN LÝ HỆ ĐIỀU HÀNH 
Mã môn học:MH 10 
Vị trí, tính chất, ý nghĩa và vai trò môn học: 
- Vị trí: Môn học được bố trí sau khi sinh viên học xong các môn học chung, 
trước các môn học, mô đun đào tạo chuyên môn nghề. 
- Tính chất: Là môn học cơ sở. 
- Ý nghĩa và vai trò: Đây là môn học cơ sở ngành của các ngành liên quan 
đến công nghệ thông tin, cung cấp cho sinh viên các kiến thức cơ bản về hệ 
điều hành để làm nền tản cho việc lập trình giải quyết các vấn đề cần thiết, 
tối ưu hóa hệ thống máy tính. 
Mục tiêu của môn học: 
- Hiểu vai trò và chức năng của hệ điều hành trong hệ thống máy tính; 
- Biết các giai đoạn phát triển của hệ điều hành; 
- Hiểu các nguyên lý thiết kế, thực hiện của hệ điều hành; 
- Hiểu cách giải quyết các vấn đề phát sinh trong hệ điều hành. 
- Bố trí làm việc khoa học đảm bảo an toàn cho người và phương tiện học 
tập. 
 Nội dung chính của môn học (danh sách các chương mục...): 
Số 
TT 
Tên chương, mục 
Thời gian 
Tổng Lý Thực hành Kiểm 
6 
số thuyết tra* (LT 
hoặc TH) 
I Tổng quan về hệ điều 
hành 
5 5 0 0 
 Khái niệm về hệ điều hành 2 2 0 0 
 Phân loại hệ điều hành 2 2 0 0 
 Sơ lược lịch sử phát triển 
của HĐH 
1 1 0 0 
II Điều khiển dữ liệu 15 9 5 1 
 Các phương pháp tổ chức và 
truy nhập dữ liệu 
5 3 2 0 
 Bản ghi và khối 2 1 1 0 
 Điều khiển buffer 2 1 1 0 
 Quy trình chung điều khiển 
vào – ra 
2 2 0 0 
 Tổ chức lưu trữ dữ liệu trên 
bộ nhớ ngoài 
4 2 1 1 
III Điều khiển bộ nhớ 20 10 9 1 
 Quản lý và bảo vệ bộ nhớ 2 2 0 0 
 Điều khiển bộ nhớ liên tục 
theo đa bài toán 
8 3 5 0 
 Điều khiển bộ nhớ gián 
đoạn 
10 4 5 1 
IV Điều khiển CPU, Điều 
khiển quá trình 
25 12 12 1 
 Các khái niệm cơ bản 2 2 0 0 
 Trạng thái của quá trình 5 2 3 0 
 Điều phối quá trình 3 1 2 0 
 Các thuật toán lập lịch 10 4 6 0 
 Hệ thống ngắt 1 1 0 0 
 Hiện tượng bế tắc 4 2 1 1 
V Hệ điều hành đa xử lý 10 7 2 1 
 Hệ điều hành đa xử lý tập 
trung 
5 3 2 0 
 Hệ điều hành đa xử lý phân 
tán 
5 3 1 1 
Cộng 75 43 28 4 
7 
CHƯƠNG 1:GIỚI THIỆU CHUNG VỀ HỆ ĐIỀU HÀNH 
 Mã chương: MH10-01 
Mục tiêu: 
- Nắm được yêu cầu cần có hệ điều hành; 
- Nắm được khái niệm hệ điều hành, chức năng, phân loại và các thành phần 
cơ bản trong hệ điều hành; 
 - Thực hiện các thao tác an toàn với máy tính. 
1. Khái niệm về hệ điều hành 
Mục tiêu: Nắm được yêu cầu cần có hệ điều hành; 
 Nắm được khái niệm hệ điều hành. 
 1.1. Tài nguyên hệ thống 
 Tài nguyên của một trung tâm máy tính được tổng hợp từ ba thành tố, 
đó là tài nguyên về phần cứng, tài nguyên về phần mềm và tài nguyên về 
nguồn nhân lực của trung tâm máy tính đó. 
 Trong các tài liệu giới thiệu về một trung tâm máy tính bất kỳ, các số 
liệu thống kê về phần cứng (số lượng và chủng loại máy tính, hệ thống thiết bị 
8 
ngoại vi, khả năng liên kết với môi trường ngoài v.v) luôn là những yếu tố 
được quan tâm sớm nhất và là thành tố dễ nhận biết nhất về sức mạnh của 
trung tâm máy tính đó. 
 Tài nguyên về phần mềm cũng được chú ý thông qua các thông tin về 
hệ điều hành được sử dụng, về các phần mềm ứng dụng đã có tại cơ sở tính 
toán đó. Hiện nay, tại những trung tâm tính toán mạnh, giá trị (tính theo tiền) 
thực sự của tài nguyên phần mềm lại cao hơn và vượt trội nhiều so với giá trị 
của tài nguyên phần cứng. 
 Tài nguyên về nguồn nhân lực cũng được chú ý, tuy rằng trong một số 
trường hợp, thành tố này lại khó nhận biết và khó đánh giá hơn so hai loại tài 
nguyên đã nói ở trên. Năng lực về nguồn nhân lực trong hệ thống nhằm đảm 
bảo việc thực hiện chức năng bảo trì, phục vụ và phát triển hệ thống (kỹ sư hệ 
thống, kỹ thuật viên, thao tác viên v.v) thực sự lại đánh giá hơn rất nhiều so 
với phần cứng và phần mềm. 
 Tuy nhiên, trong giáo trình này, chúng ta hạn chế trong một phạm vi 
tiếp cận là mọi công việc của hệ điều hành bắt đầu từ hệ thống phần cứng có 
sẵn và hệ điều hành cần phải hoạt động nhằm phát huy cao nhất năng lực của 
hệ thống phần cứng đó và vì vậy chúng ta chỉ đề cập đến tài nguyên về phần 
cứng (có thể kể tới một phần về tài nguyên phần mềm) và định hướng tới vấn 
đề phát huy hiệu quả khai thác các tài nguyên đó. 
 Để định hướng tới mục tiêu phát huy hiệu quả các thành phần trong tài 
nguyên phần cứng, cần xem xét một số đặc trưng cơ bản và đánh giá giá trị 
của mỗi thành phần trong hệ thống phần cứng, hướng tới mục đích đưa ra 
được các chiến lược ưu tiên thích đáng (hoặc khả dụng) đối với mỗi thành 
phần khi xây dựng hệ thống các chương trình điều khiển sự hoạt động của 
máy tính. 
Theo cách tiếp cận của hệ điều hành, các tài nguyên điển hình thuộc 
phần cứng bao gồm: thiết bị xử lý trung tâm (CPU), bộ nhớ trong, và 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, bộ nhớ 
ngoài v.v). CPU và bộ nhớ trong thuộc và khu vực trung tâm còn hệ thống 
vào – ra thường được xếp vào khu vực ngoại vi của hệ thống máy tính. 
 Trong các thiết bị nói trên, đáng chú ý nhất phải kể đến là CPU và bộ 
nhớ trong. 
 Bộ xử lý trung tâm (Central Processing Unit-CPU) 
 Trước hết chúng ta xem xét về các đặc trưng liên quan đến CPU. Việc 
đánh giá tài nguyên CPU về cơ bản cũng dựa trên các đặc trưng này: tốc 
độ xử lý, độ dài từ máy, phương pháp thiết kế hệ lệnh máy trong CPU. 
 Tốc độ xử lý là thông số thể hiện mức độ làm việc nhanh chậm của 
CPU dựa trên các đơn vị biểu diễn ... l Block): chứa thông tin quản lý làm việc đối với 
File. Trong một số hệ điều hành thuật ngữ “thẻ File” có ý nghĩa thay thế 
tương đương. Trong khối này có những thông tin cụ thể về File tương ứng: số 
lượng bản ghi, bản ghi hiện thời, địa chỉ các khối liên kết v.v 
 Khối DCB (Data Control Block): chương trình người dùng được viết 
theo ngôn ngữ bậc cao thì chương tình dịch tạo DCB, còn nếu được viết theo 
hợp ngữ thì chương trình người dùng tạo DCB. Khối DCB chứa mọi thông tin 
liên quan đến điều khiển vào ra: tổ chức File, phương pháp truy nhập, địa chỉ 
các khối điều khiển liên quan v.v 
 Khối UCB (Unit Control Block): chứa thông tin về thiết bị vào ra, vật 
dẫn ngoài tương ứng, giúp cho quá trình điều khiển thiết bị. 
 Ngoài ra còn có một số khối mở rộng khác cho điều khiển dữ liệu. 
4.2 Ví dụ về sơ đồ chung điều khiển vào ra trong hệ điều hành 
Qua xem xét sơ đồ ở hình 2.3 chúng ta thấy: 
 Chương trình người dùng và chương trình của phương pháp truy nhập ở 
vùng bộ nhở RAM (địa chỉ của chúng tùy theo trạng thái máy trước khi chúng 
được nạp vào). 
 Các chương trình gọi ngắt vào ra, thân ngắt và kết thúc ngắt được đặt 
trên những địa chỉ xác định. Trong thân ngắt có chứa lệnh bắt đầu vào/ra(SIO: 
start Input/Output). Như đã biết điều khiển vào ra do kênh đảm nhận và kênh 
hoạt động theo hệ thống lệnh riêng (lệnh kênh). 
Buffer ra Vùng làm 
.. 
.. 
READ 
.. 
.. 
.. 
.. 
EXCP 
.. 
.. 
Chương 
trình 
Chương trình 
của hệ điều 
Gọi ngắt 
hướng 
Hoàn thiện 
hướng tới 
supervisor 
.. 
.. 
SIO 
.. 
.. 
38 
 (Trong sơ đồ trên, vùng nằm trong đường rời nét là thuộc các vùng nhớ 
cố định của bộ nhớ trong) 
Hình 2.3. Một ví dụ về điều khiển vào – ra trong hệ điều hành OS 
 Chi tiết quá trình được tóm tắt như sau (xét các máy theo hệ OS): 
 -chuẩn bị một chương trình kênh (dãy các lệnh kênh) 
 -xây dựng từ địa chỉ kênh (CAW: channel address Word) 
 -gửi từ địa chỉ kênh nói trên vào một địa chỉ quy định sẵn 
 -đưa ra lệnh SIO và tải chương trình kênh (theo kênh và thiết bị tương 
ứng) 
 -phân tích kết quả việc tải chương trình kênh 
 -sau khi tải thành công chương trình kênh, CPU và kênh làm việc song 
song 
 -sau khi kết thúc (tốt hay không tốt) công việc vào ra, kênh đưa ra tín 
hiệu cho ngắt vào/ra. Chương trình xử lý ngắt sẽ phân tích tín hiệu trên để biết 
thành công hay không và dấu hiệu sai sót. 
 Chương trình người dùng, dựa vào kiểm tra kết quả vào/ra để xử lý: nếu 
hoàn thiện thì công việc tiếp tục; nếu có sai sót sẽ tùy từng ngữ cảnh để xử lý. 
 Nếu chỉ ra rằng, thao tác vào ra không thể kết thúc ngay được thì 
chương trình sẽ chuyển sang trạng thái chờ đợi. 
5. Tổ chức lưu trữ dữ liệu trên bộ nhớ ngoài 
Mục tiêu: Nắm được cách thức tổ chức lưu trữ dữ liệu, các phương pháp quản 
lý trên bộ nhớ ngoài. 
 5.1. Các khái niệm cơ bản 
 Yêu cầu quản lý bộ nhớ ngoài 
 Khi cần lưu trữ các chương trình hoặc dữ liệu, các hệ thống máy tính 
bắt buộc phải sử dụng bộ nhớ ngoài (đĩa từ, băng từ,...). Nhiệm vụ chính hệ 
điều hình phải đảm bảo các chức năng sau: 
 Quản lý không gian nhớ tự do trên bộ nhớ ngoài (free space manage) 
 Cấp phát không gian nhớ tự do (allocation methods) 
 Cung cấp các khả năng định vị bộ nhớ ngoài 
 Lập lịch cho bộ nhớ ngoài 
 Cấu trúc vật lý đĩa từ 
39 
 Đĩa từ bao gồm một hoặc nhiều lá đĩa đặt đồng trục. Mỗi mặt đĩa chia 
thành các rãnh tròn đồng tâm gọi là track, mỗi track được chia thành các cung 
gọi là sector. Trên mỗi mặt đĩa có đầu đọc ghi dữ liệu. 
 Hệ điều hành xem đĩa như mảng một chiều mà thành phần là các khối 
đĩa (disk block). Mỗi khối đĩa ghi các thông tin về mặt đĩa, track, sector mà hệ 
điều hành có thể định vị trên đó. 
5.2. Các phương pháp quản lý không gian tự do 
Vì không gian trống là giới hạn nên chúng ta cần dùng lại không gian 
từ các tập tin bị xoá cho các tập tin mới nếu có thể. Để giữ vết của không 
gian đĩa trống, hệ thống duy trì một danh sách không gian trống. Danh 
sách không gian trống ghi lại tất cả khối đĩa trống. Để tạo tập tin, chúng ta 
tìm trong danh sách không gian trống lượng không gian được yêu cầu và 
cấp phát không gian đó tới tập tin mới. Sau đó, không gian này được xoá 
từ danh sách không gian trống. Khi một tập tin bị xoá, không gian đĩa của 
nó được thêm vào danh sách không gian trống. Mặc dù tên của nó là danh 
sách nhưng danh sách không gian trống có thể không được cài như một 
danh sách. 
a) Bit vector 
Thường thì danh sách không gian trống được cài đặt như một bản 
đồ bit (bit map) hay một vector bit (bit vector). Mỗi khối được biểu diễn 
bởi 1 bit. Nếu khối là trống, bit của nó được đặt là 1, nếu khối được cấp 
phát bit của nó được đặt là 0. 
Thí dụ, xét một đĩa khi các khối 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 
26, và 27 là trống và các khối còn lại được cấp phát. Bản đồ bit không 
gian trống sẽ là: 
001111001111110001100000011100000 
Lợi điểm chính của tiếp cận này là tính tương đối đơn giản và hiệu 
quả của nó trong việc tìm khối trống đầu tiên, hay n khối trống tiếp theo 
trên đĩa. 
Một lần nữa, chúng ta thấy các đặc điểm phần cứng định hướng 
chức năng phần mềm. Tuy nhiên, các vector bit là không đủ trừ khi toàn 
bộ vector được giữ 
trong bộ nhớ chính. Giữ nó trong bộ nhớ chính là có thể cho các đĩa nhỏ 
hơn, như trên các máy vi tính nhưng không thể cho các máy lớn hơn. Một 
đĩa 1.3 GB với khối 51 bytes sẽ cần một bản đồ bit 332 KB để ghi lại các 
khối trống. Gom bốn khối vào một nhóm có thể giảm số này xuống còn 83 
KB trên đĩa. 
b) Danh sách liên kết 
40 
Hình 2.4 danh sách không gian trống được liên kết trên đĩa 
Một tiếp cận khác để quản lý bộ nhớ trống là liên kết tất cả khối 
trống, giữ một con trỏ tới khối trống đầu tiên trong một vị trí đặc biệt trên 
đĩa và lưu nó trong bộ nhớ. Khối đầu tiên này chứa con trỏ chỉ tới khối đĩa 
trống tiếp theo,..Trong thí dụ trên, chúng ta có thể giữ một con trỏ chỉ tới 
khối 2 như là khối trống đầu tiên. Khối 2 sẽ chứa một con trỏ chỉ tới khối 
3, khối này sẽ chỉ tới khối 4,(như hình X-10). Tuy nhiên, cơ chế này 
không hiệu quả để duyệt danh sách, chúng ta phải đọc mỗi khối, yêu cầu 
thời gian nhập/xuất đáng kể. Tuy nhiên, duyệt danh sách trống không là 
hoạt động thường xuyên. Thường thì, hệ điều hành cần một khối trống để 
mà nó có thể cấp phát khối đó tới một tập tin, vì thế khối đầu tiên trong 
danh sách trống được dùng. Phương pháp FAT kết hợp với đếm khối trống 
thành cấu trúc dữ liệu cấp phát. 
c) Nhóm 
Thay đổi tiếp cận danh sách trống để lưu địa chỉ của n khối trống 
trong khối trống đầu tiên. n-1 khối đầu tiên này thật sự là khối trống. 
Khối cuối cùng chứa địa chỉ của n khối trống khác, Sự quan trọng của 
việc cài đặt này là địa chỉ của một số lượng lớn khối trống có thể được 
tìm thấy nhanh chóng, không giống như trong tiếp cận danh sách liên kết 
chuẩn. 
d) Bộ đếm 
Một tiếp cận khác đạt được lợi điểm trong thực tế là nhiều khối kề 
có thể được cấp phát và giải phóng cùng lúc, đặc biệt khi không gian được 
cấp phát với giải thuật cấp phát kề hay thông qua nhóm. Do đó, thay vì giữ 
một danh sách n địa chỉ đĩa trống, chúng ta có thể giữ địa chỉ của khối 
trống đầu tiên và số n khối kề trống theo sau khối đầu tiên. Mỗi mục từ 
trong danh sách không gian trống sau đó chứa một địa chỉ đĩa và bộ đếm. 
41 
Mặc dù mỗi mục từ yêu cầu nhiều không gian hơn một địa chỉ đĩa đơn, 
nhưng toàn bộ danh sách sẽ ngắn hơn với điều kiện là bộ đếm lớn hơn 1. 
 5.3. Các phương pháp cấp phát không gian tự do 
Tính tự nhiên của truy xuất trực tiếp đĩa cho phép chúng ta khả năng 
linh hoạt trong việc cài đặt tập tin. Trong hầu hết mọi trường hợp, nhiều 
tập tin sẽ được lưu trên cùng đĩa. Vấn đề chính là không gian cấp phát tới 
các tập tin này như thế nào để mà không gian đĩa được sử dụng hiệu quả và 
các tập tin có thể được truy xuất nhanh chóng. Ba phương pháp quan trọng 
cho việc cấp phát không gian đĩa được sử dụng rộng rãi: cấp phát kề, liên 
kết và chỉ mục. Mỗi phương pháp có ưu và nhược điểm. Một số hệ thống 
hỗ trợ cả ba. Thông dụng hơn, một hệ thống sẽ dùng một phương pháp cụ 
thể cho tất cả tập tin. 
a) Cấp phát kề 
Phương pháp cấp phát kề yêu cầu mỗi tập tin chiếm một tập hợp các 
khối kề nhau trên đĩa. Các địa chỉ đĩa định nghĩa một thứ tự tuyến tính trên 
đĩa. Với thứ tự này, giả sử rằng chỉ một công việc đang truy xuất đĩa, truy 
xuất khối b+1 sau khi khối b không yêu cầu di chuyển trước. Khi di 
chuyển đầu đọc được yêu cầu (từ cung từ cuối cùng của cylinder tới cung 
từ đầu tiên của cylinder tiếp theo), nó chỉ di chuyển một rãnh (track). Do 
đó, số lượng tìm kiếm đĩa được yêu cầu cho truy xuất kề tới các tập tin 
được cấp phát là nhỏ nhất. 
Cấp phát kề của một tập tin được định nghĩa bởi địa chỉ đĩa và chiều 
dài (tính bằng đơn vị khối) của khối đầu tiên. Nếu tập tin có n khối và bắt 
đầu tại khối b thì nó chiếm các khối b, b+1, b+2,..,b+n-1. Mục từ thư mục 
cho mỗi tập tin hiển thị địa chỉ của khối bắt đầu và chiều dài của vùng 
được cấp phát cho tập tin này 
42 
Hình 2.5 danh sách không gian trống được cấp phát kề 
b) Cấp phát liên kết 
Cấp phát liên kết giải quyết vấn đề của cấp phát kề. Với cấp phát liên kết, 
mỗi tập tin là một danh sách các khối đĩa được liên kết; các khối đĩa có thể 
được phân tán khắp nơi trên đĩa. Thư mục chứa một con trỏ chỉ tới khối đầu 
tiên và các khối cuối cùng của tập tin. Thí dụ, một tập tin có 5 khối có thể bắt 
đầu tại khối số 9, tiếp tục là khối 16, sau đó khối 1, khối 10 và cuối cùng khối 
25 . Mỗi khối chứa một con trỏ chỉ tới khối kế tiếp. Các con trỏ này không 
được làm sẳn dùng cho người dùng. 
Hình 2.6 danh sách không gian trống được cấp phát liên kết 
Một thay đổi quan trọng trên phương pháp cấp phát liên kết là dùng 
bảng cấp phát tập tin (file allocation table-FAT). Điều này đơn giản nhưng 
là phương pháp cấp phát không gian đĩa hiệu quả được dùng bởi hệ điều 
hành MS-DOS và OS/2. Một phần đĩa tại phần bắt đầu của mỗi phân khu 
43 
được thiết lập để chứa bảng này. Bảng này có một mục từ cho mỗi khối đĩa 
và được lập chỉ mục bởi khối đĩa. FAT được dùng nhiều như là một danh 
sách liên kết. Mục từ thư mục chứa số khối của khối đầu tiên trong tập tin. 
Mục từ bảng được lập chỉ mục bởi số khối đó sau đó chứa số khối của khối 
tiếp theo trong tập tin. Chuỗi này tiếp tục cho đến khi khối cuối cùng, có 
giá trị cuối tập tin đặc biệt như mục từ bảng. Các khối không được dùng 
được hiển thị bởi giá trị bảng 0. Cấp phát một khối mới tới một tập tin là 
một vấn đề đơn giản cho việc tìm mục từ bảng có giá trị 0 đầu tiên và thay 
thế giá trị kết thúc tập tin trước đó với địa chỉ của khối mới. Sau đó, số 0 
được thay thế với giá trị kết thúc tập tin. Một thí dụ minh hoạ là cấu trúc 
FAT của hình X-7 cho một tập tin chứa các khối đĩa 217, 618 và 339. 
 Hình 2.7 Bảng cấp phát tập tin 
Cơ chế cấp phát FAT có thể dẫn tới số lượng lớn tìm kiếm đầu đọc 
đĩa nếu FAT không được lưu trữ(cache). Đầu đọc đĩa phải di chuyển tới 
điểm bắt đầu của phân khu để đọc FAT và tìm vị trí khối sau đó di 
chuyển tới vị trí của chính khối đĩa đó. Trong trường hợp xấu nhất, cả hai 
di chuyển xảy ra cho mỗi khối đĩa. Lợi điểm là thời gian truy xuất ngẫu 
nhiên được cải tiến vì đầu đọc đĩa có thể tìm vị trí của bất cứ khối nào 
bằng cách đọc thông tin trong FAT. 
c) Cấp phát được lập chỉ mục 
Cấp phát liên kết giải quyết việc phân mãnh ngoài và vấn đề khai 
báo kích thước của cấp phát kề. Tuy nhiên, cấp phát liên kết không hỗ trợ 
truy xuất trực tiếp hiệu quả vì các con trỏ chỉ tới các khối được phân tán 
với chính các khối đó qua đĩa và cần được lấy lại trong thứ tự. Cấp phát 
được lập chỉ mục giải quyết vấn đề này bằng cách mang tất cả con trỏ vào 
44 
một vị trí: khối chỉ mục (index block). 
Mỗi tập tin có khối chỉ mục của chính nó, khối này là một mảng các 
địa chỉ khối đĩa. Mục từ thứ i trong khối chỉ mục chỉ tới khối i của tập tin. 
Thư mục chứa địa chỉ của khối chỉ mục (như hình 2.8). Để đọc khối i, 
chúng ta dùng con trỏ trong mục từ khối chỉ mục để tìm và đọc khối mong 
muốn. Cơ chế này tương tự như cơ chế phân trang. 
Hình 2 . 8 Cấp phát không gian đĩa được lập chỉ mục 
5.4. Lập lịch cho đĩa 
 Khái niệm về lập lịch cho đĩa 
 Lập lịch cho đĩa là xây dựng các thuật toán dịch chuyển đầu từ đọc ghi 
sao cho thời gian truy nhập đĩa là tối ưu nhất. 
 Một số phương pháp lập lịch 
 -FCFS 
 -SSTF 
 -Scan 
 -C-Scan 
 -Look 
 -C-Look 
 5.5. Hệ file 
 Dữ liệu được xử lý trong máy tính được bảo quản lâu dài trên băng từ, 
đĩa từ, đĩa quang v.v và dữ liệu được tập hợp lại một cách có tổ chức 
thành các file dữ liệu theo mục đích sử dụng. File có thể là chương trình 
của người dùng, một chương trình của hệ điều hành, một văn bản, một tập 
45 
hợp dữ liệu. Trong một số hệ điều hành, một số thiết bị ngoại vi cũng 
được quan niệm như file dữ liệu. 
 Theo góc độ quan sát của người dùng, dữ liệu trong một file lại được 
tổ chức thành các bản ghi lôgic (gọi tắt bản ghi), mà mỗi bản ghi lôgic có 
thể là một byte hoặc một cấu trúc dữ liệu nào đó. Bản ghi chính là đơn vị 
dữ liệu mà chương trình người dùng quan tâm đến và xử lý theo mỗi nhịp 
làm việc: file là tập hợp (được người dùng quan niệm là một dãy) các bản 
ghi có tổ chức. Thông thường, trong file tồn tại một thứ tự giữa các bản 
ghi, thứ tự đó thể hiện vị trí logic giữa các bản ghi với nhau (chẳng hạn 
như thứ tự đưa bản ghi vào file). 
CÂU HỎI VÀ BÀI TẬP 
1. Nêu các phương pháp tổ chức và truy nhập dữ liệu. 
2. Nêu chức năng của hệ thống điều khiển dữ liệu. 
3. Khái niệm về kết khối và tách khối. 
4. Nêu vai trò buffer. 
5. Trình bày các khối điều khiển dữ liệu 
6. Trình bày các phương pháp của quản lý và cấp phát không gian nhớ 
trên bộ nhớ ngoài của hệ điều hành. 
7. Khái niệm file. 
 HƯỚNG DẪN TRẢ LỜI 
1. Các phương pháp tổ chức : tổ chứ kế tiếp, tổ chức chỉ số kế tiếp, tổ 
chức truy nhập trực tiếp, tổ thư viện, tổ chức theo bộ nhớ ảo. 
Các phương pháp truy nhập dữ liệu: cách thức truy nhập tuần tự, cách 
thức truy nhập cơ sở. 
2. Chức năng của hệ thống điều khiển dữ liệu: Bảo quản dữ liệu trên thiết 
bị ngoài, đảm bảo cách thức tổ chức khác nhau đối với dữ liệu, thực 
hiện các phương pháp truy nhập khác nhau tới dữ liệu, catalog dữ liệu 
và thực hiện việc tìm kiếm tự động hóa dữ liệu theo tên kí hiệu mà 
không cần theo địa chỉ. 
3. Kết khối diễn ra sau khi chương trình người dùng chuẩn bị xong nội 
dung bản ghi và đưa bản ghi đó vào khối để đưa ra thiết bị nhớ ngoài. 
46 
Tách khối là quá trình từ các khối đưa ra được các bản ghi cần tìm có 
liên quan đến khối đó. Quá trình này diễn ra sau khi hệ điều hành đã 
đọc một khối từ vật dẫn ngoài vào bộ nhớ trong và trước khi chương 
trình người dùng xử lý bản ghi. 
4. Buffer là vùng nhớ đệm trung gian lưu trữ tạm thời, thuận tiện cho việc 
vào –ra. 
5. Có các khối điều khiển: Khối FCB (File Control Block), Khối DCB 
(Data Control Block), Khối UCB (Unit Control Block). 
6. Các phương pháp quản lý không gian nhớ : quản lý bằng bit vectơ 
(bitmap), quản lý bằng danh sách móc nối. 
Các phương pháp cấp phát không gian nhớ: cấp phát kề (liên tục), cấp 
phát liên kết, cấp phát chỉ số. 
7. Xem phần khái niệm file.