Bài giảng Hệ điều hành - Đỗ Tuấn Anh

hành động để đảm 
bảo điều độ.
58
172
SƠ ĐỒ NGUYÊN LÝ• BEGIN
• Ban đầu k = 0; khoá mở
• PARBEGIN
• tt1: while k = 1 do; <-chờ đợi tích cực
• k := 1;
• 
• k := 0;
• 
• tt2 : while k = 1 do; <-chờ đợi tích cực
• k := 1;
• 
• k := 0;
• 
• PAREND
• END
173
KIỂM TRA VÀ XÁC LẬP
(TEST and SET)
• Cơ sở: dùng lệnh máy TS có từ các máy 
tính thế hệ III trở đi.
174
TEST and SET
• IBM 360/370: $ 1 lệnh TS ( mã 92H),
• IBM PC: Nhóm lệnh BTS (Binary Test and Set):
L:= G ¬G G ¬G
G:= 1 0 1 0
59
175
TEST and SET
• Sơ đồ điều độ:
176
TEST and SET
Đặc điểm:
• Đơn giản, độ phức tạp không tăng khi số 
tiến trình tăng. Nguyên nhân: Cục bộ hoá 
biến và tính liên tục của KT & XL,
• Tồn tại hiện tượng chờ đợi tích cực. Nguyên 
nhân: Mỗi TT phải tự đưa mình vào đoạn 
găng.
177
KỸ THUẬT ĐÈN 
BÁO(Semaphore)
• Dijsktra đề xuất 1972.
• Đề xuất:
– Mỗi tài nguyên găng được đặt tương ứng với 
một biến nguyên đặc biệt S (Semaphore),
– Ban đầu: S ← Khả năng phục vụ t.ng. găng,
– $ 2 lệnh máy P(S) và V(S) thay đổi giá tri của 
S, mỗi lệnh làm 2 công việc và làm một cách 
liên tục.
60
178
KỸ THUẬT ĐÈN BÁO
• Nội dung lệnh P(S):
* Dec(s);
** If S < 0 then Đưa TT đi xếp hàng.
• Nội dung lệnh V(S):
* Inc(s);
** If S £ 0 then Kích hoạt TT đang xếp hàng.
179
KỸ THUẬT ĐÈN BÁO
• Thực hiện:
– Vì nhiều lý do, không thể chế tạo MT với 2 lệnh 
trên,
– Lệnh P(S), V(S) ž thủ tục tương ứng.
• Đảm bảo tính liên tục:
180
KỸ THUẬT ĐÈN BÁO
• Sơ đồ điều độ:
61
181
Semaphore nhị phân:
• Phần lớn các tài nguyên găng có khả năng 
phục vụ = 1 ž S nhị phân.
• P(S):
If s = 0 then Xếp_hàng Else s := 0;
• V(S):
If dòng_xếp_hàng ¹ NULL then Kích_hoạt
Else s := 1;
Vấn đề đặt tên các thủ tục P và V.
KỸ THUẬT ĐÈN BÁO
182
6 – CÔNG CỤ ĐIỀU ĐỘ CẤP 
CAO
• Đoạn găng quy ước,
• Biến điều kiện quy ước,
• Monitor hỗ trợ điều độ: cung cấp giá trị 
cho biến điều kiện quy ước.
• Monitor đóng vai trò vỏ bọc bảo vệ ngăn 
cách giữa tài nguyên găng và công cụ truy 
nhập tới nó.
183
7 - BẾ TẮC và CHỐNG BẾ TẮC
• Khái niệm bế tắc (Deadlock):
• Cùng chờ đợi,
• Vô hạn nếu không có tác động từ bên 
ngoài.
• Sẽ không có bế tắc nếu TT A bắt đầu đủ 
sớm hay đủ muộn.
62
184
BẾ TẮC và CHỐNG BẾ TẮC
• Điều kiện xuất hiện bế tắc: hội đủ đồng thời
4 điều kiện:
– $ tài nguyên găng,
– Có tổ chức xếp hàng chờ đợi,
– Không phân phối lại tài nguyên,
– $ hiện tượng chờ đợi vòng tròn.
• Chống bế tắc: 3 lớp giải thuật:
– Phòng ngừa,
– Dự báo và tránh,
– Nhận biết và khắc phục.
185
Phòng ngừa
• Điều kiện áp dụng:
– Xác xuất xuất hiện bế tắc lớn,
– Các biện phápTổn thất lớn.
• Biện pháp: tác động lên một hoặc một số 
điều kiện gây bế tắc để 4 điều kiện không 
xuất hiện đồng thời.
• Các giải pháp: được áp dụng để nâng cao 
hiệu quả của hệ thống.
186
Phòng ngừa
• Chống tài nguyên găng:
– Tổ chức hệ thống tài nguyên lô gíc,
– 2 mức truy nhập,
– SPOOL.
• Chống xếp hàng chờ đợi:
– Chế độ phân phối sơ bộ,
– Trước khi ngắt TT: lưu trạng thái (Dump),
– Công cụ: 
• Điểm gác (Control Points),
• Điểm ngắt (Break Points)
63
187
Phòng ngừa
• Đặt điểm gác:
– Cố định trong CT,
– Theo tác nhân ngoài
(vd: thời gian)
• Ứng dụng:
– Hiệu chỉnh CT,
– Thực hiện các CT dài,
– Với toàn bộ hệ thống: Hibernating.
188
Phòng ngừa
• Phân phối lại tài nguyên:
– Các tài nguyên quan trọng (Bộ nhớ, Processor . 
. .) luôn luôn được phân phối lại,
– Chủ yếu: chỉ cần lưu ý các tài nguyên riêng,
– Hệ thống tài nguyên lô gíc: giảm nhu cầu phân 
phối lại.
– Để phân phối lại: Lưu và khôi phục trạng thái 
tài nguyên.
189
Phòng ngừa
• Chống chờ đợi vòng tròn:
– Phân lớp tài nguyên, tạo thành hệ thống phân 
cấp,
– Nguyên tắc phân phối: Khi chuyển lớp - phải 
giải phóng tài nguyên lớp cũ.
64
190
DỰ BÁO VÀ TRÁNH
• Mỗi lần phân phối một tài nguyên: kiểm tra 
xem việc phân phối này có thể dẫn đến 
nguy cơ bế tắc cho một số tiến trình nào đó 
hay không và là những tiến trình nào?
• Điều kiện môi trường:
– Xác xuất xẩy ra bế tắc nhỏ,
– Tổn thất (nếu có bế tắc) – lớn. 
191
DỰ BÁO VÀ TRÁNH
• Giải thuật tiêu biểu: “Người chủ ngân 
hàng”.
• Giả thiết:
– Xét 1 loại tài nguyên, số lượng ž tstb,
– n tiến trình,
– Maxi, 
– Ffoii,
– Kti – boolean,
• True – chắc chắn kết thúc được,
• False – trong trường hợp ngược lại. 
192
DỰ BÁO VÀ TRÁNH
65
193
DỰ BÁO VÀ TRÁNH
• Tiêu chuẩn dự báo: ngặt,
• Dựa vào Kti ž biết các TT có nguy cơ bế tắc,
• Xử lý trước khi TT bị bế tắc.
• Đặc điểm giải thuật: 
– Đơn giản,
– Input: Maxi – tin cậy,
– Mỗi loại tài nguyên Û thủ tục,
– Mỗi lần phân phối ž kiểm tra.
194
NHẬN BIẾT VÀ KHẮC PHỤC
• Định kỳ kiểm tra các TT chờ đợi để phát 
hiện bế tắc,
• Điều kiện áp dụng:
– Xác xuất xẩy ra bế tắc bé,
– Tổn thất (nếu có bế tắc) – bé.
• Áp dụng với phần lớn OS trong thực tế,
• Do OP đảm nhiệm.
195
NHẬN BIẾT VÀ KHẮC PHỤC
• Lệnh OP ž các nhóm lệnh phục vụ nhận 
biết và khắc phục,
• Nhóm lệnh xem trạng thái (Display 
Status),
• Nhóm lệnh tác động lên dòng xếp hàng 
TT,
• Nhóm lệnh tác động lên TT,
• Quan trọng: các lệnh huỷ tiến trình,
• Các biện pháp hỗ trợ và ngăn chặn tự 
động.
66
196
8 - GỌI TIẾN TRÌNH
• TT có thể cạnh tranh hoặc tương tác với nhau,
• Mối quan hệ tương tác: tuần tự hoặc song song,
• Xác lập quan hệ:
– Lời gọi,
– Cơ chế xử lý sự kiện (Sẽ xét ở chương sau),
• Các cách gọi:
– Trong phạm vi một hệ thống,
– Giữa các hệ thống:
• RI (Remote Invocation),
• RPC (Remote Procedure Call),
– Lý thuyết chung: RMI (Remote Methods Invocation)
197
GỌI TIẾN TRÌNH
• Sơ đồ gọi: 
– Không đối xứng,
– Đối xứng.
• Kỹ thuật truyền tham số:
– Theo giá trị,
– Theo địa chỉ,
– CR (Call by Copy/Restore).
198
GỌI TIẾN TRÌNH
• Thông tin tối thiểu để lưu và khôi phục TT:
– Nội dung các thanh ghi,
– Địa chỉ lệnh,
– Vùng bộ nhớ RAM liên quan,
– Vùng bộ nhớ phục vụ của hệ thống,
– Các sự kiện chưa xử lý.
• Phân biệt sơ đồ gọi đối xứng và đệ quy.
67
199
V – QUẢN LÝ PROCESSOR
• Mục đích: Giảm thời gian chết của 
Processor ž nâng cao hiệu quả hệ thống,
• Vai trò thiết bị trung tâm: liên kết các bộ 
phận đọc lập (cứng và mềm) thành hệ 
thống hoạt động đồng bộ.
• Trong phần này: xét hoạt động của 1 
CPU.
200
1 – PROCESSOR LÔ GÍC
201
2 – CÁC TRẠNG THÁI CƠ BẢN CỦA 
TIẾN TRÌNH 
• Đặc trưng các loại trạng thái,
• Vấn đề cần giải quyết: 3 loại.
68
202
VẤN ĐỀ
203
VẤN ĐỀ
a) Liên quan tới dòng TT sẵn sàng: Cách tổ
chức phục vụ dòng xếp hàng? 
204
VẤN ĐỀ
• Trình tự phục vụ tác động lên thời gian 
chờ đợi trung bình tw : giả thiết – 3 TT :
69
205
VẤN ĐỀ
• Thời gian thực hiện 
tiến trình:
– Không đẩy ra (Non-
preemptive),
(Xử lý theo lô)
– Có đẩy ra 
(Preemptive)
(Phân chia thời gian)
Lượng tử thời gian: 
0.03” ¸ 0.2”.
206
VẤN ĐỀ
• c) Thời điểm đưa TT chờ đợi trở lại sẵn 
sàng? Cơ chế sự kiện và ngắt.
207
3 - ĐIỀU ĐỘ THỰC HIỆN TT
• TT Û thứ tự ưu tiên phục vụ,
• Yêu cầu:
– tw ž min.
– TT kết thúc.
• Chế độ:
– Một dòng xếp hàng,
– Nhiều dòng xếp hàng.
70
208
Chế độ một dòng xếp hàng
• a) FCFS (First come – First served):
– Đơn giản,
– " TT kết thúc được,
– Không cần input bổ sung,
– Tw – lớn,
– Non-Preemtipve. 
209
Chế độ một dòng xếp hàng
• b) SJN (Shortest Job – Next):
– Thời gian thực hiện ít ž ưu tiên cao,
– Tw giảm,
– TT dài có nguy cơ không kết thúc được,
– Khó dự báo thời điểm phục vụ TT,
– Non-Preemtipve,
– Input: Thời gian thực hiện TT.
210
Chế độ một dòng xếp hàng
• c) SRT (Shortest Remaining Time):
– Thứ tự ưu tiên phục vụ: xác định theo lượng thời gian 
còn lại cần thiết để kết thúc TT,
– tw giảm mạnh,
– Các đặc trưng khác: tương tự như SJN,
– TT dài càng có nguy cơ không kết thúc được!
• Ở các chế độ Non-Preemtipve: cần có tlim ž huỹ 
TT hoặc đưa về thứ tự ưu tiên thấp nhất.
71
211
Chế độ một dòng xếp hàng
• d) RR (Round 
Robin):
– Preemtipve,
– " TT - kết thúc 
đươc,
– Khả năng đối 
thoại với TT,
– Ưu tiên thích 
đáng với TT dài: 
phân lớp phục vụ 
với t lớn hơn.
212
Chế độ nhiều dòng xếp hàng
213
4 - NGẮT và XỬ LÝ NGẮT
• Định nghĩa ngắt 
(Interrupt):
– Cơ chế Sự kiện và 
Ngắt: từ MT thế hệ III,
– IBM 360/370 – 7 loại 
sự kiện,
– IBM PC – 256 loại sự 
kiện.
72
214
PHÂN LOẠI NGẮT
• Ngắt trong và ngắt ngoài,
– Ngắt trong: /0, tràn ô, . . . 
– Ngắt ngoài: I/O Int, Timer, . . .
• Ngắt chắn được và không chắn được:
– Chắn được: i/o Int,
– Không chắn được: Timer Int.
• Ngắt cứng và ngắt mềm.
215
XỬ LÝ NGẮT
TT bị ngắt
TT xử
 lý ngắt
