Đề cương Ôn tập Hệ Điều Hành - Thi Trắc Nghiệm 2023

ĐỀ CƯƠNG ÔN TẬP HỆ ĐIỀU HÀNH (TRẮC NGHIỆM)
Chương 1, 2. Tổng quan về Hệ điều hành, Cấu trúc Hệ điều hành 1. Hệ điều hành là gì?
• Là thành phần trung gian giữa người dùng và hệ thống phần cứng máy tính
2. Hệ điều hành có các chức năng gì? Quản lý thiết bị, quản lý tiến trình và tài nguyên, quản lý
bộ nhớ và quản lý file.
- Phân chia thời gian xử lý và định thời CPU.
- Phối hợp và đồng bộ hoạt động giữa các processes (coordination & synchronization).
- Quản lý tài nguyên hệ thống (thiết bị I/O, bộ nhớ, file chứa dữ liệu,…).
- Thực hiện và kiểm soát access control, protection.
- Duy trì sự nhất quán (integrity) của hệ thống, kiểm soát lỗi và phục hồi hệ thống
khi có lỗi (error recovery).
- Cung cấp giao diện làm việc cho users
3. Tài nguyên hệ thống gồm những gì?
Tài nguyên không gian
Tài nguyên thời gian
4..Hệ điều hành đơn, đa nhiệm? HĐH thời gian thực? Hệ điều hành tập trung?
-Hệ điều hành đơn nhiệm
Tại một thời điểm xác định, khi một chương trình được đưa vào bộ nhớ thì
nó chiếm giữ mọi tài nguyên của hệ thống, và vì vậy chương trình khác không
thể được đưa vào bộ nhớ trong khi nó chưa kết thúc.
Nhưng do các thiết bị vào ra thường làm việc với tốc độ chậm, người ta
dùng kỹ thuật SPOOLING(simultanous peripheral Operation on line): cho phép
tạo ra hiệu ứng song song các thiết bị chỉ cho phép vào ra tuần tự(sẽ để cập chi tiết ở chương sau).
-Hệ điều hành đa nhiệm
Hệ điều hành cho phép tại một thời điểm có nhiều chương trình ở trong bộ
nhớ trong. Chúng có nhu cầu được phân phối thời gian phục vụ CPU, bộ nhớ và
thiết bị ngoại vi. Như vậy CPU, bộ nhó, thiết bị ngoại vi v.v. là các tài nguyên
được chia sẻ cho các chương trình đó. Vấn đề là làm sao đảm bảo tốt nhất tính
bình đẳng khi giải quyết vấn đề phân phối tài nguyên.
-Hệ điều hành thời gian thực (Real time)
Một tiến trình khi đã xâm nhập vào hệ thống thì ở bất kỳ lúc nào đều được phân phối CPU.
-Hệ điều hành tập trung
Trên một hệ thống máy tính chỉ có một HĐH duy nhất cài ở máy chủ. Các
máy trạm được khởi động nhờ máy chủ và nó chỉ làm chức năng nhập/xuất dữ
liệu. Mọi xử lý đều tập trung ở máy chủ.
Hệ điều hành phân chia thời gian (Share time)
Một CPU luôn phiên phục vụ các tiến trình và 1 tiến trình có thể rơi vào
trạng thái chờ đợi khi chưa được phân phối CPU.
- Hệ điều hành phân tán
Trên mỏi máy có 1 hệ điều hành khác nhau, máy chủ chịu trách nhiệm
cung ứng các dịch vụ để truy nhập đến các tài nguyên chung và điều hành toàn
hệ thống, các phép xử lý có thể tiến hành ở máy trạm. 5.
Các tính chất (yếu tố) của HĐH: hiệu suất, bảo vệ và an ninh, tính chính xác, khả
năng bảo trì, thương mại, chuẩn và hệ thống mở 6.
Cấu trúc phân lớp của HĐH: ý nghĩa, lời gọi hệ thống là gì, hoạt động thế nào?
-Mỗi lời gọi hệ thống tương ứng với một thủ tục trong thư viện của hệ điều hành, do đó chương
trình của người sử dụng có thể gọi thủ tục để thực hiện một lời gọi hệ thống. Lời gọi hệ thống
còn được thiết dưới dạng các câu lệnh trong các ngôn ngữ lập trình cấp thấp. Lệnh gọi ngắt
trong hợp ngữ (Int), và thủ tục gọi hàm API trong windows được xem là một lời gọi hệ thống. Hoặc
Các lời gọi hệ thống
• Là giao diện lập trình đến các dịch vụ hệ thống được cung cấp bởi OS
• Thường được viết bằng ngôn ngữ bậc cao (C hay C++)
• Các chương trình thường truy nhập đến các lời gọi hệ thống thông qua giao diện chương
trình ứng dụng (API) (không gọi trực tiếp các lời gọi hệ thống)
• Ví dụ: Win32 API, POSIX API, Java AP Hoặc
- Lời gọi hệ thống là việc một chương trình máy tính yêu cầu một dịch vụ từ nhân
của hệ điều hành mà nó được thực thi. - Tác dụng:
• Dùng để giao tiếp giữa tiến trình và hệ điều hành
• Cung cấp giao diện giữa tiến trình và hệ điều hành
Chương 2. Quản lý tiến trình 1. Định nghĩa tiến trình
-Trong chương I chúng ta đã có khái niệm về tiến trình: Tiến trình là một bộ phận của một
chương trình đang thực hiện, đơn vị thực hiện tiến trình là processer
-Định nghĩa của Saltzer: Tiến trình là một chương trình do một processor logic thực hiện.
-Định nghĩa của Horning & Rendell: Tiến trình là một quá trình chuyển từ trạng thái này sang
trạng thái khác dưới tác động của hàm hành động, xuất phát từ một trạng thái ban đầu nào đó. Hoặc
• Một Hệ điều hành thực hiện nhiều chương trình
• Hệ thống xử lý theo lô: công việc (job)
• Hệ thống chia sẻ thời gian: tác vụ (task)
• Ở đây chúng ta dùng tiến trình và công việc với cùng ý nghĩa 2.
Các trạng thái của tiến trình
• new : Tiến trình vừa được tạo.
• ready :Tiến trình đã có đủ tài nguyên, đang chờ được cấp CPU để chạy.
• running :Các lệnh của tiến trình đang được thực thi.
• waiting (hay blocked) : Tiến trình đợi I/O hoàn tất.
• terminated : Tiến trình đã kết thúc (đã thực thi xong). 3.
Khối điều khiển tiến trình (PCB) Process Control Block 4.
Các kiểu tiến trình: độc lập, hợp tác, song song, tuần tự
5. Tiến trình cha, con, các tiến trình cha con dùng chung cái gì? ? Chung tài nguyên do hđh cấp phát
6. Ngữ cảnh tiến trình là gì, gồm những gì? chứa giá trị các thanh ghi, trạng thái tiến trình và
thông tin quản lý bộ nhớ
7. Nhiệm vụ của bộ điều phối, bộ phân phối
Việc chọn thời điểm dừng của tiến trình đang hoạt động (đang chiến giữ processor) để thu hồi
processor chuyển cho tiến trình khác hay việc chọn tiến trình tiếp theo nào trong số các tiến trình
đang ở trạng thái sẵn sàng để cấp processor là những vấn đề khá phức tạp đòi hỏi hệ điều hành
phải có một cơ chế điều phối thích hợp thì mới có thể tạo ra được hiệu ứng song song giả và sử
dụng tối ưu thời gian xử lý của processor. Bộ phận thực hiện chức năng này của hệ điều hành
được gọi là bộ điều phối (dispatcher) tiến trình.
Bộ phân phối phải giải quyết vấn đề cấp phát tài nguyên cho các tiến trình
8. Giờ CPU là gì? (là thời gian mà CPU phục vụ cho tiến trình hoạt động)
9. Các trạng thái của tiến trình liên quan đến giờ CPU (ready, running, waiting)
10. Khái niệm lập lịch CPU
11. Các thuật toán lập lịch một hàng đợi
▪ Đến trước–Phục vụ trước (FCFS)
▪ Công việc ngắn nhất trước (SJF)
▪ Lập lịch với độ ưu tiên(SRN)(SRT)
▪ Lập lịch Round-Robin (RR)
12. Lập lịch nhiều hàng đợi (MLQ, MLFQ)
Chương 4 Đồng bộ tiến trình
1. Bài toán đoạn tới hạn (đoạn găng)
n tiến trình cùng muốn truy cập đến dữ liệu chia sẻ
Mỗi tiến trình có một đoạn mã gọi là “đoạn tới hạn”, trong “đoạn tới hạn”dữ liệu chia sẻ
mới được truy cập tới.
Vấn đề - đảm bảo rằng khi một tiến trình đang trong đoạn tới hạn của nó, các tiến trình
khác không được phép thực thi đoạn tới hạn của chúng.
2. Các phương pháp giải quyết bài toán đoạn tới hạn: Peterson, khoá trong (tt Dekker), kiểm tra và
xác lập, đèn hiệu, dùng trình thư ký (monitor), tổ chức liên lạc giữa các tiến trình
Giải pháp của Peterson
• Giải pháp đồng bộ cho hai tiến trình • Giả sử hai lệnh LOAD và STORE là các lệnh
nguyên tử (thao tác không thể phân chia)
• Các tiến trình chia sẻ các biến sau: • int turn; • Boolean flag[2];
• Biến turn cho biết tiến trình nào được vào đoạn tới hạn.
• Mảng flag chỉ xem liệu một tiến trình có sẵn sàng vào đoạn tới hạn hay không.
• flag[i] = true là tiến trình Chương 5 Bế tắc 1. Hiện tượng bế tắc:
Một tập các tiến trình bị block, mỗi tiến trình giữ một tài nguyên và chờ một tài nguyên bị
chiếm giữ bởi một tiến trình khác trong tập
2. Điều kiện xảy ra bế tắc
Bế tắc có thể xảy ra nếu cả bốn điều kiện sau xảy ra đồng thời
a. Loại trừ lẫn nhau: chỉ một tiến trình được sử dụng tài nguyên tại một thời điểm.
b. Giữ và chờ: một tiến trình giữ ít nhất một tài nguyên và chờ các tài nguyên
khác đang được giữ bởi các tiến trình khác.
c. Không chiếm đoạt: một tài nguyên chỉ có thể được giải phóng một cách tự
nguyện bởi tiến trình giữ nó, sau khi tiến trình đó hoàn thành công việc của nó.
d. Chờ đợi vòng tròn: Một tập các tiến trình đang chờ {P0, P1, …, Pn} , trong
đó P0 chờ một tài nguyên bị giữ bởi P1, P1 chờ một tài nguyên bị giữ bởi P2,
…, Pn–1chờ một tài nguyên được giữ bởi Pn, và Pn đang chờ một tài nguyên P0 3. Cách phòng bế tắc
Yêu cầu hệ thống phải có trước một số thông tin (prior information available).
• Mô hình đơn giản: mỗi tiến trình khai báo số tài nguyên lớn nhất thuộc mỗi loại mà nó cần.
• Thuật toán tránh bế tắc kiểm tra trạng thái phân phối tài nguyên để đảm bảo
rằng không bao giờ có điều kiện “chờ đợi vòng tròn” xảy ra.
• Trạng thái phân phối tài nguyên được xác định bằng số các tài nguyên rỗi, số
tài nguyên đã được phân phối và số cực đại yêu cầu của các tiến trình
4. Đồ thị cấp phát tài nguyên (HÌNH ẢNH TRONG ĐIỆN THOẠI)
❖ Có một tập các đỉnh V và một tập các cạnh E
➢ V được chia thành hai tập:
• P = {P1, P2, …, Pn}, tập chứa tất cả các tiến trình trong hệ thống.
• R = {R1, R2, …, Rm}, tập chứa tất cả các kiểu tài nguyên trong hệ thống.
➢ Cạnh request – cạnh có hướng Pi ⟶ Rj
➢ Cạnh assignment – cạnh có hướng Rj ⟶ Pi Chương 6. Bộ nhớ chính
1. Nhiệm vụ quản lý bộ nhớ của HĐH
Để có hiệu suất sử dụng CPU và thời gian đáp ứng tốt, hệ điều hành cần dùng giải thuật
quản lý bộ nhớ thích hợp
Các nhiệm vụ của thành phần
Theo dõi, quản lý các vùng nhớ trống và đã cấp phát
Quyết định sẽ nạp chương trình nào khi có vùng nhớ trống
Cấp phát và thu hồi các vùng nhớ 2.
Khái niệm địa chỉ luận lý (logic), địa chỉ vật lý (physical)
Khái niệm không gian địa chỉ luận lý gắn với không gian địa chỉ vật lý là trung tâm của
các kĩ thuật quản lý bộ nhớ
 Các địa chỉ luận lý – được sinh ra bởi CPU; còn được gọi là địa chỉ ảo
 Địa chỉ vật lý – địa chỉ thật trong bộ nhớ, thấy được bởi đơn vị quản lý bộ nhớ 3.
