1
MỤC LỤC
Chương 1: TỔNG QUAN.................................................................................. 4
1.1 Giới thiệu ...................................................................................................... 4
1.1.1 Hệ điều hành là gì? ................................................................................ 4
1.1.2 Các hệ xử lý theo lô đơn giản ................................................................ 7
1.1.3 Các hệ xử lý theo lô, đa chương ............................................................ 8
1.1.4 Các hệ phân chia thời gian ..................................................................... 9
1.1.5 Các hệ máy tính cá nhân ...................................................................... 11
1.1.6 Các hệ song song, các hệ phân tán, các hệ thời gian thực ................... 11
1.2 Cấu trúc hệ điều hành ............................................................................... 15
1.2.1 Các thành phần hệ thống ..................................................................... 16
1.2.2 Các dịch vụ của hệ điều hành .............................................................. 22
1.2.3 Lời gọi hệ thống .................................................................................. 24
1.2.4 Các chương trình hệ thống .................................................................. 25
1.2.5 Cấu trúc hệ thống ................................................................................. 26
1.2.6 Cài đặt và thiết kế hệ thống ................................................................. 33
Câu hỏi và bài tập chương 1 ........................................................................... 35
Chương 2: QUẢN LÝ TIẾN TRÌNH ............................................................. 36
2.1 Tiến tình ...................................................................................................... 36
2.1.1 Khái niệm tiến trình ............................................................................ 36
2.1.2 Lập lịch tiến trình................................................................................. 39
2.1.3 Các thao tác trên tiến trình ................................................................... 45
2.1.4 Hợp tác giữa các tiến trình ................................................................... 49
2.1.5 Luồng ................................................................................................... 52
2.1.6 Truyền thông giữa các tiến trình .......................................................... 70
2.2 Lập lịch CPU .............................................................................................. 74
2.2.1 Các khái niệm cơ bản........................................................................... 74
2.2.2 Các tiêu chí lập lịch ............................................................................. 78
2.2.3 Các thuật toán lập lịch ......................................................................... 79
2.2.4 Đánh giá thuật toán .............................................................................. 95
2.3 Đồng bộ hóa tiến trình ............................................................................... 96
2.3.1 Cơ sở .................................................................................................... 96
2.3.2 Bài toán Critical - Sestion .................................................................... 99
2.3.4 Các bài toán cổ điển trong việc đồng bộ hoá..................................... 114
2.4 Bế tắc ......................................................................................................... 126
2.4.1 Mô hình .............................................................................................. 126
2.4.2 Đặc trưng hóa bế tắc .......................................................................... 128
2.4.3 Các phương pháp thao tác với bế tắc ................................................. 132
2.4.4 Phòng tránh bế tắc ............................................................................. 136
2.4.5 Phát hiện bế tắc .................................................................................. 144
2.4.6 Khôi phục từ bế tắc ............................................................................ 148
2
Câu hỏi và bài tập chương 2 ......................................................................... 150
Chương 3: QUẢN LÝ LƯU TRỮ ................................................................ 155
3.1 Quản lý bộ nhớ ......................................................................................... 155
3.1.1 Cơ sở .................................................................................................. 155
3.1.2 Bộ nhớ vật lý và bộ nhớ logic............................................................ 160
3.1.3 Hoán vị (Swap) .................................................................................. 161
3.1.4 Cấp phát liên tục ................................................................................ 163
3.1.5 Phân trang .......................................................................................... 172
3.1.6 Phân đoạn ........................................................................................... 188
3.2 Bộ nhớ ảo .................................................................................................. 198
3.2.1 Cơ sở .................................................................................................. 198
3.2.2 Phân trang theo yêu cầu ..................................................................... 201
3.2.3 Hiệu năng của phân trang theo yêu cầu ............................................. 205
3.2.4 Thay thế trang .................................................................................... 205
3.2.5 Các thuật toán thay thế trang ............................................................. 207
3.2.6 Cấp phát frame ................................................................................... 215
3.2.7 Thrashing ........................................................................................... 218
3.2.8 Các vấn đề khác ................................................................................. 220
3.2.9 Phân đoạn theo yêu cầu ..................................................................... 221
3.3 Giao diện hệ thống tệp ............................................................................. 225
3.3.1 Khái niệm tệp ..................................................................................... 225
3.3.2 Các phương pháp truy cập ................................................................. 229
3.3.3 Cấu trúc thư mục ............................................................................... 231
3.3.4 Bảo vệ ................................................................................................ 243
3.3.5 Tính nhất quán về ngữ nghĩa ............................................................. 246
3.4 Cài đặt hệ thống tệp ................................................................................. 246
3.4.1 Cấu trúc hệ thống tệp ......................................................................... 247
3.4.2 Các phương pháp cấp phát................................................................. 249
3.4.3 Quản lý không gian rỗi ...................................................................... 260
3.4.4 Cài đặt thư mục .................................................................................. 262
3.4.5 Hiệu quả và hiệu năng ....................................................................... 264
3.4.6 Khôi phục ........................................................................................... 265
Câu hỏi và bài tập chương 3 ......................................................................... 265
Chương 4: HỆ VÀO RA ................................................................................ 271
4.1 Hệ vào ra ................................................................................................... 271
4.1.1 Tổng quan .......................................................................................... 271
4.1.2 Vào ra phần cứng ............................................................................... 272
4.1.3 Giao diện lập trình vào ra .................................................................. 275
4.1.4 Hệ vào ra của nhân ............................................................................ 277
4.1.5 Chuyển đổi yêu cầu vào ra thành các thao tác phần cứng ................. 281
4.1.6 Hiệu năng ........................................................................................... 283
4.2 Cấu trúc lưu trữ phụ ............................................................................... 285
4.2.1 Cấu trúc đĩa ........................................................................................ 285
3
4.2.2 Lập lịch đĩa ........................................................................................ 286
4.2.3 Quản lý đĩa ......................................................................................... 290
4.2.4 Quản lý không gian swap .................................................................. 292
4.2.5 Độ tin cậy của đĩa .............................................................................. 292
4.2.6 Cài đặt hệ lưu trữ ổn định .................................................................. 294
4.2.7 Các thiết bị lưu trữ thứ ba: Các công việc của hệ điều hành và vấn đề
về hiệu năng ..................................................................................................... 294
Câu hỏi và bài tập chương 4 ......................................................................... 297
TÀI LIỆU THAM KHẢO ............................................................................. 300
4
Chương 1: TỔNG QUAN
1.1 Giới thiệu
Hệ điều hành là một chương trình phần mềm quản lý phần cứng máy tính. Nó
cung cấp nền tảng cho các chương trình ứng dụng và đóng vai trò trung gian giao tiếp
giữa người dùng máy tính và phần cứng của máy tính đó. Hệ điều hành thực hiện các
nhiệm vụ rất đa dạng, một vài hệ điều hành được thiết kế để thực hiện một nhiệm vụ
chuyên biệt nào đó trong khi một số hệ điều hành khác được thiết kế đa năng.
1.1.1 Hệ điều hành là gì?
Một hệ điều hành là một thành phần quan trọng của mọi hệ thống máy tính.
Một hệ thống máy tính có thể được chia thành bốn thành phần: phần cứng, hệ điều
hành, các chương trình ứng dụng và người sử dụng.
- Phần cứng (hardware): bao gồm bộ xử lý trung tâm (CPU), bộ nhớ
(memory), thiết bị xuất/nhập (I/O),… cung cấp tài nguyên cơ bản cho hệ thống.
- Các chương trình ứng dụng (application programs): trình biên dịch
(compiler), trình soạn thảo văn bản (text editor), hệ cơ sở dữ liệu (database system),
trình duyệt Web,... hỗ trợ người dùng sử dụng tài nguyên, giải quyết yêu cầu của
người dùng.
- Người dùng (user): là người sử dụng hệ thống, những người dùng khác nhau
thực hiện những yêu cầu khác nhau bằng các ứng dụng khác nhau.
- Hệ điều hành (operating system): hay còn gọi là chương trình hệ thống, điều
khiển và phối hợp việc sử dụng phần cứng giữa những chương trình ứng dụng khác
nhau cho những người dùng khác nhau. Hệ điều hành có thể được khai thác từ hai
phía: người dùng và hệ thống.
Hình 1.1 Các thành phần của một hệ thống máy tính
User 1
User 2
User N
…
System and application programs
Compliler
Text editor
Database
Hardwave
…
5
+ Tầm nhìn người sử dụng
Tầm nhìn người sử dụng máy tính rất đa dạng bởi giao diện được dùng. Hầu
hết những người dùng máy tính ngồi trước máy tính cá nhân gồm có màn hình, bàn
phím, chuột và bộ xử lý hệ thống (system unit). Một hệ thống như thế được thiết kế
cho một người dùng độc quyền sử dụng tài nguyên của nó để tối ưu hoá công việc mà
người dùng đang thực hiện. Trong trường hợp này, hệ điều hành được thiết kế dễ
dàng cho việc sử dụng với sự quan tâm về năng lực thực hiện ít quan tới việc sử dụng
tài nguyên.
Có người sử dụng ngồi tại thiết bị đầu cuối (terminal) được nối kết tới máy
tính lớn (mainframe) hay máy tính tầm trung (minicomputer). Những người khác
đang truy xuất cùng máy tính thông qua các thiết bị đầu cuối khác. Những người dùng
này chia sẻ các tài nguyên và có thể trao đổi thông tin. Hệ điều hành được thiết kế để
tối ưu hoá việc sử dụng tài nguyên để đảm bảo rằng tất cả thời gian phục vụ của CPU,
bộ nhớ và thiết bị xuất nhập được sử dụng hữu hiệu, công bằng.
Gần đây, các máy tính xách tay được sử dụng rộng rãi. Các thiết bị này được
sử dụng chỉ bởi cá nhân người dùng. Một vài máy tính này được nối mạng hoặc nối
trực tiếp bằng cáp mạng hay thông qua các modem không dây. Do sự giới hạn về
năng lượng, hệ điều hành được thiết kế để tiết kiệm tối đa năng lượng của máy tính.
Một số máy tính có rất ít hay không có giao diện với người dùng. Thí dụ, các
máy tính được nhúng vào các thiết bị gia đình và xe ôtô có thể có một bảng số và các
đèn hiển thị trạng thái mở, tắt nhưng hầu hết chúng và các hệ điều hành được thiết kế
để điều khiển thiết bị không cần giao tiếp với ngưới sử dụng.
+ Tầm nhìn hệ thống
Chúng ta có thể thấy một hệ điều hành như bộ cấp phát tài nguyên. Hệ thống
máy tính có nhiều tài nguyên - phần cứng và phần mềm - có thể được yêu cầu để cấp
phát các tài nguyên: thời gian CPU, không gian bộ nhớ, không gian lưu trữ tập tin,
các thiết bị xuất/nhập,... Hệ điều hành hoạt động như bộ quản lý tài nguyên, thực hiện
một lượng lớn các yêu cầu cấp phát có thể xung đột về tài nguyên, hệ điều hành phải
quyết định cách cấp phát tài nguyên tới những chương trình cụ thể và người dùng để
có thể điều hành hệ thống máy tính hữu hiệu và công bằng.