Giải chi tiết đề thi Giữa kỳ Môn Hệ điều hành | Đại học Bách Khoa Hà Nội

lOMoAR cPSD| 61552889
Giải chính: Nguyễn Công Hùng, Phạm Quang Anh, Nguyễn Minh Tú - IT1 K67 Ghi
chú: Kiến thức trích ở slide Handouts thầy Phạm Đăng Hải.
Link youtube record thầy Hải:
https://www.youtube.com/playlist?
list=PLgaUq0lEBS4Z5aZvZ0IBeigFZ_wBcnOVC
Đề thi Giữa kì IT3070 K66 Ngày thi 08 /06/ 2023 ĐỀ TRẮC NGHIỆM
Câu 1. Giải thuật điều phối Prossesor không độc quyền và ưu tiên tiến trình ngắn là
A. RR (Round Robin, Không độc quyền nhưng không ưu tiên tiến trình ngắn)
B. SJF (Shortest Job First, vừa có thể độc quyền vừa có thể không)
C. SRTF (short remaining Time First, đây là một kiểu SJF, ưu tiên tiến trình ngắn, không độc quyền) D. SJN => short job next
E. FCFS (First Come Fist Sevice, độc quyền)
Đến trước phục vụ trước (FCFS: First Come, First Served) Nguyên tắc:
- Tiến trình được quyền sử dụng CPU theo trình tự xuất hiện
- Tiến trình sở hữu CPU tới khi kết thúc hoặc chờ đợi vào ra Đặc điểm
- Đơn giản, dễ thực hiện
- Tiến trình ngắn phải chờ đợi như tiến trình dài
Công việc ngắn trước (SJF: Shortest Job First) Nguyên tắc:
- Mỗi tiến trình lưu trữ thời gian của chu kỳ sử dụng CPU tiếp theo
- Tiến trình có thời gian sử dụng CPU ngắn nhất sẽ sở hữu CPU
- Hai phương pháp o Không trưng dụng CPU => Độc quyền
o Có trưng dụng CPU (SRTF: Shortest Remaining Time First) => Không
độc quyền và ưu tiên tiến trình ngắn
- Đặc điểm SJF (SRTF) là tối ưu: Thời gian chờ đợi trung bình nhỏ nhất
- Không thể biết chính xác thời gian của chu kỳ sử dụng CPU. Dự báo dựa trên
những giá trị trước đó lOMoAR cPSD| 61552889
Vòng tròn (RR: Round Robin Scheduling) Nguyên tắc:
- Mỗi tiến trình được cấp một lượng tử thời gian τ để thực hiện
- Khi hết thời gian, tiến trình bị trưng dụng processor và được đưa vào cuối
hàng đợi sẵn sàng => Không độc quyền
- Nếu có n tiến trình, thời gian chờ đợi nhiều nhất (n − 1)τ
Vấn đề: Lựa chọn lượng tử thời gian τ
Câu 2. Hãy chỉ ra thuật ngữ không nằm cùng nhóm với các thuật ngữ còn lại
(Chương III slide 45) A. First-Fit B. Buddy Allocation C. Next-Fit D. LRU (Least Recently Used) E. Best-Fit
A, C, B, E => Chiến lược phân chương động
D => Chiến lược đổi trang
(* Phần dữ liệu sau dành cho các câu 3-4 *)
Giả thiết có 5 tiến trình đang trong trạng thái sẵn sàng thức hiện với các tham số như
sau (thời gian tính theo đơn vị ms): Tiến trình Thời gian thực hiện thời điểm xuất hiện P1 7 0 P2 3 1 P3 4 2 P4 2 3 P5 5 4
Câu 3. Thời gian chờ đợi trung bình khi áp dụng thuật đoán điều độ SJF là A. 7,0 B. 8,8 D. 6,8 E. 5,0
C. Tất cả các giá trị trên đều sai
SJF: Công việc ngắn trước
Thực hiện các việc lần lượt theo thứ tự: P1, P4, P2, P3, P5 Thời
gian chờ đợi của mỗi tiến trình:
P1: 0; P4: 7 – 3 = 4; P2:9 – 1 = 8; P3:12 – 2 = 10; P5: 16 – 4 = 12 lOMoAR cPSD| 61552889
Vậy thời gian chờ trung bình là: (0 + 4 + 8 + 10 + 12)/5 = 6,8
Câu 4. Thời gian chờ đợi trung bình khi áp dụng thuật đoán điều độ FCFS là A. 7.4 B. 8,4 D. 9,0 E. 9,4
C. Tất cả các giá trị trên đều sai
[0 + (7 – 1) + (10 – 2) + (14 – 3) + (16 – 4)]/5 = 7,4
Câu 5. Hãy chọn phát biểu hợp lý nhất. Lời gọi hệ thống trong hệ điều hành
nhằm mục đích (Câu này hơi phân vân giữa C và D)
A. Khởi tạo, hủy bỏ và đồng bộ các tiến trình trong hệ thống
B. Cấp phát, thu hồi bộ nhớ đã cấp
C. Sử dụng các dịch vụ của hệ điều hành
D. Quản lý tài nguyên trong hệ thống
E. Không có câu trả lời nào đúng
Bởi vì phân loại lời gọi hệ thống đều là quản lý
Lời gọi hệ thống cung cấp một giao tiếp giữa tiến trình và hệ điều hành Phân
loại lời gọi hệ thống:
- Quản lý tiến trình: khởi tạo tiến trình, huỷ tiến trình..
- Quản lý bộ nhớ: cấp phát và giải phóng bộ nhớ...
- Quản lý file: tạo mới, xoá, đọc và ghi file...
- Quản lý thiết bị vào ra: thực hiện trao đổi vào/ra...
- Trao đổi thông tin với hệ thống lấy/đặt ngày giờ...
- Truyền thông liên tiến trình
Câu trả lời chính xác nhất là: C. Sử dụng các dịch vụ của hệ điều hành. Giải thích: •
Lời gọi hệ thống (system call) là cơ chế giao tiếp giữa chương trình ứng dụng và hệ điều hành. •
Chương trình ứng dụng sử dụng lời gọi hệ thống để yêu cầu hệ điều hành thực hiện các
hành động mà nó không thể thực hiện trực tiếp, ví dụ như: o Truy cập và quản lý tài nguyên
hệ thống (như bộ nhớ, CPU, thiết bị I/O) o Tạo, hủy bỏ và đồng bộ các tiến trình
o Giao tiếp mạng o Quản lý tập
tin và thư mục o Cung cấp các dịch vụ bảo mật lOMoAR cPSD| 61552889 Ví dụ: •
Khi bạn mở một tập tin, chương trình ứng dụng sẽ thực hiện một lời gọi hệ thống để yêu
cầu hệ điều hành mở tập tin đó. •
Khi bạn gửi email, chương trình ứng dụng email sẽ thực hiện một lời gọi hệ thống để yêu
cầu hệ điều hành kết nối với máy chủ email và gửi email đi.
Các lựa chọn khác không chính xác vì lý do sau: •
A. Khởi tạo, hủy bỏ và đồng bộ các tiến trình trong hệ thống: Đây là một chức năng
của hệ điều hành, nhưng nó không phải là mục đích chính của lời gọi hệ thống. •
B. Cấp phát, thu hồi bộ nhớ đã cấp: Đây là một chức năng quan trọng khác của hệ điều
hành, nhưng nó cũng không phải là mục đích chính của lời gọi hệ thống. •
D. Quản lý tài nguyên trong hệ thống: Lời gọi hệ thống đóng góp vào việc quản lý tài
nguyên hệ thống, nhưng nó không phải là chức năng duy nhất của nó. •
E. Không có câu trả lời nào đúng: Đây là lựa chọn sai. Lời gọi hệ thống có một mục đích
rõ ràng và quan trọng trong hệ điều hành.
Do đó, lựa chọn C là lựa chọn chính xác nhất.
Câu 6. Yêu cầu nào dưới đây thuộc về tính an toàn của hệ điều hành (câu này
là phần TÍNH CHẤT CƠ BẢN CỦA HỆ ĐIỀU HÀNH CHƯƠNG I)
A. Thích nghi với thay đổi trong tương lai (Tổng quát theo thời gian) Tổng quát
- Hệ thống phải có tính kế thừa.
- Các thao tác, thông báo không được thay đổi
- Nếu thay đổi: thông báo và hướng dẫn cụ thể (chkdsk/scandisk)
- Đảm bảo tính kế thừa duy trì và phát triển người sử dụng
- Hệ thống cần phải có khả năng thích nghi với những thay đổi có thể xảy ra Ví dụ: Vấn đề Y2K; FAT 12/16/32
B. Nhiều mức khai thác với hiệu quả khác nhau (Thuận tiện) Thuận tiện - Dễ sử dụng
- Nhiều mức với hiệu quả khác nhau
- Có hệ thống trợ giúp phong phú
C. Thiết bị chậm không ảnh hưởng tới hệ thống (Hiệu quả) Hiệu quả -
Các tài nguyên phải được khai thác triệt để: Tài nguyên hạn chế vẫn giải quyết
được những yêu cầu phức tạp. lOMoAR cPSD| 61552889 -
Hệ thống cần phải duy trì được tính đồng bộ: Các thiết bị tốc độ chậm không
ảnh hưởng tới hoạt động của toàn hệ thống
D. Hoạt động phải chính xác tuyệt đối (Độ tin cậy cao)
Độ tin cậy cao: Mọi hoạt động, thông báo của HĐH phải chuẩn xác
- Cung cấp thông tin chỉ khi chắc chắn đúng. Khi gặp lỗi: thông
báo và ngừng xử lý hoặc trao quyền quyết định cho người dùng
- Cần có hỗ trợ từ thiết bị
E. Không bị truy nhập bất hợp lệ (An toàn) An toàn
- Dữ liệu và chương trình phải được bảo vệ o Không bị thay đổi ngoài ý muốn
và trong mọi chế độ làm việc
o Hạn chế truy nhập bất hợp pháp
- Các tài nguyên khác nhau có yêu cầu bảo vệ khác nhau
- Bảo vệ nhiều mức với nhiều công cụ khác nhau
- Quan trọng với hệ điều hành đa nhiệm
Câu 7. "Hệ điều hành cần phải có nhiều mức khái thác khác nhau với hiệu quả
ứng với trình độ và kinh nghiệm của người dung” là tính chất A. An toàn
B. Thuận tiện (Nhiều mức với hiệu quả khác nhau)
C. Tổng quát theo thời gian D. Hiệu quả E. Tin cậy cao
Theo lý thuyết đã nêu ở câu 6.
Câu 8. “Hệ điều hành là hệ thống chương trình nhằm tạo ra một máy ảo trên một
máy vật lý" là quan điểm của: A. Người dùng B. Quản lý D. Hệ thống E. Kỹ thuật
C. Tất cả các quan niệm trên Slide trang 50 chương I Góc độ quan sát
- Các đối tượng khác nhau có yêu cầu khác nhau về HĐH
- Nhiều góc độ quan sát đánh giá ⇒ nhiều định nghĩa o Người sử dụng Là
hệ thống chương trình phục vụ khai thác hệ thống tính toán một cách thuận lợi lOMoAR cPSD| 61552889
o Người quản lý Là hệ thống chương trình phục vụ quản lý chặt chẽ và
sử dụng tối ưu các tài nguyên của hệ thống tính toán
o Quan điểm kỹ thuật Là một hệ thống chương trình trang bị cho một
máy tính cụ thể để tạo ra một máy tính logic mới với tài nguyên mới và khả năng mới
o Quan điểm hệ thống Là một hệ thống mô hình hoá, mô phỏng hoạt
động của máy tính, của người sử dụng và của các thao tác viên, hoạt
động trong chế độ đối thoại nhằm tạo môi trường khai thác thuận lợi hệ
thống máy tính và quản lý tối ưu tài nguyên của hệ thống. Câu 9. Mục
đích chính của hệ điều hành trong giai đoạn phần cứng rẻ, nhân công đắt là:
A. Giảm thời gian rảnh rỗi của Processor
B.Tăng khả năng phòng chống tấn công từ bên ngoài
C.Giảm thời gian chờ đợi của người dùng
D.Tăng tốc độ hoạt động của các thiết bị vào ra
E. Tiết kiệm năng lượng tiêu thụ
Câu 10. Cho hệ thống gồm 5 tiến trình và 3 tài nguyên với số lượng (3, 14, 12).
Nhu cầu cực đại và lượng tài nguyên đã cấp cho trong bảng sau. A B C A B C P1 0 0 1 P1 0 0 1 P2 1 7 5 P2 1 0 0 P3 2 3 5 P3 1 3 5 P4 0 6 5 P4 0 6 3 P5 0 6 5 P5 0 0 1 MAX ALOCATION
Hãy chọn câu trả lời đúng nhất A B C P1 0 0 0 P2 0 7 5 P3 1 0 0 P4 0 0 2 P5 0 6 4 Bảng NEED NEED = MAX – ALOCATION
Tài nguyên còn lại hiện có là (A, B, C) = (1,5, 2) lOMoAR cPSD| 61552889
Từ bảng NEED ta có P1 an toàn vì NEED(P0) = (0, 0 ,0)
Cũng có P3 an toàn vì NEED(P3) = (1, 0, 0) <= (1, 5, 2) => P3 hoàn thành, trả lại
tài nguyên cho hệ thống => tài nguyên hiện có là (1, 5, 2) + (1, 3, 5) = (2, 8, 7)
Như vậy các tiến trình còn lại hoàn toàn có thể an toàn theo nhiều thứ tự
Trong đó có thứ tự P1, P3, P5, P2, P4
A. Hệ thống an toàn với dãy: P1, P2, P3, P4, P5
B. Hệ thống an toàn với dãy: P1, P3, P5, P2, P4
C.Hệ thống không an toàn
D. Hệ thống an toàn với dãy: P1, P5, P2, P3, P4
E. Hệ thống an toàn với dãy: P5, P3, P1, P4, P2
Câu 11. Một hệ thống được quản lý theo chiến lược kết hợp phân trang phân
đoạn với kích thước trang vật lý là 1000 bytes (để đơn giản trong tính toán).
Một chương trình gồm 5 đoạn lần lượt có kích thước là 12234bytes, 7434bytes,
24668bytes, 5456bytes và 7910bytes. Biết rằng khi thực hiện chương trình, bảng
quản lý đoạn và bảng quản lý trang luôn được nạp vào các trang độc lập. Nếu
nạp toàn bộ chương trình khi thực hiện, cần bao nhiêu
trang vật lý (kể cả các trang dành cho phần quản lý) A. 60 B. 72 D. 65 E. 66
C. Tất cả các đáp án khác đều sai
(Lý thuyết trong slide 79 chương III)
Gọi [X] là làm tròn lên của X. Ví dụ X = 5,1 thì [X] = 6
- Số trang cho các đoạn: [12234/1000] + [7434/1000] + [24668/1000] +
[5456/1000] + [7910/1000] = 13 + 8 + 25 + 6 + 8 = 60
- Số trang cần thiết cho bảng quản lý đoạn: 1
- Số trang cần thiết cho bảng quản lý trang: 5 bảng cho từng đoạn
Số trang cần thiết nếu nạp toàn bộ chương trình khi thực hiện là: 60 + 1 + 5 = 66
Câu 12. Giải thuật điều độ nào được cho rằng KHÔNG gây ra hiện tượng chờ
đợi tích cực (Phần tài nguyên găng) A. Kiểm tra và xác lập (phải chờ đợi tích cực)
B. Kỹ thuật đèn báo (Không tồn tại hiện tượng chờ đợi tích cực)
C. Phương pháp khóa trong (phải chờ đợi tích cực)
D. Thuật toán Kiểm tra và xác lập mở rộng (Phải chờ đợi tích cực)
E. Thuật toán Dekker (phải chờ đợi tích cực) lOMoAR cPSD| 61552889
Đọc slide trang 120 – 140 Phương pháp khóa trong. Nguyên tắc:
- Mỗi t/trình dùng một byte trong vùng nhớ chung làm khóa o Tiến
trình vào đoạn găng, đóng khoá (byte khóa: true) o Tiến trình thoát
khỏi đoạn găng, mở khóa (byte khóa: false)
- Tiến trình muốn vào đoạn găng: kiểm tra khóa của tiến trình còn lại o Đang khóa ⇒ Đợi
o Đang mở ⇒ Được quyền vào đoạn găng Nhận xét
- Điều độ chưa hợp lý: Hai t/trình yêu cầu tài nguyên tại một thời điểm
o Vấn đề loại trừ lẫn nhau (trường hợp 1) o Vấn đề tiến triển (trường hợp 2)
- Nguyên nhân: Do tách rời giữa o Kiểm tra quyền vào đoạn găng =>
Phải chờ đợi tích cực o Xác lập quyền sử dụng tài nguyên găng
Chờ đợi tài nguyên (busy waiting): trước khi vào đoạn găng
- Khi chờ đợi vẫn phải thực hiện kiểm tra quyền vào đoạn găng => Lãng
phí thời gian của processor
Câu 13. Hệ thống thực hiện nạp lần lượt từng chương trình vào bộ nhớ để thực
hiện. Khi một chương trình kết thúc hệ thống sẽ tự động nạp chương trình tiếp
theo vào bộ nhớ được gọi là: (Chương I slide 54 – 59 Phân loại hệ điều hành)
A. Hệ thống xử lý theo lô đơn chương trình
- Thực hiện các chương trình lần lượt theo những chỉ thị đã được xác định trước.
- Khi một chương trình kết thúc, hệ thống tự động thực hiện chương trình tiếp
theo mà không cần sự can thiệp từ bên ngoài
- Phải tồn tại bộ giám sát thực hiện dãy các công việc và bộ giám sát phải thường trú trong hệ thống
- Đòi hỏi tổ chức hàng đợi công việc
- Vấn đề: khi chương trình truy nhập thiết bị vào/ra; processor rơi vào trạng thái chờ đợi
B. Hệ thống xử lý theo lô đa chương trình
- Cho phép thực hiện nhiều chương trình đồng thời => Duy trì nhiều chương
trình trong bộ nhớ o Nạp một phần mã và dữ liệu của các chương trình/tiến
trình vào bộ nhớ (phần còn lại sẽ được nạp tại thời điểm thích hợp). Chương
trình sẵn sàng được thực hiện => Nạp một phần chương trình cần thực thi vào bộ nhớ khi thực hiện lOMoAR cPSD| 61552889
o Thực hiện chương trình như hệ thống đơn chương trình o Nếu chương
trình thực hiện vào ra, processor được chuyển giao cho chương trình đang
sẵn sàng khác => Chuyển processor cho tiến trình khác khi tiến trình đang
thực hiện yêu cầu vào ra.
- Tiết kiệm bộ nhớ (không cần nạp toàn bộ chương trình vào bộ nhớ)
- Hạn chế thời gian rỗi của processor
- Chi phí cao cho điều phối processor. Chương trình nào tiếp theo sẽ được sử dụng processor?
- Giải quyết vấn đề chia sẻ bộ nhớ giữa các chương trình => Bảo vệ không gian
nhớ giữa các tiến trình
C. Hệ thống phân chia thời gian
- Chia sẻ thời gian của processor cho các chương trình/tiến trình đang sẵn sàng thực hiện
- Nguyên tắc giống như hệ thống xử lý theo lô đa chương trình (nạp một phần của các chương trình)
- Processor được phân phối lại phụ thuộc chủ yếu vào sự điều phối của hệ điều
hành ⇒ Điều phối như thế nào? ⇒ Chương 2
- Thời gian hoán đổi giữa các tiến trình nhỏ, các chương trình cảm giac song song
Thường được gọi: Hệ điều hành đa nhiệm (Windows)
D. Hệ thống thời gian thực
- Được sử dụng chủ yếu trong lĩnh vực điều khiển.
- Giải quyết bài toán không muộn hơn một thời điểm nào đó o Mỗi bài toán
có một hạn định (deadline)
o Hệ thống phải cho kết quả chính xác trong khoảng thời gian xác định
- Hệ điều hành này đòi hỏi sự phối hợp cao giữa phần mềm và phần cứng. E. Hệ thống song song
- Xây dựng cho các hệ thống có nhiều bộ vi xử lý
- Nhiều VXL, công việc thực hiện nhanh chóng hơn (Amdahl 67)
- Độ tin cậy cao: hỏng một VXL không ảnh hưởng đến hệ thống - Ưu
thế hơn hệ thống nhiều máy có một VXL vì cùng chia xẻ
bộ nhớ, thiết bị ngoại vi..
- Đa xử lý đối xứng (SMP: symmetric) lOMoAR cPSD| 61552889
- Mỗi bộ xử lý chạy một tiến trình/luồng
- Các VXL giao tiếp với nhau thông qua một bộ nhớ dùng chung
- Cơ chế chịu lỗi và khả năng cân bằng tải tối ưu
- Vấn đề: Đồng bộ giữa các VXL - Ví dụ: HĐH WinNT
- Đa xử lý không đối xứng (ASMP: asymmetric)
- Một bộ xử lý chính kiểm soát toàn bộ hệ thống
- Các bộ xử lý khác thực hiện theo lệnh của bộ xử lý chính hoặc
theo những chỉ thị đã được định nghĩa trước
- Mô hình theo dạng quan hệ chủ tớ: Bộ xử lý chính lập lịch cho các bộ xử lý khác
Câu 14. Chọn phải biểu KHÔNG chính xác về đồ thị chờ đợi
A. Thu được từ đồ thị cung cấp tài nguyên
B. Các cung trên đồ thị biểu diễn mỗi quan hệ chờ đợi giữa các tiến trình trong hệ thống
C. Trên đồ thị có chu trình, hệ thống có bế tắc (trên đồ thị có chu trình thì hệ thống
rơi vào trạng thái không an toàn chứ không hẳn là bế tắc)
D.Không tồn tại các đỉnh kiểu tài nguyên
E. Chỉ sử dụng hiệu quả khi các tài nguyên có đúng một đơn vị
Một chương trình có cấu trúc theo chiến lược phân đoạn, Khi thực hiện, bảng
quản lý đoạn của chương trình có giá trị như bảng SCB bên dưới lOMoAR cPSD| 61552889
Với các yêu cầu truy được cho trong bảng Địa chỉ logic ở trên, hãy cho biết địa
chỉ logic nào sinh ra kết quả sau (Câu trả lời là E nếu không có địa chỉ logic nào
thỏa mãn) Cấu trúc phân đoạn
- Chương trình là tập hợp các đoạn (modul,segment) o Tên đoạn (số hiệu
đoạn), độ dài của đoạn o Mỗi đoạn có thể được biên tập riêng.
- Dịch và biên tập chương trình tạo ra bảng quản lý đoạn (SCB: Segement
Control Block) o Mỗi phần tử của bảng ứng với một đoạn của
chương trình o Dấu hiệu (Mark (0/1)): Đoạn đã tồn tại trong
bộ nhớ o Địa chỉ (Address): Vị trí cơ sở (base) của đoạn trong bộ nhớ
o Độ dài (Length): Độ dài của đoạn
- Địa chỉ truy nhập: tên (số hiệu) đoạn và độ lệch trong đoạn
Vấn đề: Chuyển đổi từ địa chỉ 2 chiều ⇒ địa chỉ một chiều
Câu 15 Địa chỉ vật lý 682 (A) (B) (C) (D) (E) 682 = 252 + 430
Đoạn 0, offset = 430 => Chọn B
Câu 16. Địa chỉ vật lý 980 (A) (B) (C) (D) (E)
980 không nằm trong chương trình => Chọn E lOMoAR cPSD| 61552889
Câu 17. Lỗi truy nhập (A) (B) (C) (D) (E)
D là lỗi truy nhập do <4, 112> có 112 > 96 là length của đoạn 4
Câu 18. Địa chỉ vật lý 1530 thuộc về đoạn nào
A. Đoạn 0 B. Đoạn 1 D. Đoạn 2 E. Đoạn 3
C. Không thuộc về chương trình trên 1530 = 1327 + 203
Có 203 < 580 (Thỏa mãn) => thuộc đoạn 3
Câu 19. Hệ thống gồm 5 tiến trình, 3 tài nguyên với số lượng lần lượt là (3, 9,
12). Trạng thái cung cấp tài nguyên và yêu cầu tài nguyên của từng tiến trình
cho trong các bảng sau.
Hãy chọn câu trả lời đúng
A. Hệ thống không bế tắc
B. Hệ thống bế tắc với các tiến trình: P2, P3, P4
C. Hệ thống bế tắc với các tiến trình: P1, P4, P5
D. Hệ thống bế tắc với các tiến trình: P1, P3, P4
E. Hệ thống bế tắc với các tiến trình: P2, P3, P5
Tài nguyên hiện có là (A, B, C) = (3, 9, 12) - (1+1, 3+6, 1+5+3+1) = (1, 0, 2)
=> Giải quyết được P2 => tài nguyên hiện có là (1, 0, 2) + (1, 0, 0) = (2, 0, 2)
=> P5 được giải quyết => Tài nguyên hiện có là (2, 0, 2) + (0, 0, 1) = (2, 0, 3)
=> đến đây không giải quyết được tiến trình P1, P3, P4 => bế tắc lOMoAR cPSD| 61552889
Câu 20. Chọn giải thích hợp lý nhất cho phát biểu: Tiến trình đa luồng nhanh
hơn tiến trình đơn luồng
A. Luôn đúng. Do vậy trong các hệ điều hành tiên tiến mới sử dụng mô hình này
Sai bởi vì tiến trình đơn luồng nhanh hơn tiến trình đa luồng trong trường hợp khi
công việc chỉ chạy tuần tự hoặc tài nguyên nguyên hạn chế B. Đúng khi tiến trình
thực hiện nhiều tính toán. Sai bởi vì có thể thực hiện tính toán một cách tuần tự C.
Đúng khi tiến trình thực hiện nhiều vào ra.
D. Sai do tiến trình đa luồng và tiến trình đơn luồng có tốc độ thực hiện như nhau E.
Luôn sai, do phải tốn thời gian chuyển đổi giữa các luồng trong tiến trình đa luồng
Câu 21. "Tăng kích thước của bộ nhớ vật lý không làm thay đổi hiểu quả sử dụng
chương trình" là đặc điểm của cấu trúc chương trình nào dưới đây?: A.
Cấu trúc nạp động => Tăng kích thước => hiệu quả cao hơn, nạp được nhiều hơn B.
Cấu trúc Overlay => Modul được chia làm các mức, bộ nhớ cũng được chia
thành các mức ứng với các mức chương trình (Do người dùng chia) => Tăng kích
thước của bộ nhớ vật lý làm thay đổi kích thước bộ nhớ nhưng không thay đổi kích
thước các mức của chương trình mà chương trình yêu cầu nên không làm thay đổi hiệu quả sử dụng. C.
Cấu trúc liên kết động => Tăng kích thước => Liên kết được nhiều chương
trình hơn => Hiệu quả tăng D.
Cấu trúc phân đoạn => Hiệu quả sử dụng phụ thuộc vào cấu trúc chương trình
=> Tăng kích thước của bộ nhớ vật lý có thể giúp nạp được nhiều modul hơn 1 lúc,
tăng hiệu quả sử dụng E. Cấu trúc phân trang
Câu 22. Phát biểu nào dưới đây là đúng về bộ điều phối CPU (CPU-Scheduler)
(Slide 22 – 24 chương II)
A. Yêu cầu tốc độ thực hiện nhanh
B. Lựa chọn tiến trình trong Job queue
Sai vì phải lựa chọn tiến trình trong Ready queue C.
Được thực hiện không thường xuyên
Sai vì tính chất này là của bộ điều phối công việc
D. Quyết định số tiến trình tồn tại đồng thời trong bộ nhớ
Sai vì tính chất này là của bộ điều phối công việc
E. Tất cả các phát biểu trên đều sai
Bộ điều phối (Scheduler): Lựa chọn tiến trình trong các hàng đợi
- Điều phối công việc (Job scheduler; Long-term scheduler)
- Điều phối CPU (CPU scheduler; Short-term scheduler)
Điều phối công việc lOMoAR cPSD| 61552889
- Chọn các tiến trình từ hàng đợi tiến trình được lưu trong các vùng đệm
(đĩa từ) và đưa vào bộ nhớ để thực hiện
- Thực hiện không thường xuyên (đơn vị giây/phút)
- Điều khiển mức độ đa chương trình (số t/trình trong bộ nhớ )
- Khi mức độ đa chương trình ổn định, điều phối công việc được gọi chỉ khi
có tiến trình rời khỏi hệ thống
- Vấn đề lựa chọn công việc o Tiến trình thiên về vào/ra: sử dụng ít thời
gian CPU o Tiến trình thiên về tính toán: sử dụng nhiều thời gian CPU
o Cần lựa chọn lẫn cả 2 loại tiến tình ⇒ tt vào ra: hàng đợi sẵn sàng rỗng,
lãng phí CPU ⇒ tt tính toán: hàng đợi thiết bị rỗng, lãng phí thiết bị Điều phối CPU
- Lựa chọn một tiến trình từ hàng đợi các tiến trình đang sẵn sàng thực hiện và phân phối CPU cho nó
- Được thực hiện thường xuyên (VD: 100ms/lần) o Tiến trình thực hiện
vài ms rồi thực hiện vào ra
o Lựa chọn tiến trình mới, đang sẵn sàng - Phải thực hiện nhanh
o 10ms để quyết định ⇒10/(110)=9% thời gian CPU lãng phí
- Vấn đề luân chuyển CPU từ tiến trình này tới tiến trình khác o Phải lưu
trạng thái của tiến trình cũ (PCB) và khôi phục trạng thái cho tiến trình mới
o Thời gian luân chuyển là lãng phí o Có thể được hỗ trợ bởi phần cứng
- Vấn đề lựa chọn tiến trình (điều phối CPU)
Câu 23: ....486, nếu chế độ phân trang được kích hoạt thì số lần truy nhập bộ
nhớ để tính ra địa chỉ vật lý của một địa chỉ logic, là (không tính đến lần truy
nhập vào địa chỉ vật lý ứng với địa chỉ logic cần tim): A. 1 B. 2 D. 3 E. 4
C. Không có đáp án nào đúng
Câu 24. Giải thuật Dekker điều độ tiến trình qua đoạn găng KHÔNG đảm bảo điều kiện nào?
A. Chỉ một tiến trình sử dụng tài nguyên tại một thời điểm (Đúng do có sử dụng biến
turn để chỉ ra tiến trình được ưu tiên)
B. Khi tài nguyên tự do các tiến trình đều có thể sử dụng tài nguyên găng (Đúng) lOMoAR cPSD| 61552889
C. Không tiến trình nào phải đợi tài nguyên găng vô hạn (Đúng với giải thuật Dekker
nhưng không đúng với phương pháp khóa trong bởi vì Điều độ chưa hợp lý:
- Vấn đề loại trừ lẫn nhau (trường hợp 1)
- Vấn đề tiến triển (trường hợp 2)
D. Tiến trình không sử dụng processor khi đợi tới lượt sử dụng tài nguyên găng (Sai
do Tiến trình cần phải sử dụng processor để kiểm tra điều kiện trước khi vào đoạn
găng, chỉ có semaphore là block hẳn rồi wake up như vậy sẽ không cần sử dụng processor)
E. Các tiến trình phải chờ đợi khi tài nguyên găng đang bị tiến trình khác sử dụng (Đúng)
Nhận xét về giải thuật DEKKER:
- Điều độ hợp lý cho mọi trường hợp => C. Không tiến trình nào phải chờ đợi tài nguyên vô hạn
- Không đòi hỏi sự hỗ trợ đặc biệt của phần cứng nên có thể thực hiện bằng ngôn ngữ bất kỳ
- Quá phức tạp khi số tiến trình và số tài nguyên tăng lên
- Phải chờ đợi tích cực (busy waiting) trước khi vào đoạn găng Khi chờ đợi
vẫn phải thực hiện kiểm tra quyền vào đoạn găng Lãng phí thời gian của lOMoAR cPSD| 61552889
processor => E. Các tiến trình phải chờ đợi khi tài nguyên găng đang bị
tiến trình khác sử dụng
- Ghi chú: Thuật toán có thể thực hiện sai trong một số trường hợp o CPU
cho phép thực hiện các lệnh không đúng trật tự o Chương trình dịch thực
hiện tối ưu hóa khi sinh mã
 Các mã bất biến bên trong vòng lặp được đưa ra ngoài Câu 25.
Hãy chỉ ra phát biểu KHÔNG chính xác về luồng (thread) trong hệ diều hành
A. Mỗi tiến trình luôn phải tồn tại ít nhất một luồng thực thi. (Đúng)
B. Các luồng trong một tiến trình chia sẻ nhau không gian ngăn xếp của tiến trình (Sai)
C. Mô hình lập trình đa luồng cho phép tăng tính đáp ứng của hệ thống. (Đúng, đọc
phần Lợi ích của lập trình đa luồng slide trang 62 chương II)
D. Trên hệ thống đơn vị xử lý, thực chất các luồng trong một tiến trình thực hiện tuần tự (Đúng)
E. Các luồng trong một tiến trình dùng chung không gian địa chỉ. (Đúng)
Tiến trình >< Luồng Tiến trình Luồng
- Tiến trình có đoạn mã/dữ
- Luồng không có đoạn dữ liệu
liệu/heap & các đoạn khác hay heap riêng
- Phải có ít nhất một luồng trong
- Luồng không đứng riêng mà mỗi tiến trình
nằm trong một tiến trình
- Các luồng trong phạm vi một
- Có thể tồn tại nhiều luồng
tiến trình chia sẻ mã/dữ
trong mỗi tiến trình. Luồng đầu
liệu/heap, vào/ra nhưng có
là luồng chính và sở hữu không
stack và tập thanh ghi riêng
gian stack của tiến trình
- Thao tác khởi tạo, luân chuyển
- Thao tác khởi tạo và luân tiến trình tốn kém
chuyển luồng không tốn kém
- Bảo vệ tốt do có không gian điạ
- Không gian điạ chỉ chung, cần chỉ riêng phải bảo vệ
- Khi tiến trình kết thúc, các tài
- Luồng kết thúc, stack của nó
nguyên được đòi lại và các
luồng phải kết thúc theo được thu hồi
Câu 26. Hệ thống có 3 tiến trình dùng chung một tài nguyên găng. Nhu cầu tài
nguyên lớn nhất của mỗi tiến trình lần lượt là 4, 3, 5 đơn vị. Lượng đơn vị tài
nguyên nhỏ nhất để hệ thống không bao giờ rơi vào tình trạng bế tắc trong mọi
chế độ hoạt động là:
A. 5 B. 10 C.Tất cả các giá trị trên đều sai lOMoAR cPSD| 61552889 D. 8 E. 12 -
Giả sử tiến trình 1 chiếm 3 đơn vị => tiến trình chưa được hoàn thiện, vẫn ôm
đơn vị tài nguyên đó và cần đòi thêm 1 đơn vị tài nguyên nữa. -
Nếu Tiến trình 1 chiếm được 4 đơn vị => Tiến trình được hoàn thành => trả lại tài nguyên -
Do đó trường hợp ngốn tài nguyên nhất mà vẫn bế tắc của lần lượt cả 3 tiến
trình là 3, 2, 4 => 3 + 2 + 4 = 9 đơn vị => Nếu có thêm 1 đơn vị nữa thì sẽ có 1 tiến
trình được hoàn thành => Giải phóng bế tắc
=> Lượng đơn vị tài nguyên nhỏ nhất để tiến trình không bao giờ rơi vào tình trạng bế tắc là 10 đơn vị
Câu 27. Với 3 trạng thái của tiến trình: Sẵn sàng, Thực hiện và chờ đợi. Các
chuyển đổi có thể xảy ra là
A. Sẵn sàng → Thực hiện (có thể); Chờ đợi → Thực hiện (không thể)
B. Thực hiện → Sẵn sàng (có thể); Chờ đợi → Sẵn sàng (có thể)
C. Thực hiện → Chờ đợi (có thể); Sẵn sàng → Chờ đợi (Không thể)
D. Cả 3 cách chuyển đổi trên đều được
E. Cả 3 cách chuyển đổi trên đều sai
Câu 28. Điều kiện nào dưới đây KHÔNG có trong các điều kiện xảy ra bế tắc
A. Có xếp hàng chờ đợi trước khi vào đoạn găng B. Có tài nguyên găng
C. Có hệ thống phân phối lại tài nguyên (Phải là không có)
D. Có chờ đợi vòng tròn
E. Cả 4 điều kiện trên đều cần thiết để xảy ra bế tắc
Điều kiện xảy ra bế tắc: Điều kiện cần:
Cần có 4 điều kiện sau, không được thiếu điều kiện nào lOMoAR cPSD| 61552889
- Có tài nguyên găng
• Tài nguyên được sử dụng theo mô hình không phân chia được o Chỉ có một
tiến trình dung tài nguyên tại một thời điểm o Tiến trình khác cũng yêu cầu
tài nguyên ⇒ yêu cầu phải được hoãn lại tới khi tài nguyên được giải phóng
- Chờ đợi trước khi vào đoạn găng
• Tiến trình không được vào đoạn găng phải xếp hàng chờ đợi.
• Trong khi chờ đợi vẫn chiếm giữ các tài nguyên được cung cấp
- Không có hệ thống phân phối lại tài nguyên găng => Còn gọi là trưng dụng nguyên găng
• Tài nguyên không thể được trưng dụng
• Tài nguyên được giải phỏng chỉ bởi tiến trình đang chiếm giữ khi đã hoàn
thành nhiệm vụ - Chờ đợi vòng tròn
• Tồn tại tập các tiến trình {P0, P1, . . . , Pn} đang đợi nhau theo kiểu: P0 → R1
→ P1; P1 → R2 → P2; . . . Pn−1 → Rn → Pn; Pn → R0 → P0
• Chờ đợi vòng tròn tạo ra chu trình không kết thúc
(* Phần dữ liệu sau dành cho các câu hỏi 29, 30 *)
Hãy cho biết các trang còn lại trong bộ nhớ sau khi kết thúc các truy nhập sau:
1, 2, 3, 4, 2, 5, 4, 1, 3, 5, 3, 2, 3, 2; nếu hệ
thống có 3 trang vật lý và sử dụng:
Câu 29. Thuật toán đổi trang FIFO: A. 1, 2, 5 B. 1, 3, 5 D. 2, 3, 5 E. 1, 2, 3
C. Không có câu trả lời đúng
FIFO: First in, First out 1 2 3 4 2 5 4 1 3 5 3 1 1 1 4 4 4 4 4 3 3 3 3 3 3 2 2 2 2 5 5 5 5 5 5 2 2 2 3 3 3 3 3 1 1 1 1 1 1 1
Nạ Nạp Nạ 1 vào 2 có 2 vào p 1 2 p 3 đầu tiên sẵn trước rồi Tương tự vào vào vào nên nên nhường nhường nên Chỗ lại chỗ lại cho 4 không cho 5 thay lOMoAR cPSD| 61552889 đổi
Ở đây chỉ quan tâm đến xem trang nạp từ bao giờ, việc nạp lặp lại kiểu như 2 có sẵn
rồi nên không thay đổi không tác động gì, cứ cái nào vào trước ưu tiên cho cái sau
Câu 30. Thuật toán đổi trang LRU A. 1, 3, 4 B. 2, 4, 5 D. 1,3,5 E. 2, 3, 5
C. Không có câu trả lời đúng
LRU (Least Recently Used): Trang có lần sử dụng cuối cách lâu nhất
Nguyên tắc: Đưa ra trang có lần sử dụng cuối cách xa nhất 1 2 3 4 2 5 4 1 3 5 3 2 3 2 1 1 1 4 4 4 4 4 4 5 5 5 5 5 2 2 2 2 2 2 1 1 1 1 2 2 2 3 3 3 5 5 5 3 3 3 3 3 3
Ở đây cũng gần giống trên, bổ sung thêm là ví dụ cột số 5 nạp 2 là coi như bắt đầu
mới vào luôn, ko quan tâm 2 được nạp từ bao giờ. Vì thế ở cột số 6 thay vì thay 2
bởi 5 như FIFO thì ta phải thay 3 bởi 5 do 2 mới được nạp lại trước đó, 3 được xem
là tồn tại trong trang lâu hơn.
Trich lỏ của Tú: Tìm 3 số từ cuối, từ phải sang trái, 3 số đầu tiên khác nhau. Giải quiz thầy Hải Quiz 1:
Hệ thống xử lý theo lô đa chương trình lOMoAR cPSD| 61552889
- Cho phép thực hiện nhiều chương trình đồng thời => Duy trì nhiều chương
trình trong bộ nhớ o Nạp một phần mã và dữ liệu của các chương trình/tiến
trình vào bộ nhớ (phần còn lại sẽ được nạp tại thời điểm thích hợp). Chương
trình sẵn sàng được thực hiện => Nạp một phần chương trình cần thực thi vào bộ nhớ khi thực hiện
o Thực hiện chương trình như hệ thống đơn chương trình o Nếu chương
trình thực hiện vào ra, processor được chuyển giao cho chương trình
đang sẵn sàng khác => Chuyển processor cho tiến trình khác khi tiến
trình đang thực hiện yêu cầu vào ra (không phải là sau mỗi khoảng thời gian xác định)
- Tiết kiệm bộ nhớ (không cần nạp toàn bộ chương trình vào bộ nhớ)
- Hạn chế thời gian rỗi của processor
- Chi phí cao cho điều phối processor. Chương trình nào tiếp theo sẽ được sử dụng processor?
- Giải quyết vấn đề chia sẻ bộ nhớ giữa các chương trình => Bảo vệ không gian
nhớ giữa các tiến trình