Các cấu trúc cơ bản của chương trình (tuyến tính, phân đoạn, overlay, động) 4.
Các sơ đồ quản lý bộ nhớ (phân hoạch, tráo đổi, phân đoạn, phân trang) 5.
Các thuật toán FirstFit, BestFit, WorstFit Chương 7 Bộ nhớ ảo
1. Bộ nhớ ảo là gì? Đặc điểm
2. Các thuật toán thay trang FIFO, Optimal, LRU
Thuật toán vào trước ra trước (FIFO):
• Thay thế FIFO – Belady’s Anomaly: Nhiều frame → nhiều lỗi trang
Thuật toán tối ưu (Optimal algorithm):
• Thay trang sẽ không được sử dụng trong thời gian dài
• Được sử dụng để đánh giá hiệu suất thuật toán sử dụng
Thuật toán LRU (Least Recently Used): • Thực thi counter
• Mọi phần tử trang có một counter; mỗi lần trang được tham chiếu đến ⟶
cập nhật counter bằng thời điểm tham chiếu mới.
• Khi một trang cần thay đổi, xem xét các counter để xác định trang nạn nhân
Chương 8 Hệ thống tập tin
1. Phương pháp cấp phát liên tục, danh sách móc nối (liệt kê), chỉ số trong quản lý đĩa từ
• Mỗi file lưu trong một tập các khối liên tục trên đĩa
• Đơn giản – chỉ cần điểm bắt đầu (block #) và kích cỡ (số các blocks)
• Truy nhập ngẫu nhiên
• Không tận dụng không gian tối ưu
• Các file không thể thay đổi kích cỡ
2. Phương pháp bitmap trong quản lý đĩa từ (không gian trống)
• Cần phải bảo vệ:
• Con trỏ đến danh sách rỗi • Ánh xạ bit
• Phải được giữ trên đĩa
• Bản sao trong đĩa và trong bộ nhớ có thể khác nhau
• Không cho phép khối[i] ở trong trạng thái mà bit[i] = 1 trong bộ nhớ
và bit[i] = 0 trên đĩa • Giải pháp:
• Thiết lập bit[i] = 1 trong đĩa • Phân phối khối[i]
• Thiết lập bit[i] = 1 trong bộ nhớ
3. Phương pháp lập nhóm, đếm trong quản lý đĩa (không gian trống)
4. Một số kiểu tổ chức file của hệ điều hành: tổ chức thư mục hai mức, tổ chức thư mục theo cấu
trúc cây, tổ chức theo đồ thị không chu trình
Chương 9 Quản lý thiết bị 1. Nguyên lý hoạt động
2. Chiến lược quản lý thiết bị và vào /ra (Polling, Ngắt, DMA)
3. Trình điều khiển thiết bị
4. Cấu trúc vật lý của đĩa từ (disk, platter, head)
5. Cấu trúc luận lý của đĩa từ (track, cylinder, sector, cluster)
6. Định thời truy cập đĩa: các phương pháp First Come First Serve
(FCFS), Shortest-Seek-Time First (SSTF), SCAN, C-SCAN (Circular SCAN), C-LOOK