216
CT con và CT xử lý ngắt
73
217
5 - Xử lý ngắt trong IBM PC
• Ngắt Û Pointer (4 bytes),
• Véc tơ ngắt = {Pointers} (1 KB),
• Khối bộ nhớ xử lý ngắt,
• Nét đặc biệt:
– $ các ngắt | Pointer ž Bảng tham số (Int 11, 1E, 41, . . .),
– Ngắt KT CT – Int 20, Ngắt thường trú CT Int 27,
– Ngắt R/W đĩa theo địa chỉ tuyệt đối – Int 25, 26,
– $ ngắt tương ứng với việc bấm phím (Int 05, 1B),
– Ngăt OS mô phỏng xử lý các sự kiện (Int 21),
– Một số sự kiện: dành cho user tạo ngắt mềm ž Lập trình 
hướng sự kiện (EOP).
218
VI - CẤU HÌNH và QUẢN LÝ HỆ 
THỐNG
• 1 - Hệ thống nhiều Processors.
• Các loại cấu hình:
– Cấu hình phân cấp,
– Liên kết linh hoạt,
– Đẳng cấu,
• Quản lý tiến trình:
– S – tài nguyên găng,
– TS ž S ž điều độ,
• Đảm bảo toàn vẹn chức năng và toàn vẹn cấu hình.
219
CẤU HÌNH và QUẢN LÝ HỆ THỐNG
• 2 - Bảo vệ hệ thống:
• Nguy cơ:
– Mất hoặc hỏng dữ liệu,
– Sử dụng tài nguyên với mục đích xấu,
– Truy nhập không đăng ký,
– Dò rỉ thông tin.
• Cơ chế bảo vệ:
– Nguyên lý ngăn chặn,
– Nguyên lý cho phép.
• Giải thuật và biện pháp bảo vệ: linh hoạt, thường 
xuyên thay đổi.
74
220
CẤU HÌNH và QUẢN LÝ HỆ THỐNG
• 3 – Thiết kế và xây dựng hệ thống:
• Nguyên lý tập trung: WINDOWS, UNIX, 
OS IBM, . . .
• Nguyên lý “Thử và sai”: LINUX:
– Không có đề xuất hướng chung,
– Mã nguồn mở cho phép mọi người nghiên 
cứu, bổ sung sửa đổi,
– Phát triển theo nguyên lý tự điều chỉnh,
– Giao diện: User tự trang bị.
221
4 - Hệ thống của Microsoft
• .